Type:     THEORY SEMINAR
Who:      Robert Schapire, AT&T Bell Labs
Topic:    A Decision-Theoretic Generalization of On-Line Learning and an 
        Application to Boosting
Dates:    17-Feb-95
Time:     3:30
Place:    Wean 4623
Host:     Avrim Blum
                        ABSTRACT

A gambler, frustrated by persistent horse-racing losses and envious of
his friends' winnings, decides to allow a group of his fellow gamblers
to make bets on his behalf.  He decides he will wager a fixed sum of
money in every race, but that he will apportion his money among his
friends based on how well they are doing.  Certainly, if he knew
psychically ahead of time which of his friends would win the most, he
would naturally have that friend handle all his wagers.  Lacking such
clairvoyance, however, he attempts to allocate each race's wager in
such a way that his total winnings for the season will be reasonably
close to what he would have won had he bet everything with the
luckiest of his friends.

In this talk, I will describe a simple algorithm for solving such
dynamic allocation problems, and an analysis which is derived in a
``worst-case'' setting without using statistical assumptions of any
kind.  Our algorithm, which is a direct generalization of Littlestone
and Warmuth's ``weighted majority'' algorithm, can be applied to a
broad assortment of learning problems.  Perhaps the most surprising of
these applications is the derivation of a new algorithm for
``boosting,'' that is, for converting a ``weak'' PAC learning
algorithm that performs just slightly better than random guessing into
one with arbitrarily high accuracy.

This is joint work with Yoav Freund.

Cboards:  general
PostedBy: Dorothy.A.Zaborowski on 13-Feb-1995 at 15:07 from AMM.ADM.CS.CMU.EDU
LastMod:  Monday, 13-Feb-95 at 15:12