Kernels and methods for selecting kernels for use in learning machines

• US 20050071300A1
• Filed: 05/07/2002
• Published: 03/31/2005
• Est. Priority Date: 05/07/2001
• Status: Active Grant

• 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: Curtis Anderson, Garry L. Carls, Glynn Bergeron, James Roberts, Joe Mckenzie, John E. Matthews, Jules B. Paderewski, Julian N. Stern, Memorial Health Systems Incorporated, Peter J. Farley, Simpson K. Russell, Timothy P. O'Hayer
• Inventors: Schoelkopf, Bernard, Bartlett, Peter L, Elisseeff, Andre
• Granted Patent: US 7,353,215 B2
• Time in Patent Office: Days
• 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

Kernels (206) for use in learning machines, such as support vector machines, and methods are provided for selection and construction of such kernels are controlled by the nature of the data to be analyzed (203). In particular, data which may possess characteristics such as structure, for example DNA sequences, documents; graphs, signals, such as ECG signals and microarray expression profiles; spectra; images; spatio-temporal data; and relational data, and which may possess invariances or noise components that can interfere with the ability to accurately extract the desired information. Where structured datasets are analyzed, locational kernels are defined to provide measures of similarity among data points (210). The locational kernels are then combined to generate the decision function, or kernel. Where invariance transformations or noise is present, tangent vectors are defined to identify relationships between the invariance or noise and the data points (222). A covariance matrix is formed using the tangent vectors, then used in generation of the kernel.

Claims

1. A kernel for use in a learning machine for extracting knowledge from a dataset in data space wherein the dataset has at least one characteristic, the kernel comprising:

a function for mapping data in the dataset into a feature space, wherein the function incorporates the at least one characteristic of the dataset, the at least one characteristic selected from the group consisting of structure, transformation invariance and noise.

2. The kernel of claim 1, wherein the at least one characteristic comprises structure and the function comprises a kernel on a set of structures obtained from a combination of locational kernels, each locational kernel being defined on a structure comprising a pattern in the dataset and having a plurality of indices.

3. The kernel of claim 2, 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.

4. The kernel of claim 2, wherein the combination of locational kernels is formed by 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.

5. The kernel of claim 2, wherein the kernel on a set of structures is obtained by fixing the indices of the kernel given the locational kernel.

6. The kernel of claim 2, 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.

7. The kernel of claim 2, 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.

8. The kernel of claim 1, wherein the at least one characteristic comprises transformation invariance and the function is generated 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.

9. The kernel of claim 1, wherein the at least one characteristic comprises transformation invariance and the function is obtained using a kernel PCA map.

10. The kernel of claim 1, wherein the at least one characteristic comprises noise and the function is generated 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.

19. The method of claim 1 wherein the at least one characteristic comprises transformation invariance and the function is obtained using a kernel PCA map.

11. A method for selecting a kernel for use in a learning machine for extracting knowledge from a dataset in data space wherein the dataset has at least one characteristic, the method comprising:

identifying at least one characteristic of the dataset, the at least one characteristic selected from the group consisting of structure, transformation invariance and noise; and

constructing the kernel by incorporating the at least one characteristic in the construction.

12. The method of claim 11, wherein the at least one characteristic comprises structure and the function comprises a kernel on a set of structures obtained from a combination of locational kernels, each locational kernel being defined on a structure comprising a pattern in the dataset and having a plurality of indices.

13. The method of claim 12, 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.

14. The kernel method of claim 12, wherein the combination of locational kernels is formed by 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.

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

16. The method of claim 12, 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.

17. The method of claim 12, 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.

18. The method of claim 11, wherein the at least one characteristic comprises transformation invariance and the function is generated 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.

20. The method of claim 11, wherein the at least one characteristic comprises noise and the function is generated 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.