Friday, March 30, 2012

NTA7:Dimensional Sparseness Or What Tokens To Use?

NTA7: Dimensional Sparseness Or What Tokens To Use?

Guide to all Numerical Text Analysis posts

 Word histogram and Zipf plot of corpus for identifying stop words

After
  • lowercasing,
  • depunctuating,
  • removing single atom words,
  • removing single occurrence tokens,
  • stemming and removing a few stop words (whether the 125 I have chosen or the ~ 450 in standard lists,
we are left with about 14000 tokens from a bit less than 100 documents.

Here is the Zipf plot:


Before going on to the Cosine Similarity business, let's think about Word-vector space. Each token represents a dimension, the frequency of occurrence is the coordinate. Each document represents a point in this space. So what we have is a 14,000 dimensional space for a 100 points. That's ridiculous! But let's consider we have a million documents, that is still only 70 points per dimension!

Now of course this is going to vary from case to case, e.g. the categorization problem I worked on had 25,000 points in 50,000 dimensions. Hardly a situation where standard clustering algorithms – most of which are designed for denser graphs (at least dimensionally speaking) can be expected to apply. My solution to this is on SlideShare, and I'll blob on it at length later.

My point, as was my point for selecting stop words, is that some [statistical or numerical] and purpose-based criteria have to be used to decide which set of tokens to use. If you look at the Zipf plot above, in my view there are clearly three families of tokens:
  • the high ranking ones that approximate a Zipf line with a coefficient marginally less than 1

  • the mid ranking tokens at the knee of the plot which fall off the Zipf line

  • the low ranking tokens whose power law deviates very strongly from 1


My choices for the cutoffs are somewhat arbitrary, but unimportant for now. Summarizing,


What do these mean? Consider the extremely rare ones that occur only once in the corpus, and hence in only one document. So they are extremely powerful for distinguishing one document from another and a reasonably small set of these plus a few that occur a few times (There may be a few documents which contain no singly occurring tokens.) will be sufficient to label every document uniquely. However, precisely because of their rarity, we can't use them for finding any similarities between texts. So these low ranking tokens lead to a very fine-graining of the set of documents. Rejecting these will have the advantage of reducing the dimensionality of word space by an order of magnitude.

What about the high-ranking ones? They suffer from the converse problem, they occur so often in so many texts that they are likely to not be able to distinguish well between texts at all, which is sort of the motivation for throwing out the stop words in the first place. (Though my suspicion is that stop words are, or should be, chosen based on the smallness of the standard deviation of their relative frequencies.) So short of calculating these frequency standard deviations for the tokens, which I hope to get to soon, we should reject these stochastic tokens, the ones that closely follow Zipf's law (or Mandelbrot's modification). Rejecting these will not reduce the dimensionality of word-vector space by much, but it will reduce the radial distance of the document-points from the origin, the de facto center for the Cosine Similarity.

So we can use only 1500 mid-ranking tokens (that is “only” 15 dimensions per point, which is better than 144 dimensions per point) for the next steps.

Last point: before calculating Cosine Similarities, a standard step is to scale all the token - frequencies by the log of the document frequency for the token. This is a flat metric on wordspace. This will have the effect of bringing down the weight at the high-ranking end, and since log(f) increases slower than f, not scaling down as much the low ranking end. So the overall weights of the tokens may show precisely the bump in the mid-range that we want. So another point for comparison.

So many choices, so little time.

Thursday, March 29, 2012

NTA6: Constructing Histograms For A Corpus

Constructing Histograms For A Corpus : Numerical Text Analysis 6

Guide to all Numerical Text Analysis Posts

For the corpus, or the set of documents I am going to analyse, I've chosen the top 100 books over the last 30 days (as of 3/27/2012) from Project Gutenberg. (Incidentally, Vatsayana's Kamasutra is a perennial number 3, and this accords with Amartya Sen's footnote (pg. 25, The Contemplative Indian): In fairness to Western expertise on India, it must be conceded that there has never been any lack of Occidental interest in what may be called the 'carnal sciences', led by the irrepressible Kamasutra and Anangaranga.) I looked at the source code for the page, copied it, and did regular expression searches for the serial numbers of the books, then wrote Python code to suck them from the website, keeping my fingers crossed that they wouldn't think I = Robot and block my IP address. Some of the .txt files turned out to be empty. I chopped off the beginning (Project Gutenberg info.) and the last bit ( license info.) for each document.

As a reminder, the steps for processing text are:
  1. Lowercase, depunctuate and stem the words in the text of each document.
  2. Construct a word histogram for each document, for all the tokens. For example, for eBook3600:
    Zipf plot for eBook3600
  3. Construct the histogram for the corpus: for each token, add the occurrence frequencies in all the documents in the corpus.
  4. Identify the rare tokens – those that occur a total of only one time in the entire corpus. Why remove any low-frequency tokens at all? There are a large number of non standard-English letters (possibly some of the documents are in languages other than English or there may be a few words from other languages or simple mitsakes) and non-ASCII and non-UTF-8 punctuation marks (for example Sanskrit diacritical notation from the book ranked number 3 above) that my algorithm doesn't pick up.
    I thought that restricting the allowed atoms to lowercase unaccented Latin letters would rule out too many accented letters, and played with removing small frequency words. It turns out that even for a 100 documents, ruling out the unipresent tokens is enough since the remaining bipresent tokens seem quite reasonable.
  5. Identify the small tokens, that is, the single character ones except “a” and “i”, and put both the small and the rare tokens in a list of raw words to be removed. The few small tokens can be removed from all the documents in the corpus, but since the rarity of a token can change as documents are added to the corpus the rare tokens should be left in place, even though the number of rare tokens will increase almost linearly with the number of words in the corpus whereas the number of higher frequency words will increase much slower.
    From which you can see

    • The number of unipresent tokens is about half of all tokens, but represent marginally few words.
    • There are a surprisingly large number (132) of unidentified atoms, which on average occur multiple times.
    • If you think that English is a gender-neutral language, think again.
  1. Zipf plot of the entire corpus,
    which should be used to determine the minimum rank to exclude “stop” words (deviations from flatness at the high frequency end. Let's take a look at the high frequency end in more detail:
    from which I can see choosing a stop rank anywhere between 50 and a 150, but I don't see at all why the stop rank should be between 450 and 500 words, which is what standard stop-word lists consist of. Ignorance => opportunity to learn. However, for now I am going to go with the list of the top-ranked 103 as the stopword list, which reverentially saves "god" "himself", which come in at #s124th and 125th.
  2. Add the set of stop words to the set of words to be removed. The complement of this subset in the set of all tokens in the corpus is the set of tokens to be used for the statistical calculations. The truncations of the histograms to this “use-set” of words are what we will use for studying Cosine Similarity, its alternatives, and what should really be done with the histograms.

So in the next post, I'll lay out my arguments comparing the ubiquitous Cosine Similarity to some simple trignometric alternatives, with some simple illustrative examples. The post after that will consider document similarity within the above corpus using both Cosine and my proposed alternative.

Next what I'll propose is to go beyond this approach to similarity, to really situate ourselves well in word-vector space and see what really good measures we can construct there, and of course, following all that theory, apply those ideas to the documents in the corpus. Yum-yum!


Monday, March 26, 2012

NTA5: WordPlay

Numerical Text Analysis 5

Guide to All Text Analysis Posts

Prev: Constructing Word Histograms

This is not serious stuff, so indulge me here. I am just playing with a cute idea which probably has zipf practical applications.
Read this after reading about the construction of word histogram space.

Since I'll be analysing text, and writing text to do so, let me distinguish text to be analysed by putting it on a gray background. For example, the result of the action of the lower-casing operator on some text can be shown as
low:
ThiS is tHe TeXt fOR makiNG LowER case
=
this is the text for making lower case

Before proceeding I just want to point out that it is not really the text I am interested in as in the histogram of the text. So
LOWER case
and
case LOWER
are the same as vectors or word-histograms, as are:
text text text
=
3 *
text

Eigen Wha?: Just to refresh our memories, a linear operator on a vector space acts on any vector and gives you back another vector in the space. If the result of the action of the operator on a specific vector is to return that same vector multiplied by a scalar, that vector is called an eigenvector of the operator and the corresponding scalar is an eigenvalue of the operator. The determinant of the operator is the product of its eigenvalues. The eigenvalues are solutions to det(oper. - lambda* Identity Op.) = 0.

An eigenvector of the low operator with eigenvalue 1 is
upper
, since
low:
upper
= 1*
upper

Let's just look at the low operator in a bit more detail. If I restrict my word space to only 'a', both lower and upper case, then it is two dimensional. Let me represent text in this space by the ordered pair of the number of occourences of 'a' and 'A', (x, y). So the text
a A A a a
is represented by (3,2). Now the action of the lowering operator is low(x,y) = (x+y,0), and the eigenvector with eigenvalue 1 is (1,0). However, if you calculate the determinant of low, it turns out to be 0!, so we know that it has an eigenvector with 0 eigenvalue. In the above representation, this is (1,-1). But what does '-1' occurences mean? We know that a word can't occur -1 times in a text!

Or, do we?
My word but it can

So what are the rules? Well there is only one:
word
+
word
=
word word
=


So the 0-eigenvalue eigenvector of low is the following text!
a A

When we read text like this, we are only sensitive to the magnitude. 

What we've accomplished is that we have extended word histogram space (linear space but only in the positive 2n-ant) to be a genuine, full-fledged, authentic VECTOR space!

This raises the possibility –which, since I am a self-acknowledged ignoramus in this field, I am sure has already been explored– of using vector space and operator analysis to look at text. However, I doubt that there is anything new there beyond what is already known from standard statistical text analysis.

In any case, I hope this was as good for you as it was for me. 

Word Histograms for the Corpus 

Next: Cosine Theta, Murdabad!

NTA3: StopAndRareWordsToBeOrNotToBeZipf

Exactly, that is the question!

Numerical Text Analysis 3

Guide to All Text Analysis Posts

Prev:  Text Analysis with Illustrative Example

Let's stop and think about stop words. What is the reason to remove them before doing numerical text analysis? Surely the reason is not that they account for 50% of all the words in a text (they do) and that hence removing them will result in data savings. These are words like 'the', 'and', 'to' and 'of' that occur with very high frequency in the corpus of all texts and whose relative frequencies across texts are approximately constant. As such stop words do not serve to distinguish one text from another. (I was about to say that they do not have any semantic content, but I'll carefully ... step ... around ... that ... mine.) So we can now choose to drop some number of the most frequent words. Note that this decision should absolutely be corpus-based! and not based on some canonical list of stop words that some grad. student came up with. For example, the most frequent words in the corpus(Wm. Shakespeare's works), corpus(Charles A. Dodgson's works), corpus(LinkedIn profiles) or corpus(Match.com profiles) will likely be different.



So if there isn't a canonical set (nor even number) of stop words, how should one choose the cut-off? For this let's consider another, more numerical reason to drop stop words.
In Numerical Text Analysis, there is a law that captures the general distribution of word frequencies in texts. For any text or corpus, rank all the word tokens by decreasing order of frequency, so 'the' is ranked 1 (relative frequency is 0.05) and something like 'zitterbewegung' –with relative frequency of 10-9 even within physics texts– is ranked 250,000. Zipf's Law essentially states that the product of the rank and the frequency is a constant function of rank. Mandelbrot –who got his start in science doing numerical text analysis until he tried to analyse Jorge Luis Borges' works and switched to chaos theory– made a modification to this law that the exponent for frequency as a function of rank is less than -1, and took into account deviations near the ends. In any case, we then expect a plot of log10(frequency * Rank) vs log10(Rank) to approximate a straight line. So let's look at a sample Zipf plot for Alice:



Alice in Wonderland original text



Note that the way I am plotting the data is slightly different from Zipf's. Typically (meaning every instance I've seen so far) log(frequency) is plotted vs. log(rank), and one looks for a slope of -1. What that implies is that Frequency * Rank = constant, hence if I plot log(Frequency * Rank), data that satisfies Zipf's law should be flatlined, and deviations from Zipf's law will be zoomed up.

"What's with the discontinuities?". The text has only 50K words and, after stemming, 2,000 tokens. There are a very large number of words (~700) that occur only once in the text. As we go up this (unsorted) subset, the frequency remains the same but the numerical rank keeps reducing, until we get to the top end and enter the subset of words which occur twice: at this point the rank only changes by '1', but the frequency doubles, adding the 0.3 on the log10 scale. Note that this discontinuity is almost half the y-axis range! For a large corpus the number of genuine words that occur only a few times will reduce and their rank will be pushed to larger numbers on a wider y-axis range, so even though the first discontinuity will still be log10(2), the plot will appear smoother.

We clearly see the deviations from the expected power law behaviour at low ranks, i.e. for frequently occouring words. Roughly speaking from the 100th token onwards we see that a fit is an almost 0-slope line, whereas higher ranked tokens deviate from that behaviour. If we wanted to be aggressive about stemming, we would drop words ranked lower than 359. If we wanted to be less aggressive, we would perhaps choose a cut off rank of 99. See the application of this idea to a corpus.

For the full corpus of all texts, we should also expect deviations from linearity at the low frequency end of the plot, and this should be used to find a cut off for the rare words.

Conclusion for stop and rare words

For the corpus of texts under consideration:
  1. Do a Cummings and stem the words in the texts
  2. count the frequencies of occurrence in the corpus of all the word tokens, and rank the word tokens by order of frequency.
  3. Plot log(frequency * rank) vs. log(rank) of the word tokens – the Zipf Plot for the corpus.
  4. Look for deviations from the expected straight line behaviour and choose a cut-off rank at both ends.
  5. The set of stop words are the word tokens with higher rank (more frequent) than the corrsponding cut-off and the rare words are those with lower rank (less frequent).
  6. Remove these sets of stop and rare words from all texts under consideration.
  7. The resulting truncated histograms are the word-histograms for the texts that one should then proceed to use for further numerical text analysis.

    Next: Word Histograms