PAC学習 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• PAC学習 へ行く。

* PAC学習 (probably approximately correct learning) [#j153b897]

//ここには %項目の説明を書いてください．よろしければ署名しておいてください．

パラメータ：入力の誤差 \(\epsilon\)，信頼度 \(\delta\)，学習する概念の複雑さの上限 \(s\)．

学習する概念についてのエラーがたかだか \(\epsilon\) である確率が \(1-\delta\) 大きくなるような仮説を出力できるアルゴリズムが存在するとき ''PAC学習可能 (probably approximately correct learnable)''．
こうした学習問題を扱うのが''PAC学習 (probably approximately correct learning)''

さらに，\(1/\epsilon\)，\(1/\delta\)，\(s\) について，計算時間が多項式時間で抑えられるとき，''多項式時間PAC学習可能''であるという．

> -- しましま

**関連項目 [#t52e661f]

//英語や同義語のあとに，#brで区切って関連する項目をリストしてください．
-[[PAC learning]]
-[[probably approximately correct learning]]
#br
-[[計算論的学習理論]]
-[[VC次元]]
-[[経験損失最小化]]
-[[構造的損失最小化]]
-[[ブースティング]]
-[[NP完全]]
#br
-[[検索:PAC学習]]

**リンク集 [#z4b921e2]

//関連するWWW資源があればリンクしてください．
-[[Wikipedia:Probably approximately correct learning]]

**関連文献 [#h1e50665]

//この%項目%に関連する書籍や論文を紹介してください．

-基本文献~
L.G.Valiant "A Theory of the Learnable" Communications of ACM, vol.27, no.11, pp.1134-1142 (1984)~
[[GoogleScholarAll:A Theory of the Learnable]]
-[[Book/人工知能学事典]] 5-11節
-[[Book/Machine Learning]] 7.2節