Automatically assigned DDC number:

Manually assigned DDC number: 00631

Number of references: 0

Title: Microchoice Bounds and Self Bounding Learning Algorithms



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



Language: en

Rights: unrestricted


<?xml   version="1.0"   encoding="UTF-8"?>


      <rec   ID="SELF"   Type="SELF"   CiteSeer_Book="SELF"   CiteSeer_Volume="SELF"   Title="Microchoice   Bounds   and   Self   Bounding   Learning   Algorithms">

            <identifier   Org="ISBN:1581131674"   Paper_ID="SELF"   Extracted="1581131674"   />

            <identifier   Org="ISBN:3540729259"   Paper_ID="SELF"   Extracted="3540729259"   />