Automatically assigned DDC number:

Manually assigned DDC number: 00631

Number of references: 0

Title: Microchoice Bounds and Self Bounding Learning Algorithms

Author:

Author:

Subject: John Langford,Avrim Blum Microchoice Bounds and Self Bounding Learning Algorithms

Description: We prove adaptive bounds for learning algorithms that operate by making a sequence of choices. These adaptive bounds, which we call Microchoice bounds, can be used to make these algorithms self-bounding in the style of Freund [Fre98]. Furthermore, we can combine these bounds with Freund's more sophisticated query-tree approach, producing a modified query-tree structure that yields similar bounds to those in [Fre98] but that permits a much more efficient algorithmic approximation. 1 Introduction PAC bounds tend to be too loose for application to real world learning problems using common learning algorithms. They require more examples then expirementally necessary to guarantee a reasonable accuracy with a reasonable probability. Chief amongst the reasons for this failure is that typical PAC bounds are worst-case in nature and do not take into account what may turn out to be a fortunate target function and/or data distribution. A tighter bound can perhaps be derived by taking properties ...

Contributor: The Pennsylvania State University CiteSeer Archives

Publisher: unknown

Date: 1999-05-13

Pubyear: 1999

Format: ps

Identifier: http://citeseer.ist.psu.edu/140785.html

Source: http://www.cs.cmu.edu/People/avrim/Papers/microchoice.ps.gz

Language: en

Rights: unrestricted