Analysis of Text Patterns Using Kernel Methods - Text Mining: Classification, Clustering, and Applications - page 4

non-linear relations in the data, by using a linear algorithms in a different
space.
If X is not a vector space itself, as is the case of text, the use of kernels
enables us to operate on generic entities with essentially algebraic tools. In
fact, kernel functions make possible the use of structured input space, i.e., with
an exponential or even infinite number of dimensions, and we can produce
practical algorithms having computation time that scales polynomially in the
number of training examples.
From a computational point of view kernel methods exhibit two funda-
mental properties; they make it possible to access very high-dimensional and
flexible feature spaces at low computational cost, and then pattern analysis
algorithms can solve and compute convex optimization problems eciently
without suffering from local minima, no matter the complexity of the result-
ing function classes.

Example. We now give an example of a kernel function whose complexity
is less than the dimension of its corresponding feature space F .Considera
two-dimensional input space X

2 together with the feature map

⊆ R

φ ( x )=( x 1 ,x 2 , √ 2 x 1 x 2 )

3 .

φ : x =( x 1 ,x 2 ) −→ ∈ F = R

Here, the data are moved from a two-dimensional to a three-dimensional
space using the feature map, and the linear relations in the feature space cor-
respond to quadratic relations in the input space. The resulting composition
of the feature map with the inner product in the feature space is the following:

= ( x 1 ,x 2 , √ 2 x 1 x 2 ) , ( z 1 ,z 2 , √ 2 z 1 z 2 )
= x 1 z 1 + x 2 z 2 +2 x 1 x 2 z 1 z 2
=( x 1 z 1 + x 2 z 2 ) 2 =

φ ( x ) ,φ ( z )

2 .

x , z

Hence, the function

2

κ ( x , z )= x , z

is a kernel function and F =

3 is the corresponding feature space. Once
again we are computing the inner product between the projections of two
points into the feature space without explicitly evaluating their coordinates.
It is important to highlight that the feature space is not uniquely deter-
mined by the kernel function; the same kernel computes the inner product
corresponding to the four-dimensional feature map

R

φ ( x )=( x 1 ,x 2 ,x 1 x 2 ,x 2 x 1 )

4 .

φ : x =( x 1 ,x 2 ) −→ ∈ F = R

This property of the kernel function does not affect the algorithms discussed
in this chapter.