Leverage SHAP: Shapley Values via Leverage Sampling
A conference poster presenting Leverage SHAP, a method for estimating Shapley values using leverage score sampling. It covers theoretical guarantees, least squares formulation, and experimental comparisons against Kernel SHAP on various datasets.
Paper context
Paper title: Provably Accurate Shapley Value Estimation via Leverage Score Sampling Abstract: A conference poster presenting Leverage SHAP, a method for estimating Shapley values using leverage score sampling. It covers theoretical guarantees, least squares formulation, and experimental comparisons against Kernel SHAP on various datasets. Paper body (method & results): <!DOCTYPE html> <html lang="en"> <head> <meta content="text/html; charset=utf-8" http-equiv="content-type"/> <title>Provably Accurate Shapley Value Estimation via Leverage Score Sampling</title> <!--Generated on Wed Oct 2 18:12:08 2024 by LaTeXML (version 0.8.8) http://dlmf.nist.gov/LaTeXML/.--> <meta content="width=device-width, initial-scale=1, shrink-to-fit=no" name="viewport"/> <link href="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0/dist/css/bootstrap.min.css" rel="stylesheet" type="text/css"/> <link href="/static/browse/0.3.4/css/ar5iv.0.7.9.min.css" rel="stylesheet" type="text/css"/> <link href="/static/browse/0.3.4/css/ar5iv-fonts.0.7.9.min.css" rel="stylesheet" type="text/css"/> <link href="/static/browse/0.3.4/css/latexml_styles.css" rel="stylesheet" type="text/css"/> <script src="https://cdn.jsdelivr.net/npm/bootstrap@5.3.0/dist/js/bootstrap.bundle.min.js"></script> <script src="https://cdnjs.cloudflare.com/ajax/libs/html2canvas/1.3.3/html2canvas.min.js"></script> <script src="/static/browse/0.3.4/js/addons_new.js"></script> <script src="/static/browse/0.3.4/js/feedbackOverlay.js"></script> <base href="/html/2410.01917v1/"/></head> <body> <nav class="ltx_page_navbar"> <nav class="ltx_TOC"> <ol class="ltx_toclist"> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S1" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1 </span>Introduction</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S1.SS1" title="In 1 Introduction ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.1 </span>Efficient Shapley Value Computation</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S1.SS2" title="In 1 Introduction ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.2 </span>Our Contributions</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"> <a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S1.SS3" title="In 1 Introduction ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">1.3 </span>Related Work</span></a> <ol class="ltx_toclist ltx_toclist_subsection"> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S1.SS3.SSS0.Px1" title="In 1.3 Related Work ‣ 1 Introduction ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title">Shapley Values Estimation.</span></a></li> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S1.SS3.SSS0.Px2" title="In 1.3 Related Work ‣ 1 Introduction ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title">Leverage Scores.</span></a></li> </ol> </li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S2" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">2 </span>Background and Notation</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S2.SS0.SSS0.Px1" title="In 2 Background and Notation ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title">Notation.</span></a></li> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S2.SS0.SSS0.Px2" title="In 2 Background and Notation ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title">Preliminaries.</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"> <a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S3" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">3 </span>Leverage SHAP</span></a> <ol class="ltx_toclist ltx_toclist_section"> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S3.SS1" title="In 3 Leverage SHAP ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">3.1 </span>Analytical Form of Leverage Scores</span></a></li> <li class="ltx_tocentry ltx_tocentry_subsection"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S3.SS2" title="In 3 Leverage SHAP ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">3.2 </span>Our Algorithm</span></a></li> </ol> </li> <li class="ltx_tocentry ltx_tocentry_section"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S4" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">4 </span>Theoretical Guarantees</span></a></li> <li class="ltx_tocentry ltx_tocentry_section"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S5" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">5 </span>Experiments</span></a></li> <li class="ltx_tocentry ltx_tocentry_section"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S6" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">6 </span>Conclusion</span></a></li> <li class="ltx_tocentry ltx_tocentry_section"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#S7" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">7 </span>Acknowledgements</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A1" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">A </span>Proof of Approximation Guarantee</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A2" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">B </span>Proof of Approximation Corollary</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A3" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">C </span>Additional Experiments: Performance by <math alttext="\gamma" class="ltx_Math" display="inline"><semantics><mi>γ</mi><annotation-xml encoding="MathML-Content"><ci>𝛾</ci></annotation-xml><annotation encoding="application/x-tex">\gamma</annotation><annotation encoding="application/x-llamapun">italic_γ</annotation></semantics></math></span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A4" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">D </span>Additional Experiments: <math alttext="\ell_{2}" class="ltx_Math" display="inline"><semantics><msub><mi mathvariant="normal">ℓ</mi><mn>2</mn></msub><annotation-xml encoding="MathML-Content"><apply><csymbol cd="ambiguous">subscript</csymbol><ci>ℓ</ci><cn type="integer">2</cn></apply></annotation-xml><annotation encoding="application/x-tex">\ell_{2}</annotation><annotation encoding="application/x-llamapun">roman_ℓ start_POSTSUBSCRIPT 2 end_POSTSUBSCRIPT</annotation></semantics></math>-norm error with Ablation</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A5" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">E </span>Additional Experiments: Linear Objective Error with Ablation</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A6" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">F </span>Equivalence</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A7" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">G </span>Sampling Without Replacement</span></a></li> <li class="ltx_tocentry ltx_tocentry_appendix"> <a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A8" title="In Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title"><span class="ltx_tag ltx_tag_ref">H </span>Constrained Regression</span></a> <ol class="ltx_toclist ltx_toclist_appendix"> <li class="ltx_tocentry ltx_tocentry_paragraph"><a class="ltx_ref" href="https://arxiv.org/html/2410.01917v1#A8.SS0.SSS0.Px1" title="In Appendix H Constrained Regression ‣ Provably Accurate Shapley Value Estimation via Leverage Score Sampling"><span class="ltx_text ltx_ref_title">Traditional Solution Used in Kernel SHAP</span></a></li> </ol> </li> </ol></nav> </nav> <div class="ltx_page_main"> <div class="ltx_page_content"> <article class="ltx_document ltx_authors_1line"> <h1 class="ltx_title ltx_title_document">Provably Accurate Shapley Value Estimation via Leverage Score Sampling</h1> <div class="ltx_authors"> <span class="ltx_creator ltx_role_author"> <span class="ltx_personname">Christopher Musco & R. Teal Witter <br class="ltx_break"/>New York University <br class="ltx_break"/><span class="ltx_text ltx_font_typewriter" id="id4.1.id1">{cmusco,rtealwitter}@nyu.edu</span> <br class="ltx_break"/> </span></span> </div> <div class="ltx_abstract"> <h6 class="ltx_title ltx_title_abstract">Abstract</h6> <p class="ltx_p" id="id3.3">Originally introduce
