{"corpus_id":18317501,"paper_sha":"17fa04092cc8f557de27ebe06f99be2dc62e803e","doi":"10.17863/CAM.4533","arxiv_id":"1606.05241","pmid":null,"pmcid":null,"mag_id":2963522946,"dblp_id":"conf/uai/BalogLGRT16","acl_id":null,"title":"The Mondrian Kernel","year":2016,"publication_date":"2016-06-16","venue":"Conference on Uncertainty in Artificial Intelligence","journal":{"name":"arXiv: Machine Learning","pages":null,"volume":""},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle","Conference"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":21,"citation_count":29,"influential_citation_count":6,"is_open_access":false,"arxiv_categories":["stat.ML"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"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.","claims":[{"public_id":"cl_8e24645206cc77eec7c3195651c87445","status":"active","text":"Its features are constructed by sampling trees via a Mondrian process.","confidence":0.97,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_8e24645206cc77eec7c3195651c87445"},{"public_id":"cl_9b8a6ef84e9bbac86d39c461ab99ed40","status":"active","text":"Kernel-width selection can be performed efficiently because the same random features are re-used across all kernel widths.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_9b8a6ef84e9bbac86d39c461ab99ed40"},{"public_id":"cl_7457423d4af37bc12fa37cebe9964eb8","status":"active","text":"Mondrian kernel is a fast random feature approximation to the Laplace kernel.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_7457423d4af37bc12fa37cebe9964eb8"},{"public_id":"cl_99be97db4f7a44f53a82e1fa7243f1c7","status":"active","text":"Mondrian kernel is suitable for both batch and online learning.","confidence":0.93,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_99be97db4f7a44f53a82e1fa7243f1c7"},{"public_id":"cl_d88f55a30c5493280edbc82ed39dc74c","status":"active","text":"The connection to Mondrian forests provides a new insight into the relationship between kernel methods and random forests.","confidence":0.9,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_d88f55a30c5493280edbc82ed39dc74c"}],"concepts":[{"public_id":"co_1476b6b257421ed4ffe6727edc574ee9","status":"active","name":"kernel methods","description":"Learning methods that operate using kernels to represent similarity or structure in data.","types":["method family"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1476b6b257421ed4ffe6727edc574ee9"},{"public_id":"co_1479332a2b7e3ab20c058fa382bfd887","status":"active","name":"random forests","description":"An ensemble learning approach based on multiple decision trees.","types":["ensemble method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1479332a2b7e3ab20c058fa382bfd887"},{"public_id":"co_17ea6de02b5797ed36b953c05b0fda74","status":"active","name":"Mondrian process","description":"A stochastic process used here to sample tree structures for constructing random features.","types":["stochastic process","sampling method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_17ea6de02b5797ed36b953c05b0fda74"},{"public_id":"co_3eeb5d7b285c04d6fc5ff5b3bc9115ea","status":"active","name":"Mondrian kernel","description":"A random feature-based kernel approximation introduced as a fast approximation to the Laplace kernel.","types":["method","kernel approximation"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_3eeb5d7b285c04d6fc5ff5b3bc9115ea"},{"public_id":"co_463e3463ac356acaf10fc57a133e7463","status":"active","name":"online learning","description":"A learning setting in which model updates are made incrementally as data arrive.","types":["learning setting"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_463e3463ac356acaf10fc57a133e7463"},{"public_id":"co_5ca26966a4470e48aee5c68f3dbb976f","status":"active","name":"trees","description":"Tree-structured models sampled from the Mondrian process for feature construction.","types":["model structure"],"aliases":["decision trees"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_5ca26966a4470e48aee5c68f3dbb976f"},{"public_id":"co_8dcb83a9be338e0d4d0d1dbb65a8722a","status":"active","name":"batch learning","description":"A learning setting in which training is performed on a fixed dataset as a whole.","types":["learning setting"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_8dcb83a9be338e0d4d0d1dbb65a8722a"},{"public_id":"co_a967a6c628797209df68f1730e29d55c","status":"active","name":"Mondrian forests","description":"An ensemble of trees sampled via a Mondrian process and fit independently.","types":["random forest","ensemble method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_a967a6c628797209df68f1730e29d55c"},{"public_id":"co_b1a506b5e0df944a4e9346029d76ac8e","status":"active","name":"kernel-width-selection procedure","description":"A procedure for choosing the kernel width parameter in the model.","types":["method","hyperparameter selection"],"aliases":["kernel width selection"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b1a506b5e0df944a4e9346029d76ac8e"},{"public_id":"co_c613c610eb57357d86816eab9e99a941","status":"active","name":"random features","description":"Randomly generated feature mappings used to approximate a kernel while enabling efficient computation.","types":["representation","method"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c613c610eb57357d86816eab9e99a941"},{"public_id":"co_e314e109b3105b9ae801a9c7f189428e","status":"active","name":"Laplace kernel","description":"A kernel function used as the target of the random feature approximation.","types":["kernel"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_e314e109b3105b9ae801a9c7f189428e"}],"external_ids":{"DOI":"10.17863/CAM.4533","ArXiv":"1606.05241","PubMed":null,"PubMedCentral":null,"MAG":2963522946,"DBLP":"conf/uai/BalogLGRT16","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://arxiv.org/pdf/1606.05241","landing_url":"https://arxiv.org/abs/1606.05241","source":"arxiv","pdf_url_source":"derived_arxiv","license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":637828,"paper_uid":"63e394c1-cd7c-4b5b-b632-14a1bca9bf73","canonical_identity":{"paper_id":637828,"paper_uid":"63e394c1-cd7c-4b5b-b632-14a1bca9bf73","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/18317501"}