Deep Ordinal Regression Based on Data Relationship for Small Datasets

1 Introduction

The ordinal regression is a supervised learning problem, which aims at predicting the rank label of an input vector. The natural order of the labels (e.g., 1,2,3) indicates the order of the ranks. This problem is different from the multi-class classification problem as there is an ordinal relationship between the categories. It is also different from the metric regression problem because the target values to be predicted are discrete and the distances between different categories are not defined.

From the problem setting, obviously, the most important task of ordinal regression methods is to model the ordinal relationship between the categories. Recently, a number of machine learning approaches have been proposed for ordinal regression. The main difference between these approaches is the way to make use of the ordinal information. For example, the max-margin based approaches [Shashua and Levin, 2002][Chu and Keerthi, 2007] predict contiguous boundaries to split the ordinal classes and the projection based approaches [Liu et al., 2011][Tian and Chen, 2015] map instances to a new space preserving the ordinal relationship between classes. However, few of existing works extract and represent the ordinal relationship from instances directly. Herbrich et al. (1999) [Herbrich et al., 1999] proposed to explore the relationship between instances by using feature pairs and the ordinal relationship is represented by whose rank is greater in a pair. However, this pairwise representation cannot describe the ordinal relationship among instances completely. For example, it cannot distinguish the difference between pairs of instances from rank 1 and rank 2 and those from rank 1 and rank 3. Another limitation of this method [Herbrich et al., 1999] is that the feature pairs are constructed highly based on prior knowledge. The strategy of the pairwise feature construction greatly influences the performance of the method and thus it is task dependent.

Being able to automatically extract high-level features from raw data, deep neural networks (DNNs), such as convolutional neural networks (CNNs), have attracted great attention in these several years and performed very well on many classification problems. However, instances are inputted individually into DNNs. To our best knowledge, there is no any existing work employing DNNs to extract and represent high-level features describing relationship among data instances for ordinal regression problems. Generally speaking, to train a deep neural network, a large training dataset is necessary. Using deep learning on small datasets is challenging, but many real-world ordinal regression problems are in fact small data problems. For example, in computer-aided diagnostic problems, datasets of rare disease grading and tumor staging are usually small as collecting data for these diseases is difficult, expensive and invasive. Even for more common diseases, the datasets are not large, because of privacy. In this paper, representing instances relationship and small dataset problems are two challenges that we are targeting.

This paper proposes to use triplets whose elements are from different ranks as samples to explore the ordinal data relationship. The intuition is simple: if a method can predict that the rank of an input x is greater than k - 1 and smaller than k + 1, then the rank label of x will be k. Therefore, the proposed approach transforms a m-rank ordinal regression problem to m binary classification problems with triplets as inputs. And the k-th classifier answers the question: "Is the rank of x greater than k - 1 and smaller than k + 1?" One of state-of-the-art ordinal regression methods RED-SVM [Lin and Li, 2012] trained a binary classifier to answer "Is the rank of x greater than k or not?" Comparing with RED-SVM, the proposed question in this paper is more precise so that it is straightforward to recover the rank label from the answers. In the proposed approach, DNNs are adopted to extract high-level features from the triplets, and for each rank k, a separate DNN is trained for the corresponding binary classification problem. Because the distance between every two adjacent ranks can be different, separate DNNs are used instead of one multi-class CNN. A significant benefit of the proposed approach is data augmentation. If the size of a training dataset is n, the number of triplets used for training the CNNs will be O(n3 ). Therefore, the proposed approach makes deep learning on small datasets possible.

The rest of this paper is organized as follows. Section 2 reviews the literature of ordinal regression. Section 3 describes the proposed deep ordinal regression framework. Section 4 reports the experimental results. Section 5 gives some conclusive remarks.

2 RelatedWork

Comprehensive reviews of ordinal regression can be found in [McCullagh and Nelder, 1989], [O'Connell, 2006] and [Gutierrez et al., 2016]. Gutierrez et al.'s survey [Gutierrez et al., 2016] is the most recent one, which classifies ordinal regression approaches into three categories: na¨ıve, binary decomposition and threshold approaches. The na¨ıve approaches adapt nominal classification or metric regression methods to solve the ordinal regression problem. Binary decomposition separates the ordinal target labels to binary ones, which are then estimated by a single or multiple models [Herbrich et al., 1999][Frank and Hall, 2001]. Threshold approaches assume that there is a latent function mapping the instances to a real line, and the categories of the instances are intervals on the line. The natural order of interval boundaries on the real line represents the ordinal relationship between categories [Chu and Keerthi, 2007][Chu and Ghahramani, 2005].

However, from the data point of view, most of existing approaches are pointwise. Their input spaces are the raw feature spaces and they estimate weights or parameters for instances inputted separately instead of pairs or lists of instances. For example, SVOR [Chu and Keerthi, 2007], a SVM based method, estimates the weight w for input vectors x and boundaries b, and the decision criteria is that the rank of x is k if and only if wT x ∈ [bk-1, bk], where bk is the boundary separating rank k and rank k + 1. A neural network based approach [Cheng et al., 2008] employed a standard feedforward neural network with m outputs for the mrank ordinal regression problem. Also the network weights w are estimated for input vectors x and the decision function f(x) = ∑Hj=1 βjBj(x,wj), where H is the number of hidden nodes, wj is the input weight vector for the j-th hidden node, Bj(x,wj) is a basis function, and βj is the j-th output weight. A probabilistic method GPOR [Chu and Ghahramani, 2005] uses Gaussian Process to estimate the parameters θ for the conditional probability p(k|x,D, θ), where k is a rank label and D is a training set. Then the rank of x is predicted as k with the maximum conditional probability. In all above pointwise methods, the parameters are learned from individual data points, and therefore, the relationship between instances is not explored explicitly. The method proposed by Herbrich et al. (1999) [Herbrich et al., 1999] can be viewed as a pairwise method. Input vectors are paired up first, for example (xi, xj), and then their difference xi - xj as a feature vector is inputted into a standard SVM and the label is sign(yi -yj), where yi is the rank of xi and sign(·) is a sign function. However, to form the feature vector for a pair by subtracting one element from another is ad-hoc. And sign(·) operation is only able to indicate whose rank is greater, but cannot show how far between the ranks of the two elements. Furthermore, they rely on prior knowledge to design effective features.

In the last decade, although deep learning has achieved great success on classification, there are very few works to adopt DNNs to ordinal regression problems. Niu et al. (2016) [Niu et al., 2016] have recently adopted CNN for age estimation and claimed that they are the first one to address ordinal regression problems by using CNN. Their method is a pointwise approach. The training instances are inputted to CNN individually and the relationships between input instances are not considered. And as traditional deep learning methods, their method is more applicable for large scale datasets.

3 AConvolutional Neural Network for Ordinal Regression

An ordinal regression problem with m ranks denoted by Y = {1, 2, · · · ,m} is considered, where the natural order of the numbers in Y indicates the order of the ranks. A training set with labeled instances T = {(xi, yi)|xi ∈ X, yi ∈ Y } is given, where X is the input space. The target is to predict the rank yt ∈ Y of an input xt ∈ X. In the rest of this section, the outline of the proposed approach will be provided first, and then its key components, including a pre-trained CNN and a decoding scheme will be presented.

3.1 The Proposed Approach

The proposed deep neural network for ordinal regression is to predict rank label by answering the questions: "Is k - 1 < yt < k + 1 true?" for all k ∈ Y . Obviously, if the answer is "yes" for a certain k, then the predicted rank label yt will be k. In the proposed approach, for each rank k in Y , a separate binary classifier is trained to answer the above question. Since convolutional neural networks are used in the current implementation, the proposed method is named convolutional neural network for ordinal regression (CNNOR). Algorithm 1 gives the pseudo code of the CNNOR. It consists of three steps: pre-training (line 1), training (line 2-6) and decoding (line 7-11). Given a training set T with labeled instances and a testing point xt, the goal of CNNOR is to predict the rank of xt being most likely between which two ranks. In other words, CNNOR aims to predict whether a triplet (xi, xt, xj) is consistent in order, where "consistent" means xi ∈ Xk-1, xt ∈ Xk, and xj ∈ Xk+1. Therefore, Algorithm 1 starts from training CNNreg which aims to make the ranks of xi and xj in order first for all possible triplets (xi, xt, xj).

Algorithm 1 Pseudo code of CNNOR

Input: Training set T = {(xi, yi)|xi ∈ X, yi ∈ Y } where X is an input space, Y = {1, 2, · · · ,m}, and a test point xt ∈ X.

Output: yt, the predicted rank of xt.

• 1: Train CNNreg on T by minimizing Eq. 1.
• 2: Split T into m subsets X1, · · · ,Xm with Xk = {xi|(xi, yi) ∈ T, yi = k} for k = 1, · · · ,m.
• 3: for k = 1 to mdo
• 4: Construct positive and negative triplet setsD+ k andDk using Eq. 2. (Denote Dk =D+ k ∪Dk )
• 5: Train CNNk on Dk with weights initialized from the pre-trained CNNreg model.
• 6: end for
• 7: for k = 1 to mdo
• 8: Construct d test triplets Dtk by Eq. 3.
• 9: Input Dtk to CNNk and assign pk = ck d where ck is the number of positive predictions for rank k.
• 10: end for
• 11: return yt = argmaxk(pk).

Let φ(x) denote the output of the network CNNreg which is an one-dimensional real value, and x be an instance. The objective of CNNreg is to learn a function φ(·) which maps xi and xj to a real line such that φ(xi) < φ(xj) if yi < yj. Hence, we construct the training set with lists (x1i , x2i , · · · , xki , · · · , xmi ) as instances, where xki is from rank k. The loss function is defined by Eq. 1,

where xki is from the k-th rank, m is the number of ranks and n is the size of training set (i.e., the number of lists in the training set), g is a hyperparameter which controls the margin of mapped value between adjacent ranks. Eq. 1 is named as Ordinal Loss, which calculates the total error of all pairs of instances if their orders are incorrect or their margin is smaller than g. Figure 1 illustrates the Ordinal Loss for a 3-rank ordinal regression problem. The axis is the real line which is the range of φ(·). The red circles are the set of points mapped from instances of the rank 1, i.e., {φ(xi)|yi = 1}. The green crosses are the mapped points from the rank 2, and the blue stars are those from the rank 3. g in Eq. 1 is the expected margin between two adjacent ranks as shown in Figure 1. The Ordinal Loss only counts the errors from pairs of adjacent ranks, e.g., e1, e2 and e3. But other errors such as e4 are not considered explicitly, because if both (φ(x1), φ(x2)) and (φ(x2), φ(x3))) are in order, it can be inferred that (φ(x1), φ(x3))) are also in order. In other words, when e2 is minimized, e4 is minimized implicitly.

Then, the next step of Algorithm 1 is to learn a separate CNN for each rank to extract high level features describing ordinal relationship. For each rank k, a new training set with triplets as instances is derived. In line 2 of Algorithm 1, the training set T is split into m subsets X1, · · · ,Xm according to the rank labels. All the instances in the subset Xk have the same rank label which is k. The new training set Dk is derived as Eq. 2:

D+ k is a positive training set which includes triplets with three elements from ranks k - 1, k and k + 1 and the negative training set Dk includes the triplets whose middle elements are from other ranks and the other two elements are from the ranks k - 1 and k + 1. Because there is no previous rank for rank 1, the training set is formed by pairs (xp, xj) where xj ∈ X2. The classifier for rank 1 aims to decide whether the rank of xi is smaller than xj. Similarly, the training samples for rank m is the pairs (xi, xp) where xi ∈ Xm-1. Based on the derived training set, CNNk is fine-tuned from the pretrained CNNreg in line 5 of Algorithm 1. Each CNNk has a binary output, indicating whether the input is consistent in order or not.

In the testing phase, as shown in line 7-11, given a testing point xt, the test triplets are formed for each CNNk according to Eq. 3.

For each rank k, d pairs of xi and xj are randomly selected from Xk-1 and Xk+1 and they are constructed as triplets with the testing point xt. The decision for the rank label of xt i.e, yt is made by majority voting. Each classifier k predicts how many triplets (ck) of the d inputs are consistent in order respect to rank k, and the percentage ck d indicates the probability that xt belongs to rank k. Finally, the prediction of yt is assigned to the rank k with maximum probability. It should be pointed out that the proposed approach produces a set of

(a) The architecture of CNNreg

(b) The architecture of CNNk

Figure 2: The architecture of CNNOR for a 5-rank problem.

testing instances for one testing point. Through reusing training data, it increases both training and testing data to overcome the weaknesses of traditional deep learning for small dataset problems. Increasing the size of the testing set is not always an issue because of the advancement of hardware and no real-time requirements in some applications e.g., healthcare.

3.2 The Architecture of CNNOR

For a m-rank ordinal regression problem, CNNOR includes one CNNreg and m CNNs, each of which is a binary classifier for one rank. Figure 2 shows the architecture of CNNreg for a 5-rank ordinal regression problem and the network CNNk for the rank k. The input of CNNreg is a list (x1, · · · , xm) which consists of m images for m-rank ordinal regression problem. Each image xi in (x1, · · · , xm) is inputted into one of the networks, and all the m networks share the same weights. All the networks in CNNreg have one output neuron, and the output value of the i-th network represents φ(xi). All the m outputs are inputted to the Ordinal Loss layer to minimize the loss function in Eq. 1. At each iterations of training, the error of the loss layer is back propagated to all networks in CNNreg.

Once the well-trained CNNreg is obtained, its weights are used to initialize the weights of the networks in CNNk. As shown in Figure 2b, the input of CNNk is a triplet (xi, xk, xj), which consists of three images. Each of the three images is inputted to one of the networks denoted as Gi, Gk and Gj in Figure 2b, and all the three networks share the same weights. CNNk with k = 1 (k = m) in Figure 2b only has Gk and Gj (Gi). The layers and the parameters of the networks in CNNk are same as those in CNNreg except for the last fullyconnected layer. The last fully-connected layer of CNNreg has only one output neuron, but it is removed in CNNk and the features extracted from the previous fully-connected layer are passed to the Diff layer as shown Figure 2b. Because CNNk is trained to model the rank order of (xi, xk, xj) by exploring the data relationship, the Diff layer is used to represent the ordinal information within triplets. Based on the assumption that the distance between instances in the mapped feature space indicates the distance between their ranks, the Diff layer combines two parts of features ψ(xk) - ψ(xi) and ψ(xj) - ψ(xk), where ψ(xi) is the feature vectors exacted from the last fully-connected layers of Gi. It can be concluded from the proposed architecture, although the augmented dataset has n3 triplets, CNNOR is computational feasible even for large datasets. As shown in Figure 2b, the elements of a triplet are processed individually before the Diff layer. For all (xi, xj, xk), only unique xi, xj and xk are necessary to be computed. And Gi, Gk and Gj share weights. Therefore, before the Diff layer, the computation cost of CNNk is same as a standard CNN. The operation of the Diff layer is a simple subtraction, which is not an issue for a modern hardware even for huge data.

3.3 The Decoder Based onMajority Voting

A simple decoder is designed to predict the rank label of a testing point xt from the outputs of CNNk as shown in line 7-11 of Algorithm 1. Table 1 is the coding matrix of CNNOR for a 5-rank example. Each row is for one rank and each column is for one CNNk. The elements in the matrix represent the training targets for different CNNk and different ranks. For example, the first column of Table 1 is labeled as (xt, 2), which represents a testing triplet constructed as Eq. 3 for CNN1, and rank 1 is considered as a positive rank and the rest are negative ranks. In the testing phase, d triplets for each column are predicted and the rank with maximum positive predications is regarded as the rank label of xt.

4 Evaluation

The proposed CNNOR framework is evaluated on a historical color image dataset [Palermo et al., 2012] and an image retrieval dataset MSRA-MM1.0 [Wang et al., 2009]. Two metrics are used as performance indexes. The first one is accuracy defined by acc = 1 |T | ∑xt∈T [ ˆ yt = yt], where T is a testing set, |T| is its size, yt is the ground truth of xt, ˆ yt is the predicted label for xt and [·] is the indicator function. The second one is mean absolute error (MAE) defined by e = 1 |T | ∑xt∈T | ˆ yt - yt|.

4.1 Results on the Historical Color Images Dataset

The historical color image dataset [Palermo et al., 2012] is a benchmark dataset for algorithm evaluation, which includes historical color images photographed in different decades. As shown in Figure 3, the dataset consists of five ordinal categories corresponding to five decades from 1930s to 1970s, and each category has 265 color images. For fair comparison, the same experimental setting as [Palermo et al., 2012] is taken in this study. In each category, 215 images are selected for training and the rest 50 images are for testing. The same training and testing image partitions in [Palermo et al., 2012] are used.

Figure 4: MSRA-MM1.0 dataset: cat subset.

Two categories of baselines are used for comparison: handcrafted feature based methods and deep learning methods. For each category, state-of-the-art multi-class classification methods and ordinal regression methods are evaluated as shown in Table 2. Palermo et al. [Palermo et al., 2012] designed six categories of features for this task, which are 8168 dimensions in total. For fair comparison, all hand-crafted feature based methods in Table 2 are tested on these same features. Palermo et al. [Palermo et al., 2012] focused on feature design for this specific task, and based on that they tackle the task as a multi-class classification problem by using a linear multi-class SVM as the classifier. Martin et al. [Martin et al., 2014] improved the ordinal regression method for this particular task and got better MAE result. RED-SVM [Lin and Li, 2012] is a state-of-the-art general ordinal regression method but performs worse than Palermo et al. [Palermo et al., 2012] and Martin et al. [Martin et al., 2014] on this dataset.

The deep multi-class classification method (CNNm in Table 2) and the deep ordinal regression method (Niu et al.'s method in Table 2) based on CNN are implemented for comparison. The layers, parameters and organizations of the networks in CNNOR (i.e, G1-G5,Gi,Gj and Gk in Figure 2) are implemented exactly same as that in CNNm and Niu et al.'s method, except for the number of output neurons and the loss layer. Alex's architecture [Krizhevsky et al., 2012] is employed in all the comparison methods. The image size of the historical dataset is equal or greater than 315 × 315 pixels, and we crop the images to 227 × 227 pixels for inputing to Alex's architecture. For each training/testing image partition, the last 5 images in the training set are used as the validation images, i.e., 210 images for training, 5 images for validation, and 50 images for testing in each rank. Thus, the total sizes of training, validation and testing sets for CNNm and Niu et al.'s method are 1050, 25 and 250 images. For CNNreg of CNNOR, all the possible permutations of the images in the five ranks produce 2105 training instances (i.e., the list (x1i , x2i , · · · , xki , · · · , xmi ) in Eq. 1). In the experiments, 40960 instances are randomly selected from them to train CNNreg and 40960 training triplets and 2100 validation triplets with equal numbers of positive and negative triplets are randomly selected to train CNNk. In the testing phase, 30 triplets for each CNNk are used to infer the label. The minibatch size is set to 64 in all the experiments. The learning rate for CNNm, Niu et al.'s method and CNNreg are 0.01, and the learning rate for fine-tuning CNNk from CNNreg is 0.001. In the training phase, it is observed that the accuracies on validation sets of both CNNm and Niu et al.'s method are fluctuated dramatically because the validation sets are too small to reliably estimate the performance on the testing set. However, for CNNOR, the size of validation set is 33 mini-batches, and therefore, we can use the early stopping strategy to stop training when accuracy converges on the validation set. This is a benefit from the proposed method for small datasets for training and validation. In the experiments, the numbers of training iterations for CNNm and Niu et al.'s method need to be predefined. Table 3 and Table 4 show the test accuracies of CNNm and Niu et al.'s method on different numbers of iterations. After 7500 iterations for CNNm and 12500 iterations for Niu et al.'s method the losses on both training sets are smaller than 0.01. In Table 2, we choose the best accuracy from Table 3 and Table 4 for comparison. For CNNOR, the number of iterations to train CNNreg is 2500, and to train CNNk is 2111, which is the average value on all 20 training/testing partitions. It shows that CNNOR outperforms the other two deep learning methods in terms of accuracy. Though Niu et al.'s method performs better than CNNOR in terms of MAE, its accuracy is significantly lower. It should be emphasized that the CNNm and Niu et al.'s results in Table 2 are the best results selected from Tables 3 and 4, where predefined iterations are used because the small validation sets cannot reliably estimate the testing accuracy. Comparing with the methods based on the hand-crafted features, CNNOR performs 5.64% better than RED-SVM in terms of accuracy and its performance is also comparable with the other two methods. Note that RED-SVM is an ordinal regression method for general ordinal regression problems but Palermo et al. and Martin et al.s methods, which are highly based on prior knowledge to design the classifiers and the features, are tailed-made for this dataset.

4.2 Results on the Image Retrieval Dataset

Microsoft Research Asia Multimedia 1.0 (MSRA-MM 1.0) dataset [Wang et al., 2009] is a benchmark dataset to evaluate multimedia information retrieval algorithms and includes an image subset and a video subset. In the image dataset, 68 representative queries are selected based on the query log of Microsoft Live Search and then about 1000 images for each query are collected from the image search engine of Microsoft Live Search. The relevance annotations of the images are provided. For each image, its relevance to the corresponding query is labeled with three levels: very relevant, relevant and irrelevant. These three levels are indicated by rank 2, 1 and 0, respectively. Figure 4 shows an example of the "cat" query, where the first row lists images labeled as

"very relevant", the second row shows some images labeled as "relevant", and the last row is "irrelevant" images. Given a testing image in a query set, predicting its relevance to the query is an ordinal regression problem. Hence, five subsets of MSRA-MM 1.0 image dataset which are "cat", "baby", "beach", "rose" and "tiger" are used to evaluate the performance of algorithms. The number of images in each rank of the five subsets is shown in Table 5. The total number of images in each subset is less than 1100 which is also a small dataset. The experiments on MSRA-MM 1.0 evaluate the CNNOR on data with different properties, including the different number of ranks, non-equal number of images in each rank and smaller image size.

The images in MSRA-MM 1.0 are thumbnails (i.e., the small images displayed on Microsoft Live Search) which are cropped to 3-channel 60 × 60 pixels in the experiments. The LeNet architecture [LeCun et al., 1998] is employed in all the comparison methods: CNNm, Niu et al.'s method and CNNOR. The setting of mini-batch and learning rate are same as those in Section 4.1. Tables 6 and 7 summarize the results, which are the mean values on three random training/testing partitions. For accuracy, CNNOR performs 5.16% higher than CNN and 5.20% than Niu et al.'s methods averagely on the five subsets. For MAE, CNNOR achieves better results on three of the five subsets. Because there are not handcrafted features for MSRA-MM 1.0 dataset published in literature, to evaluate non-deep methods, the best baseline method in Table 2 using the 8168 features proposed for the historical dataset is tested. The accuracy on "cat" subset is 37.11%, which is 15.56% lower than CNNOR. The results indicate that CNNOR performs better than the two deep learning based multiclass classification method and ordinal regression method.

5 Conclusions

In this paper, a new ordinal regression algorithm is proposed for small data problems. CNNs are adapted to automatically extract high-level features to describe the ordinal relationship. To increase training data, this paper proposes a new network organization with triplets as instances and employs a new objective to pre-train the networks. Thus, deep learning can be applied more effectively on small dataset problems. The experimental results show that the proposed algorithm is comparable with the state-of-the-art methods.

Acknowledgments

This work was conducted within Rolls-Royce@NTU Corporate Lab with support from the National Research Foundation (NRF) Singapore under the Corp Lab@University Scheme.