图 书 馆
确定性标签下不可知学习的样本复杂度The sample complexity of agnostic learning under deterministic labels |
|
| 课程网址: | http://videolectures.net/colt2014_urner_labels/ |
| 主讲教师: | Ruth Urner |
| 开课单位: | 卡内基梅隆大学 |
| 开课时间: | 2014-07-15 |
| 课程语种: | 英语 |
| 中文简介: |  随着机器学习工具的出现，该工具允许处理具有大量功能的数据，因此有理由假设，在全部功能上，（几乎）完全确定了真实的标签。也就是说，标记函数是确定性的，但不一定是某些已知假设类的成员。但是，到目前为止，确定性标签的不可知论学习很少受到研究关注。我们调查了此设置，并表明它显示的行为与常见（PAC）学习设置的基本结果完全不同。首先，我们证明了学习二元假设类（相对于确定性标记函数）的样本复杂性并没有完全由该类的VC维确定。对于任何d，我们提供VC维d的类，这些类可以从O（d / d）中学到许多样本，而类则需要大小为Ω（d / ϵ2）的样本。此外，我们表明，在这种设置中，某些类的任何合适的学习者的样本复杂度都不理想。虽然可以使用样本复杂度O（d / ϵ）来学习该类，但是任何适当的（因此，任何ERM）算法都需要Ω（d / ϵ2）个样本。我们提供两种现象的组合特征，并进一步分析这种情况下未标记样品的效用。最后，我们讨论了确定性标签下的最近邻算法的错误率和数据假设的额外好处。 |
| 课程简介: | With the emergence of Machine Learning tools that allow handling data with a huge number of features, it becomes reasonable to assume that, over the full set of features, the true labeling is (almost) fully determined. That is, the labeling function is deterministic, but not necessarily a member of some known hypothesis class. However, agnostic learning of deterministic labels has so far received little research attention. We investigate this setting and show that it displays a behavior that is quite different from that of the fundamental results of the common (PAC) learning setups. First, we show that the sample complexity of learning a binary hypothesis class (with respect to deterministic labeling functions) is not fully determined by the VC-dimension of the class. For any d, we present classes of VC-dimension d that are learnable from O(d/ϵ)-many samples and classes that require samples of size Ω(d/ϵ2). Furthermore, we show that in this setup, there are classes for which any proper learner has suboptimal sample complexity. While the class can be learned with sample complexity O(d/ϵ), any proper (and therefore, any ERM) algorithm requires Ω(d/ϵ2) samples. We provide combinatorial characterizations of both phenomena, and further analyze the utility of unlabeled samples in this setting. Lastly, we discuss the error rates of nearest neighbor algorithms under deterministic labels and additional niceness-of-data assumptions. |
| 关 键 词: | 机器学习; 标记函数 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2020-12-07：zyk |
| 最后编审: | 2020-12-07：zyk |
| 阅读次数: | 40 |