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

10

давайте предположим, что я хочу обучить алгоритм регрессии стохастического градиентного спуска, используя набор данных, который имеет N выборок. Поскольку размер набора данных фиксирован, я буду использовать данные T раз. На каждой итерации или «эпохе» я использую каждую обучающую выборку ровно один раз после случайного переупорядочения всего обучающего набора.

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

Кто-нибудь знает векторизованную реализацию стохастического градиентного спуска?

РЕДАКТИРОВАТЬ : Меня спросили, почему я хотел бы использовать градиентный спуск онлайн, если размер моего набора данных фиксирован.

Из [1] видно, что градиентный спуск в режиме онлайн сходится медленнее, чем градиентный спуск в пакетном режиме, до минимума эмпирической стоимости. Однако он сходится быстрее к минимуму ожидаемой стоимости, которая измеряет производительность обобщения. Я хотел бы проверить влияние этих теоретических результатов на мою конкретную проблему с помощью перекрестной проверки. Без векторизованной реализации мой онлайн-код градиентного спуска будет намного медленнее, чем кодовый спуск. Это значительно увеличивает время, необходимое для завершения процесса перекрестной проверки.

РЕДАКТИРОВАТЬ : я включаю здесь псевдокод моей реализации градиентного спуска в режиме онлайн, по запросу ffriend. Я решаю проблему регрессии.

Method: on-line gradient descent (regression)
Input: X (nxp matrix; each line contains a training sample, represented as a length-p vector), Y (length-n vector; output of the training samples)
Output: A (length-p+1 vector of coefficients)

Initialize coefficients (assign value 0 to all coefficients)
Calculate outputs F
prev_error = inf
error = sum((F-Y)^2)/n
it = 0
while abs(error - prev_error)>ERROR_THRESHOLD and it<=MAX_ITERATIONS:
    Randomly shuffle training samples
    for each training sample i:
        Compute error for training sample i
        Update coefficients based on the error above
    prev_error = error
    Calculate outputs F
    error = sum((F-Y)^2)/n
    it = it + 1

[1] «Крупномасштабное онлайн-обучение», Л. Ботту, Й. Ле Канн, NIPS 2003.

Пабло Суау
источник
2
Разделите набор данных на мини-партии и последовательно установите модель для каждой мини-партии.
друг
Спасибо, @ffriend. Однако это не будет чисто онлайн-реализацией.
Пабло Суау
1
В чем причина использования «чисто онлайн» реализации, если ваш набор данных исправлен? SGD только говорит, что вам не нужно итерировать весь набор данных сразу, но вы можете разбить его на произвольное количество частей (мини-пакетов) и обрабатывать их одну за другой. Мини-пакет размером 1 имеет смысл, только если у вас есть непрерывный и, возможно, бесконечный источник данных (например, канал Twitter) и вы хотите обновлять модель после каждого нового наблюдения. Но это очень редкий случай и определенно не для фиксированных наборов данных.
друг
Извиняюсь за мой очень поздний ответ. Пожалуйста, проверьте текст, который я добавил к исходному вопросу.
Пабло Суау
1
Можете ли вы показать свою реализацию? Я вижу недоразумение, но без примера кода это будет сложно объяснить.
друг

Ответы:

10

Прежде всего, слово «образец» обычно используется для описания подгруппы населения , поэтому я буду ссылаться на то же, что и «пример».

Ваша реализация SGD медленная из-за этой строки:

for each training example i:

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

Вы можете, однако, приблизить истинный SGD, используя мини-партии . Мини-пакет - это небольшое подмножество исходного набора данных (скажем, 100 примеров). Вы рассчитываете ошибки и обновления параметров, основываясь на мини-пакетах, но вы все равно выполняете итерацию по многим из них без глобальной оптимизации, что делает процесс стохастическим. Итак, чтобы сделать вашу реализацию намного быстрее, достаточно изменить предыдущую строку на:

batches = split dataset into mini-batches
for batch in batches: 

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

Хотя это довольно очевидно, я должен также упомянуть векторизацию на уровне каждого отдельного примера. То есть вместо чего-то вроде этого:

theta = np.array([...])  # parameter vector
x = np.array([...])      # example
y = 0                    # predicted response
for i in range(len(example)):
    y += x[i] * theta[i]
error = (true_y - y) ** 2  # true_y - true value of response

Вы должны определенно сделать что-то вроде этого:

error = (true_y - sum(np.dot(x, theta))) ** 2

которые, опять же, легко обобщить для мини-партий:

true_y = np.array([...])     # vector of response values
X = np.array([[...], [...]]) # mini-batch
errors = true_y - sum(np.dot(X, theta), 1)
error = sum(e ** 2 for e in errors)
ffriend
источник
1
Я думаю, что это путь. Мини-партии с правильно выбранным размером на самом деле могут сходиться быстрее, чем пакетная или онлайн-версия (первые обновляют веса только один раз для всего набора, а последние не могут быть векторизованы, а также имеют дополнительные шаги по обновлению веса)
Нил Слейтер,
Спасибо вам обоим. Извиняюсь за упорно отвергая мини партии раньше, но я не был уверен в последствиях этого метода на скорости сходимости. Нил, твое утверждение исходит из твоего собственного опыта, или есть опубликованные теоретические / эмпирические результаты?
Пабло Суау
1
@PabloSuau Вы можете проверить курс машинного обучения Эндрю Нга на Coursera, 10-я неделя, он объясняет, почему конвергенция может быть быстрее, чем как SGD, так и групповой GD. Чтобы быть более точным: это всегда должно быть так же быстро, как SGD, но иногда это должно быть еще быстрее на практике.
Габорист
1

Посмотрите метод part_fit в SGD-классификаторе scikit . Вы можете контролировать то, что вы называете этим: вы можете сделать это «истинным» обучением в режиме онлайн, передавая экземпляр за раз, или вы можете группировать экземпляры в мини-пакеты, если все ваши данные доступны в массиве. Если они есть, вы можете нарезать массив, чтобы обеспечить мини-пакеты.

Бен Аллисон
источник