jmlr jmlr2012 jmlr2012-57 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Daniel L. Ly, Hod Lipson
Abstract: A hybrid dynamical system is a mathematical model suitable for describing an extensive spectrum of multi-modal, time-series behaviors, ranging from bouncing balls to air traffic controllers. This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. MMSR consists of two subalgorithms—clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. MMSR is evaluated on a collection of four synthetic data sets and outperforms other multi-modal machine learning approaches in both accuracy and interpretability, even in the presence of noise. Furthermore, the versatility of MMSR is demonstrated by identifying and inferring classical expressions of transistor modes from recorded measurements. Keywords: hybrid dynamical systems, evolutionary computation, symbolic piecewise functions, symbolic binary classification
Reference: text
sentIndex sentText sentNum sentScore
1 This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. [sent-6, score-1.191]
2 MMSR consists of two subalgorithms—clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. [sent-7, score-1.059]
3 These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. [sent-8, score-0.631]
4 Keywords: hybrid dynamical systems, evolutionary computation, symbolic piecewise functions, symbolic binary classification 1. [sent-11, score-1.445]
5 In contrast, symbolic and analytical models, such as those derived from first principles, provide such insight in addition to producing accurate predictions. [sent-15, score-0.403]
6 Therefore, the automated the search for symbolic models is an important challenge for machine learning research. [sent-16, score-0.427]
7 Thus, the ability to automate the modeling of hybrid dynamical systems from time-series data will have a profound affect on the growth and automation of science and engineering. [sent-28, score-0.596]
8 Despite the variety of approaches for inferring models of time-series data, none are particularly well-suited for building apt descriptions of hybrid dynamical systems. [sent-29, score-0.616]
9 Thus, constructing symbolic models of hybrid dynamical systems which can be easily and naturally interpreted by scientists and engineers is a key challenge. [sent-39, score-0.985]
10 The primary contribution of this paper is a novel algorithm, called multi-modal symbolic regression (MMSR), to learn symbolic models of discrete dynamical systems with continuous mappings, as an initial step towards learning hybrid automata. [sent-40, score-1.483]
11 It is a data-driven algorithm that formulates symbolic expressions to describe both the continuous behavior and discrete dynamics of an arbitrary system. [sent-41, score-0.69]
12 Two general learning processes are presented: the first algorithm, clustered symbolic regression (CSR), generates symbolic models of piecewise functions and the second algorithm, transition Modeling (TM), searches for symbolic inequalities to model transition conditions. [sent-42, score-1.57]
13 These processes are then applied to a hybrid dynamical systems framework and are used to reliably model a variety of classical problems. [sent-43, score-0.558]
14 The remainder of this paper is organized as follows: Section 2 provides a brief introduction to hybrid dynamical systems, as well as a description of the relevant work in related fields. [sent-45, score-0.558]
15 Background This section begins with a brief introduction to the mathematical background of hybrid automata, an inclusive model that describes a variety of hybrid systems. [sent-52, score-0.573]
16 This is followed by a discussion of the related work in learning hybrid dynamical systems. [sent-54, score-0.558]
17 1 Hybrid Automata Due to the its inherent complexity, hybrid dynamical systems have only recently emerged as an area of formal research. [sent-56, score-0.558]
18 If none of the transition conditions are satisfied, then the hybrid automata remains in the current mode and the state variables evolves according to the specified behavior. [sent-77, score-0.603]
19 The challenge in modeling hybrid automata arises from the property that the latent “state” of a hybrid automata depends on both the discrete mode, mk , as well as the continuous state space vector, x. [sent-81, score-0.855]
20 As with all dynamical systems, the evolution of the system depends on the initial condition of the latent modes as well as the input variables. [sent-82, score-0.516]
21 These assumptions describe a continuous-discrete hybrid system that evolves with discrete dynamics but contains continuous input-output relationships. [sent-92, score-0.41]
22 This formulation makes the symbolic inference tractable while also providing a first step to the general solution of inferring hybrid automata. [sent-93, score-0.705]
23 To continue with the driverless car example, a hybrid automata is transformed into the desired model by converting the mode and differentiated inputs as explicit inputs and outputs (Figure 2). [sent-100, score-0.514]
24 Figure 2: A conversion of the 1D driverless car hybrid automata as a discrete dynamical model with continuous mappings. [sent-101, score-0.751]
25 Interest in hybrid dynamical systems is primarily spurred by the control systems community and consequently, they have proposed a variety of approaches to infer dynamical systems. [sent-105, score-0.892]
26 One approach addresses the problem of modeling discrete-time hybrid dynamical systems by reducing the problem to switched, piecewise affine models (Ferrari-Trecate et al. [sent-106, score-0.657]
27 Another approach uses non-linear, generalized, parametric models to represent hybrid dynamical systems. [sent-111, score-0.644]
28 Consequently, there has been significant interest in extracting rules from parametric, recurrent neural networks to build a formal, symbolic model and providing an important layer of knowledge abstraction (Omlin and Giles, 1993, 1996a,b; Vahed and Omlin, 2004). [sent-123, score-0.524]
29 Our technique attempts to resolve these various challenges by building models of hybrid dynamical systems that uses non-linear symbolic expressions for both the behaviors as well as the transitions. [sent-131, score-1.229]
30 Rather than imposing a linear structure or using parametric models, symbolic expressions are inferred to provide a description that is in the natural, mathematical representation used by scientists and engineers. [sent-132, score-0.673]
31 This is followed by the description of two, general algorithms: clustered symbolic regression and transition modelling. [sent-135, score-0.585]
32 The section is concluded by combining both subalgorithms within a hybrid dynamics framework to form the multi-modal symbolic regression algorithm. [sent-136, score-0.751]
33 1 Problem Formalization The goal of the algorithm is to infer a symbolic discrete dynamics model with continuous mappings from time-series data, where symbolic mathematical expressions are learned for both the behaviors as well as the transition events. [sent-138, score-1.31]
34 Consider a dynamical system that is described by: mn = T (mn−1 , un ), yn = F(mn , un ) F1 (un ) , if mn = 1 . [sent-139, score-0.585]
35 To learn symbolic models of discrete dynamical systems with continuous mappings, the multimodal symbolic regression (MMSR) algorithm is composed of two general algorithms: clustered symbolic regression (CSR) and transition modelling (TM). [sent-155, score-1.836]
36 CSR is used to cluster the data into symbolic subfunctions, providing a method to determine the modal data membership while also inferring meaningful expressions for each subfunction. [sent-156, score-0.768]
37 After CSR determines the modal membership, TM is then applied to find symbolic expressions for the transition conditions. [sent-157, score-0.705]
38 By dividing the problem into the CSR and TM subdomains, our approach leverages the property that each behavior is unique to infer accurate and consistent hybrid dynamical systems. [sent-161, score-0.638]
39 2 Clustered Symbolic Regression The first algorithm is clustered symbolic regression (CSR), which involves using unsupervised learning techniques to solve the challenging issue of distinguishing individual functions while simultaneously infers a symbolic model for each of them. [sent-163, score-0.87]
40 This subsection begins with a formal definition of the problem, followed by a brief overview of two learning approaches: symbolic regression (SR) and expectation-maximization (EM), respectively. [sent-165, score-0.464]
41 These approaches are then unified as clustered symbolic regression. [sent-166, score-0.443]
42 However, unlike traditional clustering problems, each cluster is represented by a symbolic expression and there is no prior knowledge regarding the structure of these submodels. [sent-179, score-0.403]
43 2 S YMBOLIC R EGRESSION The first component of CSR is symbolic regression (SR): an genetic programming algorithm that is capable of reliably inferring symbolic expressions that models a given data set (Cramer, 1985; Dickmanns et al. [sent-183, score-1.128]
44 In particular, SR uses a microprogram or tree structure to represent symbolic expressions. [sent-191, score-0.427]
45 This tree structure provides a terse representation of symbolic functions that is capable of representing a wide range of plausible expressions—for example, complex expressions, including non-linear and rational equations, can be easily represented. [sent-193, score-0.467]
46 Evaluating an expression requires simply substituting values from the data set, traversing the tree and computing well-defined 3592 L EARNING S YMBOLIC R EPRESENTATIONS OF H YBRID DYNAMICAL S YSTEMS Figure 3: Flowchart describing the symbolic regression algorithm. [sent-195, score-0.451]
47 Unlike other machine learning algorithms which tweak a vast collection of intangible numerical parameters, symbolic expressions are the foundation of mathematical notation and often provide key insight into the fundamental relationships of such models. [sent-204, score-0.556]
48 In symbolic expressions, 3593 LY AND L IPSON Figure 5: An example of the set of solutions provided by symbolic regression. [sent-207, score-0.806]
49 Currently, there are no algorithms that are capable of symbolically regressing unlabeled data generated by multi-modal systems, such as data from a hybrid dynamical system or piecewise function. [sent-223, score-0.679]
50 4 C LUSTERED S YMBOLIC R EGRESSION The clustered symbolic regression (CSR) is a novel algorithm that is capable of finding symbolic expressions for piecewise functions. [sent-238, score-1.1]
51 ∑K N yn | fk (un ), σ2 k=1 k (4) Note that the membership probability reinforces exclusivity—given two subfunctions with the same expression, the model with lower variance has stronger membership values over the same data. [sent-244, score-0.442]
52 This algorithm is presented as a generalized solution to classification with symbolic expressions, separate from the hybrid dynamics framework. [sent-270, score-0.698]
53 (10) n=1 Despite the variety of approaches to binary classification, the explicit requirements for a nonlinear, symbolic model of the discriminant function makes this problem challenging. [sent-276, score-0.403]
54 While multiclass classification may be more appropriate, it results in a significantly more challenging problem for symbolic models and is left for future work. [sent-277, score-0.427]
55 2 R ELATED W ORK Although using evolutionary computation for classification has been previously investigated, this algorithm is novel due to its reformulation of the classification problem as symbolic regression, providing an assortment of benefits. [sent-284, score-0.447]
56 (2004) designed an evolutionary program that is capable of generating symbolic expressions for discriminant functions. [sent-292, score-0.64]
57 Using the step function and function composition, the classification problem (Equation 9) is reformatted as a standard symbolic regression problem using the search relationship: ζn = step(Z(un )). [sent-301, score-0.427]
58 This reformulation allows a symbolic regression framework to find for symbolic, classification expressions, Z(·), that define membership domains. [sent-302, score-0.574]
59 4 Modeling Hybrid Dynamical Systems To infer symbolic models of hybrid dynamical systems, two general CSR and TM algorithms are applied to form the multi-modal symbolic regression algorithm (MMSR). [sent-320, score-1.456]
60 CSR is first used to cluster the data into distinct modes while simultaneously inferring symbolic expressions for each subfunction. [sent-321, score-0.724]
61 Using the modal membership from CSR, TM is subsequently applied to find symbolic expressions for the transition conditions. [sent-322, score-0.852]
62 CSR determines the modes of the hybrid system, M , by calculating the membership of an input-output pair (expectation step of Algorithm 2). [sent-326, score-0.549]
63 Simultaneously, CSR also infers a non-linear, symbolic expression for each of the behaviors, F , through weighted symbolic regression (maximization step of Algorithm 2). [sent-327, score-0.83]
64 Using the modal memberships from CSR, TM searches for symbolic expressions of the transition events, T . [sent-328, score-0.705]
65 Using the membership values from CSR to determine the mode at every data point, searching for transition events is rephrased as a classification problem: a transition from mode k to mode k′ occurs at index n if and only if γk,n = 1 and γk′ ,n+1 = 1 (Figure 6). [sent-331, score-0.782]
66 This definition is advantageous since PTPs are identified by only using the membership information of only the current mode, γk,n , and no other membership information from the other modes are required. [sent-341, score-0.428]
67 − n=1 N−1 ˜ ∑n=1 γk,n (17) (18) The complete MMSR algorithm to learn analytic models of hybrid dynamical systems is summarized in Algorithm 3. [sent-354, score-0.582]
68 1 Experimental Details In these experiments, the publicly available Eureqa API (Schmidt and Lipson, 2012) was used as a backend for the symbolic regression computation in both the CSR and TM. [sent-361, score-0.427]
69 In symbolic representations, expressions are considered equivalent if and only if each subtree differs by at most scalar multiplicatives. [sent-436, score-0.556]
70 3 DATA S ETS Since there are no standardized data sets for the inference of hybrid dynamical systems, the MMSR algorithm was evaluated on a collection of four data sets based on classical hybrid systems (Henzinger, 1996; van der Schaft and Schumacher, 2000) and intelligent robotics (Reger et al. [sent-447, score-0.826]
71 Furthermore, these data sets contain non-trivial transitions and behaviors, and thus, present more challenging inference problems than the simple switching systems often used to evaluate parametric models of hybrid systems (Le et al. [sent-459, score-0.463]
72 Hysteresis Relay—The first data set is a hysteresis relay: a classical hybrid system (Visintin, 1995; van der Schaft and Schumacher, 2000). [sent-467, score-0.444]
73 Although it is a simple hybrid dynamical system with 3607 LY AND L IPSON linear behaviors, it does not exhibit simple switching as the transitions depend on the mode since both behaviors are defined for u ∈ [−0. [sent-470, score-0.926]
74 Continuous Hysteresis Loop—The second data set is a continuous hysteresis loop: a non-linear extension of the classical hybrid system (Visintin, 1995). [sent-473, score-0.485]
75 Non-linear System—The fourth and final data set is a system without any physical counterpart, but the motivation for this system was to evaluate the capabilities of the learning algorithms for finding non-linear, symbolic expressions. [sent-485, score-0.491]
76 The process of converting the program output into a hybrid automata model is summarized in Figure 13, from a run obtained on the light-interacting robot training data with 10% noise. [sent-493, score-0.437]
77 Provided with the number of modes, the algorithm searched for distinct behaviors and their subsequent transitions, returning a single symbolic expression for each of the inferred components. [sent-494, score-0.549]
78 The expressions were algebraically simplified as necessary, and a hybrid dynamical model was constructed. [sent-495, score-0.711]
79 There is an inverse relationship between the generality of the algorithm and its performance at inferring hybrid dynamical systems. [sent-552, score-0.592]
80 MMSR, however, is tailored to inferring hybrid dynamical systems from unlabeled, time-series data and consequently infers a superior model for numerical predictions. [sent-554, score-0.592]
81 38*u1ˆ2) 0 −2 −4 −6 −6 −4 −2 0 u −u 1 (b) Inferred System Diagram 2 4 6 2 (c) Behaviors with Training Data Figure 13: Conversion from program output to hybrid dynamical model for the phototaxic robot with 10% noise. [sent-569, score-0.692]
82 This suggests that the symbolic approach is better suited for the primary goal of knowledge extraction, by providing accurate as well as parsimonious models. [sent-573, score-0.403]
83 5 1 u (c) Figure 14: The input-output relationship of the regression networks of NNHMM and symbolic expressions of MMSR (black) overlaid on the Continuous Hysteresis Loop data (grey). [sent-599, score-0.607]
84 Continuous Hysteresis Loop—This data set was ideal as it was sufficiently difficult to model, but simple enough to analyze and provide insight into how the algorithms perform on hybrid dynamical systems. [sent-602, score-0.558]
85 This data set provides an example of how symbolic expressions aid in knowledge abstraction as it is easy to infer that the relative distance between the robot and the light position, u1 − u2 , is an integral component of the system as it is a repeated motif in the each of the behaviors. [sent-623, score-0.696]
86 As the transitions events were consistent between modes, which is indicative of the simple switching behavior exhibited by transistors, the system diagram was simplified to a piecewise representation with additional symbolic manipulations (Figure 16b). [sent-656, score-0.705]
87 , 2012), determining the optimal model for hybrid dynamical systems is intractable. [sent-664, score-0.558]
88 Discussion and Future Work A novel algorithm, multi-modal symbolic regression (MMSR), was presented to infer non-linear, symbolic models of hybrid dynamical systems. [sent-678, score-1.456]
89 The first subalgorithm is clustered symbolic regression (CSR), designed to construct expressions for piecewise functions of unlabeled data. [sent-680, score-0.657]
90 By combining symbolic regression (SR) with expectationmaximization (EM), CSR is able to separate the data into distinct clusters, and then subsequently find mathematical expressions for each subfunction. [sent-681, score-0.58]
91 The second subalgorithm is transition modeling (TM), which searches for binary classification boundaries and expresses them as a symbolic inequality. [sent-683, score-0.559]
92 These two subalgorithms are combined and used to infer symbolic models of hybrid dynamical systems. [sent-685, score-1.058]
93 Symbolic modelling provides numerous benefits over parametric numerical models with the primary advantage of operating in symbolic expressions, the standard language of mathematics and science. [sent-691, score-0.525]
94 In addition, there is a wealth of theory in symbolic mathematics, including approximation and equivalence theories such as Taylor expansions, which may aid understanding inferred models. [sent-693, score-0.458]
95 A primary concern for symbolic modeling is how well it extends as the complexity increases and whether an easily interpretable model exists. [sent-695, score-0.469]
96 Deriving models from first principles is often similarly challenging while parametric approaches, such as RNN and NNHMM, are likely to settle on local optima and have difficulty achieve even numerically accurate models, even for relatively simple hybrid dynamical systems. [sent-697, score-0.703]
97 While symbolic expressions may not exist for complex systems, it does present a viable alternative approach that may have the additional benefit of insight and interpretability. [sent-699, score-0.556]
98 Extraction, insertion and refinement of symbolic rules in dynamically driven recurrent neural networks. [sent-904, score-0.471]
99 A machine learning method for extracting symbolic knowledge from recurrent neural networks. [sent-1007, score-0.471]
100 Order of nonlinearity as a complexity measure for models generated by symbolic regression via Pareto genetic programming. [sent-1029, score-0.526]
wordName wordTfidf (topN-words)
[('symbolic', 0.403), ('mmsr', 0.373), ('dynamical', 0.29), ('hybrid', 0.268), ('csr', 0.219), ('sr', 0.17), ('expressions', 0.153), ('membership', 0.147), ('modes', 0.134), ('hysteresis', 0.132), ('ymbolic', 0.132), ('ipson', 0.124), ('vgs', 0.124), ('mode', 0.124), ('transition', 0.118), ('epresentations', 0.117), ('ybrid', 0.117), ('ystems', 0.117), ('ly', 0.113), ('nnhmm', 0.11), ('un', 0.104), ('automata', 0.093), ('behaviors', 0.091), ('tm', 0.087), ('aic', 0.079), ('transitions', 0.077), ('pareto', 0.075), ('sig', 0.075), ('tness', 0.073), ('fk', 0.068), ('recurrent', 0.068), ('em', 0.067), ('transistor', 0.066), ('parametric', 0.062), ('phototaxic', 0.058), ('inferred', 0.055), ('robot', 0.052), ('fitness', 0.051), ('delity', 0.05), ('diagram', 0.049), ('genetic', 0.047), ('hidden', 0.044), ('system', 0.044), ('relay', 0.044), ('rnns', 0.044), ('vds', 0.044), ('evolutionary', 0.044), ('infer', 0.044), ('yn', 0.043), ('continuous', 0.041), ('network', 0.041), ('capable', 0.04), ('clustered', 0.04), ('temporary', 0.039), ('np', 0.039), ('population', 0.039), ('modeling', 0.038), ('earning', 0.038), ('frasconi', 0.038), ('piecewise', 0.037), ('begins', 0.037), ('lipson', 0.037), ('omlin', 0.037), ('ptp', 0.037), ('subfunctions', 0.037), ('fuzzy', 0.036), ('behavior', 0.036), ('modelling', 0.036), ('tk', 0.035), ('optima', 0.034), ('inferring', 0.034), ('switching', 0.032), ('noise', 0.032), ('modal', 0.031), ('rnn', 0.031), ('nodes', 0.031), ('discrete', 0.03), ('drain', 0.029), ('driverless', 0.029), ('ecsr', 0.029), ('ntp', 0.029), ('schaft', 0.029), ('subalgorithms', 0.029), ('subfunction', 0.029), ('schmidt', 0.029), ('equation', 0.028), ('predictive', 0.028), ('complexity', 0.028), ('events', 0.027), ('dynamics', 0.027), ('networks', 0.027), ('layer', 0.026), ('principles', 0.025), ('recombination', 0.025), ('tree', 0.024), ('latent', 0.024), ('regression', 0.024), ('output', 0.024), ('evolution', 0.024), ('models', 0.024)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000005 57 jmlr-2012-Learning Symbolic Representations of Hybrid Dynamical Systems
Author: Daniel L. Ly, Hod Lipson
Abstract: A hybrid dynamical system is a mathematical model suitable for describing an extensive spectrum of multi-modal, time-series behaviors, ranging from bouncing balls to air traffic controllers. This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. MMSR consists of two subalgorithms—clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. MMSR is evaluated on a collection of four synthetic data sets and outperforms other multi-modal machine learning approaches in both accuracy and interpretability, even in the presence of noise. Furthermore, the versatility of MMSR is demonstrated by identifying and inferring classical expressions of transistor modes from recorded measurements. Keywords: hybrid dynamical systems, evolutionary computation, symbolic piecewise functions, symbolic binary classification
2 0.057281464 55 jmlr-2012-Learning Algorithms for the Classification Restricted Boltzmann Machine
Author: Hugo Larochelle, Michael Mandel, Razvan Pascanu, Yoshua Bengio
Abstract: Recent developments have demonstrated the capacity of restricted Boltzmann machines (RBM) to be powerful generative models, able to extract useful features from input data or construct deep artificial neural networks. In such settings, the RBM only yields a preprocessing or an initialization for some other model, instead of acting as a complete supervised model in its own right. In this paper, we argue that RBMs can provide a self-contained framework for developing competitive classifiers. We study the Classification RBM (ClassRBM), a variant on the RBM adapted to the classification setting. We study different strategies for training the ClassRBM and show that competitive classification performances can be reached when appropriately combining discriminative and generative training objectives. Since training according to the generative objective requires the computation of a generally intractable gradient, we also compare different approaches to estimating this gradient and address the issue of obtaining such a gradient for problems with very high dimensional inputs. Finally, we describe how to adapt the ClassRBM to two special cases of classification problems, namely semi-supervised and multitask learning. Keywords: restricted Boltzmann machine, classification, discriminative learning, generative learning
3 0.055712979 51 jmlr-2012-Integrating a Partial Model into Model Free Reinforcement Learning
Author: Aviv Tamar, Dotan Di Castro, Ron Meir
Abstract: In reinforcement learning an agent uses online feedback from the environment in order to adaptively select an effective policy. Model free approaches address this task by directly mapping environmental states to actions, while model based methods attempt to construct a model of the environment, followed by a selection of optimal actions based on that model. Given the complementary advantages of both approaches, we suggest a novel procedure which augments a model free algorithm with a partial model. The resulting hybrid algorithm switches between a model based and a model free mode, depending on the current state and the agent’s knowledge. Our method relies on a novel definition for a partially known model, and an estimator that incorporates such knowledge in order to reduce uncertainty in stochastic approximation iterations. We prove that such an approach leads to improved policy evaluation whenever environmental knowledge is available, without compromising performance when such knowledge is absent. Numerical simulations demonstrate the effectiveness of the approach on policy gradient and Q-learning algorithms, and its usefulness in solving a call admission control problem. Keywords: reinforcement learning, temporal difference, stochastic approximation, markov decision processes, hybrid model based model free algorithms
4 0.052903023 41 jmlr-2012-Exploration in Relational Domains for Model-based Reinforcement Learning
Author: Tobias Lang, Marc Toussaint, Kristian Kersting
Abstract: A fundamental problem in reinforcement learning is balancing exploration and exploitation. We address this problem in the context of model-based reinforcement learning in large stochastic relational domains by developing relational extensions of the concepts of the E 3 and R- MAX algorithms. Efficient exploration in exponentially large state spaces needs to exploit the generalization of the learned model: what in a propositional setting would be considered a novel situation and worth exploration may in the relational setting be a well-known context in which exploitation is promising. To address this we introduce relational count functions which generalize the classical notion of state and action visitation counts. We provide guarantees on the exploration efficiency of our framework using count functions under the assumption that we had a relational KWIK learner and a near-optimal planner. We propose a concrete exploration algorithm which integrates a practically efficient probabilistic rule learner and a relational planner (for which there are no guarantees, however) and employs the contexts of learned relational rules as features to model the novelty of states and actions. Our results in noisy 3D simulated robot manipulation problems and in domains of the international planning competition demonstrate that our approach is more effective than existing propositional and factored exploration techniques. Keywords: reinforcement learning, statistical relational learning, exploration, relational transition models, robotics
5 0.048824459 6 jmlr-2012-A Model of the Perception of Facial Expressions of Emotion by Humans: Research Overview and Perspectives
Author: Aleix Martinez, Shichuan Du
Abstract: In cognitive science and neuroscience, there have been two leading models describing how humans perceive and classify facial expressions of emotion—the continuous and the categorical model. The continuous model defines each facial expression of emotion as a feature vector in a face space. This model explains, for example, how expressions of emotion can be seen at different intensities. In contrast, the categorical model consists of C classifiers, each tuned to a specific emotion category. This model explains, among other findings, why the images in a morphing sequence between a happy and a surprise face are perceived as either happy or surprise but not something in between. While the continuous model has a more difficult time justifying this latter finding, the categorical model is not as good when it comes to explaining how expressions are recognized at different intensities or modes. Most importantly, both models have problems explaining how one can recognize combinations of emotion categories such as happily surprised versus angrily surprised versus surprise. To resolve these issues, in the past several years, we have worked on a revised model that justifies the results reported in the cognitive science and neuroscience literature. This model consists of C distinct continuous spaces. Multiple (compound) emotion categories can be recognized by linearly combining these C face spaces. The dimensions of these spaces are shown to be mostly configural. According to this model, the major task for the classification of facial expressions of emotion is precise, detailed detection of facial landmarks rather than recognition. We provide an overview of the literature justifying the model, show how the resulting model can be employed to build algorithms for the recognition of facial expression of emotion, and propose research directions in machine learning and computer vision researchers to keep pushing the state of the art in these areas. We also discuss how the model can aid in stu
6 0.045475379 21 jmlr-2012-Bayesian Mixed-Effects Inference on Classification Performance in Hierarchical Data Sets
7 0.042706564 31 jmlr-2012-DEAP: Evolutionary Algorithms Made Easy
8 0.038239803 78 jmlr-2012-Nonparametric Guidance of Autoencoder Representations using Label Information
9 0.033263691 42 jmlr-2012-Facilitating Score and Causal Inference Trees for Large Observational Studies
10 0.032158148 15 jmlr-2012-Algebraic Geometric Comparison of Probability Distributions
11 0.029140634 38 jmlr-2012-Entropy Search for Information-Efficient Global Optimization
12 0.028641069 95 jmlr-2012-Random Search for Hyper-Parameter Optimization
13 0.028434834 35 jmlr-2012-EP-GIG Priors and Applications in Bayesian Sparse Learning
14 0.028273726 70 jmlr-2012-Multi-Assignment Clustering for Boolean Data
15 0.027875086 73 jmlr-2012-Multi-task Regression using Minimal Penalties
16 0.026843963 116 jmlr-2012-Transfer in Reinforcement Learning via Shared Features
17 0.026039401 79 jmlr-2012-Oger: Modular Learning Architectures For Large-Scale Sequential Processing
18 0.025195263 106 jmlr-2012-Sign Language Recognition using Sub-Units
19 0.02376505 80 jmlr-2012-On Ranking and Generalization Bounds
20 0.023719262 11 jmlr-2012-A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models
topicId topicWeight
[(0, -0.126), (1, 0.05), (2, 0.114), (3, -0.074), (4, 0.045), (5, -0.058), (6, 0.028), (7, 0.0), (8, -0.017), (9, 0.067), (10, -0.031), (11, 0.013), (12, 0.061), (13, 0.024), (14, -0.039), (15, 0.085), (16, 0.024), (17, 0.061), (18, 0.063), (19, -0.049), (20, -0.081), (21, 0.037), (22, 0.061), (23, 0.089), (24, -0.087), (25, -0.12), (26, -0.018), (27, 0.037), (28, -0.239), (29, -0.085), (30, -0.114), (31, 0.02), (32, 0.005), (33, -0.05), (34, 0.059), (35, 0.325), (36, 0.102), (37, 0.072), (38, -0.093), (39, -0.069), (40, 0.132), (41, -0.19), (42, 0.111), (43, 0.06), (44, -0.053), (45, 0.053), (46, -0.23), (47, 0.149), (48, -0.087), (49, -0.264)]
simIndex simValue paperId paperTitle
same-paper 1 0.95454419 57 jmlr-2012-Learning Symbolic Representations of Hybrid Dynamical Systems
Author: Daniel L. Ly, Hod Lipson
Abstract: A hybrid dynamical system is a mathematical model suitable for describing an extensive spectrum of multi-modal, time-series behaviors, ranging from bouncing balls to air traffic controllers. This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. MMSR consists of two subalgorithms—clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. MMSR is evaluated on a collection of four synthetic data sets and outperforms other multi-modal machine learning approaches in both accuracy and interpretability, even in the presence of noise. Furthermore, the versatility of MMSR is demonstrated by identifying and inferring classical expressions of transistor modes from recorded measurements. Keywords: hybrid dynamical systems, evolutionary computation, symbolic piecewise functions, symbolic binary classification
2 0.46989438 6 jmlr-2012-A Model of the Perception of Facial Expressions of Emotion by Humans: Research Overview and Perspectives
Author: Aleix Martinez, Shichuan Du
Abstract: In cognitive science and neuroscience, there have been two leading models describing how humans perceive and classify facial expressions of emotion—the continuous and the categorical model. The continuous model defines each facial expression of emotion as a feature vector in a face space. This model explains, for example, how expressions of emotion can be seen at different intensities. In contrast, the categorical model consists of C classifiers, each tuned to a specific emotion category. This model explains, among other findings, why the images in a morphing sequence between a happy and a surprise face are perceived as either happy or surprise but not something in between. While the continuous model has a more difficult time justifying this latter finding, the categorical model is not as good when it comes to explaining how expressions are recognized at different intensities or modes. Most importantly, both models have problems explaining how one can recognize combinations of emotion categories such as happily surprised versus angrily surprised versus surprise. To resolve these issues, in the past several years, we have worked on a revised model that justifies the results reported in the cognitive science and neuroscience literature. This model consists of C distinct continuous spaces. Multiple (compound) emotion categories can be recognized by linearly combining these C face spaces. The dimensions of these spaces are shown to be mostly configural. According to this model, the major task for the classification of facial expressions of emotion is precise, detailed detection of facial landmarks rather than recognition. We provide an overview of the literature justifying the model, show how the resulting model can be employed to build algorithms for the recognition of facial expression of emotion, and propose research directions in machine learning and computer vision researchers to keep pushing the state of the art in these areas. We also discuss how the model can aid in stu
3 0.37441957 79 jmlr-2012-Oger: Modular Learning Architectures For Large-Scale Sequential Processing
Author: David Verstraeten, Benjamin Schrauwen, Sander Dieleman, Philemon Brakel, Pieter Buteneers, Dejan Pecevski
Abstract: Oger (OrGanic Environment for Reservoir computing) is a Python toolbox for building, training and evaluating modular learning architectures on large data sets. It builds on MDP for its modularity, and adds processing of sequential data sets, gradient descent training, several crossvalidation schemes and parallel parameter optimization methods. Additionally, several learning algorithms are implemented, such as different reservoir implementations (both sigmoid and spiking), ridge regression, conditional restricted Boltzmann machine (CRBM) and others, including GPU accelerated versions. Oger is released under the GNU LGPL, and is available from http: //organic.elis.ugent.be/oger. Keywords: Python, modular architectures, sequential processing
4 0.34000757 78 jmlr-2012-Nonparametric Guidance of Autoencoder Representations using Label Information
Author: Jasper Snoek, Ryan P. Adams, Hugo Larochelle
Abstract: While unsupervised learning has long been useful for density modeling, exploratory data analysis and visualization, it has become increasingly important for discovering features that will later be used for discriminative tasks. Discriminative algorithms often work best with highly-informative features; remarkably, such features can often be learned without the labels. One particularly effective way to perform such unsupervised learning has been to use autoencoder neural networks, which find latent representations that are constrained but nevertheless informative for reconstruction. However, pure unsupervised learning with autoencoders can find representations that may or may not be useful for the ultimate discriminative task. It is a continuing challenge to guide the training of an autoencoder so that it finds features which will be useful for predicting labels. Similarly, we often have a priori information regarding what statistical variation will be irrelevant to the ultimate discriminative task, and we would like to be able to use this for guidance as well. Although a typical strategy would be to include a parametric discriminative model as part of the autoencoder training, here we propose a nonparametric approach that uses a Gaussian process to guide the representation. By using a nonparametric model, we can ensure that a useful discriminative function exists for a given set of features, without explicitly instantiating it. We demonstrate the superiority of this guidance mechanism on four data sets, including a real-world application to rehabilitation research. We also show how our proposed approach can learn to explicitly ignore statistically significant covariate information that is label-irrelevant, by evaluating on the small NORB image recognition problem in which pose and lighting labels are available. Keywords: autoencoder, gaussian process, gaussian process latent variable model, representation learning, unsupervised learning
5 0.33699077 31 jmlr-2012-DEAP: Evolutionary Algorithms Made Easy
Author: Félix-Antoine Fortin, François-Michel De Rainville, Marc-André Gardner, Marc Parizeau, Christian Gagné
Abstract: DEAP is a novel evolutionary computation framework for rapid prototyping and testing of ideas. Its design departs from most other existing frameworks in that it seeks to make algorithms explicit and data structures transparent, as opposed to the more common black-box frameworks. Freely available with extensive documentation at http://deap.gel.ulaval.ca, DEAP is an open source project under an LGPL license. Keywords: distributed evolutionary algorithms, software tools
6 0.27918494 41 jmlr-2012-Exploration in Relational Domains for Model-based Reinforcement Learning
7 0.27510595 70 jmlr-2012-Multi-Assignment Clustering for Boolean Data
8 0.27178019 15 jmlr-2012-Algebraic Geometric Comparison of Probability Distributions
9 0.26155937 51 jmlr-2012-Integrating a Partial Model into Model Free Reinforcement Learning
10 0.22457588 55 jmlr-2012-Learning Algorithms for the Classification Restricted Boltzmann Machine
11 0.22218798 85 jmlr-2012-Optimal Distributed Online Prediction Using Mini-Batches
12 0.20680769 112 jmlr-2012-Structured Sparsity via Alternating Direction Methods
13 0.18986005 56 jmlr-2012-Learning Linear Cyclic Causal Models with Latent Variables
14 0.1823788 61 jmlr-2012-ML-Flex: A Flexible Toolbox for Performing Classification Analyses In Parallel
15 0.16851532 10 jmlr-2012-A Unified View of Performance Metrics: Translating Threshold Choice into Expected Classification Loss
16 0.1652981 11 jmlr-2012-A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models
17 0.16465552 53 jmlr-2012-Jstacs: A Java Framework for Statistical Analysis and Classification of Biological Sequences
18 0.16283016 42 jmlr-2012-Facilitating Score and Causal Inference Trees for Large Observational Studies
19 0.15330137 21 jmlr-2012-Bayesian Mixed-Effects Inference on Classification Performance in Hierarchical Data Sets
20 0.15051833 114 jmlr-2012-Towards Integrative Causal Analysis of Heterogeneous Data Sets and Studies
topicId topicWeight
[(7, 0.011), (21, 0.05), (26, 0.037), (27, 0.016), (29, 0.044), (35, 0.032), (43, 0.413), (49, 0.022), (56, 0.019), (57, 0.026), (69, 0.04), (75, 0.039), (77, 0.019), (79, 0.011), (81, 0.02), (92, 0.065), (96, 0.066)]
simIndex simValue paperId paperTitle
1 0.81750113 119 jmlr-2012-glm-ie: Generalised Linear Models Inference & Estimation Toolbox
Author: Hannes Nickisch
Abstract: The glm-ie toolbox contains functionality for estimation and inference in generalised linear models over continuous-valued variables. Besides a variety of penalised least squares solvers for estimation, it offers inference based on (convex) variational bounds, on expectation propagation and on factorial mean field. Scalable and efficient inference in fully-connected undirected graphical models or Markov random fields with Gaussian and non-Gaussian potentials is achieved by casting all the computations as matrix vector multiplications. We provide a wide choice of penalty functions for estimation, potential functions for inference and matrix classes with lazy evaluation for convenient modelling. We designed the glm-ie package to be simple, generic and easily expansible. Most of the code is written in Matlab including some MEX files to be fully compatible to both Matlab 7.x and GNU Octave 3.3.x. Large scale probabilistic classification as well as sparse linear modelling can be performed in a common algorithmical framework by the glm-ie toolkit. Keywords: sparse linear models, generalised linear models, Bayesian inference, approximate inference, probabilistic regression and classification, penalised least squares estimation, lazy evaluation matrix class
same-paper 2 0.74556357 57 jmlr-2012-Learning Symbolic Representations of Hybrid Dynamical Systems
Author: Daniel L. Ly, Hod Lipson
Abstract: A hybrid dynamical system is a mathematical model suitable for describing an extensive spectrum of multi-modal, time-series behaviors, ranging from bouncing balls to air traffic controllers. This paper describes multi-modal symbolic regression (MMSR): a learning algorithm to construct non-linear symbolic representations of discrete dynamical systems with continuous mappings from unlabeled, time-series data. MMSR consists of two subalgorithms—clustered symbolic regression, a method to simultaneously identify distinct behaviors while formulating their mathematical expressions, and transition modeling, an algorithm to infer symbolic inequalities that describe binary classification boundaries. These subalgorithms are combined to infer hybrid dynamical systems as a collection of apt, mathematical expressions. MMSR is evaluated on a collection of four synthetic data sets and outperforms other multi-modal machine learning approaches in both accuracy and interpretability, even in the presence of noise. Furthermore, the versatility of MMSR is demonstrated by identifying and inferring classical expressions of transistor modes from recorded measurements. Keywords: hybrid dynamical systems, evolutionary computation, symbolic piecewise functions, symbolic binary classification
3 0.28373912 11 jmlr-2012-A Unifying Probabilistic Perspective for Spectral Dimensionality Reduction: Insights and New Models
Author: Neil D. Lawrence
Abstract: We introduce a new perspective on spectral dimensionality reduction which views these methods as Gaussian Markov random fields (GRFs). Our unifying perspective is based on the maximum entropy principle which is in turn inspired by maximum variance unfolding. The resulting model, which we call maximum entropy unfolding (MEU) is a nonlinear generalization of principal component analysis. We relate the model to Laplacian eigenmaps and isomap. We show that parameter fitting in the locally linear embedding (LLE) is approximate maximum likelihood MEU. We introduce a variant of LLE that performs maximum likelihood exactly: Acyclic LLE (ALLE). We show that MEU and ALLE are competitive with the leading spectral approaches on a robot navigation visualization and a human motion capture data set. Finally the maximum likelihood perspective allows us to introduce a new approach to dimensionality reduction based on L1 regularization of the Gaussian random field via the graphical lasso.
4 0.2821953 85 jmlr-2012-Optimal Distributed Online Prediction Using Mini-Batches
Author: Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, Lin Xiao
Abstract: Online prediction methods are typically presented as serial algorithms running on a single processor. However, in the age of web-scale prediction problems, it is increasingly common to encounter situations where a single processor cannot keep up with the high rate at which inputs arrive. In this work, we present the distributed mini-batch algorithm, a method of converting many serial gradient-based online prediction algorithms into distributed algorithms. We prove a regret bound for this method that is asymptotically optimal for smooth convex loss functions and stochastic inputs. Moreover, our analysis explicitly takes into account communication latencies between nodes in the distributed environment. We show how our method can be used to solve the closely-related distributed stochastic optimization problem, achieving an asymptotically linear speed-up over multiple processors. Finally, we demonstrate the merits of our approach on a web-scale online prediction problem. Keywords: distributed computing, online learning, stochastic optimization, regret bounds, convex optimization
5 0.28135762 64 jmlr-2012-Manifold Identification in Dual Averaging for Regularized Stochastic Online Learning
Author: Sangkyun Lee, Stephen J. Wright
Abstract: Iterative methods that calculate their steps from approximate subgradient directions have proved to be useful for stochastic learning problems over large and streaming data sets. When the objective consists of a loss function plus a nonsmooth regularization term, the solution often lies on a lowdimensional manifold of parameter space along which the regularizer is smooth. (When an ℓ1 regularizer is used to induce sparsity in the solution, for example, this manifold is defined by the set of nonzero components of the parameter vector.) This paper shows that a regularized dual averaging algorithm can identify this manifold, with high probability, before reaching the solution. This observation motivates an algorithmic strategy in which, once an iterate is suspected of lying on an optimal or near-optimal manifold, we switch to a “local phase” that searches in this manifold, thus converging rapidly to a near-optimal point. Computational results are presented to verify the identification property and to illustrate the effectiveness of this approach. Keywords: regularization, dual averaging, partly smooth manifold, manifold identification
6 0.28071821 8 jmlr-2012-A Primal-Dual Convergence Analysis of Boosting
7 0.28015107 42 jmlr-2012-Facilitating Score and Causal Inference Trees for Large Observational Studies
8 0.27962509 117 jmlr-2012-Variable Selection in High-dimensional Varying-coefficient Models with Global Optimality
9 0.27647209 103 jmlr-2012-Sampling Methods for the Nyström Method
10 0.27538005 72 jmlr-2012-Multi-Target Regression with Rule Ensembles
11 0.27489412 70 jmlr-2012-Multi-Assignment Clustering for Boolean Data
12 0.27406994 83 jmlr-2012-Online Learning in the Embedded Manifold of Low-rank Matrices
13 0.27300358 104 jmlr-2012-Security Analysis of Online Centroid Anomaly Detection
14 0.27144581 65 jmlr-2012-MedLDA: Maximum Margin Supervised Topic Models
15 0.27115896 80 jmlr-2012-On Ranking and Generalization Bounds
16 0.27079862 98 jmlr-2012-Regularized Bundle Methods for Convex and Non-Convex Risks
17 0.27041048 73 jmlr-2012-Multi-task Regression using Minimal Penalties
18 0.27012724 92 jmlr-2012-Positive Semidefinite Metric Learning Using Boosting-like Algorithms
19 0.26973474 111 jmlr-2012-Structured Sparsity and Generalization
20 0.26973003 36 jmlr-2012-Efficient Methods for Robust Classification Under Uncertainty in Kernel Matrices