Oddiy chiziqli regressiya tenglamasini yechish

Maqolada oddiy (juftlangan) regressiya chizig'ining matematik tenglamasini aniqlashning bir necha usullari ko'rib chiqiladi.

Bu yerda muhokama qilingan tenglamani yechishning barcha usullari eng kichik kvadratlar usuliga asoslangan. Usullarni quyidagicha belgilaymiz:

• Analitik yechim
• Gradient tushishi
• Stokastik gradient tushishi

To'g'ri chiziq tenglamasini echishning har bir usuli uchun maqolada turli xil funktsiyalar berilgan, ular asosan kutubxonadan foydalanmasdan yozilganlarga bo'linadi. numpy va hisob-kitoblar uchun foydalanadiganlar numpy. Bu mohirona foydalanish, deb ishoniladi numpy hisoblash xarajatlarini kamaytiradi.

Maqolada keltirilgan barcha kodlar tilda yozilgan piton 2.7 foydalanish Yupyter daftarchasi. Manba kodi va namuna ma'lumotlari bilan fayl joylashtirilgan Github

Maqola ko'proq yangi boshlanuvchilar uchun ham, sun'iy intellektning juda keng bo'limini - mashinani o'rganishni asta-sekin o'rganishni boshlaganlar uchun mo'ljallangan.

Materialni tasvirlash uchun biz juda oddiy misoldan foydalanamiz.

Misol shartlari

Bizda qaramlikni tavsiflovchi beshta qiymat mavjud Y от X (1-jadval):

№1-jadval “Namunali shartlar”

Biz qadriyatlar deb taxmin qilamiz yilning oyi, va - bu oydagi daromad. Boshqacha qilib aytganda, daromad yilning oyiga bog'liq va - daromad bog'liq bo'lgan yagona belgi.

Masalan, daromadning yil oyiga shartli bog'liqligi nuqtai nazaridan ham, qiymatlar soni nuqtai nazaridan ham - ular juda oz. Biroq, bunday soddalashtirish, ular aytganidek, yangi boshlanuvchilar o'zlashtiradigan materialni har doim ham osonlik bilan tushuntirishga imkon beradi. Shuningdek, raqamlarning soddaligi misolni qog'ozda katta mehnat xarajatlarisiz hal qilishni xohlaydiganlarga imkon beradi.

Faraz qilaylik, misolda keltirilgan bog'liqlik shaklning oddiy (juftlangan) regressiya chizig'ining matematik tenglamasi bilan juda yaxshi yaqinlashishi mumkin:

qayerda daromad olingan oy, - oyga to'g'ri keladigan daromad; и taxminiy chiziqning regressiya koeffitsientlari hisoblanadi.

Koeffitsientga e'tibor bering ko'pincha taxminiy chiziqning qiyalik yoki gradienti deb ataladi; miqdorini ifodalaydi o'zgarganda .

Shubhasiz, bizning misoldagi vazifamiz tenglamada bunday koeffitsientlarni tanlashdir и , bunda bizning hisoblangan daromad qiymatlarining oylar bo'yicha haqiqiy javoblardan og'ishlari, ya'ni. namunada keltirilgan qiymatlar minimal bo'ladi.

Eng kichik kvadrat usuli

Eng kichik kvadratlar usuliga ko'ra, og'ish uni kvadratga aylantirish orqali hisoblanishi kerak. Ushbu uslub, agar ular qarama-qarshi belgilarga ega bo'lsa, og'ishlarni o'zaro bekor qilishdan qochish imkonini beradi. Misol uchun, agar bir holatda, og'ish bo'lsa +5 (ortiqcha besh) va boshqasida -5 (minus besh), keyin og'ishlar yig'indisi bir-birini bekor qiladi va 0 (nol) ga teng bo'ladi. Bu og'ish kvadratiga emas, balki modulning xususiyatidan foydalanish mumkin va keyin barcha og'ishlar ijobiy bo'ladi va to'planadi. Biz bu nuqtaga batafsil to'xtalib o'tmaymiz, shunchaki hisob-kitoblarning qulayligi uchun og'ishning kvadratiga solish odatiy hol ekanligini ko'rsatamiz.

Kvadrat og'ishlarning (xatolarning) eng kichik yig'indisini aniqlaydigan formula shunday ko'rinadi:

qayerda bu to'g'ri javoblarni yaqinlashtirish funktsiyasidir (ya'ni biz hisoblagan daromad),

to'g'ri javoblar (namunada ko'rsatilgan daromad),

namunaviy indeks (og'ish aniqlangan oyning soni)

Funksiyani farqlaylik, qisman differensial tenglamalarni aniqlaymiz va analitik yechimga o‘tishga tayyormiz. Ammo birinchi navbatda, differentsiatsiya nima ekanligi haqida qisqacha ekskursiya qilaylik va hosilaning geometrik ma'nosini eslaylik.

Differentsiatsiya

Differentsiallash funksiyaning hosilasini topish amalidir.

hosila nima uchun ishlatiladi? Funktsiyaning hosilasi funktsiyaning o'zgarish tezligini tavsiflaydi va bizga uning yo'nalishini aytadi. Agar berilgan nuqtadagi hosila musbat bo'lsa, u holda funktsiya ortadi, aks holda funktsiya kamayadi. Va mutlaq lotin qiymati qanchalik katta bo'lsa, funktsiya qiymatlarining o'zgarish tezligi shunchalik yuqori bo'ladi, shuningdek, funktsiya grafigining qiyaligi qanchalik tik bo'ladi.

Masalan, Dekart koordinata sistemasi sharoitida M(0,0) nuqtadagi hosilaning qiymati ga teng. + 25 ma'lum bir nuqtada, qiymat o'zgartirilganda, degan ma'noni anglatadi an'anaviy birlik, qiymat bilan o'ngga 25 an'anaviy birlikka oshadi. Grafikda bu qiymatlarning keskin o'sishiga o'xshaydi berilgan nuqtadan.

Yana bir misol. Hosila qiymati teng -0,1 ko'chirilganda degan ma'noni anglatadi bitta an'anaviy birlik uchun qiymat faqat 0,1 an'anaviy birlikka kamayadi. Shu bilan birga, funktsiya grafigida biz deyarli sezilmaydigan pastga qiyalikni kuzatishimiz mumkin. Tog'ga o'xshatish, biz avvalgi misoldan farqli o'laroq, biz juda tik cho'qqilarga chiqishimiz kerak bo'lgan tog'dan yumshoq qiyalikdan juda sekin tushayotganga o'xshaymiz :)

Shunday qilib, funktsiyani farqlashdan keyin ziddiyatlar bilan и , 1-tartibli qisman differentsial tenglamalarni aniqlaymiz. Tenglamalarni aniqlagandan so'ng, biz ikkita tenglamalar tizimini olamiz, ularni hal qilish orqali biz koeffitsientlarning bunday qiymatlarini tanlashimiz mumkin. и , buning uchun berilgan nuqtalarda mos keladigan hosilalarning qiymatlari juda, juda kichik miqdorga o'zgaradi va analitik yechimda umuman o'zgarmaydi. Boshqacha qilib aytganda, topilgan koeffitsientlardagi xato funktsiyasi minimal darajaga etadi, chunki bu nuqtalarda qisman hosilalarning qiymatlari nolga teng bo'ladi.

Demak, differentsiallash qoidalariga ko'ra, koeffitsientga nisbatan 1-tartibli qisman hosila tenglamasi shaklni oladi:

ga nisbatan 1-tartibli qisman hosila tenglama shaklni oladi:

Natijada, biz juda oddiy analitik yechimga ega bo'lgan tenglamalar tizimini oldik:

boshlash{tenglama*}
boshlash{holatlar}
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
end{holatlar}
end{tenglama*}

Tenglamani yechishdan oldin, keling, oldindan yuklaymiz, yuklanishning to'g'riligini tekshiramiz va ma'lumotlarni formatlaymiz.

Ma'lumotlarni yuklash va formatlash

Shuni ta'kidlash kerakki, analitik yechim uchun, keyinchalik gradient va stokastik gradient tushishi uchun biz kodni ikkita variantda ishlatamiz: kutubxonadan foydalanish numpy va undan foydalanmasdan, keyin bizga tegishli ma'lumotlarni formatlash kerak bo'ladi (kodga qarang).

Ma'lumotlarni yuklash va qayta ishlash kodi

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

Vizualizatsiya

Endi, birinchidan, ma'lumotlarni yuklaganimizdan so'ng, ikkinchidan, yuklanishning to'g'riligini tekshirib, nihoyat ma'lumotlarni formatlashdan so'ng, biz birinchi vizualizatsiyani amalga oshiramiz. Buning uchun tez-tez ishlatiladigan usul juftlik chizmasi kutubxonalar Dengiz tug'ilishi. Bizning misolimizda raqamlar cheklanganligi sababli kutubxonadan foydalanishning ma'nosi yo'q Dengiz tug'ilishi. Biz oddiy kutubxonadan foydalanamiz matplotlib va shunchaki scatterplotga qarang.

Tarqalish kodi

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

Grafik № 1 «Daromadning yil oyiga bog'liqligi»

Analitik yechim

Keling, eng keng tarqalgan vositalardan foydalanaylik python va tenglamalar tizimini yeching:

boshlash{tenglama*}
boshlash{holatlar}
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
end{holatlar}
end{tenglama*}

Kramer qoidasiga ko'ra umumiy aniqlovchini, shuningdek, tomonidan aniqlovchilarni topamiz va tomonidan , shundan keyin aniqlovchini bo'lish umumiy determinantga - koeffitsientni toping , xuddi shunday koeffitsientni topamiz .

Analitik yechim kodi

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

Mana bizda nima bor:

Shunday qilib, koeffitsientlarning qiymatlari topildi, kvadratik og'ishlar yig'indisi aniqlandi. Tarqalish gistogrammasida topilgan koeffitsientlarga muvofiq to'g'ri chiziq chizamiz.

Regressiya satr kodi

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

Grafik № 2 "To'g'ri va hisoblangan javoblar"

Har oy uchun og'ish grafigiga qarashingiz mumkin. Bizning holatda, biz undan muhim amaliy ahamiyatga ega bo'lmaymiz, lekin oddiy chiziqli regressiya tenglamasi daromadning yil oyiga bog'liqligini qanchalik yaxshi tavsiflashiga qiziqishimizni qondiramiz.

Og'ish diagrammasi kodi

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

Grafik № 3 “Og'ishlar, %”

Mukammal emas, lekin biz vazifamizni bajardik.

Koeffitsientlarni aniqlash uchun funksiya yozamiz и kutubxonadan foydalanadi numpy, aniqrog'i, biz ikkita funktsiyani yozamiz: biri psevdoteskari matritsa yordamida (amalda tavsiya etilmaydi, chunki jarayon hisoblash jihatidan murakkab va beqaror), ikkinchisi matritsa tenglamasi yordamida.

Analitik yechim kodi (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

Keling, koeffitsientlarni aniqlashga sarflangan vaqtni taqqoslaylik и , taqdim etilgan 3 ta usulga muvofiq.

Hisoblash vaqtini hisoblash uchun kod

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)

Kichik miqdordagi ma'lumotlar bilan "o'z-o'zidan yozilgan" funksiya oldinga chiqadi, bu esa Cramer usuli yordamida koeffitsientlarni topadi.

Endi siz koeffitsientlarni topishning boshqa usullariga o'tishingiz mumkin и .

Gradient tushishi

Birinchidan, gradient nima ekanligini aniqlaylik. Oddiy qilib aytganda, gradient - bu funksiyaning maksimal o'sish yo'nalishini ko'rsatadigan segment. Tog'ga ko'tarilish bilan taqqoslaganda, gradient yuzlari tog' cho'qqisiga eng tik ko'tarilish joyi bo'lgan joyda. Tog' bilan misolni ishlab chiqsak, biz pasttekislikka imkon qadar tezroq erishish uchun eng tik tushish kerakligini eslaymiz, ya'ni minimal - funktsiya o'smaydigan yoki kamaymaydigan joy. Bu vaqtda hosila nolga teng bo'ladi. Shuning uchun bizga gradient emas, balki antigradient kerak. Antigradientni topish uchun gradientni ko'paytirish kifoya -1 (minus bir).

Funktsiyaning bir nechta minimalari bo'lishi mumkinligiga e'tibor qarataylik va quyida taklif qilingan algoritm yordamida ulardan biriga tushsak, topilganidan pastroq bo'lishi mumkin bo'lgan boshqa minimumni topa olmaymiz. Keling, tinchlanaylik, bu bizga tahdid emas! Bizning holatimizda biz bitta minimal bilan shug'ullanamiz, chunki bizning funktsiyamiz Grafikda muntazam parabola. Va hammamiz maktab matematika kursidan juda yaxshi bilishimiz kerakki, parabolaning faqat bitta minimumi bor.

Bizga gradient nima uchun kerakligini, shuningdek, gradient segment, ya'ni koordinatalari bir xil koeffitsientlarga ega vektor ekanligini aniqlaganimizdan so'ng. и gradient tushishni amalga oshirishimiz mumkin.

Boshlashdan oldin, men tushish algoritmi haqida bir nechta jumlalarni o'qishni taklif qilaman:

• Biz koeffitsientlarning koordinatalarini psevdo-tasodifiy tarzda aniqlaymiz и . Bizning misolimizda biz nolga yaqin koeffitsientlarni aniqlaymiz. Bu odatiy amaliyot, ammo har bir holatda o'z amaliyoti bo'lishi mumkin.
• Koordinatadan nuqtadagi 1-tartibli qisman hosilaning qiymatini ayirish . Shunday qilib, agar hosila ijobiy bo'lsa, u holda funktsiya ortadi. Shuning uchun hosila qiymatini ayirib, biz o'sishning teskari yo'nalishi bo'yicha, ya'ni tushish yo'nalishi bo'yicha harakat qilamiz. Agar hosila manfiy bo'lsa, bu nuqtadagi funktsiya kamayadi va hosila qiymatini ayirish orqali biz tushish yo'nalishi bo'yicha harakat qilamiz.
• Biz koordinata bilan shunga o'xshash operatsiyani bajaramiz : nuqtadagi qisman hosilaning qiymatini ayirish .
• Minimaldan sakrab o'tmaslik va chuqur kosmosga uchmaslik uchun qadam o'lchamini tushish yo'nalishi bo'yicha belgilash kerak. Umuman olganda, hisoblash xarajatlarini kamaytirish uchun qadamni qanday to'g'ri o'rnatish va tushish jarayonida uni qanday o'zgartirish haqida butun maqola yozishingiz mumkin. Ammo endi oldimizda biroz boshqacha vazifa turibdi va biz qadam o'lchamini ilmiy "poke" usuli yoki ular aytganidek, empirik tarzda o'rnatamiz.
• Berilgan koordinatalardan chiqqanimizdan keyin и hosilalarning qiymatlarini olib tashlasak, biz yangi koordinatalarni olamiz и . Biz hisoblangan koordinatalardan keyingi qadamni (ayirish) qilamiz. Va shuning uchun tsikl kerakli konvergentsiyaga erishilgunga qadar qayta-qayta boshlanadi.

Hammasi! Endi biz Mariana xandaqining eng chuqur darasini qidirishga tayyormiz. Qani boshladik.

Gradient tushish uchun kod

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

Biz Mariana xandaqining eng tubiga sho'ng'idik va u erda bir xil koeffitsient qiymatlarini topdik и , aynan nima kutilgan edi.

Keling, yana bir sho'ng'in qilaylik, faqat bu safar bizning chuqur dengiz transportimiz boshqa texnologiyalar, xususan kutubxona bilan to'ldiriladi. numpy.

Gradient tushish kodi (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

Koeffitsient qiymatlari и o'zgarmas.

Keling, gradient tushishi paytida xato qanday o'zgarganini, ya'ni har bir qadamda kvadrat og'ishlar yig'indisi qanday o'zgarganini ko'rib chiqaylik.

Kvadrat og'ishlar yig'indisini chizish uchun kod

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

Grafik № 4 «Gradiyent tushish paytida kvadrat og'ishlar yig'indisi»

Grafikda biz har bir qadamda xato kamayib borishini ko'ramiz va ma'lum miqdordagi iteratsiyalardan so'ng biz deyarli gorizontal chiziqni kuzatamiz.

Nihoyat, kodni bajarish vaqtidagi farqni hisoblaylik:

Gradient tushishini hisoblash vaqtini aniqlash uchun kod

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)

Ehtimol, biz noto'g'ri ish qilyapmiz, lekin yana bu kutubxonadan foydalanmaydigan oddiy "uyda yozilgan" funksiya. numpy kutubxonadan foydalangan holda funksiyani hisoblash vaqtidan oshib ketadi numpy.

Ammo biz bir joyda turmayapmiz, balki oddiy chiziqli regressiya tenglamasini yechishning boshqa qiziqarli usulini o'rganishga intilyapmiz. Tanishing!

Stokastik gradient tushishi

Stokastik gradient tushishining ishlash printsipini tezda tushunish uchun uning oddiy gradient tushishidan farqini aniqlash yaxshiroqdir. Biz, gradient tushish holatida, hosilalarining tenglamalarida и namunada mavjud bo'lgan barcha xususiyatlar va to'g'ri javoblar qiymatlari yig'indisidan foydalangan (ya'ni barcha xususiyatlarning yig'indisi). и ). Stokastik gradient tushishida biz namunadagi barcha qiymatlardan foydalanmaymiz, aksincha, psevdo-tasodifiy ravishda namunaviy indeks deb ataladigan narsani tanlaymiz va uning qiymatlaridan foydalanamiz.

Misol uchun, agar indeks 3 (uch) raqami bo'lishi aniqlansa, biz qiymatlarni olamiz и , keyin biz qiymatlarni hosila tenglamalariga almashtiramiz va yangi koordinatalarni aniqlaymiz. Keyin koordinatalarni aniqlab, biz yana psevdo-tasodifiy namuna indeksini aniqlaymiz, indeksga mos keladigan qiymatlarni qisman differentsial tenglamalarga almashtiramiz va koordinatalarni yangi usulda aniqlaymiz. и va hokazo. konvergentsiya yashil rangga aylanmaguncha. Bir qarashda, bu umuman ishlamaydigandek tuyulishi mumkin, ammo shunday bo'ladi. To'g'ri, xato har qadamda kamaymasligini ta'kidlash joiz, ammo tendentsiya albatta mavjud.

Stokastik gradient tushishning an'anaviydan qanday afzalliklari bor? Agar bizning tanlama hajmimiz juda katta bo'lsa va o'n minglab qiymatlar bilan o'lchanadigan bo'lsa, unda butun namunani emas, balki, aytaylik, tasodifiy mingtasini qayta ishlash ancha oson bo'ladi. Bu erda stokastik gradient tushishi o'ynaydi. Bizning holatlarimizda, albatta, biz katta farqni sezmaymiz.

Keling, kodni ko'rib chiqaylik.

Stokastik gradient tushish uchun kod

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

Biz koeffitsientlarga diqqat bilan qaraymiz va "Bu qanday bo'lishi mumkin?" Degan savolni qo'lga kiritamiz. Biz boshqa koeffitsient qiymatlarini oldik и . Balki stoxastik gradient tushishi tenglama uchun maqbulroq parametrlarni topgandir? Afsuski yo `q. Kvadrat og'ishlar yig'indisiga qarash va koeffitsientlarning yangi qiymatlari bilan xato kattaroq ekanligini ko'rish kifoya. Biz umidsizlikka shoshilmaymiz. Keling, xato o'zgarishining grafigini tuzamiz.

Stokastik gradient tushishdagi kvadratik og'ishlar yig'indisini chizish uchun kod

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

Grafik № 5 «Stokastik gradient tushish paytida kvadrat og'ishlar yig'indisi»

Jadvalga qarasak, hamma narsa joyiga tushadi va endi biz hamma narsani tuzatamiz.

Xo'sh, nima bo'ldi? Quyidagi voqea sodir bo'ldi. Bir oyni tasodifiy tanlaganimizda, bizning algoritmimiz tanlangan oy uchun daromadni hisoblashda xatolikni kamaytirishga harakat qiladi. Keyin biz yana bir oyni tanlaymiz va hisobni takrorlaymiz, lekin biz ikkinchi tanlangan oy uchun xatoni kamaytiramiz. Endi birinchi ikki oy oddiy chiziqli regressiya tenglamasi chizig'idan sezilarli darajada og'ishini unutmang. Bu shuni anglatadiki, ushbu ikki oydan birortasi tanlanganda, ularning har birining xatosini kamaytirish orqali bizning algoritmimiz butun namunadagi xatoni jiddiy ravishda oshiradi. Xo'sh, nima qilish kerak? Javob oddiy: siz tushish bosqichini kamaytirishingiz kerak. Axir, tushish qadamini kamaytirish orqali, xato ham yuqoriga va pastga "sakrash" ni to'xtatadi. To'g'rirog'i, "sakrash" xatosi to'xtamaydi, lekin u buni juda tez qilmaydi :) Keling, tekshiramiz.

SGDni kichikroq qadamlar bilan ishga tushirish uchun kod

# запустим функцию, уменьшив шаг в 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()

Grafik № 6 “Stokastik gradient tushishi (80 ming qadam) paytida kvadrat og'ishlar yig'indisi”

Koeffitsientlar yaxshilandi, lekin hali ham ideal emas. Gipotetik jihatdan, buni shu tarzda tuzatish mumkin. Biz, masalan, oxirgi 1000 iteratsiyada minimal xatolikka yo'l qo'yilgan koeffitsientlarning qiymatlarini tanlaymiz. To'g'ri, buning uchun biz koeffitsientlarning qiymatlarini ham yozishimiz kerak. Biz buni qilmaymiz, aksincha, jadvalga e'tibor beramiz. Bu silliq ko'rinadi va xatolik teng ravishda kamaygan ko'rinadi. Aslida bu haqiqat emas. Keling, birinchi 1000 ta takrorlashni ko'rib chiqaylik va ularni oxirgisi bilan taqqoslaylik.

SGD diagrammasi uchun kod (birinchi 1000 qadam)

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

Grafik № 7 "SGD kvadrat og'ishlar yig'indisi (birinchi 1000 qadam)"

Grafik № 8 "SGD kvadrat og'ishlar yig'indisi (oxirgi 1000 qadam)"

Tushishning boshida biz xatolikning bir xil va keskin kamayishini kuzatamiz. Oxirgi iteratsiyalarda biz xato 1,475 qiymati atrofida va ba'zi daqiqalarda bu optimal qiymatga teng ekanligini ko'ramiz, lekin keyin u hali ham ko'tariladi ... Takrorlayman, siz qiymatlarni yozib olishingiz mumkin. koeffitsientlar и , va keyin xato minimal bo'lganlarni tanlang. Biroq, bizda jiddiyroq muammo bor edi: qiymatlarni optimalga yaqinlashtirish uchun 80 ming qadamni (kodga qarang) bajarishimiz kerak edi. Va bu allaqachon gradient tushishga nisbatan stokastik gradient tushishi bilan hisoblash vaqtini tejash g'oyasiga zid keladi. Nimani tuzatish va yaxshilash mumkin? Birinchi iteratsiyalarda biz ishonch bilan pastga tushayotganimizni payqash qiyin emas va shuning uchun biz birinchi iteratsiyalarda katta qadam qoldirib, oldinga siljishda qadamni kamaytirishimiz kerak. Biz buni ushbu maqolada qilmaymiz - bu juda uzoq. Xohlaganlar buni qanday qilishni o'zlari o'ylab ko'rishlari mumkin, bu qiyin emas :)

Endi kutubxona yordamida stokastik gradient tushishini amalga oshiramiz numpy (va biz ilgari aniqlagan toshlarga qoqilmaylik)

Stokastik gradient tushish kodi (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

Qadriyatlar foydalanmasdan tushganda deyarli bir xil bo'lib chiqdi numpy. Biroq, bu mantiqiy.

Keling, stokastik gradient tushishi bizni qancha vaqt olganini bilib olaylik.

SGD hisoblash vaqtini aniqlash uchun kod (80 ming qadam)

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)

O'rmonga qanchalik uzoq bo'lsa, bulutlar qorong'i bo'ladi: yana "o'z-o'zidan yozilgan" formula eng yaxshi natijani ko'rsatadi. Bularning barchasi kutubxonadan foydalanishning yanada nozik usullari bo'lishi kerakligini ko'rsatadi numpy, bu haqiqatan ham hisoblash operatsiyalarini tezlashtiradi. Ushbu maqolada biz ular haqida bilib olmaymiz. Bo'sh vaqtingizda o'ylaydigan narsa bo'ladi :)

Xulosa qilaylik

Xulosa qilishdan oldin, men aziz o'quvchimizdan kelib chiqqan savolga javob bermoqchiman. Nega, aslida, bunday "qiynoqlar" tushish bilan, agar qo'limizda shunday kuchli va oddiy qurilma bo'lsa, nega biz qimmatbaho pasttekislikni topish uchun tog'dan pastga va tog'dan (asosan pastga) yurishimiz kerak. Bizni bir zumda to'g'ri joyga teleportatsiya qiladigan analitik yechim shakli?

Bu savolga javob sirtda yotadi. Endi biz juda oddiy misolni ko'rib chiqdik, unda to'g'ri javob bor bir belgiga bog'liq . Siz buni hayotda tez-tez uchratmaysiz, shuning uchun bizda 2, 30, 50 yoki undan ortiq belgilar borligini tasavvur qilaylik. Keling, har bir atribut uchun minglab, hatto o'n minglab qiymatlarni qo'shamiz. Bunday holda, analitik yechim sinovga bardosh bermasligi va muvaffaqiyatsiz bo'lishi mumkin. O'z navbatida, gradient tushishi va uning o'zgarishi asta-sekin, lekin shubhasiz bizni maqsadga yaqinlashtiradi - funktsiyaning minimal darajasi. Va tezlik haqida tashvishlanmang - biz qadam uzunligini (ya'ni tezlikni) o'rnatish va tartibga solish imkonini beradigan usullarni ko'rib chiqamiz.

Va endi haqiqiy qisqacha xulosa.

Birinchidan, umid qilamanki, maqolada keltirilgan material boshlang'ich "ma'lumotlar olimlariga" oddiy (va nafaqat) chiziqli regressiya tenglamalarini qanday echishni tushunishda yordam beradi.

Ikkinchidan, biz tenglamani yechishning bir necha usullarini ko'rib chiqdik. Endi vaziyatga qarab, biz muammoni hal qilish uchun eng mos keladiganini tanlashimiz mumkin.

Uchinchidan, biz qo'shimcha sozlamalarning kuchini, ya'ni gradient tushish qadamining uzunligini ko'rdik. Ushbu parametrni e'tiborsiz qoldirib bo'lmaydi. Yuqorida ta'kidlab o'tilganidek, hisob-kitoblarning narxini pasaytirish uchun, tushish vaqtida qadam uzunligini o'zgartirish kerak.

To'rtinchidan, bizning holatlarimizda "uyda yozilgan" funktsiyalar hisob-kitoblar uchun eng yaxshi vaqt natijalarini ko'rsatdi. Bu, ehtimol, kutubxonaning imkoniyatlaridan eng professional tarzda foydalanilmaganligi bilan bog'liq numpy. Qanday bo'lmasin, quyidagi xulosa o'zini oqlaydi. Bir tomondan, ba'zida o'rnatilgan fikrlarni shubha ostiga qo'yishga arziydi, boshqa tomondan, har doim ham hamma narsani murakkablashtirishga arzimaydi - aksincha, ba'zida muammoni hal qilishning oddiy usuli samaraliroq bo'ladi. Va bizning maqsadimiz oddiy chiziqli regressiya tenglamasini echishning uchta yondashuvini tahlil qilish bo'lganligi sababli, biz uchun "o'z-o'zidan yozilgan" funktsiyalardan foydalanish etarli edi.

Adabiyot (yoki shunga o'xshash narsa)

1. Chiziqli regressiya

http://statistica.ru/theory/osnovy-lineynoy-regressii/

2. Eng kichik kvadratlar usuli

mathprofi.ru/metod_naimenshih_kvadratov.html

3. Hosil

www.mathprofi.ru/chastnye_proizvodnye_primery.html

4. Gradient

mathprofi.ru/proizvodnaja_po_napravleniju_i_gradient.html

5. Gradientning tushishi

habr.com/ru/post/471458

habr.com/ru/post/307312

artemarakcheev.com//2017-12-31/linear_regression

6. NumPy kutubxonasi

docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.linalg.solve.html

docs.scipy.org/doc/numpy-1.10.0/reference/generated/numpy.linalg.pinv.html

pythonworld.ru/numpy/2.html

Manba: www.habr.com