Jak uruchomić regresję liniową w sposób równoległy / rozproszony dla ustawienia dużych zbiorów danych?

Pracuję nad bardzo dużym problemem z regresją liniową, przy czym rozmiar danych jest tak duży, że muszą być przechowywane na klastrze maszyn. Będzie o wiele za duży, aby zgrupować wszystkie próbki w pamięci jednego komputera (nawet dysku)

Aby wykonać regresję tych danych, myślę o podejściu równoległym, tj. Uruchom regresję dla każdego pojedynczego pola, a następnie oblicz beta w oparciu o statystyki każdej indywidualnej wersji beta (prawdopodobnie średniej lub mediany)

czy to ma jakiś sens? jeśli tak, to w jaki sposób powinienem uzyskać całkowitą oczekiwaną z każdego pojedynczego ?R $R^2$$R^2$

Krótka odpowiedź:

Tak, równoległa regresja liniowa została wykonana. Na przykład Xiangrui Meng i in. (2016) dla Machine Learning w Apache Spark. Jego działanie polega na użyciu stochastycznego spadku gradientu (SGD). W części 3 kluczowe cechy autor wspomniał:

Uogólnione modele liniowe uczy się za pomocą algorytmów optymalizacji, które równolegle obliczają gradienty, używając szybkich bibliotek algebry opartej na C ++ do obliczeń roboczych.

Przykład działania SGD można znaleźć w mojej odpowiedzi tutaj: W jaki sposób stochastyczne obniżanie gradientu może zaoszczędzić czas w porównaniu do standardowego spadku?

Długa odpowiedź:

Uwaga: notacja nie jest zgodna z linkiem, który podałem, wydaje mi się, że notacja macierzowa jest lepsza w tym pytaniu.

Aby wykonać regresję liniową, próbujemy to zrobić

Pochodną jest

W małych ustawieniach danych możemy ustawić pochodną na i rozwiązać ją bezpośrednio. (np. dekompozycja QR w R.) W ustawieniach dużych danych macierz danych jest zbyt duża, aby ją zapisać w pamięci, i może być trudna do bezpośredniego rozwiązania. (Nie wiem, jak wykonać rozkład QR lub rozkład Cholesky'ego dla wielkich matryc).$0$$X$

Jednym ze sposobów na zrównoleglenie tego jest próba zastosowania metody iteracyjnej: stochastycznego spadku gradientu, w którym możemy aproksymować gradient za pomocą podzbioru danych. (Jeśli stosujemy , reprezentuje podzbiór danych gradient można przybliżyć , i może aktualizować z przybliżonego gradient).y s 2 X T s ( X s β - y s ) $X_s$$y_s$$2X_s^T(X_s\beta-y_s)$$\beta$

Ponadto w przypadku statystyki możemy obliczyć dla wszystkich danych równolegle lub w przybliżeniu, stosując podzbiór danych.R $R^2$$R^2$

Intuicja, jak to działa (paradygmat mapreduce):

Powtarzam przybliżenie za pomocą podzbioru; intuicję, dlaczego to działa, można opisać w następującym przykładzie: załóżmy, że mam 100 miliardów punktów danych i chcemy obliczyć średnią wszystkich punktów danych. Załóżmy, że przeprowadzenie takiej operacji zajmuje bardzo dużo czasu, a ponadto całe dane nie mogą być przechowywane w pamięci.

Możemy po prostu wziąć podzbiór, powiedzmy 1 miliard pozycji i obliczyć jego średnią. Tak uzyskane przybliżenie nie powinno być dalekie od prawdy (tj. Z wykorzystaniem całych danych).

Aby zrównoważyć, możemy użyć 100 komputerów, z których każdy pobiera inny podzbiór 1 miliarda punktów danych i oblicza ich średnią. (Powszechnie nazywany krokiem MAP). Na koniec uruchom kolejną średnią dla tych 100 liczb (inaczej krok ZMNIEJSZ).

Zauważ, że „paradygmat mapreduce” działałby dobrze w niektórych przypadkach, ale w innych nie. Na przykład wspomniana wcześniej operacja „średnia” jest bardzo łatwa, ponieważ wiemy , ( przy założeniu, że długość i są takie same). W przypadku niektórych metod iteracyjnych, tj. Bieżąca iteracja zależy od wcześniejszych wyników iteracji, trudno jest zrównoważyć. Stochastyczne obniżanie gradientu rozwiązuje ten problem poprzez aproksymację gradientu za pomocą podzbioru danych. Szczegóły można znaleźć w odpowiedzi na @ user20160.x $\text{mean}(<x,y>)=\text{mean}(x)+\text{mean(y)}$$x$$y$

Bibliografia:

Xiangrui Meng i in. (2016) . MLlib: Uczenie maszynowe w Apache Spark

Jak wspomniano @ hxd1011, jednym z podejść jest sformułowanie regresji liniowej jako problemu optymalizacji, a następnie rozwiązanie jej za pomocą algorytmu iteracyjnego (np. Opadanie gradientu stochastycznego). Podejście to można zrównoważyć, ale jest kilka ważnych pytań: 1) Jak problem powinien zostać podzielony na podproblemy? 2) Biorąc pod uwagę, że algorytmy optymalizacji, takie jak SGD, są z natury sekwencyjne, w jaki sposób należy połączyć rozwiązania podproblemów, aby uzyskać rozwiązanie globalne?

Zinkevich i in. (2010) opisują niektóre wcześniejsze podejścia do paralelizacji na wielu komputerach:

• 1) Równolegle SGD w następujący sposób: Podziel dane na wiele komputerów. Na każdym etapie każda lokalna maszyna ocenia gradient przy użyciu podzbioru danych. Wszystkie oszacowania gradientu są przekazywane do centralnej maszyny, która agreguje je w celu przeprowadzenia globalnej aktualizacji parametrów. Minusem tego podejścia jest to, że wymaga intensywnej komunikacji sieciowej, co zmniejsza wydajność.

• 2) Podziel dane równomiernie na komputery lokalne. Każda maszyna rozwiązuje problem dokładnie dla własnego podzbioru danych za pomocą solvera. Szacunki parametrów końcowych z maszyn lokalnych uśrednia się, aby uzyskać globalne rozwiązanie. Zaletą tego podejścia jest to, że wymaga bardzo małej komunikacji sieciowej, ale wadą jest to, że oszacowania parametrów mogą być nieoptymalne.

Proponują nowe podejście:

• 3) Pozwól każdej maszynie lokalnej losowo rysować punkty danych. Uruchom SGD na każdej maszynie. Wreszcie uśrednij parametry na różnych maszynach, aby uzyskać globalne rozwiązanie. Podobnie jak (2), ta metoda wymaga niewielkiej komunikacji sieciowej. Jednak szacunki parametrów są lepsze, ponieważ każda maszyna ma dostęp do większej części danych.

Podejście do optymalizacji równoległej jest bardzo ogólne i dotyczy wielu algorytmów uczenia maszynowego (nie tylko regresji liniowej).

Inną alternatywą byłoby zastosowanie algorytmów rozkładu macierzy równoległych / rozproszonych lub solwerów liniowych. Regresja liniowa metodą najmniejszych kwadratów ma specjalną strukturę, która pozwala na jej rozwiązanie za pomocą metod rozkładu macierzy. Tak zazwyczaj rozwiązuje się go w przypadku mniejszego zestawu danych, który mieści się w pamięci. Można to zrównoważyć, rozdzielając bloki macierzy na wiele maszyn, a następnie rozwiązując problem za pomocą obliczeń macierzy równoległych / rozproszonych. Biorąc pod uwagę, że to podejście jest bardziej wyspecjalizowane w rozwiązywaniu układów liniowych, interesujące byłoby porównanie jego wydajności z bardziej ogólnym podejściem do optymalizacji rozproszonej. Jeśli ktoś może podać więcej informacji na ten temat, chętnie to usłyszę.

Bibliografia:

Zinkevich i in. (2010) . Równoległe stochastyczne zejście gradientu.

Długo, długo, zanim mapa się zmniejszyła, rozwiązałem to. Poniżej znajduje się odniesienie do mojego starego artykułu w Journal of Econometrics 1980. Było to dla równoległego nieliniowego maksymalnego prawdopodobieństwa i działałoby dla oszacowania M.

Metoda jest dokładna w przypadku regresji. Podziel dane na k podzbiorów na k procesorach / jednostkach (można to również zrobić sekwencyjnie). Czy regresje k utrzymują współczynniki regresji i macierz X'X dla każdego. Wywołaj odpowiednio te b1, ..., bk i W1, ..., Wk, a następnie ogólne współczynniki regresji są podane przez b = odwrotne (W1 + .. + Wk) * (W1 * b1 + ... + Wk * bk) jeden potrzebuje kolejnego przejścia przez dane w celu obliczenia reszt za pomocą b dla parametrów, aby uzyskać sigma ^ 2 szacunkową wariancję błędu, R ^ 2 ogólne F i tym podobne. Następnie macierz kowariancji b jest podawana dokładnie przez sigma ^ 2 (odwrotna (W1 + .. + Wk)). Powyżej * oznacza mnożenie macierzy.

https://www.sciencedirect.com/science/article/pii/0304407680900950