Prakash Panangaden

Mark Rowland

We present a novel perspective on behavioural metrics for Markov decision processes via the use of positive definite kernels. We define a ne… (see more)w metric under this lens that is provably equivalent to the recently introduced MICo distance (Castro et al., 2021). The kernel perspective enables us to provide new theoretical results, including value-function bounds and low-distortion finite-dimensional Euclidean embeddings, which are crucial when using behavioural metrics for reinforcement learning representations. We complement our theory with strong empirical results that demonstrate the effectiveness of these methods in practice.

2022-12-31

Trans. Mach. Learn. Res. (published)

openreview.net

Towards an AAK Theory Approach to Approximate Minimization in the Multi-Letter Case

Clara Lacroce

Guillaume Rabusseau

We study the approximate minimization problem of weighted finite automata (WFAs): given a WFA, we want to compute its optimal approximation … (see more)when restricted to a given size. We reformulate the problem as a rank-minimization task in the spectral norm, and propose a framework to apply Adamyan-Arov-Krein (AAK) theory to the approximation problem. This approach has already been successfully applied to the case of WFAs and language modelling black boxes over one-letter alphabets \citep{AAK-WFA,AAK-RNN}. Extending the result to multi-letter alphabets requires solving the following two steps. First, we need to reformulate the approximation problem in terms of noncommutative Hankel operators and noncommutative functions, in order to apply results from multivariable operator theory. Secondly, to obtain the optimal approximation we need a version of noncommutative AAK theory that is constructive. In this paper, we successfully tackle the first step, while the second challenge remains open.

2022-05-31

ArXiv (preprint)

Augmenting Human Selves Through Artificial Agents – Lessons From the Brain

Georg Northoff

Maia Fraser

John Griffiths

Dimitris A. Pinotsis

Rosalyn Moran

Karl Friston

Much of current artificial intelligence (AI) and the drive toward artificial general intelligence (AGI) focuses on developing machines for f… (see more)unctional tasks that humans accomplish. These may be narrowly specified tasks as in AI, or more general tasks as in AGI – but typically these tasks do not target higher-level human cognitive abilities, such as consciousness or morality; these are left to the realm of so-called “strong AI” or “artificial consciousness.” In this paper, we focus on how a machine can augment humans rather than do what they do, and we extend this beyond AGI-style tasks to augmenting peculiarly personal human capacities, such as wellbeing and morality. We base this proposal on associating such capacities with the “self,” which we define as the “environment-agent nexus”; namely, a fine-tuned interaction of brain with environment in all its relevant variables. We consider richly adaptive architectures that have the potential to implement this interaction by taking lessons from the brain. In particular, we suggest conjoining the free energy principle (FEP) with the dynamic temporo-spatial (TSD) view of neuro-mental processes. Our proposed integration of FEP and TSD – in the implementation of artificial agents – offers a novel, expressive, and explainable way for artificial agents to adapt to different environmental contexts. The targeted applications are broad: from adaptive intelligence augmenting agents (IA’s) that assist psychiatric self-regulation to environmental disaster prediction and personal assistants. This reflects the central role of the mind and moral decision-making in most of what we do as humans.

2021-12-31

Frontiers in Computational Neuroscience (published)

Bisimulation metrics and norms for real-weighted automata

Borja Balle

Pascale Gourdeau

2021-12-31

Information and Computation (published)

Continuous MDP Homomorphisms and Homomorphic Policy Gradient

Sahand Rezaei-Shoshtari

Abstraction has been widely studied as a way to improve the efficiency and generalization of reinforcement learning algorithms. In this pape… (see more)r, we study abstraction in the continuous-control setting. We extend the definition of MDP homomorphisms to encompass continuous actions in continuous state spaces. We derive a policy gradient theorem on the abstract MDP, which allows us to leverage approximate symmetries of the environment for policy optimization. Based on this theorem, we propose an actor-critic algorithm that is able to learn the policy and the MDP homomorphism map simultaneously, using the lax bisimulation metric. We demonstrate the effectiveness of our method on benchmark tasks in the DeepMind Control Suite. Our method's ability to utilize MDP homomorphisms for representation learning leads to improved performance when learning from pixel observations.

2021-12-31

Advances in Neural Information Processing Systems 35 (NeurIPS 2022) (published)

openreview.net

Riemannian Diffusion Models

Avishek Joey Bose

Diffusion models are recent state-of-the-art methods for image generation and likelihood estimation. In this work, we generalize continuous-… (see more)time diffusion models to arbitrary Riemannian manifolds and derive a variational framework for likelihood estimation. Computationally, we propose new methods for computing the Riemannian divergence which is needed in the likelihood estimation. Moreover, in generalizing the Euclidean case, we prove that maximizing this variational lower-bound is equivalent to Riemannian score matching. Empirically, we demonstrate the expressive power of Riemannian diffusion models on a wide spectrum of smooth manifolds, such as spheres, tori, hyperboloids, and orthogonal groups. Our proposed method achieves new state-of-the-art likelihoods on all benchmarks.

2021-12-31

Neural Information Processing Systems (published)

openreview.net

Interpreting Lambda Calculus in Domain-Valued Random Variables

Robert Furber

Radu Mardare

Douglas Scott

2021-12-11

ArXiv (preprint)

Weighted automata are compact and actively learnable

Artem Kaznatcheev

2021-09-30

Information Processing Letters (published)

Proceedings 17th International Conference on Quantum Physics and Logic

Benoît Valiron

Shane Mansfield

Pablo Arrighi

This volume contains the proceedings of the 17th International Conference on Quantum Physics and Logic (QPL 2020), which was held June 2-6, … (see more)2020. Quantum Physics and Logic is an annual conference that brings together researchers working on mathematical foundations of quantum physics, quantum computing, and related areas, with a focus on structural perspectives and the use of logical tools, ordered algebraic and category-theoretic structures, formal languages, semantical methods, and other computer science techniques applied to the study of physical behavior in general. Work that applies structures and methods inspired by quantum theory to other fields (including computer science) is also welcome.

2021-09-05

Electronic Proceedings in Theoretical Computer Science (published)

Extracting Weighted Automata for Approximate Minimization in Language Modelling

Clara Lacroce

Guillaume Rabusseau

In this paper we study the approximate minimization problem for language modelling. We assume we are given some language model as a black bo… (see more)x. The objective is to obtain a weighted finite automaton (WFA) that fits within a given size constraint and which mimics the behaviour of the original model while minimizing some notion of distance between the black box and the extracted WFA. We provide an algorithm for the approximate minimization of black boxes trained for language modelling of sequential data over a one-letter alphabet. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. This allows us to use the spectral norm to measure the distance between the black box and the WFA. We provide theoretical guarantees to study the potentially infinite-rank Hankel matrix of the black box, without accessing the training data, and we prove that our method returns an asymptotically-optimal approximation.

2021-08-24

Proceedings of the Fifteenth International Conference on Grammatical Inference (published)

proceedings.mlr.press

Fixed-Points for Quantitative Equational Logics

Radu Mardare

Gordon Plotkin

We develop a fixed-point extension of quantitative equational logic and give semantics in one-bounded complete quantitative algebras. Unlike… (see more) previous related work about fixed-points in metric spaces, we are working with the notion of approximate equality rather than exact equality. The result is a novel theory of fixed points which can not only provide solutions to the traditional fixed-point equations but we can also define the rate of convergence to the fixed point. We show that such a theory is the quantitative analogue of a Conway theory and also of an iteration theory; and it reflects the metric coinduction principle. We study the Bellman equation for a Markov decision process as an illustrative example.

2021-07-01

2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (published)

Universal Semantics for the Stochastic λ-Calculus

Pedro H. Azevedo de Amorim

Dexter Kozen

Radu Mardare

Michael Roberts

We define sound and adequate denotational and operational semantics for the stochastic lambda calculus. These two semantic approaches build … (see more)on previous work that used an explicit source of randomness to reason about higher-order probabilistic programs.

2021-07-01

2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (published)