Źródło:
Regresja liniowa to jeden z podstawowych algorytmów w wielu dziedzinach związanych z analizą danych. Powód jest oczywisty. Jest to bardzo prosty i zrozumiały algorytm, co przyczynia się do jego szerokiego zastosowania od dziesięcioleci, jeśli nie setek lat. Idea polega na założeniu liniowej zależności jednej zmiennej od zestawu innych zmiennych, a następnie próbę odtworzenia tej zależności.
Jednak w tym artykule nie będziemy mówić o zastosowaniu regresji liniowej do rozwiązywania praktycznych problemów. Skoncentrujemy się na interesujących aspektach realizacji rozproszonych algorytmów jej rekonstrukcji, z którymi zetknęliśmy się podczas pisania modułu uczenia maszynowego w . Trochę podstawowej matematyki, zasad uczenia maszynowego oraz obliczeń rozproszonych pomoże zrozumieć, jak rekonstruować regresję liniową, nawet gdy dane są rozproszone między tysiącami węzłów.
O co chodzi?
Przed nami zadanie odzyskania liniowej zależności. Jako dane wejściowe otrzymujemy zbiór wektorów przypuszczalnie niezależnych zmiennych, którym przypisuje się pewne wartości zmiennej zależnej. Te dane można przedstawić w postaci dwóch macierzy:
Teraz, skoro zakładamy zależność, a do tego liniową, zapiszmy nasze przypuszczenie w postaci iloczynu macierzy (dla uproszczenia zapisu w tym i kolejnych przypadkach zakłada się, że człon wolny równania jest ukryty za 
, a ostatnia kolumna macierzy 
zawiera jedynki):
Bardzo podobne do systemu równań liniowych, prawda? Podobne, ale system ten najprawdopodobniej nie ma rozwiązań. Przyczyną jest szum, który występuje praktycznie w każdych rzeczywistych danych. Inną przyczyną może być brak liniowej zależności jako takiej, z którą można próbować walczyć, wprowadzając dodatkowe zmienne, nieliniowo zależne od początkowych. Rozważmy następujący przykład:
Źródło:
To prosty przykład regresji liniowej, który demonstruje zależność jednej zmiennej (po osi 
) od innej zmiennej (w kierunku 
). Aby odpowiedni układ równań liniowych miał rozwiązanie, wszystkie punkty muszą leżeć dokładnie na jednej prostej. Ale tak nie jest. A nie leżą na jednej prostej właśnie z powodu szumu (lub dlatego, że założenie o istnieniu liniowej zależności było błędne). W związku z tym, aby przywrócić liniową zależność na podstawie rzeczywistych danych, zazwyczaj trzeba wprowadzić jeszcze jedno założenie: dane wejściowe zawierają szum i ten szum ma . Można również formułować założenia dotyczące innych typów rozkładów szumu, ale w przeważającej większości przypadków rozważa się właśnie rozkład normalny, o którym mowa będzie dalej.
Metoda największej wiarygodności
Zatem założyliśmy obecność losowego szumu rozłożonego normalnie. Co zatem zrobić w takiej sytuacji? Na ten przypadek w matematyce istnieje i jest szeroko stosowana . Mówiąc krótko, jej istota polega na wyborze i jej maksymalizacji.
Wracamy do przywracania liniowej zależności na podstawie danych z normalnym szumem. Zauważmy, że zakładana liniowa zależność jest matematycznym oczekiwaniem 
istniejącego rozkładu normalnego. Jednocześnie prawdopodobieństwo, że 
przyjmuje określoną wartość, pod warunkiem, że istnieją obserwowalne 
, wygląda w następujący sposób:
Podstawmy teraz zamiast 
и 
potrzebne nam zmienne:
Pozostaje tylko znaleźć wektor 
, dla którego to prawdopodobieństwo jest maksymalne. Aby zmaksymalizować taką funkcję, wygodnie jest najpierw ją przełożyć na logarytm (logarytm funkcji osiągnie maksimum w tym samym punkcie, co sama funkcja):
Co z kolei sprowadza się do minimalizacji następującej funkcji:
Zresztą to nazywa się metodą . Często wszystkie powyższe rozważania są pomijane i po prostu stosuje się tę metodę.
Rozkład QR
Minimum powyższej funkcji można znaleźć, jeśli znajdziemy punkt, w którym gradient tej funkcji jest równy zero. A gradient będzie zapisany w następujący sposób:
jest metodą macierzową rozwiązywania problemu minimalizacji, wykorzystywaną w metodzie najmniejszych kwadratów. W związku z tym przepiszemy równanie w formie macierzowej:
Zatem rozkładamy macierz 
na macierze 
и 
i wykonujemy szereg przekształceń (sam algorytm rozkładu QR nie będzie tutaj omawiany, tylko jego zastosowanie w kontekście danego zadania):
Macierz 
jest ortogonalna. Pozwala to nam pozbyć się iloczynu 
:
A jeśli zastąpimy 
na 
, to otrzymamy 
. Biorąc pod uwagę, że 
jest macierzą trójkątną górną, wygląda to następująco:
Można to rozwiązać metodą podstawienia. Element 
jest obliczany jako 
, poprzedni element 
jest obliczany jako 
i tak dalej.
Tutaj warto zauważyć, że złożoność otrzymanego algorytmu dzięki zastosowaniu rozkładu QR wynosi 
. Przy tym, mimo że operacja mnożenia macierzy jest dobrze równoległa, napisanie efektywnej rozproszonej wersji tego algorytmu nie wydaje się możliwe.
Spadek gradientowy
Mówiąc o minimalizacji pewnej funkcji, warto wspomnieć o metodzie (stochastycznego) spadku gradientu. To prosty i skuteczny sposób minimalizacji, oparty na iteracyjnym obliczaniu gradientu funkcji w danym punkcie, a następnie przesuwaniu go w kierunku przeciwnym do gradientu. Każdy taki krok przybliża rozwiązanie do minimum. Gradient wygląda wciąż tak samo:
Dodatkowo, ta metoda dobrze się paralelizuje i rozkłada dzięki liniowym właściwościom operatora gradientu. Zauważmy, że w powyższej formule pod znakiem sumy znajdują się niezależne składniki. Innymi słowy, możemy obliczyć gradient niezależnie dla wszystkich indeksów 
od pierwszego do 
, równolegle obliczając gradient dla indeksów od 
do 
. Następnie sumujemy uzyskane gradienty. Rezultatem sumy będzie taki sam wynik, jak gdybyśmy obliczyli gradient dla indeksów od pierwszego do 
. Tak więc, jeśli dane są rozproszone pomiędzy kilkoma częściami, gradient może być obliczony niezależnie w każdej części, a następnie wyniki tych obliczeń mogą zostać zsumowane w celu uzyskania ostatecznego wyniku:
Zrealizowanie tego wpisuje się w paradygmat . Na każdym etapie spadku gradientu zadanie obliczenia gradientu jest wysyłane do każdego węzła danych, a następnie obliczone gradienty są zbierane i ich suma jest wykorzystywana do poprawy wyników.
Pomimo łatwości realizacji i możliwości wykonania w paradygmacie MapReduce, spadek gradientu ma swoje wady. W szczególności liczba kroków potrzebnych do osiągnięcia zbieżności jest znacznie większa w porównaniu do innych, bardziej specjalistycznych metod.
LSQR
— kolejna metoda rozwiązania postawionego zadania, która nadaje się zarówno do rekonstrukcji regresji liniowej, jak i rozwiązania układów równań liniowych. Jej główną cechą jest połączenie zalet metod macierzowych i podejścia iteracyjnego. Implementacje tej metody można znaleźć zarówno w bibliotece , jak i w . Opis tej metody nie będzie tutaj podawany (można go znaleźć w artykule ). Zamiast tego zostanie zaprezentowane podejście, które pozwala dostosować LSQR do wykonania w środowisku rozproszonym.
Podstawą metody LSQR jest . Jest to procedura iteracyjna, której każda iteracja składa się z następujących kroków:
Jednak jeśli założyć, że macierz 
jest partycjonowana poziomo, to każdą iterację można przedstawić jako dwa kroki MapReduce. Dzięki temu udaje się zminimalizować przesyłanie danych w trakcie każdej z iteracji (tylko wektory o długości równej liczbie niewiadomych):
To właśnie to podejście jest stosowane przy implementacji regresji liniowej w .
Podsumowanie
Istnieje wiele algorytmów do rekonstrukcji regresji liniowej, ale nie wszystkie mogą być stosowane w każdych warunkach. Rozkład QR doskonale nadaje się do precyzyjnego rozwiązania na małych zbiorach danych. Gradient descent jest łatwy do zaimplementowania i pozwala szybko znaleźć przybliżone rozwiązanie. Z kolei LSQR łączy najlepsze cechy dwóch poprzednich algorytmów, ponieważ może być rozproszony, szybciej zbiega w porównaniu do gradient descent, a także umożliwia wczesne zatrzymanie algorytmu w przeciwieństwie do rozkładu QR w celu znalezienia przybliżonego rozwiązania.
Źródło: habr.com
