Statistical Verification of Linear Classifiers

Zhiyanov A.P. 1 , Shklyaev A.V. 2 , Galatenko A.V. 2 , Galatenko V.V. 2 and Tonevitksy A.G. 1,3,4 · 2025

Read Statistical Verification of Linear Classifiers by Zhiyanov A.P. 1 , Shklyaev A.V. 2 , Galatenko A.V. 2 , Galatenko V.V. 2 and Tonevitksy A.G. 1,3,4 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-14430.txt.

Introduction

Anton Zhiyanov and co-authors give in 2025 a stat test to tell if a line based sorter is real or just chance. The test ties to the old idea of line split between two groups. It asks if the sorter caught a true gap or drew a line through noise.

Bounds on the test's tail chance are set for two dim data. For bell shaped data, tests show the bound is tight in use. The team then runs the test on sorters built to flag breast cancer return from gene pairs. Two genes came out as firm marks in that check.

Catalog record

CREATORZhiyanov A.P. 1 , Shklyaev A.V. 2 , Galatenko A.V. 2 , Galatenko V.V. 2 and Tonevitksy A.G. 1,3,4
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE39 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-14430

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Statistical Verification of Linear Classifiers Zhiyanov A.P. 1 , Shklyaev A.V. 2 , Galatenko A.V. 2 , Galatenko V.V. 2 and Tonevitksy A.G. 1,3,4 Abstract . We propose a homogeneity test closely related to the concept of linear separability between two samples. Using the test one can answer the question whether a linear classifier is merely ‘‘random’’ or effectively captures differences between two classes. We focus on establishing upper bounds for the test’s p -value when applied to two-dimensional samples. Specifically, for normally distributed samples we experimentally demonstrate that the upper bound is highly accurate. Using this bound, we evaluate classifiers designed to detect ER-positive breast cancer recurrence based on gene pair expression. Our findings confirm significance of IGFBP6 and ELOVL5 genes in this process. Keywords: homogeneity test, linear classifier, k k -sets, linear separability. 1. Introduction Classification algorithms are widely used in biomedical applications to identify patterns and biological features that differentiate data across various classes [ 1 ] . For example, they can be applied to determine whether a patient has a particular disease based on gene expression profile (diagnostic test) [ 2 ] , or to separate patients into groups of high and low risk (prognostic test) [ 3 ] . The construction of a classifier involves two major steps: selecting a classification method and choosing a metric to evaluate the classifier’s performance [ 4 ] . In biological contexts, linear methods are particularly important. These classifiers are interpretable, because they assign each feature (e.g., gene expression) a corresponding significance (weight). Among classification metrics satisfying various natural conditions [ 5 ] , accuracy is considered the simplest and, at the same time, the most interpretable. Informally, it measures the proportion of correctly classified samples, providing a straightforward evaluation of classifier performance. In medical applications, many testing systems use a small number of genes to identify specific pathologies [ 6 , 7 , 8 ] . As a result, pairs of genes are often used as a starting point for building classifiers with a limited number of features [ 9 ] . From bioinformatics perspective, construction of such classifiers begins with analysis of expression matrices that include data for thousands of genes. Based on this matrix, one can identify one or several gene pairs minimizing the number of classification errors. However, an important question arises: does the resulting classifier truly capture the differences between classes, or does the observed (possibly small) number of errors result solely from testing a large number of gene pairs? We demonstrate that upper bounds on the probability of near-linear separability (i.e., separability with several errors) can be used to address this question in real-world scenarios, even in the presence of the multiple testing challenge. Furthermore, we connect this probability to the p -value of a corresponding homogeneity test, which reduces the question to a statistical hypothesis testing. The best classifiers are often tested on an independent testing set, if it is available. In this case, the issue of multiple testing does not arise, but another challenge frequently emerges: the small size of this testing set. We show that, in real world scenarios, even small testing sets can be sufficient to confirm statistical significance of classification ‘‘non-randomness’’. Formally, let Y=(Y_{i},\ i\leq k) , k\in\mathbb{N} , and Z=(Z_{i},\ i\leq l) , l\in\mathbb{N} , be two independent samples in \mathbb{R}^{d} , d\in\mathbb{N} . We assume that Y and Z consist of independent identically distributed (i.i.d.) random vectors (r.v.) distributed according to \mathcal{F}_{Y} and \mathcal{F}_{Z} , respectively. Denote by X=\{X_{i},\ i\leq n\} , n=k+l , the union of these samples. Suppose that Y and Z are linearly separable . In that case, it is natural to assume that \mathcal{F}_{Y}\neq\mathcal{F}_{Z} . But what is the probability of the event \mathcal{A}_{0} , where two samples are linearly separable under the assumption that their distributions are equal? Linear separability of gene expression datasets has been previously studied in [ 10 ] . The authors developed an algorithm that checks this property for any pair of genes in constant time on average. Also, they showed that the number of gene pairs which expression level linearly separates normal and tumor samples is significantly greater than expected. In comparison with [ 10 ] , we extend the problem of linear separability in several directions. We consider the more general event \mathcal{A}_{m} , which represents near-linear separability with m\in\mathbb{N} errors, and \mathcal{A}_{\leq m}=\bigcup_{h\leq m}\mathcal{A}_{h} which represents the separability with m errors or less. In the theoretical component, we derive upper bounds for \mathbf{P}\left(\mathcal{A}_{\leq m}\right) in the case d=2 using two approaches. In the first approach, we analyze \mathbf{P}\left(\left.\mathcal{A}_{\leq m}\,\right|X={S}\right) , where {S}=\{x_{i}\in\mathbb{R}^{2},\ i\leq n\} represents a set of all observations. Under the assumption \mathcal{F}_{Y}=\mathcal{F}_{Z} , all {\binom{n}{k}} possible partitions of {S} into Y and Z are equiprobable . Here, we derive upper bounds on \mathbf{P}\left(\left.\mathcal{A}_{\leq m}\,\right|X={S}\right) and construct the corresponding conditional test. This is particularly relevant for challenging settings (e.g., recurrence prediction), where even the best classifiers often fail to achieve perfect separability on non-trivial training and testing sets. Consequently, having p -value estimates for near-linear separability is essential for applying these estimates in practice. In the second approach, the upper bounds on integrated probability \mathbf{P}\left(\mathcal{A}_{\leq m}\right) are established and the corresponding integral test is built. While these bounds rely heavily on results from [ 11 , 12 , 13 , 14 , 15 ] , we introduce a novel statistical perspective on this problem. Furthemore, we propose a new upper bound on \mathbf{P}\left(\mathcal{A}_{\leq m}\right) for normally distributed samples, which are of particular interest in medical applications. This focus is justified by the observation that most genes exhibit normal or \log -normal expression level distributions [ 16 ] . In the computational component, we develop an enumerative algorithm to compute \mathbf{P}\left(\left.\mathcal{A}^{\prime}_{\leq m}\,\right|X={S}\right) and \mathbf{P}\left(\left.\mathcal{A}_{\leq m}\,\right|X={S}\right) for a given {S} . The event \mathcal{A}^{\prime}_{\leq m} differs from \mathcal{A}_{\leq m} as follows: while \mathcal{A}_{\leq m} controls the maximum number of misclassified points of both classes, \mathcal{A}^{\prime}_{\leq m} evaluates classifier accuracy, i.e., the total number of classification errors. Compared to the algorithm presented in [ 10 ] , our method addresses cases where m>0 and is applicable for multidimensional data, i.e., not only for d=2 , but also for d>2 . We experimentally validate the proposed methods on synthetic datasets and show the theoretical bounds to be tight in the normal case. Further, we apply the test to the classifiers developed in [ 9 ] for detecting breast cancer recurrence for ER-positive patients and confirm the critical role of ELOVL5 and IGFBP6 gene pair in the differentiation. 2. Results 2.1. Conditional bounds Let {S}=\{x_{i},\ i\leq n\} be a set of n>0 points in general position in \mathbb{R}^{2} . Consider a random partition of {S} into two disjoint subsets Y and Z of the given sizes k>0 and l=n-k>0 , where k\leq l . For a fixed {S} , these partitions are equiprobable and have probability 1/{\binom{n}{k}} . Definition 1 . The subsets Y and Z are called near-linearly seaparable with m errors if there exists a half-plane H^{+} such that \left\lvert H^{+}\cap Y\right\rvert=k-m_{Y} , \left\lvert H^{-}\cap Z\right\rvert=l-m_{Z} and \max(m_{Y},m_{Z})=m , where H^{-}=\mathbb{R}^{2}\setminus H^{+} . If m_{Y}+m_{Z}=m , we call the subsets nearly separable with accuracy m .

Read the complete text