Locally Adaptive Classification Piloted by Uncertainty

by Juan Dai, Shuicheng Yan, Xiaoou Tang and James T. Kwok

It is known that the region mixed with samples from different classes requires special attention in the classification task. So how should be model these regions? The authors propose a criteria for this property, uncertainty, which is simply the similarity of samples from other classes divided by the total similarity of the whole region(nearest L neighbors), where the similarity is analogous to that of Laplacian eigenmap(heat kernel). Then each sample is associated with an uncertainty factor. GMM is adopted to describe the distribution of the uncertainty. Here the only difference between the original GMM and the one here denoted as RMM is the log-likelihood function of the latter one is weighted by uncertainty factors.

But the model can still be trained with EM algorithms as with GMM. The RMM tells us the probability of each sample's membership of each Gaussian(cluster).

Then for each cluster, it is desired to find a linear transform(reduction) such that

the sum of correctly-classified probability weighted by the probability of membership of the corresponding cluster(c.f. the equation below)

is maximized. This objective function is not necessarily a convex one, so gradient descent with simulated annealing is applied.

To classify a testing sample, first find the probability of its membership of each cluster. And the class it belongs to is the one that maximizes correctly-classified probability weighted by the probability of membership of corresponding cluster.

This work is related to NCA(neighborhood component analysis) when the number of Gaussians is 1. And we might read something on loc boost(Localized boosting by Meir, R and et al.)

ps: These equations are copied from the original paper, thus copyrighted by the authors above.