在线紧凑凸化因子分解机：一种优于传统方法的在线学习算法

Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16330在线紧凑凸化因子分解机0清华大学 张文鹏†0清华大学 Min Zhang ‡0清华大学0清华大学 裴健 京东方和西南大学 赵培林 南方科技大学0Junzhou Huang腾讯AI实验室0摘要0因子分解机（FM）是一种具有强大特征工程能力的监督学习方法。它在各种批量学习任务中取得了最先进的性能，其中所有训练数据在训练之前都是可用的。然而，在实际应用中，数据以流式方式顺序到达时，使用批量学习算法进行重新训练的高成本在在线学习场景中带来了巨大的挑战。最初的挑战是，没有先前的FM公式可以直接满足在线凸优化（OCO）的要求-这是在线学习算法设计的重要框架。为了解决这个挑战，我们发明了一种新的凸化方案，导致了一个紧凑的凸化FM（CCFM），它无缝地满足OCO中的要求。然而，在在线学习设置中学习紧凑的凸化FM（CCFM），大多数现有算法都面临着昂贵的投影操作。为了解决这个后续挑战，我们遵循在线条件梯度的通用无投影算法框架，并提出了一种在线紧凑凸化因子分解机（OCCFM）算法，它通过高效的线性优化步骤避免了投影操作。为了支持所提出的OCCFM在其理论基础方面的性能，我们证明了该算法实现了亚线性的遗憾界限。为了评估OCCFM的实证性能，我们对6个实际数据集进行了广泛的在线回归和在线分类任务的实验。实验结果表明，OCCFM在FM的在线学习方法中表现优于最先进的方法。0ACM参考格式：Xiao Lin，Wenpeng Zhang，Min Zhang，WenwuZhu，Jian Pei，Peilin Zhao和JunzhouHuang。2018年。在线紧凑凸化因子分解机。在WWW2018：2018年网络会议，2018年4月23日至27日，里昂。0� 相等贡献，jackielinxiao@gmail.com†相等贡献，通讯作者，zhangwenpeng0@gmail.com‡通讯作者，z-m@tsinghua.edu.cn§ 通讯作者，wwzhu@tsinghua.edu.cn0本文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW2018，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据创作共用CC BY 4.0许可证发布。ACM ISBN978-1-4503-5639-8 / 18 / 04。https://doi.org/10.1145/3178876.31860750法国。ACM，纽约，纽约，美国，10页。https://doi.org/10.1145/3178876.318607501 引言0因子分解机（FM）[23]是一种用于监督学习的通用方法。它提供了一种有效的特征工程机制，以分解形式的低秩矩阵捕捉每个输入特征的一阶信息以及二阶成对特征交互。FM在各种应用中取得了最先进的性能，包括推荐[22,24]，计算广告[17]，搜索排名[20]和毒物基因组预测[33]等。因此，由于在工业应用和数据科学竞赛[17,38]中越来越受欢迎，FM最近重新引起了研究人员的重视[4,5,18,31]。尽管对因子分解机的研究非常多，但大多数现有研究都是在批量学习设置中进行的，其中所有训练数据在训练之前都是可用的。然而，在许多实际场景中，如在线推荐和在线广告[21,29]，训练数据以流式方式顺序到达。如果按照这些场景中的流进行批量学习算法，则每次有新数据到达时都必须重新训练模型。由于这些数据流通常以大规模方式到达，并且以实时方式不断变化，因此由此产生的高成本使得批量学习算法在此类设置中不切实际。这为因子分解机的高效在线学习算法创造了迫切需求。此外，期望在线学习算法在性能方面具有理论保证。在本文中，我们旨在基于在线学习设置中的重要框架-在线凸优化（OCO）[12,26]开发一种理想算法。不幸的是，现有的公式不能直接满足OCO中提出的两个基本要求：（i）所有参数的任何实例都应表示为凸紧致决策集合中的单个点；以及（ii）预测引起的损失应该在决策集合上以凸函数的形式表示。实际上，在大多数现有的FM公式[4,8,17,20,23]中，损失函数对于分解特征交互矩阵是非凸的，从而违反了要求（ii）。此外，尽管一些研究提出了凸FM的公式，但是...(V V T )ijxixj,Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16340纠正非凸性问题[3,33]，他们仍然将特征权重向量和特征交互矩阵视为分离的参数，从而违反了OCO中的要求（i）。为了解决这些问题，我们提出了一种新的FM凸化方案。具体而言，我们将全局偏差、特征权重向量和特征交互矩阵重写为紧凑的增广对称矩阵，并通过核范数约束限制增广矩阵，核范数约束是低秩约束的凸代理[6]。因此，增广矩阵形成了一个凸紧凑的决策集，本质上是一个对称有界核范数球。然后，我们将FM的预测重写为相对于增广矩阵的凸线性函数，因此预测所产生的损失是凸的。基于凸化方案，紧凑凸化FM（CCFM）的结果公式可以无缝地满足OCO框架的上述要求。然而，当我们在OCO框架内研究紧凑凸化分解机的各种在线学习算法时，我们发现大多数现有的在线学习算法在每次迭代中都涉及到投影步骤。当决策集是有界核范数球时，投影等同于计算代价高昂的奇异值分解（SVD），从而限制了大多数在线学习算法的适用性。值得注意的是，一个例外的算法是在线条件梯度（OCG），它通过线性优化步骤避免了投影操作。当OCG应用于核范数球时，线性优化等同于计算矩阵的最大奇异向量，这要简单得多。然而，目前尚不清楚是否存在类似于OCG的算法适用于有界核范数球的特定子集。为此，我们提出了一种CCFM的在线学习算法，命名为在线紧凑凸化分解机（OCCFM）。我们证明，当决策集是对称核范数球时，OCG类似算法所需的线性优化仍然存在，即它等同于计算特定对称矩阵的最大奇异向量。基于这一发现，我们为OCCFM提出了一种类似于OCG的在线学习算法。由于OCCFM是OCG的一种变体，我们证明了OCG的理论分析仍适用于OCCFM，它在O(T^3/4)的次线性遗憾界中取得了成果。此外，我们对真实世界数据集进行了大量实验，以评估OCCFM的实证性能。正如在线回归和在线分类任务的实验结果所示，OCCFM在效率和预测准确性方面优于最先进的在线学习算法。本文的贡献总结如下：0(1)根据我们的了解，我们是第一个提出具有理论保证的在线紧凑凸化分解机（Online Compact Convexified FactorizationMachine，CCFM）的人，这是在线学习环境中FM的一种新变体。（2）CCFM的提出公式优于先前的研究，因为它可以无缝地适应在线凸优化的重要框架。此外，这个公式不仅可以在在线环境中使用，还可以在批处理和随机环境中使用。0(3)我们提出了一种基于在线条件梯度算法的CCFM决策集上的线性优化例程，从而得到了一种类似于OCG的在线学习算法，命名为OCCFM。此外，这一发现也适用于任何其他决策集为对称有界核范数球的在线学习任务。（4）我们评估了所提出的OCCFM在在线回归和在线分类任务上的性能，结果显示OCCFM在效率和预测准确性方面优于最先进的在线学习算法。0我们相信我们的工作对因子分解机研究有所启发，特别是对于在线因子分解机。由于FM的广泛应用，我们的工作在理论和实践上都具有重要意义。02 预备知识0在本节中，我们首先详细回顾因子分解机的更多细节，然后介绍在线凸优化框架和在线条件梯度算法，这两者都被我们用来设计因子分解机的在线学习算法。02.1 因子分解机0因子分解机（FM）[23]是一种通用的监督学习方法，适用于任何实值特征向量。FM最重要的特点是强大的特征工程能力。除了每个输入特征的通常一阶信息外，它还捕捉建模中的二阶特征对交互，这导致比线性模型更强的表达能力。给定输入特征向量x∈Rd，vanillaFM使用以下公式进行预测ˆy∈R：0ˆy ( x ,  ω 0 ,  ω ,  V  )  =  ω 0  +  ω T x  +0d0d0其中ω0∈R是偏置项，ω∈Rd是一阶特征权重向量，V∈Rd×k是二阶分解特征交互矩阵；(VV T)ij是矩阵VVT中第i行第j列的元素，k�d是决定V的秩的超参数。如前研究所示[3,33]，ˆy对V是非凸的。FM中的非凸性会导致一些实践中的问题，如局部最小值和收敛不稳定性。为了克服这些问题，已经提出了两种凸FM的公式[3,33]，其中特征交互直接建模为Z∈Rd×d，而不是分解形式中的VVT，这导致了非凸性。然后对矩阵Z施加有界核范数约束以保持低秩性质。总的来说，凸FM允许更一般的特征交互建模，并且在实践中非常有效。两种公式之间的区别在于是否在预测中使用Z的对角线元素。为了清楚起见，我们将[3]中的公式称为凸FM（1），将[33]中的公式称为凸FM（2）。请注意，我们在这项工作中提出了一种新的FM凸化方案，与上述两种凸FM的公式本质上不同。我们的凸化细节ft (xt ) − minx ∗∈Qft (x ∗)is sub-linear inT, i.e. lim1 regretT = 0. The sub-linearity implies2Track: Web Search and MiningWWW 2018, April 23-27, 2018, Lyon, France16350在第3.1节中将介绍该方案及其与凸FMs的比较。02.2 在线凸优化 在线凸优化（OCO）[12,26]是设计在线学习算法的重要框架。它可以看作是学习器和对手之间的结构化重复博弈。在每一轮t∈{1, 2, ...,T}中，学习器需要从凸紧致集合Q�Rn中生成一个决策点xt。然后对手用凸损失函数ft：Q→R回应学习器的决策，学习器遭受损失ft(xt)。学习器的目标是生成一系列决策{x1, x2, ...,XT}，使得相对于事后最佳固定决策的遗憾0遗憾T =0T0T0当T足够大时，学习器可以和最佳固定决策一样表现出色。基于OCO框架，已经提出了许多在线学习算法，并成功应用于各种应用[10,14,36]。其中最受欢迎的代表是在线梯度下降（OGD）[39]和Follow-The-Regularized-Leader（FTRL）[21]。02.3 在线条件梯度0在线条件梯度（OCG）[12]是一种无投影的在线学习算法，它避免了其对应算法（包括OGD和FTRL）中可能需要的计算昂贵的投影操作，在处理有界核范数球决策集时具有很大的计算优势。正如将在第3节中展示的那样，我们在提出的凸化方案中使用了类似的决策集，因此我们将OCG作为我们算法设计的基石。在接下来的内容中，我们将介绍更多细节。在实践中，为了确保新生成的决策点位于感兴趣的决策集内，大多数在线学习算法在每次迭代中都会调用投影操作。例如，在OGD中，当梯度下降步骤生成一个不可行的迭代点位于决策集之外时，我们必须将其投影回来以恢复可行性。一般来说，这种投影相当于在决策集上求解一个二次凸规划问题，不会引起太多问题。然而，当决策集是特定类型时，例如有界核范数球、所有半正定矩阵和多面体[12,13]，它就会变成非常昂贵的代数运算。为了避免这些昂贵的操作，提出了无投影的在线学习算法OCG。它更加高效，因为它在每次迭代中使用线性优化步骤而不是投影操作。例如，当决策集是有界核范数球时，其他在线学习算法中所需的投影操作相当于计算矩阵的完全奇异值分解（SVD），而OCG中的线性优化步骤只需要计算最大奇异向量，简单程度至少高出一个数量级。最近，在[35]中提出了OCG算法的分散分布式变体。0算法1 在线条件梯度（OCG）0输入：凸集Q，最大轮数T，参数η和{γt}101：初始化x1∈Q 2：对于t=1,2,...,T执行以下操作3：播放xt并观察ft4：令Ft(x)=η∑t−1τ=1��fτ(Cτ),x�+∥x−x1∥225：计算vt=argminx∈Q�x,�Ft(xt)�6：设置xt+1=(1−γt)xt+γtvt 7：结束循环0它允许高效处理大规模机器学习问题。03 在线紧凸化因子分解机0在本节中，我们转向我们的在线紧凸化因子分解机的开发。如前所述，OCO是设计在线学习算法的最重要的框架。它有两个基本要求：（i）所有模型参数的任何实例都应表示为凸紧凸决策集中的单个点；（ii）预测产生的损失应该被构造为决策集上的凸函数。由于以下两个原因，普通FM不能直接适应OCO框架。首先，普通FM包含无约束特征权重向量ω（ω0可以写成ω）和因子化特征交互矩阵V；它们是分离的组件，不能被构造为决策集中的单个点，因此很难直接适应OCO框架。其次，由于普通FM中的预测ˆy相对于V是非凸的[3,32]，当我们将其插入到每一轮t的损失函数ft中时，由预测产生的损失也是相对于V非凸的。虽然一些先前的研究提出了两种凸FM的形式，但它们也不能直接适应OCO框架。与普通FM类似，这两种凸形式将无约束特征权重向量ω和特征交互矩阵Z视为分离的组件，违反了要求（i）。为了满足OCO框架的要求，我们首先发明了一种新的FM凸化方案，得到了一种称为紧凸化FM（CCFM）的公式。然后基于新的公式，我们设计了一种在线学习算法 -在线紧凸化因子分解机（OCCFM），它是OCG算法的一种新变体，专为我们的设置量身定制。03.1 紧凑的凸化因子机0我们提出的凸化方案的主要思想是将所有参数，包括偏置项、一阶特征权重向量和二阶特征交互矩阵，放入一个单独的增广矩阵中，并强制使其具有低秩性。由于低秩性不是一个凸约束，我们用有界核范数约束来近似它，这是机器学习社区中的常见做法 [3, 13,26]。方案的详细信息如下所示。0通常将  γ t  设置为 1C =ZωωT2ω0K = {C |C =ZωωT2ω0αC1 + (1 − α )C2 = αωT12ω0+ (1 − α )ωT22ω0=� ZαωαωTα2ω0, C trδ, Z1Tˆy(C ) = 1 ˆx T C ˆx = ω0 + ωT x + 1x T Z x ., ∥C∥tr ≤ δ, Z ∈Sd×d, ω ∈ Rd, ω0 ∈ R}.ˆy(C ) = д(Z ) + h(ω) + ω0,ˆy(αC1 + (1α )C2) = д(αZ1 + (1α )Z2) + h(αω1 + (1α )ω2) + ω0.д(αZ1 + (1 − α )Z2) + h(αω1 + (1 − α )ω2) + ω0= αд(Z1) + (1 − α )д(Z2) + αh(ω1) + (1 − α )h(ω2) + ω0= α (д(Z1) + h(ω1) + ω0) + (1α )(д(Z2) + h(ω2) + ω0).α (д(Z1)+h(ω1)+ω0)+(1 α )(д(Z2)+h(ω2)+ω0) = α ˆy(C1)+(1 α ) ˆy(C2).16360回顾一下在传统的FM中， ω 0 ， ω 和 V分别被称为偏置项、线性特征权重向量和二阶特征交互矩阵。由于预测值  ˆ y 相对于 V 的非凸性，我们采用一个对称矩阵  Z  ∈ R d × d来建模特征之间的成对交互，这是设计FM的凸变体中的一种常见做法 [3, 33]。然后我们将偏置项  ω 0 ，一阶特征权重向量  ω和二阶特征交互矩阵  Z 重新写成一个紧凑的增广矩阵  C ：0�，0其中  Z  =  Z T ∈  R d × d ，  ω  ∈  R d ，  ω 0  ∈  R。为了实现一个复杂度较低的模型，我们限制增广矩阵  C的秩较低。然而，对矩阵秩的约束是非凸的，不符合OCO框架。矩阵  C 秩的一个典型近似是其核范数  ∥ C ∥ tr  [6]：  ∥ C ∥ tr  =  tr( �0C T C )  = � d i = 1 σ i ，其中 σ i  是矩阵 C 的第 i个奇异值。由于奇异值非负，核范数本质上是矩阵秩的一个凸代理[3, 13, 26]。因此，通常会使用一个将秩约束替换为有界核范数  ∥ C∥ tr  ≤  δ 的松弛方法。将 S 定义为对称矩阵的集合：  S d × d =  {X  |  X  ∈ R d × d ，  X  =  X T } ，则增广矩阵 C的决策集可以写成以下形式：0� ，  ∥ C  ∥ tr  ≤  δ ，  Z  ∈  S d × d ， ω  ∈ R d ， ω 0  ∈  R } 。0由于集合  K是是0引理1. 集合 K =  { C  | C  = � Z ω ω T 2 ω 00� ，  ∥ C  ∥ tr  ≤  δ，  Z  ∈0S d × d ， ω  ∈  R d ， ω 0  ∈  R }0证明. 该证明基于凸集的一个重要性质：如果两个集合  S 1  和  S 2是凸的，那么它们的交集  S  = S 1  ∩  S 2  也是凸的0˜ K 和 B 的交集，其中 ˜ K  =  { C  | C  = � Z ω ω T 2 ω 00� ，  Z∈0S d × d ， ω  ∈  R d ， ω 0  ∈  R ， 且 B  =  { C |∥ C ∥ tr  ≤  δ，  C  ∈  R ( d + 1 ) × ( d + 1 ) } 。为了证明 K是凸集，我们需要证明 ˜ K 和 B 都是凸集。首先，我们证明 ˜ K是一个凸集。对于任意的两个点 C 1 ， C 2  ∈ ˜ K 和任意的  α  ∈[0 ,  1]，我们有0�，0其中  Z α  =  α Z 1  +  ( 1  −  α ) Z 2  且  ω α  =  α ω 1  +  ( 1  −α ) ω 2 。根据 ˜ K 的定义，有  Z 1  =  Z T 1 ，  Z 2  =  Z T 2，因此  α Z 1  +  ( 1  − α ) Z 2  =  α Z T 1 + ( 1 − α ) Z T 2。根据转置的性质，  α ω T 1 +  ( 1 − α ) ω T 2 = ( α ω 1  +  ( 1− α ) ω 2 ) T 。因此我们得到  α C 1  +  ( 1  − α ) C 2  ∈ ˜ K。根据定义，  ˜ K  是凸集。其次，我们需要证明 B也是一个凸集。有界核范数球是矩阵的一个典型凸集[6]，在机器学习社区中被广泛采用 [12, 26]。详细的证明可以在 [6]中找到。0根据凸集的交集保持凸性质，我们有  K  = ˜ K ∩ B  也是凸的。 □0由于决策集  K由具有有界核范数的增广矩阵组成，根据块矩阵的性质，我们证明决策集  K  等价于引理2中的对称核范数球。0引理2.  集合  K  =  { C | C  = � Z ω ω T 2 ω 00S d × d ,  ω  ∈  R d }  和  K ′  =  { C | C  ∈ S ( d + 1 ) × ( d + 1 ),  ∥ C ∥ tr  ≤  δ }  是等价的：  K  =  K ′ .0证明很简单，只需将任意对称矩阵写成块状形式，这里省略了细节。通过选择来自紧凑决策集  K  的点  C ，一个实例  x  的预测 ˆ y ( C )可以表示为：0其中 C  ∈ K  ,  ˆ x  = �x 10� .  虽然预测函数  ˆ y  具有02 x T  Zx  of vanilla FM，它们本质上是不同的。将公式代入0的  C  = � Z ω ω T 2 ω 00� 和  ˆ x  = �  x10将其代入预测函数中，0我们有0因此，预测函数  ˆ y ( C )  包含了vanillaFM中的三个组成部分，包括全局偏差、一阶特征权重和二阶特征交互。最重要的是，  ˆ y ( C )  是关于  C  的凸函数，如引理3所示。0C  ∈ K  , 其中  K  =  { C | C  = � Z ω ω T 2 ω 00证明. 根据定义，ˆ y ( C )  是一个可分离的函数：02 x T  Zx ,  h ( ω )  =  ω T  x . 根据定义，  д ( Z )  和 h ( ω )  是关于  Z  和  ω的线性函数，因此是凸函数。考虑  � α  ∈  [0 ,  1] ,  � C 1  = �  Z 1 ω 1 ω T 1 2 ω 00� ∈ K  , 根据分离-0可分离形式的 ˆ y ，我们得到0根据线性函数  д ( Z )  和  h ( ω )的定义以及公式的重新排列，我们有0再次应用可分离形式的 ˆ y ，我们得到0因此，  ˆ y ( α C 1  +  ( 1  − α ) C 2 )  =  ˆ y ( α C 1  +  ( 1  − α )C 2 ) ，根据定义， ˆ y ( C )  是关于  C  ∈ K  的凸线性函数。 □0追踪：Web搜索和挖掘WWW 2018年4月23日至27日，法国里昂FM\\\\CFM [3]√\√\C16370表1：不同FM公式之间的比较 20属性 凸紧凑 全对 在线0CCFM √ √ √ √0接下来，我们证明了在给定上述预测函数ˆy(C): K →R和任意凸损失函数f(y): R → R的情况下，嵌套函数f(ˆy(C)) =f(C)也是凸的，如引理4所示：02ˆxTCˆx，C∈K，ˆxT=[xT,1]，x∈Rd，f(y): R →R为任意凸函数，嵌套函数f(ˆy(C)) = f(C): K →R对于C∈K也是凸的。0证明。令C1∈K和C2∈K为集合K中的任意两个点，f(y)为任意凸函数，根据ˆy的定义，对于任意α∈[0,1]，我们得到0f(ˆy(αC1 + (1-α)C2)) = f(αˆy(C1) + (1-α)ˆy(C2))。0由于f(y)的凸性，我们得到0f(αˆy(C1) + (1-α)ˆy(C2)) ≤ αf(ˆy(C1)) + (1-α)f(ˆy(C2))。0因此，f(αC1 + (1-α)C2) ≤ αf(C1) +(1-α)f(C2)。根据定义，嵌套函数f(ˆy(C)) = f(C)也是凸的。□0总之，通过引入新的凸化方案，我们得到了FM的新公式，其中决策集是凸紧凑的，嵌套损失函数是凸的。我们将得到的公式称为紧凸化FM（CCFM）。表1中展示了普通FM，凸FM和提出的CCFM之间的比较。普通FM和CCFM之间的差异有三个：（i）普通FM的预测函数是非凸的，而CCFM中的预测函数是凸的。（ii）普通FM将特征交互矩阵Z分解为VVT，从而将Z限制为对称且半正定；而在CCFM中，对Z没有特定的限制，除了对称性。（iii）普通FM只考虑不同特征之间的交互：xixj，�i，j∈{1,...,d}，i≠j，而CCFM模拟了所有可能的特征对之间的交互：xixj，�i，j∈{1,...,d}。结合（ii）和（iii），我们发现CCFM允许对特征交互进行一般建模，从而提高了其表达能力。凸FM和CCFM之间的比较。尽管凸FM涉及凸预测函数，但它们与CCFM仍然有本质上的不同：（i）在凸FM中，一阶特征权重向量和二阶特征交互矩阵是分离的，导致非紧凑的公式；但在CCFM中，所有参数都写入一个紧凑的增广矩阵。（ii）在CCFM中，我们限制紧凑的增广矩阵C为低秩；而凸FM的公式只要求二阶矩阵Z为低秩，不限制一阶特征权重向量ω的范围。（iii）凸FM无法轻松适应OCO框架02在表1中，FM，CFM，CCFM分别指代普通FM，凸FM和紧凸FM。术语“凸”表示预测函数是否凸；术语“紧凸”表示公式的可行解集是否紧凑；术语“全对”表示公式中是否涉及所有两两特征交互；术语“在线”表示公式是否适用于在线学习的OCO框架。0，因为其决策集非紧凑，而CCFM可以无缝地适应OCO框架。03.2 紧凸化分解机的在线学习算法0通过上述凸化方案，我们得到了紧凸化分解机（CCFM）的新公式，其中包含了凸紧凑的集合和凸损失函数，这使得我们能够设计遵循OCO框架[26]的在线学习算法。如Preliminaries中所示，决策集是影响投影步骤的计算复杂性的重要问题。在CCFM中，决策集是有界核范数球的子集，投影步骤涉及奇异值分解，并通过我们已知的最佳方法[12]以超线性时间进行。尽管在线梯度下降（OGD）和Follow-The-Regularized-Leader（FTRL）是最经典的在线学习算法，但它们在投影步骤中的昂贵SVD运算方面存在问题，因此在这个特定的决策集上效果不佳。与此同时，核范数球是一个典型的决策集，其中昂贵的投影步骤可以通过投影无需OCG算法中的高效线性优化子程序来替代。由于CCFM的决策集是有界核范数球的子集，我们首先提出了CCFM的在线学习算法（OC-CFM），它本质上是OCG的变体。然后我们详细介绍了OCCFM的理论分析。03.2.1算法。如引言中介绍的，将OCG算法应用于有界核范数球是一种典型的做法。这个典型的例子与CCFM有关，但也有本质上的不同。一方面，CCFM的决策集是有界核范数球的子集。因此，很容易在CCFM的决策集上应用OCG的子程序；另一方面，CCFM的决策集也是对称矩阵的子集，目前尚不清楚子程序是否可以应用于对称有界核范数球。因此，设计一个适用于CCFM的OCG类算法是一个非平凡的问题。为了避免在CCFM的决策集上进行昂贵的投影，我们遵循OCG的核心思想，用线性优化问题替代投影步骤。剩下的工作是设计一个高效的子程序，以低计算复杂度解决这个集合上的线性优化问题。回顾算法1中OCG的过程，这个子程序的有效性取决于以下两个重要要求：0•首先，子程序应以较低的计算复杂度解决决策集上的线性优化问题；在我们的情况下，子程序应以线性或更低的复杂度生成问题的最优解 ˆ C t ，其中  C t是第t轮的迭代结果，K是CCFM的决策集， � F t  ( C t  )是直到第t轮的损失函数梯度的总和。 •其次，子程序应在凸决策集上封闭；在我们的情况下，增广矩阵 C t  应始终在决策集  K  内部：  C t + 1  =0跟踪：Web搜索和挖掘WWW 2018，2018年4月23日至27日，法国里昂theorem 1. In Algorithm 2, the subroutine of linear optimizationamounts to the computation of maximal singular vectors: Given Ct ∈K = {C| ∥C∥tr ≤ δ, C ∈ S(d+1)×(d+1)}, ˆCt = argminC ∈K⟨C, ∇Ft (Ct )⟩ =δu1vT1 , whereu1 andv1 are the maximal singular vectors of −∇Ft (Ct ).theorem 2. In Algorithm 2, the subroutine is closed over the de-cision set K , i.e. the augmented matrix Ct generated at each itera-tion t is inside the decision set K : Ct ∈ K , ∀t = 1, . . . ,T, where= C C trδ, C(d+1)×(d+1) .Similarly, γt is set tomatrices, and Σ ∈ RK×K is a diagonal matrix. The diagonal entriesσi of Σ are non-negative real numbers and known as singular val-ues of C. Conventionally, the singular values are in a permutationof non-increasing order: σ1 ≥ σ2 ≥, . . . , ≥ σK.Next, we prove Lemma 5, which is an important part for the proofof both theorems. In this lemma, we show that the outer product ofthe left and right maximal singular vectors of a symmetric matrix(as part of the subroutine in Algorithm 2) is also a symmetric matrix.16380算法2 在线紧凑凸化因子分解机（OCCFM）0输入：凸集  K  =  { C  | ∥ C  ∥ tr  ≤  δ ,  C  ∈ S ( d + 1 ) × ( d + 1 ) }，最大轮数  T  ，参数  η  和  { γ t  } 3 。01: 初始化  C 1  ∈ K 2:  对于  t  =  1 ,  2 , . . . ,  T  执行以下步骤 3: 获取输入  ( x t ,  y t  )并计算  f t  ( C t  ) 4: 令  F t  ( C  )  =  η � t − 1 τ  = 1 �� f τ  ( C τ  ) ,  C �  +  ∥ C  −  C 1  ∥ 2 2 5:计算  −� F t  ( C t  )  的最大奇异向量：  u  和  v 6: 解决 ˆ C t  =  argmin C  ∈K  � C ,  � F t  ( C t) � ，其中 ˆ C t  =  δ u v T07: 设置  C t + 1  =  ( 1  −  γ t  ) C t+  γ t ˆ C t 8:  结束循环0( 1 − γ t  ) C t  + γ t ˆ C t  ∈ K  ，对于所有 t  =  1 , . . . , T ，其中ˆ C t  是子程序的输出， γ t是第t轮的步长。考虑到这两个要求，我们提出了一个关于对称有界核范数球上线性优化的子程序，基于此我们构建了紧凑凸化因子分解机的在线学习算法。具体来说，我们证明在每一轮中，CCFM决策集上的线性优化也等价于计算特定对称矩阵的最大奇异向量。通过幂法，这个子程序可以在线性时间内解决，验证了其效率。算法2中详细描述了该过程，其中  u  和  v  分别是  −� F t  ( C t  )的左奇异向量和右奇异向量。投影步骤在算法的第5-6行用子程序替代，算法的详细分析将在后面给出。03.2.2理论分析。在线紧凑凸化因子分解机（OCCFM）算法本质上是OCG算法的一种变体，保留了类似的过程。首先，我们证明OCCFM满足前述的两个要求，然后我们根据OCO框架证明OCCFM的遗憾界。为了证明OCCFM满足前述的两个要求，我们分别在定理1和定理2中给出了理论保证。0在我们继续证明定理1和定理2之前，我们对矩阵的奇异值分解（SVD）进行简要介绍，这在定理的证明中经常使用。对于任意矩阵C ∈ Rm×n，奇异值分解是形式为C= UΣVT的分解，其中U ∈ Rm×K和V ∈ Rn×K（K = min{m,n}）是正交矩阵，Σ ∈RK×K是对角矩阵。Σ的对角元素σi是非负实数，被称为C的奇异值。通常，奇异值按非递增顺序排列：σ1 ≥ σ2 ≥ ... ≥σK。接下来，我们证明引理5，这是定理证明的一个重要部分。在这个引理中，我们证明了对称矩阵的左奇异向量和右奇异向量的外积（作为算法2中的子程序的一部分）也是一个对称矩阵。0t1/20引理5.设C ∈ Sd×d是任意的实对称矩阵，C =UΣVT是C的奇异值分解，u1，v1 ∈Rd是C的左奇异向量和右奇异向量，那么矩阵u1vT1也是对称的：u1vT1 ∈ Sd×d。0证明。该证明基于实对称矩阵的奇异值分解和特征值分解之间的联系。将C的奇异值分解表示为C = UΣVT = Σdi=1σiuivi^T，将其特征值分解表示为C = QΛQT = Σdj=1 λjqjqTj。0首先，我们证明CC^T的特征值是C的奇异值的平方：0D = CT C = VΣUTUΣTVT = VΣΣTVT。0由于V是一个正交矩阵，VΣΣTVT是D的特征值分解，其中ΣΣT是D的特征值的对角矩阵，vi，�i ∈{1,...,d}是D的特征向量。由于C是对称的，D = CT C =C^2。对于C的任意特征值λ和特征向量q：Cq = λq，我们有0Dq = CT Cq = CT(Cq) = λCTq = λCq = λ^2q。0因此，C的每个特征值λ的平方也是D的特征值λ^2，每个特征向量q也是D的特征向量v。通过重新排列C的特征值，使得|ˆλi|，i =1,...,d非递增，我们有σi = |ˆλi|。通过将特征值分解C重写为Σdi=1ˆλiˆqiˆqTi = Σdi=1 |ˆλi|ˆpiˆqTi = Σdi=1 σiuivi^T，其中ˆpi =sign(ˆλi)ˆqi，我们有ˆpi = ui，ˆqi = vi，�i = 1,...,d。因此，uivi^T =sign(λi)ˆqiˆqTi，�i = {1,...,d}是一个对称矩阵。□0准备工作完成后，我们证明定理1。0定理1的证明。首先，回忆对于任意的C ∈S(d+1)×(d+1)，C的奇异值分解为C = UΣV = Σ(d+1)i=1σiuivi^T。根据引理5的结论，我们有|ui| = |vi|，�i ∈{1,...,d+1}，我们用C的奇异值分解来重写决策集K：0K={C|C=UΣVT=0i=1σiuivTi,|ui|=|vi|,�i，0�C∈S(d+1)×(d+1)，0i=1σi≤δ，U,V∈R(d+1)×(d+1)}。0回顾一下在算法2中，点是从决策集K生成的：Ct,C1∈K，我们有0�Ft(Ct)=η0τ=1fτ(Cτ)ˆxtˆxTt+2(Ct−C1)∈S(d+1)×(d+1)。0将−�Ft(Ct)表示为Ht∈S(d+1)×(d+1)，Ht的奇异值分解为Ht=�d+1i=1θiµiνTi，其中θi，�i∈{1,...,d+1}是奇异值0Track: Web Search and Mining WWW 2018, April 23-27, 2018, Lyon, France∇FT (CT ) = η2Tt=1ft (Ct ) ˆxt ˆx Tt + 2(CT − C1) ∈ S(d+1)×(d+1),ˆCT = argminC⟨C, ∇FT (CT )⟩ = δu1vT1 ∈ S(d+1)×(d+1),CT +1 =CT + ()CT.T�t=1ft (Ct ) − minC ∗∈KT�t=1ft (C ∗) ≤ 252 DGT 3/4,16390Ht的值，µi，νi分别是左奇异向量和右奇异向量，算法2中的子程序解决以下线性优化问题：0min.�C,�Ft(Ct)�0s.t.C∈S(d+1)×(d+1),∥C∥tr≤δ。0目标函数可以重写为�C,�Ft(Ct)�=�C,−Ht�。线性优化问题可以重写为：0argminC∈K�C,�Ft(Ct)�=argm∈K�0i=1σiuivTi,Ht�。0利用标量的迹的不变性，我们有0argmaxC∈K�0i=1σiuivTi,Ht�=argmaxC∈K0i=1σiuTiHtvi0≤argmaxC∈K0i=1σiξiθπ(i)，�ξi∈{-1,1}。0其中θπ(i)，�i是矩阵Ht的奇异值的一个置换，π是[d+1]上的任意置换。最后一个不等式可以通过引理6得到。根据奇异值的非负性和重新排列不等式，我们有：0d+0i=1σiξiθπ(i)≤0d+0i=1σiθπ(i)≤0d+0i=1σiθi≤0d+0i=1σi∙θ1=∥C∥trθ1。0其中θ1是Ht=�Ft(Ct)的最大奇异值。回忆一下Ht=−�