Recent zbMATH articles in MSC 68Nhttps://zbmath.org/atom/cc/68N2024-07-25T18:28:20.333415ZWerkzeugAlgebraic dynamical systems in machine learninghttps://zbmath.org/1537.180032024-07-25T18:28:20.333415Z"Jones, Iolo"https://zbmath.org/authors/?q=ai:jones.iolo"Swan, Jerry"https://zbmath.org/authors/?q=ai:swan.jerry"Giansiracusa, Jeffrey"https://zbmath.org/authors/?q=ai:giansiracusa.jeffreyThe relationship between the structure of a model and its observable behavior is of central importance to applied mathematics. In both linguistics and computer science, there are corresponding notions of the syntax and semantics of an expression or program. In machine learning, behavior is determined via learned parameters, while the structure of a model is typically considered to be prescribed by hyperparameters, which is often categorified in the context of functional programming, and programs are viewed as morphisms in a category of data types. The syntax is specified by an algebraic data type, on which recursively-defined functions determine the semantics [\textit{G. Malcolm}, Sci. Comput. Program. 14, No. 2--3, 255--279 (1990; Zbl 0712.68014)]. The categorical perspective forms a basis for describing compositionality. Compositional modelling provides vital support for safe and causal inference.
This paper develops this theory to include the increasingly popular class of models based on dynamical systems. The authors describe these models via universal algebra [\textit{S. Burris} and \textit{H. P. Sankappanavar}, A course in universal algebra. New York - Heidelberg Berlin: Springer-Verlag (1981; Zbl 0478.08001)] and category theory, showing that term rewriting systems are the exact algebraic analogue of dynamical systems while explicitly encoding the structure of the model in their expression. The rewrite rule corresponds to this syntax or structure, whereas the semantics are specified by a recursive function on that algebraic structure. It is shown that rewriting models are naturally compositional in the sense that the corresponding dynamical system lifts to any category with the appropriate structure.
The main results go as follows.
Theorem 6.3. The class of dynamical systems embeds in the class of rewriting models, such that every rewriting model projects onto a dynamical system.
Theorem 7.1. If the sets and functions used in a rewriting model are all in a category \(C\), where \(C\)\ has the same coproduct as \(\boldsymbol{Set}\), then the rewriting model is equivalent to one in \(C\).
Reviewer: Hirokazu Nishimura (Tsukuba)A matrix-free exact Newton methodhttps://zbmath.org/1537.490282024-07-25T18:28:20.333415Z"Naumann, Uwe"https://zbmath.org/authors/?q=ai:naumann.uweSummary: A modification of Newton's method for solving systems of \(n>0\) nonlinear equations is presented. The new matrix-free method is exact as opposed to a range of inexact Newton methods in the sense that both the Jacobians and the solutions to the linear Newton systems are computed without truncation. It relies on a given decomposition of a structurally dense invertible Jacobian of the residual into a product of \(q>0\) structurally sparse invertible elemental Jacobians according to the chain rule of differentiation. Inspired by the adjoint mode of algorithmic differentiation, explicit accumulation of the Jacobian of the residual is avoided. Prospective, generally applicable implementations of the new method can be based on similar ideas. Sparsity is exploited for the direct solution of the linear Newton systems. Optimal exploitation of sparsity yields various well-known computationally intractable combinatorial optimization problems in sparse linear algebra such as Bandwidth or Directed Elimination Ordering. The method is motivated in the context of a decomposition into elemental Jacobians with bandwidth \(2\mu+1\) for \(0\leq\mu\ll n\). In the likely scenario of \(q>n\), the computational cost of the standard Newton algorithm is dominated by the cost of accumulating the Jacobian of the residual. It can be estimated as \(\mathcal{O}(q\mu n^2)\), thus exceeding the cost of \(\mathcal{O}(n^3)\) for the direct solution of the linear Newton system. The new method reduces this cost to \(\mathcal{O}(qn\mu^2)\), yielding a potential improvement by a factor of \(\mathcal{O}\left(\frac{n}{\mu}\right)\). Supporting run time measurements are presented for the tridiagonal case showing a reduction of the computational cost by \(\mathcal{O}(n)\). Generalization yields the combinatorial Matrix-Free Exact Newton Step problem. We prove NP-completeness, and we present algorithmic components for building methods for the approximate solution. Potential applications of the matrix-free exact Newton method in machine learning of surrogates for computationally expensive nonlinear residuals are touched on briefly as part of various conclusions to be drawn.Sequential composition of propositional logic programshttps://zbmath.org/1537.680292024-07-25T18:28:20.333415Z"Antić, Christian"https://zbmath.org/authors/?q=ai:antic.christianSummary: This paper introduces and studies the sequential composition and decomposition of propositional logic programs. We show that acyclic programs can be decomposed into single-rule programs and provide a general decomposition result for arbitrary programs. We show that the immediate consequence operator of a program can be represented via composition which allows us to compute its least model without any explicit reference to operators. This bridges the conceptual gap between the syntax and semantics of a propositional logic program in a mathematically satisfactory way.An efficient approach to achieve compositionality using optimized multi-version object based transactional systemshttps://zbmath.org/1537.680302024-07-25T18:28:20.333415Z"Juyal, Chirag"https://zbmath.org/authors/?q=ai:juyal.chirag"Kulkarni, Sandeep"https://zbmath.org/authors/?q=ai:kulkarni.sandeep-s"Kumari, Sweta"https://zbmath.org/authors/?q=ai:kumari.sweta"Peri, Sathya"https://zbmath.org/authors/?q=ai:peri.sathya"Somani, Archit"https://zbmath.org/authors/?q=ai:somani.architSummary: In the modern era of multi-core systems, the main aim is to utilize the cores properly. This utilization can be done by concurrent programming. But developing a flawless and well-organized concurrent program is difficult. Software Transactional Memory Systems (STMs) are a convenient programming interface which assist the programmer to access the shared memory concurrently without worrying about consistency issues.
Many STMs available in the literature execute read/write primitive operations on memory buffers. We represent them as Read-Write STMs or RWSTMs. Whereas, there exists some STMs which work on higher level operations. We refer these STMs as Object Based STMs or OSTMs.
The literature of databases and RWSTMs say that maintaining multiple versions ensures greater concurrency. So, this paper proposes the notion of Optimized Multi-version Object Based STMs or OPT-MVOSTMs which encapsulates the idea of multiple versions in OSTMs to harness the greater concurrency efficiently.Higher-order recursion schemes and their automata modelshttps://zbmath.org/1537.680672024-07-25T18:28:20.333415Z"Carayol, Arnaud"https://zbmath.org/authors/?q=ai:carayol.arnaud"Serre, Olivier"https://zbmath.org/authors/?q=ai:serre.olivierFrom the introduction: The main goal of this chapter is to give a self-contained presentation of the equivalence
between two models: higher-order recursion schemes and collapsible pushdown automata. Roughly speaking, a recursion scheme is a finite typed term rewriting system
and a natural view of recursion schemes is to be considered generators for (possibly infinite) trees. Collapsible pushdown automata (CPDA) are an extension of deterministic
(higher-order) pushdown automata and they naturally induce labelled transition systems
(\textsc{Lts}). An \textsc{Lts} is merely a set of relations labelled by a finite alphabet, together with
a distinguished element called the root. Hence unfolding an \textsc{Lts} and contracting silent
transitions define an infinite tree. Applying this construction to CPDA defines a family
of trees that exactly coincides with the family of trees defined by higher-order recursion
schemes. This introduction tries to provide the necessary background and motivation
for these objects.
For the entire collection see [Zbl 1470.68002].Polymorphic lambda calculus with context-free session typeshttps://zbmath.org/1537.680982024-07-25T18:28:20.333415Z"Almeida, Bernardo"https://zbmath.org/authors/?q=ai:almeida.bernardo-f"Mordido, Andreia"https://zbmath.org/authors/?q=ai:mordido.andreia"Thiemann, Peter"https://zbmath.org/authors/?q=ai:thiemann.peter-j"Vasconcelos, Vasco T."https://zbmath.org/authors/?q=ai:vasconcelos.vasco-thudichumSummary: Session types provide a typing discipline for structured communication on bidirectional channels. Context-free session types overcome the restriction to tail recursive protocols characteristic of conventional session types. This extension enables the serialization and deserialization of tree structures in a fully type-safe manner.
We present the theory underlying the language \textsc{FreeST} 2, which features context-free session types in an extension of System F with linear types and a kinding system to distinguish message types, session types, and channel types. The system presents metatheoretical challenges which we address: contractivity in the presence of polymorphism, a non-trivial equational theory on types, and decidability of type equivalence. We also establish standard results on typing preservation, progress, and a characterization of erroneous processes.From statistical relational to neurosymbolic artificial intelligence: a surveyhttps://zbmath.org/1537.681622024-07-25T18:28:20.333415Z"Marra, Giuseppe"https://zbmath.org/authors/?q=ai:marra.giuseppe"Dumančić, Sebastijan"https://zbmath.org/authors/?q=ai:dumancic.sebastijan"Manhaeve, Robin"https://zbmath.org/authors/?q=ai:manhaeve.robin"De Raedt, Luc"https://zbmath.org/authors/?q=ai:de-raedt.lucSummary: This survey explores the integration of learning and reasoning in two different fields of artificial intelligence: neurosymbolic and statistical relational artificial intelligence. Neurosymbolic artificial intelligence (NeSy) studies the integration of symbolic reasoning and neural networks, while statistical relational artificial intelligence (StarAI) focuses on integrating logic with probabilistic graphical models. This survey identifies seven shared dimensions between these two subfields of AI. These dimensions can be used to characterize different NeSy and StarAI systems. They are concerned with (1) the approach to logical inference, whether model or proof-based; (2) the syntax of the used logical theories; (3) the logical semantics of the systems and their extensions to facilitate learning; (4) the scope of learning, encompassing either parameter or structure learning; (5) the presence of symbolic and subsymbolic representations; (6) the degree to which systems capture the original logic, probabilistic, and neural paradigms; and (7) the classes of learning tasks the systems are applied to. By positioning various NeSy and StarAI systems along these dimensions and pointing out similarities and differences between them, this survey contributes fundamental concepts for understanding the integration of learning and reasoning.