In that case, we need to compute dot pro ducts of
input vectors mapped by , with a p ossibly pro-
hibitive computational cost. The solution to this
problem, which will b e describ ed in the following
section, builds on the fact that we
exclusively
need
to compute dot pro ducts between mapped pat-
terns (in (10) and (17))
we never need the mapped
patterns explicitly.
3 Computing Dot Pro ducts in
Feature Space
In order to compute dot products of the form
((
x
)
(
y
)), we use kernel representations of the
form
k
(
x
y
)=((
x
)
(
y
))
(18)
which allow us to compute the value of the dot
product in
F
without having to carry out the map
. This metho d was used by Boser, Guyon, &
Vapnik (1992) to extend the \Generalized Por-
trait" hyperplane classier of Vapnik & Chervo-
nenkis (1974) to nonlinear Supp ort Vector ma-
chines. To this end, they substitute a priori chosen
kernel functions for all o ccurances of dot products.
This way, the p owerful results of Vapnik & Cher-
vonenkis (1974) for the Generalized Portrait carry
over to the nonlinear case. Aizerman, Braver-
man & Rozono er (1964) call
F
the \linearization
space", and use it in the context of the p oten-
tial function classication metho d to express the
dot pro duct between elements of
F
in terms of ele-
ments of the input space. If
F
is high{dimensional,
wewould like to b e able to nd a closed form ex-
pression for
k
which can b e eciently computed.
Aizerman et al. (1964) consider the p ossibilityof
choosing
k
a priori, without b eing directly con-
cerned with the corresp onding mapping into
F
.
A sp ecic choice of
k
might then corresp ond to a
dot pro duct b etween patterns mapp ed with a suit-
able . A particularly useful example, whichis a
direct generalization of a result proved byPoggio
(1975, Lemma 2.1) in the context of p olynomial
approximation, is
(
x
y
)
d
=(
C
d
(
x
)
C
d
(
y
))
(19)
where
C
d
maps
x
to the vector
C
d
(
x
) whose entries
are all p ossible
n
-th degree ordered products of
the entries of
x
.For instance (Vapnik, 1995), if
x
=(
x
1
x
2
), then
C
2
(
x
)=(
x
2
1
x
2
2
x
1
x
2
x
2
x
1
),
or, yielding the same value of the dot product,
c
2
(
x
)=(
x
2
1
x
2
2
p
2
x
1
x
2
)
:
(20)
For this example, it is easy to verify that
;
(
x
1
x
2
)(
y
1
y
2
)
>
2
= (
x
2
1
x
2
2
p
2
x
1
x
2
)(
y
2
1
y
2
2
p
2
y
1
y
2
)
>
=
c
2
(
x
)
c
2
(
y
)
>
:
(21)
In general, the function
k
(
x
y
)=(
x
y
)
d
(22)
corresponds to a dot pro duct in the space of
d
-th order monomials of the input coordinates.
If
x
represents an image with the entries b eing
pixel values, we can thus easily work in the space
spanned by pro ducts of any
d
pixels | provided
that we are able to do our work solely in terms
of dot pro ducts, without any explicit usage of a
mapped pattern
c
d
(
x
). The latter lives in a p os-
sibly very high{dimensional space: even though
we will identify terms like
x
1
x
2
and
x
2
x
1
into one
coordinate of
F
as in (20), the dimensionalityof
F
, the image of
R
N
under
c
d
, still is
(
N
+
p
;
1)!
p
!(
N
;
1)!
and
thus grows like
N
p
.For instance, 16
16 input im-
ages and a polynomial degree
d
= 5 yield a dimen-
sionalityof10
10
.Thus, using kernels of the form
(22) is our only wayto takeinto account higher{
order statistics without a combinatorial explosion
of time complexity.
The general question which function
k
corre-
sponds to a dot product in some space
F
has
been discussed by Boser, Guyon, & Vapnik (1992)
and Vapnik (1995): Mercer's theorem of functional
analysis states that if
k
is a continuous kernel of
a positiveintegral op erator, we can construct a
mapping into a space where
k
acts as a dot prod-
uct (for details, see App endix B.
The application of (18) to our problem is
straightforward: we simply substitute an a priori
chosen kernel function
k
(
x
y
) for all o ccurances
of ((
x
)
(
y
)). This was the reason whywe had
to formulate the problem in Sec. 2 in a waywhich
only makes use of the values of dot products in
F
. The choice of
k
then
implicitly
determines the
mapping and the feature space
F
.
In App endix B, we give some examples of ker-
nels other than (22) whichmay b e used.
4 Kernel PCA
4.1 The Algorithm
To perform kernel{based PCA (Fig. 1), from now
on referred to as
kernel PCA
, the following steps
have to be carried out: rst, we compute the dot
product matrix (cf. Eq. ( 10))
K
ij
=(
k
(
x
i
x
j
))
ij
:
(23)
Next, we solve(12)by diagonalizing
K
, and nor-
malize the Eigenvector expansion coecients
n
by requiring Eq. (16),
1=
n
(
n
n
)
:
4
剩余17页未读，继续阅读
ppower123456
- 粉丝: 0
- 资源: 2
我的内容管理
展开
最新资源
- Flex垃圾回收与内存管理：防止内存泄露
- Python编程规范与最佳实践
- EJB3入门：实战教程与核心概念详解
- Python指南v2.6简体中文版——入门教程
- ANSYS单元类型详解：从Link1到Link11
- 深度解析C语言特性与实践应用
- Gentoo Linux安装与使用全面指南
- 牛津词典txt版：信息技术领域的便捷电子书
- VC++基础教程：从入门到精通
- CTO与程序员职业规划：能力提升与路径指南
- Google开放手机联盟与Android开发教程
- 探索Android触屏界面开发：从入门到设计原则
- Ajax实战：从理论到实践
- 探索Android应用开发：从入门到精通
- LM317T稳压管详解：1.5A可调输出，过载保护
- C语言实现SOCKET文件传输简单教程
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
