The Support Vector Machine has gained significant popularity over recent years as a kernel-based supervised learning technique. However, choosing the appropriate kernel function and its associated parameters is not a trivial task. The kernel is often chosen from several widely-used and general-purpose functions, and the parameters are then empirically tuned for the best results on a specific data set. This paper explores the use of Particle Swarm Optimization and Genetic Programming as evolutionary approaches to evolve effective kernel functions for a given dataset. Rather than using expert knowledge, we evolve kernel functions without human-guided knowledge or intuition. Our results show consistently better SVM performance with evolved kernels over a variety of traditional kernels on several datasets.

Algorithms for finding frequent and/or interesting subgraphs in a single large graph scenario are computationally intensive because of the graph isomorphism and the subgraph isomorphism problem. These problems are compounded by the size of most real-world datasets which have sizes in the order of 105 or 106. The SUBDUE algorithm developed by Cook and Holder finds the most compressing subgraph in a large graph. In order to perform the same task on real-world data sets efficiently, Cook et al. developed a parallel approach to SUBDUE called the SP-SUBDUE based on the MPI framework. This paper extends the work done by Cook et al. to improve the efficiency of MPI SUBDUE by modifying the evaluation phase. Our experiments show an improvement in speed-up while retaining the quality of the results of serial SUBDUE. The techniques that we have used in this study can also be used in similar algorithms which use static partitioning of the data and re-evaluation of locally interesting patterns over all the nodes of the cluster.

In this paper we describe an improvement to the popular IDA* search algorithm that emphasizes a different space-for-time trade-off than previously suggested. In particular, our algorithm, called Iterative-Expansion A* (IEA*), focuses on reducing redundant node expansions within individual depth-first search DFS iterations of IDA* by employing a relatively small amount of available memory—bounded by the error in the heuristic—to store selected nodes. The additional memory required is exponential not in the solution depth, but only in the difference between the solution depth and the estimated solution depth. A constant-time hash set lookup can then be used to prune entire subtrees as DFS proceeds. Overall, we show 2- to 26-fold time speedups vs. an optimized version of IDA* across several domains, and compare IEA* with several other competing approaches. We also sketch proofs of optimality and completeness for IEA*, and note that IEA* is particularly efficient for solving implicitly-defined general graph search problems.

In reinforcement learning (RL), rewards have been considered the most important feedback in understanding the environment. However, recently there have been interesting forays into other modes such as using sporadic supervisory inputs. This brings into the learning process richer information about the world of interest. In this paper, we model these supervisory inputs as specific types of instructions that provide information in the form of an expert's control decision and certain structural regularities in the state space. We further provide a mathematical formulation for the same and propose a framework to incorporate them into the learning process.

We consider a cross-cultural interaction scenario where a group of soldiers assisted by robots interact with local vendors in a market place. We develop a model to quantify, analyze and predict the perception of the actions of the soldiers and the robot by the local population. The model assumes that humans are considering collections of concrete and intangible values which are not, in general, directly and linearly convertible into each other. We argue that satisfactory modeling accuracy can be achieved by restricting the considered intangibles to a small set of {\em culture sanctioned social values}. For these values, the culture provides a name, calculation methods, as well as associated rules of conduct. We validate our model by comparing the predicted values with the judgment of a large group of human observers cognizant of the modeled culture. We use the model to evaluate the tradeoffs between several long term strategies to maintain security as well as to increase the trust and goodwill of the local population.

For many classification problems, genetic algorithms prove to be effective without extensive domain engineering. However, the chess King-Rook-King endgame problem appears to be an exception. We explore whether modifications to a baseline parallel genetic algorithm can improve the accuracy on this particular problem. After describing the problem domain and our implementation of a parallel genetic algorithm, we present an empirical evaluation of several approaches intended to improve overall performance. Our results confirm the challenging nature of this domain. We describe several directions that may yet deliver significant improvements.

We present a framework to represent and reason about nar- ratives. We build a symbolic probabilistic representation of the temporal sequence of world states and events implied by a narrative using statistical approaches. We show that the combination of this representation together with domain knowledge and symbolic probabilistic reasoning algorithms enables understanding of a narrative and answering semantic questions whose responses are not contained in the narrative. In our experiments, we show the power of our framework (vs. traditional approaches) in answering semantic questions for two domains of RoboCup soccer commentaries and early reader children stories focused on spatial contexts.

When analysing social media conversations, in search of the public opinion about an unfolding event that is be- ing discussed in real-time (e.g., presidential debates, major speeches, etc.), it is important to distinguish between two groups of participants: opinion-makers and opinion-holders. To address this problem, we propose a supervised machine-learning approach, which uses inexpensively acquired labeled data from monothematic Twitter accounts to learn a binary classifier for the labels “political account” (opinion-makers) and “non-political account” (opinion-holders). While the classifier has a 83% accuracy on individual tweets, when applied to the last 200 tweets from accounts of a set of 1000 Twitter users, it classifies accounts with a 97% accuracy. This high accuracy derives from our decision to incorporate information about classifier probability into the classification. Our work demonstrates that machine learning algorithms can play a critical role in improving the quality of social media analytics and understanding, whose importance is increasing as social media adoption becomes widespread.

Many exponentially-hard problems can be solved by searching through a space of states to determine a sequence of steps constituting a solution. Algorithms that produce optimal solutions (e.g., shortest path) generally require greater computational resources (e.g., time) than their sub-optimal counterparts. Consequently, many optimal algorithms cannot produce any usable solution when the amount of time available is limited or hard to predict in advance. Anytime algorithms address this problem by initially finding a suboptimal solution very quickly and then generating incrementally better solutions with additional time, effectively providing the best solution generated so far anytime it is required. In this research, we generate initial solutions cheaply using a fast search algorithm. We then improve this low-quality solution by identifying subsequences of steps that appear, based on heuristic estimates, to be considerably longer than necessary. Finally, we perform a more expensive search between the endpoints of each subsequence to find a shorter connecting path. We will show that this improves the overall solution incrementally over time while always having a valid solution to return whenever time runs out. We present results that demonstrate in several problem domains that AIRS (Anytime Iterative Refinement of a Solution) rivals other widely used and recognized anytime algorithms and also produces results comparable to other popular (but not anytime) heuristic algorithms such as Bidirectional A* search.

Automated planning is a well studied research topic thanks to its wide range of real-world applications. Despite significant progress in this area many planning problems still remain hard and challenging. Some techniques such as learning macro-operators improve the planning process by reformulating the (original) planning problem. While many encouraging practical results have been derived from such reformulation methods, little attention has been paid to the theoretical properties of reformulation such as soundness, completeness, and algorithmic complexity. In this paper we build up a theoretical framework describing reformulation schemes such as action elimination or creating macro-actions. Using this framework, we show that finding entanglements (relationships useful for action elimination) is as hard as planning itself. Moreover, we design a tractable algorithm for checking under what conditions it is safe to reformulate a problem by removing primitive operators (assembled to a macro-operator).