Записки программиста, обо всем и ни о чем. Но, наверное, больше профессионального.

2015-08-17

Week 3


В прошлый раз я обрисовал материал второй недели обучения. Пощупали Apache Spark руками.
Теперь посмотрим, что было на третьей неделе.

Линейная регрессия и как ее обсчитывать распределенно.

WEEK 3: Linear Regression and Distributed Machine Learning Principles
Topics:
  • Linear regression formulation and closed-form solution,
  • distributed machine learning principles (related to computation, storage, and communication),
  • gradient descent,
  • quadratic features,
  • grid search.

Lab 3: Millionsong Regression Pipeline.
Develop an end-to-end linear regression pipeline to predict the release year of a song given a set of audio features.
You will implement a gradient descent solver for linear regression, use Spark's machine Learning library ( mllib) to train additional models, tune models via grid search, improve accuracy using quadratic features, and visualize various intermediate results to build intuition.

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

Задача линейной регрессии (supervised learning problem) заключается в отыскании такого вектора w, чтобы умножение этого вектора на вектор свойств (features) давало желаемый результат.
y = w0*x0 + w1*x1 + w2*x2 + w3*x3
То есть, надо решить задачу оптимизации, минимизировать потери
(y — yTrain)**2
Эту задачу можно решить аналитически, closed-form solution. Такое решение существует, если существует инверсная матрица
inv(Xtranspose * X)
w = inv(Xtranspose * X) * Xtranspose * y

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

Но пока нам заливают про общие проблемы: overfitting, regularization, generalization and so on.

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

Модель с регуляризацией называется Ridge Regression.

Чтобы подобрать подходящую лямбду, иными словами – найти оптимальный гиперпараметр модели, используется набор данных cross validation set. Как мы помним, начальный набор данных делится на три: training set, test set, cross validation set.
Меняя гиперпараметр, мы обучаем модель на training set и проверяем на cross validation set. Выбираем такой гиперпараметр, который на кросс-валидации дает наименьшую ошибку.

Метод поиска гиперпараметров называется grid search, потому как для двух гиперпараметров схема похожа на решетку.

И закончить описание регрессии можно способом оценки результата.
Оценка проводится через вычисление RMSE root-mean-square error.
Сумма квадратов разниц, поделенная на количество наблюдений. Да, проверка проводится на test set.

Дальше стало интереснее, пошла тема про особенности распределенного вычисления регресии.

Что нам стоит дом построить найти closed-form solution для линейной регрессии с наименьшей квадратичной ошибкой
w = inv(Xtranspose * X) * Xtranspose * y
Какие потребности во времени и хранилище?

Выходит так, что Xtranspose * X по времени занимает O(n * d**2)
а inv(matrix) уже O(d**3)
То есть, когда количество фичей (features) становится очень большим, считать closed-form solution уже совсем невыгодно.
In summary, we say that computing
the closed-form solution for linear regression
takes O of nd squared plus d cubed time.

С хранилищем не лучше.
Xtranspose * X и их инверсия занимают O(d**2) места,
тогда как X требует O(nd).

В общем, выходит так, что при большом количестве наблюдений n и малом количестве фич d, мы можем посчитать closed-form solution, распределив записи (n) по разным выч.узлам.
Фишка в том, что Xtranspose * X можно посчитать как сумму outer products между строками X. Поэтому строки можно раздать на разные ноды и там считать.

Но, в целом, это все имеет чисто академический интерес для нас. Ибо первое правило гласит: вычислительная и хранительная сложность должны быть линейны в терминах n, d.
Нам нужен другой алгоритм.

Кроме того, можно использовать такое свойство данных как разреженность (sparsity). Очень часто вектор содержит 99% нулей и только 1% значимых чисел.
Данные можно сжать и обрабатывать в сжатом виде.

Другой вариант, применить метод снижения размерности, типа PCA. И работать с сильно сокращенной версией данных.

Но всех спасти может только Gradient Descent. Алгоритм оптимизации (поиск минимума loss function) с линейной зависимостью от n,d.
Все, что требуется, это наличие одного минимума у оптимизируемой функции.

Thankfully for us, least squares regression, ridge regression,
and logistic regression, which we'll
be looking at later in this course,
all involve minimizing convex functions.

Направление движения к минимуму мы определяем по знаку производной;
Количество итераций алгоритма – гиперпараметр (можно подобрать через grid search);
Шаг движения alpha – тоже гиперпараметр.
На практике применяют постепенное уменьшение alpha
alpha[i] = alpha / (n * sqrt(i))
i – iteration number
n — training points (records)

This entire process can be concisely described
via the following Spark code snippet.
In this snippet, we perform a fixed number of iterations
as specified by numIters.
And on each iteration, we first compute
the iteration-specific step size and then compute the gradient
via a MapReduce operation.
Finally, we use the gradient descent update
rule to update w.

Now to conclude, gradient descent
has some nice favorable properties.
It is easily parallelized, and each iteration
is cheap enough to scale to the big N, big D setting.
Additionally, stochastic variance of gradient descent
can be used to further speed up the algorithm.

Но, что поделать, алгоритм медленно сходится и требует общения между нодами – передача параметров w на каждой итерации на каждую ноду.

В завершение описания Gradient Descent нам продемонстрировали важность таких вещей как локальность вычислений и минимизация сообщений.
Передавать данные дорого и чем дальше от процессора, тем дороже.
Mini-batch.

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

Distributed iterative algorithms was both compute
and perform communication.
And in a bulk synchronous, in Bulk Synchronous Parallel
Systems or BSP systems like Apache Spark
we strictly alternate between computation and communication,
so that all worker nodes are synchronized.
Hence each iteration of an iterative algorithm
incurs some communication overhead.
In order to take advantage of parallel computation,
but reduce network cost, we'd like
to design algorithms that compute more and communicate
less.

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

In parallel gradient descent, at each iteration
each worker simply computes its contribution to the gradient
and sends it back to the driver.
In contrast, at the beginning of each mini-batch iteration,
each worker starts with the same parameter vector,
but then performs a few steps of gradient descent locally.
After each of the k workers has performed its local updates,
these workers then send their updated parameter vectors
back to the driver and the driver
combines these different models, perhaps via averaging.

И, конечно, не надо забывать о network latency. Сообщения надо собирать в большие пакеты и отправлять весь пакет разом. Например, через раздачу на ноды сразу нескольких моделей для тренировки.

Про лабораторку расскжу в следующий раз.











original post http://vasnake.blogspot.com/2015/08/week-3.html

Комментариев нет:

Отправить комментарий

Архив блога

Ярлыки

linux (241) python (191) citation (186) web-develop (170) gov.ru (159) video (124) бытовуха (115) sysadm (100) GIS (97) Zope(Plone) (88) бурчалки (84) Book (83) programming (82) грабли (77) Fun (76) development (73) windsurfing (72) Microsoft (64) hiload (62) internet provider (57) opensource (57) security (57) опыт (55) movie (52) Wisdom (51) ML (47) driving (45) hardware (45) language (45) money (42) JS (41) curse (40) bigdata (39) DBMS (38) ArcGIS (34) history (31) PDA (30) howto (30) holyday (29) Google (27) Oracle (27) tourism (27) virtbox (27) health (26) vacation (24) AI (23) Autodesk (23) SQL (23) humor (23) Java (22) knowledge (22) translate (20) CSS (19) cheatsheet (19) hack (19) Apache (16) Manager (15) web-browser (15) Никонов (15) Klaipeda (14) functional programming (14) happiness (14) music (14) todo (14) PHP (13) course (13) scala (13) weapon (13) HTTP. Apache (12) SSH (12) frameworks (12) hero (12) im (12) settings (12) HTML (11) SciTE (11) USA (11) crypto (11) game (11) map (11) HTTPD (9) ODF (9) Photo (9) купи/продай (9) benchmark (8) documentation (8) 3D (7) CS (7) DNS (7) NoSQL (7) cloud (7) django (7) gun (7) matroska (7) telephony (7) Microsoft Office (6) VCS (6) bluetooth (6) pidgin (6) proxy (6) Donald Knuth (5) ETL (5) NVIDIA (5) Palanga (5) REST (5) bash (5) flash (5) keyboard (5) price (5) samba (5) CGI (4) LISP (4) RoR (4) cache (4) car (4) display (4) holywar (4) nginx (4) pistol (4) spark (4) xml (4) Лебедев (4) IDE (3) IE8 (3) J2EE (3) NTFS (3) RDP (3) holiday (3) mount (3) Гоблин (3) кухня (3) урюк (3) AMQP (2) ERP (2) IE7 (2) NAS (2) Naudoc (2) PDF (2) address (2) air (2) british (2) coffee (2) fitness (2) font (2) ftp (2) fuckup (2) messaging (2) notify (2) sharepoint (2) ssl/tls (2) stardict (2) tests (2) tunnel (2) udev (2) APT (1) CRUD (1) Canyonlands (1) Cyprus (1) DVDShrink (1) Jabber (1) K9Copy (1) Matlab (1) Portugal (1) VBA (1) WD My Book (1) autoit (1) bike (1) cannabis (1) chat (1) concurrent (1) dbf (1) ext4 (1) idioten (1) join (1) krusader (1) license (1) life (1) migration (1) mindmap (1) navitel (1) pneumatic weapon (1) quiz (1) regexp (1) robot (1) science (1) serialization (1) spatial (1) tie (1) vim (1) Науру (1) крысы (1) налоги (1) пианино (1)