Крыніца:
Лінейная рэгрэсія з'яўляецца адным з базавых алгарытмаў для многіх абласцей, звязаных з аналізам даных. Чыннік гэтаму відавочная. Гэта вельмі просты і зразумелы алгарытм, што спрыяе яго шырокаму прымяненню ўжо многія дзясяткі, калі не сотні, гадоў. Ідэя заключаецца ў тым, што мы мяркуем лінейную залежнасць адной зменнай ад набору іншых зменных, а потым спрабуем гэтую залежнасць аднавіць.
Але ў гэтым артыкуле прамова пайдзе не пра ўжыванне лінейнай рэгрэсіі для рашэння практычных задач. Тут будуць разгледжаны цікавыя асаблівасці рэалізацыі размеркаваных алгарытмаў яе аднаўлення, з якімі мы сутыкнуліся пры напісанні модуля машыннага навучання . Трохі базавай матэматыкі, асноў машыннага навучання і размеркаваных вылічэнняў дапамогуць разабрацца, як аднаўляць лінейную рэгрэсію, нават калі дадзеныя размеркаваны паміж тысячамі вузлоў.
Аб чым гаворка?
Перад намі стаіць задача аднаўлення лінейнай залежнасці. У якасці ўваходных дадзеных даецца мноства вектараў меркавана незалежных зменных, кожнаму з якіх ставіцца ў адпаведнасць некаторае значэнне залежнай зменнай. Гэтыя дадзеныя можна прадставіць у выглядзе двух матрыц:
Зараз, раз ужо мяркуецца залежнасць, ды да таго ж яшчэ і лінейная, запішам нашу здагадку ў выглядзе твора матрыц (для спрашчэння запісу тут і далей мяркуецца, што вольны чалец раўнання хаваецца за , а апошні слупок матрыцы змяшчае адзінкі):
Вельмі падобна на сістэму лінейных раўнанняў, ці не так? Падобна, але рашэнняў у такой сістэмы раўнанняў хутчэй за ўсё не будзе. Чыннікам таму з'яўляецца шум, які прысутнічае практычна ў любых рэальных дадзеных. Гэтак жа чыннікам можа быць адсутнасць лінейнай залежнасці як такой, з якой можна спрабаваць дужацца ўвядзеннем дадатковых зменных, нелінейна якія залежаць ад зыходных. Разгледзім наступны прыклад:
Крыніца:
Гэта просты прыклад лінейнай рэгрэсіі, які дэманструе залежнасць адной зменнай (па восі ) ад іншай зменнай (па восі ). Каб якая адпавядае дадзенаму прыкладу сістэма лінейных раўнанняў мела рашэнне, усе кропкі павінны ляжаць сапраўды на адной прамой. Але гэта не так. А не ляжаць яны на адной прамой менавіта з-за шуму (ці з-за таго што здагадка аб наяўнасці лінейнай залежнасці было памылковым). Такім чынам, каб аднавіць лінейную залежнасць па рэальных дадзеных звычайна патрабуецца ўвесці яшчэ адна здагадка: уваходныя дадзеныя ўтрымоўваюць шум і гэты шум мае . Можна рабіць здагадкі і пра іншыя тыпы размеркавання шуму, але ў пераважнай большасці выпадкаў разглядаюць менавіта звычайнае размеркаванне, аб якім далей і пайдзе прамову.
Метад максімальнага праўдападабенства
Такім чынам, мы выказалі здагадку наяўнасць выпадковага нармальна размеркаванага шуму. Як жа быць у такой сытуацыі? На гэты выпадак у матэматыцы існуе і шырока выкарыстоўваецца . Калі коратка, яго сутнасць заключаецца ў выбары і наступнай яе максімізацыі.
Вяртаемся да аднаўлення лінейнай залежнасці па дадзеных са звычайным шумам. Заўважым, што меркаваная лінейная залежнасць з'яўляецца матэматычным чаканнем наяўнага нармальнага размеркавання. У той жа час, верагоднасць таго, што прымае тое ці іншае значэнне, пры ўмове наяўнасці назіраных , Выглядае наступным чынам:
Падставім зараз замест и патрэбныя нам зменныя:
Засталося толькі знайсці вектар , пры якім гэтая верагоднасць максімальная. Каб максымізаваць такую функцыю зручна спачатку яе пралагаарыфмаваць (лагарыфм функцыі будзе дасягаць максімуму ў той жа кропцы, што і сама функцыя):
Што, у сваю чаргу, зводзіцца да мінімізацыі наступнай функцыі:
Дарэчы, гэта называецца метадам . Часцяком усе прыведзеныя вышэй развагі апускаюцца і проста выкарыстоўваецца гэты метад.
QR разлажэнне
Мінімум прыведзенай вышэй функцыі можна знайсці, калі знайсці кропку ў якой градыент гэтай функцыі роўны нулю. А градыент будзе запісаны наступным чынам:
з'яўляецца матрычным метадам рашэння задачы мінімізацыі выкарыстоўваным у метадзе найменшых квадратаў. У сувязі з гэтым перапішам раўнанне ў матрычнай форме:
Такім чынам, мы раскладваем матрыцу на матрыцы и і выконваем шэраг пераўтварэнняў (сам алгарытм QR раскладання тут разглядацца не будзе, толькі яго выкарыстанне ў дачыненні да пастаўленай задачы):
матрыца з'яўляецца артаганальнай. Гэта дазваляе нам пазбавіцца ад твора. :
А калі замяніць на , то атрымаецца . Улічваючы, што з'яўляецца верхняй трохкутнай матрыцай, выглядае гэта наступным чынам:
Гэта можна вырашаць метадам падстаноўкі. Элемент знаходзіцца як , папярэдні элемент знаходзіцца як і гэтак далей.
Тут варта адзначыць, што складанасць атрыманага алгарытму за рахунак выкарыстання QR раскладання роўная . Пры гэтым, нягледзячы на тое, што аперацыя множання матрыц добра распаралельваецца, напісаць эфектыўную размеркаваную версію гэтага алгарытму не ўяўляецца магчымым.
Градыентны спуск
Кажучы аб мінімізацыі некаторай функцыі, заўсёды варта ўспамінаць метад (стахастычнага) градыентнага спуску. Гэта просты і эфектыўны метад мінімізацыі, заснаваны на ітэратыўнай вылічэнні градыенту функцыі ў кропцы і наступным яе зняцці ў бок, процілеглы градыенту. Кожны такі крок набліжае рашэнне да мінімуму. Градыент пры гэтым выглядае ўсё гэтак жа:
Яшчэ гэты метад добра распаралельваецца і размяркоўваецца за кошт лінейных уласцівасцяў аператара градыенту. Заўважым, што ў прыведзенай вышэй формуле пад знакам сумы знаходзяцца незалежныя складнікі. Іншымі словамі, мы можам палічыць градыент незалежна для ўсіх азначнікаў з першага да , паралельна з гэтым палічыць градыент для індэксаў з да . Затым скласці атрыманыя градыенты. Вынікам складання будзе такім жа, як калі б мы палічылі адразу градыент для азначнікаў з першага да . Такім чынам, калі дадзеныя размеркаваны паміж некалькімі часткамі дадзеных, градыент можа быць вылічаны незалежна на кожнай частцы, а затым вынікі гэтых вылічэнняў могуць быць прасумаваны для атрымання канчатковага выніку:
З пункту гледжання рэалізацыі, гэта ўкладваецца ў парадыгму. . На кожным кроку градыентнага спуску на кожны вузел дадзеных адпраўляецца заданне на вылічэнне градыенту, затым вылічаныя градыенты збіраюцца разам, і вынік іх сумавання выкарыстоўваецца для паляпшэння выніку.
Нягледзячы на прастату рэалізацыі і магчымасць выканання ў парадыгме MapReduce градыентны спуск валодае і сваімі недахопамі. У прыватнасці, колькасць крокаў, неабходнае для дасягнення збежнасці, істотна большая ў параўнанні з іншымі больш спецыялізаванымі метадамі.
LSQR
- Яшчэ адзін метад рашэння пастаўленай задачы, які падыходзіць як для аднаўлення лінейнай рэгрэсіі, так і для вырашэння сістэм лінейных раўнанняў. Яго галоўная асаблівасць заключаецца ў тым, што ён сумяшчае ў сабе перавагі матрычных метадаў і ітэратыўнага падыходу. Рэалізацыі гэтага метаду можна знайсці як у бібліятэцы , Так і ў . Апісанне дадзенага метаду прыводзіцца тут не будзе (яго можна знайсці ў артыкуле ). Замест гэтага будзе прадэманстраваны падыход, які дазваляе адаптаваць LSQR да выканання ў размеркаваным асяроддзі.
У аснове метаду LSQR ляжыць . Гэта ітэратыўная працэдура, кожная ітэрацыя якой складаецца з наступных крокаў:
Але калі зыходзіць з таго, што матрыца гарызантальна партыцыянавана, то кожную ітэрацыю можна прадставіць у выглядзе двух крокаў MapReduce. Такім чынам атрымоўваецца мінімізаваць перасыланнямі дадзеных падчас кожнай з ітэрацый (толькі вектара даўжынёй роўнай колькасці невядомых):
Менавіта гэты падыход выкарыстоўваецца пры рэалізацыі лінейнай рэгрэсіі ў .
Заключэнне
Існуе шмат алгарытмаў аднаўлення лінейнай рэгрэсіі, але не ўсе з іх могуць прымяняцца ў любых умовах. Так QR разлажэнне выдатна падыходзіць для дакладнага рашэння на невялікіх масівах дадзеных. Градыентны спуск проста рэалізуецца і дазваляе хутка знайсці набліжанае рашэнне. А LSQR спалучае ў сабе лепшыя ўласцівасці папярэдніх двух алгарытмаў, бо ён можа быць размеркаваны, хутчэй збягаецца ў параўнанні з градыентным спускам, а гэтак жа дазваляе ранні прыпынак алгарытму ў адрозненне ад QR-раскладання для пошуку набліжанага рашэння.
Крыніца: habr.com