The Tradeoffs of Large Scale Learningを読んだ

 The Tradeoffs of Large Scale Learning (L. Bottou and O. Bousquet, NIPS 2008) は、大規模データから機械学習を行う際のエラーについての考察を行った論文である。
 機械学習を行う場合、なんらかの損失を定義し、その損失を最小化するようにパラメータを調整する事が多い。また、最終的にその損失を0にする事は概ね不可能である。エラーが発生する理由を、さらに3つに分解する事ができる。

  • 真の確率分布を近似する際に発生するエラー(例えば、混合正規分布を単なる正規分布で近似したりすると、表現力が不足する)
  • 期待損失と経験損失で、最小化している物が違うために発生するエラー
  • 最適なパラメータと、現実的な時間で求める事ができるパラメータの差分として発生するエラー

 一つ目のエラーを減らすためには、できるだけ表現力の大きなモデルを選ぶべきであるが、あまり複雑なモデルを選ぶと二つ目のエラーが大きくなる。
 また、現実的な問題には、使えるデータサンプルの数と、計算に使える時間の両方に制限がある(学習に100年かかる、とかでは困る)。このどちらの制限が厳しいかは、学習用のデータセットが大規模であるかどうかで変わってくる。
 小規模なデータセットからの学習では、エラーの大きさはデータサンプル数の制限を受ける。例えば、データサンプルが100個しかなかったら、200混合の混合正規分布なんかを使ったらどう考えても過学習するだろう。真の分布とは違ったとしても、オーバーフィットしないようなシンプルな分布で近似せざるを得ない。
 大規模なデータセットからの学習では、データサンプル数の制限を受ける可能性は少ないが、代わりに計算時間の制限を受ける。"On-line Learning for Very Large Datasets" (L.Bottou and Y. L. Cun, Applied Stochastic Models in Business and Industry, 2005) では、大規模データからの学習においては、できるだけたくさんのデータサンプルを使うアルゴリズムを用いる事が良い、と結論している。多くのオンラインアルゴリズムはバッチアルゴリズムと比べて収束速度が遅いがそれは致命的な問題ではなく、シンプルなオンラインアルゴリズムの方が複雑なバッチアルゴリズムと比べて学習に使えるデータサンプル数が多く、良い性能を示す可能性がある。(とまでは書いていないが、「バッチアルゴリズムの複雑さは、シンプルなオンラインアルゴリズムの方が学習に使えるデータサンプル数が多い事を示唆する」とは書いてある。)
 要するに、大規模なデータセットからの学習では、これまでよく考慮されていたエラーの他に、現実的な時間で求める事ができるパラメータと最適なパラメータの間のエラーを考える必要があり、単純にSVMのような複雑なバッチアルゴリズム(まぁ、SVMカーネル使わない限りではどんどんとシンプルになってきてますが…)を使うことが最適な結果を生み出すとは限らない、という話である、と思う。
 また、後半では、Gradient Descent, Second Order Gradient Descent, Stochastic Gradient Descent, Second Order Stochastic Gradient Descentの凸最適化問題に対する計算量の解析を行っているが、この論文の主眼は、最適化エラーというものは大規模データセットからの学習では無視できないよ、というところだと感じた。
 これまでこういう理論的な解析の論文を読むのをサボってきたツケが回ってきていて、正直良く分かっていないのだが、エラーが発生する理由にはデータセットに含まれるノイズなんかもあり得ると思うのだが、そういうのはどこに分類されるんだろう? ここら辺は、もう少しちゃんと基礎を勉強しないとダメだな。
 さて、こんな理論的な論文を読んでいたのには訳があって、"Large Scale Learning to Rank" (D. Sculley, NIPS 2009?)を読んでいたらこちらの論文が参照されていてしかも重要そうだったから、という理由で読んだのだが、興味深い論文だった。読んでよかったと思う。来年は、こういう理論的な論文の方ももうちょっと読んでいきたい。"Large Scale Learning to Rank" については、また来年1月中には紹介しようと思っている。
 これで2009年の更新は終了です。前のエントリでよいお年をと書いてしまったのはちょっと早かったが、皆様、どうぞよいお年をお迎えください。