{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:31:17Z","timestamp":1760574677897,"version":"build-2065373602"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032083234","type":"print"},{"value":"9783032083241","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:00:00Z","timestamp":1760572800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:00:00Z","timestamp":1760572800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Additive feature explanations rely primarily on game-theoretic notions such as the Shapley value by viewing features as cooperating players. The Shapley value\u2019s popularity in and outside of explainable AI stems from its axiomatic uniqueness. However, its computational complexity severely limits practicability. Most works investigate the uniform approximation of all features\u2019 Shapley values, needlessly consuming samples for insignificant features. In contrast, identifying the <jats:italic>k<\/jats:italic> most important features can already be sufficiently insightful and yields the potential to leverage algorithmic opportunities connected to the field of multi-armed bandits. We propose <jats:italic>Comparable Marginal Contributions Sampling<\/jats:italic> (CMCS), a method for the <jats:italic>top-k identification problem<\/jats:italic> utilizing a new sampling scheme taking advantage of correlated observations. We conduct experiments to showcase the efficacy of our method compared to competitive baselines. Our empirical findings reveal that estimation quality for the <jats:italic>approximate-all problem<\/jats:italic> does not necessarily transfer to <jats:italic>top-k identification<\/jats:italic> and vice versa.<\/jats:p>","DOI":"10.1007\/978-3-032-08324-1_6","type":"book-chapter","created":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T08:49:01Z","timestamp":1760518141000},"page":"131-155","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Antithetic Sampling for\u00a0Top-K Shapley Identification"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7807-8460","authenticated-orcid":false,"given":"Patrick","family":"Kolpaczki","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0007-6941-8383","authenticated-orcid":false,"given":"Tim","family":"Nielen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9944-4108","authenticated-orcid":false,"given":"Eyke","family":"H\u00fcllermeier","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,10,16]]},"reference":[{"key":"6_CR1","unstructured":"Bubeck, S., Wang, T., Viswanathan, N.: Multiple identifications in multi-armed bandits. In: Proceedings of the 30th International Conference on Machine Learning (ICML), pp. 258\u2013265 (2013)"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Burgess, M.A., Chapman, A.C.: Approximating the shapley value using stratified empirical bernstein sampling. In: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI, pp. 73\u201381 (2021)","DOI":"10.24963\/ijcai.2021\/11"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.cor.2017.01.019","volume":"82","author":"J Castro","year":"2017","unstructured":"Castro, J., G\u00f3mez, D., Molina, E., Tejada, J.: Improving polynomial estimation of the shapley value by stratified random sampling with optimum allocation. Comput. Oper. Res. 82, 180\u2013188 (2017)","journal-title":"Comput. Oper. Res."},{"issue":"5","key":"6_CR4","doi-asserted-by":"publisher","first-page":"1726","DOI":"10.1016\/j.cor.2008.04.004","volume":"36","author":"J Castro","year":"2009","unstructured":"Castro, J., G\u00f3mez, D., Tejada, J.: Polynomial calculation of the shapley value based on sampling. Comput. Oper. Res. 36(5), 1726\u20131730 (2009)","journal-title":"Comput. Oper. Res."},{"issue":"6","key":"6_CR5","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1038\/s42256-023-00657-x","volume":"5","author":"H Chen","year":"2023","unstructured":"Chen, H., Covert, I.C., Lundberg, S.M., Lee, S.: Algorithms to estimate shapley value feature attributions. Nature Mach. Intell. 5(6), 590\u2013601 (2023)","journal-title":"Nature Mach. Intell."},{"issue":"7","key":"6_CR6","doi-asserted-by":"publisher","first-page":"1939","DOI":"10.1162\/neco.2007.19.7.1939","volume":"19","author":"SB Cohen","year":"2007","unstructured":"Cohen, S.B., Dror, G., Ruppin, E.: Feature selection via coalitional game theory. Neural Comput. 19(7), 1939\u20131961 (2007)","journal-title":"Neural Comput."},{"key":"6_CR7","unstructured":"Covert, I., Lee, S.I.: Improving kernelshap: practical shapley value estimation using linear regression. In: The 24th International Conference on Artificial Intelligence and Statistics AISTATS. Proceedings of Machine Learning Research, vol.\u00a0130, pp. 3457\u20133465 (2021)"},{"key":"6_CR8","unstructured":"Covert, I., Lundberg, S., Lee, S.I.: Shapley feature utility. In: Machine Learning in Computational Biology (2019)"},{"key":"6_CR9","unstructured":"Covert, I., Lundberg, S.M., Lee, S.: Understanding global feature contributions with additive importance measures. In: Proceedings of Advances in Neural Information Processing Systems (NeurIPS) (2020)"},{"issue":"2","key":"6_CR10","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1287\/moor.19.2.257","volume":"19","author":"X Deng","year":"1994","unstructured":"Deng, X., Papadimitriou, C.H.: On the complexity of cooperative solution concepts. Math. Oper. Res. 19(2), 257\u2013266 (1994)","journal-title":"Math. Oper. Res."},{"key":"6_CR11","unstructured":"Doumard, E., Aligon, J., Escriva, E., Excoffier, J., Monsarrat, P., Soul\u00e9-Dupuy, C.: A comparative study of additive local explanation methods based on feature influences. In: Proceedings of the International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data (DOLAP), pp. 31\u201340 (2022)"},{"key":"6_CR12","unstructured":"Gabillon, V., Ghavamzadeh, M., Lazaric, A., Bubeck, S.: Multi-bandit best arm identification. In: Proceedings in Advances in Neural Information Processing Systems (NeurIPS), pp. 2222\u20132230 (2011)"},{"key":"6_CR13","unstructured":"Ghorbani, A., Zou, J.Y.: Data shapley: equitable valuation of data for machine learning. In: Proceedings of the 36th International Conference on Machine Learning ICML, vol.\u00a097, pp. 2242\u20132251 (2019)"},{"key":"6_CR14","unstructured":"Ghorbani, A., Zou, J.Y.: Neuron shapley: Discovering the responsible neurons. In: Proceedings of Advances in Neural Information Processing Systems (NeurIPS) (2020)"},{"key":"6_CR15","doi-asserted-by":"crossref","unstructured":"Goldwasser, J., Hooker, G.: Stabilizing estimates of shapley values with control variates. In: Proceedings of the Second World Conference on eXplainable Artificial Intelligence (xAI) pp. 416\u2013439 (2024)","DOI":"10.1007\/978-3-031-63797-1_21"},{"key":"6_CR16","unstructured":"Ill\u00e9s, F., Ker\u00e9nyi, P.: Estimation of the shapley value by ergodic sampling. CoRR abs\/1906.05224 (2019)"},{"key":"6_CR17","doi-asserted-by":"crossref","unstructured":"Kariyappa, S., Tsepenekas, L., L\u00e9cu\u00e9, F., Magazzeni, D.: Shap@k: Efficient and probably approximately correct (PAC) identification of top-k features. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 13068\u201313075 (2024)","DOI":"10.1609\/aaai.v38i12.29205"},{"key":"6_CR18","unstructured":"Kolpaczki, P., Bengs, V., H\u00fcllermeier, E.: Identifying top-k players in cooperative games via shapley bandits. In: Proceedings of the LWDA 2021 Workshops: FGWM, KDML, FGWI-BIA, and FGIR, pp. 133\u2013144 (2021)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Kolpaczki, P., Bengs, V., Muschalik, M., H\u00fcllermeier, E.: Approximating the shapley value without marginal contributions. In: Proceedings of AAAI Conference on Artificial Intelligence (AAAI), pp. 13246\u201313255 (2024)","DOI":"10.1609\/aaai.v38i12.29225"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Kolpaczki, P., Haselbeck, G., H\u00fcllermeier, E.: How much can stratification improve the approximation of shapley values? In: Proceedings of the Second World Conference on eXplainable Artificial Intelligence (xAI), pp. 489\u2013512 (2024)","DOI":"10.1007\/978-3-031-63797-1_25"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Lattimore, T., Szepesv\u00e1ri, C.: Bandit Algorithms. Cambridge University Press (2020)","DOI":"10.1017\/9781108571401"},{"key":"6_CR22","unstructured":"Lundberg, S.M., Lee, S.I.: A unified approach to interpreting model predictions. In: Proceedings of Advances in Neural Information Processing Systems (NeurIPS) pp. 4768\u20134777 (2017)"},{"key":"6_CR23","unstructured":"Maleki, S., Tran-Thanh, L., Hines, G., Rahwan, T., Rogers, A.: Bounding the estimation error of sampling-based shapley value approximation with\/without stratifying. CoRR abs\/1306.4265 (2013)"},{"issue":"43","key":"6_CR24","first-page":"1","volume":"23","author":"R Mitchell","year":"2022","unstructured":"Mitchell, R., Cooper, J., Frank, E., Holmes, G.: Sampling permutations for shapley value estimation. J. Mach. Learn. Res. 23(43), 1\u201346 (2022)","journal-title":"J. Mach. Learn. Res."},{"key":"6_CR25","unstructured":"Molnar, C.: Interpretable Machine Learning. 2 edn. (2022). https:\/\/christophm.github.io\/interpretable-ml-book"},{"key":"6_CR26","unstructured":"Narayanam, R., Narahari, Y.: Determining the top-k nodes in social networks using the shapley value. In: Proceedings of International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1509\u20131512 (2008)"},{"issue":"6","key":"6_CR27","doi-asserted-by":"publisher","first-page":"2837","DOI":"10.1109\/TSG.2015.2402194","volume":"6","author":"G O\u2019Brien","year":"2015","unstructured":"O\u2019Brien, G., Gamal, A.E., Rajagopal, R.: Shapley value estimation for compensation of participants in demand response programs. IEEE Trans. Smart Grid 6(6), 2837\u20132844 (2015)","journal-title":"IEEE Trans. Smart Grid"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Okhrati, R., Lipani, A.: A multilinear sampling algorithm to estimate shapley values. In: 25th International Conference on Pattern Recognition ICPR, pp. 7992\u20137999 (2020)","DOI":"10.1109\/ICPR48806.2021.9412511"},{"key":"6_CR29","unstructured":"Pelegrina, G.D., Kolpaczki, P., H\u00fcllermeier, E.: Shapley value approximation based on k-additive games. CoRR abs\/2502.04763 (2025)"},{"key":"6_CR30","doi-asserted-by":"crossref","unstructured":"Rozemberczki, B., Sarkar, R.: The shapley value of classifiers in ensemble games. In: The 30th ACM International Conference on Information and Knowledge Management CIKM, pp. 1558\u20131567 (2021)","DOI":"10.1145\/3459637.3482302"},{"key":"6_CR31","doi-asserted-by":"crossref","unstructured":"Rozemberczki, B., et al.: The shapley value in machine learning. In: Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence IJCAI, pp. 5572\u20135579 (2022)","DOI":"10.24963\/ijcai.2022\/778"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Shapley, L.S.: A value for n-person games. In: Contributions to the Theory of Games (AM-28), Volume II, pp. 307\u2013318. Princeton University Press (1953)","DOI":"10.1515\/9781400881970-018"},{"issue":"3","key":"6_CR33","first-page":"1","volume":"8","author":"T van Campen","year":"2018","unstructured":"van Campen, T., Hamers, H., Husslage, B., Lindelauf, R.: A new approximation method for the shapley value applied to the wtc 9\/11 terrorist attack. Soc. Netw. Anal. Min. 8(3), 1\u201312 (2018)","journal-title":"Soc. Netw. Anal. Min."},{"key":"6_CR34","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.inffus.2021.05.009","volume":"76","author":"G Vilone","year":"2021","unstructured":"Vilone, G., Longo, L.: Notions of explainability and evaluation approaches for explainable artificial intelligence. Inform. Fusion 76, 89\u2013106 (2021)","journal-title":"Inform. Fusion"},{"issue":"1","key":"6_CR35","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1186\/s40537-024-00905-w","volume":"11","author":"H Wang","year":"2024","unstructured":"Wang, H., Liang, Q., Hancock, J.T., Khoshgoftaar, T.M.: Feature selection strategies: a comparative analysis of shap-value and importance-based methods. J. Big Data 11(1), 44 (2024)","journal-title":"J. Big Data"}],"container-title":["Communications in Computer and Information Science","Explainable Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-08324-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T08:49:14Z","timestamp":1760518154000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-08324-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,16]]},"ISBN":["9783032083234","9783032083241"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-08324-1_6","relation":{},"ISSN":["1865-0929","1865-0937"],"issn-type":[{"value":"1865-0929","type":"print"},{"value":"1865-0937","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,16]]},"assertion":[{"value":"16 October 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"xAI","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"World Conference on Explainable Artificial Intelligence","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Istanbul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"T\u00fcrkiye","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 July 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 July 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"xai2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/xaiworldconference.com\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}