マルコフモデル ~概要から原理まで~ (後編)

本記事は、元記事を翻訳した記事の後編となります。
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に登録している方にも閲覧していただくことが可能になります。

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