著者

岡野原 大輔 辻井 潤一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告自然言語処理(NL) (ISSN:09196072)

巻号頁・発行日

vol.2008, no.90, pp.59-64, 2008-09-17

---

本稿では,全ての部分文字列が素性として利用される文書分類モデル,及びその効率的な学習,推定手法を提案する.文書分類に有効な部分文字列は,単語と異なる場合や,署名やテンプレートなど,非常に長くなる場合が少なくない.しかし,部分文字列の種類数は文書長の二乗に比例するため,それらを素性として直接用いて学習することは,計算量的に困難だった.本稿では,テキスト長に比例する個数のみ存在する極大部分文字列に関する統計量を扱うことで,有効な部分文字列を漏れなく求めることができることを示す.また,拡張接尾辞配列を用いることで,これらを効率的に列挙可能であり,全文書長に比例した時間で学習可能であることを示す.さらに L1 正則化を適用することで,コンパクトな学習結果が得られ,高速な推定が可能であることを示す.このモデルは,形態素解析結果や TF/IDF などの統計量と組み合わせられることを示し,従来の単語ベースの Bag of Words 表現と比較し,精度が向上することを示す.This paper presents a novel document classification method using all substrings as features. Although an effective substring for a document classification task is often different from tokenized words, the number of all candidate substrings is the quadratic of the length of a document, and a learning using all these substrings as features requires a prohibitive computational cost. We show that all effective substrings can be computed exhaustively by checking only maximal substrings, which can be enumerated in linear time by using enhanced suffix arrays. Moreover, we use L1 regularization to obtain a compact learning result, which makes an inference efficient. We show that many prior weights (tf, idf, other tokenized result) can be included in this method naturally. In experiments, we show that our model can extract effective substrings, and more accurate than that of word-base BOW representation.