* 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節

トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS