部分パスに基づいた線形時間木カーネル(ポスターセッション,第14回情報論的学習理論ワークショップ)

スポンサーリンク

概要

• 論文の詳細を見る

• カーネル法は木構造データに対する有望な手法の一つであり,木構造の有用な情報を捉えるためにこれまで様々な高速に働く木カーネルが提案されてきた.木稿ではそれらの木カーネルの中でも,特に木構造の垂直方向の特徴である「部分パス」を用いた木力ーネルに着目する.この部分パス木カーネルは他の木カーネルと同等以上の予測性能を示し,なおかつVishwanathanらによって提案された線形時間木力ーネルよりも実験的には高速であるが,その時間計算量はO((|T_1|+|T_2|)log(|T_1|+|T_2|))であり,オーダーでは遅い.ここで|T_1|と|T_2|はそれぞれ2つの木構造のノート数である.そこでわれわれは文字列カーネルの線形時間計算アルゴリズムの考え方を木構造に対して拡張し,部分パス木カーネルの効率的な計算アルゴリズムを新たに提案する.提案アルゴリズムは木構造に対する接尾辞配列を用いるものであり,時間計算量と空間計算量はともにO((|T_1|+|T_2|)である.人工データに対して実験を行ったところ,提案する線形時間アルゴリズムの計算時間は木構造のノート数に対して線形にスケールした.

• 2011-11-02

著者

• 鹿島 久嗣

  東京大学大学院情報理工学系研究科

• 鹿島 久嗣

  日本アイ・ビー・エム株式会社

• 鹿島 久嗣

  日本アイ・ビー・エム(株)東京基礎研究所

• 鹿島 久嗣

  日本ibm 東京基礎研究所

• 鹿島 久嗣

  京都大学大学院情報学研究科

• 木村 大翼

  東京大学大学院情報理工学系研究科

• 鹿島 久嗣

  東京大学大学院情報理工学系研究科:jstさきがけ「知の創生と情報社会」研究領域

• 鹿島 久嗣

  東京大学大学院 情報理工学系研究科

関連論文

• 現場発想による自然言語処理ブレークスルーの探求(平成21年度論文賞の受賞論文紹介)
• 教師付き学習を用いた教師なし変化解析手法(知識獲得,機械学習,情報爆発論文)
• ネットワーク構造の確率的な時変モデルに基づく教師ありリンク予測
• 複数生物種ネットワークの同時予測--半教師つき学習によるアプローチ (ニューロコンピューティング)
• 複数生物種ネットワークの同時予測--半教師つき学習によるアプローチ (非線形問題)
• リンク伝播法--リンク予測のための半教師付き学習法 (特集 「大規模データからの機械学習と自然言語処理への応用」および一般)
• 部分的かつ曖昧なラベル付き構造データからのマルコフ条件付確率場の学習(情報抽出・ラベル付与)
• カーネル法に基づく構造データのラベル付け学習アルゴリズム(「自動推論:帰納,演繹,モデル検査/生成,学習,発見,仮説推論、論理プログラム,プランニングetc.」及び一般)
• グラフとネットワークの構造データマイニング
• 日本語単語分割の分野適応のための部分的アノテーションを用いた条件付き確率場の学習
• 2.Becoming a Service Scientist(サービス・サイエンスの出現)
• 0. 編集にあたって(最新!データマイニング手法)
• 赤穂昭太郎, カーネル多変量解析-非線形データ解析の新しい展開-, 岩波書店, 2008年
• ネットワークデータを用いた分散システムにおける異常検出(データマイニング,データ工学論文)
• スプライスト・アライソメントに基づいたcDNAライブラリの正確なクラスタリング・アルゴリズム
• クラスラベル付きグラフデータからの有用なパターンペア発見 (特集 「医療及び化学情報マイニング」および一般)
• 動的計画法によるリターン分布推定(IBIS2010(情報論的学習理論ワークショップ))
• 木構造データに対するカーネル関数の設計と解析
• 半構造データへのサポートベクターマシンの適用 (テーマ:一般演題及び「webとtext」)
• グラフとネットワークの機械学習の確立を目指して : 受賞タイトル 構造データ解析のための機械学習手法(平成20年度長尾真記念特別賞紹介)
• ネットワーク構造予測(ベイジアンネットワークと確率的情報処理の新展開)
• カーネル法による構造データの解析(機械学習による自然言語処理・言語処理を利用したメディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
• カーネル法による構造データの解析(機械学習による自然言語処理・言語処理を利用したメディア理解, 学習理論とパターン認識メディア理解, 機械学習による自然言語処理・言語処理を利用したメディア理解, 一般)
• The 21st International Conference on Machine Learning (ICML) 2004 参加報告
• Web探訪 : カーネル法
• 電子調達オークションにおける最適な財の分配アルゴリズム
• 4. カーネル法による構造データマイニング(最新!データマイニング手法)
• 補助情報を用いたテンソル分解(主成分分析,テキスト・Webマイニング,一般)
• 複数情報源に対する主成分分析(主成分分析,テキスト・Webマイニング,一般)
• 文書量に不変な定数 : Yule の K, Golcher のVM
• 凸最適化に基づくテンソル分解の統計的性能について(機械学習とその応用)
• 構造データ解析のための機械学習法(学習と発見,人工知能分野における博士論文)
• 部分パスに基づいた線形時間木カーネル (情報論的学習理論と機械学習)
• 部分パスに基づいた線形時間木カーネル(ポスターセッション,第14回情報論的学習理論ワークショップ)
• クラウドソーシングを用いた教師付き学習の凸最適化による定式化(ポスターセッション,第14回情報論的学習理論ワークショップ)
• カーネル法に基づく行列あるいはテンソル補完(ポスターセッション,第14回情報論的学習理論ワークショップ)
• クラウドソーシングと機械学習(知識の転移)
• 部分パスに基づいた線形時間木カーネル
• 上位カテゴリにおける観測データが与えられる場合の行列およびテンソル分解法(行列分解,応用,統計推理,データベース,一般)
• クラウドソーシングを用いた教師付き学習の凸最適化による定式化
• Learning from Crowds and Experts
• 複数の関係データの関連を考慮した同時補完法(機械学習)
• ヒューマンコンピュテーション概説(ヒューマンコンピュテーションとクラウドソーシング)
• 1-5 ビッグデータに挑むクラウドソーシング(1.ビッグデータを読み解く機械学習技術,データを読み解く技術-ビッグデータ,e-サイエンス,潜在的ダイナミクス-)

もっと見る 閉じる

スポンサーリンク