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

Не путать онлайн и оффлайн .

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

Введение

В условиях контролируемого обучения функция $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$ намного меньше общего количества тренировочных очков. Мини-пакетные методы используются с повторной передачей обучающих данных для получения оптимизированных внеядерных версий алгоритмов машинного обучения, например, стохастического градиентного спуска . В сочетании с обратным распространением ошибки в настоящее время это фактический метод обучения искусственных нейронных сетей .

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

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

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

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

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

$$f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}$$

где $x_{j}\in \mathbb {R} ^{d}$ представляет собой вектор входных данных (точек данных) и $w\in \mathbb {R} ^{d}$ — вектор линейного фильтра.Цель состоит в том, чтобы вычислить вектор фильтра $w$.С этой целью квадратичная функция потерь

$$V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}$$

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

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

где

$$y_{j}\in \mathbb {R} .$$

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

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

Теперь вычисляем ковариационную матрицу $\Sigma _{i}=\sum _{j=1}^{i}x_{j}x_{j}^{\mathsf {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}^{\mathsf {T}}$, что занимает $O(d^{2})$ время, сокращая общее время до $O(nd^{2}+nd^{3})=O(nd^{3})$, но с дополнительным местом для хранения $O(d^{2})$ хранить $\Sigma _{i}$.

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

Алгоритм рекурсивного метода наименьших квадратов (RLS) рассматривает онлайн-подход к задаче наименьших квадратов. Можно показать, что инициализируя $\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}^{\mathsf {T}}\Gamma _{i-1}}{1+x_{i}^{\mathsf {T}}\Gamma _{i-1}x_{i}}}$$

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

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

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

спуск

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

Когда это

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

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

$$w_{i}=w_{i-1}-\gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)=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}}},$ можно доказать сходимость средней итерации ${\textstyle {\overline {w}}_{n}={\frac {1}{n}}\sum _{i=1}^{n}w_{i}}$. Этот параметр является частным случаем стохастической оптимизации , хорошо известной проблемы оптимизации.

спуск

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

$$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$ шаги алгоритма SGD , то

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

где $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}$, размерность которого равна размеру набора обучающих данных. В общем, это следствие теоремы о представителе .

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

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

Для $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}$.

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

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

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

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

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

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

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

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

$$w_{t}=\mathop {\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}$. Предположим, что функция регуляризации ${\textstyle R(w)={\frac {1}{2\eta }}\left\|w\right\|_{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 , как и хотелось.

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

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

Вышеупомянутое доказало ограничение сожаления для линейных функций потерь. $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$ т.е. $w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}$

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

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

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

Постоянное обучение

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

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

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

$$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 )$ в приведенной выше итерации представляют собой iid выборку стохастических оценок градиента ожидаемого риска. $I[w]$ и поэтому можно применить результаты сложности для метода стохастического градиентного спуска, чтобы ограничить отклонение $I[w_{t}]-I[w^{\ast }]$, где $w^{\ast }$ является минимизатором $I[w]$. Эта интерпретация справедлива и в случае конечного обучающего набора; хотя при многократном проходе по данным градиенты больше не являются независимыми, в особых случаях все же можно получить результаты по сложности.

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

$$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 : Обеспечивает внеядерные реализации алгоритмов для
  • Классификация: Персептрон , классификатор SGD , классификатор Наивного Байеса .
  • Регрессия: SGD-регрессор, пассивно-агрессивный регрессор.
  • Кластеризация: мини-пакетные k-средние .
  • Извлечение функций: мини-пакетное обучение словарю , инкрементальный PCA .

См. также

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

• Постепенное обучение
• Ленивое обучение
• Офлайн-обучение , противоположная модель
• Обучение с подкреплением
• Многорукий бандит
• Обучение под присмотром

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

• Онлайн-алгоритм
• Онлайн-оптимизация
• Алгоритм потоковой передачи
• Стохастический градиентный спуск

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

• Теория адаптивного резонанса
• Иерархическая временная память
• алгоритм k-ближайшего соседа
• Обучение векторному квантованию
• Персептрон

Внешние ссылки

• 6.883: Онлайн-методы машинного обучения: теория и приложения. Александр Рахлин. Массачусетский технологический институт