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.
Paper
Similar papers
Peer review
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.
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. 2. The proposed unit test is model-agnostic. Therefore, any existing or future MIL algorithms can be tested. 3. 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. 2. 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.
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. **Formatting and writing**: This area need a lot of improvement. I try my best to list some: line 15, "MIL respecting" to "MIL assumption respecting" line 19, "points" to "bags", sample in MIL are not points line 34, "occurs with frequency" to "occurs frequently" line 41-42, the sentence needs rewriting. "that is that"... are difficult to follow. line 45, "as well as a strategy to avoid repeat occurrences" it is unclear what "repeat occurrences" refers to I 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. line 184, "testing distribution AUC of <0.05" should be "<0.5" line 186-188, it's better to explicitly say which AUC is for test and which AUC is for trainining. All table should be reformated. Currently, they looks like they are prepared for a two-column submission. line 391-392, these texts only occupy half of the page width. **References also need work**: [4] [10] should have page number, should as Advances in Neural Information Processing Systems xx. Please check how neurips papers are properly cited. [21] "h" should be upper case. [32] [33], "citation key" should be deleted. Also, please check how to properly cite NeurIPS and ECAI published papers. ............. and many more. *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*. **Discussion**: As 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. As 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.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
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: Foulds and Frank, A review of multi-instance learning assupmtions. 2010.
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.
Strengths
**Originality** 1. The work is unique in its exploration of whether MIL models adhere to the underlying MIL assumptions that fit the constraints of their problems. 2. 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. **Quality** 1. 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. 2. The results of the tests are easy to interpret - it is obvious which models are violating which tests. **Clarity** 1. The majority of the paper is easy to read and follow. 2. A strong combination of mathematical notation and algorithmic blocks are used to convey the tests. 3. The results are clearly presented and well discussed. **Significance** 1. 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** 1. 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. **Clarity** 1. $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. 2. Line 184 - I believe "... a testing distribution AUC of < 0.05" should be 0.5 not 0.05. 3. 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. 4. 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. 5. 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. 6. 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. 7. 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). 8. Typo on line 438 - "onlye". **Significance** 1. 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?
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. 2. 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. In 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).
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
Limitations and areas for future work are not clearly listed. Suggested limitations: 1. 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. 2. 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? I 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. [1] Early, Joseph, Christine Evers, and Sarvapali Ramchurn. "Model Agnostic Interpretability for Multiple Instance Learning." ICLR (2022).
Summary
This paper investigates whether multiple-instance learning (MIL) models actually respect the constraints of MIL problems. This 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. The 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. Experimental 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).
Strengths
- Well written paper, congrats to the authors for the clarity - The methodology is sound - 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.
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. - 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.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
Yes
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: 1. Designing a unified framework for checking MIL assumptions by creating synthetic datasets that check for one or more of the implicit MIL assumptions 2. Running experiments to show how often algorithms fail these tests despite being the most recent ones. 3. Arguing that not passing these tests means a model is not performing MIL correctly, however, passing these tests does not imply certification.
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: 1. 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. 2. 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. 3. 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. Also 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.
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\}$. 2. 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. 3. Line 209, How does $N(0, 3)$ denote a normal distribution in d-dimensional space? What does 0 and 3 refer to here? 4. Line 304, “learn a noisy but erroneous …”, not sure what is the difference between a noisy and erroneous function, I assumed noise → erroneous? 5. 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?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
N/A
I thank the authors for writing compact answers to my questions and thoughts. The authors answers improved my understanding of the paper, where I misunderstood a few aspects before that are now clarified. I have increased the score from 3 to 6 accordingly.
I would suggest improving the paper's writing. There are few grammatical mistakes which makes the paper less readable. 1. Line 370-371: The goal is that models are tested to the properties the properties to have. In addition to many more typo/writing issues reviewer 3dcE has mentioned. Furthermore, a discussion of real-world MIL-benchmarks/settings [1, 2], their construction and if their construction respect/do not respect the MIL assumptions here would strengthen the paper and showcase its novelty. [1] mil-benchmarks: Standardized Evaluation of Deep Multiple-Instance Learning Techniques, https://arxiv.org/abs/2105.01443 [2] Multiple Instance Learning: A Survey of Problem Characteristics and Applications, https://arxiv.org/abs/1612.03365
We appreciate the raised score in light of the clarification. Thank you! We have fixed all mentioned typos and will carefully review to correct any remaining typos. 2105.01443 : This appears to be 2 versions of the Standard MIL formulation, 1 version of the Threshold MIL, 1 appears to be a version of the extended GMIL per Foulds & Frank, and one that might be a Counting-GMIL per Foulds & Frank. 1612.03365: This has three synthetic/semi-synthetic tasks (amongst other real datasets). Newsgroups, Letters, and Gaussian, are all standard MIL. We will add these related works and a discussion about prior synthetic MIL datasets to the camera ready. We will emphasize that we are not the first to create synthetic data with the goal of testing specific properties and their identifiability by a MIL model. However, to the best of our knowledge, ours is the first work to create adversarial test sets with a MIL solution, and a non-MIL solution, as a way to test that a model restricts itself to a valid hypothesis. 1612.03365 is also an excellent catalog of many real-world datasets for MIL, as you note, that highlights the importance of understanding (1) which version of the MIL hypothesis we wish to leverage, and (2) why it is important to respect the (desired) MIL hypothesis. This will also be worked into the discussion. We hope this further clarifies any concerns, and we are again appreciative of your time. Please let us know if any further thoughts remain, and we hope you have a great weekend!
Thanks the authors for the replies. These addressed most of my previously concerns. I raised my score from 6 to 7 in favour of the paper. However, I still suggest the authors to carefully proofread and improve the manuscript.
We appreciate the score raise and the helpful feedback for the paper. We will be reviewing the manuscript carefully for typos as we work on the revisions discussed with you and the other reviewers. Thank you!
Thank you for the rebuttal comments. The direct responses to my questions and the general rebuttal have helped provide clarity around the work, especially on the implications for not adhering to the MIL assumptions. I appreciate the additional experiment for L1. I would still like to push for a summary table in the main body showing with simple ticks and crosses to highlight which models pass which tests, potentially placed early on the first or second page. I think this would help showcase the main takeaway that CausalMIL and mi-Net should be the best starting points for new models. I will increase my score in light of the strong rebuttal.
We are very appreciative of the score raise and glad we could address your concerns! Please do not hesitate to let us know of any other items that arise. We will absolutely include a summary table in the main body to pass which tests, and it has already been written. Thank you again for your time.
Thanks
Thanks for your answers, which have clarified the motivation for the paper as well as the questions I had. I will update my score to 7.
We are very glad we could resolve your questions and appreciate the raised score, thank you! Please let us know if any other questions arise.
Decision
Accept (poster)