Multi-instance tree learning

ABSTRACT

We introduce a novel algorithm for decision tree learning in the multi-instance setting as originally defined by Dietterich et al. It differs from existing multi-instance tree learners in a few crucial, well-motivated details. Experiments on synthetic and real-life datasets confirm the beneficial effect of these differences and show that the resulting system outperforms the existing multi-instance decision tree learners.

REFERENCES

• 1: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4 ]
• 2: Breiman, L., Friedman, J., Olshen, R., & Stone, C. (1984). Classification and regression trees. Belmont: Wadsworth.
• 3: Cestnik, B. (1990). Estimating probabilities: A crucial task in machine learning. Proceedings of the 9th European Conference on Artificial Intelligence (pp. 147--149). London: Pitman.
• 4: Yann Chevaleyre , Jean-Daniel Zucker, Solving Multiple-Instance and Multiple-Part Learning Problems with Decision Trees and Rule Sets. Application to the Mutagenesis Problem, Proceedings of the 14th Biennial Conference of the Canadian Society on Computational Studies of Intelligence: Advances in Artificial Intelligence, p.204-214, June 07-09, 2001
• 5: Cohen, W. (1995). Fast effective rule induction. Proceedings of the twelfth International Conference on Machine Learning (pp. 115--123). Morgan Kaufmann.
• 6: Thomas G. Dietterich , Richard H. Lathrop , Tomás Lozano-Pérez, Solving the multiple instance problem with axis-parallel rectangles, Artificial Intelligence, v.89 n.1-2, p.31-71, Jan. 1997 [doi>10.1016/S0004-3702(96)00034-3 ]
• 7: J. R. Quinlan, Induction of Decision Trees, Machine Learning, v.1 n.1, p.81-106 [doi>10.1023/A:1022643204877]
• 8: Ruffo, G. (2000). Learning single and multiple instance decision trees for computer security applications. Doctoral dissertation, Department of Computer Science, University of Torino.
• 9: Ashwin Srinivasan , S. H. Muggleton , M. J. E. Sternberg , R. D. King, Theories for mutagenicity: a study in first-order and feature-based induction, Artificial Intelligence, v.85 n.1-2, p.277-299, Aug. 1996 [doi>10.1016/0004-3702(95)00122-0 ]
• 10: Xu, X. (2003). Statistical learning in multiple instance problems. Master's thesis, University of Waikato.