Date of Graduation

2008

Document Type

Thesis

Degree Type

MS

Committee Chair

Tim Menzies

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.

Download

Share

COinS