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$
5
  • 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 '19 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 '19 at 18:10
  • $\begingroup$ My next step would be numerical experimentation. $\endgroup$
    – Matt F.
    Jan 25 '19 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 '19 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 '19 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$
2
  • 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 '19 at 12:26
  • $\begingroup$ Thank you to the both of you! $\endgroup$
    – Alfred
    Jan 31 '19 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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