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

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

Определение

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

Объяснение

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

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

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

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

Решение

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

$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}}$

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

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

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

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

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

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

${\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)$

$=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)$

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

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

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

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

${\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)$

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

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

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

См. также

Ссылки

Дж. Голдбергер, Г. Хинтон, С. Роуэйс, Р. Салахутдинов. (2005) Анализ компонентов соседства . Достижения в области нейронных систем обработки информации. 17, 513–520, 2005.

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

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

Библиотека MLPACK содержит C++. реализацию
инка ( C++ )
» от scikit-learn Реализация « NeighborhoodComponentsAnaанализ ( Python )