Active ordinal classification by querying relative information

2.1 Active learning

Active learning aims to induce a prediction model while minimizing the labeling cost through interactive instance selection and label inquiry. It is suitable for machine learning scenarios where a large amount of unlabeled data are available or easy to collect, but label acquisition is expensive. The fundamental issue of active learning is to determine which instances would be most valuable if it is labeled and used as training instances [15]. Informativeness and representativeness are two primary considerations for assessing the value of an unlabeled instance. Active learning strategies focusing on the informativeness of unlabeled instances include uncertainty sampling [5, 16, 17], query-by-committee [18, 19], expected change [20, 21], and so on. Active learning strategies that concentrate on the representativeness of unlabeled instances prefer to select the instances that can represent the data distribution. The commonly used methods of this type include clustering-based AL methods [22, 23], experimental designs [24, 25], and so on. Combining multiple assessment criteria for active instance selection is usually encouraged in the active learning community and often results in robust active learning performance.

Although great progress has been made in active learning research on classification, little effort has been devoted to the active learning problem for ordinal classification. Soons and Feelders [26] first proposed an active learning method for ordinal classification by exploiting the monotonicity constraints in the data. However, this work is only suitable for monotonic ordinal classification data [27] and cannot scale up to the general ordinal classification data. Recently, Li et al. [6] designed an active ordinal classification method based on the adjacent category logistic model and an A-optimal experimental design criterion. The major shortcoming of this method is that it has to calculate the inverse of a large matrix in each iteration for each unlabeled instance, which may limit its usability in practice. In the study of the imbalanced ordinal classification problem, Ge et al. [10] proposed an uncertainty sampling-based active learning method to achieve the minority class oversampling in the ordinal data. This method labels the instance with the smallest distance from its nearest decision boundary. Although this method may suffer from sampling redundancy, it generally performs satisfactorily. To our knowledge, the above two methods are the only two active learning methods for the general ordinal classification. In practice, obtaining labels directly from human experts is often expensive or time-consuming. When the query budget is insufficient, collecting sufficient training instances using the aforementioned pointwise query AL methods is unaffordable.

In recent years, active learning by soliciting low-cost instance-pair relation information has attracted more attention. Nevertheless, most of those studies concentrate on active clustering [28] and active learning for ranking [29]. Since there are essential differences between learning for ranking and ordinal classification [30], the active ranking methods cannot be used for active ordinal classification. Fu et al. [8] first developed a pairwise query active learning method by asking the annotator “whether instances 𝐱 i and 𝐱 j belong to the same class?”. However, this method is only suitable for binary classification problems and cannot immediately extend to multiclass problems. Chien et al. [31] presented a hypergraph-based pairwise query active learning method. Although this method is compatible with multiclass classification, it needs to pair the critical instance with the labeled instances of different classes, which costs 𝒪 ⁢ ( K - 1 ) times pairwise queries to obtain one explicit label. Here, the K is the number of classes. In addition, this method is computationally expensive due to the breadth-first searching for the shortest path in a hypergraph. So far, no research has been devoted to pairwise query active learning for ordinal classification. In addition, the existing pairwise query AL methods are unsuitable for solving this problem. The above situation motivates us to carry out the new study in this paper.

2.2 Ordinal classification with absolute and relative information

It is believed that non-expert annotators or novices can provide low-cost relative information, and the cost is much lower than that of asking experts for absolute information. Therefore, To reduce the labeling cost of ordinal classification problems, researchers have recently constructed various new ordinal classification models to learn with absolute and low-cost relative information simultaneously. Tang et al. [1] proposed a nearest neighbors-based ordinal classification model by fusing absolute and relative information. This method was further extended based on a distance metric learning technique in [32]. However, the performance of these methods is heavily dependent on the number of labeled instances. If there are not enough labeled instances, these methods usually perform unsatisfactorily. Therefore, these methods are unsuitable for active learning scenarios where only a small number of labeled samples exist. Sader et al. [12] proposed a novel proportional odds model, where the relative information is formulated as the constraint component in the loss function. Subsequently, Tang et al. [13] extended this scheme to several existing ordinal classification models and conducted a comparative study. The comparative study shows that the methods SVLORR and LDLORR generally perform better. However, one apparent shortcoming of these methods is that they were only suitable for linear separable ordinal data and cannot be immediately extended to nonlinear methods. In this study, we overcome this limitation. The proposed method is suitable for nonlinear data by leveraging the kernel trick.

Although the above works paid much effort into designing ordinal classification models for learning with absolute and relative information simultaneously, they failed to consider how to select valuable query pairs. When requesting relative information, these models randomly select query pairs from the unlabeled pool for querying, which leads to inefficient use of pairwise query resources. On the one hand, these methods do not guarantee that the instances in the query pair are informative. On the other hand, when the two instances in a query pair belong to an identical class, one cannot obtain any valuable information. All the above issues have been addressed in this paper. This paper builds each query pair with an informative unlabeled instance and a carefully selected labeled instance. In this setup, we can obtain useful information from the annotator regardless of whether the two instances in a query pair belong to an identical class. In particular, the proposed method can produce labeled instances during pairwise query active learning.

2.3 Reduction-based ordinal classification framework

To solve the ordinal classification problem more effectively, Li and Lin [14] have proposed a reduction framework to reduce an ordinal classification problem to a binary classification problem and gave a theoretical explanation. The model based on this framework is essentially a threshold-based OC model. We instantiate an OC model in this paper based on this reduction-based framework to learn with labeled instances and instance-pair relation information simultaneously. Therefore, in what follows, we will recall this framework’s formulations.

To predict the class label of an instance 𝐱 , the threshold-based ordinal classification model typically learns K - 1 orderd thresholds: , where θ 0 = - ∞ and θ K = + ∞ are typically assumed. Thus, the instance 𝐱 is classified as 𝒞 k in the case that the predictive output h ⁢ ( 𝐱 ) = 𝐰 T ⁢ 𝐱 falls in the range of , where 𝐰 ∈ ℝ d , 𝐰 T ⁢ 𝐱 is the inner product of 𝐱 and 𝐰 .

For each original training instance ⟨ 𝐱 i , y i ⟩ , the reduction framework extends it into K - 1 binary training instances by the following rule:

⟨ 𝐱 i k , y i k ⟩ , k = { 1 , ⋯ , K - 1 } , 𝐱 i k = ( 𝐱 i , 𝐞 k ) ∈ ℝ d + K - 1 ,(1) y i k = 1 - 2 I [ y i ≺ 𝒞 k + 1 ] ,

where 𝐞 k ∈ 𝐑 K - 1 denotes a vector with the k -th element as value 1 and the rest of the elements are all 0, and I ⁢ [ ⋅ ] is an indicator function that returns 1 if the inside condition holds; otherwise, a zero is returned. Thus, for each extended instance 𝐱 i k , there is a binary class label y i k ∈ { - 1 , 1 } associated with it.

The weight vector in the extended binary classification problem

𝐰 ¯ = ( 𝐰 , - θ ) ∈ ℝ d + K - 1(2)

can be learned to predict the output of 𝐱 i k , such that g ⁢ ( 𝐱 i k ) = ( 𝐰 , - θ ) T ⁢ 𝐱 i k = 𝐰 T ⁢ 𝐱 i - θ k = h ⁢ ( 𝐱 i ) - θ k , where θ = [ θ 1 , ⋯ , θ K - 1 ] . Therefore, the g ⁢ ( 𝐱 i k ) can be explained as the distance from 𝐱 i to the k -th threshold. Whereafter, the predictive ordinal label y i ^ = 𝒞 l of instance 𝐱 i can be obtained with the l computed as

$l=1+{\displaystyle \sum _{k=1}^{K-1}}I[g({𝐱}_i^k)>0]$(3)

For an unlabeled instance 𝐱 i , its cumulative probabilities can be computed as [33]

P ( y i ≺ 𝒞 k + 1 | 𝐱 i ) = 1 1 + exp ⁡ ( - ( θ k - 𝐰 T ⁢ 𝐱 i ) ) = 1 1 + exp ⁡ ( 𝐰 ¯ T ⁢ ϕ ⁢ ( 𝐱 i k ) ) ,(4) k = 1 , ⋯ , K - 1 ,

where K is the number of classes. Consequently, we can obtain the posterior probability estimate of 𝐱 i by decomposing the cumulative probabilities as follows

(5)

Note that the function g ⁢ ( 𝐱 ) in Eq. (3) can be any of the existing well-established binary prediction models [14], such as support vector machine, logistic regression, and so on. In Section 3, we instantiate this reduction framework with the kernel extreme learning machine [34] and introduce how to train the new OC model using labeled instances and relative information.

3.1 Problem setting and method overview

In the considered scenario, let 𝒯 = { ⟨ 𝐱 i , y i ⟩ } i = 1 n be the initial training set (also referred to as seed set) where each instance 𝐱 i ∈ ℒ ⊆ ℝ d is a feature vector and associated with a label y i ∈ 𝒴 = { 𝒞 1 , 𝒞 2 , ⋯ , 𝒞 K } . There is a total ordering among the classes, such as 𝒞 1 ≺ 𝒞 2 ≺ ⋯ ≺ 𝒞 K , where the notation “ ≺ ” indicates a certain ordering relation or grading relation. Let 𝒰 = { 𝐱 j } j = n + 1 N be the unlabeld pool, where n ≪ N . Thereinafter, if not specified, K indicates the number of classes.

Instead of directly querying the instance label in a traditional active learning way, we consider a pairwise query setting in this paper. In each pairwise query, when a query pair ( 𝐱 i , 𝐱 j ) is determined, the annotator is inquired “what is the relation between instances 𝐱 i and 𝐱 j ?”. The feedbacks of the annotator are as follows:

“ 𝐱 i ≺ c 𝐱 j ”, which means the class of 𝐱 i is of a higher level than that of 𝐱 j . Without loss of generality, if the class of 𝐱 j is of a higher level than that of 𝐱 i , the feedback will be “ 𝐱 j ≺ c 𝐱 i ”.

In order to use the labeled instance and the instance-pair relation information simultaneously in the pairwise query active learning process, we introduce a class interval concept and two reasoning rules.

Without loss of generality, the class interval of an unlabeled instance 𝐱 i is [ 𝒞 1 , 𝒞 K ] at the initial time. If the class interval size of an instance is larger than 1, this instance is essentially still an unlabeled instance. Intuitively, an unlabeled instance belongs to each class within its class interval with an identical probability if no additional information exists. Given a labeled instance ⟨ 𝐱 i , 𝒞 k ⟩ , we say 𝐱 i corresponds to a narrow class interval [ 𝒞 k , 𝒞 k ] . Therefore, we can obtain an explicit label once the class interval size of an unlabeled instance is reduced to 1. Based on the concept of class interval, two reasoning rules are designed as follows.

Based on the above two reasoning rules, we can update the class interval of the critical instance in the query pair after information acquisition from the annotator. Accordingly, we can convert the labeled instances and the relative information into the class interval-labeled form, i.e., ⟨ 𝐱 i , [ 𝒞 L i , 𝒞 R i ] ⟩ . We call the training instance of this form the class interval-labeled training instance. The instance that its class interval size is smaller than K can be used to train the base learner. Thus, we can construct a interval-labeled training set ℒ I = { ⟨ 𝐱 i , [ 𝒞 L i , 𝒞 R i ] ⟩ } i = 1 m , n ⩽ m . For any unlabeled instance, we can always obtain its explicit label through a few pairwise queries and reasonings. Therefore, the goal of our method is to obtain more labeled instances with the least number of pairwise queries, thus producing a promising ordinal classifier.

In our method, each query pair is built with an unlabeled instance and a labeled instance. Such that we can obtain useful information for model training from each pairwise query and reasoning, and we have a chance to infer the critical instance’s explicit label with a few pairwise queries. If the two instances in the query pair are all unlabeled, such as ( 𝐱 i , 𝐱 j ) , where 𝐱 i ∈ 𝒰 and 𝐱 j ∈ 𝒰 . It is just when the intersection size of the class intervals of the two instances is less than or equal to 2 that there is a chance to obtain the explicit label. This usually requires a large number of pairwise queries. Compared to the latter, the former query pair building form can obtain more explicit labels with a given pairwise query budget, facilitating the learning of a good ordinal classifier.

To visually show the difference between pointwise query active learning and pairwise query active learning, we depict the traditional pointwise query active learning framework and the proposed pairwise query active learning framework in Fig. 1a and b, respectively. In the traditional pointwise query active learning, the annotator must provide a reliable label for each query instance. In such a situation, the label acquisition usually depends on experts with domain knowledge or even rigorous physical or chemical testing. In the proposed pairwise query active learning, we can induce an ordinal classifier by interactively asking for low-cost relative information. Since it is not difficult to compare two instances with each other in the context of ordinal classification, non-experts or novices can provide relative information [1]. Therefore, a non-expert or novice can be employed as an annotator.

OPEN IN VIEWER

We summarize the algorithmic procedure of the proposed method in Algorithm 1. In the algorithm, lines 1 and 2 correspond to the initialization stage, where the initial training instances in 𝒯 are converted into the class interval-labeled training instances. Based on the class interval-labeled training set ℒ I , the base learner ℳ is induced. The base learner will be presented in Section 3.2. In each iteration, the algorithm selects one critical unlabeled instance and joins it into ℒ I ; this corresponds to line 4. The critical unlabeled instances selection method will be introduced in Section 3.3.1. In each iteration, for each class interval-labeled instance, if its class interval size is larger than 1, we will pair a labeled instance with it to build a query pair for querying. The labeled instance selection method will be introduced in Section 3.3.2. After the annotator feeds back the relative information, we will update the class interval of the unlabeled instance and retrain the base learner. The above operations correspond to line 5 to line 15. The algorithm is terminated when the pairwise query budget is exhausted.

[h] : Active Ordinal Classification Based on Pairwise Queries (AOCpair).[1] Seed set 𝒯 , unlabeled set 𝒰 , pairwise query budget b , base learner ℳ . The trained base learner ℳ , the extened labeled instance set 𝒯 . B ← b ; ℒ I ← ∅ ; Convert the training instances in 𝒯 into the class interval-labeled instances and join them into ℒ I ; Train ℳ with ℒ I ; $B>0$ Select a critical instance 𝐱 ∗ ∈ 𝒰 ; ℒ I ← ℒ I ∪ { ⟨ 𝐱 ∗ , [ 𝒞 1 , 𝒞 K ] ⟩ } ; i ← 1 ; $B>0$ and i ⩽ | ℒ I | $IS({𝐱}_i)>1$ Build a query pair ( 𝐱 i , 𝐱 j ) ; / ⁣ / ⟨ 𝐱 i , [ 𝒞 L i , 𝒞 R i ] ⟩ ∈ ℒ I , ⟨ 𝐱 j , y j ⟩ ∈ 𝒯 Inquire the instance-pair relation information about ( 𝐱 i , 𝐱 j ) ; Update 𝐱 i ’s class interval according to the reasoning rules; B ← B - 1 ; I ⁢ S ⁢ ( 𝐱 i ) = 1 𝒯 ← 𝒯 ∪ { ⟨ 𝐱 i , y i ⟩ } ; 𝒰 ← 𝒰 / { 𝐱 i } ; Retrain ℳ with ℒ I ; i ← i + 1 ;

Before introducing how to use the class interval-labeled instances to train an OC model, we first instantiate an OC model based on the reduction-based framework [14] introduced in Section 2.3. As mentioned in Section 2.3, the g ⁢ ( 𝐱 ) can be any well-developed binary prediction model. Therefore, we employ a kernel extreme learning machine (KELM) model to instantiate the reduction-based ordinal classification framework. The KELM model is simple to implement and has comparable performance to the SVM model [34].

An extreme learning machine is a generalized single-hidden-layer feedforward neural network where the hidden layer need not be tuned, and we can formulate it as

g ⁢ ( 𝐱 ) = 𝐡 ⁢ ( 𝐱 ) ⁢ β = 𝐡 ⁢ ( 𝐱 ) ⁢ 𝐇 T ⁢ ( 1 C ⁢ 𝐈 + 𝐇𝐇 T ) - 1 ⁢ 𝐓(9)

where the β = [ β 1 , ⋯ , β L ] T is the vector of the output weights between the hidden layer of L nodes and the output node, 𝐡 ⁢ ( 𝐱 ) = [ h 1 ⁢ ( 𝐱 ) , ⋯ , h L ⁢ ( 𝐱 ) ] is the output vector of the hidden layer about input 𝐱 , 𝐇 = [ 𝐡 ⁢ ( 𝐱 1 ) , ⋯ , 𝐡 ⁢ ( 𝐱 n ) ] T , 𝐈 is an identity matrix, and 𝐓 = [ y 1 , ⋯ , y n ] T . For binary classification, the decision function is

y ^ = 𝑠𝑖𝑔𝑛 ⁢ ( 𝐡 ⁢ ( 𝐱 ) ⁢ β )(10)

Following the work in [34], the kernel-based extreme learning machine model takes the hidden layer as an unknown feature mapping 𝐡 ⁢ ( 𝐱 ) from the input space ℝ d to a feature space. Thus, the Mercer’s condition can be applied and a kernel matrix can be defined as 𝐊 = 𝐇𝐇 T , and has 𝐡 ⁢ ( 𝐱 i ) ⁢ 𝐡 ⁢ ( 𝐱 j ) = 𝒦 ⁢ ( 𝐱 i , 𝐱 j ) , where 𝒦 ⁢ ( 𝐱 i , 𝐱 j ) is a kernel function. Then, the output weight vector β can be computed as

β = ( 1 C ⁢ 𝐈 + 𝐊 ) - 1 ⁢ 𝐓 ,(11)

and the predictive output can be formalized as

g ⁢ ( 𝐱 ) = ∑ i = 1 n β i ⁢ 𝒦 ⁢ ( 𝐱 i , 𝐱 ) = 𝐤 ⁢ ( 𝐱 ) ⁢ β = 𝐤 ⁢ ( 𝐱 ) ⁢ ( 1 C ⁢ 𝐈 + 𝐊 ) - 1 ⁢ 𝐓 ,(12)

where 𝐤 ⁢ ( 𝐱 ) = [ 𝒦 ⁢ ( 𝐱 1 , 𝐱 ) , ⋯ , 𝒦 ⁢ ( 𝐱 n , 𝐱 ) ] ∈ ℝ 1 × n .

We can instantiate the reduction-based OC framework by plugging the g ⁢ ( 𝐱 ) in Eq. (12) into Eq. (3). Thus, for an unobserved instance 𝐱 i ∈ 𝒰 , we can obtain

g ⁢ ( 𝐱 i k 1 ) = 𝒲 ¯ T ⁢ ( ϕ ⁢ ( 𝐱 i ) , 𝐞 k 1 ) = ( 𝒲 , - θ ) T ⁢ ( ϕ ⁢ ( 𝐱 i ) , 𝐞 k 1 ) = ∑ j = 1 n ∑ k 2 = 1 K - 1 β i k 2 ⁢ 𝒦 ⁢ ( 𝐱 i k 1 , 𝐱 j k 2 )(13) = ∑ j = 1 n ∑ k 2 = 1 K - 1 β i k 2 ⁢ ( ϕ ⁢ ( 𝐱 i ) T ⁢ ϕ ⁢ ( 𝐱 j ) + 𝐞 k 1 T ⁢ 𝐞 k 2 ) , k 1 = 1 , ⋯ , K - 1 ,

where ( ϕ ⁢ ( 𝐱 i ) T ⁢ ϕ ⁢ ( 𝐱 j ) + 𝐞 k 1 T ⁢ 𝐞 k 2 ) is a resultant kernel [35, 10]. In this paper, we consider the perceptron kernel [35], i.e., ϕ ⁢ ( 𝐱 i ) T ⁢ ϕ ⁢ ( 𝐱 j ) = - ∥ 𝐱 i - 𝐱 j ∥ 2 . Here, g ⁢ ( 𝐱 i k 1 ) can be interpreted as the distance from 𝐱 i to the k 1 -th decision hyperplane. Of course, g ⁢ ( 𝐱 i k 1 ) could be a negative value. Then, instance 𝐱 i ’s ordinal scale label can be calculated based on Eq. (3). We refer to the above ordinal classification model as the RKELM model.

In order to train the RKELM model using class interval-labeled training instances, we change the original extended binary training instances generation rule in Eq. (2.3) into a new rule. Suppose ⟨ 𝐱 i , [ 𝒞 L i , 𝒞 R i ] ⟩ is a class interval-labeled training instance, the extended binary training instances are generated as follows

⟨ 𝐱 i k , y i k ⟩ , (14) 𝐱 i k = ( 𝐱 i , 𝐞 k ) ∈ ℝ d + K - 1

Instead of generates K - 1 binary instances for each training instance ⟨ 𝐱 i , y i ⟩ , the RKELM model with the new rule generates K - I ⁢ S ⁢ ( 𝐱 i ) binary instances for each class interval-labeled training instance ⟨ 𝐱 i , [ 𝒞 L i , 𝒞 R i ] ⟩ . Table 1 shows the examples of extended binary instances generation for an instance when it associates with different class intervals. In the table, “ y i k = ? ” denotes that the binary label of 𝐱 i k is undetermined, and the instance 𝐱 i k is therefore not involved in the extended binary training set. The complexity of the RKELM model is 𝒪 ⁢ ( m 3 ⁢ ( K - 1 ) 3 ) , where m = | ℒ I | is the number of class interval-labeled training instances.

For an unlabeled instance 𝐱 i ∈ 𝒰 , suppose it associates with a class interval [ 𝒞 L i , 𝒞 R i ] , its cumulative probabilities are computed as

P ( y i ≺ 𝒞 k + 1 | 𝐱 i ) = 1 1 + exp ⁡ ( g ⁢ ( 𝐱 i k ) ) , (15) L i ⩽ k ⩽ R i - 1 .

Accordingly, we can obtain the posterior probabilities of 𝐱 i ∈ 𝒰 by decomposing the cumulative probabilities as follows

(16)

In our method, each query pair is built with a critical unlabeled instance and a labeled instance. Therefore, in what follows, we will describe how to choose the two instances separately.

Let N = | 𝒯 ∪ 𝒰 | be the number of all instances and K be the number of classes. Suppose in the current iteration, the size of the training set is n = | 𝒯 | and the size of the class interval-labeled training set is m = | ℒ I | . We will then analyze the computational complexity of one pairwise query from the aspects of base learner training, critical instances selection, and labeled instance selection, respectively.

The time complexity of training the based learner RKELM model is 𝒪 ⁢ ( m 3 ⁢ ( K - 1 ) 3 ) . Selecting the critical unlabeled instance for the query pair requires the following two operations: (1) calculate g ⁢ ( 𝐱 i ) in Eq. (3.2) for all the instances in 𝒰 requires 𝒪 ⁢ ( ( N - m ) 2 ⁢ ( K - 1 ) 2 ) time; (2) obtain the critical unlabeled instance based on Eq. (18) requires 𝒪 ⁢ ( ( N - m ) ⁢ ( K - 1 ) ) time. Therefore, the time complexity of selecting a critical unlabeled instance is 𝒪 ⁢ ( ( N - m ) 2 ⁢ ( K - 1 ) 2 ) . For the labeled instance selection, the main computational cost is the calculation of the expected cost with Eq. (21), which requires 𝒪 ⁢ ( K 2 ) time in the worst case.

In summary, suppose N ≫ m , the time complexity of performing one pairwise query is 𝒪 ⁢ ( N 2 ⁢ K 2 + m 3 ⁢ K 3 ) .

4.1 Datasets and experimental configuration

Table 4 summarizes the information of the twelve used datasets. The datasets Cleveland and Obesity are from the KEEL dataset repository and the UCI dataset repository, respectively. The other ten datasets are from reference [30]. Since a part of the attributes in Obesity are nominal attributes, we have preprocessed those nominal attributes using one-hot encoding. Before experiments, all the datasets are standardized by the following Z-score:

x i ⁢ j = x i ⁢ j - 𝑚𝑒𝑎𝑛 ⁢ ( x j ) 𝑠𝑡𝑑 ⁢ ( x j ) ,(23)

where x i ⁢ j denotes the j -th attribute value of instance 𝐱 i , and 𝑚𝑒𝑎𝑛 ⁢ ( x j ) and 𝑠𝑡𝑑 ⁢ ( x j ) are the mean value and the standard deviation of the j -th attribute, respectively.

In the experiments, each of the datasets is split based on four times five-fold cross-validation, i.e., each dataset is split into an unlabeled pool (80% of the data) and a testing set (20% of the data) in each run (a total of 20 runs). The metrics of Mean Zero-one Error (MZE), Mean Absolute Error (MAE), and Macro F1 score (F1) are employed in the experiments. MZE and MAE are the longstanding benchmark metrics to measure the performance of ordinal classification [38]. Macro F1 score is a commonly used metric to measure the performance of multi-class classification.

To verify the effectiveness of our method (denoted as AOCpair), we compare it with the following three state-of-the-art methods:

LDLORR [13] is the method of linear discriminant learning for ordinal classification with labeled instances and instance-pair relation information.

The above methods are the three existing methods most related to our method. These three methods select the query pairs from the pool set and request the relative information interactively from the annotators. In the proposed method, the coefficient C in the RKELM model is fixed as 10. We assume that the annotators provide the ground-truth instance-pair relation information in each pairwise query. In each run, the performances of the compared methods are evaluated on the testing set. Finally, the average results of 20 runs for the different methods are reported.

We are interested in whether our approach can achieve a better ordinal classification performance under a given pairwise query budget. To comparatively study the performance of the proposed method and the three competitors, we set the given pairwise query budget as 10 ⁢ K and 20 ⁢ K and compare those methods under three different sizes ( K , 3 ⁢ K , and 5 ⁢ K ) of the initial training set (seed set). The seed set consists of instances selected 1 / 3 / 5 from each class randomly from the unlabeled pool.