Chapter 11: Mathematical Methods
Processing of written and spoken human language is computation. However, language processing is not a single type of computation. The different levels of information encoding in our language as well as the spectrum of applications for language technology pose a range of very distinct computational tasks. Therefore a wide variety of mathematical methods have been employed in human language technology. Some of them have led to specialized tools for a very restricted task, while others are part of the mathematical foundations of the technology. In this overview a very general map is drawn that groups the different approaches. Some particularly relevant classes of methods are highlighted in the remaining sections of the chapter.
In the early days of language processing, most if not all researchers underestimated the complexity of the problem. Many of them tried to bypass a mathematical characterization of their tasks and solve the problem simply by looking at the envisaged inputs and outputs of their systems. Purely procedural early approaches to machine translation fall in this category. These attempts failed very badly. However, there is one major difference between language processing and most other areas with highly complex calculation tasks, e.g., computational meteorology. One system exists that can handle human language quite decently, i.e., the human cognitive system. Moreover, there is a scientific discipline that strives for a formal description of the human language faculty. Very soon the great majority of researchers became convinced that one needed to utilize insights from linguistics---including phonetics and psycholinguistics---in order to make progress in modelling the human language user.
Modern linguistics tries to characterize the mapping between a spoken or written utterance and its meaning. Linguists do this in roughly the following way. They break up the complex mapping into suitable levels of representation, specify representations in dedicated formalisms, and they employ the same formalisms for specifying the implicit linguistic knowledge of a human language user. Traditionally their main data are collected or invented example sentences, judged and interpreted by introspection. Almost exclusively, discrete symbolic methods have been employed for representing different types of information in linguistics. (The only exception was phonetic signal processing, where Fourier transformations converted the two-dimensional acoustic signal into a three-dimensional spectrogram.)
The mathematical methods of syntax, morphology and phonology are suited for describing sets of strings, especially hierarchically structured strings. Most of these methods came from formal language theory. Most notable is the formal theory of languages and grammars emerging from the Chomsky hierarchy, an inclusion hierarchy of classes of languages. Each class of languages corresponds to a certain level of computational complexity. For these classes of languages, classes of grammars were found that generate the languages. Each class of languages also corresponds to a type of automaton that accepts strings of a language. Typical for this research was the close interaction between theoretical computer science and formal syntax with strong influences in both directions. Much investigation has gone into the question of the proper characterization of human language with respect to the Chomsky hierarchy.
The grammars and automata of formal language theory can rarely be applied to natural language processing without certain modifications. The grammar models developed in linguistics do not directly correspond to the ones from formal language theory. A variety of grammar models have been designed in linguistics and language technology. Some of these
models are mentioned in section 3.3. For a comprehensive description you will have to resort to handbooks such as [JvSSV93]. A long tradition of work was devoted to efficient parsing algorithms for many grammar models. This work is summarized in section 1.6.
The grammars of formal language theory are rewrite systems with atomic nonterminal symbols that stand for lexical and syntactic categories. However, in human language such categories have complex properties that influence their syntactic distribution. Therefore mathematical tools were developed for expressing linguistic entities as sets of complex features. A new class of logic, so called feature logic evolved. This branch of research, often subsumed under the term unification grammar, had close links with similar developments in knowledge representation and programming languages. The specialized processing methods that were developed for unification grammars had strong connections with constraint logic programming. In this book, unification grammars are described in section 3.1. For a more detailed introduction, please refer to [Shi88].
The situation is somewhat different in semantics. Here representation languages are needed in which we can represent the meaning---or better informational content---of an utterance. In order to provide unambiguous representations of meaning that can serve as the basis for inferences, logic is employed. Many varieties of higher order predicate logic have been developed for this purpose. Special representation languages such as frame and script languages came from artificial intelligence (AI). In the last few years, many of them have received a logical foundation. General purpose and specialized inference techniques have been employed for interpreting the meaning representation in connection with knowledge about the linguistic context, situational context, and the world. Logical deduction is the inference technique mainly used, but there are also approaches that utilize abduction methods. For the use of some semantic formalisms in language technology, refer to section 3.5.
The last two decades witnessed a convergence of theoretical linguistics and language processing with respect to their mathematical methods. On the one hand, this movement proved very fruitful in many areas of language processing. On the other hand, it also lead to some disillusionment concerning the potentials of formal linguistic tools among practitioners of language technology.
Although the specification of linguistic knowledge improved quite a bit through the use of advanced representation techniques, the resulting systems still lacked coverage, robustness, and efficiency, the properties required for realistic applications. It even seemed that every increase in linguistic coverage was accompanied by a loss of efficiency since efficient processing methods for linguistic representation formalisms are still missing.
Encouraged by a breakthrough in the recognition of spoken words, many researchers turned to statistical data-driven methods for designing language technology applications. For most of them, the line of reasoning went as follows. Linguistic investigation of linguistic competence and cognitive modelling of human language processing have not yet achieved a sufficient understanding and formalization of the mapping from the language signal to the informational contents of the utterance or vice versa. However, only very few applications need the complete mapping anyway. Even if we had a formal model of the complete mapping, we do not have a model of the cognitive system that could support it, since AI has not come close to modelling human knowledge processing.
If one cannot get access to the human linguistic competence through standard methods of linguistic research, it may be possible to induce the knowledge necessary for a specific application indirectly by correlating linguistic data with the desired outputs of the machine. In case of a dictation system, this output is the appropriate written words. For a machine translation system, the output consists of the translated sentences. For an information access system the output will be a query to a data base. After decades of expecting technological progress mainly from investigating the cognitive structures and processes of the human language user, attention moved back to the linguistic data produced by humans and to be processed by language technology.
The predominant approach is based on an information theoretic view of language processing as a noisy-channel information transmission. In this metaphor, it is assumed that a message is transmitted which we have to recover from observing the output of the noisy channel. It is described as the source-channel model in section 1.6. The approach requires a model that characterizes the transmission by giving for every message the probability of the observed output. The other component is the language model which gives the so-called a-priori distribution, the probability of a message in its context to be sent.
A special type of stochastic finite-state automata, hidden Markov
models (HMMs) have been utilized for the recognition of spoken
words, syllables or phonemes (section 1.5).
Probabilistic
derivatives of many grammar models have been proposed. Statistical
methods are employed today for substituting or supporting discrete
symbolic methods in almost every area of language
processing. Examples of promising approaches are statistical
part-of-speech tagging (section 3.2),
probabilistic parsing (section 3.7),
ambiguity resolution (section 3.7),
lexical knowledge acquisition
[Pus92], and statistical
machine translation
[BCP
90].
A special area that has developed rapidly during the last few years,
mainly in conjunction with the statistical methods, is the
utilization of optimization techniques for spoken and
written language processing. Optimization methods are used to find
the best solution or solutions among a number of possible solutions
applying some evaluation criterion. Since the number of possible
solutions, e.g., word hypotheses for a whole utterance in speech
recognition, can be rather large, the search needs to be highly
efficient. Optimization techniques, especially from dynamic
programming, are presented in section 
.
Connectionist methods constitute a different paradigm for
statistical learning and probabilistic processing
on the basis of an
acquired language model. Neural nets have proven very useful
in pattern recognition. In language technology, both
self-trained and prestructured nets are explored for a variety of
tasks. A major problem for syntactic and semantic processing is the
limitations of connectionist methods
concerning the modelling of
recursion. A major problem for applying neural nets to
speech processing that stems from the temporal nature of speech is
time sequence matching. In section
connectionist methods for speech processing are summarized. A combination of
connectionist methods with hidden Markov models is
described.
Another major area of very promising new technology is the
development of specialized low-level processing methods for natural
language. Especially noteworthy is the renaissance of
finite-state processing techniques. Finite state transducers were applied with great success to morphological processing. These approaches are described in section .
Recently finite state parsers were constructed that out-perform their
competition in coverage and performance. The finite-state technology
for syntax is presented in section 3.2. Finite-state methods are also applied in semantics and in discourse modelling.
Challenges for future research concerning the individual mathematical methods are presented in the sections that describe them. We will conclude this section by addressing key research problems that extend over the multitude of approaches.
One major challenge is posed by the lack of good formal methods for concurrent symbolic processing. Although there have been various attempts to employ methods and programming languages for concurrent processing in language technology, the results are not yet convincing. The appropriate hardware and well-suited problems for parallel processing are there. What are missing are better formal concepts of concurrency in computation.
Badly needed for progress in language technology is a better general view linking the diverse formal approaches and characterizing their respective virtues and shortcomings. With respect to the employed mathematical methods we currently witness the coexistence of three major research paradigms, shown in Figure 11.1.
Figure 11.1: Major research paradigms.
However, when we look at individual research systems and new applications, we rarely see a system that does not combine formal tools from more than one of the paradigms. In most cases the observed combinations of methods are rather ad-hoc. There is no general methodology yet that tells us which mix of methods is most appropriate for a certain type of application.
A few examples from recent research may illustrate the relevant direction for future investigation:
Compilation methods may be used to relate high-level competence grammars and low-level performance methods [Als92,KKNVS95]. Alternatively, learning methods such as explanation-based learning can also be applied in order to derive low-level performance grammars from high-level linguistic specifications [Sam94].
The connections between statistical methods and general automata theory are addressed in [PRS94], where it is proposed that the concept of weighted finite-state automata (acceptors and transducers) may serve as the common formal foundation for language processing.
Statistical methods can be used for extending knowledge specified in high-level formalisms. An example is the learning of lexical valency information from corpora [Man93]. Statistical methods can also be used for deriving control information that may speed up processing with high-level grammars. Specific linguistic generalizations could be merged or intersected with statistical language models in order to improve their robustness. Intersecting linguistic and statistical models, for instance, can improve precision in part-of-speech tagging.
We expect that extensive research on the theoretical and practical connections among the diverse methods will lead to a more unified mathematical foundation of human language processing.