Por que não usar a terceira derivada para otimização numérica?

29

Se os hessianos são tão bons em otimização (veja, por exemplo, o método de Newton ), por que parar aí? Vamos usar o terceiro, quarto, quinto e sexto derivados? Por que não?

eco
fonte
11
Depois de encontrar o ideal, por que procurar mais? Na verdade, o que você realmente está tentando perguntar? Qual é a sua pergunta estatística?
whuber
2
Em muitos casos, a distribuição limitadora de estimativas que resolvem equações ótimas de estimativa ou minimizam funções objetivas é conjuntamente normal, para que possam ser caracterizadas inteiramente pelo primeiro e segundo momentos.
Adamo
3
Se você pode fazer algo, não significa que você deve fazê-lo. Derivados de ordem superior são cada vez mais suscetíveis ao ruído.
Vladislavs Dovgalecs
6
Estou votando para encerrar esta questão como fora de tópico, porque não se trata de estatísticas. Trata-se de otimização numérica.
Aksakal
11
Você não fez um avanço científico. Halley venceu você por cerca de 3 1/4 séculos. Halley, E., 1694, "Um método novo, exato e fácil de encontrar as raízes de qualquer equação em geral, e sem nenhuma redução anterior" Philos. Trans. Roy. Soc. Londres, 18, 136–145. Os métodos da 3ª derivada para otimização existem e são estudados há muitos anos, mas não alcançaram grande popularidade. Se bem implementada, sua maior vantagem pode ser um aumento na robustez versus um método de Newton bem implementado. Isso pode ser vantajoso para os problemas mais desagradáveis.
Mark L. Stone

Respostas:

31

Estou interpretando a pergunta como sendo "Por que o método de Newton usa apenas a primeira e a segunda derivadas, não as derivadas de terceiros ou superiores?"

Na verdade, em muitos casos, ir para a terceira derivada ajuda; Eu já fiz isso com coisas personalizadas antes. No entanto, em geral, ir para derivadas mais altas acrescenta complexidade computacional - você precisa encontrar e calcular todas essas derivadas e, para problemas multivariados, há muito mais derivadas terceiras do que derivadas iniciais! - supera em muito as economias na contagem de etapas que você obtém, se houver. Por exemplo, se eu tiver um problema tridimensional, eu tenho 3 primeiras derivadas, 6 segundas derivadas e 10 terceiras derivadas, portanto, ir para uma versão de terceira ordem mais do que duplica o número de avaliações que tenho que fazer (de 9 para 19), para não mencionar o aumento da complexidade do cálculo da direção / tamanho da etapa depois que eu tiver feito essas avaliações, mas quase certamente não reduzirá o número de etapas que tenho que executar pela metade.

knth(k+n1k1)

jbowman
fonte
3
Você poderia explicar como você está usando derivadas mais altas?
whuber
5
@whuber O que o OP está se referindo, extremamente claro que eu tenho que admitir, é o método de otimização de Newton. A questão é: "Por que o método de Newton usa apenas a primeira e a segunda derivadas, não as derivadas de terceiros ou superiores?". É fora de tópico e não está claro o que ele está perguntando, mas pensei em dar uma resposta em vez de votar para fechar por um motivo ou outro.
jbowman
4
+1 Acho que essa é uma boa resposta, mas poderia ser melhorada mostrando o que você está fazendo com base na expansão de taylor.
Matthew Drury
8
Como um dos meus professores - um consultor de muito sucesso - nos disse uma vez: "Sempre que você pensar em como construir uma ratoeira melhor, tente descobrir por que as mil pessoas que tiveram essa mesma idéia antes que você não o coloque no mercado ". O objetivo de usar Newton é salvar a computação - caso contrário, faríamos uma pesquisa exaustiva. Garanto-lhe que adicionar uma terceira derivada a um problema tridimensional pagará muito, muito raramente, pela duplicação da computação em cada etapa, com iterações muito reduzidas, a menos que a função seja ~ cúbica.
jbowman
9
Não, não é - é um comentário um pouco mais profundo do que parece à primeira vista. O ponto é duplo - a maioria das idéias que parecem boas no começo não é, por razões que podem não ser óbvias, e a chave real para uma quebra pode não ser a ideia em si, mas algo que supera ou contorna a falha no a ideia. Esse raciocínio, na verdade, aponta isso e diz para você procurar pontos fracos na idéia. Não se trata de desistir, é de pensar sobre as coisas, e com um olhar crítico nisso.
jbowman
22

Realmente não vejo qual é o aspecto estatístico dessa pergunta, então responderei a parte da otimização.

Existem duas partes na convergência: custo da iteração e contagem da iteração

Praticamente todas as respostas aqui estão focadas apenas no custo da iteração e ignorando a contagem de iterações . Mas os dois são importantes. Um método que itera em 1 nanossegundo, mas que leva iterações para convergir não fará nenhum bem. E um método que explode também não ajuda, por mais barato que seja o custo da iteração.1020

Vamos descobrir o que está acontecendo.

Então: por que não usar derivados de segunda ordem?

Em parte porque (e isso também é válido para a segunda ordem, mas mais sobre isso daqui a pouco):

Métodos de ordem superior geralmente convergem mais rapidamente quando estão próximos do ideal .

Por outro lado, explodem mais facilmente quando estão mais longe do ideal!

(Obviamente, isso nem sempre é verdade; por exemplo, um quadrático irá convergir em 1 passo com o método de Newton. Mas, para funções arbitrárias no mundo real que não têm boas propriedades, isso geralmente é verdade.)

Isso significa que, quando você está mais longe do ideal, geralmente deseja um método de ordem baixa (leia-se: primeira ordem). Somente quando você estiver perto, você deseja aumentar a ordem do método.

Então, por que parar na 2ª ordem quando você está perto da raiz?

Porque o comportamento de convergência "quadrático" é realmente "bom o suficiente"!

Para entender por que, primeiro você precisa entender o que significa "convergência quadrática" .

Matematicamente, convergência quadrática significa que, se for seu erro na iteração , o seguinte será válido para alguma constante :ϵkkc

|ϵk+1|c |ϵk|2

Em inglês simples, isso significa que, quando você estiver próximo do ideal (importante!), Cada etapa extra dobra o número de dígitos de precisão .

Por quê? É fácil ver com um exemplo: para e , você tem , , etc., o que é ridiculamente rápido . (É super-exponencial !)c=1|ϵ1|=0.1|ϵ2|0.01|ϵ3|0.0001

Por que não parar na 1ª ordem e não na 2ª ordem?

Na verdade, as pessoas costumam fazer isso quando os derivativos de segunda ordem ficam muito caros. Mas a convergência linear pode ser muito lenta. por exemplo, se você obteve , talvez precise de 10.000.000 de iterações com convergência linear para obter , mas apenas 23 iterações com convergência quadrática. Então você pode ver por que há uma diferença drástica entre convergência linear e quadrática. Isso não é verdade para a convergência de segunda e terceira ordem, por exemplo (veja o próximo parágrafo).ϵk=0.9999999|ϵ|<0.5

Nesse ponto, se você conhece alguma ciência da computação, entende que, com a convergência de segunda ordem, o problema está resolvido . Se você não vê o porquê, eis o porquê: não há nada prático a ganhar ao triplicar o número de dígitos a cada iteração, em vez de dobrá -lo - o que ele vai comprar? Afinal, em um computador, mesmo um doublenúmero de precisão tem 52 bits de precisão, que tem cerca de 16 dígitos decimais. Talvez isso diminua o número de etapas necessárias de 16 para 3 ... o que parece ótimo, até você perceber que isso custa o preço de ter que calcular terceiros derivados a cada iteração, e é aí que está a maldição da dimensionalidade.bate forte em você. Para um problema de dimensão , você acabou de pagar um fator de para obter um fator de , o que é idiota. E no mundo real, os problemas têm pelo menos centenas de dimensões (ou mesmo milhares ou até milhões), e não apenas ! Então você ganha um fator de talvez 20 pagando um fator de, digamos, 20.000 ... dificilmente é uma troca sábia.6656

Mas, novamente: lembre-se de que a maldição da dimensionalidade é metade da história .

A outra metade é que você geralmente tem um comportamento pior quando está longe do ideal, o que geralmente afeta negativamente o número de iterações que você deve fazer.

Conclusão

Em um cenário geral, métodos de ordem superior a 2 são uma má idéia. Obviamente, se você pode trazer suposições úteis adicionais para a tabela (por exemplo, talvez seus dados se assemelhem a um polinômio de alto grau ou você tenha maneiras de limitar a localização do ótimo etc.), talvez seja possível que eles sejam uma boa idéia - mas essa será uma decisão específica do problema, e não uma regra geral a seguir.

Mehrdad
fonte
Ótima resposta, mas acho que o teorema de Abel-Ruffini é um arenque vermelho. Antes de tudo, estamos falando de problemas multivariados; portanto, calcular zeros de polinômios univariados é, no máximo, um subproblema fácil de interesse limitado. E, mais importante, não importa se existe ou não uma fórmula fechada: na prática, tanto quanto eu sei, as pessoas não usam fórmulas fechadas nem para polinômios de grau 4. Eles são muito longos, complicados e instáveis. Zeros de polinômios são computados numericamente, na prática (usando QR na matriz associada).
Federico Poloni
@FedericoPoloni: Sim, os mesmos pensamentos me vieram à mente quando eu decidi colocá-lo. Eu não o tinha originalmente ... pensei que talvez devesse colocá-lo como apenas mais um exemplo de por que os graus mais altos podem ter problemas inesperados. Mas acho que vou retirá-lo novamente se não for útil, obrigado pelo comentário.
Mehrdad 23/12
@FedericoPoloni: PS: Enquanto estamos no assunto da computação numérica, você pode achar as funções do Sturm interessantes (se você ainda não as ouviu).
Mehrdad 23/12
7

Até calcular Hessianos é bastante trabalhoso:

H=[2fx122fx1x22fx1xn2fx2x12fx222fx2xn2fxnx12fxnx22fxn2].

Agora veja como é a terceira derivada: Essa é uma matriz tridimensional. Veja como seus elementos se parecem:

H/x=[Hx1Hx2Hxn]
(H/x)ijk=3fxixjxk

A derivada da sexta será a matriz tridimensional:

6fxixjxkxlxmxn

Normalmente, o trade-off não é favorável para ir mais alto que o Hessian. Quero dizer a troca entre ganho potencial em velocidade através do uso de aproximações de ordem superior versus amplificação de ruído. Você sempre tem ruído nas entradas, porque estamos falando de aplicações estatísticas. Este ruído será amplificado pelos derivados.

Se você joga golfe, a analogia na otimização é primeiro balançar tentando chegar ao verde, não se preocupe muito com um buraco. Uma vez, no verde, colocaremos um buraco.

Aksakal
fonte
4

Normalmente, quando você analisa a eficácia de tais algoritmos, encontrará resultados como uma etapa de um algoritmo de quarta ordem com aproximadamente a mesma eficácia de duas etapas de um algoritmo de segunda ordem.

Portanto, a escolha de qual algoritmo usar é relativamente simples: se uma etapa do algoritmo de quarta ordem exige duas vezes mais trabalho ou mais de uma etapa do algoritmo de segunda ordem, você deve usá-lo.

Essa é a situação típica para esses tipos de métodos: o algoritmo clássico possui a taxa ideal de trabalho / eficácia para problemas gerais. Embora existam problemas ocasionais em que uma abordagem de ordem superior é incomumente fácil de calcular e possa superar a variante clássica, eles são relativamente incomuns.


fonte
2

Você pode pensar na ordem das derivadas como a ordem de uma aproximação polinomial da função. A maioria das rotinas de otimização depende de convexidade. Um polinômio quadrático será convexo / côncavo em todos os lugares, enquanto um polinômio de terceira ordem ou superior não será convexo em todos os lugares. A maioria das rotinas de otimização se baseia em aproximações sucessivas de funções convexas com quadráticos por esse motivo. Uma aproximação quadrática que é convexa exige que uma condição de definição positiva seja imposta para que o quadrático seja convexo.

Lucas Roberts
fonte
3
Não, os quadráticos não são necessariamente convexos ou côncavos (pense em ). x2y2
Dirk
@Dirk igual a quê? x2y2
Ovi
1
É uma função quadrática, mas nem convexa nem côncava.
Dirk
@Dirk sim, você está certo, eu deveria ter adicionado uma ressalva semi-definida positiva. Vou acrescentar isso à minha resposta.
Lucas Roberts
1

Deixe-me ser o único aqui defendendo métodos de 3ª ordem para a convergência SGD, mas definitivamente não em todo o espaço o que precisaria coeficientes, mas por exemplo, em apenas uma direção, que precisa apenas de um único coeficiente adicional se já tendo modelo de 2ª ordem nessa direção.dim3/6

Por que o modelo de 3ª ordem de direção única pode ser benéfico? Por exemplo, porque quase zero segundo derivado nessa direção significa basicamente dois cenários alternativos: platô ou ponto de inflexão - apenas o primeiro requer tamanho de passo maior e o terceiro derivado permite distingui-los.

Acredito que iremos para métodos híbridos de múltiplas ordens: método de 2ª ordem em um subespaço de baixa dimensão, por exemplo, do PCA de gradientes recentes, o que ainda permite a descida simultânea de gradiente de 1ª ordem gratuita em direção a parte do gradiente ortogonal a esse subespaço ... e adicionalmente Eu acrescentaria, por exemplo, o modelo de terceira ordem para uma única direção mais relevante.

Jarek Duda
fonte