Answers.Body: <p>Well, conditional probability (density) does not necessarily need to be no greater than its marginal probability (density). That means <span class="math-container">$p(x_j|c_t)\le p(x_j)$</span> is not always true. For example, consider two discrete r.v.s <span class="math-container">$X,Y\in\{0,1\}$</span> such that <span class="math-container">$$
  P(X=0,Y=0)=0.05,\\
  P(X=1,Y=0)=0.05,\\
  P(X=0,Y=1)=0.05,\\
  P(X=1,Y=1)=0.85
  $$</span>. We have <span class="math-container">$P(X=0)=0.1$</span>; however, <span class="math-container">$P(X=0|Y=0)=0.5$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-11-06T22:48:20.073Z
Answers.LastActivityDate: 2021-11-06T22:48:20.073Z
Answers.UserDisplayName: TQCH
Answers.Body: <p>The mathematical notation in this paper is an absolute mess.</p>
  <p>What I <em>think</em> the authors meant to say with <span class="math-container">$\mathbb{E}_{x_j}$</span> is actually <span class="math-container">$\mathbb{E}_{x\in X_\text{neg}}$</span>, where <span class="math-container">$X_\text{neg}$</span> is the set of negative samples.</p>
  <p>Since you are sampling <span class="math-container">$N$</span> random points (<span class="math-container">$|X| = N$</span>) where only a single one of them is positive, this means that all the other <span class="math-container">$N-1$</span> elements are negative, so <span class="math-container">$|X_\text{neg}| = N-1$</span>. Then, we can calulate the expectation value of some function <span class="math-container">$f(x)$</span> as:</p>
  <p><span class="math-container">$$\mathbb{E}_{x \in X_\text{neg}} \left[f(x)\right] = \frac{1}{N-1}\sum_{x \in X\text{neg}}f(x)$$</span></p>
  <p>Replacing <span class="math-container">$f(x)$</span> with <span class="math-container">$\frac{p(x | c_t)}{p(x)}$</span>, we have:</p>
  <p><span class="math-container">$$\mathbb{E}_{x \in X_\text{neg}} \left[\frac{p(x | c_t)}{p(x)}\right] = \frac{1}{N-1}\sum_{x \in X\text{neg}}\frac{p(x | c_t)}{p(x)}$$</span></p>
  <p>or</p>
  <p><span class="math-container">$$\sum_{x \in X\text{neg}}\frac{p(x | c_t)}{p(x)} = (N-1)\mathbb{E}_{x \in X_\text{neg}} \left[\frac{p(x | c_t)}{p(x)}\right]$$</span></p>
  <p>I think using the subscript <span class="math-container">$x_j$</span> is stupid, so I omitted it. However, notice that this is an equality, not an approximation, so I'm unsure if this is really what the authors had in mind. Also, setps (8) to (9) look a bit suspicious because it isn't very obvious why the expectation value would be one.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-12-28T17:13:49.950Z
Answers.LastActivityDate: 2024-12-28T17:13:49.950Z
Answers.UserDisplayName: Ícaro Lorran
Body: <p>In the appendix of <a href="https://arxiv.org/abs/1807.03748" rel="nofollow noreferrer">Representation Learning with Contrastive Predictive Coding</a>, van den Oord et al. prove that optimizing InfoNCE is equivalent to maximize the mutual information between input image <span class="math-container">$x_t$</span> and the context latent <span class="math-container">$c_t$</span> as follows:
  <a href="https://i.sstatic.net/FximA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/FximA.png" alt="enter image description here" /></a></p>
  <p>where <span class="math-container">$x_{t+k}$</span> is the image at time step <span class="math-container">$t+k$</span>, <span class="math-container">$X_{neg}$</span> is a set of negative samples that do not appear in the sequence <span class="math-container">$x_t$</span> belongs to, and <span class="math-container">$N-1$</span> is the negative samples used to compute InfoNCE.</p>
  <p>I'm confused about Equation <span class="math-container">$(8)$</span>. van den Oord et al. stressed that Equation <span class="math-container">$(8)$</span> becomes more accurate as <span class="math-container">$N$</span> increases, but I cannot see why. Here's my understanding, for <span class="math-container">$x_j\in X_{neg}$</span>, we have <span class="math-container">$p(x_j|c_t)\le p(x_j)$</span> . Therefore, <span class="math-container">$\sum_{x_j\in X_{neg}}{p(x_j|c_t)\over p(x_j)}\le N-1$</span> and this does not become accurate as <span class="math-container">$N$</span> increases. In fact, I think the gap between the left and right of <span class="math-container">$\le$</span> increases as <span class="math-container">$N$</span> increases. Do I make any mistake?</p>
  
Tags: <machine-learning><deep-learning>
Title: Confusion about the proof that optimizing InfoNCE equals to maximizing mutual information
UserDisplayName: Maybe
ThreadText: # Confusion about the proof that optimizing InfoNCE equals to maximizing mutual information
  
  (Asked by: username_0 on 2020-06-03)
  
  In the appendix of [Representation Learning with Contrastive Predictive Coding](https://arxiv.org/abs/1807.03748), van den Oord et al. prove that optimizing InfoNCE is equivalent to maximize the mutual information between input image $x\_t$ and the context latent $c\_t$ as follows:
  [![enter image description here](https://i.sstatic.net/FximA.png)](https://i.sstatic.net/FximA.png)
  
  where $x\_{t+k}$ is the image at time step $t+k$, $X\_{neg}$ is a set of negative samples that do not appear in the sequence $x\_t$ belongs to, and $N-1$ is the negative samples used to compute InfoNCE.
  
  I'm confused about Equation $(8)$. van den Oord et al. stressed that Equation $(8)$ becomes more accurate as $N$ increases, but I cannot see why. Here's my understanding, for $x\_j\in X\_{neg}$, we have $p(x\_j|c\_t)\le p(x\_j)$ . Therefore, $\sum\_{x\_j\in X\_{neg}}{p(x\_j|c\_t)\over p(x\_j)}\le N-1$ and this does not become accurate as $N$ increases. In fact, I think the gap between the left and right of $\le$ increases as $N$ increases. Do I make any mistake?
  
  **Tags:** machine-learning, deep-learning
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2021-11-06. Score: 0
  
  Well, conditional probability (density) does not necessarily need to be no greater than its marginal probability (density). That means $p(x\_j|c\_t)\le p(x\_j)$ is not always true. For example, consider two discrete r.v.s $X,Y\in\{0,1\}$ such that $$
  P(X=0,Y=0)=0.05,\\
  P(X=1,Y=0)=0.05,\\
  P(X=0,Y=1)=0.05,\\
  P(X=1,Y=1)=0.85
  $$. We have $P(X=0)=0.1$; however, $P(X=0|Y=0)=0.5$.
  
  
  ---
  
  ### Answer by username_2 on 2024-12-28. Score: 0
  
  The mathematical notation in this paper is an absolute mess.
  
  What I *think* the authors meant to say with $\mathbb{E}\_{x\_j}$ is actually $\mathbb{E}\_{x\in X\_\text{neg}}$, where $X\_\text{neg}$ is the set of negative samples.
  
  Since you are sampling $N$ random points ($|X| = N$) where only a single one of them is positive, this means that all the other $N-1$ elements are negative, so $|X\_\text{neg}| = N-1$. Then, we can calulate the expectation value of some function $f(x)$ as:
  
  $$\mathbb{E}\_{x \in X\_\text{neg}} \left[f(x)\right] = \frac{1}{N-1}\sum\_{x \in X\text{neg}}f(x)$$
  
  Replacing $f(x)$ with $\frac{p(x | c\_t)}{p(x)}$, we have:
  
  $$\mathbb{E}\_{x \in X\_\text{neg}} \left[\frac{p(x | c\_t)}{p(x)}\right] = \frac{1}{N-1}\sum\_{x \in X\text{neg}}\frac{p(x | c\_t)}{p(x)}$$
  
  or
  
  $$\sum\_{x \in X\text{neg}}\frac{p(x | c\_t)}{p(x)} = (N-1)\mathbb{E}\_{x \in X\_\text{neg}} \left[\frac{p(x | c\_t)}{p(x)}\right]$$
  
  I think using the subscript $x\_j$ is stupid, so I omitted it. However, notice that this is an equality, not an approximation, so I'm unsure if this is really what the authors had in mind. Also, setps (8) to (9) look a bit suspicious because it isn't very obvious why the expectation value would be one.
  
  
  ---
  
  