Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse, réalisée en entreprise en tant que thèse CIFRE dans l'entreprise fifty-five, étudie les algorithmes des systèmes de recommandation. Nous avons proposé trois nouveaux algorithmes améliorant l'état de l'art que ce soit en termes de performance ou de prise en compte des contraintes industrielles. Pour cela nous avons proposé un premier algorithme basé sur la factorisation de tenseur, généralisation de la factorisation de matrice couramment appliquée en filtrage collaboratif.Nous avons ensuite proposé un algorithme permettant d'améliorer l'état de l'art des solutions de complétion de paniers. L'objectif des algorithmes de complétion de paniers est de proposer à l'utilisateur un nouveau produit à ajouter au panier qu'il/elle est en train d'acheter permettant ainsi d'augmenter la valeur d'un utilisateur. Pour cela nous nous sommes appuyés sur les processus ponctuels déterminantal. Nous avons généralisé l'approche de la complétion de paniers par DPP en utilisant une approche tensorielle. Enfin nous avons proposé un algorithme d'apprentissage par renforcement permettant d'alterner entre différents algorithmes de recommandation. En effet, utiliser toujours le même algorithme peut avoir tendance à ennuyer l'utilisateur pendant un certain temps, ou à l'inverse lui donner de plus en plus confiance en l'algorithme. Ainsi la performance d'un algorithme donné n'est pas stationnaire et dépend de quand et à quelle fréquence celui-ci a été utilisé. Notre algorithme d'apprentissage par renforcement apprend en temps réel à alterner entre divers algorithmes de recommandations dans le but de maximiser les performances sur le long terme. / This thesis, written in a company as a CIFRE thesis in the company fifty-five, studies recommender systems algorithms. We propose three new algorithms that improved over state-of-the-art solutions in terms of performance or matching industrial constraints. To that end, we proposed a first algorithm based on tensor factorization, a generalization of matrix factorization, commonly used on collaborative filtering. We then proposed a new algorithm that improves basket completion state-of-the-art algorithms. The goal of basket completion algorithms is to recommend a new product to a given user based on the products she is about to purchase in order to increase the user value. To that end we leverage Determinantal Point Processes, i.e., probability measure where the probability to observe a given set is proportional to the determinant of a kernel matrix. We generalized DPP approaches for basket completion using a tensor point of view coupled with a logistic regression. Finally, we proposed a reinforcement learning algorithm that allows to alternate between several recommender systems algorithms. Indeed, using always the same algorithm may either bore the user for a while or reinforce her trust in the system. Thus, the algorithm performance is not stationary and depends on when and how much the algorithm has been used in the past. Our reinforcement learning algorithm learns in real time how to alternate between several recommender system algorithms in order to maximize long term performances, that is in order to keep the user interested in the system as long as possible.

La largeur linéaire et la largeur arborescente ont été introduites par Robertson et Seymour dans leurs travaux sur les mineurs de graphes. De manière informelle, la largeur linéaire (resp. la largeur arborescente) d'un graphe mesure l'écart entre ce graphe et la classe des chaînes (des arbres). Les deux paramètres se sont révélés très puissants de point de vue algorithmique, car de nombreux problèmes NP-difficiles deviennent polynomiaux lorsque l'on se restreint à des classes de graphes de largeur linéaire ou de largeur arborescente bornée. Etant donné un graphe G=(V,E) quelconque, un graphe d'intervalles H=(V,F) contenant G est appelé complétion d'intervalles de G. Calculer la largeur linéaire de G revient à trouver une complétion d'intervalles H, tout en minimisant la clique maximum de H. Le problème étant NP-difficile, nous calculerons des complétions d'intervalles minimales, où l'on demande seulement que l'ensemble d'arêtes rajoutées F\E soit minimal par inclusion parmi toutes les complétions possibles. Une approche similaire, à travers les triangulations minimales, est fortement utilisée pour comprendre et calculer la largeur arborescente. Ce mémoire présente nos résultats sur les complétions d'intervalles minimales. Nous donnons trois algorithmes calculant une complétion d'intervalles minimale, basés sur des approches différentes. Nous présentons également un algorithme calculant une complétion d'intervalles propres minimale. Enfin, nous montrons que la largeur linéaire des graphes d'intervalles circulaires peut être calculée en temps polynomial.

Les pâtes enrichies représentent un produit d’intérêt pour l’industrie, car elles offrent aux consommateurs la possibilité de profiter des bienfaits sur la santé de l’ingrédient d’enrichissement sans modifier leurs habitudes alimentaires. Cependant, la durée et le coût du développement de nouvelles pâtes enrichies sont significatifs et limitent leur probabilité de succès commercial. Dans cette thèse, des modèles ont été développés pour décrire la production des pâtes traditionnelles et enrichies et accélérer leur développement. Deux objectifs généraux ont été poursuivis. Le premier objectif était l’identification et la quantification des mécanismes de transfert affectant la qualité des pâtes lors du séchage, leur étape de transformation la plus importante. L’état de l’art a révélé que les modèles développés précédemment pour décrire le séchage des pâtes combinent la description des mécanismes de transfert de masse de l’eau à partir d’un coefficient de diffusion effectif. La qualité de ces modèles a été évaluée par analyses de sensibilité, d’incertitude et d’identifiabilité. Ces analyses ont montré que l’incertitude des modèles précédents sur la prédiction du temps de séchage requis est importante (environ ± 4 h) et que cette incertitude peut être expliquée par la faible identifiabilité pratique des coefficients de transfert de masse à partir de mesures bruitées de la teneur en eau. L’analyse des modèles de séchage précédents a également montré leur imprécision à décrire les profils internes de teneur en eau générés dans les pâtes lors du séchage, alors que ces profils en eau sont critiques à la prédiction de la formation de craques. Cette thèse a donc conduit au développement d’un nouveau modèle de séchage mécanistique, couplant le transfert de masse de l’eau liquide par capillarité et convection, le transfert de masse de l’eau vapeur par diffusion et convection, le transfert d’énergie par conduction, convection et évaporation et la déformation mécanique. Ce modèle a été validé pour 3 températures de séchage (40, 60 et 80 ºC) représentatives des conditions utilisées en industrie. Le deuxième objectif était la quantification de l’impact de l’enrichissement et des variables de procédé sur les propriétés des pâtes. Cet objectif a été atteint par la construction et la méta-analyse d’une base de données regroupant les propriétés des pâtes traditionnelles et enrichies mesurées dans la littérature. Les propriétés manquantes de la base de données ont été estimées par le développement d’une approche novatrice et originale basée sur la complétion de matrice. L’approche par complétion de matrice a permis d’expliquer en moyenne 40% de la variance des propriétés manquantes. Elle a également permis de déterminer pour près de 20% des propriétés manquantes, avec un niveau de confiance de plus de 90%, si elles sont supérieures ou inférieures à la valeur moyenne de la propriété, améliorant la caractérisation du produit sans coût expérimental additionnel. Les travaux de cette thèse ont conduit à la réalisation de 7 articles dans des revues avec comité de lecture et ont été présentés à 4 congrès internationaux. Les travaux ont permis le développement de 2 outils, le modèle de séchage mécanistique et l’estimation des propriétés manquantes par complétion de matrice, que l’industrie pourra utiliser pour accélérer le développement de nouvelles pâtes enrichies. Plusieurs contributions majeures de cette thèse, notamment l’établissement des conditions expérimentales pour l’identifiabilité pratique des coefficients de transfert de masse et les méthodologies pour la méta-analyse d’un produit et l’estimation de ses propriétés manquantes par complétion de matrice, ont été appliquées aux pâtes enrichies, mais leur impact s’étend à de nombreux produits et procédés.

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.

Ce travail s'intéresse à la preuve de propriétés de sûreté sur les programmes. Prouver de telles propriétés revient généralement à démontrer que les configurations critiques ne sont jamais atteintes lors de l'exécution du programme. Pour ces propriétés, nous proposons une technique de vérification semi-automatique qui tente de combiner les avantages du model-checking, interprétation abstraite et preuve interactive. Comme en model-checking, cette technique permet de prouver automatiquement des propriétés de sûreté sur les systèmes finis, ainsi que sur certaines classes de systèmes infinis ayant une présentation finie. En dehors de ces classes et comme en interprétation abstraite, notre technique permet d'approcher le comportement infini d'un système par une sur-approximation sûre. Enfin, lorsque les approximations sont trop grossières, il nous est possible d'intervenir manuellement sur la définition des approximations afin de les raffiner et, si cela est possible, de mener la preuve à son terme. Cette approche est basée sur les systèmes de réécriture qui sont un des outils centraux de la déduction automatique. Nous les utilisons comme formalisme pour représenter les programmes: une configuration de programme est représentée par un terme et les transitions entre configurations par des règles de réécriture. Sur de tels modèles, prouver la sûreté d'un programme revient à faire une analyse d'atteignabilité, c.-à-d. vérifier que les termes représentant les configurations critiques sont inatteignables par réécriture des termes initiaux. L'ensemble des termes atteignables est représenté par un automate d'arbre. La construction de cet automate est effectuée en utilisant un algorithme de complétion spécifique. Pour la définition des approximations, nous avons proposé deux langages spécifiques, l'un calqué sur la structure des automates et l'autre utilisant des équations sur les termes. Ce dernier permet, en particulier, d'estimer la précision des approximations construites par rapport à la réécriture modulo équations. Cette technique a été expérimentée pour la vérification de protocoles cryptographiques ainsi que pour le protoypage rapide d'analyses statiques de programmes Java byte code.

Établir des preuves de bon fonctionnement des programmes est délicat ; on a recours à des outils de preuve, qui doivent procéder par surapproximation (à cause du théorème de Rice). La complétion d'automate est un tel outil, qui surapproxime l'ensemble des termes accessibles lors de l'exécution d'un programme représenté par un système de réécriture. La stratégie d'évaluation donne l'ordre dans lequel les sous-termes d'un terme doivent être réécrits ; en tenir compte permet une meilleur précision de l'analyse. Notre thèse propose une adaptation de la complétion d'automate à la stratégie en profondeur, utilisée notamment par OCaml. Nous établissons la correction et la précision de notre méthode et montrons comment elle s'inscrit dans le cadre plus large de l'analyse de programmes fonctionnels (OCaml). / Proving that programs behave correctly is difficult; one uses proof tools, which must rely on overapproximation (because of Rice's theorem). Automaton completion is such a tool, which overapproximates the set of reachable terms during the execution of a program represented as a TRS. An evaluation strategy dictates which subterm of a term should be rewritten first; taking this into account allows for a better approximation. Our thesis sets forward an adaptation of automaton completion to the innermost strategy, which is used among others by OCaml. We prove the soundness and the precision of our adaptation and show how it is part of a greater framework for analysis of functional programms (OCaml).

La biologie des systèmes intègre données et connaissances par des méthodes bioinformatiques, afin de mieux appréhender la physiologie des organismes. Une problématique est l’applicabilité de ces techniques aux organismes non modèles, au centre de plus en plus d’études, grâce aux avancées de séquençage et à l’intérêt croissant de la recherche sur les microbiotes. Cette thèse s’intéresse à la modélisation du métabolisme par des réseaux, et de sa fonctionnalité par diverses sémantiques basées sur les graphes et les contraintes stoechiométriques. Une première partie présente des travaux sur la complétion de réseaux métaboliques pour les organismes non modèles. Une méthode basée sur les graphes est validée, et une seconde, hybride, est développée, en programmation par ensembles réponses (ASP). Ces complétions sont appliquées à des réseaux métaboliques d’algues en biologie marine, et étendues à la recherche de complémentarité métabolique entre Ectocarpus siliculosus et une bactérie symbiotique. En s’appuyant sur les méthodes de complétion, la seconde partie de la thèse vise à proposer et implémenter une sélection de communautés à l’échelle de grands microbiotes. Une approche en deux étapes permet de suggérer des symbiotes pour l’optimisation d’un objectif donné. Elle supporte la modélisation des échanges et couvre tout l’espace des solutions. Des applications sur le microbiote intestinal humain et la sélection de bactéries pour une algue brune sont présentées. Dans l’ensemble, cette thèse propose de modéliser, développer et appliquer des méthodes reposant sur des sémantiques de graphe pour élaborer des hypothèses sur le métabolisme des organismes. / Systems biology relies on computational biology to integrate knowledge and data, for a better understanding of organisms’ physiology. Challenges reside in the applicability of methods and tools to non-model organisms, for instance in marine biology. Sequencing advances and the growing importance of elucidating microbiotas’ roles, have led to an increased interest into these organisms. This thesis focuses on the modeling of the metabolism through networks, and of its functionality using graphs and constraints semantics. In particular, a first part presents work on gap-filling metabolic networks in the context of non-model organisms. A graph-based method is benchmarked and validated and a hybrid one is developed using Answer Set Programming (ASP) and linear programming. Such gap-filling is applied on algae and extended to decipher putative interactions between Ectocarpus siliculosus and a symbiotic bacterium. In this direction, the second part of the thesis aims at proposing formalisms and implementation of a tool for selecting and screening communities of interest within microbiotas. It enables to scale to large microbiotas and, with a two-step approach, to suggest symbionts that fit the desired objective. The modeling supports the computation of exchanges, and solving can cover the whole solution space. Applications are presented on the human gut microbiota and the selection of bacterial communities for a brown alga. Altogether, this thesis proposes modeling, software and biological applications using graph-based semantics to support the elaboration of hypotheses for elucidating the metabolism of organisms.

Cette thèse porte sur l'étude du problème inverse de détection d'obstacle/objet par des méthodes d'optimisation. Ce problème consiste à localiser un objet inconnu oméga situé à l'intérieur d'un domaine borné connu Oméga à l'aide de mesures de bord et plus précisément de données de Cauchy sur une partie Gammaobs de thetaOmega. Nous étudions les cas scalaires et vectoriels pour ce problème en considérant les équations de Laplace et de Stokes. Dans tous les cas, nous nous appuyons sur une résultat d'identifiabilité qui assure qu'il existe un unique obstacle/objet qui correspond à la mesure de bord considérée. La stratégie utilisée dans ce travail est de réduire le problème inverse à la minimisation d'une fonctionnelle coût: la fonctionnelle de Kohn-Vogelius. Cette approche est fréquemment utilisée et permet notamment d'utiliser des méthodes d'optimisation pour des implémentations numériques. Cependant, afin de bien définir la fonctionnelle, cette méthode nécessite de connaître une mesure sur tout le bord extérieur thetaOmega. Ce dernier point nous conduit à étudier le problème de complétion de données qui consiste à retrouver les conditions de bord sur une région inaccessible, i.e. sur thetaOmega\Gammaobs, à partir des données de Cauchy sur la région accessible Gammaobs. Ce problème inverse est également étudié en minimisant une fonctionnelle de type Kohn-Vogelius. La caractère mal posé de ce problème nous amène à régulariser la fonctionnelle via une régularisation de Tikhonov. Nous obtenons plusieurs propriétés théoriques comme des propriétés de convergence, en particulier lorsque les données sont bruitées. En tenant compte de ces résultats théoriques, nous reconstruisons numériquement les données de bord en mettant en oeuvre un algorithme de gradient afin de minimiser la fonctionnelle régularisée. Nous étudions ensuite le problème de détection d'obstacle lorsque seule une mesure de bord partielle est disponible. Nous considérons alors les conditions de bord inaccessibles et l'objet inconnu comme les variables de la fonctionnelle et ainsi, en utilisant des méthodes d'optimisation de forme géométrique, en particulier le gradient de forme de la fonctionnelle de Kohn-Vogelius, nous obtenons la reconstruction numérique de l'inclusion inconnue. Enfin, nous considérons, dans le cas vectoriel bi-dimensionnel, un nouveau degré de liberté en étudiant le cas où le nombre d'objets est inconnu. Ainsi, nous utilisons l'optimisation de forme topologique afin de minimiser la fonctionnelle de Kohn-Vogelius. Nous obtenons le développement asymptotique topologique de la solution des équations de Stokes 2D et caractérisons le gradient topologique de cette fonctionnelle. Nous déterminons alors numériquement le nombre d'obstacles ainsi que leur position. De plus, nous proposons un algorithme qui combine les méthodes d'optimisation de forme topologique et géométrique afin de déterminer numériquement le nombre d'obstacles, leur position ainsi que leur forme. / This PhD thesis is dedicated to the study of the inverse problem of obstacle/object detection using optimization methods. This problem consists in localizing an unknown object omega inside a known bounded domain omega by means of boundary measurements and more precisely by a given Cauchy pair on a part Gammaobs of thetaOmega. We cover the scalar and vector scenarios for this problem considering both the Laplace and the Stokes equations. For both cases, we rely on identifiability result which ensures that there is a unique obstacle/object which corresponds to the considered boundary measurements. The strategy used in this work is to reduce the inverse problem into the minimization of a cost-type functional: the Kohn-Vogelius functional. This kind of approach is widely used and permits to use optimization tools for numerical implementations. However, in order to well-define the functional, this approach needs to assume the knowledge of a measurement on the whole exterior boundary thetaOmega. This last point leads us to first study the data completion problem which consists in recovering the boundary conditions on an inaccessible region, i.e. on thetaOmega\Gammaobs, from the Cauchy data on the accessible region Gammaobs. This inverse problem is also studied through the minimization of a Kohn-Vogelius type functional. The ill-posedness of this problem enforces us to regularize the functional via a Tikhonov regularization. We obtain several theoretical properties as convergence properties, in particular when data is corrupted by noise. Based on these theoretical results, we reconstruct numerically the boundary data by implementing a gradient algorithm in order to minimize the regularized functional. Then we study the obstacle detection problem when only partial boundary measurements are available. We consider the inaccessible boundary conditions and the unknown object as the variables of the functional and then, using geometrical shape optimization tools, in particular the shape gradient of the Kohn-Vogelius functional, we perform the numerical reconstruction of the unknown inclusion. Finally, we consider, into the two dimensional vector case, a new degree of freedom by studying the case when the number of objects is unknown. Hence, we use the topological shape optimization in order to minimize the Kohn-Vogelius functional. We obtain the topological asymptotic expansion of the solution of the 2D Stokes equations and characterize the topological gradient for this functional. Then we determine numerically the number and location of the obstacles. Additionally, we propose a blending algorithm which combines the topological and geometrical shape optimization methods in order to determine numerically the number, location and shape of the objects.

Dans les applications modernes des statistiques et de l'apprentissage, il est courant que les données récoltées présentent un certain nombre d'imperfections. En particulier, les données sont souvent hétérogènes, c'est-à-dires qu'elles contiennent à la fois des informations quantitatives et qualitatives, incomplètes, lorsque certaines informations sont inaccessibles ou corrompues, et multi-sources, c'est-à-dire qu'elles résultent de l'agrégation de plusieurs jeux de données indépendant. Dans cette thèse, nous développons plusieurs méthodes pour l'analyse de données hétérogènes, incomplètes et multi-source. Nous nous attachons à étudier tous les aspects de ces méthodes, en fournissant des études théoriques précises, ainsi que des implémentations disponibles au public, et des évaluations empiriques. En particulier, nous considérons en détail deux applications issues de l'écologie pour la première et de la médecine pour la seconde. / In modern applications of statistics and machine learning, one often encounters many data imperfections. In particular, data are often heterogeneous, i.e. combine quantitative and qualitative information, incomplete, with missing values caused by machine failure or nonresponse phenomenons, and multi-source, when the data result from the compounding of diverse sources. In this dissertation, we develop several methods for the analysis of multi-source, heterogeneous and incomplete data. We provide a complete framework, and study all the aspects of the different methods, with thorough theoretical studies, open source implementations, and empirical evaluations. We study in details two particular applications from ecology and medical sciences.