Bug Diagnosis By String Matching

Application to ILTS for Translation

Authors

  • Liang Chen University of Northern British Columbia
  • Naoyuki Tokuda Utsunomiya University

DOI:

https://doi.org/10.1558/cj.v20i2.227-244

Keywords:

Language Translation, tutoring system, Template, Heaviest Common Sequence

Abstract

We have developed an entirely new template-automaton-based knowledge database system for an interactive intelligent language tutoring system (ILTS) for Japanese-English translation whereby model translations as well as a taxonomy of bugs extracted from ill formed translations typical of nonnative learners are collected. Unlike conventional rule-based systems whose complicated solution search procedure and labor-intensive processing have led to so-called knowledge engineer bottlenecks of the expert systems, the new dynamic programming-based heaviest common sequence (HCS) matching algorithm is both efficient and robust in which error diagnosis is implemented by selecting, from among many candidates' paths in the system template, a path having an HCS of a highest similarity with a student's free-format translation input. This best matched path to the given ill formed sentence is used to provide contingent feedback messages. We have laid down a theoretical framework for the global HCS matching algorithm which is applied to the dual form of acyclic weighted digraphs by topologically sorting the template automaton structured according to augmented transition networks. An extensive evaluation test of the diagnostic engine has ensured the validity, efficiency, and robustness of the algorithm in providing error-contingent feedback to a wide spectrum of learners even with different educational backgrounds.

Author Biographies

  • Liang Chen, University of Northern British Columbia

    Liang Chen is currently an Associate Professor of Computer Science at the University of Northern British Columbia, Prince George, BC. He has published in the areas of CALL, fuzzy systems, image processing, theoretical computer science, Game, and discrete mathematics.

  • Naoyuki Tokuda, Utsunomiya University

    Naoyuki Tokuda, Emeritus Professor of Computer Science at Utsunomiya University, Japan, is Director of Research and Development of SunFlare Co., Tokyo, Japan. He has published extensively in the areas of intelligent tutoring systems, including ICALL CG, image and pattern recognition, and natural language processing.

References

Aho, A. V., & Ullman, J. D. (1992). Foundations of computer science. Rockville, MD: Computer Science Press.

Allen, J. (1995). Natural language understanding. Menlo Park, CA: The Benjamin/ Cummings Publishing Company Inc.

Apostolico, A., & Guerra, C. (1987). The longest common subsequence problem revised. Algorithmica, 2, 315-336.

Brown, P. F., Cocke, J., Della Pitra, S. A., Della Pietra, V. J., Jelinek, F., Mercer, R. L., & Rossin, P. S. (1990). A statistical approach to machine translation. Computational Linguistics, 16, 79-85.

Carl, M. (1999). Inducing translation templates for example-based machine translation. Proceedings of Machine Translation Summit VII (pp. 250-258).

Catt, M., & Hirst, G. (1990). An intelligent CALI system for grammatical error diagnosis. Computer Assisted Language Learning, 3, 3-27.

Chomsky, N. (1981). Lectures on government and binding. Dordrecht: Foris.

Chomsky, N. (1986). Barriers. Cambridge, MA: MIT Press.

Collins, B. (1999). Example-based machine translation: An adaptation-guided retrieval approach. Unpublished doctoral dissertation, Trinity College, Dublin.

Collins, B., & Cunningham, P. (1997, July). Adaptation-guided retrieval: Approaching EBMT with caution. In S. Nirenburg (Ed.), Proceedings of the 7th International Conference on Theoretical and Methodological Issues in Machine Translation (pp. 119-127). Santa Fe, NM.

Colmerauer, A. (1978). Metamorphosis grammars. In L. Bole (Ed.), Natural language communication with computers. New York: Springer Verlag.

Dagan, I., Itai, A., & Schwall, U. (1991, June). Two languages are more informative than one. In Proceedings of 29th Annual Meeting of the Association for Computational Linguistics (pp. 130-137). San Francisco, CA: Morgan Kaufmann Publishers.

Fries, C. C. (1945). Teaching and learning English as a foreign language. Ann Arbor, MI: University of Michigan Press.

Gu, Z., Tokuda, N., & Ye, Y. (1998). A corpus-based bootstrapping WSD algorithm using a downstairs-like threshold. IJSP Research Bulletin 97-NL-128, 73-78.

Hagen, L. K. (1994). Unification-based parsing applications for intelligent foreign language tutoring systems. CALICO Journal, 12 (2), 5-31.

Heift, T. (1998). Designed intelligence: A language teacher model, Unpublished doctoral dissertation, Simon Fraser University, British Columbia.

Hindle, D. (1990, June). Noun classification from predicate-argument structures. In Proceedings of 28th Annual Meeting of the Association for Computational Linguistics (pp. 268-275). San Francisco, CA: Morgan Kaufmann Publishers.

Hopcroft, J. E., & Ullman, J. D. (1979). Introduction to automata theory, language, and computation. New York: Addison-Wesley Publishing Co.

Huang, Z., & Tokuda, N. (1996). A syntactical approach to diagnosing multiple bugs in an intelligent tutoring system. IEEE Transactions on Systems, Man, and Cybernetics, 26 (2), 280-285.

Kay, M. (1997). The proper place of men and machines in language translation. Machine Translation, 12 (1/2), 3-23.

Kay, M. (1999). Chart translation. In M. Butt & T. Hollaway King (Eds.), Proceedings of machine translation summit VII (pp. 9-14). Singapore: The Asia-Pacific Association for Machine Translation (AAMT).

Kay, M., Gawron, J. M., & Norvig, P. (1995). Verbmobil: A translation system for face-toface dialogue, CLSI publications, Palo Alto, CA: Stanford University Press.

Nagao, M. (1984). A framework of mechanical translation between Japanese and English by analogy principle. In Elithorn & Banerji (Eds.), Artificial and human intelligence (pp. 173-180). North Holland: Elsevier Science Publishers.

Pereira, F. C. N., & Warren, D. H. D. (1980). Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks. Artificial Intelligence, 13, 231-278.

Shemtov, H. (1997). Ambiguity management in natural language generation, Unpublished doctoral dissertation, Stanford University, Palo Alto, CA.

Shieber, S. M. (1986). An introduction to unification-based approaches to grammar, vol. 4 of CSLI Lecture Notes, Palo Alto, CA: Stanford University Press.

Stetina, J., & Nagao, M. (1997, August). Corpus-based pp attachment ambiguity resolution with a semantic dictionary. In J. Shou & K. Church (Eds.), Proceedings of the fifth workshop on very large corpora (pp. 66-80).

Tokuda, N., & Chen, L. (2001, July-September). A template-based online intelligent tutoring system for language translation over the Internet. IEEE MULTIMEDIA [Special issue on intelligent multimedia and distance education], 8 (3), 46-55.

Wang, Y., & Garigliano, R. (1992). An intelligent language tutoring system for handling errors caused by transfer. In C. Frasson, G. Gauthier, & G. I. McCalla (Eds.), Intelligent tutoring systems, lecture notes in computer science (pp. 395-404). New York: Springer Verlag.

Wang, Y., & Garigliano, R. (1995). Empirical studies and intelligent language tutoring. Instructional Science, 23, 47-64.

Woods, W. (1970). Cascaded ATN grammars. American Journal of Computational Linguistics, 6 (1), 1-12.

Yarowsky, D. (1995, June). Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of 33rd Annual Meeting of the Association for Computational Linguistics (pp. 189-196). San Francisco, CA: Morgan Kauf-mann Publishers.

Downloads

Published

2013-01-14

Issue

Section

Articles

How to Cite

Chen, L., & Tokuda, N. (2013). Bug Diagnosis By String Matching: Application to ILTS for Translation. CALICO Journal, 20(2), 227-244. https://doi.org/10.1558/cj.v20i2.227-244