Ядро персептрона

В машинном обучении ядерный персептрон — это вариант популярного алгоритма обучения персептрона , который может обучать ядерные машины , т. е. нелинейные классификаторы , которые используют функцию ядра для вычисления сходства невидимых образцов с обучающими образцами. Алгоритм был изобретен в 1964 году ^[1] , что сделало его первым обучающимся ядерной классификацией. ^[2]

Предварительные

Алгоритм персептрона

Алгоритм персептрона — это алгоритм онлайн-обучения , работающий по принципу, называемому «обучение на основе ошибок». Он итеративно улучшает модель, запуская ее на обучающих образцах, а затем обновляя модель всякий раз, когда обнаруживает, что она сделала неверную классификацию относительно контролируемого сигнала . Модель, изученная стандартным алгоритмом персептрона, представляет собой линейный двоичный классификатор: вектор весов w (и, возможно, член прерывания b , опущенный здесь для простоты), который используется для классификации вектора образца x как класса «один» или класса «минус один» в соответствии с

${\displaystyle {\hat {y}}=\operatorname {sgn}(\mathbf {w} ^{\top }\mathbf {x} )}$

где ноль произвольно отображается на единицу или минус единицу. (« Шляпка » на ŷ обозначает оценочное значение.)

В псевдокоде алгоритм персептрона задается следующим образом:

Инициализируем w вектором из всех нулей длиной p , числом предикторов (признаков).

Для некоторого фиксированного числа итераций или до тех пор, пока не будет выполнен некоторый критерий остановки:

Для каждого обучающего примера x _i с меткой истинности y _i ∈ {-1, 1 }:

Пусть ŷ = sgn( w ^T x _i ) .

Если ŷ ≠ y _i , обновить w ← w + y _i x _i .

Методы ядра

В отличие от линейных моделей, изученных персептроном, метод ядра ^[3] представляет собой классификатор, который хранит подмножество своих обучающих примеров x _i , связывает с каждым из них вес α _i и принимает решения для новых образцов x' путем оценки

${\displaystyle \operatorname {sgn} \sum _{i}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x'} )}$.

Здесь K — некоторая функция ядра. Формально функция ядра — это неотрицательное полуопределенное ядро ​​(см. условие Мерсера ), представляющее собой скалярное произведение между образцами в многомерном пространстве, как если бы образцы были расширены для включения дополнительных признаков функцией Φ : K ( x , x' ) = Φ( x ) · Φ( x' ) . Интуитивно ее можно рассматривать как функцию сходства между образцами, поэтому машина ядра устанавливает класс нового образца путем взвешенного сравнения с обучающим набором. Каждая функция x' ↦ K ( x _i , x' ) служит базисной функцией в классификации.

Алгоритм

Чтобы получить версию алгоритма персептрона с ядром, мы должны сначала сформулировать его в двойственной форме , исходя из наблюдения, что весовой вектор w может быть выражен как линейная комбинация n обучающих образцов. Уравнение для весового вектора имеет вид

${\displaystyle \mathbf {w} =\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}}$

где α _i — количество раз, когда x _i был неправильно классифицирован, что приводит к обновлению w ← w + y _i x _i . Используя этот результат, мы можем сформулировать алгоритм двойного персептрона, который, как и прежде, проходит по образцам, делая прогнозы, но вместо сохранения и обновления вектора веса w он обновляет вектор «счетчика ошибок» α . Мы также должны переписать формулу прогноза, чтобы избавиться от w :

${\displaystyle {\begin{aligned}{\hat {y}}&=\operatorname {sgn}(\mathbf {w} ^{\mathsf {T}}\mathbf {x} )\\&=\operatorname {sgn} \left(\sum _{i}^{n}\alpha _{i}y_{i}\mathbf {x} _{i}\right)^{\mathsf {T}}\mathbf {x} \\&=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}(\mathbf {x} _{i}\cdot \mathbf {x} )\end{aligned}}}$

Включение этих двух уравнений в цикл обучения превращает его в алгоритм двойного персептрона .

Наконец, мы можем заменить скалярное произведение в двойном персептроне произвольной функцией ядра, чтобы получить эффект карты признаков Φ без явного вычисления Φ( x ) для любых образцов. Это дает алгоритм персептрона ядра: ^[4]

Инициализируем α вектором из всех нулей длиной n , числом обучающих образцов.

Для некоторого фиксированного числа итераций или до тех пор, пока не будет выполнен некоторый критерий остановки:

Для каждого обучающего примера x _j , y _j :

Позволять ${\displaystyle {\hat {y}}=\operatorname {sgn} \sum _{i}^{n}\alpha _{i}y_{i}K(\mathbf {x} _{i},\mathbf {x} _{j})}$

Если ŷ ≠ y _j , выполнить обновление, увеличив счетчик ошибок:

αj ← αj ₊ 1_​

Варианты и расширения

Одна из проблем с ядерным персептроном, представленная выше, заключается в том, что он не обучает машины с разреженным ядром. Изначально все α _i равны нулю, поэтому оценка функции решения для получения ŷ не требует никаких ядерных оценок вообще, но каждое обновление увеличивает один α _i , делая оценку все более затратной. Более того, когда ядерный персептрон используется в онлайн- режиме, количество ненулевых α _i и, следовательно, стоимость оценки растут линейно с количеством примеров, представленных алгоритму.

Для решения этой проблемы был предложен вариант ядра персептрона «забытый». Он поддерживает активный набор примеров с ненулевым α _i , удаляя («забывая») примеры из активного набора, когда он превышает заранее определенный бюджет, и «сжимая» (снижая вес) старые примеры, когда новые повышаются до ненулевого α _i . ^[5]

Другая проблема с ядерным персептроном заключается в том, что он не регуляризуется , что делает его уязвимым к переобучению . Онлайновый алгоритм обучения ядра NORMA можно рассматривать как обобщение алгоритма ядерного персептрона с регуляризацией. ^[6] Алгоритм последовательной минимальной оптимизации (SMO), используемый для обучения опорных векторных машин, также можно рассматривать как обобщение ядерного персептрона. ^[6]

Алгоритм голосовавшего персептрона Фройнда и Шапира также распространяется на ядерный случай, ^[7] давая границы обобщения, сравнимые с ядерным SVM. ^[2]

Ссылки

1. Айзерман, МА; Браверман, Эммануэль М.; Розонер, ЛИ (1964). «Теоретические основы метода потенциальной функции в обучении распознаванию образов». Автоматизация и дистанционное управление . 25 : 821–837.Цитируется в Guyon, Isabelle; Boser, B.; Vapnik, Vladimir (1993). Автоматическая настройка емкости очень больших классификаторов VC-измерения . Достижения в нейронных системах обработки информации. CiteSeerX 10.1.1.17.7215 . 
2. Бордес, Антуан; Эртекин, Сейда; Уэстон, Джейсон; Ботту, Леон (2005). «Быстрые ядерные классификаторы с онлайн-обучением и активным обучением». JMLR . 6 : 1579–1619.
3. Шёлькопф, Бернхард; и Смола, Александр Дж.; Обучение с помощью ядер , MIT Press, Кембридж, Массачусетс, 2002. ISBN 0-262-19475-9 
4. Шоу-Тейлор, Джон; Кристианини, Нелло (2004). Методы ядра для анализа шаблонов . Cambridge University Press. С. 241–242.
5. Декель, Офер; Шалев-Шварц, Шай; Сингер, Йорам (2008). «Забытый: персептрон на основе ядра с ограниченным бюджетом» (PDF) . SIAM Journal on Computing . 37 (5): 1342–1372. CiteSeerX 10.1.1.115.568 . doi :10.1137/060666998. 
6. Кивинен, Юрки; Смола, Александр Дж.; Уильямсон, Роберт К. (2004). «Онлайн-обучение с ядрами». Труды IEEE по обработке сигналов . 52 (8): 2165–2176. CiteSeerX 10.1.1.578.5680 . doi :10.1109/TSP.2004.830991. 
7. Фройнд, И.; Шапир , Р. Э. (1999). «Классификация с большим запасом с использованием алгоритма персептрона» (PDF) . Машинное обучение . 37 (3): 277–296. doi : 10.1023/A:1007662407062 .