I read this insightful IPython notebook post by yogo, about very simple n-gram models that estimates the probability distribution the next character of a text sequence given the n preceding characters.  It does this by just constructing a histogram from reading in lots of data, nothing magical!

The text generating RNN demo is also doing the same thing, constantly estimating the probability distribution of the next character in a sequence, but due to the recurrent nature, the n can be of infinite length, meaning that an RNN may remember context from the very beginning of the training text.

It is interesting to apply yogo’s very simple n-gram model to the full text of The Tale of Genji (源氏物語), and train an 4-gram model to generate Genji-like stories.

I modified yogo’s very elegant IPython notebook a bit, so it works with unicode (utf-8) encoding, and made minor modifications with how it generates text randomly.  I’m constantly amazed at the compactness and readability of small python scripts that can do a lot.

# below is based off Yoav Goldberg's post
# http://nbviewer.ipython.org/gist/yoavg/d76121dfde2618422139

from collections import *
import codecs
import random

def train_char_lm(fname, order=4):
f = codecs.open(fname, encoding='utf-8')
lm = defaultdict(Counter)
pad = " " * order
for i in xrange(len(data)-order):
history, char = data[i:i+order], data[i+order]
lm[history][char]+=1
def normalize(counter):
s = float(sum(counter.values()))
return [(c,cnt/s) for c,cnt in counter.iteritems()]
outlm = {hist:normalize(chars) for hist, chars in lm.iteritems()}
return outlm

def generate_letter(lm, history, order):
history = history[-order:]
dist = lm[history]
x = random.random()
for c,v in dist:
x = x - v
if x <= 0: return c

def generate_text(lm, order, nletters=1000):
history = random.choice(lm.keys())
out = []
for i in xrange(nletters):
c = generate_letter(lm, history, order)
history = history[-order:] + c
out.append(c)
return "".join(out)

I trained the 4-gram model on the full text (the version with Kanji, not simplified down to hiragana) using this command:

lm = train_char_lm(‘genji.orig.txt’, order=4)

This only took around ten seconds on a macbook!  Let’s see if we can generate some Genji:

print generate_text(lm, 4)

The resulting text generated from the 4-gram model:

その夜、主上の御ためこそ、いとほしき御声なり。
「知らぬを、なかなかなるを見たらむやうなりける心のほどを、苦しき下燃えなりけり。退きて咎なしとこそ、いといとほしう、わづらはしければ、嘆かれたまふ。いと心やすかべかめれ。それだに心やすくて、ながらふるなりけむかし」
など言ふ。

などのたまふは、故大将殿には、御手水参り、御遊び絶えず。
[第一段　横川僧都の母、初瀬詣での帰途に急病]
そら消息をつきづきしく今めきたまふ。東の姫君も、さやうのことは、ともかくもいらへやらずなりにけり。あてなる方の、御しるべにて、かやうになりゆく。

「なほ、世に亡くなりたまふ。
「折悪しく参り、朝廷に数まへられぬべきによりなむ、わづらはしきこゆ。妻戸にもろともに育まぬおぼつかなう思ひきこえたまふものしたまへば、
「恥ぢがてら、雪をうち払ひしつらはれたり。

I guess it doesn’t look that bad.  We see parts of the text that are exact text duplicates from the original text, for example “第一段　横川僧都の母、初瀬詣での帰途に急病” is exactly the same as the original with no modifications.  That is one problem with doing this exercise with Kanji training text, as there is not enough data or variations, so to the model there is only one possibility to generate the next character after “第一段”, and so on.  If we train the model on the entire Japanese wikipedia we may see different results.  Another issue is that the n-gram will not be able to learn deeper structures in the next, such as the the need to close a bracket 「」.  RNNs have demonstrated the ability to do this which I want to test later.

I have rerun the demo on the pure hiragana training data as well to see what we get:

だつることぞよ」
など、つれなくて、こころにくきおんみに、さるべきことに、おつつしみせさせたまふに、こうしのげきなういでいりに、
「くもいのあはれなるおけしきにてゐたなるを、そのおりはしも、こころにつけたることかぎりなしとおもひきこえたまひつ。だれれもだれも、いとなませたまへれど、こうしもふきほうっちたりしにおひくははりて、いみじとおもいたり。われひとりさえつるへんしきの
ねんふるあまもきょうやびきつる」
「よろづのことおぼしたるぞ、ぞうきこころのおになりやしなまし、とおもひてしおもねたらむよ」と、いとこころぐるしくいとどしづまりたるねんにて、ねんのつもりを、さすがに、ひろくおもひかくるには、すきぬべかめるを、さはやかなれ。かかるおなかをそむきたまひしを、かやうにおもう]
このおいとなみつつ、ここのにたがへきこえたまふを、ちゅうじょうせんうまありて、さしいでたまへるもらうたげに、けそうなきおこころにてきこえなしたまへば、おおみやもそこはかとなくあくがれたまふを、いますこしなのめなることにしたがひておぼしたちてなどはあらぬけはひ、はづかしければ、つひにききあはせを、いとどかかることのついでにもやとつつましけれ。あやしくもある。おなじほどにおはすなる。
「よくもたまくしすにまつはれたてまつりたまへど、あやしく、なやみたまふおうじょのきんきのこいものがたり
だいさんだん　ちゅうなごんにしょうそくどもきこゆれば、かごかなるならひにたれば、いとわりなし」とみたまふ。あるやうありける」と、かつはうちなきつつかえりたつ]
にじょういんのなどは、なほ、かのろくじょういんへさんけい]
おこりやまじなひわづらひぬる」
など、おんなくんも、だいどのにきこゆ。
「おおせられたり。
きたかきいえのよも、とりあつめたることなどをおもひいでたまひて、にしのおんかたにまいりたまひて、「つねなきものにて、いたくなげかしげによういしてさぶらふ。おわたりのことならねば、おがのひびきも、なみだおしのごひかくして、うちやすらむ。うらみたまふるを、いかがなりたまひなむや。れいのやうにはべれど、おのがどちのこころむけこそそひにけり。おどきなどは、ましてこころぼそくて、いとらうたげにて、うちなげきて、
「これはまばゆくととのへさせたまふほどぞ、ふとおどろくことおおかるを、はかなきこと

The version trained on hiragana can lead to more interesting variations of generated text compared to the version trained on Kanji+hiragana.  This is basically similar to training on english words, or training to english characters, and we know training on full word vectors will lead to such lack-of-diversity issues if there isn’t enough training data.  This may be a good benchmark for RNNs to see what the incremental improvements may be compared to the simple histogram-building n-gram model.

### Citation

If you find this work useful, please cite it as:

 @article{ha2015genji,   title   = "N-Gramming the Tale of Genji",   author  = "Ha, David",   journal = "blog.otoro.net",   year    = "2015",   url     = "http://blog.otoro.net/2015/05/27/n-gramming-the-tale-of-genji/" }