Artificial Intelligence Seminar

Speaker: Yiling Chen, Harvard

Host: Eva Tardos

Title: Computation and Incentives in Social Computing

Abstract: Social computing is a broad and evolving research area that concerns harnessing human intelligence to solve computational problems. The term is sometimes taken as synonymous with a few other closely related research areas such as “human computation,” “crowdsourcing,” and “collective intelligence.” Social computing systems function via complex and dynamic interactions among people and computing technologies. As a result, understanding how to purposefully design social computing systems requires advances in at least a few interleaving directions: algorithms and computational theory, theory of incentive alignment, and understanding of human social behavior. 

In this talk, I discuss two projects that my group and collaborators have carried out along the first and third directions respectively. The first project introduces a computational framework for designing prediction markets, markets for eliciting and aggregating probabilistic information about uncertain events of interests. Achieving the goal of information elicitation and aggregation requires prediction markets to have appropriate economic properties, which however pose a significant computational challenge on operating these markets. We propose an online convex optimization framework for designing prediction markets with desirable economic properties and for reasoning about the tractability of the designed markets. In the second project, we conduct behavioral experiments to evaluate the performance of a classical peer prediction mechanism in practice. Peer prediction mechanisms have an elegant game-theoretic equilibrium where participants truthfully reveal their information even if there is no verification of the elicited information. This equilibrium behavior is particularly desirable in social computing for harnessing human knowledge. A surprising result of our experiments is that truthful equilibrium is not focal and that participants seem able to coordinate on other, more profitable equilibria in peer prediction.  

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Chenhao Tan, Cornell University

Host: Thorsten Joachims

Title: It takes two to tango: Understanding the effects of language via "natural experiments"

Abstract: More and more human behaviors can be observed online, many in the format of language. This gives us an opportunity to observe some communications "repeatedly". For example, campaigners can now try different wordings to see which works better to mobilize or impress people on social media. In this talk, I will discuss two papers published in ACL this year on how these resources can be used to open doors to important problems that were difficult to study and present our efforts in addressing them.

First, we will look at the effects of wording on message propagation through natural experiments on Twitter. While there has been extensive prior work looking into predicting popularity of social-media content, the effect of wording per se has rarely been studied since it is often confounded with the popularity of the author and the topic. In this talk, I will present natural experiments on Twitter, which take advantage of the surprising fact that there are many pairs of tweets containing the same url and written by the same user but employing different wording to control for these confounding factors. Given such pairs, we ask: which version attracts more retweets? This turns out to be a more difficult task than predicting popular topics. Still, humans can answer this question better than chance (but far from perfectly). I will explain the features that can predict which tweet attracts more retweets. Using these features outperforms an average human and a strong competing method trained on non-controlled data.

Second, we will explore the problem of statement stregnth. The strength with which a statement is made can have a significant impact on the audience. For example, international relations can be strained by how the media in one country describes an event in another; and papers can be rejected because they overstate or understate their findings. As a first step to approach the problem, we introduce a corpus of sentence-level revisions from academic writing.

This is joint work with Lillian Lee and Bo Pang.

“The AI-Seminar is sponsored by Yahoo!”

Speaker:

Host:

Bio:

Title:

Abstract:

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Peter Frazier, Cornell University

Host: Thorsten Joachims

Title: Parallel Bayesian Global Optimization of Expensive Functions, for Metrics Optimization at Yelp

Abstract: We consider parallel derivative-free global optimization of expensive-to-evaluate functions. We present a new decision-theoretic algorithm for this problem, which places a Bayesian prior distribution on the objective function, and chooses the set of points to evaluate next that provide the largest value of the information.  This decision-theoretic approach was previously proposed by Ginsbourger and co-authors in 2008, but was deemed too difficult to actually implement in practice. Using stochastic approximation, we provide a practical algorithm implementing this approach, and demonstrate that it provides a significant speedup over the single-threaded expected improvement algorithm. We then describe how Yelp, the online business review company, uses this algorithm to optimize the content that their users see.  An open source implementation, called the Metrics Optimization Engine (MOE), was co-developed with engineers at Yelp and is available at github.com/yelp/MOE.

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Giles Hooker & Lucas Mentch, Cornell University

Host: Thorsten Joachims

Title: Subsample Trees and CLT's: Inference and Machine Learning

Abstract: This talk proposes a first method for performing formalized statistical inference using ensemble learners. Diagnostics such as variable importance scores and partial dependence plots have proved to be highly popular tools for understanding the output of machine learning processes.  However, until now there has been no computationally-tractable means of assessing the statistical precision of these predictors.

We review the development of some of these tools, all of which can be expressed in terms of the predictions made at given points in the input space. We then go on to show that for ensemble methods created using subsamples of the training data (random forests, for example), it is possible to develop a central limit theorem for the distribution of these predicted values.  This result allows us to construct formalized confidence intervals, tests for variable importance, and tests of additivity, providing a quantification of the statistical uncertainty in diagnostic tools. We illustrate our methods with results from a collaboration with Cornell's Laboratory of Ornithology.

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Stefano Ermon, Cornell University

Host: Carla Gomes

Title: Decision Making and Inference under Limited Information and High Dimensionality

Abstract: Statistical inference in high-dimensional probabilistic models (i.e., with many variables) is one of the central problems of statistical machine learning and stochastic decision making. To date, only a handful of distinct methods have been developed, most notably (MCMC) sampling, decomposition, and variational methods. In this talk, I will introduce a fundamentally new approach based on random projections and combinatorial optimization. Our approach provides provable guarantees on accuracy, and outperforms traditional methods in a range of domains, in particular those involving combinations of probabilistic and causal dependencies (such as those coming from physical laws) among the variables. This allows for a tighter integration between inductive and deductive reasoning, and offers a range of new modeling opportunities. As an example, I will discuss an application in the emerging field of Computational Sustainability aimed at discovering new fuel-cell materials where we greatly improved the quality of the results by incorporating prior background knowledge of the physics of the system into the model.

“The AI-Seminar is sponsored by Yahoo!”

Speaker:

Host:

Bio:

Title:

Abstract:

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Daniel Romero, University of Michigan

Host: Jon Kleinberg

Title: Temporal Dynamics of Communication Networks: Trade-Offs, External Shocks, and Efficiency.

Abstract: Communication plays a crucial role in key processes of collaborative environments such as coordination, decision-making, and information sharing. Through the analysis of fine-grained data of interactions in teams, we identify features of the composition of the team and external events that are related to changes in the team’s communication structure. Furthermore, we examine how these shifts in communication structure relate to behavioral patterns and to the effectiveness of the group’s performance.

We consider two distinct collaborative settings. First, we analyze the communication structure of a hedge fund through the social network generated by the exchange of instant messages. We find that when large price movements in the stock market occur, the communication network tends to “compress” --- exhibiting high mean clustering coefficient, stronger ties, and less communication with people external to the hedge fund. Furthermore, we find that the structure of the networks is predictive of emotional words and cognitive processes in the instant messages as well as the firm’s performance in trading.

Second, we analyze communication among members of two decentralized on-line collaboration settings --- Wikipedia and GitHub. We consider the trade-offs inherent communication, balancing the benefits to communicate with the cost in effort that could be spent directly working on the project. We show that, in aggregate, high performing projects exhibit larger levels of communication than typical projects. We also develop a theoretical model for the cost-benefit trade-off in communication. The model shows how communication should increase as projects become more “crowded” --- with relatively small size but many participants. 

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Ross Knepper, Cornell University

Host: Thorsten Joachims

Title: "Planning Complex Multi-Robot Assembly"

Abstract: In factory settings, robots have long participated in complex assembly processes, but the sequence of operations has always been planned out by a human process engineer.  As factories become more agile, robots must assume a greater extend of autonomy in order to support rapid reconfiguration.  Robots must autonomously reason about complex assembly sequences and multi-robot collaboration.  In this talk, I describe several approaches to symbolic programming applied to the problem of IKEA furniture assembly.  I discuss the strengths and weaknesses of STRIPS-style planning and AND/OR graphs and then conclude with a set of open problems.

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Filip Radinski, Microsoft

Host: Thorsten Joachims

Title: Optimized Interleaving for Retrieval Evaluation

Abstract: Interleaving is an online evaluation technique for comparing the relative quality of information retrieval functions by combining their result lists and tracking clicks. A sequence of such algorithms have been proposed, each being shown to address problems in earlier algorithms. In this talk, I will formalize and generalize this process, while introducing a formal model: After identifying a set of desirable properties for interleaving, I will show that an interleaving algorithm can be obtained as the solution to an optimization problem within those constraints. This approach makes explicit the parameters of the algorithm, as well as assumptions about user behavior. Further, this approach leads to an unbiased and more efficient interleaving algorithm than any previous approach, as I will show a novel log-based analysis of user search behavior.
This is joint work with Nick Craswell.

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Anshumali Shrivastava

Host: Thorsten Joachims

Title: “An Excursion in Probabilistic Hashing Techniques for Big Data”

Abstract: Large scale machine learning and data mining applications are constantly dealing with datasets at TB scale and the anticipation is that soon it will reach PB level. At this scale, simple data mining operations such as search, learning, and clustering become challenging.
In this talk, I will introduce probabilistic hashing techniques for efficient search and learning. I will show how the same hashing scheme originally meant for sub-linear search also leads to efficient kernel learning.  Later I will talk about some of my recent works on leveraging the hashing framework, which will include a faster variant of minwise hashing and an asymmetric extension for solving a new class of search problems in sub-linear time which were impossible before.  I will demonstrate the utility of the above techniques on various real applications including search, learning, record linkage and collaborative filtering.     

“The AI-Seminar is sponsored by Yahoo!”

Speaker: Ozan Irsoy, Cornell University

Host: Thorsten Joachims

Title: Deep Sequential and Structural Models of Compositionality in Natural Language

Abstract: Compositional models of language deal with how meaning of larger units (e.g. phrases or sentences) can be generated from smaller parts (e.g. words). I will discuss how sequential and structural views of compositionality can be realized with deep neural network based models and apply them to opinion mining and sentiment detection tasks.

In the first part of the talk, I will show how deep recurrent neural networks can be applied to the task of opinion expression extraction. Recurrent nets outperform preexisting CRF-based approaches, without having access to manually curated opinion lexicons or preprocessing components such as parsers, and achieve new state-of-the-art.

In the second part, I will introduce the deep recursive neural network which is constructed by stacking multiple recursive layers. When applied to the task of fine-grained sentiment analysis, deep recursive nets outperform their shallow counterparts, as well as previous baselines. They capture different notions of similarity and different aspects of compositionality across multiple recursive layers.

This is joint work with Claire Cardie, based on EMNLP14 and NIPS14 papers.

“The AI-Seminar is sponsored by Yahoo!”

NO AI SEMINAR- ACSU LUNCH

Speaker: Yisong Yue, Caltech

Host: Thorsten Joachims

Title: Balancing the Explore/Exploit Tradeoff in Interactive Structured Prediction

Abstract:Many prediction domains, ranging from content recommendation in a digital system to motion planning in a physical system, require making structured predictions. Broadly speaking, structured prediction refers to any type of prediction performed jointly over multiple input instances, and has been a topic of active research in the machine learning community over the past 10-15 years. However, what has been less studied is how to model structured prediction problems for an interactive system. For example, a recommender system necessarily interacts with users when recommending content, and can learn from the subsequent user feedback on those recommendations. In general, each "prediction" is an interaction where the system not only predicts a structured action to perform, but also receives feedback (i.e., training data) corresponding to the utility of that action.

In this talk, I will describe methods for balancing the tradeoff between exploration (collecting informative feedback) versus exploitation (maximizing system utility) when making structured predictions in an interactive environment. Exploitation corresponds to the standard prediction goal in non-interactive settings, where one predicts the best possible action given the current model. Exploration refers to taking actions that maximize the informativeness of the subsequent feedback, so that one can exploit more reliably in future interactions. I will show how to model and optimize for this tradeoff in two settings: diversified news recommendation (where the feedback comes from users) and adaptive vehicle routing (where the feedback comes from measuring congestion).

This is joint work with Carlos Guestrin, Sue Ann Hong, Ramayya Krishnan and Siyuan Liu.

“The AI-Seminar is sponsored by Yahoo!”