Computer Science 4750, Fall '25
Course Diary

---

Copyright 2025 by H.T. Wareham
All rights reserved

---

Week 1, (Course Project Proposal and Report Notes), (end of diary)

Tuesday, September 9 (Lecture #1) (FS)
[Class Notes]

• Went over course outline.
• Introduction: What is Natural Language?
  • A natural language is any language (be it spoken, signed, or written) used by human beings to communicate with each other.
  • There are ~7000 natural languages, with ~20 these languages, e.g., Mandarin, Spanish, English, Hindi, and Arabic, being spoken by more than 1% of the world's population.
  • Example: The natural languages spoken by students in this course.
  • Human language allows a complexity of expression and meaning that has to date not been seen in linguistic behaviour in animals, e.g., bird calls,, primate vocalizations, bee dances, which are more akin to lists of codewords with specific meanings that are not combined, e.g., "danger", "(this way to) food".
    • Gorilla ASL experiments suggest that it is not just the lack of an appropriate vocal apparatus -- the ability to combine words to form arbitrarily complex expressions is simply not present in animals.
    • Talking animals are for now firmly in the domain of fiction (and comedy).
  • Example: Not the Nine O'Clock News (1980): Gerald the Gorilla (Link)
  • The ability to acquire and effectively communicate with a natural language is one of the major hallmarks of human intelligence and sentience; those individuals who have for whatever reasons fail to develop this ability are often considered subhuman, e.g., feral children (the Wild Boy of Aveyron), the deaf (Children of a Lesser God, Helen Keller).
  • Example: The Miracle Worker (1962) [excerpt]
  • The ability to acquire and effectively communicate with a natural language is thus one of the major hallmarks of true artificial intelligence.
• Introduction: What is Natural Language Processing (NLP)?
  • NLP is the subfield of Artificial Intelligence (AI) concerned with the computations underlying the processing (recognition, generation, and acquisition) of natural human language (be it spoken, signed, or written).
    • NLP is distinguished from (though closely related to) the processing of artificial languages, e.g., computer languages, formal languages (regular, context-free, context-sensitive, etc).
  • NLP emerged in the early 1950's with the first commercial computers; originally focused on machine translation, but subsequently broadened to include all natural-language related tasks (J&M, Section 1.6; Kay (2003); see also BKL, Section 1.5 and Afterword).
  • Two flavors of NLP: strong and weak
    • The focus of Strong NLP is on discovering and implementing human-level language abilities using approximately the same mechanisms as human beings when they communicate; as such, it is more closely allied with classical linguistics (and hence often goes by the name "computational linguistics").
    • The focus of Weak NLP is on giving computers human-level language abilities by whatever means possible; as such, it is more closely allied with AI (and is often referred to by either "NLP" or more specific terms like "speech processing").
    • Weak NLP is nonetheless influenced by Strong NLP, and vice versa (to the extent that the mechanisms proposed in Weak NLP to get systems up and running help to revise and make more plausible the theories underlying Strong NLP).
    • In this course, we will look at both types of NLP, and distinguish them as necessary.

Thursday, September 11

• Course Project Proposal and Report Notes
  Over the next 7 weeks, you should choose the topic of your course project (for inspiration, see the lists of presented student course projects in the last two weeks of the course diarys of previous offerings of CS 4750). This project can take the form of a literature survey on an NLP topic of interest to you or a software system implementing a particular NLP task. Each course project *** MUST *** be approved by the course instructor; please do this by chatting with your course instructor by October 30th. Course projects that are not approved prior to the submission of the associated project proposal (see below) will receive a mark of zero.

  Once a course project is approved, you must write and submit a printout of your project proposal to the course instructor by 9am on Thursday, October 31. This proposal is worth 5 course marks. It should be about a page long and consist of a 3-paragraph proposal text (3.5 marks total) (with the first paragraph motivating why your topic is of interest (1 mark), the second summarizing previous work on this topic (1.5 marks), and the third summarizing the focus of your survey or the approach you will use in constructing your software system (1 mark)) followed by at least five full-information literature references particular to the topic of your project which must each be cited at least once in your proposal text (1.5 marks total) (0.3 marks per reference up to 5 references).

  Once the project proposal is submitted, you have until noon on Friday, December 5, to do your project. In general, In general, this project will entail (as a minimum) a 15-20 page report (double-spaced) with 10-30 literature references (for a literature-survey project) or a 5-8 page report (double-spaced) with 5-15 references in addition to the software (for a software project). All included references MUST be cited in the body of the report. Though purely Web-based references (e.g., blogs, reference manuals) are acceptable, please try where at all possible to obtain literature-based references, e.g., books, book chapters, journal papers, conference papers; in those cases, You MUST give full references listing all reference information appropriate to the type of reference, author names, publication year, full paper title, book title with editors, journal name, journal volume and number, publisher, page numbers.

  The length and reference-number requirements above may vary depending on the nature of the chosen project and whether or not this project is being done by one or more people; this should be settled with the course instructor. Ideally, the submitted project should be on the same topic as that described in your project proposal. However, it being an imperfect world, if any difficulties do arise, chat with your course instructor as soon as possible so appropriate action, e.g., revision of stated goals and/or scope of project, can be taken.

  Each project will also have an associated short in-class presentation scheduled in the last two weeks of course lectures. Details of talk format and scheduling will be posted in early November after project proposals are submitted and marked.

  Here's to each of you choosing and carrying out a fun course project!

Thursday, September 11 (Lecture #2) (FS)
[Class Notes]

• The Characteristics of Natural Language: Why Bother?
  • Natural language is the area of study of linguistics. We focus here on descriptive linguistics (which studies the languages actually spoken by people) as opposed to prescriptive linguistics (which enforces particular standards of language).
  • Example: My Fair Lady (1964) [excerpt]
  • Looking at what linguists have to say about the characteristics of natural language is very valuable in an NLP course for two reasons:
    1. Linguists have studied many languages and hence have described and proposed mechanisms for handling phenomena that may lie outside those handled by existing NLP systems (many of which have been developed to only handle English).
    2. Linguists have studied the full range of natural processes, from sound perception to meaning, in some cases for centuries (~2500 and 1300 years, respectively, in the case of Sanskrit and Arabic linguists), and have had insights that may be invaluable in mitigating known problems with existing NLP systems, e.g., Marcus and Davis (2019, 2021).
• The Characteristics of Natural Language: Overview
  • General model of language processing (adapted from BKL, Figure 1.5):

    

    • "A LangAct" is an utterance in spoken or signed communication or a sentence in written communication.
    • The topmost left-to-right tier encodes language recognition and the right-to-left tier immediately below encodes language production.
    • The knowledge required to perform each step (all of which must be acquired by a human individual to use language) is the third tier, and the lowest is the area or areas of linguistics devoted to each type of knowledge.
    • Three language-related processes are thus encoded in this diagram: recognition and production (explicitly) and acquisition (implicitly).
  • Whether one is modeling actual human language or implementing language abilities in machines, the mechanisms underlying each of language recognition, production, and acquisition must be able to both (1) handle actual human language inputs and outputs and (2) operate in a computationally efficient manner.
    • As we will see over the duration of this course, the need to satisfy both of these criteria is one of major explanations for how research has proceeded (and diverged) in Strong and Weak NLP.
• The Characteristics of Natural Language: Phonetics (J&M, Section 7)
  • Phonetics is the study of the actual sounds produced in human languages (phones), both from the perspectives of how they are produced by the human vocal apparatus (articulatory phonetics) and how they are characterized as sound waves (acoustic phonetics).
    • Acoustic phonetics is particularly important in artificial speech analysis and synthesis.
  • In many languages, the way words are written does not correspond to the way sounds are pronounced in those words, e.g., the sound corresponding to the letter "t" is pronounced differently in each of the words "toucan", "starfish", "kitten", and "butter" (see below). Hence, another way has to be used to describe the sounds people actually produce in speech.
  • The most common way of representing phones is to use special sound-alphabets, e.g., International Phonetic Alphabet (IPA) [charts], ARPAbet [Wikipedia] (J&M, Table 7.1).
    • By convention, symbols denoting phones are written in square brackets, e.g., [b], [t].
    • Symbols in these alphabets may be modified by diacritics indicating more specific features of individual sounds, e.g., aspiration or palatalization, or the utterances in which these sounds occur, e.g., primary and secondary stress, utterance intonation.
  • Another way of representing phones uses phonetic features based on how sounds are articulated in the human vocal tract, e.g.,
    • consonants, e.g., [p], [d], [g]:
      • voicing (unvoiced / voiced), e.g., [p] / [b]
      • place of articulation, e.g., bi-labial ([p]) / labio-dental ([f]) / alveolar ([t]) / velar [k] / glottal ([?])
      • manner of articulation, e.g., plosive ([t]) / nasal ([m]) / fricative ([s]) / affricate (plosive + fricative) [ks]) / tap)
    • vowels, e.g., [a], [e], [i], [o], [u]:
      • height
      • "width" (front / back)
      • roundedness (rounded / unrounded)
  • Each language has its own characteristic repertoire of sounds, and no natural language (let alone English) uses the full range of possible sounds.
  • Example: Xhosa tongue twisters (clicks)
  • Even within a language, sounds can vary depending on their context, due to constraints on the way articulators can move in the vocal tract when progressing between adjacent sounds (both within and between words) in an utterance.
    • Variation in pronouncing [t] (J&M, Table 7.9):
      • aspirated (in initial position), e.g., "toucan"
      • unaspirated (after [s]), e.g., "starfish"
      • glottal stop (after vowel and before [n], e.g., "kitten"
      • tap (between vowels), e.g., "butter"
    • word-final [t]/[d] palatalization (J&M, Table 7.10), e.g., "set your", "not yet", "did you"
    • Word-final [t]/[d] deletion (J&M, Table 7.10) e.g., "find him", "and we", "draft the"
  • Variation in sounds can also depend on a variety of other factors, e.g., rate of speech, word frequency, speaker's state of mind / gender / class / geographical location (J&M, Section 7.3.3).
  • As if all this wasn't bad enough, it is often very difficult to isolate individual sounds and words from acoustic speech signals

References

• Abney, S.P. (1996) "Partial parsing via finite-state cascades." Natural Language Engineering, 2(4), 337-344.
• BBC News (2014) "Translation tech helps firms talk business round the world." (URL: Retrieved November 14, 2014)
• Baker, J.M., Deng, L., Glass, J., Khuanpur, S., Lee, C.-H., Morgan, N., and O'Shaughnessy, D. (2009a) "Research Developments and Directions in Speech Recognition and Understanding, Part 1." IEEE Signal Processing Magazine, 26(3), 75-80.
• Baker, J.M., Deng, L., Khuanpur, S., Lee, C.-H., Glass, J., Morgan, N., and O'Shaughnessy, D. (2009b) "Research Developments and Directions in Speech Recognition and Understanding, Part 2." IEEE Signal Processing Magazine, 26(6), 78-85.
• Barton, G.E., Berwick, R.C., and Ristad, E.S. (1987) Computational Complexity and Natural Language. MIT Press.
• Beesley, K.R. and and Karttunen, L. (2000) "Finite-state Non-concatenative Morphotactics." In SIGPHON 2000. 1-12. [PDF]
• Beesley, K.R. and and Karttunen, L. (2003) Finite-State Morphology. CSLI Publications.
• Bird, S. (2003) "Phonology." In R. Mitkov (ed.) (2003), pp. 3-24.
• Bird, S., Klein, E., and Loper, E. (2009) Natural Language Processing with Python. O'Reilly Media. [Abbreviated above as BKL]
• Carpenter, B. (2003) "Complexity." In R. Mitkov (ed.) (2003), pp. 178-200.
• Carroll, J. (2003) "Parsing." In R. Mitkov (ed.) (2003), pp. 233-248.
• Clark, A. and Lappin, S. (2011) Linguistic Nativism and the Poverty of the Stimulus. Blackwell.
• Colby, K.M. (1981) "Modeling a paranoid mind." Behavioral and Brain Sciences, 4(4), 515-534.
• Daciuk, J. (2002) "Comparison of Construction Algorithms for Minimal Acyclic, Deterministic, Finite-State Automata from Sets of Strings." In CIAA 2002. Lecture Notes in Computer Science no. 2608. Springer-Verlag; Berlin. 255-261. [PDF]
• Daciuk, J., Mihov, S., Watson, B.W., and Watson, R.E. (2000) "Incremental Construction of Acyclic Finite-State Automata." Computational Linguistics, 26(1), 3-16.
• Damerau, F.J. (1964) "A Technique for Computer Detection and Correction of Spelling Errors." Communications of the ACM, 7(3), 171-176.
• Demers, R.A. and Farmer, A.K. (1991) A Linguistic Workbook (2nd Edition). The MIT Press.
• Denning, P.J. (2023) "The Smallness of Large Language Models." Communications of the ACM, 66(9), 24-27. [Text]
• Du, M.W. and Chang, S.C. (1992) "A model and a fast algorithm for multiple errors spelling correction." Acta Informatica, 29, 281-302.
• Duffy, C. and Uzquiano, K. (2023) "Bot or not? How to tell when you're reading something written by AI." CNN. [Link]
• Dupont, P., Denis, F., and Esposito, Y. (2005) "Links between probabilistic automata and hidden Markov models: probability distributions, learning models, and induction algorithms." Pattern Recognition, 38, 1349-1371.
• Dutoit, T. and Stylianou, Y. (2003) "Text-to-Speech Synthesis." In R. Mitkov (ed.) (2003), pp. 323-338.
• Edwards, C. (2021) "The best of NLP." Communications of the ACM, 64(4), 9-11. [Text]
• Epstein, R. (2007) From Russia With Love: How I got fooled (and somewhat humiliated) by a computer." Scientific American Mind, October, 6-17.
• Eisenstein, J. (2019) Introduction to Natural Language Processing. The MIT Press.
• Gazdar, G. and Pullum, G.K. (1985) "Computationally Relevant Properties of Natural Languages and Their Grammars." Next Generation Computing, 3, 273-306. [PDF]
• Grana, J., Barcala, M., and Alonso, M.A. (2001) "Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries." In CIAA 2001. Lecture Notes in Computer Science no. 2494. Springer-Verlag; Berlin. 135-148. [PDF]
• Greengard, S. (2023) "Computational Linguistics Finds Its Voice." Communications of the ACM, 66(2), 18-20. [Text]
• Greengard, S. (2023) "Distilling What We Know." Communications of the ACM, 66(9), 15-17. [Text]
• Grishman, R. (2003) "Information Extraction." In R. Mitkov (ed.) (2003), pp. 545-559
• Harabagiou, S. and Moldovan, D. (2003) "Question Answering." In R. Mitkov (ed.) (2003), pp. 560-582
• Hopcroft, J.E., Motwani, R., and Ullman, J.D. (2001) Introduction to Automata Theory, Languages, and Computation (Second Edition). Addison-Wesley. [Abbreviated above as HMU01]
• Hopcroft, J.E. and Ullman, J.D. (1979) Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. [Abbreviated above as HU79]
• Hutchins, J. (2003) "Machine Translation: General Overview." In R. Mitkov (ed.) (2003), pp. 501-511.
• Indurkhya, N. and Damerau, F.J. (eds.) (2010) Handbook of Natural Language Processing (2nd Edition). Chapman and Hall / CRC.
• Jurafsky, D. and Martin, J.H. (2008) Speech and Natural Language Processing (2nd Edition). Prentice-Hall. [Abbreviated above as J&M]
• Jurafsky, D. and Martin, J.H. (2023) Speech and Natural Language Processing (3rd Edition). (Book Website) [Abbreviated above as J&M2]
• Kaplan, R. (2003) "Syntax." In R. Mitkov (ed.) (2003), pp. 70-90.
• Kaplan, R and Kay, M. (1994) "Regular Models of Phonological Rule Systems." Computational Linguistics, 20(3), 331-378. [PDF]
• Kaplan, R. and Kay, M. (1996) "Finite-state Methods in Natural Language Processing: Algorithms." Lecture notes. [PDF]
• Kari, L., Konstantinidis, S., Perron, S., Wozniak, G., and Xu, J. (2003) "Finite-state error edit-systems and difference measures for languages and words." Technical report 2003-01, Department of Mathematics and Computing Science, Saint Mary's University, Canada.
• Kay, M. (2003) "Introduction." In R. Mitkov (ed.) (2003), pp. xvii-xx.
• Kedia, A, and Rasu, M. (2020) Hands-On Python Natural Language Processing. Packt Publishing; Birmingham, UK.
• Kenstowicz, M.J. (1994) Phonology in Generative Grammar. Basil Blackwell.
• Kiraz, G.A. (2000) "Multi-tiered nonlinear morphology using multitape finite automata: A case study on Syriac and Arabic." Computational Linguistics, 26(1), 77-105. [PDF]
• Kruskal, J.B. (1984) "An Overview of Sequence Comparison." In D. Sankoff and J.B. Kruskal (eds.) Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley; Reading, MA. 1-44.
• Lamel, L. and Gauvin, J.-L. R. (2003) "Speech Recognition." In R. Mitkov (ed.) (2003), pp. 305-322.
• Lappin, S. (2003) "Semantics." In R. Mitkov (ed.) (2003), pp. 91-111.
• Leech, G. and Weisser, M. (2003) "Pragmatics and Dialogue." In R. Mitkov (ed.) (2003), pp. 136-156.
• Li, H. (2022) "Language models: past, present, and future." Communications of the ACM, 65(7), 56-63. (HTML)
• Lovins, J.B. (1973) Loanwords and the Phonological Structure of Japanese. PhD thesis, University of Chicago.
• Lucchesi, C.L. and Kowaltowski, T. (1993) "Applications of finite automata representing large vocabularies." Software - Practice and Experience, 23(1), 15-20. [PDF]
• Manning, C. and Schutze, H. (1999) Foundations of Statistical Natural Language Processing. The MIT Press. [Abbreviated above as M&S]
• Marcus, G. and Davis, E. (2019) Rebooting AI: Building Artificial Intelligence We Can Trust. Pantheon Books; New York.
• Marcus, G. and Davis, E. (2021) "Insights for AI from the Human Mind", Communications of the ACM, 64(1), 38-41. [Text]
• Martin-Vide, C. (2003) "Formal Grammars and Languages." In R. Mitkov (ed.) (2003), pp. 157-177.
• Mihov, S. and Maurel, D. (2000) "Direct Construction of Minimal Acyclic Subsequential Transducers." In CIAA 2000. Lecture Notes in Computer Science no. 2088. Springer-Verlag; Berlin. 217-229.
• Mihov, S. and Schulz, K.U.. (2004) "Fast Approximate Search in Large Dictionaries." Computational Linguistics, 30(4), 451-477.
• Mitkov, R. (ed.) (2003) The Oxford Handbook of Computational Linguistics. Oxford University Press.
• Mitkov, R. (2003a) "Anaphora Resolution." In R. Mitkov (ed.) (2003), pp. 266-283.
• Mohri, M. (1996) "On some applications of finite-state automata theory to natural language processing." Natural Language Engineering, 2(1), 61-80.
• Mohri, M. (1997) "Finite-state transducers in language and speech processing." Computational Linguistics, 23(2), 269-311. [PDF]
• Mohri, M. (2004) "Weighted Finite-State Transducer Algorithms: An Overview." In Formal Languages and Applications. Studies in Fuzziness and Soft Computing no. 148. Physica-Verlag; Berlin. 551-564. [PDF]
• Mohri, M., Pereira, F., and Riley, M. (2000) "The Design Principles of a Weighted Finite-State Transducer Library." Theoretical Computer Science, 231, 17-32. [PDF]
• Mohri, M., Pereira, F., and Riley, M. (2002) "Weighted Finite-State Transducers in Speech Recognition." Computer Speech & Language, 16(1), 69-88. [PDF]
• Myers, E.W. and Miller, W. (1989) "Approximate Matching of Regular Expressions." Bulletin of Mathematical Biology, 51, 5-37.
• Nederhof, M.-J. (1996) "Introduction to Finite-State Techniques." Lecture notes. [PDF]
• Nederhof, M.-J. (2000) "Practical Experiments with Regular Approximation of Context-Free Languages." Computational Linguistics, 26(1), 17-44. [PDF]
• Oflazer, K. (1996) "Error-Tolerant Finite-State Recognition with Applications to Morphological Analysis and Spelling Correction." Computational Linguistics, 22(1), 73-89.
• Pereira, F. and Riley, M. (1997) "Speech Recognition by Composition of Weighted Finite-State Automata." In E. Roche and Y. Schabes (eds.) (1997), pp. 431-454.
• Ramsay, A. (2003) "Discourse." In R. Mitkov (ed.) (2003), pp. 112-135.
• Rao, D. and McMahan, B. (2019) Natural Language Processing with PyTorch: Build Intelligent Language Applications Using Deep Learning. O'Reilly; Boston, MA.
• Reis, E. S. D., Costa, C. A. D., Silveira, D. E. D., Bavaresco, R. S., Righi, R. D. R., Barbosa, J. L. V., and Federizzi, G. (2021) "Transformers aftermath: current research and rising trends." Communications of the ACM, 64(4), 154-163. [Text]
• Robson, D. (2023) ``Why we personify threatening events.'' BBC Future [Link]
• Roche, E. and Schabes, Y. (eds.) (1997) Finite-state Natural Language Processing. The MIT Press.
• Roche, E. and Schabes, Y. (1997a) "Introduction." In E. Roche and Y. Schabes (Eds.) (1997), pp. 1-66.
• Savary, A. (2002) "Typographical Nearest-Neighbor Search in a Finite-State Lexicon and Its Application to Spelling Correction." In CIAA 2002. Lecture Notes in Computer Science no. 2494. Springer-Verlag; Berlin. 251-260.
• Schmidhuber, J. (2015) "Deep learning in neural networks: An overview." Neural Networks, 61, 85-117.
• Somers, H. (2003) "Machine Translation: Latest Developments." In R. Mitkov (ed.) (2003), pp. 512-528.
• Sproat, R. (1992) Morphology and Computation. The MIT Press.
• Tellman, Z. (2023) "Designing a Framework for Conversational Interfaces." Communications of the ACM, 66(10), 44-7. [Text]
• Tomlin, R. (1986) Basic Word Order: Functional Principles. Croom Helm.
• Trost, H. (2003) "Morphology." In R. Mitkov (ed.) (2003), pp. 25-47.
• Tzoukermann, E., Klavans, J.L., and Strazalkowski, T. (2003) "Information Retrieval." In R. Mitkov (ed.) (2003), pp. 529-544.
• Vajjala, S., Majumder, B., Gupta, A., and Surana, H. (2019) Practical Natural Language Processing: A Comprehensive Guide to Building Real-world NLP Systems. O'Reilly; Boston, MA.
• Vidal, E., Thollard, F., Higuera, C., Casacuberta, F., and Carrasco, R.C. (2005a) "Probabilistic Finite-State Machines -- Part I." IEEE Transactions on Pattern Analysis and Machine Intelligence, 237(7), 1013-1025.
• Vidal, E., Thollard, F., Higuera, C., Casacuberta, F., and Carrasco, R.C. (2005b) "Probabilistic Finite-State Machines -- Part II." IEEE Transactions on Pattern Analysis and Machine Intelligence, 237(7), 1026-1039.
• Wareham, T. (1999) Systematic Parameterized Complexity Analysis in Computational Phonology. PhD thesis, Department of Computer Science, University of Victoria.
• Wareham, T. (2001) "The Parameterized Complexity of Intersection and Composition Operations on Sets of Finite-State Automata." In CIAA 2000. Lecture Notes in Computer Science no. 2088. Springer-Verlag; Berlin. 302-310. [PDF]
• Weizenbaum, J. (1966) "ELIZA - A computer program for the study of natural language communication between man and machine." Communications of the ACM, 9(1), 36-45.
• Weizenbaum, J. (1967) "Contextual understanding by computers." Communications of the ACM, 10(8), 474-480.
• Weizenbaum, J. (1979) Computer Power and Human Reason. W.H. Freeman.
• Yang, Y. and Piantadosi, S.T. (2022) "One model for the learning of language." Proceedings of the National Academy of Sciences 119(5), e2021865119 (12 pages).

Created: July 11, 2025
Last Modified: July 24, 2025