The ability to recognize analogies is an important factor that is closely related to human intelligence. Verbal analogies have been used for evaluating both examinees at university entrance exams as well as algorithms for measuring relational similarity. However, relational similarity measures proposed so far are confined to measuring the similarity be- tween pairs of words. Unfortunately, such pairwise approaches ignore the rich relational structure that exists in real-world knowledge bases containing millions of entities and semantic relations. We pro- pose a method to efficiently identify analogous en- tity tuples from a given entity-relation graph. First, we present an efficient approach for extract- ing potential analogous tuples from a given entity- relation graph. Second, to measure the structural similarity between two tuples, we propose two types of kernel functions: vertex-feature kernels, and edge-feature kernels. Moreover, we combine those kernels to construct composite kernels that simultaneously consider both vertex and edge fea- tures. Experimental results show that our proposed method accurately identifies analogous tuples and significantly outperforms a state-of-the-art pairwise relational similarity measure, extended to tuples.

Post-editing feedback provided by users of on-line translation services offers an excellent opportunity for automatic improvement of statistical machine translation (SMT) systems. However, feedback provided by casual users is very noisy, and must be automatically filtered in order to identify the potentially useful cases. We present a study on automatic feedback filtering in a real weblog collected from Reverso.net. We extend and re-annotate a training corpus, define an extended set of simple features and approach the problem as a binary classification task, experimenting with linear and kernelbased classifiers and feature selection. Results on the feedback filtering task show a significant improvement over the majority class, but also a precision ceiling around 70-80%. This reflects the inherent difficulty of the problemand indicates that shallow features cannot fully capture the semantic nature of the problem. Despite the modest results on the filtering task, the classifiers are proven effective in an application-based evaluation. The incorporation of a filtered set of feedback instances selected from a larger corpus significantly improves the performance of a phrase-based SMT system, according to a set of standard evaluation metrics.

Understanding the molecular mechanisms of life requires decoding the functions of the proteins in an organism. Various high-throughput experimental techniques have been developed to characterize biological systems at the genome scale. A fundamental challenge of the post-genomic era is to assign biological functions to all the proteins encoded by the genome using high-throughput biological data. To address this challenge, we propose a novel Laplacian Network Partitioning incorporating function category Correlations (LNPC) method to predict protein function on proteinprotein interaction (PPI) networks by optimizing a Laplacian based quotient objective function that seeks the optimal network configuration to maximize consistent function assignments over edges on the whole graph. Unlike the existing approaches that have no unique optimization solutions, our optimization problem has unique global solution by eigen-decomposition methods. The correlations among protein function categories are quantified and incorporated into a correlated protein affinity graph which is integrated into the PPI graph to significantly improve the protein function prediction accuracy. We apply our new method to the BioGRID dataset for the Saccharomyces Cerevisiae species using the MIPS annotation scheme. Our new method outperforms other related state-of-the-art approaches more than 63% by the average precision of function prediction and 53% by the average F1 score.

The goal of controlling a gene regulatory network (GRN) is to generate an intervention strategy, i.e., a control policy, such that by applying the policy the system will avoid undesirable states. In this work, we propose a method to control GRNs by using Batch Mode Reinforcement Learning (Batch RL). Our idea is based on the fact that time series gene expression data can actually be interpreted as a sequence of experience tuples collected from the environment. Existing studies on this control task try to infer a model using gene expression data and then calculate a control policy over the constructed model. However, we propose a method that can directly use the available gene expression data to obtain an approximated control policy for gene regulation that avoids the time consuming model building phase. Results show that we can obtain policies for gene regulation systems of several thousands of genes just in several seconds while existing solutions get stuck for even tens of genes. Interestingly, the reported results also show that our method produces policies that are almost as good as the ones generated by existing model dependent methods.

Authoring tutorials for complex software applications is a time consuming process. It also highly depends on the tutorial designer's skill level and experience. This paper introduces an approach which automatically generates software tutorials using the digital artifacts produced by the users of a software program. We model this process as an optimal planning problem using software produced artifacts, software specifications and the human-computer interaction Keystroke-Level Model (KLM). We present TutorialPlan, an automated tutorial generator, which creates step-by-step text and image instructions from CAD drawings and helps users learn AutoCAD, a complex design and drafting software. In our tutorial generator, the optimal planning problem is represented and solved using DLV, a general Answer Set Programming (ASP) system. DLV offers a natural representation of both the problem and the heuristics needed to solve it efficiently. A user study shows that the tutorials generated by our system are comparable to those generated by experienced AutoCAD users.

On-line portfolio selection has been attracting increasing interests from artificial intelligence community in recent decades. Mean reversion, as one most frequent pattern in financial markets, plays an important role in some state-of-the-art strategies. Though successful in certain datasets, existing mean reversion strategies do not fully consider noises and outliers in the data, leading to estimation error and thus non-optimal portfolios, which results in poor performance in practice. To overcome the limitation, we propose to exploit the reversion phenomenon by robust $L_1$-median estimator, and design a novel on-line portfolio selection strategy named ``Robust Median Reversion" (RMR), which makes optimal portfolios based on the improved reversion estimation. Empirical results on various real markets show that RMR can overcome the drawbacks of existing mean reversion algorithms and achieve significantly better results. Finally, RMR runs in linear time, and thus is suitable for large-scale trading applications.

Interactive Narrative is a form of digital entertainment heavily based on AI techniques to support narrative generation and user interaction, significant progress arriving with the adoption of planning techniques. However, there is a lack of unified models that integrate generation, user responses and interaction. This paper addresses this by revisiting existing Interactive Narrative paradigms, granting explicit status to users’ disposition towards story characters as part of narrative generation as well as adding support for new forms of interaction. We demonstrate this with a novel Brain-Computer Interface (BCI) design, incorporating empathy for a main character derived from brain signals within filmic conceptions of narrative which drives generation using planning techniques. Results from an experimental study with a fullyimplemented system demonstrate the effectiveness of a EEG neurofeedback-based approach, showing that subjects can successfully modulate empathic support of a character in a medical drama. MRI analysis also shows activations in associated regions of the brain during expression of support.

Constraint-based applications such as configurators, recommenders, and scheduling systems support users in complex decision making scenarios. Typically, these systems try to identify a solution that satisfies all articulated user requirements. If the requirements are inconsistent with the underlying constraint set, users have to be actively supported in finding a way out from the no solution could be found dilemma. In this paper we introduce techniques that support the calculation of personalized diagnoses for inconsistent constraint sets. These techniques significantly improve the diagnosis prediction quality compared to approaches based on the calculation of minimal cardinality diagnoses. In order to show the applicability of our approach we present the results of an empirical study and a corresponding performance analysis.

Natural deduction, which is a method for establishing validity of propositional type arguments, helps develop important reasoning skills and is thus a key ingredient in a course on introductory logic. We present two core components, namely solution generation and practice problem generation, for enabling computer-aided education for this important subject domain. The key enabling technology is use of an offline-computed data-structure called Universal Proof Graph (UPG) that encodes all possible applications of inference rules over all small propositions abstracted using their bitvector-based truth-table representation. This allows an efficient forward search for solution generation. More interestingly, this allows generating fresh practice problems that have given solution characteristics by performing a backward search in UPG. We obtained around 300 natural deduction problems from various textbooks. Our solution generation procedure can solve many more problems than the traditional forward-chaining based procedure, while our problem generation procedure can efficiently generate several variants with desired characteristics.

Cross-domain learning targets at leveraging the knowledge from source domains to train accurate models for the test data from target domains with different but related data distributions. To tackle the challenge of data distribution difference in terms of raw features, previous works proposed to mine high-level concepts (e.g., word clusters) across data domains, which shows to be more appropriate for classification. However, all these works assume that the same set of concepts are shared in the source and target domains in spite that some distinct concepts may exist only in one of the data domains. Thus, we need a general framework, which can incorporate both shared and distinct concepts, for cross-domain classification. To this end, we develop a probabilistic model, by which both the shared and distinct concepts can be learned by the EM process which optimizes the data likelihood. To validate the effectiveness of this model we intentionally construct the classification tasks where the distinct concepts exist in the data domains. The systematic experiments demonstrate the superiority of our model over all compared baselines, especially on those much more challenging tasks.