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

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

Введение

В условиях обучения с учителем обучается функция $f:X\to Y$, где $X$ рассматривается как пространство входных данных, а $Y$ — пространство выходных данных, которая хорошо предсказывает на элементах совместного распределения вероятностей $p(x,y)$ на $X\times Y$. В действительности при обучении истинное распределение $p(x,y)$ никогда не известно. Обычно, наоборот, есть доступ к тренировочному набору примеров $(x_{1},y_{1}),\ldots ,(x_{n},y_{n})$. В этих условиях функция потерь задаётся как $V:Y\times Y\to \mathbb {R}$, такая, что $V(f(x),y)$ измеряет разницу между предсказанным значением $f(x)$ и истинным значением $y$. Идеальная цель — выбрать функцию $f\in {\mathcal {H}}$, где ${\mathcal {H}}$ является пространством функций, называемым пространством гипотез, так, что полные потери минимальны в некотором смысле. В зависимости от типа модели (статистическая или состязательная), можно разработать различные понятия потерь, которые приводят к различным алгоритмам обучения.

Статистический взгляд на онлайновое обучение

В статистических моделях обучения проверочная выборка $(x_{i},y_{i})$ предполагается извлечённой из истинного распределения $p(x,y)$ и целью обучения является минимизация ожидаемого «риска»

$I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .$

Общей парадигмой в этой ситуации является оценка функции ${\hat {f}}$ посредством минимизации эмпирического риска или минимизации регуляризованного эмпирического риска (обычно используется регуляризация Тихонова). Выбор функции потерь здесь даёт несколько хорошо известных алгоритмов обучения, таких как регуляризованный метод наименьших квадратов и метод опорных векторов. Чисто онлайновой моделью в этой категории было бы обучение лишь на новых входных данных $(x_{t+1},y_{t+1})$, текущем лучшем предсказателе $f_{t}$ и некоторой добавочной запомненной информации (которая, обычно, имеет требования к памяти, не зависящие от размера данных). Для многих постановок задачи, например для нелинейных ядерных методов, истинное онлайновое обучение невозможно, хотя могут быть использованы гибридные формы онлайнового обучения с рекурсивными алгоритмами, где значению $f_{t+1}$ разрешено зависеть от $f_{t}$ и всех предыдущих точек данных $(x_{1},y_{1}),\ldots ,(x_{t},y_{t})$. В этом случае требования к памяти больше нельзя ограничить, поскольку требуется сохранение всех предыдущих точек, но решение может брать меньше времени для вычисления с добавлением новых точек данных, чем техники пакетного обучения.

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

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

Основная статья: Линейный метод наименьших квадратов

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

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

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

$I_{n}[w]=\sum _{j=1}^{n}V(\langle w,x_{j}\rangle ,y_{j})=\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}$, где

$x_{j}\in \mathbb {R} ^{d},w\in \mathbb {R} ^{d},y_{j}\in \mathbb {R}$.

Пусть $X$ будет $i\times d$ матрицей данных и $Y$ будет $i\times 1$ матрицей целевых значений после поступления первых $i$ точек данных. При предположении, что матрица ковариации $\Sigma _{i}=X^{T}X$ обратима (в противном случае следует провести процедуру, аналогичную регуляризации Тихонова), лучшее решение $f^{*}(x)=\langle w^{*},x\rangle$ метода наименьших квадратов задаётся равенством

$w^{*}=(X^{T}X)^{-1}X^{T}Y=\Sigma _{i}^{-1}\sum _{j=1}^{i}x_{j}y_{j}$.

Теперь вычисление ковариационной матрицы $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{T}$ займёт $O(id^{2})$ времени, обращение $d\times d$ матрицы займёт $O(d^{3})$ времени, а умножение матриц займёт $O(d^{2})$ времени, что даёт общее время $O(id^{2}+d^{3})$. Если имеется в общей сложности $n$ точек в наборе данных и необходимо перевычислить решение после прибытия каждой точки данных $i=1,\ldots ,n$, естественный подход будет иметь полную сложность $O(n^{2}d^{2}+nd^{3})$. Заметим, что в случае сохранения матрицы $\Sigma _{i}$ обновление на каждом шаге требует лишь добавления $x_{i+1}x_{i+1}^{T}$, что занимает $O(d^{2})$ времени, что сокращает общее время до $O(nd^{2}+nd^{3})=O(nd^{3})$, но требует дополнительного пространства $O(d^{2})$ для запоминания $\Sigma _{i}$.

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

Рекурсивный метод наименьших квадратов рассматривает онлайновый подход к методу наименьших квадратов. Можно показать, что при инициализации $\textstyle w_{0}=0\in \mathbb {R} ^{d}$ и $\textstyle \Gamma _{0}=I\in \mathbb {R} ^{d\times d}$ решение линейного метода наименьших квадратов может быть вычислено следующим образом:

$\Gamma _{i}=\Gamma _{i-1}-{\frac {\Gamma _{i-1}x_{i}x_{i}^{T}\Gamma _{i-1}}{1+x_{i}^{T}\Gamma _{i-1}x_{i}}}$

$w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$

Приведённый выше итерационный алгоритм может быть доказан с помощью индукции по $i$. Доказательство также показывает, что $\Gamma _{i}=\Sigma _{i}^{-1}$. Можно рассматривать рекурсивный метод наименьших квадратов в контексте адаптивных фильтров (см. Рекурсивный метод наименьших квадратов).

Сложность $n$ шагов этого алгоритма равна $O(nd^{2})$, что быстрее, чем соответствующая сложность пакетного обучения. Память, требуемая для каждого шага $i$ для сохранения матрицы $\Gamma _{i}$, здесь является константой $O(d^{2})$. Для случая, когда $\Sigma _{i}$ не обратима, рассматривается регуляризованная версия функции потерь $\sum _{j=1}^{n}(x_{j}^{T}w-y_{j})^{2}+\lambda ||w||_{2}^{2}$. Тогда просто показать, что тот же алгоритм работает с $\Gamma _{0}=(I+\lambda I)^{-1}$, и продолжение итераций даёт $\Gamma _{i}=(\Sigma _{i}+\lambda I)^{-1}$.

Метод стохастического градиентного спуска

Основная статья: Стохастический градиентный спуск

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

$\textstyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})$

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

$\textstyle w_{i}=w_{i-1}-\gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{i}\rangle ,y_{i})$

или $\Gamma _{i}\in \mathbb {R} ^{d\times d}$ на $\gamma _{i}\in \mathbb {R}$, это становится алгоритмом стохастического градиентного спуска. В этом случае сложность для $n$ шагов этого алгоритма сокращается до $O(nd)$. Требования к памяти на каждом шаге $i$ являются константой $O(d)$.

Однако размер шага $\gamma _{i}$ для решения задачи минимизации ожидаемого риска следует выбирать осторожно, как объяснено выше. При выборе размера шага затухания $\gamma _{i}\approx {\frac {1}{\sqrt {i}}}$ можно доказать сходимость средней итерации ${\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}$. Эти установки являются частным случаем стохастической оптимизации, хорошо известной задачи оптимизации.

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

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

$\textstyle w_{i}=w_{i-1}-\gamma _{i}\nabla V(\langle w_{i-1},x_{t_{i}}\rangle ,y_{t_{i}})$

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

Ядерные методы

См. также: Ядерный метод

Ядра могут быть использованы для расширения вышеприведённых алгоритмов до непараметрических моделей (или моделей, в которых параметры образуют бесконечномерное пространство). Соответствующая процедура более не будет истинно онлайновой и вместо этого сохраняет все точки данных, но метод остаётся более быстрым, чем прямой перебор. Данное обсуждение ограничено случаем квадратных потерь, хотя оно может быть расширено до любой выпуклой функции потерь. Можно показать прямой индукцией, что когда $X_{i}$ является матрицей данных, а $w_{i}$ является выходом после $i$ шагов алгоритма случайного градиентного спуска, то

$w_{i}=X_{i}^{T}c_{i}$

где $\textstyle c_{i}=((c_{i})_{1},(c_{i})_{2},...,(c_{i})_{i})\in \mathbb {R} ^{i}$ и последовательность $c_{i}$ удовлетворяет рекуррентным соотношениям

$c_{0}=0$

$(c_{i})_{j}=(c_{i-1})_{j},j=1,2,...,i-1$ и

$(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x_{i}\rangle {\Big )}$

Заметим, что здесь $\langle x_{j},x_{i}\rangle$ является стандартным ядром в $\mathbb {R} ^{d}$, и предсказательная функция имеет вид

$f_{i}(x)=\langle w_{i-1},x\rangle =\sum _{j=1}^{i-1}(c_{i-1})_{j}\langle x_{j},x\rangle$.

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

$f_{i}(x)=\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x)$,

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

$(c_{i})_{i}=\gamma _{i}{\Big (}y_{i}-\sum _{j=1}^{i-1}(c_{i-1})_{j}K(x_{j},x_{i}){\Big )}$

Приведённое выражение требует запоминания всех данных для обновления $c_{i}$. Общая сложность по времени для рекурсии, если вычислять для $n$-ой точки данных, равна $O(n^{2}dk)$, где $k$ является ценой вычисления ядра на одной паре точек. Тогда использование ядра позволяет движение от конечномерного пространства параметров $\textstyle w_{i}\in \mathbb {R} ^{d}$ к возможно бесконечномерному пространству, представленному ядром $K$, вместо осуществления рекурсии по пространству параметров $\textstyle c_{i}\in \mathbb {R} ^{i}$, размерность которого та же, что и размер тренировочного множества данных. В общем случае этот подход является следствием теоремы о представлении.

Прогрессивное обучение

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

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

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

Для $t=1,2,...,T$

• Ученик получает вход $x_{t}$
• Ученик образует выход $w_{t}$ из фиксированного выпуклого множества $S$
• Природа возвращает значение выпуклой функции потерь $v_{t}:S\rightarrow \mathbb {R}$.
• Ученик учитывает потерю $v_{t}(w_{t})$ и обновляет модель

Целью является минимизация «сожаления» или разности между общей потерей и потерей на лучшей фиксированной точке $u\in S$ в ретроспективе. Как пример, рассмотрим случай онлайновой линейной регрессии методом наименьших квадратов. Здесь вес векторов приходит из выпуклого множества $S=\mathbb {R} ^{d}$ и природа возвращает выпуклую функцию потерь $v_{t}(w)=(\langle w,x_{t}\rangle -y_{t})^{2}$. Заметим, что $y_{t}$ неявно присылается с $v_{t}$.

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

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

Следование за лидером

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

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)$

Этот метод можно тогда рассматривать как жадный алгоритм. Для случая онлайновой квадратичной оптимизации (где функция потерь равна $v_{t}(w)=||w-x_{t}||_{2}^{2}$), можно показать, что граница «сожаления» растёт как $\log(T)$. Однако похожие границы не могут быть получены для алгоритма «следования за лидером» для других важных семейств моделей, как для онлайновой линейной оптимизации. Чтобы их получить, в алгоритм добавляется регуляризация.

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

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

$w_{t}=\operatorname {arg\,min} _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)+R(w)$

В качестве частного случая рассмотрим случай онлайновой линейной оптимизации, то есть, когда природа возвращает функции потерь вида $v_{t}(w)=\langle w,z_{t}\rangle$. Также пусть $S=\mathbb {R} ^{d}$. Предположим, что функция регуляризации $R(w)={\frac {1}{2\eta }}||w||_{2}^{2}$ выбирается для некоторого положительного числа $\eta$. Тогда можно показать, что итерация минимизации «сожаления» превращается в

$w_{t+1}=-\eta \sum _{i=1}^{t}z_{i}=w_{t}-\eta z_{t}$

Заметим, что это может быть переписано как $w_{t+1}=w_{t}-\eta \nabla v_{t}(w_{t})$, что выглядит совершенно аналогично методу онлайнового градиентного спуска.

Если S является выпуклым подпространством $\mathbb {R} ^{d}$, S нужно спроецировать, что приводит к модифицированному правилу обновления

$w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})$

Алгоритм известен как ленивая проекция, так как вектор $\theta _{t+1}$ аккумулирует градиенты. Это известно также как алгоритм двойного усреднения Нестерова (или субградиентным методом с двойным усреднением). В этом сценарии линейные функции потерь и квадратичная регуляризация «сожаление» ограничено значением $O({\sqrt {T}})$, а тогда среднее «сожаления» стремится к 0.

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

См. также: Субградиентный метод

Выше доказана граница «сожаления» для линейных функций потерь $v_{t}(w)=\langle w,z_{t}\rangle$. Для обобщения алгоритма на любую выпуклую функции потерь используется субградиент $\partial v_{t}(w_{t})$ функции $v_{t}$ как линейная аппроксимация $v_{t}$ около $w_{t}$, что приводит к алгоритму онлайнового субградиентного спуска:

Инициируем параметр $\eta ,w_{1}=0$

Для $t=1,2,...,T$

• Делаем предсказание, используя $w_{t}$, получаем от природы $f_{t}$.
• Выбираем $z_{t}\in \partial v_{t}(w_{t})$
• Если $S=\mathbb {R} ^{d}$, делаем обновление $w_{t+1}=w_{t}-\eta z_{t}$
• Если $S\subset \mathbb {R} ^{d}$, проецируем кумулятивные градиенты в $S$ i.e. $w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}$

Можно использовать алгоритм онлайнового субградиентного спуска для получения границ «сожаления» $O({\sqrt {T}})$ для онлайновой версии метода опорных векторов для классификации, которая использует кусочно-линейную функция потерь$v_{t}(w)=\max\{0,1-y_{t}(w\cdot x_{t})\}$

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

Алгоритмы следования за квадратично регуляризованным лидером приводят к алгоритмам лениво проецируемого градиента, как описаны выше. Чтобы использовать описанный выше подход для любых выпуклых функций и регуляризаторов, можно использовать онлайновый зеркальный спуск. Оптимальная регуляризация в кусочно-линейной функции может быть получена для линейных функций потерь, что приводит к алгоритму AdaGrad. Для евклидовой регуляризации можно показать, что граница «сожаления» равна $O({\sqrt {T}})$ и она может быть улучшена до $O(\log T)$ для строго выпуклых и exp-вогнутых функций потерь.

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

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

$\textstyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})$

Первая интерпретация рассматривает метод стохастического градиентного спуска как применение к задаче минимизации ожидаемого риска $I[w]$, определённого выше . Более того, в случае бесконечного потока данных, поскольку экземпляры $(x_{1},y_{1}),(x_{2},y_{2}),\ldots$ предполагаются выбранными из независимого и одинаково распределённого распределения $p(x,y)$, последовательности градиентов $V(\cdot ,\cdot )$ в итерации выше являются независимыми и одинаково распределёнными выборками стохастической оценки градиента ожидаемого риска $I[w]$, а потому можно применить результаты сложности для метода стохастического градиентного спуска для ограничения отклонения $I[w_{t}]-I[w^{\ast }]$, где $w^{\ast }$ является минимизатором $I[w]$. Эта интерпретация верна также в случае конечных тренировочных наборов. Хотя при неоднократном проходе по данным градиенты уже не будут независимыми, результаты сложности в частных случаях могут быть получены.

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

$I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .$

Поскольку градиенты $V(\cdot ,\cdot )$ в итерациях инкрементального градиентного спуска являются стохастическими оценками градиента $I_{n}[w]$, эта интерпретация связана с методом стохастического градиентного спуска, но применённого к минимизации эмпирического риска в противоположность ожидаемому риску. Поскольку эта интерпретация касается эмпирического риска, а не ожидаемого риска, многократные проходы по данным совершенно допустимы и, на самом деле, ведут к тесным границам отклонений $I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]$, где $w_{n}^{\ast }$ минимизатор $I_{n}[w]$.

Реализации

• Vowpal Wabbit: Быстрая система онлайнового обучения с внешней памятью и открытым кодом с некоторым набором поддерживаемых техник машинного обучения, со взвешиванием важности и выбором различных функций потерь и алгоритмов оптимизации. Система использует хеш-трюк для ограничения размера набора признаков независимо от размера тренировочных данных.
• scikit-learn: Обеспечивает реализацию с внешней памятью алгоритмов для
  • классификаторов: перцептрон, классификатор методом статистического градиентного спуска, наивный байесовский классификатор.
  • регрессии: регрессия стохастическим градиентным спуском, пассивный агрессивный регрессор.
  • кластеризации: метод k-средних.
  • выделения признаков: минипакетное словарное обучение, инкрементальный метод главных компонент.

См. также

• Иерархическая временная память
• Метод k ближайших соседей
• Ленивое обучение
• Квантизация вектора при обучении
• Офлайновое обучение, противоположная модель
• Онлайновый алгоритм
• Поточный алгоритм
• Перцептрон
• Стохастический градиентный спуск
• Обучение с учителем
• Онлайновая оптимизация

Ссылки

• http://onlineprediction.net/ Архивная копия от 31 октября 2018 на Wayback Machine, Wiki for On-Line Prediction.