158 lines
4.5 KiB
TeX
158 lines
4.5 KiB
TeX
\section{Chapitre 13: L'incertain}
|
|
\label{sec:ch13}
|
|
|
|
\subsection{Probabilités}
|
|
\label{sec:ch13prob}
|
|
|
|
\paragraph{Types de probabilités}
|
|
|
|
\begin{itemize}
|
|
\item \textit{a priori}: avant la perception
|
|
\item \textit{a posteriori}: après la perception
|
|
\item inconditionnelle: en l'absence de tout autre information
|
|
\item conditionnelle: lorsque certaines informations sont disponibles
|
|
\end{itemize}
|
|
|
|
\paragraph{Variables aléatoires}
|
|
|
|
\begin{itemize}
|
|
\item Domaine de valeurs:
|
|
\begin{itemize}
|
|
\item Booléennes (vrai,faux)
|
|
\item Discrètes (valeurs mutuellement exclusives et exhaustives)
|
|
\item Continues (valeurs réelles, souvent un intervalle)
|
|
\end{itemize}
|
|
\item Distribution de probabilités:
|
|
\begin{itemize}
|
|
\item Probabilité pour chacune des assignations possibles
|
|
\item Conjointe: pour toutes les combinaisons de valeurs possibles
|
|
\end{itemize}
|
|
\end{itemize}
|
|
|
|
\paragraph{Règle de Bayes}
|
|
|
|
\begin{align}
|
|
P(a|b)&=\frac{P(a \wedge b)}{P(b)}\\
|
|
P(a \wedge b)&=P(a|b)P(b)\\
|
|
&=P(b|a)P(a)
|
|
\end{align}
|
|
|
|
\paragraph{Axiomes probabilistes}
|
|
|
|
\begin{itemize}
|
|
\item $P(x) \in \left[ 0,1 \right]$
|
|
\item Vrai$\mapsto 1$, Faux$\mapsto 0$
|
|
\item Disjonsction: $P(a \vee b)=P(a)+P(b)-P(a \wedge b)$
|
|
\item Théorème de Finetti: Si les croyances de l'agent 1 ne respecte pas les axiomes, alors il existe une combinaison de paris pour un agent 2 qui fait toujours perdre l'agent 1.
|
|
\end{itemize}
|
|
|
|
\subsection{Inférence}
|
|
\label{sec:ch13inference}
|
|
|
|
\paragraph{Inférence par énumération}
|
|
|
|
\begin{itemize}
|
|
\item Utilise la distribution conjointe
|
|
\item Somme de toutes les probabilités où la proposition est vraie
|
|
\item Lorsqu'on somme pour une variable aléatoire, on obtient une probabilité marginale
|
|
\item Probabilité conditionnelle: en utilisant la Règle de Bayes.
|
|
\end{itemize}
|
|
|
|
\paragraph{Normalisation}
|
|
|
|
Le dénominateur peut être vu comme une constante de normalisation $\alpha$.
|
|
|
|
\begin{align}
|
|
P(A|B)&=\alpha P(A \wedge B)\\
|
|
\alpha&=\frac{1}{P(B)}
|
|
\end{align}
|
|
|
|
Idée générale: Fixer les variables d'évidence $\mathbf{e}$ et effectuer la somme sur les variables cachées (sommation partielle).
|
|
|
|
\begin{align}
|
|
P(Y) &= \sum_{z}P(Y \wedge z)\\
|
|
&= \sum_{z}P(Y|z)P(z)\\
|
|
P(Y|\mathbf{e})&=\alpha P(Y \wedge \mathbf{e})\\
|
|
&= \alpha \sum_{y}P(X \wedge \mathbf{e} \wedge y)
|
|
\end{align}
|
|
|
|
\paragraph{Problèmes de l'inférence par énumération}
|
|
|
|
\begin{itemize}
|
|
\item Complexité en temps et en espace de $O(d^n)$
|
|
\item Difficile de trouver les $d^n$ valeurs de la table
|
|
\item Plutôt une base théorique pour des méthodes d'approximation
|
|
\end{itemize}
|
|
|
|
\subsection{Règle de Bayes}
|
|
\label{sec:ch13bayes}
|
|
|
|
\begin{mydef}
|
|
Deux variables sont indépendantes si $P(X|Y)=P(X)$, $P(Y|X)=P(Y)$ ou $P(X \wedge Y) = P(X)P(Y)$
|
|
\end{mydef}
|
|
|
|
\begin{mydef}
|
|
Règle de Bayes:
|
|
\begin{align}
|
|
P(b|a)&=\frac{P(a|b)P(b)}{P(a)}\\
|
|
P(\mathtt{cause}|\mathtt{effet})&=\frac{P(\mathtt{effet}|\mathtt{cause})P(\mathtt{cause})}{P(\mathtt{effet})}
|
|
\end{align}
|
|
\end{mydef}
|
|
|
|
En appliquant la normalisation:
|
|
|
|
\begin{align}
|
|
\mathbf{P}(Y|X)=\alpha \mathbf{P}(X|Y)\mathbf{P}(Y)
|
|
\end{align}
|
|
|
|
\begin{mydef}
|
|
Deux variables sont conditionnellement indépendantes par rapport à une 3e variable si
|
|
\begin{align}
|
|
\mathbf{P}(X \wedge Y|Z)=\mathbf{P}(X|Z)\mathbf{P}(Y|Z)
|
|
\end{align}
|
|
\end{mydef}
|
|
|
|
Avec l'indépendance conditionnelle, la complexité passe de $O(d^n)$ à $O(n)$.
|
|
|
|
\begin{align}
|
|
P(\mathtt{cause},\mathtt{Effet}_1,\ldots,\mathtt{Effet}_n)&=P(\mathtt{cause})\prod_iP(\mathtt{effet}_i|\mathtt{cause})
|
|
\end{align}
|
|
|
|
C'est un classificateur de Bayes naïf.
|
|
|
|
\paragraph{Jeu du Wumpus}
|
|
|
|
\begin{itemize}
|
|
\item Un trou cause une brise dans les cases adjacentes.
|
|
\item Toutes les cases sauf [1,1] contiennent un trou avec une probabilité de $0.2$.
|
|
\end{itemize}
|
|
|
|
La distribution conjointe complète est
|
|
|
|
\begin{align}
|
|
\mathbf{P}(B_{1,1},B_{1,2},B_{2,1}|P_{1,1},\ldots,P_{4,4})\mathbf{P}(P_{1,1},\ldots,P_{4,4})
|
|
\end{align}
|
|
|
|
Par indépendance, on a
|
|
|
|
\begin{align}
|
|
\mathbf{P}(P_{1,1},\ldots,P_{4,4}) = \prod_{i,j=1,1}^{4,4}\mathbf{P}(P_{i,j})
|
|
\end{align}
|
|
|
|
On veut trouver $P(1,3|\mathtt{known},b)$. Par énumération, on obtient:
|
|
|
|
\begin{align}
|
|
\alpha \sum_{\mathtt{unknown}}\mathbf{P}(P_{1,3},\mathtt{unknown},\mathtt{known},b)
|
|
\end{align}
|
|
La somme contient $2^{12}=4096$ termes. En utilisant les indépendances conditionnelles:
|
|
|
|
\begin{align}
|
|
P(b|P_{1,3},\mathtt{known},\mathtt{unknown})=P(b|P_{1,3},\mathtt{known},\mathtt{fringe})
|
|
\end{align}
|
|
|
|
|
|
|
|
%%% Local Variables:
|
|
%%% mode: latex
|
|
%%% TeX-master: "notes_de_cours"
|
|
%%% End:
|