Visualization and self-organization of multidimensional data through equalized orthogonal mapping

• US 6,212,509 B1
• Filed: 05/02/2000
• Issued: 04/03/2001
• Est. Priority Date: 09/29/1995
• Status: Expired due to Term

• Current Assignee: CA, Inc. (d/b/a CA Technologies) (Broadcom, Inc.)
• Original Assignee: Computer Associates Think Inc. (Broadcom, Inc.)
• Inventors: Pao, Yoh-Han, Meng, Zhuo
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): Starks, Wilbert L.
• Application Number:
  US09/562,777
• Time in Patent Office: 336 Days
• Field of Search: 706/16, 706/22, 706/25, 706/62, 703/13, 707/532, 704/9, 382/156, 382/205
• US Class Current: 706/16
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06F 18/21355 nonlinear criteria, e.g. embedding a manifold in a Euclidean space
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps

Abstract

The subject system provides reduced-dimension mapping of pattern data. Mapping is applied through conventional single-hidden-layer feed-forward neural network with non-linear neurons. According to one aspect of the present invention, the system functions to equalize and orthogonalize lower dimensional output signals by reducing the covariance matrix of the output signals to the form of a diagonal matrix or constant times the identity matrix. The present invention allows for visualization of large bodies of complex multidimensional data in a relatively “topologically correct” low-dimension approximation, to reduce randomness associated with other methods of similar purposes, and to keep the mapping computationally efficient at the same time.

Claims

1. A system for organizing multi-dimensional pattern data into a reduced-dimension representation comprising:

a neural network comprised of a plurality of layers of nodes, the plurality of layers including;

an input layer comprised of a plurality of input nodes,

a hidden layer, and

an output layer comprised of a plurality of non-linear output nodes, wherein the number of non-linear output nodes is less than the number of input nodes;

receiving means for receiving multi-dimensional pattern data into the input layer of the neural network;

output means for generating an output signal for each of the output nodes of the output layer of the neural network corresponding to received multi-dimensional pattern data; and

training means for completing a training of the neural network, wherein the training means includes means for equalizing and orthogonalizing the output signals of the output nodes by reducing a covariance matrix of the output signals to the form of a diagonal matrix.

2. A system according to claim 1, wherein said training means uses backpropagation to iteratively update weights for the links between nodes of adjacent layers.

3. A system according to claim 2, wherein said weights are generated randomly in the interval (W, −

W).

4. A system according to claim 3, wherein averaged variance of all dimensions of the multi-dimensional pattern data is:

$V_{i<br><br>\text{\hspace{1em}<br><br>}<br><br>n}=\frac{1}{\mathrm{SP}}<br><br>\underset{i=1}{\overset{S}{\sum <br><br>}}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ip}}-〈<br><br>x_i〉<br><br>\right)}^2,$

and the elements of the covariance matrix of the output signals of the output nodes are defined by;

$V_{\mathrm{out},k_1<br><br>k_2}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\left(O_{k_1<br><br>p}-〈<br><br>O_{k_1}〉<br><br>\right)<br><br>\left(O_{k_2<br><br>p}-〈<br><br>O_{k_2}〉<br><br>\right),$

where

p=1, 2, . . . , P;

O_k1p is the output signal of the k₁th node of the output layer for the pth input data pattern vector;

O_k2p is the output signal of the k₂th node of the output layer for the pth input data pattern vector;

<

O_k1>

is the average of O_k1p evaluated over the set of input data pattern vectors

<

O_k2>

is the average of O_k2p evaluated over the set of input data pattern vectors

k₁=1 to K;

k₂=1 to K;

K is the number of dimensions in the reduced-dimension representation; and

<

>

denotes the mean evaluated over the set of input data pattern vectors for each indicated component.

5. A system according to claim 4, wherein weights Δ

w_kj between the hidden layer and the output layer are iteratively updated according to the expression;

$\begin{array}{c}\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj}}=\text{\hspace{1em}<br><br>}<br><br>-\mathrm{\eta <br><br>}<br><br>\frac{\partial <br><br>E}{\partial <br><br>w_{\mathrm{kj}}}\\ =\text{\hspace{1em}<br><br>}<br><br>\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\mathrm{\eta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp}}<br><br>O_{\mathrm{jp}}\\ =\text{\hspace{1em}<br><br>}<br><br>-\mathrm{\eta <br><br>}<br><br>\left(\frac{\partial <br><br>E_{\mathrm{kk}}}{\partial <br><br>w_{\mathrm{kj}}}+\underset{k_2=k+1}{\overset{K}{\sum <br><br>}}<br><br>\frac{\partial <br><br>E_{{\mathrm{kk}}_2}}{\partial <br><br>w_{\mathrm{kj}}}+\underset{k_1=1}{\overset{k-1}{\sum <br><br>}}<br><br>\partial <br><br>\frac{E_{k_1<br><br>k}}{\partial <br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj}}}\right)\\ =\text{\hspace{1em}<br><br>}<br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},1}+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},2}+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},3},\end{array}$

where η

is a constant of suitable value chosen to provide efficient convergence but to avoid oscillation;

O_jp is the output signal from the jth node in the layer preceeding the output layer due to the pth input data pattern vector;

E is the error given by;

$E=\underset{k_1=1}{\overset{K}{\sum <br><br>}}<br><br>\underset{k_2=k_1}{\overset{K}{\sum <br><br>}}<br><br>E_{k_1<br><br>k_2}$$\mathrm{and},<br><br>E_{k_1<br><br>k_2}={\left(\frac{V_{\mathrm{out},\mathrm{kk}}-r_{\mathrm{kk}}<br><br>V_{i<br><br>\text{\hspace{1em}<br><br>}<br><br>n}}{r_{\mathrm{kk}}<br><br>V_{i<br><br>\text{\hspace{1em}<br><br>}<br><br>n}}\right)}^2,$

where k₁=k₂=k;

k=1, . . . , K; and

r_kk is a positive constant which has an effect of increasing the speed of training, $E_{k_1<br><br>k_2}={\left(\frac{V_{\mathrm{out},k_1<br><br>k_2}}{r_{k_1<br><br>k_2}}<br><br>V_{i<br><br>\text{\hspace{1em}<br><br>}<br><br>n}\right)}^2,$

where k₂>

k₁;

k₁=1, . . . , K; and

r_k1k2 is a positive constant which has an effect of increasing the speed of training; and

δ

_kp=δ

_kp,1+δ

_kp,2+δ

_kp,3, where δ

_kp is a value proportional to the contribution to the error E by the outputs of the kth node of the output layer, for the pth input data pattern vector, and δ

_kp,1, δ

_kp,2, and δ

_kp,3 are components of δ

_kp.

6. A system according to claim 5, wherein:

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},1}=-\mathrm{\eta <br><br>}<br><br>\frac{\partial <br><br>E_{\mathrm{kk}}}{\partial <br><br>w_{\mathrm{kj}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\mathrm{\eta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp},1}<br><br>O_{\mathrm{jp}}$$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},2}=-\mathrm{\eta <br><br>}<br><br>\underset{k_2=k+1}{\overset{K}{\sum <br><br>}}<br><br>\frac{\partial <br><br>E_{{\mathrm{kk}}_2}}{\partial <br><br>w_{\mathrm{kj}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\mathrm{\eta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp},2}<br><br>O_{\mathrm{jp}}$$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},3}=-\mathrm{\eta <br><br>}<br><br>\underset{k_1=1}{\overset{k-1}{\sum <br><br>}}<br><br>\frac{\partial <br><br>E_{k_1<br><br>k}}{\partial <br><br>w_{\mathrm{kj}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\mathrm{\eta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp},3}<br><br>O_{\mathrm{jp}}$

where

Δ

w_kj,1 is the contribution from the diagonal terms of the covariance matrix of the outputs,

Δ

w_kj,2 is the contribution from the off-diagonal terms in kth row,

Δ

w_kj,3 is the contribution from the off-diagonal terms in kth column, and

O_jp is the output signal from the jth node in the layer preceeding the output layer for the pth input data pattern vector.

7. A system according to claim 6, wherein:

${\mathrm{\delta <br><br>}}_{\mathrm{kp},1}=4<br><br>\left(V_{\mathrm{out},\mathrm{kk}}-r_{\mathrm{kk}}<br><br>V_{i<br><br>\text{\hspace{1em}<br><br>}<br><br>n}\right)<br><br>\left(〈<br><br>O_k〉<br><br>-O_{\mathrm{kp}}\right)<br><br>O_{\mathrm{kp}}<br><br>\left(1-O_{\mathrm{kp}}\right)$${\mathrm{\delta <br><br>}}_{\mathrm{kp},1}=2<br><br>\left(\underset{k_2=k+1}{\overset{K}{\sum <br><br>}}<br><br>V_{\mathrm{out},{\mathrm{kk}}_2}<br><br>\left(〈<br><br>O_k〉<br><br>-O_{\mathrm{kp}}\right)\right)<br><br>O_{\mathrm{kp}}<br><br>\left(1-O_{\mathrm{kp}}\right)$${\mathrm{\delta <br><br>}}_{\mathrm{kp},3}=2<br><br>\left(\underset{k_1=1}{\overset{k-1}{\sum <br><br>}}<br><br>V_{\mathrm{out},k_1<br><br>k}<br><br>\left(〈<br><br>O_k〉<br><br>-O_{\mathrm{kp}}\right)\right)<br><br>O_{\mathrm{kp}}<br><br>\left(1-O_{\mathrm{kp}}\right),$

where

O_kp is the output signal from the kth node in the output layer for the pth input data pattern vector, and

<

O_kp>

is the average of O_kp evaluated over the set of input data pattern vectors.

8. A system according to claim 5, wherein backpropogation of error to the weights Δ

w_ji between the jth node in a layer of nodes and the ith node in its'"'"' preceeding layer;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{ji}}=\mathrm{\eta <br><br>}<br><br>\frac{\partial <br><br>E}{\partial <br><br>w_{\mathrm{ji}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\mathrm{\eta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{jp}}<br><br>x_{\mathrm{ip}}$

where, δ

_jp is given by;

${\mathrm{\delta <br><br>}}_{\mathrm{jp}}=\left(\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp}}<br><br>w_{\mathrm{kj}}\right)<br><br>O_{\mathrm{jp}}<br><br>\left(1-O_{\mathrm{jp}}\right).$

9. A method for effecting the organization of multi-dimensional pattern data into a reduced dimensional representation using a neural network having an input layer comprised of a plurality of input nodes, a hidden layer, and an output layer comprised of a plurality of non-linear output nodes, wherein the number of non-linear output nodes is less than the number of input nodes, said method comprising:

receiving multi-dimensional pattern data into the input layer of the neural network;

generating an output signal for each of the output nodes of the neural network corresponding to received multi-dimensional pattern data; and

training the neural network by equalizing and orthogonalizing the output signals of the output nodes by reducing a covariance matrix of the output signals to the form of a diagonal matrix.

10. A method according to claim 9, wherein said step of training includes backpropagation to iteratively update weights for links between nodes of adjacent layers.

11. A method according to claim 10, wherein said weights are generated randomly in the interval (W, −

W).

12. A method according to claim 11, wherein averaged variance of all dimensions of the multi-dimensional pattern data is:

$V_{i<br><br>\text{\hspace{1em}<br><br>}<br><br>n}=\frac{1}{\mathrm{SP}}<br><br>\underset{i=1}{\overset{S}{\sum <br><br>}}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ip}}-〈<br><br>x_i〉<br><br>\right)}^2,$

and the elements of the covariance matrix of the output signals of the output nodes is;

$V_{\mathrm{out},k_1<br><br>k_2}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\left(O_{k_1<br><br>p}-〈<br><br>O_{k_1}〉<br><br>\right)<br><br>\left(O_{k_2<br><br>p}-〈<br><br>O_{k_2}〉<br><br>\right),$

where

p=1, 2, . . . , P;

O_k1p is the output signal of the k₁th node of the output layer for the pth input data pattern vector;

O_k2p is the output signal of the k₂th node of the output layer for the pth input data pattern vector;

<

O_k1p>

is the average of O_k1p evaluated over the set of input data pattern vectors

<

O_k2p>

is the average of O_k2p evaluated over the set of input data pattern vectors

k₁=1 to K;

k₂=1 to K;

K is the number of dimensions in the reduced-dimension representation; and

<

>

denotes the mean evaluated over the set of input data pattern vectors for each indicated component.

13. A method according to claim 12, wherein weights Δ

w_kj between the hidden layer and the output layer are iteratively updated according to the expression;

$\begin{array}{c}\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj}}=\text{\hspace{1em}<br><br>}<br><br>-\mathrm{\eta <br><br>}<br><br>\frac{\partial <br><br>E}{\partial <br><br>w_{\mathrm{kj}}}\\ =\text{\hspace{1em}<br><br>}<br><br>\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>\mathrm{\eta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp}}<br><br>O_{\mathrm{jp}}\\ =\text{\hspace{1em}<br><br>}<br><br>-\mathrm{\eta <br><br>}<br><br>\left(\frac{\partial <br><br>E_{\mathrm{kk}}}{\partial <br><br>w_{\mathrm{kj}}}+\underset{k_2=k+1}{\overset{K}{\sum <br><br>}}<br><br>\frac{\partial <br><br>E_{{\mathrm{kk}}_2}}{\partial <br><br>w_{\mathrm{kj}}}+\underset{k_1=1}{\overset{k-1}{\sum <br><br>}}<br><br>\partial <br><br>\frac{E_{k_1<br><br>k}}{\partial <br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj}}}\right)\\ =\text{\hspace{1em}<br><br>}<br><br>\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},1}+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},2}+\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},3},\end{array}$

where η

is a constant of suitable value chosen to provide efficient convergence but to avoid oscillation;

O_jp is the output signal from the jth node in the layer preceeding the output layer, due to the pth input data pattern vector;

E is the error given by;

$E=\underset{k_1=1}{\overset{K}{\sum <br><br>}}<br><br>\underset{k_2=k_1}{\overset{K}{\sum <br><br>}}<br><br>E_{k_1<br><br>k_2}$$\mathrm{and},<br><br>E_{k_1<br><br>k_2}={\left(\frac{V_{\mathrm{out},k,k}-r_{\mathrm{kk}}<br><br>V_{\mathrm{in}}}{r_{\mathrm{kk}}<br><br>V_{\mathrm{in}}}\right)}^2,$

where k₁=k₂=k;

k=1, . . . , K; and

r_kk is a positive constant which has an effect of increasing the speed of training, $E_{k_1<br><br>k_2}={\left(\frac{V_{\mathrm{out},k_1<br><br>k_2}}{r_{k_1<br><br>k_2}}<br><br>V_{\mathrm{in}}\right)}^2,$

where k₂>

k₁;

k₁=1, . . . , K−

1;

k₂=k₁+1, . . . , K; and

r_k1k2 is a positive constant which has an effect of increasing the speed of training; and

δ

_kp=δ

_kp,1+δ

_kp,2+δ

_kp,3, where δ

_kp is a value proportional to the contribution to the error E by the outputs of the kth node of the output layer, for the pth input data pattern vector, and δ

_kp,1, δ

_kp,2, and δ

_kp,3 are components of δ

_kp.

14. A method according to claim 13, wherein:

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},1}=-\mathrm{\eta <br><br>}<br><br>\frac{\partial <br><br>E_{\mathrm{kk}}}{\partial <br><br>w_{\mathrm{kj}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>{\mathrm{\eta <br><br>\delta <br><br>}}_{\mathrm{kp},1}<br><br>O_{\mathrm{jp}}$$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},2}=-\mathrm{\eta <br><br>}<br><br>\underset{k_2=k+1}{\overset{K}{\sum <br><br>}}<br><br>\frac{\partial <br><br>E_{{\mathrm{kk}}_2}}{\partial <br><br>w_{\mathrm{kj}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>{\mathrm{\eta <br><br>\delta <br><br>}}_{\mathrm{kp},2}<br><br>O_{\mathrm{jp}}$$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{kj},3}=-\mathrm{\eta <br><br>}<br><br>\underset{k_1=1}{\overset{k-1}{\sum <br><br>}}<br><br>\frac{\partial <br><br>E_{k_1<br><br>k_2}}{\partial <br><br>w_{\mathrm{kj}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>{\mathrm{\eta <br><br>\delta <br><br>}}_{\mathrm{kp},3}<br><br>O_{\mathrm{jp}}$

where

Δ

w_kj,1 is the contribution from the diagonal term,

Δ

w_kj,2 is the contribution from the off-diagonal terms in kth row, and

Δ

w_kj,3 is the contribution from the off-diagonal terms in kth column.

15. A method according to claim 14, wherein δ

_kp,1, δ

_kp,2 and δ

_kp,3 are given by;

${\mathrm{\delta <br><br>}}_{\mathrm{kp},1}=4<br><br>\left(V_{\mathrm{out},\mathrm{kk}}-r_{\mathrm{kk}}<br><br>V_{\mathrm{in}}\right)<br><br>\left(〈<br><br>O_k〉<br><br>-O_{\mathrm{kp}}\right)<br><br>O_{\mathrm{kp}}<br><br>\left(1-O_{\mathrm{kp}}\right)$${\mathrm{\delta <br><br>}}_{\mathrm{kp},1}=2<br><br>\left(\underset{k_2=k+1}{\overset{K}{\sum <br><br>}}<br><br>V_{\mathrm{out},{\mathrm{kk}}_2}<br><br>\left(〈<br><br>O_k〉<br><br>-O_{\mathrm{kp}}\right)\right)<br><br>O_{\mathrm{kp}}<br><br>\left(1-O_{\mathrm{kp}}\right)$${\mathrm{\delta <br><br>}}_{\mathrm{kp},3}=2<br><br>\left(\underset{k_1=1}{\overset{k-1}{\sum <br><br>}}<br><br>V_{\mathrm{out},k_1<br><br>k}<br><br>\left(〈<br><br>O_k〉<br><br>-O_{\mathrm{kp}}\right)\right)<br><br>O_{\mathrm{kp}}<br><br>\left(1-O_{\mathrm{kp}}\right),$

where

O_kp is the output signal from the kth node in the layer preceeding the output layer for the pth input data pattern vector, and

<

O_kp>

is the average of O_kp evaluated over the set of input data pattern vectors.

16. A method according to claim 13, wherein backpropogation of error to the weights Δ

w_ji between the jth node in a layer of nodes and the ith node in its'"'"' preceeding layer are;

$\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>w_{\mathrm{ji}}=\mathrm{\eta <br><br>}<br><br>\frac{\partial <br><br>E}{\partial <br><br>w_{\mathrm{ji}}}=\frac{1}{P}<br><br>\underset{p=1}{\overset{P}{\sum <br><br>}}<br><br>{\mathrm{\eta <br><br>\delta <br><br>}}_{\mathrm{jp}}<br><br>x_{\mathrm{jp}}$

where, δ

_jp is given by;

${\mathrm{\delta <br><br>}}_{\mathrm{jp}}=\left(\underset{k=1}{\overset{K}{\sum <br><br>}}<br><br>{\mathrm{\delta <br><br>}}_{\mathrm{kp}}<br><br>w_{\mathrm{kj}}\right)<br><br>O_{\mathrm{jp}}<br><br>\left(1-O_{\mathrm{jp}}\right).$