* no free lunch定理 (no free lunch theorem) [#ie5d6fc1]

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

直観的には,事例の分布などについて事前知識がなければ,
あらゆる目的関数について他を常に上回るような学習アルゴリズムは存在しないという定理.
「ただ(=事前の知見なし)の飯(=予測や探索での改善)はない(no free lunch)」といった意味の名称.

形式的には,訓練事例に含まれないデータに対するエラーを
\[\mathcal{E}_k(E|F,\mathcal{D})=\sum_{\mathbf{x}\notin\mathcal{D}}P(\mathbf{x})[1-\delta(F(\mathbf{x}),h(\mathbf{x}))]P_k(h(\mathbf{x}|\mathcal{D})\]
ただし
- \(F(\mathbf{x})\):学習目標の関数
- \(h(\mathbf{x})\):アルゴリズムが獲得した関数
- \(\mathcal{D}\):訓練事例集合
- \(\delta(F,h)\):目標\(F(\mathbf{x})\)と\(h(\mathbf{x})\)が一致すると1になるKroneckerのδ
- \(P_k(h|\mathcal{D})\):アルゴリズム\(k\)が,訓練事例集合\(h(\mathbf{x})\)を与えられたときに出力する関数\(h\)の分布

''no free lunch定理''は,任意の二つのアルゴリズム\(P_1(h|\mathcal{D})\)と\(P_2(h|\mathcal{D})\)について,サンプリング分布\(P(\mathbf{x})\)と\(n\)個の訓練事例とは独立に以下のことが成立:
+ 全ての目的関数\(F\)上で均一に平均すると \(\mathcal{E}_1(E|F,n)-\mathcal{E}_2(E|F,n)=0\).すなわち
\[\sum_F \sum_{\mathcal{D}}P(\mathcal{D}|F)[\mathcal{E}_1(E|F,\mathcal{D})-\mathcal{E}_2(E|F,\mathcal{D})]=0\]
+ ある固定した訓練集合\(\mathcal{D}\)について,\(F\)上で均一に平均すると
\(\mathcal{E}_1(E|F,\mathcal{D})-\mathcal{E}_2(E|F,\mathcal{D})=0\)
+ 全ての事前分布\(P(F)\)上で均一に平均すると \(\mathcal{E}_1(E|n)-\mathcal{E}_2(E|n)=0\)
+ ある固定した訓練集合\(\mathcal{D}\)について,\(P(F)\)上で均一に平均をすると
\(\mathcal{E}_1(E|\mathcal{D})-\mathcal{E}_2(E|\mathcal{D})=0\)

> -- しましま

**関連項目 [#pce0a50d]

//英語や同義語のあとに,#brで区切って関連する項目をリストしてください.
-[[no free lunch theorem]]
#br
-[[醜いアヒルの子の定理]]
#br
-[[検索:ノーフリーランチ定理]]

**リンク集 [#x44bf479]

//関連するWWW資源があればリンクしてください.
-[[no-free-lunch.org>http://www.no-free-lunch.org/]]
-[[No Free Lunch Theorem —理想の**の探し方—>http://www.unfindable.net/~yabuki/article/no_free_lunch/]]
#br
-[[Wikipedia:No_free_lunch_in_search_and_optimization]]
-[[Wikipedia.jp:ノーフリーランチ定理]]

**関連文献 [#b076e97b]

//この%項目%に関連する書籍や論文を紹介してください.
-基本文献~
David H.Wolpert and William G. Macready, "No Free Lunch Theorems for Search", Technical Report SFI-TR-95-02-010, Santa Fe Institute, 1995~
[[GoogleScholarAll:No Free Lunch Theorems for Search]]~
David H.Wolpert and William G. Macready, "No Free Lunch Theorems for Optimization", IEEE Transactions on Evolutionary Computation, vol.1, pp.67-82 (1997)~
[[GoogleScholarAll:No Free Lunch Theorems for Optimization]]
-[[Book/Pattern Classification]] 9.2.1節
-[[Book/人工知能学事典]] 6-8節

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