在线子集选择问题中的子模和凸优化方法

117830通过子模和凸优化进行在线摘要0Ehsan Elhamifar 计算机与信息科学学院东北大学0eelhami@ccs.neu.edu0M. Clara De Paolis Kaluza计算机与信息科学学院 东北大学0clara@ccs.neu.edu0摘要0我们考虑在线环境中的子集选择问题，其中数据逐步到达。我们提出了一种增量子集选择框架，该框架在每个时间点使用先前选择的代表集和新的数据批次来更新代表集。我们将问题建模为整数二进制优化，通过代表项的编码成本最小化来规范化数据。由于所提出的优化通常是NP-hard和非凸的，我们研究了基于无约束子模优化的贪婪方法，并提出了一种高效的凸松弛方法。我们证明，在适当的条件下，我们提出的凸算法的解决方案可以实现非凸问题的全局最优解。我们的结果还解决了离线环境中的常规子集选择问题，作为一种特殊情况。通过对视频摘要问题进行广泛实验，我们证明了我们提出的在线子集选择算法在真实数据上表现良好，能够捕捉视频中多样的代表性事件，同时获得接近离线环境的目标函数值。01. 引言0子集选择是从一个基准集中找到最具信息量的项目子集的任务。除了帮助减少算法的计算时间和内存消耗，由于在一个更小的代表性集合上工作[1]，它还有许多应用，包括图像和视频摘要[2,3,4]，聚类[5,6,7,8,9]，特征和模型选择[10,11,12]，语音和文档摘要[13,14,15]，传感器布置[16,17]，社交网络营销[18]和产品推荐[19]。与诸如Kmeans[20]，KSVD[21]和HMMs[22]等字典学习方法相比，这些子集选择方法从给定的项目集中选择中心/原子。0子集选择算法的输入形式可以是特征向量表示或项目之间的成对相似性。文献中研究了几种子集选择标准，包括最大割目标[23,24]，最大边际相关性[25]，容量限制和无容量限制的设施位置目标[26,27]，多线性编码[2,28]和最大体积子集[14,29]，它们都试图以能够代表整个分布和/或在所选项目之间具有最小信息重叠的能力来表征子集的信息价值。另一方面，几乎所有子集选择标准的优化都是NP-hard和非凸的[24,26,30]，这促使人们开发和研究近似优化这些标准的方法。这包括贪婪近似算法[26]，用于最大化子模函数的图割和设施位置等，它们具有最坏情况下的近似保证，以及从确定性点过程(DPP)[14,29,31]中对所有子集的概率测度，用于近似找到最大体积子集。受凸优化和稀疏低秩恢复的成熟方法和进展的启发，最近的方法集中在基于凸松弛的子集选择方法上[5,6,32,33]。0在线子集选择。顺序数据，包括时间序列，如视频和语音，以及有序数据，如文本，构成现代数据集的重要部分。这些数据集通常以增量方式增长，例如，新的文本/文档/语音随着事件或讨论的发展而到达，或者视频帧不断地从监控摄像头添加到数据库中。鉴于新数据的不断到来，为了进行子集选择和摘要，等待收集整个数据集不仅是不切实际的，而且需要大量的计算和内存资源。事实上，我们经常需要使用代表性进行实时学习、推理、决策和/或规划。此外，捕获数据的设备的内存和计算限制不允许等待和收集整个数据集来进行子集选择。6minS✓D λ|S| +min{zij} λXi2DI(��⇥zi1 zi2 · · ·⇤��p) +Xj2DXi2Ddijzijs. t. zij 2 {0, 1},NXi=1zij = 1, 8 i, j 2 D.(2)17840因此，需要在线子集选择技术，可以在新项目到达时从数据集中选择代表性项目并相应地更新代表集合，以最小化先前选择的项目和新代表之间的信息重叠。尽管这一问题非常重要，但在文献中尚未得到适当的研究，现有的方法依赖于对新数据批次使用离线子集选择技术或使用贪婪方法选择下一个样本，而忽略了新项目相对于旧项目的信息性以及可能需要更新已选择项目集合的可能性。请注意，具有代表数量约束的标准子模方法在在线设置中通常不起作用，因为应该从每个批次中选择的信息性项目数量通常是不同的。此外，它们会导致选择最大数量的代表，这可能会导致信息重叠。0论文贡献。在本文中，我们提出了一个在线子集选择框架，可以有效处理增量观测，而无需存储和处理整个数据。我们将问题建模为整数二进制优化问题，使用已获得的代表和新到达的数据来增量更新代表集合。由于所提出的优化问题是非凸的，并且通常是NP难的，我们首先研究了一种基于子模优化的前向-后向贪婪方法，该方法具有次优性能保证。此外，我们提出并研究了原始在线子集选择优化问题的凸松弛。我们证明，在适当的条件下，我们提出的凸算法是精确的，即它实现了原始非凸公式的全局最优解。我们的理论结果不仅解决了在线子集选择问题，还解释了离线情况下凸松弛的成功。通过对真实视频数据的大量实验，我们证明了我们的框架在在线视频摘要中的有效性。0论文结构。本文的结构如下。第2节回顾了离线设置下的子集选择问题。第3节提出了一个增量在线子集选择框架，并研究了问题的贪婪和凸松弛方法。第4节研究了凸公式的理论保证。第5节展示了我们的方法在视频摘要问题上的有效性。最后，第6节总结了本文。02. 子集选择回顾0在本节中，我们使用成对不相似性来回顾子集选择问题。我们重点关注便利性。0位置目标函数，促进代表性的多样性，诱导数据的聚类，并且易于进行凸松弛。在下一节中，我们基于这个目标函数来解决在线子集选择问题。0设D表示我们想要选择一个小的代表集合的N个项的集合。设d ij表示项i和j在D中的不相似性。换句话说，dij表示i代表j的程度（越小越好）。我们假设d ij ≥0，并且对于每个项j，我们有d jj < d ij对于所有i ≠j，即每个点都是自己的最佳代表。我们的目标是找到一个小的D的子集S，通过代表的总编码成本最小地代表整个集合，给定成对的不相似性{ d ij } i,j =1 ,...,|D|。设施位置目标通过选择一部分项并将其余项分配给一个且仅一个代表来实现这个目标，从而最小化通过代表对集合D的编码成本。更准确地说，我们求解0j 2D min i 2S d ij , (1)0其中，λ >  0是一个正则化参数，用于在代表集合的大小|S|和通过S对D进行编码的编码成本之间进行权衡。需要注意的是，如果没有这样的正则化，即λ = 0，我们将得到S =D的平凡解，其中每个项都是自己的代表。0[5]中的最新工作将(1)重新表述为一个同时稀疏恢复优化问题，其中引入了与d ij对应的二进制优化变量z ij，其中zij表示i是否将成为j的代表，并提出求解0类似于(1)，上述优化问题中的第一项计算代表数量（I( ∙)表示指示函数），第二项对集合D通过代表的编码进行编码。我们可以从(2)中获得代表，即对于某个D中的j，使得z ij=1的项i。我们用R表示代表的集合。此外，(2)通过代表将集合D进行聚类，其中每个聚类由R中的每个代表i和满足z ij =1的D中的项j组成。0由于(2)通常是NP-hard和非凸的，[5]提出了一个凸松弛，通过去掉指示函数并放宽变量的二进制约束来解决min{zij} λXi2D��⇥zi1 zi2 · · ·⇤��p +X Xdijzijs. t. zij ≥ 0,Assume we have a sequential set of items that arrive inan incremental fashion. Our goal is to select a small subsetof items in an online fashion that effectively represents theentire dataset. Let D(t)odenote the set of data points arrivedprior to time t and D(t)n denote the set of newly arrived itemsat time t. To perform subset selection, we ideally would liketo run the offline algorithm in (2) or its convex relaxationin (3) on the entire dataset available thus far, i.e., D(t)o[D(t)n . However, as t grows, the set D(t)ogrows, which has thedrawback of increasing the computational time and memoryfor running the offline subset selection.In this section, we propose an algorithm that updates rep-resentatives at time t using previously selected representa-tives, denoted by E(t)o , and the set D(t)n , which significantlyreduces the computational time and memory, especially incases where D(t)n is of small or moderate size compared toD(t)o . More specifically, starting from D(0)o , we performsubset selection to obtain E(0)oand at time t, we proposea framework that uses old representatives E(t)oand new setD(t)n to update the set of representatives, forming E(t+1)othatwill be used in the next time index. To do so, we need tomake sure that representatives selected from D(t)nare notredundant with respect to previous representatives, E(t)o .Since we only need to focus on the formulation at time t,for simplicity of notation, we use Eo instead of E(t)o , andsimilarly use Do, Dn. With abuse of notation, we referto both items and indices of items using Do, Dn and Eo.Let {do,oij }i,j2Eo denote dissimilarities between old repre-sentatives, {do,nij }i2Eo,j2Dn denote dissimilarities betweeni2Eoi2Dn(5)17850z ij  2  [0 ,  1] . 更准确地说，通过求解优化问题0i 2D z ij  = 1 ,  8  i, j  2 D , (3)0对于 p  ≥  1，(3)是凸的。事实上，在适当的成对不相似性条件下，(3)可以获得数据的真实聚类，如[5]所示。重要的是要注意，(3)在离线情况下执行子集选择，即整个集合D可用。此外，(3)等价于原始问题(2)的理论保证尚不清楚。为了解决这些问题，在下一节中，我们提出了一种增量子集选择算法，以处理在线观测，研究了问题的贪婪和凸松弛，并提出了在在线和离线设置中保证凸形式与原始问题等价的理论结果。03. 在线子集选择0旧代表和新数据之间的{dn,oij} i 2Dn，j2Eo是新数据和旧代表之间的不相似性，{dn,nij} i，j2Dn表示新数据之间的不相似性。在本文中，我们让不相似性是非对称的和/或违反三角不等式的。为了解决增量子集选择的问题，我们通过定义与不相似性相关的变量Z，{{zo,oij}，{zo,nij}，{zn,oij}，{zn,nij}}提出了一个优化。我们考虑以下编码成本函数0Jenc，X0j 2Eo do,oij zo,oij+ X0j 2Dn do,nij zo,nij0+ X0j 2Eo dn,oij zn,oij+ X0j 2Dn dn,nijzn,nij，(4)0它衡量了通过从Eo[Dn中选择的代表来编码旧代表和新数据的总成本。与离线模式类似，我们需要限制来自Eo[Dn的代表集的大小。然而，与以前不同，Eo中的项已经显示具有代表性，即它们是D o \Eo中的项的代表，因此选择Eo中的项不应受到惩罚。另一方面，只要Eo中的项没有足够的代表性，我们只需要从Dn中选择代表。因此，我们只需要惩罚从Dn中选择的代表的数量。0min Z Jenc +0i 2Dn I( ��� zn,ni1 zn,ni2 ∙ ∙ ∙ zn,n,i1 zn,n,i2 ∙ ∙∙ ��� p )0s .  t . zo,oij，zn,oij，zo,nij，zn,nij 2 { 0 ,1 }，0i 2Eo zo,oijX0i 2Dn zn,oij = 1，8 j 2Eo，0i 2Eo zo,nij0i 2Dn zn,nij = 1，8 j 2Dn，0其中目标函数中的第一项衡量了通过从Eo [Dn中选择的代表来编码Eo[Dn的成本，而第二项惩罚了从Dn中选择的代表的数量。约束条件确保选择变量是二进制的，并且Eo[Dn中的每个点必须由一个代表表示。换句话说，所提出的优化的效果是使用旧代表来表示新项目，只要相关的编码成本足够小（我们将在后面量化这一点），并且在旧代表不足时从Dn中添加新代表，例如当数据中出现新的聚类时。请注意，足够大的正则化参数λ促使仅选择旧代表Eo，而较小的λ促使从Dn中选择更多的新代表。101我们可以通过对选择旧代表的正则化进行小幅度的调整和更新来允许删除和更新旧代表。(6)i2EoNotice that the solution of the above optimization willdetermine the representatives and clustering of the data atthe same time. More specifically, optimization variableszn,nijthat are equal to 1 indicate that i 2 Dn is a repre-sentative (we already know that all points in Eo will remainrepresentatives). We denote the set of all representatives byR. For j 2 Dn, we denote the representative of j by M(j).In other words, we always have zM(j)j = 1. We also obtainclustering of the data, where the `-th group corresponds toitems that are assigned to the `-th representative.In this section, we discuss an efficient algorithm basedon unconstrained submodular optimization for solving theproposed online optimization in (6). To do so, note that wecan write (6) in the equivalent formi2Dn(10)17860我们可以证明，在（5）中优化的解总是找到zo,oii =1，对于所有i 2 Eo，以及zn,oij = 0，对于所有i 2 Dn和j 2Eo。换句话说，每个旧代表将始终被选为其自身的代表。因此，我们考虑更简单的优化0min Z0 J0enc 0i 2Dn I( ��� zn,ni1 zn,ni2 ∙ ∙ ∙ ���p )0s .  t . zo,nij，zn,nij 2 { 0 , 1}，8 0i 2Eo zo,nij0i 2Dn zn,nij = 1，8 j 2Dn，0通过较小的优化变量集Z0，{{zo,nij}，{zn,nij}}，定义J0enc为0J0enc，X0j 2Dn do,nij zo,nij +X0j 2Dn dn,nijzn,nij，(7)0通过Eo中的项来测量新数据Dn的编码成本。实际上，我们可以证明以下结果。0命题1优化程序（5）和（6）是等价的，即它们对{zo,nij}和{zn,nij}获得相同的解。03.1. 贪心无约束子模优化算法0min S∈Dn f(S)，(8)0f(S)，X0在本节中，我们讨论了一种基于无约束子模优化的高效算法，用于解决（6）中提出的在线优化问题。为此，注意我们可以将（6）写成等价形式0需要注意的是，尽管（9）中的在线优化问题通常是非凸的和NP难的，但它是子模的。换句话说，f(S)满足递减回报性质，即J(S[{`}]) - J(S) ≥ J(T[{`}]) - J(T)0其中函数f(S)定义为0输入：无约束最大化集合Dn上的子模函数f(∙)。0j 2D n min {min i 2E o d o,n i,j, min i 2S d n,ni,j} + λ |S|。(9)05：以概率a`/(a` + b`)执行以下操作：6：X` =X`-1[{D`n}]，Y` = Y`-1。7：否则（以概率b`/(a` +b`)）执行以下操作：8：X` = X`-1，Y` =Y`-1\D`n。9：结束循环。输出：由X|Dn|索引的Dn中的代表集合。0算法1：无约束子模优化的随机贪心算法03.2. 基于凸松弛的算法01：初始化：X0 = �和Y0 = Dn。2：对于` =1，...，|Dn|，执行以下操作：3：a` = max{f(X`-1[D`n]) -f(X`-1), 0}4：b` = max{f(Y`-1\D`n) - f(Y`-1), 0}0min J0enc + λ X0s.t. zo,nij, zn,nij ∈ [0, 1], �i, j, X0i 2E o z o,nX0i∈Dn zn,nij = 1, �j∈Dn。0我们选择 p = 2 {2,1}，对于这两个选择，上述优化都是凸的。正如我们将通过理论分析展示的那样，选择“p-范数”会影响代表结构。当p = 1 时，促进选择每个聚类的中心点，而当 p = 2时，允许偏离中心点以实现不平衡的聚类大小。04. 理论分析06650010001500200025003000350050010001500200025003000350050010001500200025003000350050010001500200025003000350017870定理2：对于给定的λ和p =1，优化程序（10）的解等同于（6），如果满足以下所有条件：0定理1：优化程序（6）的解满足以下条件：0N M(j) + d0j：M(j) = M(i) dn,nM(i)j≤ P。0N M(j) + dn,nM(j)j ≥dn,nij；02. 对于每有P。0（a）0粗略地说，上述条件是关于从Dn和Eo中的代表物的中心点的定义。上述定理中的第一个条件是群组中的中心点的传统定义，即群组中达到最小编码成本的项目。第二个条件描述了由Eo中的项目表示的Dn中的群组的中心点。它说明了Eo中的每个代表通过成本最多比我们通过将代表从Dn分配给Eo而获得的最佳编码大λ来对Dn中的项目进行编码。否则，我们可以将群组中的所有项目分配给在Dn中获得此最小编码成本的项目，从而将目标函数的第一项减小超过λ，而附加的代表仅将目标函数的第二项增加λ，从而降低总体成本。请注意，上述结果也适用于离线设置，其中Eo为空。在这种情况下，我们只有定理1的第一个条件得到满足。接下来，我们研究在凸松弛（10）中以p =1恢复（6）中的优化程序解的条件。0（c）01. 对于每个i ∈ Dn，其中i∈R，并且对于每个j，其中M(j) ≠M(i)0（e）02. 对于每个i ∈ Dn，其中i∈R，M(i)∈Dn，并且对于每个j，其中M(j) =M(i)0（e）03. 对于每个i ∈ Dn，其中i∈R，并且对于每个j，其中M(j)≠ M(i)且M(j)∈Eo，我们有do,nM(j)j < dn,nij。0图1：来自SumMe数据集[37]的视频“自由女神像”的真实摘要（a）每个用户选择的摘要帧，黑色表示选择的帧。上面显示了一些说明性的帧，红线表示它们在时间轴上的位置。注意，不同用户的真实摘要不同，但大多数用户之间的片段有重叠。（b）组合真实摘要，通过对所有用户摘要进行平均计算。（c-g）选择了正则化以匹配平均用户摘要长度。（c）离线凸方法选择的摘要，p = ∞，α =0.095。（d）在线凸方法摘要，p = ∞，α =0.38，批量大小为15个超帧，约占视频长度的20%。（e）在线凸方法摘要，p = ∞，α =0.77，批量大小为8个，约占视频长度的10%。0第一个条件说明了从其他组到由新代表表示的组的最近项与之足够远。第二个条件说明了同一组中的项之间不远，即组j中的每个项与该组的代表之间的距离最多为λ/NM(j)。最后，最后一个条件说明了由新代表表示的项必须与由旧代表表示的项足够远。0注1本节中呈现的结果也适用于离线设置，其中Eo为空。在这种情况下，定理1只满足第一个条件，定理2必须满足前两个条件。05. 实验0在本节中，我们评估和比较了我们提出的凸松弛和子模块算法的性能。17880图2：SumMe数据集中“埃菲尔铁塔”视频的在线凸方法摘要，其中p = ∞，正则化参数α =0.445。显示了一个代表帧来代表一个超级帧。红色边框表示选择的超级帧包含在摘要中。批处理大小固定为视频的约10％，即每个批处理处理10个超级帧，对于92个超级帧的视频。0图3：在线子模块方法选择的超级帧，与图2中相同的视频。正则化参数（α = 0.855）已设置为选择与凸方法相同数量的超级帧，其中p =∞。批处理大小固定为视频的约10％。0我们还将这些在线方法与相应的离线摘要方法进行比较。最后，我们研究了选择`p-范数p2 {2,1}`和正则化参数λ对在线摘要选择的影响。为此，我们将我们的方法应用于两个真实世界的视频数据集并报告结果。05.1. 数据集和预处理0我们在两个真实世界的数据集上评估我们的方法的性能，分别是SumMe [37]和TVSum50[38]数据集。SumMe数据集包含25个视频，长度从不到1分钟到超过6分钟不等，由具有静止、移动或自我中心摄像机设置的视频组成，涵盖不同的主题类别。每个视频至少有15个附带的人工提供的摘要，每个参与者在每个视频中选择了5％到15％的帧包含在他们的摘要中。这些人工提供的摘要作为数据集的真实摘要。TVSum数据集包含来自不同类别的50个视频，长度在2到10分钟之间。这里，每个视频至少提供了20个人工评估。与提供视频摘要不同，参与者对每个视频中的每个两秒段落的相对重要性进行了排名。按照[38]中的实验设置，我们使用这些段落排名选择前15％的段落作为每个视频的人工摘要。为了评估我们的方法与这些用户提供的摘要的性能，我们计算了跨所有用户的综合或平均的真实摘要。综合摘要包含视频中每个帧的分数，对应于选择该帧作为摘要的用户的百分比。0mary.图1a展示了SumMe数据集中一个视频的所有用户的真实摘要，图1b展示了相应的综合真实摘要。对于这两个数据集，我们按照[37]中的描述将每个视频分割成超级帧，其中每个超级帧是一系列帧的序列，选择这些帧以产生自然的镜头切换。对于每个超级帧，我们提取描述在[39]中描述的卷积3D（C3D）特征。我们使用这些特征生成不相似性矩阵D，其中(D)ij是超级帧i和超级帧j之间特征向量的欧氏距离。因此，我们的方法在超级帧级别生成摘要。也就是说，自动生成的摘要是选择用于总结每个视频的超级帧的集合。我们通过将所选超级帧中包含的所有帧作为摘要来将超级帧级别的摘要转换为帧级别的摘要。为了通过我们提出的方法选择代表，我们设置λ =λmax，其中λmax是我们选择一个代表的正则化参数值。我们通过类似于[5]的方法分析确定λmax。图1c-1e展示了SumMe数据集中视频“自由女神像”的离线和在线凸方法选择的帧。结果显示，不同批次大小的在线方法选择与人工真实摘要非常吻合的视频帧。图2和图3分别展示了在线凸方法和子模块方法得到的多样化自动摘要，选择了9个代表性超级帧。在每种情况下，每个所选超级帧都显示了一个代表帧。05.2. 使用地面真实摘要评估错误0为了评估我们提出的方法的性能，我们将自动生成的摘要与每个数据集中的地面真实摘要进行比较。)1357911131517191357911131517890凸，p = ∞ 凸，p = 2 贪婪子模块化0人类 离线 基线 在线 离线 基线 在线 离线 基线 在线0SumMe 0.03220 0.00869 -0.0211 0.0230 -0.0273 -0.0282 0.0291 0.0263 -0.0071 0.01420TVSum 0.1696 0.0159 0.00055 0.02303 0.00524 -0.00777 -0.00357 0.005016 0.007184 0.024460表1：SumMe和TVSum数据集上所有用户摘要和所有视频的平均MCC。首先列出了与所有视频的所有人工摘要相比的平均MCC。我们还计算了每个视频与自动摘要最相似的人工摘要的MCC，括号中显示。第一列显示了人工摘要之间的一致性。0在每个数据集中，我们没有明确限制我们的方法生成的摘要的大小，因此自动摘要的大小可能与近似固定大小的地面真实摘要差异很大。比较的摘要大小差异使得传统的F-measure（例如[37]和[38]中使用的）不适合作为一致性的度量。特别是，F-measure是精确度和召回率的函数，不包含摘要的特异性。特异性或真负率是衡量方法能够识别负例（在本例中，不在摘要中的帧）的能力的指标。如果不限制自动摘要的大小，F-measure将偏向于更大的摘要。考虑极端情况，自动摘要选择所有帧都在摘要中。在这种情况下，召回率为1，因为该方法确实识别出了所有“真正”的摘要帧，而精确度等于地面真实摘要的大小。在这种情况下，F-measure失败，因为没有对漏掉的“负例”进行惩罚。作为F-measure的替代，我们使用马修斯相关系数（MCC）[40]定义如下0MCC = TP × TN - FP × FN p0（TP + FP）（TP + FN）（TN + FP）（TN +FN）（11）其中TP是真正例的数量（正确识别为摘要的帧数），TN是真负例的数量（正确识别为不属于摘要的帧数），FP是假正例的数量（算法选择为摘要中的帧数，但不在地面真实摘要中），最后FN是假负例的数量（地面真实摘要中的帧数，但不在自动摘要中）。MCC的值介于1和-1之间，分别对应于与地面真实摘要的完全一致和完全不一致。05.3. 结果0为了评估提出的在线方法，我们比较了数据集中每个视频的MCC，包括i）相应的离线摘要方法；ii）基线02000 4000 6000 8000 10000 12000 14000帧编号0用户编号01000 2000 3000 4000 5000 6000 帧编号0用户编号0图4：TVSum（顶部）和SumMe（底部）数据集中样本视频的用户摘要。用户摘要差异很大。有些用户更喜欢较少但较长的片段，有些用户更喜欢较多但较短的片段，有些用户同时使用两种技术进行摘要。0在线摘要，每个批次的摘要都是在不考虑之前选择的代表性摘要的情况下选择的；iii）提出的在线方法。对于在线和基线摘要方法，批次大小固定为视频中超帧的10％。对于每种方法，选择正则化来选择与视频中15％的帧尺寸最接近的超帧摘要，以匹配地面真实摘要的大小。SumMe和TVSum数据集的平均MCC结果列在表1中。我们列出了所有用户和所有视频的平均MCC。为了解决用户之间的低一致性，我们还显示了视频之间的平均最佳MCC。该指标显示了与自动摘要最相似的人工摘要的平均一致性。所有视频和所有用户之间的平均一致性（MCC）与平均最佳一致性之间的差异显示了使用用户摘要作为地面真实摘要评估摘要的局限性。特别是，用户可能以不同的方式摘要每个视频，每个用户可能以不同的方式摘要特定视频，如图4所示。表1还列出了每个数据集中人工摘要之间的平均MCC。00.20.40.6MCConline convex p=2offline convex p=2online convex p=∞offline convex p=∞online submodularoffline submodular-0.100.10.20.30.4MCC(a)010203040(b)0510152025179000 0.2 0.4 0.6 0.8 1 λ  (正则化参数)00 0.2 0.4 0.6 0.8 1 λ  (正则化参数)0在线凸优化 p=2离线凸优化 p=2在线凸优化 p=∞离线凸优化 p=∞在线子模块化离线子模块化0图5：在线和离线设置中贪婪子模块和凸优化方法的MCC，其中p∈ {2,∞}。在线方法的批处理大小为总超帧的10%（上）和20%（下）。00 0.2 0.4 0.6 0.8 1 λ  (正则化参数)0目标函数0基线离线在线00 0.2 0.4 0.6 0.8 1 λ  (正则化参数)0目标函数0基线离线在线0图6：凸优化方法的目标函数值，其中（a）p = 2，（b）p =∞，用于总结SumMe数据集中的视频“Car overcamera”。在线方法实现的值与相应的离线方法相似。基线获得更高的成本，对应于长时间和/或重复的摘要。0方法的性能与用户摘要的可变性有关，因此与用户摘要相比，所提出的在线方法的性能接近离线设置，并且通常优于基线方法。离线方法考虑整个视频优化目标函数。0然而，对于两个数据集，对于p = 1，对于SumMe的p =2以及对于TVSum的子模块化，离线方法的性能低于在线方法。这个结果可以归因于人工摘要是“在线”生成的，即用户在播放视频时摘要，尽管他们可以返回到以前的帧来修改摘要。然而，人工摘要之间的差异可能导致不直观的结果，因此我们还分析了方法实现的目标值，将在下面讨论。目标函数捕捉编码成本和过长摘要的惩罚，因此可以比依赖于不同的真实摘要更直接地解释。图5展示了在线和离线设置的MCC值，其中包括两个批处理大小的结果。结果表明，有很大范围的λ使得所提出的方法表现良好。此外，注意到p =1的凸优化方法和贪婪子模块化方法的一致性比p =2的凸优化方法更接近。最后，图6显示了基线、在线和离线设置中原始非凸目标函数的值。结果表明，在线方法实现了与离线方法相近的目标值，同时比基线方法获得更低的成本。较小的λ值表示选择长摘要的惩罚较小，因此所有方法通过选择大多数超帧来执行类似的操作。随着正则化的增加，较长的摘要将受到更强烈的惩罚。在线和离线设置之间的一致性验证了我们的在线方法的有效性，其中每个在线批次的代表帧是在先前选择的代表帧和当前批次的帧中选择的。这些结果还可以作为评估自动摘要的替代方法，特别是在没有人工真实摘要或人工摘要之间的一致性较低时。06. 结论0我们研究了在线设置中的子集选择问题，其中数据逐渐到达。我们提出了一个增量子集选择框架，每个时间点使用先前选择的代表集和新的数据批次来更新代表集。我们将问题建模为整数二进制优化，通过代表物品的编码成本最小化，由选择的项目数量进行正则化。通过对真实视频的实验，我们证明了我们的在线视频摘要方法的有效性。17910参考文献0[1] S. Garcia，J. Derrac，J. R. Cano和F.Herrera，“最近邻分类的原型选择：分类和实证研究”，《IEEE模式分析与机器智能交易》，第34卷，第3期，第417-435页，2012年。10[2] E. Elhamifar，G. Sapiro和R.Vidal，“通过查看少量对象来查看全部：用于寻找代表性对象的稀疏建模”，《IEEE计算机视觉和模式识别会议》，2012年。10[3] B. Gong，W. Chao，K. Grauman和F.Sha，“用于监督视频摘要的多样化顺序子集选择”，《神经信息处理系统》，2014年。10[4] I. Simon，N. Snavely和S. M.Seitz，“在线图像集合的场景摘要”，《IEEE国际计算机视觉会议》，2007年。10[5] E. Elhamifar，G. Sapiro和S. S.Sastry，“基于差异的稀疏子集选择”，《IEEE模式分析与机器智能交易》，2016年。1, 2, 3, 60[6] E. Elhamifar，G. Sapiro和R.Vidal，“通过同时稀疏恢复从成对不相似性中找到典型对象”，《神经信息处理系统》，2012年。10[7] G. Kim，E. Xing，L. Fei-Fei和T.Kanade，“通过各向异性扩散上的子模优化进行分布式共分割”，《国际计算机视觉会议》，2011年。10[8] A. Shah和Z.Ghahramani，“行列式聚类过程-一种基于核的半监督聚类的非参数贝叶斯方法”，《不确定性人工智能会议》，2013年。10[9] R. Reichart和A.Korhonen，“通过DPP的动词聚类改进的词汇获取”，《计算语言学协会会议》，2013年。10[10] E. Elhamifar，S. Burden和S. S.Sastry，“自适应分段仿射逆建模混合动力系统”，《国际自动控制联合会(IFAC)世界大会》，2014年。10[11] I. Guyon和A.Elisseeff，“变量和特征选择简介”，《机器学习研究杂志》，2003年。10[12] I. Misra，A. Shrivastava和M.Hebert，“数据驱动的典型模型选择”，《计算机视觉应用冬季会议》，2014年。10[13] H. Lin和J.Bilmes，“学习混合子模壳并应用于文档摘要”，《不确定性人工智能会议》，2012年。10[14] A. Kulesza和B.Taskar，“用于机器学习的行列式点过程”，《机器学习基础与趋势》，第5卷，2012年。10[15] B. J. Frey和D.Dueck，“通过数据点之间的消息传递进行聚类”，《科学》，第315卷，2007年。10[16] A. Krause，H. B. McMahan，C. Guestrin和A.Gupta，“鲁棒的子模观测选择”，《机器学习研究杂志》，第9卷，2008年。1, 20[17] S. Joshi和S.Boyd，“通过凸优化进行传感器选择”，《IEEE信号处理交易》，2009年。10[18] J. Hartline，V. S. Mirrokni和M.Sundararajan，“社交网络上的最优营销策略”，《万维网会议论文集》，2008年。10[19] D. McSherry，“多样化感知检索”，《案例推理进展》，2002年。10[20] R. Duda, P. Hart和D.Stork，“模式分类”，Wiley-Interscience，2004年10月。10[21] M. Aharon，M. Elad和A. M.Bruckstein，“K-SVD：一种用于稀疏表示的过完备字典设计算法”，《IEEE信号处理交易》，第5