Как создать простой алгоритм градиентного спуска

Question

Я изучаю простые алгоритмы машинного обучения, начиная с простого градиентного спуска, но у меня возникли некоторые проблемы при попытке реализовать его на python.

Вот пример, который я пытаюсь воспроизвести, у меня есть данные о домах (жилая площадь (в футах2) и количество спален) с итоговой ценой:

Жилая площадь (футы 2): 2104

# спальни: 3

Цена (1000 $ с): 400

Я пытаюсь сделать простую регрессию с использованием градиентного спускаметод, но мой алгоритм не будет работать ... Форма алгоритма не использует векторы специально (я пытаюсь понять это шаг за шагом).

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

Я понимаю математику, я строю функцию прогнозирования $$ h _ {\ theta} (x) = \ theta_0 + \ theta_1 x_1 + \ theta_2 x_2 $$ http://mathurl.com/hoy7ege.pngгде $ x_1 $ http://mathurl.com/2ga69bb.png и $ x_2 $ http://mathurl.com/2cbdldp.png являются переменными (жилая площадь, количество спален) и $ h _ {\ theta} (x) $ http://mathurl.com/jckw8ke.png по оценкамцена.

Я использую функцию стоимости ( $ hserror $ http://mathurl.com/guuqjv5.png) (за одну точку): $$ hserror = \ frac {1} {2} (h _ {\theta} (x) - y) ^ 2 $$ http://mathurl.com/hnrqtkf.png Это обычная проблема, но я больше программист и изучаю один шаг за раз, вы можете сказать мне, что не так?

Я понял, что работает с этим кодом:

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)

, который заканчивается такими ответами:

 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

Первая проблема заключается в том, что выполнение этого только с одним фрагментом данных дает вам недостаточно определенную систему ... это означает, что у нее может быть бесконечное количество решений. С тремя переменными вы ожидаете иметь как минимум 3 точки данных, предпочтительно намного выше.

Во-вторых, использование градиентного спуска, когда размер шага является масштабированной версией градиента, не обязательно сходится, за исключением небольшой окрестности решения. Это можно исправить, переключившись либо на шаг фиксированного размера в направлении отрицательного градиента (медленно), либо на поиск линии в направлении отрицательного градиента (быстрее, но немного сложнее)

То есть для фиксированного размера шага вместо

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

Вы делаете это

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

Похоже, что в ваших шагах может быть ошибка знака.

Я также не уверен, что деррор является хорошим критерием остановки. (Но критерии остановки, как известно, трудно получить «правильно»)

Мое последнее замечание - градиентный спуск ужасно медленный для подбора параметров. Вы, вероятно, хотите вместо этого использовать методы сопряженного градиента или Левенберга-Марквадта. Я подозреваю, что оба эти метода уже существуют для python в пакетах numpy или scipy (которые по умолчанию не являются частью python, но довольно просты в установке)