Manba:
Chiziqli regressiya ma'lumotlarni tahlil qilish bilan bog'liq ko'plab sohalar uchun asosiy algoritmlardan biridir. Buning sababi aniq. Bu juda oddiy va tushunarli algoritm bo'lib, uning ko'p o'nlab, balki yuzlab yillar davomida keng qo'llanilishiga hissa qo'shgan. G'oya shundan iboratki, biz bir o'zgaruvchining boshqa o'zgaruvchilar to'plamiga chiziqli bog'liqligini qabul qilamiz va keyin bu bog'liqlikni tiklashga harakat qilamiz.
Ammo bu maqola amaliy muammolarni hal qilish uchun chiziqli regressiyadan foydalanish haqida emas. Bu erda biz mashinani o'rganish modulini yozishda duch kelgan uni qayta tiklash uchun taqsimlangan algoritmlarni amalga oshirishning qiziqarli xususiyatlarini ko'rib chiqamiz. . Bir oz oddiy matematika, mashinani o'rganish va taqsimlangan hisoblash sizning ma'lumotlaringiz minglab tugunlar bo'ylab taqsimlanganda ham chiziqli regressiyani qanday amalga oshirishni aniqlashga yordam beradi.
Biz nima haqida gapiryapmiz?
Bizning oldimizda chiziqli qaramlikni tiklash vazifasi turibdi. Kirish ma'lumotlari sifatida har biri bog'liq o'zgaruvchining ma'lum bir qiymati bilan bog'liq bo'lgan mustaqil o'zgaruvchilarning vektorlari to'plami berilgan. Ushbu ma'lumotlar ikkita matritsa shaklida ifodalanishi mumkin:
Endi, qaramlik qabul qilinganligi sababli, va bundan tashqari, chiziqli, biz taxminimizni matritsalar mahsuloti shaklida yozamiz (yozishni soddalashtirish uchun bu erda va quyida tenglamaning erkin muddati orqasida yashiringan deb taxmin qilinadi. 
, va matritsaning oxirgi ustuni 
birliklarni o'z ichiga oladi):
Chiziqli tenglamalar tizimiga juda o'xshaydi, shunday emasmi? Ko'rinadi, lekin, ehtimol, bunday tenglamalar tizimiga hech qanday yechim bo'lmaydi. Buning sababi deyarli har qanday haqiqiy ma'lumotlarda mavjud bo'lgan shovqin. Yana bir sabab chiziqli bog'liqlikning yo'qligi bo'lishi mumkin, bu asl o'zgaruvchilarga nochiziqli bog'liq bo'lgan qo'shimcha o'zgaruvchilarni kiritish orqali kurashish mumkin. Quyidagi misolni ko'rib chiqing:
Manba:
Bu bitta o'zgaruvchining (o'q bo'ylab) munosabatini ko'rsatadigan chiziqli regressiyaning oddiy misolidir 
) boshqa o'zgaruvchidan (o'q bo'ylab 
). Bu misolga mos chiziqli tenglamalar sistemasi yechimga ega bo'lishi uchun barcha nuqtalar aynan bir xil to'g'ri chiziqda yotishi kerak. Ammo bu unday emas. Ammo ular shovqin tufayli (yoki chiziqli munosabatlar haqidagi taxmin noto'g'ri bo'lganligi sababli) bir xil to'g'ri chiziqda yotmaydilar. Shunday qilib, haqiqiy ma'lumotlardan chiziqli munosabatlarni tiklash uchun odatda yana bitta taxminni kiritish kerak: kirish ma'lumotlari shovqinni o'z ichiga oladi va bu shovqin bor . Siz shovqin taqsimotining boshqa turlari haqida taxminlar qilishingiz mumkin, ammo aksariyat hollarda bu oddiy taqsimot hisoblanadi, bundan keyin ham muhokama qilinadi.
Maksimal ehtimollik usuli
Shunday qilib, biz tasodifiy normal taqsimlangan shovqin mavjudligini taxmin qildik. Bunday vaziyatda nima qilish kerak? Bu holat uchun matematikada mavjud va keng qo'llaniladi . Muxtasar qilib aytganda, uning mohiyati tanlovda yotadi va undan keyingi maksimallashtirish.
Oddiy shovqin bilan ma'lumotlardan chiziqli munosabatlarni tiklashga qaytamiz. E'tibor bering, taxmin qilingan chiziqli munosabatlar matematik kutishdir 
mavjud normal taqsimot. Shu bilan birga, ehtimollik 
kuzatilishi mumkin bo'lgan narsalar mavjudligi sharti bilan u yoki bu qiymatni oladi 
, quyidagicha:
Keling, uning o'rniga almashtiraylik 
и 
Bizga kerak bo'lgan o'zgaruvchilar:
Faqat vektorni topish qoladi 
, bunda bu ehtimollik maksimal bo'ladi. Bunday funktsiyani maksimal darajaga ko'tarish uchun avval uning logarifmini olish qulay (funktsiyaning logarifmi funktsiyaning o'zi bilan bir xil nuqtada maksimalga etadi):
Bu, o'z navbatida, quyidagi funktsiyani minimallashtirishga olib keladi:
Aytgancha, bu usul deb ataladi . Ko'pincha yuqoridagi barcha fikrlar o'tkazib yuboriladi va bu usul oddiygina qo'llaniladi.
QR parchalanishi
Yuqoridagi funktsiyaning minimalini ushbu funktsiyaning gradienti nolga teng bo'lgan nuqtasini topish orqali topish mumkin. Va gradient quyidagicha yoziladi:
eng kichik kvadratlar usulida qo'llaniladigan minimallashtirish masalasini yechishning matritsa usulidir. Shu munosabat bilan biz tenglamani matritsa shaklida qayta yozamiz:
Shunday qilib, biz matritsani ajratamiz 
matritsalarga 
и 
va bir qator o'zgarishlarni amalga oshiring (bu erda QR dekompozitsiya algoritmining o'zi ko'rib chiqilmaydi, faqat uning vazifaga nisbatan qo'llanilishi):
Matritsa 
ortogonaldir. Bu bizga ishdan xalos bo'lishga imkon beradi 
:
Va agar siz almashtirsangiz 
haqida 
, keyin u ishlaydi 
. Shuni hisobga olib 
yuqori uchburchak matritsa bo'lib, u quyidagicha ko'rinadi:
Buni almashtirish usuli yordamida hal qilish mumkin. Element 
sifatida joylashgan 
, oldingi element 
sifatida joylashgan 
va hokazo.
Shuni ta'kidlash kerakki, QR parchalanishidan foydalanish natijasida olingan algoritmning murakkabligi tengdir. 
. Bundan tashqari, matritsani ko'paytirish operatsiyasi yaxshi parallellashtirilganiga qaramay, ushbu algoritmning samarali taqsimlangan versiyasini yozish mumkin emas.
Gradient tushishi
Funktsiyani minimallashtirish haqida gapirganda, har doim (stokastik) gradient tushish usulini esga olish kerak. Bu nuqtada funksiyaning gradientini iterativ tarzda hisoblash va keyin uni gradientga qarama-qarshi tomonga siljitishga asoslangan oddiy va samarali minimallashtirish usuli. Har bir bunday qadam yechimni minimal darajaga yaqinlashtiradi. Gradient hali ham bir xil ko'rinadi:
Bu usul ham gradient operatorining chiziqli xossalari tufayli yaxshi parallellashtirilgan va taqsimlangan. E'tibor bering, yuqoridagi formulada yig'indi belgisi ostida mustaqil atamalar mavjud. Boshqacha qilib aytganda, biz barcha indekslar uchun gradientni mustaqil ravishda hisoblashimiz mumkin 
birinchidan 
, bunga parallel ravishda indekslar uchun gradientni hisoblang 
uchun 
. Keyin olingan gradientlarni qo'shing. Qo'shish natijasi xuddi birinchidan boshlab indekslar uchun gradientni darhol hisoblagandek bo'ladi 
. Shunday qilib, agar ma'lumotlar bir nechta ma'lumotlar bo'laklari orasida taqsimlangan bo'lsa, gradient har bir bo'lak bo'yicha mustaqil ravishda hisoblab chiqilishi mumkin, so'ngra yakuniy natijani olish uchun ushbu hisob-kitoblarning natijalarini jamlash mumkin:
Amalga oshirish nuqtai nazaridan, bu paradigmaga mos keladi . Gradient tushishining har bir bosqichida gradientni hisoblash uchun har bir ma'lumot tuguniga topshiriq yuboriladi, so'ngra hisoblangan gradientlar birgalikda yig'iladi va natijani yaxshilash uchun ularning yig'indisidan foydalaniladi.
Amalga oshirish qulayligi va MapReduce paradigmasida bajarish qobiliyatiga qaramay, gradient tushishi ham o'zining kamchiliklariga ega. Xususan, konvergentsiyaga erishish uchun zarur bo'lgan qadamlar soni boshqa ixtisoslashgan usullar bilan solishtirganda sezilarli darajada yuqori.
LSQR
chiziqli regressiyani tiklash uchun ham, chiziqli tenglamalar tizimini echish uchun ham mos keladigan muammoni hal qilishning yana bir usuli. Uning asosiy xususiyati shundaki, u matritsali usullarning afzalliklarini va iterativ yondashuvni birlashtiradi. Ushbu usulning qo'llanilishini ikkala kutubxonada ham topish mumkin , va . Ushbu usulning tavsifi bu erda berilmaydi (uni maqolada topish mumkin ). Buning o'rniga, LSQRni taqsimlangan muhitda bajarishga moslashtirish uchun yondashuv namoyish etiladi.
LSQR usuli quyidagilarga asoslanadi . Bu iterativ protsedura bo'lib, har bir iteratsiya quyidagi bosqichlardan iborat:
Ammo matritsa deb faraz qilsak 
gorizontal bo'lingan bo'lsa, har bir iteratsiya ikkita MapReduce qadami sifatida ifodalanishi mumkin. Shunday qilib, har bir iteratsiya davomida ma'lumotlar uzatishni minimallashtirish mumkin (faqat uzunliklari noma'lumlar soniga teng bo'lgan vektorlar):
Aynan shu yondashuv chiziqli regressiyani amalga oshirishda qo'llaniladi .
xulosa
Chiziqli regressiyani tiklash algoritmlari ko'p, ammo ularning hammasi ham barcha sharoitlarda qo'llanilishi mumkin emas. Shunday qilib, QR parchalanishi kichik ma'lumotlar to'plamlarida aniq yechim uchun juda yaxshi. Gradient tushishini amalga oshirish oson va sizga taxminiy yechimni tezda topish imkonini beradi. Va LSQR oldingi ikkita algoritmning eng yaxshi xususiyatlarini birlashtiradi, chunki u taqsimlanishi mumkin, gradient tushishiga nisbatan tezroq birlashadi va shuningdek, taxminiy yechim topish uchun QR parchalanishidan farqli o'laroq, algoritmni erta to'xtatishga imkon beradi.
Manba: www.habr.com
