1. 战略分类中的学习复杂性从理论到实践的核心挑战在机器学习领域我们常常面临一个核心问题一个算法需要多少数据才能学得好以及在学习过程中它最多会犯多少错误这两个问题分别由PAC学习Probably Approximately Correct Learning理论和在线学习Online Learning理论来回答。PAC学习关注样本复杂度——为了以高概率学到一个错误率不超过ε的模型最少需要多少独立同分布的样本。在线学习则关注错误界限——在与环境序列交互的整个过程中算法累积犯错的次数上限。这两个指标是衡量学习算法数据效率和在线性能的理论基石。然而现实世界并非静态。在许多关键应用中如信贷审批、内容推荐或安全检测被分类的个体我们称之为“智能体”并非被动接受判决。他们会观察学习器部署的规则并策略性地调整自己的特征表示以期获得更有利的分类结果例如将贷款申请从“拒绝”变为“批准”。这就是战略分类Strategic Classification研究的问题。它打破了传统机器学习中“特征分布固定”的假设引入了博弈和激励的维度。在战略分类中学习器的挑战陡然增加。你不仅要找到一个能拟合当前数据的假设还要预见到这个假设本身会如何改变未来的数据分布。这就引出了本文探讨的核心在这种动态博弈环境下学习的理论极限发生了什么变化具体来说我们关心在不同的信息反馈设置下样本复杂度和错误界限如何随假设类的丰富度即假设类大小 |ℋ|增长。为什么这个问题重要因为答案直接决定了算法设计的可行性。如果样本复杂度是 |ℋ| 的对数级那么即使假设空间很大我们也能用相对较少的数据进行学习。如果是线性级甚至更高那么对于庞大的假设类学习可能就变得不切实际。本文的工作正是系统性地剖析了不同信息结构如何影响这一复杂性为设计既鲁棒又高效的战略学习算法划清了理论边界。2. 问题框架与核心概念解析要深入理解战略分类中的学习复杂性我们首先需要建立一个清晰、形式化的问题模型。这就像在下一盘复杂的棋我们必须先定义棋盘、棋子和行棋规则。2.1 战略分类的基本交互协议想象一个重复进行的分类游戏。在每一轮t环境给出一个智能体其本质是一个三元组(x_t, u_t, y_t)。x_t ∈ 是智能体的原始特征向量例如原始的信用分数、简历内容。u_t描述了智能体的操纵能力。在最常见的“球型操纵”模型中u_t就是一个半径r_t表示智能体可以将其特征修改到以x_t为中心、r_t为半径的“球”内的任何一点。更一般地u_t可以定义为一个允许的操纵集合U(x_t) ⊆ 。y_t ∈ {1, -1}是智能体的真实标签例如是否具有良好的还款能力。学习器在观察到部分信息后需要选择一个分类器假设f_t ∈ ℋ来部署。这里的关键在于信息反馈的时机它定义了四种主要设置(C, F)C代表选择f_t前能看到什么x看到x_t或⊥什么都看不到。F代表得到反馈后能看到什么Δ只看到操纵后的特征Δ_t、(x, Δ)看到原始和操纵后的特征或⊥什么都看不到。例如(x, Δ)是最宽松的设置先看原始特征再决策决策后能看到智能体是如何操纵的。(⊥, ⊥)则是最严苛的盲选分类器且事后也看不到智能体具体做了什么只能知道自己的预测ŷ_t是对是错。智能体在知道f_t后为了获得正标签ŷ_t 1会从其操纵集合U(x_t)中选择一个点Δ_t进行报告通常选择能使其被f_t判为正且代价最小的点例如离x_t最近的点。学习器收到反馈根据F的设置可能是Δ_t,(x_t, Δ_t)或什么都没有并得知自己的预测ŷ_t f_t(Δ_t)是否正确即是否等于y_t。这个协议精准地刻画了战略交互的核心学习器的决策会影响智能体的行为特征操纵而学习器只能通过有限的反馈来观察和适应这种影响。2.2 核心复杂度度量错误界限与样本复杂度在这个动态博弈中我们如何衡量一个学习算法的好坏我们引入两个核心指标。定义 2.1在线学习的错误界限对于一个给定的设置(C, F)和学习算法考虑任何由某个目标假设h* ∈ ℋ能完美分类的序列S即可实现序列。算法在该序列上犯的错误总数记为ℳ_(S)。假设类(ℋ, )在该设置下的错误界限MB_{C,F}定义为存在某个算法能使其在所有可实现序列S上的错误数都不超过的最小整数B。简单来说错误界限是最坏情况下任何在线学习算法都至少会犯的错误数也是存在某个算法能保证犯的错误不超过的数。它衡量了在线环境下问题的内在难度。定义 2.2PAC学习的样本复杂度在分布设定中智能体从一个未知分布中独立同分布地采样。学习器的目标是经过T轮交互即看到T个样本后输出一个最终分类器f_out使其在分布上的战略损失即期望错误率足够小。 对于精度ε和置信度δ样本复杂度SC_{C,F}(ε, δ)定义为存在一个算法对于任何存在零损失目标假设h*的分布当使用至少m个样本时能以至少1-δ的概率保证输出分类器的损失≤ ε。这个最小的m就是样本复杂度。样本复杂度回答了“需要多少数据才能学得好”的问题。它与错误界限紧密相关通常可以通过标准转化技术从一个算法的错误界限推导出相应的PAC样本复杂度上界。2.3 信息反馈的层级与难度排序直观上学习器获得的信息越多问题应该越简单。我们的理论分析证实了这一点并给出了严格的难度排序。对于错误界限和样本复杂度均有MB_{x,Δ} ≤ MB_{⊥,(x,Δ)} ≤ MB_{⊥,Δ} ≤ MB_{⊥,⊥}SC_{x,Δ} ≤ SC_{⊥,(x,Δ)} ≤ SC_{⊥,Δ} ≤ SC_{⊥,⊥}这个排序非常符合直觉(x, Δ)是最简单的先知特征再决策事后还能看到操纵结果信息最全。(⊥, (x, Δ))次之虽然决策前是盲选但事后能同时看到原始特征和操纵结果仍有丰富信息用于更新信念。(⊥, Δ)和(⊥, ⊥)更难决策前盲选且事后信息更少。(⊥, ⊥)是最极端的情况几乎是在“摸黑”学习。这个排序为我们后续分析不同设置下的算法设计和下界证明提供了清晰的框架。我们接下来的探索将围绕一个核心问题展开在战略分类中我们能否像经典非战略学习那样实现对假设类大小 |ℋ| 的对数依赖还是说战略行为会迫使依赖关系恶化到线性甚至更高3. 球型操纵下的算法设计与复杂性分析“球型操纵”是一个重要且具有良好结构的特例。智能体的操纵能力被限制在以原始特征x为球心、某个未知半径r为半径的球内。这个结构带来一个关键性质对于给定的x和假设h我们可以定义一个距离d(x, h)即x到h的正类区域_{h,}的最短距离。如果d(x, h) ≤ r则该智能体可被h正确分类为正反之则为负。这个距离度量在算法设计中起到了核心作用。3.1 设置 (x, Δ)信息最全场景下的高效学习在这个设置下学习器在决策前能看到x_t决策后能看到Δ_t。对于球型操纵知道Δ_t等价于知道了x_t和r_t因为可以从x_t和Δ_t反推最小所需的操纵距离。因此这几乎是信息最丰富的场景。3.1.1 在线学习战略版“折半”算法经典在线学习中的“折半算法”Halving Algorithm通过维护一个与历史一致的假设集合版本空间并在每一轮采用版本空间中多数假设的投票结果作为预测。一旦预测错误所有投错误票的假设都可以被排除从而保证每犯一次错版本空间至少缩小一半错误界限为log(|ℋ|)。在战略分类中我们无法直接知道其他假设的“投票”因为智能体只针对当前部署的f_t进行最优操纵。然而球型操纵结构提供的距离排序让我们能够绕过这个障碍。我们设计了战略折半算法。算法 1战略折半算法初始化版本空间VS ℋ。对于每一轮t1 to T a. 观察原始特征x_t。 b. 计算版本空间VS中每个假设h到x_t的距离d(x_t, h)。 c. 选择一个假设f_t ∈ VS使得d(x_t, f_t)是上述距离集合的中位数。 d. 部署f_t获得反馈ŷ_t和真实标签y_t。 e. 如果预测错误 (ŷ_t ≠ y_t) * 如果真实标签是正 (y_t 1)说明f_t将本应判正的样本判负了。这意味着d(x_t, f_t) r_t。而目标假设h*必须满足d(x_t, h*) ≤ r_t。因此所有满足d(x_t, h) ≥ d(x_t, f_t)的假设h都不可能是h*将其从VS中剔除。 * 如果真实标签是负 (y_t -1)说明f_t将本应判负的样本判正了。这意味着d(x_t, f_t) ≤ r_t。而目标假设h*必须满足d(x_t, h*) r_t。因此所有满足d(x_t, h) ≤ d(x_t, f_t)的假设h都不可能是h*将其从VS中剔除。为什么选择中位数这是算法的精妙之处。因为d(x_t, f_t)是中位数所以无论剔除哪一边大于等于或小于等于中位数的假设我们都保证至少能剔除当前版本空间中至少一半的假设。这就复现了经典折半算法的核心逻辑。实操心得距离计算是关键算法的高效执行依赖于快速计算d(x_t, h)。对于许多常见的假设类如线性分类器、决策树桩在欧氏空间下计算点到正区域的距离可能有闭式解或高效算法。在实际实现时需要根据具体的假设类ℋ和距离度量d来优化这部分计算否则可能成为性能瓶颈。定理 2.1表明战略折半算法实现了MB_{x,Δ} ≤ log(|ℋ|)的错误界限。这与经典非战略在线学习的对数界限一致说明在信息充分的球型操纵下战略行为并未增加在线学习的渐进难度。3.1.2 PAC学习从错误界限到样本复杂度在PAC设定下我们可以利用标准技术Gallant, 1986将在线算法的错误界限转化为样本复杂度上界。基本思想是反复运行在线算法直到某个假设在连续O((1/ε) log(log(|ℋ|)/δ))轮中都没有被淘汰然后输出这个假设。通过概率分析可以证明这个输出假设的期望误差不超过ε。定理 2.2表明通过结合战略折半算法和上述转化技术我们可以实现样本复杂度SC_{x,Δ}(ε, δ) O( (log|ℋ|/ε) log(log|ℋ|/δ) )。这同样是对数依赖仅比经典PAC界限多一个对数对数因子在理论上是非常高效的。3.2 设置 (⊥, (x, Δ))决策前信息缺失的挑战当学习器在选择f_t之前无法看到x_t时情况发生了根本变化。战略折半算法失效了因为我们无法计算距离的中位数来指导f_t的选择。3.2.1 在线学习线性错误界限的下界我们首先通过一个精心构造的例子例2.1证明任何确定性算法在最坏情况下都可能遭受|ℋ| - 1次错误。这个例子构造了一个星形度量空间和单点假设类使得对手可以根据学习器选择的f_t来生成一个让学习器犯错且几乎无法获得信息的样本。更令人惊讶的是定理 2.3表明即使允许学习器使用随机化算法错误界限的下界仍然是Ω(|ℋ|)。证明的核心是设计一个对抗性环境使得在学习器确定目标假设h*之前每一轮都有大约1/|ℋ|的概率犯错且只有犯错时才能获得信息。这意味着在最坏情况下学习器本质上需要逐个“试错”所有假设错误数线性于假设类大小。然而一个细微的区别在于时间。达到Ω(|ℋ|)错误需要T Ω(|ℋ|^2)轮。我们提出了一个随机化算法算法17基于乘性权重更新思想其期望错误数上界为min(√(4 log(|ℋ|)T), |ℋ|-1)。当T约等于|ℋ|^2时上下界匹配在对数因子内。这说明虽然错误总数可能是线性的但错误发生的速率可以很慢。3.2.2 PAC学习非适定算法与对数平方样本复杂度在PAC学习中我们关心的是最终输出分类器的质量。一类常见的算法是适定算法它保证输出f_out ∈ ℋ。然而定理 2.5证明对于适定算法存在问题实例使得样本复杂度下界为Ω(|ℋ|/ε)即线性依赖。这意味着要获得好的适定输出可能需要与假设类大小成比例的样本量。这迫使我们去考虑非适定算法即允许输出不在ℋ中的假设。我们设计了算法 2其核心思想是在每一轮从当前版本空间VS中随机抽取k个假设k从1, 2, 4, ... 等几何级数中随机选取并将它们的“或” (∨) 作为本轮部署的假设f_t。f_t预测为正当且仅当至少有一个被抽中的假设预测为正。如果f_t犯错则根据错误类型误报或漏报和观察到的x_t像战略折半算法一样更新版本空间。最终从某个中间轮次的版本空间中随机抽取两个假设输出它们的“或”。为什么输出两个假设的“或”这是为了应对战略分类中正负样本的不对称性智能体总想被分为正。输出单个假设可能对正例过于保守。输出两个假设的“或”扩大了正类区域提高了对正例的召回率从而在理论上能补偿信息缺失带来的损失。定理 2.6表明通过结合算法2和一个标准的置信度提升技术我们可以实现样本复杂度SC_{⊥,(x,Δ)}(ε, δ) O( (log²(|ℋ|) log(1/δ)) / ε * log(1/δ) )。这是一个仅对数平方依赖的样本复杂度远优于适定算法的线性下界。这揭示了在战略PAC学习中放弃“适定性”这一约束可以带来巨大的样本效率提升。3.3 设置 (⊥, Δ) 与 (⊥, ⊥)信息极度受限的困境这两个设置比(⊥, (x, Δ))更难因为反馈信息更少。(⊥, Δ)只能看到操纵后的特征(⊥, ⊥)则什么都看不到。3.3.1 在线学习由于难度递增(⊥, (x, Δ))设置下的线性错误下界Ω(|ℋ|)自然适用于这两个更难的设置。因此MB_{⊥,Δ}和MB_{⊥,⊥}也都是Ω(|ℋ|)。3.3.2 PAC学习在(⊥, Δ)设置下算法2不再适用因为更新版本空间需要x_t信息。我们注意到迄今为止讨论的PAC算法都属于保守算法它们只利用犯错轮次的信息进行更新。在正确轮次所有假设的预测要么正确要么未知很难利用。定理 2.7证明对于保守算法存在实例使得样本复杂度下界为Ω(|ℋ|/ε)。这留下一个开放问题是否存在非保守的算法能利用正确轮次的信息来突破这个线性下界目前尚未可知。在(⊥, ⊥)设置下问题简化为一个随机多臂赌博机中的最佳臂识别问题。每个假设可以看作一个“臂”学习器选择部署哪个假设就像拉哪个臂得到的奖励是二元的预测正确与否。定理 2.8通过将其归约到随机线性赌博机问题并利用信息论工具证明了样本复杂度下界也是Ω(|ℋ|/ε)。同时通过将在线学习的线性错误界限转化为PAC界限可以得到一个O(|ℋ|/ε)的上界忽略对数因子因此该设置的样本复杂度是Θ̃(|ℋ|/ε)。4. 非球型操纵结构缺失导致的普遍困难球型操纵的优雅之处在于其诱导的距离全序关系这为高效学习提供了可能。然而一旦离开这个结构化领域进入一般的非球型操纵情况急转直下。在非球型操纵中对于给定的x不同假设之间不再有一个清晰的“距离”排序。智能体的操纵集合U(x)可以是任意形状。这意味着即使我们观察到x_t和Δ_t也很难推断出其他假设会对这个x_t作何预测。定理 2.9给出了一个强有力的负面结果即使在最简单的(x, Δ)设置下决策前知x决策后知Δ也存在非球型操纵的问题实例其PAC样本复杂度下界为Ω(|ℋ|/ε)。证明的构造很巧妙让所有智能体的原始特征x_t都相同例如全为0。这样即使事先观察到x_t也提供不了任何信息来区分不同假设。学习器本质上是在盲猜哪个假设能应对各种不同的操纵集合。由于(x, Δ)是最简单的设置且任何错误界限都可以通过标准技术转化为样本复杂度下界我们得到以下推论推论 2.1存在非球型操纵的问题实例使得对于所有四种信息反馈设置(C, F)其错误界限都是Ω(|ℋ|)样本复杂度都是Ω(|ℋ|/ε)。这个结论意义重大。它表明操纵的结构性信息对于高效学习至关重要。如果没有像“球型”这样的良好几何结构它隐含了单调性和距离比较那么即使拥有最丰富的信息反馈战略分类的学习复杂度也会退化到与假设类大小成线性关系这在大假设类下是难以承受的。5. 无限假设类与可学习性前面的讨论聚焦于有限假设类|ℋ| ∞。对于无限假设类|ℋ| ∞我们不能再依赖|ℋ|来度量复杂度而是需要更精细的组合度量如VC维用于PAC学习和Littlestone维用于在线学习。一个核心问题是在经典设定中“可学习”的假设类在战略分类中是否仍然“可学习”我们考虑一个用图模型表示的更一般的操纵设定每个特征x是图中的一个节点从x到x的有向边表示智能体可以从x操纵到x。我们假设图的最大出度为k这反映了智能体操纵能力的有限性。这个假设不仅是现实的而且理论上是必要的因为放松它会导致即使对非常简单的假设类也无法学习。我们研究了三种反馈设置完全信息反馈学习器在决策前知道x_t决策后知道Δ_t和y_t并且知道整个操纵图。这是最理想的情况。事后特征反馈学习器决策前不知道x_t决策后可能知道x_t或Δ_t或两者但仍知道操纵图。未知图反馈学习器知道x_t和Δ_t但不知道真实的操纵图只知道它来自一个有限的图类。5.1 主要结论概述令人振奋的是在所有这些设置下答案基本上是肯定的经典可学习性意味着战略可学习性但代价是学习复杂度会增加一个与操纵能力k相关的因子。完全信息反馈已知图PAC学习战略VC维为Θ̃(d₁ log k)其中d₁是原假设类的标准VC维。样本复杂度为Õ((d₁ log k)/ε)。这意味着操纵使样本复杂度增加了约log k倍。在线学习战略Littlestone维为Θ(d₂ log k)其中d₂是标准Littlestone维。错误界限为O(d₂ log k)。同样增加了log k因子。算法在PAC中对战略损失经验风险最小化ERM即可。在在线中可以通过运行多个标准在线算法作为“专家”并对它们进行加权多数投票将标准在线算法转化为战略在线算法。事后特征反馈已知图PAC学习样本复杂度与完全信息反馈相同。因为即使决策前不知道x_t通过实施“全正”或“全负”分类器作为探测也能间接获得所需信息。在线学习情况更复杂因为探索获取信息和利用做出正确预测无法分离。我们设计了另一种转化算法但得到的最优错误界限是O(d₂ k)。注意这里对k的依赖是指数级恶化的从log k到k这解决了Ahmadi等人2023年提出的一个开放问题。未知图反馈PAC学习可实现情况主要挑战是无法获得每个图-假设对损失的无偏估计。我们通过使用期望度数作为正则项来解决。通过寻找经验损失为零且经验度数最小的图-假设对我们可以实现样本复杂度Õ((d₁ log k k log ||)/ε)。只要图类不是太大这仍然是有效的。这些结果表明尽管战略行为增加了学习难度但只要操纵能力是有限的有界度k并且我们拥有关于操纵结构的部分知识即使是有限的候选图集那么从经典学习到战略学习的扩展在复杂度上通常是可控的不会导致不可学习。6. 讨论、实践启示与开放问题6.1 核心发现总结我们的研究系统性地描绘了战略分类中学习复杂性的版图信息是关键学习器在决策前后能获得的信息量从根本上决定了学习的难度。从(x, Δ)的对数复杂度到(⊥, (x,Δ))的混合结果在线线性、PAC对数平方再到更受限设置的线性复杂度信息层级清晰对应难度阶梯。结构是救星在“球型操纵”这种具有良好几何结构的设定下即使信息受限我们仍能设计出巧妙的算法如战略折半、随机“或”假设来获得优于线性的复杂度。这提示我们在实际应用中对智能体操纵行为施加或假设合理的结构约束如基于距离的成本是设计可学习系统的关键。适定性可能是代价在(⊥, (x,Δ))的PAC设置中适定算法需要线性样本而非适定算法可以达到对数平方样本。这告诉我们为了应对战略环境有时必须跳出“从假设类中选一个”的思维定式考虑更复杂的聚合输出形式。无限类的希望对于无限假设类只要操纵能力有限有界度经典的可学习性基本上能延续到战略环境中尽管需要付出一个与操纵能力k相关的额外代价。6.2 对算法设计与评估的启示反馈机制设计系统设计者应尽可能让学习器在决策前观察到原始特征x并在决策后获得操纵反馈Δ。这能最大程度降低学习复杂度。例如在贷款审批中要求申请人提供历史信用记录x并在审批后记录其最终提交的材料Δ。假设类的谨慎选择面对战略智能体假设类的复杂度VC维、Littlestone维依然主导学习难度但还需考虑其与预期操纵结构的交互。选择与潜在操纵模式“对齐”的假设类可能更高效。探索非适定预测器当信息受限时考虑输出假设的聚合如投票委员会、假设的“或”/“与”而不仅仅是单个假设可能会带来显著的性能提升。评估基准在评估战略学习算法时除了传统泛化误差还应考虑其在不同的信息反馈设置下的错误界限和样本复杂度。我们的理论下界可以作为算法性能的基准。6.3 重要开放问题我们的工作开启了许多未来研究方向不可知情形本文聚焦于“可实现”设定存在零误差假设。在更现实的“不可知”设定中不存在完美假设我们的目标是与最佳假设的损失竞争。这里的样本复杂度和遗憾界如何初步结果表明对于有限类类似的下界可能仍然成立但上界需要新的算法。设置(⊥, Δ)的最优样本复杂度我们给出了保守算法的线性下界但最优算法可能非保守的样本复杂度是否可以是亚线性这仍然悬而未决。更一般的操纵结构除了有界度图模型还有其他可以表征现实世界操纵、同时又能保证可学习性的结构假设吗例如基于某种度量的 Lipschitz 连续性假设。计算效率本文的算法许多是计算高效的如战略折半但一些算法如处理未知图的算法可能涉及对图类的搜索。如何设计计算高效的、适用于大规模假设类和图类的战略学习算法是通向实际应用的关键。与稳健学习的联系战略分类与对抗性稳健学习有深刻联系。智能体的操纵可以看作一种针对已部署分类器的、有界的对抗性扰动。两者理论工具的交叉融合可能催生新的见解。战略分类将机器学习从被动的模式识别推向了一个与动态环境、智能体进行博弈的前沿领域。理解其学习复杂性不仅是理论上的突破更是构建在真实世界中可靠、公平、且能抵御操纵的智能系统的基石。本文的工作为这片充满挑战的领域打下了一块坚实的理论基石。