Что определяет, сходится ли мой алгоритм спуска градиента Python?

Question

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

Данные, которые я использую, приведены ниже. sales - зависимая переменная (в долларах) и temp - независимая переменная (градусы Цельсия) (думаю, продажи мороженого по сравнению с температурой или что-то подобное).

sales temp 
215  14.20 
325  16.40 
185  11.90 
332  15.20 
406  18.50 
522  22.10 
412  19.40 
614  25.10 
544  23.40 
421  18.10 
445  22.60 
408  17.20 

И это мои данные после того, как она была нормализована:

sales  temp 
0.06993007 0.174242424 
0.326340326 0.340909091 
0   0 
0.342657343 0.25 
0.515151515 0.5 
0.785547786 0.772727273 
0.529137529 0.568181818 
1   1 
0.836829837 0.871212121 
0.55011655 0.46969697 
0.606060606 0.810606061 
0.51981352 0.401515152 

Мой код для алгоритма:

import numpy as np 
import pandas as pd 
from scipy import stats 

class SLRegression(object): 
    def __init__(self, learnrate = .01, tolerance = .000000001, max_iter = 10000): 

     # Initialize learnrate, tolerance, and max_iter. 
     self.learnrate = learnrate 
     self.tolerance = tolerance 
     self.max_iter = max_iter 

    # Define the gradient descent algorithm. 
    def fit(self, data): 
     # data : array-like, shape = [m_observations, 2_columns] 

     # Initialize local variables. 
     converged = False 
     m = data.shape[0] 

     # Track number of iterations. 
     self.iter_ = 0 

     # Initialize theta0 and theta1. 
     self.theta0_ = 0 
     self.theta1_ = 0 

     # Compute the cost function. 
     J = (1.0/(2.0*m)) * sum([(self.theta0_ + self.theta1_*data[i][1] - data[i][0])**2 for i in range(m)]) 
     print('J is: ', J) 

     # Iterate over each point in data and update theta0 and theta1 on each pass. 
     while not converged: 
      diftemp0 = (1.0/m) * sum([(self.theta0_ + self.theta1_*data[i][1] - data[i][0]) for i in range(m)]) 
      diftemp1 = (1.0/m) * sum([(self.theta0_ + self.theta1_*data[i][1] - data[i][0]) * data[i][1] for i in range(m)]) 

      # Subtract the learnrate * partial derivative from theta0 and theta1. 
      temp0 = self.theta0_ - (self.learnrate * diftemp0) 
      temp1 = self.theta1_ - (self.learnrate * diftemp1) 

      # Update theta0 and theta1. 
      self.theta0_ = temp0 
      self.theta1_ = temp1 

      # Compute the updated cost function, given new theta0 and theta1. 
      new_J = (1.0/(2.0*m)) * sum([(self.theta0_ + self.theta1_*data[i][1] - data[i][0])**2 for i in range(m)]) 
      print('New J is: %s') % (new_J) 

      # Test for convergence. 
      if abs(J - new_J) <= self.tolerance: 
       converged = True 
       print('Model converged after %s iterations!') % (self.iter_) 

      # Set old cost equal to new cost and update iter. 
      J = new_J 
      self.iter_ += 1 

      # Test whether we have hit max_iter. 
      if self.iter_ == self.max_iter: 
       converged = True 
       print('Maximum iterations have been reached!') 

     return self 

    def point_forecast(self, x): 
     # Given feature value x, returns the regression's predicted value for y. 
     return self.theta0_ + self.theta1_ * x 


# Run the algorithm on a data set. 
if __name__ == '__main__': 
    # Load in the .csv file. 
    data = np.squeeze(np.array(pd.read_csv('sales_normalized.csv'))) 

    # Create a regression model with the default learning rate, tolerance, and maximum number of iterations. 
    slregression = SLRegression() 

    # Call the fit function and pass in the data. 
    slregression.fit(data) 

    # Print out the results. 
    print('After %s iterations, the model converged on Theta0 = %s and Theta1 = %s.') % (slregression.iter_, slregression.theta0_, slregression.theta1_) 
    # Compare our model to scipy linregress model. 
    slope, intercept, r_value, p_value, slope_std_error = stats.linregress(data[:,1], data[:,0]) 
    print('Scipy linear regression gives intercept: %s and slope = %s.') % (intercept, slope) 

    # Test the model with a point forecast. 
    print('As an example, our algorithm gives y = %s given x = .87.') % (slregression.point_forecast(.87)) # Should be about .83. 
    print('The true y-value for x = .87 is about .8368.') 

У меня возникли проблемы с пониманием, что именно позволяет алгоритму сходятся по отношению к возвращаемым значениям, которые являются полностью неправильными. Учитывая learnrate = .01, tolerance = .0000000001 и max_iter = 10000, в сочетании с нормализованными данными я могу получить алгоритм спуска градиента для схождения. Однако, когда я использую ненормированные данные, самым маленьким я могу сделать скорость обучения без возврата алгоритма NaN - .005. Это приводит к изменению функции затрат от итерации до итерации примерно до 614, но я не могу заставить ее идти ниже.

Определенно ли это требование, чтобы алгоритм такого типа имел нормализованные данные, и если да, то почему? Кроме того, что было бы лучшим способом взять роман x-value в ненормированной форме и подключить его к прогнозу точки, учитывая, что алгоритм нуждается в нормализованных значениях? Например, если я собираюсь доставить этот алгоритм клиенту, чтобы они могли делать прогнозы своих собственных (я не, но ради аргумента ..), не хочу ли я, чтобы они просто могли подключаться в ненормированном x-value?

В целом, играя с tolerance, max_iter, и learnrate дает мне не-конвергентные результаты большую часть времени. Это нормально, или есть ли недостатки в моем алгоритме, которые способствуют этой проблеме?

Answer 1

Данные learnrate = .01, tolerance = .0000000001 и max_iter = 10000, в сочетании с нормализованными данными, я могу получить алгоритм спуска градиента, чтобы сходиться. Однако, когда я использую не-нормированный данные, наименьший я могу сделать скорость обучения без алгоритма возвращения NaN является .005

Это отчасти можно ожидать, как у вас есть ваш алгоритм настройки.

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

Определенно ли это требование, чтобы алгоритм такого типа имел нормализованные данные, и если да, то почему?

Нет, абсолютно нет, но если вы не нормализуетесь, вы должны выбрать стартовую точку более разумно (вы начинаете с (m, b) = (0,0)). Ваш уровень обучения также может быть слишком мал, если вы не нормализуете свои данные, и то же самое с вашим допуском.

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

Примените любое преобразование, которое вы применили к исходным данным, чтобы получить нормализованные данные в новое значение x. (Код нормализации не соответствует тому, что вы показали). Если эта контрольная точка попала в диапазон (minx, maxx) ваших исходных данных, после преобразования она должна упасть до 0 < = x < = 1. Как только у вас есть эта нормализованная контрольная точка, подключите ее к вашему уравнению theta линии (помните, что ваши теты - m, b формы y-перехвата уравнения линии).

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

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

Если это просто не сходящиеся, прежде чем она попадает на максимум итераций, которые могли бы быть несколько вопросов:

• Ваш размер шага слишком мал,
• Ваша терпимость слишком мал,
• Ваш макс итерации слишком малы,
• вашей точка плохо выбрана

В вашем случае, используя ноны нормализованных данных приводит к тому, что ваша стартовая точка (0,0) очень далека ((m, b) ненормированных данных находится вокруг (-159, 30), а (m, b) ваших нормализованных данных (0.10 , 0.79)), поэтому большинство, если не все ваши итерации, используются только для получения интересующей области.

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

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

Возможно, вам будет полезно хранить историю тэта-пар по всему алгоритму, а затем нарисовать их. Вы сможете сразу увидеть разницу между использованием нормализованных и ненормированных входных данных.