Analysis: Clustering words by tags in the SwDA

1. Overview
2. Word vectors
   1. Count dictionary
   2. Word–tag matrix
   3. Length normalization
3. K-means clustering
   1. Background on k-means clustering
   2. Experiment runs
      1. Interjections
      2. Pronouns
      3. Prepositions
   3. Discussion
4. Exercises

Overview

This section is less assessment oriented than the previous ones have been. I want to instead map out a general investigative strategy that is only feasible for data-intensive, computational approaches like the ones we've been exploring.

The guiding empirical idea is that the meanings for discourse particles, very broadly construed, are best given as use conditions, rather than as denotations that depend on a truth-functional foundation. That is, whereas it might be fruitful to analyze a term like cat as the (world-relative set of cats), this idea stumbles with things like interjection-well, which makes no claims, but rather functions to manage the information flow in complex ways.

The technique I propose is an example of vector-space semantics. It makes crucial use of the dialog act tags in the SwDA. It doesn't get us down to specific meanings, but it moves us in that direction, by exposing abstract usage patterns that are reflective of those usage conditions.

Associated reading:

• Turney and Patel 2010

Code and data:

• swda.zip: our distribution of the data
• swda.py: Python classes for working with swda
• swda_wordtag_clusterer.py: the clustering interface
• kmeans-illustration.py: a toy k-means clusterer for producing figure KMEANS

Word vectors

The main class in swda_wordtag_clusterer.py is SwdaWordTagClusterer, which makes use of the NLTK clustering module. Here is the instance that I make use of for most of this section:

1. corpus = CorpusReader('swda') # The SwDA corpus.
2. cats = ['uh'] # A set of POS tags
3. clust = SwdaWordTagClusterer(cats, corpus, count_threshold=20, # Remove words with fewer than this many tokens. num_means=5, # Number of word clusters to build. repeats=10, # Number of times to repeat the clustering with random initial means. distance_measure=nltk.cluster.util.euclidean_distance) # Distance measure.

Calling clust.kmeans() then does the following:

1. Builds a word--tag matrix for all the words that appear at least 20 times with one of the POS tags in cats.
2. Applies k-means clustering to that matrix, forming 5 clusters, seeking to minimize the mean euclidean distance of points in those clusters.

The clutering is repeated 10 times because the clustering method is not guaranteed to find a globally optimal clustering. The final output is the most frequently seen set of clusters.

The next few subsections explain this pocedure in more detail.

Count dictionary

The kmeans() method starts by building a count dictionary using the method build_count_dictionary, which constructs a mapping word → DAMSL-tag → count capturing the number of times that (word, pos) appears in an utterance marked DAMSL-tag, where pos is in cats. This count dictionary is an intermediate step towards the matix we need.

Word–tag matrix

The method build_matrix() maps the count dictionary to an n x m matrix, where n is the size of the vocabulary and m is the number of DAMSL tags. The cells in this matrix are filled with the final count values from the count dictionary.

Intuitively, the rows represent words and the columns represent tags. Table MATRIX gives the upper left corner of this matrix.

Figure COUNTS depicts the distances between these count vectors from the initial vector absolutely (which I chose more or less arbitrarily for the sake of illustration).

Figure COUNTS

Count distances from absolutely.

The distance measure is euclidean distance. Here is the Python code from nltk.cluster.util.euclidean_distance():

1. def euclidean_distance(u, v):
2. """
3. Returns the euclidean distance between vectors u and v. This is equivalent
4. to the length of the vector (u - v).
5. """
6. diff = u - v
7. return math.sqrt(numpy.dot(diff, diff))

It's of course very hard to visualize this in 44 dimensions (the length of our vectors), but it's easy in two and even three dimensions:

1. euclidean_distance(numpy.array([0,0]), numpy.array([0,1]))
2. 1.0
3. euclidean_distance(numpy.array([0,0]), numpy.array([1,1]))
4. 1.4142135623730951
5. euclidean_distance(numpy.array([0,0]), numpy.array([1,0]))
6. 1.0
7. euclidean_distance(numpy.array([0,0]), numpy.array([-1,-1]))
8. 1.4142135623730951
9. euclidean_distance(numpy.array([0,0,0]), numpy.array([0,1,0]))
10. 1.0
11. euclidean_distance(numpy.array([0,0,0]), numpy.array([0,1,1]))
12. 1.4142135623730951

Length normalization

The distance between raw count vectors is very heavily dependent upon the sum of the counts in those vectors. For example:

1. euclidean_distance(numpy.array([1,1]), numpy.array([4,4]))
2. 4.2426406871192848
3. euclidean_distance(numpy.array([1,1]), numpy.array([1,2]))
4. 1.0

The first pair of vectors are similar in the sense that their totals are distributed in the same way. The second pair is very different in this regard.

This is not what we want from semantic word clusters; overall frequency is not a good predictor of meaning or usage conditions. The relevant notion of similarity for us is distribution with respect to the tags.

Thus, when initializing SwdaWordTagClusterer cluster instances, we call the method length_normalize_matrix, which rescales each row of the matrix by dividing each of its elements by its length (magnitude).

1. def length_normalization(vec):
2. return vec / numpy.sqrt(numpy.dot(vec, vec))

(This step can also be done with normalise=False as one of the arguments to NLTK's cluster.KMeansClusterer, but I decided to do this to the matrix beforehand, to make it easier to study its effects.)

1. euclidean_distance(length_normalization(numpy.array([1,1])), length_normalization(numpy.array([4,4])))
2. 0.0
3. euclidean_distance(length_normalization(numpy.array([1,1])), length_normalization(numpy.array([1,2])))
4. 0.32036448601393441

Table NORMMATRIX is the length-normalized version of table MATRIX.

Figure NORMED depicts the normed distances from absolutely (cf. figure COUNTS).

Figure NORMED

Normed distances from absolutely.

The impact of normalization is dramatic.

First, two words that should be close:

1. yeah (43008 tokens) vs. yep (318 tokens)
   1. Count: 25989.16 (25 words apart)
   2. Normed: 1.117172 (5 words apart; between them: right, sure, huh-uh)

And two words that ought not to be close:

1. jeez (120 tokens) vs. good-bye (80 tokens)
   1. Count: 50.65570 (13 words apart)
   2. Normed: 1.4293055 (40 words apart)

exercise WORDCMP

K-means clustering

Background on k-means clustering

This section gives a brief overview of how k-means clustering works. I don't devote too much time to this because I actually think that k-means is not the right approach to this kind of modeling — I am using it as a first step because it is conceptually and computationally simple introduction to using clustering for pragmatic analysis.

The goal of k-means clustering is to group items, qua vectors, into k clusters, where k is a prespecified integer value. The algorithm works by randomly picking k mean values, assigning every item to the closes of those means, and then recalcualting the means for those new clusters. This process repeats iteratively until the mean values stop changing.

The Wikipedia page for the algorithm tells the story both in math and in pictures. See also Manning and Schütze 1999: §14. Figure KMEANS shows Wikipedia's examples for a particular run with randomly chosen initial values (which is what NLTK does; the Wikipedia example begins with pre-selected ones).

Figure KMEANS

The Wikipedia k-means example with numerical values and randomly chosen initial means. The mean values are given are colored squares, and the data points are dots, with color representing which cluster they belong to. The initial means are very poor, but the algorithm recovers. In the last two panels, the change in means does not affect the clustering — the algorithm has converged.

The SwdaWordTagClusterer method kmeans() calls the NLTK clustering algorithm using the following code:

1. clusterer = cluster.KMeansClusterer(self.num_means, self.distance_measure, repeats=self.repeats, normalise=False)
2. cluster_vector = clusterer.cluster(self.mat, assign_clusters=True, trace=False)

This instructs the clusterer to use the user's value for the number of means, distance measure, and number of repeats. normalise=False because we normalize the matrix ourselves. self.mat is our matrix. assign_clusters=True does the actual clustering. trace=False supresses the printing of a little bit of progress reporting.

For more on how to work with the NLTK interface, check out their demo, which you can run with from nltk.cluster import kmeans; kmeans.demo(), and also the class documentation.

exercise OTHERS, exercise LSA

Experiment runs

Interjections

[uh] with a threshold of 20, euclidean distance:

0: [bye, bye-bye, good-bye, hello, hi, thanks]
1: [dear, golly, good, goodness, gosh, great, my, ooh, ugh, wow]
2: [absolutely, definitely, exactly, huh, huh-uh, no, oh, okay, really, right, sure, true, uh-huh, ye-, yeah, yep, yes]
3: [actually, anyway, hey, like, now, say, see, so, uh, um, well]
4: [boy, gee, god, jeez, man, shoot]

Assessment: Remarkably good; the dialog act tags capture something important about how these items are used.

Pronouns

['prp', 'prp$', 'wp', 'wp$'], with a threshold of 20, euclidean distance:

0: [her, hers, herself, mine, my, myself, ours, she]
1: [he, him, himself, his, i, me, our, theirs, w-, we]
2: [it, ourselves, them, they, us, what, whatever, who, whoever, whose]
3: [i-, its, itself, one, th-, their, themselves, y-, you, your, yourself]
4: ['s, wh, wha, yo-, yours]

Assessment: Pretty good; pronouns are a mix of dialog-act relevant things (who, whatever) and things that are largely independent of dialog act.

Prepositions

[in] with a threshold of 20, euclidean distance:

0: [across, around, at, before, behind, course, down, during, except, inside, outside, prior, since, through, till, underneath, up, while]
1: [about, above, after, along, although, because, between, by, cause, due, for, from, in, into, like, of, off, on, out, over, past, per, so, the, to, under, until, with, within]
2: [instead, onto, throughout]
3: [among, once, rather, such, than, towards, unless, upon, versus, whereas]
4: [against, as, besides, beyond, but, i-, if, that, though, toward, whether, without]

Assessment: Very bad; the dialog act tags seem not to have any interesting relationship to preposition usage. I think this is what we expect given that prepositions are not typically discourse oriented in a sense reflected in the tags.

Discussion

The results of k-means clustering seem promising overall, though I think the approach is not ideal. Some criticisms:

1. It is difficult to know how many clusters to use, but whatever number we choose has a dramatic impact on performance.
2. K-means is a hard clustering algorithm in the sense that each word belongs to one and only one cluster. It would be better to allow words to belong to multiple clusters, or no cluster at all (for true outliers/isolates).
3. We lack an independent measure of success to use for assessment, so we are left to stare at the clusters and try to make sense of them (which can lead us to perceive patterns that are not really there).

exercise ALGORITHMS

Exercises