9.2.1 Notation

We first introduce a labeling for the tree nodes following [23]. The root node is labeled with an empty binary string λ and assuming that a node has a label n, where n is a binary string, we label its upper and lower children as n1 and n0, respectively. Here we emphasize that a string can only take its letters from the binary alphabet $\{0,1\}$, where 0 refers to the lower child and 1 refers to the upper child of a node. We also introduce another concept, i.e., the definition of the prefix of a string. We say that a string $n^{\prime }=q_1^{\prime }\dots q_{l^{\prime }}^{\prime }$ is a prefix to string $n=q_1\dots q_l$ if $l^{\prime }⩽l$ and $q_i^{\prime }=q_i$ for all $i=1,\dots ,l^{\prime }$ and the empty string λ is a prefix to all strings. Let $\mathcal{P}(n)$ represent all prefixes to the string n, i.e., $\mathcal{P}(n)\triangleq \{n_0,\dots ,n_l\}$, where $l\triangleq l(n)$ is the length of the string n, $n_i$ is the string with $l(n_i)=i$ and $n_0=\lambda$ is the empty string, such that the first i letters of the string n form the string $n_i$ for $i=0,\dots ,l$.

For a given SOT of depth D, we let ${\mathcal{N}}_D$ denote all nodes defined on this SOT and ${\mathcal{L}}_D$ denote all leaf nodes defined on this SOT. We also let ${\beta }_D$ denote the number of partitions defined on this SOT. This yields the recursion ${\beta }_{j+1}={\beta }_j^2+1$ for all $j⩾1$, with the base case ${\beta }_0=1$. For a given partition k, we let ${\mathcal{M}}_k$ denote the set of all nodes in this partition.

For a node $n\in {\mathcal{N}}_D$ (defined on the SOT of depth D), we define ${\mathcal{S}}_D(n)\triangleq \{\acute{n}\in {\mathcal{N}}_D|\mathcal{P}(\acute{n})=n\}$ as the set of all nodes of the SOT of depth D, whose set of prefixes includes node n.

For a node $n\in {\mathcal{N}}_D$ (defined on the SOT of depth D) with length $l(n)⩾1$, the total number of partitions that contain n can be found by the following recursion:

${\gamma }_d(l(n))\triangleq \prod _{j=1}^{l(n)}{\beta }_{d-j}.$

For the case where $l(n)=0$ (i.e., for $n=\lambda$), one can clearly observe that there exists only one partition containing λ, therefore ${\gamma }_d(0)=1$.

For two nodes $n,\acute{n}\in {\mathcal{N}}_D$ (defined on the SOT of depth D), we let $\rho (n,\acute{n})$ denote the number of partitions that contain both n and $\acute{n}$. Trivially, if $\acute{n}=n$, then $\rho (n,\acute{n})={\gamma }_d(l(n))$. If $n\ne \acute{n}$, then letting $\overline{n}$ denote the longest prefix to both n and $\acute{n}$, i.e., the longest string in $\mathcal{P}(n)\cap \mathcal{P}(\acute{n})$, we obtain

$\rho (n,\acute{n})\triangleq \{\begin{array}{cc}{\gamma }_d(l(n)),\hfill & \text{if }n=\acute{n,}\hfill \\ \frac{{\gamma }_d(l(n)){\gamma }_{d-l(\overline{n})-1}(l(\acute{n})-l(\overline{n})-1)}{{\beta }_{d-l(\overline{n})-1}},\hfill & \text{if }n\notin \mathcal{P}(\acute{n})\cup {\mathcal{S}}_D(\acute{n}),\hfill \\ 0,\hfill & \text{otherwise.}\hfill \end{array}$

Since $l(\overline{n})+1⩽l(n)$ and $l(\overline{n})+1⩽l(\acute{n})$ from the definition of the SOT, we naturally have $\rho (n,\acute{n})=\rho (\acute{n},n)$.

9.2.2 Construction of the Algorithm

For each node n on the SOT, we define a node predictor

${\hat{d}}_{t,n}={\mathit{v}}_{t,n}^T{\mathit{x}}_t,$

whose parameter ${\mathit{v}}_{t,n}$ is updated using the online gradient descent algorithm. We also define a separator function for each node p on the SOT except the leaf nodes (note that leaf nodes do not have any children) using the sigmoid function

$s_{t,n}=\frac{1}{1+\exp ({\mathit{\varphi }}_{t,n}^T{\mathit{x}}_t)},$

where ${\mathit{\varphi }}_{t,n}$ is the normal to the separation plane. We then define the prediction of any partition according to the hierarchical structure of the SOT as the weighted sum of the prediction of the nodes in that partition, where the weighting is determined by the separator functions of the nodes between the leaf node and the root node. In particular, the prediction of the kth partition at time t is defined as follows:

${\hat{d}}_t^{(k)}=\sum _{n\in {\mathcal{M}}_k}\left({\hat{d}}_{t,n}\prod _{i=0}^{l(n)-1}{s}_{t,n_i}^{q_i}\right),$

where $n_i\in \mathcal{P}(n)$ is the prefix to string n with length $i-1$, $q_i$ is the ith letter of the string n, i.e., $n_{i+1}=n_i{q}_i$, and finally $s_{t,n_i}^{q_i}$ denotes the value of the separator function at node $n_i$ such that

$s_{t,n_i}^{q_i}\triangleq \{\begin{array}{cc}{s}_{t,n_i},\hfill & \text{if }{q}_i=0,\hfill \\ 1-s_{t,n_i},\hfill & \text{otherwise,}\hfill \end{array}$

with $s_{t,n_i}$ defined as in (9.3). We emphasize that we dropped the n dependency of $q_i$ and $n_i$ to simplify notation. Using these definitions, we can construct the final estimate of our algorithm as

${\hat{d}}_t=\sum _{k\in {\beta }_D}{w}_t^{(k)}{\hat{d}}_t^{(k)},$

where $w_t^{(k)}$ represents the weight of partition k at time t.

Having found a method to combine the predictions of all partitions to generate the final prediction of the algorithm, we next aim to obtain a low-complexity representation since there are $\mathcal{O}({1.5}^{2^D})$ different partitions defined on the SOT and (9.6) requires a storage and computational complexity of $\mathcal{O}({1.5}^{2^D})$. To this end, we denote the product terms in (9.4) as follows:

${\hat{\delta }}_{t,n}\triangleq {\hat{d}}_{t,n}\prod _{i=0}^{l(n)-1}{s}_{t,n_i}^{q_i},$

where ${\hat{\delta }}_{t,n}$ can be viewed as the estimate of the node n at time t. Then (9.4) can be rewritten as follows:

${\hat{d}}_t^{(k)}=\sum _{p\in {\mathcal{M}}_k}{\hat{\delta }}_{t,n}.$

Since we now have a compact form to represent the tree and the outputs of each partition, we next introduce a method to calculate the combination weights of $\mathcal{O}({1.5}^{2^D})$ partitions in a simplified manner. For this, we assign a particular linear weight to each node. We denote the weight of node n at time t as $w_{t,n}$ and then define the weight of the kth partition as the sum of the weights of its nodes, i.e.,

$w_t^{(k)}=\sum _{n\in {\mathcal{M}}_k}{w}_{t,n},$

for all $k\in \{1,\dots ,{\beta }_D\}$. Since we use online gradient descent to update the weight of each partition, the weight of partition k is recursively updated as

$w_{t+1}^{(k)}=w_t^{(k)}+{\mu }_t{e}_t{\hat{d}}_t^{(k)}.$

This yields the following recursive update on the node weights:

$w_{t+1,n}=w_{t,n}+{\mu }_t{e}_t{\hat{\delta }}_{t,n},$

where ${\hat{\delta }}_{t,n}$ is defined as in (9.7). This result implies that instead of managing $\mathcal{O}({1.5}^{2^D})$ memory locations and making $\mathcal{O}({1.5}^{2^D})$ calculations, only keeping track of the weights of every node is sufficient and the number of nodes in a depth-D model is $|{\mathcal{N}}_D|=2^{D+1}-1$. Therefore, we can reduce the storage and computational complexity from $\mathcal{O}({1.5}^{2^D})$ to $\mathcal{O}(2^D)$ by performing the update in (9.8) for all $n\in {\mathcal{N}}_D$.

Using these node predictors and weights, we construct the final estimate of our algorithm as follows:

${\hat{d}}_t=\sum _{k=1}^{{\beta }_d}\left\{\left(\sum _{n\in {\mathcal{M}}_k}{w}_{t,n}\right)\left(\sum _{n\in {\mathcal{M}}_k}{\hat{\delta }}_{t,n}\right)\right\}.$

Here, we observe that for arbitrary two nodes $n,\acute{n}\in {\mathcal{N}}_d$, the product $w_{t,n}{\hat{\delta }}_{t,\acute{n}}$ appears $\rho (n,\acute{n})$ times in ${\hat{d}}_t$ (cf. (9.1)). Hence, the combination weight of the estimate of the node n at time t can be calculated as follows:

${\kappa }_{t,n}=\sum _{\acute{n}\in {\mathcal{N}}_d}\rho (n,\acute{n})w_{t,\acute{n}}.$

Using the combination weight (9.9), we obtain the final estimate of our algorithm as follows:

${\hat{d}}_t=\sum _{n\in {\mathcal{N}}_D}{\kappa }_{t,n}{\hat{\delta }}_{t,n}.$

Note that (9.10) is equal to (9.6) with a storage and computational complexity of $\mathcal{O}(4^D)$ instead of $\mathcal{O}({1.5}^{2^D})$.

As we derived all the update rules for the node weights and the parameters of the individual node predictors, what remains is to provide an update scheme for the separator functions. To this end, we use the online gradient descent update

${\mathit{\varphi }}_{t+1,n}={\mathit{\varphi }}_{t,n}-\frac{1}{2}{\eta }_t\mathrm{\nabla }{e}_t^2({\mathit{\varphi }}_{t,n}),$

for all nodes $n\in {\mathcal{N}}_D\setminus {\mathcal{L}}_D$, where ${\eta }_t$ is the learning rate of the algorithm and $\mathrm{\nabla }{e}_t^2({\mathit{\varphi }}_{t,n})$ is the derivative of $e_t^2({\mathit{\varphi }}_{t,n})$ with respect to ${\mathit{\varphi }}_{t,n}$. After some algebra, we obtain

$\begin{array}{cc}\hfill {\mathit{\varphi }}_{t+1,n}& ={\mathit{\varphi }}_{t,n}+{\eta }_t{e}_t\frac{\partial {\hat{d}}_t}{\partial s_{t,n}}\frac{\partial s_{t,n}}{\partial {\mathit{\varphi }}_{t,n}}\hfill \\ \hfill & ={\mathit{\varphi }}_{t,n}+{\eta }_t{e}_t\left\{\sum _{\acute{n}\in {\mathcal{N}}_D}{\kappa }_{t,\acute{n}}\frac{\partial {\hat{\delta }}_{t,\acute{n}}}{\partial s_{t,n}}\right\}\frac{\partial s_{t,n}}{\partial {\mathit{\varphi }}_{t,n}}\hfill \\ \hfill & ={\mathit{\varphi }}_{t,n}+{\eta }_t{e}_t\left\{\sum _{q=0}^1\sum _{\acute{n}\in {\mathcal{S}}_D(nq)}{(-1)}^q{\kappa }_{t,\acute{n}}\frac{{\hat{\delta }}_{t,\acute{n}}}{s_{t,n}^q}\right\}\frac{\partial s_{t,n}}{\partial {\mathit{\varphi }}_{t,n}},\hfill \end{array}$

where we use the logistic regression classifier as our separator function, i.e., $s_{t,n}={(1+\exp ({\mathit{x}}_t^T{\mathit{\varphi }}_{t,n}))}^{-1}$. Therefore, we have

$\begin{array}{cc}\hfill \frac{\partial s_{t,n}}{\partial {\mathit{\varphi }}_{t,n}}& =-{(1+\exp ({\mathit{x}}_t^T{\mathit{\varphi }}_{t,n}))}^{-2}\exp ({\mathit{x}}_t^T{\mathit{\varphi }}_{t,n}){\mathit{x}}_t\hfill \\ \hfill & =-s_{t,n}(1-s_{t,n}){\mathit{x}}_t.\hfill \end{array}$

We emphasize that other separator functions can also be used in a similar way by simply calculating the gradient with respect to the extended direction vector and plugging in (9.12) and (9.13). From (9.13), we observe that $\mathrm{\nabla }{e}_t^2({\mathit{\varphi }}_{t,n})$ includes the product of $s_{t,n}$ and $1-s_{t,n}$ terms; hence, in order not to slow down the learning rate of our algorithm, we restrict $s^{+}⩽s_t⩽1-s^{+}$ for some $0<s^{+}<0.5$. In accordance with this restriction, we define the separator functions as follows:

$s_t=s^{+}+\frac{1-2s^{+}}{1+e^{{\mathit{x}}_t^T{\mathit{\varphi }}_t}}.$

According to the update rule in (9.12), the computational complexity of the introduced algorithm results in $\mathcal{O}(p{4}^d)$. This concludes the construction of the algorithm and a pseudocode is given in Algorithm 1.

9.2.3 Convergence of the Algorithm

For Algorithm 1, we have the following convergence guarantee, which implies that our regressor (given in Algorithm 1) asymptotically achieves the performance of the best linear combination of the $\mathcal{O}({1.5}^{2^D})$ different adaptive models that can be represented using a depth-D tree with a computational complexity $\mathcal{O}(p{4}^D)$. While constructing the algorithm, we refrain from any statistical assumptions on the underlying data, and our algorithm works for any sequence of ${\left\{d_t\right\}}_{t⩾1}$ with an arbitrary length of n. Furthermore, one can use this algorithm to learn the region boundaries and then feed this information to the first algorithm to reduce computational complexity.

Proof of this theorem can be found in Appendix 9.A.1.

9.3.1 Construction of the Algorithm

Using the notations described in Section 9.2.1, the output of a partition classifier $k\in \{1,\dots ,{\beta }_D\}$ is constructed as follows. Without loss of generality, suppose that the feature ${\mathit{x}}_t$ has fallen into the region represented by the leaf node $n\in {\mathcal{L}}_D$. Then ${\mathit{x}}_t$ is contained in the nodes $n_0,\dots ,n_D$, where $n_d$ is the i letter prefix of n, i.e., $n_D=n$ and $n_0=\lambda$. For example, if node $n_d$ is contained in partition k, then one can simply set $f_t^{(k)}({\mathit{x}}_t)=f_{t,n_d}({\mathit{x}}_t)$. Instead of making a hard selection, we allow an error margin for the classification output $f_{t,n_d}({\mathit{x}}_t)$ in order to be able to update the region boundaries later in the proof. To achieve this, for each node contained in partition k, we define a parameter called path probability to measure the contribution of each leaf node to the classification task at time t. This parameter is equal to the multiplication of the separator functions of the nodes from the respective node to the root node, which represents the probability that ${\mathit{x}}_t$ should be classified using the region classifier of node $n_d$. This path probability (similar to the node predictor definition in (9.7)) is defined as

$P_{t,n_d}({\mathit{x}}_t)\triangleq \prod _{i=0}^{d-1}{s}_{t,n_i}^{q_{i+1}}({\mathit{x}}_t),$

where $p_{t,n_i}^{q_{i+1}}(\cdot )$ represents the value of the partitioning function corresponding to node $n_i$ towards the $q_{i+1}$ direction as in (9.5). We consider that the classification output of node $n_d$ can be trusted with a probability of $P_{t,n_d}({\mathit{x}}_t)$. This and the other probabilities in our development are independently defined for ease of exposition and gaining intuition, i.e., these probabilities are not related to the unknown data statistics in any way and they definitely cannot be regarded as certain assumptions on the data. Indeed, we do not take any assumptions about the data source.

Intuitively, the path probability is low when the feature vector is close to the region boundaries; hence we may consider to classify that feature vector by another node classifier (e.g., the classifier of the sibling node). Using these path probabilities, we aim to update the region boundaries by learning whether an efficient node classifier is used to classify ${\mathit{x}}_t$, instead of directly assigning ${\mathit{x}}_t$ to node $n_d$ and lose a significant degree of freedom. To this end, we define the final output of each node classifier according to a Bernoulli random variable with outcomes $\{-f_{t,n_d}({\mathit{x}}_t),f_{t,n_d}({\mathit{x}}_t)\}$, where the probability of the latter outcome is $P_{t,n_d}({\mathit{x}}_t)$. Although the final classification output of node $n_d$ is generated according to this Bernoulli random variable, we continue to call $f_{t,n_d}({\mathit{x}}_t)$ the final classification output of node $n_d$, with an abuse of notation. Then the classification output of the partition classifier is set to $f_t^{(k)}({\mathit{x}}_t)=f_{t,n_d}({\mathit{x}}_t)$.

Before constructing the SOT classifier, we first introduce certain definitions. Let the instantaneous empirical loss of the proposed classifier $f_t$ at time t be denoted by ${\ell }_t(f_t)\triangleq {\mathbb{1}}_{\{f_t({\mathit{x}}_t)\ne y_t\}}$. Then the expected empirical loss of this classifier over a sequence of length T can be found by

$L_T(f_t)=E[\sum _{t=1}^T{\ell }_t(f_t)],$

with the expectation taken with respect to the randomization parameters of the classifier $f_t$. We also define the effective region of each node $n_d$ at time t as follows: ${\mathcal{R}}_{t,n_d}\triangleq \{\mathit{x}:P_{t,n_d}(\mathit{x})⩾{(0.5)}^d\}$. According to the aforementioned structure of partition classifiers, the node $n_d$ classifies an instance ${\mathit{x}}_t$ only if ${\mathit{x}}_t\in {\mathcal{R}}_{t,n_d}$. Therefore, the time accumulated empirical loss of any node n during the data stream is given by

$L_{T,n}\triangleq \sum _{t⩽T:{\left\{{\mathit{x}}_t\right\}}_{t⩾1}\in {\mathcal{R}}_{t,n}}{\ell }_t(f_{t,n}).$

Similarly, the time accumulated empirical loss of a partition classifier k is $L_T^{(k)}\triangleq {\sum }_{n\in {\mathcal{M}}_k}{L}_{T,n}$.

We then use a mixture-of-experts approach to achieve the performance of the best partition classifier that minimizes the accumulated classification error. To this end, we set the final classification output of our algorithm as $f_t({\mathit{x}}_t)=f_t^{(k)}$ with probability $w_t^{(k)}$, where

$w_t^{(k)}=\frac{1}{Z_{t-1}}{2}^{-J(k)}\exp (-b{L}_{t-1}^{(k)}),$

$b⩾0$ is a constant controlling the learning rate of the algorithm, $J(k)⩽2|\mathcal{L}(k)|-1$ represents the number of bits required to code the partition k (which satisfies ${\sum }_{k=1}^{{\beta }_D}J(k)=1$) and $Z_t={\sum }_{k=1}^{{\beta }_D}{2}^{-J(k)}\exp (-b{L}_t^{(k)})$ is the normalization factor.

Although this randomized method can be used as the SOT classifier, in its current form, it requires a computational complexity $\mathcal{O}({1.5}^{2^D}p)$ since the randomization $w_t^{(k)}$ is performed over the set $\{1,\dots ,{\beta }_D\}$ and ${\beta }_D\approx {1.5}^{2^D}$. However, the set of all possible classification outputs of these partitions has a cardinality as small as $D+1$ since ${\mathit{x}}_t\in {\mathcal{R}}_{t,n_D}$ for the corresponding leaf node $n_D$ (in which ${\mathit{x}}_t$ is included) and $f_t^{(k)}=f_{t,n_d}$ for some $d=0,\dots ,D$, $\forall k\in \{1,\dots ,{\beta }_D\}$. Hence, evaluating all the partition classifiers in k at the instance ${\mathit{x}}_t$ to produce $f_t({\mathit{x}}_t)$ is unnecessary. In fact, the computational complexity for producing $f_t({\mathit{x}}_t)$ can be reduced from $\mathcal{O}({1.5}^{2^D}p)$ to $\mathcal{O}(Dp)$ by performing the exact same randomization over $f_{t,n_d}$'s using the new set of weights $w_{t,n_d}$, which can be straightforwardly derived as follows:

$w_{t,n_d}=\sum _{k=1}^{{\beta }_D}{w}_t^{(k)}{\mathbb{1}}_{f_t^{(k)}({\mathit{x}}_t)=f_{t,n_d}({\mathit{x}}_t)}.$

To efficiently calculate (9.21) with complexity $\mathcal{O}(Dp)$, we consider the universal coding scheme and let

$M_{t,n}\triangleq \{\begin{array}{cc}\exp (-b{L}_{t,n}),\hfill & \text{ if}\mathit{n}\text{has depth}\mathit{D}\text{,}\hfill \\ \frac{1}{2}[M_{t,n0}{M}_{t,n1}+\exp (-b{L}_{t,n})],\hfill & \text{ otherwise}\hfill \end{array}$

for any node n and observe that we have $M_{t,\lambda }=Z_t$ [23]. Therefore, we can use the recursion (9.22) to obtain the denominator of the randomization probabilities $w_t^{(k)}$. To efficiently calculate the numerator of (9.21), we introduce another intermediate parameter as follows. Letting $n_d^{\prime }$ denote the sibling of node $n_d$, we recursively define

${\kappa }_{t,n_d}\triangleq \{\begin{array}{cc}\frac{1}{2},\hfill & \text{ if }d=0\hfill \\ \frac{1}{2}{M}_{t-1,n_d^{\prime }}{\kappa }_{t,n_{d-1}},\hfill & \text{ if }0<d<D\hfill \\ M_{t-1,n_d^{\prime }}{\kappa }_{t,n_{d-1}},\hfill & \text{ if }d=D\hfill \end{array},$

$\forall d\in \{0,\dots ,D\}$, where ${\mathit{x}}_t\in {\mathcal{R}}_{t,n_D}$. Using the intermediate parameters in (9.22) and (9.23), it can be shown that we have

$w_{t,n_d}=\frac{{\kappa }_{t,n_d}\exp (-b{L}_{t,n_d})}{M_{t,\lambda }}.$

Hence, we obtain the final output of the algorithm as $f_t({\mathit{x}}_t)=f_{t,n_d}({\mathit{x}}_t)$ with probability $w_{t,n_d}$, where $d\in \{0,\dots ,D\}$ (i.e., with a computational complexity $\mathcal{O}(D)$).

We then use the final output of the introduced algorithm and update the region boundaries of the tree (i.e., organize the tree) to minimize the final classification error. To this end, we minimize the loss $E[{\ell }_t(f_t)]=E[{\mathbb{1}}_{\{f_t({\mathit{x}}_t)\ne y_t\}}]=\frac{1}{4}E\left[{(y_t-f_t({\mathit{x}}_t))}^2\right]$ with respect to the region boundary parameters, i.e., we use the stochastic gradient descent method as follows:

$\begin{array}{cc}\hfill {\mathit{\varphi }}_{t+1,n_d}& ={\mathit{\varphi }}_{t,n_d}-\eta \mathrm{\nabla }E[{\ell }_t(f_t)]\hfill \\ \hfill & ={\mathit{\varphi }}_{t,n_d}-{(-1)}^{q_{d+1}}\eta (y_t-f_t({\mathit{x}}_t))s_{t,n_d}^{q_{d+1}^{\prime }}({\mathit{x}}_t)[\sum _{i=d+1}^D{f}_{t,n_i}({\mathit{x}}_t)]{\mathit{x}}_t,\hfill \end{array}$

$\forall d\in \{0,\dots ,D-1\}$, where η denotes the learning rate of the algorithm and $q_{d+1}^{\prime }$ represents the complementary letter to $q_{d+1}$ from the binary alphabet $\{0,1\}$. Defining a new intermediate variable

${\pi }_{t,n_d}\triangleq \{\begin{array}{cc}{f}_{t,n_d}({\mathit{x}}_t),\hfill & \text{ if }d=D-1\text{,}\hfill \\ {\pi }_{t,n_{d+1}}+f_{t,n_d}({\mathit{x}}_t),\hfill & \text{ if }d<D-1\text{,}\hfill \end{array}$

one can perform the update in (9.25) with a computational complexity $\mathcal{O}(p)$ for each node $n_d$, where $d\in \{0,\dots ,D-1\}$, resulting in an overall computational complexity of $\mathcal{O}(Dp)$ as follows:

${\mathit{\varphi }}_{t+1,n_d}={\mathit{\varphi }}_{t,n_d}-{(-1)}^{m_{d+1}}\eta (y_t-f_t({\mathit{x}}_t)){\pi }_{t,n_d}{s}_{t,n_d}^{q_{d+1}^{\prime }}({\mathit{x}}_t){\mathit{x}}_t.$

This concludes the construction of the algorithm and the pseudocode of the SOT classifier can be found in Algorithm 2.

9.3.2 Convergence of the Algorithm

In this section, we illustrate that the performance of Algorithm 2 is asymptotically as good as the best partition classifier such that, as $T\to \infty$, we have $R_T(f_t;f_t^{(k)})\to 0$. Hence, Algorithm 2 asymptotically achieves the performance of the best partition classifier among $\mathcal{O}({1.5}^{2^D})$ different classifiers that can be represented using the SOT of depth D with a significantly reduced computational complexity of $\mathcal{O}(Dp)$ without any statistical assumptions on data.

Proof of this theorem can be found in Appendix 9.A.2.

9.4.1 Numerical Results for Regression Problems

Throughout this section, “SOTR” represents the self-organizing tree regressor defined in Algorithm 1, “CTW” represents the context tree weighting algorithm of [16], “OBR” represents the optimal batch regressor, “VF” represents the truncated Volterra filter [1], “LF” represents the simple linear filter, “B-SAF” and “CR-SAF” represent the Beizer and the Catmull–Rom spline adaptive filter of [2], respectively, and “FNF” and “EMFNF” represent the Fourier and even mirror Fourier nonlinear filter of [3], respectively. Finally, “GKR” represents the Gaussian-kernel regressor and it is constructed using n node regressors, say ${\hat{d}}_{t,1},\dots ,{\hat{d}}_{t,n}$, and a fixed Gaussian mixture weighting (that is selected according to the underlying sequence in hindsight), giving

${\hat{d}}_t=\sum _{i=1}^{n}f({\mathit{x}}_t;{\mathit{\mu }}_i,{\mathbf{\Sigma }}_i){\hat{d}}_{t,i},$

where ${\hat{d}}_{t,i}={\mathit{v}}_{t,i}^T{\mathit{x}}_t$ and

$f({\mathit{x}}_t;{\mathit{\mu }}_i,{\mathbf{\Sigma }}_i)\triangleq \frac{1}{2\pi \sqrt{\left|{\mathbf{\Sigma }}_i\right|}}{e}^{-\frac{1}{2}{({\mathit{x}}_t-{\mathit{\mu }}_i)}^T{\mathbf{\Sigma }}_i^{-1}({\mathit{x}}_t-{\mathit{\mu }}_i)},$

for all $i=1,\dots ,n$.

For a fair performance comparison, in the corresponding experiments in Subsection 9.4.1.2, the desired data and the regressor vectors are normalized between $[-1,1]$ since the satisfactory performance of several algorithms requires the knowledge on the upper bounds (such as the B-SAF and the CR-SAF) and some require these upper bounds to be between $[-1,1]$ (such as the FNF and the EMFNF). Moreover, in the corresponding experiments in Subsection 9.4.1.1, the desired data and the regressor vectors are normalized between $[-1,1]$ for the VF, the FNF and the EMFNF algorithms due to the aforementioned reason. The regression errors of these algorithms are then scaled back to their original values for a fair comparison.

Considering the illustrated examples in the respective papers [2,3,16], the orders of the FNF and the EMFNF are set to 3 for the experiments in Subsection 9.4.1.1 and 2 for the experiments in Subsection 9.4.1.2. The order of the VF is set to 2 for all experiments. Similarly, the depth of the trees for the SOTR and CTW algorithms is set to 2 for all experiments. For these tree-based algorithms, the feature space is initially partitioned by the direction vectors ${\mathit{\varphi }}_{t,n}={[{\varphi }_{t,n}^{(1)},\dots ,{\varphi }_{t,n}^{(p)}]}^T$ for all nodes $n\in {\mathcal{N}}_D\setminus {\mathcal{L}}_D$, where ${\varphi }_{t,n}^{(i)}=-1$ if $i\equiv l(n)(\mathrm{mod}D)$, e.g., when $D=p=2$, we have the four quadrants as the four leaf nodes of the tree. Finally, we use cubic B-SAF and CR-SAF algorithms, whose number of knots are set to 21 for all experiments. We emphasize that both these parameters and the learning rates of these algorithms are selected to give equal rates of performance and convergence.

9.4.1.1 Mismatched Partitions

In this subsection, we consider the case where the desired data is generated by a piece-wise linear model that mismatches with the initial partitioning of the tree-based algorithms. Specifically, the desired signal is generated by the following piece-wise linear model:

$d_t=\{\begin{array}{cc}{\mathit{w}}^T{\mathit{x}}_t+{\pi }_t,\hfill & \text{if }{\mathit{\varphi }}_0^T{\mathit{x}}_t⩾0.5\text{ and }{\mathit{\varphi }}_1^T{\mathit{x}}_t⩾1,\hfill \\ -{\mathit{w}}^T{\mathit{x}}_t+{\pi }_t,\hfill & \text{if }{\mathit{\varphi }}_0^T{\mathit{x}}_t⩾0.5\text{ and }{\mathit{\varphi }}_1^T{\mathit{x}}_t<1,\hfill \\ -{\mathit{w}}^T{\mathit{x}}_t+{\pi }_t,\hfill & \text{if }{\mathit{\varphi }}_0^T{\mathit{x}}_t<0.5\text{ and }{\mathit{\varphi }}_2^T{\mathit{x}}_t⩾-1,\hfill \\ {\mathit{w}}^T{\mathit{x}}_t+{\pi }_t,\hfill & \text{if }{\mathit{\varphi }}_0^T{\mathit{x}}_t<0.5\text{ and }{\mathit{\varphi }}_2^T{\mathit{x}}_t<-1,\hfill \end{array}$

(9.29)

where $\mathit{w}={[1,1]}^T$, ${\mathit{\varphi }}_0={[4,-1]}^T$, ${\mathit{\varphi }}_1={[1,1]}^T$, ${\mathit{\varphi }}_2={[1,2]}^T$, ${\mathit{x}}_t={[x_{1,t},x_{2,t}]}^T$, ${\pi }_t$ is a sample function from a zero mean white Gaussian process with variance 0.1 and $x_{1,t}$ and $x_{2,t}$ are sample functions of a jointly Gaussian process of mean ${[0,0]}^T$ and variance ${\mathit{I}}_2$. The learning rates are set to 0.005 for SOTR and CTW, 0.1 for FNF, 0.025 for B-SAF and CR-SAF, 0.05 for EMFNF and VF. Moreover, in order to match the underlying partition, the mass points of GKR are set to ${\mathit{\mu }}_1={[1.4565,1.0203]}^T$, ${\mathit{\mu }}_2={[0.6203,-0.4565]}^T$, ${\mathit{\mu }}_3={[-0.5013,0.5903]}^T$ and ${\mathit{\mu }}_4={[-1.0903,-1.0013]}^T$ with the same covariance matrix as in the previous example.

Fig. 9.3 shows the normalized time accumulated regression error of the proposed algorithms. We emphasize that the SOTR algorithm achieves a better error performance compared to its competitors. Comparing the performances of the SOTR and CTW algorithms, we observe that the CTW algorithm fails to accurately predict the desired data, whereas the SOTR algorithm learns the underlying partitioning of the data, which significantly improves the performance of the SOTR. This illustrates the importance of the initial partitioning of the regressor space for tree-based algorithms to yield a satisfactory performance.

In particular, the CTW algorithm converges to the best batch regressor having the predetermined leaf nodes (i.e., the best regressor having the four quadrants of two-dimensional space as its leaf nodes). However that regressor is suboptimal since the underlying data is generated using another constellation; hence its time accumulated regression error is always lower bounded by $\mathcal{O}(1)$ compared to the global optimal regressor. The SOTR algorithm, on the other hand, adapts its region boundaries and captures the underlying unevenly rotated and shifted regressor space partitioning perfectly. Fig. 9.4 shows how our algorithm updates its separator functions and illustrates the nonlinear modeling power of SOTs.

9.4.1.2 Chaotic Signals

In this subsection, we illustrate the performance of the SOTR algorithm when estimating chaotic data generated by the Henon map and the Lorenz attractor [31].

First, we consider a zero mean sequence generated by the Henon map, a chaotic process given by

$d_t=1-\zeta d_{t-1}^2+\eta d_{t-2},$

(9.30)

known to exhibit chaotic behavior for the values of $\zeta =1.4$ and $\eta =0.3$. The desired data at time t is denoted as $d_t$ whereas the extended regressor vector is ${\mathit{x}}_t={[d_{t-1},d_{t-2},1]}^T$, i.e., we consider a prediction framework. The learning rate is set to 0.025 for B-SAF and CR-SAF, whereas it is set to 0.05 for the rest.

Fig. 9.5 (left plot) shows the normalized regression error performance of the proposed algorithms. One can observe that the algorithms whose basis functions do not include the necessary quadratic terms and the algorithms that rely on a fixed regressor space partitioning yield unsatisfactory performance. On the other hand, VF can capture the salient characteristics of this chaotic process since its order is set to 2. Similarly, FNF can also learn the desired data since its basis functions can well approximate the chaotic process. The SOTR algorithm, however, uses a piece-wise linear modeling and still achieves asymptotically the same performance as the VF algorithm, while outperforming the FNF algorithm.

Second, we consider the chaotic signal set generated using the Lorenz attractor [31] that is defined by the following three discrete-time equations:

$\begin{array}{cc}\hfill x_t& =x_{t-1}+(\sigma (y-x))dt,\hfill \\ \hfill y_t& =y_{t-1}+(x_{t-1}(\rho -z_{t-1})-y_{t-1})dt,\hfill \\ \hfill z_t& =z_{t-1}+(x_{t-1}{y}_{t-1}-\beta z_{t-1})dt,\hfill \end{array}$

(9.31)

where we set $dt=0.01$, $\rho =28$, $\sigma =10$ and $\beta =8/3$ to generate the well-known chaotic solution of the Lorenz attractor. In the experiment, $x_t$ is selected as the desired data and the two-dimensional region represented by $y_t,z_t$ is set as the regressor space, that is, we try to estimate $x_t$ with respect to $y_t$ and $z_t$. The learning rates are set to 0.01 for all algorithms.

Fig. 9.5 (right plot) illustrates the nonlinear modeling power of the SOTR algorithm even when estimating a highly nonlinear chaotic signal set. As can be observed from Fig. 9.5, the SOTR algorithm significantly outperforms its competitors and achieves a superior error performance since it tunes its region boundaries to the optimal partitioning of the regressor space, whereas the performances of the other algorithms directly rely on the initial selection of the basis functions and/or tree structures and partitioning.

9.4.2 Numerical Results for Classification Problems

9.4.2.2 Nonstationary Data: Concept Change/Drift

In this section, we apply the SOTC algorithm to nonstationary data, where there might be continuous or sudden/abrupt changes in the source statistics, i.e., concept change. Since the SOTC algorithm processes data in a sequential manner, we choose the Dynamically Weighted Majority (DWM) algorithm (DWM) [35] with Perceptron (DWM-P) or naive Bayes (DWM-N) experts for the comparison, since the DWM algorithm is also an online algorithm. Although the batch algorithms do not truly fit into our framework, we still devise an online version of the tree-based local space partitioning algorithm [24] (which also learns the space partitioning and the classifier using the coordinate ascent approach) using a sliding-window approach and abbreviate it as the WLSP algorithm. For the DWM method, which allows the addition and removal of experts during the stream, we set the initial number of experts to 1, where the maximum number of experts is bounded by 100. For the WLSP method, we use a window size of 100. The parameters for these compared methods are set as in their original proposals.

We run these methods on the BMC dataset (1200 instances, Fig. 9.6), where a sudden/abrupt concept change is obtained by rotating the feature vectors (clock-wise around the origin) ${180}^{\circ }$ after the 600th instance. This is effectively equivalent to flipping the label of the feature vectors; hence the resulting dataset is denoted as BMC-F. For a continuous concept drift, we rotate each feature vector ${180}^{\circ }/1200={0.15}^{\circ }$ starting from the beginning; the resulting dataset is denoted as BMC-C. In Fig. 9.6, we present the classification errors for the compared methods averaged over 1000 trials. At each 10th instance, we test the algorithms with 1200 instances drawn from the active set of statistics (active concept).

Since the BMC dataset is non-Gaussian with strongly nonlinear class separations, the DWM method does not perform well on the BMC-F data. For instance, DWM-P operates with an error rate fluctuating around 0.48–0.49 (random guess). This results since the performance of the DWM method is directly dependent on the expert success and we observe that both base learners (Perceptron or the naive Bayes) fail due to the high separation complexity in the BMC-F data. On the other hand, the WLSP method quickly converges to steady state, however it is also asymptotically outperformed by the SOTC algorithm in both experiments. Increasing the window size is clearly expected to boost the performance of WLSP, however at the expense of an increased computational complexity. It is already significantly slower than the SOTC method even when the window size is 100 (for a more detailed comparison, see Table 9.2). The performance of the WLSP method is significantly worse on the BMC-C data set compared to the BMC-F data set, since in the former scenario, WLSP is trained with batch data of a continuous mixture of concepts in the sliding windows. Under this continuous concept drift, the SOTC method always (not only asymptotically as in the case of the BMC-F data set) performs better than the WLSP method. Hence, the sliding-window approach is sensitive to the continuous drift. Our discussion about the DWM method on the concept change data (BMC-F) remains valid in the case of the concept drift (BMC-C) as well. In these experiments, the power of self-organizing trees is obvious as the SOTC algorithm almost always outperforms the TNC algorithm. We also observe from Table 9.2 that the SOTC algorithm is computationally very efficient and the cost of region updates (compared to the TNC algorithm) does not increase the computational complexity of the algorithm significantly.

Table 9.2

Running times (in seconds) of the compared methods when processing the BMC data set on a daily-use machine (Intel(R) Core(TM) i5-3317U CPU @ 1.70 GHz with 4 GB memory)

PER	OZAB	OGB	OSB	TNC	DWM-P	DWM-N	WLSP	SOTC
0.06	12.90	3.57	3.91	0.43	2.06	6.91	68.40	0.62