読者です 読者をやめる 読者になる 読者になる

論文:Beating the World’s Best at Super Smash Bros. Melee with Deep Reinforcement Learning

モデルフリー系の深層強化学習の手法を用いてスマブラDXのゲームAIを作ったという論文が出ていたので読んだ。以下はそのメモ。

概要

論文URL : https://arxiv.org/abs/1702.06230
著者のグループは github でコードを公開しており、そのデモ動画が twitch や youtube に上がっている。
www.youtube.com
上の動画はその一例。明記されていないが、動きからして 2P のキャプテン・ファルコンが強化学習 AI で、1P が人間だと思われる。スマブラの素人が見てもあまりピンと来ないのだが、人間側は世界ランキングでトップ50相当のプレイヤー(二人いて、途中で交代している)らしい。

reddithacker news でも活発に議論されている模様。

内容

環境の定義について

  • Atari のゲーム環境などとは異なり、画像ではなくエミュレーターのメモリから必要な情報を取り出してそれを観測情報としている。具体的にはプレイヤーの位置、速度、行動状態などがあると記されている。観測の次元がどれくらいなのかは自分が見た限りでは明記されていないように見えるが、多くとも数十次元程度といったところだろうか。
  • ゲーム自体は60フレームで動いているが、行動は2フレームおきに行うようにしている。スキップしたフレームでは何も行わないと記されている(が、これだと左右移動とかが不自然になるので正確には直前の行動を繰り返しているのでは?)
  • ゲームキューブのコントローラーには2つのアナログスティックと幾つかのボタンが有り、複雑な入力を入れることが可能である。が、簡略化のために、アナログスティックの操作は9個に限定し、ボタンは5つのうち高々1つしか選べないようにしている。これにより、9*(5+1)=54個の離散の行動値から1つを選ぶように設定している。
  • 報酬関数の設計は、相手を倒す/相手に倒されるでそれぞれ+1/-1が得られる設定にしている。が、これだけだと報酬を得るまでが遠すぎるので、相手に与えた/相手から与えられたダメージも報酬に加えている。

手法

  • ニューラルネットを用いたQ学習(DQN)と方策勾配法(Advantage Actor-Critic)を試した。
  • Atari ではゲーム環境を実時間の数百倍でエミュレートできるが、スマブラDXではせいぜい1~2倍の速度でしかエミュレートできず、そこがボトルネックになってしまう。これを解決するために、複数個(50個とかのオーダー)のエミュレーターを並列で走らせた。計算資源はどこかから調達した。
  • ハイパーパラメータは色々チューニングした。ε(行動をランダムに選ぶ確率?)は0.02、割引率は0.99くらい、割引報酬の和は10ステップまで取る。
  • Q関数やactor,criticのニューラルネットアーキテクチャには隠れ層2、チャンネル数128の全結合のものを用いた。詳しく調べていないが、層を増やしたりしても結果は良くはならなかったと記されている。
  • 活性化関数として、leaky relu のソフト版のようなものを使ったと記されている : $f(x) = \log(\exp(0.01x) + \exp(x))$ …が、一体なぜ?
  • 学習率は手で調整して 1e-4 にした。
    • この後で、TRPO でステップ幅を決める手法も紹介されているが、実験どの部分で使ったのかよく分からない。

実験1 : 普通に対戦

  • エージェントをそれぞれスマブラDXに標準搭載されているAIと対戦させた。
  • ステージは「戦場」、プレイキャラは両方ともキャプテン・ファルコン (↑の動画の通り)
  • DQN も Actor-Critic も20時間くらい経てば相手を上回る性能になった。DQNの方が収束が速い。
  • 報酬関数の値を見ると DQN と Actor-Critic で大差はなかったが、学習した方策に大きな違いが見られた。DQN は相手(標準AI)に対してハメ技のような手を探して相手を自滅に追い込むのに対し、Actor-Critic では人間と似た戦略に落ち着いた。
  • 学習アルゴリズムのベースラインとして、OpenAI が提供している A3C のアルゴリズムを試してみたが、うまくいかなかったと記されている。

実験2 : 自己対戦

  • それなりに強いエージェントが出来たことなので、AlphaGo のときと同じ要領で自己対戦のアプローチを試した。
  • 最初は弱い人間プレイヤーにも負けるエージェントだったが、1週間自己対戦を行うと中級プレイヤー(著者)も勝てないほどになった。
  • その後さらに1週間自己対戦を行った後、スマブラDXのトッププレイヤー達と対戦を行わせたところ、エージェントの方が倒した回数を上回る結果となった。(詳細は論文のテーブル1)
  • しかし、エージェントは謎のハメ技を使うと倒せてしまうことも判明した。具体的には、ステージの端で座ったままで居るとエージェントは変な挙動をして、自滅してしまうこともあるらしい。学習中にハメ技を仕掛けてくるような対戦相手が居ないことが原因だろうとしている。

実験3 : 複数キャラ

  • キャプテン・ファルコンしか使えないのは不満なので、他のキャラクターでも学習を試みた。具体的には Sheik, Marth, Fox, Falco, Peach, Falcon が挙がっている。
    • 投擲技を行うキャラ(フォックスとか)が居る気がするのだがいいのだろうか…
  • …学習した結果、どれくらい強くなかったのか書かれていない。
  • 環境が多様になったおかげか、奇妙な挙動をしたりハメ技で死んだりすることは無くなったと書かれている。
  • あるキャラクターのエージェントを学習する時に、初期値として他のキャラクターで学習したパラメータを持ってきて学習すると、学習時間が短くて済んだと記されている。

議論

  • Q学習は固定された環境ではうまくいったものの、自己対戦のような環境が変遷していく場合にはうまくいかなかった。policy iteration に加えて環境の変化に追随するのが難しいのではないかと筆者らは予想している。
  • 探索と活用について:Actor-Critic ではエントロピー項の係数で探索量を調整しているが、スマブラDXでは多くのフレームではどう動こうが重要ではない場面が多く、そういったときにエントロピーが高くなり、行動が不安定になりがちになるのでなんとかする方法が欲しい。
    • どうでもいい場面ならどう動こうが別に良いのでは? と思ったのだけど違うのだろうか
  • 人間には反射速度に200ms程度の限界があるのに、このエージェントは2フレーム(33ms)で反射していて、人間との対戦ではフェアではないのではないか、という批判がある。これに対して、行動を即時に行うのではなく、一定フレームだけ遅れて行うようにして学習させたところ、6フレーム遅延させたあたりから一気に性能が悪化していったと記されている。遅延そのものだけでなく、報酬の遅れなどが原因なのかもしれないが、定かではない。

感想

  • 手法面での真新しさは特に無いものの、モデルフリー系の強化学習手法を実際の難しいタスクに適応しようとしたケーススタディとして面白い。細かいチューニングとかの話も結構参考になる(かも)。
  • Q学習系と方策勾配系の手法で振る舞い方に差が出るという話は聞いたことがなかったので面白いと思った。普通の論文では報酬の合計値でしか性能を見ないので、こういった違いにはなかなか気付けない気がする。ただ、この話がどこまで一般的なものなのかはよく分からない。
  • 良い強化学習エージェントを作り上げるには、試行錯誤も学習も含めやはり相当な計算資源と時間が必要なのだと感じた。
  • そもそも海外で未だにスマブラDXが人気ということを知らなかった。
  • 論文のタイトルはやや誇張気味で、まだやることは色々残っている。

読書メモ:Drones: The Facts, Fun & Dangers of Drone Technology

最近のドローン事情について知りたくなったのでいろいろ調べていたらこれを見つけたのでとりあえず読んだ.
www.amazon.co.jp

概要

昨今はドローン市場が盛り上がっているが,どのような分野でドローンが活用されているのか,または活用されると期待されているかについて書かれている.分量は43ページとかなり少ない.値段も320円とお手頃で評価もそこそこよい.英語読むのが速い人なら速攻で読み終えられるのではなかろうか.
分量が少ないだけあってあまり細部については書かれていない印象がある.例えば Amazon Prime Air のようなドローンを使った配達業なんかは注目度が高い気がするのだが,自分の画面だと2ページくらいしか書かれてなくて短い.(法規制のこともあってあまりおもしろい話が無いせいもあるのかもしれないが.)

部の構成については以下のようになっている.

  • Introduction
    • ドローンの歴史について.戦争の最中に開発され,今でも主に軍事用途で使われていることが説明されている.
  • Chapter 1
    • ドローンの種類について.空中に浮遊するヘリコプタータイプ(ロータリー)のものと,RQ-11 Raven のような固定翼のものがある.ロータリーは移動を精密にできるが,電気をよく消費するし移動速度が低い.固定翼のものは省電力で移動速度が大きいが,飛行機と同じように移動するため離着陸に滑走路が必要になる.
  • Chapter 2
    • ドローンの市場規模について.大体軍事用途である(c.f., Drones Report Market Forecast - Business Insider)が,今後は商用利用・個人利用も増えていくだろうとの見通しを立てている.ドローンメーカーは垂直統合と技術ライセンスが主な戦略になっていく.商用利用では農業が80%を占めるようになるだろうと予想している.
  • Chapter 3
    • ドローンは軍事だけでなく,警察でも使われる.
  • Chapter 4--10 : いろんな軍事以外の応用について書かれている.
    • いろいろな応用があるが,以下の3つのどれかに分類できるような気がした.
      • ドローンにカメラなどのセンサーを積んで,人間では辿りつけないか,あるいは従来のヘリコプターのような機体で移動するには高コストだった場所から広範囲に地上の情報を集める.例えば,災害地の監視,上空地図の作成,農地の監視など.農業用途のドローンの需要が大きいのは,現状は多くを人手でやっている農地の監視作業をドローンで肩代わりできるようになるのが大きいのと,今後も世界人口の増加で農業自体の需要が大きいため.
      • ドローンに何かものを積んで,ものの移動手段とする.農地での農薬散布,商品の配送など.法規制が厳しいため,配送は現状ではすごい田舎など人がいない場所に限られる.そういえば,商品の配送でドローンを最初に使おうとしたのは Amazon Prime Air なのかとおもいきや実はオーストラリアの Flirtey というベンチャー企業だったらしい.
      • カメラを載せてかっこいい映像を作る.報道用の映像撮影,不動産の物件のかっこいいPV作成(建物を上空からいい感じに映したらそれで興味を惹かせることができる,らしい… ほんまか)など.
  • Chapter 11
    • ドローンがテロに使われちゃったら嫌だから法規制はやっぱり慎重にしないといけないという話.短い.

感想

ドローンが期待されている使われ方についての記述は自分みたいな素人でも分かりやすかった.反面,ドローン市場の全体像については具体的な数字が少なくていまいちつかみにくいような気がする.今後も状況はガンガン変わっていくので油断ならない.

ニューラルネットのメモリ消費を小さくする類の手法

ちょっと前に論文読んだので備忘録としてメモしておく.

前置き

  • 本格的なニューラルネットはパラメータ数が多いのでモデルサイズが大きくなってしまうことが多い
  • このようなモデルでも普通のマシンで動かす場合には(GPUのメモリを使い切らない限り)問題にならないことも多いが,モバイル端末などメモリ容量が制限されたハードウェア上で動かしたい場合には問題になる.
  • これをなんとかする論文をいくつか読んだ.

Deep Learning with Limited Numerical Precision (ICML2015)

  • 普通はNNのパラメータは32bit浮動小数点数で保持されているが,小数の精度を落とす(たとえば16bitとか8bitとかにする)ことでメモリ消費を単純に1/2とか1/4にできる.
  • 16ビット幅の固定小数を使ってNNを学習のフェーズから行う.
  • 小数を丸めるときに,単に一番近い値に丸めるのではなく,切り上げか切り下げかをその値によって確率的に選ぶと良い感じになる,と主張している.
    • 更新のときに小さい値が何度も足されるふうになる時に,一番近い値に丸めるのだと全く更新されないけど,確率的にやるとたまにちゃんと更新されて良い感じになるというイメージ.
    • この丸め方の違いで学習性能が大きく変わることが実験結果から示されている.
  • 後半に,それ用のハードウェアをFPGAで構成する話も載っている(未読)
  • 感想
    • 確率的に丸めることでまともになるというのは結構妥当な感じがするしNN以外の手法でも使えそうな気がする.ある良い感じの条件下(たとえば目的関数が凸とか)だったら高確率で高精度小数で計算した時から結果がずれないみたいなことは言えても不思議じゃない気もする.ちゃんと考えたわけじゃないので雑な意見だけど….
    • 小さいモデルでしか実験してないけど最近の10層以上のネットワークでも同じような結果は得られるか気になった.
    • しかしメモリが制限された環境で学習したい状況というのがどんな状況なのかあまりイメージが沸かなかった.学習自体は富豪環境でやってテストだけ貧民環境でやりたいことのほうが多いんではないか.
      • GPUのメモリに入りきらないくらいでかいモデルを訓練したい時には良いのかもしれない?

Fixed Point Quantization of Deep Convolutional Networks (ICLR2015 under review)

  • レビュー中だけど引用されていたので読んだ.
  • これも,精度を落とした固定小数点数でNNを学習のフェーズから行う.
  • この論文では,NN全体で同じビット幅の固定小数を使うのではなく,レイヤーによって幅を変えるともっと消費メモリを抑えられるということを主張している.
  • 適切なビット幅を求めるために,SQNR(signal-to-quantization-noise ratio)という量を考える.
    • SQNR については知らなかったが,量子化した際に元の値からの誤差がどれくらい大きくなるかの期待値(の対数)を表す(という理解でいいんかな…)
    • 量子化幅を求めるには,量子化したい値がある分布に従っていると仮定して,SQNRが最小になるような幅を求めることにする.
    • 分布が正規分布だとどれくらいにすればいいかというのが大体知られている.実際のCNNに渡される入力を見ると,おおむねどのレイヤーの重みの分布もactivation valueも正規分布っぽいかんじになっていると分かるので,そう仮定する.
    • CNNでのSQNR(の逆数)は各層でのSQNR(の逆数)の和になる.これを最小化しようとすると閉じた式が得られる.
  • 提案手法によると,入力に近い層ほど高い精度の小数を使うべきで,出力に近い層ほど精度を落としても良いということになるらしい
  • Fine-tuning は重要
    • CIFAR10のCNNを使った手法のベースラインの精度は7%程度だが,実験を見るとFine-tuningすると全層4ビットでも1~2%程度悪くなるだけで済むらしい.Fine-tuningしないとひどくなる.
    • …と書かれているのだけど細部があんまり書かれていないような.普通に勾配法実行するのだとして丸め方はどうするのかとか.
  • 感想
    • 単にモデルの容量削減という目的で性能だけ見るとそんなに良くなってないけど,
    • 下のレイヤーのほうが上のレイヤーより小数精度が高くないといけないというのは,特徴量の最低限必要な量子化粒度がレイヤーによって違うということを示唆していて面白いかもしれない.

Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding(ICLR2015 under review)

  • これもレビュー中だけど紹介されたので読んだ
  • 小数の精度を落とす以外にも色々工夫して最近のモデルを50倍くらい圧縮する.工夫としては3つくらいある.
    • その1.値が小さい重みを0につぶして,畳込みの重み行列を疎行列として扱う.(図2)
      • これだけでもだいぶ効き目がある.(10倍くらい圧縮される)
      • ただ,閾値をいくらにするかはどこにも書いてなくて謎だけど適当でいいのか…
    • その2.非零の重みを量子化して何種類かにして,重みをHashedNetsみたいに共有させる.そこからさらに再学習も行う.
      • HashedNetsはハッシュによって重みを共有する要素を決めていたが,この手法は学習済みのモデルからどの要素を共有させるかを重みのクラスタリングによって決めている.
    • その3.重みの分布と,疎行列で表す際のlocation indexの分布は偏っているのでハフマン符号化して表すとよりメモリ消費を抑えられる.
  • 感想
    • オーソドックスな圧縮手法を一通り使ったら良くなったという話っぽい.
    • 実験を大きいモデルでちゃんとやってて性能もかなり出てるので実用的そう.

2014年度振り返り

働き始めて1年位経ったっぽいので去年度の振り返りでもします.

仕事

PFIに入社していたのですが入社して半年くらいで PFN (Preferred Networks) という新たに立ち上げた関連会社に移籍しました.環境自体はそこまで大きく変わってません.
仕事で表に出せる情報が現状は少ないです.そのうち何か表に出せる成果になるとよいのですが.

ニューラルネットでなんかうまくいくことがわかっているけどちゃんとした理由はよく分かってないようなテクが世の中には結構色々あるのですが,なぜうまくいくのか理解する助けになりそうなことに最近は興味があります.本当は理論的な結果を言えれば美しくて一番良いのですが,この分野はいかんせん理論的な解析が何十年も前から大して進んでいなくてあんまり期待が持てないので,当面は実験して色々分析するのが手っ取り早いし,ついでに変なお絵かきみたいなこともできるので楽しいんじゃないかと思っています.あるいはうまくいくと思われているテクを撃墜するとかも.

大学の頃やっていた研究分野と今仕事でやっている分野は結構違うところが多く,学び直すことも多かったですが最近段々ノリが分かってきたという気がしないでもないです.

学会

修士にやってた頃の研究のおかげで3回国際学会(SIGMOD,KDD,ICALP)に行くことができました.SIGMOD,KDDはアカデミックのみならず企業からの関心が非常に高く,参加者数もとても多く賑わっていました.一方でICALPの参加者は大体アカデミックのいかにも理論っぽい人たちの集まりで,落ち着いた雰囲気を感じました.理論のコミュニティと応用のコミュニティの空気の違いを見れたのは大きかったのかなぁと思います.
あとネガティブなネタではありますが,SIGMOD 併設のデータベース系理論会議 PODS のどんよりとした雰囲気のビジネスミーティングは,理論出身の自分にとってはとても悲しいものに見えました.
また論文書いてどっかいって発表とかできると面白いですが,なんか良いネタを探さないと….

弐寺DP

京都にいる頃は弐寺の置いてあるゲーセンにはほとんど行かなかったのですが,東京に来てから比較的職場の近くにゲーセンがあるのでたまに行っています.12.3にイージーランプが付きました.十段の達成率も75%までいきました.調子が良いのでこれは年内皆伝ペースか? と思ってましたが最近になって段々自信がなくなってきました.とりあえず12.3を大体埋めないといけないけど先が長い.

競プロ

もうすっかり選手ではなく運営をする立場になりました.競プロは良いコミュニティが形成されていると思うのでそれが長く続くことを願っています.そういう点では最近の topcoder の運営には不満な点がかなり多く,改善されることを期待しています.
なんかせっかくなので巷ではあんまり無さそうなタイプのコンテストを開けると面白そうだと前から薄々思っているのですがそれはできたとしても結構先になるのだろうなぁ.

旅行

色々なところに行きました.今年も色々なところに行きたいです.

語学

英語が宇宙一できないので iKnow やってるんですが全然リスニング力が向上しなくて辛いです.

情報オリンピック春合宿で講義しました

1週間前の出来事ですが「機械学習とその理論」というタイトルで講義しました.大体 PAC 学習の話してます.スライドを公開しているので以下にそのリンクを載せます.

今回の講義では,才能がありそうな若い人らを前にどんなことを話せばいいか,テーマ選びに少し悩みました.色々考えた所「プログラミングコンテストの界隈ではあんまり触れられないけどコンピュータサイエンスの研究や実際の応用で重要なことっていっぱいあるしそういうのを伝えるのが大事なのかなぁ」と思い,その中の1つである機械学習のことについて話すことにしました.
機械学習を語るには色んな切り口があると思うのですが,情報オリンピックに参加しているような人ならきっと理論っぽい話が好きなんじゃないかなぁと思い,基本的な理論のモデルである「PAC学習」について話しました.機械学習というと大体統計的な観点から入門することが多いのですが,それだと少し数学の道具の準備とかが大変そうだったため今回は敢えて全く話してません.まぁ本当は準備してる時間がなかったからなんですが. アルゴリズムの話も全くしてないのですが本当はパーセプトロンくらいは話したかったような気がしないでもないです.
ちなみにこの講義はこの合宿のメインイベントではないので,あんまり堅いことばっかりしゃべると聞いてて面白くないだろうなぁと思ったためスライド構成は割とエンターテインメントに走っています.

…どうでもいいんですがマイクロソフトのパワーポイントがクリップアートの提供を終了したせいで画像探しに苦労しました.いちいち自分でライセンス確認しないといけないとか勘弁して欲しい.

ラグランジュ関数の背後にある理論 (Boyd本5章概要)

ラグランジュ関数は以下のような形をした制約付き最適化問題を解くために導入される有名な手法です.

  • $\min_{x \in D} f_0(x),$
  • $\mbox{subject to}$
    • $f_i(x) \le 0$ $(i=1,2,...,m)$
    • $h_i(x) = 0$ $(i=1,2,...,p)$
  • ここで,$D \subseteq \mathbb{R}^n$ は目的関数の定義域で, $f_0,f_1,\cdots,f_m, h_1, \cdots, h_p: D \rightarrow \mathbb{R}$ は任意の関数.

この記事では "Convex Optimization" (by Boyd and Vandenberghe) の5章 "Duality" の項を元に,ラグランジュ関数とその背後にある理論について記します.主に記したことは以下のとおりです.

  • ラグランジュ関数の定義とその解釈の仕方について
  • 強双対性が成り立つ関数のクラスについて
  • その正当性の証明

キーワード:ラグランジュ関数,ラグランジュの未定乗数法,双対関数,KKT条件

この記事を書こうと思った理由

ラグランジュ関数は計算機科学の応用分野で重要になる手法であり,世の中には数多くのラグランジュ関数に関する説明があります.しかし,僕が目にした多くの説明は,直感的な説明に留めているものや,目的関数や制約関数について暗黙的に何らかの制約があるもの(例えばパラメータ表示可能である,といったような)についてのみ書かれている(それも恐らく厳密ではない)に過ぎないなど,不満に思っていた点がありました.このようにちゃんとした証明が添えられていない理由は詳細に立ち入ると難解になってしまうからでしょう.基礎分野ならともかく応用分野では飽くまでブラックボックスとして使えればよくて詳細に立ち入るのにあまり時間を割くのは本質ではないので,そうなってしまうのはしょうがないという面があるのだと思います.

しかし,ちゃんとした理由があまりわからないまま使うというのは怖いものです.実際には適応できないできない関数について手法を使ってしまって,とんでもない結果を導出してしまったりしうるからです.で,何か良い資料はないものかと先日会社の人に聞いたところ,上記の本 (Boyd本) に詳しく書かれていると教えてもらったので,それについて自分なりのまとめを記したいと思います.

Boyd本は pdf が無料で公開されているので誰でも読めますのでこの記事でよくわからなかったり詳しく知りたくなった方はBoyd本を見て下さい.ラグランジュ関数について書かれているのは5章からですが,大学1~2年生相当の数学の素養があれば途中からでも十分読めると思います.たまに前の章を少し読み返す必要があるかもしれませんが.

ラグランジュ関数

冒頭でも挙げましたが,以降では以下の最小化問題について考えていくことにします.特に明記しない限り,定義域,目的関数,各制約関数には制限を設けないことにします.この問題のことを主問題と呼ぶことにします.

  • (再掲) $\min_{x \in D} f_0(x),$
  • $\mbox{subject to}$
    • $f_i(x) \le 0$ $(i=1,2,...,m)$
    • $h_i(x) = 0$ $(i=1,2,...,p)$

主問題に対してラグランジュ関数 $L:\mathbb{R}^n \times \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$ は以下で定義されます.

\[
L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)
\]

$\lambda, \nu$ はそれぞれ $m $,$p$ 次元のベクトルです.$\lambda$ はラグランジュ乗数,また $(\lambda$,$\nu$) は双対変数と呼ばれます.

…で,突然なんなんだこの関数は,と思う人が多いんじゃないかと思うのですが,Boyd本ではこれについて良さそうな解釈が乗っていたのでそれについて記します.

"線形関数による置き換え" という見方

主問題は制約付き問題でしたが,以下のように書けば制約無しの問題に(強引に)書き換えることが出来ます.
\[
\min_{x \in D} f_0(x) + \sum_{i=1}^m I_{-}(f_i(x)) + \sum_{i=1}^p I_{0}(h_i(x))
\]
ここで,

  • $I_{-} : \mathbb{R} \rightarrow \mathbb{R}$ は正のとき $\infty$,$0$ 以下のとき $0$ となる関数
  • $I_{0} : \mathbb{R} \rightarrow \mathbb{R}$ は非0のとき $\infty$,$0$ のとき $0$ となる関数

です.要するに制約を満たさない場合に目的関数の値が $\infty$ になるように調整しているというだけです.
$I_{-}$,$I_{0}$ は $0$ 近傍でとても急激な変化をする関数です.ここで,新たにパラメータ $\lambda$,$\nu$ を導入し,急激に変化する関数 $I_{-}$,$I_{0}$ を線形関数で置き換えたものがラグランジュ関数という風に見なせます.(i.e., $I_{-}(f_i(x))$ → $\lambda_i f_i(x)$, $I_{0}(h_i(x))$ → $\nu_i h_i(x)$.)
f:id:ir5:20141214022940p:plain
もちろんこの置換えはかなりいい加減で問題自体も大きく変わってしまっているのですが,適切なパラメータを選べばこの雑な置き換えでも主問題と同じような最適値を達成できるというのが後で述べるラグランジュ関数を考える利点です.

ラグランジュ双対関数

ラグランジュ双対関数 $g : \mathbb{R}^m \times \mathbb{R}^p \rightarrow \mathbb{R}$ は以下で定義されます.

 g(\lambda, \nu) = \inf_{x \in D} L(x, \lambda, \nu)
先ほどの見方を踏まえているとこれは理解がしやすいです.パラメータ(というか双対変数) $\lambda$,$\nu$ で目的関数を"置き換え"た場合の問題の最適値です.

ラグランジュ双対関数は,(主問題の目的関数と制約関数がなんであれ)上に凸な関数になっています.これは, \inf_{z} (a_z + b_z) \le \inf_z a_z + \inf_z b_z 型の不等式をラグランジュ関数に適応するとわかります:$\alpha \in [0,1]$ に対し,
 \alpha g(\lambda, \nu) + (1-\alpha) g(\lambda', \nu')
 =   \inf_x \alpha L(x, \lambda, \nu) +  \inf_x (1 - \alpha) L(x, \lambda', \nu')

 \le \inf_x \left( \alpha L(x, \lambda, \nu) + (1 - \alpha) L(x, \lambda', \nu') \right)
 =   g(\alpha \lambda + (1 - \alpha) \lambda',
       \alpha \nu + (1 - \alpha) \nu').
ここで最後の式変形はラグランジュ関数が $\lambda$,$\mu$ について線形な関数であることを用いました.

弱双対性

ここで,$\lambda \ge 0$ だとする*1と,先ほどの図のように,$I_{-}(f_i(x)) \ge \lambda_i f_i(x)$, $I_{0}(h_i(x)) \ge \nu_i h_i(x)$ なので,任意の $x \in D$,$\lambda \ge 0$,$\nu \in \mathbb{R}^p$ に対して $g(\lambda, \nu) \le f_0(x)$ が成り立ちます.これを弱双対性と呼びます.

双対問題

$g(\lambda, \nu)$ は主問題の解の値を下からバウンドできます.ここで,このバウンドがどこまで成り立つのか,つまり $g(\lambda, \nu)$ はどこまで大きく出来るのかというのを考えるのは自然なことです.以下の問題を(主問題に対する)双対問題と呼びます.

  • $\max_{(\lambda,\nu) \in \mathbb{R}^m \times \mathbb{R}^p} g(\lambda, \nu)$
  • $\mbox{subject to}$ $\lambda \ge 0$

先ほど述べたように $g$ は上に凸であり,$\lambda$ の取りうる範囲も凸なので,双対問題は主問題に関係なく凸最適化問題になります.
$p^\star$ を主問題の最適解,$d^\star$ を双対問題の最適解とすると,弱双対性は $d^\star \le p^\star$ と表せます.

具体例

ここで1つ簡単な具体例を挙げます.最適化問題として以下の1変数の問題を考えましょう.

  • $\min_{x_1 \in \mathbb{R}} (x_1-3)^2$
  • $\mbox{subject to}$ $x_1^2 \le 1$

まぁこの程度の問題ならラグランジュ関数とか考える必要全く無いのですが細かいことは置いておきましょう.
この主問題に対するラグランジュ関数は $L(x_1, \lambda_1) = (x_1-3)^2 + \lambda_1 (x_1^2 - 1)$ です.また,ラグランジュ双対関数は  g(\lambda_1) = \inf_{x_1 \in \mathbb{R}} L(x_1, \lambda_1) = 9-\lambda_1-9/(1+\lambda_1) となります.
主問題の最適解は $x_1=1$ のときに $p^\star=4$,双対問題の最適解は $\lambda_1=2$ のときに $d^\star=4$ となります*2

ラグランジュ関数は図示すると以下のようになります.(主問題,双対問題のそれぞれで最適解を取る点 $(x_1, \lambda_1)=(1,2)$ がなんとなく鞍点になってそうな雰囲気がします.)
f:id:ir5:20141214044146p:plain

強双対性

先ほどの具体例のように $d^\star=p^\star$ が成り立つとき,その問題について強双対性が成り立つと呼びます.強双対性が成り立てば,主問題の代わりに双対問題を考えれば良いことになり,双対問題の方が考えやすい場合には役立ちます.たとえば主問題では変数の個数は多いけど制約の個数が少ない場合,双対問題では変数の個数が少なくなるため,双対問題の方が考えやすいことが多いようです.
残念ながら強双対性は一般には成り立ちませんが,限られた条件下では成り立ちます.それを以下に記します.

凸な場合

以降は主問題が凸である場合を考えます.つまり,$f_0, f_1, \cdots, f_m $ が下に凸,定義域 $D$ が凸で,主問題が以下のような形式になっている場合です.

  • $\min_{x \in D} f_0(x)$
  • $\mbox{subject to}$
    • $f_i(x) \le 0$
    • $Ax=b$ ($A$ は $p \times n$ の行列)

以下では簡単のため等号制約の行列 $A$ は行フルランク($\mathbf{rank} A = p$) とします.

Slaterの条件 (凸な場合)

強双対性が成り立つための条件の1つとして,次のものをSlaterの条件と呼びます:ある $x \in \mathbf{int} D$ *3 があって,以下を満たす.
\[
f_i(x) < 0 (i=1,\cdots,m), Ax=b.
\]
つまりSlaterの条件とは,狭義に実行可能な点があるということです.

次の節では以下のことを示します.

補題主問題が凸であり,Slaterの条件が成り立つとき,ラグランジュ関数について強双対性が成り立つ.

補題の証明

$\mathcal{G}$ を,$x$ を動かしたときに目的関数と制約関数が取りうる範囲とします:
\[
\mathcal{G} = \{f_1(x), \cdots, f_m(x), h_1(x), \cdots, h_p(x), f_0(x) \mid x \in D\}.
\]
このとき,ラグランジュ双対関数は
 g(\lambda, \nu) = \inf_{x \in D} L(x,\lambda,\nu) = \inf\{ (\lambda,\nu,1)^\top (u,v,t) \mid (u,v,t) \in \mathcal{G} \}
です.また,主問題の最適解は  p^\star = \inf\{ t \mid (u,v,t) \in \mathcal{G}, u \le 0, v = 0 \} と表せます.

また,$\mathcal{A}$ を,$\mathcal{G}$ の上側領域と右側領域とします.(エピグラフっぽいもの)
\[
\mathcal{A} = \{(u,v,t) \mid \exists x \in D, f_i(x) \le u_i, h_j(x) = v_j, f_0(x) \le t\}.
\]
$\mathcal{G}$ の定義は
\[
\mathcal{G} = \{(u,v,t) \mid \exists x \in D, f_i(x) = u_i, h_j(x) = v_j, f_0(x) = t\}.
\]
だったことを踏まえると $\mathcal{G} \subseteq \mathcal{A}$ に注意して下さい.
例えば先程の具体例の問題ですと, $\mathcal{G}$ は下図の青色曲線,$\mathcal{A}$ は赤色領域に対応します.ここで横軸が $u$,縦軸が $t$ に対応します.

f:id:ir5:20141214145228p:plain

一般に主問題が凸最適化問題なら,$\mathcal{A}$ は凸領域になることが示せます.
いま,$\mathcal{B} = \{(0,0,t) \mid t < p^\star \}$ とします(上図の緑色領域).このとき$\mathcal{A}$,$\mathcal{B}$ は共有点をもたない凸領域なので,ある超平面があってこの2つを分離することが出来ます(separating hyperplane theorem).つまり,ある $(\tilde\lambda, \tilde\nu, \mu) \not= 0$ と $\alpha$ があって,

  • $(u, v, t) \in \mathcal{A} \Rightarrow \tilde\lambda^\top u + \tilde\nu^\top v + \mu t \ge \alpha$
  • $(u, v, t) \in \mathcal{B} \Rightarrow \tilde\lambda^\top u + \tilde\nu^\top v + \mu t \le \alpha$

ここでもしある $i$ について $\tilde\lambda_i < 0$ とすると,ある $(u,v,t) \in \mathcal{A}$ をとったとき,$u_i$ の座標をどんどん大きくすると分離平面を突き抜けることになりますが $\mathcal{A}$ の定義からそのようになっていはいけない($u_i$ の座標を大きくしても $\mathcal{A}$ に属したままでないとけない)ので矛盾します.$\mu$ についても同様のことが言えます.なので $\tilde\lambda \ge 0, \mu \ge 0$ です.

また,$\mathcal{B}$ に属する $u,v$ の座標は $0$ で,$t < p^\star$ であるので,分離平面の式から $\mu p^\star \le \alpha$ です.これらを踏まえると,任意の点 $x \in D$ について,
\[
\sum_{i=1}^m \tilde\lambda_i f_i(x) + \tilde\nu^\top(Ax-b) + \mu f_0(x) \ge \alpha \le \mu p^\star
\]
です.

ここでもし $\mu > 0$ (分離平面は $t$ 軸方向に平行ではない) と仮定すると,定式を $\mu$ で割って
\[
L(x, \tilde\lambda / \mu, \tilde\nu / \mu) \ge p^\star
\]
となり,つまり $\lambda = \tilde\lambda / \mu$, $\mu = \tilde\nu / \mu$ とおけば g(\lambda, \nu) = \inf_{x \in D} L(x, \lambda, \nu) \ge p^\star となります.これはまさに強双対性を示唆するものです.

では $\mu=0$ (分離平面が $t$ 軸に平行) の場合はどうでしょうか.詳細は疲れてきたので省きますが,Slater の条件と,$A$ が行フルランクであるという仮定を使えば,そのようなケースは存在しないということが言えます.

最適性条件

強双対性が成り立てば双対問題をかわりに考えればいいことが分かりました.しかし実際にそれを解く,つまりにはどうすればいいでしょうか.
$x^\star$, $(\lambda^\star, \nu^\star)$ がそれぞれ主問題,双対問題で最適解となるための必要条件を与えるのがKKT条件です.

相補性条件

強双対性が成り立っていると仮定した上で,$x^\star$, $(\lambda^\star, \nu^\star)$ をそれぞれ主問題,双対問題の最適解とします.このとき,
 f_0(x^\star)
 = g(\lambda^\star, \nu^\star)
 = \inf_{x} \left( f_0(x) + \sum_i \lambda^\star_i f_i(x) + \sum_i \nu^\star_i h_i(x) \right)
 \le f_0(x^\star) + \sum_i \lambda^\star_i f_i(x^\star) + \sum_i \nu^\star_i h_i(x^\star)
      \le f_0(x^\star)
です.最後の不等式は各変数が主問題,双対問題の実行可能解であるることから $\lambda^\star \ge 0$,$f_i(x^\star) \le 0$,$h_i(x^\star)=0$ であることを用いています.これより道中の不等号は等号なので,
\[
\lambda^\star_i f_i(x^\star) = 0
\]
が成り立ちます.つまり制約関数とそれに対応するラグランジュ乗数のどちらかは必ず $0$ になります.これを相補性条件と呼びます.

勾配=0

ここで簡単のため,各関数 $$ は各点で微分可能 (したがってラグランジュ関数も微分可能) とします.
先ほどの項でも示しましたが,$x^\star$ は  \inf_{x \in D} L(x, \lambda^\star, \nu^\star) の minimizer なので,$x=x^\star$ における偏微分は $0$ でなければなりません.つまり,
\[
\nabla f_0(x^\star) + \sum_i \lambda^\star_i \nabla f_i(x^\star) + \sum_i \nu^\star_i \nabla h_i(x^\star) = 0
\]
でなくてはなりません.

KKT 条件=0

KKT 条件は,主問題と双対問題の制約条件と,上記の相補性条件と勾配=0の条件から成り立ちます.列挙すると以下のとおりです.

  • $f_i(x^\star) \le 0$
  • $h_i(x^\star) = 0$
  • $\lambda^\star_i \ge 0$
  • $\lambda^\star_i f_i(x^\star) = 0$
  • $\nabla f_0(x^\star) + \sum_i \lambda^\star_i \nabla f_i(x^\star) + \sum_i \nu^\star_i \nabla h_i(x^\star) = 0$

これまでに見たように,問題が強双対性を満たしかつ $(x^\star, \lambda^\star, \nu^\star)$ が主問題/双対問題で最適解なら,$(x^\star, \lambda^\star, \nu^\star)$ はKKT条件を満たします.つまりKKT条件は最適解であるための必要条件です.
では,逆はどうでしょうか.実は,主問題が凸の場合は,KKT条件は最適解であるための十分条件になっていることが言えます.細かい証明は省略しますが,ある $(\tilde{x}, \tilde\lambda, \tilde\nu)$ がKKT条件を満たすとすると,相補性条件のあの式みたいな感じで式変形をすれば $g(\tilde\lambda, \tilde\nu) = f_0(\tilde{x})$ が言えます.

したがって,主問題が凸でかつ各関数が微分可能な場合は,KKT条件に沿って最適解を達成する変数を求めることができます.

その他

  • 今まで最小化問題を考えていましたが,代わりに最大化問題にしても同様の議論が成り立ちます.不等号制約関数で向きが逆になったりしても同様.
  • Boyd本には上記で書いた解釈以外にも様々な解釈(conjugate function,min-max,ゲーム等)が載っています.
  • 非凸の場合には具体的にはどうすればいいのかとかは僕が見た限り書かれていませんでした.一般には綺麗に解けないということなんでしょうか.
  • 等号制約は線形のものばかり扱われましたが,線形以外だとどうでしょうか.Boyd本のExercise 5.21に例があるのですが,等号制約関数が凸であるのに強双対性が成り立たない例があります.次のようなものです:$\max_{x\in \mathbb{R},y>0} e^{-x}$ $\mbox{subject to}$ $x^2/y=0$.主問題の最適解は $1$ ですが,双対問題の最適解は $0$ になってしまいます.
  • ラグランジュの未定乗数法は,等号制約しかない場合にKKT条件を使って最適解を解析的に求める手法のこと(だと思います).

まとめ

  • 強双対性が成り立つと主問題の代わりに考えやすい(かもしれない)双対問題を考えれば良くなって便利.
    • たとえば,主問題で変数の個数が多いが制約の個数が少ないような場合,双対問題では変数の個数が少なくなって解きやすくなる可能性がある.
  • 主問題が凸(目的関数と不等号制約関数が下に凸で等号制約関数が線形)でSlaterの条件が成り立つなら強双対性が成り立つ.
  • KKT条件 = 主問題の条件 + 双対問題の条件 + 相補性条件 + 勾配=0の条件
  • 強双対性が成立し,かつ目的関数と各制約関数が微分可能な場合,KKT条件は各変数が最適解を取るための必要条件になっている.
  • 実際に問題を解きたい場合は,まず主問題に強双対性が成り立つことを確認した上で,KKT 条件にしたがって解けば良い.
  • 主問題が凸じゃない場合に強双対性が成り立つかはちょっと考える必要があるかもしれません.
    • 指標の1つとして,等号制約が線形でない場合は,$\mathcal{A}$,$\mathcal{B}$ の分離平面で $t$ 軸に平行なものが存在しなければセーフ(のはず).

*1:ベクトル同士の不等号は要素ごとの不等号です

*2:双対問題の計算は若干面倒なのですがここでは省略します.

*3:$\mathbf{int}$ は集合の内点を表す記号.

PFIセミナーで「ICALP参加記」について話しました

先週木曜(2014/8/7)のPFIセミナーで表記のタイトルで発表したので,その資料を公開します.
7月にコペンハーゲンで開かれた理論計算機科学の学会に行ってきたときの話を雑多に書いています.

僕が会議に参加した時の発表スライドも公開しています.


余談