# Probability of linear separation in a dataset with categorical response

I am simulating datasets to which I fit polytomous logistic regression models. The maximum likelihood estimator of this model is undefined when all categories are linearly separated (and it is quite unstable when there are "close" to be) from all others. My question is: what is the probability of this happening ? It clearly increases with the dimension of explanatory variables and decreases with the number of data points. Is there any known result on that ?

More formally, let $$x_1, ..., x_n$$ be $$n$$ i.i.d. realizations of a random variable $$X \in \mathbb{R} ^ p$$ following a distribution $$F_X$$, and $$Y_1, ..., Y_n$$ be n categorical responses among $$\{1, ..., K\}$$ following multinomial distribution with logistic link (including an intercept) to $$x_1, ..., x_n$$, i.e. such that $$P(Y_i = k) = \frac{e^{\alpha_k + {\beta_k}^T x_i}}{1 + \sum_{j = 1}^{K-1} e^{\alpha_j + \beta_j^T x_i}}$$ for $$k \in \{1..K-1\}$$ and $$P(Y = K) = \frac{1}{1 + \sum_{j = 1}^{K-1} e^{\alpha_j + \beta_j ^T x_i}}$$.

What is the probability that there exist $$K$$ lines $$l_1, ..., l_K$$ such that $$l_k$$ separates $$\{x_i : Y_i = k\}$$ from $$\{x_i : Y_i \neq k\}$$ ?

Any asymptotic equivalent would already be of great use.

For simplicity, $$X$$ can be assumed to be $$\mathcal{N}(0, I_p)$$ or can be supposed fixed.

First of all, for more than one class, the estimator is stable unless you add the intercepts to your model (one for each class other than baseline), so $$P(Y_i = k) = \frac{e^{{\beta_k} x_i}}{1 + \sum_{j = 1}^{K-1} e^{\eta_{ji}}}$$ where $$\eta_{ji} = \beta_{0j} + \beta_{ji} \cdot x_i$$ if $$x$$ is univariate. Note that I also had to introduce another index $$j$$ to distinguish it from $$i$$, that ranges over the observations instead.

Also, another point is that, for the estimation to diverge, you need at least one category to be linearly separable from all the others, not all of them being linearly separable from each other. For instance, a multilogit won't converge in Iris dataset even if versicolor and virginica species are not separable, that's because there is setosa, which is.

I am not sure about what answer are you looking for, but the exact one depends on a set of $$(K-1)(m+1)$$ postulated parameters, where $$m$$ is the number of predictors, as well as the distribution of $$X$$ and on the total number of observations of course. Given these, you can estimate the probability that any of the classes is linearly separated from all the others put together. That's the probability that the model estimation won't converge.

By the way, I'm not saying that given all this information the computation will be easy, but without it, it is clearly impossible.

Take this simple example, which doesn't even include information on the number of sample $$n$$ or on the steepness of the slopes:

Of course, the steepier are the slopes, the likelier is that your data will show linearly separable categories, but it is also clear from this example that the distribution of $$X$$ also plays a crucial role: here we can reasonably expect category $$y_1$$ to be separable because it has good probability of being observed just on a little proportion of the sample, quite set aside from the other data points.

• Thanks for your answer. Indeed, this probability will depend on the distribution of $X$, your example makes it clear. Sorry for the unprecise question (I edited it a bit). I am indeed considering model with an intercept and multivariate $X$. I am looking for a formula, an approximation, a bound, or any result on the probability of a linear separation happening. May 26, 2020 at 16:45
• Would you have any reference explaining why a linear separation between one category and all the others is sufficient to get non finite estimate ? From this paper : "On the existence of maximum likelihood estimatesin logistic regression models" Albert & Anderson, 1984, I understood (maybe wrongly) that a separation between all pairs of categories is necessary. May 26, 2020 at 16:49
• I did look for references, but the ones I found are vague, and so it's yours. Anyway you can try a model implementation on Iris dataset and see by yourself. Odds ratios between between setosa and other groups diverge for the variables that make the separation possible. May 26, 2020 at 17:32
• In any case, X distribution (whatever random or fixed) is a factor, but so they are the parameters of the data generating model. May 26, 2020 at 17:34
• Yes you are absolutely right, this probability depends on both distribution of $X$ and model parmeters. Still, I am more interested of the dependancy of this probability on number of datapoints $n$ and the covariate dimension $p$. May 26, 2020 at 19:06