Por que o método de Newton não é amplamente utilizado no aprendizado de máquina?

Isso é algo que me incomoda há um tempo e eu não consegui encontrar respostas satisfatórias online, então aqui vai:

Depois de revisar um conjunto de palestras sobre otimização convexa, o método de Newton parece ser um algoritmo muito superior ao da descida do gradiente para encontrar soluções globalmente ótimas, porque o método de Newton pode fornecer uma garantia para sua solução, é invariante afim e, acima de tudo, converge. muito menos etapas. Por que algoritmos de otimização de segunda ordem, como o método de Newton, não são tão amplamente utilizados como a descida estocástica do gradiente em problemas de aprendizado de máquina?

A descida em gradiente maximiza uma função usando o conhecimento de sua derivada. O método de Newton, um algoritmo de busca de raiz, maximiza uma função usando o conhecimento de sua segunda derivada. Isso pode ser mais rápido quando a segunda derivada é conhecida e fácil de calcular (o algoritmo de Newton-Raphson é usado na regressão logística). No entanto, a expressão analítica para a segunda derivada é frequentemente complicada ou intratável, exigindo muita computação. Os métodos numéricos para calcular a segunda derivada também exigem muita computação - se forem necessários valores de para calcular a primeira derivada, N 2 será necessário para a segunda derivada.$N$$N^2$

Mais pessoas devem usar o método de Newton no aprendizado de máquina *. Digo isso como alguém com experiência em otimização numérica, que se interessou por aprendizado de máquina nos últimos dois anos.

As desvantagens nas respostas aqui (e mesmo na literatura) não são um problema se você usar o método de Newton corretamente. Além disso, as desvantagens que importam também diminuem o gradiente na mesma quantidade ou mais, mas através de mecanismos menos óbvios.

• Usar a pesquisa de linha com as condições de Wolfe ou usar ou confiar em regiões impede a convergência para pontos de sela. Uma implementação de descida de gradiente adequada também deve estar fazendo isso. O artigo mencionado na resposta de Cam.Davidson.Pilon aponta problemas com o "método de Newton" na presença de pontos de sela, mas a correção que eles defendem é também um método de Newton.

• Usar o método de Newton não requer a construção de todo (denso) Hessiano; você pode aplicar o inverso do Hessian a um vetor com métodos iterativos que usam apenas produtos vetoriais de matriz (por exemplo, métodos de Krylov, como gradiente conjugado). Veja, por exemplo, o método de região confiável CG-Steihaug.

• É possível calcular com eficiência os produtos vetoriais de matriz Hessian, resolvendo duas equações adjuntas de ordem superior da mesma forma que a equação adjunta que já é usada para calcular o gradiente (por exemplo, o trabalho de duas etapas de retropropagação no treinamento de redes neurais).

• O mau condicionamento diminui a convergência dos solucionadores lineares iterativos, mas também diminui a descida do gradiente de forma igual ou pior. Usar o método de Newton em vez de gradiente descendente muda a dificuldade do estágio de otimização não-linear (onde não é possível fazer muito para melhorar a situação) para o estágio de álgebra linear (onde podemos atacá-lo com todo o arsenal de técnicas de pré-condicionamento de álgebra linear numérica).

• Além disso, o cálculo muda de "muitas etapas baratas" para "algumas etapas caras", abrindo mais oportunidades de paralelismo no nível da subpasta (álgebra linear).

Para obter informações básicas sobre esses conceitos, recomendo o livro "Otimização Numérica" de Nocedal e Wright.

* Obviamente, o método de Newton não o ajudará com L1 ou outras funções de penalidade / esparsidade comprimida similar que promovem a penalidade, pois elas não possuem a suavidade necessária.

Recentemente, eu mesmo aprendi isso - o problema é a proliferação de pontos de sela no espaço de alta dimensão, para a qual os métodos de Newton desejam convergir. Consulte este artigo: Identificando e atacando o problema do ponto de sela na otimização não-convexa de alta dimensão .

De fato, a razão entre o número de pontos de sela e os mínimos locais aumenta exponencialmente com a dimensionalidade N.

Enquanto a dinâmica da descida do gradiente é repelida de um ponto de sela para um erro menor, seguindo as direções da curvatura negativa, ... o método Newton não trata os pontos de sela de maneira apropriada; como discutido abaixo, os pontos de sela tornam-se atraentes sob a dinâmica de Newton.

Uma combinação de dois motivos:

• O método de Newton atrai para pontos de sela;
• pontos de sela são comuns no aprendizado de máquina ou, de fato, em qualquer otimização multivariável.

$$f=x^2-y^2$$

$$\mathbf{x}_{n+1} = \mathbf{x}_n - [\mathbf{H}f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n)$$

$$\mathbf{H}= \begin{bmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex] \dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex] \vdots & \vdots & \ddots & \vdots \\[2.2ex] \dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{bmatrix}.$$

$$\mathbf{H}= \begin{bmatrix} 2 & 0 \\[2.2ex] 0 & -2 \end{bmatrix}$$

$$[\mathbf{H} f]^{-1}= \begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix}$$

$$\nabla f=\begin{bmatrix} 2x \\[2.2ex] -2y \end{bmatrix}$$

Obtenha a equação final:

$$\mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_{n+1} = \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n -\begin{bmatrix} 1/2 & 0 \\[2.2ex] 0 & -1/2 \end{bmatrix} \begin{bmatrix} 2x_n \\[2.2ex] -2y_n \end{bmatrix}= \mathbf{\begin{bmatrix} x \\[2.2ex] y \end{bmatrix}}_n - \begin{bmatrix} x \\[2.2ex] y \end{bmatrix}_n = \begin{bmatrix} 0 \\[2.2ex] 0 \end{bmatrix}$$

$x=0,y=0$

Por outro lado, o método de descida gradiente não levará ao ponto de sela. O gradiente é zero no ponto de sela, mas um pequeno passo afastaria a otimização, como você pode ver no gradiente acima - seu gradiente na variável y é negativo.

Você fez duas perguntas: por que mais pessoas não usam o método de Newton e por que tantas pessoas usam a descida estocástica do gradiente? Essas perguntas têm respostas diferentes, porque existem muitos algoritmos que diminuem a carga computacional do método de Newton, mas geralmente funcionam melhor que o SGD.

$H$$O(N^2)$$N$$g$$O(N)$$H^{-1} g$$O(N^3)$para calcular. Assim, enquanto a computação do Hessian é cara, invertê-lo ou resolver mínimos quadrados é muitas vezes ainda pior. (Se você tem recursos esparsos, os assintóticos parecem melhores, mas outros métodos também têm melhor desempenho, portanto a escarsidade não torna Newton relativamente mais atraente.)

Segundo, muitos métodos, não apenas a descida em gradiente, são usados ​​com mais frequência do que Newton; geralmente são imitações do método de Newton, no sentido de que se aproximam de um passo de Newton a um custo computacional mais baixo por passo, mas são necessárias mais iterações para convergir. Alguns exemplos:

• $H^{-1}$

• $O(N^2)$

• Quando você não deseja lidar com a aproximação de derivadas secundárias, a descida em gradiente é atraente, porque ela usa apenas apenas informações de primeira ordem. A descida do gradiente aproxima-se implicitamente do Hessiano inverso à medida que a taxa de aprendizado vezes a matriz de identidade. Pessoalmente, raramente uso descida de gradiente: o L-BFGS é igualmente fácil de implementar, pois requer apenas a especificação da função objetivo e do gradiente; tem uma aproximação Hessiana inversa melhor do que a descida do gradiente; e porque a descida do gradiente exige o ajuste da taxa de aprendizado.

• Às vezes, você tem um número muito grande de observações (pontos de dados), mas pode aprender quase tão bem com um número menor de observações. Quando esse for o caso, você pode usar "métodos em lote", como descida de gradiente estocástico, que alternam usando subconjuntos das observações.

A direção da descida do gradiente é mais barata de calcular e a realização de uma pesquisa de linha nessa direção é uma fonte de progresso mais confiável e estável em direção a um ótimo. Em resumo, a descida do gradiente é relativamente confiável.

O método de Newton é relativamente caro, pois você precisa calcular o Hessian na primeira iteração. Então, em cada iteração subsequente, você pode recalcular completamente o Hessian (como no método de Newton) ou simplesmente "atualizar" o Hessian da iteração anterior (nos métodos quase-Newton) que é mais barato, mas menos robusto.

No caso extremo de uma função muito bem-comportada, especialmente uma função perfeitamente quadrática, o método de Newton é o vencedor. Se for perfeitamente quadrático, o método de Newton convergirá em uma única iteração.

No caso extremo oposto de uma função muito mal comportada, a descida do gradiente tenderá a vencer. Ele seleciona uma direção de pesquisa, pesquisa nessa direção e, finalmente, dá um passo pequeno, mas produtivo. Por outro lado, o método de Newton tenderá a falhar nesses casos, especialmente se você tentar usar as aproximações quase-Newton.

Entre a descida do gradiente e o método de Newton, existem métodos como o algoritmo Levenberg-Marquardt (LMA), embora eu tenha visto os nomes um pouco confusos. A essência é usar uma pesquisa mais informada por gradiente de descida quando as coisas são caóticas e confusas, depois alternar para uma pesquisa mais informada pelo método Newton quando as coisas estão ficando mais lineares e confiáveis.

$Hd = g$ para uma direção pode ser caro. Também é mais difícil fazer um paralelo.

O método de Newton funciona bem quando perto de uma solução, ou se o Hessian está variando lentamente, mas precisa de alguns truques para lidar com a falta de convergência e a falta de definição.

Muitas vezes, busca-se uma melhoria, em vez de uma solução exata, caso em que o custo extra de Newton ou métodos semelhantes a Newton não se justifica.

Existem várias maneiras de melhorar o acima, como métricas variáveis ​​ou métodos de região de confiança.

Como uma observação lateral, em muitos problemas, uma questão importante é a escala e o Hessian fornece excelentes informações de escala, embora a um custo. Se alguém pode se aproximar do Hessian, muitas vezes pode melhorar consideravelmente o desempenho. Até certo ponto, o método de Newton fornece a 'melhor' escala na medida em que é invariante afim.

Existem muitas dificuldades em relação ao uso do método de Newton para SGD, especialmente:

• ele precisa da matriz Hessiana - como estimar, por exemplo, a partir de gradientes barulhentos com precisão suficiente a um custo razoável?

• Hessian completo é muito caro - precisamos de algumas restrições, por exemplo, para um subespaço (qual subespaço?),

• $H^{-1}$$\lambda=0$

• O método de Newton atrai diretamente para o ponto mais próximo com gradiente zero ... o que geralmente é uma sela aqui. Como repelir eles? Por exemplo , Newton livre de sela inverte as direções negativas da curvatura, mas requer controle de sinais de autovalores,

• seria bom fazê-lo on-line - em vez de fazer muitos cálculos em um único ponto, tente dividi-lo em vários pequenos passos para explorar mais informações locais.

Podemos ir da 1ª à 2ª ordem em pequenas etapas, por exemplo, adicionando atualização de apenas 3 médias ao método de momentum, podemos simultaneamente o MSE ajustar a parábola em sua direção para uma escolha mais inteligente do tamanho da etapa ... Modelagem de 2ª ordem em um subespaço de baixa dimensão ainda é possível usar as coordenadas restantes para a descida simultânea do gradiente.