Reproducibility in Multiple Instance Learning: A Case For Algorithmic Unit Tests
Authors: Edward Raff
James Holt
Venue: NeurIPS 2023 poster (2023)
Keywords: reproducibility; multiple instance learning
TL;DR: Most multiple instance learning papers don't check if they respect the multiple instance assumption. Some simple unit tests detect this.

Abstract: Multiple Instance Learning (MIL) is a sub-domain of classification problems with positive and negative labels and a "bag" of inputs, where the label is positive if and only if a positive element is contained within the bag, and otherwise is negative. Training in this context requires associating the bag-wide label to instance-level information, and implicitly contains a causal assumption and asymmetry to the task (i.e., you can't swap the labels without changing the semantics). MIL problems occur in healthcare (one malignant cell indicates cancer), cyber security (one malicious executable makes an infected computer), and many other tasks. In this work, we examine five of the most prominent deep-MIL models and find that none of them respects the standard MIL assumption. They are able to learn anti-correlated instances, i.e., defaulting to "positive" labels until seeing a negative counter-example, which should not be possible for a correct MIL model. We suspect that enhancements and other works derived from these models will share the same issue. In any context in which these models are being used, this creates the potential for learning incorrect models, which creates risk of operational failure.  We identify and demonstrate this problem via a proposed ``algorithmic unit test'', where we create synthetic datasets that can be solved by a MIL respecting model, and which clearly reveal learning that violates MIL assumptions. The five evaluated methods each fail one or more of these tests. This provides a model-agnostic way to identify violations of modeling assumptions, which we hope will be useful for future development and evaluation of MIL models.

Reproducibility in Multiple Instance Learning: A Case For Algorithmic Unit Tests
Edward Raff
Jim Holt
Booz Allen Hamilton
Laboratory for Physical Sciences holtelps und. edu
University Maryland, Baltimore County raff edward@bah. com
Abstract
Multiple Instance Learning (MIL) is a sub-domain of classification problems with positive and negative labels and "bag" of inputs, where the label is positive and only if positive element is contained within the bag. and otherwise is negative. Training in this context requires associating the bag-wide label to instance- information, and implicitly contains causal assumption and asymmetry the task (i.e., you can't swap the labels without changing the semantics). MIL, problems occur in healthcare (one malignant cell indicates cancer), cyber security (one malicious executable makes an infected computer), and many other tasks. In this work, we examine five of the most prominent deep-MIL models and find that none of them respects the standard MIL assumption. They are able to learn anti- correlated instances, i.e., defaulting counter- counter-example, which should not be possible for correct MIL model. We suspect that enhancements and other works derived from these models will share the same issue. In any context in which these models are being used, this creates the potential for learning incorrect models, which creates risk of operational failure. We identify and demonstrate this problem via a proposed "algorithmic unit test", where we create synthetic datasets that can be solved by a MIL. respecting model, and which clearly reveal learning that violates MII. assumptions. The five evaluated methods each fail one or more of these tests. This provides model-agnostic way to identify violations of modeling assumptions, which we hope will be useful for future development and evaluation of MIL models.
"positive" labels until seeing a negative
Introduction
In Multiple Instance Learning (MIL) we have dataset of N labeled points, which we will represent as X' with associated labels [-1,1} } for the negative and positive labels respectively. As originally described, the MIL problem involves each datum X; E X' being a bag of multiple instances, where X, {x1, X2,.... ... Xn, } is bag of n, instances. Each instance x, E X, is D-dimensional vector, and every bag X, may have a different total number of items n4. Given instant level classifier h(-), most MIL. algorithms work by predicting ýs m h(v,).
As originally described, the positive/negative label of each bag X; has a special meaning. By default, a bag's 's label is negative (y = 1). The label of bag will become positive (y 1) if and only if positive instance Xj present inside the bag, at which point the entire bag's label becomes positive. Because instance-level labels mapping each xj y E 1} are not given, the MII. problem is to infer the instance-level labels from the whole-bag level labeling. This implies a critical asymmetric nature the given labels and how they must be handled. A value of y 1 tells us that all instances are negative in the given bag, whereas label of y = tells us that one or more instances have positive label. For this reason, swapping the positive and negative labels in MIL problem is not
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

semantically meaningful or correct, whereas, in standard classification problem, the labels can be interchanged without altering the semantics of the learning task.
The MIL. problem occurs with frequency in many real-world applications, in particular in the medical community where the presence of any abnormal cell type (i.e., instance) is the confirmative indicator for a larger organism's 's disease (i.e, bag and label). As the MIL problem implies, and the medical example makes explicit, the MIL model has an implicit casual assumption: the right combination of positive indicators dictate the output label, and so the MIL model is both a valuable inductive bias toward the solution and a guard against physically implausible solutions.
Algorithms that fail, or intentionally forgo, the MIL constraints may appear to obtain better accuracy "in situ" (i.e., the lab environment). But if it is known that the MIL assumption is true, ignoring creates a significant risk of failure to generalize "in vivo" (i.e., in real production environments). In the clinical context, this is important as many MI algorithms are often proposed with superior in situ performance relative to physicians [1], but fail to maintain that performance when applied to new clinical populations [2-4]. In this case, respecting underlying MIL properties eliminates one major axis of bias between situ and vivo settings and higher confidence in potential utility. In the cyber security space, respecting the MIL nature eliminates a class of "good word" style attacks [5-7] where inconsequential content is added to evade detection, an attack that has worked on production anti-virus software [8-10]. These reasons are precisely why MIL has become increasingly popular, and the importance of ensuring the constraints are satisfied.
Notably, this creates dearth of options when more complex MII. hypotheses required, as MII and mi-Net succeed by restricting themselves to the Standard MII. assumption. The creation of MIL models that satisfy this, and other more complex hypotheses, are thus an open line of research that would have potentially significant clinical relevance. Similarly, users with more niche MIL needs may desire to more thoroughly test their models respect the constraints critical their deployment. Our work has demonstrated that many articles have not properly vetted the more basic MIL setting, and so we suspect other more complex MIL problems are equally risk.
Our work contributes the identification of this issue, as well as a strategy to avoid repeat occurrences, by developing algorithmic unit tests where synthetic dataset is created that captures specific properties about the desired solution. The test will fail if an invariant of the algorithm's 's solution is not maintained, summarized in Table 1. Such failures indicate that a MIL. method is not properly constrained, and the learning goal is not being achieved. We construct three such datasets for the MIL problem, which can be reused by any subsequent MIL research mitigate this problem. Based on these results, we would suggest practitioners/rrseareeee begin with CausalMIL and mi-Net as solid foundation ensure they are actually satisfying the MIL hypothesis, and thus avoiding excess risk in deployment.
Table 1: Our work proposes test of the Standard Multiple Instance Learning (MIL) hypothesis and two tests for the Threshold MIL. Most modern deep learning MIL models do not test or prove that they respect any MIL hypothesis, and our tests show that most are insufficient. When a model passes the Threshold test, but fails the Standard test, it is still not a valid Threshold MIL model because the tests do not guarantee correctness, they are like software unit tests that identify failures.
Model Claim
mi-Net MI-Net Standard Standard
MIL-Pooling Tran-MIL GCN-MIL CausalMIL. Hopfield Threshold
Standard Threshold Threshold
Standard
Standard Test
x
X
X
X
Threshold Tests
X
X
X
x
This paper is organized as follows. In $ we will review broadly related works, including prior work in non-deep-MIL and deep-MIL literature. It is in this related work we will denote the bascline algorithms we test, in particular the five deep-MIL models that form the foundation of most current deLp-MIL research, and a sixth deep-MIL. method that is little-known but does pass our tests. Next in $ we will define three algorithmic unit tests for MIL models. The first tests the fundamental MIL assumption that all models must respect, and the second and third tests extend to a generalized version of the MIL problem known as "threshold" MIL. Prior deep-MIL. works might tacitly assume they can tackle the generalized MII., but make no formal specification of the types of MIL. models they tackle. Then we apply our tests to six deep-MII. and seven older Support Vector Machine based MIL models in $ 4, demonstrating how different algorithms pass and fail different unit tests. In doing

---

so we provide hard evidence that the foundations of most current deep-MIL works are invalid, and thus dangerous to use in any case where the MIL assumption is used for casual or clinically relevant constraints. For example, although a cancer diagnosis should occur only because cancer was detected, a non-MII, model could learn the absence of something unrelated as false signal, causing it to overfit. In addition, we discuss cases where known non-MIL. algorithm still passes the unit test, prompting a discussion on how unit tests should be used for invalidation, not certification. Finally, we conclude in 5.
2 Related Work
Concerns about reproducibility within the fields of machine and deep learning have increased in recent years. Prior works have studied reproducibility issues with respect to dataset labels/integrity [11-13), comparison methodology. and making conclusions on improvement [14-18), discrepancies between math and floating point precision [19], discrepancies between code and paper, [20]. and false conclusions in repeatability [21]. We note that none of these prior efforts on reproducibility would have identified the MIL assumption violation that we identify in this work. Our situation is different aspect of reproducibility that the methods under test can be reproduceedrepliicaeed, but the methods themselves fundamentally are not designed to enforce the modeling assumptions, and no testing was done to ensure that they do. By developing tests meant to elicit certain and specific behaviors of MIL model, we show how unit tests may be developed for algorithm in the form of synthetic datasets.
Within the reproducibility literature, we believe the work by Ahn et al. [19] is the most similar to ours, where they develop a mathematical framework for characterizing the reproducibility of an optimization procedure when initialization and gradient computations are not exact. This is motivated by the fact that proofs of optimization do not account for floating point precision in the majority of cases, so specialized domain tests can be useful. A key point is that having source code is helpful, but does not confer correctness of the property of interest [22]. In contrast, our work is more empirical in that we actually implement our proposed tests, and our tests are born not from a mismatch between math and implementation but from the observation that prior works have neglected the mathematical work to ensure their methods follow the MIL assumptions. Other relevant works in reproducibility have looked at methodological errors [15, 23, 24].
The MIL problem bears resemblance to a niche set of defenses used within the malware detection literature. To defend against adversarial attacks, mnon-negative" [5] or "monotonic" [6] models were developed where features can only be positive (read, malicious) indicators, and by default, all files would be marked negative (benign) absent any features. This is similar to the MIL. model assumption that there is no positive response unless specific instance is present, and indeed, MIL approaches have been used to build malware detectors that are interpretable and not susceptible to attack [8].
2.1 Relevant Multi-Instance Learning Work
An explosion of interest in MIL. literature has occurred due to its relevance in medical imaging and other tasks where the MII. assumption aligns with clinically relevant or important physical/causal constraints of the underlying system. Shockingly, we find much of the literature does not test or ultimately respect this core MIL. assumption, resulting models that are at risk of over-fitting their training data and learning climically/physscally invalid solutions. Simulated benchmarks in MIL literature, but focus primarily on the Standard formulation and accuracy [25]. [26] built synthetic benchmarks of MIL tasks, but did not formalize what kinds of MIL tasks or attempt to check if a model was violating the underlying generative MIL hypothesis', The key difference of our work is to create synthetic datasets to test that model respects the MIL assumptions, rather than benchmark accuracy. We will first review the older, predominantly Support Vector Machine (SVM) history of MII. models that will test in this work. Then we consider the more recent deep learning counterparts.
common
'Two tasks are Standard MIL, one is Threshold MIL, and a fourth is indeterminate but closest to the Generalized MIL of [27]
3

---

2.1.1 Historical Non-Deep MIL
Issues with under-specification of the MIL problem had been previously identified in the seminal survey of Foulds and Frank [27], who synthesized many implicit MIL extensions into a set of generalized and well-specified MIL types. As noted by this prior work, many MIL papers from this time period do not provide proof or attempt to enforce the MIL assumption. Thus while they may be exploring broader scope of the MIL hypothesis space, the developed solutions may still fundamentally not satisfy the definition of any MIL. model.
We will briefly review some significant non-deep MIL. models that we include as comparison points, and their status with respect to the MIL assumption. Most notably the mi-SVM and MI-SVM algorithms [28] are correct by construction to the standard MIL model that we will discuss further in $ 3.1. The MI-SVM in particular introduces the idea of "witness", where the bag label is inferred from a singular maximum- rexponddinggg instance, thus incorporating the standard MIL assumption. SIL is intentionally MIL violating by construction [29]. NSK and STK algorithms [30] were previously recognized to not abide by the MIL hypothesis [27], even though the paper includes formal proofs on the learning theory, the MIL. constraints were neglected. Not analyzed previously, we also include two additional models. Firstly, the MissSVM [31], which uses semi-supervised SVM approach that uses the "single witness" approach to guarantee the standard MIL. model. Secondly, the MICA model [32], which is invalid under the standard MIL model because it uses a convex combination of points in the positive bag, and thus does not preclude the possibility of a negative sample.
2.1.2 Deep MIL Models
The first MIL neural network by Zhou and Zhang [33] was later re-invented as the "mi-Net"2 model, and directly translates the "witness" strategy [28] to a neural network, using weight sharing to process each bag independently, produce a maximal score, and then takes the max over those scores to reach final decision. This re-invention was done by Wang et al. [34] who added "MI-Net" as a "better" alternative by concatenating the results across bags, allowing final fully-connected layer to make the prediction by looking at all instances without any constraints. This error allows the MI-Net to learn to use the absence of an instance as positive indicator, thus violating the MIL assumption. This is true of the MIL pooling layer by Ilse al. [35] (which forms the basis of their Attention MIL), the Graph Neural Network based GNN-MIL of [36], the Transformer based TransMIL [37], and the Hopfield MIL model of [38]. These latter five deep-MIL models have formed the foundation of many extensions that have the same fundamental designs/prediction mechanisms, with various tweaks to improve training speed or handle large medical images [39-43]. For this reason, we will test these five deep-MIL models exemplars of the broader deep-MIL ecosystem, and show that all five models fail a simple test.
Two additional deep tests are included, which we note as distinct (because they respect MIL but are rarely used) from the preceding five highly popular methods. The mi-Net, which is the older and not widely used model of [33] respects the standard MIL assumptions. Second is CausalMIL [44, 45], the only recent line of MIL research of which we are aware that properly considers the standard MIL assumption, producing an enhanced version of the "witness" strategy. It does so by representing the problem as a graphical model to infer per-instance labels. While Zhang et al. [44] note the causal nature of MIL modeling to inform their design, they did not document that other deep-MIL approaches fail to respect the MIL assumptions.
3 MIL Unit Tests
The prior works in deep-MIL research have all cited the seminal Dietterich et al. [46] for the MIL problem without elaborating further on the assumptions of the MIL model. As denoted by Foulds and Frank [27], there are many different generalizations of the MIL hypothesis to more complex hypothesis spaces, all of which require respecting that it the presence of some item(s) that induce positive label. We will focus on Weidmann's 's Concept Hierarchy [47] that includes Dietterich et al. [46] as the most basic MII. hypothesis space, and test it along with a generalization of the MII. problem. We note that an algorithm passing test is not a certificate of correctness. Thus,
Nottbby this was a mischaracterization and should have been named "MI-Net" going by the original naming scheme, but the names mi-Net and MI-Net with incorrect designation have stuck, and repeat them.

---

if an algorithm passes the generalized Weidmann MIL tests (specified below), but fails the basic Dietterich test (specified below), means the model fails all possible MIL models because it has failed the most foundational MII. test. Our code for these tests can be found at gi thub. com/ httppppppp....ooooooooooaaaaaaaa AAlorrara//iiiiiiii wwt.orittmiiuiiieeeo www.tnii..eet.....
We will now formalize the general MIL problem in a notation that can capture both the standard and Weidmann versions of the MIL problem. We leverage this formalization make it clear what properties our unit tests are attempting to capture, and to discuss how a non-MIL model learns invalid solutions.
For all of the tests we consider, let h(x) be a function that maps a instance vector x to one of K concept-classes E C = {2, 1. }} (i.e., hxx) E C), which includes the null-class Ø. This null class has the role of identifying "other" items that are unrelated to the positive output decision of the MIL. problem. The null-class is the fundamental informative prior and useful constraint of the MIL. problem space, where any item belonging to Ø does not contribute to a negative class label prediction. That is to say, only the occurrence of the concept classes C1,... Cg can be used indicate a positive label in a valid MIL model [46, 27].
For all k E ,L...., KK where Cj Zzu let g [c1, c2..... ,.k,, the number of times concept Cj occurred in a bag, and outputs a class label E {-1, 1, for negative or positive bag respectively. Given MIL bag X {xi..... ,,....,,,,,,. let 1 [predicate] be the indicator function that returns if and only if the predicate is true. Then we can express the generalized MIL decision hypothesis space by Equation 1.
cx }) be function that takes in the set of
K (Ü VX'XX
[Mxx) k1 ))
This generalized form can cover multiple different versions of the MIL problem by changing the constraints on the size of the concept class C and the decision function g(-).
In the remaining sub-sections, we will use this framework to specify the MIL model being tested, how the test works, and how an invalid MIL-model can "solve" the problem by violating the constraints. This done by specifying constraints on C and g(-) that define the class of MII. models, and a unit test that checks that these constraints being respected by the algorithm. We will do so by specifying a NegativeSampla and PositiveSample function that returns bags X that should have negative and positive labels respectively. Each function will have an argument called Training, as a boolean variable indicating if the bag is meant to be used at training or testing time. This is because we will alter the training and testing distributions in a manner that should be invariant to valid MIL model, but have a detectable impact on non-MIL models. For this reason, we will refer to data obtained when Training=True as the training distribution and Training=False as the lesting distribution.
In each unit test, our training bags will have a signal that easy to learn but violates the MIL. assumption being tested. There will be a second signal corresponding to the true MII. decision process, that is intentionally (mildly) harder to detect. At test time (i.c., -Training). the casy-but- incorrect signal will be altered in way that does not interfere with the true MIL classification rule.
If a model receives training distribution AUC > 0.5, but testing distribution AUC of < 0.5, then the model is considered to have failed a test. This is because normally degenerate model should receive an AUC of 0.5, indicating random- random-guessing performance. To obtaín an AUC < 0.5 means the model has learned function anti-correlated with the target function. If this occurs simultaneously with an AUC of > 0.5, it means the model has learned the invalid non-MIL bait concept, which is designed to be anti-correlated in the testing distribution.
To simplify the reading of each algorithmic unit test, we will use (a La b) to indicate a vector sampled from the multivariate normal distribution with dimensions that has a mean μ I and a covariance Σ- = Ia b. In all cases, we use d = 16 dimensions, but the test is valid for any dimensionality. In many of our tests, the number of items will be varied, and we denote an integer sampled from the range (a, b] as ~ U(a, b) when an integer is randomly sampled from range. When this value is not critical to the function of our tests, the sampling range will be noted as a comment in the pseudo-code provided.
5

---

3.1 Presence MI Assumption and Test
We begin with the simplest form of the MII. decision model as expressed by Dietterich et al. [46]. In this case, the concept class is unitary with K 1, = {22, 1}, giving the positive classes as the only option, and the non-contributing null-class Ø. The decision function g((c1)) C1 1, that is, the label is positive if and only if the positive concept ej has occurred at least once within the bag.
Given these constraints, we design a simple dataset test to check that an algorithm respects these learning constraints on the solution. We will abuse notation with h(N Ia 1)) == to indicate that the space of samples from normal distribution as specified is defined as corresponding to the null-class 2. This first value will be the general "background class" that is not supposed to indicate anything of importance.
To make learnable but not trivial class signal, we will have two positive class indicators that never co- occur in the training data. Half will have (N La
Algorithm Single-Conceps Standard-MIL.
1: function MPPLLTVVES
3)) = Ci and the other half will have ((N(1, La 1)) = c1. We remind the reader that this a normal distribution in d-dimensional space, so it is not challenging to distinguish these two classes from the background class (0, La 1), as any one dimension with value 2 becomes a strong indicator of the cj class.
2: if T'Trinnin then // Poisoning
3: Add ~ (N Ia 0.1) to bag X
4: for b iterations do
5: Add x ~ (O, la 1) to bag X
6: return X, y = -1
7: function
Finally will have poison class h(N(-10, La 0.1))= = Ø that is easy to distinguish from all other items, and training time always occurs in the nega- tive classes only. If we let g(-) and h(-) represent the MIL-violating class-concept and decision function
8: if -Trainnng then // Poisoning
Add y ~ Ia 0.1) to bag X
10:
for i iterations do// k ~ (11,4)
11:
c - coin flip
12:
if c is True then
that should not be learned. This creates an easier-to-
13:
x x~ S=, Ia
learn signal, where h-N 0.1)) = Ø and the remaining spaces (o, 1)) h(, Ia-3))
14:
else
15:
x N11, Ia
L( 1)) C1 with decision function of (((8,a)) == Ø S O. This ğ is easier to learn, but violates the MIL assumptions by looking for the ab- sence of an item (the Ø class) to make prediction. It is again critical remind the reader that the MIL learning problem is asymmetric - we can not arbi- trarily rs-asnign the roles of Ø and Cı, and so ğ(-) A g(-) because we can not use in place of et.
16:
Add x to bag X
17:
for b iterations do
18:
Add x ~ (O, Ia 1) to bag X
19:
return X, y =
The entire algorithmic unit test is summarized in Alg. 1, that we term the Single- Standard- MIL Test. We choose this name because there is single concept-class e1 to be learned, and this test checks obedience to the most basic MIL formulation.
Because this test is subset of all other MIL generalizations, any algorithm that fails this test is not respecting the MIL hypothesis.
Theorem 1. Given an algorithm A(-): X + R. if trained on Alg. 1 and lested on the corresponding distribution. A fails to respect the MIL hypothesis if the truining AUC is above 0.5, and the test AUC is below 0.5.
Proof. 9((0,c1)) c1 2 is the target function. Using Øp to represent the background poison
signal and BB to represent the indiscriminate background noise. Let é denote the A((0, La 3) samples and é the N la 1) samples. The training distribution contains negative samples (y -))
of the form {Øp = 1, Bb). and positive samples (y = 1) of the form {ØB 2 1, = 1} and {Ø 2 1, = 1}.
By exhaustive enumeration, only two possible logic rules can distinguish the positive and negative bags. Either the (MIL) rule é 2 v è > 1 = 2 1 (where +- é V 0g which is allowed under [46)) or the non-MII. rule 60, = 0. However, a MIL. model cannot legally learn to use 2s because occurs only in negative bags.

---

Thus if the training distribution has an AUC > 0.5 but test distribution ACU < 0.5, it has learned the non-MIL rule and failed the test.
3.2 Threshold-basee MI Assumption and Tests
Algorithm Multi- Contcpt Standard-
1:
function if Training then// Poison
We now turn to the threshold-based MIL assumption,
2:
of which the presence- based assumption is a sub-set set-set.
3: Add p ~ ~ La 0.1) to bag X
In this case, we now have variable number of con- cept classes K, and we have a minimum threshold la for the number of times a concept-class CR is ob- served. Then Vk E [1, K] it must be the case that Ca 2 l for the rule to be positive. More formally,
4: f coin flip
if is True then
6: x ~ N22 La 0.1)
else
we have = {22, 1, .,....K, K} and we define the de-
8:
x M33, La -0.1)
cision function g()) as:
Add x to bag X
10: for b iterations do // b ~ ((1, 10)
11: Add (O La 1) to bag X
g O2. .k)) = Ck tk
(2)
12:
return X, y/ = -
13:
function POSITIVES if -Training then// Poison
where A is the logical "and" operator indicating that
14:
all K predicates must be true. It is easy to see that the ressence-based MIL is a subset by setting 1 = and to 0, Ak > 1. Thus any case that fails Alg. 1 is not a valid Threshold MIL model, even if it passes the test we devise. We will implement two different tests that check the ability to learn a threshold-MHI model.
15:
Add p ~ ( 10, Ia 0.1) to bag X
16:
for iterations do// l: ~ (1(1 4)
17:
Add (2,, La 0.1) to bag X
18:
Add x ~ (3,, La 0.1) to bag X
19:
for b iterations do // b U(1, 10)
20:
Add x ~ (O, Ta 1) to bag X
3.2.1 Poisoned Test
21:
return X, y =
For our first test, we use similar "poison" signal h(N La 0.1)) = Ø that easier to classify but would require violating the threshold-MIL decision function in Equation 2. This poison occurs perfectly in all negative bags training time, and switches to positive bags at test time.
For the threshold part of the assumption under test, we use a simple K = 2 test, giving C = ( 1,2) The two exemplars of the classes will have overlap this time, given by h(V 0.1)) = ci and h(W Ia 0.1)) == C2, with one item selected at random occurring in every negative bag, and both items occurring between 1 and 4 times in the positive labels. This tests that the model learns that 4 = L2 = 1. Last, generic background instances h(NNO,, La 1)) = Ø occur in both the positive and negative bags. The overall procedure is detailed in Alg. 2.
As with the presence test, the MIL-violating decision function g( [8, c₁ (2,c) = co S 0 to indicate a positive label, which is looking for the absence of a class to make positive label, fundamentally violating the MIL hypothesis.
Though this test is fundamentally a similar strategy to the presented unit test, the results are sig- nificantly different, as we will show in $ 4. This test will help us highlight the need produce algorithmic unit tests that capture each property we want to ensure our algorithms maintain.
Theorem 2. Given an algorithm A(-): : X + R, if trained on Alg. 2 and tested on the corresponding distribution. A fails to respect the threshold MIL hypothesis if the training AUC is above 0.5, and the test AUC is below 0.5.
Proof. See appendix, structurally similar to proof of Theorem
3.2.2 False-Frequency Reliance
Our last test checks for different kind of failure. Rather than violation of the MIL hypothesis entirely, we check that the model isn't 't learning a degenerate solution to the threshold-MII model.
To do so, we will again use K- = 2 classes as before, so the decision function 9(-) does not change with the same l = l2 = thresholds, with the same positive instances (2, Ta 0.1)) = e₁ and h(NV(22,14 la 0.1)) = c2. The negative training bags X will include one or two samples of
7

---

either 01 or 02, not both. The positive training will contain one or two samples of each e1 and C2. This gives direct example with no extraneous distractors of the target threshold-MII model, g((er,e2) = (er > 41) A (e2 > /2).
However, it is possible for a model that is not well aligned with the MIL model to learn a degenerate solution h that maps (2, la 0.1)) = ei and (-N(-2, Ta 0.1)) = c1, and thus learns an erro- neous (((c1,0)) = > fg. While this solution does respect the overall MIL hypothesis, indicates a failure of the model to recognize two distinct con- cept classes 61 and C2. and thus does not fully satisfy the space of threshold-Min
Algorithm 3 False Frequency MIL Test
1:
function NECATIIESAAPLEECTannng if -Trainnng then
2:
I U(3, 40)
4:
else
((1,2)
6: C + coin flip
solutions.
for t iterations do
Theorem 3. Given algorithm A()
R. if trained on Alg. 3 and tested on the corresponding distribution. A fails respect the threshold MIL. hypothesis if the training AUC is above 0.5, and the test AUC is below 0.5.
8:
if c is True then
Add ((-2, 0.11 to bag X
10:
else
11: Add x M2, Ta 0.1) to bag X
12:
for b iterations do // b ~ (11, 10)
13: Add x (O, Ia 1) to bag X
14:
return X, y =
Proof. See appendix, structurally similar to the proof of Theorem
15:
function POSITIVESAMPLEL for t ~ 2(11 iterations do
16:
17: Add x ~ ( 2, Ia 0.1) to bag X
Results
18:
for l ~ (4, iterations do
19:
Add x ~ ~2 la 0.1) to bag X for b iterations do // b ((1, 10)
We will now review the results of our three unit tests
across both deep-MIL models and prior SVM based
20:
MIL algorithms. In every deep learning case, we
21:
Add x ~ (O, Ia 1) to bag X
generate 100,000 training bags with 10,000 test bags.
22: return X, y
Each model was trained for 20 epochs. Each network was trained using the Adam optimizer using three layers of the given deep model type. We found this was sufficient for each model type to nearly perfectly learn the training set, with the exception of the Hopfield network that struggled to learn under all tests even in extended testing with varying layers and model sizes.
For the SVM models the O(N3) training complexity limited the training size. MissSVM and MICA were trained on only 200 samples because larger sizes took over a day. All others were trained on 1,000 samples. A test set of 10,000 was still used. For each SVM model, we use a Radial Basis
where y set to be 0.100 in all tests. This value was found by running each algorithm on a sample of N = 50 training bags across each of the training sets, to find single value of y from 10-1 to 10s that worked across all SVM models and tests. This was done because the SVM results took hours to run, and obtaining the best possible accuracy is not goal. The point of our tests is to identify algorithms that appear learn (high training numbers) but learn the wrong solution (< 0.5 test AUC). For this reason, a simple and fast way to run the algorithms was more important and equally informative.
Function (RBF) kernel K (x,x') exp (-> ||x 1
x 11]x-x(13
In our experiments, the only models known and designed to conform to the standard Presence MIL assumption are mi-Net, mi-SVM. MI-SVM, and MissSVM. For this reason, we expect these models to pass the first test of Alg. 1. We note that none of the models being tested was designed for the Threshold MI assumptions that comprise the second two tests. Still, we will show how the results on the Threshold tests are informative to the nature of the model being investigated. We remind the reader that each unit test can be solved perfectly by model respecting the appropriate MII. assumptions.
4.1 Presence Test Results
Our initial results are in Table 2, showing the training and testing accuracy and AUC for each algorithm against the unit test described by Alg. 1. All deep-MIL models introduced after mi-Net [33] and tested here have failed the test, with the exception of [44]. This makes the increased accuracyfiprrovement
8

---

on MIL problems of many prior work suspect. This because any test could be learning to check for the absence of feature, violation of the MII. assump- tion that Alg. 1 tests, and thus learning the kinds of relationships that are explicitly forbidden by the hypothesis space.
Table 2: Results for the standard MIL assump- tion test Alg. 1. Any algorithm that fails this test (testing AUC < 0.5) is fundamentally invalid as a MIL algorithm under all circum- stances, and should not be used in cases where the MIL assumptions are important. Failing algorithms are shown in italics.
The results of the older SVM literature are interesting. As noted by Foulds and Frank [27], the NSK and STK models are not actually MIL-respecting, and thus fail the test. However, the SIL model was explicitly de- signed to ignore the MIL assumption, yet still passes this test. The MICA algorithm, while not designed to ignore MIL. explicitly is not designed to enforce either, so it also passes the test. While the MIL. respecting MissSVM passes but only marginally.
Training
Testing
Algorithm
Acc.
AUC
Acc.
AUC
mi-Net Net
0.991
0.998
0.993
1.000
MI-Net
1.000
1.000
0,000
0,000
MIl.-Pooling
1,000
1.000
0.000
0.000
Tran-MII.
1.000
1.000
0.000
0.000
GNN-MIT.
1,000
1.000
0.000
0.000
CausalMIL
0.999
0.999
0.996
1,000
We find these results informative and instructive. They demonstrate that algorithmic unit tests are not certificates of correctness. Rather, failure of these tests is a certificate of an errant algorithm, but may produce false positives. While the design of more powerful test is beyond the scope of this article, the work presented here provides practical caveats for the use of such tests in future studies. Any future MIL. pa- per can use the tests and provide results to the reader to help boost confidence, but the test should not itself be used means of proving the correctness.
Hopfield
0.624
0.495
0.500
0.488
Mi-SVM
0,999
1.000
0.935
1.000
MI-SVM
1.000
1.000
0.986
1,000
SIL
0.992
1.000
0.766
0.998
NSK
1.000
1.000
0.000
0.000
STK
1,000
1.000
0.466
0.000
MICA
0,500
1.000
0.500
1,000
MissSVM
0.995
1.000
0.449
0.551
Of note, CausalMIL is the only recent deep-MIL model we evaluated which is designed to respect the standard MIL assumption, and passes the test accordingly. While CausalMIL was not designed for the threshold MII., it still passes the next two tests - but with marginal AUC, near 0.5. This reasonable since it is testing a scenario beyond CausalMIL's design. Indeed it would be acceptable even if CausalMIL. failed the next tests, because they are beyond its scope (which happens to mi-Net). The goal is that models are tested to the properties they purport to have.
Table 3: Results for the Threshold MIL as- sumption test Alg. 2. Any algorithm that fails this test (testing AUC < 0.5) learns the invalid relationship that the absence of an instance indicates a positive label. Failing algorithms are shown in italics.
Training
Testing
Algorithm
Acc.
AUC
Acc.
AUC
mi-Ner
0.735
0.999
0.500
0.000
MI-Net
0.991
0.807
0.000
0.827
MIL-PPoliing
0.999
1.000
1.000
1.000
Tran-MIL
0.955
0.949
0.500
0,000
GNN-MIL.
0.978
0.997
0.624
0.678
4.2 Threshold Results
CausalMII.
0.717
0.745
0.500
0.500
Hopfield
0.624
0.540
0.500
0.503
Our next two unit tests cover two different aspects of the Threshold MIL assumption: 1) that they can learn to require two concepts to denote positive class, and
mi-SVM
0,500
0.857
0,500
0.818
MI-SVM
0.759
0.887
0.727
0.828
SIL
0.500
0.861
0.500
0.732
2) that they do not degrade to relying on frequency
NSK
1.000
0.889
0.889
0.966
(i.e., perform the desired counting behavior of each class). Any algorithm that passes either of these tests,
STK
0.947
0.991
0,000
0,000
MICA
0,500
0.998
0.500
0.490
but fails the Presence test, is still an invalid MIL. algorithm by both the Presence and Threshold models because the Presence MIL model is subset of the Threshold model.
MissSVM
0.640
0.943
0.499
0.763
The results of our first test of Alg. 2 on learning two concepts are shown in Table 3, where only the MIL-Pooling model learns the completely correct solution. This test is most valuable in showing how mi-Net, which is valid Presence MIL model, is not valid Threshold MIL model, reaching AUC of O.
One may wonder why the mi-Net performs poorly, while the mi-SVM and MI-SVM pass the test with peculiar results. In the case of the mi-SVM, its label propagation step means that instance (2, la 0.1) and instance ~ N/, la 0.1) will receive inferred negative labels (from negative

---

bags), and positive labels (from positive bags). There are proportionally more ~ N Ia 0.1) samples with positive labels, though, and each positive bag. by having more samples, can select the most-extreme data point (largest positive values in each coordinate) to infer that the positive hags are "more positive" than a negative bag. This results in non-trivial AUC of 82%. In the mi-SVM case, the 50% accuracy remains because the overlapping and conflicting labels cause the optimization of the slack terms Ç to become degenerate. Because the MI-SVM does not result in conflicted labels by using the "witness" strategy, it instead can respond to the most maximal item in bag learning to key off of the most right-tail extreme values of ~ (3,, la 0.1) to indicate a positive label, because the positive bags are more likely to have such extreme values by having more samples, and avoiding the conflicting label problem of mi-SVM.
By contrast, the mi-Net model fails due to the increased flexibility of the neural network to learn a more complex decision surface, "slicing" the different maximal values to over-fit onto the training data, resulting in degenerate performance. Note that mi-Net's results do not change with the removal of the poisoned item at test time, as otherwise, its accuracy would degrade to zero. The MI-Net instead suffers from this problem, and by using the poison token ironically learns a less over-fit solution, allowing it to obtain a non-trivial AUC.
Table 4: Results for the Treshold MIL as- sumption test Alg. 3. Any algorithm that fails this test (testing AUC < 0.5) is not able to learn that two concepts are required make a positive bag. Failing algorithms are shown in italics.
The discussion on why mi-SVM and MI-SVM are able to pass the Alg. test is similarly instructive as to why they perform worse on the Alg. 3 test as shown in Table This test checks that the models do not learn to "cheat" by responding to the magnitude of the values or the frequency of a specific concept class occurrence. Because the frequency of concept classes changes from train-to-test, {mi, MIJ-SVMs learn to over-focus on the magnitude of coordinate features to indicate a positive direction, which inverts at test time. Thus the performance of both methods drops significantly, and the mi-SVM ends up failing the test.
Training
Testing
Algorithm
Acc.
AUC
Acc.
AUC
mi-Net
0.689
0.744
0.740
0.496
MI-Net
0.957
0.992
0.500
1.000
MIL-Pooling
0.997
0.999
0.500
0.477
Tran-MIL
0.989
0.998
0.994
1.000
GNN-MII.
0.965
0.995
0.475
0.000
We also note that between the two Threshold tests, we see different algorithms pass/fail each test. MIL. Pooling, Mran-MIl. and STK, and NSK have dramatic changes in behavior from test test. By developing unit tests that exercise specific desired properties, we are able to immediately elucidate how these algo- rithms fail to satisfy the Threshold-MIL- assumption.
CausalMIL
0.688
0.752
0.496
0.602
Hoplield
0.625
0.493
0.500
0,515
mi-SVM
0.500
0.738
0.500
0.054
MI-SVM
0,770
0.875
0.511
0.518
SIL
0.500
0.778
0.500
0,180
NSK
1.000
1.000
0.500
0.000
STK
1,000
1.000
0.996
1.000
Because Tran-MIL and STK pass Figure 3 but fail Figure 2, we can infer that both Tran-MIL and STK able to successfully learn the concept that "two concepts are required to occur" property, but are also able to learn to detect the absence of an instance as positive indicator, and so fail the test.
MICA
0,985
0.999
0.482
0.481
MissSVM
0.785
0.935
0.327
0.093
5 Conclusion
Our article has proposed the development of algorithmic unit tests, which are synthetic training and testing sets that exercise a specific learning criterion/property of algorithm being tested. By developing three such unit tests for the Multiple Instance Learning problem, we have demonstrated that only one post-2016 deep-MIL algorithm that tested, CausalMIL, appears to actually qualify as a MIL model. We conclude that this is because the algorithms were designed without verifying that the MIL assumptions were respected.
Acknowledgements
We would like to thank the reviewers of this work for their valuable feedback that has improved this paper. We note that some formatting changes were attempted but we could not make them a readable
10

---

font and within the page limits, and so we apologize that the formatting requests could not be fully satisfied.
References
[1] G. D. Poore, E. Kopylova, Q. Zhu, C. Carpenter. S. Fraraccio, S. Wandro, T. Kosciolek, Janssen, J. Metcalf, S. Song. Kanbar, S. Miller-Montgomery. R. Heaton, R. Mckay, Patel, A. D. Swafford, and R. Knight, "Microbiome analyses of blood and tissues suggest cancer diagnostic approach," Nature, vol. 579, no. 7800, pp- 567-574, Mar. 2020. [Online]. https://doi.i orr.oiiorrr/////// wwwp///.//////////. 10011088/44156-00002200000
Available:
[2] A. Gihawi, Y. Ge, J. Lu, D. Puiu, A. Xu, C. S. Cooper, D. S. Brewer, M. Pertea, and S. L. Salzberg, "Major data analysis errors invalidate cancer microbiome findings," mBio, Oct. 2023. [Online]. Available: https::/ddi.org/ 0. 128/mmio. 01600022200
[3] G. Varoquaux and V. Cheplygina, "Machine learning for medical imaging: methodological failures and recommendations for the future," npj Digital Medicine, vol. 5, no. 1, Apr. 2022.
[Online]. Available: https://doi.org/ 10. 10.1008//41770 00050/44176-0220052227 022-00592-y
[4] L. Wynants, B. V. Calster, G. S. Collins. R. D. Riley, G. Heinze, E. Schuit, Albu, B. Arshi,
V. Bellou, M. M. J. Bonten, D. L. Dahly. J. A. Damen, T. P. A. Debray, V. M. T. de Jong, M. Vos, Dhiman, Ensor, S. Gao, M. C. Haller, M. Harhay, Henckaerts, P. Heus,
J. Hoogland, M. Hudda, K. Jenniskens, M. Kammer, N. Kreuzberger, A. Lohmann, B. Levis,
K. Luijken, Ma, P. Martin, D. McLernon, C. A. Navarro, J. B. Reitsma, C. Sergeant, C. Shi, N. Skoetz, L. J. M. Smits, K. I. E. Snell, M. Sperrin, R. Spijker, E. W. Steyerberg, Takada, I. Tzoulaki, S. M. van Kuijk, B. T. van Bussel, C. C. van der Horst, K. Reeve, F. S. van Royen, J. Y. Verbakel, C. Wallisch, J. Wilkinson, R. Wolff, L. Hooft, K. G. M. Moons, and M. van Smeden, "Prediction models for diagnosis and prognosis of covid- systematic review and critical appraisal." BMJ, p. m1328, Apr. 2020. [Online]. Available: https://doi.org/100 1e1111.11111bmm. 1136//mj..m.....
[5] W. Fleshman, E. Raff, J. Sylvester, S. Forsyth, and M. McLean, "Non-negative networks against adversarial attacks," 2019.
[6] I. n. incer Romeo, M. Theodorides, S. Afroz, and D. Wagner, "Adversarially robust malware detection using monotonic classification," in Proceedings of the Fourth ACM International Workshop on Security and Privacy Analytics, ser. IWSPA '18. New York, NY, USA: Association for Computing Machinery, 2018, p. 54-63. [Online]. Available: http://doi.org//II 1 //t.://.....r//1..11144/1114444 104431
[7] D. Lowd and C. Meek, "Good word attacks on statistical spam filters." CEAS, 2005. [Online]. Available: http://lw.uiiiiieeeeeedd///meeee
[8] J. Stiborek, T. Pevný, and M. Rehák, "Multiple instance learning for malware classification," Expert Systems with Applications. vol. 93, pp. 346-357, mar 2018. [Online]. Available: if..
[9] T. Pevny and M. Dedic, "Nested multiple instance learning in modelling of http network traffic," 2020.
[10] Z. Jorgensen, Y. Zhou, and M. Inge, "A multiple instance learning strategy for combating good word attacks on spam filters." " Journal of Machine Learning Research, vol. 9, no. 38, pp. 1115 155-1144 146, 2008. [Online]. Available: http:///mllloory/paapeess///gggp
[11] L. Beyer, O. J. Hénaff, A. Kolesnikov, X. Zhai, and A. van den Oord, "Are we done with imagenet?" 2020.
[12] B. Barz and J. Denzler, "Do we train on test data? purging CIFAR of near- duplicates." " Journal of Imaging, vol. 6, no. 6, p. 41, jun 2020. [Online]. Available: http://tcino////.33336///emennon
11

---

[13] R. S. Geiger, D. Cope, J. Ip. M. Lotosh, A. Shah, J. Weng, and R. Tang, " ""garbage in, garbage out" revisited: What do machine learning application papers report about human-labeled training data?" Quantitative Science Studies, vol. 2, no. 3, pp. 795-827, 2021. [Online]. Available:
a a_00144
[14] A. F. Cooper, Y. Lu, J. Forde, and C. M. De Sa, "Hyperparameter optimization is deceiving us, and how to stop it," in Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. 3081 1008--300 1-3095. [Online]. Available: paper/202 httpeeeeeeeaaeffeee2299944 Parpoeaa0000aealaaaaaiaaaraarrrp
[15] X. Bouthillier, P. Delaunay, M. Bronzi, A. Trofimov, B. Nichyporuk, J. Szeto, N. Mohammadi Sepahvand, E. Raff, K. Madan, V. Voleti, S. Ebrahimi Kahou, V. Michalski, Arbel, C. Pal, G. Varoquaux, and Vincent, "Accounting for variance in machine learning benchmarks," in Proceedings of Machine Learning and Systems, A. Smola, A. Dimakis, and Stoica, Eds., vol. 3, 2021, pp. 747-769, [Online]. Available: https//proceeddigggmll...oo Paper..df
[16] R. Dror, G. Baumer, M. Bogomolov, and R. Reichart, "Replicability analysis for natural language processing: Testing significance with multiple datasets," Transactions of the Association for Computational Linguistics, vol. 5, pp. 471-486, 2017. [Online]. Available: https//aclanntollogy wwwp://ooooooooo//////--/11 0r7/Q171133
[17] A. Benavoli, G. Corani, and F. Mangilli, "Should we really use post-hoc tests based on
mean-ranks?" Journal of Machine Leurning Research, vol. 17, no. 5, pp. 1-10, 2016. [Online]. Available:
wwwppnnrrrrr/ppps//////saa/ 17tper////////eevoliii 7/beeavoli 6a.html
[18] Demsar, "Statistical comparisons of classifiers over multiple data sets," Journal of Machine Learning Research, vol. 7, no. 1, pp. 1-30, 2006. [Online]. Available:
http://mmltorrgpappps////llmmmmm
[19] K. Ahn, Jain, Z. Ji, S. Kale, Netrapalli, and G. I. Shamir, "Reproducibility in optimization: Theoretical framework and limits," in Advances in Neural Information Processing Systems, Koyejo, S. Mohamed,
Agarwal, D. Belgrave, K. Cho, and Oh, Eds., vol. 35. Curran Associates, Inc., 2022, pp. 18 128-22-188 18 033. [Online]. Available: https//proceedings.eerrjj hbppelllleeoopper22222///////419 2al00000000000000000000033333310 Pf
[20] E. Raff, "A step toward quantifying independently reproducible machine learning research," in Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available: Paper,ddf c429429bf1 1202 Ic92aaeeea--aaaaaai
[21] X. Bouthillier, C. Laurent, and Vincent, "Unreproducible research reproducible," in Proceedings of the 36th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. PMLR, 09-15 Jun 2019, pp. 725-734. [Online]. Available: https: ptw..//.eee///9/7tooooiiii... 19a.html
[22] E. Raff and A. L. Farris, "A siren song of open source reproducibility, examples from machine learning," in Proceedings of the 2023 ACM Conference on Reproducibility and Replicability, ser. ACM REP '23. New York, NY, USA: Association for Computing Machinery, 2023, 115-120. [Online], Available:
[23] M. Ferrari Dacrema, P. Cremonesi, and D. Jannach, "Are we really making much progress? a worrying analysis of recent neural recommendation approaches," in Proceedings of the 13th ACM Conference on Recommender Systems, ser. RecSys '19. New York, NY, USA: Association for Computing Machinery, 2019, p. 101-109, [Online]. Available: http:///oi.or/11.1155533333
3347055
[24] F. Lu, F. Raff, and J. Holt, "A coreset learning reality check," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 7, pp. 8940-8948, Jun. 2023. [Online].
Available: https://doi.or//10. 10. 37779///
12

---

[34] X. Wang, Y. Yan, P. Tang, X. Bai, and W. Liu, "Revisiting multiple instance neural networks," * Pattern Recognition, vol. 74, pp. 15-24, feb 2018. [Online]. Available: 1ttp:/...11122Fjj.p.o. [25] M.-A. Carbonneau, V. Cheplygina, E. Granger, and G. Gagnon, "Multiple instance learning: A
survey of problem characteristics and applications," Pattem Recognition, vol. 77, pp. 329-353, May 2018. [Online]. Available: https://doi.or//10 1ttp://00011111..aaaaaa.. 1016//.patcog.201111.0000
[26] D. Grahn, beilhbbnnchmrks: Standardized evaluation of deep multiple-instanee learning tech- niques," 2021.
[27] J. Foulds and E. Frank, "A review of multi-instance learning assumptions," The Knowledge Engineering Review, vol. 25, no. 1, pp. 1-25, mar 2010. [Online]. Available: https://doi.org/10.. wttp:://ww.....00000//0000099990
[28] S. Andrews, Tsochantaridis, and T. Hofmann, "Support vector machines for multiple-instant learning." in Advances in Neural Information Processing Systems, S. Becker, S. Thrun, and K. Obermayer, Eds., vol. 15. MIT Press, 2002. [Online]. Available: https://roceedinng. neurips.cc/paper_flesssiss hwt.cppppeeiiiiseeeeeeee/efeeeeo hacp:// 898heacda3d 6db379ed3329 Paper.pdf
[29] S. Ray and M. Craven, "Supervised versus multiple instance learning," in Proceedings of the 22nd international conference Machine learning ICML '05. ACM Press, 2005. [Online]. Available: https://doi.or wrapoooooorg/....0
10.1/00.1111 11..1......FF. (445%F2F1225 10235
[30] Z.-H. Zhou and J.-M. Xu, "On the relation between multi-instance learning and semi-supervised learning," in Proceedings of the 24th International Conference on Machine Learning, ser. ICML '07. New York, NY, USA: Association for Computing Machinery, 2007, p. 1167-1174.
[Online]. Available: https://doi.orr//000 14511//2774 1273643
[31]
"On the relation between multi-instance learning and semi-supervised learning." in Proceedings of the 24th international conference on Machine learning. ACM, jun 2007.
[Online]. Available:
[32] O. L. Mangasarian and E. W. Wild, "Multiple instance classification via successive linear pro- gramming," Journal of Optimization Theory and Applications,, vol. 137, no. 3, pp. 555-568, dec 2007. [Online]. Available: https://doi.org// wwt.:/oiiir/1110.11111.1111 0000000000000000
[33] Z.-H. Zhou and M.-L.. Zhang, "Neural networks for multi-instance learning," in Proceedings of the International Conference on Intelligent Information Technology, Beijing, China. Citeseer, 2002, pp. 455-459.
[35] M. Ilse, J. Tomczak, and M. Welling, naatenttion-basee deep multiple instance learning," in Proceedings of the 35th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, J. Dy and A. Krause, Eds., vol. 80. PMLR, 10-15 Jul 2018, pp. 2127-2136. [Online]. Available: http::/ppoeeddigg...rrrrssvvioi wtt.. 1 html
[36] M. Tu, J. Huang, X. He, and B. Zhou, "Multiple instance learning with graph neural networks." 2019.
[37] Z. Shao, H. Bian, Y. Chen, Y. Wang, Zhang, X. Ji, and y. zhang, "Transmil: Transformer based correlated multiple instance learning for whole slide image classification,"" in Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, Eds., vol. 34. Curran Associates, Inc., 2021, pp. http:/ppooeediig....errss..//pee htt.ge/g..eei.i.ecoooooeeeee/eee 2136-2147, [Online]. Available: Pappep
[38] M. Widrich, Schäfl, M. Pavlović, H. Ramsauer, L. Gruber, M. Holzleimer, J. Brandstetter, G. K. Sandve, V. Greiff, S. Hochreiter, and G. Klambauer, "Modern hopfield networks and attention for immune repertoire classification," in Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, Eds., vol. 33. Curran Associates, Inc., 2020, pp. 18 832-18 845. [Online]. Available: http://roceeddngss.euiiisscoe paper wttp://ppcee//////aaaaaaoooooo.. Pappp
13

---

[39] S. Pal, A. Valkanas. F. Regol, and M. Coates, "Bag graph: Multiple instance learning using bayesian graph neural networks," " Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 7, pp. 7922-7930, Jun. 2022. [Online]. Available: http://os...aa..or/nneee. whtp:pppp///aaaaa Allarticcee/vieew/2076...
[40] Y. Yan, X. Wang. X. Guo. J. Fang, W. Liu, and J. Huang, "Deep multi inltiiinsttnce learning with dynamic pooling." in Proceedings of The 10th Asian Conference Machine Learning. Proceedings of Machine Learning Research, J. Zhu and I. Takeuchi, Eds., vol. 95. PMLR, 14- 16 Nov 2018, pp. 662-677. [Online]. Available:
ha.html
[41] Y. Lin, M. Moosaei, and H. Yang. "OutfitNet: Fashion outfit recommendation with attention- based multiple instance learning," in Proceedings of The Web Conference 2020. ACM, apr 2020. [Online]. Available: https::/doi.org/// 215
[42] X. Shi, Xing, Xie, Z. Zhang, Cui, and L. Yang. instance learning," Proceedings of the AAAI Conference on Artificial Intelligence, vol. 34, no. 04, pp. 5742-5799 apr 2020. [Online]. Available: https://doi.org/IV 1609% 2Faaai v34104.6030
attention for deep multiple
[43] K. Thandiackal, Chen, Pati, G. Jaume, D. F. K. Williamson, M. Gabrani, and O. Goksel, "Differentiable zooming for multiple instance learning whole-slide images," in Lecture Notes in Computer Science. Springer Nature Switzerland, 2022, pp. 699-715. [Online]. Available:
https://doi.org/100 1007%12977---0000 3-1778-3--31---1 19803-8. 41
[44] W. Zhang, X. Zhang. h. deng, and M.-L. Zhang, "Multi-instance causal representation learning for instance label prediction and nul-of-distribution generalization." in Advances in Neural Information Processing Systems, S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, Eds., vol. 35. Curran Associates, Inc., 2022, pp- 34 94044404499 953. [Online]. Available: https://proceedings.. wwtp:es.ecrpeppppppp...ee httpp/sccppppppelcsppppppppe files/paper/2222/ille/ hate:92eeeeeob0aa000eeeeeeBeeee Paacecadd-Pppee-ee Paper- Senerr-Coffrenee.p..
[45] W. Zhang, L. Liu, and J. Li, Robust Multi- Instance Learning with Stable Instances. IOS Press, 2020, p. 1682-1689, citation Key: Available:
[Online].
[46] T. G. Dietterich, R. H. Lathrop, and T. Lozano-Párez, "Solving the multiple instance problem with axis axis-parallel rectangles," Artificial Intelligence, vol. 89, no. 1-2, pp. 31-71, jan 1997. [Online]. Available: https://doi.org// 10.
[47] N. Weidmann, E. Frank, and B. Pfahringer, "A two-level learning method for generalized multi-instance problems," in Machine Learning: ECML 2003. Springer Berlin Heidelberg, 2003, pp. 468-479. [Online]. Available:
14

---

A Proofs
Proof of Theorem
Proof. g((0,c1, c2)) (2))) = 2 A 02 2 1 is the target function. Using 2p to represent the background poison signal and Ø to represent the indiscriminate background noise, The training
1} and (2,p (0, 1, 2 1, 02 1], and positive samples (y 1) of the form (23 2 C1 = 1, =
distribution contains negative samples (y = -1) of the form { = R 2 1,
=)-
=
By exhaustive enumeration, only two possible logic rules can distinguish the positive and negative bags. Either the (MIL) rule e₁ 2 1 A c 2 and the non-MIL rule 2n However, MIL model cannot respect the MIL hypothesis and learn to use Øp simultancously, because Øp occurs only in negative bags.
By changing the test distribution to evaluate the sample Øg = 1, 1. = and observing the model produce the negative label y -1, the only possible conclusion is it has learned the non-MIL hypothesis.
Proof of Theorem
2 1A 2 is the target function. Using ØB to represent the indiscriminate background noise, The training distribution contains negative samples (y -1) of the form {Øg E [1, 10], c1 e [1. [ and {ØB E [1, 10), 02 E [1, and positive samples (y 1) of the form {Øx E [1, 10], cr [1,2], c2 E []]
Proof. 9([0, cı, c2})
By exhaustive enumeration, only two possible logic rules can distinguish the positive and negative bags: C1 2 1 0 2 1. However, there is naive MIL rule that can obtain non-random, but not perfect accuracy, 61 + C2 2 3.
By changing the test distribution to evaluate the samples Øn = 1, 2 35 and Øn 1, 02 2 35 and observing the model produce the positive label y = 1, the only possible conclusion it has learned the non -hrthhreshold MIL hypothesis.
15


Reviews:
[{"review_id": "59WG2H4KBP", "reviewer": "Reviewer_6q8u", "summary": "The paper deals with multiple instance learning (MIL), where a collection of items is considered in a bag/collection, whereby presence of certain items in the bag implies a positive label for the whole collection, and otherwise the collection has a negative label. The paper discusses prior MIL methods that do not respect implicit MIL assumptions (i.e., learning a degenerate solution), and proceeds to develop algorithmic unit tests to check if a model satisfies those. Their main contribution is:\n\n1. Designing a unified framework for checking MIL assumptions by creating synthetic datasets that check for one or more of the implicit MIL assumptions\n2. Running experiments to show how often algorithms fail these tests despite being the most recent ones.\n3. Arguing that not passing these tests means a model is not performing MIL correctly, however, passing these tests does not imply certification.\n", "questions": "1. Line 163, is $g(\\{c_1, \\ldots, c_K\\})$ a function or a value of the function at a particular point? What is its domain and range? A better notation would be $g: N_{\\geq 0}^d \\rightarrow \\{+1, -1\\}$.\n2. Line 250, why is the presence based test needed if it is a subset of the threshold based test? An explanation should be included in the main paper. \n3. Line 209, How does $N(0, 3)$ denote a normal distribution in d-dimensional space? What does 0 and 3 refer to here?\n4. Line 304, “learn a noisy but erroneous …”, not sure what is the difference between a noisy and erroneous function, I assumed noise → erroneous?\n5. I would be curious to see some sort of exploration with real-world MIL benchmarks (instead of the synthetic datasets used here), why do they not check for these MIL assumptions/why would good performance on these benchmarks not correlate with satisfying MIL assumptions? What does that tell us about the MIL problem setting in general/prior benchmarks?\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem setting and idea is generally interesting. The work seems novel with detailed experimentation.", "weaknesses": "I believe the paper’s writing/organization can be improved. For example:\n1. Lines 51-66 discusses the paper’s sections. It would strengthen the paper if instead the paper discusses at least a few of the algorithmic unit tests/MIL assumptions that would give the reader a better understanding of what the paper is trying to do. Reading the introduction does not give specific information like this. Also highlighting how an example popular MIL method fail an important MIL assumption would also make the introduction much more intriguing.\n2. Also, **there is no mention of reproducibility in the whole paper other than the title and related work**. I am genuinely curious about how reproducibility is related to the algorithmic unit tests here, or what “reproducibility” means in this context. some clarification from the authors would be important.\n3. The paper is missing a “preliminaries” section, and it is not self-contained. It ought to contain a section describing the problem setup of MIL.\n\nAlso I think the theorems are rather straightforward and do not contain any particularly interesting insight. They can be seen as **tautological** with the constructed tests.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are at response limit. Please let us know if anything was not satisfied. \n\nQ1: $g()$ is a function, the domain is $\\forall k \\in [1, \\ldots, K]$ that $c_k$ is an integer $\\geq 0$ (though it could be relaxed to a continuous non-negative as well, this has no impact on our results, but MIL is commonly thought of in integer counts). We believe your notation proposal is correct, though we have not seen in used in the MIL literature off the top of our heads. We are happy to consider this notation alternative. \n\nQ2: The presence test is needed because an algorithm may only be designed to satisfy the presence version of the MIL problem. This occurs with the `mi-Net` algorithm, which is designed for and passes the presence test, but fails the threshold test. `mi-Net` indeed satisfies all algorithmic claims it makes, and so should not be \"penalized\" for failing the threshold test. \n\nThis is relevant in the malware case: if one malicious function is present at all, the binary is malicious. The \"amount\" of malicious content does not change this fact. In the clinical case, sometimes thresholds are the critical differentiator. e.g., mold is present and measurable in all places, but is only considered a problem if the amount measured is beyond an acceptable threshold. \n\nQ3: This denoted a $d$ dimensional normal where the mean $\\boldsymbol{\\mu} = [0, 0, \\ldots, 0]$ and the covariance $\\Sigma = I_d \\cdot 3$. Based on your and reviewer BYpB's feedback we will revise the paper to use a notation of $\\mathcal{N}(\\vec{0}, I_d \\cdot 3)$ to make it clear that the mean is a vector with a diagonal covariance. \n\nQ4: The reviewer's point is well taken, our verbiage was redundant in this context since the problem can be solved without any noise, and so any level of noise would imply at least a degree of error. We will revise it to just \"erroneous\" in that section. \n\nQ5: The CausalMIL work (citations 32, 33 in the article) has already shown empirically that respecting the MIL assumptions can lead to significant gains in accuracy. It would be hard to adapt our benchmarks to \"real world\" data because we would need to label the bag-level information for every data point to construct our testing approach. The benefit of synthetic tests like this are:\n\n1. Once it is shown to fail, it does not matter what any other dataset may look like, because an existence certificate of non-MIL behavior has been achieved. \n2. This makes it easy to apply our tests to any MIL model (e.g., many computer vision-based MIL algorithms would be hard to adapt to NLP/cyber security problems). \n\nWe have added new text to an all-reviewer rebuttal that we believe will satisfy this concern. \n\n> Lines 51-66 discusses the paper’s sections. It would strengthen the paper if instead the paper discusses at least a few of the algorithmic unit tests/MIL assumptions that would give the reader a better understanding of what the paper is trying to do. Reading the introduction does not give specific information like this. Also highlighting how an example popular MIL method fail an important MIL assumption would also make the introduction much more intriguing.\n\nAlg. 1 and 2 test the fundamental property of the MIL hypothesis: that you can not make a positive prediction ($y =1$) based on the absence of an instance $\\boldsymbol{x}_i$  from the larger bag $X$. The difference between them is that in Alg. 1, there is only one instance necessary to make a bag label become positive. In Alg. 2, there are two instances that must occur for a positive label. This distinction is important as it sperates two versions of the MIL problem: the Standard MIL (Alg 1) and Threshold MIL (Alg 2). \n\nAlg 3 tests that a Threshold MIL algorithm must be able to count and recognize two different items to detect a positive bag. \n\nAs an example of how an algorithm can fail the MIL model, consider the case of cancer detection. The goal is to detect any _instance_ of a cancerous cell, which indicates the whole sample (i.e., _bag_) is infected. However, noise in the data may cause spurious items to correlate with a non-cancerous prediction: mislabeled data, artifacts from the imaging equipment, the tool used for excising the sample, the clinician who collected the samples, and more could correlate with a benign prediction. A non-MIL model is free to learn to use these spurious anti-correlated features. But in deployment, the physician, hospital, and equipment, all change -- and so the non-MIL model's accuracy may drop. Indeed, the failure of medical ML models to generalize has been a noted problem (see all-reviewer citations), and so ensuring MIL assumptions can help avoid these high-risk failures. \n\nWe will add all the above to the introduction. \n\n> Also, there is no mention of reproducibility in the whole paper other than the title and related work. I am genuinely curious about how reproducibility is related to the algorithmic unit tests here, or what “reproducibility” means in this context. some clarification from the authors would be important.\n\nMany papers that study reproducibility focus not on generating the same results, but on issues in procedure that would prevent robust conclusions about utility. This includes methodological issues like not tuning baselines [1], or insufficient statistical tests [2]. Our work falls in this latter group of identifying a methodological issue, in not validating the hypothesis constraints. \n\n1. https://doi.org/10.1145/3298689.3347058\n2. https://proceedings.mlsys.org/paper_files/paper/2021/hash/0184b0cd3cfb185989f858a1d9f5c1eb-Abstract.html\n\n> The paper is missing a “preliminaries” section, and it is not self-contained. It ought to contain a section describing the problem setup of MIL.\n\nWe attempted to interleave this with the introduction. The only detail we might say is missing is that most MIL algs work by learning an instance classifier $h(x)$, and using $\\hat{y} = \\max_i h(x_i)$ to make a prediction. We will add to the introduction. "}, {"review_id": "qem3kTTIaq", "reviewer": "Reviewer_kMQN", "summary": "This paper investigates whether multiple-instance learning (MIL) models actually respect the constraints of MIL problems.\n\nThis paper defines MIL problems as classification of bag-of-instances, such that the bag is only classified positive if any instance is classified positive (or a more complex rule based on positive classes of the instances, but crucially, not on negative instances, cf Eq 1 in the paper). Therefore, contrary to classification problems, there is an asymmetry between positive and negative classes in MIL problems.\n\nThe authors design tests to check whether proposed MIL models structurally enforce this constraint. More specifically, they design 1 test for the presence MIL, a more complex test for threshold-MIL, and a test to check that for the latter test, no degenerate rule is found. Each test is based on synthetic data, and are designed to fool models not enforcing the MIL constraint.\n\nExperimental results demonstrate that many deep MIL models actually do not enforce the MIL constraint as understood by the authors, except for 2 of them (Table 1).", "questions": "- The motivation of the paper remains blurry to me. Why is it so important that MIL models enforce what the authors present as the natural structure of MIL problems? The sentence \"a MIL model cannot **legally** learn to use $\\emptyset_P$\" L245 seems to indicate there are regulatory or legal issues at stake, but more details would be appreciated.\n- I fail to understand the motivation for the false-frequency reliance test: what is the problem of a true MIL model not passing this test? If there are no instance-level annotations or additional prior on the problem, I do not see why such models would not be used.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Well written paper, congrats to the authors for the clarity\n- The methodology is sound\n- The experimental results are compelling", "weaknesses": "- Limited impact: this paper shows that what the community calls \"MIL models\" is closer to \"set-of-instances classifiers\". I think it does not mean that they are irrelevant in some problems; but it is true that if there are issues at stake, one cannot trust these models for enforcing the MIL constraints. To sum up, the main impact of the paper for the community would be to clarify what \"MIL\" actually means.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We hope the below fully addresses your concerns. Please do not hesitate to let us know if any further clarification is required. \n\n> Why is it so important that MIL models enforce what the authors present as the natural structure of MIL problems?\n\nPlease see the paragraphs we added in the all-reviewer rebuttal, which we believe helps to articulate why MIL is important. As you noted in the weakness, the current \"MIL\" models that violate the assumptions may still be very valuable as set-classifiers, but it is thus important that we compare like-to-like, so that we can extract what good set-classification techniques have been inadvertently labeled \"MIL\". \n\n>a MIL model cannot legally learn to use\n\nWe now see this was not the best word choice on our part. There is no regulatory constraint at stack (as far as we are aware). The purpose was to convey that learning to use $\\emptyset_P$ is outside of the hypothesis space of MIL models, and so its use indicates a violation of the MIL hypothesis. We will re-word accordingly. \n\n>the motivation for the false-frequency reliance test (Alg. 3)\n\nLet $\\mathcal{H}_0$ denote the hypothesis class of the standard MIL model, and $\\mathcal{H}_1$ the threshold MIL. It is the case that $\\mathcal{H}_0 \\subset \\mathcal{H}_1$. Two important questions are \n\n1) Can the model I'm using represent $\\mathcal{H}_1$\n2) Can the learning procedure successfully produce solutions from all of $\\mathcal{H}_1$ when necessary? \n\nFor most of the deep models (i.e., no miNet), the answer to (1) is Yes. However, our test shows that (2) is sometimes false (and false for different algorithms compared to Alg 2. in the paper). Instead, an incomplete solution is found and is important in understanding the scope of capabilities/limitations of the algorithm under test. \n\nThe false-frequency test is also relevant to different properties of interest. For example, if many background objects might be expected in deployment (e.g., benign health cells), then even just low performance (without failing) on Alg. 3 may give caution that the approach may not work well. \n\nWe will work these points and clarification into the revision. "}, {"review_id": "KlX2GtFuC2", "reviewer": "Reviewer_BYpB", "summary": "This work proposes a set of algorithmic unit tests to verify whether multiple instance learning (MIL) models adhere to underlying MIL assumptions. The standard assumption is that a bag of instances is positive if and only if at least one of the instances in the bag is positive, otherwise it is negative (binary classification). The negative instances are considered null (background) instances, meaning the only causal link between instances and bag label is the occurrence of positive instances, and thus models should only be using the presence of positive instances for decision-making. Through the use of three algorithmic unit tests, it is demonstrated that existing MIL models do not adhere to this strict assumption, and instead utilise information from the null instances in their decision-making (i.e., to make a negative bag prediction). The tests are applied to a set of non-deep MIL models (such as SVM models) and deep MIL models.", "questions": "1. In each unit test, is the number of instances per bag consistent (maybe not fixed, but equal in expectation) for the positive and negative bags in the train and test distributions? The number of instances per bag does not need to be the same across tests, but I would expect the average bag size to be the same in the train and test distribution within an experiment to ensure this is not a factor in changing the model performance. By the MIL assumptions studied in this work, bags should be invariant to the number of instances per bag, but it is unclear whether this is accounted for in the tests. This could be the case for an additional fourth test that investigates different bag sizes (instances per bag) between the train and test distributions.\n2. Following for the above question, does the witness rate (number of positive instances in a bag) remain consistent between the train and test distributions for each of the algorithmic tests? For example, when injecting the poison instances, does the number of true negative instances change to keep the witness rate consistent? I wonder if some models are sensitive to the witness rate (i.e., they have learnt something about the expected bag size and witness rate during training), and if this affects the outcomes of the algorithmic tests. \n\nIn both questions 1 and 2 above, I'm highlighting potential additional changes between the train and test distribution that could also affect the performance of the MIL models (beyond the intended changes).", "limitations": "Limitations and areas for future work are not clearly listed.\n\nSuggested limitations:\n1. Algorithm 2 does not have negative bags that contain neither of the $c_1$ or $c_2$ concept classes (i.e., negative bags have either one instance from $c_1$ or one instance from $c_2$). This may impact what the models are learning and is not discussed.\n2. The work discusses multiple underlying concept classes, but only uses binary bag labels (positive and negative bags). Some MIL datasets have multiple positive classes, see the SIVAL and Four MNIST-Bags datasets discussed in [1]. In these datasets, null (background) instances still exist, but the different concept classes for instances relate to different positive classes. An extension to this style of problem is not discussed in this work - would the proposed algorithmic unit tests be able to scale to these datasets?\n\nI think the work is mostly robust and the findings are interesting, but additional clarity and discussion of the impacts is required to push me towards acceptance.\n\n[1] Early, Joseph, Christine Evers, and Sarvapali Ramchurn. \"Model Agnostic Interpretability for Multiple Instance Learning.\" ICLR (2022).", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**Originality**\n1. The work is unique in its exploration of whether MIL models adhere to the underlying MIL assumptions that fit the constraints of their problems.\n2. The proposed tests are a novel way of constructing train and test datasets where the assumptions hold but it is possible to detect if the model is learning rules that do not adhere to the assumption. \n\n**Quality**\n1. The deep models are well chosen. Many pieces of new research build upon these models, so the assumption is that if the original models violate the MIL assumptions, then the more advanced models will also be in violation.\n2. The results of the tests are easy to interpret - it is obvious which models are violating which tests.\n\n**Clarity**\n1. The majority of the paper is easy to read and follow.\n2. A strong combination of mathematical notation and algorithmic blocks are used to convey the tests.\n3. The results are clearly presented and well discussed.\n\n**Significance**\n1. The findings that MIL models that are widely utilised in research do not actually adhere to the implicit MIL assumptions they are meant to follow is an interesting result.", "weaknesses": "**Quality**\n1. The way concept classes are defined in the algorithmic tests is a little convoluted. For example, in the presence assumption (test 1), two positive class indicators are used: $\\mathcal{N}(0,3)$ and $\\mathcal{N}(1,1)$, but these belong to the same concept. It is not stated why two positive class indicators are required and why these belong to the same concept class. This appears to unnecessarily complicates the dataset generation process.\n\n**Clarity**\n1. $x$ is used in most cases to represent an instance, but Section 3 (lines 156 and 157) use $z$ instead of $x$. I don't see any reason why this is the case - I think it would aid understanding to use $x$ or $x_i$ instead.\n2. Line 184 - I believe \"... a testing distribution AUC of < 0.05\" should be 0.5 not 0.05. \n3. The use of $t$ in Section 3 to describe the \"number of items\" is a little misleading as $t_k$ is also used for thresholds in Sections 3.2 and 3.3. Furthermore, I assume number of items in this case is the number of instances per bag? In this case, it may be easier to utilise the notation of $n$ for number of instances per bag as defined elsewhere in the work.\n4. The number of instances per bag in the various unit tests is not clear. There are various parameters ($t$, $b$, $k$) used differently in three algorithmic tests that are sometimes undefined. It would be useful to have a summary of the distribution of bags sizes and witness rates for the train/test datasets for each algorithmic test. Please also see questions below.\n5. In Section 4, it is mentioned that there are 100,000 training samples - I assume this is the number of bags, but making this explicit may aid clarity.\n6. I think extra clarity is needed in the instance generation notation to show that the instance has $d$ dimensions, for example $x \\sim \\mathcal{I}(\\mathcal{N}(a, b), d)$. This would overcome the need to \"abuse notation\" in line 202 and make the algorithmic blocks clearer - at the moment if viewed in isolation it appears the items being added to the bags are scalar values rather than $d$-dimensional instances.\n7. It would be useful to have a summary table with simple ticks and crosses to state which models pass which algorithmic tests. At the moment it is difficult to get a high-level summary of the findings (having to scroll between three different tables).\n8. Typo on line 438 - \"onlye\".\n\n**Significance**\n1. The fact that some models do not adhere to the underlying MIL assumptions is an interesting finding. However, the actual implications of models not following these assumptions is not extensively discussed. The impact of the work would be more significant if real world examples can be given that describe why not adhering these assumptions is a problem. My main argument against this work is that even though some models do not adhere to all assumptions, they still perform well on datasets they are applied to in the literature, so why does failing the unit tests matter? What implications does this have for designing/using MIL models going forward?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We hope the below answers all of your questions and resolves any concerns in supporting our manuscript. Please do let us know if there are any unresolved concerns.  \n\nQ1: With the exception of the false-frequency test, which is explicitly testing an errant bias to the frequency of items, yes the bag sizes are approximately equivalent. Our code implementation actually supports a second version of each experiment where the number of background items is increased to make each bag have the same total number of instances, and this does not change any of our results.\n\nQ2: Again, the false-frequency test is a test changing the witness rate, but the other two tests have the same average witness rate.\n\nL1: This is an excellent point. We have conducted a new experiment that gives 1/3 chance of having only $c_1$, $c_2$, or neither. In this case, all deep learning results are the same except TranMIL which goes from 0% AUC to 89% AUC. While this does not alleviate TranMIL's failure of the test under the original settings, it matches our intuition that the modified test is \"easier\". For the algorithms to get right, and so we would recommend the current form as the default. \n\nThe SVMs take a very long time to run, but we will include their results in an appendix with this new information. \n\nL2: this is a good point that our tests do not cover all MIL scenarios, including non-binary MIL problems. We will incorporate this into revision and the similar feedback from reviewer 3dcE. \n\nQuality: The design is because we take an adversarial approach to the MIL problem: what kind of structure could we develop that has a valid MIL solution, but is more easily \"solved\" by a non-MIL hypothesis? The MIL problem places no limit on the distribution of any concept class $c_j$, and so we use a multi-modal distribution to create a scenario that has MIL-violating solutions that may appear to better match the training data, but would not generalize to a test set like a MIL-adhearing solution would. \n\nIn the case of test 1, we will add the following text to clarify: Note that the multi-modal positive class (swapping between $\\mathcal{N}(\\vec{0}, I_d \\cdot 3)$ and $\\mathcal{N}(\\vec{0}, I_d $ ) is necessary for the test to be effective in practice. Using a unimodal distribution makes the positive signal equally as strong as the `Poisoning` signal, and thus lets more (in this case, all) methods pass when they don't actually support the MIL model. In addition, we find providing a large variance to one of the Gaussian increases the difficulty of learning a wide area of recognition of the positive classes, compared to the tight variance of the `Poisoning` signal. Note that the positive class signal is not an overtly challenging learning problem, but the goal is to make the `Poisoning` signal sufficiently easier to learn that a non-MIL model would reliably prefer to learn the (invalid) hypothesis over the MIL hypothesis. \n\nClarity 1: Our intuition was that $\\boldsymbol{z}$ would be clearer, but apparently we were in error. We agree using $\\boldsymbol{x}$ is correct and happy to change it accordingly. \n\nC2: You are correct, thank you for the catch. \n\nC3: In this case, $t$ was meant to be an arbitrary value sampled from the discrete uniform distribution. We will clarify this in revision and change it to $i$ for integer. \n\nC4: See Qs\n\nC5: Training bags yes, we will fix that in revision, thank you for the catch. \n\nC6: Your point is well taken, we propose updating the manuscript to $\\mathcal{N}(\\vec{a}, I_d \\cdot b)$ to make it clear that this is a $d$ dimensional distribution with a mean vector and diagonal covariance. \n\nSignificance: Please see our all-reviewer rebuttal, which we believe addresses the concern you have raised. In many cases, MIL is a necessary defense against unknown biases that have prevented ML use in clinical settings and a defense against attacks performed against real-world anti-virus systems. The unknown violation of the MIL hypothesis creates unrecognized risk in both settings and broadly insufficient scientific understanding of our field. "}, {"review_id": "FWQm9LIyqh", "reviewer": "Reviewer_3dcE", "summary": "This paper exams whether existing deep multi-instance learning algorithms are indeed \"multi-instance learning\". Specifically, it proposes a unit test for multi-instance learning (MIL) algorithms. The goal of this test is to examine whether an MIL algorithm satisfies the multi-instance assumption. Two widely-accepted MIL assumptions are tested, the standard MIL assumption, and the threshold assumption. The results show that all attention-based MIL algorithms do not pass the test. However, CausalMIL which is proposed in last year NeurIPS, and mi-Net which is a basic deep extension from mi-SVM, are the only deep MIL algorithms that passed the test. ", "questions": "I have reviewed a previous version of this manuscript. This version has addressed most of my previous concerns by adding some important recent deep MIL algorithms. However, there are still a few point that need urgent improvemnt.\n\n**Formatting and writing**: \n\nThis area need a lot of improvement. I try my best to list some:\n\nline 15, \"MIL respecting\" to \"MIL assumption respecting\"\n\nline 19, \"points\" to \"bags\", sample in MIL are not points\n\nline 34, \"occurs with frequency\" to \"occurs frequently\"\n\nline 41-42, the sentence needs rewriting. \"that is that\"... are difficult to follow.\n\nline 45, \"as well as a strategy to avoid repeat occurrences\" it is unclear what \"repeat occurrences\" refers to\n\nI suggest include a brief test result summary in the introduction. E.g., which algorithms satisfy the standard MIL assumption and which algorithms satisfy threshold assumption. \n\nline 184, \"testing distribution AUC of <0.05\" should be \"<0.5\"\n\nline 186-188, it's better to explicitly say which AUC is for test and which AUC is for trainining.\n\nAll table should be reformated. Currently, they looks like they are prepared for a two-column submission.\nline 391-392, these texts only occupy half of the page width.\n\n**References also need work**:\n\n[4] [10] should have page number, should as Advances in Neural Information Processing Systems xx. Please check how neurips papers are properly cited.\n\n[21] \"h\" should be upper case.\n\n[32] [33], \"citation key\" should be deleted. Also, please check how to properly cite NeurIPS and ECAI published papers.\n\n............. and many more.\n\n*I would like to see the authors to provide an updated manuscript with these issues (not limited to those listed above, there most likely will be more) addressed during rebuttal*. \n\n**Discussion**: \n\nAs the Test 1 in Section 4.1 has more implication on the current interest of MIL applications, e.g., histopathology image classification. More space should be allocated for discussion these test results. One way of improving the organization is to divide the test results into classical MIL and deep MIL algorithms. For classical methods, the results are easily expected so you only need to report them. For deep MIL methods, MI-Net/MIL-pooling/Tran-MIL/GCN-MIL/Hopfield failing Test 1 has important implication in applications and should be heavily discussed. \n\nAs this work empirically shows that attention-based deep MIL algorithms do not meet any of the tested MIL assupmtions, it should provide more discussion on the implication of these results, ideally in a separate discussion/practical implication section. For applications that are suitable for the standard MIL assumption, e.g., histopathology image classification and other medical applications, it is important to develop algorithms that can pass Test 1. In other words, CausalMIL and mi-Net should be expored more in this direction, while attention-based methods should be avoided. For applications that are suitable for threshold MIL assumption, i.e., nature scene classification and others, it is important to develop algorithms that pass Test 2 and Test 3. These discussions can further improve the impact of this work, and possibly improve the correctness and explainability of future MIL algorithms.", "limitations": "The authors can further improve this work by adding limitations on there exists other MIL assupmtions that this work does not test. See the assumptions mentioned in:\nFoulds and Frank, A review of multi-instance learning assupmtions. 2010.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The motivation of this work is great. As the test results have shown, all deep MIL algorithms based on attention do not respect the standard MIL assumption. Although the results are not theoreticall surprising as attention performs a weighted average, it is nice to have a paper that formally identify the problem with good experiment support.\n\n2. The proposed unit test is model-agnostic. Therefore, any existing or future MIL algorithms can be tested. \n\n3. The MIL algorithms tested in this work is representative of the current state-of-the-art in classic and deep MIL algorithms.", "weaknesses": "1. The writing, formatting, presentation of this work need significant improvement. See my detailed comments for more.\n\n2. The discussion on the implication of the test results should be expanded. There should be more discussion on how the algorithms that passed the test can be better explored in applications such as histopathology image classification, and the algorithms that failed the test should be treated cautiously in downstream applications. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We hope the below fully satisfies your concerns. Please let us know if there are any outstanding issues that we did not fully satisfy. \n\nW2/Discussion 1: Please see our all-reviewer rebuttal, where we have added a new paragraph that we believe helps to satisfy this concern. If it does not we are happy to expand. \n\n\n> include a brief test result summary\n\nWe will include the below table with an explanation in revision (italics for claims are implied by the writing but not formally stated, italics for Threshold _Pass_ are because they fail the standard test, which means they can't fully satisfy the Threshold MIL). \n\n|                 |  mi-Net  |  MI-Net  | MIL-Pooling |   Tran-MIL  |   GCN-MIL   | CausalMIL |  Hopfield |  mi-SVM  |  MI-SVM  |  SIL |  NSK |  STK |   MICA   |  MissSVM |\n|-----------------|:--------:|:--------:|:-----------:|:-----------:|:-----------:|:---------:|:---------:|:--------:|:--------:|:----:|:----:|:----:|:--------:|:--------:|\n|          Claim: | Standard | Standard |   Standard  | _Threshold_ | _Threshold_ |  Standard | Threshold | Standard | Standard | None | None | None | Standard | Standard |\n|   Standard Test |   Pass   |     F    |      F      |      F      |      F      |    Pass   |     F     |   Pass   |   Pass   | Pass |   F  |   F  |   Pass   |   Pass   |\n| Threshold Tests |     F    |  _Pass_  |      F      |      F      |      F      |    Pass   |   _Pass_  |     F    |   Pass   |   F  |   F  |   F  |     F    |     F    |\n\nWe have re-formatted tables to be wider, please see the below example (Table 1):\n\n|            | mi-Net | MI-Net | MIL-Pooling | Tran-MIL | GNN-MIL | CausalMIL | Hopfield | mi-SVM | MI-SVM | SIL   | NSK   | STK   | MICA  | MissSVM |\n|------------|--------|-----------------|----------------------|-------------------|------------------|-----------|-------------------|--------|--------|-------|----------------|----------------|-------|---------|\n| Train Acc. | 0.991  | 1.000  | 1.000       | 1.000    | 1.000   | 0.999     | 0.624    | 0.999  | 1.000  | 0.992 | 1.000 | 1.000 | 0.500 | 0.995   |\n|  Train AUC | 0.998  | 1.000  | 1.000       | 1.000    | 1.000   | 0.999     | 0.495    | 1.000  | 1.000  | 1.000 | 1.000 | 1.000 | 1.000 | 1.000   |\n|  Test Acc. | 0.993  | 0.000  | 0.000       | 0.000    | 0.000   | 0.996     | 0.500    | 0.935  | 0.986  | 0.766 | 0.000 | 0.466 | 0.500 | 0.449   |\n|  Test AUC  | 1.000  | 0.000  | 0.000       | 0.000    | 0.000   | 1.000     | 0.488    | 1.000  | 1.000  | 0.998 | 0.000 | 0.000 | 1.000 | 0.551   |\n\nWe have noted and fixed all other formatting notes you have mentioned. Our citation style was generated using paper organization software.  We are creating a new `.bib` file and manually re-entering all cited works based on the host's platform (e.g., ACM) suggested bibtex. \n\n>I would like to see the authors to provide an updated manuscript\n\nThe NeurIPS open review does not allow us to do this. We hope the reviewer recognizes that we have earnestly incorporated every item of feedback and followed through on all our prior commitments in this article's previous review, and will do so again. We believe the paper has been significantly improved, and are glad the reviewer recognized the improvements-  and that two of the new reviewers find the paper highly readable thanks to your prior feedback. \n\n\n> Limitations \n\nWe will add the following text to the revised manuscript. \n\nNote that our current work addresses only two of the most common forms of MIL, and does not guarantee a passing algorithm is valid. This is critical when the MIL algorithm under test is in a larger hypothesis class than that considered in this work. As noted in the seminal work of [15 from paper], the MIL model includes radial extensions to the concept class [1], unsupervised MIL clustering [2], and multi-class MIL [3], among others. In all of these cases, our tests may be insufficient to detect issues that are more focused. Future work may develop more general program synthesis to generate tests given MIL constraints or attempt to develop techniques for gradient-based search of a \"failure certificate\" given a differentiable model and constraint specification. Such future work could eliminate the manual work necessary to devise new tests of our current approach. In particular, the parameters of our test distributions are developed by manual checking, which may not be tenable in more complex hypothesis spaces. \n\n(Note, current citation formation in rebuttal is copied from the original website default style as we focus on rebuttal and preparing all updates to the manuscript)\n1. ON GENERALIZED MULTIPLE-INSTANCE LEARNING, STEPHEN SCOTT, JUN ZHANG, and JOSHUA BROWN, International Journal of Computational Intelligence and Applications 2005 05:01, 21-35\n2. Zhang, ML., Zhou, ZH. Multi-instance clustering with applications to multi-instance prediction. Appl Intell 31, 47–68 (2009). https://doi.org/10.1007/s10489-007-0111-x\n3. MULTIPLE CLASS MULTIPLE-INSTANCE LEARNING AND ITS APPLICATION TO IMAGE CATEGORIZATION, XINYU XU and BAOXIN LI, International Journal of Image and Graphics 2007 07:03, 427-444"}]

Author rebuttal:
We are pleased most reviewers found our paper readable, sound, and technically novel in identifying a previously undocumented issue in the Multiple Instance Learning literature. One shared note of reviewers was that we could more strongly communicate the importance of this to readers outside the standard MIL audience. We will add the below text to the manuscript and hope it satisfies your concerns. 


Algorithms that fail, or intentionally forgo, the MIL constraints may appear to obtain better accuracy "in situ" (i.e., the lab environment). But if it is known that the MIL assumption is true, ignoring it creates a significant risk of failure to generalize "in vivo" (i.e., in real production environments). In the clinical context, this is important as many ML algorithms are often proposed with superior in situ performance relative to physicians [1], but fail to maintain that performance when applied to new clinical populations [2,3,4]. In this case, respecting underlying MIL properties eliminates one major axis of bias between situ and vivo settings and higher confidence in potential utility. In the cyber security space, respecting the MIL nature eliminates a class of "good word" style attacks [5,6,7] where inconsequential content is added to evade detection, an attack that has worked on production anti-virus software [8]. These reasons are precisely why MIL has become increasingly popular, and the importance of ensuring the constraints are satisfied.  For these reasons, we would suggest practitioners/researchers begin with CausalMIL and mi-Net as a solid foundation to ensure they are actually satisfying the MIL hypothesis, and thus avoiding excess risk in deployment. 

Notably, this creates a dearth of options when more complex MIL hypotheses are required, as CausalMIL and mi-Net succeed by restricting themselves to the Standard MIL assumption. The creation of MIL models that satisfy this, and other more complex hypothesis, are thus an open line of research that would have potentially significant clinical relevance. Similarly, users with more niche MIL needs may desire to more thoroughly test their models respect the constraints critical to their deployment. Our work has demonstrated that many articles have not properly vetted the more basic MIL setting, and so we suspect other more complex MIL problems are equally at risk. 

1. Poore GD, Kopylova E, Zhu Q, Carpenter C, Fraraccio S, Wandro S, Kosciolek T, Janssen S, Metcalf J, Song SJ, Kanbar J, Miller-Montgomery S, Heaton R, Mckay R, Patel SP, Swafford AD, Knight R. Microbiome analyses of blood and tissues suggest cancer diagnostic approach. Nature. 2020 Mar;579(7800):567-574. doi: 10.1038/s41586-020-2095-1. Epub 2020 Mar 11. PMID: 32214244; PMCID: PMC7500457.
2. Abraham Gihawi, Yuchen Ge, Jennifer Lu, Daniela Puiu, Amanda Xu, Colin S. Cooper, Daniel S. Brewer, Mihaela Pertea, Steven L. Salzberg bioRxiv 2023.07.28.550993; doi: https://doi.org/10.1101/2023.07.28.550993
3. Varoquaux, G., Cheplygina, V. Machine learning for medical imaging: methodological failures and recommendations for the future. npj Digit. Med. 5, 48 (2022). https://doi.org/10.1038/s41746-022-00592-y
4. Wynants L, Van Calster B, Collins G S, Riley R D, Heinze G, Schuit E et al. Prediction models for diagnosis and prognosis of covid-19: systematic review and critical appraisal BMJ 2020; 369 :m1328 doi:10.1136/bmj.m1328

Meta-review: Reviewers were unanimously supportive of this paper, which provides an interesting analysis of subtle failure cases of multiple instance learning algorithms. The author response significantly improved many reviewers' scores; the authors are encouraged to update the final version based on the this discussion, which will likely benefit future readers.
Decision: Accept (poster)