¿Descenso de gradiente estocástico basado en operaciones vectoriales?

10

supongamos que quiero entrenar un algoritmo de regresión de descenso de gradiente estocástico usando un conjunto de datos que tiene N muestras. Como el tamaño del conjunto de datos es fijo, reutilizaré los datos T veces. En cada iteración o "época", uso cada muestra de entrenamiento exactamente una vez después de reordenar aleatoriamente todo el conjunto de entrenamiento.

Mi implementación se basa en Python y Numpy. Por lo tanto, el uso de operaciones vectoriales puede disminuir notablemente el tiempo de cálculo. Proponer una implementación vectorizada del descenso de gradiente por lotes es bastante sencillo. Sin embargo, en el caso del descenso de gradiente estocástico, no puedo entender cómo evitar el bucle externo que recorre todas las muestras en cada época.

¿Alguien sabe alguna implementación vectorizada de descenso de gradiente estocástico?

EDITAR : Me han preguntado por qué me gustaría usar el descenso de gradiente en línea si el tamaño de mi conjunto de datos es fijo.

A partir de [1], se puede ver que el descenso de gradiente en línea converge más lentamente que el descenso de gradiente por lotes al mínimo del costo empírico. Sin embargo, converge más rápido al mínimo del costo esperado, que mide el rendimiento de la generalización. Me gustaría probar el impacto de estos resultados teóricos en mi problema particular, mediante validación cruzada. Sin una implementación vectorizada, mi código de descenso de gradiente en línea es mucho más lento que el de descenso de gradiente por lotes. Eso aumenta notablemente el tiempo que lleva completar el proceso de validación cruzada.

EDITAR : Incluyo aquí el pseudocódigo de mi implementación de descenso de gradiente en línea, según lo solicitado por ffriend. Estoy resolviendo un problema de regresión.

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] "Aprendizaje en línea a gran escala", L. Bottou, Y. Le Cunn, NIPS 2003.

Pablo Suau
fuente
2
Divida el conjunto de datos en mini lotes y ajuste el modelo a cada mini lote secuencialmente.
amigo
Gracias @ amigo. Sin embargo, eso no sería una implementación pura en línea.
Pablo Suau
1
¿Cuál es la razón para usar la implementación "puramente en línea" si su conjunto de datos es fijo? SGD solo dice que no necesita iterar todo el conjunto de datos a la vez, sino que puede dividirlo en un número arbitrario de piezas (mini lotes) y procesarlos uno por uno. El mini lote de tamaño 1 solo tiene sentido cuando tiene una fuente de datos continua y posiblemente interminable (como el feed de Twitter, por ejemplo) y desea actualizar el modelo después de cada nueva observación. Pero ese es un caso muy raro y definitivamente no es para conjuntos de datos fijos.
amigo
Disculpas por mi respuesta tardía. Por favor, revise el texto que agregué a la pregunta original.
Pablo Suau
1
¿Puedes mostrar tu implementación? Veo malentendidos, pero sin código de muestra será difícil explicarlo.
amigo

Respuestas:

10

En primer lugar, la palabra "muestra" se usa normalmente para describir un subconjunto de población , por lo que me referiré a lo mismo que "ejemplo".

Su implementación de SGD es lenta debido a esta línea:

for each training example i:

Aquí utiliza explícitamente exactamente un ejemplo para cada actualización de los parámetros del modelo. Por definición, la vectorización es una técnica para convertir operaciones en un elemento en operaciones en un vector de tales elementos. Por lo tanto, no, no puede procesar ejemplos uno por uno y seguir utilizando la vectorización.

Sin embargo, puede aproximarse al SGD verdadero utilizando mini lotes . Mini-lote es un pequeño subconjunto del conjunto de datos original (por ejemplo, 100 ejemplos). Calcula las actualizaciones de parámetros y errores en base a mini lotes, pero aún itera sobre muchos de ellos sin optimización global, lo que hace que el proceso sea estocástico. Entonces, para que su implementación sea mucho más rápida, es suficiente cambiar la línea anterior a:

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

y calcular el error del lote, no de un solo ejemplo.

Aunque es bastante obvio, también debería mencionar la vectorización en el nivel por ejemplo. Es decir, en lugar de algo como esto:

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

definitivamente deberías hacer algo como esto:

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

que, de nuevo, es fácil de generalizar para mini lotes:

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)
amigo
fuente
1
Creo que este es el camino a seguir. Los mini lotes con un tamaño bien elegido pueden converger realmente más rápido que la versión por lotes o en línea (el primero solo actualiza los pesos una vez por conjunto completo, y el segundo no se puede vectorizar, además tiene pasos de actualización de peso adicionales con más frecuencia)
Neil Slater
Gracias a los dos. Disculpas por rechazar obstinadamente mini lotes antes, pero no estaba seguro de las implicaciones de este método en la tasa de convergencia. Neil, ¿tu afirmación proviene de tu propia experiencia, o hay resultados teóricos / empíricos publicados?
Pablo Suau
1
@PabloSuau Puede consultar la clase de aprendizaje automático de Andrew Ng en Coursera, semana 10, explica por qué la convergencia puede ser más rápida que SGD y GD por lotes. Para ser más precisos: siempre debe ser tan rápido como SGD, pero a veces debería ser aún más rápido en la práctica.
gaborous
1

Echa un vistazo al método partial_fit del clasificador SGD de scikit . Usted tiene control sobre lo que llama con él: puede hacerlo aprendizaje en línea "verdadero" pasando una instancia a la vez, o puede agrupar instancias en mini lotes si todos sus datos están disponibles en una matriz. Si lo son, puede cortar la matriz para proporcionar los minibatches.

Ben Allison
fuente