论文标题
某些功能类的natarajan尺寸上的上限
Upper bounds on the Natarajan dimensions of some function classes
论文作者
论文摘要
Natarajan维度是表征多级PAC可学习性的基本工具，将Vapnik-Chervonenkis（VC）维度推广到从二进制到多类分类问题。这项工作在某些功能类别的Natarajan维度上建立了上限，包括（i）多类决策树和随机森林，以及（ii）具有二进制，线性和relu激活的多级神经网络。这些结果可能与描述某些多级学习算法的性能有关。
The Natarajan dimension is a fundamental tool for characterizing multi-class PAC learnability, generalizing the Vapnik-Chervonenkis (VC) dimension from binary to multi-class classification problems. This work establishes upper bounds on Natarajan dimensions for certain function classes, including (i) multi-class decision tree and random forests, and (ii) multi-class neural networks with binary, linear and ReLU activations. These results may be relevant for describing the performance of certain multi-class learning algorithms.
