Dual diffusion model of spreading activation for content-based image retrieval

ABSTRACT

This paper introduces a content-based information retrieval method inspired by the ideas of spreading activation models. In response to a given query,the proposed approach computes document ranks as their final activation values obtained upon completion of a diffusion process. This diffusion process,in turn,is dual in the sense that it models the spreading of the query 's initial activation simultaneously in two similarity domains: low-level feature-based and high-level semantic.The formulation of the diffusion process relies on an approximation that makes it possible to compute the final activation as a solution to a linear system of differential equations via a matrix exponential without the need to resort to an iterative simulation.The latter calculation is performed efficiently by adapting a sparse routine based on Krylov sub-space projection method.The empirical performance of the described dual diffusion model has been evaluated in terms of precision and recall on the task of content-based digital image retrieval in query-by-example scenario. The obtained experimental results demonstrate that the proposed method achieves better overall performance compared to traditional feature-based approaches. This performance improvement is attained not only when both similarity domains are used, but also when a diffusion model operates only on the feature-based similarities.

REFERENCES

• 1: Dipti Aswath , Syed Toufeeq Ahmed , James D'cunha , Hasan Davulcu, Boosting Item Keyword Search with Spreading Activation, Proceedings of the The 2005 IEEE/WIC/ACM International Conference on Web Intelligence (WI'05), p.704-707, September 19-22, 2005 [doi>10.1109/WI.2005.44]
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: J.-Y. Bouguet, C. Dulong, I. Kozintsev, and Y. Wu. Requirements for benchmarking personal image retrieval systems. In S. Santini, R. Schettini, and T.Gevers, editors, Proceedings of SPIE Photonics West, Electronic Imaging volume 6061. SPIE, 2006.
• 4: C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines 2001. Software available at http://www.csie.ntu.edu.tw/¿cjlin/libsvm.
• 5: F. Crestani, Application of Spreading Activation Techniques in InformationRetrieval, Artificial Intelligence Review, v.11 n.6, p.453-482, Dec. 1997 [doi>10.1023/A:1006569829653]
• 6: Fabio Crestani , Puay Leng Lee, Searching the Web by constrained spreading activation, Information Processing and Management: an International Journal, v.36 n.4, p.585-605, July 2000 [doi>10.1016/S0306-4573(99)00073-4]
• 7: Nello Cristianini , John Shawe-Taylor , Huma Lodhi, Latent Semantic Kernels, Journal of Intelligent Information Systems, v.18 n.2-3, p.127-152, March-May 2002 [doi>10.1023/A:1013625426931]
• 8: S. Deerwester, S. Dumais, G. Furnas, T. Landauer, and R. Harshman. Indexing by latent semantic analisys.Journal of the American Society of Information Science 41(6):391--407, 1990.
• 9: King-Shy Goh , Edward Y. Chang , Beitao Li, Using One-Class and Two-Class SVMs for Multiclass Image Annotation, IEEE Transactions on Knowledge and Data Engineering, v.17 n.10, p.1333-1346, October 2005 [doi>10.1109/TKDE.2005.170]
• 10: B. Haasdonk and C. Bahlmann. Learning with distance substitution kernels. In 26th Pattern Recognition Symposium of the German Association for Pattern Recognition (DAGM 2004)Tübingen, Germany, 2004. Springer Verlag.
• 11: Marlis Hochbruck , Christian Lubich, On Krylov Subspace Approximations to the Matrix Exponential Operator, SIAM Journal on Numerical Analysis, v.34 n.5, p.1911-1925, Oct. 1997 [doi>10.1137/S0036142995280572]
• 12: Jing Huang , S. Ravi Kumar , Mandar Mitra , Wei-Jing Zhu , Ramin Zabih, Image Indexing Using Color Correlograms, Proceedings of the 1997 Conference on Computer Vision and Pattern Recognition (CVPR '97), p.762, June 17-19, 1997
• 13: J. Kandola, J. Shawe-Taylor, and N. Cristianini. Learning semantic similarity. In S. T. S. Becker and K. Obermayer, editors, Advances in Neural Information Processing Systems 15 pages 657--664. MIT Press, Cambridge, MA, 2003.
• 14: Risi Imre Kondor , John D. Lafferty, Diffusion Kernels on Graphs and Other Discrete Input Spaces, Proceedings of the Nineteenth International Conference on Machine Learning, p.315-322, July 08-12, 2002
• 15: Mark Magennis , Cornelis J. van Rijsbergen, The potential and actual effectiveness of interactive query expansion, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.324-332, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 16: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 17: B. R. Munson, D. F. Young,and T. H. Okiishi. Fundamentals of Fluid Mechanics John Wiley & Sons,1990.
• 18: Scott Everett Preece, A spreading activation network model for information retrieval, 1981
• 19: P. Resnik. Using information content to evaluate semantic similarity in a taxonomy. In International Joint Conference for Artificial Intelligence (IJCAI-95) pages 448--453, 1995.
• 20: D. E. Rumelhart and D. A. Norman. Representation in memory. In Steven's handbook of experimental psychology volume 2, pages 511--587. Wiley, 1988.
• 21: Gerard. Salton, Automatic Information Organization and Retrieval., McGraw Hill Text, 1968
• 22: G. Salton , C. Buckley, On the use of spreading activation methods in automatic information, Proceedings of the 11th annual international ACM SIGIR conference on Research and development in information retrieval, p.147-160, May 1988, Grenoble, France [doi>10.1145/62437.62447]
• 23: Bernhard Schölkopf , John C. Platt , John C. Shawe-Taylor , Alex J. Smola , Robert C. Williamson, Estimating the Support of a High-Dimensional Distribution, Neural Computation, v.13 n.7, p.1443-1471, July 2001 [doi>10.1162/089976601750264965]
• 24: Roger B. Sidje, Expokit: a software package for computing matrix exponentials, ACM Transactions on Mathematical Software (TOMS), v.24 n.1, p.130-156, March 1998 [doi>10.1145/285861.285868]
• 25: Georges Siolas , Florence d'Alché-Buc, Support Vector Machines Based on a Semantic Kernel for Text Categorization, Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks (IJCNN'00)-Volume 5, p.5205, July 24-27, 2000
• 26: D. M. J. Tax. Ddtools, the data description toolbox for matlab, June 2006. version 1.5.3.
• 27: David M. J. Tax , Robert P. W. Duin, Support Vector Data Description, Machine Learning, v.54 n.1, p.45-66, January 2004 [doi>10.1023/B:MACH.0000008084.60811.49]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Initial value problems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.8 Scene Analysis
          Subjects: Object recognition

General Terms:
Algorithms, Experimentation, Performance

Keywords:
diffusion models, semantic similarity, spreading activation