Pinagmulan:
Ang linear regression ay isa sa mga pangunahing algorithm para sa maraming lugar na nauugnay sa pagsusuri ng data. Ang dahilan nito ay maliwanag. Ito ay isang napakasimple at nauunawaan na algorithm, na nag-ambag sa malawakang paggamit nito sa loob ng maraming sampu, kung hindi man daan-daang taon. Ang ideya ay ipinapalagay namin ang isang linear na dependence ng isang variable sa isang set ng iba pang mga variable, at pagkatapos ay subukang ibalik ang dependence na ito.
Ngunit ang artikulong ito ay hindi tungkol sa paggamit ng linear regression upang malutas ang mga praktikal na problema. Dito ay isasaalang-alang namin ang mga kagiliw-giliw na tampok ng pagpapatupad ng mga ipinamahagi na algorithm para sa pagbawi nito, na nakatagpo namin noong sumulat ng isang module sa pag-aaral ng machine sa . Ang isang maliit na pangunahing matematika, machine learning, at distributed computing ay makakatulong sa iyong malaman kung paano magsagawa ng linear regression kahit na ang iyong data ay ipinamahagi sa libu-libong node.
Tungkol Saan yan?
Kami ay nahaharap sa gawain ng pagpapanumbalik ng linear dependence. Bilang data ng pag-input, ibinibigay ang isang hanay ng mga vector ng diumano'y independyenteng mga variable, na ang bawat isa ay nauugnay sa isang tiyak na halaga ng dependent variable. Ang data na ito ay maaaring kinakatawan sa anyo ng dalawang matrice:
Ngayon, dahil ang pag-asa ay ipinapalagay, at, bukod dito, linear, isusulat namin ang aming palagay sa anyo ng isang produkto ng mga matrice (upang gawing simple ang pag-record, dito at sa ibaba ay ipinapalagay na ang libreng termino ng equation ay nakatago sa likod , at ang huling column ng matrix naglalaman ng mga yunit):
Parang isang sistema ng mga linear equation, hindi ba? Tila, ngunit malamang na walang mga solusyon sa gayong sistema ng mga equation. Ang dahilan nito ay ingay, na naroroon sa halos anumang totoong data. Ang isa pang dahilan ay maaaring ang kakulangan ng linear dependence, na maaaring labanan sa pamamagitan ng pagpapakilala ng mga karagdagang variable na hindi linear na nakadepende sa mga orihinal. Isaalang-alang ang sumusunod na halimbawa:
Pinagmulan:
Ito ay isang simpleng halimbawa ng linear regression na nagpapakita ng relasyon ng isang variable (kasama ang axis ) mula sa isa pang variable (kasama ang axis ). Upang ang sistema ng mga linear na equation na tumutugma sa halimbawang ito ay magkaroon ng solusyon, ang lahat ng mga punto ay dapat na eksaktong nasa parehong tuwid na linya. Ngunit hindi iyon totoo. Ngunit hindi sila nakahiga sa parehong tuwid na linya nang tumpak dahil sa ingay (o dahil ang pagpapalagay ng isang linear na relasyon ay mali). Kaya, upang maibalik ang isang linear na relasyon mula sa totoong data, kadalasang kinakailangan na ipakilala ang isa pang palagay: ang data ng input ay naglalaman ng ingay at ang ingay na ito ay may. . Maaari kang gumawa ng mga pagpapalagay tungkol sa iba pang mga uri ng pamamahagi ng ingay, ngunit sa karamihan ng mga kaso ito ay ang normal na pamamahagi na isinasaalang-alang, na tatalakayin pa.
Paraan ng maximum na posibilidad
Kaya, ipinapalagay namin ang pagkakaroon ng random na normal na ipinamamahagi na ingay. Ano ang gagawin sa ganoong sitwasyon? Para sa kasong ito sa matematika mayroong at malawakang ginagamit . Sa madaling salita, ang kakanyahan nito ay nakasalalay sa pagpili at ang kasunod na pag-maximize nito.
Bumalik kami sa pagpapanumbalik ng isang linear na relasyon mula sa data na may normal na ingay. Tandaan na ang ipinapalagay na linear na relasyon ay ang mathematical na inaasahan umiiral na normal na distribusyon. Kasabay nito, ang posibilidad na tumatagal sa isang halaga o iba pa, napapailalim sa pagkakaroon ng mga napapansin , mukhang sumusunod:
Sa halip, palitan natin ΠΈ Ang mga variable na kailangan namin ay:
Ang natitira na lang ay hanapin ang vector , kung saan ang posibilidad na ito ay pinakamataas. Upang i-maximize ang naturang function, maginhawang kumuha muna ng logarithm nito (ang logarithm ng function ay aabot sa maximum sa parehong punto ng function mismo):
Na, sa turn, ay bumababa sa pagliit ng sumusunod na function:
Sa pamamagitan ng paraan, ito ay tinatawag na isang pamamaraan . Kadalasan ang lahat ng mga pagsasaalang-alang sa itaas ay tinanggal at ang pamamaraang ito ay ginagamit lamang.
QR decomposition
Ang pinakamababa ng function sa itaas ay matatagpuan sa pamamagitan ng paghahanap ng punto kung saan ang gradient ng function na ito ay zero. At ang gradient ay isusulat tulad ng sumusunod:
ay isang pamamaraan ng matrix para sa paglutas ng problema sa pag-minimize na ginamit sa pamamaraang least squares. Kaugnay nito, muling isinulat namin ang equation sa matrix form:
Kaya nabubulok namin ang matrix sa matrices ΠΈ at magsagawa ng isang serye ng mga pagbabagong-anyo (ang QR decomposition algorithm mismo ay hindi isasaalang-alang dito, ang paggamit lamang nito kaugnay sa gawaing nasa kamay):
matris ay orthogonal. Ito ay nagpapahintulot sa amin na mapupuksa ang trabaho :
At kung papalitan mo sa , pagkatapos ay gagana ito . Isinasaalang-alang na ay isang upper triangular matrix, ganito ang hitsura:
Ito ay maaaring malutas gamit ang paraan ng pagpapalit. Elemento ay matatagpuan bilang , nakaraang elemento ay matatagpuan bilang at iba pa.
Kapansin-pansin dito na ang pagiging kumplikado ng resultang algorithm dahil sa paggamit ng QR decomposition ay katumbas ng . Bukod dito, sa kabila ng katotohanan na ang operasyon ng pagpaparami ng matrix ay mahusay na parallelized, hindi posible na magsulat ng isang epektibong ipinamamahagi na bersyon ng algorithm na ito.
Gradient Descent
Kapag pinag-uusapan ang pag-minimize ng isang function, palaging sulit na alalahanin ang paraan ng (stochastic) gradient descent. Ito ay isang simple at epektibong paraan ng minimization batay sa paulit-ulit na pagkalkula ng gradient ng isang function sa isang punto at pagkatapos ay inililipat ito sa direksyon na kabaligtaran sa gradient. Ang bawat hakbang na ito ay naglalapit sa solusyon sa pinakamababa. Ang gradient ay mukhang pareho pa rin:
Ang pamamaraang ito ay mahusay din parallelized at ipinamamahagi dahil sa mga linear na katangian ng gradient operator. Tandaan na sa formula sa itaas, sa ilalim ng sum sign ay may mga independiyenteng termino. Sa madaling salita, maaari nating kalkulahin ang gradient nang nakapag-iisa para sa lahat ng mga indeks mula sa una hanggang , kaayon nito, kalkulahin ang gradient para sa mga indeks na may sa . Pagkatapos ay idagdag ang mga nagresultang gradients. Ang resulta ng karagdagan ay magiging kapareho ng kung agad naming kinakalkula ang gradient para sa mga indeks mula sa una hanggang . Kaya, kung ang data ay ibinahagi sa ilang piraso ng data, ang gradient ay maaaring kalkulahin nang nakapag-iisa sa bawat piraso, at pagkatapos ay ang mga resulta ng mga kalkulasyong ito ay maaaring isama upang makuha ang pangwakas na resulta:
Mula sa isang punto ng pagpapatupad ng view, ito ay akma sa paradigm . Sa bawat hakbang ng gradient descent, isang gawain ang ipinapadala sa bawat data node upang kalkulahin ang gradient, pagkatapos ay ang mga nakalkulang gradient ay sama-samang kinokolekta, at ang resulta ng kanilang kabuuan ay ginagamit upang mapabuti ang resulta.
Sa kabila ng kadalian ng pagpapatupad at kakayahang magsagawa sa paradigm ng MapReduce, may mga kakulangan din ang gradient descent. Sa partikular, ang bilang ng mga hakbang na kinakailangan upang makamit ang convergence ay makabuluhang mas mataas kumpara sa iba pang mas espesyal na mga pamamaraan.
LSQR
ay isa pang paraan para sa paglutas ng problema, na angkop kapwa para sa pagpapanumbalik ng linear regression at para sa paglutas ng mga sistema ng linear equation. Ang pangunahing tampok nito ay pinagsasama nito ang mga pakinabang ng mga pamamaraan ng matrix at isang umuulit na diskarte. Ang mga pagpapatupad ng paraang ito ay matatagpuan sa parehong mga aklatan , at sa . Ang isang paglalarawan ng paraang ito ay hindi ibibigay dito (matatagpuan ito sa artikulo ). Sa halip, isang diskarte ang ipapakita upang iakma ang LSQR sa pagpapatupad sa isang distributed na kapaligiran.
Ang pamamaraan ng LSQR ay batay sa . Ito ay isang umuulit na pamamaraan, ang bawat pag-ulit ay binubuo ng mga sumusunod na hakbang:
Ngunit kung ipagpalagay natin na ang matrix ay pahalang na nahahati, pagkatapos ang bawat pag-ulit ay maaaring katawanin bilang dalawang hakbang sa MapReduce. Sa ganitong paraan, posibleng mabawasan ang paglilipat ng data sa bawat pag-ulit (mga vector lang na may haba na katumbas ng bilang ng mga hindi alam):
Ito ang diskarteng ito na ginagamit kapag nagpapatupad ng linear regression sa .
Konklusyon
Mayroong maraming mga linear regression recovery algorithm, ngunit hindi lahat ng mga ito ay maaaring ilapat sa lahat ng mga kondisyon. Kaya ang QR decomposition ay mahusay para sa tumpak na solusyon sa maliliit na set ng data. Ang gradient descent ay simpleng ipatupad at nagbibigay-daan sa iyong mabilis na makahanap ng tinatayang solusyon. At pinagsasama ng LSQR ang pinakamahusay na mga katangian ng nakaraang dalawang algorithm, dahil maaari itong maipamahagi, mas mabilis na mag-converge kumpara sa gradient descent, at pinapayagan din ang maagang paghinto ng algorithm, hindi tulad ng QR decomposition, upang makahanap ng tinatayang solusyon.
Pinagmulan: www.habr.com