Which Spatial Partition Trees are Adaptive to Intrinsic Dimension?
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913757933862912 |
|---|---|
| author | Verma, Nakul Kpotufe, Samory Dasgupta, Sanjoy |
| author_facet | Verma, Nakul Kpotufe, Samory Dasgupta, Sanjoy |
| contents | Recent theory work has found that a special type of spatial partition tree - called a random projection tree - is adaptive to the intrinsic dimension of the data from which it is built. Here we examine this same question, with a combination of theory and experiments, for a broader class of trees that includes k-d trees, dyadic trees, and PCA trees. Our motivation is to get a feel for (i) the kind of intrinsic low dimensional structure that can be empirically verified, (ii) the extent to which a spatial partition can exploit such structure, and (iii) the implications for standard statistical tasks such as regression, vector quantization, and nearest neighbor search. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1205_2609 |
| institution | arXiv |
| publishDate | 2012 |
| record_format | arxiv |
| spellingShingle | Which Spatial Partition Trees are Adaptive to Intrinsic Dimension? Verma, Nakul Kpotufe, Samory Dasgupta, Sanjoy Machine Learning Recent theory work has found that a special type of spatial partition tree - called a random projection tree - is adaptive to the intrinsic dimension of the data from which it is built. Here we examine this same question, with a combination of theory and experiments, for a broader class of trees that includes k-d trees, dyadic trees, and PCA trees. Our motivation is to get a feel for (i) the kind of intrinsic low dimensional structure that can be empirically verified, (ii) the extent to which a spatial partition can exploit such structure, and (iii) the implications for standard statistical tasks such as regression, vector quantization, and nearest neighbor search. |
| title | Which Spatial Partition Trees are Adaptive to Intrinsic Dimension? |
| topic | Machine Learning |
| url | https://arxiv.org/abs/1205.2609 |