2012年の総括

2012年の個人的な総括を以下にまとめます。

子供が生まれました

無事子供が7月に生まれました。毎日子育てに翻弄していますが想像していたよりも大変で楽しい時間を過ごしています。

また、妻が実家に里帰り出産したため夏の間は、毎週末妻の実家に帰り車を運転して病院・お店に行くという、まるで妻の実家で生活して月〜金は東京で働いているような感覚で過ごしていました。

高速文字列本を出しました

高速文字列の世界を12/27に出しました。

2012年の目標として本をだすということを考えていました。2010年夏頃から本の話はいただいていましたが、結婚、会社（途中から経営陣に入ってさらに時間確保が困難に）、子育てと時間確保がどんどん困難になっていきずるずると伸びてしまっていました。

しかし、文字列解析の話は小さいころから扱っていた話（もう10歳ぐらいからの付き合い）で一度まとめてみたかったというのもありますし、なにより私がこれからもっと時間確保が難しくなっていくだろう中で、今のこの時の考え、ノウハウを残し、伝えていかないと失われてしまうのではという危惧が強くあり、移動時間、深夜/早朝のちょっとした時間をちょこちょこ使って書き進めていきました。

この本をきっかけに、私が小さい頃nifty serverのデータ圧縮のフォーラムでデータ圧縮に出会い出会いのめりこんでいったように、興味を持っていただく人がでてきていただけたら幸いです

いくつか学校に行きました

グロービス

経営を勉強しようということで会社の同僚（@soshitw）の誘いでグロービスに通いました。ちょうど、PFIぐらいの大きさの会社の経営陣を対象にした短期のベンチャーマネジメントプログラムがあったのでそれを受講しました（グロービスの対象ページが消えちゃっているので他のところをリンク）。予習や授業はかなりの量・質でどちらも全力を出さないとだめでしたが、大変役に立ちました。参加者はみんな会社を興こし・経営している人たちばかりで考えや意見は常に鋭く本気であり、私が今まで交流のなかった違う分野の人たちも多くいたので大変勉強になりました。この授業を通し、純粋に経営にもっと興味を持つようになりました。

ベルリッツ

海外の企業とのお付き合いもいくつか始まり、英語は学ばないとなぁということで、会社の補助制度もできましたし、ベルリッツに行ってみました。
英会話は学生時代ESSにいて、なんちゃって英会話（聞こえているふり、話せているつもり）ができているつもりですが、通ってみると大分まだまだなのだなというのもわかりました。ただ、通う期間の半年ぐらいでは何ともならないというのも分かったので、これを英語学習は今後も続けていこうと思っています。

画像映像解析・バイオはじめました

今後伸びていく分野であろう、画像・映像解析、バイオについての勉強をはじめました。まず教科書をダーっと読んで、論文読んで、この分野の専門家の方々にあってお話を伺うということを進めています。元々いろんな分野をつまみ食いしてきているので違う分野のところのぞいてみるということは好きです。

本をたくさん読みました

技術本もそうですが、それ以外にも会社ではオススメ本紹介の会があるのですがそこでお勧めされた本や、いろんな人の回顧録を読みました。あとkindleが出てきた後は新書・マンガを大量に読みました。読みたいなと思ってすぐ買って読める便利さはすごいです。

やせました

去年の個人的な大きな目標として、健康になり痩せるということを掲げていました。健康診断の結果、やせろという明確な指示がでていたからです。結果1年で10kg（殆どは年の前半で8kg）やせました。2年前からは18キロ近くやせました。昔が大きすぎた。
やったことは、毎朝必ず体重を測るということ、野菜から食べるということ、歩けることは歩くこと（一駅ぐらい）でした。体重記録はsimple weightというアプリがとても便利でした。

また、健康になることが目標だったので、この本とか参考になりました。
医師がすすめる男のダイエット (集英社新書 539I)

頭痛とたたかいました

やせたのはやせたのですが年末はひどい頭痛と戦いました。2年前も1ヶ月程度頭痛と戦った経験があり、偏頭痛と思っていたのですがどうにもつらいということで、頭痛専門の病院を見つけて行ったら痛さで有名な群発頭痛ということでした。この痛さと戦う経験をすると、残りのことは何でもすばらしく感じられるようになります。仕事中/講演中に急に頭痛がきたらどうしようという不安もありましたが、家族や会社のサポートもあり、なんとかなり大変感謝してます。今は期間も終わりに近づき、医者から頂いた予防薬も効き、万一痛くなったとしても自己注射を持ち歩いているので数分で何とかなるということで平常の生活に戻ってきています。

教訓として、病気の時、いい病院、医者に出会うことがどれだけ大切かを思い知らされました。（私が頭痛で最終的にたどり着いたのは喜多村脳神経クリニックでした。もし頭痛で困っていたらお勧めです）

---
昨年もみなさまに大変お世話になりました。
2013年もよろしくお願いします。

本の紹介：「SONYの旋律」、「植村直己シリーズ」

最近読んだ本の中でお薦めのものの紹介です。

どの本も出てからしばらくたつ物で、既に読んでいる人も多いかもしれませんが、まだ読んでないかもしれないのでお薦めします。私も知りませんでした。

（もう偉すぎるので敬称略で書きます）

- SONYの旋律

SONYの黄金時代を築いた大賀典雄の話。今年の4月になくなったというのがニュースになり、そういえば読んでみたかったと思い出し、読んでみました。

SONYは井深、盛田という二人の創業者が作ったというのが有名だが、その後にグローバル化を進め、メディアやゲームなど他の分野も巻き込み現在のようなソニーを創り上げたのが大賀である。

大賀は、芸術分野でも芸大を出た後にドイツベルリン国立芸術大学を主席で卒業し、音楽の分野でも活躍することは間違いなかったが、彼はその後、ソニーに入り、SONYブランドを確立させ、また音楽・映画などのソフト分野を開拓し、現在の世界のSONYを創り上げていく。

この経歴を昔聞いたことがあった私はなんでそうなったのと思っていたが、この本では、大賀が小さいころから電気、電子にも非常に詳しく、また音楽の分野で活躍している間も、井深、盛田の二人が後継者の候補と目をつけて、いろいろしていたというのが詳しくかかれている。この他にも大指揮者カラヤンとの公私に渡る関係や、CDが生まれるまでの話など盛りだくさん。

また戦後、日本の産業がどのように成長していったのかを見ていくことができて面白い。

技術に生きる人だけでなく、人生の過ごし方の指針にもなり、お薦め

- 植村直己シリーズ
青春を山に賭けて
極北に駆ける

とりあえず最初の二つの本の紹介。

植村直己は世界の大冒険家であり、今の多くの冒険家が憧れとして知っている人である。私も国民栄誉賞をとったのだとか、冬のマッキンリーで姿を消したままというのは知っていて、いつかは読んでみたいと思っていた。

植村が、明大の山岳部を出た後に、ヨーロッパの海外の山も登りたいと、アメリカ行きの船に密航し、ついた先で不法労働者としてお金を稼ぎ、強制送還されるところを必死で説得しヨーロッパに飛ばされ、次に山につき、言葉が全く通じないところで必死に働き信頼を勝ち取っていく。次にアフリカの山に登りたいと思い、アフリカに行きのその帰りにエヴェレストに日本隊が登るというので直接エヴェレストに向かう。

もう展開が嘘だろというようなもの続きで、山とか川を下る冒険だけでなく、生き方がもう冒険続きですごすぎる。

二冊目の極北を駆けるという方も、犬ぞりを学びたいということで、エスキモーのところに直接行き、そこで現地の人と一緒に過ごしはじめ、トイレとかは室内でダイレクトにやるとか、腐りかけの生肉がぶらさがってて、それをナイフできって食べるだとか、そういうのもこなしていき実際に現地の生き方を学ぶ。最後の犬ぞりでの縦断記録は、特に後半スリル満点で面白い

他の冒険家の話もいくつか読んだことがあるのだが、みな文章での伝え方がうまい気がする。体験したことを伝えたいという気持ちが特に強いからだろうか。

本の紹介：「SONYの旋律」、「植村直己シリーズ」

最近読んだ本の中でお薦めのものの紹介です。

どの本も出てからしばらくたつ物で、既に読んでいる人も多いかもしれませんが、まだ読んでないかもしれないのでお薦めします。私も知りませんでした。

（もう偉すぎるので敬称略で書きます）

- SONYの旋律

SONYの黄金時代を築いた大賀典雄の話。今年の4月になくなったというのがニュースになり、そういえば読んでみたかったと思い出し、読んでみました。

SONYは井深、盛田という二人の創業者が作ったというのが有名だが、その後にグローバル化を進め、メディアやゲームなど他の分野も巻き込み現在のようなソニーを創り上げたのが大賀である。

大賀は、芸術分野でも芸大を出た後にドイツベルリン国立芸術大学を主席で卒業し、音楽の分野でも活躍することは間違いなかったが、彼はその後、ソニーに入り、SONYブランドを確立させ、また音楽・映画などのソフト分野を開拓し、現在の世界のSONYを創り上げていく。

この経歴を昔聞いたことがあった私はなんでそうなったのと思っていたが、この本では、大賀が小さいころから電気、電子にも非常に詳しく、また音楽の分野で活躍している間も、井深、盛田の二人が後継者の候補と目をつけて、いろいろしていたというのが詳しくかかれている。この他にも大指揮者カラヤンとの公私に渡る関係や、CDが生まれるまでの話など盛りだくさん。

また戦後、日本の産業がどのように成長していったのかを見ていくことができて面白い。

技術に生きる人だけでなく、人生の過ごし方の指針にもなり、お薦め

- 植村直己シリーズ
青春を山に賭けて
極北に駆ける

とりあえず最初の二つの本の紹介。

植村直己は世界の大冒険家であり、今の多くの冒険家が憧れとして知っている人である。私も国民栄誉賞をとったのだとか、冬のマッキンリーで姿を消したままというのは知っていて、いつかは読んでみたいと思っていた。

植村が、明大の山岳部を出た後に、ヨーロッパの海外の山も登りたいと、アメリカ行きの船に密航し、ついた先で不法労働者としてお金を稼ぎ、強制送還されるところを必死で説得しヨーロッパに飛ばされ、次に山につき、言葉が全く通じないところで必死に働き信頼を勝ち取っていく。次にアフリカの山に登りたいと思い、アフリカに行きのその帰りにエヴェレストに日本隊が登るというので直接エヴェレストに向かう。

もう展開が嘘だろというようなもの続きで、山とか川を下る冒険だけでなく、生き方がもう冒険続きですごすぎる。

二冊目の極北を駆けるという方も、犬ぞりを学びたいということで、エスキモーのところに直接行き、そこで現地の人と一緒に過ごしはじめ、トイレとかは室内でダイレクトにやるとか、腐りかけの生肉がぶらさがってて、それをナイフできって食べるだとか、そういうのもこなしていき実際に現地の生き方を学ぶ。最後の犬ぞりでの縦断記録は、特に後半スリル満点で面白い

他の冒険家の話もいくつか読んだことがあるのだが、みな文章での伝え方がうまい気がする。体験したことを伝えたいという気持ちが特に強いからだろうか。

今後、技術的な記事はPreferred Researchの方に書きます

こちらのブログの更新がだいぶ止まってしまっていましたが、今後、技術的な話題については、基本的にPreferred Research Blog の方に書いていきます（もし読んで無い方がいたら既にいくつか書いていますので観てみてください）。それ以外にもtwitter @hillbigの方でも書きます。

このブログでは、技術的な話や会社の話以外の個人的な話や本の紹介とかをすることにします。
よろしくです。

オンライン最適化とRegret最小化

大量のデータから、何か有益な情報を求める問題の多くは最適化問題を解くことに帰着されます．
最適化問題とは与えられた関数fの値を最小（最大）にするような変数xを探すといった問題です。

例えば、機械学習（これを利用する自然言語処理、情報検索など）、画像処理、AI(ロボットの経路制御）、
など多くの分野で最適化問題は登場します。

その中でもオンライン最適化（機械学習の文脈でいえばオンライン学習）と呼ばれる最適化手法は
実用性の高さと実装のしやすさから多く利用されるようになってきました。

このオンライン最適化は近年Regret（後悔）最小化というゲーム理論などで使われていた枠組みで
解析されることが多くなってきました。

今回はこのRegret最小化について簡単に解説してみようと思います。

（機械学習が詳しい人向けに補足すると、VC次元など他の機械学習を解析する手法と比べてRegret最適化の面白い点は入力、最適化関数に対する仮定が非常に少ない点、有限回数に対する収束度合いを求められ、それがタイトな場合が多い点などです。）

厳密な議論については[1]を参考にしてください。

Regret最小化の問題設定は次の通りです。

プレイヤーは毎回、可能なアクション集合Kから一つのアクションx∈Kを選択します．
その後に関数fが提示され、コストf(x)が決まります。
この操作を何回も繰り返していきます。t回目のアクションと関数をそれぞれx_t、f_tとします。ここでf_tは必ずしも同じでなく毎回違ってもよいものとします。

この時、プレイヤーは合計コストf_1(x_1)+f_2(x_2)+...+f_t(x_t)をどのようにすれば最小化することができるでしょうか。

合計コストで戦略をそのまま評価するには関数を自由に決められるのでどんな戦略に対しても
コストを無限大にすることができるので問題設定として面白くありません。

そこで、同じアクションしかとらない固定戦略の中で最も合計コストが少なくなる戦略が達成する合計コストとの差を考えてみます。これを「あの戦略をとっていればよかったのに・・」との差を測る指標というわけでRegret（後悔）と呼びます。

もう少し詳しく説明してみます。T回ラウンドが進んだ後に、時間を巻き戻して合計コストが最小になるようなアクションをx^*を一つ選びます。

この時、ある戦略AのRegret(A)とは、最適の固定戦略と実際にとった戦略との合計コストの差をいいます。

Regret_T(A) = (f_1(x_1)+f_2(x_2)+...+f_t(x_t) ) - (f_1(x^*)+f_2(x^*)+...+f_t(x^*) )

さて、この値がどのような意味を持つのかについて考えてみましょう

Regret_T(A)が試行回数Tに対し線形（O(T))であれば、どれだけ回数を重ねても最適な戦略との差は埋まりません。
それに対し、Regret_T(A)がTに対し線形よりも少しでも小さければ(o(T))、試行回数を重ねるにつれ、最適な固定戦略と戦略Aによる
1回あたりのコストの差は0に近づいていきます。つまり、_1...f_tがどのような形をとっても最適な固定戦略に限りなく近づくことが言えます。

このRegret最小化問題はオンライン最適化を特殊ケースとしてふくんでいます

関数fが与えられた時、その値f(x)が最小となるような入力x=x^*を求めるのが最適化問題でした。
オンライン最適化の場合は毎回関数が固定であり、プレイヤーのアクションは毎回その時点での最適化結果に対応します。

この場合Regret_T(A)はfの最適値f(x^*)と、現在の最適化結果f(x_t)との差の合計となります。Regret_T(A)=o(T)を達成するような戦略は最適値を見つけられるようなオンライン最適化であることがいえます。

オンライン学習の例をみていきましょう
機械学習の目標は（すごい大雑把にいえば）訓練例とパラメータθで特徴付けられる学習器F（θ)が与えられた時、
訓練例を全て正しく分類してくれるようなパラメータθ^*を求めることです。

オンライン学習の場合には毎回訓練例が一つ与えられ、それを利用して現在のパラメータを更新します。

t回目の関数f_tをt番目の訓練例を正解した時0, 不正解の時に1となるような関数に選ぶことで、Regret_T(A)は最適なパラメータθ^*を利用した場合の不正解数と、現在のオンライン学習の不正解数の差となります。

Regret_T(A)/Tが0に速く近づけば近づくほど、より高速な学習が達成できることになります。

====

もう少し実際の問題に近づけてみましょう

- 各関数 f_tが凸関数（f_1..f_tが同じ関数である必要はない）
- とりうるアクションxが凸空間中の点（多くの場合m次元ユークリッド空間中の点）

まず最初に最も単純な戦略Follow The Leader(FTL)を紹介します。

この戦略ではt回目のアクションx_tを次のように決定します

f_1(x) + f_2(x) + ... + f_{t-1}(x) を最小化するようなアクションxをx_tとする

一見よさそうな戦略ですが、f_1...f_{t-1}とf_tの間に何も仮定をおいていない点に注意してください。
f_t(x_t)を最小化したいのに、それと全く関係の無いf_1...f_{t-1}を最小化するxを選んでいるわけです。

実際、この戦略がうまくいかないようなコスト関数の例を作ることができます。
例えば、アクションが一次元中の-1<=x<=1中の点だとし、f_i(x) = (1/2)(-1)^{i}x という関数がi回目に来るとすると
FTLの戦略のとるアクションは最初は0のあと、-1,1,-1..1となりコスト値は常に1です。
それに対しこのコスト関数列に対する最適な固定戦略はx=0であり、コストの合計値は0です。
よって、Regret_T(A)=T-1であり、縮まることがありません。

どのように改善できるかを考えてみると、最適な固定戦略との差を評価している以上、毎回のアクションが大きく変わって
しまわなければよさそうです。そこで、t回目のアクションx_tを次のように求めてみることを考えてみます

f_1(x_t) + f_2(x_t) + ... + f_{t-1}(x_t) + 1/C R(x_t)を最小化するようなアクションx_t

但し、R(a)は正規化項でaから実数への関数、Cは学習時のパラメータです。この戦略をRegularized Follow The Leader
(RFTL)と呼びます。

このRFTLはいくつかの重要なオンライン最適化法をふくんでいます。
fが線形関数、xがシンプレックス上にあり、R(x)=-x log xの場合、RTFLはmultiplicative
updateと一致します（x_{t+1} ∝ x_t e^{-C f_t'(x_t)})
fがxの線形関数、xが単位円上にあり、R(x)=|x|_2^の場合、RTFLは勾配降下法に一致します（x_{t+1} ∝ x_t - Cf_t'(x_t))

そして、RTFLはFTLと非常に似ているのにも関わらずどんなコスト関数に対してもうまくいきます。
つまりRegret_T(A)=o(T)を達成します。

具体的にはRegret_T(A) <= 2(λDT)^{1/2}です。但し、
λは{f_i}とRによってのみ決定される定数、
Dは正則化関数とx^*, x_1によってのみ決定される定数です。

証明はコーシー・シュワルツの定理とテイラー展開を使って比較的素直に導出できます。（[1]を参照）

この結論は、もちろんその特殊な場合であるオンライン凸最適化にも適用できます。
つまりこのFTLという単純な戦略は正則化項を入れることにより、どんなコスト関数がやってきても動的に対応でき、常に最適解に漸近する戦略に化けます。

# コスト関数を調整することで、いくらでもRegretを増やすことができるように思えますが、
　この戦略を騙すように、コスト関数を調整すればするほど、最適な戦略が達成するコスト値も上昇し、
　結局Regretは大きくすることはできません。

===

最後に、最近の話を少しみてみましょう

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization,
J. Duchi, E. Haza, Y. Singer, COLT 2010 [pdf]

この手法ではRegret最小化を詳細に分析することにより、現時点で最も高速に収束し、任意の損失関数、正則化（L1正則化も含む）を利用できるようなオンライン最適化アルゴリズムを構成することに成功しています。

通常の正則化に加え、Regret自体が小さくなるような正則化項を入れて更新即を導くと
他のオンライン最適化（例えばCWやAROW）が行っているのと同じように確信度が高い次元に対しては更新幅を小さくしそうでない場合は大きく更新するような更新即が自然と導くことができます。

この手法では任意の損失関数、正則化が使えるので、例えばL1正則化を併用することでCW, AROWと同程度の性能でありながら、多くのパラメータが0であるような結果を得ることができます。

また、結果として得られるパラメータの更新即は非常にシンプルで実用的です。

==

Regret 最小化については以下の簡潔によくまとまったサーベイが参考になります。
今回の解説の例や解説も以下から引用いたしました。
[1] "The convex optimization approach to regret minimization", E.Hazan, [pdf]

買ってよかったもの 2010秋

寒くなってきましたね。

日々働いております。
今年、私が衝動買いしたもので、今でも使っているよかったものを気分転換に紹介してみます。
純粋にオススメしたい＆面倒なのでリンクありません。

電気製品

* amazon kindle 3
-- 非常に良い。読みやすい。薄い。軽い。バッテリー１ヶ月ぐらい持つ
-- でも現在基本洋書しかないので洋書読めない人はまだ待ちかも。洋書読める人にとっては本が欲しいとおもって５分後には手元で読めるこの改善はすごい。今まで１ヶ月とか待っていたのに。
-- 通勤中にたくさん本読めました

* ipad
-- 家ではもとからPCは殆ど使わなかったが、ipadが来て家では殆どipad使ってる
-- pdfとか読むのにこれ使う。私はaoe3のプレイ動画とか見てる
-- 周りの評判は半々。PCのヘビーユーザーは使わないかも。

* torne
-- PS3持っていて、HDDレコーダーがないならこれで。デジタルチューナーもついてる。操作性すごい良い。
-- これに1TBぐらいの外付けHDDをくっつければ完璧

* SSD (for thinkpad)
-- 1万ぐらい安いのでthinkpadがスーパーパワーアップ
-- 環境吹っ飛んだらこわいから博論終わるまでずっとSSDは換装しなかったが、しておけば博論の質が変わったに違いない

本

（以下のは全部kindleで読むために洋書版を買いました。
　日本語訳版でも、どれも評判がよいです）

* Clean Code アジャイルソフトウェア達人の技
-- プログラミングする際に守るべき指針が簡潔に正確に書かれている。本当に勉強になった
-- 例えば　関数は短く、二つ以上のことはしてはいけない、
　　コメントで書くよりソースで表現することを頑張れなど（コメントはメンテされず情報を正しく伝えられない）

* レガシーコード改善ガイド
-- レガシー（時代遅れで古い）コードをいかに改善していくか、とかいてあるが多くの人のコードがあてはまる。
-- 私のコードのことばかり書いてある
-- テストされていないコードは全てレガシー。テストがなければ、そのコードを容易に改良、変更、拡張できなくなる。レガシーなコードを現実的にどのように対処していくかが述べられる
-- プログラミングの設計の際、テストしやすい設計は優先事項

* アジャイルな見積りと計画づくり
-- 見積りと計画づくりはなんどやってもうまくいかなかったがかなり勉強になった。
-- 研究計画とか人生とかも似たような話だとおもった。
-- もっとも重要なモチベーションをいかにあげるかという点についてはまた別の本で

* Hadoop: The Definitive Guide, Second Edition
-- Hadoopの解説本の最新版。なんでもHadoopでやればいいってものではないと思っていたが、この本の前半に書かれている、歴史や背景の部分で、なぜhadoopの仕組みが必要になってきたが非常に分かりやすく書かれて、説得された。
-- 記憶媒体（例：HDDドライブ）の容量がこの２０年で約１０００倍になったが、転送速度がたった２０倍にしか速くならなかったのが全ての問題の元凶。データ保存できるけどそのままだと使えない、、といったところから話が始まる

* Fundamentals of Matrix Computations, David S. Watkins
-- 行列についてちゃんと勉強しておこうとおもって買った。面白かった
-- SVD、ランチョス、クリノフ部分空間とかその周辺の話をきちんと抑えられる

何かオススメがあったら教えてください（mbaは存じあげております）

行列分解ライブラリredsvdを公開しました

大規模疎行列向けの行列分解ライブラリredsvdを公開しました．
redsvd

大規模疎行列向けの特異値分解や主成分分析，固有値分解を行うライブラリredsvdを公開しました．
修正BSDライセンスで公開しており，コマンドラインから使える他，C++ライブラリが用意されています．

例えば，行と列数がそれぞれ10万，非零の要素が1000万からなる疎行列に対する上位20位までの特異値分解を約2秒で処理します．

特異値分解とか，使っている技術の詳細とか応用事例を以下に簡単に紹介しましたので，興味のある方は参考にしてください．

特異値分解とは

まず行列を適当に復習します．行列Xの転置をX^tと表すことにします．またIを単位行列とし，Oを全ての成分が0である零行列とします．また，行列XX^t=IであるようなXを直交行列と呼びます．Xが直交行列の時，Xvはベクトルvを長さを変えずに回転させます．ここでは簡単のために，成分が全て実数である実行列のみを扱いますが，一般の場合では直交行列をエルミート行列と読み替えてください。

n行m列の行列Aが与えられた時，この行列はつぎのように必ず分解できます．この分解を特異値分解（SVD: Singular Value Decomposition)と呼びます．
A = USV^t
ただしU，Vはそれぞれn行n列，m行m列の直交行列であり，Sはn行m列の対角行列（対角成分以外は0）です．Sの対角成分は大きい順に並んでいるとします．これらを特異値と呼びます．UとVの列ベクトルをそれぞれ左特異ベクトル，右特異ベクトルと呼びます．Aを線形変換としてみた場合，A = USV^tという変換は任意の線形変換は，回転・軸毎のスケーリング・回転という三つの連続した操作に変換できることを意味します．

ちなみに
Ax = r xであるようなベクトルxをAの固有ベクトル，rを固有値と呼びます．それに対し特異値ベクトルの場合は
u_iA=s_i v_i
Av_i=s_i u_i
のような関係があります．但し，u_i, v_iはそれぞれU, Vのi列目の列ベクトルです．Aが対称行列の場合は，特異値分解A=USV^t=VSU^t=A^tとなり，V=Uとなって，固有値分解U^tAU = S（A=USU^t)に対応しますので，特異値分解は一般行列への特異値分解の一般化と見ることもできます．

この特異値分解は行列の"マスターアルゴリズム"であり，これさえできれば，線形方程式を効率的に解けたり，他の有用な行列分解（LU, QR）を効率的に求められたり，Aが観測行列の時、データ解析ができたりする非常に有用な分解です．例えば主成分分析は，主成分方向がVの各列であり，各サンプルの主成分スコアがUSの各列に対応するので特異値分解そのものです．レコメンデーションや画像索引，HMMの最尤解を求めるなどSVDの新しい使い方については最後の方で説明します．

特異値分解を理解するために別の表現をしてみます．先程の特異値分解で，Sが対角行列であることを利用して式を並び替えると，次のように表現できます
A = \sum_i s_i u_i v_i^t
但し，u_i, v_iはそれぞれU, Vのi列目の列ベクトルであり，s_iはi番目の特異値です．T_i = u_i v_i^tとした時T_iはAと同じサイズであり，また行と列の自由度は1であることから階数(rank)は1です．さらに，U, Vが直交行列であることからi≠jの時T_i^t T_j = Oとなり，{T_i}はお互い直交しています．よって，特異値分解はAをrankが1で直交している行列の重み付き和として表現していることになります．

この表現から導けることとして、Aの階数がrの時，Aはr個の行列の和A = \sum_{i=1...r} s_i u_i v_i^tで表せます。

これはさらに強いことがいえて，Sの要素のうち，i>rのときs_i=0とした行列をS~とした時，行列A~=US~Vは，階数がrである任意の行列の中でAとの二乗距離が最小であるような行列となっています．つまり階数rの中でAの最良の近似がA~となっていることになります．

S~の0となっているのに対応する部分をUとVから取り除き、U~,V~をそれぞれn行r列の直交行列とし，S~をr行r列で対角成分に特異値が並んだ対角行列とした時、A~=U~S~V~となります．

これをtruncated SVDと呼びます．

実世界から得られる多くの行列は，行数，列数に比べ実際の自由度は小さい場合が多いです．先程の文書・単語行列の例でいえば，同じような単語集合が同じ文書で出現するなどです．そこで上位の特異値のみからなるSVD，つまりtruncated SVDを行うことで、実際のAの情報をコンパクトに表現することができます。

また、多くの成分が0であるような行列を疎行列と呼びます．例えば，行が文書，列が単語に対応し，i行j列の成分が文書iに単語jが出現した時1，そうでなければ0であるとして，作られた文書-単語行列Aは非常に疎になります（英語Wikipediaの例だと非零の割合は0.1%）．レコメンデーションで使われるような行が購入者，列が購入したアイテムに対応する行列も疎行列の代表例です．従来の疎行列向けの固有値分解では，クリノフ部分空間を利用した手法が多く利用されていました。

redsvdが利用しているアルゴリズム

redsvdは次の論文で紹介されている乱択化アルゴリズムを元にしています．

"Finding structure with randomness: Stochastic algorithms for constructing approximate matrix decompositions", N. Halko, P.G. Martinsson, J. Tropp, arXiv 0909.4061 [pdf] [nips tutorial slide]

オリジナルのアルゴリズムが一方向のみにサンプリングしているのに対し，redsvdでは行と列の両方向でサンプリングをしていますのでそのまま論文で述べられている解析は適用できませんが、多くの場合うまくいっているようです。

今回利用している乱択化アルゴリズムが従来の乱択化を用いた手法とと違うのは，結果が非常に高い確率で真の値に一致するということです．オーバーサンプリングを利用することでさらに精度をあげることができます。redsvdを利用する場合は実際に欲しいrの値よりちょっと多め(+5ぐらい）に求めておき、上位だけを取り出すことで実現できます。詳細については上記論文を参照してください．

では具体的なアルゴリズムを紹介します．

n行m列の行列Aに対し上位r個の特異値に関する特異値分解をすることを考えてみます． 初めに各成分が平均0，分散1のGaussianからサンプルされたn行r列のGaussian行列Oを作ります． 次に，Y = A^t Oを求め，Yの各列を正規直交化します． この時AYY^t ≒ Aが成り立ちます． n行r列のB = AYを求めます． AはYによって列方向に圧縮していると考えられ，Y^tを書けることで元のAに復元できます．そして扱うのは圧縮した状態であるBです． 次に同様の方法で行方向に情報を圧縮します。 まず，各成分が平均0，分散1のGaussianからサンプルされたr行r列の行列Pをサンプリングし，Z= BPを求めます．そしてZの各列を正規直交化します． B = Z Z^t Bが成り立ちます． 最後にC = Z^t Bを求めます． Cはr行r列の行列であり，Z^tによってBを列方向に圧縮し，Zで復元できると考えられます．最後にCに対してSVDを従来手法で求め，C=USV^tを得ます． Cは非常に小さい行列なので，この部分は高速に行えます．

A = AYY^t = BY^t = ZZ^tBY^t = ZCY^t =ZUSV^tY^tとなります． ZU，YVは直交行列であり，それぞれAの左特異ベクトル，右ベクトルに対応します． またSはAの特異値が対角にならんだ対角行列です．

Eigenについて

以前C++の便利ツールとしてEigenを紹介しましたがredsvdはそれをフルに利用しています．例えばコア部分のコード(redsvd.hpp)は15行ぐらいです．疎行列の利用の仕方とかはredsvd.cppのconvertFV2Matとかを参考にしてみてください

特異値分解の応用

特異値分解は，解が一意に求まり（ベクトルが逆方向とか特異値が同じ場合の自由度はあるものの），しかもそれを効率的に求める手法が存在するという大きな利点があります．これは他のクラスタリング手法や隠れ層があるような手法には無い大きな特徴です．

SVD自体は古くからある技術であり，一度は様々な分野に応用されていましたが，最近再度，その重要性が注目されてきているようです

- 教師無学習による品詞推定
-- "SVD and Clustering for Unsupervised POS Tagging", M. Lamar, Y. Maron, M. Johnson and E. Bienenstock, ACL 2010
-- 各単語の前方コンテキストのBigram行列と，後方コンテキストのBigram行列をそれぞれSVDして，(USだけを利用して）隠れクラスタを求めた後にそれを特徴量としてクラスタリング．現在教師無学習の品詞推定で最高精度

- 索引
-- "Spectral Hashing", Y. Weiss, A. Torralba, R. Fergus, NIPS 2008
-- 以前記事にかいたり，WEB+DB Pressで記事を書きましたが，要は制約ありのグラフ分割問題に帰着して主成分分析で解く．

- 隠れマルコフモデル
-- "A Spectral Algorithm for Learning Hidden Markov Models", D. Hsu, S. M. Kakade and T. Zhang. COLT 2009
-- 隠れマルコフモデルの学習を従来のEMのような更新式で求めるのではなく，bigram,trigramの統計量からのSVD一発で求める
-- 高橋さんによる解説スライド [pdf]

もちろんスペクトラルクラスタリングなどにも利用できるでしょう。

今回のredsvdを利用して従来SVDや固有値分解が適用できなかったいろいろな手法に試していただければ幸いです．

redsvdの名前は普段飲んでいる飲み物由来でつけました。
なお，redsvdはPFIの20%プロジェクトで作りました．今後も何かできたら公開していきます．

C++の便利ツール・ライブラリ

フルタイムで働きはじめて4ヶ月。
いろんなことがありました。

今日はインターンが来ているということもあり日頃のC++コーディングライフの中で大変重用しているツールを紹介します。といってもどれも有名なツールでググれば解説がでてくるとは思いますので、一言ずつだけ紹介してみます。みなさんも何かよさげなライブラリ・ツールがありましたら教えてください。

- valgrind/callgrind/cachegrind

プログラムの実行結果を解析するツール群。まぁ、王道であえて紹介する必要はないかもしいませんが.。valgrindはプログラムのどこかでメモリが漏れているかどうかのチェックに使います．コードのどの部分で確保した領域がどこで漏れているかまで追跡することができます
　 valgrind --leak-check=full command

プログラムのどのが計算量的にボトルネックになっているかを調べるにはcallgrindを使います。ソースのどこで何クロック使っているかのレベルでわかります
　 valgrind --tool=callgrind command
　 callgrind_annotate -I=ソースの場所 --auto=yes callgrind.out.xxxx

cachegrindはcallgrindと同様にプログラムのどこで何回キャッシュミスしているかどうかを調べることができます。

- gtest

かゆいところに手が届くGoogle製C++テストフレームワークです。他のテストフレームワークを使ったことがないのでなんとも言えないですが、これでかなり満足しています。テストをちゃんと書かないとやっぱりだめですね。

- glog

Google製ロギングライブラリでサーバーなどを書いてログを吐く場合に使う。ずっと使い渋りをしていたが、使ってみるとこんなに便利なことはないと思う。面倒なログローテーションとかもやってくれるし落ちた時はどこで落ちたかも教えてくれる。gflagsを介した初期化をしたくないので、初期化の際、間に一つ挟んで使っています。

- re2

Google便利ツール三つ目、正規表現ライブラリ。これも直感的に使える。従来の多くの正規表現ライブラリは最悪時の計算量は爆発するが、re2は正規表現長に比例する計算量で必ず動作する保障があります。

- cmdline

tanakhさんが作ってくれたコマンドラインパーサー。fujimapでの使用例．gflagsは大きすぎるので、もっとコンパクトでヘッダだけのやつ作ってと頼んだらさらっと作ってくれた。

- waf

Pythonベースのビルドシステム。autotoolsがいくらたってもよくわからないところに現れた．といってもこれもよくわからないが最近良く使います。tanakhさんの解説が重宝します。

- openMP

共有メモリ型計算機環境下においてマルチスレッドなプログラム書くのに比べ圧倒的に簡単に並列化できる。ディレクティブをいれる形で並列部分を指示するのでopenMPが利用できない環境では勝手に無視されるのもよい。依存関係がないforではとりあえず使ってみてます。

- Eigen

最近特に使っている行列ライブラリ。C++上でmatlabのように直感的に書けて、しかもかなり速い(Eigen3βとかはGOTO BLAS並らしい）。SSE使えるときはつかってくれる。ヘッダファイルをコピーするだけでよい。解説記事がみあたらないので今度解説記事かいてみようかな。

大規模文字列解 析の理論と実践＠IBISML

IBISML 第一回研究会の招待講演での発表資料です。参考文献などを追加しました。

"大規模文字列解 析の理論と実践" (pdf|pptx)

最初はもっとサーベイ的にしたかったのですが、まとめあげられず、テーマを部分文字列の計量に絞ってやりました。後半の予備スライドにそのへんの名残があります。

本番で口頭で説明したところは、スライドだけだと追いづらいかもしれません。

---

研究会は武田ホールで立ち見がでるくらい盛況でした。
プログラムを見ていただければわかるとおもいますが、みなさん非常に濃い内容でした。
久しぶりのこうした研究会参加で大変刺激になりました。

博士生活振り返り

ずっとドタバタしていたのですが、ようやく新しい生活のリズムがでてきました。

無事、情報理工学の博士号を取得して卒業し、4月からPreferred Infrastructureでフルタイムで働いています。
研究方面からのお誘いもいろいろあったのですが、会社一本に専念しております。
ただ、研究活動はこれからも会社のバックアップのもとしていきます。

また、3月に結婚もしました。

年明けから博士卒業、結婚の二本柱に加えてNLPチュートリアル、会社の仕事とテンパってました。
なんとか体を壊さず乗り越えられたのはみなさんの助けです。

しかし、喉元過ぎると熱さ忘れるという言葉通り、「これはもうだめだろう」と追い詰められていた時の気持ちを既に忘れつつあります。

誰かの参考になるかもしれませんので、この時の気持ちも含め博士３年過ごして感じたことや、研究の話とかを思い出せる範囲で書いてみます。

---
私が修士に進学した頃は、就職もしくは起業を考えていて、博士への進学は殆ど考えていませんでした。博士に進もうと思い始めたのは研究に打ち込んでいき、様々な論文を読み、各学会で他の人と話をすればするほど、世界との差を感じ、もっと成長しなければと思ったからです。

この思いが決定的になったのは修士2年時のGoogleへのインターンでした（この時点では博士進学は決めていたが）。ここでは非常に優秀な人達と仕事をできたのですが、彼らの知識と経験の奥深さと幅広さには日々驚かされました。完全に理論の人だと思っていたらシステムのコードもバリバリ書けたり、その逆もいる。

基本的に、自分が想像できる範囲でしか、その人は成長することはできないと思っています。逆に目標となる自分を明確にイメージできれば、そうなることもできるのでしょう。このインターンでは、そうした人達をみることができ、そうした人に近づけるよう、まずは基礎固めをしなければと思い、会社をやりながら博士に進む道を選びました。

----
博士課程（とポスドク）は人生において、自由に研究テーマを決められて、じっくり勉強できる最後のチャンスだと考えてました。
プロジェクトチームに入ったり、会社に入ってからや、予算をとってからだと、なかなかそうはいかないからと思ってるからです。また、研究社会に自分を売り出す重要な時期だとも考えてました。

そうしたことをふまえて、私は博士で過ごしてた間は次のことを考えながら過ごしました。

(1) 基礎の勉強をする
(2) 研究を可能な限り自由に進める（やりたい）
(3) できるだけ多くのテーマ、分野に触れる
(4) 社会に貢献しアピールする

(1) 博士の前半は研究活動はそこそこに、ひたすら本と論文とコードを読んでました。特に数学、統計などの基礎力を高めるのに努力しました。こうした自己投資活動に時間をたくさんとれるのは博士進学の大きなメリットでした。

(2) 研究のテーマ、進め方、問題の処理の仕方について可能な限り自由にやっていきました。全く違う分野へ応用してみたり、共同研究をしたりなどです。そのため、できるだけシガラミがないように立ち振る舞いました。

(3) できるだけ多くの分野の様々な課題を取り組むようにしました。実際取り組んでみないと分からないことが多いし、また、ただやってみたかったからです。論文になってないのが殆どですが、小さいのも含めて課題、手法だと延べ５０ぐらいは試して作ったと思います。結果として一つの仕事に深く突っ込めなったのは残念だったかもしれませんが、今後これらの経験が生かされる日がくるのだと思ってます。

(4) 仕事をしたら、できるだけ早く論文、スライド、実装を公開するようにしました。また、本などの雑誌などに寄稿できる機会があれば積極的に書くようにしました。世の中に触れる人の量は「論文＜＜雑誌＜＜一般向けの雑誌＜＜実装」であることを常に心がけました。

--
さて、精神面の話です。

一番難しかったのがモチベーションの維持でした。もし、3年間やる気を全開にし続けられたら、10倍ぐらいの成果がでていたでしょう。実際はやる気が全くでない時期、パソコンを開いても全く論文が書けず、実験ができない時期というのがよくありました。

また、欝とまではいかないですが、言い知れぬプレッシャーと戦ってました。自分がやらなくても誰も何も言わないし、何をいつまでどのようにやるか全部自分で決められる、というのは最初はいいなぁと思ってましたが、途中からこれは何と厳しいことかと思いました。人の心は弱いので、こうした状況では何もしない楽な方向にまずいきます。そして研究が進まないことに不安になります。

これとはちょっと違う不安もありました。
以前、研究者の人達との飲み会で、突然アイディアがぱたっと出なくなるのではないかという不安が常にあるというという話がありました。研究者は、与えられたルーチンワークを日々やるわけではなく、どちらかというとクリエーターに似ているのだと思います。毎週締め切りがあり、何もないところからイメージを膨らませて作品を作っていく漫画家とかは本当に偉いと思います。頑張ってもどうにもならないかもしれないというのがありました。

モチベーションを上げ、不安を解消するためにいろいろ試行錯誤しました。

他の分野や外の人との共同研究というのはモチベーションをあげるのに良い手段でした。また、ワークショップや研究会などに出て刺激をうけたのも多々あります。私は何度も刺激的な研究・論文・人に出会い、やる気が0からMAXになったことがあります。

それでも、どうしてもダメなときがあります。こんなとき、よく効いたのは、「全く研究やらない」メソッドです。１ヶ月から２ヶ月ぐらい、やらない。こんなに離れて大丈夫かなと心配になってきてもやらない。そうすると研究がしたいという気持ちが自然とどんどん湧いてきます。抜本的な気分転換は私には非常に大切でした。

また、「目標を自分の能力にあわせて諦める・下げる」というのが大切だということを学びました。ネガティブなようにみえますが、とても重要なことだと思います。
ある目標を達成しようとして、達成できない⇒自分は駄目だ、といく前に、諦めるか目標を修正するようにしました。
自分が達成できるよりもはるかに高く目標を置いて無理をして生きていくのは、とても辛いことです。夢はもつべきだと思いますが、実際に行動に移すための目標は適切に設定されるべきだとつくづく思いました。

あとは、きついタスクは可能な限り小分けにするとやる気を出すのに効果的だとわかりました。大体１～３時間ぐらいの粒度までタスクを分解するとやる気がでてきます。前、本で読みましたが、人はやり始めるとやる気がでるそうです（面倒なことですが）。自分に簡単だなと思わせてやりはじめるのがよいのでしょう。

--
一番厳しい時期は博士論文書きでした。特に11, 12, 1月は論文と結婚と仕事で肉体的、精神的にいっぱいで、「これはもうだめだろう」とか、「今年の冬はこえられそうにない」とか毎日いってました。「これ終わったら結婚するんだ」というフラグが立っているという冗談をtwitterに書いて、本当になったらどうしようと思うほど追い詰められてました。

修士論文を書き終えた瞬間に、博士論文を書くのは苦労するんだろうなぁと思ってましたが、その想像を遥かに超えてました。夜に何度も締め切りに間に合わない、論文が受理されないという夢を見て起きました。

それでも何とか終えることができました。審査が終わったときは本当に嬉しかったです。そのあとしばらくはニヤニヤしてました。客観的に考えるとなぜそんなに大変だったのかと思えるのですが、それでも当事者の日々の精神状態は大変でした。

早めにストーリーをまとめ、書き始め、見てもらうのがやっぱり大切だと思います。
私は言われてましたができませんでした。

あとは今まで自分がやってきたことを振り返り、自信を持ち、耐える

--
さて、博士に進んでどうだったかです。

研究の基礎体力（知識・論文読み・書き・実装）は修士の頃と比べたらケタ違いに上がりました。例えば、あの修士入学当時もプログラミングはよくやってる方でしたが、今、その当時の実装を見ると相当やばいと思えるぐらいに成長しました（会社で学んだ事も多いが）。論文読み・書きも相当速くなったと思います。

あと、研究を個人でやっていくだけのスキルもまだまだ未熟ですが最低限はついたと思います。

---
会社と博士の二本立ての３年間、
たくさんの人にお世話になりました。ありがとうございました。

これからもよろしくお願いします。