Машинное обучение онлайн - Online machine learning

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

Вступление

В обстановке контролируемое обучение, функция ${displaystyle f:X o Y}$ нужно узнать, где ${displaystyle X}$ рассматривается как пространство входов и ${displaystyle Y}$ как пространство выходных данных, которое хорошо предсказывает экземпляры, взятые из совместное распределение вероятностей ${displaystyle p(x,y)}$ на ${displaystyle X imes Y}$. На самом деле ученик никогда не знает истинного распределения ${displaystyle p(x,y)}$ по экземплярам. Вместо этого ученик обычно имеет доступ к обучающему набору примеров. ${displaystyle (x_{1},y_{1}),ldots ,(x_{n},y_{n})}$. В этой настройке функция потерь дается как ${displaystyle V:Y imes Y o mathbb {R} }$, так что ${displaystyle V(f(x),y)}$ измеряет разницу между прогнозируемым значением ${displaystyle f(x)}$ и истинная ценность ${displaystyle y}$. Идеальная цель - выбрать функцию ${displaystyle fin {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 bgeq 1}$ точек данных за раз, это можно рассматривать как псевдо-онлайн-обучение для ${displaystyle b}$ намного меньше, чем общее количество тренировочных точек. Используются мини-пакетные методы с повторной передачей обучающих данных для получения оптимизированных вне ядра.^{[требуется разъяснение ]} версии алгоритмов машинного обучения, например, стохастический градиентный спуск. В сочетании с обратное распространение, в настоящее время это де-факто метод обучения для тренировки искусственные нейронные сети.

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

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

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

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

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

${displaystyle f(x_{j})=langle w,x_{j}angle =wcdot x_{j}}$

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

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

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

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

где

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

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

${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 imes 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}}$.^[1]

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

Рекурсивный алгоритм наименьших квадратов (RLS) рассматривает онлайн-подход к проблеме наименьших квадратов. Можно показать, что инициализируя ${displaystyle extstyle w_{0}=0in mathbb {R} ^{d}}$ и ${displaystyle extstyle Gamma _{0}=Iin mathbb {R} ^{d imes 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}$.^[2] Доказательство также показывает, что ${displaystyle Gamma _{i}=Sigma _{i}^{-1}}$. Можно посмотреть на RLS и в контексте адаптивных фильтров (см. RLS ).

Сложность для ${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}}$.^[1]

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

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

Когда это

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

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

${displaystyle extstyle w_{i}=w_{i-1}-gamma _{i}x_{i}(x_{i}^{T}w_{i-1}-y_{i})=w_{i-1}-gamma _{i}abla V(langle w_{i-1},x_{i}angle ,y_{i})}$

или ${displaystyle Gamma _{i}in mathbb {R} ^{d imes 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}}$. Этот параметр является частным случаем стохастическая оптимизация, хорошо известная проблема в оптимизации.^[1]

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

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

${displaystyle extstyle w_{i}=w_{i-1}-gamma _{i}abla V(langle w_{i-1},x_{t_{i}}angle ,y_{t_{i}})}$

Основное отличие от метода стохастического градиента состоит в том, что здесь последовательность ${displaystyle t_{i}}$ выбирается, чтобы решить, какую тренировочную точку посетить в ${displaystyle i}$-й шаг. Такая последовательность может быть стохастической или детерминированной. Затем количество итераций отделяется от количества точек (каждая точка может рассматриваться более одного раза). Можно показать, что метод инкрементного градиента минимизирует эмпирический риск.^[3] Дополнительные методы могут быть полезными при рассмотрении целевых функций, состоящих из суммы многих членов, например эмпирическая ошибка, соответствующая очень большому набору данных.^[1]

Методы ядра

Смотрите также: Метод ядра

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

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

где ${displaystyle extstyle 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}angle {Big )}}$

Обратите внимание, что здесь ${displaystyle langle x_{j},x_{i}angle }$ это просто стандартное ядро ​​на ${displaystyle mathbb {R} ^{d}}$, а предиктор имеет вид

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

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

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

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

За ${displaystyle t=1,2,...,T}$

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

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

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

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

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

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

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

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

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

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

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

В качестве частного примера рассмотрим случай линейной оптимизации онлайн, то есть когда природа возвращает функции потерь вида ${displaystyle v_{t}(w)=langle w,z_{t}angle }$. Кроме того, пусть ${displaystyle S=mathbb {R} ^{d}}$. Предположим, что функция регуляризации ${displaystyle R(w)={frac {1}{2eta }}||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 abla 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 heta _{t+1})}$

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

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

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

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

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

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

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

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

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

${displaystyle extstyle w_{t}=w_{t-1}-gamma _{t}abla V(langle w_{t-1},x_{t}angle ,y_{t})}$

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

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

${displaystyle I_{n}[w]={frac {1}{n}}sum _{i=1}^{n}V(langle w,x_{i}angle ,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]}$.

Реализации

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

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

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

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

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

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

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

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

Рекомендации

1. Л. Росаско, Т. Поджио, Машинное обучение: подход регуляризации, MIT-9.520 Lectures Notes, Manuscript, декабрь 2015 г. Глава 7 - Онлайн-обучение
2. Инь, Гарольд Дж. Кушнер, Дж. Джордж (2003). Стохастическая аппроксимация и рекурсивные алгоритмы и приложения (Второе изд.). Нью-Йорк: Спрингер. стр.8 –12. ISBN  978-0-387-21769-7.
3. Бертсекас, Д. П. (2011). Инкрементальный градиент, субградиент и проксимальные методы выпуклой оптимизации: обзор. Оптимизация для машинного обучения, 85.
4. Хазан, Элад (2015). Введение в онлайн-оптимизацию выпуклости (PDF). Основы и тенденции оптимизации.
5. Ботту, Леон (1998). «Онлайн-алгоритмы и стохастические аппроксимации». Онлайн-обучение и нейронные сети. Издательство Кембриджского университета. ISBN  978-0-521-65263-6.
6. Алгоритмы и приложения стохастической аппроксимации, Гарольд Дж. Кушнер и Дж. Джордж Инь, Нью-Йорк: Springer-Verlag, 1997. ISBN  0-387-94916-X; 2-е изд., Назв. Стохастическая аппроксимация и рекурсивные алгоритмы и приложения, 2003, ISBN  0-387-00894-2.

внешняя ссылка

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