Approaches and Applications of Inductive Programming

Anti-unification (AU) is a fundamental operation for the computation of symbolic generalizations useful for inductive inferencing [1]. It is the dual operation to unification, an operation at the foundation of automated theorem proving. In contrast to unification, where one is interested in constructing most general unifiers (mgus), anti-unification is concerned with the construction of least general generalizations (lggs); that is, expressions capturing the commonalities shared between members of a set of symbolic expressions.

The operation was introduced by Plotkin and Reynolds and found many applications within the area of Inductive synthesis and, in particular, early inductive logic programming (ILP) systems. However, since their seminal work, the number of applications has grown tremendously with uses in program analysis, program repair, automated reasoning, and beyond. With the growing number of applications, several investigations have developed anti-unification methods over various symbolic objects, such as the simply-typed lambda calculus, term graphs, and hedge expression, to name a few. In particular, there has been significant progress in understanding equational anti-unification and the cardinality of the set of solutions (set of lggs). In many cases, the solution sets are either infinitely large or do not exist (every generalization allows a more specific generalization).

We ask, is least general generalization the right characterization of a solution to an anti-unification problem? In particular, is there a characterization of a solution more amenable to modern approaches to inductive synthesis? Secondly, what does the inductive synthesis community need from symbolic generalization techniques, which is currently missing?

Knowledge Graphs (KGs) are multi-relational graphs designed to organize and share real-world knowledge where nodes represent entities of interest and edges represent different types of relationships between such entities [1]. Despite the large usage, it is well known that KGs suffer from incompleteness and noise. For tackling these problems, solutions to the link prediction task, that amount at predicting an unknown component of a triple, have been investigated. Mostly, Knowledge Graph Embedding methods (KGE) have been devised since they have been shown to scale even to very large KGs. KGE convert the data graph into an optimal low dimensional space where structural graph information is preserved as much as possible. Embeddings are learned based on the constraint that a valid (positive) triple score has to be lower than the invalid (negative) triple score. As KGs mainly encode positive triples, negative triples are obtained by randomly corrupting true/observed triples [2], thus possibly injecting false negatives during the learning process.

In this talk we present a solution for an informed generation of negative examples that, by exploiting the semantics of the KGs and reasoning capabilities, is able to limit false negatives. A key element is represented by disjointness axioms, that are essential for making explicit the negative knowledge about a domain. Yet, disjointness axioms are often overlooked during the modeling process [3]. For the purpose, a symbolic method for discovering disjointness axioms from the data distribution is illustrated. Moving from the assumption that two or more concepts may be mutually disjoint when the sets of their (known) instances do not overlap, the problem is cast as a conceptual clustering problem, where the goal is both to find the best possible partitioning of the individuals in (a subset of) the KG and also to induce intensional definitions of the corresponding classes expressed in the standard representation languages.

The talk will conclude with the analysis of some open challenges related to the presented solutions.

Neurosymbolic AI (NeSy) is regarded as the third wave in AI. It aims at combining knowledge representation and reasoning with neural networks. Numerous approaches to NeSy are being developed and there exists an ‘alphabet-soup’ of different systems, whose relationships are often unclear. I will discuss the state-of-the art in NeSy and argue that there are many similarities with statistical relational AI (StarAI).

Taking inspiration from StarAI, and exploiting these similarities, I will argue that Neurosymbolic AI = Logic + Probability + Neural Networks. I will also provide a recipe for developing NeSy approaches: start from a logic, add a probabilistic interpretation, and then turn neural networks into “neural predicates”. Probability is interpreted broadly here, and is necessary to provide a quantitative and differentiable component to the logic. At the semantic and the computation level, one can then combine logical circuits (ako proof structures) labeled with probability, and neural networks in computation graphs.

I will illustrate the recipe with NeSy systems such as DeepProbLog, a deep probabilistic extension of Prolog, and DeepStochLog, a neural network extension of stochastic definite clause grammars (or stochastic logic programs).

This talks consists of two parts. In the first part, I provide a brief introduction to Inductive Logic Programming: what is it, why is it interesting, and what interesting has recently happened. In the second part, I will explore what I think we should do next in ILP and program synthesis to further advance the field, all centered around the idea of avoiding search.

A core tension in models of concept learning is that the model must carefully balance the tractability of inference against the expressivity of the hypothesis class. Humans, however, can efficiently learn a broad range of concepts. We introduce a model of inductive learning that seeks to be human-like in that sense. It implements a Bayesian reasoning process where a language model first proposes candidate hypotheses expressed in natural language, which are then re-weighed by a prior and a likelihood. By estimating the prior from human data, we can predict human judgments on learning problems involving numbers and sets, spanning concepts that are generative, discriminative, propositional, and higher-order.

This short talk was a pitch for a new problem, called Programmatic Reinforcement Learning: assuming that the environment is given as a program, the goal is to construct an optimal policy in the form of a program. Some motivations, basic examples, and preliminary experimental results were presented and discussed.

Methods of explainable artificial intelligence (XAI) and of inductive programming (IP) can profit from each other in two ways: (1) Inductive programming results in symbolic models (programs) which are inherently interpretable. These programs can provide expressive, relational explanations for learned black box models, for instance Convolutional Neural Networks for image classification. This perspective (IP for XAI) is addressed in this summary. (2) On the other hand, there might be a need for explainability of IP programs to humans. This perspective (XAI for IP) is addressed in the contribution of U. Schmid in this report.

End-to-end and data-driven approaches to learning, like deep convolutional neural networks in image classification, have become prevalent and the center of attention in many research and application areas. However, some research objectives and real world problems may not be solvable by just processing large amounts of data. In some cases, like medical diagnostics, “big data” simply may not be available [2]. At the same time, deep learning models are not inherently transparent opposed to those generated by interpretable machine learning algorithms, such as Inductive Logic Programming (ILP) [6]. This may be a crucial deficency and a barrier to high stakes applicability of deep learning. At the same time, ILP frameworks provide symbolic representations in the form of predicates in First-Order-Logic, tracing capabilities and the integration of relational background knowledge by design, e.g., from human expertise and domain knowledge [3]. Moreover, their learning process is data-efficient in comparison to deep learning. In addition, being a relational learning approach qualifies ILP for explainability [1], e.g., in complex knowledge domains like medicine [2] and AI evaluation in general [5]. Deep learning may therefore profit from being combined with ILP for explanation, validation and a bi-directional interaction between a human and an AI system [3]. A crucial part of this avenue is the design of interfaces between internal representations of what a deep learning model has learned and the relational background knowledge of IP systems, like ILP, to provide human-understandable surrogate models, explanations and interactions. First attempts to bridge this gap have already been proposed [4]. However, several open questions remain to date: How can we find and extract relevant internal representations from deep learning models and present them in a human-understandable manner? How can we disambiguate representations? Which relations should be included in the IP module and satisfied by the deep learning model? How can we implement a knowledge exchange between IP and deep learning models to support the interplay of learning and reasoning in knowledge discovery and AI evaluation? In my opinion, to build such systems is the way toward approximating the strengths of the human inductive bias and adaptability of AI systems to the real world.

Rule learning algorithms form the basis of classic inductive logic programming algorithms such as FOIL or PROGOL. Studying them in a propositional logic setting allows to focus on the algorithmic aspects. A key limitation of the current state-of-the-art such as the LORD algorithm recently developed in our group [1], is that they are all limited to learning rule sets that directly connect the input features to the target feature. In a logical setting, this corresponds to learning a DNF expression. While every logical function can be expressed as a DNF formula, we argue in this talk that learning deeply structured theories may be beneficial, by drawing an analogy to (deep) neural networks [3], and recapitulating some recent empirical results [2].

I’ll talk about three learning problems in planning: learning lifted action models, learning generalized policies, and learning general problem decomposition or sketches. We have been approaching these problems in a top-down fashion, making a clear distinction between what is to be learned andd how is it to be learned. Indeed, we have been pursuing two types of approaches in parallel: formulations that rely on combinatorial optimization solvers on the one hand, and deep (reinforcement) learning approaches on the other. I’ll also discuss the relation between the two approaches which in the common form are limited by the expressive power of C2 logic; first-order logic with two variables and counting, and challenges to get beyond C2.

Inductive logic programming (ILP) is a form of program synthesis. The goal is to induce a logic program that generalises training examples. Popper is a recent ILP system which frames the ILP problem as a constraint satisfaction problem [1, 2]. Popper continually generates hypotheses and tests them on the training examples. If a hypothesis is not a solution, Popper builds constraints to prune hypotheses which are also provably no solutions. Popper supports learning of recursive programs, predicate invention and learning moderately large programs. We present a recent extension of Popper which supports learning minimal description length programs from noisy data [3]. Our approach leverages recent progress in MaxSAT solvers to efficiently find an optimal program.

Learning programs with numerical values is fundamental to many AI applications, including bio-informatics and drug design. However, current program synthesis approaches struggle to learn programs with numerical values. Program synthesis approaches based on enumeration of candidate numerical symbols cannot handle infinite domains. Recent program synthesis approaches also have difficulties reasoning from multiple examples, which is required for instance to identify numerical thresholds or intervals. To overcome these limitations, we introduce an inductive logic programming approach which combines relational learning with numerical reasoning [1]. Our approach uses satisfiability modulo theories solvers to efficiently identify numerical values. Our approach can identify numerical values in linear arithmetic fragments, such as real difference logic, and from infinite domains, such as real numbers or integers. Our results show our approach can outperform existing program synthesis approaches. However, our approach has limited scalability with respect to the complexity of the numerical reasoning stage.

Human problem solvers are able to adapt their problem solving strategies to new situations. They program they own behavior. In order to do so, they introspect, test, debug, and optimize their problem solving algorithms. These metacognitive activities can be implemented in standard cognitive architectures that can store code in working memory and execute it with an interpreter that is implemented as a set of rules in a production system. Additional rules can then modify the code at runtime. Unfortunately, the programming language in which such mental code is written has remained elusive. Here, I will argue that it is time to revive the old idea that program code is directly given in natural language. Traditionally, research on cognitive architectures has mostly avoided natural language even though language is obviously an important aspect of human cognition. With the advent of large language models it seems more plausible than ever that natural language interpreters might become an essential part of a new generation of cognitive architectures. In particular, the metacognitive activity of modifying your own programs might simply consist of transforming one natural language expression into another – the task that transformers were developed for and have turned out to be quite successful at.

Many rule-learning algorithms require prior discretization before they can effectively process datasets with numerical data. For example, consider a dataset with attributes such as temperature and humidity. Discretization (also called quantization) means binning their values into intervals. A simple equidistant algorithm would produce intervals such as (0;10], (10;20], and (20; 30]. If we consider rule learning algorithms based on association rule learning, such as Classification based on Associations [3], discretization is necessary to ensure fast pruning of the state space and also learning of sufficiently generalized rules. Only after the discretization is it possible to learn the rules of the type IF temperature=(20;30] and humidity=(50;60] THEN worker_comfort= good.

While some rule learning algorithms can directly work with numerical attributes, such as the recently proposed extension of the POPPER ILP system [4], for those based on association rule learning, integrating quantization may not be efficient as it could excessively slow down the candidate generation phase. A common approach is thus to apply prediscretization, e.g., following the Minimum Description Length Principle (MDLP)-based method proposed by [2]. However, as the determination of interval lengths is done globally (i.e., same intervals for all instances) and outside of the learning algorithm (e.g. CBA), information is lost, resulting in efficiencies in the final classifier.

Following this problem, this talk introduced the Quantitative CBA (QCBA) algorithm for the subsequent processing of rule models learned on arbitrarily pre-discretized data (e.g., with equidistant binning, MDLP or other method). Extensive experiments have shown that the proposed algorithm consistently reduces the models’ size and thus makes them more understandable. Additionally, in many cases, the predictive performance is also improved. The algorithm can be used to process the results of many rule learning algorithms, including CBA, Interpretable Decision Sets [1] and Scalable Bayesian Rule Lists [5]. The results are available in the R package qCBA available in CRAN. The method is described in detail in [6].

Many commonly used machine learning algorithms are limited to tabular data sets, but real-world data is often stored in relational databases and increasingly in knowledge graphs. Processing of such data with standard „tabular“ machine learning usually requires extensive data transformation and aggregations, resulting in a loss of information. As an alternative, relational Horn rules can be used to model complex relational structures naturally and use these in a range of machine learning tasks, including exploratory analysis, classification, and imputation of missing information.

The RDFRules system for learning rules from knowledge graphs is based on the high-performance AMIE+ algorithm [1] and includes a number of improvements based on more than 10 years of experience with the development of its sister tabular EasyMiner [2] rule learning system. While the AMIE+ algorithm was initially designed for a narrower exploratory task of discovery of rules with the potential to perform knowledge graph (KG) completion, the current version of the RDFRules system goes significantly beyond the original capabilities of the AMIE+ algorithm [1] as it now makes possible to perform the following tasks:

• $\mathrm{■}$

  load not only graph data in RDF but also relational databases described as SQL scripts,

• $\mathrm{■}$

  specify fine-grained patterns to limit the search space,

• $\mathrm{■}$

  preprocess numerical literals,

• $\mathrm{■}$

  cluster discovered rules,

• $\mathrm{■}$

  perform classification tasks,

• $\mathrm{■}$

  evaluate results using standard metrics adapted to graph data and open world assumption,

• $\mathrm{■}$

  support the KG completion task,

The new features make it possible to graph-based rule learning directly on complex real-world data.

The system is described in [3] and available at https://github.com/propi/rdfrules.

I describe the child as hacker hypothesis, which relates program induction with aspects of human cognition, particularly learning [1]. By the deep relationship proposed to exist between knowledge and program-like structures, the child as hacker treats the activities and values of human programmers as hypotheses for the activities and values of many forms of human learning. After introducing this idea, I then look briefly at a project where we’ve begun to implement it in a system called HL (Hacker-Like) [2]. HL explains human behaviour better than some recent alternative program induction systems by representing a concept not only in terms of its object-level content but also in terms of the inferences required to produce that content. By searching over both kinds of representations, HL learns orders of magnitude faster than competing systems. I close by discussing three major areas ripe for future research: i) developing a better empirical understanding of how people solve hard search problems; ii) understanding the neural and psychological basis for human computational abilities; and iii) better understanding the goals and values of human programmers. All three areas have the potential to significantly improve both our understanding of human intelligence and our ability to use program induction systems to solve complex problems.

In this talk, I present our notion of abstraction for answer set programming, a prominent rule-based language for knowledge representation and reasoning with roots in logic programming and non-monotonic reasoning. With the aim to abstract over the irrelevant details of answer set programs, we focus on two approaches of abstraction: (1) abstraction by omission [2], and (2) domain abstraction [1], and introduce a method to construct an abstract program with a smaller vocabulary, by ensuring that the original program is over-approximated. We provide an abstraction & refinement methodology that makes it possible to start with an initial abstraction and upon encountering spurious solutions automatically refining the abstraction until an abstract program with a non-spurious solution is reached. Experiments based on the prototypical implementations reveal the potential of the approach for problem analysis by focusing on the parts of the program that cause the unsatisfiability, some even matching a human-like focus shown by a user study, and by achieving generalization of the answer sets that reflect relevant details only. This makes abstraction an interesting topic of research whose further use in human-understandability of logic programs remains to be explored.

Methods of explainable artificial intelligence (XAI) and of inductive programming (IP) can profit from each other in two ways: (1) Inductive programming results in symbolic models (programs) which are inherently interpretable. Nevertheless, there might be a need for explainability to humans – end-users or domain experts from other areas than computer science. This perspective (XAI for IP) is addressed in this summary. (2) On the other hand, expressive, relational explanations for learned black box models, for instance Convolutional Neural Networks for image classification, can be provided by IP. This perspective (IP for XAI) is addressed in the contribution of B. Finzel in this report.

The power of IP approaches lies in their ability to learn highly expressive models from small sets of examples [2]. Learned programs can support humans to get insights into complex relational or recursive patterns underlying a set of observed data. That is, IP might be an ultra-strong learning approach as defined by Donald Michie (see [3]) under the condition that the learning system can teach the learned model to a human, whose performance is consequently increased to a level beyond that of the human studying the training data alone. For programs which consist of several rules or for programs involving complex relations or recursion, different approaches to construct explanations might support human understanding. One possibility to reduce complexity is to introduce new predicates. For instance, the introduction of a predicate parent/2 as generalization for father/2 and mother/2, reduces four rules for the grandparent/2 relation to one (see [3]). Another possibility is, to translate the rule which covers the current instant to a verbal explanation for humans without background in computer science. This can be realized by simple template-based methods [5]. Alternatively, Large Language Models could be used. For effective teaching a concept to humans, near miss explanations have been proposed by [4]. Winston showed in his early work on learning rules for relational perceptual concepts such as arcs, that providing near misses rather than arbitrary negative examples results in faster convergence of the learned model. In cognitive science it has been shown that teaching concepts by their difference to similar concepts is much more efficient than contrasting them with more distant concepts (for a discussion of these aspects and references, see [4]). In [4] an algorithm for constructing near miss explanations is presented an applied to different domains. Furthermore, an empirical study is presented where it could bew shown that in pairwise comparisons, participants preferred near miss explanations over other types of explanations as more helpful.

Augmenting IP models with explanations can also be helpful to support medical decision making [1]. Here, it might be helpful to go beyond ultrastrong machine learning and bring the human expert in the loop for incremental model correction and adaption. In contrast to standard interactive machine learning, human feedback might go beyond label correction and allow human domain experts to also correct explanations which might be right for the wrong reasons. Correcting explanations can be seen as a special case of knowledge injection in human-in-the-loop IP which exploits such corrections for efficient model adaption.

We consider the problem of explaining learned (relational) ensemble models. Ensemble models (bagging and gradient-boosting) of relational decision trees have proved to be one of the most effective learning methods in the area of probabilistic logic models (PLMs). While effective, they lose one of the most important aspect of PLMs – interpretability.

Our key hypothesis in this work is that combining large number of logical decision trees would yield in a more compressed model compared to that of combining standard decision trees. This is due to the fact that unification of variables in logic would allow for effective and efficient compression.

To this effect, we propose CoTE – Compression of Tree Ensembles – that produces a single small decision list as a compressed representation. CoTE first converts the trees to decision lists and then performs the combination and compression with the aid of the original training set. Experiments on standard benchmarks demonstrate the value of this approach and justifies the hypotheses that compression is more effective in logical decision trees.

Both inductive programming (IP) and large language models (LLMs) are able to complete a task from a few examples. Instead of pitting them against each other, together they can achieve a lot more. One example of such integration is FlashGPT, which iteratively uses witness functions to break an inductive programming problem into smaller subproblems until all are solved (FlashFill) and leverages an LLM to solve the subproblems that cannot be solved symbolically (GPT-3). Instead of reiterating what has been discovered, this talk focused on (a non-exhaustive list of) next steps for combining IP and LLMs.

First, we discuss how the LLM can be used to improve learning in a fully symbolic IP system. Two approaches are (1) using the LLM to generate additional input-output examples for the IP system, or (2) using the LLM to generate candidate solutions to serve as seeds for initiating a search. The latter is a combination of component-based synthesis [1] and sketching, both of which rely on generating useful substructures over the grammar of the target language.

Second, we show how the LLM can be used to improve the experience of working with an IP system, by providing natural language descriptions of the learned programs.

Third, we show how the scope of IP can be improved with LLMS in systems that do not leverage witness functions. One potential method is masking semantic components, performing IP as usual and learning a program that emits masks, and then resolving the masks using an LLM.

Fourth, we show how operators that only use the embeddings from LLMs strike a balance between the inference speed of symbolic operations and the number of examples and capabilities of semantic operations. When the domain of a semantic relation is finite, or when the task is extraction of relevant parts of the input, we can use embeddings of tokens from the input to capture semantic relations between input and output.

We show two novel applications of inductive programming that bring some unique challenges with respect to parsing user input. Both problems share some challenges: the need for speed, noisy input and labels, inferring constant values that adhere to a semantic bias, underspecification of the problem, and suppression of programs with low confidence.

First, we consider the problem of predicting the folder to which an email should be moved. Popular email clients offer to automate this functionality by setting rules, and the expected output of our learner is thus such a rule. An additional challenge with this problem is concept drift. Our approach [1] learns simple propositional rules in conjunctive normal form by generalizing (if an email is mistakenly not covered) or specializing (if an email is mistakenly covered) the rule corresponding to a folder. Because we guarantee that all historical emails are correctly classified, we easily adapt to concept drift. This classic inductive programming approach performs better than many neural and hybrid baselines.

Second, we consider the problem of learning conditional formatting rules in spreadsheets. An additional challenge is the scope of functions that can be used. Our approach [2, 3] uses semi-supervised clustering of input values to tackle underspecification, then learns different rules as decision trees, and ranks them with a learned ranker. Our corpus of 102K rules from real spreadsheets allows this ranker to encode the semantic bias, which allows us to outperform many neural and symbolic approaches, even if they have access to the same set of base predicates.

Probabilistic Inductive Logic Programming refers to learning probabilistic relational programs from “examples”. These could be probabilistic logic programs, but many considerations also apply to learning other statistical relational models. From the perspective of statistical relational artificial intelligence, this is usually referred to as structure learning. Probabilistic Inductive Logic Programming is key in several areas of artificial intelligence, including knowledge discovery in stochastic, relational domains and causal structure discovery in a Boolean relational setting. Probabilistic inductive logic programming is traditionally considered difficult, since it adds another dimension to the classical ILP problem. Current approaches are still based on traditional ILP approaches developed in the 1990s, while the field of ILP has since made huge progress: Metainterpretive learning provides a new conceptual framework for rethinking Inductive Logic Programming, Constraints and learning from failures can help prune the search space, and Powerful ASP encodings can be leveraged to achieve more consistent outcomes.

This raises the question: Can we leverage these modern techniques for PILP?

A crucial part of inductive programming (IP) is search. Since search is costly, an important question is how we can avoid to search so much or too much.

What we search for can be very different things: logic or functional programs, but also decision lists, policies, classifications, language representations or deep learned models. How search is performed can be also realized with many different approaches: enumeration, anti-unification, genetic programming, greedy strategies, combinatorial optimization, stochastic gradient descent, deep reinforcement learning, or Monte Carlo Tree Search. In general, we do need to learn structure as well as probabilities.

To evaluate the quality of the learned program, different aspects might be focused on alone or in combination which is a challenge for search. Obvious criteria are sample complexity and scalability. But one might also be interested in novelty of the learned program, how similar is the inductive strategy to human learning (humans do not enumerate first and than select but typically generalise over few examples).

To push research on becoming more search efficient, a set of benchmark problems and a competition should be introduced. Promising challenge data sets might come from the FlashFill domain (learning more complex Excel functions and string transformations), the abstract reasoning challenge (ARC) and the modified ILP version might be interesting, furthermore, we could look at problems from the International Math Olympiad Challenge.

We should critically evaluate for which problems deep learning/generative approaches are more successful and hopefully identify a class of problems where symbolic IP is superior. For instance, the IP system FlashFill performs better than the transformer-based SmartFill. The core difference between neural network approaches and symbolic IP is that IP returns explicit programs which give the intensional characterisation of the input/output-examples while neural networks are extensional representations. Therefore, one might postulate that neural networks cannot learn recursion.

Currently, string transformation problems are often either syntactic (return the first letter of a string) – which works very well for symbolic IP – or semantic (give the capital for a country) – where generative AI is very good at. Maybe we should look for transformation problems which combine syntactic and semantic transformations (return the first letter for every string which names a capital). As it is so often the case, it might be a good idea to combine symbolic IP and deep learning/generative approaches. A paper we should look at is [1].

Inductive programming results in symbolic models (programs) which are inherently interpretable. Nevertheless, there might be a need for explainability to humans – end-users or domain experts from other areas than computer science. In the discussion group we focused on the question of how to measure the quality of interpretable representations (programs) and of post-hoc generated explanations. The main challenge is to provide for assessment metrics which are not dependent on studies with humans but which can be evaluated directly for the interpretation/explanations. A core difficulty is that the quality of an explanation is context-dependent: it depends on what is explained to whom in what way (how) and for what reason (why). The way to explain something can be a set of symbolic rules (learned with IP or a rule learning system or extracted from a neural net), highlighting important features (which is done by many XAI approaches such as LIME, SHAP or LRP), a natural language explanation, prototypical or near miss examples. Furthermore, explanations can be more abstract or give more details. Explanations can either be constructed to explain for what reason a learned (black box) model gave a specific output (mechanistic explanation) or to explain the learned content to a human (functional explanation, ultra-strong machine learning).

As candidates for assessment metrics we discussed (1) complexity measures (proposals for cognitive complexity measures, structural information theory, Kolmogorov complexity), (2) semantic coherence, (3) reliability of a component (of a program) which can result in abstracting this part away if a human has sufficient/justified trust. A further aspect for evaluation might be a suitable trade-off between the size of the explanation (memory) and the effort to interpret it (run time) as proposed, for instance by Donald Michie [1] or Lun Ai [2].

A program itself can be a good explanation, depending of its complexity. Abstraction might be a useful method to make explanations more comprehensible. Here approaches like predicate/function invention, anti-unification, introducing higher-orderness (such as map/fold), or compression might be helpful. A hierarchy of abstractions can be helpful for providing the ‘right’ level of detail for a given explanatory context. There are first approaches of explanations as a dialogue where more detailed or different forms of explanations can be presented to a human [3]. Learned (Prolog) programs are also suitable in this context: The highest level of abstraction refers to a single (left-hand/target/head) predicate, the next level of detail can be achieved by presenting the instantiated right-hand side of a rule (or a verbal description of it), continued by expanding predicates in the body until ground facts are reached.

Recently, an explainable version FlashFill has been developed. It showed that users sometimes reject a FlashFill rule which correctly covers the examples because they do not understand it. Here approximate symbolic regression has been applied to provide simpler explanations [4]. In the group of Josh Tenenbaum, the system LILO [5] has been developed which provides explanations by abstraction.

A final idea on assessing the quality of an interpretation/explanation has been to input explanations of a learned programs to a LLM, let the LLM generate a program from that and than compare the originally synthesized program with the one generated by the LLM (a kind of loss function). Comparison can be done by behavioral comparison for test cases or by comparing the code.

To advance progress as well as visibility of IP, a collection of suitable benchmarks, convincing use cases, and joint formats to represent problems, as well as starting an IP challange have been identified as helpful. In the discussion group, we focussed on benchmark sets.

First we collected problems currently used in different groups: List problems, regular expressions (RegEx), boolean language inference, competitive programming, Math Olympiad Challenge, Reasoning/Theorem Proving, Planning, Knowledge Graphs, Zendo, Games, Navigation, Biology, standard ML benchmarks (UCML Repository), natural language to programs (NL2P), abstract reasoning challenge (ARC).

Than we discussed what characteristics benchmark problems should have: tunable, clear performance metrics, standard format, correct annotations, noise, social recognition/PR, breadth, not solvable by LLMs (alone), conceptual jumps, linkable to external resources, curriculum, dramatic finish line, doable by humans. Several of these characteristic were discarded. For instance, clear metrics (beyond just right or wrong) did not seem to be a good fit (but see discussion results about explainability). Format has also been seen as not relevant compared to having good environments to execute and evaluate learned programs and tools/environments which are easily usable.

For a selected set of characteristics, we identified that problems from the list above which fulfill the respective characteristic:

• $\mathrm{■}$

  Tunable: List problems, RegEx, Boolean languages, Knowledge Graphs, Games, Navigation, (competitive programming)

• $\mathrm{■}$

  Breadth: List problems, competitive programming, Games, NLP2P, Math Olymp, ARC

• $\mathrm{■}$

  Not solvable by LLM: List problems, Knowledge Graphs, Math Olymp, ARC

• $\mathrm{■}$

  Dramatic finish: Math Olymp, Biology, NLP2P, ARC

• $\mathrm{■}$

  Curriculum: List problems, RegEx, Math Olymp, Navigation

• $\mathrm{■}$

  Doable by (average) humans: List Problems, RegEx, Games, Navigation, ARC

Given the number of criteria which are met, the following problem domains have been identified as the most promising ones: List problems (including string transformations and other domain-specific language based approaches), RegEx, Math Olymp, ARC.

We than had a further critical look at the selected problem classes and evaluated the following aspects: Not suitable for application, lack of format, producable, lack of probabilistic benchmarks, tension between standard and generation, domain specific problems, not perceived as difficult/relevant, need/miss to have a relational core, loss of propositional benchmarks, lack of diversity of evolution, novelty (invent a new sorting algorithm, automated computer scientist), plugable.

After discussing these additional aspects, we came up with the following set of potentially interesting benchmark problems:

• $\mathrm{■}$

  The Automated Computer Scientist (from Andrew Cropper): learning novel (e.g. sorting) algorithms or novel data structures [1]

• $\mathrm{■}$

  Joint IP and KG (Knowledge Graph) problems, especially for combining syntactic and semantic transformations (e.g. give the capital for a country and than take the first letter of it), this can be list problems or Excel tables [5]

• $\mathrm{■}$

  Strategy learning (explicit compared to implicit policy learning in reinforcement learning): for human problem solving, planning (look at problems from the planning competition) [2, 3, 4]

• $\mathrm{■}$

  Online encyclopedia of integer sequences OEIS (not for all of them exists a closed formula)

• $\mathrm{■}$

  Expert domains: learning strategies/patterns for SAT-solvers, theorem provers

• $\mathrm{■}$

  Constructing ML pipelines (AutoML)

Links to benchmark data sets:

• $\mathrm{■}$

  Popper’s (includes Zendo, many others)
  https://github.com/logic-and-learning-lab/Popper/tree/main/examples

• $\mathrm{■}$

  SyGuS (includes list problems, FlashFill, phone numbers)
  https://github.com/SyGuS-Org/benchmarks

• $\mathrm{■}$

  IP Repository (programming benchmarks, including problem solving like Tower of Hanoi)
  https://www.inductive-programming.org/repository.html

• $\mathrm{■}$

  Regular expressions
  https://codalab.lisn.upsaclay.fr/competitions/15096

• $\mathrm{■}$

  Boolean language inference
  https://www.iwls.org/contest/

• $\mathrm{■}$

  Competitive programming
  https://github.com/openai/human-eval

• $\mathrm{■}$

  Math Olympiad Challenge
  https://github.com/lupantech/dl4math#-mathematical-reasoning-benchmarks
  https://github.com/openai/miniF2F/tree/v1

• $\mathrm{■}$

  Planning
  https://github.com/AI-Planning/pddl-generators

• $\mathrm{■}$

  Program synthesis benchmarks from genetic programming community
  https://cs.hamilton.edu/˜thelmuth/PSB2/PSB2.html
  https://zenodo.org/records/5084812

• $\mathrm{■}$

  Standard ML benchmarks: UC Irvine ML Repository
  https://archive.ics.uci.edu/

• $\mathrm{■}$

  Abstract Reasoning Challenge (ARC) [7, 8]
  https://github.com/fchollet/ARC
  https://lab42.global/arc/

• $\mathrm{■}$

  E-Mail Folder Classification
  http://www-2.cs.cmu.edu/˜enron/
  https://catalog.ldc.upenn.edu/LDC2015T03

• $\mathrm{■}$

  Rule learning
  https://github.com/kliegr/arcbench