WikiDer > Перцептрон ядра

Kernel perceptron

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

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

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

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

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

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

Инициализировать ш к полностью нулевому вектору длины п, количество предикторов (признаков).
Для некоторого фиксированного количества итераций или до тех пор, пока не будет выполнен какой-либо критерий остановки:
Для каждого обучающего примера Икс с меткой наземной истины йᵢ ∈ {-1, 1}:
Позволять ŷ = sgn (шТ Икс).
Если ŷйᵢ, Обновить шш + йᵢ Икс.

Методы ядра

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

.

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

Алгоритм

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

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

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

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

Инициализировать α к вектору из нулей длины п, количество обучающих выборок.
Для некоторого фиксированного количества итераций или до тех пор, пока не будет выполнен какой-либо критерий остановки:
Для каждого обучающего примера Иксj, уj:
Позволять
Если ŷуj, выполните обновление, увеличив счетчик ошибок:
αjαj + 1

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

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

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

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

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

Рекомендации

  1. ^ Айзерман, М. А .; Браверман, Эммануэль М .; Розонер, Л. И. (1964). «Теоретические основы метода потенциальных функций в обучении распознаванию образов». Автоматизация и дистанционное управление. 25: 821–837. Цитируется в Гийон, Изабель; Boser, B .; Вапник, Владимир (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). Методы ядра для анализа паттернов. Издательство Кембриджского университета. С. 241–242.
  5. ^ Декель, Офер; Шалев-Шварц, Шай; Певец, Йорам (2008). «Забыточный: персептрон на основе ядра с ограниченным бюджетом» (PDF). SIAM Журнал по вычислениям. 37 (5): 1342–1372. CiteSeerX 10.1.1.115.568. Дои:10.1137/060666998.
  6. ^ а б Кивинен, Юрки; Смола, Александр Дж .; Уильямсон, Роберт С. (2004). «Онлайн-обучение с ядрами». Транзакции IEEE при обработке сигналов. 52 (8): 2165–2176. CiteSeerX 10.1.1.578.5680. Дои:10.1109 / TSP.2004.830991.
  7. ^ Фройнд, Ю.; Шапире, Р. Э. (1999). «Классификация большой маржи с использованием алгоритма персептрона» (PDF). Машинное обучение. 37 (3): 277–296. Дои:10.1023 / А: 1007662407062.