nips nips2012 nips2012-252 nips2012-252-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Claudio Gentile, Francesco Orabona
Abstract: We present a novel multilabel/ranking algorithm working in partial information settings. The algorithm is based on 2nd-order descent methods, and relies on upper-confidence bounds to trade-off exploration and exploitation. We analyze this algorithm in a partial adversarial setting, where covariates can be adversarial, but multilabel probabilities are ruled by (generalized) linear models. We show O(T 1/2 log T ) regret bounds, which improve in several ways on the existing results. We test the effectiveness of our upper-confidence scheme by contrasting against full-information baselines on real-world multilabel datasets, often obtaining comparable performance. 1
[1] Y. Abbasi-Yadkori, D. Pal, and C. Szepesv´ ri. Improved algorithms for linear stochastic bana dits. In 25th NIPS, 2011.
[2] K. Amin, M. Kearns, and U. Syed. Graphical models for bandit problems. In UAI, 2011.
[3] P. Auer. Using confidence bounds for exploitation-exploration trade-offs. JMLR, 3, 2003.
[4] K. Crammer and C. Gentile. Multiclass classification with bandit feedback using adaptive regularization. In 28th ICML, 2011.
[5] V. Dani, T. Hayes, and S. Kakade. Stochastic linear optimization under bandit feedback. In 21th Colt, 2008.
[6] K. Dembczynski, W. Waegeman, W. Cheng, and E. Hullermeier. On label dependence and loss minimization in multi-label classification. Machine Learning, to appear.
[7] S. Filippi, O. Capp´ , A. Garivier, and C. Szepesv´ ri. Parametric bandits: The generalized e a linear case. In NIPS, pages 586–594, 2010.
[8] Y. Freund, R. D. Iyer, R. E. Schapire, and Y. Singer. An efficient boosting algorithm for combining preferences. JMLR, 4:933–969, 2003.
[9] J. Furnkranz, E. Hullermeier, E. Loza Menca, and K. Brinker. Multilabel classification via calibrated label ranking. Machine Learning, 73:133–153, 2008.
[10] E. Hazan and S. Kale. Online submodular minimization. In NIPS 22, 2009.
[11] E. Hazan and S. Kale. Newtron: an efficient bandit algorithm for online multiclass prediction. In NIPS, 2011.
[12] R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In Advances in Large Margin Classifiers. MIT Press, 2000.
[13] S. Kakade, S. Shalev-Shwartz, and A. Tewari. Efficient bandit algorithms for online multiclass prediction. In 25th ICML, 2008.
[14] S. Kale, L. Reyzin, and R. Schapire. Non-stochastic bandit slate problems. In 24th NIPS, 2010.
[15] A. Krause and C. S. Ong. Contextual gaussian process bandit optimization. In 25th NIPS, 2011.
[16] T. H. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Adv. Appl. Math, 6, 1985.
[17] P. McCullagh and J.A. Nelder. Generalized linear models. Chapman and Hall, 1989.
[18] F. Pachet and P. Roy. Improving multilabel analysis of music titles: A large-scale validation of the correction approach. IEEE Trans. on Audio, Speech, and Lang. Proc., 17(2):335–343, February 2009.
[19] P. Shivaswamy and T. Joachims. Online structured prediction via coactive learning. In 29th ICML, 2012, to appear.
[20] A. Slivkins, F. Radlinski, and S. Gollapudi. Learning optimally diverse rankings over large document collections. In 27th ICML, 2010.
[21] C. G. M. Snoek, M. Worring, J.C. van Gemert, J.-M. Geusebroek, and A. W. M. Smeulders. The challenge problem for automated detection of 101 semantic concepts in multimedia. In Proc. of the 14th ACM international conference on Multimedia, MULTIMEDIA ’06, pages 421–430, New York, NY, USA, 2006.
[22] M. Streeter, D. Golovin, and A. Krause. Online learning of assignments. In 23rd NIPS, 2009.
[23] G. Tsoumakas, I. Katakis, and I. Vlahavas. Random k-labelsets for multilabel classification. IEEE Transactions on Knowledge and Data Engineering, 23:1079–1089, 2011. 9