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

Question

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

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

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

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

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

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

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.

Answer 1

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

Ваша реализация 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)

Answer 2

Проверьте метод partial_fit SGD -классификатор SGIKIT. Анкет У вас есть контроль над тем, что вы называете с этим: вы можете сделать это «истинное» онлайн-обучение, пропустив экземпляр за раз, или вы можете разобраться в экземплярах в мини-партии, если все ваши данные доступны в массиве. Если они есть, вы можете нарезать массив, чтобы предоставить Minibatches.