Convergence d'un algorithme
La convergence d'un algorithme fait souvent référence à un état de stabilité de certaines valeurs d'un système mesuré via une certaine métrique. Un algorithme étant une série d'étapes de calculs élémentaires, on dira souvent qu'un algorithme converge lorsqu'une métrique particulière ne varie plus, du moins de façon significative, d'une étape à l'autre de l'algorithme.
Par exemple, considérons[style à revoir] un algorithme de propagation de scores dans un graphe. Une étape de l'algorithme consiste en la propagation des scores de chacun des nœuds du graphe à ses voisins. Ainsi, chaque nœud, à une étape particulière, peut mettre à jour la valeur du score qui lui est associé en fonction de l'ensemble des scores reçus de ses nœuds voisins. Dans ce cas particulier, on dira que l'algorithme converge s'il existe bien une étape à partir de laquelle les scores des nœuds du graphe ne varient plus. A partir de cette étape, on pourra dira que l'algorithme "a convergé". Dans cet exemple, une métrique pouvant mesurer la stabilité des scores peut être la somme des différences des scores de chacun des nœuds prises à deux étapes successives de l'algorithme. La métrique mesure donc la variation des scores d'une étape à l'autre de l'algorithme. Si cette métrique, en fonction du nombre d'étapes de calculs réalisées par l'algorithme atteint un plateau, c'est-à-dire si cette métrique tend vers une certaine valeur particulière sans jamais la dépasser, on pourra dire que l'algorithme converge.
En apprentissage automatique, une métrique communément utilisée consiste à mesurer la variation dans l'erreur du modèle lors de la phase d'apprentissage: lorsque l'erreur varie très peu entre deux pas de temps, on considère que le modèle a convergé.
Notes et références[modifier]
Erreur Lua dans Module:Catégorisation_badges à la ligne 170 : attempt to index field 'wikibase' (a nil value).Erreur Lua dans Module:Suivi_des_biographies à la ligne 189 : attempt to index field 'wikibase' (a nil value).
Cet Article wiki "Convergence d'un algorithme" est issu de Wikipedia. La liste de ses auteurs peut être visible dans ses historiques et/ou la page Edithistory:Convergence d'un algorithme.
