BACH Francis

Nous introduisons l'accélération de Nesterov "continuée", une variante proche de l'accélération de Nesterov dont les variables sont indexées par un paramètre de temps continu. Les deux variables se mélangent continuellement suivant une équation différentielle ordinaire linéaire et prennent des pas de gradient à des moments aléatoires. Cette variante continuée bénéficie du meilleur des cadres continu et discret : en tant que processus continu, on peut utiliser le calcul différentiel pour analyser la convergence et obtenir des expressions analytiques pour les paramètres. Mais une discrétisation du processus continu peut être calculée exactement avec des taux de convergence similaires à ceux de l'accélération originale de Nesterov. Nous montrons que la discrétisation a la même structure que l'accélération de Nesterov, mais avec des paramètres aléatoires.

Machine Learning et intelligence artificielle. Le Machine Learning est l'un des domaines de l'intelligence artificielle qui a pour but de concevoir des programmes qui ne sont pas explicitement codés pour s'acquitter d'une tâche particulière. Les concepts de ce domaine sont fondés sur la logique inférentielle et tentent de dégager des règles générales à partir d'un nombre fini d'observations. Un ouvrage de référence. Cet ouvrage présente les fondements scientifiques de la théorie de l'apprentissage supervisé, les algorithmes les plus répandus développés suivant ce domaine ainsi que les deux cadres de l'apprentissage semi-supervisé et de l'ordonnancement, à un niveau accessible aux étudiants de master et aux élèves ingénieurs. La première édition, connue sous le nom Apprentissage machine, fut traduite en chinois par les éditions iTuring. Dans cette deuxième édition, un nouveau chapitre est dédié au Deep Learning, sur les réseaux de neurones artificiels, et nous avons réorganisé les autres chapitres pour un exposé cohérent reliant la théorie aux algorithmes développés dans cette sphère. Vous trouverez également dans cette édition quelques programmes des algorithmes classiques, écrits en langages Python et C (langages à la fois simples et populaires), et à destination des lecteurs qui souhaitent connaître le fonctionnement de ces modèles désignés parfois comme des boites noires. Ces programmes libres (GPLv3) essentiels au développement de solutions big data sont déposés progressivement sur ce gitlab (https://gricad- gitlab.univ-grenoble-alpes.

Les algorithmes de Frank-Wolfe sont des méthodes d’optimisation de problèmes sous contraintes. Elles décomposent un problème non-linéaire en une série de problèmes linéaires. Cela en fait des méthodes de choix pour l’optimisation en grande dimension et notamment explique leur utilisation dans de nombreux domaines appliqués. Ici nous proposons de nouveaux algorithmes de Frank-Wolfe qui convergent plus rapidement vers la solution du problème d’optimisation sous certaines hypothèses structurelles assez génériques. Nous montrons en particulier, que contrairement à d’autres types d’algorithmes, cette famille s’adapte à ces hypothèses sans avoir à spécifier les paramètres qui les contrôlent.

Les processus ponctuels déterminantaux sont des modèles probabilistes de répulsion. Ces modèles ont été étudié dans différents domaines: les matrices aléatoires, l’optique quantique, les statistiques spatiales, le traitement d’images, l’apprentissage automatique et récemment les quadratures.Dans cette thèse, on étudie l’échantillonnage des sous-espaces à l’aide des processus ponctuels déterminantaux. Ce problème se trouve à l’intersection de trois branches de la théorie d’approximation: la sous sélection dans les ensembles discrets, la quadrature à noyau et l’interpolation à noyau. On étudie ces questions classiques à travers une nouvelle interprétation de ces modèles aléatoires: un processus ponctuel déterminantal est une façon naturelle de définir un sous-espace aléatoire. En plus de donner une analyse unifiée de l’intégration et l’interpolation numériques sous les DPPs, cette nouvelle approche permet de développer les garanties théoriques de plusieurs algorithmes à base de DPPs, et même de prouver leur optimalité pour certains problèmes.

Pas de résumé disponible.

Dans cette thèse, nous examinons plusieurs aspects de l'estimation des paramètres pour les statistiques et les techniques d'apprentissage automatique, aussi que les méthodes d'optimisation applicables à ces problèmes. Le but de l'estimation des paramètres est de trouver les paramètres cachés inconnus qui régissent les données, par exemple les paramètres dont la densité de probabilité est inconnue. La construction d'estimateurs par le biais de problèmes d'optimisation n'est qu'une partie du problème, trouver la valeur optimale du paramètre est souvent un problème d'optimisation qui doit être résolu, en utilisant diverses techniques. Ces problèmes d'optimisation sont souvent convexes pour une large classe de problèmes, et nous pouvons exploiter leur structure pour obtenir des taux de convergence rapides. La première contribution principale de la thèse est de développer des techniques d'appariement de moments pour des problèmes de régression non linéaire multi-index. Nous considérons le problème classique de régression non linéaire, qui est irréalisable dans des dimensions élevées en raison de la malédiction de la dimensionnalité. Nous combinons deux techniques existantes : ADE et SIR pour développer la méthode hybride sans certain des aspects faibles de ses parents. Dans la deuxième contribution principale, nous utilisons un type particulier de calcul de la moyenne pour la descente stochastique du gradient. Nous considérons les familles exponentielles conditionnelles (comme la régression logistique), où l'objectif est de trouver la valeur inconnue du paramètre. Nous proposons le calcul de la moyenne des paramètres de moments, que nous appelons fonctions de prédiction. Pour les modèles à dimensions finies, ce type de calcul de la moyenne peut entraîner une erreur négative, c'est-à-dire que cette approche nous fournit un estimateur meilleur que tout estimateur linéaire ne peut jamais le faire. La troisième contribution principale de cette thèse porte sur les pertes de Fenchel-Young. Nous considérons des classificateurs linéaires multi-classes avec les pertes d'un certain type, de sorte que leur double conjugué a un produit direct de simplices comme support. La formulation convexe-concave à point-selle correspondante a une forme spéciale avec un terme de matrice bilinéaire et les approches classiques souffrent de la multiplication des matrices qui prend beaucoup de temps. Nous montrons que pour les pertes SVM multi-classes avec des techniques d'échantillonnage efficaces, notre approche a une complexité d'itération sous-linéaire, c'est-à-dire que nous devons payer seulement trois fois O(n+d+k) : pour le nombre de classes k, le nombre de caractéristiques d et le nombre d'échantillons n, alors que toutes les techniques existantes sont plus complexes.

Nous présentons un nouvel algorithme pour l'analyse en composantes indépendantes (ICA) surcomplète, où le nombre de sources latentes k dépasse la dimension p des variables observées. Les algorithmes précédents souffrent d'une complexité de calcul élevée ou font des hypothèses fortes sur la forme de la matrice de mélange. Notre algorithme ne fait aucune hypothèse de sparsité et bénéficie pourtant de propriétés informatiques et théoriques favorables. Notre algorithme se compose de deux étapes principales : (a) l'estimation des Hessiens de la fonction génératrice du cumulant (par opposition aux cumulants d'ordre 4 et plus utilisés par la plupart des algorithmes) et (b) une nouvelle relaxation de programmation semi-définie (SDP) pour récupérer une composante de mélange. Nous montrons que cette relaxation peut être résolue efficacement avec une méthode de descente de gradient accélérée projetée, ce qui rend l'algorithme entier pratique sur le plan informatique. De plus, nous conjecturons que le programme proposé récupère une composante de mélange au taux k < p^2/4 et nous prouvons qu'une composante de mélange peut être récupérée avec une probabilité élevée lorsque k < (2 - epsilon) p log p lorsque les composantes originales sont échantillonnées uniformément au hasard sur l'hyper sphère. Des expériences sont fournies sur des données synthétiques et sur le jeu de données CIFAR-10 d'images réelles.

L'analyse en composantes indépendantes (ACI) est une technique d'exploration des données très répandue, où les signaux observés sont modélisés comme des mélanges linéaires de composantes indépendantes. Du point de vue de l'apprentissage automatique, elle revient à un problème de factorisation de matrice avec un critère d'indépendance statistique. Infomax est l'un des algorithmes ICA les plus utilisés. Il est basé sur une fonction de perte qui est une log-vraisemblance non convexe. Nous développons un nouveau cadre de majorisation-minimisation adapté à cette fonction de perte. Nous dérivons un algorithme en ligne pour l'environnement de flux, et un algorithme incrémental pour l'environnement de somme finie, avec les avantages suivants. Premièrement, contrairement à la plupart des algorithmes trouvés dans la littérature, les méthodes proposées ne dépendent pas d'un hyperparamètre critique comme une taille de pas, et ne nécessitent pas de technique de recherche linéaire. Deuxièmement, l'algorithme pour le paramètre de la somme finie, bien que stochastique, garantit une diminution de la fonction de perte à chaque itération. Les expériences démontrent des progrès par rapport à l'état de l'art pour des ensembles de données à grande échelle, sans qu'il soit nécessaire de régler manuellement les paramètres.

Pas de résumé disponible.

" Bonjour Dave, vous avez l'air en forme aujourd'hui ".

Les explosions combinées de la puissance computationnelle et de la quantité de données disponibles ont fait des algorithmes les nouveaux facteurs limitants en machine learning. L’objectif de cette thèse est donc d’introduire de nouvelles méthodes capables de tirer profit de quantités de données et de ressources computationnelles importantes. Nous présentons deux contributions indépendantes. Premièrement, nous développons des algorithmes d’optimisation rapides, adaptés aux avancées en architecture de calcul parallèle pour traiter des quantités massives de données. Nous introduisons un cadre d’analyse pour les algorithmes parallèles asynchrones, qui nous permet de faire des preuves correctes et simples. Nous démontrons son utilité en analysant les propriétés de convergence et d’accélération de deux nouveaux algorithmes. Asaga est une variante parallèle asynchrone et parcimonieuse de Saga, un algorithme à variance réduite qui a un taux de convergence linéaire rapide dans le cas d’un objectif lisse et fortement convexe. Dans les conditions adéquates, Asaga est linéairement plus rapide que Saga, même en l’absence de parcimonie. ProxAsaga est une extension d’Asaga au cas plus général où le terme de régularisation n’est pas lisse. ProxAsaga obtient aussi une accélération linéaire. Nous avons réalisé des expériences approfondies pour comparer nos algorithms à l’état de l’art. Deuxièmement, nous présentons de nouvelles méthodes adaptées à la prédiction structurée. Nous nous concentrons sur les réseaux de neurones récurrents (RNNs), dont l’algorithme d’entraînement traditionnel – basé sur le principe du maximum de vraisemblance (MLE) – présente plusieurs limitations. La fonction de coût associée ignore l’information contenue dans les métriques structurées . de plus, elle entraîne des divergences entre l’entraînement et la prédiction. Nous proposons donc SeaRNN, un nouvel algorithme d’entraînement des RNNs inspiré de l’approche dite “learning to search”. SeaRNN repose sur une exploration de l’espace d’états pour définir des fonctions de coût globales-locales, plus proches de la métrique d’évaluation que l’objectif MLE. Les modèles entraînés avec SeaRNN ont de meilleures performances que ceux appris via MLE pour trois tâches difficiles, dont la traduction automatique. Enfin, nous étudions le comportement de ces modèles et effectuons une comparaison détaillée de notre nouvelle approche aux travaux de recherche connexes.

Les scores de levier statistique sont apparus comme un outil fondamental pour l'esquisse de matrice et l'échantillonnage en colonne, avec des applications à l'approximation de rang bas, à la régression, à l'apprentissage de caractéristiques aléatoires et à la quadrature. Pourtant, la nature même de cette quantité est à peine comprise. En empruntant des idées à la littérature sur les polynômes orthogonaux, nous introduisons la fonction de Christoffel régularisée associée à un noyau défini positif. Cela permet de découvrir une formulation variationnelle des scores de levier pour les méthodes à noyau et d'élucider leurs relations avec le noyau choisi ainsi que la densité de population. Notre résultat principal décrit quantitativement une relation décroissante entre le score de levier et la densité de population pour une large classe de noyaux sur des espaces euclidiens. Des simulations numériques confirment nos résultats.

Les théories de perception des catégories phonétiques interlinguistiques postulent que les auditeurs perçoivent les sons étrangers en les mettant en correspondance avec leurs catégories phonétiques natives, mais, jusqu'à présent, aucun moyen de mettre en œuvre efficacement cette mise en correspondance n'a été proposé. Dans cet article, des systèmes de reconnaissance automatique de la parole entraînés sur des corpus de parole continus sont utilisés pour fournir une correspondance entièrement spécifiée entre les sons étrangers et les catégories natives. Les auteurs montrent comment la méthode d'évaluation machine ABX peut être utilisée pour comparer les prédictions des modèles quantitatifs résultants avec les effets empiriquement attestés dans la perception humaine des catégories phonétiques interlinguistiques.

Dans de nombreux domaines, comme par exemple l’optimisation, la performance d’une méthode est souvent caractérisée par son taux de convergence. Cependant, accélérer un algorithme requiert une certaine connaissance de la structure du problème et de telles améliorations sont le fruit d’une étude au cas-par-cas. De nombreuses techniques d’accélération ont été développées ces dernières décennies et sont maintenant massivement utilisées. En dépit de leur simplicité, ces méthodes sont souvent basées sur des arguments purement algébriques et n’ont généralement pas d’explications intuitives. Récemment, de nombreux travaux ont été menés pour faire des liens entre les algorithmes accélérés et d’autres domaines scientifiques, comme par exemple avec la théorie du contrôle ou des équations différentielles. Cependant, ces explications reposent souvent sur des arguments complexes et la plupart utilisent des outils non-conventionnels dans leur analyse. Une des contributions de cette thèse est une tentative d’explication des algorithmes accélérés en utilisant la théorie des méthodes d’intégration, qui a été très étudiée et jouit d’une analyse théorique solide. En particulier, nous montrons que les méthodes d’optimisation sont en réalité des instances de méthode d’intégration, lorsqu’on intègre l’équation du flot de gradient. Avec des arguments standards, nous expliquons intuitivement l’origine de l’accélération. De l’autre côté, les méthodes accélérées ont besoin de paramètres supplémentaires, en comparaison d’autres méthodes plus lentes, qui sont généralement difficiles à estimer. De plus, ces schémas sont construits pour une configuration particulière et ne peuvent pas être utilisés autre part. Ici, nous explorons une autre approche pour accélérer les algorithmes d’optimisation, qui utilise des arguments d’accélération générique. En analyse numérique, ces outils ont été développés pour accélérer des séquences de scalaires ou de vecteurs, en construisant parallèlement une autre séquence avec un meilleur taux de convergence. Ces méthodes peuvent être combinées avec un algorithme itératif, l’accélérant dans la plupart des cas. En pratique, ces méthodes d’extrapolation ne sont pas tellement utilisées, notamment dû à leur manque de garanties de convergence et leur instabilité. Nous étendons ces méthodes en les régularisant, ce qui permettra une analyse théorique plus profonde et des résultats de convergence plus fort, en particulier lorsqu’elles sont appliquées à des méthodes d’optimisation.

Nous considérons la minimisation d'une fonction objective en ayant accès à des estimations non biaisées de son gradient par la descente de gradient stochastique (SGD) avec une taille de pas constante. Bien que l'analyse détaillée n'ait été effectuée que pour des fonctions quadratiques, nous fournissons une expansion asymptotique explicite des moments des itérations SGD moyennées qui souligne la dépendance aux conditions initiales, l'effet du bruit et de la taille du pas, ainsi que l'absence de convergence dans le cas général (non quadratique). Pour cette analyse, nous introduisons des outils issus de la théorie des chaînes de Markov dans l'analyse du gradient stochastique. Nous montrons ensuite que l'extrapolation de Richardson-Romberg peut être utilisée pour se rapprocher de l'optimum global et nous montrons les améliorations empiriques du nouveau schéma d'extrapolation.

Nous considérons la minimisation d'une fonction définie sur un collecteur riemannien $\mathcal{M}$ accessible uniquement par des estimations non biaisées de ses gradients. Nous développons un cadre géométrique pour transformer une séquence d'itérations à convergence lente générée par la descente de gradient stochastique (SGD) sur $\mathcal{M}$ en une séquence d'itérations moyennées avec un taux de convergence robuste et rapide de $O(1/n)$. Nous présentons ensuite une application de notre cadre à des problèmes géodésiquement fortement convexes (et éventuellement non convexes euclidiens). Enfin, nous démontrons comment ces idées s'appliquent au cas de l'ACP à k$ en continu, où nous montrons comment accélérer le taux lent de la méthode de puissance aléatoire (sans exiger la connaissance de l'eigengap) en un algorithme robuste atteignant le taux de convergence optimal.

Pas de résumé disponible.

Nous montrons que les méthodes d'optimisation accélérée peuvent être considérées comme des instances particulières des schémas d'intégration multi-étapes de l'analyse numérique, appliquées à l'équation du flux de gradient. Par rapport aux avancées récentes dans ce domaine, l'équation différentielle considérée ici est l'écoulement de gradient de base et nous montrons que les schémas multi-étapes permettent l'intégration de cette équation différentielle en utilisant des tailles d'étapes plus grandes, expliquant ainsi intuitivement les résultats d'accélération.

Nous fournissons de nouvelles perspectives théoriques sur la prédiction structurée dans le contexte de la minimisation efficace de la perte de substitution convexe avec des garanties de cohérence. Pour toute perte de tâche, nous construisons un substitut convexe qui peut être optimisé par descente de gradient stochastique et nous prouvons des limites étroites sur la "fonction de calibration" qui relie le risque excédentaire du substitut au risque réel. Contrairement aux travaux antérieurs, nous contrôlons soigneusement l'effet du nombre exponentiel de classes sur les garanties d'apprentissage ainsi que sur la complexité de l'optimisation. Comme conséquence intéressante, nous formalisons l'intuition que certaines pertes de tâches rendent l'apprentissage plus difficile que d'autres, et que la perte 0-1 classique est mal adaptée à la prédiction structurée.

Le but de l’apprentissage supervisé est d’inférer des relations entre un phénomène que l’on souhaite prédire et des variables « explicatives ». À cette fin, on dispose d’observations de multiples réalisations du phénomène, à partir desquelles on propose une règle de prédiction. L’émergence récente de sources de données à très grande échelle, tant par le nombre d’observations effectuées (en analyse d’image, par exemple) que par le grand nombre de variables explicatives (en génétique), a fait émerger deux difficultés : d’une part, il devient difficile d’éviter l’écueil du sur-apprentissage lorsque le nombre de variables explicatives est très supérieur au nombre d’observations. d’autre part, l’aspect algorithmique devient déterminant, car la seule résolution d’un système linéaire dans les espaces en jeupeut devenir une difficulté majeure. Des algorithmes issus des méthodes d’approximation stochastique proposent uneréponse simultanée à ces deux difficultés : l’utilisation d’une méthode stochastique réduit drastiquement le coût algorithmique, sans dégrader la qualité de la règle de prédiction proposée, en évitant naturellement le sur-apprentissage. En particulier, le cœur de cette thèse portera sur les méthodes de gradient stochastique. Les très populaires méthodes paramétriques proposent comme prédictions des fonctions linéaires d’un ensemble choisi de variables explicatives. Cependant, ces méthodes aboutissent souvent à une approximation imprécise de la structure statistique sous-jacente. Dans le cadre non-paramétrique, qui est un des thèmes centraux de cette thèse, la restriction aux prédicteurs linéaires est levée. La classe de fonctions dans laquelle le prédicteur est construit dépend elle-même des observations. En pratique, les méthodes non-paramétriques sont cruciales pour diverses applications, en particulier pour l’analyse de données non vectorielles, qui peuvent être associées à un vecteur dans un espace fonctionnel via l’utilisation d’un noyau défini positif. Cela autorise l’utilisation d’algorithmes associés à des données vectorielles, mais exige une compréhension de ces algorithmes dans l’espace non-paramétrique associé : l’espace à noyau reproduisant. Par ailleurs, l’analyse de l’estimation non-paramétrique fournit également un éclairage révélateur sur le cadre paramétrique, lorsque le nombre de prédicteurs surpasse largement le nombre d’observations. La première contribution de cette thèse consiste en une analyse détaillée de l’approximation stochastique dans le cadre non-paramétrique, en particulier dans le cadre des espaces à noyaux reproduisants. Cette analyse permet d’obtenir des taux de convergence optimaux pour l’algorithme de descente de gradient stochastique moyennée. L’analyse proposée s’applique à de nombreux cadres, et une attention particulière est portée à l’utilisation d’hypothèses minimales, ainsi qu’à l’étude des cadres où le nombre d’observations est connu à l’avance, ou peut évoluer. La seconde contribution est de proposer un algorithme, basé sur un principe d’accélération, qui converge à une vitesse optimale, tant du point de vue de l’optimisation que du point de vue statistique. Cela permet, dans le cadre non-paramétrique, d’améliorer la convergence jusqu’au taux optimal, dans certains régimes pour lesquels le premier algorithme analysé restait sous-optimal. Enfin, la troisième contribution de la thèse consiste en l’extension du cadre étudié au delà de la perte des moindres carrés : l’algorithme de descente de gradient stochastiqueest analysé comme une chaine de Markov. Cette approche résulte en une interprétation intuitive, et souligne les différences entre le cadre quadratique et le cadre général. Une méthode simple permettant d’améliorer substantiellement la convergence est également proposée.

Pas de résumé disponible.

Nous considérons l'optimisation d'une fonction objectif quadratique dont les gradients ne sont accessibles qu'à travers un oracle stochastique qui renvoie le gradient à tout point donné plus une erreur aléatoire de variance finie de moyenne nulle. Nous présentons le premier algorithme qui atteint conjointement les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, à la fois en termes d'oubli des conditions initiales en O(1/n 2), et en termes de dépendance au bruit et à la dimension d du problème, en O(d/n). Notre nouvel algorithme est basé sur la descente de gradient régularisée accélérée moyenne, et peut également être analysé par des hypothèses plus fines sur les conditions initiales et la matrice hessienne, conduisant à des quantités sans dimension qui peuvent encore être petites alors que les termes " optimaux " ci-dessus sont grands. Afin de caractériser l'étanchéité de ces nouvelles limites, nous considérons une application à la régression non paramétrique et utilisons les limites inférieures connues de la performance statistique (sans limites de calcul), qui correspondent à nos limites obtenues à partir d'un seul passage sur les données et montrent ainsi l'optimalité de notre algorithme dans une grande variété de compromis particuliers entre le biais et la variance.

Pas de résumé disponible.

Le problème de représentation d’image est au cœur du domaine de vision. Le choix de représentation d’une image change en fonction de la tâche que nous voulons étudier. Un problème de recherche d’image dans des grandes bases de données exige une représentation globale compressée, alors qu’un problème de segmentation sémantique nécessite une carte de partitionnement de ses pixels. Les techniques d’apprentissage statistique sont l’outil principal pour la construction de ces représentations. Dans ce manuscrit, nous abordons l’apprentissage des représentations visuels dans trois problèmes différents : la recherche d’image, la correspondance sémantique et classification d’image. Premièrement, nous étudions la représentation vectorielle de Fisher et sa dépendance sur le modèle de mélange Gaussien employé. Nous introduisons l’utilisation de plusieurs modèles de mélange Gaussien pour différents types d’arrière-plans, e.g., différentes catégories de scènes, et analyser la performance de ces représentations pour objet classification et l’impact de la catégorie de scène en tant que variable latente. Notre seconde approche propose une extension de la représentation l’exemple SVM pipeline. Nous montrons d’abord que, en remplaçant la fonction de perte de la SVM par la perte carrée, on obtient des résultats similaires à une fraction de le coût de calcul. Nous appelons ce modèle la « square-loss exemplar machine », ou SLEM en anglais. Nous introduisons une variante de SLEM à noyaux qui bénéficie des même avantages computationnelles mais affiche des performances améliorées. Nous présentons des expériences qui établissent la performance et l’efficacité de nos méthodes en utilisant une grande variété de représentations de base et de jeux de données de recherche d’images. Enfin, nous proposons un réseau neuronal profond pour le problème de l’établissement sémantique correspondance. Nous utilisons des boîtes d’objets en tant qu’éléments de correspondance pour construire une architecture qui apprend simultanément l’apparence et la cohérence géométrique. Nous proposons de nouveaux scores géométriques de cohérence adaptés à l’architecture du réseau de neurones. Notre modèle est entrainé sur des paires d’images obtenues à partir des points-clés d’un jeu de données de référence et évaluées sur plusieurs ensembles de données, surpassant les architectures d’apprentissage en profondeur récentes et méthodes antérieures basées sur des caractéristiques artisanales. Nous terminons la thèse en soulignant nos contributions et en suggérant d’éventuelles directions de recherche futures.

De multiples problèmes en apprentissage automatique consistent à minimiser une fonction lisse sur un espace euclidien. Pour l’apprentissage supervisé, cela inclut les régressions par moindres carrés et logistique. Si les problèmes de petite taille sont résolus efficacement avec de nombreux algorithmes d’optimisation, les problèmes de grande échelle nécessitent en revanche des méthodes du premier ordre issues de la descente de gradient. Dans ce manuscrit, nous considérons le cas particulier de la perte quadratique. Dans une première partie, nous nous proposons de la minimiser grâce à un oracle stochastique. Dans une seconde partie, nous considérons deux de ses applications à l’apprentissage automatique : au partitionnement de données et à l’estimation sous contrainte de forme. La première contribution est un cadre unifié pour l’optimisation de fonctions quadratiques non-fortement convexes. Celui-ci comprend la descente de gradient accélérée et la descente de gradient moyennée. Ce nouveau cadre suggère un algorithme alternatif qui combine les aspects positifs du moyennage et de l’accélération. La deuxième contribution est d’obtenir le taux optimal d’erreur de prédiction pour la régression par moindres carrés en fonction de la dépendance au bruit du problème et à l’oubli des conditions initiales. Notre nouvel algorithme est issu de la descente de gradient accélérée et moyennée. La troisième contribution traite de la minimisation de fonctions composites, somme de l’espérance de fonctions quadratiques et d’une régularisation convexe. Nous étendons les résultats existants pour les moindres carrés à toute régularisation et aux différentes géométries induites par une divergence de Bregman. Dans une quatrième contribution, nous considérons le problème du partitionnement discriminatif. Nous proposons sa première analyse théorique, une extension parcimonieuse, son extension au cas multi-labels et un nouvel algorithme ayant une meilleure complexité que les méthodes existantes. La dernière contribution de cette thèse considère le problème de la sériation. Nous adoptons une approche statistique où la matrice est observée avec du bruit et nous étudions les taux d’estimation minimax. Nous proposons aussi un estimateur computationellement efficace.

La plupart des systèmes de recommandation actuels se base sur des évaluations sous forme de notes (i.e., chiffre entre 0 et 5) pour conseiller un contenu (film, restaurant.) à un utilisateur. Ce dernier a souvent la possibilité de commenter ce contenu sous forme de texte en plus de l'évaluer. Il est difficile d'extraire de l'information d'un texte brut tandis qu'une simple note contient peu d'information sur le contenu et l'utilisateur. Dans cette thèse, nous tentons de suggérer à l'utilisateur un texte lisible personnalisé pour l'aider à se faire rapidement une opinion à propos d'un contenu. Plus spécifiquement, nous construisons d'abord un modèle thématique prédisant une description de film personnalisée à partir de commentaires textuels. Notre modèle sépare les thèmes qualitatifs (i.e., véhiculant une opinion) des thèmes descriptifs en combinant des commentaires textuels et des notes sous forme de nombres dans un modèle probabiliste joint. Nous évaluons notre modèle sur une base de données IMDB et illustrons ses performances à travers la comparaison de thèmes. Nous étudions ensuite l'inférence de paramètres dans des modèles à variables latentes à grande échelle, incluant la plupart des modèles thématiques. Nous proposons un traitement unifié de l'inférence en ligne pour les modèles à variables latentes à partir de familles exponentielles non-canoniques et faisons explicitement apparaître les liens existants entre plusieurs méthodes fréquentistes et Bayesiennes proposées auparavant. Nous proposons aussi une nouvelle méthode d'inférence pour l'estimation fréquentiste des paramètres qui adapte les méthodes MCMC à l'inférence en ligne des modèles à variables latentes en utilisant proprement un échantillonnage de Gibbs local. Pour le modèle thématique d'allocation de Dirichlet latente, nous fournissons une vaste série d'expériences et de comparaisons avec des travaux existants dans laquelle notre nouvelle approche est plus performante que les méthodes proposées auparavant. Enfin, nous proposons une nouvelle classe de processus ponctuels déterminantaux (PPD) qui peut être manipulée pour l'inférence et l'apprentissage de paramètres en un temps potentiellement sous-linéaire en le nombre d'objets. Cette classe, basée sur une factorisation spécifique de faible rang du noyau marginal, est particulièrement adaptée à une sous-classe de PPD continus et de PPD définis sur un nombre exponentiel d'objets. Nous appliquons cette classe à la modélisation de documents textuels comme échantillons d'un PPD sur les phrases et proposons une formulation du maximum de vraisemblance conditionnel pour modéliser les proportions de thèmes, ce qui est rendu possible sans aucune approximation avec notre classe de PPD. Nous présentons une application à la synthèse de documents avec un PPD sur 2 à la puissance 500 objets, où les résumés sont composés de phrases lisibles.

Nous cherchons à regrouper les caractéristiques dans les problèmes d'apprentissage supervisé en contraignant les coefficients du vecteur de prédiction à ne prendre qu'un petit nombre de valeurs. Ce problème inclut des contraintes non convexes et est résolu en utilisant la descente de gradient projetée. Nous prouvons des résultats de récupération exacts en utilisant des conditions de valeurs propres restreintes. Nous étendons ensuite ces résultats pour combiner les contraintes d'éparpillement et de regroupement, et nous développons un algorithme de projection efficace sur l'ensemble des vecteurs regroupés et épars. Des expériences numériques illustrent les performances de nos algorithmes sur des ensembles de données synthétiques et réelles.

La mise en grappes de données à haute dimension nécessite souvent une certaine forme de réduction de la dimensionnalité, où les variables mises en grappes sont séparées des variables " bruyantes ". Ce problème consiste à trouver une projection à faible dimension des données qui sont bien groupées. Cela donne une projection unidimensionnelle dans la situation la plus simple avec deux clusters, et s'étend naturellement à un scénario multi-label pour plus de deux clusters. Dans cet article, (a) nous montrons d'abord que cette formulation conjointe de clustering et de réduction de dimension est équivalente aux cadres de clustering discriminatif proposés précédemment, ce qui conduit à des relaxations convexes du problème. (b) Nous proposons une nouvelle extension éparse, qui reste une relaxation convexe et permet l'estimation dans des dimensions supérieures. (c) Nous proposons une extension naturelle pour le scénario multi-labels. (d) nous fournissons une nouvelle analyse théorique de la performance de ces formulations avec un modèle probabiliste simple, conduisant à des mises à l'échelle de la forme d = O(√ n) pour le cas affine invariant et d = O(n) pour le cas clairsemé, où n est le nombre d'exemples et d la dimension ambiante. et enfin, (e) nous proposons un algorithme itératif efficace avec une complexité de temps d'exécution proportionnelle à O(nd 2), améliorant les algorithmes précédents qui avaient une complexité quadratique dans le nombre d'exemples.

De nombreux modèles de régression ordinale qui ont été proposés dans la littérature peuvent être considérés comme des méthodes qui minimisent une substitution convexe des fonctions de perte nulle, absolue ou au carré. Une propriété clé qui permet d'étudier les implications statistiques de telles approximations est celle de la cohérence de Fisher. La cohérence de Fisher est une propriété souhaitable pour les fonctions de perte de substitution et implique que dans le cadre d'une population, c'est-à-dire si la distribution de probabilité qui génère les données était disponible, l'optimisation de la substitution donnerait le meilleur modèle possible. Dans cet article, nous caractérisons la cohérence de Fisher d'une riche famille de fonctions de perte de substitution utilisées dans le contexte de la régression ordinale, y compris la régression ordinale à vecteur de support, l'ORBoosting et la moindre déviation absolue. Nous verrons que, pour une famille de fonctions de perte de substitution qui subsume la régression ordinale à vecteur de support et l'ORBoosting, la cohérence peut être entièrement caractérisée par la dérivée d'une fonction à valeur réelle à zéro, comme cela se produit pour les fonctions de substitution convexes basées sur la marge dans la classification binaire. Nous dérivons également des limites de risque excessif pour un substitut de l'erreur absolue qui généralisent les limites de risque existantes pour la classification binaire. Enfin, notre analyse suggère un nouveau substitut de la perte par erreur quadratique. Nous comparons ce nouveau substitut avec des approches concurrentes sur 9 jeux de données différents. Notre méthode s'avère très compétitive en pratique, surpassant la perte des moindres carrés sur 7 des 9 jeux de données.

Nous étudions l'inférence des paramètres dans les modèles à variables latentes à grande échelle. Nous proposons d'abord un traitement unifié de l'inférence en ligne pour les modèles à variables latentes d'une famille exponentielle non canonique, et établissons des liens explicites entre plusieurs méthodes fréquentistes ou bayésiennes proposées précédemment. Nous proposons ensuite une nouvelle méthode d'inférence pour l'estimation fréquentiste des paramètres, qui adapte les méthodes MCMC à l'inférence en ligne des modèles à variables latentes avec l'utilisation appropriée de l'échantillonnage local de Gibbs. Ensuite, pour l'allocation latente Dirich-let, nous fournissons un ensemble étendu d'expériences et de comparaisons avec les travaux existants, où notre nouvelle approche surpasse toutes les méthodes proposées précédemment. En particulier, l'utilisation de l'échantillonnage de Gibbs pour l'inférence des variables latentes est supérieure à l'inférence variationnelle en termes de log-vraisemblance de test. De plus, l'inférence bayésienne par des méthodes variationnelles donne de mauvais résultats, conduisant parfois à de moins bons ajustements avec des variables latentes de plus grande dimension.

Nous considérons l'optimisation d'une fonction objectif quadratique dont les gradients ne sont accessibles qu'à travers un oracle stochastique qui renvoie le gradient à tout point donné plus une erreur aléatoire de variance finie de moyenne nulle. Nous présentons le premier algorithme qui atteint conjointement les taux d'erreur de prédiction optimaux pour la régression des moindres carrés, à la fois en termes d'oubli des conditions initiales en O(1/n 2), et en termes de dépendance au bruit et à la dimension d du problème, en O(d/n). Notre nouvel algorithme est basé sur la descente de gradient régularisée accélérée moyenne, et peut également être analysé par des hypothèses plus fines sur les conditions initiales et la matrice hessienne, conduisant à des quantités sans dimension qui peuvent encore être petites alors que les termes " optimaux " ci-dessus sont grands. Afin de caractériser l'étanchéité de ces nouvelles limites, nous considérons une application à la régression non paramétrique et utilisons les limites inférieures connues de la performance statistique (sans limites de calcul), qui correspondent à nos limites obtenues à partir d'un seul passage sur les données et montrent ainsi l'optimalité de notre algorithme dans une grande variété de compromis particuliers entre le biais et la variance.

Zepeda et Pérez ont récemment démontré la promesse du SVM exemplaire (ESVM) comme codeur de caractéristiques pour la recherche d'images. Cet article étend cette approche dans plusieurs directions : Nous montrons d'abord que le remplacement de la perte de charnière par la perte carrée dans la fonction de coût de l'ESVM réduit considérablement le temps d'encodage avec un effet négligeable sur la précision. Nous appelons ce modèle machine exemplaire à perte carrée, ou SLEM. Nous présentons ensuite un SLEM à noyau qui peut être mis en œuvre efficacement par la décomposition de matrices à faible rang, et qui affiche de meilleures performances. Les deux variantes de SLEM exploitent le fait que les exemples négatifs sont fixes, de sorte que la majeure partie de la complexité informatique de SLEM est reléguée à un processus hors ligne indépendant des exemples positifs. Nos expériences établissent les performances et les avantages informatiques de notre approche en utilisant un large éventail de caractéristiques de base et des ensembles de données standard de recherche d'images.

Dans cet article, nous proposons une théorie unifiée pour les normes convexes structurées induisant la sparsité sur des vecteurs associés à des fonctions de pénalité combinatoires. Plus précisément, nous considérons la situation d'un modèle simultanément (a) pénalisé par une fonction d'ensemble définie sur le support du vecteur paramètre inconnu qui représente la connaissance préalable sur les supports, et (b) régularisé en p-norme. Nous montrons que chacun des problèmes d'optimisation combinatoire obtenus admet une relaxation naturelle en tant que problème d'optimisation régularisé par une norme correspondante induisant la sparsité. Pour caractériser l'étanchéité de la relaxation, nous introduisons une notion d'enveloppe combinatoire inférieure d'une fonction-ensemble. Symétriquement, une notion d'enveloppe combinatoire supérieure produit l'expression de norme la plus concise. Nous montrons que ces relaxations prennent la forme de Lassos de groupes latents combinatoires associés à des pénalités à couverture minimale, également connues sous le nom de schémas de codage par blocs. Pour les fonctions de pénalité submodulaires, la norme associée, la norme duale et l'opérateur proximal correspondant peuvent être calculés efficacement à l'aide d'un algorithme générique de type diviser pour régner. Notre cadre obtient des dérivations constructives pour le Lasso, le Lasso de groupe, le Lasso exclusif, les pénalités OWL, OSCAR et SLOPE, la norme k-support, plusieurs pénalités hiérarchiques considérées dans la littérature pour les chaînes et les structures arborescentes, et produit également de nouvelles normes. Elle conduit à des algorithmes généraux efficaces pour toutes ces normes, récupérant comme cas particuliers plusieurs algorithmes proposés dans la littérature et produisant des procédures améliorées pour certains cas. Pour les normes associées à des pénalités submodulaires, y compris un grand nombre de normes non-décomposables, nous généralisons les résultats classiques de récupération de support et de convergence rapide basés respectivement sur la généralisation de la condition d'irreprésentabilité et de la condition de valeur propre restreinte.

Nous introduisons trois nouvelles extensions semi-paramétriques de l'analyse de corrélation canonique probabiliste avec des garanties d'identifiabilité. Nous considérons des techniques d'appariement de moments pour l'estimation dans ces modèles. Pour cela, en établissant des liens explicites entre les nouveaux modèles et une version discrète de l'analyse en composantes indépendantes (DICA), nous étendons d'abord les tenseurs cumulants de la DICA à la nouvelle version discrète de l'ACC. En utilisant ensuite un lien étroit avec l'analyse en composantes indépendantes, nous introduisons des matrices de covariance généralisées, qui peuvent remplacer les tenseurs cumulants dans le cadre de l'appariement des moments et, par conséquent, améliorer la complexité de l'échantillon et simplifier considérablement les dérivations et les algorithmes. Comme la méthode de puissance des tenseurs ou la diagonalisation conjointe orthogonale ne sont pas applicables dans ce nouveau cadre, nous utilisons des techniques de diagonalisation conjointe non orthogonale pour l'appariement des cumulants. Nous démontrons la performance des modèles et des techniques d'estimation proposés lors d'expériences avec des ensembles de données synthétiques et réelles.

Nous proposons une nouvelle classe de processus ponctuels déterminants (DPPs) qui peuvent être manipulés pour l'inférence et l'apprentissage de paramètres en un temps potentiellement sublinéaire dans le nombre d'items. Cette classe, basée sur une factorisation spécifique de bas rang du noyau marginal, est particulièrement adaptée à une sous-classe de DPPs continus et de DPPs définis sur un nombre exponentiel d'items. Nous appliquons cette nouvelle classe à la modélisation de documents textuels comme échantillonnage d'un DPP de phrases, et nous proposons une formulation de maximum de vraisemblance conditionnelle pour modéliser les proportions de sujets, ce qui est possible sans approximation pour notre classe de DPP. Nous présentons une application au résumé de documents avec un DPP sur $2^{500}$ items.

La modélisation de processus complexes peut impliquer un grand nombre de variables ayant entre elles une structure de corrélation compliquée. Par exemple, les phénomènes spatiaux possèdent souvent une forte régularité spatiale, se traduisant par une corrélation entre variables d’autant plus forte que les régions correspondantes sont proches. Le formalisme des graphes pondérés permet de capturer de manière compacte ces relations entre variables, autorisant la formalisation mathématique de nombreux problèmes d’analyse de données spatiales. La première partie du manuscrit se concentre sur la résolution efficace de problèmes de régularisation spatiale, mettant en jeu des pénalités telle que la variation totale ou la longueur totale des contours. Nous présentons une stratégie de préconditionnement pour l’algorithme generalized forward-backward, spécifiquement adaptée à la résolution de problèmes structurés par des graphes pondérés présentant une grande variabilité de configurations et de poids. Nous présentons ensuite un nouvel algorithme appelé cut pursuit, qui exploite les relations entre les algorithmes de flots et la variation totale au travers d’une stratégie de working set. Ces algorithmes présentent des performances supérieures à l’état de l’art pour des tâches d’agrégations de données geostatistiques. La seconde partie de ce document se concentre sur le développement d’un nouveau modèle qui étend les chaînes de Markov à temps continu au cas des graphes pondérés non orientés généraux. Ce modèle autorise la prise en compte plus fine des interactions entre noeuds voisins pour la prédiction structurée, comme illustré pour la classification supervisée de tissus urbains.

Pas de résumé disponible.

Cette thèse est, au départ, une contribution indirecte au problème de la modélisation de l'acquisition des catégories phonétiques chez l'enfant. Les modèles computationnels déjà proposés n'ont encore jamais été testés de manière systématique pour déterminer s'ils sont réellement à même de rendre compte d'une partie conséquente des observations empiriques disponibles. Nous développons une approche permettant une évaluation systématique des modèles sur la base de Mesures de Discriminabilité ABX. Nous montrons l'intérêt de notre approche en l'appliquant à deux problèmes reliés: la traitement des catégories phonétiques à la naissance et à l'âge adulte. La prochaine étape sera bien sûr d'appliquer notre approche aux modèles d'acquisition des catégories phonétiques.L'intérêt des Mesures de Discriminabilité ABX ne se restreint pas au cas particulier de l'évaluation des modèles de traitement des catégories phonétiques. Elle sont utiles dans l'étude de signaux autre que la parole et de catégories autres que les catégories phonétiques, ainsi que dans le cadre de champs disciplinaires autres que les sciences cognitives, comme l'ingénierie, l'exploration des données ou l'intelligence artificielle par exemple. Nous le justifions en étudiant les propriétés de ces mesures dans un cadre abstrait général et en présentant trois grandes familles d'applications: l'évaluation de la capacité de systèmes opérant en l'absence de supervision explicite à représenter une structure catégorielle. la formulation de modèles computationnels simples du comportement dans des tâches de discrimination. la définition de mesures descriptives pour des représentations associées à des données catégorielles.

Dans cet article, nous considérons une nouvelle approche discriminante du problème de l'alignement audio vers la partition. Nous considérons les deux informations distinctes fournies par les partitions musicales : (i) une liste ordonnée exacte des événements musicaux et (ii) une information préalable approximative sur la durée relative des événements. Nous étendons l'algorithme de base de déformation temporelle dynamique à un problème convexe qui apprend des classificateurs optimaux pour tous les événements tout en alignant conjointement les fichiers, en utilisant uniquement cette supervision faible. Nous montrons que la durée relative entre les événements peut être facilement utilisée comme une pénalisation de notre fonction de coût et nous permet d'améliorer considérablement les performances de notre approche. Nous démontrons la validité de notre approche sur un jeu de données large et réaliste.

Dans cet article, nous considérons une nouvelle approche discriminante du problème de l'alignement audio vers la partition. Nous considérons les deux informations distinctes fournies par les partitions musicales : (i) une liste ordonnée exacte des événements musicaux et (ii) une information préalable approximative sur la durée relative des événements. Nous étendons l'algorithme de base de déformation temporelle dynamique à un problème convexe qui apprend des classificateurs optimaux pour tous les événements tout en alignant conjointement les fichiers, en utilisant uniquement cette supervision faible. Nous montrons que la durée relative entre les événements peut être facilement utilisée comme une pénalisation de notre fonction de coût et nous permet d'améliorer considérablement les performances de notre approche. Nous démontrons la validité de notre approche sur un jeu de données large et réaliste.

Nous montrons un lien fort entre les limites de risque PAC-Bayesiennes fréquentistes et la vraisemblance marginale bayésienne. En d'autres termes, pour la fonction de perte de log-vraisemblance négative, nous montrons que la minimisation des limites de risque de généralisation PAC-Bayes maximise la vraisemblance marginale bayésienne. Ceci fournit une explication alternative au critère bayésien du rasoir d'Occam, sous l'hypothèse que les données sont générées par un modèle i.i. (i.i.).

Nous étudions un problème de regroupement supervisé qui cherche à regrouper soit des caractéristiques, soit des tâches, soit des points d'échantillonnage en utilisant des pertes extraites de problèmes d'apprentissage supervisé. Nous formulons un problème d'optimisation unifié gérant ces trois paramètres et dérivons des algorithmes dont la complexité d'itération principale est concentrée dans une étape de clustering k-means, qui peut être approximée efficacement. Nous testons nos méthodes sur des ensembles de données artificielles et réalistes extraites de critiques de films et de 20NewsGroup.

Pas de résumé disponible.

Pas de résumé disponible.

Pas de résumé disponible.

Les services de streaming tels que Netflix, M-Go et Hulu utilisent des systèmes de recommandation avancés pour aider leurs clients à identifier rapidement et facilement les contenus pertinents. Ces systèmes de recommandation affichent la liste des films recommandés organisée en sous-listes étiquetées avec le genre ou des étiquettes plus spécifiques. Malheureusement, les méthodes existantes pour extraire ces sous-listes étiquetées nécessitent des annotateurs humains pour étiqueter manuellement les films, ce qui prend du temps et est biaisé par les opinions des annotateurs. Dans cet article, nous concevons une méthode qui s'appuie sur les critiques de la foule pour identifier automatiquement des groupes de films similaires et étiqueter ces groupes. Notre méthode utilise le contenu des critiques de films disponibles en ligne comme entrée pour un algorithme basé sur l'allocation de Dirichlet latente (LDA) qui identifie les groupes de films similaires. Nous séparons l'ensemble des films similaires qui partagent la même combinaison de genres en sous-listes et personnalisons les films à montrer dans chaque sous-liste en utilisant la factorisation matricielle. Les résultats d'une comparaison côte à côte de notre méthode avec le service de VoD M-Go de Technicolor sont encourageants.

Nous considérons le problème de la régression des moindres carrés à conception aléatoire dans le cadre de l'espace de Hilbert à noyau reproducteur (RKHS). Étant donné un flux de données d'entrée/sortie indépendantes et identiquement distribuées, nous cherchons à apprendre une fonction de régression dans un RKHS $\mathcal{H}$, même si le prédicteur optimal (c'est-à-dire l'espérance conditionnelle) n'est pas dans $\mathcal{H}$. Dans un cadre d'approximation stochastique où l'estimateur est mis à jour après chaque observation, nous montrons que l'algorithme des moindres carrés moyens non régularisés (une forme de gradient stochastique), compte tenu d'une taille de pas suffisamment grande, atteint des taux de convergence optimaux pour une variété de régimes pour les lissages de la fonction de prédiction optimale et des fonctions dans $\mathcal{H}$.

De nombreux outils modernes d'apprentissage automatique et de traitement du signal, tels que l'apprentissage par dictionnaire clairsemé, l'analyse en composantes principales (ACP), la factorisation de matrices non négatives (NMF), le clustering $K$-means, etc., reposent sur la factorisation d'une matrice obtenue en concaténant des vecteurs de haute dimension provenant d'une collection d'apprentissage. Alors que la tâche idéalisée serait d'optimiser la qualité attendue des facteurs sur la distribution sous-jacente des vecteurs d'entraînement, elle est réalisée en pratique en minimisant une moyenne empirique sur la collection considérée. L'objectif de cet article est de fournir des estimations de la complexité de l'échantillon afin de contrôler uniformément la déviation de la moyenne empirique par rapport à la fonction de coût attendue. Des arguments standard impliquent que les performances du prédicteur empirique présentent également de telles garanties. Le niveau de généricité de l'approche englobe plusieurs contraintes possibles sur les facteurs (structure de produit tensoriel, shift-invariance, sparsité \ldots), fournissant ainsi une perspective unifiée sur la complexité d'échantillon de plusieurs schémas de factorisation de matrice largement utilisés. Les limites de généralisation dérivées se comportent de manière proportionnelle à $\sqrt{\log(n)/n}$ par rapport au nombre d'échantillons $n$ pour les techniques de factorisation matricielle considérées.

Dans cette thèse nous nous intéressons à des problèmes d’apprentissage automatique dans le cadre de sorties structurées avec une structure séquentielle. D’une part, nous considérons le problème de l’apprentissage de mesure de similarité pour deux tâches : (i) la détection de rupture dans des signaux multivariés et (ii) le problème de déformation temporelle entre paires de signaux. Les méthodes généralement utilisées pour résoudre ces deux problèmes dépendent fortement d’une mesure de similarité. Nous apprenons une mesure de similarité à partir de données totalement étiquetées. Nous présentons des algorithmes usuels de prédiction structuré, efficaces pour effectuer l’apprentissage. Nous validons notre approche sur des données réelles venant de divers domaines. D’autre part, nous nous intéressons au problème de la faible supervision pour la tâche d’alignement d’un enregistrement audio sur la partition jouée. Nous considérons la partition comme une représentation symbolique donnant (i) une information complète sur l’ordre des symboles et (ii) une information approximative sur la forme de l’alignement attendu. Nous apprenons un classifieur pour chaque symbole avec ces informations. Nous développons une méthode d’apprentissage fondée sur l’optimisation d’une fonction convexe. Nous démontrons la validité de l’approche sur des données musicales.

Supposons que l'on nous donne un ensemble de vidéos, ainsi que des descriptions en langage naturel sous la forme de phrases multiples (par exemple, des phrases de type "c").

Jusqu'à l'avènement de méthodes de neuroimagerie non invasives les connaissances du cerveau sont acquis par l'étude de ses lésions, des analyses post-mortem et expérimentations invasives. De nos jours, les techniques modernes d'imagerie telles que l'IRMf sont capables de révéler plusieurs aspects du cerveau humain à une résolution spatio-temporelle progressivement élevé. Cependant, afin de pouvoir répondre à des questions neuroscientifiques de plus en plus complexes, les améliorations techniques dans l'acquisition doivent être jumelés à de nouvelles méthodes d'analyse des données. Dans cette thèse, je propose différentes applications de l'apprentissage statistique au traitement des données d'IRMf. Souvent, les données acquises par le scanner IRMf suivent une étape de sélection de variables dans lequel les cartes d'activation sont extraites du signal IRMf. La première contribution de cette thèse est l'introduction d'un modèle nommé Rank-1 GLM (R1-GLM) pour l'estimation jointe des cartes d'activation et de la fonction de réponse hémodynamique (HRF). Nous quantifions l'amélioration de cette approche par rapport aux procédures existantes sur différents jeux de données IRMf. La deuxième partie de cette thèse est consacrée au problème de décodage en IRMf, ce est à dire, la tâche de prédire quelques informations sur les stimuli à partir des cartes d'activation du cerveau. D'un point de vue statistique, ce problème est difficile due à la haute dimensionnalité des données, souvent des milliers de variables, tandis que le nombre d'images disponibles pour la formation est faible, typiquement quelques centaines. Nous examinons le cas où la variable cible est composé à partir de valeurs discrets et ordonnées. La deuxième contribution de cette thèse est de proposer les deux mesures suivantes pour évaluer la performance d'un modèle de décodage: l'erreur absolue et de désaccord par paires. Nous présentons plusieurs modèles qui optimisent une approximation convexe de ces fonctions de perte et examinent leur performance sur des ensembles de données IRMf. Motivé par le succès de certains modèles de régression ordinales pour la tâche du décodage basé IRMf, nous nous tournons vers l'étude de certaines propriétés théoriques de ces méthodes. La propriété que nous étudions est connu comme la cohérence de Fisher. La troisième, et la plus théorique, la contribution de cette thèse est d'examiner les propriétés de cohérence d'une riche famille de fonctions de perte qui sont utilisés dans les modèles de régression ordinales.

Récemment, l'algorithme d'optimisation de Frank-Wolfe a été proposé comme une procédure permettant d'obtenir des règles de quadrature adaptatives pour les intégrales de fonctions dans un espace de Hilbert à noyau reproducteur (RKHS) avec un taux de convergence potentiellement plus rapide que l'intégration de Monte Carlo (et il a été démontré que le "kernel herding" était un cas particulier de cette procédure). Dans cet article, nous proposons de remplacer l'étape d'échantillonnage aléatoire dans un filtre particulaire par une optimisation de Frank-Wolfe. En optimisant la position des particules, nous pouvons obtenir une meilleure précision que l'échantillonnage aléatoire ou quasi-Monte Carlo. Dans les applications où l'évaluation des probabilités d'émission est coûteuse (comme dans la localisation de robots), le coût de calcul supplémentaire pour générer les particules par optimisation peut être justifié. Les expériences sur des exemples synthétiques standard ainsi que sur une tâche de localisation de robot indiquent effectivement une amélioration de la précision par rapport à l'échantillonnage aléatoire et quasi-Monte Carlo.

Une approche populaire dans les communautés du traitement du signal et de l'apprentissage automatique consiste à modéliser les signaux comme des combinaisons linéaires éparses d'atomes sélectionnés dans un dictionnaire appris. Si ce paradigme a donné lieu à de nombreux succès empiriques dans divers domaines allant du traitement des images au traitement du son, seuls quelques arguments théoriques sont venus étayer ces preuves. En particulier, le codage clairsemé, ou l'apprentissage de dictionnaires clairsemés, repose sur une procédure non convexe dont les minima locaux n'ont pas encore été complètement analysés. Dans cet article, nous considérons un modèle probabiliste de signaux clairsemés, et montrons que, avec une forte probabilité, le codage clairsemé admet un minimum local autour du dictionnaire de référence générant les signaux. Notre étude prend en compte le cas de dictionnaires sur-complets, de signaux bruyants, et d'éventuelles valeurs aberrantes, étendant ainsi les travaux précédents limités à des contextes sans bruit et/ou à des dictionnaires sous-complets. L'analyse que nous menons est non-asymptotique et permet de comprendre comment les quantités clés du problème, telles que la cohérence ou le niveau de bruit, peuvent évoluer en fonction de la dimension des signaux, du nombre d'atomes, de la sparsité et du nombre d'observations.

La segmentation audio est un problème essentiel dans de nombreuses tâches de traitement du signal audio, qui tente de segmenter un signal audio en morceaux homogènes. Plutôt que de trouver séparément les points de changement et de calculer les similarités entre les segments, nous nous concentrons sur la segmentation et le regroupement conjoints, en utilisant le cadre des modèles de Markov cachés et des modèles semi-Markov. Nous introduisons un nouvel algorithme EM incrémental pour les modèles de Markov cachés (HMM) et montrons qu'il se compare favorablement aux algorithmes EM en ligne existants pour les HMM. Nous présentons des résultats pour la segmentation en temps réel de notes de musique et de scènes acoustiques.

Nous considérons les techniques d'appariement de moments pour l'estimation dans l'allocation latente de Dirichlet (LDA). En établissant des liens explicites entre la LDA et les versions discrètes de l'analyse en composantes indépendantes (ICA), nous dérivons d'abord un nouvel ensemble de tenseurs basés sur le cumulant, avec une complexité d'échantillonnage améliorée. De plus, nous réutilisons les techniques standard de l'ICA, telles que la diagonalisation conjointe des tenseurs, pour améliorer les méthodes existantes basées sur la méthode de la puissance des tenseurs. Dans un vaste ensemble d'expériences sur des ensembles de données synthétiques et réelles, nous montrons que notre nouvelle combinaison de tenseurs et de techniques de diagonalisation conjointe orthogonale surpasse les méthodes existantes de correspondance des moments.

Dans cet article, nous abordons le problème de la classification multi-labels. Nous considérons des classifieurs linéaires et proposons d'apprendre un antécédent sur l'espace des étiquettes afin d'améliorer directement les performances de ces méthodes. Cet antécédent prend la forme d'une fonction quadratique des étiquettes et permet d'encoder les relations attractives et répulsives entre les étiquettes. Nous présentons ce problème comme un problème de prédiction structurée visant à optimiser soit la précision des prédicteurs, soit le score F 1. Cela conduit à un problème d'optimisation étroitement lié au problème de coupe maximale, qui conduit naturellement à des relaxations semi-définies et spectrales. Nous montrons sur des ensembles de données standard comment une telle antériorité générale peut améliorer les performances des techniques multi-labels.

La segmentation audio est un problème essentiel dans de nombreuses tâches de traitement du signal audio, qui tente de segmenter un signal audio en morceaux homogènes. Plutôt que de trouver séparément les points de changement et de calculer les similarités entre les segments, nous nous concentrons sur la segmentation et le regroupement conjoints, en utilisant le cadre des modèles de Markov cachés et des modèles semi-Markov. Nous introduisons un nouvel algorithme EM incrémental pour les modèles de Markov cachés (HMM) et montrons qu'il se compare favorablement aux algorithmes EM en ligne existants pour les HMM. Nous présentons des résultats pour la segmentation en temps réel de notes de musique et de scènes acoustiques.

Nous montrons que la descente de gradient accélérée, la descente de gradient moyennée et la méthode de la boule lourde pour les problèmes non fortement convexes peuvent être reformulées comme des algorithmes d'équation aux différences du second ordre à paramètres constants, où la stabilité du système est équivalente à la convergence à un taux O(1/n 2), où n est le nombre d'itérations. Nous fournissons une analyse détaillée des valeurs propres du système dynamique linéaire correspondant, montrant divers comportements oscillatoires et non-oscillatoires, ainsi qu'un résultat de stabilité net avec des constantes explicites. Nous considérons également la situation où des gradients bruyants sont disponibles, où nous étendons notre résultat de convergence général, ce qui suggère un algorithme alternatif (c'est-à-dire avec différentes tailles de pas) qui présente les bons aspects de la moyenne et de l'accélération.

Une approche populaire dans les communautés du traitement du signal et de l'apprentissage automatique consiste à modéliser les données à haute dimension comme des combinaisons linéaires éparses d'atomes sélectionnés dans un dictionnaire. Étant donné l'importance du choix du dictionnaire pour le déploiement opérationnel de ces outils, un intérêt croissant pour les dictionnaires \emph{learned} a émergé. Les techniques d'apprentissage de dictionnaires les plus populaires, qui s'expriment sous la forme d'une factorisation matricielle à grande échelle par l'optimisation d'une fonction de coût non convexe, ont été largement diffusées grâce aux nombreuses preuves empiriques de leur succès et aux progrès algorithmiques constants. Pourtant, jusqu'à récemment, elles sont restées essentiellement heuristiques. Nous présenterons des travaux récents sur les aspects statistiques de l'apprentissage de dictionnaires clairsemés, contribuant à la caractérisation de l'excès de risque en fonction du nombre d'échantillons d'entraînement. Les résultats couvrent non seulement l'apprentissage de dictionnaires clairsemés mais aussi une classe beaucoup plus large de problèmes de factorisation de matrices sous contraintes.

Cette thèse, organisée en deux parties indépendantes, a pour objet la sémantique distributionnelle et la sélection de variables. Dans la première partie, nous introduisons une nouvelle méthode pour l'apprentissage de représentations de mots à partir de grandes quantités de texte brut. Cette méthode repose sur un modèle probabiliste de la phrase, utilisant modèle de Markov caché et arbre de dépendance. Nous présentons un algorithme efficace pour réaliser l'inférence et l'apprentissage dans un tel modèle, fondé sur l'algorithme EM en ligne et la propagation de message approchée. Nous évaluons les modèles obtenus sur des taches intrinsèques, telles que prédire des jugements de similarité humains ou catégoriser des mots et deux taches extrinsèques~: la reconnaissance d'entités nommées et l'étiquetage en supersens. Dans la seconde partie, nous introduisons, dans le contexte des modèles linéaires, une nouvelle pénalité pour la sélection de variables en présence de prédicteurs fortement corrélés. Cette pénalité, appelée trace Lasso, utilise la norm trace des prédicteurs sélectionnés, qui est une relaxation convexe de leur rang, comme critère de complexité. Le trace Lasso interpole les normes $\ell_1$ et $\ell_2$. En particulier, lorsque tous les prédicteurs sont orthogonaux, il est égal à la norme $\ell_1$, tandis que lorsque tous les prédicteurs sont égaux, il est égal à la norme $\ell_2$. Nous proposons deux algorithmes pour calculer la solution du problème de régression aux moindres carrés regularisé par le trace Lasso et réalisons des expériences sur des données synthétiques.

La modélisation de la langue naturelle est l¿un des défis fondamentaux de l¿intelligence artificielle et de la conception de systèmes interactifs, avec applications dans les systèmes de dialogue, la génération de texte et la traduction automatique. Nous proposons un modèle log-linéaire discriminatif donnant la distribution des mots qui suivent un contexte donné. En raison de la parcimonie des données, nous proposons un terme de pénalité qui code correctement la structure de l¿espace fonctionnel pour éviter le sur-apprentissage et d¿améliorer la généralisation, tout en capturant de manière appropriée les dépendances à long terme. Le résultat est un modèle efficace qui capte suffisamment les dépendances longues sans occasionner une forte augmentation des ressources en espace ou en temps. Dans un modèle log-linéaire, les phases d¿apprentissage et de tests deviennent de plus en plus chères avec un nombre croissant de classes. Le nombre de classes dans un modèle de langue est la taille du vocabulaire, qui est généralement très importante. Une astuce courante consiste à appliquer le modèle en deux étapes: la première étape identifie le cluster le plus probable et la seconde prend le mot le plus probable du cluster choisi. Cette idée peut être généralisée à une hiérarchie de plus grande profondeur avec plusieurs niveaux de regroupement. Cependant, la performance du système de classification hiérarchique qui en résulte dépend du domaine d¿application et de la construction d¿une bonne hiérarchie. Nous étudions différentes stratégies pour construire la hiérarchie des catégories de leurs observations.

Nous disposons d'un ensemble de clips vidéo, chacun annoté d'une liste ordonnée d'actions, telles que "marcher", "s'asseoir" et "répondre au téléphone", extraites, par exemple, du texte associé. Nous cherchons à localiser temporairement les actions individuelles dans chaque clip ainsi qu'à apprendre un classificateur discriminant pour chaque action. Nous formulons le problème comme une affectation temporelle faiblement supervisée avec des contraintes d'ordonnancement. Chaque clip vidéo est divisé en petits intervalles de temps et chaque intervalle de temps de chaque clip vidéo se voit attribuer une étiquette d'action, tout en respectant l'ordre dans lequel les étiquettes d'action apparaissent dans les annotations données. Nous montrons que l'attribution des étiquettes d'action peut être déterminée en même temps que l'apprentissage d'un classificateur pour chaque action de manière discriminante. Nous évaluons le modèle proposé sur un nouveau jeu de données difficile de 937 clips vidéo avec un total de 787720 images contenant des séquences de 16 actions différentes provenant de 69 films hollywoodiens.

Ces dernières années, un grand nombre de recherches pluridisciplinaires ont été menées sur les modèles épars et leurs applications. En statistique et en apprentissage automatique, le principe de sparsité est utilisé pour effectuer une sélection de modèles, c'est-à-dire pour sélectionner automatiquement un modèle simple parmi une grande collection de modèles. En traitement du signal, le codage clairsemé consiste à représenter les données par des combinaisons linéaires de quelques éléments de dictionnaire. Par la suite, les outils correspondants ont été largement adoptés par plusieurs communautés scientifiques telles que les neurosciences, la bioinformatique ou la vision par ordinateur. L'objectif de cette monographie est d'offrir une vision autonome de la modélisation clairsemée pour la reconnaissance visuelle et le traitement des images. Plus précisément, nous nous concentrons sur les applications où le dictionnaire est appris et adapté aux données, ce qui donne une représentation compacte qui a fait ses preuves dans divers contextes.

Motivation : Les profils de nombre de copies d'ADN caractérisent les régions de gains, de pertes et de points de rupture chromosomiques dans les génomes tumoraux. Bien que de nombreux modèles aient été proposés pour détecter ces altérations, il n'est pas évident de savoir quel modèle est approprié avant l'inspection visuelle du signal, du bruit et des modèles pour un profil particulier. . Résultats : Nous proposons SegAnnDB, un système de vision par ordinateur basé sur le Web pour la segmentation génomique : il faut d'abord inspecter visuellement les profils et annoter manuellement les régions altérées, puis SegAnnDB détermine les emplacements précis des altérations en utilisant un modèle mathématique des données et des annotations. SegAnnDB facilite la collaboration entre biologistes et bioinformaticiens, et utilise le navigateur génomique de l'Université de Californie, Santa Cruz, pour visualiser les altérations du nombre de copies à côté des gènes connus. . Disponibilité et mise en œuvre : Le projet breakpoints sur INRIA GForge héberge le code source, une image machine Amazon peut être lancée et un site Web de démonstration est http://bioviz.rocq.inria.fr. . Contact : pj.ca.hcetit.sc.gs@ybot . Informations supplémentaires : Des données supplémentaires sont disponibles sur Bioinformatics online.

Dans ce travail, nous introduisons une nouvelle méthode d'optimisation appelée SAGA dans l'esprit de SAG, SDCA, MISO et SVRG, un ensemble d'algorithmes de gradient incrémental récemment proposés avec des taux de convergence linéaire rapides. SAGA améliore la théorie derrière SAG et SVRG, avec de meilleurs taux de convergence théoriques, et supporte les objectifs composites où un opérateur proximal est utilisé sur le régularisateur. Contrairement à SDCA, SAGA supporte directement les problèmes non fortement convexes, et s'adapte à toute convexité forte inhérente au problème. Nous donnons des résultats expérimentaux montrant l'efficacité de notre méthode.

Dans le modèle de synthèse, les signaux sont représentés comme des combinaisons éparses d'atomes provenant d'un dictionnaire. L'apprentissage du dictionnaire décrit le processus d'acquisition du dictionnaire sous-jacent pour un ensemble donné d'échantillons d'apprentissage. L'idéal serait d'optimiser l'espérance des facteurs sur la distribution sous-jacente des données d'apprentissage, mais en pratique, les informations nécessaires sur la distribution ne sont pas disponibles. Par conséquent, dans les applications du monde réel, on y parvient en minimisant une moyenne empirique sur les échantillons disponibles. L'objectif principal de cet article est de fournir une estimation de la complexité de l'échantillon qui contrôle dans quelle mesure la moyenne empirique s'écarte de la fonction de coût. Cette estimation fournit ensuite une estimation appropriée de la précision de la représentation du dictionnaire appris. L'approche présentée exemplifie les résultats généraux proposés par les auteurs dans [1] et donne des limites plus concrètes de la complexité d'échantillon de l'apprentissage du dictionnaire. Nous couvrons une variété de mesures de sparsité employées dans la procédure d'apprentissage.

Nous considérons les problèmes de partitionnement non supervisé basés explicitement ou implicitement sur la minimisation des distorsions euclidiennes, tels que le clustering, la segmentation d'images ou de vidéos, et d'autres problèmes de détection de points de changement. Nous mettons l'accent sur les cas à structure spécifique, qui incluent de nombreuses situations pratiques allant de la détection de points de changement basée sur la moyenne aux problèmes de segmentation d'images. Notre objectif est d'apprendre une métrique de Mahalanobis pour ces problèmes non supervisés, ce qui permet de pondérer et/ou de sélectionner les caractéristiques. Cet apprentissage est réalisé de manière supervisée en supposant la disponibilité de plusieurs ensembles de données (partiellement) étiquetées qui partagent la même métrique. Nous présentons le problème de l'apprentissage de la métrique comme un problème de prédiction structuré à grande marge, avec une définition appropriée des régularisateurs et des pertes, ce qui conduit à un problème d'optimisation convexe qui peut être résolu efficacement. Nos expériences montrent comment l'apprentissage de la métrique peut améliorer de manière significative les performances sur des problèmes de bioinformatique, de segmentation de vidéos ou d'images.

Dans cet article, nous décrivons une nouvelle approche de la sémantique distributionnelle. Cette approche s'appuie sur un modèle génératif de phrases avec des variables latentes, qui prend en compte la syntaxe en utilisant des arbres de dépendance syntaxique. Les mots sont alors représentés comme des distributions postérieures sur ces classes latentes, et le modèle permet d'obtenir naturellement des représentations de mots en contexte et hors contexte, qui sont comparables. Nous entraînons notre modèle sur un large corpus et démontrons les capacités de composition de notre approche sur différents jeux de données.

Dans cet article, nous proposons d'apprendre une distance de Mahalanobis pour effectuer l'alignement de séries temporelles multivariées. Les exemples d'apprentissage pour cette tâche sont des séries temporelles pour lesquelles le véritable alignement est connu. Nous présentons le problème d'alignement comme une tâche de prédiction structurée et proposons des pertes réalistes entre les alignements pour lesquels l'optimisation est réalisable. Nous fournissons des expériences sur des données réelles dans le contexte audio à audio, où nous montrons que l'apprentissage d'une mesure de similarité conduit à des améliorations de la performance de la tâche d'alignement. Nous proposons également d'utiliser ce cadre d'apprentissage métrique pour effectuer une sélection de caractéristiques et, à partir de caractéristiques audio de base, construire une combinaison de celles-ci avec de meilleures performances pour l'alignement.

Dans les modèles de segmentation, le nombre de points de changement est généralement choisi en utilisant une fonction de coût pénalisée. Dans ce travail, nous proposons d'apprendre la pénalité et ses constantes dans des bases de données de signaux avec de faibles annotations de points de changement. Nous proposons une relaxation convexe pour le problème de régression par intervalles qui en résulte, et nous le résolvons en utilisant des méthodes accélérées de gradient proximal. Nous montrons que cette méthode permet une détection de pointe des points de changement dans une base de données de profils de nombre de copies d'ADN annotés provenant de tumeurs de neuroblastome.

Cette thèse a pour objet la construction, la calibration et l'étude d'estimateurs multi-tâches, dans un cadre fréquentiste non paramétrique et non asymptotique. Nous nous plaçons dans le cadre de la régression ridge à noyau et y étendons les méthodes existantes de régression multi-tâches. La question clef est la calibration d'un paramètre de régularisation matriciel, qui encode la similarité entre les tâches. Nous proposons une méthode de calibration de ce paramètre, fondée sur l'estimation de la matrice de covariance du bruit entre les tâches. Nous donnons ensuite pour l'estimateur obtenu des garanties d'optimalité, via une inégalité oracle, puis vérifions son comportement sur des exemples simulés. Nous obtenons par ailleurs un encadrement précis des risques des estimateurs oracles multi-tâches et mono-tâche dans certains cas. Cela nous permet de dégager plusieurs situations intéressantes, où l'oracle multi-tâches est plus efficace que l'oracle mono-tâche, ou vice versa. Cela nous permet aussi de nous assurer que l'inégalité oracle force l'estimateur multi-tâches à  avoir un risque inférieur à  l'estimateur mono-tâche dans les cas étudiés. Le comportement des oracles multi-tâches et mono-tâche est vérifié sur des exemples simulés.

Nous abordons le problème de l'apprentissage d'un modèle conjoint des acteurs et des actions dans les films en utilisant une supervision faible fournie par les scripts. Plus précisément, nous extrayons les paires acteur/action du scénario et les utilisons comme contraintes dans un cadre de regroupement discriminant. Le problème d'optimisation correspondant est formulé comme un programme quadratique avec des contraintes linéaires. Les personnes dans la vidéo sont représentées par des visages extraits et suivis automatiquement avec les caractéristiques de mouvement correspondantes. Dans un premier temps, nous appliquons le cadre proposé à la tâche d'apprentissage des noms des personnages du film et démontrons des améliorations significatives par rapport aux méthodes précédentes utilisées pour cette tâche. Ensuite, nous explorons la contrainte conjointe acteur/action et montrons son avantage pour l'apprentissage d'actions faiblement supervisées. Nous validons notre méthode dans le cadre difficile de la localisation et de la reconnaissance des personnages et de leurs actions dans les longs métrages Casablanca et American Beauty.

Dans cet article, nous proposons une nouvelle méthode d'induction de classes sémantiques. Tout d'abord, nous introduisons un modèle génératif de phrases, basé sur des arbres de dépendance et qui prend en compte l'homonymie. Notre modèle peut ainsi être considéré comme une généralisation du clustering de Brown. Deuxièmement, nous décrivons un algorithme efficace pour effectuer l'inférence et l'apprentissage dans ce modèle. Troisièmement, nous appliquons la méthode proposée sur deux grands ensembles de données (10^8$ tokens, 10^5$ types de mots), et nous démontrons que les classes induites par notre algorithme améliorent les performances par rapport au clustering de Brown sur la tâche de marquage supersens semi-supervisé et de reconnaissance d'entités nommées.

Nous présentons un nouveau cadre pour l'évaluation des représentations vocales dans des environnements sans ressources, qui étend et complète le travail précédent de Carlin, Jansen et Hermansky [1]. En particulier, nous remplaçons leur tâche de discrimination Same/Different par plusieurs tâches Minimal-Pair ABX (MP-ABX). Nous expliquons les avantages analytiques de ce nouveau cadre et l'appliquons pour dé-composer les pipelines de traitement du signal standard pour calculer les coefficients PLP et MFC. Cette méthode nous permet de confirmer et de quantifier une variété de résultats connus et moins connus dans un cadre unique.

Nous considérons le problème d'approximation stochastique où une fonction convexe doit être minimisée, en ne connaissant que des estimations non biaisées de ses gradients en certains points, un cadre qui inclut des méthodes d'apprentissage automatique basées sur la minimisation du risque empirique. Nous nous concentrons sur les problèmes sans forte convexité, pour lesquels tous les algorithmes connus précédemment atteignent un taux de convergence pour les valeurs de la fonction de O(1/n^{1/2}). Nous considérons et analysons deux algorithmes qui atteignent un taux de O(1/n) pour les problèmes classiques d'apprentissage supervisé. Pour la régression des moindres carrés, nous montrons que la descente de gradient stochastique moyennée avec une taille de pas constante atteint le taux souhaité. Pour la régression logistique, cela est obtenu par un nouvel algorithme de gradient stochastique simple qui (a) construit des approximations quadratiques locales successives des fonctions de perte, tout en (b) préservant la même complexité de temps d'exécution que la descente de gradient stochastique. Pour ces algorithmes, nous fournissons une analyse non asymptotique de l'erreur de généralisation (en espérance, et aussi en haute probabilité pour les moindres carrés), et nous effectuons des expériences approfondies sur des repères standards d'apprentissage automatique montrant qu'ils surpassent souvent les approches existantes.

De nombreux modèles ont été proposés pour détecter les altérations du nombre de copies dans les profils de nombre de copies chromosomiques, mais il n'est généralement pas évident de décider lequel est le plus efficace pour un ensemble de données donné. En outre, la plupart des méthodes ont un paramètre de lissage qui détermine le nombre de points d'arrêt et qui doit être choisi à l'aide de diverses heuristiques.

Nous abordons le problème de la conception d'un régularisateur convexe non lisse encourageant plusieurs effets structurels simultanément. En nous concentrant sur l'inférence de matrices éparses et à faible rang, nous proposons un nouvel indice de complexité et une pénalité convexe qui s'en approche. Le nouveau terme de pénalité peut être écrit comme la norme de trace d'une fonction linéaire de la matrice. En analysant les propriétés théoriques de cette famille de régularisateurs, nous proposons des égalités d'oracle et des résultats de détection comprimée garantissant la qualité de notre estimateur régularisé. Nous fournissons également des algorithmes et des expériences numériques de soutien.

Les méthodes basées sur les noyaux offrent un cadre riche et élégant pour développer des procédures de détection non paramétriques pour le traitement du signal. Plusieurs procédures récemment proposées peuvent être décrites simplement en utilisant les concepts de base des noyaux reproducteurs de l'espace de Hilbert des distributions de probabilité, à savoir les éléments moyens et les opérateurs de covariance. Nous proposons une vue unified de ces outils, et établissons des relations avec les divergences d'information entre les distributions.

La sériation cherche à reconstruire un ordre linéaire entre les variables en utilisant des informations de similarité non triées. Elle a des applications directes en archéologie et en séquençage génétique shotgun par exemple. Nous prouvons l'équivalence entre la sériation et le problème combinatoire 2-sum (un problème de minimisation quadratique sur les permutations) sur une classe de matrices de similarité. Le problème de la sériation peut être résolu exactement par un algorithme spectral dans le cas sans bruit et nous produisons une relaxation convexe pour le problème de la somme 2 afin d'améliorer la robustesse des solutions dans un cadre bruyant. Cette relaxation nous permet également d'imposer des contraintes structurelles supplémentaires sur la solution, afin de résoudre les problèmes de sériation semi-supervisée. Nous présentons des expériences numériques sur des données archéologiques, des chaînes de Markov et des séquences de gènes.

La plupart des systèmes de traitement du langage naturel basés sur l'apprentissage automatique ne sont pas robustes au changement de domaine. Par exemple, un analyseur syntaxique de dépendance à la pointe de la technologie, entraîné sur des phrases du Wall Street Journal, présente une baisse absolue de performance de plus de dix points lorsqu'il est testé sur des données textuelles provenant du Web. Une solution efficace pour rendre ces méthodes plus robustes au changement de domaine consiste à apprendre d'abord une représentation des mots en utilisant de grandes quantités de données non étiquetées provenant des deux domaines, puis à utiliser cette représentation comme caractéristique dans un algorithme d'apprentissage supervisé. Dans cet article, nous proposons d'utiliser des modèles de Markov cachés pour apprendre des représentations de mots pour l'étiquetage de la parole partielle. En particulier, nous étudions l'influence de l'utilisation des données de la source, de la cible ou des deux domaines pour apprendre la représentation et les différentes manières de représenter les mots en utilisant un HMM.

Dans les modèles de segmentation, le nombre de points de changement est généralement choisi à l'aide d'une fonction de coût pe- nalisée. Dans ce travail, nous proposons d'apprendre la pénalité et ses constantes dans des bases de données de signaux avec de faibles annotations de points de changement. Nous proposons une relaxation convexe pour le problème de régression par intervalles qui en résulte, et nous le résolvons en utilisant des méthodes de gradient proximal accélérées. Nous montrons que cette méthode permet une détection de pointe des points de changement dans une base de données de profils annotés du nombre de copies d'ADN provenant de tumeurs de neuroblastome.

Les modèles de langage peuvent être formalisés comme des modèles de régression log-linéaire où les caractéristiques d'entrée représentent des contextes précédemment observés jusqu'à une certaine longueur m. La complexité des algorithmes existants pour apprendre les paramètres par maximum de vraisemblance s'étend linéairement en nd, où n est la longueur du corpus d'apprentissage et d est le nombre de caractéristiques observées. Nous présentons un modèle qui croît logarithmiquement en d, ce qui permet d'exploiter efficacement des contextes plus longs. Nous tenons compte de la structure séquentielle du langage naturel en utilisant des objectifs pénalisés arborescents pour éviter le surajustement et obtenir une meilleure généralisation.

Il existe des situations de modélisation statistique pour lesquelles le problème classique de classification non supervisée (c'est-à-dire sans information a priori sur la nature ou le nombre de classes à constituer) se double d'un problème d'identification des variables réellement pertinentes pour déterminer la classification. Cette problématique est d'autant plus essentielle que les données dites de grande dimension, comportant bien plus de variables que d'observations, se multiplient ces dernières années : données d'expression de gènes, classification de courbes. Nous proposons une procédure de sélection de variables pour la classification non supervisée adaptée aux problèmes de grande dimension. Nous envisageons une approche par modèles de mélange gaussien, ce qui nous permet de reformuler le problème de sélection des variables et du choix du nombre de classes en un problème global de sélection de modèle. Nous exploitons les propriétés de sélection de variables de la régularisation l1 pour construire efficacement, à partir des données, une collection de modèles qui reste de taille raisonnable même en grande dimension. Nous nous démarquons des procédures classiques de sélection de variables par régularisation l1 en ce qui concerne l'estimation des paramètres : dans chaque modèle, au lieu de considérer l'estimateur Lasso, nous calculons l'estimateur du maximum de vraisemblance. Ensuite, nous sélectionnons l'un des ces estimateurs du maximum de vraisemblance par un critère pénalisé non asymptotique basé sur l'heuristique de pente introduite par Birgé et Massart. D'un point de vue théorique, nous établissons un théorème de sélection de modèle pour l'estimation d'une densité par maximum de vraisemblance pour une collection aléatoire de modèles. Nous l'appliquons dans notre contexte pour trouver une forme de pénalité minimale pour notre critère pénalisé. D'un point de vue pratique, des simulations sont effectuées pour valider notre procédure, en particulier dans le cadre de la classification non supervisée de courbes. L'idée clé de notre procédure est de n'utiliser la régularisation l1 que pour constituer une collection restreinte de modèles et non pas aussi pour estimer les paramètres des modèles. Cette étape d'estimation est réalisée par maximum de vraisemblance. Cette procédure hybride nous est inspirée par une étude théorique menée dans une première partie dans laquelle nous établissons des inégalités oracle l1 pour le Lasso dans les cadres de régression gaussienne et de mélange de régressions gaussiennes, qui se démarquent des inégalités oracle l0 traditionnellement établies par leur absence totale d'hypothèse.

La prédiction de connexions entre objets, basée soit sur une observation bruitée, soit sur une suite d'observations est un problème d'intérêt pour un nombre d'applications allant de la conception de système de recommandation en commerce électronique et réseaux sociaux jusqu'à l'inférence de réseaux en biologie moléculaire. Ce travail présente des formulations du problème de prédiction de lien, dans les cadres statique et temporel, comme un problème régularisé. Dans le scénario statique c'est la combinaison de deux normes bien connues, la norme L1 et la trace-norme qui permet de prédire les liens, alors que dans le cas dynamique, l'utilisation d'un modèle autoregressif sur des descripteurs linéaires permet d'améliorer la qualité de la prédiction. Nous étudierons la nature des solutions des problèmes d'optimisation à la fois en termes statistique et algorithmique. Des résultats empiriques encourageant mettent en évidence l'apport de la méthodologie adoptée.

La simplicité apparente avec laquelle un humain perçoit ce qui l'entoure suggère que le processus impliqué est en partie mécanique, donc ne nécessite pas un haut degré de réflexion. Cette observation suggère que notre perception visuelle du monde peut être simulée sur un ordinateur. La vision par ordinateur est le domaine de recherche consacré au problème de la création d'une forme de perception visuelle pour des ordinateurs. La puissance de calcul des ordinateurs des années 50 ne permettait pas de traiter et d'analyser les données visuelles nécessaires à l'élaboration d'une perception visuelle virtuelle. Depuis peu, la puissance de calcul et la capacité de stockage ont permis à ce domaine de vraiment émerger. En deux décennies, la vision par ordinateur a permis de répondre à problèmes pratiques ou industrielles comme la détection des visages, de personnes au comportement suspect dans une foule ou de défauts de fabrication dans des chaînes de production. En revanche, en ce qui concerne l'émergence d'une perception visuelle virtuelle non spécifique à une tâche donnée, peu de progrès ont été réalisés et la communauté est toujours confrontée à des problèmes fondamentaux. Un de ces problèmes est de segmenter un stimuli optique ou une image en régions porteuses de sens, en objets ou actions. La segmentation de scène est naturelle pour les humains, mais aussi essentielle pour comprendre pleinement son environnement. Malheureusement elle est aussi extrêmement difficile à reproduire sur un ordinateur car il n'existe pas de définition claire de la région "significative''. En effet, en fonction de la scène ou de la situation, une région peut avoir des interprétations différentes. Etant donnée une scène se passant dans la rue, on peut considérer que distinguer un piéton est important dans cette situation, par contre ses vêtements ne le semblent pas nécessairement. Si maintenant nous considérons une scène ayant lieu pendant un défilé de mode, un vêtement devient un élément important, donc une région significative. Ici, nous nous concentrons sur ce problème de segmentation et nous l'abordons sous un angle particulier pour éviter cette difficulté fondamentale. Nous considérerons la segmentation comme un problème d'apprentissage faiblement supervisé, c'est-à-dire qu'au lieu de segmenter des images selon une certaine définition prédéfinie de régions "significatives'', nous développons des méthodes permettant de segmenter simultanément un ensemble d'images en régions qui apparaissent régulièrement. Nous définissons donc une région "significative'' d'un point de vue statistique: Ce sont les régions qui apparaissent régulièrement dans l'ensemble des images données. Pour cela nous concevons des modèles ayant une portée qui va au-delà de l'application à la vision. Notre approche prend ses racines dans l'apprentissage statistique, dont l'objectif est de concevoir des méthodes efficaces pour extraire et/ou apprendre des motifs récurrents dans des jeux de données. Ce domaine a récemment connu une forte popularité en raison de l'augmentation du nombre et de la taille des bases de données disponibles. Nous nous concentrons ici sur des méthodes conçues pour découvrir l'information "cachée'' dans une base à partir d'annotations incomplètes ou inexistantes. Enfin, nos travaux prennent racine dans le domaine de l'optimisation numérique afin d'élaborer des algorithmes efficaces et adaptés à nos problèmes. En particulier, nous utilisons et adaptons des outils récemment développés afin de relaxer des problèmes combinatoires complexes en des problèmes convexes pour lesquels il est garanti de trouver la solution optimale. Nous illustrons la qualité de nos formulations et algorithmes aussi sur des problèmes tirés de domaines autres que la vision par ordinateur. En particulier, nous montrons que nos travaux peuvent être utilisés dans la classification de texte et en biologie cellulaire.

Nous proposons dans cette thèse trois contributions principales aux méthodes d'apprentissage de dictionnaire. La première est un critère de parcimonie par groupes adapté à la NMF lorsque la mesure de distorsion choisie est la divergence d'Itakura-Saito. Dans la plupart des signaux de musique on peut trouver de longs intervalles où seulement une source est active (des soli). Le critère de parcimonie par groupe que nous proposons permet de trouver automatiquement de tels segments et d'apprendre un dictionnaire adapté à chaque source. Ces dictionnaires permettent ensuite d'effectuer la tâche de séparation dans les intervalles où les sources sont mélangés. Ces deux tâches d'identification et de séparation sont effectuées simultanément en une seule passe de l'algorithme que nous proposons. Notre deuxième contribution est un algorithme en ligne pour apprendre le dictionnaire à grande échelle, sur des signaux de plusieurs heures. L'espace mémoire requis par une NMF estimée en ligne est constant alors qu'il croit linéairement avec la taille des signaux fournis dans la version standard, ce qui est impraticable pour des signaux de plus d'une heure. Notre troisième contribution touche à l'interaction avec l'utilisateur. Pour des signaux courts, l'apprentissage aveugle est particulièrement dificile, et l'apport d'information spécifique au signal traité est indispensable. Notre contribution est similaire à l'inpainting et permet de prendre en compte des annotations temps-fréquences. Elle repose sur l'observation que la quasi-totalité du spectrogramme peut etre divisé en régions spécifiquement assignées à chaque source. Nous décrivons une extension de NMF pour prendre en compte cette information et discutons la possibilité d'inférer cette information automatiquement avec des outils d'apprentissage statistique simples.

L'apprentissage statistique est le domaine des mathématiques qui aborde le développement des algorithmes d'analyse de données. Cette thèse est divisée en deux parties : l'introduction de modèles mathématiques et l'implémentation d'outils logiciels. Dans la première partie, je présente de nouveaux algorithmes pour la segmentation et pour le partitionnement de données (clustering). Le partitionnement de données et la segmentation sont des méthodes d'analyse qui cherche des structures dans les données. Je présente les contributions suivantes, en soulignant les applications à la bioinformatique. Dans la deuxième partie, je présente mes contributions au logiciel libre pour la statistique, qui est utilisé pour l'analyse quotidienne du statisticien.

De nombreux domaines issus de l’industrie et des sciences appliquées ont été les témoins d’une révolution numérique. Cette dernière s’est accompagnée d’une croissance du volume des données, dont le traitement est devenu un défi technique. Dans ce contexte, la parcimonie est apparue comme un concept central en apprentissage statistique. Il est en effet naturel de vouloir exploiter les données disponibles via un nombre réduit de paramètres. Cette thèse se concentre sur une forme particulière et plus récente de parcimonie, nommée parcimonie structurée. Comme son nom l’indique, nous considérerons des situations où, au delà de la seule parcimonie, nous aurons également à disposition des connaissances a priori relatives à des propriétés structurelles du problème. L’objectif de cette thèse est d'analyser le concept de parcimonie structurée, en se basant sur des considérations statistiques, algorithmiques et appliquées. Nous commencerons par introduire une famille de normes structurées parcimonieuses dont les aspects statistiques sont étudiées en détail. Nous considérerons ensuite l’apprentissage de dictionnaires, où nous exploiterons les normes introduites précédemment dans un cadre de factorisation de matrices. Différents outils algorithmiques efficaces, tels que des méthodes proximales, seront alors proposés. Grâce à ces outils, nous illustrerons sur de nombreuses applications pourquoi la parcimonie structurée peut être bénéfique. Ces exemples contiennent des tâches de restauration en traitement de l’image, la modélisation hiérarchique de documents textuels, ou encore la prédiction de la taille d’objets à partir de signaux d’imagerie par résonance magnétique fonctionnelle.

Nous étudions dans cette thèse une représentation particulière de signaux fondée sur une méthode d’apprentissage statistique, qui consiste à modéliser des données comme combinaisons linéaires de quelques éléments d’un dictionnaire appris. Ceci peut être vu comme une extension du cadre classique des ondelettes, dont le but est de construire de tels dictionnaires (souvent des bases orthonormales) qui sont adaptés aux signaux naturels. Un succès important de cette approche a été sa capacité à modéliser des imagettes, et la performance des méthodes de débruitage d’images fondées sur elle. Nous traitons plusieurs questions ouvertes, qui sont reliées à ce cadre : Comment apprendre efficacement un dictionnaire ? Comment enrichir ce modèle en ajoutant une structure sous-jacente au dictionnaire ? Est-il possible d’améliorer les méthodes actuelles de traitement d’image fondées sur cette approche ? Comment doit-on apprendre le dictionnaire lorsque celui-ci est utilisé pour une tâche autre que la reconstruction de signaux ? Y a-t-il des applications intéressantes de cette méthode en vision par ordinateur ? Nous répondons à ces questions, avec un point de vue multidisciplinaire, en empruntant des outils d’apprentissage statistique, d’optimisation convexe et stochastique, de traitement des signaux et des images, de vison par ordinateur, mais aussi d'optimisation sur des graphes.

Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de noeuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendents dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques.