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 \R^p, \; C= \acc { \vecteur{y_1}{y_p} \in \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( \R^p\right) ^{n}, \; \exists \vecteur{\gamma_1}{\gamma_n} \in \R^n \text{ tels que } \forall x\in \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\Rightarrow\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\R^p compact, alors :

\begin{array}{c} \forall\varepsilon>0, \; \forall\alpha>0, \; \exists\left( x_{1},...,x_{n}\right) \in\left( \R^{p}\right)^{n}, \; \exists\left( b_{1},...,b_{n}\right) \in\R^n \text{ tels que } \forall x\in\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\Rightarrow\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\R^{p}\longrightarrow\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 \R^p \text{ et } b \in \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 \infegal t \infegal 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} \infegal 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 \infegal s} et F_X(s)=\pr{X \infegal s}. On définit en fonction d’un seuil s \in \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 \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 \infegal 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 \infegal 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 \infegal k \infegal 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 \R^d et Y_i \in \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 \infegal i \infegal 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