Comment créer un algorithme simple de gradient de descente

Question

J'étudie des algorithmes simples d'apprentissage automatique, en commençant par une simple descente de dégradé, mais j'ai quelques difficultés à l'implémenter en python.

Voici l'exemple que je suis en train de reproduire, j'ai données sur les maisons avec le (salon (en feet2), et le nombre de chambres à coucher) avec le prix qui en résulte:

Surface habitable (feet2): 2104

#bedrooms: 3

Prix (1000 $ s): 400

Je suis en train de faire une régression simple en utilisant la méthode de descente de gradient, mais mon algorithme ne fonctionnera pas. .. La forme de l'algorithme n'est pas usi ng vecteurs exprès (j'essaie de comprendre étape par étape).

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 

Je comprends les mathématiques, je construire une fonction de prédiction $$h_{\theta}(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2$$ http://mathurl.com/hoy7ege.png avec $x_1$ http://mathurl.com/2ga69bb.png et $x_2$ http://mathurl.com/2cbdldp.png étant variables (surface habitable, nombre de chambres) et $h_{\theta}(x)$ http://mathurl.com/jckw8ke.png le prix estimé.

J'utilise la fonction de coût ($hserror$ http://mathurl.com/guuqjv5.png) (pour un point): $$hserror = \frac{1}{2} (h_{\theta}(x) - y)^2$$ http://mathurl.com/hnrqtkf.png Ce problème est d'habitude, mais je suis plus d'un ingénieur logiciel et j'apprends un pas à la fois, puis vous me dites ce qui ne va pas?

Je l'ai travailler avec ce code:

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) 

qui finit avec des réponses comme celle-ci:

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

Le premier numéro est que l'exécution de ce avec un seul morceau de données que vous donne un sous-déterminé système ... cela signifie qu'il peut avoir un nombre infini de solutions. Avec trois variables, vous vous attendez à avoir au moins 3 points de données, de préférence beaucoup plus élevé. Deuxièmement, l'utilisation de la descente de gradient où la taille de pas est une version réduite du gradient n'est pas garantie pour converger sauf dans un petit voisinage de la solution. Vous pouvez corriger cela en passant soit à un pas de taille fixe dans la direction du gradient négatif (lent) ou à une recherche linéaire dans le sens du dégradé négatif (plus rapide, mais légèrement plus compliqué)

de

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

Pour ce faire,

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

Il semble aussi que vous pouvez avoir une erreur de signe dans vos démarches.

Je ne suis pas sûr que derror soit un bon critère d'arrêt. (Mais les critères d'arrêt sont notoirement difficiles à obtenir "correct")

Mon dernier point est que la descente de gradient est terriblement lente pour le réglage des paramètres. Vous voulez probablement utiliser des méthodes conjuguées-gradient ou Levenberg-Marquadt à la place.Je suspecte que ces deux méthodes existent déjà pour python dans les paquets numpy ou scipy (qui ne font pas partie de python par défaut mais qui sont assez faciles à installer)