2
$\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}$.

I'm confused by this part:

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}$.

Firstly, I've only heard of naive Bayes classifiers, so I'm not sure whether this is referring to the naive Bayes classifier, or some more general type of "Bayes classifier"; is there a difference between these? Lastly, related to my first point, I don't see anything resembling (1.11) in the Wikipedia article for naive Bayes classifier, so how is (1.11) a "Bayes classifier", as the authors claim?

$\endgroup$
3
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Bayes_classifier , naive Bayes is just an algorithm. $\endgroup$
    – Tim
    Jan 1 at 9:56
  • $\begingroup$ @Tim Ahh, ok, thanks; for some reason, that article wasn't showing up in my searches. Still, I don't see anything resembling (1.11) in that article. Any idea how (1.11) qualifies as a Bayes classifier? $\endgroup$ Jan 1 at 10:19
  • $\begingroup$ watch this may help :P youtube.com/… $\endgroup$
    – mpountou
    Jan 4 at 13:38
1
$\begingroup$

Overview of what the book is saying

According to the book, there are two classes of interest. Let these classes be $\omega_1$ and $\omega_2$. Also, given a feature vector $\mathbf{x}$, let:

$$ y = \begin{cases} +1 & \text{if} \quad \mathbf{x} \in \omega_1 \\ -1 & \text{if} \quad \mathbf{x} \in \omega_2 \end{cases} $$

According to the book:

The basic idea of the algorithm is to assign a previously unseen pattern to the class with closer mean.

Given the training dataset $\mathcal{D}$ that consists of feature vectors with their corresponding class labels:

$$ \mathcal{D} = \{\mathbf{x}_1|\omega_1,\mathbf{x}_2|\omega_1,...,\mathbf{x}_N|\omega_1,\mathbf{x}_1|\omega_2,\mathbf{x}_2|\omega_2,...,\mathbf{x}_M|\omega_2\} $$

The book also defines the following vectors as the mean vectors for each class:

$$ \mathbf{c}_+ = \frac{1}{m_+} \sum_{\{i \vert y_i = +1\}} \mathbf{x}_i \\ \mathbf{c}_- = \frac{1}{m_-} \sum_{\{i \vert y_i = -1\}} \mathbf{x}_i $$

Where $m_+$ is the number of feature vectors that belong to class $\omega_1$ (this is the same as $N$ in $\mathcal{D}$) and $m_-$ is the number of feature vectors that belong to class $\omega_2$ (this is the same as $M$ in $\mathcal{D}$).

This means that, given a not-seen-before feature vector $\mathbf{x}$, the label $y$ of this feature vector is defined as follows:

$$ y = \begin{cases} +1 & \text{if} \quad \text{dist}(\mathbf{x},\mathbf{c}_+) < \text{dist}(\mathbf{x},\mathbf{c}_-) \\ -1 & \text{if} \quad \text{dist}(\mathbf{x},\mathbf{c}_+) > \text{dist}(\mathbf{x},\mathbf{c}_-) \end{cases} \tag{1} \label{eq1} $$

Where $\text{dist}(\cdot)$ is an arbitrary distance function. Note that:

$$ \mathbf{x} \in \omega_1 \iff \text{dist}(\mathbf{x},\mathbf{c}_+) < \text{dist}(\mathbf{x},\mathbf{c}_-) \\ \mathbf{x} \in \omega_2 \iff \text{dist}(\mathbf{x},\mathbf{c}_+) > \text{dist}(\mathbf{x},\mathbf{c}_-) $$

Relationship to the Bayes classifier

The Bayes classifier assigns a feature vector $\mathbf{x}$ to class $\omega_1$ if:

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

And assigns a feature vector $\mathbf{x}$ to class $\omega_2$ if:

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

In other words:

$$ y = \begin{cases} +1 & \text{if} \quad p(\omega_1|\mathbf{x}) > p(\omega_2|\mathbf{x}) \\ -1 & \text{if} \quad p(\omega_1|\mathbf{x}) < p(\omega_2|\mathbf{x}) \end{cases} \tag{2} \label{eq2} $$

The goal then is to show that equation \ref{eq1} is the same as equation \ref{eq2}.

Since:

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

Using the law of total probability in the denominator:

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

So:

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

Dividing the numerator and the denominator by $p(\mathbf{x}|\omega_1)p(\omega_1)$:

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

Since:

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

Then:

$$ p(\omega_1|\mathbf{x}) = \frac{1}{1 + \exp\left(\text{ln}\left(\frac{p(\mathbf{x}|\omega_2)p(\omega_2)}{p(\mathbf{x}|\omega_1)p(\omega_1)}\right)\right)} = \sigma\left(\text{ln}\left(\frac{p(\mathbf{x}|\omega_2)p(\omega_2)}{p(\mathbf{x}|\omega_1)p(\omega_1)}\right)\right) \tag{3} \label{eq3} $$

Where $\sigma(\cdot)$ is the logistic function. Note that since the right hand side of equation \ref{eq3} is only a function of the feature vector $\mathbf{x}$, then let:

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

Where:

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

Since:

$$ \begin{align} p(\omega_1|\mathbf{x}) + p(\omega_2|\mathbf{x}) &= 1 \\ p(\omega_2|\mathbf{x}) &= 1 - p(\omega_1|\mathbf{x}) \end{align} $$

Then the decision rule for the Bayes classifier becomes:

$$ y = \begin{cases} +1 & \text{if} \quad \sigma(f(\mathbf{x})) > 1 - \sigma(f(\mathbf{x})) \\ -1 & \text{if} \quad \sigma(f(\mathbf{x})) < 1 - \sigma(f(\mathbf{x})) \end{cases} $$

Or:

$$ y = \begin{cases} +1 & \text{if} \quad \sigma(f(\mathbf{x})) > \frac{1}{2} \\ -1 & \text{if} \quad \sigma(f(\mathbf{x})) < \frac{1}{2} \end{cases} $$

Notice that for the logistic function, given an arbitrary input $a \in \mathbb{R}$, $\sigma(a) \geq 0.5$ for $a \geq 0$ and $\sigma(a) < 0.5$ for $a < 0$. This means that the Bayes classifier decision rule can be further simplified to:

$$ y = \begin{cases} +1 & \text{if} \quad f(\mathbf{x}) > 0 \\ -1 & \text{if} \quad f(\mathbf{x}) < 0 \end{cases} \tag{4} \label{eq4} $$

Equation \ref{eq1} can be re-written as:

$$ y = \begin{cases} +1 & \text{if} \quad \text{dist}(\mathbf{x},\mathbf{c}_+) - \text{dist}(\mathbf{x},\mathbf{c}_-) < 0 \\ -1 & \text{if} \quad \text{dist}(\mathbf{x},\mathbf{c}_+) - \text{dist}(\mathbf{x},\mathbf{c}_-) > 0 \end{cases} \tag{5} \label{eq5} $$

Notice any similarity between equation \ref{eq5} and equation \ref{eq4}? They are in fact almost the same, we just need to flip the sign of $y$ for one of them. However, what is more interesting is that:

$$ f(\mathbf{x}) \equiv \text{dist}(\mathbf{x},\mathbf{c}_+) - \text{dist}(\mathbf{x},\mathbf{c}_-) $$

The relationship above is almost true. What is missing is $\mathbf{c}_+$ and $\mathbf{c}_-$ in $f(\mathbf{x})$. This leads us to the central idea of almost all of supervised machine learning.

According to the Bayes classifer decision rule, we need to accurately estimate both $p(\omega_1|\mathbf{x})$ and $p(\omega_2|\mathbf{x})$. This in turn requires estimating $p(\mathbf{x}|\omega_1),p(\mathbf{x}|\omega_2),p(\omega_1),$ and $p(\omega_2)$. However, why estimate $p(\mathbf{x}|\omega_1),p(\mathbf{x}|\omega_2),p(\omega_1),$ and $p(\omega_2)$ when we can estimate $p(\omega_1|\mathbf{x})$ and $p(\omega_2|\mathbf{x})$ directly? See this question for more details.

Recall that:

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

Therefore, to estimate $p(\omega_1|\mathbf{x})$ and $p(\omega_2|\mathbf{x})$ directly, we can choose some function $f$ and parameterize it by some parameters $\theta$ and estimate these parameters using the training dataset $\mathcal{D}$:

$$ p(\omega_1|\mathbf{x}) = \sigma(f(\mathbf{x};\theta(\mathcal{D}))) $$

In your case, this function is:

$$ \text{dist}(\mathbf{x},\mathbf{c}_+) - \text{dist}(\mathbf{x},\mathbf{c}_-) $$

And the parameters are $\theta = (\mathbf{c}_+,\mathbf{c}_-)$, which are estimated using $\mathcal{D}$.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. With regards to (1.11), what do you mean $f$ would be the product, kernel $k$, and bias $b$? This part wasn't clear to me. $\endgroup$ Jan 3 at 14:41
  • $\begingroup$ I have updated my answer with a better explanation. $\endgroup$
    – mhdadk
    Jan 4 at 8:52
  • $\begingroup$ @ThePointer did my new answer help at all? $\endgroup$
    – mhdadk
    Jan 7 at 14:03

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.