Abstract
Standard probit regression is a fundamental tool for binary classification but suffers from fixed sensitivity to outliers and computational bottlenecks on massive datasets. This paper introduces the $p$-generalized probit model, which utilizes the Subbotin distribution to provide a tunable "robustness knob" via the parameter $p$. To enable scalability, we propose a "sketch-and-solve" framework that constructs $(1+\epsilon)$-accurate coresets using $\ell_p$-leverage scores. Experimental results on large-scale benchmarks demonstrate that our approach achieves significant data reduction while maintaining high predictive accuracy.
Introduction
In binary classification, the probit model assumes that the probability of a positive response is determined by the Cumulative Distribution Function (CDF) of a standard normal distribution. While widely used, this model lacks flexibility; its fixed tail behavior makes it sensitive to outliers in ways that may not suit all datasets. Furthermore, as data volumes reach millions of instances, traditional Maximum Likelihood Estimation (MLE) becomes computationally prohibitive due to the need for multiple passes over the entire dataset during optimization.
This work addresses these challenges by generalizing the link function and providing a scalable estimation framework based on coresets—weighted subsets of data that approximate the full loss function with provable guarantees.
The $p$-Generalized Probit Model
The core innovation is the replacement of the standard normal CDF with the CDF of the $p$-generalized normal (Subbotin) distribution. By varying the shape parameter $p$, researchers can control the distribution's tails and peak:
- $p=1$: Corresponds to the Laplace distribution, providing heavy tails and increased robustness to outliers.
- $p=2$: Recovers the standard probit model.
- $p \to \infty$: Approaches a uniform distribution, making the model highly sensitive to extreme values.
This flexibility allows the model to act as a "robustness slider," adapting to the specific noise characteristics of the underlying data.
Scalable Estimation via Sketching and Coresets
To handle massive datasets, we employ a two-pass "sketch-and-solve" algorithm to build a coreset. The primary challenge in coreset construction for non-linear models is determining the "sensitivity" or importance of each data point without first solving the optimization problem.
Our framework bridges classification loss functions with numerical linear algebra by approximating $\ell_p$-leverage scores. The process involves:
- Sketching: Using fast random projections to estimate leverage scores in a single pass.
- Sampling: Constructing a small, weighted coreset based on these scores.
- Solving: Performing MLE optimization on the coreset, which is significantly smaller than the original dataset.
This approach provides a $(1+\epsilon)$ approximation guarantee and operates in nearly input-sparsity time, making it suitable for web-scale data.
Experimental Evaluation
We evaluated the $p$-generalized probit model and the coreset framework on several large-scale benchmarks, including Webspam (350k instances), Covertype (581k instances), and Kddcup (494k instances).
Key findings include:
- Decision Boundary Sensitivity: As shown in the synthetic 2D example, changing $p$ significantly shifts the decision boundary, allowing for better alignment with data clusters and handling of outliers.
- Data Reduction: The coreset algorithm maintained an approximation ratio near 1.0 even when reducing data by 90-99%.
- Robustness: On the Kddcup dataset, the $p=1$ model (robust) outperformed standard probit and logit models by effectively ignoring influential outliers.
Conclusion
The $p$-generalized probit model offers a principled way to tune model robustness in binary classification. By combining this flexible model with a scalable coreset framework, we provide a solution that is both statistically versatile and computationally efficient for the big data era. Future work includes exploring asymmetric distributions and further optimizing the sketching process for very high values of $p$.
Summary updated