British Computer Society
Natural Language Translation Specialist Group
URL: http://www.bcs.org.uk/siggroup/sg37.htm
Machine Translation Review,
ISSN 1358-8346
No.9, April 1999 - pages 18-19
Document URL: http://www.bcs.org.uk/siggroup/nalatran/mtreview/mtr-9/mtr-9-7.htm
Document size: 3 A4 pages when printed
Book Review
by Oliver Mason
| Emmanuel Roche and Yves Schabes (eds) (1997) Finite-State Language Processing.
MIT Press, 464p. Price unknown. ISBN 0-262-1812-7. |
About forty years ago a well-known linguist stated that English was not a finite state language.
He justified this by pointing to phenomena such as the theoretical possibility of infinitely
embedding subordinate clauses. This statement put an end to attempts to describe language
using Markovian models, and it was only in the more engineering-oriented branch of speech
processing that such models survived in linguistics.
Nowadays finite state methods are coming back into fashion, as the orientation towards
empirical linguistics shows something that has been known in speech analysis for quite some
time: finite state methods are after all suitable for describing natural language, since infinite
embeddings are purely fictitious and do not actually happen very often in real life.
Today finite state processing is quite common in areas such as morphological analysis and
efficient storage of dictionaries on the computer. These and several other applications are
described in this book, which is a collection of fifteen papers by different authors from a
handful of research centres around the world.
The book is a good overall introduction to the possibilities of finite state processing.
However, it seems to be addressing two rather different target audiences at the same time, as
the chapters are pitched at widely differing levels. Some chapters are extremely technical and
require more knowledge of mathematics than just some automata theory. The algorithms are
described in an extremely formal way, which anybody who has only had a brief exposure to the
theory of formal languages would need a lot of time and effort to understand. In addition,
some of the algorithms are mainly of theoretical interest anyway.
On the other side of the spectrum are some chapters that are much easier to digest for the
average linguist who might take an interest in actually making use of those techniques
themselves. In particular, the chapters on local grammars are easy to understand, and it is easy
to see how a (rather large) collection of these may be used to describe language appropriately.
The book begins with an introduction to the basic principles of finite state methods, and the
operations that can be performed on automatons (such as making them deterministic,
intersecting and merging them).
This even includes some linguistic examples, rather than simply using toy languages (such as
anbn) as is customary in automata theory. The remaining chapters then investigate the
application of finite state methods in different linguistic areas.
And finite state methods can be usefully applied to almost every area of linguistics. Beginning
with phonology, coverage includes mophological analysis and the organisation of machine-
readable dictionaries, lexical analysis and local grammars, part-of-speech tagging, and several
aspects of parsing. In addition there are some more theoretical papers as well as two on
applications, namely information extraction and speech recognition.
A minor point of criticism is the organisation of the book; it might have been a consideration
to group the chapters differently. Phonology, for example, is only dealt with in the penultimate
chapter, instead of its more logical place before morphology. Chapters on the same topic, such
as parsing, are dispersed throughout the book, when they could equally well have been
grouped together to provide a more logical flow for the reader.
The chapters themselves are very interesting, presenting cutting edge research on applying
the rather old methodology to linguistic problems in new ways, showing that finite state
methods have been undeservedly neglected for a long time. As often with mathematical models
in linguistics, interfacing the formalism with the object of study is a difficult problem, as known
from the case of neural networks in language processing. For finite state machines, there are
several possible solutions demonstrated in the book, depending on which linguistic units are
involved.
The main drawback of this book is that it leaves the reader feeling a bit frustrated. After
having been teased with a display of the capabilities of finite state automata in language
processing there is no way to get started on your own research problems immediately, as you
are lacking all the computational tools to do so. Creating them yourself requires not only
programming skills but also a profound understanding of the algorithms described, which is
quite taxing even for the average computational linguist. I would have liked some pointers to
tools already available, which one can download and get started with.
Luckily some are available, and they are reasonably easy to find on the Web by searching for
the names of some of the authors. Here are just two sources, to save you going through the
trouble of searching yourself, but ideally the book should have included these pointers:
|
Despite a few shortcomings this book has succeeded in getting me interested in finite state
methods. It is quite encouraging to see how far you can go with this formalism, and a lot of
state-of-the-art language processing tools are in fact based on this technology. The mixture of
theoretical background and description of applications might after all be a good idea, as the
'easy' chapters get you interested, while the 'heavy' theoretical descriptions provide quite a
challenge which one would not take up under normal circumstances. But I still feel that this
book could have profited from a few 'intermediate' chapters, or some actual programming
code and working examples to illustrate the rather abstract formal descriptions of the
algorithms.
All in all this is a book worth reading even if you are not interested in all the theoretical
details. Finite state methods are too important to be left only to the mathematicians. If you
have access to the right tools, then you don't really need to know how to minimise an
automaton yourself, as long as you know what it is good for and how you can use it to tackle a
problem. After all, you don't have to know how a combustion engine works in order to drive a
car.