Kernelizing the output of tree-based methods

ABSTRACT

We extend tree-based methods to the prediction of structured outputs using a kernelization of the algorithm that allows one to grow trees as soon as a kernel can be defined on the output space. The resulting algorithm, called output kernel trees (OK3), generalizes classification and regression trees as well as tree-based ensemble methods in a principled way. It inherits several features of these methods such as interpretability, robustness to irrelevant variables, and input scalability. When only the Gram matrix over the outputs of the learning sample is given, it learns the output kernel as a function of inputs. We show that the proposed algorithm works well on an image reconstruction task and on a biological network inference problem.

References

1. Blockeel, H., Bruynooghe, M., Dzeroski, S., Ramon, J., & Struyf, J. (2002). Hierarchical multi-classification. KDD-2002 Workshop Notes: MRDM 2002, Workshop on Multi-Relational Data Mining (pp. 21--35).]]
2. Blockeel, H., De Raedt, L., & Ramon, J. (1998). Top-down induction of clustering trees. Proc. of ICML 1998 (pp. 55--63).]]
3. Breiman, L. (1996). Bagging predictors. Machine Learning, 24, 123--140.]]
4. Breiman, L., Friedman, J., Olsen, R., & Stone, C. (1984). Classification and regression trees. Wadsworth International (California).]]
5. Cortes, C., Mehryar, M., & Weston, J. (2005). A general regression technique for learning transductions. Proceedings of ICML 2005 (pp. 153--160).]]
6. Dhillon, I., Guan, Y., & Kullis, B. (2004). Kernel k-means, spectral clustering and normalized cuts (Technical Report). University of Austin, Texas.]]
7. Geurts, P., Ernst, D., & Wehenkel, L. (2006). Extremely randomized trees. Machine Learning Journal (advance access: DOI 10.1007/s10994-006-6226-1).]]
8. Kondor, R., & Lafferty, J. (2002). Diffusion kernels on graphs and other discrete input. Proc. of ICML 2002 (pp. 315--322).]]
9. Ralaivola, L., & d'Alchéé-Buc, F. (2003). Dynamical modeling with kernels for nonlinear time series prediction. Advances in Neural Information Processing Systems.]]
10. Scholkopf, B., & Smola, A. (2002). Learning with kernels. MIT Press.]]
11. Segal, M. (1992). Tree structured methods for longitudinal data. Journal of the American Statistical Association, 87, 407--418.]]
12. Taskar, B., Chatalbashev, V., Koller, D., & Guestrin, C. (2005). Learning structured prediction models: A large margin approach. Proc. of the 22nd International Conference on Machine Learning (pp. 897--904).]]
13. Todorovski, L., Blockeel, H., & Dzeroski, S. (2002). Ranking with predictive clustering trees. Proc. of the 13th European Conference on Machine Learning (pp. 444--456).]]
14. Tsochantaridis, I., Joachims, T., Hofmann, T., & Altun, Y. (2005). Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6, 1453--1484.]]
15. Tsuda, K., Akaho, S., & Asai, K. (2003). The em algorithm for kernel matrix completion with auxiliary data. Journal of machine learning research, 4, 67--81.]]
16. Vert, J.-P., & Yamanishi, Y. (2004). Supervised graph inference. Advances in Neural Information Processing Systems, 17, 1433--1440.]]
17. Weston, J., Chapelle, O., Elisseeff, A., Schoelkopf, B., & Vapnik, V. (2002). Kernel dependency estimation. Advances in Neural Information Processing Systems, 15.]]
18. Weston, J., Schoelkopf, B., & Bousquet, O. (2005). Joint kernel maps. Proceedings of the 8th International Work-Conference on Artificial Neural Networks (pp. 176--191).]]
19. Yamanishi, Y., Vert, J.-P., & Kanehisa, M. (2004). Protein network inference from multiple genomic data: a supervised approach. Bioinformatics, 20, i363--i370.]]
20. Yamanishi, Y., Vert, J.-P., & Kanehisa, M. (2005). Supervised enzyme network inference from the integration of genomic data and chemical information. Bioinformatics, 21, i468--i477.]]

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Discrete space search

      • Game tree search

  • Machine learning

    • Machine learning approaches

      • Factorization methods

        • Canonical correlation analysis

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Regression analysis