F-036 Online Rank Aggregation
スポンサーリンク
概要
- 論文の詳細を見る
We consider an online learning framework where the task is to predict a permutation which represents a ranking of n fixed objects. At each trial, the learner incurs a loss defined as the Kendall tau distance between the predicted permutation and the true permutation given by the adversary. This setting is quite natural in many situations such as information retrieval and recommendation tasks. We propose algorithms for this problem and prove relative loss bounds with regret only depending on O(n^2). Further, we also prove a matching lower bound of the regret, which shows our algorithms are almost optimal.
- 2010-08-20
著者
-
瀧本 英二
九州大学大学院システム情報科学研究院情報理学部門
-
瀧本 英二
九州大学システム情報科学研究院情報学部門
-
瀧本 英二
九州大学大学院システム情報科学研究院
-
竹田 正幸
九州大学大学院システム情報科学研究院
-
安武 翔太
九州大学工学部電気情報工学科
-
竹田 正幸
九州大学大学院システム情報科学研究院情報学部門
-
畑埜 晃平
九大
-
竹田 正幸
九大
-
安武 翔太
九大
-
瀧本 英二
九大
-
畑埜 晃平
九州大学大学院システム情報科学研究院
-
畑埜 晃平
九州大学大学院システム情報科学府
関連論文
- オンラインランク統合問題 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 楽曲の分類と文字列間の類似性指標について (特集 「脳科学と知識処理」および一般)
- 『恵慶法師集』比良歌群試注
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- 最簡な論理式でNPN同値類の代表のみを生成するアルゴリズム
- ある決定木のクラスに対する量子質問複雑さの下界について
- リスク情報を用いたオンライン資源分配
- 最終段ミニマックスアルゴリズム
- ガウス分布推定問題に対するミニマックス戦略
- 国文学の研究教育における機械学習応用(機械学習の科学研究への応用)
- 最大エントロピー原理に基づくオンライン学習 (理論計算機科学の深化と応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- Online Learning of Approximate Maximum $p$-Norm Margin Classifiers with Bias (Foundations of Theoretical Computer Science : For New Computational View)
- 漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング(夏のデータベースワークショップ2007(データ工学,一般))
- 漸増的なパストライ構築に基づく高速・軽量XML文書フィルタリング(テキスト検索,夏のデータベースワークショップ2007(データ工学,一般))
- 定数項の大きな線形しきい値関数に対する高速なオンライン学習(計算機科学の理論とその応用)
- 接尾辞配列による効率的な文字列上の同値類計算
- ブール関数の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)
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習(IBIS2010(情報論的学習理論ワークショップ))
- オンライン予測の理論に基づく意思決定(新世代の計算限界-その解明と打破-招待解説論文)
- F-036 Online Rank Aggregation
- 対称関数を計算するユネイト回路のサイズとエネルギーのトレードオフ
- ブール剰余関数を計算するしきい値論理回路のサイズとエネルギー複雑度のトレードオフ
- しきい値回路のパターン数について (理論計算機科学の深化 : 新たな計算世界観を求めて)
- エネルギー計算量に制限のある定数段しきい値論理回路のサイズの指数下界について
- 2.情報爆発時代のための新しい超高速アルゴリズム(パートI:情報爆発時代における新しい基盤技術,情報爆発時代におけるわくわくするITの創出を目指して)
- 路カーネルと乗算型重み更新
- 最終段ミニマックスアルゴリズム
- メトリカルタスクシステムに対する乗算型重み更新アルゴリズム
- ブール関数に対するフィルタのノイズ除去効果について
- F-037 Sparse Substring Pattern Set Discovery using Linear Programming Boosting
- A-016 Verifying a Parameterized Border Array in O(n^) Time
- 1V-3 間引きを用いたパス技術の自律学習(学習・推論,学生セッション,人工知能と認知科学)
- 圧縮文字列上での $q$-gram 頻度の高速な計算方法 (計算機科学とアルゴリズムの数理的基礎とその応用)
- 確率的評価値をもつゲーム木における最善手探索 (計算機科学とアルゴリズムの数理的基礎とその応用)
- DS-1-10 文字列パターン上の同値関係と飽和パターンの列挙(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- Predicting like the best pruning of a decision tree
- Practical Algorithms for Pattern Based Linear Regression (テーマ:特集「シンボルグラウンディング問題」および一般)
- エネルギー複雑度を用いた線形決定木の下界導出
- 類似性指標を用いた楽曲のジャンル分類 (「メディアとAI」および一般)
- ブール関数のフーリエ変換とその応用
- SVMによるバイパータイトランキング学習を用いたコンピュータ将棋における評価関数の学習
- 非線形コラージュシステムにおける文字列パターン照合
- 非線形テキストにおける最長共通部分文字列・部分列アルゴリズム
- MDL原理に基づいた決定木枝刈りアルゴリズムのシミュレーション
- エネルギー複雑度を用いた線形決定木の下界導出
- 複数の予測戦略を統合する実時間予測アルゴリズム(計算理論とその応用)
- 複数の予測戦略を統合する実時間予測アルゴリズム
- Online Prediction under Submodular Constraints (情報論的学習理論と機械学習)
- ブールドメイン上の関数に対するサンプリングの定理
- 決定木に基づいたオンライン学習アルゴリズム
- Efficient AUC Maximization by Approximate Reduction of Ranking SVMs (情報論的学習理論と機械学習・第15回情報論的学習理論ワークショップ)
- DNF式の学習可能性
- 劣モジュラ制約下におけるオンライン予測(機械学習一般とその応用)
- 非定常な木情報源に対応する文脈木重みづけ法に関する研究
- ランキングSVMの近似に基づく効率的なAUC最大化(第15回情報論的学習理論ワークショップ)
- バイアス付きPassive-Aggressiveアルゴリズム
- 類似度に基づくポリフォニックな楽曲の分類
- SVMによる2部ランキング学習を用いたコンピュータ将棋における評価関数の学習(情報・システム基礎)