Cosa significa per un algoritmo convergere?

5

Continuo a leggere questo termine quando leggo sull'apprendimento rinforzato, per esempio in questa frase:

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

link

o qui:

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

link

La mia comprensione della parola converge è che significa che diverse cose si uniscono nello stesso punto, ma come può una singola cosa (l'algoritmo) farlo?

    
posta starfish 05.07.2015 - 18:56
fonte

1 risposta

8

Si dice che un algoritmo iterativo converge quando, mentre procede l'iterazione, l'output si avvicina sempre più ad uno specifico valore. Più precisamente, indipendentemente da quanto piccolo valore di errore si sceglie, se si continua abbastanza a lungo la funzione alla fine rimarrà più vicino di quel valore di errore da qualche valore finale.

In alcune circostanze, un algoritmo non convergerà; potrebbe persino divergere, dove la sua uscita subirà oscillazioni sempre più grandi, senza mai avvicinarsi a un risultato utile. Più precisamente, indipendentemente da quanto tempo continui, il valore della funzione non si stabilirà mai entro un intervallo di qualsiasi valore "finale".

La frase "convergere in un globale ottimale" nella tua prima frase è un riferimento ad algoritmi che possono convergere, ma non al valore "ottimale" (ad esempio un algoritmo di salita che, a seconda delle condizioni iniziali, può convergere in un massimo locale, non raggiungendo mai il massimo globale.

    
risposta data 05.07.2015 - 21:52
fonte

Leggi altre domande sui tag