CS60075�Natural Language Processing

Somak Aditya,

Assistant Professor, Department of CSE

NLP– In Short

NLP: A branch of Artificial Intelligence (AI) that teaches computers to understand, interpret, and generate human language.

- Stanford HAI

​

​

2

Delusion of “Pure NLP”

• Philosophy and Logic
• Linguistics
• Computational Linguistics
• Neuroscience
• Cognitive Science
• Statistics
• Machine Learning, Deep Learning
• Bayesian, Graphical Models
• Causality
• …

​

​

3

Course and motivations

• Lectures: WED 10-11, THU 9-10, FRI 11-12
• Venue: NR411

​

• Prerequisite: Machine Learning (or equivalent)
• https://cs60075-a2026-nlp-course-page.netlify.app/
• Teaching Assistants
• Aritra Dutta: aritradutta18@gmail.com
• Sachin Vasistha: sachinvashistha6916@gmail.com 
• Arghyadeep Ghosh: ghosh.arghyadeep7@gmail.com
• (Substitute/Project TA) Preeta Das: preetadas21@gmail.com

​

4

​

​

​

​

Tentative Weightage

• Midsem: 30%
• Final Sem: 30%
• Assignment 1: 10%
• Assignment 2: 15%
• Quizzes + Attendances: 15%

5

Human Language Understanding & Reasoning

6

Four eras of NLP

• 1940–1969: Early Explorations
• 1970–1992: Hand-built symbolic NLP

systems, of increasing formalization

• 1993–2012: Statistical or Probabilistic NLP and then more general Supervised ML for NLP
• 2013–now: Deep Learning or Artificial Neural Networks; Unsupervised or Self-Supervised NLP; Reinforcement Learning

Only somewhat entwined fields

• NLP / Computational Linguistics
• AI / Neural Networks

Dædalus 151(2): 127–138 ( Spring 2022) https://www.amacad.org/publication/human

-language-understanding-reasoning

1. Early Explorations

1940-1969

7

NLP – Symbolic, Statistical to early ML

8

Machine Translation: The origin of NLP/Computational Linguistics

“Also knowing nothing official about, but having guessed and inferred considerable about, the powerful new mechanized methods in cryptography—methods which I believe succeed even when one does not know what language has been coded—one naturally wonders if the problem of translation could conceivably be treated as a problem in cryptography. When I look at an article in Russian, I say: ‘This is really written in English, but it has been coded in some strange symbols. I will now proceed to decode.’ ”

– Warren Weaver (1955:18, quoting a letter he wrote in 1947)

“When I look at an article in Russian, I say: ‘This is really written in English, but it has been coded in some strange symbols. I will now proceed to decode.’” – Warren Weaver, March 1947

“… as to the problem of mechanical translation, I frankly am afraid that the [semantic] boundaries of words in different languages are too vague … to make any quasi-mechanical translation scheme very hopeful.”

– Norbert Wiener, April 1947

Wiener: MIT originator of cybernetics, which sought to tie together communication, control, and feedback in living things and computers.

Weaver was a mathematician & engineer known for his work as a science funder at the Rockefeller Foundation and OSR&D (US Govt WWII science funder) and for coauthoring an approachable Info Theory intro with Shannon

The early history of NLP: MT in the 1950s

AI Begins: The Dartmouth Summer Research Project 1956

John McCarthy

- Invented LISP (programming language)

- Coined the term AI

​

Deemed as “Father of AI”

Neural Networks: The inspiration from knowledge of neurons

11

Structural Inspiration only!

McCulloch-Pitts Neuron

15

Original McCulloch & Pitts 1943 threshold unit:

𝟏(𝑊𝑥 > 𝜃)

= 𝟏(𝑊𝑥 − 𝜃 > 0)

This function has no slope,

so, no gradient-based learning

“A Logical Calculus of Ideas Immanent in Nervous Activity”,

Frank Rosenblatt: The (Mark I) Perceptron

16

https://news.cornell.edu/stories/2019/09/professors-perceptron-paved-way-ai-60-years-too-soon

Early AI Hype! New York Times July 8, 1958

17

NEW NAVY DEVICE LEARNS BY DOING

Psychologist Shows Embryo of Computer Designed to Read and Grow Wiser

The Navy revealed the embryo of an electronic computer today that it expects will be able to walk, talk, see, write, reproduce itself and be conscious of its existence.

The embryo—the Weather Bureau’s

$2,000,000 “704” computer—learned to differentiate

between right and left after fifty attempts in the Navy’s demonstration for newsmen.

Two visions of artificial intelligence in the 1950s

18

Cybernetics

Wiener, Rosenblatt

(Symbolic) Artificial Intelligence

Minsky, McCarthy, Simon, Newell

Information Retrieval: Vannevar Bush

19

Bush (1945): As We May Think

“Consider a future device for individual use, which is a sort of mechanized private file and library. It needs a name, and, to coin one at random, “memex” will do. A memex is a device in which an individual stores all his books, records, and communications, and which is mechanized so that it may be consulted with exceeding speed and flexibility. It is an enlarged intimate supplement to his memory.

​

https://www.theatlantic.com/magazine/ar

chive/1945/07/as-we-may-think/303881/

Bush went from being Dean of Engineering at MIT and president of the Carnegie Institution of Washington to chairman of the National Defense Research Committee in WWII (which had huge funding, directing all wartime science, including the Manhattan Project)

Cyril Cleverdon introduces benchmarking

20

• Cranfield tests (1957–1967)

​

• Defined the idea of benchmark tests for language, with a document collection, queries, and correct answers.

​

• He had exhaustive answers on document relevance over a small corpus!

The 1950s origins of NLP/Computational Linguistics

21

I grabbed these timelines from Ruth Camburn’s “A Short History of Computational Linguistics”. She was a CSU Fresno Linguistics grad student around 2013.

• Foundational work on automata, formal languages, probabilistic modeling, and information theory
• First speech systems (Davis et al.)
• MT heavily funded by military — huge overconfidence
• But using machines dumber than a pocket calculator
• Little understanding of syntax, semantics, pragmatics

NLP in the 1960s

22

ALPAC report (1966): crap, this is really hard!

2. Hand-built demonstration NLP�systems, of increasing formalization

Knowledge Representation

Knowledge Graphs and Knowledge Bases

1970–1992

​

23

Terry Winograd

(1946–, Stanford faculty 1973–2014; AI/NLP 1973–1984)

24

Seymour Papert

​

​

Terry Winograd

​

​

Stuart Shieber

SHRDLU – First NLU System on blocks world

Constructing the meaning of human language: 1967–2017

𝜆𝑥(apple(𝑥) ∧ red(𝑥))

red apple

𝜆𝑃. 𝜆𝑥(𝑃(𝑥) ∧ red(𝑥)) 𝜆𝑥. apple(𝑥)

𝜄(𝜆𝑦. table(𝑦))

table

𝜆𝑦. table(𝑦)

𝜆𝑥. on(𝑥, 𝜄(𝜆𝑦. table(𝑦)))

• Tokenize a sentence into words: The red apple is on the table
• Parse it into a tree or graph data structure (using CFG and beyond)
• Construct its meaning by: (i) lexical lookup, then (ii) semantic composition, using a “rule-to-rule” approach working up the tree (e.g., PP: 𝛼(𝛽) → P: 𝛼NP: 𝛽 )

on(𝜄(𝜆𝑥(apple(𝑥) ∧ red(𝑥))), 𝜄(𝜆𝑦. table(𝑦)))

on(𝜄(𝜆𝑥(apple(𝑥) ∧ red(𝑥))), 𝜄(𝜆𝑦. table(𝑦)))

𝜆𝑥. on(𝑥, 𝜄(𝜆𝑦. table(𝑦)))

The

𝜆𝑃. 𝜄(𝑃)

the

𝜆𝑃. 𝜄(𝑃)

𝜄(𝜆𝑥(apple(𝑥) ∧ red(𝑥)))

on

𝜆𝑦. 𝜆𝑥(on(𝑥, 𝑦))

is

𝜆𝑃. 𝑃

(Compositional) Constructing the meaning of human language: 1967–2017

From a sentence to a logical form: tokenizing, parsing, and composing meaning rule-to-rule

1

Tokenize

Split a sentence into discrete word tokens.

The

red

apple

is

on

the

table

2

Parse

Arrange the tokens into a tree or graph structure, using a context-free grammar (CFG) and beyond.

3

Construct Meaning

(i) lexical lookup → build each word's meaning, then (ii) semantic composition — combine meanings rule-to-rule, working up the tree.

rule: PP: α(β) → P: α NP: β

Syntax + Semantics for “The red apple is on the table”

S — The red apple is on the table

on(ι(λx. apple(x) ∧ red(x)), ι(λy. table(y)))

NP — the red apple

ι(λx. apple(x) ∧ red(x))

Det

λP. ι(P)

N′ — red apple

λx. apple(x) ∧ red(x)

Adj

𝜆𝑃. 𝜆𝑥(𝑃(𝑥) ∧ red(𝑥))

N

λx. apple(x)

VP — is on the table

λx. on(x, ι(λy. table(y)))

V

λP.P

PP — on the table

λx. on(x, ι(λy. table(y)))

P

λyλx. on(x,y)

NP — the table

ι(λy. table(y))

Det

λP. ι(P)

N

λy. table(y)

λ function abstraction ι unique/definite (“the”) ∧ logical and PM predicate modification FA function application

NLP and Knowledge Representation: Norvig (1986) Ph.D.

27

Peter Norvig’s thesis: A Unified Theory of Inference for Text Understanding (1986)

The language analyzed:

​

In a poor fishing village built on an island not far from the coast of China, a young boy named Chang Lee lived with his widowed mother. Every day, little Chang bravely set off with his net, hoping to catch a few fish from the sea, which they could sell and have a little money to buy bread.

1. There is a sea, which surrounds the island, is used by the villagers for fishing, and forms part of the coast of China
2. Chang intends to trap fish in his net, which is a fishing net
3. The word which refers to the fish
4. The word they refers to Chang and his mother

Compile Knowledge in KB & Then Infer

“As we have just seen, a suitable knowledge base is a prerequisite for making proper inferences” (p. 4). It’s built to enable inferences

• System had 6 general forms of inference; 2 pairs, so 4 basic types:
• Elaboration: Filling a slot to connect two entities
• John got piggybank for REASON have money for REASON buy present
• Reference Resolution: Hey – it’s coreference!!!
• View Application: The Red Sox killed the Yankees
• KILLED is not animal; KILLING is viewed as a DEFEAT-CONVINCINGLY
• Concretization: Infer more specific
• TRAVELLING in an AUTOMOBILE is an instance of
• DRIVING

​

28

NLP in the 1970s and 1980s

29

• Foundational work on speech recognition: stochastic modeling, hidden Markov models, the “noisy channel”
• Ideas from this work would

later revolutionize NLP!

• Logic programming, rules-driven AI, deterministic algorithms for syntactic parsing (e.g., LFG)
• Increasing interest in natural language understanding: SHRDLU, LUNAR, CHAT-80
• But symbolic AI hit the wall: “AI winter”

3. Statistical or Probabilistic NLP (“StatNLP”)

and then more general Supervised ML for NLP

1993–2012

​

30

Claude Shannon

31

A Mathematical Theory of Communication (1948)

32

https://www.quantamagazine.org/how-claude-shannons-information-theory-invented-the-future-20201222/

The noisy channel model

Claude Shannon

The statistical revolution: 1990s

• Influx of new ideas from EE & ASR: probabilistic modeling, corpus statistics, supervised learning, empirical evaluation
• New sources of data: explosion of machine-readable text;

human-annotated training data (e.g., the Penn Treebank)

• Annotated data + algorithms + probabilistic prediction
• Lowered expectations: forget full semantic understanding, let’s do text cat, part-of-speech tagging, NER, and parsing!
• Tools: Naïve Bayes classifiers, HMMs, PCFGs, CRFs (CS228!)

Fred Jelinek

Probabilistic spelling correction

• “She is a stellar and versatile acress whose combination of sass and glamour attracts”
• Let’s estimate probabilities of corrections following one another
• P(actress|versatile)= .0019
• P(across|versatile)= .000092

​

• P(“versatile actress whose”) = .00019 × .0043
• P(“versatile across whose”) = .000092 ×.000026

​

​

36

The rise of the machines: 2000s

• Availability of much more powerful machines
• Consolidation of the gains of the statistical revolution
• More sophisticated statistical modeling and machine
• learning algorithms: MaxEnt, SVMs, Bayes Nets, LDA, etc.
• Big big data: 100x growth of web, massive server farms
• Focus shifting from supervised to unsupervised learning
• Revived interest in higher-level semantic applications

​

4.Deep Learning or Artificial Neural Networks for NLP

4a. Neural NLP 2013–2021

​

​

36

NLP – DL to LLMs

37

Symbolic AI vs. “Cybernetics”

Stanford, the home of “Symbolic Systems”

38

• “Symbolic systems” studies systems of meaningful symbols that represent the world about us—like human languages, logics, and programming languages—and the systems that work with these symbols—like brains, computers, and complex social systems
• While “cognitive science” focuses on the mind and intelligence as naturally occurring phenomena, Symbolic Systems gives equal focus to human-constructed systems that use symbols to communicate and to represent information

Jon Barwise (1942–2000)

Symbolic systems versus their processors

• Language is the symbolic system par excellence; we should study and make use of its symbolic structure
• This does not show that the main processor of these symbols—the human brain—is implemented as a physical symbol system
• We need not design NLP systems as physical symbol systems
• The brain is more like a neural network model
• Artificial neural network models scale better and can capture the world represented by symbols

​

40

cat

Source: https://www.freepik.com/free-photos-vectors/cat-drawing

Deep Learning Breakthroughs by Hinton

… at the University of Toronto, 2009–2012

41

Deep Learning for Speech Recognition

41

• Speech recognition had first shown the breakthrough success of probabilistic methods: HMMs and GMMs
• The first breakthrough results of “deep learning” on large datasets also happened in speech recognition
• George Dahl et al. (2010/2012): Context-Dependent Pre-trained Deep Neural Networks for Large Vocabulary Speech Recognition

Words

“(Artificial) neural (network)” or

“deep learning” models for word meaning

42

We learn to represent a word as a vector of numbers

0.286

0.792

−0.177

−0.107

0.109

−0.542

0.349

0.271

versatile =

Similar vectors = similar meaning

Learn vectors via distributional similarity

How do we learn those word vectors?

“You shall know a word by the company it keeps”

(J. R. Firth 1957: 11)

any devices with a web browser, from laptops and tablets to smart phones Users can download it for home computers or laptops from Microsoft Update website

​

🡼 These words will represent laptops 🡽

​

Defining similarity via contextual distributions in texts is one of the most successful ideas of modern computational linguistics

An RNN encoder-decoder network

I

am

a

student

<EOS> Je

suis

étudiant

Je

suis

étudiant <EOS>

Encoder

Decoder

h_t = tanh(W[x_t] + Uh_t–1 + b)

An LSTM encoder-decoder network

[Sutskever et al. 2014]

Die Proteste waren am Wochenende eskaliert <EOS> The protests escalated over

the weekend

The protests escalated

over

the weekend <EOS>

Encoder: Builds up sentence

Source

sentence

Translation generated

Feeding in

last word

Decoder

Bottleneck

MT progress over time

20.3

​

​

13.5

​

​

6.8

​

​

0.

27.

2013 2014 2015

Source: http://www.meta-net.eu/events/meta-forum-2016/slides/09_sennrich.pdf

2016

Phrase-based SMT Syntax-based SMT Neural MT

On Google Neural MT, see: https://www.nytimes.com/2016/12/14/magazine/the-great-ai-awakening.html

[Edinburgh En-De WMT newstest2013 Cased BLEU; NMT 2015 from U. Montréal]

47

4.Deep Learning or Artificial Neural Networks for NLP

4b. Large Language Models 2022–present

​

​

48

The Rise of Generative AI: S&P 500 Companies Discussing “AI”

ChatGPT launch

Source: https://insight.factset.com/more-than-40-of-sp-500-companies-have-cited-ai-on-earnings-calls-for-5th-straight-quarter

50% of S&P 500

​

40% of S&P 500

| 2024 | 2025

Large Language Models

50

Source: GPT 4o

An abstract image in pastel manga style of a large language model as a big machine that takes in text and produces fresh writing on an endless scroll and which is maintained by a large number of scientists and engineers.

The History of Language Models

Andrey A. Markov explores consonant-vowel transition probabilities in

Alexander Pushkin novel, Eugene Onegin, developing Markov Models

Claude E. Shannon develops A Mathematical Theory of Information;

explores character/word-level n-gram models, entropy, text generation

Frederick Jelinek’s group at IBM defines and names the modern concept of a (probabilistic) “language model” for next token prediction. Used for spelling correction, speech recognition, machine translation….

1913

1948

1975

51

But this technology wasn’t considered a pathway to machines with artificial intelligence: For that we needed models of memory, knowledge representations, planning systems, and reasoning over abstract concepts

The History of Large Language Models

CPAT-Tree-Based Language Models with an Application for Text Verification in

Chinese. ROCLing 1998. First use of “LLM” trigram I know of; 200M word corpus

A Neural Probabilistic Language Model. Bengio, Ducharme & Vincent NIPS 2000

First neural language model built on 32 million token corpus, 31K vocab

Large Language Models in Machine Translation. Brants, Popat, Xu, Och and

Dean. EMNLP 2007. 2 trillion token corpus n-gram model of up to 5-grams

1998

2000

2007

GPT (Radford, Narasimhan, Salimans & Sutskever) and BERT (Devlin, Chang, Lee & Toutanova). 3.3 billion token corpus

100+ billion parameter neural language models trained on > 1 trillion tokens:

GPT-3, GPT-4, PaLM 2, Llama 3, Nemotron-4, ….

2018

2020–

The History of Large Language Models

CPAT-Tree-Based Language Models with an Application for Text Verification in

Chinese. ROCLing 1998. First use of “LLM” trigram I know of; 200M word corpus

1998

Vincent NIPS 2000

First neural l

babilistic Language Model. Bengio, Ducharme &

anguage model built on 32 million token corpus

, 31K vocab

2000

Large Language M

Dean. EMNLP 200

odels in Machine Translation. Brants, Popat, Xu,

7. 2 trillion token corpus n-gram model of up to

Och and

5-grams

2007

ang,

Lee & Toutanova). 3.3 bill

an, Salimans & Sutskever) and BERT (Devlin, Ch ion token corpus

2018

GPT-3, GPT-4, PaLM 2, Llama 3,

nguage models trained on > 1 trillion tokens:

Nemotron-4, ….

2020–

^{A Neural Pro} Not enough compute!

Not enough model flexibility!

GPT (Radford, Narasimh _{Not enough data!}

100+ billion parameter neural la _{LLMs go brrr!}

Consultants using GPT-4 outperform non-users

• Consultants (from Boston Consulting Group) using GPT-4 finished 12.2% more tasks on average, completed tasks 25.1% more quickly, and produced 40% higher quality
• results than those not using AI
• Use of an LLM particularly improved the performance of lower-performing humans
• Results vary depending on the task
• — Dell’Acqua et al. 2023; Mollick 2023

Distribution of output quality across all tasks. Blue group did not use GPT-4; green and red groups used GPT-4; red group got additional training on how to use AI.

Can GPT-4 write fiction that matches the quality of New Yorker fiction?

Good news! No! (At least in 2023….)

GPT-4 is still 3–10x worse at creative writing!

56

https://arxiv.org/abs/ 2309.14556

What about 2026? Seems answer is still no..

56