Proceedings

Massively Parallel Memory-Based Parsing

Download BibTeX Cite

Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Natural Language. Pages 918-923.

© 1991 International Joint Conferences on Artificial Intelligence

Abstract

This paper discusses a radically new scheme of natural language processing called massively parallel memorybased parsing. Most parsing schemes are rule-based or principle-based which involves extensive serial rule application. Thus, it is a time consuming task which requires a few seconds or even a few minutes to complete th e parsing of one sentence. Also, the degree of parallelism attained by mapping such a scheme on parallel computers is at most medium, so that the existing scheme can not take advantage of massively parallel computing. The massively parallel memory-basedparsing takes a radical departure from the traditional view. It views parsing as a memory-intensive process which can be sped up by massively parallel computing. Although we know of some studies in this direction, we have seen no report regarding implementation strategies on actual massively parallel machines, on performance, or on practicality accessment based on actual data. Thus, this paper focuses on discussion of the feasibility and problems of the approach based on actual massively parallel implementation using real data. The degree of parallelism attained in our model reaches a few thousands, and the performance of a few milliseconds per sentence has been accomplished. In addition, parsing time grows only linearly (or sublinearly) to th e length of the input sentences. The experimental results show the approach is promising for real-time parsing and bulk text processing.

  1. [Becker, 1975] Becker, J. D., The Phrasal Lexicon, BBN, Technical Report, 3081, 1975.
  2. [Gibson, 1990] Gibson, E., "Memory Capacity and Sentence Pro- cessing," Proceedings of ACL-90, 1990.
  3. [Higuchi et. al., 1991] Higuchi, T., K.itano, H., . Furuya, T., Kusumoto, H., Handa, K., and Kokubu, A., "IXM2: A Paral- lel Associate Processor for Knowledge Processing," Proceedings of the National Conference on Artificial Intelligence (AAAI-91), 1991.
  4. [Hillis, 1985] Hillis, D., TheConnectionMachine, TheM.I.T. Press, 1985.
  5. [Inmos, 1987] Inmos, IMS T800 Transputer, 1987.
  6. [K.itano, et. al., 1991] K.itano, H., Moldovan, D., Urn, I., Cha, S., "High Performance Natural Language Processing on Semantic Network Array Processor," Proceeding of the International Joint Conference on Artificial Intelligence (/JCAJ-91 ), 1991. IJCAI
  7. [K.itano and Higuchi, 1991] K.itano, H. and Higuchi, T., "High Per- formance Memory-Based Translation on IXM2 Massively Paral- lel Associative Memory Processor," Proceeding of the National Conference on Artificial Intelligence (AAA/-91 ), 1991.
  8. [K.itano, 1990] K.itano, H., "4>DMDIALOG: A Speech-to-Speech Di- alogue Translation System," Machine Translation, 5, 1990.
  9. [K.itano et. al., 1989] K.itano, H., Tomabechi, H., and Levin, L., "Ambiguity Resolution in DMTRANs PLus," Proceedings of the European Chapter of the ACL, 1989.
  10. [M9ldovan et. al., 1990] Moldovan, D., Lee, W., and Lin, C., SNAP: A Marker-Passing Architecture for Knowledge Process- ing, Technical Report PKPL 90-4, Department of Electrical En- gineering Systems, University of Southern California, 1990.
  11. [Nagao, 1989] Nagao, M., Machine Translation: How Far Can It Go?, Oxford, 1989.
  12. [Pollard and Sag, 1987] Pollard, C. and Sag, 1., Information-Based Syntax and Semantics, CSLI Lecture Notes, 13, 1987.
  13. [Riesbeck and Martin, 1986] Riesbeck, C. and Martin, C., "Direct Memory Access Parsing," Experience, Memory, and Reasoning, Lawrence Erlbaum Associates, 1986.
  14. [Stanfill and Waltz, 1988] Stanfill, C. and Waltz, D., ''The Memory- Based Reasoning Paradigm," Proceedings of the Case-Based Reasoning Workshop, DARPA, 1988.
  15. [Stanfill and Waltz, 1986] Stanfill, C. and Waltz, D., ''Toward Memory-Based Reasoning," Communications of the ACM, 1986.
  16. [Stanfill, 1988] Stanfill, C., "Memory-Based Reasoning Applied to English Pronunciation," Proceedings of the AAA/-88, 1988.
  17. [Sumita and Iida, 1991] Sumita, E., and Iida, H., "Experiments and Prospects of Example-Based Machine Translation," Proceedings ofACL-91,1991.
  18. [Tanaka and Numazaki, 1989] Tanaka, H. and Numazaki, H., "Par- allel GeneralizedLR Parsing based on Logic Programming," Pro- ceedings of the First International Workshop on Parsing Tech- nologies, Pittsburgh, 1989.
  19. [Tomabechi, 1987] Tomabechi, H., "Direct Memory Access Trans- lation," Proceedingof/JCA/-87, 1987. IJCAI
  20. [Tomita, 1986] Tomita, M., EfficientParsingforNaturalLanguage, Kluwer Academic Publishers,1986.
  21. [Waltz, 1990] Waltz, D., "Massively Parallel AI," Proceedings of AAA/-90, 1990.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards