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

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.

Randomized first-mover strategies of Stackelberg games are used in several deployed applications to allocate limited resources for the protection of critical infrastructure. Stackelberg games model the fact that a strategic attacker can surveil and exploit the defender's strategy, and randomization guards against the worst effects by making the defender less predictable. In accordance with the standard game-theoretic model of Stackelberg games, past work has typically assumed that the attacker has perfect knowledge of the defender's randomized strategy and will react correspondingly. In light of the fact that surveillance is costly, risky, and delays an attack, this assumption is clearly simplistic: attackers will usually act on partial knowledge of the defender's strategies. The attacker's imperfect estimate could present opportunities and possibly also threats to a strategic defender. In this paper, we therefore begin a systematic study of security games with limited surveillance. We propose a natural model wherein an attacker forms or updates a belief based on observed actions, and chooses an optimal response. We investigate the model both theoretically and experimentally. In particular, we give mathematical programs to compute optimal attacker and defender strategies for a fixed observation duration, and show how to use them to estimate the attacker's observation durations. Our experimental results show that the defender can achieve significant improvement in expected utility by taking the attacker's limited surveillance into account, validating the motivation of our work.