Abstract Boolean networks (BNs) are well-studied models of genomic regulation in biology where nodes are genes and their state transition is controlled by Boolean functions. We propose to learn Boolean functions as Boolean formulas in disjunctive normal form (DNFs) by an explainable neural network Mat_DNF and apply it to learning BNs. Directly expressing DNFs as a pair of binary matrices, we learn them using a single layer NN by minimizing a logically inspired non-negative cost function to zero. As a result, every parameter in the network has a clear meaning of representing a conjunction or literal in the learned DNF. Also we can prove that learning DNFs by the proposed approach is equivalent to inferring interpolants in logic between the positive and negative data. We applied our approach to learning three literature-curated BNs and confirmed its effectiveness. We also examine how generalization occurs when learning data is scarce. In doing so, we introduce two new operations that can improve accuracy, or equivalently generalizability for scarce data. The first one is to append a noise vector to the input learning vector. The second one is to continue learning even after learning error becomes zero. The first one is explainable by the second one. These two operations help us choose a learnable DNF, i.e., a root of the cost function, to achieve high generalizability.

Boolean networks (BNs) are one of the standard tools for modeling gene regulatory networks in biology but their learning has been limited to small networks due to computational difficulty. Aiming at unprecedented scalability, we focus on a subclass of BNs called AND/OR Boolean networks where Boolean formulas are restricted to a conjunction or a disjunction of literals. We represent an AND/OR BN with N nodes by an N x 2N binary matrix Q paired with an N dimensional integer vector theta called a threshold vector, a state of the BN by an N dimensional binary state vector s and a state transition by matrix operations on Q, theta and s. Given a list of state transitions S = s_0...s_L, we learn Q and theta in a continuous space by minimizing a cost function J(Q*,theta,S) w.r.t. a real number matrix Q* and theta while thresholding Q* into a binary matrix Q using theta so that Q represents an AND/OR BN realizing the target state transitions S. We conducted experiments with artificial and real data sets to check scalability and accuracy of our learning algorithm. First we randomly generated AND/OR BNs up to N=5,000 nodes and empirically confirmed O(N^2) learning time behavior using them. We also observed 99.8% bit-by-bit prediction accuracy (prediction accuracy = 1 - test error) with state transition data generated by AND/OR BNs. For real data, we learned genome-wide AND/OR BNs with 10,928 nodes for budding yeast from transcription profiling data sets, each containing 10,928 mRNAs and 40 transitions and achieved for instance 84.3% prediction accuracy and successfully extracted more than 6,000 small AND/ORs whose average prediction accuracy reaches much higher 94.9%.

Abstract In this paper, we introduce methods of encoding propositional logic programs in vector spaces. Interpretations are represented by vectors and programs are represented by matrices. The least model of a definite program is computed by multiplying an interpretation vector and a program matrix. To optimize computation in vector spaces, we provide a method of partial evaluation of programs using linear algebra. Partial evaluation is done by unfolding rules in a program, and it is realized in a vector space by multiplying program matrices. We perform experiments using artificial data and real data, and show that partial evaluation has the potential for realizing efficient computation of huge scale of programs in vector spaces.

We propose a new approach to abduction, i.e., non-deductive inference to find a hypothesis H for an observation O such that H,KB |- O where KB is background knowledge. We reformulate it linear algebraically in vector spaces to abduce ``relations'', not logical formulas, to realize approximate but scalable abduction that can deal with web-scale knowledge bases. More specifically we consider the problem of abducing relations for Datalog programs with binary predicates. We treat two cases, the non-recursive case and the recursive case. In the non-recursive case, given r1(X,Y) and r3(X,Z), we abduce r2(Y,Z) so that r3(X,Z) <= r1(X,Y)&r2(Y,Z) approximately holds, by computing a matrix R2 that approximately satisfies a matrix equation R3 = min1(R1R2) containing a nonlinear function min1(x). Here R1, R2 andR3 encode as adjacency matrix r1(X,Y), r2(Y,Z) and r3(Y,Z) respectively. We apply this matrix-based abduction to rule discovery and relation discovery in a knowledge graph. The recursive case is mathematically more involved and computationally more difficult but solvable by deriving a recursive matrix equation and solving it. We illustrate concrete recursive cases including a transitive closure relation.

Abstract We propose a fundamentally new approach to Datalog evaluation. Given a linear Datalog program DB written usingNconstants and binary predicates, we first translate if-and-only-if completions of clauses in DB into a setEq(DB) of matrix equations with a non-linear operation, where relations inMDB, the least Herbrand model of DB, are encoded as adjacency matrices. We then translateEq(DB) into another, but purely linear matrix equationsẼq(DB). It is proved that the least solution ofẼq(DB) in the sense of matrix ordering is converted to the least solution ofEq(DB) and the latter givesMDBas a set of adjacency matrices. Hence, computing the least solution ofẼq(DB) is equivalent to computingMDBspecified by DB. For a class of tail recursive programs and for some other types of programs, our approach achievesO(N3) time complexity irrespective of the number of variables in a clause since only matrix operations costingO(N3) or less are used. We conducted two experiments that compute the least Herbrand models of linear Datalog programs. The first experiment computes transitive closure of artificial data and real network data taken from the Koblenz Network Collection. The second one compared the proposed approach with the state-of-the-art symbolic systems including two Prolog systems and two ASP systems, in terms of computation time for a transitive closure program and the same generation program. In the experiment, it is observed that our linear algebraic approach runs 101~ 104times faster than the symbolic systems when data is not sparse. Our approach is inspired by the emergence of big knowledge graphs and expected to contribute to the realization of rich and scalable logical inference for knowledge graphs.

This paper introduces "Boxcan", an information retrieval platform for aggregated objects in ID-based object management system based on GS1 EPCglobal architecture framework. Boxcan platform receives an EPC of a container, then provides a tree structure of current parent-child relationship between the EPCs of the container and its inner objects. This paper proposes the system design of Boxcan platform and its applications. The proposed system design is evaluated with a field test of a practical object management system including Boxcan platform. A technical challenge to realize this function of Boxcan platform, fast retrieval of current parent-child relationship of EPCs from EPCIS, is also discussed in this paper. The effectiveness of the caching mechanism of EPC's current parent-child tree, which is a solution to this technical problem, is also evaluated by an experiment in a comparison with direct querying to EPCIS.

Recently, the combination of probability, logic and learning has received considerable attention in the artificial intelligence and machine learning communities; see e.g. Getoor and Taskar (2007); De Raedt et al. (2008). Computational logic often plays a major role in these developments since it forms the theoretical backbone for much of the work in probabilistic programming and logical and relational learning. Contemporary work in this area is often application- and experiment-driven, but is also concerned with the theoretical foundations of formalisms and inference procedures and with advanced implementation technology that scales well.

Abstract VT (Viterbi training), or hard expectation maximization (EM), is an efficient way of parameter learning for probabilistic models with hidden variables. Given an observation y, it searches for a state of hidden variables x that maximizes p(x,y | θ) by coordinate ascent on parameters θ and x. In this paper we introduce VT to PRogramming In Statistical Modeling (PRISM), a logic-based probabilistic modeling system for generative models. VT improves PRISM in three ways. First, VT in PRISM converges faster than EM in PRISM due to VT's termination condition. Second, parameters learned by VT often show good prediction performance compared with those learned by EM. We conducted two parsing experiments with probabilistic grammars while learning parameters by a variety of inference methods, i.e. VT, EM, MAP and VB. The result is that VT achieved the best parsing accuracy among them in both experiments. Also, we conducted a similar experiment for classification tasks where a hidden variable is not a prediction target unlike probabilistic grammars. We found that in such a case VT does not necessarily yield superior performance. Third, since VT always deals with a single probability of a single explanation, Viterbi explanation, the exclusiveness condition imposed on PRISM programs is no more required if we learn parameters by VT. Last but not least, we can say that as VT in PRISM is general and applicable to any PRISM program, it largely reduces the need for the user to develop a specific VT algorithm for a specific model. Furthermore, since VT in PRISM can be used just by setting a PRISM flag appropriately, it makes VT easily accessible to (probabilistic) logic programmers.

Abstract Tabling in logic programming has been used to eliminate redundant computation and also to stop infinite loop. In this paper we investigate another possibility of tabling, i.e. to compute an infinite sum of probabilities for probabilistic logic programs. Using PRISM, a logic-based probabilistic modeling language with a tabling mechanism, we generalize prefix probability computation for probabilistic context-free grammars (PCFGs) to probabilistic logic programs. Given a top-goal, we search for all proofs with tabling and obtain an explanation graph which compresses them and may be cyclic. We then convert the explanation graph to a set of linear probability equations and solve them by matrix operation. The solution gives us the probability of the top-goal, which, in nature, is an infinite sum of probabilities. Our general approach to prefix probability computation through tabling not only allows to deal with non-probabilistic context-free grammars such as probabilistic left-corner grammars but has applications such as plan recognition and probabilistic model checking and makes it possible to compute probability for probabilistic models describing cyclic relations.

One practical inconvenience in frequent pattern mining is that it often yields a flood of common or uninformative patterns, and thus we should carefully adjust the minimum support. To alleviate this inconvenience, based on FP-growth, this paper proposes RP-growth, an efficient algorithm for top-k mining of discriminative patterns which are highly relevant to the class of interest. RP-growth conducts a branch-and-bound search using anti-monotonic upper bounds of the relevance scores such as F-score and χ2, and the pruning in branch-and-bound search is successfully translated to minimum support raising, a standard, easy-to-implement pruning strategy for top-k mining. Furthermore, by introducing the notion called weakness and an additional, aggressive pruning strategy based on weakness, RP-growth efficiently finds k patterns of wide variety and high relevance to the class of interest. Experimental results on text classification exhibit the efficiency and the usefulness of RP-growth.

In a knowledge discovery process, interpretation and evaluation of the mined results are indispensable in practice. In the case of data clustering, however, it is often difficult to see in what aspect each cluster has been formed. This paper proposes a method for automatic and objective characterization or "verbalization" of the clusters obtained by mixture models, in which we collect conjunctions of propositions (attribute value pairs) that help us interpret or evaluate the clusters. The proposed method provides us with a new, in-depth and consistent tool for cluster interpretation/evaluation, and works for various types of datasets including continuous attributes and missing values. Experimental results exhibit the utility of the proposed method, and the importance of the feedbacks from the interpretation/evaluation step.

We propose a generalMCMC method for Bayesian inference in logic-based probabilistic modeling. It covers a broad class of generativemodels including Bayesian networks and PCFGs. The idea is to generalize an MCMC method for PCFGs to the one for a Turing-complete probabilistic modeling language PRISM in the context of statistical abduction where parse trees are replaced with explanations. We describe how to estimate the marginal probability of data from MCMC samples and how to perform Bayesian Viterbi inference using an example of Naive Bayesmodel augmentedwith a hidden variable.

Mode-directed tabling amounts to using table modes to control what arguments are used in variant checking of subgoals and how answers are tabled. A mode can be min, max, + (input), (output), or nt (non-tabled). While the traditional table-all approach to tabling is good for finding all answers, mode-directed tabling is well suited to dynamic programming problems that require selective answers. In this paper, we present three application examples of mode-directed tabling, namely, (1) hydraulic system planning, a dynamic programming problem, (2) the Viterbi algorithm in PRISM, a probabilistic logic reasoning and learning system, and (3) constraint checking in evaluating Answer Set Programs (ASP). For the Viterbi application, the feature of enabling a cardinality limit in a table mode declaration plays an important role. For a PRISM program and a set of data, the explanations may be too large to be completely stored and the cardinality limit allows for Viterbi inference based on a subset of explanations. The mode nt, which specifies an argument that can participate in the computation of a tabled predicate but is never tabled either in subgoal or answer tabling, is useful in constraint checking for the Hamilton cycle problem encoded as an ASP. These examples demonstrate the usefulness of mode-directed tabling.

Abstract PRISM is an extension of Prolog with probabilistic predicates and built-in support for expectation-maximization learning. Constraint Handling Rules (CHR) is a high-level programming language based on multi-headed multiset rewrite rules. In this paper, we introduce a new probabilistic logic formalism, called CHRiSM, based on a combination of CHR and PRISM. It can be used for high-level rapid prototyping of complex statistical models by means of “chance rules”. The underlying PRISM system can then be used for several probabilistic inference tasks, including probability computation and parameter learning. We define the CHRiSM language in terms of syntax and operational semantics, and illustrate it with examples. We define the notion of ambiguous programs and define a distribution semantics for unambiguous programs. Next, we describe an implementation of CHRiSM, based on CHR(PRISM). We discuss the relation between CHRiSM and other probabilistic logic programming languages, in particular PCHR. Finally, we identify potential application domains.

Abstract Recently there has been a growing interest in research in tabling in the logic programming community because of its usefulness in a variety of application domains including program analysis, parsing, deductive databases, theorem proving, model checking, and logic-based probabilistic learning. The main idea of tabling is to memorize the answers to some subgoals and use the answers to resolve subsequent variant subgoals. Early resolution mechanisms proposed for tabling such as OLDT and SLG rely on suspension and resumption of subgoals to compute fixpoints. Recently, the iterative approach named linear tabling has received considerable attention because of its simplicity, ease of implementation, and good space efficiency. Linear tabling is a framework from which different methods can be derived on the basis of the strategies used in handling looping subgoals. One decision concerns when answers are consumed and returned. This article describes two strategies, namely, lazy and eager strategies, and compares them both qualitatively and quantitatively. The results indicate that, while the lazy strategy has good locality and is well suited for finding all solutions, the eager strategy is comparable in speed with the lazy strategy and is well suited for programs with cuts. Linear tabling relies on depth-first iterative deepening rather than suspension to compute fixpoints. Each cluster of interdependent subgoals as represented by a topmost looping subgoal is iteratively evaluated until no subgoal in it can produce any new answers. Naive re-evaluation of all looping subgoals, albeit simple, may be computationally unacceptable. In this article, we also introduce semi-naive optimization, an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers, into linear tabling. We give the conditions for the technique to be safe (i.e., sound and complete) and propose an optimization technique called early answer promotion to enhance its effectiveness. Benchmarking in B-Prolog demonstrates that with this optimization linear tabling compares favorably well in speed with the state-of-the-art implementation of SLG.

Semi-naive evaluation is an effective technique employed in bottom-up evaluation of logic programs to avoid redundant joins of answers. The impact of this technique on top-down evaluation had been unknown. In this paper, we introduce semi-naive evaluation into linear tabling, a top-down resolution mechanism for tabled logic programs. We give the conditions for the technique to be safe and propose an optimization technique called early answer promotion to enhance its effectiveness. While semi-naive evaluation is not as effective in linear tabling as in bottom-up evaluation, it is worthwhile to be adopted. Our benchmarking shows that this technique gives significant speed-ups to some programs.

Early resolution mechanisms proposed for tabling such as OLDT rely on suspension and resumption of subgoals to compute fixpoints. Recently, a new resolution framework called linear tabling has emerged as an alternative tabling method. The idea of linear tabling is to use iterative computation rather than suspension to compute fixpoints. Although linear tabling is simple, easy to implement, and superior in space efficiency, the current implementations are several times slower than XSB, the state-of-the-art implementation of OLDT, due to re-evaluation of looping subgoals. In this paper, we present a new linear tabling method and propose several optimization techniques for fast computation of fixpoints. The optimization techniques significantly improve the performance by avoiding redundant evaluation of subgoals, re-application of clauses, and reproduction of answers in iterative computation. Our implementation of the method in B-Prolog not only consumes an order of magnitude less stack space than XSB for some programs but also compares favorably well with XSB in speed.

We propose a logical/mathematical framework for statistical parameter learning of parameterized logic programs, i.e. definite clause programs containing probabilistic facts with a parameterized distribution. It extends the traditional least Herbrand model semantics in logic programming to distribution semantics, possible world semantics with a probability distribution which is unconditionally applicable to arbitrary logic programs including ones for HMMs, PCFGs and Bayesian networks. We also propose a new EM algorithm, the graphical EM algorithm, that runs for a class of parameterized logic programs representing sequential decision processes where each decision is exclusive and independent. It runs on a new data structure called support graphs describing the logical relationship between observations and their explanations, and learns parameters by computing inside and outside probability generalized for logic programs. The complexity analysis shows that when combined with OLDT search for all explanations for observations, the graphical EM algorithm, despite its generality, has the same time complexity as existing EM algorithms, i.e. the Baum-Welch algorithm for HMMs, the Inside-Outside algorithm for PCFGs, and the one for singly connected Bayesian networks that have been developed independently in each research field. Learning experiments with PCFGs using two corpora of moderate size indicate that the graphical EM algorithm can significantly outperform the Inside-Outside algorithm.

This paper introduces a new approach to genetic programming (GP), based on a numerical technique, which integrates a GP-based adaptive search of tree structures, and a local parameter tuning mechanism employing statistical search (a system identification technique). In traditional GP, recombination can cause frequent disruption of building blocks or mutation can cause abrupt changes in the semantics. To overcome these difficulties, we supplement traditional GP with a local hill-climbing search, using a parameter tuning procedure. More precisely, we integrate the structural search of traditional GP with a multiple regression analysis method and establish our adaptive program, called STROGANOFF (STructured Representation On Genetic Algorithms for NOn-linear Function Fitting). The fitness evaluation is based on a minimum description length (MDL) criterion, which effectively controls the tree growth in GP. We demonstrate its effectiveness by solving several system identification (numerical) problems and compare the performance of STROGANOFF with traditional GP and another standard technique (radial basis functions). We then extend STROGANOFF to symbolic (nonnumerical) reasoning by introducing multiple types of nodes, using a modified MDL-based selection criterion and a pruning of the resultant trees. The effectiveness of this numerical approach to GP is demonstrated by successful application to symbolic regression problems.