# Hyperplanes optimally classify data when inputs are conditionally independent - Why?

In the paper called Deep Learning and the Information Bottleneck Principle the authors state in section II A) the following:

Single neurons classify only linearly separable inputs, as they can implement only hyperplanes in their input space $u = wh+b$. Hyperplanes can optimally classify data when the inputs are conditioanlly indepenent.

To show this, they derive the following. Using Bayes theorem, they get:

$p(y|x) = \frac{1}{1 + exp(-log\frac{p(x|y)}{p(x|y')} -log\frac{p(y)}{p(y')})}$ (1)

Where $x$ is the input, $y$ is the class and $y'$ is the predicted class (I assume, $y'$ not defined). Continuing on, they state that:

$\frac{p(x|y)}{p(x|y')} = \prod^N_{j=1}[\frac{p(x_j|y)}{p(x_j|y')}]^{np(x_j)}$ (2)

Where $N$ is the input dimension and $n$ I'm not sure (again, both are undefined). Considering a sigmoidal neuron, with the sigmoid activation function $\sigma(u) = \frac{1}{1+exp(-u)}$ and preactivation $u$, after inserting (2) into (1) we get the optimal weight values $w_j = log\frac{p(x_j|y)}{p(x_j|y')}$ and $b=log\frac{p(y)}{p(y')}$, when the input values $h_j=np(x_j)$.

Now on to my questions. I understand how inserting (2) into (1) leads to the optimal weight and input values $w,b,h$. What I do not understand however, is the following:

1. How is (1) derived using Bayes theorem?
2. How is (2) derived? What is $n$? What is the meaning of it? I assume it has something to do with conditional independence
3. Even if the dimensions of x are conditionally independent, how can one state that it is equal to to its scaled probability? (i.e how can you state $h_j=np(x_j)$?)

EDIT: The variable $y$ is a binary class variable. From this I assume that $y'$ is the "other" class. This would solve question 1. Do you agree?

• I am struggling to understand where eq 2 comes from, despite the pointers in the answer by the author of the paper (Prof. Tishby). I do understand the part that comes from the conditional independence assumption. However, I am not sure about the exponent $n p(x_j)$ - why is it there? – IcannotFixThis Apr 3 '19 at 8:35

Sorry about the missing details in our short paper, but these relations and connections between Likelihood Ratio test and sigmoidal neurons are certainly not new, and can be found in textbooks (e.g. Bishop 2006). In our paper, 'N' is the input dimension and 'n' is the test sample size (which actually translated to the input SNR under the assumption that the SNR grows like sqrt(n)). The connection to the sigmoidal function is done through Bayes rule, as the posterior of the class. Nothing in the rest of the paper and our newer and more important paper from 2017 actually depends on this.

Naftali Tishby

• Thank you for clarifying this here. It is standard practice in this community to write full citations so that interested readers may seek out the sources. Could you please do this for Bishop (2006)? – mkt - Reinstate Monica Dec 19 '17 at 12:27

This is a model setup where the authors are using a special form of Bayes theorem that applies when you have a binary variable of interest. They first derive this special form of Bayes theorem as Equation (1), and then they show that the condition in Equation (2) leads them to the linear form specified for their network. It is important to note that the latter equation is not derived from previous conditions --- rather, it is a condition for the linear form they are using for their network.

Deriving the first equation: Equation (1) in the paper is just a form of Bayes theorem that frames the conditional probability of interest in terms of the standard logistic (sigmoid) function operating on functions of the likelihood and prior. Taking $$y$$ and $$y'$$ to be the two binary outcomes of the random variable $$Y$$, and applying Bayes theorem, gives:

\begin{aligned} p(y|\mathbf{x}) = \frac{p(y,\mathbf{x})}{p(\mathbf{x})} &= \frac{p(\mathbf{x}|y) p(y)}{p(\mathbf{x}|y) p(y)+p(\mathbf{x}|y') p(y')} \\[6pt] &= \frac{1}{1+ p(\mathbf{x}|y') p(y')/p(\mathbf{x}|y) p(y)} \\[6pt] &= \frac{1}{1+ \exp \Big( \log \Big( \tfrac{p(\mathbf{x}|y') p(y')}{p(\mathbf{x}|y) p(y)} \Big) \Big)} \\[6pt] &= \frac{1}{1+ \exp \Big( - \log \tfrac{p(\mathbf{x}|y)}{p(\mathbf{x}|y')} - \log \tfrac{p(y)}{p(y')} \Big)} \\[6pt] &= \text{logistic} \Bigg( \log \frac{p(\mathbf{x}|y)}{p(\mathbf{x}|y')} + \log \frac{p(y)}{p(y')} \Bigg). \\[6pt] \end{aligned}

Using Equation (2) as a condition for the lienar form of the network: As stated above, this equation is not something that is derived from previous results. Rather, it is a sufficient condition that leads to the linear form that the authors use in their model ---i.e., the authors are saying that if this equation holds, then certain subsequent results follow. Letting the input vector $$\mathbf{x} = (x_1,...,x_N)$$ have length $$N$$, if Equation (2) holds, then taking logarithms of both sides gives:

\begin{aligned} \log \frac{p(\mathbf{x}|y)}{p(\mathbf{x}|y')} &= \log \prod_{i=1}^N \Big[ \frac{p(x_i|y)}{p(x_i|y')} \Big]^{n p (x_i)} \\[6pt] &= \sum_{i=1}^N n p (x_i) \log \Big[ \frac{p(x_i|y)}{p(x_i|y')} \Big] \\[6pt] &= \sum_{i=1}^N h_i w_i. \\[6pt] \end{aligned}

Under this condition, we therefore obtain the posterior form:

\begin{aligned} p(y|\mathbf{x}) &= \text{logistic} \Bigg( \log \frac{p(\mathbf{x}|y)}{p(\mathbf{x}|y')} + \log \frac{p(y)}{p(y')} \Bigg) \\[6pt] &= \text{logistic} \Bigg( \sum_{i=1}^N h_i w_i + b \Bigg), \\[6pt] \end{aligned}

which is the form that the authors are using in their network. This is the model form postulated by the authors in the background section, prior to specifying Equations (1)-(2). The paper does not define $$n$$ is in this model setup, but as you point out, the answer by Prof Tishby says that this is the test sample size. In regard to your third question, it appears that the requirement of Equation (2) means that the values in $$\mathbf{x}$$ are not conditionally independent given $$y$$.

• Prof. Tishby (author) says, in his own answer, that $n$ is the test sample size. This is why I felt that eq (2) had a much richer interpretation than just an arbitrary condition to the linear form of the network. – IcannotFixThis Apr 7 '19 at 8:36
• Thanks - I have edited my answer to reflect this additional information. – Ben Apr 9 '19 at 22:26

For 1

$P(y \mid x) = \frac{P(y, x)}{P(x)}$

$= \frac{P(y,x)}{\sum_{i}P(y_{i},x)}$

Now as $y_{i}$ is binary, this becomes:

$= \frac{P(y,x)}{P(y,x)+P(y',x)}$

$= \frac{1}{1+\frac{P(y',x)}{P(y,x)}}$

$= \frac{1}{1+exp[-log \ \frac{P(y,x)}{P(y',x)}]}$

and from there its just the property of the logarithm to get to the final form (should be sufficiently clear by this point, let me know if not).