Sur l’échantillonnage des processus ponctuels ...
Document type :
Thèse
Title :
Sur l’échantillonnage des processus ponctuels déterminantaux
English title :
On sampling determinantal point processes
Author(s) :
Gautier, Guillaume, Michel, Jean [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Thesis director(s) :
Michal Valko
Rémi Bardenet
Rémi Bardenet
Defence date :
2020-03-20
Jury president :
Pierre-Olivier Amblard [Président]
Agnès Desolneux [Rapporteur]
Romain Couillet [Rapporteur]
Frédéric Lavancier
Michalis Titsias
Sheehan Olver
Agnès Desolneux [Rapporteur]
Romain Couillet [Rapporteur]
Frédéric Lavancier
Michalis Titsias
Sheehan Olver
Jury member(s) :
Pierre-Olivier Amblard [Président]
Agnès Desolneux [Rapporteur]
Romain Couillet [Rapporteur]
Frédéric Lavancier
Michalis Titsias
Sheehan Olver
Agnès Desolneux [Rapporteur]
Romain Couillet [Rapporteur]
Frédéric Lavancier
Michalis Titsias
Sheehan Olver
Accredited body :
Centrale Lille Institut
Doctoral school :
École doctorale Sciences pour l'ingénieur (Lille)
NNT :
2020CLIL0002
Keyword(s) :
Processus ponctuels déterminantaux
Echantillonnage
Simulation
Méthodes Monte Carlo
Matrices aléatoires
Echantillonnage
Simulation
Méthodes Monte Carlo
Matrices aléatoires
English keyword(s) :
Determinantal point processes
Sampling
Simulation
Monte Carlo methods
Random matrices
Sampling
Simulation
Monte Carlo methods
Random matrices
HAL domain(s) :
Sciences de l'ingénieur [physics]/Autre
French abstract :
Un processus ponctuel déterminantal (DPP) génère des configurations aléatoires de points ayant tendance à se repousser. La notion de répulsion est encodée par les sous-déterminants d’une matrice à noyau, au sens des méthodes ...
Show more >Un processus ponctuel déterminantal (DPP) génère des configurations aléatoires de points ayant tendance à se repousser. La notion de répulsion est encodée par les sous-déterminants d’une matrice à noyau, au sens des méthodes à noyau en apprentissage artificiel. Cette forme algébrique particulière confère aux DPP de nombreux avantages statistiques et computationnels. Cette thèse porte sur l'échantillonnage des DPP, c'est à dire sur la conception d'algorithmes de simulation pour ce type de processus. Les motivations pratiques sont l'intégration numérique, les systèmes de recommandation ou encore la génération de résumés de grands corpus de données. Dans le cadre fini, nous établissons la correspondance entre la simulation de DPP spécifiques, dits de projection, et la résolution d'un problème d'optimisation linéaire dont les contraintes sont randomisées. Nous en tirons une méthode efficace d'échantillonnage par chaîne de Markov. Dans le cadre continu, certains DPP classiques peuvent être simulés par le calcul des valeurs propres de matrices tridiagonales aléatoires bien choisies. Nous en fournissons une nouvelle preuve élémentaire et unificatrice, dont nous tirons également un échantillonneur approché pour des modèles plus généraux. En dimension supérieure, nous nous concentrons sur une classe de DPP utilisée en intégration numérique. Nous proposons une implémentation efficace d'un schéma d'échantillonnage exact connu, qui nous permet de comparer les propriétés d'estimateurs Monte Carlo dans de nouveaux régimes. En vue d'une recherche reproductible, nous développons une boîte à outils open-source, nommée DPPy, regroupant les différents outils d'échantillonnage sur les DPP.Show less >
Show more >Un processus ponctuel déterminantal (DPP) génère des configurations aléatoires de points ayant tendance à se repousser. La notion de répulsion est encodée par les sous-déterminants d’une matrice à noyau, au sens des méthodes à noyau en apprentissage artificiel. Cette forme algébrique particulière confère aux DPP de nombreux avantages statistiques et computationnels. Cette thèse porte sur l'échantillonnage des DPP, c'est à dire sur la conception d'algorithmes de simulation pour ce type de processus. Les motivations pratiques sont l'intégration numérique, les systèmes de recommandation ou encore la génération de résumés de grands corpus de données. Dans le cadre fini, nous établissons la correspondance entre la simulation de DPP spécifiques, dits de projection, et la résolution d'un problème d'optimisation linéaire dont les contraintes sont randomisées. Nous en tirons une méthode efficace d'échantillonnage par chaîne de Markov. Dans le cadre continu, certains DPP classiques peuvent être simulés par le calcul des valeurs propres de matrices tridiagonales aléatoires bien choisies. Nous en fournissons une nouvelle preuve élémentaire et unificatrice, dont nous tirons également un échantillonneur approché pour des modèles plus généraux. En dimension supérieure, nous nous concentrons sur une classe de DPP utilisée en intégration numérique. Nous proposons une implémentation efficace d'un schéma d'échantillonnage exact connu, qui nous permet de comparer les propriétés d'estimateurs Monte Carlo dans de nouveaux régimes. En vue d'une recherche reproductible, nous développons une boîte à outils open-source, nommée DPPy, regroupant les différents outils d'échantillonnage sur les DPP.Show less >
English abstract : [en]
Determinantal point processes (DPPs) generate random configuration of points where the points tend to repel each other. The notion of repulsion is encoded by the sub-determinants of a kernel matrix, in the sense of kernel ...
Show more >Determinantal point processes (DPPs) generate random configuration of points where the points tend to repel each other. The notion of repulsion is encoded by the sub-determinants of a kernel matrix, in the sense of kernel methods in machine learning. This special algebraic form makes DPPs attractive both in statistical and computational terms. This thesis focuses on sampling from such processes, that is on developing simulation methods for DPPs. Applications include numerical integration, recommender systems or the summarization of a large corpus of data. In the finite setting, we establish the correspondence between sampling from a specific type of DPPs, called projection DPPs, and solving a randomized linear program. In this light, we devise an efficient Markov-chain-based sampling method. In the continuous case, some classical DPPs can be sampled by computing the eigenvalues of carefully randomized tridiagonal matrices. We provide an elementary and unifying treatment of such models, from which we derive an approximate sampling method for more general models. In higher dimension, we consider a special class of DPPs used for numerical integration. We implement a tailored version of a known exact sampler, which allows us to compare the properties of Monte Carlo estimators in new regimes. In the context of reproducible research, we develop an open-source Python toolbox, named DPPy, which implements the state of the art sampling methods for DPPsShow less >
Show more >Determinantal point processes (DPPs) generate random configuration of points where the points tend to repel each other. The notion of repulsion is encoded by the sub-determinants of a kernel matrix, in the sense of kernel methods in machine learning. This special algebraic form makes DPPs attractive both in statistical and computational terms. This thesis focuses on sampling from such processes, that is on developing simulation methods for DPPs. Applications include numerical integration, recommender systems or the summarization of a large corpus of data. In the finite setting, we establish the correspondence between sampling from a specific type of DPPs, called projection DPPs, and solving a randomized linear program. In this light, we devise an efficient Markov-chain-based sampling method. In the continuous case, some classical DPPs can be sampled by computing the eigenvalues of carefully randomized tridiagonal matrices. We provide an elementary and unifying treatment of such models, from which we derive an approximate sampling method for more general models. In higher dimension, we consider a special class of DPPs used for numerical integration. We implement a tailored version of a known exact sampler, which allows us to compare the properties of Monte Carlo estimators in new regimes. In the context of reproducible research, we develop an open-source Python toolbox, named DPPy, which implements the state of the art sampling methods for DPPsShow less >
Language :
Anglais
Collections :
Source :
Files
- https://tel.archives-ouvertes.fr/tel-03132893/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-03132893/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-03132893/document
- Open access
- Access the document
- document
- Open access
- Access the document
- Gautier_Guillaume_DLE.pdf
- Open access
- Access the document