arXiv:2502.16352cs.LGcs.CR2025-02

提出验证分类器的最小披露协议,控制非相关文档暴露数量。

Verifying Classification with Limited Disclosure

  • 用留一法维度衡量分类器可验证性,控制披露非相关文档数。
  • 当线性分类器边距>1/3时,仅需披露常数量级非相关文档。
  • 适用于电子取证场景,对隐私保护型机器学习有参考价值。

我们研究由Dong、Hartline和Vijayaraghavan(2022)提出的多方分类问题,该问题源于电子发现。目标是设计一种协议,使请求方获得几乎全部相关文件,同时最小化非相关文件的披露。我们提出验证协议,通过披露少量非相关文件来证明分类器正确性。引入分类器族的留一法维度概念,并证明在可实现情形下(存在完美分类器),协议披露的非相关文件数不超过该维度。针对带边距的线性分类器,我们刻画了边距与需披露非相关文件数之间的权衡:在d维输入空间中,当边距超过1/3时,仅需O(1)个非相关文件;当边距恰好为1/3时,最坏情况下至少需披露Ω(d)个;当边距小于1/3时,需披露Ω(e^d)个。该结果在编码理论和组合几何中亦具独立意义。我们还将协议扩展至不可实现情形,定义了鲁棒留一法维度,并考虑了对Alice误分类容忍的场景。

原文摘要 · Abstract (English)

We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) motivated by electronic discovery. In this problem, our goal is to design a protocol that guarantees the requesting party receives nearly all responsive documents while minimizing the disclosure of nonresponsive documents. We develop verification protocols that certify the correctness of a classifier by disclosing a few nonresponsive documents. We introduce a combinatorial notion called the Leave-One-Out dimension of a family of classifiers and show that the number of nonresponsive documents disclosed by our protocol is at most this dimension in the realizable setting, where a perfect classifier exists in this family. For linear classifiers with a margin, we characterize the trade-off between the margin and the number of nonresponsive documents that must be disclosed for verification. Specifically, we establish a trichotomy in this requirement: for $d$ dimensional instances, when the margin exceeds $1/3$, verification can be achieved by revealing only $O(1)$ nonresponsive documents; when the margin is exactly $1/3$, in the worst case, at least $Ω(d)$ nonresponsive documents must be disclosed; when the margin is smaller than $1/3$, verification requires $Ω(e^d)$ nonresponsive documents. We believe this result is of independent interest with applications to coding theory and combinatorial geometry. We further extend our protocols to the nonrealizable setting defining an analogous combinatorial quantity robust Leave-One-Out dimension, and to scenarios where the protocol is tolerant to misclassification errors by Alice.

分类验证隐私保护机器学习

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。