Анализ компонентов окрестности - это метод обучения с учителем для классификации многомерных данных в отдельные классы в соответствии с заданной метрикой расстояния по данным. Функционально он служит тем же целям, что и алгоритм K-ближайших соседей , и напрямую использует связанную концепцию, называемую стохастическими ближайшими соседями .
Определение
Анализ компонентов соседства направлен на «изучение» метрики расстояния путем нахождения линейного преобразования входных данных, так что средняя эффективность классификации с исключением по одному (LOO) максимизируется в преобразованном пространстве. Ключевым моментом в алгоритме является то, что матрица соответствующее преобразованию, можно найти, задав дифференцируемую целевую функцию для с последующим использованием итеративного решателя, такого как спуск сопряженного градиента . Одним из преимуществ этого алгоритма является то, что количество классов можно определить как функцию , с точностью до скалярной постоянной. Таким образом, такое использование алгоритма решает проблему выбора модели .
Объяснение
Чтобы определить , мы определяем целевую функцию, описывающую точность классификации в преобразованном пространстве, и пытаемся определить таким образом, чтобы эта целевая функция была максимальной.
Классификация с исключением по одному (LOO)
Рассмотрите возможность прогнозирования метки класса отдельной точки данных на основе консенсуса ее -ближайшие соседи с заданной метрикой расстояния. Это называется классификацией с исключением по одному . Однако набор ближайших соседейможет быть совершенно другим после прохождения всех точек через линейное преобразование. В частности, набор соседей для точки может претерпевать дискретные изменения в ответ на плавные изменения элементов, подразумевая, что любая целевая функция основанный на соседях точки, будет кусочно-постоянным и, следовательно, не дифференцируемым .
Решение
Мы можем решить эту проблему, используя подход, вдохновленный стохастическим градиентным спуском . Вместо того, чтобы рассматривать-ближайшие соседи в каждой преобразованной точке в LOO-классификации, мы будем рассматривать весь преобразованный набор данных как стохастических ближайших соседей . Мы определяем их, используя функцию softmax квадрата евклидова расстояния между данной точкой классификации LOO и каждой другой точкой в преобразованном пространстве:
Вероятность правильной классификации точки данных вероятность отнести точки каждого из его соседей к одному классу :
где вероятность классификации соседа точки .
Определите целевую функцию, используя классификацию LOO, на этот раз используя весь набор данных в качестве ближайших стохастических соседей:
Обратите внимание, что при стохастических ближайших соседях консенсусный класс для одной точки ожидаемое значение класса точки в пределе бесконечного числа выборок, взятых из распределения по его соседям то есть: . Таким образом, предсказанный класс представляет собой аффинную комбинацию классов любой другой точки, взвешенную функцией softmax для каждой точки. где теперь весь преобразованный набор данных.
Такой выбор целевой функции предпочтительнее, поскольку она дифференцируема по (обозначить ):
Получение градиента дляозначает, что его можно найти с помощью итеративного решателя, такого как сопряженный градиентный спуск . Обратите внимание, что на практике большинство самых внутренних членов градиента оцениваются как незначительные вклады из-за быстро убывающего вклада удаленных точек от интересующей точки. Это означает, что внутренняя сумма градиента может быть усечена, что приведет к разумному времени вычислений даже для больших наборов данных.
Альтернативная формулировка
"Максимизация эквивалентно минимизации -расстояние между предсказанным распределением классов и истинным распределением классов (т.е. индуцированный все равны 1). Естественной альтернативой является KL-дивергенция, которая индуцирует следующую целевую функцию и градиент: "(Goldberger 2005)
На практике оптимизация использование этой функции дает результаты, аналогичные исходным.
История и предыстория
Анализ компонентов окружения был разработан Джейкобом Голдбергером, Сэмом Роуисом, Русланом Салахудиновым и Джеффом Хинтоном на факультете информатики Университета Торонто в 2004 году.
Смотрите также
Рекомендации
- Дж. Гольдбергер, Г. Хинтон, С. Роуейс, Р. Салахутдинов. (2005) Анализ компонентов соседства . Достижения в системах обработки нейронной информации. 17, 513-520, 2005.
Внешние ссылки
Программное обеспечение
- Библиотека MLPACK содержит C ++ реализации
- nca ( C ++ )
- реализация sklearn ( Python )