La regresión penalizada L1 (también conocida como lazo) se presenta en dos formulaciones. Deje que las dos funciones objetivas sean
fuente
La regresión penalizada L1 (también conocida como lazo) se presenta en dos formulaciones. Deje que las dos funciones objetivas sean
Las dos formulaciones son equivalentes en el sentido de que para cada valor de en la primera formulación, existe un valor de para la segunda formulación de tal manera que las dos formulaciones tienen el mismo minimizador .
Aquí está la justificación:
Considere la formulación del lazo: Deje que el minimizador seaβ∗y deje queb=| El | β∗| El | 1. Mi afirmación es que si establecet=ben la primera formulación, entonces la solución de la primera formulación también seráβ∗. Aquí está la prueba:
ß | El | ß | El | 1<| El | β∗| El | 1=bf( β )<f(β*)β*β*
Como , la condición de holgura complementaria se cumple en el punto de solución .β ∗
Entonces, dada una formulación de lazo con , construyes una formulación restringida usando una igual al valor de la norma de la solución de lazo. Por el contrario, dada una formulación restringida con , encontrará una tal que la solución al lazo será igual a la solución de la formulación restringida.t l 1 t λ
(Si conoce subgraduados, puede encontrar este resolviendo la ecuación , dondeX T ( y - X β ∗ ) = λ z ∗ z ∗ ∈ ∂ | El | β ∗ | El | 1 )
Creo que la idea de Elexhobby para esta prueba es buena, pero no creo que sea completamente correcta.
Al demostrar que existe una solución para la primera formulación, , de modo queconduce a una contradicción, solo podemos asumir la necesidad de, no eso . ‖ β ‖<‖β*‖‖ β ‖=‖β*‖ β =β*β^ ∥β^∥<∥β∗∥ ∥β^∥=∥β∗∥ β^=β∗
Sugiero, en cambio, que procedamos de la siguiente manera:
Por conveniencia, por y la primera y segunda formulación respectivamente. Supongamos que tiene una solución única, , con . Deje que tenga una solución, . Entonces, tenemos que(no puede ser mayor debido a la restricción) y, por lo tanto, . Si entonces no es la solución para , lo que contradice nuestras suposiciones. SiP 2 P 2 β ∗ ‖ β ∗ ‖ = b P 1P1 P2 P2 β∗ ∥β∗∥=b P1 ‖ β ‖≤‖β*‖f( β )≤f(β*)f( β )<f(β*)β*P2f( ββ^≠β∗ ∥β^∥≤∥β∗∥ f(β^)≤f(β∗) f(β^)<f(β∗) β∗ P2 β = β *f(β^)=f(β∗) entonces , ya que asumimos que la solución es única.β^=β∗
Sin embargo, puede darse el caso de que el lazo tenga múltiples soluciones. Según el lema 1 de arxiv.org/pdf/1206.0313.pdf , sabemos que todas estas soluciones tienen la misma -norm (y el mismo valor mínimo, por supuesto). Establecemos esa norma como la restricción para y procedemos.P 1ℓ1 P1
Vamos a denotar por el conjunto de soluciones a , con . Dejar que tiene una solución, . Entonces, tenemos que y por lo tanto . Si para algunos (y, por lo tanto, para todos ellos), entonces , lo que contradice nuestras suposiciones. Si para algunos entonces no es el conjunto de soluciones paraP 2 ‖ β ‖ = b ∀ β ∈ S P 1 f ( β ) < f ( β ) β ∈ S S P 2 P 1 S P 1 P 2S P2 ∥β∥=b ∀β∈S P1 ‖ β ‖≤‖β‖∀β∈Sf( β )≤f(β)∀β∈Sf( β )=f(β)β∈S β ∈Sβ^∉S ∥β^∥≤∥β∥∀β∈S f(β^)≤f(β)∀β∈S f(β^)=f(β) β∈S β^∈S f(β^)<f(β) β∈S S P2 . Por lo tanto, cada solución a está en , es decir, cualquier solución a también es una solución a . Quedaría por demostrar que lo complementario se mantiene también.P1 S P1 P2
fuente