Русская Википедия:Онлайновое машинное обучение

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

Введение

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

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

В статистических моделях обучения проверочная выборка <math> (x_i,y_i) </math> предполагается извлечённой из истинного распределения <math>p(x,y)</math> и целью обучения является минимизация ожидаемого «риска»

<math>I[f] = \mathbb{E}[V(f(x), y)] = \int V(f(x), y)\,dp(x, y) \ .</math>

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

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

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

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

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

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

<math> I_n[w] = \sum_{j=1}^{n} V(\langle w,x_j\rangle,y_j) = \sum_{j=1}^{n} (x_j^Tw-y_j)^2 </math>, где
<math> x_j \in \mathbb{R}^d, w \in \mathbb{R}^d, y_j \in \mathbb{R}</math>.

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

<math> w^* = (X^TX)^{-1}X^TY = \Sigma_i^{-1} \sum_{j=1}^{i} x_j y_j </math>.

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

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

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

<math> \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} </math>
<math>w_i = w_{i-1}-\Gamma_ix_i(x_i^T w_{i-1}-y_i)</math>

Приведённый выше итерационный алгоритм может быть доказан с помощью индукции по <math> i </math>Шаблон:Sfn. Доказательство также показывает, что <math> \Gamma_i = \Sigma_i^{-1} </math>. Можно рассматривать рекурсивный метод наименьших квадратов в контексте адаптивных фильтров (см. Шаблон:Не переведено 5).

Сложность <math>n</math> шагов этого алгоритма равна <math>O(nd^2)</math>, что быстрее, чем соответствующая сложность пакетного обучения. Память, требуемая для каждого шага <math>i</math> для сохранения матрицы <math>\Gamma_i</math>, здесь является константой <math>O(d^2)</math>. Для случая, когда <math> \Sigma_i </math> не обратима, рассматривается регуляризованная версия функции потерь <math> \sum_{j=1}^{n} (x_j^Tw - y_j)^2 + \lambda||w||_2^2 </math>. Тогда просто показать, что тот же алгоритм работает с <math> \Gamma_0 = (I + \lambda I)^{-1} </math>, и продолжение итераций даёт <math> \Gamma_i = (\Sigma_i + \lambda I)^{-1} </math>Шаблон:Sfn.

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

Шаблон:Основная статья Если равенство

<math>\textstyle w_i = w_{i-1}-\Gamma_ix_i(x_i^T w_{i-1}-y_i)</math>

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

<math> \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)</math>

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

Однако размер шага <math>\gamma_i</math> для решения задачи минимизации ожидаемого риска следует выбирать осторожно, как объяснено выше. При выборе размера шага затухания <math> \gamma_i \approx \frac{1}{\sqrt{i}}</math> можно доказать сходимость средней итерации <math> \overline{w}_n = \frac{1}{n} \sum_{i=1}^{n} w_i </math>. Эти установки являются частным случаем стохастической оптимизации, хорошо известной задачи оптимизацииШаблон:Sfn.

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

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

<math> \textstyle w_i = w_{i-1} - \gamma_i \nabla V(\langle w_{i-1}, x_{t_i} \rangle, y_{t_i})</math>

Основная разница с методом стохастического градиента заключается в том, что здесь выбирается <math> t_i </math> для решения, какая тренировочная точка посещена на шаге <math> i </math>. Такая последовательность может быть случайной или детерминированной. Число итераций, таким образом, отвязывается от числа точек (каждая точка может быть просмотрена более чем один раз). Можно показать, что метод инкрементального градиента даёт минимизацию эмпирического рискаШаблон:Sfn. Инкрементальные техники могут иметь преимущества, если рассматривать целевую функцию как сумму многих элементов, например, как эмпирическую ошибку очень большого набора данныхШаблон:Sfn.

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

Шаблон:См. также Ядра могут быть использованы для расширения вышеприведённых алгоритмов до непараметрических моделей (или моделей, в которых параметры образуют бесконечномерное пространство). Соответствующая процедура более не будет истинно онлайновой и вместо этого сохраняет все точки данных, но метод остаётся более быстрым, чем прямой перебор. Данное обсуждение ограничено случаем квадратных потерь, хотя оно может быть расширено до любой выпуклой функции потерь. Можно показать прямой индукциейШаблон:Sfn, что когда <math> X_i </math> является матрицей данных, а <math> w_i </math> является выходом после <math> i </math> шагов алгоритма случайного градиентного спуска, то

<math> w_i = X_i^T c_i </math>

где <math> \textstyle c_i = ((c_i)_1, (c_i)_2, ..., (c_i)_i) \in \mathbb{R}^i</math> и последовательность <math> c_i </math> удовлетворяет рекуррентным соотношениям

<math> c_0 = 0 </math>
<math> (c_i)_j = (c_{i-1})_j, j=1,2,...,i-1 </math> и
<math> (c_i)_i = \gamma_i \Big(y_i - \sum_{j=1}^{i-1} (c_{i-1})_j\langle x_j, x_i \rangle\Big) </math>

Заметим, что здесь <math> \langle x_j, x_i \rangle </math> является стандартным ядром в <math> \mathbb{R}^d </math>, и предсказательная функция имеет вид

<math> f_i(x) = \langle w_{i-1},x \rangle = \sum_{j=1}^{i-1} (c_{i-1})_j \langle x_j,x \rangle </math>.

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

<math> f_i(x) = \sum_{j=1}^{i-1} (c_{i-1})_j K(x_j,x) </math>,

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

<math> (c_i)_i = \gamma_i \Big(y_i - \sum_{j=1}^{i-1}(c_{i-1})_j K(x_j,x_i) \Big)</math>

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

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

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

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

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

Для <math> t = 1,2,...,T </math>

  • Ученик получает вход <math> x_t </math>
  • Ученик образует выход <math> w_t </math> из фиксированного выпуклого множества <math> S </math>
  • Природа возвращает значение выпуклой функции потерь <math> v_t : S \rightarrow \mathbb{R} </math>.
  • Ученик учитывает потерю <math>v_t(w_t)</math> и обновляет модель

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

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

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

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

Простейшее обучающее правило для пробы — выбрать (на текущем шаге) гипотезу, которая имеет наименьшие потери среди всех предыдущих раундов. Этот алгоритм называется «Следование за лидером» (Шаблон:Lang-en) и просто даёт раунд <math> t </math>:

<math> w_t = \operatorname{arg\,min}_{w \in S} \sum_{i=1}^{t-1} v_i(w) </math>

Этот метод можно тогда рассматривать как жадный алгоритм. Для случая онлайновой квадратичной оптимизации (где функция потерь равна <math> v_t(w) =||w - x_t||_2^2 </math>), можно показать, что граница «сожаления» растёт как <math> \log(T) </math>. Однако похожие границы не могут быть получены для алгоритма «следования за лидером» для других важных семейств моделей, как для онлайновой линейной оптимизации. Чтобы их получить, в алгоритм добавляется регуляризация.

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

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

<math>w_t = \operatorname{arg\,min}_{w \in S} \sum_{i=1}^{t-1}v_i(w) + R(w) </math>

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

<math > w_{t+1} = - \eta \sum_{i=1}^{t} z_i = w_t - \eta z_t</math>

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

Если Шаблон:Mvar является выпуклым подпространством <math> \mathbb{R}^d </math>, Шаблон:Mvar нужно спроецировать, что приводит к модифицированному правилу обновления

<math> w_{t+1} = \Pi_S(- \eta \sum_{i=1}^{t} z_i) = \Pi_S(\eta \theta_{t+1}) </math>

Алгоритм известен как ленивая проекция, так как вектор <math> \theta_{t+1} </math> аккумулирует градиенты. Это известно также как алгоритм двойного усреднения Нестерова (или субградиентным методом с двойным усреднениемШаблон:Sfn). В этом сценарии линейные функции потерь и квадратичная регуляризация «сожаление» ограничено значением <math> O(\sqrt{T}) </math>, а тогда среднее «сожаления» стремится к Шаблон:Mvar.

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

Шаблон:См. также Выше доказана граница «сожаления» для линейных функций потерь <math> v_t(w) = \langle w, z_t \rangle </math>. Для обобщения алгоритма на любую выпуклую функции потерь используется субградиент <math> \partial v_t(w_t) </math> функции <math> v_t </math> как линейная аппроксимация <math> v_t </math> около <math> w_t </math>, что приводит к алгоритму онлайнового субградиентного спуска:

Инициируем параметр <math> \eta, w_1 = 0 </math>

Для <math> t = 1,2,...,T </math>

  • Делаем предсказание, используя <math> w_t </math>, получаем от природы <math>f_t</math>.
  • Выбираем <math>z_t \in \partial v_t(w_t)</math>
  • Если <math> S = \mathbb{R}^d </math>, делаем обновление <math> w_{t+1} = w_t - \eta z_t</math>
  • Если <math> S \subset \mathbb{R}^d </math>, проецируем кумулятивные градиенты в <math> S </math> i.e. <math> w_{t+1} = \Pi_S(\eta\theta_{t+1}) , \theta_{t+1} = \theta_t + z_t</math>

Можно использовать алгоритм онлайнового субградиентного спуска для получения границ «сожаления» <math> O(\sqrt{T}) </math> для онлайновой версии метода опорных векторов для классификации, которая использует Шаблон:Не переведено 5<math> v_t(w) = \max \{ 0, 1 - y_t(w \cdot x_t) \} </math>

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

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

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

Парадигма онлайнового обучения имеет различные интерпретации в зависимости от выбора обучающей модели, каждая из которых имеет разное качество предсказаний последовательности функций <math>f_1, f_2, \ldots, f_n</math>. Для обсуждения используем алгоритм стохастического градиентного спуска. Как замечено выше, рекурсия алгоритма задаётся равенством

<math> \textstyle w_t = w_{t-1} - \gamma_t \nabla V(\langle w_{t-1}, x_t \rangle, y_t)</math>

Первая интерпретация рассматривает метод стохастического градиентного спуска как применение к задаче минимизации ожидаемого риска <math>I[w]</math>, определённого выше Шаблон:Sfn. Более того, в случае бесконечного потока данных, поскольку экземпляры <math>(x_1, y_1), (x_2, y_2), \ldots </math> предполагаются выбранными из независимого и одинаково распределённого распределения <math>p(x,y)</math>, последовательности градиентов <math>V(\cdot, \cdot)</math> в итерации выше являются независимыми и одинаково распределёнными выборками стохастической оценки градиента ожидаемого риска <math>I[w]</math>, а потому можно применить результаты сложности для метода стохастического градиентного спуска для ограничения отклонения <math>I[w_t] - I[w^\ast]</math>, где <math>w^\ast</math> является минимизатором <math>I[w]</math>Шаблон:Sfn. Эта интерпретация верна также в случае конечных тренировочных наборов. Хотя при неоднократном проходе по данным градиенты уже не будут независимыми, результаты сложности в частных случаях могут быть получены.

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

<math>I_n[w] = \frac{1}{n}\sum_{i = 1}^nV(\langle w,x_i \rangle, y_i) \ .</math>

Поскольку градиенты <math>V(\cdot, \cdot)</math> в итерациях инкрементального градиентного спуска являются стохастическими оценками градиента <math>I_n[w]</math>, эта интерпретация связана с методом стохастического градиентного спуска, но применённого к минимизации эмпирического риска в противоположность ожидаемому риску. Поскольку эта интерпретация касается эмпирического риска, а не ожидаемого риска, многократные проходы по данным совершенно допустимы и, на самом деле, ведут к тесным границам отклонений <math>I_n[w_t] - I_n[w^\ast_n]</math>, где <math>w^\ast_n</math> минимизатор <math>I_n[w]</math>.

Реализации

См. также

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки

Шаблон:Машинное обучение Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Катастрофическая помеха — это склонность искусственных нейронных сетей внезапно полностью забыть всё, чему сеть была обучена до этого.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Онлайновое_машинное_обучение&oldid=10516994