Learning ranking functions for efficient search Public Deposited

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

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • This dissertation explores algorithms for learning ranking functions to efficiently solve search problems, with application to automated planning. Specifically, we consider the frameworks of beam search, greedy search, and randomized search, which all aim to maintain tractability at the cost of not guaranteeing completeness nor optimality. Our learning objective for each of these frameworks is to induce a linear ranking function for guiding the search that performs nearly as well as unconstrained search, hence gaining computational efficiency without seriously sacrificing optimality. We first investigate the problem of learning ranking functions to guide beam search, with a focus on learning feature weights given a set of features. We present a theoretical analysis of the problem's computational complexity that identifies the core efficient and hard subclasses. In addition we study online learning algorithms for the problem and analyze their convergence properties. The algorithms are applied to automated planning, showing that our approach is often able to outperform an existing state-of-the-art planning heuristic as well as a recent approach to learning such heuristics. Next, we study the problem of automatically learning both features and weights to guide greedy search. We present a new iterative learning algorithm based on RankBoost, an efficient boosting algorithm for ranking and demonstrate strong empirical results in the domain of automated planning. Finally, we consider the problem of learning randomized policies for guiding randomized greedy search with restarts. We pose this problem in the framework of reinforcement learning and investigate policy-gradient algorithms for learning both features and weights. The results show that in a number of domains this approach is significantly better than those obtained for deterministic greedy search.
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
Keyword
Subject
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2010-08-12T16:07:56Z (GMT) No. of bitstreams: 1 XuYuehua2010.pdf: 666585 bytes, checksum: a3ae94b2c7ac91a63872219eb545d4ec (MD5)
  • description.provenance : Made available in DSpace on 2010-08-12T16:07:56Z (GMT). No. of bitstreams: 1 XuYuehua2010.pdf: 666585 bytes, checksum: a3ae94b2c7ac91a63872219eb545d4ec (MD5)
  • description.provenance : Approved for entry into archive by Julie Kurtz(julie.kurtz@oregonstate.edu) on 2010-08-11T18:54:32Z (GMT) No. of bitstreams: 1 XuYuehua2010.pdf: 666585 bytes, checksum: a3ae94b2c7ac91a63872219eb545d4ec (MD5)
  • description.provenance : Submitted by Yuehua Xu (xuy@onid.orst.edu) on 2010-08-09T21:40:17Z No. of bitstreams: 1 XuYuehua2010.pdf: 666585 bytes, checksum: a3ae94b2c7ac91a63872219eb545d4ec (MD5)

Relationships

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

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items