Cours
* Donner l'implémentation de la méthode d'apprentissage
* Tracer la courbe de l'évolution de la vraisemblance au cours des itérations
Comme dans le TME précédent, proposer une procédure de génération de lettres.
* Donner le code de @@generateHMM@@ qui génère une séquence d'observations (et une séquence d'états) à partir des sommes cumulées des modèles de lettres (cf usage ci-dessous)
* Faire tourner le code suivant qui réalise la génération de n échantillon pour nClred classes de lettres
(:source lang=python:)
# affichage d'une lettre (= vérification bon chargement)
def tracerLettre(let):
a = -let*np.pi/180;
coord = np.array([[0, 0]]);
for i in range(len(a)):
x = np.array([[1, 0]]);
rot = np.array([[np.cos(a[i]), -np.sin(a[i])],[ np.sin(a[i]),np.cos(a[i])]])
xr = x.dot(rot) # application de la rotation
coord = np.vstack((coord,xr+coord[-1,:]))
plt.plot(coord[:,0],coord[:,1])
return
#Trois lettres générées pour 5 classes (A -> E)
n = 3 # nb d'échantillon par classe
nClred = 5 # nb de classes à considérer
fig = plt.figure()
for cl in xrange(nClred):
Pic = models[cl][0].cumsum() # calcul des sommes cumulées pour gagner du temps
Ac = models[cl][1].cumsum(1)
Bc = models[cl][2].cumsum(1)
long = np.floor(np.array([len(x) for x in Xd[itrain[cl]]]).mean()) # longueur de seq. à générer = moyenne des observations
for im in range(n):
s,x = generateHMM(Pic, Ac, Bc, int(long))
intervalle = 360./d # pour passer des états => angles
newa_continu = np.array([i*intervalle for i in x]) # conv int => double
sfig = plt.subplot(nClred,n,im+n*cl+1)
sfig.axes.get_xaxis().set_visible(False)
sfig.axes.get_yaxis().set_visible(False)
tracerLettre(newa_continu)
plt.savefig("lettres_hmm.png")
(:sourceend:)
%width=600px% (Attach:)TME7genLettres.png
!!!%subsection% Génération de lettres
# Initialisation (avec les indices à 0 en python):
# Récursion:
#Terminaison (indices à {$T-1$} en python)
# Chemin
!!!%subsection% Viterbi
Rappels:
* Viterbi sert à estimer la séquence d'états la plus probable étant donnés les observations et le modèle.
* Viterbi peut servir à approximer la probabilité de la séquence d'observation étant donné le modèle.
# Initialisation:
{$$ \myarr{ \delta_{1} (i) &=& \pi_{i} b_{i} (x_{1}) \\ \Psi_{1}(i) &=& 0}$$}
# Récursion:
{$$ \begin{array}{ccccccccc}
\delta_{t} (j) &=&\displaystyle \left[\max_{i} \delta_{t-1}(i) a_{ij}\right] b_{j}(x_{t}) \\
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \delta_{t-1} (i) a_{ij}
\end{array}$$}
#Terminaison
{$$ S^{\star} = max_{i} \delta_{T}(i)$$}
# Chemin
{$$\begin{array}{ccccccccc}
s_{T}^{\star} & = &\displaystyle \arg\max_{i} \delta_{T}(i) \\
s_{t}^{\star} & = & \displaystyle \Psi_{t+1}(s_{t+1}^{\star})
\end{array}$$}
!!!%subsection% Probabilité d'une séquence d'observation
[ 0. 0.76 0.24 0. 0. ]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
[ 0. 0.04 0. 0.13 0.09 0.13 0.02 0.09 0.41 0.09]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
[ 0. 0.76 0.24 0. 0. ]
[ 0. 0. 0.77 0.23 0.]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
[ 0. 0.04 0. 0.13 0.09 0.13 0.02 0.09 0.41 0.09]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
Au niveau de la mise en oeuvre, vous définirez la méthode @@def initGD(X,N):@@ qui prend un ensemble de séquences d'observations et qui retourne l'ensemble des séquences d'états. Pour chaque séquence @@x@@, vous pouvez utiliser:
(:source lang=python:)
np.floor(np.linspace(0,N-.00000001,len(x)))
(:sourceend:)
! TME 7: analyse de données vélib
!!%section% Données vélib
Charger les données vélib [[(Attach:) TME6_velib.pkl.zip | lien]]. Ces données sont zippées pour gagner de la place... Il suffit de les décompresser pour retrouver un pickle.
(:source lang=python:)
# -*- coding: utf-8 -*-
import numpy as np
import pickle as pkl
import matplotlib.pyplot as plt
all = pkl.load(file("velib.pkl", "rb"))
X = all.get('data')
infos = all.get('infos')
(:sourceend:)
Structuration des données dans {$X$}.
Nombre de vélos disponibles dans chaque station, capturé environ toutes les 10 minutes entre le 26 février 2014 (mercredi) et le 4 mars 2014.
* {$X\in \mathbb{R}^{1219,1008}$}:
** Chaque ligne = 1 station (il y a 1219 stations valides cette semaine là en région parisienne)
** 1008 = nombre de mesures sur 1 semaine
* @@infos@@
** 1219 lignes
** 5 colonnes:
*** 0: arrondissement (>20 = banlieue),
*** 1/2:latitude/longitude
*** 3 altitude (google API)
*** 4 taille de la station
!!%section% Problème 1: distinguer les stations par arrondissements
* Même problématique que sur les lettres
Cours.Semaine7TME7 History
Hide minor edits - Show changes to output
Changed lines 187-188 from:
to:
!! %part%Partie optionnelle%%
Deleted line 251:
Changed line 59 from:
%width=600px center% Attach:mmc.png
to:
%center% %width=600px% Attach:mmc.png
Changed line 59 from:
%width=600px% Attach:mmc.png
to:
%width=600px center% Attach:mmc.png
Added lines 3-5:
%define=part apply=block bgcolor=#e6d8c0%
!! %part%Partie obligatoire%%
!! %part%Partie obligatoire%%
Changed line 167 from:
{$$\log\mathcal L^k = \sum_{lettre}\sum_i p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$$}
to:
{$$\log\mathcal L^k = \sum_{lettre}\sum_i \log p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$$}
Changed line 35 from:
On fait l'hypothèse que les états sont connus... Alors que ce n'est pas le cas. Mais il existe des stratégies simples (et parfois efficace) pour attribuer arbitrairement des états sur les chaines.
to:
On fait l'hypothèse que les états sont connus... Alors que ce n'est pas le cas. Mais il existe des stratégies simples (et parfois efficaces) pour attribuer arbitrairement des états sur les chaines.
Changed line 40 from:
* On affecte l'état 0 au début, puis on incrémenté jusqu'à l'état N pour la dernière portion de la chaine
to:
* On affecte l'état 0 au début, puis on incrémente jusqu'à l'état N pour la dernière portion de la chaine
Changed lines 232-233 from:
* est en général plus loin de la solution optimale {$h^\star$},
* mais comme l'espace des hypothèses {$\mathcal H$} est peu étendu, les résultats sont relativement stable.
* mais comme
to:
* est en général plus loin de la solution optimale {$h^\star$} (grand biais),
* mais comme l'espace des hypothèses {$\mathcal H$} est peu étendu, les résultats sont relativement stable (faible variance).
* mais comme l'espace des hypothèses {$\mathcal H$} est peu étendu, les résultats sont relativement stable (faible variance).
Changed lines 237-238 from:
* peut s'approcher plus près de la solution optimale {$h^\star$},
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses {$\mathcal H$} à explorer...
* mais présente un problème de stabilité du fait de
to:
* peut s'approcher plus près de la solution optimale {$h^\star$} (biais faible),
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses {$\mathcal H$} à explorer... (grande variance)
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses {$\mathcal H$} à explorer... (grande variance)
Changed lines 182-184 from:
to:
Comme lors de la semaine précédente, dessiner la matrice de confusion pour détecter les lettres faciles/difficiles à distinguer.
Deleted line 247:
Changed lines 230-231 from:
* est en général plus loin de la solution optimale,
* mais comme l'espace des hypothèses est peu étendu, les résultats sont relativement stable.
*
to:
* est en général plus loin de la solution optimale {$h^\star$},
* mais comme l'espace des hypothèses {$\mathcal H$} est peu étendu, les résultats sont relativement stable.
* mais comme l'espace des hypothèses {$\mathcal H$} est peu étendu, les résultats sont relativement stable.
Changed lines 235-236 from:
* peut s'approcher plus près de la solution optimale,
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses à explorer...
*
to:
* peut s'approcher plus près de la solution optimale {$h^\star$},
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses {$\mathcal H$} à explorer...
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses {$\mathcal H$} à explorer...
Changed lines 239-241 from:
Les solutions de régularisation (comme celle proposée dans l'algorithme de comptage) cherche à optimiser le compromis
to:
Les solutions de régularisation (comme celle proposée dans l'algorithme de comptage) cherche à optimiser le compromis, c'est à dire à isoler une partie de l'espace des hypothèses {$\mathcal H$} particulièrement intéressante:
%width=400px% Attach:TME7_biais3.png
En faisant tourner plusieurs fois les algorithmes de chaines de Markov simples et plusieurs fois les algorithmes de MMC avec différentes valeurs de N et K:
* calculer les moyennes et variances des performances obtenues,
* analyser les résultats par rapport au compromis biais-variance
%width=400px% Attach:TME7_biais3.png
En faisant tourner plusieurs fois les algorithmes de chaines de Markov simples et plusieurs fois les algorithmes de MMC avec différentes valeurs de N et K:
* calculer les moyennes et variances des performances obtenues,
* analyser les résultats par rapport au compromis biais-variance
Changed lines 178-179 from:
* Apprendre les modèles sur les échantillons d'apprentissage, évaluer les performances sur les données de test
to:
* Apprendre les modèles sur les échantillons d'apprentissage.
* Evaluer les performances sur les données de test.
Le code de cette partie est grossièrement identique à la séance passée. Pour plus de détails : [[Cours.Semaine6TME6|semaine 6]]
* Evaluer les performances sur les données de test.
Le code de cette partie est grossièrement identique à la séance passée. Pour plus de détails : [[Cours.Semaine6TME6|semaine 6]]
Changed lines 225-243 from:
!!%section% Dilemme Biais-Variance, reflexion sur la complexité des modèles
to:
!!%section% Dilemme Biais-Variance, reflexion sur la complexité des modèles
Durant ces deux semaines, on a étudié des modèles de complexités croissantes: architecture plus complexe, nombre de paramètres en hausse.
Cela nous amène à discuter le compromis biais-variance.
On considère en général qu'un modèle ''pauvre'':
* est en général plus loin de la solution optimale,
* mais comme l'espace des hypothèses est peu étendu, les résultats sont relativement stable.
%width=400px% Attach:TME7_biais1.png
A l'inverse, un modèle plus ''riche'':
* peut s'approcher plus près de la solution optimale,
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses à explorer...
%width=400px% Attach:TME7_biais2.png
Les solutions de régularisation (comme celle proposée dans l'algorithme de comptage) cherche à optimiser le compromis
Durant ces deux semaines, on a étudié des modèles de complexités croissantes: architecture plus complexe, nombre de paramètres en hausse.
Cela nous amène à discuter le compromis biais-variance.
On considère en général qu'un modèle ''pauvre'':
* est en général plus loin de la solution optimale,
* mais comme l'espace des hypothèses est peu étendu, les résultats sont relativement stable.
%width=400px% Attach:TME7_biais1.png
A l'inverse, un modèle plus ''riche'':
* peut s'approcher plus près de la solution optimale,
* mais présente un problème de stabilité du fait de l'étendue de l'espace d'hypothèses à explorer...
%width=400px% Attach:TME7_biais2.png
Les solutions de régularisation (comme celle proposée dans l'algorithme de comptage) cherche à optimiser le compromis
Changed lines 177-179 from:
* Récupérer la méthode:
# separation app/test, pc=ratio de points en apprentissage
def separeTrainTest(y, pc):
def separeTrainTest(y, pc):
to:
* Récupérer la méthode @@separeTrainTest(y, pc)@@ documentée lors de la séance précédente.
Changed line 220 from:
%width=600px% (Attach:)TME7genLettres.png
to:
%width=600px% Attach:TME7genLettres.png
Added lines 170-173:
* Donner l'implémentation de la méthode d'apprentissage
* Tracer la courbe de l'évolution de la vraisemblance au cours des itérations
Added lines 176-181:
Comme dans la séance précédente, il faut trouver un moyen d'évaluer les performances sans biaiser les résultats... Nous utilisons la même procédure.
* Récupérer la méthode:
# separation app/test, pc=ratio de points en apprentissage
def separeTrainTest(y, pc):
* Apprendre les modèles sur les échantillons d'apprentissage, évaluer les performances sur les données de test
* Récupérer la méthode:
# separation app/test, pc=ratio de points en apprentissage
def separeTrainTest(y, pc):
* Apprendre les modèles sur les échantillons d'apprentissage, évaluer les performances sur les données de test
Added lines 183-222:
Comme dans le TME précédent, proposer une procédure de génération de lettres.
* Donner le code de @@generateHMM@@ qui génère une séquence d'observations (et une séquence d'états) à partir des sommes cumulées des modèles de lettres (cf usage ci-dessous)
* Faire tourner le code suivant qui réalise la génération de n échantillon pour nClred classes de lettres
(:source lang=python:)
# affichage d'une lettre (= vérification bon chargement)
def tracerLettre(let):
a = -let*np.pi/180;
coord = np.array([[0, 0]]);
for i in range(len(a)):
x = np.array([[1, 0]]);
rot = np.array([[np.cos(a[i]), -np.sin(a[i])],[ np.sin(a[i]),np.cos(a[i])]])
xr = x.dot(rot) # application de la rotation
coord = np.vstack((coord,xr+coord[-1,:]))
plt.plot(coord[:,0],coord[:,1])
return
#Trois lettres générées pour 5 classes (A -> E)
n = 3 # nb d'échantillon par classe
nClred = 5 # nb de classes à considérer
fig = plt.figure()
for cl in xrange(nClred):
Pic = models[cl][0].cumsum() # calcul des sommes cumulées pour gagner du temps
Ac = models[cl][1].cumsum(1)
Bc = models[cl][2].cumsum(1)
long = np.floor(np.array([len(x) for x in Xd[itrain[cl]]]).mean()) # longueur de seq. à générer = moyenne des observations
for im in range(n):
s,x = generateHMM(Pic, Ac, Bc, int(long))
intervalle = 360./d # pour passer des états => angles
newa_continu = np.array([i*intervalle for i in x]) # conv int => double
sfig = plt.subplot(nClred,n,im+n*cl+1)
sfig.axes.get_xaxis().set_visible(False)
sfig.axes.get_yaxis().set_visible(False)
tracerLettre(newa_continu)
plt.savefig("lettres_hmm.png")
(:sourceend:)
%width=600px% (Attach:)TME7genLettres.png
Changed lines 165-166 from:
Le critère de convergence sera la vraisemblance:
* achaque itération {$k$} et pour toutes les lettres {$lettre$}, calculer pour l'ensemble des séquences d'observation : {$\log\mathcal L^k = \sum_{lettre}\sum_i p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$}
* a
to:
Le critère de convergence sera la vraisemblance.
* A chaque itération {$k$} et pour toutes les lettres {$lettre$}, calculer pour l'ensemble des séquences d'observation :
{$$\log\mathcal L^k = \sum_{lettre}\sum_i p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$$}
* Lorsque la vraisemblance n'évolue plus (ie {$\frac{\log\mathcal L^k - \log\mathcal L^{k+1}}{\log\mathcal L^k} < 1e-4$}), sortir de la boucle de mise à jour.
* A chaque itération {$k$} et pour toutes les lettres {$lettre$}, calculer pour l'ensemble des séquences d'observation :
{$$\log\mathcal L^k = \sum_{lettre}\sum_i p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$$}
* Lorsque la vraisemblance n'évolue plus (ie {$\frac{\log\mathcal L^k - \log\mathcal L^{k+1}}{\log\mathcal L^k} < 1e-4$}), sortir de la boucle de mise à jour.
Changed lines 92-93 from:
to:
# Xd = angles observés discrétisés
Changed lines 165-166 from:
to:
Le critère de convergence sera la vraisemblance:
* a chaque itération {$k$} et pour toutes les lettres {$lettre$}, calculer pour l'ensemble des séquences d'observation : {$\log\mathcal L^k = \sum_{lettre}\sum_i p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$}
* a chaque itération {$k$} et pour toutes les lettres {$lettre$}, calculer pour l'ensemble des séquences d'observation : {$\log\mathcal L^k = \sum_{lettre}\sum_i p(\mathbf x_i^{lettre} | \lambda_{lettre}^k)$}
Added lines 169-170:
!!!%subsection% Génération de lettres
Changed lines 156-158 from:
En utilisant la procédure de Baum-Welch simplifiée vue en TD et rappelée ci-dessous, proposer un code pour apprendre les modèles
to:
En utilisant la procédure de Baum-Welch simplifiée vue en TD et rappelée ci-dessous, proposer un code pour apprendre les modèles correspondant aux 26 lettres de l'alphabet.
'''Baum-Welch simplifié:'''
# Initialisation des états cachés arbitraire (eg méthode gauche-droite)
# Tant que ''critère de convergence'' non atteint
## Apprentissage des modèles {$\lambda_{lettre}=\{\Pi, A, B\}$}
## Estimation des états cachés par Viterbi
'''Baum-Welch simplifié:'''
# Initialisation des états cachés arbitraire (eg méthode gauche-droite)
# Tant que ''critère de convergence'' non atteint
## Apprentissage des modèles {$\lambda_{lettre}=\{\Pi, A, B\}$}
## Estimation des états cachés par Viterbi
Changed line 168 from:
!!%section% Dilemme Biais-Variance, reflexion sur la complexité des modèles
to:
!!%section% Dilemme Biais-Variance, reflexion sur la complexité des modèles
Added lines 14-19:
import numpy as np
import matplotlib.pyplot as plt
# truc pour un affichage plus convivial des matrices numpy
np.set_printoptions(precision=2, linewidth=320)
plt.close('all')
import matplotlib.pyplot as plt
# truc pour un affichage plus convivial des matrices numpy
np.set_printoptions(precision=2, linewidth=320)
plt.close('all')
Deleted line 161:
Changed lines 84-85 from:
K = 10
N = 5
to:
K = 10 # discrétisation (=10 observations possibles)
N = 5 # 5 états possibles (de 0 à 4 en python)
N = 5 # 5 états possibles (de 0 à 4 en python)
Added lines 84-86:
K = 10
N = 5
N = 5
Changed line 121 from:
{$$ S^{\star} = max_{i} \delta_{T-1}(i)$$}
to:
{$$ S^{\star} = \max_{i} \delta_{T-1}(i)$$}
Changed lines 132-133 from:
%red% validation en utilisant le modèle précédent {$\lambda_A$}:
to:
%red% validation en utilisant le modèle précédent {$\lambda_A$} (mêmes valeurs de N et K):
Changed lines 138-156 from:
!!!%subsection% Probabilité d'une séquence d'observation
to:
!!!%subsection% [OPT] Probabilité d'une séquence d'observation
En fonction de votre vitesse d'avancement, coder la version {$\alpha$} de l'estimation (exacte) des probabilités d'une séquence d'observations.
Comparer avec l'approximation estimée précédemment (le résultat attendu est-il plus ou moins élevé avec la procédure exacte?).
%red% validation
p = calc_log_pobs_v2(Xd[0],Pi, A, B)
p = -34.8950422805
!!!%subsection% Apprentissage complet (Baum-Welch simplifié)
En utilisant la procédure de Baum-Welch simplifiée vue en TD et rappelée ci-dessous, proposer un code pour apprendre les modèles
!!!%subsection% Evaluation des performances
!!%section% Dilemme Biais-Variance, reflexion sur la complexité des modèles
En fonction de votre vitesse d'avancement, coder la version {$\alpha$} de l'estimation (exacte) des probabilités d'une séquence d'observations.
Comparer avec l'approximation estimée précédemment (le résultat attendu est-il plus ou moins élevé avec la procédure exacte?).
%red% validation
p = calc_log_pobs_v2(Xd[0],Pi, A, B)
p = -34.8950422805
!!!%subsection% Apprentissage complet (Baum-Welch simplifié)
En utilisant la procédure de Baum-Welch simplifiée vue en TD et rappelée ci-dessous, proposer un code pour apprendre les modèles
!!!%subsection% Evaluation des performances
!!%section% Dilemme Biais-Variance, reflexion sur la complexité des modèles
Added lines 66-81:
'''Variante stabilisée''': afin d'éviter les transitions à probabilité nulle et de régulariser l'ensemble du système, il est intéressant d'initialiser les matrices de transition à une valeur non nulle. Cette initialisation ''spéciale'' peut être faite de manière optionnelle en utilisant les arguments par défaut de python:
(:source lang=python:)
def learnHMM(allx, allq, N, K, initTo0=False):
if initTo0:
A = np.zeros((N,N))
B = np.zeros((N,K))
Pi = np.zeros(N)
eps = 1e-8
else:
A = np.ones((N,N))*eps
B = np.ones((N,K))*eps
Pi = np.ones(N)*eps
...
(:sourceend:)
(:source lang=python:)
def learnHMM(allx, allq, N, K, initTo0=False):
if initTo0:
A = np.zeros((N,N))
B = np.zeros((N,K))
Pi = np.zeros(N)
eps = 1e-8
else:
A = np.ones((N,N))*eps
B = np.ones((N,K))*eps
Pi = np.ones(N)*eps
...
(:sourceend:)
Changed line 107 from:
to:
1. Initialisation (avec les indices à 0 en python):
Changed line 112 from:
to:
2. Récursion:
Changed line 117 from:
to:
3. Terminaison (indices à {$T-1$} en python)
Changed line 119 from:
to:
4. Chemin
Changed lines 125-127 from:
L'estimation de {$\log p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}.
to:
L'estimation de {$\log p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}.\\
Donner le code de la méthode @@def viterbi(x,Pi,A,B):@@
Donner le code de la méthode @@def viterbi(x,Pi,A,B):@@
Changed lines 84-85 from:
!!!%subsection% Viterbi
to:
!!!%subsection% Viterbi (en log)
Changed lines 98-99 from:
\delta_{t} (j) &=&\displaystyle \left[\max_{i} \log \delta_{t-1}(i) + \log a_{ij}\right] + \log b_{j}(x_{t}) \\
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \log \delta_{t-1} (i) + \log a_{ij}
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]}
to:
\delta_{t} (j) &=&\displaystyle \left[\max_{i} \delta_{t-1}(i) + \log a_{ij}\right] + \log b_{j}(x_{t}) \\
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \delta_{t-1} (i) + \log a_{ij}
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \delta_{t-1} (i) + \log a_{ij}
Changed line 99 from:
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \delta_{t-1} (i) a_{ij}
to:
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \log \delta_{t-1} (i) + \log a_{ij}
Changed line 93 from:
\delta_{0} (i) &=& \pi_{i} b_{i} (x_{1}) \\
to:
\delta_{0} (i) &=& \log \pi_{i} +\log b_{i} (x_{1}) \\
Changed line 98 from:
\delta_{t} (j) &=&\displaystyle \left[\max_{i} \delta_{t-1}(i) a_{ij}\right] b_{j}(x_{t}) \\
to:
\delta_{t} (j) &=&\displaystyle \left[\max_{i} \log \delta_{t-1}(i) + \log a_{ij}\right] + \log b_{j}(x_{t}) \\
Changed lines 109-110 from:
L'estimation de {$p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}.
to:
L'estimation de {$\log p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}.
Changed line 117 from:
!!!%subsection% Probabilité d'une séquence d'observation
to:
!!!%subsection% Probabilité d'une séquence d'observation
Changed line 91 from:
# Initialisation (avec les indices à 0):
to:
# Initialisation (avec les indices à 0 en python):
Changed line 101 from:
#Terminaison (indices à {$T-1$})
to:
#Terminaison (indices à {$T-1$} en python)
Changed line 105 from:
s_{T}^{\star} & = &\displaystyle \arg\max_{i} \delta_{T}(i) \\
to:
s_{T-1}^{\star} & = &\displaystyle \arg\max_{i} \delta_{T-1}(i) \\
Changed lines 109-110 from:
L'estimation de {$p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}
to:
L'estimation de {$p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}.
%red% validation en utilisant le modèle précédent {$\lambda_A$}:
s_est, p_est = viterbi(Xd[0], Pi, A, B)
s_est = [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 2. 2. 2. 2. 2. 3. 3. 3. 3. 4. 4. 4. 4. 4.]
p_est = -38.0935655456
%red% validation en utilisant le modèle précédent {$\lambda_A$}:
s_est, p_est = viterbi(Xd[0], Pi, A, B)
s_est = [ 0. 0. 0. 0. 0. 0. 0. 0. 1. 2. 2. 2. 2. 2. 3. 3. 3. 3. 4. 4. 4. 4. 4.]
p_est = -38.0935655456
Deleted line 117:
Changed line 94 from:
\Psi_{0}(i) &=& -1 \mbox{Note: -1 car non utilisé normalement}
to:
\Psi_{0}(i) &=& -1 \mbox{ Note: -1 car non utilisé normalement}
Changed line 109 from:
to:
L'estimation de {$p(x_0^{T-1} | \lambda)$} est obtenue en cherchant la plus grande probabilité dans la dernière colonne de {$\delta$}
Changed line 91 from:
# Initialisation:
to:
# Initialisation (avec les indices à 0):
Changed lines 93-94 from:
\delta_{1} (i) &=& \pi_{i} b_{i} (x_{1}) \\
\Psi_{1}(i) &=& 0
\Psi_{
to:
\delta_{0} (i) &=& \pi_{i} b_{i} (x_{1}) \\
\Psi_{0}(i) &=& -1 \mbox{Note: -1 car non utilisé normalement}
\Psi_{0}(i) &=& -1 \mbox{Note: -1 car non utilisé normalement}
Changed lines 101-102 from:
#Terminaison
{$$ S^{\star} = max_{i} \delta_{T}(i)$$}
to:
#Terminaison (indices à {$T-1$})
{$$ S^{\star} = max_{i} \delta_{T-1}(i)$$}
{$$ S^{\star} = max_{i} \delta_{T-1}(i)$$}
Changed lines 92-95 from:
{$$ \myarr{
to:
{$$\begin{array}{ccccccccc}
\delta_{1} (i) &=& \pi_{i} b_{i} (x_{1}) \\
\Psi_{1}(i) &=& 0
\end{array}$$}
\delta_{1} (i) &=& \pi_{i} b_{i} (x_{1}) \\
\Psi_{1}(i) &=& 0
\end{array}$$}
Deleted line 111:
Added line 69:
Added line 71:
Added line 77:
Added lines 83-108:
!!!%subsection% Viterbi
Rappels:
* Viterbi sert à estimer la séquence d'états la plus probable étant donnés les observations et le modèle.
* Viterbi peut servir à approximer la probabilité de la séquence d'observation étant donné le modèle.
# Initialisation:
{$$ \myarr{ \delta_{1} (i) &=& \pi_{i} b_{i} (x_{1}) \\ \Psi_{1}(i) &=& 0}$$}
# Récursion:
{$$ \begin{array}{ccccccccc}
\delta_{t} (j) &=&\displaystyle \left[\max_{i} \delta_{t-1}(i) a_{ij}\right] b_{j}(x_{t}) \\
\Psi_{t}(j) &=&\displaystyle \arg\max_{i\in [1,\ N]} \delta_{t-1} (i) a_{ij}
\end{array}$$}
#Terminaison
{$$ S^{\star} = max_{i} \delta_{T}(i)$$}
# Chemin
{$$\begin{array}{ccccccccc}
s_{T}^{\star} & = &\displaystyle \arg\max_{i} \delta_{T}(i) \\
s_{t}^{\star} & = & \displaystyle \Psi_{t+1}(s_{t+1}^{\star})
\end{array}$$}
!!!%subsection% Probabilité d'une séquence d'observation
Changed lines 60-63 from:
to:
Ce qui donne l'algorithme:
# {$b_{ij}$} = comptage des émissions depuis l'état {$s_i$} vers l'observation {$x_j$}
# normalisation des lignes de {$B$}
# {$b_{ij}$} = comptage des émissions depuis l'état {$s_i$} vers l'observation {$x_j$}
# normalisation des lignes de {$B$}
Changed lines 66-67 from:
%red% Validation:
to:
%red% Validation sur les séquences de la classe A:
Changed lines 71-74 from:
to:
[ 0. 0.76 0.24 0. 0. ]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
Changed lines 76-79 from:
to:
[ 0. 0.04 0. 0.13 0.09 0.13 0.02 0.09 0.41 0.09]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
Changed lines 68-71 from:
to:
[ 0. 0.76 0.24 0. 0. ]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
Changed lines 73-76 from:
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
to:
[ 0. 0.04 0. 0.13 0.09 0.13 0.02 0.09 0.41 0.09]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
Added lines 65-76:
Pi, A, B = learnHMM(Xd[Y=='a'],q[Y=='a'],N,K)
Pi=[ 1. 0. 0. 0. 0.]
A=[[ 0.79 0.21 0. 0. 0. ]
[ 0. 0.76 0.24 0. 0. ]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
B=[[ 0.06 0.02 0. 0. 0. 0. 0. 0.04 0.49 0.4 ]
[ 0. 0.04 0. 0.13 0.09 0.13 0.02 0.09 0.41 0.09]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
Pi=[ 1. 0. 0. 0. 0.]
A=[[ 0.79 0.21 0. 0. 0. ]
[ 0. 0.76 0.24 0. 0. ]
[ 0. 0. 0.77 0.23 0. ]
[ 0. 0. 0. 0.76 0.24]
[ 0. 0. 0. 0. 1. ]]
B=[[ 0.06 0.02 0. 0. 0. 0. 0. 0.04 0.49 0.4 ]
[ 0. 0.04 0. 0.13 0.09 0.13 0.02 0.09 0.41 0.09]
[ 0. 0. 0. 0.02 0.12 0.5 0.31 0.04 0. 0. ]
[ 0.07 0. 0. 0. 0. 0. 0.26 0.33 0.2 0.15]
[ 0.73 0.12 0. 0. 0. 0. 0. 0.02 0.02 0.12]]
Added lines 13-20:
(:source lang=python:)
data = pkl.load(file("ressources/lettres.pkl","rb"))
X = np.array(data.get('letters'))
Y = np.array(data.get('labels'))
nCl = 26
(:sourceend:)
data = pkl.load(file("ressources/lettres.pkl","rb"))
X = np.array(data.get('letters'))
Y = np.array(data.get('labels'))
nCl = 26
(:sourceend:)
Added lines 59-64:
* Chaque ligne correspond à une loi d'émission pour un état (ie, chaque ligne somme à 1)
Donner le code de la fonction @@def learnHMM(allX, allS, N, K):@@ qui apprend un modèle à partir d'un ensemble de couples (seq. d'observations, seq. d'états)
%red% Validation:
Donner le code de la fonction @@def learnHMM(allX, allS, N, K):@@ qui apprend un modèle à partir d'un ensemble de couples (seq. d'observations, seq. d'états)
%red% Validation:
Changed lines 45-52 from:
Etant donné la structure d'un MMC:
to:
Etant donné la structure d'un MMC:
* les observations n'influencent pas les états: les matrices {$\Pi, A$} s'obtiennent comme dans un modèle de Markov simple (cf [[Cours.Semaine6TME6|semaine 6]])
* chaque observation ne dépend que de l'état courant
La nature des données nous pousse à considérer des lois de probabilités discrètes quelconques pour les émissions. L'idée est donc de procéder par comptage en définissant la matrice {$B$} comme suit:
* K colonnes (nombre d'observations), N lignes (nombre d'états)
* les observations n'influencent pas les états: les matrices {$\Pi, A$} s'obtiennent comme dans un modèle de Markov simple (cf [[Cours.Semaine6TME6|semaine 6]])
* chaque observation ne dépend que de l'état courant
La nature des données nous pousse à considérer des lois de probabilités discrètes quelconques pour les émissions. L'idée est donc de procéder par comptage en définissant la matrice {$B$} comme suit:
* K colonnes (nombre d'observations), N lignes (nombre d'états)
Changed line 42 from:
%width=600px%%center% Attach:mmc.png
to:
%width=600px% Attach:mmc.png
Changed line 42 from:
%width=600px center% Attach:mmc.png
to:
%width=600px%%center% Attach:mmc.png
Changed line 42 from:
%width=300px% Attach:mmc.png
to:
%width=600px center% Attach:mmc.png
Changed line 42 from:
%center, width=300px% Attach:mmc.png
to:
%width=300px% Attach:mmc.png
Changed line 42 from:
%center% Attach:mmc.png
to:
%center, width=300px% Attach:mmc.png
Changed lines 40-45 from:
!!!! Apprentissage
to:
!!!! Apprentissage
%center% Attach:mmc.png
Etant donné la structure d'un MMC:
%center% Attach:mmc.png
Etant donné la structure d'un MMC:
Added line 23:
Added lines 32-38:
Au niveau de la mise en oeuvre, vous définirez la méthode @@def initGD(X,N):@@ qui prend un ensemble de séquences d'observations et qui retourne l'ensemble des séquences d'états. Pour chaque séquence @@x@@, vous pouvez utiliser:
(:source lang=python:)
np.floor(np.linspace(0,N-.00000001,len(x)))
(:sourceend:)
Changed line 24 from:
* On découpe chaque série d'observations en $N$ portions à peu près égales
to:
* On découpe chaque série d'observations en N portions à peu près égales
Added lines 27-30:
Sur un exemple:
X0 = [ 1. 9. 8. 8. 8. 8. 8. 9. 3. 4. 5. 6. 6. 6. 7. 7. 8. 9. 0. 0. 0. 1. 1.]
S0 = [ 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 2. 2. 2. 2. 2. 3. 3. 3. 3. 3. 3.]
X0 = [ 1. 9. 8. 8. 8. 8. 8. 9. 3. 4. 5. 6. 6. 6. 7. 7. 8. 9. 0. 0. 0. 1. 1.]
S0 = [ 0. 0. 0. 0. 0. 0. 1. 1. 1. 1. 1. 1. 2. 2. 2. 2. 2. 3. 3. 3. 3. 3. 3.]
Added lines 17-28:
!!!%subsection% Apprentissage d'un modèle connaissant les états
!!!! Hypothèse Gauche-Droite
On fait l'hypothèse que les états sont connus... Alors que ce n'est pas le cas. Mais il existe des stratégies simples (et parfois efficace) pour attribuer arbitrairement des états sur les chaines.
La plus classique est l'hypothèse gauche-droite, qui est bien adaptée aux signaux courts et non périodiques:
* On définit le nombre d'états N
* On découpe chaque série d'observations en $N$ portions à peu près égales
* On affecte l'état 0 au début, puis on incrémenté jusqu'à l'état N pour la dernière portion de la chaine
!!!! Apprentissage
!!!! Hypothèse Gauche-Droite
On fait l'hypothèse que les états sont connus... Alors que ce n'est pas le cas. Mais il existe des stratégies simples (et parfois efficace) pour attribuer arbitrairement des états sur les chaines.
La plus classique est l'hypothèse gauche-droite, qui est bien adaptée aux signaux courts et non périodiques:
* On définit le nombre d'états N
* On découpe chaque série d'observations en $N$ portions à peu près égales
* On affecte l'état 0 au début, puis on incrémenté jusqu'à l'état N pour la dernière portion de la chaine
!!!! Apprentissage
Changed lines 11-16 from:
Les mécanismes de discrétisation et de tracé sont donc les mêmes (cf [[Cours.Semaine6TME6|semaine 6]]
to:
Les mécanismes de discrétisation et de tracé sont donc les mêmes (cf [[Cours.Semaine6TME6|semaine 6]])
!!%section% Passage au MMC
Le but de la séance est de mettre en oeuvre un modèle de Markov caché (MMC). Pour cela, nous allons développer les algorithmes vus en TD.
!!%section% Passage au MMC
Le but de la séance est de mettre en oeuvre un modèle de Markov caché (MMC). Pour cela, nous allons développer les algorithmes vus en TD.
Changed lines 5-40 from:
!!%section% Données vélib
Charger les données vélib [[(Attach:) TME6_velib.pkl.zip | lien]]. Ces données sont zippées pour gagner de la place... Il suffit de les décompresser pour retrouver un pickle.
(:source lang=python:)
# -*- coding: utf-8 -*-
import numpy as np
import pickle as pkl
import matplotlib.pyplot as plt
all = pkl.load(file("velib.pkl", "rb"))
X = all.get('data')
infos = all.get('infos')
(:sourceend:)
Structuration des données dans {$X$}.
Nombre de vélos disponibles dans chaque station, capturé environ toutes les 10 minutes entre le 26 février 2014 (mercredi) et le 4 mars 2014.
* {$X\in \mathbb{R}^{1219,1008}$}:
** Chaque ligne = 1 station (il y a 1219 stations valides cette semaine là en région parisienne)
** 1008 = nombre de mesures sur 1 semaine
* @@infos@@
** 1219 lignes
** 5 colonnes:
*** 0: arrondissement (>20 = banlieue),
*** 1/2:latitude/longitude
*** 3 altitude (google API)
*** 4 taille de la station
!!%section% Problème 1: distinguer les stations par arrondissements
* Même problématique que sur les lettres
to:
! TME 7: MMC et reconnaissance de lettres
La base de données est la même que dans la séance précédente:\\
[[(Attach:) TME6_lettres.pkl]]
Les mécanismes de discrétisation et de tracé sont donc les mêmes (cf [[Cours.Semaine6TME6|semaine 6]]
La base de données est la même que dans la séance précédente:\\
[[(Attach:) TME6_lettres.pkl]]
Les mécanismes de discrétisation et de tracé sont donc les mêmes (cf [[Cours.Semaine6TME6|semaine 6]]
Added lines 1-4:
%define=subsection color=purple%
%define=section color=blue%
%define=section color=blue%
Changed lines 8-9 from:
!! Données vélib
to:
!!%section% Données vélib
Deleted line 23:
Changed lines 29-39 from:
to:
* @@infos@@
** 1219 lignes
** 5 colonnes:
*** 0: arrondissement (>20 = banlieue),
*** 1/2:latitude/longitude
*** 3 altitude (google API)
*** 4 taille de la station
!!%section% Problème 1: distinguer les stations par arrondissements
* Même problématique que sur les lettres
** 1219 lignes
** 5 colonnes:
*** 0: arrondissement (>20 = banlieue),
*** 1/2:latitude/longitude
*** 3 altitude (google API)
*** 4 taille de la station
!!%section% Problème 1: distinguer les stations par arrondissements
* Même problématique que sur les lettres
Changed lines 6-8 from:
Charger les données vélib
to:
Charger les données vélib [[(Attach:) TME6_velib.pkl.zip | lien]]. Ces données sont zippées pour gagner de la place... Il suffit de les décompresser pour retrouver un pickle.
(:source lang=python:)
# -*- coding: utf-8 -*-
import numpy as np
import pickle as pkl
import matplotlib.pyplot as plt
all = pkl.load(file("velib.pkl", "rb"))
X = all.get('data')
infos = all.get('infos')
(:sourceend:)
Structuration des données dans {$X$}.
Nombre de vélos disponibles dans chaque station, capturé environ toutes les 10 minutes entre le 26 février 2014 (mercredi) et le 4 mars 2014.
* {$X\in \mathbb{R}^{1219,1008}$}:
** Chaque ligne = 1 station (il y a 1219 stations valides cette semaine là en région parisienne)
** 1008 = nombre de mesures sur 1 semaine
(:source lang=python:)
# -*- coding: utf-8 -*-
import numpy as np
import pickle as pkl
import matplotlib.pyplot as plt
all = pkl.load(file("velib.pkl", "rb"))
X = all.get('data')
infos = all.get('infos')
(:sourceend:)
Structuration des données dans {$X$}.
Nombre de vélos disponibles dans chaque station, capturé environ toutes les 10 minutes entre le 26 février 2014 (mercredi) et le 4 mars 2014.
* {$X\in \mathbb{R}^{1219,1008}$}:
** Chaque ligne = 1 station (il y a 1219 stations valides cette semaine là en région parisienne)
** 1008 = nombre de mesures sur 1 semaine
Added lines 1-8:
! TME 7: analyse de données vélib
!! Données vélib
Charger les données vélib
[[(Attach:) TME6_velib.pkl.zip | lien]]
!! Données vélib
Charger les données vélib
[[(Attach:) TME6_velib.pkl.zip | lien]]