らこらこブログ

唐揚げとアニメとプログラミングが大好きです

メカらこ開発記録 02/09

進捗報告と今後について

とりあえずPCFGとトリグラムモデルでのマルコフ連鎖を組み合わせた文章生成botは完成してます。

PCFGのC#での実装の解説については近いうちに別の場所でPCFGそのものの解説も含めてしようと思います

文章生成系の実装ですが今の流れは

  1. リプライを受け取ると生成開始
  2. 非終端記号SからPCFGで計算した確率を反映しながらトップダウンで終端記号列(品詞列)を生成
  3. 品詞列を元に拡張トリグラムモデルでのマルコフ連鎖を行って文章生成

です

3の拡張トリグラムは単語と品詞をセットにしたトリグラムモデルで、単語列W1, W2, W3と、それに対応する品詞列P1, P2, P3を持っています。

すでに生成された品詞列をP[n](n=0～N, N>2)、
連鎖で生成された単語列をW[n]とすると
i番目の単語W[i]の決定条件は

  1. W2がW[i-1]と一致している（前方1単語一致）
  2. かつP3がP[i]と一致している（品詞一致)
  3. かつW1がW[i-2]と一致している（前方2単語一致）
  4. かつP2がP[i-1]と一致している（前方1品詞一致）
  5. かつP1がP[i-2]と一致している（前方2品詞一致）

の順番でより下の方の条件にマッチしたトリグラムモデルの集合からランダムで選択します。

現状の課題は2のトップダウンで品詞列を生成するところで、確率に依存するので短い文になるときもあれば長い文になることもあって、長いこと自体は構わないのだけど今までに見たことのない品詞列が生成されることがあるため、トリグラムの連鎖条件がなかなか下の方に進めなくてめちゃくちゃな文章になります

なのでPCFGの恩恵をうけつつスムーズに文章生成するために、文章生成のたびにランダムに品詞列を作るのではなく、UserStreamからPCFGで得られた「見たことのある品詞列」をそのままDBに保存して、それをランダムに選択して利用するように変えます

これならより人間らしい自然な構文が得られる上に文章生成も早くなる（品詞列生成はそこまでネックではないが）ので期待大です

デメリットとしてはランダム要素が減るので面白みが減る可能性がありますがこれは実際に動かしてみてから考えます

現状でもhttps://twitter.com/la0cは稼働中ですので遊んであげてください

メカらこ開発記録 02/02

今日はめちゃくちゃ実装を進めました

構文木を作るにあたってMeCabが吐き出す生の形態素のままでは細分化されすぎていてとても文法規則を定義しきれないので、ある程度の補正が必要だということに気づいた

ということで思いついたのは連続する重複品詞を結合する方法。
適当にやったらこうなった


ということでもうちょっと細かく品詞を読み取ってあげたら
ということでまあ解決？

ソースコードはこんな感じで、連続した重複品詞をまとめて、単語を結合してます

public void Fix()
{
    var list = new List<PosPair>();
    var current = PosPairs.First();
    foreach(var x in PosPairs.Skip(1))
    {
        if(current.Pos == x.Pos)
        {
            current.Gram = string.Concat(current.Gram, x.Gram);
        }
        else
        {
            list.Add(current);
            current = x;
        }
    }
    list.Add(current);
    PosPairs = list;
}

なんやかんや実装を進めてなんとか構文木を作れるまでになりました


構文木の最尤推定がちょっと危ういんですがこれは追々どうにかします

残りのタスクは、

  • 構文解析系…文法規則を増やして受理できる文を広げる(手動)
  • 語彙学習系…未着手
  • 文章生成系…未着手

です

一番きつそうなところが終わったので完成まで頑張ります

メカらこ開発記録 01/26

少しずつ実装進めてますが基本的な方針がやっと決まりました

問題



助けを求める





ひらめく

ということで、以下の工程で。

学習

  • 文をMeCabで形態素解析
  • 品詞列とそれに対応する単語列を得る
  • 複雑すぎる日本語を扱いやすくするためにいろいろ補正する（結合など）
  • 補正された品詞列をPCFGで構文解析する
    • ボトムアップで品詞,品詞句を結合していく（右辺から左辺への逆変換）
    • 開始記号Sに収束したパターンで使用された規則の出現回数を加算する
  • 加算された出現回数をもとに全規則の確率を再計算する
  • 品詞列と単語列から、(品詞,単語)のペアのNグラムモデル（拡張N-POSモデルとでも呼ぶか？）の出現回数を加算する

文章生成

  • 開始記号Sから確率に従って規則を適用して品詞列まで分解する
  • 品詞列を先頭から拡張N-POSモデルを適用して、品詞ごとに単語を割り当てていく
    • 先頭N個の品詞と一致する並びのモデルを開始モデルとする
    • 単語情報を元にマルコフ連鎖を行うが、品詞列と品詞が一致しないモデルは除外する
      • モデルの割り当ては連鎖可能モデルのそれぞれの出現回数に比例した確率を適用する

やっと形が見えてきたのでぼちぼち頑張っていきましょう

[追記]
確率補正用の学習については上の通りでそこまで難しくなさそうだけども、生成規則自体を学習する方法がないかどうか検討してみた


  • 文法的に信頼できる文を規則の学習データを用意する
  • 形態素解析を行う
  • ボトムアップで品詞,品詞句を結合していくが、まずすでに存在する規則を適用し、Sに至らなかった場合は仮の規則を作って開始記号Sに至る全てのパターンを得る

ここまで考えたところで、仮の規則の数が一番少ないパターンを新しい構文として認めて、仮の規則を正式に採用して確率学習に用いる…っていうのは、正直どうなんだろうと思った。
仮の規則の数が少ないからといってもっともらしい構文であるという保証がないので、そうするならその証明が必要。最尤推定の問題を作らないといけない。死。

できるわ　とか書いたけど、出来そうにないのでやっぱり棚に上げときます。いつかやろう

誕生日プレゼントまとめ 2014

全て出揃いました！！
全部並べた画像がこちら！！

なかなかにておい

画像に確率的言語モデルを入れるのを忘れてました

となりました。

カロリー計算しました。

頭お菓子インカ


去年とは比べ物にならない数と質にただただ感謝です。頑張って食べて太ります

IEnumerable<T>#Random()の実装について

C# プログラミング

C#、LINQネタです。

LINQでIE<T>を扱っていると、「ランダムに要素を1つ取り出したい」と思うことが時々あります。なのでそういう時は拡張メソッドで

IEnumerable<T>#Random()

を実装すると便利ですね。
ところでこのメソッドの中身、どう実装するのがパフォーマンスがいいのかを実験してみたので書いてみます。
とりあえず思いついたのは3種類だったのでそれぞれ実装しました


  • RandomOrderBy

SQLなんかでよくやる、OrderByでランダムにソートして先頭を取り出すというやりかた。
全要素に対して1回のソートが必要なので計算量はO(n)ですかね

  • RandomElementAt

これは直感的に、ランダムな位置の要素を直接取り出すというやり方。
計算はRandom#Nextの一回とElementAtの2回だけですが、ElementAtの実装によってはインデックスの値によって計算量が変わるかも…？

  • RandomSkip

これはちょっと工夫して、ランダムな数だけ要素をスキップして得られた列挙の先頭をとるやり方です。効率はそんなによくなさそうですが操作が単純なので内部の実装しだいでは勝てるかもと思って実装しました

それぞれを要素数100000の整数の列挙に対して1000回行った実行時間でパフォーマンスを比較しますが、IE<T>の内部実装によって挙動が変わるかもしれないので、サンプルの方も、
IE<T>型、配列型、List<T>型の3種類を用意しました。最終的なコードがこちら

そして実行結果がこちら


  • RandomOrderBy

遅い。とにかく遅い。内部実装によらず遅い。論外。

  • RandomElementAt

クッソ早い。IE<T>型はおそらく内部でインデックス化されていないために若干の時間ロスがあるが、配列、List<T>型ではあまりにも早い。多分これが最強。

  • RandomSkip

これも結構早い。ElementAtには勝てない。

結論: ElementAtを使うべき。

だいたい予想通りの結果になりましたがOrderByのあまりの遅さとElementAtのあまりの早さに笑いました。
ElementAtは早かったですが、さらにこれは多分要素数に非依存なので、他の2つとくらべて100000件よりもずっと大きな列挙に対しても同じようなパフォーマンスが得られると思います。

以上LINQ小ネタでした。多分Qiitaにも要約して書きます