Coevolutionary feature synthesized EM algorithm for image retrieval

ABSTRACT

As a commonly used unsupervised learning algorithm in Content-Based Image Retrieval (CBIR), Expectation-Maximization (EM) algorithm has several limitations, especially in high dimensional feature spaces where the data are limited and the computational cost varies exponentially with the number of feature dimensions. Moreover, the convergence is guaranteed only at a local maximum. In this paper, we propose a unified framework of a novel learning approach, namely Coevolutionary Feature Synthesized Expectation-Maximization (CFS-EM), to achieve satisfactory learning in spite of these difficulties. The CFS-EM is a hybrid of coevolutionary genetic programming (CGP) and EM algorithm. The advantages of CFS-EM are: 1) it synthesizes low-dimensional features based on CGP algorithm, which yields near optimal nonlinear transformation and classification precision comparable to kernel methods such as the support vector machine (SVM); 2) the explicitness of feature transformation is especially suitable for image retrieval because the images can be searched in the synthesized low-dimensional space, while kernel-based methods have to make classification computation in the original high-dimensional space; 3) the unlabeled data can be boosted with the help of the class distribution learning using CGP feature synthesis approach. Experimental results show that CFS-EM outperforms pure EM and CGP alone, and is comparable to SVM in the sense of classification. It is computationally more efficient than SVM in query phase. Moreover, it has a high likelihood that it will jump out of a local maximum to provide near optimal results and a better estimation of parameters.

REFERENCES

• 1: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 2: Ron Meir , Gunnar Rätsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
• 3: Simon Tong , Edward Chang, Support vector machine active learning for image retrieval, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500159]
• 4: T. Hertz, N. Shental, A. Bar-Hillel and D. Weinshall, "Enhancing image and video retrieval: learning via equivalence constraint," IEEE Conf. on CVPR, pp. 668--674, 2003.
• 5: Q. Tian, J. Yu, Q. Xue and N. Sebe, "A new analysis of the value of unlabeled data in semi-supervised learning for image retrieval," ICME, 2004.
• 6: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 7: Bernhard Scholkopf , Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, 2001
• 8: G. Baudat , F. Anouar, Generalized Discriminant Analysis Using a Kernel Approach, Neural Computation, v.12 n.10, p.2385-2404, October 2000 [doi>10.1162/089976600300014980]
• 9: Daniel L. Swets , Juyang Weng, Hierarchical Discriminant Analysis for Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.21 n.5, p.386-401, May 1999 [doi>10.1109/34.765652]
• 10: Zhong Su , Stan Li , Hongjiang Zhang, Extraction of feature subspaces for content-based retrieval using relevance feedback, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada [doi>10.1145/500141.500158]
• 11: P. Wu, B. S. Manjunath, and H. D. Shin, "Dimensionality reduction for image search and retrieval," Proc. Int Conf. Image Processing, 2000.
• 12: D. D. Lee and H. S. Seung, "Learning the parts of objects by non-negative matrix factorization," Nature, vol. 401, pp. 788--791, 1999.
• 13: S. Z. Li, X.W. Hou, H.J. Zhang and Q.S. Cheng, "Learning spatially localized, parts-based representation," IEEE Conf. on CVPR, pp. 207--212, 2001.
• 14: Wei Xu , Xin Liu , Yihong Gong, Document clustering based on non-negative matrix factorization, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860485]
• 15: Ron Meir , Gunnar Rätsch, An introduction to boosting and leveraging, Advanced lectures on machine learning, Springer-Verlag New York, Inc., New York, NY, 2003
• 16: Kinh Tieu , Paul Viola, Boosting Image Retrieval, International Journal of Computer Vision, v.56 n.1-2, p.17-36, January-February 2004 [doi>10.1023/B:VISI.0000004830.93820.78]
• 17: A. Torralba, K.P. Murphy and W.T. Freeman, "Sharing features: efficient boosting procedures for multiclass," IEEE Conf. on CVPR pp. 762--769, 2004.
• 18: Xiaofei He , Shuicheng Yan , Yuxiao Hu , Hong-Jiang Zhang, Learning a Locality Preserving Subspace for Visual Recognition, Proceedings of the Ninth IEEE International Conference on Computer Vision, p.385, October 13-16, 2003
• 19: Xiaofei He , Wei-Ying Ma , Hong-Jiang Zhang, Learning an image manifold for retrieval, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027532]
• 20: Anlei Dong , Bir Bhanu , Yingqiang Lin, Evolutionary Feature Synthesis for Image Databases, Proceedings of the Seventh IEEE Workshops on Application of Computer Vision (WACV/MOTION'05) - Volume 1, p.330-335, January 05-07, 2005 [doi>10.1109/ACVMOT.2005.50]
• 21: A. Dempster, N. Laird, and D. Rubin, "Maximum Likelihood Estimation from Incomplete Data Via the EM algorithm," J. Royal Statistical Soc. B, vol.39, pp.1--38, 1977.
• 22: G. McLachlan and D. Peel, Finite Mixture Models. New York John Wiley & Sons, 1997.
• 23: http://www.corel.com, 2005
• 24: B. S. Manjunath , W. Y. Ma, Texture Features for Browsing and Retrieval of Image Data, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.8, p.837-842, August 1996 [doi>10.1109/34.531803]
• 25: X.S. Zhou, Y. Rui, and T.S. Huang, Exploration of Visual Data, Kluwer Academic Publishers, 2003.
• 26: J Grefenstette, Optimization of control parameters for genetic algorithms, IEEE Transactions on Systems, Man and Cybernetics, v.16 n.1, p.122-128, Jan./Feb. 1986 [doi>10.1109/TSMC.1986.289288]
• 27: A.E. Eiben, R. Hinterding, and Z. Michalewicz, "Parameter control in evolutionary algorithms", IEEE Transactions on Evolutionary Computation, 3(2): 124--141, 1999.
• 28: Mario A. T. Figueiredo , Anil K. Jain, Unsupervised Learning of Finite Mixture Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.3, p.381-396, March 2002 [doi>10.1109/34.990138]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

General Terms:
Algorithms, Experimentation

Keywords:
coevolutionary feature synthesis, content-based image retrieval, expectation maximization algorithm, genetic programming, semi-supervised learning