WikiDer > Машинное обучение онлайн

Online machine learning

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

Вступление

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

Статистическое представление онлайн-обучения

В статистических моделях обучения обучающая выборка считаются взятыми из истинного распределения и цель - минимизировать ожидаемый «риск»

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

Распространенной стратегией преодоления вышеуказанных проблем является обучение использованию мини-пакетов, которые обрабатывают небольшую партию точек данных за раз, это можно рассматривать как псевдо-онлайн-обучение для намного меньше, чем общее количество тренировочных точек. Используются мини-пакетные методы с повторной передачей обучающих данных для получения оптимизированных вне ядра.[требуется разъяснение] версии алгоритмов машинного обучения, например, стохастический градиентный спуск. В сочетании с обратное распространение, в настоящее время это де-факто метод обучения для тренировки искусственные нейронные сети.

Пример: линейный метод наименьших квадратов

Простой пример линейного метода наименьших квадратов используется для объяснения различных идей онлайн-обучения. Идеи достаточно общие, чтобы их можно было применить к другим параметрам, например, к другим выпуклым функциям потерь.

Пакетное обучение

Рассмотрим настройку контролируемого обучения с будучи линейной функцией, которую необходимо изучить:

где вектор входов (точек данных) и - вектор линейного фильтра. Цель состоит в том, чтобы вычислить вектор фильтра . С этой целью квадратная функция потерь

используется для вычисления вектора что минимизирует эмпирические потери

где

.

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

.

Теперь вычисляем ковариационную матрицу требуется время , инвертируя матрица требует времени , а остальная часть умножения требует времени , что дает общее время . Когда есть общее количество точек в наборе данных, чтобы повторно вычислить решение после прибытия каждой точки данных , наивный подход будет иметь полную сложность . Обратите внимание, что при хранении матрицы , то для его обновления на каждом этапе нужно только добавить , который занимает время, сокращая общее время до , но с дополнительным пространством для хранения хранить .[1]

Онлайн-обучение: рекурсивные методы наименьших квадратов

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

Приведенный выше итерационный алгоритм можно доказать индукцией по .[2] Доказательство также показывает, что . Можно посмотреть на RLS и в контексте адаптивных фильтров (см. RLS).

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

Стохастический градиентный спуск

Когда это

заменяется на

или к , это становится алгоритмом стохастического градиентного спуска. В этом случае сложность для шаги этого алгоритма сводятся к . Требования к хранению на каждом этапе постоянны на .

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

Инкрементальный стохастический градиентный спуск

На практике можно выполнить несколько проходов стохастического градиента (также называемых циклами или эпохами) над данными. Полученный таким образом алгоритм называется методом инкрементного градиента и соответствует итерации

Основное отличие от метода стохастического градиента состоит в том, что здесь последовательность выбирается, чтобы решить, какую тренировочную точку посетить в -й шаг. Такая последовательность может быть стохастической или детерминированной. Затем количество итераций отделяется от количества точек (каждая точка может рассматриваться более одного раза). Можно показать, что метод инкрементного градиента минимизирует эмпирический риск.[3] Дополнительные методы могут быть полезными при рассмотрении целевых функций, состоящих из суммы многих членов, например эмпирическая ошибка, соответствующая очень большому набору данных.[1]

Методы ядра

Ядра можно использовать для расширения вышеуказанных алгоритмов на непараметрические модели (или модели, в которых параметры образуют бесконечномерное пространство). Соответствующая процедура больше не будет по-настоящему онлайн и вместо этого будет включать в себя сохранение всех точек данных, но по-прежнему быстрее, чем метод грубой силы. Это обсуждение ограничивается случаем квадратичной потери, хотя ее можно распространить на любые выпуклые потери. Это может быть показано простой индукцией [1] что если матрица данных и вывод после шаги алгоритма SGD, то

где и последовательность удовлетворяет рекурсии:

и

Обратите внимание, что здесь это просто стандартное ядро ​​на , а предиктор имеет вид

.

Теперь, если общее ядро вводится вместо этого, и пусть предиктор будет

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

Вышеупомянутое выражение требует сохранения всех данных для обновления . Общая временная сложность рекурсии при оценке -я точка данных , где - стоимость оценки ядра по одной паре точек.[1]Таким образом, использование ядра позволило выйти из конечномерного пространства параметров. к возможно бесконечномерному объекту, представленному ядром вместо этого выполняя рекурсию в пространстве параметров , размерность которого совпадает с размером обучающего набора данных. В общем, это следствие теорема о представителе.[1]

Выпуклая оптимизация онлайн

Выпуклая оптимизация онлайн (OCO) [4] это общая основа для принятия решений, которая использует выпуклая оптимизация чтобы учесть эффективные алгоритмы. Основа состоит в следующем:

За

  • Учащийся получает ввод
  • Результаты обучения из фиксированного выпуклого множества
  • Природа возвращает выпуклую функцию потерь .
  • Учащийся терпит поражение и обновляет свою модель

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

Однако некоторые задачи онлайн-прогнозирования не подходят для OCO. Например, в онлайн-классификации область прогнозирования и функции потерь не являются выпуклыми. В таких сценариях используются два простых метода конвексификации: рандомизация и суррогатные функции потерь.[нужна цитата].

Вот несколько простых онлайн-алгоритмов выпуклой оптимизации:

Следуй за лидером (FTL)

Самое простое правило обучения - выбрать (на текущем шаге) гипотезу, которая имеет наименьшие потери за все предыдущие раунды. Этот алгоритм называется «Следуй за лидером» и просто дается по кругу от:

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

Следуй за регуляризованным лидером (FTRL)

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

В качестве частного примера рассмотрим случай линейной оптимизации онлайн, то есть когда природа возвращает функции потерь вида . Кроме того, пусть . Предположим, что функция регуляризации выбирается для некоторого положительного числа . Тогда можно показать, что итерация минимизации сожалений становится

Обратите внимание, что это можно переписать как , который выглядит как градиентный спуск онлайн.

Если S вместо этого является выпуклым подпространством , S нужно будет проецировать на, что приведет к измененному правилу обновления

Этот алгоритм известен как ленивое проектирование, поскольку вектор накапливает градиенты. Он также известен как алгоритм двойного усреднения Нестерова. В этом сценарии линейных функций потерь и квадратичной регуляризации сожаление ограничено , и поэтому среднее сожаление уходит 0 по желанию.

Субградиентный спуск онлайн (OSD)

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

Параметр инициализации

За

  • Прогнозировать с помощью , получить от природы.
  • выбирать
  • Если , обновить как
  • Если , спроецировать кумулятивные градиенты на т.е.

Можно использовать алгоритм OSD для получения границы сожаления для онлайн-версии SVM для классификации, которые используют потеря петли

Другие алгоритмы

Квадратично регуляризованные алгоритмы FTRL приводят к алгоритмам ленивого проецирования градиента, как описано выше. Чтобы использовать вышеизложенное для произвольных выпуклых функций и регуляризаторов, используется онлайн-зеркальный спуск. Оптимальная регуляризация задним числом может быть получена для линейных функций потерь, что приводит к АдаГрад Для евклидовой регуляризации можно показать границу сожаления , который может быть улучшен до для сильно выпуклых и эксп-вогнутых функций потерь.

Интерпретации онлайн-обучения

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

Первая интерпретация рассматривает стохастический градиентный спуск метод применительно к проблеме минимизации ожидаемого риска определено выше.[5] Действительно, в случае бесконечного потока данных, поскольку примеры считаются нарисованными i.i.d. из раздачи , последовательность градиентов в приведенной выше итерации - это i.i.d. выборка стохастических оценок градиента ожидаемого риска и поэтому можно применить результаты сложности для метода стохастического градиентного спуска, чтобы ограничить отклонение , где минимизатор .[6] Эта интерпретация также верна в случае конечной обучающей выборки; хотя при нескольких проходах через данные градиенты больше не являются независимыми, в особых случаях все же можно получить результаты по сложности.

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

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

Реализации

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

Парадигмы обучения

Общие алгоритмы

Модели обучения

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

  1. ^ а б c d е ж грамм Л. Росаско, Т. Поджио, Машинное обучение: подход регуляризации, MIT-9.520 Lectures Notes, Manuscript, декабрь 2015 г. Глава 7 - Онлайн-обучение
  2. ^ Инь, Гарольд Дж. Кушнер, Дж. Джордж (2003). Стохастическая аппроксимация и рекурсивные алгоритмы и приложения (Второе изд.). Нью-Йорк: Спрингер. стр.8–12. ISBN 978-0-387-21769-7.
  3. ^ а б Бертсекас, Д. П. (2011). Инкрементальный градиент, субградиент и проксимальные методы выпуклой оптимизации: обзор. Оптимизация для машинного обучения, 85.
  4. ^ Хазан, Элад (2015). Введение в онлайн-оптимизацию выпуклости (PDF). Основы и тенденции оптимизации.
  5. ^ Ботту, Леон (1998). «Онлайн-алгоритмы и стохастические аппроксимации». Онлайн-обучение и нейронные сети. Издательство Кембриджского университета. ISBN 978-0-521-65263-6.
  6. ^ Алгоритмы и приложения стохастической аппроксимации, Гарольд Дж. Кушнер и Дж. Джордж Инь, Нью-Йорк: Springer-Verlag, 1997. ISBN 0-387-94916-X; 2-е изд., Назв. Стохастическая аппроксимация и рекурсивные алгоритмы и приложения, 2003, ISBN 0-387-00894-2.

внешняя ссылка