ナイーブベイズ分類器であいさつbot作ってみた

スパムフィルタでよく使われてる、ベイジアンフィルタのことです。これを使って「おはよう」判定してみました。
1000speakersのときに「ベイズやらないんですか？」って言われたり、tockriの人が以前「やっぱベイズよくできとるわ」とか書いてたり、テキスト分類ならベイズでいいん違うかと思ってみたので、やってみました。

結果から言うと、なんか不安定というか、1文字の違いで「おはよう」判定してしまうことがあります。ちゃんと性能測ってみないとわかんないですけど。
考えられるのは、データが少ないことですが(「おはよう」が750件中39件)、それよりも、ついったの発言では「おはよう」発言の中に「おはよう」と関係ない言葉が入ることが多くて、それが悪影響あたえてるんじゃないかと思います。ナイーブベイズのアルゴリズムを考えると、データ中のノイズに弱い気がします。
「。」や「！」で文章を区切って学習・判定するといいかもしれません。これだとSVMの場合でも性能でそう。

比べてみて思ったのは、ベイズは実装が簡単だし大量データに強いということです。学習はデータ数をカウントするだけだし、判定は割り算して全部掛けるだけ。
決定論的に計算するので、ゆらぎがないし、ノイズがなければ強そう。
一方で、やっぱSVMは大量データには学習時間かかりまくるのだけど、データが少なくてもうまいこと特徴を抜き出してくれるな、と思いました。

ということで、ナイーブベイズ版のソース
こんな感じで「おはよう」の先頭に「m,」をつけて区別したデータを使います。このファイルをtwit.txtという名前でプログラムと同じフォルダに保存しておきます。

バスで駅に向かっている。
ただいま。
m,おはよ-
早く来い飯。
とりあえずシャワ-浴びるか。
だいじなメ-ルおくった。
m,うぐう、起きた。10時半から会社。
m,おはようございます。本を読んでたら寝てしまってました。

あとは、ソースはこんな感じ。GUIまわりは、NetBeansで生成したソースからコメントを抜いただけです。

改めて2次多項式カーネルであいさつbotをやってみる

こうですね。わかります。

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 + 1) * (n + 1);
}

ということで、2次多項式カーネルにするには、1足して2乗するだけということなのでやってみました。結果ですが、なんかよくなってるような気もするけど、よくわかりません。。。
やっぱ、ちゃんと交差検証で性能試せるようにしないと。

あいさつbotで2次の多項式カーネルを試してみる。

こうですか？わかりません＞＜

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

前のエントリで、しましまさんに教えてもらったので、2次の多項式カーネルでやってみようと思ったんだけど、これでいいんだろか？
共通する2文字について、文書1と文書2での頻度をすべての組み合わせで掛け合わせたものを足してみました。
でやってみたけど、やっぱり「おは」には反応しまくりでした。
ということで、せっかくしましまさんに文字列カーネルの参考文献教えてもらったので、次はまじめに文字列カーネルを作ってみます。

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

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

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

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

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

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

ガウシアンカーネルのパラメータを自動的に求めてみる

サポートベクターマシンでよく使うガウシアンカーネルでは、パラメータが重要になるということを書きました。
で、ちょうどいいところに、id:audioswitch:20080730で、そのガウシアンカーネルのパラメータを自動的に求める方法が書かれていたので、試してみました。
σ^2=100程度の数値が出てきます。(リンク先でのパラメータはσとかいてますが、ぼくのところでは同じ値をσ^2としてます。)

今回のデータでは、だいたいいい感じだけど、もう少し大きい数値のほうがいいかな〜という感じですね。それにしても、とりあえずの値を求めるにはよさそうです。
関係ある部分のソースだけを書いておきます。

private void btnLearnActionPerformed(java.awt.event.ActionEvent evt) {
    if(patterns.size() == 0) return;
    solveGaussianParam();
    learn();
    learned = true;
    paint();
    canvas.repaint();    
}

    void solveGaussianParam(){
        double s = 0;
        int count = 0;
        for(Map.Entry<Integer, Point> p1 : patterns){
            double m = Double.MAX_VALUE;
            for(Map.Entry<Integer, Point> p2 : patterns){
                double d = (p1.getValue().x - p2.getValue().x) * (p1.getValue().x - p2.getValue().x) +
                        (p1.getValue().y - p2.getValue().y) * (p1.getValue().y - p2.getValue().y);
                if(d == 0) continue;
                if(d < m) m = d;
            }
            if(m == Double.MAX_VALUE) continue;
            s += m;
            ++count;
        }
        sig = Math.sqrt(s / count);
        System.out.println(sig);
    }

    double sig = 35;

    double kernel(Point x1, Point x2){

        //ガウシアンカーネル
        double n = (x1.x - x2.x) * (x1.x - x2.x) + (x1.y - x2.y) * (x1.y - x2.y);
        return Math.exp(-n / (sig * sig));//5 1.2 .5は分散の2乗
    }

ところでサポートベクターマシンって何なの？

最近、機械学習とか、そのアルゴリズムのひとつであるサポートベクターマシンとかやってるわけですが、そもそも機械学習ってなんなんでしょか？
機械学習ってのは、なんとなく与えられた点の分類から、新たに与えられた点の分類を推測するのですが、ようするに、点が与えられたときにそこから分類の領域を推測しておいて、新たな点がきたときにはどの領域に入るかを判別するのです。

ニューラルネットワークは、名前にニューロンとかついてて、とてもステキな響きがするのですが、あれは関数のあてはめを行っているのです。そうやって関数をあてはめることで、領域の境界面を求めます。
NN法は、学習とかせず、一番近いデータが同じ分類になるはずという戦略でやってます。
サポートベクターマシンも考え方としてはNN法と同じで、新しい点がやってくると、学習したそれぞれの点までの近さを計算して、一番ちかい分類を求めます。そのため、学習データが増えると、学習に時間がかかるようになります。ただ、NN法と違うのは、学習した点のうち、境界面を形作るものだけをサポートベクターとして残して、判別にはそのサポートベクターだけを使うところです。そうすると、学習結果はサポートベクターとそれに対応する係数だけを覚えておけばいいことになります。そのため、実際の判別では、限られた数のサポートベクターとの比較を行えばよくなり、メモリも食わず時間もかからないということになります。

どんな点がサポートベクターになるかを見てみると、こんな感じになりました。大きい点がサポートベクターです。いい感じに、境界付近の点だけがサポートベクターになっています。サポートベクターではない点は、データ判別の段階では捨ててしまってもかまいません。

ところで、SVMではカーネルを使って非線形分離を行うのですが、そこで大切なのがカーネル固有のパラメタです。今回はガウシアンカーネルを使うのですが、ここでもひとつパラメータを与える必要があります。Math.expの引数の分母になってる数ですね。σの二乗を指定することになってます。
このパラメータがなにかを見てみるために、いろいろいじってみました。上の画像のときには1500を指定してるので、σはだいたい40程度ということになります。
これをσ^2=100、つまりσ=10とするとこんな感じになります。

境界面がガタガタになっています。ほとんどの点がサポートベクターになっています。この境界面は、学習データに適合しすぎて、学習データが変われば判別面は大きく変わるし、ちょっとデータがずれると判別結果が変わることになってしまいます。
機械学習で大切なことは、既知の学習データから未知のデータを分類することですが、これでは既知の学習データはうまく分類できるけど、未知のデータがうまく分類できるかどうかは学習データに強く依存することになってしまします。未知のデータをうまく分類できるかどうかのことを汎化能力といいます。
σ=5くらいにしてMath.exp(-n/30)とすると、もっとひどいことに。

学習データはうまく判別できてるのですが、おそらく未知データはまったく判別できない境界面になっています。数個の点を除いて、すべてがサポートベクターになっているという感じです。そうすると、近い学習点があるかどうかで判別をすることになってしまいます。
で、わかったことは、ガウシアンカーネルのσは、学習データの影響範囲で、判別面はその影響範囲をつなぎ合わせたものになるということです。今回のサンプルでは、σは学習データの影響するドット数と言えます。
ガウシアンカーネルのパラメータσは少なすぎるよりは大きすぎる方がよさそうです。

サポートベクターマシンの本はこの本が参考になります。

サポートベクターマシン入門

ということで、今回のプログラム。単独で動きます。

SMOの収束速い！

KKT条件だけじゃなくて、変位の合計を見て収束しているかどうか判定するようにしたら、これめちゃくちゃ収束速いじゃないですか。
非線形分離の方で50回程度、線形分離の方だと2回とか3回で収束しちゃってます。
線形分離の場合で分離面が全然変なところに行っちゃうのは、バイアス(b)の求め方が悪かったからで、平均を取るようにしたらそれなりにいい感じのところに収まるようになりました。

とりあえず、これならいろいろとSVMを試すのに使えそうです。
さて、ところでこうやって実装したサポートベクターマシン、なんに使おう？

ソースはこれ。