Tesi: "Algorithme de bandit"

1

Saadane, Sofiane. "Algorithmes stochastiques pour l'apprentissage, l'optimisation et l'approximation du régime stationnaire". Thesis, Toulouse 3, 2016. http://www.theses.fr/2016TOU30203/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse, nous étudions des thématiques autour des algorithmes stochastiques et c'est pour cette raison que nous débuterons ce manuscrit par des éléments généraux sur ces algorithmes en donnant des résultats historiques pour poser les bases de nos travaux. Ensuite, nous étudierons un algorithme de bandit issu des travaux de N arendra et Shapiro dont l'objectif est de déterminer parmi un choix de plusieurs sources laquelle profite le plus à l'utilisateur en évitant toutefois de passer trop de temps à tester celles qui sont moins performantes. Notre but est dans un premier temps de comprendre les faiblesses structurelles de cet algorithme pour ensuite proposer une procédure optimale pour une quantité qui mesure les performances d'un algorithme de bandit, le regret. Dans nos résultats, nous proposerons un algorithme appelé NS sur-pénalisé qui permet d'obtenir une borne de regret optimale au sens minimax au travers d'une étude fine de l'algorithme stochastique sous-jacent à cette procédure. Un second travail sera de donner des vitesses de convergence pour le processus apparaissant dans l'étude de la convergence en loi de l'algorithme NS sur-pénalisé. La particularité de l'algorithme est qu'il ne converge pas en loi vers une diffusion comme la plupart des algorithmes stochastiques mais vers un processus à sauts non-diffusif ce qui rend l'étude de la convergence à l'équilibre plus technique. Nous emploierons une technique de couplage afin d'étudier cette convergence. Le second travail de cette thèse s'inscrit dans le cadre de l'optimisation d'une fonction au moyen d'un algorithme stochastique. Nous étudierons une version stochastique de l'algorithme déterministe de boule pesante avec amortissement. La particularité de cet algorithme est d'être articulé autour d'une dynamique qui utilise une moyennisation sur tout le passé de sa trajectoire. La procédure fait appelle à une fonction dite de mémoire qui, selon les formes qu'elle prend, offre des comportements intéressants. Dans notre étude, nous verrons que deux types de mémoire sont pertinents : les mémoires exponentielles et polynomiales. Nous établirons pour commencer des résultats de convergence dans le cas général où la fonction à minimiser est non-convexe. Dans le cas de fonctions fortement convexes, nous obtenons des vitesses de convergence optimales en un sens que nous définirons. Enfin, l'étude se termine par un résultat de convergence en loi du processus après une bonne renormalisation. La troisième partie s'articule autour des algorithmes de McKean-Vlasov qui furent introduit par Anatoly Vlasov et étudié, pour la première fois, par Henry McKean dans l'optique de la modélisation de la loi de distribution du plasma. Notre objectif est de proposer un algorithme stochastique capable d'approcher la mesure invariante du processus. Les méthodes pour approcher une mesure invariante sont connues dans le cas des diffusions et de certains autre processus mais ici la particularité du processus de McKean-Vlasov est de ne pas être une diffusion linéaire. En effet, le processus a de la mémoire comme les processus de boule pesante. De ce fait, il nous faudra développer une méthode alternative pour contourner ce problème. Nous aurons besoin d'introduire la notion de pseudo-trajectoires afin de proposer une procédure efficace
In this thesis, we are studying severa! stochastic algorithms with different purposes and this is why we will start this manuscript by giving historicals results to define the framework of our work. Then, we will study a bandit algorithm due to the work of Narendra and Shapiro whose objectif was to determine among a choice of severa! sources which one is the most profitable without spending too much times on the wrong orres. Our goal is to understand the weakness of this algorithm in order to propose an optimal procedure for a quantity measuring the performance of a bandit algorithm, the regret. In our results, we will propose an algorithm called NS over-penalized which allows to obtain a minimax regret bound. A second work will be to understand the convergence in law of this process. The particularity of the algorith is that it converges in law toward a non-diffusive process which makes the study more intricate than the standard case. We will use coupling techniques to study this process and propose rates of convergence. The second work of this thesis falls in the scope of optimization of a function using a stochastic algorithm. We will study a stochastic version of the so-called heavy bali method with friction. The particularity of the algorithm is that its dynamics is based on the ali past of the trajectory. The procedure relies on a memory term which dictates the behavior of the procedure by the form it takes. In our framework, two types of memory will investigated : polynomial and exponential. We will start with general convergence results in the non-convex case. In the case of strongly convex functions, we will provide upper-bounds for the rate of convergence. Finally, a convergence in law result is given in the case of exponential memory. The third part is about the McKean-Vlasov equations which were first introduced by Anatoly Vlasov and first studied by Henry McKean in order to mode! the distribution function of plasma. Our objective is to propose a stochastic algorithm to approach the invariant distribution of the McKean Vlasov equation. Methods in the case of diffusion processes (and sorne more general pro cesses) are known but the particularity of McKean Vlasov process is that it is strongly non-linear. Thus, we will have to develop an alternative approach. We will introduce the notion of asymptotic pseudotrajectory in odrer to get an efficient procedure

2

Faury, Louis. "Variance-sensitive confidence intervals for parametric and offline bandits". Electronic Thesis or Diss., Institut polytechnique de Paris, 2021. http://www.theses.fr/2021IPPAT046.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse présente des contributions récentes au problème d’optimisation sous feedback bandit, au travers de la construction d’intervalles de confiance sensibles à la variance. Nous traitons deux aspects distincts du problème: (1) la minimisation du regret pour les bandits à modèle linéaire généralisé (GLBs), une large classe de bandits paramétriques non-linéaires et (2) le problème d’optimisation de politique hors ligne sous signal bandit. Concernant (1) nous étudions les effets de la non-linéarité dans les GLBs et remettons en question la compréhension actuelle selon laquelle des hauts niveaux de non-linéarité ne peuvent être que préjudiciables à l’équilibre exploration-exploitation. Des algorithmes améliorés suivis d’une nouvelle méthode d’analyse montrent que lorsque correctement manipulé, le problème de minimisation du regret dans les GLBs n’est pas nécessairement plus dur que pour leur contrepartie linéaire. Il peut même être significativement facilité pour certains membres importants de la famille GLB comme le bandit logistique. Notre approche utilise de nouveaux ensembles de confiance sensibles à la non-linéarité au travers de la variance qu’elle impose à la fonction récompense, accompagnés d’un traitement local de la non-linéarité au travers d’une analyse dite auto-concordante. Concernant (2) nous utilisons des résultats de la littérature de l’optimisation robuste afin de construire des intervalles de confiance asymptotiques sensibles à la variance pour l’évaluation contrefactuelle de politiques. Cela permet d’assurer du conservatisme (désirable pour des agents averses au risque) lors de la recherche hors-ligne de politiques prometteuses. Cet intervalle de confiance engendre de nouveaux objectifs contrefactuels qui sont plus adaptés à des applications pratiques, car convexes et de nature composites
In this dissertation we present recent contributions to the problem of optimization under bandit feedback through the design of variance-sensitive confidence intervals. We tackle two distincts topics: (1) the regret minimization task in Generalized Linear Bandits (GLBs), a broad class of non-linear parametric bandits and (2) the problem of off-line policy optimization under bandit feedback. For (1) we study the effects of non-linearity in GLBs and challenge the current understanding that a high level of non-linearity is detrimental to the exploration-exploitation trade-off. We introduce improved algorithms as well as a novel analysis that prove that if correctly handled, the regret minimization task in GLBs is not necessarily harder than for their linear counterparts. It can even be easier for some important members of the GLB family such as the Logistic Bandit. Our approach leverages a new confidence set which captures the non-linearity of the reward signal through its variance, along with a local treatment of the non-linearity through a so-called self-concordance analysis. For (2) we leverage results from the distributionally robust optimization framework to construct asymptotic variance-sensitive confidence intervals for the counterfactual evaluation of policies. This allows to ensure conservatism (sought out by risk-averse agents) while searching off-line for promising policies. Our confidence intervals lead to new counterfactual objectives which, contrary to their predecessors, are more suited for practical deployment thanks to their convex and composite natures

3

Sani, Amir. "Apprentissage automatique pour la prise de décisions". Thesis, Lille 1, 2015. http://www.theses.fr/2015LIL10038/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

La prise de décision stratégique concernant des ressources de valeur devrait tenir compte du degré d'aversion au risque. D'ailleurs, de nombreux domaines d'application mettent le risque au cœur de la prise de décision. Toutefois, ce n'est pas le cas de l'apprentissage automatique. Ainsi, il semble essentiel de devoir fournir des indicateurs et des algorithmes dotant l'apprentissage automatique de la possibilité de prendre en considération le risque dans la prise de décision. En particulier, nous souhaiterions pouvoir estimer ce dernier sur de courtes séquences dépendantes générées à partir de la classe la plus générale possible de processus stochastiques en utilisant des outils théoriques d'inférence statistique et d'aversion au risque dans la prise de décision séquentielle. Cette thèse étudie ces deux problèmes en fournissant des méthodes algorithmiques prenant en considération le risque dans le cadre de la prise de décision en apprentissage automatique. Un algorithme avec des performances de pointe est proposé pour une estimation précise des statistiques de risque avec la classe la plus générale de processus ergodiques et stochastiques. De plus, la notion d'aversion au risque est introduite dans la prise de décision séquentielle (apprentissage en ligne) à la fois dans les jeux de bandits stochastiques et dans l'apprentissage séquentiel antagoniste
Strategic decision-making over valuable resources should consider risk-averse objectives. Many practical areas of application consider risk as central to decision-making. However, machine learning does not. As a result, research should provide insights and algorithms that endow machine learning with the ability to consider decision-theoretic risk. In particular, in estimating decision-theoretic risk on short dependent sequences generated from the most general possible class of processes for statistical inference and through decision-theoretic risk objectives in sequential decision-making. This thesis studies these two problems to provide principled algorithmic methods for considering decision-theoretic risk in machine learning. An algorithm with state-of-the-art performance is introduced for accurate estimation of risk statistics on the most general class of stationary--ergodic processes and risk-averse objectives are introduced in sequential decision-making (online learning) in both the stochastic multi-arm bandit setting and the adversarial full-information setting

4

Clement, Benjamin. "Adaptive Personalization of Pedagogical Sequences using Machine Learning". Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0373/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les ordinateurs peuvent-ils enseigner ? Pour répondre à cette question, la recherche dans les Systèmes Tuteurs Intelligents est en pleine expansion parmi la communauté travaillant sur les Technologies de l'Information et de la Communication pour l'Enseignement (TICE). C'est un domaine qui rassemble différentes problématiques et réunit des chercheurs venant de domaines variés, tels que la psychologie, la didactique, les neurosciences et, plus particulièrement, le machine learning. Les technologies numériques deviennent de plus en plus présentes dans la vie quotidienne avec le développement des tablettes et des smartphones. Il semble naturel d'utiliser ces technologies dans un but éducatif. Cela amène de nombreuses problématiques, telles que comment faire des interfaces accessibles à tous, comment rendre des contenus pédagogiques motivants ou encore comment personnaliser les activités afin d'adapter le contenu à chacun. Au cours de cette thèse, nous avons développé des méthodes, regroupées dans un framework nommé HMABITS, afin d'adapter des séquences d'activités pédagogiques en fonction des performances et des préférences des apprenants, dans le but de maximiser leur vitesse d'apprentissage et leur motivation. Ces méthodes utilisent des modèles computationnels de motivation intrinsèque pour identifier les activités offrant les plus grands progrès d'apprentissage, et utilisent des algorithmes de Bandits Multi-Bras pour gérer le compromis exploration/exploitation à l'intérieur de l'espace d'activité. Les activités présentant un intérêt optimal sont ainsi privilégiées afin de maintenir l'apprenant dans un état de Flow ou dans sa Zone de Développement Proximal. De plus, certaines de nos méthodes permettent à l'apprenant de faire des choix sur des caractéristiques contextuelles ou le contenu pédagogique de l'application, ce qui est un vecteur d'autodétermination et de motivation. Afin d'évaluer l'efficacité et la pertinence de nos algorithmes, nous avons mené plusieurs types d'expérimentation. Nos méthodes ont d'abord été testées en simulation afin d'évaluer leur fonctionnement avant de les utiliser dans d'actuelles applications d'apprentissage. Pour ce faire, nous avons développé différents modèles d'apprenants, afin de pouvoir éprouver nos méthodes selon différentes approches, un modèle d'apprenant virtuel ne reflétant jamais le comportement d'un apprenant réel. Les résultats des simulations montrent que le framework HMABITS permet d'obtenir des résultats d'apprentissage comparables et, dans certains cas, meilleurs qu'une solution optimale ou qu'une séquence experte. Nous avons ensuite développé notre propre scénario pédagogique et notre propre serious game afin de tester nos algorithmes en situation réelle avec de vrais élèves. Nous avons donc développé un jeu sur la thématique de la décomposition des nombres, au travers de la manipulation de la monnaie, pour les enfants de 6 à 8 ans. Nous avons ensuite travaillé avec le rectorat et différentes écoles de l'académie de bordeaux. Sur l'ensemble des expérimentations, environ 1000 élèves ont travaillé sur l'application sur tablette. Les résultats des études en situation réelle montrent que le framework HMABITS permet aux élèves d'accéder à des activités plus diverses et plus difficiles, d'avoir un meilleure apprentissage et d'être plus motivés qu'avec une séquence experte. Les résultats montrent même que ces effets sont encore plus marqués lorsque les élèves ont la possibilité de faire des choix
Can computers teach people? To answer this question, Intelligent Tutoring Systems are a rapidly expanding field of research among the Information and Communication Technologies for the Education community. This subject brings together different issues and researchers from various fields, such as psychology, didactics, neurosciences and, particularly, machine learning. Digital technologies are becoming more and more a part of everyday life with the development of tablets and smartphones. It seems natural to consider using these technologies for educational purposes. This raises several questions, such as how to make user interfaces accessible to everyone, how to make educational content motivating and how to customize it to individual learners. In this PhD, we developed methods, grouped in the aptly-named HMABITS framework, to adapt pedagogical activity sequences based on learners' performances and preferences to maximize their learning speed and motivation. These methods use computational models of intrinsic motivation and curiosity-driven learning to identify the activities providing the highest learning progress and use Multi-Armed Bandit algorithms to manage the exploration/exploitation trade-off inside the activity space. Activities of optimal interest are thus privileged with the target to keep the learner in a state of Flow or in his or her Zone of Proximal Development. Moreover, some of our methods allow the student to make choices about contextual features or pedagogical content, which is a vector of self-determination and motivation. To evaluate the effectiveness and relevance of our algorithms, we carried out several types of experiments. We first evaluated these methods with numerical simulations before applying them to real teaching conditions. To do this, we developed multiple models of learners, since a single model never exactly replicates the behavior of a real learner. The simulation results show the HMABITS framework achieves comparable, and in some cases better, learning results than an optimal solution or an expert sequence. We then developed our own pedagogical scenario and serious game to test our algorithms in classrooms with real students. We developed a game on the theme of number decomposition, through the manipulation of money, for children aged 6 to 8. We then worked with the educational institutions and several schools in the Bordeaux school district. Overall, about 1000 students participated in trial lessons using the tablet application. The results of the real-world studies show that the HMABITS framework allows the students to do more diverse and difficult activities, to achieve better learning and to be more motivated than with an Expert Sequence. The results show that this effect is even greater when the students have the possibility to make choices

5

Maillard, Odalric-Ambrym. "APPRENTISSAGE SÉQUENTIEL : Bandits, Statistique et Renforcement". Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2011. http://tel.archives-ouvertes.fr/tel-00845410.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse traite des domaines suivant en Apprentissage Automatique: la théorie des Bandits, l'Apprentissage statistique et l'Apprentissage par renforcement. Son fil rouge est l'étude de plusieurs notions d'adaptation, d'un point de vue non asymptotique : à un environnement ou à un adversaire dans la partie I, à la structure d'un signal dans la partie II, à la structure de récompenses ou à un modèle des états du monde dans la partie III. Tout d'abord nous dérivons une analyse non asymptotique d'un algorithme de bandit à plusieurs bras utilisant la divergence de Kullback-Leibler. Celle-ci permet d'atteindre, dans le cas de distributions à support fini, la borne inférieure de performance asymptotique dépendante des distributions de probabilité connue pour ce problème. Puis, pour un bandit avec un adversaire possiblement adaptatif, nous introduisons des modèles dépendants de l'histoire et traduisant une possible faiblesse de l'adversaire et montrons comment en tirer parti pour concevoir des algorithmes adaptatifs à cette faiblesse. Nous contribuons au problème de la régression en montrant l'utilité des projections aléatoires, à la fois sur le plan théorique et pratique, lorsque l'espace d'hypothèses considéré est de dimension grande, voire infinie. Nous utilisons également des opérateurs d'échantillonnage aléatoires dans le cadre de la reconstruction parcimonieuse lorsque la base est loin d'être orthogonale. Enfin, nous combinons la partie I et II : pour fournir une analyse non-asymptotique d'algorithmes d'apprentissage par renforcement; puis, en amont du cadre des Processus Décisionnel de Markov, pour discuter du problème pratique du choix d'un bon modèle d'états.

6

Dorard, L. R. M. "Bandit algorithms for searching large spaces". Thesis, University College London (University of London), 2012. http://discovery.ucl.ac.uk/1348319/.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Bandit games consist of single-state environments in which an agent must sequentially choose actions to take, for which rewards are given. The objective being to maximise the cumulated reward, the agent naturally seeks to build a model of the relationship between actions and rewards. The agent must both choose uncertain actions in order to improve its model (exploration), and actions that are believed to yield high rewards according to the model (exploitation). The choice of an action to take is called a play of an arm of the bandit, and the total number of plays may or may not be known in advance. Algorithms designed to handle the exploration-exploitation dilemma were initially motivated by problems with rather small numbers of actions. But the ideas they were based on have been extended to cases where the number of actions to choose from is much larger than the maximum possible number of plays. Several problems fall into this setting, such as information retrieval with relevance feedback, where the system must learn what a user is looking for while serving relevant documents often enough, but also global optimisation, where the search for an optimum is done by selecting where to acquire potentially expensive samples of a target function. All have in common the search of large spaces. In this thesis, we focus on an algorithm based on the Gaussian Processes probabilistic model, often used in Bayesian optimisation, and the Upper Confidence Bound action-selection heuristic that is popular in bandit algorithms. In addition to demonstrating the advantages of the GP-UCB algorithm on an image retrieval problem, we show how it can be adapted in order to search tree-structured spaces. We provide an efficient implementation, theoretical guarantees on the algorithm's performance, and empirical evidence that it handles large branching factors better than previous bandit-based algorithms, on synthetic trees.

7

Jedor, Matthieu. "Bandit algorithms for recommender system optimization". Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM027.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse de doctorat, nous étudions l'optimisation des systèmes de recommandation dans le but de fournir des suggestions de produits plus raffinées pour un utilisateur.La tâche est modélisée à l'aide du cadre des bandits multi-bras.Dans une première partie, nous abordons deux problèmes qui se posent fréquemment dans les systèmes de recommandation : le grand nombre d'éléments à traiter et la gestion des contenus sponsorisés.Dans une deuxième partie, nous étudions les performances empiriques des algorithmes de bandit et en particulier comment paramétrer les algorithmes traditionnels pour améliorer les résultats dans les environnements stationnaires et non stationnaires qui l'on rencontre en pratique.Cela nous amène à analyser à la fois théoriquement et empiriquement l'algorithme glouton qui, dans certains cas, est plus performant que l'état de l'art
In this PhD thesis, we study the optimization of recommender systems with the objective of providing more refined suggestions of items for a user to benefit.The task is modeled using the multi-armed bandit framework.In a first part, we look upon two problems that commonly occured in recommendation systems: the large number of items to handle and the management of sponsored contents.In a second part, we investigate the empirical performance of bandit algorithms and especially how to tune conventional algorithm to improve results in stationary and non-stationary environments that arise in practice.This leads us to analyze both theoretically and empirically the greedy algorithm that, in some cases, outperforms the state-of-the-art

8

Besson, Lilian. "Multi-Players Bandit Algorithms for Internet of Things Networks". Thesis, CentraleSupélec, 2019. http://www.theses.fr/2019CSUP0005.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse de doctorat, nous étudions les réseaux sans fil et les appareils reconfigurables qui peuvent accéder à des réseaux de type radio intelligente, dans des bandes non licenciées et sans supervision centrale. Nous considérons notamment des réseaux actuels ou futurs de l’Internet des Objets (IoT), avec l’objectif d’augmenter la durée de vie de la batterie des appareils, en les équipant d’algorithmes d’apprentissage machine peu coûteux mais efficaces, qui leur permettent d’améliorer automatiquement l’efficacité de leurs communications sans fil. Nous proposons deux modèles de réseaux IoT, et nous montrons empiriquement, par des simulations numériques et une validation expérimentale réaliste, le gain que peuvent apporter nos méthodes, qui se reposent sur l’apprentissage par renforcement. Les différents problèmes d’accès au réseau sont modélisés avec des Bandits Multi-Bras (MAB), mais l’analyse de la convergence d’un grand nombre d’appareils jouant à un jeu collaboratif sans communication ni aucune coordination reste délicate, lorsque les appareils suivent tous un modèle d’activation aléatoire. Le reste de ce manuscrit étudie donc deux modèles restreints, d’abord des banditsmulti-joueurs dans des problèmes stationnaires, puis des bandits mono-joueur non stationnaires. Nous détaillons également une autre contribution, la bibliothèque Python open-source SMPyBandits, qui permet des simulations numériques de problèmes MAB, qui couvre les modèles étudiés et d’autres
In this PhD thesis, we study wireless networks and reconfigurable end-devices that can access Cognitive Radio networks, in unlicensed bands and without central control. We focus on Internet of Things networks (IoT), with the objective of extending the devices’ battery life, by equipping them with low-cost but efficient machine learning algorithms, in order to let them automatically improve the efficiency of their wireless communications. We propose different models of IoT networks, and we show empirically on both numerical simulations and real-world validation the possible gain of our methods, that use Reinforcement Learning. The different network access problems are modeled as Multi-Armed Bandits (MAB), but we found that analyzing the realistic models was intractable, because proving the convergence of many IoT devices playing a collaborative game, without communication nor coordination is hard, when they all follow random activation patterns. The rest of this manuscript thus studies two restricted models, first multi-players bandits in stationary problems, then non-stationary single-player bandits. We also detail another contribution, SMPyBandits, our open-source Python library for numerical MAB simulations, that covers all the studied models and more

9

Deffayet, Romain. "Bandit Algorithms for Adaptive Modulation and Coding in Wireless Networks". Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-281884.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

The demand for quality cellular network coverage has been increasing significantly in the recent years and will continue its progression throughout the near future. This results from an increase of transmitted data, because of new use cases (HD videos, live streaming, online games, ...), but also from a diversification of the traffic, notably because of shorter and more frequent transmissions which can be due to IOT devices or other telemetry applications. The cellular networks are becoming increasingly complex, and the need for better management of the network’s properties is higher than ever. The combined effect of these two paradigms creates a trade-off : whereas one would like to design algorithms that achieve high performance decision-making, one would also like those to be able to do so in any settings that can be encountered in this complex network. Instead, this thesis proposes to restrict the scope of the decision-making algorithms through on-line learning. The thesis focuses on the context of initial MCS selection in Adaptive Modulation and Coding, in which one must choose an initial transmission rate guaranteeing fast communications and low error rate. We formulate the problem as a Reinforcement Learning problem, and propose relevant restrictions to simpler frameworks like Multi-Armed Bandits and Contextual Bandits. Eight bandit algorithms are tested and reviewed with emphasis on practical applications. The thesis shows that a Reinforcement Learning agent can improve the utilization of the link capacity between the transmitter and the receiver. First, we present a cell-wide Multi-Armed Bandit agent, which learns the optimal initial offset in a given cell, and then a contextual augmentation of this agent taking user-specific features as input. The proposed method achieves with burst traffic an 8% increase of the median throughput and 65% reduction of the median regret in the first 0:5s of transmission, when compared to a fixed baseline.
Efterfrågan på mobilnät av hög kvalitet har ökat mycket de senaste åren och kommer att fortsätta öka under en nära framtid. Detta är resultatet av en ökad mängd trafik på grund av nya användningsfall (HD-videor, live streaming, onlinespel, ...) men kommer också från en diversifiering av trafiken, i synnerhet på grund av kortare och mer frekventa sändningar vilka kan vara på grund av IOT-enheter eller andra telemetri-applikationer. Mobilnätet blir allt komplexare och behovet av bättre hantering av nätverkets egenskaper är högre än någonsin. Den kombinerade effekten av dessa två paradigmer skapar en avvägning: medan man vill utforma algoritmer som uppnår mycket hög prestanda vid beslutsfattning, skulle man också vilja att algoritmerna kan göra det i alla konfigurationer som kan uppstå i detta komplexa nätverk. Istället föreslår denna avhandling att begränsa omfattningen av beslutsalgoritmerna genom att introducera online-inlärning. Avhandlingen fokuserar på första MCS-valet i Adaptiv Modulering och Kodning, där man måste välja en initial överföringshastighet som garanterar snabb kommunikation och minsta möjliga transmissionsfel. Vi formulerar problemet som ett Reinforcement Learning problem och föreslår relevanta begränsningar för matematikt enklare ramverk som Multi-Armed Bandits och Contextual Bandits. Åtta banditalgoritmer testas och granskas med hänsyn till praktisk tillämpning. Avhandlingen visar att en Reinforcement Learning agent kan förbättra användningen av länkkapaciteten mellan sändare och mottagare. Först presenterar vi en Multi-Armed Bandit agent på cell-nivå, som lär sig den optimala initiala MCSen i en given cell och sedan en kontextuell utvidgning av dennaa agent med användarspecifika funktioner. Den föreslagna metoden uppnår en åttaprocentig (8%) ökning av medianhastigheten och en sextiofemprocentig (65%) minskning av median ångern vid skurvis trafik det första 0.5s av tranmissionen, jämfört med ett fast referensvärde.

10

Degenne, Rémy. "Impact of structure on the design and analysis of bandit algorithms". Thesis, Université de Paris (2019-....), 2019. http://www.theses.fr/2019UNIP7179.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse porte sur des problèmes d'apprentissage statistique séquentiel, dits bandits stochastiques à plusieurs bras. Dans un premier temps un algorithme de bandit est présenté. L'analyse de cet algorithme, comme la majorité des preuves usuelles de bornes de regret pour algorithmes de bandits, utilise des intervalles de confiance pour les moyennes des bras. Dans un cadre paramétrique,on prouve des inégalités de concentration quantifiant la déviation entre le paramètre d'une distribution et son estimation empirique, afin d'obtenir de tels intervalles. Ces inégalités sont exprimées en fonction de la divergence de Kullback-Leibler. Trois extensions du problème de bandits sont ensuite étudiées. Premièrement on considère le problème dit de semi-bandit combinatoire, dans lequel un algorithme choisit un ensemble de bras et la récompense de chaque bras est observée. Le regret minimal atteignable dépend alors de la corrélation entre les bras. On considère ensuite un cadre où on change le mécanisme d'obtention des observations provenant des différents bras. Une source de difficulté du problème de bandits est la rareté de l'information: seul le bras choisi est observé. On montre comment on peut tirer parti de la disponibilité d'observations supplémentaires gratuites, ne participant pas au regret. Enfin, une nouvelle famille d'algorithmes est présentée afin d'obtenir à la fois des guaranties de minimisation de regret et d'identification du meilleur bras. Chacun des algorithmes réalise un compromis entre regret et temps d'identification. On se penche dans un deuxième temps sur le problème dit d'exploration pure, dans lequel un algorithme n'est pas évalué par son regret mais par sa probabilité d'erreur quant à la réponse à une question posée sur le problème. On détermine la complexité de tels problèmes et on met au point des algorithmes approchant cette complexité
In this Thesis, we study sequential learning problems called stochastic multi-armed bandits. First a new bandit algorithm is presented. The analysis of that algorithm uses confidence intervals on the mean of the arms reward distributions, as most bandit proofs do. In a parametric setting, we derive concentration inequalities which quantify the deviation between the mean parameter of a distribution and its empirical estimation in order to obtain confidence intervals. These inequalities are presented as bounds on the Kullback-Leibler divergence. Three extensions of the stochastic multi-armed bandit problem are then studied. First we study the so-called combinatorial semi-bandit problem, in which an algorithm chooses a set of arms and the reward of each of these arms is observed. The minimal attainable regret then depends on the correlation between the arm distributions. We consider then a setting in which the observation mechanism changes. One source of difficulty of the bandit problem is the scarcity of information: only the arm pulled is observed. We show how to use efficiently eventual supplementary free information (which do not influence the regret). Finally a new family of algorithms is introduced to obtain both regret minimization and est arm identification regret guarantees. Each algorithm of the family realizes a trade-off between regret and time needed to identify the best arm. In a second part we study the so-called pure exploration problem, in which an algorithm is not evaluated on its regret but on the probability that it returns a wrong answer to a question on the arm distributions. We determine the complexity of such problems and design with performance close to that complexity

11

Nicol, Olivier. "Data-driven evaluation of contextual bandit algorithms and applications to dynamic recommendation". Thesis, Lille 1, 2014. http://www.theses.fr/2014LIL10211/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Ce travail de thèse a été réalisé dans le contexte de la recommandation dynamique. La recommandation est l'action de fournir du contenu personnalisé à un utilisateur utilisant une application, dans le but d'améliorer son utilisation e.g. la recommandation d'un produit sur un site marchant ou d'un article sur un blog. La recommandation est considérée comme dynamique lorsque le contenu à recommander ou encore les goûts des utilisateurs évoluent rapidement e.g. la recommandation d'actualités. Beaucoup d'applications auxquelles nous nous intéressons génèrent d'énormes quantités de données grâce à leurs millions d'utilisateurs sur Internet. Néanmoins, l'utilisation de ces données pour évaluer une nouvelle technique de recommandation ou encore comparer deux algorithmes de recommandation est loin d'être triviale. C'est cette problématique que nous considérons ici. Certaines approches ont déjà été proposées. Néanmoins elles sont très peu étudiées autant théoriquement (biais non quantifié, borne de convergence assez large...) qu'empiriquement (expériences sur données privées). Dans ce travail nous commençons par combler de nombreuses lacunes de l'analyse théorique. Ensuite nous discutons les résultats très surprenants d'une expérience à très grande échelle : une compétition ouverte au public que nous avons organisée. Cette compétition nous a permis de mettre en évidence une source de biais considérable et constamment présente en pratique : l'accélération temporelle. La suite de ce travail s'attaque à ce problème. Nous montrons qu'une approche à base de bootstrap permet de réduire mais surtout de contrôler ce biais
The context of this thesis work is dynamic recommendation. Recommendation is the action, for an intelligent system, to supply a user of an application with personalized content so as to enhance what is refered to as "user experience" e.g. recommending a product on a merchant website or even an article on a blog. Recommendation is considered dynamic when the content to recommend or user tastes evolve rapidly e.g. news recommendation. Many applications that are of interest to us generates a tremendous amount of data through the millions of online users they have. Nevertheless, using this data to evaluate a new recommendation technique or even compare two dynamic recommendation algorithms is far from trivial. This is the problem we consider here. Some approaches have already been proposed. Nonetheless they were not studied very thoroughly both from a theoretical point of view (unquantified bias, loose convergence bounds...) and from an empirical one (experiments on private data only). In this work we start by filling many blanks within the theoretical analysis. Then we comment on the result of an experiment of unprecedented scale in this area: a public challenge we organized. This challenge along with a some complementary experiments revealed a unexpected source of a huge bias: time acceleration. The rest of this work tackles this issue. We show that a bootstrap-based approach allows to significantly reduce this bias and more importantly to control it

12

Zhong, Hongliang. "Bandit feedback in Classification and Multi-objective Optimization". Thesis, Ecole centrale de Marseille, 2016. http://www.theses.fr/2016ECDM0004/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Des problèmes de Bandit constituent une séquence d’allocation dynamique. D’une part, l’agent de système doit explorer son environnement ( à savoir des bras de machine) pour recueillir des informations; d’autre part, il doit exploiter les informations collectées pour augmenter la récompense. Comment d’équilibrer adéquatement la phase d’exploration et la phase d’exploitation, c’est une obscurité des problèmes de Bandit, et la plupart des chercheurs se concentrent des efforts sur les stratégies d’équilibration entre l’exploration et l’exploitation. Dans cette dissertation, nous nous concentrons sur l’étude de deux problèmes spécifiques de Bandit: les problèmes de Bandit contextuel et les problèmes de Bandit Multi- objectives. Cette dissertation propose deux aspects de contributions. La première concerne la classification sous la surveillance partielle, laquelle nous codons comme le problème de Bandit contextuel avec des informations partielles. Ce type des problèmes est abondamment étudié par des chercheurs, en appliquant aux réseaux sociaux ou systèmes de recommandation. Nous proposons une série d’algorithmes sur la base d’algorithme Passive-Aggressive pour résoudre des problèmes de Bandit contextuel. Nous profitons de sa fondations, et montrons que nos algorithmes sont plus simples à mettre en œuvre que les algorithmes en état de l’art. Ils réalisent des biens performances de classification. Pour des problèmes de Bandit Multi-objective (MOMAB), nous proposons une méthode motivée efficace et théoriquement à identifier le front de Pareto entre des bras. En particulier, nous montrons que nous pouvons trouver tous les éléments du front de Pareto avec un budget minimal dans le cadre de PAC borne
Bandit problems constitute a sequential dynamic allocation problem. The pulling agent has to explore its environment (i.e. the arms) to gather information on the one hand, and it has to exploit the collected clues to increase its rewards on the other hand. How to adequately balance the exploration phase and the exploitation phase is the crux of bandit problems and most of the efforts devoted by the research community from this fields has focused on finding the right exploitation/exploration tradeoff. In this dissertation, we focus on investigating two specific bandit problems: the contextual bandit problems and the multi-objective bandit problems. This dissertation provides two contributions. The first contribution is about the classification under partial supervision, which we encode as a contextual bandit problem with side informa- tion. This kind of problem is heavily studied by researchers working on social networks and recommendation systems. We provide a series of algorithms to solve the Bandit feedback problem that pertain to the Passive-Aggressive family of algorithms. We take advantage of its grounded foundations and we are able to show that our algorithms are much simpler to implement than state-of-the-art algorithms for bandit with partial feedback, and they yet achieve better perfor- mances of classification. For multi-objective multi-armed bandit problem (MOMAB), we propose an effective and theoretically motivated method to identify the Pareto front of arms. We in particular show that we can find all elements of the Pareto front with a minimal budget

13

Gajane, Pratik. "Multi-armed bandits with unconventional feedback". Thesis, Lille 3, 2017. http://www.theses.fr/2017LIL30045/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse, nous étudions des problèmes de prise de décisions séquentielles dans lesquels, pour chacune de ses décisions, l'apprenant reçoit une information qu'il utilise pour guider ses décisions futures. Pour aller au-delà du retour d’information conventionnel tel qu'il a été bien étudié pour des problèmes de prise de décision séquentielle tels que les bandits multi-bras, nous considérons des formes de retour d’information partielle motivées par des applications pratiques.En premier, nous considérons le problème des bandits duellistes, dans lequel l'apprenant sélectionne deux actions à chaque pas de temps et reçoit en retour une information relative (i.e. de préférence) entre les valeurs instantanées de ces deux actions.En particulier, nous proposons un algorithme optimal qui permet à l'apprenant d'obtenir un regret cumulatif quasi-optimal (le regret est la différence entre la récompense cumulative optimale et la récompense cumulative constatée de l’apprenant). Dans un second temps, nous considérons le problème des bandits corrompus, dans lequel un processus de corruption stochastique perturbe le retour d’information. Pour ce problème aussi, nous concevons des algorithmes pour obtenir un regret cumulatif asymptotiquement optimal. En outre, nous examinons la relation entre ces deux problèmes dans le cadre du monitoring partiel qui est un paradigme générique pour la prise de décision séquentielle avec retour d'information partielle
The multi-armed bandit (MAB) problem is a mathematical formulation of the exploration-exploitation trade-off inherent to reinforcement learning, in which the learner chooses an action (symbolized by an arm) from a set of available actions in a sequence of trials in order to maximize their reward. In the classical MAB problem, the learner receives absolute bandit feedback i.e. it receives as feedback the reward of the arm it selects. In many practical situations however, different kind of feedback is more readily available. In this thesis, we study two of such kinds of feedbacks, namely, relative feedback and corrupt feedback.The main practical motivation behind relative feedback arises from the task of online ranker evaluation. This task involves choosing the optimal ranker from a finite set of rankers using only pairwise comparisons, while minimizing the comparisons between sub-optimal rankers. This is formalized by the MAB problem with relative feedback, in which the learner selects two arms instead of one and receives the preference feedback. We consider the adversarial formulation of this problem which circumvents the stationarity assumption over the mean rewards for the arms. We provide a lower bound on the performance measure for any algorithm for this problem. We also provide an algorithm called "Relative Exponential-weight algorithm for Exploration and Exploitation" with performance guarantees. We present a thorough empirical study on several information retrieval datasets that confirm the validity of these theoretical results.The motivating theme behind corrupt feedback is that the feedback the learner receives is a corrupted form of the corresponding reward of the selected arm. Practically such a feedback is available in the tasks of online advertising, recommender systems etc. We consider two goals for the MAB problem with corrupt feedback: best arm identification and exploration-exploitation. For both the goals, we provide lower bounds on the performance measures for any algorithm. We also provide various algorithms for these settings. The main contribution of this module is the algorithms "KLUCB-CF" and "Thompson Sampling-CF" which asymptotically attain the best possible performance. We present experimental results to demonstrate the performance of these algorithms. We also show how this problem setting can be used for the practical application of enforcing differential privacy

14

Soare, Marta. "Sequential resources allocation in linear stochastic bandits". Thesis, Lille 1, 2015. http://www.theses.fr/2015LIL10147/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse nous étudions des problèmes d'allocation de ressources dans des environnements incertains où un agent choisit ses actions séquentiellement. Après chaque pas, l'environnement fournit une observation bruitée sur la valeur de l'action choisie et l'agent doit utiliser ces observations pour allouer ses ressources de façon optimale. Dans le cadre le plus classique, dit modèle du bandit à plusieurs bras (MAB), on fait l'hypothèse que chaque observation est tirée aléatoirement d'une distribution de probabilité associée à l'action choisie et ne fournit aucune information sur les valeurs espérées des autres actions disponibles dans l'environnement. Ce modèle a été largement étudié dans la littérature et plusieurs stratégies optimales ont été proposées, notamment pour le cas où le but de l'agent est de maximiser la somme des observations. Ici, nous considérons une version du MAB où les actions ne sont plus indépendantes, mais chaque observation peut être utilisée pour estimer les valeurs de l'ensemble des actions de l'environnement. Plus précisément, nous proposons des stratégies d'allocation de ressources qui sont efficaces et adaptées à un environnement caractérisé par une structure linéaire globale. Nous étudions notamment les séquences d'actions qui mènent à : (i) identifier la meilleure action avec une précision donnée et en utilisant un nombre minimum d'observations, ou (ii) maximiser la précision d'estimation des valeurs de chaque action. De plus, nous étudions les cas où les observations provenant d'un algorithme de bandit dans un environnement donné peuvent améliorer par la suite la performance de l'agent dans d'autres environnements similaires
This thesis is dedicated to the study of resource allocation problems in uncertain environments, where an agent can sequentially select which action to take. After each step, the environment returns a noisy observation of the value of the selected action. These observations guide the agent in adapting his resource allocation strategy towards reaching a given objective. In the most typical setting of this kind, the stochastic multi-armed bandit (MAB), it is assumed that each observation is drawn from an unknown probability distribution associated with the selected action and gives no information on the expected value of the other actions. This setting has been widely studied and optimal allocation strategies were proposed to solve various objectives under the MAB assumptions. Here, we consider a variant of the MAB setting where there exists a global linear structure in the environment and by selecting an action, the agent also gathers information on the value of the other actions. Therefore, the agent needs to adapt his resource allocation strategy to exploit the structure in the environment. In particular, we study the design of sequences of actions that the agent should take to reach objectives such as: (i) identifying the best value with a fixed confidence and using a minimum number of pulls, or (ii) minimizing the prediction error on the value of each action. In addition, we investigate how the knowledge gathered by a bandit algorithm in a given environment can be transferred to improve the performance in other similar environments

15

Brégère, Margaux. "Stochastic bandit algorithms for demand side management Simulating Tariff Impact in Electrical Energy Consumption Profiles with Conditional Variational Autoencoders Online Hierarchical Forecasting for Power Consumption Data Target Tracking for Contextual Bandits : Application to Demand Side Management". Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM022.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

L'électricité se stockant difficilement à grande échelle, l'équilibre entre la production et la consommation doit être rigoureusement maintenu. Une gestion par anticipation de la demande se complexifie avec l'intégration au mix de production des énergies renouvelables intermittentes. Parallèlement, le déploiement des compteurs communicants permet d'envisager un pilotage dynamique de la consommation électrique. Plus concrètement, l'envoi de signaux - tels que des changements du prix de l'électricité – permettrait d'inciter les usagers à moduler leur consommation afin qu'elle s'ajuste au mieux à la production d'électricité. Les algorithmes choisissant ces signaux devront apprendre la réaction des consommateurs face aux envois tout en les optimisant (compromis exploration-exploitation). Notre approche, fondée sur la théorie des bandits, a permis de formaliser ce problème d'apprentissage séquentiel et de proposer un premier algorithme pour piloter la demande électrique d'une population homogène de consommateurs. Une borne supérieure d'ordre T⅔ a été obtenue sur le regret de cet algorithme. Des expériences réalisées sur des données de consommation de foyers soumis à des changements dynamiques du prix de l'électricité illustrent ce résultat théorique. Un jeu de données en « information complète » étant nécessaire pour tester un algorithme de bandits, un simulateur de données de consommation fondé sur les auto-encodeurs variationnels a ensuite été construit. Afin de s'affranchir de l'hypothèse d'homogénéité de la population, une approche pour segmenter les foyers en fonction de leurs habitudes de consommation est aussi proposée. Ces différents travaux sont finalement combinés pour proposer et tester des algorithmes de bandits pour un pilotage personnalisé de la consommation électrique
As electricity is hard to store, the balance between production and consumption must be strictly maintained. With the integration of intermittent renewable energies into the production mix, the management of the balance becomes complex. At the same time, the deployment of smart meters suggests demand response. More precisely, sending signals - such as changes in the price of electricity - would encourage users to modulate their consumption according to the production of electricity. The algorithms used to choose these signals have to learn consumer reactions and, in the same time, to optimize them (exploration-exploration trade-off). Our approach is based on bandit theory and formalizes this sequential learning problem. We propose a first algorithm to control the electrical demand of a homogeneous population of consumers and offer T⅔ upper bound on its regret. Experiments on a real data set in which price incentives were offered illustrate these theoretical results. As a “full information” dataset is required to test bandit algorithms, a consumption data generator based on variational autoencoders is built. In order to drop the assumption of the population homogeneity, we propose an approach to cluster households according to their consumption profile. These different works are finally combined to propose and test a bandit algorithm for personalized demand side management

16

Bouttier, Clément. "Optimisation globale sous incertitude : algorithmes stochastiques et bandits continus avec application aux performances avion". Thesis, Toulouse 3, 2017. http://www.theses.fr/2017TOU30176.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse est consacrée à l'étude théorique et numérique d'algorithmes d'optimisation stochastiques adaptés au traitement du problème de planification des trajectoires d'avions en environnement incertain. L'optimisation des temps de vol et de la consommation de carburant est un élément central de la compétitivité des compagnies aériennes. Elles sont à la recherche d'outils permettant d'optimiser le choix de leurs routes aériennes avec toujours plus de précision. Pourtant, les méthodes actuellement disponibles pour l'optimisation de ces routes aériennes requièrent l'utilisation de représentations simplifiées des performances avion. Nous proposons, dans cette thèse, de répondre à cette exigence de précision et d'adapter, par conséquent, nos méthodes de résolution aux contraintes de la modélisation industrielle des performances avion tout en tenant compte de l'incertitude qui pèse sur les conditions réelles de vol (trafic aérien et conditions atmosphériques). Nous appuyons notre démarche par trois contributions scientifiques. Premièrement, nous avons mis en place un environnement de test pour algorithmes d'optimisation de trajectoires. Ce cadre a permis d'unifier la procédure de test pour l'ensemble des modèles de performances avion. Deuxièmement, nous avons développé et analysé sur le plan théorique deux nouveaux algorithmes d'optimisation stochastique globale en l'absence de dérivés. La première approche, très générique, n'utilise pas d'information particulière liée à la dynamique avion. Il s'agit de l'algorithme NSA basé sur la méthode du recuit simulé. Les développements théoriques ont abouti à la formulation des conditions et vitesse de convergence de cet algorithme. La seconde approche, l'algorithme SPY, est plus spécifique, il utilise une information de régularité lipschitzienne autour de l'optimum recherche. Il s'agit d'un algorithme de type bandits Lipschitz, basé sur la méthode de Piyavskii. De même, nous analysons les conditions de convergence de cet algorithme et fournissons une borne supérieure sur son erreur d'optimisation (regret simple)
This PhD thesis is dedicated to the theoretical and numerical analysis of stochastic algorithms for the stochastic flight planning problem. Optimizing the fuel consumption and flight time is a key factor for airlines to be competitive. These companies thus look for flight optimization tools with higher and higher accuracy requirements. However, nowadays available methodologies for flight planning are based on simplified aircraft performance models. In this PhD, we propose to fulfill the accuracy requirements by adapting our methodology to both the constraints induced by the utilization of an industrial aircraft performance computation code and the consideration of the uncertainty about the real flight conditions, i.e., air traffic and weather conditions. Our proposal is supported by three main contributions. First, we design a numerical framework for benchmarking aircraft trajectory optimization tools. This provides us a unified testing procedure for all aircraft performance models. Second, we propose and study (both theoretically and numerically) two global derivative-free algorithms for stochastic optimization problems. The first approach, the NSA algorithm, is highly generic and does not use any prior knowledge about the aircraft performance model. It is an extension of the simulated annealing algorithm adapted to noisy cost functions. We provide an upper bound on the convergence speed of NSA to globally optimal solutions. The second approach, the SPY algorithm, is a Lipschitz bandit algorithm derived from Piyavskii's algorithm. It is more specific as it requires the knowledge of some Lipschitz regularity property around the optimum, but it is therefore far more efficient. We also provide a theoretical study of this algorithm through an upper bound on its simple regret

17

Gisselbrecht, Thibault. "Algorithmes de bandits pour la collecte d’informations en temps réel dans les réseaux sociaux". Electronic Thesis or Diss., Paris 6, 2017. http://www.theses.fr/2017PA066655.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse, nous nous intéressons au problème de la collecte de données en temps réel dans les médias sociaux. En raison des différentes limitations imposées par ces médias, mais aussi de la quantité très importante de données, il n’est pas envisageable de collecter la totalité des données produites par des sites tels que Twitter. Par conséquent, pour être en mesure de récolter des informations pertinentes, relativement à un besoin prédéfini, il est nécessaire de se focaliser sur un sous-ensemble des données existantes. Dans ce travail, nous considérons chaque utilisateur d’un réseau social comme une source de données pouvant être écoutée à chaque itération d’un processus de collecte, en vue de capturer les données qu’elle produit. Ce processus, dont le but est de maximiser la qualité des informations récoltées, est contraint à chaque pas de temps par le nombre d’utilisateurs pouvant être écoutés simultanément. Le problème de sélection du sous-ensemble de comptes à écouter au fil du temps constitue un problème de décision séquentielle sous contraintes, que nous formalisons comme un problème de bandit avec sélections multiples. Dans cette optique, nous proposons plusieurs modèles visant à identifier en temps réel les utilisateurs les plus pertinents. Dans un premier temps, le cas du bandit dit stochastique, dans lequel chaque utilisateur est associé à une distribution de probabilité stationnaire, est étudié. Par la suite, nous étudions deux modèles de bandit contextuel, l’un stationnaire et l’autre non stationnaire, dans lesquels l’utilité de chaque utilisateur peut être estimée de façon plus efficace en supposant une certaine structure, permettant ainsi de mutualiser l’apprentissage. En particulier, la première approche introduit la notion de profil, qui correspond au comportement moyen de chaque utilisateur. La seconde approche prend en compte l’activité d’un utilisateur à un instant donné pour prédire son comportement futur. Pour finir, nous nous intéressons à des modèle permettant de prendre en compte des dépendances temporelles complexes entre les utilisateurs, grâce à des transitions entre états cachés du système d’une itération à la suivante. Chacune des approches proposées est validée sur des données artificielles et réelles
In this thesis, we study the problem of real time data capture on social media. Due to the different limitations imposed by those media, but also to the very large amount of information, it is not possible to collect all the data produced by social networks such as Twitter. Therefore, to be able to gather enough relevant information related to a predefined need, it is necessary to focus on a subset of the information sources. In this work, we focus on user-centered data capture and consider each account of a social network as a source that can be listened to at each iteration of a data capture process, in order to collect the corresponding produced contents. This process, whose aim is to maximize the quality of the information gathered, is constrained at each time step by the number of users that can be monitored simultaneously. The problem of selecting a subset of accounts to listen to over time is a sequential decision problem under constraints, which we formalize as a bandit problem with multiple selections. Therefore, we propose several bandit models to identify the most relevant users in real time. First, we study of the case of the so-called stochastic bandit, in which each user corresponds to a stationary distribution. Then, we introduce two contextual banditmodels, one stationary and the other non stationary, in which the utility of each user can be estimated more efficiently by assuming some underlying structure in the reward space. In particular, the first approach introduces the notion of profile, which corresponds to the average behavior of each user. On the other hand, the second approach takes into account the activity of a user at a given instant in order to predict his future behavior. Finally, we are interested in models that are able to take into account complex temporal dependencies between users, with the use of a latent space within which the information transits from one iteration to the other. Moreover, each of the proposed approaches is validated on both artificial and real datasets

18

Cuvelier, Thibaut. "Polynomial-Time Algorithms for Combinatorial Semibandits : Computationally Tractable Reinforcement Learning in Complex Environments". Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG020.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

La prise de décision séquentielle est une composante essentielle de nombreuses applications, de la gestion des réseaux informatiques aux annonces en ligne. L'outil principal est l'apprentissage par renforcement : un agent prend une séquence de décisions afin d'atteindre son objectif, avec des mesures typiquement bruitées de son environnement. Par exemple, un agent peut contrôler une voiture autonome; l'environnement est la ville dans laquelle la voiture se déplace. Les problèmes de bandits forment une classe d'apprentissage de renforcement pour laquelle on peut démontrer de très forts résultats théoriques. Les algorithmes de bandits se concentrent sur le dilemme exploration-exploitation : pour avoir une bonne performance, l'agent doit avoir une connaissance approfondie de son environnement (exploration) ; cependant, il doit aussi jouer des actions qui le rapprochent de son but (exploitation).Dans cette thèse, nous nous concentrons sur les bandits combinatoires, qui sont des bandits dont les décisions sont très structurées (une structure "combinatoire"). Il s'agit notamment des cas où l'agent détermine un chemin à suivre (sur une route, dans un réseau informatique, etc.) ou des publicités à afficher sur un site Web. De telles situations partagent leur complexité algorithmique : alors qu'il est souvent facile de déterminer la décision optimale lorsque les paramètres sont connus (le temps pour traverser une route, le profit généré par l'affichage d'une publicité à un endroit donné), la variante bandit (lorsque les paramètres doivent être déterminés par des interactions avec l'environnement) est bien plus complexe.Nous proposons deux nouveaux algorithmes pour aborder ces problèmes par des techniques d'optimisation mathématique. Basés sur des hypothèses faibles, ils présentent une complexité temporelle polynomiale, tout en étant performants par rapport aux algorithmes de pointe pour les mêmes problèmes. Ils présentent également d'excellentes propriétés statistiques, ce qui signifie qu'ils trouvent un équilibre entre exploration et exploitation proche de l'optimum théorique. Les travaux précédents sur les bandits combinatoires ont dû faire un choix entre le temps de calcul et la performance statistique ; nos algorithmes montrent que ce dilemme n'a pas lieu d'être
Sequential decision making is a core component of many real-world applications, from computer-network operations to online ads. The major tool for this use is reinforcement learning: an agent takes a sequence of decisions in order to achieve its goal, with typically noisy measurements of the evolution of the environment. For instance, a self-driving car can be controlled by such an agent; the environment is the city in which the car manœuvers. Bandit problems are a class of reinforcement learning for which very strong theoretical properties can be shown. The focus of bandit algorithms is on the exploration-exploitation dilemma: in order to have good performance, the agent must have a deep knowledge of its environment (exploration); however, it should also play actions that bring it closer to its goal (exploitation).In this dissertation, we focus on combinatorial bandits, which are bandits whose decisions are highly structured (a "combinatorial" structure). These include cases where the learning agent determines a path to follow (on a road, in a computer network, etc.) or ads to display on a Website. Such situations share their computational complexity: while it is often easy to determine the optimum decision when the parameters are known (the time to cross a road, the monetary gain of displaying an ad at a given place), the bandit variant (when the parameters must be determined through interactions with the environment) is more complex.We propose two new algorithms to tackle these problems by mathematical-optimisation techniques. Based on weak hypotheses, they have a polynomial time complexity, and yet perform well compared to state-of-the-art algorithms for the same problems. They also enjoy excellent statistical properties, meaning that they find a balance between exploration and exploitation that is close to the theoretical optimum. Previous work on combinatorial bandits had to make a choice between computational burden and statistical performance; our algorithms show that there is no need for such a quandary

19

Martins, Renato Juliano. "Controle coerente das bandas de emissão do ZnO através de algoritmo genético". Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/76/76131/tde-12032012-081648/.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Neste trabalho, investigamos o controle coerente das bandas de emissão, excitadas via absorção multifotônica, em um cristal de óxido de Zinco (ZnO) através das formatação de pulsos laser ultracurtos (790 nm, 30 fs, 80 MHz e 5 nJ). O ZnO vem se mostrado um possível candidato a dispositivos fotônicos devido a sua grande energia de ligação de éxciton (60 meV).Inicialmente, implementamos a montagem experimental do sistema de formatação de pulsos, bem como de excitação e coleta da fluorescência do ZnO. O controle coerente foi feito através de um programa baseado em um algoritmo genético (GA), também desenvolvido no transcorrer deste trabalho. Através do algoritmo genético, observamos um ganho significativo da emissão do ZnO por meio de fases espectrais impostas ao pulso laser. Monitorando o traço de autocorrelação do pulso, inferimos que este se torna mais longo após a otimização das bandas de emissão via GA. Além disso, verificamos que as funções de fase que otimizam o processo são complexas e oscilatórias. Através da análise das componentes principais (PCA), fizemos uma análise do conjunto de dados providos pelo GA, onde observamos que este método pode ser usado como um filtro para os dados, suavizando as curvas e enfatizando os aspectos mais importantes das máscaras de fase obtidas pelo controle coerente. Por fim investigamos qual a importância das máscaras suavizadas para o entendimento físico do processo.
In this work, we investigate the coherent control of the emission bands, excited via multiphoton absorption, in a zinc oxide crystal (ZnO) by pulse shaping ultrashort laser pulses (790 nm, 30 fs, 5 nJ and 80 MHz). ZnO has been preposed as a potential material for photonic devices due to its strong exciton binding energy(60 meV). Initially, we have implemented the pulse shaper experimental setup, as well as the fluorescence measurements of ZnO. The coherent control was carried out through genetic algorithm (GA) based software, also developed in the course of this work. Using the genetic algorithm, we have observed a significant increase in the ZnO emission when appropriated spectral phase masks are applied to the laser pulse. Autocorrelation measurements were used to infer the pulse duration, which get longer after optimization of the emission band via GA. Additionally, we have found that the phase masks that optimize the process are complex oscillatory functions. Through the Principal Component Analysis, we analyzed the data provided by the GA and observed that it can be used to filter the data, smoothing the curves and highlighting the most important aspects of phase masks obtained by the coherent control. Finally we investigate how important the smoothed masks are for the physical understanding of the process.

20

Meurisse, Yann. "Contributions à l'étude de performances statistiques de réseaux d'antennes". Paris 11, 2002. http://www.theses.fr/2002PA112209.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

En traitement d'antenne, les performances statistiques des méthodes d'estimation de direction d'arrivée (DOA) de sources sont en général évaluées en supposant d'une part que les réseaux d'antennes utilisés sont linéaires, à répartition régulière uniforme des capteurs et d'autre part que les signaux sources et le bruit, sont gaussiens, temporellement non corrélés et indépendants entre eux. Les signaux observés sont d'autre part supposés, soit "bande étroite" soit "large bande", donnant lieu à des méthodes spécifiques de complexité différente. L'objectif général de notre étude est d'évaluer les performances statistiques des méthodes d'estimation de DOA du second ordre lorsque les hypothèses conventionnelles précédentes ne sont pas vérifiées. Dans ce cadre général notre étude a porté sur les points suivants: l'étude de géométries de réseaux d'antennes, régulières non uniformes, optimales selon certains critères, pouvant permettre l'amélioration des performances des méthodes conventionnelles en DOA, l'étude des performances des méthodes du second ordre d'estimation de DOA utilisées dans des situations non conventionnelles, en particulier si les signaux sources et/ou le bruit sont des processus aléatoires éventuellement corrélés temporellement et éventuellement non gaussiens, l'étude de la robustesse des algorithmes bande étroite d'estimation de DOA vis à vis de la largeur de bande des signaux et de la symétrie de leurs spectres, l'étude enfin d'une méthode dite de "covariance matching estimation" (COMET) appliquée à l'estimation de DOA ainsi qu'à l'estimation de fréquences de sinusoi͏̈des qui fournit, sous certaines conditions, des estimations asymptotiquement de variance minimale
In antenna array processing, statistical performance of the estimation methods of direction of arrival (DOA) of sources are generally evaluated by assuming on one band that the antenna arrays are linear with a regular uniform repartition of the sensors and, on the other hand, that sources and noise signals are gaussian, temporally uncorrelated and independent among each other. The observed signals are on the other hand supposed to be narrowband or wideband, leading to specific methods of different complexity. The general objective of our work is to evaluate the statistical performance of second order DOA estimation methods when the preceding convention al hypotheses are not verified. In this general framework, our study has dealt with the following points: the study of array geometries, regular, non-uniform, optimal according to certain criteria and allowing the improvement of the performance of conventional methods of DOA estimation, the study of the performance of second order methods of DOA estimation used in unconventional situations, in particular if the source signals and/or the noise signal are stochastic processes eventually temporally correlated and eventually non-gaussian, the study of the robustness of narrowband DOA algorithms with respect to the signal bandwidth and the symmetry of their spectra, finally, the study of a method called "covariance matching estimation" (COMET) applied to the DOA estimation problem as well as the sinusoidal frequencies estimation problem which provides, under certain conditions, asymptotically minimum variance estimations

21

Gabillon, Victor. "Algorithmes budgétisés d'itérations sur les politiques obtenues par classification". Thesis, Lille 1, 2014. http://www.theses.fr/2014LIL10032/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse étudie une classe d'algorithmes d'apprentissage par renforcement (RL), appelée « itération sur les politiques obtenues par classification » (CBPI). Contrairement aux méthodes standards de RL, CBPI n'utilise pas de représentation explicite de la fonction valeur. CBPI réalise des déroulés (des trajectoires) et estime la fonction action-valeur de la politique courante pour un nombre limité d'états et d'actions. En utilisant un ensemble d'apprentissage construit à partir de ces estimations, la politique gloutonne est apprise comme le produit d'un classificateur. La politique ainsi produite à chaque itération de l'algorithme, n'est plus définie par une fonction valeur (approximée), mais par un classificateur. Dans cette thèse, nous proposons de nouveaux algorithmes qui améliorent les performances des méthodes CBPI existantes, spécialement lorsque le nombre d’interactions avec l’environnement est limité. Nos améliorations se portent sur les deux limitations de CBPI suivantes : 1) les déroulés utilisés pour estimer les fonctions action-valeur doivent être tronqués et leur nombre est limité, créant un compromis entre le biais et la variance dans ces estimations, et 2) les déroulés sont répartis de manière uniforme entre les états déroulés et les actions disponibles, alors qu'une stratégie plus évoluée pourrait garantir un ensemble d'apprentissage plus précis. Nous proposons des algorithmes CBPI qui répondent à ces limitations, respectivement : 1) en utilisant une approximation de la fonction valeur pour améliorer la précision (en équilibrant biais et variance) des estimations, et 2) en échantillonnant de manière adaptative les déroulés parmi les paires d'état-action
This dissertation is motivated by the study of a class of reinforcement learning (RL) algorithms, called classification-based policy iteration (CBPI). Contrary to the standard RL methods, CBPI do not use an explicit representation for value function. Instead, they use rollouts and estimate the action-value function of the current policy at a collection of states. Using a training set built from these rollout estimates, the greedy policy is learned as the output of a classifier. Thus, the policy generated at each iteration of the algorithm, is no longer defined by a (approximated) value function, but instead by a classifier. In this thesis, we propose new algorithms that improve the performance of the existing CBPI methods, especially when they have a fixed budget of interaction with the environment. Our improvements are based on the following two shortcomings of the existing CBPI algorithms: 1) The rollouts that are used to estimate the action-value functions should be truncated and their number is limited, and thus, we have to deal with bias-variance tradeoff in estimating the rollouts, and 2) The rollouts are allocated uniformly over the states in the rollout set and the available actions, while a smarter allocation strategy could guarantee a more accurate training set for the classifier. We propose CBPI algorithms that address these issues, respectively, by: 1) the use of a value function approximation to improve the accuracy (balancing the bias and variance) of the rollout estimates, and 2) adaptively sampling the rollouts over the state-action pairs

22

Guingne, Franck. "Contribution à l’algorithmique des automates pondérés à une, deux ou plusieurs bandes". Rouen, 2005. http://www.theses.fr/2005ROUES009.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les travaux présentés dans ce mémoire se situent dans le cadre de la théorie des automates. Une étude générale des relations de similarité et la notion d'automate couvrant sont présentés. On définit les relations de fusion ainsi que la notion de transducteur couvrant. Un algorithme de réduction est proposé et expérimenté. Les automates multi-bandes pondérés sont une généralisation des automates et transducteurs. On définit des opérations de jointure et d'auto-intersection et on présente les algorithmes correspondants. Une conséquence du Problème de Correspondance de Post est qu'il n'existe pas d'algorithme général d'auto-intersection. On définit alors une classe d'automates multi-bandes pondérés dans laquelle il est possible de calculer l'auto-intersection. Après un état de l'art des logiciels manipulant les machines d'état finis, on présente les compilateurs d'états finis de XEROX, WFSC et XFST, à travers leurs spécificités. On présente le symbole '?' et les machines à alphabet étendu, puis la notion de réseau virtuel dans XFST. Plusieurs caractéristiques de la conception générique et modulaire de WFSC sont exposées. On propose une étude de la complexité au pire des cas de l'impression de tous les chemins d'un automate acyclique. On décrit la structure qui maximise la complexité, et on calcule cette complexité pour un nombre d'états donné
This PhD thesis deals with the automata theory. A general study of similarity relations and the notion a cover automata are presented. We define merging relations and the notion of cover transducers. A reduction algorithm is exposed and tested. Weighted multi-tape automata are a generalisation of automata and transducers. We define the join and auto-intersection operations and we present the corresponding algorithms. As a consequence of the Post's Correspondence Problem there does not exist a general algorithm of auto-intersection. We define a class of weighted multi-tape automata in which it is possible to compute the auto-intersection. After a State of the Art of finite state machine compilers, we present XEROX's compilers, WFSC and XFST, through their specificities. We present the '?' symbol and extended-alphabet machines, then the notion of virtual networks in XFST. Several characteristics of the generic and modular design of WFSC are exposed. We study the worst-case complexity for the printing of all paths of an acyclic automaton. We describe the structure that maximizes the complexity, then we compute this complexity for a given number of states

23

Iacob, Alexandra. "Scalable Model-Free Algorithms for Influencer Marketing". Electronic Thesis or Diss., université Paris-Saclay, 2023. http://www.theses.fr/2023UPASG012.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Motivés par les scénarios de diffusion de l'information et de publicité dans le les réseaux sociaux, nous étudions un problème de maximisation de l'influence (MI) dans lequel on suppose que l'on en sait peu sur le réseau de diffusion ou sur le modèle qui détermine comment l'information peut se propager.Dans un tel environnement incertain, on peut se concentrer sur des campagnes de diffusion à plusieurs tours, avec l'objectif de maximiser le nombre d'utilisateurs distincts qui sont influencés ou activés, à partir d'une base de nœuds influents.Au cours d'une campagne, les graines de propagation sont sélectionnées séquentiellement lors de tours consécutifs, et les commentaires sont collectés sous la forme des nœuds activés à chaque tour.L'impact (récompense) d'un tour est alors quantifié par le nombre de nœuds nouvellement activés. En général, il faut maximiser la propagation totale de la campagne, comme la somme des récompenses des tours.Nous considérons deux sous-classes de d'IM, emph{cimp} (CIMP) et emph{ecimp} (ECIMP), où (i) la récompense d'un tour d'une campagne en cours consiste uniquement en de nouvelles activations (non observées lors des tours précédents de cette campagne),(ii) le contexte du tour et les données historiques des tours précédents peuvent être exploités pour apprendre la meilleure politique, et(iii) ECIMP est CIMP répété plusieurs fois, ce qui permet d'apprendre également des campagnes précédentes.Ce problème est directement motivé par les scénarios du monde réel de la diffusion de l'information dans le marketing d'influence, où (i) seule la première / unique activation d'un utilisateur cible présente un intérêt (et cette activation persistera comme une activation acquise, latente, tout au long de la campagne).(ii) de précieuses informations secondaires sont disponibles pour l'agent d'apprentissageDans ce contexte, une approche d'exploration-exploitation pourrait être utilisée pour apprendre les principaux paramètres de diffusion sous-jacents, tout en exécutant les campagnes.Pour CIMP, nous décrivons et comparons deux méthodes de bandits à bras multiples contextuels, avec des limites supérieures de confiance sur le potentiel restant des influenceurs, l'une utilisant un modèle linéaire généralisé et l'estimateur de Good-Turing pour le potentiel restant, et l'autre adaptant directement l'algorithme LinUCB à notre cadre.Pour ECIMP, nous proposons l'algorithmelgtlsvi qui implémente le principe d'optimisme face à l'incertitude pour l'apprentissage par renforcement, avec approximation linéaire.L'agent d'apprentissage estime pour chaque nœud de départ son potentiel restant avec un estimateur de Good-Turing, modifié par une fonction Q estimée. Nous montrons qu'ils surpassent les performances des méthodes de base utilisant les idées les plus récentes, sur des données synthétiques et réelles, tout en présentant un comportement différent et complémentaire, selon les scénarios dans lesquels ils sont déployés
Motivated by scenarios of information diffusion and advertising in social media, we study an emph{influence maximization} (IM) problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In such a highly uncertain environment, one can focus on emph{multi-round diffusion campaigns}, with the objective to maximize the number of distinct users that are influenced or activated, starting from a known base of few influential nodes.During a campaign, spread seeds are selected sequentially at consecutive rounds, and feedback is collected in the form of the activated nodes at each round.A round's impact (reward) is then quantified as the number of emph{newly activated nodes}.Overall, one must maximize the campaign's total spread, as the sum of rounds' rewards.We consider two sub-classes of IM, emph{cimp} (CIMP) and emph{ecimp} (ECIMP), where (i) the reward of a given round of an ongoing campaign consists of only the extit{new activations} (not observed at previous rounds within that campaign), (ii) the round's context and the historical data from previous rounds can be exploited to learn the best policy, and (iii) ECIMP is CIMP repeated multiple times, offering the possibility of learning from previous campaigns as well.This problem is directly motivated by the real-world scenarios of information diffusion in emph{influencer marketing}, where (i) only a target user's emph{first} / unique activation is of interest (and this activation will emph{persist} as an acquired, latent one throughout the campaign), and (ii) valuable side-information is available to the learning agent.In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaigns.For CIMP, we describe and compare two methods of emph{contextual multi-armed bandits}, with emph{upper-confidence bounds} on the remaining potential of influencers, one using a generalized linear model and the Good-Turing estimator for remaining potential (glmucb), and another one that directly adapts the LinUCB algorithm to our setting (linucb).For ECIMP, we propose the algorithmlgtlsvi, which implements the extit{optimism in the face of uncertainty} principle for episodic reinforcement learning with linear approximation. The learning agent estimates for each seed node its remaining potential with a Good-Turing estimator, modified by an estimated Q-function.We show that they outperform baseline methods using state-of-the-art ideas, on synthetic and real-world data, while at the same time exhibiting different and complementary behavior, depending on the scenarios in which they are deployed

24

Bubeck, Sébastien. "JEUX DE BANDITS ET FONDATIONS DU CLUSTERING". Phd thesis, Université des Sciences et Technologie de Lille - Lille I, 2010. http://tel.archives-ouvertes.fr/tel-00845565.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Ce travail de thèse s'inscrit dans le domaine du machine learning et concerne plus particulièrement les sous-catégories de l'optimisation stochastique, du online learning et du clustering. Ces sous-domaines existent depuis plusieurs décennies mais ils ont tous reçu un éclairage différent au cours de ces dernières années. Notamment, les jeux de bandits offrent aujourd'hui un cadre commun pour l'optimisation stochastique et l'online learning. Ce point de vue conduit a de nombreuses extensions du jeu de base. C'est sur l'étude mathématique de ces jeux que se concentre la première partie de cette thèse. La seconde partie est quant à elle dédiée au clustering et plus particulièrement à deux notions importantes: la consistance asymptotique des algorithmes et la stabilité comme méthode de sélection de modèles.

25

Perrault, Pierre. "Apprentissage efficient dans les problèmes de semi-bandits stochastiques combinatoires". Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM023.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les problèmes de semi-banditsstochastiques combinatoires se présentent naturellement dans de nombreux contextes où le dilemme exploration/exploitation se pose, tels que l’optimisation de contenu web (recommandation/publicité en ligne) ou encore les méthodes de routage à trajet minimal. Ce problème est formulé de la manière suivante : un agent optimise séquentiellement une fonction objectif inconnue et bruitée, définie sur un ensemble puissance mathcal{P}([n]). Pour chaque ensemble A testé,l'agent subit une perte égale à l'écart espéré par rapport à la solution optimale tout en obtenant des observations lui permettant de réduire son incertitude sur les coordonnées de A.Notre objectif est d'étudier l'efficience des politiques pour ce problème, en nous intéressant notamment aux deux aspects suivants : l'efficience statistique, où le critère considéré est le regret subi par la politique (la perte cumulée) qui mesure la performance d'apprentissage ; et l'efficience computationnelle (i.e., de calcul). Il est parfois difficile de réunir ces deux aspects dans une seule politique. Dans cette thèse, nous proposons différentes directions pour améliorer l'efficience statistique, tout en essayant de maintenir l'efficience computationnelle des politiques. Nous avons notamment amélioré les méthodes optimistes en développant des algorithmes d'approximation et en affinant les régions de confiance utilisées. Nous avons également exploré une alternative aux méthodes optimistes, à savoir les méthodes randomisées, et avons constaté qu'elles constituent un candidat sérieux pour pouvoir réunir les deux types d'efficience
Combinatorial stochastic semi-bandits appear naturally in many contexts where the exploration/exploitation dilemma arises, such as web content optimization (recommendation/online advertising) or shortest path routing methods. This problem is formulated as follows: an agent sequentially optimizes an unknown and noisy objective function, defined on a power set mathcal{P}([n]). For each set A tried out, the agent suffers a loss equal to the expected deviation from the optimal solution while obtaining observations to reduce its uncertainty on the coordinates from A. Our objective is to study the efficiency of policies for this problem, focusing in particular on the following two aspects: statistical efficiency, where the criterion considered is the regret suffered by the policy (the cumulative loss) that measures learning performance; and computational efficiency. It is sometimes difficult to combine these two aspects in a single policy. In this thesis, we propose different directions for improving statistical efficiency, while trying to maintain the computational efficiency of policies.In particular, we have improved optimistic methods by developing approximation algorithms and refining the confidence regions used. We also explored an alternative to the optimistic methods, namely randomized methods, and found them to be a serious candidate for combining the two types of efficiency

26

Hadiji, Hédi. "On some adaptivity questions in stochastic multi-armed bandits". Thesis, université Paris-Saclay, 2020. http://www.theses.fr/2020UPASM021.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse s'inscrit dans le domaine des statistiques séquentielles. Le cadre principal étudié est celui des bandits stochastiques à plusieurs bras, cadre idéal qui modélise le dilemme exploration-exploitation face à des choix répétés. La thèse est composée de quatre chapitres, précédés d'une introduction. Dans la première partie du corps de la thèse, on présente un nouvel algorithme capable d'atteindre des garanties optimales à la fois d'un point de vue distribution-dépendent et distribution-free. Les deux chapitres suivants sont consacrés à des questions dites d'adaptation. D'abord, on propose un algorithme capable de s'adapter à la régularité inconnue dans des problèmes de bandits continus, mettant en évidence le coût polynomial de l'adaptation en bandits continus. Ensuite, on considère un problème d'adaptation au supports pour des problèmes de bandits à K bras, à distributions de paiements bornés dans des intervalles inconnus. Enfin, dans un dernier chapitre un peu à part, on étudie un cadre légèrement différent de bandits préservant la diversité. On montre que le regret optimal dans ce cadre croît à des vitesses différentes des vitesses classiques, avec notamment la possibilité d'atteindre un regret constant sous certaines hypothèses
The main topics adressed in this thesis lie in the general domain of sequential learning, and in particular stochastic multi-armed bandits. The thesis is divided into four chapters and an introduction. In the first part of the main body of the thesis, we design a new algorithm achieving, simultaneously, distribution-dependent and distribution-free optimal guarantees. The next two chapters are devoted to adaptivity questions. First, in the context of continuum-armed bandits, we present a new algorithm which, for the first time, does not require the knowledge of the regularity of the bandit problem it is facing. Then, we study the issue of adapting to the unknown support of the payoffs in bounded K-armed bandits. We provide a procedure that (almost) obtains the same guarantees as if it was given the support in advance. In the final chapter, we study a slightly different bandit setting, designed to enforce diversity-preserving conditions on the strategies. We show that the optimal regert in this setting at a speed that is quite different from the traditional bandit setting. In particular, we observe that bounded regret is possible under some specific hypotheses

27

Silvestre, Fialho Álvaro Roberto. "Adaptive operator selection for optimization". Paris 11, 2010. http://www.theses.fr/2010PA112292.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les Algorithmes Evolutionnaires sont des algorithmes d'optimisation qui ont déjà montré leur efficacité dans plusieurs domaines ; mais leur performance dépend du réglage de plusieurs paramètres. Cette thèse est consacrée au développement de techniques pour automatiser ce réglage par le biais de l'apprentissage automatique. Plus spécifiquement, nous avons travaillé sur un sous-problème : étant donné un ensemble d'opérateurs, cela consiste à choisir lequel doit être appliqué pour la génération de chaque nouvelle solution, basé sur la performance connue de chaque opérateur. Cette approche est utilisée en ligne, au cours de la résolution du problème, en utilisant exclusivement l'histoire du processus d'optimisation courant pour décider parmi les différents opérateurs ; ce paradigme est couramment référencé comme Sélection Adaptative d'Opérateurs (SAO). Pour faire de la SAO, deux composants sont nécessaires. L'Affectation de Crédit définit comment récompenser les opérateurs selon l'impact de leur application sur le processus de recherche. La Sélection d'Opérateurs règle leur choix selon les récompenses reçues ultérieurement. En résumé, la contribution principale de cette thèse consiste dans la proposition et l'analyse de différentes approches pour la SAO, basées sur le paradigme de Bandit Manchot (BM) ; nous avons proposé plusieurs modifications pour transformer un algorithme BM en une technique à la fois performante dans l'environnement dynamique de la SAO, et robuste par rapport aux caractéristiques des problèmes diverses. La dernière méthode, appelé AUC-MAB, est capable de suivre efficacement le meilleur opérateur sans nécessiter d'un réglage spécifique pour chaque problème
Evolutionary Algorithms have demonstrated their ability to address a wide range of optimization problems; but their performance relies on tuning a few parameters, depending on the problem at hand. During this thesis work, we have focused on the development of tools to automatically set some of these parameters, using machine learning techniques. More specifically, we have worked on the following sub-problem: given a number of available variation operators, it consists in selecting which is the best operator to be applied at each moment of the search, based on how the operators have performed up to the given time instant of the current search/optimization process. This approach is applied online, i. E. , while solving the problem, using only the history of the current run to evaluate and decide between the operators; this paradigm is commonly referred to as Adaptive Operator Selection (AOS). To do AOS, we need two components: a Credit Assignment scheme, that defines how to reward the operators based on their impact in the search process, and an Operator Selection mechanism that, based on the rewards received, decides which is the best operator to be applied next. The contributions of this thesis, in summary, lie in the proposaI and analysis of schemes to solve the AOS problem based on the Multi-Armed Bandit (MAB) paradigm; we have proposed different techniques, in order to enable a MAB algorithm to efficiently cope with the dynamics of evolution and with the very different characteristics of the problems to be tackled. The latest one, referred to as AUC-MAB, is able to efficiently control the application of operators, while being robust with respect to its own parameters

28

Benhamiche, Amal. "Designing optical multi-band networks : polyhedral analysis and algorithms". Thesis, Paris 9, 2013. http://www.theses.fr/2013PA090075/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans cette thèse, on s'intéresse à deux problèmes de conception de réseaux, utilisant la technologie OFDM multi-bandes. Le premier problème concerne la conception d'un réseau mono-couche avec contraintes spécifiques. Nous donnons une formulation en PLNE pour ce problème et étudions le polyèdre associé à sa restriction sur un arc. Nous introduisons deux familles d'inégalités valides définissant des facettes et développons un algorithme de coupes et branchements pour le problème. Nous étudions la variante multicouche du problème précédent et proposons plusieurs PLNE pour le modéliser. Nous identifions plusieurs familles de facettes et discutons des problèmes de séparation associés. Nous développons un algorithme de coupes et branchements utilisant l'ensemble des contraintes identifiées. Enfin, une formulation compacte et deux formulations basées sur des chemins sont proposées pour le problème. Nous présentons deux algorithmes de génération de colonnes et branchements pour le problème
In this thesis we consider two capacitated network design (CND) problems, using OFDM multi-band technology. The first problem is related to single-layer network design with specific requirements. We give an ILP formulation for this problem and study the polyhedra associated with its arc-set restriction. We describe two families of facet defining inequalities. We devise a Branch-and-Cut algorithm for the problem. Next, we investigate the multilayer version of CND using OFDM technology. We propose several ILP formulations and study the polyhedron associated with the first (cut) formulation. We identify several classes of facets and discuss the related separation problem. We devise a Branch-and-Cut algorithm embedding valid inequalities of both single-layer and multilayer problems. The second formulation is compact, and holds a polynomial number of constraints and variables. Two further path formulations are given which yield two efficient Branch-and-Price algorithms for the problem

29

Abeille, Marc. "Exploration-exploitation with Thompson sampling in linear systems". Thesis, Lille 1, 2017. http://www.theses.fr/2017LIL10182/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse est dédiée à l'étude du Thompson Sampling (TS), une heuristique qui vise à surmonter le dilemme entre exploration et exploitation qui est inhérent à tout processus décisionnel face à l'incertain. Contrairement aux algorithmes issus de l'heuristique optimiste face à l'incertain (OFU), où l'exploration provient du choix du modèle le plus favorable possible au vu de la connaissance accumulée, les algorithmes TS introduisent de l'aléa dans le processus décisionnel en sélectionnant aléatoirement un modèle plausible, ce qui les rend bien moins coûteux numériquement. Cette étude se concentre sur les problèmes paramétriques linéaires, qui autorisent les espaces état-action continus (infinis), en particulier les problèmes de Bandits Linéaires (LB) et les problèmes de contrôle Linéaire et Quadratique (LQ). Nous proposons dans cette thèse de nouvelles analyses du regret des algorithmes TS pour chacun de ces deux problèmes. Bien que notre démonstration pour les LB garantisse une borne supérieure identique aux résultats préexistants, la structure de la preuve offre une nouvelle vision du fonctionnement de l'algorithme TS, et nous permet d'étendre cette analyse aux problèmes LQ. Nous démontrons la première borne supérieure pour le regret de l'algorithme TS dans les problèmes LQ, qui garantie dans le cadre fréquentiste un regret au plus d'ordre O(\sqrt{T}). Enfin, nous proposons une application des méthodes d'exploration-exploitation pour les problèmes d'optimisation de portefeuille, et discutons dans ce cadre le besoin ou non d'explorer activement
This dissertation is dedicated to the study of the Thompson Sampling (TS) algorithms designed to address the exploration-exploitation dilemma that is inherent in sequential decision-making under uncertainty. As opposed to algorithms derived from the optimism-in-the-face-of-uncertainty (OFU) principle, where the exploration is performed by selecting the most favorable model within the set of plausible one, TS algorithms rely on randomization to enhance the exploration, and thus are much more computationally efficient. We focus on linearly parametrized problems that allow for continuous state-action spaces, namely the Linear Bandit (LB) problems and the Linear Quadratic (LQ) control problems. We derive two novel analyses for the regret of TS algorithms in those settings. While the obtained regret bound for LB is similar to previous results, the proof sheds new light on the functioning of TS, and allows us to extend the analysis to LQ problems. As a result, we prove the first regret bound for TS in LQ, and show that the frequentist regret is of order O(sqrt{T}) which matches the existing guarantee for the regret of OFU algorithms in LQ. Finally, we propose an application of exploration-exploitation techniques to the practical problem of portfolio construction, and discuss the need for active exploration in this setting

30

Habermann, Mateus. "Band selection in hyperspectral images using artificial neural networks". Thesis, Compiègne, 2018. http://www.theses.fr/2018COMP2434/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les images hyperspectrales (HSI) fournissent des informations spectrales détaillées sur les objets analysés. Étant donné que différents matériaux ont des signatures spectrales distinctes, les objets ayant des couleurs et des formes similaires peuvent être distingués dans le domaine spectral. Toutefois, l’énorme quantité de données peut poser des problèmes en termes de stockage et de transmission des données. De plus, la haute dimensionnalité des images hyperspectrales peut entraîner un surajustement du classificateur en cas de données d'apprentissage insuffisantes. Une façon de résoudre de tels problèmes consiste à effectuer une sélection de bande (BS), car elle réduit la taille du jeu de données tout en conservant des informations utiles et originales. Dans cette thèse, nous proposons trois méthodes de sélection de bande différentes. La première est supervisée, conçu pour utiliser seulement 20% des données disponibles. Pour chaque classe du jeu de données, une classification binaire un contre tous utilisant un réseau de neurones est effectuée et les bandes liées aux poids le plus grand et le plus petit sont sélectionnées. Au cours de ce processus, les bandes les plus corrélées avec les bandes déjà sélectionnées sont rejetées. Par conséquent, la méthode proposée peut être considérée comme une approche de sélection de bande orientée par des classes. La deuxième méthode que nous proposons est une version non supervisée du premier framework. Au lieu d'utiliser les informations de classe, l'algorithme K-Means est utilisé pour effectuer une classification binaire successive de l'ensemble de données. Pour chaque paire de grappes, un réseau de neurones à une seule couche est utilisé pour rechercher l'hyperplan de séparation, puis la sélection des bandes est effectuée comme décrit précédemment. Pour la troisième méthode de BS proposée, nous tirons parti de la nature non supervisée des auto-encodeurs. Pendant la phase d'apprentissage, le vecteur d'entrée est soumis au bruit de masquage. Certaines positions de ce vecteur sont basculées de manière aléatoire sur zéro et l'erreur de reconstruction est calculée sur la base du vecteur d'entrée non corrompu. Plus l'erreur est importante, plus les fonctionnalités masquées sont importantes. Ainsi, à la fin, il est possible d'avoir un classement des bandes spectrales de l'ensemble de données
Hyperspectral images (HSIs) are capable of providing a detailed spectral information about scenes or objects under analysis. It is possible thanks to both numerous and contiguous bands contained in such images. Given that di_erent materials have distinct spectral signatures, objects that have similar colors and shape can be distinguished in the spectral domain that goes beyond the visual range. However, in a pattern recognition system, the huge amount of data contained in HSIs may pose problems in terms of data storage and transmission. Also, the high dimensionality of hyperspectral images can cause the overfitting of the classifer in case of insufficient training data. One way to solve such problems is to perform band selection(BS) in HSIs, because it decreases the size of the dataset while keeping both useful and original information. In this thesis, we propose three different band selection frameworks. The first one is a supervised one, and it is designed to use only 20% of the available training data. For each class in the dataset, a binary one-versus-all classification using a single-layer neural network is performed, and the bands linked to the largest and smallest coefficients of the resulting hyperplane are selected. During this process, the most correlated bands with the bands already selected are automatically discarded, following a procedure also proposed in this thesis. Consequently, the proposed method may be seen as a classoriented band selection approach, allowing a BS criterion that meets the needs of each class. The second method we propose is an unsupervised version of the first framework. Instead of using the class information, the K-Means algorithm is used to perform successive binary clustering of the dataset. For each pair of clusters, a single-layer neural network is used to find the separating hyperplane, then the selection of bands is done as previously described. For the third proposed BS framework, we take advantage of the unsupervised nature of autoencoders. During the training phase, the input vector is subjected to masking Noise - some positions of this vector are randomly flipped to zero and the reconstruction error is calculated based on the uncorrupted input vector. The bigger the error, the more important the masked features are. Thus, at the end, it is possible to have a ranking of the spectral bands of the dataset

31

Cayuela, Rafols Marc. "Algorithmic Study on Prediction with Expert Advice : Study of 3 novel paradigms with Grouped Experts". Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-254344.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

The main work for this thesis has been a thorough study of the novel Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigm. This is newly proposed in this thesis, and it extends the widely studied Prediction with Expert Advice paradigm. The extension is based on two assumptions and one restriction that modify the original problem. The first assumption, Grouped, presumes that the experts are structured into groups. The second assumption, Side Information, introduces additional information that can be used to timely relate predictions with groups. Finally, the restriction, Partially Monitored, imposes that the groups’ predictions are only known for one group at a time. The study of this paradigm includes the design of a complete prediction algorithm, the proof of a theoretical bound of the worse-case cumulative regret for such algorithm, and an experimental evaluation of the algorithm (proving the existence of cases where this paradigm outperforms Prediction with Expert Advice). Furthermore, since the development of the algorithm is constructive, it allows to easily build two additional prediction algorithms for the Prediction with Grouped Expert Advice and Prediction with Grouped Expert Advice and Side Information paradigms. Therefore, this thesis presents three novel prediction algorithms, with corresponding regret bounds, and a comparative experimental evaluation including the original Prediction with Expert Advice paradigm.
Huvudarbetet för den här avhandlingen har varit en grundlig studie av den nya Prediction with Partially Monitored Grouped Expert Advice and Side Information paradigmet. Detta är nyligen föreslagit i denna avhandling, och det utökar det brett studerade Prediction with Expert Advice paradigmet. Förlängningen baseras på två antaganden och en begränsning som ändrar det ursprungliga problemet. Det första antagandet, Grouped, förutsätter att experterna är inbyggda i grupper. Det andra antagandet, Side Information, introducerar ytterligare information som kan användas för att i tid relatera förutsägelser med grupper. Slutligen innebär begränsningen, Partially Monitored, att gruppens förutsägelser endast är kända för en grupp i taget. Studien av detta paradigm innefattar utformningen av en komplett förutsägelsesalgoritm, beviset på en teoretisk bindning till det sämre fallet kumulativa ånger för en sådan algoritm och en experimentell utvärdering av algoritmen (bevisar förekomsten av fall där detta paradigm överträffar Prediction with Expert Advice). Eftersom algoritmens utveckling är konstruktiv tillåter den dessutom att enkelt bygga två ytterligare prediksionsalgoritmer för Prediction with Grouped Expert Advice och Prediction with Grouped Expert Advice and Side Information paradigmer. Därför presenterar denna avhandling tre nya prediktionsalgoritmer med motsvarande ångergränser och en jämförande experimentell utvärdering inklusive det ursprungliga Prediction with Expert Advice paradigmet.

32

Pham, Trung-Kien. "Étude et conception de réseaux transmetteurs reconfigurables en bande Ka". Thesis, Rennes 1, 2017. http://www.theses.fr/2017REN1S065.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans les systèmes de communication et de détection sans fil, l'antenne est un élément indispensable pour transformer l'énergie électrique en ondes électromagnétiques rayonnée dans l'espace, et vice versa. Les antennes sont utilisées dans de nombreux dispositifs militaires et civils, tels que les radars (SAR, secteur automobile, détection de débris, etc.), les instruments biomédicaux, les systèmes de télécommunication (téléphones mobiles, stations de base) pour les communications point à multi-point ou point à point par exemple. Les antennes jouent aussi un rôle essentiel pour le développement de futurs réseaux connectés reliant plusieurs appareils à des utilisateurs en temps réel, par exemple pour l'Internet des objets (IoT). Les réseaux transmetteurs sont une solution attrayante pour de nombreuses applications telles que les communications par satellite (Satcom) ou les futurs réseaux 5G. L'architecture des antennes à réseau transmetteur les rend extrêmement compétitifs comparés aux réseaux phasés par exemple grâce à leur alimentation par onde d’espace et car ils ne souffrent pas du blocage induit par la source primaire, comme c’est le cas pour les réseaux réflecteurs ou les antennes à réflecteur. Grâce à leur fonctionnement en mode transmission, les réseaux transmetteurs peuvent être également facilement montés sur des plates-formes mobiles.Les applications Satcom en bande Ka constituent le secteur applicatif majeur de cette thèse. Cette bande fournit un débit de données élevé à la fois pour les liaisons descendantes et les liaisons montantes, en remplacement des systèmes actuels en bande Ku. Dans ce contexte, il convient aussi de prêter une attention particulière aux communications avec des plates-formes mobiles, par exemple les trains à grande vitesse, les avions, etc., ce qui nécessite de mettre au point des antennes à balayage de faisceau. De nombreuses propriétés avancées sont exploitées depuis ces dernières années pour accroître les débits et la flexibilité des systèmes de communication sans fil, par exemple la polarisation circulaire, la double polarisation, le fonctionnement multi-fréquence ou large bande, le dépointage électronique de faisceau. Pour réduire les coûts, des preuves de concept de réseaux transmetteurs non diélectriques sont également proposées. Cette thèse s’est déroulée dans le cadre du projet ANR TRANSMIL (Reconfigurable TRANSmitarrays for beam steering and beam forming at MILlimetre wave). Les objectifs de cette thèse sont de proposer de nouvelles architectures de réseaux transmetteurs fonctionnant en bande Ka en liaison descendante (de 17,7 GHz à 21,2 GHz) et en liaison montante (de 27,5 GHz à 31 GHz). Différents prototypes ont été conçus et fabriqués afin de valider les concepts proposés en bande X et en bande Ka. Un bon accord entre les résultats numériques et mesurés a été obtenu systématiquement. En particulier, les réseaux transmetteurs à double polarisation que nous avons conçus en bande X présentent un gain de 25 dBi et une bande passante à 3 dB de 20% à 10 GHz. Ces propriétés sont indépendantes de la polarisation du champ rayonné, ce qui signifie que des faisceaux de polarisation linéaire orthogonale peuvent être rayonnés indépendamment dans des directions différentes. Un réseau transmetteur bi-bande fonctionnant en bande Ka a également été mis au point. Sa bande passante à 3 dB est de 10% autour des fréquences centrales (19,5 GHz et 29 GHz) et son efficacité de rayonnement atteint 60%. D’autres concepts ont également été étudiés (réseaux transmetteurs sans diélectrique, réseau transmetteur reconfigurable)
Transmitarray is an attractive solution for front-end devices in the next generation of communications (5G). The spatial-fed architecture of transmitarray antennas can compete with phase-arrays due to the absence of feeding network and with reflectarrays since they do not suffer from feed blockage. Thanks to their operation in transmission mode, transmitarrays can be easily mounted on platforms for outdoor environment applications. With mature printed-circuit board technology, there are unstoppable experiments in various frequency bands from cm-wave to mm-wave and up to terahertz in upcoming years for potential applications. Many advanced properties are exploited in transmitarrays in recent years to meet high demands of communications facilities, for example, circular-polarization, dual-/multi-polarization or frequencies through many techniques. Some experiments are consid-ered to validate eligibility of this antenna type in commercial services or military missions, namely electronically steering beam, broad bandwidth, etc. In terms of cost reduction and rigidity, non-dielectric prototypes are also proposed. The Ka-band Satcom applications are the main objective of this thesis through trans-mitarray solution. This band provides high data rate for both down-link and up-link in replacement of the current Ku-band systems with miniaturized module in next dec-ades. Hence, it is worth to pay attention to communications for moving platforms, for example, high-speed trains, planes, etc

33

Delestre, Cyrile. "Géolocalisation d'émetteurs en une étape : Algorithmes et performances". Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLN006/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Le contexte de cette thèse est celui de la géolocalisation d'émetteurs (estimation de la position dans l’espace) de radiocommunication à partir de plusieurs stations multi-capteur qui sont spatialement éloignées. Les méthodes conventionnelles de géolocalisation telles que la triangulation sont en 2 étapes (la première étape estime des paramètres intermédiaires et la seconde étape "fusionne" ces mesures effectuées sur plusieurs stations afin de fournir la position des émetteurs). Les méthodes en 1 étape quant à elles utilisent les observations issues de toutes les antennes pour estimer directement et de manière optimale la position des sources. Le fait de traiter les signaux directement sur l'antenne globale (composée de toutes les stations d'antenne locales) entraîne un effet large bande sur les signaux entre stations. La thèse propose d'étudier l'effet large bande résiduel présent sur l'antenne globale des méthodes en 1 étape. Elle propose ensuite des améliorations sur des méthodes de géolocalisation en 1 étape, notamment grâce à l'apport de la théorie de matrice aléatoire à grande dimension et à l'introduction d'une nouvelle méthode nommée LOST-FIND. Finalement, une nouvelle approche visant à aborder différemment le problème large bande a été introduite donnant l'algorithme TARGET
The context of the thesis is the transmitters geolocalization (position estimation in the space) of radiocommunication from several widely spaced multi-sensor stations. The conventional geolocalization methods as the tirnagulation are in 2 staps (the first step estimates intermediate parameters and the second step "merges" these mesures from the stations in order to obtain the transmitters positions). The 1 stap methods use the observertions from all the stations to directly and optimally estimate the sources positions. Directly handling the signals on the global array (composed of all the local stations) leads to a broadband effect on the signals between the stations.The thesis proposes to study the residual broadband effect on the global array of the 1 step methods. Then we propose improvements on some 1 step geolocalization methods, especially based on the random matrix theory in large dimension and on the introduction of a new method named LOST-FIND. Finally, a new approach differently tackling the braodband problem has been introduced and leads to TARGET algorithm

34

Steinberg, David. "Otimização da largura de banda de ganho de um amplificador Raman na banda "O" baseada em algoritmo genético". Universidade Presbiteriana Mackenzie, 2011. http://tede.mackenzie.br/jspui/handle/tede/1401.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Made available in DSpace on 2016-03-15T19:37:35Z (GMT). No. of bitstreams: 1 David Steinberg.pdf: 1201176 bytes, checksum: 38de6b0554611de53adf67ca19a556a1 (MD5) Previous issue date: 2011-01-28
In this work, the O-band discrete Raman amplifier gain bandwidth optimization using genetic algorithm of a commercial simulator is carried out. The main objective of the study was to optimize the wide Raman amplifier gain bandwidth obtaining values of gain variation less than 0.5 dB. Using a fiber DCF (Dispersion Compensating Fiber) as Raman amplifier medium, the pump number was varied and the gain variation for each pump configuration has been verified. For a fixed 70 nm (1275-1345 nm) bandwidth consisting of 62 signal frequencies points, the results were generated for one, two, three, four, five, six, seven and eight backward pumps, which with the last one it was obtained the best result of 0.35 dB gain variation. In addition to this analysis, it was also found the Raman amplifier noise figure for this band and made a brief comparison with the conventional profile bands.
Neste trabalho a otimização da largura de banda de ganho de um amplificador Raman discreto na banda "O" utilizando algoritmo genético de um simulador comercial foi realizada. O objetivo principal do trabalho foi otimizar a maior largura de banda de ganho do amplificador Raman obtendo valores de variação de ganho menores que 0.5 dB. Utilizando uma fibra DCF (Dispersion Compensating Fiber) como meio de ganho do amplificador Raman, o número de bombeio foi variado e a variação de ganho para cada configuração de bombeio foi verificada. Para uma largura de banda fixa em 70 nm (1275-1345 nm) compreendendo 62 pontos de freqüências de sinal, foram gerados resultados para um, dois, três, quatro, cinco, seis, sete e oito bombeios contrapropagantes sendo que com esta última configuração foi obtido o melhor resultado de variação de ganho de 0.35 dB. Além desta análise, também foi verificado o perfil da figura de ruído do amplificador Raman nesta banda e feita uma breve comparação com o perfil em bandas convencionais.

35

Gómez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions". Angers, 2010. http://www.theses.fr/2010ANGE0022.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine. . . ). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i. E. N'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies
Packing problems are usually NP-hard, or NP-complete according to the objective. One has to locate a set of objects into one or more “container(s)”, with fix dimensions or of infinite height, while respecting constraints related to some characteristics (weight, quantity, rotation, stability, guillotine cuts. . . ). Themain interest of these problems are the numerous practical applications from various domains. The most effective solution strategies for these problems are usually approximate methods, local search in particular. In this thesis, we are interested in a particular two-dimensional packing problem (without rotation nor guillotine cuts) known as “strip packing” (SPP). The objective of this problem, after locating rectangular objects without overlap, is to minimize the height of the resulting packing. We developed two “meta-heuristic” approaches for the SPP, both including innovative components based on problem knowledge. The first one is a genetic algorithm with a new (highly “visual”) crossover and a hierarchical fitness function. The second one is a tabu search with “direct” representation (i. E. Not using the classical permutations) whose main characteristics are a consistent neighborhood, a “well-informed” diversification (based on the search history), and a fitness function able to evaluate possibly partial solutions. The two proposed approaches, assessed on a well-known and very difficult benchmark, show good performances compared with other strategies

36

Fialho, Álvaro. "Selection Adaptative d'Operateurs pour l'Optimisation". Phd thesis, Université Paris Sud - Paris XI, 2010. http://tel.archives-ouvertes.fr/tel-00578431.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les Algorithmes Évolutionnaires sont des algorithmes d'optimisation qui ont déjà montré leur efficacité dans plusieurs domaines; mais leur performance dépend du réglage de plusieurs paramètres. Cette thèse est consacrée au développement de techniques pour automatiser ce réglage par le biais de l'apprentissage automatique. Plus spécifiquement, nous avons travaillé sur un sous-problème: étant donné un ensemble d'opérateurs, cela consiste à choisir lequel doit être appliqué pour la génération de chaque nouvelle solution, basé sur la performance connue de chaque opérateur. Cette approche est utilisée en ligne, au cours de la résolution du problème, en utilisant exclusivement l'histoire du processus d'optimisation courant pour décider parmi les différents opérateurs; ce paradigme est couramment référencé comme Sélection Adaptative d'Opérateurs (SAO). Pour faire de la SAO, deux composants sont nécessaires. L'Affectation de Crédit définit comment récompenser les opérateurs selon l'impact de leur application sur le processus de recherche. La Sélection d'Opérateurs règle leur choix selon les récompenses reçues ultérieurement. En résumé, la contribution principale de cette thèse consiste dans la proposition et l'analyse de différentes approches pour la SAO, basées sur le paradigme de Bandit Manchot (BM); nous avons proposé plusieurs modifications pour transformer un algorithme BM en une technique à la fois performante dans l'environnement dynamique de la SAO, et robuste par rapport aux caractéristiques des problèmes diverses. La dernière méthode, appelé AUC-MAB, est capable de suivre efficacement le meilleur opérateur sans nécessiter d'un réglage spécifique pour chaque problème.

37

Bouton, Eric Albert. "Algorithmes d'allocation de ressources pour des systèmes à interférence". Phd thesis, Télécom ParisTech, 2010. http://pastel.archives-ouvertes.fr/pastel-00005795.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

L'interférence est un phénomène présent dans de nombreux systèmes de communication et est souvent un sérieux frein à leur développement. Une gestion intelligente de ce phénomène est alors nécessaire, afin de limiter son impact négatif. Dans cette thèse, nous avons abordé trois sujets liés à sa présence. Dans la première partie, de façon à augmenter le débit de transmission dans les systèmes à ultra large bande basés sur des impulsions brèves, nous proposons d'attribuer plusieurs codes à saut temporel au même utilisateur. Ceci génère un nouveau type d'interférence associée aux codes supplémentaires alloués à l'utilisateur d'intérêt. Le bénéfice de ce type de stratégie n'étant pas immédiat, nous étudions l'impact de notre proposition sur les performances du système. Dans la deuxième partie, nous traitons le problème de l'optimisation de la probabilité de coupure dans un système multi-antennaire, soumis à un canal de Rice à évanouissement lent. Nous proposons d'optimiser cette probabilité dans le contexte à N antennes de transmission et une antenne de réception, lorsque le rapport signal-à-bruit est grand, et de l'améliorer dans le contexte à plusieurs antennes de transmission et plusieurs antennes de réception. Dans la dernière partie, nous étudions le problème de l'allocation de puissance dans un canal à interférence gaussien. En nous basant sur une nouvelle expression approchée de la capacité de ce canal et moyennant une modulation OFDM, nous proposons de développer un nouvel algorithme d'allocation de puissance qui améliore la région de débits atteignables, en comparaison avec une allocation uniforme et des schémas classiques de gestion dynamique du spectre.

38

Bouton, Eric. "Algorithmes d'allocation de ressources pour des systèmes à interférence". Paris, Télécom ParisTech, 2010. http://www.theses.fr/2010ENST0002.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

L'interférence est un phénomène présent dans de nombreux systèmes de communication et est souvent un sérieux frein à leur développement. Une gestion intelligente de ce phénomène est alors nécessaire, afin de limiter son impact négatif. Dans cette thèse, nous avons abordé trois sujets liés à sa présence. Dans la première partie, de façon à augmenter le débit de transmission dans les systèmes à ultra large bande basés sur des impulsions brèves, nous proposons d'attribuer plusieurs codes à saut temporel au même utilisateur. Ceci génère un nouveau type d'interférence associée aux codes supplémentaires alloués à l'utilisateur d'intérêt. Le bénéfice de ce type de stratégie n'étant pas immédiat, nous étudions l'impact de notre proposition sur les performances du système. Dans la deuxième partie, nous traitons le problème de l'optimisation de la probabilité de coupure dans un système multi-antennaire, soumis à un canal de Rice à évanouissement lent. Nous proposons d'optimiser cette probabilité dans le contexte à N antennes de transmission et une antenne de réception, lorsque le rapport signal-à-bruit est grand, et de l'améliorer dans le contexte à plusieurs antennes de transmission et plusieurs antennes de réception. Dans la dernière partie, nous étudions le problème de l'allocation de puissance dans un canal à interférence gaussien. En nous basant sur une nouvelle expression approchée de la capacité de ce canal et moyennant une modulation OFDM, nous proposons de développer un nouvel algorithme d'allocation de puissance qui améliore la région de débits atteignables, en comparaison avec une allocation uniforme et des schémas classiques de gestion dynamique du spectre
Interference is a phenomenon that is present in many communication systems and is often a serious hindrance to their development. An intelligent management of this phenomenon is thus necessary to limit its negative impact. In this thesis, we addressed three issues related to its presence. In the first part, in order to boost transmission rates in impulse radio ultra-wide band systems, we propose to assign multiple time-hopping codes to the same user. This generates a new type of interference associated with the additional codes allocated to the user of interest. Since the benefit of this type of strategy is not straightforward, we study the impact of our proposition on the system's performance. In the second part, we tackle the problem of optimizing the outage probability of multiple-antenna systems in a slow fading Rician channel. We propose to optimize this probability in the context of N transmit antennas and one single receive antenna, when the signal-to-noise ratio is high, and improve it when there are multiple antennas both at the transmitter and at the receiver. In the last part, we study the problem of power allocation in a Gaussian interference channel. Based on a new approximate expression of this channel's capacity and using an OFDM modulation, we propose to develop a new power allocation algorithm that improves the achievable rates region, compared with a uniform allocation and classic dynamic spectrum management techniques

39

Djouob, Charles. "Contribution à la synthèse des filtres microondes par une méthode de prédiction fondée sur des données expérimentales : application à la technologie microruban suspendu". Limoges, 1990. http://www.theses.fr/1990LIMO4001.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

40

Zaarour, Farah. "Channel estimation algorithms for OFDM in interference scenarios". Thesis, Lille 1, 2015. http://www.theses.fr/2015LIL10105/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

La rareté du spectre radio et la demande croissante de bande passante rendent l'optimisation de l'utilisation du spectre essentiel. Tandis qu'une efficacité maximale devrait être atteinte, un niveau minimal d'interférence devrait être maintenu. L’OFDM a été retenu comme un schéma de modulation dans plusieurs normes sans fil. L'estimation de canal est une tâche fondamentale dans les systèmes OFDM et elle devient plus difficile en présence d'interférence. Dans cette thèse, notre objectif est de proposer des algorithmes d'estimation de canal pour les systèmes OFDM en présence d’interférence, où les algorithmes classiques échouent. Tout d'abord, nous considérons l'environnement radio intelligente et nous proposons un nouveau cadre d'estimation de canal pour les canaux à variations rapides contaminés par des interférences bandes étroites (NBI). Cela est accompli avec l'algorithme EM et une expression explicite pour l'estimation de la puissance du bruit est obtenue. Ensuite, nous considérons un nouveau schéma de pilotes superposés (DNSP) qui assure des pilotes sans interférence au détriment d'interférence des donnés. Donc, un récepteur adapté à son design doit être conçu. Nous proposons un annuleur d’interférences (IC) à faible complexité pour les canaux à variations lentes avec DNSP. Cependant, la performance de l'IC proposé n'est fiable que quand l'erreur de l'estimation du canal est faible. Donc, dans une autre contribution, nous proposons un IC pour DNSP en tenant compte des erreurs d'estimation du canal. Enfin l'estimation robuste du canal est considérée comme l’une des perspectives de cette thèse
The scarcity of the radio spectrum and the increasing demand on bandwidth makes it vital to optimize the spectrum use. While a maximum efficiency should be attained, a minimal interference level should be maintained. OFDM has been selected as the modulation scheme in several wireless standards. Channel estimation is a fundamental task in OFDM and it becomes even more challenging in the presence of interference. In this thesis, our aim is to propose channel estimation algorithms for OFDM systems in the presence of interference, where conventional channel estimators designed for OFDM fail. First, we consider the cognitive radio environment and propose a novel channel estimation framework for fast time-varying channels in OFDM with NBI. This is accomplished through an expectation maximization (EM) based algorithm. This formulation allows us to obtain a closed-form expression for the estimation of the noise power. In this thesis, we are particularly interested in a very recent scheme of superimposed pilots for OFDM (DNSP). DNSP assures interference-free pilots at the expense of data interference. Seen the modernity of DNSP, a suitable receiver has to be designed to cope with its design. We first propose a low-complexity interference canceler (IC) for slow time-varying channels with DNSP. The performance of the proposed IC is guaranteed when the channel estimation error is small. As another contribution, we extend the design of the approximated IC for DNSP so as to take the channel estimation errors into account. Finally, we consider robust channel estimation which can be viewed as one of the perspectives of this thesis

41

Bouzegzi, Abdelaziz. "Algorithmes de discrimination de signaux pour la radio cognitive". Paris, Télécom ParisTech, 2009. http://www.theses.fr/2009ENST0048.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Dans le contexte de la Radio Cognitive, la reconnaissance des systèmes radio relève d’une grande importance (e. G. , Wifi, Wimax, 3GPP/LTE, DVB-T). Nous proposons d’étudier ce problème en se focalisant sur les systèmes basés sur la modulation OFDM largement utilisés actuellement. Nous avons noté que les standards existants diffèrent dans la valeur de l’espacement inter-porteuses utilisée. Par conséquent, nous avons développé des algorithmes qui se basent sur l’estimation de ce paramètre pour réaliser la reconnaissance aveugle du système intercepté. Les approches issues de la littérature et basées essentiellement sur l’utilisation du préfixe cyclique se retrouvent inefficaces dans le cas d’un très court préfixe ou d’un canal de propagation fortement sélectif en fréquence. Ce travail de thèse propose alors des solutions alternatives pour estimer les paramètres d’un signal OFDM en faisant appel à différentes approches : i) le kurtosis normalisé, ii) le principe du maximum de vraisemblance, iii) le filtrage adapté et iv) la cyclostationnarité d’ordre deux. Nous avons démontré la grande efficacité de ces algorithmes avec des conditions de fonctionnement très sévères ( un préfixe cyclique court, un canal de propagation très sélectif en fréquence, non sychronisation temporelle et/ou fréquentielle)
In the context of cognitive radio it is a crucial task to distinguish blindly various wireless systems (e. G. , Wifi, Wimax, 3GPP/LTE, DVB-T) from each others. We focus on the OFDM based systems which differ from their subcarrier spacing used in OFDM modulation. One can thus carry out recognition algorithms based on the value of the subcarrier spacing. Standard approaches developed in the literature rely on the detection of the cyclic prefix which enables to exhibit the value of the used subcarrier spacing. Nevertheless, these approaches fail when either the cyclic prefix duration is small or the channel impulse response is almost as large as the cyclic prefix. Therefore, this thesis proposes new algorithms to estimate the parameters of OFDM modulated signal (especially the subcarrier spacing) relying on i) the normalized kurtosis, ii) the maximum-likelihood principle, iii) the matched filter, and iv) the second-order cyclostationary property. We have shown the strong robustness of proposed algorithms to short cyclic prefix, multipath channel, time offset, and frequency offset

42

Allmendinger, Richard. "Tuning evolutionary search for closed-loop optimization". Thesis, University of Manchester, 2012. https://www.research.manchester.ac.uk/portal/en/theses/tuning-evolutionary-search-for-closedloop-optimization(d54e63e2-7927-42aa-b974-c41e717298cb).html.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Closed-loop optimization deals with problems in which candidate solutions are evaluated by conducting experiments, e.g. physical or biochemical experiments. Although this form of optimization is becoming more popular across the sciences, it may be subject to rather unexplored resourcing issues, as any experiment may require resources in order to be conducted. In this thesis we are concerned with understanding how evolutionary search is affected by three particular resourcing issues -- ephemeral resource constraints (ERCs), changes of variables, and lethal environments -- and the development of search strategies to combat these issues. The thesis makes three broad contributions. First, we motivate and formally define the resourcing issues considered. Here, concrete examples in a range of applications are given. Secondly, we theoretically and empirically investigate the effect of the resourcing issues considered on evolutionary search. This investigation reveals that resourcing issues affect optimization in general, and that clear patterns emerge relating specific properties of the different resourcing issues to performance effects. Thirdly, we develop and analyze various search strategies augmented on an evolutionary algorithm (EA) for coping with resourcing issues. To cope specifically with ERCs, we develop several static constraint-handling strategies, and investigate the application of reinforcement learning techniques to learn when to switch between these static strategies during an optimization process. We also develop several online resource-purchasing strategies to cope with ERCs that leave the arrangement of resources to the hands of the optimizer. For problems subject to changes of variables relating to the resources, we find that knowing which variables are changed provides an optimizer with valuable information, which we exploit using a novel dynamic strategy. Finally, for lethal environments, where visiting parts of the search space can cause the permanent loss of resources, we observe that a standard EA's population may be reduced in size rapidly, complicating the search for innovative solutions. To cope with such scenarios, we consider some non-standard EA setups that are able to innovate genetically whilst simultaneously mitigating risks to the evolving population.

43

Paraschakis, Dimitris. "Algorithmic and Ethical Aspects of Recommender Systems in e-Commerce". Licentiate thesis, Malmö universitet, Fakulteten för teknik och samhälle (TS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:mau:diva-7792.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Recommender systems have become an integral part of virtually every e-commerce application on the web. These systems enable users to quickly discover relevant products, at the same time increasing business value. Over the past decades, recommender systems have been modeled using numerous machine learning techniques. However, the adoptability of these models by commercial applications remains unclear. We assess the receptiveness of the industrial sector to algorithmic contributions of the research community by surveying more than 30 e-commerce platforms, and experimenting with various recommenders on proprietary e-commerce datasets. Another overlooked but important factor that complicates the design and use of recommender systems is their ethical implications. We identify and summarize these issues in our ethical recommendation framework, which also enables users to control sensitive moral aspects of recommendations via the proposed “ethical toolbox”. The feasibility of this tool is supported by the results of our user study. Because of moral implications associated with user profiling, we investigate algorithms capable of generating user-agnostic recommendations. We propose an ensemble learning scheme based on Thompson Sampling bandit policy, which models arms as base recommendation functions. We show how to adapt this algorithm to realistic situations when neither arm availability nor reward stationarity is guaranteed.

44

Rippl, Michael [Verfasser], Thomas [Akademischer Betreuer] Huckle, Bruno [Gutachter] Lang e Thomas [Gutachter] Huckle. "Parallel Algorithms for the Solution of Banded Symmetric Generalized Eigenvalue Problems / Michael Rippl ; Gutachter: Bruno Lang, Thomas Huckle ; Betreuer: Thomas Huckle". München : Universitätsbibliothek der TU München, 2020. http://d-nb.info/1230985379/34.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

45

Chaux, Caroline. "Analyse en ondelettes M-bandes en arbre dual : application à la restauration d'images". Phd thesis, Université de Marne la Vallée, 2006. http://tel.archives-ouvertes.fr/tel-00714292.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Cette thèse porte sur les décompositions en ondelettes M-bandes en arbre dual ainsi que sur leur application à l'analyse et la restauration d'images. Ces décompositions permettent d'obtenir une analyse multi-échelles, directionnelle et locale des images. Elles s'inscrivent donc dans la perspective de travaux récents visant à mieux représenter les informations géométriques (textures, contours) et les préserver lors de traitements. Ce travail s'appuie sur les travaux antérieurs de N. Kingsbury et I. Selesnick portant sur la construction de décompositions en ondelettes formant des paires de Hilbert (approchées). Ces auteurs ont établi divers résultats concernant le cas dyadique et l'une de nos contributions a été de montrer qu'il était possible de généraliser leurs conclusions et de montrer de nouveaux résultats dans le cas M-bandes. Les représentations proposées présentent de nombreux avantages notamment en termes d'invariance par translation de l'analyse et de sélectivité directionnelle. Nous avons établi les conditions que doivent satisfaire les bancs de filtres en arbre dual servant à l'analyse et à la synthèse des signaux traités. Nous avons également étudié les pré-traitements qu'il est nécessaire d'appliquer à des données discrètes. Ces décompositions introduisant typiquement une redondance d'un facteur 2 (dans le cas réel, et de 4 dans le cas complexe), elles constituent des trames à partir desquelles on peut calculer une reconstruction optimale. Ces nouvelles transformées ont finalement été généralisées aux cadres biorthogonal et complexe. Notre volonté d'appliquer ces outils d'analyse au débruitage de signaux nous a conduit à l'étude des propriétés statistiques des coefficients issus de la décomposition M-bandes en arbre dual d'un processus aléatoire stationnaire au sens large. Nous avons tout d'abord calculé les statistiques au second ordre de ces coefficients et nous avons étudié le rôle du post-traitement dans le calcul des corrélations. Quelques résultats asymptotiques concernant les corrélations d'un couple de coefficients primal/dual ont également été obtenus. Les inter-corrélations entre les ondelettes primale et duale jouant un rôle clé dans notre étude, nous en avons fourni des expressions exactes pour quelques familles d'ondelettes usuelles. Des simulations numériques nous ont aussi permis de valider nos résultats théoriques ainsi que d'évaluer la zone d'influence de la dépendance statistique induite. Pour démontrer l'efficacité de ces décompositions, nous avons été amenés à nous intéresser à deux types de problèmes : le débruitage et la déconvolution d'images. En ce qui concerne le débruitage, nous avons poursuivi deux buts principaux liés au cheminement de la thèse. Dans un premier temps, nous nous sommes attachés à montrer que la décomposition en arbre dual M-bandes apporte un gain significatif en terme de qualité, à la fois objective et subjective, par rapport à une décomposition en ondelettes classique, voire une décomposition dyadique en arbre dual. Dans un second temps, nous avons considéré le débruitage d'images multi-canaux pour lesquelles nous avons mis en place un estimateur statistique original reposant sur l'emploi du principe de Stein et permettant notamment de prendre en compte des voisinages quelconques (spatial, intercomposantes, inter-échelles, ...). Les problèmes de déconvolution d'images ont été appréhendés dans le cadre de méthodes variationnelles, en mettant en place un algorithme itératif, utilisant des outils récemment développés en analyse convexe. L'approche proposée permet de résoudre des problèmes inverses associés à des modèles probabilistes variés et elle est applicable à l'analyse M-bandes en arbre dual ainsi qu'à tout autre type de représentation à l'aide d'une trame.

46

Attalah, Samir. "Amélioration des performances des algorithmes LMS 1-D et 2-D : utilisation des techniques de décomposition en ondelettes, en sous-bandes et filtrage rapide". Bordeaux 1, 1996. http://www.theses.fr/1996BOR10666.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

La these porte sur l'amelioration des performances des algorithmes de type gradient-stochastique (dit lms) 1-d et 2-d par l'utilisation de techniques de decomposition en ondelettes orthogonales, en sous-bandes et du filtrage rapide. Dans le premier cas (lms 1-d), l'application de la transformee en ondelettes au signal d'entree, suppose colore, suivi d'une normalisation de l'energie des coefficients obtenus permet d'ameliorer le conditionnement de sa matrice d'autocorrelation et d'accelerer ainsi la convergence du lms 1-d. En plus de l'etude de ce type d'algorithme, nous proposons quelques versions rapides, dont la complexite de calcul est comparable a celle d'un lms 1-d temporel. Dans le deuxieme cas (lms 2-d), nous utilisons des techniques de filtrage rapide afin de reduire la complexite de calcul du lms 2-d sans toutefois affecter sa convergence. Ces nouveaux algorithmes sont, ensuite, appliques aux problemes d'annulation d'echo acoustique, d'egalisation et de rehaussement d'images

47

Elias, Jocelyne. "Allocation dynamique de la bande passante dans les réseaux à qualité de service". Paris 6, 2006. http://www.theses.fr/2006PA066169.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

48

Jin, Yan. "Hybrid metaheuristic algorithms for sum coloring and bandwidth coloring". Thesis, Angers, 2015. http://www.theses.fr/2015ANGE0062/document.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Le problème de somme coloration minimum (MSCP) et le problème de coloration de bande passante (BCP) sont deux généralisations importantes du problème de coloration des sommets classique avec de nombreuses applications dans divers domaines, y compris la conception de circuits imprimés, la planication, l’allocation de ressource, l’affectation de fréquence dans les réseaux mobiles, etc. Les problèmes MSCP et BCP étant NP-difficiles, les heuristiques et métaheuristiques sont souvent utilisées en pratique pour obtenir des solutions de bonne qualité en un temps de calcul acceptable. Cette thèse est consacrée à des métaheuristiques hybrides pour la résolution efcace des problèmes MSCP et BCP. Pour le problème MSCP, nous présentons deux algorithmes mémétiques qui combinent l’évolution d’une population d’individus avec de la recherche locale. Pour le problème BCP, nous proposons un algorithme hybride à base d’apprentissage faisant coopérer une méthode de construction “informée” avec une procédure de recherche locale. Les algorithmes développés sont évalués sur des instances biens connues et se révèlent très compétitifs par rapport à l’état de l’art. Les principaux composants des algorithmes que nous proposons sont également analysés
The minimum sum coloring problem (MSCP) and the bandwidth coloring problem (BCP) are two important generalizations of the classical vertex coloring problem with numerous applications in diverse domains, including VLSI design, scheduling, resource allocation and frequency assignment in mobile networks, etc. Since the MSCP and BCP are NP-hard problems, heuristics and metaheuristics are practical solution methods to obtain high quality solutions in an acceptable computing time. This thesis is dedicated to developing effective hybrid metaheuristic algorithms for the MSCP and BCP. For the MSCP, we present two memetic algorithms which combine population-based evolutionary search and local search. An effective algorithm for maximum independent set is devised for generating initial solutions. For the BCP, we propose a learning-based hybrid search algorithm which follows a cooperative framework between an informed construction procedure and a local search heuristic. The proposed algorithms are evaluated on well-known benchmark instances and show highly competitive performances compared to the current state-of-the-art algorithms from the literature. Furthermore, the key issues of these algorithms are investigated and analyzed

49

Bouneffouf, Djallel. "DRARS, A Dynamic Risk-Aware Recommender System". Phd thesis, Institut National des Télécommunications, 2013. http://tel.archives-ouvertes.fr/tel-01026136.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

L'immense quantité d'information générée et gérée au quotidien par les systèmes d'information et leurs utilisateurs conduit inéluctablement ?a la problématique de surcharge d'information. Dans ce contexte, les systèmes de recommandation traditionnels fournissent des informations pertinentes aux utilisateurs. Néanmoins, avec la propagation récente des dispositifs mobiles (Smartphones et tablettes), nous constatons une migration progressive des utilisateurs vers la manipulation d'environnements pérvasifs. Le problème avec les approches traditionnelles de recommandation est qu'elles n'utilisent pas toute l'information disponible pour produire des recommandations. Davantage d'informations contextuelles pourraient être utilisées dans le processus de recommandation pour aboutir à des recommandations plus précises. Les systèmes de recommandations sensibles au contexte (CARS) combinent les caractéristiques des systèmes sensibles au contexte et des systèmes de recommandation an de fournir des informations personnalisées aux utilisateurs dans des environnements ubiquitaires. Dans cette perspective ou tout ce qui concerne l'utilisateur est dynamique, les contenus qu'il manipule et son environnement, deux questions principales doivent être adressées : i) Comment prendre en compte la dynamicité des contenus de l'utilisateur ? et ii ) Comment éviter d'être intrusif en particulier dans des situations critiques ?. En réponse ?a ces questions, nous avons développé un système de recommandation dynamique et sensible au risque appelé DRARS (Dynamic Risk-Aware Recommender System), qui modélise la recommandation sensible au contexte comme un problème de bandit. Ce système combine une technique de filtrage basée sur le contenu et un algorithme de bandit contextuel. Nous avons montré que DRARS améliore la stratégie de l'algorithme UCB (Upper Con dence Bound), le meilleur algorithme actuellement disponible, en calculant la valeur d'exploration la plus optimale pour maintenir un compromis entre exploration et exploitation basé sur le niveau de risque de la situation courante de l'utilisateur. Nous avons mené des expériences dans un contexte industriel avec des données réelles et des utilisateurs réels et nous avons montré que la prise en compte du niveau de risque de la situation de l'utilisateur augmentait significativement la performance du système de recommandation.

50

Gomez-Villouta, Giglia. "Méthodes heuristiques pour le problème de placement sur bande en deux dimensions". Phd thesis, Université d'Angers, 2010. http://tel.archives-ouvertes.fr/tel-00575859.

Testo completo

Gli stili APA, Harvard, Vancouver, ISO e altri

Abstract (sommario):

Les problèmes de placement sont généralement NP-difficiles, ou NP-complets suivant l'objectif à atteindre. Il s'agit ici de positionner un ensemble d'objets dans un ou plusieurs “container(s)”, de dimensions données ou de hauteur infinie, en respectant des contraintes liées à certaines caractéristiques (poids, quantité, rotation, équilibre, découpe guillotine...). Ces problèmes ont de nombreuses applications pratiques. Les stratégies de résolution les plus efficaces sont généralement les méthodes approchées, en particulier la recherche locale. Dans cette thèse, nous nous intéressons à un problème de placement particulier en deux dimensions (sans rotation possible des objets (rectangulaires) ni prise en compte de la contrainte guillotine) connu sous le nom de “strip packing” (SPP). L'objectif de ce problème est de minimiser la hauteur atteinte après placement (sans chevauchement) des objets. Nous avons développé deux approches “méta-heuristiques” incluant des composants novateurs reposant sur une connaissance approfondie du problème. La première est un algorithme génétique avec un nouveau croisement (très “visuel”) et une fonction d'évaluation hiérarchique. La seconde est une recherche tabou avec représentation “directe” (i.e. n'utilisant pas les habituelles permutations) dont les caractéristiques principales sont un voisinage consistant, une diversification reposant sur l'historique de la recherche et une fonction d'évaluation qui mesure la qualité de solutions éventuellement partielles. Les deux approches proposées, évaluées sur un jeux de test bien connu et très difficile, se sont révélées performantes comparées à d'autres stratégies.

Tesi sul tema "Algorithme de bandit"

Cita una fonte nei formati APA, MLA, Chicago, Harvard e in molti altri stili