Технологии искусственного интеллекта. Задача выбора признаков при обучении с учителем

Задача выбора признаков заключается в том, чтобы найти такие признаки, значения которых мало меняются для объектов одного класса, но сильно меняются для объектов разных классов. Часто оказывается, что для надежного распознавания достаточно лишь небольшого числа таких признаков, так что выбор признаков может также приводить и к снижению размерности признакового пространства. Задача выбора признаков может возникать как при обучении с учителем, так и при обучении без учителя.

Исходные данные: алфавит классов ; набор векторов признаков признакового пространства Х: , для которых известна принадлежность классам. Обозначим через образы, принадлежащие k -тому классу, где – число образов в i -том классе, причем .

Образы, принадлежащие одному классу, должны быть похожи между собой или должны иметь близкие значения некоторых признаков. Однако могут присутствовать и признаки, которые сильно различаются для объектов данного класса. Таким образом, различные признаки могут в разной степени характеризовать тот или иной класс образов. Наилучшими будут инвариантные признаки, то есть признаки, одинаковые для всех образов класса. Из этих соображений задачу выбора признаков можно трактовать как задачу выбора инвариантных признаков. Однако для признаков с вещественными значениями характерна погрешность их измерения, поэтому задачу следует ставить как задачу присвоения весов , с которыми должны учитываться признаки в процессе классификации.

Мерой сходства двух образов является расстояние между ними. В случае евклидового расстояния с учетом весов получаем:

.

Следует найти такие веса, которые бы максимизировали среднее расстояние между образами различных классов и минимизировали среднее расстояние между образами, принадлежащими одному и тому же классу:

где – средние расстояния внутри множества и между двумя множествами соответственно (с учетом весов признаков). Для их вычисления необходимо усреднить расстояния между всеми парами точек, однако в случае евклидовой метрики вместо этого можно считать расстояния до векторов средних.

Пусть y^k – эталонный образ (вектор средних) k -го класса, тогда внутриклассовое расстояние может быть вычислено по формуле:

.

Преобразуем среднее внутриклассовое расстояние:

,

где – средняя по всем классам дисперсия i -го признака.

Расстояние между классами образов в простейшем случае может быть вычислено как расстояние между их эталонными образами:

.

Среднее расстояние между классами составит

,

где – среднее расстояние вдоль i -го признака между классами образов.

Тогда целевую функцию можно записать в виде:

.

Здесь дисперсии и зависят только от распределения образов внутри классов и от взаимного расположения классов, но не зависят от вектора параметров q.

Очевидно, для нахождения единственного минимума целевой функции необходимо ввести некоторое ограничение на вектор весов. В качестве такого ограничения можно использовать, например, условие нормировки:

.

Тогда получаем задачу нахождения условного экстремума, для которой необходимо составить функцию Лагранжа:

.

Используя условие экстремума, приравняв частные производные лангранжиана по q_i к 0, можно получить формулу для вычисления значений весов:

.

Однако если вычислять межклассовые расстояния как расстояния между эталонными образами, то веса могут получиться отрицательными. По этой и ряду других причин подобный способ вычисления расстояний между классами является не вполне корректным: правильнее считать среднее расстояние от образов одного класса до эталонного образа другого класса. В этом случае межклассовые расстояния всегда будут превосходить внутриклассовые.

Руководствуясь несколько другой эвристически сконструированной функцией потерь и условием , описывающим сохранение элемента объема, можно получить более удобные в использовании веса:

.

Использование евклидового расстояния в качестве меры сходства имеет очевидные ограничения. Более универсальным критерием является количество информации. В классическом (шенноновском) подходе среднее количество информации выражается через энтропию, для вычисления которой необходимо знать соответствующие вероятности.

Поскольку речь идет об обучении с учителем, можно полагать, что плотности распределения вероятностей p_k (x), k = 1, …, d для каждого класса вычислены. Тогда аналог расстояние от образа x до класса k будет равен , то есть собственному количеству информации, содержащейся в образе в предположении, что он принадлежит k -му классу. Связь количества информации с расстоянием становится очевидной, если в качестве плотности вероятностей подставить нормальное распределение.

Теперь вместо среднего внутриклассового расстояния мы можем использовать энтропию, вычисляемую по формуле:

Величина H_k определяет среднее количество информации, содержащееся в произвольном образе k -го класса, если известна его принадлежность этому классу. Аналог расстояния от класса l до класса k следует определить как среднее «расстояние» образов класса l до класса k:

Эта величина характеризует среднюю длину оптимального кода, кодирующего произвольный образ класса l в предположении, что он принадлежит классу k.

Как и выше для случая евклидового расстояния, нас интересует ситуация, в которой расстояния между классами образов максимальны, а внутриклассовые расстояния минимальны. Тогда в качестве целевой функции (при рассмотрении двух классов) следует взять величину

Эта величина выражает полную среднюю информацию для различения двух классов и обычно называется дивергенцией двух классов. Таким образом, концепция дивергенции позволяет строго ввести и оперировать степенью различия между классами. При этом также учитываются стохастические модели классов p_k (x).

Описанные выше подходы позволяют упорядочивать признаки по весам, то есть по степени их эффективности, и выбирать из них некоторое количество наиболее значимых для уменьшения размерности пространства признаков. Однако при этом не происходит построение новых признаков.