Онлайновое обучение машин

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Введение[править | править код]

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

Статистический взгляд на онлайновое обучение[править | править код]

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

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

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

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

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

Пакетное обучение[править | править код]

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

где
.

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

.

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

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

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

Приведённый выше итерационный алгоритм может быть доказан с помощью индукции по [3]. Доказательство также показывает, что . Можно рассматривать рекурсивный метод наименьших квадратов в контексте адаптивных фильтров (см. Рекурсивный метод наименьших квадратов[en]).

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

Метод стохастического градиентного спуска[править | править код]

Если равенство

Заменяется на

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

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

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

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

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

Ядерные методы[править | править код]

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

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

and

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

.

Теперь, если ввести общее ядро и представить функцию предсказания как

,

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

Приведённое выражение требует запоминания всех данных для обновления . Общая сложность по времени для рекурсии, если вычислять для -ой точки данных, равна , где является ценой вычисления ядра на одной паре точек[2]. Тогда использование ядра позволяет движение от конечномерного пространства параметров к возможно бесконечномерному пространству, представленному ядром , вместо осуществления рекурсии по пространству параметров , размерность которого та же самая, что и размер тренировочного множества данных. В общем случае является следствием теоремы о представлении[en][2].

Прогрессивное обучение[править | править код]

Прогрессивное обучение — это эффективная модель обучения, которая демонстрируется процессом обучения людей. Этот процесс обучения происходит непрерывно, исходя из прямого опыта. Техника прогрессивного обучения в машинном обучении может обучать новые классы/метки динамически на лету[5]. Хотя онлайновые обучения могут обучать новые выборки данных, которые поступают последовательно, они не могут обучать новые классы данных. Парадигма обучения прогрессивного обучения не зависит от числа ограничений на классы и может обучать новые классы, удерживая знания предыдущих классов. Как бы то ни было, если встречается новый класс (не возникающий естественно), классификатор перестраивается автоматически и параметры вычисляются таким образом, что удерживаются предыдущие знания. Эта техника пригодна для приложений реального мира, в которых число классов часто неизвестно и требуется онлайновое обучение из данных, поступающих в реальное время.

Онлайновая выпуклая оптимизация[править | править код]

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

Для

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

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

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

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

Следование за лидером[править | править код]

Простейшее обучающее правило для пробы — выбрать (на текущем шаге) гипотезу, которая имеет наименьшие потери среди всех предыдущих раундов. Этот алгоритм называется «Следование за лидером» (англ. Follow the leader) и просто даёт раунд :

Этот метод можно тогда рассматривать как жадный алгоритм. Для случая онлайновой квадратичной оптимизации (где функция потерь равна ), можно показать, что граница «сожаления» растёт как . Однако похожие границы не могут быть получены для алгоритма «следования за лидером» для других важных семейств моделей, как для онлайновой линейной оптимизации. Чтобы их получить, в алгоритм добавляется регуляризация.

Следование за регуляризованным лидером[править | править код]

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

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

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

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

Алгоритм известен как ленивая проекция, так как вектор аккумулирует градиенты. Это известно также как алгоритм двойного усреднения Нестерова (или субградиентным методом с двойным усреднением[7]). В этом сценарии линейные функции потерь и квадратичная регуляризация «сожаление» ограничено значением , а тогда среднее «сожаления» стремится к 0.

Онлайновый субградиентный спуск[править | править код]

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

Инициируем параметр

Для

  • Делаем предсказание, используя , получаем от природы .
  • Выбираем
  • Если , делаем обновление
  • Если , проецируем кумулятивные градиенты в i.e.

Можно использовать алгоритм онлайнового субградиентного спуска для получения границ «сожаления» для онлайновой версии метода опорных векторов для классификации, которая использует кусочно-линейную функция потерь[en]

Другие алгоритмы[править | править код]

Алгоритмы следования за квадратично регуляризованным лидером приводят к алгоритмам лениво проецируемого градиента, как описаны выше. Чтобы использовать описанный выше подход для любых выпуклых функций и регуляризаторов, можно использовать онлайновый зеркальный спуск. Оптимальная регуляризация в кусочно-линейной функции может быть получена для линейных функций потерь, что приводит к алгоритму AdaGrad[en]. Для евклидовой регуляризации можно показать, что граница «сожаления» равна и она может быть улучшена до для строго выпуклых и exp-вогнутых функций потерь.

Интерпретации онлайнового обучения[править | править код]

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

Первая интерпретация рассматривает метод стохастического градиентного спуска[en] как применение к задаче минимизации ожидаемого риска , определённого выше [8]. Более того, в случае бесконечного потока данных, поскольку экземпляры предполагаются выбранными из независимого и одинаково распределённого распределения , последовательности градиентов в итерации выше являются независимыми и одинаково распределёнными выборками стохастической оценки градиента ожидаемого риска , а потому можно применить результаты сложности для метода стохастического градиентного спуска[en] для ограничения отклонения , где является минимизатором [9]. Эта интерпретация верна также в случае конечных тренировочных наборов. Хотя при неоднократном проходе по данным градиенты уже не будут независимыми, результаты сложности в частных случаях могут быть получены.

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

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

Реализации[править | править код]

См. также[править | править код]

Примечания[править | править код]

  1. Катастрофическая помеха — это склонность искусственных нейронных сетей внезапно полностью забыть всё, чему сеть была обучена до этого.
  2. 1 2 3 4 5 6 7 Rosasco, Poggio, 2015.
  3. Yin, Kushner, 2003, с. 8–12.
  4. 1 2 Bertsekas, 2011.
  5. Venkatesan, Meng Joo, 2016, с. 310–321.
  6. Hazan, 2015.
  7. Долгополик, 2016.
  8. Bottou, 1998.
  9. Kushner, Yin, 1997.

Литература[править | править код]

  • Léon Bottou. Online Algorithms and Stochastic Approximations // Online Learning and Neural Networks. — Cambridge University Press, 1998. — ISBN 978-0-521-65263-6.
  • Rosasco L., Poggio T. Chapter 7 - Online Learning // Machine Learning: a Regularization Approach. MIT-9.520 Lectures Notes. — 2015. — (Manuscript).
  • Harold J. Kushner, G. George Yin. Stochastic Approximation Algorithms and Applications. — New York: Springer-Verlag, 1997. — ISBN 0-387-94916-X.
    • Harold J. Kushner, G. George Yin. Stochastic Approximation and Recursive Algorithms and Applications. — 2nd ed.. — New York: Springer-Verlag, 2003. — ISBN 0-387-00894-2.
  • Elad Hazan. Introduction to Online Convex Optimization. — Foundations and Trends® in Optimization, 2015.
  • Rajasekar Venkatesan, Er Meng Joo. A novel progressive learning technique for multi-class classification // Neurocomputing. — 2016. — Т. 207. — DOI:10.1016/j.neucom.2016.05.006. — arXiv:1609.00085.
  • Долгополик М. В. Метод Нестерова минимизации выпуклых функций. — 2016.
  • Harold J. Yin, G. George Kushner. Stochastic approximation and recursive algorithms and applications. — Second. — New York: Springer, 2003. — ISBN 978-0-387-21769-7.
  • Bertsekas D. P. Incremental gradient, subgradient, and proximal methods for convex optimization: a survey // Optimization for Machine Learning. — 2011. — Вып. 85.

Ссылки[править | править код]