A Relationship Between Classification Accuracy and Search Quality
Sharad Saxena, Paul E. Utgoff · 1988
A SELF ORGANIZING BEST FIRST SEARCH ALGORITHM FOR STATE SPACE PROBLEMS IS PRESENTED. THE ALGORITHM PERMITS THE EFFECTIVE USE OF AN IMPERFECT PREFERENCE PREDICATE. A PERFECT PREFERENCE PREDICATE, GIVEN ANY TWO STATES (A,B), RETURNS `TRUE'' IF AND ONLY IF STATE `A'' SHOULD BE EXPLORED BEFORE STATE `B''. THE ANALYSIS OF THE ALGORITHM GIVES A QUANTATIVE RELATIONSHIP BETWEEN THE CLASSIFICATION ACCURACY OF THE PREFERENCE PREDICATE, THE MAXIMUM ALLOWABLE SEARCH EFFORT, AND THE PROBABILITY OF OBTAINING A SOLUTION WITHIN THE ALLOWED SEARCH EFFORT. THE ALGORITHM, ITS ANALYSIS AND ITS APPLICATIONS IN THE DESIGN OF MACHINE LEARNING SYSTEMS, ARE ILLUSTRATED USING THE EIGHT PUZZLE PROBLEM.