人工知能基本問題研究会(SIG-FPAI)での岡野原さんの発表のときに取ったメモ

hillbig.cocolog-nifty.com

ということで僕が取ったメモも出してみようと思う。内容としては大体3つで

  • オンライン学習
  • L1正則化
  • 索引を用いた効率化, 全ての部分文字列を利用した文書分類

という感じだったんだけど、最後の索引の付近はid:syou6162の勉強不足によりよく分からなかった。が、最初の二つはなんとか付いていけたので、出してみます。主に自分用のメモですが。

オンライン学習

自然言語処理のデータは3つの特徴がある。

  • 高次元
  • 冗長

で、あとはデータがばかでかいので、いわゆるバッチ処理だとメモリに乗り切らなかったりとかということがある。それでオンライン学習というのが今よく使われているようだ。オンライン学習の方法には下のような方法がある。簡単なものから難しいものへ。

  • perceptron
    • 自然言語処理と相性がよい
    • 色んなもののベースになる
    • 線形分離できるときには有限回で収束することが保証されている
  • averaged perceptron
    • 普通のperceptronだとデータの順番とかで影響を受けてしまうので、それを避けるために重みをならしてやるということをする
  • structured perceptron
    • 構造学習(木とか複雑なデータ構造のものも)
    • これもパーセプトロンでできる
  • passive aggressive algorithm
    • 結構重要らしい
    • 解析的な解が閉じた形で書ける!!というのが大きい
    • 確信度というものを導入
      • 確信度が低い場合、正解の時でも更新する
  • confidence weighted learning
    • 性能がかなりよい
    • 確信度を導入
    • 解析的な解が閉じた形で書ける!!
  • 確率的勾配降下法
    • 勾配ベクトルを一部のデータの勾配で近似
      • とメモに書いてあるがなんか意味が分からないw
      • 全部だとメモリに乗らねーよってことだったっけかなあ
    • w:=w-tv
      • ステップ幅tはだんだんと小さくなる
    • 収束は非常に早い
    • パラメータの選択とかも完全に自動化が可能!!

オンライン学習の特徴は、実装するコストが少なくて済むということもある。共役勾配法をバッチ処理とかでまともに書こうとすると500行くらいかかるが、オンライン学習だと10行くらい。Codingにかかるコストが小さくて済むというのはすごくうれしいですよね。特に最適化のような複雑な計算のやつだと。

L1正則化

機械学習とかだとパラメータの数が数億とかになる場合がある*1ということで、少ないパラメータでどうにかしたいという要望がある。使えるリソースが限られているような組み込み系だとかだと特にそうらしい(デジカメの顔認識の話がされていたと思う)。機械学習だと過学習を避けるために、目的関数に正規化項を付けたりするんだけど、その正規化項にL1正規化というものを使うと多くの重みが0になるという特徴があり、そういうわけで多くのパラメータを保持しておかなくてもよい、という利点があるとのことだった。

  • 多くのパラメータが0になるということで学習の結果が分かりやすい
  • 計算が早い
  • メモリが少なくてよい

などのメリットを持つ。L1正則化というのは絶対値の和のこと。なお、L2正則化だとほとんどの重みが0になる、ということはない。で、それはRepresentation Theoremというもので示されているとのことだった。L2正則化だとx^2のような感じで、微分すると直線の形になるわけだけど、0周辺では値が0に近くなるため、パラメータが0に収束しないでどっかで均衡みたいな形になり、止まる。しかし、L1正則化だと微分すると0付近でも一定の値となり、パラメータは(どっかで止まらないで)0に収束していく、という説明がされていた。

L1の意味付けとして、ベイズの事前分布とかMap推定の話が出ていた。この辺は確かPRMLの3章付近にあったので確認しようと思う。

L1は上に書いたようなメリットがあったんだけど、じゃあL2にはどんなメリットが?ということになるんだけど、ちょっとでも性能が欲しいという場合にはL2のほうがよいというのが表で示されていた。L2の実装は簡単で、Averaged perceptoronが、という話が出ていたけど詳細はメモしきれていない。

L1では絶対値という微分不可能なものが入ってくるんだけど、そうすると微分可能性を仮定しているような最適化法が使えなくて苦しい(そういう意味ではL2は凸関数の和で凸関数となり、最適化しやすいということがあるのかな)。どうにかならないのかな?ということでFOLOS(ふぉろす)という方法が紹介されていた。最適化理論は基礎っぽいところしか触ってないのでこの辺は初めて聞く感じだった。FOLOSは目的関数が微分可能なものと微分不可能なものの和になっているようなものに対する最適化法の一つらしく、2つのステップからなる。最初に微分可能な項を最適化、次に微分不可能な項のほうを最適化、ということをやるらしい。「これで本当にいいところに行くんかいな?」という疑問が湧くが行くのが示されているらしい。この方法のうれしいところは2つめのステップのところで解が閉じた形で得られることが多いということだった。キーワードは「L1は引く、L2は割る」。FOLOSは微分不可能なものを正則化項に持ってきてもできるよ、ということで複雑な正則化項、例えばL1とL2の和とかも考えることができるようになるということだった。質疑で、「複雑な正規化項を考えるというのは、直感的にどういう風に考えればいいですか」みたいな質問をさせてもらったんだけど、例えばL1とL2の和の場合だとL1のほとんどのパラメータを0にする、という効果とL2のちょっとでも性能を上げるというもののバランスを保てるということがメリットじゃないかということだったと思う。ただ、理論的なところでは弱くなるのかなあという感じだったかな。

*1:統計のほうにいた人なのでびびる