On Online Learning of Decision Lists
On Online Learning of Decision Lists
复制标题
论决策表的在线学习
DOI：
--
复制
发表时间：
2003
影响因子：
6
通讯作者：
Ran El
中科院分区：
文献类型：
--
作者：
Ziv Nevo;Ran El
计算学习理论中的一个基本问题是决策表概念类是否存在属性有效学习算法（Rivest，1987; Blum，1996）。我们考虑一个较弱的问题，其中的概念类被限制为决策列表与D交替。对于这个类，我们提出了一种新的在线算法，实现了O（rDlog n）的错误界，其中r是相关变量的数量，n是变量的总数。该算法可以视为Littlestone（1988）著名的Winnow算法的严格推广，并改进了Balanced Winnow算法的O（r2 Dlog n）错误界。我们的界限比Dhagat和Hellerstein（1994）的类似PAC学习结果更强。将我们的算法与Rivest（1987）提出的算法相结合，可能会获得更好的边界。
A fundamental open problem in computational learning theory is whether there is an attribute efficient learning algorithm for the concept class of decision lists (Rivest, 1987; Blum, 1996). We consider a weaker problem, where the concept class is restricted to decision lists with D alternations. For this class, we present a novel online algorithm that achieves a mistake bound of O(rDlog n), where r is the number of relevant variables, and n is the total number of variables. The algorithm can be viewed as a strict generalization of the famous Winnow algorithm by Littlestone (1988), and improves the O(r2Dlog n) mistake bound of Balanced Winnow. Our bound is stronger than a similar PAC-learning result of Dhagat and Hellerstein (1994). A combination of our algorithm with the algorithm suggested by Rivest (1987) might achieve even better bounds.