A “hub” is an object closely surrounded by, or very similar to, many other objects in the dataset. Recent studies by Radovanovi´c et al. indicate that in high dimensional spaces, hubs almost always emerge, and objects close to the data centroid tend to become hubs. In this paper, we show that the family of kernels based on the graph Laplacian makes all objects in the dataset equally similar to the centroid, and thus they are expected to make less hubs when used as a similarity measure. We investigate this hypothesis using both synthetic and real-world data. It turns out that these kernels suppress hubs in some cases but not always, and the results seem to be affected by the size of the data—a factor not discussed previously. However, for the datasets in which hubs are indeed reduced by the Laplacian-based kernels, these kernels work well in ranking and classification tasks. This result suggests that the amount of hubs, which can be readily computed in an unsupervised fashion, can be a yardstick of whether Laplacian-based kernels work effectively for a given data.

Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to polytrees of bounded in-degree. Polynomial-time algorithms are known only for rare special cases, perhaps most notably for branchings, that is, polytrees in which the in-degree of every node is at most one. Here, we study the complexity of finding an optimal polytree that can be turned into a branching by deleting some number of arcs or nodes, treated as a parameter. We show that the problem can be solved via a matroid intersection formulation in polynomial time if the number of deleted arcs is bounded by a constant. The order of the polynomial time bound depends on this constant, hence the algorithm does not establish fixed-parameter tractability when parameterized by the number of deleted arcs. We show that a restricted version of the problem allows fixed-parameter tractability and hence scales well with the parameter. We contrast this positive result by showing that if we parameterize by the number of deleted nodes, a somewhat more powerful parameter, the problem is not fixed-parameter tractable, subject to a complexity-theoretic assumption.

Predicting entailment between two given texts is an important task upon which the performance of numerous NLP tasks depend on such as question answering, text summarization, and information extraction. The degree to which two texts are similar has been used extensively as a key feature in much previous work in predicting entailment. However, using similarity scores directly, without proper transformations, results in suboptimal performance. Given a set of lexical similarity measures, we propose a method that jointly learns both (a) a set of non-linear transformation functions for those similarity measures and, (b) the optimal non-linear combination of those transformation functions to predict textual entailment. Our method consistently outperforms numerous baselines, reporting a micro-averaged F-score of 46.48 on the RTE- 7 benchmark dataset. The proposed method is ranked 2-nd among 33 entailment systems participated in RTE-7, demonstrating its competitiveness over numerous other entailment approaches. Although our method is statistically comparable to the current state-of-the-art, we require less external knowledge resources.

Homotopy classes of trajectories, arising due to the presence of obstacles, are defined as sets of trajectories that can be transformed into each other by gradual bending and stretching without colliding with obstacles. The problem of exploring/finding the different homotopy classes in an environment and the problem of finding least-cost paths restricted to a specific homotopy class (or not belonging to certain homotopy classes) arises frequently in such applications as predicting paths for unpredictable entities and deployment of multiple agents for efficient exploration of an environment. In [Bhattacharya, Kumar, Likhachev, AAAI 2010] we have shown how homotopy classes of trajectories on a two-dimensional plane with obstacles can be classified and identified using the Cauchy Integral Theorem and the Residue Theorem from Complex Analysis. In more recent work [Bhattacharya, Likhachev, Kumar, RSS 2011] we extended this representation to three-dimensional spaces by exploiting certain laws from the Theory of Electromagnetism (Biot-Savart law and Ampere's Law) for representing and identifying homotopy classes in three dimensions in an efficient way. Using such a representation, we showed that homotopy class constraints can be seamlessly weaved into graph search techniques for determining optimal path constrained to certain homotopy classes or forbidden from others, as well as for exploring different homotopy classes in an environment. (This is a condensed, non-technical overview of work previously published in the proceedings of Robotics: Science and Systems, 2011 conference [Bhattacharya, Likhachev, Kumar, RSS 2011].)

Symmetry is an important problem in many combinatorial problems. One way of dealing with symmetry is to add constraints that eliminate symmetric solutions. We survey recent results in this area, focusing especially on two common and useful cases: symmetry breaking constraints for row and column symmetry, and symmetry breaking constraints for eliminating value symmetry.

General Game Playing (GGP) agents must be capable of playing a wide variety of games skillfully. Monte-Carlo Tree Search (MCTS) has proven an effective reasoning mechanism for this challenge, as is reflected by its popularity among designers of GGP agents. Providing GGP agents with the knowledge relevant to the game at hand in real time is, however, a challenging task. In this paper we propose two enhancements for MCTS in the context of GGP, aimed at improving the effectiveness of the simulations in real time based on in-game statistical feedback. The first extension allows early termination of lengthy and uninformative simulations while the second improves the action-selection strategy when both explored and unexplored actions are available. The methods are empirically evaluated in a state-of-the-art GGP agent and shown to yield an overall significant improvement in playing strength.

A General Similarity Measurement (GSM), which takes into account of both non-temporal and rich temporal aspects including temporal order, temporal duration and temporal gap, is proposed for state-sequence matching. It is believed to be versatile enough to subsume representative existing measurements as its special cases.

In conservation biology and natural resource management, adaptive management is an iterative process of improving management by reducing uncertainty via monitoring. Adaptive management is the principal tool for conserving endangered species under global change, yet adaptive management problems suffer from a poor suite of solution methods. The common approach used to solve an adaptive management problem is to assume the system state is known and the system dynamics can be one of a set of pre-defined models. The solution method used is unsatisfactory, employing value iteration on a discretized belief MDP which restricts the study to very small problems. We show how to overcome this limitation by modelling an adaptive management problem as a restricted Mixed Observability MDP called hidden model MDP (hmMDP). We demonstrate how to simplify the value function, the backup operator and the belief update computation. We show that, although a simplified case of POMDPs, hm-MDPs are PSPACE-complete in the finite-horizon case. We illustrate the use of this model to manage a population of the threatened Gouldian finch, a bird species endemic to Northern Australia. Our simple modelling approach is an important step towards efficient algorithms for solving adaptive management problems.

Prior work done in learning by instruction (Huffman and Laird, 1995) Learning by interacting with humans is a powerful learning demonstrated learning systems that focus on agent-initiated paradigm. In a complex world learning through self-directed interaction, where instruction is directed by impasses arising experience alone can be slow, requiring repeated interactions in a Soar agent. They noted that instructor-initiated interaction with the environment. Learning from human-agent interaction is difficult to support because of the likely interruption can reduce the complexity of the learning task by reducing of agent's reasoning.

Metaphors being at the heart of our language and thought process, computationally modelling them is imperative for reproducing human cognitive abilities. In this work, we propose a plausible grounded cognitive model for artificial metaphor acquisition. We put forward a rule-based metaphor acquisition system, which doesn't make use of any prior 'seed metaphor set'. Through correlation between a video and co-occurring commentaries, we show that these rules can be automatically acquired by an early learner capable of manipulating multi-modal sensory input. From these grounded linguistic concepts, we derive classes based on lexico-syntactical language properties. Based on the selectional preferences of these linguistic elements, metaphorical mappings between source and target domains are acquired.