# Multiple Instance Learning with Trainable Soft Decision Tree Ensembles
## 3 Preliminary  
### Multiple Instance Learning  
First, we formulated the MIL classification problem [7; 8; 9; 13]. It differs from the standard classification in data structure. Namely, in the MIL problem, bags have class labels, but instances, which compose each bag, are usually unlabeled. As a result, this problem can be regarded as a kind of weakly supervised learning problem. Due to the availability of labels which are only for bags, the following tasks can be stated in the framework of MIL. The first task is concerned with annotation of instances from a bag. The second task aims to annotate new bags by having a training set of bags, i.e., the task is to train a classifier at the bag level. The above tasks can be solved by introducing special rules which establish the relationship between instances and the bag class labels. Let us formally state the MIL problem taking into account the rules connecting different levels of the MIL data consideration. Suppose that each bag is defined by a set of \(n\) instances \(\mathbf{X}=\{\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\}\), where the \(i\)-th instance \(\mathbf{x}_{i}\in\mathbb{R}^{m}\) is represented by the feature vector. Each instance \(\mathbf{x}_{i}\) has a label \(y_{i}\in\{0,1\}\) taking two values: 0 (negative class) and 1 (positive class). We do not know labels \(y_{i}\) during training, as it follows from the MIL problem statement. According to the first task, we constructed a function \(g\) which maps each vector \(\mathbf{x}_{i}\) into the label \(y_{i}\). There are various rules establishing the relationship between labels of bags and instances. One of the most common rules can be rewritten as follows: [9]:  
\[f(\mathbf{X})=\left\{ \begin{array}{ll}1,&\exists\mathbf{x}\in\mathbf{X}:g( \mathbf{x})=1,\\ 0,&\text{otherwise},\end{array} \right. \tag{1}\]  
where \(f(\mathbf{X})\) is a bag classifier. It follows from (1) that at least one positive instance makes the bag positive, and negative bags contain only negative instances. As an example, we considered histopathological images divided into several patches [12; 14]. The whole image with one of the labels \"cancer\" or \"non-cancer\" can be viewed as a bag, whereas each patch of the image can be regarded as an instance. The function \(f(\mathbf{X})\), taking values 1 and 0, corresponds to the image labels \"cancer\" or \"non-cancer\", respectively. The function \(g(\mathbf{x})\), which also takes values 1 and 0, corresponds to the patch labels \"cancer\" or \"non-cancer\", respectively. If the image is from the high-risk patient, then it should be labeled as \"cancer\" if at least one of all patches belonging to the image contain malignant tumor [12]. On the other hand, if the patient is low risk, then the rule establishing the relationship between labels of bags and instances can be relaxed, i.e., some number of \"cancer\" patches are necessary to assign the \"cancer\" label to the whole histopathological image. In this case, the function \(f(\mathbf{X})\) can be defined in another way, taking into account a threshold \(\theta\); for example, the number of \"cancer\" patches, can be defined as  
\[f(\mathbf{X})=\left\{ \begin{array}{ll}1,&\theta\leq\sum_{\mathbf{x}\in \mathbf{X}}g(\mathbf{x}),\\ 0,&\text{otherwise}.\end{array} \right. \tag{2}\]  
We use the rule defined in (1). The dataset can be represented as  
\[\mathcal{D}=\Big{\{}\Big{(}\{\mathbf{x}_{k}^{(i)}\}_{k=1}^{n_{i}},y_{i}\Big{)} \Big{\}}_{i=1}^{N}, \tag{3}\]  
where \(\mathbf{x}_{k}^{(i)}\) is the \(k\)-th instance vector belonging to the \(i\)-th bag; \(n_{i}\) is the number of instances in the \(i\)-th bag; \(N\) is the number of labeled bags in the training set.