全ての部分文字列を考慮した文書分類 岡野原 大輔 † 辻井 潤一 †‡§ † 東京大学情報理工学系研究科コンピュータ科学専攻 ‡ SORST, 科学技術振興事業団 § School of Informatics, University of Manchester { hillbig, tsujii }@is.s.u-tokyo.ac.jp 本稿では,全ての部分文字列が素性として利用される文書分類モデル,及びその効率的な学習,推定手法を提案す る.文書分類に有効な部分文字列は,単語と異なる場合や,署名やテンプレートなど,非常に長くなる場合が少な くない.しかし,部分文字列の種類数は文書長の二乗に比例するため,それらを素性として直接用いて学習する ことは,計算量的に困難だった.本稿では,テキスト長に比例する個数のみ存在する極大部分文字列に関する統 計量を扱うことで,有効な部分文字列を漏れなく