意訳：2009年から2014年の機械学習の理論的進歩について教えてください
Quoraに投稿された質問 "What has happened in theoretical machine learning in the last 5 years (2009-2014)?"
「2009年から2014年の機械学習の理論的進歩について教えてください」
への、機械学習研究者Yisong Yueの回答を翻訳しました。そのままだと通じない部分は意訳しているので、原文に忠実ではありません。
「2009年から2014年の機械学習の理論的進歩について教えてください」への回答
私の個人的な視点で話します。
潜在変数モデルに対する最適推定について:
理論的な進歩として私が最初に思いつくのは、潜在変数モデルに対する（ほぼ）最適な推定です。この潜在変数モデルの最適推定は一般的に非凸な問題であり、つまり（よく知られている）凸最適化の手法の通用しない難題です。
最も輝かしいアプローチはスペクトラル学習を利用するものです。スペクトラル学習の最も重要なツールは特異値分解です。特異値分解は、問題の構造を仮定することにより、特定の非凸の問題を最適に解くことができます。大雑把にいうと、スペクトラル学習や関連手法は線形代数とモーメントの方法を使い、潜在変数のある非凸な問題を特異値分解によって最適に解ける問題に再定式化します。
近いアプローチとして、低ランク行列復元とスパース辞書からの完全情報復元があります。これらの手法に共通しているのは、推定問題に対する代数構造の性質をうまく利用することによって最適な解を導くというものです。
機械学習のコミュニティにはそんなに有名ではないかもしれませんが、ノイズのあるデータからの超解像という問題があります。基本的なアイディアとしては、同じデータに対して複数の解像度の低いノイズを含むソースがあった場合にそれらを重ねあわせて信号解析を行おうというものです。ソースが解像度が低くノイズが乗っているにもかかわらず、解像度の高いデータを復元可能なことをこの論文は示しました。
インタラクティブな機械学習について：
近年、適応的・インタラクティブなアルゴリズムの最適性について多くの研究がなされています。
適応的劣モジュラ性の方向性は非常に興味深いです。劣モジュラ関数は、情報量の増加や多様性を扱うためのツールとして近年注目されています。まず、その前に能動学習について説明しましょう。能動学習は、クエリ（データ要求）を適応的に出すことによって少ないデータ数で問題に対しての不確定性を減らし正確な推定を得る方法です。
適応的劣モジュラ性は、多くの能動学習の問題を一般的な枠組みで解く仕組みだと思ってください。これらの問題が適用可能な例としては、医療テストでの患者の病気をできるだけ少ない問診で絞り込む問題などです。
関連問題として、インタラクティブ劣モジュラ集合被覆の問題などがあります。
能動学習の分野はここ数年で大きな進歩がありました。とくにこれという論文は思いつきませんでしたが、いくつか良い論文が挙げられます。能動学習において強い性能保証があるアルゴリズムを作るための課題は、問題を解く決定木の組み合わせが指数的になることです。例えば、20のYes/No式の組み合わせがあった場合には、2^20通りの組み合わせが知識の状態としてありえることになります。理想的なアルゴリズムは、20の問題の回答がどのようにあっても解くことができなければなりません。
関連する研究の流れとしては、多腕バンディット問題のアルゴリズムがあります。この分野で最も興味深い進歩は、トンプソンサンプリングをはじめとする確率マッチングのアルゴリズムでしょう。これらのアルゴリズムは、計算的な単純さから非常に大きな興味を持たれています。しかし、理論的な解析はこれまであまり行われていませんでした。近年の２本の論文（とその関連研究）は、この分野における理論的な解析を行っています。とくに、後者の論文は確率マッチングの解析をよく知られている信頼上限法の解析に還元するものですが、適用範囲が非常に広く興味深いです。
機械学習とゲーム理論：
ゲーム理論は戦略的な意思決定を扱う分野です。
ゲーム理論の応用例としては、オンライン広告における価格の決定があります。オンライン広告の価格は、ウェブサイトと広告出稿者の収益を最適化するように決められます。最適価格は広告のコンバージョン率や、コンテキスト（つまり検索クエリ、コンテンツ、ユーザ情報）に依存するため、この価格の学習ではこれらの要因を考慮にいれる必要があります。
一般的に、ゲーム理論の研究者はこれまで、エージェントが(A)十分大きな計算リソースを持っていることと(B)自分にとっての環境に対して完全な情報を持っていることを仮定してきました。言い換えると、(A)は指数的な計算量を要求するような戦略を許容すること、(B)は環境に対する学習が要らないことを意味します。
もちろん、この2つの仮定は現実世界では正しくありません。しかし、多くのゲーム理論における解析はこの２つの仮定において特定のメカニズム（メカニズムの例としては、オンライン広告では広告出稿者が広告市場とどのようにやりとりを行うかの枠組みを想定してください）が誘引両立的であること（訳注：戦略的に価格を操作したりしてもメリットが得られない健全なシステムであること）を示すことに成功してきました。この分野はメカニズムデザインと呼ばれています。
ここ数年の優れた論文は、メカニズムデザイン下での学習（誘引両立的を満たす学習）をこの２つの伝統的な仮定の外でも行うにはどのようにすればいいかを示しました。例えば、(B)を仮定せずに不確定性のある状況下でどのような学習をすればよいか。例としては"Truthful Mechanisms with Implicit Payment Computation"という論文があります。
もうひとつの研究の流れは、複雑なマーケットの動きを予測することです。こちらは戦略の計算量の削減に貢献し、２つの仮定の(A)を取り除いた計算可能な戦略を作ることに貢献しました。例としてはこの論文を挙げておきます。
機械学習とプライバシー：
プライバシー保護は、データを扱う上でどんどん重要になっています。差分プライバシーという概念は、公開データに故意にノイズを入れることによってどれだけその中にあるプライベートなデータを守れるのかを統計的に考察します。差分プライバシー下での機械学習は近年の研究の１つの流れとなっています。この論文が参考例です。
（訳はここまで）
所感：
Yisong Yueの論文は結構追っているので、彼が機械学習に対してどういう概観を持っているのかというのは僕にとっては面白いですね。
あまり関係ありませんが、YisongのHPは彼の顔写真がたくさん掲載されていてすごい自信家だなーと思います。
