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

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

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

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

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

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

Answer 4

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

Answer 5

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

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

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

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

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

#!/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

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