Spectral Clustering for German Verbs

Spectral Clustering for German Verbs Chris Brew Department of Linguistics The Ohio State University Columbus, Ohio, USA cbrew@ling.osu.edu Sabine Schulte im Walde Institut f¨ur Maschinelle Sprachverarbeitung Universit¨at Stuttgart Stuttgart, Germany schulte@ims.uni-stuttgart.de Abstract We describe and evaluate the application of a spectral clustering technique (Ng et al., 2002) to the unsupervised clustering of German verbs. Our previous work has shown that standard clustering techniques succeed in inducing Levin- style semantic classes from verb subcategorisa- tion information. But clustering in the very high dimensional spaces that we use is fraught with technical and conceptual difficulties. Spec- tral clustering performs a dimensionality reduc- tion on the verb frame patterns, and provides a robustness and efficiency that standard cluster- ing methods do not display in direct use. The clustering results are evaluated according to the alignment (Christianini et al., 2002) between the Gram matrix defined by the cluster output and the corresponding matrix defined by a gold standard. 1 Introduction Standard multivariate clustering technology (such as k-Means) can be applied to the problem of inferring verb classes from information about the estimated prevalence of verb frame patterns (Schulte im Walde and Brew, 2002). But one of the problems with multivariate clustering is that it is something of a black art when applied to high-dimensional natural language data. The search space is very large, and the available techniques for searching this large space do not offer guarantees of global optimality. In response to this insight, the present work applies a spectral clustering technique (Ng et al., 2002) to the verb frame patterns. At the heart of this approach is a transformation of the original input into a set of orthogonal eigen- vectors. We work in the space defined by the first few eigenvectors, using standard clustering techniques in the reduced space. The spectral clustering technique has been shown to han- dle difficult clustering problems in image pro- cessing, offers principled methods for initializ- ing cluster centers, and (in the version that we use) has no random component. The clustering results are evaluated accord- ing to their alignment with a gold standard. Alignment is Pearson correlation between corre- sponding elements of the Gram matrices, which has been suggested as a measure of agreement between a clustering and a distance measure (Christianini et al., 2002). We are also able to use this measure to quantify the fit between a clustering result and the distance matrix that serves as input to clustering. The evidence is that the spectral technique is more effective than the methods that have previously been tried. 2 Verb valency description The data in question come from a subcate- gorization lexicon induced from a large Ger- man newspaper corpus (Schulte im Walde, 2002). The verb valency information is pro- vided in form of probability distributions over verb frames for each verb. There are two condi- tions: the first with 38 relatively coarse syntac- tic verb subcategorisation frames, the second a more delicate classification subdividing the verb frames of the first condition using prepositional phrase information …

Content truncated to 500 words