- Rating
- 3
- Confidence
- 1
- Informativeness
- 1
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This theoretical paper studies learning with explanations modeled as positive witnesses: each input / sample is a collection of items, and an explanation identifies one item sufficient for a positive label. It investigates how history-dependent witness selection affects sample complexity, proving separations from memoryless selection and giving conditions under which the learning benefit is preserved.
My assessment is mostly an educated guess because this work lies outside my main expertise. Unfortunately, the authors did not attempt to make the paper self-contained and understandable for people of various backgrounds. I have not identified a specific correctness issue, but I could not independently verify the central proofs. As a result, the soundness score should be read with that limitation.
Critical strengths
- The paper formulates a precise question about whether valid explanations (under the chosen semantics) remain useful when their selection depends on training history.
- The stated results look interesting from the learning theory perspective.
Critical weaknesses
- To my taste, the paper's presentation is not great and leaves much to be desired, from the perspective of an average reader. While definitions and proof sketches are provided, I found the central construction hard to follow without substantial background in learning theory.
- The connection between the witness abstraction and explanations used in practical classification is insufficiently developed. A worked example using ordinary feature-based inputs would help.
- The main separation relies on a highly constructed family with very large bags, making its implications for realistic learning settings unclear.
Questions for authors
- How does this framework relate to learning from abductive explanations expressed as sufficient partial feature assignments? Can the separation be demonstrated in a typical ML classification setup?
- What conclusions still apply when bag size is realistically bounded?
4 comments
Reply to Reviewer PbxM(2/3)
W2 (connection to practical explanations; a worked feature example)
Thank you for this suggestion; we agree. The revision adds such an example in the second paragraph of the introduction and maps it onto the model in Section 2.1. Take three binary features and two rules, a = x₁∧x₂ and b = x₂∧x₃, each sufficient for a positive label.
- On x = (1,1,1), both rules fire, so an annotator can correctly explain the positive label by citing either one.
- On x' = (0,1,1), only b fires. A learner told b on x can label x' positive without seeing its label; a learner told a cannot.
The two explanations are equally valid on x, yet carry different information about future inputs. Which one is shown may depend on what the annotator explained before, and this choice is what the paper studies. In our model an input is represented by the set of rules that fire on it, A(x) = {a, b} and A(x') = {b}. The unknown target G is the set of rules sufficient for a positive label, here {a, b}, and an explanation (a witness) is one rule in A(x) ∩ G. In general, input x ↔ bag A(x) of rules that fire, rule ↔ instance, rules sufficient for positivity ↔ target G, and explanation ↔ witness.
Rules can be any checkable conditions on features, such as conjunctions of feature values or the presence of a phrase or substructure. In text classification with rationales, for example, a document is positive if it contains any of a few unknown key phrases, and the annotator highlights one key phrase it contains. When the highlighted phrase alone suffices for the label, it is exactly a witness. This is the sparse-rule setting of Section 5.3 (new Proposition H.4), where explanations reduce the labels needed under any annotator behavior.
W3 and Q2 (the constructed family; realistic bag sizes)
Thank you for raising this concern and the related question. We agree that the separating family is highly constructed and that its inputs are very large. Its role is to answer a worst-case question, whether valid explanations alone guarantee the label savings whatever the annotator's selection, and it shows that they do not. New Proposition H.3 shows that large inputs are necessary for any such loss, which needs many rules firing on an input and a very large rule dictionary.
This also answers what holds when inputs are realistically bounded. If at most b rules fire on any input, history dependence costs at most a factor of order log b in labels compared with a fixed selection criterion. Learning then never becomes impossible, as it does in our countable extension, which needs unbounded inputs. When only one rule fires, the explanation is forced and all annotator behaviors coincide. All positive results hold at any input size. Any fixed selection criterion is safe, and every annotator behavior is safe for sparse rule dictionaries, for the simplest rule families and for linear subspaces. We know of no natural annotator behavior that is harmful, and Section 6 now asks whether one exists.
Reply to Reviewer PbxM(3/3)
Q1 (abductive explanations; a typical ML setup)
Thank you for this question, which connects the paper to formal explainability. Our explanations are abductive explanations of the target. An abductive explanation (a minimal sufficient reason, or prime implicant) of a positive input is a minimal partial feature assignment that forces a positive label whatever the remaining features are. In the example of W2, with f = (x₁∧x₂) ∨ (x₂∧x₃) and x = (1,1,1), the abductive explanations of f at x are exactly {x₁=1, x₂=1} and {x₂=1, x₃=1}, that is, the rules a and b, the two valid explanations in our model. New Proposition H.2 shows that this holds in general when each input is encoded by one Boolean feature per rule, indicating whether the rule fires. The target is then a disjunction of these features, and the minimal sufficient reasons of a positive input, even allowing features fixed to zero, are exactly its valid explanations in our model. Our framework is thus learning from abductive explanations of the target concept, rather than of a trained model, with one abductive explanation per positive example. Requiring minimal explanations removes none of the annotator's choices, and all results hold verbatim. The freedom we study is that an input often has several abductive explanations, as x does above.
The separation can be demonstrated in this feature form. Under this encoding, the family of Section 4 is a binary classification problem over Boolean features in which every explanation the annotator gives is a minimal abductive explanation, and Theorem 4.1 holds unchanged. The encoding needs a very large number of features, and by new Proposition H.3 this is true of any separation, not only ours (see W3 and Q2). In typical setups the conclusion is positive. When an input is positive iff it contains any of at most s unknown key features out of N candidates, explanations reduce the labels needed from order s log(N/s) to order s for every annotator behavior, including history-dependent ones (new Proposition H.4). If instead the target is a disjunction of at most s short conjunctions of raw features and each explanation names one satisfied conjunction, O((s+log(1/δ))/ε) samples suffice for every annotator behavior, independently of the number of features and of the length of the conjunctions (Appendix H.4).
Thank you again for your review; we would be glad to clarify anything further.
Thank you for the constructive responses. I appreciate it.
Reply to Reviewer PbxM(1/3)
Dear Reviewer PbxM,
Thank you for your careful reading and candid assessment, and for the concrete suggestions on a worked example and on abductive explanations. They shaped several revisions, marked in blue in the revised PDF; "new" below refers to results added in the new Appendix H.
W1 (presentation)
Thank you for this comment. We agree that the original version was hard to follow for readers outside learning theory, and we first restate the paper in machine-learning terms.
Problem. Training labels increasingly come with explanations, such as annotator rationales. A rule that explains one example can also label future examples, so explanations can reduce the number of labels needed. An input, however, often has several valid explanations, and which one is shown may depend on the annotation history, for example when annotators stay consistent with their earlier answers. We ask whether the label savings from valid explanations survive when the choice among them depends on this history.
Findings. First, explanations chosen by any fixed criterion that ignores earlier annotations, such as the shortest, first, or most salient valid one, reduce the labels needed, and the cost depends on the complexity of the explanation rules rather than of the classifier. Second, history dependence is harmless in several natural cases, namely the simplest rule families, linear subspaces, and sparse rule dictionaries, where an input is positive if any of a few unknown key features is present. Third, it is not harmless in general. For some rule families, a history-dependent annotator can give only valid, even minimal, explanations that together reveal nothing about unseen examples beyond the labels, so many more labels are needed. Such a loss requires a very large number of candidate rules.
Approach. We study sample complexity, the number of labeled examples needed to reach a given accuracy, with labels alone, with explanations chosen by a fixed criterion, and with explanations chosen depending on the history. Explanations are modeled as sufficient reasons, or abductive explanations, over a dictionary of rules. Our guarantees hold for every valid choice of explanation, because a learner can check that an explanation is valid but cannot verify the annotator's intent.
Implications. For annotation design, a fixed selection criterion is always safe, and in sparse-rule settings any selection is safe. For explainability, the validity, or even minimality, of each explanation does not guarantee that a set of explanations is informative; when explanations are reused as supervision, how they are selected across examples matters.
Changes for readability. The second paragraph of the introduction now gives a worked feature example (see W2), and Section 2.1 maps it onto the model with a table. The detailed dimension arguments of Section 4.3 have moved to Appendix C.2, and a new related-work paragraph connects our explanations to abductive explanations. The central construction rests on one idea, which Section 4.1 explains before the formal details. Every explanation is valid, but the code it carries is masked by a random pad, as in a one-time pad, so a learner who sees all explanations learns nothing about the labels of the unseen designated bags beyond what the observed labels reveal (Proposition 4.2).