<テクニカルレポート>
Refutably Probably Approximately Correct Learning

作成者
本文言語
出版者
発行日
収録物名
出版タイプ
アクセス権
関連DOI
関連URI
関連情報
概要 We propose a notion of the rejutably PAC learnability, which formalizes the refutability of hypothesis spaces in the PAC learning model. Intuitively, the refutable PAC learnability of a concept class ...F requires that the learning algorithm should refute F with high probability if a target concept can not be approximated by any concept in F with respect to the underlying probability distribution. We give a general upper bound of $ Oleft((1/ \varepsilon + 1/\varepsilon' )log(mid F_n mid
delta)\right) $ on the number of examples required for refutably PAC learning of F. Here, $ \varepsilon $ and $ delta $ are the standard accuracy and confidence parameters, and $ \varepsilon' $ is the refutation accuracy. We also define the strongly refutably PAC learnability by introducing the refutation threshold. We prove a general upper bound of $ Oleft((1/\varepsilon^2 + 1/ \varepsilon'^2\right) log left(mid F_n mid
delta)\right) for strongly refutably PAC learning of F. These upper bounds reveal that both the refutably PAC learnability and the strongly refutably PAC learnability are equivalent to the standard PAC learnability within the polynomial size restriction.
続きを見る

本文ファイル

pdf rifis-tr-87 pdf 580 KB 375  

詳細

レコードID
査読有無
注記
タイプ
登録日 2009.04.22
更新日 2017.01.20