Classification#

Vraisemblance d’un échantillon de variable suivant une loi multinomiale#

Soit \pa{Y_i}_{1 \infegal i \infegal N} un échantillon de variables aléatoires i.i.d. suivant la loi multinomiale \loimultinomiale { \vecteurno{p_1}{p_C}}. On définit \forall k \in \intervalle{1}{C}, \; d_k = \frac{1}{N}
\sum_{i=1}^{N} \indicatrice{Y_i = k}. La vraisemblance de l’échantillon est :

(1)#\begin{eqnarray}
L\pa{\vecteurno{Y_1}{Y_N}, \vecteurno{p_1}{p_C}} &=& \prod_{i=1}^{n} p_{Y_i} \nonumber\\
\ln L\pa{\vecteurno{Y_1}{Y_N}, \vecteurno{p_1}{p_C}} &=& \sum_{i=1}^{n} \ln p_{Y_i}  \nonumber\\
\ln L\pa{\vecteurno{Y_1}{Y_N}, \vecteurno{p_1}{p_C}} &=& \sum_{k=1}^{C} \cro{ \pa{\ln p_k}
                                                                \sum_{i=1}^{N}  \indicatrice{Y_i = k}}  \nonumber\\
\ln L\pa{\vecteurno{Y_1}{Y_N}, \vecteurno{p_1}{p_C}} &=& N \sum_{k=1}^{C} d_k \ln p_k
                \nonumber
\end{eqnarray}

Cette fonction est aussi appelée distance de Kullback-Leiber ([Kullback1951]), elle mesure la distance entre deux distributions de variables aléatoires discrètes. L”estimateur de maximum de vraisemblance (emv) est la solution du problème suivant :

Problème P1 : estimateur du maximum de vraisemblance

Soit un vecteur \vecteur{d_1}{d_N} tel que :

\left\{
\begin{array}{l}
\sum_{k=1}^{N} d_k = 1 \\
\forall k \in \ensemble{1}{N}, \; d_k \supegal 0
\end{array}
\right.

On cherche le vecteur \vecteur{p_1^*}{p_N^*} vérifiant :

\begin{array}{l}
\vecteur{p_1^*}{p_N^*} = \underset{ \vecteur{p_1}{p_C} \in \R^C }{\arg \max}
               \sum_{k=1}^{C} d_k \ln p_k \medskip \\
\quad \text{avec } \left \{
    \begin{array}{l}
    \forall k \in \intervalle{1}{C}, \; p_k \supegal 0 \\
    \text{et } \sum_{k=1}^{C} p_k = 1
    \end{array}
    \right.
\end{array}

Théorème T1 : résolution du problème du maximum de vraisemblance

La solution du problème du maximum de vraisemblance est le vecteur :

\vecteur{p_1^*}{p_N^*} = \vecteur{d_1}{d_N}

Démonstration

Soit un vecteur \vecteur{p_1}{p_N} vérifiant les conditions :

\left\{
\begin{array}{l}
\sum_{k=1}^{N} p_k = 1 \\
\forall k \in \ensemble{1}{N}, \;  p_k \supegal 0
\end{array}
\right.

La fonction x \longrightarrow \ln x est concave, d’où :

\begin{eqnarray*}
\Delta  &=&         \sum_{k=1}^{C} d_k \ln p_k - \sum_{k=1}^{C} d_k \ln d_k \\
        &=&         \sum_{k=1}^{C} d_k \pa{ \ln p_k - \ln d_k } = \sum_{k=1}^{C} d_k \ln \frac{p_k}{d_k} \\
        &\infegal&  \ln \pa{ \sum_{k=1}^{C} d_k \frac{p_k}{d_k} } = \ln \pa { \sum_{k=1}^{C} p_k } = \ln 1 = 0 \\
        &\infegal&  0
\end{eqnarray*}

La distance de KullBack-Leiber compare deux distributions de probabilités entre elles. C’est elle qui va faire le lien entre le problème de classification discret et les réseaux de neurones pour lesquels il faut impérativement une fonction d’erreur dérivable.

Problème de classification pour les réseaux de neurones#

Le problème de classification est un cas particulier de celui qui suit pour lequel il n’est pas nécessaire de connaître la classe d’appartenance de chaque exemple mais seulement les probabilités d’appartenance de cet exemple à chacune des classes.

Soient une variable aléatoire continue X \in \R^p et une variable aléatoire discrète multinomiale Y \in \intervalle{1}{C}, on veut estimer la loi de :

Y|X \sim \loimultinomiale {p_1\pa{W,X},\dots , p_C\pa{W,X}}
\text { avec } W \in \R^M

Le vecteur \vecteur{p_1\pa{W,X}}{p_C\pa{W,X}} est une fonction f de \pa{W,X}W est l’ensemble des M paramètres du modèle. Cette fonction possède p entrées et C sorties. Comme pour le problème de la régression, on cherche les poids W qui correspondent le mieux à l’échantillon :

A = \acc{\left. \pa {X_i,y_i=\pa{\eta_i^k}_{1 \infegal k \infegal C}} \in \R^p \times \cro{0,1}^C
           \text{ tel que } \sum_{k=1}^{c}y_i^k=1 \right| 1 \infegal i \infegal N }

On suppose que les variables \pa{Y_i|X_i}_{1 \infegal i \infegal N} suivent les lois respectives \pa{\loimultinomiale{y_i}}_{1 \infegal i \infegal N} et sont indépendantes entre elles, la vraisemblance du modèle vérifie d’après l’équation (1) :

\begin{eqnarray*}
L_W & \propto & \prod_{i=1}^{N}\prod_{k=1}^{C} \cro{p_k \pa{W,X_i}}^{\pr{Y_i=k}} \\
\ln L_W & \propto & \sum_{i=1}^{N}\sum_{k=1}^{C} \eta_i^k \ln\cro { p_k\pa{W,X_i}}
\end{eqnarray*}

La solution du problème \overset{*}{W} = \underset{W \in \R^l}{\arg \max} \; L_W est celle d’un problème d’optimisation sous contrainte. Afin de contourner ce problème, on définit la fonction f :

\begin{array}{l}
f : \R^M \times \R^p \longrightarrow \R^C \\
\forall \pa{W,x} \in \R^M \times \R^p, \; f\pa{W,x} = \pa{f_1\pa{W,x}}, \dots ,
                f_C\pa{W,x} \vspace{0.5ex}\\
\text{et }\forall i \in \intervalle{1}{N}, \; \forall k \in \intervalle{1}{C}, \;
                            p^k \pa{W,X_i} = \dfrac{e^{f_k\pa{W,X_i}}}
{\sum_{l=1}^{C}e^{f_l\pa{W,X_i}}}
\end{array}

Les contraintes sur \pa{p^k\pa{W,X_i}} sont bien vérifiées :

\begin{array}{l}
\forall i \in \intervalle{1}{N},\; \forall k \in \intervalle{1}{C}, \; p^k\pa{W,X_i} \supegal 0 \\
\forall i \in \intervalle{1}{N},\; \sum_{k=1}^{C} p^k\pa{W,X_i} = 1
\end{array}

On en déduit que :

\begin{eqnarray*}
            \ln L_W & \propto & \sum_{i=1}^{N}\sum_{k=1}^{C} \; \eta_i^k  \cro{ f_k\pa{W,X_i} - \ln
            \cro{\sum_{l=1}^{C}e^{f_l\pa{W,X_i}}}} \\
            \ln L_W & \propto & \sum_{i=1}^{N}\sum_{k=1}^{C} \; \eta_i^k  f_k\pa{W,X_i} -
                              \sum_{i=1}^{N}  \ln \cro{\sum_{l=1}^{C}e^{f_l\pa{W,X_i}}}
                              \underset{=1}{\underbrace{\sum_{k=1}^{C} \eta_i^k}}
            \end{eqnarray*}

D’où :

(2)#\begin{eqnarray}
    \begin{array}[c]{c}
    \ln L_W \propto  \sum_{i=1}^{N} \sum_{k=1}^{C} \eta_i^k  f_k\pa{W,X_i} - \sum_{i=1}^{N}
     \ln \cro{ \sum_{l=1}^{C} e^{f_l\pa{W,X_i} }}
    \end{array} \nonumber
\end{eqnarray}

Ceci mène à la définition du problème de classification suivant :

Problème P2 : classification

Soit A l’échantillon suivant :

A = \acc {\left. \pa {X_i,y_i=\pa{\eta_i^k}_{1 \infegal k \infegal C}} \in
                                        \R^p \times \R^C
                    \text{ tel que } \sum_{k=1}^{c}\eta_i^k=1 \right| 1 \infegal i \infegal N }

y_i^k représente la probabilité que l’élément X_i appartiennent à la classe k : \eta_i^k = \pr{Y_i = k | X_i}

Le classifieur cherché est une fonction f définie par :

\begin{array}{rcl}
f : \R^M \times \R^p &\longrightarrow& \R^C \\
\pa{W,X}    &\longrightarrow&  \vecteur{f_1\pa{W,X}}{f_p\pa{W,X}} \\
\end{array}

Dont le vecteur de poids W^* est égal à :

W^* =   \underset{W}{\arg \max} \;
        \sum_{i=1}^{N} \sum_{k=1}^{C} \eta_i^k  f_k\pa{W,X_i} -
        \sum_{i=1}^{N}  \ln \cro{ \sum_{l=1}^{C} e^{f_l\pa{W,X_i} }}

Réseau de neurones adéquat#

Dans le problème précédent, la maximisation de \overset{*}{W} = \underset{W \in \R^M}{\arg \max} \, L_W aboutit au choix d’une fonction :

X \in \R^p \longrightarrow f(\overset{*}{W},X) \in \R^C

Le réseau de neurones suivant g : \pa{W,X} \in \R^M \times \R^p \longrightarrow \R^C choisi pour modéliser f aura pour sorties :