Метод ядра

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

В машинном обучении машины ядра — это класс алгоритмов анализа шаблонов , наиболее известным представителем которого является машина опорных векторов (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] Независимо от того, является ли ядро ​​Mercer, его все равно можно называть «ядром». ${\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. «Метод ядра». Энгати . Проверено 4 апреля 2023 г.
2. Теодоридис, Сергиос (2008). Распознавание образов . Эльзевир Б.В. с. 203. ИСБН 9780080949123.
3. Айзерман, Массачусетс; Браверман, Эммануэль М.; Розоноер, Л.И. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и дистанционное управление . 25 : 821–837.Цитируется в Гийоне, Изабель; Бозер, Б.; Вапник, Владимир (1993). Автоматическая настройка производительности очень больших классификаторов VC-размерности . Достижения в области нейронных систем обработки информации. CiteSeerX 10.1.1.17.7215 . 
4. Хофманн, Томас; Шолькопф, Бернхард; Смола, Александр Дж. (2008). «Методы ядра в машинном обучении». Анналы статистики . 36 (3). arXiv : математика/0701907 . дои : 10.1214/009053607000000677 . S2CID  88516979.
5. Мори, Мехриар ; Ростамизаде, Афшин; Талвалкар, Амит (2012). Основы машинного обучения . США, Массачусетс: MIT Press. ISBN 9780262018258.
6. Сьюэлл, Мартин. «Машины опорных векторов: состояние Мерсера». Машины опорных векторов. Архивировано из оригинала 15 октября 2018 г. Проверено 30 мая 2014 г.
7. Расмуссен, Карл Эдвард; Уильямс, Кристофер К.И. (2006). Гауссовы процессы для машинного обучения . МТИ Пресс. ISBN 0-262-18253-Х.^{[ нужна страница ]}
8. Хонарха, М.; Каерс, Дж. (2010). «Стохастическое моделирование закономерностей с использованием дистанционного моделирования закономерностей». Математические науки о Земле . 42 (5): 487–517. Бибкод : 2010MaGeo..42..487H. doi : 10.1007/s11004-010-9276-7. S2CID  73657847.

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

• Шоу-Тейлор, Дж .; Кристианини, Н. (2004). Ядерные методы анализа закономерностей . Издательство Кембриджского университета.
• Лю, В.; Принсипи, Дж.; Хайкин, С. (2010). Адаптивная фильтрация ядра: всестороннее введение. Уайли. ISBN 9781118211212.
• Шёлкопф, Б .; Смола, Эй Джей; Бах, Ф. (2018). Обучение с помощью ядер: машины опорных векторов, регуляризация, оптимизация и многое другое. МТИ Пресс. ISBN 978-0-262-53657-8.

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

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