文章基本信息

标题：Unlabeled Data Does Provably Help
本地全文：下载
作者：Malte Darnst{\"a}dt ; Hans Ulrich Simon ; Bal{\'a}zs Sz{\"o}r{\'e}nyi 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：185-196
DOI：10.4230/LIPIcs.STACS.2013.185
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：A fully supervised learner needs access to correctly labeled examples whereas a semi-supervised learner has access to examples part of which are labeled and part of which are not. The hope is that a large collection of unlabeled examples significantly reduces the need for labeled-ones. It is widely believed that this reduction of "label complexity" is marginal unless the hidden target concept and the domain distribution satisfy some "compatibility assumptions". There are some recent papers in support of this belief. In this paper, we revitalize the discussion by presenting a result that goes in the other direction. To this end, we consider the PAC-learning model in two settings: the (classical) fully supervised setting and the semi-supervised setting. We show that the "label-complexity gap"' between the semi-supervised and the fully supervised setting can become arbitrarily large for concept classes of infinite VC-dimension (or sequences of classes whose VC-dimensions are finite but become arbitrarily large). On the other hand, this gap is bounded by O(ln |C|) for each finite concept class C that contains the constant zero- and the constant one-function. A similar statement holds for all classes C of finite VC-dimension.
关键词：algorithmic learning; sample complexity; semi-supervised learning