先週の土曜日にPFIで行ったEMNLP2014読み会で、Skip-gramモデル（word2vec）と語義曖昧性解消を同時に解く論文の紹介をしました。 発表スライドはこちら。 単語の表現学習と語義曖昧性解消を同時に解く話は、もう一つ論文がありましたが、なんだかいまいちだったのでこちらになりました。 要点だけ整理します。 Skip-gramモデルは、単語に対するベクトル表現を学習する手法として注目を集めています。 このモデルは、ある単語の出現が周囲の出現単語に影響を与えるため、中心単語のベクトルと周囲の単語のベクトル（word2vecの実装では両者は別のベクトルとして区別します）の内積のexpに比例する確率で、周辺単語が決定されるというモデルを置きます（詳細は以前のスライド参照）。 実データを使って、対数尤度が最大になるようにベクトルを学習します。 ここまでがSkip-gramでした。 この

先週のPFIセミナーで生成語彙論とDeep Learning（特に表現学習の領域）の関係について、思っていることを話しました。前半は生成語彙論の入門的な内容で、数式もなくてだれでも読めるような内容になっていると思います。生成語彙論の勉強を始めたのが最近なので、入門という程の内容にもなってないですが、こうした言語学の知見をもう一度紐解くと面白いかもしれません。 発表中にあまりちゃんと話さなかったことをちょっと書いておきます。2012年あたりから、Socherが既存のNLPタスクにバシバシ一連の手法を試していました。私もその辺りで初めて深層学習の話を聞いたわけですが、ちょうど構文解析をnon-terminalのところで表現ベクトルを使うという話がありました。これに対して、「素性構造のような複雑な構造と演算を、ベクトル空間と非線形関数の中に埋め込んでいることになるのでは」という感想を、宮尾さん（

報道機関の発表の通り、10/27日に分散オンライン機械学習基盤Jubatusを発表しました。これに関しても書きたいことは山ほどあるのですが、来週Jubatus Workshopがあるので、それまでは秘密です（ウソです、聞かれたら答えます）。 さて、同時に公開されたのがpficommonです。これは、弊社内で使われていた便利ライブラリで、あまりの便利さにこれがないと開発できないため、Jubatusでも使われています（もちろんSedueでも）。そして、Jubatus公開に伴い公開となりました。pficommonは明日からでも使うべきなライブラリなので、先にこちらを紹介します。 pficommonは様々なライブラリからなる、複合的なライブラリです。 今日は個人的にお気に入りの、 xhtml_cgi json の２つを紹介します。 xhtml_cgi 実験用のコードなどを書くと、たくさんログを出力

会社のブログにも書いたのですが、9/21, 22にNAISTで開催されたNLP若手の会シンポジウムで発表してきました。私は幸運にも最優秀奨励賞をいただきました。投票してくださった皆様どうもありがとうございます。発表資料はこちら。 さて、ちょっと裏話でも書きます。もともと発表する気（も時間も）はなかったのですが、プログラム委員ということでどちらにしろ奈良に行くのと（これは後に案外みんな来てないことがわかった）、最近開発＆案件続きでちょっと研究もやりたいねということで、急遽発表ネタを捻出することになりました。特に検索クオリティを上げるような面白いネタはないだろうか。以前から確率的単語分割で検索品質を上げるという話があったのですが、これを確率的構文解析に適用したら・・・。単語境界情報のみだと、スキップのある部分文字列検索に自然な適応ができません。係り受け関係というのは、ある意味こうしたスキップの

今日は、サイボウズ・ラボさんにおじゃまして、ACL2011読み会で発表しました 今日読んだ論文はこれです。 Exploiting Web-Derived Selectional Preference to Improve Statistical Dependency Parsing. Guangyou Zhou, Jun Zhao, Kang Liu, Li Cai. ACL2011. [pdf] 発表スライドはこちらです。 内容はすごい簡単です。一言で言えば、単語の出現確率のPMIをgraph baseの係り受け解析の特徴量にいれたら精度が上がりました。これだけ。でも、これだけ主張が短くてはっきりしていて、アイデアも適用方法も明確なのは良いと思いました。一方で、いかにも誰かやってそうな方法で、既存研究ないのかという方が気になる論文です。 さて、もうちょっとちゃんと説明しましょう。係り受け

昨日は@nokunoさん主催のICML2011読み会に参加しました。ボクは場所貸ししただけで、発表してません（汗　本当は超簡単なsemi-supervised naive bayseを実装して発表しようかと思ったんですが、発表者いっぱいいるし、まぁいいかなと。 さて、みなさん発表上手なので話半分に分かった気になりました。一番面白かったのは松島さんが紹介した下の論文。 Parallel Coordinate Descent for L1-Regularized Loss Minimization Joseph Bradley, Aapo Kyrola, Daniel Bickson, Carlos Guestrin coordinate descentというのは、特徴空間の中で適当な次元の断面を考えて、その平面上で目的関数を最小化し（特に、解析的に最小点が求まることもある）、これを繰り返せば

坪井さんの論文がAAAIに通りました。おめでとうございます。AAAI記念ということで、宣伝その２。今回はCRFのヘシアンを具体的に計算してみます。 入力文x、ラベル系列y、重みベクトルwに対して、CRFの対数尤度関数は です。fは特徴ベクトルで、普通f(x, y)と書きますが省略します。Zは分配関数です。正則化項を無視すれば、学習データに対するこの値の総和、 が目的関数でした。この勾配はきれいな形をしていて、 という形でかけます。NLP屋さん的にはここでおしまいですが、実はもう１回微分した形、つまりヘシアンもきれいな形で求まります。では頑張って微分しましょうというのが今回の主旨。 まず、第１項のΣyfの項はwで微分すると消えます。考えないといけないのは第２項のE[f]の部分だけです。ベクトルの微分なのでちょっとめんどくさいです。もとの式に戻しましょう。 ではwで微分しましょう。まずは積の微

先日、@sleepy_yoshiさんがCRFの目的関数の導関数を求める記事を書いていました。ここに便乗して、@yuutatさんたちとやっていたNewton-CG法について解説を書きます。・・・、と思ってたのですが引っ越してから未だにネットにつながらなくてなかなか更新できませんでした。今、マックで書いてますｗ まず、Newton法のおさらいから。Newton法は、目的関数を２次関数で近似して、その最小値（放物線の頂点）に更新する方法です。２次関数による近似は現在のパラメータx0の周りでテーラー展開すればよいです。 これが最小値を取るのはxで微分した値が0になる時で、それは に更新すればよいことがわかります。xがベクトルの場合も同様で、この場合、１階微分がベクトル（勾配）g、２階微分が行列（ヘシアン）Hになることに気をつけます。 さて、CRFの目的関数に関してこれを適用することを考えます。勾配

twitter上で書いたとおり、３月末をもちまして日本アイ・ビー・エムを退社いたしまして、4月から株式会社Preferred Infrastructureの研究開発部門で働きます。ここに戻ってくることは無いだろうと思った本郷に、たった3年で戻ってくることになるとは思っても見ませんでした。 内外いろんな人から、なんで転職するんだという質問をいただきます。別に前職に大きな不満があるわけでもなかったし（小さな不満はどこに行ってもあると思います）、ちょうど自分がやり始めた研究、開発が成果を上げ始めて、まさにこれからという微妙なタイミングでもありました。 昨年末あたりから@hillbigさんに声をかけてもらって、悩んだ末での決断でした。これから研究開発を強化する、その過程を体験するというのは非常にチャレンジングで貴重な体験になるだろうと考えたのが主要な理由です。また、特に心に響いたのが、「変わらない

先週は月曜から金曜まで、豊橋技術科学大学で開催されいていた言語処理学会年次大会に参加しました。会場がホテルから遠いとか、駅から遠いとか、豊橋技科大出身の友人が何にもないよとか言ってて不安でしたが、梅村先生はじめ、技科大のスタッフの尽力のおかげでこれといった不便はありませんでした。初日に暖房が効いてなくて死ぬかと思いましたが、次の日から改善されていました。あったとすれば、「たかり事件」くらいでしょうかｗ 私の発表は、若手の会での発表の続きで、表現統一のために既存文書の頻出表現を動的に取り出して入力支援に活かす話です。予測入力とおもってもいいと思います。主に若手の会で@nokunoさんに質問された、頻出Nグラムを使う方法とどう違うのか、という回答をしたつもりです。文書のクオリティーを上げるために表現統一を実現したいというモチベーションと、他手法と比べて文字列集合を探索する定式化をしていたり、単

@nokunoさん主催の自然言語処理勉強会@東京で「統計的係り受け解析入門」というタイトルで話をしてきました．資料はこちらにおいておきます．CKYアルゴリズムに関して質問が多かったので，説明を加筆しました． 内容は「入門」と銘打っておきながら，3rd order Eisnerまで紹介するアレな内容．どういう方が出席されるかわからなかったので，ちょっと最新の話題も入れてみたかったのでした．もともと社内セミナーで使った資料を半分流用しています． Eisner法の理解の肝は，三角と台形がCFGにおける非終端記号に相当している，三角が三角と台形に分割されるというルールが，CFGにおける書き換え規則に相当している，という点が理解できれば後はCFGの知識で理解できます．この記法に慣れてくると，例えば3rd orderの論文はほとんど図を見るだけで理解できます :) 割愛しましたが，本当はこのあとスコア

NLP若手の会シンポジウムで発表しました．前々から何度も参加はしてたんですが，発表は初めて．タイトルは緩い感じの会議ですが，発表者も参加者も30台前後のポスドクや助教，博士課程学生が中心で，議論も活発，新規な内容が多い．特に自分の同世代，近い世代の人たちがこんなに活躍しているというのを見れて，とてもよい刺激になります．そういうのは，会議の前に書けって？　すいません． 私の発表の内容なんですが，一言で言うとKWIC (KeyWord In Context)をかっちょよくしました，という内容です（片側しか見てないからKWICじゃ無いじゃん，と突っ込まれました．実は事前に坪井さんにも突っ込まれてました）．KWICは検索結果を俯瞰するのに便利なんですが，ヒット数が多いと全体を見られなくなります．なので，うまい単位でまとめたい．これを探索問題として定式化してあげると，動的計画法に落とし込めます．さら

少し前にtwitter上でCRFSuiteはスケーリング法を使っているから速い，的なことを書いたのでその解説です． linear-chain CRFのパラメタ推定に必要なのは対数尤度関数の微分です．これの計算に必要なのが，前向き・後ろ向きのスコアαとβです．時刻t（系列上での位置）とラベルiに対する前向きスコアαは，以下の式で計算されます．fは特徴ベクトル，wは重みベクトルです． ところがこのままだと問題が起こります．αの値はexp個の足し算で構成されるため，最終的にかなり大きくて，簡単に倍精度の限界を超えてしまうのです．困った．そこで，logの世界に落とします．αの代わりにlog(α)を計算します．すると，expの世界の掛け算はlogの世界の足し算になります．問題は，足し算です．expの世界の足し算を，logの世界で行う２項関数がlogsumexpです． で定義されます．expをかけてる

ちょっと報告が遅れましたが，会議には参加してませんが，NTCIR-8のPatent Mining Taskに，チーム西山の隊員として参加しました．タスクの内容は，特許文書中からその特許が解決したい課題や効果がかかれたフレーズを抜き出すというものです．結果的に参加チーム中で結構いい順位につけたということで，論文も公開されています．実は私がポカしたせいで，本当はもう少し結果よかったです（後述）． 正解付与済みデータが与えられるということで，CRFを使った教師あり学習の枠組みに，おのおのの得意とする特徴量をこれでもかとてんこ盛りに入れ込みました．正解データを見る限り，明らかに係り関係にある単語や文節が分類に貢献していることがわかったので，私に召集令状が係った次第です．特に特許文書は一文が長く，構文解析が難しいので，NLP2010で発表したような距離期待値のテクでロバストになることを期待しました．

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

先月途中まで書いてたのが今更になってしまいました． 昨年末，Googleが日本語入力システムを出したのを皮切りに，Baiduも日本語入力を投入したニュースを聞いて久しい． Google日本語入力 「Google日本語入力」開発者が語る、その狙い Baidu Type - 日本語入力システム バイドゥ、日本語入力ソフト「Baidu Type」を公開 日本語入力システムといえば，それこそ初期の自然言語処理の花形，そして自然言語処理が最も成功したアプリケーションの代表格です．しかし，それは詰まるところよい意味で枯れた技術．それがここに来て検索2社から立て続けにリリースされたというのは，なぜ今更？という意味で新鮮でした．加えてこれらがフリーで提供されていることが，すでに商品として，お金をいただいて提供するソフトウェアではないほどに成熟したことを表しているように感じられます． もちろんお家芸のジャス

Stochastic Gradient Descent Training for L1-regularized Log-linear Models with Cumulative Penalty Yoshimasa Tsuruoka, Jun’ichi Tsujii and Sophia Ananiadou, ACL2009. 論文紹介．鶴岡さんのL1正則化付き確率的勾配降下法（Stochastic Gradient Descent，SGD）．L1正則化はコンパクトなモデルパラメタになってくれるので，実用上はとてもうれしい．しかし，0の点で微分できないので面倒だった．提案手法は実装が超簡単（擬似コードで20行くらい），超高速で，収束も早いし，性能もいい，いいこと尽くめ．初めての人にもお勧めできる簡単さで，しかもそのまま実用品になります． L1正則化は目的関数に重みベクトルのL1 normを

思いがけずたくさんブックマークしていただいたので，この機会になんで構文解析なんかやるのかというお話を書こうと思います．おそらく，NLP界隈の人には何をいまさらと思われるかもしれませんが，それが本当に役立つかというとなかなか一筋縄では行きません．今回興味を持たれた方の多くはNLP分野外の方なんじゃないかな，と勝手に考えてますのでそのつもりで書きます． 構文解析というのは，文の構造を判別する処理のことで，NLP的には単語分割，品詞タグ付け（いわゆる形態素解析）のあとにくる処理です．ソフトウェアで言えばCabochaやKNPがこれにあたります．ここに大変わかり易いチュートリアルがありますｗ　例えば「値段の高いワイン」が，「値段のワイン」ではなくて，「値段の高い」「高いワイン」であることを認識する技術，と理解していただければ良いと思います．このように，文節間の係り関係を解析することを，係り受け解析

そろそろ論文紹介記事を書いてみます． NLP2010のプログラムにもあるとおり，しばらく係り受け構文解析周りをやっていました（います）．私の出身研究室では構文解析をやっている人がたくさんいたのですが，最近その面白さがなんとなくわかってきました．いや，一応私も2年間日本語係り受け解析の演習担当やってたよ！　構文解析のおもしろさというのは，言語学，機械学習，プログラミング，情報科学が非常にバランスよくミックスされた問題で，いろんな定式化の仕方や，いろんな技術が，いろいろな組み合わせで，かつわりとキレイな形で程々の難しさに仕上がっているあたりにあると思います．今日は，特に情報科学的教養が大事でしたという話を3つ． Non-Projective Dependency Parsing using Spanning Tree Algorithms Ryan McDonald, Fernando Per