Year: 2018

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.

heading: 1 INTRODUCTION
text: One of the most challenging and intensively studied problems in machine learning is regression— predicting 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
Partition A partition Π on a set Y is
Π(Y) = {C1, . . . , CN} satisfying ⋃N i=1 Ci = Y and Cis are disjoint. When acting on a y ∈ Y, Π(y) := Cj subjected to y ∈ Cj .
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 7→ {C1, . . . , CN} and a regressor r : Ci 7→ 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 := {t0, . . . , tN} to determine Π(y) = Cn if tn−1 ≤ y ≤ tn. 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 tn for a node n, we use a binary classifier hn : X→ {−1, 1} to find the optimal t∗n by minimizing the classification error t ∗ n = arg mintn Ehn(Dn, tn), where Ehn is the classification error of hn, and Dn 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.

heading: 2 RELATED WORK
text: 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.

heading: 3 NEURAL REGRESSION TREE
text: In this section, we formulate the neural regression tree model for optimal discretization of RvC, and provide algorithms to optimize the model.

heading: 3.1 MODEL FORMULATION
text: Formally, following the description of RvC in Section 1, a classification rule classifies the data into disjoint bins hθ : x 7→ {C0, · · · , CN}, where Ci = Π(y) corresponds to ti−1 ≤ y ≤ ti, and θ
parameterizes the classifier. Then, a regression rule predicts the value of the dependent variable
ŷ(x) = r(hθ(x)), (1)
where r : Ci 7→ [ti−1, ti] is any regression function that operates locally on all instances that are assigned to the bin Ci.
Alternatively, the classification rule may compute the probability of a data point x being classified into bin Ci, P (Ci | x) = hθ(x), and the regression rule is given by
ŷ(x) = ECi [r(hθ(x))] = N∑ i=0 P (Ci | x)r(Ci). (2)
Defining an error E(y, ŷ(x)) between the true y and the estimated ŷ(x), our objective is to learn the thresholds {t0, . . . , tN} and the parameters {θ1, . . . , θN} such that the expected error is minimized
{t∗n}, {θ∗n} ←− arg min t,θ Ex [E(y, ŷ(x))] . (3)
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(yi, ŷ(xi))) computed over a training set. However, joint optimization of {tn} 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 n1 and n2, if n1 < n2, n1 occurs either to the left of n2 or above it in the tree. Each node n in the tree has an associated threshold tn, 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 < tn, 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 7→ {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 l0, · · · , lp represent the chain of nodes from root to leaf, where l0 is the root and lp = l is the leaf itself. The a posteriori probability of the leaf is given by P (l | x) = ∏p r=1 P (lr | lr−1, x), where each P (lr | lr−1, x) is
given by the neural classifier on node lr−1. Substitution into (2) yields the final regressed value of the dependent variable
ŷ(x) = ∑
l∈leaves
P (l | x)r(l), (4)
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.

heading: 3.2 LEARNING THE TREE
text: We learn the tree in a greedy manner, optimizing each node individually. The procedure to optimize an individual node n is as follows. Let Dn = {(xi, yi)} represent the set of training instances arriving at node n. Let n′ and n′′ be the children induced through threshold tn. In principle, to locally optimize n, we must minimize the average regression error E(Dn; tn, θ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(Dn; tn, θ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(tn) = sign(y − tn) be a binary indicator function that indicates if an instance (x, y) must be assigned to child n′ or n′′. Let E(y(tn), 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
Eθn,tn = 1
|Dn| E(y(tn), hθn(x)). (5)
The classification loss Eθn,tn cannot be directly minimized w.r.t tn, since this can lead to trivial solutions, e.g. setting tn 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 tn (other triviality penalties such as the Gini index Breiman et al. (1984) may also apply though)
T (tn) = −p(tn) log p(tn)− (1− p(tn)) log(1− p(tn)), (6)
where
p(tn) =
∑ (x,y)∈Dn(1 + y(tn))
2|Dn| .
The overall optimization of node n is performed as
θ∗n, t ∗ n = arg min
θn,tn
λEθn,tn + (1− λ)T (tn), (7)
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 tn through y(tn), which is a discrete function of tn. Hence, we have two possible ways of optimizing (7). In the first, we can scan through all possible values of tn 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. tn. Here the discrete function sign(y − tn) is replaced by a smooth, differentiable relaxation: y(tn) = 0.5(tanh(β(y − tn)) + 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. tn) as the proximity to the median T (tn) = ‖tn−median(y | (x, y) ∈ Dn)‖2, since the median is the minimizer of (6). We use coordinate descent to optimize the resultant loss.
Once optimized, the data Dn 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 :{tn}, {θn} Output: {t∗n}, {θ∗n} Initialize t = {}, θ = {}, D1 ← D; Function BuildTree(Dn)
Initialize tn, θn; t∗n, θ ∗ n ← NeuralClassifier(Dn, tn, θn); t← t∗n, θ ← θ∗n; Dn′ ,Dn′′ ← Partition(Dn, t∗n) ; for Dn in {Dn′ ,Dn′′} do
if Dn is pure then continue; else BuildTree(Dn)
end end
BuildTree(D1); 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.

heading: 4 EXPERIMENTS
text: 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).

heading: 4.1 DATA
text: 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.
Since the recordings for both datasets have plenty of silences and the silences do not contribute to the information gain, Gaussian based voice activity detection (VAD) is performed on the recordings. Then, the resulting recordings are segmented to 1-minute segments.
To properly represent the speech signals, we adopt one of the most effective and well-studied representations, the i-vectors Dehak et al. (2011). I-vectors are statistical low-dimensional representations over the distributions of spectral features, and are commonly used in state-of-the-art speaker recognition systems Sadjadi et al. (2016) and age estimation systems Shivakumar et al. (2014); Grzybowska & Kacprzak (2016). Respectively, 400-dimensional and 600-dimensional i-vectors are extracted for Fisher and SRE datasets using the state-of-the-art speaker identification system Dhamyal et al. (2018)

heading: 4.2 MODEL
text: 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.

heading: 4.3 RESULTS
text: 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.

heading: 4.4 NODE-BASED ERROR ANALYSIS
text: 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).

heading: 4.5 LIMITATIONS
text: 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.

heading: 5 CONCLUSIONS
text: 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.

Review summaries:
The paper presents a novel supervised-learning method for regression using decision trees and neural nets. The core idea is based on a 90s technique called "regression via classification" by first apply discretization of target response y by some clustering, and apply any "classification" to those discretized values as class labels. Because real-valued y is one-dimensional and ordered, discretization means setting up any thresholds to give N-partitions of training {y_i}s. The proposed method tries to jointly learn these thresholds as well as node splitters of decision trees using neural nets. Because each node splitters are given by neural nets here, probability outputs for binary classification are also available. Regarding these probabilities as probabilistic splitting at each node, response y weighted by the path probabilities to leaves is the final prediction. The learning is in a greedy manner as in standard tree learning because exact joint learning is computationally hard.  Experiments on speaker profiling illustrate the performance improvements against standard nonlinear regression such as SVR and regression trees.