13. Word2Vec#

Hide code cell source
# packageのimport
import os 
import math 
from typing import Any, Union, Callable, Type, TypeVar
from tqdm.std import trange,tqdm
import numpy as np 
import numpy.typing as npt
import pandas as pd 
import matplotlib.pyplot as plt 
import plotly.express as px
import seaborn as sns

# pytorch関連のimport
import torch
import torch.nn as nn 
import torch.nn.functional as F 
import torch.optim as optim 

13.1. 単語のベクトル表現#

自然言語処理において,単語をそのまま機械学習モデルに扱わせることはできません.そのため,それぞれの単語に対応するベクトル表現を利用することになります.このベクトル表現方法はいろいろとあり,離散表現と分散表現という大別ができます.これらについて見ていきましょう.

13.1.1. 離散表現と分散表現#

単語をベクトルとして表現する方法として古くから使われているのがone-hot表現(1-of-K表現とも呼ばれます)です.これはある要素のみが1でそれ以外が0であるような表現のことであり,単語に対応したベクトルのある要素のみが1でそれ以外が0であるようなベクトルを用いることで,単語をベクトル表現します.

one-hotベクトルはシンプルなアイディアで理解しやすいですが,語彙の数だけベクトルの次元数が必要になることに注意が必要です.また,「オートバイ」と「バイク」のようなほぼほぼ似たような意味の単語同士の類似度をcosine類似度で計算しようとしても,それぞれが別の次元が立っているだけのベクトルなので内積0となってしまい,意味的な類似度を測ることには適さないことがわかります.

ここではこのone-hot表現を離散表現の例として紹介しました.

また,文書中に登場した単語のone-hotベクトルを足し合わせることで,文書をベクトル表現するBag-of-Words(BoW)という表現方法もあります.

この場合はただ足し合わせるだけなので,文書中に同じ単語が何回か登場したら,1以上の整数がベクトル内に現れることもあります.

onehotやbowの様な表現方法は非常に簡便で分かりやすい反面,語彙数分だけの次元数が常に必要になるなどの嬉しくない特徴を持ちます.

13.1.2. 様々な分散表現#

one-hot表現に対して,分散表現とは単語を語彙数に比べて低次元の実数値ベクトルで表す表現です.気持ちとしては,one-hotで表現された単語をより低次元空間の座標として表現し,one-hot→embedding→onehotの様に可逆圧縮しているイメージです.そのため多くの場合任意の比較的小さい次元数(50, 100, 200, 300次元など)が用いられています.これの利点としては,

  • 語彙数に左右されずにベクトルの次元数を決定できるため計算量を抑えられる

  • 同じような意味の単語に同じようなベクトル表現を当てがうことができるのならば,cosine類似度のような簡単な計算で意味の類似度(のようなもの)を評価することができる

などが考えられます.現代の自然言語処理においても,このアプローチが取られることが多いです.

この分散表現の作り方には色々な方法があります.例えばBoWで表現された文章データをNMF(Non-Negative Matrix Factorization, 非負値行列因子分解)[Lee and Seung, 1999, Lee and Seung, 2000]やLSA(Latent Semantic Analysis, 潜在的意味解析)[Deerwester et al., 1990]のような手法で行列分解することで作成することもできます.ただし作成できるベクトルが持つ意味(作成されたベクトルがどのような使い方に適したものなのか)は手法により様々です.今回は,ニューラルネットワークを用いて単語の分散表現が作れるword2vec[Mikolov et al., 2013, Mikolov et al., 2013, Mikolov et al., 2013]と呼ばれる手法群の中でも,CBOWについて紹介します.

13.2. Continuous Bag-of-Words#

13.2.1. CBOWと分布仮説#

例えば以下の文章があったときに,XXXYYY に相当する単語がなんなのかがわかるでしょうか?

(この例ではもちろんXXXは ガンダム ですし,YYYは ノリス・パッカード大佐 ですね.)

私たちはある単語を聞きそびれたり,何かの固有名詞が分からなくても,周辺の言葉から大体類推して言葉の意味を把握することができます.

このような「単語の意味は、周囲の単語によって形成される」という仮説を自然言語処理では 分布仮説 と呼びます.

この文脈において,対象の単語の周辺の単語のことをコンテキストと呼びます.


説明したい単語「goodbye」と,その周辺にあってこの単語の意味を推測するのに使えそうな単語達(コンテキスト)の関係.
出典: ゼロから作るDeep Learning 2 自然言語処理編

この分布仮説をもとに,ニューラルネットワークを使って単語の意味をある程度表現できるようなベクトル表現を獲得できる手法がこれから紹介するCBOWです.

13.2.2. CBOWのアーキテクチャ#

CBoWでは,周辺の単語を入力にして目的の単語を予測するネットワークを構築します.


コンテキストを使った単語の予測.
出典: ゼロから作るDeep Learning 2 自然言語処理編

CBOWは単純なMLPを利用して,語彙数\(V\),埋め込み次元数\(N\)の場合に,全ての語彙それぞれに対応する単語埋め込みベクトルの束である\(\mathbf{W}_{V, N}\)を作成します.(ノーテーションは正しく定義しておけばなんでもいいのですが,私は埋め込み次元数を\(L\)と置くことが多いです.)

Illustration of the word2vec models: (a) CBOW, (b) skip-gram [16, 33].
word2vecのアーキテクチャ.左側がCBoW,また右側はSkip-Gram.
出典: Demographic Prediction Based on User Reviews about Medications

13.2.3. 実装#

まずは,forwardメソッドの入力値が「コンテクストのBoW表現」である場合の実装を考えます.一層目の全結合層の結合重みをそれぞれの語彙に対応する単語埋め込みベクトルとして利用しましょう.

一つ目のnn.Linearはこのモデルで扱いたい語彙(異なり語,ユニークな単語)の数\(V\)(コード中では vocab_size)の数だけベクトルを持っており,入力された語彙に対応したベクトルを取り出して返します.この語彙に対応したベクトルを 単語埋め込みベクトル と呼びます.また,単語埋め込みベクトルの次元数\(N\)埋め込み次元数 などと呼び,コード中では embedding_dimという変数で扱います.
ある単語は,同じ文書中に存在する「その単語の周辺に出現する単語」によって類推することができるというのが自然言語処理の分布仮説でした.これに則り,周辺単語を入力として,予測したい単語の出現確率を出力するMLPを作ります.

class CBoW(nn.Module):
    def __init__(self, vocab_size:int, embedding_dim:int) -> None:
        super().__init__()
        self.embeddingbag = nn.Linear(vocab_size, embedding_dim, bias=False)
        self.linear = nn.Linear(embedding_dim, vocab_size)

    def forward(self, inputs:Any)->Any:
        h = self.embeddingbag(inputs) / inputs.sum(1)[:,None]
        return self.linear(h)

この実装のCBoWクラスはMLPとほぼ同じなので非常にわかりやすいですが,contextsをBoW表現に直す必要があります.データが少ない場合は問題になりませんが,データ量が増えた時には大変です.

PyTorchでは,このような実装をしなくとも単語のid列を入力に,onehotやbowを介さずに埋め込みベクトルを返してくれるnn.Embeddingクラスとnn.Embeddingbagクラスがあります.これを使ってより賢い実装を以下に示します.

Hint

単語idを一つ一つ単語埋め込みベクトルに変換したいならnn.Embeddingを使います.文書(単語idのシーケンス)に対する単純な埋め込みベクトルが欲しいならばnn.Embeddingbagを使います.

class CBoW(nn.Module):
    def __init__(self, vocab_size:int, embedding_dim:int) -> None:
        super().__init__()
        self.embeddingbag = nn.EmbeddingBag(vocab_size, embedding_dim)
        self.linear = nn.Linear(embedding_dim, vocab_size)

    def forward(self, inputs:Any)->Any:
        h = self.embeddingbag(inputs) / inputs.size(-1)
        return self.linear(h)

クラスの実装上で明確に異なるのはMLPの最初のLinear層の代わりに,Embeddingbagレイヤーと名付けられた層が追加されていることです.これによりforwardメソッドへの入力をいちいちonehotやbowにしなくとも,単語idのシーケンスを渡すだけで,埋め込みベクトルを返してくれます.

最終層は「ターゲットの単語が出現する確率」なので,Softmax関数を用います(ここでもSoftmaxを利用することにします).ただし,word2vecが発表された当初はGPUで計算するのではなく,CPUで計算できるような工夫として,Softmaxを近似した別の関数を利用していました.これにはHierarchical Softmax(階層的ソフトマックス)やNegative Sampling(不例サンプリング)が用いられます.是非調べてみてください.

13.2.4. 損失関数#

\(x\)の出現確率\(p(x)\)とモデルの予測した\(x\)の出現確率\(q(x)\)の交差エントロピーは以下のように求まります.

(13.1)#\[ H(p, q) = -\sum_{x} p(x) \log(q(x)) \]

今回の場合,予測したい単語が\(y\)であり,これは単語idになっています.これを語彙数\(V\)のonehotベクトルにする関数を\(\operatorname{onehot}(y)\)としましょう.
コード中,CBoWのforwardメソッドの出力(予測する値)はself.linear(h)であり,下に示す訓練ループの中ではlogitsとされてますが,これは全結合層の出力でしかありません.本来はこれをSoftmaxに通した値が出力値であり,これが予測したい単語の出現確率です.よってここでのクロスエントロピーは

(13.2)#\[ H(y,\operatorname{logits}) = -\operatorname{onehot}(y) \cdot \log(\operatorname{softmax}(\operatorname{logits})) \]

で求められます.ただし,minibatchごとに訓練する場合は,データ一つ一つに対して計算した後に平均をとる必要があります.

13.3. 実験#

13.3.1. データのダウンロード#

wikipediaを使いやすい形で公開してくれているtext8の日本語版,ja.text8を使ってw2vを学習してみましょう.

import os 
if "ja.text8" not in os.listdir("./data/"):
    !wget -P ./data https://s3-ap-northeast-1.amazonaws.com/dev.tech-sketch.jp/chakki/public/ja.text8.zip
    !unzip ./data/ja.text8.zip

13.3.2. データの準備#

with open("./data/ja.text8") as f:
    text8 = f.read()

print(text8[:200])
ちょん 掛け ( ちょん がけ 、 丁 斧 掛け ・ 手斧 掛け と も 表記 ) と は 、 相撲 の 決まり 手 の ひとつ で ある 。 自分 の 右 ( 左 ) 足 の 踵 を 相手 の 右 ( 左 ) 足 の 踵 に 掛け 、 後方 に 捻っ て 倒す 技 。 手斧 ( ちょう な ) を かける 仕草 に 似 て いる こと から 、 ちょう な が 訛っ て ちょん 掛け と なっ 

ja.text8では(英文のように)単語ごとにスペースを入れてくれているので,簡単にこれ以降の自然言語処理に進めます.このような処理を 分かち書き と呼びます.

本当はtext8の全てのデータを使いたいのですが,学習に時間がかかりすぎるので1/10の量を使うことにします.

LIMIT = math.floor(len(text8)*0.1)
print(f"{LIMIT}/ {len(text8)}")

text8 = text8[:LIMIT]
4650779/ 46507793

読み込んだテキストから,以下の条件で単語をフィルタリングします.

  1. 日本語のみで構成された単語だけを取り出します.

  2. 5個以上の文書に出現している単語のみを取り出し

ここまでやった後に,語彙の辞書を作ります.

  1. id2word(id→単語)

  2. word2id (単語→id)

import re
def build_simply_dictionary(texts):
    token_set = set(token for text in texts for token in text.split())
    word2id = {token:id for id, token in enumerate(token_set)}  
    return word2id

def my_analyzer(text):
    #text = code_regex.sub('', text)
    tokens = text.split()
    tokens = filter(lambda token: re.search(r'[ぁ-ん]+|[ァ-ヴー]+|[一-龠]+', token), tokens)
    return tokens 

def build_dictionary(texts, min_df=1):
    from sklearn.feature_extraction.text import CountVectorizer
    countvectorizer = CountVectorizer(min_df=min_df, analyzer=my_analyzer)

    X = countvectorizer.fit_transform(texts)
    id2word = {id:w for id,w in enumerate(countvectorizer.get_feature_names_out())}
    word2id = {w:id for id,w in id2word.items()}
    return id2word, word2id, X

texts = text8.split("。")
id2word, word2id,X = build_dictionary(texts,5)
V = len(id2word)
D = len(texts)
print(f"文書数: {D}, 語彙数: {V}")
文書数: 57498, 語彙数: 17143

ここでは,予測したい単語とコンテキストを合わせたものをウィンドウと呼びます.このウィンドウサイズを5として,予測したい単語の前後2単語をまとめた5単語を取り出し,contextsとtargetを作成します.

def build_contexts_and_target(preprocessed_texts, window_size=5):
    contexts = []
    target = []
    a = window_size//2
    for text in preprocessed_texts:
        for i in range(a, len(text)-a):
            target.append(text[i])
            tmp = text[i-a:i]
            tmp += text[i+1:i+1+a]
            contexts.append(tmp)
    return np.array(contexts), np.array(target)
WINDOW_SIZE = 11

preprocessed_texts = [[word2id[w] for w in text.split() if w in word2id] for text in texts]
preprocessed_texts = [text for text in preprocessed_texts if len(text) > WINDOW_SIZE]
contexts, target = build_contexts_and_target(preprocessed_texts, WINDOW_SIZE)
print("前処理後の文書数:", len(preprocessed_texts))
print(f"contextsの数: {len(contexts)}")
前処理後の文書数: 44599
contextsの数: 750947

ミニバッチを作成する関数を用意します.

def get_batch(contexts, target, batch_size=32, shuffle=True):
    D = target.size
    index = np.arange(D)
    
    if shuffle:
        np.random.shuffle(index)

    n_batches = D // batch_size
    for minibatch_indexes in np.array_split(index, n_batches):
        a = torch.tensor(contexts[minibatch_indexes])
        b = torch.tensor(target[minibatch_indexes])
        yield a,b

13.3.3. 訓練ループの作成#

通常のMLPと同様の学習ループを作成します.w2vの学習は時間がかかるので,プログレスバーを表示するようにしておきます.ここではepochごとに更新するバーとミニバッチごとに更新するバーを用意します.(ここで使うコーパスサイズだと,CPUで10~20分程度かかります)

学習が終わり次第,損失関数の増減を折れ線グラフにして確認できるようにもしておきましょう.

max_epochs = 10
lr = 0.01
batch_size = 512
L = 50
n_batches = len(target) // batch_size
DEVICE="cpu"
if torch.cuda.is_available():
    DEVICE ="cuda:0"

cbow = CBoW(V, L)
criterion = nn.CrossEntropyLoss()
save_fname = f"{cbow.__class__.__name__}_ep{max_epochs}_lr{lr}_b{batch_size}_emb{L}.pth"

"""
# 学習済みの重みがある場合
print("loading pretrained weights...")
cbow.load_state_dict(torch.load(f"./models/{save_fname}"))
cbow.eval()
"""

# 学習済みの重みがない場合
print("training CBoW from scrach...")
cbow.train()
cbow = cbow.to(DEVICE)
optimizer = optim.Adam(cbow.parameters(), lr=lr)
monitoring_loss = []

for epoch in trange(max_epochs):
    with tqdm(total=n_batches) as tbar:
        for batch in get_batch(contexts, target, batch_size):
            x,y = batch
            x,y = x.to(DEVICE), y.to(DEVICE)

            optimizer.zero_grad()
            logits = cbow(x)
            loss = criterion(logits, y)
            loss.backward()
            optimizer.step()
            
            monitoring_loss.append(float(loss))
            tbar.update(1)
cbow.eval()
cbow = cbow.cpu()
torch.save(cbow.state_dict(), f"./models/{save_fname}")

plt.title("cross entropy of training set")
plt.xlabel("iteration")
plt.ylabel("cross entropy loss")
plt.plot(monitoring_loss)
Hide code cell output
training CBoW from scrach...
  0%|                                                                                                                                                                                                                                                                              | 0/10 [00:00<?, ?it/s]

  0%|                                                                                                                                                                                                                                                                            | 0/1466 [00:00<?, ?it/s]


  0%|▌                                                                                                                                                                                                                                                                   | 3/1466 [00:00<01:00, 24.18it/s]


  0%|█▏                                                                                                                                                                                                                                                                  | 7/1466 [00:00<00:49, 29.24it/s]


  1%|█▉                                                                                                                                                                                                                                                                 | 11/1466 [00:00<00:46, 31.08it/s]


  1%|██▋                                                                                                                                                                                                                                                                | 15/1466 [00:00<00:45, 31.94it/s]


  1%|███▎                                                                                                                                                                                                                                                               | 19/1466 [00:00<00:44, 32.23it/s]


  2%|████                                                                                                                                                                                                                                                               | 23/1466 [00:00<00:44, 32.37it/s]


  2%|████▊                                                                                                                                                                                                                                                              | 27/1466 [00:00<00:45, 31.94it/s]


  2%|█████▍                                                                                                                                                                                                                                                             | 31/1466 [00:00<00:44, 32.12it/s]


  2%|██████▏                                                                                                                                                                                                                                                            | 35/1466 [00:01<00:44, 31.99it/s]


  3%|██████▉                                                                                                                                                                                                                                                            | 39/1466 [00:01<00:44, 32.33it/s]


  3%|███████▌                                                                                                                                                                                                                                                           | 43/1466 [00:01<00:43, 32.50it/s]


  3%|████████▎                                                                                                                                                                                                                                                          | 47/1466 [00:01<00:43, 32.49it/s]


  3%|█████████                                                                                                                                                                                                                                                          | 51/1466 [00:01<00:44, 31.69it/s]


  4%|█████████▋                                                                                                                                                                                                                                                         | 55/1466 [00:01<00:44, 31.62it/s]


  4%|██████████▍                                                                                                                                                                                                                                                        | 59/1466 [00:01<00:43, 32.08it/s]


  4%|███████████▏                                                                                                                                                                                                                                                       | 63/1466 [00:01<00:43, 32.38it/s]


  5%|███████████▊                                                                                                                                                                                                                                                       | 67/1466 [00:02<00:42, 32.59it/s]


  5%|████████████▌                                                                                                                                                                                                                                                      | 71/1466 [00:02<00:42, 32.65it/s]


  5%|█████████████▎                                                                                                                                                                                                                                                     | 75/1466 [00:02<00:42, 32.76it/s]


  5%|█████████████▉                                                                                                                                                                                                                                                     | 79/1466 [00:02<00:42, 32.82it/s]


  6%|██████████████▋                                                                                                                                                                                                                                                    | 83/1466 [00:02<00:42, 32.85it/s]


  6%|███████████████▎                                                                                                                                                                                                                                                   | 87/1466 [00:02<00:42, 32.74it/s]


  6%|████████████████                                                                                                                                                                                                                                                   | 91/1466 [00:02<00:41, 32.91it/s]


  6%|████████████████▊                                                                                                                                                                                                                                                  | 95/1466 [00:02<00:41, 33.07it/s]


  7%|█████████████████▍                                                                                                                                                                                                                                                 | 99/1466 [00:03<00:41, 33.12it/s]


  7%|██████████████████▏                                                                                                                                                                                                                                               | 103/1466 [00:03<00:41, 33.01it/s]


  7%|██████████████████▊                                                                                                                                                                                                                                               | 107/1466 [00:03<00:41, 33.05it/s]


  8%|███████████████████▌                                                                                                                                                                                                                                              | 111/1466 [00:03<00:41, 33.05it/s]


  8%|████████████████████▏                                                                                                                                                                                                                                             | 115/1466 [00:03<00:40, 32.97it/s]


  8%|████████████████████▉                                                                                                                                                                                                                                             | 119/1466 [00:03<00:40, 33.04it/s]


  8%|█████████████████████▋                                                                                                                                                                                                                                            | 123/1466 [00:03<00:40, 33.05it/s]


  9%|██████████████████████▎                                                                                                                                                                                                                                           | 127/1466 [00:03<00:40, 33.00it/s]


  9%|███████████████████████                                                                                                                                                                                                                                           | 131/1466 [00:04<00:40, 32.90it/s]


  9%|███████████████████████▊                                                                                                                                                                                                                                          | 135/1466 [00:04<00:41, 32.43it/s]


  9%|████████████████████████▍                                                                                                                                                                                                                                         | 139/1466 [00:04<00:41, 31.63it/s]


 10%|█████████████████████████▏                                                                                                                                                                                                                                        | 143/1466 [00:04<00:41, 31.73it/s]


 10%|█████████████████████████▊                                                                                                                                                                                                                                        | 147/1466 [00:04<00:41, 32.02it/s]


 10%|██████████████████████████▌                                                                                                                                                                                                                                       | 151/1466 [00:04<00:41, 31.47it/s]


 11%|███████████████████████████▎                                                                                                                                                                                                                                      | 155/1466 [00:04<00:41, 31.63it/s]


 11%|███████████████████████████▉                                                                                                                                                                                                                                      | 159/1466 [00:04<00:41, 31.67it/s]


 11%|████████████████████████████▋                                                                                                                                                                                                                                     | 163/1466 [00:05<00:40, 32.02it/s]


 11%|█████████████████████████████▍                                                                                                                                                                                                                                    | 167/1466 [00:05<00:40, 32.16it/s]


 12%|██████████████████████████████                                                                                                                                                                                                                                    | 171/1466 [00:05<00:41, 31.13it/s]


 12%|██████████████████████████████▊                                                                                                                                                                                                                                   | 175/1466 [00:05<00:42, 30.59it/s]


 12%|███████████████████████████████▌                                                                                                                                                                                                                                  | 179/1466 [00:05<00:43, 29.66it/s]


 12%|████████████████████████████████                                                                                                                                                                                                                                  | 182/1466 [00:05<00:43, 29.45it/s]


 13%|████████████████████████████████▌                                                                                                                                                                                                                                 | 185/1466 [00:05<00:43, 29.54it/s]


 13%|█████████████████████████████████                                                                                                                                                                                                                                 | 188/1466 [00:05<00:43, 29.37it/s]


 13%|█████████████████████████████████▊                                                                                                                                                                                                                                | 192/1466 [00:06<00:42, 29.89it/s]


 13%|██████████████████████████████████▍                                                                                                                                                                                                                               | 196/1466 [00:06<00:41, 30.37it/s]


 14%|███████████████████████████████████▏                                                                                                                                                                                                                              | 200/1466 [00:06<00:41, 30.72it/s]


 14%|███████████████████████████████████▉                                                                                                                                                                                                                              | 204/1466 [00:06<00:40, 31.24it/s]


 14%|████████████████████████████████████▌                                                                                                                                                                                                                             | 208/1466 [00:06<00:42, 29.68it/s]


 14%|█████████████████████████████████████▎                                                                                                                                                                                                                            | 212/1466 [00:06<00:41, 30.19it/s]


 15%|██████████████████████████████████████                                                                                                                                                                                                                            | 216/1466 [00:06<00:41, 30.16it/s]


 15%|██████████████████████████████████████▋                                                                                                                                                                                                                           | 220/1466 [00:06<00:43, 28.57it/s]


 15%|███████████████████████████████████████▏                                                                                                                                                                                                                          | 223/1466 [00:07<00:44, 28.00it/s]


 15%|███████████████████████████████████████▊                                                                                                                                                                                                                          | 226/1466 [00:07<00:44, 27.78it/s]


 16%|████████████████████████████████████████▎                                                                                                                                                                                                                         | 229/1466 [00:07<00:50, 24.71it/s]


 16%|████████████████████████████████████████▊                                                                                                                                                                                                                         | 232/1466 [00:07<01:00, 20.43it/s]


 16%|█████████████████████████████████████████▎                                                                                                                                                                                                                        | 235/1466 [00:07<01:08, 17.94it/s]


 16%|█████████████████████████████████████████▋                                                                                                                                                                                                                        | 237/1466 [00:07<01:17, 15.84it/s]


 16%|██████████████████████████████████████████                                                                                                                                                                                                                        | 239/1466 [00:08<01:19, 15.45it/s]


 16%|██████████████████████████████████████████▍                                                                                                                                                                                                                       | 241/1466 [00:08<01:21, 15.02it/s]


 17%|██████████████████████████████████████████▊                                                                                                                                                                                                                       | 243/1466 [00:08<01:20, 15.12it/s]


 17%|███████████████████████████████████████████▎                                                                                                                                                                                                                      | 246/1466 [00:08<01:09, 17.47it/s]


 17%|███████████████████████████████████████████▊                                                                                                                                                                                                                      | 249/1466 [00:08<01:00, 20.20it/s]


 17%|████████████████████████████████████████████▌                                                                                                                                                                                                                     | 253/1466 [00:08<00:52, 23.23it/s]


 17%|█████████████████████████████████████████████                                                                                                                                                                                                                     | 256/1466 [00:08<00:48, 24.84it/s]


 18%|█████████████████████████████████████████████▌                                                                                                                                                                                                                    | 259/1466 [00:08<00:46, 25.94it/s]


 18%|██████████████████████████████████████████████                                                                                                                                                                                                                    | 262/1466 [00:09<00:45, 26.45it/s]


 18%|██████████████████████████████████████████████▊                                                                                                                                                                                                                   | 266/1466 [00:09<00:42, 28.30it/s]


 18%|███████████████████████████████████████████████▌                                                                                                                                                                                                                  | 270/1466 [00:09<00:40, 29.65it/s]


 19%|████████████████████████████████████████████████▏                                                                                                                                                                                                                 | 274/1466 [00:09<00:38, 30.62it/s]


 19%|████████████████████████████████████████████████▉                                                                                                                                                                                                                 | 278/1466 [00:09<00:38, 31.19it/s]


 19%|█████████████████████████████████████████████████▋                                                                                                                                                                                                                | 282/1466 [00:09<00:37, 31.60it/s]


 20%|██████████████████████████████████████████████████▎                                                                                                                                                                                                               | 286/1466 [00:09<00:36, 31.93it/s]


 20%|███████████████████████████████████████████████████                                                                                                                                                                                                               | 290/1466 [00:09<00:36, 31.96it/s]


 20%|███████████████████████████████████████████████████▋                                                                                                                                                                                                              | 294/1466 [00:10<00:36, 32.15it/s]


 20%|████████████████████████████████████████████████████▍                                                                                                                                                                                                             | 298/1466 [00:10<00:36, 32.30it/s]


 21%|█████████████████████████████████████████████████████▏                                                                                                                                                                                                            | 302/1466 [00:10<00:36, 32.11it/s]


 21%|█████████████████████████████████████████████████████▊                                                                                                                                                                                                            | 306/1466 [00:10<00:36, 32.07it/s]


 21%|██████████████████████████████████████████████████████▌                                                                                                                                                                                                           | 310/1466 [00:10<00:36, 32.06it/s]


 21%|███████████████████████████████████████████████████████▎                                                                                                                                                                                                          | 314/1466 [00:10<00:35, 32.11it/s]


 22%|███████████████████████████████████████████████████████▉                                                                                                                                                                                                          | 318/1466 [00:10<00:35, 32.18it/s]


 22%|████████████████████████████████████████████████████████▋                                                                                                                                                                                                         | 322/1466 [00:10<00:35, 32.38it/s]


 22%|█████████████████████████████████████████████████████████▎                                                                                                                                                                                                        | 326/1466 [00:11<00:35, 32.52it/s]


 23%|██████████████████████████████████████████████████████████                                                                                                                                                                                                        | 330/1466 [00:11<00:35, 32.39it/s]


 23%|██████████████████████████████████████████████████████████▊                                                                                                                                                                                                       | 334/1466 [00:11<00:35, 32.18it/s]


 23%|███████████████████████████████████████████████████████████▍                                                                                                                                                                                                      | 338/1466 [00:11<00:35, 32.13it/s]


 23%|████████████████████████████████████████████████████████████▏                                                                                                                                                                                                     | 342/1466 [00:11<00:34, 32.22it/s]


 24%|████████████████████████████████████████████████████████████▉                                                                                                                                                                                                     | 346/1466 [00:11<00:34, 32.14it/s]


 24%|█████████████████████████████████████████████████████████████▌                                                                                                                                                                                                    | 350/1466 [00:11<00:35, 31.38it/s]


 24%|██████████████████████████████████████████████████████████████▎                                                                                                                                                                                                   | 354/1466 [00:11<00:35, 30.97it/s]


 24%|███████████████████████████████████████████████████████████████                                                                                                                                                                                                   | 358/1466 [00:12<00:35, 30.97it/s]


 25%|███████████████████████████████████████████████████████████████▋                                                                                                                                                                                                  | 362/1466 [00:12<00:35, 31.48it/s]


 25%|████████████████████████████████████████████████████████████████▍                                                                                                                                                                                                 | 366/1466 [00:12<00:34, 31.86it/s]


 25%|█████████████████████████████████████████████████████████████████                                                                                                                                                                                                 | 370/1466 [00:12<00:33, 32.24it/s]


 26%|█████████████████████████████████████████████████████████████████▊                                                                                                                                                                                                | 374/1466 [00:12<00:33, 32.48it/s]


 26%|██████████████████████████████████████████████████████████████████▌                                                                                                                                                                                               | 378/1466 [00:12<00:33, 32.78it/s]


 26%|███████████████████████████████████████████████████████████████████▏                                                                                                                                                                                              | 382/1466 [00:12<00:32, 32.87it/s]


 26%|███████████████████████████████████████████████████████████████████▉                                                                                                                                                                                              | 386/1466 [00:12<00:32, 32.92it/s]


 27%|████████████████████████████████████████████████████████████████████▋                                                                                                                                                                                             | 390/1466 [00:13<00:32, 33.01it/s]


 27%|█████████████████████████████████████████████████████████████████████▎                                                                                                                                                                                            | 394/1466 [00:13<00:32, 32.84it/s]


 27%|██████████████████████████████████████████████████████████████████████                                                                                                                                                                                            | 398/1466 [00:13<00:32, 32.55it/s]


 27%|██████████████████████████████████████████████████████████████████████▋                                                                                                                                                                                           | 402/1466 [00:13<00:34, 31.29it/s]


 28%|███████████████████████████████████████████████████████████████████████▍                                                                                                                                                                                          | 406/1466 [00:13<00:33, 31.80it/s]


 28%|████████████████████████████████████████████████████████████████████████▏                                                                                                                                                                                         | 410/1466 [00:13<00:32, 32.03it/s]


 28%|████████████████████████████████████████████████████████████████████████▊                                                                                                                                                                                         | 414/1466 [00:13<00:32, 32.17it/s]


 29%|█████████████████████████████████████████████████████████████████████████▌                                                                                                                                                                                        | 418/1466 [00:13<00:32, 32.48it/s]


 29%|██████████████████████████████████████████████████████████████████████████▎                                                                                                                                                                                       | 422/1466 [00:14<00:32, 32.58it/s]


 29%|██████████████████████████████████████████████████████████████████████████▉                                                                                                                                                                                       | 426/1466 [00:14<00:31, 32.68it/s]


 29%|███████████████████████████████████████████████████████████████████████████▋                                                                                                                                                                                      | 430/1466 [00:14<00:31, 32.62it/s]


 30%|████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                                                     | 434/1466 [00:14<00:31, 32.79it/s]


 30%|█████████████████████████████████████████████████████████████████████████████                                                                                                                                                                                     | 438/1466 [00:14<00:31, 32.88it/s]


 30%|█████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                                                    | 442/1466 [00:14<00:31, 32.90it/s]


 30%|██████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                                                   | 446/1466 [00:14<00:31, 32.69it/s]


 31%|███████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                                                  | 450/1466 [00:14<00:31, 32.74it/s]


 31%|███████████████████████████████████████████████████████████████████████████████▉                                                                                                                                                                                  | 454/1466 [00:14<00:30, 32.86it/s]


 31%|████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                                                                 | 458/1466 [00:15<00:30, 32.99it/s]


 32%|█████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                                                                | 462/1466 [00:15<00:30, 33.12it/s]


 32%|██████████████████████████████████████████████████████████████████████████████████                                                                                                                                                                                | 466/1466 [00:15<00:30, 33.14it/s]


 32%|██████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                                                               | 470/1466 [00:15<00:30, 33.02it/s]


 32%|███████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                                              | 474/1466 [00:15<00:30, 33.01it/s]


 33%|████████████████████████████████████████████████████████████████████████████████████                                                                                                                                                                              | 478/1466 [00:15<00:29, 33.04it/s]


 33%|████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                                             | 482/1466 [00:15<00:29, 33.01it/s]


 33%|█████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                                                            | 486/1466 [00:15<00:29, 33.10it/s]


 33%|██████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                                           | 490/1466 [00:16<00:29, 32.99it/s]


 34%|██████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                                                           | 494/1466 [00:16<00:30, 32.24it/s]


 34%|███████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                                                          | 498/1466 [00:16<00:29, 32.42it/s]


 34%|████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                                                         | 502/1466 [00:16<00:29, 32.65it/s]


 35%|█████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                                                         | 506/1466 [00:16<00:29, 32.83it/s]


 35%|█████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                                        | 510/1466 [00:16<00:29, 32.89it/s]


 35%|██████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                                       | 514/1466 [00:16<00:29, 32.81it/s]


 35%|███████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                                      | 518/1466 [00:16<00:29, 31.80it/s]


 36%|███████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                                      | 522/1466 [00:17<00:29, 32.10it/s]


 36%|████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                                                     | 526/1466 [00:17<00:29, 32.40it/s]


 36%|█████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                                                    | 530/1466 [00:17<00:28, 32.67it/s]


 36%|█████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                                                    | 534/1466 [00:17<00:28, 32.85it/s]


 37%|██████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                                                   | 538/1466 [00:17<00:28, 33.01it/s]


 37%|███████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                                  | 542/1466 [00:17<00:28, 33.00it/s]


 37%|████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                                                  | 546/1466 [00:17<00:27, 33.01it/s]


 38%|████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                                 | 550/1466 [00:17<00:27, 32.76it/s]


 38%|█████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                                | 554/1466 [00:18<00:27, 32.62it/s]


 38%|██████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                               | 558/1466 [00:18<00:27, 32.48it/s]


 38%|██████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                                               | 562/1466 [00:18<00:27, 32.58it/s]


 39%|███████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                                              | 566/1466 [00:18<00:27, 32.64it/s]


 39%|████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                                             | 570/1466 [00:18<00:27, 32.68it/s]


 39%|█████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                                             | 574/1466 [00:18<00:27, 32.80it/s]


 39%|█████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                                            | 578/1466 [00:18<00:27, 32.86it/s]


 40%|██████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                           | 582/1466 [00:18<00:26, 32.94it/s]


 40%|███████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                          | 586/1466 [00:19<00:26, 33.00it/s]


 40%|███████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                          | 590/1466 [00:19<00:26, 32.93it/s]


 41%|████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                                         | 594/1466 [00:19<00:26, 33.05it/s]


 41%|█████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                        | 598/1466 [00:19<00:26, 32.87it/s]


 41%|█████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                                        | 602/1466 [00:19<00:26, 32.85it/s]


 41%|██████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                                       | 606/1466 [00:19<00:26, 32.82it/s]


 42%|███████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                                      | 610/1466 [00:19<00:29, 29.10it/s]


 42%|████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                                      | 614/1466 [00:19<00:28, 29.88it/s]


 42%|████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                     | 618/1466 [00:20<00:27, 30.60it/s]


 42%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                                    | 622/1466 [00:20<00:26, 31.31it/s]


 43%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                                   | 626/1466 [00:20<00:26, 31.70it/s]


 43%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                                   | 630/1466 [00:20<00:26, 32.08it/s]


 43%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                                  | 634/1466 [00:20<00:25, 32.44it/s]


 44%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                                 | 638/1466 [00:20<00:25, 32.49it/s]


 44%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                                 | 642/1466 [00:20<00:25, 32.30it/s]


 44%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                                | 646/1466 [00:20<00:26, 31.19it/s]


 44%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                               | 650/1466 [00:21<00:25, 31.77it/s]


 45%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                               | 654/1466 [00:21<00:25, 32.14it/s]


 45%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                              | 658/1466 [00:21<00:24, 32.36it/s]


 45%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                             | 662/1466 [00:21<00:24, 32.59it/s]


 45%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                            | 666/1466 [00:21<00:24, 32.68it/s]


 46%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                            | 670/1466 [00:21<00:24, 32.79it/s]


 46%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                           | 674/1466 [00:21<00:24, 32.08it/s]


 46%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                          | 678/1466 [00:21<00:25, 30.72it/s]


 47%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                          | 682/1466 [00:22<00:25, 30.90it/s]


 47%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                         | 686/1466 [00:22<00:24, 31.42it/s]


 47%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                        | 690/1466 [00:22<00:24, 31.58it/s]


 47%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                       | 694/1466 [00:22<00:24, 31.71it/s]


 48%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                       | 698/1466 [00:22<00:24, 31.82it/s]


 48%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                                      | 702/1466 [00:22<00:23, 31.98it/s]


 48%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                     | 706/1466 [00:22<00:23, 31.96it/s]


 48%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                     | 710/1466 [00:22<00:23, 32.11it/s]


 49%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                                    | 714/1466 [00:23<00:23, 31.94it/s]


 49%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                                   | 718/1466 [00:23<00:23, 31.24it/s]


 49%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                                   | 722/1466 [00:23<00:24, 30.81it/s]


 50%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                                  | 726/1466 [00:23<00:24, 30.01it/s]


 50%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                                 | 730/1466 [00:23<00:24, 30.31it/s]


 50%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                                | 734/1466 [00:23<00:23, 30.81it/s]


 50%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                                | 738/1466 [00:23<00:23, 31.29it/s]


 51%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                               | 742/1466 [00:23<00:22, 31.49it/s]


 51%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                              | 746/1466 [00:24<00:22, 31.66it/s]


 51%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                              | 750/1466 [00:24<00:22, 31.99it/s]


 51%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                             | 754/1466 [00:24<00:22, 32.10it/s]


 52%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                            | 758/1466 [00:24<00:21, 32.38it/s]


 52%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                            | 762/1466 [00:24<00:21, 32.56it/s]


 52%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                           | 766/1466 [00:24<00:21, 32.70it/s]


 53%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                          | 770/1466 [00:24<00:21, 32.81it/s]


 53%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                         | 774/1466 [00:24<00:20, 32.99it/s]


 53%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                         | 778/1466 [00:25<00:20, 32.94it/s]


 53%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                        | 782/1466 [00:25<00:21, 32.45it/s]


 54%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                       | 786/1466 [00:25<00:21, 31.83it/s]


 54%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                       | 790/1466 [00:25<00:21, 32.16it/s]


 54%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                      | 794/1466 [00:25<00:21, 31.97it/s]


 54%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                                     | 798/1466 [00:25<00:21, 31.09it/s]


 55%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                                    | 802/1466 [00:25<00:21, 31.35it/s]


 55%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                                    | 806/1466 [00:25<00:21, 30.56it/s]


 55%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                                   | 810/1466 [00:26<00:21, 31.06it/s]


 56%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                  | 814/1466 [00:26<00:20, 31.66it/s]


 56%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                                  | 818/1466 [00:26<00:20, 31.25it/s]


 56%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                                 | 822/1466 [00:26<00:20, 31.32it/s]


 56%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                                | 826/1466 [00:26<00:20, 31.79it/s]


 57%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                                | 830/1466 [00:26<00:20, 31.46it/s]


 57%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                               | 834/1466 [00:26<00:20, 31.50it/s]


 57%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                              | 838/1466 [00:26<00:19, 31.70it/s]


 57%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                             | 842/1466 [00:27<00:19, 31.83it/s]


 58%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                             | 846/1466 [00:27<00:19, 31.93it/s]


 58%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                            | 850/1466 [00:27<00:19, 32.02it/s]


 58%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                           | 854/1466 [00:27<00:18, 32.26it/s]


 59%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                           | 858/1466 [00:27<00:18, 32.41it/s]


 59%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                          | 862/1466 [00:27<00:18, 32.49it/s]


 59%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                         | 866/1466 [00:27<00:18, 32.07it/s]


 59%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                         | 870/1466 [00:27<00:18, 32.01it/s]


 60%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                        | 874/1466 [00:28<00:18, 31.89it/s]


 60%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                       | 878/1466 [00:28<00:20, 29.10it/s]


 60%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                       | 881/1466 [00:28<00:20, 28.81it/s]


 60%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                      | 885/1466 [00:28<00:19, 29.25it/s]


 61%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                     | 889/1466 [00:28<00:19, 29.91it/s]


 61%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▏                                                                                                    | 893/1466 [00:28<00:18, 30.57it/s]


 61%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                                    | 897/1466 [00:28<00:18, 31.25it/s]


 61%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▌                                                                                                   | 901/1466 [00:28<00:17, 31.79it/s]


 62%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▎                                                                                                  | 905/1466 [00:29<00:18, 31.01it/s]


 62%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▉                                                                                                  | 909/1466 [00:29<00:18, 30.90it/s]


 62%|████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                                 | 913/1466 [00:29<00:19, 28.98it/s]


 63%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                                | 917/1466 [00:29<00:18, 29.35it/s]


 63%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████                                                                                                | 921/1466 [00:29<00:18, 29.97it/s]


 63%|██████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▊                                                                                               | 925/1466 [00:29<00:17, 30.73it/s]


 63%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▍                                                                                              | 929/1466 [00:29<00:17, 31.36it/s]

 63%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████▋                                                                                              | 930/1466 [00:29<00:17, 31.02it/s]
  0%|                                                                                                                                                                                                                                                                              | 0/10 [00:29<?, ?it/s]

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
Cell In[10], line 37
     35 logits = cbow(x)
     36 loss = criterion(logits, y)
---> 37 loss.backward()
     38 optimizer.step()
     40 monitoring_loss.append(float(loss))

File ~/.pyenv/versions/miniforge3-4.10.3-10/envs/datasci/lib/python3.10/site-packages/torch/_tensor.py:487, in Tensor.backward(self, gradient, retain_graph, create_graph, inputs)
    477 if has_torch_function_unary(self):
    478     return handle_torch_function(
    479         Tensor.backward,
    480         (self,),
   (...)
    485         inputs=inputs,
    486     )
--> 487 torch.autograd.backward(
    488     self, gradient, retain_graph, create_graph, inputs=inputs
    489 )

File ~/.pyenv/versions/miniforge3-4.10.3-10/envs/datasci/lib/python3.10/site-packages/torch/autograd/__init__.py:200, in backward(tensors, grad_tensors, retain_graph, create_graph, grad_variables, inputs)
    195     retain_graph = create_graph
    197 # The reason we repeat same the comment below is that
    198 # some Python versions print out the first line of a multi-line function
    199 # calls in the traceback and some print out the last line
--> 200 Variable._execution_engine.run_backward(  # Calls into the C++ engine to run the backward pass
    201     tensors, grad_tensors_, retain_graph, create_graph, inputs,
    202     allow_unreachable=True, accumulate_grad=True)

KeyboardInterrupt: 

13.3.4. 類似単語検索#

CBoWでは第一層目の結合重みが単語埋め込みベクトルとして利用できます.例えばこれは,以下のようなコードで取り出すことが可能です.

word_embeddings = list(cbow.embeddingbag.parameters())[0].data.detach().cpu().numpy()

ここから更にクエリとして与えられた単語に対応する単語埋め込みベクトルを取り出して,自分以外の全ての埋め込みベクトルとの類似度を計算することで,類似単語検索が実装できます. ここでは類似として コサイン類似度 (13.3)を使います.

(13.3)#\[ \cos (\mathbf{x}, \mathbf{y})=\frac{\langle\mathbf{x}, \mathbf{y}\rangle}{\|\mathbf{x}\|\|\mathbf{y}\|} =\frac{\sum_{k=1}^N x_k y_k}{\sqrt{\sum_{k=1}^N x_k^2} \sqrt{\sum_{k=1}^N y_k^2}} \]

ただし, \(\|\mathbf{x}\|=\sqrt{\sum_{k=1}^N x_k^2}\) はL2ノルム, \(\langle\mathbf{x}, \mathbf{y}\rangle=\sum_{k=1}^n x_k y_k\) はベクトルの内積です.

これが大きい順にtopn個を取り出して表示する関数を作りましょう.例えば,クエリとして「インド」を渡した時に,以下のような結果を返す予定です.

>>> インド
1:アフリカ 	0.9803917407989502
2:ホルシュタイン 	0.9631898403167725
3:セルビア 	0.962059497833252
4:ハンガリー 	0.9611229300498962
word_embeddings = list(cbow.embeddingbag.parameters())[0].data.detach().cpu().numpy()
def get_similar_words(query, topn=5, word2id=word2id, word_embeddings=word_embeddings):
    """単語埋め込みベクトルを使って似た単語を検索する

    Args:
        query (str): 類似単語を検索したい単語
        topn (int, optional): 検索結果の表示個数. Defaults to 5.
        word2id (dict[str,int], optional): 単語→単語idの辞書. Defaults to word2id.
        word_embeddings (np.ndarray, optional): 単語埋め込み行列.必ず(語彙数x埋め込み次元数)の行列であること. Defaults to word_embeddings.
    """
    id=word2id[query]
    E = (word_embeddings.T / np.linalg.norm(word_embeddings,ord=2, axis=1)).T # {(V,L).T / (V)}.T = (V,L)
    target_vector = E[id]
    cossim = E @ target_vector # (V,L)@(L)=(V)
    sorted_index = np.argsort(cossim)[::-1][1:topn+1] # 最も似たベクトルは自分自身なので先頭を除外

    print(f">>> {query}")
    _id2word = list(word2id.keys())
    for rank, i in enumerate(sorted_index):
        print(f"{rank+1}:{_id2word[i]} \t{cossim[i]}")
get_similar_words("ソフトウェア")
get_similar_words("インド")
get_similar_words("犬")
get_similar_words("日本")
>>> ソフトウェア
1:システム 	0.7365995049476624
2:アプリ 	0.7077406048774719
3:ネットワーク 	0.6998056173324585
4:計算 	0.6755282878875732
5:ファイル 	0.6713197827339172
>>> インド
1:ローマ帝国 	0.7319226861000061
2:山岳 	0.6649739742279053
3:パキスタン 	0.6315129399299622
4:ネパール 	0.6283044219017029
5:アメリカ大陸 	0.6265026926994324
>>> 犬
1:ペット 	0.6025487780570984
2:泥 	0.5757102370262146
3:和名 	0.553511381149292
4:炭 	0.5409188270568848
5:頁岩 	0.5395538806915283
>>> 日本
1:巨人 	0.507787823677063
2:台湾 	0.5001265406608582
3:英国 	0.4997516870498657
4:親善 	0.49010732769966125
5:低迷 	0.48958519101142883

今回の例では訓練に使うコーパスの量が圧倒的に足りないので,対応している語彙の数も学習して得られる単語埋め込みの質もイマイチです.そのため時間がある場合はtext8全体を利用して更なる実験を行なってみてください.より人間の感覚に近い類似単語検索が可能になるはずです.

13.4. 学習済みword2vecの利活用#

13.4.1. 類似単語検索#

Wikipediaのdumpファイルのような大規模で広いドメイン知識を含んだテキストを使って,word2vecやそれに類する手法を訓練したPretrained model, Pretrained weightsが様々なところで公開されています.ここではこの様な学習済みの単語埋め込みベクトルをダウンロードして,利用する手順を確認します.

日本語の学習済み単語埋め込みの例:

  1. 日本語 Wikipedia エンティティベクトル |東北大学 乾・岡崎研究室

  2. chiVe: SudachiとNWJCによる日本語単語ベクトル |Works Applications

今回は日本語 Wikipedia エンティティベクトル |東北大学 乾・岡崎研究室からファイル(20170201.tar.bz2)をダウンロードし,これを使って類似単語検索を行います. Pythonのトピックモデル手法パッケージであるGensimには,word2vecのクラスが実装されています.これを使ってもOKです.ここでは自力で埋め込みベクトルを取り出してみます.
ファイルの中身は一行目に「単語数,埋め込み次元数」が書かれています.また,データは全て半角スペースがセパレータとして利用されてます.

今回はデータ読み込みのために以下の様な関数を用意しました.この関数は返り値として,keyを単語,valueを埋め込みベクトルにした辞書keyedvectorsを返します.

def load_keyedvectors(fpath):
    keyedvectors = {}
    with open(fpath) as f:
        lines = f.readlines()[1:]
    with tqdm(total=len(lines)) as t:
        for i, line in enumerate(lines):
            word,*arr = line.split()
            keyedvectors[word] = np.array(arr).astype(np.float32)
            t.update(1)
    return keyedvectors

fpath="./data/entity_vector/entity_vector.model.txt"
kv=load_keyedvectors(fpath)
Hide code cell output
100%|██████████| 1015474/1015474 [01:14<00:00, 13692.18it/s]

類似単語検索の関数は上に示したものを少し修正すればいいでしょう.またはkvからword2idと単語埋め込み行列を使ってもいいかもしれません.何にせよ十分に訓練された単語埋め込みベクトルを使って,埋め込みベクトルが人間の感覚に近い結果を返すか確認してみましょう.

tohoku_w2id = {k:id for id,k in enumerate(kv)}
tohoku_emb = np.vstack([vec for vec in kv.values()])
topn=10
get_similar_words("ソフトウェア",topn,tohoku_w2id,tohoku_emb)
get_similar_words("インド",topn,tohoku_w2id,tohoku_emb)
get_similar_words("犬",topn,tohoku_w2id,tohoku_emb)
get_similar_words("東京",topn,tohoku_w2id,tohoku_emb)
>>> ソフトウェア
1:[ソフトウェア] 	0.9343680739402771
2:アプリケーション 	0.8889141082763672
3:ハードウェア 	0.8524743318557739
4:[アプリケーションソフトウェア] 	0.8515217900276184
5:ソフトウエア 	0.8409579992294312
6:ツール 	0.8184429407119751
7:[オペレーティングシステム] 	0.818361759185791
8:[ハードウェア] 	0.8154588341712952
9:ディストリビューション 	0.8022889494895935
10:[プラグイン] 	0.7999409437179565
>>> インド
1:[インド] 	0.8461795449256897
2:チベット 	0.7447131872177124
3:東南アジア 	0.7305631637573242
4:エジプト 	0.7292859554290771
5:アフリカ 	0.7172137498855591
6:イラン 	0.6968802213668823
7:西アジア 	0.6928515434265137
8:アラビア 	0.6927241683006287
9:中国 	0.6918002963066101
10:中東 	0.6847600936889648
>>> 犬
1:[犬] 	0.8519492745399475
2:[イヌ] 	0.8118769526481628
3:[ネコ] 	0.7639949917793274
4:[猫] 	0.7535459995269775
5:猟犬 	0.75133216381073
6:猫 	0.7439810037612915
7:[猟犬] 	0.7298945188522339
8:子犬 	0.727935254573822
9:[オオカミ] 	0.7274285554885864
10:[牧羊犬] 	0.7150676846504211
>>> 東京
1:大阪 	0.8608449697494507
2:[東京] 	0.8446128368377686
3:名古屋 	0.7717304825782776
4:[大阪] 	0.7522143721580505
5:横浜 	0.7329142093658447
6:神戸 	0.7294299602508545
7:京都 	0.7215739488601685
8:札幌 	0.7169389724731445
9:関西 	0.7126983404159546
10:浅草 	0.687187135219574

類似単語検索ではある程度納得できる答えが出ていると思います.このように大規模な言語資源を使って訓練された単語埋め込みモデルはベクトル表現として「言葉の意味」をある程度上手に獲得できる様です.

13.4.2. 単語ベクトルの足し算,引き算#

作成した単語埋め込みベクトルは,うまく訓練すると意味の足し引きができることが知られています.


Trained Word2Vec Vectors with Semantic and Syntactic relationship
出典: Word2Vec Research Paper Explained

# 例
女王 -  = 

これが正しく動作するか確認してみましょう.

def get_similar_words_from_vector(query, topn=5, word2id=word2id, word_embeddings=word_embeddings):
    E = word_embeddings.T / np.linalg.norm(word_embeddings,ord=2, axis=1)
    target_vector = query / np.linalg.norm(query, ord=2)
    cossim = target_vector@E # (K)@(K,V)->(V)
    sorted_index = np.argsort(cossim)[::-1][:topn]
    id2word = list(word2id.keys())
    for i in sorted_index:
        print(f"{id2word[i]} \t{cossim[i]}")

x = "女王"
y = "女"
print(f">>> {x}+{y}")
get_similar_words_from_vector(tohoku_emb[tohoku_w2id[x]] - tohoku_emb[tohoku_w2id[y]],
                  5,tohoku_w2id,tohoku_emb)

print('\n参考までに,"女王"と"女"と"王"の類似単語-----')
get_similar_words("女王",5,tohoku_w2id,tohoku_emb)
get_similar_words("女",5,tohoku_w2id,tohoku_emb)
get_similar_words("王",5,tohoku_w2id,tohoku_emb)
>>> 女王+女
女王 	0.4823855459690094
[エリザベス2世] 	0.4214708209037781
国王 	0.4064805507659912
[イギリスの君主] 	0.40320461988449097
[国王] 	0.39549916982650757

参考までに,"女王"と"女"と"王"の類似単語-----
>>> 女王
1:王女 	0.7546545267105103
2:[女王] 	0.7532833814620972
3:国王 	0.7170188426971436
4:王妃 	0.7075302600860596
5:[王配] 	0.6518748998641968
>>> 女
1:男 	0.8477675318717957
2:姫君 	0.6818373203277588
3:老女 	0.6539143323898315
4:美女 	0.6511508822441101
5:女房 	0.6428915858268738
>>> 王
1:[王] 	0.7630562782287598
2:は王 	0.7305535078048706
3:国王 	0.7254170775413513
4:大王 	0.7170721292495728
5:皇帝 	0.6928742527961731

期待通りの答えにはなっていませんが,訓練を工夫することで欲しい答えを返してきそうな雰囲気はありますね.他のキーワードペアも試してみましょう.

add_vecs = lambda x,y:(print(f">>> {x}+{y}"),get_similar_words_from_vector(tohoku_emb[tohoku_w2id[x]] + tohoku_emb[tohoku_w2id[y]],
                  5,tohoku_w2id,tohoku_emb))
sub_vecs = lambda x,y:(print(f">>> {x}-{y}"),get_similar_words_from_vector(tohoku_emb[tohoku_w2id[x]] - tohoku_emb[tohoku_w2id[y]],
                  5,tohoku_w2id,tohoku_emb))

add_vecs("王","女性")
add_vecs("王","女性")
sub_vecs("女王","女性");
add_vecs("ナルト","写輪眼")
sub_vecs("ナルト","写輪眼");
>>> 王+女性
王 	0.8152725100517273
女性 	0.7048345804214478
王妃 	0.6942119598388672
[王] 	0.6658982634544373
王族 	0.6649365425109863
>>> 王+女性
王 	0.8152725100517273
女性 	0.7048345804214478
王妃 	0.6942119598388672
[王] 	0.6658982634544373
王族 	0.6649365425109863
>>> 女王-女性
女王 	0.5956608057022095
国王 	0.40800678730010986
王 	0.3981504440307617
聖王 	0.39811018109321594
王国 	0.38871997594833374
>>> ナルト+写輪眼
ナルト 	0.9913040995597839
サスケ 	0.8586304783821106
[うずまきナルト] 	0.8437241315841675
カカシ 	0.8275482654571533
[うちはサスケ] 	0.8235551118850708
>>> ナルト-写輪眼
ナルト 	0.9860731959342957
[うずまきナルト] 	0.849785327911377
サスケ 	0.8380293846130371
カカシ 	0.8109898567199707
一護 	0.8019786477088928

13.5. word2vecの応用#

このような便利な特性を持つ単語埋め込みベクトルは,この論文の発表後に様々なNLP技術の中で当たり前に利用されるようになりました.前提として,通常データが少ない場合にはうまく単語の意味を訓練によって習得させることは難しいことが知られていましたが,このような問題にうまく対処できるのが,事前学習済み単語埋め込みの利用です.この例に大規模な言語リソースを使って事前訓練された単語埋め込みを使えば,効率的に各々のタスクを解決するモデルを作成できます.

例として,文書からの話題抽出タスクに事前学習モデルを利用する場合のワークフローを示します.下図において,NTM(ニューラルトピックモデル)は学習用コーパスのみを使って単語埋め込みを含めたモデルのパラメータを訓練します.これに対して,NTM-PWEは事前学習した埋め込みを利用します.この場合は単語埋め込みに相当するパラメータは学習用データを使ってパラメータ更新をしません.一番右のNTM-PWE/finetuningはNTM-PWEのように事前学習した埋め込みを利用し,単語埋め込みに相当するパラメータも学習用データを使ってパラメータ更新します.つまり,パラメータのより良い初期値として事前学習済み単語埋め込みを利用するということです.その方針を取るのかは状況によって異なりますが,多くの場合で事前学習済みモデルを初期値として利用すると良い結果をもたらすでしょう.


文書からの話題抽出タスクに事前学習モデルを利用する場合のワークフロー

この事前学習済みのモデルを(pretrained model, pretrained weights)などと呼びます.事前学習済みモデルを利用するアプローチは,現在ではNLPのみならず,CV(Computer Vision)などの様々な分野で当たり前に利用されています.

13.6. 参考文献#

DDF+90

Scott Deerwester, Susan T Dumais, George W Furnas, Thomas K Landauer, and Richard Harshman. Indexing by latent semantic analysis. J. Am. Soc. Inf. Sci., 41(6):391–407, September 1990. doi:10.1002/(sici)1097-4571(199009)41:6<391::aid-asi1>3.0.co;2-9.

LS99

D D Lee and H S Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401(6755):788–791, October 1999. doi:10.1038/44565.

LS00

Daniel Lee and H Sebastian Seung. Algorithms for non-negative matrix factorization. In T Leen, T Dietterich, and V Tresp, editors, Advances in Neural Information Processing Systems, volume 13. MIT Press, 2000.

MSC+13

Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. Adv. Neural Inf. Process. Syst., 2013.

MYZ13

Tomas Mikolov, Wen-Tau Yih, and Geoffrey Zweig. Linguistic regularities in continuous space word representations. In Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 746–751. Atlanta, Georgia, June 2013. Association for Computational Linguistics.

MCCD13

Tomás Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. Efficient estimation of word representations in vector space. In Yoshua Bengio and Yann LeCun, editors, 1st International Conference on Learning Representations, ICLR 2013, Scottsdale, Arizona, USA, May 2-4, 2013, Workshop Track Proceedings. 2013.