Large-Scale Machine Learning & Example

https://www.coursera.org/course/ml

После линейной регрессии была логистическая регрессия.

А потом начались нейросети — Neural Networks.

Потом нас учили правильно применять изученные алгоритмы (Advice for Applying Machine Learning).

А потом нам рассказали про Support Vector Machines (SVMs) и Kernels.

А потом была неделя посвященная темам Clustering (K-Means) и Dimensionality Reduction (PCA).

А после были рассмотрены алгоритмы систем Anomaly Detection и Recommender Systems.

А потом наступила последняя, 10-я неделя обучения, на которой кратенько были рассмотрены способы масштабирования задач ML — Large-scale Machine Learning и, более подробно, пример решения практической задачи с применением инструментов ML.

Итак, Large-scale Machine Learning.

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

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

В чем заключаются проблемы огромных датасетов? В том, что алгоритм будет слишком долго заниматься расчетами. К примеру, gradient descent итеративно (в смысле многократно) вычисляет суммы расчетов по всем записям датасета. А записей — миллионы и даже миллиарды. Это реально долго.

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

Как проверить — имеет ли смысл увеличение датасета? Просто. Использовать learning curves. Кривые обучения от размера датасета показывают оверфиттинг / high variance на малых датасетах? Значит увеличение датасета может помочь (а может и нет, надо и к этому быть готовым, увеличение датасета это не серебряная пуля).

Допустим, решено использовать огромный датасет.

Есть два основных подхода к перевариванию больших датасетов:

Stochastic Gradient Descent и

Map Reduce (data parallelizm)

Широко используемый в ML метод оптимизации (нахождение оптимума/минимума) Batch Gradient Descent становится неподъемным при обработке огромных датасетов. Вычислительно очень дорогим из-за необходимости крутить циклы вычислений по всем записям датасета.

Модификация BGD называется Stochastic Gradient Descent.

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

В итоге получается интересная картина. Вместо плавного продвижения к оптимуму наблюдается нервная пляска вокруг дороги к этому оптимуму.

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

Как много повторений внешнего цикла надо сделать? Это зависит от размера датасета и определяется сходимостью результата тета. Обычно хватает 1-10 повторений.

Компромиссом между Batch Gradient Descent и Stochastic Gradient Descent является Mini-batch Gradient Descent.

Мини-батч GD использует не все и не одну запись, он использует поднабор b (mini-batch size) записей датасета.

Хорошо векторизованная реализация мини-батч GD может обогнать по производительности стохастический GD.

Недостаток мини-батч GD в том, что у нас появляется еще один параметр b, надо уделять время на его подбор и проверку.

Stochastic Gradient Descent Convergence. А как подобрать learning rate альфа для стохастик GD? Как убедиться в безглючности стохастик GD? Сходится ли стохастик GD?

Для этого используем уже известную технику — рисование графика зависимости цены (ошибки) от количества итераций. Правильный график должен снижаться. В данном случае цена представляет собой среднее значение для последних, скажем, 1000 итераций.

Свойство стохастического GD (обработка по одной записи) используется в отдельном классе задач — Online Learning. Суть алгоритма решения таких задач в том, что мы имеем дело с потоком записей, обрабатываем их по мере поступления и выбрасываем, не сохраняем.

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

Продолжение следует...

original post http://vasnake.blogspot.com/2014/07/large-scale-machine-learning-example.html