3
$\begingroup$

I am currently studying the textbook Learning with kernels: support vector machines, regularization, optimization and beyond by Schölkopf and Smola. Chapter 1.2 A Simple Pattern Recognition Algorithm says the following:

We are now in the position to describe a pattern recognition learning algorithm that is arguably one of the simplest possible. We make use of the structure introduced in the previous section; that is, we assume that our data are embedded into a dot product space $\mathcal{H}$. Using the dot product, we can measure distances in this space. The basic idea of the algorithm is to assign a previously unseen pattern to the class with closer mean.
We thus begin by computing the means of the two classes in feature space; $$\mathbf{c}_+ = \dfrac{1}{m_+} \sum_{\{i \vert y_i = +1\}} \mathbf{x}_i, \tag{1.7}$$ $$\mathbf{c}_- = \dfrac{1}{m_-} \sum_{\{i \vert y_i = -1\}} \mathbf{x}_i, \tag{1.8}$$ where $m_+$ and $m_-$ are the number of examples with positive and negative labels, respectively. We assume that both classes are non-empty, thus $m_+, m_- > 0$. We assign a new point $\mathbf{x}$ to the class whose mean is closest (Figure 1.1). This geometric construction can be formulated in terms of the dot product $\langle \cdot, \cdot \rangle$. Half way between $\mathbf{c}_+$ and $\mathbf{c}_-$ lies the point $\mathbf{c} := (\mathbf{c}_+ + \mathbf{c}_-)/2$. We compute the class of $\mathbf{x}$ by checking whether the vector $\mathbf{x} - \mathbf{c}$ connecting $\mathbf{c}$ to $\mathbf{x}$ encloses an angle smaller than $\pi / 2$ with the vector $\mathbf{w} := \mathbf{c}_+ - \mathbf{c}_-$ connecting the class means. This leads to $$\begin{align} y &= \text{sgn} \langle (\mathbf{x} - \mathbf{c}), \mathbf{w} \rangle \\ &= \text{sgn} \langle ( \mathbf{x} - ( \mathbf{c}_+ + \mathbf{c}_- ) / 2), ( \mathbf{c}_+ - \mathbf{c}_- ) \rangle \\ &= \text{sgn}( \langle \mathbf{x}, \mathbf{c}_+ \rangle - \langle \mathbf{x}, \mathbf{c}_- \rangle + b). \tag{1.9} \end{align}$$ Here, we have defined the offset $$b := \dfrac{1}{2} ( \left| \right| \mathbf{c}_- \left| \right|^2 - \left| \right| \mathbf{c}_+ \left| \right|^2), \tag{1.10}$$ with the norm $\left| \right| \mathbf{x} \left| \right| := \sqrt{\langle \mathbf{x}, \mathbf{x} \rangle}$. If the class means have the same distance to the origin, then $b$ will vanish.
Note that (1.9) induces a decision boundary which has the form of a hyperplane (Figure 1.1); that is, a set of points that satisfy a constraint expressible as a linear equation.
It is instructive to rewrite (1.9) in terms of the input patterns $x_i$, using the kernel $k$ to compute the dot products. Note, however, that (1.6) only tells us how to compute the dot products between vectorial representations $\mathbf{x}_i$ of inputs $x_i$. We therefore need to express the vectors $\mathbf{c}_i$ and $\mathbf{w}$ in terms of $\mathbf{x}_1, \dots, \mathbf{x}_m$.
enter image description here To this end, substitute (1.7) and (1.8) into (1.9) to get the decision function $$\begin{align} y &= \text{sgn} \left( \dfrac{1}{m_+} \sum_{\{i \vert y_i = +1 \}} \langle \mathbf{x}, \mathbf{x}_i \rangle - \dfrac{1}{m_-} \sum_{\{i \vert y_i = -1 \}} \langle \mathbf{x}, \mathbf{x}_i \rangle + b \right) \\ &= \text{sgn} \left( \dfrac{1}{m_+} \sum_{\{i \vert y_i = +1 \}} k( x, x_i ) - \dfrac{1}{m_-} \sum_{\{i \vert y_i = -1 \}} k( x, x_i ) + b \right). \tag{1.11} \end{align}$$ Similarly, the offset becomes $$b := \dfrac{1}{2} \left( \dfrac{1}{m^2_-} \sum_{\{(i, j) \vert y_i = y_j = -1 \}} k( x_i, x_j ) - \dfrac{1}{m^2_+} \sum_{\{(i, j) \vert y_i = y_j = +1 \}} k( x_i, x_j ) \right). \tag{1.12}$$ Surprisingly, it turns out that this rather simple-minded approach contains a well-known statistical classification method as a special case. Assume that the class means have the same distance to the origin (hence $b = 0$, cf. (1.10)), and that $k$ can be viewed as a probability density when one of its arguments is fixed. By this we mean that it is positive and has unit integral, $$\int_\mathcal{X} k(x, x^\prime) \ dx = 1 \ \text{for all} \ x^\prime \in \mathcal{X}. \tag{1.13}$$ In this case, (1.11) takes the form of the so-called Bayes classifier separating the two classes, subject to the assumption that the two classes of patterns were generated by sampling from two probability distributions that are correctly estimated by the Parzen windows estimators of the two class densities, $$p_+ (x) := \dfrac{1}{m_+} \sum_{\{ i \mid y_i = +1 \}} k(x, x_i) \ \ \text{and} \ \ p_- (x) := \dfrac{1}{m_-} \sum_{\{ i \mid y_i = -1 \}} k(x, x_i), \tag{1.14}$$ where $x \in \mathcal{X}$.
Given some point $x$, the label is then simply computed by checking which of the two values $p_+ (x)$ or $p_- (x)$ is larger, which leads directly to (1.11). Note that this decisions the best we can do if we have no prior information about the probabilities of the two classes.

I'm interested in this part:

Note that this decision is the best we can do if we have no prior information about the probabilities of the two classes.

How do we know this? What is the justification for this?

$\endgroup$

1 Answer 1

0
+50
$\begingroup$

Let $\omega_1$ and $\omega_2$ be the two classes. The book mentions:

In this case, (1.11) takes the form of the so-called Bayes classifier separating the two classes, subject to the assumption that the two classes of patterns were generated by sampling from two probability distributions that are correctly estimated by the Parzen windows estimators of the two class densities,

So, it is assumed that:

$$ \begin{align} p_+ (x) \equiv p(\mathbf{x}|\omega_1) &= \frac{1}{m_+} \sum_{\{ i \mid y_i = +1 \}} k(x, x_i) \\ p_- (x) \equiv p(\mathbf{x}|\omega_2) &= \frac{1}{m_-} \sum_{\{ i \mid y_i = -1 \}} k(x, x_i) \end{align} $$

Where $m_+$ is the number of feature vectors belonging to class $\omega_1$ and $m_-$ is the number of feature vectors belonging to class $\omega_2$. Also, the book mentions:

Assume that the class means have the same distance to the origin (hence $b=0$, cf. (1.10))

This implies that the classes are assumed to have equal prior probability, such that $p(\omega_1) = p(\omega_2)$.


Side Note

Here is an explanation of why $b=0$ implies $p(\omega_1) = p(\omega_2)$.

The Bayes classifier decision rule is:

$$ \begin{cases} \mathbf{x} \in \omega_1 &\text{if} \quad p(\omega_1|\mathbf{x}) > p(\omega_2|\mathbf{x}) \\ \mathbf{x} \in \omega_2 &\text{if} \quad p(\omega_1|\mathbf{x}) < p(\omega_2|\mathbf{x}) \end{cases} $$

Or:

$$ \begin{cases} \mathbf{x} \in \omega_1 &\text{if} \quad p(\mathbf{x}|\omega_1)p(\omega_1) > p(\mathbf{x}|\omega_2)p(\omega_2) \\ \mathbf{x} \in \omega_2 &\text{if} \quad p(\mathbf{x}|\omega_1)p(\omega_1) < p(\mathbf{x}|\omega_2)p(\omega_2) \end{cases} $$

Therefore, the equation for the decision surface/hyperplane that separates the two classes is:

$$ p(\mathbf{x}|\omega_1)p(\omega_1) = p(\mathbf{x}|\omega_2)p(\omega_2) $$

Applying the natural logarithm to both sides of this equation, noting that the natural logarithm is monotonically increasing:

$$ \text{ln}(p(\mathbf{x}|\omega_1)) + \text{ln}(p(\omega_1)) = \text{ln}(p(\mathbf{x}|\omega_2)) + \text{ln}(p(\omega_2)) $$

Re-arranging:

$$ \text{ln}(p(\mathbf{x}|\omega_1)) - \text{ln}(p(\mathbf{x}|\omega_2)) + \text{ln}(p(\omega_1)) - \text{ln}(p(\omega_2)) = 0 $$

Using logarithm rules:

$$ \text{ln}\left(\frac{p(\mathbf{x}|\omega_1)}{p(\mathbf{x}|\omega_2)}\right) + \text{ln}\left(\frac{p(\omega_1)}{p(\omega_2)}\right) = 0 $$

In this case:

$$ \begin{align} \text{ln}\left(\frac{p(\mathbf{x}|\omega_1)}{p(\mathbf{x}|\omega_2)}\right) &\equiv \frac{1}{m_+} \sum_{\{i | y_i = +1 \}} k( x, x_i ) - \dfrac{1}{m_-} \sum_{\{i \vert y_i = -1 \}} k( x, x_i ) \\ \text{ln}\left(\frac{p(\omega_1)}{p(\omega_2)}\right) &\equiv b \end{align} $$

Therefore, $b=0$ only if:

$$ \begin{align} \frac{p(\omega_1)}{p(\omega_2)} &= 1 \\ p(\omega_1) &= p(\omega_2) \end{align} $$


If $p(\omega_1) = p(\omega_2)$, the Bayes classifier decision rule becomes:

$$ \begin{cases} \mathbf{x} \in \omega_1 &\text{if} \quad p(\mathbf{x}|\omega_1) > p(\mathbf{x}|\omega_2) \\ \mathbf{x} \in \omega_2 &\text{if} \quad p(\mathbf{x}|\omega_1) < p(\mathbf{x}|\omega_2) \end{cases} $$

This is exactly the same decision rule as:

Given some point x, the label is then simply computed by checking which of the two values p+(x) or p−(x) is larger, which leads directly to (1.11).

Which the author writes. Therefore, when the author writes:

Note that this decision is the best we can do if we have no prior information about the probabilities of the two classes.

What they mean is that given the assumption that $b=0$, such that the class prior probabilities are equal, then this decision rule is optimal.

$\endgroup$
1
  • $\begingroup$ @ThePointer did this answer help? $\endgroup$
    – mhdadk
    Jan 7, 2021 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.