complejidad de ajustar modelos a datos

Supongamos que $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$ es alguna función continua

$x_1 \ldots x_n$ es un conjunto de valores reales, y nos gustaría calcular

$\text{argmin}_a \sum_i f(a,x_i)$ con la precisión prescrita

¿Hay algunos resultados sobre la dificultad de este problema para varias f?

Por ejemplo, supongamos que $f(m,x)=(m-x)^2$ . El mínimo de nuestro problema ahora es la media de las x, fácil de calcular. Por otro lado, supongamos que $f(m,x)=\log (1+\exp(-m x))$ , no hay una solución de forma cerrada, por lo que parece que argmin es más difícil de calcular ... ¿o no?

Motivación: este problema de minimización surge cuando se ajustan modelos a los datos. El primer ejemplo de f es el ajuste de mínimos cuadrados y el segundo f es la regresión logística.

Editar : acabo de ver una pregunta relacionada , y está en el espíritu de lo que estaba preguntando, para una elección particular de f

approximation-algorithms machine-learning st.statistics Yaroslav Bulatov
fuente

Respuestas:

Cuando es convexo, incluso si no tiene una forma cerrada, puede usar métodos de búsqueda (en un dominio acotado) para encontrar un punto lo más cercano al mínimo local, que también será el mínimo global. - esto funcionará para encontrar el mínimo de la suma, ya que la suma de las funciones convexas también es convexa. $f$

Existen muchos otros métodos numéricos mejores con diferentes garantías (según las propiedades de la función) para optimizar las funciones convexas: este libro es una buena referencia (¡y gratuita!).

Lev Reyzin
fuente

Una nota adicional: la pérdida cuadrada, la pérdida logística y las divergencias de Bregman (en su primer argumento) son convexas.

Lev Reyzin

Pensé que toda la optimización convexa era fácil hasta que recientemente encontré algunos objetivos convexos en los que probé todos los optimizadores numéricos (incluido el método de Newton con Hessian exacto). El problema era que el objetivo era demasiado plano. La solución fue utilizar métodos algebraicos ( tinyurl.com/2dz8wky ), esto sugiere que algunos problemas prácticos de optimización convexa son difíciles

Yaroslav Bulatov

Supongo que depende del significado de difícil / fácil. Si tiene una restricción de cuadro en el dominio, siempre puede hacer una búsqueda binaria.

Lev Reyzin

OK, eso es verdad. La razón de esta pregunta es que me sorprende que pueda tomar un modelo para el que el ajuste sea demostrablemente difícil, hacer un pequeño cambio en la medida del ajuste y obtener un modelo donde el ajuste sea fácil. (es decir, máxima verosimilitud frente a pseudolimilitud para modelos gráficos densos, ambos son estimadores consistentes, pero solo uno es manejable)

Yaroslav Bulatov,

Puede que ya lo sepas, pero si f es una divergencia de Bregman , entonces este argumento siempre tiene una solución fácil. La forma específica depende del orden de los parámetros, pero si la expresión que se minimiza es

\arg min_{a} \sum_{i} f (x_{i}, a)

$\arg\min_a \sum_i f(x_i, a)$

donde es una divergencia de Bregman, entonces la respuesta es siempre la media de . Si el orden de los parámetros es al revés, puede utilizar la dualidad de las divergencias de Bregman. Específicamente, si es generado por una función estrictamente convexa , entonces la solución es significa dada por . $f$ $x_i$ $f$ $\phi$ $\phi$ $c$

\nabla ϕ (c) = (1 / n) \sum_{i} \nabla ϕ (x_{i})

$\nabla \phi(c) = (1/n)\sum_i \nabla \phi(x_i)$

Otro caso interesante es cuando es la norma euclidiana (no al cuadrado). En ese caso, el argumento mínimo es el conocido punto de Fermat-Weber , y ha sido ampliamente estudiado en investigación de operaciones. Hay un esquema iterativo globalmente óptimo para resolverlo, pero no hay una expresión de forma cerrada. $f$

Suresh Venkat
fuente

Interesante, no sabía esto ... ¿tiene referencia para la fórmula phi-mean? Me pregunto si esto ofrece una forma más rápida de ajustar los modelos de regresión logística

Yaroslav Bulatov

la derivación es muy sencilla (cálculo básico, combinado con el Fenchel dual), pero una referencia es el documento JMLR de Banerjee et al: jmlr.csail.mit.edu/papers/v6/banerjee05b.html

Suresh Venkat