Não Aqui!

今年のCIKMチュートリアル，Log-linear models and conditional random fieldsのノート．主にロジスティック回帰と条件付き確率場に関して，最尤推定（MLE）や尤度などの基本概念から丁寧に説明しています．

対数線形モデルに詳しい人なら，知っている内容が大半を占めると思います．特徴的なのは，

• L-BFGSによるパラメータ推定が説明されていない
• 代わりに，Stochastic gradient descent (SGD) が説明されている
• Gibbs samplingによる最適パス計算が説明されている
• 正則化に関して全く触れられていない
• 参考文献にBergerやLaffertyの名前が一度も出てこない

上から３つは面白い試みですが，L2正則化はSGDでも簡単にできるので，触れても良かったんじゃないかなぁと思います．

darts-cloneというダブル配列の実装が公開されているのに気づきました．DASTrieで採用しているコンパクトなダブル配列構造を提案されたYata様の作品です．ただ，インタフェースの設計思想はかなり違っていて，DASTrieはstd::mapやstd::setに類似したインタフェース，darts-cloneはDartsに類似したインタフェースになっています．

Web1T unigramでdarts-clone-0.32cをテストしてみると，構築時間が140[sec]くらいで，データベースサイズが223,290,696バイトでした．DASTrieの構築時間（182[sec]）よりも速いので，DASTrieはもう少し高速化の余地がありそうです．DASTrieのデータベースサイズ（131,542,283バイト）よりも大きいのは，HugeDoubleArrayにおける要素サイズが8バイトになっているからだと思います（データベースのサイズ比が0.59で，5/8に近い値になっている）．

また，SVNのバージョン（0.32d）では，構築時間が30[sec]に高速化されています．データベースのサイズが226,293,064バイトに増加していますが，BASE値の検索をやや緩く行う戦略のようです．

このように実装の性能を比較していると，DASTrieの何処を修正すべきなのかはっきりしてくるので，大変有り難いです．ただ，今年度は時間が無さそうなので，更新は来年度に持ち越しになるかもしれません．

CRFsuiteのバージョン0.5をリリースしました．変更点はバグ修正のみです．

• liblbfgsに該当する部分のソースコードを削除し，外部からリンクする仕様に変更した．*NIXな環境でCRFsuiteをビルドするには，liblbfgsを別途ダウンロードし，ビルドもしくはインストールする必要があります．
• L-BFGSの収束判定に関するパラメータ（lbfgs.stopとlbfgs.delta）を追加した．このパラメータは，${lbfgs.stop}回前から現在の反復において，対数尤度の改善率が${lbfgs.delta}を下回った時に，L-BFGSのアルゴリズムを終了させることができます．これらのパラメータのデフォルト値は，lbfgs.stop = 10, lbfgs.delta = 1e-5 です．
• L-BFGSの直線探索のアルゴリズムを指定するパラメータ（lbfgs.linesearch）を追加した．利用可能なアルゴリズムは，”MoreThuente”, “Backtracking”, “LooseBacktracking”で，”MoreThuente”がデフォルトです．
• 訓練データやテストデータにおいて，item:valueの形式をきちんと読みこめていなかったバグを修正
• タグ付け時の精度の計算が一部間違っていた問題を修正
• タグ付け時に，あるアイテムの素性が空（訓練時にその素性が出現しなかった場合を含む）だったときに，そのアイテムを無視してしまい，シーケンスの長さが変わってしまう問題を修正

Static Double Array Trie (DASTrie) という静的ダブル配列のライブラリをリリースしました．ダブル配列の実装はいろいろありますが，このライブラリの特徴を以下に挙げます．

1. C++テンプレートを利用して，std::mapのような連想配列，std::setのような集合を簡単に実装できる．
2. ダブル配列の要素を４バイト，もしくは５バイトで表現し，データベースをコンパクトにする（通常の実装では要素サイズは８バイト）．
3. 最小接頭辞トライを実装し，データベースのサイズをコンパクトにする．

よくあるダブル配列の実装では，レコードのキーとユニークなIDがトライの中に格納され，レコードのデータは配列などで独自に管理する必要があります．DASTrieはC++のテンプレートで，任意のデータ型をレコードとして使い，レコードをトライの中に格納するので，連想配列として簡単に利用できます．もちろん，トライを（レコードの値がない）集合として使うこともできます．

２番目の特徴は，A compact static double-array keeping character codesという論文に記述されているアイディアを実装したものです．通常のダブル配列は，int（４バイト）を要素サイズとして，BASEとCHECKと呼ばれる２つの（同じ要素数の）配列を使います．つまり，BASEとCHECKをまとめて考えると，ダブル配列の要素のサイズは８バイトということになります．この論文で提案されているのは，CHECKにBASE配列へのバックリンク（インデックス）を作るのではなく，ノード遷移に用いられた文字を格納すれば，CHECK配列は１バイトで済むという提案です．ただし，ダブル配列をこのように修正すると，すべてのBASE値は異ならなければならないという制約が付きます．元々の論文では，BASEを３バイト，CHECKを１バイトで表現して，BASEとCHECKをint（４バイト）で表現することを提案しています．ただし，BASEを３バイトで表現すると，格納できるデータのサイズにかなりの制限がかかるので，DASTrieではBASEを４バイト，CHECKを１バイトとして，従来通り大規模なデータが格納できるトライも実装しました．

せっかくなので，Google Web 1TコーパスとUMLS SPECIALIST Lexiconを用いて，パフォーマンスを評価してみました．Google Web 1Tコーパスは，レコードの数が多いので，ダブル配列の要素を５バイトで表現したDASTrieを用いました．実験結果によると，DASTrieのデータベースは，従来のトライの実装と比べて，1/3～2/3くらいのサイズで格納できることが示されました．

Darts: Double-ARray Trie Systemと比べると，DASTrieのデータベース構築時間がかなり長いですが，これはデータベースのサイズを小さくするために犠牲にした部分です．ダブル配列の構築で一番時間がかかるのは，「あるノードの下のすべての子ノードを格納できるBASE値を探す」という処理です．これは，あるノードのすべての子ノード集合を「クロスワードパズルのピース」のようなもので表現し，そのピースがぴったりはまる「未使用箇所」を，ダブル配列の先頭から探すという操作になります．ダブル配列が断片化されていないときは，格納可能場所を速く見つけることができますが，ダブル配列が断片化されてくると，ぴったりはまる箇所を見つけるのが大変になります．Dartsは，最小接頭辞トライとして実装されていないので，子を一つしか持たないノードを大量に格納し，断片化されたダブル配列の隙間を埋めことができます．また，Dartsはダブル配列の断片化の度合いを計測し，ある程度断片化されたら，その領域を諦め，今後使用しないようにするというヒューリスティックが実装されています．Dartsのデータベースサイズが大きいのはこのためで，速さと引き替えにデータベースサイズが大きくなります．DASTrieは，ダブル配列の空きスペースをできるだけ減らすように頑張るので，Google Web 1Tコーパスのような分枝数が大きいレコードを格納しようとすると，時間がかかります．

DASTrieはダブル配列の実装の中では，かなり頑張っているのですが，Level-Order Unary Degree Sequence (LOUDS) を実装した Tx: Succinct Trie Data structure には，データベースサイズで大きく水をあけられています．Txはすごいですね．ダブル配列は，この辺が限界なのかなぁと思っています．

libLBFGS 1.6をリリースしました．変更点は以下の通りです．

• 今道様より頂いた，backtrackingアルゴリズムにおいて，strong Wolfe conditionを満たすようにステップ幅を決定する実装を取り込みました．これにより，サンプルプログラムにおいてbacktrackingアルゴリズムを使っても，途中でコケることなく，最小化が行えるようになりました（すばらしい！）．なお，この実装を頂いたのは，だいぶ前のことになるのですが，私がサボっていたためにリリースがかなり遅れました．今道さま，どうもありがとうございました．
• OW-LQNを適用する変数の範囲を，lbfgs_parameter_t::orthantwise_start と lbfgs_parameter_t::orthantwise_end で設定できるようにしました（以前はorthantwise_startだけでした）．
• C++のサンプルプログラムが欲しいという人がいるので，配布パッケージに同封しました．C++のクラスの中からlbfgs関数を呼び出すときは，lbfgs関数のinstanceパラメータの使い方，staticメンバ関数を経由したコールバックの実装など，ちょっと経験が必要かも知れませんね．

また忙しい時期に突入していくので，今のうちにソフトウェアをリリースしておかねば…．

以前の日記にちょこっと書いたEMNLPですが，結果はポスターでした．レビューがなぜか４つ付いていたという話をしましたが，oral or posterの振り分けに使われたようです．ちなみに，ディフェンスしてもrecommendationは全く変化しませんでした．基本的にはレビューアーの意見に激しく同意という書き方でレスポンスしたので（よわ）…．

こちらの論文は略語の話ではなく，動詞の活用語尾，動詞から名詞への派生，綴りのバリエーションなど，語レベルで文字が変化する過程を，辞書から機械学習を用いて自動獲得する話です．今年の人工知能学会で発表した内容がベースになっていて，詳細なアルゴリズムや欠けていた実験を追加したものになっています．手法自体は汎用的であるものの，かなり細かいテーマを扱っているので，イントロダクションから細かい議論に持ち込み，手法の有用性や必然性が伝わるように工夫しました．締切直前は，学生がAMTAに書いていた論文の手直しをしていて，溜まったフラストレーションをこの論文を書いて発散していました．

カメラレディに必要な実験を追加したり，実際のシステムを作成して公開するなど，今後も継続して育てていこうと思っています．

といっても，帰国したのは２日前ですが．週末には登山があるので，何とか早く時差を直したいけど，この時間になかなか眠たくならず．

Coling 2008での自分での発表は，「識別的アライメントモデルを用いた略語抽出」というタイトルで，略語の定義の抽出というタスクを，機械翻訳で研究されてきたアライメント問題として定式化するというものです．略語定義の抽出タスクを，機械学習に基づいた自然なアプローチで解いてみました．個人的には，略語抽出の決定版と位置付けていて，今後軽微な修正や改良が必要かも知れませんが，英語の略語抽出はこの研究で十分だと考えています．

以下のような例文を考えます．

We evaluated the effect of thyriod transcription factor 1 (TTF-1).

英語の略語抽出では，もっぱら，括弧表現の内側に略語，括弧表現の外側に定義があると仮定するのが主流です．逆の（括弧表現の内側に定義が来る）ケースや，括弧表現以外で略語が定義されるケースもありますが，ちゃんとした文書を扱っている分には，無視できるくらい少ないことが分かっています．さて，括弧表現TTF-1が略語であるかどうかは，その前の表現に `T’, `T’, `F’, `1′ の起源となる文字があるかどうかで決まります．人間は，

• `T’: thriodの語頭の文字`t’に基づく
• `T’: transcriptionの語頭の文字`t’に基づく
• `F’: factorの語頭の文字`f’に基づく
• `1′: 1の文字`1′に基づく

という，略語の起源に関する情報をたちどころに認識できます．この略語の起源の関係を，略語の文字 y と定義の文字 x の間のアライメント a であると捉え，条件付き確率 P(a|x,y) を最大エントロピー法で近似し，なんとかコンピュータに分からせようというのが研究のアイディアです．日本語で書かれた詳細は，言語処理学会の年次大会の論文を参照してください．

発表後にたくさん質問して頂けたのは嬉しい限りでしたが，質問者の意図をくみ取ることができなかった質問が一つあったり，もっと良い応答をすべき質問があって，悔いが残りました．ただ，質問の英語そのものは，ほぼ100%聞き取れていたので，質問者ときちんとディスカッションをする能力を身につけるのが，今後の課題です．

日本の方から，「アライメントの経路の列挙にDPを使っているのかどうか」質問をされました．ある文が与えられた時，その略語アライメントの候補は高々100程度であることが実験的に分かっているので，DPなどは使っていないというのが私の回答でした．「x_i に略語文字 y_j が割り当て可能であるためには，x_i-1, x_i-2, …, x₁ において y_j を割り当てていないことが必要」というヒストリ依存の問題があって，通常のsum-productやmax-productのアルゴリズムでは難しく，constrainted inferencingが必要になります．略語抽出アライメントの場合は，略語候補の枝狩りがかなりできてしまうので，constrainted inferencingをしなくても，十分であるというのが，もっとマシな答えになります．

帰りの飛行機でこの質問のことを考えていたら，現状の実装の問題点に気付きました．現状の実装では，入力文に対する可能なアライメントにおけるすべての素性を書き出して，学習器に渡しています．ところが，複数のアライメントが共通に含むノードやエッジがたくさんあるはずなので，この実装方法は無駄だらけです．すなわち，ノードIDとそのノードにおけるすべての素性，エッジIDとそのエッジにおけるすべての素性を書き出しておき，各アライメントはノードIDとエッジIDの参照リストで構成しておく方が，同じノードやエッジに関与する素性のスコア計算を無駄に繰り返すことがなくなり，学習・タグ付けの両方が速くなるはずです．論文に書けないくらい軽微な工夫なのですが，なんで気付かなかったのか…．

そろそろ寝てみます．

午前３時（日本時間午前11時）起床．なかなか良い起床時間だが，これ以上遅くならないように注意しよう．

パスポートにUKのエントリークリアランスが貼りっぱなしなので，入国審査でなぜ来たのかしつこく質問される．渡航目的を「sightseeing」と言ったら，「Did you live in UK before?」とか「Are you going to work in UK?」「Are you familiar with Manchester?」「What kind of sightseeing?」など，質問責めに遭う．まぁ向こうが怪しむのは当然なので，適当に答えて入国．

空港からManchester Piccadillyに向かう電車の中で，野生のうさぎときつねを見かける．Northern Railのディーゼル車の轟音と共に，懐かしい気持ちに浸る．マンチェスターの市内は，以前とあんまり変わっていない．金曜の夕方はパブでビールを飲んでいる人たちが楽しそうだった．

土曜日はCoNLLの初日に出かける．Regina Barzilayの招待講演，”Climbing the Tower of Babel: Advances in unsupervised multilingual learning” を興味深く聞く．２言語の並列コーパスからGIZA++でアライメントを取り，両方の言語における２つのHMMを１つに統合したモデルを作り，ベイズ推定でunsupervised POS taggingを実現する話がメインだった．ただ，並列コーパスもsupervisionの一種なので，「unsupervisedとsupervisedの性能のgapを埋める」という大目標に近づいているかというと，やや疑問が残った．

会場のUniversity Placeは，Manchester Musiumの反対側に出来た新しい建物．そういえば，マンチェスターに住んでいた時は，この辺ずっと工事をしていたなぁと思い出す．この辺は食べるところが少ない（というか知らないだけかも）ので，日本から来た皆さんを引き連れて昼食をどこにするか困ったが，無難なところでBBC近くのKROバーにした．マンチェスターにしては美味しくて，個人的には感心したが，他の人は高く（£9）て，味が微妙と思ったに違いない．時間があればChineseやThaiを食べに行きたいのだが･･･．

私が宿泊しているホテルから会場に行くにはPiccadilly Gardensからバスに乗るのが一番早いので，Stagecoachのウェブサイトを調べ，MagicriderというMagic Busの142, 143, 145が一週間£5で乗り放題のチケットを購入することにした．

libLBFGS 1.5をリリースしました．変更点は以下の通りです．

• OW-LQN法を使うときに，変数の中でノルムの計算に用いるものと，用いないものを区別出来るようにした．具体的には，lbfgs_parameter_t::orthantwise_startというパラメータで変数のインデックス番号を指定できるようにして，このインデックス番号よりも前の変数はL1ノルムの計算から除外し，このインデックス番号以降の変数はL1ノルムの計算に用います．つまり，orthantwise_start = 1ならば，x0はL1ノルムの計算から除外され，x1, …, xNの変数のみでL1ノルムの計算を行うことになります．
• 初期変数がすでに目的関数を最小化しているとき（すなわち勾配が0になっているとき），ゼロ除算などで変なことが発生するので，L-BFGSの反復計算を行う前に，勾配をチェックするようにした．
• LBFGS_SUCCESSという変数を0のシノニムとして定義した．
• void*からのキャストを忘れている箇所を修正した

最初の変更点は，ロジスティック回帰を行うときに，バイアス項は正則化しない方が良いので，追加した機能です．これについては，岡野原氏のブログエントリやBishop本に書かれています．つまり，x0をバイアス項として，orthantwise_start = 1を設定すればOKです．ちなみに，L2正則化に関してはL-BFGSは何も面倒を見ていないので，目的関数や勾配の計算を自由に変えてください．

２番目の変更点は，以前からバグ報告をしていただいている今道様よりご指摘があった問題の修正です．自然言語処理などのアプリケーションではかなり希なケースですが，せっかくminimizerをL-BFGSに入れているのに，正常な動作をしないのはマズいですね．

それ以外の変更点は，かなり軽微です．

みんないろいろ頑張ってるなー，と感心する全国大会でした．あと，最近よく言われていることですが，言語処理をもっと世の中にアピールしないとイカンと実感しました．面白い研究をして来年も高松に行きたいですね．

久々に会う人が多かったためか，学会後の夜は毎日飲み歩いていました．３ハシゴや４ハシゴを続けていたので，お腹の脂肪が増加したのが自分でも分かります．印象に残ったお店は，成吉思汗 大黒屋，炭やで，どちらも安くておいしいお店でした．炭やは大宮にも支店があるようなので，週末にでも早速煙に巻かれてこようと思っています．