インフラエンジニアが見た機械学習のトップカンファレンス NIPS 2016

これは [リクルートライフスタイル Advent Calendar 2016](http://qiita.com/advent-calendar/2016/recruitlifestyle) の23日目の記事です。

# この記事は何？

ども、データエンジニアリンググループで主にログ収集・解析基盤の面倒を見ている tmshn と申します :raised_hand:
この記事は、私が機械学習のトップカンファレンスである [NIPS](https://nips.cc) に参加して感じたことや注目した発表などを共有するものです。

機械学習の研究界隈の最新の動向について把握するのに役立つかも知れ……いや、うーん、やっぱ役立たんかも。私の所属するグループ※の特性上、**「機械学習における研究とアプリケーションの橋渡し」** という観点で見ていただいた方がいいかも知れませんね。

※ 弊グループがどんなグループかについては、[6日目の \_stakaya さんの記事](http://qiita.com/_stakaya/items/21d6e8b9c1f7c8529e2f#%E3%81%AF%E3%81%98%E3%82%81%E3%81%AB) を御覧ください :eyes:

# NIPS とは？

正式には "Conference on Neural Information Processing Systems" という、30年の歴史を持つ国際学会。今では機械学習（特に理論寄り）のトップカンファレンスの1つに数えられます。

実はもともとニューラルネットの学会として発足したもので、近年の深層学習の隆盛である種の「原点回帰」を果たしたのは数奇な奇跡/軌跡ですね！

## 数ある機械学習系学会の中での立ち位置

これは、産総研の神嶌敏弘さんがまとめられている "ML, DM, and AI Conference Map" という図が分かりやすいので下に引用します。

![MLDMAImap.png](https://qiita-image-store.s3.amazonaws.com/0/105378/b55aa43c-cd5f-5291-8784-f69f3752d40e.png)

[Software and Data Sets (Toshihiro Kamishima)](http://www.kamishima.net/soft/) より

ちょっと数が多くて見づらいですが、NIPS が左上の方で *Neural Network* と *Machine Learning* というカテゴリに入っているのが分かりますね。
*Data Mining* カテゴリに入っている WSDM や KDD といった学会よりも青字で *Statistics, Brain Science* などと書かれた方に近いのが特徴かと思います。

## 今年の NIPS

今年の NIPS は、スペインはバルセロナで12月5日（月）から12月10日（土）までおよそ1週間に渡って開催されました。
機械学習ブームの中で年々参加者が増え、今年は5000人超だったとか（6000人だったという人も？）。
「早くチケットを買わないと売り切れる」なんて連絡が回ってきて慌てて購入したくらいで、実際にチケットが買えずに悔しい思いをした人も多かったようです。
そのせいもあるのか、例年シングルトラックだったのが今年はマルチトラックでした。

今年のトピックは下記ツイートに端的にまとまっています:

<blockquote class="twitter-tweet" data-lang="ja"><p lang="en" dir="ltr">NIPS 2016 trends: learning-to-learn, GANification of X, Reinforcement learning for 3D navigation, RNNs, and Creating/Selling AI companies</p>&mdash; Tomasz Malisiewicz (@quantombone) <a href="https://twitter.com/quantombone/status/807712841230852096">2016年12月10日</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

個人的な感覚としても、GAN（深層学習による生成モデルの一種）の話と強化学習の話（3Dナビゲーションに限らずですが）はかなり多かったかな、という印象です。

一方で最適化・行列分解・クラスタリングといった話をやり続けている方もかなりたくさんいたようで、時流に乗らずともきちっと評価される研究が出てくるのがいいなと感じました。

## 併せて読みたい

さて、本題に入る前に、既にインターネット上に公開されている今回の NIPS の参加報告記事などへのリンクを紹介したいと思います。

- [NIPS 2016 Proceedings](https://papers.nips.cc/book/advances-in-neural-information-processing-systems-29-2016)
    - 公式の proceedings （論文集）。全部読めます :tada: （大学等の研究機関に所属してない身としては超ありがたい！）
- [Neural Information Processing Systems Conference - NIPS 2016 | Channel 9](https://channel9.msdn.com/Events/Neural-Information-Processing-Systems-Conference/Neural-Information-Processing-Systems-Conference-NIPS-2016)
    - 発表の公式ビデオ :tada: 
- [しましまのNIPS2016まとめ - Togetterまとめ](https://togetter.com/li/1055793)
    - 先にも名前の出た神嶌さんによる参加者のツイートまとめ。会場のライブな空気感が伝わってきます。
- [NIPS 2016参加報告 - Qiita](http://qiita.com/yoh_okuno/items/2494bc79630eb57e81ba)
    - おそらく本記事執筆時点で Qiita 上唯一の NIPS 2016 参加報告（個別の論文の紹介等は既に上がっている/これから上がると思いますが）。深層学習周りの雰囲気がつかめます。
- [NIPS2016報告記【前編】 | RCO アドテクLabブログ](https://www.rco.recruit.co.jp/career/engineer/blog/54/)
    - 一緒に参加していたリクルートコミュニケーションズ社員の参加報告（前編）。同じグループ会社に所属していながら、私とはまた違った研究に着目しています。
- [NIPS 2016 - Andrew L. Beam](http://beamandrew.github.io/deeplearning/2016/12/12/nips-2016.html)
    - Harvard のポスドクの方による参加報告（もちコース英語です）。実際に会場で話題になっていたことがまとまっていて良い記事です。
- [NIPS2016.md - artsobolev’s gists](https://gist.github.com/artsobolev/63942e24c81fc296472affb1f138d54c)
    - まとめ記事のまとめ。ほとんど見られていないのですが、まぁたぶん全部イングリッシュ。

# ためになったチュートリアルたち

### Nuts and Bolts of Building Applications using Deep Learning ― Andrew Ng

- [資料 (Dropbox)](https://www.dropbox.com/s/dyjdq1prjbs8pmc/NIPS2016%20-%20Pages%202-6%20%281%29.pdf)

![Ng_NutsBolts.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/621a5d7b-cbbc-f01d-8857-927ad61c298a.jpeg)
当日の講演の様子（筆者撮影／被写体のコンテンツの著作権および肖像権は発表者本人にあります）

スタンフォード大・Baidu 社の Andrew Ng による、機械学習を用いたアプリケーションを作るためのガイドライン。
エンジニアとして大変ためになるチュートリアルでした :clap:

なんと5000人の聴衆を前にホワイトボードに板書しながら進めていく講義スタイルでかっこよかったのですが、字が~~汚すぎて~~大変達筆でいらっしゃって、一生懸命聞きながらじゃないと全然読めないマジつらい。

話は主に下記の3点：

1. 深層学習のトレンド：
    - 旧来の機械学習はデータ量が増えても精度がある程度のところでサチるが、（特に大規模ネットワークによる）深層学習はそれがちゃんと「スケール」する
    - End-to-end 学習（前処理かけたり複数のモデルを組み合わせたりすることなく、入力と出力の関係を直接単一のモデルで学習すること）が今後複雑なデータでも一般的になる
1. 訓練データセットとテストデータセットの分布が違う場合のバイアス／バリアンスの考え方
    - どうしても大量の訓練データが手にはいらない場合、訓練データを人工的に生成したり、類似のデータセットを使うケース（たとえば自動車内の音声認識の学習に、スタジオ録音の音声を訓練データに使うなど）が増えてくる
    - 詳細はスライド参照
    - 「医療画像認識におけるヒューマンレベルエラーとは、次のうちどれ？ 1.素人、2.普通の医者、3.熟練の医者、4.熟練の医者のチーム」という問題で会場のみんなに手を挙げさせたりしていた（だいたいの人があっていたので Ng 先生は喜んでいた）（答えはスライドをご確認ください）
1. AI プロダクトにおけるプロダクトマネージャとエンジニアの役割分担
    - プロマネがテストデータセットと評価指標を用意して、エンジニアが訓練データの収集とシステム開発を行う、という提案
    - ~~汚い~~達筆な字で板書しながら「読めなくても安心して！ 『Andrew がこんなこと言ってたよ』って同僚や上司に見せるためのスライドはあとで公開するから！」って言ってた

あとは学生向けに、前処理とかデータクレンジングとか大変だろうけど、そういう汚れ仕事をちゃんと自分でやるのも大事だという旨のアドバイスもしていました。

### Generative Adversarial Networks ― Ian Goodfellow

- [資料 (PDF)](http://www.iangoodfellow.com/slides/2016-12-04-NIPS.pdf)

![Goodfellow_GAN.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/eff5f423-0491-0a8b-6759-8862de096892.jpeg)
当日の発表スライドより（筆者撮影／被写体のコンテンツの著作権は発表者にあります）

今年の最大のトレンドである GAN (Generative adversarial network) について、考案者である Ian Goodfellow 本人による大変わかりやすいチュートリアルがありました。

そもそも GAN というのは深層学習を用いたデータの生成モデルで、データの分布も明示的に扱わずマルコフ鎖も使わないのが特徴です。
GAN は実際にデータを生成する generator というモジュールと、データが真のデータなのかどうかを見分けようとする discriminator というモジュールを組み合わせたものなのですが、それらの関係を偽札師と警察の関係に喩えた比喩が分かりやすかったです。

またこの発表ではとある「一悶着」がありました。
それは、Jürgen Schmidhuber （LSTM 考案者）が「それは私の○○という研究と関係があるのか？」というような質問で割り込んできたことです。
他の参加者の方に教えてもらったのですが、この Schmidhuber という方は Bengio, Hinton, LeCun のいわゆる「ディープラーニング三聖」が深層学習の関する手柄を不当に独占していて、先行研究に十分な敬意を払っていないという問題提起をずっと続けているんだそうです（本人の主張については [こちら](http://people.idsia.ch/~juergen/deep-learning-conspiracy.html) が詳しい）。

とは言え聴衆としては知ったことではないですし、チュートリアルの邪魔をするなという反応が多かったようです（たとえば下記ツイート）。個人的には、会場がけっこうザワザワしていて面白かったです。

<blockquote class="twitter-tweet" data-lang="ja"><p lang="en" dir="ltr">Schmidhuber interrupted the GAN tutorial, stealing time from those listening &amp; learning. I don&#39;t care who you are, don&#39;t do that.<a href="https://twitter.com/hashtag/nips2016?src=hash">#nips2016</a> <a href="https://t.co/NqCHkAynCm">pic.twitter.com/NqCHkAynCm</a></p>&mdash; Smerity (@Smerity) <a href="https://twitter.com/Smerity/status/805785999959879680">2016年12月5日</a></blockquote>
<script async src="//platform.twitter.com/widgets.js" charset="utf-8"></script>

※ 後で気づきましたが、このツイート主さんは [「LSTMを超えたか！？」と今話題](http://qiita.com/icoxfog417/items/d77912e10a7c60ae680e) の QRNN のセカンドオーサーでした。

# 個人的に注目の研究たち

まだちゃんと論文にまでは目を通せていないのですが、オーラル発表・ポスター発表で個人的に「おっ」と思ったものをバシバシ紹介していきたいと思います。

なお下記に載せている画像は（特段の断りがない限り）、会場のポスターセッションで本記事著者が撮影したもので、当然ですが__個々のポスター自体の著作権は発表者にあります__。

## 目次

- 深層学習篇
    - [Learning What and Where to Draw ― Scott Reed, et al.](#learning-what-and-where-to-draw--scott-reed-et-al)
    - [Learnable Visual Markers ― Oleg Grinchuk, et al.](#learnable-visual-markers--oleg-grinchuk-et-al)
    - [Phased LSTM: Accelerating RNN Learning for Long or Event-based Sequences ― Daniel Neil, et al.](#phased-lstm-accelerating-rnn-learning-for-long-or-event-based-sequences--daniel-neil-et-al)
    - [Hierarchical Question-Image Co-Attention for Visual Question Answering ― Jiasen Lu, et al.](#hierarchical-question-image-co-attention-for-visual-question-answering--jiasen-lu-et-al)
    - [Learning values across many orders of magnitude ― Hado van Hasselt, et al.](#learning-values-across-many-orders-of-magnitude--hado-van-hasselt-et-al)
    - [Deep Learning without Poor Local Minima ― Kenji Kawaguchi](#deep-learning-without-poor-local-minima--kenji-kawaguchi)
- レコメンデーション篇
    - [Deconvolving Feedback Loops in Recommender Systems ―  Ayan Sinha, et al.](#deconvolving-feedback-loops-in-recommender-systems---ayan-sinha-et-al)
    - [Matrix Completion has No Spurious Local Minimum ― Rong Ge, et al.](#matrix-completion-has-no-spurious-local-minimum--rong-ge-et-al)
- 最適化篇
    - [Minimizing Quadratic Functions in Constant Time ― Kohei Hayashi, et al.](#minimizing-quadratic-functions in-constant-time--kohei-hayashi-et-al)
    - [Large-Scale Price Optimization via Network Flow ― Shinji Ito, et al.](#large-scale-price-optimization-via-network-flow--shinji-ito-et-al)
- 教師あり学習篇
    - [A Communication-Efficient Parallel Algorithm for Decision Tree ― Qi Meng, et al.](#a-communication-efficient-parallel-algorithm-for-decision-tree--qi-meng-et-al)
    - [General Tensor Co-Clustering for Higher-order Data ― Tao Wu, et al.](#general-tensor-co-clustering-for-higher-order-data--tao-wu-et-al)
    - [Supervised Word Mover's Distance ― Gao Huang, et al.](#supervised-word-movers-distance--gao-huang-et-al)
- その他
    - [Fast and Provably Good Seeding for k-Means ― Olivier Bachem, et al.](#fast-and-provably-good-seeding for-k-means--olivier-bachem-et-al)
    - [Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embedding ― Tolga Bolukbasi, et al.](#man-is-to-computer-programmer-as-woman-is-to-homemaker-debiasing-word-embedding--tolga-bolukbasi-et-al)

## 深層学習篇

### Learning What and Where to Draw ― Scott Reed, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6111-learning-what-and-where-to-draw)
- [ソースコード (GitHub)](https://github.com/reedscot/nips2016)

<details>
<summary>ポスター画像</summary>
![Reed_Learning_What_and_Where_to_Draw.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/008eaa99-88f9-d6c0-b86a-309b1d1671ff.jpeg)
</details>

GAN を用いた画像生成で、タイトルにある通り「どこに何を描くか」を指定できるようにするという研究です。「どこに」の部分は長方形の領域指定かキーポイントの指定で、「何を」の部分はテキストで指定できるようです。

サンプルで提示されている結果がすごく綺麗で「もうこんなことが出来るのか」とけっこう驚いた一方で使われているネットワーク構造がかなり複雑で「こんなものよく思いついたな」とも感じました（実際に会場からも「もうちょっとシンプルな構成ではできなかったのか？」みたいな質問があったくらいです）。
ただそれがどんなに複雑で「そんなの思いつかねーよ」という構成でも、逆に言えばその構成を発見/発明してくれた功績は大きいわけで、そういう意味でも良い研究と言えるんじゃないかなーと思いました。

### Learnable Visual Markers ― Oleg Grinchuk, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6323-learnable-visual-markers)

<details>
<summary>ポスター画像</summary>
![Grinchuk_Learnable_Visual_Markers.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/a3e3e7e2-bdc9-6b9f-90af-5b8304ad4e38.jpeg)
</details>

こちらも画像生成系の話ですが、これは QR コードのようなビジュアルマーカーを入力テクスチャ画像に馴染むような形で生成するという研究。
GAN を使っているわけではないようですが、マーカーをデコードする recognizer が GAN でいう discriminator と似た役割を果たしているのかも？と思いました。

今すぐ「コレに使える」というのがあるわけではないですが、応用先を色々と妄想できる楽しい研究ですね。

### Phased LSTM: Accelerating RNN Learning for Long or Event-based Sequences ― Daniel Neil, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6310-phased-lstm-accelerating-recurrent-network-training-for-long-or-event-based-sequences)
- [ソースコード (GitHub)](https://github.com/dannyneil/public_plstm)

<details>
<summary>ポスター画像</summary>
![Neil_Phased_LSTM_Accelerating_RNN_Learning_for_Long_or_Event-based_Sequences.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/ae86235c-028a-027a-96a8-c194d9716da4.jpeg)
</details>

こちらは LSTM に明示的にいろんな周波数のクロックゲートを追加することで、長いシーケンスや、色々な記録周波数のデータに対して高精度を達成したという研究。

センサーネットワークなどでは個々のセンサーの記録周波数がまちまちで、それらを統合して学習するのは難しそうなのですが、このモデルはそういった状況に対応できるということで頼もしいです。
また、ゲートは閉まっている時間のほうが長いので、ドロップアウト同等の正則化効果があるということも言っていました。

### Hierarchical Question-Image Co-Attention for Visual Question Answering ― Jiasen Lu, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6202-hierarchical-question-image-co-attention-for-visual-question-answering)
- [ソースコード (GitHub)](https://github.com/jiasenlu/HieCoAttenVQA)

<details>
<summary>ポスター画像</summary>
![Lu_Hierarchical_Question-Image_Co-Attention_for_Visual_Question_Answering.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/947fa5af-037a-8e45-c5b0-a8c99db40f67.jpeg)
</details>

与えられた画像について質問に答える Visual Question Answering の問題設定で、画像のアテンション（どこに注目すべきか）とともに質問のアテンション（どの言葉に傾聴すべきか）を学習するという研究。
質問に関しては文章レベル・句レベル・単語レベルの3段階の階層を導入したとのことです。

自分はこのトピックの研究がどのくらい進んでいるのか分からないので正当な評価はできませんが、コントリビューション部分の拡張の仕方も自然だし、サンプルの結果もきれいで納得感の高い研究でした。

### Learning values across many orders of magnitude ― Hado van Hasselt, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6076-learning-values-across-many-orders-of-magnitude)
- [動画 (YouTube)](https://www.youtube.com/watch?v=68LfBLPLySg)

<details>
<summary>ポスター画像</summary>
![Hasselt_Learning_values_accross_many_orders_of_magnitude.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/c496917c-c70c-eeac-bf2c-f0c92555225e.jpeg)
</details>

オンライン学習や強化学習では一般に、入力値のスケールが事前に分かっていない（最初のデータと後から来るデータのオーダーが違うなど）と学習が大変だったり、モデルの挙動が後から変わってしまったりといった問題がありました。
これに対し、都度うまく正規化をかけていくことでこの問題を解決したのがこの研究です。

パックマンなどのゲームでの応用例が紹介されていましたが、Web データの学習でも同様の問題は起きうるので大変有意義な研究だなと思いました。

### Deep Learning without Poor Local Minima ― Kenji Kawaguchi

- [論文 (proceedings)](https://papers.nips.cc/paper/6112-deep-learning-without-poor-local-minima)

_（すみません、これはポスター画像を撮っていなかったようです……）_

線形な、または ReLU を活性化関数に用いた深層学習モデルには「悪い局所最適」は存在しないけれど、「悪い鞍点」は存在するという研究です。
ここで言う「悪い局所最適」とは大域最適よりも悪い局所最適のことで、逆に言えば、それが存在しないということはすべての最適値が大域最適値に等しいということです。
一方で「悪い鞍点」というのはヘッセ行列が負の固有値を持たない、ということのようです。

現在実際に用いられている深層学習のモデルのほとんどはこの研究が扱うものよりずっと複雑なので、そういう意味ではまだまだ応用の領域まではギャップがありますが、深層学習の理論解析としては重要な一歩になっていると思います。

また著者は日本人で MIT の博士学生ということで、個人的には NIPS に学生が単著で通すってものすごいことだなと感じました（どうやら AAAI にも単著で通していたりと、他の業績もけっこうスゴイ）。

## レコメンデーション篇

### Deconvolving Feedback Loops in Recommender Systems ―  Ayan Sinha, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6283-deconvolving-feedback-loops-in-recommender-systems)

<details>
<summary>ポスター画像</summary>
![Sinha_Deconvolving_Feedback_Loops_in_Recommender_Systems.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/7646763e-5c9a-7e4b-11cf-95fa7394777c.jpeg)
</details>

実際のサービスにおけるレコメンデーションは、普通1回で終わりではなく継続的に行われるものです。
そうすると、ある時点で協調フィルタリングなどで利用する評価行列は、「それ以前のレコメンド提示によって変わった評価」が含まれているわけで、ユーザの評価とレコメンドシステムの間でフィードバックループが形成されています。そうして、やがてそのレコメンドシステムのバイアスが評価行列には蓄積されていってしまいます。

このバイアスを教師無しで補正するというのがこの研究です。
手法としては観測された評価行列を特異値分解することで、ユーザからの真の評価行列が得られるというものでした。

このように継続的な観点でレコメンドシステムを見る視点と、「真の評価行列をもとにレコメンデーションを出すべき」という提案は非常に自分にとって有意義でした。
一方で実際の応用を考えると、レコメンドを出す側はいつ誰にどんなアルゴリズムでアイテムを提示したかは分かっているので、教師ありでより高い精度でこれを実現できるのかも知れないなとも思いました。

### Data Poisoning Attacks for Factorization Based Collaborative Filtering ― Bo Li, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6142-data-poisoning-attacks-on-factorization-based-collaborative-filtering)

<details>
<summary>ポスター画像</summary>
![Li_Data_Poisoning_Attacks_for_Factorization_Based_Collaborative_Filtering.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/2922ead4-f959-0c99-a9df-63de216901bf.jpeg)
</details>

悪意のあるユーザが意図を持ったコンバージョンをすることで、協調フィルタリングの元データを「汚染」することができるよという研究です。

汚染手法もいくつか提案していて、ある程度ナイーブな手法ならば $t$ 検定で発見できるが、通常ユーザへのなりすましまでされたら検出するのは難しいという話でした。

ただし、この「通常ユーザへのなりすまし」をするには推薦システムの内部情報を知っていないといけないので、現実的ではないよね、とのこと。
というか、そもそも悪意のあるデータを注入するには（ハッキングするとかならともかく）「実際にコンバージョン」しなきゃいけないわけだから、それほど警戒する必要はないのかも知れないとも思いました。

とは言え「学習データに対する攻撃」という意識は現場では持っておくべきだと思い、選出しました。

### Matrix Completion has No Spurious Local Minimum ― Rong Ge, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6048-matrix-completion-has-no-spurious-local-minimum)

<details>
<summary>ポスター画像</summary>
![Ge_Matrix_Completion_has_No_Sprious_Local_Minimum.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/24df0223-354a-7e8c-fa45-2067b34074df.jpeg)
</details>

Deep learning の方であった「『悪い』局所最適がないよ」研究の行列補完版にあたるもので、やはりいくつかの前提を置けば、すべての局所最適値が大域最適値に一致するというもの。
ただし、その前提の1つとして半正定値行列でなければならない（つまりそもそも対称行列でなくてはいけない）という条件があり、現実的な問題設定にはまだすこし距離があるようです。

ただ、deep learning の方の研究同様ですが、やはり応用では非常によく使われている手法に対する理論的な解析解いて重要な研究の一歩になるのだろうとは思いました。
（ところで、こんな似た研究がかぶるなんて偶然なのか、それともけっこうよくある話なんでしょうかね。私にはちょっと判断できかねますが）

## 最適化篇

### Minimizing Quadratic Functions in Constant Time ― Kohei Hayashi, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6044-minimizing-quadratic-functions-in-constant-time)

<details>
<summary>ポスター画像</summary>
![Hayashi_Minimizing_Quadratic_Functions_in_Constant_Time.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/06dd85f2-a248-f263-b126-96a26d662120.jpeg)
</details>

タイトルの通り、2次関数を次元数に対して定数時間で（近似）最小化するという研究です。
手法としては行列要素をサンプリングしてその小さい行列を最小化するというものなのですが、このサイズの違う行列間の類似度の計算が肝になります。
この研究では、行列を graphon （グラフの極限を取って連続化したような何か）の空間に埋め込むことでこれを達成し、手法の正当性を証明することに成功しています（全然分かってない）。

全然時流に乗っていないもののかなり有用な研究だなと思ったのと、「定数時間」という変態的な成果を達成するために難しい理論が出てくるところが好きです。いいですよね、定数時間。

それから、こちらも日本人（産総研の方と NII の方）の研究でした。

### Large-Scale Price Optimization via Network Flow ― Shinji Ito, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6301-large-scale-price-optimization-via-network-flow)

_（すみません、これもポスター画像を撮っていなかったようです……）_

一般的には（混合）整数計画問題が登場してかなり解きづらい商品の価格最適化を、うまく制約を入れることで最小カット問題に帰着、最大フローアルゴリズムで解いたのがこちらの研究です。

最大フロー最小カットという手法自体はかなり古典的な感じがしますが、未だに業界では必要とされている（そしてまだまだ改善の余地がある）内容なんですね。
そう言えば弊社でも去年、大規模最適化の事例が話題になっていました（良い紹介ページが見つからないので、とりあえず [IBM の事例紹介](https://www-01.ibm.com/common/ssi/cgi-bin/ssialias?htmlfid=YTC04090JPJA&) へリンク）。

実はこちらの研究も NEC の日本人の発表で、オーラル発表までしていた姿は同じ日本の企業人としてはかっこよかったです。
発表自体の英語はいくらかたどたどしく、質問の人がすごく優しい英語だったのが記憶に残っています。
やっぱり難しいよなぁ、僕も発表は出来ても質問には答えられる気がしません。

日本の企業といえば、この研究とは関係ないですが、NIPS 自体のスポンサーに日本企業で唯一 Panasonic 入ってました（企業ブース覗いたら日本人いませんでしたが）。

### A Communication-Efficient Parallel Algorithm for Decision Tree ― Qi Meng, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6381-a-communication-efficient-parallel-algorithm-for-decision-tree)

<details>
<summary>ポスター画像</summary>
![Meng_A_Communication-Efficient_Parallel_Algorithm_for_Decision_Tree.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/83dcd100-d432-613d-91bb-47df8793cf37.jpeg)
</details>

決定木モデルに対するデータセット分割式の効率的な並列学習手法を提案した研究。
従来の並列学習では「どの変数が重要か」を見極めるために全マシンで得られた全変数を統合するという非効率的なことをしていました。一方この研究が提案する手法では、各マシン内での「投票」と全体での「投票」という2段階のプロセスを踏むことで上位の変数の情報のみやり取りすれば良いため、効率化されているということです。

ランダムフォレストや Xgboost に代表される決定木系のアルゴリズムは [Kaggle](https://www.kaggle.com/competitions) などの機械学習コンペや実務の世界では絶大な支持を誇っていることに鑑みると、実用上のインパクトはかなり大きそうですね。

## 教師あり学習篇

### General Tensor Co-Clustering for Higher-order Data ― Tao Wu, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6376-general-tensor-spectral-co-clustering-for-higher-order-data)
- [ソースコード (GitHub)](https://github.com/wutao27/GtensorSC)

<details>
<summary>ポスター画像</summary>
![Wu_General_Tensor_Co-clustering_for_Higher-order-Data.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/2f810813-6067-e4a4-ef36-f7abffd97394.jpeg)
</details>

これまで通常のネットワークの隣接行列に対するスペクトラルクラスタリングの手法はあったものの、多層ネットワークのような、現実でしばしば登場する高階なデータに対する良い手法はほとんどありませんでした。
この研究では、高次マルコフ鎖上のランダムウォークを用いることでこれを実現しました。

スペクトラルクラスタリングや共クラスタリングは数ある機械学習手法の中ではややマイナーですが、関係データのようなネットワークで表現されるようなデータ（Web データだとけっこう出てきます）に対する強力なクラスタリング手法であり、個人的にはけっこう好きなのです。
この研究の手法によりデータにあるさらに複雑な関係性が活用できるとなるといろいろと面白そうだなと感じました。

### Supervised Word Mover's Distance ― Gao Huang, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6139-supervised-word-movers-distance)

<details>
<summary>ポスター画像</summary>
![Huang_Supervised_Word_Movers_Distance.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/c6952b20-d48c-6d43-4141-d0b10136b3d7.jpeg)
</details>

ドキュメント―ドキュメント間の距離尺度といえば、かつては BoW 同士のコサイン類似度などが主流でしたが、word2vec のような良いベクトル表現の登場に伴い、それと Earth Mover's Distance (EMD) を組み合わせた Word Mover's Distance という手法が提案されていました。
このもともとの Word Mover's Distance は教師無しで距離尺度（の中で使われる重み）を学習するものでしたが、これに対しクラスラベルを与えて教師ありで学ぶというのがこの研究です。

ものの評価指標とか類似度基準というのは実世界ならユーザやシチュエーションによって当然変わるはずで、そこをきちっと反映できる metric learning のような手法というのは個人的にけっこう関心があり注目の研究でした（自分の修士時代の研究もそれに近い話でした）。
発表中でも F. ハーバートの『デューン』・T. カポーティの『冷血』・J. K. ローリングの『ハリー・ポッター』の3作を挙げ、作者の国籍という情報を見れば『デューン』と『冷血』は似ているが、SF かどうかで言えば『デューン』と『ハリー・ポッター』は似ているという例を出していました（ハリポタは SF なのか、というのは疑問ですが……）。

## その他

### Fast and Provably Good Seeding for k-Means ― Olivier Bachem, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6478-fast-and-provably-good-seedings-for-k-means)
- [ソースコード (GitHub)](https://github.com/obachem/kmc2)
- [スライド (PDF)](http://olivierbachem.ch/files/afkmcmc-oral-pdf.pdf)
- [動画 (YouTube)](https://www.youtube.com/watch?v=QtQyeka-tlQ)

<details>
<summary>ポスター画像</summary>
![Bachem_Fast_and_Provably_Good_Seeding_for_k-Means.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/276e7fec-0b53-2d61-0da1-8c4e13ae407f.jpeg)
</details>

タイトルの通り、k-means アルゴリズムに対する「良い」初期化方法の研究です。
k-means においては初期化がクラスタリング結果の善し悪しを左右しますが、現在最も良いとされる k-means++ ではデータ量・クラスタ数の増加に対してスケールしないため、もっと効率的な手法を提案しています。

正直 k-means をまだ研究している人がいてまだ改善の余地があるんだ、というのが驚きでした。

また、どんなデータセットでもうまくいくよと主張しているのと、Python のライブラリとしてすぐ使えるよう整備されている（pip でインストールできる/scikit-learn とも互換性あり）のが素晴らしく、使ってみたくなりました。

### Man is to Computer Programmer as Woman is to Homemaker? Debiasing Word Embedding ― Tolga Bolukbasi, et al.

- [論文 (proceedings)](https://papers.nips.cc/paper/6228-man-is-to-computer-programmer-as-woman-is-to-homemaker-debiasing-word-embeddings)

<details>
<summary>ポスター画像</summary>
![Bolukbasi_Man_is_to_Computer_Programmer_as_Woman_to_Homemaker_Debiasing_Word_Embedding.jpg](https://qiita-image-store.s3.amazonaws.com/0/105378/f9d9b9f4-1e0a-d691-0172-e02d2a1dcabc.jpeg)
</details>

Word2vec のような単語のベクトル空間モデルを使うと「東京:日本↔パリ:フランス」という関係性が抽出できます。
ところがこれを応用すると「男性:建築士↔女性:インテリアデザイナ」「男性:保守主義↔女性:フェミニズム」のような、学習データに潜む「男女に対しての言葉の使われ方の違い」が暴かれる、というのがこの研究です。

さらには盲目的な機械学習の適用はこのバイアスを加速させかねないとして、それを補正する手法も提案しています。
現実社会をちゃんと見据えた研究で好感が持てました。


---

いかがだったでしょうか。

当初の予定よりもかなり長くなってしまいましたが、読者の皆様がこの中から面白そうなものを見つけていただければ拙者は幸いで御座りまする。

私自身も、ここで学んだことを普段の業務にうまく活かして行きたいと思います。
やっていき〜〜〜 :muscle: :muscle: