Sparse class representation with linear programming

• US 9,189,735 B2
• Filed: 12/17/2012
• Issued: 11/17/2015
• Est. Priority Date: 12/17/2012
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Ni, Karl, Bouman, Katherine L., Bliss, Nadya T.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): LAMARDO, VIKER ALEJANDRO
• Application Number:
  US13/716,940
• Publication Number:
  US 20140172764A1
• Time in Patent Office: 1,065 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

A method, apparatus and computer program product for providing sparse class representation with linear programming is provided. A first model is built using a positive data set. A second model is built using a negative data set. Linear programming is used to distinguishing the first model from the second model to determine a set of salient features for a filter for use as an image classifier.

Claims

1. A computer-implemented method in which a computer system performs operations comprising:

building a first model using a positive data set;

building a second model using a negative data set; and

using linear programming, distinguishing said first model from said second model to determine a set of features that make the object stand apart from rest of image data for a filter for use as an image classifier and wherein said using linear programming comprises using the minimization formula

2. The method of claim 1 wherein said using linear programming further comprises using a first constraint

3. The method of claim 2 wherein said using linear programming further comprises

using a second constraint 0≦

β

_ij≦

t_i≦

1.

4. The method of claim 3 wherein said using a second constraint further comprises

using β

^T1=1.

5. The method of claim 1 further comprising using said filter to recognize image content in an image.

6. The method of claim 2 wherein the choice of a value for λ

is based on at least one of the group consisting of expected clustering structure, inherent feature similarity, and a size of the data set.

7. The method of claim 1 wherein said positive data set is considered minimally supervised wherein said positive data set includes images having the object wherein the object is not identified in said images.

18. The method of claim 1 wherein said salient features comprises features that make an object stand out from a remainder of an image.

8. A non-transitory computer readable storage medium having computer readable code thereon for sparse class representation using linear programming, the medium including instructions in which a computer system performs operations comprising:

building a first model using a positive data set;

building a second model using a negative data set; and

using linear programming, distinguishing said first model from said second model to determine a set of features that make the object stand apart from rest of image data for a filter for use as an image classifier and wherein said using linear programming comprises using the minimization formula

9. The computer readable storage medium of claim 8 further comprising instructions wherein said using linear programming further comprises

using a first constraint

10. The computer readable storage medium of claim 9 further comprising instructions wherein said using linear programming further comprises using a second constraint 0≦

β

_ij≦

t_i≦

1.

11. The computer readable storage medium of claim 10 further comprising instructions wherein said using a second constraint further comprises using β

^T1=1.

12. The computer readable storage medium of claim 8 further comprising further comprising instructions for using said filter to recognize image content in an image.

13. The computer readable storage medium of claim 9 further comprising instructions wherein the choice of a value for λ

is based on at least one of the group consisting of expected clustering structure, inherent feature similarity, and a size of the data set.

14. The computer readable storage medium of claim 8 further comprising instructions wherein said positive data set is considered minimally supervised wherein said positive data set includes images having the object wherein the object is not identified in said images.

19. The computer readable medium of claim 8 wherein said salient features comprises features that make an object stand out from a remainder of an image.

15. A computer system comprising:

a memory;

a processor;

a communications interface;

an interconnection mechanism coupling the memory, the processor and the communications interface; and

wherein the memory is encoded with an application providing sparse class representation using linear programming, that when performed on the processor, provides a process for processing information, the process causing the computer system to perform the operations of;

building a first model using a positive data set;

building a second model using a negative data set; and

using linear programming, distinguishing said first model from said second model to determine a set of features that make the object stand apart from rest of image data for a filter for use as an image classifier and wherein said using linear programming comprises using the minimization formula

16. The computer system of claim 15 wherein said using linear programming further comprises using a first constraint

17. The computer system of claim 16 wherein said using linear programming further comprises using a second constraint 0≦

β

_ij≦

t_i≦

1 and β

^T1=1.

20. The computer system of claim 15 wherein said salient features comprises features that make an object stand out from a remainder of an image.