PROGRAM FOR TUESDAY, JULY 16TH, 2013
View: session overviewtalk overviewside by side with other conferences
09:00 | AAAI-13 Keynote Address: Grounded Language Learning SPEAKER: Raymond Mooney ABSTRACT. Most approaches to semantics in computational linguistics represent meaning in terms of words or abstract symbols. Grounded-language research bases the meaning of natural language on perception and/or action in the (real or virtual) world. Machine learning has become the most effective approach to constructing natural-language systems; however, current methods require a great deal of laboriously annotated training data. Ideally, a computer would be able to acquire language like a child, by being exposed to language in the context of a relevant but ambiguous environment, thereby grounding its learning in perception and action. We will review recent research in grounded language learning and discuss future directions. |
10:20 | AAAI/IAAI Joint Invited Talk: Telling Stories at Internet Scale SPEAKER: Larry Birnbaum ABSTRACT. Taking full advantage of the massive scale of "big data" will require technologies for analyzing and communicating these data to people, in terms they can understand and act on, at an equally massive scale. The automatic generation of narratives from data offers the promise of meeting this critical need. Our technology, which leverages human editorial judgment at scale, is today generating millions of stories from data, including highly personalized stories, in domains varying from business operations, to sports, education, medicine, and finance. The resulting narratives are often indistinguishable from those written by human analysts and writers. |
11:20 | Time-dependent Trajectory Regression on Road Networks via Multi-Task Learning SPEAKER: unknown ABSTRACT. Road travel costs are important knowledge hidden in large-scale GPS trajectory data set, the discovery of which can benefit many applications such as intelligent route planning and automatic driving navigation. While there are previous studies which tackled this task by modeling it as a regression problem with spatial smoothness taken into account, they unreasonably assumed that the latent cost of each road remains unchanged over time. Other works on route planning and recommendation that have considered temporal factors simply assumed temporal dynamics be known in advance as a parametric function over time, which is not faithful to reality. To overcome these limitations, in this paper, we propose an extension to a previous static trajectory regression framework by learning the temporal dynamics of road travel costs in an innovative non-parametric manner which can effectively overcome temporal sparsity problem. In particular, we unify multiple different trajectory regression problems in a multi-task framework by introducing a novel cross-task regularization factor which encourages temporal smoothness on the change of road travel costs. We then propose an efficient block coordinate descent method to solve the resulting problem by exploiting its separable structures and prove its convergence to global optimum. Experiments conducted on both synthetic and real data sets demonstrate the effectiveness of our method and its improved accuracy on travel time prediction. |
11:35 | A Concave Conjugate Approach for Nonconvex Penalized Regression with the MCP Penalty SPEAKER: unknown ABSTRACT. The minimax concave plus penalty (MCP) function has been demonstrated to be effective in nonconvex penalization for feature selection. In this paper we propose a novel construction approach for MCP. In particular, we show that MCP can be derived from a concave conjugate of the Euclidean distance function. This construction approach in turn leads us to an augmented Lagrange multiplier method for solving the penalized regression problem with the MCP penalty. In our method each feature corresponds to a distinct tuning parameter, and these tuning parameters can be automatically updated. We also develop a d.c. (difference of convex functions) programming approach for the penalized regression problem using the notion of concave conjugate. We show that the augmented Lagrange multiplier method degenerates into the d.c. method under specific conditions. We conduct experimental analysis on a set of simulated data. The result is encouraging. |
11:50 | Lazy Gaussian Process Committee for Real-Time Online Regression SPEAKER: Han Xiao ABSTRACT. A significant problem of Gaussian process (GP) is its unfavorable scaling with a large amount of data. To overcome this issue, we present a novel GP approximation scheme for online regression. Our model is based on a combination of multiple GPs with random hyperparameters. The model is trained by incrementally allocating new examples to a selected subset of GPs. The selection is carried out efficiently by optimizing a submodular function. Experiments on real-world data sets showed that our method outperforms existing online GP regression methods in both accuracy and efficiency. The applicability of the proposed method is demonstrated by the mouse-trajectory prediction in an Internet banking scenario. |
12:05 | Continuous Conditional Random Fields for Efficient Regression in Large Fully Connected Graphs SPEAKER: unknown ABSTRACT. When used for structured regression, powerful Conditional Random Fields (CRFs) are typically restricted to modeling effects of interactions among examples in local neighborhoods. Using more expressive representation would result in dense graphs, making these methods impractical for large-scale applications. To address this issue, we propose an effective CRF model with linear scale-up properties regarding approximate learning and inference for structured regression on large, fully connected graphs. The proposed method is validated on real-world large-scale problems of image de-noising and remote sensing. In conducted experiments, we demonstrated that dense connectivity provides an improvement in prediction accuracy. Inference time of less than a second on graphs with billions of edges makes the proposed model an attractive tool for large-scale, structured regression problems. |
11:20 | Reduce and Re-Lift: Bootstrapped Lifted Likelihood Maximization for MAP SPEAKER: Fabian Hadiji ABSTRACT. By handling whole sets of indistinguishable objects together, lifted belief propagation approaches have rendered large, previously intractable, probabilistic inference problems quickly solvable. In this paper, we show that Kumar and Zilberstein's likelihood maximization (LM) approach to MAP inference is liftable, too, and actually provides additional structure for optimization. Specifically, it has been recognized that some pseudo marginals may converge quickly, turning intuitively into pseudo evidence. This additional evidence typically changes the structure of the lifted network: it may expand or reduce it. The current lifted network, however, can be viewed as an upper bound on the size of the lifted network required to finish likelihood maximization. Consequently, we re-lift the network only if the pseudo evidence yields a reduced network, which can efficiently be computed on the current lifted network. Our experimental results on Ising models, image segmentation and relational entity resolution demonstrate that this bootstrapped LM via "reduce and re-lift" finds MAP assignments comparable to those found by the original LM approach, but in a fraction of the time. |
11:35 | m-Transportability: Transportability of Causal Effect from Multiple Environments SPEAKER: unknown ABSTRACT. We introduce m-transportability, a generalization of transportability, which offers a license to transfer causal information obtained from experiments and observations in m>=1 source environments to estimate a causal effect in a given target environment. We provide a novel characterization of m-transportability that directly exploits the completeness of do-calculus to obtain the necessary and sufficient conditions for m-transportability. We provide a sound and complete algorithm for deciding m-transportability that: (i) indicates non-m-transportability if a causal relation is not m-transportable from a given set of m source environments to a specified target environment; (ii) produces a transport formula, that is, a recipe for combining experimental information from m source environments with only observational information from the target environment to synthesize an estimate of the desired causal effect, otherwise. |
11:50 | RockIt: Exploiting Parallelism and Symmetry for MAP Inference in Statistical Relational Models SPEAKER: Jan Noessner ABSTRACT. In this paper we present RockIt a maximum a-posteriori (MAP) query engine for statistical relational models. MAP inference in graphical models is an optimization problem and can naturally be mapped to integer linear programs (ILPs). With this paper, we present several optimizations for ILP translation of MAP queries including the meta algorithm Cutting Plane Aggregation (CPA). CPA exploits context-specific symmetries, that is, symmetries introduced by evidence and bundles large numbers of linear constraints. The resulting counting constraints lead to more compact ILPs and, more importantly, make the symmetry of the ground model explicit to state-of-the-art ILP solvers. Moreover, we parallelize all parts of the MAP inference pipeline in order to take advantage of multi-core architectures. We conducted numerous experiments on standard Markov logic networks (MLN) benchmarks, demonstrating that RockIt outperforms state-of-the-art systems such as Alchemy and Tuffy both in terms of efficiency and quality of results. |
12:05 | Causal Transportability with Limited Experiments SPEAKER: Elias Bareinboim ABSTRACT. We address the problem of transferring causal knowledge learned in one environment to another, potentially different environment, when only limited experiments may be conducted at the source. This generalizes the treatment of transportability introduced in [Pearl and Bareinboim, 2011; Bareinboim and Pearl, 2012b], which deals with transferring causal information when any experiment can be conducted at the source. Given that it is not always feasible to conduct certain controlled experiments, we consider the decision problem whether experiments on a selected subset Z of variables together with qualitative assumptions encoded in a diagram may render causal effects in the target environment computable from the available data. This problem, which we call z-transportability, reduces to ordinary transportability when Z is all-inclusive, and, like the latter, can be given syntactic characterization using the do-calculus [Pearl, 1995; 2000]. This paper establishes a necessary and sufficient condition for causal effects in the target domain to be estimable from both the non-experimental information available and the limited experimental information transferred from the source. We further provides a complete algorithm for computing the transport formula, that is, a way of fusing experimental and observational information to synthesize an unbiased estimate of the desired causal relation. |
11:20 | Graph Traversal Methods for Reasoning in Large Knowledge-Based Systems SPEAKER: unknown ABSTRACT. Commonsense reasoning at scale is a core problem for cognitive systems. In this paper, we discuss two ways in which heuristic graph traversal methods can be used to generate plausible inference chains. First, we discuss how Cyc’s predicate-type hierarchy can be used to get reasonable answers to queries. Second, we explain how connection graph-based techniques can be used to identify script-like structures. Finally, we demonstrate through experiments that these methods lead to significant improvement in accuracy for both Q/A and script construction. |
11:35 | Automatic Extraction of Efficient Axiom Sets from Large Knowledge Bases SPEAKER: unknown ABSTRACT. Efficient reasoning in large knowledge bases is an important problems for cognitive systems. Hand-optimization of reasoning becomes impractical as KBs grow, and impossible as knowledge is automatically added via knowledge capture or machine learning. This paper describes a method for automatic extraction of axioms for efficient inference over large knowledge bases, given a set of query types and information about the types of facts in the KB currently as well as what might be learned. We use the highly right skewed distribution of predicate connectivity in large knowledge bases to prune intractable regions of the search space. We show the efficacy of these techniques via experiments using queries from a cognitive system which does learning by reading. Results show that these methods lead to an order of magnitude improvement in time with minimal loss in coverage. |
11:50 | Preemptive Strategies for Overcoming the Forgetting of Goals SPEAKER: unknown ABSTRACT. Maintaining and pursuing multiple goals over varying time scales is an important ability for artificial agents in many cognitive architectures. Goals that remain suspended for long periods, however, are prone to be forgotten. This paper presents a class of preemptive strategies that allow agents to selectively retain goals in memory and to recover forgotten goals. Preemptive strategies work by retrieving and rehearsing goals at triggers, which are either periodic or are predictive of the opportunity to act. Since cognitive architectures contain common hierarchies of memory systems and share similar forgetting mechanisms, these strategies work across multiple architectures. We evaluate their effectiveness in a simulated mobile robot controlled by Soar, and demonstrate how preemptive strategies can be adapted to different environments and agents. |
12:05 | Learning to Efficiently Pursue Communication Goals on the Web with the GOSMR Architecture SPEAKER: Kevin Gold ABSTRACT. We present GOSMR ("goal oriented scenario modeling robots"), a cognitive architecture designed to show coordinated, goal-directed behavior when using networked computer applications, focusing on the web browser as a case study. The architecture combines a variety of artificial intelligence techniques, including planning, temporal difference learning, elementary reasoning over uncertainty, and communication, but is designed to be computationally lightweight. Its intended use is to drive applications on large-scale cyber security experiments in which users' adaptation in the face of resource denial should be intelligent but varied. The planning system performs temporal difference learning of action times, discounts goals according to hyperbolic discounting of time-to-completion and chance of success, takes into account the assertions of other agents, and separates abstract action from site-specific affordances. Our experiment, in which agents learn to prefer a social networking style site for sending and receiving messages, shows that utility-proportional goal selection is a reasonable alternative to Boltzmann goal selection for producing a rational mix of behavior. |
12:20 | Fast, Near-Optimal Computation for Multi-robot Path Planning on Graphs SPEAKER: unknown ABSTRACT. We report a new method for computing near optimal makespan solutions to multi-robot path planning problem on graphs. Our focus here is with hard instances - those with up to 85% of all graph nodes occupied by robots. Our method yields 100-1000x speedup compared with existing methods. At the same time, our solutions have much smaller and often optimal makespans. |
12:22 | Uncertainty Reduction For Active Image Clustering via a Hybrid Global-Local Uncertainty Model SPEAKER: unknown ABSTRACT. We propose a novel combined global/local model for active semi-supervised spectral clustering based on the principle of uncertainty reduction. We iteratively compute the derivative of the eigenvectors produced by spectral decomposition with respect to each item/image, and combine this with local label entropy provided by the current clustering results in order to estimate the uncertainty reduction potential of each item in the dataset. We then generate pairwise queries with respect to the best candidate item and retrieve the needed constraints from the user. We evaluate our method using three different image datasets---faces, leaves and dogs, and consistently demonstrate performance superior to the current state-of-the-art. |
12:24 | Towards Joint Inference for Complex Ontology Matching SPEAKER: Jan Noessner ABSTRACT. In this paper, we show how to model the matching problem as a problem of joint inference. In opposite to existing approaches, we distinguish between the layer of labels and the layer of concepts and properties. Entities from both layers appear as first class citizens in our model. We present an example and explain the benefits of our approach. Moreover, we argue that our approach can be extended to generate correspondences involving complex concept descriptions. |
12:26 | AMRec: An Intelligent System for Academic Method Recommendation SPEAKER: unknown ABSTRACT. Finding new academic methods for research problems is the key task in a researcher’s research career. It is usually very difficult for new researchers to find good methods for their research problems since they lack of research experiences. In order to help researchers carry out their researches in a more convenient way, we describe a novel recommendation system called AMRec to recommend new academic methods for research problems in this paper. Our proposed system first extracts academic concepts (Tasks and Methods) and their relations from academic literatures, and then leverages the regularized matrix factorization model for academic method recommendation. Preliminary evaluation results are also reported and discussed. |
12:28 | An Ensemble of Linearly Combined Reinforcement-Learning Agents SPEAKER: unknown ABSTRACT. Reinforcement-learning (RL) algorithms are often tweaked and tuned to specific environments when applied, calling into question whether learning can truly be considered autonomous in these cases. In this work, we show how more robust learning across environments is possible by adopting an ensemble approach to reinforcement learning. Our approach learns a weighted linear combination of Q-values from multiple independent learning algorithms. In our evaluations in generalized RL environments, we find that the algorithm compares favorably to the best tuned algorithm. Our work provides a promising basis for further study into the use of ensemble methods in RL. |
13:45 | AAAI-13 Invited Talk: Aerial Robot Swarms SPEAKER: Vijay Kumar ABSTRACT. Autonomous microaerial robots can operate in three-dimensional unstructured environments, and offer many opportunities for environmental monitoring, search and rescue, and first response. I will describe the challenges in developing small, agile robots and our recent work in the areas of (1) control and planning, (2) state estimation and mapping, and (3) coordinating large teams of robots, with applications to cooperative manipulation and transport, construction, and exploration and mapping. |
13:45 | EAAI-13 Teaching and Mentoring Session 1 SPEAKER: unknown |
14:45 | Multi-Armed Bandit with Budget Constraint and Variable Costs SPEAKER: unknown ABSTRACT. We study the multi-armed bandit problems with budget constraint and variable costs (MAB-BV). In this setting, pulling an arm will receive a random reward together with a random cost, and the objective of an algorithm is to pull a sequence of arms in order to maximize the expected total reward with the costs of pulling those arms complying with a budget constraint. This new setting models many Internet applications (e.g., ad exchange, sponsored search, and cloud computing) in a more accurate manner than previous settings where the pulling of arms is either costless or with a fixed cost. We propose two UCB based algorithms for the new setting. The first algorithm needs prior knowledge about the lower bound of the expected costs when computing the exploration term. The second algorithm eliminates this need by estimating the minimal expected costs from empirical observations, and therefore can be applied to more real-world applications where prior knowledge is not available. We prove that both algorithms have nice learning abilities, with regret bounds of $O(\ln B)$. Furthermore, we show that when applying our proposed algorithms to a previous setting with fixed costs (which can be regarded as our special case), one can improve the previously obtained regret bound. Our simulation results on real-time bidding in ad exchange verify the effectiveness of the algorithms and are consistent with our theoretical analysis. |
15:00 | Basis Adaptation for Sparse Nonlinear Reinforcement Learning SPEAKER: Sridhar Mahadevan ABSTRACT. This paper presents a new approach to basis adaptation in reinforcement learning (RL) using the recently proposed {\em mirror-descent} framework. Mirror descent can be viewed as an enhanced gradient method, particularly suited to minimization of convex functions in high-dimensional spaces. Unlike traditional gradient methods, mirror descent undertakes gradient updates of weights in both the dual space and primal space, which are linked together using a Legendre transform. Mirror descent can be viewed as a proximal algorithm where the distance generating function used is a Bregman divergence. We introduce a general framework for nonlinear separable value function approximation based on finding Frechet gradients of an error function based on variable projection functionals. We then show how to combine basis adaptation methods with proximal-gradient based temporal-difference (TD) methods and present a new class of regularized TD methods, which combine feature selection through sparse $L_1$ regularization and basis adaptation. Experimental results are provided to illustrate and validate the approach. |
15:15 | Pruning for Monte Carlo Distributed Reinforcement Learning in Decentralized POMDPs SPEAKER: Bikramjit Banerjee ABSTRACT. Decentralized partially observable Markov decision processes (Dec-POMDPs) offer a powerful modeling technique for realistic multi-agent coordination problems under uncertainty. Prevalent solution techniques are centralized and assume prior knowledge of the model. Recently a Monte Carlo based distributed reinforcement learning approach was proposed, where agents take turns to learn best responses to each other’s policies. This promotes decentralization of the policy computation problem, and relaxes reliance on the full knowledge of the problem parameters. However, this Monte Carlo approach has a large sample complexity, which we address in this paper. In particular, we propose and analyze a modified version of the previous algorithm that adaptively eliminates parts of the experience tree from further exploration, thus requiring fewer samples while ensuring unchanged confidence in the learned value function. Experiments demonstrate significant reduction in sample complexity – the maximum reductions ranging from 61% to 93% over different benchmark Dec-POMDP problems – with the final policies being often better due to more focused exploration. |
15:30 | Structured Kernel-Based Reinforcement Learning SPEAKER: unknown ABSTRACT. Kernel-based reinforcement learning (KBRL) is a popular approach to learning non-parametric value function approximations. In this paper, we present structured KBRL, a paradigm for kernel-based RL that allows for modeling independencies in the transition and reward models of problems. Real-world problems often exhibit this structure and can be solved more efficiently when it is modeled. We make three contributions. First, we motivate our work, define a structured backup operator, and prove that it is a contraction. Second, we show how to evaluate our operator efficiently. Our analysis reveals that the fixed point of the operator is the optimal value function in a special factored MDP. Finally, we evaluate our method on a synthetic problem and compare it to two KBRL baselines. In most experiments, we learn better policies than the baselines from an order of magnitude less training data. |
14:45 | Incremental Learning Framework for Indoor Scene Recognition SPEAKER: unknown ABSTRACT. This paper presents a novel framework for online incremental place recognition in an indoor environment. The framework addresses the scenario in which scene images are gradually obtained during long-term operation in the real-world indoor environment. Multiple users may interact with the classification system and confirm either current or past prediction results; the system then immediately updates itself to improve the classification system. This framework is based on the proposed n-value self-organizing and incremental neural network (n-SOINN), which has been derived by modifying the original SOINN to be appropriate for use in scene recognition. The evaluation was performed on the standard MIT 67-category indoor scene dataset and shows that the proposed framework achieves the same accuracy as that of the state-of-the-art offline method, while the computation time of the proposed framework is significantly faster and fully incremental update is allowed. Additionally, a small extra set of training samples is incrementally given to the system to simulate the incremental learning situation. The result shows that the proposed framework can leverage such additional samples incrementally and achieve the state-of-the-art result. |
15:00 | Video Saliency Detection via Dynamic Consistent Spatio-Temporal Attention Modelling SPEAKER: unknown ABSTRACT. Human vision system actively seeks salient regions and movements in video sequences to reduce the search effort. Modeling computational visual saliency map provides important information for semantic understanding in many real world applications. In this paper, we propose a novel video saliency detection model for detecting the attended regions that correspond to both interesting objects and dominant motions in video sequences. In spatial saliency map, we in-herit the classical bottom-up spatial saliency map based on intensity, color, contrast, and orientation features in pixel-level. In temporal saliency map, a novel optical flow model is proposed based on the dynamic consistency of motion. The spatial and the temporal saliency maps are constructed and further fused together to create a novel attention model. The proposed attention model is evaluated on three video datasets. Empirical validations demonstrate the salient regions detected by our dynamic consistent saliency map highlight the interesting objects effectively and efficiency. More importantly, the automatically video attended regions detected by proposed attention model are consistent with the ground truth saliency maps of eye movement data. |
15:15 | Gradient Networks: Explicit Shape Matching without Extracting Edges SPEAKER: Edward Hsiao ABSTRACT. We present a novel framework for shape-based template matching in images. While previous approaches required brittle contour extraction, considered only local information, or used coarse statistics, we propose to match the shape explicitly on low-level gradients by formulating the problem as traversing paths in a gradient network. We evaluate our algorithm on a challenging dataset of objects in cluttered environments and demonstrate significant improvement over state-of-the-art methods for shape matching and object detection. |
15:30 | Vesselness Features and the Inverse Compositional AAM for Robust Face Recognition Using Thermal IR SPEAKER: unknown ABSTRACT. Over the course of the last decade, infrared (IR) and particularly thermal IR imaging based face recognition has emerged as a promising complement to conventional, visible spectrum based approaches which continue to struggle when applied in the real world. While inherently insensitive to visible spectrum illumination changes, IR images introduce specific challenges of their own, most notably sensitivity to factors which affect facial heat emission patterns, e.g. emotional state, ambient temperature, and alcohol intake. In addition, facial expression and pose changes are more difficult to correct in IR images because they are less rich in high frequency detail which is an important cue for fitting any deformable model. In this paper we describe a novel method which addresses these major challenges. Specifically, to normalize for pose and facial expression changes we generate a synthetic frontal image of a face in a canonical, neutral facial expression from an image of the face in an arbitrary pose and facial expression. This is achieved by piecewise affine warping which follows active appearance model (AAM) fitting. This is the first publication which explores the use of an AAM on thermal IR images; we propose a pre-processing step which enhances detail in thermal images, making AAM convergence faster and more accurate. To overcome the problem of thermal IR image sensitivity to the exact pattern of facial temperature emissions we describe a representation based on reliable anatomical features. In contrast to previous approaches, our representation is not binary; rather, our method accounts for the reliability of the extracted features. This makes the proposed representation much more robust both to pose and scale changes. The effectiveness of the proposed approach is demonstrated on the largest public database of thermal IR images of faces on which it achieves perfect recognition performance and significantly outperforms previously described methods. |
14:45 | Modern Dynamic Organ Exchanges: Algorithms and Market Design SPEAKER: Tuomas Sandholm ABSTRACT. In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this is NP-hard. It was one of the main obstacles to a national kidney exchange. We developed the first (and still only) algorithm capable of clearing these exchanges optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store. On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. Furthermore, clearing is actually an online problem where patient-donor pairs and altruistic donors appear and expire over time. We first developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. Such algorithms tend to be too compute-intensive at run time, so recently we developed a general approach for giving batch algorithms guidance about the future without a run-time hit. It learns potentials of elements of the problem, and then uses them in each batch clearing. I will share experiences from using our algorithms to run the UNOS US-wide kidney exchange since its inception two and a half years ago, and two regional ones before that. We introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I will present results – both theoretical and experimental – on the role of long chains. I will present probabilistic planning algorithms that are robust against last-minute execution failures - currently the main challenge in kidney exchange. I will discuss how general-purpose integer program solvers do not scale to this task, and will present a brand new branch-and-price algorithm that does. I will also give an overview about other issues in kidney exchanges such as sniping in the context of competing exchanges, and transplant centers' incentives to hide some of their pairs. Finally, I will discuss simulation results about the possibility of liver lobe exchanges and cross-organ exchanges. The talk covers material from the following papers of ours. In addition, the talk will cover results by Alvin Roth, Utku Unver, Itai Ashlagi, and others. - Algorithms for Robust Kidney Exchange Clearing. (With Dickerson, J. and Procaccia, A.) - Liver and Multi-Organ Exchange. (With Dickerson, J.) Under review. - Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. AAAI-12. (With Dickerson, J. and Procaccia, A.) - Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. AAMAS-12. (With Dickerson, J. and Procaccia, A.) - Online Stochastic Optimization in the Large: Application to Kidney Exchange. IJCAI-09. (With Awasthi, P.) - A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), March 2009. (With Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Ünver, U., and Montgomery, R.) - Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. EC-07. (With Abraham, D. and Blum, A.) |
15:15 | Data Mining Social Media for Public Health Applications SPEAKER: Henry Kautz ABSTRACT. There is much activity in data mining social media for marketing campaigns, financial prediction, and similar purposes. Recently, however, a smaller group of researchers have begun to leverage this sensor network for a singular public good: modeling public health at a population scale. Researchers have shown, for example, that Twitter postings can be used to track and predict influenza and detect affective disorders such as depression. Such work provides strong evidence that there is a strong health ``signal'' in social media. |
14:45 | EAAI-13 Teaching and Mentoring Session 2 SPEAKER: unknown |
16:15 | EAAI Senior Member Paper: Meeting the Responsibility to Explain AI SPEAKER: unknown |
16:45 | A General Formal Framework for Pathfinding Problems with Multiple Agents SPEAKER: Peter Schüller ABSTRACT. Pathfinding for a single agent is the problem of planning a route from an initial location to a goal location in an environment, going around obstacles. Pathfinding for multiple agents also aims to plan such routes for each agent, subject to different constraints, such as restrictions on the length of each path or on the total length of paths, no self-intersecting paths, no intersection of paths/plans, no crossing/meeting each other. It also has variations for finding optimal solutions, e.g., with respect to the maximum path length, the sum of plan lengths. These problems are important for many real-life applications, such as motion planning, vehicle routing, environmental monitoring, patrolling, computer games. Motivated by such applications, we introduce a formal framework that is general enough to address all these problems: we use the expressive high-level representation formalism and efficient solvers of the declarative programming paradigm Answer Set Programming. We also introduce heuristics to improve the computational efficiency and/or solution quality. We show the applicability and usefulness of our framework by experiments, with randomly generated problem instances on a grid, on a real-world road network, and on a real computer game terrain. |
17:00 | Multi-Cycle Query Caching in Agent Programming SPEAKER: unknown ABSTRACT. In many logic-based BDI agent programming languages, plan selection involves inferencing over some underlying knowledge representation. While context-sensitive plan selection facilitates the development of flexible, declarative programs, the overhead of evaluating repeated queries to the agent's beliefs and goals can result in poor run time performance. In this paper we present an approach to multi-cycle query caching for logic-based BDI agent programming languages. We extend the abstract performance model presented in (Alechina et al 2012) to quantify the costs and benefits of caching query results over multiple deliberation cycles. We also present results of experiments with prototype implementations of both single- and multi-cycle caching in three logic-based BDI agent platforms, which demonstrate that significant performance improvements are achievable in practice. |
17:15 | Liberal Safety for Answer Set Programs with External Sources SPEAKER: unknown ABSTRACT. Answer set programs with external source access may introduce new constants that are not present in the program, which is known as value invention. As naive value invention leads to programs with infinite grounding and answer sets, syntactic safety criteria are imposed on programs. However, traditional criteria are in many cases unnecessarily strong and limit expressiveness. We present liberal domain-expansion (de-) safe programs, a novel generic class of answer set programs with external source access that has a finite grounding and allows for value invention. De-safe programs use so-called term bounding functions as a parameter for modular instantiation with concrete---e.g., syntactic or semantic or both---safety criteria. This ensures extensibility of the approach in the future. We provide concrete instances of the framework and develop an operator that can be used for computing a finite grounding. Finally, we discuss related notions of safety from the literature, and show that our approach is strictly more expressive. |
17:30 | Domain-Specific Heuristics in Answer Set Programming SPEAKER: unknown ABSTRACT. We introduce a general declarative framework for incorporating domain-specific heuristics into ASP solving. We accomplish this by extending the first-order modeling language of ASP by a distinguished heuristic predicate. The resulting heuristic information is processed as an equitable part of the logic program and subsequently exploited by the solver when it comes to non-deterministically assigning a truth value to an atom. We implemented our approach as a dedicated heuristic in the ASP solver clasp and show its great prospect by an empirical evaluation. |
16:45 | Symbiotic-Autonomous Intelligent Robots SPEAKER: Manuela Veloso ABSTRACT. In this presentation, we will contribute the research and development we successfully pursue on effective mobile intelligent robots that service users in multiple different tasks. We overview the multiple aspects of our intelligent mobile CoBot robots that have been autonomously acting in our multi-floor environment, navigating so far for more than 200km. Users request tasks from CoBot using a web-based interface, and CoBot plans, localizes, and autonomously navigates between floors of the building. More importantly, the CoBot robot recognizes its perceptual, cognitive, and actuation limitations, and is capable to proactively ask for help or check the web, in a {\it symbiotic} relationship with humans and the web. We present the details of such challenging deployment, in particular the effective real-time depth-camera based localization and navigation algorithms, the symbiotic human-robot interaction approach, the multi-task dynamic planning and scheduling algorithm, the safety execution, the exploration and learning from the web. We show multiple illustrations of the robot performance, including a comprehensive analysis of extensive deployment results. |
17:15 | RuleML: What's Hot SPEAKER: unknown ABSTRACT. methods for automated translation between business and legal regulation written in natural language, and formal rules; papers on methods for visualization of formal rules; and integration of machine learning techniques and methods for reasoning with formal rules. |
17:30 | RuleML: Computing the Stratified Well-Founded Semantics over Big Data through Mass Parallelization SPEAKER: Ilias Tachmazidis ABSTRACT. Increasingly huge amounts of data are published on the Web, and generated from sensors and social media. This Big Data challenge poses new scientific and technological challenges and create new opportunities - thus the increasing attention in academia and industry. Traditionally, logic programming has focused on complex knowledge structures/programs, so the question arises whether and how it can work in the face of Big Data. In this paper, we examine how logic programming, under the well-founded semantics, can process huge amounts of data through mass parallelization. In particular, we propose and evaluate a parallel approach, using the MapReduce framework, under the assumption of stratification. Our experimental results indicate that our approach is scalable and that well-founded semantics can be applied to billions of facts. |
16:45 | EAAI-13 Discussion of Big Ideas in Education and AI SPEAKER: unknown |
17:45 | Evening poster session SPEAKER: unknown ABSTRACT. Reception/poster session including the Student Abstracts, Intern Posters, DC Abstracts, Poker Posters and EAAI posters. |