Метод ядра - Kernel method

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

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

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

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

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

Методы ядра можно рассматривать как обучающихся на основе экземпляров : вместо того, чтобы изучать некоторый фиксированный набор параметров, соответствующих характеристикам их входных данных, они вместо этого «запоминают» -й обучающий пример и изучают для него соответствующий вес . Прогнозирование для немаркированных входов, т. Е. Тех, которые не входят в обучающий набор, обрабатывается применением функции подобия , называемой ядром , между немаркированными входными данными и каждым из обучающих входов . Например, бинарный классификатор с ядром обычно вычисляет взвешенную сумму сходств. ${\ displaystyle i}$ ${\ Displaystyle (\ mathbf {х} _ {я}, у_ {я})}$ ${\ displaystyle w_ {i}}$ ${\ displaystyle k}$ ${\ Displaystyle \ mathbf {х '}}$ ${\ Displaystyle \ mathbf {х} _ {я}}$

{\ displaystyle {\ hat {y}} = \ operatorname {sgn} \ sum _ {i = 1} ^ {n} w_ {i} y_ {i} k (\ mathbf {x} _ {i}, \ mathbf {Икс'} )}

,

где

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

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

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

SVM с ядром, заданным формулой φ (( a , b )) = ( a , b , a ² + b ² ) и, следовательно, K ( x , y ) = . Точки обучения отображаются в трехмерном пространстве, где можно легко найти разделяющую гиперплоскость.

{\ Displaystyle \ mathbf {x} \ cdot \ mathbf {y} + \ left \ | \ mathbf {x} \ right \ | ^ {2} \ left \ | \ mathbf {y} \ right \ | ^ {2} }

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

Некоторые задачи машинного обучения имеют более сложную структуру, чем произвольная весовая функция . Вычисление значительно упростится, если ядро можно записать в форме «карты характеристик», удовлетворяющей ${\ displaystyle k}$ ${\ Displaystyle \ varphi \ двоеточие {\ mathcal {X}} \ to {\ mathcal {V}}}$

{\ Displaystyle К (\ 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 \ му (Т) = | Т |}$ ${\ Displaystyle T \ подмножество X}$ ${\ displaystyle T}$

{\ displaystyle \ sum _ {я = 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}$

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

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

Приложения

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

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

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

Shawe-Taylor, J .; Кристианини, Н. (2004). Методы ядра для анализа паттернов . Издательство Кембриджского университета.
Liu, W .; Principe, J .; Хайкин, С. (2010). Адаптивная фильтрация ядра: всестороннее введение . Вайли.
Шёлкопф, Б .; Смола, AJ; Бах, Ф. (2018). Обучение с помощью ядер: машины опорных векторов, регуляризация, оптимизация и не только . MIT Press. ISBN 978-0-262-53657-8.

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

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

Languages

In other projects