Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms
复制标题
在线学习算法的布尔核的效率与收敛性
DOI：
10.1613/jair.1655
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
R. Servedio
中科院分区：
文献类型：
--
作者：
R. Khardon;D. Roth;R. Servedio
我们研究在线学习布尔域使用内核捕获功能扩展相当于使用连词的基本功能。我们证明了这些内核可以计算的计算效率和所得到的分类器的泛化能力之间的权衡。我们首先描述几个核函数，捕捉有限形式的合取或所有合取。我们表明，这些内核可以用来有效地运行的感知算法的指数数量的合取;然而，我们也证明，使用这样的内核的感知算法可以使指数数量的错误，即使在学习简单的功能。我们还考虑了一个类似的使用核函数运行乘法更新Winnow算法在一个扩展的特征空间的指数许多合取。虽然已知的上限意味着Winnow可以学习DNF公式在这种设置中的多项式错误界，我们证明了它是计算上很难模拟Winnow的行为学习DNF在这样的功能集，因此，这样的内核功能Winnow是不能有效地计算。
We study online learning in Boolean domains using kernels which capture feature expansions equivalent to using conjunctions over basic features. We demonstrate a tradeoff between the computational efficiency with which these kernels can be computed and the generalization ability of the resulting classifier. We first describe several kernel functions which capture either limited forms of conjunctions or all conjunctions. We show that these kernels can be used to efficiently run the Percep-tron algorithm over an exponential number of conjunctions; however we also prove that using such kernels the Perceptron algorithm can make an exponential number of mistakes even when learning simple functions. We also consider an analogous use of kernel functions to run the multiplicative-update Winnow algorithm over an expanded feature space of exponentially many conjunctions. While known upper bounds imply that Winnow can learn DNF formulae with a polynomial mistake bound in this setting, we prove that it is computationally hard to simulate Win-now's behavior for learning DNF over such a feature set, and thus that such kernel functions for Winnow are not efficiently computable.
DOI：
10.1007/3-540-45435-7_6
发表时间：
2002-07
期刊：
--
影响因子：
--
作者：
Eiji Takimoto;Manfred K. Warmuth
通讯作者：
Eiji Takimoto;Manfred K. Warmuth