Back to search

West Virginia University

WHICH: A stochastic best-first search learner.

Abstract

dc:description.abstract

Rule-based learners search a version space of combinations of features. Starting at “false”, features can be added using disjunctions, conjunctions and negations which can combine to some top-most “true” node that covers all possible examples. A complete search of all possible combinations can be too slow, due to the size of the space, or too error prone, due to noise in the space. When complete search fails, stochastic search may be a useful alternative. For example, the TAR3 “treatment learner” is a stochastic rule learner that leaps around random parts of the version space. TAR favors the construction of tiny rules and, often, the rules generated by TAR are much smaller that the models generated by other methods, e.g. decision trees. Also, while older, and complete, versions of TAR did not scale well, the stochastic search of TAR3 was shown to scale linearly while providing nearly identical rules to TAR2. The inventors of TAR3 never explored alternate forms of stochastic rule learning. In this thesis we find the TAR3’s stochastic search is over−elaborate. Our new algorithm, called Which, is a stochastic best−first search that scales in the same linear manner as TAR3. WHICH returns the same rules as TAR3 but does so after generating 20%, or less, of the rules of TAR3. Further, WHICH shows that TAR3’s stochastic rule generation methods can be significantly generalized. While TAR3 uses a hard−wired rule assessment predicate, Which allows for arbitrary assessment predicates. Also, we have found a new evaluation criteria that out-performs the current state of the high−water mark in static code defect prediction. In summary, this research has repeated, simplified, and improved old results on stochastic rule generation. Which is simpler than TAR3, and can be easily customized to produce better learning systems that out−perform certain state−of−the−art results.

Degree

thesis:*
Name thesis:degree_name
MS
Level thesis:degree_level
Thesis

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Milton, Zachery A.
Contributors dc:contributor
  • Tim Menzies

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Milton, Zachery A.. WHICH: A stochastic best-first search learner.. Thesis thesis, https://doi.org/10.33915/etd.11090