Indo-US Symposium on

New Directions in Machine Learning, Game Theory, and Optimization

Bangalore, November 12-13 2010


[Program]  [Speaker Abstracts]  [Poster Session]  [Travel Awards]  [Visitor Information]  [Report]  [Organization]  [Sponsors] 


Overview

With the virtual explosion in the magnitude of data being generated across the world -- in fields as diverse as astronomy, biology, geology, and even defense -- there is an urgent need for methods that can analyze such data and transform it into meaningful scientific conclusions. Machine learning, one of the fastest growing fields in computer science, holds the promise of providing such methods. For example, machine learning techniques are being used in computer vision to develop face recognition systems, in computational biology to discover new genes, and in drug discovery to prioritize chemical structures for screening.

Machine learning is a highly interdisciplinary field that brings together techniques from a variety of mathematical and engineering disciplines, including in particular computer science, statistics, and mathematical optimization, in order to analyze complex data. It is anticipated that future developments in machine learning will depend on a stronger understanding of the mathematical optimization tools that form the core of many modern machine learning algorithms, and on expanding the range of problems for which machine learning algorithms can be developed, for example allowing for situations involving multiple players (as is often the case with the internet or the healthcare industry) by incorporating techniques from game theory. In turn, machine learning techniques can be used for portfolio selection in optimization, and for mechanism design in game theory.

To this end, this symposium aims to bring together researchers from India and the US to share their perspectives on both recent advances in the fields of machine learning, game theory, and optimization, and challenges that lie ahead. Our hope is that the interactions initiated at this symposium will act as a catalyst for further Indo-US collaborations, particularly at the interface of these exciting disciplines.

Program

Friday November 12  

Venue: Indian Institute of Science, Faculty Hall
Registration: Open to all

  1:00 - 1:55 pm Registration
  1:55 - 2:00 pm Welcome & Introduction [slides]
  2:00 - 3:30 pm







Session Chair: Y. Narahari

Avrim Blum
Approximate Clustering Without the Approximation Algorithm,
and a New Approach to Optimization
[slides]

Devavrat Shah
Message Passing Networks: Inference, Optimization and Games [slides]
  3:30 - 4:00 pm Coffee Break
  4:00 - 5:30 pm






Session Chair: David Parkes

Y. Narahari
Design of Mechanisms for Dynamic Environments [slides]

Gert Lanckriet
Learning Multi-Modal Similarity: A Novel Multiple Kernel Learning Technique

Saturday November 13  

Venue: Lalit Ashok Hotel, Convention Hall
Registration: By invitation

  8:00 -   9:15 am Breakfast & Registration
  9:30 - 11:00 am






Session Chair: Avrim Blum

Ravi Kannan
k-Means Converges

Dinesh Garg
Market Design for Data Labeling [slides]
11:00 - 11:30 am Coffee Break
11:30 -   1:00 pm






Session Chair: Devavrat Shah

Chiranjib Bhattacharyya
On the Design of Kernels [slides]

Shivani Agarwal
Learning to Rank: Optimization of Ranking Performance Measures [slides]
  1:00 -   2:00 pm Lunch
  2:00 -   3:30 pm






Session Chair: Chiranjib Bhattacharyya

David Parkes
The Interplay of Machine Learning and Mechanism Design [slides]

Indrajit Bhattacharya
Collective Relational Clustering [slides]
  3:30 -   4:00 pm Coffee Break
  4:00 -   5:30 pm






Session Chair: Shivani Agarwal

Kameshwaran Sampath
Two-sided Matching Mechanisms for Project Fulfillment

B. Ravindran
Finding Approximate Symmetries of Markov Decision Processes
  5:30 -   7:00 pm Poster Session
  7:00 - 10:00 pm Banquet Dinner (Poolside)

Speaker Abstracts

Shivani Agarwal
Indian Institute of Science

Learning to Rank: Optimization of Ranking Performance Measures

Abstract: Ranking problems have received increasing attention in machine learning and data mining in recent years. Such problems arise in a variety of domains, ranging from recommendation systems to information retrieval and from computational biology to drug discovery. In this talk, I will briefly survey some of the popular approaches to ranking in machine learning, including both basic algorithms and more recent algorithms that focus on optimizing ranking accuracy at the top of the list, and will describe a new algorithm called the Infinite Push that is designed to optimize accuracy at the absolute top of a ranked list. I will conclude with some examples of applications of ranking methods in drug discovery, in information retrieval, and in computational biology.

Bio: Shivani Agarwal is currently an Assistant Professor in the Department of Computer Science & Automation at the Indian Institute of Science. Prior to this she was a postdoctoral lecturer and associate in the Computer Science and Artificial Intelligence Laboratory at MIT. She obtained her PhD in Computer Science at the University of Illinois, Urbana-Champaign, where she received the Liu Award for her research; an MA in Computer Science at Trinity College, University of Cambridge, where she was a Nehru Scholar; and a BSc with Honors in Mathematics at St Stephen's College, University of Delhi. Her research interests include machine learning and learning theory, in particular the study of ranking and other new learning problems, as well as applications of machine learning methods, particularly in the life sciences. More broadly, she is excited by research at the intersection of computer science, mathematics, and statistics, and its applications in scientific discovery.

Indrajit Bhattacharya
Indian Institute of Science

Collective Relational Clustering

Abstract: Over the last decade or so, abundant data that is relational in nature has been generated by many different applications. Hyperlink data from the internet, citation data from scientific literature, data from social and telecommunication networks, biological interaction data, retail data on customer shopping patterns are some examples. The recent years have seen a lot of research in the emerging area of unsupervised learning or clustering over such relational data. Traditional clustering approaches based on features of individual data items are insufficient for this problem. In contrast, in collective relational clustering, clustering decisions are made jointly over relational neighborhoods in the network. In this talk, I will first introduce the collective relational clustering problem, and touch upon the different approaches that have been proposed. Then I will talk about the probabilistic approach in more detail. Specifically, I will present probabilistic graphical models that capture cluster relationships using latent groups over the clusters. Inference in such models is a challenge, and I will describe efficient approximate algorithms based on sampling methods.

Bio: Indrajit Bhattacharya is an Assistant Professor in the Department of Computer Science and Automation at the Indian Institute of Science, Bangalore. While his broad area of interest is machine learning and data mining, his research focus is on models for clustering in multi-relational data mentioning different entities and their relationships. He received his PhD in Computer Science from the University of Maryland, College Park in December 2006. Prior to joining IISc in June 2010, he worked as a Research Scientist at IBM Research - India since April 2007.

Chiranjib Bhattacharyya
Indian Institute of Science

On the Design of Kernels

Abstract: Methods based on Kernel functions have emerged as powerful tools for several learning tasks. The choice of Kernel function is an important area of research which involves Convex Optimization and Statistics. In the Multiple Kernel Learning (MKL) framework one chooses a kernel function from a conic combination of multiple pre-specified kernels. Existing results apply to either the sparse or the non-sparse setting of MKL. We will discuss a novel formulation and efficient algorithm, based on Mirror Descent procedure, which works for both the settings. In reality it is often easier to specify similarity functions rather than kernels. We report results which address the open question of kernel choice given multiple similarity functions. Time permitting we will present our progress on the issue of robust classifiers when the kernel is corrupted by noise.

Bio: Chiranjib Bhattacharyya is an Associate Professor in the Dept of Computer Science and Automation, Indian Institute of Science. His research interests are in Machine Learning. For more details of his work please see http://drona.csa.iisc.ernet.in/~chiru

Avrim Blum
Carnegie Mellon University

Approximate Clustering Without the Approximation Algorithm, and a New Approach to Optimization

Abstract: Many important optimization problems unfortunately turn out to be NP-hard, even to approximate well. In this talk, I will discuss an approach---especially for problems of identifying hidden patterns in data or predicting behavior in a multiagent system---that in some cases can bypass these hardness results by using implicit assumptions in the problem formulations. In particular, often in these settings the optimization objective is a proxy for some other underlying goal. For example, a distance-based clustering objective (such as k-means) for clustering protein sequences is generally a proxy for a true goal of correctly identifying the functions of the proteins; computing an (approximate) equilibrium may be primarily a proxy for a true goal of predicting behavior. Making explicit the assumption (or hope) that a good solution to the formal objective implies a good solution to the final goal yields structure that an algorithm can potentially use. As one example, for clustering we show that if a c-approximation to the k-means or k-median objective would be sufficient to yield solutions that are epsilon-close to a desired target clustering, then we can produce clusterings that are O(epsilon)-close to the target, even for values c for which obtaining a c-approximation is NP-hard. In particular, we achieve this guarantee for *any* constant c>1. We also discuss initial steps in this direction for the problem of estimating Nash equilibria, and connections to a related condition of perturbation stability.

This talk includes work joint with Nina Balcan, Pranjal Awasthi, Anupam Gupta, Or Sheffet, and Santosh Vempala.

Bio: Avrim Blum is Professor of Computer Science at Carnegie Mellon University. He received his PhD from MIT in 1991 under Prof. Ronald Rivest. His main research interests are in Machine Learning Theory, Approximation Algorithms, and Algorithmic Game Theory, and he is also known for his work in AI Planning. He has served as Program Chair for the IEEE Symposium on Foundations of Computer Science (FOCS) and the Conference on Learning Theory (COLT), and on the organizing committee for the U.S. National Academy of Sciences Frontiers of Science Symposium. He was recipient of the Sloan Fellowship, the NSF National Young Investigator Award, and the ICML/COLT 10-year best paper award, and is a Fellow of the ACM.

Dinesh Garg
Yahoo! Labs Bangalore

Market Design for Data Labeling

Abstract: In many practical situations such as web page annotation, crowdsourcing, and medical image diagnostic, a learning agent needs to train a classifier through data coming from multiple human annotators where each annotator possibly makes mistakes in labeling the data and also charges a price for providing data labeling service. In this talk, I will present a simple and scalable PAC learning scheme for two class classification problem where training examples are subjected to noisy labels. The noisy labeled examples are obtained from two annotators where each annotator is characterized by its classification noise rate and annotation price per example. The learning algorithm is given a fixed budget and the algorithm needs to decide the purchase plan for data labeling services from each of the two annotators. The goal is to keep the data labeling cost within a given budget while maintaining the quality of the learnt concept at a minimum specified PAC level. For this scenario, given a concept class and noise rates, we derive theoretical bounds on the number of examples (labeled from each annotator), learning budget, and annotation prices from PAC learning perspective. We also analyze a Data Labeling Marketplace which naturally arises among annotators (service providers) and learning agent (service consumer). We also analyze a Data Labeling Marketplace which naturally arises among annotators (service providers) and learning agent (service consumer). We formulate a non-cooperative game to model the joint decision making problems faced by the annotators and the learning agent and derive an insightful result for market equilibrium in this setting.

Ravi Kannan
Microsoft Research India

k-Means Converges

Abstract: The k-means algorithm is widely used. No proof of its convergence is known. We will supply one under the assumption that "most'' points are "in proximity'' to the centres of their clusters, a condition which will be formalized. We show that in most probabilistic models so far studied, this assumption holds and so this proof subsumes earlier results.

Joint work with Amit Kumar, IIT Delhi.

Gert Lanckriet
University of California, San Diego

Learning Multi-Modal Similarity: A Novel Multiple Kernel Learning Technique

Abstract: In many applications involving multimedia data, the definition of similarity between items is integral to several key tasks, e.g., nearest-neighbor retrieval, classification, or visualization. Data in such regimes typically exhibits multiple modalities, such as acoustic and visual content of a video, or audio clips, web documents and art work describing musical artists. Integrating such heterogeneous data to form a holistic similarity space is therefore a key challenge to be overcome in many real-world applications.

We present a novel multiple kernel learning (MKL) technique for integrating heterogeneous data into a single, unified similarity space. Instead of finding a weighted linear combination of base kernels, as in the original MKL formulation, we learn a concatenation of linear projections, where each projection extracts the relevant information from a base kernel's feature space. This new formulation results in a more flexible model than previous methods, that can adapt to the case where the discriminative power of a kernel varies over the data set or feature space.

First, we apply this framework to derive a multiple kernel nearest neighbor algorithm, and we show it allows to outperform state-of-the-art methods for object localization on a number of standard evaluation databases. Second, in an application to music recommendation, we leverage this MKL framework to learn an optimal ensemble of kernel transformations, such that the resulting embedding conforms to human perception of music similarity.

Bio: Gert Lanckriet received a Master's degree in Electrical Engineering from the Katholieke Universiteit Leuven, Leuven, Belgium, in 2000 and the M.S. and Ph.D. degrees in Electrical Engineering and Computer Science from the University of California, Berkeley in 2001 respectively 2005. In 2005, he joined the Department of Electrical and Computer Engineering at the University of California, San Diego, where he heads the Computer Audition Laboratory. He was awarded the SIAM Optimization Prize in 2008 and is the recipient of a Hellman Fellowship and an IBM Faculty Award. His research focuses on the interplay of convex optimization, machine learning and applied statistics, with applications in computer audition and music information retrieval.

Y. Narahari
Indian Institute of Science

Design of Mechanisms for Dynamic Environments

Abstract: Success in e-business is based on the fact that offerings can be made more relevant and reliable by using historical data to rank, filter, recommend, and in general learn characteristics of users and products. When these data are held by strategic agents, the classical learning algorithms fail to elicit the data truthfully from the agents. Motivated by this, in this talk, we first provide a glimpse of some current approaches for developing truthful mechanisms with dynamic agents and learning. We next describe some of our current work in this area (which is quite preliminary at this stage). We also provide an outlook for future work and opportunities for Indo-US collaboration in this area.

Bio: Y. Narahari is currently Professor and Chair at the Department of Computer Science and Automation, Indian Institute of Science, Bangalore. The focus of his current research is to apply Game Theory and Mechanism Design to Internet and Network Economics, Social Networks, and Electronic Commerce Problems. He is the lead author of a research monograph entitled Game Theoretic Problems in Network Economics and Mechanism Design Solutions" published by Springer, London in 2009.

David C. Parkes
Harvard University

The Interplay of Machine Learning and Mechanism Design

Abstract: In the economic theory of mechanism design, the goal is to elicit private information from each of multiple agents in order to select a desirable system wide outcome, and despite agent self-interest in promoting individually beneficial outcomes. Auctions provide a canonical example, with information elicited in the form of bids, and an allocation of resources and payments defining an outcome. Indeed, one aspect of the emerging interplay between machine learning (ML) and mechanism design (MD) arises by interpreting auctions as a method for learning agent valuation functions. In addition to seeking sufficient accuracy to support optimal resource allocation, we require for incentive compatibility that prices are insensitive to the inputs of any individual agent and find an interesting connection with regularization in statistical ML. More broadly, ML can be used for de novo design, in learning payment rules with suitable incentive properties. Ideas from MD are also flowing into ML. One example considers the use of mechanisms to elicit private state, reward and transition models, in enabling coordinated exploration and exploitation in multi-agent systems despite self-interest. Another application is to supervised learning, where labeled training data is elicited from self-interested agents, each with its own objective criterion on the hypothesis learned by the mechanism. Looking ahead, a tantalizing challenge problem is to adopt incentive mechanisms for the design of robust agent architectures, for example in assigning internal rewards that promote modular intelligent systems.

Bio: David C. Parkes is Gordon McKay Professor of Computer Science in the School of Engineering and Applied Sciences at Harvard University. He was the recipient of the NSF Career Award, the Alfred P. Sloan Fellowship, the Thouron Scholarship and the Harvard University Roslyn Abramson Award for Teaching. Parkes received his Ph.D. degree in Computer and Information Science from the University of Pennsylvania in 2001, and an M.Eng. (First class) in Engineering and Computing Science from Oxford University in 1995. At Harvard, Parkes leads the EconCS group and teaches classes in artificial intelligence, optimization, and topics at the intersection between computer science and economics. Parkes has served as Program Chair of ACM EC'07 and AAMAS'08 and General Chair of ACM EC'10, served on the editorial board of Journal of Artificial Intelligence Research, and currently serves as Editor of Games and Economic Behavior and on the boards of Journal of Autonomous Agents and Multi-agent Systems and INFORMS Journal of Computing. His research interests include computational mechanism design, electronic commerce, stochastic optimization, preference elicitation, market design, bounded rationality, computational social choice, networks and incentives, multi-agent systems, crowd-sourcing and social computing.

B. Ravindran
Indian Institute of Technology, Madras

Finding Approximate Symmetries of Markov Decision Processes

Kameshwaran Sampath
IBM Research India

Two-sided Matching Mechanisms for Project Fulfillment

Abstract: Workforce of a IT service organization consists of varied and highly skilled practitioners, who are assigned to specific projects with matching requirements. Fulfillment process of assigning practitioners to projects is a daily activity, that should take into account individual and organization level objectives and constraints. A practitioner would prefer to be assigned to a project that matches her skill sets and future aspirations. Project managers prefer practitioners with matching skills and attributes for higher productivity. The organization has to maintain an optimal/allowable bench mix (unassigned practitioners), higher fulfillment rate, and overall higher productivity. In this talk, we review various two-sided matching mechanisms for practitioner-project fulfillment.

Bio: Kameshwaran is a Researcher with Analytics and Optimization group in IBM India Research Laboratory, Bangalore. Prior to joining IBM Research he held similar positions at the The Logistics Insitute - Asia Pacific (NUS, Singapore), INRIA Grand Est (France) and the Indian School of Business (Hyderabad). Kamesh obtained his Ph.D. in Computer Science from IISc, Bangalore in 2004 and his research interests are in Mathematical Programming, Game Theory, and Random Graphs.

Devavrat Shah
Massachusetts Institute of Technology

Message Passing Networks: Inference, Optimization and Games

Abstract: Simple, distributed and iterative algorithms, popularly known as message-passing, have emerged as an architecture of choice for a variety of engineered networks and serve as canonical behavioral model for natural networks. Their effectiveness lies in their simplicity. In this talk, I will try to argue in favor of such algorithms by discussing examples from statistical inference, optimization and games.

In the first part, I will discuss strengths and limitation of the popular message passing heuristic called belief propagation (BP) for inference and optimization. BP arose as distributed, dynamic programming based approximation for tree-like graphs. However, it seems to work quite well empirically even when graphical models are far from tree-like. I will attempt to explain this unexpected behavior by drawing connection between BP, Linear Programing and continuous optimization.

In the second part, I will discuss a class of message-passing algorithms that have been thought of as behavioral model of agents/humans in "networks''. I will use "mixing time" of appropriate Markov chain as a metric to refute this as a reasonable model and propose an alternative model by introducing notion of 'herding'.

Bio: Devavrat Shah is currently a Jamieson career development associate professor with the department of electrical engineering and computer science, MIT. He is a member of the Laboratory for Information and Decision Systems (LIDS). His research focus is on theory of large complex networks which includes network algorithms, stochastic networks, network information theory and large scale statistical inference. He was co-awarded the best paper awards at the IEEE INFOCOM '04, ACM SIGMETRICS/Performance '06; and supervised best student paper awards at Neural Information Processing Systems '08 and ACM SIGMETRICS/Performance '09. He received 2005 George B. Dantzig best disseration award from the INFORMS. He received the first ACM SIGMETRICS Rising Star Award 2008 for his work on network scheduling algorithms. He was recently awarded the 2010 Erlang Prize from INFORMS which is given to a young researcher for outstanding contributions to applied probability. He is currently an associate editor of Operations Research.

Poster Session

There will be an opportunity for a selected number of students, postdocs, and young faculty (from India) to present posters on their research to symposium participants. To apply, please submit a one-page abstract on your research and a current CV (as PDF documents) to shivani@csa.iisc.ernet.in by October 18 2010. Decision notifications will be sent by October 22 2010.

Accepted Posters:

  • Rama B., Indian Institute of Science
  • Sahely Bhadra, Indian Institute of Science
  • Anunay Biswas, Indian Institute of Technology, Madras
  • Dileep A. D., Indian Institute of Technology, Madras
  • Vikas Garg, IBM Research India
  • Sujit Gujar, Indian Institute of Science
  • Sandeep Kumar, Indian Institute of Technology, Madras
  • Achintya Kundu, Indian Institute of Science
  • Naresh Manwani, Indian Institute of Science
  • Ruta Mehta, Indian Institute of Technology, Bombay
  • Adway Mitra, Indian Institute of Science
  • Vinod Nair, Yahoo! Labs Bangalore
  • Ramasuri Naranayam, Indian Institute of Science
  • Yamuna Prasad, Indian Institute of Technology, Delhi
  • Arun Rajkumar, Indian Institute of Science
  • Raman Sankaran, Indian Institute of Science
  • Veena T., Indian Institute of Technology, Madras
  • Neeraja Yadwadkar, NetApp
Poster Guidelines:
We recommend a poster size of up to 36 x 48". If your poster deviates significantly from these guidelines, please contact us.

Travel Awards

There are a limited number of travel awards available for students, postdocs, and young faculty from outside Bangalore (within India) who are interested in presenting posters on their research at this symposium. To apply, please submit a one-page abstract on your research and a current CV (as PDF documents) to shivani@csa.iisc.ernet.in. Applications must be received by October 18 2010. Awardees will be notified by October 22 2010.

Visitor Information

Map of Bangalore with symposium-related landmarks marked:


Map of IISc with symposium-related landmarks marked:


For tourism-related information, see here.

There is also a wealth of visitor information available here.

Report

Organization

Sponsors

We gratefully acknowledge support from the Indian Institute of Science and from the Indo-US Science and Technology Forum in organizing this event.