General Functional Matrix Factorization Using Gradient Boosting
Abstract
Matrix factorization is among the most successful techniques for collaborative filtering. One challenge of collaborative filtering is how to utilize available auxiliary information to improve prediction accuracy. In this paper, we study the problem of utilizing auxiliary information as features of factorization and propose formalizing the problem as general functional matrix factorization, whose model includes conventional matrix factorization models as its special cases. Moreover, we propose a gradient boosting based algorithm to efficiently solve the optimization problem. Finally, we give two specific algorithms for efficient feature function construction for two specific tasks. Our method can construct more suitable feature functions by searching in an infinite functional space based on training data and thus can yield better prediction accuracy. The experimental results demonstrate that the proposed method outperforms the baseline methods on three realworld datasets.
- Introduction
Matrix factorization has been proved to be one of the most successful approaches to collaborative filtering. It assumes that the usersrsquo; preference matrix Y isin; R ntimes;m can be factorized into a product of two low rank matrices U isin; R dtimes;n and V isin; R dtimes;m as Ycirc; (i, j) = UT i Vj , and conducts collaborative filtering by exploiting U and V. In real world scenarios, many types of auxiliary information are available besides the matrix Y, and the use of them may enhance the prediction accuracy. For example, information such as time and location can help better predict usersrsquo; preferences based on the contexts, while information such as usersrsquo; ages and gender can help make better prediction on the basis of user profiles. From the viewpoint of learning, the use of auxiliary information can overcome the sparsity of the matrix data. The use of auxiliary information in matrix factorization has been studied, various models (Agarwal amp; Chen, 2009; Rendle et al., 2011; Weston et al., 2012) have been proposed. In these models, auxiliary information is encoded as features and factorization of the matrix amounts to linearly mapping the feature vectors in the feature space into a latent space. The key question here is how to encode useful features to enhance the performance of the model. Ideally one would like to automatically construct “good” feature functions in the learning process. To the best of our knowledge, little work has been done on automatic feature function construction in matrix factorization. In this paper, we try to tackle the challenge by employing general functional matrix factorization and gradient boosting. In our method, feature functions are automatically constructed via searching in a functional space during the process of learning. The learning task is effectively and efficiently carried out with the gradient boosting algorithm. The contribution of the paper is as follows. (1) We proposea general formalization of functional matrix factorization. (2) We introduce an efficient algorithm to solve the optimization problem using gradient boosting. (3) We give two specific feature construction algorithms using time and demographic information. (4) We empirically demonstrate the effectiveness of the proposed method on three real-world datasets. The rest of the paper is organized as follows. Section 2 gives the general description of our model. Section 3 describes two specific algorithms for feature function construction. Experimental result is provided in Section 4. Related work is introduced in Section 5. Finally, the paper is concluded in Section 6.
-
General Functional Matrix Factorization
- Model
Matrix factorization with auxiliary information can be represented by the following equation, where the auxiliary information is denoted as x.
Note that for simplicity we always assume that there is an extra constant column in both U and V to model the bias effect. Further generalization can be considered, which involves the sum of multiple factorizations. To simplify the discussion, we restrict our model to a single factorization. The latent factor model in Equation (1) assumes that prediction Ycirc; is a function of user i, item j and auxiliary information x in the current context. The matrix U is constructed by linear combination of features. The kth dimension of U is calculated by the following equation1
)
The matrix V can be formalized similarly, while in many applications it seems to be sufficient to define one of them in a functional form (either U or V). F is the set of candidate feature functions (space of functions) which is closed under scaling and can be infinite. The novelty of our model lies in that it introduces functions as model parameters, which allows us to construct “good” feature functions fk,s isin; F in learning of the latent factor model. To simplify the notations, we will also use Ycirc; ij for Ycirc; (i, j, x), Uki for Uk(i, x), and Vkj for Vk(j, x). One very important factor in our method is the definition of the functional space F. As shown in Fig. 1, we will give two examples of feature functions. The first one is a user-specific k-piece step function that captures usersrsquo; interest change over time; the second one is a user-independent decision tree to model users with their properties. The details will be introduced in Section 3.
Relationship with Existing Models
General functional matrix factorization contains existing models as its special cases in which certain constraints are imposed on the model. The model degenerates to the conventional factorization models using auxiliary information, when the feature functions fk,s are predefined and fixed. The model becomes that of functional matrix factorization in (Zhou et al., 2011), when the feature functions in all the la
使用梯度增强的一般功能矩阵分解
摘要
矩阵分解是最成功的协同过滤技术之一。协同过滤的一个挑战是如何利用可用的辅助信息来提高预测准确性。在本文中，我们研究了利用辅助信息作为因子分解特征的问题，并提出将问题形式化为一般功能矩阵分解，其模型包括传统的矩阵分解模型作为其特殊情况。此外，我们提出了一种基于梯度增强的算法来有效地解决优化问题。最后，我们给出了两个特定算法，用于两个特定任务的高效特征函数构造。我们的方法可以通过在训练数据的基础上搜索无限功能空间来构造更合适的特征函数，从而可以产生更好的预测精度。实验结果表明，该方法优于三个真实世界数据集的基线方法。
1.简介
矩阵分解已被证明是协作过滤最成功的方法之一。假设用户的偏好矩阵Yisin;Rntimes;m可以被分解为两个低秩矩阵Uisin;Rdtimes;n和Visin;Rdtimes;m的乘积，作为Y（i，j）= UT i Vj，通过利用U和V进行协同过滤。在现实世界场景中，除了矩阵Y之外还有许多类型的辅助信息，并且使用它们可以提高预测精度。例如，诸如时间和位置之类的信息可以帮助更好地基于上下文预测用户的偏好，而诸如用户的年龄和性别之类的信息可以帮助基于用户简档进行更好的预测。从学习的角度来看，辅助信息的使用可以克服矩阵数据的稀疏性。已经研究了在矩阵分解中使用辅助信息，已经提出了各种模型（Agarwal和Chen，2009; Rendle等，2011; Weston等，2012）。在这些模型中，辅助信息被编码为特征，并且矩阵的因子分解量将特征空间中的特征向量线性映射到潜在空间中。这里的关键问题是如何编码有用的功能以增强模型的性能。理想情况下，人们希望在学习过程中自动构建“好”特征函数。据我们所知，在矩阵分解中对自动特征函数构造的工作很少。在本文中，我们尝试通过采用通用功能矩阵分解和梯度增强来应对挑战。在我们的方法中，通过在学习过程中在功能空间中搜索来自动构建特征函数。使用梯度增强算法有效且高效地执行学习任务。该论文的贡献如下。 （1）我们提出了功能矩阵分解的一般形式化。 （2）我们引入了一种有效的算法来解决使用梯度增强的优化问题。 （3）我们使用时间和人口统计信息给出两个特定的特征构造算法。 （4）我们凭经验证明了所提方法对三个真实世界数据集的有效性。本文的其余部分安排如下。第2节给出了我们模型的一般描述。第3节描述了两种特征函数构造的特定算法。实验结果在第4节中提供。相关工作在第5节中介绍。最后，本文在第6节中总结。
2.一般功能矩阵分解
2.1模型
具有辅助信息的矩阵分解可以由以下等式表示，其中辅助信息表示为x。
注意，为简单起见，我们总是假设在U和V中都有一个额外的常数列来模拟偏置效应。 可以考虑进一步的概括，其涉及多个因子分解的总和。 为了简化讨论，我们将模型限制为单个分解。 等式（1）中的潜在因子模型假设预测Y是当前上下文中的用户i，项j和辅助信息x的函数。 矩阵U由特征的线性组合构成。 U的第k维通过以下等式1计算
矩阵V可以类似地形式化，而在许多应用中，似乎足以以函数形式（U或V）定义它们中的一个。 F是候选特征函数集（函数空间），在缩放时关闭并且可以是无限的。 我们模型的新颖之处在于它引入了函数作为模型参数，这使我们能够在学习潜在因子模型时构造“好的”特征函数fk，sisin;F。 为了简化符号，我们还将Y i用于Y（i，j，x），Uki用于Uk（i，x），Vkj用于Vk（j，x）。 我们方法中一个非常重要的因素是功能空间F的定义。如图1所示，我们将给出两个特征函数的例子。 第一个是用户特定的k-piece步骤函数，用于捕获用户随时间变化的兴趣; 第二个是与用户无关的决策树，用于为用户建立其属性。 详情将在第3节中介绍。
与现有模型的关系
一般功能矩阵分解包含现有模型作为其特殊情况，其中对模型施加某些约束。当特征函数fk，s被预定义和固定时，该模型使用辅助信息退化为传统的因子分解模型。当假设所有潜在维度中的特征函数是相同的决策树时，该模型成为（Zhou等人，2011）中的函数矩阵分解的模型。
2.2。训练
我们方法的目标函数在下面的等式中定义
其中l是可微的凸损失函数，其测量预测Y和目标Y之间的差异，并且总和超过所有观察到的条目。第二项Omega;测量模型的复杂性（即，特征函数）以避免过度拟合。利用目标函数，将选择使用简单且有用的特征函数的模型作为最佳模型。由于模型包含函数作为参数，我们不能直接使用传统方法，如随机梯度下降来找到解。我们建议利用梯度增强来应对挑战。更具体地说，我们加法地构造潜在维度：在每个步骤中，我们选择潜在维度k并尝试向维度添加新的特征函数f。在该步骤期间，执行在功能空间F上的搜索以找到优化目标函数的特征函数f。对于一般凸损失函数l，f的搜索可能很难。我们通过使用二次损失函数来近似它来简化搜索目标。我们定义
假设我们在修复其余参数的同时向Uk（i，x）添加新特征f（i，x）。目标函数的第一部分可以通过泰勒展开近似为
我们使用L~（f） Omega;（f）来找到最佳特征函数f。 一般程序在算法1中示出，其中Sigma;是收缩参数以避免过度拟合。
训练的拟合
hij的选择不一定要求利用二阶梯度来近似损失函数。 只要以下不等式成为证明，算法就会收敛。
将上界表示为L~（Sigma;f），我们得到L（Sigma;f*） Omega;（Sigma;f*）le;L~（Sigma;f*） Omega;（Sigma;f*）le;L~（0） Omega;（0）= L（0）。 这里我们假设0isin;F且Omega;（0）= 0.因此，目标函数在每一步都减小。
时间复杂性
如果我们缓冲训练数据中观察到的对的预测，则计算一般算法中的充分统计量的时间复杂度是O（kN），其中N表示矩阵中观察到的对的数量。此外，训练算法的时间复杂度取决于特征函数学习的具体设置。我们将在第3节中提供特定学习算法的时间复杂度，这是对数线性顺序。
与现有方法集成
训练算法是一种迭代优化程序，如坐标下降。这使我们可以轻松地将我们的方法与现有的学习潜在因子模型的方法相结合：使用我们的更新算法进行特征函数构造，并使用随机梯度下降或坐标下降来优化模型的其他部分。
2.3sgmentation功能学习
训练算法的一个重要部分是在每个步骤中学习特征函数f。在本节中，我们将考虑学习一类特征函数的一般方法。它首先使用辅助信息将数据分成几个部分，然后在每个分段中学习一个独立的参数
函数p（i，x）定义实例的聚类索引，并且权重beta;被分配给每个聚类。作为sume，有| C |簇和每个簇的实例集定义为Ic = {（i，j，x）| p（i，x）= c}。特征函数的复杂性定义为
第一项代表段数;第二项代表每个集群中权重的范数。对于该问题，可以如下针对给定分割来分析地找到最佳beta;
当二阶项很小时，该值主要由lambda;确定。将beta;*置于L~（f），得到目标函数
我们可以使用等式（10）来指导搜索分割函数。分段功能的基本动机是使相同段中的数据的潜在维度尽可能相似。最广泛使用的分割函数之一是决策树（Friedman等，2001）。但是，对于特定类型的分段函数，我们可以使用特定算法而不是决策树。我们将使用本节中的一般方法来指导第3节中的特征函数构造。
3.特定功能
3.1。 时间相关的特征函数
时间是协同过滤中非常重要的辅助信息。 一个重要原因是用户的偏好随时间而变化。 为了模拟用户的本地偏好，遵循（Koren，2009）中的方法，我们可以为每个本地化时间仓定义一个指标函数作为特征函数; 该模型可以写成
我们的想法是在每个中学习一个局部潜在因素时间仓来捕捉时间依赖的偏好用户。 时间仓大小是固定的，需要预定义。 在现实世界场景中，不同的用户可能会有不同的偏好进化模式。 一些用户可能经常改变他们的兴趣，而其他人可能愿意坚持自己的兴趣。 不同主题的变化模式也可能不同; 一个用户可能会长时间不断喜欢古典音乐，同时经常改变她对流行音乐的偏好。 使用固定大小的时间箱可能难以捕获这些模式。 我们可以利用我们的模型来学习更多灵活的特征函数。 具体来说，我们将用户潜在因素定义为
其中每个fk，s，i（t）是用户特定的| C | -piece步骤功能在t中按时间分段定义。 图2给出了该模型的图示。 请注意时间bin指示器功能也可以视为特殊功能我们的时间特征函数的类型。 区别是我们的方法决定段的数量，基于训练改变点和功能值数据，提供更多的灵活性。 使用结果在2.3节中，发现时间分割的目标可以写成如下
可以使用二次时间复杂度中的动态编程算法找到目标的最优解。 我们使用更快的贪婪算法; 它从所有实例开始作为独立的段，然后在可以改进目标函数时贪婪地将段组合在一起直到达到局部最小值。
时间复杂性
设mi为第i行中观察到的条目数。 用户i的贪婪算法的时间复杂度是O（mi log mi），其中对数比例因子来自维护优先级队列的成本。 对数据集进行一次迭代的总体训练复杂度为O（kN log m）。 至于空间复杂度，可以将两步函数的加法组合成单步函数，这允许我们有效地存储Uk（i，t）并且不需要为每个实例缓冲U.
3.2。 人口特征功能
数据稀疏性是协作过滤的主要挑战。 对于处理系统中可能只有少量甚至没有记录的新用户来说，问题变得尤为严重。 可用于处理该问题的一种重要类型的辅助信息是用户人口统计数据，例如年龄，性别和职业。 该信息可以相对容易地获得并且具有对用户偏好的强烈指示。 例如，一个小男孩更倾向于喜欢动画，而计算机科学的学生可能对IT新闻感兴趣。 为了从潜在因子模型构建的用户人口统计数据中学习有用的特征函数，我们使用x来表示人口统计信息，并将潜在因素定义为
其中每个fk，s（x）是一个与用户无关的特征函数。我们将特征函数集F定义为用户属性x上的回归树集。图3给出了模型的直观解释。我们在叶节点中放置用于说明树结构的示例值，而在真实特征树中，它们使用等式（9）计算。使用树作为要素的优点是可以选择有用的属性，创建属性的高阶组合，并自动分割连续属性以构建有意义的特征。接下来，我们描述树学习算法。树结构也使用2.3节中的公式（10）进行引导。在每一轮中，我们贪婪地枚举属性并选择对可以最大程度地减少损失的属性进行拆分。重复该过程直到满足一些停止条件（例如最大深度），然后执行修剪过程以合并节点，减少损失。我们在这里可能面临的一个问题是缺失值的存在。也就是说，并非所有属性都可用于每个用户。为解决此问题，我们为每个节点确定默认方向（左子节点或右子节点），并在遇到缺失值时采用默认方向进行分类。拆分构造算法还列举了默认方向以找到最佳拆分.
3.3。 我们方法的优势
接下来，我们将讨论为什么我们的方法可以提高预测准确性。 如前所述，用户偏好模式是动态的并且难以捕获。 图4说明了我们的特征构造方法。 在时间依赖的情况下，不同的用户可能具有不同的兴趣改变模式。 我们的方法可以有效地检测沿时间轴的某些主题的感兴趣的动态变化。 当用户偏好没有发生变化时，我们方法中的正则化也将导致选择简单模型。 在用户人口统计的情况下，我们的方法可以自动创建高阶特征并构建基于树的复杂特征函数。 优化的目标是找到简单且适合数据的特征函数; 自动构建高阶特征并自动检测变化点使这成为可能，并为我们的模型提供实现更好结果的潜力。
- 实验
4.1.数据集和设置
我们在实验中使用了三个真实数据集。表1总结了数据集的统计数据。第一个数据集是Movielens数据集ml-1M，其中包含6,040个具有时间戳的用户的3,952部电影的约100万个评级。我们使用五重交叉验证来评估我们的方法和基线方法的性能。第二个数据集是Yahoo! Music Track1数据集4，其中包含来自雅虎的624,000首歌曲的100万用户的2.53亿个评分。音乐网站。数据按时间分为训练，验证和测试集。我们使用官方培训和验证数据集来训练模型和测试集以进行评估。对于这两个数据集，我们使用RMSE（均方根误差）作为评估度量。前两个数据集用于评估我们的方法的性能与时间相关的特征函数构造。我们使用的第三个数据集是腾讯微博5。它是中国最大的Twitter类社交媒体服务之一。该数据集包含大约两个月的230万用户的推荐记录。该项目集被定义为腾讯微博的名人和信息来源。数据集按时间分为训练和测试数据。此外，测试集分为公共和私人集合，用于独立评估。我们使用训练集来训练模型并使用公共测试集进行评估。我们还按时间从训练数据中分离1/5数据以进行参数选择。数据集非常稀疏，每个用户平均只有两个正记录。此外，测试集中约70％的用户从未出现在训练集中。用户人口统计信息（年龄和性别）和社交网络信息在数据集中可用。对于此数据集，我们使用MAP @ k（平均精度）作为评估度量。利用数据集来评估我们的方法与人口统计特征构造的性能。在所有实验中，我们模型的参数lambda;启发式设置为2.我们使用验证集（在ml1M中通过交叉验证）来调整基线模型和模型的元参数。
4.2。关于Movielen的结果
我们比较了ml-1M数据集上的六种方法。比较方法如下：
bull;MF是不使用辅助信息的基本矩阵分解模型。
bull;TimeMF使用预定义的时间段来模拟用户随时间变化的偏好变化。时间仓的大小通过交叉验证进行调整。 bull;GFMF是我们学习时间相关特征函数的模型。
bull;SVD 是具有隐式反馈信息的矩阵分解模型（Koren，2008）。
bull;TimeSVD 使用与TimeMF相同的时间特征功能，它还使用隐
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
