Exact learning of tree patterns Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/794080272

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Tree patterns are natural candidates for representing rules and hypotheses in many tasks such as information extraction and symbolic mathematics. A tree pattern is a tree with labeled nodes where some of the leaves may be labeled with variables, whereas a tree instance has no variables. A tree pattern matches an instance if there is a consistent substitution for the variables that allows a mapping of subtrees to matching subtrees of the instance. A finite union of tree patterns is called a forest. In this thesis, we study the learnability of tree patterns from queries when the subtrees are ordered or unordered. The learnability is determined by the semantics of matching as defined by the types of mappings from the pattern subtrees to the instance subtrees. Angluin's exact supervised learning model is used, in which the learner has to exactly identify the target from a polynomial number of queries and in polynomial time. We first show that ordered tree patterns and forests, with an infinite label alphabet (or equivalent condition), are learnable from equivalence and membership queries. Ordered forests and similar classes with bounded alphabet and branching factor are shown to be as hard to learn as DNF. We next show that unordered tree patterns and forests are not exactly learnable from equivalence and subset queries when the mapping between subtrees is one-to-one onto, regardless of the computational power of the learner. On the other hand, tree and forest patterns are learnable from equivalence and membership queries for the one-to-one into mapping. Finally, we connect the problem of learning tree patterns to inductive logic programming by describing a class of tree patterns called "clausal trees" that includes non-recursive single-predicate Horn clauses and show that this class is learnable from equivalence and membership queries.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Language
Digitization Specifications
  • PDF derivative scanned at 300 ppi (256 B+W), using Capture Perfect 3.0.82, on a Canon DR-9080C. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-06-11T21:40:17Z (GMT) No. of bitstreams: 1 Amoth_Thomas_R_2002.pdf: 1212632 bytes, checksum: a8c4e5ae82298db72fce453a3f49d124 (MD5)
  • description.provenance : Submitted by Anna Opoien (aoscanner@gmail.com) on 2009-06-11T19:53:24Z No. of bitstreams: 1 Amoth_Thomas_R_2002.pdf: 1212632 bytes, checksum: a8c4e5ae82298db72fce453a3f49d124 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2009-06-11T21:38:26Z (GMT) No. of bitstreams: 1 Amoth_Thomas_R_2002.pdf: 1212632 bytes, checksum: a8c4e5ae82298db72fce453a3f49d124 (MD5)
  • description.provenance : Made available in DSpace on 2009-06-11T21:40:17Z (GMT). No. of bitstreams: 1 Amoth_Thomas_R_2002.pdf: 1212632 bytes, checksum: a8c4e5ae82298db72fce453a3f49d124 (MD5)

Relationships

In Administrative Set:
Last modified: 08/01/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items