next up previous contents
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,

E($\displaystyle \bf\tilde\boldsymbol{\varphi}$) = $\displaystyle \bf\tilde\boldsymbol{\varphi}^{T}_{}$$\displaystyle \bf\tilde\boldsymbol{\varphi}$ - $\displaystyle \bf\tilde\boldsymbol{\varphi}^{T}_{}$$\displaystyle \bf W^{T}_{}$$\displaystyle \bf W$$\displaystyle \bf\tilde\boldsymbol{\varphi}$ . (5.5)

$ \bf\tilde\boldsymbol{\varphi}$ is a vector originating in the center of the distribution in feature space, $ \bf\tilde\boldsymbol{\varphi}$($ \bf z$) = $ \varphi$($ \bf z$) - $ \bf\bar{\boldsymbol{\varphi}}$. The matrix $ \bf W$ contains the q row vectors $ \bf\tilde{\bf w}^{l}_{}$ (q is the number of principal components)5.2.

We need to eliminate $ \bf\tilde\boldsymbol{\varphi}$ in (5.5), and write the potential as a function of a vector $ \bf z$ taken from the original space. The projection fl($ \bf z$) of $ \bf\tilde\boldsymbol{\varphi}$($ \bf z$) onto the eigenvectors $ \bf\tilde{\bf w}^{l}_{}$ = $ \sum_{{i=1}}^{n}$$ \alpha_{i}^{l}$$ \bf\tilde\boldsymbol{\varphi}$($ \bf x_{i}^{}$) can be readily evaluated using the kernel function k,


fl($\displaystyle \bf z$) = $\displaystyle \bf\tilde\boldsymbol{\varphi}$($\displaystyle \bf z$)T$\displaystyle \tilde{{{\bf w}}}^{l}_{}$  
  = $\displaystyle \left[\vphantom{\boldsymbol{\varphi}({\bf z})-\frac{1}{n}\sum_{r=1}^n \boldsymbol{\varphi}({\bf x}_r)}\right.$$\displaystyle \varphi$($\displaystyle \bf z$) - $\displaystyle {\frac{{1}}{{n}}}$$\displaystyle \sum_{{r=1}}^{n}$$\displaystyle \varphi$($\displaystyle \bf x_{r}^{}$)$\displaystyle \left.\vphantom{\boldsymbol{\varphi}({\bf z})-\frac{1}{n}\sum_{r=1}^n \boldsymbol{\varphi}({\bf x}_r)}\right]^{T}_{}$$\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.$$\displaystyle \sum_{{i=1}}^{n}$$\displaystyle \alpha_{i}^{l}$$\displaystyle \varphi$($\displaystyle \bf x_{i}^{}$) - $\displaystyle {\frac{{1}}{{n}}}$$\displaystyle \sum_{{i,r=1}}^{n}$$\displaystyle \alpha_{i}^{l}$$\displaystyle \varphi$($\displaystyle \bf x_{r}^{}$)$\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]$  
  = $\displaystyle \sum_{{i=1}}^{n}$$\displaystyle \alpha_{i}^{l}$ $\displaystyle \Bigg[$k($\displaystyle \bf z$,$\displaystyle \bf x_{i}^{}$) - $\displaystyle {\frac{{1}}{{n}}}$$\displaystyle \sum_{{r=1}}^{n}$k($\displaystyle \bf x_{i}^{}$,$\displaystyle \bf x_{r}^{}$) - $\displaystyle {\frac{{1}}{{n}}}$$\displaystyle \sum_{{r=1}}^{n}$k($\displaystyle \bf z$,$\displaystyle \bf x_{r}^{}$)  
  + $\displaystyle {\frac{{1}}{{n^2}}}$$\displaystyle \sum_{{r,s=1}}^{n}$k($\displaystyle \bf x_{r}^{}$,$\displaystyle \bf x_{s}^{}$)$\displaystyle \Bigg]$ . (5.6)

The second equality uses (5.1). As a result, E($ \bf z$) can be expressed as

E($\displaystyle \bf z$) = $\displaystyle \bf\tilde\boldsymbol{\varphi}^{T}_{}$$\displaystyle \bf\tilde\boldsymbol{\varphi}$ - $\displaystyle \sum_{{l=1}}^{q}$fl($\displaystyle \bf z$)2 . (5.7)

The scalar product $ \bf\tilde\boldsymbol{\varphi}^{T}_{}$$ \bf\tilde\boldsymbol{\varphi}$ equals the potential field of a sphere (5.3). Thus, the expression of the potential E($ \bf z$) can be further simplified to

E($\displaystyle \bf z$) = ES($\displaystyle \bf z$) - $\displaystyle \sum_{{l=1}}^{q}$fl($\displaystyle \bf z$)2 , (5.8)

which is the desired form of the cylindrical potential.

The above computation of fl($ \bf z$) requires n evaluations of the kernel function for each $ \bf z$. 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}$$ \alpha_{i}^{l}$$ \varphi$($ \bf x_{i}^{}$) is estimated by $ \sum_{{i=1}}^{m}$$ \beta_{i}^{l}$$ \varphi$($ \bf y_{i}^{}$), and 1/n$ \sum_{{i=1}}^{n}$$ \varphi$($ \bf x_{i}^{}$) by $ \sum_{{i=1}}^{m}$$ \beta_{i}^{0}$$ \varphi$($ \bf y_{i}^{}$). Doing these replacements, the equation for fl($ \bf z$) (5.6) can be approximated by


fl($\displaystyle \bf z$) = $\displaystyle \sum_{{i=1}}^{m}$ $\displaystyle \left(\vphantom{ \beta_i^l - \beta_i^0 \sum_{j=1}^n\alpha_j^l }\right.$ $\displaystyle \beta_{i}^{l}$ - $\displaystyle \beta_{i}^{0}$$\displaystyle \sum_{{j=1}}^{n}$$\displaystyle \alpha_{j}^{l}$ $\displaystyle \left.\vphantom{ \beta_i^l - \beta_i^0 \sum_{j=1}^n\alpha_j^l }\right)$ k($\displaystyle \bf z$,$\displaystyle \bf y_{i}^{}$)  
  - $\displaystyle \sum_{{i=1}}^{m}$$\displaystyle \sum_{{j=1}}^{m}$$\displaystyle \beta_{i}^{0}$$\displaystyle \beta_{j}^{l}$k($\displaystyle \bf y_{i}^{}$,$\displaystyle \bf y_{j}^{}$) + $\displaystyle \sum_{{r=1}}^{n}$$\displaystyle \alpha_{r}^{l}$$\displaystyle \sum_{{i=1}}^{m}$$\displaystyle \sum_{{j=1}}^{m}$$\displaystyle \beta_{i}^{l}$$\displaystyle \beta_{j}^{l}$k($\displaystyle \bf y_{i}^{}$,$\displaystyle \bf y_{j}^{}$) . (5.9)

The last two terms and $ \sum_{{j=1}}^{n}$$ \alpha_{j}^{l}$ do not need to be evaluated for each $ \bf z$, 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 up previous contents
Next: 5.2.2.1 Examples Up: 5.2 Pattern association algorithm Previous: 5.2.1 Spherical potential
Heiko Hoffmann
2005-03-22