文法の複雑さ

モデル化されるデータのタスクの複雑度の指標として perplexityを用いる。 perplexityは、情報理論的な意味での平均分岐数である。 例えば、言語$L$の1単語あたりのエントロピーが$H(L)$ならば、 次の単語を決定するのに$H(L)$回の選択が必要になる。 言い換えれば$2^{H(L)}$個の単語から1単語を選び出すことになる。

モデル化対象の集合を$L$とし、$L$のエントロピーを$H_0(L)$とする。 また、1単語あたりのエントロピー$H(L)$と エントロピーをもとに算出したパープレキシティ$F_p(L)$は 次のように求められる [8] 。

$$L = \{w^i_k \mid w^i_k = w_{i1} w_{i2} \ldots w_{ik}\}, \makebox[2em]{} \ldots \mbox{ 言語$L$の文集合}$$

$$H_0(L) = - \sum_{w^i_k} P(w^i_k) \log_2 P(w^i_k), \makebox[3.5em]{} \ldots \mbox{ 言語$L$のエントロピー}$$

$$H(L) = - \sum_{w^i_k} \frac{1}{k} P(w^i_k) \log_2 P(w^i_k), \makebox[2.8em]{} \ldots \mbox{ 言語$L$の1文あたりのエントロピー}$$

$$F_p(L) = 2^{H(L)}. \makebox[11em]{} \ldots \mbox{ 言語$L$のパープレキシティ} \nonumber$$