Implementación de regresión de cresta: ¿Seleccionar una cuadrícula inteligente para

Estoy implementando la Regresión de Ridge en un módulo Python / C, y me he encontrado con este "pequeño" problema. La idea es que quiero muestrear los grados efectivos de libertad más o menos equidistantes (como el gráfico de la página 65 en los "Elementos de aprendizaje estadístico" ), es decir, muestra:

d f (λ) = \sum_{i = 1}^{p} \frac{d_{i}^{2}}{d_{i}^{2} + λ},

$\mathrm{df}(\lambda)=\sum_{i=1}^{p}\frac{d_i^2}{d_i^2+\lambda},$

d_{i}^{2}

$d_i^2$

X^{T} X

$X^TX$

d f (λ_{max}) \approx 0

$\mathrm{df}(\lambda_{\max})\approx 0$

d f (λ_{min}) = p

$\mathrm{df}(\lambda_{\min})=p$

λ_{max} = \sum_{i}^{p} d_{i}^{2} / c

$\lambda_{\max}=\sum_i^p d_i^2/c$

λ_{max} ≫ d_{i}^{2}

$\lambda_{\max} \gg d_i^2$

c

$c$

c = 0.1

$c=0.1$

λ_{min} = 0

$\lambda_{\min}=0$

Como sugiere el título, entonces, necesito muestrear de a en alguna escala tal que se muestree (aproximadamente), digamos, en intervalos de a ... ¿hay una manera fácil de hacer esto? Pensé en resolver la ecuación para cada usando un método Newton-Raphson, pero esto agregará demasiadas iteraciones, especialmente cuando es grande. ¿Alguna sugerencia? $\lambda$ $\lambda_{\min}$ $\lambda_{\max}$ $\mathrm{df}(\lambda)$ $0.1$ $c$ $p$ $\mathrm{df}(\lambda)$ $\lambda$ $p$

ridge-regression Néstor
fuente

Esta función es una función racional convexa decreciente de . Las raíces, particularmente si se eligen sobre una cuadrícula diádica, deben ser muy rápidas de encontrar.

λ \geq 0

$\lambda \geq 0$

cardenal

@ cardinal, probablemente tengas razón. Sin embargo, si es posible, me gustaría saber si hay alguna cuadrícula "predeterminada". Por ejemplo, intenté obtener una grilla haciendo , donde , y funcionó bastante bien para algunos grados de libertad, pero como , explotó. Esto me hizo preguntarme si tal vez había alguna forma ordenada de elegir la cuadrícula para , que es lo que estoy preguntando. Si esto no existe, también estaría feliz de saberlo (ya que podría dejar felizmente el método Newton-Rapson en mi código sabiendo que "no existe una mejor manera").

λ = l o g (s) λ_{m a x} / l o g (s_{m a x})

$\lambda=log(s)\lambda_{max}/log(s_{max})$

s = (1, 2, . . ., s_{m a x})

$s=(1,2,...,s_{max})$

d f (λ) \to p

$df(\lambda)\to p$

λ

$\lambda$

Néstor

Para tener una mejor idea de las posibles dificultades con las que se encuentra, ¿cuáles son los valores típicos y en el peor de los casos de

? ¿Hay algo que usted sepa a priori sobre la distribución de valores propios?

p

$p$

cardenal

@cardinal, los valores típicos de

en mi aplicación oscilarían entre

, pero quiero que sea lo más general posible. Sobre la distribución del valor propio, no mucho en realidad.

es una matriz que contiene predictores en sus columnas, que no siempre son ortogonales.

p

$p$

15

$15$

40

$40$

X

$X$

Néstor

Newton-Raphson típicamente encuentra raíces a

precisión dentro de

pasos para

y pequeños valores de

; Casi nunca más de

pasos. Para valores mayores, ocasionalmente se necesitan hasta

pasos. Como cada paso requiere cálculos de

, la cantidad total de cómputo es intrascendente. De hecho, el número de pasos no parece depender de

si se elige un buen valor inicial (elijo el que usaría si todo el

10^{- 12}

$10^{-12}$

3

$3$

4

$4$

p = 40

$p=40$

d f (λ)

$df(\lambda)$

6

$6$

30

$30$

O (p)

$O(p)$

p

$p$

d_{i}

$d_i$ igual a su media).

whuber

Esta es una respuesta larga . Entonces, demos una versión de cuento corto aquí.

No hay una buena solución algebraica para este problema de búsqueda de raíces, por lo que necesitamos un algoritmo numérico.
La función tiene muchas propiedades agradables. Podemos aprovecharlos para crear una versión especializada del método de Newton para este problema con convergencia monotónica garantizada a cada raíz. $\mathrm{df}(\lambda)$
Incluso el Rcódigo con muerte cerebral sin ningún intento de optimización puede calcular una cuadrícula de tamaño 100 con en unos pocos segundos. Uncódigoescrito cuidadosamentereduciría esto en al menos 2–3 órdenes de magnitud. $p = 100\,000$ C

A continuación se detallan dos esquemas para garantizar la convergencia monotónica. Uno usa los límites que se muestran a continuación, que parecen ayudar a salvar un paso de Newton o dos en ocasiones.

Ejemplo : y una cuadrícula uniforme para los grados de libertad de tamaño 100. Los valores propios están distribuidos por Pareto, por lo tanto, muy sesgados. A continuación hay tablas de la cantidad de pasos de Newton para encontrar cada raíz. $p = 100\,000$

# Table of Newton iterations per root.
# Without using lower-bound check.
  1  3  4  5  6 
  1 28 65  5  1 
# Table with lower-bound check.
  1  2  3 
  1 14 85

No habrá una solución de forma cerrada para este , en general, pero no es una gran cantidad de estructura actual que se puede utilizar para producir soluciones muy eficaces y seguros utilizando métodos de búsqueda de raíz estándar.

Antes de profundizar demasiado en las cosas, recopilemos algunas propiedades y consecuencias de la función

d f (λ) = \sum_{i = 1}^{p} \frac{d_{i}^{2}}{d_{i}^{2} + λ} .

$\newcommand{\df}{\mathrm{df}} \df(\lambda) = \sum_{i=1}^p \frac{d_i^2}{d_i^2 + \lambda} \>.$

Propiedad 0 : es una función racional de . (Esto es evidente a partir de la definición). Consecuencia 0 : No existirá una solución algebraica general para encontrar la raíz . Esto se debe a que existe un problema equivalente de búsqueda de raíces polinomiales de grado por lo que si no es extremadamente pequeño (es decir, menos de cinco), no existirá una solución general. Entonces, necesitaremos un método numérico. $\df$ $\lambda$
$\df(\lambda) - y = 0$ $p$ $p$

Propiedad 1 : La función es convexa y disminuye en . (Tome derivados.) Consecuencia 1 (a) : el algoritmo de búsqueda de raíces de Newton se comportará muy bien en esta situación. Sean los grados de libertad deseados y la raíz correspondiente, es decir, . En particular, si comenzamos con cualquier valor inicial (entonces, $\df$ $\lambda \geq 0$
$y$ $\lambda_0$ $y = \df(\lambda_0)$ $\lambda_1 < \lambda_0$ ), entonces la secuencia de iteraciones de Newton-paso convergerámonotónicamentea la solución única . Consecuencia 1 (b): Además, si con , entonces elprimerpaso produciría $\df(\lambda_1) > y$ $\lambda_1,\lambda_2,\ldots$ $\lambda_0$
$\lambda_1 > \lambda_0$ $\lambda_2 \leq \lambda_0$ , de donde se incrementará monotónicamente a la solución por la consecuencia previa (ver advertencia más abajo). Intuitivamente, este último hecho es consecuencia de que si nos ponemos a la derecha de la raíz, la derivada es "demasiado" superficial debido a la convexidad de por lo que el primer paso Newton nos llevará algún lugar a la izquierda de la raíz. Nota: dado que no es en general convexo para negativo , esto proporciona una fuerte razón para preferir comenzar a la izquierda de la raíz deseada. De lo contrario, debemos verificar que el paso de Newton no haya resultado en un valor negativo para la raíz estimada, lo que puede colocarnos en algún lugar en una porción no convexa de . $\df$ $\df$ $\lambda$ $\df$
Consecuencia 1 (c) : una vez que hemos encontrado la raíz de algunos y estamos buscando la raíz de algunos , usamos tal que como nuestra suposición inicial garantiza que comenzamos a la izquierda de la segunda raíz. Entonces, nuestra convergencia está garantizada para ser monótona a partir de ahí. $y_1$ $y_2 < y_1$ $\lambda_1$ $\df(\lambda_1) = y_1$

Propiedad 2 : existen límites razonables para proporcionar puntos de partida "seguros". Usando argumentos de convexidad y la desigualdad de Jensen, tenemos los siguientes límites Consecuencia 2: Esto nos dice que la raíz satisface obedece a

\frac{p}{1 + \frac{λ}{p} \sum d_{i}^{- 2}} \leq d f (λ) \leq \frac{p \sum_{i} d_{i}^{2}}{\sum_{i} d_{i}^{2} + p λ} .

$\frac{p}{1+ \frac{\lambda}{p}\sum d_i^{-2}} \leq \df(\lambda) \leq \frac{p \sum_i d_i^2}{\sum_i d_i^2 + p \lambda} \>.$

λ_{0}

$\lambda_0$

d f (λ_{0}) = y

$\df(\lambda_0) = y$

Entonces, hasta una constante común, hemos intercalado la raíz entre los medios armónicos y aritméticos de

\begin{matrix} (⋆) & \frac{1}{\frac{1}{p} \sum_{i} d_{i}^{- 2}} (\frac{p - y}{y}) \leq λ_{0} \leq (\frac{1}{p} \sum_{i} d_{i}^{2}) (\frac{p - y}{y}) . \end{matrix}

$\frac{1}{\frac{1}{p}\sum_i d_i^{-2}}\left(\frac{p - y}{y}\right) \leq \lambda_0 \leq \left(\frac{1}{p}\sum_i d_i^2\right) \left(\frac{p - y}{y}\right) \>. \tag{$\star$}$

d_{i}^{2}

$d_i^2$

Esto supone que para todo . Si este no es el caso, entonces el mismo límite se mantiene considerando solo el positivo y reemplazando por el número de positivo . NB : Dado que asumiendo todos , entonces , de donde los límites son siempre no triviales (por ejemplo, el límite inferior siempre no es negativo). $d_i > 0$ $i$ $d_i$ $p$ $d_i$ $\df(0) = p$ $d_i > 0$ $y \in (0,p]$

Aquí hay una gráfica de un ejemplo "típico" de con . Hemos superpuesto una cuadrícula de tamaño 10 para los grados de libertad. Estas son las líneas horizontales en la trama. Las líneas verdes verticales corresponden al límite inferior en . $\df(\lambda)$ $p = 400$ $(\star)$

Example dof plot with grid and bounds

Un algoritmo y algún código R de ejemplo

Un algoritmo muy eficiente dado una grilla de grados de libertad deseados en es ordenarlos en orden decreciente y luego encontrar secuencialmente la raíz de cada uno, utilizando la raíz anterior como punto de partida para el siguiente. Podemos refinar esto aún más comprobando si cada raíz es mayor que el límite inferior para la siguiente raíz y, si no, podemos comenzar la siguiente iteración en el límite inferior. $y_1, \ldots y_n$ $(0,p]$

Aquí hay un código de ejemplo R, sin intentos de optimizarlo. Como se ve a continuación, todavía es bastante rápido, aunque Res, por decirlo cortésmente, horriblemente, terriblemente, muy lento en los bucles.

# Newton's step for finding solutions to regularization dof.

dof <- function(lambda, d) { sum(1/(1+lambda / (d[d>0])^2)) }
dof.prime <- function(lambda, d) { -sum(1/(d[d>0]+lambda / d[d>0])^2) }

newton.step <- function(lambda, y, d)
{ lambda - (dof(lambda,d)-y)/dof.prime(lambda,d) }

# Full Newton step; Finds the root of y = dof(lambda, d).
newton <- function(y, d, lambda = NA, tol=1e-10, smart.start=T)
{
    if( is.na(lambda) || smart.start )
        lambda <- max(ifelse(is.na(lambda),0,lambda), (sum(d>0)/y-1)/mean(1/(d[d>0])^2))
    iter <- 0
    yn   <- Inf
    while( abs(y-yn) > tol )
    {
        lambda <- max(0, newton.step(lambda, y, d)) # max = pedantically safe
        yn <- dof(lambda,d)
        iter = iter + 1
    }
    return(list(lambda=lambda, dof=y, iter=iter, err=abs(y-yn)))
}

$d_i$ $d_i^2$

newton.grid <- function(ygrid, d, lambda=NA, tol=1e-10, smart.start=TRUE)
{
    p <- sum(d>0)
    if( any(d < 0) || all(d==0) || any(ygrid > p) 
        || any(ygrid <= 0) || (!is.na(lambda) && lambda < 0) )
        stop("Don't try to fool me. That's not nice. Give me valid inputs, please.")
    ygrid <- sort(ygrid, decreasing=TRUE)
    out    <- data.frame()
    lambda <- NA
    for(y in ygrid)
    {
        out <- rbind(out, newton(y,d,lambda, smart.start=smart.start))
        lambda <- out$lambda[nrow(out)]
    }
    out
}

Llamada de función de muestra

set.seed(17)
p <- 100000
d <- sqrt(sort(exp(rexp(p, 10)),decr=T))
ygrid <- p*(1:100)/100
# Should take ten seconds or so.
out <- newton.grid(ygrid,d)

cardenal
fuente

Favoreciendo la pregunta para que pueda volver a consultar esta respuesta. Gracias por publicar este análisis detallado, cardenal.

Macro

Increíble respuesta :-), muchas gracias cardenal por las sugerencias Y la respuesta.

Néstor

Implementación de regresión de cresta: ¿Seleccionar una cuadrícula inteligente para

Respuestas: