AAAI-13: THE TWENTY-SEVENTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE

# PROGRAM FOR TUESDAY, JULY 16TH, 2013

Days:
previous day
next day
all days
08:30-09:00 Session 9: AAAI Welcome and Awards (AAAI)
09:00-10:00 Session 10: Keynote Address: Mooney (AAAI)
 09:00 AAAI-13 Keynote Address: Grounded Language LearningSPEAKER: Raymond MooneyABSTRACT. Most approaches to semantics in computational linguistics represent meaning in terms of words or abstract symbols. Grounded-language research bases the meaning of natural language on perception and/or action in the (real or virtual) world. Machine learning has become the most effective approach to constructing natural-language systems; however, current methods require a great deal of laboriously annotated training data. Ideally, a computer would be able to acquire language like a child, by being exposed to language in the context of a relevant but ambiguous environment, thereby grounding its learning in perception and action. We will review recent research in grounded language learning and discuss future directions.
10:00-10:20Coffee Break
10:20-11:20 Session 11: IAAI Joint Invited talk: Birnbaum (AAAI)
 10:20 AAAI/IAAI Joint Invited Talk: Telling Stories at Internet ScaleSPEAKER: Larry BirnbaumABSTRACT. Taking full advantage of the massive scale of "big data" will require technologies for analyzing and communicating these data to people, in terms they can understand and act on, at an equally massive scale. The automatic generation of narratives from data offers the promise of meeting this critical need. Our technology, which leverages human editorial judgment at scale, is today generating millions of stories from data, including highly personalized stories, in domains varying from business operations, to sports, education, medicine, and finance. The resulting narratives are often indistinguishable from those written by human analysts and writers.
11:20-12:20 Session 12A: Regression (AAAI)
 11:20 Time-dependent Trajectory Regression on Road Networks via Multi-Task LearningSPEAKER: unknownABSTRACT. Road travel costs are important knowledge hidden in large-scale GPS trajectory data set, the discovery of which can benefit many applications such as intelligent route planning and automatic driving navigation. While there are previous studies which tackled this task by modeling it as a regression problem with spatial smoothness taken into account, they unreasonably assumed that the latent cost of each road remains unchanged over time. Other works on route planning and recommendation that have considered temporal factors simply assumed temporal dynamics be known in advance as a parametric function over time, which is not faithful to reality. To overcome these limitations, in this paper, we propose an extension to a previous static trajectory regression framework by learning the temporal dynamics of road travel costs in an innovative non-parametric manner which can effectively overcome temporal sparsity problem. In particular, we unify multiple different trajectory regression problems in a multi-task framework by introducing a novel cross-task regularization factor which encourages temporal smoothness on the change of road travel costs. We then propose an efficient block coordinate descent method to solve the resulting problem by exploiting its separable structures and prove its convergence to global optimum. Experiments conducted on both synthetic and real data sets demonstrate the effectiveness of our method and its improved accuracy on travel time prediction. 11:35 A Concave Conjugate Approach for Nonconvex Penalized Regression with the MCP PenaltySPEAKER: unknownABSTRACT. The minimax concave plus penalty (MCP) function has been demonstrated to be effective in nonconvex penalization for feature selection. In this paper we propose a novel construction approach for MCP. In particular, we show that MCP can be derived from a concave conjugate of the Euclidean distance function. This construction approach in turn leads us to an augmented Lagrange multiplier method for solving the penalized regression problem with the MCP penalty. In our method each feature corresponds to a distinct tuning parameter, and these tuning parameters can be automatically updated. We also develop a d.c. (difference of convex functions) programming approach for the penalized regression problem using the notion of concave conjugate. We show that the augmented Lagrange multiplier method degenerates into the d.c. method under specific conditions. We conduct experimental analysis on a set of simulated data. The result is encouraging. 11:50 Lazy Gaussian Process Committee for Real-Time Online RegressionSPEAKER: Han XiaoABSTRACT. A significant problem of Gaussian process (GP) is its unfavorable scaling with a large amount of data. To overcome this issue, we present a novel GP approximation scheme for online regression. Our model is based on a combination of multiple GPs with random hyperparameters. The model is trained by incrementally allocating new examples to a selected subset of GPs. The selection is carried out efficiently by optimizing a submodular function. Experiments on real-world data sets showed that our method outperforms existing online GP regression methods in both accuracy and efficiency. The applicability of the proposed method is demonstrated by the mouse-trajectory prediction in an Internet banking scenario. 12:05 Continuous Conditional Random Fields for Efficient Regression in Large Fully Connected GraphsSPEAKER: unknownABSTRACT. When used for structured regression, powerful Conditional Random Fields (CRFs) are typically restricted to modeling effects of interactions among examples in local neighborhoods. Using more expressive representation would result in dense graphs, making these methods impractical for large-scale applications. To address this issue, we propose an effective CRF model with linear scale-up properties regarding approximate learning and inference for structured regression on large, fully connected graphs. The proposed method is validated on real-world large-scale problems of image de-noising and remote sensing. In conducted experiments, we demonstrated that dense connectivity provides an improvement in prediction accuracy. Inference time of less than a second on graphs with billions of edges makes the proposed model an attractive tool for large-scale, structured regression problems.
11:20-12:20 Session 12B: Sentiment and Recommendation (AAAI)
 11:20 The Automated Acquisition of Suggestions from TweetsSPEAKER: unknownABSTRACT. This paper targets at automatically detecting and classifying user's suggestions from tweets. The short and informal nature of tweets, along with the imbalanced characteristics of suggestion tweets, makes the task extremely challenging. To this end, we develop a classification framework on Factorization Machines, which is effective and efficient especially in classification tasks with feature sparsity settings. Moreover, we tackle the imbalance problem by introducing cost-sensitive learning techniques in Factorization Machines. Extensively experimental studies on a manually annotated real-life data set show that the proposed approach significantly improves the baseline approach, and yields the precision of 71.06% and recall of 67.86%. We also investigate the reason why Factorization Machines perform better. Finally, we introduce the first manually annotated dataset for suggestion classification. 11:35 A Hierarchical Aspect-Sentiment Model for Online ReviewsSPEAKER: unknownABSTRACT. To help users quickly understand the major opinions from massive online reviews, it is important to automatically reveal the latent structure of aspects, sentiment polarities, and the association between them from the review texts. However, there is little work available about how to do them effectively. In this paper, we propose a Bayesian nonparametric model to discover an aspect-sentiment tree from unlabeled online reviews. The model discovers hierarchical structure of aspect-based sentiments, and we name it the HASM. In HASM, the whole structure is a tree. Each node itself is a two-level tree, whose root represents an aspect and the children represent the sentiment polarities associated with it. Each aspect or sentiment polarity is modeled as a distribution of words. To automatically extract both the structure and parameters of the tree, we use recursive Chinese Restaurant Process (rCRP) as the prior and jointly infer the aspect-sentiment tree from the review texts. We experiment with two real datasets and show that our model is comparable to two other hierarchical topic models in terms of quantitative measures of topic trees. We also show that our model achieves better sentence-level classification accuracy than previously proposed aspect-sentiment joint models. 11:50 A Pattern Matching Based Model for Implicit Opinion Question IdentiﬁcationSPEAKER: unknownABSTRACT. This paper presents the results of developing subjectivity classiﬁers for Implicit Opinion Question (IOQ) identiﬁcation. IOQs are deﬁned as opinion questions with no opinion words. An IOQ example is “will the U.S. government pay more attention to the Paciﬁc Rim?” Our analysis on community questions of Yahoo! Answers shows that a large proportion of opinion questions are IOQs. It is thus important to develop techniques to identify such questions. In this research, we ﬁrst propose an effective framework based on mutual information and sequential pattern mining to construct an opinion lexicon that not only contains opinion words but also patterns. The discovered words and patterns are then combined with a machine learning technique to identify opinion questions. The experimental results on two datasets demonstrate the effectiveness of our approach. 12:05 From Semantic to Emotional Space in Probabilistic Sense Sentiment AnalysisSPEAKER: unknownABSTRACT. Sentiment Similarity of word pairs reflects the distance between the words regarding their underlying sentiments. This paper intends to infer the sentiment similarity between word pairs with respect to their senses. To achieve this aim, we propose a probabilistic emotion-based approach that is built on a hidden emotional model in which the basic human emotions are considered as hidden. This leads to predict a vector of basic emotions for each sense of the words. The emotional vectors are employed to infer the sentiment similarity of word pairs. We apply the proposed sentiment similarity approach to address two main natural language processing tasks, namely, Indirect yes/no Question Answer Pairs (IQAPs) inference and Sentiment Orientation (SO) prediction. Extensive experiments demonstrate that the proposed approach can effectively capture the sentiment similarity of word pairs and significantly outperforms semantic similarity measures on the above tasks.
11:20-12:20 Session 12C: Markets and Preferences (AAAI)
 11:20 Instructor Rating MarketsSPEAKER: unknownABSTRACT. We describe the design of Instructor Rating Markets (IRMs) where human participants interact through intelligent automated market-makers in order to provide dynamic collective feedback to instructors on the progress of their classes. The markets are among the first to enable the controlled study of prediction markets where traders can affect the very outcomes they are trading on. More than 200 students across a university campus participated in markets for ten classes in the Fall 2010 semester. In this paper, we describe how we designed these markets in order to elicit useful information, and analyze data from the deployment. We show that market prices convey useful information on future instructor ratings and contain significantly more information than do past ratings. The bulk of useful information contained in the price of a particular class is provided by students who are in that class, showing that the markets are serving to disseminate insider information. At the same time, we find little evidence of attempted manipulation by raters. The markets are also a laboratory for comparing different market designs and the resulting price dynamics, and we show how they can be used to compare market making algorithms. 11:35 How to Cut a Cake Before the Party EndsSPEAKER: unknownABSTRACT. For decades researchers have struggled with the problem of envy-free cake cutting: how to divide a divisible good between multiple agents so that each agent likes his own allocation best. Although an envy-free cake cutting protocol was ultimately devised, it is unbounded, in the sense that the number of operations can be arbitrarily large, depending on the preferences of the agents. We ask whether bounded protocols exist when the agents' preferences are restricted. Our main result is an envy-free cake cutting protocol for agents with piecewise linear valuations, which requires a number of operations that is polynomial in natural parameters of the given instance. 11:50 Online Lazy Updates for Portfolio Selection with Transaction CostsSPEAKER: unknownABSTRACT. With the ever increasing amount of data, particularly from search engines and social networks, stochastic optimization algorithms have become desirable for large-scale machine learning tasks because of their empirical efficiency and strong theoretical guarantees. However, a major challenge that is encountered is the cost of updating model parameters especially when the number of such parameters can be in the order of billions. Often times when parameters are updated, their values do not change significantly. As such, the cost of updating each parameter starts to outweigh the benefit. In this paper, we introduce an efficient primal-dual based online algorithm that performs lazy updates to the parameter vectors and show that its performance is competitive with reasonable lazy-strategies which have the benefit of hindsight. We demonstrate the effectiveness of our frugal algorithm in the online portfolio selection domain where a trader has to pay proportional transaction costs every time his portfolio is updated. We show that our Online Lazy Updates (OLU) algorithm results in sparse updates of the portfolio vector and is robust to transaction costs with extensive experiments on two real world datasets. 12:05 Abstract Preference Frameworks — A Unifying Perspective on Separability and Strong EquivalenceSPEAKER: unknownABSTRACT. To study mechanisms common across a variety of preference formalisms, we introduce a novel abstract preference framework. It makes no syntactic assumptions and uses most general representations to model the semantics. We use our abstract preference framework to study strong equivalence in preference formalisms, a version of equivalence that guarantees semantic-preserving replacements of parts of preference theories, and is fundamental for preference rewriting and modularity. To this end we identify abstract postulates in the language of preference frameworks, capturing natural semantic properties of preferences, and show that they lead to elegant characterizations, applicable in many practical settings. In a similar way, we study the separability of constraints and preferences. Preference languages have to capture constraints on the domain of interest that give rise to intended outcomes, and preferences that describe what is desirable. In many preference formalisms these two objectives are clearly separated, in some others they are not. We identify abstract postulates that guarantee separability of a preference formalism and lead to its "separated" variant.
11:20-12:20 Session 12D: Bayesian Inference and Causality (AAAI)
 11:20 Reduce and Re-Lift: Bootstrapped Lifted Likelihood Maximization for MAPSPEAKER: Fabian HadijiABSTRACT. By handling whole sets of indistinguishable objects together, lifted belief propagation approaches have rendered large, previously intractable, probabilistic inference problems quickly solvable. In this paper, we show that Kumar and Zilberstein's likelihood maximization (LM) approach to MAP inference is liftable, too, and actually provides additional structure for optimization. Specifically, it has been recognized that some pseudo marginals may converge quickly, turning intuitively into pseudo evidence. This additional evidence typically changes the structure of the lifted network: it may expand or reduce it. The current lifted network, however, can be viewed as an upper bound on the size of the lifted network required to finish likelihood maximization. Consequently, we re-lift the network only if the pseudo evidence yields a reduced network, which can efficiently be computed on the current lifted network. Our experimental results on Ising models, image segmentation and relational entity resolution demonstrate that this bootstrapped LM via "reduce and re-lift" finds MAP assignments comparable to those found by the original LM approach, but in a fraction of the time. 11:35 m-Transportability: Transportability of Causal Effect from Multiple EnvironmentsSPEAKER: unknownABSTRACT. We introduce m-transportability, a generalization of transportability, which offers a license to transfer causal information obtained from experiments and observations in m>=1 source environments to estimate a causal effect in a given target environment. We provide a novel characterization of m-transportability that directly exploits the completeness of do-calculus to obtain the necessary and sufficient conditions for m-transportability. We provide a sound and complete algorithm for deciding m-transportability that: (i) indicates non-m-transportability if a causal relation is not m-transportable from a given set of m source environments to a specified target environment; (ii) produces a transport formula, that is, a recipe for combining experimental information from m source environments with only observational information from the target environment to synthesize an estimate of the desired causal effect, otherwise. 11:50 RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational ModelsSPEAKER: Jan NoessnerABSTRACT. In this paper we present RockIt a maximum a-posteriori (MAP) query engine for statistical relational models. MAP inference in graphical models is an optimization problem and can naturally be mapped to integer linear programs (ILPs). With this paper, we present several optimizations for ILP translation of MAP queries including the meta algorithm Cutting Plane Aggregation (CPA). CPA exploits context-specific symmetries, that is, symmetries introduced by evidence and bundles large numbers of linear constraints. The resulting counting constraints lead to more compact ILPs and, more importantly, make the symmetry of the ground model explicit to state-of-the-art ILP solvers. Moreover, we parallelize all parts of the MAP inference pipeline in order to take advantage of multi-core architectures. We conducted numerous experiments on standard Markov logic networks (MLN) benchmarks, demonstrating that RockIt outperforms state-of-the-art systems such as Alchemy and Tuffy both in terms of efficiency and quality of results. 12:05 Causal Transportability with Limited ExperimentsSPEAKER: Elias BareinboimABSTRACT. We address the problem of transferring causal knowledge learned in one environment to another, potentially different environment, when only limited experiments may be conducted at the source. This generalizes the treatment of transportability introduced in [Pearl and Bareinboim, 2011; Bareinboim and Pearl, 2012b], which deals with transferring causal information when any experiment can be conducted at the source. Given that it is not always feasible to conduct certain controlled experiments, we consider the decision problem whether experiments on a selected subset Z of variables together with qualitative assumptions encoded in a diagram may render causal effects in the target environment computable from the available data. This problem, which we call z-transportability, reduces to ordinary transportability when Z is all-inclusive, and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. This paper establishes a necessary and sufficient condition for causal effects in the target domain to be estimable from both the non-experimental information available and the limited experimental information transferred from the source. We further provides a complete algorithm for computing the transport formula, that is, a way of fusing experimental and observational information to synthesize an unbiased estimate of the desired causal relation.
11:20-12:20 Session 12E: Knowledge-Based Systems (AAAI)
 11:20 Graph Traversal Methods for Reasoning in Large Knowledge-Based SystemsSPEAKER: unknownABSTRACT. Commonsense reasoning at scale is a core problem for cognitive systems. In this paper, we discuss two ways in which heuristic graph traversal methods can be used to generate plausible inference chains. First, we discuss how Cyc’s predicate-type hierarchy can be used to get reasonable answers to queries. Second, we explain how connection graph-based techniques can be used to identify script-like structures. Finally, we demonstrate through experiments that these methods lead to significant improvement in accuracy for both Q/A and script construction. 11:35 Automatic Extraction of Efficient Axiom Sets from Large Knowledge BasesSPEAKER: unknownABSTRACT. Efficient reasoning in large knowledge bases is an important problems for cognitive systems. Hand-optimization of reasoning becomes impractical as KBs grow, and impossible as knowledge is automatically added via knowledge capture or machine learning. This paper describes a method for automatic extraction of axioms for efficient inference over large knowledge bases, given a set of query types and information about the types of facts in the KB currently as well as what might be learned. We use the highly right skewed distribution of predicate connectivity in large knowledge bases to prune intractable regions of the search space. We show the efficacy of these techniques via experiments using queries from a cognitive system which does learning by reading. Results show that these methods lead to an order of magnitude improvement in time with minimal loss in coverage. 11:50 Preemptive Strategies for Overcoming the Forgetting of GoalsSPEAKER: unknownABSTRACT. Maintaining and pursuing multiple goals over varying time scales is an important ability for artificial agents in many cognitive architectures. Goals that remain suspended for long periods, however, are prone to be forgotten. This paper presents a class of preemptive strategies that allow agents to selectively retain goals in memory and to recover forgotten goals. Preemptive strategies work by retrieving and rehearsing goals at triggers, which are either periodic or are predictive of the opportunity to act. Since cognitive architectures contain common hierarchies of memory systems and share similar forgetting mechanisms, these strategies work across multiple architectures. We evaluate their effectiveness in a simulated mobile robot controlled by Soar, and demonstrate how preemptive strategies can be adapted to different environments and agents. 12:05 Learning to Efficiently Pursue Communication Goals on the Web with the GOSMR ArchitectureSPEAKER: Kevin GoldABSTRACT. We present GOSMR ("goal oriented scenario modeling robots"), a cognitive architecture designed to show coordinated, goal-directed behavior when using networked computer applications, focusing on the web browser as a case study. The architecture combines a variety of artificial intelligence techniques, including planning, temporal difference learning, elementary reasoning over uncertainty, and communication, but is designed to be computationally lightweight. Its intended use is to drive applications on large-scale cyber security experiments in which users' adaptation in the face of resource denial should be intelligent but varied. The planning system performs temporal difference learning of action times, discounts goals according to hyperbolic discounting of time-to-completion and chance of success, takes into account the assertions of other agents, and separates abstract action from site-specific affordances. Our experiment, in which agents learn to prefer a social networking style site for sending and receiving messages, shows that utility-proportional goal selection is a reasonable alternative to Boltzmann goal selection for producing a rational mix of behavior.
11:20-12:20 Session 12F: Spotlights and Senior Members (AAAI)
 11:20 SOCS: What's HotSPEAKER: unknownABSTRACT. Grand ideas and visions for search 11:35 SOCS: ChallengesSPEAKER: unknown 11:50 AAMAS: ChallengesSPEAKER: unknownABSTRACT. Curing Robot Autism: A Challenge 12:05 SDM: Best Paper: Triadic Measures on Graphs: The Power of Wedge SamplingSPEAKER: unknown
11:20-12:20 Session 12G: Deployed Application of Machine Learning (IAAI)
 11:20 Deployed: An Antimicrobial Prescription Surveillance System that Learns from ExperienceSPEAKER: unknownABSTRACT. Inappropriate prescribing of antimicrobials is a major clinical and health concern, as well as a financial burden, in hospitals worldwide. In this paper, we describe a deployed automated antimicrobial prescription surveillance system that has been assisting hospital pharmacists in identifying and reporting inappropriate antimicrobial prescriptions. One of the key characteristics of this system is its ability to learn new rules for detecting inappropriate prescriptions based on previous false alerts. The supervised learning algorithm combines instance-based learning and rule induction techniques. It exploits temporal abstraction to extract a meaningful time interval representation from raw clinical data, and applies nearest neighbor classification with a distance function on both temporal and non-temporal parameters. The learning capability is valuable both in configuring the system for initial deployment and improving its long term use. We give an overview of the application, point to lessons learned so far and provide insight into the machine learning capability. 11:50 Deployed: GRADE: Machine Learning Support for Graduate AdmissionsSPEAKER: unknownABSTRACT. This paper describes GRADE, a statistical machine learning system developed to support the work of the graduate admissions committee in the University of Texas at Austin Department of Computer Science (UTCS). In recent years, UTCS has received increasingly large pools of PhD applicants that are unwieldy to manage with a traditional review process. GRADE uses a dataset of historical admissions data to predict how likely each new applicant is to be admitted to the graduate program. Its predictions are reported to the admissions committee along with a human-readable explanation. GRADE makes the review process more efficient, in part, by enabling reviewers to identify very high- and low-quality applicants quickly, leaving more time to deliberate on borderline applicants. An evaluation over two seasons of PhD admissions indicates that the system leads to dramatic time savings, reducing the total time spent on reviews by at least 74%.
11:30-12:30 Session 13 (EAAI)
 11:30 EAAI-13 Invited Talk: Broader and Earlier Access to Machine LearningSPEAKER: unknownABSTRACT. In a world of big data, everyone needs machine learning. How do we teach it to everyone? At Villanova we have embarked on an NSF-funded project to develop a set of machine-learning modules for students from a wide variety of domains. Our goal is to have students who can make intelligent and effective use of appropriate machine learning algorithms and techniques as tools. In this talk I will describe our grant and share the state of the modules we have so far, in order to stimulate discussion about how we can teach machine learning more broadly.
12:20-12:30 Session 14A: - (AAAI)
 12:20 Predicting Professions through Probabilistic Model under Social ContextSPEAKER: unknownABSTRACT. In this paper, we investigate the problem of predicting people's professions under social context. Previous work considering clothing information as well as fore/background context preliminarily proves the feasibility of predicting professions. In this paper, we discuss this problem in a more general case --- multiple people in one photo with arbitrary poses, and argue that with appropriately built partial body features, spatial relations, and background context, a more appealing result is achieved by a probabilistic model. We conduct experiments on $14$ representative professions with over $7000$ images, and demonstrate the model's superiority with impressive results. 12:22 Algorithm Selection in Bilateral NegotiationSPEAKER: unknownABSTRACT. Despite the abundance of strategies in the literature on repeated negotiation under incomplete information, there is no single negotiation strategy that is optimal for all possible settings. Thus, agent designers face an algorithm selection'' problem--- which negotiation strategy to choose when facing a new negotiation. Our approach to this problem is to predict the performance of different strategies based on structural features of the domain and to select the negotiation strategy that is predicted to be most successful using a meta-agent''. This agent was able to outperform all of the finalists to the recent Automated Negotiation Agent Competition (ANAC). Our results have insights for agent-designers, demonstrating that a little learning goes a long way'', despite the inherent uncertainty associated with negotiation under incomplete information. 12:24 RAProp: Ranking Tweets by Exploiting the Tweet/User/Web Ecosystem and Inter-Tweet Agreement SPEAKER: unknownABSTRACT. The increasing popularity of Twitter renders improved trustworthiness and relevance assessment of tweets much more important for search. However, given the limitations on the size of tweets, it is hard to extract measures for ranking from the tweet’s content alone. We propose a method of ranking tweets by generating a reputation score for each tweet that is based not just on content, but also additional information from the Twitter ecosystem that consists of users, tweets, and the webpages that tweets link to. The reputation score is used to power a novel method of ranking tweets by propagating the reputation over an agreement graph based on tweets’ content similarity. An evaluation of our method on 16 million tweets from the TREC 2011 Microblog Dataset shows that it doubles the precision over the baseline method, and performs better than the highest-performing method on the TREC 2011 Microblog dataset. 12:26 Learning CP-net Preferences Online from User QueriesSPEAKER: unknownABSTRACT. CP-nets (Boutilier et al., 1999) offer a potentially compact qualitative representation of human preferences that operate under ceteris paribus (“with all else being equal”) semantics. In this paper we present a novel algorithm through which an agent learns the preferences of a user. CP-nets are used to represent such preferences and are learned online through a series of queries generated by the algorithm. Our algorithm builds a CP-net for the user by creating nodes and initializing CPTs, then gradually adding edges and forming more complex CPTs consistent with responses to queries until a confidence parameter is reached. 12:28 Take or Wait? Learning Turn-Taking from Multiparty DataSPEAKER: unknownABSTRACT. We build turn-taking models for autonomous characters in language-based interactions with small groups of children. Two models explore the use of support vector machines given the same multimodal features, but different methods for collecting turn-taking labels.
12:20-12:30 Session 14B (AAAI)
 12:20 Fast, Near-Optimal Computation for Multi-robot Path Planning on GraphsSPEAKER: unknownABSTRACT. We report a new method for computing near optimal makespan solutions to multi-robot path planning problem on graphs. Our focus here is with hard instances - those with up to 85% of all graph nodes occupied by robots. Our method yields 100-1000x speedup compared with existing methods. At the same time, our solutions have much smaller and often optimal makespans. 12:22 Uncertainty Reduction For Active Image Clustering via a Hybrid Global-Local Uncertainty ModelSPEAKER: unknownABSTRACT. We propose a novel combined global/local model for active semi-supervised spectral clustering based on the principle of uncertainty reduction. We iteratively compute the derivative of the eigenvectors produced by spectral decomposition with respect to each item/image, and combine this with local label entropy provided by the current clustering results in order to estimate the uncertainty reduction potential of each item in the dataset. We then generate pairwise queries with respect to the best candidate item and retrieve the needed constraints from the user. We evaluate our method using three different image datasets---faces, leaves and dogs, and consistently demonstrate performance superior to the current state-of-the-art. 12:24 Towards Joint Inference for Complex Ontology MatchingSPEAKER: Jan NoessnerABSTRACT. In this paper, we show how to model the matching problem as a problem of joint inference. In opposite to existing approaches, we distinguish between the layer of labels and the layer of concepts and properties. Entities from both layers appear as first class citizens in our model. We present an example and explain the benefits of our approach. Moreover, we argue that our approach can be extended to generate correspondences involving complex concept descriptions. 12:26 AMRec: An Intelligent System for Academic Method RecommendationSPEAKER: unknownABSTRACT. Finding new academic methods for research problems is the key task in a researcher’s research career. It is usually very difficult for new researchers to find good methods for their research problems since they lack of research experiences. In order to help researchers carry out their researches in a more convenient way, we describe a novel recommendation system called AMRec to recommend new academic methods for research problems in this paper. Our proposed system first extracts academic concepts (Tasks and Methods) and their relations from academic literatures, and then leverages the regularized matrix factorization model for academic method recommendation. Preliminary evaluation results are also reported and discussed. 12:28 An Ensemble of Linearly Combined Reinforcement-Learning AgentsSPEAKER: unknownABSTRACT. Reinforcement-learning (RL) algorithms are often tweaked and tuned to specific environments when applied, calling into question whether learning can truly be considered autonomous in these cases. In this work, we show how more robust learning across environments is possible by adopting an ensemble approach to reinforcement learning. Our approach learns a weighted linear combination of Q-values from multiple independent learning algorithms. In our evaluations in generalized RL environments, we find that the algorithm compares favorably to the best tuned algorithm. Our work provides a promising basis for further study into the use of ensemble methods in RL.
12:20-12:30 Session 14C (AAAI)
 12:20 Learning Tractable Graphical Models Using Mixture of Arithmetic CircuitsSPEAKER: unknownABSTRACT. In recent years, there has been a growing interest in learning tractable graphical models in which exact inference is efficient. Two main approaches are to restrict the inference complexity directly, as done by low-treewidth graphical models and arithmetic circuits (ACs), or introduce latent variables, as done by mixtures of trees, latent tree models, and sum-product networks (SPNs). In this paper, we combine these approaches to learn a mixtures of ACs (MAC). A mixture can represent many distributions exponentially more compactly than a single AC. By using ACs as mixture components, MAC can represent complex distributions using many fewer components than required by other mixture models. MAC generalizes ACs, mixtures of trees, latent class models, and thin junction trees, and can be seen as a special case of an SPN. Compared to state-of-the-art algorithms for learning SPNs and other tractable models, MAC is consistently more accurate while maintaining tractable inference. 12:22 The Value of Ignorance about the Number of PlayersSPEAKER: unknownABSTRACT. Our starting point is the model of Meir et al.[AAAI'12], where agents have uncertainty over the actual number of participants in a congestion game, formalized as a prior distribution over subsets of players. In this work we consider the idea of partial information revelation (signaling), for such games where the number of participants is unknown. 12:24 Chance-Constrained Strong Controllability of Temporal Plan Networks with UncertaintySPEAKER: unknownABSTRACT. This works presents a novel approach for determining chance-constrained strong controllability of Temporal Plan Networks with Uncertainty (TPNU) by framing it as an Optimal Satisfiability Problem (OpSAT). 12:26 A Novel Human Computation Game for Critique AggregationSPEAKER: unknownABSTRACT. We present a novel human computation game that elicits not only annotations, but also direct critique of a system from the players. The game is based on the popular board game - Dixit. We present the results of the initial run of the game, in which the answers of 15 players were used to profile the mistakes of an aspect based opinion mining system. We show that, for this complex problem, the gameplay allowed us to identify the major faults and the generate improvement suggestions.
12:20-12:30 Session 14D (AAAI)
 12:20 Throwing Darts: Random Sampling Helps Tree Search When the Number of Short Certificates Is ModerateSPEAKER: unknownABSTRACT. One typically proves infeasibility in satisfiability/constraint satisfaction (or optimality in integer programming) by constructing a tree certificate. However, deciding how to branch in the search tree is hard, and impacts search time drastically. We explore the power of a simple paradigm, that of throwing random darts into the assignment space and then using information gathered by that dart to guide what to do next. This method seems to work well when the number of short certificates of infeasibility is moderate, suggesting the overhead of throwing darts can be countered by the information gained by these darts. 12:22 A Formal Framework for the Specification, Verification and Synthesis of DiagnosersSPEAKER: unknownABSTRACT. In this work we present a formal approach to the design of Fault Detection and Identification (FDI) components. We define a comprehensive language for the specification of FDI, and discuss how to check whether a given FDI component fulfills its specifications. Then, we propose an automatic procedure to synthesize an FDI component that satisfies a given specification. The approach has been implemented and tested in realistic case studies from the aerospace domain. 12:24 Scaling up Quadratic Programming Feature SelectionSPEAKER: unknownABSTRACT. Domains such as vision, bioinformatics, web search and web rankings involve datasets where number of features is very large. Feature selection is commonly employed to deal with high dimensional data. Recently, Quadratic Programming Feature Selection (QPFS) has been shown to outperform many of the existing feature selection methods for a variety of datasets. In this paper, we propose an SMO based framework for QPFS. This helps in reducing the cubic computational time (in terms of data dimension) of the standard QPFS to quadratic time in practice. Further, our approach has less memory requirement than QPFS. This memory saving can be critical for doing feature selection in high dimensions. The performance of our approach is demonstrated using three publicly available benchmark datasets from bioinformatics domain. 12:26 Co-training Based Bilingual Sentiment Lexicon LearningSPEAKER: unknownABSTRACT. In this paper, we address the issue of bilingual sentiment lexicon learning which aims to automatically and simultaneously generate sentiment words for two languages. The underlying motivation is that sentiment information from two languages can perform iterative mutual-teaching in the learning procedure. We propose to develop two classifiers to determine the sentiment polarities of words under a co-training framework, which makes full use of the two-view sentiment information from the two languages. The word alignment derived from the parallel corpus is leveraged to design effective features and to bridge the learning of the two classifiers. The classifiers after co-training can be used to generate bilingual sentiment lexicons. The experimental results on English and Chinese languages indicate that the proposed approach outperforms inductive and transductive approaches. 12:28 Adversarial Cooperative Path-Finding: A First View SPEAKER: unknownABSTRACT. An adversarial version of the problem of cooperative path finding (CPF) over graphs is addressed. Two or more teams of agents compete in finding paths in the graph to given destination vertices. The task is to control agents of a selected team so that its agents reach their destinations before agents of adversaries. Tactics such a blocking agents of the adversary or protecting own agents are allowed by the suggested formal definition of the problem.
12:30-13:45Lunch Break
13:45-14:45 Session 15A: Invited talk: Kumar (AAAI)
 13:45 AAAI-13 Invited Talk: Aerial Robot SwarmsSPEAKER: Vijay KumarABSTRACT. Autonomous microaerial robots can operate in three-dimensional unstructured environments, and offer many opportunities for environmental monitoring, search and rescue, and first response. I will describe the challenges in developing small, agile robots and our recent work in the areas of (1) control and planning, (2) state estimation and mapping, and (3) coordinating large teams of robots, with applications to cooperative manipulation and transport, construction, and exploration and mapping.
13:45-14:45 Session 15B (EAAI)
 13:45 EAAI-13 Teaching and Mentoring Session 1SPEAKER: unknown
14:45-15:45 Session 16A: Clustering (AAAI)
 14:45 Smart Multi-task Bregman Clustering and Multi-task Kernel ClusteringSPEAKER: unknownABSTRACT. Multitask Bregman Clustering (MBC) alternatively updates clusters and learns relationship between clusters of different tasks, and the two phases boost each other. However, the boosting does not always have positive effects, it may also cause negative effects. Another issue of MBC is that it cannot deal with nonlinear separable data. In this paper, we show that MBC's process of using cluster relationship to boost the updating clusters phase may cause negative effects, i.e., cluster centroid may be skewed under some conditions. We propose a smart multi-task Bregman clustering (S-MBC) algorithm which identifies negative effects of the boosting and avoids the negative effect if it occurs. We then extend the framework of S-MBC to a smart multi-task kernel clustering (S-MKC) framework to deal with nonlinear separable data. We also propose a specific implementation of the framework which could be applied to any Mercer kernel. Experimental results confirm our analysis, and demonstrate the superiority of our proposed methods. 15:00 Spectral Rotation versus K-means in Spectral ClusteringSPEAKER: unknownABSTRACT. Spectral clustering has been a popular data clustering algorithm. This category of approaches often resort to other clustering methods, such as K-Means, to get the final cluster. The potential flaw of such common practice is that the obtained relaxed continuous spectral solution could severely deviate from the true discrete solution. In this paper, we propose to impose an additional orthonormal constraint to better approximate the optimal continuous solution to the graph cut objective functions. Such a method, called spectral rotation in literature, optimizes the spectral clustering objective functions better than K-Means, and improves the clustering accuracy. We would provide efficient algorithm to solve the new problem rigorously, which is not significantly more costly than K-Means. We also establish the connection between our method and K-Means to provide theoretical motivation of our method. Experimental results show that our algorithm consistently reaches better cut and meanwhile outperforms in clustering metrics than classic spectral clustering methods. 15:15 Unsupervised Cluster Matching via Probabilistic Latent Variable ModelsSPEAKER: unknownABSTRACT. We propose a probabilistic latent variable model for unsupervised cluster matching, which is the task of finding correspondences between clusters of objects in different domains. Existing object matching methods find one-to-one matching in two domains. The proposed model finds many-to-many matching, and can handle multiple domains with different numbers of objects. The proposed model assumes that there are an infinite number of latent vectors that are shared by all domains, and each object is generated using one of the latent vectors and a domain-specific linear projection. By inferring a latent vector to be used for generating each object, objects in different domains are clustered in shared groups, and thus we can find matching between clusters in an unsupervised manner. We present efficient inference procedures of the proposed model based on a stochastic EM algorithm. The effectiveness of the proposed model is demonstrated with experiments using synthetic and real data sets. 15:30 Clustering with Complex Constraints - Algorithms and ApplicationsSPEAKER: unknownABSTRACT. Clustering with constraints is an important and developing area. However, most work is confined to conjunctions of simple together and apart constraints which limit their usability. In this paper, we propose a new formulation of constrained clustering that is able to incorporate not only existing types of constraints but also more complex logical combinations beyond conjunctions. We first show how any statement in conjunctive normal form (CNF) can be represented as a linear inequality. Since existing clustering formulations such as spectral clustering cannot easily incorporate these linear inequalities, we propose a quadratic programming (QP) clustering formulation to accommodate them. This new formulation allows us to have much more complex guidance in clustering. We demonstrate the effectiveness of our approach in two applications on text and personal information management. We also compare our algorithm against existing constrained spectral clustering algorithm to show its efficiency in computational time.
14:45-15:45 Session 16B: Reinforcement Learning (AAAI)
 14:45 Multi-Armed Bandit with Budget Constraint and Variable CostsSPEAKER: unknownABSTRACT. We study the multi-armed bandit problems with budget constraint and variable costs (MAB-BV). In this setting, pulling an arm will receive a random reward together with a random cost, and the objective of an algorithm is to pull a sequence of arms in order to maximize the expected total reward with the costs of pulling those arms complying with a budget constraint. This new setting models many Internet applications (e.g., ad exchange, sponsored search, and cloud computing) in a more accurate manner than previous settings where the pulling of arms is either costless or with a fixed cost. We propose two UCB based algorithms for the new setting. The first algorithm needs prior knowledge about the lower bound of the expected costs when computing the exploration term. The second algorithm eliminates this need by estimating the minimal expected costs from empirical observations, and therefore can be applied to more real-world applications where prior knowledge is not available. We prove that both algorithms have nice learning abilities, with regret bounds of $O(\ln B)$. Furthermore, we show that when applying our proposed algorithms to a previous setting with fixed costs (which can be regarded as our special case), one can improve the previously obtained regret bound. Our simulation results on real-time bidding in ad exchange verify the effectiveness of the algorithms and are consistent with our theoretical analysis. 15:00 Basis Adaptation for Sparse Nonlinear Reinforcement LearningSPEAKER: Sridhar MahadevanABSTRACT. This paper presents a new approach to basis adaptation in reinforcement learning (RL) using the recently proposed {\em mirror-descent} framework. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in high-dimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. We introduce a general framework for nonlinear separable value function approximation based on finding Frechet gradients of an error function based on variable projection functionals. We then show how to combine basis adaptation methods with proximal-gradient based temporal-difference (TD) methods and present a new class of regularized TD methods, which combine feature selection through sparse $L_1$ regularization and basis adaptation. Experimental results are provided to illustrate and validate the approach. 15:15 Pruning for Monte Carlo Distributed Reinforcement Learning in Decentralized POMDPsSPEAKER: Bikramjit BanerjeeABSTRACT. Decentralized partially observable Markov decision processes (Dec-POMDPs) offer a powerful modeling technique for realistic multi-agent coordination problems under uncertainty. Prevalent solution techniques are centralized and assume prior knowledge of the model. Recently a Monte Carlo based distributed reinforcement learning approach was proposed, where agents take turns to learn best responses to each other’s policies. This promotes decentralization of the policy computation problem, and relaxes reliance on the full knowledge of the problem parameters. However, this Monte Carlo approach has a large sample complexity, which we address in this paper. In particular, we propose and analyze a modified version of the previous algorithm that adaptively eliminates parts of the experience tree from further exploration, thus requiring fewer samples while ensuring unchanged confidence in the learned value function. Experiments demonstrate significant reduction in sample complexity – the maximum reductions ranging from 61% to 93% over different benchmark Dec-POMDP problems – with the final policies being often better due to more focused exploration. 15:30 Structured Kernel-Based Reinforcement LearningSPEAKER: unknownABSTRACT. Kernel-based reinforcement learning (KBRL) is a popular approach to learning non-parametric value function approximations. In this paper, we present structured KBRL, a paradigm for kernel-based RL that allows for modeling independencies in the transition and reward models of problems. Real-world problems often exhibit this structure and can be solved more efficiently when it is modeled. We make three contributions. First, we motivate our work, define a structured backup operator, and prove that it is a contraction. Second, we show how to evaluate our operator efficiently. Our analysis reveals that the fixed point of the operator is the optimal value function in a special factored MDP. Finally, we evaluate our method on a synthetic problem and compare it to two KBRL baselines. In most experiments, we learn better policies than the baselines from an order of magnitude less training data.
14:45-15:45 Session 16C: Recognition and Detection (AAAI)
 14:45 Incremental Learning Framework for Indoor Scene RecognitionSPEAKER: unknownABSTRACT. This paper presents a novel framework for online incremental place recognition in an indoor environment. The framework addresses the scenario in which scene images are gradually obtained during long-term operation in the real-world indoor environment. Multiple users may interact with the classification system and confirm either current or past prediction results; the system then immediately updates itself to improve the classification system. This framework is based on the proposed n-value self-organizing and incremental neural network (n-SOINN), which has been derived by modifying the original SOINN to be appropriate for use in scene recognition. The evaluation was performed on the standard MIT 67-category indoor scene dataset and shows that the proposed framework achieves the same accuracy as that of the state-of-the-art offline method, while the computation time of the proposed framework is significantly faster and fully incremental update is allowed. Additionally, a small extra set of training samples is incrementally given to the system to simulate the incremental learning situation. The result shows that the proposed framework can leverage such additional samples incrementally and achieve the state-of-the-art result. 15:00 Video Saliency Detection via Dynamic Consistent Spatio-Temporal Attention ModellingSPEAKER: unknownABSTRACT. Human vision system actively seeks salient regions and movements in video sequences to reduce the search effort. Modeling computational visual saliency map provides important information for semantic understanding in many real world applications. In this paper, we propose a novel video saliency detection model for detecting the attended regions that correspond to both interesting objects and dominant motions in video sequences. In spatial saliency map, we in-herit the classical bottom-up spatial saliency map based on intensity, color, contrast, and orientation features in pixel-level. In temporal saliency map, a novel optical flow model is proposed based on the dynamic consistency of motion. The spatial and the temporal saliency maps are constructed and further fused together to create a novel attention model. The proposed attention model is evaluated on three video datasets. Empirical validations demonstrate the salient regions detected by our dynamic consistent saliency map highlight the interesting objects effectively and efficiency. More importantly, the automatically video attended regions detected by proposed attention model are consistent with the ground truth saliency maps of eye movement data. 15:15 Gradient Networks: Explicit Shape Matching without Extracting EdgesSPEAKER: Edward HsiaoABSTRACT. We present a novel framework for shape-based template matching in images. While previous approaches required brittle contour extraction, considered only local information, or used coarse statistics, we propose to match the shape explicitly on low-level gradients by formulating the problem as traversing paths in a gradient network. We evaluate our algorithm on a challenging dataset of objects in cluttered environments and demonstrate significant improvement over state-of-the-art methods for shape matching and object detection. 15:30 Vesselness Features and the Inverse Compositional AAM for Robust Face Recognition Using Thermal IRSPEAKER: unknownABSTRACT. Over the course of the last decade, infrared (IR) and particularly thermal IR imaging based face recognition has emerged as a promising complement to conventional, visible spectrum based approaches which continue to struggle when applied in the real world. While inherently insensitive to visible spectrum illumination changes, IR images introduce specific challenges of their own, most notably sensitivity to factors which affect facial heat emission patterns, e.g. emotional state, ambient temperature, and alcohol intake. In addition, facial expression and pose changes are more difficult to correct in IR images because they are less rich in high frequency detail which is an important cue for fitting any deformable model. In this paper we describe a novel method which addresses these major challenges. Specifically, to normalize for pose and facial expression changes we generate a synthetic frontal image of a face in a canonical, neutral facial expression from an image of the face in an arbitrary pose and facial expression. This is achieved by piecewise affine warping which follows active appearance model (AAM) fitting. This is the first publication which explores the use of an AAM on thermal IR images; we propose a pre-processing step which enhances detail in thermal images, making AAM convergence faster and more accurate. To overcome the problem of thermal IR image sensitivity to the exact pattern of facial temperature emissions we describe a representation based on reliable anatomical features. In contrast to previous approaches, our representation is not binary; rather, our method accounts for the reliability of the extracted features. This makes the proposed representation much more robust both to pose and scale changes. The effectiveness of the proposed approach is demonstrated on the largest public database of thermal IR images of faces on which it achieves perfect recognition performance and significantly outperforms previously described methods.
14:45-15:45 Session 16D: Situated Interaction (AAAI)
 14:45 Integrating Programing by Example and Natural Language ProgramingSPEAKER: unknownABSTRACT. Mehdi Manshadi, Dan Gildea and James Allen We motivate the integration of programming by example and natural language programming by developing a system for specifying programs for simple text editing operations. The programs are described with unconstrained natural language instructions, and providing a single example of input/output. We show that natural language allows the system to deduce the correct program much more often and much faster than is possible with the input/output example(s) alone, showing that natural language programming and programming by example can be combined in a way that overcomes the ambiguities that both methods suffer from individually, with a minimum of additional effort from the user. (This paper is from the main AAAI technical track, paper 251.) 15:00 A Hybrid Architectural Approach to Understanding and Appropriately Generating Indirect Speech ActsSPEAKER: unknownABSTRACT. Current approaches to handling indirect speech acts (ISAs) do not account for their sociolinguistic underpinnings (i.e., politeness strategies). Deeper understanding and appropriate generation of indirect acts will require mechanisms that integrate natural language (NL) understanding and generation with social information about agent roles and obligations, which we introduce in this paper. Additionally, we tackle the problem of understanding and handling indirect answers that take the form of either speech acts or physical actions, which requires an inferential, plan-reasoning approach. In order to enable artificial agents to handle an even wider-variety of ISAs, we present a hybrid approach, utilizing both the idiomatic and inferential strategies. We then demonstrate our system successfully generating indirect requests and handling indirect answers, and discuss avenues of future research. our system successfully generating indirect requests and handling indirect answers, and discuss avenues of future research. 15:15 An Agent Model for the Appraisal of Normative Events Based in In-Group and Out-Group RelationsSPEAKER: unknownABSTRACT. Emotional synthetic characters are able to evaluate (appraise) events as positive or negative taking into account several factors to trigger their emotional states. Currently, the vast majority of the models for the appraisal in synthetic characters consider factors related to the goals and preferences of the characters. We argue that appraisals that only take into consideration these "personal" factors are incomplete as other more social factors, such as the normative and the social context, including in-group and out-group relations, should be considered as well. Without them, moral emotions such as shame cannot be appraised, limiting the believability of the characters in certain situations. We present a model for the appraisal of characters' actions that evaluates if actions from in-group and out-group members conform or not to social norms and generates different emotions according to the social relation between the characters. The model was then implemented in an architecture for virtual agents and evaluated with humans. Results suggest that the emotions generated by our model are perceived adequately by the participants, taking into account the social context and that participants experienced very similar emotions, both in type and intensity, to the emotions appraised and generated by the characters. 15:30 SALL-E: Situated Agent for Language LearningSPEAKER: unknownABSTRACT. We describe ongoing research towards building a cognitively plausible system for near one-shot learning of the meanings of attribute words and object names, by grounding them in a sensory model. The system learns incrementally from human demonstrations recorded with the Microsoft Kinect, in which the demonstrator can use unrestricted natural language descriptions. We achieve near-one shot learning of simple objects and attributes by utilizing child language learning strategies and focusing solely on examples where the learning agent is confident, ignoring the rest of the data. We evaluate the system’s learning ability by having it generate descriptions of presented objects, including objects it has never seen before, and comparing the system response against collected human descriptions of the same objects. We propose that retrieving object examples with k-nearest neighbor using Mahalanobis distance corresponds to a cognitively plausible representation of objects. Our results show great promise for achieving rapid, near one-shot, incremental learning of word meanings.
14:45-15:45 Session 16E: Spotlights and Senior Members (AAAI)
 14:45 Modern Dynamic Organ Exchanges: Algorithms and Market DesignSPEAKER: Tuomas SandholmABSTRACT. In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this is NP-hard. It was one of the main obstacles to a national kidney exchange. We developed the first (and still only) algorithm capable of clearing these exchanges optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. Furthermore, clearing is actually an online problem where patient-donor pairs and altruistic donors appear and expire over time. We first developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. Such algorithms tend to be too compute-intensive at run time, so recently we developed a general approach for giving batch algorithms guidance about the future without a run-time hit. It learns potentials of elements of the problem, and then uses them in each batch clearing. I will share experiences from using our algorithms to run the UNOS US-wide kidney exchange since its inception two and a half years ago, and two regional ones before that. We introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I will present results – both theoretical and experimental – on the role of long chains. I will present probabilistic planning algorithms that are robust against last-minute execution failures - currently the main challenge in kidney exchange. I will discuss how general-purpose integer program solvers do not scale to this task, and will present a brand new branch-and-price algorithm that does. I will also give an overview about other issues in kidney exchanges such as sniping in the context of competing exchanges, and transplant centers' incentives to hide some of their pairs. Finally, I will discuss simulation results about the possibility of liver lobe exchanges and cross-organ exchanges. The talk covers material from the following papers of ours. In addition, the talk will cover results by Alvin Roth, Utku Unver, Itai Ashlagi, and others. - Algorithms for Robust Kidney Exchange Clearing. (With Dickerson, J. and Procaccia, A.) - Liver and Multi-Organ Exchange. (With Dickerson, J.) Under review. - Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. AAAI-12. (With Dickerson, J. and Procaccia, A.) - Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. AAMAS-12. (With Dickerson, J. and Procaccia, A.) - Online Stochastic Optimization in the Large: Application to Kidney Exchange. IJCAI-09. (With Awasthi, P.) - A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), March 2009. (With Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Ünver, U., and Montgomery, R.) - Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. EC-07. (With Abraham, D. and Blum, A.) 15:15 Data Mining Social Media for Public Health ApplicationsSPEAKER: Henry KautzABSTRACT. There is much activity in data mining social media for marketing campaigns, financial prediction, and similar purposes. Recently, however, a smaller group of researchers have begun to leverage this sensor network for a singular public good: modeling public health at a population scale. Researchers have shown, for example, that Twitter postings can be used to track and predict influenza and detect affective disorders such as depression. Such work provides strong evidence that there is a strong health signal'' in social media.
14:45-15:45 Session 16F: Monitoring and Response Systems (IAAI)
 14:45 Emerging: Timed Probabilistic Automaton: A Bridge between Raven and Song Scope for Automatic Species RecognitionSPEAKER: unknownABSTRACT. Raven and Song Scope are two state-of-the-art auto-mated sound analysis tools based on machine learning techniques for environmental monitoring. Many research works have been conducted upon them, however, no or rare exploration mentions about the performance and comparison between them. This paper compares the tools from six aspects: theory, software interface, ease of use, detection targets, detection accuracy, and potential applications. Through deep exploration one critical gap is identified that there is a lack of approach to detect both syllables and call structures, since Raven only aims to detect syllables while Song Scope targets call structures. Therefore, a Timed Probabilistic Automata (TPA) system is proposed which separates syllables first and clusters them into complex structures after. 15:05 Emerging: Multiagent Router Throttling: Decentralized Coordinated Response against DDoS AttacksSPEAKER: unknownABSTRACT. Distributed denial of service (DDoS) attacks constitute a rapidly evolving threat in the current Internet. In this paper we introduce Multiagent Router Throttling, a decentralized DDoS response mechanism in which a set of upstream routers independently learn to throttle traffic towards a victim server. We compare our approach against a baseline and a popular throttling technique from the literature, and we show that our proposed approach is more secure, reliable and cost-effective. Furthermore, our approach outperforms the baseline technique and either outperforms or has the same performance as the popular one. 15:25 Emerging: Scalable Randomized Patrolling for Securing Rapid Transit NetworksSPEAKER: unknownABSTRACT. Mass Rapid Transit using rail is a popular mode of transport employed by millions of people in many urban cities across the world. Typically, these networks are massive and can be a soft target for criminals. In this paper, we consider the problem of scheduling randomised patrols for improved security of rail networks. Similar to existing work in randomised patrols for protecting critical infrastructure, we also employ Stackelberg Games to represent the problem. Towards addressing this problem in massive rail networks, our contributions in this paper are two fold: (1) An approach called RaPtoR for computing randomized strategies in patrol teams, which guarantees (i) Strong Stackelberg equilibrium (SSE); and (ii) Optimality in terms of distance travelled by the patrol teams for certain constraints on schedules. (2) Secondly, we demonstrate this approach on a real world data set corresponding to the rail network in Singapore. Further, we also show that the algorithm scales easily to large rail networks while providing randomized strategies in SSE.
14:45-15:45 Session 16G (EAAI)
 14:45 EAAI-13 Teaching and Mentoring Session 2SPEAKER: unknown
14:45-15:45 Session 16H: Crowdsourcing (AAAI)
 14:45 Better Human Computation Through Principled VotingSPEAKER: unknownABSTRACT. Designers of human computation systems often face the need to aggregate noisy information provided by multiple people. While voting is often used for this purpose, the choice of voting method is typically not principled. We conduct extensive experiments on Amazon Mechanical Turk to better understand how different voting rules perform in practice. We also demonstrate that our empirical conclusions differ from what popular theoretical models would predict. Our short-term goal is to inform the design of better human computation systems; our long-term goal is to spark an interaction between researchers in (computational) social choice and human computation. 15:00 Clustering CrowdsSPEAKER: unknownABSTRACT. Crowdsourcing is often used to create a data set for supervised learning. Because the quality of the data set heavily depends on the abilities of workers, many methods have been proposed to learn a classifier from the data set. From some observations, we notice that workers form clusters according to their abilities. To utilize such knowledge, we propose a method to jointly learn a classifier and clusters of workers from a crowd-generated data set. The proposed method has two advantages. One is that it realizes robust estimation of a classifier because the proposed method utilizes clusters of workers whereas the other methods do not. The other is that we can obtain clusters of workers, which help us analyze the properties of the workers. Experimental results on synthetic and real data sets indicate that the proposed method can estimate a classifier robustly. In addition, clustering workers also works well because an outlier worker was found in the real data set by applying the proposed method. 15:15 The Effects of Performance-Contingent Financial Incentives in Online Labor MarketsSPEAKER: unknownABSTRACT. Online labor markets such as Amazon Mechanical Turk (MTurk) have emerged as platforms that facilitate the allocation of productive effort across global economies. Many of these markets compensate workers with monetary payments. We study the effects of performance-contingent financial rewards on work quality and worker effort in MTurk via two experiments. We find that the magnitude of performance-contingent financial rewards alone affects neither quality nor effort. However, when workers working on two tasks of the same type in a sequence, the change in the magnitude of the reward over the two tasks affects both. In particular, both work quality and worker effort increase (alternatively decrease) as the reward increases (alternatively decreases) for the second task. This suggests the existence of the anchoring effect on workers' perception of incentives in MTurk and that this effect can be leveraged in workflow design to increase the effectiveness of financial incentives. 15:30 Hotspotting --- A Probabilistic Graphical Model For Image Object Localization through CrowdsourcingSPEAKER: unknownABSTRACT. Object localization is an image annotation task which consists of finding the location of a target object in an image. It is common to crowdsource annotation tasks and aggregate responses to estimate the true annotation. While for other kinds of annotations consensus is simple and powerful, it cannot be applied to object localization as effectively due to the task's rich answer space and inherent noise in responses. We propose a probabilistic graphical model to localize objects in images based on responses from the crowd. We improve upon natural aggregation methods such as the mean and the median by simultaneously estimating the difficulty level of each question and skill level of every participant. We empirically evaluate our model on crowdsourced data and show that our method outperforms simple aggregators both in estimating the true locations and in ranking participants by their ability. We also propose a simple adaptive sourcing scheme that works well for very sparse datasets.
15:45-16:15Coffee Break
15:45-16:45 Session 17: LBP/Poster sessions (AAAI)
16:15-16:45 Session 18 (EAAI)
 16:15 EAAI Senior Member Paper: Meeting the Responsibility to Explain AISPEAKER: unknown
16:45-17:45 Session 19A: Matrices (AAAI)
 16:45 Salient Object Detection via Low-rank and Structured Sparse Matrix DecompositionSPEAKER: unknownABSTRACT. Salient object detection provides an alternative solution to various image semantic understanding tasks such as object recognition, adaptive compression and image retrieval. Recently, low-rank matrix recovery (LR) theory has been introduced into saliency detection, and achieves impressed results. However, the existing LR-based models neglect the underlying structure of images, and inevitably degrade the associated performance. In this paper, we propose a Low-rank and Structured sparse Matrix Decomposition (LSMD) model for salient object detection. In the model, a tree-structured sparsity-inducing norm regularization is firstly introduced to provide a hierarchical description of the image structure to ensure the completeness of the extracted salient object. The similarity of saliency values within the salient object is then guaranteed by the $\ell_\infty$-norm. Finally, high-level priors are integrated to guide the matrix decomposition and enhance the saliency detection. Experimental results on the largest public benchmark database show that our model outperforms existing LR-based approaches and other state-of-the-art methods, which verifies the effectiveness and robustness of the structure cues in our model. 17:00 Robust Discrete Matrix CompletionSPEAKER: unknownABSTRACT. Most existing matrix completion methods seek the matrix global structure in the real number domain and produce predictions that are inappropriate for applications retaining discrete structure, where an additional step is required to post-process prediction results with either heuristic threshold parameters or complicated mappings. Such an ad-hoc process is inefficient and impractical. In this paper, we propose a novel robust discrete matrix completion algorithm that produces the prediction from the collection of user specified discrete values by introducing a new discrete constraint to the matrix completion model. Our method achieves a high prediction accuracy, very close to the most optimal value of competitive methods with threshold values tuning. We solve the difficult integer programming problem via incorporating augmented Lagrangian method in an elegant way, which greatly accelerates the converge process of our method and provides the asymptotic convergence in theory. The proposed discrete matrix completion model is applied to solve three real-world applications, and all empirical results demonstrate the effectiveness of our method. 17:15 Rank Aggregation via Low-Rank and Structured-Sparse DecompositionSPEAKER: unknownABSTRACT. Rank aggregation, which combines multiple individual rank lists to obtain a better one, is a fundamental technique in various applications such as meta-search and recommendation systems. Most existing rank aggregation methods blindly combine multiple rank lists with possibly considerable noises, which often degrades their performances. In this paper, we propose a new model for \textit{robust rank aggregation (RRA)} via matrix learning, which recovers a latent rank list from the possibly incomplete and noisy input rank lists. In our model, we construct a pairwise comparison matrix to encode the order information in each input rank list. Based on our observations, each comparison matrix can be naturally decomposed into a shared low-rank matrix, combined with a deviation error matrix which is the sum of a column-sparse matrix and a row-sparse one. The latent rank list can be easily extracted from the learned low-rank matrix. The optimization formulation of RRA has an element-wise multiplication operator to handle missing values, a symmetric constraint on the noise structure, and a factorization trick to restrict the maximum rank of the low-rank matrix. To solve this challenging optimization problem, we propose a novel procedure based on the Augmented Lagrangian Multiplier scheme. We conduct extensive experiments on meta-search and collaborative filtering benchmark datasets. The results show that the proposed RRA has superior performance gain over several state-of-the-art algorithms for rank aggregation.
16:45-17:45 Session 19B: Options/Pricing (AAAI)
 16:45 Strategic Behavior when Allocating Indivisible Goods SequentiallySPEAKER: unknownABSTRACT. We study a simple sequential allocation mechanism for allocating indivisible goods between agents where agents take turns to pick items. We focus on computational aspects of agents behaving strategically. We view the allocation procedure as a ﬁnite repeated game with perfect information. We show that with just two agents, we can compute the unique subgame perfect Nash equilibrium in linear time. With more agents, computing one or all of the subgame perfect Nash equilibria is more difﬁcult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard in general. We identify a special case, when agents value many of the items identically, where we can efﬁciently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modiﬁcations to the mechanism that make it strategy proof. 17:00 Posted Prices Exchange for Display Advertising ContractsSPEAKER: unknownABSTRACT. We propose a new market design for display advertising contracts, based on posted prices. This requires overcoming major challenges: (i) the space of possible impression types is exponential in the number of attributes, which is typically large; therefore a complete price space cannot be maintained; (ii) the level of detail with which supply and demand are specified are often not identical, (iii) advertisers are usually unable to provide extensive demand (willingness-to-pay) functions. 17:15 AAAI-13 Outstanding Paper, Honorable Mention: On the Value of Using Group Discounts under Price CompetitionSPEAKER: unknownABSTRACT. The increasing use of group discounts has provided opportunities for buying groups with diverse preferences to coordinate their behavior in order to exploit the best offers from multiple vendors. We analyze this problem from the viewpoint of the vendors, asking under what conditions a vendor should adopt a volume-based price schedule rather than posting a fixed price, either as a monopolist or when competing with other vendors. When vendors have uncertainty about buyers' valuations specified by a known distribution, we show that a vendor is always better off posting a fixed price, provided that buyers' types are i.i.d. and other vendors also use fixed prices. We also show that these assumptions cannot be relaxed: if buyers are not i.i.d., or other vendors post discount schedules, then posting a schedule may yield higher profit for the vendor. We provide similar results under a distribution-free uncertainty model, where vendors try to minimize their maximum regret over all type realizations. 17:30 The Cascade Auction – A Mechanism for Deterring Collusion in AuctionsSPEAKER: unknownABSTRACT. We introduce a sealed bid auction of a single item in which the winner is chosen at random among the highest k bidders according to a fixed probability distribution, and the price for the chosen winner is the Vickrey-Clarke-Groves price. We call such an auction a cascade auction. Our analysis suggests that this type of auction may give higher revenues compared to second price auction in cases of collusion.
16:45-17:45 Session 19C: Search (AAAI)
 16:45 Robust Bidirectional Search via Heuristic ImprovementSPEAKER: unknownABSTRACT. Although the heuristic search algorithm A* is well-known to be optimally efficient, this result explicitly assumes forward search. Bidirectional search has long held promise for surpassing A*'s efficiency, and many varieties have been proposed, but it has proven difficult to achieve robust performance across multiple domains in practice. We introduce a simple bidirectional search algorithm called Auto-Tuning A* that judiciously performs backward search to improve the accuracy of the forward heuristic function. We assess its theoretical properties and empirically evaluate its performance across seven benchmark domains. In the best case, it yields a factor of six reduction in node expansions and CPU time compared to A*, and in the worst case, its overhead is provably bounded by a user-supplied parameter, such as 1\%. Viewing performance across all domains, it also surpasses previously proposed bidirectional search algorithms. These results indicate that Auto-Tuning A* is robust way to leverage bidirectional search in practice. 17:00 External Memory Best-First Search for Multiple Sequence AlignmentSPEAKER: unknownABSTRACT. Multiple sequence alignment (MSA) is a central problem in computational biology. It is well known that MSA can be formulated as a shortest path problem and solved using heuristic search, but the memory requirement of A* makes it impractical for all but the smallest problems. Partial Expansion A* (PEA*) reduces the space complexity of A* by generating only the most promising successor nodes. However, even PEA* exhausts available memory on many problems. Another alternative is Iterative Deepening Dynamic Programming, which uses an uninformed search order but stores only the nodes along the search frontier. However, it too cannot scale to the largest problems. In this paper, we propose storing nodes on cheap and plentiful secondary storage. We present a new general-purpose algorithm, Parallel External PEA* (PE2A*), that combines PEA* with Delayed Duplicate Detection to take advantage of external memory and multiple processors to solve large MSA problems. In our experiments, PE2A* is the first algorithm capable of solving the entire Reference Set 1 of the standard BaliBASE benchmark using a biologically accurate cost function. This work suggests that external best-first search can effectively use heuristic information to surpass methods that rely on predefined search orders. 17:15 AAAI-13 Outstanding Paper Award: HC-Search: Learning Heuristics and Cost Functions for Structured PredictionSPEAKER: unknownABSTRACT. Structured prediction is the problem of learning a function from structured inputs to structured outputs with prototypical examples being part-of-speech tagging and image labeling. Inspired by the recent successes of search-based structured prediction, we introduce a new framework for structured prediction called {\em HC-Search}. Given a structured input, the framework uses a search procedure guided by a learned heuristic H to uncover high quality candidate outputs and then uses a separate learned cost function C to select a final prediction among those outputs. We can decompose the regret of the overall approach into the loss due to H not leading to high quality outputs, and the loss due to C not selecting the best among the generated outputs. Guided by this decomposition, we minimize the overall regret in a greedy stage-wise manner by first training H to quickly uncover high quality outputs via imitation learning, and then training C to correctly rank the outputs generated via H according to their true losses. Experiments on several benchmark domains show that our approach significantly outperforms the state-of-the-art methods. 17:30 Goal-Oriented Euclidean Heuristics with Manifold LearningSPEAKER: unknownABSTRACT. Recently, a Euclidean heuristic (EH) has been proposed for A* search. EH exploits manifold learning methods to construct an embedding of the state space graph, and derives an admissible heuristic distance between two states from the Euclidean distance between their respective embedded points. EH has shown good performance and memory efficiency in comparison to other existing heuristics such as differential heuristics. However, its potential has not been fully explored. In this paper, we propose a number of techniques that can significantly improve the quality of EH. We propose a goal-oriented manifold learning scheme that optimizes the Euclidean distance to goals in the embedding while maintaining admissibility and consistency. We also propose a state heuristic enhancement technique to reduce the gap between heuristic and true distances. The enhanced heuristic is admissible but no longer consistent. We then employ a modified search algorithm that achieves optimality with inconsistent heuristics using consistency check and propagation. We demonstrate the effectiveness of the above techniques and report un-matched reduction in search costs across several non-trivial benchmark search problems.
16:45-17:45 Session 19D: Logic and Answer Set Programming (AAAI)
 16:45 A General Formal Framework for Pathfinding Problems with Multiple AgentsSPEAKER: Peter SchüllerABSTRACT. Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, going around obstacles. Pathfinding for multiple agents also aims to plan such routes for each agent, subject to different constraints, such as restrictions on the length of each path or on the total length of paths, no self-intersecting paths, no intersection of paths/plans, no crossing/meeting each other. It also has variations for finding optimal solutions, e.g., with respect to the maximum path length, the sum of plan lengths. These problems are important for many real-life applications, such as motion planning, vehicle routing, environmental monitoring, patrolling, computer games. Motivated by such applications, we introduce a formal framework that is general enough to address all these problems: we use the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming. We also introduce heuristics to improve the computational efficiency and/or solution quality. We show the applicability and usefulness of our framework by experiments, with randomly generated problem instances on a grid, on a real-world road network, and on a real computer game terrain. 17:00 Multi-Cycle Query Caching in Agent ProgrammingSPEAKER: unknownABSTRACT. In many logic-based BDI agent programming languages, plan selection involves inferencing over some underlying knowledge representation. While context-sensitive plan selection facilitates the development of flexible, declarative programs, the overhead of evaluating repeated queries to the agent's beliefs and goals can result in poor run time performance. In this paper we present an approach to multi-cycle query caching for logic-based BDI agent programming languages. We extend the abstract performance model presented in (Alechina et al 2012) to quantify the costs and benefits of caching query results over multiple deliberation cycles. We also present results of experiments with prototype implementations of both single- and multi-cycle caching in three logic-based BDI agent platforms, which demonstrate that significant performance improvements are achievable in practice. 17:15 Liberal Safety for Answer Set Programs with External SourcesSPEAKER: unknownABSTRACT. Answer set programs with external source access may introduce new constants that are not present in the program, which is known as value invention. As naive value invention leads to programs with infinite grounding and answer sets, syntactic safety criteria are imposed on programs. However, traditional criteria are in many cases unnecessarily strong and limit expressiveness. We present liberal domain-expansion (de-) safe programs, a novel generic class of answer set programs with external source access that has a finite grounding and allows for value invention. De-safe programs use so-called term bounding functions as a parameter for modular instantiation with concrete---e.g., syntactic or semantic or both---safety criteria. This ensures extensibility of the approach in the future. We provide concrete instances of the framework and develop an operator that can be used for computing a finite grounding. Finally, we discuss related notions of safety from the literature, and show that our approach is strictly more expressive. 17:30 Domain-Specific Heuristics in Answer Set ProgrammingSPEAKER: unknownABSTRACT. We introduce a general declarative framework for incorporating domain-specific heuristics into ASP solving. We accomplish this by extending the first-order modeling language of ASP by a distinguished heuristic predicate. The resulting heuristic information is processed as an equitable part of the logic program and subsequently exploited by the solver when it comes to non-deterministically assigning a truth value to an atom. We implemented our approach as a dedicated heuristic in the ASP solver clasp and show its great prospect by an empirical evaluation.
16:45-17:45 Session 19E: Learning from the Web (AAAI)
 16:45 Fast Algorithm for Modularity-based Graph ClusteringSPEAKER: unknownABSTRACT. In AI and the Web communities, modularity-based graph clustering algorithms have been applied to various applications. However, existing algorithms are not applied to large graphs because they have to scan all vertices/edges iteratively. The goal of this paper is to efficiently compute clusters with high modularity from unprecedented size of graphs that have over a few billion edges. The heart of our solution is to compute clusters from large graphs by incrementally pruning unnecessary vertices/edges and dynamically selecting vertices which provide efficient data accesses. Our experiments shows that our proposal outperforms all other modularity-based algorithms in terms of computation time, and it finds clusters with high modularity. To the best of our knowledge, our algorithm is the first solution to extract clusters from graphs of unprecedented size, that have more than 100 million vertices and 1 billion edges, in a few minutes. 17:00 Exploring the Contribution of Unlabeled Data in Financial Sentiment AnalysisSPEAKER: unknownABSTRACT. With the proliferation of its applications in various industries, sentiment analysis by using publicly available web data has become an active research area in text classification during these years. It is argued by researchers that semi-supervised learning is an effective approach to this problem since it is capable to mitigate the manual labeling effort which is usually expensive and time-consuming. However, there was a long-term debate on the effectiveness of unlabeled data in text classification. This was partially caused by the fact that many assumptions in theoretic analysis often do not hold in practice. We argue that this problem may be further understood by adding an additional dimension in the experiment. This allows us to address this problem in the perspective of bias and variance in a broader view. We show that the well-known performance degradation issue caused by unlabeled data can be reproduced as a subset of the whole scenario. We argue that if the bias-variance trade-off is to be better balanced by a more effective feature selection method unlabeled data is very likely to boost the classification performance. We then propose a feature selection framework in which labeled and unlabeled training samples are both considered. We discuss its potential in achieving such a balance. Besides, the application in financial sentiment analysis is chosen because it not only exemplifies an important application, the data possesses better illustrative power as well. The implications of this study in text classification and financial sentiment analysis are both discussed. 17:15 Learning to Rank Effective Paraphrases from Query Logs for Community Question AnsweringSPEAKER: unknownABSTRACT. We present a novel method for ranking query paraphrases for effective search in community question answering (cQA) services like Yahoo! Answers. The method uses query logs from a commercial search engine and a cQA archive for automatically extracting a corpus of paraphrases of queries and questions using the query-question click history. Elements of this corpus are automatically ranked according to recall and mean reciprocal rank, and then used for learning two independent learning to rank models (SVMRank), whereby a set of new query paraphrases can be scored according to recall and MRR. We perform several automatic evaluation procedures using cross-validation for analyzing the behavior of various aspects of our learned ranking functions, which show that our method is useful and effective for search in cQA. 17:30 OpenEval: Web Information Query EvaluationSPEAKER: unknownABSTRACT. In this paper, we investigate information extraction tasks that are initiated as queries from either automated agents or humans. We introduce OpenEval, a new online information extraction technique which uses information on the web to automatically evaluate the truth of propositions that are stated as multi-argument predicate instances (e.g., LocationHasObject(Kitchen, Coffee)). OpenEval gets a small number of instances of a predicate as seed positive examples and automatically learns how to evaluate the truth of a new predicate instance by querying the web and processing the retrieved unstructured Web pages. We show that OpenEval is able to respond to the queries within a limited amount of time while also achieving high F1 score. In addition, we show that the accuracy of responses provided by OpenEval is increased as more time is given for evaluation. We have extensively tested our model and shown empirical results that illustrate the effectiveness of our approach compared to related techniques.
16:45-17:45 Session 19F: Spotlights and Senior Members (AAAI)
 16:45 Symbiotic-Autonomous Intelligent RobotsSPEAKER: Manuela VelosoABSTRACT. In this presentation, we will contribute the research and development we successfully pursue on effective mobile intelligent robots that service users in multiple different tasks. We overview the multiple aspects of our intelligent mobile CoBot robots that have been autonomously acting in our multi-floor environment, navigating so far for more than 200km. Users request tasks from CoBot using a web-based interface, and CoBot plans, localizes, and autonomously navigates between floors of the building. More importantly, the CoBot robot recognizes its perceptual, cognitive, and actuation limitations, and is capable to proactively ask for help or check the web, in a {\it symbiotic} relationship with humans and the web. We present the details of such challenging deployment, in particular the effective real-time depth-camera based localization and navigation algorithms, the symbiotic human-robot interaction approach, the multi-task dynamic planning and scheduling algorithm, the safety execution, the exploration and learning from the web. We show multiple illustrations of the robot performance, including a comprehensive analysis of extensive deployment results. 17:15 RuleML: What's HotSPEAKER: unknownABSTRACT. methods for automated translation between business and legal regulation written in natural language, and formal rules; papers on methods for visualization of formal rules; and integration of machine learning techniques and methods for reasoning with formal rules. 17:30 RuleML: Computing the Stratified Well-Founded Semantics over Big Data through Mass ParallelizationSPEAKER: Ilias TachmazidisABSTRACT. Increasingly huge amounts of data are published on the Web, and generated from sensors and social media. This Big Data challenge poses new scientific and technological challenges and create new opportunities - thus the increasing attention in academia and industry. Traditionally, logic programming has focused on complex knowledge structures/programs, so the question arises whether and how it can work in the face of Big Data. In this paper, we examine how logic programming, under the well-founded semantics, can process huge amounts of data through mass parallelization. In particular, we propose and evaluate a parallel approach, using the MapReduce framework, under the assumption of stratification. Our experimental results indicate that our approach is scalable and that well-founded semantics can be applied to billions of facts.
16:45-17:55 Session 19G: Constraint-Based Scheduling (IAAI)
 16:45 Deployed: The Deployment of a Constraint-Based Dental School Timetabling SystemSPEAKER: unknownABSTRACT. We describe a constraint-based timetabling system that was developed for the dental school based at Cork University Hospital in Ireland. This system has been deployed since 2010. Dental school timetabling differs from other university course scheduling in that certain clinic sessions can be used by multiple courses at the same time, provided a limit on room capacity is satisfied. Starting from a constraint programming solution using a web interface, we have moved to a mixed integer programming-based solver to deal with multiple objective functions, along with a dedicated Java application, which provides a rich user interface. Solutions for the years 2010, 2011 and 2012 have been used in the dental school, replacing a manual timetabling process, which could no longer cope with increasing student numbers and resulting resource bottlenecks. The use of the automated system allowed the dental school to increase student numbers to the maximum possible given the available resources. It also provides the school with a valuable "what-if" analysis tool. 17:15 Emerging: Train Outstable Scheduling as Constraint SatisfactionSPEAKER: unknownABSTRACT. This paper outlines the design of a constraint satisfaction problem (CSP) scheduling algorithm that allocates outstabling locations to railway trains. From time to time railway trains may need to be outstabled to temporary locations, such as stations, sidings, depots, etc., until they are needed for regular operations. This is common for urban rail transit, and especially so for those that do not operate 24 hours. During non-traffic hours (NTH), trains are outstabled to various locations along the rail network so that when operations start again next day, the trains will be nearby their originating station or conveniently located so that they can be put into service whenever needed. This is the case for Hong Kong. However, this is complicated by the fact that engineering works, such as rail testing, installation, regular maintenance, etc. are all done during the NTH. Therefore, the outstabling algorithm must allocate passenger trains in such a way that they do not interfere with night-time engineering works and the movements of associated engineering trains. This paper shows how we modeled the outstabling problem as a constraint-satisfaction problem and implemented into an ìOutstabling Systemî (OSS) for MTR. 17:35 Emerging: Balancing the Traveling Tournament Problem for Weekday and Weekend GamesSPEAKER: unknownABSTRACT. The Traveling Tournament Problem (TTP) is a complex problem in sports scheduling, involving constraint programming to create a schedule of home and away games that meet the feasibility requirements, as well as integer programming to minimize total travel. In this paper, we tackle the TTP from a graph-theoretic perspective, by generating a "canonical" schedule in which each team's three-game road trips match up with the underlying graph's minimum-weight P_3-packing. We apply this canonical schedule to produce a new TTP approximation algorithm, and generate solutions for the three-dimensional n-team Galaxy benchmark data set, producing feasible tournaments for n \in {22, 28, 34, 40} that beat all previously-known solutions.
16:45-17:45 Session 19H (EAAI)
 16:45 EAAI-13 Discussion of Big Ideas in Education and AISPEAKER: unknown
16:45-17:45 Session 19I: AAAI-13 Invited Panel: Funding (AAAI)
 16:45 Funding Panel: NSF ProgramsSPEAKER: unknownABSTRACT. Representatives from NSF will discuss NSF programs of interest to Artificial Intelligence researchers, and provide advice on finding funding in economically challenging times. Topics during the subsequent question and answer session could include the following: recent NSF initiatives, advice for young investigators, funding for educational initiatives, summer schools, interdisciplinary research and international research collaborations, ways of achieving broader impacts, and current proposal acceptance rates.
17:45-19:30 Session 20: Evening poster session (AAAI)
 17:45 Evening poster sessionSPEAKER: unknownABSTRACT. Reception/poster session including the Student Abstracts, Intern Posters, DC Abstracts, Poker Posters and EAAI posters.
20:00-22:00 Session 21: AAAI Puzzle Hunt (AAAI)