Evolutionary algorithms have been frequently used for dynamic optimization problems. With this paper, we contribute to the theoretical understanding of this research area. We present the first computational complexity analysis of evolutionary algorithms for a dynamic variant of a classical combinatorial optimization problem, namely makespan scheduling. We study the model of a strong adversary which is allowed to change one job at regular intervals. Furthermore, we investigate the setting of random changes.

In this work, we introduce the first approach to the Inverse Reinforcement Learning (IRL) problem in relational domains. IRL has been used to recover a more compact representation of the expert policy leading to better generalization performances among different contexts. On the other hand, relational learning allows representing problems with a varying number of objects (potentially infinite), thus provides more generalizable representations of problems and skills. We show how these different formalisms allow one to create a new IRL algorithm for relational domains that can recover with great efficiency rewards from expert data that have strong generalization and transfer properties. We evaluate our algorithm in representative tasks and study the impact of diverse experimental conditions such as : the number of demonstrations, knowledge about the dynamics, transfer among varying dimensions of a problem, and changing dynamics.

Science ultimately seeks to reliably predict aspects of the future; but, how is this even possible in light of the logical paradox that making a prediction may cause the world to evolve in a manner that defeats it? We show how learning can naturally resolve this conundrum. The problem is studied within a causal or temporal version of the Probably Approximately Correct semantics, extended so that a learner's predictions are first recorded in the states upon which the learned hypothesis is later applied. On the negative side, we make concrete the intuitive impossibility of predicting reliably, even under very weak assumptions. On the positive side, we identify conditions under which a generic learning schema, akin to randomized trials, supports agnostic learnability.

Kernel sparse coding is an effective strategy to capturethe non-linear structure of data samples. However,how to learn a robust kernel dictionary remainsan open problem. In this paper, we propose a new optimization model to learn the robust kernel dictionary while isolating outliers in the training samples. This model is essentially based on the decomposition of the reconstruction error into small dense noises and large sparse outliers. The outliererror term is formulated as the product of the sample matrix in the feature space and a diagonal coefficient matrix. This facilitates the kernelized dictionary learning. To solve the non-convex optimization problem, we develop a whole sequence convergent algorithm which guarantees the obtained solution sequence is a Cauchy sequence. The experimental results show that the proposed robust kernel dictionary learning method provides significant performance improvement.

Recently significant advances have been witnessed in the area of distributed word representations based on neural networks, which are also known as word embeddings. Among the new word embedding models, skip-gram negative sampling (SGNS) in the word2vec toolbox has attracted much attention due to its simplicity and effectiveness. However, the principles of SGNS remain not well understood, except for a recent work that explains SGNS as an implicit matrix factorization of the pointwise mutual information (PMI) matrix. In this paper, we provide a new perspective for further understanding SGNS. We point out that SGNS is essentially a representation learning method, which learns to represent the co-occurrence vector for a word. Based on the representation learning view, SGNS is in fact an explicit matrix factorization (EMF) of the words’ co-occurrence matrix. Furthermore, extended supervised word embedding can be established based on our proposed representation learning view.

This paper studies active posterior estimation in a Bayesian setting when the likelihood is expensive to evaluate. Existing techniques for posterior estimation are based on generating samples representative of the posterior. Such methods do not consider efficiency in terms of likelihood evaluations. In order to be query efficient we treat posterior estimation in an active regression framework.  We propose two myopic query strategies to choose where to evaluate the likelihood and implement them using Gaussian processes. Via experiments on a series of synthetic and real examples we demonstrate that our approach is significantly more query efficient than existing techniques and other heuristics for posterior estimation.

The Laplacian matrix of a graph can be used in many areas of mathematical research and has a physical interpretation in various theories. However, there are a few open issues in the Laplacian graph construction: (i) Selecting the appropriate scale of analysis, (ii) Selecting the appropriate number of neighbors, (iii) Handling multiscale data, and, (iv) Dealing with noise and outliers. In this paper, we propose that the affinity between pairs of samples could be computed using sparse representation with proper constraints. This parameter free setting automatically produces the Laplacian graph, leads to significant reduction in computation cost and robustness to the outliers and noise. We further provide an efficient algorithm to solve the difficult optimization problem based on improvement of existing algorithms. To demonstrate our motivation, we conduct spectral clustering experiments with benchmark methods. Empirical experiments on 9 data sets demonstrate the effectiveness of our method.

Most approaches to causal discovery assume a fixed (or time-invariant) causal model; however, in practical situations, especially in neuroscience and economics, causal relations might be time-dependent for various reasons. This paper aims to identify the time-dependent causal relations from observational data. We consider general formulations for time-varying causal modeling on stochastic processes, which can also capture the causal influence from a certain type of unobserved confounders.  We focus on two issues: one is whether such a causal model, including the causal direction, is identifiable from observational data; the other is how to estimate such a model in a principled way. We show that under appropriate assumptions, the causal structure is identifiable according to our formulated model. We then propose a principled way for its estimation by extending Gaussian Process regression, which enables an automatic way to learn how the causal model changes over time. Experimental results on both artificial and real data demonstrate the practical usefulness of time-dependent causal modeling and the effectiveness of the proposed approach for estimation.

However, by being autonomous, structure of the policy, which is often critical for understanding these approaches have the problem of discovering the demonstration, is unobserved. We unnatural hierarchies, which may be difficult to interpret and formulate this problem as active learning of Probabilistic communicate to people. State-Dependent Grammars (PSDGs) from In this paper, we study the problem of learning policies demonstrations. Given a set of expert demonstrations, with hierarchical structure from demonstrations of a teacher our approach learns a hierarchical policy by whose policy is structured hierarchically, with natural applications actively selecting demonstrations and using queries to problems such as tutoring arithmetic, cooking, and to explicate their intentional structure at selected furniture assembly. A key challenge in this problem is that the points. Our contributions include a new algorithm demonstrations do not reveal the hierarchical task structure of for imitation learning of hierarchical policies and the teacher. Rather, only ground states and teacher actions are principled heuristics for the selection of demonstrations directly observable. This can lead to significant ambiguity in and queries.

Model selection is an important problem of cost-sensitive SVM (CS-SVM). Although using solution path to find global optimal parameters is a powerful method for model selection, it is a challenge to extend the framework to solve two regularization parameters of CS-SVM simultaneously. To overcome this challenge, we make three main steps in this paper. (i) A critical-regions-based bi-parameter space partition algorithm is proposed to present all piecewise linearities of CS-SVM. (ii) An invariant-regions-based bi-parameter space partition algorithm is further proposed to compute empirical errors for all parameter pairs. (iii) The global optimal solutions for K-fold cross validation are computed by superposing K invariant region based bi-parameter space partitions into one. The three steps constitute the model selection of CS-SVM which can find global optimal parameter pairs in K-fold cross validation. Experimental results on seven normal datsets and four imbalanced datasets, show that our proposed method has better generalization ability and than various kinds of grid search methods, however, with less running time.