劣モジュラ制約下におけるオンライン予測(機械学習一般とその応用)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では離散構造のオンライン予測問題を考える.ただし,各離散構造は劣モジュラ基多面体の頂点で表現できると仮定する.例として,全域木や,順列のオンライン予測問題がある.一般的に基多面体の端点は指数個存在するが,本論文では多項式時間オンライン予測アルゴリズムを提案し,リグレットの評価を与える.特に,劣モジュラ関数が入力のサイズのみに依存するとき,提案アルゴリズムの1つはO(n^2)時間で動作する.
- 2012-06-12
著者
-
瀧本 英二
九州大学大学院システム情報科学研究院情報理学部門
-
永野 清仁
東京大学生産技術研究所
-
来嶋 秀治
九州大学大学院システム情報科学研究院
-
末廣 大貴
九州大学大学院システム情報科学府
-
畑埜 晃平
九州大学大学院システム情報科学府
-
瀧本 英二
九州大学大学院システム情報科学府
-
来嶋 秀治
九州大学大学院システム情報科学府
関連論文
- 劣モジュラ費用集合被覆問題 (21世紀の数理計画 : アルゴリズムとモデリング)
- オンラインランク統合問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 楽曲の分類と文字列間の類似性指標について (特集 「脳科学と知識処理」および一般)
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 最簡な論理式でNPN同値類の代表のみを生成するアルゴリズム
- ある決定木のクラスに対する量子質問複雑さの下界について
- リスク情報を用いたオンライン資源分配
- 劣モジュラ構造を有する連続最適化問題の組合せ的アルゴリズム(研究会推薦博士論文速報)
- 劣モジュラ制約下の凸最適化問題について
- 最終段ミニマックスアルゴリズム
- ガウス分布推定問題に対するミニマックス戦略
- 高速なパラメトリック劣モジュラ関数最小化とその応用
- 劣モジュラ罰則を含む組合せ最適化問題の緩和問題に対するLovasz拡張とノンスムーズ凸最適化手法を用いた効率的解法
- 劣モジュラ罰則を含む組合せ最適化問題の緩和問題に対する Lovasz 拡張とノンスムーズ凸最適化手法を用いた効率的解法
- 最大エントロピー原理に基づくオンライン学習 (理論計算機科学の深化と応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- Online Learning of Approximate Maximum $p$-Norm Margin Classifiers with Bias (Foundations of Theoretical Computer Science : For New Computational View)
- 定数項の大きな線形しきい値関数に対する高速なオンライン学習(計算機科学の理論とその応用)
- ブール関数のPTF表現の複雑さについて
- ホーン式とXOR-MDNF式との関係について
- 交代数限定単調項決定リストの学習可能性
- 間引き：ロボットのスキル発見における評価の削減手法
- 基礎技術としての劣モジュラ最適化(最先端を目指す若手研究者達)
- 支配集合数え上げ問題とグラフクラス
- オンラインオークション型資源配分問題(計算理論とアルゴリズムの新展開)
- シャノンスイッチングゲームにおけるペアリング戦略の複雑さについて
- DS-1-14 ランダム写像による非線形概念の学習の効率化に向けて(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- マージンを保存するランダム性を限定したプロジェクションとブール空間への埋め込み
- リスク情報を用いたオンライン資源分配
- 分割と併合に基づくブーステイング
- 分割と併合に基づくブースティング
- オンライン学習の学習曲線に関する研究
- LA-5 決定ダイアグラムに基づくブースティング(A. アルゴリズム・基礎)
- ランダムプロジェクションによる次元圧縮
- オンライン予測 (計算学習理論の進展と応用可能性)
- Predicting like the best pruning of a decision tree based on the on-line DP (Algorithms and Theory of Computing)
- 劣モジュラ費用集合被覆問題
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習(IBIS2010(情報論的学習理論ワークショップ))
- オンライン予測の理論に基づく意思決定(新世代の計算限界-その解明と打破-招待解説論文)
- F-036 Online Rank Aggregation
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- しきい値回路のパターン数について (理論計算機科学の深化 : 新たな計算世界観を求めて)
- エネルギー計算量に制限のある定数段しきい値論理回路のサイズの指数下界について
- 路カーネルと乗算型重み更新
- イベント報告:東京工業大学サイエンスカフェ「計算で何ができるか?」 (特集 数学版サイエンスカフェ)
- 最終段ミニマックスアルゴリズム
- メトリカルタスクシステムに対する乗算型重み更新アルゴリズム
- ブール関数に対するフィルタのノイズ除去効果について
- F-037 Sparse Substring Pattern Set Discovery using Linear Programming Boosting
- 1V-3 間引きを用いたパス技術の自律学習(学習・推論,学生セッション,人工知能と認知科学)
- パラメトリックな劣モジュラ交わり問題の構造理論 (21世紀の数理計画 : 最適化モデルとアルゴリズム)
- DS-1-5 パラメトリックな劣モジュラ交わり問題の構造理論(DS-1. COMP-NHC学生シンポジウム,シンポジウムセッション)
- 劣モジュラ多面体上の最適化アルゴリズムの研究
- 劣モジュラ多面体内直線探索問題に対する強多項式時間アルゴリズム(組合せ最適化(6))
- 劣モジュラ多面体内直線探索問題に対する強多項式時間アルゴリズム
- A Strongly Polynomial Algorithm for Line Search in Submodular Polyhedra
- 確率的評価値をもつゲーム木における最善手探索 (計算機科学とアルゴリズムの数理的基礎とその応用)
- Predicting like the best pruning of a decision tree
- マッチングを用いたパターン形成アルゴリズム
- Practical Algorithms for Pattern Based Linear Regression (テーマ:特集「シンボルグラウンディング問題」および一般)
- エネルギー複雑度を用いた線形決定木の下界導出
- 類似性指標を用いた楽曲のジャンル分類 (「メディアとAI」および一般)
- ブール関数のフーリエ変換とその応用
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習
- MDL原理に基づいた決定木枝刈りアルゴリズムのシミュレーション
- エネルギー複雑度を用いた線形決定木の下界導出
- 複数の予測戦略を統合する実時間予測アルゴリズム(計算理論とその応用)
- 複数の予測戦略を統合する実時間予測アルゴリズム
- Online Prediction under Submodular Constraints (情報論的学習理論と機械学習)
- ブールドメイン上の関数に対するサンプリングの定理
- 決定木に基づいたオンライン学習アルゴリズム
- B-17-29 ヘテロジニアス型コグニティブ無線ネットワークにおけるRAN選択問題の厳密最適化(B-17.ソフトウェア無線,一般セッション)
- 劣モジュラ性に基づく知能情報処理への新展開(離散構造処理系-知能情報処理を支えるアルゴリズムの技法)
- Efficient AUC Maximization by Approximate Reduction of Ranking SVMs (情報論的学習理論と機械学習・第15回情報論的学習理論ワークショップ)
- 劣モジュラ性に基づく知能情報処理への新展開
- DNF式の学習可能性
- 劣モジュラ制約下におけるオンライン予測(機械学習一般とその応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- ランキングSVMの近似に基づく効率的なAUC最大化(第15回情報論的学習理論ワークショップ)
- バイアス付きPassive-Aggressiveアルゴリズム
- DS-1-16 ランダムウォークの定常分布と到達時間および全訪問時間の関係(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 類似度に基づくポリフォニックな楽曲の分類
- SVMによる2部ランキング学習を用いたコンピュータ将棋における評価関数の学習(情報・システム基礎)