NESCAI 2010: The Fourth North East Student Colloquium on Artificial Intelligence

Talks

Session A1: Multi-Agent Systems and Game Theory
Session A2: Information Extraction
Session B1: Reinforcement Learning and Robotics
Session B2: Natural Language Processing
Session C1: Applied Artificial Intelligence
Session C2: Structured and Relational Learning
Session D1: Planning and Information Retrieval
Session D2: Machine Learning

Session A1: Multi-Agent Systems and Game Theory

PC Member In-charge: Haoqi Zhang
10:30am-12:00pm, Saturday April 17
Room 101, Campus Center
  1. Multi-Agent Learning with Policy Prediction.
    Chongjie Zhang (UMass Amherst), Victor Lesser (UMass Amherst)
    Due to the non-stationary environment, learning in multi-agent systems is a challenging problem. This paper first introduces a new gradient-based algorithm by using policy prediction in basic gradient ascent. We prove that this modification results in a stronger notion of convergence than basic gradient ascent, that is, strategies converge to a Nash equilibrium within a restricted class of iterated games. Motivated by this modification, we then propose a new practical multi-agent reinforcement learning (MARL) algorithm exploiting approximate policy prediction. Empirical results show that it converges faster and in a wider variety of situations than state-of-the-art MARL algorithms.

  2. Hidden Market Design.
    Sven Seuken (Harvard), David C. Parkes (Harvard), Kamal Jain (Microsoft)
    The next decade will see an abundance of new intelligent systems, many of which will be market-based. Soon, users will interact with many new markets, perhaps without even knowing it: when driving their car, when listening to a song, when backing up their files, or when surfing the web. We argue that these new systems can only be successful if a new approach is chosen towards designing them. In particular, the complexities of the market must be hidden and the interaction for the user must be seamless. In this paper we introduce the general problem of "Hidden Market Design." We show that the intersection of user interface design and market design is of particular importance for the design of these markets. A key challenge is to determine how hiding certain market aspects from the user impacts the market design space. To illustrate hidden market design, we give a series of potential applications. We hope that the problem of hidden market design will inspire other researchers and lead to new research in this direction, paving the way for more successful market-based systems in the future.

  3. An Approach to Bidding in Ad Auctions.
    Jordan Berg (Brown), Amy Greenwald (Brown), Victor Naroditskiy (Univ of Southampton), Eric Sodomka (Brown)
    The Trading Agent Competition for Ad Auctions (TAC AA) is a simulated sponsored search domain that tries to capture some of the complex dynamics of bidding in sponsored search auctions. In this paper, we present a suite of agents for bidding in a stylized version of the ad auctions problem, and extend these algorithms for bidding in the more realistic TAC AA domain.
    We decompose the agent’s problem into a modeling sub-problem, where we estimate values such as click probability and cost per click, and an optimization sub-problem, where we determine what to bid given these estimates. Our optimization algorithms, the focus of this paper, are composed of rulebased algorithms, which can make decisions with minimal information, and greedy multiple choice knapsack algorithms, which are capable of finding better solutions than rulebased methods but require more accurate models.
    We evaluate agent performance in the game-theoretic TAC AA domain, as well as through a more controlled testing framework that decouples the modeling sub-problem from the optimization sub-problem. We use this testing framework to determine which optimization algorithm is most suitable for an advertiser with a given amount of model error, and which model improvements will lead to the greatest gain in performance.

Session A2: Information Extraction

PC Member In-charge: Kuzman Ganchev
10:30am-12:00pm, Saturday April 17
Room 163C, Campus Center
  1. Wikispeedia: An Online Game for Inferring Semantic Distances between Concepts.
    Robert West (McGill), Joelle Pineau (McGill), Diona Precup (McGill)
    Computing the semantic distance between real-world concepts is crucial for many intelligent applications. We present a novel method that leverages data from 'Wikispeedia', an online game played on Wikipedia; players have to reach an article from another, unrelated article, only by clicking links in the articles encountered. In order to automatically infer semantic distances between everyday concepts, our method effectively extracts the common sense displayed by humans during play, and is thus more desirable, from a cognitive point of view, than purely corpus-based methods. We show that our method significantly outperforms Latent Semantic Analysis in a psychometric evaluation of the quality of learned semantic distances.

  2. Learning Prediction Suffix Trees with Winnow.
    Nikos Karampatziakis (Cornell), Dexter Kozen (Cornell)
    Prediction suffix trees (PSTs) are a popular tool for modeling sequences and have been successfully applied in many domains such as compression and language modeling. In this work we adapt the well studied Winnow algorithm to the task of learning PSTs. The proposed algorithm automatically grows the tree, so that it provably remains competitive with any fixed PST determined in hindsight. At the same time we prove that the depth of the tree grows only logarithmically with the number of mistakes made by the algorithm. Finally, we empirically demonstrate its effectiveness in several different tasks.

  3. Title not available.
    Sean Gerrish (Princeton), David Blei (Princeton)
    Since the paper is under blind review at another conference, the title and the abstract are not available on the NESCAI website.

Session B1: Reinforcement Learning and Robotics

PC Member In-charge: George Konidaris
1:30pm-3:00pm, Saturday April 17
Room 101, Campus Center
  1. Optimal Policy Switching Algorithms for Reinforcement Learning.
    Gheorghe Comanici (McGill), Doina Precup (McGill)
    We address the problem of single-agent, autonomous sequential decision making. We assume that some controllers or behavior policies are given as prior knowledge, and the task of the agent is to learn how to switch between these policies. We formulate the problem using the framework of reinforcement learning and options (Sutton, Precup & Singh, 1999; Precup, 2000). We derive gradient-based algorithms for learning the termination conditions of options, with the goal of optimizing the expected long-term return. The termination condition is based on the accumulation of state features towards saturation points. We incorporate the proposed approach into policy-gradient methods with linear function approximation.

  2. Robust Policy Computation in Reward-uncertain MDPs using Nondominated Policies.
    Kevin Regan (Univ of Toronto), Craig Boutilier (Univ of Toronto)
    The precise specification of reward functions for Markov decision processes (MDPs) is often extremely difficult, motivating research into both reward elicitation and the robust solution of MDPs with imprecisely specified reward (IRMDPs). We develop new techniques for the robust optimization of IRMDPs, using the minimax regret decision criterion, that exploit the set of nondominated policies, i.e., policies that are optimal for some instantiation of the imprecise reward function. Drawing parallels to POMDP value functions, we devise a Witness-style algorithm for identifying nondominated policies. We also examine several new algorithms for computing minimax regret using the nondominated set, and examine both practically and theoretically the impact of approximating this set. Our results suggest that a small subset of the nondominated set can greatly speed up computation, yet yield very tight approximations to minimax regret.

  3. Graphical State-Space Programmability as a Natural Interface for Robotic Control.
    Anqi Xu (McGill), Junaed Sattar (McGill), Gregory Dudek (McGill), Gabriel Charette (McGill)
    We present an interface for controlling mobile robots that combines aspects of graphical trajectory specification and state-based programming. This work is motivated by common tasks executed by our underwater vehicles, although we illustrate a mode of interaction that is applicable to mobile robotics in general. The key aspect of our approach is to provide an intuitive linkage between the graphical visualization of regions of interest in the environment, and activities relevant to these regions. In addition to introducing this novel programming paradigm, we also describe the associated system architecture developed on-board our amphibious robot. We then present a user interaction study that illustrates the benefits in usability of our graphical interface, compared to conventionally established programming techniques.

Session B2: Natural Language Processing

PC Member In-charge: David Mimno
1:30pm-3:00pm, Saturday April 17
Room 163C, Campus Center
  1. Title not available.
    Joao Graca (IST Portugal), Kuzman Ganchev (UPenn), Ben Taskar (UPenn), Fernando Pereira (Google), Luisa Coheur (IST Portugal)
    Since the paper is under blind review at another conference, the title and the abstract are not available on the NESCAI website.

  2. Title not available.
    Elif Yamangil (Harvard)
    Since the paper is under blind review at another conference, the title and the abstract are not available on the NESCAI website.

  3. Title not available.
    Jennifer Gillenwater (UPenn), Kuzman Ganchev (UPenn), Joao Graca (IST Portugal), Ben Taskar (UPenn), Fernando Pereira (Google)
    Since the paper is under blind review at another conference, the title and the abstract are not available on the NESCAI website.

Session C1: Applied Artificial Intelligence

PC Member In-charge: Christian Muise
3:30pm-5:00pm, Saturday April 17
Room 101, Campus Center
  1. Activity recognition using the velocity histories of tracked keypoints.
    Ross Messing (Univ of Rochester), Chris Pal (Ecole Polytechnique de Montreal), Henry Kautz (Univ of Rochester)
    We present an activity recognition feature inspired by human psychophysical performance. This feature is based on the velocity history of tracked keypoints. We present a generative mixture model for video sequences using this feature, and show that it performs comparably to local spatio-temporal features on the KTH activity recognition dataset. In addition, we contribute a new activity recognition dataset, focusing on activities of daily living, with high resolution video sequences of complex actions. We demonstrate the superiority of our velocity history feature on high resolution video sequences of complicated activities. Further, we show how the velocity history feature can be extended, both with a more sophisticated latent velocity model, and by combining the velocity history feature with other useful information, like appearance, position, and high level semantic information. Our approach performs comparably to established and state of the art methods on the KTH dataset, and significantly outperforms all other methods on our challenging new dataset.

  2. Title not available.
    Jordan Frank (McGill), Shie Mannor (McGill), Doina Precup (McGill)
    Since the paper is under blind review at another conference, the title and the abstract are not available on the NESCAI website.

  3. Feature Ranking for Emotional Models used in Classroom Based Intelligent Tutoring Systems.
    David G. Cooper (UMass Amherst), Kasia Muldner (Arizona State Univ), Ivon Arroyo (UMass Amherst), Beverly Park Woolf (UMass Amherst), Winslow Burleson (Arizona State Univ)
    Recent progress has been made in using sensors with Intelligent Tutoring Systems in classrooms in order to predict the affective state of students users. If tutors were able to interpret sensor data with new students based on past experience, rather than having to be individually trained, then tutor developers could evaluate various methods of adapting to each student's affective state using consistent predictions. Classifiers for emotion in Wayang Outpost have predicted student emotions with an accuracy between 78% and 87%. However, it is still unclear which sensors are best, and the educational technology community needs to know this to develop better than baseline classifiers, e.g. ones that use only frequency of emotional occurrence to predict affective state. This paper suggests a method for comparing classifiers using different sensors as well as a method for validating the classifiers on a novel population. This involves training classifiers on data collected in the Fall of 2008 and testing them on data collected in the Spring of 2009. Results of the comparison show that the classifiers for some affective states are significantly better than the baseline, and a validation study found that not all classifier rankings generalize to new settings. The analysis suggests that though there is some benefit gained from simple linear classifiers, more advanced methods are needed for better results.

Session C2: Structured and Relational Learning

PC Member In-charge: Yuri Malitsky
3:30pm-5:00pm, Saturday April 17
Room 163C, Campus Center
  1. Structured Prediction Cascades.
    David Weiss (UPenn), Ben Taskar (UPenn)
    Structured prediction tasks are limited by a fundamental tradeoff between the need for model complexity to increase predictive power and the limited computational resources for inference in exponentially-sized output spaces such models require. We formulate and develop structured prediction cascades: a cascade of increasingly complex models that progressively filter the space of possible outputs. We represent an exponentially large set of filtered outputs using max marginals and propose novel convex loss functions that balance filtering error with filtering efficiency. We provide generalization bounds for these loss functions and evaluate our approach on a sequence learning NLP task. We find an average increase of efficiency of ×112 compared to unfiltered baseline with a 500-fold reduction in the size of the output spaces space, and we also significantly outperform standard heuristic filtering baselines.

  2. HOP-MAP: Efficient Message Passing with High Order Potentials.
    Daniel Tarlow (Univ of Toronto), Inmar Givoni (Univ of Toronto), Richard Zemel (Univ of Toronto)
    There is a growing interest in building probabilistic models with high order potentials (HOPs), or interactions, among discrete variables. Message passing inference in such models generally takes time exponential in the size of the interaction, but in some cases maximum a posteriori (MAP) inference can be carried out efficiently. In this work, we define several classes of tractable HOPs, including some existing examples and introducing several novel ones, and we show how these potentials can be incorporated naturally into several message passing algorithms. We demonstrate the breadth and utility of this general framework for constructing models and performing MAP inference by showing how it can be used to formulate familiar and new high order models.

  3. Learning causal models of relational domains.
    Marc Maier (UMass Amherst), Brian Taylor (UMass Amherst), Huseyin Oktay (UMass Amherst), David Jensen (UMass Amherst)
    Methods for discovering causal knowledge from observational data have been a persistent topic of AI research for several decades. Essentially all of this work focuses on knowledge representations for propositional domains. In this paper, we present several key algorithmic and theoretical innovations that extend causal discovery to relational domains. We provide strong evidence that effective learning of causal models is enhanced by relational representations. We present an algorithm, relational PC, that learns causal dependencies in a state-of-the-art relational representation, and we identify the key representational and algorithmic innovations that make the algorithm possible. Finally, we prove the algorithm's theoretical correctness and demonstrate its effectiveness on synthetic and real data sets.

Session D1: Planning and Information Retrieval

PC Member In-charge: Alexandra Goultiaeva
9:30am-11:00am, Sunday April 18
Room 101, Campus Center
  1. Reasoning about Plan Correctness for One-Dimensional Problems.
    Yuxiao Hu (Univ of Toronto), Hector Levesque (Univ of Toronto)
    A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is non-trivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call one-dimensional (1d), and prove a correctness result that 1d problems can be verified by finite means. We show that this theoretical result leads to a practical algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.

  2. Passage Reranking for Question Answering Using Syntactic Structures and Answer Types.
    Elif Aktolga (UMass Amherst), James Allan (UMass Amherst), David A. Smith (UMass Amherst)
    Passage Retrieval is a crucial step in question answering systems, one that has been well researched in the past. Due to the vocabulary mismatch problem and independence assumption of bag-of-words retrieval models, correct passages are often ranked lower than other incorrect passages in the retrieved list. Whereas in previous work, passages are reranked only on the basis of syntactic structures of questions and answers, our method achieves a better ranking by aligning the syntactic structures based on the question's answer type and detected named entities in the candidate passage. We compare our technique with strong retrieval and reranking baselines. Experimental results using the TREC QA 1999-2003 datasets show that our method significantly outperforms the baselines over all ranks in terms of the MRR measure.

  3. Forum Search Using Thread Structures.
    Jangwon Seo (UMass Amherst), W. Bruce Croft (UMass Amherst), David A. Smith (UMass Amherst)
    Online forums are valuable information sources where knowledge is accumulated by interactions between people. Search services provided by online forum sites are often, however, quite poor. To address this, we investigate retrieval techniques that exploit the hierarchical thread structures in forum sites. Since these structures are sometimes not explicit or accurately annotated, we introduce structure discovery techniques that use a variety of features to model relations between posts. We then make use of thread structures in retrieval experiments with two real online forums. Our results show that using thread structures that have been accurately annotated can lead to significant improvements in retrieval performance compared to strong baselines.

Session D2: Machine Learning

PC Member In-charge: Rob Hall
9:30am-11:00am, Sunday April 18
Room 163C, Campus Center
  1. Title not available.
    Jonathan Huang (CMU), Carlos Guestrin (CMU)
    Since the paper is under blind review at another conference, the title and the abstract are not available on the NESCAI website.

  2. A linear-time solver for nonsmooth nonconvex mathematical programs: Application to large-scale drug design.
    Charles Bergeron (RPI), Gregory Moore (RPI), Jed Zaretzki (RPI), Tao-wei Huang (RPI), Curt M. Breneman (RPI), Kristin P. Bennett (RPI)
    Inspired by the latest linear-time subgradient-based methods for support vector machines, we optimize multiple instance learning models formulated as nonsmooth nonconvex mathematical problems using a nonconvex bundle method. Computational results show this method is linearly scalable while improving generalization accuracy. This permit linear and kernel modeling on increasingly large computational chemistry datasets.

  3. Adaptive Regularization of Weight Vectors.
    Koby Crammer (The Technion), Mark Dredze (JHU), Alex Kulesza (UPenn)
    We present AROW, a new online learning algorithm that combines several useful properties: large margin training, confidence weighting, and the capacity to handle non-separable data. AROW performs adaptive regularization of the prediction function upon seeing each new instance, allowing it to perform especially well in the presence of label noise. We derive a mistake bound, similar in form to the second order perceptron bound, that does not assume separability. We also relate our algorithm to recent confidence-weighted online learning techniques and show empirically that AROW achieves state-of-the-art performance and notable robustness in the case of non-separable data.