Explainable AI

Explainability can come in various forms. The easiest, as it does not require opening the box, are wrapper-type methods that essentially try to describe the function being approximated in terms of something understandable, whether it be things like counterfactuals, or english interpretations of the form of the function. Similarly, one can build surrogate models (e.g. decision trees, linear models) that approximate the function (though you obviously lose accuracy), and provide a better trade-off.22 This approach seems a little weird to me though (and feels a little bit like russian dolls), where you’re basically trading (peeling) off complexity for more simple and interpretable models, but you’re not really comparing apples to oranges at that point.

Here’s an [[idea]]: what if you can come up with something like the tangent plane, but the explainable plane, in that for every point estimate provided by the machine learning model, you can just find a super simple, interpretable model that does a good, local job of explaining stuff for that particular defendent (has to exactly predict what the ML model predicted, hence the parallels to the tangent plane). Actually, this is very similar to LIME (Ribeiro, Singh, and Guestrin ⊕2016Ribeiro, Marco Tulio, Sameer Singh, and Carlos Guestrin. 2016. “"Why Should I Trust You?".” In KDD ’16: The 22nd Acm Sigkdd International Conference on Knowledge Discovery and Data Mining, 1135–44. New York, NY, USA: ACM.).

The other class of methods involve delving into the black-box, and providing method-specific interpretations of the actual learned model (e.g. for things like CNN, you can look at pixel-level heat-maps), or something more naive like just providing the model as a reproducible instance.

Noise Model

The noise model analyzed in these papers is very straightforward. It essentially follows the paradigmatic signal + noise model in statistics. Fix a graph \(G\) (defined by its adjacency matrix \(A\)), which we think of as the ground truth. Then the noisy observation (adjacency matrix \(\widetilde{A}\)) are produced by random bit-flips (0 to 1 or 1 to 0). For simplicity, the random bit-flips are modelled with only two parameters: \(\alpha\), the Type-1 error, and \(\beta\), the Type-2 error. That is,

\[ \begin{align*} P(\widetilde{A}_{ij} = 1 \given A_{ij} = 0) = \alpha, \quad P(\widetilde{A}_{ij} = 0 \given A_{ij} = 1) = \beta, \end{align*} \]

Thus, you’ve reduced the whole problem to estimating two parameters.11 Which feels a little extreme. Unsurprisingly, you use #method_of_moments to estimate them. However, because you have two parameters, you’re going to need more than one sample (i.e. two).

Actually, I think it’s a little more complicated than that (it’s not really a degree-of-freedom thing). One might think that with a large enough graph, you can probably split in two, and estimate the parameters on each half (and they’d be independent). However, I suspect the problem is that the model is a little too general, so if your \(\alpha, \beta\) are too large, then you can’t really guess anything.22 i.e. you have no control of what’s signal and what’s noise. My guess is that if you have two samples, then you have access to the intersection/set-difference, which makes it more feasible to estimate things. But the thing is that this then relies on the intersection.

This makes me think that a) if you restrict the \(\alpha, \beta\) to be suitably small, then you can probably be okay with one sample; and b) this model is actually pretty restrictive.33 I mean, in terms of the space of possible samples it is fine, but I guess like any model, you really don’t want your results to depend so much on the assumptions.

This is similar to the #stochastic_blockmodel, in that these parameters are really just nuisance parameters. In that model, you can actually estimate many things without actually knowing these nuisance parameters.

A Better Model?

Two things come to mind. First is model-fitting and checking, though not necessarily singularly focused on this particular noise model. As I’ve said before, almost all network models are a terrible model for real-life data, especially the parametric ones. This particular model is technically parametric, but very different. So what we want are diagnostic checks to see how comformal our data is to the models. Since this procedure utilizes the fact that you have multiple samples, then that also means that you probably should be able to use that for diagnostics.

Along a similar line, it seems that what we would want is a more robust version of this noise model. Or, another way to think about this is that, what you want are estimators that are more robust to the model assumptions.44 like median for measure of centrality not assuming normality in the errors. I’m not really sure what the form of this would be: something a little more non-parametric?

If we are interested in the application of contact networks, then it might be fruitful to consider in isolation, and come up with a particular noise model that we think suits this dataset.55 and potentially the paper could be a general type of paper that we can then demonstrate specializing to different data types.

Matrix Factorization

A celebrated result in this area is (Ge, Lee, and Ma ⊕2016Ge, Rong, Jason D Lee, and Tengyu Ma. 2016. “Matrix completion has no spurious local minimum.” In Advances in Neural Information Processing Systems, 2981–9. University of Southern California, Los Angeles, United States.). They consider the matrix factorization problem (with symmetric matrix, so that it can be written as \(XX^\top\)). Note that this problem is non-convex.11 The general version of this problem, with \(UV^\top\), interestingly, is at least alternatingly (marginally) convex (which is why people do alternating minimization). Under some typical incoherence conditions,22 To ensure that there is enough signal in the matrix, preventing cases where all the entries are zero, say. they are able to show that this optimization problem has no spurious local minima. In other words, for every optima to the function \[ \begin{align*} \widetilde{g}(x) = \norm{ P_\Omega (M - X X^\top) }_F^2, \end{align*} \] it is also a global minima (which means \(=0\)).33 They were inspired, in part, by the empirical observation that random initialization sufficed, even though all the theory required either conditions on the initialization, or some more elaborate procedure.

Proof technique: they compare this sample version \(\widetilde{g}(x)\) to the population version \(g(x) = \norm{ M - X X^\top }_F^2\), and use statistics and concentration equalities to get desired bounds.

To reiterate, they don’t use any explicit penalty (except something that’s helpful for the proof technique to ensure you are within the coherent regime). The matrix factorization form suffices.

Important: something I missed the first time round, but actually makes this somewhat less impressive: they basically assume the rank is given, and then force the matrix to have that dimension. This differs from (Arora et al. ⊕2019Arora, Sanjeev, Nadav Cohen, Wei Hu, and Yuping Luo. 2019. “Implicit Regularization in Deep Matrix Factorization.” arXiv.org, May. http://arxiv.org/abs/1905.13655v3.)’s deep matrix factorization as there they aren’t forcing the dimensions. This doesn’t seem that impressive anymore.

Non-Convex Optimization

src: off-convex.

The general non-convex optimization is an NP-hard problem, to find the global optima. But even ignoring the problem of local vs global, it’s even difficult to differentiate between optima and saddle points.

Saddle points are those where the gradients in the direction of the axis happen to be zero (usually one is max, the other is a min). In the case of gradient descent, since we move in the direction of gradient for each coordinate separately, then we’re basically stuck.

If one has access to second-order information (i.e. the Hessian), then it is easy to distinguish minima from saddle points (the Hessian is PSD for minima). However, it is usually too expensive to calculate the Hessian.

What you might hope is that the saddle points in the problem are somewhat well-behaved: there exists (at least) one direction such that the gradient is pretty steep. This way, if you can perturb your gradient, then hopefully you’ll accidentally end up in that direction that lets you escape it.

That’s where noisy gradient descent (NGD) comes into play. This is actually a little different to stochastic gradient descent, which is noisy, but that noise is a function of the data. What we want is actually to perturb the gradient itself, so you just add a noise vector with mean 0. This allows the algorithm to effectively explore all directions.44 In subsequent work, it has been established that gradient descent can still escape saddle points, but asymptotically, and take exponential time. On the other hand, NGD can solve it in polynomial time.

What they show is that NGD is able to escape those saddle points, as they eventually find that escape direction. However, the addition of the noise might have problems with actual minima, since it might perturb the updates sufficiently to push it out of the minima. Thankfully, they show that this isn’t the case. Intuitively, this feels like it shouldn’t be that hard – if you imagine a marble on these surfaces, then it feels like it should be pretty easy to perturb oneself to escape the saddles, while it seems fairly difficult to get out of those wells.

Proof technique: replace \(f\) by its second-order taylor expansion \(\hat{f}\) around \(x\), allowing you to work with the Hessian directly. Show that function value drops with NGD, and then show that things don’t change if you go back to \(f\). In order for this to hold, you need the Hessian to be sufficiently smooth; known as the Lipschitz Hessian condition.

It turns out that it is relatively straightforward to extend this to a constrained optimization problem (since you can just write the Lagrangian form which becomes unconstrained). Then you need to consider the tangent and normal space of this constrain set. The algorithm is basically projected noisy gradient descent (simply project onto the constraint set after each gradient update).

Thoughts

The paper itself is more interested in learning rates. What I think is interesting here is the preoccupation with scale-invariance. There seems to be something self-correcting about it that makes it ideal for neural network training. Also, I wonder if there is any way to use the above scale-invariance facts in our proofs.

They also deal with learning rates, except that the rates themselves are uniform across all parameters, make it much easier to analyze—unlike Adam where you have adaptivity.

Relation to DP

Here’s an interesting relation to #differential_privacy. One of the motivations for this paper is that DP models (DP implies you can’t memorize) fail to achive SOTA results for the same problem as these memorizing solutions. If you look at how these DP models fail, you see that they fail on the exact class of problems as those proposed here, i.e. it cannot memorize the tail of the mixture distribution. This is definitely something to keep in mind for [[project-interpolation]].

Backlinks

• [[pseudo-inverses-and-sgd]]
  • thanks to this tweet, realize there’s a section in (Zhang et al. ⊕2019Zhang, Chiyuan, Benjamin Recht, Samy Bengio, Moritz Hardt, and Oriol Vinyals. 2019. “Understanding deep learning requires rethinking generalization.” In 5th International Conference on Learning Representations, Iclr 2017 - Conference Track Proceedings. University of California, Berkeley, Berkeley, United States.) [[rethinking-generalization]] that relates to (Bartlett et al. ⊕2020Bartlett, Peter L, Philip M Long, Gábor Lugosi, and Alexander Tsigler. 2020. “Benign overfitting in linear regression.” Proceedings of the National Academy of Sciences of the United States of America vol. 80 (April): 201907378.) [[benign-overfitting-in-linear-regression]], in that they show that the SGD solution is the same as the minimum-norm (pseudo-inverse)
    • the curvature of the minimum (LS) solutions don’t actually tell you anything (they’re the same)
    • “Unfortunately, this notion of minimum norm is not predictive of generalization performance. For example, returning to the MNIST example, the \(l_2\)-norm of the minimum norm solution with no preprocessing is approximately 220. With wavelet preprocessing, the norm jumps to 390. Yet the test error drops by a factor of 2. So while this minimum-norm intuition may provide some guidance to new algorithm design, it is only a very small piece of the generalization story.”
    • but this is changing the data, so I don’t think this comparison really matters – it’s not saying across all kinds of models, we should be minimizing the norm. it’s just saying that we prefer models with minimum norm
    • interesting that this works well for MNIST/CIFAR10
    • there must be something in all of this: on page 29 of slides, they show that SGD converges to min-norm interpolating solution with respect to a certain kernel (so the norm is on the coefficients for each kernel)
    • as pointed out, this is very different to the benign paper, as this result is data-independent (it’s just a feature of SGD)
• [[matrix-factorization-to-linear-model]]
  • Update: following on from [[experimental-logs-for-matrix-completion]], we have looked at how the nuclear norm fails in the depth-1 case, which is that you dampen the top singular values and reconstruct the residuals from small singular vectors (feels ever so slightly like [[benign-overfitting-in-linear-regression]]).

Lit Review

• Testing Equivalence of Clustering, (Gao and Ma ⊕2019Gao, Chao, and Zongming Ma. 2019. “Testing Equivalence of Clustering.” arXiv.org, October. http://arxiv.org/abs/1910.12797v2.)
  • abstract
    • “In this paper, we test whether two datasets share a common clustering structure. As a leading example, we focus on comparing clustering structures in two independent random samples from two mixtures of multivariate Gaussian distributions. Mean parameters of these Gaussian distributions are treated as potentially unknown nuisance parameters and are allowed to differ. Assuming knowledge of mean parameters, we first determine the phase diagram of the testing problem over the entire range of signal-to-noise ratios by providing both lower bounds and tests that achieve them. When nuisance parameters are unknown, we propose tests that achieve the detection boundary adaptively as long as ambient dimensions of the datasets grow at a sub-linear rate with the sample size.”
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing, (Gao and Ma ⊕2018Gao, Chao, and Zongming Ma. 2018. “Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing.” arXiv.org, November. http://arxiv.org/abs/1811.06055v2.)
  • tests involving ER vs SBM
  • more general test that handle “degree-corrected” i’m guessing (via his paper with Lafferty)
  • results in a nice test that involves counts of subgraphs/motifs (essentially boiling down to edges, vees and triangles)
    • it’s independent of the heterogeneity of the degree distribution, so you don’t have to estimate those nuisance parameters
• Network Global Testing by Counting Graphlets (Jin, Ke, and Luo ⊕2018Jin, Jiashun, Zheng Tracy Ke, and Shengming Luo. 2018. “Network Global Testing by Counting Graphlets.” arXiv.org, July. http://arxiv.org/abs/1807.08440v1.)
  • reminds me of the method-of-moments type thing we did in the [[parameter-estimation-in-sbm]] paper

Backlinks

• [[master-paper-list]]
  • [[nonparametric-testing-on-graphs]] (this could also be a more applied paper, that discusses the general problem with doing tests, or just modeling things in social networks)
    • JASA

Literature Review

Candes and Plan (⊕2009Candes, Emmanuel J, and Yaniv Plan. 2009. “Matrix Completion with Noise.” Proceedings of the IEEE 98 (6): 925–36.) :

RMS: \(\dfrac{\norm{\hat{M} - M}_{F}}{N}\)

Oracle rate: \[ \begin{equation} \norm{ M^{*} - M }_{F} \approx p^{-1/2} \delta, \tag{1} \end{equation} \] where \(\delta = \norm{Z}_{F}\), \(Z\) is the added noise matrix, and \(p = \frac{m}{n^2}\) is the fraction of observed entries11 Something weird: this obviously breaks down when \(\delta = 0\), or if it has to be positive, then just take the limit.. This is for arbitrary noise. When it’s white (with s.d. \(\sigma\)), then \[ \norm{ M^{*} - M }_{F} \approx \sqrt{\frac{nr}{p}} \sigma, \] where \(r\) is the rank of the low-rank matrix. To translate this into \(\delta\), we have \(\E{\delta} = \E{\norm{F}_{Z}} \approx n \sigma\), and so RHS is \(\sqrt{\frac{r}{np}} \delta\). Comparing this to (1), this is much sharper since \(r\) is very small.

Their method (which uses some form of SDP) seem to get something like \(\sqrt{n}\) off the oracle rate.

Negahban and Wainwright (⊕2012Negahban, Sahand, and Martin J Wainwright. 2012. “Restricted strong convexity and weighted matrix completion: Optimal bounds with noise.” Journal of Machine Learning Research 13 (May): 1665–97.) :

error is scaled here by \(\frac{\eta}{d_r d_c} = \frac{\sigma}{n^2}\), so that it’s independent of the ambient dimension.

they actually use our ratio, not to regularize, but to “provide a tractable measure of how close \(\Omega\) is to a low-rank matrix”.

Hastie et al. (⊕2015Hastie, Trevor, Rahul Mazumder, Jason Lee, and Reza Zadeh. 2015. “Matrix completion and low-rank SVD via fast alternating least squares,” January.) : this is SoftImpute.

they make the comparison between (Cai, Candes, and Shen ⊕2010Cai, Jian-Feng, Emmanuel J Candes, and Zuowei Shen. 2010. “A Singular Value Thresholding Algorithm for Matrix Completion.” SIAM Journal on Optimization 20 (4): 1956–82.), which essentially solves \[ \begin{equation} \min \norm{Z}_{*} \text{ s.t. } P_{\Sigma}(Z) = P_{\Sigma}(X), \tag{2} \end{equation} \] compared to the noisy relaxed version in this paper: \[ \begin{align*} \min \norm{Z}_{*} \text{ s.t. } \norm{P_{\Sigma}(Z) - P_{\Sigma}(X)}_{F} < \delta. \end{align*} \]

Cai, Candes, and Shen (⊕2010Cai, Jian-Feng, Emmanuel J Candes, and Zuowei Shen. 2010. “A Singular Value Thresholding Algorithm for Matrix Completion.” SIAM Journal on Optimization 20 (4): 1956–82.) :

• they propose a first-order method for solving matrix completion that’s very fast and uses little memory
• as it’s iterative, they have a convergence proof
• they also show that the iterates have non-decreasing rank
• this is mainly an engineering task, in that they care about the ability to solve large-scale matrix completion problems (like the Netflix challenge)

Recht (⊕2011Recht, Benjamin. 2011. “A Simpler Approach to Matrix Completion” 12 (104): 3413–30.) :

they show optimality of the convex program (minimizing the nuclear norm, a la (2)), provided \[m > 32 \mu_1 \cdot r n \beta \log^2(n),\] for some \(\beta > 1\) and \(\mu_1\) is something like an upper bound on the entries of singular vectors. they’re not interested in noise, just recovery.

Matrix Factorization

I guess more generally, if you don’t have a square matrix, then the SVD deccomposition is no longer as regular. But that doesn’t seem to be that interesting of a generalization. In any case, iterative methods are often employed, but they suffer from the fact that oftentimes it’ll be biased towards one of the optimization variables (i.e. \(U\) vs \(V\)).

useful links:

• https://github.com/nmduc/neural-matrix-completion
• https://arxiv.org/pdf/1905.09050.pdf
• https://nuit-blanche.blogspot.com/2012/09/implementation-iterative-reweighted.html
• http://www.jmlr.org/papers/volume13/mohan12a/mohan12a.pdf