Алгоритм градиентного спуска не сходится

Question

Я пытаюсь написать немного кода для алгоритма градиентного спуска, описанного в лекции Стэнфордского машинного обучения ( лекция 2 около 25:00 ).Ниже приведена реализация, которую я использовал вначале, и я думаю, что она правильно скопирована с лекции, но она не сходится, когда я добавляю большие числа (>8) к обучающему набору.

Яввод числа X, и point (X,X) добавляется к обучающему набору, поэтому на данный момент я только пытаюсь заставить его сходиться к y=ax+b, где a=1=theta\[1\] и b=0=theta\[0\].Обучающий набор - это массив x и y, где (x[i],y[i]) - это точка.

void train()
{
    double delta;
    for (int i = 0; i < x.size(); i++)
    {
        delta = y[i]-hypothesis(x[i]);
        theta[1] += alpha*delta*x[i];
        theta[0] += alpha*delta*1;
    }
}

void C_Approx::display()
{
    std::cout<<theta[1]<<"x + "<<theta[0]<<" \t "<<"f(x)="<<hypothesis(1)<<std::endl;
}

некоторые результаты, которые я получаю: я ввожу число, оно запускается train()несколько раз, затем display()

1
0.33616x + 0.33616   f(x)=0.67232
1
0.482408x + 0.482408     f(x)=0.964816
1
0.499381x + 0.499381     f(x)=0.998762
1
0.499993x + 0.499993     f(x)=0.999986
1
0.5x + 0.5   f(x)=1

Пример того, как оно расходится после того, как прошло 8:

1
0.33616x + 0.33616   f(x)=0.67232
2
0.705508x + 0.509914     f(x)=1.21542
3
0.850024x + 0.449928     f(x)=1.29995
4
0.936062x + 0.330346     f(x)=1.26641
5
0.951346x + 0.231295     f(x)=1.18264
6
0.992876x + 0.137739     f(x)=1.13062
7
0.932206x + 0.127372     f(x)=1.05958
8
1.00077x + 0.000493063   f(x)=1.00126
9
-0.689325x + -0.0714712      f(x)=-0.760797
10
4.10321e+08x + 4.365e+07     f(x)=4.53971e+08
11
1.79968e+22x + 1.61125e+21   f(x)=1.9608e+22
12
-3.9452e+41x + -3.26957e+40      f(x)=-4.27216e+41

Я попробовал предложенное решение здесь масштабирования шага и в итоге с похожими результатами.Что я делаю не так?

Answer 1

Ваша реализация хороша.Обычно стохастический градиентный спуск может расходиться, когда α слишком велик.Что вы бы сделали с большим набором данных, это возьмите случайную выборку разумного размера, найдите α, который дает вам лучшие результаты, а затем используйте его для остальных.

Answer 2

Я столкнулся с той же проблемой (хотя и в Java), потому что моя скорость обучения была слишком большой.
Короче говоря, я использовал α = 0.001, и мне пришлось подтолкнуть его к 0.000001, чтобы увидеть фактическую конвергенцию.

Конечно, эти значения связаны с вашим набором данных.

Answer 3

используйте поиск по обратной линии для гарантии конвергенции. Это очень просто реализовать. См. Стивена Бойда, выпуклая оптимизация для справки. Вы можете выбрать некоторые стандартные значения альфа, бета для поиска линии возврата, например 0,3 и 0,8.

Answer 4

Когда ваша функция стоимости увеличивается или циклически увеличивается или уменьшается, у вас обычно слишком большое значение для alpha.Что alpha вы используете?

Начните с alpha = 0.001 и посмотрите, сходится ли это?Если нет, попробуйте различные alphas (0.003, 0.01, 0.03, 0.1, 0.3, 1) и найдите тот, который быстро сходится.

Масштабирование данных (нормализация) не поможет вам только с одной функцией (ваш theta[1]), поскольку нормализация относится только к 2+ функций (многомерная линейная регрессия).

Также имейте в виду, что для небольшого числа функций вы можете использовать Нормальное уравнение, чтобы получить правильный ответ.

Answer 5

Не понятно из вашего описания, какую проблему вы решаете.Также очень опасно размещать ссылки на внешние ресурсы - вы можете быть заблокированы в stackoverflow.

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

ps Сообщество машинного обучения не заинтересовано в «условии сходимости» и «сходимости к чему-либо» - оно заинтересовано в создании «чего-то», которое проходит перекрестную проверку с хорошим результатом.

Если вам интересна оптимизация - начните искать выпуклую оптимизацию.К сожалению, на ней трудно найти работу, но она добавляет четкое представление о том, что происходит в различных вещах по математической оптимизации.

Вот исходный код, демонстрирующий это для простой квадратичной задачи:

#!/usr/bin/env python
# Gradiend descend method (without stepping) is not converged for convex         
# objective

alpha = 0.1

#k = 10.0 # jumping around minimum
k = 20.0   # diverge
#k = 0.001  # algorithm converged but gap to the optimal is big

def f(x): return k*x*x
def g(x): return 2*k*x

x0 = 12
xNext = x0
i = 0
threshold = 0.01

while True:
    i += 1
    xNext = xNext + alpha*(-1)*(g(xNext))
    obj = (xNext)
    print "Iteration: %i, Iterate: %f, Objective: %f, Optimality Gap: %f" % (i, xNext, obj, obj - f(0.0))

    if (abs(g(xNext)) < threshold):
        break
    if i > 50:
        break

print "\nYou launched application with x0=%f,threshold=%f" % (x0, threshold)

Answer 6

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