Listes des définitions et théorèmes¶

Corollaires¶

Corollaire C1 : Estimateur de l’aire sous la courbe ROC

On dispose des scores $\vecteur{Y_1}{Y_n}$ des expériences qui ont réussi et $\vecteur{X_1}{X_m}$ les scores des expériences qui ont échoué. On suppose également que tous les scores sont indépendants. Les scores $(Y_i)$ sont identiquement distribués, il en est de même pour les scores $(X_i)$ . Un estimateur de l’aire $A$ sous la courbe ROC” est :

(1)¶ $\hat{A} = \frac{1}{nm} \; \sum_{i=1}^{m}\sum_{j=1}^{n} \pa{\indicatrice{ Y_j > X_i} + \frac{1}{2} \indicatrice{ Y_j = X_i}}$

entrée originale

Corollaire C1 : approximation d’une fonction créneau

Soit $C \subset \mathbb{R}^p, \; C= \acc { \vecteur{y_1}{y_p} \in \mathbb{R}^p \, | \forall i\in \intervalle{1}{p},\, 0 \leqslant y_{i}\leqslant 1 }$ , alors :

$\begin{array}{l} \forall \varepsilon > 0, \; \forall \alpha>0, \; \exists n \in \N^*, \; \exists \vecteur{x_1}{x_n} \in\left( \mathbb{R}^p\right) ^{n}, \; \exists \vecteur{\gamma_1}{\gamma_n} \in \mathbb{R}^n \text{ tels que } \forall x\in \mathbb{R}^p, \\ \\ \begin{array}{ll} & \left| \underset{i=1}{\overset{n}{\sum}}\dfrac{\gamma_i} {1+e^{\left\langle x_{i},x\right\rangle +b_{i}}}-\indicatrice{x\in C }\right| \leqslant1 \\ \\ \text{ et } & \underset{y\in Fr\left( C\right) }{\inf }\left\| x-y\right\| > \alpha\mathbb{R}ightarrow\left| \underset{i=1}{\overset {n}{\sum}}\dfrac{\gamma_i}{1+e^{\left\langle x_{i},x\right\rangle +b_{i}}} -\indicatrice{x\in C}\right| \leqslant\varepsilon \end{array} \end{array}$

entrée originale

Corollaire C1 : nullité d’un coefficient

Les notations utilisées sont celles du théorème sur loi asymptotique des coefficients. Soit $w_k$ un poids du réseau de neurones d’indice quelconque $k$ . Sa valeur estimée est $\widehat{w_k}$ , sa valeur optimale $w^*_k$ . D’après le théorème :

$N \dfrac{ \pa{\widehat{w_k} - w^*_k}^2 } { \widehat{\sigma_N}^2 \pa{\widehat{\Sigma_N}^{-1}}_{kk} } \; \overset{T \rightarrow + \infty}{\longrightarrow} \; \chi^2_1$

entrée originale

Corollaire C2 : Variance de l’estimateur AUC

On note $P_X = \pr{ X < \min\acc{Y_i,Y_j }}$ et $P_Y = \pr { \max\acc{X_i,X_j} < Y}$ . $X_i$ et $X_j$ sont de même loi que $X$ , $Y_i$ , $Y_j$ sont de même loi que $Y$ . La variance de l’estimateur $\hat{A}$ définie par (1) est :

$\var{\hat{A}} = \frac{ \hat{A} (1-\hat{A})}{nm} \; \cro{ 1 + (n-1) \frac { P_Y - \hat{A}^2 } { \hat{A} (1-\hat{A}) } + (m-1) \frac { P_X - \hat{A}^2 } { \hat{A} (1-\hat{A}) } }$

entrée originale

Corollaire C2 : approximation d’une fonction indicatrice

Soit $C\subset\mathbb{R}^p$ compact, alors :

$\begin{array}{c} \forall\varepsilon>0, \; \forall\alpha>0, \; \exists\left( x_{1},...,x_{n}\right) \in\left( \mathbb{R}^{p}\right)^{n}, \; \exists\left( b_{1},...,b_{n}\right) \in\mathbb{R}^n \text{ tels que } \forall x\in\mathbb{R}^{p},\\ \\ \begin{array}{ll} & \left| \sum_{i=1}^n \dfrac{\gamma_i} {1+e^{\left\langle x_{i},x\right\rangle +b_{i}}}-\indicatrice{x\in C }\right| \leqslant1+2\varepsilon^2\\ \\ \text{ et } & \underset{y\in Fr\left( C\right) }{\inf}\left\| x-y\right\| >\alpha\mathbb{R}ightarrow\left| \sum_{i=1}^n \dfrac{\gamma_i}{1+e^{\left\langle x_{i} ,x\right\rangle +b_{i}}}- \indicatrice{x\in C}\right| \leqslant \varepsilon \end{array} \end{array}$

entrée originale

Corollaire C3 : famille libre de fonctions

Soit $F_{p}$ l’ensemble des fonctions continues de $C\subset\mathbb{R}^{p}\longrightarrow\mathbb{R}$ avec $C$ compact muni de la norme : $\left\| f\right\| =\underset{x\in C}{\sup}\left\| f\left( x\right) \right\|$ Alors l’ensemble $E_{p}$ des fonctions sigmoïdes :

$E_{p} = \acc{ x \longrightarrow 1 - \dfrac{2}{1 + e^{<y,x>+b}} | y \in \mathbb{R}^p \text{ et } b \in \mathbb{R}}$

est une base de $F_{p}$ .

entrée originale

Définitions¶

Définition D1 : B+ tree

Soit $B_n$ un B+ tree, soit $N$ un noeud de $B_n$ , il contient un vecteur $V\pa{N} = \vecteur{x_1}{x_t}$ avec $0 \leqslant t \leqslant n$ et $x_1 < ... < x_t$ . Ce noeud contient aussi exactement $t-1$ noeuds fils notés $\vecteur{N_1}{N_{t-1}}$ . On désigne par $D\pa{N_t}$ l’ensemble des descendants du noeud $N_t$ et $G\pa{N_t} = \acc{ V\pa{M} \sac M \in D\pa{N_t}}$ . Le noeud $N$ vérifie :

$\begin{eqnarray*} && \forall x \in G\pa{N_t}, \; x_{t} \leqslant x < x_{t+1} \\ && \text{avec par convention } x_0 = -\infty \text{ et } x_{t+1} = + \infty \end{eqnarray*}$

entrée originale

Définition D1 : Courbe ROC

On suppose que $Y$ est la variable aléatoire des scores des expériences qui ont réussi. $X$ est celle des scores des expériences qui ont échoué. On suppose également que tous les scores sont indépendants. On note $F_Y$ et $F_X$ les fonctions de répartition de ces variables. $F_Y(s)=\pr{Y \leqslant s}$ et $F_X(s)=\pr{X \leqslant s}$ . On définit en fonction d’un seuil $s \in \mathbb{R}$ :

$R(s) = 1 - F_Y(s) = \pr{Y > s}$
$E(s) = 1 - F_X(s) = \pr{X > s}$

La courbe ROC est le graphe $\pa{E(s),R(s)}$ lorsque $s$ varie dans $\mathbb{R}$ .

entrée originale

Définition D1 : Dynamic Minimum Keystroke

On définit la façon optimale de saisir une requête sachant un système de complétion $S$ comme étant le minimum obtenu :

(1)¶ $\begin{eqnarray*} M'(q, S) &=& \min_{0 \leqslant k < l(q)} \acc{ M'(q[1..k], S) + \min( K(q, k, S), l(q) - k) } \end{eqnarray*}$

entrée originale

Définition D1 : Dynamic Minimum Keystroke arrière

On définit la façon optimale de saisir une requête sachant un système de complétion $S$ comme étant le minimum obtenu :

(1)¶ $\begin{eqnarray*} M'_b(q, S) &=& \min\acc{\begin{array}{l} \min_{0 \leqslant k < l(q)} \acc{ M'_b(q[1..k], S) + \min( K(q, k, S), l(q) - k) } \\ \min_{s \succ q} \acc{ M'_b(s, S) + l(s) - l(q) } \end{array} } \end{eqnarray*}$

entrée originale

Définition D1 : Minimum Keystroke

On définit la façon optimale de saisir une requête sachant un système de complétion $S$ comme étant le minimum obtenu :

(1)¶ $M(q,S) = \min_{0 \leqslant k \leqslant l(q)} k + K(q, k, S)$

La quantité $K(q, k, S)$ représente le nombre de touche vers le bas qu’il faut taper pour obtenir la chaîne $q$ avec le système de complétion $S$ et les $k$ premières lettres de $q$ .

entrée originale

Définition D1 : Régression quantile

On dispose d’un ensemble de n couples $(X_i, Y_i)$ avec $X_i \in \mathbb{R}^d$ et $Y_i \in \mathbb{R}$ . La régression quantile consiste à trouver $\alpha, \beta$ tels que la somme $\sum_i \abs{\alpha + \beta X_i - Y_i}$ est minimale.

entrée originale

Définition D1 : bruit blanc

Une suite de variables aléatoires réelles $\pa{\epsilon_i}_{1 \leqslant i \leqslant N}$ est un bruit blanc :

$\exists \sigma > 0$ , $\forall i \in \intervalle{1}{N}, \; \epsilon_i \sim \loinormale{0}{\sigma}$
$\forall \pa{i,j} \in \intervalle{1}{N}^2, \; i \neq j \Longrightarrow \epsilon_i \independant \epsilon_j$

entrée originale

Définition D1 : loi de Poisson et loi exponentielle

Si une variable $X$ suit une loi de Poisson de paramète $\lambda t$ , elle a pour densité :

$\begin{eqnarray} \pr{X = n} &=& \frac{(\lambda t)^n}{n!} \; e^{-\lambda t} \end{eqnarray}$

Si une variable $X$ suit une loi exponentielle de paramètre $\mu$ , elle a pour densité :

$\begin{eqnarray} f(t) &=& \mu \; e^{- \mu t} \text{ et } \pr {X \leqslant t} = \int_0^t \mu \; e^{- \mu x} dx = 1 - e^{-\mu t} \end{eqnarray}$

entrée originale

Définition D1 : mot

On note $\mathcal{C}$ l’espace des caractères ou des symboles. Un mot ou une séquence est une suite finie de $\mathcal{C}$ . On note $\mathcal{S}_\mathcal{C} = \cup_{k=1}^{\infty} C^k$ l’espace des mots formés de caractères appartenant à $\mathcal{C}$ .

entrée originale

Définition D1 : mélange de lois normales

Soit $X$ une variable aléatoire d’un espace vectoriel de dimension $d$ , $X$ suit un la loi d’un mélange de $N$ lois gaussiennes de paramètres $\pa{\mu_i, \Sigma_i}_ {1 \leqslant i \leqslant N}$ , alors la densité $f$ de $X$ est de la forme :

$\begin{eqnarray} f\pa{x} &=& \sum_{i=1}^{N} \; p_i \; \dfrac{1}{\pa{2 \pi}^{\frac{d}{2}}\sqrt{\det \Sigma_i}} \; exp \pa{-\frac{1}{2} \pa{x-\mu_i}' \Sigma_i^{-1} \pa{x-\mu_i} } \\ \end{eqnarray}$

Avec : $\sum_{i=1}^{N} \; p_i = 1$ .

entrée originale

Définition D1 : neurone

Un neurone à $p$ entrées est une fonction $f : \mathbb{R}^{p+1} \times \mathbb{R}^p \longrightarrow \mathbb{R}$ définie par :

$g : \mathbb{R} \longrightarrow \mathbb{R}$
$W \in \mathbb{R}^{p+1}$ , $W=\pa{w_1,\dots,w_{p+1}}$
$\forall x \in \mathbb{R}^p, \; f\pa{W,x} = g \pa { \sum_{i=1}^{p} w_i x_i + w_{p+1}}$ avec $x = \pa{x_1,\dots,x_p}$

entrée originale

Définition D1 : neurone distance

Un neurone distance à $p$ entrées est une fonction $f : \mathbb{R}^{p+1} \times \mathbb{R}^p \longrightarrow \mathbb{R}$ définie par :

$g : \mathbb{R} \dans \mathbb{R}$
$W \in \mathbb{R}^{p+1}$ , $W=\pa{w_1,\dots,w_{p+1}} = \pa{W',w_{p+1}}$
$\forall x \in \mathbb{R}^p, \; f\pa{W,x} = e^{-\norm{W'-x}^2 + w_{p+1}}$ avec $x = \pa{x_1,\dots,x_p}$

entrée originale

Définition D1 : orthonormalisation de Schmidt

L’orthonormalisation de Shmidt :

Soit $\left( e_{i}\right) _{1\leqslant i\leqslant N}$ une base de $\mathbb{R}^{p}$

On définit la famille $\left( \varepsilon_{i}\right) _{1\leqslant i\leqslant p}$ par :

$\begin{eqnarray*} \varepsilon_{1} &=& \dfrac{e_{1}}{\left\| e_{1}\right\|}\\ \forall i \in \intervalle{1}{p}, \; \varepsilon_{i} &=& \dfrac{e_{i}-\overset{i-1}{\underset{j=1} {\sum}}<e_{i},\varepsilon_{j}>\varepsilon_{j}}{\left\| e_{i}-\overset {i-1}{\underset{j=1}{\sum}}<e_{i},\varepsilon_{j}>\varepsilon_{j}\right\| } \end{eqnarray*}$

entrée originale

Définition D2 : Dynamic Minimum Keystroke modifié

On définit la façon optimale de saisir une requête sachant un système de complétion $S$ comme étant le minimum obtenu :

(2)¶ $\begin{eqnarray*} M"(q, S) &=& \min \left\{ \begin{array}{l} \min_{1 \leqslant k \leqslant l(q)} \acc{ M"(q[1..k-1], S) + 1 +\min( K(q, k, S), l(q) - k) } \\ \min_{0 \leqslant k \leqslant l(q)} \acc{ M"(q[1..k], S) + \delta + \min( K(q, k, S), l(q) - k) } \end{array} \right . \end{eqnarray*}$

entrée originale

Définition D2 : Régression quantile

On dispose d’un ensemble de n couples $(X_i, Y_i)$ avec $X_i \in \mathbb{R}^d$ et $Y_i \in \mathbb{R}$ . La régression quantile consiste à trouver $\alpha, \beta$ tels que la somme $\sum_i p \abs{\alpha + \beta X_i - Y_i}^+ + (1-p) \abs{\alpha + \beta X_i - Y_i}^-$ est minimale.

entrée originale

Définition D2 : couche de neurones

Soit $p$ et $n$ deux entiers naturels, on note $W \in \mathbb{R}^{n\pa{p+1}} = \pa{W_1,\dots,W_n}$ avec $\forall i \in \intervalle{1}{n}, \; W_i \in \mathbb{R}^{p+1}$ . Une couche de $n$ neurones et $p$ entrées est une fonction :

$F : \mathbb{R}^{n\pa{p+1}} \times \mathbb{R}^p \longrightarrow \mathbb{R}^n$

vérfifiant :

$\forall i \in \intervalle {1}{n}, \; f_i$ est un neurone.
$\forall W \in \mathbb{R}^{n\pa{p+1}} \times \mathbb{R}^p, \; F\pa{W,x} = \pa {f_1\pa{W_1,x}, \dots, f_n\pa{W_n,x}}$

entrée originale

Définition D2 : distance d’édition

La distance d’édition $d$ sur $\mathcal{S}_\mathcal{C}$ est définie par :

$\begin{array}{crcl} d : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \mathbb{R}^+\\ & \pa{m_1,m_2} & \longrightarrow & \underset{ \begin{subarray} OO \text{ séquence} \\ \text{d'opérations} \end{subarray}}{ \min} \, d\pa{m_1,m_2,O} \end{array}$

entrée originale

Définition D2 : neurone distance pondérée

Pour un vecteur donné $W \in \mathbb{R}^p = \pa{w_1,\dots,w_p}$ , on note $W_i^j = \pa{w_i,\dots,w_j}$ . Un neurone distance pondérée à $p$ entrées est une fonction $f : \mathbb{R}^{2p+1} \times \mathbb{R}^p \longrightarrow \mathbb{R}$ définie par :

$g : \mathbb{R} \dans \mathbb{R}$
$W \in \mathbb{R}^{2p+1}$ , $W=\pa{w_1,\dots,w_{2p+1}} = \pa{w_1,w_{2p+1}}$
$\forall x \in \mathbb{R}^p, \; f\pa{W,x} = \exp \cro {-\cro{\sum_{i=1}^{p} w_{p+i}\pa{w_i - x_i}^2 } + w_{p+1}}$ avec $x = \pa{x_1,\dots,x_p}$

entrée originale

Définition D2 : taux de classification à erreur fixe

On cherche un taux de reconnaissance pour un taux d’erreur donné. On dispose pour cela d’une courbe ROC obtenue par l’algorithme de la courbe ROC et définie par les points $R_{OC} = \acc{ \pa{e_j,r_j} | 1 \leqslant j \leqslant k}$ . On suppose ici que $\pa{e_1,r_1} = \pa{1,1}$ et $\pa{e_k,r_k} = \pa{0,}$ . Si ce n’est pas le cas, on ajoute ces valeurs à l’ensemble $R_{OC}$ .

Pour un taux d’erreur donné $e^*$ , on cherche $j^*$ tel que :

$e_{j^*+1} \leqslant e^* \leqslant e_{j^*}$

Le taux de reconnaissance $\rho$ cherché est donné par :

$\rho = \frac{e^* - x_{j^*}} { x_{j^*+1} - x_{j^*} } \; \cro{ r_{j^*+1} - r_{j^*} } + r_{j^*}$

entrée originale

Définition D3 : distance entre caractères

Soit $\mathcal{C}' = \mathcal{C} \bigcup \acc{.}$ l’ensemble des caractères ajouté au caractère vide .. On note $c : \pa{\mathcal{C}'}^2 \longrightarrow \mathbb{R}^+$ la fonction coût définie comme suit :

(1)¶ $\begin{eqnarray*} \forall \pa{x,y} \in \pa{\mathcal{C}'}^2, \; c\pa{x,y} \text{ est le coût } \left\{ \begin{array}{ll} \text { d'une comparaison} & \text{si } \pa{x,y} \in \pa{\mathcal{C}}^2\\ \text { d'une insertion} & \text{si } \pa{x,y} \in \pa{\mathcal{C}} \times \acc{.}\\ \text { d'une suppression} & \text{si } \pa{x,y} \in \acc {.} \times \pa{\mathcal{C}} \\ 0 & \text{si } \pa{x,y} = \pa{\acc{.},\acc{.}} \end{array} \right. \end{eqnarray*}$

On note $\mathcal{S}_\mathcal{C'}^2 = \cup_{n=1}^{\infty} \pa{\mathcal{C'}^2}^n$ l’ensemble des suites finies de $\mathcal{C'}$ .

entrée originale

Définition D3 : réseau de neurones multi-couches ou perceptron

Un réseau de neurones multi-couches à $n$ sorties, $p$ entrées et $C$ couches est une liste de couches $\vecteur{C_1}{C_C}$ connectées les unes aux autres de telle sorte que :

$\forall i \in \intervalle {1}{C}$ , chaque couche $C_i$ possède $n_i$ neurones et $p_i$ entrées
$\forall i \in \intervalle{1}{C-1}, \; n_i = p_{i+1}$ , de plus $p_1 = p$ et $n_C = n$

Les coefficients de la couche $C_i$ sont notés $\pa {W_1^i,\dots,W_{n_i}^i}$ , cette couche définit une fonction $F_i$ . Soit la suite $\pa{Z_i}_{0\leqslant i \leqslant C}$ définie par :

$\begin{array}{l} Z_0 \in \mathbb{R}^p \\ \forall i \in \intervalle{1}{C}, \; Z_i = F_i \pa {W_1^i,\dots,W_{n_i}^i,Z_{i-1}}\end{array}$

On pose $M = M = \sum_{i=1}^{C}n_i\pa{p_i+1}$ , le réseau de neurones ainsi défini est une fonction $F$ telle que :

$\begin{array}{lrll} F : & \mathbb{R} ^ M \times \mathbb{R}^p & \longrightarrow & \mathbb{R}^n \\ & \pa{W,Z_0} & \longrightarrow & Z_C \end{array}$

entrée originale

Définition D4 : mot acceptable

Soit $m = \vecteur{m_1}{m_n}$ un mot tel qu’il est défini précédemment. Soit $M=\pa{M_i}_{i \supegal 1}$ une suite infinie de caractères, on dit que $M$ est un mot acceptable pour $m$ si et seulement si la sous-suite extraite de $M$ contenant tous les caractères différents de $\acc{.}$ est égal au mot $m$ . On note $acc\pa{m}$ l’ensemble des mots acceptables pour le mot $m$ .

entrée originale

Définition D5 : distance d’édition

Soit $c$ la distance d’édition, $d$ définie sur $\mathcal{S}_\mathcal{C}$ est définie par :

(2)¶ $\begin{eqnarray} \begin{array}{crcl} d : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \mathbb{R}^+\\ & \pa{m_1,m_2} & \longrightarrow & \min \acc{ \sum_{i=1}^{+\infty} c\pa{M_1^i, M_2^i} | \pa{M_1,M_2} \in acc\pa{m_1} \times acc\pa{m_2}} \end{array} \end{eqnarray}$

entrée originale

Définition D6 : distance d’édition étendue

Soit d^* la distance d’édition définie en 2 pour laquelle les coûts de comparaison, d’insertion et de suppression sont tous égaux à 1. La distance d’édition $d'$ sur $\mathcal{S}_\mathcal{C}$ est définie par :

(6)¶ $\begin{eqnarray*} \begin{array}{crcl} d' : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \mathbb{R}^+\\ & \pa{m_1,m_2} & \longrightarrow & d'\pa{m_1,m_2} = \dfrac{d^*\pa{m_1,m_2}}{ \max \acc {l\pa{m_1}, l\pa{m_2}}} \\ \\ & & & \text{où } l\pa{m} \text{ est la longueur du mot } m \end{array} \end{eqnarray*}$

entrée originale

Définition D7 : distance d’édition tronquée

Soient deux mots $\pa{m_1,m_2}$ , on définit la suite :

$\left( d_{i,j}^{m_{1},m_{2}}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\left( =\left(d_{i,j}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\text{ pour ne pas alourdir les notations}\right)$

Par :

$\left\{ \begin{array}[c]{l}% d_{0,0}=0\\ d_{i,j}=\min\left\{ \begin{array}{lll} d_{i-1,j-1} & + & \text{comparaison} \left( m_1^i,m_2^j\right), \\ d_{i,j-1} & + & \text{insertion} \left( m_2^j\right), \\ d_{i-1,j} & + & \text{suppression} \left( m_1^i\right) \end{array} \right\}% \end{array} \right.$

entrée originale

Définition D8 : distance d’édition tronquée étendue

Soit deux mots $\pa{m_1,m_2}$ , on définit la suite :

$\left( d_{i,j}^{m_{1},m_{2}}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\left( =\left(d_{i,j}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\text{ pour ne pas alourdir les notations}\right)$

par :

$\left\{ \begin{array}[c]{l}% d_{0,0}=0\\ d_{i,j}=\min\left\{ \begin{array}{lll} d_{i-1,j-1} & + & \text{comparaison} \pa{m_1^i,m_2^j}, \\ d_{i,j-1} & + & \text{insertion} \pa{m_2^j,i}, \\ d_{i-1,j} & + & \text{suppression} \pa{m_1^i,j}, \\ d_{i-2,j-2} & + & \text{permutation} \pa{ \pa{m_1^{i-1}, m_1^i},\pa{m_2^{j-1}, m_2^j}} \end{array} \right\}% \end{array} \right.$

entrée originale

Lemmes¶

Lemme L1 : Dynamic Minimum Keystroke

On note $d(q, S)$ la longueur du plus long préfixe de $q$ inclus dans $S$ .

$d(q, S) = \max\acc{ l(p) | p \prec q, \; p \in S, \; p \neq q}$

(1)¶ $\begin{eqnarray*} M'(q, S) &=& \min_{d(q, S) \leqslant k < l(q)} \acc{ M'(q[1..k], S) + \min( K(q, k, S), l(q) - k) } \end{eqnarray*}$

entrée originale

Lemme L1 : M” et sous-ensemble

On suppose que la complétion $q$ est préfixe pour la requête $q'$ et $\sigma(q) < \sigma(q')$ ce qui signifie que la complétion $q$ est toujours affichée avant la complétion $q'$ si elles apparaissent ensemble. Alors $M'(q, S) < M'(q', S)$ . Plus spécifiquement, si on considère l’ensemble $S'(q) = \acc{ s-q \in S | q \prec s }$ ( $s-q$ est la complétion $s$ sans son préfixe $q$ ).

$M'(q', S) = M'(q'-q, S') + M'(q, S)$

entrée originale

Lemme L1 : Rang k

On note $M=(m_{ij})$ , $W^k=(w^k_{il})$ , $H^k=(h^k_{lj})$ avec $1 \leqslant i \leqslant p$ , $1 \leqslant j \leqslant q$ , et $1 \leqslant l \leqslant k$ avec $k < \min(p,q)$ . On suppose que les matrices sont solution du problème d’optimisation $\min_{W,H} \norm{ M - WH }^2$ . On suppose que $rang(M) \supegal k$ . Alors les les matrices $W^k$ et $H^k$ sont de rang $k$ .

entrée originale

Lemme L1 : inertie minimum

Soit $\vecteur{X_1}{X_P} \in \pa{\mathbb{R}^N}^P$ , $P$ points de $\mathbb{R}^N$ , le minimum de la quantité $Q\pa{Y \in \mathbb{R}^N}$ :

$\begin{eqnarray} Q\pa{Y} &=& \sum_{i=1}^P \; d^2\pa{X_i,Y} \end{eqnarray}$

est atteint pour $Y=G=\dfrac{1}{P} \sum_{i=1}^{P} X_i$ le barycentre des points $\vecteur{X_1}{X_P}$ .

entrée originale

Lemme L2 : Projection

On note $M=(m_{ij})$ , $W^k=(w^k_{il})$ , $H^k=(h^k_{lj})$ avec $1 \leqslant i \leqslant p$ , $1 \leqslant j \leqslant q$ , et $1 \leqslant l \leqslant k$ avec $k < \min(p,q)$ . On suppose que les matrices sont solution du problème d’optimisation $\min_{W,H} \norm{ M - WH }^2$ . On considère que la matrice $M$ est un ensemble de $q$ points dans dans un espace vectoriel de dimension $p$ . La matrice $WH$ représente des projections de ces points dans l’espace vectoriel engendré par les $k$ vecteurs colonnes de la matrice $W$ .

entrée originale

Lemme L2 : calcul de *M”(q, S)*

On suppose que $p(q, S)$ est la complétion la plus longue de l’ensemble $S$ qui commence $q$ :

$\begin{eqnarray*} k^* &=& \max\acc{ k | q[[1..k]] \prec q \text{ et } q \in S} \\ p(q, S) &=& q[[1..k^*]] \end{eqnarray*}$

La métrique $M'(q, S)$ vérifie la propriété suivante :

$M'(q, S) = M'(p(q, S), S) + l(q) - l(p(q, S))$

entrée originale

Figures¶

Figure F1 : Gradient conjugué

Wikipedia

Gradient et gradient conjugué sur une ligne de niveau de la fonction $G\pa{x,y} = 3x^2 + y^2$ , le gradient est orthogonal aux lignes de niveaux de la fonction $G$ , mais cette direction est rarement la bonne à moins que le point $\pa{x,y}$ se situe sur un des axes des ellipses, le gradient conjugué agrège les derniers déplacements et propose une direction de recherche plus plausible pour le minimum de la fonction. Voir Conjugate Gradient Method.

entrée originale

Figure F1 : Modèle optimal pour la base de test

_images/errapptest.png

entrée originale

Figure F1 : Principe de la compression par un réseau diabolo

$\begin{picture}(241,100)(0,-10) \put(1,1) {\framebox(40,22){\footnotesize \begin{tabular}{c}vecteur \\ $X \in \mathbb{R}^N$ \end{tabular}}} \put(85,-9) {\framebox(45,32){\footnotesize \begin{tabular}{c}vecteur \\ $Y \in \mathbb{R}^M$ \\ et $M < N$ \end{tabular}}} \put(200,1) {\framebox(40,22){\footnotesize \begin{tabular}{c}vecteur \\ $Z \approx X$ \end{tabular}}} \put(20,40) {\framebox(90,45){\footnotesize \begin{minipage}{30mm} première couche du réseau diabolo~: \textbf{projection (ou compression)} \end{minipage}}} \put(120,40) {\framebox(90,45){\footnotesize \begin{minipage}{30mm} seconde couche du réseau diabolo~: \textbf{reconstitution (ou décompression)} \end{minipage}}} \put(30,23) {\vector(1,1){17}} \put(130,23) {\vector(1,1){17}} \put(90,39) {\vector(1,-1){17}} \put(190,39) {\vector(1,-1){17}} \end{picture}$

entrée originale

Figure F1 : Réseau de neurones adéquat pour la classification

_images/rn_clad.png

entrée originale

Figure F1 : neurone graphique

$\begin{picture}(100,80)(0,0) \put(10,0) {\circle{20}} \put(10,25) {\circle{20}} \put(10,50) {\circle{20}} \put(10,0) {\makebox(3,3){$x_1$}} \put(10,25) {\makebox(3,3){$x_i$}} \put(10,50) {\makebox(3,3){$x_p$}} \put(80,25) {\circle{35}} \put(78,25) {\makebox(6,3){$\;y \overset{f}{\rightarrow} z$}} \put(20,25) {\line(1,0){43}} \drawline(20,0)(63,25) \drawline(20,50)(63,25) \put(30,50) {\makebox(3,3){$w_p$}} \put(30,18) {\makebox(3,3){$w_i$}} \put(30,-2) {\makebox(3,3){$w_1$}} \put(48,20) {\makebox(3,3){$\sum$}} \put(50,-20) {\circle{20}} \put(50,-20) {\makebox(3,3){$1$}} \drawline(50,-10)(63,25) \put(50,5) {\makebox(3,3){$b$}} \end{picture}$

Le vecteur $\left( x_1,...,x_p\right) \in \mathbb{R}^p$ joue le rôle des entrées. $y$ est appelé parfois le potentiel. $y=\sum_{i=1}^{p} w_ix_i+b$ . $z$ est appelée la sortie du neurone. $f$ est appelée la fonction de transfert ou de seuil. $z=f \pa{y} = f \pa { \sum_{i=1}^{p} w_ix_i+b }$ .

entrée originale

Figure F2 : Exemple de minimal locaux

_images/errminloc.png

entrée originale

Figure F2 : Modèle du perceptron multi-couche (multi-layer perceptron, MLP)

_images/rn_gradient.png

$\vecteur{x_1}{x_p}$ : entrées
$C_i$ nombre de neurones sur la couche $i$ , $C_0 = p$
$z_{c,i}$ sortie du neurone $i$ , de la couche $c$ , par extension, $z_{0,i} = x_i$
$y_{c,i}$ potentiel du neurone $i$ de la couche $c$
$w_{c,i,j}$ coefficient associé à l’entrée $j$ du neurone $i$ de la couche $c$ ,
$b_{c,i}$ biais du neurone $i$ de la couche $c$
$f_{c,i}$ fonction de seuil du neurone $i$ de la couche $c$

entrée originale

Figure F2 : Réseau de neurones pour lequel la sélection de connexions s’applique

_images/selection_connexion.png

entrée originale

Figure F2 : Réseau diabolo : réduction d’une dimension

$\begin{picture}(130,75)(0,0) \put(20,10) {\circle{20}} \put(20,40) {\circle{20}} \put(20,70) {\circle{20}} \put(18,8) {\makebox(5,5){\footnotesize $x_1$}} \put(18,38) {\makebox(5,5){\footnotesize $x_2$}} \put(18,68) {\makebox(5,5){\footnotesize $x_3$}} \put(65,25) {\circle{20}} \put(65,55) {\circle{20}} \put(63,23) {\makebox(5,5){\footnotesize $z_{1,1}$}} \put(63,53) {\makebox(5,5){\footnotesize $z_{1,2}$}} \put(110,10) {\circle{20}} \put(110,40) {\circle{20}} \put(110,70) {\circle{20}} \put(108,8) {\makebox(5,5){\footnotesize $z_{2,1}$}} \put(108,38) {\makebox(5,5){\footnotesize $z_{2,2}$}} \put(108,68) {\makebox(5,5){\footnotesize $z_{2,3}$}} \drawline(30,10)(55,25) \drawline(30,40)(55,55) \drawline(30,10)(55,55) \drawline(30,70)(55,25) \drawline(30,70)(55,55) \drawline(30,40)(55,25) \drawline(75,25)(100,10) \drawline(75,25)(100,40) \drawline(75,25)(100,70) \drawline(75,55)(100,10) \drawline(75,55)(100,40) \drawline(75,55)(100,70) \end{picture}$

Ce réseau possède 3 entrées et 3 sorties Minimiser l’erreur $\sum_{k=1}^N E\left( X_{k},X_{k}\right)$ revient à compresser un vecteur de dimension 3 en un vecteur de dimension 2. Les coefficients de la première couche du réseau de neurones permettent de compresser les données. Les coefficients de la seconde couche permettent de les décompresser.

entrée originale

Figure F3 : Courbe d’inertie pour l’ACP

_images/acp_inertie.png

Courbe d’inertie : point d’inflexion pour $d=4$ , l’expérience montre que généralement, seules les projections sur un ou plusieurs des quatre premiers vecteurs propres reflètera l’information contenue par le nuage de points.

entrée originale

Problèmes¶

Problème P1 : Classification

Soit une variable aléatoire $X$ et une variable aléatoire discrète $Y \in \N$ , l’objectif est d’approximer la fonction $\esp\pa{Y | X} = f\pa{X}$ . Les données du problème sont un échantillon de points : $\acc { \pa{ X_{i},Y_{i} } | 1 \leqslant i \leqslant N }$ avec $\forall i \in \ensemble{1}{N}, \; Y_i \in \ensemble{1}{C}$ et un modèle paramétré avec $\theta$ :

$\forall i \in \intervalle{1}{N}, \; \forall c \in \intervalle{1}{C}, \; \pr { Y_i = c | X_i, \theta} = h \pa{\theta,X_i,c }$

avec $n \in \N$ , $h$ est une fonction de paramètre $\theta$ à valeur dans $\cro{0,1}$ et vérifiant la contrainte : $\sum_{c=1}^C h(\theta,X,c) = 1$ .

entrée originale

Problème P1 : Factorisation de matrices positifs

Soit $M \in \mathcal{M}_{pq}$ , on cherche les matrices à coefficients positifs $W \in \mathcal{M}_{pk}$ et $H \in \mathcal{M}_{kq}$ qui sont solution du problème d’optimisation :

$\min_{W,H}\acc{\norme{M-WH}^2} = \min_{W,H} \sum_{ij} (m_{ij} - \sum_k w_{ik} h_{kj})^2$

entrée originale

Problème P1 : Optimiser un système de complétion

On suppose que l’ensemble des complétions $C=\acc{c_j}$ est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions $S=(s_i)$ qu’on considère comme une permutation $\sigma$ de l’ensemble de départ : $S(\sigma) = (s_i) = (c_{\sigma(j)})$ . Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes $Q=(q_i, w_i)_{1 \leqslant i \leqslant N_Q}$ . $q_i$ est la requête, $w_i$ est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :

$E(C, Q, \sigma) = \sum_{i=1}^{N_Q} w_i M'(q_i, S(\sigma))$

Déterminer le meilleur système de complétion revient à trouver la permutation $\sigma$ qui minimise $E(C, Q, \sigma)$ .

entrée originale

Problème P1 : Régression

Soient deux variables aléatoires $X$ et $Y$ , l’objectif est d’approximer la fonction $\esp\pa{Y | X} = f\pa{X}$ . Les données du problème sont un échantillon de points $\acc{ \pa{ X_{i},Y_{i} } | 1 \leqslant i \leqslant N }$ et un modèle paramétré avec :math:theta` :

$\forall i \in \intervalle{1}{N}, \; Y_{i} = f \pa{\theta,X_{i}} + \epsilon_{i}$

avec $n \in \N$ , $\pa{\epsilon_{i}}_{1 \leqslant i \leqslant N}$ bruit blanc, $f$ est une fonction de paramètre $\theta$ .

entrée originale

Problème P1 : analyse en composantes principales (ACP)

Soit $\pa{X_i}_{1 \leqslant i \leqslant N}$ avec $\forall i \in \ensemble{1}{N}, \; X_i \in \mathbb{R}^p$ . Soit $W \in M_{p,d}\pa{\mathbb{R}}$ , $W = \vecteur{C_1}{C_d}$ où les vecteurs $\pa{C_i}$ sont les colonnes de $W$ et $d < p$ . On suppose également que les $\pa{C_i}$ forment une base othonormée. Par conséquent :

$W'W = I_d$

$\pa{W'X_i}_{1 \leqslant i \leqslant N}$ est l’ensemble des vecteurs $\pa{X_i}$ projetés sur le sous-espace vectoriel engendré par les vecteurs $\pa{C_i}$ . Réaliser une analyse en composantes principales, c’est trouver le meilleur plan de projection pour les vecteurs $\pa{X_i}$ , celui qui maximise l’inertie de ce nuage de points, c’est donc trouver $W^*$ tel que :

(1)¶ $\begin{eqnarray*} W^* &=& \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; E\pa{W} = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; \cro { \sum_{i=1}^{N} \norm{W'X_i}^2 } \end{eqnarray*}$

Le terme $E\pa{W}$ est l’inertie du nuage de points $\pa{X_i}$ projeté sur le sous-espace vectoriel défini par les vecteurs colonnes de la matrice $W$ .

entrée originale

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 \mathbb{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}$

entrée originale

Problème P2 : Optimiser un système de complétion filtré

On suppose que l’ensemble des complétions $C=\acc{c_j}$ est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions $S=(s_i)$ qu’on considère comme une permutation $\sigma$ de l’ensemble de départ : $S(\sigma) = (s_i) = (c_{\sigma(j)})$ . On utilise aussi une fonction $f$ qui filtre les suggestions montrées à l’utilisateur, elle ne change pas l’ordre mais peut cacher certaines suggestions si elles ne sont pas pertinentes. Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes $Q=(q_i, w_i)_{1 \leqslant i \leqslant N_Q}$ . $q_i$ est la requête, $w_i$ est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :

$E(C, Q, \sigma, f) = \sum_{i=1}^{N_Q} w_i M'(q_i, S(\sigma), f)$

Déterminer le meilleur système de complétion revient à trouver la permutation $\sigma$ qui minimise $E(C, Q, \sigma, f)$ .

entrée originale

Problème P2 : Prédiction

Soit $M \in \mathcal{M}_{pq}$ et $H \in \mathcal{M}_{kq}$ , on cherche les matrices à coefficients positifs $W \in \mathcal{M}_{pk}$ qui sont solution du problème d’optimisation :

$\min_{W}\acc{\norme{M-WH}^2} = \min_{W,H} \sum_{ij} (m_{ij} - \sum_k w_{ik} h_{kj})^2$

entrée originale

Problème P2 : classification

Soit $A$ l’échantillon suivant :

$A = \acc {\left. \pa {X_i,y_i=\pa{\eta_i^k}_{1 \leqslant k \leqslant C}} \in \mathbb{R}^p \times \mathbb{R}^C \text{ tel que } \sum_{k=1}^{c}\eta_i^k=1 \right| 1 \leqslant i \leqslant 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 : \mathbb{R}^M \times \mathbb{R}^p &\longrightarrow& \mathbb{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} }}$

entrée originale

Propriétés¶

Problème P1 : Classification

Soit une variable aléatoire $X$ et une variable aléatoire discrète $Y \in \N$ , l’objectif est d’approximer la fonction $\esp\pa{Y | X} = f\pa{X}$ . Les données du problème sont un échantillon de points : $\acc { \pa{ X_{i},Y_{i} } | 1 \leqslant i \leqslant N }$ avec $\forall i \in \ensemble{1}{N}, \; Y_i \in \ensemble{1}{C}$ et un modèle paramétré avec $\theta$ :

$\forall i \in \intervalle{1}{N}, \; \forall c \in \intervalle{1}{C}, \; \pr { Y_i = c | X_i, \theta} = h \pa{\theta,X_i,c }$

avec $n \in \N$ , $h$ est une fonction de paramètre $\theta$ à valeur dans $\cro{0,1}$ et vérifiant la contrainte : $\sum_{c=1}^C h(\theta,X,c) = 1$ .

entrée originale

Problème P1 : Factorisation de matrices positifs

Soit $M \in \mathcal{M}_{pq}$ , on cherche les matrices à coefficients positifs $W \in \mathcal{M}_{pk}$ et $H \in \mathcal{M}_{kq}$ qui sont solution du problème d’optimisation :

$\min_{W,H}\acc{\norme{M-WH}^2} = \min_{W,H} \sum_{ij} (m_{ij} - \sum_k w_{ik} h_{kj})^2$

entrée originale

Problème P1 : Optimiser un système de complétion

On suppose que l’ensemble des complétions $C=\acc{c_j}$ est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions $S=(s_i)$ qu’on considère comme une permutation $\sigma$ de l’ensemble de départ : $S(\sigma) = (s_i) = (c_{\sigma(j)})$ . Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes $Q=(q_i, w_i)_{1 \leqslant i \leqslant N_Q}$ . $q_i$ est la requête, $w_i$ est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :

$E(C, Q, \sigma) = \sum_{i=1}^{N_Q} w_i M'(q_i, S(\sigma))$

Déterminer le meilleur système de complétion revient à trouver la permutation $\sigma$ qui minimise $E(C, Q, \sigma)$ .

entrée originale

Problème P1 : Régression

Soient deux variables aléatoires $X$ et $Y$ , l’objectif est d’approximer la fonction $\esp\pa{Y | X} = f\pa{X}$ . Les données du problème sont un échantillon de points $\acc{ \pa{ X_{i},Y_{i} } | 1 \leqslant i \leqslant N }$ et un modèle paramétré avec :math:theta` :

$\forall i \in \intervalle{1}{N}, \; Y_{i} = f \pa{\theta,X_{i}} + \epsilon_{i}$

avec $n \in \N$ , $\pa{\epsilon_{i}}_{1 \leqslant i \leqslant N}$ bruit blanc, $f$ est une fonction de paramètre $\theta$ .

entrée originale

Problème P1 : analyse en composantes principales (ACP)

Soit $\pa{X_i}_{1 \leqslant i \leqslant N}$ avec $\forall i \in \ensemble{1}{N}, \; X_i \in \mathbb{R}^p$ . Soit $W \in M_{p,d}\pa{\mathbb{R}}$ , $W = \vecteur{C_1}{C_d}$ où les vecteurs $\pa{C_i}$ sont les colonnes de $W$ et $d < p$ . On suppose également que les $\pa{C_i}$ forment une base othonormée. Par conséquent :

$W'W = I_d$

$\pa{W'X_i}_{1 \leqslant i \leqslant N}$ est l’ensemble des vecteurs $\pa{X_i}$ projetés sur le sous-espace vectoriel engendré par les vecteurs $\pa{C_i}$ . Réaliser une analyse en composantes principales, c’est trouver le meilleur plan de projection pour les vecteurs $\pa{X_i}$ , celui qui maximise l’inertie de ce nuage de points, c’est donc trouver $W^*$ tel que :

(1)¶ $\begin{eqnarray*} W^* &=& \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; E\pa{W} = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; \cro { \sum_{i=1}^{N} \norm{W'X_i}^2 } \end{eqnarray*}$

Le terme $E\pa{W}$ est l’inertie du nuage de points $\pa{X_i}$ projeté sur le sous-espace vectoriel défini par les vecteurs colonnes de la matrice $W$ .

entrée originale

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 \mathbb{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}$

entrée originale

Problème P2 : Optimiser un système de complétion filtré

On suppose que l’ensemble des complétions $C=\acc{c_j}$ est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions $S=(s_i)$ qu’on considère comme une permutation $\sigma$ de l’ensemble de départ : $S(\sigma) = (s_i) = (c_{\sigma(j)})$ . On utilise aussi une fonction $f$ qui filtre les suggestions montrées à l’utilisateur, elle ne change pas l’ordre mais peut cacher certaines suggestions si elles ne sont pas pertinentes. Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes $Q=(q_i, w_i)_{1 \leqslant i \leqslant N_Q}$ . $q_i$ est la requête, $w_i$ est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :

$E(C, Q, \sigma, f) = \sum_{i=1}^{N_Q} w_i M'(q_i, S(\sigma), f)$

Déterminer le meilleur système de complétion revient à trouver la permutation $\sigma$ qui minimise $E(C, Q, \sigma, f)$ .

entrée originale

Problème P2 : Prédiction

Soit $M \in \mathcal{M}_{pq}$ et $H \in \mathcal{M}_{kq}$ , on cherche les matrices à coefficients positifs $W \in \mathcal{M}_{pk}$ qui sont solution du problème d’optimisation :

$\min_{W}\acc{\norme{M-WH}^2} = \min_{W,H} \sum_{ij} (m_{ij} - \sum_k w_{ik} h_{kj})^2$

entrée originale

Problème P2 : classification

Soit $A$ l’échantillon suivant :

$A = \acc {\left. \pa {X_i,y_i=\pa{\eta_i^k}_{1 \leqslant k \leqslant C}} \in \mathbb{R}^p \times \mathbb{R}^C \text{ tel que } \sum_{k=1}^{c}\eta_i^k=1 \right| 1 \leqslant i \leqslant 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 : \mathbb{R}^M \times \mathbb{R}^p &\longrightarrow& \mathbb{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} }}$

entrée originale

Tables¶

Théorèmes¶

Théorème T1 : Aire sous la courbe (AUC)

On utilise les notations de la définition de la Courbe ROC. L’aire sous la courbe ROC est égale à $\pr{ Y > X}$ .

entrée originale

Théorème T1 : La factorisation de matrice est équivalente à une analyse en composantes principales

On note $M=(m_{ij})$ , $W^k=(w^k_{il})$ , $H^k=(h^k_{lj})$ avec $1 \leqslant i \leqslant p$ , $1 \leqslant j \leqslant q$ , et $1 \leqslant l \leqslant k$ avec $k < \min(p,q)$ . On suppose que les matrices sont solution du problème d’optimisation $\min_{W,H} \norm{ M - WH }^2$ . On considère que la matrice $M$ est un ensemble de $q$ points dans dans un espace vectoriel de dimension $p$ . On suppose $p < q$ . La matrice $W_k$ définit un hyperplan identique à celui défini par les $k$ vecteurs propres associés aux $k$ plus grande valeurs propres de la matrice $MM'$ où $M'$ est la transposée de $M$ .

entrée originale

Théorème T1 : M”, ordre et sous-ensemble

Soit $q$ une requête de l’ensemble de complétion $S$ ordonnées selon $sigma$ . Si cet ordre vérifie :

(1)¶ $\forall k, \; \sigma(q[1..k]) \leqslant \sigma(q[1..k+1])$

On note l’ensemble $S'(q[1..k]) = \acc{ q[k+1..len(q)] \in S }$ :

alors :

$\forall k, \; M'(q[1..k], S) = M'(q[k+1..l(q)], S'(q[1..k]) + M'(q[1..k], S)$

entrée originale

Théorème T1 : Régression linéaire après Gram-Schmidt

Soit une matrice $X \in \mathcal{M}_{nd}$ avec $n \supegal d$ . Et un vecteur $y \in \mathbb{R}^n$ . D’après l”algorithme de Gram-Schmidt, il existe deux matrices telles que $X P = T$ ou $P' X' = T'$ . $P \in \mathcal{M}_{dd}$ et $T \in \mathcal{M}_{nd}$ . La matrice T est triangulaire supérieure et vérifie $T'T = I_d$ ( $I_d$ est la matrice identité). Alors $\beta = T' y P' = P' X' y P' = (X'X)^{-1}X'y$ . $\beta$ est la solution du problème d’optimisation $\min_\beta \norme{y - X\beta}^2$ .

entrée originale

Théorème T1 : [Farago1993]_ 1

Les notations sont celles de l’algorithme précédent. Il retourne le plus proche voisin $x^*$ de $x$ inclus dans $E$ . Autrement dit, $\forall x \in X, \; x^* \in F\pa{x}$ .

entrée originale

Théorème T1 : convergence de la méthode de Newton

Soit une fonction continue $g : W \in \mathbb{R}^M \dans \mathbb{R}$ de classe $C^{1}$ . On suppose les hypothèses suivantes vérifiées :

H1 : $\underset{W\in \mathbb{R}^q}{\arg\min} \; g\left( W\right) =\left\{ W^{\ast}\right\}$ est un singleton
H2 : $\forall\varepsilon>0, \; \underset{\left| W-W^{\ast}\right| >\varepsilon}{\inf}\left[ \left( W-W^{\ast}\right) ^{\prime}.\nabla g\left( W\right) \right] >0$
H3 : $\exists\left( A,B\right) \in \mathbb{R}^2$ tels que $\forall W\in\mathbb{R}^p,\; \left\| \nabla g\left( W\right) \right\| ^{2}\leqslant A^{2}+B^{2}\left\| W-W^{\ast}\right\| ^{2}$
H4 : la suite $\left( \varepsilon_{t}\right)_{t\geqslant0}$ vérifie, $\forall t>0, \; \varepsilon_{t}\in \mathbb{R}_{+}^{\ast}$ et $\sum_{t\geqslant 0}\varepsilon_{t}=+\infty$ , $\sum_{t\geqslant 0}\varepsilon_{t}^{2}<+\infty$

Alors la suite $\left( W_{t}\right) _{t\geqslant 0}$ construite de la manière suivante $W_{0} \in \mathbb{R}^M$ , $\forall t\geqslant0$ : $W_{t+1}=W_{t}-\varepsilon_{t}\,\nabla g\left( W_{t}\right)$ vérifie $\lim_{ t \dans+\infty}W_{t}=W^{\ast}$ .

entrée originale

Théorème T1 : convergence des k-means

Quelque soit l’initialisation choisie, la suite $\pa{I_t}_{t\supegal 0}$ construite par l’algorithme des k-means converge.

entrée originale

Théorème T1 : convexité des classes formées par une régression logistique

On définit l’application $\mathbb{R}^d \rightarrow \mathbb{N}$ qui associe la plus grande coordonnée $f(X) = \arg \max_k (AX + B)_k$ . A est une matrice $\mathcal{M}_{dc}$ , B est un vecteur de $\mathbb{R}^d$ , c est le nombre de parties. L’application f définit une partition convexe de l’espace vectoriel $\mathbb{R}^d$ .

entrée originale

Théorème T1 : densité des réseaux de neurones (Cybenko1989)

[Cybenko1989] Soit $E_{p}^{q}$ l’espace des réseaux de neurones à $p$ entrées et $q$ sorties, possédant une couche cachée dont la fonction de seuil est une fonction sigmoïde $\left( x\rightarrow 1-\frac{2}{1+e^{x}}\right)$ , une couche de sortie dont la fonction de seuil est linéaire Soit $F_{p}^{q}$ l’ensemble des fonctions continues de $C\subset\mathbb{R}^{p}\longrightarrow\mathbb{R}^{q}$ avec $C$ compact muni de la norme $\left\| f\right\| =\underset{x\in C}{\sup}\left\| f\left( x\right) \right\|$ Alors $E_{p}^{q}$ est dense dans $F_{p}^{q}$ .

entrée originale

Théorème T1 : distance d’édition

Soit $c$ et $d$ les fonctions définies respectivement par (1) et (2), alors :

$c$ est une distance sur $\mathcal{C} \Longleftrightarrow d$ est une distance sur $\mathcal{S}_\mathcal{C}$

entrée originale

Théorème T1 : loi asymptotique des coefficients

Soit $f$ un réseau de neurone défini par perceptron composé de :

une couche d’entrées
une couche cachée dont les fonctions de transfert sont sigmoïdes
une couche de sortie dont les fonctions de transfert sont linéaires

Ce réseau sert de modèle pour la fonction $f$ dans le problème de régression avec un échantillon $\vecteur{\pa{X_1,Y_1}}{\pa{X_N,Y_N}}$ , les résidus sont supposés normaux. La suite $\pa{\widehat{\epsilon_k}}$ définie par (2) vérifie :

$\dfrac{1}{N} \sum_{i=1}^{N} \widehat{\epsilon_k} = 0 = \esp\cro{f\pa{\widehat{W},X} - Y}$

Et le vecteur aléatoire $\widehat{W} - W^*$ vérifie :

$\sqrt{N} \cro { \widehat{W} - W^* } \; \overset{T \rightarrow + \infty}{\longrightarrow} \; \loinormale{0}{\widehat{\sigma_N}^2 \widehat{\Sigma_N}}$

Où la matrice $\widehat{\Sigma_N}$ est définie par (2).

end{xtheorem}

entrée originale

Théorème T1 : résolution de l’ACP

Les notations utilisées sont celles du problème de l”ACP. Dans ce cas :

(2)¶ $\begin{eqnarray*} S = \underset{ \begin{subarray}{c} W \in M_{p,d}\pa{\mathbb{R}} \\ W'W = I_d \end{subarray} } { \arg \max } \; \cro { \sum_{i=1}^{N} \norm{W'X_i}^2 } &=& \underset{ W \in M_{p,d}\pa{\mathbb{R}} } { \arg \min } \; \cro { \sum_{i=1}^{N} \norm{WW'X_i - X_i}^2 } \end{eqnarray*}$

De plus $S$ est l’espace vectoriel engendré par les $d$ vecteurs propres de la matrice $XX' = \sum_{i=1}^{N} X_i X_i'$ associées aux $d$ valeurs propres de plus grand module.

entrée originale

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}$

entrée originale

Théorème T1 : simulation d’une loi quelconque

Soit $F=\int f$ une fonction de répartition de densité $f$ vérifiant $f > 0$ , soit $U$ une variable aléatoire uniformément distribuée sur $\cro{0,1}$ alors $F^{-1}(U)$ est variable aléatoire de densité $f$ .

entrée originale

Théorème T2 : Borne supérieure de l’erreur produite par k-means++

On définit l’inertie par $J_(X) = \sum_{i=1}^{P} \; \min_G d^2(X_i, G)$ . Si $J_{OPT}$ définit l’inertie optimale alors $\esp{J(X)} \leqslant 8 (\ln C + 2) J_{OPT}(X)$ .

entrée originale

Théorème T2 : [Farago1993]_ 2

Les notations sont celles du même algorithme. On définit une mesure sur l’ensemble $X$ , $B\pa{x,r}$ désigne la boule de centre $x$ et de rayon $r$ , $Z \in X$ une variable aléatoire, de plus :

$p\pa{x,r} = P_X \pa{B\pa{x,r}} = \pr{ Z \in B\pa{x,r}}$

On suppose qu’il existe $d > 0$ et une fonction $f : X \longrightarrow \mathbb{R}$ tels que :

$\underset { r \rightarrow 0 } { \lim } \; \frac{ p\pa{x,r} } { r^d } = f\pa{x} > 0$

La convergence doit être uniforme et presque sûre. On note également $F_N$ le nombre de calculs de dissimilarité effectués par l’algorithme où $N$ est le nombre d’élément de $E$ , $P$ désigne toujours le nombre de pivots, alors :

$\underset{ n \rightarrow \infty } { \lim \sup } \; \esp{F_N} \leqslant k + \pa{\frac{\alpha}{\beta}}^{2d}$

entrée originale

Théorème T2 : rétropropagation

Cet algorithme s’applique à un réseau de neurones vérifiant la définition du perceptron. Il s’agit de calculer sa dérivée par rapport aux poids. Il se déduit des formules (3), (4), (5) et (7) et suppose que l’algorithme de propagation a été préalablement exécuté. On note $y'_{c,i} = \partialfrac{e}{y_{c,i}}$ , $w'_{c,i,j} = \partialfrac{e}{w_{c,i,j}}$ et $b'_{c,i} = \partialfrac{e}{b_{c,i}}$ .

Initialisation

for i in $1..C_C$

$y'_{C,i} \longleftarrow \partialfrac{e}{z_{C,i}} \pa{W,X} f'_{c,i}\pa{y_{C,i}}$

Récurrence

for c in $1..C-1$

for i in $1..C_c$

$y'_{c,i} \longleftarrow 0$

for j in $1..C_{c+1}$

$y'_{c,i} \longleftarrow y'_{c,i} + y'_{c+1,j} \; w_{c+1,j,i}$

$y'_{c,i} \longleftarrow y'_{c,i} \; f'_{c,i}\pa{y'_{c,i}}$

Terminaison

for c in $1..C$

for i in $1..C_c$

for j in $1..C_{c-1}$

$w'_{c,i,j} \longleftarrow z_{c-1,j} \; y'_{c,i}$

$b'_{c,i,j} \longleftarrow y'_{c,i}$

entrée originale

Théorème T2 : simulation d’une loi de Poisson

On définit une suite infinie $(X_i)_i>0$ de loi exponentielle de paramètre $\lambda$ . On définit ensuite la série de variables aléatoires $S_i = \sum_{k=1}^{i} X_k$ et enfin $N(t) = \inf \acc{ i \sac S_i > t}$ . Alors la variable aléatoire $N(t)$ suit une loi de Poisson de paramètre $\lambda t$ .

entrée originale

Théorème T2 : sélection d’architecture

Les notations utilisées sont celles du théorème loi asymptotique des coefficients. $f$ est un réseau de neurones de paramètres $W$ . On définit la constante $\tau$ , en général $\tau = 3,84$ puisque $\pr {X < \tau} = 0,95$ si $X \sim \chi_1^2$ .

Initialisation

Une architecture est choisie pour le réseau de neurones $f$ incluant un nombre M de paramètres.

Apprentissage

Le réseau de neurones $f$ est appris. On calcule les nombre et matrice $\widehat{\sigma_N}^2$ et $\widehat{\Sigma_N}$ . La base d’apprentissage contient $N$ exemples.

Test

for $k$ in $1..M$

$t_k \longleftarrow N \dfrac{ \widehat{w_k} ^2 } { \widehat{\sigma_N}^2 \pa{\widehat{\Sigma_N}^{-1}}_{kk} }$

Sélection

$k' \longleftarrow \underset{k}{\arg \min} \; t_k$

si $t_{k'} < \tau$

Le modèle obtenu est supposé être le modèle optimal. L’algorithme s’arrête.

sinon

La connexion  est supprimée ou le poids  est maintenue à zéro.
Retour à l’apprentissage.

entrée originale

Théorème T3 : somme de loi exponentielle iid

Soit $X_1,...,X_n$ $n$ variables aléatoires indépendantes et identiquement distribuées de loi $Exp(\lambda)$ alors la somme $\sum_{k=1}^n X_k$ suit une loi $Gamma(n,\lambda)$ .

entrée originale