Co powoduje błąd wypukły powierzchni? Czy determinuje to macierz Covarinace'a czy Hesjan?

Obecnie uczę się o szacunkach metodą najmniejszych kwadratów (i innych) dla regresji, a z tego, co czytam również w niektórych literaturach algorytmu adaptacyjnego, często pojawia się wyrażenie „... a ponieważ powierzchnia błędu jest wypukła ...” i jakakolwiek głębia, dlaczego na początku jest wypukła, nie ma gdzie znaleźć.

... Co dokładnie sprawia, że jest wypukły ?

Uważam, że to powtarzające się pominięcie jest dość irytujące, ponieważ chcę mieć możliwość zaprojektowania własnych algorytmów adaptacyjnych z własnymi funkcjami kosztów, ale jeśli nie będę w stanie stwierdzić, czy moja funkcja kosztów daje wypukłą powierzchnię błędu, czy nie, nie będę w stanie zajmijcie się zbyt daleko, stosując coś w rodzaju zejścia gradientowego, ponieważ nie będzie globalnego minimum. Może chcę być kreatywny - może nie chcę na przykład używać najmniejszych kwadratów jako moich kryteriów błędów.

Po głębszym kopaniu (i moje pytania zaczynają się tutaj), stwierdziłem, że aby móc stwierdzić, czy masz wypukłą powierzchnię błędu, musisz upewnić się, że macierz Hesji jest półokreślona dodatnio. W przypadku matematyki symetrycznej test ten jest prosty - po prostu upewnij się, że wszystkie wartości własne macierzy Hesji są nieujemne. (Jeśli macierz nie jest symetryczna, możesz ją uczynić symetryczną, dodając ją do własnej transpozycji i wykonując ten sam test wartości własnej, na mocy Gramiana , ale to nie jest tutaj ważne).

Co to jest macierz heskańska? Matryca heskańska kodyfikuje wszystkie możliwe kombinacje częściowych funkcji kosztów. Ile jest części cząstkowych? Tyle ile funkcji w wektorze funkcji. Jak obliczyć częściowe? Weź częściowe instrumenty pochodne „ręcznie” z pierwotnej funkcji kosztów.

Tak właśnie zrobiłem: zakładam, że mamy macierz danych $m$ x , oznaczoną macierzą , gdzie oznacza liczbę przykładów, a liczbę funkcji na przykład. (która będzie również liczbą częściowych). Przypuszczam, że możemy powiedzieć, że mamy próbek czasowych i próbek przestrzennych z czujników, ale fizyczne zastosowanie nie jest tutaj zbyt ważne. $n$ $X$ $m$ $n$ $m$ $n$

Ponadto mamy również wektor o rozmiarze x . (Jest to wektor „etykiety” lub „odpowiedź” odpowiadający każdemu wierszowi ). Dla uproszczenia założyłem dla tego konkretnego przykładu. Więc 2 „przykłady” i 2 „cechy”. $y$ $m$ $1$ $X$ $m=n=2$

Załóżmy teraz, że chcesz ustalić tutaj „linię” lub wielomian najlepszego dopasowania. Oznacza to, że rzutujesz swoje funkcje danych wejściowych na wielomianowy wektor efektywny $\boldsymbol{\theta}$ tak, że twoja funkcja kosztów to:

jot (θ) = \frac{1}{2) m} \sum_{ja = 1}^{m} [θ_{0} x_{0} [ja] + θ_{1} x_{1} [ja] - y [ja]]^{2)}

$J(\theta) = \frac{1}{2m} \sum_{i=1}^{m} \bigg[\theta_{0}x_{0}[i] + \theta_{1}x_{1}[i] - y[i]\bigg]^{2}$

Weźmy teraz pierwszą pochodną częściową wrt , (funkcja 0) Tak więc: $\theta_{0}$

\frac{δ jot (θ)}{δ θ_{0}} = \frac{1}{m} \sum_{ja = 1}^{m} [θ_{0} x_{0} [ja] + θ_{1} x_{1} [ja] - y [ja]] x_{0} [ja]

$\frac{\delta J(\theta)}{\delta\theta_0} = \frac{1}{m}\sum_{i=1}^{m} \bigg[\theta_{0}x_{0}[i] + \theta_{1}x_{1}[i] - y[i]\bigg] x_{0}[i]$

\frac{δ jot (θ)}{δ θ_{0}} = \frac{1}{m} \sum_{ja = 1}^{m} [θ_{0} x_{0}^{2)} [ja] + θ_{1} x_{1} [ja] x_{0} [ja] - y [ja] x_{0} [ja]]

$\frac{\delta J(\theta)}{\delta\theta_0} = \frac{1}{m}\sum_{i=1}^{m} \bigg[\theta_{0}x_{0}^{2}[i] + \theta_{1}x_{1}[i]x_{0}[i] - y[i]x_{0}[i]\bigg]$

Teraz obliczmy wszystkie drugie częściowe, więc:

\frac{δ^{2)} jot (θ)}{δ θ_{0}^{2)}} = \frac{1}{m} \sum_{ja = 1}^{m} x_{0}^{2)} [ja]

$\frac{\delta^{2} J(\theta)}{\delta\theta_0^{2}} = \frac{1}{m}\sum_{i=1}^{m} x_{0}^{2}[i]$

\frac{δ^{2)} jot (θ)}{δ θ_{0} θ_{1}} = \frac{1}{m} \sum_{ja = 1}^{m} x_{0} [ja] x_{1} [ja]

$\frac{\delta^{2} J(\theta)}{\delta\theta_0\theta_{1}} = \frac{1}{m}\sum_{i=1}^{m} x_{0}[i]x_{1}[i]$

\frac{δ^{2)} jot (θ)}{δ θ_{1} θ_{0}} = \frac{1}{m} \sum_{ja = 1}^{m} x_{1} [ja] x_{0} [ja]

$\frac{\delta^{2} J(\theta)}{\delta\theta_1\theta_{0}} = \frac{1}{m}\sum_{i=1}^{m} x_{1}[i]x_{0}[i]$

\frac{δ^{2)} jot (θ)}{δ θ_{1}^{2)}} = \frac{1}{m} \sum_{ja = 1}^{m} x_{1}^{2)} [ja]

$\frac{\delta^{2} J(\theta)}{\delta\theta_1^{2}} = \frac{1}{m}\sum_{i=1}^{m} x_{1}^{2}[i]$

Wiemy, że Hesjan to nic innego jak:

H. (jot (θ)) = [\begin{matrix} \frac{δ^{2)} jot (θ)}{δ θ_{0}^{2)}} & \frac{δ^{2)} jot (θ)}{δ θ_{0} θ_{1}} \\ \frac{δ^{2)} jot (θ)}{δ θ_{1} θ_{0}} & \frac{δ^{2)} jot (θ)}{δ θ_{1}^{2)}} \end{matrix}]

$H(J(\theta)) = \begin{bmatrix} \frac{\delta^{2} J(\theta)}{\delta\theta_0^{2}} & \frac{\delta^{2} J(\theta)}{\delta\theta_0\theta_{1}} \\ \frac{\delta^{2} J(\theta)}{\delta\theta_1\theta_{0}} & \frac{\delta^{2} J(\theta)}{\delta\theta_1^{2}}\end{bmatrix}$

H. (jot (θ)) = [\begin{matrix} \frac{1}{m} \sum_{ja = 1}^{m} x_{0}^{2)} [ja] & \frac{1}{m} \sum_{ja = 1}^{m} x_{0} [ja] x_{1} [ja] \\ \frac{1}{m} \sum_{ja = 1}^{m} x_{1} [ja] x_{0} [ja] & \frac{1}{m} \sum_{ja = 1}^{m} x_{1}^{2)} [ja] \end{matrix}]

$H(J(\theta)) = \begin{bmatrix} \frac{1}{m}\sum_{i=1}^{m} x_{0}^{2}[i] & \frac{1}{m}\sum_{i=1}^{m} x_{0}[i]x_{1}[i] \\ \frac{1}{m}\sum_{i=1}^{m} x_{1}[i]x_{0}[i] & \frac{1}{m}\sum_{i=1}^{m} x_{1}^{2}[i] \end{bmatrix}$

Teraz, w oparciu o to, jak skonstruowałem macierz danych (moje „cechy” idą według kolumn, a moje przykłady według wierszy), wydaje się , że Hesjan jest: $X$

H. (jot (θ)) = X^{T.} X = Σ

$H(J(\theta)) = X^{T}X = \Sigma$

... co jest niczym innym jak przykładową macierzą kowariancji !

Nie jestem więc pewien, jak interpretować - a raczej powiedzieć, nie jestem pewien, jak uogólniam się tutaj. Ale myślę, że mogę powiedzieć, że:

Zawsze prawda:
- Matryca heskańska zawsze kontroluje, czy twoja powierzchnia błędu / kosztu jest wypukła.
- Jeśli macierz Hesji ma pos-semi-def, jest wypukła (i może z powodzeniem korzystać z algorytmów, takich jak opadanie gradientu, aby uzyskać optymalne rozwiązanie).
Dotyczy tylko LSE:
- Macierz Hesji dla kryterium kosztu LSE jest niczym innym jak pierwotną macierzą kowariancji. (!).
- Dla mnie oznacza to, że jeśli użyję kryterium LSE, same dane określają, czy mam powierzchnię wypukłą? ... Co zatem oznaczałoby, że wektory własne mojej macierzy kowariancji mają zdolność do „kształtowania” powierzchni kosztów? Czy to zawsze prawda? A może po prostu zadziałało w przypadku kryteriów LSE? Po prostu nie zgadza się ze mną, że wypukłość powierzchni błędu powinna zależeć od danych.

Wracając do pierwotnego pytania, w jaki sposób można ustalić, czy powierzchowność błędu (na podstawie wybranej funkcji kosztu) jest wypukła, czy nie? Czy to ustalenie opiera się na danych, czy Hesji?

Dzięki

TLDR: Jak dokładnie i praktycznie mam zająć się ustalaniem, czy moja funkcja kosztu i / lub zestaw danych dają wypukłą lub niewypukłą powierzchnię błędu?

— Spacey
źródło

Możesz myśleć o liniach najmniejszych kwadratów w jednym wymiarze. Funkcja kosztu przypomina coś w . Pierwsza pochodna (jakobowska) jest wtedy , a zatem liniowa w . Druga pochodna (heska) to - stała. $a^{2}$ $2a$ $a$ $2$

Ponieważ druga pochodna jest dodatnia, mamy do czynienia z funkcją wypukłego kosztu. Jest to równoważne z dodatnią określoną macierzą hesyjską w rachunku różniczkowym.

Masz do czynienia tylko z dwiema zmiennymi ( , ), dlatego Hesjan jest szczególnie prosty. $\theta_{1}$ $\theta_{2}$

W praktyce jednak często wiąże się to z wieloma zmiennymi, dlatego budowanie i sprawdzanie Hesji jest niepraktyczne.

Bardziej wydajną metodą jest praca bezpośrednio na macierzy jakobianu w problemie najmniejszych kwadratów: $J$

jot x = b

$Jx=b$

$J$ może mieć niedobór rang, liczbę pojedynczą lub prawie liczbę pojedynczą. W takich przypadkach kwadratowa powierzchnia funkcji kosztu jest prawie płaska i / lub bardzo rozciągnięta w pewnym kierunku. Można również stwierdzić, że macierz jest teoretycznie rozwiązalna, ale rozwiązanie jest niestabilne numerycznie. Metodę wstępnego kondycjonowania można zastosować w takich przypadkach.

Niektóre algorytmy proste uruchomienie Cholesky'iego rozkładowi z . Jeśli algorytm zawiedzie, oznacza to, że jest liczbą pojedynczą (lub źle uwarunkowaną). $J$ $J$

Liczbowo bardziej stabilny, ale droższy jest rozkład QR , który istnieje również tylko wtedy, gdy jest regularny. $J$

Wreszcie, najnowocześniejszą metodą jest rozkład wartości szczególnej (SVD) , który jest najdroższy, można go wykonać na każdej macierzy, ujawnia liczbową rangę i pozwala osobno leczyć przypadki z niedoborem rang. $J$

Napisałem artykuł o liniowych i nieliniowych rozwiązaniach najmniejszych kwadratów, który szczegółowo omawia te tematy:

Liniowe i nieliniowe najmniejsze kwadraty z Math.NET

Istnieją również odniesienia do świetnych książek, które dotyczą zaawansowanych tematów związanych z najmniejszymi kwadratami (kowariancja parametrów / punktów danych, przygotowanie wstępne, skalowanie, ortogonalna regresja odległości - całkowita najmniejszych kwadratów, określanie precyzji i dokładności estymatora najmniejszych kwadratów itp. ).

Zrobiłem przykładowy projekt artykułu, który jest open source:

LeastSquaresDemo - binarny

LeastSquaresDemo - source (C #)

— Libor
źródło

Dzięki Libor: 1) Styczny, ale wydaje się, że choleskey jest jak pierwiastek kwadratowy z macierzy, tak? 2) Nie jestem pewien, czy rozumiem twój punkt widzenia na temat tego, jak Hesjan mówi ci o wypukłości w każdym punkcie powierzchni błędu - czy ogólnie mówisz? Ponieważ z powyższego wyprowadzenia LSE, Hesjan wcale nie zależy od parametrów , a tylko od danych. Może masz na myśli ogólnie? 3) W końcu, jak ustalić, czy powierzchnia błędu jest wypukła - po prostu trzymaj się, aby upewnić się, że Hesjan jest SPD? Ale wspomniałeś, że może to zależeć od ... więc skąd można wiedzieć na pewno? Dzięki!

θ

$\theta$

θ

$\theta$

— Spacey

2) Tak, ogólnie mam na myśli. W liniowych najmniejszych kwadratach cała powierzchnia błędu ma stały Hesjan. Biorąc drugą pochodną kwadratyki jest stała, to samo dotyczy Hesji. 3) To zależy od warunkowania macierzy danych. Jeśli Hesjan jest spd, istnieje jedno zamknięte rozwiązanie, a powierzchnia błędu jest wypukła we wszystkich kierunkach. W przeciwnym razie macierz danych jest źle uwarunkowana lub pojedyncza. Nigdy nie użyłem Hesji do zbadania tego, raczej sprawdzając pojedyncze wartości macierzy danych lub sprawdzając, czy ma ona rozkład Choleskiego. Oba sposoby poinformują Cię, czy istnieje rozwiązanie.

— Libor

Libor - 1) Jeśli możesz, dodaj, jak użyłeś SVD macierzy danych lub jak użyłeś dekompozycji Choleskeya, aby sprawdzić, czy masz pojedyncze zamknięte rozwiązanie, wydają się one bardzo przydatne i jest to dobry punkt, i Byłbym ciekawy, jak się z nich korzystać. 2) Ostatnia rzecz, żeby upewnić się, że rozumiem o Hesji: Więc Hesji jest na ogół funkcją i / lub . Jeśli jest to SPD, mamy wypukłą powierzchnię. (Jeśli jednak Hesja ma w sobie , musielibyśmy to ocenić wszędzie, gdzie się wydaje). Dzięki jeszcze raz.

X

$X$

θ

$\theta$

X

$X$

θ

$\theta$

— Spacey

Mohammad: 1) Przepisałem odpowiedź i dodałem linki do mojego artykułu o Least-Squares (mogą wystąpić błędy, nie opublikowałem go jeszcze oficjalnie), w tym działający przykładowy projekt. Mam nadzieję, że pomoże ci to głębiej zrozumieć problem ... 2) W kwadratach najmniej liniowych Hesjan jest stały i zależy tylko od punktów danych. Zasadniczo zależy to również od parametrów modelu, ale dzieje się tak tylko w przypadku nieliniowych najmniejszych kwadratów.

— Libor