Understanding complete separation for logistic regression 
*

*Why does logistic regression not converge for a linearly separable data set?


For linear separable data sets the model parameters go to infinity when mimizing the error function (according to Bishop2006, Pattern recognition and machine learning, section 4.3.2). I don't understand why. It must be connected to setting the score function, i.e. the derivative of the error function, to zero.
The error function is given by $E(\mathbf{w})$ as shown in the figure below. Where $\mathbf{t}$ is the target variable vector of the training set and $\mathbf{w}$ the parameter / coefficient vector. The posterior probabiltiy for class 1 is given by 
$$y(n) = p(C_1|\mathbf{x}_n) = \sigma(\mathbf{w}'\mathbf{x}_n).$$ Where sigma is the logistic sigmoid function and $\mathbf{x}_n$ is the feature vector for instance $n$ including the predictors.



*My second question to logistic regression is if the to posterior probabilities $p(C_1|\mathbf{x}_n)$ and $p(C_2|\mathbf{x}_n)$ sum to one?

 A: Here's a visual explanation of (1)

Imagine that you have a perfectly separated set of points, with the separation occuring at zero in the picture (so a clump of $y=0$s to the left of zero and a clump of $y=1$s to the right).
The sequence of curves I plotted is
$$\frac{1}{1 + e^{-x}}, \frac{1}{1 + e^{-2x}}, \frac{1}{1 + e^{-3x}}, \ldots $$
so I'm just increasing the coefficient without bound.
Which of the 20 curves would you choose?  Each one hewes ever closer to our imagined data.  Would you keep going on to
$$\frac{1}{1 + e^{-21x}}$$
When would you stop?
For (2), yes.  This is essentially by definition, you've implicitly assumed this in the construction of the binomial likelihood(*)
$$ L = \sum_i t_i \log(p_i) + (1 - t_i) \log(1 - p_i) $$
In each term in the summation only one of $t_i \log(p_i)$ or $(1 - t_i) \log(1 - p_i)$ is non-zero, with a contribution of $p_i$ for $t_i = 1$ and $1 - p_i$ for $t_i = 0$.

Why is there no convergence mathematically?

Here's a (more) formal mathematical proof.
First some setup and notations.  Let's write
$$ S(\beta, x) = \frac{1}{1 + \exp(- \beta x)} $$
for the sigmoid function.  We will need the two properties
$$ \lim_{\beta \rightarrow \infty} S(\beta, x) = 0 \ \text{for} \ x < 0 $$
$$ \lim_{\beta \rightarrow \infty} S(\beta, x) = 1 \ \text{for} \ x > 0 $$
with each approaching the limit monotonically, the first limit is decreasing, the second is increasing.  Each of these follows easily from the formula for $S$.
Let's also arrange things so that

*

*Our data is centered, this allows us to ignore the intercept as it is zero.

*The vertical line $x = 0$ separates our two classes.

Now, the function that we are maximizing in logistic regression is
$$ L(\beta) = \sum_i y_i \log(S(\beta, x_i)) + (1 - y_i) \log(1 - S(\beta, x_i)) $$
This summation has two types of terms.  Terms in which $y_i = 0$, look like $\log(1 - S(\beta, x_i))$, and because of the perfect separation we know that for these terms $x_i < 0$.  By the first limit above, this means that
$$ \lim_{\beta \rightarrow \infty} S(\beta, x_i) = 0$$
for every $x_i$ associated with a $y_i = 0$.  Then, after applying the logarithm, we get the monotonic increasing limit towards zero:
$$ \lim_{\beta \rightarrow \infty} \log(1 - S(\beta, x_i)) = 0$$
You can easily use the same ideas to show that for the other type of terms
$$ \lim_{\beta \rightarrow \infty} \log(S(\beta, x_i)) = 0$$
again, the limit is a monotone increase.
So no matter what $\beta$ is, you can always drive the objective function upwards by increasing $\beta$ towards infinity.  So the objective function has no maximum, and attempting to find one iteratively will just increase $\beta$ forever.
It's worth noting where we used the separation.  If we could not find a separator then we could not partition the terms into two groups, we would instead have four types

*

*Terms with $y_i = 0$ and $x_i > 0$

*Terms with $y_i = 0$ and $x_i < 0$

*Terms with $y_i = 1$ and $x_i > 0$

*Terms with $y_i = 1$ and $x_i < 0$
In this case, when $\beta$ gets very large the terms with $y_i = 1$ and $x_i < 0$ will drive $\log(S(\beta, x_i))$ to negative infinity. When $\beta$ gets very large, the $y_i = 0$ and $x_i < 0$ will do the same to the corresponding $\log(1 - S(\beta, x_i))$.  So somewhere in the middle, there must be a maximum.
(*) I replaced your $y_i$ with $p_i$ because the number is a probability, and calling it $p_i$ makes it easier to reason about the situation.
