Next: 5.2.2.1 Examples
Up: 5.2 Pattern association algorithm
Previous: 5.2.1 Spherical potential
5.2.2 Cylindrical potential
We use the reconstruction error (Diamantaras and Kung, 1996, p. 45) as a potential field in feature space,
is a vector originating in the center of the distribution in feature space,
(
) =
(
) -
. The matrix
contains the q row vectors
(q is the number of principal components)5.2.
We need to eliminate
in (5.5), and write the potential as a function of a vector
taken from the original space. The projection
fl(
) of
(
) onto the eigenvectors
= ![$ \sum_{{i=1}}^{n}$](img209.gif)
![$ \alpha_{i}^{l}$](img380.gif)
(
) can be readily evaluated using the kernel function k,
fl( ) |
= |
( )T![$\displaystyle \tilde{{{\bf w}}}^{l}_{}$](img234.gif) |
|
|
= |
![$\displaystyle \left[\vphantom{\boldsymbol{\varphi}({\bf z})-\frac{1}{n}\sum_{r=1}^n \boldsymbol{\varphi}({\bf x}_r)}\right.$](img381.gif) ( ) - ![$\displaystyle {\frac{{1}}{{n}}}$](img97.gif) ![$\displaystyle \sum_{{r=1}}^{n}$](img198.gif) ( )![$\displaystyle \left.\vphantom{\boldsymbol{\varphi}({\bf z})-\frac{1}{n}\sum_{r=1}^n \boldsymbol{\varphi}({\bf x}_r)}\right]^{T}_{}$](img382.gif) ![$\displaystyle \left[\vphantom{\sum_{i=1}^n\alpha_i^l\boldsymbol{\varphi}({\bf x}_i)-\frac{1}{n}\sum_{i,r=1}^n \alpha_i^l\boldsymbol{\varphi}({\bf x}_r)}\right.$](img383.gif) ![$\displaystyle \sum_{{i=1}}^{n}$](img98.gif) ![$\displaystyle \alpha_{i}^{l}$](img384.gif) ( ) - ![$\displaystyle {\frac{{1}}{{n}}}$](img97.gif) ![$\displaystyle \sum_{{i,r=1}}^{n}$](img385.gif) ![$\displaystyle \alpha_{i}^{l}$](img384.gif) ( )![$\displaystyle \left.\vphantom{\sum_{i=1}^n\alpha_i^l\boldsymbol{\varphi}({\bf x}_i)-\frac{1}{n}\sum_{i,r=1}^n \alpha_i^l\boldsymbol{\varphi}({\bf x}_r)}\right]$](img386.gif) |
|
|
= |
![$\displaystyle \sum_{{i=1}}^{n}$](img98.gif) k( , ) - ![$\displaystyle {\frac{{1}}{{n}}}$](img97.gif) k( , ) - ![$\displaystyle {\frac{{1}}{{n}}}$](img97.gif) k( , ) |
|
|
+ |
![$\displaystyle {\frac{{1}}{{n^2}}}$](img204.gif) k( , ) . |
(5.6) |
The second equality uses (5.1). As a result,
E(
) can be expressed as
The scalar product
![$ \bf\tilde\boldsymbol{\varphi}^{T}_{}$](img391.gif)
equals the potential field of a sphere (5.3). Thus, the expression of the potential
E(
) can be further simplified to
E( ) = ES( ) - fl( )2 , |
(5.8) |
which is the desired form of the cylindrical potential.
The above computation of
fl(
) requires n evaluations of the kernel function for each
. Since, for each component l, the same kernel can be used, the total number of kernel evaluations is also n. With the speed-up described in appendix B.2, this number can be reduced to m. Here, the expression
![$ \sum_{{i=1}}^{n}$](img209.gif)
![$ \alpha_{i}^{l}$](img380.gif)
(
) is estimated by
![$ \sum_{{i=1}}^{m}$](img392.gif)
![$ \beta_{i}^{l}$](img371.gif)
(
), and
1/n![$ \sum_{{i=1}}^{n}$](img209.gif)
(
) by
![$ \sum_{{i=1}}^{m}$](img392.gif)
![$ \beta_{i}^{0}$](img393.gif)
(
). Doing these replacements, the equation for
fl(
) (5.6) can be approximated by
fl( ) |
= |
- ![$\displaystyle \beta_{i}^{0}$](img397.gif) ![$\displaystyle \sum_{{j=1}}^{n}$](img193.gif) k( , ) |
|
|
- |
![$\displaystyle \sum_{{i=1}}^{m}$](img394.gif) ![$\displaystyle \sum_{{j=1}}^{m}$](img157.gif) ![$\displaystyle \beta_{i}^{0}$](img397.gif) k( , ) + ![$\displaystyle \sum_{{r=1}}^{n}$](img198.gif) ![$\displaystyle \alpha_{r}^{l}$](img402.gif) ![$\displaystyle \sum_{{i=1}}^{m}$](img394.gif) ![$\displaystyle \sum_{{j=1}}^{m}$](img157.gif) ![$\displaystyle \beta_{i}^{l}$](img396.gif) k( , ) . |
(5.9) |
The last two terms and
![$ \sum_{{j=1}}^{n}$](img170.gif)
do not need to be evaluated for each
, but can be computed beforehand. Therefore, the computation is dominated by the m evaluations of the kernel function, which need to be carried out only once for all eigenvectors l.
Subsections
Next: 5.2.2.1 Examples
Up: 5.2 Pattern association algorithm
Previous: 5.2.1 Spherical potential
Heiko Hoffmann
2005-03-22