RI: Small: Kernelization with Outer Product Instances

RI：小：使用外部产品实例进行内核化

• 批准号: 0917397
• 负责人: Manfred Warmuth
• 金额: $ 45.5万
• 依托单位: University of California-Santa Cruz
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2014-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0917397&HistoricalAwards=false
• 关键词: RI; Small; Kernelization; Outer; Product

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.

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