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

PROGRAM FOR WEDNESDAY, JULY 17TH, 2013

Days:
previous day
next day
all days

View: session overviewtalk overviewside by side with other conferences

09:00-10:00 Session 22: Invited talk: Bennett (AAAI)
09:00
AAAI-13 Invited Talk: Fighting the Tuberculosis Pandemic Using Machine Learning

ABSTRACT. Tuberculosis (TB) infects one third of the world's population and is the second leading cause of death from a single infectious agent worldwide. The emergence of drug resistant TB remains a constant threat. We examine how machine learning methods can help control tuberculosis. DNA fingerprints of Mycobacterium tuberculosis complex bacteria (Mtb) are routinely gathered from TB patient isolates for every tuberculosis patient in the United States to support TB tracking and control efforts. We develop learning models to predict the genetic lineages of Mtb based on DNA fingerprints. Mining of tuberculosis patient surveillance data with respect to these genetic lineages helps discover outbreaks, improve TB control, and reveal Mtb phenotype differences. We discuss learning- and visualization-based tools to support public health efforts towards TB control in development for the New York City Health Department.

10:00-10:20Coffee Break
10:20-11:20 Session 23A: AI in Science (AAAI)
10:20
Mixed Heuristic Local Search for Protein Structure Prediction
SPEAKER: unknown

ABSTRACT. Protein structure prediction is an unsolved problem in computational biology. One great difficulty is due to the unknown factors in the actual energy function. Moreover, the energy models available are often not very informative particularly when spatially similar structures are compared during search. We introduce several novel heuristics to augment the energy model and present a new local search algorithm that exploits these heuristics in a mixed fashion. Although the heuristics individually are weaker in performance than the energy function, their combination interestingly produces stronger results. For standard benchmark proteins on the face centered cubic lattice and a realistic 20x20 energy model, we obtain structures with significantly lower energy than those obtained by the state-of-the-art algorithms. We also report results for these proteins using the same energy model on the cubic lattice.

10:35
Ranking Scientific Articles by Exploiting Citations, Authors, Journals and Time Information
SPEAKER: Yujing Wang

ABSTRACT. Ranking scientific articles is an important but challenging task, partly due to the dynamic nature of the evolving publication network. In this paper, we mainly focus on two problems: (1) how to rank articles in the heterogeneous network; and (2) how to use time information in the dynamic network in order to obtain a better ranking result. To tackle the problems, we propose a graph-based ranking method, which utilizes citations, authors, journals/conferences and the publication time information collaboratively. The experiments were carried out on two public datasets. The result shows that our approach is practical and ranks scientific articles more accurately than the state-of-art methods.

10:50
A Morphogenetically Assisted Design Variation Tool
SPEAKER: Aaron Adler

ABSTRACT. The complexity and tight integration of electromechanical systems often makes them "brittle" and hard to modify in response to changing requirements. We aim to remedy this by capturing expert knowledge as functional blueprints, an idea inspired by regulatory processes that occur in natural morphogenesis. We then apply this knowledge in an intelligent design variation tool. When a user modifies a design, our tool uses functional blueprints to modify other components in response, thereby maintaining integration and reducing the need for costly search or constraint solving. In this paper, we refine the functional blueprint concept and discuss practical issues in applying it to electromechanical systems. We then validate our approach with a case study applying our prototype tool to create variants of a miniDroid robot and by empirical evaluation of convergence dynamics of networks of functional blueprints.

11:05
Guiding Scientific Discovery with Explanations Using DEMUD
SPEAKER: Kiri Wagstaff

ABSTRACT. In the era of large scientific data sets, there is an urgent need for methods to automatically prioritize data for review. At the same time, for any automated method to be adopted by scientists, it must make decisions that they can understand and trust. In this paper, we propose Discovery through Eigenbasis Modeling of Uninteresting Data (DEMUD), which uses principal components modeling and reconstruction error to prioritize data. DEMUD’s major advance is to offer domain-specific explanations for its prioritizations. We evaluated DEMUD’s ability to quickly identify diverse items of interest and the value of the explanations it provides. We found that DEMUD performs as well or better than existing class discovery methods and provides, uniquely, the first explanations for why those items are of interest. Further, in collaborations with planetary scientists, we found that DEMUD (1) quickly identifies very rare items of scientific value, (2) maintains high diversity in its selections, and (3) provides explanations that greatly improve human classification accuracy.

10:20-11:20 Session 23B: Nearest Neighbors and Hierarchical Clustering (AAAI)
10:20
Discovering Hierarchical Structure for Sources and Entities
SPEAKER: unknown

ABSTRACT. In this paper, we consider the problem of jointly learning hierarchies over a set of sources and entities based on their containment relationship. We model the concept of hierarchy using a set of latent binary features and propose a generative model that assigns those latent features to sources and entities in order to maximize the probability of the observed containment. To avoid fixing the number of features beforehand, we consider a non-parametric approach based on the Indian Buffet Process. The hierarchies produced by our algorithm can be used for completing missing associations and discovering structural bindings in the data. Using simulated and real datasets we provide empirical evidence of the effectiveness of the proposed approach in comparison to the existing hierarchy agnostic approaches.

10:35
Walking on Minimax Paths for k-NN Search
SPEAKER: unknown

ABSTRACT. Link-based dissimilarity measures, such as shortest path or Euclidean commute time distance, base their distance on paths between nodes of a weighted graph. These measures are known to be better suited to data manifold with nonconvex-shaped clusters, compared to Euclidean distance, so that k-nearest neighbor (NN) search is improved in such metric spaces. In this paper we present a new link-based dissimilarity measure based on minimax paths between nodes. Two main benefits of minimax path-based dissimilarity measure are: (1) only a subset of paths is considered to make it scalable, while Euclidean commute time distance considers all possible paths; (2) it better captures nonconvex-shaped cluster structure, compared to shortest path distance. We define the total cost assigned to a path between nodes as L_p norm of intermediate costs of edges involving the path, showing that minimax path emerges from our L_p norm over paths framework. We also define minimax distance as the intermediate cost of the longest edge on the minimax path, then present a greedy algorithm to compute k smallest minimax distances between a query and N data points in O(log N + klog k) time. Numerical experiments demonstrate that our minimax k-NN algorithm reduce the search time by several orders of magnitude, compared to existing methods, while the quality of k-NN search is significantly improved over Euclidean distance.

10:50
Formalizing Hierarchical Clustering as Integer Linear Programming
SPEAKER: unknown

ABSTRACT. Hierarchical clustering is typically implemented as a greedy heuristic algorithm with no explicit objective function. In this work we formalize hierarchical clustering as an integer linear programming (ILP) problem with a natural objective function and the dendrogram properties enforced as linear constraints. Though exact solvers exists for ILP we show that a simple randomized algorithm and a linear programming (LP) relaxation can be used to provide approximate solutions faster. Formalizing hierarchical clustering also has the benefit that relaxing the constraints can produce novel problem variations such as overlapping clusterings. Our experiments show that our formulation is capable of outperforming standard agglomerative clustering algorithms in a variety of settings, including traditional hierarchical clustering as well as learning overlapping clusterings.

11:05
Reciprocal Hash Tables for Nearest Neighbor Search
SPEAKER: unknown

ABSTRACT. Recent years have witnessed the success of hashing techniques in approximate nearest neighbor search. In practice, multiple hash tables are usually employed to retrieve more desired results from all hit buckets of each table. However, there are rare works studying the unified approach to constructing multiple informative hash tables except the widely used random way. In this paper, we regard the table construction as a selection problem over a set of candidate hash functions. With the graph representation of the function set, we propose an efficient solution that sequentially applies normalized dominant set to finding the most informative and independent hash functions for each table. To further reduce the redundancy between tables, we explore the reciprocal hash tables in a boosting manner, where the hash function graph is updated with high weights emphasized on the misclassified neighbor pairs of previous hash tables. The construction method is general and compatible with different types of hashing algorithms using different feature spaces and/or parameter settings. Extensive experiments on two large-scale benchmarks demonstrate that the proposed method outperforms both naive construction method and state-of-the-art hashing algorithms, with up to 65.93% accuracy gains.

10:20-11:20 Session 23C: Teamwork (AAAI)
10:20
Cost-Optimal Planning by Self-Interested Agents
SPEAKER: unknown

ABSTRACT. As our world becomes better connected, more open ended, production becomes more customized, and autonomous agents no longer appear to be science fiction, a natural need arises for enabling groups of selfish agents to cooperate in generating a plan for diverse tasks that none of them can perform alone in a cost-effective manner. While most work on planning for/by selfish agents revolves around finding stable solutions (e.g., Nash Equilibrium), this work combines techniques from mechanism design with a recently introduced method for distributed planning, in order to find cost optimal (and, thus, social welfare maximizing) solutions. Based on the Vickrey-Clarke-Groves mechanisms, we present both a centralized, and a privacy-preserving distributed mechanism.

10:35
Teamwork with Limited Knowledge of Teammates
SPEAKER: unknown

ABSTRACT. While great strides have been made in multiagent teamwork, existing approaches typically assume extensive information exists about teammates and how to coordinate actions. This paper addresses how robust teamwork can still be created even if limited or no information exists about a specific group of teammates, as in the ad hoc teamwork scenario. The main contribution of this paper is the first empirical evaluation of an agent cooperating with teammates not created by the authors, where the agent is not provided expert knowledge of its teammates. For this purpose, we develop a general-purpose teammate modeling method and test the resulting ad hoc team agent's ability to collaborate with more than 40 unknown teams of agents to accomplish a benchmark task. These agents were designed by people other than the authors without these designers planning for the ad hoc teamwork setting. A secondary contribution of the paper is a new transfer learning algorithm, TwoStageTransfer, that can improve results when the ad hoc team agent does have some limited observations of its current teammates.

10:50
Composition Games for Distributed Systems: The EU Grant Games
SPEAKER: unknown

ABSTRACT. We analyze ways by which people decompose into groups in distributed systems. We are interested in systems in which an agent can increase its utility by connecting to other agents, but must also pay a cost that increases with the size of the system. The right balance is achieved by the right size group of agents. We formulate and analyze three intuitive and realistic games and show how simple changes in the protocol can drastically improve the price of anarchy of these games. In particular, we identify two important properties for a low price of anarchy: agreement in joining the system, and the possibility of appealing a rejection from a system. We show that the latter property is especially important if there are some preexisting constraints regarding who may collaborate (or communicate) with whom.

11:05
Information Sharing Under Costly Communication in Joint Exploration
SPEAKER: unknown

ABSTRACT. This paper studies distributed cooperative multi-agent exploration methods in settings where the exploration is costly and the overall performance measure is determined by the minimum performance achieved by any of the individual agents. Such an exploration setting is applicable to various multi-agent systems, e.g., in Dynamic Spectrum Access exploration. The goal in such problems is to optimize the process as a whole, considering the tradeoffs between the quality of the solution obtained and the cost associated with the exploration and coordination between the agents. Through the analysis of the two extreme cases where coordination is completely free and when entirely disabled, we manage to extract the solution for the general case where coordination is taken to be costly, modeled as a fee that needs to be paid for each additional coordinated agent. The strategy structure for the general case is shown to be threshold-based, and the thresholds which are analytically derived in this paper can be calculated offline, resulting in a very low online computational load. Finally, we analyze the case where the coordination is provided by a self-interested agent, showing that given the option for side-payments better socially-beneficial solutions can be extracted.

10:20-11:20 Session 23D: Robot Motion Planning (AAAI)
10:20
Robot Motion Planning with Dynamics as Hybrid Search
SPEAKER: Erion Plaku

ABSTRACT. This paper presents a general framework for motion planning with dynamics as hybrid search over the continuous space of feasible motions and the discrete space of a low-dimensional decomposition. Each step of the hybrid search consists of expanding a frontier of regions in the discrete space using cost heuristics as guide followed by sampling-based motion planning to expand a tree of feasible motions in the continuous space to reach the frontier. Comparisons to related work show significant computational speedups.

10:35
GSMDPs for Multi-Robot Sequential Decision-Making
SPEAKER: unknown

ABSTRACT. Markov Decision Processes (MDPs) provide an extensive theoretical background for problems of decision-making under uncertainty. In order to maintain computational tractability, however, real-world problems are typically discretized in states and actions as well as in time. Assuming synchronous state transitions and actions at fixed rates may result in models which are not strictly Markovian, or where agents are forced to idle between actions, losing their ability to react to sudden changes in the environment. In this work, we explore the application of Generalized Semi-Markov Decision Processes (GSMDPs) to a realistic multi-robot scenario. A case study will be presented in the domain of cooperative robotics, where real-time reactivity must be preserved, and therefore synchronous discrete-time approaches are sub-optimal. This case study is tested on a team of real robots, and also in realistic simulation. By allowing asynchronous events to be modeled over continuous time, the GSMDP approach is shown to provide greater solution quality than its discrete-time counterparts, while still being approximately solvable by existing methods.

10:50
A Simple, But NP-Hard, Motion Planning Problem
SPEAKER: unknown

ABSTRACT. Determining the existence of a collision-free path between two points is one of the most fundamental questions in robotics. However, in situations where crossing an obstacle is costly but not impossible, it may be more appropriate to ask for the path that crosses the fewest obstacles. This may arise in both autonomous outdoor navigation (where the obstacles are rough but not completely impassable terrain) or indoor navigation (where the obstacles are doors that can be opened if necessary). This problem, the minimum constraint removal problem, is at least as hard as the underlying path existence problem. In this paper, we demonstrate that the minimum constraint removal problem is NP-hard for navigation in the plane even when the obstacles are all convex, a case where the path existence problem is very easy.

11:05
Structure and Intractability of Optimal Multi-robot Path Planning on Graphs
SPEAKER: unknown

ABSTRACT. In this paper, we study the structure and computational complexity of optimal multi-robot path planning problems on graphs. Our results encompass three formulations of the discrete multi-robot path planning problem, including a variant that allows synchronous rotations of robots along fully occupied, disjoint cycles on the graph. Allowing rotation of robots provides a more natural model for multi-robot path planning because robots can communicate.

The optimality objectives that we study are total arrival time, makespan (last arrival time), and total distance. On the structure side, we show that, when there are two or more unoccupied vertices, these objectives demonstrate a pairwise Pareto optimal structure and cannot be simultaneously optimized. On the computational complexity side, we extend previous work and show that, regardless of the underlying multi-robot path planning problem, these objectives are all intractable to compute. In particular, our NP-hardness proof for the time optimal versions, based on a simple and direct reduction from the 3-satisfiability problem, shows that these problems remain NP-hard even when there are only two groups of robots (i.e. robots within each group are interchangeable).

10:20-11:20 Session 23E: Spotlights and Senior Members (AAAI)
10:20
A filtering algorithm for constraints of difference in CSPs
SPEAKER: unknown

ABSTRACT. Classic Paper Award from 1994.

10:35
Acting Optimally in Partially Observable Stochastic Domains
SPEAKER: unknown

ABSTRACT. Classic Paper Award from 1994.

10:50
Decision-Making in Open Mixed Networks
SPEAKER: Kobi Gal

ABSTRACT. Computer systems are increasingly being deployed in group settings in which they interact with people as well as with other computer agents. We refer to these heterogeneous groups of people and computer agents as ``open mixed networks'' to reflect the inclusion of people, the distributed nature of agents in the group (designed by or representing different people and organizations) and the network-like relationships that connect all of the participants in their endeavours. Despite the growing prevalence of mixed networks, the design of agents that perform well in these networks has received less attention than the design of agents for settings comprising solely computer agents. It has been shown that results obtained in such homogeneous computational settings may not hold once people are ``in the loop''. To meet the challenges associated with agent-design for open-mixed networks a new research focus in AI is required. My proposed talk will present advances and lay out the challenges in this newly emerging area focusing on three research directions. (1) Reasoning and representing social and psychological factors; (2) Factored representations and learning from sparse data; (3) Novel empirical frameworks and methodologies.

10:20-11:20 Session 23F: IAAI-13 Invited Talk (IAAI)
10:20
IAAI-13 Invited Talk: An Open-World Iterative Methodology for the Development and Evaluation of Semantically-enabled Applications
SPEAKER: unknown

ABSTRACT. As access to Earth and space science data and information became routine, efforts moved beyond their discipline, and vocabulary challenges arose; some were quite esoteric and jargon laden. As we understood the requirements, we chose a technology foundation that was based on a long history of artificial intelligence (AI) research set in the context of the modern world-wide-web (WWW) environment because of the promise for a declarative, extensible, re-usable platform. We developed and implemented the semantic methodology throughout the effort and found that it provided consistency as we met user requirements. While individual technology components might change, this did not affect our ability to deliver a capability that was useful and usable, especially by a broad range of people, some of whom will not be trained in all areas of science covered in the collection.

10:20-11:20 Session 23G: Language Processing (AAAI)
10:20
AAAI-13 Outstanding Paper, Honorable Mention: Effective Bilingual Constraints for Semi-supervised Learning of Named Entity Recognizers
SPEAKER: Mengqiu Wang

ABSTRACT. Most semi-supervised methods in Natural Language Processing capitalize on unannotated resources in a single language; however, information can be gained from using parallel resources in more than one language, since translations of the same utterance in different languages can help to disambiguate each other. We demonstrate a method that makes effective use of vast amounts of bilingual text (a.k.a. bitext) to improve monolingual systems. We propose a factored probabilistic sequence model that encourages both crosslanguage and intra-document consistency. A simple Gibbs sampling algorithm is introduced for performing approximate inference. Experiments on English-Chinese Named Entity Recognition (NER) using the OntoNotes dataset demonstrate that our method is significantly more accurate than state-of-the-art monolingual CRF models in a bilingual test setting. Our model also improves on previous work by Burkett et al. (2010), achieving a relative error reduction of 10.8% and 4.5% in Chinese and English, respectively. Furthermore, by annotating a moderate amount of unlabeled bi-text with our bilingual model, and using the tagged data for uptraining, we achieve a 9.2% error reduction in Chinese over the state-of-the-art Stanford monolingual NER system.

10:35
Grounding Natural Language References to Unvisited and Hypothetical Location
SPEAKER: unknown

ABSTRACT. While much research exists on resolving spatial natural language references to known locations, little work deals with handling references to unknown locations. In this paper we introduce and evaluate algorithms integrated into a cognitive architecture which allow an agent to learn about its environment while resolving references to both known and unknown locations. We also describe how multiple components jointly facilitate these capabilities.

10:50
An Extended GHKM Algorithm for Inducing Lambda-SCFG
SPEAKER: Peng Li

ABSTRACT. Semantic parsing, which aims at mapping a natural language (NL) sentence into its formal meaning representation (e.g., logical form), has received increasing attention in recent years. While synchronous context-free grammar (SCFG) augmented with lambda calculus (lambda-SCFG) provides an effective mechanism for semantic parsing, how to learn such lambda-SCFG rules still remains a challenge because of the difficulty in determining the correspondence between NL sentences and logical forms. To alleviate this structural divergence problem, we extend the GHKM algorithm, which is a state-of-the-art algorithm for learning synchronous grammars in statistical machine translation, to induce lambda-SCFG from pairs of NL sentences and logical forms. By treating logical forms as trees, we reformulate the theory behind GHKM that gives formal semantics to the alignment between NL words and logical form tokens. Experiments on the GEOQUERY dataset show that our semantic parser achieves an F-measure of 90.2%, the best result published to date.

11:05
Automatic Identification of Conceptual Metaphors With Limited Knowledge
SPEAKER: unknown

ABSTRACT. Complete natural language understanding requires identifying and analyzing the meanings of metaphors, which are ubiquitous in text and speech. Underlying metaphors in language are conceptual metaphors, partial semantic mappings between disparate conceptual domains. Though positive results have been achieved in identifying linguistic metaphors over the last decade, little work has been done to date on automatically identifying conceptual metaphors. This paper describes research on identifying conceptual metaphors based on corpus data. Our method uses as little background knowledge as possible, to ease transfer to new languages and to minimize any bias introduced by the knowledge base construction process. The method relies on general heuristics for identifying linguistic metaphors and statistical clustering (guided by Wordnet) to form conceptual metaphor candidates. Human experiments show the system effectively finds meaningful conceptual metaphors.

11:20-12:20 Session 24A: Bribery / Voting (AAAI)
11:20
Computational Aspects of Nearly Single-Peaked Electorates
SPEAKER: unknown

ABSTRACT. Manipulation, bribery, and control are well-studied ways of changing the outcome of an election. Many voting systems are in the general case computationally resistant to some of these manipulative actions. However when restricted to single-peaked electorates, these systems suddenly become easy to manipulate. Recently, Faliszewski, Hemaspaandra, and Hemaspaandra studied the complexity of dishonest behavior in nearly single-peaked electorates. These are electorates that are not single-peaked but close to it according to some distance measure.

In this paper we introduce several new distance measures regarding single-peakedness. We prove that determining whether a given profile is nearly single-peaked is in many cases NP-complete. For one case we present a polynomial-time algorithm. Furthermore, we explore the relations between several notions of nearly single-peakedness and study the complexity of manipulation for nearly single-peaked elections.

11:35
Ties Matter: Complexity of Manipulation when Tie-breaking with a Random Vote
SPEAKER: unknown

ABSTRACT. We study the impact on strategic voting of tie-breaking by means of considering the order of tied candidates within a random vote. We compare this to another non-deterministic tie-breaking rule where we simply choose between candidates uniformly at random. In general, we demonstrate that there is no connection between the computational complexity of computing a manipulating vote with the two different types of tie-breaking. However, we prove that for some scoring rules, the computational complexity of computing a manipulation can increase from polynomial to NP-hard. We also discuss the relationship with the computational complexity of computing a manipulating vote when we ask for an unique winner, or when we select from the set of co-winners.

11:50
Bribery in Voting with Soft Constraints
SPEAKER: unknown

ABSTRACT. We consider a multi-agent scenario where a collection of agents needs to select a common decision from a large set of possible decisions, over which they express their preferences. Such a decision set has a combinatorial structure, that is, each candidate is an element of the Cartesian product of the domains of some variables. We assume agents compactly express their preferences over the candidates via soft constraints. We consider various aggregation methods: some are sequential, in the sense that they aggregate the preferences over one variable at a time, and an other one is one-step, i.e., it aggregates the preferences over complete assignments of the variables. We study the complexity of influencing such aggregation methods through bribery: How computationally complex is it for an external agent to determine whether by paying certain agents to change their preferences, within a certain budget, a specified candidate can be made the winner decision? We prove that bribery is NP-complete for the considered sequential aggregation methods (based on Plurality, Approval, and Borda) for most of the cost schemes we defined, while the problem is polynomial for one-step Plurality.

12:05
How Bad is Selfish Voting?
SPEAKER: unknown

ABSTRACT. It is well known that strategic behavior in elections is essentially unavoidable; we therefore ask: how bad can the rational outcome be? We answer this question via the notion of the price of anarchy, using the scores of alternatives as a proxy for their quality and bounding the ratio between the score of the optimal alternative and the score of the winning alternative in Nash equilibrium. Specifically, we are interested in Nash equilibria that are obtained via sequences of rational strategic moves. Focusing on three common voting rules — plurality, veto, and Borda — we provide very positive results for plurality and very negative results for Borda, and place veto in the middle of this spectrum.

11:20-12:20 Session 24B: Planning (AAAI)
11:20
Hypothesis Exploration for Malware Detection Using Planning
SPEAKER: unknown

ABSTRACT. In this paper we apply AI planning to address the hypothesis exploration problem and provide assistance to network administrators in detecting malware based on unreliable observations derived from network traffic.Building on the already established characterization and use of AI planning for similar problems, we propose a formulation of the hypothesis generation problem for malware detection as an AI planning problem with temporally extended goals and actions costs. Furthermore, we propose a notion of hypothesis ``plausibility'' under unreliable observations, which we model as plan quality. We then show that in the presence of unreliable observations, simply finding one most ``plausible'' hypothesis, although challenging, is not sufficient for effective malware detection. To that end, we propose a method for applying a state-of-the-art planner within a principled exploration process, to generate multiple distinct high-quality plans. We experimentally evaluate this approach by generating random problems of varying hardness both with respect to the number of observations, as well as the degree of unreliability. Based on these experiments, we argue that our approach presents a significant improvement over prior work that are focused on finding a single optimal plan, and that the hypothesis exploration application can motivate the development of new planners capable of generating the top high-quality plans.

11:35
Red-Black Relaxed Plan Heuristics
SPEAKER: unknown

ABSTRACT. Despite its success, the delete relaxation has significant pit- falls in many important classes of planning domains. Recent work has devised the red-black planning framework, where red variables take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Provided the red variables are chosen so that red-black plan generation is tractable, one can generate such a plan for every search state, and take its length as the heuristic distance estimate. Previous results were not suitable for this purpose because they identified tractable fragments for red-black plan existence, as opposed to red-black plan generation. We identify a new fragment of red-black planning, that fixes this issue. We devise machinery to efficiently generate red-black plans, and to automatically select the red variables. Experiments show that the resulting heuristics can significantly improve over standard delete relaxation heuristics.

11:50
Truncated Incremental Search: Faster Replanning by Exploiting Suboptimality
SPEAKER: unknown

ABSTRACT. Incremental heuristic searches try to reuse their previous search efforts whenever these are available. As a result, they can often solve a sequence of similar planning problems much faster than planning from scratch. State-of-the-art incremental heuristic searches such as LPA*, D* and D* Lite all work by propagating cost changes to all the states on the search tree whose g-values (the costs of computed paths from the start) are no longer optimal. While such a complete propagation of cost changes is required to ensure optimality, the propagations can be stopped much earlier if we are looking for solutions within a given suboptimality bound. We develop an algorithm called Truncated LPA* (TLPA*), that builds on this observation, and uses a target suboptimality bound to efficiently restrict the cost propagations. We explain TLPA*, discuss its analytical properties and present experimental results for 2D and 3D (x, y, heading) path planning that show significant improvement in runtime over existing incremental heuristic searches when searching for close-to-optimal solutions. In addition, unlike typical incremental searches, TLPA* is much less dependent on the proximity of the cost changes to the goal of the search due to the early termination of the cost change propagation.

12:05
A First-Order Formalization of Commitments and Goals for Planning
SPEAKER: unknown

ABSTRACT. Commitments have been shown to model interactions in multiagent systems in a computationally realizable yet high-level manner without compromising the autonomy and heterogeneity of the member agents. Recent work has shown how to combine commitments with goals and apply methods such as planning by which agents can determine their actions. However, previous approaches to modeling commitments have been confined to propositional representations, which limits their applicability in practical cases.

We propose a first-order representation and reasoning technique for commitments and goals that accommodates settings where the commitments and goals are templatic and may be applied repeatedly with differing bindings for domain objects. Doing so not only leads to a more perspicuous modeling, it also enables us to support a variety of practical patterns. In particular, our approach can handle the piecemeal progress, consolidation, delegation, and compensation of commitments.

11:20-12:20 Session 24C: Situation Calculus and STRIPS (AAAI)
11:20
Multiagent Knowledge and Belief Change in the Situation Calculus
SPEAKER: unknown

ABSTRACT. Belief change is an important research area in Artificial Intelligence. It becomes more perplexing in the presence of multiple agents, since the action of an agent may be partially observable to other agents. In this paper, we present a general approach to reasoning about actions and belief change in multi-agent scenarios. Our approach is based on a multi-agent extension to the situation calculus, augmented by a plausibility relation over situations and another one over actions, which is used to represent agents' different perspectives on actions. When an action is performed, we update the agents' plausibility order over situations by giving priority to the plausibility order over actions, in line with the AGM approach of giving priority to new information. We show that our notion of belief satisfies KD45 properties. When it comes to the special case of belief change of a single agent, we show that our framework satisfies most of the classical AGM, DP, and KM postulates. Finally, we present properties concerning the change of common knowledge and belief of a group of agents.

11:35
Progression of Decomposed Situation Calculus Theories
SPEAKER: unknown

ABSTRACT. In many tasks related to reasoning about consequences of a logical theory, it is desirable to decompose the theory into a number of components with weakly-related or independent signatures. This facilitates reasoning when signature of a query formula belongs to only one of the components. However, a theory may be subject to change due to execution of actions affecting features mentioned in the theory. Having once computed a decomposition of a theory, one would like to know whether a decomposition has to be computed again in the theory obtained from taking into account all changes resulting from execution of an action. In the paper, we address this problem in the scope of the situation calculus, where change of an initial theory is related to the well-studied notion of progression. Progression provides a form of forward reasoning; it relies on forgetting values of those features which are subject to change and computing new values for them. We prove new results about properties of decomposition components under forgetting and show when a decomposition can be preserved in progression of an initial situation calculus theory.

11:50
Data-Parallel Computing Meets STRIPS
SPEAKER: Erez Karpas

ABSTRACT. The increased demand for distributed computations on “big data” has led to solutions such as SCOPE, DryadLINQ, Pig, and Hive, which allow the user to specify queries in an SQL-like language, enriched with sets of user-defined operators. The lack of exact semantics for user-defined operators interferes with the query optimization process, thus putting the burden of suggesting, at least partial, query plans on the user. In an attempt to ease this burden, we propose a formal model that allows for data-parallel program synthesis (DPPS) in a semantically well-defined manner. We show that this model generalizes existing frameworks for data-parallel computation, while providing the flexibility of query plan generation that is currently absent from these frameworks. In particular, we show how existing, off-the-shelf, AI planning tools can be used for solving DPPS tasks.

12:05
Reasoning about Saturated Conditional Independence under Uncertainty: Axioms, Algorithms and Levesque's Situations to the Rescue

ABSTRACT. The implication problem of probabilistic conditional independencies is investigated in the presence of missing data. Here, graph separation axioms fail to hold for saturated conditional independencies, unlike the known idealized case with no missing data. Several axiomatic, algorithmic, and logical characterizations of the implication problem for saturated conditional independencies are established. In particular, equivalences are shown to the implication problem of a propositional fragment under Levesque's situations, and that of Lien's class of multivalued database dependencies under null values.

11:20-12:20 Session 24D: Analyzing Networks and Graphs (AAAI)
11:20
Fast and Exact Top-k Algorithm for PageRank
SPEAKER: unknown

ABSTRACT. In AI and Web communities, many applications utilize PageRank. To obtain high PageRank score nodes, the original approach iteratively computes the PageRank score of each node until convergence by using the whole graph. If the graph is large, this approach is infeasible due to its high computational cost. The goal of this study is to find top-k PageRank score nodes efficiently for a given graph without sacrificing accuracy. Our solution, F-Rank, is based on two ideas: (1) It iteratively estimates lower/upper bounds of PageRank scores, and (2) It constructs subgraphs in each iteration by pruning unnecessary nodes and edges to identify top-k nodes. Our theoretical analysis shows that F-Rank guarantees result exactness. Experiments show that F-Rank finds top-k nodes much faster than the original approach.

11:35
Heterogeneous Metric Learning with Joint Graph Regularization for Cross-Media Retrieval
SPEAKER: unknown

ABSTRACT. As the major component of big data, unstructured heterogeneous multimedia content such as text, image, audio, video and 3D increasing rapidly on the Internet. User demand a new type of cross-media retrieval where user can search results across various media by submitting query of any media. Since the query and the retrieved results can be of different media, how to learn a heterogeneous metric is the key challenge. Most existing metric learning algorithms only focus on a single media where all of the media objects share the same data representation. In this paper, we propose a joint graph regularized heterogeneous metric learning (JGRHML) algorithm, which integrates the structure of different media into a joint graph regularization. In JGRHML, different media are complementary to each other and optimizing them simultaneously can make the solution smoother for both media and further improve the accuracy of the final metric. Based on the heterogeneous metric, we further learn a high-level semantic metric through label propagation. JGRHML is effective to explore the semantic relationship hidden across different modalities. The experimental results on two datasets with up to five media types show the effectiveness of our proposed approach.

11:50
TONIC: Target Oriented Network Intelligence Collection for the Social Web
SPEAKER: unknown

ABSTRACT. In this paper we introduce the Target Oriented Network Intelligence Collection (TONIC) problem, which is the problem of finding profiles in a social network that contain information about a given target via automated crawling. % procedure. We formalize TONIC as a search problem and a best-first approach is proposed for solving it. Several heuristics are presented to guide this search. These heuristics are based on the topology of the currently known part of the social network. The efficiency of the proposed heuristics and the effect of the graph topology on their performance is experimentally evaluated on the Google+ social network.

12:05
Preventing Unraveling in Social Networks Gets Harder
SPEAKER: unknown

ABSTRACT. The behavior of users in social networks is often observed to be affected by the actions of their friends. Bhawalkar et al. in ICALP 2012 introduced a formal mathematical model for user engagement in social networks where each individual derives a benefit proportional to the number of its friends which are engaged. Given a threshold degree $k$ the equilibrium for this model is a maximal subgraph whose minimum degree is $\geq k$. However the dropping out of individuals with degrees less than $k$ might lead to a cascading effect of iterated withdrawals such that the size of equilibrium subgraph becomes very small. To overcome this some special vertices called ``anchors" are introduced: these vertices need not have large degree. Bhawalkar et al. considered the Anchored $k$-Core problem: given a graph $G$ and integers $b, k$ and $p$, do there exist a set of vertices $B\subseteq H\subseteq V(G)$ such that $|B|\leq b, |H|\geq p$ and every vertex $v\in H\setminus B$ satisfies $\text{deg}_{G[H]} (v)\geq k$. They showed that the problem is NP-hard for $k\geq 2$ and gave some inapproximability and fixed-parameter intractability results. In this paper we give improved hardness results for this problem. In particular we show that the Anchored $k$-Core problem is W[1]-hard parameterized by $p$, even for $k=3$. This improves the result of Bhawalkar et al. (who show W[2]-hardness parameterized by $b$) as our parameter is always bigger since $p\geq b$. Then we answer a question of Bhawalkar et al. by showing that the Anchored $k$-Core problem remains NP-hard on planar graphs for all $k\geq 3$, even if the maximum degree of the graph is $k+2$. Finally we show that the problem is FPT on planar graphs parameterized by $b$ for all $k\geq 7$.

11:20-12:20 Session 24E: ML in Robotics (AAAI)
11:20
Multi-Target Detection and Recognition by UAVs Using Online POMDPs
SPEAKER: unknown

ABSTRACT. This paper tackles high-level decision-making techniques for robotic missions, which involve both active sensing and symbolic goal reaching, under uncertain probabilistic environments and strong time constraints. Our case study is a POMDP model of an online multi-target detection and recognition mission by an autonomous rotorcraft UAV. The POMDP model of the multi-target detection and recognition problem is generated on line from a list of areas of interest, which are automatically extracted at the beginning of the flight from a coarse-grained high altitude observation of the scene. The POMDP observation model relies on a statistical abstraction of the image processing algorithm's classifier output used to detect and identify targets. As the POMDP problem cannot be known and thus optimized before the beginning of the flight, our main contribution is an "optimize-while-execute" algorithmic framework: it drives a POMDP sub-planner to optimize and execute the POMDP policy in parallel under action duration constraints, reasoning about the future possible execution states of the robotic system. We present new results from real outdoor flights and software-in-the-loop simulations, which highlight both the benefits of using POMDPs in multi-target detection and recognition missions, and of our "optimize-while-execute" paradigm.

11:35
Compact RGBD Surface Models Based on Sparse Coding
SPEAKER: unknown

ABSTRACT. In this paper, we describe a novel approach to construct compact colored 3D environment models representing local surface attributes via sparse coding. Our method decomposes a set of colored point clouds into local surface patches and encodes them based on an overcomplete dictionary. Instead of storing the entire point cloud, we store a dictionary, surface patch positions, and a sparse code description of the depth and RGB attributes for every patch. The dictionary is learned in an unsupervised way from surface patches sampled from indoor maps. We show that better dictionaries can be learned by extending the K-SVD method with a binary weighting scheme that ignores undefined surface cells. Through experimental evaluation on real world laser and RGBD datasets we demonstrate that our method produces compact and accurate models. Furthermore, we clearly outperform an existing state of the art method in terms of compactness, accuracy and computation time. Additionally, we demonstrate that our sparse code descriptions can be utilized for other important tasks including object detection.

11:50
Open-Loop Planning in Large-Scale Stochastic Domains
SPEAKER: unknown

ABSTRACT. We focus on effective planning in the face of high-dimensionality, underactuation, drift, discrete system changes, and stochasticity. These are hallmark challenges for important problems such as humanoid locomotion. Because generality and broad applicability of the method is desired, we assume domain expertise is minimal and limited to a generative model. We need the method to be responsive, so it must have computational costs that scale linearly with the amount of samples taken from the generative model. We bring to bear a concrete method that satisfies all these requirements; it is a receding-horizon open-loop planner that employs cross-entropy optimization for policy construction. In empirical simulations, we demonstrate near-optimal decisions in a small domain and locomotion in several challenging humanoid control tasks.

12:05
Bayesian Nonparametric Multi-Optima Policy Search in Reinforcement Learning
SPEAKER: unknown

ABSTRACT. Skills can often be performed in many different ways. In order to provide robots with human-like adaptation capabilities, it is of great interest to consider the possibility of learning several of them in parallel, since eventual changes in the environment or in the robot can make some solutions unfeasible. In this case, the knowledge of multiple solutions can avoid to relearn the task. This problem is addressed in this paper within the framework of Reinforcement Learning, as the automatic determination of multiple optimal parameterized policies. For this purpose, a model handling a variable number of policies is built, using a Bayesian non-parametric approach. The algorithm is compared to single policy algorithms on some known benchmarks and is then applied to robotics, on problems presenting multiple solutions.

11:20-12:20 Session 24F: Spotlights and Senior Members (AAAI)
11:20
RSS: What's Hot
SPEAKER: unknown

ABSTRACT. Language Grounding

11:35
CP: What's Hot and Challenges
SPEAKER: unknown
11:50
CP: Challenges
SPEAKER: unknown
11:20-12:20 Session 24G: Structure Analysis (IAAI)
11:20
Deployed: USI Answers: Natural Language Question Answering Over (Semi-) Structured Industry Data
SPEAKER: unknown

ABSTRACT. This paper describes USI Answers - a natural language question answering system for semi-structured industry data. This paper reports on our progress towards the goal offering easy access to enterprise data to a large number of business users, most of whom are not familiar with the specific syntax or semantics of the underlying data sources. Additional complications come from the nature of the data, a combination of structured and unstructured. Our solution allows users to express questions in natural language, makes apparent the system's interpretation of the query, and allows easy query adjustment and reformulation. The application is in use by more than a thousand of users from Siemens Energy. We evaluate our approach on a dataset consisting of fleet data.

11:50
Emerging: Clustering Hand-Drawn Sketches via Analogical Generalization
SPEAKER: unknown

ABSTRACT. One of the major challenges to building intelligent educational software is determining what kinds of feedback to give learners. Useful feedback makes use of models of domain-specific knowledge, especially models that are commonly held by potential students. To empirically determine what these models are, student data can be clustered to reveal common misconceptions or common problem-solving strategies. This paper describes how analogical retrieval and generalization can be used to cluster automatically analyzed hand-drawn sketches incorporating both spatial and conceptual information. We use this approach to cluster a corpus of hand-drawn student sketches to discover common answers. Common answer clusters can be used for the design of targeted feedback and for assessment.

12:20-12:30 Session 25A (AAAI)
12:20
Multiple Outcome Supervised Latent Dirichlet Allocation for Expert Discovery in Online Forums
SPEAKER: unknown

ABSTRACT. This paper presents a supervised bayesian approach to model expertise in online forums with application to question routing. The proposed method extends the well-known LDA model to account for a supervised stage with multiple outputs per document, corresponding to each of the users of the system. A study of the characteristics of real world data revealed a number of challenges with interest for the community.

12:22
Supervised Topic Model with Consideration of User and Item
SPEAKER: unknown

ABSTRACT. In this paper, we propose a new supervised topic model by incorporating the user and the item information. The proposed model can simultaneously utilize the textual topic and user-item factors for rating prediction. We conduct rating prediction experiment with a public review data set. The results demonstrate the advantages of our model. It shows clear improvement compared with tranditional supervised topic model and recommendation method.

12:24
Combining CP-Nets with the Power of Ontologies
SPEAKER: unknown

ABSTRACT. The Web is currently shifting from data on linked Web pages towards less interlinked data in social networks on the Web. Therefore, rather than being based on the link structure between Web pages, the ranking of search results needs to be based on something new. We believe that it can be based on user preferences and ontological background knowledge, as a means to personalized access to information. There are many approaches to preference representation and reasoning in the literature. The most prominent qualitative ones are perhaps CP-nets. Their clear graphical structure unifies an easy representation of preferences with nice properties when computing the best outcome. In this paper, we introduce {\em ontological CP-nets}, where the knowledge domain has an ontological structure, i.e., the values of the variables are constrained relative to an underlying ontology. We show how the computation of Pareto optimal outcomes for such ontological CP-nets can be reduced to the solution of constraint satisfaction problems. We also provide several complexity and tractability results.

12:26
Negative Influence Minimizing by Blocking Nodes in Social Networks
SPEAKER: unknown

ABSTRACT. Social networks are becoming vital platforms for the spread of positive information such as innovations and negative information propagation like malicious rumors. In this paper, we address the problem of minimizing the influence of negative information. When negative information such as a rumor emerges in the social network and part of users have already adopted it, our goal is to minimize the size of ultimately contaminated users by discovering and blocking k uninfected users. A greedy method for efficiently finding a good approximate solution to this problem is proposed. The comparison experimental results on the Enron email network dataset demonstrate our proposed method is more effective than centrality based methods, such as degree centrality, betweenness centrality and PageRank.

12:20-12:30 Session 25B (AAAI)
12:20
Comprehensive Cross-Hierarchy Cluster Agreement Evaluation
SPEAKER: unknown

ABSTRACT. Hierarchical clustering represents a family of widely used clustering approaches that can organize objects into a hierarchy based on the similarity in objects' feature values. One significant obstacle facing hierarchical clustering research today is the lack of general and robust evaluation methods. Existing works rely on a range of evaluation techniques including both internal (no ground-truth is considered in evaluation) and external measures (results are compared to ground-truth semantic structure). The existing internal techniques may have strong hierarchical validity, but the available external measures were not developed specifically for hierarchies. This lack of specificity prevents them from comparing hierarchy structures in a holistic, principled way. To address this problem, we propose the Hierarchy Agreement Index, a novel hierarchy comparison algorithm that holistically compares two hierarchical clustering results (e.g. ground-truth and automatically learned hierarchies) and rates their structural agreement on a 0-1 scale. We compare the proposed evaluation method with a baseline approach (based on computing F-Score results between individual nodes in the two hierarchies) on a set of unsupervised and semi-supervised hierarchical clustering results, and observe that the proposed Hierarchy Agreement Index provides more intuitive and reasonable evaluation of the learned hierarchies.

12:22
Strong Nash Equilibrium Is in Smoothed P
SPEAKER: unknown

ABSTRACT. The computational characterization of game--theoretic solution concepts is a prominent topic in artificial intelligence. The central solution concept is Nash equilibrium (NE). However, it fails to capture the possibility that agents can form coalitions. Strong Nash equilibrium (SNE) refines NE to this setting. It is known that finding an SNE is NP-complete when the number of agents is constant. This hardness is solely due to the existence of mixed--strategy SNEs, given that the problem of enumerating all pure-strategy SNEs is trivially in P. Our central result is that, in order for a n-agent game to have at least one non-pure-strategy SNE, the agents' payoffs restricted to the agents' supports must lie on an (n-1)-dimensional space. Small perturbations make the payoffs to be outside such a space and thus, unlike NE, finding an SNE is in smoothed polynomial time.

12:24
Verbal IQ of a Four-Year Old Achieved by an AI System
SPEAKER: unknown

ABSTRACT. Verbal tasks that have traditionally been difficult for computer systems but are easy for young children are among AI’s “grand challenges”. We present the results of testing the ConceptNet 4 system on the verbal part of the standard WPPSI-III IQ test, using simple test-answering algorithms. It is found that the system has the Verbal IQ of an average four-year-old child.

12:26
Approximation of Lorenz-Optimal Solutions in Multiobjective Markov Decision Processes
SPEAKER: unknown

ABSTRACT. We describe and test algorithms for finding small, representative subsets of the Lorenz-optimal policies for Multiobjective Markov Decision Processes.

12:28
Covering Landmark Interactions for Semantically Diverse Plans
SPEAKER: Daniel Bryce

ABSTRACT. Prior approaches to generating diverse plans in domain-independent planning seek out syntactic variations on plan structure such as actions or causal links used, or states entered. As a result, syntactic approaches can achieve great plan set diversity by synthesizing unnecessarily long plans. This type of misleading diversity may be useful if, for example, the plans are used as training data for a learner; however, they have arguably low value to a human decision maker.

We present an approach to domain-independent diverse planning that systematically varies the semantic attributes of plans so that we do not arbitrarily inflate plan length to achieve syntactic diversity. Our contribution is based upon the fact that landmarks, which represent the minimally necessary subgoals (semantics) of a planning domain, can be disjunctive and hence satisfied in a number of ways. Varying the disjuncts that must be satisfied by alternative plans leads to a form of diversity that does not encourage irrelevant plan structure. We present an extension of the LAMA planner called DLAMA that generates multiple plans, each required to systematically satisfy alternative landmark disjuncts. We show that, in comparison with syntacticly diverse planners, DLAMA reduces average plan length while achieving plan set diversity.

12:20-12:30 Session 25C (AAAI)
12:20
Conditional Outlier Approach for Detection of Unusual Patient Care Actions
SPEAKER: unknown

ABSTRACT. Developing methods that identify important patterns in complex large-scale temporal datasets is one of the key challenges for machine learning and data mining research. Our work focuses on the development of methods that can, based on past data, identify unusual patient-management patterns in the Electronic Medical Record of the current patient and the application of these methods in clinical alerting. We developed and evaluated a conditional-outlier detection approach for identifying clinical actions such as omissions of medication orders or laboratory orders in the intensive care unit (ICU) that are unusual with respect to past patient care and may indicate possible medical error. We generated 250 medication-omission alerts and 150 laboratory-omission alerts using a database of 24,658 ICU patient admissions. These alerts were evaluated by a group of intensive care physicians. Overall, the true positive alert rate was 0.52, which is quite promising and compares very favorably to the positive alert rates of the existing clinical alerting systems.

12:22
Discriminative Multi-Task Feature Selection
SPEAKER: unknown

ABSTRACT. The effectiveness of supervised feature selection degrades in low training data scenarios. We propose to alleviate this problem by augmenting per-task feature selection with joint feature selection over multiple tasks. Our algorithm builds on the assumption that different tasks have shared structure which could be utilized to cope with data sparsity. The proposed trace-ratio based model not only selects discriminative features for each task, but also finds features which are discriminative over all tasks. Extensive experiment on different data sets demonstrates the effectiveness of our algorithm in low training data scenarios.

12:24
A Modular Framework for the Automatic Reconstruction of Shredded Documents
SPEAKER: Razvan Ranca

ABSTRACT. The unshredding problem is of interest in various domains such as forensics, investigative sciences and archeology, and has therefore been approached in many different ways. This paper tries to bridge the gap between previous, disparate, efforts by proposing a modular, probabilistic, solution. Novel approaches to two of the independent subproblems are presented and shown to both have good theoretical properties and to empirically outperform previously published methods.

12:26
Learning When to Reject an Importance Sample
SPEAKER: unknown

ABSTRACT. When observations are incomplete or data are missing, approximate inference methods based on importance sampling are often used. Unfortunately, these methods may suffer from increasing variance in sample weights with increases in observation numbers, leading to biased estimates or requiring a prohibitive number of samples. Our method approximates a target distribution by sampling from an existing proposal distribution and then accepting or rejecting the proposal. We develop the rejection-sampler framework and show we can learn the acceptance probability from local samples. In a continuous-time domain, we show our method improves upon previous importance samplers by transforming an importance sampling problem into a machine learning one.

12:20-12:30 Session 25D (AAAI)
12:20
Modular Answer Set Solving
SPEAKER: unknown

ABSTRACT. Modularity is essential for modeling large-scale practical applications. We propose modular logic programs as a modular version of answer set programming and study the relationship of our formalism to an earlier concept of lp-modules.

12:22
Additive Counterexample-guided Cartesian Abstraction Refinement
SPEAKER: unknown

ABSTRACT. We recently showed how counterexample-guided abstraction refinement can be used to derive informative heuristics for optimal classical planning. In this work we introduce an algorithm for building additive abstractions and demonstrate that they outperform other state-of-the-art abstractions heuristics on many benchmark domains.

12:24
Partial Domain Search Tree for Constraint-Satisfaction Problems
SPEAKER: unknown

ABSTRACT. CSP Solvers usually search the partial assignment search tree. We present a new formalization that spans a conceptually different search tree, where each node represents subsets of the original domains for the variables. We experiment with a simple backtracking algorithm for this search tree and show that it outperforms a simple backtracking algorithm on the traditional search tree in many cases.

12:26
Volatile Multi-Armed Bandits for Guaranteed Targeted Social Crawling
SPEAKER: unknown

ABSTRACT. We introduce a new variant of multi-armed bandit, called Volatile-multi-arm bandit problem (VMAB) and provide a policy with bounded regret. We show how the problem of collecting intelligence on profiles in social networks can be modeled as a VMAB and demonstrate experimentally the superiority of our proposed policy.

12:28
Localizing Web Videos from Heterogeneous Images
SPEAKER: unknown

ABSTRACT. While geo-localization of web images has been widely studied, there is limited work that touches the geolocation inference of web videos. However, such geographical localization functionality is of great importance to provide location-aware services , especially on mobile devices. In this paper, we tackle this problem from a novel perspective, by “transferring” the largescale web images with geographical tags to web videos, by making associations between their visual content similarities (e.g. near-duplicate detection between video frames and images). A group of experiments are conducted on a collected web image and video data set compared with several alternatives and stat-of-the-arts.

12:30-13:45Lunch Break
13:45-14:45 Session 26: Invited talk:Sandholm (AAAI)
13:45
AAAI-13 Invited Talk: Poker AI: Algorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information Games

ABSTRACT. Incomplete-information games — such as most auctions, negotiations, and future (cyber)security settings — cannot be solved using minimax search even in principle. Completely different algorithms were needed. A dramatic scalability leap has occurred in our ability to solve such games over the last seven years, fueled largely by the Annual Computer Poker Competition. I will discuss the key domain-independent techniques that enabled this leap, including automated abstraction techniques and approaches for mitigating the issues that they raise, new equilibrium-finding algorithms, safe opponent exploitation methods, techniques that use qualitative knowledge as an extra input, and endgame solving techniques. I will finish by benchmarking poker programs against the best human poker professionals and by discussing what humans can learn from the programs.

14:45-15:45 Session 27A: Constraints (AAAI)
14:45
Unified Constraint Propagation on Multi-View Data
SPEAKER: unknown

ABSTRACT. This paper presents a unified framework for intra-view and inter-view constraint propagation on multi-view data from a semi-supervised learning viewpoint. In the literature, pairwise constraint propagation has been studied extensively, where each pairwise constraint is defined over a pair of data points from a single view. In contrast, very little attention has been paid to inter-view constraint propagation, which is more challenging since each pairwise constraint is now defined over a pair of data points from different views. Although both intra-view and inter-view constraint propagation are crucial for multi-view tasks, most previous methods cannot handle them simultaneously. To address this challenging issue, we propose to decompose these two types of constraint propagation into semi-supervised learning subproblems so that they can be uniformly solved based on the traditional label propagation techniques. To further integrate them into a unified framework, we utilize the results of intra-view constraint propagation to adjust the similarity matrix of each view and then perform inter-view constraint propagation with the adjusted similarity matrices. The experimental results in cross-view retrieval have demonstrated the superior performance of our unified constraint propagation.

15:00
On the Subexponential Time Complexity of CSP
SPEAKER: unknown

ABSTRACT. A Constraint Satisfaction Problem (CSP) with n variables ranging over a domain of d values can be solved by brute-force in d^n steps (omitting a polynomial factor). With a more careful approach, this trivial upper bound can be improved for certain natural restrictions of the CSP. In this paper we establish theoretical limits to such improvements, and draw a detailed landscape of the subexponential-time complexity of CSP.

We first establish relations between the subexponential-time complexity of CSP and that of other problems, including CNF-SAT. We exploit this connection to provide tight characterizations of the subexponential-time complexity of CSP under common assumptions in complexity theory. For several natural CSP parameters, we obtain threshold functions that precisely dictate the subexponential-time complexity of CSP with respect to the parameters under consideration.

Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving CSP.

15:15
Improving the Performance of Consistency Algorithms by Localizing and Bolstering Propagation in a Tree Decomposition
SPEAKER: unknown

ABSTRACT. Certain classes of Constraint Satisfaction Problems (CSPs) can be solved in polynomial time when the consistency level corresponds to a structural parameter of the constraint network such as the treewidth or the hypertree width. In this work we exploit this condition and propose new techniques that allow us to practically approach the necessary consistency level. We proposed to apply the parametrized relational consistency property R(∗,m)C locally to the clusters of a tree decomposition and set the value of m to the total number of relations in the cluster. Moreover, we propose different schemes to bolster the separators to enhance the propagation. We conceptually compare the resulting new consistency properties to other consistency properties, and empirically evaluate them against GAC, maxRPWC and wR(∗,m)C. The empirical results suggest that our technique outperforms GAC, maxRPWC, and wR(∗,m)C in certain hard CSP classes.

15:30
Extending STR to a Higher-Order Consistency
SPEAKER: unknown

ABSTRACT. One of the most widely studied classes of constraints in constraint programming (CP) is that of table constraints. Numerous specialized filtering algorithms, enforcing the wellknown property called generalized arc consistency (GAC), have been developed for such constraints. Among the most successful GAC algorithms for table constraints, we find variants of simple tabular reduction (STR), like STR2. In this paper, we propose an extension of STR-based algorithms that achieves full pairwise consistency (FPWC), a consistency stronger than GAC and max Restricted Pairwise Consistency (maxRPWC). Our approach involves counting the number of occurrences of specific combinations of values in constraint intersections. Importantly, the worst-case time complexity of one call to the basic filtering procedure at the heart of our new algorithm is quite close to that of STR algorithms. Experiments demonstrate that our method can outperform STR2 in many classes of problems, being significantly faster in some cases. Also, it is clearly superior to maxRPWC+, an algorithm that has been recently proposed.

14:45-15:45 Session 27B: Tensors and Manifolds (AAAI)
14:45
Multiscale Manifold Learning
SPEAKER: unknown

ABSTRACT. Many high-dimensional data sets that lie on a low-dimensional manifold exhibit nontrivial regularities at multiple scales. Most work in manifold learning ignores this multiscale structure. In this paper, we propose approaches to explore the deep structures of manifolds. The proposed approaches are based on the diffusion wavelets model, data driven, and able to directly process directional neighborhood relationships without ad-hoc symmetrization. The proposed multiscale algorithms are evaluated using both synthetic and real-world data sets.

15:00
A Tensor-Variate Gaussian Process for Classification of Multidimensional Structured Data
SPEAKER: unknown

ABSTRACT. As tensors provide a natural and efficient representation of multidimensional structured data, in this paper, we consider probabilistic multinomial probit classification for tensor-variate inputs with Gaussian processes (GP) priors placed over the latent function. In order to take into account the underlying multimodes structure information within the model, we propose a framework of probabilistic product kernels for tensorial data based on a generative model assumption. More specifically, it can be interpreted as mapping tensors to probability density function space and measuring similarity by an information divergence. Since tensor kernels enable us to model input tensor observations, the proposed tensor-variate GP is considered as both a generative and discriminative model. Furthermore, a fully variational Bayesian treatment for multiclass GP classification with multinomial probit likelihood is employed to estimate the hyperparameters and infer the predictive distributions. Simulation results on both synthetic data and a real world application of human action recognition in videos demonstrate the effectiveness and advantages of the proposed approach on classification of multiway tensor data, especially in the case that the underlying structure information among multimodes is discriminative for the classification task.

15:15
A Cyclic Weighted Median Method for L1 Low-Rank Matrix Factorization with Missing Entries
SPEAKER: unknown

ABSTRACT. A challenging problem in machine learning, information retrieval and computer vision research is how to recover a low-rank representation of the given data in the presence of outliers and missing entries. The L1-norm low-rank matrix factorization (LRMF) has been a popular approach to solving this problem. However, L1-norm LRMF is difficult to achieve due to its non-convexity and non-smoothness, and existing methods are often inefficient and fail to converge to a desired solution. In this paper we propose a novel cyclic weighted median (CWM) method, which is intrinsically a coordinate decent algorithm, for L1-norm LRMF. The CWM method minimizes the objective by solving a sequence of scalar minimization sub-problems, each of which is convex and can be easily solved by the weighted median filter. The extensive experimental results validate that the proposed CWM method outperforms state-of-the-arts in terms of both accuracy and computational efficiency.

15:30
Supervised Nonnegative Tensor Factorization with Maximum-Margin Constraint
SPEAKER: unknown

ABSTRACT. Non-negative tensor factorization (NTF) has attracted great attention in the machine learning community. In this paper, we extend traditional non-negative tensor factorization into a supervised discriminative decomposition, referred as Supervised Non-negative Tensor Factorization with Maximum-Margin constraints (SNTFM^2). SNTFM^2 formulates the optimal discriminative factorization of non-negative tensorial data as a coupled least-squares optimization problem via a maximum-margin method. As a result, SNTFM^2 not only faithfully approximates the tensorial data by additive combinations of the basis, but also obtains a strong generalization power to discriminative analysis (in particular for classification in this paper). The experimental results show the superiority of our proposed model over state-of-the-art techniques on both toy and real world data sets.

14:45-15:45 Session 27C: Equilibrium and Negotiation (AAAI)
14:45
Efficient Evolutionary Dynamics with Extensive-Form Games
SPEAKER: unknown

ABSTRACT. Evolutionary game theory combines game theory and dynamical systems and is customarily adopted to describe evolutionary dynamics in multi-agent systems. In particular, it has been proven to be a successful tool to describe multi-agent learning dynamics. To the best of our knowledge, we provide in this paper the first replicator dynamics applicable to the sequence form of an extensive-form game, allowing an exponential reduction of time and space w.r.t. the currently adopted replicator dynamics for normal form. Furthermore, our replicator dynamics is realization equivalent to the standard replicator dynamics for normal form. We prove our results for both discrete-time and continuous-time cases. Finally, we extend standard tools to study the stability of a strategy profile to our replicator dynamics.

15:00
An Agent Design for Repeated Negotiation and Information Revelation with People
SPEAKER: unknown

ABSTRACT. Many negotiations in the real world are characterized by incomplete information, and participants' success depends on their ability to reveal information in a way that facilitates agreement without compromising their individual gains. This paper presents a novel agent design for repeated negotiation in incomplete information settings that learns to reveal information strategically during the negotiation process. The agent used classical machine learning techniques to predict how people make and respond to offers during the negotiation, how they reveal information, and their response to potential revelation actions by the agent. The agent was evaluated empirically in an extensive empirical study spanning hundreds of human subjects. Results show that the agent was able to outperform people. It learned to (1) make offers that were beneficial to people while not compromising its own benefit; (2) incrementally reveal information to people in a way that increased its expected performance. We also show the agent was successful in new settings without the need to acquire additional data. This work demonstrates the efficacy of combining machine learning with opponent modeling techniques towards the design of computer agents for negotiating with people in settings of incomplete information.

15:15
Algorithms for Strong Nash Equilibrium with More than Two Agents
SPEAKER: unknown

ABSTRACT. Strong Nash equilibrium (SNE) is an appealing solution concept when rational agents can form coalitions. A strategy profile is an SNE if no coalition of agents can benefit by deviating. An SNE must simultaneously be a Nash equilibrium (NE) and the optimal solution of multiple non-convex optimization problems. This makes even the derivation of necessary and sufficient equilibrium constraints in a mathematical programming fashion difficult. We show that forcing an SNE to be resilient only to pure strategy deviations by coalitions, unlike for NEs, is only a necessary condition here. Second, we show that the application of Karush-Kuhn-Tucker conditions leads to another set of necessary conditions that are not sufficient. Third, we show that forcing the Pareto efficiency of an SNE for each coalition with respect to coalition correlated strategies is sufficient but not necessary. We then develop a tree search algorithm for SNE finding. At each node, it calls an oracle to suggest a candidate SNE and then verifies the candidate. We show that our new necessary conditions can be leveraged to make the oracle more powerful. Experiments validate the overall approach and show that the new conditions significantly reduce search tree size compared to using NE conditions alone.

15:30
Equilibria of Online Scheduling Algorithms

ABSTRACT. We describe a model for competitive online scheduling algorithms. Two servers, each with a single observable queue, compete for customers. Upon arrival, each customer strategically chooses the queue with minimal expected wait time. Each scheduler wishes to maximize its number of customers, and can strategically select which scheduling algorithm, such as First-Come-First-Served (FCFS), to use for its queue. This induces a game played by the servers and the customers.

We consider a non-Bayesian setting, where servers and customers play to maximize worst-case payoffs. We show that there is a unique subgame perfect safety-level equilibrium and we describe the associated scheduling algorithm (which is not FCFS). The uniqueness result holds for both randomized and deterministic algorithms, with a different equilibrium algorithm in each case.

When the goal of the servers is to minimize competitive ratio, we prove that it is an equilibrium for each server to apply FCFS: each server obtains the optimal competitive ratio of 2.

14:45-15:45 Session 27D: Recommendation Systems (AAAI)
14:45
Understanding and Predicting Interestingness of Videos
SPEAKER: unknown

ABSTRACT. The amount of videos available on the Web is growing explosively. While some videos are very interesting and receive high rating from viewers, many of them are less interesting or even boring. This paper conducts a pilot study on the understanding of human perception of video interestingness, and demonstrates a simple computational method to identify more interesting videos. To this end we first construct two datasets of Flickr and YouTube videos respectively. Human judgements of interestingness are collected and used as the ground-truth for training computational models. We evaluate several off-the-shelf visual and audio features that are potentially useful for predicting interestingness on both datasets. Results indicate that audio and visual features are equally important and the combination of both modalities shows very promising results.

15:00
Active Transfer Learning for Cross-System Recommendation
SPEAKER: unknown

ABSTRACT. Recommender systems, especially new-launched ones, have to deal with the data sparsity issue, where little collaborative information is available. Recently, transfer learning has been proposed to address this problem by leveraging knowledge from related recommender systems where rich collaborative data are available. However, most previous transfer learning models assume that entity-correspondences across different systems are given as inputs, which means that for any entity (e.g., a user or an item) in a target system, its corresponding entity in a source system is known. This assumption can hardly be satisfied in real-world scenarios where entity-correspondences across systems are unknown, and the cost of identifying them is expensive, e.g., identifying whether a user A from Facebook and a user B from Twitter point to the same person could be extremely difficult. In this paper, inspired by the idea of active learning, we propose a framework to actively construct entity-correspondences with limited budget for knowledge transfer across recommender systems. Specifically, for the purpose of maximizing knowledge transfer, we first iteratively select entities in the target system based on our proposed criterion to query their correspondences in the source system. We then plug the actively constructed entity-correspondences into a general transfer collaborative filtering model for cross-system recommendations. Extensive experiments on real world datasets verify the effectiveness of our proposed framework for recommendation across systems.

15:15
LA-CTR: A Limited Attention Collaborative Topic Regression for Social Media
SPEAKER: unknown

ABSTRACT. Probabilistic models can learn users' preferences from the history of their item adoptions on a social media site, and in turn, recommend new items to users based on their learned preferences. However, current models ignore human cognitive factors that play an important role in shaping online behavior. One such factor is attention, the mechanism that integrates perceptual and cognitive features to select the items the user will process and eventually adopt. Recent research has shown that people have finite attention, which constrains their online interactions, and that they divide their limited attention non-uniformly over other people. We propose a collaborative topic regression model that incorporates limited, non-uniformly divided attention. We show that the proposed model is able to learn more accurate user preferences than state-of-art models, which do not take human cognitive factors into account. Specifically we analyze voting on news items on the social news aggregator and show that our model is better able to predict held out votes than alternate models. Our study demonstrates that psycho-socially motivated models are better able to describe and predict observed behavior than models, which only consider latent social structure and content.

15:30
A Fast Bandit Algorithm for Recommendations to Users with Heterogeneous Tastes
SPEAKER: unknown

ABSTRACT. We study article recommendation in scenarios where there's no prior information about the quality of content in the system. We present an online algorithm that interactively optimizes recommendation relevance based on behavior of past users. We use a stochastic optimization concept known as the correlation gap to prove that our algorithm has near optimal bounds on regret which improves upon known results in this area. Finally, we test our algorithm on real-world data collected from previous recommender systems and show that our algorithm learns faster than existing methods and performs equally well in the long-run.

14:45-15:45 Session 27E: Human-Robot Collaboration (AAAI)
14:45
Model-Lite Case-Based Planning
SPEAKER: unknown

ABSTRACT. There is increasing awareness in the planning community that depending on complete models impedes the applicability of planning technology in many real world domains where the burden of specifying complete domain models is too high. In this paper, we consider a novel solution for this challenge that combines generative planning on incomplete domain models with a library of plan cases that are known to be correct. While this was arguably the original motivation for case-based planning, most existing case-based planners assume (and depend on) from-scratch planners that work on complete domain models. In contrast, our approach views the plan generated with respect to the incomplete model as a "skeletal plan" and augments it with directed mining of plan fragments from library cases. We will present the details of our approach and present an empirical evaluation of our method in comparison to a state-of-the-art case-based planner that depends on complete domain models.

(This paper corresponds to AAAI-690.)

15:00
Learning Collaborative Impedance-based Robot Behaviors
SPEAKER: unknown

ABSTRACT. Research in learning from demonstration has focused on developing algorithms for robots to reproduce and generalize trajectories demonstrated by a human teacher. However, a need is arising for robots that do not just replicate the task on their own, but that also interact with humans in a safe and natural way to accomplish tasks cooperatively. A new generation of robots with variable impedance capabilities opens the door to a variety of challenging applications, and the learning algorithms must be extended accordingly by encapsulating force and vision information. In this paper we propose a framework to transfer impedance-based behaviors to a torque-controlled robot, with demonstrations provided by kinesthetic teaching. The proposed model encodes the examples as a task-parameterized statistical dynamical system, where the robot impedance is shaped by estimating virtual stiffness matrices from the set of demonstrations. A collaborative assembly task is used as testbed. The results show that the proposed framework can be used to modify the robot impedance along task execution to facilitate the collaboration. The resulting model learns how to automatically trigger stiff and compliant behaviors in an on-line manner by adapting to the human actions.

15:15
Inferring Robot Task Plans from Human Team Meetings: A Generative Modeling Approach with Logic-Based Prior
SPEAKER: unknown

ABSTRACT. We aim to reduce the burden of programming and deploying autonomous systems to work in concert with people in time-critical domains, such as military field operations and disaster response. Deployment plans for these operations are frequently negotiated by human planners on-the-fly. A human operator then translates the agreed upon plan into machine instructions for the robots. We present an algorithm that reduces this translation burden by inferring the final plan directly from the human team's planning conversation. Our approach combines probabilistic generative modeling with logical plan validation used to compute a highly structured prior over possible plans. This hybrid approach enables us to overcome the challenge of performing inference over the large solution space with only a small amount of noisy data from the team planning session. We validate the algorithm through human subject experimentation and show we are able to infer a human team's final plan with 73% accuracy on average. We also describe a robot demonstration in which two people plan and execute a first-response collaborative task with a PR2 robot. To the best of our knowledge, this is the first work that combines a logical planning technique with a generative modeling approach to perform plan inference.

15:30
Data-Efficient Generalization of Robot Skills with Contextual Policy Search
SPEAKER: unknown

ABSTRACT. In robotics, controllers make the robot solve a task within a specific context. The context can describe the objectives of the robot or physical properties of the environment and is always specified before task execution. To generalize the controller to multiple contexts, we follow a hierarchical approach for policy learning: A lower-level policy controls the robot for a given context and an upper-level policy generalizes among contexts. Current approaches for learning such upper-level policies are based on model-free policy search, which require an excessive number of interactions of the robot with its environment. More data-efficient policy search approaches are model based but, thus far, without the capability of learning hierarchical policies. We propose a new model-based policy search approach that can also learn contextual upper-level policies. Our approach is based on learning probabilistic forward models for long-term predictions. Using these predictions, we use information-theoretic insights to improve the upper-level policy. Our method achieves a substantial improvement in learning speed compared to existing methods on simulated and real robotic tasks.

14:45-15:45 Session 27F: Spotlights and Senior Members (AAAI)
14:45
ICWSM: What's Hot: Structure and Dynamics of Social Networks and Information Networks
SPEAKER: unknown
15:00
ICWSM: Challenges
SPEAKER: unknown
15:15
AAMAS: Best Paper
SPEAKER: unknown

ABSTRACT. Piotr Krysta (University of Liverpool, Greece); Orestis Telelis (Athens University of Economics and Business, Greece); Carmine Ventre (Teesside University, UK)

15:30
AAMAS: What's Hot
SPEAKER: unknown
14:45-15:45 Session 27G: Event Detection (IAAI)
14:45
Emerging: Leveraging Crowdsourcing to Detect Improper Tasks in Crowdsourcing Marketplaces
SPEAKER: unknown

ABSTRACT. Controlling the quality of tasks is one of the big challenges in crowdsourcing marketplaces. Most of the existing crowdsourcing services prohibit requesters from posting illegal or objectionable tasks. Operators in the marketplaces have to continuously monitor posted tasks to find such improper tasks, however it is too costly to manually investigate every single task. In this paper, we report about our trial study on automatic detection of improper tasks for supporting the monitoring activities by marketplace operators. We perform experiments by using real task data from a commercial crowdsourcing marketplace and first show that the classifier trained by the operators' judgments achieves high accuracy to detect improper tasks. In addition, to reduce the annotation costs of the operator and improve classification accuracy, we consider the use of crowdsourcing for task annotation. We hire a group of crowdsourcing (non-expert) workers to monitor posted tasks, and incorporate their judgments into the training data of the classifier. By applying quality control techniques to handle the variability of the workers' reliability, our results show that the use of non-expert judgments by crowdsourcing workers in combination with expert judgments improves the accuracy of detecting improper crowdsourcing tasks.

15:05
Emerging: Detection and Prediction of Adverse and Anomalous Events in Medical Robots
SPEAKER: unknown

ABSTRACT. Adverse and anomalous (A\&A) events are a serious concern in medical robots. We describe a system that can rapidly detect such events and predict their occurrence. As part of this system, we describe simulation, data collection and user interface tools we build for a robot for small animal biopsies. The data we collect consists of both the hardware state of the robot and variables in the software controller. We use this data to train dynamic Bayesian network models of the joint hardware-software state-space dynamics of the robot. Our empirical evaluation shows that (i) our models can accurately model normal behavior of the robot, (ii) they can rapidly detect anomalous behavior once it starts, (iii) they can accurately predict a future A\&A event within a time window of it starting and (iv) the use of additional software variables beyond the hardware state of the robot is important in being able to detect and predict certain kinds of events.

15:25
Emerging: Detecting the Moment of Snap in Real-World Football Videos
SPEAKER: unknown

ABSTRACT. In recent years, there has been a great increase in the use of web services for the storage, annotation, and sharing of sports video by athletic teams. Most of these web services, however, do not provide enhanced functionalities to their users that would enable, e.g., faster access to certain video moments, or reduce manual labor in video annotation. One such web service specializes in American football videos, supporting over 13,000 high school and college teams. Its users often need to fast forward the video to certain moments of snap when the corresponding plays of the football game start. To our knowledge, this paper describes the first effort toward automating this enhanced functionality. Under a very tight running-time budget, our approach reliably detects the start of a play in an arbitrary football video with minimal assumptions about the scene, viewpoint, and video resolution and shot quality. We face many challenges that are rarely addressed by a typical computer vision system, such as, e.g., a wide range of camera viewing angles and distances, and poor resolution and lighting conditions. Extensive empirical evaluation shows that our approach is very close to being usable in a real-world setting.

15:45-16:15Coffee Break
15:45-16:45 Session 28: LBP/Poster sessions (AAAI)
16:45-17:45 Session 29A: Reviewing (AAAI)
16:45
Conference Reviewing: Best Practices

ABSTRACT. Panel Organizers: Marie desJardins and Michael Littman Panelists: Ariel Felner, Kristian Kersting, Ashish Sabharwal

This panel will focus on the reviewing process and best practices for reviewers, senior program committee members, and area/conference chairs. Topics will include how to write an effective review, the dynamics of reviewer discussions, handling author feedback, ethics of author/reviewer conflicts, and alternative reviewing models. The panel is for all AAAI community members but is particularly designed to help graduate students, postdocs, and junior faculty "learn the ropes" of the reviewing process. Relevant issues for these junior community members, such as "standing your ground" with more senior reviewers and how to "grow" into becoming a PC member or SPC, will be explored.

16:45-17:45 Session 29B: Planning Under Uncertainty (AAAI)
16:45
Assumption-Based Planning: Generating Plans and Explanations under Incomplete Knowledge
SPEAKER: unknown

ABSTRACT. Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, simplifying the planning problem, and often resulting in high quality plans where no conformant plan exists. We are interested in this paradigm of planning for two reasons: 1) it captures a compelling form of commonsense planning, and 2) it is of great utility in the generation of explanations, diagnoses, and counter-examples -- tasks which share a computational core with planning. We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm.

17:00
A Fast Pairwise Heuristic for Planning under Uncertainty
SPEAKER: unknown

ABSTRACT. POMDP (Partially Observable Markov Decision Process) is a mathematical framework that models planning under uncertainty. Solving a POMDP is an intractable problem and even the state of the art POMDP solvers are too computationally expensive for large domains. This is a major bottleneck. In this paper, we propose a new heuristic, called the pairwise heuristic, that can be used in a one-step greedy strategy to find a near optimal solution for POMDP problems very quickly. This approach is a good candidate for large problems where real-time solution is a necessity but exact optimality of the solution is not vital. The pairwise heuristic uses the optimal solutions for pairs of states. For each pair of states in the POMDP, we find the optimal sequence of actions to resolve the uncertainty and to maximize the reward, given that the agent is uncertain about which state of the pair it is in. Then we use these sequences as a heuristic and find the optimal action in each step of the greedy strategy using this heuristic. We have tested our method on the available large classical test benchmarks in various domains. The resulting total reward is close to, if not greater than, the total reward obtained by other state of the art POMDP solvers, while the time required to find the solution is always much less.

17:15
Mixed Observability Predictive State Representations
SPEAKER: unknown

ABSTRACT. Learning accurate models of agent behaviours is crucial for the purpose of controlling multiagent systems where the agent and environment dynamics are unknown. Many multiagent systems exhibit mixed observability, where the multiple interacting agents are heterogenous - observations of some of the agents are essentially perfect and noiseless, while observations of other agents are imperfect, aliased or noisy. Predictive state representations are well-suited to model learning but had hitherto not been adapted to such systems. We present a new model learning framework, the mixed observability predictive state representation (MO-PSR), which exploits structural properties present in mixed observability multiagent systems to learn models that allow more efficient planning and control. We present a learning algorithm that is scalable to large amounts of data and to large mixed observability domains, and show theoretical analysis of the learning consistency and computational complexity. Empirical results demonstrate that our algorithm is capable of learning accurate models, at a larger scale than with the generic predictive state representation, by leveraging the mixed observability properties.

17:30
Qualitative Planning under Partial Observability in Multi-Agent Domains
SPEAKER: unknown

ABSTRACT. Decentralized POMDPs (Dec-POMDPs) provide a rich, attractive model for planning under uncertainty and partial observability in cooperative multi-agent domains with a growing body of research. In this paper we formulate a qualitative, propositional model for multi-agent planning under uncertainty with partial observability, which we call QDec-POMDP. We show that the worst-case complexity of planning in QDec-POMDPs is similar to that of Dec-POMDPs. Still, because the model is more "classical" in nature, it is more compact and easier to specify. Furthermore, it eases the adaptation of methods used in classical and contingent planning to solve problems to which Dec-POMDPs solution techniques cannot scale up. In particular, in this paper we describe a method based on compilation to classical planning, which handles multi-agent planning problems significantly larger than those handled by current Dec-POMDP algorithms.

16:45-17:45 Session 29C: Logic and Knowledge Representation (AAAI)
16:45
Dynamic Minimization of Sentential Decision Diagrams
SPEAKER: unknown

ABSTRACT. The Sentential Decision Diagram (SDD) is a recently proposed representation of Boolean functions, containing Ordered Binary Decision Diagrams (OBDDs) as a distinguished subclass. While OBDDs are characterized by total variable orders, SDDs are characterized more generally by structures called vtrees. As both OBDDs and SDDs have canonical representations, searching for OBDDs and SDDs of minimal size simplifies to searching for variable orders and vtrees, respectively. For OBDDs, there are effective heuristics for the dynamic ordering of variables, based on locally swapping variables. In this paper, we propose an analogous approach for SDDs which navigates the space of vtrees via two operations: one based on tree rotations and a second based on swapping children in a vtree. We propose a particular heuristic for dynamically searching the space of vtrees, showing that it can find SDDs that are an order-of-magnitude more concise than OBDDs found by CUDD.

17:00
Radial Restraint: A Semantically Clean Approach to Bounded Rationality for Logic Programs
SPEAKER: unknown

ABSTRACT. Declarative logic programs (LP) based on the well-founded semantics (WFS) are used for knowledge representation (KR), e.g., in databases, business rules, semantic web, and SILK. They represent logical non-monotonicity, and offer much better scalability than answer-set programs or first-order logic. In this paper, we present radial restraint: a novel approach to bounded rationality in LP. Radial restraint is parameterized by a norm that measures the syntactic complexity of a term, along with an abstraction function based on that norm. When a term exceeds a bound for the norm, the term is assigned the WFS's third truth-value of undefined. If the norm is finitary, radial restraint guarantees finiteness of models and decidability of inferencing, even when logical functions are present. It further guarantees soundness, even when non-monotonicity is present. We give a fixed-point semantics for radially restrained well-founded models which soundly approximate well-founded models. We also show how to perform correct inferencing relative to such models, via SLG_ABS, an extension of tabled SLG resolution that uses norm-based abstraction functions. Finally we discuss how SLG_ABS is implemented in theengine of XSB Prolog, and scales to knowledge bases with more than 10^8 rules and facts.

17:15
Backdoors to Normality for Disjunctive Logic Programs

ABSTRACT. Over the last two decades, propositional satisfiability (SAT) has become one of the most successful and widely applied techniques for the solution of NP-complete problems. The aim of this paper is to investigate theoretically how SAT can be utilized for the efficient solution of problems that are harder than NP or co-NP. In particular, we consider the fundamental reasoning problems in propositional disjunctive answer set programming (ASP), brave reasoning and cautious reasoning, which ask whether a given atom is contained in at least one or in all answer sets, respectively. Both problems are located at the second level of the Polynomial Hierarchy and thus assumed to be harder than NP or co-NP. One cannot transform these two reasoning problems to SAT in polynomial time, unless the Polynomial Hierarchy collapses. We show that certain structural aspects of disjunctive logic programs can be utilized to break through this complexity barrier, using new techniques from Parameterized Complexity. In particular, we exhibit transformations from brave and cautious reasoning to SAT that run in time O(2^k n^2) where k is a structural parameter of the instance and n the input size. In other words, the reduction is fixed-parameter tractable for parameter k. As the parameter k we take the size of a smallest backdoor with respect to the class of normal (i.e., disjunction-free) programs. Such a backdoor is a set of atoms that when deleted makes the program normal. In consequence, the combinatorial explosion, which is expected when transforming a problem from the second level of the Polynomial Hierarchy to the first level, can now be confined to the parameter k, while the running time of the reduction is polynomial in the input size n, where the order of the polynomial is independent of k. We show that such a transformation is not possible if we consider backdoors with respect to tightness instead of normality.

17:30
Answering Counting Aggregate Queries over Ontologies of DL-Lite Family
SPEAKER: unknown

ABSTRACT. One of the main applications of description logics is the ontology-based data access model, which requires algorithms for query answering over ontologies. In fact, some description logics, like those in the DL-Lite family, are designed so that simple queries, such as conjunctive queries, are efficiently computable. In this paper we study counting aggregate queries over ontologies, i.e. queries which use aggregate functions COUNT and COUNT DISTINCT. We propose an intuitive semantics for certain answers for these queries, which conforms to the open world assumption. We compare our semantics with other approaches that have been proposed in different contexts. We establish data and combined computational complexity for the problems of answering counting aggregate queries over ontologies for several variants of DL-Lite.

16:45-17:45 Session 29D: Kernels and Density Estimation (AAAI)
16:45
A Kernel Density Estimate-based approach to Component Goodness Modeling
SPEAKER: unknown

ABSTRACT. Intermittent fault localization approaches account for the fact that faulty components may fail intermittently by considering a parameter (known as goodness) that quantifies the probability that faulty components may still exhibit correct behavior. Current, state-of-the-art approaches (1) assume that this goodness probability is context independent and (2) do not provide means for integrating past diagnosis experience in the diagnostic mechanism. In this paper, we present a novel approach, coined Non-linear Feedback-based Goodness Estimate (NFGE), that uses Kernel Density Estimations (KDE) to address such limitations. We evaluated the approach with both synthetic and real data, yielding lower estimation errors, thus increasing the diagnosis performance.

17:00
On Power-Law Kernels, Corresponding Reproducing Kernel Hilbert Space and Applications

ABSTRACT. The role of kernels is central to machine learning. Motivated by the importance of power-law distributions in statistical modeling, in this paper, we propose the notion of power-law kernels to investigate power-laws in learning problem. We propose two power-law kernels by generalizing Gaussian and Laplacian kernels. This generalization is based on distributions, arising out of maximization of a generalized information measure known as nonextensive entropy that is very well studied in statistical mechanics. We prove that the proposed kernels are positive definite, and provide some insights regarding the corresponding Reproducing Kernel Hilbert Space (RKHS). We also study practical significance of both kernels in classification and regression, and present some simulation results.

17:15
Symmetry-Aware Marginal Density Estimation

ABSTRACT. Concepts from the field of statistics are leveraged to analyze and improve the scalability of inference in large probabilistic models that exhibit symmetries. A novel Rao-Blackwell marginal density estimator is introduced and shown both analytically and empirically to outperform standard estimators. The developed theory and algorithms apply to a broad class of probabilistic models including statistical relational models considered not susceptible to lifted probabilistic inference.

17:30
A Robust Bayesian Truth Serum for Non-binary Signals
SPEAKER: unknown

ABSTRACT. Several mechanisms have been proposed for incentivizing truthful reports of a private signals owned by rational agents, among them the peer prediction method and the Bayesian Truth Serum. The robust Bayesian truth serum (RBTS) for small populations and binary signals is particularly interesting since it does not require a common prior to be known to the mechanism. We further analyze the problem of the common prior not known to the mechanism and give several results regarding the restrictions that need to be placed in order to have an incentive compatible mechanism. Moreover, we construct a Bayes-Nash incentive compatible scheme called multi-valued RBTS that generalizes RBTS to operate on both small populations and non-binary signals.

16:45-17:45 Session 29E: Spotlights and Senior Members (AAAI)
16:45
AIIDE: What's Hot
SPEAKER: unknown

ABSTRACT. What's Hot in Games from the AIIDE Perspective: Player Modeling

17:00
LSG: Challenges
SPEAKER: unknown

ABSTRACT. About the Lemonade Stand Competition and unsolvable games.

17:15
ISWC: Best Paper: Discovering Concept Coverings in Ontologies of Linked Data Sources
SPEAKER: unknown
16:45-17:55 Session 29F: Medical Applications (IAAI)
16:45
Deployed: Integrating Digital Pens in Breast Imaging for Instant Knowledge Acquisition
SPEAKER: unknown

ABSTRACT. Future radiology practices assume that the radiology reports should be uniform, comprehensive, and easily managed. This means that reports must be "readable" to humans and machines alike. In order to improve reporting practices in breast imaging, we allow the radiologist to write structured reports with a special pen on paper with an invisible dot pattern. In this way, we provide a knowledge acquisition system for printed mammography patient forms for the combined work with printed and digital documents. In this domain, printed documents cannot be easily replaced by computer systems because they contain free form sketches and textual annotations, and the acceptance of traditional PC reporting tools is rather low among the doctors. This is due to the fact that current electronic reporting systems significantly add to the amount of time it tasks to complete the reports. We describe our real-time digital paper application and focus on the use case study of our deployed application. We think that our results motivate the design and implementation of intuitive pen-based user interfaces for the medical reporting process and similar knowledge work domains. Our system imposes only minimal overhead on traditional form-filling processes and provides for a direct, ontology-based structuring of the user input for semantic search and retrieval applications, as well as other applied artificial intelligence scenarios which involve manual form-based data acquisition.

17:15
Emerging: Policies to Optimize Work Performance and Thermal Safety in Exercising Humans
SPEAKER: unknown

ABSTRACT. Emergency workers engaged in strenuous work in hot environments risk overheating and mission failure. We describe a real-time application that would reduce these risks in terms of a real-time thermal-work strain index (SI) estimator; and a Markov Decision Process (MDP) to compute optimal work rate policies. We examined the thermo-physiological responses of 14 fit and experienced U.S. Army Ranger students (26±4 years 1.77±0.04 m; 78.3±7.3 kg) who participated in a strenuous 8 mile time-restricted pass/fail road march conducted under thermally stressful conditions. A thermoregulatory model was used to derive SI state transition probabilities and model the students' observed and policy driven movement rates. We found that policy end-state SI was significantly lower than SI when modeled using the student's own movement rates (3.94±0.88 vs. 5.62±1.20, P<0.001). We also found an inverse relationship between our policy impact and maximum SI (r=0.64 P<0.05). These results suggest that modeling real world missions as an MDP can provide optimal work rate policies that improve thermal safety and allow students to finish in a 'fresher' state. Ultimately, SI state estimation and MDP models incorporated into wearable physiological monitoring systems could provide real-time work rate guidance, thus minimizing thermal work-strain while maximizing the likelihood of accomplishing mission tasks.

17:35
Emerging: Physical Activity Recognition from Accelerometer Data Using a Multi-Scale Ensemble Method
SPEAKER: unknown

ABSTRACT. Accurate and detailed measurement of an individual's physical activity is a key requirement for helping researchers understand the relationship between physical activity and health. Accelerometers have become the method of choice for measuring physical activity due to their small size, low cost, convenience and their ability to provide objective information about physical activity. The challenge, however, is in interpreting accelerometer data once it has been collected. In this work, we applied data mining algorithms to the problem of classifying a time series as being one of several possible physical activity types. We employed a simple but effective approach of dividing the accelerometer data into short non-overlapping windows, converting each window into a feature vector, and treating each feature vector as an i.i.d training instance for a supervised learning algorithm. In addition, we improved on this simple approach with a multi-scale ensemble method (SWEM) that did not need to commit to a single window size and was able to leverage the fact that physical activities produced time series with repetitive patterns and discriminative features for physical activity occurred at different temporal scales.

19:00-22:00 Session 30: AAAI Banquet (AAAI)