# Multiple Instance Learning with Trainable Soft Decision Tree Ensembles
## 3 Preliminary
### Oblique Binary Soft Trees  
One of the important procedures to build oblique decision trees is optimization of their parameters. There are various decision rules for building trees. The so-called hard decision rules have been successfully implemented in [50; 51]. The rules are applied to oblique decision trees which may be improper when we deal with small tabular datasets because large degrees of freedom, in this case, would lead to overfitting. According to [50], an oblique binary tree of a height \(h\) represents a piece-wise constant function \(f(\mathbf{x};\mathbf{W},\mathbf{b}):\mathbb{R}^{m}\rightarrow\mathbb{R}^{K}\), parameterized by weights \(\mathbf{w}_{I(d,l)}\in\mathbb{R}^{m}\), \(b_{I(d,l)}\in\mathbb{R}\) at a node on the path from the tree root to its leaf \(l\) at the depth \(d\). Here, \(I(d,l)\) is the index of a node on the path from the tree root to its leaf \(l\) with depth \(d\). Function \(f\) computes decision functions of the form \(\mathbf{w}_{j}^{\mathrm{T}}\mathbf{x}-b_{j}>0\), that define whether \(\mathbf{x}\) must traverse the left or right child next. Here \(\mathbf{W}\) is the parameter matrix consisting of all parameter vectors \(\mathbf{w}_{j}\); \(\mathbf{b}\) is the parameter vector consisting of parameters \(b_{j}\). The tree output is represented as \(2^{h}\) vectors \(\theta_{1},\ldots,\theta_{2^{h}}\) such that vector \(\theta_{j}\in\Delta^{K}\) at the \(j\)-th leaf is associated with probabilities of \(K\) classes, where \(\geq^{K}_{i}\) is the unit simplex of dimension \(K\). One of the ways to learn parameters \(\mathbf{w}_{ij}\) and \(b_{ij}\) for all nodes is to minimize the expected loss \(l\) of the form:  
\[\min_{\mathbf{W},\mathbf{b}}\sum_{i=1}^{n}l(y_{i},f(\mathbf{x};\mathbf{W}, \mathbf{b})). \tag{6}\]  
[PERSON] et al. [50] propose the following function \(f_{\theta}(\mathbf{x};\mathbf{W},\mathbf{b})\):  
\[f_{\theta}(\mathbf{x};\mathbf{W},\mathbf{b})=\sum_{l=1}^{2^{h}}q_{l}(\mathbf{ x},\mathbf{W},\mathbf{b})\cdot\theta_{l}, \tag{7}\]  
where the tree path indicators \(q_{l}(\mathbf{x},\mathbf{W},\mathbf{b})\) are represented as the following indicator functions:  
\[q_{l}(\mathbf{x},\mathbf{W},\mathbf{b})=\mathbb{I}\left[\bigwedge_{d=1}^{h} \left([\mathbf{w}_{I(d,l)}^{\mathrm{T}}\mathbf{x}\leq b_{I(d,l)}]\oplus s(d, l)\right)\right], \tag{8}\]  
Here, \(\mathbb{I}(\cdot)\) is the indicator function taking the value \(1\) if its argument is non-negative, and otherwise it is \(0\); \(\oplus\) is the operator \(XOR\); \(s(d,l)\) determines whether the predicate of a node on the path to the leaf \(l\) at the depth \(d\) should be evaluated to be true or false, i.e., \(s(d,l)=1\) if the \(l\)-th leaf belongs to the left subtree of node \(I(d,l)\), otherwise \(s(d,l)=0\). It is well known that the conjunction in (8) can be replaced with the product, as follows:  
\[q_{l}(\mathbf{x},\mathbf{W},\mathbf{b})=\prod_{d=1}^{h}\mathbb{I}\Big{[}[ \mathbf{w}_{I(d,l)}^{\mathrm{T}}\mathbf{x}\leq b_{I(d,l)}]\oplus s(d,l)\Big{]}. \tag{9}\]  
However, this representation significantly complicates the optimization of the model by using the gradient descent algorithm, due to the vanishing gradient problem. Another representation of \(q_{l}(\mathbf{x},\mathbf{W},\mathbf{b})\) is proposed in [50]. It is of the form:  
\[q_{l}(\mathbf{x},\mathbf{W},\mathbf{b})=\sigma\Bigg{(}\sum_{d=1}^{h}\sigma \Big{[}[\mathbf{w}_{I(d,l)}^{\mathrm{T}}\mathbf{x}\leq b_{I(d,l)}]\oplus s(d, l)\Big{]}-h\Bigg{)}, \tag{10}\]  
where the indicator functions are replaced with the so-called \(\sigma\)-hard indicator approximations [50], which apply quantized functions in the forward pass, but use the smooth activation functions in the backward pass to propagate. This specific representation of the sigmoid function is called the straight-through operator and is proposed in [52]. The above representation allows us to effectively apply the gradient descent algorithm to compute optimal parameters of the tree in accordance with the loss function (6).