O que significa para um algoritmo convergir?

5

Continuo a encontrar este termo quando leio sobre a aprendizagem de reforço, por exemplo, nesta frase:

If the problem is modelled with care, some Reinforcement Learning algorithms can converge to the global optimum

link

ou aqui:

For any fixed policy Pi, the TD algorithm described above has been proved to converge to VPi

link

Meu entendimento da palavra convergem é que isso significa várias coisas se unindo no mesmo ponto, mas como pode uma única coisa (o algoritmo) fazer isso?

    
por starfish 05.07.2015 / 18:56
fonte

1 resposta

8

Um algoritmo iterativo é dito convergir quando, à medida que as iterações prosseguem, a saída se aproxima e se aproxima de um específico valor. Mais precisamente, não importa quão pequeno seja um valor de erro escolhido, se você continuar por muito tempo, a função ficará mais próxima do que o valor de erro de algum valor final.

Em algumas circunstâncias, um algoritmo não convergirá; pode até divergir, onde sua saída sofrerá oscilações cada vez maiores, nunca se aproximando de um resultado útil. Mais precisamente, não importa quanto tempo você continue, o valor da função nunca se estabelecerá dentro de um intervalo de qualquer valor "final".

A frase "convergem para um ótimo global" em sua primeira sentença é uma referência a algoritmos que podem convergir, mas não ao valor "ótimo" (por exemplo, um algoritmo de subida que, dependendo das condições iniciais, pode convergir para um máximo local, nunca atingindo o máximo global).

    
por 05.07.2015 / 21:52
fonte