« 2005年08月 | メイン | 2005年10月 »
2005年09月28日
はてなキーワードを高速に付与 (マルチバイト処理)
前回に紹介した hackですが、いくつかの問題があるようです。
とくにマルチバイトの処理は完全にスルーしてました。まずかったです。mecab がやってることは件のキーワードの処理とほぼ同じですが、ちゃんとマルチバイト処理をやっています。そこで、安直に mecab の該当部分を移植してみました。基本的には mblen 相当を実装するだけです。(mblen を使ってもかまいません)
投稿者 taku : 21:52 | コメント (44) | トラックバック
2005年09月23日
手書き文字データ
Ajax 手書き文字認識を公開して、おかげさまで多数のアクセスがありました。
みなさんが入力,選択したデータは、すべて蓄積しています。2万事例ほど集まりました。誤解があったのかもしれませんが、オンラインでの学習はしておりません。後ほどバッチで再学習するつもりです。ただ、「使える」データがどれくらいあるのか実際にチェックする必要はあると思っています。チェックに相当時間がかかりそうですが。。。どなたか協力していただけると大変助かります。
さて、本システムの公開を通じて個人的に非常に面白かったのは、不特定多数の手書き文字が非常に短時間で大量に集まったことです。機械学習ベースのシステムを作る際、いかにして学習データを作ればいいのかが大きな問題になります。企業や個人プロジェクトは、大量の人的金銭的リソースをつぎ込んでデータを作成していますが、今回はその必要ありませんでした。 改めて Web の力を実感しました。
今回得られたデータは、本家のTomoe(オープンソース手書き文字エンジン)にフィードバックする予定です。オープンソースの認識エンジンの精度向上に貢献できればと思います。
投稿者 taku : 00:43 | コメント (29) | トラックバック
2005年09月19日
Ajax を使った手書き文字認識
Ajax で手書き文字認識を作ってみました。
http://chasen.org/~taku/software/ajax/hwr/
Javascript で描画処理を行い、非同期に座標情報をサーバに送ります。サーバでは文字認識を行い、尤もらしい結果を返します。
前回の Ajax IME と違い、今回はクライアントサイドではなくサーバーサイドの認識エンジンの開発をがんばってみました。画像処理は専門外で経験がありません。逆に言えば、チャレンジングな問題だったし、精度が向上していく様を見てるとわくわくしました。
認識には、機械学習アルゴリズムのひとつである SVM を用いています。学習データとして、オープンソースの手書き文字認識エンジンの Tomoe のデータを使っています。完全に機械学習ベースなので、適当に入力して正解を提示することを繰り返せば、精度が上がっていくと思います。
まだまだ、精度が低いです。とくにストロークが単純なひらがなの精度はボロボロです。
追記
候補選択をして、結果をフィードバックするようにしました。
学習データの収集のためです。
投稿者 taku : 13:44 | コメント (14) | トラックバック
2005年09月17日
Ajax で migemo を頑健に
右の検索ボックスは migemo のようにローマ字でインクリメンタル検索ができます。
いままで動作が不安定だったのですが、より頑健にしました。
投稿者 taku : 21:13 | コメント (14) | トラックバック
2005年09月11日
はてなキーワードを高速に付与 (SWIG を使って Perl モジュール)
トラックバックにあったのですが、スクリプト言語(perl)から使えたほうが便利だとのご意見をいただきました。さくっと SWIG で perl/ruby/python binding を作ってみました。やっぱり SWIG は楽です。
C++ のインターフェイスとして以下のファイル (hatenakeyword.h) を作ります。
hatenakeyword.h には、実際のコードも入っています。
namespae HatenaKeyword {
class AutoLink {
private:
.. 省略
public:
AutoLink(const char*);
AutoLink(const char*, const char*);
virtual ~AutoLink();
const char *assign(const char*);
};
}
次に、SWIG のインターフェイスファイルを作ります。単に hatenakeyword.h を include しているだけです。
%module HatenaKeyword
%{
#include "hatenakeyword.h"
%}
%include hatenakeyword.h
以下のように swig を実行することで perl バインディングができます。-shadow としているので、C++ の OO インタフェイスをそのまま wrap するための shadow クラスを作ってくれます。
% swig -perl -shadow -c++ hatenakeyword.i % swig -python -shadow -c++ hatenakeyword.i (python の場合)
実際に使ってみます。
use HatenaKeyword;
my $sentence = "太郎と花子ははてなにblogを持っていてAjaxに興味を持っています。";
my $c = new HatenaKeyword::AutoLink("../keywordlist.da");
print $c->assign ($sentence), "\n";
コンストラクタの第二引数を使って、自分で置換のパターンを指定することができます。
my $c = new HatenaKeyword::AutoLink("../keywordlist.da",
"<a href=\"http://chasen.org/%e\">%s</a>");
%s はキーワードの文字列そのもの, %e は URL エンコードされたキーワードに置換されます。
C++ と XS の相性は悪いというご意見があるのですが、SWIG を使えばそうでもないです。shadow クラスを作ってくれるし、よっぽど特殊なインターフェイスでないかぎり C++ のクラスをそのまま perl/ruby/python のクラスに変換してくれます。C++, SWIG, perl/ruby/python の組み合わせは、長いことお世話になっています。アプリケーション作成の幅を広げてくれたのは間違いないです。
投稿者 taku : 23:35 | コメント (36) | トラックバック
2005年09月07日
はてなキーワードを高速に付与
人づてに聞いた話なのですが、はてなキーワードを実際の blog に付与する処理は、巨大な正規表現で行っているそうです。実際に調べてみると、以下のサイトからキーワード付与API と正規表現が入手できます。
http://d.hatena.ne.jp/hatenadiary/20040205
本当にはてな内部では正規表現を使っているのでしょうか? perl の 正規表現エンジンは NFA なので、単純に or でつなげると、キーワードの個数に比例する計算量になり、スケーラビリティ上の問題があります。実際に上記のサイトの API を使ってみましたが、かなり遅いです。
この手の問題は、情報処理の教科書に出てくる AC 法を使うのが高速です。 AC 法の肝は、キーワードのリストから TRIE を作り, TRIE を辿りながらキーワードをマッチさせることにあります。AC 法は、検索に失敗したときどこから開始したらよいかのリンクを持つことで、さらに高速化しています。
そこで、はてなキーワードを TRIE を使って付与するプログラムを作ってみました。
TRIE の実装には拙作の Darts (Double-Array TRIE) を使っています。実際に付与したデータは rwcp コーパス（新聞記事)の最初の100文です。
TRIE を使った場合 % time head -100 ~/rwcp.3000.text|./hatenakeyword > /dev/null 0.00s user 0.00s system 0% cpu 0.032 total オリジナルの正規表現 % time head -100 ~/rwcp.3000.text| perl hatenakeyword.pl > /dev/null 24.51s user 27.54s system 100% cpu 52.043 total
1600倍ぐらい高速になりました。TRIE 板が C++ ということを考えても充分高速だと思います。
いろいろ調べてみると、同様のコメントは既に話題になっているようです。
http://mput.dip.jp/mput/?date=20040224
http://www.hatena.ne.jp/1069991612
そのうちプログラムを公開したいと思います。
追記
公開しました。Download file
投稿者 taku : 02:28 | コメント (1203) | トラックバック
2005年09月05日
リセットが必要なリモコン
エアコンのリモコンが動かない。新品の電池に交換してもダメ。そもそも液晶の表示が出ない。ここ数日は、リモコンを使わずに応急運転で暑さをしのいでいた。
てっきりリモコンが壊れたのだろうと思って、エアコンを買った店に修理依頼に行ってきたときの話。
私 「あの～このリモコン動かないんですけど」
店員 「電池交換はいたしましたよね？ 電池の残量を調べてみます。」
店員は部屋に入ってなにか作業をしてる模様。ほどなくして、店員が帰ってきた。
なななんと、リモコンは直っていた。液晶表示もちゃんと動いている。
店員曰く、
「電池交換をしたときは、この右隅のリセットボタンをボールペンのようなもので押さないといけないのですよ。。。。」
唖然。電池交換の度にリセットが必要なリモコンなんて見たことも聞いたことも無い。確かに電池のふたのところに分かりにくい字（同じ色で単なる凹凸）でそんなこと書いてある。
いったいなんのために「リセット」が必要なのだろうか？ やりきれない思いでいっぱいになった。
投稿者 taku : 20:41 | コメント (31) | トラックバック
2005年09月03日
jcorrect
jcorrect という文書校正ツールをみつけました。CaboCha を使ってるみたいです。
jcorrect は、形態素解析 / 係受け解析ソフトウェアである、cabocha の解析結果を利用して、日本語文章の校正を補助するツールです。
http://www.ispl.jp/~oosaki/research/tips-jcorrect/
係り受けの具体的な応用がこういう形で公開されていることに感動しました。
投稿者 taku : 04:36 | コメント (29) | トラックバック
2005年09月01日
選挙権が無い問題
奥さん曰く、どうやら私は今回の選挙で投票できないみたいだ。
http://www.city.naruto.tokushima.jp/senkyo/senkyoken.html
によると、
他市町村へ引越し（転出）をした人については、引越し先の市町村に転入届出をしてから、引き続き３か月以上住所を有している人が、その市町村の選挙人名簿に登録されます。引越し前の市町村で選挙人名簿に登録されていた人は、引越し（転出）後４か月を経過するまで選挙人名簿に登録されています。
私の場合、もろもろの事情により4月中旬と7月頭に引越しをした。
4月前の住所の選挙権は、転出後4ヶ月を過ぎているためにすでに失効している。
7月からの住所は、まだ3ヶ月たっていないので選挙人名簿に登録されていない。
がーん。注目選挙なのに投票できないなんて納得できない。街頭演説も新聞の社説も討論番組もすべてが空虚になってしまう。こんなデットロックはすごく稀なケースだと思うが、しかるべきところでちゃんと事情を説明したいし、納得いく回答をもらいたい。