Listes des définitions et théorèmes#
.
Corollaires#
Corollaire C1 : Estimateur de l’aire sous la courbe ROC
On dispose des scores des expériences qui ont réussi et les scores des expériences qui ont échoué. On suppose également que tous les scores sont indépendants. Les scores sont identiquement distribués, il en est de même pour les scores . Un estimateur de l’aire sous la courbe ROC” est :
(1)#
Corollaire C1 : approximation d’une fonction créneau
Soit , alors :
Corollaire C1 : nullité d’un coefficient
Les notations utilisées sont celles du théorème sur loi asymptotique des coefficients. Soit un poids du réseau de neurones d’indice quelconque . Sa valeur estimée est , sa valeur optimale . D’après le théorème :
Corollaire C2 : Variance de l’estimateur AUC
On note et . et sont de même loi que , , sont de même loi que . La variance de l’estimateur définie par (1) est :
Corollaire C2 : approximation d’une fonction indicatrice
Soit compact, alors :
Corollaire C3 : famille libre de fonctions
Soit l’ensemble des fonctions continues de avec compact muni de la norme : Alors l’ensemble des fonctions sigmoïdes :
est une base de .
Définitions#
Définition D1 : B+ tree
Soit un B+ tree, soit un noeud de , il contient un vecteur avec et . Ce noeud contient aussi exactement noeuds fils notés . On désigne par l’ensemble des descendants du noeud et . Le noeud vérifie :
Définition D1 : Courbe ROC
On suppose que est la variable aléatoire des scores des expériences qui ont réussi. est celle des scores des expériences qui ont échoué. On suppose également que tous les scores sont indépendants. On note et les fonctions de répartition de ces variables. et . On définit en fonction d’un seuil :
La courbe ROC est le graphe lorsque varie dans .
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 comme étant le minimum obtenu :
(1)#
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 comme étant le minimum obtenu :
(1)#
Définition D1 : Minimum Keystroke
On définit la façon optimale de saisir une requête sachant un système de complétion comme étant le minimum obtenu :
(1)#
La quantité représente le nombre de touche vers le bas qu’il faut taper pour obtenir la chaîne avec le système de complétion et les premières lettres de .
Définition D1 : Régression quantile
On dispose d’un ensemble de n couples avec et . La régression quantile consiste à trouver tels que la somme est minimale.
Définition D1 : bruit blanc
Une suite de variables aléatoires réelles est un bruit blanc :
,
Définition D1 : loi de Poisson et loi exponentielle
Si une variable suit une loi de Poisson de paramète , elle a pour densité :
Si une variable suit une loi exponentielle de paramètre , elle a pour densité :
Définition D1 : mot
On note l’espace des caractères ou des symboles. Un mot ou une séquence est une suite finie de . On note l’espace des mots formés de caractères appartenant à .
Définition D1 : mélange de lois normales
Soit une variable aléatoire d’un espace vectoriel de dimension , suit un la loi d’un mélange de lois gaussiennes de paramètres , alors la densité de est de la forme :
Avec : .
Définition D1 : neurone
Un neurone à entrées est une fonction définie par :
,
avec
Définition D1 : neurone distance
Un neurone distance à entrées est une fonction définie par :
,
avec
Définition D1 : orthonormalisation de Schmidt
L’orthonormalisation de Shmidt :
Soit une base de
On définit la famille par :
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 comme étant le minimum obtenu :
(2)#
Définition D2 : Régression quantile
On dispose d’un ensemble de n couples avec et . La régression quantile consiste à trouver tels que la somme est minimale.
Définition D2 : couche de neurones
Soit et deux entiers naturels, on note avec . Une couche de neurones et entrées est une fonction :
vérfifiant :
est un neurone.
Définition D2 : distance d’édition
La distance d’édition sur est définie par :
Définition D2 : neurone distance pondérée
Pour un vecteur donné , on note . Un neurone distance pondérée à entrées est une fonction définie par :
,
avec
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 . On suppose ici que et . Si ce n’est pas le cas, on ajoute ces valeurs à l’ensemble .
Pour un taux d’erreur donné , on cherche tel que :
Le taux de reconnaissance cherché est donné par :
Définition D3 : distance entre caractères
Soit
l’ensemble des caractères ajouté au caractère vide .
.
On note
la fonction coût définie comme suit :
(1)#
On note l’ensemble des suites finies de .
Définition D3 : réseau de neurones multi-couches ou perceptron
Un réseau de neurones multi-couches à sorties, entrées et couches est une liste de couches connectées les unes aux autres de telle sorte que :
, chaque couche possède neurones et entrées
, de plus et
Les coefficients de la couche sont notés , cette couche définit une fonction . Soit la suite définie par :
On pose , le réseau de neurones ainsi défini est une fonction telle que :
Définition D4 : mot acceptable
Soit un mot tel qu’il est défini précédemment. Soit une suite infinie de caractères, on dit que est un mot acceptable pour si et seulement si la sous-suite extraite de contenant tous les caractères différents de est égal au mot . On note l’ensemble des mots acceptables pour le mot .
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 sur est définie par :
(5)#
Définition D7 : distance d’édition tronquée
Soient deux mots , on définit la suite :
Par :
Définition D8 : distance d’édition tronquée étendue
Soit deux mots , on définit la suite :
par :
Lemmes#
Lemme L1 : M” et sous-ensemble
On suppose que la complétion est préfixe pour la requête et ce qui signifie que la complétion est toujours affichée avant la complétion si elles apparaissent ensemble. Alors . Plus spécifiquement, si on considère l’ensemble ( est la complétion sans son préfixe ).
Lemme L1 : Rang k
On note , , avec , , et avec . On suppose que les matrices sont solution du problème d’optimisation . On suppose que . Alors les les matrices et sont de rang .
Lemme L1 : inertie minimum
Soit , points de , le minimum de la quantité :
est atteint pour le barycentre des points .
Lemme L2 : Projection
On note , , avec , , et avec . On suppose que les matrices sont solution du problème d’optimisation . On considère que la matrice est un ensemble de points dans dans un espace vectoriel de dimension . La matrice représente des projections de ces points dans l’espace vectoriel engendré par les vecteurs colonnes de la matrice .
Lemme L2 : calcul de *M”(q, S)*
On suppose que est la complétion la plus longue de l’ensemble qui commence :
La métrique vérifie la propriété suivante :
Figures#
Figure F1 : Gradient conjugué
Gradient et gradient conjugué sur une ligne de niveau de la fonction , le gradient est orthogonal aux lignes de niveaux de la fonction , mais cette direction est rarement la bonne à moins que le point 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.
Figure F1 : Modèle optimal pour la base de test
Figure F1 : Principe de la compression par un réseau diabolo
Figure F1 : Réseau de neurones adéquat pour la classification
Figure F1 : neurone graphique
Le vecteur joue le rôle des entrées. est appelé parfois le potentiel. . est appelée la sortie du neurone. est appelée la fonction de transfert ou de seuil. .
Figure F2 : Exemple de minimal locaux
Figure F2 : Modèle du perceptron multi-couche (multi-layer perceptron, MLP)
: entrées
nombre de neurones sur la couche ,
sortie du neurone , de la couche , par extension,
potentiel du neurone de la couche
coefficient associé à l’entrée du neurone de la couche ,
biais du neurone de la couche
fonction de seuil du neurone de la couche
Figure F2 : Réseau de neurones pour lequel la sélection de connexions s’applique
Figure F2 : Réseau diabolo : réduction d’une dimension
Ce réseau possède 3 entrées et 3 sorties Minimiser l’erreur 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.
Figure F3 : Courbe d’inertie pour l’ACP
Courbe d’inertie : point d’inflexion pour , 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.
Problèmes#
Problème P1 : Classification
Soit une variable aléatoire et une variable aléatoire discrète , l’objectif est d’approximer la fonction . Les données du problème sont un échantillon de points : avec et un modèle paramétré avec :
avec , est une fonction de paramètre à valeur dans et vérifiant la contrainte : .
Problème P1 : Factorisation de matrices positifs
Soit , on cherche les matrices à coefficients positifs et qui sont solution du problème d’optimisation :
Problème P1 : Optimiser un système de complétion
On suppose que l’ensemble des complétions est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions qu’on considère comme une permutation de l’ensemble de départ : . Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes . est la requête, est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :
Déterminer le meilleur système de complétion revient à trouver la permutation qui minimise .
Problème P1 : Régression
Soient deux variables aléatoires et , l’objectif est d’approximer la fonction . Les données du problème sont un échantillon de points et un modèle paramétré avec :math:theta` :
avec , bruit blanc, est une fonction de paramètre .
Problème P1 : analyse en composantes principales (ACP)
Soit avec . Soit , où les vecteurs sont les colonnes de et . On suppose également que les forment une base othonormée. Par conséquent :
est l’ensemble des vecteurs projetés sur le sous-espace vectoriel engendré par les vecteurs . Réaliser une analyse en composantes principales, c’est trouver le meilleur plan de projection pour les vecteurs , celui qui maximise l’inertie de ce nuage de points, c’est donc trouver tel que :
(1)#
Le terme est l’inertie du nuage de points projeté sur le sous-espace vectoriel défini par les vecteurs colonnes de la matrice .
Problème P1 : estimateur du maximum de vraisemblance
Soit un vecteur tel que :
On cherche le vecteur vérifiant :
Problème P2 : Optimiser un système de complétion filtré
On suppose que l’ensemble des complétions est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions qu’on considère comme une permutation de l’ensemble de départ : . On utilise aussi une fonction 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 . est la requête, est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :
Déterminer le meilleur système de complétion revient à trouver la permutation qui minimise .
Problème P2 : Prédiction
Soit et , on cherche les matrices à coefficients positifs qui sont solution du problème d’optimisation :
Problème P2 : classification
Soit l’échantillon suivant :
représente la probabilité que l’élément appartiennent à la classe :
Le classifieur cherché est une fonction définie par :
Dont le vecteur de poids est égal à :
Propriétés#
Problème P1 : Classification
Soit une variable aléatoire et une variable aléatoire discrète , l’objectif est d’approximer la fonction . Les données du problème sont un échantillon de points : avec et un modèle paramétré avec :
avec , est une fonction de paramètre à valeur dans et vérifiant la contrainte : .
Problème P1 : Factorisation de matrices positifs
Soit , on cherche les matrices à coefficients positifs et qui sont solution du problème d’optimisation :
Problème P1 : Optimiser un système de complétion
On suppose que l’ensemble des complétions est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions qu’on considère comme une permutation de l’ensemble de départ : . Ce système de complétion est destiné à un des utilisateurs qui forment des recherches ou requêtes . est la requête, est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :
Déterminer le meilleur système de complétion revient à trouver la permutation qui minimise .
Problème P1 : Régression
Soient deux variables aléatoires et , l’objectif est d’approximer la fonction . Les données du problème sont un échantillon de points et un modèle paramétré avec :math:theta` :
avec , bruit blanc, est une fonction de paramètre .
Problème P1 : analyse en composantes principales (ACP)
Soit avec . Soit , où les vecteurs sont les colonnes de et . On suppose également que les forment une base othonormée. Par conséquent :
est l’ensemble des vecteurs projetés sur le sous-espace vectoriel engendré par les vecteurs . Réaliser une analyse en composantes principales, c’est trouver le meilleur plan de projection pour les vecteurs , celui qui maximise l’inertie de ce nuage de points, c’est donc trouver tel que :
(1)#
Le terme est l’inertie du nuage de points projeté sur le sous-espace vectoriel défini par les vecteurs colonnes de la matrice .
Problème P1 : estimateur du maximum de vraisemblance
Soit un vecteur tel que :
On cherche le vecteur vérifiant :
Problème P2 : Optimiser un système de complétion filtré
On suppose que l’ensemble des complétions est connu. On souhaite ordonner cet ensemble pour obtenir l’ensemble ordonné des complétions qu’on considère comme une permutation de l’ensemble de départ : . On utilise aussi une fonction 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 . est la requête, est la fréquence associée à cette requête. On définit l’effort demandé aux utilisateurs par ce système de complétion :
Déterminer le meilleur système de complétion revient à trouver la permutation qui minimise .
Problème P2 : Prédiction
Soit et , on cherche les matrices à coefficients positifs qui sont solution du problème d’optimisation :
Problème P2 : classification
Soit l’échantillon suivant :
représente la probabilité que l’élément appartiennent à la classe :
Le classifieur cherché est une fonction définie par :
Dont le vecteur de poids est égal à :
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 à .
Théorème T1 : La factorisation de matrice est équivalente à une analyse en composantes principales
On note , , avec , , et avec . On suppose que les matrices sont solution du problème d’optimisation . On considère que la matrice est un ensemble de points dans dans un espace vectoriel de dimension . On suppose . La matrice définit un hyperplan identique à celui défini par les vecteurs propres associés aux plus grande valeurs propres de la matrice où est la transposée de .
Théorème T1 : M”, ordre et sous-ensemble
Soit une requête de l’ensemble de complétion ordonnées selon . Si cet ordre vérifie :
(1)#
On note l’ensemble :
alors :
Théorème T1 : Régression linéaire après Gram-Schmidt
Soit une matrice avec . Et un vecteur . D’après l”algorithme de Gram-Schmidt, il existe deux matrices telles que ou . et . La matrice T est triangulaire supérieure et vérifie ( est la matrice identité). Alors . est la solution du problème d’optimisation .
Théorème T1 : [Farago1993]_ 1
Les notations sont celles de l’algorithme précédent. Il retourne le plus proche voisin de inclus dans . Autrement dit, .
Théorème T1 : convergence de la méthode de Newton
Soit une fonction continue de classe . On suppose les hypothèses suivantes vérifiées :
H1 : est un singleton
H2 :
H3 : tels que
H4 : la suite vérifie, et ,
Alors la suite construite de la manière suivante , : vérifie .
Théorème T1 : convergence des k-means
Quelque soit l’initialisation choisie, la suite construite par l’algorithme des k-means converge.
Théorème T1 : convexité des classes formées par une régression logistique
On définit l’application qui associe la plus grande coordonnée . A est une matrice , B est un vecteur de , c est le nombre de parties. L’application f définit une partition convexe de l’espace vectoriel .
Théorème T1 : densité des réseaux de neurones (Cybenko1989)
[Cybenko1989] Soit l’espace des réseaux de neurones à entrées et sorties, possédant une couche cachée dont la fonction de seuil est une fonction sigmoïde , une couche de sortie dont la fonction de seuil est linéaire Soit l’ensemble des fonctions continues de avec compact muni de la norme Alors est dense dans .
Théorème T1 : distance d’édition
Soit et les fonctions définies respectivement par (1) et (2), alors :
est une distance sur est une distance sur
Théorème T1 : loi asymptotique des coefficients
Soit 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 dans le problème de régression avec un échantillon , les résidus sont supposés normaux. La suite définie par (2) vérifie :
Et le vecteur aléatoire vérifie :
Où la matrice est définie par (2).
end{xtheorem}
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)#
De plus est l’espace vectoriel engendré par les vecteurs propres de la matrice associées aux valeurs propres de plus grand module.
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 :
Théorème T1 : simulation d’une loi quelconque
Soit une fonction de répartition de densité vérifiant , soit une variable aléatoire uniformément distribuée sur alors est variable aléatoire de densité .
Théorème T2 : Borne supérieure de l’erreur produite par k-means++
On définit l’inertie par . Si définit l’inertie optimale alors .
Théorème T2 : [Farago1993]_ 2
Les notations sont celles du même algorithme. On définit une mesure sur l’ensemble , désigne la boule de centre et de rayon , une variable aléatoire, de plus :
On suppose qu’il existe et une fonction tels que :
La convergence doit être uniforme et presque sûre. On note également le nombre de calculs de dissimilarité effectués par l’algorithme où est le nombre d’élément de , désigne toujours le nombre de pivots, alors :
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 , et .
Initialisation
Récurrence
Terminaison
Théorème T2 : simulation d’une loi de Poisson
On définit une suite infinie de loi exponentielle de paramètre . On définit ensuite la série de variables aléatoires et enfin . Alors la variable aléatoire suit une loi de Poisson de paramètre .
Théorème T2 : sélection d’architecture
Les notations utilisées sont celles du théorème loi asymptotique des coefficients. est un réseau de neurones de paramètres . On définit la constante , en général puisque si .
Initialisation
Une architecture est choisie pour le réseau de neurones incluant un nombre M de paramètres.
Apprentissage
Le réseau de neurones est appris. On calcule les nombre et matrice et . La base d’apprentissage contient exemples.
Test
Sélection
Théorème T3 : somme de loi exponentielle iid
Soit variables aléatoires indépendantes et identiquement distribuées de loi alors la somme suit une loi .