Search

In recent years, many Machine Learning (ML) explanation techniques have been designed using ideas from cooperative game theory. These game-theoretic explainers suffer from high complexity, hindering their exact computation in practical settings. In our work, we focus on a wide class of linear game values, as well as coalitional values, for the marginal game based on a given ML model and predictor vector. By viewing these explainers as expectations over appropriate sample spaces, we design a novel Monte Carlo sampling algorithm that estimates them at a reduced complexity that depends linearly on the size of the background dataset. We set up a rigorous framework for the statistical analysis and obtain error bounds for our sampling methods. The advantage of this approach is that it is fast, easily implementable, and model-agnostic. Furthermore, it has similar statistical accuracy as other known estimation techniques that are more complex and model-specific. We provide rigorous proofs of statistical convergence, as well as numerical experiments whose results agree with our theoretical findings., Comment: 31 pages, 6 figures

Due to their power and ease of use, tree-based machine learning models, such as random forests and gradient-boosted tree ensembles, have become very popular. To interpret them, local feature attributions based on marginal expectations, e.g. marginal (interventional) Shapley, Owen or Banzhaf values, may be employed. Such methods are true to the model and implementation invariant, i.e. dependent only on the input-output function of the model. We contrast this with the popular TreeSHAP algorithm by presenting two (statistically similar) decision trees that compute the exact same function for which the "path-dependent" TreeSHAP yields different rankings of features, whereas the marginal Shapley values coincide. Furthermore, we discuss how the internal structure of tree-based models may be leveraged to help with computing their marginal feature attributions according to a linear game value. One important observation is that these are simple (piecewise-constant) functions with respect to a certain grid partition of the input space determined by the trained model. Another crucial observation, showcased by experiments with XGBoost, LightGBM and CatBoost libraries, is that only a portion of all features appears in a tree from the ensemble. Thus, the complexity of computing marginal Shapley (or Owen or Banzhaf) feature attributions may be reduced. This remains valid for a broader class of game values which we shall axiomatically characterize. A prime example is the case of CatBoost models where the trees are oblivious (symmetric) and the number of features in each of them is no larger than the depth. We exploit the symmetry to derive an explicit formula, with improved complexity and only in terms of the internal model parameters, for marginal Shapley (and Banzhaf and Owen) values of CatBoost models. This results in a fast, accurate algorithm for estimating these feature attributions., Comment: Minor corrections. 30 pages+appendix (64 pages in total), 10 figures. To appear in Foundations of Data Science

This article is a companion paper to our earlier work Miroshnikov et al. (2021) on fairness interpretability, which introduces bias explanations. In the current work, we propose a bias mitigation methodology based upon the construction of post-processed models with fairer regressor distributions for Wasserstein-based fairness metrics. By identifying the list of predictors contributing the most to the bias, we reduce the dimensionality of the problem by mitigating the bias originating from those predictors. The post-processing methodology involves reshaping the predictor distributions by balancing the positive and negative bias explanations and allows for the regressor bias to decrease. We design an algorithm that uses Bayesian optimization to construct the bias-performance efficient frontier over the family of post-processed models, from which an optimal model is selected. Our novel methodology performs optimization in low-dimensional spaces and avoids expensive model retraining., Comment: 29 pages, 32 figures

In this article, we study feature attributions of Machine Learning (ML) models originating from linear game values and coalitional values defined as operators on appropriate functional spaces. The main focus is on random games based on the conditional and marginal expectations. The first part of our work formulates a stability theory for these explanation operators by establishing certain bounds for both marginal and conditional explanations. The differences between the two games are then elucidated, such as showing that the marginal explanations can become discontinuous on some naturally-designed domains, while the conditional explanations remain stable. In the second part of our work, group explanation methodologies are devised based on game values with coalition structure, where the features are grouped based on dependencies. We show analytically that grouping features this way has a stabilizing effect on the marginal operator on both group and individual levels, and allows for the unification of marginal and conditional explanations. Our results are verified in a number of numerical experiments where an information-theoretic measure of dependence is used for grouping., Comment: 82 pages, 43 figures. Typos fixed. Some technical results have been improved

The objective of this article is to introduce a fairness interpretability framework for measuring and explaining the bias in classification and regression models at the level of a distribution. In our work, we measure the model bias across sub-population distributions in the model output using the Wasserstein metric. To properly quantify the contributions of predictors, we take into account the favorability of both the model and predictors with respect to the non-protected class. The quantification is accomplished by the use of transport theory, which gives rise to the decomposition of the model bias and bias explanations to positive and negative contributions. To gain more insight into the role of favorability and allow for additivity of bias explanations, we adapt techniques from cooperative game theory., Comment: 39 pages. (submitted for publication)

In this article we perform an asymptotic analysis of parallel Bayesian logspline density estimators. Such estimators are useful for the analysis of datasets that are partitioned into subsets and stored in separate databases without the capability of accessing the full dataset from a single computer. The parallel estimator we introduce is in the spirit of a kernel density estimator introduced in recent studies. We provide a numerical procedure that produces the normalized density estimator itself in place of the sampling algorithm. We then derive an error bound for the mean integrated squared error of the full dataset posterior estimator. The error bound depends upon the parameters that arise in logspline density estimation and the numerical approximation procedure. In our analysis, we identify the choices for the parameters that result in the error bound scaling optimally in relation to the number of samples. This provides our method with increased estimation accuracy, while also minimizing the computational cost., Comment: 31 pages, 10 figures, (submitted for publication)

In this article we develop a fully discrete variational scheme that approximates the equations of three dimensional elastodynamics with polyconvex stored energy. The fully discrete scheme is based on a time-discrete variational scheme developed by S.~Demoulini, D.~M.~A.~Stuart and A.~E.~Tzavaras (2001). We show that the fully discrete scheme is unconditionally stable. The proof of stability is based on a relative entropy estimation for the fully discrete approximates.

In this article we perform an asymptotic analysis of Bayesian parallel kernel density estimators introduced by Neiswanger, Wang and Xing (2014). We derive the asymptotic expansion of the mean integrated squared error for the full data posterior estimator and investigate the properties of asymptotically optimal bandwidth parameters. Our analysis demonstrates that partitioning data into subsets requires a non-trivial choice of bandwidth parameters that optimizes the estimation error., Comment: 31 pages, 8 pictures, submitted

In recent years, a number of methods have been developed to infer complex demographic histories, especially historical population size changes, from genomic sequence data. Coalescent Hidden Markov Models have proven to be particularly useful for this type of inference. Due to the Markovian structure of these models, an essential building block is the joint distribution of local genealogical trees, or statistics of these genealogies, at two neighboring loci in populations of variable size. Here, we present a novel method to compute the marginal and the joint distribution of the total length of the genealogical trees at two loci separated by at most one recombination event for samples of arbitrary size. To our knowledge, no method to compute these distributions has been presented in the literature to date. We show that they can be obtained from the solution of certain hyperbolic systems of partial differential equations. We present a numerical algorithm, based on the method of characteristics, that can be used to efficiently and accurately solve these systems and compute the marginal and the joint distributions. We demonstrate its utility to study the properties of the joint distribution. Our flexible method can be straightforwardly extended to handle an arbitrary fixed number of recombination events, to include the distributions of other statistics of the genealogies as well, and can also be applied in structured populations., Comment: 11 figures, 2 tables

We develop a framework in which to make sense of solutions containing the vacuum in Lagrangian gas dynamics. At and near vacuum, the specific volume becomes infinite and enclosed vacuums are represented by Dirac masses, so they cannot be treated in the usual weak sense. However, the weak* solutions recently introduced by the authors can be extended to include solutions containing vacuums. We present a definition of these natural vacuum solutions and provide explicit examples which demonstrate some of their features. Our examples are isentropic for clarity, and we briefly discuss the extension to the full $3\times3$ system of gas dynamics. We also extend our methods to one-dimensional dynamic elasticity to show that fractures cannot form in an entropy solution., Comment: 34 pages

We introduce a new notion of solution, which we call weak* solutions, for systems of conservation laws. These solutions can be used to handle singular situations that standard weak solutions cannot, such as vacuums in Lagrangian gas dynamics or cavities in elasticity. Our framework allows us to treat the systems as ODEs in Banach space. Starting with the observation that solutions act linearly on test functions $\alpha\in X$, we require solutions to take values in the dual space $X^*$ of $X$. Moreover, we weaken the usual requirement of measurability of solutions. In order to do this, we develop the calculus of the Gelfand integral, which is appropriate for weak* measurable functions. We then use the Gelfand calculus to define weak* solutions, and show that they are stronger than the usual notion of weak solution, although for $BV$ solutions the notions are equivalent. It is expected that these solutions will also shed light on vexing issues of ill-posedness for multi-dimensional systems., Comment: 33 pages, accepted to publication in Methods. Appl. Anal

Recent developments in big data and analytics research have produced an abundance of large data sets that are too big to be analyzed in their entirety, due to limits on computer memory or storage capacity. To address these issues, communication-free parallel Markov chain Monte Carlo (MCMC) methods have been developed for Bayesian analysis of big data. These methods partition data into manageable subsets, perform independent Bayesian MCMC analysis on each subset, and combine the subset posterior samples to estimate the full data posterior. Current approaches to combining subset posterior samples include sample averaging, weighted averaging, and kernel smoothing techniques. Although these methods work well for Gaussian posteriors, they are not well-suited to non-Gaussian posterior distributions. Here, we develop a new direct density product method for combining subset marginal posterior samples to estimate full data marginal posterior densities. Using a commonly-implemented distance metric, we show in simulation studies of Bayesian models with non-Gaussian posteriors that our method outperforms the existing methods in approximating the full data marginal posteriors. Since our method estimates only marginal densities, there is no limitation on the number of model parameters analyzed. Our procedure is suitable for Bayesian models with unknown parameters with fixed dimension in continuous parameter spaces., Comment: 32 pages, 3 figures

Recent developments in data science and big data research have produced an abundance of large data sets that are too big to be analyzed in their entirety, due to limits on either computer memory or storage capacity. Here, we introduce our R package 'BayesSummaryStatLM' for Bayesian linear regression models with Markov chain Monte Carlo implementation that overcomes these limitations. Our Bayesian models use only summary statistics of data as input; these summary statistics can be calculated from subsets of big data and combined over subsets. Thus, complete data sets do not need to be read into memory in full, which removes any physical memory limitations of a user. Our package incorporates the R package 'ff' and its functions for reading in big data sets in chunks while simultaneously calculating summary statistics. We describe our Bayesian linear regression models, including several choices of prior distributions for unknown model parameters, and illustrate capabilities and features of our R package using both simulated and real data sets., Comment: Updated URL in reference [12]; added to description of zero.intercept on p. 11; added minor clarifications throughout; results unchanged

We introduce various models for cellulose bio-degradation by micro-organisms. Those models rely on complex chemical mechanisms, involve the structure of the cellulose chains and are allowed to depend on the phenotypical traits of the population of micro-organisms. We then use the corresponding models in the context of multiple-trait populations. This leads to classical, logistic type, reproduction rates limiting the growth of large populations but also, and more surprisingly, limiting the growth of populations which are too small in a manner similar to the effects seen in populations requiring cooperative interactions (or sexual reproduction). This study hence offers a striking example of how some mechanisms resembling cooperation can occur in structured biological populations, even in the absence of any actual cooperation., Comment: 37 pages, accepted to ESAIM: Mathematical Modelling and Numerical Analysis (2017)

Microbial migration towards a trichloroethene (TCE) dense non-aqueous phase liquid (DNAPL) could facilitate the bioaugmentation of TCE DNAPL source zones. This study characterized the motility of the Geobacter dechlorinators in a TCE to cisdichloroethene dechlorinating KB-1TM subculture. No chemotaxis towards or away from TCE was found using an agarose in-plug bridge method. A second experiment placed an inoculated aqueous layer on top of a sterile sand layer and showed that Geobacter migrated several centimeters in the sand layer in just $7$ days. A random motility coefficient for Geobacter in water of $0.24 \pm 0.02$ cm$^2$ day$^{-1}$ was fitted. A third experiment used a diffusion-cell setup with a $5.5$ cm central sand layer separating a DNAPL from an aqueous top layer as a model source zone to examine the effect of random motility on TCE DNAPL dissolution. With top layer inoculation, Geobacter quickly colonized the sand layer, thereby enhancing the initial TCE DNAPL dissolution flux. After $19$ days, the DNAPL dissolution enhancement was only $24\%$ lower than with an homogenous inoculation of the sand layer. A diffusion-motility model was developed to describe dechlorination and migration in the diffusion-cells. This model suggested that the fast colonization of the sand layer by Geobacter was due to the combination of random motility and growth on TCE., Comment: in Journal of Contaminant Hydrology (accepted 2014), 48 pages

Recent advances in big data and analytics research have provided a wealth of large data sets that are too big to be analyzed in their entirety, due to restrictions on computer memory or storage size. New Bayesian methods have been developed for large data sets that are only large due to large sample sizes; these methods partition big data sets into subsets, and perform independent Bayesian Markov chain Monte Carlo analyses on the subsets. The methods then combine the independent subset posterior samples to estimate a posterior density given the full data set. These approaches were shown to be effective for Bayesian models including logistic regression models, Gaussian mixture models and hierarchical models. Here, we introduce the R package parallelMCMCcombine which carries out four of these techniques for combining independent subset posterior samples. We illustrate each of the methods using a Bayesian logistic regression model for simulation data and a Bayesian Gamma model for real data; we also demonstrate features and capabilities of the R package. The package assumes the user has carried out the Bayesian analysis and has produced the independent subposterior samples outside of the package. The methods are primarily suited to models with unknown parameters of fixed dimension that exist in continuous parameter spaces. We envision this tool will allow researchers to explore the various methods for their specific applications, and will assist future progress in this rapidly developing field., Comment: for published version see: http://www.plosone.org/article/fetchObject.action?uri=info%3Adoi%2F10.1371%2Fjournal.pone.0108425&representation=PDF

This article deals with relaxation approximations of nonlinear systems of hyperbolic balance laws. We introduce a class of relaxation schemes and establish their stability and convergence to the solution of hyperbolic balance laws before the formation of shocks, provided that we are within the framework of the compensated compactness method. Our analysis treats systems of hyperbolic balance laws with source terms satisfying a special mechanism which induces weak dissipation in the spirit of Dafermos [C.M. Dafermos J. Hyp. Diff. Equations, 3, 505-527, 2006], as well as hyperbolic balance laws with more general source terms. The rate of convergence of the relaxation system to a solution of the balance laws in the smooth regime is established. Our work follows in spirit the analysis presented in [S. Jin, X. Xin, Comm. Pure. Appl. Math. (1995), 48] and [Ch. Arvanitis, Ch. Makridakis, and A.E. Tzavaras, SIAM J. on Num. Anal. (2005), 42-4] for systems of hyperbolic conservation laws without source terms., Comment: 31 pages

We present a general framework for the approximation of systems of hyperbolic balance laws. The novelty of the analysis lies in the construction of suitable relaxation systems and the derivation of a delicate estimate on the relative entropy. We provide a direct proof of convergence in the smooth regime for a wide class of physical systems. We present results for systems arising in materials science, where the presence of source terms presents a number of additional challenges and requires delicate treatment. Our analysis is in the spirit of the framework introduced by Tzavaras [A. Tzavaras, Commun. Math. Sci., 3-2, 2005] for systems of hyperbolic conservation laws.

We consider a variational scheme developed by S. Demoulini, D. M. A. Stuart and A. E. Tzavaras [Arch. Ration. Mech. Anal. 157 (2001)] that approximates the equations of three dimensional elastodynamics with polyconvex stored energy. We establish the convergence of the time-continuous interpolates constructed in the scheme to a solution of polyconvex elastodynamics before shock formation. The proof is based on a relative entropy estimation for the time-discrete approximants in an environment of Lp-theory bounds, and provides an error estimate for the approximation before the formation of shocks.

The notion of singular limiting induced from continuum solutions (slic-solutions) is applied to the problem of cavitation in nonlinear elasticity, in order to re-assess an example of non-uniqueness of entropic weak solutions (with polyconvex energy) due to a forming cavity., Comment: link to the published article http://slsedp.cedram.org/item?id=SLSEDP_2012-2013____A14_0

We consider the equations describing the dynamics of radial motions for isotropic elastic materials; these form a system of non-homogeneous conservation laws. We construct a variational approximation scheme that decreases the total mechanical energy and at the same time leads to physically realizable motions that avoid interpenetration of matter., Comment: 29 pages

We consider the problem of dynamic cavity formation in isotropic compressible nonlinear elastic media. For the equations of radial elasticity we construct self-similar weak solutions that describe a cavity emanating from a state of uniform deformation. For dimensions $d =2, 3$ we show that cavity formation is necessarily associated with a unique precursor shock. We also study the bifurcation diagram and do a detailed analysis of the singular asymptotics associated to cavity initiation as a function of the cavity speed of the self-similar profiles. We show that for stress free cavities the critical stretching associated with dynamically cavitating solutions coincides with the critical stretching in the bifurcation diagram of equilibrium elasticity. Our analysis treats both stress-free cavities and cavities with contents., Comment: 49 pages