はじめに
ここでは、
- Greedy Search(貪欲法)
- Exhaustive Search（しらみつぶし探索）
- Beam Search(ビームサーチ)
これらのアルゴリズムを解説する
用語解説
$ \mathcal{V} $ : ボキャブラリー
$ |\mathcal{V}| $ : ボキャブラリー数
$\mathcal{T}$ : 文章の単語数
これらの $\mathcal{V}$ と $\mathcal{T}$ から得られる単語列は $ |\mathcal{V}|^\mathcal{T}$ の組み合わせがある。
仮に、ボキャブラリー $\mathcal{V}$ が[I, am, japanese]でボキャブラリー数 $|\mathcal{V}|$ が3個で、文章の単語数が3の場合を考えると、このとき文字列の候補は $3^3=27$ 個存在する。
具体的には
- I I I
- I I am
- I I japanese
- I am I
- I am am
- I am japanese
- I japanse I
- I japanese am
- I japanese japanese
- am I I …. …. ….
- japanese japanese japanese の計27個である
ここで、今回はボキャブラリー数が3個で、文章の単語数が3個と小さい値であったが、実際はボキャブラリー数が10,000個、単語数は500個ほどで合計で $10,000^500=1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000…$ の組み合わせを考える必要がある。
その際にすべての組み合わせの中から最も確率が高くなるような単語列を出力することを式で表すと下記のとおりになる。
$$ p(y_1,…,y_T|c)=\prod_{t=1}^{T}P(y_t|y_1,…,y_{t-1},c) $$
この確率を最大化するような単語列 $\textbf{y}(=y_1,…,y_T)$ を求める必要がある。
しかし、現在のPCでは、これらの組み合わせをすべて考えることは不可能なので、Greedy Seachといったアルゴリズムが考案された
Greedy Searchとは
数式解説
$$ y_t = \arg \max_{ y \in \mathcal{V}} P(y_t|y_1,…,y_{t-1},c) $$
となる単語$y_t$を順番に求めていき単語列$\textbf{y}(=y_1,…,y_T)$を求める。
Exhaustive Searchとは
数式解説
$$ \textbf{y}=y_1,…,y_T=\arg \max_{y_1,…,y_T}p(y_1,…,y_T|c) $$
をなる単語列$\textbf{y}$を直接求めることである。 しかし、これは愚直な方法で計算量が$O(|\mathcal{V}|^\mathcal{T})$かかってしまい現実的でない。
Beam Searchとは
数式解説
$$ \mathbf y_i^{’} = y_{1,i},…,y_{t,i}= arg topk_{y_{1,j},…,y_{t,j}}p(y_{1,j},…,y_{t,j}|c) $$
$$ \mathbf y_i^{’} = y_{1,i},…,y_{t,i} $$
ここで $1 \le i \le k, 1\le j\le k$
$k$ ビームサイズ
iは時刻tにおける確率が高い文字列のインデックスを表し、jは時刻t-1における確率が高い文字列のインデックスを表す。