Enhanced kernel representation for processing multimodal data

A computer-implemented method includes receiving multimodal data. The computer-implemented method further includes generating one or more kernel matrices from the multimodal data. The computer-implemented method further includes generating an equivalent kernel matrix using one or more coefficient matrices, wherein the one or more coefficient matrices are constrained by a nuclear norm. The computer-implemented method further includes initiating one or more iterative processes. Each of the one or more iterative processes includes: calculating an error for the one or more coefficient matrices of the equivalent kernel matrix based on a training set, and initiating a line search for the one or more coefficient matrices of the equivalent kernel matrix. The computer-implemented method further includes, responsive to generating an optimal coefficient matrix, terminating the one or more iterative processes. The method may be embodied in a corresponding computer system or computer program product.

BACKGROUND

The present invention relates generally to optimization methods and machine learning and in particular to implementation of Multiple Kernel Learning (“MKL”) methods in support vector machines (“SVM”).

Multiple Kernel Learning (“MKL”) methods are used to solve classification and regression problems involving multimodal data and machine learning. In machine learning, support vector machines (SVM) are applied to analyze data and recognize patterns, used for classification and regression analysis. More specifically, the application of MKL methods in SVM's can be used to solve various real world problems, such as classification of images, classification of proteins, recognizing hand-written characters, and biometric identity recognition. Generally, MKL methods are applied in situations where the available data involves multiple, heterogeneous data sources. In this case, each kernel may represent the similarity between data points in different modalities. In many cases, a successful identification requires that the object will be similar in both (or all) feature representations. Therefore, a sum of products of kernels is ideal. However, finding the optimal parameters for the sum of products of kernels is a high dimensional optimization problem, as the number of parameters is quadratic in the number of kernels. As a result, the increase in the number of parameters may result in the risk of overfitting data.

SUMMARY

A computer-implemented method includes receiving multimodal data. The computer-implemented method further includes generating one or more kernel matrices from the multimodal data. The computer-implemented method further includes generating an equivalent kernel matrix using one or more coefficient matrices, wherein the one or more coefficient matrices are constrained by a nuclear norm. The computer-implemented method further includes initiating one or more iterative processes. Each of the one or more iterative processes includes: calculating an error for the one or more coefficient matrices of the equivalent kernel matrix based on a training set, and initiating a line search for the one or more coefficient matrices of the equivalent kernel matrix. The computer-implemented method further includes, responsive to generating an optimal coefficient matrix, terminating the one or more iterative processes. The method may be embodied in a corresponding computer system or computer program product.

DETAILED DESCRIPTION

Referring now to various embodiments of the invention in more detail,FIG. 1is a block diagram of one embodiment of a computer system environment suitable for operation in accordance with at least one embodiment of the invention. Within a computer system100, a nuclear norm regularization (“NNR”) program101may receive multimodal data103. For example, the multimodal data103may be audio or visual images, protein or genetic structures, or hand-written characters. The NNR program101may further generate one or more kernel matrices104from the multimodal data103. More specifically, the one or more kernel matrices104may be generated based on a distance metric. For example, the kernel matrices104may include a kernel matrix105, kernel matrix106, kernel matrix107, and kernel matrix108. Each kernel matrix105-108may be formed using a different distance metric.

The NNR program101may further generate an equivalent kernel matrix109using one or more coefficient matrices110. More specifically, the equivalent kernel matrix109may be a linear sum of products of the one or more kernel matrices104and one or more coefficients. The one or more coefficient matrices110may further be constrained by a nuclear norm. For example, the nuclear norm of the one or more coefficient matrices110may be a value less than or equal to one.

The NNR program101may further initiate one or more iterative processes. Each of the one or more iterative processes may include calculating an error112for the one or more coefficient matrices110of the equivalent kernel matrix109based on a training set. More specifically, the error112may be calculated using SVM software. For example, calculating an error112for the one or more coefficient matrices110of the equivalent kernel matrix109may be accomplished using any standard SVM solvers or tools, such as a library for support vector machines (“LIBSVM”). The error112may be a separation measure of the training set and is a function of the one or more coefficient matrices110of the equivalent kernel matrix109. For example, the error112may be a classification error or a regression error in an optimization problem. The function of the one or more coefficient matrices110of the equivalent kernel matrix109may be convex. Furthermore, calculating an error112may include Eigenvalue decomposition.

The NNR program101may further, for each iterative process, initiate a line search for the one or more coefficient matrices110of the equivalent kernel matrix109. More specifically, the line search may include gradient descent. However, the line search may be accomplished by any generally known line search. For example, the line search may be Armijo's step rule or Jacobi-Davidson's step rule. The NNR program101may further, responsive to generating a result113, terminate the one or more iterative processes. The result113may be an optimal coefficient matrix, where the error112for the one or more coefficient matrices110of the equivalent kernel matrix109has been satisfied.

FIG. 2is a flow chart diagram showing various operational steps of the NNR program101according to at least one embodiment of the invention. The present embodiments of the invention implement a NNR program101that utilizes a nuclear norm regularization term. It should be appreciated that by utilizing a nuclear norm regularization term, at least one embodiment of the invention may exist as a convex MKL optimization problem. Furthermore, in accordance with at least one embodiment of the invention, the NNR program101may be implemented in a regression task, classification task, or other machine learning applications.

The NNR program101will be explained in more detail below, however, in doing so, the framework of various embodiments of an optimization problem for an equivalent kernel matrix109in accordance with a classification task will be discussed first, followed by the implementation of the NNR program101within the classification task. In presenting the NNR program101inFIG. 2, a vector may be denoted by a bold letter v and a matrix by an underlined, bold capital letter,A.

At step200, the NNR program101may receive multimodal data103. The multimodal data103may further include N data points {xi} and their corresponding labels {yi}. At step201, the NNR program101may generate one or more kernel matrices104from the multimodal data103. Furthermore, there may exist m mappings ϕβ(xi), where each mapping may induce a kernel matrix105-108:
Kβ(xi,xj)ϕβ(xi),ϕβ(Xj)(Eq. 1)

The tensor product of the mappings may be denoted as
ϕβ1β2(xi)ϕβ1(xi)ϕβ2(xi)   (Eq. 2)

The kernel product may be defined as

A set of kernels may be written as a tensor κ, where the β1, β2kernel is Kβ1β2. The space of m×m matrices with positive elements may be denoted by+m×m, and an element-wise inequality may be denoted by.

At step202, the NNR program101may generate an equivalent kernel matrix109using one or more coefficient matrices110. More specifically, the equivalent kernel matrix109may be a linear sum of products of the one or more kernel matrices104and one or more coefficients. The one or more coefficient matrices110may further be constrained by a nuclear norm. For example, the nuclear norm of the one or more coefficient matrices110may be a value less than or equal to one.

In a first embodiment of the invention (1), an optimization problem for the equivalent kernel matrix109may be defined as:

(Eq.⁢5)mins⁢∑β1,β2=1m⁢〈wβ1⁢β2,wβ1⁢β2〉2+c⁢〈1,ϵ〉⁢⁢w.r.t⁢⁢𝒮={{wβ1⁢β2❘wβ1⁢β2}=1⁢⁢…⁢⁢m},⁢ɛ∈N×1,Z_∈+m×m⁢⁢s.t.𝓎i⁡(∑β1,β2=1m⁢Zβ1,β2⁢〈wβ1⁢β2,ϕβ1⁢β2⁡(xi)〉+b)≥1-ɛ⁢⁢ɛ≥0,0<Z_*≤d,0⪯Z_.(1)
The set of optimization parametersmay include m2vectors {wβ1β2}, representing the normals to separating hyper-planes according to the mapping ϕβ1β2(⋅), the vector of slack variables ε∈N×1and Z, a matrix with elements Zβ1β2, which weigh the relative contribution of the various mappings ϕβ1β2(⋅). For simplicity, it may be assumed that the slack variables are identical for all data points, such that ∈=∈1, where ε∈.

In a second embodiment of the invention (2), a convex optimization problem for the equivalent kernel matrix109may have one or more coefficient matrices110that are convex by the following transformation:
w′|1β2=√{square root over (Zβ1,β2)}wβ1β2.   (Eq. 6)
More specifically, the optimization problem for the equivalent kernel matrix109of the first embodiment (1) may be rewritten in terms of primed variables:

In a third embodiment of the invention (3), by rescaling Z′β1β2·d=Zβ1β2, the convex optimization problem for the equivalent kernel matrix109of the second embodiment (2) may be rewritten as:

(Eq.⁢8)mins′⁢d⁡(∑β1,β2=1m⁢〈wβ1⁢β2′,wβ1⁢β2′〉2⁢zβ1⁢β2′+cd⁢〈1,ϵ〉)⁢⁢s.t.(3)𝓎i⁡(∑β1,β2=1m⁢〈wβ1⁢β2′,ϕβ1⁢β2⁡(xi)〉+b)≥1-ϵ⁢⁢ϵ≥0,0<Z_′*≤1,0≺Z_′.(3⁢a)
The solution of the convex optimization problem for the equivalent kernel matrix109of the third embodiment (3) may be obtained at ∥Z∥*=1, since, for any matrixZwhere ∥Z∥*=x, it is possible to substituteZ/x and obtain a strictly lower value without violating the constraint of (3a). More specifically, the solution may be obtained at the boundary of the feasible domain, ∥Z∥*=1.

The minimum of the convex optimization problem for the equivalent kernel matrix109for the second embodiment (2) and third embodiment (3) may be obtained at the same point. Therefore, the second embodiment (2) of the invention is invariant under the transformation c←c/d, d←1. In other words, there is effectively only a single free parameter in the second embodiment (2), and without loss of generality, d=1. This is particularly useful when the hyper-parameter c is optimized by a grid search, as it reduces dimension of the grid search from two to one.

In a fourth embodiment of the invention (4), the aforementioned second embodiment (2) and third embodiment (3) of the invention may be transformed into a convex optimization problem with dual variables for the equivalent kernel matrix109. For a fixed coefficient matrixZ, the convex optimization problem for the equivalent kernel matrix109may be denoted asA∈N×N, whereA=Z⊙κ=Σzβ1β2,Kβ1β2. Here, ⊙ is the tensor contraction operator, andAis an n×n matrix. Following (Rakotomamonjy et al., 2008; Sun & Ampornpunt, 2010), the convex optimization problem for the equivalent kernel matrix109may be transformed to the dual variables of {wβ1β2|β1β2=1 . . . m} to obtain
min ƒ(Z)(4)
z
subject to 0<∥Z∥*≤1, 0≤Z(Eq. 9)
where the function ƒ(Z) may be defined as:

The function ƒ(Z) as found in sub-embodiment (4a) must be differentiated by obtaining ∇ƒ(Z). The stationary point of the equivalent kernel matrix109of sub-embodiment (4a) may be denoted by α*. At the stationary point α*, the derivative of the target function with respect to the sub-embodiment (4a) parameterZmay be:

(Eq.⁢11)∂J⁡(Z_)∂zβ1⁢β2=⁢∂f⁡(α⁡(Z_)),A_⁢(Z))_∂zβ1⁢β2⁢❘α⁢(Z)_=α*=⁢-12⁢〈α*,∂A_∂zβ1⁢β2〉⁢α*=⁢-12⁢〈α*,K_β1⁢β2⁢α*〉.
More specifically, at the stationary point α*, it is possible to differentiate the function ƒ(α(Z),A(Z)) with respect to zβ1β2as if α is independent ofZ.

At step203, the NNR program101may initiate one or more iterative processes. At step204, each of the one or more iterative processes may include calculating an error112for the one or more coefficient matrices110of the equivalent kernel matrix109based on a training set. More specifically, the error to be calculated may be a separation measure of the training set and is a function of the one or more coefficient matrices110of the equivalent kernel matrix109. Furthermore, the function of the one or more coefficient matrices110of the equivalent kernel matrix109may be convex. The NNR program101may calculate an error112for the one or more coefficient matrices110of the equivalent kernel matrix109for one or more of the aforementioned embodiments of the invention. For example, the error112to be calculated may be a classification error or a regression error in accordance with the fourth embodiment (4) of the invention.

The NNR program101may calculate the error112through the use of an Artificial Intelligence (“AI”) machine, such as SVM software. For example, the NNR program101may use any standard SVM solvers or tools, such as a library for support vector machines (“LIBSVM”). A SVM is a form of computer software that consists of supervised learning, wherein supervised learning is the machine learning task of analyzing data and recognizing patters, used for classification and regression analysis. Given a training set, each marked for belonging to one of two categories, an SVM solver intelligently builds a model that assigns new examples into one category or the other. For example, the NNR program101may implement SVM software to calculate an error112for one or more new examples, such as the one or more coefficient matrices110of the equivalent kernel matrix109, based on a training set.

At step205, each of the one or more iterative processes may include initiating a line search for the one or more coefficient matrices110of the equivalent kernel matrix109. The line search may further include gradient descent. Here gradient-like steps are taken in theZspace. Since the optimal pointZ* is at the boundary, the line search may attempt to take a maximal step (s=1) towards the boundary. If this fails, the standard 1/m step size may be taken.

Referring to the aforementioned convex optimization problem for the equivalent kernel matrix109of the fourth embodiment (4), given a nuclear norm constrained task for a differentiable function ƒ(Z), the solution of

Here, l is the step size, while u and v are the vectors corresponding to the largest singular value of the ∇ƒ(Z) matrix. More specifically, if ∇ƒ(Z)=USVTand the diagonal elements ofSare in a decreasing order, then u (v) is the first column ofU(respectively,V). In particular, for a symmetric, positive definite matrix, both u and v are the corresponding eigenvectors of the largest eigenvalue of the ∇ƒ(Z) matrix.

Still referring to the fourth embodiment (4) of the invention, ∥Z∥*=1. SinceZis symmetric, by writingZin its spectral base,
ZΣiλiwiwiT,   (Eq. 13)
where wiis the eigenvector corresponding to the i-th nonzero eigenvalue λi,
Σλi=1.   (Eq. 14)
Specifically, the optimal stable solution is a fixed point of the gradient descent stepZ(n+1)←Z(n)(1−l)−luvT. The optimal pointZ* may be a rank one matrix. More specifically, there may be only a single non-zero eigenvalue, λ1=1 and w1=u. Here, it should be appreciated that the optimal point may be characterized by m parameters, which correspond to the entries of u, rather than m2parameters.

At step206, responsive to generating a result113, the one or more iterative processes may be terminated. The result113may be one or more optimal coefficient matrices for the equivalent kernel matrix109.

FIGS. 3-6depict the performances of single-kernel SVM and representative MKL classification methods on various data sets, including the classification method implementing the NNR program101. Here, the results for various classification methods as obtained in (Gönen & Alpaydin, 2011) have been reproduced, and the results from the classification method implementing the NNR program101have been added for comparison. The Test Accuracy column represents the accuracy of the results. The Support Vector column represents the percentage of data points that were used as support vectors. The Active Kernel column represents the sum of the number of kernels used in the solution. Lastly, the Calls to Solver column represents the number of calls to the internal support vector machine (SVM) solver. All values are accompanied by their corresponding standard deviations.

InFIGS. 3-5, 16 MKL classification methods and two SVM classification methods were compared. The SVM's were trained on each feature representation separately and the one with the highest average validation accuracy is reported (SVM (best)). The SMV's were also trained on the concatenation of all feature representations (SVM (all)). The following are explanations of the various types of classification methods found within the data sets:

RBMKL denotes rule-based MKL classification methods. RBMKL (mean) trains an SVM with the mean of the combined kernels. RBMKL (product) trains an SVM with the product of the combined kernels.

ABMKL denotes alignment-based MKL classification methods. ABMKL (ratio) is described in (Qiu et al. (2009)), ABMKL (conic) is the classification methods of (Lanckriet et al. (2004)), and ABMKL (convex) solves the quadratic programming problem posed in (He et al. (2008)).

CABMKL denotes centered-alignment-based MKL classification methods, and both variations, CABMKL (linear) and CABMKL (conic) are presented in (Cortes et al. (2010)). SimpleMKL is the iterative classification method of (Rakotomamonjy et al. (2008)). GLMKL denotes the group Lasso-based MKL classification methods proposed in (Xu et al. (2010)). GLMKL (p=1) learns a convex combination of kernels while GLMKL (p=2) updates the kernel weights setting and learns a conic combination of the kernels. NLMKL denotes the nonlinear MKL classification method of (Cortes et al. (2009)). NLMKL (p=1) and NLMKL (p=2) apply different constraints on the feasible set. LMKL denotes the localized MKL classification methods of (Gönen et al. (2008)), where the two variations LMKL (softmax) and LMKL (sigmoid) are described.

FIG. 3depicts the results of a Protein Folding classification task with respect to the aforementioned 16 MKL classification methods and 2 SVM classification methods. The initial Protein Folding prediction database consisted of 694 data points, partitioned to a trained set of 311 instances and a testing set of 383 instances. The goal in this classification task is to predict to which of the two major structural classes a given protein belongs to.

It should be appreciated that the classification method implementing the NNR program101outperforms all of the other MKL variations (85.2 Test Accuracy). Furthermore, a relatively low percentage of points were used as support vectors, less than half of the points used by the second-best classification method. Moreover, the classification method implementing the NNR program101was one of the fastest MKL classification methods in terms of the number of calls to the internal SVM solver.

FIG. 4depicts the results of an Internet Advertisement classification task with respect to the aforementioned 16 MKL classification methods and 2 SVM classification methods. The initial Internet Advertisement consisted of 3,279 labeled images. Additionally, the database included five different feature representations, each consisting of a different bag of words, with dimensions ranging from19to495. The goal in this classification task is to successfully identify whether a given image is an advertisement or not. It should be appreciated that the classification method implementing the NNR program101achieved superior performance over the aforementioned MKL variations. The fraction of data points used as support vector was extremely low, and was within less than a half standard deviation of the classification method with the lowest number of support vectors.

FIG. 5depicts the results of a few state-of-the-art Deep Neural Networks classification task. Here, classification was performed by extracting the features from the last fully connected layer, generating a linear kernel, and using an SVM classifier. The performance of the classification method implementing the NNR program101was tested on three kernels, corresponding to a set of three extracted features sets. It should be appreciated that the performance of the classification method implementing the NNR program101shows about a 4%-6% improvement over the classification results of a linear SVM classifier based on a single deep neural networks features.

Additionally, the performance of the classification method implementing the NNR program101was analyzed under noisy conditions. The networks CNN-M, CNN-M2048, and CNN-M4096 are minor variations of CNN-M128, and the latter's kernel was included in the kernel set of NuC-MKL (3) classification method. It should be appreciated that the performance of the classification method implementing the NNR program101does not deteriorate in the presence of redundant information. Thus, the classification method implementing the NNR program101is disinclined to overfitting in such scenarios.

FIG. 6is a block diagram depicting components of a computer600suitable for executing the NNR Program101.FIG. 6displays the computer600, the one or more processor(s)604(including one or more computer processors), the communications fabric602, the memory606, the RAM, the cache616, the persistent storage608, the communications unit610, the I/O interfaces612, the display620, and the external devices618. It should be appreciated thatFIG. 6provides only an illustration of one embodiment and does not imply any limitations with regard to the environments in which different embodiments may be implemented. Many modifications to the depicted environment may be made.

As depicted, the computer600operates over a communications fabric602, which provides communications between the cache616, the computer processor(s)604, the memory606, the persistent storage608, the communications unit610, and the input/output (I/O) interface(s)612. The communications fabric602may be implemented with any architecture suitable for passing data and/or control information between the processors604(e.g. microprocessors, communications processors, and network processors, etc.), the memory606, the external devices618, and any other hardware components within a system. For example, the communications fabric602may be implemented with one or more buses or a crossbar switch.

The memory606and persistent storage608are computer readable storage media. In the depicted embodiment, the memory606includes a random access memory (RAM). In general, the memory606may include any suitable volatile or non-volatile implementations of one or more computer readable storage media. The cache616is a fast memory that enhances the performance of computer processor(s)604by holding recently accessed data, and data near accessed data, from memory606.

Program instructions for the NNR program101may be stored in the persistent storage608or in memory606, or more generally, any computer readable storage media, for execution by one or more of the respective computer processors604via the cache616. The persistent storage608may include a magnetic hard disk drive. Alternatively, or in addition to a magnetic hard disk drive, the persistent storage608may include, a solid state hard disk drive, a semiconductor storage device, read-only memory (ROM), electronically erasable programmable read-only memory (EEPROM), flash memory, or any other computer readable storage media that is capable of storing program instructions or digital information.

The media used by the persistent storage608may also be removable. For example, a removable hard drive may be used for persistent storage608. Other examples include optical and magnetic disks, thumb drives, and smart cards that are inserted into a drive for transfer onto another computer readable storage medium that is also part of the persistent storage608.

The communications unit610, in these examples, provides for communications with other data processing systems or devices. In these examples, the communications unit610may include one or more network interface cards. The communications unit610may provide communications through the use of either or both physical and wireless communications links. The NNR program101may be downloaded to the persistent storage608through the communications unit610. In the context of some embodiments of the present invention, the source of the various input data may be physically remote to the computer600such that the input data may be received and the output similarly transmitted via the communications unit610.

The I/O interface(s)612allows for input and output of data with other devices that may operate in conjunction with the computer600. For example, the I/O interface612may provide a connection to the external devices618, which may include a keyboard, keypad, a touch screen, and/or some other suitable input devices. External devices618may also include portable computer readable storage media, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of the present invention may be stored on such portable computer readable storage media and may be loaded onto the persistent storage608via the I/O interface(s)612. The I/O interface(s)612may similarly connect to a display620. The display620provides a mechanism to display data to a user and may be, for example, a computer monitor.