Como o algoritmo de trabalho Levenberg-Marquardt em detalhes, mas de uma forma compreensível?

Question

Im um programador que queira aprender como o algoritmo curvefitting Levenberg-Marquardt trabalha para que eu possa implementá-lo eu mesmo. Existe um lugar bom tutorial que pode explicar como funciona em detalhes com o leitor sendo um programador e não um mathemagician.

Meu objetivo é implementar este algoritmo em OpenCL para que eu possa executá-lo hardware acelerado.

Answer 1

• Tente http://en.wikipedia.org/wiki/Levenberg-Marquardt_algorithm
• PDF Tutorial de Ananth Ranganathan
• JavaNumerics tem uma implementação muito legível
• O ICS tem um C / C ++ implementação

Answer 2

Minimizar uma função é como tentar encontrar o ponto mais baixo em uma superfície. Pense em si mesmo caminhar sobre uma superfície montanhosa e que você está tentando chegar ao ponto mais baixo. Você iria encontrar a direção que vai descer e caminhar até que ele não ir para baixo mais. Então você teria que escolher uma nova direção que vai descer e caminhar nessa direção até que ele não ir para baixo mais, e assim por diante. Eventualmente (espero) que você chegar a um ponto onde nenhuma direção vai descer mais. Você, então, seria no mínimo (local).

O algoritmo LM, e muitos outros algoritmos de minimização, use este esquema.

Suponha que a função a ser minimizada é F e estamos no ponto x (n) em nossa iteração. Desejamos para encontrar a próxima iteração x (n + 1) de modo a que F (x (n + 1))

Primeiro, computar uma aproximação linear a F no ponto x (n). É fácil encontrar a direção declive de uma função linear, por isso usamos a função de aproximação linear para determinar a direção ladeira abaixo. Em seguida, precisamos saber o quão longe podemos ir nesta direção escolhida. Se nossa função linear da aproximação é uma boa aproximação para F para uma grande área ao redor x (n), então podemos ter um bastante grande passo. Se é uma boa aproximação só é muito perto de x (n), então podemos tomar apenas um passo muito pequeno.

Isto é o que LM faz - calcula uma aproximação linear para F em x (n), dando, assim, a direção para baixo, em seguida, ele descobre como um grande passo a tomar com base em quão bem a função linear aproxima F em x (n ). LM descobre como boa a função de aproximação é por basicamente tendo um passo na direcção determinada e, portanto, comparar a quantidade da aproximação linear à F diminuiu para o quanto o a função real F diminuíram. Se eles estão perto, a função de aproximação é boa e podemos dar um passo pouco maior. Se eles não estão perto, em seguida, a função de aproximação não é boa e devemos recuar e dar um passo menor.

Answer 3

As idéias básicas do algoritmo LM pode ser explicado em poucas páginas - mas para uma implementação de produção grau que é rápido e robusto, muitas otimizações sutis são necessárias. Estado da técnica ainda é a implementação MINPACK em mais et al., Documentada em detalhe em mais de 1978 ( http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf ) e no guia do usuário MINPACK ( http://www.mcs.anl.gov/~more/ANL8074b.pdf ). Para estudar o código, o meu C tradução ( https://jugit.fz-juelich.de/mlz / LMFIT ) é provavelmente mais acessível do que o código Fortran originais.

Answer 4

Tente Numerical Recipes (Levenberg-Marquardt é na Seção 15.5). Está disponível on-line, e eu acho que eles explicam algoritmos de uma forma que está detalhado (eles têm código-fonte completo, quanto mais detalhado você pode obter ...), mas acessível.

Answer 5

estas notas de um curso na Universidade de Purdue para código de um Levenberg-Marquardt algoritmo de ajuste de curva genéricos no MATLAB que calcula derivados numéricos e, portanto, aceita qualquer função do f(x;p) formulário onde p é um vetor de montagem parâmetros.