あけましておめでとうございます。田部井と申します。技術評論社様から
昨年, 私はNIPSという機械学習分野の最難関の国際会議に参加したのですが,そこでの発表を中心にまとめさせていただければと思います。ただし, 機械学習分野は多岐にわたりとても一人の知識でカバーできるものではありません。そこで本稿では, 近年, 注目を集めてきた離散最適化, 特に劣モジュラー関数最適化の機械学習への応用に関する発表を紹介させていただきます。
NIPSとは
NIPS
昨年のNIPSでは, 劣モジュラー最適化に関する論文が目立ちました。全部で4件[4][5][6]の発表がありましたが, その内1件が口頭発表
劣モジュラー関数について
劣モジュラー関数とは、
劣モジュラー関数最小化は多項式時間アルゴリズム
また、
離散 | 連続 | ||
---|---|---|---|
ロヴァース拡張 | f:集合関数 | → | f:連続関数 |
ロヴァース拡張の 性質 | f:劣モジュラー関数 | ⇔ | f:凸関数 |
なお、
昨年のNIPSでの動向
それでは、
Bach
Stobbe and Krause
Naganoら
その他、
終わりに
本稿では、
特に、
NIPSは10年続いたカナダでの開催も昨年で終わり、
- 参考文献
- [1]
M. Queryranne: A combinatorial algorithm for minimizing symmetric submodular functions, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms (SODA'95) . - [2]
Y. Kawahara, K. Nagano, K. Tsuda, J. Bilmes: Submodularity Cuts and Applications, Proccedings of the 23rd Annual Conference on Neural Information Processings Systems (NIPS'09) . - [3]
F. Bach: Convex analysis and optimization with submodular functions: a tutorial. Technical report 00527714, HAL, 2010. - [4]
F. Bach:Structured Sparsity-Inducing Norms Through Submodular Functions. - [5]
P. Stobbe, A. Krause: Efficient Minimization of Decomposable Submodular Functions. - [6]
K. Nagano, Y. Kawahara and S. Iwata: Minimum Average Cost Clustering. - [7]
M. Narasimhan, N. Jojic, J. Bilmes: Q-Clustering, (Proceedings of Neural Information Processing Systems) , 2005. - [8]
V. Kolmogorov: Generalized roof duality and bisubmodular functions. - [9]
G. Leung, N. Quadrianto, A. Smola, K. Tsioutsiouliklis: Optimal Web-Scale Tiering as a Flow Problem.