Kernels and methods for selecting kernels for use in learning machines

[0001] The present invention relates to the use of learning machines to identify relevant patterns in datasets containing large quantities of diverse data, and more particularly to a method and system for selection of kernels to be used in kernel machines which best enable identification of relevant patterns.

[0002] In recent years, machine-learning approaches for data analysis have been widely explored for recognizing patterns which, in turn, allow extraction of significant information contained within a large data set that may also include data consisting of nothing more than irrelevant detail. Learning machines comprise algorithms that may be trained to generalize using data with known outcomes. Trained learning machine algorithms may then be applied to predict the outcome in cases of unknown outcome, i.e., to classify the data according to learned patterns. Machine-learning approaches, which include neural networks, hidden Markov models, belief networks and kernel-based classifiers such as support vector machines, are ideally suited for domains characterized by the existence of large amounts of data, noisy patterns and the absence of general theories. Support vector machines are disclosed in U.S. Pat. Nos. 6,128,608 and 6,157,921, both of which are assigned to the assignee of the present application and are incorporated herein by reference.

[0003] Many successful approaches to pattern classification, regression, clustering, and novelty detection problems rely on kernels for determining the similarity of a pair of patterns. These kernels are usually defined for patterns that can be represented as a vector of real numbers. For example, the liner kernels, radial basis function kernels, and polynomial kernels all measure the similarity of a pair of real vectors. Such kernels are appropriate when the patterns are best represented in this way, as a sequence of real numbers. The choice of a kernel corresponds to the choice of representation of the data in a feature space. In many applications, the patterns have a greater degree of structure. This structure can be exploited to improve the performance of the learning system. Examples of the types of structured data that commonly occur in machine learning applications are strings, such as DNA sequences, and documents; trees, such as parse trees used in natural language processing; graphs, such as web sites or chemical molecules; signals, such as ECG signals and microarray expression profiles; spectra; images; spatio-temporal data; and relational data, among others.

[0004] For structural objects, kernels methods are often applied by first finding a mapping from the structured objects to a vector of real numbers. In one embodiment of the kernel selection method, the invention described herein provides an alternative approach which may be applied to the selection of kernels which may be used for structured objects.

[0005] Many problems in bioinformatics, chemistry and other industrial processes involve the measurement of some features of samples by means of an apparatus whose operation is subject to fluctuations, influenced for instance by the details of the preparation of the measurement, or by environmental conditions such as temperature. For example, analytical instruments that rely on scintillation crystals for detecting radiation are known to be temperature sensitive, with additional noise or signal drift occurring if the crystals are not maintained within a specified temperature range. Data recorded using such measurement devices is subject to problems in subsequent processing, which can include machine learning methods. Therefore, it is desirable to provide automated ways of dealing with such data.

[0006] In certain classification tasks, there is a priori knowledge about the invariances related to the task. For instance, in image classification, it is known that the label of a given image should not change after a small translation or rotation. In a second embodiment of the method for selecting kernels for kernel machines, to improve performance, prior knowledge such as known transformation invariances or noise distribution is incorporated in the kernels. A technique is disclosed in which noise is represented as vectors in a feature space. The noise vectors are taken into account in constructing invariant kernel classifiers to obtain a decision function that is invariant with respect to the noise.

[0007] According to the present invention, methods are provided for selection and construction of kernels for use in kernel machines such that the kernels are suited to analysis of data which may posses 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.

[0008] In an exemplary embodiment, in a method for defining a similarity measure for structured objects, a location-dependent kernel is defined on one or more structures that comprise patterns in the structured data of a data set. This locational kernel defines a notion of similarity between structures that is relevant to particular locations in the structures. Using the locational kernel, a pair of structures can be viewed according to the similarities of their components. Multiple locational kernels can then be used to obtain yet another locational kernel. A kernel on the set of structures can be then obtained by combining the locational kernel(s). Different methods for combining the locational kernels include summing the locational kernels over the indices, fixing the indices, and taking the product over all index positions of locational kernels constructed from Gaussian radial basis function (RBF) kernels whose indices have been fixed. The resulting kernels are then used for processing the input data set.

[0009] The method of the present invention comprises the steps of: representing a structured object as a collection of component objects, together with their location within the structure; defining kernels, called locational kernels, that measure the similarity of (structure, location in structure) pairs; constructing locational kernels from kernels defined on the set of components; constructing locational kernels from other locational kernels; and constructing kernels on structured objects by combining locational kernels.

[0010] An iterative process comparing postprocessed training outputs or test outputs can be applied to make a determination as to which kernel configuration provides the optimal solution. If the test output is not the optimal solution, the selection of the kernel may be adjusted and the support vector machine may be retrained and retested. Once it is determined that the optimal solution has been identified, a live data set may be collected and preprocessed in the same manner as was the training data set to select the features that best represent the data. The pre-processed live data set is input into the learning machine for processing.

[0011] In an exemplary application of the kernel selection techniques of the first embodiment, a locational kernel construction scheme is used for comparing infrared spectra to classify disease states.

[0012] In a second embodiment, another component of kernel selection and design involves incorporating noise information into the kernel so that invariances are introduced into the learning system. The noise of the instrument that was used to generate the data can provide information that can be used in kernel design. For example, if certain peaks in a spectrum always have the same value while other peaks have values that vary with different experimental settings, the system takes this into account in its calculations. One method of compensation comprises normalizing every peak value. Analysis of control classes to infer the variability across different instruments can be incorporated into the kernel.

[0013] While the inventive methods disclosed herein are contemplated for use in different types of kernel machines, in an exemplary implementation, the kernel machine is a support vector machine. The exemplary system comprises a storage device for storing a training data set and a test data set, and a processor for executing a support vector machine. The processor is also operable for collecting the training data set from the database, pre-processing the training data set, training the support vector machine using the pre-processed training data set, collecting the test data set from the database, pre-processing the test data set in the same manner as was the training data set, testing the trained support vector machine using the pre-processed test data set, and in response to receiving the test output of the trained support vector machine, post-processing the test output to determine if the test output is an optimal solution. The exemplary system may also comprise a communications device for receiving the test data set and the training data set from a remote source. In such a case, the processor may be operable to store the training data set in the storage device prior pre-processing of the training data set and to store the test data set in the storage device prior pre-processing of the test data set. The exemplary system may also comprise a display device for displaying the post-processed test data. The processor of the exemplary system may further be operable for performing each additional function described above.

[0014] In an exemplary embodiment, a system and method are provided for enhancing knowledge discovery from data using multiple learning machines in general and multiple support vector machines in particular. Training data for a learning machine is pre-processed. Multiple support vector machines, each comprising distinct kernels, are trained with the preprocessed training data and are tested with test data that is pre-processed in the same manner. The test outputs from multiple support vector machines are compared in order to determine which of the test outputs if any represents an optimal solution. Selection of one or more kernels may be adjusted and one or more support vector machines may be retrained and retested. When it is determined that an optimal solution has been achieved, live data is pre-processed and input into the support vector machine comprising the kernel that produced the optimal solution. The live output from the learning machine may then be post-processed as needed to place the output in a format appropriate for interpretation by a human or another computer.

[0029] The present invention provides methods, systems and devices for discovering knowledge from data using learning machines. Particularly, the present invention is directed to methods, systems and devices for knowledge discovery from data using learning machines that are provided information regarding changes in biological systems. More particularly, the present invention comprises methods of use of such knowledge for diagnosing and prognosing changes in biological systems such as diseases. Additionally, the present invention comprises methods, compositions and devices for applying such knowledge to the testing and treating of individuals with changes in their individual biological systems. Preferred embodiments comprise detection of genes involved with prostate cancer and use of such information for treatment of patients with prostate cancer.

[0030] As used herein, “biological data” means any data derived from measuring biological conditions of human, animals or other biological organisms including microorganisms, viruses, plants and other living organisms. The measurements may be made by any tests, assays or observations that are known to physicians, scientists, diagnosticians, or the like. Biological data may include, but is not limited to, clinical tests and observations, physical and chemical measurements, genomic determinations, proteomic determinations, drug levels, hormonal and immunological tests, neurochemical or neurophysical measurements, mineral and vitamin level determinations, genetic and familial histories, and other determinations that may give insight into the state of the individual or individuals that are undergoing testing. Herein, the use of the term “data” is used interchangeably with “biological data”.

[0031] While several examples of learning machines exist and advancements are expected in this field, the exemplary embodiments of the present invention focus on kernel-based learning machines and more particularly on the support vector machine.

[0032] The present invention can be used to analyze biological data generated at multiple stages of investigation into biological functions, and further, to integrate the different kinds of data for novel diagnostic and prognostic determinations. For example, biological data obtained from clinical case information, such as diagnostic test data, family or genetic histories, prior or current medical treatments, and the clinical outcomes of such activities, can be utilized in the methods, systems and devices of the present invention. Additionally, clinical samples such as diseased tissues or fluids, and normal tissues and fluids, and cell separations can provide biological data that can be utilized by the current invention. Proteomic determinations such as 2-D gel, mass spectrophotometry and antibody screening can be used to establish databases that can be utilized by the present invention. Genomic databases can also be used alone or in combination with the above-described data and databases by the present invention to provide comprehensive diagnosis, prognosis or predictive capabilities to the user of the present invention.

[0033] A first aspect of the present invention facilitates analysis of data by pre-processing the data prior to using the data to train a learning machine and/or optionally post-processing the output from a learning machine. Generally stated, pre-processing data comprises reformatting or augmenting the data in order to allow the learning machine to be applied most advantageously. In some cases, pre-processing involves selecting a method for reducing the dimensionality of the feature space, i.e., selecting the features which best represent the data. Methods which may be used for this purpose include recursive feature elimination (RFE) and elimination of data points based on expert knowledge, e.g., knowledge that measurement at ends of the measurement range tend to be predominantly noise. The features remaining after feature selection are then used to train a learning machine for purposes of pattern classification, regression, clustering and/or novelty detection.

[0034] The learning machine is a kernel machine in which the kernels are selected in consideration of certain characteristics of the data. In one embodiment, the data has a structure which permits locational kernels to be defined. These locational kernels are then used to identifying similarities between components of structures in the dataset. The locational kernels are then combined through one or more of a variety of possible operations to derive the kernel function. In another embodiment, the input dataset includes invariance or noise. The invariance or noise is taken into consideration when selecting the kernel function. Virtual support vectors may be added, or a set of tangent vectors may be generated. In preferred embodiment the kernel machine is a support vector machine.

[0035] In a manner similar to pre-processing, post-processing involves interpreting the output of a learning machine in order to discover meaningful characteristics thereof. The meaningful characteristics to be ascertained from the output may be problem- or data-specific. Post-processing involves interpreting the output into a form that, for example, may be understood by or is otherwise useful to a human observer, or converting the output into a form which may be readily received by another device for, e.g., archival or transmission.

[0036] FIG. 1 is a flowchart illustrating a general method 100 for analyzing data using learning machines. The method 100 begins at starting block 101 and progresses to step 102 where a specific problem is formalized for application of analysis through machine learning. Particularly important is a proper formulation of the desired output of the learning machine. For instance, in predicting future performance of an individual equity instrument, or a market index, a learning machine is likely to achieve better performance when predicting the expected future change rather than predicting the future price level. The future price expectation can later be derived in a post-processing step as will be discussed later in this specification.

[0037] After problem formalization, step 103 addresses training data collection. Training data comprises a set of data points having known characteristics. This data may come from customers, research facilities, academic institutions, national laboratories, commercial entities or other public or confidential sources. The source of the data and the types of data provided are not crucial to the methods. Training data may be collected from one or more local and/or remote sources. The data may be provided through any means such as via the internet, server linkages or discs, CD/ROMs, DVDs or other storage means. The collection of training data may be accomplished manually or by way of an automated process, such as known electronic data transfer methods. Accordingly, an exemplary embodiment of the learning machine for use in conjunction with the present invention may be implemented in a networked computer environment. Exemplary operating environments for implementing various embodiments of the learning machine will be described in detail with respect to FIGS. 4-5.

[0038] At step 104, the collected training data is optionally pre-processed in order to allow the learning machine to be applied most advantageously toward extraction of the knowledge inherent to the training data. During this preprocessing stage a variety of different transformations can be performed on the data to enhance its usefulness. Such transformations, examples of which include addition of expert information, labeling, binary conversion, Fourier transformations, etc., will be readily apparent to those of skill in the art. However, the preprocessing of interest in the present invention is the reduction of dimensionality by way of feature selection, different methods of which are described in detail below.

[0039] Returning to FIG. 1, an exemplary method 100 continues at step 106, where the learning machine is trained using the pre-processed data. As is known in the art, a learning machine is trained by adjusting its operating parameters until a desirable training output is achieved. The determination of whether a training output is desirable may be accomplished either manually or automatically by comparing the training output to the known characteristics of the training data. A learning machine is considered to be trained when its training output is within a predetermined error threshold from the known characteristics of the training data. In certain situations, it may be desirable, if not necessary, to post-process the training output of the learning machine at step 107. As mentioned, post-processing the output of a learning machine involves interpreting the output into a meaningful form. In the context of a regression problem, for example, it may be necessary to determine range categorizations for the output of a learning machine in order to determine if the input data points were correctly categorized. In the example of a pattern recognition problem, it is often not necessary to post-process the training output of a learning machine.

[0040] At step 108, test data is optionally collected in preparation for testing the trained learning machine. Test data may be collected from one or more local and/or remote sources. In practice, test data and training data may be collected from the same source(s) at the same time. Thus, test data and training data sets can be divided out of a common data set and stored in a local storage medium for use as different input data sets for a learning machine. Regardless of how the test data is collected, any test data used must be pre-processed at step 110 in the same manner as was the training data. As should be apparent to those skilled in the art, a proper test of the learning may only be accomplished by using testing data of the same format as the training data. Then, at step 112 the learning machine is tested using the pre-processed test data, if any. The test output of the learning machine is optionally post-processed at step 114 in order to determine if the results are desirable. Again, the post processing step involves interpreting the test output into a meaningful form. The meaningful form may be one that is readily understood by a human or one that is compatible with another processor. Regardless, the test output must be post-processed into a form which may be compared to the test data to determine whether the results were desirable. Examples of post-processing steps include but are not limited of the following: optimal categorization determinations, scaling techniques (linear and non-linear), transformations (linear and non-linear), and probability estimations. The method 100 ends at step 116.

[0041] FIG. 2 is a flow chart illustrating an exemplary method 200 for enhancing knowledge that may be discovered from data using a specific type of learning machine known as a support vector machine (SVM). A SVM implements a specialized algorithm for providing generalization when estimating a multi-dimensional function from a limited collection of data. A SVM may be particularly useful in solving dependency estimation problems. More specifically, a SVM may be used accurately in estimating indicator functions (e.g. pattern recognition problems) and real-valued functions (e.g. function approximation problems, regression estimation problems, density estimation problems, and solving inverse problems). The SVM was originally developed by Boser, Guyon and Vapnik (“A training algorithm for optimal margin classifiers”, Fifth Annual Workshop on Computational Learning Theory, Pittsburgh, ACM (1992) pp. 142-152). The concepts underlying the SVM are also explained in detail in Vapnik's book, entitled Statistical Learning Theory (John Wiley & Sons, Inc. 1998), which is herein incorporated by reference in its entirety. Accordingly, a familiarity with SVMs and the terminology used therewith are presumed throughout this specification.

[0042] The exemplary method 200 begins at starting block 201 and advances to step 202, where a problem is formulated and then to step 203, where a training data set is collected. As was described with reference to FIG. 1, training data may be collected from one or more local and/or remote sources, through a manual or automated process. At step 204 the training data is optionally pre-processed. Those skilled in the art should appreciate that SVMs are capable of processing input data having extremely large dimensionality, however, according to the present invention, pre-processing includes the use of feature selection methods to reduce the dimensionality of feature space.

[0043] At step 206 a kernel is selected for the SVM. As is known in the art, different kernels will cause a SVM to produce varying degrees of quality in the output for a given set of input data. Therefore, the selection of an appropriate kernel may be essential to the desired quality of the output of the SVM. In one embodiment of the learning machine, a kernel may be chosen based on prior performance knowledge. As is known in the art, exemplary kernels include polynomial kernels, radial basis classifier kernels, linear kernels, etc. In an alternate embodiment, a customized kernel may be created that is specific to a particular problem or type of data set. In yet another embodiment, the multiple SVMs may be trained and tested simultaneously, each using a different kernel. The quality of the outputs for each simultaneously trained and tested SVM may be compared using a variety of selectable or weighted metrics (see step 222) to determine the most desirable kernel. In one of the preferred embodiments of the invention which is particularly advantageous for use with structured data, locational kernels are defined to exploit patterns within the structure. The locational kernels are then used to construct kernels on the structured object. Further discussion of the kernels for structured data is provided below. Still another embodiment incorporates noise data into selection and construction of kernels in order to facilitate extraction of relevant knowledge from noise such as measurement artifacts and other variables that may impair the accuracy of the analysis. This method for construction kernels is also described below in more detail.

[0044] At step 208 the pre-processed training data is input into the SVM. At step 210, the SVM is trained using the pre-processed training data to generate an optimal hyperplane. Optionally, the training output of the SVM may then be post-processed at step 211. Again, post-processing of training output may be desirable, or even necessary, at this point in order to properly calculate ranges or categories for the output. At step 212 test data is collected similarly to previous descriptions of data collection. The test data is pre-processed at step 214 in the same manner as was the training data above. Then, at step 216 the pre-processed test data is input into the SVM for processing in order to determine whether the SVM was trained in a desirable manner. The test output is received from the SVM at step 218 and is optionally post-processed at step 220.

[0045] Based on the post-processed test output, it is determined at step 222 whether an optimal minimum was achieved by the SVM. Those skilled in the art should appreciate that a SVM is operable to ascertain an output having a global minimum error. However, as mentioned above, output results of a SVM for a given data set will typically vary with kernel selection. Therefore, there are in fact multiple global minimums that may be ascertained by a SVM for a given set of data. As used herein, the term “optimal minimum” or “optimal solution” refers to a selected global minimum that is considered to be optimal (e.g. the optimal solution for a given set of problem specific, pre-established criteria) when compared to other global minimums ascertained by a SVM. Accordingly, at step 222, determining whether the optimal minimum has been ascertained may involve comparing the output of a SVM with a historical or predetermined value. Such a predetermined value may be dependant on the test data set. For example, in the context of a pattern recognition problem where data points are classified by a SVM as either having a certain characteristic or not having the characteristic, a global minimum error of 50% would not be optimal. In this example, a global minimum of 50% is no better than the result that would be achieved by flipping a coin to determine whether the data point had that characteristic. As another example, in the case where multiple SVMs are trained and tested simultaneously with varying kernels, the outputs for each SVM may be compared with output of other SVM to determine the practical optimal solution for that particular set of kernels. The determination of whether an optimal solution has been ascertained may be performed manually or through an automated comparison process.

[0046] If it is determined that the optimal minimum has not been achieved by the trained SVM, the method advances to step 224, where the kernel selection is adjusted. Adjustment of the kernel selection may comprise selecting one or more new kernels or adjusting kernel parameters. Furthermore, in the case where multiple SVMs were trained and tested simultaneously, selected kernels may be replaced or modified while other kernels may be re-used for control purposes. After the kernel selection is adjusted, the method 200 is repeated from step 208, where the pre-processed training data is input into the SVM for training purposes. When it is determined at step 222 that the optimal minimum has been achieved, the method advances to step 226, where live data is collected similarly as described above. By definition, live data has not been previously evaluated, so that the desired output characteristics that were known with respect to the training data and the test data are not known.

[0047] At step 228 the live data is pre-processed in the same manner as was the training data and the test data. At step 230, the live pre-processed data is input into the SVM for processing. The live output of the SVM is received at step 232 and is post-processed at step 234. The method 200 ends at step 236.

[0048] FIG. 3 is a flow chart illustrating an exemplary optimal categorization method 300 that may be used for pre-processing data or post-processing output from a learning machine. Additionally, as will be described below, the exemplary optimal categorization method may be used as a stand-alone categorization technique, independent from learning machines. The exemplary optimal categorization method 300 begins at starting block 301 and progresses to step 302, where an input data set is received. The input data set comprises a sequence of data samples from a continuous variable. The data samples fall within two or more classification categories. Next, at step 304 the bin and class-tracking variables are initialized. As is known in the art, bin variables relate to resolution, while class-tracking variables relate to the number of classifications within the data set. Determining the values for initialization of the bin and class-tracking variables may be performed manually or through an automated process, such as a computer program for analyzing the input data set. At step 306, the data entropy for each bin is calculated. Entropy is a mathematical quantity that measures the uncertainty of a random distribution. In the exemplary method 300, entropy is used to gauge the gradations of the input variable so that maximum classification capability is achieved.

[0049] The method 300 produces a series of “cuts” on the continuous variable, such that the continuous variable may be divided into discrete categories. The cuts selected by the exemplary method 300 are optimal in the sense that the average entropy of each resulting discrete category is minimized. At step 308, a determination is made as to whether all cuts have been placed within input data set comprising the continuous variable. If all cuts have not been placed, sequential bin combinations are tested for cutoff determination at step 310. From step 310, the exemplary method 300 loops back through step 306 and returns to step 308 where it is again determined whether all cuts have been placed within input data set comprising the continuous variable. When all cuts have been placed, the entropy for the entire system is evaluated at step 309 and compared to previous results from testing more or fewer cuts. If it cannot be concluded that a minimum entropy state has been determined, then other possible cut selections must be evaluated and the method proceeds to step 311. From step 311 a heretofore untested selection for number of cuts is chosen and the above process is repeated from step 304. When either the limits of the resolution determined by the bin width has been tested or the convergence to a minimum solution has been identified, the optimal classification criteria is output at step 312 and the exemplary optimal categorization method 300 ends at step 314.

[0050] The optimal categorization method 300 takes advantage of dynamic programming techniques. As is known in the art, dynamic programming techniques may be used to significantly improve the efficiency of solving certain complex problems through carefully structuring an algorithm to reduce redundant calculations. In the optimal categorization problem, the straightforward approach of exhaustively searching through all possible cuts in the continuous variable data would result in an algorithm of exponential complexity and would render the problem intractable for even moderate sized inputs. By taking advantage of the additive property of the target function, in this problem the average entropy, the problem may be divided into a series of sub-problems. By properly formulating algorithmic sub-structures for solving each sub-problem and storing the solutions of the sub-problems, a significant amount of redundant computation may be identified and avoided. As a result of using the dynamic programming approach, the exemplary optimal categorization method 300 may be implemented as an algorithm having a polynomial complexity, which may be used to solve large sized problems.

[0051] As mentioned above, the exemplary optimal categorization method 300 may be used in pre-processing data and/or post-processing the output of a learning machine. For example, as a preprocessing transformation step, the exemplary optimal categorization method 300 may be used to extract classification information from raw data. As a post-processing technique, the exemplary optimal range categorization method may be used to determine the optimal cut-off values for markers objectively based on data, rather than relying on ad hoc approaches. As should be apparent, the exemplary optimal categorization method 300 has applications in pattern recognition, classification, regression problems, etc. The exemplary optimal categorization method 300 may also be used as a stand-alone categorization technique, independent from SVMs and other learning machines.

[0052] FIG. 4 and the following discussion are intended to provide a brief and general description of a suitable computing environment for implementing biological data analysis according to the present invention. Although the system shown in FIG. 4 is a conventional personal computer 1000, those skilled in the art will recognize that the invention also may be implemented using other types of computer system configurations. The computer 1000 includes a central processing unit 1022, a system memory 1020, and an Input/Output (“I/O”) bus 1026. A system bus 1021 couples the central processing unit 1022 to the system memory 1020. A bus controller 1023 controls the flow of data on the I/O bus 1026 and between the central processing unit 1022 and a variety of internal and external I/O devices. The I/O devices connected to the I/O bus 1026 may have direct access to the system memory 1020 using a Direct Memory Access (“DMA”) controller 1024.

[0053] The I/O devices are connected to the I/O bus 1026 via a set of device interfaces. The device interfaces may include both hardware components and software components. For instance, a hard disk drive 1030 and a floppy disk drive 1032 for reading or writing removable media 1050 may be connected to the I/O bus 1026 through disk drive controllers 1040. An optical disk drive 1034 for reading or writing optical media 1052 may be connected to the I/O bus 1026 using a Small Computer System Interface (“SCSI”) 1041. Alternatively, an IDE (Integrated Drive Electronics, i.e., a hard disk drive interface for PCs), ATAPI (ATtAchment Packet Interface, i.e., CD-ROM and tape drive interface), or EIDE (Enhanced IDE) interface may be associated with an optical drive such as may be the case with a CD-ROM drive. The drives and their associated computer-readable media provide nonvolatile storage for the computer 1000. In addition to the computer-readable media described above, other types of computer-readable media may also be used, such as ZIP drives, or the like.

[0054] A display device 1053, such as a monitor, is connected to the I/O bus 1026 via another interface, such as a video adapter 1042. A parallel interface 1043 connects synchronous peripheral devices, such as a laser printer 1056, to the I/O bus 1026. A serial interface 1044 connects communication devices to the I/O bus 1026. A user may enter commands and information into the computer 1000 via the serial interface 1044 or by using an input device, such as a keyboard 1038, a mouse 1036 or a modem 1057. Other peripheral devices (not shown) may also be connected to the computer 1000, such as audio input/output devices or image capture devices.

[0055] A number of program modules may be stored on the drives and in the system memory 1020. The system memory 1020 can include both Random Access Memory (“RAM”) and Read Only Memory (“ROM”). The program modules control how the computer 1000 functions and interacts with the user, with I/O devices or with other computers. Program modules include routines, operating systems 1065, application programs, data structures, and other software or firmware components. In an illustrative embodiment, the learning machine may comprise one or more pre-processing program modules 1075A, one or more post-processing program modules 1075B, and/or one or more optimal categorization program modules 1077 and one or more SVM program modules 1070 stored on the drives or in the system memory 1020 of the computer 1000. Specifically, pre-processing program modules 1075A, post-processing program modules 1075B, together with the SVM program modules 1070 may comprise computer-executable instructions for pre-processing data and post-processing output from a learning machine and implementing the learning algorithm according to the exemplary methods described with reference to FIGS. 1 and 2. Furthermore, optimal categorization program modules 1077 may comprise computer-executable instructions for optimally categorizing a data set according to the exemplary methods described with reference to FIG. 3.

[0056] The computer 1000 may operate in a networked environment using logical connections to one or more remote computers, such as remote computer 1060. The remote computer 1060 may be a server, a router, a peer device or other common network node, and typically includes many or all of the elements described in connection with the computer 1000. In a networked environment, program modules and data may be stored on the remote computer 1060. The logical connections depicted in FIG. 5 include a local area network (“LAN”) 1054 and a wide area network (“WAN”) 1055. In a LAN environment, a network interface 1045, such as an Ethernet adapter card, can be used to connect the computer 1000 to the remote computer 1060. In a WAN environment, the computer 1000 may use a telecommunications device, such as a modem 1057, to establish a connection. It will be appreciated that the network connections shown are illustrative and other devices of establishing a communications link between the computers may be used.

[0057] In another embodiment, a plurality of SVMs can be configured to hierarchically process multiple data sets in parallel or sequentially. In particular, one or more first-level SVMs may be trained and tested to process a first type of data and one or more first-level SVMs can be trained and tested to process a second type of data. Additional types of data may be processed by other first-level SVMs. The output from some or all of the first-level SVMs may be combined in a logical manner to produce an input data set for one or more second-level SVMs. In a similar fashion, output from a plurality of second-level SVMs may be combined in a logical manner to produce input data for one or more third-level SVM. The hierarchy of SVMs may be expanded to any number of levels as may be appropriate. In this manner, lower hierarchical level SVMs may be used to pre-process data that is to be input into higher level SVMs. Also, higher hierarchical level SVMs may be used to post-process data that is output from lower hierarchical level SVMs.

[0058] Each SVM in the hierarchy or each hierarchical level of SVMs may be configured with a distinct kernel. For example, SVMs used to process a first type of data may be configured with a first type of kernel while SVMs used to process a second type of data may utilize a second, different type of kernel. In addition, multiple SVMs in the same or different hierarchical level may be configured to process the same type of data using distinct kernels.

[0059] FIG. 5 illustrates an exemplary hierarchical system of SVMs. As shown, one or more first-level SVMs 1302a and 1302b may be trained and tested to process a first type of input data 1304a, such as mammography data, pertaining to a sample of medical patients. One or more of these SVMs may comprise a distinct kernel, indicated as “KERNEL 1” and “KERNEL 2”. Also, one or more additional first-level SVMs 1302c and 1302d may be trained and tested to process a second type of data 1304b, which may be, for example, genomic data for the same or a different sample of medical patients. Again, one or more of the additional SVMs may comprise a distinct kernel, indicated as “KERNEL 1” and “KERNEL 3”. The output from each of the like first-level SVMs may be compared with each other, e.g., 1306a compared with 1306b; 1306c compared with 1306d , in order to determine optimal outputs 1308a and 1308b. Then, the optimal outputs from the two groups or first-level SVMs, i.e., outputs 1308a and 1308b , may be combined to form a new multi-dimensional input data set 1310, for example, relating to mammography and genomic data. The new data set may then be processed by one or more appropriately trained and tested second-level SVMs 1312a and 1312b . The resulting outputs 1314a and 1314b from second-level SVMs 1312a and 1312b may be compared to determine an optimal output 1316. Optimal output 1316 may identify causal relationships between the mammography and genomic data points. As should be apparent to those of skill in the art, other combinations of hierarchical SVMs may be used to process either in parallel or serially, data of different types in any field or industry in which analysis of data is desired.

Selection of Kernels

[0060] In a first embodiment, a method is provided for construction of kernels for structured data. Specifically, a similarity measure is defined for structured objects in which a location-dependent kernel is defined on one or more structures that comprise patterns in the structured data of a data set. This locational kernel defines a notion of similarity between structures that is relevant to particular locations in the structures. Using the locational kernel, a pair of structures can be viewed as a rich collection of similarities of their components. Multiple locational kernels can then be used to obtain yet another locational kernel. A kernel on the set of structures can be then obtained by combining the locational kernel(s). Different methods for combining the locational kernels include summing the locational kernels over the indices, fixing the indices, and taking the product over all index positions of locational kernels constructed from Gaussian radial basis function (RBF) kernels whose indices have been fixed. The resulting kernels are then used for processing the input data set.

[0061] A structured object is represented as a collection of components objects together with their locations within the structure. Given a component set A and α path set P, α structure on A and P is a triple s=(I, c, p),where I is the index set, c :I→A is the component function, and p: I×I→P is the path function. When I is finite, s can be said to be a finite structure.

[0062] The index set and component and path functions associated with s are denoted by I_s, c_s, and p_s,

[0063] Let S be a set of structures on A and P. A vicinity function for S is α function h:
{(s,i,i′):s∈S, i, i′∈I_s}→R of the form h(s,i,i′)=φ(p_s(i,i′)
for some φ: P→R.
This vicinity function h is stable if, for all: s∈S and i∈I_s,

[0064] $\begin{array}{cc}\sum _{i^{\prime }\in I_s}h\left(s,i,i^{\prime }\right)<\infty .& \left(2\right)\end{array}$

[0065] Notice that every vicinity function on a set of finite structures is stable. The following are a few examples of structures and vicinity functions:

[0066] 1. If A=R and P=Z, x∈Rⁿ is defined as a finite structure s, where I_s={1, . . . , n}, c_s(i)=x_i, and p_s(i−i′)=i−i′. For example, x might be noisy estimates of the energy in n adjacent frequency bands. In this case, a vicinity function might be defined as
h(s,i,i′)=e^{−c(i−i′)2}  (3)
for some c>0. This function models closeness in the frequency domain, since small values of (i−i′) correspond to nearby frequency bands.

[0067] 2. If A is finite alphabet and P=Z, a finite string t on A can be defined as the finite structure s, where I_s={1, . . . , |t|}, with |t| the length of the string t, c_s(i)=t[i], and p_s(i,i′)=i−i′. For example, t could be a DNA sequence, a protein sequence, or a document, represented as a sequence of words. In such cases, a vicinity function might be defined as
h(s,i,i′)=1(i>i′)λ^i−i′  (4)
for some λ∈[0,1). For a DNA sequence, one might choose a vicinity function such as
h(s,i,i′)=1(i>i′)λ₁^{|(i−i′+6 mod 12)−6|}λ₂^(i−i′)  (5)
for some λ₁, λ₂∈[0,1). In this case, the vicinity function reflects closeness in the molecule, since elements of the sequence separated by about 12 base pairs are in adjacent coils of the helix.

[0068] 3. If A=R, P=Z, and t∈l₂ is a discrete-time real signal, then one could define the structure s where I_s=N, c_s(i)=t[i], and p_s(i,i′)=i−i′. This is not a finite structure. An example of a vicinity function might be the impulse response h(s,i,i′)=φ(i−i′). This leads to some kind of matched filter.

[0069] 4. If A=[0,1], P=Z², and g∈A^xsxys is a grayscale image of width x_s pixels and height y_s pixels, then one could define the structure s with I_s={1, . . . . , x_s}×{1, . . . , y_s}, c_s(x,y)=g[x,y], and
p_s((x,y), (x′,y′))=(x−x′, y−y′)  (6)
An example of a vicinity function is
h(s,(x,y),(x′,y′))=e^{−((x−x′)2+(y−y′) 2)/(2σ2)}  (7)

[0070] 5. For a directed acyclic graph (“DAG”) (V,E) with vertices labeled with elements of A, one could define the structure s with I_s=V, component function c_s(i) defined to be the label associated with vertex i, path set P defined as the set of all connected DAGs, and p_s(i,i′) is the DAG consisting of all paths from i to i′. For example, A might be a set of part-of-speech tags, and s might correspond to a parse tree, with each vertex labeled with a tag. An example of a vicinity function is
h(s,i,i′)=λ^−d(i,i′),  (8)
where d(i,i′) is the number of edges in the shortest directed path from i to i′ (or ∞ if there is no such path.

[0071] Next, locational kernels are defined to measure the similarity of pairs, e.g., structure or location in the structure. A kernel on a set T means a nonnegative-definite, symmetric, real function on T².

[0072] For concreteness, consider the comparison of two documents, where the documents are represented as sequences of words. The key idea is to construct kernels comparing the two documents centered at particular words, that is, to define a measure of the similarity of two words, surrounded by the rest of the documents.

[0073] For a set S of structures, define
{hacek over (S)}={(s,i):s∈S,i␣Is}  (9)
A locational kernel on S corresponds to a kernel on {hacek over (S)}.

[0074] A locational kernel on S is said to be bounded if, for all s∈I_s.

[0075] $\begin{array}{cc}\underset{i\in I_s}{\max }k\left(\left(s,i\right),\left(s,i\right)\right)<\infty & \left(10\right)\end{array}$

[0076] Notice that every locational kernel on a set of finite structures is bounded.

[0077] If k is a locational kernel on a set S of finite structures, and h is a vicinity function on S. then h*k is a locational kernel on S. This can be shown as follows:

[0078] Let Φ: {hacek over (S)}→l₂ be the feature map for k, so that

[0079] $\begin{array}{cc}k\left(\left(s,i\right),\left(t,j\right)\right)=\langle \Phi \left(s,i\right),\left(t,j\right)\rangle .\mathrm{Then},& \left(11\right)\\ \begin{array}{c}\left(h*k\right)\left(\left(s,i\right),\left(t,j\right)\right)=\sum _{\underset{j^{\prime }\in I_s}{i^{\prime }\in I_s}}h\left(s,i,i^{\prime }\right)h\left(t,j,j^{\prime }\right)k\left(\left(s,i^{\prime }\right),\Phi \left(t,j^{\prime }\right)\right)\\ =\sum _{i^{\prime }\in I_s}\sum _{j^{\prime }\in I_s}h\left(s,i,i^{\prime }\right)h\left(t,j,j^{\prime }\right)\\ \langle \Phi \left(s,i^{\prime }\right),\Phi \left(t,j^{\prime }\right)\rangle \\ =\langle \left(\sum _{i^{\prime }\in I_s}h\left(s,i,i^{\prime }\right)\Phi \left(s,i^{\prime }\right)\right),\\ \left(\sum _{j^{\prime }\in I_s}h\left(s,j,j^{\prime }\right)\Phi \left(t,j^{\prime }\right)\right)\rangle \\ =\langle \psi \left(s,i\right),\psi \left(t,j\right)\rangle ,\end{array}& \left(12\right)\end{array}$
where

[0080] $\psi \left(s,i\right)=\sum _{i^{\prime }\in I_s}h\left(s,i,i^{\prime }\right)\Phi \left(s,i^{\prime }\right).$
Thus, h*k is a locational kernel on S provided that ψ maps to l₂. (See, e.g., Equ. (28).) To see this, notice that

[0081] $\begin{array}{cc}\psi \left(s,i\right)\le \sum _{i^{\prime }\in I_s}h\left(s,i,i^{\prime }\right)\Phi \left(s,i^{\prime }\right)\le \underset{i^{\prime }\in I_s}{\max }\Phi \left(s,i^{\prime }\right)\sum _{i^{\prime }\in I_s}h\left(s,i,i^{\prime }\right),& \left(13\right)\end{array}$
and both factors are finite, since k is bounded and h is stable. The boundedness of k and the stability of h are implied by the finiteness of I_s.

[0082] Note that the function ((s,i,i′), (t,j,j′))→h(s,i,i′)h(t,j,j′) is a kernel, and so for the case of finite structures one could express h*k as a special case of an R-convolution.

[0083] An interesting class of vicinity functions is obtained by considering smoothness properties of the component function. For example, suppose that x∈Rⁿ is a vector of the energy contained inn band-pass filtered versions of a signal, so that it is a smoothed version of the power of the signal in n adjacent frequency bands. (We can consider x as a structure by defining A=R′P=Z, I_s={1, . . . , n}, c_s(i)=x_i and p_s(i,i′)=i−i′.) Since components of the vector x already contain information about the neighboring components, it might be useful to consider a representation that focuses on how each component deviates from the value implied by a smooth interpolation of the neighboring components. One could, for example, represent each component by the coefficients of a low-degree polynomial that accurately approximates the nearby components, and by the error of such an approximation. In fact, these representations correspond to convolutions of certain vicinity functions with the component kernel.

[0084] To see this more generally, consider a kernel k₀ on the component space A, and let Φ be the corresponding feature map from A to l₂ Choose some functions φ₁, . . . , φ_n that map from P to R. For each s∈S and i∈I_s define the parameterized map ƒ: I_s→l₂ by

[0085] $\begin{array}{cc}{f}_{s,i}\left(i^{\prime }\right)=\sum _{n=1}^N{\alpha }_{s,i,n}{\varphi }_n\left(p_{s}N\left(i,i^{\prime }\right)\right)& \left(14\right)\end{array}$
for i′∈I_s, with parameters α_s,i,1, . . . , α_s,i,n∈l₂. Fix a vicinity function w for S. Then, for each I, these N parameters are chosen to minimize the weighted sum

[0086] $\begin{array}{cc}\sum _{i^{\prime }\in I}w\left(s,i,i^{\prime }\right){f_{s,i}\left(i^{\prime }\right)-\left(\Phi c_s\left(i^{\prime }\right)\right)}^2,& \left(15\right)\end{array}$
in which case one can loosely think of ƒ_s,i as an approximation of Φ in the vicinity of i.

[0087] Also, for these optimal parameters, define α_s,i,0≈Φ(c_s(i))−ƒ_s,i(i). Then, for each 0≦n≦N, define the kernel {tilde over (k)}_n((s,i),(t,j))=<α_s,i,n,α_t,j,n>.

[0088] If the functions φ₁, . . . , φ_N and the weighting function w are such that, for each s∈S and i∈I_s the parameters α_s,i,1, . . . , α_s,iN, that will minimize Equation (15) are unique, then for any 0≦n≦N, there is a vicinity function h_n for S for which {tilde over (k)}_n=h_n*k₀, i.e.,

[0089] $\begin{array}{cc}\langle a_{s,i,n},a_{t,j,n}\rangle =\sum _{i^{\prime },j^{\prime }}{h}_n\left(s,i,i^{\prime }\right)h_n\left(t,j,j^{\prime }\right)k_0\left(\left(s,i^{\prime }\right),\left(t,j^{\prime }\right)\right),& \left(16\right)\end{array}$
the proof of which follows:

[0090] Fix s ∈ and I . For the objective function

[0091] $\begin{array}{cc}J=\frac{1}{2}\sum _{i^{\prime }\in I_s}w\left(s,i,i^{\prime }\right){f_{s,i}\left(i^{\prime }\right)-\Phi \left(c_s\left(i^{\prime }\right)\right)}^2,& \left(17\right)\end{array}$
and for n_—™{1, . . . , N}, the partial derivative of J with respect to the parameter α_s,i,n is

[0092] $\begin{array}{cc}{\partial }_{a_{s,i,n}}J=\sum _{i^{\prime }\in I_s}w\left(s,i,i^{\prime }\right){\varphi }_n\left(p_s\left(i,i^{\prime }\right)\right)\left(f_{s,i}\left(i^{\prime }\right)-\Phi \left(c_s\left(i^{\prime }\right)\right)\right).& \left(18\right)\end{array}$
These N partial derivatives are zero when

[0093] $\begin{array}{cc}\sum _{i^{\prime }\in I_s}w\left(s,i,i^{\prime }\right){\varphi }_n\left(p_s\left(i,i^{\prime }\right)\right)\sum _{n=1}^N{\alpha }_{s,i,n}{\varphi }_n\left(p_s\left(i,i^{\prime }\right)\right)=\sum _{i^{\prime }\in I_z}w\left(s,i,i^{\prime }\right){\varphi }_n\left(p_s\left(i,i^{\prime }\right)\right)\Phi \left(c_s\left(i^{\prime }\right)\right)\iff W\left(\begin{array}{c}\begin{array}{c}{a}_{s,\mathrm{in}}\\ ⋮\end{array}\\ a_{s,i,N}\end{array}\right)=\sum _{l^{\prime }\in I_s}w\left(s,i,i^{\prime }\right)\Phi \left(c_s\left(i^{\prime }\right)\right)\left(\begin{array}{c}\begin{array}{c}{\varphi }_1\left(p_s\left(i,i^{\prime }\right)\right)\\ ⋮\end{array}\\ {\varphi }_N\left(p_s\left(i,i^{\prime }\right)\right)\end{array}\right),& \left(19\right)\end{array}$
where the N×N real matrix W has entries

[0094] $\begin{array}{cc}{W}_{n,n^{\prime }}=\sum _{I^{\prime }\in I_s}w\left(s,i,i^{\prime }\right){\varphi }_{n^{\prime }}\left(p_s\left(i,i^{\prime }\right)\right){\varphi }_n\left(p_s\left(i,i^{\prime }\right)\right).& \left(20\right)\end{array}$
If the matrix is invertible, one can write

[0095] $\begin{array}{cc}\begin{array}{c}{a}_{s,i,n}=\sum _{I^{\prime }\in I_s}\Phi \left(c_s\left(i^{\prime }\right)\right){w\left(s,i,i^{\prime }\right)\left[W^{-1}\left(\begin{array}{c}\begin{array}{c}{\varphi }_1\left(p_s\left(i,i^{\prime }\right)\right)\\ ⋮\end{array}\\ {\varphi }_N\left(p_s\left(i,i^{\prime }\right)\right)\end{array}\right)\right]}_n\\ =\sum _{i^{\prime }\in I_s}\Phi \left(c_s\left(i^{\prime }\right)\right)h_n\left(s,i,i^{\prime }\right),\end{array}& \left(21\right)\end{array}$
where h_n is defined appropriately. This relationship follows for n=1, . . . , N and the case n=0 follows from the definition of α_α,s,0

[0096] Locational kernels define a notion of similarity between structures s and t that is relevant to particular locations i and j in the structures. For a locational kernel k, k((s,i), (t,j)) should be thought of as the similarity of the components of s in the locality of i with the components of t in the locality of j.

[0097] If K_A is a kernel on a component set A, and S is a class of structures on A, then one can define a locational kernel on S via
k((s,i)(t,j))=K_A(c_s(i), c_t(j))  (22)
where s, t∈S, i∈I_s, and j∈I_t.

[0098] Using a locational kernel, two structures s, t∈S can be viewed as a rich collection of similarities of their components. Then, a variety of operations can be performed on locational kernels k₀, k₁ . . . on S to obtain another locational kernel. For example:

[0099] 1. Addition:
(k₀+k₁)((s,i),(t,j))=k₀((s,i),(t,j))+k₁((s,i), (t,j))  (23)

[0100] 2. Scalar Multiplication: for λ≧0,
(λk₀)((s,i),(t,j))=λk₀((s,i),(t,j))  (24)

[0101] 3. Multiplication:
(k₀k₁)((s,i),(t,j))=k₀((s,i),(t,j))k₁((s,i),(t,j))  (25)

[0102] 4. Pointwise Limits:

[0103] $\begin{array}{cc}\left(\underset{n->\infty }{\lim }{k}_n\right)\left(\left(s,i\right),\left(t,j\right)\right)=\underset{n->\infty }{\lim }{k}_n(\left(s,i\right),\left(t,j\right)& \left(26\right)\end{array}$
provided the limit exists for all s, t∈S and I_s,j∈I_t

[0104] 5. Argument transformations: if T is a set of structures and ƒ: {hacek over (T)}→{hacek over (S)}, then
k_ƒ((s,i),(t,j))=k₀(ƒ(s,i),ƒ(t,j))  (27)
is a locational kernel on T. As a special case, if T=S and I_s=I_t for all s, t∈S, one might have ƒ(s,i)=(ƒ_s(s),ƒ_I(i)) for some functions ƒ_s: S→S and ƒ_I: I_s→I_s.

[0105] 6. Convolution with a Vicinity Function h for S:

[0106] $\begin{array}{cc}\left(h*k_0\right)\left(\left(s,i\right),\left(t,j\right)\right)=\sum _{\underset{j^{\prime }\in I_t}{I^{\prime }\in I_s}}h\left(s,i,i^{\prime }\right)h\left(t,j,j^{\prime }\right)k_0\left(\left(s,i^{\prime }\right),\left(t,j^{\prime }\right)\right)& \left(28\right)\end{array}$

[0107] 7. Convolution with a real-valued function ν:{(s,t,i,i′,j,j′): s, t∈S, i,i′∈I_s, j,j′∈I_t}→R:

[0108] $\begin{array}{cc}\left(v*k_0\right)\left(\left(s,i\right),\left(t,j\right)\right)=\sum _{\underset{j^{\prime }\in I_t}{I^{\prime }\in I_s}}v\left(s,t,i,i^{\prime },j,j^{\prime }\right)k_0\left(\left(s,i^{\prime }\right),\left(t,j^{\prime }\right)\right)& \left(29\right)\end{array}$

[0109] These operations can be combined to obtain, e.g., power series (with nonnegative coefficients) of locational kernels. Moreover, the convolution can be iterated. For example, starting with a kernel k_A on the component set A, k₀ can be defined as the corresponding locational kernel on S. The multiplication and convolution operations are iterated as follows. For n=1, 2, . . . , define
k_n=k₀(h*k_n−1),  (30)
and, with k′₀=k″₀,
k′_n=k′_n−1(h*k₀).  (31)
Note that k₁=k′₁, and k′_n=k₀(h*k₀)ⁿ.

[0110] Loosely speaking, k′_n defines the similarity of s at i and t at j as a weighted product of the k₀ -similarities of n nearby components of s and t, where the weights are given by the product h(s,i₁,i) . . . h(s,i_n,i). The kernel k_n works in a similar way, but in this case the weights are given by the product h(s,i₁,i₂) . . . h(s,i_n−1,i_n). h(s,i_n,i).

[0111] More formally, the following result is obtained:

[0112] Let k_d(α,b)=<Φ(α), Φ(b)> for some feature map Φ: A→l₂,

Where d∈N∪{∞}. One can write
k_n((s,i),(t,i))=<Ψ(s,i),Ψ(t,j)>  (32)
where Ψ(s,i) is an element of l₂ with components

[0113] $\begin{array}{cc}{\Psi \left(s,i\right)}_{i_1,\dots ,i_n}=\sum _{j_1,\dots ,j_n}\prod _{i=1}^{n}h\left(s,j_1,j_{l-1}\right){\Phi \left(c_s\left(j_l\right)\right)}_{i_1},& \left(33\right)\end{array}$
where is i₁∈{1, . . . , d}. for l=1, . . . , n, and the sum is over (j₁, . . . , j_n)∈I_sⁿ, and j₀=i .

[0114] Further,
k′_n((s,i),(t,j))=<Ψ(s,i),Ψ′(t,j)>,  (34)
where Ψ(s,i) is an element of l₂ with components

[0115] $\begin{array}{cc}{{\Psi }^{\prime }\left(s,i\right)}_{i_1,\dots ,i_n}=\sum _{j_1,\dots ,j_n}\prod _{l=1}^{n}h\left(s,j_1,i\right){\Phi \left(c_s\left(j_1\right)\right)}_{i_1}& \left(35\right)\end{array}$
where the sum is over (j₁, . . . , j_n)∈I_sⁿ.

[0116] The next step in the process for constructing kernels for structured data is to obtain kernels from the locational kernels. Given a locational kernel, one can obtain a kernel on the set of structures in using a number of different methods.

[0117] The first method comprises summing over the indices:

[0118] If S is a set of finite structures and k is a locational kernel on S, the kernel K on S can be defined as

[0119] $\begin{array}{cc}K\left(s,t\right)=\sum _{\underset{j\in I_t}{i\in I_s}}k\left(\left(s,i\right),\left(t,j\right)\right)& \left(36\right)\end{array}$
for s, t∈S. More generally, if for every s∈S there is a weighting function w_s: I_s→R, then one can define the kernels K on S as

[0120] $\begin{array}{cc}K\left(s,t\right)=\sum _{\underset{j\in I_t}{i\in I_s}}{w}_s\left(i\right)w_t\left(j\right)k\left(\left(s,i\right),\left(t,j\right)\right).& \left(37\right)\end{array}$
If the structures in S are not all finite, but k is bounded and each w_s is absolutely summable, then this definition still gives a kernel. Viewing the kernel as some kind of average of locational kernels looking at the structure's components might yield principled ways of dealing with missing data, i.e., missing components.

[0121] Proof of the definition in Equation 37 is as follows: Let Φ: {hacek over (S)}→l₂ be the feature map for k, so that
k((s,i),(t,j))=<Φ(s,i),Φ(t,j)>.  (38)

[0122] $\begin{array}{cc}k\left(\left(s,i\right),\left(t,j\right)\right)=\langle \Phi \left(s,i\right),\Phi \left(t,j\right)\rangle .& \left(38\right)\\ \mathrm{Then},& \\ \underset{i\in I_{s}j\in I_t}{K\left(s,t\right)}=\sum _{t\in I_s}\sum _{j\in I_t}{w}_s\left(i\right)w_t\left(j\right)\langle \Phi \left(s,i\right),\Phi \left(t,j\right)\rangle & \left(39\right)\\ =\langle \left(\sum _{t\in I_s}{w}_s\left(i\right)\Phi \left(s,i\right)\right),\left(\sum _{j\in I_t}{w}_t\left(j\right)\Phi \left(t,j\right)\right)\rangle & \left(40\right)\\ =\langle \psi \left(s\right),\psi \left(t\right)\rangle ,& \left(41\right)\end{array}$
where

[0123] $\psi \left(s\right)=\sum _{i\in I_s}\underset{i\in I_s}{w_s}\left(i\right)\Phi \left(s,i\right).$
Thus, K is a kernel on S provided that ψ maps to l₂. But

[0124] $\begin{array}{cc}\psi \left(s\right)\le \sum _{i\in I_s}w_s\left(i\right)\Phi \left(s,i\right)=\underset{i\in I_s}{\max }\Phi \left(s,i\right)\sum _{i\in I_s}w_s\left(i\right),& \left(42\right)\end{array}$
and both factors are finite. The boundedness of k and the absolute summability of the constant weighting function w_s(i)≡1 are implied by the finiteness of I_s.

[0125] A second method for obtaining the kernel on the set of structures given a location kernel is fixing the indices.

• • [0126] If i is a function on S satisfying i(s)∈I_s, then
    K(s,t)=k((s,i(s)),(t,i(t)))  (43)
    is a kernel. Note that one must substitute the same function i in both of k's arguments, to ensure that the result is symmetric in s,t. As a special case, if I_s=I_t for all s,t∈S. one can choose a constant function i.

[0127] As a third method, one could use
K(s,t)=max k((s,i),(t,j)),  (44)
to obtain a notion of similarity that is invariant with respect to certain transformations of the index sets (e.g., translations of images), cf. the notion of ‘kernel jittering’ as discussed by D. DeCoste and M. C. Burl in “Distortion-invariant recognition via jittered queries”, Computer Vision and Pattern Recognition (CVPR-2000), June 2000.

[0128] In addition to the foregoing operations, one can apply all known manipulations allowed for kernels. Thus, a wealth of different kernels can be obtained. Further, some ‘classical’ kernels can be used as special cases:

• • [0129] The Gaussian RBF (radial basis function) kernel is a product (over all index positions) of locational kernels constructed from Gaussian RBF kernels k_A whose indices have been fixed.
  • [0130] a Polynomial kernels of degree n can be obtained via convolutions as follows: consider the case where A=R and I_s=I_t=I, use the shorthands c_s(i)=s_i,c_t(i)=t_i, and define
    k₀((s,i),(t,j))=δ_ij  (45)
    as well as, for some real-valued function u(i,i′), and n∈N,

[0131] $\begin{array}{cc}{k}_n\left(\left(s,i\right),\left(t,j\right)\right)={\delta }_{\mathrm{ij}}\sum _{i^{\prime },j^{\prime }\in I}{s}_{i}u\left(i,i^{\prime }\right)t_{j}u\left(j,j^{\prime }\right)k_{n-1}\left(\left(s,i^{\prime }\right),\left(t,j^{\prime }\right)\right).& \left(46\right)\end{array}$

[0132] Note that this has the form k_n=k₀(h*k_n−1), as introduced above, where the vicinity function h(s,i,i′)=s_iu(i,i′) is used. For constant u, the result is the homogeneous polynomial kernel as shown in the following:

[0133] For n∈N₀, the vicinity function h(s,i,i′)=s_i and the component kernel k₀(s,i),(t,j))=δ_ij lead to a locational kernel k_n, with the property that averaged over all indices, the homogeneous polynomial kernel is recovered.

[0134] $\begin{array}{cc}\frac{1}{I}\sum _{i,j\in I}{k}_n\left(\left(s,i\right),\left(t,j\right)\right)=\frac{1}{I}\sum _{i\in I}{k}_n\left(\left(s,i\right),\left(t,j\right)\right)={\left(\sum _{i\in I}{s}_i{t}_i\right)}^n.& \left(47\right)\end{array}$

[0135] The locational kernel k_n((s,i),(t,j)) can thus be thought of as the kernel computing all n-th order product features ‘belonging’ to index i.

[0136] As proof of the preceding, by induction on n, for n=0, Equation 47 holds true. Supposing, then, that it also holds true for n−1, where n≧1, yielding:

[0137] $\begin{array}{cc}\begin{array}{c}\frac{1}{I}\sum _{i,j\in I}{k}_n\left(\left(s,i\right),\left(t,j\right)\right)=\frac{I}{I}\sum _{i,j}{\delta }_{\mathrm{ij}}\sum _{i^{\prime },j^{\prime }}{s}_i{t}_j{k}_{n-1}\left(\left(s,i^{\prime }\right),\left(t,j^{\prime }\right)\right)\\ =\sum _i{s}_i{t}_i\frac{1}{I}\sum _{i^{\prime },j^{\prime }}{k}_{n-1}\left(\left(s,i^{\prime }\right),\left(t,j^{\prime }\right)\right)\\ =\sum _i{s}_i{t_i\left(\sum _i{s}_i{t}_i\right)}^{n-1}\\ ={\left(\sum _i{s}_i{t}_i\right)}^n.\end{array}& \left(48\right)\end{array}$

[0138] For non-constant functions u, polynomial kernels are obtained where different product features are weighted differently. For example, in the processing of genetic strings, one could use a function u which decays with the distance (on the string) of i and j, e.g., for some c>0,
u(i,j)=max {0, 1−c·|i−j|}.  (49)

[0139] Thus, one can obtain “locality-improved” kernels such as the ones that have successfully been used in start codon recognition and image processing.

[0140] Another interesting generalization of polynomial kernels suggested by the above view is the use of another function instead of δ_ij, such as 1_|i−j|<c, for some c∈n. This way, one should obtain polynomial kernels which compare, e.g., sequences that are not precisely registered, thus obtaining some degree of transitional invariance.

[0141] $\begin{array}{cc}\langle a_{s,i,n},a_{t,j,n}\rangle =\underset{i^{\prime },j^{\prime }}{\sum h_n}\left(s,i,i^{\prime }\right)h_n\left(t,j,j^{\prime }\right)k_0\left(\left(s,i^{\prime }\right),\left(t,j\right)\right)& \left(50\right)\end{array}$

[0142] To provide an example, in the homogeneous polynomial case, where h(s,i,i′)=s_i, h(s,j₁,j₁₋₁)=h(s,j₁,i)=s_j−1 Therefore, Ψ=Ψ′, and thus Equation 47 implies the corresponding result for k′_n:

[0143] For n∈N₀, h(s,i,i′)=s_i, and k₀((s,i),(t,j))=δ_ij,

[0144] $\begin{array}{cc}\frac{1}{I}\sum _{i,j\in I}{k}_n^{\prime }\left(\left(s,i\right),\left(t,j\right)\right)=\frac{1}{I}\sum _{i\in I}{k}_n^{\prime }\left(\left(s,i\right),\left(t,i\right)\right)={\left(\sum _{i\in I}{s}_i{t}_i\right)}^n.& \left(51\right)\end{array}$

[0145] Moreover, the component kernel k₀((s,i),(t,j))=k_A(s_i,t_j)=δ_ij can trivially be represented as a dot product in l₂^d, where d=|I|, via δ_ij=<e_i,e_j>, with {e₁, . . . , e_d} an orthonormal basis of l₂^d,. Therefore,

[0146] $\begin{array}{cc}\begin{array}{c}{\Psi \left(s,i\right)}_{i_0,\cdots ,i_n}=\sum _{j_1,\cdots ,j_n}\prod _{l=1}^n{s_{j_l}\left(e_{j_l}\right)}_{i_l}\\ =\sum _{j_1,\cdots ,j_n}\prod _{l=1}^n{s}_{j_l}{\delta }_{j_l{i}_l}\\ =\prod _{l=1}^n{s}_{i_l},\end{array}& \left(52\right)\end{array}$
the well-known feature map of the homogeneous polynomial kernel, computing all possible products of n components. Note that this is independent of i. Therefore, when summing over all i, the result is a kernel which has the same feature map, up to the overall factor |I|.

[0147] Suppose S is the set of finite strings over the finite alphabet A, his defined as
h(s,i,i′)=1(i>i′)λ^i−i′  (53)
for some λ∈[0,1), and k(α,b)=1(α=b). Then, each component of Φ(α) has the form
Φ(α)_i=1(α=α_i),  (54)
where A={α₁, . . . , α_|A|}. In this case,
k_n((s,i)(t,j)=<Ψ(s,i),Ψ(t,j)>,  (55)
where each component of Ψ(s,i) is of the form

[0148] $\begin{array}{cc}\begin{array}{c}{{\Psi }^{\prime }\left(s,i\right)}_{i_0,i_1,\cdots ,i_n}=\sum _{i=j_1,\cdots ,j_n>i}{\lambda }^{\sum _{l=1}^n{j}_l-i}\prod _{l=1}^n{\Phi \left(c_s\left(j_l\right)\right)}_{i_l}\\ =\sum _{i=j_1<\cdots -j_n}{\lambda }^{\sum _{l=1}^n{j}_l-i}1(\forall l,sj_l=a_{i_l}\end{array}& \left(56\right)\end{array}$
That is, the feature space has a component corresponding to each sequence (α_i0, . . . , α_in) and n+1 characters from A, and the value of that component is the sum over all matching subsequences
(s[i], s[j_i], . . . , s[j_n])=(α_i0, . . . , α_in)  (57)
of λ raised to the power of the length of the gap between the first and last of these characters. This is the string kernel described by H. Lodhi, J. Shawe-Taylor, N. Cristianini, and C. Watkins in “Text classification using string kernels”, Technical Report 2000-79, NeuroCOLT, 2000. Published in: T. K. Leen, T. G. Dietterich and V. Tresp (eds.), Advances in Neural Information Processing Systems 13, MIT Press, 2001, which is incorporated herein by reference.

[0149] Similarly,
k′_n((s,i),(t,j))=<Ψ(s,i),Ψ(t,j)>,  (58)
Where each component of Ψ(s,i) is of the form

[0150] $\begin{array}{cc}\begin{array}{c}{{\Psi }^{\prime }\left(s,i\right)}_{i_0,i_1,\dots ,i_n}=\sum _{j_1,\dots ,j_n>l}{\lambda }^{\sum _{l=1}^n{j}_l-i}\sum _{l=1}^n{\Phi \left(c_s\left(j_l\right)\right)}_{i_l}\\ =\sum _{i=j_1,\dots ,j_n>i}{\lambda }^{\sum _{i=1}^n{j}_i-i}1\left(\forall l,sj_l=a_{i_l}\right).\end{array}& \left(59\right)\end{array}$
In this case, the value of the component for each sequence (αi₀, . . . , αi_n) of n+1 characters from A is a sum over all matching, but not necessarily ordered, subsequences (s[i], s[j₁], . . . s[j_n]=(αi₀, . . . , αi_n). For each of these sequences, the component is incremented by λ raised to a power that depends on the distances from i to each matching character. This is a bit like a bag of words approach, in the sense that the characters can appear in any order, but each character's distance from i incurs a penalty. Using another viewpoint, each i,j pair defines the centers of clusters in the two structures, and the value of the locational kernel for those centers is a sum over all sequences of n characters of λ raised to the power of the sum over the sequence of the distances from the character to the center.

[0151] The nth order string kernel described by H. Lodhi, et al. can be defined for fixed strings s, t using:

[0152] $\begin{array}{cc}{K}_0^{\prime }\left(i,j\right)=1\mathrm{for}\mathrm{all}i,j\mathrm{and}{K}_k^{\prime }\left(i,j\right)=0\mathrm{for}\min \left(i,j\right)<k,\begin{array}{c}{K}_k^{\prime }\left(i+1,j\right)=\lambda K_k^{\prime }\left(i,j\right)+\sum _{j^{\prime }=1}^{j}1(s\left[i+1\right]\\ =t\left[j^{\prime }\right])K_{k-1}^{\prime }\left(i,j^{\prime }-1\right){\lambda }^{j-j^{\prime }+2},\end{array}& \left(60\right)\\ K_n\left(i,j\right)=0\mathrm{for}\min \left(i,j\right)<n\begin{array}{c}{K}_n\left(i+1,j\right)=K_n\left(i,j\right)+\sum _{j^{\prime }=1}^{j}1(s\left[i+1\right]\\ =t\left[j^{\prime }\right])K_{n-1}^{\prime }\left(i,j^{\prime }-1\right){\lambda }^2.\end{array}& \left(61\right)\end{array}$
Then, the nth order kernel for two strings s, t is defined as K_n(|s|,|t|).

[0153] The following result shows that the string kernel is of the form described in Equation 30, with a simple exponential weighting function.

[0154] The nth order string kernel of Lodhi et al is given by

[0155] $\begin{array}{cc}{K}_n\left(s,t\right)={\lambda }^{2n}\sum _{i,j}{L}_{n-1}\left(i,j\right),& \left(62\right)\end{array}$
where, for all integer i, j,

[0156] $\begin{array}{cc}{L}_0\left(i,j\right)=\{\begin{array}{cc}1\left(s\left[i\right]=t\left[j\right]\right)& \mathrm{if}1\le i\le s\mathrm{and}1\le j\le t,\\ 0& \mathrm{otherwise}\end{array}{L}_k\left(i,j\right)=L_0\left(i,j\right)\sum _{i^{\prime }\le i-1}\sum _{j^{\prime }\le j-1}{\lambda }^{\left(i-1\right)-i^{\prime }}{\lambda }^{\left(j-1\right)-j^{\prime }}{L}_{k-1}\left(i^{\prime },j^{\prime }\right).& \left(63\right)\end{array}$

[0157] This can be proven by first showing by induction that
L_k(i,j)=λ^−2kL₀(i,j)K′_k(i−1,j−1)  (64)
for all i, j, k. (Arbitrary values can be assigned to K′_k when its arguments are outside its range of definition, since L₀(i, j) is zero in that case.) Clearly, Equation 64 is true for k=0 and for all i, j. Suppose it is true for some k≧0, and consider L_k+1. By Equation 63,

[0158] $\begin{array}{cc}\begin{array}{c}{L}_{k+1}\left(i,j\right)=L_0\left(i,j\right)\sum _{i^{\prime }\le i-1}\sum _{j^{\prime }\le j-1}{\lambda }^{\left(i-1\right)-i^{\prime }}{\lambda }^{\left(j-1\right)-j^{\prime }}{L}_k\left(i^{\prime },j^{\prime }\right)\\ =L_0\left(i,j\right)\sum _{i^{\prime }\le i-1}\sum _{j^{\prime }\le j-1}{\lambda }^{l-1-l^{\prime }+j-1-j^{\prime }-2k}{L}_0\left(i^{\prime },j^{\prime }\right)K_k^{\prime }(i^{\prime }-1,\\ j^{\prime }-1)\\ ={\lambda }^{-2k-2}{L}_0\left(i,j\right)K_{k+1}^{\prime }\left(i-1,j-1\right).\end{array}& \left(65\right)\end{array}$

[0159] Finally, proving Equation 62, from the definition of K_n, it can be shown by induction that

[0160] $\begin{array}{cc}\begin{array}{c}{K}_n\left(i,j\right)={\lambda }^2\sum _{i^{\prime }=1}^i\sum _{j^{\prime }=1}^{j}1\left(si^{\prime }=tj^{\prime }\right)K_{n-1}^{\prime }\left(i^{\prime }-1,j^{\prime }-1\right)\\ ={\lambda }^2\sum _{i^{\prime }=1}^i\sum _{j^{\prime }=1}^j{L}_0\left(i^{\prime },j^{\prime }\right)K_{n-1}^{\prime }\left(i^{\prime }-1,j^{\prime }-1\right)\\ ={\lambda }^{2n}\sum _{i^{\prime }=1}^i\sum _{j^{\prime }=1}^j{L}_{n-1}\left(i^{\prime },j^{\prime }\right)\mathrm{by}\mathrm{Equation}64.\end{array}& \left(66\right)\end{array}$

[0161] The above-described locational kernels and method for building on the locational kernels provide a method for defining a kernel similarity measure for general structure objects by comparing the objects centered on individual components thereof. Such kernels and methods may be applied to text documents, DNA sequences, images, time-series data, and spectra, and may be used for analyses including pattern recognition, regression estimation, novelty detection, density estimation and clustering. In applications to biological data, the kernel similarity measure can be used for microarray gene expression measurements, protein measurements and medical images for classification of diseases and disease treatment.

[0162] The dataset consists of a set of curves coded as vectors of length 1688 and that are described as spectra. The task is to discriminate these spectra from a learning set built of 151 spectra of class 0 and 145 spectra of class 1. Thus, the learning set has a size of 296. The generalization set is not known: it is formed only by the spectra but not by the corresponding labels.

[0163] A linear SVM has been trained on the whole learning set. The dataset is linearly separable with a margin of 1.3e-3.

[0164] In the experiments, the dataset is used as it is (referred as the “original dataset”) or it is normalized (referred as the “normalized dataset”). The normalization consists in subtracting for each spectrum its mean over its coordinates and then to divide all spectra by their own standard deviation.

[0165] To deal with this discrimination problem, a linear SVM is applied as follows:

[0166] $\underset{w,b}{\min }{w}_2^2+C\sum _{i=1}^m{\xi }_i\mathrm{subject}\mathrm{to}\text{:}{y}_i\left(\langle w,x_i\rangle +b\right)\ge -{\xi }_i\mathrm{and}{\xi }_i\ge 0$
where m=296 is the number of learning points, <.,.> is the dot product, x_i are the spectra of the learning set and y_i are their classes.

[0167] The protocol that was used is as follows:

• • [0168] 1. Do 100 times:
  • [0169] 2. Draw 80% of the learning set and put it in X.
  • [0170] 3. Train a linear SVM on the set X.
  • [0171] 4. Compute the error on the 20% remaining points of the learning set.
  • [0172] 5. Store the error in err.
  • [0173] 6. End of Do (1).
  • [0174] 7. Output the mean of err over the 100 runs.

[0175] Table 1 provides the generalized error rates for normalized and non-normalized data. The number in parenthesis represents the standard deviation.

[0176]

	TABLE 1
	Dataset	C = +∞	C = 300
	Normalized dataset	23.3% (±4.9%)	22.7% (±5.2%)
	Non-Normalized dataset	23.3% (±4.9%)	25.3% (±4.8%)

[0177] The same experiments were performed with a reduced number of features (the first 543 coordinates of each spectra and the coordinates 1177 to 1500, selected by taking the regions of the graphs that were most different between the two classes 1 and 0), resulting in a generalization error of 22.7% (±5%) with C=∞ on the non-normalized learning set. (The same experiment was not performed with the normalized dataset.)

[0178] Another experiment involved splitting the original learning set with all the coordinates into three pieces. The first one (148 spectra) was the set used to define the linear SVM. The second one (59) was used to find the hyperparameter C and the third one (89) was used to test the SVM. The error obtained with a linear SVM on the last set (non-normalized) is 22.5% with C=200. The same experiments with the normalized dataset generated a generalization error of 23.6% with C=20.

[0179] Two additional methods were tested:

[0180] 1) The 1-Nearest Neighbor (“1NN”) classifier: the output of this system on a new spectrum is computed by taking the class of the nearest spectrum in the learning set.

[0181] 2) The Least Min Square (“LMS”) classifier: linear whose parameters are obtained with the following optimization problem:

[0182] $\underset{w,b}{\min }\sum _{i=1}^m{\left(\langle w,x\rangle +b-y_i\right)}^2.$

[0183] The experiments are the same as for the linear SVM. Table 2 shows that, both methods have a greater generalization error than the linear SVM. The number in parenthesis represents the standard deviation.

[0184]

	TABLE 2
	Dataset	1-NN	LMS
	Normalized dataset	23.5% (±5.2%)	27.2% (±5.7%)
	Non-Normalized dataset	35.8% (±6.3%)	28.1% (±9.1%)

[0185] The preliminary results support the fact that this problem may not be solved easily despite the fact that the problem is linearly separable. Non-linear SVM with accurate kernels should be used and a preprocessing step could also be useful. These two steps in the process of setting up a good system require some knowledge on the dataset. It is apparent that the linear system still learns something from this dataset since its error rate is less than 50% (the best solution is 22.5% error rate).

[0186] Table 3 sums up the results of the preceding experiments with the results in increasing order. “Norm” indicates that the normalized dataset was used, while “Non-norm” indicates the non-normalized data. “One-run means one run of a SVM whose coefficient C has been defined on a validation set. The latter are presented in decreasing order.

[0187]

TABLE 3
Description	Generalization error (std)
SVM (C = 200, Non-Norm, one run)	22.5%
SVM (C = 20, Norm, one run)	23.6%
SVM (C = 300, Norm)	22.7% (±5.2%)
SVM (C = ∞, Norm)	23.3% (±4.9%)
SVM (C = ∞, Non-Norm)	23.3% (±4.9%)
1-NN (Norm)	23.5% (±5.2%)
SVM (C = 300, Non-Norm)	25.3% (±4.8%)
LMS (Norm)	27.2% (±5.7%)
LMS (Non-Norm)	28.1% (±9.1%)
1-NN (Non-Norm)	35.8% (±6.3%)

[0188] Next, experiments were performed with non-linear SVMs on the same dataset as in the previous experiments, where the data consists of mid IR spectra of biological samples at 4 wave number resolution. During data collection, care was taken to avoid instrument drifting between the measurements of the two classes. The data are properly labeled and various linear discriminants, including LDA and :partial least square” were used directly on the spectrum used as a feature vector. A feature selection technique was also used.

[0189] The kernels used for this series of experiments are the following:

[0190] $k\left(f,g\right)=\int f\left(x\right)g\left(x-t\right)\exp \left(-\frac{t^2}{\sigma }\right)dxdt$
where ƒ and g are spectra. The value of σ controls the smoothness of the representation. Experiments were performed for both normalized and non-normalized data.

[0191]

TABLE 4
Value of σ	Generalization error (std)	Learning error (std)
2.5	32.1% (±6.3%)	23.2% (±5.0%)
5	36.3% (±5.5%)	35.8% (±3.7%)
7.5	38.7% (±11.5%)	35.5% (±10.6%)
10	38.8% (±7.6%)	34.7% (±6.2%)

[0192] The results displayed in Table 4 show that such a kernel does not provide good systems for normalized and non-normalized data. The generalization error is always greater than for linear systems. Smoothness may then appear as a bad property for this particular problem. The fact the learning error is not zero is strong evidence that the smooth representation induced by such kernel is not adapted for this discrimination task. The same experiments were run with a very small σ¹, producing the same result as for a linear SVM.

[0193] Next, the same protocol as for linear SVM previously described was used, but with polynomial kernels:

[0194] $K\left(f,g\right)={\left(\frac{\langle f,g\rangle }{1688}+1\right)}^d$
where d is the degree of the polynomial. All experiments were performed with C=∞. The normalization factor 1/1688 has been used in other experimental settings and has been found to be useful.

[0195] The results shown in Tables 5 and 6 are that the learning error for polynomial of degree 1 with C=∞ is not zero. This unusual result may be related to numerical anomalies in the implementation of the SVM software. The best result obtained here is a generalization error of 21.2% with the polynomial of degree 2 such that the improvement from the linear model is not significant.

[0196]

TABLE 5
Value of d	Generalization error (std)	Learning error (std)
1	22.9% (±5.4%)	4.6% (±4.7%)
2	21.2% (±4.7%)	0.3% (±0.3%)
3	22.0% (±5.2%)	0% (±0%)
4	23.4% (±5.1%)	0% (±0%)
5	23.4% (±5.0%)	0% (±0%)

[0197]

TABLE 6
Value of d	Generalization error (std)	Learning error (std)
1	23.5% (±5.2%)	4.2% (±0.9%)
2	20.8% (±4.7%)	0.3% (±0.3%)
3	22.6% (±4.7%)	0% (±0%)
4	22.9% (±5.6%)	0% (±0%)
5	22.3% (±4.7%)	0% (±0%)

[0198] Next, Gaussian kernels were used with C=∞. The kernel used is as

[0199] $k\left(f,g\right)=\exp \left(\frac{{f-g}_2^2}{1688{\sigma }^2}\right)$
where σ is the standard deviation of the kernel. Results of this experiment are presented in Tables 7 and 8. In order to ensure that an accurate value for σ was used, a SVM was run repeatedly for sigma between 0.1 to 10 at increments of 0.1. The best value for σ was obtained for σ=1. Nonetheless, the improvement from the linear model is not significant.

[0200]

TABLE 7
Value of σ	Generalization error (std)	Learning error (std)
0.0001	52.9% (±4.4%)	0% (±0%)
0.001	52.1% (±5.1%)	0% (±0%)
0.01	46.7% (±5.5%)	0% (±0%)
0.1	23.3% (±5.5%)	0% (±0%)
1	21.4% (±5.4%)	0% (±0%)
10	22.6% (±5.6%)	6.5% (±0.9%)

[0201]

TABLE 8
Value of σ	Generalization error (std)	Learning error (std)
0.0001	53.6% (±4.2%)	0% (±0%)
0.001	51.2% (±5.0%)	0% (±0%)
0.01	45.0% (±5.7%)	0% (±0%)
0.1	28.2% (±5.9%)	0% (±0%)
1	21.1% (±5.5%)	0% (±0%)
10	28.7% (±5.2%)	17.0% (±1.5%)

[0202] According to the nature of the learning problem, it can be useful to use kernels for distribution since a spectrum can be interpreted as the distribution of frequencies. To exploit this, a χ² kernel was built as follows:

[0203] $k_{\chi }\left(f,g\right)=\exp \left(-{\chi }^2\left(f,g\right)\right)\mathrm{where}{\chi }^2\left(f,g\right)=\sum _{i=1}^{1688}\frac{{\left(f_i-g_1\right)}^2}{f_i+g_i}$
Choosing C=∞ and using the same protocol as before, the result is presented in Table 9.

[0204]

	TABLE 9
	Generalization error	Learning error
	(std)	(std)
x2 kernel (normalized data)	% (±%)	0% (±0%)
x2 kernel (non-normalized data)	40.7% (±6.5%)	2.1% (±9.5%)

[0205] These results are poor, showing that this kernel, which is not proved to be a Mercer kernel, is not adapted for this task. Many times, the optimization procedure has not converged which indicates that the kernel is not only unacceptable from a learning point of view but also from a computational one.

[0206] In these experiments, the representation of the data is changed in which each point of the original curves is replaced by the parameters of a quadratic polynomial that fits the data in a window width 11 centered at the point. More formally, let ƒ be a spectrum, and let ƒ_i be one of its features. Consider the vector ν=(ν_i=ƒ_i−5, . . . , ν₆=ƒ_i, . . . , ν₁₁=ƒ_i+5) and compute the coefficients of the polyomial α_ix²+b_ix+c_i such that:

[0207] $\sum _{j=1}^{11}{\left({a_i\left(\frac{j}{11}\right)}^2+b_i\left(\frac{j}{11}\right)+c_1-v_j\right)}^2$
is minimum. Then, the spectrum is coded as the sequence (α_i, b_i, c_i, e_i) where

[0208] $e_i={a_i\left(\frac{6}{11}\right)}^2+b_i\left(\frac{6}{11}\right)+c_i-f_i$
is the error of the polynomial approximation for x=i which corresponds to ν₆=ƒi. The result of the experiments are described in Table 10. The best result so far is obtained with this representation (19.9% of generalization error). However, this is not significantly different from the result obtained with the same kernel on the normalized dataset (20.8%).

[0209]

	TABLE 10
	Kernel	Generalization error (std)
	Linear	26.7% (±5.1%)
	Polynomial (d = 2)	22.5% (±5.3%)
	Polynomial (d = 3)	20.9% (±5.4%)
	Polynomial (d = 4)	20.3% (±5.7%)
	Polynomial (d = 5)	19.9% (±5.1%)
	Polynomial (d = 6)	20.3% (±5.3%)
	Polynomial (d = 7)	20.2% (±4.5%)
	Polynomial (d = 8)	20.1% (±4.4)
	Polynomial (d = 9)	19.9% (±5.0%)

[0210] Because the above-described method are still far away from the 2% desired error, improved models are explored.

[0211] First, each spectrum is coded by the locations of the different maximum. This approach is motivated by the way physicists use a spectrum to analyze the physical properties of a molecule.

[0212] Second, data cleaning is used to remove many outliers that make it difficult to generalize.

[0213] In the first method, the spectra is pre-processed in order to compute the location of their maximum/minimum. Each point in a spectrum that is identified as a maximum (resp. minimum) is affected with a value of +1 (resp. −1). All the other points are set to zero. The hope is that this representation codes the number of maximum/minimum as well as their locations. The latter are usually used by physicists to study such spectra. FIG. 6 illustrates an example of one spectrum, showing the original curve and its new representation as a {0,±1}-vector, which are represented as ±1 spikes. Note that there are more extrema coded than can be seen on the curve. This bias is added to avoid loss of information by imposing overly strict conditions for maximum/minimum. Also the last 166 features were removed since they were mainly noise.

[0214] The polynomial kernels are normalized by 10, so that:

[0215] $k\left(f,g\right)={\left(\frac{\langle f,g\rangle }{10}+1\right)}^d$

[0216] Table 11 provides the results for leave-one-out error for different polynomial kernels with C=∞.

[0217]

	TABLE 11
	Value of the degree d	Leave-one-out error
	1	31.4%
	2	29.4%
	3	27.4%
	4	28.0%
	5	30.1%

[0218] The normalization number has been chosen in terms of <ƒ,g> that is of the order of 10. To compute the maximum and minimum of the spectra, the derivatives of the spectra were first computed, then the position of the zero of these derivatives was identified. The computation of the derivative was done by taking a window of width 5 and by fitting a linear model with bias on this window. The linear part was identified as being the derivative of the spectrum for the point corresponding to the center of the window. The zero elements of the derivative of the spectrum were identified simply by looking at the sign changes.

[0219] The results do not provide improvement over the results of earlier tests. However, this does not mean that this kind of approach is not adapted to this problem. Rather, there are many parameters that must be set up in these experiments, including the manners in which the derivative is computed and the extrema are located. Both parameters depend on hand-tuned parameters and can influence the final performance of the model.

[0220] Since all of the foregoing models gave roughly the same results for different experimental settings, it appeared that some of the data in the learning set may have been improperly labeled. In order to remove these data, the following data cleaning strategy was used:

[0221]

1.	Do 100 times
2.	Define a random partition of the learning set
	into two sets: X
	(80% of the data) and Xt (20% of the data).
3.	Do 100 times,
4.	Define a random partition of X into Xl
	(60% of the data in X),
	and Xv (40% of the data in X).
5.	Learn on Xl.
6.	Store the error on Xv as a matrix E:
	E ⁡ ( j ) = { Validation ⁢ ⁢ error ⁢ ⁢ of ⁢ ⁢ the ⁢ ⁢ i th ⁢ ⁢ run ⁢ ⁢ if ⁢ ⁢ j ⁢ ⁢ is ⁢ ⁢ in ⁢ ⁢ X l 0 ⁢ ⁢ Otherwise
7.	End For
8.	Compute the mean error = mean (column-wise) of
	the matrix E.
9.	Order the elements in X with increasing mean error.
10.	Learn the model on the first 80% elements of
	the ordered set X.
11.	Store the error of the model on Xt in vector err.
12.	End Do
13.	Output the mean and the standard deviation of err.

[0222] The data cleaning step removed 20% of the elements in the sets X (which corresponds to 35 data) before learning the final model. The number 20% was chosen arbitrarily. The experiments were performed with the quadratic representation since it produced the best results thus far. A polynomial kernel of degree 2 was selected, and C=∞ as before. Table 12 summarizes the test error results.

[0223]

	TABLE 12
	Value of the degree d	Generalization error (std)
	1	25.0% (±5.6%)
	2	21.3% (±4.4%)
	3	21.1% (±4.7%)

[0224] Once again, the results do not show improvement over earlier methods. However, removing 20% of data from the set X may have been too much and better results could be obtained by removing a smaller percentage of the data. To test this assertion, the same experiment was performed by removing from one to seven data in X. using a linear SVM only. The improvement is not significant.

[0225] Rather than learning with all the features, an experiment was performed where seven SVMs trained on different subsets of the features were combined. Actually, seven SVMs were trained on seven segments of the input space. The first SVM concerns the first 251 features, the second concerns the features at position 252-502. The results included a generalization error of 27.5% (±5%) on the original dataset.

[0226] A bagging method was applied on the quadratic representation. Fifty splits of the data were computed into a training set of size 251 and a test sets 45. Then, a bagging of 30 SVMs was performed by drawing with replacements 251 points from the training sets according to the uniform distribution over the learning set. For the test set, there was an estimated generalization error of 18% (±5.9%) which represents a slight improvement compared to what has been presented so far.

[0227] A different way bagging SVM was tried in which, rather than taking the sign of each single SVM before bagging them, the real output was considered and combined by taking the sign of the sum of their outputs. Also, each single SVM was trained on a set of size 213. The results are shown in Table 13.

[0228]

	TABLE 13
	Representation	Generalization error (std)
	Quadratic (C = ∞)	20% (±5.2%)
	Fourier (C = ∞)	22.4% (±6.7%)

[0229] Finally, the data was split into a learning set (85% of the data) and a test set. Thirty runs of a polynomial SVM (degree 2) were performed on a subset of the training set (80% elements were drawn without replacement in the learning set). The best node was identified by computing its error on the whole learning set, resulting in a generalization error of 19% (±4.2%).

[0230] Noise and Invariance. The selection of a kernel corresponds to the choice of representation of the data in a feature space and, to improve performance, it should therefore incorporate prior knowledge such as known transformation invariances or noise distribution. In a second embodiment of kernel selection according to the present invention, an invariance or noise is represented as vectors in a feature space. The noise vectors are taken into account in constructing invariant support vector classifiers to obtain a decision function that is invariant with respect to the noise.

[0231] In certain classification tasks, there is a priori knowledge about the invariances related to the task. For example, in image classification, it is known that the label of a given image should not change after a small translation or rotation.

[0232] Generally, a local transformation _t depending on a parameter t (for instance, a vertical translation of t pixels) is assumed such that any point x should be considered equivalent to _tx, the transformed point. Ideally, the output of the learned function should be constant when its inputs are transformed by the desired invariance.

[0233] It has been shown that one cannot find a non-trivial kernel which is globally invariant (see C. J. C. Burges, “Geometry and invariance in kernel based methods”, B. Schölkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods—Support Vector Learning. NIT Press, 1999.) For this reason, local invariances are considered for which each training point x_i is associated with a tangent vector dx_i.

[0234] $\begin{array}{cc}\begin{array}{c}{\mathrm{dx}}_i=\underset{t->0}{\lim }\frac{1}{t}\left({ℒ}_t{x}_i-x_i\right)\\ {=\frac{\partial }{\partial t}}_{t=0}{ℒ}_t{x}_i\end{array}& \left(67\right)\end{array}$

[0235] In practice, dx_i can be either computed by finite difference or by differentiation. Note that generally one can consider more than one invariance transformation. The multi invariance case is usually a straightforward extension of the single one.

[0236] A common method for introducing invariances in a learning system is to add the perturbed examples _tx_i in the training set (see P. Niyogi, T. Poggio, and F. Girosi, “Incorporating prior information in machine learning by creating virtual examples”, IEEE Proceedings on Intelligent Signal Processing, 86(11):2196-2209, November 1998). These points are often labeled “virtual examples”. In the SVM (support vector machine) framework, when applied only to the SVs (support vectors), it leads to the “Virtual Support Vector” (“VSV”) method. See, e.g., B. Schölkopf, C. Burges, and V. Vapnik. “Incorporating invariances in support vector learning machines”, Artificial Neural Networks—ICANN'96, volume 1112, pages 47-52, Berlin, 1996. Springer Lecture Notes in Computer Science.

[0237] An alternative to the foregoing is to directly modify the cost function in order to take into account the tangent vectors. This has been successfully applied to neural networks (P. Simard, Y. LeCun, J. Denker, and B. Victorri. “Transformation invariance in pattern recognition, tangent distance and tangent propagation”, G. Orr and K. Müller, editors, Neural Networks: Tricks of the Trade. Springer, 1998.) and linear Support Vector Machines (B. Schölkopf, P. Y. Simard, A. J. Smola, and V. N. Vapnik. Prior knowledge in support vector kernels. In MIT Press, editor, NIPS, volume 10, 1998), both of which are incorporated herein by reference. According to the present embodiment of the invention, such methods are extended to the case of nonlinear SVMs, primarily by using kernel PCA (principal components analysis) methods. See, e.g., B. Schölkopf, A. Smola, and K. R. Müller. Nonlinear component analysis as a kernel eigenvatue problem. Neural Computation, 10:1299-1310, 1998, which is incorporated herein by reference.

[0238] The following description provides a few of the standard notations used for SVMs. Let {(x_iy_i)}1<n be a set of training examples, x_i{dot over (∈)} belonging to classes labeled by y_i{dot over (∈)}{−1,1}. The domain is often, but not necessarily, taken to be ^d, d{dot over (∈)}. In kernel methods, these vectors are mapped into a feature space using a kernel function K(x_ix_j) that defines an inner product in this feature space. The decision function given by an SVM is the maximal margin hyperplane in this space,

[0239] $\begin{array}{cc}g\left(x\right)=\mathrm{sign}\left(f\left(x\right)\right),\mathrm{where}f\left(x\right)=\left(\sum _{i=1}^n{\alpha }_i^0{y}_{i}K\left(x_i,x\right)+b\right).& \left(68\right)\end{array}$
The coefficients a_i⁰ are obtained by maximizing the functional