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

^*此作品的通讯作者

National University of Singapore

科研成果: 期刊稿件 › 快报 › 同行评审

15 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	1257-1261
页数	5
期刊	IEEE Transactions on Information Theory
卷	47
期	3
DOI	https://doi.org/10.1109/18.915700
出版状态	已出版 - 3月 2001
已对外发布	是

访问文件

10.1109/18.915700

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

指纹

引用此