Mylène Maïda nous parle des processus ponctuels déterminantaux, ou comment, partant de configurations de points, on peut modéliser la répartition spatiale des termitières, repenser les moteurs de recherche ou utiliser différemment les méthodes de Monte-Carlo !
Questions :
0’00 : Bonjour Mylène, tu nous parles de DPP, qu’est-ce que c’est ?
1’15 : Et donc, ça fait intervenir de l’algèbre et des probabilités ?
2’34 : Ces processus, ils servent à quoi ? (c’est là qu’on parle de termitières)
3’28
: Et il y a des interactions entre les DPP et les autres disciplines,
en particulier l’informatique ? (c’est là qu’on parle de moteurs de
recherche et de jaguars)
5’35 : Il y a aussi des intérêts numériques aux DPP… (c’est là qu’on parle de Monte-Carlo)
Cette vidéo peut être complétée par la lecture d’un article introductif dans la Gazette des mathématiciens : Processus ponctuels déterminantaux, par Adrien Hardy et Mylène Maïda (numéro 157, année 2018).
Introduction
Si vous demandez à un enfant de 5 ans de dessiner des points au hasard dans un disque, il produira probablement une figure comme celle-ci,

qui ressemble plus à la figure de gauche ci-dessous qu’à la figure de droite.
Pourtant, la figure de droite est une réalisation d’un processus ponctuel (c’est-à-dire des configurations de points aléatoires dans l’espace) qui incarne de façon naturelle la notion de hasard en mathématiques : un processus de Poisson homogène, bien connu des probabilistes, constitué de points choisis de manière uniforme dans le disque et indépendamment les uns des autres. Rien n’empêche donc d’avoir plusieurs points très proches, ce que le cerveau humain non averti aura tendance à éviter pour de mystérieuses raisons.
La figure de gauche, elle, représente les valeurs propres dans le plan complexe d’une matrice à entrées indépendantes gaussiennes complexes (une gaussienne complexe est une variable aléatoire complexe dont la partie réelle et la partie imaginaire sont deux variables gaussiennes réelles indépendantes), dite matrice de Ginibre. Il semblerait que les enfants de 5 ans trouvent plus intuitif la notion de hasard portée par ce type de configurations structurées que ce que les processus de Poisson ont à raconter. On va discuter ici de cette structure sous-jacente, qui est un cas particulier d’une classe de processus ponctuels manifestant des propriétés assez singulières : les processus ponctuels déterminantaux, ci-après dénommés DPP (pour determinantal point processes).
Ce qui suit ne sera ni une introduction formelle ni un recensement exhaustif de ce vaste sujet mais plutôt un florilège de quelques DPP que nous trouvons particulièrement séduisants, piochés dans des domaines des mathématiques a priori éloignés. Le lecteur qui cherche une présentation plus approfondie pourra consulter des références devenues classiques comme Hough et al. (2006), Johansson (2006), Soshnikov (2000) et Lyons (2003).
Avant de commencer, pour satisfaire autant les amoureux des applications pratiques que les collectionneurs de gemmes mathématiques, imaginez-vous taper la requête « jaguar » dans un moteur de recherche. Dans les premières réponses, vous ne voulez pas obtenir 10 articles sur des voitures de sport, mais aussi un article sur l’animal au pelage tacheté, un sur le film de Francis Veber et peut-être un sur une équipe de football américain. Si on veut balayer large, il faut introduire dans les algorithmes utilisés une forme de répulsion entre les items proches : si un article a été sélectionné, les articles très proches ont moins de chance de l’être. On verra à la fin de cet article que les DPP ont déjà excité la curiosité des machine learners en offrant des solutions implémentables à ce type de problématiques, entre autres
Mon premier DPP : le processus des retenues.
Considérons le processus suivant, qui vous rappellera peut-être l’odeur de l’école primaire : on prend une colonne de chiffres et on les additionne au fur et à mesure en partant du haut. A chaque étape, on note à droite le chiffre des unités obtenu, on inscrit un point s’il y a une retenue, et on continue.

Si la colonne contient des chiffres aléatoires indépendants et identiquement distribués (iid) suivant la loi uniforme sur , comment est distribué le processus des points associés aux retenues ?
Comme une colonne de chiffres iid uniformes sur donne, après additions successives, une colonne de chiffres des unités également iid uniformes sur
, il est équivalent de considérer le processus ponctuel des descentes suivant, étudié en plus grande généralité par Borodin et al. (2010) : on se donne une colonne de
chiffres
iid uniformes sur
et, à chaque ligne, on marque un point à droite si le chiffre qui s’y trouve est strictement inférieur à celui de la ligne au-dessus. Plus précisément, en posant
le processus ponctuel des descentes est donné par les configurations aléatoires
Par exemple, on obtient dans l’exemple suivant :

Le calcul simple
montre que, comme on pouvait s’y attendre, à chaque ligne on a un peu moins d’une chance sur deux d’avoir une descente/retenue. Aussi, la suite est une suite de variables aléatoires de Bernoulli (c’est-à-dire que
) de paramètre
mais elles ne sont pas indépendantes. Intuitivement, si on a une retenue à une ligne donnée, le chiffre sur cette ligne a tendance à être petit et on a moins de chance d’en avoir une à la suivante. Sur la Figure 1, on compare une réalisation du processus
avec une configuration aléatoire
où
sont des variables de Bernoulli iid de même paramètre
On voit bien apparaître une propriété d’association négative ou de répulsion entre les descentes adjacentes, analogue discret et unidimensionnel de ce que l’on observait sur la Figure 1 à gauche. Le calcul suivant confirme que deux descentes adjacentes sont négativement corrélées :
En revanche, si l’indépendance des variables
donne
on dira que le processus est de portée 1.
Ensuite pour décrire complètement la loi du processus ponctuel des descentes, il suffit de déterminer pour tout sous-ensemble
de
Si
est de cardinal
on parle de fonction de corrélation à
points, que l’on note
Nous avons déjà déterminé la fonction de corrélation à un point,
pour tout
, ainsi que la fonction de corrélation à deux points : pour tous
Pour traiter le cas , si
est une suite consécutive de
nombres de
on a
Sinon on peut écrire
avec
et
à distance au moins
et de cardinaux respectifs
et
, de sorte que
car le processus est de portée
. En travaillant un peu plus, on peut vérifier que cette collection de fonctions de corrélation est encodée par une fonction à deux variables
au sens où, pour tout
et
distincts deux à deux, on a :
On dit donc que le processus ponctuel est déterminantal (DPP) de noyau
Borodin, Diaconis et Fulman (2010) donnent une expression relativement explicite du noyau :
Plus généralement, ils montrent que tout processus ponctuel sur un segment de de portée 1 est déterminantal. Ils étudient également les descentes d’une permutation aléatoire : on dit qu’une permutation
de
a une descente en
si
Si on choisit
uniformément dans le groupe symétrique, le processus des descentes est déterminantal de noyau
Notons que nous rencontrerons plus loin d’autres DPP intéressants en lien avec des permutations aléatoires.
DPP et matrices aléatoires.
Si l’étude mathématique des DPP a commencé dans les années 70 avec la thèse d’Odile Macchi, inspirée par le formalisme des fermions en mécanique quantique, c’est leur apparition en théorie des matrices aléatoires qui a largement popularisé les DPP. Nous présentons maintenant quelques résultats faisant apparaître le caractère déterminantal de l’ensemble des valeurs propres de certains modèles matriciels. Pour tous les résultats évoqués dans ce paragraphe, on renvoie par exemple à la monographie d’Anderson et al (2010)
Un premier exemple est celui des valeurs propres de matrices unitaires tirées « uniformément ». Plus précisément, pour , on équipe le groupe unitaire
de son unique mesure de probabilité
invariante par multiplication à droite et à gauche, c’est-à-dire sa mesure de Haar normalisée. On obtient ainsi une variable aléatoire
à valeurs dans
en spécifiant que
pour tout borelien
. Nous nous intéressons alors à la loi jointe des
valeurs propres (aléatoires) de
. L’idée est d’effectuer le changement de variables qui, à une matrice unitaire, associe ses valeurs et vecteurs propres, et puis d’intégrer sur les vecteurs propres. Ainsi, si on note
les valeurs propres de la matrice aléatoire
, un calcul de jacobien classique dans les groupes de Lie attribué à Weyl montre que les phases
ont pour loi de probabilité :
<a name= »CUE »> </a>
En remarquant que le terme d’interaction entre les valeurs propres est le carré d’un déterminant de Vandermonde, on obtient
où l’on a introduit le noyau
Remarquons que est le noyau de l’opérateur de projection sur le sous-espace de
des polynômes trigonométriques de degré au plus
. Pour prendre en compte le caractère continu des angles propres on définit la version « infinitésimale » de la fonction de corrélation à
points introduite pour les processus des retenues : pour tout
et
distincts deux à deux,
Autrement dit, pour toute fonction test raisonnable, on a
<a name= »rhoCUE »></a>
Grâce à l’invariance par permutation de , on voit que
où la dernière identité vient en développant le déterminant sous l’intégrale et en utilisant que est le noyau d’un opérateur de projection :
Ainsi, le processus ponctuel des angles propres est déterminantal. Comparons visuellement une réalisation de ce processus à des variables iid uniformes sur le cercle unité : comme dans le cas des descentes, on observe une répartition plus régulière que dans le cas indépendant. Les angles propres sont bien répartis et il y a peu de variabilité alors que dans le cas uniforme, on retrouve des paquets de points qui peuvent être sensiblement différents d’une réalisation à l’autre.
Cette répulsion se lit aussi dans le terme d’interaction de (1). Elle induit des comportements surprenants pour le probabiliste non averti. A titre d’exemple, la variance d’une somme de angles propres est bien plus petite que celle de
angles iid (la variance d’une variable aléatoire complexe
est définie par
). En effet, si
sont iid uniformément distribués sur
, alors on a :
D’un autre côté, pour les angles propres on calcule, en utilisant (1) avec :
Pour que la somme de nombres complexes aléatoires de module
ait une variance unité, et ce indépendamment de
, il faut que de nombreuses compensations s’opèrent, et cela force les réalisations des valeurs propres à ne pas trop s’éloigner d’une configuration équi-espacée sur le cercle unité. Cela confirme l’impression visuelle de la Figure 1.
Une question naturelle est d’étudier les espacements entre ces angles propres asymptotiquement quand , après un zoom adéquat. En effet, comme il y a
angles propres bien répartis sur
, le processus ponctuel
est un sous-ensemble de
dont l’écartement typique entre deux points consécutifs est d’ordre un. Par changement de variables, c’est un DPP de noyau :
On s’est permis de rajouter discrètement le terme car modifier un noyau
en
où
ne s’annule pas ne change pas les déterminants associés aux fonctions de corrélation; ces deux noyaux engendrent donc le même DPP.
On obtient ainsi la convergence locale uniforme,
où par convention . En termes probabilistes, quand
le DPP des angles propres normalisés
des matrices unitaires aléatoires distribuées selon la mesure de Haar de
converge, au sens de la convergence uniforme locale de toutes les fonctions de corrélation, vers un processus ponctuel limite qui est le DPP associé au noyau sinus
: pour tout
et toute fonction
raisonnable,
<a name= »CUEsin »></a>
De plus, , vu comme un opérateur sur
, est la projection sur les fonctions dont la transformée de Fourier est à support dans
Ce dernier DPP génère presque sûrement des configurations infinies sur
.
L’une des idées maîtresses de la théorie des matrices aléatoires, qui apparaît déjà dans les travaux des pionniers comme Dyson et Wigner, est celle que le comportement local des valeurs propres présente un caractère universel, a contrario de leur comportement global. Pour illustrer ce phénomène penchons-nous dans un premier temps sur un autre modèle populaire de matrices aléatoires : le Gaussian Unitary Ensemble (GUE). Il s’agit cette fois de munir l’espace des matrices hermitiennes d’une mesure gaussienne. Plus précisément, l’isomorphisme
induit une mesure de Lebesgue
ainsi qu’une norme euclidienne
sur
, et on considère alors la mesure gaussienne
de densité proportionnelle à
Un changement de variable et un calcul de jacobien similaire à celui des matrices unitaires montre que la loi jointe des valeurs propres
de la matrice aléatoire de loi
est alors donnée par :
où est une constante de normalisation explicite : c’est un ratio de produits de fonctions Gamma, que l’on obtient comme cas limite de la formule intégrale de Selberg. Après quelques manipulations on obtient que l’ensemble des valeurs propres
est un DPP sur
de noyau :
où, pour tout ,
est une base orthonormée de
donnée par des fonctions de Hermite renormalisées. Si
est le
-ième polynôme de Hermite, alors on prend
avec
. Là encore on a affaire à un noyau de projection sur un sous-espace de dimension finie de
, celui des fonctions de la forme
avec
un polynôme de degré au plus
. Quand
, comme illustré dans la Figure 1 les valeurs propres se concentrent sur le compact
avec une densité
appelée loi du demi-cercle.

Maintenant, si on zoome d’un facteur autour d’un point
de
, on peut montrer que le comportement local des valeurs propres autour de ce point est encore régi par le noyau sinus
Plus précisément, on a la convergence locale uniforme,
Notez que la limite ne dépend pas de . La preuve de cette convergence est un peu plus délicate que dans le cas des matrices unitaires et requiert une analyse fine du comportement asymptotique des fonctions de Hermite
D’un autre côté, si on s’intéresse aux points du bord du demi-cercle, on voit apparaître après une remise à l’échelle différente un autre noyau universel appelé noyau d’Airy,
Ici est la fonction d’Airy, qui satisfait
et qui apparaît dans l’étude optique des arcs-en-ciel. Par exemple, au point
(l’analyse en
est la même),
Avec du travail, on montre que cette convergence a lieu au sens de la convergence des opérateurs de classe trace sur pour tout
, et on en déduit les fluctuations de la plus grande valeur propre autour du bord droit. En effet, on peut exprimer la fonction de répartition de la plus grande particule d’un DPP sur
en termes d’un déterminant de Fredholm, ici
qui est continu pour cette topologie, et on obtient donc, pour tout ,
La loi de probabilité associée à la fonction de répartition est connue sous le nom de loi de Tracy-Widom. Ces derniers ont établi une formule explicite de
en terme de la solution de Hastings-McLeod de l’équation de Painlevé II. C’est aussi la loi de la plus grande particule du DPP associée au noyau d’Airy. On va retrouver cette loi un peu plus loin en dehors du cadre des matrices aléatoires.
Suite à de nombreux travaux qu’il serait impossible de tous rappeler ici, il a été constaté que les noyaux sinus et d’Airy sont omniprésents dans la description du comportement local des valeurs propres d’un grand nombre de modèles de matrices aléatoires, en lien ou non avec les DPP. On parle ainsi de phénomène d’universalité en matrices aléatoires. Il est surprenant de constater que ces deux DPP universels apparaissent également en dehors du cadre des matrices aléatoires; nous présentons maintenant trois faits d’armes particulièrement marquants.
Polynômes orthogonaux et noyau sinus
D’abord, présentons l’élégante approche de Lubinsky (2009) pour les DPP liés à des familles de polynômes orthogonaux. On considère une mesure borélienne positive supportée dans
telle que
contient tous les polynômes. On peut définir alors une famille orthonormée de polynômes
dans
de coefficients dominants
positifs. On note
la dérivée de Radon-Nikodym de
par rapport à la mesure de Lebesgue, de sorte que
avec
singulière par rapport à la mesure de Lebesgue. On introduit alors le noyau de Christoffel-Darboux, bien connu en théorie de l’approximation :
Le DPP associé à ce noyau engendre presque sûrement des configurations de points dans
. On suppose que
est une mesure régulière de
, au sens où
converge vers
quand
. C’est le cas par exemple pour les familles classiques, comme les polynômes de Legendre, Tchebychev, et plus généralement Jacobi. C’est aussi le cas dès que
presque partout sur
. Lubinsky montre alors le résultat suivant : pour tout
de
tel que
est absolument continue sur un voisinage de
, et de densité
continue et strictement positive en
, on a la convergence locale uniforme :
où cette fois Notons que sous l’hypothèse plus forte que
avec
positive et continue sur
, alors on a une convergence globale des points du DPP associé à
vers la loi de l’arcsinus de densité
, comme illustré dans la Figure 1. La preuve de ce résultat, étonnamment courte par rapport aux standards de ce domaine des mathématiques, utilise de l’analyse élémentaire de façon très astucieuse pour offrir une méthode de comparaison robuste entre des noyaux associés à différentes mesures.

Fonction zêta de Riemann et noyau sinus
Ensuite, nous rendons compte d’une apparition inattendue du DPP de noyau sinus en théorie analytique des nombres. Pour un nombre complexe de partie réelle
la fonction zêta de Riemann est définie par
Cette fonction admet une extension méromorphe à , qui possède des zéros « triviaux » en les entiers pairs négatifs :
etc. Les autres zéros sont localisés dans la bande
La célèbre conjecture de Riemann dit que ces zéros sont tous de partie réelle égale à
. Sous l’hypothèse de Riemann, on peut donc écrire ces zéros sous la forme
avec
en vertu de la symétrie
. Un résultat classique donne alors, quand
,
ce qui nous amène à poser
si bien que quand
; on s’attend à ce que l’espacement typique entre les
consécutifs soit d’ordre un. Pour mieux comprendre les espacements entre ces zéros renormalisés, au moins asymptotiquement, on peut s’inspirer des processus ponctuels et considérer l’analogue des fonctions de corrélation (1) :
pour et des fonctions
raisonnables. Rudnick et Sarnark obtiennent alors, sous d’assez fortes hypothèses sur
,
un résultat qui s’apparente à (1). Ainsi, asymptotiquement, les espacements entre les zéros renormalisés se comportent comme une réalisation typique du DPP de noyau sinus. La restriction du domaine d’intégration à l’hyperplan est liée au fait que
ne doit dépendre que des espacements entre les
. Dans le cas des corrélations par paires, on a par exemple pour
,
). Ainsi, asymptotiquement, les espacements entre les zéros renormalisés se comportent comme une réalisation typique du DPP de noyau sinus. La restriction du domaine d’intégration à l’hyperplan est liée au fait que
ne doit dépendre que des espacements entre les
. Dans le cas des corrélations par paires, on a par exemple pour
,
Ce cas particulier a été démontré par Montgomery dans les années 70, pour des fonctions dont la transformée de Fourier est
et à support dans
. La conjecture de Montgomery, toujours ouverte, affirme que le résultat doit être vrai sans restriction de support. L’histoire raconte qu’en 1972, Montgomery, alors encore étudiant et déjà auteur du résultat ci-dessus, rencontre au thé de l’après-midi à Princeton le physicien Dyson. Celui-ci, spécialiste de matrices aléatoires, reconnaît immédiatement dans le résultat de Montgomery le fameux noyau sinus.
Permutations aléatoires et noyau d’Airy
Nous terminons par une rencontre surprenante avec la loi de Tracy-Widom dans l’étude des permutations aléatoires. Si est une permutation de
, on dit que
avec
est une sous-suite croissante de
. On note
la plus grande longueur d’une sous-suite croissante; on a donc
. Par exemple, si
alors et elle est atteinte en la sous-suite croissante
(mais également en
). Si maintenant
est une permutation aléatoire tirée uniformément sur le groupe symétrique
, l’étude du comportement asymptotique de
quand
est grand est connu sous le nom de problème d’Ulam. Après des travaux de Hammersley, Vershik, Kerov, Logan et Schepp, il a été obtenu que
Une avancée fondamentale a été réalisée par Baik et al. (1999) en obtenant les fluctuations de autour de sa valeur moyenne : pour tout
,
Autrement dit, la variable aléatoire converge en loi vers la distribution de Tracy-Widom quand
. Pour comprendre le caractère déterminantal du problème, nous ne présentons pas la preuve originelle de Baik et al. (1999) mais plutôt celle de Borodin et al. (2000). Leur analyse repose sur la correspondance de Robinston-Schensted (RS), bien connue en théorie des représentations du groupe symétrique, qui associe à une permutation
une paire de tableaux d’Young de même forme. Plus précisément, une partition
d’un entier
, c’est-à-dire une suite décroissante d’entiers positifs de somme
, est encodée par un diagramme de Ferrers de
cases avec
cases sur la
-ème ligne. Par exemple la partition
de
est encodée par le diagramme :

Etant donné un diagramme de Ferrers avec
cases, on appelle tableau de Young de forme
un remplissage de ses cases par les entiers de
à
de façon strictement croissante le long des lignes et des colonnes. La correspondance RS associe à une permutation
deux tableaux de Young de même forme. On place successivement les entiers
dans le premier tableau en commençant par la première ligne avec le principe suivant : chaque nouvel élément
s’insère sur la première ligne. Si
est le plus grand entier de la ligne, on le rajoute dans une nouvelle case à droite. Sinon il prend la place du plus petit entier qui lui est supérieur. Ce dernier est alors rétrogradé à la ligne suivante, où les mêmes règles lui sont appliquées. Le second tableau mémorise l’ordre dans lequel les cases ont été créées. Ainsi, pour
la correspondance RS donne les étapes successives :

On utilise alors deux propriétés clefs. D’abord, , la longueur de la première ligne des tableaux obtenus par la correspondance RS. Ensuite, si on applique la correspondance RS à la permutation uniforme
, alors la probabilité que la forme des tableaux obtenus soit la partition
de
est égale à
Ici
est le nombre de tableaux de Young de forme
; c’est aussi la dimension de la représentation irréductible de
indexée par la partition
. Cette loi de probabilité
sur les diagrammes de Ferrers à
cases est la mesure de Plancherel. On considère maintenant
le mélange poissonnien de paramètre
des mesures de Plancherel, qui génère des diagrammes de Ferrers de taille aléatoire: on tire aléatoirement un entier
de loi de Poisson de paramètre
, puis on tire un diagramme de Ferrers à
cases suivant la mesure de Plancherel
. Ainsi, si on note
le nombre de cases d’un diagramme de Ferrers
, la probabilité sous
d’obtenir un diagramme
est :
Cette poissonnisation est motivée par le fait suivant : si a pour distribution
alors la configuration aléatoire
est un DPP sur
. Son noyau
peut être écrit sous la forme d’une double intégrale sur des contours complexes, adaptée à l’analyse asymptotique (méthode du point col). En l’occurrence, Borodin et al. (2000) ont montré que
La convergence de vers la loi de Tracy-Widom citée plus haut en est une conséquence car, sous
, le nombre de cases d’un tableau se concentre autour de
quand
(procédé de dépoissonnisation); en d’autres termes, pour
entier et grand les distributions
et
génèrent des diagrammes similaires en un sens qui peut être quantifié.
Utilisation des DPP en apprentissage automatique
Pour clore le petit voyage que nous vous avons proposé dans le vaste paysage des DPP, revenons un peu sur l’exemple des jaguars de l’introduction en esquissant quelques traits de l’utilisation des DPP dans des contextes d’apprentissage automatique. Le message principal est que lorsqu’on veut modéliser des situations impliquant de la répulsion, de la diversité, des corrélations négatives entre des objets, les DPP fournissent des modèles efficaces, simples à manipuler et à simuler. On renverra le lecteur désireux d’approfondir le sujet à Kulesza et Taskar (2012) par exemple.
Dans la plupart de ces applications, on cherche à sélectionner un sous-ensemble (aléatoire) d’objets dans une base de données, c’est-à-dire dans un ensemble discret de cardinal
éventuellement très grand; typiquement des images ou des textes. On considère alors une classe de DPP qui génèrent des configurations
de cardinal aléatoire. Dans ce contexte, on attribue au
-ème élément de
un vecteur
, où la dimension
est fixée par l’utilisateur. Par exemple
peut encoder les pixels de la
-ème image et
va dépendre de la résolution choisie. On considère alors la matrice semi-définie positive
où
est la matrice
de colonnes
. On prend ensuite
comme noyau d’un DPP
. Ainsi, pour tout
,
avec la convention En termes de la matrice
, on a
On voit alors que est égale, à une constante de normalisation près, au volume carré du parallélotope généré par les colonnes
de
avec
. Ainsi, si
avec
et
avec
alors
s’interprète comme une mesure de l’importance du
-ème objet de
tandis que
représente une mesure de la similarité entre le
-ème et le
-ème objet. Plus précisément,
est proportionnelle à
En pratique, il faut étiqueter chaque objet de
avec son attribut
, par exemple à la façon dont PageRank assigne un niveau d’importance à chaque page web, et puis calculer les matrices
et
associées. Une réalisation du DPP de noyau
fournira alors un sous-ensemble de
présentant de la diversité au sens de la matrice
. Par exemple, si
est l’ensemble des images correspondant au mot clef « jaguar » sur internet, et qu’on a au préalable étiqueté chacun de ses éléments avec des attributs
, une réalisation du DPP
fournira un sous-ensemble d’images diversifié.
On peut aussi se restreindre à une famille paramétrée de noyaux et estimer
à l’aide des méthodes usuelles en statistiques à partir de données d’entraînement. Kulesza et Taskar (2012) développent ainsi l’exemple des résumés automatiques de textes, où l’on dispose de nombreux textes sur un même sujet (par exemple des articles de presse sur un fil d’actualités) et l’on veut en extraire un résumé, c’est-à-dire un petit nombre de phrases contenant le plus d’information possible.
L’aspect séduisant de ces modèles vient surtout du fait qu’ils sont facilement implémentables de façon exacte : on peut répondre à la plupart des questions d’inférence les concernant en temps polynomial, essentiellement en multipliant, inversant, diagonalisant ou calculant des déterminants de matrices de taille au prix de
opérations élémentaires. En particulier, on dispose d’algorithmes exacts pour simuler un DPP à ce coût-là.

L’utilisation de DPP en apprentissage automatique, mais aussi en statistiques spatiales (Lavancier et al, 2015) ou en intégration numérique, n’en est qu’à ses balbutiements et semble séduire de plus en plus d’utilisateurs des mathématiques.
Remerciements
Merci à Raphaël, Rosalie et Elvire pour leurs simulations innocentes, de même que Rémi Bardenet et Guillaume Gautier. Nous tenons à remercier Sophie Grivaux pour sa relecture attentive d’une première version du texte et pour sa patience
Bibliographie
[1] G. W. Anderson, A. Guionnet, and O. Zeitouni. An introduction to random matrices, volume 118 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 2010.
[2] J. Baik, P. Deift, and K. Johansson. On the distribution of the length of the longest increasing subsequence of random permutations. J. Amer. Math. Soc., 12(4):1119–1178, 1999.
[3] A. Borodin, A. Okounkov, and G. Olshanski. Asymptotics of Plancherel measures for symmetric groups. J. Amer. Math. Soc., 13(3):481–515, 2000.
[4] A. Borodin, P. Diaconis, and J. Fulman. On adding a list of numbers (and other onedependent determinantal processes). Bull. Amer. Math. Soc. (N.S.), 47(4):639–670, 2010.
[5] J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág. Determinantal processes and independence. Probab. Surv., 3:206–229, 2006.
[6] K. Johansson. Random matrices and determinantal processes. In Mathematical statistical physics, pages 1–55. Elsevier B. V., Amsterdam, 2006.
[7] A. Kulesza and B. Taskar. Determinantal point processes for machine learning. Foudations and Trends in Machine Learning, 16, 2012.
[8] F. Lavancier, J. Møller, and E. Rubak. Determinantal point process models and statistical inference. Journal of the Royal Statistical Society. Series B: Statistical Methodology, 77 (4):853–877, 2015.
[9] D. S. Lubinsky. A new approach to universality limits involving orthogonal polynomials. Ann. of Math. (2), 170(2):915–939, 2009.
[10] R. Lyons. Determinantal probability measures. Publications Mathématiques de l’Institut des Hautes Etudes Scientifiques, 2003.
[11] A. Soshnikov. Determinantal random point fields. Uspekhi Mat. Nauk, 55(5(335)):107–160, 2000.
Votre commentaire