Enhanced max margin learning on multimodal data mining in a multimedia database

1. A method for multimodal data mining, comprising:

defining a multimodal data set comprising image information;

representing image information of a data object as a set of feature vectors in a feature space representing a plurality of constraints for each training example, wherein the feature vectors comprise a joint feature representation associated with Lagrange multipliers, the feature vectors being partitioned into a dual variable set comprising two partitions and having non-image representations associated with the respective image data object;

clustering in the feature space to group similar features;

associating a non-image representation with a respective data object based on the clustering;

determining a joint feature representation of a respective data object as a mathematical weighted combination of a set of components of the joint feature representation;

optimizing a weighting for a plurality of components of the mathematical weighted combination with respect to a prediction error between a predicted classification and a training classification by iteratively solving a Lagrange dual problem, with an automated data processor, by partitioning the Lagrange multipliers into an active set and an inactive set, wherein the Lagrange multiplier for a member of the active set is greater than or equal to zero and the Lagrange multiplier for a member of the inactive set is zero, the iteratively solving comprising moving members of the active set having zero-valued Lagrange multipliers to the inactive set without changing an objective function, and moving members of the inactive set to the active set which result in a decrease in the objective function; and

employing the mathematical weighted combination for automatically classifying a new data object,

wherein:

the set of feature vectors in the feature space represents a plurality of constraints for each training example, the feature vectors comprise joint feature representation defined by Φ, having a Lagrange multiplier μ i, y for each constraint to form the Lagrangian, wherein i and j denote different elements of a respective set, y i is an annotation and a member of the set Y, x i and x j are each annotations and members of the set X, superscript T denotes a transpose matrix, n is the number of elements in the respective set, y represents a prediction of y i from the set Y i , {tilde over (y)} is an operator of y, α=Σ i, y μ i, y Φ i,y i , y , l( y ,y i ) is a loss function defined as the number of the different entries in vectors y and y i , Φ i,yi, y =Φ i (y i )−Φ i ( y ), and a kernel function K((x i , y ),(x j ,{tilde over (y)}))=<Φ i,yi, y , Φ j,yj, y >, the feature vectors being partitioned into a dual variable set μ comprising two partitions, μ B and μ N and non-image representations S associated with the respective image data object, the dual variable set μ having i examples such that μ=[μ 1 T . . . μ n T ] T and S=[S 1 T . . . S n T ] T , wherein the lengths of μ and S are the same, and A i is defined as a vector which has the same length as that of μ, where A i , y =1 and A j , y =0 for j≠i, such that A=[A 1 . . . A n ] T , matrix D represents a kernel matrix where each entry is K((x i , y ), (x j ,{tilde over (y)})), and C represents a vector where each entry is a constant C;

the feature vectors comprise a dual variable set μ comprising labeled examples which is decomposed into two partitions, μ B and μ N ; and

said optimizing comprises iteratively solving for each member of the set:

min

⁢

1

2

⁢

μ

T

⁢

D

⁢

⁢

μ

-

μ

T

⁢

S

;

⁢

⁢

and

s

.

t

.

A

⁢

⁢

μ

⪯

C

μ

B

≽

0

,

⁢

μ

N

=

0

while there exist μ i, y ∈μ B such that μ i, y =0, moving that variable to partition μ N ;

while there exists μ i, y ∈μ N satisfying the condition

∃ i, Σ y μ i, y <C

∃μ i, y ∈μ N , α T Φ i,y i , y −l ( y ,y i )<0,

moving that variable to partition μ B ; and

if no such μ i, y ∈μ N exists, ceasing an iteration.

2. The method according to claim 1 , wherein the multimodal data set comprises image information and annotations of the image information.

3. The method according to claim 1 , wherein the dual variable set comprises a semantic variable.

4. The method according to claim 1 , wherein the dual variable set comprises linguistic data.

5. The method according to claim 1 , wherein the dual variable set comprises image data.

6. The method according to claim 1 , wherein the dual variable set comprises audio data.

7. The method according to claim 1 , wherein the dual variable set comprises a semantic variable and an image variable.

8. The method according to claim 1 , further comprising using the partitions to inference between two different examples in the set μ.

9. The method according to claim 1 , further comprising annotating at least one example based on the partitions.

10. The method according to claim 1 , further comprising receiving a query representing one of the dual variables, and identifying the examples which correspond to the query.

11. The method according to claim 1 , wherein one of the variables is a linguistic variable, and the other of the variables comprises image data, further comprising receiving at least one word as a query and responding to the query by retrieving examples having images which correspond to that word.

12. The method according to claim 1 , wherein a first of the variables represents a descriptive annotation of the second of the variables.

13. The method according to claim 1 , wherein at least one of the labeled examples comprises representations of a plurality of objects, and wherein a label variable comprises a structured output word space.

14. A system for multimodal data mining, comprising:

an input adapted to receive a multimodal data set comprising image information;

an automated processor, configured to:

represent image information of a data object as a set of feature vectors in a feature space, representing a plurality of constraints for each training example, wherein the feature vectors comprise joint feature representation associated with Lagrange multipliers, the feature vectors being partitioned into a dual variable set comprising two partitions and having non-image representations associated with the respective image data object;

perform clustering in the feature space to group similar features;

associate a non-image representation with a respective image data object based on the clustering;

determine a joint feature representation of a respective data object as a mathematical weighted combination of a set of components of the joint feature representation;

optimize a weighting for a plurality of components of the mathematical weighted combination with respect to a prediction error between a predicted classification and a training classification, by iteratively solving a Lagrange dual problem, with an automated data processor, by partitioning the Lagrange multipliers into an active set and an inactive set, wherein the Lagrange multiplier for a member of the active set is greater than or equal to zero and the Lagrange multiplier for a member of the inactive set is zero, the iteratively solving comprising moving members of the active set having zero-valued Lagrange multipliers to the inactive set without changing an objective function, and moving members of the inactive set to the active set which result in a decrease in the objective function; and

an output from the automated processor, configured to communicate a classification of a new data object based on the mathematical weighted combination,

wherein:

the set of feature vectors in the feature space represents a plurality of constraints for each training example, the feature vectors comprise joint feature representation defined by Φ, having a Lagrange multiplier μ i, y for each constraint to form the Lagrangian, wherein i and j denote different elements of a respective set, y i is an annotation and a member of the set Y, x i and x j are each annotations and members of the set X, superscript T denotes a transpose matrix, n is the number of elements in the respective set, y represents a prediction of y i from the set Y i , {tilde over (y)} is an operator of y, α=Σ i, y μ i, y Φ i,y i , y , l( y ,y i ) is a loss function defined as the number of the different entries in vectors y and y i , Φ i,yi, y =Φ i (y i )−Φ i ( y ), and a kernel function K((x i , y ),(x j ,{tilde over (y)}))=<Φ i,yi, y >, the feature vectors being partitioned into a dual variable set μ comprising two partitions, μ B and μ N and non-image representations S associated with the respective image data object, the dual variable set μ having i examples such that μ=[μ 1 T . . . μ n T ] T and S=[S 1 T . . . S n T ] T , wherein the lengths of μ and S are the same, and A 1 is defined as a vector which has the same length as that of μ, where A i , y =1 and A j , y =0 for j≠i, such that A=[A 1 . . . A n ] T , matrix D represents a kernel matrix where each entry is K((x i , y ), (x j ,{tilde over (y)})), and C represents a vector where each entry is a constant C;

the feature vectors comprise a dual variable set μ comprising labeled examples which is decomposed into two partitions, μ B and μ N ; and

said optimizing comprises iteratively solving for each member of the set:

min

⁢

1

2

⁢

μ

T

⁢

D

⁢

⁢

μ

-

μ

T

⁢

S

;

⁢

and

s

.

t

.

A

⁢

⁢

μ

⪯

C

μ

B

≽

0

,

⁢

μ

N

=

0

while there exists μ i, y ∈μ B such that μ i, y =0, moving that variable to partition μ N ;

while there exists μ i, y ∈μ N satisfying the condition

∃ i, Σ y μ i, y <C

∃μ i, y ∈μ N , α T Φ i,y i , y −l ( y ,y i )<0,

moving that variable to partition μ B ; and

if no such μ i, y ∈μ N exists, ceasing an iteration.

15. The system according to claim 14 , wherein the multimodal data set comprises image information and annotations of the image information.

16. The system according to claim 14 , wherein one of the variables is a linguistic variable, and the other of the variables comprises image data, the automated processor being further configured to receive at least one word as a query and to respond to the query by retrieving examples having images which correspond to that word.

17. A method for multimodal data processing, comprising:

representing image information of a data object as a set of feature vectors in a feature space, representing a plurality of constraints for each training example, wherein the feature vectors comprise joint feature representation associated with Lagrange multipliers, the feature vectors being partitioned into a dual variable set comprising two partitions and having non-image representations associated with the respective image data object;

clustering data objects having similar features in the feature space together;

associating non-image information with a respective image data object based on the clustering;

representing a respective data object as a mathematical weighted combination of a set of joint feature representation components;

optimizing a weighting for a plurality of components of the mathematical weighted combination with respect to a prediction error between a predicted classification and a training classification, by iteratively solving a Lagrange dual problem, with an automated data processor, by partitioning the Lagrange multipliers into an active set and an inactive set, wherein the Lagrange multiplier for a member of the active set is greater than or equal to zero and the Lagrange multiplier for a member of the inactive set is zero, the iteratively solving comprising moving members of the active set having zero-valued Lagrange multipliers to the inactive set without changing an objective function, and moving members of the inactive set to the active set which result in a decrease in the objective function; and

employing the mathematical weighted combination for automatically classifying a new data object,

wherein:

the set of feature vectors in the feature space represents a plurality of constraints for each training example, the feature vectors comprise joint feature representation defined by Φ, having a Lagrange multiplier μ i, y for each constraint to form the Lagrangian, wherein i and j denote different elements of a respective set, y i is an annotation and a member of the set Y, x i and x j are each annotations and members of the set X, superscript T denotes a transpose matrix, n is the number of elements in the respective set, y represents a prediction of y i from the set Y i , {tilde over (y)} is an operator of y, α=Σ i, y μ i, y Φ i,y i , y , l( y ,y i ) is a loss function defined as the number of the different entries in vectors y and y i , Φ i,yi, y =Φ i (y i )−Φ i ( y ), and a kernel function K((x i , y ),(x j ,{tilde over (y)}))=<Φ i,yi, y >, the feature vectors being partitioned into a dual variable set μ comprising two partitions, μ B and μ N and non-image representations S associated with the respective image data object, the dual variable set μ having i examples such that μ=[μ 1 T . . . μ n T ] T and S=[S 1 T . . . S n T ] T , wherein the lengths of μ and S are the same, and A 1 is defined as a vector which has the same length as that of μ, where A i , y =1 and A j , y =0 for j≠i, such that A=[A 1 . . . A n ] T , matrix D represents a kernel matrix where each entry is K((x i , y ), (x j ,{tilde over (y)})), and C represents a vector where each entry is a constant C;

the feature vectors comprise a dual variable set μ comprising labeled examples which is decomposed into two partitions, μ B and μ N ; and

said optimizing comprises iteratively solving for each member of the set:

min

⁢

1

2

⁢

μ

T

⁢

D

⁢

⁢

μ

-

μ

T

⁢

S

;

⁢

and

s

.

t

.

A

⁢

⁢

μ

⪯

C

μ

B

≽

0

,

⁢

μ

N

=

0

while there exists μ i, y ∈μ B such that μ i, y =0, moving that variable to partition μ N ;

while there exists μ i, y ∈μ N satisfying the condition

∃ i, Σ y μ i, y <C

∃μ i, y ∈μ N , α T Φ i,y i , y −l ( y ,y i )<0,

moving that variable to partition μ B ; and

if no such μ i, y ∈μ N exists, ceasing an iteration.

18. The method according to claim 17 , wherein the multimodal data set comprises image information and annotations of the image information.

19. The method according to claim 17 , wherein one of the variables is a linguistic variable, and the other of the variables comprises image data, further comprising receiving at least one word as a query and responding to the query by retrieving examples having images which correspond to that word.

20. The method according to claim 17 , further comprising annotating at least one example based on the partitions.