コーパス内の単語共起関係を用いた文書分類

この記事は[scouty Advent Calendar](https://qiita.com/advent-calendar/2018/scouty)の9日目の記事になります。

今回は、**コーパス範囲での単語共起関係**を用いて文書分類問題に挑戦し、SOTAを達成した手法を紹介したいと思います。

本手法は、以下の論文で発表されてあり、すでにソースコードも共有されています。
[Graph Convolutional Networks for Text Classification](https://arxiv.org/pdf/1809.05679.pdf)
[ソースコード](https://github.com/yao8839836/text_gcn)

# 背景
文書分類問題を解決するために、いろんな視点から取り込みがあります。その一つの視点が単語の分散表現に関する取り込みで、bag-of-words, n-gram, entities, word2vecなど様々な手法が提案されてあり、文書分類問題において、まず文書を単語や文書の分散表現に変換し、更に具体的な分類手法で取り込むのが一般的な流れになっています。 

もう一つの重要な視点は、ニューラルネットワークを用いた取り込みで、単語や文書の分散表現に加え、単語の順序関係(word order)や意味的、構文的関係(semantic and syntactic information)を考慮しているため、良い分類結果を出しています。しかし、これらの取り込みで考慮しているのは、あくまでも文(sentence)範囲や段落(paragraph)範囲での単語間の関係で、コパース範囲での関係ではありません。

本手法では、単語の分散表現を事前に学習することなく、コーパス範囲での単語共起関係のみを使って、文書分類問題を解決しようとしています。

# 本手法の特徴

1. 既存の手法では、文内の意味的、構文的関係を学習しているのに対して、本手法では**コーパス内の単語共起関係を用いて
non-consecutive and long-distance semanticsをキャプチャ**します。
2. 本手法は文書分類モデルを構築すると同時に**単語分散表現と文書分散表現も学習します。**

# 手法の詳細
## データの作成
コーパス範囲での単語共起関係を学習する為に、本手法では単語や文書からなる **グラフデータ構造** を扱います。グラフ構造を採用することで、各単語や文書が持つ分散表現に加え、グラフ頂点間の情報伝搬により伝達される情報も学習対象になります。

作成されるグラフデータにおいて、コパス内で出現した全ての単語と文書がグラフ頂点になります。頂点間を繋ぐ辺としては、単語と単語、単語と文書間の二種類が存在し、それぞれ以下のルールによって生成し、重み付けられます。

**単語と単語間の辺**
- 生成ルール： 全コーパスにおいて、単語間で共起関係が存在する場合、単語頂点間で辺を引きます。
- 重みルール：
1. 一定長さのスライディング・ウィンドウ(sliding window)を定義し、コーパス内で順次移動させながら、スライディング・ウィンドウの長さ分のトークンを収集します。

  例えば、「自然言語処理は面白い分野です。」という文書を長さ2のスライディング・ウィンドウで処理すると[自然言語処理、面白い]、[面白い、分野]のようなトークンが収集されます。
2. スライディング・ウィンドウ数を用いて、以下の式で単語間辺の重みをきめます。

```math
PMI(i, j) = \log \frac{p(i, j)}{p(i)p(j)}
```

```math
p(i,j) = \frac{\#W(i,j)}{\#W}
```

```math
p(i) = \frac{\#W(i)}{\#W}
```

ただし、$\\#W$はスライディング・ウィンドウの数、$\\#W(i)$ は単語 $i$ を持つスライディング・ウィンドウ数、 $\\#W(i, j)$ は単語 $i$, $j$ を同時に持つスライディング・ウィンドウ数を指します。

[PMI(Point-wise mutual information)](https://en.wikipedia.org/wiki/Pointwise_mutual_information)は自己相互情報量のことで、以下の意味を持ちます。
- 正の場合、$i$,$j$が共起しやすい傾向にある
- 負の場合、$i$,$j$が共起しにくい傾向にある
- 0の場合、$i$,$j$が独立に出現する


**単語と文書間の辺**
- 生成ルール： 単語が文書内で出現した場合、単語と文書頂点間で辺を引きます。
- 重みルール： [TF-IDF](https://ja.wikipedia.org/wiki/Tf-idf)を用いて重みをつけます。

結果、以下のような隣接行列を持つグラフデータが作成されます。 グラフ辺の重みの意味から、出現頻度が高い単語と該当文書が繋がっていて、かつ一緒に出現しやすい単語同士が繋がっているグラフデータが作成されるのがわかります。

```math
A_{i,j} = \left\{
\begin{array}{ll}
PMI(i, j) & i,jが単語、PMI(i,j)>0 \\
TFIDF(i,j) & iが文書、jが単語 \\
1 & i = j \\
0 & otherwise
 \end{array}
\right.
```

## ネットワークモデルの構築
本手法ではモデルとして、2層のGCN(graph convolutional networks) layerからなるニューラルネットを考えます。GCNは2017年Kipfらによって提案されたグラフ畳み込みニューラルネットワークで、GCN layerを一つ加えることによって、グラフ上の各頂点が持つ情報が隣接頂点に伝搬されることになります。

本手法の場合、2層のGCN layerを使っているため、各文書が持つ情報が隣接単語頂点を通して、隣接単語の隣接文書頂点に伝搬されることになります。

詳細の説明は省略しますが、本手法のネットワークモデル( $Z$ ) と損失関数 ( $L$ ) は以下のように定義されます。(GCNに関する論文や解説記事は参考文献にまとめておきました。)

```math
Z = softmax(\tilde　A ReLU( \tilde　A X W_0) W_1)
```

```math
\tilde A = D^{-\frac{1}{2}} A D^{-\frac{1}{2}}
```

```math
D_{i,j} = \sum_j A_{i,j}
```

```math
L = - \sum_{d\in y_{D}}\sum_{f=1}^{F} Y_{df} ln Z_{df}
```
ただし、$X$は入力される文書の分散表現で、$W_0$, $W_1$はモデルで学習する重みになります。。まだ、$y_{D}$はラベルを持つ文書の索引集合、$F$は出力の次元を指します。

まだ、定義の中で、$E_1 = \tilde A X W_0$ が第一レイヤから得られる単語や文書の分散表現になり、 $E_2 = \tilde　A ReLU( \tilde　A X W_0) W_1$が第二レイヤから得られる単語や文書の分散表現になります。

上記の２層ネットワークを図で表すと以下のようになります。
![スクリーンショット 2018-12-09 22.41.13.png](https://qiita-image-store.s3.amazonaws.com/0/77744/d4edb65e-92bb-848b-dcd5-131ce36f9363.png)

# 実験
論文では本手法の有効性を表すために、他手法との比較、スライディング・ウィンドウサイズ、単語・文書分散表現の次元変化による精度の変化、モデルで学習されてた分散表現の有効性、ラベル付きデータの割合が学習に対する影響など、様々な面から実験されています。

この記事では、他手法との比較結果と分散表現の有効性検証結果のみを記載します。

### 他手法との比較
![スクリーンショット 2018-12-09 22.53.06.png](https://qiita-image-store.s3.amazonaws.com/0/77744/7ac1f8a1-edef-ac09-37ac-06ae0cc6192b.png)

各比較対象となっている手法の詳細は省略しますが、結果からCNN、LSTM, Bi-LSTMなどの手法より良い精度を出しているのが見えます。ただ、MRデータセット(映画レビューデータ)に対しては、CNNやLSTMに負けているのですが、これは本手法で単語の共起関係は考慮しているが、センチメント分析で重要な順序関係は無視しているためであると解釈されています。

### 学習された分散表現の有効性
![スクリーンショット 2018-12-09 23.06.30.png](https://qiita-image-store.s3.amazonaws.com/0/77744/8380ea40-5ad8-6694-6a50-8c9ce95b9e4a.png)

[20NG(20 newsgroups, 約20000文書、20カテゴリのデータセット)](http://qwone.com/~jason/20Newsgroups/)データをモデルに投入した時の学習された文書分散表現を可視化した結果になります。結果から、PV-DBOW手法,　本手法の第一レイヤ、本手法の第二レイヤの順により区別の付く文書の分散表現が学習されていることがわかります。

![スクリーンショット 2018-12-09 23.14.58.png](https://qiita-image-store.s3.amazonaws.com/0/77744/1518d0ad-ec7b-aab1-11f5-b02750ffb479.png)

更に、単語の分散表現を可視化してみても、単語が所属する文書クラスごとに分類されてあることがわかります。

![スクリーンショット 2018-12-09 23.20.23.png](https://qiita-image-store.s3.amazonaws.com/0/77744/b911e1c1-e454-6902-9bda-8793f4a07140.png)

最後に、各文書クラスでもっとも高い値を持つ単語を並べて見ると、例えばcomp.graphicsクラスの場合、jpeg, graphics, imageなどそれらしい代表的な単語が集まっているのが見えます。

# 感想
- 個人的には、コーバス範囲での共起関係を考慮したというところが斬新的でした。
- 論文では記載されていないですが、コパースに置ける全単語と文書を対象に$PMI$, $TFIDF$を計算しなければならないので、かなりの処理時間が必要になるのではないかと推測しています。
- グラフデータを扱うアルゴリズムだと大体直面する問題だと思いますが、本手法でも全く未知のデータに対する予測ができないところが残念です。streaming処理にも対応できるように拡張されれば実用性が一気に上がると思いました。
- 短い文書からなるデータだと辺の数が少なくなるため、情報伝搬がうまく行かず精度が下がると思いました。

# 最後に
今回は準備不足で、非常にざっくりした感じで論文を紹介しました。しかし、自分でコードを修正したり、他のデータでいじって見たりと色々やっていますので、何かあればコメント残して下さればしょぼい経験でも共有します。

更に、本手法に関しても、自然言語処理に関しても本記事で何か見違ったことを書いていれば指摘してくださると幸いです。


# 参考資料
[Graph Convolution Networks関連論文まとめページ](https://github.com/sungyongs/graph-based-nn)
[Semi-Supervised Classification with Graph Convolutional Networks](https://arxiv.org/pdf/1609.02907.pdf)
[機は熟した！グラフ構造に対するDeep Learning、Graph Convolutionのご紹介](https://tech-blog.abeja.asia/entry/2017/04/27/105613)
[グラフ構造を畳み込む -Graph Convolutional Networks-](https://qiita.com/tktktks10/items/98d21133cf3e121676c3)
[Deeper insights into graph convolutional networks for semi- supervised learning.](https://arxiv.org/pdf/1801.07606.pdf)