サポートベクターマシンであいさつbotを作るためのカーネル関数

nowokay2008-08-08

Twitterの発言に、「おはよう」かどうかのフラグをつけてSVMに食わせると、その発言が「おはよう」かどうか判定できるようになるので、「おはよう」判定したら「おはよ〜」と返すようにするとあいさつbotのできあがり。


というときに問題になるのが、カーネル関数をどうするかということ。文字列カーネルというのがあるようなんだけど、詳しいことがわからなかったのと、ちゃんと調べて実装するのもめんどかったので、とりあえず2文字ずつを比べてみるようなカーネル関数を考えてみた。
  2文字の頻度=√(2文字の出現回数/全体の長さ)
としておいて
  一致度=Σ(発言1での頻度 * 発言2での頻度)
とするようなカーネル関数を作成。完全に一致すると1、まったく一致しないと0になるはず。これがカーネル関数として使えるかどうかわかんないけど、内積の計算っぽいから大丈夫なはず。


そう。計算としては超高次元の内積を計算していることになるわけです。
1000発言とかの学習が10分程度だったので、これを速いとみるか遅いとみるかですけど、使い物にならない速度ではなくて、「サポートベクターマシンは超高次元に対応できる」というのがなんとなくわかりました。内積をとったことになればいいんですね。


で、結果としては、なんとなく「おはよ〜」とか「おっはよ」とかに反応するようになった。
けど、2文字単位の一致度をみてるので「おは」とか「はよ」とかが入ってる「起き」が入ってる文章に反応してるっぽい。
実際には使えませんな。
ついったの発言は、短くて乱れまくりなので確実な解析は難しい気もしますが。


というか、マジレスすると、ついったであいさつbot作るときは@で「おはよう」とか返されている人に「おはよ〜」ってするようにすれば、はずれ率の低いあいさつbotになるわけですがね。
あと、「おはよう」は比較的簡単で、一定時間アクセスがなくて、なおかつSVMがおはよう判定したものをあいさつとみなすようにすればいいんですよね。


とりあえず、頻度を求めるところはこんな感じ

    static Map<String, Double> getHisto(String str){
        Map<String, Double> ret = new HashMap<String, Double>();
        str = "。" + str.trim();
        if(!str.endsWith("。")){
            str = str + "。";
        }
        int length = str.length() - 1;
        for(int i = 0; i < length; ++i){
            String bi = str.substring(i, i + 2);
            if(!ret.containsKey(bi)){
                ret.put(bi, 1.);
            }else{
                double d = ret.get(bi);
                ret.put(bi, d + 1);
            }
        }
        for(Map.Entry<String, Double> ent : ret.entrySet()){
            ent.setValue(Math.sqrt(ent.getValue() / length));
        }
        return ret;
    }


カーネル関数がこんな感じ

    double kernel(Map<String, Double> x1, Map<String, Double> x2){
        double n = 0;
        for(Map.Entry<String, Double> ent : x1.entrySet()){
            if(!x2.containsKey(ent.getKey())) continue;
            n += ent.getValue() * x2.get(ent.getKey());
        }
        return n;
    }