25

Dada uma função de custo convexa, usando o SGD para otimização, teremos um gradiente (vetor) em um determinado ponto durante o processo de otimização.

Minha pergunta é, dado o ponto no convexo, o gradiente apenas aponta na direção em que a função aumenta / diminui mais rapidamente, ou o gradiente sempre aponta no ponto ótimo / extremo da função de custo ?

O primeiro é um conceito local, o segundo é um conceito global.

O SGD pode eventualmente convergir para o valor extremo da função de custo. Estou me perguntando sobre a diferença entre a direção do gradiente, dado um ponto arbitrário no convexo e a direção apontando para o valor extremo global.

A direção do gradiente deve ser a direção na qual a função aumenta / diminui mais rapidamente nesse ponto, certo?

neural-networks optimization gradient-descent sgd convex Tyler 十三将士归玉门
fonte

6

Alguma vez você já andou em declive direto de um cume da montanha, apenas para se encontrar em um vale que continua ladeira abaixo em uma direção diferente? O desafio é imaginar uma situação com topografia convexa: pense em uma ponta da faca onde a crista é mais íngreme no topo.

whuber

4

Não, porque é descida de gradiente estocástico, não descida de gradiente. O ponto principal do SGD é que você joga fora algumas das informações do gradiente em troca de maior eficiência computacional - mas, obviamente, ao jogar fora algumas das informações do gradiente, você não terá mais a direção do gradiente original. Isso já está ignorando a questão de saber se o gradiente regular aponta ou não na direção da descida ideal, mas o ponto é que, mesmo se a descida regular do gradiente o fez, não há razão para esperar que a descida estocástica do gradiente o faça.

Chill2Macht

3

@ Tyler, por que sua pergunta é específica sobre a descida do gradiente estocástico . Você imagina de alguma forma algo diferente em comparação com a descida de gradiente padrão?

Sextus Empiricus

2

O gradiente sempre apontará para o ótimo no sentido de que o ângulo entre o gradiente e o vetor para o ótimo terá um ângulo menor que e, caminhando na direção do gradiente, uma quantidade infinitesimal aproximá-lo do ideal.

\frac{π}{2}

$\frac{\pi}{2}$

Restabeleça Monica

5

Se o gradiente apontasse diretamente para um minimizador global, a otimização convexa se tornaria super fácil, porque poderíamos fazer uma pesquisa de linha unidimensional para encontrar um minimizador global. Isso é demais para esperar.

littleO

36

Eles dizem que uma imagem vale mais que mil palavras. No exemplo a seguir (cortesia do MS Paint, uma ferramenta útil para estatísticos amadores e profissionais), você pode ver uma superfície de função convexa e um ponto em que a direção da descida mais íngreme claramente difere da direção em direção ao ideal.

Em uma observação séria: há respostas muito superiores neste tópico que também merecem um voto positivo.

Jan Kukacka
fonte

27

E o contra-exemplo de hoje é ... um abacate!

JDL

11

Você vê que, ao cortar um abacate, você deve cortar na direção mais descida para evitar as sementes e uma possível lesão .

Jan KUKACKA

28

Os métodos de descida em gradiente usam a inclinação da superfície.
Isso não necessariamente (ou mesmo provavelmente não) aponta diretamente para o ponto extremo.

Uma visão intuitiva é imaginar um caminho de descida que é um caminho curvo. Veja, por exemplo, os exemplos abaixo.

Como uma analogia: imagine que eu te venda os olhos e os coloco em algum lugar em uma montanha com a tarefa de voltar ao ponto extremo (baixo). Na colina, se você tiver apenas informações locais , não saberá em que direção estará o fundo do lago.

Se você pode assumir convexidade

Então você sabe que existe apenas um ponto extremo.
Então você sabe que certamente alcançará o ponto extremo enquanto se mover para baixo.
E então você também sabe que o ângulo entre a direção de descida mais íngreme e a direção ideal é sempre no máximo $\pi/2$ , como o Segredo de Salomonoff mencionado nos comentários.

Sem convexidade

O ângulo pode exceder $\pi/2$ . Na imagem abaixo, isso é enfatizado desenhando uma seta de direção de descida para um ponto específico em que a solução final está atrás da linha perpendicular à direção de descida.

No problema convexo, isso não é possível. Você pode relacionar isso às isolinhas para a função de custo com uma curvatura na mesma direção quando o problema é convexo.

Em descida estocástica de gradiente

Você segue a direção mais íngreme para um único ponto (e dá repetidamente um passo para um ponto diferente). No exemplo, o problema é convexo, mas pode haver mais de uma solução. No exemplo, os valores extremos estão em uma linha (em vez de um único ponto) e, desse ponto de vista específico, você poderia dizer que A direção de descida mais íngreme pode apontar diretamente para o "ideal" (embora seja apenas o ideal para a função desse ponto de amostra de treinamento específico)

Abaixo está outra visão para quatro pontos de dados . Cada uma das quatro imagens mostra a superfície para um ponto único diferente. Cada etapa é escolhido um ponto diferente ao longo do qual o gradiente é calculado. Isso faz com que haja apenas quatro direções pelas quais uma etapa é feita, mas o tamanho da etapa diminui quando nos aproximamos da solução.

As imagens acima são para 4 pontos de dados gerados pela função:

y_{Eu} = e^{- 0,4 x_{Eu}} - e^{- 0,8 x_{Eu}} + ϵ_{Eu}

$y_i = e^{-0.4x_i}-e^{-0.8 x_i} + \epsilon_i$

x = 0      2      4      6           
y = 0.006  0.249  0.153  0.098

o que resulta em:

um problema de otimização não convexo quando minimizamos a função de custo (não linear)
$S (uma, b) = \sum_{Eu = 1} {(y_{Eu} - (e^{- uma x_{Eu}} - e^{- b x_{Eu}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (e^{-ax_i}-e^{-b x_i}) \right)^2$ $\nabla S (uma, b) = [\begin{matrix} \sum_{Eu = 1} 2 x_{Eu} e^{- uma x_{Eu}} (y_{Eu} - e^{- uma x_{Eu}} - e^{- b x_{Eu}}) \\ \sum_{Eu = 1} - 2 x_{Eu} e^{- b x_{Eu}} (y_{Eu} - e^{- uma x_{Eu}} - e^{- b x_{Eu}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} 2 x_i e^{-a x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \\ \sum_{i=1} -2 x_i e^{-b x_i}\left( y_i - e^{-ax_i}-e^{-b x_i} \right) \end{bmatrix}$
um problema de otimização convexa (como quaisquer mínimos quadrados lineares) quando minimizamos
$S (uma, b) = \sum_{Eu = 1} {(y_{Eu} - (uma e^{- 0,4 x_{Eu}} - b e^{- 0,8 x_{Eu}}))}^{2}$ $S(a,b) = \sum_{i=1} \left( y_i - (a e^{-0.4 x_i}- b e^{-0.8 x_i} )\right)^2$ $\nabla S (uma, b) = [\begin{matrix} \sum_{Eu = 1} - 2 e^{- 0,4 x_{Eu}} (y_{Eu} - uma e^{- 0,4 x_{Eu}} - b e^{- 0,8 x_{Eu}}) \\ \sum_{Eu = 1} 2 e^{- 0,8 x_{Eu}} (y_{Eu} - uma e^{- 0,4 x_{Eu}} - b e^{- 0,8 x_{Eu}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} \sum_{i=1} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ \sum_{i=1} 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$
um problema de otimização convexa (mas não com um único mínimo) quando minimizamos para alguns que tem gradiente esta tem múltiplos mínimos (existem múltiplos e para o qual ) $i$
$S (uma, b) = {(y_{Eu} - (uma e^{- 0,4 b x_{Eu}} - b e^{- 0,8 x_{Eu}}))}^{2}$ $S(a,b) = \left( y_i - (a e^{-0.4 b x_i}- b e^{-0.8 x_i}) \right)^2$ $\nabla S (uma, b) = [\begin{matrix} - 2 e^{- 0,4 x_{Eu}} (y_{Eu} - uma e^{- 0,4 x_{Eu}} - b e^{- 0,8 x_{Eu}}) \\ 2 e^{- 0,8 x_{Eu}} (y_{Eu} - uma e^{- 0,4 x_{Eu}} - b e^{- 0,8 x_{Eu}}) \end{matrix}]$ $\nabla S(a,b) = \begin{bmatrix} -2 e^{-0.4x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \\ 2 e^{-0.8x_i}\left( y_i - a e^{-0.4x_i}- b e^{-0.8 x_i} \right) \end{bmatrix}$ $a$ $b$ $S = 0$

Escrito por StackExchangeStrike

Sextus Empiricus
fonte

17

A descida mais acentuada pode ser ineficiente, mesmo que a função objetivo seja fortemente convexa.

Descida de gradiente comum

Quero dizer "ineficiente" no sentido de que uma descida mais íngreme pode dar passos que oscilam muito longe do ideal, mesmo que a função seja fortemente convexa ou quadrática.

Considere . Isso é convexo porque é um quadrático com coeficientes positivos. Por inspeção, podemos ver que ele tem um mínimo global em . Possui gradiente $f(x)=x_1^2 + 25x_2^2$ $x=[0,0]^\top$

\nabla f (x) = [\begin{matrix} 2 x_{1} \\ 50. x_{2} \end{matrix}]

$\nabla f(x)= \begin{bmatrix} 2x_1 \\ 50x_2 \end{bmatrix}$

Com uma taxa de aprendizado de e suposição inicial temos a atualização gradiente $\alpha=0.035$ $x^{(0)}=[0.5, 0.5]^\top,$

x^{(1)} = x^{(0 0)} - α \nabla f (x^{(0 0)})

$x^{(1)} =x^{(0)}-\alpha \nabla f\left(x^{(0)}\right)$

que exibe esse progresso extremamente oscilante em direção ao mínimo.

De fato, o ângulo formado entre e decai gradualmente para 0. O que isso significa é que a direção da atualização às vezes está errada - no máximo, está quase 68 graus - mesmo que o algoritmo esteja convergindo e funcionando corretamente. $\theta$ $(x^{(i)}, x^*)$ $(x^{(i)}, x^{(i+1)})$

Cada etapa é extremamente oscilante porque a função é muito mais íngreme na direção que na direção . Por esse fato, podemos inferir que o gradiente nem sempre é, ou mesmo geralmente, apontando para o mínimo. Essa é uma propriedade geral da descida do gradiente quando os autovalores do Hessian estão em escalas diferentes. O progresso é lento nas direções correspondentes aos vetores próprios com os menores valores próprios correspondentes e mais rápido nas direções com os maiores valores próprios. É essa propriedade, em combinação com a escolha da taxa de aprendizado, que determina a rapidez com que a descida do gradiente progride. $x_2$ $x_1$ $\nabla^2 f(x)$

O caminho direto para o mínimo seria mover-se "diagonalmente" em vez de dessa maneira, que é fortemente dominada por oscilações verticais. No entanto, a descida em gradiente só possui informações sobre inclinação local; portanto, "não sabe" que a estratégia seria mais eficiente e está sujeita aos caprichos do hessiano com valores próprios em diferentes escalas.

Descida do gradiente estocástico

O SGD tem as mesmas propriedades, com exceção das atualizações barulhentas, o que implica que a superfície do contorno parece diferente de uma iteração para a seguinte e, portanto, os gradientes também são diferentes. Isso implica que o ângulo entre a direção da etapa do gradiente e a ideal também terá ruído - imagine as mesmas plotagens com alguma instabilidade.

Mais Informações:

Esta resposta empresta este exemplo e figura do Projeto de Redes Neurais (2ª Ed.), Capítulo 9, de Martin T. Hagan, Howard B. Demuth, Mark Hudson Beale, Orlando De Jesús.

Sycorax diz restabelecer Monica
fonte

13

A direção mais íngreme local não é a mesma com a direção ideal global. Se fosse, sua direção do gradiente não mudaria; porque se você for para o seu ideal sempre, seu vetor de direção apontará sempre ideal. Mas não é esse o caso. Se fosse esse o caso, por que se preocupar em calcular seu gradiente a cada iteração?

gunes
fonte

3

As outras respostas destacam alguns problemas irritantes de taxa de convergência para GD / SGD, mas seu comentário "SGD pode eventualmente convergir ..." nem sempre é correto (ignorando as observações de uso pedante sobre a palavra "pode", pois parece que você quis dizer "vai").

Um bom truque para encontrar contra-exemplos com o SGD é perceber que, se cada ponto de dados for o mesmo, sua função de custo é determinística. Imagine o exemplo extremamente patológico em que temos um ponto de dados e temos um modelo de como nosso sistema deve funcionar com base em um único parâmetro

(x_{0 0}, y_{0 0}) = (1, 0 0)

$(x_0,y_0)=(1,0)$

α

$\alpha$

f (x, α) = \sqrt{α^{2} - α x} .

$f(x,\alpha)=\sqrt{\alpha^2-\alpha x}.$

Com o MSE como nossa função de custo, isso simplifica para uma função convexa. Suponha que escolhemos mal a nossa taxa de aprendizado modo que nossa regra de atualização seja a seguinte:Agora, a nossa função de custo tem um mínimo de , mas se começar literalmente em qualquer lugar que não seja então SGD simplesmente saltar entre o ciclo entre o ponto de partida e e não convergem .

(f (x_{0 0}, α) - y_{0 0})^{2} = α^{2} - α,

$(f(x_0,\alpha)-y_0)^2=\alpha^2-\alpha,$

β

$\beta$

α_{n + 1} = α_{n} - β (2 α_{n} - 1) = α_{n} - (2 α_{n} - 1) = 1 - α_{n} .

$\alpha_{n+1}=\alpha_n-\beta(2\alpha_n-1)=\alpha_n-(2\alpha_n-1)=1-\alpha_n.$

α = \frac{1}{2}

$\alpha=\frac12$ $p=\frac12$

p

$p$

1 - p

$1-p$

Não tenho certeza se a convexidade é suficiente para interromper um comportamento pior que existe para o SGD geral, mas se você permitir funções tão complexas quanto as cúbicas para sua função de custo, o SGD poderá saltar em um denso subconjunto do domínio e nunca convergir para lugar algum. ou abordar qualquer ciclo.

O SGD também pode se aproximar / obter ciclos de qualquer comprimento finito, divergir em direção a , oscilar em direção a (desculpe a notação) e ter muitos outros comportamentos patológicos. $\infty$ $\pm\infty$

Uma coisa interessante sobre toda a situação é que existem inúmeras funções (como SGD) que assumem funções convexas arbitrárias como entradas e, em seguida, emitem uma regra de atualização que sempre converge rapidamente para o mínimo global (se houver). Embora conceitualmente existam muitas delas, todas as nossas melhores tentativas de otimização convexa têm contra-exemplos patológicos. De alguma forma, a idéia de uma regra de atualização simples / intuitiva / de desempenho contraria a idéia de uma regra de atualização comprovadamente correta.

Hans Musgrave
fonte

1

+1 para esta observação. Mas, este é um pouco de má escolha e também seria ruim no caso de descida regular de gradiente. É um bom comentário, mas não está realmente relacionado à questão de saber se o caminho de descida mais íngreme aponta para a solução ou não, mas sim à questão de tamanhos de etapas muito grandes que podem levar a atualizações divergentes.

β = 1

$\beta=1$

Sexto Empírico

1

Note-se que a prova de convergência SGD assume um tamanho de passo diminuindo ...

Jan KUKACKA

@MartijnWeterings Boa observação. Acho que meu exemplo realmente aponta a direção correta. Devo atualizá-lo com um exemplo 2D que nunca aponta a direção certa e diverge?

Hans Musgrave

β = 1

$\beta=1$

β > 0

$\beta>0$

β

$\beta$

f (x, α) = \sqrt{\frac{α^{2} - α x}{β}} .

$f(x,\alpha)=\sqrt{\frac{\alpha^2-\alpha x}{\beta}}.$

Hans Musgrave

@JanKukacka Essa é uma modificação comum no SGD que sofre de uma falha semelhante. Em vez de a função de custo ser uma parábola, você escolhe para que a função de custo seja uma função convexa simétrica aumentando rapidamente o suficiente em ambas as direções a partir do mínimo para neutralizar a taxa de resfriamento de . As provas de convergência SGD que eu vi são apenas com probabilidade 1 e baseiam-se em funções de custo mal escolhidas, existindo com probabilidade 0 com medidas típicas no espaço das funções de custo.

f

$f$

β

$\beta$

Hans Musgrave

2

Talvez as respostas a esta pergunta precisem de uma atualização rápida. Parece que o SGD produz um mínimo global também no caso não convexo (convexo é apenas um caso especial disso):

SGD Converge Para Mínimo Global Em Deep Learning Por Star-Convex Path, autores Anônimos , Artigo sob revisão duplo-cega na ICLR 2019

https://openreview.net/pdf?id=BylIciRcYQ

Os autores estabelecem a convergência do SGD para um mínimo global para problemas de otimização não-convexos que são comumente encontrados no treinamento de redes neurais. O argumento explora as duas propriedades importantes a seguir: 1) a perda de treinamento pode atingir valor zero (aproximadamente); 2) O SGD segue um caminho convexo em estrela. Nesse contexto, embora o SGD tenha sido considerado um algoritmo aleatório há muito tempo, o artigo revela que ele converge de maneira intrinsecamente determinística para um mínimo global.

Isso deve ser tomado com um grão de sal. O artigo ainda está em revisão.

A noção de caminho estrela-convexo fornece uma dica sobre para onde o gradiente apontaria a cada iteração.

Tolga Birdal
fonte

Para problemas convexos, o gradiente na descida do gradiente estocástico (SGD) sempre aponta para o valor extremo global?

Respostas:

Se você pode assumir convexidade

Sem convexidade

Em descida estocástica de gradiente

Descida de gradiente comum

Descida do gradiente estocástico