.png){kind=icon}
返回
Tracking the best disjunction
.png){kind=icon}
OA
AI
DOI：10.1023/A:1007472513967.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Littlestone developed a simple deterministic on-line learning algorithm for learning k-literal disjunctions. This algorithm (called WINNOW) keeps one weight for each of the n variables and does multiplicative updates to its weights. We develop a randomized version of WINNOW and prove bounds for an adaptation of the algorithm for the case when the disjunction may change over time. In this case a possible target disjunction schedule T is a sequence of disjunctions (one per trial) and the shift size is the total number of literals that are added/removed from the disjunctions as one progresses through the sequence. We develop an algorithm that predicts nearly as well as the best disjunction schedule for an arbitrary sequence of examples. This algorithm that allows us to track the predictions of the best disjunction is hardly more complex than the original version. However, the amortized analysis needed for obtaining worst-case mistake bounds requires new techniques. In some cases our lower bounds show that the upper bounds of our algorithm have the right constant in front of the leading term in the mistake bound and almost the right constant in front of the second leading term. Computer experiments support our theoretical Endings.
Keyword:
on-line learning
prediction
concept drift
WINNOW
computational learning theory
amortized analysis
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
