Перцептрон ядра - Kernel perceptron

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

Предварительные мероприятия

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

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

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

где ноль произвольно отображается на единицу или минус один. ("шляпа " на $ŷ$ обозначает оценочную стоимость.)

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

Инициализировать

ш

к полностью нулевому вектору длины

п

, количество предикторов (признаков).

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

Для каждого обучающего примера

Икс ᵢ

с меткой наземной истины

йᵢ \in {-1, 1

}:

Позволять

ŷ = sgn (ш Т Икс ᵢ)

.

Если

ŷ \neq йᵢ

, Обновить

ш \leftarrow ш + йᵢ Икс ᵢ

.

Методы ядра

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

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

.

Здесь, $K$ это некоторая функция ядра. Формально функция ядра - это неотрицательное полуопределенное ядро (видеть Состояние Мерсера ), представляющий внутренний продукт между образцами в многомерном пространстве, как если бы образцы были расширены для включения дополнительных функций с помощью функции $Φ$ : $K (Икс, Икс') = Φ (Икс) \cdot Φ (Икс')$ . Интуитивно это можно рассматривать как функция подобия между выборками, поэтому машина ядра устанавливает класс новой выборки путем взвешенного сравнения с обучающей выборкой. Каждая функция $Икс' \mapsto K (Икс ᵢ, Икс')$ служит базисная функция в классификации.

Алгоритм

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

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

куда $α я$ это количество раз $Икс я$ был неправильно классифицирован, что привело к обновлению $ш \leftarrow ш + у я Икс я$ . Используя этот результат, мы можем сформулировать алгоритм двойного персептрона, который, как и раньше, перебирает образцы, делая прогнозы, но вместо сохранения и обновления вектора весов $ш$ , он обновляет вектор "счетчика ошибок" $α$ . Мы также должны переписать формулу прогноза, чтобы избавиться от $ш$ :

{ displaystyle { begin {align} { 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 { выровнено}}}

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

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

Инициализировать

α

к вектору из нулей длины

п

, количество обучающих выборок.

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

Для каждого обучающего примера

Икс j, у j

:

Позволять

{ displaystyle { hat {y}} = operatorname {sgn} sum _ {i} ^ {n} alpha _ {i} y_ {i} K ( mathbf {x} _ {i}, mathbf {x} _ {j})}

Если

ŷ \neq у j

, выполните обновление, увеличив счетчик ошибок:

α j \leftarrow α j + 1

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

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

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

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

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