« 2006年02月 | メイン | 2006年05月 »

2006年03月30日

CRF++ マルチスレッド化

マルチスレッドを使って CRF++ の学習を高速化してみました。手元の Core Duo の Windows XP ではきちんと二つの CPU を使っていることが確認できました。

http://chasen.org/~taku/software/CRF++/

直接 _beginthread やら pthread を呼んでもよかったのですが、再利用しにくいです。 せっかくなので差異を吸収する class を書いてみました。関数ポインタの生々しい API を隠蔽してくれる目的も兼ねています。
#define BEGINTHREAD(src, stack, func, arg, flag, id) \
     (HANDLE)_beginthreadex((void *)(src), (unsigned)(stack), \
                       (unsigned (_stdcall *)(void *))(func), (void *)(arg), \
                       (unsigned)(flag), (unsigned *)(id))

namespace CRFPP {

  class thread
  {
  private:
#ifdef HAVE_PTHREAD_H   
    pthread_t hnd;
#else
#ifdef _WIN32   
    HANDLE  hnd;
#endif
#endif
   
  public:
    static void* wrapper(void *ptr) {
      thread *p = static_cast(ptr);
      p->run();
      return 0;
    }

    virtual void run () {}

    void start() {
#ifdef HAVE_PTHREAD_H      
      pthread_create(&hnd, 0, &thread::wrapper, 
                     static_cast(this));
      
#else
#ifdef _WIN32
      DWORD id;
      hnd = BEGINTHREAD(0, 0, &thread::wrapper, this, 0, &id);
#endif
#endif
    }
   
    void join() {
#ifdef HAVE_PTHREAD_H            
      pthread_join(hnd, 0);
#else
#ifdef _WIN32
      WaitForSingleObject(hnd, INFINITE);
      CloseHandle(hnd);
#endif
#endif      
    }

    virtual ~thread() {};
  };
}
ifdef の嵐ですし、エラー処理を考えていませんが、 基本的に pthread_create と _beginthreadex の差異を隠蔽してるだけです。使うときは
class foo: public thread {
  void run () {
    // do something
  }
}

foo f1;
foo f2;
f1.start();
f2.start();
f1.join();
f2.join();
とすれば、f1 と f2 の run の中身が並列に動きます。

投稿者 taku : 01:20 | コメント (11) | トラックバック

2006年03月21日

CRF++ 0.40

http://chasen.org/~taku/software/CRF++/

CRF++-0.40 を公開しました。リファクタリングして、C/C++ の API を作ってみました。
メモリーリークのバグも修正しています。

FlexCRFsという CRFのパッケージがあるのですが、そちらはマルチスレッドを使って学習の処理を高速にしているみたいです。深追いしてみると、期待値の計算を並列にやってパラメータのの更新は単純にLBFGSをシングルスレッドで動かしているようです。実際に期待値計算とパラメータ更新にそれぞれどれぐらい時間がかかるか調べてみると、圧倒的に前者の方が時間がかかっています。これはちょっと予想はずれでした。LBFGSってもっと処理時間がかかるものかと考えていたのですが。。。 

CRF、広くは最大エントロピー法の学習はEMアルゴリズムに似ています。モデルの確率分布の期待値を計算し、それを元にパラメータを更新するというプロセスを何度も繰り返していきます。期待値の計算ってのは、簡単に言ってしまえば頻度計算なので並列処理に向いているのは当たり前ですね。パラメータの更新はそんなに時間がかからない(LBFGSは高速である)ということがわかったので、超大規模な学習もやろうと思えばできそうです。

CRF++もマルチスレッドにしてみようとしたのですが、かなりトリッキーな方法でメモリを共有してメモリの消費量を抑えているため、簡単にはできそうにありません。

投稿者 taku : 23:46 | トラックバック

2006年03月19日

CRF++ に激しいバグ

CRF++ に激しいバグが見つかりました。

http://chasen.org/~taku/software/CRF++/

海外の方から、数万文解析するとメモリーが足りなくなる。という報告を受けたのですが、
そんなことはねーだろうと、適当にあしらっていました。 valgrind で調べてみてもリークしてる風ではないし。。
適当な時間があったので、ソースのリファクタリングも含めて確認してみると、各文毎に開放されるべきフリーリストがそのまま放置されていました。フリーリストはデストラクタで適切にメモリが開放されるので、valgrind ではリークとは認識されません。

今のリファクタリングも含めて急ピッチで修正しています。ご迷惑をかけて申し訳ありません。

投稿者 taku : 23:37 | コメント (1) | トラックバック

2006年03月18日

MeCab: 制約つき解析を実装してみた

実装しようと思って先延ばしにしていた制約付き解析を実装してみました。制約付き解析とは部分解析とも呼ばれ、部分的に正解がわかっているときに、それを制約として解析する機能のことを言います。これが実現できると

- 絶対に間違ってはいけない定型部分を制約として解析
- 形態素解析のマルコフ的なモデルでは解消できないあいまい性を高次の処理で解消しフィードバック
- 固有表現抽出の前処理
- 人間とのインタラクション
- かな漢字変換への応用 (ユーザの修正を反映して再解析)

などといったことができます。

さて、ChaSen 2.4.0 ではすでに実装されています。 MeCab もほぼそれを踏襲しました。

基本的には、MeCab のデフォルトの出力結果をいじって制約を記述するという格好になります。

- 品詞の部分に * が指定されると、その単語で切り出し、品詞は適当に最適なものを付与します。

にわ    *
に      *
はにわ  *
にわとり        *
が      *
いる    *
EOS

- 品詞そのものを指定することができます。( "*" はワイルドカード)

にわ  *
に      助詞
はにわ  *
にわとり        *
が      接続詞
いる    *,非自立
EOS

- 品詞のカラムを指定しないと、そのトークンは文断片となり、制約がないときと同じように解析されます。ただし、文断片をまたぐような形態素は出力されません。

にわ
に 
はにわにわとり
がいる
EOS

まだバグがあると思いますが、cvs にはコミットしてみました。もうちょっとテストして公開したいと思います。

投稿者 taku : 01:38 | コメント (6) | トラックバック

2006年03月07日

Thinkpad と無線LAN ユーテリィティー

Thinkpad X60s を購入しました。今まで使っていた Let's note R4を手放すことになったので、先月くらいから何を買おうか考えていたのですが、最後まで T4 と悩んだあげく X60s に決まりました。バッテリの持ちは T4 に比べれば比較にならないほど短いですが、メモリが2GBまで積めるのと、なんといても Core Duo というのが最大の魅力です。指紋認証も使ってみるとなかなか便利です。

さて、Thinkpad にはいわゆるバンドルソフトの類はほとんど付属していません。ただし、レノボ製の
Thinkpad ユティリティーがインストールされています。が、何のツールなのかまったくわからないのです。

- EasyEject ユーティリティー
- バックグラウンドプログラムマネージャー
- プレゼンテーションディレクター
- プロダクティビティーセンター
- System Migration Assistant
- Rescure and Recovery
- Access Connections
... などなど

いったい何のことやらさっぱりわかりません。IBM らしいといえばそれまでなんですが、ユーザへの配慮に欠けています。

あと、無線 LAN。 Thinkpad は独自の無線 LAN ユーティリティーを使う必要があります。確かにアクセスポイントの強度や方向を図示してくれて使いやすいとは思うのですが、XP のインタフェイスに慣れてしまった私には、ありがた迷惑です。どういうメリットがあるのかもいまいちピントきません。さらに、認証方法を自分で指定しないといけないのにはかなりガックリしました。初心者は使いこなせるのでしょうか?

そこで、強引にこの機能を切って XP のインタフェイスを使うようにしてみました。

1 スタート → ファイル名を指定して実行 → msconfig
2. スタートアップのタグを開く
3. ACTray と ACWLIcon を無効にして再起動
4. ワイヤレス接続ネットワークのプロパティで
「Windows でワイヤレスネットワークの設定を構成する」をチェック

これで Thinkpad のツールを無効にして XP の機能を使うことができました。

投稿者 taku : 21:51 | トラックバック