Линейная регрессия плохой градиентный спуск производительности

Question

Я реализовал простой пример линейной регрессии (единственный вариант на данный момент) на C++, чтобы помочь мне разобраться в концепциях. Я почти уверен, что ключевой алгоритм прав, но мое исполнение ужасно.

Это метод, который фактически выполняет градиентный спуск:

void LinearRegression::BatchGradientDescent(std::vector<std::pair<int,int>> & data,float& theta1,float& theta2) 
{ 

    float weight = (1.0f/static_cast<float>(data.size())); 
    float theta1Res = 0.0f; 
    float theta2Res = 0.0f; 

    for(auto p: data) 
    { 

     float cost = Hypothesis(p.first,theta1,theta2) - p.second; 
     theta1Res += cost; 
     theta2Res += cost*p.first; 
    } 

    theta1 = theta1 - (m_LearningRate*weight* theta1Res); 
    theta2 = theta2 - (m_LearningRate*weight* theta2Res); 
} 

С другими ключевыми функциями, заданных как:

float LinearRegression::Hypothesis(float x,float theta1,float theta2) const 
{ 
    return theta1 + x*theta2; 
} 


float LinearRegression::CostFunction(std::vector<std::pair<int,int>> & data, 
            float theta1, 
            float theta2) const 
{ 
    float error = 0.0f; 
    for(auto p: data) 
    { 

     float prediction = (Hypothesis(p.first,theta1,theta2) - p.second) ; 
     error += prediction*prediction; 
    } 

    error *= 1.0f/(data.size()*2.0f); 
    return error; 
} 

void LinearRegression::Regress(std::vector<std::pair<int,int>> & data) 
{ 
    for(unsigned int itr = 0; itr < MAX_ITERATIONS; ++itr) 
    { 
     BatchGradientDescent(data,m_Theta1,m_Theta2); 
     //Some visualisation code 
    } 
} 

Теперь вопрос заключается в том, что, если скорость обучения больше, чем вокруг 0,000001 значение функции стоимости после градиентный спуск выше, чем до. То есть, алгоритм работает обратным образом. Линия образуется в прямую линию через начало довольно быстро, но затем принимает миллионов итераций, чтобы фактически достичь хорошо подходящей линии.

При скорости обучения 0,01, после шести итераций выход: (где разница в том, costAfter-costBefore)

Cost before 102901.945312, cost after 517539430400.000000, difference 517539332096.000000 
Cost before 517539430400.000000, cost after 3131945127824588800.000000, difference 3131944578068774912.000000 
Cost before 3131945127824588800.000000, cost after 18953312418560698826620928.000000, difference 18953308959796185006080000.000000 
Cost before 18953312418560698826620928.000000, cost after 114697949347691988409089177681920.000000, difference 114697930004878874575022382383104.000000 
Cost before 114697949347691988409089177681920.000000, cost after inf, difference inf 
Cost before inf, cost after inf, difference nan 

В этом примере thetas установлены равными нулю, скорость обучения на 0,000001, и есть 8 000 000 итераций! Код визуализации обновляет график только после каждых 100 000 итераций.

Функция, которая создает точки данных:

static void SetupRegressionData(std::vector<std::pair<int,int>> & data) 
{ 
    srand (time(NULL)); 

    for(int x = 50; x < 750; x += 3) 
    { 
     data.push_back(std::pair<int,int>(x+(rand() % 100), 400 + (rand() % 100))); 
    } 
} 

Короче говоря, если мой курс обучения слишком высок алгоритм градиентного спуска эффективно работает в обратном направлении и стремится к бесконечности, и если она снижается до точка, где она фактически сходится к минимуму, количество итераций, необходимых для этого, является неприемлемо высоким.

Я что-то пропустил/допустил ошибку в основном алгоритме?

Answer 1

Похоже, что все ведет себя так, как ожидалось, но у вас возникают проблемы с выбором разумной скорости обучения. Это не совсем тривиальная проблема, и существует множество подходов, начиная от заранее определенных графиков, которые постепенно уменьшают скорость обучения (см., Например, this paper), адаптивным методам, таким как AdaGrad или AdaDelta.

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