Most Influential Subset Selection: Challenges, Promises, and Beyond
This work addresses the challenge of understanding collective data influence for researchers and practitioners in machine learning, though it is incremental as it builds on existing influence function methods.
The paper tackles the problem of attributing machine learning model behaviors to training data by studying the Most Influential Subset Selection (MISS) problem, revealing that influence-based greedy heuristics can fail in linear regression but an adaptive iterative version can partially address these issues, with experiments on real-world datasets showing effectiveness in classification and non-linear neural networks.
How can we attribute the behaviors of machine learning models to their training data? While the classic influence function sheds light on the impact of individual samples, it often fails to capture the more complex and pronounced collective influence of a set of samples. To tackle this challenge, we study the Most Influential Subset Selection (MISS) problem, which aims to identify a subset of training samples with the greatest collective influence. We conduct a comprehensive analysis of the prevailing approaches in MISS, elucidating their strengths and weaknesses. Our findings reveal that influence-based greedy heuristics, a dominant class of algorithms in MISS, can provably fail even in linear regression. We delineate the failure modes, including the errors of influence function and the non-additive structure of the collective influence. Conversely, we demonstrate that an adaptive version of these heuristics which applies them iteratively, can effectively capture the interactions among samples and thus partially address the issues. Experiments on real-world datasets corroborate these theoretical findings and further demonstrate that the merit of adaptivity can extend to more complex scenarios such as classification tasks and non-linear neural networks. We conclude our analysis by emphasizing the inherent trade-off between performance and computational efficiency, questioning the use of additive metrics such as the Linear Datamodeling Score, and offering a range of discussions.