No Free Lunch Theoremの別証明と解釈
スポンサーリンク
概要
- 論文の詳細を見る
本稿ではNo Free Lunch Treorem (NFL)の別証明を与える.NFLは「どんな問題に対しても平均的に効率良く解けるような探索アルゴリズムは存在しない」ということを主張する定理であり, 探索アルゴリズムあるいは最適化法の研究に大きな影響を与えた.本稿では, より簡潔でかつ直観的な証明を与える.我々は評価関数の空間を部分集合に分割し, それぞれの部分集合ごとにパフォーマンスが得られる確率を合計する.関数空間の分割により, 定理のより深い理解が可能となり, またアルゴリズムと問題の関係が明確となる.
- 2005-03-17
著者
-
伊庭 斉志
東京大学大学院・電子情報工学専攻
-
伊庭 斉志
東京大学大学院工学系研究科
-
伊庭 斉志
通商産業省工業技術院電子技術総合研究所知能情報部推論研究室
-
柳井 孝介
東京大学大学院新領域創成科学研究科
-
伊庭 斉志
東京大学大学院 工学系研究科 電気系工学専攻
関連論文
- 確率モデルGPのための二分岐化プロトタイプ木
- IECを用いた歌声パラメータの最適化システム(音楽生成)
- No Free Lunch Theoremの別証明と解釈
- 分子生物情報研究会特別セッションパネル : 生命理解のためのABC-人工生命(A)、分子生物(B)、情報(C)の立場から見た生命現象を解明するための方法論について
- n人繰り返し囚人のジレンマゲーム戦略のGAによる進化 : 技術研究報告形式
- D-8-17 対話型進化計算法を用いた3D Avatar設計
- 遺伝的アルゴリズムから人工生命へ(9)対話型計算による3次元アニメーションの生成
- PCFGの文法拡大による音列パターン解析(音楽構造解析)
- 遺伝的プログラミングと強化学習の統合に基づく実ロボットの行動獲得(GP)(進化的計算)
- ノード順位による選択を用いたスケールフリー・ネットワークモデル(ネットワークが創発する知能)
- 木構造のランダムサンプリングによるGPの個体生成手法の提案と評価
- 遺伝的アルゴリズムによる量子テレポテーション回路の生成
- 遺伝的アルゴリズムによる量子回路生成
- n人繰り返し囚人のジレンマゲーム戦略のGAによる進化 : 技術研究報告形式
- 自動型と対話型の遺伝的プログラミングを用いた自動表情付けシステム
- 拡張PCFGによる演奏MIDIデータからの拍節構造推定
- 進化的コンピューティング(知能コンピューティングとその周辺〔第9回〕)
- 量子コンピュータってどんなもの?(知らないわけではないけれど第37回)
- 遺伝的プログラミングを用いたロボット協調行動の学習
- AreaView2001 : WWWからの構造化した領域総覧提示システム
- AreaView2001 KeyGraphを用いたWWW構造化システム
- 遺伝的プログラミングによる微分方程式系の推定
- ベクトル場マシン : 情報処理と処理空間の位相
- 対話型作曲支援システムにおけるユーザ嗜好の獲得
- 初心者向け音楽創作IECのためのユーザアシスト機能についての検討(セッション5)
- 初心者向け音楽創作IECのためのユーザアシスト機能についての検討(セッション5)
- 確率文脈自由文法による旋律の拍節モデル推定
- 能動的音楽聴取インタフェースの作曲支援IECへの取り込み
- Swarm : 複雑系のシミュレーションツール(研究のツールボックス 第6回)
- AdaBoost を用いた遺伝子制御ネットワークの統合的推定
- ベイジアンネットワーク推定による確率モデル遺伝的プログラミング
- GPを用いた旋律のグルーピングルール生成
- ECを用いた作曲支援システムと作曲モデルの客観的評価手法
- 進化論的手法を用いた金融データの予測(予測技術の信頼性)
- 免疫系を用いた遺伝的プログラミングによる多峰性探索
- マルチエージェント協調作業のためのランダムサンプリングを用いた経路プランニングアルゴリズム(人工知能,認知科学)
- ヒューマノイドロボットの柔軟な制御のためのGPとCBRの統合
- 2R-8 WWW情報空間における特徴ベクトルを用いたリンクの分類
- WWW 情報空間のリンク構造を用いた弱い構造化
- D-7-11 進化型ベイジアンネットによる遺伝子ネットワークの推定
- 遺伝的アルゴリズムによる電柱配置の自動設計
- 移民世代数と深さ依存型交叉を用いた並列分散GP(≤特集≥進化的計算)
- Robustness of robot programs generated by genetic programming
- 対話型進化論的計算による作曲支援システム : CACIE(音楽生成・表情生成 2)
- 1U-6 概念体系に基づくFish Eyeマッチングと仮説推論を用いたユーザの視点の抽出
- タグ付遺伝子型を用いたネットワーク構造の進化的学習と最適化
- 遺伝的アルゴリズムから人工生命へ(4)アリの探索モデル:集団による知能
- 可変長遺伝子を用いた進化型アナログ回路
- 可変長遺伝子を用いたアナログ回路の進化
- 1L-9 可変長染色体を用いた遺伝的アルゴリズムによる電気回路の生成
- D-8-19 共進化モデルに基づく遺伝的プログラミングの並列化
- Swarmによる複雑系のシミュレーション(進化型計算と創発のシミュレーション)
- 関数の回帰的なネットワークを用いた言語判定装置の生成(新しいGA,GAの改良)(進化的計算)
- 遺伝的アルゴリズムから人工生命へ(最終回)進化論と進化論的計算
- 遺伝的アルゴリズムから人工生命へ(10)知的なエージェントの学習環境
- 遺伝的アルゴリズムから人工生命へ(3)No Free Lunch Theorem--理想の※※の探し方
- 2M-1 遺伝的プログラミングを用いたマルチエージェント学習 : 通信を用いた追跡問題の解法
- D-8-16 エージェント間の通信を用いたロボット協調行動の進化
- 遺伝的プログラミングの理論的展開
- 5L-10 遺伝的プログラミングを用いた株価指数予測
- 人間の演奏者と音楽インタラクションを行うマルチエージェントシステムの構築
- プログラムのインタラクションによる情報構造の創発に関する研究(創発システム,人工知能分野における博士論文)
- 条件付き確率に基づく分布推定アルゴリズムによるプログラム進化
- 条件付き確率に基づく分布推定アルゴリズムによるプログラム進化(進化的計算)
- λ関数群がなす自己触媒ネットワークの構造
- 1N-10 自然言語に近い知識表現を可能にする概念化学プログラミングの実現
- 3P-1 WebBeholder Personal Edition : Webの差分情報提供システム
- 遺伝的アルゴリズムから人工生命へ(11)EDAアルゴリズム:GAから交叉や突然変異をなくしたら?
- 環境モデルにおける物体の見え方と見方
- 拡張型GPによるロボット行動の自動生成へのアプローチ : ライブラリ導入による部分汎化行動の獲得
- 遺伝的アルゴリズムから人工生命へ(7)Particle Swarm Optimization--魚の群の美しさに学ぶ
- PCFG-LA混合モデルに基づく分布推定アルゴリズム
- AIの非伝統的アプローチ
- Richard Dawkins : The Selfish Gene(20世紀の名著名論)
- 対話型進化計算による3次元動作設計
- 遺伝的アルゴリズムから人工生命へ(8)遺伝子の中に眠る歴史--分子系統学
- 遺伝的アルゴリズムから人工生命へ(6)獲得形質は遺伝する!?--学習が進化に及ぼす影響
- 遺伝的アルゴリズムから人工生命へ(5)孔雀の羽
- 遺伝的アルゴリズムから人工生命へ(2)対話型進化計算とその応用
- 遺伝的アルゴリズムから人工生命へ(1)GAとGP入門
- F02-(1) 進化論的計算手法の現状と将来
- 対話型進化的計算によるリズムの生成
- 5L-9 汎用Linear GPシステムの実装と評価
- 遺伝的プログラミング
- 遺伝的プログラミングと進化論的計算手法
- 遺伝的プログラミングと進化論的計算手法
- 遺伝的プログラミングとロボット
- CEC'99およびCECCO'99の報告
- 遺伝的アルゴリズムとロボットの共進化(創発システムとその応用)
- 進化論的計算手法の最近の研究動向
- 進化論的計算手法の最近の研究動向