Probabilistic Classification Vector Machine for Multi-Class Classification

The formulation of the PCVM with binary classification will be given as follows:

where $\Psi(\cdot)$ is the Gaussian cumulative distribution function, and $\bm{\phi}(\bm{x})=[\phi_{1}(\bm{x}),\phi_{2}(\bm{x}),...,\phi_{N}(\bm{x})]^{\mathrm{T}}$ the basis function. If ${\bm{\phi}}(\bm{x})^{\rm T}{\bm{w}}+b$ is greater than 0, the datum is more likely to be in class $2$ than class $1$ ²²2We use class {1, 2} here instead of {-1, +1} to be compatible with multi-class cases. . The PCVM makes use of a truncated Gaussian prior to constrain weights of basis functions of the class 1 to be nonpositive and weights of basis functions of the class 2 to be nonnegative, in order to be consistent with the SVM [19].

For multi-class cases, we assign a set of independent weights to each class and extend the idea of the PCVM such that weights of basis functions of the class $c\in\{1,2,...,C\}$ in the $c$-th weight column vector (denoted as $\bm{w}_{c}$) are restricted as nonnegative for training samples in the class $c$ and nonpositive otherwise. The definition of the multi-class classification principle for the mPCVM is given as below.

Definition 1. Given multi-class data $D={\{\bm{x}_{n},t_{n}\}}_{n=1}^{N}$ with the class labels $(1,2,...,C)$. The multi-class classification principle for the mPCVM is that the weight ${w}_{nc}$ of a datum $(\bm{x}_{n},t_{n})$ is consistent with the class labels if

With this principle, weights are consistent with class labels like binary classification. Further, a class-based potential $y_{nc}$ for a training datum ($\bm{x}_{n},t_{n}$) is defined as

where ${b}_{c}$ is the bias for the $c$-th class. Subsequently, for data $(\bm{X},\bm{t})$, where $\bm{X}=(\bm{x}_{1},\bm{x}_{2},...,\bm{x}_{N})$ and $\bm{t}=(t_{1},t_{2},...,t_{N})^{\mathrm{T}}$, we have

where $\bm{W}=(\bm{w_{1}},\bm{w_{2}},...,\bm{w_{C}})$, $\bm{b}=(b_{1},b_{2},...,b_{C})^{\mathrm{T}}$, $\bm{\Phi}=(\bm{\phi}(\bm{x}_{1}),\bm{\phi}(\bm{x}_{2}),...,\bm{\phi}(\bm{x}_{N}))^{\rm T}$, and $\bm{1}$ is an all-1 vertical vector.

For any $\bm{x}_{n}$, the predicted class is determined by $\mathop{\arg\max}_{c}\{y_{nc}\}$. Following the procedure in [20], the term $y_{nc}$ in Eq. 4 is assumed to be coupled with an auxiliary random variable, which is denoted as $z_{nc}$

where $\varepsilon_{nc}$ obeys a standard normal distribution (i.e., $\varepsilon_{nc}\sim\mathcal{N}(0,1)$). The joint distribution of $\bm{Z}$ is given as

The connection of noisy term $\bm{z_{n}}$ to the target $t_{n}$ as defined in multinomial probit regression [18] is formulated as $t_{n}=i$ if $z_{ni}>z_{nj},\forall j\neq i$. Sequentially, the joint probability between $t_{n}=i$ and $\bm{z_{n}}$ is

where $\delta(\cdot)$ is the indicator function. And we have

By marginalizing the noisy potential $\bm{z_{n}}$, the multinomial probit is obtained as (more details in Appendix 5.2)

And we have

As discussed in Section 2.1, for the sake of ensuring the multi-class classification principle, the left-truncated Gaussian prior [21] and the right-truncated Gaussian prior over weights are chosen. Their distributions are formulated in Eq. 12 and illustrated in Fig. 1

where ${\alpha}_{nc}$ is the inverse variance and $f_{nc}=1$ if $t_{n}=c$ otherwise $-1$.

Then, the prior distribution over the weight $\bm{W}$ is

where $\bm{A}$ is the matrix extension of $\alpha_{nc}$ (i.e., $\bm{A}\in\mathbb{R}^{N\times C}$).

We impose no further restriction to the bias term $b_{c}$, so a normal zero-mean Gaussian prior is proper

where ${\beta}_{c}$ is the inverse variance and $\bm{\beta}$ the vertical stacking vector of ${\beta}_{c}$’s.

To follow the Bayesian framework and encourage the model sparsity, hyper-priors over $\bm{A}$ and $\bm{\beta}$ need be defined. The truncated Gaussian belongs to the exponential family and the conjugate distribution of the variance of the truncated Gaussian is the Gamma distribution (more details in Appendix 5.1). The conjugate prior in this paper is introduced for the reason that it is very convenient and belongs to analytically favorable class of subjective priors to the exponential family. Other priors are also alternative such as objective priors and empirical priors [22]. In the optimization procedure of our experiments, most of the weights will converge to zero.

The forms of Gamma prior distributions are presented as

and

where $(u_{1},v_{1})$ and $(u_{2},v_{2})$ are hyper-parameters of the Gamma hyper-priors. With these assumptions in place, marginalizing with respect to ${\alpha}_{nc}$, we get the complete prior over the weight $w_{nc}$

For the bias $b_{c}$, similar to $w_{nc}$, its prior distribution is

To make these priors non-informative, we fix $u_{1},u_{2},v_{1}$ and $v_{2}$ to small values [3, 23]. The plate graph of our proposed model is shown in Fig. 2.

This subsection presents the algorithm mPCVM₁ by means of the derivation of the expectation-maximization (EM) [24] algorithm that is a general algorithm for the MAP estimation in the situation where observations are incomplete. In the following part, we detail an expectation (E) step and a maximization (M) step of the mPCVM₁.

The joint posterior probability for $\bm{W}$ and $\bm{b}$ is first estimated in the E-step. The posterior probability is expressed as

Equivalently, the log-posterior is obtained as

where $\bm{z}_{c}$, $\bm{w}_{c}$ and $\bm{\alpha}_{c}$ are the $c$-th columns of $\bm{Z}$, $\bm{W}$ and $\bm{A}$, respectively, and $\bm{A}_{c}$ = diag($\bm{\alpha}_{c}$), $\bm{B}$ = diag($\bm{\beta}$) diagonal matrices.

Note that a normal zero-mean Gaussian prior over $\bm{W}$ is used in Eq. 20 for simplicity of computation. The multi-class classification principle for the mPCVM is ensured in Eq. 24

A constructive framework for fast marginal likelihood maximization is proposed in [7] and is extended to the mRVMs in [17] where each sample $n$ is assumed to have the same $\alpha_{n}$ for all classes. Following this framework, we propose the mPCVM₂ that ensures the multi-class classification principle as the mPCVM₁. Since a sample that belongs to a special class is unequally contributed in the predication of classes, we assume that each sample has distinct $\alpha_{nc}$ about each class.

For conciseness, we only consider the weight $\bm{W}$ and ignore the bias $\bm{b}$ by setting $\bm{b}=\bm{0}$. The posterior of $\bm{W}$ is given as

where $\bm{F_{c}}=$ diag$(f_{1c},f_{2c},...,f_{Nc})$. So the MAP for ${w_{nc}}$ could be estimated as

In the mPCVM₂, firstly we compute the marginal likelihood of $p(\bm{Z}|\bm{A})=\int p(\bm{Z}|\bm{W})p(\bm{W}|\bm{A})d\bm{W}$ with respect to $\bm{W}$. We formulate the marginal likelihood, or equivalently, its logarithm $\mathcal{L}(\bm{A})$:

where $\bm{\mathcal{C}}_{c}=\bm{I}+\bm{\Phi}{\rm diag(\bm{\alpha_{c}})}^{-1}\bm{\Phi}^{\rm T}$ and $\bm{I}$ is the identity matrix. Note that we assume $w_{nc}$ is subject to a truncated Gaussian with a scale $\alpha_{nc}$.

Then following the procedure of [7], we decompose $\bm{\mathcal{C}}_{c}$ as

where ${\bm{\mathcal{C}}_{c}}_{\,-n}^{\,}$ is ${\bm{\mathcal{C}}_{c}}$ without the contribution of $\bm{\phi}(\bm{x}_{n})$. Furthermore, the determinant and the inverse of $\bm{\mathcal{C}}_{c}$ could be decomposed as

As everything is ready, $\mathcal{L}(\bm{A})$ is derived as:

where we have the “sparsity factor”

and the “quality factor”

By decomposing $\mathcal{L}(\bm{A})$, we isolate the term $l(\alpha_{nc})$ that is the contribution of $\alpha_{nc}$ to this marginal likelihood. Analytically, $\mathcal{L}(\bm{A})$ has a unique maximum with respect to $\alpha_{nc}$

The pseudo code of the mPCVM₂ can be summarized in Algorithm 2.

Comparing the mPCVM₂ with the mPCVM₁, there are four main differences. Firstly, they possess different object functions. The mPCVM₁ maximizes a posterior estimation while the mPCVM₂ maximizes the marginal likelihood. Secondly, they have different initial states. The mPCVM₁ initially contains all vectors in the model while the mPCVM₂ has only one vector for each class. Thirdly, they use very different update strategies. In each iteration, the mPCVM₁ gradually deletes the vectors that are related with large $\alpha$’s, while exterior vectors can be added or vectors that already exist can be deleted in the mPCVM₂. Finally, they treat basis functions differently. The mPCVM₁ considers a vector only once. So basis functions that have been deleted cannot be added anymore. Conversely, the mPCVM₂ might add a basis function that has been removed recently. Hence, the number of iterations of the mPCVM₁ may be comparably less than the mPCVM₂. However, the distinguishing characteristic that the mPCVM₂ can re-add the vectors that have been wrongly deleted in the previous iterations, makes it more likely to escape some local optima and gets higher accuracy. In a word, the mPCVM₁ executes in a top-down fashion while the mPCVM₂ is like a bottom-up one.

This subsection presents experimental results of the mPCVM₁, the mPCVM₂, the mRVM₁ and the mRVM₂ on two synthetic data sets, i.e., Overlap and Overclass, to analyze their differences.

The data set Overlap is generated from several different 2-dimensional Gaussian distributions. It contains 3 classes but exhibits heavy overlaps. In this case, a nonlinear classifier is necessary. We compare four algorithms on this data set and mark the resulting class regions with different colors. The relevant vectors are marked with circles.

In Fig. 3, although the mRVM₁ spots the leftmost pivotal relevant vector that belongs to the blue class and locates in the narrow gap between two clusters in red, this blue key point contributes wrongly to the red class instead of the blue class, resulting in an erroneous classification boundary. We infer that the violation of the multi-class classification principle for the mPCVM proposed in Section 2.1 leads to the degradation of the mRVMs although the mRVM₂ avoids this vulnerability. In contrast, the mPCVMs, which aim to ensure this principle, manage to get correct regions. Meanwhile, the leftmost pivotal blue point should contribute positively to the blue class, contribute negatively to the red class and contribute nothing to the black class. However, this point is regarded as a relevant vector for all classes in the mRVMs. Its influence on the black class could be uncontrollable noise in this case. In other words, a point as a relevant vector should be only for one or two rather than all classes, which is apparent in a case with a large number of classes. Finally, although the mRVMs have less relevant vectors (the mRVM₁ 9, the mRVM₂ 7) than the mPCVMs (the mPCVM₁ 21, the mPCVM₂ 7), in the view of non-zero weights, the mPCVMs (the mPCVM₁ 21, the mPCVM₂ 7) are sparser than the mRVMs (the mRVM₁ 27, the mRVM₂ 21). We argue that the mPCVMs are superior to the mRVMs for the reason that the mPCVMs choose precisely relevant vectors for each class and impede unnecessary noise.

The second synthetic data set, Overclass, has 127 points in ten classes. The challenge of this data is the high imbalance over classes. The minor class (pink) has only 3 points while the major class (gray) contains 28 points, over 9 times more than those in the minor class.

We conducted an experiment on Overclass with four algorithms. In Fig. 4, four algorithms dye every region that is deemed to belong to a certain class with a separate color. In the current experimental setting, the mRVMs ignore erroneously the minor class and consider the pink class to be a part of the crimson class. The area of the brown class is narrowed down into a band as its sample size is relatively small. However, in our algorithms, each class contributes equally to the classification boundary. In other words, the classification is unlikely to be affected by the sample size of each class. This property gives the mPCVMs an advantage when they are applied in the experiment where a large number of classes exists yet the class size is imbalanced.

Table 1 lists the number of relevant vectors and the number of non-zero weights for the four learning algorithms. Since the absence of relevant vectors belonging to the pink class (class 10) and the brown class (class 6), the mRVMs cannot separate out the two classes. The classification boundaries in the mRVM₁ and the mRVM₂ are almost linear while those in the mPCVM₁ and the mPCVM₂ are mostly curved. The results show that the mRVM₁, the mRVM₂, the mPCVM₁, and the mPCVM₂ have 28, 16, 58, and 13 relevant vectors, respectively. Each relevant vector in the mRVMs has 10 non-zero weights as there are ten classes. So the mRVM₁ and the mRVM₂ have 280 and 160 non-zero weights, respectively, while the mPCVM₁ and the mPCVM₂ have 76 and 13 non-zero weights, respectively. Therefore, the mPCVMs are sparser than the mRVMs.

In order to evaluate the performance of the mPCVMs, we compare different algorithms on 8 benchmark data sets³³3https://archive.ics.uci.edu/ml/index.php. The information of these data sets is summarized in Table 2. We partition randomly every data set into a training set and a test set if no pre-partition exists. In addition, standardization is conducted dimensionwise on the training set and the test set. The comparison algorithms include the mRVM₁ [25], the mRVM₂ [25], the SVM [10], the DLSR [16] and the MLR. As the mPCVM₁ and the mPCVM₂ need to set the RBF kernel parameter $\theta$, we follow the method suggested in [26]. The hyper-parameter is tuned in the first five partitions and the best one is picked according to the mean accuracy on the five partitions. Then, the performance is measured on the remaining 45 partitions.

In our experiment, we select the ERR and the generalized AUC [27] as metrics to measure performance of these algorithms. The ERR reports classification error rates of algorithms. The generalized AUC complements the ERR in measuring the performance of algorithms in imbalanced cases. The overall performance of an algorithm is measured using the AUC metric:

where $\hat{A}(i,j)=[\hat{A}(i|j)+\hat{A}(j|i)]/2$ is the measure of separability between the $i$-th class and the $j$-th one. $\hat{A}(i|j)$ denotes the probability that a sample from the $j$-th class is misclassified into the $i$-th one, where $i,j\in\{1,2,...,C\}$. When $C$ equals to 2, $\hat{A}(1|2)=\hat{A}(2|1)$, the generalized AUC is equivalent to the traditional AUC. Notationally, we use the AUC instead of the AUC_generalized for succinctness.