complexidade de ajustar modelos a dados

Suponha que sejam algumas funções contínuas $f:\mathbf{R}\times \mathbf{R} \to \mathbf{R}$

$x_1 \ldots x_n$ é um conjunto de valores reais e gostaríamos de calcular

$\text{argmin}_a \sum_i f(a,x_i)$ a precisão prescrita

Existem resultados na dificuldade desse problema para vários f?

Por exemplo, suponha que . O mínimo do nosso problema agora é a média de x, fácil de calcular. Por outro lado, suponha que , não exista uma solução de formulário fechado, então parece que argmin é mais difícil de calcular ... ou é? $f(m,x)=(m-x)^2$ $f(m,x)=\log (1+\exp(-m x))$

Motivação: esse problema de minimização surge ao ajustar modelos aos dados. O primeiro exemplo de f é o ajuste dos mínimos quadrados e o segundo f é a regressão logística.

Edit : Acabei de ver uma pergunta relacionada , e é no espírito do que eu estava perguntando, uma escolha específica de f

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

Respostas:

Quando é convexo, mesmo que não tenha um formulário fechado, você pode usar métodos de pesquisa (em um domínio limitado) para encontrar um ponto o mais próximo possível do mínimo local, que também será o mínimo global - isso funcionará para encontrar o mínimo da soma, pois a soma das funções convexas também é convexa. $f$

Existem muitos outros métodos numéricos melhores com garantias variadas (dependendo das propriedades da função) para otimizar funções convexas - este livro é uma boa referência (e gratuita!).

Lev Reyzin
fonte

Uma observação adicional: perda quadrada, perda logística e divergências de Bregman (em seu primeiro argumento) são convexas.

Lev Reyzin

Eu pensei que toda otimização convexa era fácil até que me deparei com alguns objetivos convexos nos quais tentei todos os otimizadores numéricos (incluindo o método de Newton com o exato Hessian). O problema era que o objetivo era muito plano. Solução foi usar métodos algébricas ( tinyurl.com/2dz8wky ), isto sugere que alguns problemas de optimização convexas práticos são difíceis

laroslav Bulatov

Eu acho que depende do significado de difícil / fácil. Se você tiver uma restrição de caixa no domínio, sempre poderá fazer uma pesquisa binária.

Lev Reyzin

OK, é verdade. O motivo dessa pergunta é que me surpreende que você possa usar modelos para os quais o ajuste é comprovadamente difícil, fazer uma pequena alteração na medida do ajuste e obter um modelo em que o ajuste seja fácil. (ou seja, a probabilidade máxima vs. pseudo-verossimilhança para modelos gráficos densas, ambos são estimadores consistentes, mas só um é tratável)

laroslav Bulatov

Você já deve estar ciente disso, mas se f for uma divergência de Bregman , esse argumento sempre terá uma solução fácil. A forma específica depende da ordem dos parâmetros, mas se a expressão que está sendo minimizada for

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

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

onde é uma divergência de Bregman, a resposta é sempre a média do . Se a ordem dos parâmetros for inversa, você poderá usar a dualidade das divergências de Bregman. Especificamente, se é gerado por uma função estritamente convexa , a solução é o -mean fornecido 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)$

Outro caso interessante é quando é a norma euclidiana (não ao quadrado). Nesse caso, o argumento min é o ponto Fermat-Weber bem conhecido e tem sido extensivamente estudado em pesquisa operacional. Existe um esquema iterativo globalmente ideal para resolvê-lo, mas nenhuma expressão fechada. $f$

Suresh Venkat
fonte

Interessante, não sabia disso ... você tem referência para a fórmula phi-mean? Eu estou querendo saber se isso lhe dá uma maneira mais rápida para ajustar modelos de regressão logística

Yaroslav Bulatov

a derivação é muito direta (cálculo básico, combinado com o duplo de Fenchel), mas uma referência é o artigo JMLR de Banerjee et al: jmlr.csail.mit.edu/papers/v6/banerjee05b.html

Suresh Venkat