| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連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.続きを見る
|
Mendeley出力
rifis-tr-87