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

Метод машинного обучения

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

Введение

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

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

В статистических моделях обучения предполагается, что обучающая выборка была взята из истинного распределения , а цель состоит в том, чтобы минимизировать ожидаемый «риск». Распространенной парадигмой в этой ситуации является оценка функции с помощью минимизации эмпирического риска или регуляризованной минимизации эмпирического риска (обычно регуляризация Тихонова ). Выбор функции потерь здесь приводит к появлению нескольких известных алгоритмов обучения, таких как регуляризованные наименьшие квадраты и машины опорных векторов . Чисто онлайн-модель в этой категории будет обучаться только на основе новых входных данных , текущего наилучшего предиктора и некоторой дополнительной сохраненной информации (которая, как обычно ожидается, будет иметь требования к хранению, независимые от размера обучающих данных). Для многих формулировок, например, нелинейных методов ядра , настоящее онлайн-обучение невозможно, хотя можно использовать форму гибридного онлайн-обучения с рекурсивными алгоритмами, где разрешено зависеть от и всех предыдущих точек данных . В этом случае требования к пространству больше не гарантируются постоянными, поскольку для этого требуется хранение всех предыдущих точек данных, но решение может занять меньше времени для вычисления с добавлением новой точки данных по сравнению с методами пакетного обучения. ${\displaystyle (x_{i},y_{i})}$ ${\displaystyle p(x,y)}$ $${\displaystyle I[f]=\mathbb {E} [V(f(x),y)]=\int V(f(x),y)\,dp(x,y)\ .}$$ ${\displaystyle {\hat {f}}}$ ${\displaystyle (x_{t+1},y_{t+1})}$ ${\displaystyle f_{t}}$ ${\displaystyle f_{t+1}}$ ${\displaystyle f_{t}}$ ${\displaystyle (x_{1},y_{1}),\ldots ,(x_{t},y_{t})}$

Распространенной стратегией преодоления вышеуказанных проблем является обучение с использованием мини-пакетов, которые обрабатывают небольшую партию точек данных за раз, это можно рассматривать как псевдо-онлайн обучение для гораздо меньшего, чем общее количество точек обучения. Методы мини-пакетов используются с повторным прохождением по учебным данным для получения оптимизированных версий алгоритмов машинного обучения вне ядра , например, стохастического градиентного спуска . В сочетании с обратным распространением это в настоящее время является фактическим методом обучения для обучения искусственных нейронных сетей . ${\displaystyle b\geq 1}$ ${\displaystyle b}$

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

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

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

Рассмотрим настройку контролируемого обучения, где линейная функция должна быть изучена: где — вектор входов (точек данных), а — вектор линейного фильтра. Цель состоит в том, чтобы вычислить вектор фильтра . Для этого используется квадратичная функция потерь для вычисления вектора , который минимизирует эмпирические потери , где ${\displaystyle f}$ $${\displaystyle f(x_{j})=\langle w,x_{j}\rangle =w\cdot x_{j}}$$ ${\displaystyle x_{j}\in \mathbb {R} ^{d}}$ ${\displaystyle w\in \mathbb {R} ^{d}}$ ${\displaystyle w}$ $${\displaystyle V(f(x_{j}),y_{j})=(f(x_{j})-y_{j})^{2}=(\langle w,x_{j}\rangle -y_{j})^{2}}$$ ${\displaystyle w}$ $${\displaystyle 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}}$$ $${\displaystyle y_{j}\in \mathbb {R} .}$$

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

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

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

Алгоритм рекурсивных наименьших квадратов (RLS) рассматривает онлайн-подход к задаче наименьших квадратов. Можно показать, что, инициализируя и , решение линейной задачи наименьших квадратов, приведенной в предыдущем разделе, может быть вычислено с помощью следующей итерации: Вышеуказанный алгоритм итерации может быть доказан с помощью индукции по . ^[2] Доказательство также показывает, что . Можно также рассматривать RLS в контексте адаптивных фильтров (см. RLS ). ${\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}^{\mathsf {T}}\Gamma _{i-1}}{1+x_{i}^{\mathsf {T}}\Gamma _{i-1}x_{i}}}}$$ $${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ ${\displaystyle i}$ ${\displaystyle \Gamma _{i}=\Sigma _{i}^{-1}}$

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

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

Если заменить это на или на , это становится алгоритмом стохастического градиентного спуска. В этом случае сложность шагов этого алгоритма уменьшается до . Требования к памяти на каждом шаге постоянны и составляют . $${\displaystyle w_{i}=w_{i-1}-\Gamma _{i}x_{i}\left(x_{i}^{\mathsf {T}}w_{i-1}-y_{i}\right)}$$ $${\displaystyle 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})}$$ ${\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)}$

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

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

На практике можно выполнить несколько проходов стохастического градиента (также называемых циклами или эпохами) по данным. Полученный таким образом алгоритм называется методом инкрементального градиента и соответствует итерации. Главное отличие от метода стохастического градиента заключается в том, что здесь выбирается последовательность для решения того, какая точка обучения посещается на -м шаге. Такая последовательность может быть стохастической или детерминированной. Затем количество итераций отделяется от количества точек (каждая точка может рассматриваться более одного раза). Можно показать, что метод инкрементального градиента обеспечивает минимизацию эмпирического риска. ^[3] Инкрементальные методы могут быть выгодны при рассмотрении целевых функций, состоящих из суммы многих членов, например эмпирической ошибки, соответствующей очень большому набору данных. ^[1] $${\displaystyle 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}$

Методы ядра

Ядра могут использоваться для расширения вышеуказанных алгоритмов до непараметрических моделей (или моделей, где параметры образуют бесконечномерное пространство). Соответствующая процедура больше не будет по-настоящему онлайновой и вместо этого будет включать хранение всех точек данных, но все еще быстрее, чем метод грубой силы. Это обсуждение ограничено случаем квадратичной потери, хотя его можно расширить до любой выпуклой потери. Можно показать с помощью простой индукции ^[1] , что если — матрица данных, а — выход после шагов алгоритма SGD , то, где и последовательность удовлетворяет рекурсии: и Обратите внимание, что здесь просто стандартное ядро ​​на , а предиктор имеет вид ${\displaystyle X_{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle i}$ $${\displaystyle w_{i}=X_{i}^{\mathsf {T}}c_{i}}$$ ${\displaystyle 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 .}$$

Теперь, если вместо этого ввести общее ядро ​​и пусть предиктор будет тогда то же доказательство также покажет, что предиктор, минимизирующий потери наименьших квадратов, получается путем изменения вышеприведенной рекурсии на Вышеприведенное выражение требует сохранения всех данных для обновления . Общая временная сложность для рекурсии при оценке для -й точки данных составляет , где - стоимость оценки ядра по одной паре точек. ^[1] Таким образом, использование ядра позволило перейти от конечномерного пространства параметров к возможно бесконечномерному признаку, представленному ядром , вместо этого выполняя рекурсию по пространству параметров , размерность которого совпадает с размером обучающего набора данных. В общем, это является следствием теоремы о представителе . ^[1] ${\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}$ ${\displaystyle \textstyle w_{i}\in \mathbb {R} ^{d}}$ ${\displaystyle K}$ ${\displaystyle \textstyle c_{i}\in \mathbb {R} ^{i}}$

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

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

Для ${\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})}$

Цель состоит в том, чтобы минимизировать regret , или разницу между кумулятивными потерями и потерей лучшей фиксированной точки в ретроспективе. В качестве примера рассмотрим случай линейной регрессии наименьших квадратов онлайн. Здесь векторы веса берутся из выпуклого множества , а природа посылает обратно выпуклую функцию потерь . Обратите внимание, что здесь неявно отправляется с . ${\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}}$

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

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

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

Самое простое правило обучения, которое можно попробовать, — это выбрать (на текущем шаге) гипотезу, которая имеет наименьшие потери по всем прошлым раундам. Этот алгоритм называется Следовать за лидером, а раунд просто задается как: Таким образом, этот метод можно рассматривать как жадный алгоритм . Для случая квадратичной оптимизации онлайн (где функция потерь равна ) можно показать границу сожаления, которая растет как . Однако аналогичные границы не могут быть получены для алгоритма FTL для других важных семейств моделей, таких как линейная оптимизация онлайн. Чтобы сделать это, нужно модифицировать FTL, добавив регуляризацию. ${\displaystyle t}$ $${\displaystyle w_{t}=\mathop {\operatorname {arg\,min} } _{w\in S}\sum _{i=1}^{t-1}v_{i}(w)}$$ ${\displaystyle v_{t}(w)=\left\|w-x_{t}\right\|_{2}^{2}}$ ${\displaystyle \log(T)}$

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

Это естественная модификация FTL, которая используется для стабилизации решений FTL и получения лучших границ сожаления. Функция регуляризации выбирается и обучение выполняется в раунде t следующим образом: В качестве особого примера рассмотрим случай онлайн-линейной оптимизации, т.е. когда природа посылает обратно функции потерь вида . Также пусть . Предположим, что функция регуляризации выбрана для некоторого положительного числа . Тогда можно показать, что итерация минимизации сожаления становится Обратите внимание, что это можно переписать как , что выглядит в точности как онлайн-градиентный спуск. ${\displaystyle R:S\to \mathbb {R} }$ $${\displaystyle w_{t}=\mathop {\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}}$ ${\textstyle R(w)={\frac {1}{2\eta }}\left\|w\right\|_{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 — это некоторое выпуклое подпространство , S необходимо спроецировать на , что приводит к измененному правилу обновления Этот алгоритм известен как ленивая проекция, поскольку вектор накапливает градиенты. Он также известен как алгоритм двойного усреднения Нестерова. В этом сценарии линейных функций потерь и квадратичной регуляризации сожаление ограничено , и, таким образом, среднее сожаление стремится к 0, как и требовалось. ${\displaystyle \mathbb {R} ^{d}}$ $${\displaystyle w_{t+1}=\Pi _{S}(-\eta \sum _{i=1}^{t}z_{i})=\Pi _{S}(\eta \theta _{t+1})}$$ ${\displaystyle \theta _{t+1}}$ ${\displaystyle O({\sqrt {T}})}$

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

Выше доказано ограничение сожаления для линейных функций потерь . Чтобы обобщить алгоритм на любую выпуклую функцию потерь, субградиент используется как линейное приближение к близкому , что приводит к алгоритму спуска субградиента онлайн: ${\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}}$
• Если , спроецировать кумулятивные градиенты на ie ${\displaystyle S\subset \mathbb {R} ^{d}}$ ${\displaystyle S}$ ${\displaystyle w_{t+1}=\Pi _{S}(\eta \theta _{t+1}),\theta _{t+1}=\theta _{t}+z_{t}}$

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

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

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

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

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

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

Парадигма онлайн-обучения имеет различные интерпретации в зависимости от выбора модели обучения, каждая из которых имеет различные последствия относительно качества прогнозирования последовательности функций . Для этого обсуждения используется прототипный алгоритм стохастического градиентного спуска. Как отмечено выше, его рекурсия задается как ${\displaystyle f_{1},f_{2},\ldots ,f_{n}}$ $${\displaystyle w_{t}=w_{t-1}-\gamma _{t}\nabla V(\langle w_{t-1},x_{t}\rangle ,y_{t})}$$

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

Вторая интерпретация применима к случаю конечного обучающего набора и рассматривает алгоритм SGD как пример метода инкрементального градиентного спуска. ^[3] В этом случае вместо этого рассматривается эмпирический риск: поскольку градиенты в итерациях инкрементального градиентного спуска также являются стохастическими оценками градиента , эта интерпретация также связана с методом стохастического градиентного спуска, но применяется для минимизации эмпирического риска в отличие от ожидаемого риска. Поскольку эта интерпретация касается эмпирического риска, а не ожидаемого риска, многократные проходы по данным легко допускаются и фактически приводят к более узким границам отклонений , где — минимизатор . $${\displaystyle I_{n}[w]={\frac {1}{n}}\sum _{i=1}^{n}V(\langle w,x_{i}\rangle ,y_{i})\ .}$$ ${\displaystyle V(\cdot ,\cdot )}$ ${\displaystyle I_{n}[w]}$ ${\displaystyle I_{n}[w_{t}]-I_{n}[w_{n}^{\ast }]}$ ${\displaystyle w_{n}^{\ast }}$ ${\displaystyle I_{n}[w]}$

Реализации

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

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

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

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

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

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

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

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

Ссылки

1. Л. Росаско, Т. Поджио, Машинное обучение: подход регуляризации, MIT-9.520 Lectures Notes, рукопись, декабрь 2015 г. Глава 7 - Онлайн-обучение
2. Кушнер, Гарольд Дж.; Инь, Г. Джордж (2003). Стохастическая аппроксимация и рекурсивные алгоритмы с приложениями (второе изд.). Нью-Йорк: Springer. С. 8–12. ISBN 978-0-387-21769-7.
3. Bertsekas, DP (2011). Методы инкрементального градиента, субградиента и проксимального метода для выпуклой оптимизации: обзор. Оптимизация для машинного обучения, 85.
4. Хазан, Элад (2015). Введение в онлайн-выпуклую оптимизацию (PDF) . Основы и тенденции в оптимизации.
5. Паризи, Герман И.; Кемкер, Рональд; Парт, Хосе Л.; Канан, Кристофер; Вермтер, Стефан (2019). «Непрерывное обучение на протяжении всей жизни с помощью нейронных сетей: обзор». Нейронные сети . 113 : 54–71. arXiv : 1802.07569 . doi : 10.1016/j.neunet.2019.01.012. ISSN  0893-6080.
6. Ботту, Леон (1998). "Онлайн-алгоритмы и стохастические аппроксимации". Онлайн-обучение и нейронные сети . Cambridge University Press. ISBN 978-0-521-65263-6.
7. Стохастические аппроксимационные алгоритмы и их применение , Гарольд Дж. Кушнер и Г. Джордж Ин, Нью-Йорк: Springer-Verlag, 1997. ISBN 0-387-94916-X ; 2-е изд., под названием Стохастические аппроксимационные и рекурсивные алгоритмы и их применение , 2003, ISBN 0-387-00894-2 .  

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

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