Non-asymptotic Properties of Generalized Mondrian Forests in Statistical Learning

Our method about generalizing RF is based on a global perspective, while the method of generalizing RF in Athey et al. (2019) starts from a local perspective. In other words, by doing one optimization with full data points, we can estimate the objective function $m(x),\forall x\in[0,1]^{d}$ and Athey et al. (2019) can only estimate a specific point $m(x_{0})$. Therefore, our generalized method can save a lot of time in computation especially when the dimension $d$ is large. Secondly, the generalized method based on globalization can also be easily applied to the statistical problem with a penalization $Pen(m)$, where $Pen(m)$ is a functional of $m(x),\forall x\in[0,1]^{d}$. In Section 6.4, we show the application of our method in one of these penalty optimizations, namely the nonparametric density estimation. Since Athey et al. (2019) only perform estimation pointwisely, it is difficult for them to ensure the obtained estimator satisfies shape constraints and the corresponding case is not included in their scope.

Let $(X,Y)\in[0,1]^{d}\times{\mathbb{R}}$ be the random vector, where we normalize the range of $X$. In statistical learning, we would like a policy $h$ to learn $Y$ from $X$, which is defined as a function $h:[0,1]^{d}\to{\mathbb{R}}$. Usually, a loss function $\ell(h(x),y):{\mathbb{R}}\times{\mathbb{R}}\to[0,\infty)$ is used to measure the difference or loss between the decision $h(x)$ and goal $y$. Taking expectation w.r.t. $X,Y$, the risk function

denotes the averaged loss by using the policy $h$. Naturally, people have reasons to select the best policy $h^{*}$ by minimizing the averaged loss over some function class $\mathcal{H}_{1}$, namely

Therefore, $R(h^{*})$ has the minimal risk in theory that one can try the best to achieve. In practice, the distribution of $(X,Y)$ is unknown and (1) is not able to be used for the calculation of $R(h)$. Thus, such best $h^{*}$ can not be obtained in a direct way. On the other hand, we usually use i.i.d. data ${\mathcal{D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}$ to approximate $R(h)$. Thus, the empirical risk function can be approximated by

Traditionally, people always find an estimator/policy $\hat{h}_{n}:[0,1]^{d}\times{\mathbb{R}}$ by minimizing $\hat{R}(h)$ over a known function class; see spline regression in Györfi et al. (2002), wavelet regression in Györfi et al. (2002) and regression by deep neural networks in Schmidt-Hieber (2020). Recently, instead of minimizing $\hat{R}(h)$ globally, tree-based algorithms have been applied to construct the empirical estimator $\hat{h}_{n}$. According to many practitioners’ experience, the strong prediction ability of RF’s have shown the superiority of tree-based estimators over many traditional methods in statistical learning. In this paper, we are interested in bounding the regret function

where $\hat{h}_{n}$ will be an ensemble estimator obtained by Mondrian Forests.

Mondian partitions correspond with a case of random tree partitions, where the partition of $[0,1]^{d}$ is independent of data points. This scheme totally depends on a stochastic process, named as Mondrian process and denoted by $MP([0,1]^{d})$. The Mondrian process $MP([0,1]^{d})$ is a distribution on infinite tree partitions of $[0,1]^{d}$ introduced by Roy and Teh (2008) and Roy (2011). To reduce notations, the details of its definition is omitted here and can be checked in Definition 3 in Mourtada et al. (2020).

Let us come back to the Mondrian partitions. The partition that will be used in this paper is called the Mondrian partitions with stopping time $\lambda$ and is denoted by $MP(\lambda,[0,1]^{d})$. (see Section 1.3 in Mourtada et al. (2020)) Its construction consists of two steps. Firstly, we construct partitions according to $MP([0,1]^{d})$ by iteratively splitting cells at random times, which depend on the linear dimension of each cell. The probability of splitting along each side is proportional to the side length of the cell, and the splitting position is chosen uniformly. Secondly, we cut the nodes whose birth time is behind the tuning parameter $\lambda>0$. Note that each tree node generated in the first step was given a specific birth time. When the tree layer grows, the birth time also increases. Therefore, the second step can be regarded as a pruning process, which helps us choose the best tree model in learning problems.

Let $C=\Pi_{j=1}^{d}{C^{j}}\subseteq[0,1]^{d}$ with closed intervals $C^{j}=[a_{j},b_{j}]$. Denote $|C^{j}|=b_{j}-a_{j}$ and $|C|=\sum_{j=1}^{d}{|C^{j}|}$. Let $Exp(|C|)$ be an exponential distribution with expectation $|C|>0$. Then, our Mondrian partition with stopping time $\lambda>0$ can be generated according to Algorithm 1. In fact, this algorithm is a recursive process and in the initial time we input the root node $[0,1]^{d}$. On the other hand, we give an example in Figure 1 to show how Algorithm 1 works.

Nonparametric least squares regression refers to methods that do not assume a specific parametric form of the conditional expectation ${\mathbf{E}}(Y|X)$. Instead, these methods are flexible and can adapt to the underlying structure of the data. The loss function of least square regression is given by $\ell_{1}(x,y)=(x-y)^{2}$. First, we define the event $A_{n}:=\{\max_{1\leq i\leq n}{|Y_{i}|}\leq\ln n\}$. Under the Assumption 4, by (34) we can find constants $c,c^{\prime}>0$ such that ${\mathbf{P}}(A_{n})\geq 1-c^{\prime}\cdot ne^{-c\ln^{2}n}$. This means ${\mathbf{P}}(A_{n})$ is very close to $1$ as $n\to\infty$. On the event $A_{n}$, from (2) we further know

where $Card(\cdot)$ denotes the cardinality of a set. Therefore, $\hat{c}_{b,\lambda,j}$ is just the average of $Y_{i}$s that are in the leaf ${\small\mathcal{C}}_{b,\lambda,j}$.

Let us discuss the property of $\ell_{1}(x,y)=(x-y)^{2}$. First, it is obvious that Assumption 1 holds for this $\ell^{2}$ loss. By some simple calculations, we also know Assumption 1 is satisfied with $M_{1}(x,y)=2(|x|+|y|)$ and Assumption 2 is satisfied with $M_{2}(x,y)=2(x^{2}+y^{2})$. Choosing $\lambda_{n}=n^{\frac{1}{2(p+d)}}$ and $\beta_{n}\asymp\ln n$, Theorem 1 implies the following property of $\hat{h}_{n}$.

Then, we check Theorem 1. By some simple calculations, we have $m(x)={\mathbf{E}}(Y|X=x)$ and

The above inequality shows Assumption 5 holds with $c=1$ and $\kappa=2$. When $\lambda_{n}=n^{\frac{1}{2(p+d)}}$ is selected, Corollary 1 tells us

We can also show $\hat{h}_{n}$ is consistent for any general function $m$ defined in (5) if the convergence rate of $\lambda_{n}$ is chosen as stated in Corollary 2. Finally, choose $\alpha_{n}=n^{-\frac{p}{2p+4d}}$ and $\beta_{n}\asymp\ln n$ in Theorem 2. The regret function of the estimator $\hat{h}^{*}_{n}$ that is based on the model selection in (8) has the upper bound below.

Generalized regression refers to a broad class of regression models that extend beyond the traditional ordinary least squares (OLS) regression, accommodating various types of response variables and relationships between predictors and response. Usually, in this model the conditional distribution of $Y$ given $X$ follows an exponential family of distribution

where $\Psi(dy)$ is a positive measure defined on ${\mathbb{R}}$ and $\Psi({\mathbb{R}})>\Psi(y)$ for any $y\in{\mathbb{R}}$. The above function $D(\cdot)$ is used as the aim of normalization that is defined on a open subinterval $\mathcal{I}$ of ${\mathbb{R}}$ and $D(m)=\ln\int_{R}{\exp\{B(m)y\}}\Psi(dy)$. Now, we suppose the function $A(m):=D^{\prime}(m)/B^{\prime}(m)$ exists and we have ${\mathbf{E}}(Y|X=x)=A(m(x))$ by some calculations. Thus, the conditional expectation ${\mathbf{E}}(Y|X=x)$ will be known if we can estimate the unknown function $m(x)$. More information about (11) can be found in Stone (1986), Stone (1994) and Huang (1998).

The problem of generalized regression is to estimate the unknown function $m(x)$ by using the i.i.d. data ${\mathcal{D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}$. Note that both $B(\cdot)$ and $D(\cdot)$ are known in (11). In this case, we use the maximal likelihood method for the estimation and the corresponding loss function is given by

and by some calculations we know the true function $m$ satisfies Definition 5, namely

Therefore, we have reasons to believe Mondrian forests is statistically consistent in this problem, which is stated in Corollary 2. Now we give some mild restrictions on $B(\cdot)$ and $D(\cdot)$ in order to make sure our general results can be applied in generalized regression.

Conditions

1. (i)

   $B(\cdot)$ has the 2nd continuous derivative and its first derivative is strictly positive on $\mathcal{I}$.

2. (ii)

   We can find a subinterval $S$ of ${\mathbb{R}}$ satisfying the measure $\Psi$ is concentrated on $S$ and

   $$-B^{\prime\prime}(\xi)y+D^{\prime\prime}(\xi)>0,\quad\quad y\in\breve{S},\xi\in\mathcal{I}$$

   (12)

   where $\breve{S}$ denotes the interior of $S$. If $S$ is bounded, (12) holds for at least one of endpoints.

3. (iii)

   ${\mathbf{P}}(Y\in S)=1$ and ${\mathbf{E}}(Y|X=x)=A(m(x))$ for each $x\in[0,1]^{d}$.

4. (iv)

   There is a compact subinterval $\mathcal{K}_{0}$ of $\mathcal{I}$ such that the range of $m$ is contained in $\mathcal{K}_{0}$.

The above restrictions on $B(\cdot)$ and $D(\cdot)$ were used in Huang (1998). In fact, we can know from Huang (1998) that many commonly used distributions satisfy these conditions, including normal distribution, Poisson distribution and Bernoulli distribution. Now, let us verify our Assumption 1-5 under this setting.

In particular, Assumption 1 is verified by using Condition (i)-(iii). On the other hand, we choose the Lipchitz constant in Assumption 2 by

Thirdly, the envelop function of $\ell_{2}(x,y)$ can be set by

Since we assume $Y$ is a sub-Gaussian random variable in Assumption 4, thus ${\mathbf{E}}(M_{2}^{2}(x,y))<\infty$ in this case. This indicates Assumption 3 is satisfied. Finally, under conditions (i)-(iv), Lemma 4.1 in Huang (1998) shows that our Assumption 5 holds with $\kappa=2$ and

From (12), the constant $c$ in (13) must be larger than zero. On the other hand, we will see later the above $c$ does not equal to infinity in many cases.

Therefore, those general theoretical results in Section 4 & 5 can be applied in generalized regression. Finally, we need to stress those coefficients in the general results, such as $M_{1}(\beta_{n},\ln n)$ in Theorem 1 and $c$ in (13), are only of polynomial order of $\ln n$ if we choose $\beta_{n}$ properly. Let us give some specific examples.

Examples

1. 1.

   The first example is Gaussian regression, where the conditional distribution $Y|X=x$ follows $N(m(x),1)$. Therefore, $B(x)=x$, $D(x)=\frac{1}{2}x^{2}$, $\mathcal{I}={\mathbb{R}}$ and $S={\mathbb{R}}$. Our goal is to estimate the unknown conditional mean $m(x)$. Now, Conditions (i)-(iii) are satisfied. To satisfy the fourth one, we assume the range of $m$ is contained in a compact set of ${\mathbb{R}}$, denoted by $\mathcal{K}_{0}$. Choose $\beta_{n}\asymp\ln n$. Meanwhile, we can ensure $Y$ is a sub-Gaussian random variable. The constant $c$ in (13) equals to $1$ and those coefficients in general theoretical results are all of polynomial order of $\ln n$, such as $M_{1}(\beta_{n},\ln n)\asymp 2\ln n$.

2. 2.

   The second example is Poisson regression, where the conditional distribution $Y|X=x$ follows $Poisson(\lambda(x))$ with $\lambda(x)>0$. Therefore, $B(x)=-x$, $D(x)=\exp(x)$, $\mathcal{I}={\mathbb{R}}$ and $S=[0,\infty)$. Our goal is to estimate the $\ln n$ transformation of conditional mean, namely $m(x)=\ln\lambda(x)$ in (11), by using Mondrian forest (3). It is not difficult to show Conditions (i)-(iii) are already satisfied. To satisfy the fourth one, we assume the range of $\lambda(x)$ is contained in a compact set of $(0,\infty)$. Thus, $m(x)$ satisfies Assumption (iv). Choose $\beta_{n}\asymp\ln\ln n$. Meanwhile, we can ensure $Y$ satisfies Assumption 4 by using the fact that Poisson distribution is sub-Gaussian. The constant $c$ in (13) equals to $\ln n$ and those coefficients in general theoretical results are also all of polynomial order of $\ln n$, such as $M_{1}(\beta_{n},\ln n)\asymp 2\ln n$.

3. 3.

   The third example is $0-1$ classification, where the conditional distribution $Y|X=x$ follows Bernoulli distribution (taking values in $\{0,1\}$) with ${\mathbf{P}}(Y=1|X=x)=p(x)\in(0,1)$. It is well known that the best classifier is named as Bayes rule,

   $$C^{Bayes}(x)=\left\{\begin{array}[]{lc}1,&p(x)-\frac{1}{2}\geq 0\\ 0,&p(x)-\frac{1}{2}<0.\\ \end{array}\right.$$

   Therefore, the main focus in this problem is how to estimate the conditional probability $p(x)$ well. Here, we use Mondrian forest for the estimation. First, we make a shift of $p(x)$, which means $m(x):=p(x)-\frac{1}{2}\in(-\frac{1}{2},\frac{1}{2})$ is used in (11) instead. By some calculations, $B(x)=\ln(0.5+x)-\ln(0.5-x)$, $D(x)=-\ln(0.5-x)$, $\mathcal{I}=(-0.5,0.5)$ and $S=[0,1]$ in this case. Now, the final goal is to estimate $m(x)$ by using the forest estimator (3). It is not difficult to show Conditions (i)-(iii) are already satisfied. To satisfy the fourth one, we assume the range of $m(x)$ is contained in a compact set of $(-\frac{1}{2},\frac{1}{2})$. Now, choose $\beta_{n}\asymp\frac{1}{2}-(\frac{1}{\ln n})^{\gamma}$ for some $\gamma>0$. Meanwhile, Assumption 4 is satisfied since $Y$ is bounded. The constant $c$ in (13) equals to $(\ln n)^{2\gamma}$ and those coefficients in general theoretical results are also all of polynomial order of $\ln n$, such as $M_{1}(\beta_{n},\ln n)\asymp 2(\ln n)^{\gamma+1}$.