1
$\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 chapter 1.1 Data Representation and Similarity, $k$ was defined as follows:

Let us consider a similarity measure of the form $$\begin{align} k: &\mathcal{X} \times \mathcal{X} \to \mathbb{R} \\ &(x, x^\prime) \mapsto k(x, x^\prime), \tag{1.2} \end{align}$$ that is, a function that, given two patterns $x$ and $x^\prime$, returns a real number characterizing their similarity. Unless stated otherwise, we will assume that $k$ is symmetric, that is, $k(x, x^\prime) = k(x^\prime, x)$ for all $x, x^\prime \in \mathcal{X}$. For reasons that will become clear later (cf. Remark 2.16), the function $k$ is called a kernel.

What is the reasoning behind

$$\int_\mathcal{X} k(x, x^\prime) \ dx = 1 \ \text{for all} \ x^\prime \in \mathcal{X} \tag{1.13}$$

only being integrated with respect to $x$? What about the $x^\prime$?

$\endgroup$
5
  • 3
    $\begingroup$ The statement below (1.2) states $k$ is symmetric, which implies integrating over $x$ will give the same result as integrating over $x^\prime.$ $\endgroup$
    – whuber
    Dec 31 '20 at 21:30
  • $\begingroup$ @whuber Ok, thanks for the clarification. $\endgroup$ Jan 1 '21 at 6:21
  • $\begingroup$ Could you please clarify your question, then? If it isn't answered by the symmetry, what are you trying to ask? $\endgroup$
    – whuber
    Jan 1 '21 at 14:37
  • $\begingroup$ @whuber You indeed answered my question. Am I supposed to delete this? Or should I post a community answer? $\endgroup$ Jan 1 '21 at 14:39
  • 1
    $\begingroup$ If you think the point isn't entirely trivial then posting an answer would be good. $\endgroup$
    – whuber
    Jan 1 '21 at 14:46
0
$\begingroup$

As whuber stated in the comments, the statement below (1.2) states $k$ is symmetric, which implies integrating over $x$ will give the same result as integrating over $x^\prime$.

$\endgroup$

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.