ift7025-notes-de-cours/chapitre20.tex

\section{Chapitre 20: Apprentissage de modèles probabilistes}
\label{sec:ch20}

\subsection{Apprentissage bayesien}
\label{sec:ch20apprbayesien}

Forme d'apprentissage: mise à jour de la distribution de probabilités de l'espace des hypothèses.

\begin{align}
  P(h_i|\mathbf{d}) &= \underbrace{\alpha P(\mathbf{d} \mid h_i)}_{vraisemblance}\underbrace{P(h_i)}_{a priori}\\
  P(X|\mathbf{d}) &= \sum_iP(X|\mathbf{d},h_i)P(h_i|\mathbf{d})\\
                    &=\sum_iP(X|h_i)P(h_i|\mathbf{d})
\end{align}

\subsection{Apprentissage du maximum a posteriori et de la vraisemblance}
\label{sec:ch20maximumvrai}

Choisir $h_{MAP}$ maximisant $P(h_i|\mathbf{d})$:

\begin{align}
  h_{MAP} &= \argmax_{h_i}P(\mathbf{d}|h_i)P(h_i)\\
          &= \argmax_{h_i} \log P(\mathbf{d}|h_i) + \log P(h_i) 
\end{align}

C'est la base de l'apprentissage à longueur de description minimale. Pour de grand ensembles de données, l'hypothèse à priori n'est pas pertinente. On utilise alors l'apprentissage par maximum de vraisemblance. On choisit $h_{ML}$ qui maximise $P(\mathbf{d}|h_i)$.

\subsection{Apprentissage des réseaux bayesiens}
\label{sec:ch20reseaux}

On cherche une proportion $\theta$ d'éléments dans un ensemble de taille $N$ où $F=1$. L'hypothèse figure parmi un continuum d'hypothèses représenté par une distribution binomiale. On décompte $x$ exemples où $F=1$.

\begin{align}
  P(\mathbf{d}|h_{\theta}) &= \prod_{j=1}^NP(d_j|h_\theta)\\
  &= \theta^x(1-\theta)^{N-x}
\end{align}

Maximiser cette probabilité est plus facile en passant par le logarithme:

\begin{align}
  L(\mathbf{d}|h_{\theta}) &= \log P(\mathbf{d}|h_{\theta})\\
                           &= \sum {j=1}^N \log P(d_j|h_\theta)\\
                           &= x \log \theta + (N-x) \log (1-\theta)\\
  \frac{\partial L(\mathbf{d}|h_{\theta})}{\partial \theta} &= \frac{x}{\theta}-\frac{N-x}{1-\theta} = 0\\
                           \Rightarrow \theta &= \frac{x}{x+N-x} = \frac{x}{N}
\end{align}

Si on ajoute une autre variable $W$ qui dépend de la première variable $F$, on ajoute par exemple les paramètres $\theta_1$ et $\theta_2$ pour $P(W|F=0)$ et $P(W|F=1)$. La vraisemblance devient:
\begin{align}
  P(F=1,W=0|h_{\theta,\theta_1,\theta_2}) &= P(F=1|h_{\theta,\theta_1,\theta_2})P(W=0|F=1,h_{\theta,\theta_1,\theta_2}) \\
  &= \theta (1-\theta_1)
\end{align}

On a N éléments où $x_y$ valent $F=1,W=1$, $x_{\not y}$ valent $F=1,W=0$, $\not x_y$ valent $F=0,W=1$, $\not x_{\not y}$ valent $F=0,W=0$.

\begin{align}
  P(\mathbf{d}|h_{\theta,\theta_1,\theta_2}) &= \theta^x(1-\theta)^{N-x}\theta_1^{x_y}(1-\theta_1)^{\not x_y}\theta_2^{x_{not_y}}(1-\theta_2)^{\not x_{\not y}}\\
  L (\mathbf{d}|h_{\theta,\theta_1,\theta_2}) &= x \log \theta + (N-x) \log (1-\theta)\\
                                             &+ x_y \log \theta_1 + \not x_y \log (1-\theta_1)\\
                                             &+ x_{\not_y} \log \theta_2 + \not x_{\not y} (1-\theta_2)
\end{align}

En utilisant des données complètes, le problème de l'apprentissage par vraisemblance des paramètres pour un réseau bayesien se décompose en un problème séparé pour chaque paramètre.

\subsection{Modèle de Bayes Naif}
\label{sec:ch20bayesnaif}

\begin{itemize}
\item Modèle simple qui fonctionne bien dans de nombreuses situations. 
\item Assume l'indépendance conditionnelle des attributs par rapport à la valeur. 
\item On évalue les probabilités depuis les exemples d'apprentissage, puis on multiplue les probabilités conditionnelles pour chacunes des valeurs de la variable réponse. 
\item On choisit la variable réponse avec le plus grande probabilité. 
\end{itemize}

\begin{align}
  v = \argmax_{v_j \in V}P(v_j)\prod_{i}P(X_i|v_j)
\end{align}

\subsection{Modèles continus}
\label{sec:ch20modelescont}

Hypothèses:

\begin{itemize}
\item Lignes droites avec un bruit gaussien.
\item On choisit les paramètres $\theta = (a,b)$ qui maximisent la vraisemblance.
\item Les exemples dont indépendants et identiquement distribués
\end{itemize}

\begin{align}
  P(d_j|h_i) &= \alpha \exp (-\frac{y_j-(ax_j+b)^2}{2\sigma^2})\\
  L(d_j|h_i) &= -\alpha^{\prime}\sum_j (y_j-(ax_j+b))^2\\
  \frac{\partial L}{\partial a} &= -\alpha^{\prime} \sum_j 2(y_j-(ax_j+b))(-x_j)=0\\
  \frac{\partial L}{\partial b} &= -\alpha^{\prime} \sum_j 2(y_j-(ax_j+b))(-1)=0\\
\end{align}

On résous pour les paramètres $a$ et $b$:

\begin{align}
  a &= \frac{\sum_j x_j \sum_j y_j - N\sum_j x_jy_j}{(\sum_j x_j)^2 - N \sum_j x_j^2}\\
  b &= \frac{1}{N}(\sum_j y_j - a \sum_j x_j)
\end{align}

\subsection{Apprentissage avec variables cachées (EM)}
\label{sec:ch20em}

Les variables cachées peuvent réduire énormément le nombre de paramètres pour spécifier un réseau bayesien. Ce qui réduit d'autant la quantité de données nécessaire pour l'apprentissage de ceux-ci.

\begin{mydef}
  L'algorithme d'\textbf{espérance-maximisation} est une méthode itérative en deux étapes:
  
  \begin{itemize}
  \item Espérance: Calculer l'espérance des valeurs des variables cachées
  \item Maximisation: Trouver de nouvelles valeurs des paramètres qui maximisent la valeur de log-vraisemblance des données, considérant les valeur espérées des valeurs cachées.
  \end{itemize}

  La forme générale s'écrit comme suit ($\mathbf{x}$:observé exemples, $Z$: variables cachées, $\theta$: paramètres du modèle):

  \begin{align}
    \theta^{(i+1)}=\argmax_{\theta}\sum_z P(Z=z|\mathbf{x},\theta^{(i)})L(\mathbf{x},Z=z|\theta)
  \end{align}
\end{mydef}

\subsubsection{Clustering non-supervisé}
\label{sec:ch20emcluster}

\begin{itemize}
\item Objectif: identifier plusieurs catégories dans une collection d'objets. 
\item On utilise un mélange de gaussiennes avec $k$ composantes. 
\item On suppose que les données ont été générées depuis ce mélange $P$.
\item Soit une composante $C \in 1, \ldots, k$, alors le mélange est:
  \begin{align}
    P(\mathbf{x}) = \sum_{i=1}^kP(C=i)P(\mathbf{x}|C=i)
  \end{align}
\item Les paramètres sont:
  \begin{itemize}
  \item $w_i=P(C=i)$, le poids de chaque composante
  \item $\mu_i$, la moyenne de chaque composante
  \item $\Sigma_i$, la matrice de covariance de chaque composante
  \end{itemize}
\end{itemize}

Algorithme:

\begin{itemize}
\item Espérance:
  \begin{align}
    P_{ij} &= P(C=i|\mathbf{x}_j)\\
           &= \alpha P(\mathbf{x}_j|C=i)P(C=i)
  \end{align}
\item Maximisation:
  \begin{align}
    \mu_i &\leftarrow \sum_jp_{ij}\mathbf{x}_j/p_i\\
    \Sigma_i &\leftarrow \sum_j p_{ij}\mathbf{x}_j\mathbf{x}_j^T/p_i\\
    w_i &\leftarrow p_i
  \end{align}
\end{itemize}

\subsubsection{Réseaux bayesiens}
\label{sec:ch20embayes}

On calcule les probabilités espérées depuis les données en utilisant le théorème de Bayes. Il n'y a pas d'apprentissage en tant que tel.

\begin{align}
  \theta_{ijk} \leftarrow \hat{N}(X_i=x_{ij},U_i=u_{ik})/\hat{N}(U_i=u_{ik})
\end{align}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "notes_de_cours"
%%% End: