バンディットアルゴリズムの評価と因果推論
Blog
NeurIPS 2019 参加報告
はじめに
AI Labの森下，野村，インターンの齋藤です．
本稿では，2019年12月8日から14日にカナダのバンクーバーで開催された機械学習の国際会議，NeurIPS 2019についての参加報告を行います．なんと参加者数は12000人を突破しており，2018年の約8000人を大きく上回っていました．
会場からの風景
AI Labからの発表
AI Labからは残念ながら今回本会議の発表はありませんが，ワークショップとメンタリングセッション合わせて3件の研究発表をさせていただきました．
- Dual Learning Algorithm for Delayed Feedback in Display Advertising
Yuta Saito, Gota Morishita, Shota Yasui
http://tripods.cis.cornell.edu/neurips19_causalml/
- Warm Starting Method for CMA-ES
Masahiro Nomura, Shuhei Watanabe, Yoshihiko Ozaki, Masaki Onishi
- Simple and Scalable Parallelized Bayesian Optimization
Masahiro Nomura
https://nehzux.github.io/NewInML2019/
研究の動向（EconCS）
EconCSと呼ばれる経済学とコンピューターサイエンスの融合分野があります. NeurIPSではGame Theory and Computational Economicsと呼ばれるポスタートラックがあり, 18本ほどありました. その中で, テーマの内訳は以下のようです.
- Mechanism Design 8本
- Auction関連
- Computation of Nash Equilibria 6本
- 展開型ゲームのCorrelated equilibriaを求めるアルゴリズム
- Others 4本
- Security GameやGANの評価方法
経済学でも花形であるMechanism Designの研究が多く, その中でもオークション理論に関するものが多かったです.
その中で１つ紹介したいと思います.
Learning Auctions with Robust Incentive Guarantees
EconCSの文脈では, メカニズムデザイナーは入札者の価値の分布を標本から近似し, 最適なメカニズムを作ることを目的とすることが多いです. その中で, この論文では, 入札者が戦略的に嘘の入札額を申告して, 入札者にとって望ましいメカニズムを作るようなインセンティブが存在しないようにメカニズムを標本から学習するアルゴリズムを提案しました.
この論文の肝となるアイディアは, アルゴリズムのセキュリティを担保するdifferential privacyという性質を用いたことです. differential privacyとは, 標本の中のある特定の１つのサンプルが大きく変わったとして, アルゴリズムのアウトプットはほとんど変化しないという性質です. これをオークションの文脈で読み替えると, 入札者の中である特定の1人が嘘の申告をしたとしてもメカニズムの結果はほとんど変化しないという性質となります. この性質を持つようなメカニズムを学習するアルゴリズムは, 嘘をつくインセンティブを減らし, 結果として利益もある程度担保されることを証明しました.
研究の動向（Causal Inference）
今回のNeurIPS本会議では因果推論関連の研究の存在感はあまりなかったように感じます (CausalML Workshopではたくさん議論されていますが). 特に近年乱立傾向にあった個別的因果効果予測の精度を追求するような研究は他の会議も含め（やられ尽くしたのか）少なくなってきていると思います. 一方で今年は操作変数と機械学習の融合のような研究がいくらか見られました. 以下はその一例です.
Kernel Instrumental Variable Regression
操作変数法の通常のアプローチは, 2段階最小二乗法と呼ばれるものです. これは, まず操作変数ZでX(Z)を回帰する. そのX(Z)を用いてYを回帰します. ただし, これには変数間に線型性を仮定しています. この論文では, 線形回帰の部分をKernel Ridgeに変えることで計算時間や実装コストの改善をしました. また実験的にデータが少ない時でも, 性能良く推定できたことも示しました. 著者のインタービュー動画も上がっています.
Machine Learning Estimation of Heterogeneous Treatment Effects with Instruments
こちらは操作変数を使える状況で個別的因果効果を予測するためのメタ的な学習過程を提案している論文です. Lassoなどよく用いられる機械学習の手法と組み合わせることが可能であり, 実装が簡単であることや解釈性を担保できることが推されていました. 実際, 論文ではTripAdvisorのデータを活用し, 介入が効きそうな群をデータから解釈するような解析が載っています. そのそも著者がEconMLの開発グループなのですが, 実際にこの論文で提案されている手法もEconMLに実装されているようです.
研究の動向（Off-Policy Evaluation & Learning）
Off-Policy Evaluationとは, ある方策(policy)の性能を別のpolicyによって集められたデータを使って推定するための手法を開発する分野です. 強化学習よりもシンプルなcontextual banditの設定におけるOPEに関してAI Labから過去にAAAI2019で論文を発表したり, Blogにまとめるなどしています. まだまだ日本ではメジャーな分野ではないのかなと思っていますが, ことNeurIPSにおいてはこのOPEが強化学習の中の1分野として確立されているんだなということを肌で感じました. また因果推論ですでに知られた結果の強化学習への移植はだいぶ進みほかの分野との融合が動き始めた印象があります. 例えば今年はPositive-Unlabeled Learningの応用が存在しました(後述). 一方で, OPEの精度を実データで検証している論文はなく企業としては今後狙い目になってくるのかなと感じました.
Semi-Parametric Efficient Off-Policy Learning with Continuous Action Spaces
Microsoft ResearchのEconMLのグループの研究. 連続的な介入空間に置いてofflineで最適な方策を学習する問題(例えば投薬量最適化)について, 報酬関数のsemi-parametric性を仮定した上でlossの構築方法 (doubly-robust like)の提案と理論解析を行う. 仮定が満たされない場合のrobustnessも証明しました.
Off-Policy Evaluation via Off-Policy Classification
Google BrainとDeep Mindの研究. Off-Policy Evaluationの基本はImportance Weightを用いてバイアスを除去する. しかし, この論文はImportance Weightを全く使わず報酬がbinaryの場合のOPEをPositive-Unlabeled Learningで定式化することで, importance weightを用いたときに発生する問題を回避しています.
研究の動向（AutoML）
本会議ではベイズ最適化についての研究もたくさんあったのですが，純粋なBlack-box最適化の研究の数はそれほど多くないと感じました．具体的には，以下のような一歩踏み込んだ問題設定についての研究が発表されていました．
- 多目的最適化問題
- 動的な探索空間における最適化
- Heavy-tailedなノイズの分布の仮定
- Contextualなベイズ最適化
- 組み合わせ最適化のためのベイズ最適化
その中から，いくつか私が気になった論文を以下に紹介します．
Bayesian Optimization with Unknown Search Space
通常，ベイズ最適化を実行する際は，Box制約を指定（各変数ごとに上限と下限を指定）した後に最適化を開始します．しかし，例えばハイパーパラメータ最適化を考えた時，ユーザが指定した探索空間に最適解（または良好解）が含まれているという保証はありません．こちらの論文では，状況に応じて段々探索空間を大きくすることで，上記の問題点に対処した方法を提案しています．アルゴリズムはGP-UCBをベースとしたアルゴリズムとなっています．論文内では，最適解までの接近条件に関する理論解析も行われています．
Bayesian Optimization under Heavy-tailed Payoffs
ベイズ最適化における多くの研究では，ノイズの従う分布が(sub-)Gaussianであることを仮定しています．しかし，金融や保険の分野などではノイズの従う分布がheavy-tailedな場合が多くあります．こちらの論文では，ノイズがheavy-tailedな分布に従っている場合でも適切に動作するアルゴリズムを提案しています．また，このような場合に緩い条件下でno regretを達成するという解析も行われています．
Practical Two-Step Lookahead Bayesian Optimization
従来のベイズ最適化は，one-stepの意味で最適な点を選択していました．例えば，最も頻繁に用いられる獲得関数であるExpected Improvement (EI) は，次の探索点がどれだけ基準点（多くの場合，最良点）の評価値を改善するかを計測する指標です．しかし，これは残り評価回数が1回よりも多く存在する場合にはgreedyな選択になるすぎるという傾向がありました．こちらの論文では，two-stepの意味で最適な点を選択する2-OPTという獲得関数を提案しています．また，2-OPTの勾配に関するunbiased estimatorの導出，効率的なモンテカルロ近似のためのvariance reductionなども提案されています．
Scalable Global Optimization via Local Bayesian Optimization
こちらの論文で提案されている手法は，ある定められたtrust region内にサンプルを生成するように制限をしています．具体的には，これまで得られている最良解の周りにtrust regionを形成し，その付近でbatch Thompson Samplingを実行しています．より良い解が見つかったら拡大，そうでなければ縮小することで，動的にtrust regionを更新していきます．これにより，有望領域に解が生成されやすくなり，良好な性能に繋がったとの報告がなされています．
Constrained Bayesian Optimization with Max-Value Entropy Search
こちらはWorkshop on Meta Learningにて発表されていた，制約付き問題のためのベイズ最適化手法を提案している論文になります．明示的な制約のみでなく，”制約を満たしていない”ことだけがわかるbinary feedbackにも対応しているというのが一つの特徴です．従来手法としてExpected Improvement (EI) ベースの手法がありましたら，こちらの手法では基準点からの改善量を計算する必要があるため，実行可能解が存在しない場合には定義できない量となっていました．そこで，Max-Value Entropy Searchを用いることでこの問題を回避しています．Max-Value Entropy SearchはEntropy Searchを少ない計算コストで近似する手法です．
おわりに
参加者数としては非常に大規模となった今年のNeurIPSですが，ポスターセッションなどで分野の近い研究者と議論をすることができ，有意義な時間となりました．AI Labでは，機械学習を活用した研究開発を積極的に行っています．興味を持っていただいた方は，採用のページもぜひご覧ください．
Author
nomura
