分割と併合に基づくブースティング
スポンサーリンク
概要
- 論文の詳細を見る
lnfoBoostは,学習対象に関する相互情報量が0ではない複数の仮説を統合して精度の高い仮説を構築するブースティングアルゴリズムである.本稿は,InfoBoostが,ドメインの分割と併合を繰り返すブランチングプログラムを生成するアルゴリズムとみなせることを示す.ただ,ブランチングプログラムを定義する決定グラフの各頂点には重みが割り当てられ,各事例に対する統合仮説の値は,その事例がたどる道上の重みの和に基づいて定められる.さらに,併合の手続きを一般化し,新しいブースティング手法のクラスBP.InfoBoostを提案する.InfoBoostは,分割された領域をすべて併合してしまう極端なアルゴリズムとみなせる.一方,併合をあまり行わないと,仮説の性能向上の効率は良くなるが過学習のリスクを伴う.本稿では,仮説の性能向上の効率化と過学習のリスクの回避を両立する併合手法を提案する.
- 2004-10-07
著者
-
瀧本 英二
九州大学大学院システム情報科学研究院情報理学部門
-
丸岡 章
東北大学大学院情報科学研究科
-
丸岡 章
Graduate School Of Information Sciences Tohoku University
-
瀧本 英二
東北大学大学院情報科学研究科
-
小屋 州平
東北大学大学院情報科学研究科
関連論文
- オンラインランク統合問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 最簡な論理式でNPN同値類の代表のみを生成するアルゴリズム
- 発見科学の構想と展開(発見科学)
- ある決定木のクラスに対する量子質問複雑さの下界について
- リスク情報を用いたオンライン資源分配
- 最終段ミニマックスアルゴリズム
- ガウス分布推定問題に対するミニマックス戦略
- 充足割り当て数を最小化/最大化する単調DNF式について
- 連数限定入力に対する否定数限定ソーティング回路
- 直交F-ホーン式の学習アルゴリズム
- ブール関数のPTF表現の複雑さについて
- ホーン式とXOR-MDNF式との関係について
- 交代数限定単調項決定リストの学習可能性
- 単調DNF式の排他的論理和の学習可能性
- 和集合のサイズの近似評価について
- アルゴリズムの非確率化と制限付き独立性
- Selection Networks with $8n$ log$_2$ $n$ Size and $O$(log $n$) Depth
- 二部グラフの拡張性の評価について(計算機科学の基礎理論)
- 単項性判定のための論理関数に関する条件
- オンラインオークション型資源配分問題(計算理論とアルゴリズムの新展開)
- シャノンスイッチングゲームにおけるペアリング戦略の複雑さについて
- DS-1-14 ランダム写像による非線形概念の学習の効率化に向けて(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- マージンを保存するランダム性を限定したプロジェクションとブール空間への埋め込み
- リスク情報を用いたオンライン資源分配
- 指数重み閾値関数の多項式重みによる模倣手法の改良
- 指数重み閾値関数の多項式重みによる模倣手法の改良
- 二次論理関数の単調回路計算量について
- 分割と併合に基づくブーステイング
- 二次論理関数の単調回路計算量について
- 分割と併合に基づくブースティング
- 最適なマージングネットワークについて
- 最適なマージングネットワークについて
- オンライン学習の学習曲線に関する研究
- 計算の複雑さと効率化の研究(フェロー受賞記念講演)
- 単調論理関数の性質判定アルゴリズムについて
- LA-5 決定ダイアグラムに基づくブースティング(A. アルゴリズム・基礎)
- 単調論理関数間の距離について
- ランダムプロジェクションによる次元圧縮
- 論理関数のフーリエスペクトルと非線形性の関係
- 決定森の族の計算能力
- 制限付集合に対する包除原理の性質と数え上げ問題への応用
- 決定木における補助ビット問題について
- CC(6)型回路と(MOD3-MOD2)回路における計算の複雑さについて
- オンライン予測 (計算学習理論の進展と応用可能性)
- 否定数限定論理回路におけるマージングの複雑さ
- 最適なマージングネットワークについて
- Predicting like the best pruning of a decision tree based on the on-line DP (Algorithms and Theory of Computing)
- 否定素子数限定論理回路における単調論理関数の複雑さ (アルゴリズムと計算の理論)
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習(IBIS2010(情報論的学習理論ワークショップ))
- オンライン予測の理論に基づく意思決定(新世代の計算限界-その解明と打破-招待解説論文)
- 連数限定入力に対する否定数限定ソーティング回路
- F-036 Online Rank Aggregation
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- しきい値回路のパターン数について (理論計算機科学の深化 : 新たな計算世界観を求めて)
- エネルギー計算量に制限のある定数段しきい値論理回路のサイズの指数下界について
- A learning algorithm for monotone $k$-term DNF
- 榊原康文, 小林聡, 横森貴(著), 計算論的学習, 情報数理シリーズ(B-6), 培風館, 221p., 3,000円(税別), ISBN4-563-01496-6
- ALT'97 報告
- LEARNING MONOTONE LOG-TERM DNF FORMULAS
- 単調O(log n)項DNF式の学習
- 路カーネルと乗算型重み更新
- 最終段ミニマックスアルゴリズム
- メトリカルタスクシステムに対する乗算型重み更新アルゴリズム
- ブール関数に対するフィルタのノイズ除去効果について
- 確率的評価値をもつゲーム木における最善手探索 (計算機科学とアルゴリズムの数理的基礎とその応用)
- Predicting like the best pruning of a decision tree
- 多値論理素子が細分的であるための条件 (情報科学の数学的理論)
- 近似法のサイズ限定モデル
- エネルギー複雑度を用いた線形決定木の下界導出
- サイズ限定モデルに基づく近似法による単調複雑さの下界
- ブール関数のフーリエ変換とその応用
- クリーク関数の否定数限定複雑さ
- 否定素子数限定論理回路における単調論理関数の複雑さ
- 論理関数の複雑さと近似演算(計算理論とその応用)
- 論理関数の複雑さと近似演算
- 論理関数の複雑さと近似演算
- MDL原理に基づいた決定木枝刈りアルゴリズムのシミュレーション
- 複数の予測戦略を統合する実時間予測アルゴリズム
- エネルギー複雑度を用いた線形決定木の下界導出
- 複数の予測戦略を統合する実時間予測アルゴリズム(計算理論とその応用)
- 複数の予測戦略を統合する実時間予測アルゴリズム
- 情報獲得と近似学習
- 相互情報量に基づく学習モデル
- ブールドメイン上の関数に対するサンプリングの定理
- 決定木に基づいたオンライン学習アルゴリズム
- Efficient AUC Maximization by Approximate Reduction of Ranking SVMs (情報論的学習理論と機械学習・第15回情報論的学習理論ワークショップ)
- DNF式の学習可能性
- 劣モジュラ制約下におけるオンライン予測(機械学習一般とその応用)
- 「AIマップ : 機械学習から機械発見へ」へのコメントと回答
- 単調論理関数と擬似補関数に対する近似モデル(計算モデルと計算の複雑さに関する研究)
- 否定制約のもとでのクリーク関数の複雑さに対する指数関数の下界
- 単調論理関数と擬似補関数に対する近似モデル
- 非単調論理回路に対する Razborov の近似モデルの構造
- 制限付回路モデルに対するRazborovの近似法の適用
- k-限定独立性に基づいたDNFの近似アルゴリズム
- ランキングSVMの近似に基づく効率的なAUC最大化(第15回情報論的学習理論ワークショップ)