Linguistic Spaces: Kernel-based models of natural language

Abstract

This thesis discusses ways to employ a certain mathematical characterization of similarity, kernel functions, and machine learning techniques building on it to abstract from data-oriented models of language. A prominent task in machine learning and in linguistic modeling is the classification of data items, the recognition of grammatical features. A bit more complex is the modeling of surface-to-surface relations, e.g. in inflectional paradigms. These morphological changes reflect the underlying grammatical features. Traditional rule-based approaches to feature recognition and inflection fail to explain local regularities within the so-called exceptions. Many linguistic domains exhibit islands of reliability (Albright 2002) both within classes of exceptions and the regular cases. For its best-studied instance, the debate on the proper treatment of this phenomenon is known as the past tense debate (see Pinker and Ullman 2002). More recent models (along with the increase in available computational power) adapted data-orientation, first in the shape of prototypes, and later as full-fledged exemplar models. These model grammar as the collective episodic memory of a speaker’s experience with language. New utterances are classified or generated in proportional analogy (de Saussure 1916) to previous ones: if two pairs of linguistic items instantiate the same grammatical relation, the proportion of the first pair is analogous to that of the second. Analogy crucially relies on a notion of similarity. Similar linguistic items are more likely to be classified alike. Learning paradigmatic relations via proportional analogy goes beyond learning as classification (Pirrelli and Yvon 1999, Albright 2008). It extends to surface-level outputs. Kernels are a mathematical formulation of similarity. Essentially, they are an inner product in a feature space, where each dimension is an observable feature of the data items. Kernel methods are closely related to exemplar models (Ashby and Alfonso-Reese 1995, Jäkel et al. 2008), and they are successful in cognitive modeling, mostly outside linguistics. In this thesis I devise methods to generate linguistic models using Kernel Principal Component Analysis (KPCA; Schölkopf and Smola 2002). I cover models of classification (predicting the gender of German nouns) and of production (predicting the plural form). Models of production require a model’s output, which is a representation in the continuous feature space, to be mapped onto a discrete valid data item. I devise a general strategy of the required pre-imaging for complex data, which incrementally approximates the desired item, and instantiate this strategy for the data type of strings. I compare KPCA to a variant including weights on data items, Weighted KPCA (Wang et al. 2005). I prove WKPCA’s equivalence to a KPCA performed on a data set where weights are simulated via multiple identical entries of data items. In the experiments, WKPCA performs inferior to KPCA, probably due to over-generalization of the most frequent patterns. Further, I investigate the linguistic interpretation of the principal components. These form the orthogonal basis of the feature space as calculated by KPCA. It turns out that — as is often the case with data-orientation — they do not represent abstract, scientific, human-readable descriptions of linguistic problems. I also discuss rotations of the principal components as alternative bases. I devise a method of rotation towards abstract features which retains all variation within these features in a low-dimensional model. By this I obtain a two-dimensional model of German gender, in which the three genders form clusters. While this is a practical model, it is still not an interpretable one. Most models presented here are morphological in nature. In the syntactic domain, I extend the implementation of grammaticality as planar languages (Clark et al. 2006) from string languages to trees, using a tree kernel (Collins and Duffy 2001a,b).

Diese Dissertation behandelt verschiedene Möglichkeiten, mittels einer bestimmten mathematischen Charakterisierung von Ähnlichkeit, Kernel-Funktionen, und darauf aufbauenden maschinellen Lernverfahren über datenorientierte Sprachmodelle zu abstrahieren. Die Klassifizierung von Datenpunkten, ist eine der häufigsten Anwendungen maschinellen Lernens, und auch in der Linguistik findet sie als Erkennung grammatischer Eigenschaften Anwendung. Konzeptuell anspruchsvoller ist es, die Beziehung zwischen sprachlichen Ausdrücken zu modellieren. So realisieren zum Beispiel Wörter innerhalb eines Flexionsparadigmas die verschiedenen Merkmale, entlang derer flektiert wird. Ausnahmen und gerade auch systematische Ausnahmen stellen sowohl in der Merkmalserkennung als auch in der Flexion die traditionellen regelbasierten Erklärungsansätze in Frage. Nicht nur innerhalb der Ausnahmen, sondern auch für die als einheitlich erachteten regelmäßigen Fälle, sind sogenannte islands of reliability (Albright 2002), kleine Gruppen ähnlicher Ausdrücke mit daraus folgenden ähnlichen Eigenschaften, beschrieben. Wegen der in der Literatur oft studierten Vergangenheitsform englischer Verben trägt die Debatte um die angemessene Behandlung dieses Phänomens den Namen past tense debate (siehe Pinker and Ullman 2002). Spätere Modelle orientierten sich — angesichts steigender Rechenkraft — mehr und mehr an Daten, zuerst in Gestalt von Prototypen, und zuletzt als ausgewachsene Exemplarmodelle. Als Grammatik gilt darin das gesammelte episodische Gedächtnis des Sprechers für Sprache. Neue Äußerungen werden in proportioneller Analogie (de Saussure 1916) zu den alten verstanden beziehungsweise gebildet: Wenn zwei Paare sprachlicher Ausdrücke den selben grammatischen Bezug untereinander haben, dann ist auch ihr Bezug hinsichtlich ihrer Form ähnlich. Analogie basiert auf einem Konzept der Ähnlichkeit. Ähnliche sprachliche Ausdrücke verhalten sich ähnlich, gehören eher den selben Klassen an und flektieren ähnlich. Paradigmatische Beziehungen zwischen Wörtern zu lernen geht über simple Klassifizierung hinaus (Pirrelli and Yvon 1999, Albright 2008), weil hier nicht abstrakte Merkmale gesucht sind, sondern ganze Wortformen. Mit Kernel-Funktionen lässt sich Ähnlichkeit formalisieren. Im Wesentlichen handelt es sich bei ihnen um ein inneres Produkt in einem aus den beobachtbaren Merkmalen sprachlicher Ausdrücke aufgespannten Raum. Kernelmethoden stehen in einem engen Verhältnis zu Exemplarmodellen (Ashby and Alfonso-Reese 1995, Jäkel et al. 2008) und werden — meist außerhalb der Linguistik — erfolgreich zur kognitiven Modellierung eingesetzt. Deswegen entwickele ich in dieser Dissertation Methoden um mittels kernelisierter Hauptkomponentenanalyse (Kernel Principal Component Analysis, KPCA; Schölkopf and Smola 2002) Modelle von Sprache zu erstellen. Dabei decke ich sowohl Klassifizierungs- (am Beispiel des Genus im Deutschen) als auch Produktionsmodelle (am Beispiel des Plurals) ab. In Produktionsmodellen muss das jeweilige Ergebnis, ein Punkt im stetigen Merkmalsraum, zusätzlich auf einen diskreten, gültigen Ausdruck abgebildet werden. Zu diesem Zweck gebe ich eine allgemeine Pre-Imaging-Strategie für komplexe Daten an, die den Zielausdruck schrittweise annähert. Ich exemplifiziere sie für Zeichenketten (strings, also Wörter). Ich vergleiche die KPCA mit ihrer gewichteten Variante, Weighted KPCA (Wang et al. 2005). Ich zeige, dass die WKPCA zu einer KPCA über einen erweiterten Datensatz, in dem jeder Ausdruck gemäß seiner Häufigkeit mehrfach vorkommt, äquivalent ist. In den Anwendungen unterliegt die WKPCA jedoch der KPCA, was daran liegen mag, dass sie ohnehin schon häufige Muster übergeneralisiert. Ferner untersuche ich die linguistische Interpretation der Hauptkomponenten. Diese sind die per KPCA berechnete, orthogonale Basis des Merkmalsraumes. Wie so oft in datenorientierten Ansätzen stellt sich heraus, dass sie keine abstrakt-wissenschaftlichen, menschenlesbaren Beschreibungen des jeweiligen linguistischen Problems sind. Ich erwäge Drehungen der Basis, um andere Interpretationen zu ermöglichen, und stelle eine Rotation auf die grammatischen Merkmale vor, die sämtliche Variation bezüglich dieser Merkmale in einem niedrigdimensionalen Modell darstellt. Dadurch erhalte ich ein beispielsweise zwei-dimensionales Modell, in welchem die drei Genera des Deutschen Cluster bilden. Obschon nützlich, ist diese Ebene immer noch nicht linguistisch interpretierbar. Die meisten hier vorgestellten Modelle sind morphologischer Natur. Hinsichtlich der Syntax erweitere ich unter Verwendung einer Kernelfunktion über Bäume (Collins and Duffy 2001a,b) den Begriff der Grammatikalität im Sinne der planaren Sprachen (Clark et al. 2006) von Zeichenketten auf Baumdarstellung.