Partially supervised machine learning of data classification based on local-neighborhood Laplacian Eigenmaps

• US 20060235812A1
• Filed: 04/14/2005
• Published: 10/19/2006
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Rifkin, Ryan, Andrews, Stuart
• Granted Patent: US 7,412,425 B2
• Time in Patent Office: Days
• US Class Current: 706/14
• CPC Class Codes: G06F 18/21375 involving differential geometry, e.g. embedding of pattern manifold
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A local-neighborhood Laplacian Eigenmap (LNLE) algorithm is provided for methods and systems for semi-supervised learning on manifolds of data points in a high-dimensional space. In one embodiment, an LNLE based method includes building an adjacency graph over a dataset of labelled and unlabelled points. The adjacency graph is then used for finding a set of local neighbors with respect to an unlabelled data point to be classified. An eigen decomposition of the local subgraph provides a smooth function over the subgraph. The smooth function can be evaluated and based on the function evaluation the unclassified data point can be labelled. In one embodiment, a transductive inference (TI) algorithmic approach is provided. In another embodiment, a semi-supervised inductive inference (SSII) algorithmic approach is provided for classification of subsequent data points. A confidence determination can be provided based on a number of labeled data points within the local neighborhood. Experimental results comparing LNLE and simple LE approaches are presented.

Claims

1. A computer based method for learning a label of an unlabelled data point from a plurality of data points, the method comprising:

determining relative distances between all data points in the plurality of data points;

determining a set of neighboring data points with respect to the unlabelled data point;

performing an eigen decomposition of a matrix of distances between the set of neighboring data points to determine a function; and

labeling the unlabelled data point based on a result from evaluating the function with respect to the unlabelled data point.

2. The method of claim 1, further comprising:

receiving an additional unlabelled data point;

determining a relative distance between the additional unlabelled data point and the plurality data points;

determining a second set of neighboring data points with respect to the additional unlabelled data point;

performing an eigen decomposition of a matrix of distances between the second set of neighboring data points to determine a second function; and

labeling the additional unlabelled data point based on a result from evaluating the second function with respect to the additional unlabelled data point.

3. The method of claim 1, further comprising providing a confidence value based on a number of labelled data points determined within the set of neighboring data points.

4. The method of claim 1, wherein the eigen decomposition is not performed in response to determining that no labelled data points are within the set of neighboring data points and further wherein the labeling of the unlabelled data point results in an error condition.

5. The method of claim 1, further comprising:

determining that no labelled data point is within the set of neighboring data points with respect to the unlabelled data point;

increasing a number of neighbors for determining the set of neighboring data points; and

determining a second set of neighboring data points with respect to the unlabelled data point based on the increased number of neighbors.

6. The method of claim 1, wherein determining relative distances between all data points includes computing an adjacency matrix.

7. A computer based system for learning a label of an unlabelled data point from a plurality of data points, the system comprising:

means for determining relative distances between all data points in the plurality of data points;

means for determining a set of neighboring data points with respect to the unlabelled data point;

means for performing an eigen decomposition of a matrix of distances between the set of neighboring data points to determine a function; and

means for labeling the unlabelled data point based on a result from evaluating the function with respect to the unlabelled data point.

8. The system of claim 7, further comprising:

means for receiving an additional unlabelled data point;

means for determining a relative distance between the additional unlabelled data point and the plurality data points;

means for determining a second set of neighboring data points with respect to the additional unlabelled data point;

means for performing an eigen decomposition of a matrix of distances between the second set of neighboring data points to determine a second function; and

means for labeling the additional unlabelled data point based on a result from evaluating the second function with respect to the additional unlabelled data point.

9. The system of claim 7, further comprising means for providing a confidence value based on a number of labelled data points determined within the set of neighboring data points.

10. The system of claim 7, wherein the means for performing the eigen decomposition fails to perform the eigen decomposition in response to receiving from the means for determining the set of neighboring data points an indication that no labelled data points are within the set of neighboring data points and further wherein the means for labeling the unlabelled data point provides an error condition.

11. The system of claim 7, further comprising:

means for determining that no labelled data point is within the set of neighboring data points with respect to the unlabelled data point; and

means for increasing a number of neighbors for determining the set of neighboring data points;

wherein the means for determining the set of neighboring data points determines a second set of neighboring data points with respect to the unlabelled data point based on the increased number of neighbors.

12. The system of claim 7, wherein the means for determining relative distances between all data points includes a means for computing an adjacency matrix.

13. A computer based system for learning a label of an unlabelled data point from a plurality of data points, the system comprising:

a local-neighborhood Laplacian Eigenmap (LNLE) classifier module for determining a set of neighboring data points with respect to the unlabelled data point and performing an eigen decomposition of a matrix of distances between the set of neighboring data points to determine a function.

14. A computer readable medium for learning a label of an unlabelled data point from a plurality of data points, the computer readable medium comprising software instructions that when executed in a computer processor cause a computer system to implement the steps of:

determining relative distances between all data points in the plurality of data points;

determining a set of neighboring data points with respect to the unlabelled data point;

performing an eigen decomposition of a matrix of distances between the set of neighboring data points to determine a function; and

labeling the unlabelled data point based on a result from evaluating the function with respect to the unlabelled data point.

15. The computer readable medium of claim 14, wherein the steps further comprise the steps of:

receiving an additional unlabelled data point;

determining a relative distance between the additional unlabelled data point and the plurality data points;

determining a second set of neighboring data points with respect to the additional unlabelled data point;

performing an eigen decomposition of a matrix of distances between the second set of neighboring data points to determine a second function; and

labeling the additional unlabelled data point based on a result from evaluating the second function with respect to the additional unlabelled data point.

16. The computer readable medium of claim 14, wherein the steps further comprise the step of providing a confidence value based on a number of labelled data points determined within the set of neighboring data points.

17. The computer readable medium of claim 14, wherein the eigen decomposition is not performed in response to determining that no labelled data points are within the set of neighboring data points and further wherein the labeling of the unlabelled data point results in an error condition.

18. The computer readable medium of claim 14, wherein the steps further comprise the steps of:

determining that no labelled data point is within the set of neighboring data points with respect to the unlabelled data point;

increasing a number of neighbors for determining the set of neighboring data points; and

determining a second set of neighboring data points with respect to the unlabelled data point based on the increased number of neighbors.

19. The computer readable medium of claim 14, wherein determining relative distances between all data points includes computing an adjacency matrix.