The one-inclusion graph algorithm is near-optimal for the prediction model of learning

Y. Li; P. M. Long; A. Srinivasan

doi:10.1109/18.915700

The one-inclusion graph algorithm is near-optimal for the prediction model of learning

Y. Li^*
, P. M. Long
, A. Srinivasan

^*Corresponding author for this work

National University of Singapore

Research output: Contribution to journal › Letter › peer-review

14 Scopus citations

Abstract

Haussler, Littlestone, and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1 + o(1) of the best possible such bound for any algorithm.

Original language	English
Pages (from-to)	1257-1261
Number of pages	5
Journal	IEEE Transactions on Information Theory
Volume	47
Issue number	3
DOIs	https://doi.org/10.1109/18.915700
State	Published - Mar 2001
Externally published	Yes

Keywords

Computational learning
One-inclusion graph algorithm
Prediction model
Sample complexity
Vapnik-Chervonenkis (VC) dimension

Access to Document

10.1109/18.915700

Cite this

@article{5eb4269c6bb74358b682f6a7c8a26084,

title = "The one-inclusion graph algorithm is near-optimal for the prediction model of learning",

abstract = "Haussler, Littlestone, and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1 + o(1) of the best possible such bound for any algorithm.",

keywords = "Computational learning, One-inclusion graph algorithm, Prediction model, Sample complexity, Vapnik-Chervonenkis (VC) dimension",

author = "Y. Li and Long, \{P. M.\} and A. Srinivasan",

year = "2001",

month = mar,

doi = "10.1109/18.915700",

language = "英语",

volume = "47",

pages = "1257--1261",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - The one-inclusion graph algorithm is near-optimal for the prediction model of learning

AU - Li, Y.

AU - Long, P. M.

AU - Srinivasan, A.

PY - 2001/3

Y1 - 2001/3

N2 - Haussler, Littlestone, and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1 + o(1) of the best possible such bound for any algorithm.

AB - Haussler, Littlestone, and Warmuth described a general-purpose algorithm for learning according to the prediction model, and proved an upper bound on the probability that their algorithm makes a mistake in terms of the number of examples seen and the Vapnik-Chervonenkis (VC) dimension of the concept class being learned. We show that their bound is within a factor of 1 + o(1) of the best possible such bound for any algorithm.

KW - Computational learning

KW - One-inclusion graph algorithm

KW - Prediction model

KW - Sample complexity

KW - Vapnik-Chervonenkis (VC) dimension

UR - https://www.scopus.com/pages/publications/0035269626

U2 - 10.1109/18.915700

DO - 10.1109/18.915700

M3 - 快报

AN - SCOPUS:0035269626

SN - 0018-9448

VL - 47

SP - 1257

EP - 1261

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 3

ER -

The one-inclusion graph algorithm is near-optimal for the prediction model of learning

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this