Taisuke Sato

NAI Journal 2026 Journal Article

Towards End-to-End ASP Computation

• Taisuke Sato
• Akihiro Takemura
• Katsumi Inoue

We propose an end-to-end approach for Answer Set Programming (ASP) and linear algebraically compute stable models satisfying given constraints. The idea is to implement Lin-Zhao’s theorem together with constraints directly in vector spaces as numerical minimization of a cost function constructed from a matricized normal logic program, loop formulas in Lin-Zhao’s theorem and constraints, thereby no use of symbolic ASP or SAT solvers involved in our approach. We also propose precomputation that shrinks the program size and heuristics for loop formulas to reduce computational difficulty. We empirically test our approach with programming examples including the three-coloring and Hamiltonian cycle problems.

KR Conference 2021 Conference Paper

Boolean Network Learning in Vector Spaces for Genome-wide Network Analysis

• Taisuke Sato
• Ryosuke Kojima

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%.

NeSy Conference 2019 Conference Paper

T-PRISM: A tensorized logic programming language for data modelling

• Ryosuke Kojima
• Taisuke Sato

We introduce a new logic programming language T-PRISM based on tensor embeddings. Our embedding scheme is a modification of the distribution semantics in PRISM, one of the state-of-the-art probabilistic logic programming languages, by replacing distribution functions with multidimensional arrays, i. e. , tensors. T-PRISM consists of two parts: logic programming part and numerical computation part. The former provides flexible and interpretable modeling at the level of first order logic, and the latter part provides scalable computation utilizing parallelization and hardware acceleration with GPUs. Combing these two parts provides a remarkably wide range of high-level declarative modeling from symbolic reasoning to deep learning. To embody this programming language, we also introduce a new semantics, termed tensorized semantics, which combines the traditional least model semantics in logic programming with the embeddings of tensors. In T-PRISM, we first derive a set of equations related to tensors from a given program using logical inference, i. e. , Prolog execution in a symbolic space and then solve the derived equations in a continuous space by TensorFlow. Using our preliminary implementation of T-PRISM, we have successfully dealt with a wide range of modeling. We have succeeded in dealing with real large-scale data in the declarative modeling. This paper presents a DistMult model for knowledge graphs using the FB15k and WN18 datasets.

IJCAI Conference 2018 Conference Paper

Abducing Relations in Continuous Spaces

• Taisuke Sato
• Katsumi Inoue
• Chiaki Sakama

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.

IJCAI Conference 2011 Conference Paper

A General MCMC Method for Bayesian Inference in Logic-Based Probabilistic Modeling

• Taisuke Sato

We propose a general MCMC method for Bayesian inference in logic-based probabilistic modeling. It covers a broad class of generative models 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 Bayes model augmented with a hidden variable.

IJCAI Conference 2009 Conference Paper

• Katsumi Inoue
• Taisuke Sato
• Masakazu Ishihata
• Yoshitaka Kameya
• Hidetomo Nabeshima

Abductive inference is an important AI reasoning technique to find explanations of observations, and has recently been applied to scientific discovery. To find best hypotheses among many logically possible hypotheses, we need to evaluate hypotheses obtained from the process of hypothesis generation. We propose an abductive inference architecture combined with an EM algorithm working on binary decision diagrams (BDDs). This work opens a way of applying BDDs to compress multiple hypotheses and to select most probable ones from them. An implemented system has been applied to inference of inhibition in metabolic pathways in the domain of systems biology.

IJCAI Conference 2007 Conference Paper

• Taisuke Sato

In this paper we prove that the well-known correspondence between the forward-backward algorithm for hidden Markov models (HMMs) and belief propagation (BP) applied to HMMs can be generalized to one between BP for junction trees and the generalized inside-outside probability computation for probabilistic logic programs applied to junction trees.

IJCAI Conference 2007 Conference Paper

• Shin-ichi Minato
• Ken Satoh
• Taisuke Sato

Compiling Bayesian networks (BNs) is a hot topic within probabilistic modeling and processing. In this paper, we propose a new method for compiling BNs into Multi-Linear Functions (MLFs) based on Zero-suppressed Binary Decision Diagrams (ZBDDs), which are a graph-based representation of combinatorial item sets. Our method differs from the original approach of Darwiche et al. , which encodes BNs into Conjunctive Normal Forms (CNFs) and then translates CNFs into factored MLFs. Our approach directly translates a BN into a set of factored MLFs using a ZBDD-based symbolic probability calculation. The MLF may have exponential computational complexity, but our ZBDD-based data structure provides a compact factored form of the MLF, and arithmetic operations can be executed in a time almost linear with the ZBDD size. In our method, it is not necessary to generate the MLF for the whole network, as we can extract MLFs for only part of the network related to the query, avoiding unnecessary calculation of redundant MLF terms. We present experimental results for some typical benchmark examples. Although our algorithm is simply based on the mathematical definition of probability calculation, performance is competitive to existing state-of-the-art methods.

IJCAI Conference 2005 Conference Paper

Generative Modeling with Failure in PRISM

• Taisuke Sato
• Yoshitaka Kameya
• Neng-Fa

PRISM is a logic-based Turing-complete symbolicstatistical modeling language with a built-in parameter learning routine. In this paper, we enhance the modeling power of PRISM by allowing general PRISM programs to fail in the generation process of observable events. Introducing failure extends the class of definable distributions but needs a generalization of the semantics of PRISM programs. We propose a three valued probabilistic semantics and show how failure enables us to pursue constraint-based modeling of complex statistical phenomena.

LOPSTR Conference 2004 Conference Paper

Negation Elimination for Finite PCFGs

• Taisuke Sato
• Yoshitaka Kameya

Abstract We introduce negation to a symbolic-statistical modeling language PRISM and propose to eliminate negation by program transformation called negation technique which is applicable to probabilistic logic programs. We also introduce finite PCFGs (probabilistic context free grammars) as PCFGs with finite constraints as part of generative modeling of stochastic HPSGs (head-driven phrase structure grammars). They are a subclass of log-linear models and allow exact computation of normalizing constants. We apply the negation technique to a PDCG (probabilistic definite clause grammar) program written in PRISM that describes a finite PCFG with a height constraint. The resulting program computes a normalizing constant for the finite PCFG in time linear in the given height. We also report on an experiment of parameter learning for a real grammar (ATR grammar) with the height constraint. We have discovered that the height constraint does not necessarily lead to a significant decrease in parsing accuracy.

ECAI Conference 2004 Conference Paper

Yet More Efficient EM Learning for Parameterized Logic Programs by Inter-Goal Sharing

• Yoshitaka Kameya
• Taisuke Sato
• Neng-Fa Zhou

IJCAI Conference 1997 Conference Paper

PRISM: A Language for Symbolic-Statistical Modeling

• Taisuke Sato
• Yoshitaka Kameya

We present an overview of symbolic-statistical modeling language PRISM whose programs are not only a probabilistic extension of logic programs but also able to learn from examples with the help of the EM learning algorithm. As a knowledge representation language appropriate for probabilistic reasoning, it can describe various types of symbolic-statistical modeling formalism known but unrelated so far in a single framework. We show by examples, together with learning results, that most popular probabilistic modeling formalisms, the hidden Markov model and Bayesian networks, are described by PRISM programs.

IJCAI Conference 1993 Conference Paper

Evolutionary Learning Strategy using Bug-Based Search

• Hitoshi Iba
• Tetsuya Higuchi
• Hugo deGaris
• Taisuke Sato

We introduce a new approach to GA (Genetic Algorithms) based problem solving. Earlier GAs did not contain local search (i. e. hill climbing) mechanisms, which led to optimization difficulties, especially in higher dimensions. To overcome such difficulties, we introduce a "bug-based" search strategy, and implement a system called BUGS2. The ideas behind this new approach are derived from biologically realistic bug behaviors. These ideas were confirmed empirically by applying them to some optimization and computer vision problems.

TCS Journal 1992 Journal Article

Equivalence-preserving first-order unfold/fold transformation systems

• Taisuke Sato

Two unfold/fold transformation systems for first-order programs, one basic and the other extended, are presented. The systems comprise an unfolding rule, a folding rule and a replacement rule. They are intended to work with a first-order theory Δ specifying the meaning of primitives, on top of which new relations are built by programs. They preserve the provability relationship Δ ∪ Γ ⊬ G between a call-consistent program Γ and a goal formula G such that Γ is strict with respect to G. They also preserve the logical consequence relationship in three-valued logic.

TCS Journal 1984 Journal Article

Enumeration of success patterns in logic programs

• Taisuke Sato
• Hisao Tamaki