本文研究了数据估值对嘈杂模型性能得分的鲁棒性。特别是，我们发现广泛使用的随机梯度下降的固有随机性会导致现有的数据值概念（例如，沙普利值和剩余错误），以在不同运行中产生不一致的数据值排名。为了应对这一挑战，我们首先提出一个正式的框架，在该框架中可以测量数据值概念的鲁棒性。我们表明，Banzhaf的价值是一个源自合作游戏理论文献的价值概念，它在所有半估计中实现了最大的鲁棒性 - 一类价值概念满足ML应用程序所带来的重要属性。我们提出了一种算法，以根据最大样本重用（MSR）原理有效地估计Banzhaf值。我们得出了Banzhaf值近似的下限样品复杂性，并表明我们的MSR算法的样品复杂性几乎与下限匹配。我们的评估表明，Banzhaf值的表现优于几个下游ML任务（例如使用加权样品学习和嘈杂的标签检测）的现有基于半半数的数据值概念。总体而言，我们的研究表明，当基础ML算法是随机的时，Banzhaf值是基于半杂志的数据值方案的有前途的替代方法，因为其计算优势和能力可靠地区分数据质量。

Data valuation, especially quantifying data value in algorithmic prediction and decision-making, is a fundamental problem in data trading scenarios. The most widely used method is to define the data Shapley and approximate it by means of the permutation sampling algorithm. To make up for the large estimation variance of the permutation sampling that hinders the development of the data marketplace, we propose a more robust data valuation method using stratified sampling, named variance reduced data Shapley (VRDS for short). We theoretically show how to stratify, how many samples are taken at each stratum, and the sample complexity analysis of VRDS. Finally, the effectiveness of VRDS is illustrated in different types of datasets and data removal applications.

我们开发了一种新的原则性算法，用于估计培训数据点对深度学习模型的行为的贡献，例如它做出的特定预测。我们的算法估计了AME，该数量量衡量了将数据点添加到训练数据子集中的预期（平均）边际效应，并从给定的分布中采样。当从均匀分布中采样子集时，AME将还原为众所周知的Shapley值。我们的方法受因果推断和随机实验的启发：我们采样了训练数据的不同子集以训练多个子模型，并评估每个子模型的行为。然后，我们使用套索回归来基于子集组成共同估计每个数据点的AME。在稀疏假设（$ k \ ll n $数据点具有较大的AME）下，我们的估计器仅需要$ O（k \ log n）$随机的子模型培训，从而改善了最佳先前的Shapley值估算器。

The Shapley value (SV) is adopted in various scenarios in machine learning (ML), including data valuation, agent valuation, and feature attribution, as it satisfies their fairness requirements. However, as exact SVs are infeasible to compute in practice, SV estimates are approximated instead. This approximation step raises an important question: do the SV estimates preserve the fairness guarantees of exact SVs? We observe that the fairness guarantees of exact SVs are too restrictive for SV estimates. Thus, we generalise Shapley fairness to probably approximate Shapley fairness and propose fidelity score, a metric to measure the variation of SV estimates, that determines how probable the fairness guarantees hold. Our last theoretical contribution is a novel greedy active estimation (GAE) algorithm that will maximise the lowest fidelity score and achieve a better fairness guarantee than the de facto Monte-Carlo estimation. We empirically verify GAE outperforms several existing methods in guaranteeing fairness while remaining competitive in estimation accuracy in various ML scenarios using real-world datasets.

沙普利价值是衡量单个特征影响的流行方法。尽管Shapley功能归因是基于游戏理论的Desiderata，但在某些机器学习设置中，其某些约束可能不太自然，从而导致不直觉的模型解释。特别是，Shapley值对所有边际贡献都使用相同的权重 - 即，当给出大量其他功能时，当给出少数其他功能时，它具有相同的重要性。如果较大的功能集比较小的功能集更具信息性，则此属性可能是有问题的。我们的工作对沙普利特征归因的潜在局限性进行了严格的分析。我们通过为较小的影响力特征分配较大的属性来确定Shapley值在数学上是次优的设置。在这一观察结果的驱动下，我们提出了加权图，它概括了沙普利的价值，并了解到直接从数据中关注哪些边际贡献。在几个现实世界数据集上，我们证明，与沙普利值确定的功能相比，加权图确定的有影响力的特征可以更好地概括模型的预测。

基于Shapley值的功能归因在解释机器学习模型中很受欢迎。但是，从理论和计算的角度来看，它们的估计是复杂的。我们将这种复杂性分解为两个因素：（1）〜删除特征信息的方法，以及（2）〜可拖动估计策略。这两个因素提供了一种天然镜头，我们可以更好地理解和比较24种不同的算法。基于各种特征删除方法，我们描述了多种类型的Shapley值特征属性和计算每个类型的方法。然后，基于可进行的估计策略，我们表征了两个不同的方法家族：模型 - 不合时宜的和模型特定的近似值。对于模型 - 不合稳定的近似值，我们基准了广泛的估计方法，并将其与Shapley值的替代性但等效的特征联系起来。对于特定于模型的近似值，我们阐明了对每种方法的线性，树和深模型的障碍至关重要的假设。最后，我们确定了文献中的差距以及有希望的未来研究方向。

机器学习（ML）模型需要经常在改变各种应用场景中更改数据集，包括数据估值和不确定量化。为了有效地重新培训模型，已经提出了线性近似方法，例如影响功能，以估计数据变化对模型参数的影响。但是，对于大型数据集的变化，这些方法变得不准确。在这项工作中，我们专注于凸起的学习问题，并提出了一般框架，用于学习使用神经网络进行不同训练集的优化模型参数。我们建议强制执行预测的模型参数，以通过正则化技术遵守最优性条件并保持效用，从而显着提高泛化。此外，我们严格地表征了神经网络的表现力，以近似凸起问题的优化器。经验结果展示了与最先进的准确高效的模型参数估计中提出的方法的优点。

联合学习是一种新兴的分散机器学习方案，允许多个数据所有者在确保数据隐私的同时协同工作。联邦学习的成功在很大程度上取决于数据所有者的参与。为了维持和鼓励数据业主的参与，公正地评估数据所有者提供的数据质量并相应地奖励它们是至关重要的。联邦福利价值，最近由Wang等人提出。 [联合学习，2020]是联合学习框架下的数据值的措施，其满足数据估值的许多所需属性。然而，联邦福利价值设计中潜在的不公平仍然存在因素，因为具有相同本地数据的两个数据所有者可能无法接收相同的评估。我们提出了一种新的措施，称为已联邦福利价值，以提高联邦福利价值的公平性。该设计取决于完成由数据所有者的不同子集的所有可能贡献组成的矩阵。它在温和条件下显示，该矩阵通过利用优化而利用概念和工具而大致低等级。理论分析和实证评估都验证了拟议的措施在许多情况下改善公平性。

Good models require good training data. For overparameterized deep models, the causal relationship between training data and model predictions is increasingly opaque and poorly understood. Influence analysis partially demystifies training's underlying interactions by quantifying the amount each training instance alters the final model. Measuring the training data's influence exactly can be provably hard in the worst case; this has led to the development and use of influence estimators, which only approximate the true influence. This paper provides the first comprehensive survey of training data influence analysis and estimation. We begin by formalizing the various, and in places orthogonal, definitions of training data influence. We then organize state-of-the-art influence analysis methods into a taxonomy; we describe each of these methods in detail and compare their underlying assumptions, asymptotic complexities, and overall strengths and weaknesses. Finally, we propose future research directions to make influence analysis more useful in practice as well as more theoretically and empirically sound. A curated, up-to-date list of resources related to influence analysis is available at https://github.com/ZaydH/influence_analysis_papers.

Machine learning models are often susceptible to adversarial perturbations of their inputs. Even small perturbations can cause state-of-the-art classifiers with high "standard" accuracy to produce an incorrect prediction with high confidence. To better understand this phenomenon, we study adversarially robust learning from the viewpoint of generalization. We show that already in a simple natural data model, the sample complexity of robust learning can be significantly larger than that of "standard" learning. This gap is information theoretic and holds irrespective of the training algorithm or the model family. We complement our theoretical results with experiments on popular image classification datasets and show that a similar gap exists here as well. We postulate that the difficulty of training robust classifiers stems, at least partially, from this inherently larger sample complexity.

在线性回归中，我们希望根据少量样本估算超过$ d $维的输入点和实价响应的最佳最小二乘预测。根据标准随机设计分析，其中绘制样品i.i.d。从输入分布中，该样品的最小二乘解决方案可以看作是最佳的自然估计器。不幸的是，该估计器几乎总是产生来自输入点的随机性的不良偏置，这在模型平均中是一个重要的瓶颈。在本文中，我们表明可以绘制非i.i.d。输入点的样本，无论响应模型如何，最小二乘解决方案都是最佳的无偏估计器。此外，可以通过增强先前绘制的I.I.D。可以有效地生产该样本。带有额外的$ d $点的样品，根据点由点跨越的平方量重新缩放的输入分布构建的一定确定点过程，共同绘制。在此激励的基础上，我们开发了一个理论框架来研究体积响应的采样，并在此过程中证明了许多新的矩阵期望身份。我们使用它们来表明，对于任何输入分布和$ \ epsilon> 0 $，有一个随机设计由$ o（d \ log d+ d+ d+ d/\ epsilon）$点，从中可以从中构造出无偏见的估计器，其预期的是正方形损耗在整个发行版中，$ 1+\ epsilon $ times最佳损失。我们提供有效的算法来在许多实际设置中生成这种无偏估计量，并在实验中支持我们的主张。

As data becomes the fuel driving technological and economic growth, a fundamental challenge is how to quantify the value of data in algorithmic predictions and decisions. For example, in healthcare and consumer markets, it has been suggested that individuals should be compensated for the data that they generate, but it is not clear what is an equitable valuation for individual data. In this work, we develop a principled framework to address data valuation in the context of supervised machine learning. Given a learning algorithm trained on n data points to produce a predictor, we propose data Shapley as a metric to quantify the value of each training datum to the predictor performance. Data shapley value uniquely satisfies several natural properties of equitable data valuation. We develop Monte Carlo and gradient-based methods to efficiently estimate data Shapley values in practical settings where complex learning algorithms, including neural networks, are trained on large datasets. In addition to being equitable, extensive experiments across biomedical, image and synthetic data demonstrate that data Shapley has several other benefits: 1) it is more powerful than the popular leave-one-out or leverage score in providing insight on what data is more valuable for a given learning task; 2) low Shapley value data effectively capture outliers and corruptions; 3) high Shapley value data inform what type of new data to acquire to improve the predictor.

我们提出了使用多级蒙特卡罗（MLMC）方法的变分推理的差异减少框架。我们的框架是基于Reparameterized梯度估计的梯度估计，并在优化中从过去更新历史记录获得的“回收”参数。此外，我们的框架还提供了一种基于随机梯度下降（SGD）的新优化算法，其自适应地估计根据梯度方差的比率用于梯度估计的样本大小。理论上，通过我们的方法，梯度估计器的方差随着优化进行而降低，并且学习率调度器函数有助于提高收敛。我们还表明，就\ Texit {信噪比}比率而言，我们的方法可以通过提高初始样本大小来提高学习速率调度器功能的梯度估计的质量。最后，我们确认我们的方法通过使用多个基准数据集的基线方法的实验比较来实现更快的收敛性并降低梯度估计器的方差，并降低了与其他方法相比的其他方法。

在许多多机构设置中，参与者可以组建团队以实现可能超过其个人能力的集体成果。衡量代理商的相对贡献并分配促进持续合作的奖励份额是艰巨的任务。合作游戏理论提供了识别分配方案（例如沙普利价值）的解决方案概念，这些概念公平地反映了个人对团队或核心表现的贡献，从而减少了代理人放弃团队的动机。此类方法的应用包括识别有影响力的特征并分享合资企业或团队成立的成本。不幸的是，即使在受限设置中，使用这些解决方案也需要解决计算障碍，因为它们很难计算。在这项工作中，我们展示了如何通过训练神经网络提出公平和稳定的回报分配来将合作游戏理论解决方案蒸馏成学习的模型。我们表明，我们的方法创建的模型可以推广到远离训练分布的游戏，并且可以预测比训练期间观察到的更多玩家的解决方案。我们框架的一个重要应用是可以解释的AI：我们的方法可用于加快在许多情况下的Shapley价值计算。

提出测试释放（PTR）是一个差异隐私框架，可符合局部功能的敏感性，而不是其全球敏感性。该框架通常用于以差异性私有方式释放强大的统计数据，例如中位数或修剪平均值。尽管PTR是十年前引入的常见框架，但在诸如Robust SGD之类的应用程序中使用它，我们需要许多自适应鲁棒的查询是具有挑战性的。这主要是由于缺乏Renyi差异隐私（RDP）分析，这是一种瞬间的私人深度学习方法的基础。在这项工作中，我们概括了标准PTR，并在目标函数界定全局灵敏度时得出了第一个RDP。我们证明，与直接分析的$（\ eps，\ delta）$ -DP相比，我们的RDP绑定的PTR可以得出更严格的DP保证。我们还得出了亚采样下PTR的算法特异性隐私扩增。我们表明，我们的界限比一般的上限和接近下限的界限要紧密得多。我们的RDP界限可以为PTR的许多自适应运行的组成而更严格的隐私损失计算。作为我们的分析的应用，我们表明PTR和我们的理论结果可用于设计私人变体，用于拜占庭强大的训练算法，这些变体使用可靠的统计数据用于梯度聚集。我们对不同数据集和体系结构的标签，功能和梯度损坏的设置进行实验。我们表明，与基线相比，基于PTR的私人和强大的培训算法可显着改善该实用性。

机器学习模型，尤其是人工神经网络，越来越多地用于为在各个领域的高风险场景中（从金融服务，公共安全和医疗保健服务）提供信息。尽管神经网络在许多情况下都取得了出色的性能，但它们的复杂性质引起了人们对现实情况下的可靠性，可信赖性和公平性的关注。结果，已经提出了几种A-tostori解释方法来突出影响模型预测的特征。值得注意的是，Shapley的价值 - 一种满足几种理想特性的游戏理论数量 - 在机器学习解释性文献中获得了知名度。然而，更传统上，在统计学习中的特征是通过有条件独立性正式化的，而对其进行测试的标准方法是通过有条件的随机测试（CRT）。到目前为止，有关解释性和特征重要性的这两个观点已被认为是独特的和独立的。在这项工作中，我们表明基于沙普利的解释方法和针对特征重要性的有条件独立性测试密切相关。更确切地说，我们证明，通过类似于CRT的程序实现了一组特定的条件独立性测试，评估了Shapley系数量，以执行特定的条件独立性测试，但用于不同的零假设。此外，获得的游戏理论值上限限制了此类测试的$ p $值。结果，我们授予大型Shapley系数具有精确的统计意义，并具有控制I型错误。

测量贡献是合作游戏理论中的一个经典问题，其中沙普利价值是最著名的解决方案概念。在本文中，我们在参数贝叶斯学习游戏中建立了沙普利价值的收敛属性，玩家使用其组合数据进行贝叶斯推断，后端kl差异被用作特征函数。我们表明，对于任何两个玩家，在某些规律性的条件下，其在Shapley价值上的差异与限制性游戏的Shapley值的差异有关，其特征功能与联合Fisher信息的对数确定性成正比。作为一个应用程序，我们介绍了一个在线协作学习框架，该框架是渐近的沙普利 - 费尔。我们的结果使得可以实现这一目标，而无需对后端KL差异的任何昂贵计算。仅需要一致的Fisher信息估计器。使用现实世界数据通过实验证明了我们框架的有效性。

子模块功能一直是多种现实应用程序的强大数学模型。最近，用于建模数据和功能等实体之间的建模概念（例如信息和冗余），在机器学习（ML）中越来越重要。在这些应用中，一个关键问题是回报分配，即如何评估每个实体对集体目标的重要性？为此，合作游戏理论的经典解决方案概念提供了有原则的收益分配方法。然而，尽管游戏理论文献广泛，但在研究中的收益分配相对不足。特别是，在新兴的子模型应用程序中出现的一个重要概念是冗余，这可能来自各种来源，例如丰富的数据或恶意操纵，在这些来源中，玩家复制其资源并在多个身份下行动。尽管许多游戏理论解决方案概念可以直接用于子模型游戏中，但天真地将它们应用于这些设置中的回报可能会导致鲁棒性问题，以防止复制。在本文中，我们系统地研究了子模型游戏中的复制操作并研究了复制鲁棒性，该指标可以定量测量解决方案概念抗复制的鲁棒性。使用该指标，我们提出了从理论上描述半相象的鲁棒性的条件，该标准是夏普利和班扎夫价值在内的广泛解决方案概念的鲁棒性。此外，我们从经验上验证了我们在新兴的Subsodular ML应用程序（即ML数据市场）上验证我们的理论结果。

作为算法公平性的概念，多核算已被证明是一个强大而多才多艺的概念，其含义远远超出了其最初的意图。这个严格的概念 - 预测在丰富的相交子群中得到了很好的校准 - 以成本为代价提供了强大的保证：学习成型预测指标的计算和样本复杂性很高，并且随着类标签的数量而成倍增长。相比之下，可以更有效地实现多辅助性的放松概念，但是，仅假设单独使用多学历，就无法保证许多最可取的多核能概念。这种紧张局势提出了一个关键问题：我们能否以多核式式保证来学习预测因素，以与多审核级相称？在这项工作中，我们定义并启动了低度多核的研究。低度的多核净化定义了越来越强大的多组公平性概念的层次结构，这些概念跨越了多辅助性和极端的多核电的原始表述。我们的主要技术贡献表明，与公平性和准确性有关的多核算的关键特性实际上表现为低级性质。重要的是，我们表明，低度的数学振动可以比完整的多核电更有效。在多级设置中，实现低度多核的样品复杂性在完整的多核电上呈指数级（在类中）提高。我们的工作提供了令人信服的证据，表明低度多核能代表了一个最佳位置，将计算和样品效率配对，并提供了强大的公平性和准确性保证。

在随着时间变化的组合环境中的在线决策激励，我们研究了将离线算法转换为其在线对应物的问题。我们专注于使用贪婪算法对局部错误的贪婪算法进行恒定因子近似的离线组合问题。对于此类问题，我们提供了一个通用框架，该框架可有效地将稳健的贪婪算法转换为使用Blackwell的易近算法。我们证明，在完整信息设置下，由此产生的在线算法具有$ O（\ sqrt {t}）$（近似）遗憾。我们进一步介绍了Blackwell易接近性的强盗扩展，我们称之为Bandit Blackwell的可接近性。我们利用这一概念将贪婪的稳健离线算法转变为匪（t^{2/3}）$（近似）$（近似）的遗憾。展示了我们框架的灵活性，我们将脱机之间的转换应用于收入管理，市场设计和在线优化的几个问题，包括在线平台中的产品排名优化，拍卖中的储备价格优化以及supperular tossodular最大化。 。我们还将还原扩展到连续优化的类似贪婪的一阶方法，例如用于最大化连续强的DR单调下调功能，这些功能受到凸约束的约束。我们表明，当应用于这些应用程序时，我们的转型会导致新的后悔界限或改善当前已知界限。我们通过为我们的两个应用进行数值模拟来补充我们的理论研究，在这两种应用中，我们都观察到，转换的数值性能在实际情况下优于理论保证。