読者です 読者をやめる 読者になる 読者になる

Arantium Maestum

プログラミング、囲碁、読書の話題

Clojureとマルコフ連鎖で自動文章生成

自動文章生成の手法の一つとして昔から有名なのが、マルコフ連鎖n-gramから次の単語を確率的に決めて行くやり方である。

  1. 元となる文章データから、n語の連なり(prefixと呼ばれる)の後に来る単語の確率分布を作る。
  2. 起点としてn語を用意し、確率分布に従ってn+1の位置の単語を決定。
  3. 2~n+2までの位置の語をprefixとして次の単語を決定
  4. 3~n+3までの...
  5. と一個ずつ位置をずらして続けていく。

Clojureだと比較的簡単にコードできそうだったので作ってみる。

まずはヘルパー関数二つ。

(defn map-vals [f hmap]
  (zipmap (keys hmap) (map f (vals hmap))))

(defn reductions-vals [f hmap]
  (apply array-map
    (interleave 
      (keys hmap) 
      (reductions f (vals hmap)))))

hash-mapのvalueを変形していくことが多いので、hash-mapをkeyとvalueに分け、valueにmapとreduceをかけてからhash-mapに戻す関数を定義している。

ついでにhash-mapをarray-mapに変換する関数も。

元データとなるテキストファイルを読み込んで、確率分布に変換する関数を用意。

(defn file->words [file]
  (-> file 
      slurp       
      (clojure.string/split #" ")))

(defn make-ngrams [words n]
  (->> words
       (iterate rest)
       (take n)
       (apply map vector)))

(defn cumulative-frequencies 
  [xs]
  (->> xs
       frequencies
       (reductions-vals +)))

(defn words->datamap [words n]
  (let [ngrams   (make-ngrams words n)
        n-1gram  (comp vec drop-last)
        grouped  (group-by n-1gram ngrams)]                            
    (->> grouped
         (map-vals #(map last %))
         (map-vals cumulative-frequencies))))

n語の連なりから次の語を確率的に決める関数と、それを使った無限に続くマルコフ連鎖を定義。

(defn next-word [starting-words data]
  (let [cum-freq  (get data starting-words)
        total     (second (last cum-freq))
        i         (rand-int total)
        pair-at-i (first 
                    (filter #(< i (second %)) cum-freq))
        word-at-i (first pair-at-i)]
    word-at-i))

(defn markov-sequence [starting-words datamap]
  (letfn [(f [words]
             (conj (vec (rest words))
                   (next-word words datamap)))]
    (->> starting-words
         (iterate f)
         (map first))))

初期値の語の連なりと、最終的な文章の長さと、元データのファイル名を引数にとるランダム文章生成関数。

(defn combine-words [words]
   (->> words 
        (interpose " ") 
        (apply str)))

(defn random-text [words word-count file]
  (let [datamap (-> file 
                    file->words
                    (words->datamap (inc (count words))))]
    (if (contains? datamap words)
      (-> words
          (markov-sequence datamap)
          (#(take word-count %))
          combine-words))))

試しに戦争と平和を元データに作成してみる。

(random-text ["in" "a" "sad"] 50 "war-and-peace.txt")

結果:

"in a sad voice, as if anything were now permissible; \"the door to the left, was listening with a dissatisfied air. The Emperor moved forward evidently wishing to show her short-waisted, lace-trimmed, dainty gray dress, girdled with a broad ribbon just below the roof, and around which swarmed a crowd"

なんとなくそれっぽい。

さらに手を加えるとしたらmecabか何かとinteropして、日本語を形態素分解した上で同じプロセスに入力してみたい。

あるいは、英語のままでも、最初の数語もランダムに選択(しかも文章の始まりに合致しそうなところを)という風に作った方が完全にランダムに、それっぽい文章を作るシステムになるかもしれない。

書き方の不満としては、なんとなくrandom-textにいろいろ詰め込みすぎた気がする。確率分布の作成は別にして、引数として入れても良かったかも。

全部今後のTODOということにしておく。