programación - ejercicios python avanzados

Cómo crear un algoritmo simple de Gradient Descent

Question

Estoy estudiando algoritmos simples de aprendizaje automático, comenzando con un simple descenso de degradado, pero tengo problemas para tratar de implementarlo en Python.

Este es el ejemplo que estoy tratando de reproducir, tengo datos sobre casas con el (área de vida (en pies2) y el número de habitaciones) con el precio resultante:

Superficie habitable (pies2): 2104

#bedrooms: 3

Precio (1000 $ s): 400

Intento hacer una regresión simple usando el método de descenso de gradiente, pero mi algoritmo no funcionará ... La forma del algoritmo no usa vectores a propósito (estoy tratando de entenderlo paso a paso).

i = 1
import sys
derror=sys.maxint
error = 0
step = 0.0001
dthresh = 0.1
import random
theta1 = random.random()
theta2 = random.random()
theta0 = random.random()
while derror>dthresh:
diff = 400 - theta0 - 2104 * theta1 - 3 * theta2
theta0 = theta0 + step * diff * 1
theta1 = theta1 + step * diff * 2104
theta2 = theta2 + step * diff * 3
hserror = diff**2/2
derror = abs(error - hserror)
error = hserror
print ''iteration : %d, error : %s'' % (i, error)
i+=1

Entiendo las matemáticas, estoy construyendo una función de predicción $$ h _ {/ theta} (x) = / theta_0 + / theta_1 x_1 + / theta_2 x_2 $$ http://mathurl.com/hoy7ege.png con $ x_1 $ http://mathurl.com/2ga69bb.png y $ x_2 $ http://mathurl.com/2cbdldp.png siendo las variables (área de vida, número de habitaciones) y $ h _ {/ theta} (x) $ http: //mathurl.com/jckw8ke.png el precio estimado.

Estoy usando la función de costo ( $ hserror $ http://mathurl.com/guuqjv5.png ) (para un punto): $$ hserror = / frac {1} {2} (h _ {/ theta} (x) - y) ^ 2 $$ http://mathurl.com/hnrqtkf.png Este es un problema habitual, pero soy más un ingeniero de software y estoy aprendiendo un paso a la vez, ¿puedes decirme qué pasa? ?

Lo tengo trabajando con este código:

data = {(2104, 3) : 400, (1600,3) : 330, (2400, 3) : 369, (1416, 2) : 232, (3000, 4) : 540}
for x in range(10):
i = 1
import sys
derror=sys.maxint
error = 0
step = 0.00000001
dthresh = 0.0000000001
import random
theta1 = random.random()*100
theta2 = random.random()*100
theta0 = random.random()*100
while derror>dthresh:
diff = 400 - (theta0 + 2104 * theta1 + 3 * theta2)
theta0 = theta0 + step * diff * 1
theta1 = theta1 + step * diff * 2104
theta2 = theta2 + step * diff * 3
hserror = diff**2/2
derror = abs(error - hserror)
error = hserror
#print ''iteration : %d, error : %s, derror : %s'' % (i, error, derror)
i+=1
print '' theta0 : %f, theta1 : %f, theta2 : %f'' % (theta0, theta1, theta2)
print '' done : %f'' %(theta0 + 2104 * theta1 + 3*theta2)

que termina con respuestas como esta:

 theta0 : 48.412337, theta1 : 0.094492, theta2 : 50.925579
done : 400.000043
theta0 : 0.574007, theta1 : 0.185363, theta2 : 3.140553
done : 400.000042
theta0 : 28.588457, theta1 : 0.041746, theta2 : 94.525769
done : 400.000043
theta0 : 42.240593, theta1 : 0.096398, theta2 : 51.645989
done : 400.000043
theta0 : 98.452431, theta1 : 0.136432, theta2 : 4.831866
done : 400.000043
theta0 : 18.022160, theta1 : 0.148059, theta2 : 23.487524
done : 400.000043
theta0 : 39.461977, theta1 : 0.097899, theta2 : 51.519412
done : 400.000042
theta0 : 40.979868, theta1 : 0.040312, theta2 : 91.401406
done : 400.000043
theta0 : 15.466259, theta1 : 0.111276, theta2 : 50.136221
done : 400.000043
theta0 : 72.380926, theta1 : 0.013814, theta2 : 99.517853
done : 400.000043

Answer 1

El primer problema es que ejecutar esto con solo una parte de datos le da un sistema indeterminado ... esto significa que puede tener un número infinito de soluciones. Con tres variables, esperaría tener al menos 3 puntos de datos, preferiblemente mucho más altos.

En segundo lugar, no se garantiza que el descenso de gradiente en el que el tamaño del paso sea una versión escalada del gradiente converja, excepto en un vecindario pequeño de la solución. Puede solucionarlo cambiando a un paso de tamaño fijo en la dirección del gradiente negativo (lento) o una búsqueda de líneas en la dirección del gradiente negativo (más rápido, pero un poco más complicado)

Por lo tanto, para el tamaño de paso fijo en lugar de

theta0 = theta0 - step * dEdtheta0
theta1 = theta1 - step * dEdtheta1
theta2 = theta2 - step * dEdtheta2

Tu hiciste esto

n = max( [ dEdtheta1, dEdtheta1, dEdtheta2 ] )
theta0 = theta0 - step * dEdtheta0 / n
theta1 = theta1 - step * dEdtheta1 / n
theta2 = theta2 - step * dEdtheta2 / n

También parece que puede tener un error de signo en sus pasos.

Tampoco estoy seguro de que derror sea un buen criterio para detenerse. (Pero detener los criterios es notoriamente difícil de "corregir")

Mi punto final es que el descenso del gradiente es terriblemente lento para el ajuste de los parámetros. Probablemente desee usar métodos de gradiente conjugado o de Levenberg-Marquadt. Sospecho que ambos métodos ya existen para Python en los paquetes numpy o scipy (que no son parte de Python por defecto, pero son bastante fáciles de instalar)