Pruning improves heuristic search for cost-sensitive learning Public Deposited

http://ir.library.oregonstate.edu/concern/technical_reports/0p0968123

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • This paper addresses cost-sensitive classification in the setting where there are costs for measuring each attribute as well as costs for misclassification errors. We show how to formulate this as a Markov Decision Process in which the transition model is learned from the training data. Specifically we assume a set of training examples in which all attributes and the true class have been measured. We describe a learning algorithm based on the AO* heuristic search procedure that searches for the classification policy with minimum expected cost. We provide an admissible heuristic for AO* that substantially reduces the number of nodes that need to be expanded particularly when attribute measurement costs are high. To further prune the search space we introduce a statistical pruning heuristic based on the principle that if the values of two policies are statistically indistinguishable on the training data then we can prune one of the policies from the AO* search space. Experiments with realistic and synthetic data demonstrate that these heuristics can substantially reduce the memory needed for AO* search without significantly affecting the quality of the learned policy. Hence these heuristics expand the range of cost-sensitive learning problems for which AO* is feasible.
Resource Type
Date Available
Date Issued
Series
Keyword
Subject
Rights Statement
Funding Statement (additional comments about funding)
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2012-06-04T17:58:01Z (GMT). No. of bitstreams: 1 Pruning improves heuristic search for cost-sensitive learning.pdf: 209947 bytes, checksum: ce9e944e33712aec0e8c41fedc2f4416 (MD5) Previous issue date: 2004
  • description.provenance : Submitted by Laura Wilson (laura.wilson@oregonstate.edu) on 2012-06-04T17:56:58Z No. of bitstreams: 1 Pruning improves heuristic search for cost-sensitive learning.pdf: 209947 bytes, checksum: ce9e944e33712aec0e8c41fedc2f4416 (MD5)
  • description.provenance : Approved for entry into archive by Laura Wilson(laura.wilson@oregonstate.edu) on 2012-06-04T17:58:01Z (GMT) No. of bitstreams: 1 Pruning improves heuristic search for cost-sensitive learning.pdf: 209947 bytes, checksum: ce9e944e33712aec0e8c41fedc2f4416 (MD5)

Relationships

In Administrative Set:
Last modified: 07/18/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items