Probability of linear separation in a dataset with categorical response

Question

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.

Answer 1

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.