Adaptación, comparación y mejora de algoritmos metaheurísticos al problema de etiquetado de partes del discurso

Resumen

La identificación de partes del discurso (Part-of-Speech Tagging, POST) es una tarea compleja en las aplicaciones de procesamiento de lenguaje natural. Ha sido abordada desde enfoques basados en información estadística y reglas, haciendo uso de distintos métodos y, últimamente, se destacan los algoritmos metaheurísticos obteniendo buenos resultados. Por ello, se involucran en esta investigación para asignar la mejor secuencia de etiquetas (roles) para las palabras de una oración, basándose en información estadística. Este proceso se desarrolló en 2 ciclos, donde cada ciclo tuvo 4 fases para la adaptación al problema de etiquetado en los algoritmos metaheurísticos Particle Swarm Optimization, Jaya, Random-Restart Hill Climbing, y un algoritmo memético basado en Global-Best Harmony Search como optimizador global, y en Hill Climbing como optimizador local. Se realizaron experimentos preliminares (utilizando validación cruzada), para ajustar los parámetros de cada algoritmo y luego ejecutarlos sobre los datasets completos de los corpus etiquetados IULA (castellano), Brown (inglés) y Nasa Yuwe (Nasa). Los resultados obtenidos por los etiquetadores propuestos se compararon mediante las pruebas estadísticas no paramétricas de Friedman y Wilcoxon, ratificando que el memético propuesto, GBHS Tagger, obtiene mejores resultados de precisión. Los etiquetadores propuestos se convierten en un aporte muy importante para el POST, tanto para lenguas tradicionales (Inglés y Castellano), no tradicionales (Nasa Yuwe), y sus áreas de aplicación.

Palabras clave

algoritmos heurísticos, computación evolutiva, etiquetado de partes del discurso, inteligencia computacional, lingüística computacional, métodos de búsqueda, procesamiento de lenguaje natural

Biografía del autor/a

Miguel Alexis Solano-Jiménez

Roles: Análisis Formal, Curación de datos, Investigación, Metodología, Software, Validación, Visualización, Escritura – borrador original, Escritura – revisión y edición.

Jose Julio Tobar-Cifuentes

Roles: Análisis Formal, Curación de datos, Investigación, Metodología, Software, Validación, Visualización, Escritura – borrador original, Escritura – revisión y edición.

Luz Marina Sierra-Martínez, Ph. D.

Roles: Conceptualización, Metodología, Supervisión, Administración del proyecto, Escritura – borrador original, Escritura – revisión y edición.

Carlos Alberto Cobos-Lozada, Ph. D.

Roles: Conceptualización, Metodología, Supervisión, Administración del proyecto, Escritura – borrador original, Escritura – revisión y edición.

Citas

[1] T. Güngör, Handbook of Natural Language Processing (2 Edition ), 2011.

[2] D. Jurafsky, and J. H. Martin, “Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition,” Computational Linguistics, vol. 26(4), pp. 638-641, 2009. https://doi.org/10.1162/089120100750105975

[3] A. Alhasan, and A. T. Al-taani, “POS Tagging for Arabic Text Using Bee Colony Algorithm,” Procedia Computer Science, pp. 158-165, 2018. https://doi.org/10.1016/j.procs.2018.10.471

[4] L. M. Sierra Martínez, C. A. Cobos, and J. C. Corrales, “Memetic algorithm based on global-best harmony search and hill climbing for part of speech tagging,” in International Conference on Mining Intelligence and Knowledge Exploration, 2017, pp. 198-211. https://doi.org/10.1007/978-3-319-71928-3_20

[5] R. Forsati, and M. Shamsfard, “Novel harmony search-based algorithms for part-of-speech tagging,” Knowledge and Information Systems, vol. 42, pp. 709-736, 2014. https://doi.org/10.1007/s10115-013-0719-6

[6] A. Ekbal, and S. Saha, “Simulated annealing based classifier ensemble techniques: Application to part of speech tagging,” Information Fusion, vol. 14 (3), pp. 288-300, 2013. https://doi.org/10.1016/j.inffus.2012.06.002

[7] S. Bandyopadhyay, S. Saha, U. Maulik, and K. Deb, “A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA,” IEEE Transactions on Evolutionary Computation, vol. 12 (3), pp. 269-283, Jun. 2008. https://doi.org/10.1109/TEVC.2007.900837

[8] W. N. Francis, and H. Kucera, Brown Corpus Manual, 1979. http://clu.uni.no/icame/manuals/BROWN/INDEX.HTM#bc8

[9] M. P. Marcus, M. A. Marcinkiewicz, and B. Santorini, “Building a large annotated corpus of English: the penn treebank,” Computational Linguistics, vol. 19 (2), pp. 313-330, 1993. https://doi.org/10.1162/coli.2010.36.1.36100

[10] M. El-Haj, and R. Koulali, “KALIMAT a multipurpose Arabic Corpus,” in Second Workshop on Arabic Corpus Linguistics, 2013.

[11] T. Chakraborty, “Identification of Reduplication in Bengali Corpus and their Semantic Analysis : A Rule-Based Approach,” in Proceedings of the Workshop on Multiword Expressions: from Theory to Applications, 2010, pp. 73-76.

[12] O. Bojar, V. Diatka, P. Rychly, P. Strañak, V. Suchomel, Al. Tamchyna, and D. Zeman, “HindEnCorp - Hindi-English and Hindi-only corpus for machine translation,” in Proceedings of the Ninth International Conference on Language Resources and Evaluation, 2014, pp. 3550-3555.

[13] S. S. Mukku, and R. Mamidi, “ACTSA: Annotated Corpus for Telugu Sentiment Analysis,” in Proceedings of the First Workshop on Building Linguistically Generalizable NLP Systems, 2018, pp. 54-58. https://doi.org/10.18653/v1/w17-5408

[14] L. M. Sierra Martínez, C. A. Cobos, C. J. Muñoz Corrales, T. Curieux Rojas, E. Herrera-viedma, and D. H. Peluffo-ordóñez, “Building a Nasa Yuwe Language Corpus and Tagging with a Metaheuristic Approach,” Computación y Sistemas, vol. 22 (3), pp. 881-894, 2018. https://doi.org/10.13053/CyS-22-3-3018

[15] S. Petrov, D. Das, and R. McDonald, “A Universal Part-of-Speech Tagset,” in Proceedings of the Eighth International Conference on Language Resources and Evaluation, 2012, pp. 2089-2096.

[16] X. S. Yang, and S. Deb, “Cuckoo search: Recent advances and applications,” Neural Computing and Applications, vol. 24 (1), pp. 169-174, 2014. https://doi.org/10.1007/s00521-013-1367-1

[17] J. Brownlee, Clever Algorithms, 2011.

[18] F. Neri, and C. Cotta, “A Primer on Memetic Algorithms,” in Handbook of Memetic Algorithm, pp. 43-52, 2012.

[19] C. Cotta, Una Visión General de los Algoritmos Meméticos. http://www.lcc.uma.es/~ccottap/papers/memeticos.pdf

[20] E. R. R. Kato, G. D. de A. Aranha, and R. H. Tsunaki, “A new approach to solve the flexible job shop problem based on a hybrid particle swarm optimization and Random-Restart Hill Climbing,” Computers & Industrial Engineering, vol. 125, pp. 178-189, Nov. 2018. https://doi.org/10.1016/j.cie.2018.08.022

[21] J. Kennedy, and R. Eberhart, “Particle Swarm Optimization,” in Proceedings of ICNN'95 - International Conference on Neural Networks, 1995, pp. 1942-1948. https://doi.org/10.1109/ICNN.1995.488968

[22] A. Nickabadi, M. M. Ebadzadeh, and R. Safabakhsh, “A novel particle swarm optimization algorithm with adaptive inertia weight,” Applied Soft Computing, vol. 11 (4), pp. 3658-3670, 2011. https://doi.org/10.1016/j.asoc.2011.01.037

[23] R. Venkata Rao, “Jaya: A simple and new optimization algorithm for solving constrained and unconstrained optimization problems,” International Journal of Industrial Engineering Computations, vol. 7 (1), pp. 19-34, Dec. 2016. https://doi.org/10.5267/j.ijiec.2015.8.004

[24] Institut Universitari de Lingüística Aplicada, IULA Spanish LSP Treebank, 2012.

[25] K. S. Pratt, “Design Patterns for Research Methods: Iterative Field Research,” in AAAI Spring Symposium: Experimental Design for Real, 2009, pp. 1-7.

[26] Q. Pan, M. F. Tasgetiren, and Y. Liang, “A discrete particle swarm optimization algorithm for the no-wait flowshop scheduling problem,” Computers & Operations Research, vol. 35, pp. 2807-2839, 2008. https://doi.org/10.1016/j.cor.2006.12.030

[27] K. Gao, F. Yang, M. Zhou, Q. Pan, and P. N. Suganthan, “Flexible job-shop rescheduling for new job insertion by using discrete Jaya algorithm,” IEEE Transactions on Cybernetics, vol. 49 (5), pp. 1944-1955, 2019. https://doi.org/10.1109/TCYB.2018.2817240

[28] D. H. Wolpert, and W. G. Macready, “No free lunch theorems for optimization,” IEEE Transactions on Evolutionary Computation, vol. 1 (1), pp. 67-82, Apr. 1997. https://doi.org/10.1109/4235.585893

[29] J. Alcalá-Fdez, L. Sánchez, S. García, M. J. del Jesus, S. Ventura, J. M. Garrell, J. Otero, C. Romero, J. Bacardit, V. M. Rivas, J. C. Fernández, and F. Herrera, “KEEL: A software tool to assess evolutionary algorithms for data mining problems,” Soft Computing, vol. 13, pp. 307-318, 2009. https://doi.org/10.1007/s00500-008-0323-y