Logic & Formal Reasoning
TaBooN -- Boolean Network Synthesis Based on Tabu Search
Aghamiri, Sara Sadat, Delaplace, Franck
Recent developments in Omics-technologies revolutionized the investigation of biology by producing molecular data in multiple dimensions and scale. This breakthrough in biology raises the crucial issue of their interpretation based on modelling. In this undertaking, network provides a suitable framework for modelling the interactions between molecules. Basically a Biological network is composed of nodes referring to the components such as genes or proteins, and the edges/arcs formalizing interactions between them. The evolution of the interactions is then modelled by the definition of a dynamical system. Among the different categories of network, the Boolean network offers a reliable qualitative framework for the modelling. Automatically synthesizing a Boolean network from experimental data therefore remains a necessary but challenging issue. In this study, we present taboon, an original work-flow for synthesizing Boolean Networks from biological data. The methodology uses the data in the form of Boolean profiles for inferring all the potential local formula inference. They combine to form the model space from which the most truthful model with regards to biological knowledge and experiments must be found. In the taboon work-flow the selection of the fittest model is achieved by a Tabu-search algorithm. taboon is an automated method for Boolean Network inference from experimental data that can also assist to evaluate and optimize the dynamic behaviour of the biological networks providing a reliable platform for further modelling and predictions.
Induction and Exploitation of Subgoal Automata for Reinforcement Learning
Furelos-Blanco, Daniel, Law, Mark, Jonsson, Anders, Broda, Krysia, Russo, Alessandra
In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task's subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several grid-world and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning process performance in terms of the traces, the symmetric breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand.
Generative Language Modeling for Automated Theorem Proving
Polu, Stanislas, Sutskever, Ilya
We explore the application of transformer-based language models to automated theorem proving. This work is motivated by the possibility that a major limitation of automated theorem provers compared to humans -- the generation of original mathematical terms -- might be addressable via generation from language models. We present an automated prover and proof assistant, GPT-f, for the Metamath formalization language, and analyze its performance. GPT-f found new short proofs that were accepted into the main Metamath library, which is to our knowledge, the first time a deep-learning based system has contributed proofs that were adopted by a formal mathematics community.
A framework for a modular multi-concept lexicographic closure semantics
Giordano, Laura, Duprรฉ, Daniele Theseider
We define a modular multi-concept extension of the lexicographic closure semantics for defeasible description logics with typicality. The idea is that of distributing the defeasible properties of concepts into different modules, according to their subject, and of defining a notion of preference for each module based on the lexicographic closure semantics. The preferential semantics of the knowledge base can then be defined as a combination of the preferences of the single modules. The range of possibilities, from fine grained to coarse grained modules, provides a spectrum of alternative semantics.
MAP Inference for Probabilistic Logic Programming
Bellodi, Elena, Alberti, Marco, Riguzzi, Fabrizio, Zese, Riccardo
In Probabilistic Logic Programming (PLP) the most commonly studied inference task is to compute the marginal probability of a query given a program. In this paper, we consider two other important tasks in the PLP setting: the Maximum-A-Posteriori (MAP) inference task, which determines the most likely values for a subset of the random variables given evidence on other variables, and the Most Probable Explanation (MPE) task, the instance of MAP where the query variables are the complement of the evidence variables. We present a novel algorithm, included in the PITA reasoner, which tackles these tasks by representing each problem as a Binary Decision Diagram and applying a dynamic programming procedure on it. We compare our algorithm with the version of ProbLog that admits annotated disjunctions and can perform MAP and MPE inference. Experiments on several synthetic datasets show that PITA outperforms ProbLog in many cases. This paper is under consideration for acceptance in Theory and Practice of Logic Programming.
Landscape of Machine Implemented Ethics
Abstract: This paper surveys the state-of-the-art in machine ethics, that is, considerations of how to implement ethical behaviour in robots, unmanned autonomous vehicles, or software systems. The emphasis is on covering the breadth of ethical theories being considered by implementors, as well as the implementation techniques being used. There is no consensus on which ethical theory is best suited for any particular domain, nor is there any agreement on which technique is best placed to implement a particular theory. Another unresolved problem in these implementations of ethical theories is how to objectively validate the implementations. The paper discusses the dilemmas being used as validating'whetstones' and whether any alternative validation mechanism exists. Finally, it speculates that an intermediate step of creating domain-specific ethics might be a possible stepping stone towards creating machines that exhibit ethical behaviour. Computers are increasingly a part of the socio-technical systems around us. Domains such as smartgrids, cloud computing, healthcare, and transport are but some examples where computers are deeply embedded. The speed and complexity of decision-making in these domains have meant that humans are ceding more and more autonomy to these computers (Nallur & Clarke 2018). Autonomy, in machines, can be defined as the effective decision-making power over goals, that influences some action in the real-world. For instance, smart traffic lights can autonomically change their timings, depending on the flow and density of traffic on the roads.
Machine Reasoning Explainability
Cyras, Kristijonas, Badrinath, Ramamurthy, Mohalik, Swarup Kumar, Mujumdar, Anusha, Nikou, Alexandros, Previti, Alessandro, Sundararajan, Vaishnavi, Feljan, Aneta Vulgarakis
As a field of AI, Machine Reasoning (MR) uses largely symbolic means to formalize and emulate abstract reasoning. Studies in early MR have notably started inquiries into Explainable AI (XAI) -- arguably one of the biggest concerns today for the AI community. Work on explainable MR as well as on MR approaches to explainability in other areas of AI has continued ever since. It is especially potent in modern MR branches, such as argumentation, constraint and logic programming, planning. We hereby aim to provide a selective overview of MR explainability techniques and studies in hopes that insights from this long track of research will complement well the current XAI landscape. This document reports our work in-progress on MR explainability.
How Close Are Computers to Automating Mathematical Reasoning?
"They're this crazy contact between an imaginary, nonphysical world and biologically evolved creatures," said the cognitive scientist Simon DeDeo of Carnegie Mellon University, who studies mathematical certainty by analyzing the structure of proofs. "We did not evolve to do this." Computers are useful for big calculations, but proofs require something different. Conjectures arise from inductive reasoning -- a kind of intuition about an interesting problem -- and proofs generally follow deductive, step-by-step logic. They often require complicated creative thinking as well as the more laborious work of filling in the gaps, and machines can't achieve this combination. Computerized theorem provers can be broken down into two categories.
Google AI introduces TF-Coder, a program synthesis tool that helps you write TensorFlow code
Manipulating tensors is not an easy task as it requires a lot of prerequisites, such as keeping track of multiple dimensions, Dtype compatibility, mathematical correctness, and tensor shape. The real challenge is identifying the right TensorFlow operations from the hundreds of options available. TensorFlow Coder(TF-Coder) makes the tensor manipulation possible without coding and by using examples. TF-Coder helps you write the TensorFlow code. The process is providing input-output examples of the required transformation.
On modularity in reactive control architectures, with an application to formal verification
Biggar, Oliver, Zamani, Mohammad, Shames, Iman
Modularity is a central principle throughout the design process for cyber-physical systems. Modularity reduces complexity and increases reuse of behavior. In this paper we pose and answer the following question: how can we identify independent `modules' within the structure of reactive control architectures? To this end, we propose a graph-structured control architecture we call a decision structure, and show how it generalises some reactive control architectures which are popular in Artificial Intelligence (AI) and robotics, specifically Teleo-Reactive programs (TRs), Decision Trees (DTs), Behavior Trees (BTs) and Generalised Behavior Trees ($k$-BTs). Inspired by the definition of a module in graph theory, we define modules in decision structures and show how each decision structure possesses a canonical decomposition into its modules. We can naturally characterise each of the BTs, $k$-BTs, DTs and TRs by properties of their module decomposition. This allows us to recognise which decision structures are equivalent to each of these architectures in quadratic time. Our proposed concept of modules extends to formal verification, under any verification scheme capable of verifying a decision structure. Namely, we prove that a modification to a module within a decision structure has no greater flow-on effects than a modification to an individual action within that structure. This enables verification on modules to be done locally and hierarchically, where structures can be verified and then repeatedly locally modified, with modules replaced by modules while preserving correctness. To illustrate the findings, we present an example of a solar-powered drone controlled by a decision structure. We use a Linear Temporal Logic-based verification scheme to verify the correctness of this structure, and then show how one can modify modules while preserving its correctness.