Gradiente Descendente & Regularização

A solução em forma fechada dos mínimos quadrados ordinários (OLS) é elegante, mas não escala para grandes quantidades de atributos, não existe para a maioria dos outros modelos e nada diz sobre controlar o sobreajuste. Esta aula acrescenta as duas ferramentas que fazem isso: o gradiente descendente — o motor de otimização por trás de quase todo o ML moderno — e a regularização — o freio padrão para a complexidade do modelo.

Gradiente descendente

A ideia é a que fecha a aula anterior. Para achar o mínimo de uma perda \(J(w)\), em vez de resolver \(\nabla J = 0\) no papel, desça a ladeira: meça a inclinação onde você está, dê um passo contra ela, repita.

O \(\eta\) é a taxa de aprendizado, o tamanho do passo. O gradiente \(\nabla_w J\) aponta para onde a perda mais cresce, então é o sinal de menos que faz o método descer em vez de subir.

Falta uma coisa só para isso virar código: saber o que é \(\nabla_w J\). Ele é uma lista de derivadas parciais, uma para cada parâmetro, que vale a pena montar com as mãos antes de aceitar a forma matricial pronta.

De onde vem o gradiente

Comece pelo caso menor, a reta de dois parâmetros. Escreva a perda como média, para a escala não depender de \(n\):

Cada parcela é o quadrado de um resíduo, \(e_i^2\). Pela regra da cadeia, a derivada de \(e_i^2\) em relação a qualquer parâmetro é \(2e_i\) vezes a derivada de \(e_i\) em relação a esse parâmetro. Ou seja: tudo se reduz a saber como o resíduo reage a cada peso. E isso é simples, porque \(e_i\) depende dos pesos de forma linear:

O \(-1\) aparece porque subir o intercepto em uma unidade baixa todo resíduo em uma unidade. O \(-x_i\) aparece porque subir a inclinação em uma unidade baixa o resíduo em \(x_i\) — quanto mais longe o ponto está da origem, mais ele sente uma mudança de inclinação.

Substituindo:

E assim por diante: o parâmetro \(j\)

Com \(d\) atributos o modelo é \(\hat{y}_i = w_0 + w_1x_{i1} + \dots + w_dx_{id}\). Adote a convenção \(x_{i0} = 1\) — a coluna de 1s que já está na matriz de projeto — e o intercepto deixa de ser caso especial: ele passa a ser só o peso de uma coluna constante. Com isso a derivada do resíduo tem sempre a mesma cara,

e uma fórmula só cobre todos os parâmetros:

Repare que a primeira linha não é uma exceção à última: ela é a última com \(x_{i0}=1\). É o mesmo truque da coluna de 1s que transformou \(\hat{y} = w_0 + w_1x\) em \(\hat{y} = Xw\).

Empilhando tudo: a forma matricial

Agora junte essas \(d+1\) derivadas num vetor. A entrada \(j\) é \(\sum_i e_i x_{ij}\), que é o produto da coluna \(j\) de \(X\) pelo vetor de resíduos. Fazer isso para todas as colunas de uma vez é multiplicar por \(X^\top\):

Não há mágica nessa fórmula: ela é a tabela acima, escrita de forma compacta. É por isso que uma linha de numpy calcula o gradiente de um modelo com um milhão de parâmetros — a estrutura é exatamente a de \(w_0\) e \(w_1\), repetida.

Duas leituras saem daí e as duas vão longe.

Primeira: iguale o gradiente a zero e você recupera as equações normais, \(X^\top(y - Xw) = 0\) — que é a solução em forma fechada da aula passada. A forma fechada e o gradiente são a mesma afirmação por dois caminhos: um resolve \(\nabla J = 0\) de uma vez, o outro caminha até lá.

Segunda: veja do que o gradiente é feito — uma soma ponderada pelos resíduos. O ponto que o modelo já acerta entra com \(e_i \approx 0\) e quase não vota; o ponto em que ele erra feio domina o passo. Então a regra \(w \leftarrow w - \eta\,\nabla J\) lê-se, em português claro: mova cada peso na direção para onde os erros apontam, numa quantidade proporcional ao tamanho desses erros. Essa frase continua verdadeira, sem trocar uma vírgula, quando o modelo for uma rede de 100 camadas e \(\nabla J\) vier da retropropagação.

Um passo, à mão

Três pontos — \((1,2), (2,4), (3,7)\) — partindo de \(w_0 = w_1 = 0\), com \(\eta = 0{,}1\).

Com os dois pesos zerados a reta prevê 0 em toda parte, então o resíduo é o próprio \(y\):

Jogue nas duas fórmulas que acabamos de deduzir:

As duas deram negativas, o que faz sentido: os dois pesos estão baixos demais e aumentar qualquer um reduz a perda. O passo, então, sobe com ambos:

Só nesse passo a perda cai de \(J = 23\) para \(J = 0{,}625\). Repetindo o procedimento:

Leia a tabela devagar, porque ela mostra três coisas de uma vez.

O primeiro passo é enorme: a perda cai de 23 para 0,63, quase todo o trabalho. Depois o progresso se arrasta — 0,344, depois 0,327. Esse formato é a regra, não a exceção — é por isso que ver \(J\) cair rápido no início não diz quase nada sobre ter convergido.

Os gradientes trocam de sinal entre as iterações 1 e 2. Isso é o passo tendo ultrapassado o mínimo e sendo desandado — o mesmo vaivém que o simulador da taxa de aprendizado mostra adiante, aqui em escala pequena.

E os dois parâmetros não andam no mesmo ritmo: na iteração 0 a derivada em \(w_1\) é 2,4 vezes a de \(w_0\), porque cada resíduo entra na conta de \(w_1\) multiplicado por \(x_i\), que vale até 3. Guarde essa assimetria — ela é o assunto da paisagem logo abaixo.

Deixando rodar até 2000 iterações chega-se a \(w_0 = -0{,}667\) e \(w_1 = 2{,}5\), exatamente o que as equações normais dão — a mesma resposta, por um caminho mais lento.

A paisagem que você está descendo

Até aqui foram números numa tabela. Vale ver o que eles são geometricamente, porque a figura explica de uma vez tanto a lentidão quanto a cura.

Pense em \(J(w_0, w_1)\) como uma paisagem: cada ponto do plano é um par de pesos, ou seja, uma reta candidata, cuja altura naquele ponto é o erro que essa reta comete. Minimizar é procurar o fundo do vale. O gradiente é a direção de maior subida naquele ponto, então \(-\nabla J\) é a direção da descida mais íngreme.

No painel da esquerda estão as curvas de nível dessa paisagem, com o ótimo em forma fechada marcado. À direita, os mesmos pesos desenhados como uma reta sobre os dados. Clique à esquerda para soltar um palpite inicial e vá clicando em Passo:

Agora ligue centrar x e recomece de um ponto parecido. Mesmos dados, mesmo algoritmo, comportamento completamente diferente.

Sem centrar, as curvas de nível formam um vale longo e estreito. A razão é a mesma assimetria que você viu na tabela: \(w_0\) e \(w_1\) ficam acoplados, porque mexer na inclinação de uma reta cujos \(x\) estão todos longe de zero também levanta ou abaixa a altura dela. O gradiente aponta atravessado ao vale em vez de ao longo dele, então o caminho ziguezagueia e demora. Centrado, o vale vira uma tigela redonda e os mesmos passos vão quase direto à resposta.

A taxa de aprendizado

• \(\eta\) pequeno demais → passos minúsculos, convergência dolorosamente lenta;
• \(\eta\) grande demais → os passos ultrapassam o mínimo; a perda oscila ou diverge;
• receita prática: experimente \(\eta \in \{10^{-3}, 10^{-2}, 10^{-1}\}\), monitore a curva de perda de treino — ela deve cair suavemente.

Sinta você mesmo. Na perda abaixo o limiar fica exatamente em \(\eta = 1\), que põe a história inteira num lugar só: em \(\eta = 0{,}5\) o passo acerta o mínimo de uma vez; abaixo disso ele se aproxima aos poucos; entre 0,5 e 1 ele passa do ponto mas ainda fecha, pulando de um lado para o outro; em \(\eta = 1\) exatamente ele fica batendo entre os mesmos dois pontos para sempre, sem nunca chegar mais perto; acima de 1 ele explode. Defina \(\eta = 1{,}05\) e avance passo a passo:

Batch, estocástico e mini-batch

from sklearn.linear_model import SGDRegressor
model = SGDRegressor(loss='squared_error', penalty='l2', alpha=1e-4,
                     learning_rate='invscaling', max_iter=1000)

O mesmo laço — com perdas diferentes — treina a regressão logística, as SVMs e as redes neurais. Aprenda-o uma vez, reutilize em todo lugar.

De retas a curvas: atributos polinomiais

A regressão linear é linear nos parâmetros, não necessariamente nas entradas. Expandir os atributos para potências, \(x \mapsto (x, x^2, \dots, x^p)\), ajusta polinômios com a mesma maquinaria do OLS:

from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import PolynomialFeatures

model = make_pipeline(PolynomialFeatures(degree=3), LinearRegression())

Mas a flexibilidade corta dos dois lados:

O grau 1 subajusta — rígido demais para seguir o seno. O grau 15 sobreajusta — 16 parâmetros perseguem 25 pontos ruidosos, produzindo oscilações selvagens. O painel da direita mantém todos os 16 parâmetros mas adiciona uma penalidade Ridge: a curva relaxa de volta ao sinal. Isso é a regularização em ação.

Subajuste e sobreajuste, medidos

A figura convence o olho. Vale medir, porque o número mostra uma coisa que o desenho esconde.

Os dados são 100 pontos de \(y = 0{,}5x^2 + x + 2\) com ruído de desvio 3, para \(x\) entre \(-3\) e \(3\). Três modelos: grau 1, grau 2 — o grau certo — e grau 30. Para cada um, o erro no próprio treino ao lado do erro em validação cruzada de cinco dobras:

O grau 30 tem o menor erro de treino dos três. Quem escolhesse o modelo por essa coluna escolheria justamente o pior.

A coluna mais instrutiva, porém, é a última. Veja as cinco dobras do grau 30 uma a uma:

Em três das cinco ele vai tão bem quanto o grau 2. Em uma delas, explode. Sobreajuste não é errar sempre — é errar de forma imprevisível — é por isso que a variação entre dobras denuncia o problema antes da média denunciar.

Daí sai um diagnóstico de bolso:

Existe também um piso. O ruído tem desvio 3 e essa parcela do \(y\) não depende de \(x\), então nenhum modelo consegue removê-la. O grau 2 chega perto desse piso, que é tudo o que se pode pedir de um modelo.

"Complexo demais" é relativo à quantidade de dados

Complexidade não é propriedade só do modelo: ela é a relação entre o número de parâmetros e o número de pontos.

Um polinômio de grau 10 tem 11 parâmetros livres — dez potências mais o intercepto. Enquanto os pontos de treino não passarem disso, a curva consegue atravessar exatamente todos eles:

Erro de treino zero não é sinal de sucesso: é sinal de que não sobrou informação. Com dez pontos e onze parâmetros, o modelo não precisou aprender coisa alguma sobre a forma da curva — bastou memorizar. A partir do décimo primeiro ponto ele passa a ter de escolher e o erro de treino sai do chão.

Repare no que isso implica: o mesmo modelo de grau 10 é complexo demais para 10 pontos e perfeitamente razoável para 100. Não há um grau "certo" em abstrato, só um grau certo para um volume de dados. A ferramenta que torna essa dependência visível é a curva de aprendizado — erro de treino e de validação em função do tamanho do conjunto —, tratada em seleção de modelos.

Regularização

Em vez de restringir o número de parâmetros, penalize sua magnitude — adicione um termo de complexidade à perda:

Ridge (L2) — Tikhonov, 1943; Hoerl & Kennard, 1970

• encolhe todos os coeficientes suavemente em direção a zero (nunca exatamente zero);
• distribui o peso entre atributos correlacionados — a cura padrão para a multicolinearidade;
• a forma fechada ainda existe: \(\hat{w} = (X^\top X + \alpha I)^{-1} X^\top y\) — o \(\alpha I\) torna a matriz inversível mesmo com atributos colineares.

Lasso (L1) — Tibshirani, 1996

• a penalidade de valor absoluto tem quinas em zero: as soluções pousam exatamente em zero para atributos fracos;
• realiza seleção automática de atributos — os coeficientes não nulos que sobrevivem nomeiam os atributos que importam;
• entre um grupo de atributos altamente correlacionados, tende a manter um arbitrariamente e zerar o resto.

O Elastic Net mistura ambas as penalidades (l1_ratio) — um padrão robusto quando os atributos são muitos e correlacionados.

from sklearn.linear_model import Ridge, Lasso, ElasticNet

Ridge(alpha=1.0)
Lasso(alpha=0.1)
ElasticNet(alpha=0.1, l1_ratio=0.5)

Por que o L1 zera e o L2 não

As duas listas acima afirmam a diferença. A razão é geométrica; vale ver em vez de acreditar.

Escreva a penalidade como um orçamento: minimize o erro quadrático sujeito a \(\sum |w_j| \le t\) (lasso) ou \(\sum w_j^2 \le t^2\) (ridge). As duas formulações são equivalentes — todo \(\alpha\) tem um \(t\) correspondente. Agora a figura tem dois objetos: as curvas de nível elípticas do erro, centradas na solução OLS, mais a região viável.

A solução restrita é onde a elipse, crescendo a partir do ótimo OLS, toca primeiro a região:

O círculo não tem cantos, então o ponto de contato pode ficar em qualquer lugar dele — e cai sobre um eixo apenas por coincidência. O losango tem quatro cantos, que ficam exatamente sobre os eixos. Uma curva suave que se expande em direção a uma região pontuda tende a encontrar uma ponta primeiro — e encontrar um canto é um coeficiente ser exatamente zero.

Arraste o ótimo OLS e veja com que frequência o losango é tocado num canto enquanto o círculo quase nunca é. O lasso não seleciona atributos por limiar — seleciona por causa do formato da restrição dele.

O caso unidimensional, em forma fechada

Com um único atributo padronizado as duas penalidades têm solução explícita — e ambas dizem a mesma coisa em álgebra:

Com \(\alpha = 1\):

O ridge divide; divisão nunca chega a zero. O lasso subtrai uma quantidade fixa e corta em zero — então todo coeficiente abaixo do limiar \(\alpha/2\) não encolhe, desaparece. Essa subtração é o canto do losango, escrito como fórmula.

Acompanhando o caminho

Rode a penalidade ao longo de uma faixa de \(\alpha\) e plote todos os coeficientes. São oito atributos: três carregam sinal real, três são puro ruído, dois são quase cópias um do outro.

O lasso remove primeiro os atributos de ruído — exatamente a seleção que se esperava — e a contagem segue caindo. O ridge nunca cai abaixo de oito em nenhum \(\alpha\): os coeficientes de ruído ficam pequenos e permanecem.

Passe então ao par correlacionado \(c_1, c_2\), cujos coeficientes verdadeiros são ambos 2. Em \(\alpha = 2\) o lasso reporta (1,89; 0,98) — está começando a escolher um e descartar o outro; qual deles é quase arbitrário. O ridge reporta (1,02; 0,97): divide o peso por igual. É essa a razão inteira de o ridge ser a resposta padrão à multicolinearidade e o lasso não.

O botão α

O \(\alpha\) troca fidelidade aos dados por tamanho dos coeficientes:

• \(\alpha \to 0\): OLS puro (sem freio);
• \(\alpha \to \infty\): todos os coeficientes esmagados para ~0, o modelo prevê a média (freio total);
• o \(\alpha\) certo não é conhecido de antemão — é escolhido por validação cruzada (RidgeCV, LassoCV ou uma busca em grade).

Material de aula

Referências

• Tikhonov, A. N. "On the stability of inverse problems." C. R. (Doklady) Acad. Sci. URSS, n. Ser. 39 (1943), 176–179. registro zbMATH
• Robbins, H.; Monro, S. "A Stochastic Approximation Method." Annals of Math. Statistics 22 (1951). DOI
• Hoerl, A. E.; Kennard, R. W. "Ridge Regression: Biased Estimation for Nonorthogonal Problems." Technometrics 12 (1970). DOI
• Tibshirani, R. "Regression Shrinkage and Selection via the Lasso." JRSS B 58 (1996). DOI

Bibliografia completa do curso na página de referências.

Quiz