analiza aiqbench
This research addresses the scalability bottleneck in decision forest proximity computations by introducing a sparse factorization method that reduces complexity from quadratic to near-linear. By unifying various leaf-collision metrics under a single separable kernel framework, the authors enable efficient memory usage and faster task-aware embeddings for large-scale machine learning pipelines. The work provides both theoretical guarantees and practical library implementations to accelerate representation-learning workflows involving decision forests.
Revisiting Forest Proximities via Sparse Leaf-Incidence Kernels
arXiv:2601.02735v3 Announce Type: replace Abstract: Decision forests induce supervised similarities through the partition structure of their trees. Yet forest proximity computation is still often treated as a quadratic operation in the number of samples, which limits scalability and restricts broader use in kernel and representation-learning pipelines. We introduce a unified view of leaf-collision forest proximities through a class of Separable Weighted Leaf-Collision (SWLC) kernels, showing that most existing proximities differ only in their weighting scheme while sharing a common sparse leaf-incidence structure. This yields an explicit leaf-space representation that clarifies their kernel interpretation and leads to an exact finite-sample sparse factorization of the proximity matrix, avoiding an explicit all-pairs comparison and reducing computation to sparse linear algebra over leaf collisions. We implement this framework in a memory-efficient Python library and show, both theoretically and empirically, that exact kernel computation scales near-linearly in time and memory under standard forest regimes. Benchmarks verify the predicted scaling behavior in practice across datasets, proximity definitions, and forest settings, and show that the resulting sparse leaf-space representation can also be used directly for fast task-aware embedding.
Abstract:Decision forests induce supervised similarities through the partition structure of their trees. Yet forest proximity computation is still often treated as a quadratic operation in the number of samples, which limits scalability and restricts broader use in kernel and representation-learning pipelines. We introduce a unified view of leaf-collision forest proximities through a class of Separable Weighted Leaf-Collision (SWLC) kernels, showing that most existing proximities differ only in their weighting scheme while sharing a common sparse leaf-incidence structure. This yields an explicit leaf-space representation that clarifies their kernel interpretation and leads to an exact finite-sample sparse factorization of the proximity matrix, avoiding an explicit all-pairs comparison and reducing computation to sparse linear algebra over leaf collisions. We implement this framework in a memory-efficient Python library and show, both theoretically and empirically, that exact kernel computation scales near-linearly in time and memory under standard forest regimes. Benchmarks verify the predicted scaling behavior in practice across datasets, proximity definitions, and forest settings, and show that the resulting sparse leaf-space representation can also be used directly for fast task-aware embedding.
Machine Learning (cs.LG); Data Structures and Algorithms (cs.DS); Performance (cs.PF)
arXiv:2601.02735 [cs.LG]
(or arXiv:2601.02735v3 [cs.LG] for this version)
Text integral sub licența deschisă a publicației · 194 cuvinte
Subiecte conexe
[AINews] High Taste Testers Ep. 1
Latent Space · 17 oct. 2026
PIRAMID: Progress and Plans
LessWrong · 27 iul. 2026
[AINews] Meta Connect 2026: Muse glasses, voice, video, and Charm
Latent Space · 24 sept. 2026
SOCKET: SOft Collision Kernel EsTimator for Sparse Attention
arXiv · 30 sept. 2026