Multiple Instance Learning (MIL) addresses problems where labels exist only for bags of instances, often requiring complex assumptions or computationally expensive embedding techniques to solve. While dissimilarity-based representations capture global structure effectively, they frequently suffer from high computational costs and difficult hyperparameter tuning. To address these limitations, this study proposes bridging the gap between dissimilarity-based embeddings and interpretable tree-based ensembles by introducing two novel frameworks: Prototype Forest (PF) and Prototype Forest with Prototype Learning (PFPL). Both methods represent bags via dissimilarity features (minimum, maximum, and mean distances) to reference prototypes within a decision tree structure. PF leverages the efficiency of Random Forests by using randomly selected instances as prototypes at split nodes, serving as a regularization technique that minimizes tuning requirements and computational load. Conversely, PFPL incorporates a stochastic gradient descent-based learning mechanism to optimize prototypes at each node, generating splits that better separate bag classes. We evaluated both approaches against 18 state-of-the-art baselines across 71 benchmark datasets from diverse domains, including image, text, and audio classification. Extensive experiments demonstrate that PFPL achieves the highest predictive performance among all tested methods (Average AUC: 0.899). However, this accuracy comes with a computational trade-off, as PFPL requires significantly higher run-time compared to the standard PF, which remains highly competitive (Average AUC: 0.887) while maintaining the speed advantages of non-parametric ensembles.
