Kernels for identifying patterns in datasets containing noise or transformation invariances

• US 8,209,269 B2
• Filed: 08/25/2010
• Issued: 06/26/2012
• Est. Priority Date: 05/07/2001
• Status: Expired due to Term

• Current Assignee: Curtis Anderson, Health Discovery Corporation, James Roberts, Joe Mckenzie, Jules B. Paderewski, Julian N. Stern, Memorial Health Systems Incorporated, Timothy P. O'Hayer
• Original Assignee: Health Discovery Corporation
• Inventors: Schoelkopf, Bernhard, Chapelle, Olivier
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Buss, Benjamin
• Application Number:
  US12/868,658
• Publication Number:
  US 20100318482A1
• Time in Patent Office: 671 Days
• Field of Search: 706/45, 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 18/2113 by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation
• CPC Class Codes: G06F 18/21355 nonlinear criteria, e.g. embedding a manifold in a Euclidean space
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• 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]
• CPC Class Codes: G06Q 20/042 characterized in that the payment protocol involves at least one cheque
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures
• CPC Class Codes: G06V 10/764 using classification, e.g. of video objects
• CPC Class Codes: G06V 10/771 Feature selection, e.g. selecting representative features from a multi-dimensional feature space
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/20 Supervised data analysis

Abstract

Learning machines, such as support vector machines, are used to analyze datasets to recognize patterns within the dataset using kernels that are selected according to the nature of the data to be analyzed. Where the datasets include an invariance transformation or noise, tangent vectors are defined to identify relationships between the invariance or noise and the training data points. A covariance matrix is formed using the tangent vectors, then used in generation of the kernel, which may be based on a kernel PCA map.

Claims

1. A computer-implemented method for analyzing data containing a noise component, the method comprising:

inputting the data into a computing environment comprising one or more pre-processing program modules and one or more support vector machine modules stored on a drive or a system memory of a computer or computer network;

dividing the data into a training dataset and a test dataset;

associating each datapoint within the training dataset with a tangent vector by applying a local transformation by the noise component to the datapoint;

mapping the training dataset and the tangent vectors into feature space;

in feature space, training a support vector machine comprising a kernel function to calculate a hyperplane for separating the training dataset into two or more classes, wherein the hyperplane has a normal vector that is orthogonal to the tangent vectors;

testing the trained support vector machine using the test dataset to determine whether an optimal solution has been achieved;

if the optimal solution has been achieved, inputting a new dataset having unknown classifications into the support vector machine; and

generating an output comprising an identification of patterns identified in the new dataset to one or more of the system memory, the drive, an external memory, and a display device.

2. The method of claim 1, wherein the step of mapping comprises mapping the training dataset and the tangent vectors into a PCA subspace using a kernel PCA map.

3. The method of claim 2, wherein the kernel PCA map is computed by:

generating covariance matrices for each of the training dataset and the tangent vectors;

diagonalizing each covariance matrix in a PCA subspace by;

generating a Gram matrix on the points within the covariance matrix;

computing the eigendecomposition of the Gram matrix;

using the computed eigendecomposition, expanding the eigenvectors of the covariance matrix;

using the expanded eigenvectors, computing an orthonormal matrix.

4. The method of claim 2, wherein the kernel PCA map is of the form ψ

(x)=Λ

<sup>−

1/2</sup>U^Tk(x), where x is an input datapoint, U is an orthonormal matrix, Λ

is a diagonal matrix, and k(x)=(K(x, x₁), . . . , K(x, x_n))^T, where K is the kernel matrix.

5. The method of claim 1, wherein the data comprises an image and the noise comprises translation or rotation.

6. The method of claim 1, wherein the data comprises spectral data and the noise is one or more of instrument noise, temperature drift, or signal drift.

7. A computer-implemented method for analyzing data containing a noise component, the method comprising:

generating a training dataset comprising measurements taken on a sample;

generating p additional measurements on the sample;

inputting the training dataset and the p additional measurements into a computing environment comprising one or more pre-processing program modules and one or more support vector machine modules stored on a drive or a system memory of a computer or computer network;

constructing p noise vectors;

using a kernel PCA map, mapping the training dataset and the p noise vectors to span a subset in feature space;

training a support vector machine comprising a kernel function to compute a decision boundary for separating the training dataset wherein substantially all of the p noise vectors are orthogonal to the decision boundary;

testing the trained support vector machine using the test dataset to determine whether an optimal solution has been achieved;

if the optimal solution has been achieved, inputting a new dataset having unknown classifications into the support vector machine; and

generating an output comprising an identification of patterns identified in the new dataset to one or more of the system memory, the drive, an external memory, and a display device.

8. The method of claim 7, wherein the kernel PCA map is of the form ψ

(x)=Λ

<sup>−

1/2</sup>U^Tk(x), where x is an input datapoint, U is an orthonormal matrix, Λ

is a diagonal matrix, and k(x)=(K(x, x₁), . . . , K(x, x_n))^T, where K is the kernel matrix.

9. The method of claim 7, wherein the kernel PCA map is computed by:

generating covariance matrices for each of the training dataset and a set of tangent vectors;

diagonalizing each covariance matrix in a PCA subspace by;

generating a Gram matrix on the points within the covariance matrix;

computing the eigendecomposition of the Gram matrix;

using the computed eigendecomposition, expanding the eigenvectors of the covariance matrix;

using the expanded eigenvectors, computing an orthonormal matrix.

10. The method of claim 7, wherein the data comprises an image and the noise comprises translation or rotation.

11. The method of claim 7, wherein the data comprises spectral data and the noise is one or more of instrument noise, temperature drift, or signal drift.

12. A computer program product embodied on a computer readable medium for predicting patterns in data containing a noise component, the computer program product comprising instructions for executing support vector machine classifiers and further for causing a computer processor to:

receive each of a training dataset comprising measurements taken on a sample and p additional measurements on the sample;

construct p noise vectors;

use a kernel PCA map to map the training dataset and the p noise vectors to span a subset in feature space;

train a support vector machine comprising a kernel function to compute a decision boundary for separating the training dataset wherein substantially all of the p noise vectors are orthogonal to the decision boundary;

test the trained support vector machine using a test dataset to determine whether an optimal solution has been achieved;

if the optimal solution has been achieved, receive a new dataset having unknown classifications into the support vector machine; and

generate an output comprising an identification of patterns identified in the new dataset to one or more of the system memory, the drive, an external memory, and a display device.

13. The computer program product of claim 12, wherein the kernel PCA map is of the form ψ

(x)=Λ

<sup>−

1/2</sup>U^Tk(x), where x is an input datapoint, U is an orthonormal matrix, Λ

is a diagonal matrix, and k(x)=(K(x, x₁), . . . , K(x, x_n))^T, where K is the kernel matrix.

14. The computer program product of claim 12, wherein the kernel PCA map is computed by:

generating covariance matrices for each of the training dataset and a set of tangent vectors;

diagonalizing each covariance matrix in a PCA subspace by;

generating a Gram matrix on the points within the covariance matrix;

computing the eigendecomposition of the Gram matrix;

using the computed eigendecomposition, expanding the eigenvectors of the covariance matrix;

using the expanded eigenvectors, computing an orthonormal matrix.

15. The computer program product of claim 12, wherein the data comprises an image and the noise comprises translation or rotation.

16. The computer program product of claim 12, wherein the data comprises spectral data and the noise is one or more of instrument noise, temperature drift, or signal drift.