Artificial Intelligence Seminar

Title/Speaker/Abstract/Host

In recent years, abundant DNA sequence data has led to widespread interest in computational methods for detecting sequences that are evolving faster, slower, or by different patterns of evolution than would be expected under neutral drift, and hence are likely to have evolutionarily important biological functions. These methods are providing new insights into the evolutionary dynamics that have shaped present-day genomes, and they are beginning to reveal the genetic basis of key differences between species, including some of the specific differences that differentiate humans from other mammals. In this talk, I will review established methods for detecting positive and lineage-specific selection, focusing on likelihood ratio tests based on continuous-time Markov models of nucleotide and codon substitution. In addition, I will discuss new methods for detecting lineage-specific selection, and for evaluating the statistical significance of apparent lineage-specific changes in evolutionary rate. I will also discuss a comprehensive study of positively selected protein-coding genes in mammals that my group has recently completed. The talk will be geared for an audience of computational and statistical scientists, and no background in biology is required.

Host: Thorsten Joachims

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete structure of the game. In particular, they may not be aware of moves that they and other agents can make. We show how such games can be represented; the key idea is to describe the game from the point of view of every agent at every node of the game tree. We provide a generalization of Nash equilibrium and show that every game with awareness has a generalized Nash equilibrium. Finally, we extend these results to games with awareness of unawareness, where a player i may be aware that a player j can make moves that i is not aware of and to subjective games, where payers may have no common knowledge regarding the actual game.

This is joint work with Leandro Rego.

Bayesian Networks provide a compact, intuitive description of the dependency structure of a domain by using a directed acyclic graph to encode statistical dependencies between variables. When learned from observational data, this dependency graph can yield valuable insights into the problem at hand.

Until now, Bayesian Network structure learning research has focused on learning the dependency graph for one data set in isolation. In many situations, however, data is available for multiple related data sets. In these cases, it may be possible to learn more accurate dependency graphs by transferring information between data sets.

In this talk I present a score and search algorithm for jointly learning the structure of multiple related Bayesian Networks. The algorithm relies on defining a scoring function over sets of structures (one structure for each data set) and on devising an efficient procedure for searching for a set of structures that has a high score. The proposed algorithm is able to transfer useful information between the related data sets leading to significant improvements in the quality of the learned dependency structures, especially in data scarce regimes.

Host: Rich Caruana

There is great appetite to study query logs as a rich window into human intent, but as the AOL incident shows, the privacy concerns are broad and well-founded. It is important to understand the latent user information present in query logs and the vulnerabilities of simple query log anonymization methods.

We start by studying the privacy preservation properties of a specific technique for query log anonymization: token-based hashing, where each query is tokenized, and then a secure hash function is applied to each token. We show that statistical techniques may be applied to partially compromise the anonymization, and sensitive information about users can be revealed from the reconstructed query log. We then investigate the risk of revealing user identity from queries in two different scenarios.

In the first setting, we study the application of simple classifiers to map a sequence of queries into a gender, age, and location of the user issuing the queries; based on this information, we examine how we can map the queries into a set of candidate users and how to identify a known user from a large query log. In the second setting, we examine an anonymization approach to ``bundle'' logs of multiple users together.

We investigate the risk of recovering queries from a given user by first locating the bundle for that user via vanity search, followed by an analysis of the structural and analytical vulnerabilities inside the bundles.

Joint work with Rosie Jones, Ravi Kumar, Jasmine Novak, and Andrew Tomkins

Host: Lillian Lee

In recent years, the Cornell Laboratory of Ornithology has collected millions of bird observations through voluntary reporting. This data is a rich source of information about bird distributions, and simple animations clearly reveal migratory behavior. Our goal is to learn quantitative migration models from these static observations.

We model migration dynamics as a population-wide Markov model where each bird is an independent sample. This leads to a family of inference problems in which many sample paths are drawn from a Markov chain and partial information is revealed to an observer who attempts to reconstruct the sample paths. I'll discuss algorithms and hardness results for several variants of this problem, focusing on the application to bird migration. Our algorithms use network flow techniques, generalizing the classical Viterbi algorithm for Hidden Markov Models.

At the end of the talk, I will discuss some ongoing work to jointly model the processes of bird migration and observation, and I will discuss possible applications of our modeling techniques to other problems.

This is joint work with Dexter Kozen and Saleh Elmohamed.

Host: John Hopcroft

Modern constraint solvers can handle problems with up to a million variables and several million constraints. This is a significant advance compared to solvers of a little over a decade ago, when a few hundred variables was practical limit. A recent explanation for the good scaling properties of state-of-the-art constraint solvers is that in many real-world combinatorial problems the true combinatorics is captured by a relatively small set of critical variables. We call such variables the backdoor variables. I will discuss a series of new insights into backdoor variables sets that reveal important structural properties of real-world combinatorial problems and the underlying constraint networks. In particular, I will cover different variants of the notion of backdoor sets, the computational complexity of identifying minimal such sets and their respective practical relevance.

Joint work with Carla Gomes and Ashish Sabharwal

Host: Carla Gomes

Local aspects of Web search — associating Web content and queries with geography — is a topic of growing interest.  However, the underlying question of how spatial variation is manifested in search queries is still not well understood.  Here we develop a probabilistic framework for quantifying such spatial variation; on complete Yahoo! query logs, we find that our model is able to localize large classes of queries to within a few miles of their natural centers based only on the distribution of activity for the query. Our model provides not only an estimate of a query's geographic center, but also a measure of its spatial dispersion, indicating whether it has highly local interest or broader regional or national appeal. We also show how variations on our model can track geographically shifting topics over time, annotate a map with each location's "distinctive queries," and delineate the "spheres of influence" for competing queries in the same general domain.

Joint work with Jon Kleinberg, Ravi Kumar, and Jasmine Novak

Host: Jon Kleinberg

Abstract: Many complex domains offer limited information about their exact state and the way actions affect them. There, autonomous agents need to make decisions at the same time that they learn action models and track the state of the domain. This combined problem can be represented within the framework of reinforcement learning in POMDPs, and is known to be computationally difficult.

In this presentation I will describe a new framework for such decision making, learning, and tracking. This framework applies results that we achieved about updating logical formulas (belief states) after deterministic actions. It includes algorithms that represent and update the set of possible action models and world states compactly and tractably. It makes a decision with this set, and updates the set after taking the chosen action. Most importantly, and somewhat surprisingly, the number of actions that our framework takes to achieve a goal is bounded polynomially by the length of an optimal plan in a fully observable, fully known domain, under lax conditions.

Finally, our framework leads to a new stochastic-filtering approach that has better accuracy than previous techniques.

* Joint work with Allen Chang, Hannaneh Hajishirzi, Stuart Russell, Dafna Shahaf, and Afsaneh Shirazi (IJCAI'03,IJCAI'05,AAAI'06,ICAPS'06,IJCAI'07,AAAI'07).

Bio: Eyal Amir is an Assistant Professor of Computer Science at the University of Illinois at Urbana-Champaign (UIUC) since January 2004. His research includes reasoning, learning, and decision making with logical and probabilistic knowledge, dynamic systems, and commonsense reasoning. Before UIUC he was a postdoctoral researcher at UC Berkeley (2001-2003) with Stuart Russell, and did his Ph.D. on logical reasoning in AI with John McCarthy. He received B.Sc. and M.Sc. degrees in mathematics and computer science from Bar-Ilan University, Israel in 1992 and 1994, respectively. Eyal is a Fellow of the Center for Advanced Studies and of the Beckman Institute at UIUC (2007-2008), was chosen by IEEE as one of the "10 to watch in AI" (2006), received the NSF CAREER award (2006), and awarded the Arthur L. Samuel award for best Computer Science Ph.D. thesis (2001-2002) at Stanford University.

Host: Joe Halpern

Abstract:  The field of machine translation (MT) has made major strides in recent years. An important enabling factor has been the adoption of automatic evaluation metrics to guide researchers in making improvements to their systems. Research in automatic evaluation metrics faces two major challenges. One is to achieve higher agreement with human judgments when evaluating MT outputs at the sentence-level. Another is to minimize the reliance on expensive, human-developed resources such as reference sentences. In this talk, I present a regression-based approach to metric development. Our experiments suggest that by combining a wide range of features, the resulting metric has higher correlations with human judgments. Moreover, we show that the features do not have to be extracted from comparisons with human produced references. Using weaker indicators of fluency and adequacy, our learned metrics rival standard reference-based metrics in terms of correlations with human judgments on new test instances.

Bio: Rebecca Hwa is an Assistant Professor in the Department of Computer Science at the University of Pittsburgh. Her recent research focus is on multilingual processing and machine translation. Before joining Pitt, she was a postdoc at University of Maryland. She received her PhD from Harvard University and her B.S. from UCLA.

Host: Lillian Lee

Affective computing systems face challenges in relating objective measures with subjective human experiences. Many systems have either focused on objective measures as a substitute for subjective experience (e.g. skin conductance as a direct representation of arousal) or have abandoned objective measures to focus purely on subjective experience. In this work, we explore how to negotiate the relationship between objective signals and subjective experiences by highlighting the role of human interpretation. Our approach is informed by a reflective analysis drawing on the arts and the humanities and by a participatory study examining the emergence of emotional meaning. We demonstrate the potential of our approach for interactive affective systems through a series of conceptual designs that embody these understandings.

Joint work with Steve Schwenk and Phoebe Sengers. Presented at DIS 2008.

Host: Phoebe Sengers

In many retrieval tasks, one important goal involves retrieving a diverse set of results (e.g., documents covering a wide range of topics for a search query). First of all, this reduces redundancy, effectively showing more information with the presented results. Secondly, queries are often ambiguous at some level. For example, the query "Jaguar" can refer to many different topics (such as the car or the feline). A set of documents with high topic diversity ensures that fewer users abandon the query because no results are relevant to them. Unlike existing approaches to learning retrieval functions, we present a method that explicitly trains to diversify results. In particular, we formulate the learning problem of predicting diverse subsets and derive a training method based on structural SVMs.

This is joint work with Thorsten Joachims

Host: Thorsten Joachims