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)