本記事は、元記事を翻訳した記事の後編となります。
A節については 前編 をご参照ください。

もう一歩進んだマルコフモデル ????

＊＊免責事項＊＊ ???? 上で説明したマルコフモデルを作る時と同じプロセスで進めますが、いくつかのステップは省きます。もし、何か分からないことが出てきたら、最初のセクションを参照してください????

1.スケールアップした例

最初のドクター・スースの言葉はそのまま取っておき、私が更に見つけた、ドクター・スースの 不朽の 名言を4つご紹介します。

Today you are you. That is truer than true. There is no one alive who is you-er than you

You have brains in your head. You have feet in your shoes. You can steer yourself any direction you choose. You’re on your own

The more that you read, the more things you will know. The more that you learn, the more places you’ll go

Think left and think right and think low and think high. Oh, the thinks you can think up if only you try
ドクター・スース ????

最初の文章と、これらの新しい文章の最も大きな違いは、いくつかの キー においては、異なるキーが 不規則な回数 、続いている点です。例えば “more” は “the” の後に4回続いています。では新たに加わった複雑さは、マルコフモデルにどのような影響を与えるのでしょうか？　???? 全体としては、文章の論理的結論を 改善できる でしょう。つまり何が言いたいかというと、英語という言語では、ある単語が他の単語より多く出現するということです（これについては、どんな言語でも同じことが言えます）。例えば、毎日の会話の中で “a” は “wizard” よりもずっと多く出てきます????　世の中の仕組みと同じです。これを考えると、あるキーの出現回数が他のキーよりも多く出現するということは、原文により近づけるために 非常に重要 なことです????　マルコフモデルでは、次のステップを決める際に 重み付け を考慮することが知られています。

各 キー に続く、 キー とその出現回数が保存されたウィンドウをプログラム上????で示す方法があります。これがディクショナリの使用で、ディクショナリの キー は 現在のウィンドウ を示します。そして ディクショナリのキー の値を、 キー として追従する 固有のトークン を保存する別のディクショナリに変えます。そして、それらの値が 出現回数 となります。これを聞いて、すでに説明した内容を思い出しませんか????？ ヒストグラム ！　その通りです。 内部のディクショナリ は単独で キー と出現回数の記録を行うヒストグラムに分割されます。そう、驚くほどたくさんのキー????とディクショナリが出現します。もしコードに興味があれば、以下をチェックしてください????。しかし興味がない場合でも認識だけはしておいてください。これは、より高度なモデルを作成する上で、どの キー がどの キー に続くかを追跡し、そしてそれらのキーの 出現回数 を記録する必要があります。

2. 分布

それでは、短い余談の後、実際の例を見て説明していきましょう????????　優れたコーパスにするには とても 小さいですが、このデータセットはクールです。なぜかって？　異なる言葉の分布を得ることができる素晴らしい点がありますし、構造全体に影響を与えることができるからです。しかし、 固有で自然 に生成された文を生成することを目的とした大きなスコープの場合には、 最低でも20,000 トークンはあった方がいいでしょう。最低 100,000 トークンあれば、なおいいと思います。そして、驚くほど素晴らしいモデルを作りたいなら、 500,000 以上のトークンを目指してください????

では、以下のように大規模な例を使って、単語の分布がどのように 1つのキーウィンドウ に配置されるかについて見ていきましょう。

色分けされたキーの分布

これは素晴らしいですね????　全データを見てください。事前にデータをきれいに整理しておいたので、コーパスの各一意の キー には、それに続く キー と 出現回数 が含まれた配列が表示されています。いいですね！

ここで秘密をお教えしましょう????　今回のマルコフモデルと最初のモデルとでは、少し違いがあります。どちらの場合も 単に現在の状態に基づいて 次のステップが決められていますが、単語の分布を保存することは、次のステップの重み付けを可能にします。実際の例を使って説明しましょう。

more : [things : 1, places : 1, that : 2]

素晴らしい！????　マルコフモデルの現在の状態が “more” であった場合、次に続く単語は、 “things” 、 “places” または “that” のどれかがランダムに選択されることになります。しかし “that” の出現回数は、 “things” や “places” の2倍です。つまり、 “that” が選択される可能性は50％、 “things” もしくは “places” が選択される可能性は25％ということになります！????

think : [high : 1, up : 1, right : 1, low : 1, left : 1]

☝️☝️☝️いいですね。では、上記に似た例を見てみます。今回のように、 “think” が現在の状態であった場合、 “high” 、 “up” 、 “right” 、 “low” 、そして “left” の単語が次の状態として選択される可能性は、それぞれ20％となります。理解できましたか？????

3. さらに大きなウィンドウ

これまでは、 ウィンドウ のサイズが1つの場合のマルコフモデルを見てきました。それでは、より “正確”な文 を取得するために、ウィンドウのサイズを増やしてみたいと思います。ここで言う正確とは、モデルによって生成される文のランダム性を軽減するということです。そうすることで、コーパスにある原文により近づけることができるのです。ただし、この処理が良い場合もあれば悪い場合もあります???? ????　と言うのも、マルコフモデルの目的が一意のランダムな文を忠実に生成することである場合、小さなウィンドウにする必要があるからです。大きなウィンドウを使用するのは、 100,000以上のトークン を含む 著しく 大きなコーパスの場合にのみ有効的です。

ウィンドウのサイズを増やすことを、マルコフモデルでは “高次” と呼んでいて、これまでの例で示してきたモデルは 一次マルコフモデル と言います。つまり二次マルコフモデルと言った場合は、ウィンドウのサイズが2つということになります！　同様に、三次であればウィンドウサイズは3つです。

ウィンドウとはマルコフモデルの現在の状態があるデータのことで、意思決定をする際に使用されます。小さなデータセット内に大きなウィンドウがあった場合、1つのウィンドウから起こるであろう結果に対する、大きな一意の分布があることは考えにくくなります。そのため、 同じ文が改めて生成されるだけ でしょう。

二次マルコフモデル 、つまりウィンドウのサイズが2つある場合のモデルを使ったオリジナルの例を見てみましょう！

二次マルコフモデル

とても興味深いですね！　何か気付いたことはありますか？????️　一意のウィンドウサイズが2つである全ウィンドウには、 起こるであろう結果が1つ しかないことに気付いたでしょう。つまりこれは、どの単語から開始したとしても、常に同じ文を取得するということになります。なぜなら、オリジナルの過程から外れてしまう可能性がないからです。同じ文が生成される確率は100％となります????　よくないですね。これは、マルコフモデルが持つ潜在的な問題を明らかにしています。十分に大きなサイズのコーパスを持っていないと、一意の文を生成することのないコーパス内で、単に文を生成するだけということなります。 500,000以上のトークンを含む大規模なデータセット を入手し、 異なる高次 マルコフモデルを使って 色々と試してみてください ????

Pythonでの実装????

1. Dictogramデータ構造

Dictogramの目的は、ヒストグラムと同様の働きをさせることですが、こちらの場合は起動が非常に早く????、データセットの大きさにかかわらず、一定の時間で検索を行ってくれます。簡単に言うと、Dictogramはディクショナリを使ったヒストグラム構築と言えます。なぜならディクショナリには、一定の検索時間O(1)を持つ一意のプロパティがあるからです！

import random

class Dictogram(dict):
    def __init__(self, iterable=None):
        """Initialize this histogram as a new dict; update with given items"""
        super(Dictogram, self).__init__()
        self.types = 0  # the number of distinct item types in this histogram
        self.tokens = 0  # the total count of all item tokens in this histogram
        if iterable:
            self.update(iterable)

    def update(self, iterable):
        """Update this histogram with the items in the given iterable"""
        for item in iterable:
            if item in self:
                self[item] += 1
                self.tokens += 1
            else:
                self[item] = 1
                self.types += 1
                self.tokens += 1

    def count(self, item):
        """Return the count of the given item in this histogram, or 0"""
        if item in self:
            return self[item]
        return 0

    def return_random_word(self):
        # Another way:  Should test: random.choice(histogram.keys())
        random_key = random.sample(self, 1)
        return random_key[0]

    def return_weighted_random_word(self):
        # Step 1: Generate random number between 0 and total count - 1
        random_int = random.randint(0, self.tokens-1)
        index = 0
        list_of_keys = self.keys()
        # print 'the random index is:', random_int
        for i in range(0, self.types):
            index += self[list_of_keys[i]]
            # print index
            if(index > random_int):
                # print list_of_keys[i]
                return list_of_keys[i]

Dictogramクラスは、単語リストや書籍全体といった、繰り返し使用が可能なデータセットを使って作成することができます。私は、Dictogramクラスを作成する際に トークン 数と キー 数を記録しておき、全データセットを調べることなく、これらの値にアクセスできるようにしておきました????

また、ランダムな単語を返す2つの関数も作成したので、こちらも覚えておくといいでしょう。1つは、 ランダムなキーを選択する だけの関数で、もう1つは、各単語に対する出現回数を考慮し、 重み付けされたランダムな単語 を返す関数です????️♀️

2. マルコフモデル構造

マルコフモデルが 何なのか から話を初めて、ここまでくるのに随分と長い旅でした。ここからは、マルコフモデルを どのように 実装するかについて話していきたいと思います????

from histograms import Dictogram

def make_markov_model(data):
    markov_model = dict()

    for i in range(0, len(data)-1):
        if data[i] in markov_model:
            # We have to just append to the existing histogram
            markov_model[data[i]].update([data[i+1]])
        else:
            markov_model[data[i]] = Dictogram([data[i+1]])
    return markov_model

私の実装では、 Key-Valueペアにあるキー として ウィンドウ を保存する ディクショナリ を持っており、各 キー の 値 が Dictogram となります。つまり、各ウィンドウに単語のヒストグラムを保存することで、現在の状態に基づいた次の状態が何であるかを知ることができます????　現在のウィンドウにデータが存在する場合は、キーに対するDictogram内のデータをインクリメントします。

3. 高次マルコフモデル構造

高次マルコフモデルをどのように実装するのか 気になっている方もいると思います。私がどのように行ったのか、以下で説明しましょう????

from histograms import Dictogram


def make_higher_order_markov_model(order, data):
    markov_model = dict()

    for i in range(0, len(data)-order):
        # Create the window
        window = tuple(data[i: i+order])
        # Add to the dictionary
        if window in markov_model:
            # We have to just append to the existing Dictogram
            markov_model[window].update([data[i+order]])
        else:
            markov_model[window] = Dictogram([data[i+order]])
    return markov_model

☝️☝️☝️☝️☝️ 一次マルコフモデルと非常によく似ていますが、この場合、 Key-Valueペア 内に キー として タプル を ディクショナリ に保存しています。その理由は、シングルリストを表すには タプル が最適な方法だからです。また、リストの代わりにタプルを使うのは、ディクショナリ内のキーが変更されるべきではないからです。タプルは不変なので、変更されることはありません????‍♂️

4. マルコフモデルの解析

やりました！！???????? ???? Dictogramの実装が完了しました。しかし、 現在の状態 に基づくコンテンツを生成してから、新しい状態へのステップはどうなるのでしょう？????????????以下のモデルを使って説明します????

from histograms import Dictogram
import random
from collections import deque
import re


def generate_random_start(model):
    # To just generate any starting word uncomment line:
    # return random.choice(model.keys())

    # To generate a "valid" starting word use:
    # Valid starting words are words that started a sentence in the corpus
    if 'END' in model:
        seed_word = 'END'
        while seed_word == 'END':
            seed_word = model['END'].return_weighted_random_word()
        return seed_word
    return random.choice(model.keys())


def generate_random_sentence(length, markov_model):
    current_word = generate_random_start(markov_model)
    sentence = [current_word]
    for i in range(0, length):
        current_dictogram = markov_model[current_word]
        random_weighted_word = current_dictogram.return_weighted_random_word()
        current_word = random_weighted_word
        sentence.append(current_word)
    sentence[0] = sentence[0].capitalize()
    return ' '.join(sentence) + '.'
    return sentence

さて、個人的には、有効な最初の文の単語だけを使いたいと思っていたので、 END キーのDictogram内を全て確認しました????　他の方法としては、（有効な最初の文から生成された） 最初の状態 を使って生成されたデータから開始し、 現在の状態に続く可能性のあるキー を（Dictogram内で）探し続けます。そして 確率 と ランダム性 （ 重み付けされた確率 ）に基づいて決断を下します。これを length 回行うまで何度も繰り返します????

参考資料、提案と考察????

1. 応用

マルコフモデルの典型的な例には、天気予報や証券取引、ツイートの生成に基づいた人々の行動があります！???? マルコフモデル に基づいた 新規コンテンツ を作成し、 生成する ために、どのように コーパス を活用することができるか考えてみてください。また、どういった変化があるでしょう？
ヒント：マルコフモデルがどういうもので、なぜそれが必要なのか、そしてどのようにそれが機能し、作成されるのかをしっかりと理解できていれば、大きな変化がないことは分かるでしょう。 唯一、違い があるとすれば、 マルコフモデルをどのように解析するか という点と、 一意の制限 を加えるかどうかです。

例えば、私の粋な シリコンバレー・ツイート・ジェネレータ では、大きなウィンドウを使用し、生成されるコンテンツを140文字までと制限しました。不定量の文が存在する可能性があったので、文の “シード” を設定するために既存の文の最初のウィンドウだけを使用しました????

2. 参考資料

マルコフモデルがどういうものであるかについてよく理解できたと思いますので、次は、隠れマルコフモデルについて理解を深めてみるといいでしょう。今回新しく学んだ知識を使って何かを作成したいと考えているのであれば、マルコフモデルを使ったHBOシリコンバレー・ツイート・ジェネレータの構築に関する私の記事を読んでみてください（近日中に投稿予定）！

3. まとめ

私は常にフィードバックをお待ちしていますので、この記事の構成や内容、取り上げた例、その他何でもいいので、皆さんの考えを共有してください????　マルコフモデルは素晴らしいツールですし、このモデルを使って何か構築してみることをお勧めします。独自のツイート・ジェネレータを構築してみるのもいいですね????　それでは！????

この記事を気に入っていただけたようであれば、以下に表示されている????をクリックしてください。Mediumに登録している方にも閲覧していただくことが可能になります。

訳注:元記事へのフィードバックは、 元記事 から行ってください。