Źródło:
Regresja liniowa jest jednym z podstawowych algorytmów wykorzystywanych w wielu dziedzinach związanych z analizą danych. Powód jest oczywisty. To bardzo prosty i zrozumiały algorytm, co sprzyja jego szerokiemu zastosowaniu przez wiele 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óbie odtworzenia tej zależności.
Jednak w tym artykule nie będziemy omawiać zastosowania regresji liniowej do rozwiązywania praktycznych problemów. Zostaną omówione interesujące aspekty realizacji rozproszonych algorytmów jej odtwarzania, z którymi spotkaliśmy się podczas pisania modułu uczenia maszynowego w . Trochę podstawowej matematyki, podstaw uczenia maszynowego i obliczeń rozproszonych pomoże zrozumieć, jak odtwarzać regresję liniową, nawet jeśli dane są rozproszone pomiędzy tysiącami węzłów.
O co chodzi?
Stoi przed nami zadanie odtworzenia liniowej zależności. Jako dane wejściowe podawane jest wiele wektorów przypuszczalnie niezależnych zmiennych, z którymi każdemu przypisana jest pewna wartość zmiennej zależnej. Te dane można przedstawić w postaci dwóch macierzy:
Teraz, skoro zakładamy zależność, a do tego jeszcze liniową, zapiszmy nasze przypuszczenie w postaci iloczynu macierzy (dla uproszczenia zapisu w tym i kolejnych podpunktach przyjmuje się, że wolny człon równania jest ukryty za 
, a ostatnia kolumna macierzy 
zawiera jedynki):
Bardzo przypomina to układ równań liniowych, prawda? Przypomina, ale taki układ równań prawdopodobnie nie będzie miał rozwiązań. Przyczyną tego jest szum, który obecny jest praktycznie w każdym rzeczywistym zbiorze danych. Przyczyną może być także brak liniowej zależności jako takiej, z którą można by próbować walczyć poprzez wprowadzenie dodatkowych zmiennych nieliniowo zależnych od wyjściowych. Rozważmy następujący przykład:
Źródło:
To prosty przykład regresji liniowej, który demonstruje zależność jednej zmiennej (na osi 
) od innej zmiennej (na osi 
). Aby odpowiedni system równań liniowych miał rozwiązanie, wszystkie punkty muszą leżeć dokładnie na tej samej prostej. Ale tak nie jest. A to, że nie leżą one na jednej prostej, wynika właśnie z szumu (lub z błędnego założenia o istnieniu zależności liniowej). W związku z tym, aby odtworzyć zależność liniową na podstawie rzeczywistych danych, zazwyczaj trzeba wprowadzić jeszcze jedno założenie: dane wejściowe zawierają szum, a ten szum ma . Można również wysuwać założenia o innych typach rozkładu szumu, ale w przeważającej większości przypadków rozpatruje się właśnie rozkład normalny, o którym poniżej będzie mowa.
Metoda największej wiarygodności
Zatem, założyliśmy obecność losowego szumu o rozkładzie normalnym. Co w takiej sytuacji zrobić? W matematyce istnieje i jest szeroko stosowana . W skrócie, polega ona na wyborze i jej późniejszej maksymalizacji.
Wracając do odtwarzania zależności liniowej na podstawie danych z normalnym szumem. Zauważmy, że zakładana zależność liniowa jest matematyczną oczekiwaną wartością 
istniejącego rozkładu normalnego. Jednocześnie prawdopodobieństwo, że 
przyjmuje wartość, pod warunkiem występowania obserwowanych 
, wygląda następująco:
Podstawmy teraz zamiast 
i 
potrzebne nam zmienne:
Pozostało tylko znaleźć wektor 
, przy którym to prawdopodobieństwo jest maksymalne. Aby zmaksymalizować taką funkcję, wygodnie jest najpierw ją zlogarytmayzować (logarytm funkcji będzie osiągał maksimum w tym samym punkcie, co sama funkcja):
Co z kolei sprowadza się do minimalizacji następującej funkcji:
Przy okazji, nazywa się to metodą . Często wszystkie powyższe rozważania są pomijane, a po prostu używa się tej metody.
Rozkład QR
Minimum powyższej funkcji można znaleźć, jeśli znajdziemy punkt, w którym gradient tej funkcji jest równy zeru. A gradient zapisuje się w następujący sposób:
jest macierzową metodą rozwiązania problemu minimalizacji stosowaną w metodzie najmniejszych kwadratów. W związku z tym przepiszemy równanie w formie macierzowej:
Zatem rozkładamy macierz 
na macierze 
i 
i wykonujemy szereg przekształceń (sam algorytm rozkładu QR nie będzie tutaj omawiany, tylko jego zastosowanie w kontekście postawionego zadania):
Macierz 
jest ortogonalna. Pozwala nam to pozbyć się iloczynu 
:
A jeśli zamienić 
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ą podstawień. Element 
znajduje się jako 
, poprzedni element 
znajduje się jako 
i tym podobne.
Należy zauważyć, że złożoność uzyskanego algorytmu dzięki zastosowaniu rozkładu QR wynosi 
. Warto przy tym zauważyć, że operacja mnożenia macierzy dobrze się równolegle wykonuje, jednak napisanie efektywnej rozproszonej wersji tego algorytmu nie wydaje się możliwe.
Spadek gradientu
Mówiąc o minimalizacji pewnej funkcji, zawsze warto pamiętać o metodzie (stochastycznego) spadku gradientu. To prosty i skuteczny sposób minimalizacji, oparty na iteracyjnym obliczaniu gradientu funkcji w punkcie, a następnie przesunięciu go w kierunku przeciwnym do gradientu. Każdy taki krok przybliża rozwiązanie do minimum. Gradient przy tym wygląda tak samo:
Ten sposób dobrze się również równolegle wykonuje i rozprasza dzięki liniowym właściwościom operatora gradientu. Zauważmy, że w powyższym wzorze pod symbolem 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 z 
do 
. Następnie zsumować uzyskane gradienty. Wynikiem sumowania będzie taki sam, jakbyśmy od razu obliczyli gradient dla indeksów od pierwszego do 
. W ten sposób, jeśli dane są rozproszone pomiędzy kilka części danych, gradient może być obliczany niezależnie w każdej części, a następnie wyniki tych obliczeń mogą być zsumowane, aby uzyskać ostateczny rezultat:
Z punktu widzenia realizacji, mieści się to w paradygmacie . Na każdym kroku spadku gradientu do każdego węzła danych wysyłane jest zadanie obliczenia gradientu, następnie obliczone gradienty są zbierane razem, a wynik ich sumowania jest wykorzystywany do poprawy rezultatu.
Mimo prostoty realizacji i możliwości wykonywania w paradygmacie MapReduce, metoda gradientowego spadku ma również swoje wady. W szczególności liczba kroków potrzebnych do osiągnięcia zbieżności jest znacznie większa w porównaniu z innymi, bardziej wyspecjalizowanymi metodami.
LSQR
to kolejna metoda rozwiązania zadanego problemu, która nadaje się zarówno do rekonstrukcji regresji liniowej, jak i do rozwiązania układów równań liniowych. Jej główną cechą jest to, że łączy zalety metod macierzowych i podejścia iteracyjnego. Implementacje tej metody można znaleźć w bibliotece , jak i w . Opis tej metody nie będzie tu podawany (można go znaleźć w artykule ). Zamiast tego zaprezentowane zostanie podejście, które pozwala na dostosowanie LSQR do realizacji w rozproszonym środowisku.
W podstawie metody LSQR leży . To iteracyjna procedura, której każda iteracja składa się z następujących kroków:
Jednak zakładając, że macierz 
jest partycjonowana poziomo, można każdą iterację przedstawić w postaci dwóch kroków 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 podejście jest używane przy realizacji regresji liniowej w .
Podsumowanie
Istnieje wiele algorytmów rekonstrukcji regresji liniowej, ale nie wszystkie z nich mogą być stosowane w każdych warunkach. Na przykład rozkład QR doskonale nadaje się do dokładnych rozwiązań na małych zbiorach danych. Gradientowy spadek jest łatwy w realizacji i pozwala szybko znaleźć przybliżone rozwiązanie. A LSQR łączy najlepsze właściwości dwóch wcześniejszych algorytmów, ponieważ może być rozproszony, szybciej zbiega w porównaniu do gradientowego spadku oraz umożliwia wcześniejsze zatrzymanie algorytmu w przeciwieństwie do rozkładu QR w celu znalezienia przybliżonego rozwiązania.
Źródło: habr.com
