メインコンテンツへスキップ
見出し画像

言語AIの進化史⑥シャノンのn-gram

    前回は、フレーム理論やオントロジーについて解説し、知識を論理的に扱うためのデータ構造やロジックの発展を追ってきました。

    これらの手法は、人間が考えたデータ構造やロジックによって言語を処理するものであり、言語というテキストデータの中に秘められた内部構造をモデル化するものではありません。

    そこで今回は、テキストデータの統計的特性を解析するための手法として考案されたn-gramを紹介します。

    n-gramの概念を考案したのはクロード・シャノンです。1948年に発表し情報理論の基礎を築いた論文「A Mathematical Theory of Communication」において初めて紹介されました。

    当時、クロード・シャノンはデータ通信の効率性を高めるための研究をしており、データ通信において多くの情報をできるだけ少ないビット数で表現する手法を研究していました。これを達成するために、シャノンは以下のような原則を用いました。

    • 頻度の高いデータを少ないビット数で表現する

    • 頻度の低いデータにはより多いビット数を使う

    つまり、よく使われるデータには短いビット列を割り当て、使用頻度が低いデータには長いビット列を割り当てることで、全体のデータ量を減らすことができる、というわけです。この方法によって、シャノンはデータ通信の効率を向上させる理論を構築しました。

    また、データの頻度に関する情報を計算する指標として情報エントロピー(以下、エントロピーと略)が考案されました。エントロピーはデータの出現確率によって決まる量であり、どのデータにどのくらいのビット数を使うかを決めることができます。n-gram は連続した文字列の出現確率を計算し、そのエントロピーを求めるために使われました。

    このように、クロード・シャノンが n-gram モデルを情報理論の文脈で提案した際、彼の主要な目的はデータの圧縮や通信の効率化に関するものであって、自然言語処理における具体的な応用を念頭に置いていたわけでありません。

    しかし、シャノンの n-gram モデルは、後の言語モデルや自然言語処理に大きな影響を与えたことは確かです。

    なお、エントロピーについてはこちらで具体例を使って解説しています。

    情報量とは

    定義

    あるデータやイベントをiiで表現します。そして、このデータあるいはイベント(以下、単にイベントと呼ぶ)が出現する確率をP(i)P(i)とすると、その情報量は次のように定義されます。

    −log⁡P(i)- \log P(i)

    P(i)P(i)は確率なので、0から1の値になります。よって、その対数log⁡P(i)\log P(i)は負の無限大から0の範囲の値になります。これにマイナスをつけるので、−log⁡P(i)- \log P(i)の値は、0から正の無限大になります。

    つまり、確率が0に近いほど、情報量は大きくなります。また、確率が1に近いほど情報量が0に近づきます。

    具体例

    ある地域のある季節における天気の確率が以下になっているとします。

    • P(晴)P(\text{晴}):78%

    • P(曇)P(\text{曇}):12%

    • P(雨)P(\text{雨}): 9%

    • P(雪)P(\text{雪}): 1%

    これを情報量で表現すると以下になります。

    • P(晴)P(\text{晴}):−log⁡20.78≈0.36-\log_2 0.78 \approx 0.36

    • P(曇)P(\text{曇}):−log⁡20.12≈3.06-\log_2 0.12 \approx 3.06

    • P(雨)P(\text{雨}):−log⁡20.09≈3.47-\log_2 0.09 \approx 3.47

    • P(雪)P(\text{雪}):−log⁡20.01≈6.64-\log_2 0.01 \approx 6.64

    ここでは基底2の対数を使っており、情報量がビットで計算されています。

    情報量を自然対数(基底e)で計算しても情報量の大小の比較には問題ありません。機械学習では自然対数の方が計算が簡単になるのでよく使われます。ただし、ビット数としての解釈はできません。

    直感的に言うと、稀な出来事の方が情報としてのインパクトが大きくなります。したがって、情報量はあるイベントが発生した時の驚きの度合いを表現しているとも言えます。

    エントロピーとは

    定義

    エントロピーは、あるデータセットに含まれる情報の平均量を表します。

    確率 P(i)P(i) で発生するイベントiiのエントロピー HH は以下の式で定義されます。

    H=−∑iP(i)log⁡P(i)H = - \sum\limits_i P(i) \log P(i)

    よって、エントロピーは各情報量にその確率をかけて和をとったものです。

    H= ∑iP(i)×情報量H =  \sum\limits_i P(i) \times \text{情報量}

    要するに、エントロピーとは情報量の期待値です。

    具体例

    前述した天気の例でエントロピーを計算します。

    H= 0.78×0.36 +(晴)    0.12×3.06 +(曇)    0.09×3.47 +(雨)    0.01×6.64      (雪)≈ 1.03 ビット\begin{aligned} H =\ &0.78 \times 0.36  + \quad (\text{晴}) \\        &0.12 \times 3.06  + \quad (\text{曇}) \\        &0.09 \times 3.47  + \quad (\text{雨}) \\        &0.01 \times 6.64     \quad\ \ \ (\text{雪}) \\ \approx\ &1.03 \text{ ビット} \end{aligned}

    この結果から、この地域の天気に関する情報のエントロピーが約1.03ビットであることがわかります。これは、平均的にそれだけのビットが通信に必要だということです。

    ただし、エントロピーは理論的な最小値であり、実際にデータをエンコードする場合には必要となるビット数は変わってきます。

    エンコーディングの実例

    この地域の天気の情報を通信データにして送ることを考えます。4つのパターンしかないので、最大でも2ビットあれば十分です。

    そこで情報量の少ない天気(晴と曇)に対して1ビットを使い、情報量の多い天気(雨と雪)に対して2ビットを使うことにします。つまり、次のように天気情報を伝えます。

    • P(晴)P(\text{晴}): 0 (1ビット)

    • P(曇)P(\text{曇}): 1 (1ビット)

    • P(雨)P(\text{雨}):10 (2ビット)

    • P(雪)P(\text{雪}):11 (2ビット)

    平均的なビット数は以下になります。

    0.78×1 ビット +0.12×1 ビット +0.09×2 ビット +0.01×2 ビット=1.1 ビット \begin{aligned} &0.78 \times 1 \text{ ビット} \ + \\ &0.12 \times 1 \text{ ビット} \ + \\ &0.09 \times 2 \text{ ビット}\ + \\ &0.01 \times 2 \text{ ビット} = 1.1 \text{ ビット}  \end{aligned}

    このエンコーディングでは、1.1 ビットが必要です。エントロピーによる理想的な最低値は約1.03ビットなので近い値になりました。

    しかし、次のようにエンコーディングを変更したらどうでしょうか。

    • P(晴)P(\text{晴}):11 (2ビット)

    • P(曇)P(\text{曇}):10 (2ビット)

    • P(雨)P(\text{雨}): 1 (1ビット)

    • P(雪)P(\text{雪}): 0 (1ビット)

    平均的なビット数は以下になります。

    0.78×2 ビット +0.12×2 ビット +0.09×1 ビット +0.01×1 ビット=1.9 ビット \begin{aligned} &0.78 \times 2 \text{ ビット}\ + \\ &0.12 \times 2 \text{ ビット}\ + \\ &0.09 \times 1 \text{ ビット}\ + \\ &0.01 \times 1 \text{ ビット} = 1.9 \text{ ビット}  \end{aligned}

    つまり、平均的に必要なビット数は2に近くなります。情報量が少ないイベントに2ビットを費やしているからです。よって、効率的ではありません。

    以上より、理論的なエントロピーと実際のエンコードにおける違いが明確になりました。また、エントロピーがエンコーディングの効率性を評価するのに使えるのがわかります。

    エントロピーとn-gram

    テキストデータをエンコードする際にエントロピーを利用することを考えます。

    uni-gramの例

    まず、各文字を独立に扱う場合であるuni-gram(ユニグラム)を考えます。この場合、各文字の出現確率に基づいて情報量を計算します。

    例えば、以下のような確率で文字が出現するとします。

    • P(こ)=0.1P(\text{こ}) = 0.1

    • P(ん)=0.2P(\text{ん}) = 0.2

    • P(に)=0.3P(\text{に}) = 0.3

    • P(ち)=0.2P(\text{ち}) = 0.2

    • P(は)=0.2P(\text{は}) = 0.2

    このデータセットには、これ以外の文字はないとします。よって、確率の合計は1になります。

    そして、これらの情報量は次のように計算されます。

    I(こ)=−log⁡20.1≈3.32I(ん)=−log⁡20.2≈2.32I(に)=−log⁡20.3≈1.74I(ち)=−log⁡20.2≈2.32I(は)=−log⁡20.2≈2.32\begin{aligned} I(\text{こ}) &= -\log_2 0.1 \approx 3.32 \\ I(\text{ん}) &= -\log_2 0.2 \approx 2.32 \\ I(\text{に}) &= -\log_2 0.3 \approx 1.74 \\ I(\text{ち}) &= -\log_2 0.2 \approx 2.32 \\ I(\text{は}) &= -\log_2 0.2 \approx 2.32 \end{aligned}

    よって、このデータセットのエントロピーは次のように計算されます。

    H= 0.1×3.32 + 0.2×2.32 + 0.3×1.74 + 0.2×2.32 + 0.2×2.32≈ 2.27 ビット\begin{aligned} H = & \ 0.1 \times 3.32 \ + \\ & \ 0.2 \times 2.32 \ + \\ & \ 0.3 \times 1.74 \ + \\ & \ 0.2 \times 2.32 \ + \\ & \ 0.2 \times 2.32 \\ \approx & \ 2.27 \text{ ビット} \end{aligned}

    よって、この例では、uni-gram は 2.27 ビットが必要となります。

    bi-gramの例

    次に、bi-gram(バイグラム)モデルを使った場合を考えます。この場合、文字の連続したペアの出現確率を考慮します。

    例えば、以下のようなバイグラムの確率があるとします。

    • P(こに)=0.1P(\text{こに}) = 0.1

    • P(んに)=0.2P(\text{んに}) = 0.2

    • P(にち)=0.3P(\text{にち}) = 0.3

    • P(ちは)=0.2P(\text{ちは}) = 0.2

    • P(には)=0.2P(\text{には}) = 0.2

    これらの情報量は次のように計算されます。

    I(こに)=−log⁡20.1≈3.32I(んに)=−log⁡20.2≈2.32I(にち)=−log⁡20.3≈1.74I(ちは)=−log⁡20.2≈2.32I(には)=−log⁡20.2≈2.32 \begin{aligned} I(\text{こに}) &= -\log_2 0.1 \approx 3.32 \\ I(\text{んに}) &= -\log_2 0.2 \approx 2.32 \\ I(\text{にち}) &= -\log_2 0.3 \approx 1.74 \\ I(\text{ちは}) &= -\log_2 0.2 \approx 2.32 \\ I(\text{には}) &= -\log_2 0.2 \approx 2.32  \end{aligned}

    これ以外の組み合わせは存在しない(確率が0)とします。

    このデータセットのエントロピーは次のように計算されます。

    H= 0.1×3.32 +0.2×2.32 +0.3×1.74 +0.2×2.32 +0.2×2.32≈ 2.20 ビット\begin{aligned} H = \ &0.1 \times 3.32\ + \\ &0.2 \times 2.32\ + \\ &0.3 \times 1.74\ + \\ &0.2 \times 2.32\ + \\ &0.2 \times 2.32 \\ \approx \ &2.20 \text{ ビット} \end{aligned}

    よって、この例では、bi-gram は 2.20 ビットが必要となります。

    この例ではあまり明らかではないですが、仮にある組み合わせがより多く出現する場合は、エントロピーが低くなるので、より少ないビット数でデータを表現することが可能になります。

    もちろん、テキストデータ次第ではそれほどの効果はないかもしれませんが、通常テキストデータは完全にランダムでないことを考えると bi-gram の方が uni-gram よりも効率的なエンコーダが可能になるはずです。

    bi-gramの情報量

    bi-gram における情報量は、次のように定義されます。

    −log⁡P(j∣i)-\log P(j \mid i)

    ここで、P(j∣i)P(j \mid i) は、文字 ii が出現した後に文字 jj が出現する条件付き確率です。よって、bi-gramの情報量は、2つの文字がある順番で並んで出現する確率から計算されます。

    つまり、文字 ii と jj がこの順番で連続して現れる確率が大きければ、そのような並びの情報量は小さくなります。

    bi-gramのエントロピー

    bi-gram によるエントロピーは、次のように計算されます。

    H=−∑iP(i)∑jP(j∣i)log⁡P(j∣i)H = - \sum_{i} P(i) \sum_{j} P(j \mid i) \log P(j \mid i)

    ちょっと複雑に見えますが、分解するとわかりやすくなります。

    • 内側の和の部分 −∑jP(j∣i)log⁡P(j∣i)-\sum_{j} P(j \mid i) \log P(j \mid i)は、文字 ii が出現した後に、文字 jjが続いた場合の情報量の期待値です。つまり、文字 iiが生じたことが期待値の計算の条件となっています。

    • 外側の和の部分 ∑iP(i)\sum_{i} P(i)があるのは、文字 ii の出現確率を掛け合わせることで、全体の期待値を計算しているからです。

    上記の式は、通常以下のように短縮した和の表記で表現されます。

    H=−∑i,jP(i,j)log⁡P(j∣i)H = - \sum_{i,j} P(i, j) \log P(j \mid i)

    ここで、∑i,j\sum_{i,j}は、文字 ii と文字 jj がこの順番に出現したケースに対しての和を計算しています。また、P(i,j)=P(i)P(j∣i)P(i, j) = P(i) P(j \mid i)で 文字 ii と文字 jj が共に出現する確率です。

    以上より、データセットから bi-gram によるエントロピーの計算が行えます。

    n-gramへの一般化

    3つの文字が続く場合は、tri-gram(トリグラム)となりますが、考え方は同じです。条件がもう一つ増えるだけです。

    もっと一般的に考えれば、n-gram となります。n の数値が変わると、条件確率の式が変わります。

    n-gramモデルを使うことで、文字の並び順の傾向を取り入れることができます。つまり、連続する文字や単語の依存関係を考慮することで、独立した文字の扱いよりもエントロピーが低減します。出現確率による情報量に従って、効率的なデータ圧縮が可能になります。

    n-gramと言語モデル

    シャノンのn-gramアプローチは、テキストの意味をまったく考えず、確率にのみ依存しています。この手法は、意味ネットワークやオントロジーとは大きく異なります。

    n-gram を言語モデルとして考えると、テキストデータの統計的特性を自然に取り入れ、次に来るアイテムを条件確率分布で予測することができます。また、このシンプルなアプローチは、計算とメモリ使用量が少なく、扱いやすい技術として広まりました。そのため、多くの自然言語処理アプリケーションで基礎技術として採用されました。

    n-gramモデルは、テキスト分類などのさまざまに応用されました。

    スパム・フィルタリング

    初期のスパムフィルタリングでは、n-gramモデルがよく使われました。

    メールの内容を解析してスパムメールを識別する際に、特定のn-gramパターンがスパムメールに頻繁に出現することを利用します。例えば、「無料」「クレジットカード」「特典」といった連続した単語やフレーズの出現頻度を分析することで、スパムメールを効果的に検出できます。

    テキスト分類

    n-gramモデルは、感情分析などのテキスト分類にも応用されます。

    例えば、映画のレビューをポジティブなものとネガティブなものに分類する場合、n-gramモデルを使って特定のフレーズや単語の出現頻度を分析します。ポジティブなレビューでは「素晴らしい」「感動した」などのフレーズが多く、ネガティブなレビューでは「退屈」「失望」などのフレーズが多く出現するため、これらのパターンを元に分類します。

    次に来る単語の予測

    n-gramモデルは、次に来る単語の予測に利用できます。

    特定の単語シーケンスが与えられたとき、そのシーケンスに続く単語の確率を計算します。これにより、文章を自然な形で続けることができます。

    例えば、「私は今日」というシーケンスが与えられた場合、「学校に行きます」や「友達と会います」といった続きが高確率で予測されます。

    ランダムなテキスト生成

    n-gramモデルは、ランダムなテキスト生成にも使われます。これは、ある単語やフレーズに続く単語を確率的に選択することで実現されます。

    例えば、「私」は次に「は」「が」「に」などの単語が続く確率を持ち、それぞれの確率に基づいて次の単語が選ばれます。このプロセスを繰り返すことで、自然な文脈を持つランダムなテキストが生成されます。この技術は、チャットボットや対話システムの初期の開発において重要な役割を果たしました。

    n-gram の限界

    上述の例などからも、n-gramモデルは、単語や文字のシーケンスを考慮することで、ある程度の文脈を取り入れています。

    しかし、n-gramモデルは取り入れる文脈の範囲が限られています。例えば、bi-gramモデルは直前の単語のみ、tri-gramモデルは直前の2単語のみを考慮します。文脈の範囲を広げるためには、nnを増やす必要がありますが、nnが大きくなると計算量とデータの必要量が急増します。

    より複雑な文脈を考慮するためには、後に登場するリカレントニューラルネットワーク(RNN)やトランスフォーマーモデルなどのより高度な手法が必要になります。

    次回予告

    シャノンの n-gram では、テキストを連続した文字のシーケンスとして捉えています。ただし、統計的な言語モデルが発展するためにはトークン化されたコーパスの出現が重要となります。次回は、様々なトークン化の手法を紹介します。

    お楽しみに!

     
     
    「わかりやすく、具体的に」AIとサイエンスの情報を発信中

    あなたへのおすすめ