Cómo crear un algoritmo de gradiente de gradiente simple

Question

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

Aquí es el ejemplo que estoy tratando de reproducir, tengo datos sobre las casas con el (sala de estar (en pies2), y el número de dormitorios) con el precio resultante:

zona de estar (feet2): 2104

#bedrooms: 3

Precio (1000): $ s 400

que estoy tratando de hacer una regresión simple utilizando el método de descenso de gradiente, pero mi algoritmo no funcionará. .. La forma del algoritmo no es usi ng 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 

que entender 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 y $h_{\theta}(x)$ http://mathurl.com/jckw8ke.png el precio estimado (de área, número de dormitorios que viven).

estoy usando la función de coste ($hserror$ http://mathurl.com/guuqjv5.png) (por un punto): $$hserror = \frac{1}{2} (h_{\theta}(x) - y)^2$$ http://mathurl.com/hnrqtkf.png Este es un problema habitual, pero yo soy más de un ingeniero de software y estoy aprendiendo un paso a la vez, puedo tu me dices que esta mal?

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

primera cuestión es que la ejecución de este con una sola pieza de datos le da una underdetermined sistema ... 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, el uso de gradiente de pendiente donde el tamaño de paso es una versión escalada del degradado no se garantiza que 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 degradado negativo (lento) o una búsqueda de líneas en la dirección del degradado negativo (más rápido, pero un poco más complicado)

Por lo tanto, para el paso de paso fijo de

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

Para ello,

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 los criterios de detención son muy difíciles de obtener "correctos")

Mi punto final es que el descenso del gradiente es terriblemente lento para la instalación de parámetros. Probablemente desee usar métodos de gradiente conjugado o de Levenberg-Marquadt.Sospecho que estos dos 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)