社団法人

電子情報通信学会

信学技報

                    

半構造化テキストの分類のためのブースティングアルゴ リズム
拓

工藤

裕治

松本

Ý 奈良先端科学技術大学院大学 情報科学研究科 〒  奈良県生駒市高山町  Ý        ÝÝ
あらまし     近年 テキスト分類は  単純なトピック分類から 文のモダ リティ 意見性 主観性といった書き手の意図に基づく分類へと  そのタスクの多様化が進んでいる それに伴い 単語の集合  

を素性とする古典的手法では十分な精度を得にくくなっている 精度向上に

は  テキストの構造 構文レ イアウト  を考慮する必要があるが  恣意的に選択された部分構造のみを用いた手法が多い 本稿では  構造を考慮したテキスト分類 半構造化テキスト分類 に向け  部分木を素性とする

 

と  それを弱学習器とする   アルゴ リズムを提

案する また      を用いた  との関連性 及び本手法の利点について言及する 実
データを用いた実験により 提案手法の有効性を検証する
キーワード

テキスト分類 半構造化テキスト                      Ý    !"" "# $#"

"  %  $ "#   &!""'( &  ( $"  %    )   Ý        ÝÝ        

 !         #    

&   ( ' ! )    !

 *  

!   +  

 





!





$ " %      

 

Æ 





 

     $ 
 





 

                     $            "    

 

"  #                   







"

"   $ Æ     







 #     

 

"  #  

((  

! ,

"   

 は じ め に や  といった機械学習手法が テ
キスト 分類に応用され 多くの成功をおさめている   テキスト分類では 一般に単語の集合

!        以下  を素性として用い 政
治 経済 スポーツといったカテゴ リにテキストを分類する 個々の単語が これらのカテゴ リを特徴付けるのに十分な情報を与えるため  といった単純な素性でも十分な精度を達成できる一方 テキストマイニングの分野では 「お客様の声」や「現場の声」といったテキストデータから早期に危機の茅や要求を発見 分析するための要素技術が求められている 例えば コールセンターロ
グからの知識発見 自由記述アンケートや製品レビュー記事からの不満要素の発見といったタスクがそれにあたる これらのタスクでは 旧来の文書分類に典型的なカテゴ リは用いられず 主観的客観的に述べているのか ある製品を  誉めている
けなしているのか 背景結果結論を述べているのか といった書き手の意図に関するカテゴ リが使われる さらに 分類単位が 文書といった大きな単
位から パッセージ 文のような小さな単位に変化している これらは テキスト分類には変わりないが  といった素朴な素性では 高い精度が得られにくい 単純には 固定長の グラム 係り受け関係 係り元 係り先のペア  といった 有効そうな素性を発見的に追加することで ある程度精度向上が期待できる しかし これらの手法は タスク
依存性が強く テキスト分類全般に適用できる汎用的な手法とは言い難い
本稿では テキストが単語の集合であると仮定したり 部分構造を発見的に追加する従来法に対しテキストが持つ「構造」を直接考慮する学習 分類
アルゴ リズムを提案する ここでの構造とは 単語の系列 係り受け構造といったラベル付き順序木を指す この構造は 自然言語処理において一般的なものである さらに  !"! 文書もラベル付
き順序木として定式化できる以下 次章では提案手法の詳細 # 章でその実装方法について説明する $ 章で %% &% %' を用いた  と提案手法の関連性に言及する ( 章で評
価実験とそれらの結果を報告し ) 章でまとめる

 提 案 手 法
詳細に入る前に 木に対するいくつかの定義 表
記について言及する  準備［ 定義  ］ ラベル付き順序木
ラベル付き順序木は すべてのノードに一意のラベルが付与されており 兄弟関係に順序が与えられる木である ¾
［ 定義 * ］ 部分木 と  をラベル 付き順序木とする ある木  が にマッチする もし くは  が  の部分木である
+ とは  と  のノード 間に  対  の写像関数  が定義できることである ただし  は 以下の # つの条件を満たす   は 親子関係を保存する *  は 兄弟の順序関係を保存する # 
はラベルを保存する ¾
本稿では ラベル付き順序木を単純に順序木 もしくは木と呼ぶ  さらに 木  中のすべての部分木の集合を    +   +  さらに 木  の
ノード の数を  と表記する









    ラベル付き順序木の分類問題
ラベル付き順序木の分類問題 木の分類問題 とは  個の学習データ  +     から 分 

類関数   , を 導出することである ただし はラベル 付き順序木であり
 は 木  に付与されたラベルである こ
こでは * 値分類問題を考える 通常の学習 分類
問題との違いは 事例  が 数値ベクトルで表現されるのではなく ラベル付き順序木として表現される点にある   
   -%. /01 は  つの素性の有無に基づき分類を行う 単純なアルゴ リズムである -%.
/01 は 深さ  の -%. %% 決定木 と同一である .21% らは 個々の単語を  つの素性とする -%. /01 を用い テキスト分類を行っている  本稿では ラベル付き順序木の分類問題に対し 以下のような部分木の有無に基づく-%. /01 を考える
［ 定義 # ］ -%. /01  %% を ク
 および  を ラベル付き順序木 
ラスラベルとする 木を分類するための -%.
/01 を以下のように定義する  



 +









+


+  * 
+

 

 ¾

分類器のパラ メータは 木  と ラベル  の組
  である 以後 この組を ルール と呼ぶ -%. /01 の 学習は 学習デ ータ  +    に対するエラー率を最小にするルール 3 3 を導出することで実現できる

 



 




          Ü

ただし  は 全部分木の集合 素性集合 である +     ここで ルール    に対する   を以下のように定義する  

    +








 

 

*



 を用いると  の最小化問題は 以下の最大化問題と等価となる3 3 +  04     

本稿では エラー率最小のかわりに  の最大化を用いて -%. /01 の学習を定式化する    の適用
部分木を素性とする -%. /01 は  つの部分木の有無に基づき分類を行うため それ単独では精度が悪い しかし 
( を用いてその精度を向上させることができる  は 逐次
弱学習器 ここでは 部分木を素性とする -%.
/01 を構築し それらの重み付き多数決によって 最終的な分類器  を構成する  番目の弱学習
器は それぞれ異なった事例分布 重み  を用

いて学習され る  +         ただし



 
は 分類が困難な +   + 5 分布 
 



*

最右拡張 t’

事例に高い重みが与えられるように逐次更新される
弱学習器が無作為分類よりも精度が良いことさえ満足すれば 単一の弱学習器より  の汎化能力が高くなることが理論的に証明されている (-%. /01 を弱学習器とする  を構築するには 分布  を考慮するよう 式 * を再定
義すればよい



1 A

t

最右枝

1 A
2 B
3 C

2 B

4

3 C

5 A

C
4
5 A

C

7

6 B

1 A

6 B
2 B

4

3 C

5 A

1 A
2 B

4

3 C

5 A

C
6 B

C
7

6 B 7



  
+   







 

図

 

最右拡張



6 ( は 

の代表的なアルゴ リ
ズ ムで あ るが 本稿では 漸近 特性の 良さか ら%0 らによる 6.7 # を用いる

 実

装

 

本章では 最適なルール 3 3 を発見するための高速なアルゴ リズムを提案する 最適ルール発見問
題は以下のように定式化される
［ 問題  ］ 最適ルール発見問題
学 習デ ータ  +              
た だ し  は 順 序 木 
 は 木に 対
応 す る ク ラ ス ラベ ル     +   +
5 は 木 の 重 み が 与 え ら え た 時  を 最
大 に す る ル ー ル 3 3 を 発 見 せ よ た だ し3 3 +  04
   

 

 
  



     









 

 



 +



単純な方法は 全部分木を陽に列挙し そこから最大の  を与える部分木を選択することであろう しかし 部分木の個数は木のサイズに対し指数的に増えていくために こういったしらみつぶしの方法は実問題には適用困難である 実際に 木の集合から全部分木を完全に列挙する問題は 8 困難であることが分かっている
本稿では 最適ルール発見問題のための効率良いアルゴ リズムを提案する 提案手法は 以下の #つの戦略から構成される 基本的には 分枝限定法
 .2 /  の考え方と同一である（  ） 木の集合から 全部分木を完全に重複なく列挙するための正準的な探索空間を定義する（ * ）  で定義した探索空間を深さ優先探索し最大の  を与える部分木を発見する（ # ）  * だけでは 全部分木をしらみつぶしに列挙してることと変わりない そこで  の上限
値を見積もり 探索空間を枝刈りする
この # つの戦略について 順に説明する  部分木の列挙方法
6% と 9: は 木から その部分木を 完全に重複なく列挙するアルゴ リズム最右拡張をそれぞれ独立に提案している  # 最右拡張は 部分集合を列挙するアルゴ リズム % ; /0/
%% *
の部分木への自然な拡張となっている 最右拡張では まず サイズ  の木が列挙される そして サイズ   の木に  つのノードを追加することでサイズ  の木を構築する この手続きを再帰的に適用することで全部分木を列挙する しかし 任意の位置にノードを追加すると重複する木を生成してしまうため ノード の追加に一種の制限を設ける こ

図

最右拡張の再帰 探索木の制限が最右拡張の鍵となるアイデアである 以下に最右拡張の定義を与える
［ 定義 $ ］ 最右拡張 木  に  つのノード  を追加して得られる順序木
 を 木  の 最右拡張と定義する ただし ノードの追加には以下の制約がある  ノードは  の最右枝 ルートから常に右端のノード を葉まで選ぶ
に追加される * 追加されるノード は 最右の兄
弟 末弟 である ¾
図  に最右拡張の例を示す 便宜上 木  は前順
序 1%% でノード に順序が付与されているものとする 図  の例では 位置 のノードが最右拡張で追加されるノード となる また 追加される位置の候補は # 種類 位置  $ ) あるが ラベルの候
補集合を考えると ラベルの種類数
位置数 図 では  # + < 通りの木  が 最右拡張より生成される
さらに 最右拡張を 再帰的に適用することで 一種の「探索木」を構築するとができる 図 * に その探索木の例を示す 図 * 中では 便宜的にラベルの種類を  種類のみとしている この探索木を探索することで 全部分木を 完全に重複なく列挙で
きる





 

  探索空間の枝刈り

前章で定義した探索空間を分枝限定法  .2
 /  の考えに従い枝刈りする 本章ではその具体的な手法について述べる 定理  
2 < の拡張 は  の全上位木    + に対する     の上限値を与える
［ 定理  ］  の上限値, 
 の 全 上 位 木       に つ いて+ル ール     の  は  を 上 限 値と す る   
+  ただし  は 以下で 与
えられる




+ 04 *



 

*
 


+Ü













 



 






 =

 
+Ü









#

証明






    



ここで


 



Ü

  



    の場合に着目すると      
Ü









¼



 



 



  
Ü
¼












 

 

∵





Ü 







 





 


Ü





 





   
 について   
Üが成立するため

 

 

の全上位木

  
Ü


 
¼








 

 

同様に





    
 



Ü 

以上より  の全上位木  
 




    






 



 





について







    

¾

定理  より  の上限値が与えられるので 分枝限定法を用い 探索空間を枝刈りすることができる 具体的には まず 最右拡張が定義する探索空間を深さ優先探索しながら 準最適  これまで探索した中で最大の    と それに対応する準最適ルールを保持する もし       となるようなルールが探索中に見つかれば 準最適ルー
ル 準最適解をそれぞれ更新する
ここで 木  について もし  +  ならば  の全上位木  の  は  以下であるため  が張る
部分空間は安全に枝刈りできる 逆に    ならば        となる上位木  が存在する
可能性があるため 枝刈りできない また   となり ノード  が 木  に最右拡張により追加される場合でも    ならば 拡張された木  が張る部分空間を枝刈りできる

 





ムである  は  ノルム  は  ノル
ム 文献 5 では このノルムの違いを モデルのスパース性という観点で議論している 詳細は 5
に譲るが  は 事例スパースの解を導出し できるだけ少数の事例でモデルを表現しようとする の分離平面  は 学習事例の線形結合で与えられ 非 5 の係数が付いた事例が サポート ベク
ターと呼ばれるのは上記の理由からである 一方 は 素性スパースの解を導出する つまりできるだけ少数の素性で  を表現しようとする と  を精度という観点で比較することは タスク依存性が強いため ここでは行わない しかし  を用いる提案手法は スパー
ス素性の性質から 以下のような「現実的な」利点がある
解釈のしやすさできるだけ少数の素性で分類し 分類自身が陽に実行されるため どのような素性が分類に使用されているか 分類に寄与する素性は何か といった分析が行いやすい  では 素性空間が陰に表現されるため そのような分析を与えにくい
高速な分類
スパースな素性空間は 高速な分類を可能にする
%% &% %' の計算量は  
 である ただし  とは内積をとる * つの木である さらに &% %' 法に基づく分類アルゴ リズムはサポー
トベクターの数  に依存する つまり  の
分類コストは   となり非常に大きい
この問題は 実際の応用において障壁になっている  との関連性
 は &% %' 関数と組み合わせることで 任意の構造を持った事例を学習 分類できる ラベル付き順序木を分類するための &% %' として %%&% %' $ > があり 全部分木を個別の素性とするような写像関数を与える 部分木を最小単位の情報として用いていることから 部分木を素性とする-%. /01 と %% &%  %' に基づく は 素性空間という観点において 本質的に同一であるといえる* つのアルゴ リズムの違いは マージンのノル 実験と考察  実験環境 設定
実験は 以下の * 種類のタスクで行った 8 レビュー分類  8 ユーザに 良い点悪い点を区別してレビューを投稿するよう指示した掲示板のデータである 分
類単位は「 文」 文数は ( $ カテゴ リは「 良い点」「悪い点」の * つである 文のモダ リティ分類 
被験者  名が 田村ら $ の大分類に従い << 年毎
日新聞の社説からランダムに選んだ )5 記事に 文
単位のモダリティ付与したデータである 分類単位
は「 文」 文数は  5 カテゴ リは 「 意見」「断定」「叙述」の # つである# つのタスクのデータの一例を図 # に示す文の表現方法として 以下の # つを用いた     ベースライン
構造は考慮せず 単語の有無を素性とする 具体
的には まず ?2% （ 注  ）を用いて単語を切り出す
ただし 単語の表層形ではなく 原形を用いた  提案手法では サイズ  の構造のみが素性集合となる
これは %4%  と同一である 係り受け 
単語単位の係り受け構造として文を表現する 具体
的には ??2（ 注  ）を使い 文節単位の係り受け  !"# $ !"%&' &'()*!+(

（注 ）
：
（注 ）
：

$

PHS
mod

良い点 メールを送受信した日付、時間が表示されるのも結構ありがたいです。
悪い点 なんとなく、レスポンスが悪いように思います。
断定 「ポケモン」の米国での成功を単純に喜んでいてはいけない。
意見 その論議を詰め、国民に青写真を示す時期ではないのか。
叙述 バブル崩壊で会社神話が崩れ、教育を取り巻く環境も変わった。
:
:

:
:
:

図  データの例

構造を導出した後 単語 原形 単位の係り受け構造に変換する 基本的に 文節中の単語は直後の単語に 文節中の最後の単語は係り先文節の主辞となる単語に係るものとする また 文頭 文末にはダ
ミーのノード を置くグラム  !
各単語 原形 の係り先が 直後の単語であるとみなした係り受け木である 任意の部分木は 単語 
グラムになる
これらのデータ 文の表現方法を用い 提案手法
  と %% &% %' による  の比較実験を行った %% &% %' には 文献 > で提案されている部分木のサイズに対する事前分布や 親子間の伸縮等は考慮せず 全部分木に展開するオリジナ
ルの %% &% %' を用いた  これは 学習に使われる素性を同一にし 比較を公平にするためである
複数クラスの分類には * 値分類器を多値分類問題へ拡張する手法の  つである  %@% を用いた 
評価は (' 交差検定により得られた A 値の平均にて行う  のソフトマージンパラメータ 及び 
の繰り返し回数は それぞれ適当に変化させながら テストデータに対する精度を最良にする値を採用した（
 注  ） 即ち それぞれ最良かつ公平な条件での比較を行う  実 験 結 果
表  * に 8 - の実験結果を示す  は提案手法    は  を用いた結果である

表



結果 

表  

値

!""
!%&
#$
 !%

!!
#$
!!
 !%'


#$
#$

結果 ()*

 ()*
断定

意見

叙述

! 
+!,
+!"
! 
+ !
+ !

" 
+&,
!+'
,%
"
"

+&
% %
% %
+ ,
++
++

  考察   構造を考慮する有効性
全タスクにおいて 構造を用いないベースライン に比べ 構造を考慮する提案手法が顕著に精度が高いことが確認できる 係り受け %1 と 
グラム  0 を比較すると - タスクの「意見」カテゴ リにおいて 係り受け構造を用いるほうが精度が良いが 全般的に顕著な差は確認できない

,（注 ）：これらのパラメータは 正則化の強さをコントロールするという意味で同種のものである   %% &% %' を用いた  との比較
 を素性とした場合  と  には顕著な差は確認されない %1
0 を用いた場
合でも 提案手法が同一かそれ以上の精度を示している しかし  の場合 カテゴ リによっては著しく精度が悪い このような顕著な精度低下の要因として %% &% %' をはじめとする ? @'/&% %' 全体が持つ欠点が挙げられる 言語データといった疎データに ? @'/ &% %' を用いると 素性数が指数的に増えるため 自分以外との内積と比較して 自分自身との内積が極めて大きくなる傾向にある これにより 学習事例に酷似した事
例のみを分類し 残りはデフォルトクラスに分類するような丸暗記学習が行われやすくなる これを回避する方法として  大きな部分構造の重みを減衰させる > * 正規分布の分散と同形の平滑化を与える ) # カイ * 乗値により素性選択する * といった手法が提案されている これらの手法を用いることで 提案手法より高い精度を得る可能性がある しかし これらの手法の目的は あくまでも精度向上であり 提案手法の持つ利点 「高速分類」「解釈のしやすさ」の実現ではない また 学習の素性空間が大きく変わってしまうため 素性空間が同一という条件での公平な比較ができない さらに減衰率といった設定すべきパラメータの数が増えるという意味で問題が複雑になってしまう   提案手法の利点$ 章にて 提案手法の「 現実的な」利点について述べた ここでは 実験結果 8 から それらの利点を検証する
提案手法は 必要最小限の素性を自動的に選択する能力を備える 8 タスクにおいて 実際に使われた素性 サポート素性 の数は  <# であり 人手による分析に耐えうるサイズであった 学習データから抽出した全  0 * 0 # 0 の異なり
数がそれぞれ $ * *$ *5) $# )(> であることから いかに少数の素性で分類を行っているかが分かる もし  のサポートベクターの集合から サ
ポート素性を列挙すると 数十万から数百万の素性数になると予想される
サポート素性の分析の例として 図 $ に 個々のサポート素性 と  が算出した素性
重み ! の一部を示す
6「 〜し  にくい」を含む素性「 〜し  にくい」は 一般に否定的な意味の形容詞であり 多くの素性は負 悪い点 の重みが与えらえている しかし 「 切れにくい」のみ正の重みとな
り ド メイン知識 8 をよく反映している「使う」を含む素性「 使う」は 評判には中立な意味の単語だが 周辺のコンテキストで重みが変化している 「使いたい」

(→正 「使いやすい」→正 さらに 過去形 「使いやすかった」 になったり 他の要素との比較 「 〜の〜する 方が使いやすい」 になると 負の重みが与えられており 興味深い?「充電」を含む素性ド メイン知識を反映した素性 「充電時間が短い」→正 「充電時間が長い」→負 が抽出されている
また これらは係り受け構造を考慮した素性である（ 注  ）

「にくい」を含む素性
切れる にくいにくい EOS 。
にくい なる たにくい 。
読む にくいにくい なる使う にくいにくい
C. 「充電」を含む素性
0.0028 充電 時間 が 短い
-0.0041 充電 時間 が 長いA.

0.004024-0.000177-0.000552-0.000566-0.000696-0.000738-0.000760-0.001702「使う」を含む素性
使う たい
使う
使う てる
使う やすい使う やすい た使う にくいは 使う づらい方 が 使う やすいを 使う てる た
PHSデータ
単語単位の係り受けB.
0.002730.000150.000130.00007-0.00010-0.00076-0.00085-0.00188-0.00233

ルール中の素性は係り受けのパス)
(dep)

(

図 ' サポート素性の一部

さらに 図 ( に分類の実行例を示す 入力文「液晶が大きくて 綺麗 見やすい 」に対し ど ういう素性が適用されたか陽に出力し 分析を容易にしている このような分析は %% &% %' では困難である

ズムを拡張し 弱学習器の効率良い学習分類手法を提案した 実データを用いた実験にて 文の構造を考慮する本手法の有効性を示した さらに 提案
手法の * つの利点 解釈のしやすさ 高速分類 を実タスクにおいて確認した

謝

辞文のモダリティ判別データを 
コミュニケーション科学基礎研究所の平尾努氏に提供していただ
きました ここに感謝いたします
文

献- . /0 1 20 /  3 1 45 1 #  15  )$6#7 #783 9 47## :        && - .  ; 3#<Æ73 
 $ 9 # : 

       !
 "        #     

1=(  %%+-. >  #7  # 72 $  " #  
! ? '% @, + %%%
-'. (72 = # A *B3 =8
5 9   :   $  "#    % # &$' && -,. C8 # #  < 72$ 1#7427 6 9 4 #  $$7  (  "  #    % #   

適用された素性とその重み λ事例

分類結果
図,

分類の実行例-注 前順序の  式で木を表現しているため 語順が逆になる.
最後に 分類速度であるが 提案手法の分類速度が 5#( 秒 $< 事例に対し  は ( <秒 $< 事例 であった（ 注  ） 提案手法がおよそ $55
倍高速であることが確認された

 おわりに
本稿では テキストの構造 構文構造やレイアウト
構造 を考慮したテキスト分類 半構造化テキスト分
類 に向け 部分木を素性とする -%. /01
と それらを弱学習器として用いる 
アルゴ リズムを提案した さらに 部分木列挙アルゴ リ/（注 ）：「充電時間がとても短い」は 係り受けパターンならマッ グラムだとできない
（ 注 0）： 1 #/2 主記憶 /3+4 の '5 上で測定
チできるが

した

,, ? %@ % %%"-". *8#  =8 5  #4
7 7 727 $ D= 
=6 D=4=>4%%4 &%%%-!. 2 ;72 E 76 2
$$ 87 72?  2 3
8 9 :     )!
 $ !@ ' %%+-+. 2 /2 #  /3 8
5 9 47# # :  !
   )!*++* $ % @ %+ && -%. 272 (22 =$ $ 234$2 Æ73 9  :   , %   $ '! @'+  $
&& - &. F G72 -.  / , , 0 #1  2* 2 *$ 9 =4$ 77 D83 9 # && 
- .  < 72$ # C  4E? 1 4# 3 9 E 74
6   )  %  ? ,@ "+&&&- . ; 65   #5 :65# <5 (#  5 2 94 7 97  ;$  : ( 2  " -  *++3!4!5*6*++3!$)!
75 &&- . (2# H5 <Æ73  9I   9 :      !

   "     8"  ,!
%      $ ! @+& && - '. 田村直良 # 和田啓二 セグ メントの分割と統合による文章の構造解析 自然言語処理 ,%%")