認知科学会サマースクールで登壇しました

2015/08/31に、箱根湯本富士屋ホテルで開催された、認知科学会のサマースクールで登壇しました。 内容は最近の自然言語処理関連の、深層学習に関するまとめです。 単語、文法、知識の3つのテーマに対して、埋め込みベクトル、構造の学習（recurrentとrecursive）、知識ベースの学習の3つに分けて話しました。 この1年位で作ったslideのまとめみたいな感じになっています。

言語と知識の深層学習@認知科学会サマースクール from Yuya Unno

日本語で読める自然言語処理のチュートリアルスライドまとめ

先日、自然言語処理の講演などをしていたときに、そもそも私なんかが話すよりも公開されているチュートリアルスライドを集めたほうが有用なんではないかと思い立って、これから自然言語処理を学びたい人や、ちょっと新しい分野を知りたい人向けに、日本語で読めるチュートリアルスライドを分野別にまとめてみました。 主に、学会のチュートリアルや招待講演、それから研究者の方のWebページなどを参照しながら作りました。 自然言語処理全般系の資料や、少し境界的なテーマは入っていません。 また、ぱっと読めるスライドだけにしています。 幾つか手前味噌な資料も載せてます・・。

頑張って集めてみましたが、思ったほど集まりませんでした。 作っていてわかったのですが、意外とスライドを公開している人は少ないようです。 埋もれてしまうのはもったいないですね。 いずれ、英語で読めるスライドを集めてみようと思います。 そっちはそっちで、数が多すぎて大変そう。

自然言語処理と最適化

さて言語処理学会の年次大会で気になった発表などについて書いてみます。 といっても、個別の発表にというよりは全体感です。 今年気になったのは、最適化について少し考えなおしたほうがいいのかなということでした。

言語処理学会年次大会に参加しました

先週1週間、3/16から21まで、京都大学で行われた言語処理学会の年次大会に参加しました。 参加者が確か800人くらい？、発表件数270件以上と、年々増えているようです。 他の業界の規模を知らないのですが、情報処理の中の1つの分野でこれだけ集まるというのは多い方なのでしょうか。

EMNLP2014読み会で単語の表現学習と語義曖昧性解消を同時に解く論文を紹介しました

先週の土曜日にPFIで行ったEMNLP2014読み会で、Skip-gramモデル（word2vec）と語義曖昧性解消を同時に解く論文の紹介をしました。 発表スライドはこちら。 単語の表現学習と語義曖昧性解消を同時に解く話は、もう一つ論文がありましたが、なんだかいまいちだったのでこちらになりました。

EMNLP2014読み会 "Efficient Non-parametric Estimation of Multiple Embeddings per Word in Vector Space" from Yuya Unno

PFIセミナーで生成語彙論についてDeep Learningの文脈で話をしました

先週のPFIセミナーで生成語彙論とDeep Learning（特に表現学習の領域）の関係について、思っていることを話しました。前半は生成語彙論の入門的な内容で、数式もなくてだれでも読めるような内容になっていると思います。生成語彙論の勉強を始めたのが最近なので、入門という程の内容にもなってないですが、こうした言語学の知見をもう一度紐解くと面白いかもしれません。

表現学習時代の生成語彙論ことはじめ from Yuya Unno

AdaGradが12倍速くなる魔法

AdaGradは学習率を自動調整してくれる勾配法の亜種で、いろんな人が絶賛しています。 勾配を足し込む時に、各次元ごとに今までの勾配の2乗和をとっておいて、その平方根で割ってあげるだけと、恐ろしくシンプルです。

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization
John Duchi, Elad Hazan, Yoram Singer. JMLR 2011.

丁度、 @echizen_tm さんがブログを書いてました。

AdaGrad+RDAを実装しました。

通常のSGDなどは学習率をだんだん減衰させながら勾配を足していくわけですが、どの様に減衰させるかという問題にいつも頭を悩ませます。 AdaGradでは最初の学習率こそ外から与えますが、減衰のさせ方や減衰率といったハイパーパラメータから開放されます。 今日の話は、そんなAdaGradがちょっとの工夫で12倍速になった話です。

今、人工知能研究で何が起こっているのか

半年前くらいに書いた草稿が、投稿されずに残ってたのでちゃんと書きました。 最近、人工知能という言葉がまた流行しているような印象を受けます。 ブームということの本質は2つ有ると思っています。 1つは学術会で、最近良い成果が立て続けに出てきたという側面です。 もう一つは、それに呼応して大きな会社、特にIBMやGoogle、Facebookといった大きなコンピュータ系、インターネット関連企業が力を入れていることが大々的に報道されたことです。 両者はもちろん関係していて、いくつか技術的ブレークスルーがあって、それが企業の投資を呼んでいる、それと呼応するように学術的な成果が企業からでているという、正のスパイラルが生まれている様に見えます。 こうした流れをいち早くとらえた新書として、「クラウドからAIへ」という本があったので読んでみたのですが、一般のビジネスマンを意識して、歴史、現在、未来について大局的に捉えてあってなかなか良かったです。

クラウドからＡＩへ 小林 雅一 朝日新聞出版 2013-07-30 売り上げランキング : 285 Amazonで詳しく見る by G-Tools

技術者の視点で、今どうなってきていると考えているか、自分の考えを整理してみます。

NLP若手の会で発表しました

会社のブログにも書いたのですが、9/21, 22にNAISTで開催されたNLP若手の会シンポジウムで発表してきました。私は幸運にも最優秀奨励賞をいただきました。投票してくださった皆様どうもありがとうございます。発表資料はこちら。

N-gram統計量からの係り受け情報の復元 (YANS2011)

View more presentations from Yuya Unno

さて、ちょっと裏話でも書きます。もともと発表する気（も時間も）はなかったのですが、プログラム委員ということでどちらにしろ奈良に行くのと（これは後に案外みんな来てないことがわかった）、最近開発＆案件続きでちょっと研究もやりたいねということで、急遽発表ネタを捻出することになりました。特に検索クオリティを上げるような面白いネタはないだろうか。以前から確率的単語分割で検索品質を上げるという話があったのですが、これを確率的構文解析に適用したら・・・。単語境界情報のみだと、スキップのある部分文字列検索に自然な適応ができません。係り受け関係というのは、ある意味こうしたスキップのある構造に対する答えの気がしてきます。長い複合語などの検索がやりやすくなるのでは。そういう風な議論から話が始まりました。

発表は、私がネタを振って、みなさんの考えを色々引き出す感じで行いました。発表する中で気になったのは、文の「構造」をどういう風に捉えているのかということでした。文が、「構造」を持っている、つまりシーケンス以上の情報を持っているということはおそらく同意が取れると思うのですが、その「情報」がなんなのか、どう表現できるのかについては十人十色の考えを持っているようです。係り受けのような表現（全域木）もあれば、句構造にように中間のノードを付与する表現方法もあります。でも、実はこれらの幾つかが同じ情報の別表現（一対一対応がとれる）だったりもするし、グラフ構造のように視覚的に表現しやすい必要もないのかもしれない・・・。こうした構造のもつ情報、また表現方法などを探ると、文に対してもう少し別の見方が見つかるんじゃないのか、というのが今回思ったことでした。また、発表の途中で松本先生がいらっしゃって、文字単位の係り受け表現についていろいろ教えていただけたことも収穫でした。たまたま、こうした研究を以前やっていらっしゃったらしく、取り扱いの面倒な現象をたくさん教えていただけました。その他にも、今回は知り合いの研究者の方がたくさんいらっしゃって、論文やらアイデアやらをたくさん教えていただき、感謝です。

ACL2011読み会で発表してきました

今日は、サイボウズ・ラボさんにおじゃまして、ACL2011読み会で発表しました

今日読んだ論文はこれです。

Exploiting Web-Derived Selectional Preference to Improve Statistical Dependency Parsing.
Guangyou Zhou, Jun Zhao, Kang Liu, Li Cai.
ACL2011. [pdf]

発表スライドはこちらです。

ACL2011読み会 Exploiting Web-Derived Selectional Preference to Improve Statistical Dependency Parsing

View more presentations from Yuya Unno

動的計画法は再帰で表せ

動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています．
メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります．

今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x - 2)とかけます．このままプログラムにかくと，

def fib(x):
if x == 0 or x == 1:
return 1
else
return fib(x - 1) + fib(x - 2)

これで参照透過な関数はかけました．後はメモ化するだけ．

def fib(x):
if x in cache:
return cache[x]
elif x == 0 or x == 1:
return 1
else:
v = fib(x - 1) + fib(x - 2)
cache[x] = v
return v

これだけです．基本，再帰が書ければそこでおしまい．パフォーマンスがシビアにならない限り，基本的に全部これでプログラム書いています．

もっとNLPよりな例を出します．たとえば，linear-chain CRFのViterbiパスのスコアを求めてみましょう．



s(x, y)は素性ベクトルと重みベクトルの内積です．やはり再帰でかけますので，同じようにメモ化するだけです．メモ化したあとに，じっとにらめっこすると，いわゆるDPテーブルを使った動的計画法に変換できます．ただ，DPテーブルを使う場合は，計算の順番を考えないといけない点で面倒です．つまり，v[t][x]の計算にはv[t-1][・]が全部終わっている必要があります．関数呼び出しコストがなくなるので，実用上は速くなります．ただし，CRFやHMMくらいならいいですが，CKYの計算順序くらいになると直感ではわからなりません．再帰で書けば，計算されてなかったら計算する，計算済みならキャッシュを返す．それだけです．まぁ，依存関係を図示すれば多くの場合すぐわかりますが．


On Efficient Viterbi Decoding for Hidden semi-Markov Models.
Ritendra Datta, Jianying Hu, Bonnie Ray, ICPR 2008.

Semi-MarkovのViterbiがDPテーブルを2つ使うと高速になるよ，という論文を以前先輩に紹介されました．最初この論文は式が全然追えなくて，なんて複雑怪奇な計算をしているんだと思ったのですが，途中にある再帰式を眺めてたら気づきました．



Bの部分は一部省略してます．これの計算量はT * N引数で，T回ループとN回ループがあるのでO(N²T²)といってます．これをちょっと変形します．



単に内側のmaxを外だしにしました．相互再帰になりました．見えましたか？　どちらの関数もT * N引数で，ηはN回，δはT回のループです．これを素直にメモ化すれば，計算量はO(NT(N + T))です．恐ろしく簡単になりました．こう書けばいいのに・・・．

思うに，この程度まで複雑になってしまうとDPテーブルを使って考えるのは難しいです．まず，再帰で表す．そしてメモ化．速くしたければDPテーブル化．再帰で表すセンスは関数型言語で磨きましょう．リストや木やDAGを見ると再帰で表したくてうずうずしたくなりますよ．

ICML2011読み会に行ってきました

昨日は@nokunoさん主催のICML2011読み会に参加しました。ボクは場所貸ししただけで、発表してません（汗　本当は超簡単なsemi-supervised naive bayseを実装して発表しようかと思ったんですが、発表者いっぱいいるし、まぁいいかなと。

CRFのヘシアン

坪井さんの論文がAAAIに通りました。おめでとうございます。AAAI記念ということで、宣伝その２。今回はCRFのヘシアンを具体的に計算してみます。

入力文x、ラベル系列y、重みベクトルwに対して、CRFの対数尤度関数は



です。fは特徴ベクトルで、普通f(x, y)と書きますが省略します。Zは分配関数です。正則化項を無視すれば、学習データに対するこの値の総和、



が目的関数でした。この勾配はきれいな形をしていて、



という形でかけます。NLP屋さん的にはここでおしまいですが、実はもう１回微分した形、つまりヘシアンもきれいな形で求まります。では頑張って微分しましょうというのが今回の主旨。

まず、第１項のΣ_yfの項はwで微分すると消えます。考えないといけないのは第２項のE[f]の部分だけです。ベクトルの微分なのでちょっとめんどくさいです。もとの式に戻しましょう。



ではwで微分しましょう。まずは積の微分公式です。



第１項は簡単ですね。



第２項は1/Zの微分ですが、これも勾配の時と同じように落ち着いて計算すれば綺麗に消えていきます。



結果的に、全体では



になりました。なんともシンプル。ところで、勾配を求める時もものすごくキレイに期待値が出てきますよね。何回か手を動かしていると、その心がなんとなく分かってきます。イメージで言うと、expの微分がexpである（自分自身である）ということ、そしてexpの中のfwが微分されて、fが外に出てくるというのが結構ポイントのように思います。前者の特徴がP(y|x)を生み出し、後者がfを生み出し、全体でEを生み出している、そういう風に感じられます。

さて、この式から具体的な再帰式（DPの式）を導くことが出来るでしょうか。実はここまでの式変形にCRFのCRFたる特徴は使っていません。使っているのは対数線形モデルであるという特徴だけです。したがって、MEもsemi-CRFもparsingの対数線形モデルも同じ式で表せます。CRFの特徴、すなわち特徴ベクトルfがグラフィカルモデル上でのクリークに対する特徴関数の和で表せるという性質を使うのはここからです。



だとします。iはクリークにつけられたインデックスです。すると、期待値の線形性から



に分解できます。P(f_i)は各クリークが選ばれる周辺確率です。これは一般のCRFでは必ずしも効率的に計算できませんが、例えば直鎖CRF（linear-chain CRF)の場合は前向きスコアと後ろ向きスコアの積で簡単に表せることが知られています。すなわち、



です。細かいノーテーションは省略します。雰囲気で察してください（ぉ　αとβの値は動的計画法を使えば多項式時間で計算できますから、予め計算してあげれば上記のE[f]も多項式時間で計算できる、という寸法でした。lnear-chain CRFだと効率的に勾配を計算できるのは、このあたりが絡んでいます。先の@sleepy_yoshiさんの日記で省略されていたのがこの部分です。もちろん、前向き後ろ向きを内側外側にすれば構文解析ができます。


同じことを先のヘシアンに対しても適応できないか考えてみます。ところが、E[ff^T]を分解しようとしたところで詰まってしまいます。実は私は先ほど求めた式から動的計画法の式を導き出す方法をまだ編み出していません。しかし再帰式自体はもとまっていて、それが最初に紹介した坪井さんの言語処理学会の論文、及びAAAIの論文でした。個人的には、勾配の時と同じように上の式から直接きれいな形で再帰式を導き出せると思っています。実は別の導出もあるんですが、それも含めて再帰式の導出はまた今度。

Newton-CG法とは

先日、@sleepy_yoshiさんがCRFの目的関数の導関数を求める記事を書いていました。ここに便乗して、@yuutatさんたちとやっていたNewton-CG法について解説を書きます。・・・、と思ってたのですが引っ越してから未だにネットにつながらなくてなかなか更新できませんでした。今、マックで書いてますｗ

まず、Newton法のおさらいから。Newton法は、目的関数を２次関数で近似して、その最小値（放物線の頂点）に更新する方法です。２次関数による近似は現在のパラメータx₀の周りでテーラー展開すればよいです。



これが最小値を取るのはxで微分した値が0になる時で、それは



に更新すればよいことがわかります。xがベクトルの場合も同様で、この場合、１階微分がベクトル（勾配）g、２階微分が行列（ヘシアン）Hになることに気をつけます。



さて、CRFの目的関数に関してこれを適用することを考えます。勾配は@sleepy_yoshiさんの日記のとおり計算できます。問題はヘシアンの逆行列です。この計算には２つの難しさがあります。ひとつは、xの次元が大きすぎるため、ヘシアン自体を陽に計算できません。もうひとつは、その逆行列は尚更計算できません。

この問題を解決するために、ヘシアンの逆行列を近似するのが擬ニュートン法でした。よく知られたL-BFGSは、反復の直近の勾配を使ってこれを近似します。しかし、実はもっと正確に計算できます。欲しいのはヘシアンでもヘシアンの逆行列でもなく、ヘシアンの逆行列を勾配に掛けた値です。つまり、欲しいのはベクトルです。ヘシアンもヘシアンの逆行列も陽に計算しないで、ヘシアンの逆行列と勾配との積を直接計算できないか、というアイデアが生まれます。実はこれが数値解析的に計算できます。すなわち、共役勾配法（CG法）を利用してこれを計算してしまう方法、これがNewton-CG法です。

ここでCG法を思い出してみましょう。CG法は連立一次方程式Ax=bを数値的に解く手法です。この解というのは、すなわちx=A^-1bを求めるということです。ところで先ほど求めたかったのは、H^-1gでした。すなわち、Hx=gという連立一次方程式をCG法でといてやれば、求めたかった更新式を計算できるという寸法です。ようやく道が開けてきました。CG法の更新式にAの逆行列は出てきません。これでヘシアンの逆行列を計算する必要がなくなりました。代わりにAとベクトルとの積が出てきます。この、ヘシアン・ベクトル積（Hessian-vector product）を計算できるか否かがポイントに成ります。そして、CRFの目的関数に対するヘシアン・ベクトル積が、動的計画法によって効率的に計算できるよ、ということを示したのが言語処理学会での@yuutatさんの論文なのでした。肝心のCRFのヘシアン・ベクトル積の計算方法ですが、これは導出が結構めんどくさい。言語処理学会の論文でもほとんど省略、発表では完全に省略（笑）しています。ところで、Newton-CG法自体は既存手法だったので、ひょっとすると機械学習やあるいは最適化の人にとってはよく知られた手法なのかもしれません。



言語処理ではベクトルの次元が巨大になるのでヘシアンを陽に計算できないよね、だから大雑把な近似しかできないよね、だからL-BFGSを使うんだよ、というのが教科書的な説明でした（だったと思う）。ちょうど、機械学習アルゴリズムを実装しようと思ってこの辺りの最適化アルゴリズムを勉強していて、ほうほうだから近似するんだね、ひとつ賢くなったよ、と思ってたときにNewton-CG法を教えてもらいました。せっかくできないことを知った直後に、実はできるよと言われたものだから結構衝撃的だったのを覚えています。ヘシアンもヘシアンの逆行列も陽に求まらないけど、それらをすっ飛ばしてヘシアン・ベクトル積なら計算できる。この辺りは全系列を列挙はできないけど、周辺確率なら計算できる、分配関数なら計算できるというのに似ていて、DPスキーとしてはニヤリとしてしまいます。
ところで時はオンライン学習大全盛の時代。L-BFGSに劇的勝利を果たしたあと、SGDの驚異的な学習の速さにあ然とするのでした。

L1正則化で重みが0につぶれる理由

L1正則化、つまり正則化項としてL1-normを使うとパラメタの大部分が0につぶれてモデルがコンパクトになるよという話をよく聞くと思います。初めて聞くと、何で？と思われるかと思います。先日の岡野原握手会でもこの話題がさらっとでて、@hillbigさんはよく微分した形でこれを説明しています（「押すなよ押すなよー」）。私は目的関数の形で理解した方がわかりやすいと思っているので、それを紹介。

まず、正則化項の入っていない凸な目的関数を考えます。



普通パラメタベクトルは多次元なので、多次元の山みたいな形になりますが、ここでは1次元だと思いましょう。この時点で最適値は（頂点の位置）は3です。これに正則化項を足します。L2だとこんな形をしています、というか0を中心とする放物線です。



足しましょう。



足すと0に向かってシフトすることがわかるでしょう。L2正則化の式は原点中心の山なので、元の山（頂点がどこだかわからない）に足すと、必ず頂点は0に近づきます。ここで大事なのは、頂点の”値”ではなくて”位置”です。求めたいのは最小値をとる引数です。このとききれいな山になるのですが、滑らかな曲線に滑らかな曲線を足したんだから、滑らかな曲線ができるに決まってます（目的関数が滑らかな場合）。目的関数の頂点の位置にかかわらず0に近づく、しかし0にはならないことは明白です。これが、L2でパラメタの値が小さくなる、しかし0につぶれない理由です。

では、L1だったら？ L1は下のような形をしています。尖ってます。



足したときの形というのは、0で折り曲がるのは（微分できない）確実ですが、元の目的関数の形に依存して以下の2種類が考えられます。ひとつは依然として0以外のところで最適値をとるケース。もう一方は0でぱきっと折れて、0が最適値になるケースです。



先ほど書いたとおり、本当の目的関数は多次元ですから、0になる次元とならない次元があります。この、0になる次元というのが、0につぶれる次元ということです。
ではどういう次元が0につぶれるのでしょう。正則化項を足した後の関数を微分すれば関数の傾きがわかります。0の前後で傾きの正負が変われば0につぶれることがわかります。正則化項の傾きは0の前後でそれぞれ一定ですので、結局目的関数の0の周辺での傾き（微分）の大小によって決定されると理解できそうです。

さて、この傾きが@hillbigさんのいうところの「0に向かって押す力」です。目的関数は自分の頂点（≠0）に向かってみんなで押していて、その力は頂点からの距離で変わります。一方、正則化項は一定の力で0に向かって押しています。両者の大きさの大小は場所によって違うということです。正則化項の押す力のほうが0近辺で強ければ、目的関数の押す力は負けてしまいますので0の前後で正則化項の力に負けて最適点は0になります。すると、先ほどのぱきっと折れた後者のグラフ、0で最適値をとるグラフになるわけですね。

言語処理学会年次大会2011に参加しました

先週は月曜から金曜まで、豊橋技術科学大学で開催されいていた言語処理学会年次大会に参加しました。会場がホテルから遠いとか、駅から遠いとか、豊橋技科大出身の友人が何にもないよとか言ってて不安でしたが、梅村先生はじめ、技科大のスタッフの尽力のおかげでこれといった不便はありませんでした。初日に暖房が効いてなくて死ぬかと思いましたが、次の日から改善されていました。あったとすれば、「たかり事件」くらいでしょうかｗ

私の発表は、若手の会での発表の続きで、表現統一のために既存文書の頻出表現を動的に取り出して入力支援に活かす話です。予測入力とおもってもいいと思います。主に若手の会で@nokunoさんに質問された、頻出Nグラムを使う方法とどう違うのか、という回答をしたつもりです。文書のクオリティーを上げるために表現統一を実現したいというモチベーションと、他手法と比べて文字列集合を探索する定式化をしていたり、単語単位を使っていないなどの比較がメインでした。手法の概要も話しましたが、かなり長いので、ほとんど省いてなんか大変なんだねというのが伝わる程度にしました。ざっくり書くと、KWICをコンパクトに表示すれば入力支援に使えると思い立ち、文字列集合に対するスコア関数を最大化させる形に定式化して、TRIEや接尾辞木などの文字列テクを駆使して実時間で実行出来るレベルにチューンしました。ちょっと笑いもとれたので良かったです。論文はこちらのサイトにおいてあります。

Google、Microsoft、ジャストシステム、Appleと日本語入力をやっている企業から、ChaIME、Social IMEの開発者まで参加するオールスター的なセッションだったにも関わらず、不自然言語処理の裏セッションになってしまって聴衆を取られたっぽかったです。しかし、かなりクオリティーの高い議論ができた気がします。ちなみに、金曜に地震の影響で延泊したとき、さらに濃密なIME話を聞けて鼻血でそうでしたｗ

坪井さん達との共著でNewton CG法をlinear chain CRFに適応した論文も発表しています。Newton CG法はHessianの逆行列（でか過ぎて計算できない）を使う代わりにCG法を使ってNewton方向を求める方法です。この際必要となるのは、Hessianと与えられたベクトルxとの積で、これがHessian vector積と言われる計算。問題は、CRFのように複雑な構造から計算される目的関数のHessian vector積を計算できるのかという点ですが、それを示したのがこの論文でした。入社してしばらくして、ねちねちL-BFGSをつくっていたときに教えてもらった思い出深い手法です。反復ごとの収束がものすごく速くなったのを覚えています。ちょうどSGDが大流行しているときで、出すタイミングを見失っていましたｗ

発表以外では、若手の会、関根会、懇親会、岡野原握手会などの各種イベントに参加して、知り合いが増えました。私は学生時代、研究室の傾向でしょうか、あまり学会に参加しなかったのですが、いろんな知り合いを作るとアドバイスを貰えたり、相談できたり、なによりモチベーションの増加につながります。業界を俯瞰するにも役立ちます。最近は勉強会などもありますし、特にここを読んでくれている学生の方は外に出てみることをおすすめしますよ。

第200回NL研に参加しました

先週，SIG-NL 200に聴講者として参加しました．NHK放送技研に潜入できる！と意気揚々と行ったのですが，どうやら建物自体には入れず，脇にある講堂のようなところが会場でした．中に入ったからといって何があるというわけでもないんですが．

さて，第200回記念ということで，歴代主査の先生も呼んでパネル討論まであったのですが，参加人数はイマイチ．少々寂しい．パネル討論でも最近盛り上がりに欠けるよね，というのが大きな一つのテーマでした．詳細は@mamorukさんのブログを参照．私の印象としては，発表者のインセンティブになるようなメリット，つまりアドバイスやコメントや議論が少ないというのが一番よくないなぁと思っています．発表すると関連研究を教えてもらえる，アドバイスをもらえる，新しい発想が得られる，これはよいまた発表しよう，新しい発表が聞ける，また聞きに行こう，というサイクルが回れば参加者も増えそうですが，今はその逆になっているように思います．これに限らず，発表準備はそれなりにコストのかかることなわけで，発表者にインセンティブが働く仕組みがなければ勉強会でも何でも続かないですよね．経験的にも・・・．
討論の中で印象的だったのは，松本先生の「何となくみんな忙しい」という言葉でした．なるべく多くの研究者が集まった方がいいとは思いますが，仕事が「何となく」忙しいと難しいですよね，何となく．めちゃくちゃ忙しいはずの（実際は知らないけど）松本先生が，毎回のようにいらしているのはすごいなぁといつも感服します．自分も忙しいとか言ってないでちゃんと時間を見つけられるようにしないと．


発表で気になったのはロンゴロンゴでした．完全にタイトルでだまされましたｗ　昨年の5月も聴講したので発表を聞くのは2回目ですが，すごい楽しそうに研究していて，いいなぁと思っていました．たまたま帰りのバスで一緒になったので，色々教えてもらいました．未解読言語の解析というのはわくわくしますね．

自然言語処理勉強会@東京に参加しました

@nokunoさん主催の自然言語処理勉強会@東京で「統計的係り受け解析入門」というタイトルで話をしてきました．資料はこちらにおいておきます．CKYアルゴリズムに関して質問が多かったので，説明を加筆しました．

内容は「入門」と銘打っておきながら，3rd order Eisnerまで紹介するアレな内容．どういう方が出席されるかわからなかったので，ちょっと最新の話題も入れてみたかったのでした．もともと社内セミナーで使った資料を半分流用しています．
Eisner法の理解の肝は，三角と台形がCFGにおける非終端記号に相当している，三角が三角と台形に分割されるというルールが，CFGにおける書き換え規則に相当している，という点が理解できれば後はCFGの知識で理解できます．この記法に慣れてくると，例えば3rd orderの論文はほとんど図を見るだけで理解できます :)
割愛しましたが，本当はこのあとスコアをどうやって学習するかという話しに行きます．log-linearにして，微分するとinside-outsideがでてきたり，周辺確率がinsideとoutsideの積で求まったりします．当然logsumexpもつかいますし，動的計画法のオンパレードです．

学会と違って，企業の方が多かったのもありますが，どうやって応用するのかという議論がいたるところでなされました．これは非常に良いことだと思います．学術的には興味を誘わない話題，特に強調した分野適応や辞書リソースの効率的な構築法などは応用上きわめて重要だと考えています．学生時代分野適応なんて，特許かWebデータに適応することだろくらいに高をくくっていましたが，実際には特定分野のお客様（例えば製造業，医療，法律，銀行）にいかに効率的に分野適応できるかが性能の鍵を握っています．こうした問題意識と研究テーマをもっと啓蒙していかないとと思っています．MeCab以来教師あり形態素解析が進んでいませんが，こうした部分でものすごく問題を抱えたまま放置されている気がします．まぁ，自分がやればいいんですけどね．

NLP若手の会シンポジウム

NLP若手の会シンポジウムで発表しました．前々から何度も参加はしてたんですが，発表は初めて．タイトルは緩い感じの会議ですが，発表者も参加者も30台前後のポスドクや助教，博士課程学生が中心で，議論も活発，新規な内容が多い．特に自分の同世代，近い世代の人たちがこんなに活躍しているというのを見れて，とてもよい刺激になります．そういうのは，会議の前に書けって？　すいません．

私の発表の内容なんですが，一言で言うとKWIC (KeyWord In Context)をかっちょよくしました，という内容です（片側しか見てないからKWICじゃ無いじゃん，と突っ込まれました．実は事前に坪井さんにも突っ込まれてました）．KWICは検索結果を俯瞰するのに便利なんですが，ヒット数が多いと全体を見られなくなります．なので，うまい単位でまとめたい．これを探索問題として定式化してあげると，動的計画法に落とし込めます．さらに，最大値を求めるということは，一番最大っぽいところを探索したら，残りはそれを超えないことを確認すればOKという感じで，スコアの上限を求める関数で枝刈りをします．最後に，あらかじめ接尾辞木を頻度順に並べておくことで，TRIEの構築もサボれます．もともと，入力支援に使おうと思っていて，発表の1週間前に狙ったようにGoogle Scribeがでて困りました．デモ画面そっくり．
枝刈りのアイデアは，オセロのαβ枝刈りからインスパイアされました．αβ枝刈りは，最大値を求めるときに，超えなければいけない上限を渡して探索する方法です．学部時代にオセロプログラム大会をやったことがあって，move orderingとか色々知識を持っていました．どこでどういう知識が役にたつかなんてわからない，知れる機会があれば何でも知るべき，ということを少し体現できたかなと思います．

他の発表ですが，奨励賞の松林さんは同じセッションで聞けなかったのが残念．高村さんの語彙をつくる話は，「言語とは何ぞや」という問題に対して新しいアプローチで迫っていて面白かったです．私ももっと夢のある話をした方がよかったかなぁ．それから，内田さんがオノマトペと動詞の対応みたいな話をしてました．一応，私も言語処理学会でオノマトペネタを（共著で）発表したので気になります．当時色々アイデアを出して，ほとんどやってなかったので少しやろうかな．


いくつか聞いてて，やっぱり自分は応用よりだ，と思いました．工藤さんの講演での回帰テストの話とか，それに対する岡野原さんの質問とか，T2ミーティングでの橋本さんの話とかがやっぱり自分にはピンとくるところがあって，企業系の人（あるいはアプリ屋さん）がもってる問題意識とアカデミックの問題意識でギャップが進んでいるように思いました．もっとも，そこはちゃんと住み分けが進んでていいとも思っています．むしろ，アカデミックには短期の実用より，長期的に見て必要な基礎研究を進めて欲しい．ただ実用まで持っていくにはこれだけ必要なステップがあるよ，そしてどこも手を抜けないよ，ということが一歩引いたところから俯瞰して共有できればいいなと思います．

logsumexpとスケーリング法

少し前にtwitter上でCRFSuiteはスケーリング法を使っているから速い，的なことを書いたのでその解説です．

linear-chain CRFのパラメタ推定に必要なのは対数尤度関数の微分です．これの計算に必要なのが，前向き・後ろ向きのスコアαとβです．時刻t（系列上での位置）とラベルiに対する前向きスコアαは，以下の式で計算されます．fは特徴ベクトル，wは重みベクトルです．



ところがこのままだと問題が起こります．αの値はexp個の足し算で構成されるため，最終的にかなり大きくて，簡単に倍精度の限界を超えてしまうのです．困った．そこで，logの世界に落とします．αの代わりにlog(α)を計算します．すると，expの世界の掛け算はlogの世界の足し算になります．問題は，足し算です．expの世界の足し算を，logの世界で行う２項関数がlogsumexpです．



で定義されます．expをかけてるから，結局オーバーフローしてしまうように見えますが，以下のように式変形することで，見事にオーバーフローしなくなりました．ただし，y < x とします．



これを使うとlogαの計算は以下のようになります．



ここまでがlogsumexpの話．


logsumexpを使い出すと，今までただの足し算でよかったのにlogやらexpやら，いかにも重そうな関数を使わなくてはならなくて激しく遅くなります．できる事ならexpの世界のまま計算したい．そこで使われるのがスケーリング法です．ここで大事な点を思い出します．最後に計算したかったのは周辺確率です．つまり，0から1の間に収まるような値が出力です．最後にZで割れば，彼らは器用にoverflowもunderflowもおこしません．ということは，少しずつ割っていって，最終的にZで割った値が出るように調整してあげれば，オーバーフローせずに計算が終わるはずです．

時刻 t ごとに和が 1 になるように正規化したα'を以下で定義します．



これを，普通のα同様にα'の再帰計算で計算できればlogの世界で計算する必要がなくなるという寸法です．結局α'は，毎時刻ごとに1になるように正規化しているだけなので，正規化するときに割った値を覚えておけばよいのでした．ちなみにこのテクは，PRMLのHMM（だったかな？）の章に書いてあります．って教わりました．

ところで，これで本当に速くなるんでしょうか．改めてαの式とlogαの式を見返して見ます．確かにαにはlogsumexpがありません．しかし，logαでは実は重みベクトルと特徴ベクトルの内積に対するexpが消えました．結局，logsumexpの代わりにexpになっただけ，このままではexpの実行回数で両者に差がありません．ここにもう一つトリックが存在します．一般にlinear-chain CRFではラベル遷移の特徴（遷移素性）と各時刻ごとの特徴（状態素性）は別々にあらわされます．つまり，

という2種類の特徴量に分けられています．ラベル数L，文長Tとします．これらのexpはあらかじめ計算しておくと，必要なexpの計算量はO(TL + L²)，一方でlogαではO(TL²)．結果的にαを直接計算した方が，つまりスケーリング法の方が速くなるのでした．


ところで，そんなわけで私も以前スケーリング法を実装したのですが，なんだか思わぬタイミングでoverflowやunderflowを起こしてしまいます．なので，私も完璧に理解したわけではありません．まだ実装上のテクニックがあるのかもしれません．logsumexpもスケーリング法も，たまたま何かで見たり，たまたま教えてもらったり，罠がいっぱい．