未分類

ノーフリーランチ定理

/*Yoshua Bengio先生のテキストではイントロダクションの後は線形代数,統計学,数値最適化の初歩の復習が載っていましたが,私自身にとって既知であり,本題はDeep learningである事を考慮して省きました*/

/*TODO:no free lunch theoremと書いてあったのでググってみました*/

No Free Lunch Theorem—理想の**の探し方—

によると,No Free Lunch定理(NFL)とは

「すべての評価関数に適用できる効率のよいアルゴリズムは存在しない。」

とのことです.

証明はどうしてもよくわからなかったのですが,

  • 候補空間、評価値空間は有限である。

  • 探索履歴のみを見るような探索アルゴリズムに限る。

  • アルゴリズムの効率は評価関数の評価回数に関するものである(同じ点を何度も評価する可能性を考慮しない)。

  • すべての評価関数に対して平均した場合の話である(すべての問題に対して平均したという話ではない)。

  • アルゴリズムが探索空間や評価関数を変化させることはないとしている。

という条件を満たす最適化アルゴリズムで,どんな状況でも少ないステップ数で答えを出すものは存在しないと言っているみたいです.

ノーフリーランチ定理 – Wikipedia

によると,ある問題に特化したアルゴリズムがあるなら汎用のアルゴリズムではなくそっちを使うべきだ,といった文脈でよく使われるみたいです.

/*最初のリンクでは万人受けする人物はいないという比喩を使ってわかりやすく説明されているので読んでみるといいかもしれません*/

広告

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中