L'algorithme avant-arrière est une technique fondamentale de programmation dynamique utilisée dans le contexte des modèles de Markov cachés (HMM) et des modèles de séquences probabilistes associés. Il calcule la distribution marginale a posteriori de chaque état caché étant donné une séquence d'observations, permettant une inférence efficace et une estimation des paramètres. L'algorithme est une pierre angulaire de l'apprentissage automatique classique et reste pertinent dans des applications modernes telles que la reconnaissance vocale, la bioinformatique et le traitement du langage naturel.
Développé à la fin des années 1960 et au début des années 1970, l'algorithme a été formalisé par Leonard Baum et ses collègues dans une série d'articles sur l'estimation statistique pour les fonctions probabilistes des chaînes de Markov. Il est souvent présenté aux côtés de l'algorithme de Viterbi, qui trouve la séquence d'états cachés la plus probable, tandis que l'algorithme avant-arrière calcule les probabilités pour chaque état individuel à chaque pas de temps. L'algorithme fonctionne en deux passes : une passe avant qui calcule la probabilité d'observer la séquence jusqu'à un point donné et de se terminer dans un état particulier, et une passe arrière qui calcule la probabilité d'observer le reste de la séquence étant donné un état de départ. La combinaison de ces deux ensembles de probabilités donne les marginales a posteriori souhaitées.
Formulation mathématique
Considérons un HMM avec des états cachés \( S = \{s_1, s_2, \ldots, s_N\} \), des probabilités de transition \( a_{ij} = P(s_j | s_i) \), des probabilités d'émission \( b_j(o_t) = P(o_t | s_j) \), et une distribution initiale des états \( \pi_i = P(s_i) \). Pour une séquence d'observations \( O = (o_1, o_2, \ldots, o_T) \), la variable avant \( \alpha_t(i) \) est définie comme la probabilité de la séquence d'observations partielle jusqu'au temps \( t \) et d'être dans l'état \( s_i \) au temps \( t \) : \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \), où \( \lambda \) désigne les paramètres du modèle. La passe avant initialise \( \alpha_1(i) = \pi_i b_i(o_1) \) et calcule récursivement \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \).
La variable arrière \( \beta_t(i) \) est définie comme la probabilité de la séquence d'observations du temps \( t+1 \) à \( T \) étant donné que l'état au temps \( t \) est \( s_i \) : \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \). La passe arrière initialise \( \beta_T(i) = 1 \) pour tout \( i \) et calcule récursivement \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \). La probabilité a posteriori d'être dans l'état \( s_i \) au temps \( t \) est alors donnée par \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \).
Applications dans la modélisation de séquences
L'algorithme est largement utilisé pour l'entraînement des HMM via l'algorithme de Baum-Welch, une instance de l'espérance-maximisation. Dans l'étape E, l'algorithme avant-arrière calcule les statistiques suffisantes attendues, telles que le nombre attendu de transitions entre états et le nombre attendu d'émissions de chaque symbole d'observation. Ces statistiques sont ensuite utilisées dans l'étape M pour mettre à jour les paramètres du modèle. Cette procédure itérative converge vers un maximum local de la fonction de vraisemblance.
En reconnaissance vocale, les HMM avec entraînement avant-arrière étaient l'approche dominante pour la modélisation acoustique des années 1970 au début des années 2000, avant d'être largement supplantés par les méthodes de apprentissage profond. En bioinformatique, l'algorithme est utilisé pour la prédiction de gènes et pour l'analyse de séquences protéiques, où les HMM modélisent des motifs conservés. En traitement du langage naturel, il apparaît dans l'étiquetage morpho-syntaxique et dans l'entraînement des modèles séquence à séquence lorsqu'ils sont utilisés avec des couches de sortie structurées.
Relation avec l'apprentissage automatique moderne
Bien que l'algorithme avant-arrière soit une technique classique, ses principes persistent dans le apprentissage automatique moderne. La passe avant est analogue à la propagation de l'information dans les réseaux de neurones récurrents, et la passe arrière ressemble à la rétropropagation des signaux d'erreur, bien que les objectifs mathématiques diffèrent. Dans les réseaux de neurones utilisés pour l'étiquetage de séquences, tels que les LSTM bidirectionnels, les états cachés avant et arrière sont combinés pour capturer le contexte dans les deux directions, reflétant les variables avant et arrière de l'algorithme. De plus, l'utilisation efficace de la programmation dynamique par l'algorithme a inspiré des techniques similaires dans les modèles basés sur transformers, comme l'algorithme avant-arrière utilisé dans certaines formes de prédiction structurée et dans l'entraînement des grands modèles de langage pour des tâches comme la reconnaissance d'entités nommées.
L'algorithme est également lié au concept de recherche en faisceau dans la mesure où les deux gèrent la complexité computationnelle dans les problèmes de séquences, mais ils servent des objectifs différents : la recherche en faisceau approxime la séquence la plus probable, tandis que l'avant-arrière calcule des probabilités marginales exactes. Dans les modèles graphiques probabilistes, l'algorithme avant-arrière est un cas particulier de l'algorithme somme-produit sur un graphe en chaîne, et il se généralise aux modèles en arbre via la propagation de croyances.
Complexité computationnelle et variantes
L'algorithme avant-arrière s'exécute en \( O(T N^2) \) temps et \( O(T N) \) espace, où \( T \) est la longueur de la séquence et \( N \) le nombre d'états cachés. Cette efficacité le rend réalisable pour des séquences de milliers de pas de temps avec des centaines d'états. Pour de grands espaces d'états, des approximations telles que l'algorithme de filtrage avant avec échantillonnage arrière sont utilisées dans le filtrage particulaire et les méthodes de Monte Carlo. Dans les contextes en ligne, l'algorithme avant seul peut être utilisé pour le filtrage, tandis que la passe arrière nécessite la séquence entière, ce qui le rend hors ligne. Les variantes incluent l'algorithme avant-arrière mis à l'échelle pour éviter le sous-dépassement numérique, courant lors du traitement de longues séquences et de petites probabilités.
Voir aussi
- hidden-markov-model
- algorithme de Viterbi
- algorithme de Baum-Welch
- dynamic-programming
- sequence-modeling