[論文メモ] SCDV : Sparse Composite Document Vectors using soft clustering over distributional representations

# 前置き
- [SCDV : Sparse Composite Document Vectors using soft clustering over distributional representations](https://arxiv.org/pdf/1612.06778.pdf)
- [文書ベクトルをお手軽に高い精度で作れるSCDVって実際どうなのか日本語コーパスで実験した(EMNLP2017)](https://qiita.com/fufufukakaka/items/a7316273908a7c400868) の記事が圧倒的にわかりやすいのでそっちも見たほうがいいよ!!


# SCDVの概要
- document embeddingの新しい手法。文書分類だけでなく情報探索等にも活用できる。数値実験では既存の方法(doc2vec, LDA, NTSG)に比べ高い精度が出た。
- アルゴリズムのアイデアは、
    - 単語はトピックを持つ。
        - 医療、スポーツ、政治など
    - 文書に多く含まれるトピックと同じトピックを持つ単語のほうが影響力が大きい。
        - 医療の単語が多く含まれるとき、政治に関係する単語の影響力は小さくなる。
    - idf(逆文書頻度)が大きいほうが文書への影響力は大きい。
    - 絶対値が小さい要素はゼロにし、スパースなベクトルに変換する。

# SCDVのアルゴリズム
1. word2vec等で$d$次元の単語の表現ベクトル$wv \in R^d$を求める。
2. [Gaussian Mixture Model(GMM)](https://pdfs.semanticscholar.org/734b/07b53c23f74a3b004d7fe341ae4fce462fc6.pdf)で$K$クラスタへの単語のクラスタリングを行い、単語$w$がクラスタ$c$に属する確率$p(c|w) \in R$を求める。
3. 単語のIDFを求める。
4. word cluster vector ($wcv_{ik} \in R^d$)を求める。$wcv_{ik} := wv_{i} \times p(c_k|w_i)$. 
5. word topic vector ($wtv_i \in R^{K \times d}$ )を求める。$wtv_i := \text{idf}(w_i) \times \oplus_{k=1}^K wcv_{ik}$. (※ $\oplus$はconcatenationを意味する。)
6. document vector ($dv_{D_n} \in R^{K \times d}$ )を求める。 $dv_n := \sum_{w_i \in D_n} wtv_i$.
7. document vectorの絶対値がゼロに近い要素をゼロにすることsparse composite document vector $SCDV_{D_n} \in R^{K \times d}$を求める。

# SCDVを実装する前の準備
### word2vecで単語の表現ベクトルを求める方法
- gensimに実装されている。詳しくは[こちら](https://radimrehurek.com/gensim/models/word2vec.html)。

### Gaussian Mixture Modelを使ってp(c|w)を求める方法
- [Gaussian Mixture Models](https://pdfs.semanticscholar.org/734b/07b53c23f74a3b004d7fe341ae4fce462fc6.pdf)
- $p(w|\lambda) = \sum_{j=1}^K \pi_j p(w|\mu_j, \Sigma_j)$ をEMアルゴリズムやMAP推定を行えばよい。論文中に出てき下記の式を評価できる。
- $p(c_k = 1) = \pi_k$
- $p(c_k = 1|w) = \frac{\pi_k N(w|\mu_k, \Sigma_k)}{\sum_{j=1}^K \pi_j N(w|\mu_j, \Sigma_j)}$
- GMMはsklearnに実装されている。詳しくは[こちら](https://scikit-learn.org/stable/modules/mixture.html)。

### IDFを求める方法
- これもsklearnに実装されている。詳しくは[こちら](https://scikit-learn.org/stable/modules/generated/sklearn.feature_extraction.text.TfidfVectorizer.html)。

### document vectorをsparseにする方法
- document vectorの各要素$a_i$に対して、絶対値が$\frac{p}{100} \times t$未満だったら$a_i=0$とする。
- $p$はモデルパラメータ
- $t = \frac{|a_{min}| + |a_{max}|}{2}$
- $a_{min} = avg_n(min_i(a_i))$
- $a_{max} = avg_n(max_i(a_i))$

# 実装
- 著者らによる実装はGithubに公開されている。[こちら](https://github.com/dheeraj7596/SCDV)

- 今回自分でも実装してみた。[こちら](https://github.com/nishiba/scdv)
    - 仕事で作っているライブラリを作らなかったので前処理やパイプラインは雑になった。
    - SCDVクラスの関数のほとんどがstaticmethodなのは単体テストを書きやすくするため。
    - `word_topic_vectors`を保持しないのはモデルのサイズを小さくするため。
        - pickle化できなかったので。sparse vector等を使ってメモリを減らすか、pickleでの保存方法を変更する必要がある(macを使っているのでpickleの問題で大きいファイルを保存するのが面倒)。


**※改行されて読みにくいので[github](https://github.com/nishiba/scdv/blob/master/model/scdv.py)で見てください**

```python

from typing import Dict, Any, List

import itertools
import numpy as np
from gensim.corpora import Dictionary
from gensim.models import Word2Vec, TfidfModel
from sklearn.mixture import GaussianMixture


class SCDV(object):
    """ This is a model which is described in "SCDV : Sparse Composite Document Vectors using soft clustering over distributional representations"
    See https://arxiv.org/pdf/1612.06778.pdf for details
    
    """

    def __init__(self, documents: List[List[str]], embedding_size: int, cluster_size: int, sparsity_percentage: float,
                 word2vec_parameters: Dict[Any, Any], gaussian_mixture_parameters: Dict[Any, Any],
                 dictionary_filter_parameters: Dict[Any, Any]) -> None:
        """
        
        :param documents: documents for training.
        :param embedding_size: word embedding size.
        :param cluster_size:  word cluster size.
        :param sparsity_percentage: sparsity percentage. This must be in [0, 1].
        :param word2vec_parameters: parameters to build `gensim.models.Word2Vec`. Please see `gensim.models.Word2Vec.__init__` for details.
        :param gaussian_mixture_parameters: parameters to build `sklearn.mixture.GaussianMixture`. Please see `sklearn.mixture.GaussianMixture.__init__` for details.
        :param dictionary_filter_parameters: parameters for `gensim.corpora.Dictionary.filter_extremes`. Please see `gensim.corpora.Dictionary.filter_extremes` for details.
        """
        self._dictionary = self._build_dictionary(documents, dictionary_filter_parameters)
        vocabulary_size = len(self._dictionary.token2id)

        self._word_embeddings = self._build_word_embeddings(documents, self._dictionary, embedding_size,
                                                            word2vec_parameters)
        assert self._word_embeddings.shape == (vocabulary_size, embedding_size)

        self._word_cluster_probabilities = self._build_word_cluster_probabilities(self._word_embeddings, cluster_size,
                                                                                  gaussian_mixture_parameters)
        assert self._word_cluster_probabilities.shape == (vocabulary_size, cluster_size)

        self._idf = self._build_idf(documents, self._dictionary)
        assert self._idf.shape == (vocabulary_size, )

        word_cluster_vectors = self._build_word_cluster_vectors(self._word_embeddings, self._word_cluster_probabilities)
        assert word_cluster_vectors.shape == (vocabulary_size, cluster_size, embedding_size)

        word_topic_vectors = self._build_word_topic_vectors(self._idf, word_cluster_vectors)
        assert word_topic_vectors.shape == (vocabulary_size, (cluster_size * embedding_size))

        document_vectors = self._build_document_vectors(word_topic_vectors, self._dictionary, documents)
        assert document_vectors.shape == (len(documents), cluster_size * embedding_size)

        self._sparse_threshold = self._build_sparsity_threshold(document_vectors, sparsity_percentage)

    def infer_vector(self, new_documents: List[List[str]]) -> np.ndarray:
        word_cluster_vectors = self._build_word_cluster_vectors(self._word_embeddings, self._word_cluster_probabilities)
        word_topic_vectors = self._build_word_topic_vectors(self._idf, word_cluster_vectors)
        document_vectors = self._build_document_vectors(word_topic_vectors, self._dictionary, new_documents)
        return self._build_scdv_vectors(document_vectors, self._sparse_threshold)

    @staticmethod
    def _build_dictionary(documents: List[List[str]], filter_parameters: Dict[Any, Any]) -> Dictionary:
        d = Dictionary(documents)
        d.filter_extremes(**filter_parameters)
        return d

    @staticmethod
    def _build_word_embeddings(documents: List[List[str]], dictionary: Dictionary, embedding_size: int,
                               word2vec_parameters: Dict[Any, Any]) -> np.ndarray:
        w2v = Word2Vec(documents, size=embedding_size, **word2vec_parameters)
        embeddings = np.zeros((len(dictionary.token2id), w2v.vector_size))
        for token, idx in dictionary.token2id.items():
            embeddings[idx] = w2v.wv[token]
        return embeddings

    @staticmethod
    def _build_word_cluster_probabilities(word_embeddings: np.ndarray, cluster_size: int,
                                          gaussian_mixture_parameters: Dict[Any, Any]) -> np.ndarray:
        gm = GaussianMixture(n_components=cluster_size, **gaussian_mixture_parameters)
        gm.fit(word_embeddings)
        return gm.predict_proba(word_embeddings)

    @staticmethod
    def _build_idf(documents: List[List[str]], dictionary: Dictionary) -> np.ndarray:
        corpus = [dictionary.doc2bow(doc) for doc in documents]
        model = TfidfModel(corpus=corpus, dictionary=dictionary)
        idf = np.zeros(len(dictionary.token2id))
        for idx, value in model.idfs.items():
            idf[idx] = value
        return idf

    @staticmethod
    def _build_word_cluster_vectors(word_embeddings: np.ndarray, word_cluster_probabilities: np.ndarray) -> np.ndarray:
        vocabulary_size, embedding_size = word_embeddings.shape
        cluster_size = word_cluster_probabilities.shape[1]
        assert vocabulary_size == word_cluster_probabilities.shape[0]

        wcv = np.zeros((vocabulary_size, cluster_size, embedding_size))
        wcp = word_cluster_probabilities
        for v, c in itertools.product(range(vocabulary_size), range(cluster_size)):
            wcv[v][c] = wcp[v][c] * word_embeddings[v]
        return wcv

    @staticmethod
    def _build_word_topic_vectors(idf: np.ndarray, word_cluster_vectors: np.ndarray) -> np.ndarray:
        vocabulary_size, cluster_size, embedding_size = word_cluster_vectors.shape
        assert vocabulary_size == idf.shape[0]

        wtv = np.zeros((vocabulary_size, cluster_size * embedding_size))
        for v in range(vocabulary_size):
            wtv[v] = idf[v] * word_cluster_vectors[v].flatten()
        return wtv

    @staticmethod
    def _build_document_vectors(word_topic_vectors: np.ndarray, dictionary: Dictionary,
                                documents: List[List[str]]) -> np.ndarray:
        return np.array([
            np.sum([word_topic_vectors[idx] * count for idx, count in dictionary.doc2bow(d)], axis=0) for d in documents
        ])

    @staticmethod
    def _build_sparsity_threshold(document_vectors: np.ndarray, sparsity_percentage) -> float:
        def _abs_average_max(m: np.ndarray) -> float:
            return np.abs(np.average(np.max(m, axis=1)))

        t = 0.5 * (_abs_average_max(document_vectors) + _abs_average_max(-document_vectors))
        return sparsity_percentage * t

    @staticmethod
    def _build_scdv_vectors(document_vectors: np.ndarray, sparsity_threshold: float) -> np.ndarray:
        keep_elements = np.abs(document_vectors) >= sparsity_threshold
        return document_vectors * keep_elements

```

# 数値検証（オープンデータ）
- livedoorニュースの文書分類を行う。
- SCDVで特徴量を作り、LGBMClassifierで多クラス分類を行う。
- 精度検証はcv=3で交差検証を行う(時間がかかるので)。

### 実行方法
- 詳しくは[ReadMe](https://github.com/nishiba/scdv)。動かなかったらコメントください(対応するかも)。

### 結果
- 3回のvalidationの結果の平均。
- なんか凄く良い。なにかリークしてないかな?


|precision|recall|f1-score|support|
|---|---|---|---|
|0.92|0.92|0.92|2458|

- 参考: [文書ベクトルをお手軽に高い精度で作れるSCDVって実際どうなのか日本語コーパスで実験した(EMNLP2017)](https://qiita.com/fufufukakaka/items/a7316273908a7c400868)
  - 他の手法との比較もされています!

- 日本語の前処理を一切していないのに精度がでるのは単語のカテゴリ分類が上手くできているから？(あとで検証)
  - おそらくストップワードのカテゴリができていて、lightGBMがその項を無視できているのでは?

# モデルに対する感想
- 単語をクラスタリングしてクラスタごとに単語の表現ベクトルを足し合わせるのはすごく良いように思う。
- 例えば、業務で医療系のデータを扱っており、文書を診療科別に分類したいニーズがある。
- しかし、文書の中には関係ない単語(政治の話、日常会話、講演会等の実施情報)が多く含まれており、医療に関係する単語のみを取り出すのも一苦労。
- この方法を使えば、理想的には医療に関係の深い単語のクラスタが生成されて、それらの単語のみを足し合わせたものが表現ベクトルの一部になる。
- その後の分類問題は理想的には分類器が医療に関連するクラスタの要素のみを見てくれるはず。
- そう考えるとクラスタごとに表現ベクトルを正規化したほうがいいような・・・

# そのうち追加の検証するかも。
- 「いいね」がいっぱいついたら・・・

## 追加検証①
文書分類に効いている・効いてない単語のクラスタを確認する。

- 下記テーブルはimportanceの上位と下位のクラスタとそのクラスタの上位の単語です。
- それっぽく分類できていそう。
- importanceが低いものもほうが分類に関係なさそうな単語が多いような気もする。
- もっと差がつくかなと期待したが。

|cluster|importance|word|
|---|---|---|
|29|1513|['に対して', '番組', '逮捕', '氏', 'メンバー', '書き込み', '明かし', '反論', 'ツイート', '香川', 'つぶやき', '騒動', 'ネット上', '自身', '日本', 'ブログ', 'に対する', 'AKB', '怒り', '一方']|
|38|1275|['2011', '特集', '『', '編集部', 'MOVIE', 'ENTER', '公式サイト', '2010', 'エスマックス', '作品情報', '関連リンク', 'S', 'MAX', '型名', '探せる', '盗難', '突起', '営業活動', '兼用', '個人向け']|
|40|1162|['アナ', '米', 'イギリス', 'タレント', '移籍', '巨人', '深夜', 'フジテレビ', 'ロンドン五輪', '代表', '題し', '19日', '会見', '戦', '日本テレビ', '五輪', '優勝', '司会', '21日', '大会']|
|44|1118|['批判', '報じ', '話題', '発言', 'ネット掲示板', '声', '寄せ', 'コメント', '報道', '意見', 'やって来', '営業活動', '4月3日', '10年目', '突起', '盗難', 'わからん', '探せる', '型名', '-1']|
|59|1000|['livedoorニュース', '問い合わせ', '募集', '映画批評', '概要', 'レア', '開発者', 'リコー', '＞', 'RainbowApps', 'フォトギャラリー', 'RING', 'NEXT', 'GR', 'CUBE', 'ジャパン', '成長率', '掴め', '9回', 'にゃんこ']|
|37|985|['サイト', 'プラットフォーム', 'SNS', '家電', '新製品', 'ブランド', '広告', '技術', 'Ubuntu', '拡大', 'ロゴ', 'マイクロソフト', '多数', '市場', 'ツール', 'iOS', '大手', 'デバイス', '各社', '海外']|
|10|844|"['details', 'html', 'of', 'co.jp', 'by', ""'"", '_', '＋', '」(', 'HOMME', 'rights', 'reserved', ')', '(', '求人', '?', ';', '：', 'Sandwich', 'All']|"
|49|814|['心配', '当たり前', '少なく', '差', 'こそ', 'いう', '回答', '評価', '全て', '現実', '変化', '姿勢', '形', '関心', '不満', '要素', 'つつ', '格好', '現状', '期待']|
|43|791|['前田敦子', 'さんま', '炎上', '一時', 'ものまね', '9日', '2ちゃんねる', 'いじめ', 'インターネット上', 'ネット上では', '騒然', 'ダル', '原発', 'ダルビッシュ', '公表', '生放送', '——。', '紗栄子', '連発', 'オファー']|
|17|755|['ご覧', '参考', 'さっそく', '今回', '届け', 'いかが', 'iPhoneアプリ', '早速', 'Androidアプリ', '読み', '参照', 'レポート', '記事', い', '飛び出し', '掲げ', '会わ', '驚い', '添え']|
|28|117|['分かり', '言い', 'あれ', 'いえ', '聞き', 'できれ', '見れ', '使え', '思い', 'なり', 'すれ', 'わかり', '変わり', 'やり', '出来', '行き', '見え', '使い', 'なれ', '言え']|
|33|111|['いき', 'たく', 'たい', 'くれ', 'てる', 'み', '欲しい', 'みる', 'ほしい', 'くれる', 'ください', 'おく', '10年目', '4月3日', '突起', '盗難', '探せる', '型名', '兼用', '営業活動']|
|26|99|['メモ', 'ID', '書類', '貼り', '固定', 'セル', '途中', '形式', '数値', '右上', '音声', '解除', 'ワザ', 'タブ', 'タグ', 'ジャンプ', 'ウィンドウ', 'Word', 'Excel', '計算']|
|56|88|['8', '5', '6', '2', '1', '0', '3', '4', '7', '秘', 'プロファイル', '4月3日', '10年目', '突起', '盗難', '探せる', '型名', '営業活動', '兼用', '個人向け']|
|32|48|['包ま', '押さ', '引か', '置か', '言わ', '許さ', '切ら', '限ら', 'やら', '癒さ', '含ま', '語ら', '知ら', '狙わ', '襲わ', 'フラ', 'いわ', '思わ', '売ら', '失わ']|
|57|44|['くる', 'いく', 'おり', 'き', 'しまう', 'しまっ', 'しまい', '探せる', '盗難', 'プロファイル', '型名', '突起', '営業活動', '10年目', '兼用', '個人向け', 'モノラル', 'プリインストールアプリ', 'プリンタ', 'やって来']|
|11|43|['GHz', 'データ通信', 'RAM', 'NOTTV', 'CMOS', '900', 'Bluetooth', '外部', '32GB', '2GB', 'Xi', '1GB', '出力', '画素', 'カード', 'スロット', 'ドット', 'メモリ', '無線LAN', 'ワンセグ']|