Vector Quantization by Minimizing Kullback-Leibler Divergence

2015·Arxiv

Abstract

Abstract

This paper proposes a new method for vector quantization by minimizing the Kullback-Leibler Divergence between the class label distributions over the quantization inputs, which are original vectors, and the output, which is the quantization subsets of the vector set. In this way, the vector quantization output can keep as much information of the class label as possible. An objective function is constructed and we also developed an iterative algorithm to minimize it. The new method is evaluated on bag-of-features based image classification problem.

Keywords: Vector quantization, Kullback-Leibler Divergence, Bag-of-features, Image Classification

1 Introduction

Vector quantization is a problem to quantize the continuous signal vectors into a discrete dictionary [32,37,5,54,34,41]. The vectors are usually quantized into several discrete quantization subsets, and then the index of the subset will be used as its new representation [13,14]. It should compress the original vectors, and also be helpful for the effective representation of these vectors [17]. An example is the bag-of-features based image representation [18,28,51,2,15,38]. In this problem, the local image features are quantized to a visual dictionary. The quantization is usually conducted in an unsupervised way, assuming that the class labels are not available [35]. But it’s better to learn it by combining the class labels in a supervised way. The ideal quantization we are seeking is the one that can contains all the information needed for the classification [16,50,1,42].

In this paper, we present a new quantization algorithm so that the class label can be used. The algorithm is developed by first modeling the distribution of the class labels over the quantization input (the original vectors), and the distribution of the class labels over the quantization output (the quantization subsets), and then minimizing the Kullback-Leibler divergence between the two distributions [33,7,12,29,10,4,31,19,11]. We build an objective function to this end, which involvesthe quantization of the vectors. This idea is shown ni Fig. 1. Our method is motivated by Wang et al.’work [39], which learned the codebook for vector quantization in an supervised way. However, the differences are of tow-folds:

– Wang et al. [39] used the class label to define the margin and then maximize it, while we directly minimize the Kullback-Leibler divergence between the class label distributions over the quantization input and output.

– Wang et al. [39] implement the vector quantization by using a codebook, while we directly quantize the vectors into subsets without using a codebook.

Fig. 1. Minimizing the distribution of class labels over the original vectors and the quantization subsets.

The rest part of this paper is organized as follows: Section 2 introduce the proposed algorithm in details. Section 3 shows the evaluation of the proposed algorithm bag-of-features image classification. Finally, Section 6 concludes the paper.

2 Method

We first introduce the distribution of the class label over the vectors and the quantization subsets in Section 2.1 and then given the algorithm to minimis the Kullback-Leibler divergence between these distributions to quantize the vectors in Section 2.2.

2.1 Class label distributions

Assume we have a set of N labeled training data samples, denoted as . is the d-dimensional vector of the i-th sample, and is its corresponding class label. The classification problem is to predict the class label of a sample from its vector. To estimate the class label distribution over the vector, we define the p(y|x) as the conditional distribution of class label y over a sample vector x, where , and .

Class label distribution over input Given a input sample and a class label y, to estimate ), we first find its nearest neighbors [9,8,20,40,36],

and then

where

Class label distribution over output Then we quantize the vectors into M non-overlapping quantization subsets, denoted as , as shown in Fig. 2. Given subset , and a class label , the conditional distribution for y over is defined as

Kullback—Leibler divergence The Kullback—Leibler divergence between the two distributions ) and ) are defined as (5).

We try to have a quantization output from so that the the quantization can minimize the Kullback—Leibler divergence

To solve this problem, we adapted a iterative algorithm.

Fig. 2. Vector quantization from vectors to quantization subsets.

2.2 Interactive algorithm

In this algorithm, we repeat a two-step procedure for many times:

– In this first step, we fixe the quantization subset as , and com- pute the class label distribution over the quantization output as:

– In the second step, we fixe the distribution and update quantization subset by (8).

When a new sample x not in the training set is given, it is quantized to the quantization subset as

where

3 Experiment

Experimental evaluation is given in this section on a real data set with a bag-of-features based image classification problem. We use the Fifteen Natural Scene Categories database in this experiment [18]. There are 15 classes and for each class, there are around 200 or 300 images. We use the proposed vector quantization algorithm to represent the image as a quantization histogram under the bag-of-features framework.

Fig. 4 shows the results for the Fifteen Natural Scene Categories data set. The kmeans algorithm is used as a baseline quantization method [6,45,3,25,55,44]. As in Fig. 4 , the proposed method outperforms the the baseline method.

4 Conclusion

In this paper, the problem of vector quantization is investigated. The idea is motivated by the supervised quantization dictionary learning method proposed by Wang et al. [39]. We try to keep all information about the class label from the quantization input to the output. It is implemented by minimizing KullbackLeibler Divergence between the class label distributions over quantization input and output. This method can also be applied to social media data analysis [21,27,24], user recognition of mobile [26], transportation prediction [23,22], web news extraction [43], malicious websites detection [47,49,30,52,46,48,53].

Acknowledgements

This project was supported by a open research program of the Tianjin Key Laboratory of Cognitive Computing and Application, Tianjin University, China.

References

1. Abu-Mahfouz, I.: Drill flank wear estimation using supervised vector quantization neural networks. Neural Computing and Applications 14(3), 167–175 (2005)

Fig. 3. Images in the Fifteen Natural Scene Categories database.

2. Amato, G., Falchi, F., Gennaro, C.: On reducing the number of visual words in the bag-of-features representation. In: VISAPP 2013 - Proceedings of the International Conference on Computer Vision Theory and Applications. vol. 1, pp. 657–662 (2013)

Fig. 4. Classification results.

3. Barakbah, A., Kiyoki, Y.: A new approach for image segmentation using pillar- kmeans algorithm. World Academy of Science, Engineering and Technology 59, 23–28 (2009)

4. Belov, D.: Detection of test collusion via kullback-leibler divergence. Journal of Educational Measurement 50(2), 141–163 (2013)

5. Chang, C.C., Chou, Y.C., Lin, C.Y.: An indicator elimination method for side- match vector quantization. Journal of Information Hiding and Multimedia Signal Processing 4(4), 233–249 (2013)

6. Cuell, C., Bonsal, B.: An assessment of climatological synoptic typing by principal component analysis and kmeans clustering. Theoretical and Applied Climatology 98(3-4), 361–373 (2009)

7. Dahlhaus, R.: On the kullback-leibler information divergence of locally stationary processes1. Stochastic Processes and their Applications 62(1), 139–168 (1996)

8. Emrich, T., Kriegel, H.P., Kr¨oger, P., Niedermayer, J., Renz, M., Z¨ufle, A.: Reverse- k-nearest-neighbor join processing. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8098 LNCS, 277–294 (2013)

9. Frentzos, E., Pelekis, N., Giatrakos, N., Theodoridis, Y.: Cost models for nearest neighbor query processing over existentially uncertain spatial data. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8098 LNCS, 391–409 (2013)

10. Gofman, A., Kelbert, M.: Un upper bound for kullback-leibler divergence with a small number of outliers. Mathematical Communications 18(1), 75–78 (2013)

11. Harmouche, J., Delpha, C., Diallo, D.: Incipient fault detection and diagnosis based on kullback-leibler divergence using principal component analysis: Part i. Signal Processing 94(1), 278–287 (2014)

12. Hershey, J., Olsen, P.: Approximating the kullback leibler divergence between gaus- sian mixture models. vol. 4, pp. IV317–IV320 (2007)

13. J´egou, H., Douze, M., Schmid, C.: Improving bag-of-features for large scale image search. International Journal of Computer Vision 87(3), 316–336 (2010)

14. Jiang, Y.G., Ngo, C.W., Yang, J.: Towards optimal bag-of-features for object categorization and semantic video retrieval. pp. 494–501 (2007), cited By (since 1996)99

15. Kashihara, K.: Classification of individually pleasant images based on neural net- works with the bag of features. In: ICOT 2013 - 1st International Conference on Orange Technologies. pp. 291–293 (2013)

16. K¨astner, M., Villmann, T.: Fuzzy supervised self-organizing map for semi- supervised vector quantization. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7267 LNAI(PART 1), 256–265 (2012)

17. Lai, J., Liaw, Y.C.: A novel encoding algorithm for vector quantization using trans- formed codebook. Pattern Recognition 42(11), 3065–3070 (2009)

18. Lazebnik, S., Schmid, C., Ponce, J.: Beyond bags of features: Spatial pyramid matching for recognizing natural scene categories. vol. 2, pp. 2169–2178 (2006)

19. Lee, J., Renard, E., Bernard, G., Dupont, P., Verleysen, M.: Type 1 and 2 mixtures of kullback-leibler divergences as cost functions in dimensionality reduction based on similarity preservation. Neurocomputing 112, 92–108 (2013)

20. Lee, K.W., Choi, D.W., Chung, C.W.: Dart: An efficient method for direction- aware bichromatic reverse k nearest neighbor queries. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8098 LNCS, 295–311 (2013)

21. Li, H., Cao, T., Li, Z.: Learning the information diffusion probabilities by using variance regularized em algorithm. In: IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. pp. 273–280 (2014)

22. Li, H., Li, Z., White, R., Wu, X.: A real-time transportation prediction system. In: The 25th International Conference on Industrial, Engineering &. Other Applications of Applied Intelligent Systems, vol. 7345, pp. 68–77. Springer Berlin Heidelberg (2012)

23. Li, H., Li, Z., White, R.T., Wu, X.: A real-time transportation prediction system. Applied intelligence 39(4), 793–804 (2013)

24. Li, H., Wu, G.Q., Hu, X.G., Wu, X., Bi, Y.J., Li, P.P.: A relation extraction method of chinese named entities based on location and semantic features. In: IEEE International Conference on Granular Computing. pp. 334–339. IEEE (2009)

25. Li, H., Wu, G.Q., Hu, X.G., Zhang, J., Li, L., Wu, X.: K-means clustering with bagging and mapreduce. In: The 44th Hawaii International Conference on System Sciences. pp. 1–8. IEEE (2011)

26. Li, H., Wu, X., Li, Z.: Online learning with mobile sensor data for user recognition. In: The 29th Symposium On Applied Computing. pp. 64–70. ACM (2014)

27. Li, H., Wu, X., Li, Z., Wu, G.: A relation extraction method of chinese named entities based on location and semantic features. Applied Intelligence 38(1), 1–15 (2013)

28. Lian, Z., Godil, A., Sun, X., Xiao, J.: Cm-bof: visual similarity-based 3d shape re- trieval using clock matching and bag-of-features. Machine Vision and Applications pp. 1–20 (2013)

29. Liang, Z., Li, Y., Xia, S.: Adaptive weighted learning for linear regression problems via kullback-leibler divergence. Pattern Recognition 46(4), 1209–1219 (2013)

30. Luo, W., Xu, L., Zhan, Z., Zheng, Q., Xu, S.: Federated cloud security architecture for secure and agile clouds. In: High Performance Cloud Auditing and Applications, pp. 169–188. Springer (2014)

31. Park, S., Shin, M.: Kullback-leibler information of a censored variable and its applications. Statistics (2013)

32. Pham, T., Brandl, M., Beck, D.: Fuzzy declustering-based vector quantization. Pattern Recognition 42(11), 2570–2577 (2009)

33. Rached, Z., Alajaji, F., Campbell, L.: The kullback-leibler divergence rate between markov sources. IEEE Transactions on Information Theory 50(5), 917–921 (2004)

34. Singh, A., Murthy, K.: Neuro-curvelet model for efficient image compression using vector quantization. Lecture Notes in Electrical Engineering 258 LNEE, 179–185 (2013)

35. Sprechmann, P., Sapiro, G.: Dictionary learning and sparse coding for unsupervised clustering. pp. 2042–2045 (2010)

36. Taniar, D., Rahayu, W.: A taxonomy for nearest neighbour queries in spatial databases. Journal of Computer and System Sciences 79(7), 1017–1039 (2013)

37. Tasdemir, K.: Vector quantization based approximate spectral clustering of large datasets. Pattern Recognition 45(8), 3034–3044 (2012)

38. Wang, C., Zhang, B., Qin, Z., Xiong, J.: Spatial weighting for bag-of-features based image retrieval. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8032 LNAI, 91–100 (2013)

39. Wang, J.J.Y., Bensmail, H., Gao, X.: Joint learning and weighting of visual vo- cabulary for bag-of-feature based tissue classification. Pattern Recognition 46(12), 3249–3255 (2013)

40. Wang, J.S., Lin, C.W., Yang, Y.: A k-nearest-neighbor classifier with heart rate variability feature-based transformation algorithm for driving stress recognition. Neurocomputing 116, 136–143 (2013)

41. Wang, W.J., Huang, C.T., Liu, C.M., Su, P.C., Wang, S.J.: Data embedding for vector quantization image processing on the basis of adjoining state-codebook mapping. Information Sciences 246, 69–82 (2013)

42. Wang, Y., Jiang, W., Agrawal, G.: SciMATE: A Novel MapReduce-Like Frame- work for Multiple Scientific Data Formats. In: Cluster, Cloud and Grid Computing (CCGrid), 2012 12th IEEE/ACM International Symposium on. pp. 443–450. IEEE (2012)

43. Wu, G.Q., Wu, X., Hu, X.G., Li, H., Liu, Y., Xu, R.G.: Web news extraction based on path pattern mining. In: The Sixth International Conference on Fuzzy Systems and Knowledge Discovery. vol. 7, pp. 612–617. IEEE (2009)

44. Wu, G., Li, H., Hu, X., Bi, Y., Zhang, J., Wu, X.: Mrec4. 5: C4. 5 ensemble classification with mapreduce. In: The Fourth ChinaGrid Annual Conference. pp. 249–255. IEEE (2009)

45. Xu, J., Liu, H.: Web user clustering analysis based on kmeans algorithm. vol. 2, pp. V26–V29 (2010)

46. Xu, L., Zhan, Z., Xu, S., Ye, K.: Cross-layer detection of malicious websites. In: CODASPY 2013 - Proceedings of the 3rd ACM Conference on Data and Application Security and Privacy. pp. 141–152 (2013)

47. Xu, L., Zhan, Z., Xu, S., Ye, K.: An evasion and counter-evasion study in malicious websites detection. In: Communications and Network Security (CNS), 2014 IEEE Conference on. pp. 265–273. IEEE (2014)

48. Xu, S., Lu, W., Zhan, Z.: A stochastic model of multivirus dynamics. IEEE Trans- actions on Dependable and Secure Computing 9(1), 30–45 (2012)

49. Xu, S., Lu, W., Xu, L., Zhan, Z.: Adaptive epidemic dynamics in networks: Thresholds and control. ACM Transactions on Autonomous and Adaptive Systems (TAAS) 8(4), 19 (2014)

50. Yu, G., Russell, W., Schwartz, R., Makhoul, J.: Discriminant analysis and super- vised vector quantization for continuous speech recognition. vol. 2, pp. 681–688 (1990)

51. Yu, J., Qin, Z., Wan, T., Zhang, X.: Feature integration analysis of bag-of-features model for image retrieval. Neurocomputing (2013)

52. Zhan, Z., Xu, M., Xu, S.: Characterizing honeypot-captured cyber attacks: Statis- tical framework and case study. IEEE Transactions on Information Forensics and Security 8(11), 1775–1789 (2013)

53. Zhan, Z., Xu, M., Xu, S.: A characterization of cybersecurity posture from network telescope data. In: Proceedings of The 6th International Conference on Trustworthy Systems, InTrust. vol. 14

54. Zhang, B., Zhou, Y., Pan, H.: Vehicle classification with confidence by classified vector quantization. IEEE Intelligent Transportation Systems Magazine 5(3), 8–20 (2013)

55. Zhang, J., Wu, G., Li, H., Hu, X., Wu, X.: A 2-tier clustering algorithm with mapreduce. In: The Fifth Annual ChinaGrid Conference. pp. 160–166. IEEE (2010)

designed for accessibility and to further open science