著者

木村 大翼 田中 久美子

出版者

一般社団法人 言語処理学会

雑誌

自然言語処理 (ISSN:13407619)

巻号頁・発行日

vol.18, no.2, pp.119-137, 2011 (Released:2011-09-28)

参考文献数

17

被引用文献数

1 1

---

本稿では,文書量に不変な定数を考える.このような定数には,言語や文書の複雑さや冗長性を定量化して捉える計算言語学上の意義がある.これらの指標は既存研究でさまざまなものが提案されてきたが,ほとんどの場合英語を中心とする小規模な文書を対象としてきた.本研究では英語以外のさまざまな言語や,大規模な文書も対象として扱い,主に先行研究において値が文長に依らないとされる 3 つの指標 K, Z, VM と本研究で新たに試みた指標である H と r の 5 つの指標に対し,値が一定となるかどうかの実験を行った.結果,値が言語の種類や文長に依らずに一定となる指標は K と VM の 2 つの指標であった.なおかつこの 2 つの指標の値には自然言語とプログラミング言語の間で有意な差が見られ,言語の複雑さや冗長性をある観点で表した指標となっていると考えることができる.

著者

木村 大翼 鹿島 久嗣

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.27, 2013

---

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

著者

木村 大翼 久保山 哲二 渋谷 哲朗 鹿島 久嗣

出版者

一般社団法人 人工知能学会

雑誌

人工知能学会論文誌 (ISSN:13460714)

巻号頁・発行日

vol.26, no.3, pp.473-482, 2011 (Released:2011-04-19)

参考文献数

26

被引用文献数

2 12

---

Kernel method is one of the promising approaches to learning with tree-structured data, and various efficient tree kernels have been proposed to capture informative structures in trees. In this paper, we propose a new tree kernel function based on ``subpath sets'' to capture vertical structures in tree-structured data, since tree-structures are often used to code hierarchical information in data. We also propose a simple and efficient algorithm for computing the kernel by extending the Multikey quicksort algorithm used for sorting strings. The time complexity of the algorithm is O((|T_1|+|T_2|)log(|T_1|+|T_2|)) time on average, and the space complexity is O({|T_1|+|T_2|)}, where |T_1| and |T_2| are the numbers of nodes in two trees T_1 and T_2. We apply the proposed kernel to two supervised classification tasks, XML classification in web mining and glycan classification in bioinformatics. The experimental results show that the predictive performance of the proposed kernel is competitive with that of the existing efficient tree kernel proposed by Vishwanathan et al., and is also empirically faster than the existing kernel.

著者

木村 大翼 鹿島 久嗣

出版者

人工知能学会

雑誌

人工知能学会全国大会論文集 (ISSN:13479881)

巻号頁・発行日

vol.26, 2012

---

カーネル法は木構造データに対する有望な学習手法であり木構造の有用な情報を捉え るために様々な木カーネルが提案されてきた。本論文では木構造の垂直方向の構造に 基づいた木カーネルに着目する。この木カーネルは木構造に対する拡張接尾辞配列 を用いて入力サイズの線形時間で計算が可能であるが、さらに本論文では予測時に おける計算がサポートベクトルの数に依存せずに高速に行うことが可能であることを示す。