La représentation d’image sous une forme hiérarchique a été largement utilisée dans un contexte de classification. Une telle représentation est capable de modéliser le contenu d’une image à travers une structure arborescente. Dans cette thèse, nous étudions les méthodes à noyaux qui permettent de prendre en entrée des données sous une forme structurée et de tenir compte des informations topologiques présentes dans chaque structure en concevant des noyaux structurés. Nous présentons un noyau structuré dédié aux structures telles que des arbres non ordonnés et des chemins (séquences de noeuds) équipés de caractéristiques numériques. Le noyau proposé, appelé Bag of Subpaths Kernel (BoSK), est formé en sommant les noyaux calculés sur les sous-chemins (un sac de tous les chemins et des noeuds simples) entre deux sacs. Le calcul direct de BoSK amène à une complexité quadratique par rapport à la taille de la structure (nombre de noeuds) et la quantité de données (taille de l’ensemble d’apprentissage). Nous proposons également une version rapide de notre algorithme, appelé Scalable BoSK (SBoSK), qui s’appuie sur la technique des Random Fourier Features pour projeter les données structurées dans un espace euclidien, où le produit scalaire du vecteur transformé est une approximation de BoSK. Cet algorithme bénéficie d’une complexité non plus linéaire mais quadratique par rapport aux tailles de la structure et de l’ensemble d’apprentissage, rendant ainsi le noyau adapté aux situations d’apprentissage à grande échelle. Grâce à (S)BoSK, nous sommes en mesure d’effectuer un apprentissage à partir d’informations présentes à plusieurs échelles dans les représentations hiérarchiques d’image. (S)BoSK fonctionne sur des chemins, permettant ainsi de tenir compte du contexte d’un pixel (feuille de la représentation hiérarchique) par l’intermédiaire de ses régions ancêtres à plusieurs échelles. Un tel modèle est utilisé dans la classification des images au niveau pixel. (S)BoSK fonctionne également sur les arbres, ce qui le rend capable de modéliser la composition d’un objet (racine de la représentation hiérarchique) et les relations topologiques entre ses sous-parties. Cette stratégie permet la classification des tuiles ou parties d’image. En poussant plus loin l’utilisation de (S)BoSK, nous introduisons une nouvelle approche de classification multi-source qui effectue la classification directement à partir d’une représentation hiérarchique construite à partir de deux images de la même scène prises à différentes résolutions, éventuellement selon différentes modalités. Les évaluations sur plusieurs jeux de données de télédétection disponibles dans la communauté illustrent la supériorité de (S)BoSK par rapport à l’état de l’art en termes de précision de classification, et les expériences menées sur une tâche de classification urbaine montrent la pertinence de l’approche de classification multi-source proposée. / Hierarchical image representations have been widely used in the image classification context. Such representations are capable of modeling the content of an image through a tree structure. In this thesis, we investigate kernel-based strategies that make possible taking input data in a structured form and capturing the topological patterns inside each structure through designing structured kernels. We develop a structured kernel dedicated to unordered tree and path (sequence of nodes) structures equipped with numerical features, called Bag of Subpaths Kernel (BoSK). It is formed by summing up kernels computed on subpaths (a bag of all paths and single nodes) between two bags. The direct computation of BoSK yields a quadratic complexity w.r.t. both structure size (number of nodes) and amount of data (training size). We also propose a scalable version of BoSK (SBoSK for short), using Random Fourier Features technique to map the structured data in a randomized finite-dimensional Euclidean space, where inner product of the transformed feature vector approximates BoSK. It brings down the complexity from quadratic to linear w.r.t. structure size and amount of data, making the kernel compliant with the large-scale machine-learning context. Thanks to (S)BoSK, we are able to learn from cross-scale patterns in hierarchical image representations. (S)BoSK operates on paths, thus allowing modeling the context of a pixel (leaf of the hierarchical representation) through its ancestor regions at multiple scales. Such a model is used within pixel-based image classification. (S)BoSK also works on trees, making the kernel able to capture the composition of an object (top of the hierarchical representation) and the topological relationships among its subparts. This strategy allows tile/sub-image classification. Further relying on (S)BoSK, we introduce a novel multi-source classification approach that performs classification directly from a hierarchical image representation built from two images of the same scene taken at different resolutions, possibly with different modalities. Evaluations on several publicly available remote sensing datasets illustrate the superiority of (S)BoSK compared to state-of-the-art methods in terms of classification accuracy, and experiments on an urban classification task show the effectiveness of proposed multi-source classification approach.

Dans cette thèse nous nous intéressons aux méthodes de complétion de matrices de faible rang et étudions certains problèmes reliés. Un premier ensemble de résultats visent à étendre les garanties statistiques existantes pour les modèles de complétion avec bruit additif sous-gaussiens à des distributions plus générales. Nous considérons en particulier les distributions multinationales et les distributions appartenant à la famille exponentielle. Pour ces dernières, nous prouvons l'optimalité (au sens minimax) à un facteur logarithmique près des estimateurs à pénalité norme trace. Un second ensemble de résultats concernent l'algorithme du gradient conditionnel qui est notamment utilisé pour calculer les estimateurs précédents. Nous considérons en particulier deux algorithmes de type gradient conditionnel dans le cadre de l'optimisation stochastique. Nous donnons les conditions sous lesquelles ces algorithmes atteignent les performance des algorithmes de type gradient projeté. / This thesis deals with the low rank matrix completion methods and focuses on some related problems, of both statistical and algorithmic nature. The first part of this work extends the existing statistical guarantees obained for sub-Gaussian additive noise models, to more general distributions. In particular,we provide upper bounds on the prediction error of trace norm penalized estimatorwith high probability for multinomial distributions and for distributions belonging to the exponential family. For the latter, we prove that the trace norm penalized estimators are minimax optimal up to a logarithmic factor by giving a lower bound.The second part of this work focuses on the conditionnal gradient algorithm, which is used in particular to compute previous estimators. We consider the stochastic optimization framework and gives the convergence rate of twovariants of the conditional gradient algorithm. We gives the conditions under which these algorithms match the performance of projected gradient algorithms.