В прошлый раз
я обрисовал материал
второй недели обучения. Пощупали
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
Комментариев нет:
Отправить комментарий