Não Aqui!

ロジスティック回帰やCRFなどの対数線形モデルの学習でよく出てくるのが，expの計算です．これをSSE2を使って高速化するのが，今回のテーマです．まずは，背景の理論を説明します．

まず，指数関数を２の指数関数に変換することを考えます（なぜ２の指数関数かはいずれ分かります）．

両辺の自然対数をとり，について解くと，．IEEE754など，２を基数とした指数部を採用している浮動小数点形式では，整数に対してを容易に構築できるので，上式の実数解の代わりに整数， を用い，の大まかな値を計算することを考えます．ただし，はを超えない最大の整数を表します．

さて，をで近似したときの誤差の範囲は，．誤差にを乗じたものを，と定義すると，

上式の両辺の指数をとると，

ここで，はを超えない最大の整数なので，の値域は，．

これらのことから，は以下のステップで計算出来ることが分かります．

1. を計算する．
2. を計算する．
3. を定義域において，テーラー展開もしくは最良近似多項式などで近似計算する．
4. 浮動小数点形式を利用してを構築し，との積を計算する．

ステップ1は簡単そうに見えますが，負の数を整数にキャストすると，0に近づいてしまうことに注意が必要です．つまり，doubleからintへのキャストは，正の値は切り下げ，負の値は切り上げになってしまいます．このことに注意すると，このステップは次のように書けます（a < 0で，ifによる分岐を作らないのが賢いやり方）．

a = LOG2E * x;
a -= (a < 0);
n = (int)a;

ステップ２はそのまま書けばOKです．

ステップ３では，を多項式に近似します．多項式近似というとテーラー展開が一般的ですが，「･･･点の周りについてテーラー展開すると」という表現の通り，ある点の近傍の近似は良いのですが，そこから離れた点では近似精度があんまりよくないという欠点があります．Cephesというライブラリでは，パデ近似（Padé approximant）を採用していますが，除算を１回だけ行う必要があります．最近のCPUは速くなったとはいえ，SSE2で倍精度のパック除算（DIVPD）をやるのに必要なレイテンシ・スループットは，70・70で，倍精度のパック乗算（MULPD）の7・6と比べると，除算が圧倒的に遅いことになります．そこで，今回は最良近似式を用います．なにやら難しそうに見えますが，Sollya というソフトウェアを使えば，簡単に最良多項式が求まります．以下の例では，の範囲で，５次の最良多項式を求めています．

> remez(exp(x), 5, [0, log(2)]);
0.99999989311082729779536722205742989232069120354073 + x *
(1.00001092396453942157124178508842412412025643386873 + x *
(0.49981934577169208735732248650232562589934399402426 + x *
(0.16775408658617866431779970932853611481292418818223 + x *
(3.87412011356070379615759057344100690905653320886699e-2 + x *
1.185268231308989403584147407056378360798378534739e-2))))

多項式がホーナー形式（horner scheme）で出てくるので，至れり尽くせりです．これをそのままC言語に書き直せば，ステップ３の実装は完了です．

y = 1.185268231308989403584147407056378360798378534739e-2;
y *= b;
y += 3.87412011356070379615759057344100690905653320886699e-2;
y *= b;
y += 0.16775408658617866431779970932853611481292418818223;
y *= b;
y += 0.49981934577169208735732248650232562589934399402426;
y *= b;
y += 1.00001092396453942157124178508842412412025643386873;
y *= b;
y += 0.99999989311082729779536722205742989232069120354073;

最後のステップ４ですが，もちろんpow(2, n)なんてやってしまったら，せっかくの高速化が台無しです．浮動小数点形式IEEE754では，２を基数として指数部が構成されているので，はちょっとした工夫で一瞬で作れます．あんまり移植性がないコードですが，は次のように作ります．

typedef union {
    double d;
    unsigned short s[4];
} ieee754;

ieee754 u;
u.d = 0;
u.s[3] = (unsigned short)(((n + 1023) << 4) & 0x7FF0);

こうすると，u.dでの値にアクセスできます．なぜそうなるかは，IEEE754の仕様と睨めっこすればすぐに分かると思います．あとは，u.dとyの積を計算すれば，の計算が出来たことになります．

昨日撮れた奇跡の一枚．最近急激にかわいくなってる気が･･･．

娘は順調に育っています．特訓（!?）の甲斐あって，首座りと寝返りを３ヶ月でほぼ同時にマスターしました．寝返りは仰向け→うつぶせ方向が得意で，逆はまだ苦手．日中は「仰向け→寝返り→うつぶせ→疲れて泣く→仰向けに戻してやる→懲りずに寝返り」を，ずぅっと繰り返しています．

SimStringという類似文字列検索ライブラリをBSDライセンスでリリースしました．類似文字列検索とは，文字列集合（データベース）の中から，クエリ文字列と似ているものを見つけ出す処理です．コンピュータは，正確に一致する文字列を探すのは得意ですが，表記揺れに出くわすと，途端に対応できなくなります．例えば，「スパゲティ」に対して，レストラン情報などを返すサービスにおいて，「スパゲッティ」や「スパゲティー」などの表記揺れが検索クエリに与えられると，通常のデータベースでは情報を提示することが出来ません．類似文字列検索を用いると，表記揺れが検索クエリに与えられても，「スパゲティ」という既知語を代替クエリとして提案したり，「スパゲティ」の情報をダイレクトに引き出すことができるようになります．

似てる語を探す技術って，文字列処理の基本中の基本で，自然言語処理では当たり前のように使われていてもおかしくないと思うのですが，研究ではほとんど見かけません．２つの文字列が与えられたときに，似てるか似てないかの識別する研究は，色々あるのですが，ある文字列が与えられたときに，どの文字列が近いかを高速に収集する方法は，あまり見かけません．検索エンジンを提供している会社では，検索クエリログに基づくクエリ訂正などを行っていますが，検索クエリログは誰でも入手できるわけではありません．類似文字列検索は，データベースやデータマイニングの分野で盛んに研究がされていますが，単語や用語レベルの文字列が簡単に扱えるツールが見つからなかったので，自分で作ってみました．

SimStringは，「文字列集合の中で，検索文字列との類似度がある閾値以上のものをすべて返す」という処理を高速に行えるように設計されています．類似度関数としては，コサイン係数，ジャッカード係数，ダイス係数，オーバーラップ係数をサポートしています．類似度を計算するときの文字列の特徴として，文字Nグラムを採用しています．

例えば，3グラム（N=3）を用いたとき，「スパゲティ」は「＄＄ス」「＄スパ」「スパゲ」「パゲテ」「ゲティ」「ティ＄」「ィ＄＄」と表現されます．このとき，文字列の先頭と末尾を表す特殊な記号「＄」が挿入されていますが，これを用いるか用いないかはカスタマイズ可能です（デフォルトでは用いないことになっている）．また，Nグラムの単位（すなわちNの値）も，自由に設定できます．また，日本語などのマルチバイト文字でも正確にNグラムが計算できるように，ユニコードをサポートしています．

SimStringは，類似文字列検索を正確に，かつ高速に行えるように設計されています．Google Web 1Tコーパス の英単語（13,588,391文字列）から，コサイン類似度が0.7以上の文字列を検索するのに必要な時間は，１クエリあたり平均 1.10 [ms] 程度です．

実装はC++で，ヘッダファイルをインクルードするだけで他のアプリケーションに組み込めるようになっています．また，PythonとRubyのSimStringモジュールも，ビルドできるようになっています．他言語のモジュールはSWIGを用いてラッパを自動生成しているので，Perlなどの言語にも対応できるはずです（ビルド報告，サンプルプログラムなど歓迎致します）．Pythonで類似文字列が一瞬で検索出来るなんて，楽しい世界が広がると思いませんか？

$ python
Python 2.5.1 (r251:54863, Oct 15 2007, 23:38:19)
[GCC 3.4.6 20060404 (Red Hat 3.4.6-8)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import simstring
>>> db = simstring.reader('web1tuni/web1tuni.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.9
>>> db.retrieve('approximate')
('approximat', 'pproximate', 'approximate', 'approximated', 'approximatel',
'approximates', 'approximatey', 'anapproximate', 'approximatelt', 'approxima
tely', 'reapproximate', 'toapproximate')
>>> db = simstring.reader('web1tja/unigrams.db')
>>> db.measure = simstring.cosine
>>> db.threshold = 0.7
>>> print(' '.join(db.retrieve('スパゲッティー')))
スパゲッティ スパゲッテー スパゲティー スパッティー スパゲッティー スパゲッ
ティーニ スパゲッティー・ スパッゲッティー スパゲッティーニ・ ・・スパゲッテ
ィー スープスパゲッティー スパゲッティーモンスター
>>>

いろんなクエリを入れながら遊んでいるだけで，研究ネタが浮かんできそうです．この例では，単にコサイン類似度で類似文字列を検索しているだけなので，表記揺れ，語尾変化，派生語，その他別の概念を指すものが混ざって獲得されます．ここからルールや機械学習を用いて，所望の語を選別するのは，別タスクになります．

アルゴリズムの詳細については，今週東大で開催される情報処理学会の全国大会で発表する予定です．学会初日の朝一番の発表（1C-1）ですが，興味のある方は，是非遊びに来て下さい．

先週まで論文執筆モードだったので，ご報告が遅れましたが，娘の名前は心優（みゆ）にしました．この名前を聞いて「当て字っぽくて読めねー」と感じるか，「ありがちな名前」と感じるかで，最近の子供の名前に対する精通度が分かります．人気の名前はあまり付けたくなかったのですが，2009年の名前のランキングに普通に出てきます．文字通り「心優しい」ですが，「優」を漢語林で引くと，「上品で美しい」「みやびやか」「おだやか」「しとやか」「情深い」「のびやか」「ゆるやか」など，女の子にはうってつけの多義が並べられています．

名前を決めるのは本当に大変でした．考えれば考えるほど，自分の探索空間が足りているのか不安になりました．結局は，コンピュータが生成した6,084個（読みで数えた数）の名前の候補から，私と嫁で一つ一つチェックしながら結論を出しました．

名前の候補を生成する流れは，次の通りです．

1. 名前辞典などを見ながら，名前に使いたい漢字とその読みを入力する
2. 姓名判断に基づき，よい名前の画数の組み合わせを調べ，入力する
3. 名前はひらがなの読みにして３文字以内，漢字では２文字もしくは３文字として，可能な名前の候補（漢字と読み）を全列挙する
4. Google Nグラムコーパスを使って，名前の漢字と読みの頻度が閾値以下のものは刈る．

１はひたすら本を見ながら入力する作業です．日本語の名前には，漢字の読みをほぼ無尽蔵に作り出せる「名乗り」という特徴があります．例えば，「美」という字の音読みは「ビ」，訓読みは「うつく-しい」ですが，「美咲」「美結」など，名前の中では何の違和感もなく「み」と読めます．これは，「み」という名乗りが，一般的に知れ渡っているからです．

IMEの辞書データなど，名乗りを収録していそうな電子データを探したのですが，見つからなかったので，自分で入力することにしました．自分が使いたい漢字だけ読みを入力すればよいし，そもそも名前に使える漢字は常用漢字と人名用漢字の2930字が上限なので，普段の研究で正解コーパスを作る作業よりは，はるかに楽でした．後の処理が楽になるよう，画数毎に入力しておきます．こんな感じです．

[3]
弓	きゅう　ゆみ　み　ゆ
才	さい　さ　た　たえ　とし
子	し　す　こ　ず　たか　ちか　とし　ね
女	じょ　にょ　にょう　おんな　め　こ　たか　よし
小	しょう　ちいさい　こ　お　さ　ささ
夕	せき　ゆう　ゆ
千	せん　ち　かず　ゆき
万	まん　ばん　よろず　かず　かつ　たか　つむ　ま

[4]
月	つき　げつ　がつ　つき　つぎ　づき
元	げん　がん　もと　あさ　ちか　はる　まさ　ゆき　よし
心	しん　こころ　きよ　ここ　さね　なか　み　むね　もと
仁	じん　に　きみ　さと　と　ひと　み　めぐみ　よし
日	にち　じつ　ひ　か　あき　はる　ひる
文	ぶん　もん　ふみ　あや　いと　とも　のり　み　や
友	ゆう　とも　すけ　ゆ

２は，姓名判断により，名前の１文字目及び２文字目を何画にすればよいか求めます．簡単な数式があるのですが，さしあたって自分の苗字に対してだけ機能すればよいので，本や参考資料を元に，可能な画数の組み合わせを入力し，制約条件としました．いろいろな流派や，旧字体を使うか新字体を使うかという問題があるのですが，一般的なものに準拠するようにしました．画数はそれほど重視していないのですが，可能な画数の組み合わせは結構あるので，この画数の組み合わせの中から名前の読みと漢字を生成することにしました．日本人の名前の漢字の分布が，姓名判断によってどのくらい偏っているのか調べると，楽しそうだと思いました．

３は，スクリプトを書いて総当たりに生成するだけです．４により，Google Nグラムコーパスに出現しない名前の読みや，漢字の組み合わせを削除すると，6,084個の候補が生成されました．この中で，女の子の名前としてふさわしくないものを手作業で削除すると，名前の候補は485個まで減りました．この作業も，日頃の研究からするとずいぶん楽な作業なのですが，女の子の名前らしさを表現するfeatureは何なのか，考えさせられる作業でした．読みにしたときに最後に来るひらがなには，かなりパターン化されている感じがしました．

あとは，一つ一つじっくり見ながら検討する段階に入ります．コンピュータが生成した名前を見ていると，「万桜（まお）」「才華（さいか）」「智咲（ちさ）」など，思いもつかなかったものがいくつかあって，感心させられました．

全部コンピュータが作ったような話になっていますが，実際には名前の候補を最初にある程度選んでありました．他の名前候補をコンピュータで探そうとしたものの，最初のインスピレーションが最後まで勝ってしまったというオチでした．やはり，名前で大切なのは読みの雰囲気で，最終的には人間の感性ですね．

CRFsuite 0.10をリリースしました．修正点は，以下の２点です．

• タガー使用時にメモリリークがある問題を修正．この問題を修正するパッチは，株式会社高電社の真鍋宏史様から頂きました．（どうもありがとうございました）
• タガーに-r (–reference) オプションを追加．このオプションは，入力データがラベル付きであると仮定し，各行に正解のラベルと予測されたラベルをタブ区切り形式で並べて出力します．

CRFsuiteのライブラリ・インタフェースは，タガーと学習器を分離しようと計画中です．タグ付けするだけなのにL-BFGSのライブラリとリンクするのは無駄だと思うので．現在，CRFsuiteを使ったあるソフトウェアを準備中で，カンファレンスシーズンが終わってそちらの開発が進めば，CRFsuiteのインタフェースに手を加えると思います．

タガーに新しく追加した-rオプションは，conlleval.plを簡単に使えるようにするためのものです．が，conlleval.plは正解のラベルの前に，何かのトークンがないと，大量のワーニングを吐き出すようです．仕方がないので，CRFsuite tag -rの出力に，

import sys

for line in sys.stdin:
    line = line.strip('\n')
    if line:
        sys.stdout.write('a\t%s\n' % line)
    else:
        sys.stdout.write('\n')

という，タグ付け結果の先頭に”a”を追加するアホなフィルタを通してからconlleval.plを使っています．conlleval.plを直すのがスジだと思いますが，Perlは読み書きが全くできないので…．

libLBFGS 1.9をリリースしました．すごく些細なミスの修正なので，最適化問題への影響はほぼ皆無かと思います．ミスの内容は，”ftol”と”wolfe”というパラメータが間違って指定されているかどうかをチェックするコードが間違っていたというものです．

この問題はKevin S. Van Hornさんに指摘していただきました．よっぽどlibLBFGSを使い込んでいたか，コードをじっくり読んで頂いたんですね．コンパイラが自動的に発見したという可能性も捨てきれませんが・・・．

意味深なタイトルですが，娘が生まれました．体重は2895グラムと，やや軽めですが，正期産の中では早め（38週）なので，だいたい平均くらいのようです．身長は45.7cmで，平均よりは小さめでした．母子共に無事に生まれてきてくれて，ほっとしています．

赤ちゃんはとにかく元気で，ご機嫌斜めになると，「ギャー」という叫び声を上げ，手を付けられないくらいにキレます．病院では自己主張の強い赤ちゃんと言われているようです．まだあんまり外界が見えないためか，起きていてもそんなに目をぱっちり開けてくれません．なので，あんまりかわいい写真が撮れません．女の子なので，目力をもう少しつけさせたいところです．

先週末から，娘の顔を見に病院に行くのが楽しみな日々になりました．自分の中でコンピュータを超える優先順位のものはないと思ってましたが，子供が生まれると，たやすく最優先が塗り替えられるのですね．

昨年の話になりますが，Classias 1.1をリリースしました．ほとんどは，classias-tagのバグ修正，新しい機能の追加，使い勝手の改善が主です．

classias-tagには，失敗解析オプション（-f）を追加しました．失敗解析といっても，高度なことをやってくれるわけではなく，ラベル付け時に正解と食い違う事例のみを出力する機能です．classias-tagには，データ中のコメント行（#から始まる行）をそのままスルーして出力するオプション（-k）があるので，各事例を識別するような文字列をコメント行に入れておけば，どの事例で予測が失敗するのか調べることができます．

多クラス分類，もしくは候補選択ですべてのラベル付け候補に関する情報を出力するオプション（-a）を追加しました．ひとつの事例に対して，@boiと@eoiという行の間に，各候補がラベルとして予測されたかどうか（+もしくは-）が出力されます．タグ付けのスコアや確率を付与するオプション（-sもしくは-p）と併用すると，各ラベル候補がどのくらいの確信度だったのか確認することができます．

また，与えられていたデータに含まれていた正解ラベルをそのまま出力するオプション（-r）を追加しました．このオプションを使用しないと，classias-tagは予測されたラベルしか出力しませんが，-rを有効にすると，同じ行に正解のラベルと予測したラベルを並べて出力します．

[正解のラベル] [予測されたラベル]

正解のラベルと予測されたラベルが並ぶので，ラベル付けの評価（精度などの計算）を行うスクリプトが書きやすくなると思います．

classias-trainでは，候補選択において正しい候補が存在しない事例があるときに，データ読み込みでクラッシュする問題を修正しました．この問題は，東芝の若木さんに指摘していただきました．若木さんは，学習データの中でどの事例でクラッシュするのかを調べるために，二分法でクラッシュを再現しない事例を半分ずつ減らしながら，クラッシュを再現する事例を見つけ出したそうです．すごいです．

次は，新しい学習アルゴリズムをいくつか載せてみたいですが，もう少し先になると思います．

あけましておめでとうございます．

イギリスのラジオを聴いていると，2010年は「新しい10年の幕開け」と表現されるようです．私なんか，「あー，もう2000年ミレニアムから10年経ってしまったか･･･」というネガ印象だったのですが，なるほど，新しい時代の節目と考えると，新鮮な気持ちになります．

実家の猫が腹出して寝ている写真を年賀状にしました．今年もよろしくお願いします．

年賀状2010

私が昔所属していたNaCTeMで公開している，略語辞書サービスAcromineをひっそりと更新しました．以前のバージョンからの変更点は，以下の通りです．

• 2009年版Medlineのアブストラクトで略語抽出をやり直した
• 略語の完全形のクラスタリング方法を改良した
• 略語の完全形の異表記を表示できるインタフェースにするため，辞書検索結果の表示を表形式からツリービューに変更した
• 辞書引きサービスのAPIを，SOAPからREST/JSONに変更した

単に辞書の中身を新しくするだけではつまらないので，ツリービューをウェブブラウザ上で実装するときに，YUI Libraryを初めて使ってみました．ノード・ラベルの遅延ロードを行うツリービューが簡単に実装できて，便利ですね．

辞書引きサービスのAPIを使うには，登録手続きが必要になるようです（残念ながら私のコントロール範囲外）．アカデミックな人たちは問題無く認可されると思いますが，コマーシャルな方は，相談していただければNaCTeMに取り次いでみます．また，手持ちの大量の文書セットに含まれるテキストから略語の定義をマイニングしたいというのも，相談して頂ければ対応できるかと思います．