Método de Gauss–Newton

Visão geral

O método de Gauss–Newton é uma técnica clássica de otimização de segunda ordem para resolver problemas de mínimos quadrados não lineares da forma

[ \min_{\theta \in \mathbb{R}^p}; F(\theta) ;=; \frac{1}{2},|r(\theta)|2^2 ;=; \frac{1}{2}\sum{i=1}^m r_i(\theta)^2, ]

onde (r(\theta)\in\mathbb{R}^m) é um vetor de resíduos (erros de predição). Ele funciona repetidamente:

Linearizando os resíduos em torno dos parâmetros atuais usando uma aproximação de Taylor de primeira ordem.
Resolvendo um subproblema de mínimos quadrados lineares para a atualização dos parâmetros.
Atualizando os parâmetros e repetindo até a convergência.

Gauss–Newton é um método fundamental em computação científica e aparece frequentemente em áreas adjacentes à IA, como visão computacional (por exemplo, ajuste de feixe (bundle adjustment)), inferência probabilística (por exemplo, aproximações de Laplace (Laplace approximations)), robótica (otimização de grafo de poses) e identificação de sistemas.

Comparado à Descida do Gradiente, ele explora informações de curvatura de forma eficiente para objetivos de mínimos quadrados — muitas vezes convergindo em bem menos iterações quando o modelo é bem-comportado.

Por que mínimos quadrados é especial

Para um objetivo geral (f(\theta)), o método de Newton usa a Hessiana (\nabla^2 f(\theta)). Para mínimos quadrados,

[ F(\theta) = \frac{1}{2} r(\theta)^\top r(\theta), ]

a estrutura fornece:

Jacobiana (Jacobian) (J(\theta) = \frac{\partial r(\theta)}{\partial \theta} \in \mathbb{R}^{m \times p})
Gradiente [ \nabla F(\theta) = J(\theta)^\top r(\theta) ]
Hessiana [ \nabla^2 F(\theta) = J^\top J ;+; \sum_{i=1}^m r_i(\theta),\nabla^2 r_i(\theta) ]

A observação-chave: quando os resíduos são pequenos perto da solução (um caso comum em modelos de mínimos quadrados bem especificados), o segundo termo muitas vezes é pequeno; assim,

[ \nabla^2 F(\theta)\approx J^\top J. ]

Essa aproximação é exatamente o que Gauss–Newton utiliza.

Derivação: linearize os resíduos, resolva um passo de mínimos quadrados lineares

Em uma iteração (\theta_k), aproxime os resíduos pela expansão de Taylor de primeira ordem:

[ r(\theta_k + \delta) \approx r(\theta_k) + J(\theta_k),\delta. ]

Em seguida, aproxime o objetivo:

[ F(\theta_k + \delta) \approx \frac{1}{2}|r_k + J_k \delta|_2^2, ] onde (r_k = r(\theta_k)), (J_k = J(\theta_k)).

Gauss–Newton escolhe (\delta) para minimizar esse problema de mínimos quadrados lineares:

[ \delta_k = \arg\min_\delta |J_k \delta + r_k|_2^2. ]

As equações normais para isso são:

[ (J_k^\top J_k),\delta_k = -J_k^\top r_k. ]

Então atualize:

[ \theta_{k+1} = \theta_k + \delta_k. ]

Interpretando o passo

É o passo de Newton para a aproximação quadrática que usa a Hessiana aproximada (J^\top J).
É o melhor passo (no sentido de mínimos quadrados) que torna pequenos os resíduos linearizados.

Algoritmo (forma prática)

Um laço típico de Gauss–Newton:

Calcule o vetor de resíduos (r_k) e a Jacobiana (J_k).
Resolva (\min_\delta |J_k \delta + r_k|_2^2) usando um método estável (QR/SVD).
Opcionalmente aplique uma busca de linha ou um mecanismo de salvaguarda por região de confiança.
Atualize (\theta).

Pseudocode:

given initial θ
repeat:
    r ← r(θ)
    J ← jacobian of r at θ
    δ ← argminδ ||J δ + r||^2     (solve via QR/SVD; avoid forming JᵀJ if possible)
    θ ← θ + δ                     (or θ ← θ + α δ with line search)
until convergence

Resolvendo o subproblema: equações normais vs QR (e por que isso importa)

Você frequentemente verá o passo computado via equações normais:

[ (J^\top J)\delta = -J^\top r. ]

Isso é computacionalmente conveniente, mas pode ser numericamente frágil:

O número de condição piora: (\kappa(J^\top J) = \kappa(J)^2)
Se (J) é mal condicionado, as equações normais podem perder precisão significativa

Alternativas mais estáveis:

Fatoração QR (QR factorization): (J = Q R) (com (Q) ortonormal, (R) triangular superior) [ \delta = -R^{-1} Q^\top r ]
Decomposição em valores singulares (SVD, singular value decomposition): (J = U \Sigma V^\top), robusta para casos com posto deficiente e útil para detectar degenerescência
Cholesky em (J^\top J) pode ser aceitável se (J) for bem condicionado, mas QR geralmente é mais seguro.

Em problemas esparsos de grande escala (por exemplo, ajuste de feixe), solucionadores frequentemente usam formas semelhantes a equações normais porque a esparsidade pode ser explorada intensamente, mas combinam isso com amortecimento, reordenação e cuidados numéricos.

Quando Gauss–Newton funciona bem

Gauss–Newton tende a se destacar quando:

O problema é realmente (ou aproximadamente) uma soma de erros ao quadrado.
A função de resíduos é suave e não muito não linear na região explorada.
Você tem uma boa inicialização (método local).
A Jacobiana (J(\theta^*)) na solução tem posto completo nas colunas (parâmetros identificáveis).
Os resíduos no ótimo são pequenos (ou próximos de zero), tornando a aproximação da Hessiana precisa.

Na prática, muitos problemas de estimação “geométrica” (pose de câmera, structure-from-motion, registro) satisfazem essas condições após uma inicialização razoável, motivo pelo qual Gauss–Newton e suas variantes amortecidas são onipresentes nesses contextos.

Intuição de convergência e garantias (alto nível)

Gauss–Newton é um método local: o comportamento perto da solução importa.

Se a solução verdadeira tem resíduo zero (isto é, (r(\theta^*) = 0)) e (J(\theta^*)) tem posto completo, Gauss–Newton frequentemente alcança convergência quadrática (semelhante a Newton), porque o termo descartado na Hessiana se anula no ótimo.
Se os resíduos não são pequenos no ótimo, a convergência tipicamente é linear (ainda assim, muitas vezes rápida).
Se (J^\top J) é singular ou quase singular, os passos podem se tornar instáveis ou enormes, e a convergência pode falhar sem amortecimento/regiões de confiança.

Essa é uma das razões pelas quais muitos sistemas reais usam Levenberg–Marquardt (próxima seção), que estabiliza Gauss–Newton.

Relação com o método de Newton

O método de Newton para minimizar (F(\theta)) usa:

[ \nabla^2 F(\theta_k),\delta_k = -\nabla F(\theta_k). ]

Para mínimos quadrados, substituindo as expressões exatas obtemos:

[ \Big(J^\top J + \sum_i r_i \nabla^2 r_i\Big)\delta = -J^\top r. ]

Gauss–Newton descarta o termo de curvatura de segunda ordem dos resíduos:

[ (J^\top J)\delta = -J^\top r. ]

Assim, você pode pensar em Gauss–Newton como:

Um método de Newton aproximado especializado para mínimos quadrados
Um método que evita computar (\nabla^2 r_i) (segundas derivadas), que são caras e propensas a erros

Em termos de ML, isso está intimamente relacionado ao uso de uma aproximação semidefinida positiva (positive semidefinite, PSD) da Hessiana, que tende a produzir direções de descida mais estáveis do que informações de segunda ordem indefinidas.

Relação com Levenberg–Marquardt (LM)

O Levenberg–Marquardt (LM) é melhor entendido como um método Gauss–Newton amortecido:

[ (J^\top J + \lambda I),\delta = -J^\top r ]

(ou às vezes (J^\top J + \lambda \operatorname{diag}(J^\top J))).

Quando (\lambda \to 0): LM se aproxima de Gauss–Newton.
Quando (\lambda) é grande: (\delta \approx -\frac{1}{\lambda} J^\top r), o que se assemelha a um pequeno passo de Descida do Gradiente.

LM também é comumente interpretado como um método de região de confiança (trust-region) para o modelo de mínimos quadrados linearizado:

[ \min_\delta |J\delta + r|^2 \quad \text{s.t.}\quad |\delta|\le \Delta. ]

Essa interpretação importa na prática porque métodos de região de confiança tipicamente têm comportamento global mais robusto do que passos puros de Gauss–Newton.

Por que LM é comum em pipelines adjacentes à IA

Ajuste de feixe em SLAM/SfM: problemas grandes, esparsos e às vezes mal condicionados; LM fornece robustez e passos bem escalonados.
Aproximação de Laplace em modelos probabilísticos: frequentemente encontra-se um ponto MAP por otimização iterativa e, então, aproxima-se o posterior com uma Gaussiana usando curvatura. Uma aproximação do tipo Gauss–Newton (J^\top J) pode servir como substituto eficiente de curvatura quando a verossimilhança é (aproximadamente) de mínimos quadrados (por exemplo, ruído de observação Gaussiano) ou após linearização local.

Se você tiver um artigo dedicado, veja Algoritmo de Levenberg–Marquardt.

Exemplo prático: ajustando uma curva exponencial

Suponha que você observe dados ((x_i, y_i)) e modele

[ \hat{y}(x;\theta) = a,e^{b x} + c,\quad \theta=(a,b,c). ]

Defina resíduos (r_i(\theta)=\hat{y}(x_i;\theta)-y_i). Então Gauss–Newton atualiza iterativamente ((a,b,c)).

Abaixo está uma implementação mínima em NumPy usando uma resolução baseada em QR (estável):

import numpy as np

def model(x, theta):
    a, b, c = theta
    return a * np.exp(b * x) + c

def residuals(x, y, theta):
    return model(x, theta) - y

def jacobian(x, theta):
    a, b, c = theta
    e = np.exp(b * x)
    # r = a*e^{bx} + c - y
    # dr/da = e^{bx}
    # dr/db = a*x*e^{bx}
    # dr/dc = 1
    J = np.column_stack([e, a * x * e, np.ones_like(x)])
    return J

def gauss_newton(x, y, theta0, max_iter=20, tol=1e-8):
    theta = theta0.astype(float).copy()
    for k in range(max_iter):
        r = residuals(x, y, theta)
        J = jacobian(x, theta)

        # Solve min ||J δ + r|| via QR: J = Q R
        Q, R = np.linalg.qr(J, mode="reduced")
        delta = -np.linalg.solve(R, Q.T @ r)

        theta_new = theta + delta
        if np.linalg.norm(delta) <= tol * (1.0 + np.linalg.norm(theta)):
            theta = theta_new
            break
        theta = theta_new
    return theta

# Example usage
x = np.linspace(0, 1, 50)
true_theta = np.array([2.0, -3.0, 0.5])
y = model(x, true_theta) + 0.05 * np.random.randn(len(x))

theta_hat = gauss_newton(x, y, theta0=np.array([1.0, -1.0, 0.0]))
print(theta_hat)

Notas:

Uma inicialização razoável importa: modelos altamente não lineares podem ter muitas regiões locais ruins.
Se a atualização for agressiva demais, você tipicamente adicionaria amortecimento (LM) ou uma busca de linha (line search).

Mínimos quadrados ponderados e perdas robustas (comuns na prática)

Muitos problemas reais usam resíduos ponderados:

[ \min_\theta \frac{1}{2}|W^{1/2} r(\theta)|^2 ]

onde (W) é diagonal (confiança por observação) ou mais geral (ruído correlacionado). O passo de Gauss–Newton torna-se:

[ (J^\top W J)\delta = -J^\top W r. ]

Em visão/robótica, também é comum usar perdas robustas (robust losses) (Huber, Cauchy) para reduzir a influência de outliers. Uma abordagem comum é mínimos quadrados iterativamente reponderados (IRLS, iteratively reweighted least squares), em que a perda robusta induz pesos que mudam a cada iteração, e cada iteração resolve um passo ponderado de Gauss–Newton/LM.

Aplicações em sistemas adjacentes a IA e ML

Ajuste de feixe e SLAM (otimização de grafo de poses)

No ajuste de feixe, os parâmetros incluem poses de câmera e pontos 3D; os resíduos são erros de reprojeção. A Jacobiana é esparsa e estruturada. Solucionadores práticos:

Usam Gauss–Newton/LM com álgebra linear esparsa
Frequentemente resolvem equações normais com truques de complemento de Schur (Schur complement) para eliminar variáveis de pontos de forma eficiente
Dependem fortemente de amortecimento e de uma boa inicialização para evitar divergência

Essa é uma grande razão pela qual Gauss–Newton é “o otimizador padrão” em visão geométrica.

Aproximação de Laplace e aproximações de curvatura

Em inferência Bayesiana, a aproximação de Laplace aproxima um posterior ao redor de um modo (\theta^*) usando uma Gaussiana com covariância (\Sigma \approx H^{-1}), onde (H) é a Hessiana do log posterior negativo.

Se o seu log-verossimilhança negativo é (aproximadamente) uma soma de resíduos ao quadrado — por exemplo, ruído de observação Gaussiano — então a aproximação de Gauss–Newton (H \approx J^\top J) pode ser usada:

para otimizar em direção ao modo (Gauss–Newton/LM),
e para aproximar a curvatura perto do ótimo.

Isso conecta Gauss–Newton a ideias práticas aproximadas de segunda ordem usadas em ML (aproximações eficientes de curvatura que são PSD e exploram estrutura).

Treinamento e métodos de segunda ordem em ML

Embora o aprendizado profundo mainstream dependa fortemente de variantes de SGD (Otimização Estocástica), matrizes de curvatura do tipo Gauss–Newton aparecem em:

Matrizes “Gauss–Newton generalizadas” para certas perdas e arquiteturas de rede
Aproximações inspiradas em gradiente natural
Regimes de lote grande (large-batch) ou fine-tuning, onde informação de segunda ordem pode ajudar

Em redes neurais, calcular Jacobianas de forma eficiente frequentemente depende de diferenciação automática e retropropagação; veja Retropropagação.

Considerações numéricas e de estabilidade (o que quebra e o que fazer)

1) Deficiência de posto e mau condicionamento

Se (J) tiver posto deficiente, então (J^\top J) é singular e o passo de Gauss–Newton pode ser indefinido ou instável.

Mitigações:

Use SVD ou um QR revelador de posto para computar um passo de norma mínima
Adicione amortecimento: LM ((J^\top J + \lambda I))
Reparametrize para remover graus de liberdade não identificáveis

2) Aceitação do passo e globalização

Gauss–Newton puro pode passar do ponto quando está longe da solução, porque a linearização é imprecisa.

Salvaguardas comuns:

Busca de linha em (\alpha): (\theta \leftarrow \theta + \alpha\delta)
Região de confiança (LM é uma escolha padrão)
Monitorar a redução do objetivo; aumentar o amortecimento se o passo falhar

3) Escalonamento

Parâmetros e resíduos podem ter escalas muito diferentes, prejudicando o condicionamento.

Práticas comuns:

Escalonar parâmetros (trabalhar em unidades normalizadas)
Usar amortecimento diagonal baseado em (\operatorname{diag}(J^\top J))
Escalonar resíduos pelos desvios padrão do ruído de medição (estatisticamente fundamentado)

4) Não forme \(J^\top J\) a menos que seja necessário

Formar (J^\top J) explicitamente pode:

perder a estrutura de esparsidade (dependendo da representação)
elevar ao quadrado o número de condição
amplificar erros numéricos

Prefira resolver (\min|J\delta + r|) com QR/SVD quando viável, especialmente para problemas densos ou de tamanho moderado.

Intuição: por que a aproximação da Hessiana frequentemente é “boa o suficiente”

O termo descartado na Hessiana,

[ \sum_i r_i(\theta),\nabla^2 r_i(\theta), ]

é escalonado pelos valores dos resíduos (r_i(\theta)). Assim, à medida que o algoritmo se aproxima de uma solução com resíduos pequenos:

o termo naturalmente diminui,
(J^\top J) torna-se um modelo de curvatura muito preciso,
os passos tornam-se semelhantes aos de Newton, permitindo convergência local rápida.

Essa “aproximação que se autoaperfeiçoa” é uma grande razão pela qual Gauss–Newton é tão eficaz na prática quando o modelo ajusta bem os dados.

Resumo: quando escolher Gauss–Newton

Gauss–Newton é uma forte opção padrão quando:

Seu objetivo é naturalmente de mínimos quadrados (ou pode ser formulado como tal).
Você consegue computar Jacobianas de forma confiável (analíticas ou via autodiff).
Você tem uma inicialização decente e quer convergência mais rápida do que métodos de primeira ordem.
Você se importa com aproximações de curvatura PSD estáveis.

Se você precisar de mais robustez (comum), use Levenberg–Marquardt, que é essencialmente Gauss–Newton com comportamento de região de confiança/amortecimento.

Artigos de base relacionados: Descida do Gradiente, Otimização Convexa, Otimização Estocástica e Otimização com Restrições.