Method, system, and computer program product for representing object relationships in a multidimensional space

• US 7,139,739 B2
• Filed: 04/03/2001
• Issued: 11/21/2006
• Est. Priority Date: 04/03/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, Francis R, Agrafiotis, Dimitris K, Lobanov, Victor S, Rassokhin, Dmitrii N
• Primary Examiner(s): STARKS, WILBERT L
• Application Number:
  US09/823,977
• Publication Number:
  US 20020099675A1
• Time in Patent Office: 2,058 Days
• Field of Search: 706/20, 706/25, 706/16, 706/45, 706/15, 382/157, 382/224
• US Class Current: 706/20
• CPC Class Codes: G06F 18/2137 based on criteria of topology preservation, e.g. multidimensional scaling or self-organising maps
• CPC Class Codes: G06N 3/02 Neural networks

Abstract

A method, system, and computer product is presented for mapping a set of patterns into an m-dimensional space so as to preserve relationships that may exist between these patterns. A subset of the input patterns is chosen and mapped into the m-dimensional space using an iterative nonlinear mapping process based on subset refinements. A set of n attributes are determined for each pattern, and one or more neural networks or other supervised machine learning techniques are 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 determining their n input attributes and using the neural networks in a feed-forward (prediction) mode.

Claims

1. A method of mapping a set of input patterns to an m-dimensional space, wherein each pattern represents a compound selected from a database of compounds, the method comprising the steps of:

(a) selecting k patterns from said set of input patterns to form a subset of patterns {p_i, i=1, . . . , k};

(b) determining at least some pairwise relationships between at least some of the patterns in said subset of patterns {p_i}

(c) mapping the patterns {p_i} into a set of images in an m-dimensional space {p_i→

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

R^m) so that at least some of the pairwise distances between at least some of the images {y_i} are representative of the relationships of the respective patterns {p_i};

(d) determining a set of n attributes for each pattern in said subset of patterns {p_i} {x_i, i=1, 2, . . . k, x_i∈

Rⁿ};

(e) forming a training set T={(x_i, y_i), i=1, 2, . . . k};

(f) using a supervised machine learning technique to determine a mapping function based on the training set T; and

(g) using said mapping function determined in step (f) to map additional patterns.

2. The method of claim 1, wherein said mapping function is encoded in at least one neural network.

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

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

Rⁿ};

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

d(x_i, c_j).≦

d(x_i, c_k) for all k≠

j;

j=1, 2, . . . c;

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

(iii) using a supervised machine learning technique to determine c independent mapping functions {ƒ

i^L, i=1, 2, . . . c}, based on the respective subsets C_i of the training set T.

4. The method of claim 3, wherein each said mapping function is encoded in at least one neural network.

5. The method of claim 3, wherein step (g) further comprises the steps of:

(i) for an additional input pattern p, determining a set of n attributes x, x ∈

Rⁿ;

(ii) determining the distance of x from each said reference point {c_i};

(iii) identifying the reference point c_j closest to x; and

(iv) mapping x→

y, y∈

R^m, using the mapping function ƒ

j^L associated with the reference point c_j identified in step (iii).

6. The method of claim 5, wherein each said mapping function is encoded in at least one neural network.

7. The method of claim 3, wherein step (i) is performed using a clustering algorithm.

8. The method of claim 1, wherein step (f) further comprises the steps of:

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

R^m};

(ii) 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}};

(iii) using a supervised machine learning technique to determine c independent local mapping functions {ƒ

i^L, i=1, 2, . . . c}, based on the respective subsets C_i of the training set T; and

(iv) using a supervised machine learning technique to determine a global mapping function ƒ

^G, based on the entire training set T.

9. The method of claim 8, wherein each said mapping function is encoded in at least one neural network.

10. The method of claim 8, wherein step (g) further comprises the steps of:

(i) for an additional input pattern p, determining a set of n attributes x, x∈

Rⁿ;

(ii) mapping x→

y′

, y′

∈

R^m, using the global mapping function ƒ

^G;

(iii) determining the distance of y′

to each reference point in {c_i};

(iv) identifying the reference point c_j closest to y′

; and

(v) mapping x→

y′

, y′

∈

R^m, using the local mapping function ƒ

_j^L associated with the reference point c_j identified in step (iv).

11. The method of claim 10, wherein each said mapping function is encoded in at least one neural network.

12. The method of claim 8, wherein step (i) is performed using a clustering algorithm.

13. The method of claim 1, wherein step (c) further comprises the steps of:

(i) selecting a subset of patterns from {p_i};

(ii) revising the positions of the images of said selected subset of patterns in the m-dimensional space based on the relationships between said selected subset of patterns determined in step (b); and

(iii) repeating steps (i) and (ii) for additional subsets of patterns from {p_i}.

14. The method of claim 1, wherein step (d) comprises the step of:

(i) determining a set of n attributes for each pattern in said subset of patterns {p_i}, {x_i, i=1, 2, . . . k, x_i ∈

Rⁿ), wherein said attributes represent the relationships of each pattern in said subset of patterns with respect to n other reference patterns.

15. The method of claim 1, wherein step (b) comprises the step of receiving pairwise relationship data from a subject.

16. The method of claim 15, wherein step (b) comprises the steps of:

(1) randomly selecting two patterns from the plurality of patterns;

(2) presenting the two patterns to at least one subject; and

(3) receiving pairwise relationship data from said subject about the patterns.

17. The method of claim 16, further comprising the step of:

(4) repeating steps (b)(1) through (b)(3) for additional pairs of patterns.

18. The method of claim 17, wherein step (b) further comprises the step of receiving data about the subjects providing the pairwise relationship data.

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

(1) receiving pairwise relationship data via a communications path coupled to a computer; and

(2) storing the received pairwise relationship data in a memory.

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

(1) selecting a pair of patterns for similarity comparison;

(2) transmitting information about the selected pair of patterns to a remote computer system; and

(3) receiving pairwise relationship data about the selected pair of patterns from the remote computer system.

21. The method of claim 20, further comprising the step of:

(4) repeating steps (b)(1) through (b)(3) for additional pairs of compounds.

22. The method of claim 21, wherein step (b)(1) comprises the step of selecting the pair of patterns at random.

23. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor to obtain pairwise relationship data about the selected pair of patterns, wherein each pattern represents a compound selected from a database of compounds, said computer program logic comprising:

a selecting procedure that enables the processor to select a plurality of patterns from a database for similarity;

a transmitting procedure that enables a processor to transmit selected patterns to a remote computer for similarity comparison; and

a receiving procedure that enables the processor to receiving similarity data about patterns transmitted to the remote computer.

24. The computer program product of claim 23, further comprising:

a storing procedure that enables the processor to store received similarity data for subsequent retrieval.

25. The computer program product of claim 24, wherein said selecting procedure randomly selecting patterns from the database.

26. A system for mapping a set of input patterns to an m-dimensional space, wherein each pattern represents a compound selected from a database of compounds, the system comprising:

means for selecting k patterns from said set of input patterns to form a subset of patterns {p_i, i=1, . . . , k};

means for determining at least some pairwise relationships between at least some of the patterns in said subset of patterns {p_i};

means for mapping the patterns {p_i} into a set of images in an m-dimensional space {p_i→

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

R^m) so that at least some of the pairwise distances between at least some of the images {y_i} are representative of the relationships of the respective patterns {p_i};

means for determining a set of n attributes for each pattern in said subset of patterns {p_i}, {x_i, i=1, 2, . . . k, x_i ∈

Rⁿ};

means for forming a training set T={x_i, y_ii=1, 2, . . . k};

means for using a supervised machine learning technique to determine a mapping function based on the training set T; and

means for using said mapping function determined in step (f) to map additional patterns.

27. A computer program product comprising a computer useable medium having computer program logic recorded thereon for enabling a processor to obtain map a set of input patters to an m-dimensional space, wherein each pattern represents a compound selected from a database of compounds, said computer program logic comprising:

a procedure that selects k patterns from said set of input patterns to form a subset of patterns {p_i, i=1, . . . , k};

a procedure that determines at least some pairwise relationships between at least some of the patterns in said subset of patterns {p_i};

a procedure that maps the patterns {p_i} into a set of images in an m-dimensional space {p_i→

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

R^m) so that at least some of the pairwise distances between at least some of the images are representative of the relationships of the respective patterns {p_i};

a procedure that determines a set of n attributes for each pattern in said subset of patterns {p_i}, {x_i, i=1, 2, . . . k, x_i ∈

Rⁿ};

a procedure that forms a training set T={x_i, y_i), i=1, 2, . . . k };

a procedure that uses a supervised machine learning technique to determine a mapping function based on the training set T; and

a procedure that uses said mapping function determined in step (f) to map additional patterns.