A PROJECT SUMMARY

There has been a recent revolution in machine learning based on the following simple idea. Instead of using for example a complicated neural net as your hy-potheses class, map the instances into a high dimensional feature space and learn with linear models in that feature space. Provided that the dot products in the feature space can be computed efficiently via the use of a kernel function and the algorithm’s linear weight vector is a linear combination of the expanded in-stances, then the resulting algorithms are efficient. To apply the algorithms to a specific problem domain, it then suffices to design a suitable kernel function for that domain. Intellectual merit: So far the kernel methods have been mainly applied to the case when the instances are vectors. We will lift kernel methods to the matrix domain, where the instances are outer products of two vectors. Matrix parameters can model all interactions between components and therefore take second order information into account. We discovered that in the matrix setting a much larger class of algorithms based on any spectrally invariant regularization can be kernel-ized. Therefore we believe that the impact of the kernelization method will be even greater in the matrix setting. In particular we will show how to kernelize the matrix versions of the multiplicative updates. This family is motivated by using the quantum relative entropy as a regularization. Most importantly we will use methods from on-line learning to prove generalization bounds for multiplicative updates that grow logarithmic in the feature dimension. This is important because it lets us use high dimensional feature spaces. Broader impact: We will apply our methods to collaborative filtering. In this case an instance is defined by two vectors, one describing a user and another describing an object. The outer products of such pairs of vectors become the input instances to the machine learning algorithms. The multiplicative updates are ideally suited to learn well when there is a low-rank matrix that can accurately explain the preference labels of the instances. The kernel method greatly enhances the applicability of the method because now we can expand the user and object vectors to high-dimensional feature vectors and still obtain efficient algorithms