Polynomial Time Inductive Inference of Ordered Tree Patterns with Internal Structured Variables from Positive Data

Yusuke Suzuki, Ryuta Akanuma, Takayoshi Shoudai, Tetsuhiro Miyahara, Tomoyuki UchidaCOLT 2002 · DOI

TL;DR

This paper introduces "term trees," a powerful new representation for structured data patterns that can capture complex relationships beyond standard tree patterns. The authors develop polynomial-time algorithms for key problems related to these term trees, demonstrating that they can be learned efficiently from positive examples, a significant step for knowledge discovery in structured data.

What Problem Does This Paper Address?

The explosion of structured data, particularly from sources like the web (HTML/XML), presents a challenge for traditional data mining and machine learning techniques. These data formats are often represented as rooted trees with ordered children and edge labels. Discovering meaningful patterns within this data is crucial for knowledge extraction. Existing methods for representing tree patterns, like standard tree patterns, are limited in their expressiveness. They struggle to represent patterns with nested, structured variables. This paper addresses this limitation by proposing "term trees," a more expressive model that allows for internal structured variables, and then tackles the problem of efficiently learning these patterns from data.

Methods

The core contribution of this paper lies in the introduction of term trees and the development of polynomial-time algorithms for two fundamental problems:

  • Membership Problem: Given a term tree t and a data tree T, determine if T belongs to the language generated by t (i.e., if T can be formed by substituting arbitrary trees for the variables in t). The paper proposes a polynomial-time algorithm called Matching for this problem. This algorithm works by attaching "correspondence-sets" to vertices of the data tree, which represent potential matches for sub-term trees.
  • Minimal Language Problem (MINL): Given a set of data trees S, find a term tree t such that its language L(t) is the smallest possible among all term tree languages that contain all trees in S. This is essentially finding the most specific pattern that explains the given data. The paper presents two algorithms for this:
  • MINL1: For a specific class of term trees (OTTL^1,K), this algorithm uses a candidate tree list derived from the input trees and iteratively refines a term tree through operations like "Variable-Branching," "Adding-Ending-Part," "Edge-Replacing," and "Edge-Extension."
    • MINL*: For a broader class of term trees (OTTL*), this algorithm uses "Variable-Extension" to increase the complexity of the term tree and then "Edge-Replacing" to simplify it by converting variables to edges.

The paper then leverages these algorithms to prove that two classes of term trees (OTTL^1,K and OTTL*) are polynomial time inductively inferable from positive data. This means an "inductive inference machine" can learn these patterns efficiently by observing only positive examples.

Datasets

The paper does not introduce or use specific named datasets for training or evaluation. Instead, it focuses on theoretical aspects of inductive inference. The "datasets" are abstract sets of trees, denoted by S, which are assumed to be drawn from OTA (the set of all ground term trees with edge labels from A).

Key Insights and Ideas

  • Expressiveness of Term Trees: The introduction of "internal structured variables" in term trees significantly enhances their expressive power compared to standard tree patterns. This allows for the representation of more complex and nested patterns commonly found in real-world structured data.
  • Polynomial-Time Learnability: The paper demonstrates that despite the increased expressiveness of term trees, they can still be learned efficiently (in polynomial time) from positive examples. This is a crucial result for practical applications in data mining and knowledge discovery.
  • Bridging Theory and Practice: By developing polynomial-time algorithms for membership and minimal language problems, the paper provides a theoretical foundation for practical inductive learning of structured patterns.
  • The Power of Refinement Operators: The algorithms for the minimal language problem rely on operations that can be seen as refinement operators, which are standard tools in inductive inference for systematically exploring the hypothesis space.

Key Results

  • The paper establishes that two classes of term tree languages, OTTL^1,K and OTTL*, are polynomial time inductively inferable from positive data.
  • Polynomial-time algorithms are presented for the Membership Problem and the Minimal Language Problem for these classes of term trees.
  • The paper provides a formal definition of term trees and their languages, laying the groundwork for theoretical analysis.

Limitations and Future Work

  • Open Question for OTTL^L,K with L > 2: The paper states that for L > 2, it is still an open question whether OTTL^L,K is polynomial time inductively inferable from positive data.
  • Specific Classes of Term Trees: The algorithms are developed for specific classes of term trees (OTTL^1,K and OTTL*) defined by constraints on variable size and path length. Extending these results to more general classes of term trees might be challenging.
  • Practical Implementation and Evaluation: While the paper presents theoretical algorithms, it does not include empirical evaluations on real-world datasets. Future work could involve implementing these algorithms and testing their performance on actual structured data.
  • Generalization to Unordered Trees: The paper focuses on ordered trees. Extending the framework to unordered trees (as mentioned in related work) could be a direction for future research.

Summary updated

BibTeX
@inproceedings{suzuki2002polynomial,
  author = {Yusuke Suzuki and Ryuta Akanuma and Takayoshi Shoudai and Tetsuhiro Miyahara and Tomoyuki Uchida},
  title = {{Polynomial Time Inductive Inference of Ordered Tree Patterns with Internal Structured Variables from Positive Data}},
  booktitle = {Conference on Learning Theory},
  year = {2002},
  doi = {10.1007/3-540-45435-7\_12},
}
Figure