きしだのはてな このページをアンテナに追加 RSSフィード

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

nowokay2008-08-08

[][]サポートベクターマシンであいさつbotを作るためのカーネル関数 15:38 サポートベクターマシンであいさつbotを作るためのカーネル関数を含むブックマーク

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


というときに問題になるのが、カーネル関数をどうするかということ。文字列カーネルというのがあるようなんだけど、詳しいことがわからなかったのと、ちゃんと調べて実装するのもめんどかったので、とりあえず2文字ずつを比べてみるようなカーネル関数を考えてみた。

  2文字の頻度=√(2文字の出現回数/全体の長さ)

としておいて

  一致度=Σ(発言1での頻度 * 発言2での頻度)

とするようなカーネル関数を作成。完全に一致すると1、まったく一致しないと0になるはず。これがカーネル関数として使えるかどうかわかんないけど、内積の計算っぽいから大丈夫なはず。


そう。計算としては超高次元の内積を計算していることになるわけです。

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


で、結果としては、なんとなく「おはよ〜」とか「おっはよ」とかに反応するようになった。

けど、2文字単位の一致度をみてるので「おは」とか「はよ」とかが入ってる「起き」が入ってる文章に反応してるっぽい。

実際には使えませんな。

ついったの発言は、短くて乱れまくりなので確実な解析は難しい気もしますが。

f:id:nowokay:20080808153718p:image


というか、マジレスすると、ついったであいさつ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;
    }

しましましましま 2008/08/08 22:38 > これがカーネル関数として使えるかどうかわかんないけど、内積の計算っぽいから大丈夫なはず。

平方根をとらなければ,バイグラム(=2文字ずつ)を要素とするベクトルの内積なので,普通の線形カーネルですね.
これだと,「おは」があるかどうかしか効いてこないので「おは」と「はよ」が同時に生じるということを考えるために,2次の多項式カーネルとかだと改善されるかもしれません.

> 文字列カーネルというのがあるようなんだけど、詳しいことがわからなかった

この分野を代表する福水先生のスライドの5章とかにあります.
http://www.ism.ac.jp/~fukumizu/ISM_lecture_2004/

よろしければ,朱鷺の杜Wikiにもちょっとあります.
http://ibisforest.org/index.php?%E6%96%87%E5%AD%97%E5%88%97%E3%82%AB%E3%83%BC%E3%83%8D%E3%83%AB

コードをご覧になりたければ,機械学習のコードのポータル mloss
http://www.mloss.org/software/
で”string kernel”とかで検索するといくつかでてきます.(残念ながら java のものはないようです)
※ Smola とか Vert とかこの分野の大物の名前が見えます.