豪鬼メモ

一瞬千撃

Wikipediaを解析して共起語抽出をしよう

DBMで単語辞書を作る連載の2回目だ。今回作る辞書検索システムの看板機能は、類語検索である。そして、類語を自動的に推定するための一手法として、共起語を使う方法がある。ここでは、Wikipediaコーパスとして、共起語を抽出する。

解析結果

先に結論から書く。Wikipediaの英語版と日本語版をそれぞれ解析して、各単語について主要共起語のデータベースを作った。その過程及び結果として以下のデータが得られた。

これらを作るための実装について考察する。ここで抽出したWikipediaコーパスは英語版で880万文書、日本語版で160万文書くらいある巨大なものだ。各記事で60文くらいを読むので、英語版で5.6億文、日本語版で1億文を解析する。1文の単語数は20語くらいなので、英語版で112億語、日本語版で20億語を対象とした共起語抽出を行うことになる。なかなかの規模だが、ノートPCを1台だけ使って解析を行った。PythonとDBMライブラリを駆使すれば短いプログラムでそれができる。

なお、Wikipedia英語版に含まれる英文における各単語の出現率は以下のものである。「the」は42%の文で1回以上出現するということだ。上位語を見る限り、現代英語の最頻英単語リストとそんなに解離していない。説明的な文が多いのでやたら定冠詞や代名詞や接続詞が多いのかと思っていたが、そうでもないようだ。

the .42131538
of .27894917
in .25715088
and .24588148
a .20404020
to .18763389
is .12326909
was .11799351
on .09638384
for .09497908
as .09386162
by .07527513
with .07093599
it .06127755
at .05979451
he .05949171
that .05764467
from .05510457
this .05457562
an .05211625

動機

わざわざ共起語のデータベースを作るのは、辞書検索システムで類語検索機能を実装するためである。ここで「類義語」でなく「類語」と書いたのは意図的である。語義が似ている語を探すのではなく、用法やコンテキストが似ている語を探しているからだ。関連語と言い換えてもよく、それには対義語や上位語や下位語なども含む。ちなみに、「シソーラス」というと、関連語のことではなく、関連語をまとめた辞書のことを指す。よって、「hogeシソーラスを調べる」といった用法は誤りであり、「シソーラスhoge について調べる」が正しい。今回はそのシソーラスを自動的に作るために共起語抽出を行う。

話は少しずれるが、昔、某SNSの会社にいたときに、マイミクのレコメンドシステムの開発に関わったことがある(設計実装したのは私ではないが)。直接のマイミクでなくても共通のマイミクが多いユーザは実際には面識がある可能性が高いという経験則に基づいて推薦を行う仕組みだ。マイミクのマイミクは潜在的マイミクである。その際に、多くのマイミクを持つハブ的なユーザだけがやたら推薦されると使いにくいので、共通のマイミクの数を見るだけではなく、候補のユーザに至る経路の重要性が反映されるアルゴリズムを使って最終的なランキングを生成していた。Facebookの友人推薦機能とかもおそらく同じようなアルゴリズムだろう。

共起語による類語推定も友人推薦機能と同じように考えるとわかりやすいかもしれない。共起語の共起語は類語である可能性が高い。例えば「soccer」という語は「play」「watch」「ball」「score」「win」といった語と一緒に使われる傾向があるが、この傾向は同義語である「football」とかなり類似するはずだし、類語である「baseball」や「tennis」も似たような傾向を持つだろう。なので、全ての英単語について共起語の頻度を数えてベクトル表現を作り、その類似度が高いものを類語とみなすのは合理的だ。実際には全ての英単語のペアを比較するのは現実的ではないし、全ての共起語を数えるのも現実的ではないので、うまいこと足切りをした簡便法を実装することになる。また、友人推薦システムでハブ的なユーザにペナルティを与えていたように、共起語でも「a」「the」「is」などの頻出語にはペナルティを与えることが望ましい。いわゆるTF-IDF法に近い考え方だ。

f:id:fridaynight:20200804133436p:plain:w450

基本構造

類語の推定アルゴリズムについてはまた別の記事で書くとして、今回は共起語を抽出する実装に焦点を当てよう。まず、入力データだが、Wikipediaのデータベースダンプデータを用いる。各言語のWikiepdiaの全記事とそのメタデータが巨大なXMLファイルにまとめらている。英語版だと18GB、日本語版だと3GBほどだ。これを加工して、共起語データベースを作る。

作業環境には私のノートPCを使う。搭載メモリは16GBであり、そのうち10GBほどを作業メモリとして用いる。大きめのコーパスの分析をするならクラウド環境を借りるなりしてApache HadoopとかのMapReduce的な分散処理システムを使った方が楽なのだが、今回は敢えて単体のマシンで行う。うまいことデータを分割して逐次処理を行えば、狭い作業空間でも巨大データの集計処理を行うことができる。DBMがそのためにも有用であることを示したい。たとえ作業メモリが1GBでも、チューニングを変えれば実行可能だ。貧しき者は幸いなり。DBMはその人達の物である。

実装言語にはPythonを使う。以下のプログラムを開発して順に実行することで目的を達する。実際のコードはGitHubに置いておく。

  • count_wikipedia.py
    • 標準入力からWikipediaXMLデータを読み込む。
    • XMLデータを解析し、生テキストが抽出できる記事の数を数える。
    • 結果の記事数を標準出力する。
  • parse_wikipedia.py
    • 標準入力からWikipediaXMLデータを読み込む。
    • 引数でサンプリングの採用率を指定できる。
    • XMLデータを解析し、各記事の生テキストを抽出する。
    • 処理結果は段落をタブで区切ったTSVデータとして標準出力する。
  • tokenize_text.py
    • 標準出力から行区切りのTSVデータを読み込む。
    • 引数で言語コード("en" か "ja")を受け取る
    • 引数で各記事から採用する文の最大数を指定できる。
    • 各記事各セクションの生テキストを文のリストに分割し、さらに各々の文を単語のリストに分割する。
    • 各文はタブで区切られ、単語は空白文字で区切られたTSVデータを生成し、標準出力する。
  • count_cooccurrences.py
    • 標準入力から文書毎のTSVを読み込む。
    • 出現した単語の文単位の出現数を記録したDBMファイルを作成する。
    • 出現した単語とその共起語のペアの文単位の出現数を記録したDBMファイルを作成する。
  • divide_cooccurrences.py
    • 単語の出現数と共起語の出現数のDBMファイルを読み込む。
    • 単語の出現数を出現率に変換する。
    • 共起語を片方の単語でまとめ、単語毎に最大256語を抽出し、出現率とともに記録する。

count_wikipedia.py はサンプリングの採用率を決めるために単独で実行する。中間の三つのプログラムはパイプで繋げて実行できる。こうすると各々のステージが文字通りパイプライン化されて並列実行されるので、時間短縮になる。

$ bzcat enwiki-20200701-pages-articles-multistream.xml.bz2 |
  ./count_wikipedia.py
$ bzcat enwiki-20200701-pages-articles-multistream.xml.bz2 |
  ./parse_wikipedia.py 0.1 |
  ./tokenize_text.py en 100 |
  ./count_cooccurrences.py enwiki en
$ ./divide_cooccurrences.py enwiki en

とはいえ、今回は記事単位のサンプリングは行わなかった。固有名詞の類語を取得するという観点でもWikipediaは優れたコーパスだが、記事を丸ごとを読み飛ばすと、採用された記事の固有名詞と採用されなかった固有名詞の差が大きくなりすぎるからだ。その代わり、各記事の中から冒頭の64文だけを読み込むというサンプリングは行なった。また、個々のステージの結果を一時ファイルに保存して、結果を確かめながら作業を進めた。途中の結果が確かめられるので、少なくとも開発中はこちらの方法が適切だ。下の例では作業結果をいちいちBZIP2で圧縮しているが、そうしなくてももちろん大丈夫だ。

$ bzcat enwiki-20200701-pages-articles-multistream.xml.bz2 |
  ./parse_wikipedia.py | bzip2 -c > enwiki-raw.tsv.bz2
$ bzcat enwiki-raw.tsv.bz2 |
  ./tokenize_text.py en 100 | bzip2 -c > enwiki-tokenized-100.tsv.bz2
$ bzcat enwiki-tokenized-100.tsv.bz2 |
  ./count_cooccurrences.py enwiki en
$ ./divide_cooccurrences.py enwiki en

XMLの解析

XMLパーザを使ってWikipediaXMLデータを解析することを考える。いきなり大きいプログラムを書く前に、まずはXMLデータ全体をスキャンして、記事の数を数える count_wikipedia.py というプログラムを書くことにする。XMLの解析には、SAXパーザを用いる必要がある。DOMパーザだとメモリに乗り切らないからだ。

import logging
import sys
import xml.sax
import xml.sax.handler

log_format = "%(levelname)s\t%(message)s"
logging.basicConfig(format=log_format, stream=sys.stderr)
logger = logging.getLogger("enwiki_wordcount")
logger.setLevel(logging.INFO)

class XMLHandler(xml.sax.handler.ContentHandler):
  def __init__(self):
    self.count = 0
    self.tags = []
    self.is_redirect = False
    self.model = None
    self.format = None
    
  def startDocument(self):
    logger.info("Start the document")

  def endDocument(self):
    logger.info("End the document")

  def startElement(self, name, attrs):
    self.tags.append(name)
    if self.tags == ['mediawiki', 'page']:
      self.is_redirect = False
      self.has_restrictions = False
    if self.tags == ['mediawiki', 'page', 'redirect']:
      self.is_redirect = True
    if self.tags == ['mediawiki', 'page', 'restrictions']:
      self.has_restrictions = True
    if self.tags == ['mediawiki', 'page', 'revision', 'model']:
      self.model = ""
    if self.tags == ['mediawiki', 'page', 'revision', 'format']:
      self.format = ""

  def endElement(self, name):
    if self.tags == ['mediawiki', 'page', 'revision']:
      if (not self.is_redirect and not self.has_restrictions and
          self.model == 'wikitext' and self.format == 'text/x-wiki'):
        self.count += 1
        if self.count % 1000 == 0:
          logger.info("Progress: {}".format(self.count))
      self.model = None
      self.format = None
    self.tags.pop()

  def characters(self, content):
    if self.tags == ['mediawiki', 'page', 'revision', 'model']:
      self.model += content
    if self.tags == ['mediawiki', 'page', 'revision', 'format']:
      self.format += content

  def getCount(self):
    return self.count

def main():
  logger.info("Process started")
  parser = xml.sax.make_parser()
  handler = XMLHandler()
  parser.setContentHandler(handler)
  parser.parse(sys.stdin)
  print(handler.getCount(), flush=True)
  logger.info("Process done")

if __name__=="__main__":
  main()

このプログラムも標準入力からXMLを受け取って処理を行う。階層化されたタグの構造を調べるには、スタックとみなすリストを持ち、開始タグのハンドラで末尾にタグ名を加え、終了タグのハンドラで末尾のタグ名を除去する実装が確実だ。各記事の本文は、XPathで言うところの/mediawiki/page/revision/textの子要素のテキストデータであるが、ここではそれは見ない。代わりに、/mediawiki/page/revision要素の終了タグの個数を数えている。その際に、/mediawiki/page/redirectが含まれていないことを確認している。それが含まれている記事は、単なるリダイレクトだからだ。/mediawiki/page/restrictonsが含まれていないことも確認している。それが含まれている記事は編集者用のメモだからだ。さらに、/mediawiki/page/modelの子要素の値が "wikitext" で、/mediawiki/page/formatの値が "text/x-wiki" であることも確認している。後で書くプログラムがその形式を前提としているから、非互換のものは数えないようにする。

20200701のダンプデータの英語版Wikipediaの解析対象記事数は880万ほどで、日本語版では160万ほどである。確認することが大事だ。Wikipediaに書いてある「純記事数」よりもかなり少ないのだが、MediaWiki形式以外の記事を無視しているのが主な原因だろう。既に述べたが、今回は記事単位のサンプリングは行わない。しかし、もし記事単位のサンプリングを行うならば、各入力レコードの採用確率を決めるために入力レコード数を知っておく必要がある。XMLデータ内の記事はタイトルの辞書順で並んでいるため、データの先頭部分だけ採用するという方法だとひどい偏りが生じる。全体から満遍なくサンプルを拾うには確率的な方法を用いることなるが、その確率設定をサンプリングと同時に行うreservoir samplingはここでは使えない。reservoir samplingでは最終的に採用されるかもしれない候補をメモリ上に載せておくのが前提なので、実メモリに収まらない規模のサンプル数を扱うのが簡単ではない。現在のサンプル候補をDBMとして退避しておくということも考えられるが、そうするとランダムアクセスが発生するので遅くなる。だったら先に全体をスキャンして全体の件数を数えておいてから一律のサンプリング率を設定した方が効率的だ。

XMLから記事の本文を抽出

parse_wikipedia.py の実装について考える。基本的な構造は count_wikipedia.py と同じだ。SAXパーザが文字列データを読み込んだ際には、charactersというメソッドをコールバックするが、文字列が長い場合にはcharactersは適当なチャンクに分割して呼ばれることに注意だ。なので、文字列を解析する場合には、開始要素でバッファを空にして、charactersハンドラでは受け取った内容をバッファの末尾に連結し、終了要素でバッファの内容を一気に処理すると良い。記事のテキストデータに含まれるMediaWiki形式のデータの解析には、ガチなパーザを呼ぶのが面倒なので、それっぽい正規表現を並べてお茶を濁している。共起語の統計値を取りたいだけなんで多少の漏れがあっても問題はないだろう。このステージは言語非依存であるべきなので文の分割は行わないが、段落の区切りは保存する必要があるので、それをタブで表現したTSVとして結果を出力する。

文を単語のリストに分解

tokenize_text.py の実装について考える。入力の各行のTSVデータにおいて各列は複数の文を含むセクションである。各言語用の関数にデータを渡して文区切りと単語の分かち書きを同時に行わせる。現状では言語は英語と日本語のみに対応している。文区切りの実装は、英語でも日本語でも、以下のような関数でだいたいうまくいく。すなわち、ピリオドの後に空白が来て、その後にラテン文字の大文字が来た場合には、文区切りとする。しかし、その場合に「Mr. Smith」や「U. S. A.」のピリオドで文が切れてしまうのは困るので、泥臭いルールを書いて防御している。それにしても、「.」を文末記号と省略記号と小数点に兼用するという決断をした輩が呪わしい。

def SplitSentences(text):
  text = regex.sub(r'(^|\W)(Mr\.|Mrs\.|Dr\.|Prof\.|Esq\.)', r'\1\2{_XxX_}', text)
  text = regex.sub(r'(^|\W)(e\.g\.|eg\.|i\.e\.|ie\.|p\.s\.|ps\.)',
                   r'\1\2{_XxX_}', text, flags=regex.IGNORECASE)
  text = regex.sub(r'(^|\W)(\p{Lu}\.) *(\p{Lu}\.) *(\p{Lu}\.)', r'\1\2\3\4', text)
  text = regex.sub(r'(^|\W)(\p{Lu}\.) *(\p{Lu}\.)', r'\1\2\3', text)
  text = regex.sub(r'([.?!]) +([\"\p{Lu}\p{Lo}])', '\\1\n\\2', text)
  text = regex.sub(r'{_XxX_}', '', text)
  text = regex.sub('。', '。\n', text)
  sentences = []
  for sentence in text.split('\n'):
    sentence = sentence.strip()
    if sentence:
      sentences.append(sentence)
  return sentences

文を抽出した後に、文字列を正規化する。大文字は小文字に統一し、ラテン文字につくダイアクリティカルマーク(発音区別符号)は削除する。「NIÑO」は「nino」に、「Résumé」は「resume」に、「Tōkyū」は「tokyu」する。以下のような関数でだいたいうまくいく。UnicodeのNFD正規化で主要文字と結合文字を分離した後、ラテン文字の後ろの結合文字を削除してから、最後にNFC正規化を行う。日本語の濁点や半濁点も結合文字なので、直前の非結合文字がラテン文字かどうかを調べるのが必要になる。小文字にする処理は単にstringクラスのlowerメソッドを呼べば良い。

def RemoveDiacritic(text):
  decomposed = unicodedata.normalize('NFD', text)
  stripped = ""
  removable = True
  for c in decomposed:
    if unicodedata.combining(c) == 0:
      removable = bool(regex.match(r"\p{Latin}", c))
      stripped += c
    elif not removable:
      stripped += c
  return unicodedata.normalize('NFC', stripped)

さらに、以下のアドホック気味な正規化も行う。「u.s.a.」等のピリオド付きの略語が後で文字単位になってしまうと情報量がほとんどなくなってしまうので、「usa」としてまとめてしまう。括弧や句読点やその他の記号は空白に置換する。ここでP(Punctuation)クラス全体を指定しないのは、ハイフンやアポストロフィが置換されるとまずいからだ。さらに、中黒をLatin Middle Dotに置換する。中黒はUnicodeとしてはKatakana Middle Dotであり、片仮名の一種だ。片仮名の連続を一語として扱う傾向があるMecabが中黒で片仮名語を切ってくれないことに対する対処として、中黒を片仮名扱いではない文字に置換する必要がある。

def NormalizeWords(text):
  text = regex.sub(r"(^|\W)(\p{Ll})\.(\p{Ll})\.(\p{Ll})\.(\p{Ll})\.", r"\1\2\3\4\5", text)
  text = regex.sub(r"(^|\W)(\p{Ll})\.(\p{Ll})\.(\p{Ll})\.", r"\1\2\3\4", text)
  text = regex.sub(r"(^|\W)(\p{Ll})\.(\p{Ll})\.", r"\1\2\3", text)
  text = regex.sub(r"[\p{Ps}\p{Pd}\p{Pi}\p{Pf}\p{S}]", " ", text)
  text = text.replace("\u30FB", "\u00B7")
  return text

英語の単語抽出に関しては以下のような関数でだいたいうまくいく。すなわち、ラテン文字で始まり、ハイフンかアンダースコアか省略符かラテン文字か数字が連続する文字列を単語とみなす。この時点で英単語に関係ない記号や数字などの情報は全て捨てられる。「co2」とか「R2-D2」とかの数字付きの単語は認める。

def GetWordsEn(sentence):
  words = []
  for word in regex.findall(r"[\p{Latin}]+[-_'\p{Latin}0-9]*", sentence):
    words.append(word)
  return words

日本語の単語抽出に関しては、Mecabを呼んで分かち書きをさせた上で、仮名か漢字か英字からなる文字列を単語とみなす。この時点で日本語の単語に関係ない文字の情報は捨てられる。英字の単語も拾っているのは、「Linux」などの英字の固有名詞も共起語として意味があるからだ。なお、Mecabは異なる字種の文字列の間を単語区切りとみなす。したがって、「CO2」を一語として取るためには、「CO」と「2」が連続していることを検出する必要があり、単に「-Owakati」を呼ぶのより複雑な処理が必要となる。

tagger = MeCab.Tagger(r"--node-format=%m\t%ps\t%pe\n")
def GetWordsJa(sentence):
  words = []
  last_word = None
  last_end = -1
  for token in tagger.parse(sentence).split("\n"):
    fields = token.split("\t")
    if len(fields) != 3: continue
    word = fields[0]
    begin = int(fields[1])
    end = int(fields[2])
    if (last_word and begin == last_end and
        regex.search(r"[-_'\p{Latin}0-9]$", last_word) and
        regex.search(r"^[-_'\p{Latin}0-9]", word)):
      last_word += word
    else:
      if last_word:
        words.append(last_word)
      last_word = word
    last_end = end
  if last_word:
    words.append(word)
  good_words = []
  for word in words:
    if (regex.search(r"[\p{Katakana}\p{Hiragana}ー\p{Han}]+", word) or
        regex.search(r"[\p{Latin}]+[-_'\p{Latin}0-9]*", word)):
      good_words.append(word)
  return good_words

tokenize_text.py は文を区切った後に先頭のいくつかを残して残りを捨てる機能を持たせる。Wikipediaの記事は長さのばらつきが大きく、やたら長い記事から多くの文を取り込むと結果が偏ることが考えられる。各記事から先頭50文くらいを取れば十分だろう。今回は先頭64文を取ることにする。なお、正規表現には標準のreモジュールではなく、現在のところ非標準のregexモジュールを使っている。これは\pで始まるUnicodeクラスを使いたいからだ。

ここまでの処理で、Wikipediaに依存した部分と自然言語に依存した部分は終わりだ。TSVの中に分かち書き済みのテキストを入れたデータを用意すれば、ここから先の後半ステージを再利用することができる。逆に、ここまでの前半ステージを再利用してWikipadiaデータを対象とした別の統計処理や言語処理を行うのも一興だ。

単語と共起語の集計

さて、ここからが面白い。集計の世界、データベースの世界だ。count_cooccurrences.py の実装について考察する。共起語抽出は組み合わせ問題なので、恐ろしい量のデータを扱うことになる。例えば「I live in Meguro, Tokyo.」という文からは "i", "live", "in", "meguro", "tokyo" という5つの単語が取得できる。同じ文に現れた2つの語の組み合わせを語を共起語とみなすと、5*4 = 20個の事象が観測されることになる。100単語の文があれば100*99 = 9900個の事象が観測される。理想的にはそれらを全て集計したい。しかし、さすがにそれは無理なので、適当な簡便法を編み出さねばならない。今回は以下の方針でいくことにする。

  • スライドウィンドウ: 出現した各単語に対して、前後20単語までを共起とみなす。
  • ディケイスコアリング: 共起したかしないかのバイナリでなく、隣を1とし、1語離れる毎にスコアを0.95倍した数値を合算する。
  • ソフトセンテンス: 文区切りの判定が信用できないし、文を跨った情報も拾いたいので、文区切りを跨った語もスコアを0.5倍させて拾う。

こうすると、出現した各単語についてだいたい40個の共起語を安定的に拾うことになる。文の長さに左右されないことが重要だ。しかし、それでも各語で40個のデータを生成するのは厳しい。平均20語からなる100万文を読んだら8億レコードになってしまう。もちろん、集計処理なので、語の組み合わせが同じレコードは結合してカウントアップしていくことで8億レコードよりは減るのだが、いわゆるロングテールな低頻度の組み合わせが多くの空間を使ってしまう。それらをうまいことオンラインで足切りしつつ、限られた作業メモリとDBMファイルだけで集計するのが腕の見せ所だ。基本的な技術課題は以前、「DBMを使った検索エンジンの作り方」で述べたものと共通している。

このプログラムは、改行で区切られた文書毎のタブで区切られた文毎のスペースで区切られた単語のリストを受け取り、4種類のデータベースを生成する。

  • 単語頻度データベース: 各単語とそれが出現した頻度
    • SkipDBMクラスのDBMファイル
    • キーは単語の文字列
      • 例外的に、空文字列のキーを文の数を表すのに使う。
    • 値はその単語が出現した頻度
    • e.g.: ("the", "1234567"), ("a", "654321"), ("is", "345678")
  • 共起頻度頻度データベース: 共起語のペアとそれが出現した頻度
    • SkipDBMクラスのDBMファイル
    • キーは二つの単語を空白で区切って並べた文字列
      • 例外的に、空文字列のキーを文の数を表すのに使う。
    • 値はその単語のペアが同じ文に出現した頻度
    • e.g.: ("the a", "87671"), ("the is", "13521"), ("a the", "67521")
  • 単語確率データベース: 各単語の文単位の出現確率
    • HashDBMクラスのDBMファイル
    • キーは単語の文字列。
    • 値はその単語が文に出現する確率
    • e.g.: ("the", "0.4657"), ("a", "0.3241"), ("is", "0.1234")
  • 共起語確率データベース: 各単語とその代表的な共起語とその確率のリスト
    • HashDBMクラスのDBMファイル
    • キーは単語の文字列
    • 値は、その単語と共起しやすい語とその共起確率を空白で区切ったペアのタブ区切りのリスト
      • ここで言う共起確率は、キーとなる単語が現れた場合の共起語のウィンドウ内の出現確率である
    • e.g.: ("a", "the 0.2823\tis 0.1523"), ("the", "a 0.2123\tis 0.2079")

手順としては、まずは単語頻度データベースと共起語頻度データベースを構築してから、それらを変換して単語確率データベースと共起語確率データベースを構築する。単語頻度データベースを作るには、各文における単語の出現を最大1回として数えてデータベースに記録する。全ての単語を収録するとデータベースが大きくなりすぎるため、一定の頻度を下回るものは捨てる。その後、各レコードの値を文の数で割れば、単語確率データベースができあがる。同様に、共起語頻度データベースは各文における共起語のペアの出現を最大1回として数えてデータベースに記録する。全ての共起語のペアを収録するとデータベースが大きくなりすぎるため、一定の頻度を下回るものは捨てる。その後、ペアの片方の語をキーにしてレコードを結合し、元々の値をリストとして表現してから、元々の頻度をキーの単語の出現数で割ると、共起語確率データベースができあがる。なお、多くの語の出現確率は非常に低いので、確率を記録するにはIDFと同様に対数の絶対値に変換してから1000倍とかした整数を記録記録した方が空間効率が良い。しかし、それはメンテナンス性が劣るので、現状では率直に10進小数で表現する。

ここで、MapReduceでワードカウントを行うことを考える。Mapプロセスでは分かち書きされた単語のリストを受け取り、個々の語の出現の観測する度に、その語の文字列がキーで、"1" という値を持つレコードを出力する。共起語を扱う場合は語の組み合わせのペアを繋げた文字列がキーで、"1" という文字列を値を持つレコードを出力する。そして、基盤システムは、Shuffleプロセスとして、同じキーのレコード群をまとめてから、同一キーのレコード群毎にReduceプロセスを呼び出す。そこでは値を合算した値を "325" などの文字列として出力する。このような、頻度を数える処理の場合、全体のシャッフルを行う前に、途中経過の部分集合でShuffleとReduceを行った上で、その出力に対して最終的なShuffleとReduceを行っても結果は同じになる。この途中に呼ばれるReduceはCombineプロセスと呼ばれる。Hadoopのこの資料とかを読むとわかりやすい。

Mini-Batch 1:
Map("I love you")  -> ("i", "1"), ("love", "1"), ("you", "1")
Map("You love me") -> ("you", "1"), ("love", "1"), ("me", "1")
  -> Combine(
        ("i", "1"), ("love", "1"), ("you", "1"),
        ("you", "1"), ("love", "1"), ("me", "1"))
     -> ("i", "1"), ("love", "2"), ("you", "2"), ("me", "1")

Mini-Batch 2:
Map("You hit me")  -> ("you", "1"), ("hit", "1"), ("me", "1")
Map("I hit you") -> ("i", "1"), ("hit", "1"), ("you", "1")
  -> Combine(
        ("you", "1"), ("hit", "1"), ("me", "1"),
        ("i", "1"), ("hit", "1"), ("you", "1"))
     -> ("you", "2"), ("hit", "2"), ("me", "1"), ("i", "1")
 
Final Reduce:
Reduce(
  ("i", "1"), ("love", "2"), ("you", "2"), ("me", "1"),
  ("you", "2"), ("hit", "2"), ("me", "1"), ("i", "1"))
  -> ("i", "2"), ("love", "2"), ("you", "4"), ("me", "2"), ("hit", "2")

今回行うのは分散処理ではないが、似たような考え方で問題を分割できる。まず、全体の入力を、一定数の入力レコード毎にミニバッチに分割して扱う。各々のミニバッチでは、語や共起語の出現はオンメモリのデータベースを使ってその場で集計する。そのオンメモリのデータベースには、TkrzwのBabyDBMクラスを用いる。これはB+木をオンメモリで実装したものである。

一定数の文を読み込んでミニバッチの処理が終了する際には、オンメモリデータベース内のレコードをファイルに吐き出す。出力ファイルはTkrzwのSkipDBMである。これはスキップリストのデータベースであり、Google MapReduceApache HadoopがSSTableファイルを書き出すの全く同じ要領だ。レコードがキーの順序でソートされているのが要件であり、そのことが後でマージソートを行うのに必要となる。ところで、全ての語または共起語についてレコードを出力すると、頻度が1や2しかないロングテールなレコード群によって空間効率が悪化してしまう。ロングテールなレコードは最終的な出力では上位に残らずに捨てられてしまう可能性が高いので、それらを出力する意味はない。ということで、一定数以下の頻度のレコードを無視するカットオフという処理をするのが一般的だ。ミニバッチのサイズが十分に大きい場合、カットオフはそれに応じて5とか10とかの強気の設定にしても実用上の問題はない。さらに、ミニバッチの途中に3回のミニミニカットオフを行い、最終的な閾値の4分の1以下のレコードを消すことで、メモリ使用量を節約する。今回はカットオフの値は、単語で16、共起語で4を設定している。

読み込んだ語が1000万語に到達していたら、現在のミニバッチを終了させる。1000万語だとだいたい8GBくらいのメモリを消費し、だいたい15万文書(610万文)を読み込んでいる。もし、メモリ使用量を1GBに抑えたいなら、45万語くらいをミニバッチのサイズに指定すると良い。なお、ミニバッチのサイズが大きいほど、ミニバッチ間に分散されて出現する低頻度語が捨てられるリスクが低減する。全体の処理にかかる時間はミニバッチのサイズにはあまり関係ない。ミニバッチが直列に実行されるからであり、ミニバッチのデータをマージする処理は全体のレコード数に律速されるからだ。

個々の語に対しては絶対的な頻度でカットオフを行うので良いのだが、共起語に対しては順位でもカットオフを行うとさらに効率的だ。「a」や「the」の共起語はどれも高い頻度になってしまうが、その全てを保持するのは無駄だ。したがって、個々の語に対して上位256語の共起語のみを出力する。ミニバッチの結果を統合していくに従って共起語の異なり語は256語よりも増えていくことにはなるが、最終的な出力の際にまた上位256語に絞り込む。ミニバッチ化をした上で、絶対的な頻度と順位の双方でカットオフを行うことによって、精度をほとんど落とさずにロングテールの問題が緩和できる。

ミニバッチ毎に用いるオンメモリデータベースが順序付きのB+木であるBabyDBMであるのには理由が三つある。一つ目は、メモリの使用量が少ないことである。std::mapに比べてメモリ使用量が半分くらいになる。二つ目は、キーが辞書順に並んでいるので、イテレータを回すだけでペアの片方の語を基準にReduce処理ができることである。三つ目は、キーが辞書順に並んでいるので、そのままの順序で出力すればSkipDBMのinsert_in_orderモードを使って効率的にデータベースの構築ができることである。

個々の語の共起語の上位を頻度だけで考えると、「a」「the」「is」などの頻出語に多くを占められてしまい、特徴的な共起語が残らない。そこで、上位の共起語を選択する際には、ミニバッチ内での各語の出現頻度を使ってIDFを算出した上で、それで重み付けしたスコアをもとにソートを行う。今回は普通のIDFよりもさらに強力な補正をかけたいので、IDFの1.5乗を重み付けに使っている。1乗だと機能語が上位に来すぎるし、2乗だと固有名詞ばかりが上位を占めてしまうので、1.5乗くらいが具合がいい。さらに、数値を含む語と平仮名のみの語にはスコアを半減させるペナルティを与える。ここで重要なのは、ソートはIDFを適用した値で行うが、記録する値はあくまでIDFを適用しない生の頻度だということだ。共起語データベースから最終的に類語の抽出を行う際にコーパス全体から算出したIDFを適用したいので、ミニバッチ内のIDFの影響が残らないようにしたい。

複数のミニバッチの結果をマージするためには、SkipDBMが備えるマージ機能をそのまま使えばよい。その際に、同一キーのレコードはまとめられて、reducerとして仕掛けた関数が呼ばれる。reducerは渡された値のリストを読んで、任意の値を出力することができる。今回は、各レコードの値を10進数値とみなして加算する組み込みのreducerを指定することで、スコアの合算を行っている。このように、SkipDBM自体をローカルのMapReduceフレームワークとみなすと設計がしやすい。分散処理を行なっているわけではないが、比較的コストの高いShuffleプロセスとReduceプロセスをC++の実装に担わせることで、全体のスループットが向上する。実際のところ、ミニバッチの出力はレコードがソートされているデータであればDBMである必要はなく、改行区切りのテキストとかでも問題ない。SkipDBMのマージ機能が使いたいからそうしているだけなのだ。

およそ15万文書毎にミニバッチを作るとなると、880万文書はおよそ60個のミニバッチに分けて処理されることになる。ミニバッチは独立して実行されるので、直列に実行する場合の時間計算量はバッチ数Mに対してO(M)だ。また、100個くらいのDBMファイルをマージするのは造作もないことだ。個々のミニバッチのSkipDBMのレコードは事前にソートされているので、マージ処理の計算量は全レコード数Nとミニバッチ数Mに対して N log(M) で済む。しかし、制限もある。ミニバッチの数が100とかなら良いのだが、多すぎるとプロセス毎のファイルディスクリプタの数の制限に引っかかったり、ファイルシステムのキャッシュが効きにくくなって遅くなったり、ストレージ要領が足りなくなったりする懸念がある。メモリ容量が限定された環境ではミニバッチの数はもっと増えるだろうし、Wikipediaよりももっと大きなコーパスを解析したくなることもあるだろうから、スケーラブルなシステムとしてはそれに対応しておきたい。なので、ミニバッチを階層的にマージする機能を実装する。16回のミニバッチ毎に結果をマージするのだ。それを16回続けて256回目のミニバッチが終わった際には、過去にマージされて成長した16個をさらにマージする。もし4096回目があれば同じ要領で、256回毎にマージされた16個の結果をさらにマージする。全部のミニバッチを終えた時点で複数個の結果があった場合には当然全てをマージする。これによってミニバッチの数に上限がなくなるので、ストレージと時間が許す限りはどんなに大きなコーパスも解析できるようになる。

集計結果の変換

ここまでで、単語の頻度を数えたSkipDBMのデータベースと、二つの単語の共起を数えたSkipDBMのデータベースが出来上がっている。最後に、divide_cooccurrences.py の実装について考察する。単語の頻度のデータベースを単語の生起確率のHashDBMデータベースに変換し、共起の頻度のデータベースを共起の確率のHashDBMデータベースに変換する。単語の頻度に関しては文毎に異なり語を数えているので、文の数で割れば確率に変換できる。共起の頻度も同様に文毎の異なり語で数えているので、ペアの片方の頻度で割ればもう片方が共起する確率が求められる。共起語データベースに関しては、最終的な単語データベースの確率値を使ったIDFで単語毎の共起語のランキングをやり直した上で、上位256語をTSVにシリアライズして、単一レコードとして記録する。

ところで、共起語の出現頻度を片方の単語の出現頻度で割る処理を行うには、単語の文字列でその出現頻度を調べるための連想配列が必要になる。HashDBMである単語データベースがまさにそれなのだが、それを使ったランダムアクセスを行うのはスケーラビリティの観点では望ましくない。探索の計算量がO(1)であるのは良いのだが、データベースがメモリに乗るという前提が怪しいからだ。理想的には、単語データベースと共起語頻度データベースを単語をキーとしてマージした上で、共起語の確率を出力するというMapReduce処理を実装すべきだ。ただ、今回はそうしていない。Wikipedia程度の規模では単語データベースに関しては10MBも行かないことが経験的に分かっているからだ。カットオフの後の1単語の異なり語の数はコーパスの規模が大きくなっても線形には増えないので、単語頻度データベースがメモリに乗らないと言う事態にはまずならないのが実際のところだ。また、ミニバッチで生き残った語は頻出語に偏る傾向があるため、単語頻度データベースの前段にキャッシュを使うと非常に効率的に処理が行える。キャッシュにはCacheDBMクラスを用いる。50000語もキャッシュすればヒット率は100%にかなり近くなる。こんなこともあろうかとCacheDBMクラスを実装していたのだ。

考察

観測事象の頻度をただ数えるだけの割に、やたら複雑な仕様である。こんなんで本当に動くのか。もちろん、動くのだ。そのためのDBMであり、Tkrzwである。解析するのに4日間かかったが、メモリ(プロセスのRSS)は最大で9.5GBしか使っていない。ここがポイント。金がなくても時間があればスケールするのだ。スポンサーがいれば1万台のマシンを唸らせて20分で終えられる処理だろうが、スポンサーがいなくても4日かければ同じような結果が得られる。プロだったらイテレーションの遅さはむしろ金に直結するわけだが、アマチュアだったらその間に勉強なりバイトなりアニメ鑑賞なりで有意義に過ごせばよいので、遅くて安いという選択肢もありだろう。

英語の共起語のサンプルをいくつか見てみよう。単語毎に、主要共起語を示す。順位は重要度順であり、重要度は共起確率にIDFの重み付けを適用したものである。

単語 共起語1位 共起語2位 共起語3位 共起語4位 共起語5位 共起語6位 共起語7位 共起語8位
japan prefecture japanese tokyo in korea china and of
tokyo japan japanese at in university and on osaka
saitama prefecture seibu japan lions tokyo omiya urawa chichibu
tokorozawa saitama seibu station prefecture japan ikebukuro nishi tokyo
president vice of was served he as elected and
emperor roman holy ii reign dynasty his of empire
christmas eve merry day carol on album a tree
summer olympics competed at men"s paralympics in athletics he
winter olympics at skiing summer during competed skating ice
love song with her you i and me album
hate i love speech crime you to but and
run to by a for and on in with
swim adult swimming team water and a fish at
car racing a accident driver cars touring was race
boat u torpedo flotilla a patrol by was on
soccer football league team men's player women's club played
football association team league national club played american player
man a who his young spider he and as
woman her she a who first young man to

「japan」や「christmas」などの特徴的な単語であれば、単語を隠しても共起語のリストを見れば元の単語が推測できるだろう。もしそうであれば、その単語の特徴を良く表していると言えるし、似たような共起語を持つ単語との間には類語の関係が成立すると言っても良さそうだ。一方で、「run」や「man」などの頻出語に関しては、IDFによる補正をかけてもなお「a」や「to」などの頻出語が上位の共起語になるため、共起語だけを見て語を推定するのは容易ではない。とはいえ、例えば「run」であれば、「to」や「by」などの前置詞の共起率から類似度を計算するだけでも、一般的な文脈での類語が推定できる。また、下位の共起語も見れば「election」などのと特徴的な共起語もあるので、文脈依存の類語も推定できる。

日本語の共起語のサンプルもいくつか見てみよう。

単語 共起語1位 共起語2位 共起語3位 共起語4位 共起語5位 共起語6位 共起語7位 共起語8位
日本 協会 学会 代表 放送
東京 出身 本社 大学 学校 都立
埼玉 西武ライオンズ 出身 県立 さいたま
所沢 埼玉 西武 都道 小手指 入間
大統領 選挙 アメリカ合衆国 候補 就任 共和 首相 ルーズベルト
皇帝 ローマ 神聖 帝国 即位 ローマ帝国
クリスマス キャロル ソング プレゼント christmas イブ イヴ スペシャ
大会 祭り 甲子園 野球 全国
気候 気温
愛する こよなく 自分
憎む 激しく べき よう 自分
走る 道路 南北 路線 東西 国道 列車
泳ぐ 水中 速く こと 姿 イルカ 水泳
機関 蒸気 国鉄 車両 鉄道 電気
輸送 貨物 建造 巡視 連絡
サッカー 選手 代表 ポジション クラブ 出身 リーグ ディフェンダー フォワード
フットボール リーグ クラブ チャンピオンシップ サッカー チーム 日本 カレッジ 選手
たち 映画
教師

日本語も同じ傾向で、特徴的な語ほど共起語から元の単語が推定しやすいが、一般的な語ほど難しい。英語で前置詞がよく共起するように、日本語では助詞が共起しやすい。日本語ならではの問題として、分かち書きの曖昧性がある。「西武」も「ライオンズ」もそれぞれ単語として出現しうるが、「西武ライオンズ」と連続した場合、Mecabはそれを一つの単語として扱う。「西武ライオンズ」が出現した場合には「西武」も「ライオンズ」も数えられないので、そのような表記ゆれによって精度や再現率が落ちる可能性がある。これに関してはMecabのN-best機能を使うと緩和できる。この考え方を拡張すると、bi-gramやtri-gramのフレーズを数える機能に発展するが、さらに計算量を増やすのは大変なので今回は割愛する。

唐突に思い出したのだが、昔、某SNSに日記キーワードランキングなる機能があった。秋に金木犀の花が香りだすとちゃんとそれがランクインするし、ユーザ目線で注目のニュースがあればその言葉をタイムリーに拾う。一方で、推しキーワードをランクインさせるために様々な工作を行う各方面のコミュニティがあったりして、なかなか楽しい機能だった。その集計システムは私が実装したものだ。分かち書きした後の単語N-gramの確率モデルでキーワードのフレーズを推定するとともに、表記揺れを吸収するために類語推定を行った上で、候補となるキーワードの頻度の上昇率を比べる仕組みであった。そこでも共起語の数え上げをPerlで書いていたわけで、10数年経ってもやってることが変わってないなと。

まとめ

Wikipediaのデータを使って共起語の頻度を数えるプログラム群を実装してみた。入力データがWikipediaであるかどうかは実際にはどうでもよい。たった1台のノートPCでも、880万記事(5.6億文、112億語)の規模のコーパスを分析して各単語の出現確率と共起語の出現確率を記録したデータベースが作れることを示したかったのだ。分散処理のフレームワークを一切使わずとも、DBMにデータを入れていくだけでそれなりに実用的な共起語データベースを作ることができるのだ。並列分散でなく直列集中なアーキテクチャの中で、できる限りスケーラブルなシステムを実現できたと思う。分散処理システムが暗黙的かつ並列にやっている手順をローカルで明示的かつ直列にやっているだけだし、様々なレベルでカットオフを導入しているおかげでなんとか動いているだけとも言えるが、敢えてそういう泥臭い部分をスクリプトとして表現するのも一興であろう。

同じようなやり方で、言語モデルも作ることができる。複数の単語が連続して出現する確率をデータベースにしたものだ。同じようにカットオフを駆使すれば、tri-gram(3単語)くらいまでなら1台でも実用的なモデルが作れる。素直に分散処理システムを学んで使った方がより良い高品質な結果が得られるだろうが、基本的な課題と解法は分散させようがさせまいが変わらないので、ここで書いたことも役立つだろう。

手段に没頭して目的を忘れるところだった。本来の目的は、類語の自動抽出を行うことである。次回は、共起語データベースを変換して類語のデータベースを作る手法について検討する。