Many real world applications require managing both system requirements and user preferences where the latter are usually provided in a qualitative way. We introduce a new approach to handle these two aspects, in an efficient way, respectively through Constraint Satisfaction Problems (CSPs) and CP-nets. In particular, we use Arc Consistency (AC) in order to reduce the search space needed when looking for the optimal outcome in an acyclic CP-net. More precisely, assuming that there are always some shared variables between the CP-net and the CSP, our approach works by first applying AC to the CSP and then update the CP-net with the remaining variables values. The resulting simplified CP-net will then be used to look for the best outcome. Experimental tests conducted on randomly generated problem instances clearly show the effect of AC on the size of the search space and the time needed to find the best outcome.

Biologists seek concise, testable models of behavior for the animals they study. We suggest a robot programming paradigm in which animal behaviors are described as robot controllers to support a cycle of hypothesis generation and testing of animal models. In this work we illustrate that approach by modeling the hunting behavior of a captive colony of Aphaenogaster cockerelli , a desert harvester ant. In laboratory animal experiments we introduce live prey (fruit flies) into the foraging arena of the colony. We observe the behavior of the ants, and we measure aspects of their performance in capturing the prey. Based on these observations we create a model of their behavior using Clay, a Java library developed for coding hybrid controllers in a behavior-based manner. We then validate that model in quantitative comparisons with the live animal behavior.

The dynamic between speaker intent and listener perception is played out in the variation of acoustical cues by the speaker that must be interpreted by the listener to determine in an appropriate way. Emotion speech research must rely on either acted intent (i.e., an actor attempting to express an emotion) or listener perception (i.e., listening tests to assign emotional categories to non-acted data) to define ground truth labels for analysis. The emotion labels are described either using emotion dimension or emotion category. This study examines the two emotion characterization strategies dimension and category in communication of emotion embedded in speech as expressed through acted intent and the perception of emotion determined by a group of listeners. The results reveal that, without context information, intended emotion categories could be perceived by listeners with the averaged accuracy rate five times of chance in category. Also, the trend of listener ratings between emotion dimensions (valence/arousal) and emotional word categories was shown to be well correlated. Furthermore, while listeners confused the specific identity of certain emotional expressions, they were generally very accurate at identifying the intended affective space of the actor as determined by intended valence and arousal.

Entity coreference is the process to decide which identifiers (e.g., person names, locations, ontology instances, etc.) refer to the same real world entity. In the Semantic Web, entity coreference can be used to detect equivalence relationships between heterogeneous Semantic Web datasets to explicitly link coreferent ontology instances via the owl:sameAs property. Due to the large scale of Semantic Web data today, we propose two pruning techniques for scalably detecting owl:sameAs links between ontology instances by comparing the similarity of their context graphs. First, a sampling based technique is designed to estimate the potential contribution of each RDF node in the context graph and prune insignificant context. Furthermore, a utility function is defined to reduce the cost of performing such estimations. We evaluate our pruning techniques on three Semantic Web instance categories. We show that the pruning techniques enable the entity coreference system to run 10 to 35 times faster than without them while still maintaining comparably good F1-scores.

Gene selection has become a vital component in the learning process when using high-dimensional gene expression data. Although extensive research has been done towards evaluating the performance of classifiers trained with the selected features, the stability of feature ranking techniques has received relatively little study. This work evaluates the robustness of eleven threshold-based feature selection techniques, examining the impact of data sampling and class noise on the stability of feature selection. To assess the robustness of feature selection techniques, we use four groups of gene expression datasets, employ eleven threshold-based feature rankers, and generate artificial class noise to better simulate real-world datasets. The results demonstrate that although no ranker consistently outperforms the others, MI and Dev show the best stability on average, while GI and PR show the least stability on average. Results also show that trying to balance datasets through data sampling has on average no positive impact on the stability of feature ranking techniques applied to those datasets. In addition, increased feature subset sizes improve stability, but only does so reliably for noisy datasets.

Recommender systems assist users in the daunting task of sifting through large amounts of data in order to select relevant information or items. Common examples include consumer products and services, such as for songs, books, articles, etc. Unfortunately, such systems may be subject to attack by malicious users who want to manipulate the system’s recommendations to suit their needs: to promote their own (or demote a competitor’s) product/service, or to cause disruption in the recommender system. Attacks can cause the recommender system to become unreliable and untrustworthy, resulting in user dissatisfaction. Developers already face tradeoffs in system efficiency and accuracy, and designing for robustness adds an additional dimension for consideration. In this paper, we show how the underlying implementation choices for item-based and user-based Collaborative Filtering recommender systems can affect the accuracy and robustness of recommender systems. We also show how accuracy and robustness can change over a system’s lifetime by analyzing a set of temporal snapshots from system usage over time. Results provide insight into some of the tradeoffs between robustness and accuracy that operators may need to consider in development and evaluation.

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.