AAAI ON TUESDAY, JULY 16TH, 2013

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.

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.

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.

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.

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.

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.

ABSTRACT. This paper targets at automatically detecting and classifying user's suggestions from tweets. The short and informal nature of tweets, along with the imbalanced characteristics of suggestion tweets, makes the task extremely challenging. To this end, we develop a classification framework on Factorization Machines, which is effective and efficient especially in classification tasks with feature sparsity settings. Moreover, we tackle the imbalance problem by introducing cost-sensitive learning techniques in Factorization Machines. Extensively experimental studies on a manually annotated real-life data set show that the proposed approach significantly improves the baseline approach, and yields the precision of 71.06% and recall of 67.86%. We also investigate the reason why Factorization Machines perform better. Finally, we introduce the first manually annotated dataset for suggestion classification.

ABSTRACT. To help users quickly understand the major opinions from massive online reviews, it is important to automatically reveal the latent structure of aspects, sentiment polarities, and the association between them from the review texts. However, there is little work available about how to do them effectively. In this paper, we propose a Bayesian nonparametric model to discover an aspect-sentiment tree from unlabeled online reviews. The model discovers hierarchical structure of aspect-based sentiments, and we name it the HASM. In HASM, the whole structure is a tree. Each node itself is a two-level tree, whose root represents an aspect and the children represent the sentiment polarities associated with it. Each aspect or sentiment polarity is modeled as a distribution of words. To automatically extract both the structure and parameters of the tree, we use recursive Chinese Restaurant Process (rCRP) as the prior and jointly infer the aspect-sentiment tree from the review texts. We experiment with two real datasets and show that our model is comparable to two other hierarchical topic models in terms of quantitative measures of topic trees. We also show that our model achieves better sentence-level classification accuracy than previously proposed aspect-sentiment joint models.

ABSTRACT. This paper presents the results of developing subjectivity classifiers for Implicit Opinion Question (IOQ) identification. IOQs are defined as opinion questions with no opinion words. An IOQ example is “will the U.S. government pay more attention to the Pacific Rim?” Our analysis on community questions of Yahoo! Answers shows that a large proportion of opinion questions are IOQs. It is thus important to develop techniques to identify such questions. In this research, we first propose an effective framework based on mutual information and sequential pattern mining to construct an opinion lexicon that not only contains opinion words but also patterns. The discovered words and patterns are then combined with a machine learning technique to identify opinion questions. The experimental results on two datasets demonstrate the effectiveness of our approach.

ABSTRACT. Sentiment Similarity of word pairs reflects the distance between the words regarding their underlying sentiments. This paper intends to infer the sentiment similarity between word pairs with respect to their senses. To achieve this aim, we propose a probabilistic emotion-based approach that is built on a hidden emotional model in which the basic human emotions are considered as hidden. This leads to predict a vector of basic emotions for each sense of the words. The emotional vectors are employed to infer the sentiment similarity of word pairs. We apply the proposed sentiment similarity approach to address two main natural language processing tasks, namely, Indirect yes/no Question Answer Pairs (IQAPs) inference and Sentiment Orientation (SO) prediction. Extensive experiments demonstrate that the proposed approach can effectively capture the sentiment similarity of word pairs and significantly outperforms semantic similarity measures on the above tasks.

ABSTRACT. We describe the design of Instructor Rating Markets (IRMs) where human participants interact through intelligent automated market-makers in order to provide dynamic collective feedback to instructors on the progress of their classes. The markets are among the first to enable the controlled study of prediction markets where traders can affect the very outcomes they are trading on. More than 200 students across a university campus participated in markets for ten classes in the Fall 2010 semester. In this paper, we describe how we designed these markets in order to elicit useful information, and analyze data from the deployment. We show that market prices convey useful information on future instructor ratings and contain significantly more information than do past ratings. The bulk of useful information contained in the price of a particular class is provided by students who are in that class, showing that the markets are serving to disseminate insider information. At the same time, we find little evidence of attempted manipulation by raters. The markets are also a laboratory for comparing different market designs and the resulting price dynamics, and we show how they can be used to compare market making algorithms.

ABSTRACT. For decades researchers have struggled with the problem of envy-free cake cutting: how to divide a divisible good between multiple agents so that each agent likes his own allocation best. Although an envy-free cake cutting protocol was ultimately devised, it is unbounded, in the sense that the number of operations can be arbitrarily large, depending on the preferences of the agents. We ask whether bounded protocols exist when the agents' preferences are restricted. Our main result is an envy-free cake cutting protocol for agents with piecewise linear valuations, which requires a number of operations that is polynomial in natural parameters of the given instance.

ABSTRACT. With the ever increasing amount of data, particularly from search engines and social networks, stochastic optimization algorithms have become desirable for large-scale machine learning tasks because of their empirical efficiency and strong theoretical guarantees. However, a major challenge that is encountered is the cost of updating model parameters especially when the number of such parameters can be in the order of billions. Often times when parameters are updated, their values do not change significantly. As such, the cost of updating each parameter starts to outweigh the benefit.

In this paper, we introduce an efficient primal-dual based online algorithm that performs lazy updates to the parameter vectors and show that its performance is competitive with reasonable lazy-strategies which have the benefit of hindsight. We demonstrate the effectiveness of our frugal algorithm in the online portfolio selection domain where a trader has to pay proportional transaction costs every time his portfolio is updated. We show that our Online Lazy Updates (OLU) algorithm results in sparse updates of the portfolio vector and is robust to transaction costs with extensive experiments on two real world datasets.

ABSTRACT. To study mechanisms common across a variety of preference formalisms, we introduce a novel abstract preference framework. It makes no syntactic assumptions and uses most general representations to model the semantics. We use our abstract preference framework to study strong equivalence in preference formalisms, a version of equivalence that guarantees semantic-preserving replacements of parts of preference theories, and is fundamental for preference rewriting and modularity. To this end we identify abstract postulates in the language of preference frameworks, capturing natural semantic properties of preferences, and show that they lead to elegant characterizations, applicable in many practical settings. In a similar way, we study the separability of constraints and preferences. Preference languages have to capture constraints on the domain of interest that give rise to intended outcomes, and preferences that describe what is desirable. In many preference formalisms these two objectives are clearly separated, in some others they are not. We identify abstract postulates that guarantee separability of a preference formalism and lead to its "separated" variant.

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.

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.

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.

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.

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.

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.

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.

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.

ABSTRACT. Grand ideas and visions for search

ABSTRACT. Curing Robot Autism: A Challenge

ABSTRACT. In this paper, we investigate the problem of predicting people's professions under social context. Previous work considering clothing information as well as fore/background context preliminarily proves the feasibility of predicting professions. In this paper, we discuss this problem in a more general case --- multiple people in one photo with arbitrary poses, and argue that with appropriately built partial body features, spatial relations, and background context, a more appealing result is achieved by a probabilistic model. We conduct experiments on $14$ representative professions with over $7000$ images, and demonstrate the model's superiority with impressive results.

ABSTRACT. Despite the abundance of strategies in the literature on repeated negotiation under incomplete information, there is no single negotiation strategy that is optimal for all possible settings. Thus, agent designers face an ``algorithm selection'' problem--- which negotiation strategy to choose when facing a new negotiation. Our approach to this problem is to predict the performance of different strategies based on structural features of the domain and to select the negotiation strategy that is predicted to be most successful using a ``meta-agent''. This agent was able to outperform all of the finalists to the recent Automated Negotiation Agent Competition (ANAC). Our results have insights for agent-designers, demonstrating that ``a little learning goes a long way'', despite the inherent uncertainty associated with negotiation under incomplete information.

ABSTRACT. The increasing popularity of Twitter renders improved trustworthiness and relevance assessment of tweets much more important for search. However, given the limitations on the size of tweets, it is hard to extract measures for ranking from the tweet’s content alone. We propose a method of ranking tweets by generating a reputation score for each tweet that is based not just on content, but also additional information from the Twitter ecosystem that consists of users, tweets, and the webpages that tweets link to. The reputation score is used to power a novel method of ranking tweets by propagating the reputation over an agreement graph based on tweets’ content similarity. An evaluation of our method on 16 million tweets from the TREC 2011 Microblog Dataset shows that it doubles the precision over the baseline method, and performs better than the highest-performing method on the TREC 2011 Microblog dataset.

ABSTRACT. CP-nets (Boutilier et al., 1999) offer a potentially compact qualitative representation of human preferences that operate under ceteris paribus (“with all else being equal”) semantics. In this paper we present a novel algorithm through which an agent learns the preferences of a user. CP-nets are used to represent such preferences and are learned online through a series of queries generated by the algorithm. Our algorithm builds a CP-net for the user by creating nodes and initializing CPTs, then gradually adding edges and forming more complex CPTs consistent with responses to queries until a confidence parameter is reached.

ABSTRACT. We build turn-taking models for autonomous characters in language-based interactions with small groups of children. Two models explore the use of support vector machines given the same multimodal features, but different methods for collecting turn-taking labels.

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.

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.

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.

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.

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.

ABSTRACT. In recent years, there has been a growing interest in learning tractable graphical models in which exact inference is efficient. Two main approaches are to restrict the inference complexity directly, as done by low-treewidth graphical models and arithmetic circuits (ACs), or introduce latent variables, as done by mixtures of trees, latent tree models, and sum-product networks (SPNs). In this paper, we combine these approaches to learn a mixtures of ACs (MAC). A mixture can represent many distributions exponentially more compactly than a single AC. By using ACs as mixture components, MAC can represent complex distributions using many fewer components than required by other mixture models. MAC generalizes ACs, mixtures of trees, latent class models, and thin junction trees, and can be seen as a special case of an SPN. Compared to state-of-the-art algorithms for learning SPNs and other tractable models, MAC is consistently more accurate while maintaining tractable inference.

ABSTRACT. Our starting point is the model of Meir et al.[AAAI'12], where agents have uncertainty over the actual number of participants in a congestion game, formalized as a prior distribution over subsets of players. In this work we consider the idea of partial information revelation (signaling), for such games where the number of participants is unknown.

ABSTRACT. This works presents a novel approach for determining chance-constrained strong controllability of Temporal Plan Networks with Uncertainty (TPNU) by framing it as an Optimal Satisfiability Problem (OpSAT).

ABSTRACT. We present a novel human computation game that elicits not only annotations, but also direct critique of a system from the players. The game is based on the popular board game - Dixit. We present the results of the initial run of the game, in which the answers of 15 players were used to profile the mistakes of an aspect based opinion mining system. We show that, for this complex problem, the gameplay allowed us to identify the major faults and the generate improvement suggestions.

ABSTRACT. One typically proves infeasibility in satisfiability/constraint satisfaction (or optimality in integer programming) by constructing a tree certificate. However, deciding how to branch in the search tree is hard, and impacts search time drastically. We explore the power of a simple paradigm, that of throwing random darts into the assignment space and then using information gathered by that dart to guide what to do next. This method seems to work well when the number of short certificates of infeasibility is moderate, suggesting the overhead of throwing darts can be countered by the information gained by these darts.

ABSTRACT. In this work we present a formal approach to the design of Fault Detection and Identification (FDI) components. We define a comprehensive language for the specification of FDI, and discuss how to check whether a given FDI component fulfills its specifications. Then, we propose an automatic procedure to synthesize an FDI component that satisfies a given specification. The approach has been implemented and tested in realistic case studies from the aerospace domain.

ABSTRACT. Domains such as vision, bioinformatics, web search and web rankings involve datasets where number of features is very large. Feature selection is commonly employed to deal with high dimensional data. Recently, Quadratic Programming Feature Selection (QPFS) has been shown to outperform many of the existing feature selection methods for a variety of datasets. In this paper, we propose an SMO based framework for QPFS. This helps in reducing the cubic computational time (in terms of data dimension) of the standard QPFS to quadratic time in practice. Further, our approach has less memory requirement than QPFS. This memory saving can be critical for doing feature selection in high dimensions. The performance of our approach is demonstrated using three publicly available benchmark datasets from bioinformatics domain.

ABSTRACT. In this paper, we address the issue of bilingual sentiment lexicon learning which aims to automatically and simultaneously generate sentiment words for two languages. The underlying motivation is that sentiment information from two languages can perform iterative mutual-teaching in the learning procedure. We propose to develop two classifiers to determine the sentiment polarities of words under a co-training framework, which makes full use of the two-view sentiment information from the two languages. The word alignment derived from the parallel corpus is leveraged to design effective features and to bridge the learning of the two classifiers. The classifiers after co-training can be used to generate bilingual sentiment lexicons. The experimental results on English and Chinese languages indicate that the proposed approach outperforms inductive and transductive approaches.

ABSTRACT. An adversarial version of the problem of cooperative path finding (CPF) over graphs is addressed. Two or more teams of agents compete in finding paths in the graph to given destination vertices. The task is to control agents of a selected team so that its agents reach their destinations before agents of adversaries. Tactics such a blocking agents of the adversary or protecting own agents are allowed by the suggested formal definition of the problem.

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.

ABSTRACT. Multitask Bregman Clustering (MBC) alternatively updates clusters and learns relationship between clusters of different tasks, and the two phases boost each other. However, the boosting does not always have positive effects, it may also cause negative effects. Another issue of MBC is that it cannot deal with nonlinear separable data. In this paper, we show that MBC's process of using cluster relationship to boost the updating clusters phase may cause negative effects, i.e., cluster centroid may be skewed under some conditions. We propose a smart multi-task Bregman clustering (S-MBC) algorithm which identifies negative effects of the boosting and avoids the negative effect if it occurs. We then extend the framework of S-MBC to a smart multi-task kernel clustering (S-MKC) framework to deal with nonlinear separable data. We also propose a specific implementation of the framework which could be applied to any Mercer kernel. Experimental results confirm our analysis, and demonstrate the superiority of our proposed methods.

ABSTRACT. Spectral clustering has been a popular data clustering algorithm. This category of approaches often resort to other clustering methods, such as K-Means, to get the final cluster. The potential flaw of such common practice is that the obtained relaxed continuous spectral solution could severely deviate from the true discrete solution. In this paper, we propose to impose an additional orthonormal constraint to better approximate the optimal continuous solution to the graph cut objective functions. Such a method, called spectral rotation in literature, optimizes the spectral clustering objective functions better than K-Means, and improves the clustering accuracy. We would provide efficient algorithm to solve the new problem rigorously, which is not significantly more costly than K-Means. We also establish the connection between our method and K-Means to provide theoretical motivation of our method. Experimental results show that our algorithm consistently reaches better cut and meanwhile outperforms in clustering metrics than classic spectral clustering methods.

ABSTRACT. We propose a probabilistic latent variable model for unsupervised cluster matching, which is the task of finding correspondences between clusters of objects in different domains. Existing object matching methods find one-to-one matching in two domains. The proposed model finds many-to-many matching, and can handle multiple domains with different numbers of objects. The proposed model assumes that there are an infinite number of latent vectors that are shared by all domains, and each object is generated using one of the latent vectors and a domain-specific linear projection. By inferring a latent vector to be used for generating each object, objects in different domains are clustered in shared groups, and thus we can find matching between clusters in an unsupervised manner. We present efficient inference procedures of the proposed model based on a stochastic EM algorithm. The effectiveness of the proposed model is demonstrated with experiments using synthetic and real data sets.

ABSTRACT. Clustering with constraints is an important and developing area. However, most work is confined to conjunctions of simple together and apart constraints which limit their usability. In this paper, we propose a new formulation of constrained clustering that is able to incorporate not only existing types of constraints but also more complex logical combinations beyond conjunctions. We first show how any statement in conjunctive normal form (CNF) can be represented as a linear inequality. Since existing clustering formulations such as spectral clustering cannot easily incorporate these linear inequalities, we propose a quadratic programming (QP) clustering formulation to accommodate them. This new formulation allows us to have much more complex guidance in clustering. We demonstrate the effectiveness of our approach in two applications on text and personal information management. We also compare our algorithm against existing constrained spectral clustering algorithm to show its efficiency in computational time.

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.

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.

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.

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.

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.

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.

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.

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.

ABSTRACT. Mehdi Manshadi, Dan Gildea and James Allen

We motivate the integration of programming by example and natural language programming by developing a system for specifying programs for simple text editing operations. The programs are described with unconstrained natural language instructions, and providing a single example of input/output. We show that natural language allows the system to deduce the correct program much more often and much faster than is possible with the input/output example(s) alone, showing that natural language programming and programming by example can be combined in a way that overcomes the ambiguities that both methods suffer from individually, with a minimum of additional effort from the user.

(This paper is from the main AAAI technical track, paper 251.)

ABSTRACT. Current approaches to handling indirect speech acts (ISAs) do not account for their sociolinguistic underpinnings (i.e., politeness strategies). Deeper understanding and appropriate generation of indirect acts will require mechanisms that integrate natural language (NL) understanding and generation with social information about agent roles and obligations, which we introduce in this paper. Additionally, we tackle the problem of understanding and handling indirect answers that take the form of either speech acts or physical actions, which requires an inferential, plan-reasoning approach. In order to enable artificial agents to handle an even wider-variety of ISAs, we present a hybrid approach, utilizing both the idiomatic and inferential strategies. We then demonstrate our system successfully generating indirect requests and handling indirect answers, and discuss avenues of future research. our system successfully generating indirect requests and handling indirect answers, and discuss avenues of future research.

ABSTRACT. Emotional synthetic characters are able to evaluate (appraise) events as positive or negative taking into account several factors to trigger their emotional states. Currently, the vast majority of the models for the appraisal in synthetic characters consider factors related to the goals and preferences of the characters. We argue that appraisals that only take into consideration these "personal" factors are incomplete as other more social factors, such as the normative and the social context, including in-group and out-group relations, should be considered as well. Without them, moral emotions such as shame cannot be appraised, limiting the believability of the characters in certain situations. We present a model for the appraisal of characters' actions that evaluates if actions from in-group and out-group members conform or not to social norms and generates different emotions according to the social relation between the characters. The model was then implemented in an architecture for virtual agents and evaluated with humans. Results suggest that the emotions generated by our model are perceived adequately by the participants, taking into account the social context and that participants experienced very similar emotions, both in type and intensity, to the emotions appraised and generated by the characters.

ABSTRACT. We describe ongoing research towards building a cognitively plausible system for near one-shot learning of the meanings of attribute words and object names, by grounding them in a sensory model. The system learns incrementally from human demonstrations recorded with the Microsoft Kinect, in which the demonstrator can use unrestricted natural language descriptions. We achieve near-one shot learning of simple objects and attributes by utilizing child language learning strategies and focusing solely on examples where the learning agent is confident, ignoring the rest of the data. We evaluate the system’s learning ability by having it generate descriptions of presented objects, including objects it has never seen before, and comparing the system response against collected human descriptions of the same objects. We propose that retrieving object examples with k-nearest neighbor using Mahalanobis distance corresponds to a cognitively plausible representation of objects. Our results show great promise for achieving rapid, near one-shot, incremental learning of word meanings.

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.)

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.

ABSTRACT. Designers of human computation systems often face the need to aggregate noisy information provided by multiple people. While voting is often used for this purpose, the choice of voting method is typically not principled. We conduct extensive experiments on Amazon Mechanical Turk to better understand how different voting rules perform in practice. We also demonstrate that our empirical conclusions differ from what popular theoretical models would predict. Our short-term goal is to inform the design of better human computation systems; our long-term goal is to spark an interaction between researchers in (computational) social choice and human computation.

ABSTRACT. Crowdsourcing is often used to create a data set for supervised learning. Because the quality of the data set heavily depends on the abilities of workers, many methods have been proposed to learn a classifier from the data set. From some observations, we notice that workers form clusters according to their abilities. To utilize such knowledge, we propose a method to jointly learn a classifier and clusters of workers from a crowd-generated data set. The proposed method has two advantages. One is that it realizes robust estimation of a classifier because the proposed method utilizes clusters of workers whereas the other methods do not. The other is that we can obtain clusters of workers, which help us analyze the properties of the workers. Experimental results on synthetic and real data sets indicate that the proposed method can estimate a classifier robustly. In addition, clustering workers also works well because an outlier worker was found in the real data set by applying the proposed method.

ABSTRACT. Online labor markets such as Amazon Mechanical Turk (MTurk) have emerged as platforms that facilitate the allocation of productive effort across global economies. Many of these markets compensate workers with monetary payments. We study the effects of performance-contingent financial rewards on work quality and worker effort in MTurk via two experiments. We find that the magnitude of performance-contingent financial rewards alone affects neither quality nor effort. However, when workers working on two tasks of the same type in a sequence, the change in the magnitude of the reward over the two tasks affects both. In particular, both work quality and worker effort increase (alternatively decrease) as the reward increases (alternatively decreases) for the second task. This suggests the existence of the anchoring effect on workers' perception of incentives in MTurk and that this effect can be leveraged in workflow design to increase the effectiveness of financial incentives.

ABSTRACT. Object localization is an image annotation task which consists of finding the location of a target object in an image. It is common to crowdsource annotation tasks and aggregate responses to estimate the true annotation. While for other kinds of annotations consensus is simple and powerful, it cannot be applied to object localization as effectively due to the task's rich answer space and inherent noise in responses.

We propose a probabilistic graphical model to localize objects in images based on responses from the crowd. We improve upon natural aggregation methods such as the mean and the median by simultaneously estimating the difficulty level of each question and skill level of every participant.

We empirically evaluate our model on crowdsourced data and show that our method outperforms simple aggregators both in estimating the true locations and in ranking participants by their ability. We also propose a simple adaptive sourcing scheme that works well for very sparse datasets.

ABSTRACT. Salient object detection provides an alternative solution to various image semantic understanding tasks such as object recognition, adaptive compression and image retrieval. Recently, low-rank matrix recovery (LR) theory has been introduced into saliency detection, and achieves impressed results. However, the existing LR-based models neglect the underlying structure of images, and inevitably degrade the associated performance. In this paper, we propose a Low-rank and Structured sparse Matrix Decomposition (LSMD) model for salient object detection. In the model, a tree-structured sparsity-inducing norm regularization is firstly introduced to provide a hierarchical description of the image structure to ensure the completeness of the extracted salient object. The similarity of saliency values within the salient object is then guaranteed by the $\ell_\infty$-norm. Finally, high-level priors are integrated to guide the matrix decomposition and enhance the saliency detection. Experimental results on the largest public benchmark database show that our model outperforms existing LR-based approaches and other state-of-the-art methods, which verifies the effectiveness and robustness of the structure cues in our model.

ABSTRACT. Most existing matrix completion methods seek the matrix global structure in the real number domain and produce predictions that are inappropriate for applications retaining discrete structure, where an additional step is required to post-process prediction results with either heuristic threshold parameters or complicated mappings. Such an ad-hoc process is inefficient and impractical. In this paper, we propose a novel robust discrete matrix completion algorithm that produces the prediction from the collection of user specified discrete values by introducing a new discrete constraint to the matrix completion model. Our method achieves a high prediction accuracy, very close to the most optimal value of competitive methods with threshold values tuning. We solve the difficult integer programming problem via incorporating augmented Lagrangian method in an elegant way, which greatly accelerates the converge process of our method and provides the asymptotic convergence in theory. The proposed discrete matrix completion model is applied to solve three real-world applications, and all empirical results demonstrate the effectiveness of our method.

ABSTRACT. Rank aggregation, which combines multiple individual rank lists to obtain a better one, is a fundamental technique in various applications such as meta-search and recommendation systems. Most existing rank aggregation methods blindly combine multiple rank lists with possibly considerable noises, which often degrades their performances. In this paper, we propose a new model for \textit{robust rank aggregation (RRA)} via matrix learning, which recovers a latent rank list from the possibly incomplete and noisy input rank lists. In our model, we construct a pairwise comparison matrix to encode the order information in each input rank list. Based on our observations, each comparison matrix can be naturally decomposed into a shared low-rank matrix, combined with a deviation error matrix which is the sum of a column-sparse matrix and a row-sparse one. The latent rank list can be easily extracted from the learned low-rank matrix. The optimization formulation of RRA has an element-wise multiplication operator to handle missing values, a symmetric constraint on the noise structure, and a factorization trick to restrict the maximum rank of the low-rank matrix. To solve this challenging optimization problem, we propose a novel procedure based on the Augmented Lagrangian Multiplier scheme. We conduct extensive experiments on meta-search and collaborative filtering benchmark datasets. The results show that the proposed RRA has superior performance gain over several state-of-the-art algorithms for rank aggregation.

ABSTRACT. We study a simple sequential allocation mechanism for allocating indivisible goods between agents where agents take turns to pick items. We focus on computational aspects of agents behaving strategically. We view the allocation procedure as a finite repeated game with perfect information. We show that with just two agents, we can compute the unique subgame perfect Nash equilibrium in linear time. With more agents, computing one or all of the subgame perfect Nash equilibria is more difficult. There can be an exponential number of equilibria and computing even one of them is PSPACE-hard in general. We identify a special case, when agents value many of the items identically, where we can efficiently compute the subgame perfect Nash equilibria. We also consider the effect of externalities and modifications to the mechanism that make it strategy proof.

ABSTRACT. We propose a new market design for display advertising contracts, based on posted prices. This requires overcoming major challenges: (i) the space of possible impression types is exponential in the number of attributes, which is typically large; therefore a complete price space cannot be maintained; (ii) the level of detail with which supply and demand are specified are often not identical, (iii) advertisers are usually unable to provide extensive demand (willingness-to-pay) functions.

ABSTRACT. The increasing use of group discounts has provided opportunities for buying groups with diverse preferences to coordinate their behavior in order to exploit the best offers from multiple vendors. We analyze this problem from the viewpoint of the vendors, asking under what conditions a vendor should adopt a volume-based price schedule rather than posting a fixed price, either as a monopolist or when competing with other vendors. When vendors have uncertainty about buyers' valuations specified by a known distribution, we show that a vendor is always better off posting a fixed price, provided that buyers' types are i.i.d. and other vendors also use fixed prices. We also show that these assumptions cannot be relaxed: if buyers are not i.i.d., or other vendors post discount schedules, then posting a schedule may yield higher profit for the vendor. We provide similar results under a distribution-free uncertainty model, where vendors try to minimize their maximum regret over all type realizations.

ABSTRACT. We introduce a sealed bid auction of a single item in which the winner is chosen at random among the highest k bidders according to a fixed probability distribution, and the price for the chosen winner is the Vickrey-Clarke-Groves price. We call such an auction a cascade auction. Our analysis suggests that this type of auction may give higher revenues compared to second price auction in cases of collusion.

ABSTRACT. Although the heuristic search algorithm A* is well-known to be optimally efficient, this result explicitly assumes forward search. Bidirectional search has long held promise for surpassing A*'s efficiency, and many varieties have been proposed, but it has proven difficult to achieve robust performance across multiple domains in practice. We introduce a simple bidirectional search algorithm called Auto-Tuning A* that judiciously performs backward search to improve the accuracy of the forward heuristic function. We assess its theoretical properties and empirically evaluate its performance across seven benchmark domains. In the best case, it yields a factor of six reduction in node expansions and CPU time compared to A*, and in the worst case, its overhead is provably bounded by a user-supplied parameter, such as 1\%. Viewing performance across all domains, it also surpasses previously proposed bidirectional search algorithms. These results indicate that Auto-Tuning A* is robust way to leverage bidirectional search in practice.

ABSTRACT. Multiple sequence alignment (MSA) is a central problem in computational biology. It is well known that MSA can be formulated as a shortest path problem and solved using heuristic search, but the memory requirement of A* makes it impractical for all but the smallest problems. Partial Expansion A* (PEA*) reduces the space complexity of A* by generating only the most promising successor nodes. However, even PEA* exhausts available memory on many problems. Another alternative is Iterative Deepening Dynamic Programming, which uses an uninformed search order but stores only the nodes along the search frontier. However, it too cannot scale to the largest problems. In this paper, we propose storing nodes on cheap and plentiful secondary storage. We present a new general-purpose algorithm, Parallel External PEA* (PE2A*), that combines PEA* with Delayed Duplicate Detection to take advantage of external memory and multiple processors to solve large MSA problems. In our experiments, PE2A* is the first algorithm capable of solving the entire Reference Set 1 of the standard BaliBASE benchmark using a biologically accurate cost function. This work suggests that external best-first search can effectively use heuristic information to surpass methods that rely on predefined search orders.

ABSTRACT. Structured prediction is the problem of learning a function from structured inputs to structured outputs with prototypical examples being part-of-speech tagging and image labeling. Inspired by the recent successes of search-based structured prediction, we introduce a new framework for structured prediction called {\em HC-Search}. Given a structured input, the framework uses a search procedure guided by a learned heuristic H to uncover high quality candidate outputs and then uses a separate learned cost function C to select a final prediction among those outputs. We can decompose the regret of the overall approach into the loss due to H not leading to high quality outputs, and the loss due to C not selecting the best among the generated outputs. Guided by this decomposition, we minimize the overall regret in a greedy stage-wise manner by first training H to quickly uncover high quality outputs via imitation learning, and then training C to correctly rank the outputs generated via H according to their true losses. Experiments on several benchmark domains show that our approach significantly outperforms the state-of-the-art methods.

ABSTRACT. Recently, a Euclidean heuristic (EH) has been proposed for A* search. EH exploits manifold learning methods to construct an embedding of the state space graph, and derives an admissible heuristic distance between two states from the Euclidean distance between their respective embedded points. EH has shown good performance and memory efficiency in comparison to other existing heuristics such as differential heuristics. However, its potential has not been fully explored. In this paper, we propose a number of techniques that can significantly improve the quality of EH. We propose a goal-oriented manifold learning scheme that optimizes the Euclidean distance to goals in the embedding while maintaining admissibility and consistency. We also propose a state heuristic enhancement technique to reduce the gap between heuristic and true distances. The enhanced heuristic is admissible but no longer consistent. We then employ a modified search algorithm that achieves optimality with inconsistent heuristics using consistency check and propagation. We demonstrate the effectiveness of the above techniques and report un-matched reduction in search costs across several non-trivial benchmark search problems.

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.

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.

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.

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.

ABSTRACT. In AI and the Web communities, modularity-based graph clustering algorithms have been applied to various applications. However, existing algorithms are not applied to large graphs because they have to scan all vertices/edges iteratively. The goal of this paper is to efficiently compute clusters with high modularity from unprecedented size of graphs that have over a few billion edges. The heart of our solution is to compute clusters from large graphs by incrementally pruning unnecessary vertices/edges and dynamically selecting vertices which provide efficient data accesses. Our experiments shows that our proposal outperforms all other modularity-based algorithms in terms of computation time, and it finds clusters with high modularity. To the best of our knowledge, our algorithm is the first solution to extract clusters from graphs of unprecedented size, that have more than 100 million vertices and 1 billion edges, in a few minutes.

ABSTRACT. With the proliferation of its applications in various industries, sentiment analysis by using publicly available web data has become an active research area in text classification during these years. It is argued by researchers that semi-supervised learning is an effective approach to this problem since it is capable to mitigate the manual labeling effort which is usually expensive and time-consuming. However, there was a long-term debate on the effectiveness of unlabeled data in text classification. This was partially caused by the fact that many assumptions in theoretic analysis often do not hold in practice. We argue that this problem may be further understood by adding an additional dimension in the experiment. This allows us to address this problem in the perspective of bias and variance in a broader view. We show that the well-known performance degradation issue caused by unlabeled data can be reproduced as a subset of the whole scenario. We argue that if the bias-variance trade-off is to be better balanced by a more effective feature selection method unlabeled data is very likely to boost the classification performance. We then propose a feature selection framework in which labeled and unlabeled training samples are both considered. We discuss its potential in achieving such a balance. Besides, the application in financial sentiment analysis is chosen because it not only exemplifies an important application, the data possesses better illustrative power as well. The implications of this study in text classification and financial sentiment analysis are both discussed.

ABSTRACT. We present a novel method for ranking query paraphrases for effective search in community question answering (cQA) services like Yahoo! Answers. The method uses query logs from a commercial search engine and a cQA archive for automatically extracting a corpus of paraphrases of queries and questions using the query-question click history. Elements of this corpus are automatically ranked according to recall and mean reciprocal rank, and then used for learning two independent learning to rank models (SVMRank), whereby a set of new query paraphrases can be scored according to recall and MRR. We perform several automatic evaluation procedures using cross-validation for analyzing the behavior of various aspects of our learned ranking functions, which show that our method is useful and effective for search in cQA.

ABSTRACT. In this paper, we investigate information extraction tasks that are initiated as queries from either automated agents or humans. We introduce OpenEval, a new online information extraction technique which uses information on the web to automatically evaluate the truth of propositions that are stated as multi-argument predicate instances (e.g., LocationHasObject(Kitchen, Coffee)). OpenEval gets a small number of instances of a predicate as seed positive examples and automatically learns how to evaluate the truth of a new predicate instance by querying the web and processing the retrieved unstructured Web pages. We show that OpenEval is able to respond to the queries within a limited amount of time while also achieving high F1 score. In addition, we show that the accuracy of responses provided by OpenEval is increased as more time is given for evaluation. We have extensively tested our model and shown empirical results that illustrate the effectiveness of our approach compared to related techniques.

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.

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.

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.

ABSTRACT. Representatives from NSF will discuss NSF programs of interest to Artificial Intelligence researchers, and provide advice on finding funding in economically challenging times. Topics during the subsequent question and answer session could include the following: recent NSF initiatives, advice for young investigators, funding for educational initiatives, summer schools, interdisciplinary research and international research collaborations, ways of achieving broader impacts, and current proposal acceptance rates.

ABSTRACT. Reception/poster session including the Student Abstracts, Intern Posters, DC Abstracts, Poker Posters and EAAI posters.