Although successfully employed on many industrial problems, Combinatorial Optimization still has limited applicability on several real-world domains, often due to modeling difficulties. This is typically the case for systems under the control of an on-line policy: even when the policy itself is well known, capturing its effect on the system in a declarative model is often impossible by conventional means. Such a difficulty is at the root of the classical, sharp separation between off- line and on-line approaches. In this paper, we investigate a general method to model controlled systems, based on the integration of Machine Learning and Constraint Programming (CP). Specifically, we use an Artificial Neural Network (ANN) to learn the behavior of a controlled system (a multicore CPU with thermal con- trollers) and plug it into a CP model by means of Neuron Constraints. The method obtains significantly better results compared to an approach with no ANN guidance. Neuron Constraints were first introduced in [Bartolini et al., 2011b] as a mean to model complex systems: providing evidence of their applicability to controlled systems is a significant step forward, broadening the application field of combinatorial methods and disclosing opportunities for hybrid off-line/on-line optimization.

Deciding what mix of engine and battery power to use is critical to hybrid vehicles' fuel efficiency. Current solutions consider several factors such as the charge of the battery and how efficient the engine operates at a given speed. Previous research has shown that by taking into account the future power requirements of the vehicle, a more efficient balance of engine vs. battery power can be attained. In this paper, we utilize a probabilistic driving route prediction system, trained using Inverse Reinforcement Learning, to optimize the hybrid control policy. Our approach considers routes that the driver is likely to be taking, computing an optimal mix of engine and battery power. This approach has the potential to increase vehicle power efficiency while not requiring any hardware modification or change in driver behavior. Our method outperforms a standard hybrid control policy, yielding an average of 1.22% fuel savings.

Scott Turner's 1993 Minstrel system was a high water mark in story generation, harnessing the concept of imaginative recall to generate creative stories. Using case-based reasoning and an author level planning system, Minstrel models human creative processes. However, the algorithmic and representational commitments made in Minstrel were never subject to principled and quantitative analysis. By rationally reconstructing Minstrel, we are able to investigate Turner's computational model of creativity and learn new lessons about his architecture. We find that Minstrel's original performance was tied to a well-groomed case library, but by modifying several components of the algorithm we can create a more general version which can construct stories using a sparser and less structured case library. Through a rational reconstruction of Minstrel, we both learn new architectural and algorithmic lessons about Minstrel’s computational model of creativity as well as make his architecture available to the contemporary research community for further experimentation.

An important difference between traditional AI systems and human intelligence is our ability to harness common sense knowledge gleaned from a lifetime of learning and experiences to inform our decision making and behavior. This allows humans to adapt easily to novel situations where AI fails catastrophically for lack of situation-specific rules and generalization capabilities. Common sense knowledge also provides the background knowledge for humans to successfully operate in social situations where such knowledge is typically assumed. In order for machines to exploit common sense knowledge in reasoning as humans do, moreover, we need to endow them with human-like reasoning strategies. In this work, we propose a two-level affective reasoning framework that concurrently employs multi-dimensionality reduction and graph mining techniques to mimic the integration of conscious and unconscious reasoning, and exploit it for sentiment analysis.

Automatic Subjective Question Answering (ASQA), which aims at answering users'subjective questions using summaries of multiple opinions, becomes increasingly important. One challenge of ASQA is that expected answers for subjective questions may not readily exist in the Web. The rising and popularity of Community Question Answering (CQA) sites, which provide platforms for people to post and answer questions, provides an alternative to ASQA. One important task of ASQA is question subjectivity identification, which identifies whether a user is asking a subjective question. Unfortunately, there has been little labeled training data available for this task. In this paper, we propose an approach to collect training data automatically by utilizing social signals in CQA sites without involving any manual labeling. Experimental results show that our data-driven approach achieves 9.37% relative improvement over the supervised approach using manually labeled data, and achieves 5.15% relative gain over a state-of-the-art semi-supervised approach. In addition, we propose several heuristic features for question subjectivity identification. By adding these features, we achieve 11.23% relative improvement over word n-gram feature under the same experimental setting.

Entity Recognition (ER) is a key component of relation extraction systems and many other natural-language processing applications. Unfortunately, most ER systems are restricted to produce labels from to a small set of entity classes, e.g., person, organization, location or miscellaneous. In order to intelligently understand text and extract a wide range of information, it is useful to more precisely determine the semantic classes of entities mentioned in unstructured text. This paper defines a fine-grained set of 112 tags, formulates the tagging problem as multi-class, multi-label classification, describes an unsupervised method for collecting training data, and presents the FIGER implementation. Experiments show that the system accurately predicts the tags for entities. Moreover, it provides useful information for a relation extraction system, increasing the F1 score by 93%. We make FIGER and its data available as a resource for future work.

Comparing entities is an important part of decision making. Several approaches have been reported for mining comparable entities from Web sources to improve user experience in comparing entities online.However, these efforts extract only entities explicitly compared in the corpora, and may exclude entities that occur less-frequently but potentially comparable. To build a more complete comparison machine that can infer such missing relations, here we develop a solutionto predict transitivity of known comparable relations. Named CliqueGrow, our approach predicts missing links given a comparable entity graph obtained from versus query logs. Our approach achieved the highest F1-score among five link prediction approaches and a commercial comparison engine provided by Yahoo!.

With the exponential increase in the number of documents available online, e.g., news articles, weblogs, scientific documents, the development of effective and efficient classification methods is needed. The performance of document classifiers critically depends, among other things, on the choice of the feature representation. The commonly used "bag of words" and n-gram representations can result in prohibitively high dimensional input spaces. Data mining algorithms applied to these input spaces may be intractable due to the large number of dimensions. Thus, dimensionality reduction algorithms that can process data into features fast at runtime, ideally in constant time per feature, are greatly needed in high throughput applications, where the number of features and data points can be in the order of millions. One promising line of research to dimensionality reduction is feature clustering. We propose to combine two types of feature clustering, namely hashing and abstraction based on hierarchical agglomerative clustering, in order to take advantage of the strengths of both techniques. Experimental results on two text data sets show that the combined approach uses significantly smaller number of features and gives similar performance when compared with the "bag of words" and n-gram approaches.

With the increasing popularity of smartphones, the wide availability of mobile Internet and the higher computational power of mobile devices, new types of applications are now possible. It is important to provide a smooth user experience by facilitating the interaction with the device. To do so, the goal of the work is support proactive recommendations on the mobile device. In order to determine the best point in time for a recommendation, various context information needs to be taken into account. One interesting aspect is determining the current user activity, e.g. whether the user is walking or not. In this paper, we present an algorithm that runs online on a smartphone and analyzes the user activity based on GPS data.

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