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

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

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

${\displaystyle 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}}$, где

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

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

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

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

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

${\displaystyle \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}}}}$

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

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

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

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

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

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

${\displaystyle \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})}$

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

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

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

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

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

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

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

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

${\displaystyle c_{0}=0}$

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

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

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

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

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

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

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

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

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

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

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

Для ${\displaystyle t=1,2,...,T}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Для ${\displaystyle t=1,2,...,T}$

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

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

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