なぜNetflixはNetflix Prizeで優勝したアルゴリズムを実用化していないのか？

ダヌシカさんのツイート経由で、以下のURLから。

　超簡単に要約しておく。詳しく知りたい人は上記のリンク先を読んで下さい。

  • Netflix Prizeの優勝アルゴリズムでは多くのアルゴリズムが混合されていた。そのうちSVDとRBMは今でも使ってる。
    • 100万件のデータに使えるものであっても、1億件で利用可能なようにスケールさせるのは大変だった。
    • スケールさせるのが大変なので、Grand Prizeで用いられた数百のアルゴリズムの混合は、Netflixでは使ってない。
  • Netflix Prizeの成果を使ってない理由としては、技術の進化によってビジネスのスタイルが変換したため、という点もある。
    • 要するに、DVDをレンタルするモデルから、ビデオをインターネット経由でストリーミングするモデルに切り替わってきている。このため、問題が単なる行列穴埋めではなくなってきている。
    • わかりやすい違いとして、ユーザの反応がすぐにわかる、とか。（ちょっと大胆なレコメンドをしても大丈夫？）

　後半は力尽きてほとんど読んでないが、どんな軸でどんなオススメをするかとか、多様性（カバー率）が重要だよ、みたいな話が書いてあるような気がする。
　Netflix Tech Blogは他にもIntroducing Exhibitor - A Supervisor System for Apache ZooKeeperとか、面白げな記事が散見されるのでチェックしておくと良さそう。

最近のX.orgにおける2Dアクセラレーションの改善について

　ゴールデンウィークなのでちょっと息抜きを。
　Intelのドライバは最近はSNAという新しいアーキテクチャを実装していて、まだデフォルトでは有効になっていないのだが、だいぶ高速なようだ。

　この他、Glamorというのが出てきた。これはOpenGLを使ってX Winddow Systemのアクセラレーションを行うライブラリである。各種ドライバの内部で使われることを意図しているそうだ。Gallium3DのX.org state trackerとやってることは近い。Galliumの場合はOpenGLではなくGallium用の中間形式に変換するところ、アクセラレーション対象が広い（GalliumはXのアクセラレーションだけじゃなく、OpenGLとかOpenCLとかも扱う）ところがGlamorとの違いになる。SNAと比べるとまだ遅いみたいだけど、今後どうなるかちょっと期待している。ただ、OpenGLをまともにアクセラレートしてくれるドライバが少ないわけで、そこんところがちょっと微妙かなぁ。
　Cairo自体も1.12でかなり高速化されているのだが、これは一部のドライバのバグを踏むということで、まだ各ディストリビューションには導入されていない。
　こちらの記事では最近のドライバについていくつか実験をして、簡単な2Dアクセラレーション（単なるアルファブレンディングとか）であればCPUを使った方がGPUを使うより速い、なぜならGPUにデータを転送するのは結構時間がかかるから、という結論に達している。Cairoみたいな描画モデルだと描画関数それぞれに対してまともにGPUにデータ転送しちゃうので遅くなりやすいよね、シーングラフみたいに描画命令列を一旦メモリ上に保持して後で効率良く実行できるといいのかもね、ともある。
　最近のマルチコアCPUだと、2DアクセラレーションぐらいならCPUにやらせた方がいいのかもね、というのはその通りかもしれないが、なんのためにGPUがついてるのかわからなくなるなぁ…。

古くて新しいエディタ、Emacs

　技術評論社さんからEmacs実践入門を献本いただきました。たぶん数日前に届いてたんだけど、しばらく郵便受け見てなかった…。表紙
　私が書いた日本語入力を支える技術と同じWEB+DB PRESS plusシリーズということで献本頂いたのだと思いますが、レビューしとけよという無言のアレを感じる気もするので、時宜を外さないうちにレビューを書いておきます。
　本書に寄せてって何それ羨ましい！自分も書いてもらえば良かった！ というのが最初に出てくる感想なわけですが、それはさておき。
　Emacs実践入門は入門の名の通り、Emacsの使い方を説明する本です。基本的なキーバインドから便利なツールまで一通り説明している感じです。EmacsといえばEmacs Lispでガシガシと自分なりに拡張していけるところがメリットであり、同時にそれは初心者からすると何それ怖いと思わされる点でもあるわけですが、自分でelispを書くようなハードな話は出てこないので、初心者でも問題なく最後まで読み通せると思います。
　私はEmacsが最強のエディタだと思っているわけでは特に無いのですが、私にとっては手放せないエディタであることは事実です。仕事でプログラムを書くときにはEmacsを使いますし、本を書いているときにもEmacsを使っていました。そんな私にとって、Emacsについての新しい書籍が出るというのはうれしい話です。まだEmacsを使っていていいんだ、と認められた気分です。
　Emacsは初心者にとってやさしいエディタではないのですが、便利なコマンドを10個か20個ぐらい覚えると急に便利になってきて、「まぁこれでいいか…」という気分になってきます。そしてそのうちmigemoみたいに便利なelispに出会い、「なんかいつのまにかEmacsが便利な体になってしまった…」という気分になってくる。私にとってはそういう位置づけにいるエディタです。
　この本が3月に出たというのは意図があって、きっと4月に新入社員が世にあふれて、研修でEmacsとかいうのを使わされるんだけど不便で敵わん、と思ってるような人を取り込もう、というような目論見があるのだと思います。実際、この本を読むべき人はそういう人でしょう。Emacs使って10年という人が読んではいけないわけではない（実際、10年使ってる人は却って最近のパッケージシステムの話とかは知らなかったりしそうです）ですが、どちらかというと今Emacsに不便を感じていて、でも便利に使いたい人がパッと買って便利な使い方を覚える、そういう読み方が似合う本のように思います。エディタの効率は開発の効率に直結しているので、これからEmacsを覚えるつもりならば、買ってもすぐに元は取れるでしょう。

　おまけ。この本に載ってなかった機能やelispでおすすめしておきたいのはmigemoとiswitchb-modeとdmacroぐらいでしょうか。こちらも便利ですので、興味があったら検索して調べてみて下さい。

日本語入力を支える技術、本日発売

　発売ですよ、というだけではアレなので、日本語入力と私、という題目で自分語りでもしてみようかと思っていました…が、時間もないのでそれはまた今度にして、細かなトピック選択について少し触れてみようかと思います。（写真は昨日既に入荷していたジュンク堂池袋店です。右上に見えるプログラミングコンテストチャレンジブックもオススメ！）
　データ構造については、カッコウハッシュ、ダブル配列、LOUDSを選択しました。カッコウハッシュはやや唐突な感じがしますが、本当はfujimapまで紹介してfalse positiveを許すとサイズが小さくできるねー、とかやりたかったのです。fujimapをボツにしてしまったので、結果としてカッコウハッシュはちょっと浮いてしまったかなと思います。ただ、面白いデータ構造なので知っといて損はないでしょう。ダブル配列、LOUDSあたりは選択としては特に異論もないところかと思います。しかし、LOUDSは平易に説明しようとするとものすごく大変で、かなり苦戦しました。うまく説明できたかわかりませんが、とりあえず現時点でのベストは尽くしました。
　学習系に関しては、当初は確率的言語モデル→構造化SVM→CRFの順に説明を書いていたのですが、確率の説明がやっかいなことから、構造化SVM→CRF→確率的言語モデルの順番に変更しました。つまり、確率が出てくるのはできるだけ後回しにしたかったし、確率が出てきたとしてもベイズの定理とか使うのは後ろの方にしたかったのです。構造化SVMは前向き後ろ向きアルゴリズムが要らないし、オーバーフローとかアンダーフローとかあんま気にしなくても動くし、良い手法だと思っています。確率値が出せないけどね。最適化にFOBOSを使ったのは、目的関数があって劣微分が定義できたら使えるので汎用性が高い点、実装が簡単である点を評価しました。他にも条件を満たす手法はきっとあるとは思いますが、要件は十分に満たせているので今回は（自分の中で）定評があるFOBOSを使いました。
　その他、隠れマルコフモデルについてはスライスサンプリングでパラメーター推定を行う説明とか書いていたのですが、これ書いてたら発売が半年伸びるなと思って途中でボツにしました。
　とにかく、学生時代の自分が知りたかったことを今の能力で出来る限り噛み砕きつつ詰め込んだので、誰に読ませたいかというと、一番読ませたいのは過去の自分です。タイムマシンがあったら、一冊過去に送りたい。

　あとでレビュアの方々が書いてくれた記事にリンクを張ります。今日はもう寝ますのでおやすみなさい。

日本語入力を支える技術という本を書きました

　（追記）：「この本に書かれていないこと」という項を追加しました。
　以前も告知しましたが、日本語入力を支える技術という本を書きました。技術評論社から2012年2月8日に発売されます。（私の知っている限りでは、ジュンク堂池袋店、有隣堂AKIBA店、丸善丸の内店、書泉ブックタワーでは既に先行販売しているよう…でしたが、ジュンク堂池袋店、有隣堂AKIBA店、書泉ブックタワーは先行販売分は売り切れの模様です。）どんな本なのか、目次などについては公式ページを参照していただくとして、以下ではどんな本なのか宣伝したいと思います。

　この本のキーワードは「実装」と「初心者向け」です。初心者でも実装ができるようにサンプルコードを多用し、また数式が出てくる部分に関してはちょっとしつこいぐらいに説明を加えました。私自身の経験からすると、本を読んだで理解したと思っていても、大抵の場合、細かいところはわかっていないものです。実際に自分で作ってみることは、そういった理解があやふやなところを浮き彫りにするにはとてもよい手段です。本書を読んだ人にはぜひ、実際にプログラムを書いていただきたいです。一度書いてみると、以後その分野については想像力が大幅に増しますので、そのような観点からも、書いてみることは重要です。

ここがポイント

  • 日本語入力の歴史を説明する部分は地味にがんばっていて、九州大学の栗原教授の論文まで確認しました。NHK技研の相沢, 江原らの論文は、入手するためにNAISTの小町さん経由でNTTの永田さんを紹介していただき、さらにそこから山梨英和大の江原さんを紹介していただいた、というような複雑なルートをたどったりしました。そうやって頑張った割には、ちょっとしか書いてないけど…。あと、MS-IMEやATOKに関しては、MicrosoftやJust Systemの人にお聞きした知識が入っています。
  • データ構造に関して、特にLOUDSを使ったトライを紹介しているような日本語で書かれた書籍はまだ他にないはず。
  • ビタビアルゴリズムについては動的計画法とかメモ化再帰とかをからめて詳細に説明しました。ちょっと詳しすぎるかもしれない。すいません、書きたかったんです。
  • 機械学習に関して、構造化パーセプトロンや構造化SVMを説明している書籍はまだないはず。また、CRFについても前向き後ろ向きアルゴリズムの説明に6ページ使うとか、かなり力を入れて紹介しました。

　上記の通り、日本語入力を軸として、いくつかのトピックが詰め込まれています。大雑把に構成を説明すると、日本語入力の話がまず最初にあって、その後は日本語入力を実現するための要素技術としてデータ構造と機械学習についての説明がある、というような感じです。

こういう人にオススメ

  • 日本語入力に興味がある人
    • 日本語入力について歴史から実装まで、一通り知ることができます。日本語入力の技術的なところにまで突っ込んだ本って、たぶん今世紀初なはず。
  • 自然言語処理に興味がある人
    • 形態素解析器や係り受け解析器も応用として自分で実装できるようになります。（※効果は個人差があります）
  • 機械学習に興味がある人
    • 高次元かつスパースという性質を持った問題は多いですが、そのような場合に効果的な実装が紹介してあります。短い行数で実際に使える機械学習のプログラムを書くことができます。

この本に書かれていないこと

  • 文字入力用のAPI（IMMとかTSFとか）については、概念は紹介していますが、具体的な説明は書いていません。具体的なAPI仕様はOSによって変わるし、同一OSでもバージョンによって変わってくるからです。
  • 歴史的な用語などについては、有名なものは紹介してありますが、やや手薄です。
  • 個別のかな漢字変換エンジンの話はあまり載っていません。ある程度ページを割いているのはATOK、Microsoft IME、Google日本語入力、Baidu IMEの4種類です。詳しい中身はわからないので、全部あわせても数ページ程度の紹介です。
  • 日本語の文法の話についてはほぼ触れていません。もちろん、実用的な物をつくろうとすると日本語そのものと向き合うことはどうしても避けられないのですが、それだけで一冊の本になってしまうこと、今の私には書ききる力が無いことから、バッサリと省略しました。

感謝

　謝辞にも書きましたが、多くの方にレビューしていただき、多くの改善がなされました。特に小町さんには全体にわたって何度もチェックしていただきました。レビューによるクオリティの向上は通常どれぐらいのものなのかはわかりませんが、この本に関して言うと相当な向上が行われました。大変感謝しております。もちろん、残った間違いやわかりづらい部分は筆者の責任です。
　また、すでに何人かの方には 宣伝 して いただいて おり、ちょっとハードル上げすぎな感もありつつ、感謝しております。また、ステマと言いながら全然ステルスではない宣伝をしてくださった 皆 様 にも感謝しております。

リンク

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

　やっと一息ついたので。

2011年振り返り

  • 余暇の時間はほとんどを本の執筆に使った。
  • 余裕がなかったせいでやると言っていてやらないといった不義理があったので、キャパオーバーな状態にある期間を減らしていきたい。
  • 無茶なことを引き受けて精神を消耗するみたいな事例がいくつかあったので、積極的に断る力を発揮していきたい。

2012年の目標

  • 英語
    • 去年IJCNLPに行ってきて英語力の不足をかなり感じた。また、海外のニュースサイトなんかも能力不足で時間がかかりすぎて実質的に読めないことが多い。だいぶ能力が足りないと感じている。学校行こうかな…。
  • ダイエット
    • 体重を減らす方法はだいたいわかった。週2でジムに行って外食を控えればよい。BCAAで筋肉痛に対処できることがわかったので、後は時間に余裕さえあれば週2は実現可能である。
  • bell
    • コードを整理して公開する。
  • dual decomposition（を使ったargmaxの素敵な求め方）
    • Rushのチュートリアルを読んで大体理解できたんだけど、まだ実装はできる気がしないのでもうちょっと勉強して実装したい。RushのチュートリアルはSontagのイントロダクションより例が多くて分かりやすいのでお勧め。
  • MCMC
    • 簡単なのは実装できる（正規分布のパラメーターをサンプリングするとか）けど、複雑なのはまだ無理。PCFGのslice samplerぐらいまで実装できるようになりたい。
  • suffix array
    • multi key quicksort, dc3, saisあたりを実装してみたい。
  • Goliath
    • node.jsはちょっと使ってみてめげたのでちょっと違うアプローチにチャレンジしてみたい。
  • raphael.js
    • web系技術勉強の一環として勉強する。
  • MathJax
    • web系技術勉強の一環として勉強する。

　全部ちゃんとできるとは思えないし、心の平穏も大事なので、ぼちぼちやっていこうと思います。

IM飲み会2011

　もう去年の話ですが。思ったことをメモだけ。

  • 自分の発表はもっと具体例を載せるべきだった。反省。
  • グラムさんの発表が自分の興味の方向と近くて特に興味深かった。
    • コンテキスト単語を全部突っ込むと学習ができないのはAdaptive Lasso的な感じで正則化をかければいけるんじゃなかろうかと思うが、明らかに実装がめんどくさいな
  • アカデミックよりな発表が増えているというのはまったくその通りだと思うので、来年は発表するならもっとゆるい発表内容にしたい。顔文字辞書生成と活用とかそんな感じで。
  • 飲み会だと誘われてきてみたらガチなワークショップだった…というパターンの人が結構居たらしい。
  • 人数多すぎてもうちょっといろんな人と話したかったけど話せなかった。来年はもっとうろうろする。

　今年も大変面白い会でした。小町さん、森さん、どうもありがとうございました。