Artikkelen diskuterer flere måter å bestemme den matematiske ligningen for en enkel (paret) regresjonslinje.
Alle metoder for å løse ligningen diskutert her er basert på minste kvadraters metode. La oss betegne metodene som følger:
- Analytisk løsning
- Gradient Nedstigning
- Stokastisk gradientnedstigning
For hver metode for å løse ligningen til en rett linje, gir artikkelen forskjellige funksjoner, som hovedsakelig er delt inn i de som er skrevet uten å bruke biblioteket nusset og de som brukes til beregninger nusset. Det antas at dyktig bruk nusset vil redusere datakostnadene.
All kode gitt i artikkelen er skrevet på språket python 2.7 med Jupyter Notebook. Kildekoden og filen med eksempeldata er lagt ut på
Artikkelen er mer rettet mot både nybegynnere og de som allerede så smått har begynt å mestre studiet av et veldig bredt avsnitt innen kunstig intelligens – maskinlæring.
For å illustrere materialet bruker vi et veldig enkelt eksempel.
Eksempelforhold
Vi har fem verdier som kjennetegner avhengighet Y fra X (Tabell nr. 1):
Tabell nr. 1 "Eksempelforhold"
Vi vil anta at verdiene er måneden i året, og — inntekt denne måneden. Med andre ord avhenger inntektene av måneden i året, og - det eneste tegnet som inntektene avhenger av.
Eksemplet er så som så, både fra synspunktet om den betingede avhengigheten av inntekter på måneden i året, og fra synspunktet om antall verdier - det er svært få av dem. Imidlertid vil en slik forenkling gjøre det mulig, som de sier, å forklare, ikke alltid med letthet, materialet som nybegynnere assimilerer. Og også tallenes enkelhet vil tillate de som ønsker å løse eksemplet på papir uten betydelige arbeidskostnader.
La oss anta at avhengigheten gitt i eksemplet kan tilnærmes ganske godt ved den matematiske ligningen av en enkel (paret) regresjonslinje av formen:
der er måneden inntekten ble mottatt, – inntekt tilsvarende måneden, и er regresjonskoeffisienten til den estimerte linjen.
Merk at koeffisienten ofte kalt skråningen eller gradienten til den estimerte linjen; representerer beløpet som når det endres .
Det er klart at vår oppgave i eksemplet er å velge slike koeffisienter i ligningen и , der avvikene til våre beregnede inntektsverdier per måned fra de sanne svarene, dvs. verdier presentert i prøven vil være minimale.
Minste kvadratiske metode
I henhold til minste kvadraters metode skal avviket beregnes ved å kvadrere det. Denne teknikken lar deg unngå gjensidig kansellering av avvik hvis de har motsatte fortegn. For eksempel, hvis i ett tilfelle er avviket +5 (pluss fem), og i den andre -5 (minus fem), da vil summen av avvikene oppheve hverandre og utgjøre 0 (null). Det er mulig å ikke kvadrere avviket, men å bruke egenskapen til modulen og da vil alle avvikene være positive og akkumulere. Vi vil ikke dvele på dette punktet i detalj, men ganske enkelt indikere at det er vanlig å kvadrere avviket for å gjøre beregningene lettere.
Slik ser formelen ut som vi skal bestemme minste sum av kvadrerte avvik (feil):
der er en funksjon av tilnærming av sanne svar (det vil si inntektene vi beregnet),
er de sanne svarene (inntekt gitt i prøven),
er prøveindeksen (nummeret på måneden hvor avviket er bestemt)
La oss differensiere funksjonen, definere de partielle differensialligningene, og være klare til å gå videre til den analytiske løsningen. Men først, la oss ta en kort ekskursjon om hva differensiering er og huske den geometriske betydningen av derivatet.
Differensiering
Differensiering er operasjonen for å finne den deriverte av en funksjon.
Hva brukes derivatet til? Den deriverte av en funksjon karakteriserer endringshastigheten til funksjonen og forteller oss dens retning. Hvis den deriverte på et gitt punkt er positiv, øker funksjonen, ellers synker funksjonen. Og jo større verdien av den absolutte deriverte er, desto høyere er endringshastigheten til funksjonsverdiene, så vel som jo brattere helningen til funksjonsgrafen.
For eksempel, under betingelsene for et kartesisk koordinatsystem, er verdien av den deriverte i punktet M(0,0) lik + 25 betyr at på et gitt punkt, når verdien er forskjøvet til høyre av en konvensjonell enhet, verdi øker med 25 konvensjonelle enheter. På grafen ser det ut som en ganske bratt verdistigning fra et gitt punkt.
Et annet eksempel. Den deriverte verdien er lik -0,1 betyr at når fortrengt per en konvensjonell enhet, verdi reduseres med bare 0,1 konvensjonell enhet. Samtidig, på grafen til funksjonen, kan vi observere en knapt merkbar nedoverbakke. Når vi tegner en analogi med et fjell, er det som om vi sakte går ned en slak skråning fra et fjell, i motsetning til det forrige eksemplet, hvor vi måtte bestige veldig bratte topper :)
Dermed etter å differensiere funksjonen etter odds и , definerer vi 1. ordens partielle differensialligninger. Etter å ha bestemt likningene, vil vi motta et system med to likninger, ved å løse disse vil vi kunne velge slike verdier av koeffisientene и , for hvilke verdiene til de tilsvarende derivatene på gitte punkter endres med en veldig, veldig liten mengde, og i tilfelle av en analytisk løsning ikke endres i det hele tatt. Med andre ord vil feilfunksjonen ved de funnet koeffisientene nå et minimum, siden verdiene til de partielle derivatene på disse punktene vil være lik null.
Så, i henhold til reglene for differensiering, den partielle deriverte ligningen av 1. orden med hensyn til koeffisienten vil ta formen:
1. ordens partiell deriverte ligning mht vil ta formen:
Som et resultat mottok vi et ligningssystem som har en ganske enkel analytisk løsning:
begynne{ligning*}
begynne{cases}
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
slutt{cases}
slutt{ligning*}
Før vi løser ligningen, la oss forhåndslaste, sjekke at lastingen er riktig og formatere dataene.
Laster og formaterer data
Det skal bemerkes at på grunn av det faktum at for den analytiske løsningen, og deretter for gradient og stokastisk gradientnedstigning, vil vi bruke koden i to varianter: ved å bruke biblioteket nusset og uten å bruke det, vil vi trenge passende dataformatering (se kode).
Datainnlasting og behandlingskode
# импортируем все нужные нам библиотеки
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 '********************************************'Visualisering
Nå, etter at vi for det første har lastet inn dataene, for det andre kontrollert at innlastingen er riktig og til slutt formatert dataene, vil vi utføre den første visualiseringen. Metoden som ofte brukes for dette er parplott bibliotek sjøfødt. I vårt eksempel, på grunn av det begrensede antallet, er det ingen vits i å bruke biblioteket sjøfødt. Vi vil bruke det vanlige biblioteket Matplotlib og bare se på scatterplotten.
Scatterplot-kode
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()Figur nr. 1 «Inntektsavhengighet av måneden i året»
Analytisk løsning
La oss bruke de vanligste verktøyene i python og løse ligningssystemet:
begynne{ligning*}
begynne{cases}
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
slutt{cases}
slutt{ligning*}
I følge Cramers regel vi finner den generelle determinanten, samt determinanter ved og av , hvoretter å dele determinanten med til den generelle determinanten - finn koeffisienten , på samme måte finner vi koeffisienten .
Analytisk løsningskode
# определим функцию для расчета коэффициентов 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)Her er hva vi fikk:
Så, verdiene til koeffisientene er funnet, summen av kvadrerte avvik er etablert. La oss tegne en rett linje på spredningshistogrammet i samsvar med de funnet koeffisientene.
Regresjonslinjekode
# определим функцию для формирования массива рассчетных значений выручки
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()Figur nr. 2 «Riktige og beregnede svar»
Du kan se på avviksgrafen for hver måned. I vårt tilfelle vil vi ikke utlede noen vesentlig praktisk verdi av det, men vi vil tilfredsstille vår nysgjerrighet på hvor godt den enkle lineære regresjonsligningen karakteriserer inntektens avhengighet av måneden i året.
Avvikskartkode
# определим функцию для формирования массива отклонений в процентах
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()Diagram nr. 3 "Avvik, %"
Ikke perfekt, men vi fullførte oppgaven vår.
La oss skrive en funksjon som bestemmer koeffisientene и bruker biblioteket nusset, mer presist vil vi skrive to funksjoner: den ene bruker en pseudoinvers matrise (anbefales ikke i praksis, siden prosessen er beregningsmessig kompleks og ustabil), den andre bruker en matriseligning.
Analytisk løsningskode (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_npLa oss sammenligne tiden brukt på å bestemme koeffisientene и , i samsvar med de 3 presenterte metodene.
Kode for beregning av beregningstid
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)
Med en liten mengde data kommer en "selvskrevet" funksjon ut foran, som finner koeffisientene ved hjelp av Cramers metode.
Nå kan du gå videre til andre måter å finne koeffisienter på и .
Gradient Nedstigning
Først, la oss definere hva en gradient er. Enkelt sagt er gradienten et segment som indikerer retningen for maksimal vekst av en funksjon. I analogi med å bestige et fjell, hvor gradienten er der den bratteste stigningen til toppen av fjellet er. Når vi utvikler eksemplet med fjellet, husker vi at vi faktisk trenger den bratteste nedstigningen for å nå lavlandet så raskt som mulig, det vil si minimum - stedet der funksjonen ikke øker eller reduseres. På dette tidspunktet vil den deriverte være lik null. Derfor trenger vi ikke en gradient, men en antigradient. For å finne antigradienten trenger du bare å multiplisere gradienten med -1 (minus én).
La oss ta hensyn til det faktum at en funksjon kan ha flere minima, og etter å ha gått ned i en av dem ved å bruke algoritmen foreslått nedenfor, vil vi ikke kunne finne et annet minimum, som kan være lavere enn det som ble funnet. La oss slappe av, dette er ikke en trussel for oss! I vårt tilfelle har vi å gjøre med et enkelt minimum, siden vår funksjon på grafen er en vanlig parabel. Og som vi alle burde vite veldig godt fra skolematematikkkurset vårt, har en parabel bare ett minimum.
Etter at vi fant ut hvorfor vi trengte en gradient, og også at gradienten er et segment, det vil si en vektor med gitte koordinater, som er nøyaktig de samme koeffisientene и vi kan implementere gradientnedstigning.
Før du starter, foreslår jeg at du bare leser noen få setninger om nedstigningsalgoritmen:
- Vi bestemmer på en pseudo-tilfeldig måte koordinatene til koeffisientene и . I vårt eksempel vil vi definere koeffisienter nær null. Dette er en vanlig praksis, men hver sak kan ha sin egen praksis.
- Fra koordinat trekke fra verdien av 1. ordens partielle deriverte ved punktet . Så hvis den deriverte er positiv, øker funksjonen. Derfor, ved å trekke fra verdien av den deriverte, vil vi bevege oss i motsatt retning av vekst, det vil si i retning av nedstigning. Hvis den deriverte er negativ, så avtar funksjonen på dette punktet og ved å trekke fra verdien av den deriverte beveger vi oss i nedstigningsretningen.
- Vi gjennomfører en lignende operasjon med koordinaten : trekk fra verdien av den partielle deriverte ved punktet .
- For ikke å hoppe over minimumet og fly inn i det dype rommet, er det nødvendig å stille inn trinnstørrelsen i nedstigningsretningen. Generelt kan du skrive en hel artikkel om hvordan du setter trinnet riktig og hvordan du endrer det under nedstigningsprosessen for å redusere beregningskostnadene. Men nå har vi en litt annen oppgave foran oss, og vi vil etablere trinnstørrelsen ved hjelp av den vitenskapelige metoden "poke" eller, som de sier i vanlig språkbruk, empirisk.
- Når vi er fra de gitte koordinatene и trekke fra verdiene til de deriverte, får vi nye koordinater и . Vi tar neste trinn (subtraksjon), allerede fra de beregnede koordinatene. Og slik starter syklusen igjen og igjen, til den nødvendige konvergensen er oppnådd.
Alle! Nå er vi klare til å gå på leting etter den dypeste kløften i Marianergraven. La oss komme i gang.
Kode for gradientnedstigning
# напишем функцию градиентного спуска без использования библиотеки 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
Vi dykket helt til bunnen av Marianergraven og der fant vi alle de samme koeffisientverdiene и , som er akkurat det som var å forvente.
La oss ta et nytt dykk, bare denne gangen vil vårt dyphavsfartøy fylles med andre teknologier, nemlig et bibliotek nusset.
Kode for gradientnedstigning (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
Koeffisientverdier и uforanderlig.
La oss se på hvordan feilen endret seg under gradientnedstigning, det vil si hvordan summen av kvadrerte avvik endret seg med hvert trinn.
Kode for plotting av summer av kvadrerte avvik
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()Graf nr. 4 "Summen av kvadrerte avvik under gradientnedstigning"
På grafen ser vi at for hvert trinn avtar feilen, og etter et visst antall iterasjoner observerer vi en nesten horisontal linje.
Til slutt, la oss anslå forskjellen i kodeutførelsestid:
Kode for å bestemme tid for beregning av gradientnedstigning
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)
Kanskje vi gjør noe galt, men igjen er det en enkel "hjemmeskrevet" funksjon som ikke bruker biblioteket nusset overgår beregningstiden til en funksjon ved bruk av biblioteket nusset.
Men vi står ikke stille, men går mot å studere en annen spennende måte å løse den enkle lineære regresjonsligningen på. Møt oss!
Stokastisk gradientnedstigning
For raskt å forstå prinsippet om drift av stokastisk gradientnedstigning, er det bedre å bestemme forskjellene fra vanlig gradientnedstigning. Vi, i tilfelle av gradient nedstigning, i ligningene av derivater av и brukte summene av verdiene til alle funksjoner og sanne svar tilgjengelig i prøven (det vil si summene av alle и ). I stokastisk gradientnedstigning vil vi ikke bruke alle verdiene som er tilstede i prøven, men i stedet velge pseudo-tilfeldig den såkalte prøveindeksen og bruke verdiene.
For eksempel, hvis indeksen er bestemt til å være nummer 3 (tre), så tar vi verdiene и , så erstatter vi verdiene i de deriverte ligningene og bestemmer nye koordinater. Etter å ha bestemt koordinatene, bestemmer vi igjen pseudo-tilfeldig prøveindeksen, erstatter verdiene som tilsvarer indeksen i partielle differensialligninger og bestemmer koordinatene på en ny måte и etc. til konvergensen blir grønn. Ved første øyekast virker det kanskje ikke som om dette kan fungere i det hele tatt, men det gjør det. Det er sant at det er verdt å merke seg at feilen ikke avtar for hvert trinn, men det er absolutt en tendens.
Hva er fordelene med stokastisk gradientnedstigning fremfor konvensjonell? Hvis prøvestørrelsen vår er veldig stor og målt i titusenvis av verdier, er det mye lettere å behandle, for eksempel, et tilfeldig tusen av dem, i stedet for hele utvalget. Det er her stokastisk gradientnedstigning kommer inn i bildet. I vårt tilfelle vil vi selvfølgelig ikke merke stor forskjell.
La oss se på koden.
Kode for stokastisk gradientnedstigning
# определим функцию стох.град.шага
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])
Vi ser nøye på koeffisientene og tar oss selv i å stille spørsmålet "Hvordan kan dette være?" Vi har andre koeffisientverdier и . Kanskje stokastisk gradientnedstigning har funnet mer optimale parametere for ligningen? Dessverre ikke. Det er nok å se på summen av kvadrerte avvik og se at med nye verdier av koeffisientene er feilen større. Vi har ikke hastverk med å fortvile. La oss bygge en graf over feilendringen.
Kode for å plotte summen av kvadrerte avvik i stokastisk gradientnedstigning
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()Graf nr. 5 "Summen av kvadrerte avvik under stokastisk gradientnedstigning"
Ser vi på timeplanen faller alt på plass og nå skal vi fikse alt.
Så hva skjedde? Følgende skjedde. Når vi tilfeldig velger en måned, er det for den valgte måneden algoritmen vår prøver å redusere feilen i beregningen av inntekter. Så velger vi en annen måned og gjentar beregningen, men vi reduserer feilen for den andre valgte måneden. Husk nå at de to første månedene avviker betydelig fra linjen til den enkle lineære regresjonsligningen. Dette betyr at når noen av disse to månedene velges, ved å redusere feilen for hver av dem, øker algoritmen vår alvorlig feilen for hele utvalget. Så, hva gjør vi? Svaret er enkelt: du må redusere nedstigningstrinnet. Tross alt, ved å redusere nedstigningstrinnet, vil feilen også slutte å "hoppe" opp og ned. Eller rettere sagt, "hopping"-feilen vil ikke stoppe, men den vil ikke gjøre det så raskt :) La oss sjekke.
Kode for å kjøre SGD med mindre intervaller
# запустим функцию, уменьшив шаг в 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()
Graf nr. 6 "Summen av kvadrerte avvik under stokastisk gradientnedstigning (80 tusen trinn)"
Koeffisientene har blitt bedre, men er fortsatt ikke ideelle. Hypotetisk kan dette korrigeres på denne måten. Vi velger for eksempel i de siste 1000 iterasjonene verdiene til koeffisientene som minimumsfeilen ble gjort med. Sant nok, for dette må vi også skrive ned verdiene til koeffisientene selv. Vi vil ikke gjøre dette, men heller ta hensyn til timeplanen. Det ser jevnt ut og feilen ser ut til å avta jevnt. Dette er faktisk ikke sant. La oss se på de første 1000 iterasjonene og sammenligne dem med de siste.
Kode for SGD-diagram (første 1000 trinn)
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()Graf nr. 7 "Summen av kvadrerte avvik SGD (første 1000 trinn)"
Graf nr. 8 "Summen av kvadrerte avvik SGD (siste 1000 trinn)"
Helt i begynnelsen av nedstigningen observerer vi en ganske jevn og bratt nedgang i feilen. I de siste iterasjonene ser vi at feilen går rundt og rundt verdien på 1,475 og i enkelte øyeblikk tilsvarer denne optimale verdien, men så går den fortsatt opp... Jeg gjentar, du kan skrive ned verdiene til koeffisienter и , og velg deretter de der feilen er minimal. Imidlertid hadde vi et mer alvorlig problem: vi måtte ta 80 tusen skritt (se kode) for å få verdier nær optimale. Og dette motsier allerede ideen om å spare beregningstid med stokastisk gradientnedstigning i forhold til gradientnedstigning. Hva kan korrigeres og forbedres? Det er ikke vanskelig å legge merke til at i de første iterasjonene går vi trygt ned, og derfor bør vi legge igjen et stort trinn i de første iterasjonene og redusere trinnet etter hvert som vi går fremover. Vi vil ikke gjøre dette i denne artikkelen - den er allerede for lang. De som ønsker kan tenke selv hvordan de skal gjøre dette, det er ikke vanskelig :)
La oss nå utføre stokastisk gradientnedstigning ved å bruke biblioteket nusset (og la oss ikke snuble over steinene som vi identifiserte tidligere)
Kode for Stokastisk Gradient Descent (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
Verdiene viste seg å være nesten de samme som når de gikk ned uten bruk nusset. Dette er imidlertid logisk.
La oss finne ut hvor lang tid stokastiske gradientnedstigninger tok oss.
Kode for å bestemme SGD-beregningstid (80 tusen trinn)
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)
Jo lenger inn i skogen, jo mørkere er skyene: igjen viser den "selvskrevne" formelen det beste resultatet. Alt dette tyder på at det må finnes enda mer subtile måter å bruke biblioteket på nusset, som virkelig setter fart på beregningsoperasjoner. I denne artikkelen vil vi ikke lære om dem. Det vil være noe å tenke på på fritiden :)
Vi oppsummerer
Før jeg oppsummerer, vil jeg gjerne svare på et spørsmål som mest sannsynlig dukket opp fra vår kjære leser. Hvorfor, faktisk, slik "tortur" med nedstigninger, hvorfor trenger vi å gå opp og ned fjellet (for det meste ned) for å finne det dyrebare lavlandet, hvis vi har i våre hender en så kraftig og enkel enhet, i form for en analytisk løsning, som umiddelbart teleporterer oss til rett sted?
Svaret på dette spørsmålet ligger på overflaten. Nå har vi sett på et veldig enkelt eksempel, der det sanne svaret er avhenger av ett tegn . Du ser ikke dette ofte i livet, så la oss forestille oss at vi har 2, 30, 50 eller flere tegn. La oss legge til tusenvis, eller til og med titusenvis av verdier for hvert attributt. I dette tilfellet kan det hende at den analytiske løsningen ikke tåler testen og mislykkes. I sin tur vil gradientnedstigning og dens variasjoner sakte men sikkert bringe oss nærmere målet - funksjonens minimum. Og ikke bekymre deg for hastighet - vi vil sannsynligvis se på måter som vil tillate oss å stille inn og regulere trinnlengden (det vil si hastighet).
Og nå den faktiske korte oppsummeringen.
For det første håper jeg at materialet som presenteres i artikkelen vil hjelpe begynnende "dataforskere" med å forstå hvordan man løser enkle (og ikke bare) lineære regresjonsligninger.
For det andre så vi på flere måter å løse ligningen på. Nå kan vi, avhengig av situasjonen, velge den som er best egnet til å løse problemet.
For det tredje så vi kraften i tilleggsinnstillinger, nemlig trinnlengden for gradientnedstigning. Denne parameteren kan ikke neglisjeres. Som nevnt ovenfor, for å redusere kostnadene ved beregninger, bør trinnlengden endres under nedstigningen.
For det fjerde, i vårt tilfelle, viste "hjemmeskrevne" funksjoner de beste tidsresultatene for beregninger. Dette skyldes sannsynligvis ikke den mest profesjonelle bruken av bibliotekets muligheter nusset. Men uansett, den følgende konklusjonen tyder på seg selv. På den ene siden er det noen ganger verdt å stille spørsmål ved etablerte meninger, og på den annen side er det ikke alltid verdt å komplisere alt - tvert imot, noen ganger er en enklere måte å løse et problem på mer effektiv. Og siden målet vårt var å analysere tre tilnærminger til å løse en enkel lineær regresjonsligning, var bruken av "selvskrevne" funksjoner ganske nok for oss.
Litteratur (eller noe sånt)
1. Lineær regresjon
2. Minste kvadraters metode
3. Derivat
4. gradient
5. Gradientnedstigning
6. NumPy-bibliotek
Kilde: www.habr.com