Regresja penalizowana przez L1 (aka lasso) jest prezentowana w dwóch formulacjach. Niech dwie funkcje celu to
źródło
Regresja penalizowana przez L1 (aka lasso) jest prezentowana w dwóch formulacjach. Niech dwie funkcje celu to
Oba preparaty są równoważne w tym sensie, że dla każdej wartości w pierwszym preparacie istnieje wartość dla drugiego preparatu, tak że oba preparaty mają ten sam minimalizator .
Oto uzasadnienie:
Rozważmy sformułowanie lasso: Niech minimalizator będzieβ∗i niechb=| | β∗| | 1. Moje twierdzenie jest takie, że jeśli ustawiszt=bw pierwszym preparacie, wówczas rozwiązaniem pierwszego preparatu będzie równieżβ∗. Oto dowód:
beta | | beta | | 1 < | | β ∗ | | 1 = b f ( β ) < f ( β * ) β * β *
Ponieważ , uzupełniający warunek luzu jest spełniony w punkcie rozwiązania .β ∗
Tak więc, biorąc pod uwagę formułę lasso z , konstruujesz formułę ograniczoną za pomocą równego wartości normy rozwiązania lasso. I odwrotnie, biorąc pod uwagę ograniczoną formułę z , znajdziesz taką, że rozwiązanie lasso będzie równe rozwiązaniu ograniczonej formulacji.t l 1 t λ
(Jeśli wiesz o podgradientach, możesz znaleźć to , rozwiązując równanie , gdzieX T ( y - X β ∗ ) = λ z ∗
Myślę, że pomysł Elexhobby'ego na ten dowód jest dobry, ale nie sądzę, aby był całkowicie poprawny.
Zamiast tego sugeruję, abyśmy postępowali w następujący sposób:
Dla wygody oznaczmy odpowiednio przez i pierwsze i drugie sformułowanie. Załóżmy, że ma unikalne rozwiązanie, , z . Niech znajdzie rozwiązanie, . Mamy więc ten(nie może być większy z powodu ograniczenia), a zatem . Jeśli to nie jest rozwiązaniem , co jest sprzeczne z naszymi założeniami. JeśliP 2 P 2 β * ‖ β * ‖ = b P 1 β ≠ β * ‖ βP1 P2 P2 β∗ ∥β∗∥=b P1 β^≠β∗ F ( β ) ≤ f ( β * ) f ( β ) < f ( β * ) β * P 2 f ( β )∥β^∥≤∥β∗∥ f(β^)≤f(β∗) f(β^)<f(β∗) β∗ P2 β = β *f(β^)=f(β∗) następnie , ponieważ założyliśmy, że rozwiązanie jest unikalne.β^=β∗
Może się jednak zdarzyć, że Lasso ma wiele rozwiązań. Z lematu 1 arxiv.org/pdf/1206.0313.pdf wiemy, że wszystkie te rozwiązania mają tę samą -norm (i oczywiście tę samą wartość minimalną). Ustawiamy tę normę jako ograniczenie dla i kontynuujemy.P 1ℓ1 P1
Oznaczmy przez zbiorem rozwiązań z . Niech ma rozwiązanie, . Mamy więc ten , a zatem . Jeśli dla niektórych (a stąd dla wszystkich), to , co jest sprzeczne z naszymi założeniami. Jeśli dla niektórych to nie jest zbiorem rozwiązańP 2 ‖ β ‖ = b ∀ β ∈ S P 1 β ∉ S ‖ β ‖ ≤ f ( β ) < f ( β ) β ∈ S S P 2 P 1 S P 1 P 2S P2 ∥β∥=b ∀β∈S P1 β^∉S ∥β^∥≤∥β∥∀β∈S f(β^)≤f(β)∀β∈S f(β^)=f(β) β∈S β^∈S f(β^)<f(β) β∈S S P2 . Dlatego każde rozwiązanie jest w , tzn. Każde rozwiązanie jest również rozwiązaniem . Pozostałoby udowodnić, że komplementarne również ma miejsce.P1 S P1 P2
źródło