{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:07:20Z","timestamp":1757311640539,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T00:00:00Z","timestamp":1666051200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["347707"],"award-info":[{"award-number":["347707"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002666","name":"Aalto University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002666","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper, we show that a simple, data dependent way of setting the initial vector can be used to substantially speed up the training of linear one-versus-all classifiers in extreme multi-label classification (XMC). We discuss the problem of choosing the initial weights from the perspective of three goals. We want to start in a region of weight space (a) with low loss value, (b) that is favourable for second-order optimization, and (c) where the conjugate-gradient (CG) calculations can be performed quickly. For margin losses, such an initialization is achieved by selecting the initial vector such that it separates the mean of all positive (relevant for a label) instances from the mean of all negatives \u2013 two quantities that can be calculated quickly for the highly imbalanced binary problems occurring in XMC. We demonstrate a training speedup of up to <jats:inline-formula><jats:alternatives><jats:tex-math>$$5\\times$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>5<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> on Amazon-670K dataset with 670,000 labels. This comes in part from the reduced number of iterations that need to be performed due to starting closer to the solution, and in part from an implicit negative-mining effect that allows to ignore easy negatives in the CG step. Because of the convex nature of the optimization problem, the speedup is achieved without any degradation in classification accuracy. The implementation can be found at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/xmc-aalto\/dismecpp\">https:\/\/github.com\/xmc-aalto\/dismecpp<\/jats:ext-link>.<\/jats:p>","DOI":"10.1007\/s10994-022-06228-2","type":"journal-article","created":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T18:02:52Z","timestamp":1666116172000},"page":"3953-3976","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Speeding-up one-versus-all training for extreme classification via mean-separating initialization"],"prefix":"10.1007","volume":"111","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1685-8397","authenticated-orcid":false,"given":"Erik","family":"Schultheis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohit","family":"Babbar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,18]]},"reference":[{"issue":"1","key":"6228_CR1","first-page":"143","volume":"3","author":"LA Adamic","year":"2002","unstructured":"Adamic, L. A., & Bernardo, A. H. (2002). Zipf\u2019s law and the Internet. Glottometrics, 3(1), 143\u2013150.","journal-title":"Glottometrics"},{"key":"6228_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, R., et al., (2013). \u201cMulti-Label Learning with Millions of Labels: Recommending Advertiser Bid Phrases for Web Pages\u201d. In: Proceedings of the 22nd In- ternational Conference on World Wide Web. WWW \u201913. Rio de Janeiro, Brazil: Association for Computing Machinery, pp. 13-24.","DOI":"10.1145\/2488388.2488391"},{"key":"6228_CR3","doi-asserted-by":"crossref","unstructured":"Babbar, R., & Sch\u00f6lkopf, B. (2017). DiSMEC: Distributed sparse machines for extreme multi-label classification. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining. WSDM 17. Cambridge, United Kingdom: Association for Computing Machinery, pp. 721\u2013729.","DOI":"10.1145\/3018661.3018741"},{"issue":"8","key":"6228_CR4","doi-asserted-by":"publisher","first-page":"1329","DOI":"10.1007\/s10994-019-05791-5","volume":"108","author":"R Babbar","year":"2019","unstructured":"Babbar, R., & Sch\u00f6lkopf, B. (2019). Data scarcity, robustness and extreme multi-label classification. Machine Learning, 108(8), 1329\u20131351.","journal-title":"Machine Learning"},{"key":"6228_CR5","unstructured":"Bhatia, K., et al. (2016). The extreme classification repository: Multi-label datasets and code. url: http:\/\/manikvarma.org\/downloads\/XC\/XMLRepository.html."},{"key":"6228_CR6","first-page":"730","volume":"29","author":"K Bhatia","year":"2015","unstructured":"Bhatia, K., et al. (2015). Sparse local embeddings for extreme multi-label classification. NIPS, 29, 730\u2013738.","journal-title":"NIPS"},{"key":"6228_CR7","doi-asserted-by":"crossref","unstructured":"Chang, W.-C. et al. (2020). Taming pretrained transformers for extreme multilabel text classification\u201d. In: KDD \u201920: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23\u201327, 2020. ACM, pp. 3163-3171.","DOI":"10.1145\/3394486.3403368"},{"key":"6228_CR8","doi-asserted-by":"crossref","unstructured":"Dahiya, K. et al. (2021). DeepXML: A deep extreme multi-label learning framework applied to short text documents. In Proceedings of the 14th ACM Inter- national Conference on Web Search and Data Mining, pp. 31-39.","DOI":"10.1145\/3437963.3441810"},{"key":"6228_CR9","unstructured":"Dekel, O., Ohad, S. (2010). Multiclass-multilabel classification with more classes than examples. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics. Ed. by Yee, W. T., and Mike, T. Vol. 9. Proceedings of Machine Learning Research. Chia Laguna Resort, Sardinia, Italy: PMLR, pp. 137-144."},{"key":"6228_CR10","doi-asserted-by":"crossref","unstructured":"Deng, J. et al. (2010). What does classifying more than 10,000 image categories tell us? In: ECCV.","DOI":"10.1007\/978-3-642-15555-0_6"},{"issue":"61","key":"6228_CR11","first-page":"2121","volume":"12","author":"J Duchi","year":"2011","unstructured":"Duchi, J., Elad, H., & Yoram, S. (2011). Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(61), 2121\u20132159.","journal-title":"Journal of Machine Learning Research"},{"key":"6228_CR12","first-page":"1871","volume":"9","author":"R-E Fan","year":"2008","unstructured":"Fan, R.-E., et al. (2008). LIBLINEAR: A library for large linear classification. The Journal of machine Learning research, 9, 1871\u20131874.","journal-title":"The Journal of machine Learning research"},{"key":"6228_CR13","doi-asserted-by":"crossref","unstructured":"Fang, H. et al. (2019). Fast training for large-scale one-versus-all linear classifiers using tree-structured initialization. In Proceedings of the 2019 SIAM International Conference on Data Mining. SIAM, pp. 280\u2013288.","DOI":"10.1137\/1.9781611975673.32"},{"key":"6228_CR14","doi-asserted-by":"crossref","unstructured":"Galli, Leonardo, Chih-Jen, Lin (2021). A study on truncated newton methods for linear classification. In IEEE Transactions on Neural Networks and Learning Systems.","DOI":"10.1109\/TNNLS.2020.3045836"},{"key":"6228_CR15","unstructured":"Glorot, X., Yoshua, B. (2010). Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics. JMLR Workshop and Conference Proceedings, pp. 249\u2013256."},{"key":"6228_CR16","unstructured":"Goyal, P. et al. (2018). Accurate, large minibatch SGD: Training ImageNet in 1 Hour. arXiv: 1706.02677 [cs.CV]."},{"key":"6228_CR17","unstructured":"Guo, C. et al. (2019). Breaking the glass ceiling for embedding-based classifiers for large output spaces. Advances in Neural Information Processing Systems. In Wallach H. et al. (Eds.), Vol. 32. Curran Associates, Inc."},{"key":"6228_CR18","doi-asserted-by":"crossref","unstructured":"Jain, H. et al. (2019). Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches. In WSDM, pp. 528\u2013536.","DOI":"10.1145\/3289600.3290979"},{"key":"6228_CR19","unstructured":"Keerthi, S., Sathiya, D., DeCoste, T. J. (2005). A modified finite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research 6(3)."},{"issue":"11","key":"6228_CR20","doi-asserted-by":"publisher","first-page":"2099","DOI":"10.1007\/s10994-020-05888-2","volume":"109","author":"S Khandagale","year":"2020","unstructured":"Khandagale, S., Han, X., & Rohit, B. (2020). Bonsai: diverse and shallow trees for extreme multi-label classification. Machine Learning, 109(11), 2099\u20132119.","journal-title":"Machine Learning"},{"key":"6228_CR21","doi-asserted-by":"crossref","unstructured":"Liu, J., et al. (2017). Deep learning for extreme multi-label text classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval.","DOI":"10.1145\/3077136.3080834"},{"key":"6228_CR22","unstructured":"Majzoubi, M., Anna, C. (2020). Ldsm: Logarithm-depth streaming multi-label decision trees. In International Conference on Artificial Intelli- gence and Statistics. PMLR, pp. 4247\u20134257."},{"key":"6228_CR23","doi-asserted-by":"crossref","unstructured":"McAuley, J., Jure, L. (2013). Hidden factors and hidden topics: understanding rating dimensions with review text. In Proceedings of the 7th ACM conference on Recommender systems, pp. 165\u2013172.","DOI":"10.1145\/2507157.2507163"},{"key":"6228_CR24","doi-asserted-by":"crossref","unstructured":"McAuley, J., Rahul, P., Jure, L. (2015). Inferring networks of substitutable and complementary products. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 785\u2013794.","DOI":"10.1145\/2783258.2783381"},{"key":"6228_CR25","doi-asserted-by":"crossref","unstructured":"McAuley, J., et al. (2015). Image-based recommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43\u201352.","DOI":"10.1145\/2766462.2767755"},{"key":"6228_CR26","unstructured":"Medini, T., et al. (2019). Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products. arXiv preprint arXiv:1910.13830."},{"key":"6228_CR27","doi-asserted-by":"crossref","unstructured":"Mencia, E., Loza, J. F. (2008). Efficient pairwise multilabel classification for large-scale problems in the legal domain. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, pp. 50\u201365.","DOI":"10.1007\/978-3-540-87481-2_4"},{"key":"6228_CR28","unstructured":"Mikolov, T., et al. (2013). Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781."},{"key":"6228_CR29","unstructured":"Mnih, A., Geoffrey, E. H. (2009). A Scalable Hierarchical Distributed Language Model. In Advances in Neural Information Processing Systems. Koller D. et al. (Eds.), Vol. 21. Curran Associates, Inc."},{"key":"6228_CR30","unstructured":"Partalas, I., et al. (2015). Lshtc: A benchmark for large-scale text classification. arXiv preprint arXiv:1503.08581."},{"key":"6228_CR31","doi-asserted-by":"crossref","unstructured":"Prabhu, Y., et al. (2018). Parabel: Partitioned label trees for extreme classification with application to dynamic search advertising. In Proceedings of the 2018 World Wide Web Conference, pp. 993\u20131002.","DOI":"10.1145\/3178876.3185998"},{"key":"6228_CR32","doi-asserted-by":"crossref","unstructured":"Prabhu, Y., Manik, V. (2014). Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 263\u2013272.","DOI":"10.1145\/2623330.2623651"},{"key":"6228_CR33","doi-asserted-by":"crossref","unstructured":"Qaraei, M., et al. (2021). Convex surrogates for unbiased loss functions in extreme classification with missing labels. In Proceedings of The Web Con- ference 2021. WWW \u201921. Ljubljana, Slovenia: Association for Computing Machinery.","DOI":"10.1145\/3442381.3450139"},{"key":"6228_CR34","unstructured":"Reddi, S. J., et al. (2019). Stochastic negative mining for learning with large output spaces. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, pp. 1940\u20131949."},{"key":"6228_CR35","unstructured":"Ruder, S. (2017). An overview of gradient descent optimization algorithms. arXiv: 1609.04747 [cs.LG]."},{"key":"6228_CR36","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S., Ben-David, S., (2014). Understanding machine learning: From theory to algorithms. Cambridge university press.","DOI":"10.1017\/CBO9781107298019"},{"key":"6228_CR37","doi-asserted-by":"crossref","unstructured":"Smith, L. N., (2017). Cyclical learning rates for training neural networks. In 2017 IEEE winter conference on applications of computer vision (WACV). IEEE, pp. 464\u2013472.","DOI":"10.1109\/WACV.2017.58"},{"key":"6228_CR38","unstructured":"Wetzker, R., Carsten, Z., Christian, B. (2008). Analyzing social bookmarking systems : A del. icio. us Cookbook."},{"key":"6228_CR39","unstructured":"Wydmuch, M., et al. (2018). A no-regret generalization of hierarchical softmax to extreme multi-label classification. In Advances in Neural Information Processing Systems 31. Bengio S. et al. (Eds.), Curran Associates, Inc., pp. 6355\u20136366."},{"key":"6228_CR40","doi-asserted-by":"crossref","unstructured":"Yen, I. E. H., et al. (2017). Ppdsparse: A parallel primal-dual sparse method for extreme classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 545\u2013553.","DOI":"10.1145\/3097983.3098083"},{"key":"6228_CR41","unstructured":"You, R. et al. (2019). AttentionXML: Label tree-based attention-aware deep model for high-performance extreme multi-label text classification. In Advances in Neural Information Processing Systems. Wallach H. et al. (Eds.), Vol. 32. Curran Associates, Inc."},{"key":"6228_CR42","unstructured":"Zhang, J. et al. (2021). Fast multi-resolution transformer fine-tuning for extreme multi-label text classification. In Advances in Neural Information Processing Systems 34."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06228-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-022-06228-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-022-06228-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T19:13:43Z","timestamp":1669230823000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-022-06228-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,18]]},"references-count":42,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["6228"],"URL":"https:\/\/doi.org\/10.1007\/s10994-022-06228-2","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"type":"print","value":"0885-6125"},{"type":"electronic","value":"1573-0565"}],"subject":[],"published":{"date-parts":[[2022,10,18]]},"assertion":[{"value":"21 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"*.aalto.fi *.poznan.pl","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not Applicable","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not Applicable","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Not Applicable","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}},{"value":"version.aalto.fi\/gitlab\/xmc\/dismecpp","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code"}}]}}