The Mondrian Kernel

Matej Balog, Balaji Lakshminarayanan, Zoubin Ghahramani, Daniel Roy, Yee Whye Teh
Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, PMLR R14:652-661, 2016.

Abstract

We introduce the Mondrian kernel, a fast random feature approximation to the Laplace kernel. It is suitable for both batch and online learning, and admits a fast kernel-width-selection procedure as the random features can be re-used efficiently for all kernel widths. The features are constructed by sampling trees via a Mondrian process [Roy and Teh, 2009], and we highlight the connection to Mondrian forests [Lakshminarayanan et al., 2014], where trees are also sampled via a Mondrian process, but fit independently. This link provides a new insight into the relationship between kernel methods and random forests.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR14-balog16a, title = {The Mondrian Kernel}, author = {Balog, Matej and Lakshminarayanan, Balaji and Ghahramani, Zoubin and Roy, Daniel and Teh, Yee Whye}, booktitle = {Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence}, pages = {652--661}, year = {2016}, editor = {Ihler, Alexander and Janzing, Dominik}, volume = {R14}, series = {Proceedings of Machine Learning Research}, month = {25--29 Jun}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r14/main/assets/balog16a/balog16a.pdf}, url = {https://proceedings.mlr.press/r14/balog16a.html}, abstract = {We introduce the Mondrian kernel, a fast random feature approximation to the Laplace kernel. It is suitable for both batch and online learning, and admits a fast kernel-width-selection procedure as the random features can be re-used efficiently for all kernel widths. The features are constructed by sampling trees via a Mondrian process [Roy and Teh, 2009], and we highlight the connection to Mondrian forests [Lakshminarayanan et al., 2014], where trees are also sampled via a Mondrian process, but fit independently. This link provides a new insight into the relationship between kernel methods and random forests.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T The Mondrian Kernel %A Matej Balog %A Balaji Lakshminarayanan %A Zoubin Ghahramani %A Daniel Roy %A Yee Whye Teh %B Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2016 %E Alexander Ihler %E Dominik Janzing %F pmlr-vR14-balog16a %I PMLR %P 652--661 %U https://proceedings.mlr.press/r14/balog16a.html %V R14 %X We introduce the Mondrian kernel, a fast random feature approximation to the Laplace kernel. It is suitable for both batch and online learning, and admits a fast kernel-width-selection procedure as the random features can be re-used efficiently for all kernel widths. The features are constructed by sampling trees via a Mondrian process [Roy and Teh, 2009], and we highlight the connection to Mondrian forests [Lakshminarayanan et al., 2014], where trees are also sampled via a Mondrian process, but fit independently. This link provides a new insight into the relationship between kernel methods and random forests. %Z Reissued by PMLR on 04 October 2026.
APA
Balog, M., Lakshminarayanan, B., Ghahramani, Z., Roy, D. & Teh, Y.W.. (2016). The Mondrian Kernel. Proceedings of the 32nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R14:652-661 Available from https://proceedings.mlr.press/r14/balog16a.html. Reissued by PMLR on 04 October 2026.

Related Material