Integrating Specialized Classifiers Based on Continuous Time Markov Chain

1 Introduction

Classifier combination is a widely used strategy for improving classification performance. Previous study along this line has resulted in a plethora of methods [Sharkey, 1999; Sewell, 2011; Wo´zniak et al., 2014]. However, with the recent rise of deep learning [Krizhevsky et al., 2012; Szegedy et al., 2015; Simonyan and Zisserman, 2014; He et al., 2016a], a question regarding the utility of classifier ensemble arises: Is it still useful to combine classifiers given the strong performance of state-of-the-art deep networks?

Real-world practice in recent years suggests a positive answer to this question. First, on a number of significant challenges, e.g. ImageNet [Russakovsky et al., 2015] and ActivityNet [Fabian Caba Heilbron and Niebles, 2015], top-ranked solutions all rely on ensembles to achieve competitive performance. For example, on ImageNet, an ensemble can often attain over 10% of relative error reduction compared to any individual classifiers, including state-of-the-art networks, e.g. Inception-ResNet [Szegedy et al., 2016]. We also observed empirically that combinations of specialized classifiers can often outperform a general classifier, sometimes by a considerable margin. Second, training a deep network usually requires a large dataset and a sheer amount of computational resources. This is not always feasible when factors like time, cost, and data availability are taken into account. Under such circumstances, there can be no other choices but to rely on existing classifiers. It is not uncommon that the classifiers from different sources cover different sets of classes. Therefore, classifier combination remains an effective method to improve performance. It may even be an indispensable part in certain real-world applications.

This paper proposes a novel way to integrate specialized classifiers. Instead of combining their predictions directly, we consider the procedure of reaching the final prediction as a biased random walk among classes. Specifically, we decompose each prediction into a set of pairwise preferences and then construct a continuous-time Markov chain by treating such preferences as transition channels, as shown in Figure 1. This way results in a unified picture over all specialized predictions, from which we may draw a more reliable conclusion.

We tested the proposed methods on large datasets. The results show that the presented methods can lead to further performance gains over state-of-the-art deep networks. The predictions derived from these methods are also more accurate than those based on classical combination techniques. It is also noteworthy that the presented formulations are very general and can be directly used in various contexts. For example, one can use them to combine out-of-box classifiers trained for different sets of classes to support a more general application, without re-training.

2 RelatedWork

Extensive study on classifier combination for decades had led to a plethora of methods. See [Sharkey, 1999; Sewell, 2011; Wo´zniak et al., 2014] for more comprehensive reviews. In general, existing methods fall into two categories: ensemble methods and modular methods. Specifically, ensemble methods combine a set of classifiers that work with the same set of classes; while modular methods take advantage of domainspecific knowledges to divide the classification task into subtasks, each accomplished by a specialized expert, e.g. one expert classifies flowers, while another one differentiates between animals.

Designs of ensemble methods usually revolve around two desiderata: accuracy and diversity. To be more specific, on one hand, individual classifiers should yield reasonable predictions; on the other hand, different classifiers should be complementary to each other, such that the combination of their predictions can hopefully result in improved accuracy. Methods that are widely used for constructing diverse ensembles include Bagging [Breiman, 1996], Adaboost [Freund et al., 1996], and Random subspace [Ho, 1998], etc. The way to combine individual predictions is another focus of the research along this line. Combination schemes explored in previous work range from simple aggregation rules such as majority voting, to sophisticated models, such as stacking [Wolpert, 1992], combination based on the DempsterShafer theory [E. Mandler, 1988; Rogova, 1994], and errorcorrecting output coding [Dietterich and Bakiri, 1995].

Modular methods adopt the divide-and-conquer strategy. Particularly, they decompose the original problem into modules, and combine their results based on the structures among them. Relations among modules can be either cooperative, i.e. all modules contribute to the final prediction, or competitive, i.e. each module has its own realm. In former cases, simple rules such as weighted voting are often used; while for the latter, a particular module needs to be chosen in advance to make the prediction. For example, Mixture of Experts [Jacobs et al., 1991; Jordan and Jacobs, 1994] makes this choice via a gating network.

In recent years, classifier combination remains under active research [Karakatiˇc and Podgorelec, 2016; Omari and Figueiras-Vidal, 2015; Sesmero et al., 2015], which focus primarily on the construction of complementary classifiers or adaptive weighed combination. These methods generally require all constituent classifiers to be aware of all classes, and thus cannot be directly applied for integrating specialized classifiers.

Continuous Time Markov Chain (CTMC) based ensemble, which we propose in this paper, makes no distinction between ensemble or modular methods. It is a very flexible framework that can coherently incorporate both general classifiers, i.e. those covering the all classes, and specialized classifiers, i.e. those working with only a subset of classes, into a unified formulation. Here, classifiers can overlap, and each class can be covered by a different number of classifiers. Compared to existing methods, it has two key advantages: (1) It takes into account the relations among predictions when integrating them as well as the different coverage of specialized classifiers. In this way, it can produce more reliable predictions when the ensemble is diverse or unbalanced. (2) It does not rely on any assumptions of the relations among classifiers (e.g. there is no requirements that they cover disjoint groups of classes or they form a hierarchy, etc.). This flexibility makes it applicable to a wide range of applications and real-world settings.

It is worth noting that use of stochastic processes has been explored in different machine learning areas. For example, some semi-supervised learning methods [Jaakkola and Szummer, 2002; Xu et al., 2006] rely on Markov random walk for label propagation. Their motivation and task, however, are fundamentally different from our work.

3 Classifier Integration Based on CTMC

We consider the task of combining multiple classifiers to make predictions. Suppose we have M classes denoted by c1, . . . , cM, and K classifiers, denoted by f1, . . . , fK. Each classifier may cover all M classes or just a small subset thereof. Particularly, the subset of classes that fk works with is given by {ci}i∈Ik , where Ik is a set of indexes. When |Ik| = M, i.e. fk covers all classes, fk is called a general classifier, otherwise, it is called a specialized classifier.

Given a sample x, fk yields an |Ik|-dimensional prediction vector pk ∈ R|Ik| , in which the entry pk(i) with i ∈ Ik is the probability of sample x belonging to class ci from the view of classifier fk. Various ways can be used to turn the output of a classifier into such a prediction vector. In the simplest case, where a classifier only yields a class label, pk can be constructed as the indicator vector of the predicted class. If a classifier produces scores, e.g. SVM, one can turn the scores into a probability vector via a softmax transform. A variety of other classifiers, e.g. deep networks with softmax output, can directly yield the prediction vectors by design.

Challenges arise when combining outputs from specialized classifiers. First, a specialized classifier, when presented with a sample out of its scope, yields misleading predictions. For instance, a classifier for flower recognition would consider an apple as a certain type of flower. Second, when the coverage of classifiers is unbalanced, i.e. some classes are covered by more classifiers than others, the overall prediction may favor classes that are heavily covered. Figure 2 shows an example where the majority voting yields a wrong prediction when individual classifiers predict correctly.

3.1 Continuous-Time Markov Chains

We develop a novel methodology to effectively combine specialized classifiers based on a Continuous-Time Markov Chain (CTMC) over all classes. In this section, we review some basic properties of CTMC. Formally, a homogeneous CTMC is a stochastic process characterized by a transition rate matrix Q, where qij = Q(i, j) is the transition rate from state i to j when i ̸= j, and -qii is the parameter associated with the exponentially distributed sojourn time in state i.

The dynamic of the process can be understood in terms of alarm clocks. When the chain enters state i, independent alarm clocks are placed at all other states. The clock in state j will ring after an exponentially distributed time interval with parameter qij. When the first clock rings, the chain goes to that state, discards all alarm clocks and repeats. Hence, it is more likely to transit to a state j with larger qij value, as the average waiting time 1/qij is shorter. Since the sojourn time in state i is the minimum of a set of exponentially distributed random variables with parameters {qij : j ̸= i}, it must be an exponential random variable with parameter ∑j̸=i qij . Thus,

So, to construct a CTMC, we only need to specify the set of transition rates between different states.

When the chain is ergodic, P (Xt) will converge to an equilibrium distribution π, which, from an intuitive standpoint, reflects which states it is likely to reach in the long run. π does not depend on the initial distribution, and it is related to the transition rate matrix Q by the stationary condition:

Equation (2) together with the normalization constraint

where 1 is an all-one vector, uniquely determines the stationary probability vector π. Note that once the Q is constructed, π can be efficiently solved by most linear algebra libraries.

3.2 CTMC for Integrating Predictions

The basic idea to integrate specialized predictions is to consider the procedure of reaching the overall prediction as a stochastic process, where one can walk from one class to another, following the preferences conveyed by individual predictions. One naive implementation of this idea is by tracing.

𝑐𝑖

𝐩𝑘 𝑖 𝐩𝑘 𝑗

𝑐𝑗

(a)

Specifically, given a sample x, the classifier fk assigns it to a class ci. From this prediction, one can derive |Ik| - 1 preferences, given by {cj → ci : ∀j ∈ Ik\{i}}, meaning that the classifier prefers ci to all other classes in its domain Ik. Take the example in Figure 2 for instance, the classifiers f13, f23 and f34 together result in three preferences: c1 → c3, c2 → c3, and c3 → c4. Following these preferences, one would eventually reach the ground-truth class c4 and stay there, regardless of which class it begins with.

Ideally, when the preferences derived from all classifiers are consistent with each other, it is not difficult to reach a overall prediction by tracing the preferences. However, realworld situations are often more complicated, and individual classifiers may produce contradicting predictions. Besides, this tracing algorithm also discards the rich information in the prediction vector, i.e. those relative preferences between any pair of classes in the domain. To effectively handle such issues, a more sophisticated scheme is needed. Our approach is to generalize this deterministic tracing algorithm into a CTMC, where one may walk back and forth between classes guided by the preferences, and we rely on the equilibrium distribution to make the final predictions.

We model the pairwise preferences by CTMCs with two states. Given a sample x, denote the prediction vector from classifier fk by pk. For class ci and cj where i, j ∈ Ik, i ̸= j, we build a chain using the prediction values pk(i) and pk(j) as transition rates, which is shown in Figure 3 (a). Exploiting Equation (1), the transition rate matrix Q can be written as

We can see that (pk(i), pk(j)) is a solution to the stationary condition (2). Thus, the stationary distribution for this chain reflects the relative preference of fk on these two classes.

Combining all the (|Ik| 2 ) preferences into one chain, we can construct a CTMC for classifier fk. The state space consists of all the classes that it covers, and the transition rate from class ci to cj is set to the predicted probability for cj. One example with three classes {c1, c2, c3} and pk = (p1, p2, p3) is illustrated in Figure 3 (b). It is easy to see that the transition rate matrix can be written concisely as

where I is the identity matrix. Note that the prediction vector pk itself is the solution to the stationary condition (2), as

This consistency indicates that merging small chains into a large one is a reasonable strategy for combining preferences.

Next, we combine all the chains from different classifiers by superposition, resulting in a chain over all classes, i.e., the union of individual state spaces. In the resultant chain, the transition rates from ci to cj are the sum of all the rates defined for the pair. This process is illustrated in Figure 4. The reason for using the sum operator can be seen from the alarm clock analogy. The channel from state i to state j is set with multiple alarm clocks, and the chain transits from state i to j if any of the clocks rings. This is equivalent to set only one alarm clock who will ring after an exponentially distributed time with parameter being the sum of parameters for individual clocks. Overall, the transition rate matrix Q for the final CTMC can be written as:

Here, Sij = {k : i ∈ Ik and j ∈ Ik} refers to the index set of classifiers that cover both ci and cj. Given a sample, one can construct Q and solve the equilibrium distribution π as the final prediction. In this prediction, the most likely class label is ˆi = argmaxi π(i). Let's revisit the example in Figure 2. For this case, the transition rate matrix is given by

Then the prediction is (0, 0, 0, 1), as expected.

3.3 Properties of CTMC Formulation

First, we show that the CTMC method is applicable to a reasonable configuration of specialized classifiers. We say a set of classifiers is connected, if the graph representation of the constructed CTMC described in Section 3.2 is connected.

Proposition 1. If the classifiers in the ensemble is connected, covers all the classes when combined, and the probabilistic predictions are positive (i.e. predicting non-zero probabilities on all classes that they cover). Then the constructed CTMC is ergodic, and thus CTMC ensemble is applicable and will output a unique prediction.

Proof. The number of states is finite. To show the constructed CTMC is ergodic, it suffices to show that it is irreducible. From the construction of CTMC for each classifier (Figure 3), we know that classes belong to one classifier communicates with each other. Hence, if the classifiers are connected, then all the classes communicate with each other, and thus the irreducibility follows.

This is a mild condition. For example, it is satisfied for all those classifiers relying on a softmax transform to produce a probabilistic output. The following proposition characterizes the behavior of the CTMC ensemble.

Proposition 2. Given a transition rate matrix Q defined by Equation (7), the overall prediction π has

Here, Fi refers to the set of all classifiers that cover ci.

Proof. Let aki = I(i ∈ Ik), then qij can be rewritten as

Here, we utilize a fact akiakj = aki when i = j. Hence, πQ can be expanded into

With πQ = 0, we then obtain

Swapping i and j results in Equation (9).

Proposition 2 shows that π(i) is a weighted combination of pk(i), the corresponding entry in the predictions from the classifiers that cover ci. Here, the combination weight ωk = ∑j∈Ik π(j), which equals the total probability mass that falls in its domain Ik, can be interpreted as the relevance of the classifier fk to the given sample. Note that π and ωk are mutually dependent. The optimal π can be considered as the fixed point of Equation (9), where the classifier relevances agree with the overall prediction. Under the special setting when all classifiers cover the same set of classes, we have:

Corollary 1. If every classifier covers the entire class space, then π equals the average of individual predictions,

This corollary follows immediately from Proposition 2. In particular, ωk = 1 for each k in this case. The next corollary demonstrates the power in stitching specialized classifiers.

Corollary 2. In Proposition 1, if all specialized classifiers are obtained by first restricting results from one given general classifier into their domain and then rescaling properly, then the output of CTMC exactly recovers this general classifier.

Proof. FromProposition 2, we know that the prediction from the general classifier is a solution. This is because in Equation 9, by the construction of specialized classifiers, we have π(i) = ωkpk(i) for all i and k. Then by Proposition 1, it is the unique solution.

For example in Figure 4, suppose that the two prediction vectors are (p1, p2, p3) = (0.7, 0.1, 0.2) and (q2, q3, q4) = (0.2, 0.4, 0.4). On their shared classes c2 and c3, the relative preferences are consistent, i.e. p2 : p3 = q2 : q3 = 1 : 2. The output of CTMC is (7, 1, 2, 2)/12. We can verify that the two predictions are the restricted version of the output. This shows that CTMC ensemble can find a coherent global picture if all local information collected from specialized classifiers do not contradict with each other.

4 Experiment

We tested the proposed method in comparison with mainstream baselines on two commonly used benchmarks, ILSVRC 2012 [Russakovsky et al., 2015], and CIFAR100 [Krizhevsky and Hinton, 2009]. The ILSVRC benchmark is constructed based on ImageNet, which contains 1.2M training images in 1000 classes, and 50K validation images for testing. The CIFAR-100 dataset consists of 60K images in 100 classes, of which 50K are for training and the other 10K are for testing.

The base classifiers used in our experiments are all deep Convolutional Neural Networks (CNNs), which all have a softmax layer on top of the final representations, and thus can directly output the probabilistic prediction vectors. Particularly, three network architectures are used in our experiments, namely ResNet-56 [He et al., 2016a], pre-activation ResNet101 [He et al., 2016b], and Inception-ResNet-v2 [Szegedy et al., 2016]. In this way, we can see how well the proposed method can work with different models.

We compared with several commonly used methods for classifier combination: (1) vote: each classifier votes for the class with highest probability, and choose the smaller index if there is a tie; (2) mean: averaging the prediction scores from all individual classifiers as output; (3) m-mean: multiplicityaware mean, where the prediction scores on individual classes are averages over only those covering classifiers; (4) prod: geometric mean of the prediction scores from all individual classifiers; (5) m-prod: multiplicity-aware product, where the geometric mean of prediction scores for each class is taken over only the covering classifiers. Here, m-mean and m-prod are natural way to mitigate the effect of unbalanced classifier coverage. Following the common practice, we measure the performances by top-1 and top-5 error rates.

4.1 Combining Specialized Classifiers

The primary goal of this work is to develop an effective approach to combining specialized classifiers, i.e. those that cover subsets of classes. The first experiment is to assess the effectiveness of the CTMC method on this task, in comparison with the baseline methods.

On ILSVRC We first conducted the experiment on ILSVRC. Specifically, for ILSVRC, we train 10 specialized classifiers f0, . . . , f9, each covering 300 classes. Adjacent classifiers, i.e. fk and fk+1 have 200 classes in common, as shown in Figure 5. For this experiment, we used a trimmed down version of Inception-ResNet-v2 [Szegedy et al., 2016] 1 . We followed the standard practice to train the networks, using random-crop augmentation, RMSProp [Tieleman and Hinton, 2012] with decay 0.9 and ϵ = 1.0, weight decay 0.0005, and batch size 512. The learning rate was initialized to 0.45 and scaled down by a factor 0.1 per 120K iterations. All experiments were terminated at iteration 250K to avoid overfitting.

Results obtained by combining different subsets of these specialized classifiers are shown in Table 1. For the first two rows of the table, the classifiers in the subset {f0, f2, . . . , f8} or {f1, f3, . . . , f9} are only minimally overlapped to form a connected graph, which establishes the basic performance. For the rows below, we gradually incorporate additional classifiers to increase the overlap.

From the results, we observed: (1) m-mean and m-prod, takes into account the factor of multiplicity under the condition of unbalanced coverage, yields better results than naive vote, mean and prod. Nevertheless, the CTMC method consistently outperforms all baseline methods, by considerable margins w.r.t. relative reduction of error rates compared to best baselines. (2) When increasing the number of classifiers and particularly the overlaps among them, we can observe steady improvement of the performance. (3) By combining all 10 specialized classifiers with the CTMC method, we obtained a top-1 error at 22.480% and top-5 error at 6.676%. To put the results into perspective, we also trained a general classifier using the same network structure and hyperparameters, which yields a top-1 error 24.542% and a top-5 error 7.224%. The relative reduction of top-1 and top-5 error rates are respectively 8.4% and 8.2%. This is a notable performance gain, considering the baseline was already very strong. This also suggests that combining specialized classifier is a viable way to boost performance.

1 We used a trimmed down version, so it fits our computational budget to train 10 networks. This version contains 3, 6, 3 blocks in A, B, and C regions as compared to original's 5, 10, 5.

On CIFAR-100 On CIFAR-100, we adopted different settings, as this dataset differs significantly from ImageNet. Specifically, we trained 20 specialized classifiers g0, . . . , g19, each covering 30 classes, and adjacent classifiers have 25 classes in common. As the image size here is much smaller (32 × 32), it suffices to use ResNet-56 as the base network. We followed the common practice to train the networks: data augmentation with random crop, SGD with momentum 0.9 and batch size 128, learning rates initialized to 0.1 and scaled down by 0.1 per 45K iterations, and weight decay 0.0005.

Table 2 shows the top-1 error rates obtained by combining different subsets of classifiers using different methods. We observed similar trends on CIFAR-100: CTMC method outperforms baseline methods consistently and significantly. Also, the performance generally improves as we increase the size of the ensemble and thus the overlap among classes (see the rows from top to bottom). Again, we trained a general classifier, which yields a top-1 error rate at 35.51%. The best error rate from an CTMC ensemble of specialized classifier is 32.42%, about 8.7% of relative reduction. However, we should also note that this reduction is achieved by combining many specialized classifiers. As shown in Table 2, when the minimal set of classifiers are combined, i.e. 4 specialized classifiers as in the first table block. the performance is not yet comparable to a well-trained general classifier. Albeit it defeats all other combining methods in the same table.

4.2 Ensemble Augmentation

We have seen that CTMC provides an effective means to combine specialized classifiers. In the following experiments, we study (1) whether we can obtain further performance gains by incorporating both general and specialized classifiers, and (2) if this is the case, what are the more effective strategies to configure a specialized ensemble.

We conducted the experiments on ILSVRC, and considered three configurations to generate specialized classifiers: (1) Random split. This baseline strategy randomly evenly splits the 1000 classes into 12 groups, and trains 12 specialized classifiers, each for one group. (2) Synset split. Each class in ILSVRC corresponds to a synset, which is a node in the wordnet hierarchy [Miller, 1995]. Therefore, we can exploit this hierarchical structure to group the classes, so that semantically related classes are brought together. Walking down along the hierarchy until reaching the nodes with moderate sub-tree sizes, we obtain 12 groups, which are listed below together with the number of classes contained therein: structures (55), materials (56), things (114), devices (122), homeware (106), vehicles (68), domestic (121), invertebrate (61), poultry (59), mammals (97), mollusc (60), and others (81). (3) Unbalanced. Both splits above use disjoint groups, and therefore each class will be covered by two classes (one general and one group-specific). In this split, we consider a setting with unbalanced coverage. Particularly, we select two large synset nodes, instrumentality (348) and animals (398), 20 small synsets, whose sizes are around 30, and 16 tiny synsets, whose sizes are below 10. These new synsets together with the 12 synsets in the synset split above result in a collection of 50 groups of classes. These groups may overlap with each other, and their sizes range from 4 to 398.

In the end, number of classes covered by 1/2/3/4 classifiers is 130/297/487/86.

In this experiment, we trained 3 general classifiers h0, h1 and h2, and multiple specialized classifiers, each for a group in the splits introduced above. For all these classifiers, including both the specialized classifiers and the general classifiers, we adopt the same pre-activation ResNet-101 architecture, modulo the difference in the last fully-connected layer, which is class number dependent. One same pre-trained model is used for the initialization. This setting is different from the ILSVRC experiment in Section 4.1 because the specialized classifiers in this experiment are finetuned from a well-trained general classifier; while those in the previous experiment are trained from scratch. Specifically, the training uses SGD with momentum 0.9 and weight decay 0.0005. Batch size is set to 200 for groups with over 50 classes or 128 for those smaller.

From the results shown in Table 3, we observed: (1) The CTMC method outperforms other combination methods in almost all settings. (2) The CTMC method generally obtains performance improvement when adding specialized methods, no matter whether the coverage is balanced or unbalanced. Other methods, including m-mean and m-prod, will see a significant performance degradation under the unbalanced condition. This clearly suggests a consistent reliability of the CTMC method. (3) The unbalanced setting which involves specialized classifiers trained on groups of different sizes yields the most significant gains using CTMC. This demonstrates the strength of the CTMC method in integrating very complex classifier configurations. Other methods all fail in such setting, resulting in performances even worse than the baseline. (4) If we remove the general classifier from the ensemble, the error rate sees a sharp rise for baseline methods, while for CTMC, the increase of error is quite moderate.

5 Conclusion

We presented a novel method for combining specialized classifiers based on the Continuous-Time Markov Chains (CTMC), which can reason about the relations among preferences conveyed by individual predictions, instead of just simply combining them. This allows it to work with diverse ensembles and the cases with unbalanced coverage.

We compared it with commonly used methods on two public benchmarks, ILSVRC and CIFAR-100. The proposed method consistent outperforms other methods under different settings. Especially when the ensemble is diverse and has unbalanced coverage, other methods failed (performing worse than a general classifier) while the CTMC method continues to bring performance improvement. These results clearly demonstrated the merits of the CTMC method - competitive performance and high reliability in complicated situations.

Acknowledgements

This work is partially supported by the Big Data Collaboration Research grant from SenseTime Group (CUHK Agreement No. TS1610626) and the General Research Fund (GRF) of Hong Kong (No. 14236516). We would like to thank Xingcheng Zhang for the artistic drawing of Figure 5.