Kernels and methods for selecting kernels for use in learning machines

• US 7,353,215 B2
• Filed: 05/07/2002
• Issued: 04/01/2008
• 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: Bartlett, Peter L., Elisseeff, Andre, Schoelkopf, Bernhard
• Primary Examiner(s): Hirl, Joseph P
• Application Number:
  US10/477,078
• Publication Number:
  US 20050071300A1
• Time in Patent Office: 2,156 Days
• Field of Search: 706/12, 706/46, 706/45, 707/101
• US Class Current: 706/46
• 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 possesses structural characteristics, locational kernels can be utilized to provide measures of similarity among data points within the dataset. The locational kernels are then combined to generate a decision function, or kernel, that can be used to analyze the dataset. Where invariance transformations or noise is present, tangent vectors are defined to identify relationships between the invariance or noise and the data points. A covariance matrix is formed using the tangent vectors, then used in generation of the kernel for recognizing patterns in the dataset.

Claims

1. A method for analyzing a dataset in data space to extract knowledge by identifying patterns in the dataset for classification of data within the dataset, wherein the dataset has an actual structure, the method comprising:

inputting structured training data into a memory of a computer comprising a processor having software stored therein for executing a kernel machine;

defining a kernel for execution by the kernel machine by;

representing the training dataset in the memory as a collection of components and an actual location of each component within the training data structure, wherein the actual location is specified as indices within an index set, each of the indices corresponding to a point of reference to the actual location;

applying a vicinity function to the collection of components to define subsets of components centered at different actual locations within the training dataset structure; and

measuring a similarity of the subsets of components at the different actual locations to define a locational kernel corresponding to each actual location;

combining the locational kernels for all of the different actual locations by performing an operation to produce a kernel on a set of structures;

applying the kernel on a set of structures to the dataset in the memory to identify patterns within the datase; and

storing data associated with the patterns within the dataset on a media.

2. The method of claim 1, wherein the dataset comprises data selected from the group consisting of DNA sequences, protein sequences, documents, graphs, signals, microarray expression profiles, spectra, images, spatio-temporal data and relational data.

3. The method of claim 1, wherein the step of combining the locational kernels comprises performing one or more operations selected from the group consisting of addition, scalar multiplication, multiplication, pointwise limits, argument transformations, convolution with a vicinity function and convolution with a real-valued function.

4. The method of claim 1, wherein the kernel on a set of structures is obtained by fixing the indices of the kernel given the locational kernel.

5. The method of claim 1, wherein the kernel on a set of structures is obtained by using a notion of similarity that is invariant with respect to certain transformations of the indices.

6. The method of claim 1, wherein the locational kernels comprises Gaussian radial basis function kernels having fixed indices and the kernel on a set of structures comprises a product overall all index positions of the locational kernels.

7. The method of claim 1, wherein the kernel on a set of structures further incorporates transformation invariance and the kernel is generated by estimating at least one tangent vector for associating each data point with a local invariance and selecting the kernel so that its optimization incorporates a covariance matrix of a plurality of the tangent vectors.

8. The method of claim 1, wherein the kernel further incorporates transformation invariance and the function is obtained using a kernel PCA map.

9. The method of claim 1, wherein the noise and the kernel are generated by estimating at least one noise vector associated with each data point and selecting the kernel so that its optimization incorporates a covariance matrix of a plurality of noise vectors.

10. The method of claim 1 wherein the operation includes summing the locational kernels over the indices, fixing the indices, or taking the product over all index positions of locational kernels.

11. A method for extracting knowledge from a dataset in data space, wherein the dataset has an actual structure, the method comprising:

inputting structured training data into a memory of a computer comprising a processor having software stored therein for executing a kernel machine;

representing the training data in the memory as a collection of components and a structural location of each component within the training data structure, wherein the structural location is specified as indices within an index set, wherein each of the indices corresponding to a point of reference to the structural location;

applying a vicinity function to the collection of components to define subsets of components centered at different structural locations within the training data structure;

measuring a similarity of the subsets of components at the different structural locations to define a locational kernel corresponding to each structural location;

combining the locational kernels for all of the different structural locations by performing an operation to produce a kernel on a set of structures;

applying the kernel on a set of structures in the memory to the dataset to identify patterns within the dataset; and

transferring data associated with the patterns to a storage device.

12. The method of claim 11, wherein the dataset comprises data selected from the group consisting of DNA sequences, protein sequences, documents, graphs, signals, microarray expression profiles, spectra, images, spatio-temporal data and relational data.

13. The method of claim 11, wherein the step of combining the locational kernels comprises performing one or more operations selected from the group consisting of addition, scalar multiplication, multiplication, pointwise limits, argument transformations, convolution with a vicinity function and convolution with a real-valued function.

14. The method of claim 11, wherein the kernel on a set of structures is obtained by fixing the indices of the kernel given the locational kernel.

15. The method of claim 11, wherein the kernel on a set of structures is obtained by using a notion of similarity that is invariant with respect to certain transformations of the indices.

16. The method of claim 11, wherein the locational kernels comprises Gaussian radial basis function kernels having fixed indices and the product overall all index positions of the locational kernels.

17. The method of claim 11, further comprising incorporating transformation invariance by estimating at least one tangent vector for associating each data point with a local invariance and selecting the function so that its optimization incorporates a covariance matrix of a plurality of the tangent vectors.

18. The method of claim 11, further comprising incorporating transformation invariance using a kernel PCA map.

19. The method of claim 11, further comprising incorporating noise by estimating at least one noise vector associating with each data point and selecting the function so that its optimization incorporates a covariance matrix of a plurality of noise vectors.

20. The method of claim 11 wherein the operation includes summing the locational kernels over the indices, fixing the indices, or taking the product over all index positions of locational kernels.

21. A method for analyzing a pair of structured objects to identify patterns within the pair of structure objects for classification of the structured objects, wherein each structured object comprises a dataset, the method comprising:

inputting a training dataset into a memory of a computer having a processor for executing a kernel machine, wherein the training dataset comprises structured objects;

representing each structured object in the training dataset in the memory as a collection of component objects and a structural location of a set of indices within the structured object each of the indices corresponding to a point of reference to the structural location;

applying a vicinity function to the collection of component objects to define subsets of component objects centered at different indices within each structured object in the training dataset; and

measuring a similarity between the subsets of component objects of one structured object of the training dataset and the subsets of components objects of the another structured object of the training dataset to define a locational kernel corresponding to each of the different indices;

combining the locational kernels for all of the different indices by performing an operation to produce a kernel on a set of structured objects;

applying the kernel on a set of structures in the memory to the pair of structured objects to identify patterns within the pair of structure objects; and

displaying data associated with the patterns on a display device.

22. The method of claim 21, wherein the structured object is of a type selected from the group consisting of strings, DNA sequences, protein sequences, documents, trees, graphs, signals, microarray expression profiles, spectra, images, spatio-temporal data and relational data.

23. The method of claim 21 wherein the operation includes summing the locational kernels over the indices, fixing the indices, or taking the product over all index positions of locational kernels.