Czy współczynnik błędów jest funkcją wypukłą parametru regulowania lambda?

Wybierając parametr regulowania lambda w Ridge lub Lasso, zalecaną metodą jest wypróbowanie różnych wartości lambda, zmierzenie błędu w zbiorze walidacyjnym i wybranie wartości lambda, która zwraca najmniejszy błąd.

Nie jest dla mnie kłamstwem, jeśli funkcja f (lambda) = error jest wypukła. Czy może tak być? To znaczy, że ta krzywa może mieć więcej niż jeden lokalny minim (co oznaczałoby, że znalezienie minimum błędu w pewnym regionie lambda nie wyklucza możliwości, że w innym regionie lambda zwraca jeszcze mniejszy błąd)

Twoja rada będzie mile widziana.

— rf7
źródło

Odpowiedzi:

Pierwotne pytanie brzmiało, czy funkcja błędu musi być wypukła. Nie. Przedstawiona poniżej analiza ma na celu zapewnienie wglądu i intuicji na temat tego i zmodyfikowanego pytania, które pyta, czy funkcja błędu może mieć wiele lokalnych minimów.

Intuicyjnie między danymi a zestawem treningowym nie musi istnieć żadna matematycznie niezbędna zależność. Powinniśmy być w stanie znaleźć dane treningowe, dla których model początkowo jest słaby, poprawia się z pewną regularyzacją, a następnie znów się pogarsza. Krzywa błędu nie może być w tym przypadku wypukła - przynajmniej nie, jeśli zmienimy parametr regularyzacji w zakresie od do . $0$ $\infty$

Pamiętaj, że wypukłe nie jest równoznaczne z posiadaniem unikalnego minimum! Jednak podobne pomysły sugerują, że możliwe jest uzyskanie wielu lokalnych minimów: podczas regulacji najpierw dopasowany model może ulec poprawie w przypadku niektórych danych treningowych, ale nie zmienia się znacząco w przypadku innych danych treningowych, a następnie poprawi się w przypadku innych danych treningowych itp. Odpowiedni połączenie takich danych szkoleniowych powinno dać wiele lokalnych minimów. Aby uprościć analizę, nie zamierzam tego pokazywać.

Edytuj (aby odpowiedzieć na zmienione pytanie)

Byłem tak pewny przedstawionej poniżej analizy i stojącej za nią intuicji, że postanowiłem znaleźć przykład w najokrutniejszy możliwy sposób: wygenerowałem małe losowe zestawy danych, uruchomiłem na nich Lasso, obliczyłem całkowity błąd kwadratowy dla małego zestawu treningowego, i wykreślił krzywą błędów. Kilka prób dało jeden z dwoma minimami, które opiszę. Wektory mają postać dla cech i oraz odpowiedzi . $(x_1,x_2,y)$ $x_1$ $x_2$ $y$

Dane treningowe

(1, 1, - 0.1), (2, 1, 0.8), (1, 2, 1.2), (2, 2, 0.9)

$(1,1,-0.1),\ (2,1,0.8),\ (1,2,1.2),\ (2,2,0.9)$

Dane testowe

(1, 1, 0.2), (1, 2, 0.4)

$(1,1,0.2),\ (1,2,0.4)$

glmnet::glmmetR $\lambda$ $1/\lambda$

Krzywa błędu z wieloma lokalnymi minimami

Analiza

$\beta=(\beta_1, \ldots, \beta_p)$ $x_i$ $y_i$

$\lambda \in [0, \infty)$ $\lambda=0$
$\hat\beta$ $\lambda$ $\hat\beta$
$\lambda\to\infty$ $\hat\beta\to 0$
$x$ $\hat\beta\to 0$ $\hat y(x) = f(x, \hat\beta) \to 0$
$y$ $\hat y$ $\mathcal{L}(y, \hat y)$ $|\hat y - y|$ $\mathcal{L}(|\hat y - y|)$

$(4)$

$\hat\beta(0)$ $(x_0, y_0)$ $f(x_0, \hat\beta(0))\ne 0$ $x_0$ $y_0=f(x_0, \hat\beta(0))/2$

$e: \lambda \to \mathcal{L}(y_0, f(x_0, \hat\beta(\lambda))$

$e(0) = \mathcal{L}(y_0, f(x_0, \hat\beta(0)) = \mathcal{L}(y_0, 2y_0) = \mathcal{L}(|y_0|)$ $y_0$
$\lim_{\lambda\to\infty}e(\lambda) = \mathcal{L}(y_0, 0) = \mathcal{L}(|y_0|)$ $\lambda\to\infty$ $\hat\beta(\lambda)\to 0$ $\hat{y}(x_0)\to 0$

Zatem jego wykres w sposób ciągły łączy dwa równie wysokie (i skończone) punkty końcowe.

Jakościowo istnieją trzy możliwości:

Prognozy dla zestawu treningowego nigdy się nie zmieniają. Jest to mało prawdopodobne - prawie każdy wybrany przykład nie będzie miał tej właściwości.
Niektóre prognozy pośrednie dla są gorsze niż na początku lub w granicy . Ta funkcja nie może być wypukła. $0\lt \lambda \lt \infty$ $\lambda=0$ $\lambda\to\infty$
Wszystkie prognozy pośrednie mieszczą się w przedziale od do 2 . Ciągłość oznacza, że będzie co najmniej jedno minimum , w pobliżu którego musi być wypukłe. Ale ponieważ zbliża się do skończonej stałej asymptotycznie, nie może być wypukła dla wystarczająco dużej . $0$ $2y_0$ $e$ $e$ $e(\lambda)$ $\lambda$

Pionowa linia przerywana na rysunku pokazuje, gdzie wykres zmienia się z wypukłego (po lewej) na niewypukły (po prawej). (Istnieje również region niewypukłości w pobliżu na tej figurze, ale niekoniecznie tak będzie w ogóle.) $\lambda\approx 0$

— Whuber
źródło

Dziękuję za twoją wyszukaną odpowiedź. Jeśli to możliwe, przejrzyj edytowane pytanie i zaktualizuj swoją odpowiedź.

— rf7,

Świetna odpowiedź (+1). W praktyce myślę, że często nie ma tak niewielu punktów danych szkoleniowych i testowych. Czy wniosek tej odpowiedzi zmienia się, gdy jest wystarczająca liczba punktów danych szkoleniowych i testowych zaczerpniętych z tego samego (stałego i wystarczająco regularnego) rozkładu? W szczególności, czy w tym scenariuszu istnieje unikalne lokalne minimum o wysokim prawdopodobieństwie?

— user795305

@Ben Nie liczy się liczba punktów testowych: wynik zależy wyłącznie od rozkładu punktów testowych w stosunku do rozmieszczenia punktów treningowych. Dlatego kwestia „z dużym prawdopodobieństwem” nie będzie możliwa bez pewnych konkretnych założeń dotyczących wielowymiarowego rozkładu zmiennych regresora. Ponadto, przy wielu zmiennych, zjawisko wielu lokalnych minimów będzie znacznie bardziej prawdopodobne. I podejrzewam, że losowy wybór dużego zestawu testowego (z wiele razy tyle obserwacje jak zmienne) mogą często mieć unikalną globalną min.

— whuber

@whuber Thanks! Zgadzam się: (prawdziwa) dystrybucja między punktami treningowymi a testowymi powinna być taka sama i musi istnieć wystarczająca ilość próbek, aby rozkłady empiryczne zestawu szkoleniowego i testowego były zgodne. (Wydaje się, że źle to sformułowałem w moim wcześniejszym komentarzu.) Na przykład, jeśli ma wspólnie normalny rozkład (z kowariancją niedegenerowaną), podejrzewam, że prawdopodobieństwo wystąpienia krzywej błędu o unikalnej lokalnej wartości minimalnej jest zbieżne z 1 (w przypadku, na przykład, jest próbki w treningu i zbiór testowy z z stałe (lub nawet wzrasta powoli, w stosunku do ))

(x, y)

$(\mathbf x, y)$

n

$n$

n \to \infty

$n \to \infty$

p

$p$

n

$n$

— user795305

$\newcommand{\dbeta}{\frac{\partial}{\partial \lambda} \hat\beta_\lambda}$ $\newcommand{\ddbeta}{\frac{\partial^2}{{\partial \lambda}^2} \hat\beta_\lambda}$

Ta odpowiedź dotyczy w szczególności lasso (i nie dotyczy regresji grzbietu).

Ustawiać

Załóżmy, że mamy zmienne , których używamy do modelowania odpowiedzi. Załóżmy, że mamy punktów danych treningowych i punktów danych walidacyjnych. $p$ $n$ $m$

Niech wejściem szkolenia będzie a odpowiedzią będzie . Użyjemy lasso na tych danych treningowych. To znaczy, włóż rodzina współczynników oszacowana na podstawie danych treningowych. Wybierzemy, który być używany jako nasz estymator na podstawie jego błędu w zestawie sprawdzania poprawności, z wejściem i odpowiedzią . Z $X_{(1)} \in \mathbb{R}^{n \times p}$ $y_{(1)} \in \mathbb{R}^n$

\begin{matrix} (1) & {\hat{β}}_{λ} = \arg min_{β \in R^{p}} ‖ y_{(1)} - X_{(1)} β ‖_{2}^{2} + λ ‖ β ‖_{1}, \end{matrix}

$\hat\beta_\lambda = \arg\min_{\beta \in \mathbb{R}^p} \|y_{(1)} - X_{(1)} \beta\|_2^2 + \lambda \|\beta\|_1, \tag{1}$

{\hat{β}}_{λ}

$\hat\beta_\lambda$

X_{(2)} \in R^{m \times p}

$X_{(2)} \in \mathbb{R}^{m \times p}$

y_{(2)} \in R^{m}

$y_{(2)} \in \mathbb{R}^m$

\begin{matrix} (2) & \hat{λ} = \arg min_{λ \in R_{+}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}, \end{matrix}

$\hat\lambda = \arg\min_{\lambda \in \mathbb{R}_+} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2, \tag{2}$ jesteśmy zainteresowani badaniem funkcji błędu która daje podstawę do naszego estymatora opartego na danych .

e (λ) = ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2}

$e(\lambda) = \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2$

{\hat{β}}_{\hat{λ}}

$\hat\beta_{\hat\lambda}$

Obliczenie

Teraz będzie obliczyć drugą pochodną celem określonym w równaniu , bez żadnych dystrybucyjne założenia na „S lub ” y. Używając różnicowania i pewnej reorganizacji, (formalnie) obliczamy, że $(2)$ $X$ $y$

\begin{aligned} \frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} & = \frac{\partial}{\partial λ} {- 2 y_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} + 2 {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ}} \\ = - 2 y_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 {({\hat{β}}_{λ})}^{T} X_{(2)}^{T} X_{(2)} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} + 2 \frac{\partial}{\partial λ} {\hat{β}}_{λ}^{T} X_{(2)}^{T} X_{(2)}^{T} \frac{\partial}{\partial λ} {\hat{β}}_{λ} \\ = - 2 {{(y_{(2)} - X_{(2)} {\hat{β}}_{λ})}^{T} \frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ} - ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2}} . \end{aligned}

$\begin{align*} \frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 & = \frac{\partial}{\partial \lambda} \left\{ -2 y_{(2)}^T X_{(2)} \dbeta + 2 \hat\beta_\lambda^T X_{(2)}^T X_{(2)} \dbeta \right\} \\ & = -2 y_{(2)}^T X_{(2)} \ddbeta + 2 \left( \hat\beta_\lambda \right)^T X_{(2)}^T X_{(2)} \ddbeta + 2 \dbeta^T X_{(2)}^T X_{(2)}^T \dbeta \\ & = -2 \left\{ \left( y_{(2)} - X_{(2)} \hat\beta_\lambda \right)^T \ddbeta - \|X_{(2)} \dbeta\|_2^2 \right\}. \end{align*}$ Ponieważ jest liniowo dla (ponieważ jest skończonym zestawem węzłów na ścieżce rozwiązania lasso), pochodna jest częściowo stała, a wynosi zero dla wszystkich . Dlatego nieujemna funkcja .

{\hat{β}}_{λ}

$\hat\beta_\lambda$

λ \notin K

$\lambda \not\in K$

K

$K$

\frac{\partial}{\partial λ} {\hat{β}}_{λ}

$\dbeta$

\frac{\partial^{2}}{{\partial λ}^{2}} {\hat{β}}_{λ}

$\ddbeta$

λ \notin K

$\lambda \not\in K$

\frac{\partial^{2}}{{\partial λ}^{2}} ‖ y_{(2)} - X_{(2)} {\hat{β}}_{λ} ‖_{2}^{2} = 2 ‖ X_{(2)} \frac{\partial}{\partial λ} {\hat{β}}_{λ} ‖_{2}^{2},

$\frac{\partial^2}{{\partial \lambda}^2} \|y_{(2)} - X_{(2)} \hat\beta_\lambda\|_2^2 = 2 \|X_{(2)} \dbeta\|_2^2,$

λ

$\lambda$

Wniosek

Jeśli przyjmiemy dalej, że jest pobierane z jakiegoś ciągłego rozkładu niezależnego od , wektor prawie na pewno dla . Dlatego funkcja błędu ma drugą pochodną na która jest (prawie na pewno) ściśle dodatnia. Jednak wiedząc, że jest ciągły, wiemy, że błąd sprawdzania poprawności jest ciągły. $X_{(2)}$ $\{X_{(1)}, y_{(1)} \}$ $X_{(2)} \dbeta \neq 0$ $\lambda < \lambda_\max$ $e(\lambda)$ $\mathbb{R} \setminus K$ $\hat\beta_\lambda$ $e(\lambda)$

Wreszcie z lasso dual wiemy, że zmniejsza się monotonicznie wraz ze wzrostem . Jeśli uda nam się ustalić, że jest również monotoniczny, to następuje silna wypukłość . Jest to jednak prawdopodobne, że zbliża się do jednego, jeśli . (Wkrótce uzupełnię informacje tutaj.) $\|X_{(1)} \hat\beta_\lambda\|_2^2$ $\lambda$ $\|X_{(2)} \hat\beta_\lambda\|_2^2$ $e(\lambda)$ $\mathcal{L} \left( X_{(1)} \right) = \mathcal{L} \left( X_{(2)} \right)$

— użytkownik795305
źródło

Możesz polegać tylko na tym, że jest ciągłą, liniową, częściową funkcją aby stwierdzić, że jest ściśle wypukły. Zobaczmy, czy to odliczenie jest ogólnie ważne. Jedną z takich funkcji jest(gdzie oznacza zaokrąglenie do najbliższej liczby całkowitej). Załóżmy, że i , aby . Ta funkcja błędu ma nieskończenie wiele lokalnych minimów. Nie jest wypukły - jest wypukły wszędzie, z wyjątkiem pojedynczych punktów! To prowadzi mnie do przekonania, że przyjmujesz dodatkowe niepotwierdzone założenia.

\hat{β}

$\hat\beta$

λ

$\lambda$

\hat{e}

$\hat e$

\hat{β} (λ) = | λ - [λ] |

$\hat\beta(\lambda)=|\lambda-[\lambda]|$

[]

$[]$

y_{(2)} = 0

$y_{(2)}=0$

X_{(2)} = 1

$X_{(2)}=1$

\hat{e} (λ) = \hat{β} (λ)^{2}

$\hat {e}(\lambda)=\hat\beta(\lambda)^2$

— Whuber

@whuber Dobra uwaga! Dzięki! Niedługo będę edytować ten post.

— user795305