Brown Bag Seminar - April 12, 2006
Speaker: Noam Goldberg
Affiliation: RUTCOR, Rutgers University
Title: Boosting Optimal Logical Patterns Using Noisy Data.
Time: 12:30 - 1:30 PM
Location: RUTCOR Building - Lounge, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We consider the supervised learning of a binary classifier from noisy
observations. We use smooth boosting to linearly combine abstaining hypotheses,
each of which maps a subcube of the attribute space to one of the two classes.
We introduce a new branch-and-bound weak learner to maximize the agreement rate
of each hypothesis. Dobkin et al. give an algorithm for maximizing agreement
with real-valued attributes. Our algorithm improves on the time complexity of
Dobkin et al.’s as long as the data can be binarized so that the number of
binary attributes is o(log of the number of observations × number of real-valued
attributes). Furthermore, we have fine-tuned our branch-and-bound algorithm
with a queuing discipline and optimality gap to make it fast in practice.
Finally, since logical patterns in Hammer et al.’s Logical Analysis of Data
(LAD) framework are equivalent to abstaining monomial hypotheses, any boosting
algorithm can be combined with our proposed weak learner to construct LAD
models. On various data sets, our method outperforms state-of-the-art methods
that use suboptimal or heuristic weak learners, such as SLIPPER. It is
competitive with other optimizing classifiers that combine monomials, such as
LAD. Compared to LAD, our method eliminates many free parameters that restrict
the hypothesis space and require extensive fine-tuning by cross-validation.
Acknowledgements: This work benefited from discussions with Peter L. Hammer,
who passed away prematurely. We also thank Philip M. Long, Robert E. Schapire,
Rocco A. Servedio.
This is a joint work with Chung-chieh Shan.
Back to Seminars Page.
Back to RUTCOR homepage.
| 
