2017

Efficient Data Representation by Selecting Prototypes with Importance Weights

Gurumoorthy, Karthik S., Dhurandhar, Amit, Cecchi, Guillermo et al.

Understand

Prototypical examples that best summarizes and compactly represents an underlying complex data distribution communicate meaningful insights to humans in domains where simple explanations are hard to extract.

In this paper we present algorithms with strong theoretical guarantees to mine these data sets and select prototypes a.k.a.
representatives that optimally describes them.
Our work notably generalizes the recent work by Kim et al.

Built on

V. Ivanov, The theory of approximate methods and their application to the numerical solution of singular integral equations . New York, NY, USA: Springer, 1976
1976
Earlier work this paper cites.
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An Analysis of Approximations for Maximizing Submodular Set Functions,” Math. Program. , vol. 14, pp. 265–294, December 1978
1978
Earlier work this paper cites.
M. Weiser, “Programmers use slices when debugging,” Communications of the ACM , vol. 25, no. 7, pp. 446–452, 1982
1982
Earlier work this paper cites.
L. Lovász, Mathematical programming – The State of the Art . Springer, 1983, ch. Submodular Functions and Convexity, pp. 235–257
1983
Earlier work this paper cites.
P. Stark and R. L. Parker, “Bounded-variable least-squares: an algorithm and applications,” Computational Statistics , vol. 10, pp. 129–130, 1995
1995
Earlier work this paper cites.
D. D. Lee and H. S. Seung, “Algorithms for non-negative matrix factorization,” in In NIPS . MIT Press, 2001, pp. 556–562
2001
Earlier work this paper cites.
S. Fujishige, Submodular functions and optimization , 2nd ed., ser. Annals of Discrete Mathematics. Elsevier Science, 2005, no. 58
2005
Earlier work this paper cites.
A. Gretton, K. M. Borgwardt, M. Rasch, B. Schölkopf, and A. J. Smola, “A Kernel Method for the Two-Sample-Problem,” in 20 t h 20^{th} Conference on Neural Information Processing Systems (NIPS) , 2006, pp. 513–520
2006
Earlier work this paper cites.
O. Dekel and Y. Singer, “Support Vector Machines on a Budget,” in 20 t h 20^{th} Conference on Neural Information Processing Systems (NIPS) , 2006, pp. 345–352
2006
Earlier work this paper cites.

Similar

A. Das and D. Kempe, “Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection,” in Intl. Conference on Machine Learning (ICML) , 2011
2011
Cited alongside, same era.
D. Agarwal, L. Li, and A. J. Smola, “Linear-Time Estimators for Propensity Scores,” in 14 t h 14^{th} Intl. Conference on Artificial Intelligence and Statistics (AISTATS) , 2011, pp. 93–100
2011
Cited alongside, same era.
J. Bien and R. Tibshirani, “Prototype Selection for Interpretable Classification,” Ann. Appl. Stat. , pp. 2403–2424, 2011
2011
Cited alongside, same era.
C. Chang and C.-J. Lin, “LIBSVM: A library for support vector machines,” ACM Transactions on Intelligent Systems and Technology , vol. 2, 2011
2011
Cited alongside, same era.
R. Caruana, Y. Lou, J. Gehrke, P. Koch, M. Sturm, and N. Elhadad, “Intelligible models for healthcare,” in ACM conference on Knowledge Discovery and Data Mining (KDD) , 2015
2015
Cited alongside, same era.
F. Wang and C. Rudin, “Falling rule lists,” in 18 t h 18^{th} Intl. Conference on Artificial Intelligence and Statistics (AISTATS) , 2015
2015
Cited alongside, same era.
G. Kolata, “Death rates rising for middle-aged white americans, study finds,” in https://www.nytimes.com/2015/11/03/health/death-rates-rising-for-middle-aged-white-americans-study-finds.html?_r=0 , 2015
2015
Cited alongside, same era.
B. Kim, R. Khanna, and O. Koyejo, “Examples are not Enough, Learn to Criticize! Criticism for Interpretability,” in 30 t h 30^{th} Conference on Neural Information Processing Systems (NIPS) , 2016
2016
Cited alongside, same era.
A. Semuels, “Poor at 20, poor for life,” in https://www.theatlantic.com /business/archive/ 2016/07/social-mobility-america/491240/ , 2016
2016
Cited alongside, same era.

Then

E. Elenberg, R. Khanna, A. G. Dimakis, and S. Negahban, “Restricted Strong Convexity Implies Weak Submodularity,” in arXiv:1612.00804 , 2016
Original
2016
Later among the works it cites.
M. Ribeiro, S. Singh, and C. Guestrin, “”Why Should I Trust You?” Explaining the Predictions of Any Classifier,” in ACM SIGKDD Intl. Conference on Knowledge Discovery and Data Mining (KDD) , 2016
2016
Later among the works it cites.
G. Su, D. Wei, K. Varshney, and D. Malioutov, “Interpretable Two-level Boolean Rule Learning for Classification,” in https://arxiv.org/abs/1606.05798 , 2016
Original
2016
Later among the works it cites.
B. R. Gaines, “Algorithms for Fitting the Constrained Lasso,” in https://arxiv.org/pdf/1611.01511 , 2016
Original
2016
Later among the works it cites.
L. Oneto, S. Ridella, and D. Anguita, “Tikhonov, Ivanov and Morozov Regularization for Support Vector Machine Learning,” Mach. Learn. , vol. 103, no. 1, pp. 103–136, Apr 2016
2016
Later among the works it cites.
P. W. Koh and P. Liang, “Understanding black-box predictions via influence functions,” 2017
2017
Closest in time.
T. Idé and A. Dhurandhar, “Supervised Item Response Models for Informative Prediction,” Knowl. Inf. Syst. , vol. 51, no. 1, pp. 235–257, Apr. 2017
2017
Closest in time.
CDC, in https://wwwn.cdc.gov/nchs/ nhanes/ search/ datapage.aspx? Component = Questionnaire&CycleBeginYear=2013 , 2017
2017
Closest in time.
R. Khanna, E. Elenberg, A. Dimakis, S. Neghaban, and J. Ghosh, “Scalable Greedy Feature Selection via Weak Submodularity,” in 20 t h 20^{th} Intl. Conference on Artificial Intelligence and Statistics (AISTATS) , 2017
2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…