BWT for NLP (2)

I show how the Burrows-Wheeler Transform can be used to compute the similarity between two strings. We submitted results from this method (along with results from the Context-Chain metric developed by my colleagues Frank Schilder and Ravi Kondadadi) for the Automatically Evaluating the Summaries of Peers (AESOP) task of the TAC 2009 conference.

The task was to produce an automatic metric to evaluate machine generated summaries (i.e., system summaries) against human generated summaries for the TAC '09 Update Summarization Task. Clearly the automatic metric is just some function that produces a similarity score between the system summary and the human generated (the so-called model) summary.

The  proposed metrics were evaluated by comparing their rankings of the system summaries from different peers to that of the ranking produced by human judges.
Similarity Metric

We use an estimate of the conditional "compressibility" of the model summary given the system summary as the similarity metric. The conditional compressibility is defined as the increase in the compressibility of the model summary when the system summary has been observed.

In order to judge the similarity of the system summary $latex S$, to the model summary $latex M$, we propose to use the difference in compressibility of $latex M$ when $latex S$ is not seen to when $latex S$ is given. This metric basically

captures the reduction in the uncertainty in $latex M$ when $latex S$ is known.

We define the compressibility $latex c(M)$ of any string $latex M$ by

$latex c(M) = \frac{H(M)}{|M|}$

and the conditional compressibility of string $latex M$ over an alphabet $latex \mathcal{A}$ given another string $latex S$ over the same alphabet as

$latex c(M|S) = \frac{H(S+M) - H(S)}{|M|}$

where $latex S+M$ is the concatenation of the strings $latex S$ and $latex M$, $latex H(S)$ is the entropy of string $latex S$, and $latex |M|$ is the length of the string $latex M$.
The fractional increase in compressibility of $latex M$ given $latex S$ can then measured by

$latex r(M|S) = \frac{c(M) - c(M|S)}{c(M)}$.

We use $latex r(M|S)$ as the similarity metric to measure the similarity of a system summary $latex S$ to the model summary $latex M$.

Our metric is similar to the one proposed by Li and Vitanyi and is theoretically well-justified from the perspective of algorithmic information theory. One peculiarity is that our similarity is asymmetric.

The only thing that is needed to implement the above similarity metric is an estimate of the entropy $latex H(S)$ for a string $latex S$. We use the BWT for this estimate.

BWT-based String Entropy Estimate

We use the Move-To-Front (MTF) entropy of the Burrows-Wheeler transform of a given string $latex S$ as an estimate for its entropy $H(S)$.


The MTF encoding of a string is performed by traversing the string and assigning to each symbol the position of that symbol in the alphabet and then moving the symbol to the front of the alphabet. Therefore a sequence with a lot of runs will  have a lot of zeros in its MTF encoding.

In this paper the MTF coding is used to define the MTF entropy (which the authors also call local entropy) of a string $latex R$ as

$latex \mbox{MTFE}(R) = \sum_i \mbox{log}(\mbox{MTF}(R)_i + 1)$

where $latex \mbox{MTF}(R)_i$ is the $latex i^{th}$ symbol of the MTF coding of the string $latex R$.

Now we define $latex H(S)$, the entropy of string $latex S$ as

$latex H(S) = \mbox{MTFE}(\mbox{BWT}(S))$

where $latex \mbox{BWT}(S)$ is the BWT of string $latex S$.

Since the Burrows-Wheeler transform involves just the construction of a suffix array, the computation of our compression based evaluation metric is linear in time and space in the length of the model and system summary strings.

Some Technical Details
For our implementation, we considered each word in a string as a separate symbol. Our alphabet of symbols therefore contained all the words in the two strings being compared. The words were normalized by lower casing and removing punctuation. Because BWT needs an ordered alphabet, we used the lexicographic order on the words in the alphabet.

Results
table1

The results on the TAC-AESOP task (above) show that the BWT based metric (FraCC in the table) is reasonable for summarization evaluation, especially because there are not very many knobs to tune. I obtained these results from Frank (who will present them at TAC next week). The "best metric" is the AESOP submission that seemed to have high scores across several measures.

Comments

  1. EmanueleDecember 11, 2009 at 11:26 AM

    There is a tool, "complearn", to compute this kind of distances and then do clustering: http://www.complearn.org/

    This tool airises from the Ph.D. activity of R.Cilibrasi that worked with Vitanyi: http://cilibrar.com/

    E.

    ReplyDelete
  2. mlstatDecember 12, 2009 at 2:54 AM

    Em,

    Thanks. I was aware of Cilibrasi and Vitanyi's work. Marcus Hutter is another guy who does similar things. Hopefully one day I'll get down to reading and understanding the theory behind this stuff better.

    ReplyDelete

Post a Comment

Popular posts from this blog

Incremental complexity support vector machine

Image
One of the problems with using complex kernels with support vector machines is that they tend to produce classification boundaries that are odd, like the ones below. (I generated them using a java SVM applet from here , whose reliability I cannot swear to, but have no reason to doubt.) Both SVM boundaries are with Gaussian RBF kernels: the first with $latex \sigma = 1$ and the second with $latex \sigma = 10$ on two different data sets. Note the segments of the boundary to the east of the blue examples in the bottom figure, and those to the south and to the north-east of the blue examples in the top figure. They seem to violate intuition. The reason for these anomalous boundaries is of course the large complexity of the function class induced by the RBF kernel with large $latex \sigma$, which gives the classifier a propensity to make subtle distinctions even in regions of  somewhat low example density. A possible solution: using complex kernels only where they are needed We propose to b
Read more

An effective kernelization of logistic regression

Image
I will present a sparse kernelization of logistic regression where the prototypes are not necessarily from the training data. Traditional sparse kernel logistic regression Consider an $latex M$ class logistic regression model given by $latex P(y|x)\propto\mbox{exp}(\beta_{y0} + \sum_{j}^{d}\beta_{yj}x_j)$ for $latex y =0,1,\ldots,M$ where $latex j$ indexes the $latex d$ features. Fitting the model to a data set $latex D = \{x_i, y_i\}_{i=1,\ldots,N}$ involves estimating the betas to maximize the likelihood of $latex D$. The above logistic regression model is quite simple (because the classifier is a linear function of the features of the example), and in some circumstances we might want a classifier that can produce a more complex decision boundary. One way to achieve this is by kernelization . We write $latex P(y|x) \propto \mbox{exp}(\beta_{y0} + \sum_{i=1}^N \beta_{yi} k(x,x_i))$ for $latex y=0,1,\ldots,M$. where $latex k(.,.)$ is a kernel function. In order to be able to use this c
Read more

Random Fourier Features for Kernel Density Estimation

Image
The NIPS paper Random Fourier Features for Large-scale Kernel Machines , by Rahimi and Recht presents a method for randomized feature mapping where dot products in the transformed feature space approximate (a certain class of) positive definite (p.d.) kernels in the original space. We know that for any p.d. kernel there exists a deterministic map that has the aforementioned property but it may be infinite dimensional. The paper presents results indicating that with the randomized map we  can get away with only a "small" number of features (at least for a classification setting). Before applying the method to density estimation let us review the relevant section of the paper briefly. Bochner's Theorem and Random Fourier Features Assume that we have data in $R^d$ and a continuous p.d. kernel $K(x,y)$ defined for every pair of points $x,y \in R^d$. Assume further that the kernel is shift-invariant, i.e., $K(x,y) = K(x-y) \triangleq K(\delta)$ and that the kernel is
Read more