Credit attribution is crucial across various fields. In academic research,
proper citation acknowledges prior work and establishes original contributions.
Similarly, in generative models, such as those trained on existing artworks or
music, it is important to ensure that any generated content influenced by these
works appropriately credits the original creators.
We study credit attribution by machine learning algorithms. We propose new
definitions--relaxations of Differential Privacy--that weaken the stability
guarantees for a designated subset of $k$ datapoints. These $k$ datapoints can
be used non-stably with permission from their owners, potentially in exchange
for compensation. Meanwhile, the remaining datapoints are guaranteed to have no
significant influence on the algorithm's output.
Our framework extends well-studied notions of stability, including
Differential Privacy ($k = 0$), differentially private learning with public
data (where the $k$ public datapoints are fixed in advance), and stable sample
compression (where the $k$ datapoints are selected adaptively by the
algorithm). We examine the expressive power of these stability notions within
the PAC learning framework, provide a comprehensive characterization of
learnability for algorithms adhering to these principles, and propose
directions and questions for future research.

我们研究机器学习算法对信用归因的问题，提出了新的定义 —— 对差分隐私进行放松，以使得某些数据点的稳定性保证降低，这些数据点可以在得到数据所有者的许可下非稳定地使用，可能会有对其进行补偿，同时其他数据点对算法的输出没有显著影响。我们在 PAC 学习框架内研究了这些稳定性概念的表达能力，并对遵循这些原则的算法的可学习性进行了综合刻画，并提出了未来研究的方向和问题。

信用归因与稳定压缩

Credit Attribution and Stable Compression

In 1984, Valiant [ 7 ] introduced the Probably Approximately Correct (PAC)
learning framework for boolean function classes. Blumer et al. [ 2] extended
this model in 1989 by introducing the VC dimension as a tool to characterize
the learnability of PAC. The VC dimension was based on the work of Vapnik and
Chervonenkis in 1971 [8 ], who introduced a tool called the growth function to
characterize the shattering property. Researchers have since determined the VC
dimension for specific classes, and efforts have been made to develop an
algorithm that can calculate the VC dimension for any concept class. In 1991,
Linial, Mansour, and Rivest [4] presented an algorithm for computing the VC
dimension in the discrete setting, assuming that both the concept class and
domain set were finite. However, no attempts had been made to design an
algorithm that could compute the VC dimension in the general setting.Therefore,
our work focuses on developing a method to approximately compute the VC
dimension without constraints on the concept classes or their domain set. Our
approach is based on our finding that the Empirical Risk Minimization (ERM)
learning paradigm can be used as a new tool to characterize the shattering
property of a concept class.

开发了一种在没有约束条件的情况下近似计算 VC 维度的方法，该方法基于经验风险最小化学习范式，用于表征概念类的粉碎性质。