{"id":37955,"date":"2019-10-31T22:20:47","date_gmt":"2019-10-31T19:20:47","guid":{"rendered":"https:\/\/prohoster.info\/blog\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya\/"},"modified":"2019-10-31T22:20:47","modified_gmt":"2019-10-31T19:20:47","slug":"linejnaya-regressiya-i-metody-eyo-vosstanovleniya","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya","title":{"rendered":"Regresja liniowa i metody jej rekonstrukcji","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/60ca67872405e9f15b151e958f04260d.png\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>\u0179r\u00f3d\u0142o: <noindex><a rel=\"nofollow\" href=\"https:\/\/xkcd.com\/1725\/\">xkcd<\/a><\/noindex><\/i><\/p>\n<p>Regresja liniowa to jeden z podstawowych algorytm\u00f3w w wielu dziedzinach zwi\u0105zanych z analiz\u0105 danych. Pow\u00f3d jest oczywisty. Jest to bardzo prosty i zrozumia\u0142y algorytm, co przyczynia si\u0119 do jego szerokiego zastosowania od dziesi\u0119cioleci, je\u015bli nie setek lat. Idea polega na za\u0142o\u017ceniu liniowej zale\u017cno\u015bci jednej zmiennej od zestawu innych zmiennych, a nast\u0119pnie pr\u00f3b\u0119 odtworzenia tej zale\u017cno\u015bci.<\/p>\n<p>Jednak w tym artykule nie b\u0119dziemy m\u00f3wi\u0107 o zastosowaniu regresji liniowej do rozwi\u0105zywania praktycznych problem\u00f3w. Skoncentrujemy si\u0119 na interesuj\u0105cych aspektach realizacji rozproszonych algorytm\u00f3w jej rekonstrukcji, z kt\u00f3rymi zetkn\u0119li\u015bmy si\u0119 podczas pisania modu\u0142u uczenia maszynowego w <noindex><a rel=\"nofollow\" href=\"https:\/\/ignite.apache.org\/\">Apache Ignite<\/a><\/noindex>. Troch\u0119 podstawowej matematyki, zasad uczenia maszynowego oraz oblicze\u0144 rozproszonych pomo\u017ce zrozumie\u0107, jak rekonstruowa\u0107 regresj\u0119 liniow\u0105, nawet gdy dane s\u0105 rozproszone mi\u0119dzy tysi\u0105cami w\u0119z\u0142\u00f3w.<br \/>\n<noindex><a rel=\"nofollow\" name=\"habracut\"><\/a><\/noindex><\/p>\n<h3>O co chodzi?<\/h3>\n<p>\nPrzed nami zadanie odzyskania liniowej zale\u017cno\u015bci. Jako dane wej\u015bciowe otrzymujemy zbi\u00f3r wektor\u00f3w przypuszczalnie niezale\u017cnych zmiennych, kt\u00f3rym przypisuje si\u0119 pewne warto\u015bci zmiennej zale\u017cnej. Te dane mo\u017cna przedstawi\u0107 w postaci dw\u00f3ch macierzy:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/2ffbdd09fdc5efaf287fbb4935033302.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nTeraz, skoro zak\u0142adamy zale\u017cno\u015b\u0107, a do tego liniow\u0105, zapiszmy nasze przypuszczenie w postaci iloczynu macierzy (dla uproszczenia zapisu w tym i kolejnych przypadkach zak\u0142ada si\u0119, \u017ce cz\u0142on wolny r\u00f3wnania jest ukryty za <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/21e90cb829e0bc2e12c836f7810c1b1a.png\" style=\"display:block;margin: 0 auto;\" \/>, a ostatnia kolumna macierzy <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/25c0af2e153ae371e71588efe3bc2ee2.png\" style=\"display:block;margin: 0 auto;\" \/> zawiera jedynki):<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/b1c3c8d2332ae27eedeef675178dee4f.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nBardzo podobne do systemu r\u00f3wna\u0144 liniowych, prawda? Podobne, ale system ten najprawdopodobniej nie ma rozwi\u0105za\u0144. Przyczyn\u0105 jest szum, kt\u00f3ry wyst\u0119puje praktycznie w ka\u017cdych rzeczywistych danych. Inn\u0105 przyczyn\u0105 mo\u017ce by\u0107 brak liniowej zale\u017cno\u015bci jako takiej, z kt\u00f3r\u0105 mo\u017cna pr\u00f3bowa\u0107 walczy\u0107, wprowadzaj\u0105c dodatkowe zmienne, nieliniowo zale\u017cne od pocz\u0105tkowych. Rozwa\u017cmy nast\u0119puj\u0105cy przyk\u0142ad:<br \/>\n<img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/d449b8f931e91cc7b33634ee8d4a4329.png\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<i>\u0179r\u00f3d\u0142o: <noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Linear_regression\">Wikipedia<\/a><\/noindex><\/i><\/p>\n<p>To prosty przyk\u0142ad regresji liniowej, kt\u00f3ry demonstruje zale\u017cno\u015b\u0107 jednej zmiennej (po osi <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/fdea97dff413fb13444d7fd8ab65ca0b.png\" style=\"display:block;margin: 0 auto;\" \/>) od innej zmiennej (w kierunku <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/edf9cb265e4e4655cd84fb8739843952.png\" style=\"display:block;margin: 0 auto;\" \/>). Aby odpowiedni uk\u0142ad r\u00f3wna\u0144 liniowych mia\u0142 rozwi\u0105zanie, wszystkie punkty musz\u0105 le\u017ce\u0107 dok\u0142adnie na jednej prostej. Ale tak nie jest. A nie le\u017c\u0105 na jednej prostej w\u0142a\u015bnie z powodu szumu (lub dlatego, \u017ce za\u0142o\u017cenie o istnieniu liniowej zale\u017cno\u015bci by\u0142o b\u0142\u0119dne). W zwi\u0105zku z tym, aby przywr\u00f3ci\u0107 liniow\u0105 zale\u017cno\u015b\u0107 na podstawie rzeczywistych danych, zazwyczaj trzeba wprowadzi\u0107 jeszcze jedno za\u0142o\u017cenie: dane wej\u015bciowe zawieraj\u0105 szum i ten szum ma <noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Normal_distribution\">roz\u0142o\u017cenie normalne<\/a><\/noindex>. Mo\u017cna r\u00f3wnie\u017c formu\u0142owa\u0107 za\u0142o\u017cenia dotycz\u0105ce innych typ\u00f3w rozk\u0142ad\u00f3w szumu, ale w przewa\u017caj\u0105cej wi\u0119kszo\u015bci przypadk\u00f3w rozwa\u017ca si\u0119 w\u0142a\u015bnie rozk\u0142ad normalny, o kt\u00f3rym mowa b\u0119dzie dalej.<\/p>\n<h3>Metoda najwi\u0119kszej wiarygodno\u015bci<\/h3>\n<p>\nZatem za\u0142o\u017cyli\u015bmy obecno\u015b\u0107 losowego szumu roz\u0142o\u017conego normalnie. Co zatem zrobi\u0107 w takiej sytuacji? Na ten przypadek w matematyce istnieje i jest szeroko stosowana <noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Maximum_likelihood_estimation\">metoda najwi\u0119kszej wiarygodno\u015bci<\/a><\/noindex>. M\u00f3wi\u0105c kr\u00f3tko, jej istota polega na wyborze <noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Likelihood_function\">funkcji wiarygodno\u015bci<\/a><\/noindex> i jej maksymalizacji.<\/p>\n<p>Wracamy do przywracania liniowej zale\u017cno\u015bci na podstawie danych z normalnym szumem. Zauwa\u017cmy, \u017ce zak\u0142adana liniowa zale\u017cno\u015b\u0107 jest matematycznym oczekiwaniem <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/73cd24a6605bce1a4f38339ee8c61613.png\" style=\"display:block;margin: 0 auto;\" \/> istniej\u0105cego rozk\u0142adu normalnego. Jednocze\u015bnie prawdopodobie\u0144stwo, \u017ce <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/caaf32b1af58d748244acbab640bbab8.png\" style=\"display:block;margin: 0 auto;\" \/> przyjmuje okre\u015blon\u0105 warto\u015b\u0107, pod warunkiem, \u017ce istniej\u0105 obserwowalne <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/9cda87721bba4812b7cec96f204ff5f6.png\" style=\"display:block;margin: 0 auto;\" \/>, wygl\u0105da w nast\u0119puj\u0105cy spos\u00f3b:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/7acbd6bff263d52773617904d3249a96.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nPodstawmy teraz zamiast <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/d5a167a87fa416e938678b2a80b353dc.png\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/330ad17be2629a5159b513ba95a96c72.png\" style=\"display:block;margin: 0 auto;\" \/> potrzebne nam zmienne:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/57531f93ee0d0050b1fbfc64419f44ad.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nPozostaje tylko znale\u017a\u0107 wektor <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/801ebcd43ae0bc0cf54bc0f68bdc21da.png\" style=\"display:block;margin: 0 auto;\" \/>, dla kt\u00f3rego to prawdopodobie\u0144stwo jest maksymalne. Aby zmaksymalizowa\u0107 tak\u0105 funkcj\u0119, wygodnie jest najpierw j\u0105 prze\u0142o\u017cy\u0107 na logarytm (logarytm funkcji osi\u0105gnie maksimum w tym samym punkcie, co sama funkcja):<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/7485448a44f8ee201254fea4208deb54.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nCo z kolei sprowadza si\u0119 do minimalizacji nast\u0119puj\u0105cej funkcji:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/0957864e5dfbfc1147c24784df67af20.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nZreszt\u0105 to nazywa si\u0119 metod\u0105 <noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/Linear_least_squares\">najmniejszych kwadrat\u00f3w<\/a><\/noindex>. Cz\u0119sto wszystkie powy\u017csze rozwa\u017cania s\u0105 pomijane i po prostu stosuje si\u0119 t\u0119 metod\u0119.<\/p>\n<h3>Rozk\u0142ad QR<\/h3>\n<p>\nMinimum powy\u017cszej funkcji mo\u017cna znale\u017a\u0107, je\u015bli znajdziemy punkt, w kt\u00f3rym gradient tej funkcji jest r\u00f3wny zero. A gradient b\u0119dzie zapisany w nast\u0119puj\u0105cy spos\u00f3b:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/1581c46f8fa625826ae2f76ec561dc3f.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/QR_decomposition\">Rozk\u0142ad QR<\/a><\/noindex> jest metod\u0105 macierzow\u0105 rozwi\u0105zywania problemu minimalizacji, wykorzystywan\u0105 w metodzie najmniejszych kwadrat\u00f3w. W zwi\u0105zku z tym przepiszemy r\u00f3wnanie w formie macierzowej:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/4ee809a96550577df855fbd57049a41c.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nZatem rozk\u0142adamy macierz <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/2fa2b32bef5246132da5b3b9bc713ab5.png\" style=\"display:block;margin: 0 auto;\" \/> na macierze <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/fd8c620c602ae49e8d6e39ef8b551d0b.png\" style=\"display:block;margin: 0 auto;\" \/> i <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/32804631a9a2f8bff35d0bcf7c29bfc6.png\" style=\"display:block;margin: 0 auto;\" \/> i wykonujemy szereg przekszta\u0142ce\u0144 (sam algorytm rozk\u0142adu QR nie b\u0119dzie tutaj omawiany, tylko jego zastosowanie w kontek\u015bcie danego zadania):<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/56cfb4ed9126e632cba51940c0d9afe6.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nMacierz <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/106bb4d6704eb9f42078555c662a8b97.png\" style=\"display:block;margin: 0 auto;\" \/> jest ortogonalna. Pozwala to nam pozby\u0107 si\u0119 iloczynu <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/618077c012f7b81f23756b9c1e54eb73.png\" style=\"display:block;margin: 0 auto;\" \/>:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/1715fb2e77d8be75e68e4791997aaa44.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nA je\u015bli zast\u0105pimy <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/926c51120ec8608bf81dc8f36fcc3ef4.png\" style=\"display:block;margin: 0 auto;\" \/> na <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/9e578153ea2dc36d0eb86be4eedf4899.png\" style=\"display:block;margin: 0 auto;\" \/>, to otrzymamy <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/8cd914db7317c01dc5449c70b36dba73.png\" style=\"display:block;margin: 0 auto;\" \/>. Bior\u0105c pod uwag\u0119, \u017ce <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/88fa4e81fc2bedf16e41e90e320a5647.png\" style=\"display:block;margin: 0 auto;\" \/> jest macierz\u0105 tr\u00f3jk\u0105tn\u0105 g\u00f3rn\u0105, wygl\u0105da to nast\u0119puj\u0105co:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/689eaaece2a497c5bd02582e3e672a41.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>\nMo\u017cna to rozwi\u0105za\u0107 metod\u0105 podstawienia. Element <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/e163597c97a539238731c31ca5ce011b.png\" style=\"display:block;margin: 0 auto;\" \/> jest obliczany jako <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/211d86418c9a38f164f490b1a7b5fb71.png\" style=\"display:block;margin: 0 auto;\" \/>, poprzedni element <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/ed3742b3a7cfb14bad801485a8cf01df.png\" style=\"display:block;margin: 0 auto;\" \/> jest obliczany jako <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/b3e582f565e1060b47af4008a98c3524.png\" style=\"display:block;margin: 0 auto;\" \/> i tak dalej.<\/p>\n<p>Tutaj warto zauwa\u017cy\u0107, \u017ce z\u0142o\u017cono\u015b\u0107 otrzymanego algorytmu dzi\u0119ki zastosowaniu rozk\u0142adu QR wynosi <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/c5c20145b7b165120d9979c2e2ca4711.png\" style=\"display:block;margin: 0 auto;\" \/>. Przy tym, mimo \u017ce operacja mno\u017cenia macierzy jest dobrze r\u00f3wnoleg\u0142a, napisanie efektywnej rozproszonej wersji tego algorytmu nie wydaje si\u0119 mo\u017cliwe.<\/p>\n<h3>Spadek gradientowy<\/h3>\n<p>\nM\u00f3wi\u0105c o minimalizacji pewnej funkcji, warto wspomnie\u0107 o metodzie (stochastycznego) spadku gradientu. To prosty i skuteczny spos\u00f3b minimalizacji, oparty na iteracyjnym obliczaniu gradientu funkcji w danym punkcie, a nast\u0119pnie przesuwaniu go w kierunku przeciwnym do gradientu. Ka\u017cdy taki krok przybli\u017ca rozwi\u0105zanie do minimum. Gradient wygl\u0105da wci\u0105\u017c tak samo:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/d195806787197323312be7c0b9d8b240.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Dodatkowo, ta metoda dobrze si\u0119 paralelizuje i rozk\u0142ada dzi\u0119ki liniowym w\u0142a\u015bciwo\u015bciom operatora gradientu. Zauwa\u017cmy, \u017ce w powy\u017cszej formule pod znakiem sumy znajduj\u0105 si\u0119 niezale\u017cne sk\u0142adniki. Innymi s\u0142owy, mo\u017cemy obliczy\u0107 gradient niezale\u017cnie dla wszystkich indeks\u00f3w <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/0c10d574f70b318b6562fb444e460fa7.png\" style=\"display:block;margin: 0 auto;\" \/> od pierwszego do <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/c9b39d76c5f724af137b5db3053e1a60.png\" style=\"display:block;margin: 0 auto;\" \/>, r\u00f3wnolegle obliczaj\u0105c gradient dla indeks\u00f3w od <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/1a9407fcb4ec67a171463d36dca30a80.png\" style=\"display:block;margin: 0 auto;\" \/> do <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/f1e29c5b16d68d6377108f53803a9cd0.png\" style=\"display:block;margin: 0 auto;\" \/>. Nast\u0119pnie sumujemy uzyskane gradienty. Rezultatem sumy b\u0119dzie taki sam wynik, jak gdyby\u015bmy obliczyli gradient dla indeks\u00f3w od pierwszego do <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/c5ec5004c59a5343f22894ef676606e3.png\" style=\"display:block;margin: 0 auto;\" \/>. Tak wi\u0119c, je\u015bli dane s\u0105 rozproszone pomi\u0119dzy kilkoma cz\u0119\u015bciami, gradient mo\u017ce by\u0107 obliczony niezale\u017cnie w ka\u017cdej cz\u0119\u015bci, a nast\u0119pnie wyniki tych oblicze\u0144 mog\u0105 zosta\u0107 zsumowane w celu uzyskania ostatecznego wyniku:<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/073ce5e3a6688e3a1ae7774aaff1a843.png\" style=\"display:block;margin: 0 auto;\" \/><\/p>\n<p>Zrealizowanie tego wpisuje si\u0119 w paradygmat <noindex><a rel=\"nofollow\" href=\"https:\/\/en.wikipedia.org\/wiki\/MapReduce\">MapReduce<\/a><\/noindex>. Na ka\u017cdym etapie spadku gradientu zadanie obliczenia gradientu jest wysy\u0142ane do ka\u017cdego w\u0119z\u0142a danych, a nast\u0119pnie obliczone gradienty s\u0105 zbierane i ich suma jest wykorzystywana do poprawy wynik\u00f3w.<\/p>\n<p>Pomimo \u0142atwo\u015bci realizacji i mo\u017cliwo\u015bci wykonania w paradygmacie MapReduce, spadek gradientu ma swoje wady. W szczeg\u00f3lno\u015bci liczba krok\u00f3w potrzebnych do osi\u0105gni\u0119cia zbie\u017cno\u015bci jest znacznie wi\u0119ksza w por\u00f3wnaniu do innych, bardziej specjalistycznych metod.<\/p>\n<h3>LSQR<\/h3>\n<p>\n<noindex><a rel=\"nofollow\" href=\"https:\/\/web.stanford.edu\/group\/SOL\/software\/lsqr\/\">LSQR<\/a><\/noindex> \u2014 kolejna metoda rozwi\u0105zania postawionego zadania, kt\u00f3ra nadaje si\u0119 zar\u00f3wno do rekonstrukcji regresji liniowej, jak i rozwi\u0105zania uk\u0142ad\u00f3w r\u00f3wna\u0144 liniowych. Jej g\u0142\u00f3wn\u0105 cech\u0105 jest po\u0142\u0105czenie zalet metod macierzowych i podej\u015bcia iteracyjnego. Implementacje tej metody mo\u017cna znale\u017a\u0107 zar\u00f3wno w bibliotece <noindex><a rel=\"nofollow\" href=\"https:\/\/docs.scipy.org\/doc\/scipy-0.14.0\/reference\/generated\/scipy.sparse.linalg.lsqr.html\">SciPy<\/a><\/noindex>, jak i w <noindex><a rel=\"nofollow\" href=\"http:\/\/matlab.izmiran.ru\/help\/techdoc\/ref\/lsqr.html\">MATLAB<\/a><\/noindex>. Opis tej metody nie b\u0119dzie tutaj podawany (mo\u017cna go znale\u017a\u0107 w artykule <noindex><a rel=\"nofollow\" href=\"https:\/\/web.stanford.edu\/group\/SOL\/software\/lsqr\/lsqr-toms82a.pdf\">LSQR: An algorithm for sparse linear equations and sparse least squares<\/a><\/noindex>). Zamiast tego zostanie zaprezentowane podej\u015bcie, kt\u00f3re pozwala dostosowa\u0107 LSQR do wykonania w \u015brodowisku rozproszonym.<\/p>\n<p>Podstaw\u0105 metody LSQR jest <noindex><a rel=\"nofollow\" href=\"http:\/\/www.netlib.org\/utk\/people\/JackDongarra\/etemplates\/node198.html\">procedura bidiagonalizacji<\/a><\/noindex>. Jest to procedura iteracyjna, kt\u00f3rej ka\u017cda iteracja sk\u0142ada si\u0119 z nast\u0119puj\u0105cych krok\u00f3w:<br \/>\n<img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/3c2f7b5c6f57830e9b522023a8e72a48.png\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nJednak je\u015bli za\u0142o\u017cy\u0107, \u017ce macierz <img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/e86c3c422629b78bc574f66db8a6139d.png\" style=\"display:block;margin: 0 auto;\" \/> jest partycjonowana poziomo, to ka\u017cd\u0105 iteracj\u0119 mo\u017cna przedstawi\u0107 jako dwa kroki MapReduce. Dzi\u0119ki temu udaje si\u0119 zminimalizowa\u0107 przesy\u0142anie danych w trakcie ka\u017cdej z iteracji (tylko wektory o d\u0142ugo\u015bci r\u00f3wnej liczbie niewiadomych):<\/p>\n<p><img decoding=\"async\" alt=\"Regresja liniowa i metody jej rekonstrukcji\" src=\"\/wp-content\/uploads\/2019\/09\/6b67654b29ed24283c4b04d66c05ea5c.png\" style=\"display:block;margin: 0 auto;\" \/><br \/>\n<br \/>\nTo w\u0142a\u015bnie to podej\u015bcie jest stosowane przy implementacji regresji liniowej w <noindex><a rel=\"nofollow\" href=\"https:\/\/github.com\/apache\/ignite\/blob\/master\/modules\/ml\/src\/main\/java\/org\/apache\/ignite\/ml\/math\/isolve\/lsqr\/AbstractLSQR.java\">Apache Ignite ML<\/a><\/noindex>.<\/p>\n<h3>Podsumowanie<\/h3>\n<p>\nIstnieje wiele algorytm\u00f3w do rekonstrukcji regresji liniowej, ale nie wszystkie mog\u0105 by\u0107 stosowane w ka\u017cdych warunkach. Rozk\u0142ad QR doskonale nadaje si\u0119 do precyzyjnego rozwi\u0105zania na ma\u0142ych zbiorach danych. Gradient descent jest \u0142atwy do zaimplementowania i pozwala szybko znale\u017a\u0107 przybli\u017cone rozwi\u0105zanie. Z kolei LSQR \u0142\u0105czy najlepsze cechy dw\u00f3ch poprzednich algorytm\u00f3w, poniewa\u017c mo\u017ce by\u0107 rozproszony, szybciej zbiega w por\u00f3wnaniu do gradient descent, a tak\u017ce umo\u017cliwia wczesne zatrzymanie algorytmu w przeciwie\u0144stwie do rozk\u0142adu QR w celu znalezienia przybli\u017conego rozwi\u0105zania.<br \/>\n<br \/>\u0179r\u00f3d\u0142o: <a content=\"nofollow\" rel=\"nofollow\" href=\"https:\/\/habr.com\/ru\/post\/465743\/\">habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"<p>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a: xkcd \u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u043d\u0438\u043c \u0438\u0437 \u0431\u0430\u0437\u043e\u0432\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0434\u043b\u044f \u043c\u043d\u043e\u0433\u0438\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u0435\u0439, \u0441\u0432\u044f\u0437\u0430\u043d\u043d\u044b\u0445 \u0441 \u0430\u043d\u0430\u043b\u0438\u0437\u043e\u043c \u0434\u0430\u043d\u043d\u044b\u0445. \u041f\u0440\u0438\u0447\u0438\u043d\u0430 \u044d\u0442\u043e\u043c\u0443 \u043e\u0447\u0435\u0432\u0438\u0434\u043d\u0430. \u042d\u0442\u043e \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438 \u043f\u043e\u043d\u044f\u0442\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0447\u0442\u043e \u0441\u043f\u043e\u0441\u043e\u0431\u0441\u0442\u0432\u0443\u0435\u0442 \u0435\u0433\u043e \u0448\u0438\u0440\u043e\u043a\u043e\u043c\u0443 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044e \u0443\u0436\u0435 \u043c\u043d\u043e\u0433\u0438\u0435 \u0434\u0435\u0441\u044f\u0442\u043a\u0438, \u0435\u0441\u043b\u0438 \u043d\u0435 \u0441\u043e\u0442\u043d\u0438, \u043b\u0435\u0442. \u0418\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u0430\u0433\u0430\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u044c \u043e\u0434\u043d\u043e\u0439 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u043e\u0442 \u043d\u0430\u0431\u043e\u0440\u0430 \u0434\u0440\u0443\u0433\u0438\u0445 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u044b\u0442\u0430\u0435\u043c\u0441\u044f [&hellip;]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":28483,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[688],"tags":[],"class_list":["post-37955","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-administrirovanie"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.0.1 - aioseo.com -->\n\t<meta name=\"description\" content=\"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a:\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Yuri Gagarin\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.0.1\" \/>\n\t\t<meta property=\"og:locale\" content=\"pl_PL\" \/>\n\t\t<meta property=\"og:site_name\" content=\"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"\ud83e\udd47\u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0435\u0451 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f | ProHoster\" \/>\n\t\t<meta property=\"og:description\" content=\"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a:\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya\" \/>\n\t\t<meta property=\"og:image\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:secure_url\" content=\"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg\" \/>\n\t\t<meta property=\"og:image:width\" content=\"350\" \/>\n\t\t<meta property=\"og:image:height\" content=\"350\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2019-10-31T19:20:47+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2019-10-31T19:20:47+00:00\" \/>\n\t\t<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<meta property=\"article:author\" content=\"https:\/\/www.facebook.com\/prohoster\" \/>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"\ud83e\udd47Regresja liniowa i metody jej rekonstrukcji | ProHoster","description":"\u0179r\u00f3d\u0142o:","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041b\u0438\u043d\u0435\u0439\u043d\u0430\u044f \u0440\u0435\u0433\u0440\u0435\u0441\u0441\u0438\u044f \u0438 \u043c\u0435\u0442\u043e\u0434\u044b \u0435\u0451 \u0432\u043e\u0441\u0441\u0442\u0430\u043d\u043e\u0432\u043b\u0435\u043d\u0438\u044f | ProHoster","og:description":"\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a:","og:url":"https:\/\/prohoster.info\/pl\/blog\/administrirovanie\/linejnaya-regressiya-i-metody-eyo-vosstanovleniya","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:20:47+00:00","article:modified_time":"2019-10-31T19:20:47+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"37955","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-23 19:55:19","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 01:17:23","updated":"2026-01-23 19:55:19","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/37955","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=37955"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/37955\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/28483"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=37955"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=37955"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=37955"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}