PROGRAM FOR WEDNESDAY, JULY 17TH, 2013
View: session overviewtalk overviewside by side with other conferences
09:00 | AAAI-13 Invited Talk: Fighting the Tuberculosis Pandemic Using Machine Learning SPEAKER: Kristin Bennett 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: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 | 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 | 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 | 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 | 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 SPEAKER: Sebastian Link 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 | 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 |
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 | 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. |
13:45 | AAAI-13 Invited Talk: Poker AI: Algorithms for Creating Game-Theoretic Strategies for Large Incomplete-Information Games SPEAKER: Tuomas Sandholm 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 | 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 SPEAKER: Brendan Lucier 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. |
16:45 | Conference Reviewing: Best Practices SPEAKER: Marie Desjardins 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 | 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 SPEAKER: Johannes Klaus Fichte 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 | 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 SPEAKER: Ambedkar Dukkipati 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 SPEAKER: Mathias Niepert 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. |