System and method for learning rankings via convex hull separation

• US 20070011121A1
• Filed: 06/01/2006
• Published: 01/11/2007
• Est. Priority Date: 06/03/2005
• Status: Abandoned Application

• Current Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Original Assignee: Siemens Medical Solutions USA Incorporated (Siemens AG)
• Inventors: Krishnan, Sriram, Krishnapuram, Balaji, Bi, Jinbo, Fung, Glenn, Rosales, Romer, Rao, R.
• Application Number:
  US11/444,606
• Publication Number:
  US 20070011121A1
• Time in Patent Office: Days
• US Class Current: 706/20
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines

Abstract

A method for finding a ranking function ƒ that classifies feature points in an n-dimensional space includes providing a plurality of feature points x_k derived from tissue sample regions in a digital medical image, providing training data A comprising training samples A^j where $A={\bigcup }_{j=1}^S\left(A^j={\left\{x_i^j\right\}}_{i=1}^{m_j}\right),$
providing an ordering E={(P,Q)|A^PA^Q} of at least some training data sets where all training samples x_iεA^P are ranked higher than any sample x_jεA^Q, solving a mathematical optimization program to determine the ranking function ƒ that classifies said feature points x into sets A. For any two sets Aⁱ, A^j, AⁱA^j, and the ranking function ƒ satisfies inequality constraints ƒ(x_i)≦ƒ(x_j) for all x_iεconv(Aⁱ) and x_jεconv(A^j), where conv(A) represents the convex hull of the elements of set A.

Claims

1. A method for finding a ranking function ƒ

that classifies feature points in an n-dimensional space, said method comprising the steps of;

providing a plurality of feature points x_k in an n-dimensional space Rⁿ, said feature points derived from a digital medical image;

providing training data A comprising a plurality of sets of training samples A^j wherein

$A={\bigcup <br><br>}_{j=1}^S<br><br>\left(A^j={\left\{x_i^j\right\}}_{i=1}^{m_j}\right),$

wherein S is a number of sets and a j^th set A^j includes m_j samples x_i^j;

providing an ordering E={(P,Q)|A^PA^Q} of at least some of said training data sets wherein all training samples x_iε

A^P are ranked higher than any sample x_jε

A^Q;

solving a mathematical optimization program to determine said ranking function ƒ

that classifies said feature points x into said plurality of sets A, wherein for any two sets Aⁱ, A^j, wherein AⁱA^j, the ranking function ƒ

satisfies inequality constraints ƒ

(x_i)≦

ƒ

(x_j) for all x_iε

conv(Aⁱ) and x_iε

conv(A^j), wherein conv(A) represents the convex hull of the elements of set A.

2. The method of claim 1, wherein the ranking function is a linear function of the feature points x of the form w′

x, wherein w is an n-dimensional vector.

3. The method of claim 2, wherein said mathematical optimization program includes slack variables y greater or equal to zero for non-separable sets wherein not all inequality constraints can be satisfied, wherein said slack variables are a measure of the extent to which constraints are violated in said mathematical program.

4. The method of claim 3, comprising one slack variable yⁱ for each of said training samples x_i, wherein any training sample point inside the convex hull of any set is associated with a slack variable equal to a convex combination of yⁱ with coefficients λ

.

5. The method of claim 4, wherein said mathematical program is of form

6. The method of claim 4, wherein said linear inequality constraints are equalities represented by

7. The method of claim 6, further comprising solving said mathematical program by means of least squares.

8. The method of claim 6, wherein μ

is approximately one.

9. The method of claim 1, wherein the number of sets is two, represented by A⁺ and A⁻

, wherein A⁻

A⁺, and wherein the ranking function satisfies the constraints

10. The method of claim 9, wherein A⁺ and A⁻

are non-separable, and wherein the ranking function satisfies

w′

A′

⁻

λ

⁻

−

w′

A′

⁺λ

⁺≦

−

1+(λ

⁻

y⁻

+λ

⁻

+λ

⁺y⁺), wherein y⁺, y⁻

are slack variables greater than or equal to zero.

11. The method of claim 1, wherein said feature points represent tissue sample regions.

12. The method of claim 11, further comprising using said ranking to determine a probability of said tissue sample being diseased.

13. The method of claim 11, further comprising using said ranking to determine a malignancy of diseased tissue sample regions.

14. The method of claim 11, wherein said tissue sample regions are derived from a plurality of patients, and further comprising using said ranking to sort said plurality of patients according to a predetermined criteria.

15. The method of claim 1, wherein said ordering of at least some of said training data sets is provided by a physician.

16. The method of claim 1, wherein said training samples are assigned to sets based on the results of a diagnostic test.

17. The method of claim 1, wherein said training samples are assigned to sets by a physician.

18. The method of claim 1, wherein said feature points are derived from a patient'"'"'s electronic medical record.

19. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform the method steps for finding a ranking function ƒ

that classifies feature points in an n-dimensional space, said method comprising the steps of;

providing a plurality of feature points x_k in an n-dimensional space Rⁿ, said feature points derived from a digital medical image;

providing training data A comprising a plurality of sets of training samples A^j wherein

$A={\bigcup <br><br>}_{j=1}^S<br><br>\left(A^j={\left\{x_i^j\right\}}_{i=1}^{m_j}\right),$

wherein S is a number of sets and a j^th set A^j includes m_j samples x_i^j;

providing an ordering E={(P,Q)|A^PA^Q} of at least some of said training data sets wherein all training samples x_iε

A^P are ranked higher than any sample x_jε

A^Q;

solving a mathematical optimization program to determine said ranking function ƒ

that classifies said feature points x into said plurality of sets A, wherein for any two sets Aⁱ, A^j, wherein AⁱA^j, the ranking function ƒ

satisfies inequality constraints ƒ

(x₁)≦

ƒ

(x_j) for all x_iε

conv(Aⁱ) and x_jε

conv(A^j), wherein conv(A) represents the convex hull of the elements of set A.

20. The computer readable program storage device of claim 19, wherein the ranking function is a linear function of the feature points x of the form w′

x, wherein w is an n-dimensional vector.

21. The computer readable program storage device of claim 20, wherein said mathematical optimization program includes slack variables y greater or equal to zero for non-separable sets wherein not all inequality constraints can be satisfied, wherein said slack variables are a measure of the extent to which constraints are violated in said mathematical program.

22. The computer readable program storage device of claim 21, comprising one slack variable yⁱ for each of said training samples x_i, wherein any training sample point inside the convex hull of any set is associated with a slack variable equal to a convex combination of yⁱ with coefficients λ

.

23. The computer readable program storage device of claim 22, wherein said mathematical program is of form

24. The computer readable program storage device of claim 22, wherein said linear inequality constraints are equalities represented by

25. The computer readable program storage device of claim 24, the method further comprising solving said mathematical program by means of least squares.

26. The computer readable program storage device of claim 24, wherein μ

is approximately one.

27. The computer readable program storage device of claim 19, wherein the number of sets is two, represented by A⁺ and A⁻

, wherein A⁻

A⁺, and wherein the ranking function satisfies the constraints

28. The computer readable program storage device of claim 27, wherein A⁺ and A⁻

are non-separable, and wherein the ranking function satisfies

w′

A′

⁻

λ

⁻

−

w′

A′

⁺λ

⁺≦

−

1+(λ

⁻

y⁻

+λ

⁺y⁺), wherein y⁺, y⁻

are slack variables greater than or equal to zero.

29. The computer readable program storage device of claim 19, wherein said feature points represent tissue sample regions.

30. The computer readable program storage device of claim 29, the method further comprising using said ranking to determine a probability of said tissue sample being diseased.

31. The computer readable program storage device of claim 29, the method further comprising using said ranking to determine a malignancy of diseased tissue sample regions.

32. The computer readable program storage device of claim 29, wherein said tissue sample regions are derived from a plurality of patients, and further comprising using said ranking to sort said plurality of patients according to a predetermined criteria.

33. The computer readable program storage device of claim 19, wherein said ordering of at least some of said training data sets is provided by a physician.

34. The computer readable program storage device of claim 19, wherein said training samples are assigned to sets based on the results of a diagnostic test.

35. The computer readable program storage device of claim 19, wherein said feature points are derived from a patient'"'"'s electronic medical record.

36. The computer readable program storage device of claim 19, wherein said training samples are assigned to sets by a physician.

37. A method for finding a ranking function ƒ

that classifies feature points in an n-dimensional space, said feature points derived from a digital medical image wherein said feature points represent tissue sample regions, said method comprising the steps of;

providing a plurality of feature points x_k in an n-dimensional space Rⁿ;

providing training data A comprising a plurality of sets of training samples A^j wherein

$A={\bigcup <br><br>}_{j=1}^S<br><br>\left(A^j={\left\{x_i^j\right\}}_{i=1}^{m_j}\right),$

wherein S is a number of sets and a j^th set A^j includes m_j samples x_i^j;

solving a mathematical optimization program to determine said ranking function ƒ

that classifies said feature points x into said plurality of sets A, wherein for any two sets Aⁱ, A^j, wherein AⁱA^j, the ranking function ƒ

is a linear function of the feature points x of the form w′

x, wherein w is an n-dimensional vector, the ranking function satisfying inequality constraints ƒ

(x_i)≦

ƒ

(x_j) for all x_iε

conv(Aⁱ) and x_iε

conv(A^j), wherein conv(A) represents the convex hull of the elements of set A.

38. The method of claim 37, further comprising providing an ordering E={(P,Q)|A^PA^Q} of at least some of said training data sets wherein all training samples x_iε

A^P are ranked higher than any sample x_iε

A^Q.