No description available.

Indiana University-Purdue University Indianapolis (IUPUI) / The internet is the home for massive volumes of valuable data constantly being created, making it difficult for users to find information relevant to them. In recent times, online users have been relying on the recommendations made by websites to narrow down the options. Online reviews have also become an increasingly important factor in the final choice of a customer. Unfortunately, attackers have found ways to manipulate both reviews and recommendations to mislead users. A Recommendation System is a special type of information filtering system adapted by online vendors to provide suggestions to their customers based on their requirements. Collaborative filtering is one of the most widely used recommendation systems; unfortunately, it is prone to shilling/profile injection attacks. Such attacks alter the recommendation process to promote or demote a particular product. On the other hand, many spammers write deceptive reviews to change the credibility of a product/service. This work aims to address these issues by treating the review manipulation and shilling attack scenarios independently. For the shilling attacks, we build an efficient Reinforcement Learning-based shilling attack method. This method reduces the uncertainty associated with the item selection process and finds the most optimal items to enhance attack reach while treating the recommender system as a black box. Such practical online attacks open new avenues for research in building more robust recommender systems. When it comes to review manipulations, we introduce a method to use a deep structure embedding approach that preserves highly nonlinear structural information and the dynamic aspects of user reviews to identify and cluster the spam users. It is worth mentioning that, in the experiment with real datasets, our method captures about 92\% of all spam reviewers using an unsupervised learning approach.

No description available.

In this thesis we address the multi-armed bandit (MAB) problem with stochastic rewards and correlated arms. Particularly, we investigate the case when the expected rewards are a Lipschitz function of the arm, and the learning to rank problem, as viewed from a MAB perspective. For the former, we derive a problem specific lower bound and propose both an asymptotically optimal algorithm (OSLB) and a (pareto)optimal, algorithm (POSLB). For the latter, we construct the regret lower bound and determine its closed form for some particular settings, as well as propose two asymptotically optimal algorithms PIE and PIE-C. For all algorithms mentioned above, we present performance analysis in the form of theoretical regret guarantees as well as numerical evaluation on artificial datasets as well as real-world datasets, in the case of PIE and PIE-C. / <p>QC 20160223</p>

Multi-armed bandits (MABs) have been studied extensively in the literature and have applications in a wealth of domains, including recommendation systems, dynamic pricing, and investment management. On the one hand, the current MAB literature largely seems to focus on the setting where each arm is available to play at each time step, and ignores how agents move between the arms. On the other hand, there is work that takes the movement between arms into account, but this work models the problem as a Markov decision process and applies generic reinforcement learning (RL) algorithms, like Q-learning. This thesis examines an extension of the MAB problem to a setting where the set of available arms at each round depends on which arm was played in the previous round. In this formulation the arms are nodes in a graph, and arms that can be played successively are connected via edges. We denote this the Graph Bandit (GB) problem. We show that under certain conditions the optimal action is governed by a stationary policy. Furthermore, we develop an algorithm that leverages the graphical structure of the problem to find this policy when the reward distributions are perfectly known, and denote this algorithm the Q-graph. When the reward distributions are unknown, we show how to leverage the Qgraph algorithm together with standard sampling algorithms like Thompson sampling and upper confidence bound to create an online learning algorithm that provably achieves logarithmic regret. Finally, this regret-bound is supported in numerical simulations, and it is illustrated how the proposed Q-graph algorithm outperforms generic algorithms from the MAB and RL communities. / Flerarmade banditer (FAB) har studerats omfattande i litteraturen och har applikationer inom en mängd domäner, såsom rekommendationssystem, dynamisk prissättning och finans. Å ena sidan verkar det som at en stor del av litteraturen fokuserar på situationen där alla armar är tillgängliga att spela vid varje tidssteg och ignorerar hur agenten rör sig mellan armarna. Å andra sidan finns det arbete som tar till hänsyn hur agenten rör sig mellan armarna men det arbetet modellerar systemet som en Markovprocess och använder sig av generiska inlärningsmetoder, såsom Q-learning. Den här uppsatsen undersöker en utvidgning av FAB-problemet till en situation där mängden tillgänliga armar vid varje runda beror på vilken arm som spelades i den föregående rundan. I denna formulering är armarna noder i en graf och armar som kan spelas i på varandra följande rundor är anslutna via kanter. Vi kallar det här problemt Grafbanditen. Vi visar att under vissa förutsättningar bestäms det optimala aggerandet av en stationär policy. Vi utvecklar också en algoritm som utnyttjar den grafiska strukturen i problemet för att beräkna denna policy när distributionerna hos alla armar är kända. Denna algoritm får namnet Q-grafen. När distributionerna är okända visar vi hur Q-grafen kan användas tillsammans med Thompson sampling eller upper confidence bound-metoder för att skapa en online inlärningsalgoritm som bevisligen uppnår logaritmisk regret. Slutligen stöds de teoretiska resultaten via numeriska simuleringar som illustrerar att Q-grafen är överlägsen många generiska inlärningsalgoritmer.

The fifth generation networks is rapidly becoming the new network standardand its new technological capabilities are expected to enable a far widervariety of services compared to the fourth generation networks. To ensurethat these services can co-exist and meet their standardized requirements,the network’s resources must be provisioned, managed and reconfigured ina far more complex manner than before. As such, it is no longer sufficientto select a simple, static scheme for gathering the necessary information totake decisions. Instead, it is necessary to adaptively, with regards to networksystem dynamics, trade-off the cost in terms of power, CPU and bandwidthconsumption of the taken measurements to the value their information brings.Orchestration is a wide field, and the way to quantify the value of a givenmeasurement heavily depends on the problem studied. As such, this thesisaddresses adaptive measurement schemes for a number of well-defined networkoptimization problems. The thesis is presented as a compilation, whereafter an introduction detailing the background, purpose, problem formulation,methodology and contributions of our work, we present each problemseparately through the papers submitted to several conferences. First, we study the problem of optimal spectrum access for low priorityservices. We assume that the network manager has limited opportunitiesto measure the spectrum before assigning one (if any) resource block to thesecondary service for transmission, and this measurement has a known costattached to it. We study this framework through the lens of multi-armedbandits with multiple arm pulls per decision, a framework we call predictivebandits. We analyze such bandits and show a problem specific lower bound ontheir regret, as well as design an algorithm which meets this regret asymptotically,studying both the case where measurements are perfect and the casewhere the measurement has noise of known quantity. Studying a syntheticsimulated problem, we find that it performs considerably better compared toa simple benchmark strategy. Secondly, we study a variation of admission control where the controllermust select one of multiple slices to enter a new service into. The agentdoes not know the resources available in the slices initially, and must insteadmeasure these, subject to noise. Mimicking three commonly used admissioncontrol strategies, we study this as a best arm identification problem, whereone or multiple arms is ”correct” (the arm chose by the strategy if it had fullinformation). Through this framework, we analyze each strategy and devisesample complexity lower bounds, as well as algorithms that meet these lowerbounds. In simulations with synthetic data, we show that our measurementalgorithm can vastly reduce the number of required measurements comparedto uniform sampling strategies. Finally, we study a network monitoring system where the controller mustdetect sudden changes in system behavior such as batch traffic arrivals orhandovers, in order to take future action. We study this through the lensof change point detection but argue that the classical framework is insufficientfor capturing both physical time aspects such as delay as well as measurementcosts independently, and present an alternative framework whichiidecouples these, requiring more sophisticated monitoring agents. We show,both through theory and through simulation with both synthetic data anddata from a 5G testbed, that such adaptive schedules qualitatively and quantitativelyimprove upon classical change point detection schemes in terms ofmeasurment frequency, without losing classical optimality guarantees such asthe one on required measurements post change. / Femte generationens nätverk håller snabbt på att bli den nya standarden och dess teknologiska förmågor förväntas bereda väg för en avsevärt större variation av tjänster jämfört med fjärde generationens nätverk. För att se till att dessa tjänster kan samexistera och möta sina standardiserade krav måste nätverkens resurser provisioneras, hanteras och omkonfigureras på ett mycket mer komplext vis än tidigare. Det är därmed inte längre tillräckligt att välja en simpel, statisk plan för att samla den nödvändiga information som krävs för att ta beslut. Istället behöver man adaptivt, med hänsyn till nätversystemens dynamik, avväga mätningarnas kostnad i termer av effekt-, CPU- och bandbreddskonsumtion mot det värde som de medför. Den här sortens nätverksorkestrering är ett brett fält, och hur mätningarnas värde ska kvantifieras beror i hög grad på vilket optimeringsproblem som studeras. Således bemöter den här avhandlningen adaptiva mätplaner för ett antal väldefinerade optimeringsproblem. Avhandlingen tar formen av en sammanlänkning, där följandes en introduktion som beskriver bakgrund, syfte, problemformulering, metodologi och forskningsbidrag så presenterar vi varje problem separat genom de artiklar vi inlämnat till olika konferenser. Först studerar vi optimal spektrumaccess för lågprioritetstjänster. Vi antar att nätverksregulatorn har begränsat med möjligheter att mäta spektrumanvändning innan den tillger som mest ett resursblock till tjänsten med lägre prioritet att skicka data på, och de här mätningarna har en känd kostnad. Vi studerar det här ramverket från perspektivet av flerarmade banditer med flera armdragningar per beslut, ett ramverk vi benämner förutsägande banditer (predictive bandits). Vi analyserar sådana banditer och visar en problemspecifik undre gräns på dess inlärningsförlust, samt designar en algorithm som presterar lika bra som denna gräns i den asymptotiska regimen. Vi studerar fallet där mätningarna är perfekta såväl som fallet där mätningarna har brus med känd storlek. Genom att studera ett syntetiskt simulerat problem av detta slag finner vi att vår algoritm presterar avsevärt bättre jämfört med en simplare riktmärkesstrategi. Därefter studerar vi en variation av tillträdeskontroll, där en regulator måste välja en av ett antal betjänter att släppa in en ny tjänst till (om någon alls). Agenten vet ursprungligen inte vilka resurser som finns betjänterna tillgängliga, utan måste mäta detta med brusiga mätningar. Vi härmar tre vanligt använda tillträdesstrategier och studerar detta som ett bästa-arms identifieringsproblem, där en eller flera armar är "korrekta" (det vill säga, de armar som hade valts av tillträdesstrategin om den hade haft perfekt kännedom). Med det här ramverket analyserar vi varje strategi och visar undre gränser på antalet mätningar som krävs, och skapar algoritmer som möter dessa gränser. I simuleringar med syntetisk data visar vi att våra mätalgoritmer kan drastiskt reducera antalet mätningar som krävs jämfört med jämlika mätstrategier. Slutligen studerar vi ett övervakningssystem där agenten måste upptäcka plötsliga förändringar i systemets beteende såsom förändringar i trafiken eller överräckningar mellan master, för att kunna agera därefter. Vi studerar detta med ramverket förändringsdetektion, men argumenterar att det klassiska ramverket är otillräckligt för att bemöta aspekter berörande fysisk tid (som fördröjning) samtidigt som den bemöter  mätningarnas kostnad. Vi presenterar därmed ett alternativt ramverk som frikopplar de två, vilket i sin tur kräver mer sostifikerade övervakningssystem. Vi visar, genom både teori och simulering med både syntetisk och experimentell data, att sådana adaptiva mätscheman kan förbättra mätfrekvensen jämfört med klassiska periodiska mätscheman, både kvalitativt och kvantitativt, utan att förlora klassiska optimalitetsgarantier såsom det på antalet mätningar som behövs när förändringen har skett. / <p>QC 20230915</p>

"A common problem shared amongst online tutoring systems is the time-consuming nature of content creation. It has been estimated that an hour of online instruction can take up to 100-300 hours to create. Several systems have created tools to expedite content creation, such as the Cognitive Tutors Authoring Tool (CTAT) and the ASSISTments builder. Although these tools make content creation more efficient, they all still depend on the efforts of a content creator and/or past historical. These tools do not take full advantage of the power of the crowd. These issues and challenges faced by online tutoring systems provide an ideal environment to implement a solution using crowdsourcing. I created the PeerASSIST system to provide a solution to the challenges faced with tutoring content creation. PeerASSIST crowdsources the work students have done on problems inside the ASSISTments online tutoring system and redistributes that work as a form of tutoring to their peers, who are in need of assistance. Multi-objective multi-armed bandit algorithms are used to distribute student work, which balance exploring which work is good and exploiting the best currently known work. These policies are customized to run in a real-world environment with multiple asynchronous reward functions and an infinite number of actions. Inspired by major companies such as Google, Facebook, and Bing, PeerASSIST is also designed as a platform for simultaneous online experimentation in real-time and at scale. Currently over 600 teachers (grades K-12) are requiring students to show their work. Over 300,000 instances of student work have been collected from over 18,000 students across 28,000 problems. From the student work collected, 2,000 instances have been redistributed to over 550 students who needed help over the past few months. I conducted a randomized controlled experiment to evaluate the effectiveness of PeerASSIST on student performance. Other contributions include representing learning maps as Bayesian networks to model student performance, creating a machine-learning algorithm to derive student incorrect processes from their incorrect answer and the inputs of the problem, and applying Bayesian hypothesis testing to A/B experiments. We showed that learning maps can be simplified without practical loss of accuracy and that time series data is necessary to simplify learning maps if the static data is highly correlated. I also created several interventions to evaluate the effectiveness of the buggy messages generated from the machine-learned incorrect processes. The null results of these experiments demonstrate the difficulty of creating a successful tutoring and suggest that other methods of tutoring content creation (i.e. PeerASSIST) should be explored."

Cette thèse s'inscrit dans les domaines de l'apprentissage statistique et de la statistique séquentielle. Le cadre principal est celui des problèmes de bandit stochastique à plusieurs bras. Dans une première partie, on commence par revisiter les bornes inférieures sur le regret. On obtient ainsi des bornes non-asymptotiques dépendantes de la distribution que l'on prouve de manière très simple en se limitant à quelques propriétés bien connues de la divergence de Kullback-Leibler. Puis, on propose des algorithmes pour la minimisation du regret dans les problèmes de bandit stochastique paramétrique dont les bras appartiennent à une certaine famille exponentielle ou non-paramétrique en supposant seulement que les bras sont à support dans l'intervalle unité, pour lesquels on prouve l'optimalité asymptotique (au sens de la borne inférieure de Lai et Robbins) et l'optimalité minimax. On analyse aussi la complexité pour l'échantillonnage séquentielle visant à identifier la distribution ayant la moyenne la plus proche d'un seuil fixé, avec ou sans l'hypothèse que les moyennes des bras forment une suite croissante. Ce travail est motivé par l'étude des essais cliniques de phase I, où l'hypothèse de croissance est naturelle. Finalement, on étend l'inégalité de Fano qui contrôle la probabilité d'évènements disjoints avec une moyenne de divergences de Kullback-leibler à des variables aléatoires arbitraires bornées sur l'intervalle unité. Plusieurs nouvelles applications en découlent, les plus importantes étant une borne inférieure sur la vitesse de concentration de l'a posteriori Bayésien et une borne inférieure sur le regret pour un problème de bandit non-stochastique. / The topics addressed in this thesis lie in statistical machine learning and sequential statistic. Our main framework is the stochastic multi-armed bandit problems. In this work we revisit lower bounds on the regret. We obtain non-asymptotic, distribution-dependent bounds and provide simple proofs based only on well-known properties of Kullback-Leibler divergence. These bounds show in particular that in the initial phase the regret grows almost linearly, and that the well-known logarithmic growth of the regret only holds in a final phase. Then, we propose algorithms for regret minimization in stochastic bandit models with exponential families of distributions or with distribution only assumed to be supported by the unit interval, that are simultaneously asymptotically optimal (in the sense of Lai and Robbins lower bound) and minimax optimal. We also analyze the sample complexity of sequentially identifying the distribution whose expectation is the closest to some given threshold, with and without the assumption that the mean values of the distributions are increasing. This work is motivated by phase I clinical trials, a practically important setting where the arm means are increasing by nature. Finally we extend Fano's inequality, which controls the average probability of (disjoint) events in terms of the average of some Kullback-Leibler divergences, to work with arbitrary unit-valued random variables. Several novel applications are provided, in which the consideration of random variables is particularly handy. The most important applications deal with the problem of Bayesian posterior concentration (minimax or distribution-dependent) rates and with a lower bound on the regret in non-stochastic sequential learning.

Lorsque les internautes naviguent sur le Web, ils laissent de nombreuses traces que nous nous proposons d’exploiter pour améliorer les applications d'accès à l'information. Nous étudions des techniques centrées sur les utilisateurs qui tirent parti des nombreux types de rétroaction pour perfectionner les services offerts aux utilisateurs. Nous nous concentrons sur des applications telles que la recommandation et le marketing d’influence dans lesquelles les utilisateurs génèrent des signaux (clics, "j'aime", etc.) que nous intégrons dans nos algorithmes afin de fournir des services fortement contextualisés. La première partie de cette thèse est consacrée à une approche interactive de la recherche d'information sur les médias sociaux. Le problème consiste à récupérer un ensemble de k résultats dans un réseau social sous la contrainte que la requête peut être incomplète (par exemple, si le dernier terme est un préfixe). Chaque fois que l'utilisateur met à jour sa requête, le système met à jour l'ensemble des résultats de recherche en conséquence. Nous adoptons une interprétation de la pertinence de l'information qui tient compte du réseau, selon laquelle l'information produite par les utilisateurs proches de l'utilisateur faisant la requête est jugée plus pertinente. Ensuite, nous étudions une version générique de la maximisation de l'influence, dans laquelle nous voulons maximiser l'influence des campagnes d'information ou de marketing en sélectionnant de manière adaptative les utilisateurs initiant la propagation de l'information parmi un petit sous-ensemble de la population. Notre approche ne fait aucune hypothèse sur le modèle de diffusion sous-jacent ni même sur la structure du réseau de diffusion. Notre méthode a d'importantes applications dans le marketing d’influence qui vise à s’appuyer sur les influenceurs de réseaux sociaux pour promouvoir des produits ou des idées. Enfin, nous abordons le problème bien connu du démarrage à froid auquel sont confrontés les systèmes de recommandation par une approche adaptative. Si aucune information n’est disponible concernant l'appréciation d’un article, le système de recommandation doit recueillir des signaux (clics, etc.) afin d'estimer la valeur de l'article. Cependant, afin de minimiser les mauvaises recommandations faites aux utilisateurs, le système ne doit pas recueillir ces signaux de façon négligente. Nous introduisons un algorithme dynamique qui vise à alterner intelligemment les recommandations visant à accumuler de l'information et celles s'appuyant sur les données déjà recueillies. / When users interact on modern Web systems, they let numerous footprints which we propose to exploit in order to develop better applications for information access. We study a family of techniques centered on users, which take advantage of the many types of feedback to adapt and improve services provided to users. We focus on applications like recommendation and influencer marketing in which users generate discrete feedback (e.g. clicks, "likes", reposts, etc.) that we incorporate in our algorithms in order to deliver strongly contextualized services. The first part of this dissertation is dedicated to an approach for as-you-type search on social media. The problem consists in retrieving a set of k search results in a social-aware environment under the constraint that the query may be incomplete (e.g., if the last term is a prefix). Every time the user updates his / her query, the system updates the set of search results accordingly. We adopt a "network-aware" interpretation of information relevance, by which information produced by users who are closer to the user issuing a request is considered more relevant. Then, we study a generic version of influence maximization, in which we want to maximize the influence of marketing or information campaigns by adaptively selecting "spread seeds" from a small subset of the population. Influencer marketing is a straightforward application of this, in which the focus of a campaign is placed on precise key individuals who are typically able to reach millions of consumers. This represents an unprecedented tool for online marketing that we propose to improve using an adaptive approach. Notably, our approach makes no assumptions on the underlying diffusion model and no diffusion network is needed. Finally, we propose to address the well-known cold start problem faced by recommender systems with an adaptive approach. If no information is available regarding the user appreciation of an item, the recommender system needs to gather feedback (e.g., clicks) so as to estimate the value of the item. However, in order to minimize "bad" recommendations, a well-designed system should not collect feedback carelessly. We introduce a dynamic algorithm that aims to intelligently achieve the balance between "bad" and "good" recommendations.

No description available.