Dlaczego spadek gradientu jest nieefektywny w przypadku dużych zbiorów danych?

13

Załóżmy, że nasz zestaw danych zawiera 1 milion przykładów, tj. , i chcemy użyć opadania gradientu, aby przeprowadzić regresję logistyczną lub liniową na tym zestawie danych. $x_1, \ldots, x_{10^6}$

Co to jest z metodą opadania gradientu, która sprawia, że jest nieefektywna?

Przypomnijmy, że krok opadania gradientu w czasie jest określony przez: $t$

w_{t + 1} = w_{t} + η_{t} \nabla f (x)

$w_{t+1} = w_{t} + \eta_t \nabla f(x)$

gdzie jest funkcją straty. $f$

Nie widzę nic niezwykłego w powyższym kroku, który powoduje, że algorytm jest nieefektywny. Czy to obliczenie ? Czy nie można wstępnie obliczyć tej operacji, tzn. każdy już obliczony i po prostu ocenić je w każdym punkcie danych $\nabla f(x)$ $\frac{\partial f}{\partial x}$ $x_i?$

machine-learning gradient-descent large-data

— Carlos - Mongoose - Danger
źródło

1

Nieefektywne w stosunku do ...? Nawet najmniejsze kwadraty są nieefektywne dla dużego zestawu danych. Potrzebujesz dużej notacji O, aby mieć sensowne pomysły na temat tego, co robi algorytmowi. Nie wszystkie algorytmy GD mają ten sam duży O. (prawda?)

n

$n$

— AdamO

7

Pomogłoby to, gdybyś podał kontekst twierdzenia, że spadek gradientu jest nieefektywny. Niewystarczające w stosunku do czego?

Wydaje mi się, że brakującym kontekstem jest porównanie do stochastycznego lub okresowego spadku gradientu w uczeniu maszynowym. Oto jak odpowiedzieć na pytanie w tym kontekście. Optymalizujesz parametry modelu, nawet hiperparametry. Masz więc funkcję kosztu , gdzie - twoje dane, i - wektor parametrów, a - funkcja straty. Aby zminimalizować ten koszt, korzystasz z opadania gradientu ponad parametrami : $\sum_{i=1}^n L(x_i|\Theta)$ $x_i$ $\Theta$ $L()$ $\theta_j$

\frac{\partial}{\partial θ_{j}} \sum_{i = 1}^{n} L (Θ | x_{i})

$\frac{\partial}{\partial \theta_j}\sum_{i=1}^nL(\Theta|x_i)$

Widzisz więc, że musisz uzyskać sumę dla wszystkich danych . Jest to niefortunne, ponieważ oznacza to, że ciągle przeglądasz dane dla każdego kroku zejścia gradientu. Tak powstaje okresowe i stochastyczne zejście gradientu: co, jeśli próbkujemy z zestawu danych i obliczamy gradient na próbce, a nie na pełnym zestawie? Tutaj oznacza liczbę obserwacji w próbce . Tak więc, jeśli twoja próbka stanowi 1/100 całego zestawu, przyspiesz obliczenia 100 razy! Oczywiście wprowadza to hałas, który wydłuża naukę, ale hałas zmniejsza się w tempie $x_{i=1,\dots,n}$

\frac{\partial}{\partial θ_{j}} \sum_{k = 1}^{n_{s}} L (Θ | x_{k})

$\frac{\partial}{\partial \theta_j}\sum_{k=1}^{n_s}L(\Theta|x_k)$

n_{s}

$n_s$

s

$s$

\sqrt{n}

$\sqrt n$ podczas gdy kwota obliczeniowa wzrasta przy , więc ta sztuczka może działać.

n

$n$

Alternatywnie, insteado czeka na obliczenie pełnej sumy , możesz podzielić to na partie i zrobić krok dla każdej partii . W ten sposób wykonasz M kroków do czasu obliczenia sumy dla całego zestawu danych. Byłyby to głośniejsze kroki, ale hałas z czasem zanika. $\sum_{i=1}^n$ $\sum_{s=1}^M\sum_{i_s=1}^{n_s}$

— Aksakal
źródło

19

Istnieją dwa sposoby, w których opadanie gradientu może być nieefektywne. Co ciekawe, każdy z nich prowadzi do własnej metody naprawy, która jest prawie odwrotnym rozwiązaniem. Dwa problemy to:

(1) Wymaganych jest zbyt wiele aktualizacji zejścia gradientu.

(2) Każdy stopień spadku gradientu jest zbyt drogi.

W odniesieniu do (1), porównując opadanie gradientu z metodami uwzględniającymi informacje o pochodnych drugiego rzędu, opadanie gradientu wydaje się być wysoce nieefektywne w odniesieniu do poprawy strat przy każdej iteracji. Bardzo standardowa metoda, Metoda Newtona , zazwyczaj wymaga znacznie mniej iteracji, aby zbiegać się, tj. W przypadku regresji logistycznej 10 iteracji Metody Newtona często będzie miało mniejszą stratę niż rozwiązanie zapewniane przez 5000 iteracji spadku gradientu. W przypadku regresji liniowej jest to jeszcze bardziej ekstremalne; istnieje rozwiązanie w formie zamkniętej! Jednakże, ponieważ liczba predyktorów staje się bardzo duża (tj. 500+), Metoda Newtona / bezpośrednie rozwiązywanie dla regresji liniowej może stać się zbyt kosztowne na iterację ze względu na wymaganą liczbę operacji macierzy, podczas gdy zniżanie gradientu będzie miało znacznie mniejszy koszt na iterację.

W odniesieniu do (2) możliwe jest posiadanie tak dużego zestawu danych, że każda iteracja spadku gradientu jest zbyt droga do obliczenia. Obliczenie gradientu będzie wymagało operacji ( = wielkość próbki, = liczba zmiennych towarzyszących). Podczas gdy nie jest wcale problemem na współczesnych komputerach dla wartości , z pewnością coś takiego jak , będzie. W tym przypadku metody, które aproksymują pochodną na podstawie mniejszych podzbiorów danych, są bardziej atrakcyjne, takie jak opadanie gradientu stochastycznego . $O(nk)$ $n$ $k$ $n = 10^{6}$ $k < 100$ $n = 10^{12}$ $k = 10^3$

Mówię, że poprawki te są prawie przeciwne, ponieważ coś takiego jak metoda Newtona jest droższa, ale bardziej wydajna (pod względem zmiany straty) na aktualizację, podczas gdy stochastyczne obniżanie gradientu jest w rzeczywistości mniej wydajne, ale znacznie tańsze obliczeniowo na aktualizację.

— Cliff AB
źródło

Dziękuję za niesamowitą odpowiedź. Co rozumiesz przez = liczba zmiennych towarzyszących? Nie znam tej terminologii

k

$k$

— Carlos - Mongoose - Danger

2

@Learningonepageatatime: covariates = zmienne predykcyjne.

— Cliff AB,

10

Najpierw pozwól, że zasugeruję ulepszenie twojej notacji. W szczególności oznaczmy funkcję straty przez zamiast . Korzystanie literę jest po prostu osobistych preferencji kopalni, ponieważ przypomina mi, że mamy do czynienia z L Oss. Bardziej merytoryczna zmiana wyjaśnia, że utrata jest funkcją wag a nie danych . Co ważne, gradient jest w odniesieniu do nie . Więc gdzie jest wymiarow dane. $L(w)$ $f(x)$ $L$ $w$ $x$ $w$ $x$

\nabla L (w) = (\frac{\partial L}{\partial w_{1}}, \dots, \frac{\partial L}{\partial w_{D}}),

$\nabla L(w) = \left(\frac{\partial L}{\partial w_1}, \dots, \frac{\partial L}{\partial w_D} \right),$

D

$D$

Pomimo faktu, że powinniśmy myśleć o utracie jako o funkcji wag , każda rozsądna funkcja utraty nadal będzie zależeć od całego zestawu danych (gdyby tego nie zrobiła, nie byłoby możliwe nauczenie się niczego na podstawie danych! ). Na przykład w regresji liniowej zwykle używamy funkcji utraty sumy kwadratów Tak więc ocena gradientu dla określonego zestawu wag będzie wymagać sumy na wszystkich punktach w zestawie danych . Jeśli , to każdy krok przyrostowy w optymalizacji opadania gradientu będzie wymagał rzędu miliona operacji, co jest dość drogie. $w$ $x$

L (w) = \sum_{i = 1}^{N} (y_{i} - w^{T} x_{i})^{2} .

$L(w) = \sum_{i=1}^N (y_i - w^Tx_i)^2.$

\nabla L (w)

$\nabla L(w)$

w

$w$

N

$N$

x

$x$

N = 10^{6}

$N = 10^6$

— tddevlin
źródło

3

Krótka odpowiedź: Obliczanie gradientu wymaga zsumowania wszystkich punktów danych. Jeśli mamy dużą ilość danych, zajmuje to dużo czasu.

Mam tutaj szczegółową odpowiedź.

Jak stochastyczne obniżanie gradientu może zaoszczędzić czas w porównaniu ze standardowym spadkiem gradientu?

Z drugiej strony zawsze należy pamiętać, że oprócz metod iteracyjnych istnieją metody bezpośrednie (przyzwoity gradient). Jeśli chcemy rozwiązać problem najmniejszych kwadratów, metoda bezpośrednia może być super wydajna. Na przykład rozkład QR. Jeśli nie mamy zbyt wielu funkcji, jest to bardzo szybkie.

Po zweryfikowaniu może Cię zaskoczyć: 5 milionów punktów danych z 2 funkcjami. Rozwiązanie regresji liniowej / najmniejszego kwadratu zajmuje kilka sekund!

x=matrix(runif(1e7),ncol=2)
y=runif(5e6)
start_time <- Sys.time()
lm(y~x)
end_time <- Sys.time()
end_time - start_time
# Time difference of 4.299081 secs

— Haitao Du
źródło

1

Chociaż dwa przykłady, które wymieniłeś, są zwykle wypukłe, dodam jeden punkt na temat problemów niewypukłych. Moim zdaniem istnieją dwa główne powody, dla których opadanie gradientu (partii) można uznać za „nieefektywne”. Pierwszy punkt dotyczący wysiłku obliczeniowego obliczenia gradientu „dużej” sumy funkcji został już bardzo wyraźnie zarysowany w innych odpowiedziach. W przypadku problemów niewypukłych GD ma jednak problem z utknięciem w „bliskim” lokalnym minimum. To minimum może być bardzo złe w porównaniu do globalnego minimum. SGD lub mini-partia GD mają tę „zaletę”, że wędrują (przynajmniej częściowo) losowo, a zatem mogą mieć szansę na znalezienie lepszego lokalnego minimum. Zobacz odpowiedź na CV tutaj . Lub ten inny post z CV określając, w jaki sposób losowość może być korzystna.

— Xel
źródło