Por que a descida do gradiente é necessária?

9

Quando podemos diferenciar a função de custo e encontrar parâmetros resolvendo equações obtidas por meio de diferenciação parcial com relação a cada parâmetro e descobrir onde a função de custo é mínima. Também acho que é possível encontrar vários locais onde as derivadas são zero, assim podemos verificar todos esses locais e encontrar mínimos globais

por que a descida gradiente é executada?

Niranjan Kotha
fonte
2
Como se define genericamente as derivadas para 0 para uma função? Com algoritmos, como descida de gradiente.
Cliff AB
3
Você pode pensar em descida de gradiente como o método usado para resolver as equações às quais você está se referindo. Se você acredita que pode resolver genericamente essas equações com manipulação algébrica inteligente, convido você a tentar fazê-lo para a regressão logística.
Matthew Drury
11
Veja também stackoverflow.com/questions/26804656/…
Glen_b -Reinstate Monica
você não pode resolver tudo analiticamente. Mesmo se você pudesse, se houvesse um número incontável de zeros, levaria muito tempo para verificar todos os pontos críticos.
Pinocchio

Respostas:

7

Mesmo no caso de, digamos, modelos lineares, nos quais você tem uma solução analítica, ainda pode ser melhor usar um solucionador iterativo.

Como exemplo, se considerarmos a regressão linear, a solução explícita exige a inversão de uma matriz que tenha complexidade . Isso se torna proibitivo no contexto de big data.O(N3)

Além disso, muitos problemas no aprendizado de máquina são convexos; portanto, o uso de gradientes garante que chegaremos ao extremo.

Como já apontado, ainda existem problemas não convexos relevantes, como redes neurais, onde métodos de gradiente (retropropagação) fornecem um solucionador eficiente. Novamente, isso é especialmente relevante para o caso de aprendizado profundo.

jpmuc
fonte
2
A inversão de uma matriz é um pouco complicada aqui, pois a decomposição de QR com pivô parcial é mais precisa e rápida, mas sim, o QR ainda é . Concordo que em sistemas suficientemente grandes (por exemplo,> 10.000 variáveis) que podem começar a se tornar um problema. A abordagem moderna e de alta tecnologia é aproximar a solução com métodos iterativos do subespaço de Krylov (por exemplo, gradiente conjugado, GMRES). O(n3)
Matthew Gunn
11
Um ponto que algumas pessoas podem achar confusas é como resolver um sistema linear é um problema de otimização? A resposta, é claro, é que a solução de um sistema linear pode ser reformulada, minimizando um objetivo quadrático. Alguns métodos iterativos para resolver sistemas lineares são mais fáceis de entender da perspectiva de que eles estão minimizando um objetivo quadrático de maneira iterativa. (. Por exemplo, direção etapa do método de subespaço de Krylov do gradiente conjugado é baseado no gradiente ... é vagamente relacionadas com gradiente descendente.)
Matthew Gunn
12

A descida do gradiente não é necessária. Acontece que a descida do gradiente geralmente é um algoritmo de otimização horrivelmente ineficiente! Para métodos iterativos, muitas vezes é possível encontrar uma direção melhor para se mover do que onde o gradiente é mais íngreme.

Isso é um pouco de resposta inversa. Sua pergunta realmente deveria ser: "por que precisamos de métodos iterativos?" Por exemplo. por que não ir direto para a solução se o problema é convexo, a condição de Slater se mantém e as condições de primeira ordem são necessárias e condições suficientes para um ótimo? Ou seja, quando a solução pode ser descrita como a solução para um sistema de equações, por que não simplesmente resolver o sistema? A resposta é que:

  • Para um problema de otimização quadrática, a condição de primeira ordem é um sistema de equações lineares, e podemos ir quase diretamente para a solução, porque os sistemas lineares podem ser resolvidos com eficiência! Nós não usar as condições de primeira ordem e resolver o sistema (por exemplo., Com QR decomposição, ressalva abaixo).
  • De um modo mais geral, as condições de primeira ordem definem um sistema não linear de equações e um sistema não linear pode ser bastante difícil de resolver! De fato, a maneira como você costuma resolver numericamente um sistema de equações não lineares é reformulá-lo como um problema de otimização ...
  • Para sistemas lineares extremamente grandes , a solução do sistema diretamente com decomposição QR e rotação parcial torna-se inviável. O que as pessoas fazem?! Métodos iterativos! (por exemplo, métodos iterativos de subespaço de Krylov ...)
Matthew Gunn
fonte
7

No cálculo 101, aprendemos sobre como otimizar uma função usando o "método analítico": precisamos apenas obter a derivada da função de custo e definir a derivada como 0 e depois resolver a equação. Este é realmente um problema de brinquedo e quase nunca acontecerá no mundo real.

No mundo real, muitas funções de custo não têm derivada em todos os lugares (além disso, a função de custo pode ser discreta e não possui derivada). Além disso, mesmo que você possa calcular a derivada, não pode simplesmente resolver a equação analiticamente (por exemplo, pense em como resolver analiticamente? Posso dizer que a resposta numérica é , mas não sei a solução analítica). Devemos usar alguns métodos numéricos (verifique o porquê aqui nos casos polinomiais Teorema de Abel Ruffin ).x7+x352+ex+log(x+x2)+1/x=0x=1.4786

Métodos iterativos são ótimos de usar e muito intuitivos de entender. Suponha que você queira otimizar uma função, em vez de resolver uma equação e obter a resposta, tente melhorar sua resposta pelo número de iterações / etapas após iteração suficiente, a resposta será próxima de "resposta verdadeira". Digamos que, se você usa cálculo para minimizar , obtém diretamente , mas usando métodos numéricos, pode obter .f(x)=x2x=0x=1.1234×1020

Agora, é importante entender como esses métodos iterativos funcionam. O conceito principal é saber como atualizar seus parâmetros de entrada para obter uma solução melhor. Suponha que você queira minimizar(observe que essa função de custo não é diferenciável em todos os lugares, mas pode ser diferenciada em "na maioria dos lugares", isso é bom o suficiente para nós, pois sabemos como atualizar na "maioria dos lugares".), atualmente você está em , e o custo é , agora você deseja atualizar para diminuir a função objetiva. Como você faria isso? Você pode dizer que quero diminuir os dois , mas por quê? Na verdade, você está implícito usandof(x1,x2)=x12+x22+|x1+x2|(1,1)4.0(x1,x2)x1 x2o conceito de gradiente "mudando pequena quantidade de , o que acontecerá em ". xy. Em , a derivada é , portanto, gradiente negativo vezes uma taxa de aprendizado digamos , é , por isso atualizamos nossa solução de para que possuem melhor custo.(1,1)(3,3)α=0.0011 , 1 ( 0,997 , 0,997 )(0.003,0.003)1,1(0.997,0.997)

Haitao Du
fonte
mais informações podem ser encontradas neste post relacionado #
Haitao Du 16/16
4

A abordagem que você mencionou só pode ser usada para resolver um conjunto de equações lineares, por exemplo, no caso de regressão linear, mas digamos que para resolver um conjunto de equações não lineares, em casos como redes neurais com ativações sigmóides, a descida em gradiente é a abordagem. para ir. Assim, a descida do gradiente é uma abordagem mais genérica.

Mesmo para equações lineares, o tamanho das matrizes dado pelo conjunto de equações lineares é enorme e pode ser difícil restringir o requisito de memória.

Amitoz Dandiana
fonte