№2, 2012

QUADRATIC BOOLEAN PROGRAMMING MODEL AND BINARY DIFFERENTIAL EVOLUTION ALGORITHM FOR TEXT SUMMARIZATION

Alguliev R.M., Aliguliyev R.M., Hajirahimova M.S.

We model multi-document summarization as a Quadratic Boolean Programing (QBP) problem where the objective function is a weighted combination of the content coverage and redundancy objectives. The objective function measures the possible summaries based on the identified salient sentences and overlap information between selected sentences. An innovative aspect of our model lies in its ability to remove redundancy while selecting representative sentences. The QBP problem has been solved by using a binary differential evolution algorithm. (pp. 20-29)

Keywords: text summarization, maximum coverage, less redundancy, optimization model, differential evolution algorithm
References
  • Hung S.Y., Tang K.Z., Chang C.M., Ke C.D. User acceptance of intergovernmental services: an example of electronic document management system // Government Information Quarterly, 2009, vol.26, №2, pp. 387–397.
  • Ko Y. and Seo J. An effective sentence-extraction technique using contextual information and statistical approaches for text summarization // Pattern Recognition Letters, 2008, vol.29, №9, pp.1366–1371.
  • Mani I. and Maybury M.T. Advances in automatic text summarization, MIT Press, Cambridge, 1999, 442 pp.
  • Ouyang Y., Li W., Li S., Lu Q. Applying regression models to query-focused multi-document summarization // Information Processing & Management, 2011, vol.47, №2, pp.227–237.
  • Kutlu M., Cigir C., Cicekli I. Generic text summarization for Turkish // The Computer Journal, 2010, vol.53, №8, pp.1315-1323.
  • Wan X., Xiao J. Exploiting neighborhood knowledge for single document summarization and keyphrase extraction // ACM Transactions on Information Systems, 2010, vol.28, №2, 8:1–8:34.
  • Tang J., Yao L., Chen D. Multi-topic based query-oriented summarization / Proceedings of the 9th SIAM International Conference on Data Mining, Nevada, USA, 2009, april 30 may 2, pp.1148–1159.
  • McDonald R. A study of global inference algorithms in multi-document summarization / Proceedings of the 29th European Conference on IR Research, Rome, Italy, Springer-Verlag, LNCS, 2007, April 2‒5, №25, pp. 557‒564.
  • Wang Y., Li B., Weise T. Estimation of distribution and differential evolution cooperation for large scale economic load dispatch optimization of power systems // Information Sciences, 2010, vol.180, №12, pp.2405–2420.
  • Chali Y., Hasan S.A., Joty S.R. Improving graph-based random walks for complex question answering using syntactic, shallow semantic and extended string subsequence kernels // Information Processing & Management, 2011, vol.47, №6, pp. 843-855.
  • Huang L., He Y., Wei F., Li W. Modeling document summarization as multi-objective optimization / Proceedings of the Third International Symposium on Intelligent Information Technology and Security Informatics, Jinggangshan, China, 2010, april 02–04, pp.382–386.
  • He R., Qin B., Liu T. A novel approach to update summarization using evolutionary manifold-ranking and spectral clustering // Expert Systems with Applications, 2012, vol.39, №3, pp.2375–2384.
  • Aliguliyev R.M. A new sentence similarity measure and sentence based extractivetechnique for automatic text summarization // Expert Systems with Applications, 2009, vol.36, №4, pp.7764‒7772.
  • Aliguliyev R.M. Performance evaluation of density-based clustering methods // Information Sciences, 2009, vol.179, №20, pp.3583–3602.
  • Islam A., Inkpen D. Semantic text similarity using corpus-based word similarity and string similarity // ACM Transactions on Knowledge Discovery from Data, 2008, vol.2, №2, pp.10:1-10:25.
  • Tsai F.S., Tang W., Chan K.L. Evaluation of novelty metrics for sentence-level novelty mining // Information Sciences, 2010, vol.180, №12, pp.2359–2374.
  • Wenyin L., Quan X., Feng M., Qiu B. A short text modeling method combining semantic and statistical information // Information Sciences, 2010, vol.180, no.20, pp.4031–4041.
  • Alguliev M., Aliguliyev R.M. Evolutionary algorithm for extractive text summarization //Intelligent Information Management, 2009, vol.1, №2, pp.128–138.
  • Radev D., Jing H., Stys M., Tam D. Centroid-based summarization of multiple documents // nformation Processing & Management, 2004, vol.40, №6, pp.919–938.
  • Rashedi E., Nezamabadi-pour H., Saryazdi S. GSA: a gravitational search algorithm, // Information Sciences, 2009, vol.179, №13, pp.2232–2248.
  • Zielinski K., Peters D., Laur R. Runtime analysis regarding stopping criteria for differential evolution and particle swarm optimization / Proceedings of the 1st International Conference on Experiments/Process/System Modelling/Simulation /Optimization, Athens, Greece, 2005, july 6–9.
  • Das S., Suganthan P.N. Differential evolution: a survey of the state-of-the-art, // IEEE Transactions on Evolutionary Computation, 2011, vol.15, №1, pp.4–31.
  • Das S., Sil S. Kernel-induced fuzzy clustering of image pixels with an improved differential evolution algorithm // Information Sciences, 2010, vol.180, №8, pp.1237–1256.
  • Lu Y., Zhou J., Qin H., Li Y., Zhang Y. An adaptive hybrid differential evolution algorithm for dynamic economic dispatch with valve-point effects // Expert Systems with Applications, 2010, vol.37, №7, pp.4842–4849.
  • Zhang M., Luo W., Wang X. Differential evolution with dynamic stochastic selection for constrained optimization // Information Sciences, 2008, vol.178, №15, pp.3043–3074.
  • Alguliev R.M., Aliguliyev R.M., Hajirahimova M.S., Mehdiyev C.A. MCMR: maximum coverage and minimum redundant text summarization model // Expert Systems with Applications, 2011, vol.38, №12, pp.14514–14522.
  • Aliguliyev R.M. Clustering techniques and discrete particle swarm optimization algorithm for multi-document summarization // Computational Intelligence, 2010, vol.26, №4, 420–448.