Amsterdam Science Park, February 10, 2025
This workshop will take place as part of the 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). It brings together researchers who are working on topics at the intersection of learning and logic, ranging from the logical foundations of learnability and computational learning theory to logical analyses of machine learning models and applications of machine learning in knowledge representation and reasoning.
Workshop location: CWI, Science Park 123, 1098 XG Amsterdam, Turing Room.
(Reachable by train from Amsterdam Central Station and by bus 40 from Amsterdam Amstel Station or Amsterdam Muiderpoort Station, see also CSL website and the CWI visitor information page)
Schedule:
08:30–09:00 welcome/registration
09:00–09:10 opening
09:10–09:50 invited talk: Johan van Benthem - Learning Step by Step: A Dynamic-Epistemic Approach
09:50–10:30 invited talk: Kristin Yvonne Rozier - Logic for Learning
(30-min break)
11:00–11:40 invited talk: Martin Grohe - Uniform Expressivity of Graph Neural Networks
11:40–12:40 contributed talks:
Christoph Standke - Query languages for neural networks
Arie Soeteman - The Logical Expressiveness of Hierarchical Subgraph GNNs
Olga Medrano Martín del Campo - Bounded VC dimension analogues from a local combinatorial structure lens
Adrien Pommellet - Around SAT-based Learning of Logical Formulas
(60-min lunch break)
13:40–14:20 invited talk: Dana Fisman - Learning Languages of Infinite Words
14:20–15:20 contributed talks:
Noa Izsak - Learning Broadcast Protocols
Levin Hornischer - Learning How to Vote With Principles: Axiomatic Insights Into the Collective Decisions of Neural Networks
Esther Anna Corsi - What Game are we Playing? A Game-Theoretic Approach to Data Bias and Machine Learning Unfairness
Rémi Morvan - Residual Probabilistic Automata
(30-min break)
15:50–16:30 invited talk: Alexandru Baltag - Topo-Logical Foundations of Learning Theory
16:30–17:00 contributed talks:
Martha Lewis - Compositional vector semantics for spiking neural networks
Manuel Vargas Guzmán - Hybrid Models of Natural Reasoning
17:00–17:10 workshop closing
18h00-20h30 Reception (Cafe Restaurant Polder, Science Park 203, Amsterdam)
Invited Speakers:
Univ. of Amsterdam
Topo-Logical Foundations of Learning Theory
Univ. of Amsterdam & Stanford & Tsinghua University
Learning Step by Step: A Dynamic-Epistemic Approach
Ben-Gurion University
Learning Languages of Infinite Words
RWTH Aachen
Uniform Expressivity of Graph Neural Networks
Invited talks:
Johan van Benthem - Learning Step by Step: A Dynamic-Epistemic Approach.
We present basics of a logical approach to stepwise update of knowledge and belief triggered by new information, and point out some major technical features and design challenges. In conclusion, we sketch how this approach fits with longer-term temporal learning and with modeling information at various levels of detail, coarser or finer.
Kristin Yvonne Rozier - Logic for Learning
Learning is especially challenging in cases where the learned behavior must be a safe action, or must achieve a certain level of trustworthiness where we do not have, e.g., sufficient quality or quantity of data to learn at that level. In these cases, we turn to logic to constrain learning, fill in the information gaps, and provide efficient, hallucination-free algorithms to build on. This talk will propose formalizations for safe learning, highlight the state of the art at the intersection of logic for learning, and issue challenge questions. When it comes to safety and trustworthiness, we still have a lot to learn.
Martin Grohe - Uniform Expressivity of Graph Neural Networks
Dana Fisman - Learning Languages of Infinite Words
Alexandru Baltag - Topo-Logical Foundations of Learning Theory
This talk is an introduction to Topological Learning Theory. The topological approach to inductive learning and inductive problem-solving is an abstraction and generalization of Computational Learning Theory, that has close connections to Belief Revision Theory and to Dynamic Epistemic Logic. It may also be of potential relevance to Machine Learning in AI, as well as throwing a new light on a number of topics in Philosophy of Science: falsifiability, coherence, simplicity, Ockham's Razor, and the role of paradigmatic questions and interrogative agendas in theory change.
Contributed talks:
Adrien Pommellet (EPITA Research Laboratory (LRE), EPITA, Paris, France):
Around SAT-based Learning of Logical Formulas
Passive learning is the act of computing a (if possible minimal) formula that separates a known set of desirable executions of a system from another known set of undesirable behaviors. The point of this talk is to 1. briefly present the current SAT-based learning algorithms, 2. explore their limitations and some alternatives, and 3. try to infer a more generic learning framework that leverages state-of-the-art SAT solvers and model-checkers.
Arie Soeteman (ILLC, University of Amsterdam):
The Logical Expressiveness of Hierarchical Subgraph GNNs
Graph neural networks (GNNs), and specifically message-passing neural networks (MPNNs), have become the dominant approach for representation learning on graph-structured data. Since the expressiveness of standard MPNNs is limited by their inability to distinguish pairs of graphs that pass the one-dimensional (Folklore) Weisfeiler-Leman test, a great variety of more expressive architectures has been proposed. One class of such extensions is subgraph GNN, in which message-passing is applied to a collection of subgraphs. Subgraph GNNs show state-of-the-art performance on real-world benchmarks such as the ZINC molecular property prediction. In particular, recently, a variant of subgraph GNNs in which nodes receive neighborhood embeddings based on their diameter-k neighborhood with distinguished center node label, also known as ''ego-networks'', have become prominent as simple yet expressive subgraph GNN architecture.
Simultaneously, recent studies have characterized the expressive power of GNNs with global aggregation and higher-order networks into modal and guarded fragments of first-order logic.
In this work, we provide a logical characterization of subgraph GNNs based on ego-networks, opening up the theoretical analysis of subgraph GNNs to the toolbox of logic. In addition, inspired by this logical characterization, we propose a hierarchy of subgraph GNNs with increasing nesting depth. This hierarchy distinguishes graphs up to isomorphism in the limit, and poses a simpler and more efficient alternative to higher-order GNNs.
This talk is based on ongoing joint work with Balder ten Cate.
Christoph Standke (RWTH Aachen University, Aachen):
Query languages for neural networks
We lay the foundations for a database-inspired approach to interpreting and understanding neural network models by querying them using declarative languages. Towards this end we study different query languages, based on first-order logic, that mainly differ in their access to the neural network model. First-order logic over the reals naturally yields a language which views the network as a black box; only the input-output function defined by the network can be queried. On the other hand, a white-box language can be obtained by viewing the network as a weighted graph, and extending first-order logic with summation over weight terms. In general, the two approaches are incomparable in expressive power, as we will show. Under natural circumstances, however, the white-box approach can subsume the black-box approach. We show this concretely for linear constraint queries over real functions definable by feedforward neural networks with a fixed number of hidden layers and piecewise linear activation functions.
This talk is based on joint work with Martin Grohe, Juno Steegmans and Jan Van den Bussche which will be presented at ICDT'25.
Esther Anna Corsi (University of Milan):
What Game are we Playing? A Game-Theoretic Approach to Data Bias and Machine Learning Unfairness
Predictions made by machine learning models based on biased data can be framed within a game-theoretic setting, specifically using the Ulam game. This setting allows us to model the uncertainty of a given hypothesis concerning some data through a rejection degree function and to define a variation of the rational non-monotonic consequence relation. We show that bias can be defined in terms of this non-monotonic consequence relation and investigate the connections between bias and the system arising from the Ulam game setting.
**Joint work with Chiara Manganini and Giuseppe Primiero**
Levin Hornischer (LMU Munich, MCMP):
Learning How to Vote With Principles: Axiomatic Insights Into the Collective Decisions of Neural Networks
Can neural networks be applied in voting theory, while satisfying the need for transparency in collective decisions? We propose axiomatic deep voting: a framework to build and evaluate neural networks that aggregate preferences, using the well-established axiomatic method of voting theory. Our findings are: (1) Neural networks, despite being highly accurate, often fail to align with the core axioms of voting rules, revealing a disconnect between mimicking outcomes and reasoning. (2) Training with axiom-specific data does not enhance alignment with those axioms. (3) By solely optimizing axiom satisfaction, neural networks can synthesize new voting rules that often surpass and substantially differ from existing ones. This offers insights for both fields: For AI, important concepts like bias and value-alignment are studied in a mathematically rigorous way; for voting theory, new areas of the space of voting rules are explored. This is joint work with Zoi Terzopoulou. The full paper is available at: https://arxiv.org/abs/2410.16170.
Manuel Vargas Guzmán (University of Warsaw):
Hybrid Models of Natural Reasoning
Within the Artificial Intelligence field, the ability to perform reasoning can be modelled using symbolic and connectionist approaches. Both types of models achieve a conclusion in a different fashion, while the former applies formal logic and the transformation of premises using inference rules, the latter uses neural networks. We combine these two techniques within a framework of a formally well-defined subclass of natural language to study abstract models of reasoning. We implement a symbolic prover and train neural models for one of the simplest subclasses of language, the syllogistic fragment. Our hybrid model constructs inferences using the symbolic model assisted by the connectionist one in the following tasks: for a given knowledge base KB (a set of premises) and a hypothesis H, the neural network provides the necessary premises (a subset of KB) to prove H and, if needed, it also predicts a formula to prove H by contradiction. To build a connectionist component, we use synthetic data and fine-tuning approaches on pre-trained Large Language Models. Our experiments show that a successful collaboration between symbolic and connectionist models lead to a significant decrease in the number of computations that a “naive” symbolic prover would need to find inferences.
Co-authors: Jakub Szymanick, Kentaro Yamamoto, Maciej Malicki
Martha Lewis (ILLC, University of Amsterdam):
Compositional vector semantics for spiking neural networks
Categorical compositional distributional semantics is an approach to modelling language that combines the success of vector-based models of meaning with the compositional power of formal semantics. However, this approach was developed without an eye to cognitive plausibility. Vector representations of concepts and concept binding are also of interest in cognitive science, and have been proposed as a way of representing concepts within a biologically plausible spiking neural network.
This work proposes a way for compositional distributional semantics to be implemented within a spiking neural network architecture, with the potential to address problems in concept binding, and give a small implementation. We also describe a means of training word representations using labelled images.
Noa Izsak (Ben-Gurion University):
Learning Broadcast Protocols
The problem of learning a computational model from examples has been receiving growing attention.
For the particularly challenging problem of learning models of distributed systems, existing results are restricted to models with a fixed number of interacting processes.
In this work, we look for the first time at the problem of learning a distributed system with an arbitrary number of processes, assuming only that there exists a cutoff, i.e., a number of processes that is sufficient to produce all observable behaviors.
Specifically, we consider fine broadcast protocols, these are broadcast protocols (BPs) with a finite cutoff and no hidden states.
We provide a learning algorithm that can infer a correct BP from a sample that is consistent with a fine BP, and a minimal equivalent BP if the sample is sufficiently complete.
On the negative side we show that (a) characteristic sets of exponential size are unavoidable, (b) the consistency problem for fine BPs is NP-Hard, and (c) that fine BPs are not polynomially predictable.
Olga Medrano Martín del Campo (The University of Chicago):
Bounded VC dimension analogues from a local combinatorial structure lens
This ongoing project explores connections between extremal combinatorics in bipartite graphs, model theoretic measures including ladder index and branching index, and learning theoretic measures including threshold rank, Littlestone dimension and Vapnik-Chervonenkis dimension. In this largely expository talk, we will outine some of the background for these connections and propose first analogues of \eps-good sets for VC classes. This project is initial work in progress towards the thesis of the author, who will be attending the Logic Mentoring Workshop.
Rémi Morvan (LaBRI, Univ. Bordeaux):
Residual Probabilistic Automata
Probabilistic automata form a well studied model of computation studied under different names in many fields of research with the goal of representing probabilistic distributions or stochastic processes.
From a formal perspective, many negative results show that both minimising and learning probabilistic automata is hard.
In this paper, we develop the theory of probabilistic residual automata, giving a unifying perspective for a range of similar models introduced in machine learning, speed recognition, and automata theory.
Our main results show that probabilistic residual automata can be effectively and efficiently minimised and learned. They are obtained by proving an algebraic characterisation theorem for such automata, extending the seminal result of Fliess for weighted automata.
This is a joint work with Nathanaël Fijalkow, Arthur Gall and Arka Ghosh.
Call for submissions and submission instructions:
The CSL 2025 Workshop on Learning and Logic is an on-site event happening on the 10th of February 2025 in Amsterdam, Netherlands. It will take place as part of the 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). The workshop brings together researchers who are working on topics at the intersection of learning and logic, ranging from the logical foundations of learnability and computational learning theory to logical analyses of machine learning models and applications of machine learning in knowledge representation and reasoning.
The workshop will consist of invited talks and contributed talks. It does not have any proceedings, and therefore previously published or ongoing work are both encouraged to be presented.
Topics for the presentation at the workshop include, but are not limited to, the following:
Logical analysis of machine learning architectures
Techniques for learning logical concepts
Computational learning theory
Logic for formal learning theory
Informational complexity of learning
Graph learning
Applications of ML in knowledge representation and data management
Neuro-symbolic integration
Statistical relational AI
Logical and epistemic aspects of distributed learning
Logical aspects of learning in multi-agent systems
Logical analysis of (iterated) belief dynamics and information change
Logical techniques for explainable AI
Data-driven techniques for temporal logic specification and verification
Submissions consist of a title, a short abstract, and an extended abstract in the form of a PDF file (one page, excluding references).
Important dates:
Submission deadline: January 8, 2025 (Anywhere on Earth)
Notification: January 15, 2025 *
Event: February 10, 2025
* accepted submissions will receive a chance to register for the workshop and/or for CSL by January 19 without paying late registration fee.
Organizers:
Steffen van Bergerem (Humboldt University Berlin)
Balder ten Cate (ILLC, University of Amsterdam)
Aybüke Özgün (ILLC, University of Amsterdam)
Sonja Smets (ILLC, University of Amsterdam)
This workshop acknowledges the financial support by the Research Priority Area Human(e) AI of the University of Amsterdam, and by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement no 101031081.