Speaker: Sebastien Bubeck
In the recent years the multi-armed bandit problem has attracted a lot of attention in the theoretical learning community. This growing interest is a consequence of the large number of problems that can be modeled as a multi-armed bandit: ad placement, website optimization, packet routing, ect. Furthermore the bandit methodology is also used as a building block for more complicated scenarios such as reinforcement learning, model selection in statistics, or computer game-playing. While the basic stochastic multi-armed bandit can be traced back to Thompson (1933) and Robbins (1952), it is only very recently that we obtained an (almost) complete understanding of this simple model. Moreover many extensions of the original problem have been proposed in the past fifteen years, such as bandits without a stochastic assumption (the so-called adversarial model), or bandits with a very large (but structured) set of arms.
The tutorial will be divided into three parts:
- In the first part we discuss the state-of-the-art results on the basic multi-armed bandit problem (both stochastic and adversarial).
- In the second part the focus will be on continuously-armed stochastic bandits, with a Lipschitz assumption on the mean-payoff.
- Finally in the third part we consider the case of adversarial bandits, with a linear loss and a very large set of arms with some combinatorial structure.
Sebastien Bubeck is an assistant professor in the department of Operations Research and Financial Engineering at Princeton University. He joined Princeton after a postdoc at the Centre de Recerca Matematica in Barcelona, where he was working with Gabor Lugosi. He received his Ph.D. in mathematics from the University of Lille 1, advised by Remi Munos, after undergraduate studies at the Ecole Normale Superieure de Cachan. His research focuses on the mathematics of machine learning, with emphasis on problems related to multi-armed bandits. His work was recognized by several awards, such as the COLT 2009 best student paper award, and the Jacques Neveu prize 2010 for the best French Ph.D. in Probability/Statistics.
Domain Adaptation in Real World Applications
Domain adaptation (a.k.a., cross-domain learning or transfer learning) has become an increasingly important research direction in machine learning and many other application areas. It is well-known that features sampled from different domains may differ tremendously in their distributions, such as mean, intra-class/inter-class variance. Domain adaptation methods have been developed to cope with such mismatch among domains. Recently they have also been successfully used in a broad range of real-world applications, in which the (target) domain of interest contains very few labeled samples, while an existing (auxiliary) domain is often available with a large number of labeled examples. We propose this tutorial with three specific objectives: 1) provide an overview of this fast-growing research area; ii) describe representative methods and their real-world applications to natural language processing, speech recognition and computer vision; iii) raise awareness of research challenges and engage discussions on future directions in this area.
Fei Sha is currently an Assistant Professor with U. of Southern California, Department of Computer Science. He received his Ph.D in 2007 from U. of Pennsylvania, Department of Computer and Information Science. Afterwards, he worked as a postdoctoral research at U. of California (Berkeley) and as a research scientist at Yahoo! Research. His primary research interests include statistical machine learning with applications to speech and language processing, computer vision, robotics and others. He received outstanding student paper awards at NIPS and ICML. He was a member of DARPA 2010 Computer Science Study Panel, and an awardee of Army Research Office 2012 Young Investigator Award.
Ivor W. Tsang is currently an Assistant Professor with the School of Computer Engineering, Nanyang Technological University (NTU), Singapore. He is also the Deputy Director of the Center for Computational Intelligence, NTU. He received his Ph.D. degree in computer science from the Hong Kong University of Science and Technology in 2007. His research focuses on support vector machines, large scale machine learning, transfer learning and their applications to data mining and pattern recognitions. He has more than 80 research papers published in refereed international journals and conference proceedings, including JMLR, T-NN, T-PAMI, Neural Computation, NIPS, ICML, UAI, AISTATS, SIGKDD, IJCAI, AAAI, EMNLP, ICCV, CVPR, ECCV, etc. Dr. Tsang received the prestigious IEEE Transactions on Neural Networks Outstanding 2004 Paper Award in 2006, and the second class prize of the National Natural Science Award 2008, China in 2009. His research earned him the Best Paper Award at ICTAI 11, the Best Student Paper Award at CVPR 10, and the Best Paper Award from the IEEE Hong Kong Chapter of Signal Processing Postgraduate Forum in 2006. He was also conferred with the Microsoft Fellowship in 2005. He has delivered a tutorial regarding Domain Transfer Learning for Vision Applications at CVPR 2012. He also gave an invited lecture about Structural Feature Selection for Very High Dimensional Problems in Machine Learning Summer School 2011. He has served as the workshop co-chair of NIPS 2009 workshop on Transfer Learning for Structured Data. He will serve as the local arrangement co-chair of Asian Conference of Machine Learning (ACML 2012) in Singapore.
Sinno Pan is currently a research scientist with the Data Mining Department, Institute for Infocomm Research (I2R), Singapore. He received his Ph.D. degree in computer science from the Hong Kong University of Science and Technology in 2010. His research interests include transfer learning, semi-supervised learning, active learning, and their applications to wireless-sensor-based data mining, text/Web mining, sentiment analysis, and Bioinformatics. He has published more than 20 research papers in refereed international journals and conference proceedings, including IEEE TPAMI, IEEE TNN, IEEE TKDE, IEEE/ACM TCBB, AIJ, AAAI, SIGKDD, IJCAI, ACL, WWW, UbiComp, etc. He was invited to give a lecture on Transfer Learning in Machine Learning Summer School 2011 in Singapore. He served as workshop co-chairs of the NIPS 2009 workshop on Transfer Learning for Structured Data and the ICDM 2009 workshop on Transfer Mining respectively. He also served as a co-guest editor of ACM Transactions on Intelligent Systems and Technology (ACM TIST) on the special issue: Domain Adaptation in Nature Language Processing. He is serving as the publication chair of Asian Conference of Machine Learning (ACML 2012) in Singapore.
Probabilistic Modeling of Ranking
Rankings and permutations have become, nowadays, ubiquitous. They appear in numerous areas of computer systems: information retrieval, recommender systems, identity tracking or chemical compound classification, etc. Dealing with rankings, and particularly with rankings of many objects is a complex computational task as the number of permutations of n objects scales factorially in n. Recently a number of approaches have come to the machine learning arena to address this kind of data. Most of these approaches are based on the building of a probability distribution over the space of rankings. However, given the complexity of storing, learning and making inference on this kind of models, different simplifying assumptions have been considered: the use of parametric models, models based on low-order statistics, models based on kernels and the definition and use of notions of independence and conditional independence in the space of permutations. In this tutorial we will review the literature on the topic, explaining the different approaches in detail that have emerged in the literature, putting them in relation with other non-probabilistic ranking models and giving a collection of open problems in the area. In addition we will present the most relevant applications in the field as well as the most common benchmark datasets and software.
Prof. Jose A. Lozano received an MSc degree in mathematics and an MSc degree in computer science from the the University of the Basque Country, Spain, in 1991 and 1992 respectively, and a PhD degree in computer science from the University of the Basque Country, Spain, in 1998. Since 2008 he is s full professor in the Department of Computer Science and Artificial Intelligence in the University of the Basque Country, where he leads the Intelligent Systems Group. He is the co-author of more than 50 ISI journal publications and co-editor of the first book published about Estimation of Distribution Algorithms. All his publications have received more than 3500 citations with an h-index of 24 (google scholar). His major research interests include machine learning, pattern analysis, evolutionary computation, data mining, metaheuristic algorithms, and real-world applications. Prof. Lozano is associate editor of IEEE Transactions on Evolutionary Computation and a member of the editorial board of Evolutionary Computation journal, Soft Computing, Applied Intelligence, Neural Computing and Applications and several non-ISI journals. He has been member of the program committee of the most relevant conferences in Machine Learning: ICML, ECML/PKDD, UAI, etc. and has given several tutorials in those conferences.
Ekhine Irurozki received the MSc degree in computer science from the University of the Basque Country, Spain, in 2008. She is currently a PhD student of the Intelligent Systems Group at the same university. Mrs. Irurozki is supported by a PhD grant of the Spanish Ministry of Science. She has co-authored a publication in the field of Bioinformatics in the IEEE/ACM Transactions on Computational Biology and Bioinformatics and another one in the field of Machine Learning in Lecture Notes in Computer Science. She has also reviewed for the journal IEEE/ACM Transactions on Computational Biology and attended several international conferences. Her research interests include combinatorial optimization and machine learning. She is particularly interested on probability distributions on the space of permutations where currently work on the development of new techniques for efficiently learning and sampling permutations of that kind of models.