From RKHS Scores to Binary Classification Risk

From a Score to a Classification Decision

A kernel method can produce a real-valued function, but a binary decision requires a label. The conversion is simple away from zero: positive scores predict the positive class and negative scores predict the negative class. At zero, however, the score alone does not specify a label. That convention is part of the classifier, and it can change its population error.

Let $(\mathcal X,\mathcal A)$ be a measurable input space and let $Y\in\{-1,+1\}$ be the label. Suppose $(X,Y)$ has a fixed population distribution. Let $k$ be a real-valued positive definite kernel on $\mathcal X$, with reproducing kernel Hilbert space $\mathcal H$. We consider measurable functions $f\in\mathcal H$; such a function is a real-valued score. The reproducing property is $f(x)=\langle f,k(\cdot,x)\rangle_{\mathcal H}$.

Definition: Given a measurable score $f:\mathcal X\to\mathbb R$, its positive-tie sign classifier is $$ g_f^+(x)= \begin{cases} +1,& f(x)\geq 0,\\ -1,& f(x)<0. \end{cases} $$ Its negative-tie sign classifier is $g_f^-(x)=+1$ when $f(x)>0$, and $g_f^-(x)=-1$ when $f(x)\leq 0$. Thus the two rules differ only on $\{x:f(x)=0\}$.

Both conventions are deterministic and measurable when $f$ is measurable. More generally, a classification rule can specify a label at a tie by a measurable function taking values in $\{-1,+1\}$. Unless a tie rule is stated, the phrase “classify by the sign of $f$” is incomplete whenever $f$ can equal zero.

Population Zero-One Risk

The population zero-one risk is the probability that the classifier disagrees with a new label drawn from the population distribution. It depends on the joint distribution of $X$ and $Y$, not just on the score or on the RKHS.

Definition: For a measurable classifier $g:\mathcal X\to\{-1,+1\}$, its population zero-one risk is $$ R(g)=P\{g(X)\ne Y\}=E[\mathbf 1\{g(X)\ne Y\}]. $$ For a score $f$ and a chosen tie convention, write $R(g_f)$ for the risk of its induced classifier.

To see how the tie convention enters, let $\eta(x)=P(Y=+1\mid X=x)$ be a measurable version of the conditional class probability. Conditional probabilities are understood up to sets of $X$-probability zero, which is sufficient for the expectations below. Given $X=x$, predicting $+1$ has error probability $1-\eta(x)$; predicting $-1$ has error probability $\eta(x)$.

Result: For any measurable classifier $g$, $$ R(g)=E\!\left[(1-\eta(X))\mathbf 1\{g(X)=+1\} +\eta(X)\mathbf 1\{g(X)=-1\}\right]. $$ In particular, on a score tie $f(x)=0$, the conditional error is $1-\eta(x)$ under the positive-tie rule and $\eta(x)$ under the negative-tie rule.

Derivation. Condition on $X$. If $g(X)=+1$, an error occurs exactly when $Y=-1$, whose conditional probability is $1-\eta(X)$. If $g(X)=-1$, an error occurs exactly when $Y=+1$, whose conditional probability is $\eta(X)$. These two cases are disjoint and exhaustive, so the conditional error is the expression inside the expectation. Taking expectations gives the result. On a tie, the two rules choose opposite labels, giving the stated conditional errors. $\square$

Worked Example: The Cost of a Tie Convention

Suppose $X$ takes values $a$ and $b$, with $P(X=a)=0.4$ and $P(X=b)=0.6$. Let $P(Y=+1\mid X=a)=0.3$ and $P(Y=+1\mid X=b)=0.8$. A score has $f(a)=0$ and $f(b)=-2$. Calculate the risk under both tie conventions.

At $a$, the positive-tie rule predicts $+1$, so its conditional error is $1-0.3=0.7$. At $b$, both rules predict $-1$, so the conditional error is $0.8$. Therefore, $$ R(g_f^+)=0.4(0.7)+0.6(0.8)=0.28+0.48=0.76. $$

Under the negative-tie rule, the prediction at $a$ is $-1$, with conditional error $0.3$; the error at $b$ remains $0.8$. Thus $$ R(g_f^-)=0.4(0.3)+0.6(0.8)=0.12+0.48=0.60. $$ The difference is $0.76-0.60=0.16$, entirely due to the tie at $a$. Because the positive class has conditional probability $0.3$ there, predicting negative is preferable.

Bayes Risk and an Excess-Risk Identity

At each input $x$, the lower-error label is $+1$ when $\eta(x)\geq 1/2$ and $-1$ when $\eta(x)<1/2$. Choosing $+1$ at equality is a convention; either label has the same conditional error when $\eta(x)=1/2$. A Bayes classifier is a measurable rule that makes this pointwise choice, and its risk is the Bayes risk.

Theorem: Define $g^*(x)=+1$ if $\eta(x)\geq 1/2$, and $g^*(x)=-1$ otherwise. For any measurable classifier $g$, $$ R(g)-R(g^*)=E\!\left[|2\eta(X)-1|\mathbf 1\{g(X)\ne g^*(X)\}\right]. $$ Consequently, $g^*$ minimizes population zero-one risk. The result does not depend on how $g^*$ is defined when $\eta(x)=1/2$.

Proof. Fix $x$ and compare the conditional error probabilities. If $\eta(x)>1/2$, the choice $g^*(x)=+1$ has error $1-\eta(x)$, while choosing $-1$ has error $\eta(x)$. The excess conditional error from choosing the opposite label is $$ \eta(x)-(1-\eta(x))=2\eta(x)-1=|2\eta(x)-1|. $$ If $\eta(x)<1/2$, the Bayes choice is $-1$. Choosing $+1$ instead adds $$ (1-\eta(x))-\eta(x)=1-2\eta(x)=|2\eta(x)-1|. $$ If $\eta(x)=1/2$, both labels have conditional error $1/2$, so their difference is zero. Thus, in every case, the conditional excess error equals $|2\eta(x)-1|\mathbf 1\{g(x)\ne g^*(x)\}$. Taking expectations proves the identity. Its right-hand side is nonnegative, so $R(g)\geq R(g^*)$ for every measurable $g$. $\square$

The identity clarifies the role of a tie in the score: a score tie is not necessarily a population tie. If $f(x)=0$ but $\eta(x)\ne 1/2$, one label has strictly smaller conditional error. In contrast, when $\eta(x)=1/2$, choosing either label is equally good at that input.

Population Surrogate Risk

Many learning procedures assess a score through a loss that depends on its signed margin $Yf(X)$. A positive margin means the score has the sign of the label; a negative margin means it has the opposite sign. The loss assigns a numerical cost to that margin, and its population expectation is the surrogate risk.

Definition: Let $\phi:\mathbb R\to[0,\infty]$ be measurable. The population surrogate risk of a measurable score $f$ is $$ R_\phi(f)=E[\phi(Yf(X))]. $$ This expectation is defined as a nonnegative extended expectation and may be infinite. If $\phi$ is not nonnegative, its expectation requires the usual integrability conditions; in this tutorial, surrogate losses are taken to be nonnegative.

For example, the hinge loss is $\phi(u)=\max(0,1-u)$, and the logistic loss is $\phi(u)=\log(1+e^{-u})$. These losses produce numerical risks, not probabilities of classification error. The zero-one risk of $g_f$ depends only on which side of zero the score lies (and on the tie convention); the surrogate risk can also change when the magnitude of a score changes.

Worked Example: Comparing Hinge and Zero-One Risk at a Tie

Let $X$ be constant, with $P(Y=+1)=0.7$ and $P(Y=-1)=0.3$, and let the score be $f(X)=0$. Under the positive-tie rule the classifier always predicts $+1$. Its zero-one risk is the probability of $Y=-1$, namely $0.3$. Under the negative-tie rule the risk is $0.7$.

For hinge loss, both possible labels give margin $Yf(X)=0$, so each has loss $$ \phi(0)=\max(0,1-0)=1. $$ Consequently, $R_\phi(f)=0.7(1)+0.3(1)=1$. This is not a misclassification probability: it is a loss expectation, and here it equals 1 even though the positive-tie classifier's error probability is 0.3. The surrogate risk also does not change when we switch the classifier's tie convention, because the score and labels in $Yf(X)$ have not changed.

Worked Example: Calculating Both Risks on a Finite Input Space

Take $\mathcal X=\{1,2,3\}$ with kernel $k(i,j)=\mathbf 1\{i=j\}$. Its RKHS consists of all real-valued functions on these three points, with inner product $\langle f,h\rangle=\sum_{i=1}^3 f(i)h(i)$. Indeed, $k(\cdot,j)$ is the coordinate vector that is 1 at $j$ and 0 elsewhere, so $\langle f,k(\cdot,j)\rangle=f(j)$. Consider the RKHS score $f(1)=1,\ f(2)=0,\ f(3)=-1$.

Let $P(X=1)=0.2,\ P(X=2)=0.5,\ P(X=3)=0.3$, and let the conditional probabilities of $Y=+1$ at these points be $0.9,\ 0.4,\ 0.1$, respectively. The positive-tie classifier predicts $+1,+1,-1$. Its conditional errors are $0.1,0.6,0.1$, giving $$ R(g_f^+)=0.2(0.1)+0.5(0.6)+0.3(0.1)=0.02+0.30+0.03=0.35. $$

For the hinge surrogate, at point 1 the positive label has margin $1$ and loss $0$, while the negative label has margin $-1$ and loss $2$. Its conditional expected loss is $0.9(0)+0.1(2)=0.2$. At point 2 the score is zero, so both labels have loss $1$, giving conditional expected loss $1$. At point 3 the positive label has margin $-1$ and loss $2$, while the negative label has margin $1$ and loss $0$; the conditional expected loss is $0.1(2)+0.9(0)=0.2$. Therefore, $$ R_\phi(f)=0.2(0.2)+0.5(1)+0.3(0.2)=0.04+0.50+0.06=0.60. $$ The calculations use the full label distribution at each input; the score by itself does not determine either population risk.

Why the Distinction Matters

The score, the classifier, and the risks are related but distinct objects. The score belongs to $\mathcal H$ and retains magnitude information. A specified tie convention turns it into a classifier. The zero-one risk measures the probability of a wrong label, while a surrogate risk averages a chosen loss of the signed margin. Keeping these objects separate prevents ambiguity when interpreting a kernel method.

A frequent mistake is to say that a score of zero predicts both classes with equal probability, or that it has zero classification error. Neither statement follows from the score. A deterministic sign rule must assign a label at zero, and its error there depends on $P(Y=+1\mid X=x)$. A different mistake is to treat $R_\phi(f)$ as a probability because it is called a risk. For hinge loss it can exceed 1, and for other losses it has the scale and meaning of that loss, not of a misclassification probability.

The practical discipline is to state the tie rule, name the risk being evaluated, and use the population distribution when calculating it. These definitions provide the foundation for later analysis of how surrogate losses relate to classification performance; no such relationship is automatic from the definitions alone.

Check Your Understanding

Use the definitions and derivations above to answer the following.

For a score $f(x)=0$, what labels do the positive-tie and negative-tie rules predict?
If $P(Y=+1\mid X=x)=0.2$ at a tied point, calculate the conditional error under each tie convention.
State the excess-risk identity and explain why its right-hand side is zero wherever $\eta(X)=1/2$.
For hinge loss, what is the loss when the signed margin is zero? Why does this not determine the classifier's zero-one error by itself?
Why can two classifiers induced by the same score have different zero-one risks but the same surrogate risk?