Akihiro Yamamoto

AAAI Conference 2021 Conference Paper

Differentiable Inductive Logic Programming for Structured Examples

• Hikaru Shindo
• Masaaki Nishino
• Akihiro Yamamoto

The differentiable implementation of logic yields a seamless combination of symbolic reasoning and deep neural networks. Recent research, which has developed a differentiable framework to learn logic programs from examples, can even acquire reasonable solutions from noisy datasets. However, this framework severely limits expressions for solutions, e. g. , no function symbols are allowed, and the shapes of clauses are fixed. As a result, the framework cannot deal with structured examples. Therefore we propose a new framework to learn logic programs from noisy and structured examples, including the following contributions. First, we propose an adaptive clause search method by looking through structured space, which is defined by the generality of the clauses, to yield an efficient search space for differentiable solvers. Second, we propose for ground atoms an enumeration algorithm, which determines a necessary and sufficient set of ground atoms to perform differentiable inference functions. Finally, we propose a new method to compose logic programs softly, enabling the system to deal with complex programs consisting of several clauses. Our experiments show that our new framework can learn logic programs from noisy and structured examples, such as sequences or trees. Our framework can be scaled to deal with complex programs that consist of several clauses with function symbols.

ECAI Conference 2020 Conference Paper

Metric Learning for Ordered Labeled Trees with pq-grams

• Hikaru Shindo
• Masaaki Nishino
• Yasuaki Kobayashi
• Akihiro Yamamoto

Computing the similarity between two data points plays a vital role in many machine learning algorithms. Metric learning has the aim of learning a good metric automatically from data. Most existing studies on metric learning for tree-structured data have adopted the approach of learning the tree edit distance. However, the edit distance is not amenable for big data analysis because it incurs high computation cost. In this paper, we propose a new metric learning approach for tree-structured data with pq-grams. The pq-gram distance is a distance for ordered labeled trees, and has much lower computation cost than the tree edit distance. In order to perform metric learning based on pq-grams, we propose a new differentiable parameterized distance, weighted pq-gram distance. We also propose a way to learn the proposed distance based on Large Margin Nearest Neighbors (LMNN), which is a well-studied and practical metric learning scheme. We formulate the metric learning problem as an optimization problem and use the gradient descent technique to perform metric learning. We empirically show that the proposed approach not only achieves competitive results with the state-of-the-art edit distance-based methods in various classification problems, but also solves the classification problems much more rapidly than the edit distance-based methods.

AAAI Conference 2016 Conference Paper

Inductive Logic Programming: Challenges

• Katsumi Inoue
• Hayato Ohwada
• Akihiro Yamamoto

UAI Conference 2011 Conference Paper

Discovering causal structures in binary exclusive-or skew acyclic models

• Takanori Inazumi
• Takashi Washio
• Shohei Shimizu
• Joe Suzuki
• Akihiro Yamamoto
• Yoshinobu Kawahara

Discovering causal relations among observed variables in a given data set is a main topic in studies of statistics and artificial intelligence. Recently, some techniques to discover an identifiable causal structure have been explored based on non-Gaussianity of the observed data distribution. However, most of these are limited to continuous data. In this paper, we present a novel causal model for binary data and propose a new approach to derive an identifiable causal structure governing the data based on skew Bernoulli distributions of external noise. Experimental evaluation shows excellent performance for both artificial and real world data sets.

TCS Journal 2010 Journal Article

Mind change complexity of inferring unbounded unions of restricted pattern languages from positive data

• Matthew de Brecht
• Akihiro Yamamoto

This paper shows that the mind change complexity of inferring from positive data the class of unbounded unions of languages of regular patterns with constant segment length bound is of the form ω ω α + β, assuming that the patterns are defined over a finite alphabet containing at least two elements. Here α and β are natural numbers, and we give tight bounds on their values based on the length of the constant segments and the size of the alphabet of the pattern languages. This is, to the authors’ knowledge, the first time a natural class of languages has been shown to be inferable with mind change complexity above ω ω. The proof uses the notion of closure operators on a class of languages, and also uses the order type of well-partial-orderings to obtain a mind change bound. The inference algorithm presented can be easily applied to a wide range of classes of languages. Finally, we show an interesting connection between proof theory and mind change complexity.

I&C Journal 2010 Journal Article

Topological properties of concept spaces (full version)

• Matthew Brecht
• Akihiro Yamamoto

Based on the observation that the category of concept spaces with the positive information topology is equivalent to the category of countably based T 0 topological spaces, we investigate further connections between the learning in the limit model of inductive inference and topology. In particular, we show that the “texts” or “positive presentations” of concepts in inductive inference can be viewed as special cases of the “admissible representations” of computable analysis. We also show that several structural properties of concept spaces have well known topological equivalents. In addition to topological methods, we use algebraic closure operators to analyze the structure of concept spaces, and we show the connection between these two approaches. The goal of this paper is not only to introduce new perspectives to learning theorists, but also to present the field of inductive inference in a way more accessible to domain theorists and topologists.

TCS Journal 2006 Journal Article

Hypothesis finding with proof theoretical appropriateness criteria

• Bertram Fronhöfer
• Akihiro Yamamoto

For two given formulae B and E with B ⊭ E, hypothesis finding means to produce a formula H such that B ∧ H ⊨ E. Hypothesis finding, or variants thereof, is central to various types of inference, e. g. , abductive inference, inductive inference, machine learning, and machine discovery. Clarifying the nature of hypothesis finding is still in its infancy, a situation similar to the establishment of logical foundations of inference related to induction and discovery. Although trivial solutions to hypothesis finding are easy to give, finding appropriate hypotheses still remains as a great challenge. A central role in this context plays the question, what it means for a hypothesis to be appropriate? In this paper we propose an answer to this question, which is based on proof theoretical criteria. This is in contrast to most previous approaches where appropriateness of hypotheses was based on concepts of semantical weakness in classical logic. More precisely, we use provability in Relevance Logic instead of classical semantical entailment, we demand utmost exploitation of the inferential potential (deductive content) inherent in B → E and we demand H to be a minimal deductive supplement to B → E. Along these lines we developed the concept of a minimized residue hypothesis which also constitutes an interesting trade-off between ‘logical smallness’ and ‘syntactical smallness’.

TCS Journal 2003 Journal Article

Hypothesis finding based on upward refinement of residue hypotheses

• Akihiro Yamamoto

For given logical formulae B and E such that B⊨E, hypothesis finding means the generation of a formula H such that B∧H⊨E. Hypothesis finding constitutes a basic technique for fields of inference, like inductive inference and knowledge discovery. In order to put various hypothesis finding methods proposed previously on one general ground, we use upward refinement and residue hypotheses. We show that their combination is a complete method for solving any hypothesis finding problem in clausal logic. We extend the relative subsumption relation, and show that some hypothesis finding methods previously presented can be regarded as finding hypotheses which subsume examples relative to a given background theory. Noting that the weakening rule may make hypothesis finding difficult to solve, we propose restricting this rule either to the inverse of resolution or to that of subsumption. We also note that this work is related to relevant logic.

TCS Journal 1992 Journal Article

Learning elementary formal system

• Setsuo Arikawa
• Takeshi Shinohara
• Akihiro Yamamoto

The elementary formal systems (EFS for short) Smullyan invented to develop his recursive function theory, are proved suitable to generate languages. In this paper we first point out that EFS can also work as a logic programming language, and the resolution procedure for EFS can be used to accept languages. We give a theoretical foundation to EFS from the viewpoint of semantics of logic programs. Hence, Shapiro's theory of model inference can naturally be applied to our language learning by EFS. We introduce some subclasses of EFS's with correspond to Chomsky hierarchy and other important classes of languages. We discuss computations of unifiers between two terms. Then we give inductive inference algorithms including refinement operators for these subclasses and show their completeness.