What does the complexity equation constitute exactly in “Why Should I Trust You?” LIME paper

Question

I've recently been reading this paper on LIME, an algorithm to interpret ANY machine learning model. I encountered this equation (in red) on page 4 and have just been having a hard time deciphering exactly what it means. I understand that it's a measure of complexity of something - but of what exactly? And what does each symbol in the equation entail and correspond to? What part(s) of the models and instances constitute and contribute to the complexity?

For text classification, we ensure that the explanation is interpretable by letting the interpretable representation be a bag of words, and by setting a limit $K$ on the number of words, i.e. $\color{red}{\Omega(g)=\infty \mathbb{1}\left[\left\|w_{g}\right\|_{0}>K\right]}$. Potentially, $K$ can be adapted to be as big as the user can handle, or we could have different values of $K$ for different instances.

Could anyone help me with it?

Answer 1

Let's brake down each component of the formula, on the left side we have

${\Omega(g)}$

The authors state that they use omega to refer to the set of models too difficult to be tractable (or explained), so g is just a model, or set of weights, omega g is a set of models. Next we have

${\infty \mathbb{1}}$

This is not a common notation, at least as far as I'm aware of, but conceptually they're trying to say there an infinite amount of such models, 1 could refer to the cardinality of the set, but honestly not 100% sure about it. Finally we have:

${\left[\left\|w_{g}\right\|_{0}>K\right]}$

This is the constrain that separate the intractable models from the tractable ones. K refers to the number of words allowed in the bag-of-words model used to convert words into numbers. If you're not familiar with that, you can simply think of it as one hot encoding. So if you have a vocabulary of 30k words, every word vector will be a one dimensional vector of length 30k, with a single 1 and all rest zeros. That zero norm might looks weird, but it simply refers to the length of the vectors. So to summarize:

${\Omega(g)=\infty \mathbb{1}\left[\left\|w_{g}\right\|_{0}>K\right]}$

Means: "The infinite set of intractable models, made of weights vectors with length larger than a predefined value K".

PS: if you're interested in models interpretability, you might want to check Integrated Gradients, the authors created a fantastic repo that implement many algorithms for pytorch.