Explainable Machine Learning via Axis-Aligned Tree Partitioning

This direction is split into other directions: dimension-dependent explainability cost, price of explainability, interpretable hierarchical partitioning. Its last version stays readable and citable here.

Version 1 of 150 papers58 conceptsfrozen 2026-10-04

Most modern machine learning models operate as "black boxes." Whether it is a deep neural network or a $k$-means clustering algorithm, the logic behind a specific prediction or group assignment is often buried in high-dimensional distance calculations or complex weight matrices.

A growing body of research suggests a more transparent alternative: constraining models to use axis-aligned tree partitioning. By forcing decision boundaries to be perpendicular to feature axes, researchers are creating models that are "human-simulable"—meaning an expert can trace the logic of a decision through a simple sequence of "if-then" rules.

The Geometry of Interpretability

The fundamental unit of this research direction is the axis-parallel hyperrectangle. In a standard clustering algorithm like $k$-means, data is partitioned into Voronoi cells—complex, multi-dimensional shapes defined by the nearest center. While mathematically efficient, these cells are nearly impossible for a human to describe without referencing every single feature simultaneously.

In contrast, researchers like Siong Thye Goh and Cynthia Rudin propose "Box Drawing" classifiers in Box drawings for learning with imbalanced data. By representing classes as a union of rectangles, the model provides a "disjunction of conjunctions"—a logical structure that humans find intuitive. If a patient’s age is $>65$ AND their blood pressure is $>140$, they fall into a specific "box" or cluster. This axis-aligned approach ensures that each boundary is defined by a single feature threshold.

Explainable Clustering and the Price of Explainability

Clustering is a primary frontier for this technique. Standard $k$-means is powerful but opaque. To solve this, Michal Moshkovitz, Sanjoy Dasgupta, and colleagues introduced the Iterative Mistake Minimization (IMM) algorithm in Explainable k-Means and k-Medians Clustering. IMM builds a small decision tree to partition data, ensuring that every cluster corresponds to a leaf in that tree.

However, forcing clusters into axis-aligned boxes comes with a cost. Eduardo Sany Laber and Lucas Murtinho have quantified this as the Price of Explainability (PoE) in On the price of explainability for some clustering problems. The PoE is the ratio between the cost of an explainable (tree-based) clustering and the cost of an unrestricted (Voronoi-based) clustering.

Recent work by Konstantin Makarychev and Liren Shan has achieved massive theoretical breakthroughs in minimizing this price. In Near-Optimal Algorithms for Explainable k-Medians and k-Means, they demonstrated that we can achieve explainable partitions with costs that are only logarithmically worse than black-box versions, effectively proving that we don't have to sacrifice much accuracy for total transparency.

Tree Regularization: Making Neural Networks Simulable

The same intuition is being applied to deep learning. Standard neural networks create curved, diagonal decision boundaries that are impossible to audit. In Optimizing for Interpretability in Deep Neural Networks with Tree Regularization, Mike Wu and Finale Doshi-Velez introduced a novel penalty term.

This "tree regularization" encourages the neural network’s complex decision boundary to be easily approximatable by a small, axis-aligned decision tree. By using a differentiable surrogate to estimate tree complexity during training, they produce high-performing models that an expert can "simulable" by following a few simple rules.

Applications in High-Stakes Domains

The push for axis-aligned tree partitioning is driven by fields where "why" is as important as "what":

Why It Works

Axis-aligned tree partitioning works because it aligns machine logic with the constraints of human cognition. We struggle to weigh twenty variables at once, but we are excellent at following a sequence of binary choices. By constraining the geometry of our models to axis-parallel hyperrectangles, we bridge the gap between high-dimensional data and actionable, human-readable insight.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_explainable_machine_learning_via_axis_al_8eab1605,
  title = {Explainable Machine Learning via Axis-Aligned Tree Partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/explainable-machine-learning-via-axis-aligned-tree-partitioning/rdr_8eab16052ac54e9aaebe3a077e9992b2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_explainable_machine_learning_via_axis_al_8eab1605_v1,
  title = {Explainable Machine Learning via Axis-Aligned Tree Partitioning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/explainable-machine-learning-via-axis-aligned-tree-partitioning/rdr_8eab16052ac54e9aaebe3a077e9992b2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}