23-04-2012, 11:56 AM
Efficient Heuristic Hypothesis Ranking
10.1.1.100.6749.pdf (Size: 1.39 MB / Downloads: 36)
Introduction
In many applications, the cost of information can be quite high, imposing a requirement
that learning algorithms glean as much usable information as possible with a minimum of
data. For example:
0 Data may be scarce, making learning the most possible from limited training data
key.
0 In speedup learning, minimizing processiug time is critical. Here, reducing the number
of necessary training examples is key since the expense of processing each example
can be significant (Tadepalli, 1992).
0 In decision tree learning, the cost of using all available training examples when evaluating
potential attributes for partitioning can be computationallye xpensive (Musick,
Catlett, & Russell, 1993).
0 In evaluating medical treatment policies, acquiring additional training examples might
imply that human subjects are exposed to an experimental treatment for a longer
period than is necessary.
Hypothesis Ranking Problems
Hypothesis ranking problems are an abstracctl ass of learning problems wherea n algorithm
is given a set of hypotheses to rank. The rankingde sired is that which orders the hypotheses
by their expected utility, which is determined by the hypothesis' underlying probability
distribution. These expected utilities are unknown to the algorithm and must be estimated
from the training data.
Empirical Performance Evaluation
We now turn toe mpirical evaluationo f the hypothesis ranking techniques onb oth synthetic
and real-world datasets. This evaluation serves three purposes. First, it demonstrates that
the techniques perform as predicted (in termosf bounding the probabilityof incorrect selection
or expected loss). Second, it validates the performance of the techniques as compared
to standard algorithms from the statistical literature. Third, the evaluation demonstrates
the robustness of the new approaches to real-world hypothesis ranking problems.
Evaluation on Synthetic Datasets
Evaluation on synthetic datais used to show that: (1) the techniques correctly bound probability
of incorrect ranking and expecteldo ss as predicted when the underlying assumptions
are valid even when the underlying utility distributions are inherently hard to rank lo, and
(2) that the PAC techniques compare favorably to the algorithm of Turnbull and Weiss in
a wide variety of circumstances.
Discussion and Conclusions
There are a number of areas of related work. First, there has beer1 considerable arlalysis of
hypothesis selection problems. Selection problems have been formalized using a Bayesian
framework (Moore & Lee, 1994; Rivest & Sloan, 1988) that does not require an initial
sample, but uses a rigorous encoding of prior knowledge. Howard (Howard, 1970) also
details a Bayesian framework for analyzing learning cost for selection problems. If one
uses a hypothesis selection framework for ranking, allocation of pairwise errors can be
performed rationally (Gratch et al., 1994). Reinforcement learning work (Kaelbling, 1993)
with immediate feedback can also be viewed as a hypothesis selection problem.