Learning machine that considers global structure of data

• US 8,065,241 B2
• Filed: 04/09/2008
• Issued: 11/22/2011
• Est. Priority Date: 10/18/2005
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Miller, Michael R., Vapnik, Vladimir N.
• Primary Examiner(s): Rivas; Omar Fernandez
• Assistant Examiner(s): Bharadwaj; Kalpana
• Application Number:
  US12/100,220
• Publication Number:
  US 20080313112A1
• Time in Patent Office: 1,322 Days
• Field of Search: 706/20, 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2411 based on the proximity to a decision surface, e.g. support vector machines
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]

Abstract

A new machine learning technique is herein disclosed which generalizes the support vector machine framework. A separating hyperplane in a separating space is optimized in accordance with generalized constraints which dependent upon the clustering of the input vectors in the dataset.

Claims

1. A method for training a support vector machine, the method comprising:

receiving input vectors from a labeled dataset that have been clustered into one or more clusters, the input vectors from the labeled dataset relating to a phenomenon of interest;

creating simultaneously a t+1 space of a decision function and a t space of a correcting function where t is the number of clusters;

specifying generalized constraints in said space of said correcting function which are dependent upon the clusters of input vectors in the dataset;

generating in said space of said correcting function, a subset of the input vectors from the dataset using said decision function subject to the generalized constraints, said subset of the input vectors defining a separating hyperplane in a space of said decision function, said subset of the input vectors for use by said support vector machine in describing input vectors from an unlabeled dataset relating to said phenomenon of interest; and

wherein the generalized constraints can be represented as

2. The method of claim 1 wherein the generalized constraints are dependent upon two different kernel functions, one for said space of said decision function and the other for said space of said correcting function into which the input vectors with a cluster are mapped.

3. The method of claim 2 wherein the input vectors of different clusters are mapped to the same separating space but to different spaces of said correcting function.

4. The method of claim 2 wherein said space of said correcting function defines a correction function for each cluster.

5. The method of claim 1 wherein generalized constraints are alternatively represented as

6. The method of claim 5 wherein the matrix A*_i,j is an identity matrix and defines box constraints.

7. The method of claim 5 wherein the matrix A*_i,j does not define box constraints.

8. The method of claim 1 wherein preprocessing is applied to the dataset in order to obtain the input vectors.

9. The method of claim 1 wherein multiple sets of coefficients are generated so as to form a multiclass classifier.