Title: NEURAL REGRESSION TREES

Abstract: Regression-via-Classification (RvC) is the process of converting a regression problem to a classification one. Current approaches for RvC use ad-hoc discretization strategies and are suboptimal. We propose a neural regression tree model for RvC. In this model, we employ a joint optimization framework where we learn optimal discretization thresholds while simultaneously optimizing the features for each node in the tree. We empirically show the validity of our model by testing it on two challenging regression tasks where we establish the state of the art.

1. INTRODUCTION:

One of the most challenging and intensively studied problems in machine learning is regressionpredicting the continuous value of a dependent variable (label) y from the independent variable (covariates) x. The relationship between y ∈ Y and x ∈ X, a regression function f : X → Y, is generally unknown and may not be deterministic. Varied approaches can be used to estimate the map f , such as linear regression Bishop (2006) , nonparametric regression Wasserman (2006) , neural nets Friedman et al. (2001) , etc. Among these approaches, one school of methods is regressionvia-classification (RvC) Weiss & Indurkhya (1995) , in which the continuous dependent variable y is discretized into ordered bins and an estimation y is made by classifying the independent variable x into one of the bins. Such class of methods addresses one issue with standard regression methods: different regions of Y may depend on different subsets of X, and a common statistical estimator of f on the entire Y could have high bias on some regions of Y. Therefore, a separate regression function is preferable for each region of Y.

In this study, we focus on developing the optimal discretization strategy for RvC. For the sake of a concise explanation, we first define the problem clearly. To start with, we define In our case, Y ⊂ R, and a partition on Y effectively converts the continuous-valued variable y into a categorical one C. This process is often termed as discretization Fayyad & Irani (1993) ; Dougherty et al. (1995) . Based on this discretization, a RvC system includes a classifier h : x → {C 1 , . . . , C N } and a regressor r : C i → R. Using this system, a prediction for y is y = r(h(x)).

The key aspect of an RvC system is its method of partition Π. It uses a set of thresholds T := {t 0 , . . . , t N } to determine Π(y) = C n if t n-1 ≤ y ≤ t n . Problems arise as how to set these thresholds. One approach is to set T by prior knowledge, such as equally probable intervals, equal width intervals, k-means clustering, etc. Dougherty et al. (1995) ; Torgo & Gama (1996; 1997) . However, this approach could lead to potential difficulties in defining the optimal partition Fayyad & Irani (1993) , hence the non-ideal performance. For instance, ad-hoc partitions can result in unbalanced partitions that are too easy or too difficult to regress; partitions that are not fine enough can lead to high regression bias.

Therefore, it is necessary to develop strategies to find the optimal discretization of the dependent variable, i.e., to find the optimal thresholds. We propose a top-down tree based approach, which grows a partition tree with each threshold on the node determined by a neural binary classifier, and the value of dependent variable y is predicted at the leaves. We call the resulting model a neural regression tree (NRT). Specifically, we adopt a top-down binary splitting approach to recursively grow the partition tree. To determine the splitting threshold t n for a node n, we use a binary classifier h n : X → {-1, 1} to find the optimal t * n by minimizing the classification error t * n = arg min tn E hn (D n , t n ), where E hn is the classification error of h n , and D n is the data on node n. The number of thresholds N , which determines the number of partitions and hence the depth of the tree, stops increasing when the classification performance saturates. Next, in order to determine the value y for any feature x we only need to find out which leave partition x belongs to following the partition tree, and estimate y using a regression function on that bin.

The benefits of doing so are three-fold: (1) the discretization thresholds T are explicitly optimized to obtain optimal partition; (2) By adapting a top-down binary splitting approach, we reduce the computational complexity, since directly optimizing T is a hard problem as it scales exponentially with N ; (3) the features are adapted to each node by the neural classifier, and hence the model promotes hierarchical representation learning, increasing model interpretability.

To achieve the above, we propose two algorithms, a scanning search algorithm, and a gradient based method, against a loss function for which we call the triviality loss to solve for the discretization thresholds efficiently. To demonstrate the utility of the proposed approach we conduct experiments on a pair of challenging regression tasks: estimating the age and height of speakers from their voices. Experiments show that our model achieves significant performance gain over state-of-the-art baseline models.

2. RELATED WORK:

Regression Trees Tree-structured models have been around for a long time. Among them, the most closely related are the regression trees. Following our terminology, the regression tree can be described as y = r(Π(x)), where the partition is performed on independent variable instead of dependent variable. The first regression tree algorithm was presented by Morgan & Sonquist, where they propose a greedy approach to fit a piecewise constant function by recursively splitting the data into two subsets based on partition on X. The optimal split is a result of minimizing the impurity which defines the homogeneity of the split. This algorithm set the basis for a whole line of research on classification and regression trees. Refined algorithms include CART Breiman et al. (1984) , ID3 Quinlan (1986) , m5 Quinlan et al. (1992), and C4.5 Quinlan (2014) . Recent work combines the tree-structure and neural nets to gain the power of both structure learning and representation learning. Such work include the convolutional decision trees Laptev & Buhmann (2014) , neural decision trees Xiao (2017) ; Balestriero (2017) , adaptive neural trees Tanno et al. (2018) , deep neural decision forests Kontschieder et al. (2015) , and deep regression forests Shen et al. (2017) .

We emphasize that there is a fundamental difference between our approach and the traditional regression tree based approaches: Instead of making the split based on the feature space, our splitting criteria is based on the dependent variables, enabling the features to adapt to the partitions of dependent variables.

Regression via Classification (RvC):

The idea for RvC was presented by Weiss & Indurkhya. Their algorithm was based on k-means clustering to categorize numerical variables. Other conventional approaches Torgo & Gama (1996; 1997) for discretization of continuous values are based on equally probable (EP) or equal width (EW) intervals, where EP creates a set of intervals with same number of elements, while EW divides into intervals of same range. These approaches are ad-hoc. Instead, we propose a discretization strategy to learn the optimal thresholds by improving the neural classifiers.

3. NEURAL REGRESSION TREE:

In this section, we formulate the neural regression tree model for optimal discretization of RvC, and provide algorithms to optimize the model.

3.1. MODEL FORMULATION:

Formally, following the description of RvC in Section 1, a classification rule classifies the data into disjoint bins parameterizes the classifier. Then, a regression rule predicts the value of the dependent variable

h θ : x → {C 0 , • • • , C N }, where C i = Π(y) corresponds to t i-1 ≤ y ≤ t i ,

and θ:

EQUATION

where r :

C i → [t i-1 , t i ]

is any regression function that operates locally on all instances that are assigned to the bin C i .

Alternatively, the classification rule may compute the probability of a data point x being classified into bin

C i , P (C i | x) = h θ (x)

, and the regression rule is given by

EQUATION

Defining an error E(y, y(x)) between the true y and the estimated y(x), our objective is to learn the thresholds {t 0 , . . . , t N } and the parameters {θ 1 , . . . , θ N } such that the expected error is minimized

EQUATION

Note that the number of thresholds N too is a variable that may either be manually set or explicitly optimized. In practice, instead of minimizing the expected error, we will minimize the empirical average error avg(E(y i , y(x i ))) computed over a training set.

However, joint optimization of {t n } and {θ n } is a hard problem as it scales exponentially with n. To solve this problem we recast the RvC problem in terms of a binary classification tree, where each of the nodes in the tree is greedily optimized. The structure of the proposed binary tree is shown in Figure 1 .

We now describe the tree-growing algorithm. For notational convenience the nodes have been numbered such that for any two nodes n 1 and n 2 , if n 1 < n 2 , n 1 occurs either to the left of n 2 or above it in the tree. Each node n in the tree has an associated threshold t n , which is used to partition the data into its two children n and n (we will assume w.l.o.g. that n < n ). A datum (x, y) is assigned to the "left" child n if y < t n , and to the "right" child n otherwise. The actual partitions of the dependent variable are the leaves of the tree. To partition the data, each node carries a classifier h θn : x → {n , n }, which assigns any instance with features x to one of n or n . In our instantiation of this model, the classifier h θn is a neural classifier that not only classifies the features but also adapts and refines the features to each node.

Given an entire tree along with all of its parameters and an input x, we can compute the a posteriori probability of the partitions (i.e. the leaves) as follows. For any leaf l, let l 0 , • • • , l p represent the chain of nodes from root to leaf, where l 0 is the root and l p = l is the leaf itself. The a posteriori probability of the leaf is given by P

(l | x) = p r=1 P (l r | l r-1 , x), where each P (l r | l r-1 , x) is

given by the neural classifier on node l r-1 . Substitution into (2) yields the final regressed value of the dependent variable

EQUATION

where r(l), in our setting, is simply the mean value of the leaf bin. Other options include the center of gravity of the leaf bin, using a regression function, etc.

3.2. LEARNING THE TREE:

We learn the tree in a greedy manner, optimizing each node individually. The procedure to optimize an individual node n is as follows. Let D n = {(x i , y i )} represent the set of training instances arriving at node n. Let n and n be the children induced through threshold t n . In principle, to locally optimize n, we must minimize the average regression error E(D n ; t n , θ n ) = avg (E(y, y n (x))) between the true response values y and the estimated response y n (x) computed using only the subtree with its root at n. In practice, E(D n ; t n , θ n ) is not computable, since the subtree at n is as yet unknown. Instead, we will approximate it through the classification accuracy of the classifier at n, with safeguards to ensure that the resultant classification is not trivial and permits useful regression.

Let y(t n ) = sign(y -t n ) be a binary indicator function that indicates if an instance (x, y) must be assigned to child n or n . Let E(y(t n ), h θn (x)) be a quantifier of the classification error (which is the binary cross entropy loss in our case) for any instance (x, y). We define the classification loss at node n as

EQUATION

The classification loss E θn,tn cannot be directly minimized w.r.t t n , since this can lead to trivial solutions, e.g. setting t n to an extreme value such that all data are assigned to a single class. While such a setting would result in perfect classification, it would contribute little to the regression. To prevent such solutions, we include a triviality penalty T that attempts to ensure that the tree remains balanced in terms of number of instances at each node. For our purpose, we define the triviality penalty at any node as the entropy of the distribution of instances over the partition induced by t n (other triviality penalties such as the Gini index Breiman et al. (1984) may also apply though)

EQUATION

where

p(t n ) = (x,y)∈Dn (1 + y(t n )) 2|D n | .

The overall optimization of node n is performed as

EQUATION

where λ ∈ (0, 1) is used to assign the relative importance of the two components of the loss.

In the optimization of (7), the loss function depends on t n through y(t n ), which is a discrete function of t n . Hence, we have two possible ways of optimizing (7). In the first, we can scan through all possible values of t n to select the one that results in the minimal loss. Alternatively, a faster gradient-descent approach is obtained by making the objective differentiable w.r.t. t n .

Here the discrete function sign(y -t n ) is replaced by a smooth, differentiable relaxation: y(t n ) = 0.5(tanh(β(y -t n )) + 1), where β controls the steepness of the function and must typically be set to a large value (β = 10 in our settings). The triviality penalty is also redefined (to be differentiable w.r.t. t n ) as the proximity to the median T (t n ) = t nmedian(y | (x, y) ∈ D n ) 2 , since the median is the minimizer of (6). We use coordinate descent to optimize the resultant loss.

Once optimized, the data D n at n are partitioned into n and n according to the threshold t * n , and the process is recursed down the tree. Algorithm 1 describes the entire training algorithm. The growth of the tree may be continued until the regression performance on a held-out set saturates.

Input: D:

Parameter :{t n }, {θ n } Output: {t * n }, {θ * n } Initialize t = {}, θ = {}, D 1 ← D; Function BuildTree(D n ) Initialize t n , θ n ; t * n , θ * n ← NeuralClassifier(D n , t n , θ n ); t ← t * n , θ ← θ * n ; D n , D n ← Partition(D n , t * n ) ; for D n in {D n , D n } do if D n is pure then continue; else BuildTree(D n ) end end

BuildTree(D 1 ); Algorithm 1: Learning neural regression tree. The tree is built recursively. For each node, it adapts and classifies the features, and partitions the data based on classification result.

4. EXPERIMENTS:

We consider two regression tasks in the domain of speaker profiling-age estimation and height estimation from voice. The two tasks are generally considered two of the challenging tasks in the speech literature Kim et al. (2007) ; Metze et al. (2007) ; Li et al. (2010) ; Dobry et al. (2011) ; Lee & Kwak (2012) ; Bahari et al. (2014) ; Barkana & Zhou (2015) ; Poorjam et al. (2015) ; Fu & Huang (2008) .

We compare our model with (1) a regression baseline using the support vector regression (SVR) Basak et al. (2007) , and (2) a regression tree baseline using classification and regression tree (CART) Breiman et al. (1984) . Furthermore, in order to show the effectiveness of the "neural part" of our NRT model, we further compare our neural regression tree with a third baseline (3) regression tree with the support vector machine (SVM-RT).

4.1. DATA:

To promote a fair comparison, we select two well-established public datasets in the speech community. For age estimation, we use the Fisher English corpus Cieri et al. (2004) . It consists of a 2-channel conversational telephone speech for 11, 971 speakers, comprising of a total of 23, 283 recordings. After removing 58 speakers with no age specified, we are left with 11, 913 speakers with 5, 100 male and 4, 813 female speakers. To the best of our knowledge, the Fisher corpus is the largest English language database that includes the speaker age information to be used for the age estimation task. The division of the data for the age estimation task is shown in Table 1 . The division is made such that there is no overlap of speakers and all age groups are represented across the splits. Furthermore, Figure 2 shows the age distribution of the database for the three splits (train, development, and test) in relation to the Table 1 . For height estimation, we use the NIST speaker recognition evaluation (SRE) 2008 corpus Kajarekar et al. (2009) . We only have heights for 384 male speakers and 651 female speakers from it. Because of data scarcity issues, we evaluate this task using cross-validation. Table 2 and Figure 3 show the statistics for the NIST-SRE8 database. 

4.2. MODEL:

The proposed neural regression tree is a binary tree with neural classification models as discussed in Section 3.1. The specifications for our model and the baseline models are shown in Table 3 . The NRT is composed of a collection of 3-layer ReLU neural networks. The kernels, regularizations and parameters for SVRs and SVMs are obtained from experimenting on development set. As a measure of the performance of our models and the baseline models on age and height estimation, we use the mean absolute error (MAE) and the root mean squared error (RMSE). The results are summarized in Table 4 . For both age and height estimation, we see that the proposed neural regression tree generally outperforms other baselines in both MAE and RMSE, except that for height task, the neural regression tree has slightly higher RMSE than SVR, indicating higher variance. This is reasonable as our NRT does not directly optimize on the mean square error. Bagging or forest mechanisms may be used to reduce the variance. Furthermore, with the neural classifier in NRT being replaced by a SVM classifier (SVM-RT), we obtain higher error than NRT, implying the effectiveness of the neural part of the NRT as it enables the features to refine with each partition and adapt to each node. Nevertheless, SVM-RT still yields smaller MAE values than SVR and CART, hence strengthening our hypothesis that the our model can find optimal discretization thresholds for optimal dependent variable discretization even without the use of a neural network.

To test the significance of the results, we further conduct paired-wise statistical significance tests. We hypothesize that the errors achieved from our NRT method are significantly smaller than the closest competitor SVR. Paired t-test for SVR v.s. SVM-RT and SVM-RT v.s. NRT yield p-values less than 2.2 × 10 -16 , indicating strong significance of the improvement. Similar results are obtained for height experiments as well. Hence we validate the significant performance improvement of our NRT method on estimating ages and heights over the baseline methods.

4.4. NODE-BASED ERROR ANALYSIS:

The hierarchical nature of our formulation allows us to analyze our model on every level and every node of the tree in terms of its classification and regression error. In our evaluation for the speaker age estimation task, we noticed that the regression error for the younger speakers was lower than the error in the case of older speakers. In other words, our model was able to discriminate better between younger speakers. This is in agreement with the fact that the vocal characteristics of humans undergo noticeable changes during earlier ages, and then relatively stabilize for a certain age interval Stathopoulos et al. (2011) . Figure 4 shows the per-level MAE for female and male speakers. The nodes represent the age thresholds used as splitting criteria at each level. The edges represent the regression error. The inherent structural properties of our model not only improve the overall regression performance as we saw in the previous section, but in the case of age estimation, also model the real world phenomenon. This is visible in 4 where the regression error can be seen to increase from left to right for both female and male speakers (except the left most nodes where the behavior does not follow possibly due to data scarcity issues). 

4.5. LIMITATIONS:

We acknowledge that our model might not be ubiquitous in its utility across all regression tasks. Our hypothesis is that it works well with tasks that can benefit from a partition based formulation. We empirically show that for two such tasks above. However, in future we would like to test our model for other standard regression tasks. Furthermore, because our model formulation inherits its properties from the regression-via-classification (RvC) framework, the objective function is optimized to reduce the classification error rather than the regression error. This limits us in our ability to directly compare our model to other regression methods. In future, we intend to explore ways to directly minimize the regression error while employing the RvC framework.

5. CONCLUSIONS:

In this paper, we proposed a neural regression tree for optimal discretization of dependent variables in regression-by-classification tasks. It targeted the two difficulties in regression-by-classification: finding optimal discretization thresholds and selecting optimal set of features. We developed a discretization strategy by recursive binary partition based on the optimality of neural classifiers. Furthermore, for each partition node on the tree, it was able to locally optimize features to be more discriminative. In addition, we proposed a scan method and a gradient method to optimize the tree.

The proposed neural regression tree outperformed baselines in age and height estimation experiments, and demonstrated significant improvements.

:



Figures and Tables:

Partition A partition Π on a set Y is Π(Y) = {C 1 , . . . , C N } satisfying N i=1 C i = Yand C i s are disjoint. When acting on a y ∈ Y, Π(y) := C j subjected to y ∈ C j .

Figure 1: Illustration of neural regression tree.

Figure 2: Age Distribution (in percentages) for male (Top) and female (Bottom) speakers for the fisher database for train (Left), development (Center) and test (Right) set.

Figure 3: Age Distribution (in percentages) for male (Left) and female (Right) speakers for the NIST-SRE8 database.



Table content: <table><tr><td/><td colspan="2">: Fisher Dataset Partitions</td></tr><tr><td/><td colspan="2"># of Speakers / Utterances</td></tr><tr><td/><td>Male</td><td>Female</td></tr><tr><td colspan="3">Train 3,100 / 28,178 4,813 / 45,041</td></tr><tr><td>Dev</td><td>1,000 / 9,860</td><td>1,000 / 9,587</td></tr><tr><td>Test</td><td>1,000 / 9,813</td><td>1,000 / 9,799</td></tr></table>



Table content: <table/>



Table content: <table><tr><td/><td colspan="2">: Model Specifications</td></tr><tr><td>Model</td><td colspan="2">Specification</td></tr><tr><td/><td>Age</td><td>Height</td></tr><tr><td/><td>Linear: (400, 1000)</td><td/></tr><tr><td>NRT</td><td>Linear: (1000, 1000) Linear: (1000, 1) Nonlin.: ReLU</td><td>(Same as Age with input dim. of 600)</td></tr><tr><td/><td>Optim.: Adam (lr 0.001)</td><td/></tr><tr><td>SVM-RT</td><td>Kernel: RBF Regul.: 1 Optim.: Scan (Sec. 3.2)</td><td>(Same as Age with linear kernel)</td></tr><tr><td>SVR</td><td>Kernel: RBF Regul.: 1</td><td>Kernel: Linear Regul.: 1</td></tr><tr><td>CART</td><td>Criteri.: MSE</td><td>Criteri.: MSE</td></tr><tr><td>4.3 RESULTS</td><td/><td/></tr></table>

Performance evaluation of neural regression tree and baselines.

Table content: <table><tr><td>Task</td><td>Dataset</td><td>Methods</td><td/><td>Male</td><td colspan="2">Female</td></tr><tr><td/><td/><td/><td>MAE</td><td>RMSE</td><td>MAE</td><td>RMSE</td></tr><tr><td/><td/><td>SVR</td><td>9.22</td><td>12.03</td><td>8.75</td><td>11.35</td></tr><tr><td>Age</td><td>Fisher</td><td>CART</td><td>11.73</td><td>15.22</td><td>10.75</td><td>13.97</td></tr><tr><td/><td/><td>SVM-RT</td><td>8.83</td><td>11.47</td><td>8.61</td><td>11.17</td></tr><tr><td/><td/><td>NRT</td><td>7.20</td><td>9.02</td><td>6.81</td><td>8.53</td></tr><tr><td/><td/><td>SVR</td><td>6.27</td><td>6.98</td><td>5.24</td><td>5.77</td></tr><tr><td>Height</td><td>SRE</td><td>CART</td><td>8.01</td><td>9.34</td><td>7.08</td><td>8.46</td></tr><tr><td/><td/><td>SVM-RT</td><td>5.70</td><td>7.07</td><td>4.85</td><td>6.22</td></tr><tr><td/><td/><td>NRT</td><td>5.43</td><td>6.40</td><td>4.27</td><td>6.07</td></tr></table>

Regression error (MAE) for different age groups for female (Left) and male (Right) for the task of speaker age estimation.

Table content: <table><tr><td/><td/><td/><td colspan="2">43</td><td/><td/><td/><td/><td/><td/><td colspan="2">40</td><td/><td/><td/></tr><tr><td/><td/><td>5.4</td><td/><td colspan="2">8.9</td><td/><td/><td/><td/><td>5.57</td><td/><td colspan="2">9.77</td><td/><td/></tr><tr><td/><td>31</td><td/><td/><td/><td colspan="2">55</td><td/><td/><td colspan="2">29</td><td/><td/><td>50</td><td/><td/></tr><tr><td colspan="2">5.79</td><td>5.14</td><td/><td colspan="2">5.83</td><td>12.23</td><td/><td colspan="2">5.91</td><td>5.24</td><td/><td colspan="2">6.92</td><td>12.44</td><td/></tr><tr><td>24</td><td/><td>37</td><td/><td>49</td><td/><td>61</td><td/><td>23</td><td/><td>35</td><td/><td>45</td><td/><td>56</td><td/></tr><tr><td>6.9</td><td>4.9</td><td>5.3</td><td>4.96</td><td>5.02</td><td>6.63</td><td>8.97</td><td>15.64</td><td>7.25</td><td>4.81</td><td>4.89</td><td>5.67</td><td>6.51</td><td>7.32</td><td>8.9</td><td>15.61</td></tr><tr><td colspan="2">Figure 4:</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2019):
 This paper presents a new approach to regression via classification problem utilizing a hybrid model between a neural network and a decision tree. The paper is very well written and easy to follow. It presents results on two very similar regression tasks and claims state of the art performance on both. The paper however does not motivate its contributions sufficiently, and does not provide enough experimental results to justify their method. The authors could significantly improve the paper by spending more time motivating their work. For example, it is unclear why RvC is the best strategy for the tasks they study and what other tasks one should approach from a RvC standpoint. The paper would also be significantly more compelling if the strategy was applied to more varied tasks. Furthermore the two baseline models used are 11 and 34 years old respectively and i do not believe they represent a thorough review of the potential approaches to this problem. Significant work could also be done to explore the effect of using different neural network structures for the NRT - in this paper only a fairly simple 3 layer architecture is used. Section 4.4 is interesting and i believe the paper would be improved if more time was spent exploring the explanability of this new proposed model. Finally the scan method mentioned in the conclusion could have more emphasis placed on it in the text. Over all the paper is well written and easy to follow but is limited by its lack of well detailed motivation and insufficient baselines and applied tasks.