System and method for multiple instance learning for computer aided detection

1. A computer-implemented method of training a classifier for computer aided detection of digitized medical images, comprising the steps of:

providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in said medical image, wherein said feature samples include texture, shape, intensity, and contrast of said region-of-interest, wherein each region-of-interest has been labeled as either malignant or healthy; and

training said classifier on said plurality of bags of feature samples, subject to the constraint that at least one point in a convex hull of each bag, corresponding to said feature sample, is correctly classified according to the label of the associated region-of-interest,

wherein said classifier is trained on a computer, and wherein said classifier is trained by minimizing the expression vE(ξ)+Φ(ω,η)+Ψ(λ) over arguments (ξ,ω,η,λ)εR r+n+1+γ

subject to the conditions

ξ i =d i −(λ j i B j i ω−eη ),

ξεΩ,

e′λ j i =1,

0≦λ j i ,

wherein ξ={ξ 1 , . . . ,ξ r } are slack terms, E:R r R represents a loss function, ω is a hyperplane coefficient, η is the bias term, λ is a vector containing the coefficients of the convex combination that defines the representative point of bag i in class j wherein 0≦λ j i ,e′λ j i =1, γ is the total number of convex hull coefficients corresponding to the representative points in class j,Φ:R (n+1) R is a regularization function on the hyperplane coefficients, Ψ is a regularization function on the convex combination coefficients λ j i , Ω represents a feasible set for ξ matrix B j i εR m j i ×n ,i=1, . . . ,r j , jε{±1} is the i th bag of class label j, r is the total number of representative points, n is the number of features, m j i is the number of rows in B, vector dε{±1} r j represents binary bag-labels for the malignant and healthy sets, respectively, and the vector e represents a vector with all its elements equal to one.

2. The method of claim 1 , wherein E(ξ)=∥(ξ) + ∥ 2 2 ,Φ(ω,η)=∥(ω,η)∥ 2 2 and Ω=R r + , wherein ξ + and r + are respectively slack variables and points labeled by +1.

3. The method of claim 1 , wherein E(ξ)=∥(ξ) ∥ 2 2 ,Φ(ω,η)=∥(ω,η)∥ 2 2 and Ω=R r .

4. The method of claim 1 , wherein v=1,E(ξ)=∥ξ∥ 2 2 and Ω={ξ:e′ξ j =0,jε{±1 }}.

5. The method of claim 4 , further comprising replacing ξ i by d i −(λ j i B j i ω−eη) in the objective function, replacing equality constraints e′ξ j =0 by ω′(μ + −μ − )=2, wherein said classifier is trained by minimizing the expression ω T S W ω+Φ(ω)+Ψ(λ) with respect to the arguments (ω,λ)εR n+γ subject to the conditions

ω T (μ + −μ − )= b,

e′λ j i =1,

0≦λ j i ,

wherein

S

W

=

∑

j

∈

{

±

1

}

⁢

1

r

j

⁢

(

X

j

-

μ

j

⁢

e

′

)

⁢

(

X

j

-

μ

j

⁢

e

′

)

T

is the within-class scatter matrix,

μ

j

=

1

r

j

⁢

X

j

⁢

e

is the mean for class j, X j εR r j ×n is a matrix containing the r j representative points on an n-dimensional space such that the row of X j denoted by b j i =B j i λ j i is the representative point of bag i in class j where i={1, . . . ,r j )}, jε{±1}, and μ + and μ − are the mean values for the positive and negative labeled classes, respectively.

6. The method of claim 5 , further comprising:

initializing

λ

i

⁢

⁢

0

=

e

m

i

,

∀

i

=

1

,

…

⁢

,

r

and a counter c=0,

for a fixed λ ic ,∀i=1, . . . ,r, minimizing the expression ω T S W ω+Φ(ω) to solve for w c

subject to the condition that ω T (μ + −μ − )=b;

for a fixed ω=ω c , minimizing the expression λ T S W λ+Ψ(λ) to solve for λ ic , ∀i=1, . . . ,r,

subject to the condition that

λ T ( μ + − μ − )= b,

e′λ j i =1,

0≦λ j i ,

wherein S W and μ are defined with X j replaced by X j wherein X j εR r j ×γ is a matrix containing r j new points on a γ-dimensional space wherein the row of X j denoted by b j i is a vector with its nonzero elements set to B j i ω c ; and

if ∥λ 1(c+1) −λ 1c , . . . ,λ r(c+1) −λ rc ∥ 2 is greater than a predefined tolerance, replacing λ ic by λ i(c+1) and c by c+1 and repeating the two previous steps.

7. The method of claim 6 , further comprising setting convex-hull coefficients of negative bags to be 1.

8. The method of claim 6 , further comprising transforming said feature samples into a higher dimensional space using a kernel transformation (X{+}, X) for the positive class and K(X{−}, X) for the negative class, wherein X{+}, X{−}, and X are data matrices for positive, negative and all samples respectively, wherein each row is a sample vector in these matrices, wherein if the size of X is too large, subsampling a random subset from said original feature samples.

9. The method of claim 5 , wherein Φ(ω)=ε∥ω∥ 2 2 and Ψ(λ)=ε∥λ∥ 2 2 , wherein ε is a positive regularization parameter.

10. A method of training a classifier for computer aided detection of digitized medical images, comprising the steps of:

providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in said medical image, wherein each region-of-interest has been labeled as either malignant or healthy, wherein each bag is represented by a matrix B j i εR m j i ×n , i=1, . . . ,r j,jε{± 1} is the i th bag of class label j, r is the total number of representative points, n is the number of features, m j i is the number of rows in B; and

training said classifier by minimizing the expression ∥ξ∥ 2 2 +Φ(ω,η)+Ψ(λ) over arguments (ξ,ω,η,λ)εR r+n+1+γ subject to the conditions

ξ i =d i −(λ j i B j i ω−eη ),

e′ξ j =0,

e′λ j i =1,

0≦λ j i ,

wherein ξ={ξ, . . . ,ξ r } are slack terms, ω is a hyperplane coefficient, η is the bias offset from the origin term, λ is a vector containing the coefficients of the convex combination that defines the representative point of bag i in class j wherein 0≦λ j i ,e′λ j i =1, γ is the total number of convex hull coefficients corresponding to the representative points in class j, Φ:R (n+1) R is a regularization function on the hyperplane coefficients, Ψ is a regularization function on the convex combination coefficients λ j i , matrix B j i εR m j i ×n ,i=1, . . . ,r j , jε{±1} is the i th bag of class label j, r is the total number of representative points, n is the number of features, m j i is the number of rows in B, vector dε{±1} r j represents binary bag-labels for the malignant and healthy sets, respectively, and the vector e represents a vector with all its elements equal to one.

11. A program storage device readable by a computer, tangibly embodying a non-transitory program of instructions executable by the computer to perform the method steps for training a classifier for computer aided detection of digitized medical images, said method comprising the steps of:

providing a plurality of bags, each bag containing a plurality of feature samples of a single region-of-interest in said medical image, wherein said feature samples include texture, shape, intensity, and contrast of said region-of-interest, wherein each region-of-interest has been labeled as either malignant or healthy; and

training said classifier on said plurality of bags of feature samples, subject to the constraint that at least one point in a convex hull of each bag, corresponding to said feature sample, is correctly classified according to the label of the associated region-of-interest

wherein said classifier is trained by minimizing the expression vE(ξ)+Φ(ω,η)+Ψ(λ) over arguments (ξ,ω,η,λ)εR r+n+1+γ

subject to the conditions

ξ i =d i −(λ j i B j i ω−eη ),

ξεΩ,

e′λ j i −1,

0≦λ j i ,

wherein ξ={ξ 1 , . . . ,ξ r } are slack terms, E:R r R represents a loss function, ω is a hyperplane coefficient, η is the bias term, λ is a vector containing the coefficients of the convex combination that defines the representative point of bag i in class j wherein 0≦λ j i ,e′λ j i =1, γ is the total number of convex hull coefficients corresponding to the representative points in class j, Φ:R (n+1) R is a regularization function on the hyperplane coefficients, Ψ is a regularization function on the convex combination coefficients λ j i , Ω represents a feasible set for ξ, matrix B j i εR m j i ,i=1, . . . ,r j , jε{±1} is the i th bag of class label j, r is the total number of representative points, n is the number of features, m j i is the number of rows in B, vector dε{±1} r j represents binary bag-labels for the malignant and healthy sets, respectively, and the vector e represents a vector with all its elements equal to one.

12. The computer readable program storage device of claim 11 , wherein E(ξ)=∥(ξ) + ∥ 2 2 ,Φ(ω,η)=∥(ω,η)∥ 2 2 and Ω=R r + , wherein ξ + and r + are respectively slack variables and points labeled by +1.

13. The computer readable program storage device of claim 11 , wherein E(ξ)=∥(ξ)∥ 2 2 ,Φ(ω,η)=∥(ω,η)∥ 2 2 and Ω=R r .

14. The computer readable program storage device of claim 11 , wherein v=1, E(ξ)=∥ξ∥ 2 2 and Ω={ξ:e′ξ j =0,jε{±1}}.

15. The computer readable program storage device of claim 14 , the method further comprising replacing ξ i by d i −(λ j i B j i ω−eη) in the objective function, replacing equality constraints e′ξ j =0 by ω′(μ + −μ − )=2, wherein said classifier is trained by minimizing the expression ω T S W ω+Φ(ω)+Ψ(λ) with respect to the arguments (ω,λ)εR n+γ

subject to the conditions

ω T (μ + −μ − )= b,

e′λ j i =1,

0≦λ j i ,

wherein

S

W

=

∑

j

∈

{

±

1

}

⁢

1

r

j

⁢

(

X

j

-

μ

j

⁢

e

′

)

⁢

(

X

j

-

μ

j

⁢

e

′

)

T

is the within-class scatter matrix,

μ

j

=

1

r

j

⁢

X

j

⁢

e

is the mean for class j, X j εR r j ×n is a matrix containing the r j representative points on an n-dimensional space such that the row of X j denoted by b j i =B j i λ j i is the representative point of bag i in class j where i={1, . . . ,r j }, jε{±1}, and μ + and μ − are the mean values for the positive and negative labeled classes, respectively.

16. The computer readable program storage device of claim 15 , the method further comprising:

initializing

λ

i

⁢

⁢

0

=

e

m

i

,

∀

i

=

1

,

…

⁢

,

r

and a counter c=0,

for a fixed λ ic ,∀i=1, . . . ,r, minimizing the expression ω T S W ω+Φ(ω) to solve for w c

subject to the condition that ω T (μ + −μ − )=b;

for a fixed ω=ω c , minimizing the expression λ T S W λ+Ψ(λ) to solve for λ ic ,∀i=1, . . . ,r,

subject to the condition that

λ T ( μ + − μ − )= b,

e′λ j i =1,

0≦λ j i ,

wherein S W , and μ are defined with X j replaced by X j wherein X j εR r j ×γ is a matrix containing r j new points on a γ-dimensional space wherein the row of X j denoted by b j i is a vector with its nonzero elements set to B j i ω c ; and

if ∥λ 1(c+1) −λ 1c , . . . ,λ r(c+1) −λ rc ∥ 2 is greater than a predefined tolerance, replacing λ ic by λ i(c+1) and c by c+1 and repeating the two previous steps.

17. The computer readable program storage device of claim 16 , the method further comprising setting convex-hull coefficients of negative bags to be 1.

18. The computer readable program storage device of claim 16 , the method further comprising transforming said feature samples into a higher dimensional space using a kernel transformation (X{+}, X) for the positive class and K(X{−}, X) for the negative class, wherein X{+}, X{−}, and X are data matrices for positive, negative and all samples respectively, wherein each row is a sample vector in these matrices, wherein if the size of X is too large, subsampling a random subset from said original feature samples.

19. The computer readable program storage device of claim 15 , wherein Φ(ω)=ε∥ω∥ 2 2 and Ψ(λ)=ε∥λ∥ 2 2 , wherein ε is a positive regularization parameter.