🥇Қарапайым сызықтық регрессия теңдеуін шешу

Мақалада қарапайым (жұпталған) регрессия сызығының математикалық теңдеуін анықтаудың бірнеше жолы қарастырылады.

Мұнда қарастырылатын теңдеуді шешудің барлық әдістері ең кіші квадраттар әдісіне негізделген. Әдістерді келесідей белгілейік:

Аналитикалық шешім
Градиенттің төмендеуі
Стохастикалық градиенттің түсуі

Түзу теңдеуін шешудің әрбір әдісі үшін мақалада әртүрлі функциялар қарастырылған, олар негізінен кітапхананы пайдаланбай жазылғандарға бөлінеді. сансыз және есептеулер үшін пайдаланатындар сансыз. Бұл шебер пайдалану деп саналады сансыз есептеу шығындарын азайтады.

Мақалада келтірілген барлық код тілде жазылған питон 2.7 қолдану арқылы Jupyter Notebook. Бастапқы код және үлгі деректері бар файл орналастырылған Github

Мақала жаңадан бастағандарға да, жасанды интеллекттегі өте кең бөлімді - машиналық оқытуды біртіндеп меңгере бастағандарға да бағытталған.

Материалды көрсету үшін біз өте қарапайым мысалды қолданамыз.

Мысал шарттары

Бізде тәуелділікті сипаттайтын бес құндылық бар Y от X (№1 кесте):

№1 кесте «Мысалы шарттар»

құндылықтар деп есептейміз жыл айы болып табылады, және — осы айдағы табыс. Басқаша айтқанда, табыс жылдың айына байланысты және - кіріс тәуелді болатын жалғыз белгі.

Мысал осылайша, кірістің жылдың айына шартты тәуелділігі тұрғысынан да, құндылықтар саны тұрғысынан да - олардың саны өте аз. Дегенмен, мұндай жеңілдету, олар айтқандай, жаңадан бастағандар игеретін материалды әрдайым оңай емес түсіндіруге мүмкіндік береді. Сондай-ақ сандардың қарапайымдылығы қағаздағы мысалды айтарлықтай еңбек шығындарынсыз шешуге мүмкіндік береді.

Мысалда келтірілген тәуелділікті форманың қарапайым (жұпталған) регрессия сызығының математикалық теңдеуі арқылы өте жақсы жуықтауға болады деп есептейік:

қайда табыс алынған ай, - айға сәйкес келетін кіріс; и есептелген сызықтың регрессия коэффициенттері болып табылады.

коэффициент екенін ескеріңіз жиі есептік сызықтың еңісі немесе градиенті деп аталады; сомасын көрсетеді өзгерген кезде .

Мысалдағы біздің міндетіміз теңдеудегі осындай коэффициенттерді таңдау екені анық и , бұл кезде біздің есептелген кіріс мәндерінің айлар бойынша нақты жауаптардан ауытқуы, яғни. үлгіде ұсынылған мәндер минималды болады.

Ең кіші квадрат әдісі

Ең кіші квадраттар әдісі бойынша ауытқуды квадраттау арқылы есептеу керек. Бұл әдіс қарама-қарсы белгілер болса, ауытқулардың өзара жойылуын болдырмауға мүмкіндік береді. Мысалы, егер бір жағдайда ауытқу болса +5 (плюс бес), ал екіншісінде -5 (минус бес), онда ауытқулардың қосындысы бірін-бірі жоққа шығарады және 0 (нөл) құрайды. Ауытқуды квадраттауға болмайды, бірақ модульдің қасиетін қолдануға болады, сонда барлық ауытқулар оң болады және жинақталады. Біз бұл мәселеге егжей-тегжейлі тоқталмаймыз, тек есептеулерге ыңғайлы болу үшін ауытқуды квадраттау әдеттегідей екенін көрсетеміз.

Квадраттық ауытқулардың (қателердің) ең аз сомасын анықтайтын формула осылай көрінеді:

қайда шынайы жауаптардың жуықтау функциясы (яғни біз есептеген кіріс),

дұрыс жауаптар (үлгіде берілген кіріс),

іріктеу көрсеткіші болып табылады (ауытқу анықталған айдың саны)

Функцияны дифференциалдап, дербес дифференциалдық теңдеулерді анықтап, аналитикалық шешімге көшуге дайын болайық. Бірақ алдымен дифференциацияның не екеніне қысқаша экскурсия жасап, туындының геометриялық мағынасын еске түсірейік.

Дифференциация

Дифференциалдау – функцияның туындысын табу операциясы.

Туынды не үшін қолданылады? Функцияның туындысы функцияның өзгеру жылдамдығын сипаттайды және оның бағытын айтады. Егер берілген нүктедегі туынды оң болса, онда функция өседі, әйтпесе функция кемиді. Ал абсолютті туындының мәні неғұрлым үлкен болса, функция мәндерінің өзгеру жылдамдығы соғұрлым жоғары болады, сонымен қатар функция графигінің еңісі соғұрлым тік болады.

Мысалы, декарттық координаталар жүйесінің жағдайында М(0,0) нүктесіндегі туындының мәні мынаған тең. + 25 берілген нүктеде мән ауысқанда дегенді білдіреді шартты бірлік, мән бойынша оңға қарай 25 шартты бірлікке артады. Графикте бұл мәндердің айтарлықтай күрт өсуі сияқты көрінеді берілген нүктеден.

Тағы бір мысал. Туынды мән тең -0,1 ығысқанда дегенді білдіреді бір шартты бірлікке, мәнге 0,1 шартты бірлікке ғана төмендейді. Сонымен қатар, функцияның графигінде біз әрең байқалатын төмен еңісті байқаймыз. Тауға ұқсастық жасай отырып, біз өте тік шыңдарға шығуға тура келген алдыңғы мысалға қарағанда, таудан жұмсақ еңіспен өте баяу түсіп бара жатқандай боламыз :)

Осылайша, функцияны дифференциалданғаннан кейін коэффициенттер бойынша и , 1-ші ретті дербес дифференциалдық теңдеулерді анықтаймыз. Теңдеулерді анықтағаннан кейін біз екі теңдеу жүйесін аламыз, оны шешу арқылы біз коэффициенттердің осындай мәндерін таңдай аламыз. и , онда берілген нүктелердегі сәйкес туындылардың мәндері өте, өте аз мөлшерге өзгереді, ал аналитикалық шешім жағдайында мүлдем өзгермейді. Басқаша айтқанда, табылған коэффициенттердегі қателік функциясы минимумға жетеді, өйткені бұл нүктелердегі ішінара туындылардың мәндері нөлге тең болады.

Сонымен, дифференциалдау ережелеріне сәйкес коэффициентке қатысты 1-ші ретті дербес туынды теңдеу нысанда болады:

қатысты 1-ші ретті дербес туынды теңдеу нысанда болады:

Нәтижесінде біз өте қарапайым аналитикалық шешімі бар теңдеулер жүйесін алдық:

бастау{теңдеу*}
бастау{жағдайлар}
na + bsumlimits_{i=1}^nx_i — sumlimits_{i=1}^ny_i = 0

sumlimits_{i=1}^nx_i(a +bsumlimits_{i=1}^nx_i — sumlimits_{i=1}^ny_i) = 0
соңы{жағдайлар}
соңы{теңдеу*}

Теңдеуді шешпес бұрын, алдын ала жүктеп алайық, жүктеудің дұрыстығын тексеріп, деректерді пішімдейміз.

Деректерді жүктеу және пішімдеу

Айта кету керек, аналитикалық шешім үшін, содан кейін градиент және стохастикалық градиент түсіру үшін біз кодты екі нұсқада қолданамыз: кітапхананы пайдалану сансыз және оны қолданбай, бізге сәйкес деректерді пішімдеу қажет болады (кодты қараңыз).

Мәліметтерді жүктеу және өңдеу коды

# импортируем все нужные нам библиотеки
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import math
import pylab as pl
import random

# графики отобразим в Jupyter
%matplotlib inline

# укажем размер графиков
from pylab import rcParams
rcParams['figure.figsize'] = 12, 6

# отключим предупреждения Anaconda
import warnings
warnings.simplefilter('ignore')

# загрузим значения
table_zero = pd.read_csv('data_example.txt', header=0, sep='t')

# посмотрим информацию о таблице и на саму таблицу
print table_zero.info()
print '********************************************'
print table_zero
print '********************************************'

# подготовим данные без использования NumPy

x_us = []
[x_us.append(float(i)) for i in table_zero['x']]
print x_us
print type(x_us)
print '********************************************'

y_us = []
[y_us.append(float(i)) for i in table_zero['y']]
print y_us
print type(y_us)
print '********************************************'

# подготовим данные с использованием NumPy

x_np = table_zero[['x']].values
print x_np
print type(x_np)
print x_np.shape
print '********************************************'

y_np = table_zero[['y']].values
print y_np
print type(y_np)
print y_np.shape
print '********************************************'

Көрнекілік

Енді, біріншіден, деректерді жүктегеннен кейін, екіншіден, жүктеудің дұрыстығын тексеріп, соңында деректерді пішімдегеннен кейін біз бірінші визуализацияны орындаймыз. Бұл үшін жиі қолданылатын әдіс жұптық сызба кітапханалар Теңіз. Біздің мысалда саны шектеулі болғандықтан, кітапхананы пайдаланудың мәні жоқ Теңіз. Біз кәдімгі кітапхананы пайдаланамыз matplotlib және жай ғана шашырау сызбасына қараңыз.

Шашырау коды

print 'График №1 "Зависимость выручки от месяца года"'

plt.plot(x_us,y_us,'o',color='green',markersize=16)
plt.xlabel('$Months$', size=16)
plt.ylabel('$Sales$', size=16)
plt.show()

№1 диаграмма «Кірістің жыл айына тәуелділігі»

Аналитикалық шешім

Ең көп таралған құралдарды қолданайық питон және теңдеулер жүйесін шешіңіз:

бастау{теңдеу*}
бастау{жағдайлар}
na + bsumlimits_{i=1}^nx_i — sumlimits_{i=1}^ny_i = 0

sumlimits_{i=1}^nx_i(a +bsumlimits_{i=1}^nx_i — sumlimits_{i=1}^ny_i) = 0
соңы{жағдайлар}
соңы{теңдеу*}

Крамер ережесі бойынша арқылы жалпы анықтауышты, сонымен қатар анықтауыштарды табамыз және бойынша , одан кейін анықтауышты бөлу жалпы анықтауышқа – коэффициентті табыңыз , дәл солай коэффициентті табамыз .

Аналитикалық шешім коды

# определим функцию для расчета коэффициентов a и b по правилу Крамера
def Kramer_method (x,y):
        # сумма значений (все месяца)
    sx = sum(x)
        # сумма истинных ответов (выручка за весь период)
    sy = sum(y)
        # сумма произведения значений на истинные ответы
    list_xy = []
    [list_xy.append(x[i]*y[i]) for i in range(len(x))]
    sxy = sum(list_xy)
        # сумма квадратов значений
    list_x_sq = []
    [list_x_sq.append(x[i]**2) for i in range(len(x))]
    sx_sq = sum(list_x_sq)
        # количество значений
    n = len(x)
        # общий определитель
    det = sx_sq*n - sx*sx
        # определитель по a
    det_a = sx_sq*sy - sx*sxy
        # искомый параметр a
    a = (det_a / det)
        # определитель по b
    det_b = sxy*n - sy*sx
        # искомый параметр b
    b = (det_b / det)
        # контрольные значения (прооверка)
    check1 = (n*b + a*sx - sy)
    check2 = (b*sx + a*sx_sq - sxy)
    return [round(a,4), round(b,4)]

# запустим функцию и запишем правильные ответы
ab_us = Kramer_method(x_us,y_us)
a_us = ab_us[0]
b_us = ab_us[1]
print ' 33[1m' + ' 33[4m' + "Оптимальные значения коэффициентов a и b:"  + ' 33[0m' 
print 'a =', a_us
print 'b =', b_us
print

# определим функцию для подсчета суммы квадратов ошибок
def errors_sq_Kramer_method(answers,x,y):
    list_errors_sq = []
    for i in range(len(x)):
        err = (answers[0] + answers[1]*x[i] - y[i])**2
        list_errors_sq.append(err)
    return sum(list_errors_sq)

# запустим функцию и запишем значение ошибки
error_sq = errors_sq_Kramer_method(ab_us,x_us,y_us)
print ' 33[1m' + ' 33[4m' + "Сумма квадратов отклонений" + ' 33[0m'
print error_sq
print

# замерим время расчета
# print ' 33[1m' + ' 33[4m' + "Время выполнения расчета суммы квадратов отклонений:" + ' 33[0m'
# % timeit error_sq = errors_sq_Kramer_method(ab,x_us,y_us)

Міне, бізде:

Сонымен, коэффициенттердің мәндері табылды, квадраттық ауытқулардың қосындысы белгіленді. Табылған коэффициенттерге сәйкес шашырау гистограммасына түзу жүргізейік.

Регрессия жолының коды

# определим функцию для формирования массива рассчетных значений выручки
def sales_count(ab,x,y):
    line_answers = []
    [line_answers.append(ab[0]+ab[1]*x[i]) for i in range(len(x))]
    return line_answers

# построим графики
print 'Грфик№2 "Правильные и расчетные ответы"'
plt.plot(x_us,y_us,'o',color='green',markersize=16, label = '$True$ $answers$')
plt.plot(x_us, sales_count(ab_us,x_us,y_us), color='red',lw=4,
         label='$Function: a + bx,$ $where$ $a='+str(round(ab_us[0],2))+',$ $b='+str(round(ab_us[1],2))+'$')
plt.xlabel('$Months$', size=16)
plt.ylabel('$Sales$', size=16)
plt.legend(loc=1, prop={'size': 16})
plt.show()

№2 кесте «Дұрыс және есептелген жауаптар»

Әр ай үшін ауытқу графигін қарауға болады. Біздің жағдайда біз одан ешқандай маңызды практикалық мән алмаймыз, бірақ біз қарапайым сызықтық регрессия теңдеуі кірістің жыл айына тәуелділігін қаншалықты жақсы сипаттайтыны туралы қызығушылығымызды қанағаттандырамыз.

Ауытқу диаграммасының коды

# определим функцию для формирования массива отклонений в процентах
def error_per_month(ab,x,y):
    sales_c = sales_count(ab,x,y)
    errors_percent = []
    for i in range(len(x)):
        errors_percent.append(100*(sales_c[i]-y[i])/y[i])
    return errors_percent

# построим график
print 'График№3 "Отклонения по-месячно, %"'
plt.gca().bar(x_us, error_per_month(ab_us,x_us,y_us), color='brown')
plt.xlabel('Months', size=16)
plt.ylabel('Calculation error, %', size=16)
plt.show()

№3 диаграмма «Ауытқулар, %»

Мінсіз емес, бірақ біз тапсырманы орындадық.

Коэффициенттерін анықтау үшін функцияны жазайық и кітапхананы пайдаланады сансыз, дәлірек айтсақ, біз екі функцияны жазамыз: біреуі жалған кері матрицаны (практикада ұсынылмайды, өйткені процесс есептеу тұрғысынан күрделі және тұрақсыз), екіншісі матрицалық теңдеуді пайдаланады.

Аналитикалық шешім коды (NumPy)

# для начала добавим столбец с не изменяющимся значением в 1. 
# Данный столбец нужен для того, чтобы не обрабатывать отдельно коэффицент a
vector_1 = np.ones((x_np.shape[0],1))
x_np = table_zero[['x']].values # на всякий случай приведем в первичный формат вектор x_np
x_np = np.hstack((vector_1,x_np))

# проверим то, что все сделали правильно
print vector_1[0:3]
print x_np[0:3]
print '***************************************'
print

# напишем функцию, которая определяет значения коэффициентов a и b с использованием псевдообратной матрицы
def pseudoinverse_matrix(X, y):
    # задаем явный формат матрицы признаков
    X = np.matrix(X)
    # определяем транспонированную матрицу
    XT = X.T
    # определяем квадратную матрицу
    XTX = XT*X
    # определяем псевдообратную матрицу
    inv = np.linalg.pinv(XTX)
    # задаем явный формат матрицы ответов
    y = np.matrix(y)
    # находим вектор весов
    return (inv*XT)*y

# запустим функцию
ab_np = pseudoinverse_matrix(x_np, y_np)
print ab_np
print '***************************************'
print

# напишем функцию, которая использует для решения матричное уравнение
def matrix_equation(X,y):
    a = np.dot(X.T, X)
    b = np.dot(X.T, y)
    return np.linalg.solve(a, b)

# запустим функцию
ab_np = matrix_equation(x_np,y_np)
print ab_np

Коэффициенттерді анықтауға кеткен уақытты салыстырайық и , ұсынылған 3 әдіске сәйкес.

Есептеу уақытын есептеу коды

print ' 33[1m' + ' 33[4m' + "Время выполнения расчета коэффициентов без использования библиотеки NumPy:" + ' 33[0m'
% timeit ab_us = Kramer_method(x_us,y_us)
print '***************************************'
print
print ' 33[1m' + ' 33[4m' + "Время выполнения расчета коэффициентов с использованием псевдообратной матрицы:" + ' 33[0m'
%timeit ab_np = pseudoinverse_matrix(x_np, y_np)
print '***************************************'
print
print ' 33[1m' + ' 33[4m' + "Время выполнения расчета коэффициентов с использованием матричного уравнения:" + ' 33[0m'
%timeit ab_np = matrix_equation(x_np, y_np)

Деректер саны аз болса, Крамер әдісі арқылы коэффициенттерді табатын «өздігінен жазылған» функция алға шығады.

Енді коэффициенттерді табудың басқа тәсілдеріне көшуге болады и .

Градиенттің төмендеуі

Алдымен градиенттің не екенін анықтайық. Қарапайым тілмен айтқанда, градиент – функцияның максималды өсу бағытын көрсететін сегмент. Тауға шығуға ұқсастық бойынша, градиент беттері таудың басына ең тік көтерілетін жер. Таумен мысалды дамыта отырып, біз шын мәнінде ойпатқа мүмкіндігінше тез жету үшін ең тік түсу қажет екенін, яғни минимум - функцияның артпайтын немесе азаймайтын жерін еске түсіреміз. Бұл кезде туынды нөлге тең болады. Сондықтан бізге градиент емес, антиградиент қажет. Антиградиентті табу үшін градиентті көбейту керек -1 (минус бір).

Функцияның бірнеше минимумдары болуы мүмкін екеніне назар аударайық және төменде ұсынылған алгоритмді қолдана отырып, олардың біреуіне түскеннен кейін біз басқа минимумды таба алмаймыз, ол табылғаннан төмен болуы мүмкін. Демалайық, бұл бізге қауіп төндірмейді! Біздің жағдайда біз бір минимуммен айналысамыз, өйткені біздің функциямыз графикте дұрыс парабола берілген. Біздің мектептегі математика курсынан бәріміз жақсы білуіміз керек, параболаның бір ғана минимумы бар.

Бізге градиент не үшін қажет екенін, сондай-ақ градиент сегмент екенін, яғни координаталары берілген вектор екенін анықтағаннан кейін, дәл сол коэффициенттер. и градиентті түсіруді жүзеге асыра аламыз.

Бастамас бұрын мен төмендеу алгоритмі туралы бірнеше сөйлемді оқуды ұсынамын:

Біз коэффициенттердің координаталарын жалған кездейсоқ түрде анықтаймыз и . Біздің мысалда біз нөлге жақын коэффициенттерді анықтаймыз. Бұл әдеттегі тәжірибе, бірақ әр жағдайда өз тәжірибесі болуы мүмкін.
Координатадан нүктесіндегі 1-ші ретті ішінара туындының мәнін алып тастаңыз . Демек, туынды оң болса, онда функция артады. Демек, туындының мәнін шегеру арқылы өсудің қарама-қарсы бағытына, яғни төмендеу бағытына қарай жылжимыз. Егер туынды теріс болса, онда бұл нүктедегі функция төмендейді және туындының мәнін алып тастау арқылы біз төмендеу бағытында қозғаламыз.
Біз ұқсас операцияны координатпен орындаймыз : нүктедегі ішінара туындының мәнін алып тастаңыз .
Минимумнан секіріп, терең кеңістікке ұшып кетпеу үшін қадам өлшемін түсу бағытында орнату қажет. Тұтастай алғанда, есептеу шығындарын азайту үшін қадамды қалай дұрыс орнату және оны түсіру процесінде қалай өзгерту керектігі туралы толық мақала жазуға болады. Бірақ қазір біздің алдымызда сәл басқаша міндет тұр және біз қадам өлшемін ғылыми әдіспен «пок» немесе олар айтқандай, эмпирикалық түрде белгілейміз.
Біз берілген координаталардан шыққаннан кейін и туындылардың мәндерін алып тастасақ, жаңа координаталар аламыз и . Біз есептелген координаталардан келесі қадамды (алу) жасаймыз. Осылайша цикл қажетті конвергенцияға жеткенше қайта-қайта басталады.

Барлық! Енді біз Мариана шұңқырының ең терең шатқалын іздеуге дайынбыз. Бастайық.

Градиенттің түсу коды

# напишем функцию градиентного спуска без использования библиотеки NumPy. 
# Функция на вход принимает диапазоны значений x,y, длину шага (по умолчанию=0,1), допустимую погрешность(tolerance)
def gradient_descent_usual(x_us,y_us,l=0.1,tolerance=0.000000000001):
    # сумма значений (все месяца)
    sx = sum(x_us)
    # сумма истинных ответов (выручка за весь период)
    sy = sum(y_us)
    # сумма произведения значений на истинные ответы
    list_xy = []
    [list_xy.append(x_us[i]*y_us[i]) for i in range(len(x_us))]
    sxy = sum(list_xy)
    # сумма квадратов значений
    list_x_sq = []
    [list_x_sq.append(x_us[i]**2) for i in range(len(x_us))]
    sx_sq = sum(list_x_sq)
    # количество значений
    num = len(x_us)
    # начальные значения коэффициентов, определенные псевдослучайным образом
    a = float(random.uniform(-0.5, 0.5))
    b = float(random.uniform(-0.5, 0.5))
    # создаем массив с ошибками, для старта используем значения 1 и 0
    # после завершения спуска стартовые значения удалим
    errors = [1,0]
    # запускаем цикл спуска
    # цикл работает до тех пор, пока отклонение последней ошибки суммы квадратов от предыдущей, не будет меньше tolerance
    while abs(errors[-1]-errors[-2]) > tolerance:
        a_step = a - l*(num*a + b*sx - sy)/num
        b_step = b - l*(a*sx + b*sx_sq - sxy)/num
        a = a_step
        b = b_step
        ab = [a,b]
        errors.append(errors_sq_Kramer_method(ab,x_us,y_us))
    return (ab),(errors[2:])

# запишем массив значений 
list_parametres_gradient_descence = gradient_descent_usual(x_us,y_us,l=0.1,tolerance=0.000000000001)


print ' 33[1m' + ' 33[4m' + "Значения коэффициентов a и b:" + ' 33[0m'
print 'a =', round(list_parametres_gradient_descence[0][0],3)
print 'b =', round(list_parametres_gradient_descence[0][1],3)
print


print ' 33[1m' + ' 33[4m' + "Сумма квадратов отклонений:" + ' 33[0m'
print round(list_parametres_gradient_descence[1][-1],3)
print



print ' 33[1m' + ' 33[4m' + "Количество итераций в градиентном спуске:" + ' 33[0m'
print len(list_parametres_gradient_descence[1])
print

Біз Мариана шұңқырының ең түбіне сүңгіп, сол жерден бірдей коэффициент мәндерін таптық и , бұл дәл күтуге болатын нәрсе.

Тағы бір сүңгіп көрейік, тек осы жолы біздің терең теңіз көлігіміз басқа технологиялармен, атап айтқанда кітапханамен толтырылады. сансыз.

Градиенттің түсу коды (NumPy)

# перед тем определить функцию для градиентного спуска с использованием библиотеки NumPy, 
# напишем функцию определения суммы квадратов отклонений также с использованием NumPy
def error_square_numpy(ab,x_np,y_np):
    y_pred = np.dot(x_np,ab)
    error = y_pred - y_np
    return sum((error)**2)

# напишем функцию градиентного спуска с использованием библиотеки NumPy. 
# Функция на вход принимает диапазоны значений x,y, длину шага (по умолчанию=0,1), допустимую погрешность(tolerance)
def gradient_descent_numpy(x_np,y_np,l=0.1,tolerance=0.000000000001):
    # сумма значений (все месяца)
    sx = float(sum(x_np[:,1]))
    # сумма истинных ответов (выручка за весь период)
    sy = float(sum(y_np))
    # сумма произведения значений на истинные ответы
    sxy = x_np*y_np
    sxy = float(sum(sxy[:,1]))
    # сумма квадратов значений
    sx_sq = float(sum(x_np[:,1]**2))
    # количество значений
    num = float(x_np.shape[0])
    # начальные значения коэффициентов, определенные псевдослучайным образом
    a = float(random.uniform(-0.5, 0.5))
    b = float(random.uniform(-0.5, 0.5))
    # создаем массив с ошибками, для старта используем значения 1 и 0
    # после завершения спуска стартовые значения удалим
    errors = [1,0]
    # запускаем цикл спуска
    # цикл работает до тех пор, пока отклонение последней ошибки суммы квадратов от предыдущей, не будет меньше tolerance
    while abs(errors[-1]-errors[-2]) > tolerance:
        a_step = a - l*(num*a + b*sx - sy)/num
        b_step = b - l*(a*sx + b*sx_sq - sxy)/num
        a = a_step
        b = b_step
        ab = np.array([[a],[b]])
        errors.append(error_square_numpy(ab,x_np,y_np))
    return (ab),(errors[2:])

# запишем массив значений 
list_parametres_gradient_descence = gradient_descent_numpy(x_np,y_np,l=0.1,tolerance=0.000000000001)

print ' 33[1m' + ' 33[4m' + "Значения коэффициентов a и b:" + ' 33[0m'
print 'a =', round(list_parametres_gradient_descence[0][0],3)
print 'b =', round(list_parametres_gradient_descence[0][1],3)
print


print ' 33[1m' + ' 33[4m' + "Сумма квадратов отклонений:" + ' 33[0m'
print round(list_parametres_gradient_descence[1][-1],3)
print

print ' 33[1m' + ' 33[4m' + "Количество итераций в градиентном спуске:" + ' 33[0m'
print len(list_parametres_gradient_descence[1])
print

Коэффицент мәндері и өзгермейтін.

Градиенттің түсуі кезінде қатенің қалай өзгергенін, яғни әр қадам сайын квадраттық ауытқулардың қосындысы қалай өзгергенін қарастырайық.

Квадраттық ауытқулардың қосындыларын салу коды

print 'График№4 "Сумма квадратов отклонений по-шагово"'
plt.plot(range(len(list_parametres_gradient_descence[1])), list_parametres_gradient_descence[1], color='red', lw=3)
plt.xlabel('Steps (Iteration)', size=16)
plt.ylabel('Sum of squared deviations', size=16)
plt.show()

График №4 «Градиенттің түсуі кезіндегі квадраттық ауытқулардың қосындысы»

Графикте біз әрбір қадам сайын қатенің азайғанын көреміз және белгілі бір итерациялар санынан кейін біз дерлік көлденең сызықты байқаймыз.

Соңында, кодты орындау уақытындағы айырмашылықты бағалайық:

Градиенттің түсуін есептеу уақытын анықтауға арналған код

print ' 33[1m' + ' 33[4m' + "Время выполнения градиентного спуска без использования библиотеки NumPy:" + ' 33[0m'
%timeit list_parametres_gradient_descence = gradient_descent_usual(x_us,y_us,l=0.1,tolerance=0.000000000001)
print '***************************************'
print

print ' 33[1m' + ' 33[4m' + "Время выполнения градиентного спуска с использованием библиотеки NumPy:" + ' 33[0m'
%timeit list_parametres_gradient_descence = gradient_descent_numpy(x_np,y_np,l=0.1,tolerance=0.000000000001)

Мүмкін біз бірдеңе дұрыс емес істеп жатырмыз, бірақ бұл кітапхананы пайдаланбайтын қарапайым «үйде жазылған» функция. сансыз кітапхананы пайдаланып функцияның есептеу уақытынан асып түседі сансыз.

Бірақ біз бір орында тұрған жоқпыз, бірақ қарапайым сызықтық регрессия теңдеуін шешудің тағы бір қызықты әдісін зерттеуге бет бұрып жатырмыз. Танысыңыз!

Стохастикалық градиенттің түсуі

Стохастикалық градиенттік түсірудің жұмыс істеу принципін тез түсіну үшін оның қарапайым градиенттік түсуден айырмашылығын анықтаған дұрыс. Біз, градиенттік төмендеу жағдайында, туындыларының теңдеуінде и үлгіде бар барлық мүмкіндіктер мен шынайы жауаптардың мәндерінің қосындысын пайдаланды (яғни, барлығының қосындысы и ). Стохастикалық градиентті түсіру кезінде біз үлгідегі барлық мәндерді пайдаланбаймыз, оның орнына псевдокездейсоқ таңдап алынған индекс деп аталатынды таңдап, оның мәндерін пайдаланамыз.

Мысалы, егер индекс 3 (үш) саны болып анықталса, онда біз мәндерді аламыз и , содан кейін біз мәндерді туынды теңдеулерге ауыстырамыз және жаңа координаттарды анықтаймыз. Содан кейін координаталарды анықтай отырып, біз тағы да псевдокездейсоқ таңдамалы индексті анықтаймыз, индекске сәйкес мәндерді ішінара дифференциалдық теңдеулерге ауыстырамыз және координаталарды жаңа әдіспен анықтаймыз и және т.б. конвергенция жасыл түске боялғанша. Бір қарағанда, бұл мүлдем жұмыс істемейтін сияқты көрінуі мүмкін, бірақ солай. Қателік қадам сайын азаймайтынын айта кеткен жөн, бірақ тенденция бар екені сөзсіз.

Стохастикалық градиент түсудің әдеттегіден қандай артықшылығы бар? Егер біздің іріктеме көлемі өте үлкен болса және ондаған мың мәндермен өлшенсе, онда бүкіл іріктеуден гөрі, айталық, олардың кездейсоқ мыңын өңдеу әлдеқайда оңай. Бұл жерде стохастикалық градиенттің түсуі пайда болады. Біздің жағдайда, әрине, біз көп айырмашылықты байқамаймыз.

Кодты қарастырайық.

Стохастикалық градиенттің түсу коды

# определим функцию стох.град.шага
def stoch_grad_step_usual(vector_init, x_us, ind, y_us, l):
#     выбираем значение икс, которое соответствует случайному значению параметра ind 
# (см.ф-цию stoch_grad_descent_usual)
    x = x_us[ind]
#     рассчитывыаем значение y (выручку), которая соответствует выбранному значению x
    y_pred = vector_init[0] + vector_init[1]*x_us[ind]
#     вычисляем ошибку расчетной выручки относительно представленной в выборке
    error = y_pred - y_us[ind]
#     определяем первую координату градиента ab
    grad_a = error
#     определяем вторую координату ab
    grad_b = x_us[ind]*error
#     вычисляем новый вектор коэффициентов
    vector_new = [vector_init[0]-l*grad_a, vector_init[1]-l*grad_b]
    return vector_new


# определим функцию стох.град.спуска
def stoch_grad_descent_usual(x_us, y_us, l=0.1, steps = 800):
#     для самого начала работы функции зададим начальные значения коэффициентов
    vector_init = [float(random.uniform(-0.5, 0.5)), float(random.uniform(-0.5, 0.5))]
    errors = []
#     запустим цикл спуска
# цикл расчитан на определенное количество шагов (steps)
    for i in range(steps):
        ind = random.choice(range(len(x_us)))
        new_vector = stoch_grad_step_usual(vector_init, x_us, ind, y_us, l)
        vector_init = new_vector
        errors.append(errors_sq_Kramer_method(vector_init,x_us,y_us))
    return (vector_init),(errors)


# запишем массив значений 
list_parametres_stoch_gradient_descence = stoch_grad_descent_usual(x_us, y_us, l=0.1, steps = 800)

print ' 33[1m' + ' 33[4m' + "Значения коэффициентов a и b:" + ' 33[0m'
print 'a =', round(list_parametres_stoch_gradient_descence[0][0],3)
print 'b =', round(list_parametres_stoch_gradient_descence[0][1],3)
print


print ' 33[1m' + ' 33[4m' + "Сумма квадратов отклонений:" + ' 33[0m'
print round(list_parametres_stoch_gradient_descence[1][-1],3)
print

print ' 33[1m' + ' 33[4m' + "Количество итераций в стохастическом градиентном спуске:" + ' 33[0m'
print len(list_parametres_stoch_gradient_descence[1])

Біз коэффициенттерге мұқият қарап, «Бұл қалай болуы мүмкін?» Деген сұрақты қоямыз. Басқа коэффициент мәндерін алдық и . Мүмкін стохастикалық градиенттің түсуі теңдеу үшін оңтайлы параметрлерді тапқан шығар? Өкінішке орай жоқ. Квадраттық ауытқулардың қосындысына қарап, коэффициенттердің жаңа мәндерімен қатенің үлкенірек екенін көру жеткілікті. Біз үмітсіздікке асықпаймыз. Қатені өзгерту графигін құрастырайық.

Стохастикалық градиенттік төмендеу кезінде квадраттық ауытқулардың қосындысын құру коды

print 'График №5 "Сумма квадратов отклонений по-шагово"'
plt.plot(range(len(list_parametres_stoch_gradient_descence[1])), list_parametres_stoch_gradient_descence[1], color='red', lw=2)
plt.xlabel('Steps (Iteration)', size=16)
plt.ylabel('Sum of squared deviations', size=16)
plt.show()

График №5 «Стохастикалық градиенттің түсуі кезіндегі квадраттық ауытқулар сомасы»

Кестеге қарасақ, бәрі өз орнына келеді, енді бәрін жөндейміз.

Сонымен не болды? Келесі оқиға болды. Кездейсоқ бір айды таңдаған кезде, біздің алгоритміміз кірісті есептеудегі қатені азайтуға тырысады. Содан кейін біз тағы бір айды таңдап, есептеуді қайталаймыз, бірақ біз екінші таңдалған ай үшін қатені азайтамыз. Енді алғашқы екі ай қарапайым сызықтық регрессия теңдеуінің сызығынан айтарлықтай ауытқығанын есте сақтаңыз. Бұл осы екі айдың кез келгенін таңдағанда, олардың әрқайсысының қатесін азайту арқылы біздің алгоритміміз бүкіл үлгідегі қатені айтарлықтай арттырады дегенді білдіреді. Сонымен не істеу керек? Жауап қарапайым: түсу қадамын азайту керек. Өйткені, төмендеу қадамын азайту арқылы қате жоғары және төмен «секіруді» тоқтатады. Дәлірек айтқанда, «секіру» қатесі тоқтамайды, бірақ оны тез жасамайды :) Тексерейік.

Шағын қадамдармен SGD іске қосу коды

# запустим функцию, уменьшив шаг в 100 раз и увеличив количество шагов соответсвующе 
list_parametres_stoch_gradient_descence = stoch_grad_descent_usual(x_us, y_us, l=0.001, steps = 80000)

print ' 33[1m' + ' 33[4m' + "Значения коэффициентов a и b:" + ' 33[0m'
print 'a =', round(list_parametres_stoch_gradient_descence[0][0],3)
print 'b =', round(list_parametres_stoch_gradient_descence[0][1],3)
print


print ' 33[1m' + ' 33[4m' + "Сумма квадратов отклонений:" + ' 33[0m'
print round(list_parametres_stoch_gradient_descence[1][-1],3)
print



print ' 33[1m' + ' 33[4m' + "Количество итераций в стохастическом градиентном спуске:" + ' 33[0m'
print len(list_parametres_stoch_gradient_descence[1])

print 'График №6 "Сумма квадратов отклонений по-шагово"'
plt.plot(range(len(list_parametres_stoch_gradient_descence[1])), list_parametres_stoch_gradient_descence[1], color='red', lw=2)
plt.xlabel('Steps (Iteration)', size=16)
plt.ylabel('Sum of squared deviations', size=16)
plt.show()

График №6 «Стохастикалық градиенттің түсуі кезіндегі квадраттық ауытқулар сомасы (80 мың қадам)»

Коэффиценттер жақсарды, бірақ әлі де идеалды емес. Гипотетикалық түрде, мұны осылай түзетуге болады. Біз, мысалы, соңғы 1000 итерацияда ең аз қателік жіберілген коэффициенттердің мәндерін таңдаймыз. Рас, бұл үшін біз коэффициенттердің мәндерін де жазуымыз керек. Біз мұны істемейміз, керісінше, кестеге назар аударамыз. Бұл тегіс көрінеді және қате біркелкі азаяды. Шындығында бұл дұрыс емес. Алғашқы 1000 итерацияны қарастырайық және оларды соңғысымен салыстырайық.

SGD диаграммасының коды (алғашқы 1000 қадам)

print 'График №7 "Сумма квадратов отклонений по-шагово. Первые 1000 итераций"'
plt.plot(range(len(list_parametres_stoch_gradient_descence[1][:1000])), 
         list_parametres_stoch_gradient_descence[1][:1000], color='red', lw=2)
plt.xlabel('Steps (Iteration)', size=16)
plt.ylabel('Sum of squared deviations', size=16)
plt.show()

print 'График №7 "Сумма квадратов отклонений по-шагово. Последние 1000 итераций"'
plt.plot(range(len(list_parametres_stoch_gradient_descence[1][-1000:])), 
         list_parametres_stoch_gradient_descence[1][-1000:], color='red', lw=2)
plt.xlabel('Steps (Iteration)', size=16)
plt.ylabel('Sum of squared deviations', size=16)
plt.show()

График № 7 «СGD квадраттық ауытқулар сомасы (алғашқы 1000 қадам)»

График №8 «SGD квадраттық ауытқуларының сомасы (соңғы 1000 қадам)»

Түсудің ең басында біз қателіктің айтарлықтай біркелкі және күрт төмендеуін байқаймыз. Соңғы итерацияларда қатенің 1,475 мәнін айналып өтетінін және кейбір сәттерде тіпті осы оңтайлы мәнге тең келетінін көреміз, бірақ содан кейін ол әлі де көтеріледі ... Қайталап айтамын, сіз мәндерді жаза аласыз коэффициенттер и , содан кейін қатесі аз болатындарды таңдаңыз. Дегенмен, бізде күрделі мәселе болды: оңтайлы мәндерге жақындау үшін бізге 80 мың қадам жасау керек болды (кодты қараңыз). Және бұл қазірдің өзінде градиенттің түсуіне қатысты стохастикалық градиенттің түсуімен есептеу уақытын үнемдеу идеясына қайшы келеді. Нені түзетуге және жақсартуға болады? Бірінші итерацияларда біз сенімді түрде төмендеп жатқанымызды байқау қиын емес, сондықтан бірінші итерацияларда үлкен қадам қалдырып, алға қарай қадамды азайту керек. Біз бұл мақалада мұны жасамаймыз - бұл тым ұзақ. Қалағандар мұны қалай жасау керектігін өздері ойлап алады, бұл қиын емес :)

Енді кітапхананы пайдаланып стохастикалық градиентті түсіруді орындайық сансыз (және біз бұрын анықтаған тастардан сүрінбейік)

Стохастикалық градиенттің түсу коды (NumPy)

# для начала напишем функцию градиентного шага
def stoch_grad_step_numpy(vector_init, X, ind, y, l):
    x = X[ind]
    y_pred = np.dot(x,vector_init)
    err = y_pred - y[ind]
    grad_a = err
    grad_b = x[1]*err
    return vector_init - l*np.array([grad_a, grad_b])

# определим функцию стохастического градиентного спуска
def stoch_grad_descent_numpy(X, y, l=0.1, steps = 800):
    vector_init = np.array([[np.random.randint(X.shape[0])], [np.random.randint(X.shape[0])]])
    errors = []
    for i in range(steps):
        ind = np.random.randint(X.shape[0])
        new_vector = stoch_grad_step_numpy(vector_init, X, ind, y, l)
        vector_init = new_vector
        errors.append(error_square_numpy(vector_init,X,y))
    return (vector_init), (errors)

# запишем массив значений 
list_parametres_stoch_gradient_descence = stoch_grad_descent_numpy(x_np, y_np, l=0.001, steps = 80000)

print ' 33[1m' + ' 33[4m' + "Значения коэффициентов a и b:" + ' 33[0m'
print 'a =', round(list_parametres_stoch_gradient_descence[0][0],3)
print 'b =', round(list_parametres_stoch_gradient_descence[0][1],3)
print


print ' 33[1m' + ' 33[4m' + "Сумма квадратов отклонений:" + ' 33[0m'
print round(list_parametres_stoch_gradient_descence[1][-1],3)
print



print ' 33[1m' + ' 33[4m' + "Количество итераций в стохастическом градиентном спуске:" + ' 33[0m'
print len(list_parametres_stoch_gradient_descence[1])
print

Мәндер қолданбай төмендеу кезіндегідей болды сансыз. Дегенмен, бұл логикалық.

Стохастикалық градиенттің түсуі қанша уақытқа созылғанын білейік.

SGD есептеу уақытын анықтау коды (80 мың қадам)

print ' 33[1m' + ' 33[4m' +
"Время выполнения стохастического градиентного спуска без использования библиотеки NumPy:"
+ ' 33[0m'
%timeit list_parametres_stoch_gradient_descence = stoch_grad_descent_usual(x_us, y_us, l=0.001, steps = 80000)
print '***************************************'
print

print ' 33[1m' + ' 33[4m' +
"Время выполнения стохастического градиентного спуска с использованием библиотеки NumPy:"
+ ' 33[0m'
%timeit list_parametres_stoch_gradient_descence = stoch_grad_descent_numpy(x_np, y_np, l=0.001, steps = 80000)

Орманға неғұрлым ұзағырақ болса, бұлттар соғұрлым қараңғы болады: тағы да «өзін-өзі жазған» формула ең жақсы нәтижені көрсетеді. Мұның бәрі кітапхананы пайдаланудың бұдан да нәзік жолдары болуы керек екенін көрсетеді сансыз, бұл есептеу операцияларын шынымен жылдамдатады. Бұл мақалада біз олар туралы білмейміз. Бос уақытыңызда ойланатын нәрсе болады :)

Қорытындылайық

Қорытындыламас бұрын, құрметті оқырманымыздан туындаған сұраққа жауап бергім келеді. Неліктен, шын мәнінде, мұндай «азаптау» төмен қарай, неліктен біздің қолымызда осындай қуатты және қарапайым құрылғы болса, қазыналы ойпатты табу үшін таудан (негізінен төмен) жоғары және төмен жүру керек. Бізді бірден дұрыс жерге апаратын аналитикалық шешімнің түрі?

Бұл сұрақтың жауабы бетінде жатыр. Енді біз өте қарапайым мысалды қарастырдық, онда дұрыс жауап бар бір белгіге байланысты . Сіз мұны өмірде жиі кездестіре бермейсіз, сондықтан бізде 2, 30, 50 немесе одан да көп белгілер бар деп елестетейік. Осыған әр атрибут үшін мыңдаған, тіпті он мыңдаған мәндерді қосайық. Бұл жағдайда аналитикалық шешім сынаққа төтеп бермеуі және сәтсіздікке ұшырауы мүмкін. Өз кезегінде, градиенттің төмендеуі және оның вариациялары баяу, бірақ сөзсіз бізді мақсатқа - функцияның минимумына жақындатады. Жылдамдық туралы алаңдамаңыз - біз қадам ұзындығын (яғни жылдамдықты) орнатуға және реттеуге мүмкіндік беретін жолдарды қарастыратын шығармыз.

Ал енді нақты қысқаша қорытынды.

Біріншіден, мақалада ұсынылған материал қарапайым (тек қана емес) сызықтық регрессия теңдеулерін шешу жолын түсінуде «деректер ғалымдарына» көмектеседі деп үміттенемін.

Екіншіден, теңдеуді шешудің бірнеше жолдарын қарастырдық. Енді жағдайға байланысты мәселені шешу үшін ең қолайлысын таңдай аламыз.

Үшіншіден, біз қосымша параметрлердің күшін, атап айтқанда градиенттің түсу қадамының ұзындығын көрдік. Бұл параметрді елемеуге болмайды. Жоғарыда атап өтілгендей, есептеулердің құнын төмендету үшін түсу кезінде қадам ұзындығын өзгерту керек.

Төртіншіден, біздің жағдайда «үйде жазылған» функциялар есептеулер үшін ең жақсы уақыт нәтижелерін көрсетті. Бұл кітапхананың мүмкіндіктерін кәсіби түрде пайдаланбауынан болса керек сансыз. Қалай болғанда да, келесі қорытынды өзін көрсетеді. Бір жағынан, кейде қалыптасқан пікірлерге күмән келтіруге тұрарлық, ал екінші жағынан, әрқашан бәрін қиындатудың қажеті жоқ - керісінше, кейде мәселені шешудің қарапайым әдісі тиімдірек. Біздің мақсатымыз қарапайым сызықтық регрессия теңдеуін шешудің үш тәсілін талдау болғандықтан, біз үшін «өздігінен жазылған» функцияларды пайдалану жеткілікті болды.