Learning of Primitive Formal Systems De ning Labelled Ordered Tree Languages via Queries

Abstract

A formal graph system (FGS) is a logic programming system that directly manipulates graphs by dealing with term graph patterns instead of terms of rst-order predicate logic. In this paper, based on FGS, we introduce a primitive formal ordered tree system (pFOTS) as a formal system de ning labelled ordered tree languages. A pFOTS program is a nite set of graph rewriting rules. A logic program is well-known to be suitable to represent background knowledge. The query learning model is an established mathematical model of learning via queries in computational learning theory. In this learning model, we show the exact learnability of a pFOTS program consisting of one graph rewriting rule and background knowledge de ned with a pFOTS program using a polynomial number of queries.

Introduction

Graph grammar (see [ 6 ]) has been applied to a wide range of elds including pattern recognition and image analysis. Uchida et al. [ 10 ] introduced a framework called a formal graph system (FGS) as a graph grammar. An FGS is a logic programming system that directly manipulates graphs by dealing with term graph patterns instead of terms of rst-order predicate logic.

Recently, many graph structured data become accessible on Internet. Graph structured data such as XML les having tree structures are called tree structured data. Ordered tree can represent such graph data such as XML les, glycan data and parsing structures of natural languages. In order to represent structural features Copyright ⃝c by the paper's authors. Copying permitted for private and academic purposes. from tree structured data, we propose an ordered term tree pattern [ 3, 9 ], which is a tree pattern t such that (i) t has ordered tree structures, and (ii) t has some internal structured variables. A variable of an ordered term tree pattern has a variable label and can be replaced with an arbitrary ordered tree by hyperedge replacement according to the variable label. Computational learning theory is an important research area in inductive logic programming and machine learning. In the computational learning theory, we showed in [ 9 ] that the class of languages de ned by ordered term tree patterns is polynomial time inductively inferable from positive data. The query learning model is the exact learning model of Angluin [ 1 ], which is an established mathematical model of learning via queries in computational learning theory. In this learning model, a learning algorithm accesses oracles, which answer speci c types of queries, and collects information about a target.

In this paper, based on FGS, we introduce a primitive formal ordered tree system (pFOTS) as a formal system de ning labelled ordered tree languages. A pFOTS program is a nite set of graph rewriting rules that replace variables of ordered term tree patterns with speci ed ordered trees. A logic program is well-known to be suitable to represent background knowledge. In this paper, we consider a pFOTS program to be background knowledge. We propose a learning method of new graph rewriting rules under background knowledge de ned by a pFOTS program. In Fig.1, we give a pFOTS program OT , graph rewriting rule and language L( OT [ f g; r) de ned using the pFOTS program OT [ f g and predicate symbol r as examples. In this paper, we propose leaning methods which nd the target graph rewriting rule by given background knowledge OT and the given target language L( OT [ f g; r). Our learning methods use some operators based on the given pFOTS program. Therefore, even if the given pFOTS program and the language are changed, our leaning algorithms will nd the target graph rewriting rule.

In this paper, we show that if background knowledge is given by a pFOTS program which has one predicate symbol, then one graph rewriting rule is exactly learnable with one positive example and a polynomial number of membership queries w.r.t. the size of the positive example. Moreover, we show the learnability of one graph rewriting rule under pFOTS program having multiple predicate symbols as background knowledge.

For the learning of ordered tree languages, Suzuki et al. [ 9 ] showed that the class of languages de ned by ordered term tree patterns is polynomial time inductively inferable from positive data. Matsumoto et al. [ 4 ] showed that nite unions of ordered term tree pattern languages are exactly learnable with a polynomial number of queries. For the learning of graph grammars, Okada et al. [ 5 ] showed that some classes of graph pattern languages de ned by FGS are exactly learnable with a polynomial number of equivalence and restricted subset queries. Shoudai et al. [ 8 ] showed that the regular FGS languages of bounded degree with the 1- nite context property and bounded treewidth property are learnable from positive data and membership queries with current distributional learning techniques [ 2 ].

This paper is organized as follows. In Sections 2, we introduce a primitive formal ordered tree system (pFOTS) as a formal system de ning ordered tree languages based on FGS [ 10 ]. In Section 3, we introduce the query learning model [ 1 ] and consider the exact learnability of one graph rewriting rule under pFOTS program as background knowledge in the query learning model. Moreover, we show the exact learnability of one graph rewriting rule under pFOTS program having multiple predicate symbols as background knowledge. Finally, in Section 4, we conclude this paper and discuss future work. 2

Primitive Formal Ordered Tree Systems (pFOTS)

Let and be nite alphabets whose elements are called node-labels and edge-labels, respectively. Let X be an in nite alphabet whose element is called a variable label. We assume that \ X = ∅. A node- and edge-labelled ordered tree t = (Vt; Et) over ⟨ ; [ X ⟩ is an ordered tree that has a node-labelling function t : Vt ! and an edge-labelling function φt : Et ! [ X . An edge labelled with a variable label in X is called a variable. For any x 2 X , o(t; x) denotes the number of variables in t labelled with x. A node- and edge-labelled ordered tree t over ⟨ ; [ X ⟩ is said to be a linear term tree pattern over ⟨ ; [ X ⟩ if, for any x 2 X , o(t; x) 1 holds. For a node v 2 Vt, except the root of t, and parent u 2 Vt of v, the edge e between u and v is denoted as (u; v) if φt(e) 2 and as ⟨u; v⟩ if φt(e) 2 X , respectively. Hereafter, an edge of t means an edge whose label is in . A linear term tree pattern over ⟨ ; [ X ⟩ with no variable is a node- and edge-labelled ordered tree over ⟨ ; ⟩ and is simply called a tree over ⟨ ; ⟩. The term OT denotes the set of all trees over ⟨ ; ⟩. Hereafter, a linear term tree pattern over ⟨ ; [ X ⟩ is simply called a term tree pattern. A term tree pattern is said to be primitive if it consists of two nodes and one variable between them.

Let f and g be term tree patterns with at least two nodes. Let = [u; v] be a pair of the root u and a leaf v of g and x a variable label in X . The form x := [g; ] is called a binding over ⟨ ; [ X ⟩. A new term tree pattern, 2 t 1 c a CC

C

C 2 t A p ( s b t ; ) , >9>

> p ( s 1 x 2 t ) ; p ( s 1 y 2 t ), >>>>>>

= p ( s 1 x 2 t ) ; p ( s 1 y 2 t )

p ( s 1 x 2 t ; ) ; p ( s 1 y 2 t ) L( OT [ f g; r) = <>>>os > > > > > > : 8 > > > a t

o c a , s a t t

a t a t o

a a b a c a , o a b s c a t b t

a t o a a b a , o a s c a b

t a a a > > > > > > > > > ; denoted as f fx := [g; ]g, is obtained by applying the binding x := [g; ] to f as follows. Let e = ⟨s; t⟩ be a variable in f with the variable label x, i.e., φf (e) = x. Let g′ be a copy of g, and u′ and v′ be the nodes of g′ corresponding to u and v of g, respectively. For e = ⟨s; t⟩, we attach g′ to f by removing e from f , then identifying s with u′ and t with v′. For all internal nodes of f fx := [g; ]g to have the ordered children, the children of s need to be reordered (refer to [ 9 ]). A substitution is a nite set of bindings fx1 := [g1; 1]; x2 := [g2; 2]; : : : ; xn := [gn; n]g, where xis are mutually distinct variable labels in X . For a term tree pattern f and a substitution , we denote the term tree pattern obtained from f and denoted as f by applying all bindings in to f simultaneously. Let be a set of unary predicate symbols. We assume that each predicate symbol p 2 is assigned a pair of two distinct two symbols in . The pair is denoted as pointer(p). Let p be a unary predicate symbol in and t a term tree pattern. An atom is an expression of the form p(t). Let A; B1; B2; : : : ; Bn be atoms, where n 0. A graph rewriting rule (rule) over ⟨ ; ; [ X ⟩ is a clause of the form A B1; B2; : : : ; Bn. Atom A is called the head and the right part B1; B2; : : : ; Bn is called the body of the rule. If n = 0, the rule is called a fact. A rule p(t) q1(f1); q2(f2); : : : ; qn(fn) is said to be primitive if the following conditions (1){(3) hold: (1) if n 1, fi are primitive term tree patterns over ⟨fa j a 2 pointer(qi)g; X ⟩ for all i (1 i n), (2) if n = 0, t is a tree over ⟨fa j a 2 pointer(p)g; ⟩ consisting of two nodes and the edge between them; otherwise t is a term tree pattern such that each symbol in pointer(p) appears in t, and (3) for any variable x 2 X , o(t; x) = 1 if and only if o(f1; x) + o(f2; x) + + o(fn; x) = 1. For example, the rule in Fig. 1 is primitive. The term pGRR denotes the set of all primitive rules over ⟨ ; ; [ X ⟩. For a rule =`p(t) q1(f1); q2(f2); : : : ; qn(fn)', let h( ) = fpg and b( ) = fq1; q2; : : : ; qng. A nite set of primitive rules is called a primitive formal ordered tree system program (pFOTS program) if has only one predicate symbol in . We give a pFOTS program OT [ f g in Fig. 1 as an example. For an atom p(g), a rule A B1; : : : ; Bn and a substitution , we de ne p(g) = p(g ) and (A B1; : : : ; Bn) = A B1 ; : : : ; Bn . Let be a pFOTS program. The relation ⊢ C for a rule C is inductively de ned as follows. (1) If C 2 , then ⊢ C. (2) If ⊢ C, then ⊢ C for any substitution . (3) If ⊢ A B1; : : : ; Bi; : : : ; Bn and ⊢ Bi C1; : : : ; Cm, then ⊢ A B1; : : : ; Bi 1; C1; : : : ; Cm; Bi+1; : : : ; Bn. For a pFOTS program and its predicate symbol p in , L( ; p) denotes the subset fg 2 OT j ⊢ p(g) g of OT . We say that a subset L OT is a pFOTS language if there exists a pFOTS program and its predicate symbol p such that L = L( ; p) holds. In Fig. 1, we give the pFOTS language L( OT [ f g; r) de ned by pFOTS program OT [ f g. Algorithm 1 LEARNING pFOTS Input: A tree t 2 OT.

Output: A rule 2 pGRR( ; r) such that L( [ f g; r) = L( [ f g; q).

Assumption: A pFOTS is known as BK. Predicate symbols r and q are in 1: repeat 2: for all f 2 ft′ 2 OT j t ▷ t′g do 3: if MQ(f ) = yes then t := f ; break; end if 4: end for 5: until t does not change; 6: f := t; n := 0; 7: for all edges ef in f do 8: Let be an edge label that is different from the edge label of ef ; 9: Let f ′ be a tree obtained from f by replacing ef with an edge labeled with ; 10: if MQ(f ′) = yes then 11: n := n + 1; 12: Replace the edge et of t that corresponds to ef with a new variable hn; 13: end if 14: end for 15: output := r(t) p(h1); p(h2); : : : ; p(hn); 16: // We regard variable hi as a primitive term tree pattern consisting of hi (i = 1; : : : ; n). n ( ) and the target 3

Learning of pFOTS via Queries

For a pFOTS program , h( ) = ∪ 2 h( ), b( ) = ∪ 2 b( ) and ( ) = h( ) [ b( ). For a prbe(di)cate syh(mb)o.lWre2assunme (tha)t, oleutrplGeRarRn(in g;ra)lgboeritthhemsektnoowfsalal prxiemditpivFeOrTuSlesprogsruacmh th,awthichh( i)s =refferrrgedantdo as BK, in advance as background knowledge. Then, we consider the learnability of the class fL( [ f g; r) j 2 pGRR( ; r)g via queries, where r 2 n ( ). The rule denotes the rule in pGRR( ; q) to be identi ed, which is called the target, where q 2 n ( ). Any tree in L( [ f g; q) is said to be a positive example. In the query learning model [ 1 ], a learning algorithm can access oracles that will answer queries about the target . We consider the following three queries (let r; q 2 n ( )). Membership query(MQ): The input is a tree t 2 OT . The output is yes if t 2 L( [ f g; r); otherwise, no. Restricted subset query(rSQ): The input is a rule 2 pGRR( ; r). The output of a restricted subset query is yes if L( [ f g; r) L( [ f g; q); otherwise, no. Equivalence query(EQ): The input is a rule in pGRR( ; r). The output of an equivalence query is yes if L( [ f g; r) = L( [ f g; q): otherwise, a tree, called a counterexample, in (L( [ f g; r) [ L( [ f g; q)) n (L( [ f g; r) \ L( [ f g; q)). A learning algorithm A is said to exactly identify the target 2 pGRR( ; q) if A outputs a rule 2 pGRR( ; r) such that r 2 n ( ) and L( [ f g; r) = L( [ f g; q). In the case that a target is a nite subset of pGRR( ; r), the above queries and exact identi cations are de ned in a similar way.

Let be a pFOTS program with ( ) = fpg and F ( ) denote the set of all facts in . For a predicate symbol r 2 n fpg and a rule = `p(s) p(s1); : : : ; p(sn)' 2 , let T rrp( ) = `r(s) p(s1); : : : ; p(sn)'. Let f; g be trees and e = (u; v) an edge in f with φf (e) 2 . Let f ′ be the term tree pattern obtained from f by changing the edge label φf (e) of e to a variable label x 2 X , i.e., φf′ (e) = x. Then, we write g ▷e f if there exists a substitution = fx := [t; t]g such that the following three conditions hold: (1) f ′ is isomorphic to g, (2) t is in ∪ 2W L(F ( ) [ fT rrp( )g; r), where W = n F ( ), and (3) t is the pair (u; v) of two nodes u; v of t with ( t(u); t(v)) = pointer(p). Moreover, we write g ▷ f if there exists an edge e in f such that g ▷e f holds. By using Algorithm 1, denoted as LEARNING pFOTS, we have the following theorem. Theorem 1. Let j j 2, be a xed pFOTS program that is background knowledge with j ( )j = 1, and a target primitive rule in pGRR( ; r), where r is a predicate symbol in n ( ). A primitive rule 2 pGRR( ; r′) satisfying L( [ f g; r′) = L( [ f g; r) is exactly identi ed using O(n2) membership queries and one positive example T 2 L( [ f g; r), where n is the number of nodes in T .

A pFOTS program satis es PSI condition if for each predicate symbol p 2 ( ), there exist two edge labels a1; a2 2 (a1 ̸= a2) such that P (a1) \ P (a2) = fpg, where P (a) = fq 2 ( ) j `q(T ) ' 2 s.t. T has the edge label ag. Given pFOTS program 1; : : : ; K (K 1) satis es PSI condition as background knowledge, we have the following corollary from Theorem 1.

BK: OT,

Target: rule j j < 1 Corollary 1. Let 1; : : : ; K be xed pFOTS programs such that ∪1 j K j satis es PSI condition, j j 2, j ( i)j = 1 for any i (1 i K) and ( i) \ ( j ) = ∅ for any i; j (1 i < j K). Let be a target primitive rule in pGRR( 1 [ [ K ; r), where r is a predicate symbol in n ∪1 i K ( i). A primitive rule 2 pGRR( 1 [ [ K ; r′) satisfying L( 1 [ [ K [ f g; r′) = L( 1 [ [ K [ f g; r) is exactly identi ed using one positive example T 2 L( 1 [ [ K [ f g; r) and O(n2) membership queries, where n is the number of nodes in T .

Next, given a pFOTS program having multiple predicate symbols and satisfying PSI condition as background knowledge, from Theorem 1, we have the following corollary.

Corollary 2. Let be a xed pFOTS program such that satis es PSI condition, j j 2 and j ( )j 2. Let be a target primitive rule in pGRR( ; r) with r 2 n ( ). A primitive rule in pGRR( ; r′) satisfying L( [ f g; r′) = L( [ f g; r) is exactly identi ed using one positive example T 2 L( [ f g; r) and O(n2) membership queries, where n is the number of nodes in T .

We can extend pFOTS programs to deal with the class of ordered tree languages in case of j j = 1 by using the special atom deciding whether or not the edge label is in . Therefore, it is easy to see that Theorem 1 and Corollaries 1 and 2 hold if j j = 1.

We summarize related work and the results discussed in this paper in Table 1. The terms PII and ILPU stand for the learning models \polynomial-time inductive inference from positive data" and \identi cation in the limit by polynomial-time update from positive data," respectively. The term OP means that the learning algorithm in the result requires exactly one positive example. We say that a pFOTS program satis es the Condition 1 if has the 1- nite context property with Chomsky normal form and bounded treewidth property [ 8 ]. 4

Conclusions

We have introduced a primitive formal ordered tree system (pFOTS) as a formal system de ning the ordered tree languages based on FGS [ 10 ]. For a xed pFOTS program as background knowledge, we have shown the exact learnability of tree languages de ned using pFOTS programs [ f g such that is a target primitive graph rewriting rule by using one positive example and a polynomial number of membership queries. For future work, for a xed pFOTS program as background knowledge that has only one edge label, we will consider the exact learnability of tree languages de ned by pFOTS programs using one positive example and membership queries, and tree languages de ned by pFOTS programs without background knowledge using other queries such as equivalence queries, restricted subset queries, and predicate membership queries (see [ 1, 7 ]). We would like to thank the anonymous referees for their helpful comments. This study was partially supported by Grant-in-Aid for Scienti c Research (C) (Grant Numbers JP15K00312, JP15K00313, JP17K00321) from Japan Society for the Promotion of Science (JSPS).

References

1. Angluin , D. : Queries and concept learning . Machine Learning 2 ( 4 ), 319 { 342 ( 1988 )

2. Clark , A. , Yoshinaka , R.: Distributional learning of context-free and multiple context-free grammars . In: Topics in Grammatical Inference , pp. 143 { 172 . Springer-Verlag Berlin Heidelberg ( 2016 )

3. Matsumoto , S. , Hayashi , Y. , Shoudai , T. : Polynomial time inductive inference of regular term tree languages from positive data . Proc. ALT-97 , Springer-Verlag, LNAI 1316 pp. 212 { 227 ( 1997 )

4. Matsumoto , S. , Shoudai , T. , Uchida , T. , Miyahara , T. , Suzuki , Y. : Learning of nite unions of tree patterns with internal structured variables from queries . IEICE Trans. Inf. & Syst. E91-D(2) , 222 { 230 ( 2008 )

5. Okada , R. , Matsumoto , S. , Uchida , T. , Suzuki , Y. , Shoudai , T. : Exact learning of nite unions of graph patterns from queries . In: Proc. ALT 2007 , LNAI 4754 . pp. 298 { 312 . Springer ( 2007 )

6. Rozenberg , G . (ed.): Handbook of Graph Grammars and Computing by Graph Transformation: Volume I. Foundations . World Scienti c Publishing Co., Inc., River Edge , NJ, USA ( 1997 )

7. Sakamoto , H. , Hirata , K. , Arimura , H.: Learning elementary formal systems with queries . Theoretical Computer Science 298 ( 1 ), 21 { 50 ( 2003 )

8. Shoudai , T. , Matsumoto , S. , Suzuki , Y. : Distributional learning of regular formal graph system of bounded degree . In: Proc. ILP 2016 , LNAI 10326 . pp. 68 { 80 . Springer ( 2016 )

9. Suzuki , Y. , Shoudai , T. , Uchida , T. , Miyahara , T. : Ordered term tree languages which are polynomial time inductively inferable from positive data . Theoretical Computer Science 350 ( 1 ), 63 { 90 ( 2006 )

10. Uchida , T. , Shoudai , T. , Miyano , S.: Parallel algorithms for refutation tree problem on formal graph systems . IEICE Trans. Inf. & Syst. E78-D(2) , 99 { 112 ( 1995 )