4
$\begingroup$

I'm trying to prove a result but I'm stuck at the very end of it: I'm having troubles understanding how noise propagates when considering a probability distribution. In other words, if I inject some noise in a vector, how does it change its probability distribution? Let's give some notation:

Let $\sigma: \mathbb{R}^d \rightarrow (0,1)^d$ be the softmax operator which maps $x$ to the manifold of the probability distributions on $d$ variables defined in the following way: $$\sigma(x)_i = \frac{e^{x_i}}{\sum_j e^{x_j}}$$ I have a vector $x \in \mathbb{R}^d$ with norm one. I also have random noise vector $\eta \in \mathbb{R}^d$ with norm $1/k$ taken uniformely at random from the sphere $S^{d-1}$ of radius 1/k, where k is a large natural number.

I need to compute an upper bound of the following expected value, which is the norm of the difference between the vector without noise and the one with injected noise $\eta$:

$$ \mathbb{E}[||\sigma(x) - \sigma(x+\eta)||]$$

I gave a bounty to this question because I really need to understand this problem (I will have to solve several problems of this kind).

Thank you very much!

$\endgroup$
  • 2
    $\begingroup$ In 2 dimensions this can be calculated numerically and visualized, e.g. as below with $x=(2,3)$, $k=10$, $E=0.025$. wolframalpha.com/input/… If $f(\eta)$ is the norm, then $f=0$ when $\eta$ is proportional to $(1,1)$ or to $(-1,-1)$. So $f$ can be approximated by two parabolas, and $E[f]\simeq (1/3)(f((1,-1)/k\sqrt{2})+f((-1,1)/k\sqrt{2}))$. In the example, that gives $0.026$. $\endgroup$ – Matt F. Jan 22 at 17:31
  • $\begingroup$ Thank you! do you know a way to show the same thing in more dimensions? I'm trying to get an answer but I have no idea how to keep going. Thanks again! $\endgroup$ – Alfred Jan 25 at 18:10
  • $\begingroup$ My next step would be numerical experimentation. $\endgroup$ – Matt F. Jan 25 at 20:03
  • $\begingroup$ There is one thing I don't understand from your example: $x = (2,3)$ doesn't have norm one. Did you take care of it in the Wolfram alpha experimentation? Thanks again $\endgroup$ – Alfred Jan 25 at 21:23
  • 1
    $\begingroup$ You can see what I did in WolframAlpha and redo it with $x=(0.6,0.8)$ if you like $\endgroup$ – Matt F. Jan 26 at 0:05
1
+100
$\begingroup$

$$\mathbb{E}(|\sigma(x+\eta)-\sigma(x)|)=\mathbb{E}(|J_\sigma\eta|)+O(|\eta|^2)$$where $J_\sigma$ is the Jacobi matrix $$ (J_\sigma)_{i,j}=\frac{e^{x_i}}{\sum_k e^{x_k}}\delta_{i,j} - \frac{e^{x_i+x_j}}{(\sum_k e^{x_k})^2}$$ and $$\mathbb{E}(|J_\sigma\eta|)^2\leq \mathbb{E}(|J_\sigma\eta|^2)=\mathbb{E}(\langle \eta J_\sigma^2\eta\rangle)=\frac{|\eta|^2}{d}\text{Tr}(J_\sigma^2)$$with $$\text{Tr}(J_\sigma^2 )=\sum_i \frac{e^{2x_i}}{(\sum_k e^{x_k})^2}+\sum_{i,j} \frac{e^{2x_i}e^{2x_j}}{(\sum_k e^{x_k})^4} -2\sum_{i}\frac{e^{3x_i}}{(\sum_k e^{x_k})^3} \\ = \sum_i (\sigma(x)_i)^2+\big(\sum_i (\sigma(x)_i)^2\big)^2-2\sum_i (\sigma(x)_i)^3$$

Conclusion : $$\mathbb{E}(|\sigma(x+\eta)-\sigma(x)|)\leq \frac{\eta}{\sqrt{d}}\sqrt{\sum_i (\sigma(x)_i)^2+\big(\sum_i (\sigma(x)_i)^2\big)^2-2\sum_i (\sigma(x)_i)^3 }+O(|\eta|^2)$$

$\endgroup$
  • 1
    $\begingroup$ In the first example above, the $\sigma$ coordinates are $0.27$ and $0.73$, so this gives $\frac{1}{10\sqrt{2}}\sqrt{.61 + .37 - 2(.41)} + O(1/100) \simeq .028$ $\endgroup$ – Matt F. Jan 31 at 12:26
  • $\begingroup$ Thank you to the both of you! $\endgroup$ – Alfred Jan 31 at 16:43

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.