簡潔データ構造を用いた高速かつ省メモリな木カーネルの学習

DOI Web Site
  • 木村 大翼
    東京大学大学院情報理工学系研究科数理情報学専攻
  • 鹿島 久嗣
    東京大学大学院情報理工学系研究科数理情報学専攻

Bibliographic Information

Other Title
  • カンケツ データ コウゾウ オ モチイタ コウソク カツ ショウ メモリ ナ モク カーネル ノ ガクシュウ

Search this article

Abstract

<p>カーネル法は文字列、木構造、グラフ構造などの構造データに対する強力な学習手法であり、代表的な学習器としてSVMがある。しかし、一般にカーネル関数を用いたSVM学習の計算量は入力のデータ数nについてO(n^2)であり、大規模データに対する学習は困難である。本論文では木カーネルに着目し、切断法とXBWという簡潔データ構造を用いることでO(n)の計算量で非常に省メモリであるアルゴリズムを提案する。</p>

Journal

Details 詳細情報について

Report a problem

Back to top