Discovering additive structure in black box functions

ABSTRACT

Many automated learning procedures lack interpretability, operating effectively as a black box: providing a prediction tool but no explanation of the underlying dynamics that drive it. A common approach to interpretation is to plot the dependence of a learned function on one or two predictors. We present a method that seeks not to display the behavior of a function, but to evaluate the importance of non-additive interactions within any set of variables. Should the function be close to a sum of low dimensional components, these components can be viewed and even modeled parametrically. Alternatively, the work here provides an indication of where intrinsically high-dimensional behavior takes place.The calculations used in this paper correspond closely with the functional ANOVA decomposition; a well-developed construction in Statistics. In particular, the proposed score of interaction importance measures the loss associated with the projection of the prediction function onto a space of additive models. The algorithm runs in linear time and we present displays of the output as a graphical model of the function for interpretation purposes.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: Leo Breiman, Bagging predictors, Machine Learning, v.24 n.2, p.123-140, Aug. 1996 [doi>10.1023/A:1018054314350]
• 3: A. Buja, D. F. Swayne, M. L. Littman, N. Dean, and H. Hofmann. Xgvis: Interactive data visualization with multidimensional scaling, 2001. http://www.research.att.com/areas/stat/xgobi/index.html.
• 4: S. E. Feinberg. The Analysis of Cross-Classified Categorical Data. MIT Press, 1980.
• 5: J. H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29(5):1189--1232, 2001.
• 6: D. Harrison and D. L. Rubinfeld. Hedonic prices and the demand for clean air. Journal of Environmental Economics and Management, 5:81--102, 1978.
• 7: W. Hoeffding. A class of statistics with asymptotically normal distributions. Annals of Mathematical Statistics, 19:293--325, 1948.
• 8: G. Hooker. Black box diagnostics and the problem of extrapolation: Extending the functional anova. Technical report, Stanford University, 2004.
• 9: Tao Jiang , Art B. Owen, Quasi-regression with shrinkage, Mathematics and Computers in Simulation, v.62 n.3-6, p.231-241, 3 March 2003 [doi>10.1016/S0378-4754(02)00253-7]
• 10: R. Liu and A. B. Owen. Estimating mean dimensionality. Technical report, Stanford University, 2003.
• 11: A. B. Owen. The dimension distribution and quadrature test functions. Statistica Sinica, 13(1), 2003.
• 12: R-project. http://www.r-project.org/.
• 13: Charles Benjamin Roosen, Visualization and exploration of high-dimensional functions using the functional anova decomposition, Stanford University, Stanford, CA, 1996
• 14: I. M. Sobolá, Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates, Mathematics and Computers in Simulation, v.55 n.1-3, p.271-280, Feb. 15, 2001 [doi>10.1016/S0378-4754(00)00270-6]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Measurement, Verification

Keywords:
additive models, diagnostics, draphical models, feature selection, functional ANOVA, interpretation, visualization