Verifying Classification with Limited Disclosure

• URL: http://arxiv.org/abs/2502.16352v1
• Date: Sat, 22 Feb 2025 20:56:03 GMT
• Title: Verifying Classification with Limited Disclosure
• Authors: Siddharth Bhandari, Liren Shan,
• Abstract summary: We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) motivated by electronic discovery.<n>Our goal is to design a protocol that guarantees the requesting party receives nearly all responsive documents while minimizing the disclosure of nonresponsive documents.
• Score: 4.88160756739524
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: 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 $\Omega(d)$ nonresponsive documents must be disclosed; when the margin is smaller than $1/3$, verification requires $\Omega(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.

Related papers

• Collapse of Dense Retrievers: Short, Early, and Literal Biases Outranking Factual Evidence [56.09494651178128]
  Retrieval models are commonly used in Information Retrieval (IR) applications, such as Retrieval-Augmented Generation (RAG) We show that retrievers often rely on superficial patterns like over-prioritizing document beginnings, shorter documents, repeated entities, and literal matches. We show that these biases have direct consequences for downstream applications like RAG, where retrieval-preferred documents can mislead LLMs.
  arXiv  Detail & Related papers  (2025-03-06T23:23:13Z)
• Riddle Me This! Stealthy Membership Inference for Retrieval-Augmented Generation [18.098228823748617]
  We present Interrogation Attack (IA), a membership inference technique targeting documents in the RAG datastore.<n>We demonstrate successful inference with just 30 queries while remaining stealthy.<n>We observe a 2x improvement in TPR@1%FPR over prior inference attacks across diverse RAG configurations.
  arXiv  Detail & Related papers  (2025-02-01T04:01:18Z)
• Efficient Document Ranking with Learnable Late Interactions [73.41976017860006]
  Cross-Encoder (CE) and Dual-Encoder (DE) models are two fundamental approaches for query-document relevance in information retrieval. To predict relevance, CE models use joint query-document embeddings, while DE models maintain factorized query and document embeddings. Recently, late-interaction models have been proposed to realize more favorable latency-quality tradeoffs, by using a DE structure followed by a lightweight scorer.
  arXiv  Detail & Related papers  (2024-06-25T22:50:48Z)
• Trading off Consistency and Dimensionality of Convex Surrogates for the Mode [6.096888891865663]
  In multiclass classification over $n$ outcomes, the outcomes must be embedded into the reals with dimension at least $n-1$. We investigate ways to trade off surrogate loss dimension, the number of problem instances, and restricting the region of consistency in the simplex. We show that full-dimensional subsets of the simplex exist around each point mass distribution for which consistency holds, but also, with less than $n-1$ dimensions, there exist distributions for which a phenomenon called hallucination occurs.
  arXiv  Detail & Related papers  (2024-02-16T16:42:09Z)
• Error-Tolerant E-Discovery Protocols [18.694850127330973]
  We consider the multi-party classification problem introduced by Dong, Hartline, and Vijayaraghavan (2022) Based on a request for production from the requesting party, the responding party is required to provide documents that are responsive to the request except for those that are legally privileged. Our goal is to find a protocol that verifies that the responding party sends almost all responsive documents while minimizing the disclosure of non-responsive documents.
  arXiv  Detail & Related papers  (2024-01-31T15:59:16Z)
• Generative Dense Retrieval: Memory Can Be a Burden [16.964086245755798]
  Generative Retrieval (GR) autoregressively decodes relevant document identifiers given a query. Dense Retrieval (DR) is introduced to conduct fine-grained intra-cluster matching from clusters to relevant documents. DR obtains an average of 3.0 R@100 improvement on NQ dataset under multiple settings.
  arXiv  Detail & Related papers  (2024-01-19T04:24:07Z)
• Factcheck-Bench: Fine-Grained Evaluation Benchmark for Automatic Fact-checkers [121.53749383203792]
  We present a holistic end-to-end solution for annotating the factuality of large language models (LLMs)-generated responses. We construct an open-domain document-level factuality benchmark in three-level granularity: claim, sentence and document. Preliminary experiments show that FacTool, FactScore and Perplexity are struggling to identify false claims.
  arXiv  Detail & Related papers  (2023-11-15T14:41:57Z)
• Classification Protocols with Minimal Disclosure [12.308957254601243]
  We consider multi-party protocols for classification motivated by applications such as e-discovery in court proceedings. We identify a protocol that guarantees that the requesting party receives all responsive documents and the sending party discloses the minimal amount of non-responsive documents. This protocol can be embedded in a machine learning framework that enables automated labeling of points.
  arXiv  Detail & Related papers  (2022-09-06T17:57:52Z)
• GERE: Generative Evidence Retrieval for Fact Verification [57.78768817972026]
  We propose GERE, the first system that retrieves evidences in a generative fashion. The experimental results on the FEVER dataset show that GERE achieves significant improvements over the state-of-the-art baselines.
  arXiv  Detail & Related papers  (2022-04-12T03:49:35Z)
• Online Selective Classification with Limited Feedback [82.68009460301585]
  We study selective classification in the online learning model, wherein a predictor may abstain from classifying an instance. Two salient aspects of the setting we consider are that the data may be non-realisable, due to which abstention may be a valid long-term action. We construct simple versioning-based schemes for any $mu in (0,1],$ that make most $Tmu$ mistakes while incurring smash$tildeO(T1-mu)$ excess abstention against adaptive adversaries.
  arXiv  Detail & Related papers  (2021-10-27T08:00:53Z)
• Active Learning from Crowd in Document Screening [76.9545252341746]
  We focus on building a set of machine learning classifiers that evaluate documents, and then screen them efficiently. We propose a multi-label active learning screening specific sampling technique -- objective-aware sampling. We demonstrate that objective-aware sampling significantly outperforms the state of the art active learning sampling strategies.
  arXiv  Detail & Related papers  (2020-11-11T16:17:28Z)
• Fast(er) Reconstruction of Shredded Text Documents via Self-Supervised Deep Asymmetric Metric Learning [62.34197797857823]
  A central problem in automatic reconstruction of shredded documents is the pairwise compatibility evaluation of the shreds. This work proposes a scalable deep learning approach for measuring pairwise compatibility in which the number of inferences scales linearly. Our method has accuracy comparable to the state-of-the-art with a speed-up of about 22 times for a test instance with 505 shreds.
  arXiv  Detail & Related papers  (2020-03-23T03:22:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.