Learning Decision Lists over Tree Patterns and Its Application
Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Machine Learning. Pages 995-1000.
© 1993 International Joint Conferences on Artificial Intelligence
Abstract
This paper introduces a new concept , a decision tree (or list) over tree patterns, which is a natural extension of a decision tree (or decision list) , for dealing with tree structured objects. The learnability of this class is studied within the framework of the Probably Approximately Correct learning model and the Identification in the Limit model. It is found that the class k-node-DLRTP, a subclass of decision lists over regular tree patterns, is not polynomial time PAC learnable if NP:fRP , but that the class knode-DLRTP(m), a subclass ofk-node-DLRTP where the number of variables in each tree pattern is bounded by m, is polynomial time PAC learnable. We also show that the class of decision lists over regular tree patterns is polynomial time inferable in the limit. Then we propose a more practical learning algorithm which employs heuristics based on an information theoretical evaluation function. This algorithm is applied to learning control strategies of rules in various domains , and its effectiveness is shown.
- [Quinlan, 1986] J. R. Quinlan. Induction of Decision Trees . Machine Learning, 1:81-106, 1986.
- [Quinlan and Rivest, 1989] J. R. Quinlan and R. L. Rivest. Inferring Decision Trees Using Minimum De- scription Length Principle. Information and Compu- tation, 80:227-248, 1989.
- [Valiant, 1984] L. G. Valiant. A Theory of Learnable. Comm. Assoc. Computing Machinery, 27:1134-1142, 1984.
- [Gold, 1967] E. M. Gold. Language Identification in the Limit. Information and Control, 10:447-474, 1967.
- [Plotkin, 1970] G. D. Plotkin. A Note on Inductive Gen- eralization. Machine Intelligence, 5:153-163, 1970.
- [Arimura et al., 1970] H. Arimura, T . Shinohara, and S. Otsuki. Polynomial Time Inference of Unions of Tree Pattern Languages. In Proceedings of the Sec- ond Workshop on Algorithmic Learning Theory, pages 105-114, 1991.
- [Rivest, 1987] R. L. Rivest. Learning Decision Lists. Ma- chine Learning, 2:229-246 , 1987.
- [Natarajan, 1989] B. K. Natarajan. On Learning Sets and Functions. Machine Learning, 4:67-97, 1989.
- [Kobayashi, 1993] S. Kobayashi. Explanation Based Learning: Extracting Corrunon Structures from Mul- tiple Training Examples PH.D. Th., Dept. of Aero- nautics, Tokyo University, 1993, in Japanese.
- [Arikawa et al., 1992] S. Arikawa, S. Kuhara, S. Miyano, Y. Mukouchi, A. Shinohara, and T. Shinohara. A Ma- chine Discovery from Amino Acid Sequences by Deci- sion Trees over Regular Patterns. In Proceedings of International Conference on Fifth Generation Com- puter Systems, pages 618-625, 1992.
- [Hyafil and Rivest, 1976] L. Hyafil and R. L. Rivest. Constructing Optimal Binary Decision Trees is NP- Complete. Information Processing Letters, 5:15-17, 1976.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Learning has long attracted the attention of many re searchers in the artificial intelligence community. It has also been expected to be one of the methods for over coming the knowledge acquisition bottleneck of expert systems. Learning from examples is the best studied of all proposed learning schemata, because giving ex amples of a concept is easier for humans than giving the precise definition of it. Most of past research re duces learning problems to search problems of target concepts in the hypothesis space with refinement oper ators. On the other hand, Quinlan's innovative work on learning decision trees shows another top-down ap proach for learning[Quinlan, 1986] . His method depends on an information theoretical evaluation function to se lect good attributes for decision nodes. This technique has been applied to various domains for classifying ob jects which have many attributes.
This paper introduces the new concept of a decision tree over tree patterns. This is a natural extension of a decision tree that deals with tree structured objects.
One of the most interesting application areas of this work is inference control. We can use decision trees over tree patterns as control structures for applying appro priate rules for selected subgoals in the SLD resolution process .
In section 2, we will define the concept of decision trees over tree patterns, and in section 3, we show theoretical results on learnability of this class. The learning mod els used in this paper are the Probably Approximately Correct (PAC in short) learning model and the Identifi cation in the Limit model, introduced by [Valiant, 1984] and [Gold, 1967] respectively. We prove that the class k node-DLRTP(m) is polynomial time PAC learnable and that the class DLRTP is polynomial time inferable in the limit. In section 4, we propose a practical learning algorithm for the class DLTP. In section 5, applications of the algorithm to inference control are shown.
2 Decision Trees and Decision Lists over Tree Patterns
Tree pattern language has been applied to many research areas such as term rewriting systems , logic program min~, etc. Its learnability has been well studied [Plotkin, 1970J[Arimura et a/., 1970]. In this section, we give the definition of decision trees over tree patterns which can be used for classification problems of tree structured ob jects.
Let E={a,b ,c, .. . } be a finite set of alphabets, rep resenting functors, associated with a mapping arity from E to nonnegative integers, and V={X,Y,Z, ... } be a countable set of alphabets disjoint from E whose ele ments are called variables.
Definition 1 A tree pattern on E U V is defined recur sively as follows.
- t is a tree pattern if t is a 0-ary functor (i.e. ar ity(t)=O).
- variables are tree patterns.
- an ordered tree J(t1 , .. . , tn) is a tree pattern iff is a n-ary functor, and ti , ... , tn are tree patterns.
We say a tree pattern t is regular , if all the variables in t occur at most once.
The length of a tree pattern t is the length of the ex pression representing it, and is denoted by I t 1- We sometimes regard a tree pattern as a tree structure. The height of a tree pattern t is the height when we regard t as a tree. The depth of a specified functor or variable in a tree pattern is defined in a similar manner. For exam ple, a tree pattern a(b(c(X,e(f)) ,g(h,i(Y)))j) is shown in Fig.l. The length and the height of this tree pattern are 27 and 4 respectively. The depth of the functor h is 3.

T P(E) denotes the set of all tree patterns on EUV. We define subTP as a function from TP(E) x {nonnegative integers} to TP(E) such that subTP(t, i) is a tree pattern of height i obtained from t by replacing the nodes of depth i with different variables. For instance, subTP(a(b(c(X,e(f)) ,g(h,i(Y)))j) ,2) = a(b(Z,W)j) .
A substitution is a homomorphism 8 from T P(E) to T P(E) such that 8(!) = f for any 0-ary functor f E E. We write p ~' q if there exists a substitution 8 such that P = 8(q).
Definition 2 A tree pattern p defines the following lan guage.
Let C be a set of alphabets representing classes of objects. A decision tree over (regular) tree patterns is a binary tree whose internal nodes, called decision nodes, are labeled by (regular) tree patterns and whose leaves are labeled by elements of C. The label of the node n is denoted by label(n) .
A decision tree over tree patterns dl defines the func tion funcdl from T P(E) to C. When we are given a tree pattern t, then a unique path from the root to a leaf is determined as follows. If the current node of the path is labelled by the tree pattern p, then test for t ~' p. If the test succeeds, select the left child, otherwise, select the right child, as the next node of the path, respec tively. The label of the leaf of the path is the value of the tree pattern t by the function funcdl · For the deci sion tree dl defined in Fig.2, the values of funcdl(a(b,c)) and funcdl(b(a(c),e(Z))) are c2 and c3 respectively.
A decision list over {regular) tree patterns is a decision tree over (regular) tree patterns whose decision nodes all have leaves as left children, and is written as a sequence of tuples,
where tp; and cp;(1 ~ i ~ r) are elements of TP(E) and C respectively. X is a tree pattern composed of only one variable X itself. Each tp; represents the label of the ith decision node from the root, and c; represents its left child's label. This is a natural extension of decision

/"'
lists[Rivest , 1987] over tree patterns. The decision tree in Fig.2 is also a decision list and is written;
Decision lists over tree patterns can be used as control structures to apply appropriate rules for selected sub goals in SLD resolution. For this purpose, we regard selected subgoals as tree patterns to be classified and applied rules as classes.
For example, let us consider the following rules written in Prolog.
Although del(X,Y,Z) is intended to mean that Z is the list obtained from the list X by removing all Y's in X, this program does not work correctly. If we control the inference as shown in Fig.3, then this program will work correctly.

In section 5, we show experiments of learning such control strategies as decision lists over tree patterns from correct traces of the given program.
3 Theoretical Results
We define the following classes of functions.
DLTP(DLRTP) the class of functions which can be defined by decision lists over (regular) tree patterns.
k-node-DTTP the class of functions which can be de fined by decision trees over tree patterns whose number of decision nodes is bounded by k.
k-node-DLTP(k-node-DLRTP)
the subclass of DLTP(DLRTP) where the number of tuples in decision lists is bounded by k + 1.
- DL-k,m-RTP the subclass of DLRTP where the height of tree patterns and the arity of functors are bounded by k and m respectively.
- k-node-DLRTP(m) the subclass of k-node-DLRTP where the nurriber of variables in each regular tree pattern is bounded by m.
3.1 Relationship between Decision Trees and Decision Lists
Theorem 1 k-node-DTTP = k-node-DLTP Proof
It is straightforward to show that k-node-DTTP~k node-DLTP. See [Kobayashi, 1993] in detail. 0
Because learning problems of decision lists are appar ently easier than those of decision trees, we hereafter restrict the attention to decision lists over tree patterns.
3.2 PAC Learnability
Probably Approximately Correct learning model intro duced by [Valiant, 1984] is a probabilistic learning frame work in that it only requires the learner to learn an ap proximate concept with high probability. This frame work was extended to learning functions from examples by [Natarajan, 1989] .
A sample of the function J : E* - f* is a tuple, (x E E*, f(x )). A sample set is a finite set of samples. A function which returns a sample of target function f by random selection according to an arbitrary probability distribution P over En unknown to the learner, is called an oracle for f, and written oracle/,P,n.
Definition 3 A PAC learning algorithm for a class F of functions is an algorithm A which satisfies the following conditions.
- A accepts t E (0, 1], 6 E (0, 1], and n (positive in teger)as inputs. t, 6, and n are called an error pa rameter, a confidence parameter, and a length pa rameter.
- A uses the oracle oracle/,P,n, where f is a target function.
- For any function f E F and for any distribution P over En, A outputs a function g E F such that P(! D..g) ~ t with probability at least ( 1 - 6). Here, D. denotes the symmetric difference.
Definition 4 If there exists a polynomial function p and a PAC learning algorithm A for F such that the time complexity of A is bounded by p(l, t,n), we say that the class F is polynomial time PAC learnable.
For any f E F and its sample set S, an algorithm which outputs a function consistent with S in polynomial time is called polynomial-time ordering. The projection fn of a function f E F on En and rn is a function from En to rn defined as follows.
The projection Fn ofF on En and rn is the class of func tions {/n : f E F} and the dimension ofF is defined by log I Fn 1. If the dimension of F is bounded by polyno mial function p(n), we say F is of polynomial dimension, where n is a length parameter.
Theorem 2 [Natarajan, 1989] IfF is of polynomial di mension and has a polynomial-time ordering, then F is polynomial time PAC learnable.
At first, we consider the next problem.
k-node-DLTP (k-node-DLRTP) Problem
Problem Instance A sample setS= {s1. .. . ,sn}
Query Is there a dltp Ek-node-DLTP(k-node-DLRTP) consistent with S?
Theorem 3 [Kobayashi, 1993] The k-node-DLTP (k node-DLRTP) problem is NP-Complete.
Proof
By transformation from the k-colorability problem. 0
Theorem 4 If NP#RP, k-node-DLTP (k-node-DLRT P) is not polynomial time PAC learnable.
Proof
Assume k-node-DLTP is polynomial time PAC learnable and let M be a polynomial time PAC learning algorithm of k-node-DLTP. We can construct a polynomial time randomized algorithm of the k-node-DLTP problem us ing M as follows . Let S be a sample set of the k-node DLTP problem, n = IS!, t =;;h. 6 =~~and P be the uniform distribution on S such that if (t , c) E S, then P(t) = : , otherwise, P(t) = 0. Then run M on these settings of parameters. If the output of M is consistent with S, then output 'yes', otherwise, output 'no'. This al gorithm is a randomized algorithm of the k-node-DLTP problem and runs in polynomial time. This contradicts the assumption NP#RP and Theorem 3. 0
Although k-node-DLRTP is not polynomial time PAC learnable if NP#RP, the next theorem shows that k node-DLRTP(m) is polynomial time PAC learnable.
Theorem 5 k-node-DLRTP(m) is polynomial time PAC learnable.
Proof
We denote the projection of k-node-DLRTP(m) on (E U V u {'(',')',' ,'})nand en by k-node-DLRTPn(m). Let tp be a regular tree pattern with I tp I> n. Then no tree pattern of length at most n is not an element of L(tp). Therefore, we need to consider only regular tree patterns tp such that I tp I~ n as labels of deci sion nodes. The number of such regular tree patterns is bounded by (I E I +4)n. Then we have lk-node DLRTPn(m)l~ (I E I +4)kn . I C lk+ 1 . Therefore the dimension ofk-node-DLRTP(m) is O(n). By Theorem2, it is sufficient to show that there exists a polynomial-time ordering for k-node-DLRTP(m).
The construction of the polynomial-time ordering is as follows.
Let S be a sample set. We need to consider only reg ular tree patterns tp such that 3(t, c) E S(t E L(tp)), as labels of decision nodes. Then, we can prove that the number of such regular tree patterns which have at most m variables is bounded by L(t,c)ES I t 1m. This shows that the number of possible decision lists consistent with Sis at most (L(t,c)ES It lm)k. I C lk+ 1 .
Let us consider the algorithm which enumerates such decision lists DL and checks whether DL is consistent with S or not. If a consistent decision list DL is found, the algorithm outputs DL. This construction gives us a polynomial-time ordering for k-node-DLRTP(m), since the consistency check can be done in polynomial time. This completes the proof. 0
This theorem is an extended result of Theorem 1 in [Arikawa et a/., 1992].
3.3 Polynomial Time Inference of DLRTP in the Limit
In this subsection, we prove that DLRTP is polynomial time inferable in the limit. The notion of identification in the limit is first introduced by [Gold, 1967].
An inference machine M is an algorithm that accepts a sample as an input and outputs a conjecture. Let 6 = s1 , s2, ... be a sample presentation. When M requests ith sample, M reads the sample Bi and adds the ith guess Yi to the sequence 91, 92, ... of guesses, where each Yi denotes a code of some function. We say that M on input 6 converges to g if there exists a positive integer n such that Vi~ n Yi =g.
An inference machine M is said to be consistent if it always outputs a conjecture Yi such that Yi is consistent with the sample set S = { s1. ... , si}. We say that M is conservative if it continues to produce the same guess while the guess is consistent with the sample. The class of functions F is said to be inferable by M, if, for any f E F and for any sample presentation 6, M on input 6 converges to g such that func 9 = f, where func 9 denotes the function calculated by g.
Definition 5 A class of functions F is polynomial time inferable in the limit, if there exists an inference ma chine M that infers F consistently and conservatively, and computes the guess Yi in polynomial time with re spect to II si II. where si = { W1' ... 'wi} and II si II denotes the size of si as an expression.
The next algorithm M1 is the inference machine of DL RTP which computes each guess Yi in polynomial time.
Inference Machine M1
input a sample presentation (t1. c1), (t2, c2) ...
output an infinite sequence 91. g2, ... of guesses. begin
go = none; S = t/J; i = 0; repeat i = i + 1; S = SU{(ti,Ci)}; if func 9 ;_ 1 is not consistent with (ti, Ci) then Yi = MinDLRTP(S); else Yi = Yi-1; output gi; forever end MinDLRTP(S) input a sample set S = {(t1, c1), ... , (tn, en)} output a decision list over tree patterns begin
L = null list; while( S :j:: ¢)do for each (ti, ci) E S do TPi = findMinTP((ti, Ci), S); end T Pj = minimum height tree pattern in {T Pi : 1~i~ISI}; add (T Pj, Cj) at the end of L; S = S- {(t,c) E S: t E L(TPi)}; end return L; end findMinTP((t,c),S) input a sample (t, c) and a sample set S output a tree pattern end n= height oft; for i=O to n+1 do p = subTP(t,i); if\f(t', c') E S(t' E L(p) --+ c' = c) then break; end return p;
Let maxH(d/) = max{height ofti : 1 ~ i ~ n} for a decision list dl = (tp1,c1), ... ,(tpn,cn), and let min MaxH(S) = min{maxH(d/): dl EDLRTP is consistent with S}. Then, the next lemma holds.
Lemma 1 MinDLRTP(S) returns the decision list dl = (tpl. cl), .. . , (tpn, Cn) consistent with S and such that minMaxH(S) = maxH(d/) .
Proof
It is obvious that MinDLRTP(S) terminates and out puts a decision list over tree patterns consistent with S. Therefore, minMaxH(S)~maxH(d/) holds. It is sufficient for us to show minMaxH(S)~maxH(d/). We prove this by induction of the number of tuples of d/, written rn.
In case of rn = 1, the claim holds obviously. We assume that the claim holds in case of rn = k - 1. Let us consider the case of rn = k and assume minMaxH(S)<maxH(d/). By the induction hypothesis, we have that maxH(dl')=minMaxH(S')~minMaxH(S) <maxH(d/), where dl' = (tp2, c2), .. . , (tpn, en), and S' = S- {(t, c) E S : t E L(tp1)}. Let h1 be the height oftp1. Then, we have h1 = maxH(d/).
There exists a decision list dl* = (tpi, ci), ... , (tp~, c~) consistent with S such that maxH(dl*)= minMaxH(S) by the definition of minMaxH. Let h2 be the height of tpi. Then, we have h1=maxH(d/)>minMaxH(S) ~h2.
For tpi, \f(t',c') E S(t' E L(tpi)--+ c' = ci) holds. Therefore, if we select (t, c) E S such that t E tpi, then \f(t', c') E S(t' E L(subT P(t, h2))--+ c' = ci) holds, since L(subTP(t, h2)) ~ L(tpi). This means minTP((t, c) ,S) returns a tree pattern whose height is less than or equal to h2( < h1) . This contradicts the fact that T Pj is the minimum height tree pattern in {TPi : 1 ~ i ~~ S 1}. So, we have maxH(d/)~minMaxH(S) in case of rn = k.
This completes the proof. 0
Theorem 6 The inference machine M1 infers DLRTP in polynomial time in the limit.
Proof
Let k = min{maxH(d/):d/ EDLRTP,Juncdl =!},where f is a target function, and m be the upper bound of arity. Then f EDL-k,m-RTP. By the above lemma, we can conclude that M1 converges to g such that f = func 9 , since IDL-k,m-RTPI is bounded by ((IE I +2)m"+l)!· I C I(IEI+2)m"+ 1 (i.e. finite).
The time required to compute a conjecture for each stage is bounded by O(p 2 · q 3 ), where pis the maximum size of the given samples and q is the number of them. This is a polynomial function with respect to the sample set size. D
For practical use, it is more appropriate to use M1 equipped with some heuristics as proposed in the next section, in order to obtain a decision list of short descrip tion length.
4 A Practical Learning Algorithm
In the previous section, we give the learnability results on some subclasses of DLTP. Although polynomial time learning algorithms are obtained, the results are limited to learning of decision lists on regular tree patterns. In this section, we give a practical algorithm for learning decision lists on tree patterns.
The minimum description length (MDL, in short) principle says that the hypothesis of minimum descrip tion length gives good prediction for unknown data. If we are given noise free data, it is necessary for us to ob tain a decision list over tree patterns of minimum length consistent with the given data. Unfortunately, Theory3 says that it is impossible to obtain such a description in polynomial time if N P # P.
In this section, we show a heuristic algorithm based on the information theoretical evaluation function. Al though finding the minimum cost decision tree consistent with the given data is NP-Cornplete[Hyafil and Rivest, 1976], [Quinlan, 1986] shows that the entropy function of information theory can play a significant part in the top down synthesis of small decision trees consistent with the ~iven data. Our method is an extension of [Quinlan, 1986J.
When S is a set of tree patterns, lgg(S) denotes the least generalization[Plotkin, 1970] of all elements in S .
We divide the given sample set S into its subsets sl, ... ,Sn, where n =I c I, 'v'(t,c)ES;(c=c;) for each class Cj E C, and u~=lS; = s. Let pat(S) = {t : (t , ;) E S}, lgg 1 (S) = lgg(pat(S)~, m;,i =I {t : t ~~ lgg (S;),(t,c) E Sj} I, and k; = I:j=l m;,j, then we can define an evaluation function /e as follows.
This evaluation function fe intuitively means the com plexity of the sample set {S1, ... , Sn}· We implement the learning algorithm of decision lists over tree patterns, called M2, which employs the following heuristics to ob tain a smaller decision list.
heuristic 1 if there exists i E {1, ... , n} such that 'v'j(i # j ::} 'v's E pat(Sj)·(s ~~ lgg 1 (S;))), then add (lgg 1 (S;), c;) to the decision list.
heuristic 2 otherwise, find the subset s: of S; for each i which minimalizes /e({Sl, ... ,S;-l,Si Si, S;+l, ... , Sn}) by the hill climbing method, select Sj from {S~, ... , S~} which gives the minimum value of fe, and add (lgg 1 (Sj),cj) to the decision list.
In the next section, this algorithm is applied to the learn ing of control strategies for selecting appropriate rules in the SLD resolution process.
5 Applications
In this section, we apply the algorithm described in the previous section to the inference control prob lem in robot planning domain. The setting is shown in Fig.4. The goal is to move the box b to the place g, and open all the doors. The operators are go-to-goal, go-to-left-door, go_to_righLdoor, go-to-box, go_through_door , open_door, pick_up, and put_down, which are all written as Horn clauses. The total number of problem instances in this domain is 1152.

One of the operators is shown bellow.
put-down:
op( ·I( b( X 1 ), r( X2 ),&1( X3 ), h&ve( b ) ,on( X5 ),open( X6, X 7, X8) ),(pu I ..down 10 P L] ):-
op( ·I( b( X 1 ),r( X2),&1( X3 ), h&ve( nil ),on( X3 ),open( X6,X 7, X8) ), 0 P L ) .
X in b(X) andY in r(Y) denote the rooms where the box and the robot exist respectively. X in on(X) and Y in at(Y) represent the positions of the box and the robot in the rooms. There are three positions in each room. have(X) means that the robot has X . X, Y, and Z in open( X , Y, Z) denote whether the 1st, 2nd and 3rd doors are open or not. In this setting, it seems rather difficult for a human to refine these rules so that all the problem instances can be solved with no backtracking. The aim of this experiment is to obtain a control strategy as a decision list which can solve almost all problem instances with no backtracking. The flow of the experiment is as follows .
for i=l, ... ,70 do
select i problem instances randomly and obtain traces of solutions from user.
extract ~selected subgoal,applied rule~ informa tion from the traces as samples for M2 and run M2 on them.
select 50 unknown problem instances randomly and test the learned control strategies on them.
end
The coverage of the learned control structure for un known problem instances are shown in Fig.5 The number of tuples of learned decision list in case ofi=70 is 35, and its coverage is 96 percent of the given unknown problem instances. This experiment says that M2 can produce good (i.e. small size of) hypotheses for unknown data. In the blocks world domain, M2 can learn a control struc ture for moving n-blocks from stack A to stack B with only one problem instance of moving 3-blocks. Another experiment from the circuit design domain shows similar good results of learning a general control structure from a few examples[Kobayashi, 1993].

6 Related Research
Learning decision trees is well studied. [Quinlan, 1986] proposes a method for top-down synthesis of decision trees from the given sample set based on the information theoretical evaluation function. [Quinlan and Rivest, 1989] uses MDL principle to guide the search of noise tol erant decision trees. The main difference between their works and our work is that test tree patterns are not ex plicitly predefined. The least generalization of samples is used for the construction of test tree patterns in the algorithm presented in section 4.
The learning problem of decision trees over regular patterns is studied in [Arikawa et al., 1992] and applied to transmembrane domains. Although our results are closely related to their work, the learnability result on the framework of identification in the limit is not studied in [Arikawa et al., 1992].
7 Conclusion
We propose the new concept of decision trees (or lists) over tree patterns. This is a natural extension of deci sion trees for dealing with tree structured objects. Then we show theoretical results on its learnability. Not only theoretical algorithms but the practical one is proposed based on the information theoretical evaluation function. Its application to inference control is experimented and good results are obtained in various domains such as robot planning, blocks world, circuit design, etc.
Although the proposed heuristics work well, there seems to be many other possibilities of heuristics for learning decision lists over tree patterns. Experimental comparison must be done in future works .
Acknowledgement
We would like to thank Tatsuya Akutsu and Iannis Zan nos for helpful discussions and comments.
@inproceedings{ijcai1993p137,
title = {Learning Decision Lists over Tree Patterns and Its Application},
author = {Kobayashi, Satoshi and Hori, Koichi and Ohsuga, Setsuo},
booktitle = {Proceedings of the Thirteenth International Joint Conference on
Artificial Intelligence, {IJCAI-93}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ruzena Bajcsy},
pages = {995--1000},
year = {1993},
note = {Machine Learning},
url = {https://ijcai.org/proceedings/1993/137},
}
TY - CPAPER TI - Learning Decision Lists over Tree Patterns and Its Application AU - Kobayashi, Satoshi AU - Hori, Koichi AU - Ohsuga, Setsuo T2 - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93 PB - International Joint Conferences on Artificial Intelligence PY - 1993 SP - 995 EP - 1000 UR - https://ijcai.org/proceedings/1993/137 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: