Метод ядра

Класс алгоритмов для анализа образов

В машинном обучении машины ядра представляют собой класс алгоритмов для анализа шаблонов , наиболее известным членом которого является машина опорных векторов (SVM). Эти методы включают использование линейных классификаторов для решения нелинейных задач. ^[1] Общая задача анализа шаблонов заключается в поиске и изучении общих типов отношений (например, кластеров , ранжирований , главных компонент , корреляций , классификаций ) в наборах данных. Для многих алгоритмов, решающих эти задачи, данные в необработанном представлении должны быть явно преобразованы в представления векторов признаков с помощью указанной пользователем карты признаков : напротив, методы ядра требуют только указанного пользователем ядра , т. е. функции подобия по всем парам точек данных, вычисленной с использованием внутренних произведений . Карта признаков в машинах ядра является бесконечномерной, но требует только конечномерной матрицы из пользовательского ввода в соответствии с теоремой о представителе . Машины ядра медленно вычисляют для наборов данных, превышающих пару тысяч примеров, без параллельной обработки.

Методы ядра обязаны своим названием использованию функций ядра , которые позволяют им работать в многомерном неявном пространстве признаков без вычисления координат данных в этом пространстве, а просто вычисляя внутренние произведения между изображениями всех пар данных в пространстве признаков. Эта операция часто вычислительно дешевле, чем явное вычисление координат. Этот подход называется « трюк ядра ». ^[2] Функции ядра были введены для данных последовательностей, графиков , текста, изображений, а также векторов.

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

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

Мотивация и неформальное объяснение

Методы ядра можно рассматривать как обучающиеся на основе экземпляров : вместо того, чтобы изучать некоторый фиксированный набор параметров, соответствующих особенностям их входов, они вместо этого «запоминают» -й обучающий пример и изучают для него соответствующий вес . Прогнозирование для немаркированных входов, т. е. тех, которые не входят в обучающий набор, обрабатывается путем применения функции подобия , называемой ядром , между немаркированным входом и каждым из обучающих входов . Например, бинарный классификатор с ядром обычно вычисляет взвешенную сумму подобий, где ${\displaystyle i}$ ${\displaystyle (\mathbf {x} _{i},y_{i})}$ ${\displaystyle w_{i}}$ ${\displaystyle k}$ ${\displaystyle \mathbf {x'} }$ ${\displaystyle \mathbf {x} _{i}}$ $${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k(\mathbf {x} _{i},\mathbf {x'} ),}$$

• ${\displaystyle {\hat {y}}\in \{-1,+1\}}$— это предсказанная метка нуклеированного бинарного классификатора для непомеченного входа, скрытая истинная метка которого представляет интерес; ${\displaystyle \mathbf {x'} }$ ${\displaystyle y}$
• ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$— это функция ядра, которая измеряет сходство между любой парой входных данных ; ${\displaystyle \mathbf {x} ,\mathbf {x'} \in {\mathcal {X}}}$
• сумма распространяется на n помеченных примеров в обучающем наборе классификатора, при этом ; ${\displaystyle \{(\mathbf {x} _{i},y_{i})\}_{i=1}^{n}}$ ${\displaystyle y_{i}\in \{-1,+1\}}$
• — веса для обучающих примеров, определенные алгоритмом обучения; ${\displaystyle w_{i}\in \mathbb {R} }$
• Функция знака определяет , будет ли предсказанная классификация положительной или отрицательной. ${\displaystyle \operatorname {sgn} }$ ${\displaystyle {\hat {y}}}$

Ядерные классификаторы были описаны еще в 1960-х годах с изобретением ядерного персептрона . ^[3] Они приобрели большую известность с ростом популярности машины опорных векторов (SVM) в 1990-х годах, когда было обнаружено, что SVM может конкурировать с нейронными сетями в таких задачах, как распознавание рукописного ввода .

Математика: трюк с ядром

SVM с картой признаков, заданной и, таким образом, с функцией ядра . Точки обучения отображаются в трехмерном пространстве, где разделяющая гиперплоскость может быть легко найдена. ${\displaystyle \varphi ((a,b))=(a,b,a^{2}+b^{2})}$ ${\displaystyle k(\mathbf {x} ,\mathbf {y} )=\mathbf {x} \cdot \mathbf {y} +\left\|\mathbf {x} \right\|^{2}\left\|\mathbf {y} \right\|^{2}}$

Трюк с ядром позволяет избежать явного отображения, необходимого для того, чтобы линейные алгоритмы обучения научились нелинейной функции или границе решения . Для всех и во входном пространстве определенные функции могут быть выражены как внутренний продукт в другом пространстве . Функцию часто называют ядром или функцией ядра . Слово «ядро» используется в математике для обозначения весовой функции для взвешенной суммы или интеграла . ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {x'} }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle k(\mathbf {x} ,\mathbf {x'} )}$ ${\displaystyle {\mathcal {V}}}$ ${\displaystyle k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R} }$

Некоторые проблемы машинного обучения имеют больше структуры, чем произвольная весовая функция . Вычисление становится намного проще, если ядро ​​можно записать в виде «карты признаков» , которая удовлетворяет Ключевое ограничение заключается в том, что должно быть правильным внутренним произведением. С другой стороны, явное представление для не является необходимым, пока является внутренним произведением пространства . Альтернатива следует из теоремы Мерсера : неявно определенная функция существует всякий раз, когда пространство может быть снабжено подходящей мерой , гарантирующей, что функция удовлетворяет условию Мерсера . ${\displaystyle k}$ ${\displaystyle \varphi \colon {\mathcal {X}}\to {\mathcal {V}}}$ $${\displaystyle k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle _{\mathcal {V}}.}$$ ${\displaystyle \langle \cdot ,\cdot \rangle _{\mathcal {V}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {V}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle k}$

Теорема Мерсера похожа на обобщение результата линейной алгебры, которая связывает скалярное произведение с любой положительно определенной матрицей . Фактически, условие Мерсера можно свести к этому более простому случаю. Если мы выберем в качестве меры меру подсчета для всех , которая подсчитывает количество точек внутри множества , то интеграл в теореме Мерсера сводится к суммированию Если это суммирование выполняется для всех конечных последовательностей точек в и всех выборов действительных коэффициентов (ср. положительно определенное ядро ​​), то функция удовлетворяет условию Мерсера. ${\displaystyle \mu (T)=|T|}$ ${\displaystyle T\subset X}$ ${\displaystyle T}$ $${\displaystyle \sum _{i=1}^{n}\sum _{j=1}^{n}k(\mathbf {x} _{i},\mathbf {x} _{j})c_{i}c_{j}\geq 0.}$$ ${\displaystyle (\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n})}$ ${\displaystyle {\mathcal {X}}}$ ${\displaystyle n}$ ${\displaystyle (c_{1},\dots ,c_{n})}$ ${\displaystyle k}$

Некоторые алгоритмы, зависящие от произвольных отношений в собственном пространстве , на самом деле имели бы линейную интерпретацию в другой обстановке: пространстве диапазонов . Линейная интерпретация дает нам представление об алгоритме. Более того, часто нет необходимости выполнять вычисления непосредственно во время вычисления, как в случае с машинами опорных векторов . Некоторые называют это сокращение времени выполнения основным преимуществом. Исследователи также используют его для обоснования значений и свойств существующих алгоритмов. ${\displaystyle {\mathcal {X}}}$ ${\displaystyle \varphi }$ ${\displaystyle \varphi }$

Теоретически, матрица Грама относительно (иногда также называемая «матрицей ядра» ^[4] ), где , должна быть положительно полуопределенной (PSD) . ^[5] Эмпирически, для эвристики машинного обучения, выбор функции , которая не удовлетворяет условию Мерсера, все еще может работать разумно, если по крайней мере приближается к интуитивной идее подобия. ^[6] Независимо от того, является ли ядром Мерсера, все еще может называться «ядром». ${\displaystyle \mathbf {K} \in \mathbb {R} ^{n\times n}}$ ${\displaystyle \{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}}$ ${\displaystyle K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Если функция ядра также является функцией ковариации , используемой в гауссовых процессах , то матрицу Грама также можно назвать матрицей ковариации . ^[7] ${\displaystyle k}$ ${\displaystyle \mathbf {K} }$

Приложения

Области применения ядерных методов разнообразны и включают геостатистику , ^[8] кригинг , обратные взвешивающие расстояния , 3D-реконструкцию , биоинформатику , хемоинформатику , извлечение информации и распознавание рукописного текста .

Популярные ядра

• ядро Фишера
• Графические ядра
• Ядро сглаживает
• Полиномиальное ядро
• Ядро радиальной базисной функции (RBF)
• Ядра струн
• Нейронное касательное ядро
• Ядро нейронной сети Гауссовского процесса (NNGP)

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

• Методы ядра для векторного вывода
• Оценка плотности ядра
• Теорема о представителе
• Обучение на основе сходства
• Теорема Ковера

Ссылки

1. "Метод ядра". Engati . Получено 2023-04-04 .
2. Теодоридис, Сергиос (2008). Распознавание образов . Elsevier BV стр. 203. ISBN 9780080949123.
3. Айзерман, МА; Браверман, Эммануэль М.; Розоноэр, ЛИ (1964). «Теоретические основы метода потенциальной функции в обучении распознаванию образов». Автоматизация и дистанционное управление . 25 : 821–837.Цитируется в Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Автоматическая настройка емкости очень больших классификаторов VC-измерения . Достижения в нейронных системах обработки информации. CiteSeerX 10.1.1.17.7215 . 
4. Хофманн, Томас; Шолькопф, Бернхард; Смола, Александр Дж. (2008). «Ядерные методы в машинном обучении». Анналы статистики . 36 (3). arXiv : math/0701907 . doi : 10.1214/009053607000000677 . S2CID  88516979.
5. Mohri, Mehryar ; Rostamizadeh, Afshin; Talwalkar, Ameet (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258.
6. Сьюэлл, Мартин. "Support Vector Machines: Mercer's Condition". Support Vector Machines. Архивировано из оригинала 2018-10-15 . Получено 2014-05-30 .
7. Расмуссен, Карл Эдвард; Уильямс, Кристофер КИ (2006). Гауссовские процессы для машинного обучения . MIT Press. ISBN 0-262-18253-X. ^{[ нужна страница ]}
8. Honarkhah, M.; Caers, J. (2010). «Стохастическое моделирование паттернов с использованием моделирования паттернов на основе расстояний». Mathematical Geosciences . 42 (5): 487–517. Bibcode :2010MaGeo..42..487H. doi :10.1007/s11004-010-9276-7. S2CID  73657847.

Дальнейшее чтение

• Шоу-Тейлор, Дж .; Кристианини, Н. (2004). Методы ядра для анализа шаблонов . Cambridge University Press. ISBN 9780511809682.
• Лю, В.; Принсипе, Дж.; Хайкин, С. (2010). Kernel Adaptive Filtering: A Comprehensive Introduction. Wiley. ISBN 9781118211212.
• Schölkopf, B .; Smola, AJ; Bach, F. (2018). Обучение с помощью ядер: машины опорных векторов, регуляризация, оптимизация и не только. MIT Press. ISBN 978-0-262-53657-8.

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

• Kernel-Machines Org — сайт сообщества
• onlineprediction.net Статья о методах ядра