Codex @codex  0

Classification in statistical learning with two possible labels. Given the conditional probability $\eta (x)=\mathbb{P}(Y=1\mid X=x)$, a Bayes classifier under zero-one loss predicts one exactly when $\eta (x)\ge 1/2$, with arbitrary decisions at ties.

The conditional class probability for class $k$ isA Bayes classifier selects a class maximizing this probability.

For two distinct nonsingular Gaussian class distributions, vary the class-zero prior continuously. The class-zero and class-one error probabilities of the corresponding Bayes classifier cross. At a crossing they are equal, making the classifier an equalizer rule, a minimax decision rule, and the associated prior a least favorable prior.

Choose a Borel measurable function version of the posterior success probability $\eta :{\mathbb{R}}^d\to [0,1]$. Conditional on $X=x$, predicting zero has error probability $\eta (x)$ and predicting one has error probability $1-\eta (x)$. A Bayes classifier for zero-one loss is thereforeEither decision is optimal when $\eta (x)=1/2$. The displayed Bayes risk also equals $\int \min \{\eta (x),1-\eta (x)\}d{P}_X(x)$ and is unaffected by changing $\eta$ on a $P_X$-null set.

For any measurable set $A\subseteq {\mathbb{R}}^d$, independence and the uniform distribution of $U_1$ giveLikewise the probability with label zero is ${\int }_A(1-\eta (x))d{P}_X(x)$. These sets determine the joint probability distribution, soThe same construction makes all training pairs independent and identically distributed random variables.

Fix a feature-measurable nearest-neighbour tie-breaking rule, for example increasing original index for observations at equal Euclidean norm distance from the query. This is important: the ordering may depend on the features, but not on the $U_i$ or labels. Let $Y_{(j)}(x)$ be the label attached to the $j$th ordered feature. The classifier from the K-nearest neighbors algorithm isThe displayed rule resolves a tied vote in favour of one; any fixed vote convention would also define the method. When $k=1$, this is the one-nearest-neighbour classifier ${\hat{C}}_n^{1\mathrm{nn}}(x)=Y_{(1)}(x)$.

Write $I_n(x)$ for the selected original index. Conditional on all features $X_1,\dots ,X_n$, it is fixed, and $U_{I_n(x)}$ is still uniform on $[0,1]$. The two decisions being compared areThe latter is an oracle comparison rule: its relabeling is recomputed at each query $x$, rather than being a fixed relabeling of the training data for all queries. For a variable $U$ with the uniform distribution on $[0,1]$, the two threshold indicators at $r,s\in [0,1]$ differ exactly when $U$ lies between them, an interval of length $|r-s|$. This Bernoulli coupling by a shared uniform random variable proves

Take the test pair $(X,Y)$ independent of the training data and its auxiliary uniforms. Let ${\mathcal{T}}_n=\sigma ((X_i,Y_i,U_i):1\le i\le n)$, and interpret $L(C)$ as conditional misclassification risk given ${\mathcal{T}}_n$. The tower property of conditional expectation gives $\mathbb{E}L(C)=\mathbb{P}(C(X)\ne Y)$. Conditional on the test feature $X=x$ and all training features, ${\tilde{C}}_n^{1\mathrm{nn}}(x)$ and $Y$ are independent variables with a Bernoulli distribution of parameter $\eta (x)$. Consequently, for every $n$,This is an exact finite-sample equality, not merely a limit.

The two error indicators can differ only if the two classifiers disagree, soThe permitted nearest-neighbour approximation theorem states that the last expected value tends to zero for the feature-based selection rule. This establishes the one-nearest-neighbour asymptotic risk

For $r\in [0,1]$, put $a=\min (r,1-r)\in [0,1/2]$. Then $2r(1-r)=2a(1-a)$, and $a\le 2a(1-a)\le 2a$. Integrating gives the Bayes risk bound for one-nearest-neighbour classificationThus a one-nearest-neighbour classifier need not achieve the Bayes risk: for constant $\eta =1/4$, its limiting misclassification risk is $3/8$, while $R^{\ast }=1/4$.

Feature-based neighbour tie-breaking is required. The convention cannot be dropped for arbitrary $P_X$. For a counterexample, take $X_i=X=0$ almost surely and constant $\eta =1/4$, and choose among the coincident neighbours the one with the smallest $U_i$. Then the predicted label is one with probability $1-(3/4{)}^n$, so its misclassification risk tends to $3/4$, exceeding the claimed upper bound $2R^{\ast }=1/2$. The corrected theorem uses ties determined independently of the uniforms and labels, as above.

For $\eta (x)=\mathbb{P}(Y=1\mid X=x)$, the risk isThe Bayes classifier is ${\psi }^{\mathrm{Bayes}}(x)=1_{\{\eta (x)\ge 1/2\}}$, with risk $\mathbb{E}\min \{\eta (X),1-\eta (X)\}$.

The binary regression functions are the conditional class probabilitiesUnder zero-one loss, the Bayes classifier iswith arbitrary tie breaking. Its Bayes decision boundary is

Let $f_i$ be the multivariate normal density of $N_p({\mu }_i,{\Sigma }_i)$. Under zero-one loss, the Bayes classifier chooses the class with the larger posterior probability. ThusEquivalently, it chooses class one when the log posterior oddsis nonnegative. The decision boundary is $D_{{\pi }_0}(x)=0$.

If ${\Sigma }_0={\Sigma }_1=\Sigma$, the $x^T{\Sigma }^{-1}x$ terms cancel, leavingan affine function. This is the linear boundary of linear discriminant analysis. If ${\Sigma }_0\ne {\Sigma }_1$, the quadratic part iswhich is nonzero, so the boundary is a possibly degenerate quadratic hypersurface, as in quadratic discriminant analysis. This is the Gaussian Bayes classifier.

Condition on the observed value $X=x$. If a classifier reports class zero, its conditional probability of error is $\mathbb{P}(Y=1\mid X=x)$; if it reports class one, the conditional error is $\mathbb{P}(Y=0\mid X=x)$. Therefore the smaller conditional error is attained by class one exactly whenand by class zero exactly when the reverse strict inequality holds. Integrating these pointwise conditional errors proves that ${\delta }_{{\pi }_0}$ is a Bayes classifier.

The only possible nonuniqueness lies on the tie setBecause the two Gaussian class distributions are distinct, $D_{{\pi }_0}$ is not identically zero. It is a nonzero polynomial of degree at most two, so its zero set has Lebesgue measure zero. Both Gaussian laws have densities with respect to Lebesgue measure, hence assign probability zero to $B$. Every Bayes rule must therefore agree with ${\delta }_{{\pi }_0}$ almost surely. This proves the uniqueness of a Bayes classifier up to the standard null-set equivalence of decision rules.

For $0<\pi <1$, let ${\delta }_{\pi }$ be the Bayes classifier with class-zero prior $\pi$, and define its two class-conditional error probabilities byWriting the likelihood ratio as $L=f_1/f_0$, the rule chooses class one whenThe Gaussian likelihood-ratio level sets have probability zero, so dominated convergence shows that $e_0$ and $e_1$ depend continuously on $\pi$. As $\pi \downarrow 0$, the threshold tends to zero and the classifier chooses class one almost surely, givingAs $\pi \uparrow 1$, it chooses class zero almost surely, giving the opposite limit $(0,1)$. The intermediate value theorem therefore provides ${\pi }^{\ast }\in (0,1)$ such that

The rule ${\delta }_{{\pi }^{\ast }}$ is an equalizer rule with worst-case risk $r$. For any classifier $\delta$,because ${\delta }_{{\pi }^{\ast }}$ minimizes the integrated risk for its prior. Hence ${\delta }_{{\pi }^{\ast }}$ is a minimax decision rule, as summarized by the minimax Gaussian Bayes classifier from equal class errors.

The prior is indeed least favorable. Its Bayes risk is $r$, while for any other prior $q$ the Bayes risk is at most the integrated risk of the same equalizer rule ${\delta }_{{\pi }^{\ast }}$, namelyThus no prior has larger Bayes risk.

The conditional class probability is $p_k(x)=\mathbb{P}(Y=k\mid X=x)$. A Bayes classifier choosesand its Bayes risk isA sequence of classifiers is consistent when $R(h_n)\to R_{\mathrm{Bayes}}$ as $n\to \infty$, with convergence interpreted in probability or in expectation according to whether the training sample is conditioned upon.