Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator

• URL: http://arxiv.org/abs/2111.04147v1
• Date: Sun, 7 Nov 2021 18:51:02 GMT
• Title: Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator
• Authors: Homer Walke, Daniel Ritter, Carl Trimbach, Michael Littman
• Abstract summary: We address the problem of learning a compact $mathsfLTL_f$ formula from labeled traces of system behavior. Our approach includes a specialized recurrent filter, designed to subsume $mathsfLTL_f$ temporal operators. Experiments on randomly generated $mathsfLTL_f$ formulas show Neural$mathsfLTL_f$ scales to larger formula sizes than existing approaches.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finite linear temporal logic ($\mathsf{LTL}_f$) is a powerful formal representation for modeling temporal sequences. We address the problem of learning a compact $\mathsf{LTL}_f$ formula from labeled traces of system behavior. We propose a novel neural network operator and evaluate the resulting architecture, Neural$\mathsf{LTL}_f$. Our approach includes a specialized recurrent filter, designed to subsume $\mathsf{LTL}_f$ temporal operators, to learn a highly accurate classifier for traces. Then, it discretizes the activations and extracts the truth table represented by the learned weights. This truth table is converted to symbolic form and returned as the learned formula. Experiments on randomly generated $\mathsf{LTL}_f$ formulas show Neural$\mathsf{LTL}_f$ scales to larger formula sizes than existing approaches and maintains high accuracy even in the presence of noise.

Related papers

• Spectra of Cardinality Queries over Description Logic Knowledge Bases [1.9336815376402723]
  We identify a class of counting queries whose spectra can be effectively represented. We refine constructions used for finite model reasoning and rely on a cycle-reversion technique for the Horn fragment.
  arXiv  Detail & Related papers  (2024-12-17T14:07:04Z)
• Learning sum of diverse features: computational hardness and efficient gradient-based training for ridge combinations [40.77319247558742]
  We study the computational complexity of learning a target function $f_*:mathbbRdtomathbbR$ with additive structure. We prove that a large subset of $f_*$ can be efficiently learned by gradient training of a two-layer neural network.
  arXiv  Detail & Related papers  (2024-06-17T17:59:17Z)
• Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
  We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• LU-Net: Invertible Neural Networks Based on Matrix Factorization [1.2891210250935146]
  LU-Net is a simple and fast architecture for invertible neural networks (INN) Intrepid neural networks can be trained according to the maximum likelihood principle. In our numerical experiments, we test the LU-net architecture as generative model on several academic datasets.
  arXiv  Detail & Related papers  (2023-02-21T08:52:36Z)
• Constrained Training of Neural Networks via Theorem Proving [0.2578242050187029]
  We formalise a deep embedding of linear temporal logic over finite traces (LTL$_f$) We then formalise a loss function $mathcalL$ that we formally prove to be sound, and differentiable to a function $dmathcalL$. We show that, when used for training in an existing deep learning framework for dynamic movement, our approach produces expected results for common movement specification patterns.
  arXiv  Detail & Related papers  (2022-07-08T13:13:51Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  We consider the problem of quantizing a linear model learned from measurements. We derive an information-theoretic lower bound for the minimax risk under this setting. We show that our method and upper-bounds can be extended for two-layer ReLU neural networks.
  arXiv  Detail & Related papers  (2022-02-23T02:39:04Z)
• Efficient Algorithms for Learning Depth-2 Neural Networks with General ReLU Activations [27.244958998196623]
  We present time and sample efficient algorithms for learning an unknown depth-2 feedforward neural network with general ReLU activations. In particular, we consider learning an unknown network of the form $f(x) = amathsfTsigma(WmathsfTx+b)$, where $x$ is drawn from the Gaussian distribution, and $sigma(t) := max(t,0)$ is the ReLU activation.
  arXiv  Detail & Related papers  (2021-07-21T17:06:03Z)
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation [122.70803181751135]
  We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm. Our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. We complement the theory with an empirical evaluation across known difficult exploration tasks.
  arXiv  Detail & Related papers  (2021-06-15T02:23:07Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• Learning nonlinear dynamical systems from a single trajectory [102.60042167341956]
  We introduce algorithms for learning nonlinear dynamical systems of the form $x_t+1=sigma(Thetastarx_t)+varepsilon_t$. We give an algorithm that recovers the weight matrix $Thetastar$ from a single trajectory with optimal sample complexity and linear running time.
  arXiv  Detail & Related papers  (2020-04-30T10:42:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.