In organic light-emitting diodes (OLEDs), a stack of multiple organic
layers facilitates charge flow from the low work function [~4.7
electron volts (eV)] of the transparent electrode (tin-doped indium
oxide, ITO) to the deep energy levels (~6 eV) of the active
light-emitting organic materials. We demonstrate a chlorinated ITO
transparent electrode with a work function of >6.1 eV that provides a
direct match to the energy levels of the active light-emitting
materials in state-of-the art OLEDs. A highly simplified green OLED
with a maximum external quantum efficiency (EQE) of 54% and power
efficiency of 230 lumens per watt using outcoupling enhancement was
demonstrated, as were EQE of 50% and power efficiency of 110 lumens
per watt at 10,000 candelas per square meter.
On the other side, Ernest Rutherford (physicist, 1871–1937)
disdained mere description, saying "All science is either physics or
stamp collecting." Chomsky stands with him: "You can also collect
butterflies and make many observations. If you like butterflies,
that's fine; but such work must not be confounded with research, which
is concerned to discover explanatory principles."
It seems that the algorithmic modeling culture is what Chomsky is
objecting to most vigorously. It is not just that the models are
statistical (or probabilistic), it is that they produce a form that,
while accurately modeling reality, is not easily interpretable by
humans, and makes no claim to correspond to the generative process
used by nature. In other words, algorithmic modeling describes what
does happen, but it doesn't answer the question of why.
Breiman's article explains his objections to the first
culture, data modeling. Basically, the conclusions made by data
modeling are about the model, not about nature. (Aside: I remember in
2000 hearing James
Martin, the leader of the Viking missions to Mars, saying that his
job as a spacecraft engineer was not to land on Mars, but to land on
the model of Mars provided by the geologists.) The problem is, if the
model does not emulate nature well, then the conclusions may be
wrong. For example, linear regression is one of the most powerful
tools in the statistician's toolbox. Therefore, many analyses start
out with "Assume the data are generated by a linear model..." and lack
sufficient analysis of what happens if the data are not in fact
generated that way. In addition, for complex problems there are
usually many alternative good models, each with very similar measures of goodness
of fit. How is the data modeler to choose between them? Something has
to give. Breiman is inviting us to give up on the idea that we can
uniquely model the true underlying form of nature's function
from inputs to outputs. Instead he asks us to be satisfied with a
function that accounts for the observed data well, and generalizes to
new, previously unseen data well, but may be expressed in a complex
mathematical form that may bear no relation to the "true" function's
form (if such a true function even exists). Chomsky takes the opposite
approach: he prefers to keep a simple, elegant model, and give up on
the idea that the model will represent the data well. Instead, he
declares that what he calls performance data—what people
actually do—is off limits to linguistics; what really matters is
competence—what he imagines that they should do.
Bill O'Reilly
Laplace
In January of 2011, television personality Bill O'Reilly weighed in
on more than one culture war with his statement "tide goes in, tide
goes out. Never a miscommunication. You can't explain that,"
which he proposed as an argument for the existence of God. O'Reilly
was ridiculed by his detractors for not knowing that tides can be
readily and concisely explained by a system of partial differential equations
describing the gravitational interaction of sun, earth, and moon (a
fact that was first worked out by Laplace in 1776 and has been
considerably refined since; when asked by Napoleon why the creator did
not enter into his calculations, Laplace said "I had no need of that
hypothesis."). (O'Reilly also seems not to know about Deimos and
Phobos (two of my favorite moons in the entire solar system, along with
Europa, Io, and Titan), nor that Mars and Venus orbit the sun, nor that the reason Venus has no
moons is because it is so close to the sun that there is scant room for a
stable lunar orbit.)
But O'Reilly realizes that it doesn't matter what
his detractors think of his astronomical ignorance, because his
supporters think he has gotten exactly to the key issue: why?
He doesn't care how the tides work, tell him why they
work. Why is the moon at the right distance to provide a gentle tide,
and exert a stabilizing effect on earth's axis of rotation, thus
protecting life here? Why does gravity work the way it does? Why does
anything at all exist rather than not exist? O'Reilly is correct that
these why questions can only be addressed by mythmaking, religion or
philosophy, not by science.
Chomsky has a philosophy based on the
idea that we should focus on the deep whys and that mere
explanations of reality don't matter. In this, Chomsky is in complete
agreement with O'Reilly. (I recognize that the previous sentence would
have an extremely low probability in a probabilistic model trained
on a newspaper or TV corpus.)
Chomsky believes a theory of language should be simple and understandable,
like a linear regression model where we know the underlying process is
a straight line, and all we have to do is estimate the slope and
intercept.
For example, consider the notion of a pro-drop
language from Chomsky's Lectures
on Government and Binding (1981). In English we say, for example,
"I'm hungry," expressing the pronoun "I". But in Spanish, one
expresses the same
thought with
"Tengo hambre" (literally "have hunger"), dropping the
pronoun "Yo". Chomsky's theory is that there is a "pro-drop parameter"
which is "true" in Spanish and "false" in English, and that once we
discover the small set of parameters that describe all languages, and
the values of those parameters for each language, we will have
achieved true understanding.
Dana Carvey
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
Breiman's article explains his objections to the first
culture, data modeling. Basically, the conclusions made by data
modeling are about the model, not about nature. (Aside: I remember in
2000 hearing James
Martin, the leader of the Viking missions to Mars, saying that his
job as a spacecraft engineer was not to land on Mars, but to land on
the model of Mars provided by the geologists.) The problem is, if the
model does not emulate nature well, then the conclusions may be
wrong. For example, linear regression is one of the most powerful
tools in the statistician's toolbox. Therefore, many analyses start
out with "Assume the data are generated by a linear model..." and lack
sufficient analysis of what happens if the data are not in fact
generated that way. In addition, for complex problems there are
usually many alternative good models, each with very similar measures of goodness
of fit. How is the data modeler to choose between them? Something has
to give. Breiman is inviting us to give up on the idea that we can
uniquely model the true underlying form of nature's function
from inputs to outputs. Instead he asks us to be satisfied with a
function that accounts for the observed data well, and generalizes to
new, previously unseen data well, but may be expressed in a complex
mathematical form that may bear no relation to the "true" function's
form (if such a true function even exists). Chomsky takes the opposite
approach: he prefers to keep a simple, elegant model, and give up on
the idea that the model will represent the data well. Instead, he
declares that what he calls performance data—what people
actually do—is off limits to linguistics; what really matters is
competence—what he imagines that they should do.
Bill O'Reilly
Laplace
In January of 2011, television personality Bill O'Reilly weighed in
on more than one culture war with his statement "tide goes in, tide
goes out. Never a miscommunication. You can't explain that,"
which he proposed as an argument for the existence of God. O'Reilly
was ridiculed by his detractors for not knowing that tides can be
readily and concisely explained by a system of partial differential equations
describing the gravitational interaction of sun, earth, and moon (a
fact that was first worked out by Laplace in 1776 and has been
considerably refined since; when asked by Napoleon why the creator did
not enter into his calculations, Laplace said "I had no need of that
hypothesis."). (O'Reilly also seems not to know about Deimos and
Phobos (two of my favorite moons in the entire solar system, along with
Europa, Io, and Titan), nor that Mars and Venus orbit the sun, nor that the reason Venus has no
moons is because it is so close to the sun that there is scant room for a
stable lunar orbit.)
But O'Reilly realizes that it doesn't matter what
his detractors think of his astronomical ignorance, because his
supporters think he has gotten exactly to the key issue: why?
He doesn't care how the tides work, tell him why they
work. Why is the moon at the right distance to provide a gentle tide,
and exert a stabilizing effect on earth's axis of rotation, thus
protecting life here? Why does gravity work the way it does? Why does
anything at all exist rather than not exist? O'Reilly is correct that
these why questions can only be addressed by mythmaking, religion or
philosophy, not by science.
Chomsky has a philosophy based on the
idea that we should focus on the deep whys and that mere
explanations of reality don't matter. In this, Chomsky is in complete
agreement with O'Reilly. (I recognize that the previous sentence would
have an extremely low probability in a probabilistic model trained
on a newspaper or TV corpus.)
Chomsky believes a theory of language should be simple and understandable,
like a linear regression model where we know the underlying process is
a straight line, and all we have to do is estimate the slope and
intercept.
For example, consider the notion of a pro-drop
language from Chomsky's Lectures
on Government and Binding (1981). In English we say, for example,
"I'm hungry," expressing the pronoun "I". But in Spanish, one
expresses the same
thought with
"Tengo hambre" (literally "have hunger"), dropping the
pronoun "Yo". Chomsky's theory is that there is a "pro-drop parameter"
which is "true" in Spanish and "false" in English, and that once we
discover the small set of parameters that describe all languages, and
the values of those parameters for each language, we will have
achieved true understanding.
Dana Carvey
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
In January of 2011, television personality Bill O'Reilly weighed in
on more than one culture war with his statement "tide goes in, tide
goes out. Never a miscommunication. You can't explain that,"
which he proposed as an argument for the existence of God. O'Reilly
was ridiculed by his detractors for not knowing that tides can be
readily and concisely explained by a system of partial differential equations
describing the gravitational interaction of sun, earth, and moon (a
fact that was first worked out by Laplace in 1776 and has been
considerably refined since; when asked by Napoleon why the creator did
not enter into his calculations, Laplace said "I had no need of that
hypothesis."). (O'Reilly also seems not to know about Deimos and
Phobos (two of my favorite moons in the entire solar system, along with
Europa, Io, and Titan), nor that Mars and Venus orbit the sun, nor that the reason Venus has no
moons is because it is so close to the sun that there is scant room for a
stable lunar orbit.)
But O'Reilly realizes that it doesn't matter what
his detractors think of his astronomical ignorance, because his
supporters think he has gotten exactly to the key issue: why?
He doesn't care how the tides work, tell him why they
work. Why is the moon at the right distance to provide a gentle tide,
and exert a stabilizing effect on earth's axis of rotation, thus
protecting life here? Why does gravity work the way it does? Why does
anything at all exist rather than not exist? O'Reilly is correct that
these why questions can only be addressed by mythmaking, religion or
philosophy, not by science.
Chomsky has a philosophy based on the
idea that we should focus on the deep whys and that mere
explanations of reality don't matter. In this, Chomsky is in complete
agreement with O'Reilly. (I recognize that the previous sentence would
have an extremely low probability in a probabilistic model trained
on a newspaper or TV corpus.)
Chomsky believes a theory of language should be simple and understandable,
like a linear regression model where we know the underlying process is
a straight line, and all we have to do is estimate the slope and
intercept.
For example, consider the notion of a pro-drop
language from Chomsky's Lectures
on Government and Binding (1981). In English we say, for example,
"I'm hungry," expressing the pronoun "I". But in Spanish, one
expresses the same
thought with
"Tengo hambre" (literally "have hunger"), dropping the
pronoun "Yo". Chomsky's theory is that there is a "pro-drop parameter"
which is "true" in Spanish and "false" in English, and that once we
discover the small set of parameters that describe all languages, and
the values of those parameters for each language, we will have
achieved true understanding.
Dana Carvey
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
But O'Reilly realizes that it doesn't matter what
his detractors think of his astronomical ignorance, because his
supporters think he has gotten exactly to the key issue: why?
He doesn't care how the tides work, tell him why they
work. Why is the moon at the right distance to provide a gentle tide,
and exert a stabilizing effect on earth's axis of rotation, thus
protecting life here? Why does gravity work the way it does? Why does
anything at all exist rather than not exist? O'Reilly is correct that
these why questions can only be addressed by mythmaking, religion or
philosophy, not by science.
Chomsky has a philosophy based on the
idea that we should focus on the deep whys and that mere
explanations of reality don't matter. In this, Chomsky is in complete
agreement with O'Reilly. (I recognize that the previous sentence would
have an extremely low probability in a probabilistic model trained
on a newspaper or TV corpus.)
Chomsky believes a theory of language should be simple and understandable,
like a linear regression model where we know the underlying process is
a straight line, and all we have to do is estimate the slope and
intercept.
For example, consider the notion of a pro-drop
language from Chomsky's Lectures
on Government and Binding (1981). In English we say, for example,
"I'm hungry," expressing the pronoun "I". But in Spanish, one
expresses the same
thought with
"Tengo hambre" (literally "have hunger"), dropping the
pronoun "Yo". Chomsky's theory is that there is a "pro-drop parameter"
which is "true" in Spanish and "false" in English, and that once we
discover the small set of parameters that describe all languages, and
the values of those parameters for each language, we will have
achieved true understanding.
Dana Carvey
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
Chomsky has a philosophy based on the
idea that we should focus on the deep whys and that mere
explanations of reality don't matter. In this, Chomsky is in complete
agreement with O'Reilly. (I recognize that the previous sentence would
have an extremely low probability in a probabilistic model trained
on a newspaper or TV corpus.)
Chomsky believes a theory of language should be simple and understandable,
like a linear regression model where we know the underlying process is
a straight line, and all we have to do is estimate the slope and
intercept.
For example, consider the notion of a pro-drop
language from Chomsky's Lectures
on Government and Binding (1981). In English we say, for example,
"I'm hungry," expressing the pronoun "I". But in Spanish, one
expresses the same
thought with
"Tengo hambre" (literally "have hunger"), dropping the
pronoun "Yo". Chomsky's theory is that there is a "pro-drop parameter"
which is "true" in Spanish and "false" in English, and that once we
discover the small set of parameters that describe all languages, and
the values of those parameters for each language, we will have
achieved true understanding.
Dana Carvey
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
For example, consider the notion of a pro-drop
language from Chomsky's Lectures
on Government and Binding (1981). In English we say, for example,
"I'm hungry," expressing the pronoun "I". But in Spanish, one
expresses the same
thought with
"Tengo hambre" (literally "have hunger"), dropping the
pronoun "Yo". Chomsky's theory is that there is a "pro-drop parameter"
which is "true" in Spanish and "false" in English, and that once we
discover the small set of parameters that describe all languages, and
the values of those parameters for each language, we will have
achieved true understanding.
Dana Carvey
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
The problem is that reality is messier than this theory. Here are
some dropped pronouns in English:
"Not gonna do it. Wouldn't be prudent." (Dana Carvey, impersonating
George H. W. Bush)
"Thinks he can outsmart us, does he?" (Evelyn Waugh, The Loved One)
"Likes to fight, does he?" (S.M. Stirling, The
Sunrise Lands)
"Thinks he's all that." (Kate Brian, Lucky
T)
"Go for a walk?" (countless dog owners)
"Gotcha!" "Found it!" "Looks good to me!" (common expressions)
Linguists can argue over the interpretation of these facts for hours
on end, but the diversity of language seems to be much more complex
than a single Boolean value for a pro-drop parameter. We shouldn't
accept a theoretical framework that places a priority on making the
model simple over making it accurately reflect reality.
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
From the beginning, Chomsky has focused on the generative
side of language. From this side, it is reasonable to tell a
non-probabilistic story: I know definitively the idea I want to
express—I'm starting from a single semantic form—thus all I
have to do is choose the words to say it; why can't that be a
deterministic, categorical process? If Chomsky had focused on the
other side, interpretation, as Claude Shannon did, he may have changed
his tune. In interpretation (such as speech recognition) the listener
receives a noisy, ambiguous signal and needs to decide which of many
possible intended messages is most likely. Thus, it is obvious that
this is inherently a probabilistic problem, as was recognized early on
by all researchers in speech recognition, and by scientists in other
fields that do interpretation: the astronomer Laplace said in 1819
"Probability theory is nothing more than common sense reduced to
calculation," and the physicist James Maxwell said in 1850 "The true
logic for this world is the calculus of Probabilities, which takes
account of the magnitude of the probability which is, or ought to be,
in a reasonable man's mind."
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
Finally, one more reason why Chomsky dislikes statistical models is
that they tend to make linguistics an empirical science (a science
about how people actually use language) rather than a mathematical
science (an investigation of the mathematical properties of models of
formal language, not of language itself). Chomsky prefers the later, as evidenced by his statement
in Aspects of the Theory of
Syntax (1965):
Linguistic theory is mentalistic, since it is concerned with
discovering a mental reality underlying actual behavior. Observed use of language ... may
provide evidence ... but surely cannot constitute the subject-matter
of linguistics, if this is to be a serious discipline.
I can't imagine Laplace saying that observations of the planets
cannot constitute the subject-matter of orbital mechanics, or Maxwell
saying that observations of electrical charge cannot constitute the
subject-matter of electromagnetism. It is true that physics considers
idealizations that are abstractions from the messy real world. For
example, a class of mechanics problems ignores friction. But that
doesn't mean that friction is not considered part of the
subject-matter of physics.
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
Plato's cave
So how could Chomsky say that observations of language cannot be
the subject-matter of linguistics? It seems to come from his viewpoint
as a Platonist
and a Rationalist
and perhaps a bit of a Mystic. As
in Plato's allegory of
the cave, Chomsky thinks we should focus on the ideal, abstract
forms that underlie language, not on the superficial manifestations of
language that happen to be perceivable in the real world. That is why
he is not interested in language performance. But Chomsky, like Plato,
has to answer where these ideal forms come from. Chomsky (1991) shows
that he is happy with a Mystical answer, although he shifts vocabulary
from "soul" to "biological endowment."
Plato's answer was that the knowledge is 'remembered'
from an earlier existence. The answer calls for a mechanism: perhaps
the immortal soul ... rephrasing Plato's answer in terms more
congenial to us today, we will say that the basic properties of
cognitive systems are innate to the mind, part of human biological
endowment.
Lascaux Horse
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
It was reasonable for Plato to think that the ideal of, say, a
horse, was more important than any individual horse we can perceive in
the world. In 400BC, species were thought to be eternal and
unchanging. We now know that is not true; that the horses on another
cave wall—in Lascaux—are now extinct, and that current
horses continue to evolve slowly over time. Thus there is no such
thing as a single ideal eternal "horse" form.
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
We also now know that language is like that as well: languages are
complex, random, contingent biological processes that are subject to
the whims of evolution and cultural change. What constitutes a
language is not an eternal ideal form, represented by the settings of
a small number of parameters, but rather is the contingent outcome of
complex processes. Since they are contingent, it seems they can
only be analyzed with probabilistic models. Since people have to
continually understand the uncertain, ambiguous, noisy speech of
others, it seems they must be using something like probabilistic reasoning. Chomsky for some reason
wants to avoid this, and therefore he must declare the actual facts of
language use out of bounds and declare that true linguistics only
exists in the mathematical realm,
where he can impose the formalism he wants. Then, to get
language from this abstract, eternal, mathematical realm into the
heads of people, he must fabricate a mystical facility that is exactly
tuned to the eternal realm. This may be very
interesting from a mathematical point of view, but it misses the point
about what language is, and how it works.
Thanks
Thanks to Ann Farmer, Fernando Pereira, Dan Jurafsky, Hal Varian, and others for comments
and suggestions on this essay.
Annotated Bibliography
Abney, Steve (1996) Statistical Methods and
Linguistics, in Klavans and Resnik (eds.) The Balancing Act: Combining Symbolic and
Statistical Approaches to Language, MIT Press.
An excellent overall introduction to the statistical
approach to language processing, and covers some ground that is not
addressed often, such as language change and individual differences.
Breiman, Leo (2001) Statistical Modeling: The
Two Cultures, Statistical Science, Vol. 16, No. 3, 199-231.
Breiman does a great job of describing the two
approaches, explaining the benefits of his approach, and defending
his points in the vary interesting commentary with eminent
statisticians: Cox, Efron, Hoadley, and Parzen.
Chomsky, Noam (1956) Three Models
for the Description of Language, IRE Transactions on
Information theory (2), pp. 113-124.
Compares finite state, phrase structure, and
transformational grammars. Introduces "colorless green ideas sleep
furiously."
Chomsky, Noam (1967) Syntactic Structures, Mouton.
A book-length exposition of Chomsky's theory that was
the leading exposition of linguistics for a decade. Claims that
probabilistic models give no insight into syntax.
Chomsky, Noam (1969) Some Empirical
Assumptions in Modern Philosophy of Language, in Philosophy,
Science and Method: Essays in Honor or Ernest Nagel,
St. Martin's Press.
Claims that the notion "probability of a sentence" is
an entirely useless notion.
Chomsky, Noam (1981) Lectures
on government and binding, de Gruyer.
A revision of Chomsky's theory; this version
introduces Universal Grammar. We cite it for the coverage of
parameters such as pro-drop.
Chomsky, Noam (1991) Linguistics
and adjacent fields: a personal view, in Kasher (ed.), A
Chomskyan Turn, Oxford.
I found the Plato quotes in this
article, published by the Communist Party of Great Britain, and
apparently published by someone with no linguistics training
whatsoever, but with a political agenda.
Gold, E. M. (1967) Language
Identification in the Limit, Information and Control,
Vol. 10, No. 5, pp. 447-474.
Gold proved a result in formal language theory that
we can state (with some artistic license) as this: imagine a game
between two players, guesser and chooser. Chooser says to
guesser, "Here is an infinite number of languages. I'm going to
choose one of them, and start reading sentences to you that come
from that language. On your N-th birthday there will be a True-False
quiz where I give you 100 sentences you haven't heard yet, and you
have to say whether they come from the language or not." There are
some limits on what the infinite set looks like and on how
the chooser can pick sentences (he can be deliberately
tricky, but he can't just repeat the same sentence over and over,
for example). Gold's
result is that if the infinite set of languages are all generated by
context-free grammars then there is no strategy for guesser that
guarantees she gets 100% correct every time, no matter what N you
choose for the birthday. This result was
taken by Chomsky and others to mean that it is impossible for
children to learn human languages without having an innate "language
organ." As Johnson (2004) and others show, this was an invalid
conclusion; the task of getting 100% on the quiz (which Gold called
language identification)
really has nothing in common with the task of language acquisition
performed by children, so Gold's Theorem has no
relevance.
Horning, J. J. (1969) A study of grammatical
inference, Ph.D. thesis, Stanford Univ.
Where Gold found a negative result—that
context-free languages were not identifiable from examples, Horning found a positive result—that probabilistic
context-free languages are identifiable (to within an arbitrarily
small level of error). Nobody doubts that
humans have unique innate capabilities for understanding language
(although it is unknown to what extent these capabilities are
specific to language and to what extent they are general cognitive
abilities related to sequencing and forming abstractions). But
Horning proved in 1969 that Gold cannot be used as a convincing
argument for an innate language organ that specifies all of language
except for the setting of a few parameters.
Johnson, Kent (2004) Gold's
Theorem and cognitive science, Philosophy of Science,
Vol. 71, pp. 571-592.
The best article I've seen on what Gold's Theorem
actually says and what has been claimed about it (correctly and
incorrectly). Concludes that Gold has something to say about formal
languages, but nothing about child language
acquisition.
Lappin, Shalom and Shieber, Stuart M. (2007) Machine
learning theory and practice as a source of insight into universal
grammar., Journal of Linguistics, Vol. 43, No. 2,
pp. 393-427.
An excellent article discussing the poverty of the
stimulus, the fact that all models have bias, the difference
between supervised and unsupervised learning, and modern (PAC or VC)
learning theory. It provides
alternatives to the model of Universal Grammar consisting of a fixed
set of binary parameters.
Manning, Christopher (2002) Probabilistic
Syntax, in Bod, Hay, and Jannedy (eds.), Probabilistic
Linguistics, MIT Press.
A compelling introduction to probabilistic syntax,
and how it is a better model for linguistic facts than categorical
syntax. Covers "the joys and perils of corpus
linguistics."
Norvig, Peter (2007) How to Write a Spelling
Corrector, unpublished web page.
Shows working code to implement a probabilistic,
statistical spelling correction algorithm.
Norvig, Peter (2009) Natural
Language Corpus Data, in Seagran and Hammerbacher (eds.),
Beautiful Data, O'Reilly.
Expands on the essay above; shows how to implement
three tasks: text segmentation, cryptographic decoding, and spelling
correction (in a slightly more complete form than the previous essay).
Pereira, Fernando (2002) Formal
grammar and information theory: together again?, in Nevin and
Johnson (eds.), The Legacy of Zellig Harris, Benjamins.
When I set out to write the page you are reading now,
I was concentrating on the events that took place in Cambridge,
Mass., 4800 km from home. After doing some research I was surprised
to learn that the authors of
two of the three best articles on this subject sit within a total of
10 meters from my desk: Fernando Pereira and Chris Manning. (The
third, Steve Abney, sits 3700 km away.) But perhaps I shouldn't have
been surprised. I remember giving a talk at ACL on the corpus-based
language models used at Google, and having Fernando, then a
professor at U. Penn., comment "I feel like I'm a particle physicist
and you've got the only super-collider." A few years later he moved
to Google. Fernando is also famous for his quote "The older I get, the
further down the Chomsky Hierarchy I go." His article here covers
some of the same ground as mine, but he goes farther in explaining
the range of probabilistic models available and how they are useful.
Plato (c. 380BC) The
Republic.
Cited here for the allegory of the cave.
Shannon, C.E. (1948) A
Mathematical Theory of Communication, The Bell System
Technical Journal, Vol. 27, pp. 379-423.
An enormously influential article that started the
field of information theory and introduced the term "bit" and the noisy
channel model, demonstrated successive n-gram approximations of
English, described Markov models of language, defined entropy with
respect to these models, and enabled the growth of the
telecommunications industry.
Peter Norvig
→ Baca artikel asli
.jpg)
![I bought the knock-off Pixel Watch and Fitbit Air bands, and it’s crazy how good they are [Gallery]](https://9to5google.com/wp-content/uploads/sites/4/2026/11/pixel-watch-band-dupes-1.jpg?quality=82&strip=all&resize=1200,628){kind=tracking}
.jpg?branch=production&width=8256&quality=75&auto=webp&crop=16:9)
.jpg)
.jpg)
