Logic & Formal Reasoning
10 Frequently Asked Interview Questions For Machine Learning In 2019
At the present scenario, organisations are hiring machine learning professionals to build applications with the help of machine learning techniques. The impact of this emerging technology is globally concerned. In this article, we list down 10 frequently asked questions to prepare for machine learning interviews in 2019. In Supervised machine learning technique, the machine is trained by using labelled data. Then a new dataset is fed into the learning model so that the algorithm gives a positive outcome by analysing the labelled data.
Write, Execute, Assess: Program Synthesis with a REPL
Ellis, Kevin, Nye, Maxwell, Pu, Yewen, Sosa, Felix, Tenenbaum, Josh, Solar-Lezama, Armando
We present a neural program synthesis approach integrating components which write, execute, and assess code to navigate the search space of possible programs. We equip the search process with an interpreter or a read-eval-print-loop (REPL), which immediately executes partially written programs, exposing their semantics. The REPL addresses a basic challenge of program synthesis: tiny changes in syntax can lead to huge changes in semantics. We train a pair of models, a policy that proposes the new piece of code to write, and a value function that assesses the prospects of the code written so-far. At test time we can combine these models with a Sequential Monte Carlo algorithm. We apply our approach to two domains: synthesizing text editing programs and inferring 2D and 3D graphics programs.
Inductive Logic Programming via Differentiable Deep Neural Logic Networks
We propose a novel paradigm for solving Inductive Logic Programming (ILP) problems via deep recurrent neural networks. This proposed ILP solver is designed based on differentiable implementation of the deduction via forward chaining. In contrast to the majority of past methods, instead of searching through the space of possible first-order logic rules by using some restrictive rule templates, we directly learn the symbolic logical predicate rules by introducing a novel differentiable Neural Logic (dNL) network. The proposed dNL network is able to learn and represent Boolean functions efficiently and in an explicit manner. We show that the proposed dNL-ILP solver supports desirable features such as recursion and predicate invention. Further, we investigate the performance of the proposed ILP solver in classification tasks involving benchmark relational datasets. In particular, we show that our proposed method outperforms the state of the art ILP solvers in classification tasks for Mutagenesis, Cora and IMDB datasets.
CoAPI: An Efficient Two-Phase Algorithm Using Core-Guided Over-Approximate Cover for Prime Compilation of Non-Clausal Formulae
Luo, Weilin, Wan, Hai, Zhong, Hongzhen, Wei, Ou
Prime compilation, i.e., the generation of all prime implicates or implicants (primes for short) of formulae, is a prominent fundamental issue for AI. Recently, the prime compilation for non-clausal formulae has received great attention. The state-of-the-art approaches generate all primes along with a prime cover constructed by prime implicates using dual rail encoding. However, the dual rail encoding potentially expands search space. In addition, constructing a prime cover, which is necessary for their methods, is time-consuming. To address these issues, we propose a novel two-phase method -- CoAPI. The two phases are the key to construct a cover without using dual rail encoding. Specifically, given a non-clausal formula, we first propose a core-guided method to rewrite the non-clausal formula into a cover constructed by over-approximate implicates in the first phase. Then, we generate all the primes based on the cover in the second phase. In order to reduce the size of the cover, we provide a multi-order based shrinking method, with a good tradeoff between the small size and efficiency, to compress the size of cover considerably. The experimental results show that CoAPI outperforms state-of-the-art approaches. Particularly, for generating all prime implicates, CoAPI consumes about one order of magnitude less time.
One-shot Information Extraction from Document Images using Neuro-Deductive Program Synthesis
Sunder, Vishal, Srinivasan, Ashwin, Vig, Lovekesh, Shroff, Gautam, Rahul, Rohit
Our interest in this paper is in meeting a rapidly growing industrial With the rapid advancement of Deep Learning (DL) for computer demand for information extraction from images of documents such vision problems, many DL architectures are available today for as invoices, bills, receipts etc. In practice users are able to provide a document image understanding ([11], [18], [22], [28]). But like most very small number of example images labeled with the information DLbased techniques, training these models from scratch is resource that needs to be extracted. We adopt a novel'two-level''neurodeductive', and data intensive. This is a major stumbling block for industrial approach where (a) we use pre-trained deep neural problems for which collecting and annotating data incur significant networks to populate a relational database with facts about each costs in time and money. In this paper, we use two complementary document-image; and (b) we use a form of deductive reasoning, forms learning to address this problem: related to meta-interpretive learning of transition systems to learn extraction programs: Given task-specific transitions defined using (1) Neural-learning: Using pre-trained DL models for reading the entities and relations identified by the neural detectors and document images and converting them into a structured a small number of instances (usually 1, sometimes 2) of images form by populating a predefined database schema.
Learning dynamic polynomial proofs
Fawzi, Alhussein, Malinowski, Mateusz, Fawzi, Hamza, Fawzi, Omar
Polynomial inequalities lie at the heart of many mathematical disciplines. In this paper, we consider the fundamental computational task of automatically searching for proofs of polynomial inequalities. We adopt the framework of semi-algebraic proof systems that manipulate polynomial inequalities via elementary inference rules that infer new inequalities from the premises. These proof systems are known to be very powerful, but searching for proofs remains a major difficulty. In this work, we introduce a machine learning based method to search for a dynamic proof within these proof systems. We propose a deep reinforcement learning framework that learns an embedding of the polynomials and guides the choice of inference rules, taking the inherent symmetries of the problem as an inductive bias. We compare our approach with powerful and widely-studied linear programming hierarchies based on static proof systems, and show that our method reduces the size of the linear program by several orders of magnitude while also improving performance. These results hence pave the way towards augmenting powerful and well-studied semi-algebraic proof systems with machine learning guiding strategies for enhancing the expressivity of such proof systems.
SMT-based Constraint Answer Set Solver EZSMT+
Constraint answer set programming integrates answer set programming with constraint processing. System EZSMT+ is a constraint answer set programming tool that utilizes satisfiability modulo theory solvers for search. Its theoretical foundation lies on generalizations of Niemela's characterization of answer sets of a logic program via so called level rankings.
Siamese recurrent networks learn first-order logic reasoning and exhibit zero-shot compositional generalization
Can neural nets learn logic? We approach this classic question with current methods, and demonstrate that recurrent neural networks can learn to recognize first order logical entailment relations between expressions. We define an artificial language in first-order predicate logic, generate a large dataset of sample 'sentences', and use an automatic theorem prover to infer the relation between random pairs of such sentences. We describe a Siamese neural architecture trained to predict the logical relation, and experiment with recurrent and recursive networks. Siamese Recurrent Networks are surprisingly successful at the entailment recognition task, reaching near perfect performance on novel sentences (consisting of known words), and even outperforming recursive networks. We report a series of experiments to test the ability of the models to perform compositional generalization. In particular, we study how they deal with sentences of unseen length, and sentences containing unseen words. We show that set-ups using LSTMs and GRUs obtain high scores on these tests, demonstrating a form of compositionality.
Synthesizing Datalog Programs using Numerical Relaxation
Si, Xujie, Raghothaman, Mukund, Heo, Kihong, Naik, Mayur
The problem of learning logical rules from examples arises in diverse fields, including program synthesis, logic programming, and machine learning. Existing approaches either involve solving computationally difficult combinatorial problems, or performing parameter estimation in complex statistical models. In this paper, we present Difflog, a technique to extend the logic programming language Datalog to the continuous setting. By attaching real-valued weights to individual rules of a Datalog program, we naturally associate numerical values with individual conclusions of the program. Analogous to the strategy of numerical relaxation in optimization problems, we can now first determine the rule weights which cause the best agreement between the training labels and the induced values of output tuples, and subsequently recover the classical discrete-valued target program from the continuous optimum. We evaluate Difflog on a suite of 34 benchmark problems from recent literature in knowledge discovery, formal verification, and database query-by-example, and demonstrate significant improvements in learning complex programs with recursive rules, invented predicates, and relations of arbitrary arity.
Out of Sight But Not Out of Mind: An Answer Set Programming Based Online Abduction Framework for Visual Sensemaking in Autonomous Driving
Suchan, Jakob, Bhatt, Mehul, Varadarajan, Srikrishna
We demonstrate the need and potential of systematically integrated vision and semantics} solutions for visual sensemaking (in the backdrop of autonomous driving). A general method for online visual sensemaking using answer set programming is systematically formalised and fully implemented. The method integrates state of the art in (deep learning based) visual computing, and is developed as a modular framework usable within hybrid architectures for perception & control. We evaluate and demo with community established benchmarks KITTIMOD and MOT. As use-case, we focus on the significance of human-centred visual sensemaking ---e.g., semantic representation and explainability, question-answering, commonsense interpolation--- in safety-critical autonomous driving situations.