RI: Small: Kernelization with Outer Product Instances

到目前为止，核方法主要应用于观测或实例是向量的情况。我们将核方法提升到矩阵域，其中实例是两个向量的外积。矩阵参数可以模拟组件之间的所有相互作用，因此考虑到二阶信息。我们发现，在矩阵设置一个更大的类的算法的基础上，任何谱不变的正则化可以内核化。因此，我们认为核化方法的影响在矩阵设置中会更大。特别地，我们将展示如何对乘法更新的矩阵版本进行核化。这个家族的动机是使用量子相对熵作为正则化。最重要的是，我们将使用在线学习的方法来证明乘法更新在特征维度上对数增长的泛化界。这很重要，因为它允许我们使用高维特征空间。我们将把我们的方法应用于协同过滤。在这种情况下，实例由两个向量定义，一个描述用户，另一个描述对象。这些向量对的外积成为机器学习算法的输入实例。当存在一个低秩矩阵可以准确解释实例的偏好标签时，乘法更新非常适合学习。核方法极大地增强了方法的适用性，因为现在我们可以将用户和对象向量扩展为高维特征向量，并且仍然获得有效的算法。

Thus far kernel methods have been mainly applied in cases where observations or instances are vectors. We are lifting 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 kernelized. 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. 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.