Answers.Body: <p>Let's brake down each component of the formula, on the left side we have</p>
  <p><span class="math-container">${\Omega(g)}$</span></p>
  <p>The authors state that they use omega to refer to the set of models too difficult to be tractable (or explained), so <em>g</em> is just a model, or set of weights, omega g is a set of models. Next we have</p>
  <p><span class="math-container">${\infty \mathbb{1}}$</span></p>
  <p>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:</p>
  <p><span class="math-container">${\left[\left\|w_{g}\right\|_{0}&gt;K\right]}$</span></p>
  <p>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:</p>
  <p><span class="math-container">${\Omega(g)=\infty \mathbb{1}\left[\left\|w_{g}\right\|_{0}&gt;K\right]}$</span></p>
  <p>Means: &quot;The infinite set of intractable models, made of weights vectors with length larger than a predefined value K&quot;.</p>
  <p>PS: if you're interested in models interpretability, you might want to check <a href="https://arxiv.org/pdf/1703.01365.pdf" rel="nofollow noreferrer">Integrated Gradients</a>, the authors created a fantastic <a href="https://captum.ai/" rel="nofollow noreferrer">repo</a> that implement many algorithms for pytorch.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-17T10:11:19.037Z
Answers.LastActivityDate: 2022-01-17T10:11:19.037Z
Answers.UserDisplayName: Edoardo Guerriero
Body: <p>I've recently been reading <a href="https://arxiv.org/pdf/1602.04938.pdf" rel="nofollow noreferrer">this paper on LIME</a>, 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?</p>
  <blockquote>
  <p>For text classification, we ensure that the explanation is interpretable by letting the <em>interpretable representation</em> be a bag of words, and by setting a limit <span class="math-container">$K$</span> on the number of words, i.e. <span class="math-container">$\color{red}{\Omega(g)=\infty \mathbb{1}\left[\left\|w_{g}\right\|_{0}&gt;K\right]}$</span>. Potentially, <span class="math-container">$K$</span> can be adapted to be as big as the user can handle, or we could have different values of <span class="math-container">$K$</span> for different instances.</p>
  </blockquote>
  <p>Could anyone help me with it?</p>
  
Tags: <machine-learning><papers><notation><explainable-ai>
Title: What does the complexity equation constitute exactly in “Why Should I Trust You?” LIME paper
UserDisplayName: loose the fools juice
ThreadText: # What does the complexity equation constitute exactly in “Why Should I Trust You?” LIME paper
  
  (Asked by: username_0 on 2022-01-14)
  
  I've recently been reading [this paper on LIME](https://arxiv.org/pdf/1602.04938.pdf), 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?
  
  **Tags:** machine-learning, papers, notation, explainable-ai
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-01-17. Score: 0 | Accepted answer
  
  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](https://arxiv.org/pdf/1703.01365.pdf), the authors created a fantastic [repo](https://captum.ai/) that implement many algorithms for pytorch.
  
  
  ---
  
  