Are Multiple Instance Learning Algorithms Learnable for Instances?
Authors: Jaeseok Jang
HYUK-YOON KWON
Venue: NeurIPS 2024 poster (2024)
Keywords: Multiple instance learning
Learnability
Learning theory
Probably Approximately Correct
Primary area: learning_theory

Abstract: Multiple Instance Learning (MIL) has been increasingly adopted to mitigate the high costs and complexity associated with labeling individual instances, learning instead from bags of instances labeled at the bag level and enabling instance-level labeling. While existing research has primarily focused on the learnability of MIL at the bag level, there is an absence of theoretical exploration to check if a given MIL algorithm is learnable at the instance level. This paper proposes a theoretical framework based on probably approximately correct (PAC) learning theory to assess the instance-level learnability of deep multiple instance learning (Deep MIL) algorithms. Our analysis exposes significant gaps between current Deep MIL algorithms, highlighting the theoretical conditions that must be satisfied by MIL algorithms to ensure instance-level learnability. With these conditions, we interpret the learnability of the representative Deep MIL algorithms and validate them through empirical studies.

Are Multiple Instance Learning Algorithms Learnable for Instances?
Jaeseok Jang and Hyuk- Yoon Kwon
Graduate School of Data Science, Seoul National University of Science and Technology [jangjs1027, hyukyoon. (roon]sseoulteee ac.kr
Abstract
Multiple Instance Learning (MIL) has been increasingly adopted to mitigate the high costs and complexity associated with labeling individual instances, learning instead from bags of instances labeled at the bag level and enabling instance-level labeling. While existing research has primarily focused on the learnability of MIL at the bag level, there is absence of theoretical exploration to check if given MIL. algorithm is learnable at the instance level. This paper proposes a theoretical framework based probably approximately correct (PAC) learning theory assess the instance-level learnability of deep multiple instance learning (Deep MIL) algorithms. Our analysis exposes significant gaps between current Deep MIL algorithms, highlighting the theoretical conditions that must be satisfied by MIL algorithms ensure instance-level learnability. With these conditions, we interpret the learnability of the representative Deep MIL algorithms and validate them through empirical studies.
1 Introduction
The performance of supervised learning models is greatly influenced by the amount of labeled data [ While various models utilizing large-scale datasets have achieved excellent performance, the cost and time of labeling have emerged as issues, especially in domains requiring expert knowledge. For example, in the case of pathology images, detailed labeling requires significant amount of expert time (2].
To address these issues, multiple instance learning (MIL) techniques have been introduced. MIL encompasses all methodologies that learn to predict the labels of instances by learning from the labels of bags composed of instances 3 4 5
7 8 9 [TO] This approach allows for detecting disease areas in pathology images through whole-image labeling without requiring the labeling of regions within the image. This can significantly reduce overall labeling costs and maximize the efficiency of the method (2] 19. As illustrated in Figure [ if at least one instance in a bag is positive, the bag is positive, and if all instances learning, was necessary first to confirm that learning at the bag level could be performed a high level. Therefore, traditional MIL research focused primarily on the feasibility of learning at the bag 14], and some studies validated instance-level learning level rather than the instance level [1] 12 13
2 6,
negative, the bag is negative in MIL. To achieve instance-
only for specific algorithms 15]
Figure 1:
The data structure consisting of multi-instances (Blue: Negative, Red: Positive)
16
Recently, with the advancement of deep learning technologies, traditional MIL has evolved into Deep MII., enabling more effective extraction features from individual instances and consideration of interactions between instances, leading to significant improvements in prediction performance. Despite these advancements, MIL research still predominantly focuses on learning at the bag level, with lack of exploration into the feasibility of instance-level learning [10 [8]
CCoreesponiigg author
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

In this study, we propose new framework to theoretically validate that Deep MIL can learn at the instance level, overcoming the aforementioned issues. The contributions of this study are summarized as follows:
1. The proposed theoretical framework derives conclusions about the instance-level learnability of Deep MII, algorithms, assuming that MII. algorithms are learnable at the bag level (Assumption D.
2. Utilizing the probably approximately correct (PAC) learning theory, divide the hypothesis space of the dataset into two cases: 1) each instance being statistically independent and 2) the general case without any constraints on instance distributions, including statistically dependent instances. We theoretically derive the necessary and sufficient conditions for learnability in each hypothesis space (i.e.. Condition f and Condition
7
3. By applying the derived conditions to the existing representative types of Deep MIL, verify their instance-level learnability.
4. Through Theorem 10 and Theorem [T] we show that additional information (e.g., positional information of each time point in time series, medical records provided alongside pathology images for better disease diagnosis) beyond the features directly extracted from the original data must act as weights in the independent hypothesis space of each instance.
This paper is organized as follows. Section deffnne the problem. Section outlines the conditions for Deep MIL to be instance learnable and provides theoretical proof. Section evvlluate existing Deep MIL algorithms and validates the results through experiments. Finally, Section concludes the paper.
2 Problem Definition
Notation 1 (MIL domain spaces) Given the feature space for an instance Xinsts C Rdd and the feature space for N instances X == (Ninst, , Xinstyy...
Ninstu 1. along with the label space y := (1.... k), we can define the joint distribution DXy on X' x y. Here, Xinst, E Xinst. X := (Xinste> Xinstey.... X instt). E X, and Y E y are random variables. The MIL instance domain Dx Dxmay Y represents the joint distribution of individual instances and their respective labels. The MII bag domain Dxy is the joint probability distribution composed of multiple instance domains D Dxmmy y. Here, the term "domain" refers to these joint distributions.
Based on Notation 1 the MIL Problem can be defined as in Definition
I
Definition (MIL problem) Given a training dataset S ==
x.), y, ((IT) ...,, ...., In)
: } drawn IID from the joint distribution Dxy. the goal of MIL is to learn classifier foog for the data and drawn from the marginal distribution Dx: 1) It should be able classify the class corresponding to the bag x. 2) It should be able to classify the class corresponding to the ith instance x; of the bag. Here, a random sample (I., y) == ((Z,,..., v) of the training data represents a bag consisting of instances drawn from Dxy, with total of bags. The training data for the ith instance is given by Smatt. := {(x) y²), (x." )²
Fimst..) such that for any arbitrary bag random variable x == (Z1, .... I.))
The MIL problem defined in Definition T is performed within the following MIL hypothesis spaces.
Notation 2 (MIL hypothesis spaces) 1) The bag hypothesis space Hoag (bbag X - Y is set of hypothesis functions hbag that classify bags with the correct labels. Here, hbag = f(X), where f E Freg. 2) The th instance hypothesis space Hinst, C. (hinst, : Xinst, > Y} is a set of hypothesis functions hinet, that classify the ith instance with the correct labels using the feature space of the tth instance. Here, hinst, = (X where f E Finst, Here, Fbag and F are sets of functions that take a bag or the 7th instance as input and generate the corresponding labels.
According to Notations 2 and Definition the risk for bag in MIL is defined in Definitions a
Definition 2 (Bag Risk) If the loss for a bug in the MIL. algorithm is given by (hbag (x), v), the for bag is defined as follows:
2

---

Rbag B(oaa))DDx bbag (bbag (x), v.)
(I)
Definition 3 (Instance Risk) If the loss for the 8th instance in the MIL algorithm is given by (2:),, v). the risk for the ith instance is defined as follows:
Pinst, (hinst, (x4),
Rinat: ((ers)))Dxxmm Xxmet inntt (nittt, (2z):
Based on the definitions of bag risk and instance risk in Definition 2 and the learnability for bags and instances can be defined as Definition and Definition 5
Definition 4 (PAC Learnability of Bag) Given the domain space Dxy and the bag hypothesis space
Hoag (hagg X + } the MIL algorithm A is said to be learnable on Houg with respect Dxy if. for all domains Dxv & Dxx, the following condition is satisfied:
PS-DD [[Bbn((((S)
inf Reng (h) 5
-
be hEHasg
Here, represents the acceptable enoor between the learning algorithm and the actual optimal hypothesis. contrast, represents the confidence level that the learning algorithm will return accurate results within cerlain error runge. Both and ó have a range of 0 < e, <.
Definition 5 (PAC Learnability of Instance) When given the 7th instance domain space D Xinan Y
and instance hypothesis space Himar, {hinst, X Y. the algorithm A is said to be learnable over Hinst, from D Dxmo,? if it satisfies the following for all domains DXinn,, Y E D Xmmut
Piimaty Dm
Rinse, y B (Aaeet(A(Ssse (A(Sinst))
inf hEHimet
Ranst, (h) 21-8
Based the relationship between Definitions F according to Theorem a MIl. algorithm is learnable with respect to bags, it is not learnable with respect to instances.
Theorem If MIL algorithm A satisfies Condition | then this algorithm is not PAC learnable for any instance domain space D Xmn, Y and instance hypothesis space Hinsts C {lisnst X Y).
Y U
Rinst, (A(Sinst.))
inf hEHsnst,
Rinet, (h)) > e
> 8
(5)
Condition 1 The MIL algorithm A is not PAC learnable for the given domain space D Dxy and bag hypothesis space Hoag C. {hbag X Y}:
Rbeg (Rbeg(((S)) (A(S))
inf heHaus
Roag (h)l > é
(6)
Proof: The proof of Theorem is conducted in Appendix
C.1
According to Theorem D MIL algorithms that not learnable for bags do not guarantee learnability for instances. Therefore, in this study, we discuss the Icarnability of instances under Assumption
Assumption The MIL algorithm is PAC learnable for bags.
Based on the definitions, theorem, and assumption above, formulate the definition of when the proposed Deep MIL is learnable for instances as follows:
Definition 6 If the MIL algorithm satisfies Condition 2 it is learnable for instances.

---

Condition 2 The Deep MIL algorithm A must exhibit equivalent PAC learnability for bags and instances:
P
Roag (A(5)) -
inf Riag (h)) S CA 0 Rinsti Connsti(Ae (A(SentA))))t
inf REHouut
Rinst, (h)) S 2 1-8
NEHa
Definition 6 under Assumption Jensures that if Condition is satisfied, the algorithm is guaranteed to be learnable for instances. On the other hand, MIL algorithms that do not satisfy Condition 2 cannot guarantee learnability for instances, even if they successfully learn for bags. Therefore, Condition becomes a necessary and sufficient condition for MIL algorithms to be learnable for instances.
3 Proposed Theoretical Framework
In this study, we propose a theoretical framework to verify whether given MII. algorithm satisfies Condition according to Definition 6 For some Deep MIL algorithms 6 instances are assumed to belong to independent bag domain spaces. Therefore, we address the problem by distinguishing between the independent bag domain space Din and the general bag domain space Deen 1) D Ind refers to bag domain spaces where all instances within bag are statistically independent. 2) X refers bag domain space that includes both D Dep where interactions or dependencies exist among instances within a bag, and Dind That is, Dind UDD = DXY
XY
3.1 Overview
Figure 2 shows the final summary of the definitions, relationships, and results of the theorems that comprise the theoretical framework proposed in this study.
Learnability Theorems Instances
Theorem Relationship berween leamability Bags learnaiilityy Instances
Consequence:: If MIL algorithm not PAC learnable for bags, it cannot be PAC learnable for instances.
Assumption I: The MIL algarithm is PAC learnable for bags
Thcorom Leamubility for Bage Can
Theerem PAC Leamahility for Bags in D
Consequence: For MIL algoritims to be PVC leamable in DE7 the use sttention mechanism is necoussry.
Coneapanion All MII poiling schnigrecne PAC tmmobie on fip Rlg (lintance, Entbedding, Alicatien, Addiiis, Conjunetive-Poodin Pliee-Pooiigg Iecmmpl:: drngg actidity prodiction, arolyn votcee independent chamical strutures dug grodit wheche casddlae agazol
(Atteation. Additive, Conjunctive Paeling)
Example: la revlow seatcace aselysis, MIL cossides relationskis beteoeesssbeeeeeee betweco acteeeco wittn resion prodicl everal enimens noview.
General Bag Domain Spaces D
D
Dep
Independent Bag Domnin Spaces D
Theorem Learnabliity for Dêm
Theorem 2: Instance Leamability for duy
Theerem Learubility of Conjunctive- Paoolii- Instances
Hyyethera Bodeets Information (Atteanion, Addltive Pooling)
Theorem 6: Lesmahilit
Theorem Non--_carssiility Embedding- Puoling Instances
Tastanco- Panling Instances
Theorem 10:
Theorem 1I: Non: Leamabtiity of Positional Encodling
Nom-Lccmabiliyy RNN-Based
Learnability Theorems for Instances
Figure 2: Relationships between theorems: Blue arrows indicate that the pooling methods are learnable when our proposed conditions are satisfied; Red arrows indicate that they are not learnable when the conditions not satisfied.
3.2 PAC Learnabiliyy for Independent Bag Domain Spaces
The definition of Dind is provided in Definition
Definition The independent Bag Domain Space Dind is defined as domain Space that encom- passes all instance spaces while satisfying Condition

---

Condition 3 For each Instance Space D D within D D'y. there must exist corresponding bag domain space Dxy D which should be determined as the union of each instance domain space, as follows:
N Dind = UDimay E Dind
(8)
Since D'y satisfies Condition implying independence among instances, the hypothesis space for each instance is unaffected by other instances. In this case, for MIL algorithms to learnable for instances, they must satisfy Condition according to Theorem
Theorem If MIL algorithm satisfies Condition in Dird it learnable for instances.
Condition 4 The risk of the optimal hypothesis for & must ensure that it equals the of the risks of the optimal hypotheses for individual instance spaces within D XY
inf Rody bER
inf Rinsts
(9)
1=1
Consequence: If Condition is satisfied, then Condition 2 is also satisfied. Hence, Condition becomes a necessary and sufficient condition for learnability for instances in DXY.
Proof: The proof Theorem) is provided in Appendix
3.3 PAC Learnability for General Bag Domain Spaces The definition of Den is provided in Definition
Definition
The general bag domain space D DGen defined as a domain space that encompasses all instance spaces while satisfying Condition aand
Condition For every instance space Dximasy y within DXV, there exists corresponding bag domain space Dxy E Derr. determined as the sum of each instance domain space.
Condition 6 Doen is formed using weights a E (0,1) to reflect the importance of relationships among instances. Each instance domain space Dxmn,, Y should be defined along with weight as as follows:
DXY Σ
aj ag Xxixx, Y E Den such that
Σa a =
0 05a 1
(10)
Since Den satisfies Condition 5 and Condition 6 implying the existence of relationships among instances, the hypothesis space for each instance influenced by other instances. In this case, for MIL algorithms to be learnable for instances, they must satisfy Condition according to Theorem B
Theorem If a MIL algorithm satisfies Condition 7 in Dee, is learnable for instances.
Condition The risk of the optimal hypothesis for DQen must ensure that equals the weighted sum of the risks of the optimal hypotheses, for individual instance spaces within DGen
N
N 05 o;
inf R
Σ
Os inf Rinst; such that
Σ 1=1
51
(1))
NEW
1=1
Consequence: I MIL algorithm satisfies Condition 7 it also satisfies Condition 2 Hence, Condi- tion 7 becomes necessary and sufficient condition for MIL algorithms to be learnable for instances
in D Gen
Proof: The proof of Theorem is provided in Appendix C.3
5

---

Theoretical Verification of Existing Deep MILS
4.1 Classifications of Existing Deep MIL Methodologies
The Deep MIL algorithms proposed far are primarily categorized based on 1) whether they perform
Aggregation at the Embedding-level [5] 6, 19 (0) or at the Instance-level 21 23
9 8 10] (24).
Additionally, they can be further classified into 5 types of pooling techniques according to 2) whether
they do not use an attention mechanism 5 [2 6.. perform Aggregation by multiplying attention
weights the embedding- 2 at the instance-level
19 20 perform aggregation by multiplying attention weights
23
10
as shown Table [
Table 1: Classification of existing Deep MIL methodologies.
Instance
Embedding -pooling [
Attention
Additive
Conjunctive
ppooling 21
-pooling [2119
ppooling
-pooling
P3 10] 24
Aggregation-lovel Attention-target
Instance
Embedding
Embedding
Instance Embedding
Instance
None
None
Embedding
Instance
A detailed explanation of the pooling techniques is provided in Appendix A.2
4.2
Theoretical Verification
4.2.1
Relationship between Attention Mechanism and Learnability for Bag
The application of an attention mechanism to MIL algorithms depends on the range of the domain space that the MIL algorithm can learn from. This implies that the feasibility of PAC learning for bags may vary depending on whether attention applied or not.
Theorem D the MII. algorithm is PAC learnable for bags.
Proof: The proof of Theorem ii conducted in Appendix C.4
Theorem In D MIL algorithms that aggregate independent hypothesis spaces for each instance must utilize attention satisfying Condition too be PAC learnable for bags.
Condition 8 The hypothesis space Hbagere of Attention MIL should be equal to the sum of indepen- dent hypothesis spaces hinst, multiplied by attention weights Att,:
Att, hinstty where 0 < Att, < 1, Σ Att: = 1
Hbagast
hbagars
(12)
Proof: The proof of Theorem is conducted in Appendix C.5
Validation: Experimental validation is performed in Section 4.4.1
Consequence: Theorems 4 and are direct theorems about the learnability MiL.for instances. However, the learnability for bags is a prerequisite for MIL algorithms to be able to learn from instances. According to Theorem 4 in PAC learnable DAnd, all MIL algorithms satisfy Assumption regardless of the presence of attention mechanisms. On the other hand, DXY, according to Theorem 5 the application of attention mechanisms satisfying Condition becomes a necessary condition for MIL. algorithms be learnable for instances.
4.2.2 Verification Learnability for Instances by MIL Pooling Method
The type of pooling technique used in Deep MIL algorithms becomes a determining factor in whether they are learnable for instances when they are learnable for bags. In this case, to verify whether Deep MIL. algorithm learnable for instances, a definition of Lemma] [ should be established advance, extending Condition to ensure that additional hypothesis space is included for instances.
Lemma Condition serves as a necessary condition for the learnability of instances, when the hypothesis space for the tth instance of a MIL algorithm Himst, U Haddd Here, Hinst; represents the hypothesis space for the tth instance, and Hadd, denotes the hypothesis space for the ith instance generated through elements outside the ith instance.

---

Condition 9 Hadd, must be a subset of Hinst."
Hanet, D Hadd, {hadd, Radd, + }}
(13)
Proof:
The proof of Lemma is conducted in Appendix C.6
In the case of instance-port mistance-pooling, as attention mechanisms are not utilized, Condition not satisfied. Therefore, in DXy, the algorithm is not learnable for bags, and consequently, not learnable for instances either. However, according to Theorem 6 the algorithm is learnable for instances in Day.
Theorem 6 In D MIL algorithms that perform dastance-poolingg are PAC learnable for instances.
Proof: The proof of Theorem is conducted in Appendix C.7
Unlike Instance-Pooling where the hypothesis for bags is combined from instance-level hypotheses, Seteeddinn-Pooliing does combine bag hypotheses from instance-level hypotheses. As result, does not satisfy Condition 9 leading to scenario similar to Theorem 7
Theorem MIL algorithms that perform -oooldding-Pooling not learnable for instances.
Proof: The proof of Theorem is conducted in Appendix C.8
Consequence: In Dayy, Deep MII. algorithms exhibil reproducibilityy when they avoid overfitting to easy information the bag-level and effectively learn positive instances the instance-level. Reproducibility in this context refers to the learnability of positive instances. They demonstrated experimentally that Deep MIL algorithms using Instance-Poolicn such as mi-Net [3] and Causal MIL (21 122,, exhibit reproducibility, while those using Embedding Pooling, such as Mi-Net (5), do not. However, Raff et al. [18] failed to provide a theoretical explanation for these results. In contrast, this study theoretically demonstrated that Instance-Poote Pooling is learnable for instances while Embedding-Poode
not, through Theorems 6 and 7 This provides theoretical support for the experimental findings of Raff et al. (18).
To compute the attention applied each instance's features in Attention Pooling and Additive Pooling, the bag's s features X are used as input. Multiplying attention weights to the features at the feature level results additional hypothesis space hadd, formed by the attention operations on each instance. As consequence, since Condition 9 is not satisfied, according to Theorem g the algorithm becomes not PAC Learnable for instances.
Theorem 8 If the MII. algorithm does not adhere to Condition 10 it is not learnable for instances.
Condition 10 The risk Ranst, for the tt instance should be as follows:
Rynst: Re .) Dxsmee, Linne, (h,,y) .where Hinsts U Hbag
(14)
Here, Hhag- levee, denotes the hypothesis space for the ith instance generated through bag-level features, and Hbag- = (htag-lewn lovel - }).
Intention-Pooling and Additive- multiply attention weights to each instance's 's feature-level. As a result, the hypothesis space for the 7th instance includes, in addition to Instance- Pooling, hbog- = {h h = f(Xbag), E Fbagh. In other words, it incorporates the hypothesis space for bag-level features into the prediction for the 7th instance. This, according to Theorem renders it not learnable for instances.
Consequence:
Proof: The proof of Theorem iss conducted in Appendix C.9
Validation: Experimental verification of Theorem is demonstrated in Section 4.4.2
On the other hand, Conjunctive-Powe Poooiing does not multiply attention at the feature level of instances, but rather at the prediction level of instances. Therefore, predictions are made based on individual features of instances, resulting in Hbog-tevel, = 0. satisfying Condition I0, Additionally, Theorem demonstrates that Conjunctive-Pooliin operates in a manner that is learnale for instances.
Theorem When MII. algorithms use Conjunctive- for aggregation DGen, they are learnable for instances.
7

---

According to Theorem 9 Conjunctive-Pooliie becomes the unique pooling technique learnable for instances in XXy Specifically, since Deen includes Dind by definition, Conjunctive- Pooling becomes methodology that satisfies all cases.
Consequence:
Proof: The proof of Theorem 9 conducted in Appendix C.10
Validation: Experimental validation for Theorem is presented in Section 4.4.2)
Javed et al.(9] demonstrated that the contribution of instances in MIL. algorithms performing Additive- Pooling is proportional the shapley value However, their proof contained an error where the feature multiplied by attention was mistakenly assumed to be the feature of the ith instance. Our theoretical framework identifies that when attention is applied to features, it fails satisfy Condition I0, leading to the algorithm being not learnable.
In this study, we confirmed that the error causing failure satisfy Condition also appears in studies proposing MIL based on Conjunctive-Pood 23 10 Details on this are explained in Section 4.3.1
4.3
Additional Considerations
4.3.1
Rethinking Position Dependencies of Instances Deep MILS
Text data and time series data exhibit temporal dependencies, while image data often has spatial dependencies. Therefore, research in relevant fields has utilized neural networks capable of capturing dependencies, such as RNNs and CNNs 226 extracted features to enhance performance 32
27
28
29
30
31 or additional positional encoding
33
35
36 37]. Following this trend, Deep MIL
studies have also employed RNN-based neural networks positional encoding during the feature extraction process to capture temporal dependencies of instances for performance enhancement [23] these approaches render the models unable
19 10. However, as per Theorem T0 and Theorem IT learn from instances.
Theorem 10 the MIL algorithm extracts features of instances through RNN-bused neural networks for aggregation, it is unable to learn from instances.
Proof: The proof for Theorem 10 is conducted in Appendix C.11
Validation: The experimental validation for Theorem
presented in Section 4.4.3
Theorem 11 the hypothesis space (Poo-Encodde generated through positional encoding values for the i-th position of the MIL algorithm is not a subset of Hinst,, then the algorithm not PAC learnable for instances.
Proof: If ESPos-Encode, Hinsto the algorithm fails to satisfy Condition 9 rendering it not learnable for instances.
Validation: Experimental validation for Theorem T0 is shown in Section 4.4.3
Consequence: According Theorem 77 using values outside of instance's 's features in the prediction process makes it unlearnable. Therefore, positional encoding should not be used in the process of predicting instances.
According to the investigation conducted in this study, it was observed that existing Deep MII. research using Sonjunctive-Pooline such as MILNET (23 and MILLET [10, all utilized RNN-based neural networks for feature extraction or performed positional encoding on instance features. Therefore, they failed to satisfy Condition D making them unable to learn about instances. Furthermore, these theoretical findings provide basis for the ablation study conducted by Early et al. [10] on time series data classification problems, where Conjunctive-Pooline predict the class at each time step. In essence, Early et al. [I0 demonstrated that while positional encoding contributed improving prediction performance at the bag level, it acted a detrimental factor in predicting instances. When utilizing external information such as positional dependencies through supplementary weighting factors like attention operations alone, Condition 9 may satisfied, thereby enabling learnability concerning instances.
and positional encoding were applied to
4.3.2 Learnability for Instances in Each Dimension for Multidimensionall Deep MILs
In the real world, data often composed of bags consisting of multi-dimensional instances rather than simple instances of uniform dimensions. For instance, in video data, each frame(inages)
8

---

is composed of patches in celliidimeesional structures for each frame dimension. Similarly, in multivariate time series data, each timestamp is composed of multivariate data points. the case of multi-dimensional instances, Multi-dimensional Deep MIL (MD-MIII) methodologies have emerged to perform predictions on lower-level instances based solely on labels at the top level of the bag. These methodologies apply aggregation recursively, performing aggregation on data in the first dimension and sequentially on subsequent dimensions. Existing MD-MIL approaches have employed seieeedddin-Pooliiig or IitentionPPooling for each dimension's 's instances. However, these pooling methods have been shown by Theorems 7 andd be incapable of learning about instances. Therefore, existing MD-MIL methodologies are not suitable for learning from multi-dimensional instances.
Therefore, to design methodologies capable of learning from multi- dalti--immnsional data, is essential to use aggregation techniques that are capable of learning about instances, based on Theorem 6 or [ Additionally, to ensure learnability from the top-level bag and bags each dimension, the attention operation's 's results should be set to be within the instance's 's hypothesis space based on whether the relationships among instances in each dimension are independent or dependent. Through the experiments in Appendix E.2 we confirmed that Srnjunctive-Pooliiii
capture the relation- ships between instances across different bags in an MD-MIL architecture, leading to performance improvements. These findings confirm that our proposed theoretical framework serves as a valuable guide in designing learnable models.
4.4 Experimental Validation
In this section, we conduct the following experimental validations to demonstrate whether existing Deep MIL. approaches are learnable for instances based on the theorems: 1) (Theorem (5) Demon- strating the Icarnability of the attention mechanism for bags in Dx 2) (Theorem g
Showing
that multiplying attention at the feature level is not learnable for instances. 3) (Theorem 10
Demonstrating that inputting position-related values into instance positions is not learnable for in-
stances. As this study assumes an environment where bags PAC Learnable, we preprocess the MNIST dataset to match the difficulty level of each experiment. For the validation of Theorem and 11. we the WebTraffic dataset from Early et al. [10], which is synthetic time-series classification dataset. Detailed experimental settings can be found in Appendix D
4.4.1 Experimental Validation of Theorem
To validate Theorem 5 we conducted experiments on MIL algorithms 5 21 38
19 10)
representing each pooling technique. Table 2 compares prediction performance on the synthetic datasets, detailed in Appendix D.I This reveals that Instance-Pooling based MIL algorithms 21 38), which do not apply weights to the hypothesis space, degraded learning performance for bags 9 I0 that apply weights to the hypothesis space through the attention mechanism demonstrate superior performance. which is even comparable to none- cone-pooling-- pooling-based based method that, by using fully connected layers, preserves all instance-level information without any loss during prediction. This experimentally validates Theorem 5
in Der In contrast, the other algorithms [2] 33
40
19
Table 2: Prediction performance of Deep MIL
Bags in Dee.
Pooling Methods
Deep MIL Algorithms
Macro-Fl
Micro-Fl
Weighted-F1
Instance-Pooling
mi-Net [
0.3286
0.5548
0.4550
Causal MIL
21
0,2341
0,3577
0,2645
MIREL 38
0,3623
0.5318
0,4372
Attention-Pooling
Attention MII. 2
0.7652
0.7683
0.7583
Loss-Attention 39
0.7935
0.7832
0.7753
SA-AbMILP 40
0.7540
0.7619
0.7562
TransMIL [19]
0.7834
0.7711
0.7738
Additive-Pooling
Additive MIL
9
0.5314
0.6341
0.5732
Conjunctive-Pooling
Conjunctive MIL [10
0.7544
0.7701
0.7683
None-Pooling
Fully Connected
0.7704
0.7724
0.7714

---

4.4.2 Experimental Validation of Theorems and
To assess whether the algorithm 2 39
9 10 is learnable for instances when weights from an attention mechanism that satisfies Condition are multiplied at the feature level, we compared the predictive performance instances by adjusting the variance of attention weights.
40
19
Table 3 shows the results on the synthetic dataset, which details Appendix [D2 Attention- Poollig based 2 39 40] [9] and Additive-Pooling based [9] MIL algorithms,, where attention weights are multiplied at the feature level and aggregation performed, showed significantly lower predictive performance for instances compared to bags. In particular, SA-AbMILP 40 and TransMIL [[9], which perform iterative attention operations, show a significant performance gap between bag-level predictions and instance-level predictions. This demonstrates that the Attention-Poolin based MIL algorithms [TO]
process does
not guarantee the learnability of MIL. contrast, Conjunctive-Poolle exhibited much smaller difference in predictive performance between bags and instances than other algorithms. This validates, in accordance with Theorem 2 that Conjunctive- Prooiin is learnable for instances, Additionally, experiments adjusting the variance of attention to determine its impact on the discrepancy between bag and instance performance are detailed in Appendix E.T
Table 3: Prediction performance comparison of MIL algorithms on bags and instances.
Performance for bags (P Bag)
Performance Instunees (P mat))
P Pinst
Pugg
Deep MII. Algorithms
Macro-F1
AUROC
Macro-FI
AUROC
Macro-F1
AUROC
Attention MIL 2
0.8434
0.9516
0.3215
0.7317
-0.5219
-0.2199
Loss-Attention (39
0.8228
0,9574
0.4797
0.7951
-0,3431
-0.
SA-AbMILPP 40
0,7692
0,9552
0,3340
0.5464
-0.4352
-0.4088
TransMIL [1
0,8515
0,9622
0,2192
0,5369
-0.6323
-0.4253
Additive MIL
0.4776
0.9181
0.2320
0,8092
-0,2456
-0.1089
Conjunctive MII.
10
0.7916
0.9463
0.6430
0.9516
-0.1486
+0,0053
4.4.3 Experimental Validation of Theorems 10 and 11
Table 4 compares the performance of Conjunctive MIL under various conditions, reflecting infor- mation on positional dependency: 1) Applying attention and prediction features extracted via Positional Encoding or a GRU-layer (AlI), 2) Using positional information only for attention opera- tions (Att), 3) Using positional information only for prediction (Predict), and 4) The baseline model without any positional adaptations (Default).
Comparative results the WebTraffic dataset's instance prediction performance reveal that configu- rations All and Predict, which provide additional positional information to features as in Theorem 10 and showed poorer prediction performance than Default. Particularly, RNN, which reflects more additional information than positional encoding, was found to significantly degrade performance. However, the Att configuration, which utilized positional information solely for attention operations, achieved better performance than Default. This demonstrates that incorporating helpful information such positional data, into MIL. should be selectively applied to attention computations only.
Table 4: Test positional dependencies for WebTraffic datasets
10
Default
PE (All)
PE (Att)
PE (Predict)
RNN (All)
RNN (Att)
RNN (Predict)
AOPCR
13.041
12.372 0.665
14.555
12.256 0.642
9,011 0.620
17.502
12.21
NDCG@n 0.676
0.727
0.714
0.523
5
Conclusions
In this study. we proposed a novel framework to theoretically validate that deep MIL can learn the instance level. overcoming the aforementioned issues. The proposed theoretical framework derived conclusions about the instance-level learnability of deep MIL. algorithms, assuming that MIL algorithms are learnable at the bag level. Utilizing the PAC learning theory, we theoretically derived the necessary and sufficient conditions for learnability in each hypothesis space. This provides theoretical guidance for building learnable MIL models various domains. The practical application of our proposed framework to real-world MIL scenarios is presented in Appendix F Limitations and future work are explained Appendix G
10

---

Acknowledgement
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea (MSI) (No. 2022RIFIA 1067008)), and by the Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (No.
2019R1A6ALA03032199)
References
[1] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[2] Maximilian Ilse, Jakub Tomezak, and Max Welling. Attention-base based deep multiple instance learning. In International conference on machine learning, pages 2127-2136. PMLR, 2018.
[3] Oded Maron and Tomás LozznnoPPéezz framework for multiple-instance learning. Advances in neural information processing systems, 10, 1997.
[4] Thomas G Dietterich, Richard H Lathrop, and Tomás Lozano-Pérez Pérez. Solving the multiple instance problem with axis uxis-parallel rectangles. Artificial intelligence, 89(1-2)31-71, 1997.
[5] Xinggang Wang, Yongluan Yan, Peng Tang, Xiang Bai, and Wenyu Liu. Revisiting multiple instance neural networks. Pattern Recognition, 74:15-24 1-- 2018.
[6] Alessandro Tibo, Manfred Jaeger, and Paolo Frasconi. Learning and interpreting multi-multi- instance learning networks. Journal of Machine Learning Research, 21(193):1-60) 2020.
[7] Yu Tian, Guansong Pang, Yuanhong Chen, Rajvinder Singh, Johan W Verjans, and Gustavo Carneiro. Weakly-supervised video anomaly detection with robust temporal feature magnitude learning. In Proceedings of the IEEE/CVF international conference on computer vision, pages 4975 1975-4986, 2021.
[8] Hui Lv. Zhongqi Yue, Qianru Sun, Bin Luo, Zhen Cui, and Hanwang Zhang. Unbiased multiple instance learning for weakly supervised video anomaly detection. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2023.
[9] Syed Ashar Javed, Dinkar Juyal, Harshith Padigela, Amaro Taylor-Weiner, Limin Yu, and Aa- ditya Prakash. Additive mil: Intrinsically interpretable multiple instance learning for pathology. Advances in Neural Information Processing Systems, 35:20689-20702. 2022.
[10] Joseph Early, Gavin Cheung, Kurt Cutajar, Hanting Xie, Jas Kandola, and Niall Twomey, Inherently interpretable time series classification via multiple instance learning. In The Twelfth International Conference on Learning Representations, 2024.
[11] Peter Auer, Philip M Long, and Aravind Srinivasan. Approximating hyper-rectangles: Learning and pseudo-random sets. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 314-323, 1997.
[12] Philip M Long and Lei Tan. Pac learning axis-aligned rectangles with respect to product distributions from multiple-instance examples. Proceedings of the ninth annual conference on Computational learning theory, pages 228-234, 1996.
[13] Avrim Blum and Adam Kalai. A note on learning from multiple- instance examples. Machine learning, 30:23-29, 1998.
[14] Boris Babenko. Multiple instance learning: algorithms and applications. PubMed/NCBI Google Scholar, 19, 2008.
View Article
[15] Gary Doran and Soumya Ray. Multiple-instanne learning from distributions. Journal of Machine Learning Research, 1-1128) 2016.

---

[16] Weiming Hu, Chen Li. Xiaoyan Li, Md Mamunur Rahaman, Jiquan Ma, Yong Zhang, Haoyuan Chen, Wanli Liu, Changhao Sun, Yudong Yao, al. Gashissdb: A new gastric histopathology image dataset for computer aided diagnosis of gastric cancer. Computers in biology and medicine, 142:105207, 2022.
[17] Sivan Sabato and Naftali Tishby. Multi-instance learning with any hypothesis class. The Journal of Machine Learning Research, 13(1):2999-300 3039, 2012.
[18] Edward Raff and James Holt. Reproducibility in multiple instance learning: A case for algorith- mie unit tests. Advances in Neural Information Processing Systems, 36, 2024.
[19] Zhuchen Shao, Hao Bian, Yang Chen, Yifeng Wang, Jian Zhang, Xiangyang Ji, et al. Transmil: Transformer based correlated multiple instance learning for whole slide image classification. Advances in neural information processing systems, 34:2136-211 2021.
[20] Saul Fuster, Trygve Eftestøl, and Kjersti Engan. Nested multiple instance learning with attention mechanisms. In 2022 21st IEEE International Conference on Machine Learning and Applications (ICMLA), pages 220-225. IEEE, 2022.
[21] Weijia Zhang, Xuanhui Zhang. Min-Ling Zhang, et al. Multi-instance causal representation learning for instance label prediction and out-of-distribution generalization. Advances in Neural Information Processing Systems, 35:34940-34953, 2022.
[22] Weijia Zhang, Lin Liu, and Jiuyong Li. Robust multi-instance learning with stable instances. In ECAI 2020, pages 1682-1689. IOS Press, 2020.
[23] Stefanos Angelidis and Mirella Lapata. Multiple instance learning networks for fine-grained sentiment analysis. Transactions of the Association for Computational Linguistics, 6:17-31, 2018.
[24] Jaeseok Jang and BYUK-YOON KWON. TAIL-MIL: Time-aware and instance-learnabe multiple instance learning for multivariate time series anomaly detection. In The 39th Annual AAAI Conference on Artificial Intelligence. 2025.
[25] Scott M Lundberg and Su-In Lee. A unified approach to interpreting model predictions. Advances in neural information processing systems, 30, 2017.
[26] Jun Zhang and Kim- Man. Time series prediction using rnn in multi-dimension embedding phase space. In SMC 98 Conference Proceedings. 1998 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No. 98CH36218), volume pages 1868-1873. IEEE, 1998.
[27] Jun Zhang and Kim- FFng Man. Time series prediction using mnn in multi-dimension embedding phase space. In SMC'98 Conference Proceedings. 1998 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No. 98CH36218), volume 2, pages 1998.
IEEE,
[28] Gang Liu and Jiabao Guo. Bidirectional lstm with attention mechanism and convolutional layer for text classification. Neurocomputing, 337:325-338, 2019.
[29] Rahul Chauhan, Kamal Kumar Ghanshala, and RC Joshi. Convolutional neural network (cnn) for image detection and recognition. In 2018 first international conference on secure cyber computing and communication (ICSCCC), pages 278-282. IEEE, 2018
[30] Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lei Zhang. Learning deep enn denoiser prior for image restoration. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3929-3938, 2017.
[31] Yanan Sun, Bing Xue, Mengjie Zhang. Gary G Yen, and Jiancheng Lv. Automatically designing cnn architectures using the genetic algorithm for image classification. IEEE transactions on cybemettcs, 50(9):3840-3855 2020.
[32] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need, Advances in neural information processing systems, 30, 2017.
12

---

[33] Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. Autoformer: Searching trans- formers for visual recognition. In Proceedings of the IEEE/CVF international conference on computer vision, pages 12270-12280, 2021.
[34] Haoyi Zhou, Shanghang Zhang, Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11 1010-11115, 2021.
[35] Alexey Dosovitskiy. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint (xXi:201001192)) 2020.
[36] Rui Xu, Xintao Wang, Kai Chen, Bolei Zhou, and Chen Change Loy. Positional encoding as spatial inductive bias in gans. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 15569-13578, 2021.
[37] Kan Wu, Houwen Peng, Minghao Chen, Jianlong Fu, and Hongyang Chao. Rethinking and improving relative position encoding for vision transformer. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10033-10041, 2021.
[38] Pei Liu and Luping Ji. Weakly-supervised residual evidential learning for multi-instance uncertainty estimation. In Forty-first International Conference on Machine Learning. 2024.
[39] Xiaoshuang Shi, Fuyong Xing, Yuanpu Xie, Zizhao Zhang, Lei Cui, and Lin Yang. Loss- based attention for deep multiple instance learning. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages
2020.
[40] Dawid Rymarczyk, Adriana Borowa, Jacek Tabor, and Bartosz Zielinski. Kernel self-attention image classification using deep multiple instance learning. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1721-1730, 2021.
for
[41] Yan Xu, Tao Mo, Qiwei Feng, Peilin Zhong, Maode Lai, I Eric, and Chao Chang. Deep learning of feature representation with multiple instance learning for medical image analysis. In 2014 IEEE international conference on acousties, speech and signal processing (ICASSP), pages 1626-1630. IEEE, 2014.
[42] Dimitrios Kotzias, Misha Denil, Nando De Freitas, and Padhraic Smyth. From group to individual labels using deep features. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 597-606, 2015.
[43] Yunjie Ji, Hao Liu, Bolei He, Xinyan Xiao, Hua Wu, and Yanhua Yu. Diversified multiple instance learning for document-level multi-aspect sentiment classification. In Proceedings of 2020 conference on empirical methods in natural language processing (EMNLP), pages 7012-7023, 2020.
[44] Jun Wang and Jean-Daniel Zucker. Solving multiple-instance problem: A lazy learning approach. 2000.
[45] Waqas Sultani, Chen Chen, and Mubarak Shah. Real-world anomaly detection in surveillance videos. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6488, 2018.
[46] Oren Z. Kraus, Jimmy Lei Ba, and Brendan J Frey. Classifying and segmenting microscopy images with deep multiple instance learning. Bioinformatics. 32(12):152-i5 2016.
[47] Lei Zhou, Yu Zhao, Jie Yang, Qi Yu, and Xun Xu. Deep multiple instance learning for automatic detection of diabetic retinopathy in retinal images. IET Image Processing, 12(4):563-57, 2018
[48] Yongluan Yan, Xinggang Wang, Xiaojie Guo, Jiemin Fang, Wenyu Liu, and Junzhou Huang. Deep multi-instance learning with dynamic pooling. In Asian Conference on Machine Learning, pages 662-677. PMLR, 2018.
13

---

[49] Seung-Ky Hong, Jae-Seok Jang, and Hyuk- Yoon Kwon. Enhancing performance of transformer-bast based models in natural language understanding through word importance embed- ding. Nowledge--Bssed Systems. 304:1 12404, 2024.
[50] Haoyi Zhou, Shanghang Zhang, Jieqi Peng. Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI conference artificial intelligence, volume 35, pages 11106-11115,
2021.
[51] Jong Seong Park, Jeong-Ha Park, Jihyeok Choi, and Hyuk-Yoon Kwon. Learning with correlation-guided attention for multienergy consumption forecasting. IEEE Transactions on Industrial Informatics, 2024.
[52] Joseph Early, Christine Evers, and SArvapali Ramchurn. Model agnostic interpretability for multiple instance learning. In International Conference on Learning Representations, 2022.
[53] Hang Zhao, Yujing Wang. Juanyong Duan, Congrui Huang, Defu Cao, Yunhai Tong, Bixiong Xu, Jing Bai, Jie Tong, and Qi Zhang. Multivariate time-series anomaly detection via graph attention network. In 2020 IEEE international conference on data mining (ICDM), pages 841-850. IEEE, 2020.
[54] Taehee Kim, Jae-Seok Jang, and Hyuk-Yoon anomaly detection on multiple energy sources. Applied Soft Computing, 159:1 1636, 2024.
Yoon Kwon. Correlaioon-driven multi-level learning for
[55] Yingying Zhang, Desen Zhou, Siqin Chen, Shenghua Gao, and Yi Ma. Single-image crowd counting via multi-column convolutional neural network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 589-597, 2016.
[56) Wen Liu, Weixin Luo, Dongze Lian, and Shenghua Gao. Future frame prediction for anomaly detection-a new baseline. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6536-65455 2018.
[57] Mare-André Carbonneau, Veronika Cheplygina, Eric Granger, and Ghyslain Gagnon. Multiple instance learning: A survey problem characteristics and applications. Pattern Recognition, 2018.
[58] Zhi-Hua Zhou and Jun-Ming Xu. On the relation between multi-instance learning and semi- supervised learning. In Proceedings of the 24th international conference on Machine learning, pages 1167-1174, 2007.
[59] Ragav Venkatesan, Parag Chandakkar, and Baoxin Li. Simpler non-parametric methods provide as good or better results to multiple-instance learning. In Proceedings of the IEEE International Conference on Computer Vision, pages
2015.
[60] Wu-Jun Li et al. Mild: Multiple-instance learning via disambiguation. Iece transactions on knowledge and data engineering, 22(1):76-89, 2009.
[61] Jaume Amores. Vocabulary-based approaches for multiple-instii instaace data: A comparative study. In 2010 20th International Conference on Pattern Recognition, pages 4246-4255 4250. IEEE, 2010.
[62] Yixin Chen, Jinbo Bi, and James Ze Wang. Miles: Multiple-instance learning via embedded in- stance selection. IEEE transactions on pattern analysis and machine intelligence, 28(12):1931. 1947, 2006.
[63] Zhouyu Fu, Antonio Robles- Kebles--Kelly, and Jun Zhou. Milis: Multiple instance learning with instance selection. IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(5):958-977, 2010.
[64] Shengye Yan, Xiaodong Zhu, Guoqing Liu, and Jianxin Wu. Sparse multiple instance learning as document classification. Multimedia tools and applications, 76:4553 4570, 2017.
[65] Dan Zhang, Yan Liu, Luo Si, Jian Zhang, and Richard Lawrence. Multiple instance learning on structured data. Advances in Neural Information Processing Systems, 24, 2011.
14

---

A Related Works
A.1 Multiple Instance Learning
Multiple Instance Learning (MIL), type of weakly supervised learning, is methodology where labels are assigned to bag of instances rather than individual instances, allowing for predictions field of chemistry
about individual instances based on the bag's label. MIL was first introduced to identify active molecules and has since been applied to various domains, including medical image analysis, text data processing, time-series data analysis, and video anomaly detection 8
2
22 43 44
10 45
In medical image analysis, accurate labeling of cancer cell locations requires significant time and effort. However, it is possible to use MIL to predict cancer cell locations with labels for the entire image. In text data, documents or reviews are treated as a single bag. and MIL allows for more detailed analysis by predicting the attributes of each instance within document or review. MIL is also effectively used time-series data and video anomaly detection for cause analysis and anomaly detection.
A.2 Type of Pooling in Multiple Instance Learning
Deep MIL methodologies be broadly classified based on the pooling mechanism into the following
categories: 1) Instance-Pooling, 2) Embeddingg 3) AttentionPPooling. 4) Additive-Pooling and 5) Conjunctive-Pooling.
The functional architecture of MIL incorporates several key components designed for processing instances within bag. The feature extraction function for the 7th instance is denoted by fx()). Furthermore, we utilize classifier functions to make predictions based on these features: (X,, targets the features of the 7th instance, while p(X) handles features aggregated at the bag level. The attention weight assigned the jth instance is expressed as A, Additionally, the aggregation function, pivotal for our pooling techniques, is represented by gX)). The various pooling methods utilized in our framework are described as follows:
(Instance-Pooling)
Instance-poolee performs predictions for each instance individually and then uses the max mean operator to aggregate results:
NV max(p; (X,)
Imaz pooting (X)
;=
N
Imean-pooling (X)
Σ
(p, o fx)
(Fmbbedding-Pooling)
Embedding-poolle obtains features for each instance and then uses the max or mean operator to aggregate these features to obtain feature representation for the bag, on which predictions for the bag are made:
N 9maz-pooling (X) pl m/x f((X))
N
(X) = pl N
Σ f(()))
(Attention-Pooling)
Attention-pont pooiiinn multiplies the features of each instance by attention weights and then performs embedding- poooldnggg-ooiing using the summation operator on the weighted features:
15

---

x(X)= - pl Σ Axf((.)))
(Additive-Pooling)
Additive-pooling multiplies the features of each instance by attention weights, obtains individual predictions for each instance, and then performs a summation operation to make predictions for the bag:
9X) Σ (p (x,)
(Conjuncttive-Poolinn)
Conjunctive-poole multiplies the individual predictions of instances by attention weights and performs aggregation through weighted sum:
N Σ (Asp. o fi)(s)) -=1
9(X)
A.2.1
Attention Mechanism
In early deep MIL,, the role of the deep network was to better extract the features of instances and to accurately predict instances through pooling operations in an end-to-end manner 48)
Early deep MIL models had the limitation that the bag-level prediction does not accelerate the instance-level prediction because predictions for instances were performed separately from predictions for the bag. To overcome this limitation, attention mechanisms have been used in various MIL methodologies 2 23 mechanisms have shown significant performance improvements by capturing relationships within the data. Due to these characteristics, attention weights, based on the features of all instances, assign higher weights to important instances for bag predictions, making them useful for instance-level These weights have been shown to improve the prediction performance
10 20 In other deep learning research [32 35 50 51], attention
predictions as well 2 19 20
of instances 23 9
A.2.2 Level of Aggregation
Deep MIL requires aggregating the values of instances perform predictions for the bag. Early deep MILL models performed individual predictions for instances and then aggregated these predicted values using differentiable pooling operators
[5]. However, the approach making individual predictions for instances was not effective in improving the prediction performance for the bag. To enhance bag prediction performance, new methods were proposed that perform pooling operations on features extracted from each instance to obtain feature representation for the bag and then learn the bag. These methods apply the classifier used for the bag to instances [5] or cluster the features of instances to find similar instances (6]
In the case of deep MIL utilizing the attention mechanism, early methods enhanced performance by multiplying the features of each instance by attention weights, performing mean pooling to extract feature representation for the bag, and using that feature train the bag 19 20]. This approach suggested that instances with higher attention weights contributed more to the bag's 's prediction. However, while feature-level aggregation allowed for effective bag predictions, did not facilitate detailed predictions for individual instances. Conversely, applying attention and aggregating the prediction results for instances achieved high performance prefers aggregating the prediction results for instances.
99, 10
Due this trend, recent research
16

---

A.3 Theoretical Study of Multiple Instance Learning
early theoretical research on MII. focused on simple algorithms such as axis-aligned rectangles, which facilitated the derivation of theoretical results 12] Blum et al. [33] proposed an algorithm that illustrated the relationship between supervised learning and MII,, showing that if a supervised learning algorithm learn concept space, MIL can also learn within that space. Sabato et al. [17] addressed the limitations of previous MIL research, which often derived theoretical results for specific domains or simple hypothesis classes, by presenting generalized theoretical framework applicable to various hypothesis classes and complex data structures. This framework allowed the evaluation of learnability for bags without being limited to specific algorithms. Raff et al. [8] argued that deep MIL algorithms do not adhere to standard MIL assumptions and are unsuitable for world environments. They proposed algorithm unit test verify adherence these assumptions, ensuring that models can accurately predict bags in real-world scenarios.
According to Babenko et
However, all theoretical research proposed on MII. thus far has focused solely whether MII. can learn bags as effectively as supervised learning without addressing the primary purpose MIL- predicting individual instances. Therefore, to address this issue, this study proposes a theoretical framework that can universally evaluate whether an algorithm is learnable instance level.
B Notations
The key notations used in Definitions, Theorems, Conditions, and Proofs this study are summarized in 5
Table 5: Notations.
Notations
Description
Feature Spaces
X
bag-level feature space, X' := (Kinaty Xinsty ... Xinsty i Ninstt))) the feature of the jth instance in the bag
snst
label Spaces
y
bag label space y : (1,,..k) instance label space y = {I,..k}
V
Domains
DXY
joint distribution on V, DXY = U DxmonR joint distribution Xinst; x y
D Pxmuyy
Domain Spaces
Dxy
the set space composed of Dxy the bag domain space with mutually independent domains for all instances the bag domain space with mutually dependent domains for all instances the entire bag domain space, Dind U UD
XY D Dep Deen
Hypothesis Spaces
Hong
bag hypothesis Space
Hinst;
5th instance Hypothesis Space, Hinst, = (h+ (x;))) - Y;}
Hadd.
extra hypothesis space from external values for 7th instance
Risks
Bong
risk corresponding to bag domain DXY
Rinats
risk corresponding to instance domain D Dxm.,,
RD
risk corresponding domain D
17

---

C Theoretical Proofs
C.1 Proof of Theoremm T
Theorem[iu MIL algorithm A satisfies Condition 1 then this algorithm is not PAC learnable for any instance domain space D Xx.., Y and instance hypothesis space iiss C. Khnss X + Y).
U Rinst, (A(Sinet.)) - inf he heHin
Rinet, (h)) > e >
Condition The MIL algorithm A is not PAC learnable for the given domain space Dxy and bag hypothesis space H.bag C. {heag X + }}:
P Rbeg (A(S))
inf Reag (hi) 6 8
hEHaag
Proof The performance of MIL algorithms on bags directly depends on the performance of the instances composing those bags. Therefore, the probability that bag's performance does reach the optimal hypothesis is greater than or equal to the probability that each individual instance does not reach the optimal hypothesis:
Rinsts (A(Sinstz))
inf kEHSnat,
Rinst, (h)) > 2 P
|Bag (A(())
inf
Reng (t))
hEHbag
Condition satisfied, the probability that the bag's performance does not reach the optimal hypothesis can be expressed as follows:
P Rbog (Obog(((S) (A(S))
inf heHong
Roag (h)) >
instances become unlearnable. Ultimately, if the bag is not learnable, then
T
U
Rinst, (A(Sinst.))
inf hEMinst,
Rinst, (h)) > 6
C.2 Proof of Theorem
Theorem If MIL algorithm satisfies Condition 4 in D'ad. it is learnable for instances.
Condition 4 The optimal hypothesis for Dind must be equal to the sum of optimal hypotheses for each individual instance space within D D
inf R KEH
Σ 1=1
inf Rinsts
Proof First, let's assume that the MIL algorithm satisfies Condition in Plg. Based on this assumption, we apply Definition to verify the learnability of MIL in the independen bag hypothesis space.
The learnability in the independent bag hypothesis space means that the algorithm likely to return predictions within an acceptable error margin from the true optimal hypothesis:
P P Dry
[RD(A(S))
inf Ro(h)) se 2 21-8
heH
18

---

Here, S represents the training data, and A(S) denotes the predictions returned by the MIL algorithm.
(h) represents the actual risk hypothesis Now, this probability expanded as follows:
PSNDRY [RD(A(S))
hEHoo RD(h)] S
inf
PS RD(((S)) S inf RD(h) +
heH
Now, this probability can be expressed as follows:
DTy RD(A(S)) & inf RD(h) + hEHow
Σ Ps DS-D Kinet
RD(A(S)) - inf RD(h) +
In the above equation, N represents the number of instances.
This equation implies that the learnability of bags and instances becomes equivalent. Since assumed that bags are learnable according to Assumption I Condition 4 becomes a necessary and sufficient condition for the learnability of instances.
C.3 Proof of Theorem
Theorem If MIL algorithm satisfies Condition in Der XY it is learnable for instances.
3
Condition The optimal hypothesis DXy must guarantee that it is equal weighted sum of optimal hypotheses for each individual instance space within Xy
inf R NEW
O4 inf Rinst,
Σ a, a,=1, 05 $
Proof To demonstrate that the learnability of bags equivalent to the learnability of instances, need to show that the following conditions are satisfied:
P inf R
Σ as inf Rinst, > 8
This equation represents that the weighted sum risks for bags and instances exceeds the permissible еπоог with probability d or less. Therefore, if this equation is satisfied, the learnability of bags and instances becomes equivalent.
In other words, it indicates that the probability that the difference between the risk for each instance and the weighted sum of the entire bag risks is within the permissible error N least 1 8.
P Vi, inf Rnger a; inf Rinst,
> 1 1
N
Through the inequality for the risk of each instance, we can obtain the following:
Oe inf Rinst, - inf RD <
Vi
N
To prove this, let's define the random variable Xinst, as the difference in risk for each instance:
Xinst, inf RDger Or inf Rinst:
Let's set the range of each ins, to [-M, .M. and define e; as the mean of Xinst,- Gj becomes due to cancellation between iii R and E(a, inf Ranst:].
19

---

Ci R[[ [[Xinst,] =
Let's define the function f f(Xinst, Xinstz .., Xinoxx the optimal risk over the general bag domain Dee:
[(Xinsty: Xinsty
xinstx) inf RDg
In this setup, the instances within bag are not independent; instead, they interact and contribute collectively to the overall bag risk. To capture the effect of each instance on the bag's s optimal risk, we introduce weights a that represent the contribution each instance's ' risk to the total risk. This allows us define the expected value of f as the weighted sum of the optimal risks of each instance domain:
N aj inf Rinst:
(X Xinst
Σ
This expression reflects the dependencies and interactions between instances, allowing to represent the general bag risk as function of each instance's 's weighted risk.
In the general bag domain space, where one or more instances may have dependent relationships, we apply the Azuma-Hoefiding inequality.
211
IP [I Enstr X Xinstx) )
Xinsty ))1
S
2exp
N
Since f(Xinet Xinetz:... Xinsty) represents the risk the bag as stated earlier, the equation can be written as follows:
2112 N
PP inf Rog - iif R R S exp
1i=1
The term in inf R R Efinf R pgy || represents the deviation from the expected value, so it can be replaced by the permissible enror for learnability, yielding the following:
-2e2
P [inf Ro - Elinf R >
< 2exp
Σ
Finally, it can be expressed as follows:
22
P inf R De
Σ as inf Rinsts > E
<
eexp
===
represents the mean of errors. Since Deep MIL algorithms are trained minimize the mean error, EN.C. =0
P
inf Roag Σ ag inf Rinst
This ensures that the sum e, values remains within certain range, guaranteeing that is smaller than the probability of being trained within the permissible error range c, denoted as 8.
20

---

-2
2 exp
+
log
Σ
2
Therefore, under the assumption of successful learning, Condition MII. model becomes learnable for instances.
2 is satisfied. Thus, well-trained
C.4 Proof of Theorem
Theorem In D&y. the MIL algorithm is PAC learnable for bags.
Proof The PAC learnability of Diy implies that every concept space Cr can be approximated by hypothesis spaces H
CD C HDr
Since Diad assumes that predictions for all instances are independent, predictions for bags become the union of predictions for instances.
H
Ind XY
U Hinst,
1=1
The hypothesis space Hbagmon-ner for Non-Attention MIL algorithms, which do not use Attention, is also the union of predictions of instances:
H Hbagmon-
Hinst:
Thus, Hbagnon-att becomes equivalent to the hypothesis space Houg of PAC Learnable D
H Hbagmon-dd
Therefore, in the of PAC Learnable scenarios, Non-Attention MIL is learnable.
The hypothesis space Hoagur Attention MIL encompasses hypothesis space Hoogmon si of Non-Attention MIL:
Hbagaon-ats C Hbagate
Thus, if Df Ind XY is PAC Learnable, Attention MIL is also learnable.
Ultimately, Day is PAC Learnable, then all MIL algorithms can learn from bags.
C.5 Proof of Theorem
Theorem 5 In Gen, MIL algorithms that aggregate independent hypothesis spaces for each instance must utilize attention satisfying Condition 8 to be PAC learnable for bags.
Condition & The hypothesis space Hsagaes Attention MIL should be equal to the sum of indepen- dent hypothesis spaces hinst, multiplied by attention weights Att;:
n
Att: hinstes where Att, 1, Σ Att, = = }
n
Hiag.se
hbagars
Iibagats
Proof The PAC Learnability of XX implies that all concept spaces Cogy of Gen can be approxi- mated by the hypothesis space H D of Cen:
21

---

VHD E CDyy xy
Hgggy represents the union space of hypotheses H His,, with dependencies within the same bag. The optimal hypothesis within each instance space can be expressed as:
inf Reee,, inf hann, E
R
Combining these optimal hypotheses yields:
U
inf
RGen iiists
Σ
inf RGen Risst
From previous proofs, it's shown that the Azuma-Hoeffdee inequality satisfies:
N
P inf
RD@ - Σ
a inf Rioon
6 8
1=1
Thus, the hypothesis space Hlag for Den can be expressed as:
p hDggr
h
O4
hinster where 0 < aa <,, Σ a; 1
In proving the learnability of bags for D&y. it's shown that the hypothesis space for Non-Attention MIL algorithms is:
H Hoagmon
U Hynot:
The hypothesis space H Dg extends beyond the range of hypotheses that can independently predict all instances, incorporating dependencies with weighted hypotheses
Hoagwon D
H & Hoagmon-ate
Thus, Non-Attention MIL Algorithms are not learnable from Den
However, according to Condition g the hypothesis space of Attention MIL Algorithms is:
n1
n
Hangase
Jnnag.ers
All; hinstes where All; 1,
Σ
Atl
Here, replacing Att, with as makes Hoager identical to Hpgn:
Heagee HD
Thus, Attention MIL is learnable from Gen in terms of bags.
22

---

C.6 Proof of Lemmal
Lemma I Condition serves as a necessary condition for the learnabllity of instances, when the hypothesis space for the ith instance of a MIL algorithm is Hinst, J Hodd, Here, Hinst, represents the hypothesis space for the it instance, and Hadd, denotes the hypothesis space for the ith instance generated through elements outside the ith instance.
Condition 9 Hadd, must be subset of Hinst,;
Hinst; S Hadd, = {hadd, Xadd, - }
Proof
When Hinst; & Hadd, = (hadd; Radd; + })), the hypothesis space Houg for bags follows:
Hbog V
Hinst, Hadd,
In this case, using the Azuma-Hoefiding Inequality compare the deviation between Ring and each Binst,, we get:
Varl Rinst,
Rinst,
Rhag 26
N
N22
1=1
If hadd, is not subset of hinsts additional hypothesis space exists, resulting in deviation between the risk of the Bag-level hypothesis and the risks of each Instance.
Hence, the deviation between Roog and Rinst, is greater than equal to O:
inf Roag hEH
inf Rinet;
Therefore, fails to satisfy the necessary and sufficient condition for the learnability of instances in XY The independent bag domain space implies that all weights in the general bag domain space are equal, thus the relation is as follows:
Dind Gen
Hence, it's not learnable in the independent bag domain space, it means it's not learnable in the general bag domain space. Therefore, through the proposed theoretical framework, Condition becomes a necessary condition for MIL.
Thus, Condition becomes necessary condition for learning instances in MIL.
C.7
Proof of Theorem
Theorem
6 In D XY,
MIL algorithms that perform instance- instance-pooling are PAC learnable for instances.
Proof
First, the learnability of MII. algorithms on instances Dind means the algorithm satisfies Condi- tion 4
inf Ro
inf Rinst;
heWl
1=1
23

---

Performing Instance- Pooling means forming bag-level hypotheses by independently combining hypotheses each instance level. The error the bag level derived from instance-level pooling can be defined as follows:
Ry (hbog) sty (C(bbbg Y)]
We can express the error at each instance level as:
inf Rinst, inf RD he Hinots
Kinat,
Now, comparing the two errors, we have:
inf Rogy kEW
= inf B hEH
((((s))
-B(
inf (((())))))))))))))))()) x) NEH
N Σ
= -
inf h N:EHonut
((ng(iinot.)) Yenoe,)
Eg Dind
E(hi(Xinots) Yomsts) M.eHinn
inf
Xines
inf hiEti
E (Xenarg (Xenat Di and Xinus
(114(Xinstt) Vines))
inf Hinay
Rpind Xenat,
Thus, performing pooling on instance predictions satisfies Condition 4
This proves that MIL algorithms can learn from instances Dind
C.8 Proof of Theorem 7
Theorem MIL algorithms that perform Embedding-Poolle Pooliigg are learnable for instances.
Proof
In satheeddin-pooliing features of each instance are combined using aggregation function
F(X) = ((x)) (,(()))))))..,,,,,))))))
Here, (X;) represents the feature of each 8th instance, and is function that integrates features to generate a single vector. Consequently, Hodd, includes hypotheses based on F(X), making Hadd, dependent on the features of all instances, fi (x()), f2(22). ..... fx,,)..))
Hadd, {h F(X) + YY
On the other hand, Hinst, produces results dependent solely on the 5th instance feature:
Hinst, = [h: hx(x),) + Y₁}
function E Hadd; using FXX) cannot belong to Hänst, This because functions Hinst, only use X; as input, while h is based F(X), i.c., the combined result of all X; features. Since

---

functions in Hadd, have more complex dependencies beyond the scope of Hinst, the following inequality holds:
Hinst, P Hadd,
Therefore, MIL algorithms using Embedding poolldinggg fail to satisfy Condition rendering them incapable of learning from instances.
C.9 Proof of Theorem
Theorem If the MIL. algorithm does not adhere to Condition 10 it is not learnable for instances.
g
Condition 10 The risk Ranst; for the 5th instance should be follows:
Rinst: (wimaty a) Dxma,, linst, (h, v)
where h E Hinste U Heag-tevel,
Proof
If level is not empty, then the following holds:
N
4g > 0, 3h E Hbag Reag (h)
Rinst; (hinst,) ) + 6
For every > 0, there exists at least one predictor belonging to hbag- levet that can make the lower bound of Reag greater than the sum of the lower bounds of Σi=1 Ranste This implies that if hbag-Ieved not empty, it fails to satisfy Condition 9 Thus, hbag-level must be empty for Condition
to hold.
As result, Condition 10 also becomes necessary condition for MII. algorithms to be learnable from instances.
C.10 Proof of Theorem 9
Theorem 9 When MIL algorithms conjunctive pooling for aggregation in Den they are learnable for instances.
Proof
Condition being satisfied implies learnability from instances:
inf R
RD inf Rinst.
keH
XY
Here, a4 represents the weight for the ith instance, satisfying the following conditions:
N
a; E (0,
Q =
Given Assumption] where the MIL algorithm is assumed to be PAC learnable for bags, Rong becomes the lower bound of prediction error for bags, and Risst, becomes the lower bound of prediction error for each instance, Thus, Condition can be expressed as:
inf Rony
Σ 04 inf Rinst;
bEH
For Conjunctive Pooling, the optimal hypothesis heng for bags is:
25

---

Boag
The lower bound for the optimal hypothesis hisst, for the 7th instance is:
inf Rinss R ((iisss.))
Therefore, the lower bound of prediction error for the optimal hypothesis houg for bags is:
inf Rhag R(hhagg bER
R
Or Dinsttt
N inf B(x
Σ
ayyt (x),
ag inf Rinst,
Ultimately, MII. algorithms using Conjunctive Pooling satisfy Condition and are learnable from instances.
C.11 Proof of Theorem TO
Theorem 10 If the MIL algorithm extracts features of instances through RNN-based neural networks for aggregation, unable to learn from instances.
Proof When extracting features through an RNN, the hypothesis space of the 5th instance's features includes not only the hypothesis spaces based the 5th instance's 's information but also those based on the information of preceding instances to the ith one:
Hinst, ran
Hinst,
Therefore, when extracting features of instances through neural networks like RNNs, if Hinst, Lenet (x) := (haag : X + /} # V::
(hinst, Xinst, + }), then H
X Rinst, = Besemme,, 4)~ Dx linst, (h, y) where h Hinst; U Ubhag-ter level level
B Dx Xinay linst, (h, y) where he Hinst, UHinst.-ram Hinst, *
This means that when performing MIL using features extracted through RNNs, it fails to satisfy Condition 10 a necessary condition for learning from instances. Hence, it becomes incapable of learning from instances.
Therefore, fails to satisfy Condition
As side note, in the case of extracting features through bidirectional RNNs, the size of the hypothesis space would be:
N
Hinet, -irnn U
Hinst,
So, the same conclusion applies.
26

---

D Experimental Setting
D.1 Experimental Validation of Theorem
T explains that Instance pooling MIL, which aggregates instance hypothesis spaces indepen- dently, does not satisfy Condition 8 and thus is not learnable with respect Xy In contrast, the Conjunctive Pooling model, which multiplies weights by the hypothesis space instances to reflect the relationships among them, is learnable.
To validate this, we conduct comparative experiments on the following synthetic datasets, assuming X outside of D D'yy Each bag in the dataset is labeled based on the relationships between the ten instances constituting the bag, and one four labels is assigned accordingly.
Label 1: If the bag contains both 3 and 5, the bag's ' label is 1.
Label 2: If the bag contains but not 7, the bag's label is 2.
Label 3: If the bag contains and also contains 7, the bag's label is 3.
Label 0: Any bag that does not meet the criteria for other labels assigned the negative label 0.
Under these labeling assumptions, the MNIST dataset's training data is split into training and testing datasets in an 8:2 ratio. Then, ten images are randomly selected to form a bag, and labeling is performed according the assumptions.
Label: 0
7
8
6
6
9
9
7
9
Label: 1
8
2
9
6
3
7
5
5
9
Label: 2
6
7
4
2
3
3
8
Label: 3
2
8
7
6
9
7
Figure 3: Examples of synthetic dataset to verify Theorem
To extract features of the synthetic dataset, which assumes each MNIST image instance, all models use the feature extractor structure described in Table 6 First, mi-Net (5) Attention MIL 2 Additive MIL (9. and Conjunctive MIL [T0] performed Aggregation through basic Instance, Attention, Additive, and Conjunctive-poolleee
operations. respectively. We used the same classifier structure used to perform the pooling operations described in Appendix [A.2] The employed attention mechanism is the gated attention mechanism, which is commonly used in MIL research (2). Second,
Causal MIL (2T). MIREL (38]. Loss-Attention [39], SA-AbMILP 40), and TransMIL [19 performed
additional tuning pooling for performance improvement. We implemented them using the official
code provided by each respective pape Third, for MIREL
38 although the prediction modules
httge:/gtthabb.cc///uugt.///1/1
httpp///gtthi..ccmmmmmmmeeeeeeee Attention Att.ttttiooootttnniinnn
27

---

for the bag and the instances operate separately. the validation is adjusted to fit the nature of MIL. Specifically, the bag-level prediction module is not used, and instead, the pooled instance predictions are used for bag-level evaluation. Fourth, for Conjunctive MII. [0] and Trans [19], while each
original paper utilizes positional information that affects the predictions, this factor is excluded from our experiments, as it does not influence the outcomes in our setup.
The operational processes and theoretical validation for Causal MIL 211), MIREL 38 Loss-
Attention [9]] SA-AbMILP 40 and TransMIL 19] are performed in Appendix
Table 6: The architecture of the instance feature extractor.
Layer
Type
conv(3.1,1)322+ ReLU
2
maxpool(2,2)
conv(3.1,1)-64 + ReLU
m2xpool(2,2)
5
flatten
fc-128 + ReLU
The hyperparameter settings for the models used in the experiments are shown Table
Table 7: Hyper parameter setting.
Optimizer
Learning rate
Cost funtion
Epochs
Adam
0.0001
NLL loss function
20
Since the labels for the bags are multi-class, we used macro-F1 score (Macro-F1), micro-F1 score (Micro-Fl), and weighted-F1 score measure multi-class classification performance. To ensure generalized results, each algorithm was trained ten times with different initializations, and the average performance was measured. All experiments conducted in this study performed an Intel(R) Xeon(R) Silver 4210R 40 Core CPU @ 2.40 GHz, 32GB RAM, and NVIDIA RTX A5000.
D.2 Experimental Validation of Theorems 8 and
Theorem g and Theorem demonstrate that Attention MIL (2] and Additive MIL (9] which perform attention multiplication on instance features, are not capable of learning at the instance level, whereas Conjunctive MIL capable of instance-level learning.
To empirically validate this, it is necessary to compare the prediction performance of a Deep MIL model on bags with its performance instances. Therefore. experiments should be conducted on datasets that have labels for both bags and instances. In this study, we use the labeling criteria for the synthetic dataset explained in Appendix D.I
The feature extractor and The performance measurement method also adhered to the approach specified in Appendix D.I However, due to the nature of MIL, which involves learning whether specific instance is positive for each class, we also calculated the average AUROC performance for each class and measured the overall AUROC.
settings followed the model structure used Appendix D.
To analyze the impact of the attention mechanism, we adjusted the temperature parameter (T) used in the attention operations to three values: 0.5, 1, and 2. This process was repeated ten times to calculate the average performance. The average performance of each algorithm for the bag and the average performance difference between the bag and instances are discussed Section 4.4.3 The performance analysis based the adjustment of is detailed in Appendix E.1
28

---

Label: 0
0
0
3
9
3
9
6
9
Z
2
Label: 1
0
0
0
0
1
/
4
5
g
9
le
6
3
Label: 2
0
0
2
0
0
0
0
0
4
2
4
/
A
4
3
Label: 3
0
3
4
8
4
8
5
7
Figure Example synthetic dataset to verify Theorem 8
D.3 Experimental Validation of Theorems 10 and
Theorem 10 and Theorem demonstrate that using an RNN layer to capture positional dependencies
or performing positional encoding can act factors that hinder the learnability of instances.
To experimentally validate this, we use the WebTraffic dataset [0] which provides label information for each time point in time-series sliding window data. Both the model structure and hyperparameters set identical those in Early al. [10), and models are configured based on the extent which features with positional encoding and RNN are used, as following four model
1. A model that does not use features with positional encoding and RNN for instance prediction and attention operations (Default)
2. A model that uses features with positional encoding and RNN for both instance prediction and attention operations (All)
3. A model that uses features with positional encoding and RNN only for attention operations (Att)
4. A model that uses features with positional encoding and RNN only for instance prediction operations (Predict)
All experiments conducted in this study performed Intel(R) Xeon(R) Silver 4210R 40 Core CPU @ 2.40 GHz, 32GB RAM, and NVIDIA RTX A5000.
To evaluate the instance-level prediction performance of deep MIL models, we used the normalized discounted cumulative gain (NDCG@m) and the area under the perturbation curve with random orderings (AOPCR) metrics, as employed by Early et al. 10]. To reliably measure the performance of each model, we repeated the evaluation 10 times and calculated the average performance. AOPCR assesses the interpretability of time-series data by measuring the decrease in model predictions based
29

---

on the importance of time points. Starting from the most important time point, the time series is rearranged in order of importance, AOPC then calculated by removing instances one by one from the most important time points and evaluating how the predictive performance changes.
1 AOPC(X, O1,c) = t- Σ F.())) - Fo O1.,,)))
Here, the MoRF function removes time points in the given order of importance. Instead of removing each time point individually, time points are grouped into blocks corresponding to 5% of the total time series, and perturbations are applied until 50% of the time series is removed, limiting the number of model calls to maximum of 10. Finally, AOPCR is calculated by comparing the average AOPC value for the given order of importance to the average AOPC value for random orderings to achieve normalization:
T Σ T
AOPCR(X;, Oi.))
(AOCC (xi Oi.)) AOPC(X, ).
Here, T' represents the number of repetitions of random orderings. In this study, T is set to 3 following the settings of Early et al. [10]
NDCG@n is a metric used to evaluate instance predictions by comparing them to the ground truth ordering for a specific class. Instances within bag are classified as supporting instances, neutral instances, or refuting instances based their labels. The ideal prediction order for instances should be supporting instances, neutral instances, and then refuting instances for the given class. NDCG@n is calculated by ranking the instance predictions {øi,.... & for the given class from highest to lowest importance and comparing this order to the ground truth order as follows:
rel(2)
NDCG@n On
TDCG [m
loga (i 1)
Here, IDCG is the ideal discounted cumulative gain, which normalizes the score based the value of n, where n is the number of instances with positive label.
D.4 Experimental Validation of MD-MIL
In this section, we conduct additional experiments in an extended scenario of Video Anomaly Detection (VAD) to demonstrate that the framework proposed in this study assists in designing optimal algorithms for realistic MD-MII scenarios. The traditional VAD problem has been addressed as type of 1D-MIL problem, as shown in Figure (a). where the objective is to detect anomalous snippets based on labels for the entire video. this context, each snippet should reflect temporal dependencies.
Moreover, the conventional VAD problem can be extended as an MD-MIL problem, as depicted in Figure The problem aims to detect both anomalous snippets and anomalous patches within each snippet based on labels for the entire video. this case, the patches that constitute a snippet must not only reflect relationships with other patches within the same snippet but, much like multivariate time series data (33 [54, also account for temporal dependencies with corresponding patches in other snippets. Therefore, the VAD problem in an MD-MII context requires consideration of relationships not only among instances within the same bag but also with instances at the same position across different bags.
To design model that is capable of learning about instances while reflecting relationships under this complex problem setting, the following requirements must be satisfied:
1. The VAD problem in MD-MIL should reflect relationships among complex multi-dimennsonal instances. Therefore, this should be addressed by a learnable MII. method (i.e., Conjunctive-pooling) on Den
XY
30

---

2h
(a) The vidco data structure consisting of 1-(b) The vidco data structure consisting of dimernsional-instanccs...
mulli-diinensional-inttaneee
Figure 5: The video data structure consisting 1-dimensional and multi-dimensional -nntannannininsnnnneeneeeee iinstances (Blue: Negative, Red: Positive) [55].
2. Additional information about relationships between instances, such position encoding, should be used in the attention computation process. This ensures learnability about instances and can improve performance, demonstrated in Section 4.4.3 Based this, attention operations should incorporate this information to reflect temporal relationships with patches at the same position in other snippets for each patch detection.
To validate these requirements, we measure and compare the performance between the following three types of MD-MIL models:
1. None-Attention This model predicts for higher-dimensional bags through Instance-pooling in each dimension. It independently models the relationships between snippets composing a video and patches composing the same snippet.
2. Attention: This model predicts for gigees-dimenioonl Bags by performing Sestjunctive-Poolingg based on attention weights calculated within each dimension (same bag). Through this structure, make predictions reflecting the relationships between snippets composing video and patches composing the same snippet.
3. Cross-Attention: To reflect the temporal dependencies of patches at the same position in different snippet bags, this model computes attention weights based on features of each patch computed through a bidirectional GRU-layer and performs sonjuuctivv-pooling Through this structure, it can make predictions reflecting the relationships between snippets composing video, patches composing the same snippet, and patches at the same position in different snippets.
All models trained using anomaly labels at the video level. The encoder structure for computing instances is identical across models, as shown the Table with differences only in pooling and attention operations.
The hyperparameter settings for the models used in the experiments are presented in the following Table
For this study, utilized the ShanghaiTech dataset 55 56
well-established benchmark dataset
for Video Anomaly Detection (VAD). As illustrated in Figure (b), each snippet was pre-divided into four patches. To extract features from these patches, employed pre-trained NeD-ResNet model 8 This model was used to extract snippet features for each patch, which were then utilized in our experiments.
31

---

Table 8: The architecture of the instance feature extractor in the MD-MIL model.
Layer
Type
fc-1024 + ReLU
LayerNorm(100) (1024)
fc-1024 + ReLU
4
LayerNorm( 1024)
5
fc-1024 + ReLU
LayerNorm
fc-1024 + ReLU
8
LayerNorm(10244
Table 9: Hyper parameter setting.
Optimizer Learning rate
Cost funtion
Epochs
Adam
0.0001
NLL loss function
100
E
Additional Experimental Results
E.1
Experimental Validation of Theorems and 9
The results adjusting the variance of attention by applying T in the softmax operation determine how much attention affects the error between bag prediction performance and instance performance in deep MIL are presented in Table TO While all Attention-pooling MIL models show high performance for bags, they exhibit low learning performance for instances. Theorem[) shows very little error between bag performance and instance performance, with instances sometimes even outperforming bags. However, in the case of Additive-pooling MIL, as T increases and the variance among instances decreases, AUROC between bags and instances decreases. This result suggests that for Additive-pooling MII. to be learnable for instances, the strength of the attention must be weak. In other words, the closer the structure to instance predict-level pooling, the more likely it is to be learnable for instances.
jesjjuncive-poolinng MIL, satisfying
E.2 Experimental Validation of MD-MIL
The experimental results indicate that the Cross-Attention method achieved the best performance, followed by the Attention-drive model, while the foneeAAtenntion-ae driven model showed the least favorable performance. These results demonstrate that attention weights are necessary to capture the relationships between video snippets and patches within the same snippet, and 2) when learning relationships between patches in different snippets (i.e., bags) are required, Cross-Atrention-ddiivn model, which utilizes such information only during attention computation, is desired.
F Interpretation of MIL Algorithms through Our Theoretical Framework
In this section, we demonstrate how the proposed theoretical framework can interpret actual existing MIL algorithms. To further validate our framework's 's capability to assess instance-level learning in MIL algorithms, we extended our analysis beyond the basic pooling techniques discussed earlier. We additionally selected five MIL algorithms that apply additional tuning to the existing pooling methods for performance improvement. These algorithms were chosen to demonstrate how our framework can generalize to MIL approaches that enhance standard pooling operations through additional optimization techniques.
Causal MIL. 21: This algorithm utilizes the bag-level features as external variables to identify independent latent variables directly related to the prediction of cach instance's 's feature. It then
32

---

Table 10: Performance differences for bags vs. instances in the MIL model.
0.5
2
Attention-Pooling
Bag
Macro-F1 0.8115
0.8486
0,8703
Micro-F1
0.8152
0.8497
0.8710
Weighted-FF
0.8163
0.8497
0,8710
AUROC
0.9567
0.9427
0.9555
Instance
Macro-F1
0.2912
0.3316
0.3418
Micro-F1
0.2982
0.3407
0,3519
Weighted-F1
0.2928
0.3368
0.3517
AUROC
0.7173
0.7224
0.7555
Performance differences
Macro-FI
0.5202
0,5170
0,5285
Micro-F1
0.5170
0,5090
0.5191
Weighted-F1
0.5235
0.5128
0,5193
AUROC
0.2394
0.2203
0.2000
Additive-Pooling
Bag
Macro-F1
0.4867
0,4523
0.4938
Micro-F1
0.5894
0,5560
0,5907
Weighted-FI
0.5364
0.4904
0.5367
AUROC
0,9232
0.9133
0.9177
Instance
Macro-F1
0.2265
0.2387
0,2307
Micro-F1
0.2709
0.1636
0,2777
Weighted-Fi
0.2575
0,0775
0,2713
AUROC
0.7666
0.8076
0.8533
Performance differences
Macro-F1
0.2602
0,2136
0,2631
Micro-F1
0.3185
0,3924
0,3129
Weighted-FI
0.2789
0.4130
0.2654
AUROC
0.1567
0.1058
0.0644
Conjunctive-PPolligg Bag
Macro-F1
0.7956
0.7855
0.7937
Micro-F1
0.7973
0.7867
0.7962
Weighted-Fi
0.7999
0.7880
0.7995
AUROC
0.9470
0.9442
0.9476
Instance
Macro-F1
0.6393
0.6422
0.6476
Micro-F1
0.7664
0.7644
0.7702
Weighted-FI
0.7977
0.7954
0.8012
AUROC
0.9503
0.9509
0,9537
Performance differences
Macro-FI
0.1563
0,1433
0.1461
Micro-F1
0.0309
0.0223
0.0260
Weighted-H1
0.0022
-0.0074
-0.0017
AUROC
-0.0033
-0.0067
-0.0061
Table 11: Predicted performance for Snippets (i.e., bags) and patches (i.e., instances) of MD-MIL.
None-Attention
Attention Cross-Attention
Snippet (Bag)
0.87
0.88
0.91
Patch (Instance)
0.85
0.85
0.91
performs instance-pooling based on these latent variables. Since Causal MIL derives predictions using individual instance features and performs instance-pooling based on these values, it can be learnable instances under the space Dind
2. Multi-Instanee Residual Evidential Learning (MIREL) 38 This algorithm is composed of two primary modules: 1) module that predicts bag label using the average feature the instances that constitute the bag and 2) module that performs predictions their features. MIREL calculates the residual between the bag prediction and the instance predictions, which is indirectly used to perform eestance-pooling The instance prediction module of MIREL
individual instances based on
33

---

operates based on the instance features themselves without applying weighted aggregation through additional information. Thus, it can be learnable on bag predictions under the space D Frdd
(a) The loss function of MIREL can be expressed as the sum of loss terms generated by the bag and instance prediction modules:
Lbug =
Ebag (bbag Vbog), Linst = E linstlit, 31)
Lratal = Lagg + XLinsts where À is weighting factor.
Ybag is the prediction made by the bag prediction module; Ybeg is the true label for the bag: Yi is the label predicted by the instance prediction module; y/ is the label inferred for each instance based on Ubag and residual evidence.
(b) The risks for the bag, instance, and total can be defined as follows:
Rbag
(-DD Klag (Wbag: Ybag
Rinst:
E E(x,Y) D Xinas;" x Ikinse (Ūi, Wi)]
Riotal
Rbag
> EE Rinst:
(c) Since our theoretical framework evaluates instance learnability under Assumption we can express this as follows:
inf Reotal = inf Roag + A inf E Rinst,
Roag is learnable under XY. Therefore, infRgи Rogy inf Rhag holds.
inf Ei= Rsnet, learnable with respect to the instance labels generated by the bag predic-
tion module. Therefore, infNEH BD Xinf D Rinst,
a constant, inf R inf E Rinsts Therefore, Condition holds.
Therefore, the algorithm is learnable for instances.
3. Loss-based Attention for Deep Multiple Instance Learning (lsssAAttnttion) 39 This algorithm directly connects the attention mechanism with the loss function to simultaneously learn instance weights, instance predictions, and bag predictions. Specifically, Instance weights are calculated based on the loss function. The parameters of the fully connected layer for bag prediction are shared with the instance weight calculation. A regularization term consisting of instance weights and cross-entropy functions is introduced to improve instance recall. consistent cost is added to smooth the learning process. Through this approach, Loss-Attention can more effectively learn the importance of instances and improve bag classification performance compared to existing aitention-based MIL methods.
Loss-Attention [39] aims to simultancously optimize the hypothesis spaces for both instances and bags by sharing parameters between them during the learning process. However, in DGen according to Condition g while the Loss-Attention algorithm is learnable for bags, it is not learnable for instances.
This algorithm enhances the reflection of relationships between instances compared to traditional Attention MIL (2) by employing self-attention mechanism compute instance features, which are then used for attention-poon -pooling. Since SA-AbMILP uses transformed instance features that reflect relationships with other instances via self-attention for prediction and proolignnppooligg does not satisfy Condition TO and is not learnable for instances.
Self-Attention Attention-based MIL Pooling (SA-ABMILP) 40):
5. Transformer-basee MIL (TransMIL) 19
This algorithm employs Transformer module to better capture the relationships between instances. The Transformer module extracts a cls token feature based on the information of instances that reflect their relationships with other instances. TransMIL performs prediction on the bag using the cls token feature, a form of attention-poolingg Since TransMIL uses positional encoding features, its learnability for instances cannot be guaranteed by Theorem IT Moreover, attention-pooling does not satisfy Condition 10 and is not learnable for instances.
G Limitations and Future works
According to the MII. survey by Carbonneau et al.
57 recent major issues in MIL. have been
defined label ambiguity [58] label noise [59] 60, complex bag composition 61 62 63), and
handling non-ii.d. data 664 65 This study has only addressed the learnability of instances and did
34

---

not cover the applicability of these issues. In future work, we plan to utilize the theoretical framework developed in this study to devise countermeasures for issues such as label ambiguity and label noise, aiming to enhance the performance of MII. algorithms through theoretical research. Furthermore, we will seek solutions for problems like complex bag composition and handling non-i.i.d. data based on the theoretical framework of MII. algorithms. Additionally, noting that existing MD-MIL. algorithms [6 20] have extended non-learnable MIL algorithms to multi-dimennsonal cases, we will devise new MD-MIL methodologies based on the learnable MIL algorithms by our proposed theoretical framework.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main contributions of the paper are presented in the abstract and introduc-
tion.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have shown the Limitation and Future work in Appendix G
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: The Theorems and Lemmas proposed in the paper are derived from the Definitions and Assumptions defined through Notation. Detailed proofs for each Theorem are provided in the Appendix.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: this study, to validate several final Theorems derived from the initial Theo- rems, created appropriate experimental environments for each Theorem and conducted experiments. The results from these experiments provided empirical validation for the Theorems.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Ye]]
Justification: In this study, experiments were conducted using the open datasets MNIST and the WebTraffic dataset [TO]. For MNIST, since was used to create synthetic datasets tailored to the experimental environment, model training. For the WebTraffic dataset [10), as experiments were conducted by swapping models in the code published by Early et al. [10], submit the code related to the model structures.
submit the code for data preprocessing and
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We have specified the experimental setting and test details in Appendix D
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [No]
36

---

Justification: Although we did not include error bars, we ensured the reliability of the exper- iments by repeating each experiment 10 times and taking the average of the performance results. This approach was taken to enhance the statistical reliability of our results.
8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: We specified the sentence 'All experiments conducted in this study were performed on Intel(R) Xeon(R) Silver 4210R 40 Core CPU @ 2.40 GHz, 32GB RAM, and NVIDIA RTX A5000. in the section describing the experimental settings.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification: Our research proposes conditions that must be theoretically guaranteed for the MIL. model be learnable on instances. This study poses no ethical issues; rather, expected to ensure the reliability of MII. algorithms.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Our research proposes conditions that must be theoretically guaranteed for the MIL model to be learnable on instances, Since MIL research is utilized in fields requiring reliable predictions, such pathological image diagnosis and video anomaly detection, satisfying these conditions is essential. In this regard, our research has a positive societal impact.
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Our research proposes theoretical framework to evaluate whether MIL algorithms are learnable on instances, which is not associated with such risks.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: For experiments extending existing research, we have cited the respective studies and provided the GitHub link in the section describing the experimental settings.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We provide the code for dataset preprocessing, model training, and the model itself as additional submissions.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
37

---

Answer: [NA]
Justification: This study did not involve crowdsoureing.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This study did not involve crowdsourcing research with human subjects.
38


Reviews:
[{"review_id": "gfQ86YYQO7", "reviewer": "Reviewer_2msW", "summary": "The paper addresses a critical gap in Multiple Instance Learning research by proposing a theoretical framework to evaluate instance-level learnability of MIL algorithms. Utilizing PAC learning theory, the authors derive conditions under which Deep MIL algorithms can achieve instance-level learnability. The framework is then applied to evaluate the learnability of several existing Deep MIL algorithms, and the findings are validated through empirical studies.", "questions": "1. How do the proposed theoretical conditions translate to improvements in practical MIL applications? Can you provide more detailed real-world examples?\n2. How robust are the theoretical conditions under different assumptions, such as dependent instances within bags?\n3. Can the framework be extended to other types of machine learning algorithms beyond Deep MIL?", "limitations": "NA", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a novel theoretical framework to assess instance-level learnability in MIL, filling a significant gap in current research.\n2. The authors provide clear and precise definitions of MIL domain spaces, hypothesis spaces, and risk, which aids in understanding the theoretical constructs.\n3. The theoretical conditions and their proofs are well-articulated and grounded in PAC learning theory, providing a strong foundation for the proposed framework.\n4. The paper evaluates a range of Deep MIL algorithms against the proposed theoretical conditions, offering a broad validation of the framework.\n5. The study addresses practical concerns in domains requiring expert labeling, such as pathology, highlighting the potential impact of instance-level learnable MIL algorithms.", "weaknesses": "1. The paper’s theoretical sections are dense and may be challenging for readers not well-versed in PAC learning theory.\n2. The framework relies on several assumptions, such as the independence of instances in certain conditions, which may not always hold in real-world applications.\n3. Details on experimental setups and reproducibility of empirical studies are sparse, which could hinder replication efforts.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition and feedback on our work. We've integrated your suggestions to enhance our manuscript. For more information, see Global Response. We are addressing your specific comments as follows:\n\n**(W1)** Complexity of the Theoretical Framework\n\n- To facilitate understanding of the proposed theoretical framework, we will add a summary figure and explanation of the relationships between the theorems to the paper. This figure, shown as Figure A in the Global Rebuttal PDF, will illustrate how the theorems are derived and their implications.\n- Figure A explains which theorems are derived from others and their outcomes, particularly whether certain pooling methods are learnable at the instance level. This should help readers unfamiliar with PAC learning theory to understand the goals and theoretical flow of our paper.\n\n**(W2)** Applicability of the Theoretical Framework to Real-World Applications\n\n- We addressed the learnability of MIL algorithms in independent scenarios because many studies assume independence when implementing MIL algorithms. Most studies using instance-pooling require instances to be independent.\n- To assess the learnability of algorithms in broader scenarios, we defined the General Bag Domain Space, which includes both independent and dependent bag domain spaces. This ensures that our framework is valid under Assumption 1, even when relationships between instances exist.\n\n**(W3)** Limited Empirical Validation\n\n- The experiments in our paper are reproducible, with code made available and a detailed readme file explaining the experimental setup and parameters. Appendix D provides extensive details on the experimental environment, hyperparameters, and network structures to facilitate replication.\n- Additionally, reflecting reviewers' suggestions for more empirical validation with recent Deep MIL algorithms, we conducted further experiments detailed in item 1 of the Global Rebuttal, shown in Tables A and B. These results will be added to the paper, demonstrating that our theoretical framework applies to all Deep MIL algorithms, not just representative pooling methods, and confirming its empirical validity.\n\n**(Q1)** Practical Applications of the Framework\n\n- Our proposed framework offers the advantage of theoretically evaluating whether MIL algorithms are learnable at the instance level. The Global Rebuttal PDF's Figure A clearly demonstrates the theoretical learnability of individual pooling methods, and we have empirically validated these theories through experiments on specific pooling algorithms, as shown in Global Rebuttal item 1.\n    - For example, in the medical domain, MIL algorithms have been adopted to address labeling issues. These algorithms often use attention pooling to reflect current trends. However, our study shows that attention pooling is not learnable at the instance level, indicating it is unsuitable for medical applications where accurate instance-level predictions are crucial for patient diagnosis.\n    - Our study identifies two pooling methods that are learnable at the instance level for various MIL domain spaces. This can help select appropriate MIL algorithms for specific environments.\n- Additionally, our framework can be applied to individual techniques aimed at improving MIL performance.\n    - In Section 4.4.3, we applied our framework to positional encoding, commonly used in MIL research, showing in Table 4 that positional information should be used only in attention computation to improve instance-level prediction performance.\n    - As shown in Table C of the Global Rebuttal, our framework also theoretically guarantees the best performance for models that use relationships between instances from different bags, such as in MD-MIL scenarios.\n\n**(Q2)** Theoretical Robustness of the Framework in the General Bag Domain Space\n\n- We proposed a framework under Assumption 1, which assumes MIL algorithms are learnable at the bag level, to facilitate the theoretical evaluation of instance-level learnability. Under this assumption, our framework includes both the Independent bag domain space ($D_{XY}^{Ind}$) and Dependent bag domain space ($D_{XY}^{Dep}$) in the General Bag Domain Space ($D_{XY}^{Gen} = D_{XY}^{Ind} \\cup D_{XY}^{Dep}$) and proposes Theorem 3 to determine instance-level learnability. Based on Theorem 3, we derived Theorems 5, 8, 9, 10, and 11.\n- Specifically, Theorem 3 is proven using the Azuma-Hoeffding inequality [1], which applies to dependent random variables, demonstrating the robustness of our theoretical conditions. Empirical validation of our theorems confirms the robustness of the framework in $D_{XY}^{Gen}$.\n\n**(Q3)** Extending the Framework to Other Types of Machine Learning Algorithms\n\n- Our framework can be applied to machine learning-based MIL algorithms, provided they satisfy Assumption 1.\n    - For example, the well-known machine learning-based MIL algorithm MI-SVM [2] performs individual instance predictions and then predicts the bag based on these results, satisfying Condition 4 and being learnable at the instance level.\n- Recent MIL research focuses more on Deep MIL than on machine learning-based methods because deep networks can better extract important features from instances, achieving higher performance [2]. Thus, we refer to our framework as a framework for Deep MIL.\n\n**Reference:** \n\n[1] Pelekis et al., Hoeffding’s inequality for sums of dependent random variables. *Mediterranean Journal of Mathematics*, 2017\n\n[2] Andrews et al., Support vector machines for multiple-instance learning. Neurips, 2002", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wzTVQdO4kV", "reviewer": "Reviewer_dSpL", "summary": "The main contributions of the paper are theoretical:\n- Proof of the fact that MIL algorithms that are not learnable for bags do not guarantee learnability for instances.\n- Using PAC learning theory (under some assumptions) learnability conditions are derived. These conditions are sufficient and necessary.\n- Basic experiments are carried out to support the theoretical findings empirically.\n\nThe most important results of the paper are theorems 1, 3, 5, 7, 10, 11.", "questions": "- The assumptions (referred to as conditions) 4, 6, 7 are crucial for the theorem proofs in the paper. Are these conditions assumed to be true? Or are they proven to be true somewhere? Is there a way to check if these conditions are true for a given model / dataset practically? \n\n- The framework analyzes independently distributed instances within a bag $\\mathcal{D}^{\\text{Ind}}_{XY}$  as well as cases where instances within the same bag are statistically dependent. However, in many cases it is important to model the relation between different bags (or instances inside different bags). For example, thinking of an image as a set of bags where each bag (patch of pixels) is a set of feature instances (pixels), we might want to learn relationships between nearby pixels that fall in different bags. Do the authors have any insight on if their analysis could be expanded in this direction in future work?", "limitations": "The paper discusses its limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The strongest part of the paper is the theoretical framework and mathematical setup resulting in some key results about PAC learnability at the instance level for various MIL algorithms.\n- Explicit results connecting bag learnability with instance learnability.\n- The paper derives theoretical guarantees about which kinds of pooling maintain PAC learnability for instances.\n- I think the paper could have broader impact in the development of instance level MIL methods.\n- The paper despite being quite dense with theorems and definitions flows reasonably well and is understandable when read. I checked the proofs and I can follow the arguments line by line. I appreciate that the authors take the time to set up clear notation and an proper mathematical formulation of their problem definition.", "weaknesses": "Despite the strengths of the paper there are some weaknesses.\n- From a motivation standpoint, it has been the case for a while now that the strongest methods in MIL are attention pooling based and operate at the bag/embedding level, not the individual instance level. How do the results presented in this paper affect methods such as [1]? Why should we care about instance based methods in 2024? Explainability or interpretability motivations? The paper should make the case for why these results are important given the current state-of-the-art in the field.\n- The methodology is well supported by the proofs. However, the empirical evaluation is not very thorough. It would be nice to see if the methodology has practical implications in standard MIL benchmarks used in new methods. Datasets such as the ones used in [1] are basically standard for MIL research. If the authors want to go one step further they could incorporate more elaborate testing frameworks too [2]. More experiments would help to convince me that the theoretical results have grounding in empirical findings and encourage me to raise my score.\n\nRefrences: \n\n[1] Attention-based Deep Multiple Instance Learning, Maximilian Ilse, Jakub M. Tomczak, Max Welling, ICML (2017).\n[2] Reproducibility in multiple instance learning: a case for algorithmic unit tests., Raff, Edward, and James Holt., NeruIPS (2024).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition and feedback on our work. We've integrated your suggestions to enhance our manuscript. For more information, see the Global Rebuttal. We are addressing your specific comments as follows:\n\n**(W1)** \n- **Importance of Instance Pooling:**\n    - Instance-Pooling is a fundamental method still used in recent studies [2-4].\n        - The Independent bag domain space assumes instance independence, common in medical domains and video anomaly detection. In such cases, Instance-Pooling is effective due to lower computational and memory requirements compared to other pooling methods.\n        - For example, Causal MIL (Neurips, 2022) improves prediction by identifying influential features while assuming instance independence within a bag on $D_{XY}^{Ind}$.\n- **Learnability of Attention MIL[1]:**\n    - Our paper presents Theorem 8 to evaluate the learnability of instance-based attention pooling, a popular MIL method. According to Theorem 8, if the hypothesis space for bags exceeds that of instances, Attention MIL (Pooling) is not learnable at the instance level. This conclusion applies to methods like [1], TransMIL [6], SA-AbMIL [7], and TimeMIL [8].\n    - Our framework also evaluates other attention-based methods like Additive MIL and Conjunctive MIL. We will include Figure A in the Global Rebuttal PDF for better understanding.\n\n**(W2)** \n- Our study proposes a framework to overcome the limitation of previous studies focusing only on experiments without theoretical validation of instance learnability. We prioritized empirical verification of pooling methods theories rather than specific algorithm results.\n    - The benchmark from [1], mentioned by the reviewer, is based on real datasets where generalization is not assumed, making theoretical results difficult to observe. Various algorithms have already been tested on these datasets.\n    - The benchmark from [5] confirms reproducibility of bags composed of vector datasets sampled from a normal distribution on the Independent bag domain space, evaluating MIL algorithm adherence to MIL assumptions. Our study differs by proposing a framework for evaluating instance learnability and defining the General Bag Domain space to assess learnability in environments with instance relationships.\n    - The synthetic dataset using MNIST data, similar to [2], is widely used for specific cases. It accurately verifies the theory without performance variations due to encoder differences, which is why we used it.\n- Reflecting the reviewers' suggestion for more empirical evaluations, we conducted verifications on various latest Deep MIL algorithms in the Global Rebuttal. The results, shown in Tables A and B, align with our theoretical results and will be included in the revised paper.\n\n**(Q1)** \n- For Conditions 4 and 7, we have proven they are necessary and sufficient based on Definition 6 in our paper, as shown in Appendix C.2 and C.3. Conditions 4 and 7 hold true for any model as long as Assumption 1 is satisfied. Specifically, experimental validation of Theorems 8-11, derived from Theorem 3, shows that Condition 7 is necessary and sufficient for learnability at the instance level on $D_{XY}^{Gen}$.\n- Condition 6 is assumed to be true in our paper. When relationships exist between instances, their contributions to the bag's domain space vary. The total contribution sum is 1. For example, in the **Experimental Validation of Theorems 5, 8, and 9**, if the digits 3 and 5 appear together in a bag, they are positive, but individually they are not. Thus, contributions change based on relationships.\n\n**(Q2)** \n- The scenario you mentioned relates to Multi-Dimensional MIL (MD-MIL). For example, in video data, a video is composed of snippets, and each snippet consists of image patches. For video anomaly detection, information from a snippet’s patches may require information from previous snippets’ patches.\n- Our study clarified that to make predictions at the instance level using relationships between instances, Condition 10 must not be violated, as stated in Theorem 8. External information should not be used in the prediction stage itself but only in the calculation of weights, such as attention weights.\n- We conducted additional experiments on such cases, as detailed in item 2 of the Global Rebuttal. The results confirmed that theoretically learnable algorithms achieved the best performance, demonstrating the potential for extending our theoretical framework to various domains. These findings will be included in the revised paper.\n\n**References:**\n\n[1] Ilse et al., Attention-based deep multiple instance learning. PMLR., 2018.\n\n[2] Zhang et al., Multi-instance causal representation learning for instance label prediction and out-of-distribution generalization. Neurips, 2022.\n\n[3] Liu et al., Weakly-Supervised Residual Evidential Learning for Multi-Instance Uncertainty Estimation. ICML, 2024.\n\n[4] Wang et al., Rethinking Multiple Instance Learning for Whole Slide Image Classification: A Bag-Level Classifier is a Good Instance-Level Teacher. IEEE Transaction on Medical Imaging, 2024.\n\n[5] Raff et al., Reproducibility in multiple instance learning: a case for algorithmic unit tests., Neurips, 2024.\n\n[6] Shao et al., Transmil: Transformer based correlated multiple instance learning for whole slide image classification. Neurips, 2021.\n\n[7] Rymarczyk et al., Kernel self-attention in deep multiple instance learning. arXiv, 2020.\n\n[8] Chen et al., TimeMIL: Advancing Multivariate Time Series Classification via a Time-aware Multiple Instance Learning. ICML, 2024", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "r7f5OTl5wd", "reviewer": "Reviewer_W4rs", "summary": "The paper provides theoretical considerations regarding Multiple Instance Learning.", "questions": "Is it possible to improve presentation of the paper?", "limitations": "Discussed.", "rating": 5, "confidence": 4, "soundness": 4, "presentation": 1, "contribution": 4, "strengths": "Theoretical consideration supported by the experimental results.", "weaknesses": "There are no images depicting the intuition behind those definitions and theorems. \n\nPaper is extremely hard to follow because it is not giving the intuition and implication for practitioners.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition and feedback on our work. We've integrated your suggestions to enhance our manuscript. For more information, see the Global Response. We are addressing your specific comments as follows:\n\n**(W1, 2, Q1)** Improving the Presentation of the Paper\n\n- To address the feedback that the paper is difficult to understand due to its focus on theoretical content and lack of figures, we will add example figures illustrating the problems addressed in our study. Additionally, we will include Figure A to summarize the relationships between the theorems.\n    - **Attached PDF Figure A:** Figure A summarizes the relationships between all the theorems that constitute the theoretical framework of our paper. It not only shows which theorems are derived from others but also helps to identify which MIL pooling methods or algorithms are learnable or not at the instance level. Figure A will help readers understand the theoretical framework by showing the connections and outcomes between the theorems.\n- Furthermore, since the paper focuses primarily on theoretical validation, we have significantly strengthened the empirical validation to show how the framework can be applied in practical environments, as detailed in items 1 and 2 of the Global Rebuttal. This will help readers understand the real-world impact of our framework.\n- Finally, we will enhance the presentation by thoroughly reviewing and correcting grammatical errors, table captions, typos, and other issues identified by reviewers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3gSIRbooU5", "reviewer": "Reviewer_bVsY", "summary": "This paper mainly studies the instance-level learnability of common weakly-supervised MIL algorithms. With the PAC theoretical framework, it shows the conditions for MIL algorithms to be learnable for instances. Two general cases of instance distribution, IID instances and non-IID instances, are discussed and analyzed in the proposed theoretical framework. In addition, the proposed theoretical framework covers a wide range of MIL algorithms, which could provide valuable insights for many MIL-based applications in the real-world.", "questions": "See my comments above.", "limitations": "Limitations have been indicated by the authors and written in the paper. There is no additional limitation that needs to be explicitly highlighted here.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper is overall well-written and easy to follow. All key definitions and theorems’ implications are given and explained clearly. \n- This paper studies an interesting and valuable problem, *i.e.*, instance-level learnability in weakly-supervised MIL. This problem is still in the stage of empirical exploration, so a formal study from a theoretical perspective, which this work presents, is needed and could be valuable to the community of deep MIL. \n- The proposed theoretical framework covers a wide range of MIL algorithms, which could provide valuable insights for many MIL-based applications in the real-world.", "weaknesses": "- In Definition 6, the sufficient condition for instance-level PCA learnability, i.e., Condition 2, is given. However, the authors do not prove that Condition 2 is necessary. From my understanding, the instance-level PCA learnability cannot directly deduce Condition 2, as it (Eq. 7) contains an additional bag-level constraint. \n- The authors mainly study one type of MIL algorithm in which pooling (instance embedding level or instance score level) is only performed once. In fact, there is another type of MIL algorithm with multiple pooling operations [1, 2, 3]. Most of these algorithms aim at making instance-level predictions and could be viewed as a combination of the classical algorithms discussed in the paper. The authors are encouraged to discuss them and indicate whether these MIL algorithms could also be incorporated into the proposed theoretical framework. \n\nMinor issues:\n- Table 3: Please consider using a clearer way to present the performance of instance-level prediction and bag-level prediction, as well as their difference. \n- To meet the basic publication requirements of NeurlPS, the authors are encouraged to carefully and repeatedly check those easy-to-avoid errors in their paper, *e.g.*, line 346 - “pr,edication” and “Additve” on page 33. \n\nReferences: \n\n[1] Shi et al., Loss-based attention for deep multiple instance learning. AAAI, 2020.\n\n[2] Liu et al., Weakly-Supervised Residual Evidential Learning for Multi-Instance Uncertainty Estimation. ICML, 2024.\n\n[3] Wang et al., Rethinking Multiple Instance Learning for Whole Slide Image Classification: A Bag-Level Classifier is a Good Instance-Level Teacher. IEEE Transaction on Medical Imaging, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your recognition and feedback on our work. We've integrated your suggestions to enhance our manuscript. For more information, see Global Response. We are addressing your specific comments as follows:\n\n**(W1)** Reason for Condition 2 Being a Necessary Condition for Instance-Level Learnability\n\n- According to Theorem 1, if a model is not learnable at the bag level, it cannot be learnable at the instance level. Therefore, for a model to be learnable at the instance level, learnability at the bag level must be ensured, making Condition 2 a necessary condition for instance-level learnability. In response to the reviewer's comment, we will add a clear explanation in Definition 6 to improve clarity.\n\n**(W2)** Applicability of the Framework to Various Latest Deep MIL Algorithms\n\n- Our study aims to propose a theoretical framework that serves as a baseline for MIL. Therefore, we did not discuss all methods that use various strategies for pooling to enhance performance. However, Theorems 1, 2, and 3, along with Theorems 4-12, which verify the learnability of different pooling methods at the instance level, can be applied to most MIL algorithms. Specifically, for the special MIL algorithms mentioned by the reviewer [1, 2, 3], we can determine instance-level learnability as follows:\n    - **[1]**: The MIL algorithm proposed in [1] uses an attention mechanism to derive features for the bag from the features of each instance. It then makes predictions at the bag level and uses attention to make instance-level predictions. Thus, because the algorithm in [1] does not satisfy Condition 10 of Theorem 8, it is not learnable at the instance level.\n    - **[2, 3]**: The methodologies in [2, 3] obtain predictions for instances based on their individual features and then use these features to make bag-level predictions through an independent classifier. The predictions for instances are trained to approximate the bag-level predictions, making these algorithms a type of instance-pooling. Since the optimal hypothesis space for individual instances approximates the optimal hypothesis space for bags, these MIL algorithms are learnable at the instance level according to Theorem 6.\n- As mentioned in item 1 of the Global Rebuttal, we have added detailed analyses and indications for various latest Deep MIL algorithms and will include these in the paper. Furthermore, we will strengthen the robustness of our theory through empirical validation of recent MIL algorithms, as shown in Tables A and B of the attached PDF.\n\n**(Minor Issues)**\n\n- To make the experimental results in Table 3 clearer, we will revise the table to separately show the Macro-F1 Score and AUROC results, and display the bag-level and instance-level prediction results together, as shown in Table B of the attached PDF. This should provide clearer performance metrics.\n- We have reviewed and corrected the mentioned typographical errors and will reflect these corrections in the paper.\n\n**References:**\n\n[1] Shi et al., Loss-based attention for deep multiple instance learning. AAAI, 2020.\n\n[2] Liu et al., Weakly-Supervised Residual Evidential Learning for Multi-Instance Uncertainty Estimation. ICML, 2024.\n\n[3] Wang et al., Rethinking Multiple Instance Learning for Whole Slide Image Classification: A Bag-Level Classifier is a Good Instance-Level Teacher. IEEE Transaction on Medical Imaging, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3LnlWvtTIM", "reviewer": "Reviewer_K1fQ", "summary": "This paper aims to discuss the theoretical learnability of multi-instance learning. It first gives the necessary conditions for bag-level learnability and instance-level learnability. Then it discusses how the results can be used to verify the learnability of existing MIL algorithms. Finally, some empirical experiments are adopted to validate the theoretical findings.", "questions": "1. In Section A.2, the attention pooling is different from Ilse et al., 2018, which is the attention-based MIL that most follow-up works are based on. Instead, additive pooling is actually the attention mechanism in Ilse et al., 2018. Why?\n\n2. I am not very clear about the multi-dimension MIL discussed briefly in 4.3.2. Can you explain this sentence \"For instance, in video data, each frame is composed of patches in multi-dimensional structures for each frame dimension.\"?\n\n3. In Table 2, the title is validation of theorem 4, but in the text it says validating theorem 5?\n\n4. Also in Table 2, do you have results for more recently proposed instance pooling approach, such as [21]? This also applies to the results in Table 3.", "limitations": "Some limitations are discussed in the appendix. However, it seems to contain some grammatical mistakes which hinder understanding. For example, what is the meaning of this sentence: \"to address the problem that current MD-MIL algorithms [6, 20] extend non-learnable algorithms for instances to multidimensional cases\"?", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "This paper discusses the theoretical aspects of multi-instance learning (MIL). As MIL has attracted increased interest for applications in medical image analysis and time series analysis, it is nice to have some time to pause the development of heuristic algorithms and think about the theoretical foundations.", "weaknesses": "1. Many statements are not rigorous and this significantly reduces readability. For example, in Condition 4 the text refers to that the optimal hypothesis for independent instance domain must equal the sum of hypotheses for the individual instances. However, the formula is about the risks and they are not equivalent. In theorem 4, it just says \"the MIL algorithm\" without specifying which algorithm or the defining characteristics of the algorithm, which is not rigorous.\n\n2. For the general bag domain discussed in the paper,  it is not the multi-instance bags that allow dependency among instances as commonly discussed and adopted by previous literature. According to the paper, this is essentially a weighted sum of the instances. It is better to claim this as such, instead of claiming it as a \"general\" bag domain, which it is not.\n\n3. The categorization of pooling methods, as discussed in the appendix, is not consistent with how they are used in the referenced paper. See questions for details.\n\n4. The empirical validation is somewhat lacking. Although this is mainly a theoretical discussion, I don't think the empirical are well designed to support the theoretical claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We will address their feedback in the following:\n\n**(W1)** \n- **Condition 4**: The interpretation provided in Condition 4 aligns with PAC Learning theory. Specifically, $\\inf R$ denotes the infimum of the risk within the given hypothesis space, representing the optimal hypothesis's risk. Thus, Eq. (9) refers to the risk of the optimal hypothesis concerning $D^{Ind}_{XY}$, consistent with PAC learning theory as seen in previous works [1, 2].\n- **Theorem 4**: All theorems in this paper, including Theorem 4, are proven under Assumption 1, which states that any MIL algorithm must be learnable at the instance level. Consequently, Theorem 4 applies to all MIL algorithms satisfying Assumption 1.\n\n**(W2)** \n- Many previous studies assume all instances are independent. However, recent studies such as [3-6] consider relationships between instances, improving prediction performance. These relationships are common in Deep MIL, particularly in practical environments like images, natural language, and time series. Therefore, our study treats the Independent bag domain space $D_{XY}^{Ind}$ as a special case and uses the term ‘General’ to define a space including $D_{XY}^{Ind}$.\n- To reduce misunderstandings, we propose defining the Dependent Bag Domain Space $D_{XY}^{Dep}$, which includes relationships between instances, and defining the General Bag Domain Space as $D_{XY}^{Gen} = D_{XY}^{Ind} \\cup D_{XY}^{Dep}$.\n\n**(W4)** \n- To enhance empirical support for our theoretical framework, we added comparisons between theoretical applications and empirical results for various Deep MIL algorithms. The additional experimental results are presented in Tables A and B of the Global Rebuttal. Please refer to item 1 in the Global Rebuttal for details.\n- Additionally, we conducted experiments assuming an MD-MIL (Multi-Dimensional Multiple Instance Learning) problem. The results, shown in Table C and item 2 of the Global Rebuttal, demonstrate that using information from instances in other bags during the computation of attention weights yields effective learning outcomes. This suggests our framework can guide future MIL research.\n\n**(Q1)** \n- According to Section 2.4 of Ilse et al. (2018) [7], attention pooling involves computing attention weights for each instance, multiplying these by instance features, summing the weighted features to obtain a bag-level feature, and then using this for bag classification. In contrast, Javed et al. (2022) [8] describe additive pooling, where predictions are made based on each instance's weighted features, and these individual predictions are summed for a bag-level prediction.\n- Our paper represents attention pooling as averaging the weighted features (Line 651), while additive pooling is represented by summing individual predictions (Line 655). Although our attention pooling formula includes a factor of $\\frac{1}{N}$, this does not fundamentally change the operation. To prevent misunderstanding, we will remove this factor to align it exactly with [7].\n\n**(Q2)** \n\n- The sentence provides an example to understand Multi-Dimensional MIL (MD-MIL). MD-MIL extends the traditional MIL problem to make predictions for bags-of-bags, using the outer bag's label to infer inner bags and instances.\n- For example, in video anomaly detection (VAD), the goal is to detect the exact frame with an anomaly based on the video label. By interpreting VAD as an MD-MIL problem, each frame can be considered a bag of image patches, and the video as a bag-of-bags.\n- We conducted experiments on such cases, as detailed in item 3 of the Global Rebuttal. Table C shows that MD-MIL algorithms satisfying our framework's theoretical conditions achieved the best performance.\n\n**(Q3)** \n\n- You are correct, the title should be \"Validation of Theorem 5.\" We have reviewed all similar instances and will correct this error in the final paper version.\n\n**(Q4)** \n\n- The results for the requested instance-pooling algorithm [21] are included in Table A of the Global Rebuttal PDF. These results show that other recent instance-pooling algorithms are also not learnable on $D_{XY}^{Gen}$ as they are on $D_{XY}^{Ind}$.\n- Applying these results to Table 3, we found that if an algorithm is not learnable for bags, it is also not learnable for instances, as confirmed by our experimental results in line with Theorem 1.\n\n**(Limitation 1)** \n\n- The sentence explains that current MD-MIL research adopts pooling methods that are not learnable for instances according to our theoretical framework. Specifically, embedding-pooling and attention-pooling methods used in [9] and [10] are not learnable for instances, making the MD-MIL algorithms using these methods also unlearnable.\n- We will revise and clarify these points to ensure they accurately reflect the limitations and are grammatically correct.\n\n**References**\n\n[1] Mohri et al., *Foundations of Machine Learning*, MIT Press, 2018.\n\n[2] Fang et al., \"Is out-of-distribution detection learnable?\", *NeurIPS*, 2022.\n\n[3] Angelidis et al., \"Multiple instance learning networks for fine-grained sentiment analysis\", *TACL*, 2018.\n\n[4] Shao et al., \"TransMIL: Transformer based correlated multiple instance learning for whole slide image classification\", *NeurIPS*, 2021.\n\n[5] Early et al., \"Inherently interpretable time series classification via multiple instance learning\", *ICLR*, 2024.\n\n[6] Chen et al., \"TimeMIL: Advancing Multivariate Time Series Classification via a Time-aware Multiple Instance Learning\", *ICML*, 2024.\n\n[7] Ilse et al., \"Attention-based deep multiple instance learning\", *PMLR*, 2018.\n\n[8] Javed et al., \"Additive MIL: Intrinsically interpretable multiple instance learning for pathology\", *NeurIPS*, 2022.\n\n[9] Tibo et al., \"Learning and interpreting multi-multi-instance learning networks\", *Journal of Machine Learning Research*, 2020. \n\n[10] Fuster et al., \"Nested multiple instance learning with attention mechanisms\", *ICMLA*, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
Thank you for your valuable feedback and insightful comments. We appreciate the time and effort you have invested in reviewing our work. K1fQ and W4rs recognized our focus on the theoretical foundations of our study. dSpL and 2msW acknowledged the clarity and rigor of our theoretical framework and arguments. Finally, bVsY appreciated the clarity and potential impact of our work within the MIL community.

We did our best to address all of your comments and will make the necessary revisions to improve the clarity, rigor, and validity of our manuscript. We kindly ask for your consideration in adjusting the review score if you find that our response has effectively addressed your concerns. In the revised manuscript, we will make the following major modifications.

1. **Extensive Expansion of Experimental Validation**
    - We have expaned experimental validation to a wider range of Deep MIL algorithms to demonstrate the practical applicability of our theoretical framework.
    - Tables A and B of the attached PDF show experimental validation results for Deep MILs, which confirm the same conclusions as the theoretical framework of this paper. We will include detailed analysis and experimental results for these conclusions in the revised manuscript.
    - Based on experimental validation, it was confirmed that MIL algorithms using the same pooling method exhibit a similar overall trend to the theoretical analysis of the framework, despite slight performance differences.
2. **Practical usage of Multi-Dimensional MIL (MD-MIL)**
    - MD-MIL involves learning from bag-of-bags labels, predicting labels for the bags that comprise these bag-of-bags, and for the instances within each bag.
    - According to Theorems 9, 10, and 11, using information from instances outside the target instance for prediction should be limited to the attention mechanism. Thus, in predicting instances within a specific bag, the relationships with instances from other bags should be utilized only through attention operations.
    - As the research on MD-MIL is still in its early stages, this study does not consider all possible pooling combinations for MD-MIL. Instead, it aims to demonstrate the practical effectiveness of MD-MIL by investigating whether a model that theoretically considers the relationships between bags can directly enhance performance. To this end, experiments on MD-MIL were conducted using the ShanghaiTech Video Anomaly Detection (VAD) dataset.
    - We evaluated the prediction performance of frames (i.e., bags) and image patches (i.e., instances) in videos, comparing three methods according to the instances used from other bags for instance prediction: 1) **None-Attention,** which does not utilize attention mechanisms, 2) **Attention**, which uses attention mechanisms within the same bag, and 3) **Cross-Attention**, which uses attention mechanisms that leverage features from instances in other bags.
        - These three attention mechanisms are theoretically used for **Conjunctive Pooling** in the **General Domain Space**, at each dimension (instance and bag).
    - The experimental results are in Table C of the attached PDF. The Cross-Attention method showed the highest performance by effectively utilizing relationships between instances across different bags, confirming the practical usage of MD-MIL.
3. **Overall presentation enhancement**
    - We will add the figures in the attached PDF to the paper to help readers understand.
        - **Figure A**: A summary diagram showing the relationships between theorems. This will help readers understand the flow and connections between the theorems and the corresponding pooling methods.
    - We believe these revisions address the reviewers' concerns and enhance the overall quality and clarity of the manuscript. Thank you for considering our response.

**References:**

[1] Shi et al., Loss-based attention for deep multiple instance learning. AAAI, 2020.

[2] Liu et al., Weakly-Supervised Residual Evidential Learning for Multi-Instance Uncertainty Estimation. ICML, 2024.

[3] Wang et al., Rethinking Multiple Instance Learning for Whole Slide Image Classification: A Bag-Level Classifier is a Good Instance-Level Teacher. IEEE Transaction on Medical Imaging, 2024.

[4] Shao et al., Transmil: Transformer based correlated multiple instance learning for whole slide image classification. Neurips, 2021.

[5] Zhang et al., Multi-instance causal representation learning for instance label prediction and out-of-distribution generalization. Neurips, 2022.

[6] Rymarczyk et al., Kernel self-attention in deep multiple instance learning. arXiv, 2020.

[7] Wang et al., Revisiting multiple instance neural networks. Pattern recognition, 2018.

[8] Ilse et al., Attention-based deep multiple instance learning. PMLR., 2018.

[9] Javed et al., Additive mil: Intrinsically interpretable multiple instance learning for pathology. Neurips, 2022.

[10] Early et al., Inherently interpretable time series classification via multiple instance learning. ICLR, 2024.

Meta-review: The paper develops a novel theoretical framework to investigate the instance-level learnability of deep multiple instance learning based on the probably approximately correct (PAC) learning theory. The proposed framework fills out a critical gap to understand existing MIL algorithms through the lens of PAC learning theory. The theories along with their conditions can be leverages to choose the most appropriate MIL algorithm based on the specific settings of the problem. They also provide useful insights that could help to shape the future MIL research. 

All the reviewers participated in the discussions with the authors. The authors did a decent job in their rebuttal and during their follow-up discussions with the reviewers. In the end, all reviewers assigned a positive rating in support of the acceptance of the paper. The authors are encouraged to include the important comments/suggestions from the reviewers into the final version of the paper.
Decision: Accept (poster)