Nous étudions plusieurs problèmes de coloration dans les graphes, pour certains avec une composante ludique. La coloration à distance 2 d'un graphe est une coloration de ses sommets telle que deux sommets à distance au plus 2 ont des couleurs différentes. Le L(p; q)-étiquetage est une généralisation de ce problème ou les contraintes à distance 1 et 2 sont différentes. Nous donnons des résultats pour ces deux problèmes dans plusieurs classes de graphes peu denses (ayant un faible degré moyen maximum).Le jeu de coloration sur un graphe est un jeu ou deux joueurs, Alice et Bob, colorent tour à tour un des sommets non coloriés d'un graphe, construisant ainsi une coloration propre partielle de plus en plus étendue de ce graphe. Alice tente d'étendre la coloration à l'ensemble du graphe, et Bob tente de l'en empêcher. Nous travaillons sur un invariant de graphe, le degré minmax, dont l'étude permet de déduire des résultats pour le jeu de coloration via l'étude d'un problème structurel, la (1; k)-décomposition d'un graphe, c'est-à-dire la partition de ses arêtes en une forêt et un sous-graphe de degré inférieur ou égal à k.Nous travaillons enfin sur une variante du jeu de coloration nommée jeu de coloration d'incidences, ou Alice et Bob colorient les incidences d'un graphe, pour lequel nous donnons une stratégie efficace pour Alice.Enfin, tout au long de notre mémoire, nous étudions les liens entre la notion de coloration est celle de marquage. Un marquage est un ordre sur les sommets (ou arêtes, ou incidences...) d'un graphe possédant des caractéristiques utiles pour le colorer. Pour nos différents problèmes, nous questionnons l'utilité ou les limites de l'usage de cette notion. / We study several problems of graph coloring, some of them with a game component.A 2-distance coloring of a graph is a vertex coloring where two vertices at distanceat most two have different colors. A L(p; q)-labeling is a generalisation of the distance-2coloring where constraints are different at distance 1 and 2. We give results for thesetwo problems in several classes of sparse graphs (with a low maximal average degree).The coloring game on a graph is a game where two players, Alice and Bob, taketurns coloring an uncolored vertex of the graph, constructing together a proper partialcoloring of the graph extending as time moves on. Alice try to extend the coloringto the whole graph, and Bob try to prevent her to win. We study a graph invariant,the minmax degree, who has consequences on the coloring game through the notion of(1; k)-decomposition of a graph, which is the partition of its edge set into a forest and asubgraph of degree bounded by k.We finally study a variant of the coloring game named incidence coloring game, whereAlice and Bob are coloring the incidences of a graph, and for which we give an efficientstrategy for Alice.Finally, during our thesis, we study the connections between coloring and marking,which is an order on the vertices of a graph (or its edges, or its incidences) havingproperties usefull for its coloring. For our problems, we try to determine the utility andthe limits of a marking-based approach of coloring problems.

La mise en évidence de nouvelle physique est l'un des enjeux des expériences auprès des grands collisionneurs TeVatron et LHC. Le quark top se place dans ce contexte de recherche. Des mesures de couplages et de propriétés du quark top non conformes aux prédictions théoriques seraient les premiers effets indirects d'une physique non décrite par le Modèle Standard.<br /><br />Le travail décrit dans cette thèse porte sur l'étude de la section efficace de production de quarks top par interaction forte au sein des deux collaborations D0 et ATLAS.<br /><br />Mon travail à D0 a tout d'abord consisté en l'amélioration de la reconstruction des électrons de faible impulsion au sein de jets. Ce nouvel algorithme peut désormais être utilisé pour identifier les jets de quarks b, produits dans les événements top-antitop recherchés. Ce travail s'est poursuivi par une analyse de mesure de la section efficace de production de paires de quarks top, avec 420 pb-1 de données de l'expérience D0. Les résultats de cette analyse sont en accord avec les prédictions du Modèle Standard.<br /><br />Dans l'expérience ATLAS, mon travail a consisté à élaborer une procédure de sélection des événements top-antitop, en adaptant les connaissances et les techniques issues de l'expérience D0 à l'environnement plus exigeant des collisions du LHC. Cette analyse a permis d'identifier les sources d'incertitudes qui auront un impact sur la mesure. Pour une année de fonctionnement du détecteur à basse luminosité, cette section efficace pourrait être mesurée avec une précision de quelques pourcents. Cette sensibilité permettrait de déceler des signes de nouvelle physique. La phénoménologie des événements top-antitop est modifiée par la présence de bosons de Higgs chargés apparaissant dans des modèles standard non minimaux. L'analyse effectuée dans ce nouveau cadre théorique a ainsi montré qu'une découverte serait possible pour certaines régions de l'espace des paramètres.

L'apprentissage machine (AM) est un outil important dans le domaine de la recherche d'information musicale (Music Information Retrieval ou MIR). De nombreuses tâches de MIR peuvent être résolues en entraînant un classifieur sur un ensemble de caractéristiques. Pour les tâches de MIR se basant sur l'audio musical, il est possible d'extraire de l'audio les caractéristiques pertinentes à l'aide de méthodes traitement de signal. Toutefois, certains aspects musicaux sont difficiles à extraire à l'aide de simples heuristiques. Afin d'obtenir des caractéristiques plus riches, il est possible d'utiliser l'AM pour apprendre une représentation musicale à partir de l'audio. Ces caractéristiques apprises permettent souvent d'améliorer la performance sur une tâche de MIR donnée. Afin d'apprendre des représentations musicales intéressantes, il est important de considérer les aspects particuliers à l'audio musical dans la conception des modèles d'apprentissage. Vu la structure temporelle et spectrale de l'audio musical, les représentations profondes et multiéchelles sont particulièrement bien conçues pour représenter la musique. Cette thèse porte sur l'apprentissage de représentations de l'audio musical. Des modèles profonds et multiéchelles améliorant l'état de l'art pour des tâches telles que la reconnaissance d'instrument, la reconnaissance de genre et l'étiquetage automatique y sont présentés. / Machine learning (ML) is an important tool in the field of music information retrieval (MIR). Many MIR tasks can be solved by training a classifier over a set of features. For MIR tasks based on music audio, it is possible to extract features from the audio with signal processing techniques. However, some musical aspects are hard to extract with simple heuristics. To obtain richer features, we can use ML to learn a representation from the audio. These learned features can often improve performance for a given MIR task. In order to learn interesting musical representations, it is important to consider the particular aspects of music audio when building learning models. Given the temporal and spectral structure of music audio, deep and multi-scale representations are particularly well suited to represent music. This thesis focuses on learning representations from music audio. Deep and multi-scale models that improve the state-of-the-art for tasks such as instrument recognition, genre recognition and automatic annotation are presented.

Cette thèse s’intéresse à diverses composantes du traitement et de l’analyse d’images par méthodes non locales. Ces méthodes sont basées sur la redondance d’information présente dans d’autres images, et utilisent des algorithmes de recherche de correspondance, généralement basés sur l’utilisation patchs, pour extraire et transférer de l’information depuis ces images d’exemples. Ces approches, largement utilisées par la communauté de vision par ordinateur, sont souvent limitées par le temps de calcul de l’algorithme de recherche, appliqué à chaque pixel, et par la nécessité d’effectuer un prétraitement ou un apprentissage pour utiliser de grandes bases de données.Pour pallier ces limites, nous proposons plusieurs méthodes générales, sans apprentissage,rapides, et qui peuvent être facilement adaptées à diverses applications de traitement et d’analyse d’images naturelles ou médicales. Nous introduisons un algorithme de recherche de correspondances permettant d’extraire rapidement des patchs d’une grande bibliothèque d’images 3D, que nous appliquons à la segmentation d’images médicales. Pour utiliser de façon similaire aux patchs,des présegmentations en superpixels réduisant le nombre d’éléments de l’image,nous présentons une nouvelle structure de voisinage de superpixels. Ce nouveau descripteur permet d’utiliser efficacement les superpixels dans des approches non locales. Nous proposons également une méthode de décomposition régulière et précise en superpixels. Nous montrons comment évaluer cette régularité de façon robuste, et que celle-ci est nécessaire pour obtenir de bonnes performances de recherche de correspondances basées sur les superpixels. / This thesis focuses on several aspects of image analysis and processing with non local methods. These methods are based on the redundancy of information that occurs in other images, and use matching algorithms, that are usually patch-based, to extract and transfer information from the example data. These approaches are widely used by the computer vision community, and are generally limited by the computational time of the matching algorithm, applied at the pixel scale, and by the necessity to perform preprocessing or learning steps to use large databases. To address these issues, we propose several general methods, without learning, fast, and that can be easily applied to different image analysis and processing applications on natural and medical images. We introduce a matching algorithm that enables to quickly extract patches from a large library of 3D images, that we apply to medical image segmentation. To use a presegmentation into superpixels that reduces the number of image elements, in a way that is similar to patches, we present a new superpixel neighborhood structure. This novel descriptor enables to efficiently use superpixels in non local approaches. We also introduce an accurate and regular superpixel decomposition method. We show how to evaluate this regularity in a robust manner, and that this property is necessary to obtain good superpixel-based matching performances.

La plupart des méthodes de traitement automatique des langues (TAL) peuvent être formalisées comme des problèmes de prédiction, dans lesquels on cherche à choisir automatiquement l'hypothèse la plus plausible parmi un très grand nombre de candidats. Malgré de nombreux travaux qui ont permis de mieux prendre en compte la structure de l'ensemble des hypothèses, la taille de l'espace de recherche est généralement trop grande pour permettre son exploration exhaustive. Dans ce travail, nous nous intéressons à l'importance du design de l'espace de recherche et étudions l'utilisation de contraintes pour en réduire la taille et la complexité. Nous nous appuyons sur l'étude de trois problèmes linguistiques — l'analyse morpho-syntaxique, le transfert cross-lingue et le problème du réordonnancement en traduction — pour mettre en lumière les risques, les avantages et les enjeux du choix de l'espace de recherche dans les problèmes de TAL.Par exemple, lorsque l'on dispose d'informations a priori sur les sorties possibles d'un problème d'apprentissage structuré, il semble naturel de les inclure dans le processus de modélisation pour réduire l'espace de recherche et ainsi permettre une accélération des traitements lors de la phase d'apprentissage. Une étude de cas sur les modèles exponentiels pour l'analyse morpho-syntaxique montre paradoxalement que cela peut conduire à d'importantes dégradations des résultats, et cela même quand les contraintes associées sont pertinentes. Parallèlement, nous considérons l'utilisation de ce type de contraintes pour généraliser le problème de l'apprentissage supervisé au cas où l'on ne dispose que d'informations partielles et incomplètes lors de l'apprentissage, qui apparaît par exemple lors du transfert cross-lingue d'annotations. Nous étudions deux méthodes d'apprentissage faiblement supervisé, que nous formalisons dans le cadre de l'apprentissage ambigu, appliquées à l'analyse morpho-syntaxiques de langues peu dotées en ressources linguistiques.Enfin, nous nous intéressons au design de l'espace de recherche en traduction automatique. Les divergences dans l'ordre des mots lors du processus de traduction posent un problème combinatoire difficile. En effet, il n'est pas possible de considérer l'ensemble factoriel de tous les réordonnancements possibles, et des contraintes sur les permutations s'avèrent nécessaires. Nous comparons différents jeux de contraintes et explorons l'importance de l'espace de réordonnancement dans les performances globales d'un système de traduction. Si un meilleur design permet d'obtenir de meilleurs résultats, nous montrons cependant que la marge d'amélioration se situe principalement dans l'évaluation des réordonnancements plutôt que dans la qualité de l'espace de recherche. / Most natural language processing tasks are modeled as prediction problems where one aims at finding the best scoring hypothesis from a very large pool of possible outputs. Even if algorithms are designed to leverage some kind of structure, the output space is often too large to be searched exaustively. This work aims at understanding the importance of the search space and the possible use of constraints to reduce it in size and complexity. We report in this thesis three case studies which highlight the risk and benefits of manipulating the seach space in learning and inference.When information about the possible outputs of a sequence labeling task is available, it may seem appropriate to include this knowledge into the system, so as to facilitate and speed-up learning and inference. A case study on type constraints for CRFs however shows that using such constraints at training time is likely to drastically reduce performance, even when these constraints are both correct and useful at decoding.On the other side, we also consider possible relaxations of the supervision space, as in the case of learning with latent variables, or when only partial supervision is available, which we cast as ambiguous learning. Such weakly supervised methods, together with cross-lingual transfer and dictionary crawling techniques, allow us to develop natural language processing tools for under-resourced languages. Word order differences between languages pose several combinatorial challenges to machine translation and the constraints on word reorderings have a great impact on the set of potential translations that is explored during search. We study reordering constraints that allow to restrict the factorial space of permutations and explore the impact of the reordering search space design on machine translation performance. However, we show that even though it might be desirable to design better reordering spaces, model and search errors seem yet to be the most important issues.

No description available.

Que ce soit par contrainte, pour accroître la qualité perçue d’un bien, ou encore améliorer l’image de marque, sont des raisons pouvant expliquer pourquoi une firme voudrait entreprendre des démarches de normalisation. Dans ce mémoire, de nombreuses études sont résumées afin de bien cadrer un modèle théorique qui montre qu’un transformateur, en utilisant un intrant de meilleure qualité, peut offrir un produit à valeur ajoutée (innovation de produits) pour lequel les consommateurs sont prêts à payer et ainsi se prémunir de la concurrence du grand transformateur qui produit à coût plus faible (innovation des procédés). Nos résultats montrent que lorsque le transformateur artisanal choisit son niveau de qualité en fonction des paramètres du marché et indépendamment de leur concurrent, s’assure que ce dernier ne réduit pas au maximum ses coûts. Lorsque le producteur artisanal se différentie, les deux joueurs réalisent davantage de profits. Dans un deuxième temps, deux questionnaires sont bâtis afin de vérifier si les consommateurs sont prêts à payer pour une amélioration de la qualité d’un bien laitier en offrant une nouvelle méthodologie pouvant permettre d’évaluer la volonté à payer en présentant le bien comme privé et comme public. Dans les deux questionnaires, nous relevons des signaux indiquant de fortes préférences pour l’attribut sélectionné : l’accès à l’extérieur pour les vaches laitières. / Constraints, increasing product quality or improving brand image are reasons that can justify why a firm, or a group of firms would adopt norms. In this master thesis, many studies about normalization are summarized to lay grounds for a theoretical model. The model shows that processors can produce higher value-added goods with higher a quality input (product innovation), for which consumers are willing to pay more. Our analysis shows that a small processor can mitigate market competition with a bigger processor that can decrease its unit cost (process innovation). Our results show that when the small processor chooses his quality independently from his competitor, the latter doesn’t reduce his costs aggressively. When both firms innovate, their profits increase. In the second part of this thesis, two questionnaires are constructed to assess the consumers’ willingness to pay for an increased quality milk. The two surveys allow us to treat a hypothetic type of milk having either a private or a public-good characteristic. Respondents in each survey signal strong animal welfare preferences, as the additional attribute for this type of milk is the access for cows to pastures.

Dans ce mémoire, un modèle théorique est développé pour analyser les impacts économiques de l'étiquetage des aliments génétiquement modifié (GM). Dans un premier temps, ce travail présente un cadre théorique d'offre et de demande qui s'applique aux diverses considérations des marchés des aliments GM et de ces substituts, soit les aliments dits conventionnel et biologique. Ainsi, des offres d'aliments différenciés fournis par des producteurs hétérogènes sont présentées. À cela, des demandes hétérogènes selon le concept de différenciation de produits empruntée au champ de l'organisation industrielle sont ajoutées. Ensuite, ce travail fait un exercice d'équilibre pour expliquer les impacts de cette politique publique sur les marchés des pays où il y a une grande production de culture GM. L'impact de la rigidité de la production de culture GM est aussi analysé en considérant des frictions au niveau de l'offre de culture conventionnelle et biologique. Les résultats montrent que, suite à l'étiquetage, il y a, en termes de bien-être économique, des bénéfices à tirer pour les producteurs et consommateurs d’aliment conventionnel, des pertes pour les producteurs et consommateurs d'aliments GM et que la rigidité de la production de cultures GM crée une mauvaise allocation des ressources. Celle-ci nuit à la consommation d'aliments conventionnelle et GM, bénéficie à la production de culture biologique lorsque les frictions prennent part dans la production conventionnelle et crée également une augmentation généralisée des prix des aliments issus des trois cultures. Il est ainsi recommandé de prendre en compte ces implications du marché dans les études de coûts de l'implantation d'un étiquetage obligatoire et de mettre en place des mesures permettant d'atténuer les effets de cette rigidité, advenant l'application d'une telle politique.

Cette thèse s'inscrit dans le cadre de l'émergence de l'apprentissage profond et aborde la compréhension de la parole assimilée à l'extraction et à la représentation automatique du sens contenu dans les mots d'une phrase parlée. Nous étudions une tâche d'étiquetage en concepts sémantiques dans un contexte de dialogue oral évaluée sur le corpus français MEDIA. Depuis une dizaine d'années, les modèles neuronaux prennent l'ascendant dans de nombreuses tâches de traitement du langage naturel grâce à des avancées algorithmiques ou à la mise à disposition d'outils de calcul puissants comme les processeurs graphiques. De nombreux obstacles rendent la compréhension complexe, comme l'interprétation difficile des transcriptions automatiques de la parole étant donné que de nombreuses erreurs sont introduites par le processus de reconnaissance automatique en amont du module de compréhension. Nous présentons un état de l'art décrivant la compréhension de la parole puis les méthodes d'apprentissage automatique supervisé pour la résoudre en commençant par des systèmes classiques pour finir avec des techniques d'apprentissage profond. Les contributions sont ensuite exposées suivant trois axes. Premièrement, nous développons une architecture neuronale efficace consistant en un réseau récurent bidirectionnel encodeur-décodeur avec mécanisme d’attention. Puis nous abordons la gestion des erreurs de reconnaissance automatique et des solutions pour limiter leur impact sur nos performances. Enfin, nous envisageons une désambiguïsation de la tâche de compréhension permettant de rendre notre système plus performant. / This thesis is a part of the emergence of deep learning and focuses on spoken language understanding assimilated to the automatic extraction and representation of the meaning supported by the words in a spoken utterance. We study a semantic concept tagging task used in a spoken dialogue system and evaluated with the French corpus MEDIA. For the past decade, neural models have emerged in many natural language processing tasks through algorithmic advances or powerful computing tools such as graphics processors. Many obstacles make the understanding task complex, such as the difficult interpretation of automatic speech transcriptions, as many errors are introduced by the automatic recognition process upstream of the comprehension module. We present a state of the art describing spoken language understanding and then supervised automatic learning methods to solve it, starting with classical systems and finishing with deep learning techniques. The contributions are then presented along three axes. First, we develop an efficient neural architecture consisting of a bidirectional recurrent network encoder-decoder with attention mechanism. Then we study the management of automatic recognition errors and solutions to limit their impact on our performances. Finally, we envisage a disambiguation of the comprehension task making the systems more efficient.

ATLAS, LHC, quark b, quark top, étiquetage des jets issus de quark b, calibration des algorithmes d'étiquetage des jets issus de quark b, quarks top-antitop, section efficace, section efficace différentielle des paires top-antitop, masse du top, rapidité du top, nouvelle physique.