Pontos de sela em otimização: o que são e por que importam

Mesmo que todas as derivadas parciais da sua função sejam zero, isso não garante que você esteja perto de um mínimo.

Otimização é a busca pelo menor ou maior valor de uma função, e todo método que você usa procura um ponto onde o gradiente seja plano. Mas um gradiente plano não garante que você encontrou a melhor resposta. Às vezes, significa que a função sobe em uma direção e desce em outra, no mesmo ponto.

Esse ponto é chamado de ponto de sela: desce em um sentido, sobe em outro e é plano ao redor. Reconhecer pontos de sela é importante porque seu algoritmo pode ficar preso ali e confundir um gradiente plano com um mínimo de verdade.

Neste artigo, eu vou te mostrar como identificar um ponto de sela matematicamente e por que ele costuma confundir algoritmos de otimização.

O que é um ponto de sela?

Em um ponto de sela, o gradiente é zero, assim como em um mínimo ou máximo. Mas um ponto de sela não é nem um, nem outro.

A função curva para cima em algumas direções e para baixo em outras, exatamente no mesmo ponto. Se você segue um eixo, o valor sobe; em outro eixo, ele cai. É daí que vem o nome — inspirado no formato de uma sela de cavalo, que curva para cima na frente e atrás e para baixo nas laterais.

Aqui vai uma função simples de duas variáveis para ilustrar:

Função de duas variáveis

Na origem, (0, 0), as duas derivadas parciais são zero, então é um ponto crítico (também chamado de ponto estacionário). Ao longo do eixo x, f aumenta por causa do termo x^2. Ao longo do eixo y, f diminui por causa do termo -y^2.

Se você plota essa função em 3D, a superfície curva para cima em uma direção e para baixo em outra, formando exatamente o formato que dá nome ao ponto de sela.

Gráfico de superfície 3D de f(x, y) = x^2 - y^2

Um mapa de contorno da mesma função conta a mesma história vista de cima. As linhas de nível ao redor da origem parecem hipérboles, e não os loops fechados que você veria ao redor de um mínimo ou máximo.

Mapa de contorno de f(x, y) = x^2 - y^2

A definição exata muda um pouco dependendo da área. Em cálculo multivariável, um ponto de sela é um ponto crítico que não é mínimo nem máximo local. Em otimização e teoria dos jogos, o termo pode significar outra coisa, ligada a problemas minimax em vez de curvatura. Vou abordar essa distinção mais adiante.

Pontos de sela vs. mínimos e máximos

Antes de ver como identificar pontos de sela matematicamente, vale comparar com os outros dois tipos de pontos críticos.

Mínimo local

Em um mínimo local, a função aumenta em todas as direções próximas. Imagine uma tigela — quando você se afasta do fundo em qualquer direção, sobe. A função f(x, y) = x2 + y2 se comporta assim.

Máximo local

Em um máximo local, a função diminui em todas as direções próximas. É o espelho de um mínimo, um domo em vez de uma tigela. A função f(x, y) = -x2 - y2 diminui em todas as direções à medida que você se afasta da origem.

Ponto de sela

Em um ponto de sela, a função aumenta em algumas direções e diminui em outras. É isso que faz de f(x, y) = x2 - y2, o exemplo da seção anterior, um ponto de sela e não um mínimo ou máximo: sobe ao longo do eixo x e desce ao longo do eixo y, no mesmo ponto.

Veja a comparação lado a lado:

Gráficos 3D lado a lado de um mínimo local, máximo local e ponto de sela

Como encontrar um ponto de sela

Encontrar um ponto de sela envolve derivar, achar onde as derivadas somem e então analisar como a função curva ao redor desse ponto.

Vou usar a mesma função de antes:

Função de referência

O processo, passo a passo:

1. Calcule as primeiras derivadas parciais

Derive f em relação a x, tratando y como constante, e depois faça o mesmo em relação a y:

Calculando as primeiras derivadas parciais

2. Zere as derivadas

Encontre o ponto onde as duas derivadas parciais somem simultaneamente:

Zerando as derivadas

Isso dá x = 0 e y = 0, então (0, 0) é um ponto crítico. As primeiras derivadas não dizem qual tipo.

3. Calcule as segundas derivadas

Você precisa de três: a derivada de f_x em relação a x, a derivada de f_y em relação a y, e a derivada mista:

Segundas derivadas

4. Classifique o ponto crítico usando a curvatura 

f_xx = 2 é positivo, então f curva para cima ao longo do eixo x. f_yy = -2 é negativo, então f curva para baixo ao longo do eixo y. Uma direção curva para cima e a outra para baixo, no mesmo ponto — isso é o ponto de sela.

Esse processo em quatro etapas funciona para qualquer função duas vezes diferenciável.

Nas duas próximas seções, vou formalizar a etapa 4 com ferramentas que escalam além de duas variáveis: a matriz Hessiana e o teste da segunda derivada.

Como a matriz Hessiana identifica pontos de sela

A matriz Hessiana reúne todas as segundas derivadas da última seção em um único objeto e é a ferramenta que diz se um ponto crítico é mínimo, máximo ou sela.

Para uma função de duas variáveis, a Hessiana é assim:

Hessiana para uma função de duas variáveis

Cada elemento descreve curvatura: f_xx e f_yy descrevem a curvatura ao longo dos eixos x e y, e f_xy descreve como essas duas direções interagem. Se você substituir as segundas derivadas da seção anterior, a Hessiana da nossa função de exemplo fica assim:

Hessiana da função de referência

Uma matriz sozinha não diz muita coisa. O que importa são seus autovalores — os números que descrevem como a função curva ao longo de um conjunto específico de direções chamado autovetores.

• Autovalor positivo: a função curva para cima ao longo da direção do autovetor
• Autovalor negativo: a função curva para baixo nessa direção
• Mistura de autovalores positivos e negativos: a função curva para cima em algumas direções e para baixo em outras (ponto de sela)

Como a Hessiana do nosso exemplo é diagonal, os autovalores estão na diagonal: 2 e -2. Seus autovetores apontam ao longo dos eixos x e y, exatamente a curvatura que você encontrou manualmente na seção anterior. f curva para cima em x porque o autovalor ali é positivo, e para baixo em y porque o autovalor é negativo.

Na maioria das funções, a Hessiana não será diagonal, então os autovetores não se alinham bonitinho aos eixos x e y, e você precisará resolvê-los diretamente em vez de lê-los da matriz. Ainda assim, um autovalor positivo e um negativo indicam que você está em um ponto de sela.

O teste da segunda derivada para pontos de sela

Você não precisa calcular autovalores na mão sempre. Para funções de duas variáveis, há um atalho — o teste da segunda derivada — baseado no determinante da Hessiana.

Aqui está o determinante, usando as mesmas segundas derivadas de antes:

O determinante

D é o determinante da Hessiana, e seu sinal — combinado ao sinal de f_xx — classifica o ponto crítico:

• D > 0 e f_xx > 0: mínimo local

• D > 0 e f_xx < 0: máximo local

• D < 0: ponto de sela

• D = 0: inconclusivo

No nosso exemplo, f_xx = 2, f_yy = -2 e f_xy = 0:

Teste da segunda derivada para a função de referência

D é negativo, então o teste confirma que (0, 0) é um ponto de sela.

Esse teste é a regra dos autovalores da seção anterior, reescrita em uma forma que você pode calcular sem resolver autovetores. D é o produto dos dois autovalores, e f_xx + f_yy é a soma deles. Quando D é negativo, os autovalores têm sinais opostos, e isso define um ponto de sela. Quando D é zero, pelo menos um autovalor é zero, então a curvatura nessa direção é plana, e nem o teste nem os autovalores sozinhos conseguem dizer o que está acontecendo ali.

Pontos de sela em otimização

Tudo até aqui tratou de identificar um ponto de sela quando você já tem a função em mãos. Mas, em otimização, você está procurando o melhor ponto sem saber de antemão onde ele está, e métodos baseados em gradiente usam gradiente zero para decidir quando parar.

É justamente aí que pontos de sela atrapalham.

Um otimizador baseado em gradiente se move na direção que reduz a função objetivo mais rapidamente e continua até o gradiente ficar próximo de zero. Mas um gradiente quase zero não diz ao algoritmo se ele encontrou um mínimo ou um ponto de sela.

Direções com curvatura positiva empurram a função para cima, e o algoritmo já aprendeu que dar passos por ali piora. As direções de curvatura negativa continuam existindo e são a saída — mas um algoritmo que só confia no gradiente pode não percebê-las, porque bem no ponto de sela o gradiente nessas direções também fica próximo de zero.

É também onde a otimização desacelera.

A magnitude do gradiente tende a diminuir conforme você se aproxima de qualquer ponto estacionário, então um algoritmo que escala seus passos pelo tamanho do gradiente dá passos curtos perto de uma sela, esteja ou não perto do mínimo que realmente procura.

Encontrar um ponto estacionário não é o mesmo que concluir a otimização. Você ainda precisa diferenciar um gradiente quase zero de sela versus mínimo e, depois de saber disso, encontrar a direção que continua melhorando a função objetivo.

Pontos de sela em machine learning

A função de perda de uma rede neural depende de cada peso e viés da rede — às vezes milhões ou bilhões de dimensões. Está bem longe de um exemplo de duas variáveis.

Em uma análise de otimização não convexa em alta dimensão, Dauphin e colegas argumentam que, conforme o número de dimensões cresce, pontos críticos são muito mais propensos a serem pontos de sela do que mínimos ou máximos locais. Cada dimensão adiciona outra direção em que a curvatura pode ir para qualquer lado, e basta uma direção de curvatura negativa para transformar um ponto crítico em sela, e não em mínimo.

Isso importa no treinamento porque o gradiente descendente só enxerga o gradiente onde está pisando agora.

Perto de um ponto de sela, esse gradiente fica pequeno em todas as direções — o mesmo sinal que você veria ao se aproximar de um mínimo de verdade. O treinamento pode desacelerar ou empacar em uma região nada ideal, e não dá para saber só pela curva de perda se você está perto de um mínimo ou preso em uma sela.

É por isso que pontos de sela aparecem tanto ao lado de mínimos locais quando se fala em treinar redes neurais. Mas eles não são o único obstáculo. Gradientes que somem, curvatura mal condicionada e a escala do espaço de busca também tornam a otimização em alta dimensão desafiadora.

Como algoritmos de otimização lidam com pontos de sela

Nada disso significa que o treinamento baseado em gradiente está condenado perto de uma sela. Há técnicas que ajudam a atravessá-las, cada uma sob um ângulo diferente.

Stochastic gradient descent

Stochastic gradient descent calcula o gradiente a partir de um subconjunto aleatório dos dados de treino, e esse subconjunto muda a cada passo.

O ruído introduzido faz com que o gradiente estimado raramente seja exatamente zero, mesmo numa região onde o gradiente verdadeiro é quase zero. Esse ruído pode ser suficiente para empurrar o otimizador para fora de um ponto de sela e em direção de curvatura negativa, em vez de estagnar onde o gradiente some.

Momentum

Momentum mantém uma média móvel dos gradientes passados e usa isso, em vez de só o gradiente atual, para decidir o próximo passo.

Perto de uma sela, isso ajuda porque o otimizador chega já “andando” em alguma direção, carregado pelos gradientes de antes. Esse movimento acumulado pode levá-lo através da região plana ao redor da sela, em vez de desacelerar no instante em que o gradiente local fica perto de zero.

Métodos de segunda ordem

Métodos de segunda ordem usam a informação de curvatura diretamente.

Trabalhando com a Hessiana ou uma aproximação dela, esses métodos diferenciam direções de curvatura positiva e negativa em um ponto crítico. Essa distinção é a essência de um ponto de sela, então um método de segunda ordem consegue identificar a direção descendente e segui-la, em vez de tratar todo gradiente próximo de zero do mesmo jeito.

Pontos de sela vs. conceitos relacionados

Alguns termos se confundem com pontos de sela com tanta frequência que valem um esclarecimento.

Ponto de sela vs. mínimo local

Um mínimo local curva para cima em todas as direções ao seu redor — curvatura positiva consistente, em todo o entorno. Um ponto de sela só curva para cima em algumas direções e curva para baixo em outras. No momento em que você encontra uma direção com curvatura negativa, já não está mais diante de um mínimo.

Ponto de sela vs. máximo local

O raciocínio é o inverso para máximos locais. A curvatura permanece negativa em todas as direções próximas. Um ponto de sela adiciona pelo menos uma direção de curvatura positiva ao lado das negativas.

Ponto de sela vs. ponto de inflexão

Ponto de inflexão é um conceito unidimensional. É onde uma curva troca de côncava para cima para côncava para baixo, ou vice-versa, ao longo de uma única variável.

Um ponto de sela precisa de pelo menos duas variáveis, porque todo o conceito depende de comparar curvaturas em direções diferentes no mesmo ponto. Uma função de uma variável pode ter ponto de inflexão, mas não pode ter ponto de sela, já que não há uma segunda direção para curvar ao contrário.

Ponto de sela vs. ponto estacionário

Todo ponto de sela é um ponto estacionário, já que o gradiente é zero ali. Mas o inverso não é verdade. Ponto estacionário é qualquer ponto onde o gradiente é zero — pode ser mínimo local, máximo local ou ponto de sela. Você precisa da curvatura, via Hessiana ou teste da segunda derivada, para saber qual é.

Aqui vai uma visão mais visual de como eles se comparam:

Pontos de sela comparados a outros conceitos

Pontos de sela em otimização minimax

Até aqui, usamos "ponto de sela" para descrever a curvatura de um ponto crítico. Há um segundo significado, mais antigo, da teoria dos jogos, que aparece também em machine learning moderna.

Em otimização minimax, um jogador minimiza uma função enquanto outro a maximiza, e um ponto de sela é o par de valores em que nenhum dos dois consegue melhorar seu resultado mudando apenas a própria jogada.

A teoria dos jogos usa isso para descrever estratégias de equilíbrio em jogos competitivos. A otimização adversarial empresta a mesma estrutura para problemas em que um processo busca o pior caso que outro processo precisa defender.

Redes generativas adversariais (GANs) são o melhor exemplo em machine learning. Um gerador minimiza sua perda produzindo dados falsos convincentes, enquanto um discriminador maximiza sua capacidade de diferenciar dados reais de falsos. Treinar uma GAN significa buscar um ponto de sela nesse sentido minimax — um equilíbrio em que gerador e discriminador encontraram suas melhores respostas um ao outro.

Esse ponto de sela minimax se relaciona ao ponto de sela de ponto crítico tratado antes, mas não são intercambiáveis.

A versão de ponto crítico descreve a curvatura em um único ponto de uma função. A versão minimax descreve um equilíbrio entre dois objetivos em competição. Ambas usam a mesma palavra porque envolvem uma mistura de comportamentos “para cima” e “para baixo”, mas confundi-las não ajuda se você tentar aplicar um teste baseado em Hessiana a um jogo de dois jogadores.

Erros comuns ao lidar com pontos de sela

A maior parte da confusão sobre pontos de sela vem de alguns erros recorrentes. Aqui está o que você precisa saber.

Assumir que gradiente zero significa mínimo

Gradiente zero só diz que você encontrou um ponto crítico, não qual tipo. Verifique a curvatura antes de concluir, já que um ponto de sela também tem gradiente zero.

Classificar um ponto usando apenas primeiras derivadas

Primeiras derivadas encontram pontos críticos, mas não os classificam. Você precisa das segundas derivadas, pela Hessiana ou pelo teste da segunda derivada, para diferenciar mínimo, máximo e sela.

Ignorar direções diferentes de curvatura

Uma função pode curvar para cima ao longo do eixo x e ainda assim ser um ponto de sela no geral, se alguma outra direção curvar para baixo. Verifique todas as direções, ou use os autovalores da Hessiana, que cobrem todas de uma vez.

Confundir pontos de sela com pontos de inflexão

Ponto de inflexão descreve mudança de curvatura em uma única variável. Ponto de sela descreve curvatura mista em múltiplas variáveis no mesmo ponto. São ideias relacionadas, mas não se aplicam ao mesmo tipo de função, e a matemática por trás não é intercambiável.

Tratar todos os usos de "ponto de sela" como idênticos

O ponto de sela de ponto crítico e o ponto de sela minimax compartilham o nome, não a definição. Antes de aplicar um teste baseado em Hessiana ou um argumento de autovalores, verifique qual significado está em jogo — teoria dos jogos e otimização adversarial usam a versão minimax, que não se reduz a uma checagem de curvatura de uma única função.

Conclusão

Um ponto de sela curva para cima em algumas direções e para baixo em outras, nas mesmas coordenadas — por isso não é mínimo nem máximo, embora o gradiente vá a zero ali, assim como acontece nos dois.

Gradientes encontram o ponto crítico. Os autovalores da Hessiana, ou o teste da segunda derivada, dizem qual tipo é. Em alta dimensão, essa distinção importa muito porque pontos de sela são mais numerosos que mínimos locais, e algoritmos como SGD e momentum existem em parte para superá-los.

Por fim, lembre que o ponto de sela minimax da teoria dos jogos e de GANs compartilha o nome, mas não a matemática — então garanta que você sabe a qual deles está se referindo.

Se você curtiu a ideia por trás de pontos de sela, vai gostar da nossa Deep Learning Track in Python. Além da teoria, você vai usar PyTorch para criar redes neurais para diferentes tipos de problemas.