System, method, and computer program product for representing object relationships in a multidimensional space

• US 7,039,621 B2
• Filed: 03/22/2001
• Issued: 05/02/2006
• Est. Priority Date: 03/22/2000
• Status: Expired due to Fees

• Current Assignee: Johnson & Johnson Pharmaceutical Research & Development LLC (Johnson & Johnson)
• Original Assignee: Johnson & Johnson Pharmaceutical Research & Development LLC (Johnson & Johnson)
• Inventors: Salemme, F. Raymond, Lobanov, Victor S., Agrafiotis, Dimitris K., Rassokhin, Dmitri N.
• Primary Examiner(s): NGUYEN BA, HOANG VU A
• Application Number:
  US09/814,160
• Publication Number:
  US 20020091655A1
• Time in Patent Office: 1,867 Days
• Field of Search: 706/2, 706/6, 706/14, 706 15- 18, 706/20, 706/48, 706/62, 382224-225
• US Class Current: 706/20
• 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/40 Software arrangements specially adapted for pattern recognition, e.g. user interfaces or toolboxes therefor
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06Q 10/10 Office automation; Time management

Abstract

A method and computer product is presented for mapping n-dimensional input patterns into an m-dimensional space so as to preserve relationships that may exist in the n-dimensional space. A subset of the input patterns is chosen and mapped into the m-dimensional space using an iterative nonlinear mapping process. A set of locally defined neural networks is created, then trained in accordance with the mapping produced by the iterative process. Additional input patterns not in the subset are mapped into the m-dimensional space by using one of the local neural networks. In an alternative embodiment, the local neural networks are only used after training and use of a global neural network. The global neural network is trained in accordance with the mapping produced by the iterative process. Input patterns are initially projected into the m-dimensional space using the global neural network. Local neural networks are then used to refine the results of the global network.

Claims

1. A method of mapping a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, comprising the steps of:

(a) creating a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns into an m-dimensional output space; and

(b) mapping additional n-dimensional input patterns using the locally defined neural networks wherein step (a) comprises the steps of;

(i) selecting k patterns from the subset of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈

Rⁿ};

(ii) mapping the patterns {x_i} into an m-dimensional space (x_i→

y_i, i=1, 2, . . . k, y_i∈

R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) determining c n-dimensional reference points, {(c_i;

i=1, 2, . . . c, c_i∈

Rⁿ};

(iv) partitioning T into c disjoint clusters C_j based on a distance function d, {C_j={(x_i, y_i);

d(x_i, y_i)≦

d(x_i, c_k) for all k≠

j;

j=1, 2, . . . c;

i=1, 2, . . . k}; and

(v) training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i.

2. The method of claim 1, wherein said step (iii) is performed using a clustering methodology.

3. The method of claim 1, wherein said step (b) comprises the steps of:

(i) for an additional n-dimensional input pattern x∈

Rⁿ, determining the distance to each reference point in {c_i};

(ii) identifying a reference point c_j closest to the input pattern x; and

(iii) mapping x→

y, y∈

R^m, using the local neural network Net_i^L associated with the reference point c_j identified in step (ii).

4. A method of mapping a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, comprising the steps of:

(a) creating a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns into an m-dimensional output space; and

(b) mapping additional n-dimensional input patterns using the locally defined neural networks wherein step (a) comprises the steps of;

(i) selecting k patterns of the set of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈

Rⁿ};

(ii) mapping the patterns {x_i} into an m-dimensional space, (x_i→

y_i, i=1, 2, . . . k, y_i∈

R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) determining c m-dimensional reference points, {c_i, i=1, 2, . . . c, c_i∈

R^m};

(iv) partitioning T into c disjoint clusters C_j based on a distance function d, {C_j={(x_i, y_i);

d(y_i, c_j)≦

d(y_i, c_k) for all k≠

j, j=1, 2, . . . c;

i=1, 2, . . . k)};

(v) training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i; and

(vi) training a global network Net^G using all the patterns in T.

5. The method of claim 4, wherein said step (iii) is performed using a clustering methodology.

6. The method of claim 4, wherein step (b) comprises the steps of:

(i) for an additional n-dimensional pattern x∈

Rⁿ, mapping x→

y′

, y′

∈

R^m, using Net^G;

(ii) determining the distance of y′

to each reference point in {c_i};

(iii) identifying a reference point c_j closest to y′

; and

(iv) mapping x→

y, y∈

R^m, using the local neural network Net_j^L associated with the reference point c_j identified in step (iii).

7. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that maps a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, said computer readable program code means comprising:

a first computer readable program code means for causing the computer to create a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns into an m-dimensional space; and

a second computer readable program code means for causing the computer to project additional n-dimensional patterns of the input set using the locally defined neural networks;

wherein said first computer readable code means comprises;

(i) computer readable program code means for selecting k patterns from the subset of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈

Rⁿ};

(ii) computer readable program code means for mapping the patterns {x_i} into an m-dimensional space (x_i→

y_i, i=1, 2, . . . k, y_i∈

R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) computer readable program code means for determining c n-dimensional reference points, {c_i, i=1, 2, . . . c, c_i∈

Rⁿ};

(iv) computer readable program code means for partitioning T into c disjoint clusters C_j based on a distance function d, {C_j={(x_i, y_i);

d(x_i, y_i)≦

d(x_i, c_k) for all k ≠

j;

j=1, 2, . . . c;

i=1, 2, . . . k}; and

(v) computer readable program code means for training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i.

8. The computer program product of claim 7, wherein said first computer readable program code means uses a clustering methodology.

9. The computer program product of claim of claim 7, wherein said second computer readable code means comprises:

(i) for an additional n-dimensional input pattern x∈

Rⁿ, computer readable code means for determining the distance to each reference point in {c_i};

(ii) computer readable program code means for identifying a reference point c_j closest to the input pattern x; and

(iii) computer readable program code means for mapping x→

y, y∈

R^m, using the local neural network Net_i^L associated with the reference point c_j identified in step (ii).

10. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for causing an application program to execute on a computer that maps a set of n-dimensional input patterns to an m-dimensional space for display of said patterns using locally defined neural networks, said computer readable program code means comprising:

a first computer readable program code means for causing the computer to create a set of locally defined neural networks trained according to a mapping of a subset of the n-dimensional input patterns on said m-dimensional space; and

a second computer readable program code means for causing the computer to project additional n-dimensional patterns of the input set using the locally defined neural networks;

wherein said first computer readable program code means comprises;

(i) computer readable program code means for selecting k patterns of the set of n-dimensional input patterns, {x_i, i=1, 2, . . . k, x_i∈

Rⁿ};

(ii) computer readable program code means for mapping the patterns {x_i} into an m-dimensional space, (x_i→

y_i, i=1, 2, . . . k, y_i∈

R^m), to form a training set T={(x_i, y_i), i=1, 2, . . . k};

(iii) computer readable program code means for determining c m-dimensional reference points, {c_i, i=1, 2, . . . c, c_i∈

R^m};

(iv) computer readable program code means for partitioning T into c disjoint clusters C_j based on a distance function d, {C_j={(x_i, y_i);

d(y_i, c_j)≦

d(y_i, c_k) for all k≠

j;

j=1, 2, . . . c;

i=1, 2, . . . k)};

(v) computer readable program code means for training c independent local networks {Net_i^L, i=1, 2, . . . c}, with respective pattern subsets C_i; and

(vi) computer readable program code means for training a global network Net^G using all the patterns in T.

11. The computer program product of claim 10, wherein said first computer readable program code means uses a clustering methodology.

12. The computer program product of claim 10, wherein said second computer readable program code means comprises:

(i) for an additional n-dimensional pattern x∈

Rⁿ, computer readable program code means for mapping x→

y′

, y′

∈

R^m, using Net^G;

(ii) computer readable program code means for determining the distance of y′

to each reference point in {c_i};

(iii) computer readable program code means for identifying a reference point c_j closest to y′

; and

(iv) computer readable program code means for mapping x→

y, y∈

R^m, using the local neural network Net_j^L associated with the reference point c_j identified in step (iii).