簡潔データ構造を用いた大規模かつ高速な機械学習手法の研究

本年度はこれまでの研究のまとめを行った。大規模な木構造カーネルのサポートベクターマシン(SVM)学習問題に対し、簡潔データ構造を用いた高速かつ省メモリな学習アルゴリズムを考案し、かつその性能を理論、実験の両面から評価を行った。この研究の意義は主に以下の２点である。１点目は木構造カーネルのSVMの学習問題に対する高速化である。一般にカーネル法を用いたSVMの学習時間はデータ数nに対し、O(n)の計算量がかかる。提案アルゴリズムでは木構造の共通部分の数え上げを高速化することによってO(nlogn)の計算量を達成した。なおかつそのために必要な空間計算量は非常に小さく情報論的下限に漸近する。２点目は機械学習と簡潔データ構造という２つの分野をつなぐ研究であるということである。本研究はこれまで独立して研究されており、接点が全くなかった両分野を利用したはじめての研究である。

本年度はこれまでの研究のまとめを行った。大規模な木構造カーネルのサポートベクターマシン(SVM)学習問題に対し、簡潔データ構造を用いた高速かつ省メモリな学習アルゴリズムを考案し、かつその性能を理論、実験の両面から評価を行った。この研究の意義は主に以下の２点である。１点目は木構造カーネルのSVMの学習問題に対する高速化である。一般にカーネル法を用いたSVMの学習時間はデータ数nに対し、O(n)の計算量がかかる。提案アルゴリズムでは木構造の共通部分の数え上げを高速化することによってO(nlogn)の計算量を達成した。なおかつそのために必要な空間計算量は非常に小さく情報論的下限に漸近する。２点目は機械学習と簡潔データ構造という２つの分野をつなぐ研究であるということである。本研究はこれまで独立して研究されており、接点が全くなかった両分野を利用したはじめての研究である。