Como se señaló en la pregunta y comentarios, un conjunto de datos de $m$ $(\boldsymbol{x}_i,y_i)$ $\boldsymbol{x}_i\in\mathbb{R}^n$ $y_i\in\{-1,+1\}$ es linealmente separable si podemos encontrar un vector normal a $\boldsymbol{a}$ y escalar sesgo $b$ de manera tal que la desigualdad lineal
$$y_i(\boldsymbol{a}^T\boldsymbol{x}_i+b)\geq 1$$
se satisface para todos los $i=1,\ldots,m$. Físicamente esto se dice que por cada punto de $\boldsymbol{x}_i$, el firmado distancia $d_i$ a de la separación de avión tiene que firmar $y_i$ y la magnitud de al menos $\|\boldsymbol{a}\|$.
Esto se puede escribir también como
$$\boldsymbol{w}^T\boldsymbol{z}_i \geq 1$$
donde
$$\boldsymbol{z}_i = \begin{bmatrix}\boldsymbol{x}_i \\ 1\end{bmatrix} y_i
\text{ , } \boldsymbol{w}=\begin{bmatrix}\boldsymbol{a} \\ b\end{bmatrix}$$
Como se señaló en la pregunta, esto es, esencialmente, un problema de programación lineal con un "0" de la función objetivo.
La propuesta de "grados de separación" medida $S_\min$ puede ser expresado como
$$ \min_{\boldsymbol{\sigma},\boldsymbol{w}} S[\boldsymbol{\sigma}] $$
donde $\boldsymbol{\sigma}\in\{0,1\}^m$, la función de $S$ está definido por
$$ S[\boldsymbol{\sigma}] = \sum_i\sigma_i = \boldsymbol{1}^T\boldsymbol{\sigma} $$
y la minimización está sujeta a la restricción
$$ \sigma_i(\boldsymbol{w}^T\boldsymbol{z}_i - 1) \geq 0 \text{ , } i=1,\ldots,m$$
Esta es una (ligeramente no lineal) "programación entera mixta" problema, un problema de la clase NP duro (incluso en el lineal y binario caso).
Ahora de una manera más viable alternativa podría ser la de resolver un "soft-margen" problema de clasificación utilizando un enfoque estándar como SVM*. La tolerancia y/o multiplicador de lagrange variables podría entonces ser utilizado para cuantificar la "grados de separación".
(*Por $\lambda\approx 0$ la SVM en esencia se reducen a un "suavizado" la versión de la programación lineal anterior. Sin embargo, para obtener significativas distancias, se tiene que normalizar las tolerancias por $\|\boldsymbol{a}\|$.)
Actualización: el Uso de algo como suave al margen de la SVM puede dar una idea de los puntos que están "duro" para separar, pero no necesariamente responden a su pregunta de "¿cuántos puntos debe ser eliminado para permitir un duro margen de división?"
Sin embargo, creo que, si se pre-proceso de la $\boldsymbol{X}$ matriz por el blanqueamiento, entonces debe ser posible obtener algunos resultados más consistentes. (En términos numéricos offset-escalas y direccional de la agrupación de los puntos problemáticos.)
