通过单调布尔函数的加权影响实现最大一致性

Erchuan Zhang∗David Suter∗,‡Ruwan Tennakoon∗∗Tat-Jun Chin†Alireza Bab-Hadiashar∗∗Giang Truong∗Syed Zulqarnain Gilani∗,‡{erchuan.zhang, d.suter, h.truong, s.gilani}@ecu.edu.au {ruwan.tennakoon,abh}@rmit.edu.autat-jun.chin@adelaide.edu.aumaxθθθ∈Ω,I⊆X|I|,s.t.r(xxxi,θθθ) ⩽ ε,∀ xxxi ∈ I,(1)89640通过单调布尔函数的加权影响实现最大一致性0� 澳大利亚珀斯艾迪斯科文大学人工智能与机器学习中心. ‡澳大利亚珀斯艾迪斯科文大学营养与健康创新研究所. �� 澳大利亚墨尔本皇家墨尔本理工大学.  †澳大利亚阿德莱德大学.0摘要0最大一致性最大化（MaxCon）是计算机视觉中最常用的鲁棒性准则之一。Tennakoon等人（CVPR2021）将MaxCon与单调布尔函数的影响估计联系起来。在这种情况下，涉及两个分布：定义影响度量的分布和用于估计影响度量的采样分布。本文研究了解决MaxCon的加权影响概念。特别地，我们研究了伯努利度量。从理论上讲，我们证明了在这种度量下，属于较大结构的点的加权影响小于属于较小结构的点的加权影响。我们还考虑了另一种“自然”的加权策略：在立方体的特定（Hamming）级别上集中的均匀度量采样。可以选择具有匹配分布：用于定义度量和实施采样的相同分布。这样做的好处是采样器是度量的无偏估计量。基于加权采样，我们修改了Tennakoon等人的算法，并在合成和真实数据集上进行了测试。我们展示了伯努利采样的一些适度增益，并阐明了数据结构和加权度量以及加权采样之间的一些相互作用。01. 引言0在存在异常值的情况下处理数据的鲁棒模型拟合是一个基本问题，也是一个长期存在且具有挑战性的研究课题。最大一致性最大化（MaxCon）是最流行的鲁棒拟合准则之一，其目标是找到在给定测量上具有最大一致性的模型。形式上，给定大小为 n 的数据集 X = { xxx i } n i =1 和预定的数学模型的参数集 Ω ，其中θθθ 是模型参数，|I| 是子集 I � X 的大小，r ( xxx i ,θθθ ) 是数据 xxx i 相对于模型 θθθ的拟合残差。随机抽样一致性（RANSAC），即“原始的MaxCon算法”，可能是自20世纪80年代提出以来最有影响力和广泛使用的方法之一[10]。其关键思想是采用假设和验证过程，随机抽样子集来拟合模型，并计算相对于所得模型的一致性。这种随机化方法可能非常快速，但不能保证解的最优性。RANSAC的变体，如LO-RANSAC [6]和PROSAC[5]，可以改进原始的RANSAC，但仍然继承了随机化方法的缺点。相关方法基于M-估计范式，或者其他修改残差度量的方法。例如：l1方法[20]，l∞方法[22,23]，迭代加权最小二乘法[1]，加权l1方法[21]，精确罚函数法[15,16]。已知MaxCon问题是组合难题[3]。最优方法（分支定界（BnB）搜索[17]和A*树搜索[2,4]）存在，但它们的（最坏情况）运行时间随问题规模呈指数增长，使其对于大规模和高维问题无效。本文直接继承了[24]的工作-在这里研究了影响度量和相关估计方法的替代定义。该工作又使用了Chin等人[4]的基本“树”策略，该策略在LP类型的基础上使用A*搜索树结构。0阈值  ε >  0，对于预定类型的数学模型，最大一致性准则被定义为，0其中 Ω 是预定数学模型允许的参数集，θθθ是模型参数，|I| 是子集 I � X 的大小，r ( xxx i ,θθθ ) 是数据xxx i 相对于模型 θθθ的拟合残差。随机样本一致性（RANSAC），“原始的MaxCon算法”，自20世纪80年代提出以来可能是最有影响力和广泛使用的方法之一[10]。其关键思想是采用假设和验证过程，随机抽样子集来拟合模型，并计算相对于所得模型的一致性。这种随机化方法可能非常快速，但不能保证解的最优性。RANSAC的变体，如LO-RANSAC [6]和PROSAC[5]，可以改进原始的RANSAC，但仍然继承了随机化方法的缺点。相关方法基于M-估计范式，或者其他修改残差度量的方法。例如：l1方法[20]，l∞方法[22,23]，迭代加权最小二乘法[1]，加权l1方法[21]，精确罚函数法[15,16]。已知MaxCon问题是组合难题[3]。最优方法（分支定界（BnB）搜索[17]和A*树搜索[2,4]）存在，但它们的（最坏情况）运行时间随问题规模呈指数增长，使其对于大规模和高维问题无效。本文直接继承了[24]的工作-在这里研究了影响度量和相关估计方法的替代定义。该工作又使用了Chin等人[4]的基本“树”策略，该策略在LP类型的基础上使用A*搜索树结构。0.10.20.30.40.50.60.70.80.90.40.60.811.21.41.61.8PointsSolutionOutliers0102030405060700123456780011111110001101011000101101000000001101Infi[f] := Pbbb∼{0,1}n f(bbb) ̸= f(bbb⊕i) ,(3)89650A*搜索能够找到全局最优解。然而，这种方法通常很慢，尽管Cai等人[2]引入了加速。在[25]中，提出了一种无监督学习方法来确定在解决鲁棒模型拟合问题时要删除的基向量。这种方法采用了强化学习的框架，其中删除点是通过最大化奖励来引导的。像许多基于学习的方法一样，训练时间可能很长，很难分析该方法及其泛化能力。像[25]和[24]一样，对基本树搜索的修改会丧失A*的优先级队列保证，以换取速度上的优势。本文也是在这个背景下进行的。01.1. 影响和共识最大化0最近，Tennakoon等人[24]通过单调布尔函数理论对最大共识问题进行了表征，并通过单调布尔函数的影响研究了MaxCon解的特征。详细地说，任何子集I�X={xxx i}ni=1都可以用长度为n的比特向量bbb表示，其中它的第i个分量bi=0表示排除数据xxx i，bi=1表示包含数据xxxi。然后，任何子集I不过是n维布尔立方体的一个顶点而已。布尔函数f:{0,1}n→{0,1}定义如下：0f(bbb)：=0如果r(θθθ,xxx i) > ε，则为1，如果r(θθθ,xxx i) �ε，则为0，对于所有i∈{j:b j = 1}。（2）0定义可行性（如果f(bbb)=0，则称子集{xxxi}为可行的，否则为不可行的）。解决MaxCon问题是在可行子集中寻找最大尺寸的搜索。如果对于任何aaa�bbb，都有f(aaa)�f(bbb)，则布尔函数称为单调函数，其中�表示i-th分量ai�bi，对于任何1�i�n。我们可以很容易地看出布尔函数（2）是单调的。原因是将数据点添加到不可行子集仍然保持它们的不可行性，而从可行子集中删除数据点保持它们的可行性。单调布尔函数f的上部零bbb是一个顶点，使得f(bbb)=0，并且对于任何满足bbb�aaa的aaa，都有f(aaa)=1。f的最大上部零bbb是具有最大尺寸的上部零，即f(bbb)=0，并且对于任何满足∥aaa∥1>∥bbb∥1的aaa，都有f(aaa)=1，其中∥∙∥1是l1范数。上部零系统地刻画了所有可能的候选共识解，并且找到最大共识等价于找到相关布尔函数的最大上部零。参见图1，这是一个关于2D线拟合的玩具示例，说明了单调布尔函数与MaxCon问题之间的联系。[24]中的关键概念是影响。当给布尔立方体赋予均匀度量时，影响是0图1.左图：具有8个点的2D线拟合问题。右图：与拟合问题相关的布尔立方体。将8维布尔立方体展开在平面上，其中每个蓝色点表示线拟合问题的不可行子集，其他颜色的点表示可行子集。这些点按照从上到下的顺序通过顺序关系�排列。在这个示例中，有四个上部零，即bbb6 =00111111（最大上部零，上标表示选择了多少个数据点），bbb4= 10001101，bbb3 = 011000010，bbb3' =11010000，这些在立方体和由这些顶点确定的子立方体上用不同的颜色区分开。顶点bbb3'' =00001101是一个伪上部零（见第3节中的定义）。注意，所有低于3级的顶点，即拟合少于3个点的顶点，必须是可行的。0布尔函数f的第i位bi的定义[19]如下，0其中bbb ⊕ i表示翻转bbb中的第i位，bbb � { 0 ,  1 } n0意味着bbb在布尔立方体上均匀分布。为了估计方程（3）中的影响力，最明显和自然的方法是均匀采样，并使用经验计数作为（无偏）估计。整个布尔立方体非常庞大，以至于均匀分布样本不是一种有效的采样策略。这无疑导致了“在水平p'上均匀”（对于p'稍大于组合维度p的[24]的采样策略），这将产生偏倚估计。0略大于组合维度p）的采样策略[24]，将产生偏倚估计。01.2. 本文的动机0鉴于上述情况，可以将[24]的方法视为使用对均匀测度影响力（方程（3））的偏倚估计。或者，可以将[24]中使用的采样分布隐含地定义为一种新的（加权）影响力度量（采样策略现在是这种新影响力度量的无偏估计）。这两种观点实际上是同一个问题的两个方面。然而，主要问题是偏倚估计的均匀测度影响力（第一观点：偏倚估计器-第二观点：新影响力度量）是否实际上保持了影响力大小的顺序。简而言之，在[24]中，在定义中使用的测度（以及在影响力更大的异常值的证明中使用的测度）与在经验估计中使用的测度之间存在断裂，但是可以通过使用一个与之相同的偏倚测度的影响力定义来加以调和。Inf(q)i [f] =Exxx∼µq(xxx)[I(f(xxx) ̸= f(xxx⊕i))],(4)̸⟨f1, f2⟩ :=�bbb∼Ωnf1(bbb)f2(bbb)µq(bbb)�i∈S bi−· q|S|−�i∈S bi+n−q+1−q∅89660作为用于估计影响力的采样方法。因此，我们被引导到了一个更系统和连贯的研究课题，称为“加权”（或偏倚）影响力。在第2.1节中，我们使用伯努利(q)测度µq来装备布尔立方体{0,1}n，即b i = 1的概率为q，b i =0的概率为1-q，其中包括均匀测度作为特殊情况（q = 1）。0为此，一个无偏估计器是：0其中I(∙)是指示函数，E[∙]是随机变量的样本均值。经验证据（见第4节），基于伯努利加权影响力的方法可以在更短的运行时间内实现类似的最优解，甚至在类似的运行时间内获得更好的结果。但更重要的是，我们在理论上证明了这种加权测度保持了影响力大小的必要顺序-见第3节。实际上，由于我们推导出的伯努利加权影响力的表达式包含均匀影响力作为特殊情况，并且我们涵盖了比[24]中相应部分更一般的数据特征（第3.2节），因此本文还提供了对均匀测度的更全面的理论分析。另一类测度，我们称之为汉明(k)，在一个固定大小（固定汉明范数）k的子集上放置相等的质量，并在其他地方放置零。其中的一个特殊情况应用于[24]中。对于这些测度，事实证明我们不需要从头开始进行分析。我们对伯努利(q)加权影响力的表达式自然地按级别分层（当然，[24]中的相应方程是特殊情况伯努利(0.5)）。这使我们能够通过检查每个级别的可行性/不可行性翻转的数量来获得（相应的加权影响力只是通过将这些计数除以给定级别中的顶点/子集的数量而产生的适当归一化）。然而，这在[24]中没有指出，也没有得出任何结果观察。此外，由于我们分析了更一般的数据假设集，我们也比仅仅通过检查[24]中的方程式得出的结论有更全面的画面。我们的主要贡献可以总结如下：0• 我们通过加权影响的概念来表征 MaxCon中离群值/内群值的影响。我们证明了数据中属于较大结构的点的加权影响通常对于理想和非理想情况都较小（详见第 3 节的定义）。请注意，我们的分析比 [24]中的分析更加通用。0• 我们通过实验证明了对 [24]的基本算法进行的修改，以适应伯努利测度的加权采样。在几个鲁棒拟合任务中，0我们的基于加权影响的变体是 [24]中版本的有效替代品。0我们还提出了一个猜想，根据我们推导出的方程的结构，可能将 MaxCon的固有结构复杂性与一些最近构建的困难问题的特征联系起来 - 详见第 3.1 节和第 3.2节。本文的目的是在新的影响定义和相应的估计策略下研究MaxCon。研究的重点是这些问题 -而不是生产“领先的”算法。01.3. 符号0我们采用以下符号：（1）粗体 bbb 表示布尔立方体 { 0 ,  1} n 中的一个顶点（一个 n 位向量），其第 i 个分量用 b i表示。（2）[ n ] = { 1 ,  2 ,  ∙ ∙ ∙  , n }。（3）L k := { bbb∈ { 0 ,  1 } n | ∥ bbb ∥ 1 = k } 表示布尔立方体 { 0 ,  1 } n的第 k 级，其中 0 � k � n。（4）L � k := { bbb ∈ { 0 ,  1 } n |∥ bbb ∥ 1 � k } 表示立方体 { 0 ,  1 } n 中低于第 k + 1级的级别。L k 的定义类似。（5）对于 b � b �b � ∈ L k ，B b � b � b � := { bbb ∈ { 0 ,  1 } n | ∆( bbb,b � b �b � ) = l,bbb ∈ L k − l , 1 � l � k − p − 1 } 表示由 b � b � b �确定的子立方体，其中 ∆( bbb,b � b � b � ) = |{ i : b i � = b � i }|是 bbb 与 b � b � b � 之间的汉明距离。（6）S j bbb ki := { l∈ [ n ] | b k i l = j }，其中 j = 0 ，1 。S 1 bbb ki 和 S 0bbb ki 分别表示与 bbb k i ∈ L k i相对应的内群和离群数据点的索引集合。（7）C n k表示具有 n 个元素的集合的 k 组合数，即 n ! /k ! / ( n − k)! ，其中 1 � k � n 。02. 加权影响0在本节中，我们将介绍单调布尔函数（伯努利）加权影响的定义（第 2.1 节）和（均匀汉明）加权影响的定义（第 2.2节）。02.1. 伯努利(q) 加权影响0令 Ω n = { 0 ,  1 } n 为具有伯努利测度 µ q 的离散 n维立方体，其中 µ ( { bbb : b i = 1 } ) = q ∈ (0 ,  1) ，即µ q ( bbb ) = q ∥ bbb ∥ 1 (1 − q ) n −∥ bbb ∥ 1。然后，我们可以在 Ω n 上定义一个度量 [19]，0对于在 Ω n 上定义的任何 f 1 ，f 2 ，奇偶函数0χ q S ( bbb ) :=q0形成空间 (Ω n ,  �∙ ,  ∙� ) 的一组基，其中 S 是一个子集0约定。ˆf q({i}) = ⟨f, χq{i}⟩ =�bbb∼Ωnf(bbb)qbi−q1−bi+µq(bbb).(5)Infqi [f] := µq({bbb : f(bbb) ̸= f(bbb⊕i)}),(6)q ∈ (0, 1), we sample half of a set of vertices {bbbj}⌊ h2 ⌋j=1 onthe Boolean cube Ωn according to the Bernoulli measureµq and then flip i-th bit in all bbbj to generate another halfInfi [f] = −hq(1 − q) j=1f(bbbj)q− q+µq(bbbj),123456780.10.20.30.40.50.60.70.80.91Exact weighted influencesEstimated weighted influences89670布尔函数 f 在第 i个变量上的加权一阶傅里叶系数可以表示为0对于在 Ω n 上定义的布尔函数 f ，第 i个变量对其的加权影响定义如下（参见 [14] 第 9 页）0其中ˆ f q ( { i } )和Inf q i [ f ]之间的关系为1：0定理2.1. 如果f：{0,1}^n →{0,1}是一个单调布尔函数，则Inf q i [ f ] =  − 1 / √0在实践中，计算（5）或（6）的确切值并不是非常现实，因为求和包含2^n个可能的bbb来评估。由于我们将利用所有加权影响力的顺序信息而不是它们的确切值来设计MaxCon的算法，因此获得质量较好的近似加权影响力就足够了。我们估计加权影响力的方法如下所示：给定样本大小h >p和权重02 � +1。这些顶点上评估了单调布尔函数f。因此，根据（5），（6）和定理2.1，我们估计加权影响力� Inf q i [ f ]为0其中bbb j的第i个分量是bbbj的第i个分量。注意：由于f的单调性，评估可以简化：如果f(bbb j)=0且b j,i=1，则f(bbb ⊕ i j)=0；如果f(bbbj)=1且b j,i=0，则f(bbb ⊕ ij)=1。图2显示了图1中所示数据点的估计和精确加权影响力，其中影响力通过最大影响力进行了归一化。有人可能会问-我们能推荐使用最佳的q吗？不幸的是，尽管我们可以说明玩具问题存在一个最优的q（例如见图3），但最佳的q可能是问题相关的。此外，测量的抽样是另一个复杂的问题。02.2. Hamming(k)加权影响力0将傅里叶变换（以及一般分析）限制在布尔切片（相等汉明范数级别）上实际上是一个更复杂的主题，最近才进行了研究。01 请参考补充材料中的证明。类似的结果可以在[14]（第20页）中找到，但没有证明。0图2.在图1中使用的所有数据点的归一化精确和估计加权影响力的比较，其中q设为0.375，样本数量h设为100。0图3.各种q的示例（3个异常值）用于分离MaxCon的内点和异常点。左图：所有数据点的影响力-前3个异常值。右图：分离函数（最小异常值和最大内点影响力之间的距离）：在分离方面，最佳选择的q值为0.46，并且对于这个数据集而言。注意：用于估计这个度量的抽样是一个完全不同的问题。0例如，参见[8，9，27] -可能会借助傅里叶理论来解释均匀立方体，但通常会回避切片上更复杂的傅里叶图像。同样，我们不会提及傅里叶系数。实质上，可以从过渡计数的期望的定义（从可行性到不可行性）通过翻转第i位（包括或不包括第i个数据点）直接得到切片集中度量的适当影响力定义（以及用于采样/估计策略的定义）。此外，由于这些过渡是按级别（切片）计数的，对于Bernoulli(q)影响力的适当公式（在第3节或[24]中给出的Bernoulli(0.5)度量），不需要重复复杂的推导/分析，而只需“挑选”所考虑级别下的相关计数，然后通过切片CNk上的总计数度量进行归一化。此外，由于我们只关心影响力的相对大小，可以省略归一化。03. 加权影响分析0在本节中，我们从理论上证明了属于较大结构的点具有较小的加权影响：直观地说，一个“内点”数据点的加权影响小于一个“异常值”数据点的加权影响。以下两个小节中所有理论结果的证明可以在补充材料中找到。在我们的分析中得出的结论是，可以使用加权采样来搜索MaxCon解，以获得影响力：可以有一定的保证bαl :=Infqi [f] = Cn−1pqp(1 − q)n−p−1 +k1(Cn−1p−�is=1Cks−1p)qp(1 − q)n−p−1+�is=0ks�l=p+1Cksl ql(1 − q)n−l−1.(10)00001089680估计具有正确的相对顺序以识别异常值。03.1. 伯努利(q) - 理想情况0真实数据集是“非理想”的，即数据集中存在多个结构，这些结构通常共享许多数据点；然而理想情况是一个有用的起点。0定义3.1. 假设 { bbb k i } n 0 i =1是单调布尔函数的上零点，其中 bbb k i ∈ L k i，p + 1 � k1 � k 2 � ∙ ∙ ∙ � k n 0 � n。那么如果 � i, j ∈ [ n 0 ]，| S 1 bbb ∩ S 1 bbb kj | � p，则 f 被称为理想函数；如果 � i, j ∈ [ n 0]，| S 1 bbb ki ∩ S 1 bbb kj | > p，则 f被称为非理想函数。也就是说，至少有两个结构有显著的重叠。我们定义 bbb α = ( b α 1 , ∙ ∙ ∙ , b α n )，其中0� 1，l ∈ S 1 bbb ki ∩ S 1b00，否则，对于 � l ∈ [ n ]，0是相对于 bbb k i 和 bbb k j 的伪上零点，其中 α := | S 1bbb ki ∩ S 1 bbb kj | 是伪上零点所属的级别。如果 f是非理想函数，则 { bbb α i } m 0 i =1（p + 1 � α 1 � α 2 � ∙∙ ∙ � α m 0 < k n 0）是所有伪上零点的集合。0定理3.1.（理想单一结构）如果 n0 = 1，即 f相对于单个最大上零点 bbb k 1 是理想函数，则对于 i ∈ S1 bbb k 1（内点），0Inf q i [ f ] = ( C n − 1 p −  C k 1 − 1 p ) q p (1  −  q ) n − p −1，(8)0对于 i ∈ S 0 bbb k1（异常值），0l = p +1 C k 1 l q l (1  −0(9) 这意味着 Inf q i 1 [ f ]  −  Inf q i 2 [ f ] = C k 1 − 1 pq p (1  − q ) n − p − 1 + � k 1 l = p +1 C k 1 l q l (1  −  q) n − l − 1  >  0，其中 i 1 ∈ S 0 bbb k 1，i 2 ∈ S 1 bbbk 1。0该定理表明，如果只有一个理想结构，即点要么是相对于该结构的内点要么是异常值，那么异常值的加权影响（所有异常值具有相同的影响）严格大于内点的加权影响（所有内点具有相同的影响）。0定理3.2.（理想多重结构）如果 n0 > 1，即 f是具有多个上零点的理想函数，则对于 � i ∈ ∩ n0 l =1 S i lbbb ki（如果非空），Inf q i [ f ] 是0简单地说，我们可以从对 i s的求和中看出，当数据点属于一个结构时（结构越大，减少越多），其影响力减小，并且对于数据点不属于的每个结构，其影响力增加（如果该结构较大，则增加更多）。这些增加和减少的权重不同（涉及 q的项），使关系复杂化。注意：对于多个结构，必须小心限定“内点”和“异常值”。这些只在与指定的单个结构相关时才有意义。对于该结构，所有“内点”对于其他结构来说实际上都是该结构的异常值。根据（10），数据点 i的影响力 Inf q i [ f ]如果它是相对于更多上零点的异常值（对于所有结构的数据异常值将具有最大的影响）。在这里，我们引入一个新的布尔立方体 { 0 , 1 } n 0，对于任何 i ∈ ∩ n 0 l =1 S i l bbbki，它对应于一个顶点 ( i 1 , i 2 , ∙ ∙ ∙ , i n 0 ) ∈ { 0 , 1 } n0。然后，Inf q i [ f ] 是在 { 0 , 1 } n 0上的一个实值布尔函数。为了简化表示，我们用 ˜ f q ( S iii) 表示 i ∈ ∩ n 0 l =1 S i l bbb ki 的 Inf q i [ f ]。0推论3.2.1. 影响力（10）具有以下顺序关系0�iii,jjj∈{0,1}n0，iii�jjj�˜fq(Siii)<˜fq(Sjjj)。（11）0注意只有当S•非空时，˜fq(S•)存在。03.2. 伯努利(q) - 非理想情况0给定一个伪上零bbbαi，我们引入记号Sjbbbαi={l∈[n]|bαil=1−j}，其中j=0，1。对于任何i∈(∩n0l=1Silbbbkl)∩(∩m0l=1Silbbbαn0+l)(如果非空)，用˜fq(Siii)表示i对f的影响。观察到，如果bbbαi0是相对于上零bbbki1和bbbki2的伪上零，那么数据点i相对于bbbki1和bbbki2是内点，那么它必定相对于bbbαi0是内点；如果i相对于任何上零是异常值，那么它相对于bbbαi0也是异常值。0定理3.3.如果f是非理想的，则加权影响力˜fq(Siii)由以下给出0(Cn−1p−�0Cks−1p+�0Cαs−1p)qp(1−q)n−p−10+ (�0l=p+1Cksl−�0l=p+1Cαsl)ql(1−q)n−l−1。0其中˜fq(S•)在S•=�时不存在。0证明这个定理的核心策略是对伪上零的数量进行归纳，并利用定理3.2。与理想情况类似，根据定理3.3，89690我们可以看到属于较大结构的点的加权影响力较小。显而易见的是，随着结构的增多，表达式变得非常复杂，由于它们之间可能的交集/重叠的组合数学问题而变得复杂-这使得内点/异常值的二分法度量（相对于任何给定的结构）变得复杂。这使我们猜测：0猜想3.1.（MaxCon和重叠间隙属性（OGP）的复杂性）在[11]（以及其中引用的作品）中，许多算法的计算复杂性与所谓的OGP相关。基本上，人们认为如果解空间高度聚类（这里的局部性是通过解的重叠来衡量），那么整个类别的算法将变得困难。简而言之，存在非常相似/具有大重叠的潜在解，或者相互之间相距很远（中间分隔很少）-是一个难以解决的问题的“标志”。我们猜测这对于可能的数据配置的MaxCon景观也是如此，并且上述情况（通过影响的视角）反映了这种复杂的数据实例场景如何体现在与所寻求的解决方案-影响力相关的属性中。0这个猜想特别有趣，因为最大独立集（在[11]中研究）与MaxCon之间存在联系-可以证明MaxCon解是由不可行的最小子集形成的（超）图的最大独立集（也是互补超图的最小顶点覆盖）。03.3. 均匀汉明度量影响力0考虑在定理3.1中定义的理想单一结构情况。首先，很容易看出对于理想单一结构，任何以大于组合维度的可行集合为起点，然后贪心地添加点，如果较大的集合仍然可行，将获得最大连通解。因此，这是一个容易的问题，具有明显的解决策略。但是，如果我们决定使用影响力，我们可以注意到根据方程（8），内点的影响力仅来自级别p和p+1之间的可行/不可行转换的计数。因此，对于在级别p+1以上的均匀汉明级别采样，由内点引起的可行性/不可行性转换将为零。换句话说，对于内点来说，该级别或以上的均匀汉明影响度将完全为零。由于对于相同的度量，异常值的影响将不为零，这似乎承诺了一种非常高效的采样策略-可以在首次采样中消除异常值，该采样显示了相关影响的计数-而无需继续进行完整的估计过程。当然，实际上，这对于真实数据来说太过理想化-它对我们在这里的严格假设非常脆弱。尽管如此，它确实暗示了一种较不脆弱的早期终止计数策略的有用性。0一旦某个计数达到统计显著性高于其他计数的程度，而不是总是使用固定数量的样本：这是未来的研究课题。现在考虑理想的多重结构设置。从方程10可以看出，作为某个结构的内点所获得的影响（第一项）仅在级别p和p+1之间累积。减法是由于可行性转换“未发生”，因为添加内点的子集仍然在同一个结构内）。因此，再次采样超过级别p将不会“看到”那些计数。但是由于一个结构的内点是另一个结构的离群点（我们假设没有显著的重叠）：因此，任何结构的内点的影响不会为零-与单一结构的情况不同，因为所有结构都是（所有）其他结构的离群点，因此从方程的第二项中累积影响。还可以很容易地看出，只要级别“不太高”（高于最大结构），Hamming采样的影响将是一个合适的指南（较大结构的内点的影响将较小）。（在计算该结构的影响时，最大结构在i s =0的求和中被排除。）更多讨论请参见补充材料。04. 使用伯努利测度的实验0在本节中，我们通过实验证明伯努利加权影响行为通常与我们的分析预测一致（基本上保留了内点/离群点分离的正确排序），在合成数据集和真实数据集上进行了几个鲁棒模型拟合任务。我们使用的主要算法在补充材料中介绍（算法1-遵循[24]）。为了减少丢失真正的内点的风险，我们还在算法1的最后一步实现了局部扩展（请参见补充材料中的算法2），该算法也遵循[24]的策略。注意：[24]的算法使用固定的Hamming级别进行均匀采样（因此隐含地提供了基于Hamming测度的结果），尽管在那里它被解释为估计均匀测度影响的一种有偏方法，而不是像这里一样作为一种新的影响测度。[24]经验性地优化了他们的采样级别-因此我们在这里不使用Hamming采样进行实验。作为比较，我们使用：RANSAC[10]，Lo-RANSAC [6]，A�-NAPA-DIBP[2]（我们只使用它来为低离群点率的合成数据生成基准解），MBF [24]，L1[20]。我们使用加权影响的方法简称为WI。实验使用Matlab R2020b在一台配有Intel(R) i7-8700K CPU和32GBRAM的计算机上进行。04.1. 鲁棒线性回归0加权影响估计中参数的分析：评估加权影响（7）需要两个参数：样本概率q和样本大小h。在这里，我们使用合成数据研究q和h的影响F(rrres,rrrex) =1k(k + 1)�z∈R(rrres)∩R(rrrex)|zrrres − zrrrex|,̸89700图4.二维鲁棒线性回归的比较结果：SF距离随不同的（左）样本概率q和（右）样本数量h的变化。所有实验运行了50次。0在二维线拟合问题上进行了实验。我们在一条直线周围生成n =15个点，并随机选择30%的点作为离群点，这些离群点受到范围为[-4, -0.1)∪(0.1,4]的均匀分布噪声的扰动。其余点受到[-0.1,0.1]的均匀分布噪声的扰动。在本小节的所有实验中，我们将内点阈值ε设置为0.1。设rrr es和rrrex分别为所有点的估计加权影响（由（7）计算）和精确加权影响（由（6）计算）的前k个（按降序排列），其中k由A�-NAPA-DIBP找到的离群点数量确定。我们通过归一化的Spearman Footrule（SF）距离[7]来衡量rrr es和rrrex之间的差异。用3 rrr •包含的元素集合表示为R(rrr•)，元素z在rrr •中的位置表示为z rrr •。rrr es和rrrex之间的归一化SF距离由以下公式给出：0当z  �∈ R ( rrr • )时，我们使用k  + 1来表示z rrr •。SF距离越小，rrr es和rrrex共享相同的前k个加权影响的可能性越大。对于固定数量的样本（h =300，1000，3000），我们将概率q从0.1变化到0.9；对于固定概率（q =0.3，0.5，0.7），我们将样本数量从100变化到5000。结果如图4所示，从中我们可以看出当q ∈(0.2，0.4)时，SF距离相对较小；而对于更多的样本，SF距离较小。在接下来的实验中，我们将设置概率q在(p + 1) /n和0.4之间，样本大小h在100到500之间，以保持估计精度和运行时间之间的权衡。请注意，SF距离无法区分在rrres或rrrex中共享相同加权影响的点。这些实验还显示了迭代重新估计加权影响的必要性，因为一次评估所有加权影响不能完全匹配精确加权影响的顺序。02由于精确加权影响需要指数时间来计算，因此我们选择了非常低的数据点数量，随着n的增加。3•表示es或ex。0图5.对8维鲁棒线性回归的比较结果：比较（左）一致性误差和（右）运行时间与不同数量的异常值。通过A *-NAPA-DIBP找到地面真值。所有实验重复50次。0相对性能：在这个实验中，我们考虑了8维线性回归问题，其中合成数据的生成方式与我们在上一个实验中相同。数据点的数量n选择为200，我们将异常值的数量从10变化到40，这是由于A *-NAPA-DIBP生成地面真值的计算时间限制。从图5中，我们可以发现伯努利加权影响和原始MBF都能够达到最优解，而伯努利加权方法通常比MBF更快。局部扩展的影响在补充材料中进行了比较。04.2. 线性化基础矩阵估计0我们在本小节中还在KITTIOdometry数据集[12]的序列“00”中对基于伯努利加权影响的方法进行了进一步测试。对于两个给定的图像对，使用VLFeat工具箱[26]检测和匹配了SIFT关键点[18]。假设ppp1，ppp2是匹配的两个特征，其中ppp i = (x i , y i , 1)T是视图i中的坐标，i =1，2，那么每个对应关系对基础矩阵FFF ∈ R 3 ×3提供了一个线性约束，即ppp T 1 FFFppp 2 =0。在这个实验中，我们考虑了基础矩阵估计的线性化版本[13]，其中所有图像对的内点阈值都设置为0.02。RANSAC和Lo-RANSAC的迭代次数设置为与WI的运行时间相匹配。我们在表1中报告了平均（运行所有算法20次）的一致性和运行时间。观察到：（1）尽管L1通常非常快，但找到的一致性大小小于基于伯努利的方法WI；（2）RANSAC和Lo-RANSAC被允许与WI运行相同的时间，但在返回的一致性大小方面，WI仍然更好；（3）WI几乎与MBF具有相同的一致性大小，但时间成本较低（在图像对198-201、417-420、579-582中，WI的平均一致性大小略高于MBF）。更多细节请参见补充材料。04.3. 单应性估计0这个实验考虑了单应性估计和线性残差模型。对于由{ (xxx i,yyy i ) }表示的两个视图的一组对应关系，其中104-108104-108104-108198-201198-201198-201417-420417-420417-420579-582579-582579-582738-742738-742738-74289710表1. 线性化基础矩阵估计结果. RANSAC和Lo-RANSAC的运行时间设置为WI的运行时间.0L1共识 252 264 317 497 429 时间 (s) 0.85 0.07 0.04 0.06 0.090RANSAC共识 266.55 284.00 353.30 497.05 432.60 (262,270) (283,285) (351,356) (492,503)(428,440)0Lo-RANSAC共识 268.55 284.90 355.25 501.45 439.35 (266,273) (284,287) (354,356) (496,506)(432,443)0MBF共识 271.70 287.70 358.95 507.15 444.20 (268,274) (284,289) (357,360) (503,510) (442,446)时间 (s) 3.17 1.88 2.36 3.61 3.19 (2.65,4.41) (1.65,2.47) (1.96,2.66) (3.17,4.36) (2.68,3.56)0WI共识 271.55 288.35 359.05 507.65 444.15 (269,274) (286,289) (356,360) (502,510) (442,446) 时间(s) 2.64 1.75 2.10 3.42 3.09 (2.26,3.31) (1.43,2.03) (1.82,2.51) (2.93,4.15) (2.80,3.57)0对于xxx i ,yyy i  ∈  R 2 , 让  ˜ xxx i  = ( xxx i ,  1) T ,  ˜ yyyi  = ( yyy i ,  1) T 是齐次表示, 齐次变换矩阵  H H H  ∈  R3 × 3 的估计是为了找到一个矩阵  H H H 使得  ˜ yyy i  =