Information Retrieval and Web Search まとめ(18): テキスト分類(2)

前回は、テキスト分類タスクとナイーブベイズについて説明した。今回は決定木によるテキスト分類についてまとめる。

この記事は Information Retrieval and Web Search Advent Calendar 2020 の18日目の記事です。

adventar.org

テキスト分類の評価用データセット

• Reuters-21578
  • 最も使われているデータセット
  • 文書数: 21,578
  • カテゴリ数: 118
• Reuters RCV1
  • 文書数: 810,000
  • 比較的新しいデータセット

決定木によるテキスト分類

• 内部ノード (internal node) には、タームがラベルとしてついている
• 枝 (branch) にはタームの重み（もしくは単に存在するかしないか）がラベルづけられている
  • 重みがある値以上なら右、それ未満なら左、というように
• 葉 (leaf) にはカテゴリがラベルづけられている
• 決定木による分類器は、木を下にたどりながら、文書をカテゴライズする
  • 葉についているラベルをその文書のカテゴリとする
• ほとんどの決定木は二分木

決定木の例

• 決定木はナイーブベイズと同様に、人間にとって解釈が容易
  • 決定木からルールを取り出すこともできる

決定木の学習

• トップダウンに貪欲的にノードの分岐を学習していく
  • まだ使われていない特徴量のうち、もっとも情報利得 (information gain) が大きいものを選ぶ
• 葉にはカテゴリの二値 (yes/no) かカテゴリの確率 P(class) を置く

決定木の学習

• k 個の特徴量がある場合、最大で 2k 個のノードをもつかもしれない
• もっと小さい木で表現したい
• 各ノードで、再帰的にもっともよい分割を選択する、というのを貪欲的に繰り返すことによってこれを実現する
• 分割のよさをどのように計算するか？
  • 以下で説明する情報利得が最大になるような特徴量 f を選ぶ

情報利得

• クラスのエントロピー (entropy) は以下のように定義される
  • を、クラス のサンプルの割合とする

• 次に、各ノードにおける、クラス の特徴量 による分割を考える
  • を、クラス の特徴量 をもつサンプルの割合とする
  • を、クラス の特徴量 をもたないサンプルの割合とする
• でのノード分割のあと、エントロピーは以下のようになる

• 情報利得 (information gain) は で定義される
  • 情報量 = -エントロピー

数値特徴量

• TF-IDF のような数値の特徴量の場合、どの値で分割するか？
• ビン (bin) に離散化する
  • k 個のビンに入れ、カテゴリ特徴量のように扱う
  • ビンはデータセット全体の統計量をもとに決める (k-means でのクラスタリングなど)

ノード分割の停止

• 以下の場合、分割を止める
  • あるノードにおいてサンプルがすべて同じクラスになった場合
  • 木があらかじめ決められた深さ d に達した時
  • 分割による差分が統計的に有意でなくなった時
    • カイ二乗検定 (chi-square)、フィッシャーの正確確率検定 (Fisher's exact) など
• 検証セットを使って木を最適化する
  • まずは大きい木を作る（深さの閾値 d によって止まる）
  • 検証セットを使い、ボトムアップでノードを枝刈りする
    • 葉のほうのノードから始めて、検証セットのデータで分類精度が（統計的に有意に）上がらないノードは除去
  • 木が深くなるとバイアスは減り、バリアンスは増える

クラスごとの評価指標

• 再現率 (recall)
• 精度 (precision)
• 正解率 (accuracy)
• マイクロ平均 (microaverage)
• マクロ平均 (macroaverage)

アンサンブル

• シンプルで弱い (weak) 学習器を集め、その結果をまとめて1つのもっとよい学習器として利用する
• アンサンブルの種類
  • バギング (bagging)
  • スタッキング (stacking)
  • ブースティング (boosting)

ランダムフォレスト

• 元のデータセットからサンプリングされたデータセット (bootstrap sample) を使い、 K 本の木をつくる

Boosted Decision Tree

• ランダムフォレストとは別の方法（こちらのほうがより新しい）

文書のテキスト分類の諸問題

データ量

カテゴリ数

概念ドリフト

• カテゴリは時間の経過とともに変わっていく
• 例：「アメリカの大統領」
  • 1998 年には "clinton" はいい特徴量だったが、2018 年ではそうではない
• 概念ドリフトに対する頑健性もテキスト分類システムにとっては重要
• 特徴選択をすると、概念ドリフトに弱くなる可能性がある

講義資料

• Decision trees and machine learning on documents

参考資料

• IIR chapter 15
• Reuters-21578
• A tutorial on support vector machines for pattern recognition (Burges 1998)
• Using SVMs for text categorization (Dumais 1998)
• Inductive learning algorithms and representations for text categorization (Dumais et al. 1998)
• A re-examination of text categorization methods (Yang et al. 1999)
• Text categorization based on regularized linear classification methods (Zhang et al. 2001)
• A loss function analysis for classification methods in text categorization (Li et al. 2003)
• Trevor Hastie, Robert Tibshirani, Jerome Friedman. Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer-Verlag,New York, 2001.
• Thorsten Joachims. Learning to Classify Text using Support Vector Machines. Kluwer, 2002.