🥇 Cothromóid aischéimnithí líneach shimplí a réiteach

Pléann an t-alt bealaí éagsúla chun cothromóid mhatamaiticiúil líne aischéimniúcháin shimplí (péireáilte) a chinneadh.

Tá gach modh chun an chothromóid a phléitear anseo a réiteach bunaithe ar mhodh na gcearnóga is lú. Léirímid na modhanna mar seo a leanas:

Réiteach anailíseach
Ghinealach Grádáin
Ghinealach grádán stochastic

I gcás gach modh chun cothromóid líne dhíreach a réiteach, soláthraíonn an t-alt feidhmeanna éagsúla, atá roinnte go príomha i measc na cinn atá scríofa gan úsáid a bhaint as an leabharlann UimhPy agus iad siúd a úsáideann le haghaidh ríomhaireachtaí UimhPy. Creidtear go bhfuil úsáid sciliúil UimhPy laghdófar costais ríomhaireachta.

Tá gach cód a thugtar san alt scríofa sa teanga python-2.7 ag úsáid Leabhar Nótaí Iúpatar. Postáiltear an cód foinse agus an comhad ina bhfuil sonraí samplacha Github

Tá an t-alt dírithe níos mó ar thosaitheoirí agus orthu siúd atá tar éis tosú de réir a chéile cheana féin a mháistir ar staidéar a dhéanamh ar rannán an-leathan in hintleachta saorga - foghlaim meaisín.

Chun an t-ábhar a léiriú, úsáidimid sampla an-simplí.

Coinníollacha samplach

Tá cúig luach againn arb iad is sainairíonna iad an spleáchas Y ó X (Tábla Uimh. 1):

Tábla Uimh. 1 “Coinníollacha Samplacha”

Glacfaimid leis go bhfuil na luachanna is é mí na bliana, agus — ioncam an mhí seo. I bhfocail eile, braitheann ioncam ar mhí na bliana, agus - an t-aon chomhartha ar a mbraitheann ioncam.

Is é an sampla mar sin-mar sin, an dá ó thaobh an spleáchas coinníollach ar ioncam ar mhí na bliana, agus ó thaobh líon na luachanna - tá fíor-beag acu. Mar sin féin, beidh simpliú den sórt sin indéanta, mar a deir siad, a mhíniú, ní i gcónaí gan stró, an t-ábhar a chomhshamhlú tosaitheoirí. Agus freisin ligfidh simplíocht na n-uimhreacha dóibh siúd ar mian leo an sampla a réiteach ar pháipéar gan costais saothair shuntasacha.

Glacaimid leis gur féidir an spleáchas a thugtar sa sampla a chomhfhogasú go maith trí chothromóid mhatamaiticiúil líne aischéimniúcháin shimplí (phéireáilte) den fhoirm:

i gcás an mhí a fuarthas an t-ioncam, — ioncam a fhreagraíonn don mhí, и is comhéifeachtaí cúlchéimnithe na líne measta iad.

Tabhair faoi deara go bhfuil an chomhéifeacht go minic ar a dtugtar fána nó grádán na líne measta; is ionann é agus an méid trína ndéantar an nuair a athraíonn sé .

Ar ndóigh, is é an tasc atá againn sa sampla ná comhéifeachtaí den sórt sin a roghnú sa chothromóid и , ag a bhfuil diallais ár luachanna ioncaim ríofa de réir míosa ó na freagraí fíor, i.e. beidh na luachanna a chuirtear i láthair sa sampla íosta.

Modh cearnach ar a laghad

De réir an mhodha is lú cearnóga, ba cheart an diall a ríomh trína scaráil. Ceadaíonn an teicníocht seo duit cealú frithpháirteach diallais a sheachaint má tá comharthaí os coinne acu. Mar shampla, más rud é i gcás amháin, tá an diall +5 (móide cúig), agus sa cheann eile -5 (lúide cúig), ansin cealóidh suim na n-imeachtaí a chéile agus is ionann iad agus 0 (nialas). Is féidir gan an diall a chearnóg, ach maoin an mhodúil a úsáid agus ansin beidh na diallais go léir dearfach agus carnfaidh siad. Ní bheidh muid ag dwell ar an bpointe seo go mion, ach go simplí in iúl go bhfuil ar mhaithe le háisiúlacht na n-áireamh, tá sé de nós a cearnach ar an diall.

Seo é an chuma atá ar an bhfoirmle agus socróimid an tsuim is lú de dhialltaí cearnógacha (earráidí):

i gcás feidhm de chomhfhogasú na bhfíorfhreagraí (is é sin an t-ioncam a ríomhamar),

an bhfuil na freagraí fíor (ioncam curtha ar fáil sa sampla),

an t-innéacs samplach é (líon na míosa ina gcinntear an diall)

Déanaimis an fheidhm a dhifreáil, sainímid na cothromóidí páirteacha difreálach, agus beimid réidh le bogadh ar aghaidh go dtí an réiteach anailíseach. Ach ar dtús, déanaimis turas gairid ar cad is difreáil ann agus cuimhnigh ar bhrí gheoiméadrach an díorthaigh.

Difreáil

Is éard is difreáil ann ná oibriú chun díorthach feidhme a aimsiú.

Cad chuige a úsáidtear an díorthach? Is saintréith é díorthach feidhme ráta athraithe na feidhme agus insíonn sé dúinn a treo. Má tá an díorthach ag pointe áirithe dearfach, méadaíonn an fheidhm ar shlí eile, laghdaítear an fheidhm. Agus is mó luach an díorthach absalóideach, is airde an ráta athraithe ar na luachanna feidhme, chomh maith le fána an ghraif feidhme is géire.

Mar shampla, faoi choinníollacha córais chomhordanáidí Cartesian, tá luach an díorthaigh ag an bpointe M(0,0) cothrom le + 25 ciallaíonn sé sin ag pointe ar leith, nuair a aistrítear an luach ar dheis ag aonad traidisiúnta, luach méaduithe faoi 25 gnáthaonad. Ar an ngraf is cosúil go bhfuil ardú measartha géar ar luachanna ó phointe tugtha.

Sampla eile. Tá luach an díorthach cothrom -0,1 ciallaíonn sé sin nuair a díláithrítear é in aghaidh an aonaid thraidisiúnta, luach laghdú de 0,1 aonad traidisiúnta amháin. Ag an am céanna, ar ghraf na feidhme, is féidir linn fána anuas ar éigean faoi deara a bhreathnú. Ag tarraingt analaí le sliabh, tá sé amhail is go bhfuil muid go han-mhall ag ísliú fána mhín ó shliabh, murab ionann agus an sampla roimhe seo, áit a raibh orainn beanna an-ghéar a dhreapadh :)

Dá bhrí sin, tar éis idirdhealú a dhéanamh ar an bhfeidhm ar seachrán и , sainmhínímid cothromóidí difreálach páirteach 1ú ordú. Tar éis na cothromóidí a chinneadh, gheobhaidh muid córas de dhá chothromóid, trína réiteach a mbeimid in ann luachanna den sórt sin de na comhéifeachtaí a roghnú и , as a n-athraíonn luachanna na ndíorthach comhfhreagrach ag pointí ar leith de mhéid an-bheag, agus i gcás réitigh anailíse nach n-athraíonn siad ar chor ar bith. I bhfocail eile, sroichfidh an fheidhm earráide ag na comhéifeachtaí aimsithe íosmhéid, ós rud é go mbeidh luachanna na ndíorthach páirteach ag na pointí seo cothrom le nialas.

Mar sin, de réir rialacha na difreála, is ionann cothromóid pháirteach díorthach an 1ú ordú maidir leis an gcomhéifeacht beidh an fhoirm:

Cothromóid díorthach páirteach 1ú ordú maidir le beidh an fhoirm:

Mar thoradh air sin, fuaireamar córas cothromóidí a bhfuil réiteach anailíseach simplí go leor aige:

tús {cothromóid*}
tús{cásanna}
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
críoch{cásanna}
críoch{cothromóid*}

Sula ndéantar an chothromóid a réiteach, déanaimis réamhluchtú, seiceáil go bhfuil an luchtú ceart, agus formáid na sonraí.

Luchtú agus formáidiú sonraí

Ba chóir a thabhairt faoi deara mar gheall ar an bhfíric gur le haghaidh an réiteach anailíseach, agus ina dhiaidh sin do shliocht grádán agus stochastic grádán, úsáidfimid an cód in dhá athrú: ag baint úsáide as an leabharlann UimhPy agus gan é a úsáid, beidh gá againn le formáidiú sonraí cuí (féach an cód).

Cód um luchtú agus próiseáil sonraí

# импортируем все нужные нам библиотеки
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 '********************************************'

Amharcléiriú

Anois, tar éis dúinn, ar an gcéad dul síos, na sonraí a luchtú, sa dara háit, seiceáil cruinneas an luchtaithe agus formáidiú na sonraí ar deireadh, déanfaimid an chéad léirshamhlú. Is é an modh a úsáidtear go minic le haghaidh seo péire plota leabharlanna farraige. Inár sampla, mar gheall ar an líon teoranta, níl aon phointe ag baint úsáide as an leabharlann farraige. Bainfimid úsáid as an leabharlann rialta matplotlib agus gan ach breathnú ar an scathphlota.

Cóid scatterplot

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()

Cairt Uimh. 1 “Ag brath ar ioncam ar mhí na bliana”

Réiteach anailíseach

A ligean ar úsáid a bhaint as na huirlisí is coitianta i python agus córas na gcothromóidí a réiteach:

tús {cothromóid*}
tús{cásanna}
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
críoch{cásanna}
críoch{cothromóid*}

De réir riail Cramer gheobhaidh muid an cinntitheach ginearálta, chomh maith le cinntithigh trí agus , ina dhiaidh sin, an chinntitheach a roinnt ar don chinntitheach ginearálta - faigh an comhéifeacht , mar an gcéanna feicimid an chomhéifeacht .

Cóid réitigh anailíse

# определим функцию для расчета коэффициентов 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)

Seo a fuaireamar:

Mar sin, go bhfuarthas luachanna na gcomhéifeachtaí, tá suim na n-dialltaí cearnacha bunaithe. Tarraingímid líne dhíreach ar an histeagram scaipthe de réir na gcomhéifeachtaí aimsithe.

Cóid líne aischéimnithí

# определим функцию для формирования массива рассчетных значений выручки
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()

Cairt Uimh. 2 “Freagraí cearta agus ríofa”

Is féidir leat breathnú ar an graf diall do gach mí. Inár gcás, ní bhainfimid aon luach praiticiúil suntasach uaidh, ach sásóimid ár bhfiosracht maidir le cé chomh maith is atá an chothromóid aischéimniúcháin líneach shimplí mar thréith ag spleáchas an ioncaim ar mhí na bliana.

Cóid chairt diall

# определим функцию для формирования массива отклонений в процентах
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()

Cairt Uimh. 3 “Diallais, %”

Níl sé foirfe, ach chríochnaíomar ár dtasc.

A ligean ar scríobh feidhm sin, chun a chinneadh an comhéifeachtaí и úsáideann an leabharlann UimhPy, níos cruinne, scríobhfaimid dhá fheidhm: ceann amháin ag baint úsáide as maitrís pseudoinverse (ní mholtar go praiticiúil, ós rud é go bhfuil an próiseas ríomh casta agus éagobhsaí), an ceann eile ag baint úsáide as cothromóid maitrís.

Cód Réitigh Anailíseach (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

Déanaimis comparáid idir an t-am a chaitear ar na comhéifeachtaí a chinneadh и , de réir na 3 mhodh a chuirtear i láthair.

Cód le haghaidh ríomh am a ríomh

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)

Le méid beag sonraí, tagann feidhm “féinscríofa” amach romhainn, a aimsíonn na comhéifeachtaí ag baint úsáide as modh Cramer.

Anois is féidir leat bogadh ar aghaidh go dtí bealaí eile chun comhéifeachtaí a aimsiú и .

Ghinealach Grádáin

Ar dtús, déanaimis sainmhíniú ar cad is grádán ann. Go simplí, is teascán é an grádán a léiríonn treo fáis uasta feidhme. De réir analaí le dreapadóireacht sléibhe, áit a bhfuil aghaidh an ghrádáin áit a bhfuil an dreapadh is géire go barr an tsléibhe. Agus an sampla á fhorbairt leis an sliabh, cuimhnímid go bhfuil an shliocht is géire de dhíth orainn i ndáiríre chun an ísealchríoch a bhaint amach chomh tapa agus is féidir, is é sin, an t-íosmhéid - an áit nach n-ardóidh nó nach laghdaítear an fheidhm. Ag an bpointe seo beidh an díorthach cothrom le nialas. Mar sin, ní grádán atá ag teastáil uainn, ach frithghrádán. Chun an frithghrádán a fháil ní gá duit ach an grádán a iolrú faoi -1 (lúide a haon).

Tabhair aird ar an bhfíric gur féidir roinnt minima a bheith ag feidhm, agus tar éis dul isteach i gceann acu ag baint úsáide as an algartam atá molta thíos, ní bheidh muid in ann íosmhéid eile a aimsiú, a d'fhéadfadh a bheith níos ísle ná an ceann a fuarthas. Lig dúinn a scíth a ligean, ní bagairt é seo dúinn! Inár gcás táimid ag déileáil le íosmhéid amháin, ós rud é ár bhfeidhm ar an ngraf tá parabóil rialta. Agus mar ba cheart go mbeadh a fhios againn go léir ónár gcúrsa matamaitice scoile, níl ach íosmhéid amháin ag paraból.

Tar éis dúinn fáil amach cén fáth a raibh grádán ag teastáil uainn, agus freisin gur teascán é an grádán, is é sin, veicteoir a bhfuil comhordanáidí tugtha aige, atá díreach mar na comhéifeachtaí céanna и is féidir linn shliocht grádán a chur i bhfeidhm.

Sula dtosaíonn tú, molaim cúpla abairt a léamh faoin algartam sluaite:

Cinnimid ar mhodh bréagach randamach comhordanáidí na gcomhéifeachtaí и . In ár sampla, beidh muid ag sainiú comhéifeachtaí gar náid. Is cleachtas coiteann é seo, ach d’fhéadfadh go mbeadh a chleachtas féin ag gach cás.
Ó chomhordanáid dealaigh luach an díorthaigh pháirtigh den 1ú ordú ag an bpointe . Mar sin, má tá an díorthach dearfach, méadaíonn an fheidhm. Mar sin, trí luach an díorthaigh a dhealú, bogfaimid i dtreo eile an fháis, is é sin, i dtreo an tsleachta. Má tá an díorthach diúltach, ansin laghdaítear an fheidhm ag an bpointe seo agus trí luach an díorthaigh a dhealú gluaisimid i dtreo an tsliachta.
Déanaimid oibríocht den chineál céanna leis an gcomhordanáid : dealaigh luach an díorthaigh pháirtigh ag an bpointe .
D'fhonn gan léim thar an íosmhéid agus eitilt isteach i spás domhain, is gá méid na gcéimeanna a shocrú i dtreo an tsleachta. Go ginearálta, d'fhéadfá alt iomlán a scríobh faoi conas an chéim a shocrú i gceart agus conas é a athrú le linn an phróisis shliocht chun costais ríomhaireachtúla a laghdú. Ach anois tá tasc beagán difriúil romhainn, agus socróimid méid na céime ag baint úsáide as an modh eolaíoch "póca" nó, mar a deir siad go coitianta, go heimpíreach.
Nuair atá muid ó na comhordanáidí a thugtar и a dhealú luachanna na ndíorthach, faigheann muid comhordanáidí nua и . Glacann muid an chéad chéim eile (dealú), cheana féin ó na comhordanáidí ríofa. Agus mar sin tosaíonn an timthriall arís agus arís eile, go dtí go mbaintear amach an cóineasú riachtanach.

Gach! Anois táimid réidh le dul ar thóir an ghleanna is doimhne den Mariana Trench. Ar aghaidh linn.

Cód le haghaidh ardú céime

# напишем функцию градиентного спуска без использования библиотеки 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

Léimeamar go bun an Trench Mariana agus ansin fuaireamar na luachanna comhéifeachta céanna и , agus is é sin go díreach a rabhthas ag súil leis.

Déanaimis tumadóireacht eile, ach an uair seo, líonfar ár bhfeithicil domhainfharraige le teicneolaíochtaí eile, eadhon leabharlann UimhPy.

Cód le haghaidh shliocht grádáin (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

Luachanna comhéifeachta и do-athraithe.

Breathnaímid ar conas a d'athraigh an earráid le linn shliocht an ghrádáin, is é sin, conas a d'athraigh suim na ndalltaí cearnógacha le gach céim.

Cód chun suimeanna diallais cearnacha a bhreacadh

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 Uimh. 4 “Sum na diallais chearnaithe le linn shliocht an ghrádáin”

Ar an ngraf feicimid go laghdaítear an earráid le gach céim, agus tar éis líon áirithe atriallta feicimid líne beagnach cothrománach.

Ar deireadh, déanaimis meastachán ar an difríocht in am forghníomhaithe an chóid:

Cód chun am ríomh shliocht an ghrádáin a chinneadh

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)

B’fhéidir go bhfuil rud éigin mícheart á dhéanamh againn, ach arís is feidhm shimplí “scríofa sa bhaile” í nach n-úsáideann an leabharlann UimhPy níos fearr ná an t-am ríofa d'fheidhm ag baint úsáide as an leabharlann UimhPy.

Ach nílimid ag seasamh go fóill, ach táimid ag bogadh i dtreo staidéar a dhéanamh ar bhealach spreagúil eile chun an chothromóid aischéimniúcháin líneach shimplí a réiteach. Buail le chéile!

Ghinealach grádán stochastic

D'fhonn prionsabal oibríochta an shliocht grádán stochastic a thuiscint go tapa, is fearr a dhifríochtaí a chinneadh ó ghnáthshliocht grádán. Táimid, i gcás shliocht grádán, i gcothromóidí díorthach de и d'úsáid sé suimeanna luachanna na ngnéithe go léir agus na freagraí fíora atá ar fáil sa sampla (is é sin suimeanna gach и ). I shliocht grádán stochastic, ní úsáidfimid na luachanna go léir atá i láthair sa sampla, ach ina ionad sin, roghnaigh pseudo-randamach an t-innéacs samplach mar a thugtar air agus úsáidimid a luachanna.

Mar shampla, má chinntear gurb é an t-innéacs uimhir 3 (trí), ansin glacaimid na luachanna и , ansin cuirimid na luachanna isteach sna cothromóidí díorthacha agus cinnimid comhordanáidí nua. Ansin, tar éis dúinn na comhordanáidí a chinneadh, déanaimid an t-innéacs samplach a chinneadh go randamach arís, cuirimid na luachanna a fhreagraíonn don innéacs isteach sna cothromóidí difreálach páirteacha, agus cinnimid na comhordanáidí ar bhealach nua. и srl. go dtí go n-iompaíonn an chóineasú glas. Ar an gcéad amharc, b'fhéidir nach cosúil go n-oibreodh sé seo ar chor ar bith, ach déanann sé. Is fíor gur fiú a thabhairt faoi deara nach laghdaíonn an earráid le gach céim, ach is cinnte go bhfuil claonadh ann.

Cad iad na buntáistí a bhaineann le grádán stoichastic a bheith ag teacht chun cinn thar an gceann traidisiúnta? Má tá ár méid sampla an-mhór agus tomhaiste i na mílte luachanna, ansin tá sé i bhfad níos éasca a phróiseáil, abair, míle randamach acu, seachas an sampla ar fad. Seo an áit a dtagann sliocht grádán stochastic i bhfeidhm. Inár gcás, ar ndóigh, ní thabharfaimid faoi deara mórán difríochta.

Breathnaímid ar an gcód.

Cód le haghaidh shliocht grádán stochastic

# определим функцию стох.град.шага
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])

Breathnaímid go cúramach ar na comhéifeachtaí agus glacaimid orainn féin ag cur na ceiste "Conas is féidir é seo a bheith?" Fuair muid luachanna comhéifeachta eile и . B'fhéidir go bhfuil níos mó paraiméadair optamach aimsithe ag ghinealach grádán stochastic don chothromóid? Ar an drochuair níl. Is leor breathnú ar shuim na ndalltaí cearnógacha agus a fheiceáil le luachanna nua na gcomhéifeachtaí, is mó an earráid. Níl aon deifir orainn éadóchas a dhéanamh. Déanaimis graf den athrú earráide.

Cód chun suim na diallais chearnógacha a bhreacadh i nginiúint grádáin stochastic

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 Uimh. 5 “Sum na ndalltaí cearnógacha le linn shliocht an ghrádáin stochastaigh”

Ag féachaint ar an sceideal, titeann gach rud i bhfeidhm agus anois déanfaimid gach rud a shocrú.

Mar sin, cad a tharla? Seo a leanas a tharla. Nuair a roghnaimid mí go randamach, is don mhí roghnaithe a bhféachann ár n-algartam chun an earráid a laghdú agus ioncam á ríomh. Ansin roghnóimid mí eile agus déanaimid an ríomh arís, ach laghdaítear an earráid don dara mí roghnaithe. Anois cuimhnigh go n-imíonn an chéad dá mhí go mór ó líne na cothromóide aischéimnithí líneach simplí. Ciallaíonn sé seo, nuair a roghnaítear aon cheann den dá mhí seo, trí earráid gach ceann acu a laghdú, go méadóidh ár n-algartam go mór an earráid don sampla iomlán. Mar sin, cad atá le déanamh? Is é an freagra simplí: ní mór duit an chéim shliocht a laghdú. Tar éis an tsaoil, trí chéim an tsliocht a laghdú, stopfaidh an earráid “léim” suas agus síos freisin. Nó in áit, ní stopfaidh an earráid “léim”, ach ní dhéanfaidh sé chomh tapa sin :) Déanaimis seiceáil.

Cód chun SGD a rith le hincrimintí níos lú

# запустим функцию, уменьшив шаг в 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 Uimh. 6 “Sum na ndalltaí cearnógacha le linn shliocht an ghrádáin stochastic (80 míle céim)”

Tá feabhas tagtha ar na comhéifeachtaí, ach níl siad idéalach fós. Go hipitéiseach, is féidir é seo a cheartú ar an mbealach seo. Roghnaímid, mar shampla, sna 1000 atriall deiridh luachanna na gcomhéifeachtaí lena ndearnadh an earráid íosta. Fíor, le haghaidh seo beidh orainn freisin luachanna na gcomhéifeachtaí féin a scríobh síos. Ní dhéanfaimid é seo, ach aird a thabhairt ar an sceideal. Breathnaíonn sé go réidh agus is cosúil go laghdóidh an earráid go cothrom. I ndáiríre níl sé seo fíor. Breathnaímid ar na chéad 1000 atriallta agus déanaimis iad a chur i gcomparáid leis an gceann deireanach.

Cód don chairt SGD (an chéad 1000 céim)

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 Uimh. 7 “Sum na diallais chearnaithe SGD (an chéad 1000 céim)”

Graf Uimh. 8 “Sum na diallais chearnaithe SGD (na 1000 céim dheireanach)”

Ag tús an tsliocht, tugaimid faoi deara laghdú measartha aonfhoirmeach agus géar san earráid. Sna atriallta deireanacha, feicimid go dtéann an earráid timpeall agus timpeall ar luach 1,475 agus ag roinnt chuimhneacháin fiú ionann an luach is fearr is féidir, ach ansin téann sé suas fós ... arís agus arís eile, is féidir leat a scríobh síos na luachanna an comhéifeachtaí и , agus ansin roghnaigh iad siúd a bhfuil an earráid íosta ina leith. Mar sin féin, bhí fadhb níos tromchúisí againn: bhí orainn 80 míle céim a ghlacadh (féach an cód) chun luachanna a fháil gar don bharrmhaith. Agus tá sé seo contrártha cheana féin leis an smaoineamh am ríomh a shábháil le shliocht grádán stochastic i gcoibhneas le shliocht grádáin. Cad is féidir a cheartú agus a fheabhsú? Níl sé deacair a thabhairt faoi deara go bhfuilimid ag dul síos go muiníneach sa chéad atriall agus, mar sin, ba cheart dúinn céim mhór a fhágáil sa chéad atriall agus an chéim a laghdú agus muid ag dul ar aghaidh. Ní dhéanfaimid é seo san Airteagal seo - tá sé ró-fhada cheana féin. Is féidir leo siúd ar mian leo smaoineamh ar a son féin conas é seo a dhéanamh, níl sé deacair :)

Anois, déanaimis shliocht grádán stochastic ag baint úsáide as an leabharlann UimhPy (agus ná bac linn na clocha a d’aithin muid níos luaithe)

Cód um Ghiniúint Grádáin Stochastic (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

Na luachanna iompaigh amach a bheith beagnach mar an gcéanna nuair a íslitheach gan úsáid UimhPy. Mar sin féin, tá sé seo loighciúil.

Déanaimis a fháil amach cé chomh fada agus a thóg laghduithe grádáin stochastic orainn.

Cód chun am ríofa SGD a chinneadh (80 míle céim)

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)

Dá fhaide isteach san fhoraois, is ea is dorcha na scamaill: arís, léiríonn an fhoirmle “féinscríofa” an toradh is fearr. Tugann sé seo go léir le tuiscint go gcaithfidh bealaí níos caolchúisí a bheith ann leis an leabharlann a úsáid UimhPy, rud a chuireann dlús le hoibríochtaí ríomha i ndáiríre. San Airteagal seo ní bheidh muid ag foghlaim mar gheall orthu. Beidh rud éigin le smaoineamh faoi i do chuid ama saor :)

Déanaimid achoimre

Sula ndéanaim achoimre, ba mhaith liom ceist a fhreagairt a d’eascair ónár léitheoir daor is dócha. Cén fáth, i ndáiríre, a leithéid de “chéasadh” le sliocht, cén fáth ar gá dúinn siúl suas agus síos an sliabh (den chuid is mó) chun teacht ar an ísealchríoch luachmhar, má tá gléas chomh cumhachtach agus simplí inár lámha againn, sa réiteach anailíseach, a sheolann láithreach chuig an áit cheart sinn?

Tá freagra na ceiste seo ar an dromchla. Anois táimid tar éis féachaint ar shampla an-simplí, ina bhfuil an freagra fíor ag brath ar chomhartha amháin . Ní fheiceann tú é seo go minic sa saol, mar sin déanaimis a shamhlú go bhfuil 2, 30, 50 comhartha nó níos mó againn. Cuirimis leis seo na mílte, nó fiú na mílte luach do gach tréith. Sa chás seo, ní fhéadfaidh an réiteach anailíseach an tástáil a sheasamh agus go dteipfidh air. Ina dhiaidh sin, go mall ach is cinnte go dtabharfaidh shliocht an ghrádáin agus a éagsúlachtaí níos gaire dúinn don sprioc - íosmhéid na feidhme. Agus ná bíodh imní ort faoi luas - is dócha go bhféachfaimid ar bhealaí a ligfidh dúinn fad céim a shocrú agus a rialáil (is é sin, luas).

Agus anois an achoimre ghairid iarbhír.

Ar an gcéad dul síos, tá súil agam go gcabhróidh an t-ábhar a chuirtear i láthair san alt le tosú “eolaithe sonraí” chun tuiscint a fháil ar conas cothromóidí aischéimnithí líneacha simplí (agus ní hamháin) a réiteach.

Ar an dara dul síos, d'fhéachamar ar roinnt bealaí chun an chothromóid a réiteach. Anois, ag brath ar an gcás, is féidir linn a roghnú an ceann is fearr a oireann chun an fhadhb a réiteach.

Ar an tríú dul síos, chonaic muid cumhacht na socruithe breise, is é sin fad céim shliocht an ghrádáin. Ní féidir faillí a dhéanamh ar an bparaiméadar seo. Mar a luadh thuas, d'fhonn costas na n-áireamh a laghdú, ba cheart fad na céime a athrú le linn an shliocht.

Ar an gceathrú dul síos, inár gcás, léirigh feidhmeanna “scríofa sa bhaile” na torthaí ama ab fhearr le haghaidh ríomhaireachtaí. Is dócha go bhfuil sé seo mar gheall ar an úsáid is proifisiúnta a bhaintear as cumais na leabharlainne UimhPy. Ach bíodh sin mar a fhéadfadh sé, tugann an tátal seo a leanas le fios é féin. Ar thaobh amháin, uaireanta is fiú tuairimí seanbhunaithe a cheistiú, agus ar an láimh eile, ní fiú i gcónaí gach rud a chasta - ar a mhalairt, uaireanta tá bealach níos simplí chun fadhb a réiteach níos éifeachtaí. Agus ós rud é gurb é an sprioc a bhí againn ná trí chur chuige a anailísiú chun cothromóid shimplí aischéimniúcháin líneach a réiteach, ba leor dúinne feidhmeanna “féinscríofa” a úsáid.