【ゼロから作る文書分類】Deep Learning を勉強したあとに学び直したいパーセプトロンアルゴリズム

この記事は [NTTドコモ サービスイノベーション部 Advent Calendar](https://qiita.com/advent-calendar/2018/nttdocomo_service_innovation) 9日目の記事です。

# はじめに
本記事では，パーセプトロンアルゴリズムを用いて文書分類器を実装する方法について説明します。

いざ Deep Learning の勉強をしようと思って，[Deep Learning ライブラリーのチュートリアル](https://github.com/pytorch/examples) の実装を動かしてみたけど「このモデルは何をどうやって学習しているんだ😂」と思ったことはありませんか？

確認しようとしても，学習後のモデルの重みは実数値の行列ですよね。
この実数値はどうやって求めるのか気になって，[誤差伝搬法](https://qiita.com/Ugo-Nama/items/04814a13c9ea84978a4c) を勉強したけど，多層のニューラルネットワークでは更新式が複雑になりさらに混乱しますよね。

そこで本記事では，ニューラルネットワークの基礎となるパーセプトロンアルゴリズムを Python だけで実装します。自ら手を動かしつつ，どのようにパーセプトロンアルゴリズムが重みを更新しているか目視で確認しながら， ニューラルネットワークの重み更新に関する理解を深めるような内容を準備しました。

また本記事では，英語のデータセットではなく，日本語のTwitter評判分析データセットを利用し，日本語の文書分類器を実装するチュートリアルとなっています。

# そもそもパーセプトロンとは？
こちらの[パーセプトロンとは？](https://qiita.com/nishiy-k/items/1e795f92a99422d4ba7b)という記事が非常にわかりやすく，パーセプトロンに関する内容もまとまっています。本記事を読む前に一度目を通しておくと良いかと思います。説明はこちらの記事に任せます。

# 事前準備
本記事では，下記のデータセットと参考資料を利用します。
まずは tatHiさんの [GitHub のページ](https://github.com/tatHi/tweet_extructor) をご確認のうえ，データの準備をお願いします。

- Yu Suzuki先生のもとで公開されている「Twitter日本語評判分析データセット」
    - http://bigdata.naist.jp/~ysuzuki/data/twitter/
- tatHiさんの「Twitter日本語評判分析データセット」をダウンロードするためのスクリプト
  - https://github.com/tatHi/tweet_extructor
- Graham Neubig先生の「チュートリアル5: パーセプトロンアルゴリズムと文書分類」
  - http://www.phontron.com/slides/nlp-programming-ja-05-perceptron.pdf

# 本チュートリアルの概要
本チュートリアルでは，Twitter日本語評判分析データセットを利用して，iPhoneに関するツイートが「ポジティブな内容であるか」または「ネガティブな内容であるか」を判定する文書分類器の実装を行います。

最終的に完成するプログラムでは，以下の処理を行います。

1. テキストデータの前処理を行い，パーセプトロンアルゴリズムを用いて文書分類器の学習する
2. テストデータを用いて文書分類器の性能を評価する
3. 任意の入力文に対する予測結果の確認する

``` python
python perceptron.py
>>> NumTest: 536
>>> Accuraccy: 0.8470149253731343 
>>> Input: iPhone 6 s 画質 クソ だ ふざけん な よー 。
>>> Predict: -1
```

# 学習データと評価データの準備
まずは，学習データと評価データの準備を行います。
Twitter日本語評判分析データセットをダウンロード後，前処理を行い，学習データと評価データに分割します。

学習データと評価データは，ファイル形式として「ラベル\t単語 単語 単語 … 」のデータに変換します。
日本語の場合「文 → 単語列」に変換する処理が必要ですので，ここでは，Python で簡単に利用できる単語分割ツール [nagisa](https://github.com/taishi-i/nagisa) を利用します。

まずは pip でツールのインストールを行います。

```
$ pip install nagisa
```

単語分割に関しては，下記のコードを参考に「文 → 単語列」の変換を行います。

```python
import nagisa

text = 'Pythonで簡単に使えるツールです'
words = nagisa.wakati(text)
print(words) 
#=> ['Python', 'で', '簡単', 'に', '使える', 'ツール', 'です']
```

学習データと評価データの中身です。

```
pos     iPhone 6 s の 画像 メチャ 綺麗 !
pos     iPhone 6 s に し た よー ！ 3 D タッチ 面白い
pos     iPhone 6 s 画面 大きく て 使い やすい （○' ω '○）
pos     iPhone 6 S 充電 の 減り が めっちゃ 遅い ね 使える な
neg     iPhone 6 で すら 画面 大きい と 感じる の に 、 P l u s に なっ たら もう 持て ない
pos     iPhone 6 s に 変え た けど 画面 割れ て ない 時点 で 感動 し た
neg     私 の iPhone 6 s ポンコツ 過ぎ ！ ハズレ か よ 😉💢💢💢
```

下記のように，学習データと評価データを準備してください。

```
fn_in_train = "text_classification_tutorial.train"
fn_in_test = "text_classification_tutorial.test"
```

# データの前処理
次に，上記で準備した学習データを読み込み単語ID辞書とラベルID辞書を作成します。

```python
label2id, word2id = make_vocabs(fn_in_train)
```
## make_vocabs(filename)
具体的には下記の関数を使って，学習データを辞書形式に変換します。
ファイルを一行ずつ読み込み，label2idとword2idに単語とラベルをそれぞれ登録していきます。

```python
def make_vocabs(filename):
    label2id = {}
    word2id = {"OOV":0}
    with open(filename, "r") as f:
        for line in f:
            label, words = line.strip().split("\t")
            if label not in label2id:
                label2id[label] = len(label2id)
            
            words = words.split(" ")
            for word in words:
                if word not in word2id:
                    word2id[word] = len(word2id)
    return label2id, word2id
```

学習データを辞書形式に変換した結果です。

```python
label2id = {'neg': 0, 'pos': 1}
word2id = {'減らす': 5182, 'phone': 5184, '訳':, '😜': 5190}
```
## load_file(filename)
次に，下記の関数を用いて，学習データと評価データをリスト形式に変換します。

```python
train_data = load_file(fn_in_train)
test_data = load_file(fn_in_test)
```

こちらもファイルを一行ずつ読み込み，リストに追加していきます。

```python
def load_file(filename):
    data = []
    with open(filename, "r") as f:
        for line in f:
            label, words = line.strip().split("\t")
            words = words.split(" ")
            data.append([label, words])
    return data
```

学習データをリスト形式に変換した結果です。

```python
train_data = [['pos', ['iPhone', '6', '、', '光', 'が', 'うまく', '入っ', 'て', 'いる', 'ところ', 'で', '撮影', 'し', 'た', '写真', 'は', 'ほんと', 'に', 'きれい', 'だ', 'なぁ', '。', 'いつ', 'の', 'ま', 'に', 'か', 'コンパクト', 'デジカメ', 'は', '不要', 'に', 'なっ', 'て', 'しまっ', 'た', '。']], ['neg', ['iPhone', '6', 'に', 'し', 'た', 'ん', 'だ', 'けど', '大きい', 'し', 'ダサい']]]
```

# パーセプトロンアルゴリズムによる学習
ここからはパーセプトロンアルゴリズを使って，文書分類器の学習を行います。
まずは，パーセプトロンの重みの初期化をリストを用いて行います。

```python
w = [0.] * len(word2id)
```

次に，Pythonの辞書を用いて，「ポジティブ」ラベルと「ネガティブ」ラベルを 1 と -1 で表現します。

```python
label2score = {"pos":1, "neg":-1}
```

「正解ラベル != 予測ラベル」の場合，パーセプトロンの重みを更新する処理の実装です。
ここでは，素性抽出とパーセプトロンの重みの更新方法について説明します。

```python
for epoch in range(5):
    for line in train_data:
        true_y, words = line
        true_y = label2score[true_y] # 1 or -1

        x = create_features(words, word2id)
        pred_y = predict_one(x, w)
        if pred_y != true_y:
            update_weights(x, w, true_y) # update
```

ここでは単語ユニグラムを素性として利用する関数を実装しています。

```python
def create_features(words, word2id):
    x = []
    for word in words:
        if word in word2id:
            x.append(word2id[word])
        else:
            x.append(word2id["OOV"])
    return x
```

次に，求めた素性とパーセプトロンの重みを用いて，与えられた文書が「ポジティブ」ラベル（1）か「ネガティブ」ラベル（-1）どちらに属するか計算します。

```python
def predict_one(x, w):
    score = 0.
    for x_idx in x:
        score += w[x_idx]
    if score >= 0:
        return 1
    else:
        return -1
```

最後に，update_weightsでは正解ラベル != 予測ラベルの場合，x_idxに対応するインデックスの重みを更新します。

```python
def update_weights(x, w, y):
    for x_idx in x:
        w[x_idx] += y * 1
    return w
```

# 文書分類器の性能評価
ここからは，上記で学習した文書分類器がきちんと学習できているか評価データを用いて確認します。
下記の処理では，「正解ラベル == 予測ラベル」の場合をカウントしています。

```python  
corrects = 0.
num_test = len(test_data)
mistakes = []
for line in test_data:
    true_y, words = line
    true_y = label2score[true_y]

    x = create_features(words, word2id)
    pred_y = predict_one(x, w)
    if pred_y == true_y:
        corrects += 1
    else:
        mistakes.append(words)

print("NumTest:", num_test, "Accuraccy:", corrects/num_test)
#=> NumTest: 536 Accuraccy: 0.8470149253731343
```

任意の入力文に対する予測結果を目視でも確認します。

```python
sample = "iPhone 6 s 画質 クソ だ ふざけん な よー 。"
sample_words = sample.split(" ")
x = create_features(words, word2id)
pred_y = predict_one(x, w)
print("Input:", sample, "Predict:", pred_y)
#=> Input: iPhone 6 s 画質 クソ だ ふざけん な よー 。
#=> Predict: -1
```

各素性の重みを確認します。

```python
word2weight = {k:w[v] for k, v in word2id.items()}
sorted_w2w = sorted(word2weight.items(), key=lambda x:x[1])

n = 10
positive_feats_topn = sorted_w2w[::-1][:n]
print(positive_feats_topn)
#ポジティブ（1） の方向に動いた素性
#=> [('感動', 27.0), ('画質', 25.0), ('綺麗', 21.0), ('性能', 20.0), ('快適', 20.0), ('サクサク', 17.0), ('便利', 17.0), ('できる', 17.0), ('すごい', 16.0), ('よかっ', 15.0)]

negative_feats_topn = sorted_w2w[:n]
print(negative_feats_topn)
# ネガティブ（-1） の方向に動いた素性
#=> [('にくい', -25.0), ('電源', -19.0), ('づらい', -18.0), ('落ちる', -13.0), ('誤字', -13.0), ('早く', -12.0), ('割れ', -12.0), ('ちょっと', -12.0), ('経っ', -12.0), ('にくく', -12.0)]
```

# おわりに
本記事では，パーセプトロンアルゴリズムによる文書分類器の実装方法について説明しました。
現在の自然言語処理の分野では， Deep Learning を用いた手法が主流の時代ですが，自らの手を動かしアルゴリズムを実装し，理解を深めることも時には重要だと考えこのような記事を作成しました。

この記事を読んだ人が「どのようにモデルの重みが更新されているのか，少しでもイメージすることができるきっかけ」になると嬉しいです！

# 付録
本記事で実装したコードです。

```python
# -*- coding:utf-8 -*-

def make_vocabs(filename):
    label2id = {}
    word2id = {"OOV":0}
    with open(filename, "r") as f:
        for line in f:
            label, words = line.strip().split("\t")
            if label not in label2id:
                label2id[label] = len(label2id)
            
            words = words.split(" ")
            for word in words:
                if word not in word2id:
                    word2id[word] = len(word2id)
    return label2id, word2id

def load_file(filename):
    data = []
    with open(filename, "r") as f:
        for line in f:
            label, words = line.strip().split("\t")
            words = words.split(" ")
            data.append([label, words])
    return data

def create_features(words, word2id):
    x = []
    for word in words:
        if word in word2id:
            x.append(word2id[word])
        else:
            x.append(word2id["OOV"])
    return x

def predict_one(x, w):
    score = 0.
    for x_idx in x:
        score += w[x_idx]
    if score >= 0:
        return 1
    else:
        return -1

def update_weights(x, w, y):
    for x_idx in x:
        w[x_idx] += y * 1
    return w

def ngram(words, grams=[1,2]):
    tokens = []
    for gram in grams:
        for i in range(len(words) - gram + 1):
            tokens += ["_*_".join(words[i:i+gram])]
    return tokens

def main():
    # Input files
    fn_in_train = "text_classification_tutorial.train"
    fn_in_test = "text_classification_tutorial.test"

    # Load files
    label2id, word2id = make_vocabs(fn_in_train)
    train_data = load_file(fn_in_train)
    test_data = load_file(fn_in_test)

    # Initialize the weights
    w = [0.] * len(word2id)
    label2score = {"pos":1, "neg":-1}

    # Update weights using a trainset
    for epoch in range(5):
        for line in train_data:
            true_y, words = line
            true_y = label2score[true_y]

            x = create_features(words, word2id)
            pred_y = predict_one(x, w)
            if pred_y != true_y:
                update_weights(x, w, true_y)

    # Evaluate on a testset
    corrects = 0.
    num_test = len(test_data)
    for line in test_data:
        true_y, words = line
        true_y = label2score[true_y]

        x = create_features(words, word2id)
        pred_y = predict_one(x, w)
        if pred_y == true_y:
            corrects += 1
        
    print("NumTest:", num_test, "Accuraccy:", corrects/num_test)

    # Check the trained classifier
    sample = "iPhone 6 s 画質 クソ だ ふざけん な よー 。"
    sample_words = sample.split(" ")
    x = create_features(words, word2id)
    pred_y = predict_one(x, w)
    print("Input:", sample, "Predict:", pred_y)

    # Check the features and the weights
    word2weight = {k:w[v] for k, v in word2id.items()}    
    sorted_w2w = sorted(word2weight.items(), key=lambda x:x[1])    
    n = 10
    positive_feats_topn = sorted_w2w[::-1][:n]
    negative_feats_topn = sorted_w2w[:n]

    print(positive_feats_topn)
    print(negative_feats_topn)

if __name__ == "__main__":
    main()
```