Is it possible to express a decision tree as a kernel machine? This paper argues that models trained with gradient descent like neural networks can be expressed as kernel machines with an interesting kernel function.
The kernel is
$$ K(x, x') = \int_{c(t)} \nabla_w y(x) \cdot \nabla_w y(x') \, dt$$
where $c \colon [0, 1) \rightarrow \mathbb{R}^n$ is the path taken by the weight vector $w \in \mathbb{R}^n$ during gradient descent, and $y \colon \mathbb{R}^n \rightarrow \mathbb{R}$ denotes the network output.
Is there something similar for regression (decision) trees or gradient-boosted ensembles of regression trees?  Can we write a decision tree $f$ as being a kernel regression like
$$f(x) = \sum_{i} a_i K(x, x_i) + b$$ for training points $\{x_i\}$, some kernel function $K$ and learned weights $\{a_i\}, b$?.
 A: In Domingo's paper, there is a note stating that Theorem 1 only approximates the behavior of a gradient-descent-trained model by a kernel machine. This approximation is not the result of a finite $\epsilon$ but that these coefficients $a_i$ are effective $a_i(x)$, and since they depend on the training data, that is not a standard linear (kernel) model. Concretely, it is not possible to explain a neural network as an exact kernel machine yet, with some notable exceptions (e.g. infinite width neural networks, e.g. https://arxiv.org/abs/2111.06063). Quite a few papers comment on the strengths and weaknesses of the above-described approach, for example in https://arxiv.org/abs/2212.11826, Appendix A2 (*), and here.
To the best of my knowledge, no results have been suggesting we can express a decision tree with a kernel machine. I'm expecting that, if such a procedure exists, is not based on Domingo's Path Kernel due to the fact that its Theorem 1 heavily relies on the gradient descent training.
Out of curiosity, I'm expecting the opposite to be true: any function of fixed input size $n$ can be computed by a decision tree, if we do not limit its depth (see here).
(*) Conflict of interest: I wrote that.
