Анализ компонентов соседства

Анализ компонентов соседства — это контролируемый метод обучения для классификации многомерных данных в отдельные классы в соответствии с заданной метрикой расстояния по данным. Функционально он служит тем же целям, что и алгоритм K-ближайших соседей , и напрямую использует связанную концепцию, называемую стохастическими ближайшими соседями .

Определение

Анализ компонентов соседства направлен на «изучение» метрики расстояния путем нахождения линейного преобразования входных данных таким образом, чтобы средняя производительность классификации «исключение по одному» (LOO) была максимизирована в преобразованном пространстве. Ключевым моментом алгоритма является то, что матрица, соответствующая преобразованию, может быть найдена путем определения дифференцируемой целевой функции для , а затем использования итеративного решателя, такого как метод сопряженного градиентного спуска . Одним из преимуществ этого алгоритма является то, что количество классов может быть определено как функция от , с точностью до скалярной константы. Таким образом, это использование алгоритма решает проблему выбора модели . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle k}$ ${\displaystyle A}$

Объяснение

Для определения мы определяем целевую функцию, описывающую точность классификации в преобразованном пространстве, и пытаемся определить ее так, чтобы эта целевая функция была максимизирована. ${\displaystyle A}$ ${\displaystyle A^{*}}$

${\displaystyle A^{*}={\mbox{argmax}}_{A}f(A)}$

Классификация с исключением по одному (LOO)

Рассмотрим прогнозирование метки класса одной точки данных по консенсусу ее ближайших соседей с заданной метрикой расстояния. Это известно как классификация с исключением одного . Однако набор ближайших соседей может быть совершенно другим после прохождения всех точек через линейное преобразование. В частности, набор соседей для точки может претерпевать дискретные изменения в ответ на плавные изменения элементов , подразумевая, что любая целевая функция, основанная на соседях точки, будет кусочно-постоянной и, следовательно, не дифференцируемой . ${\displaystyle k}$ ${\displaystyle C_{i}}$ ${\displaystyle A}$ ${\displaystyle f(\cdot )}$

Решение

Мы можем решить эту трудность, используя подход, вдохновленный стохастическим градиентным спуском . Вместо того, чтобы рассматривать -ближайших соседей в каждой преобразованной точке в LOO-классификации, мы будем рассматривать весь преобразованный набор данных как стохастических ближайших соседей . Мы определяем их с помощью функции softmax квадрата евклидова расстояния между заданной точкой LOO-классификации и каждой другой точкой в ​​преобразованном пространстве: ${\displaystyle k}$

${\displaystyle p_{ij}={\begin{cases}{\frac {e^{-||Ax_{i}-Ax_{j}||^{2}}}{\sum _{k\neq i}e^{-||Ax_{i}-Ax_{k}||^{2}}}},&{\mbox{if}}j\neq i\\0,&{\mbox{if}}j=i\end{cases}}}$

Вероятность правильной классификации точки данных — это вероятность классификации точек каждого из ее соседей тем же классом : ${\displaystyle i}$ ${\displaystyle C_{i}}$

${\displaystyle p_{i}=\sum _{j\in C_{i}}p_{ij}\quad }$где - вероятность классификации соседа точки . ${\displaystyle p_{ij}}$ ${\displaystyle j}$ ${\displaystyle i}$

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

${\displaystyle f(A)=\sum _{i}\sum _{j\in C_{i}}p_{ij}=\sum _{i}p_{i}}$

Обратите внимание, что при стохастических ближайших соседях консенсусный класс для одной точки представляет собой ожидаемое значение класса точки в пределе бесконечного числа выборок, взятых из распределения по ее соседям, то есть: . Таким образом, предсказанный класс представляет собой аффинную комбинацию классов каждой другой точки, взвешенную функцией softmax для каждой , где теперь представляет собой весь преобразованный набор данных. ${\displaystyle i}$ ${\displaystyle j\in C_{i}}$ ${\displaystyle P(Class(X_{i})=Class(X_{j}))=p_{ij}}$ ${\displaystyle j\in C_{j}}$ ${\displaystyle C_{j}}$

Такой выбор целевой функции предпочтителен, поскольку она дифференцируема по (обозначим ): ${\displaystyle A}$ ${\displaystyle x_{ij}=x_{i}-x_{j}}$

${\displaystyle {\frac {\partial f}{\partial A}}=-2A\sum _{i}\sum _{j\in C_{i}}p_{ij}\left(x_{ij}x_{ij}^{T}-\sum _{k}p_{ik}x_{ik}x_{ik}^{T}\right)}$

${\displaystyle =2A\sum _{i}\left(p_{i}\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}\right)}$

Получение градиента для означает, что его можно найти с помощью итерационного решателя, такого как метод сопряженного градиентного спуска . Обратите внимание, что на практике большинство внутренних членов градиента оцениваются как незначительные вклады из-за быстро уменьшающегося вклада удаленных точек от точки интереса. Это означает, что внутренняя сумма градиента может быть усечена, что приводит к разумному времени вычислений даже для больших наборов данных. ${\displaystyle A}$

Альтернативная формулировка

«Максимизация эквивалентна минимизации -расстояния между предсказанным распределением классов и истинным распределением классов (т.е. где все индуцированные значения равны 1). Естественной альтернативой является KL-дивергенция, которая индуцирует следующую целевую функцию и градиент:» (Goldberger 2005) ${\displaystyle f(\cdot )}$ ${\displaystyle L_{1}}$ ${\displaystyle p_{i}}$ ${\displaystyle A}$

${\displaystyle g(A)=\sum _{i}\log \left(\sum _{j\in C_{i}}p_{ij}\right)=\sum _{i}\log(p_{i})}$

${\displaystyle {\frac {\partial g}{\partial A}}=2A\sum _{i}\left(\sum _{k}p_{ik}x_{ik}x_{ik}^{T}-{\frac {\sum _{j\in C_{i}}p_{ij}x_{ij}x_{ij}^{T}}{\sum _{j\in C_{i}}p_{ij}}}\right)}$

На практике оптимизация использования этой функции, как правило, дает такие же результаты производительности, как и при использовании оригинала. ${\displaystyle A}$

История и предыстория

Анализ компонентов соседства был разработан Джейкобом Голдбергером, Сэмом Роуайсом, Русланом Салахудиновым и Джеффом Хинтоном на кафедре компьютерных наук Университета Торонто в 2004 году.

Смотрите также

• Спектральная кластеризация
• Большой отрыв ближайшего соседа

Ссылки

• J. Goldberger, G. Hinton, S. Roweis, R. Salakhutdinov. (2005) Анализ компонентов соседства. Достижения в области нейронных систем обработки информации. 17, 513–520, 2005.

Внешние ссылки

Программное обеспечение

• Библиотека MLPACK содержит реализацию на языке C++
• NCА ( C++ )
• Реализация "NeighborhoodComponentsAnalysis" в scikit-learn ( Python )