We present a method to determine when to stop the evaluation of a decision-making process. The method determines to stop the evaluation process when the result of the full evaluation is obvious. This trait is highly desirable for margin-based Machine Learning algorithms where a classifier traditionally evaluates all the features for every example. However, some examples are easier to classify than others, a phenomenon which is characterized by the event when most of the features agree on the class of an example. By stopping the feature evaluation when encountering an easy to classify example, a margin-based Machine Learning algorithm can achieve substantial reduction in running times.
To determine when to stop the feature evaluation, we develop a set of novel sequential tests, the Sequential Thresholded Sum Tests (STST). These tests stop the partial evaluation of the sum when the result of the full summation is guaranteed with high probability. By making different assumptions on the data and the features different tests arise. In general we look at the feature evaluation process as a random walk and apply different Brownian motion early stopping inequalities to determine when to stop the walk. From these inequalities we derive a family of stopping thresholds for sequential feature evaluations under different assumptions.
We demonstrate the effectiveness of the different STST by speeding up several Online Learning algorithms on synthetic and real data.
|School Location:||United States -- New York|
|Source:||DAI-B 72/06, Dissertation Abstracts International|
|Subjects:||Statistics, Artificial intelligence, Computer science|
|Keywords:||Attentive learning, Focus of attention, Rapid learning, Sequential threshold sum tests|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be