Boolean Algebra and Probability

Boolean Algebra is a field of algebra which formalizes the operations performed in logic, that is, on propositional statements (statements that are either true or false). This requires operations such as "AND", "OR" and "NOT" in order to compose complex statements from simpler ones, such as "it is raining" and "the road is wet" being composed into something like "NOT(it is raining) AND the road is wet". These operators work in the following way:

The statement "Math is awesome AND One Direction suck" is true because each of the simpler statements being joined together is true. If at least one of the simpler statements is false, then the whole thing becomes false.

The nice thing about this algebra is that it can be naturally extended from normal numeric algebra by representing a true statement with 1 and a false statement with 0. So then we can turn the statement "Math is awesome AND One Direction suck" into "1 AND 1" which is equal to "1". Why does it equal 1? Because for "X AND Y" to be true, both X and Y have be true individually. For example the statement "Math is awesome AND One Direction make great music" is false because one of those substatements is false. With the OR operator, as long as at least one of the substatements is true, the whole thing becomes true. For example "Math is awesome OR One Direction make great music" is true because one of the substatements is true. The NOT operator takes one substatement and inverts it, that is, if it was true then it becomes false and if it was false then it becomes true. For example "NOT Math is awesome" is false and "NOT One Direction make great music" is true. Numerically speaking, the following list summarizes these rules:

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

NOT 0 = 1
NOT 1 = 0

Can the be some normal arithmetic equations which will give us these outputs?

NOT is easy. What arithmetic equation returns 1 when given 0 and returns 0 when given 1?
NOT X = 1 - X
1 - 0 gives 1 and 1 - 1 gives 0.

AND is also easy. Just multiply the two operands together.
X AND Y = X × Y

OR is a little more tricky. This is because there is not single operation that gives the same outputs as OR. However we can easily derive an equation by using DeMorgan's laws which express an OR using AND and NOT only. The statement "in order to apply for the job you need a degree or five year's experience" can be expressed as "do not apply for the job if you do not have a degree and have less than five year's experience". Formally this is written as

X OR Y = NOT(NOT X AND NOT Y)

which numerically becomes

X OR Y = 1 - ((1 - X)(1 - Y))
X OR Y = 1 - (1 - Y - X + XY)
X OR Y = 1 - 1 + Y + X - XY
X OR Y = Y + X - XY

This makes sense. The OR operator is the addition of the two substatements minus one in case they are both true. This will return 1 whenever at least one of the two substatements is a 1.

But it also makes sense on a higher scale. If you think about it, these rules are the exact same rules for probability. Probability is a generalization of Boolean algebra. Rather than just considering truth and falsity like Boolean algebra does, probability considers values between those two cases, such that 1 is certainty, 0 is impossibility and all the numbers in between are a degree of uncertainty, where the closer the number is to 1 the more certain the statement is.

In fact AND and NOT are defined in exactly the same way in probability. But isn't OR defined simply as X + Y? That is in fact only the case when X and Y are events which are independent, that is, cannot happen together. In this case X AND Y is always zero and hence can be dropped from OR's equation. The equation we have derived is useful for dependent events as well such as asking for the probability of "two fair dice resulting in an even number and a number greater than 3". In this case you can't just add the probability of a die being even (3/6) and the probability of a die being greater than 3 (3/6) as otherwise you get 3/6 + 3/6 = 1 which means that you are certain that this will happen. The problem is that it is possible for the two substatements to be both true, that is, a die being both even and greater than 3 (namely 4 and 6). To fix this just subtract the probability of this special case occurring (2/6) which gives 3/6 + 3/6 - 2/6 = 2/3.

Let's illustrate it with a Venn diagram:


The Venn diagram above is showing two events as a red and blue circle. They have some overlap between them which is coloured purple. If the red circle represented the chance of a die being even and the blue circle represented the chance of a die being greater than 3, then the purple overlap would be the numbers 4 and 6. Now we want to find the probability of the red OR the blue circle occurring. If we just add their areas together we end up with the purple overlap being added twice since it is common to both circles, but we just want to add it once. So we subtract it once after adding both circles, which will result in having just one purple overlap. This is what is happening when you use the equation X + Y - XY.

Don't edit batch files during runtime

So it turns out that Windows batch files running under cmd (at least in Windows 7) are not preloaded into memory before runtime. Instead each line is loaded from disk right before it is executed. What this means is that if you edit the batch file during its runtime, you'll end up modifying the behaviour of the batch file being run.

Try this:

echo started
timeout 10
echo continued
echo ended
pause

This will make the batch file show "started", then wait for 10 seconds and finally show "continued" and "ended". To run it just paste the above code into Notepad and save it as "something.bat", then just double click the saved file.

Now open the batch file with Notepad again and run the file at the same time. As the batch file is waiting for 10 seconds, delete the "echo continued" line and save (before the 10 seconds are up). When the batch file continues, it will not show "continued" but will immediately jump to "ended".

Strange behaviour since this sort of thing does not happen with Python for example. I noticed this when I was trying to run multiple versions of the same batch file by just changing something in the file and running a new instance of it. Be careful of this.

Random Indexing for word space context vectors

Last time I had described what a term document matrix is and how to make it's use faster using Latent Semantic Analysis. Today I shall be explaining how to use Random Indexing as an alternative to LSA. You can read more about it here.

Unlike LSA, random indexing is a very easy and very fast online process. It is online in the sense that you don't need to first completely construct the co-occurrence matrix in order to use it, but can instead use it as you are counting co-occurrences. It also works just as well as LSA. Interested yet?

First of all, how do you construct a co-occurrence matrix? You start off with a matrix full of zeros with columns for words in context w1, w2, w3, and w4 and rows for neighbouring words n1, n2, n3, and n4:

   n1 n2 n3 n4
w1 0  0  0  0
w2 0  0  0  0
w3 0  0  0  0
w4 0  0  0  0

You go through the corpus and you encounter word w2 and near it is word n4. You record this encounter by incrementing the matrix element for w2-n4:

   n1 n2 n3 n4
w1 0  0  0  0
w2 0  0  0  1
w3 0  0  0  0
w4 0  0  0  0

You do this for every neighbouring word next to every word in context and finally you have your co-occurrence matrix.

Now this very same process can be viewed in a different way. Instead of incrementing single numbers, it can be viewed as vector addition. Forget the names given to the columns:

w1 0  0  0  0
w2 0  0  0  0
w3 0  0  0  0
w4 0  0  0  0

Instead assign a vector to each neighbour word where each vector consists of just zeros and a single 1. No two vectors can have a 1 in the same position. So these could be the vectors assigned to our 4 neighbour words:

n1: (1 0 0 0)
n2: (0 1 0 0)
n3: (0 0 1 0)
n4: (0 0 0 1)

Now when you encounter neighbour word n4 next to word in context w2, you just take w2's row, which is a vector, and add it to n4's vector:

w2: (0 0 0 0) +
n4: (0 0 0 1)
    =========
    (0 0 0 1)

Which gives you the updated matrix:

w1 0  0  0  0
w2 0  0  0  1
w3 0  0  0  0
w4 0  0  0  0

Do this for every neighbour next to every word in context and you have your co-occurrence matrix.

All random indexing does is change the neighbour words' vectors. Instead of the vectors being as long as the number of neighbours, the vectors are shortened to a fraction of what they are supposed to be. Consequently the number of columns in the matrix will also be reduced. "But how can you put a 1 in a different position for every neighbour word?" I hear you ask. You don't. What you do is you still keep the vectors mostly zero, but now you randomly put a few 1s and -1s in it:

w1 0  0  0
w2 0  0  0
w3 0  0  0
w4 0  0  0

n1: ( 1  0 -1)
n2: ( 0  1 -1)
n3: ( 0 -1  1)
n4: (-1  1  0)

If we encounter word in context w2 with neighbour word n4, then the matrix will become:

w1  0  0  0
w2 -1  1  0
w3  0  0  0
w4  0  0  0

If word in context w2 also has word n2 as a neighbour, then the matrix will become:

w1  0  0  0
w2 -1  2 -1
w3  0  0  0
w4  0  0  0

Now it will not be possible to know how many times each neighbour word co-occurs with each word in context, but that's OK. What matters is that each time you encounter a neighbour word, it leaves its mark on the word in context's row and that the more often it is encountered, the more its mark is pronounced. This means that you can still find similar words by comparing their rows together. The difference is that the rows are shorter and hence faster to compare.

Notice the online nature of this process. At any point in the corpus traversal, the matrix is always in its compressed form and there are no complex transformations that need to be made on it. You can ever add more words to or remove words from the matrix, without any further processing or extra data. You just have to find a compromise between how many columns to remove from the matrix and the individuality of the rows. The smaller the rows, the less of an individual mark each neighbour word will leave after adding its vector.

Summary of research paper "Unsupervised Lexical Substitution with a Word Space Model" by Dario Pucci, Marco Baroni, Franco Cutugno, and Alessandro Lenci

This is a summary of the research paper http://www.evalita.it/sites/evalita.fbk.eu/files/proceedings2009/Lexical%20Substitution/LS_UNINA_UNIPI_UNITN.pdf. This paper describes a way to automatically choose a word which can substitute another word in a sentence with minimal resources.

Overview

The system described in this paper was used for the EVALITA 2009 where a manually constructed evaluation set in Italian was provided.

In order to determine how well a word can replace another in a context, two types of vectors are used: a contextualized vector and an out-of-context vector. The contextualized vector is a composition of out-of-context vectors.

First, out-of-context vectors are collected from the corpus for each word using the usual method of counting how often each word co-occurs with the word being represented by the vector. The counts are then weighted to give less importance to words that co-occur with many words.

In order to find a substitutable word for a target word in a sentence, the out-of-context vectors of each content word in the sentence are collected and their weights are summed together. This is the contextualized vector. The word with the out-of-context vector that is most similar to this contextualized vector is chosen as the best word to substitute.

Nitty gritty

A lemmatized and part of speech tagged 2 billion token Italian corpus was constructed from which to extract the out-of-context vectors. The 20,000 most frequent nouns, verbs, adjectives and adverbs were considered as content words. Out-of-context vectors for these content words were extracted by counting how often they appear with other content words in the same sentence. The counts were weighted using log likelihood ratios and the co-occurrence matrix of counts was compressed to half its size using random indexing.

To create a contextualized context vector, the context sentence is lemmatized and part of speech tagged. The sentence is then split into a left and right side with respect to the target word and each side is filtered of all non-content words. The words in the sentence sub-parts that are within a set number of content words from the target word are used to construct the contextualized sentence. Their out-of-context vectors are normalized, multiplied by "1/(4*d)" where "d" is the distance of the word in the sentence sub-part from the target word (the closest content word has a distance of 1), and summed together.

Finally, cosine measure is used to find the most substitutable words by measuring the distance of the contextualized context vector to the out-of-context vectors of all the words that have the same part of speech tag as the target word.

Evaluation

The system was evaluated by using an evaluation set which consisted of sentences with a target word and suggested substitutable words by human annotators. Each suggestion included the number of annotators that suggested it. When comparing the best suggested substitutable word by the system with the most popular suggested word by the annotators, the system matched 10.84% of the evaluation set (that included a most popular suggested word).

Proof that there is only one prime number preceding a square number and any other power number (or "What is the use of factoring polynomials?")

Students are made to study how to factor polynomials but are never given an interesting task that involves using polynomial factorization. Here is a use that I find interesting.

Let's say we have the polynomial "x^2 - 1". This is a difference of two squares, which means that you can easily factorize it into "(x+1)(x-1)". But what does this factorization mean?

It means that any number which precedes a square number can always be factored into two numbers: one more than the number that was squared and one less than the number that was squared. For example, 15 precedes the square of 4, that is "4^2 - 1", so we can immediately conclude that "4+1" (5) and "4-1" (3) are factors of 15. Another example is 99 which precedes the square of 10, that is "10^2 - 1", so we can immediately conclude that "10+1" (11) and "10-1" (9) are factors of 99.

OK so maybe this is interesting, but can we use this for something more interesting?

Are there any numbers preceding a square number that are prime numbers? If there is such a number, than it's factors must be 1 and itself. So we are looking for a number of the form "x^2 - 1" such that it can only be factored into 1 and the number itself (which is prime). We said that any number of the form "x^2 - 1" can always be factored into two numbers, "x+1" and "x-1". So if this number, "(x+1)(x-1)", can only be factorized into 1 and itself, then surely one of these two factors must be 1. Which of these factors can be equal to 1? The "x+1" or the "x-1"? Since "x" is a positive number (the number that is squared), it can only be the "x-1" factor.

Will the "x-1" factor equalling 1 automatically make the other factor, "x+1", a prime number? No, because the "x+1" factor could itself be factorizable by other numbers. The fact that "x-1" equals 1 means that "(x+1)(x-1)" could be prime. But if "x-1" is not equal to 1 then, given that "x+1" cannot be equal to 1, "(x+1)(x-1)" is surely factorizable by "x-1", making it not a prime.

In order for "x-1" to equal 1, "x" must be 2. In this case, the number preceding a square number is "2^2 - 1" which is 3. Notice that the other factor, "x+1" would also equal 3 when "x" is 2 which makes sense since we said that one of the factors must be 1 and the other must be the number itself. If 3 a prime number? Yes. So when "x" is 2, "x-1" is 1 and "x+1" is a prime number. Therefore 3 is a prime number which precedes a square number.

Are there any other prime numbers which precede a square number? No, because if "x-1" is anything else but 1, then neither of the two factors will be 1, making the number factorizable into two numbers which are not 1 and itself, hence not being a prime number. This means that 2 is the only number "x" can be, which means that there are no other numbers which precede a square number that are prime.

It's interesting to also note that using the exact same method, one can proof that 7 is the only number preceding a cube number that is prime. Use this website to find the factors of numbers preceding other powers of "x".

It seems that there can only one number preceding an nth power of "x" that can be prime, for every power of "n". Can we prove this?

What will the factors of "x^n - 1" for any "n" be? Regardless of "n", will "x-1" always be a factor of "x^n - 1"? That is, will 1 always be a root of "x^n - 1"? Yes, because "1^n - 1" will always be 0, for all "n". So we can be sure that for "x^n - 1", regardless of "n", "x-1" will always be a factor. This means that "x^n - 1" will always be factored into "(x-1)(...)" where the "..." is some other polynomial factor. Since "x-1" is equal to 1 only when "x" equals 2, then "2^n - 1" is the only number preceding the power number "x^n" that can be a prime number. Of course it could be that the other number could be factored into other numbers hence making "(x-1)(...)" not a prime number when "x" is 2, but if "x" is not 2 then "(x-1)(...)" cannot be a prime number because "x-1" will be a factor.

So, regardless of what "n" is, there can only be one number which precedes "x^n" that can be prime, and that is "2^n - 1", since "x^n - 1" can always be factored into "(x-1)" and some other factor that cannot be equalled to 1. The other factor might not be prime, but if it is then it is the only one preceding "x^n" for all "x". Such prime numbers are called Mersenne primes.

Is this useful? This might be useful for testing whether a number is a prime number by checking if the number precedes a number raised to some power, x^n. If it does then it can only be a prime number if it is a number of the form of "2^n - 1", otherwise it will be always be factorizable by "x-1", regardless of what "x" or "n" are.

Term-Document matrices and Latent Semantic Analysis

Latent Semantic Analysis, or LSA, is a process used in natural language processing in order to find similar words or documents in a term-document matrix.

Term-Document matrix

A term-document matrix is a matrix which tells you how often a given word is found in a given document. Here is an example taken from the paper "Indexing by Latent Semantic Analysis" by Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer and Richard Harshman:

	D1	D2	D3	D4	D5	D6	D7	D8	D9
human	1	0	0	1	0	0	0	0	0
interface	1	0	1	0	0	0	0	0	0
computer	1	1	0	0	0	0	0	0	0
user	0	1	1	0	1	0	0	0	0
system	0	1	1	2	0	0	0	0	0
response	0	1	0	0	1	0	0	0	0
time	0	1	0	0	1	0	0	0	0
EPS	0	0	1	1	0	0	0	0	0
survey	0	1	0	0	0	0	0	0	1
trees	0	0	0	0	0	1	1	1	0
graph	0	0	0	0	0	0	1	1	1
minors	0	0	0	0	0	0	0	1	1

In this example, there are 9 nameless documents (could be websites, Wikipedia articles, anything) and 12 selected terms. Each numbers are the number of times the given term is found in the given document. For example the term "human" is found once in D1 but never occurs in D2.

Term document-matrices are neat because the meaning of both the words and the documents can be characterized by using a row or a column from the matrix. For example the row belonging to the term "human" is [1, 0, 0, 1, 0, 0, 0, 0, 0]. This says something about its meaning because it occurs in D1 and D4. Other words which are also found in the same documents would imply that they are somehow related or similar. On the other hand the column belonging to the document D1 is [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]. This says something about its meaning as well because it contains the words "human", "interface" and "computer" only. Other documents which also contain the same words would imply that they are also somehow related or similar.

This means that by comparing their respective row or column, that is, their a vector, you can determine how similar two words or documents are. You can even create a search engine which searches the documents based on keywords by treating the keyword list as a tiny document and comparing its vector with the vectors of the documents.

How can you compare vectors? You can use a vector similarity function such as Cosine similarity which given two vectors will give you a number between -1 and 1, depending on how similar they are.

Unfortunately this is not always the case because words in isolation do not discriminate meaning well enough. This is because of synonymous (different words which mean the same thing such as "couch" and "sofa") and polysemous (same word which means different things such as "bank account" and "river bank") words. This means that in the above matrix, the words "human" and "user" which should be similar will have the following vectors:
[1, 0, 0, 1, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 1, 0, 0, 0, 0]

These vectors do not hint at a similarity between the two words. However, although they appear in different documents, they may co-occur with other words which are shared between these documents. For example both "human" and "user" occur in documents which contain the words "computer" and "interface". This indirect co-occurrence can be harnessed by using LSA.

Latent Semantic Analysis

LSA uses linear algebra to bring out these latent (hidden) co-occurrences. In particular, it uses Singular Vector Decomposition (SVD). We will not go into the method used to perform this operation but will instead assume that there is a library which does it for us, in particular we will be using python's NumPy. SVD will basically decompose a matrix into 3 matrices which when multiplied together will give the original matrix again. These matrices are called U, S and V. Here is the python 2.7 code with NumPy which does this:

import numpy

a = numpy.matrix("""
1 0 0 1 0 0 0 0 0;
1 0 1 0 0 0 0 0 0;
1 1 0 0 0 0 0 0 0;
0 1 1 0 1 0 0 0 0;
0 1 1 2 0 0 0 0 0;
0 1 0 0 1 0 0 0 0;
0 1 0 0 1 0 0 0 0;
0 0 1 1 0 0 0 0 0;
0 1 0 0 0 0 0 0 1;
0 0 0 0 0 1 1 1 0;
0 0 0 0 0 0 1 1 1;
0 0 0 0 0 0 0 1 1
""")

(U, s, V) = numpy.linalg.svd(a, full_matrices=False)
S = numpy.diag(s)

print U
print S
print V

U

-0.221350778443	-0.113179617367	0.28895815444	-0.414750740379	-0.106275120934	-0.340983323615	-0.522657771461	0.0604501376207	0.406677508728
-0.197645401447	-0.0720877787583	0.135039638689	-0.552239583656	0.281768938949	0.495878011111	0.0704234411738	0.00994003720777	0.108930265566
-0.24047022609	0.0431519520879	-0.164429078921	-0.594961818064	-0.106755285123	-0.254955129767	0.302240236	-0.0623280149762	-0.492444363678
-0.403598863494	0.0570702584462	-0.337803537502	0.0991137294933	0.331733717586	0.384831917013	-0.00287217529118	0.000390504202226	-0.0123293478854
-0.644481152473	-0.167301205681	0.361148151433	0.333461601349	-0.158954979122	-0.206522587934	0.165828574516	-0.0342720233321	-0.270696289374
-0.265037470035	0.107159573274	-0.425998496887	0.073812192192	0.0803193764074	-0.169676388586	-0.282915726531	0.0161465471957	0.053874688728
-0.265037470035	0.107159573274	-0.425998496887	0.073812192192	0.0803193764074	-0.169676388586	-0.282915726531	0.0161465471957	0.053874688728
-0.300828163915	-0.141270468264	0.330308434522	0.188091917879	0.114784622474	0.272155276471	-0.0329941101555	0.0189980144259	0.165339169935
-0.205917861257	0.273647431063	-0.177597017072	-0.0323519366242	-0.537150003306	0.0809439782143	0.466897525101	0.0362988295337	0.579426105711
-0.0127461830383	0.490161792453	0.231120154886	0.0248019985275	0.594169515589	-0.392125064311	0.28831746071	-0.254567945176	0.225424068667
-0.0361358490222	0.62278523454	0.22308636259	0.000700072121447	-0.0682529381996	0.11490895384	-0.159575476506	0.681125438043	-0.231961226249
-0.0317563289336	0.450508919351	0.141115163889	-0.00872947061057	-0.30049511003	0.277343396711	-0.339495286197	-0.678417878879	-0.182534975926

S

3.34088375213	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0
0.0	2.54170100004	0.0	0.0	0.0	0.0	0.0	0.0	0.0
0.0	0.0	2.35394351766	0.0	0.0	0.0	0.0	0.0	0.0
0.0	0.0	0.0	1.64453229237	0.0	0.0	0.0	0.0	0.0
0.0	0.0	0.0	0.0	1.50483155049	0.0	0.0	0.0	0.0
0.0	0.0	0.0	0.0	0.0	1.30638195024	0.0	0.0	0.0
0.0	0.0	0.0	0.0	0.0	0.0	0.845903082647	0.0	0.0
0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.560134422839	0.0
0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.36367684004

V

-0.197392802296	-0.605990268919	-0.462917508082	-0.542114416925	-0.279469108426	-0.00381521297476	-0.0146314675059	-0.0241368353337	-0.0819573680281
-0.0559135177721	0.165592877548	-0.127312061589	-0.231755228874	0.106774717006	0.192847936262	0.437874882598	0.6151218992	0.529937071643
0.110269729184	-0.497326493627	0.207605952936	0.569921445337	-0.505449906656	0.0981842398306	0.192955571817	0.252903978748	0.0792731465334
-0.949785023586	-0.0286488989491	0.0416091951387	0.267714037747	0.15003543258	0.015081490733	0.0155071875251	0.0101990092357	-0.0245549055501
0.0456785564271	-0.206327277661	0.37833623285	-0.20560471144	0.327194409395	0.394841213554	0.349485347525	0.149798472318	-0.601992994659
-0.0765935584562	-0.256475221191	0.72439964169	-0.368860900846	0.034813049761	-0.300161116158	-0.212201424262	9.74341694268e-05	0.36221897331
-0.17731829729	0.432984244623	0.236889703269	-0.264799522759	-0.672303529825	0.340839827427	0.152194721647	-0.249145920279	-0.0380341888592
0.0143932590528	-0.0493053257482	-0.00882550204839	0.019466943894	0.0583495626425	-0.454476523485	0.761527011149	-0.449642756709	0.0696375496788
0.0636922895993	-0.242782899677	-0.0240768748334	0.0842069016903	0.262375876232	0.619847193574	-0.0179751825326	-0.51989049808	0.453506754839

Rank reduction

If U, S and V are multiplied together in that order, you'll get the original matrix again (approximately due to rounding errors). Notice that the second matrix S is a diagonal matrix, that is, every element in the matrix is zero except the diagonal. I will not go into the mathematics of this but if you take the second matrix S and replace the smallest number in the diagonal with zeros, when you multiply the three matrices together again you will get a matrix which is similar to the original matrix but which has some important differences. The more of the smallest values in the diagonal are replaced with zeros, the more similar the rows of similar words will become. This only works to a point of course. There has to be a balance between how many values are replaced with zeros and how much information is left in the matrix. Conviniently the values in the diagonal are sorted. If we replace the smallest 7 values with zeros, we get the following:

S[2][2] = 0.0
S[3][3] = 0.0
S[4][4] = 0.0
S[5][5] = 0.0
S[6][6] = 0.0
S[7][7] = 0.0
S[8][8] = 0.0

A = U*S*V
print A

0.162057973899	0.400498283106	0.378954540321	0.467566261179	0.175953674216	-0.05265494658	-0.115142842816	-0.159101981799	-0.0918382678755
0.140585289239	0.369800771629	0.328996029685	0.400427224981	0.164972474341	-0.0328154503866	-0.0705685702014	-0.0967682651277	-0.0429807318561
0.152449476913	0.505004444164	0.357936583955	0.410106780092	0.236231733239	0.0242165157003	0.0597805100865	0.086857300988	0.123966320774
0.258049326846	0.841123434512	0.60571994881	0.697357170797	0.392317949475	0.0331180051639	0.0832449070523	0.121772385778	0.187379725005
0.448789754476	1.23436483383	1.0508614968	1.26579559131	0.556331394289	-0.0737899841222	-0.154693831118	-0.209598161026	-0.0488795415146
0.159554277475	0.581681899927	0.375218968496	0.416897679847	0.276540515564	0.0559037446194	0.132218498596	0.188911459228	0.216907605531
0.159554277475	0.581681899927	0.375218968496	0.416897679847	0.276540515564	0.0559037446194	0.132218498596	0.188911459228	0.216907605531
0.218462783401	0.549580580647	0.510960471265	0.628058018099	0.242536067696	-0.0654109751045	-0.142521455703	-0.196611863571	-0.107913297073
0.096906385715	0.532064379223	0.229913654058	0.211753629516	0.266525126236	0.13675618206	0.314620778341	0.444440582128	0.424969482179
-0.0612538812664	0.232108208041	-0.138898404449	-0.265645889929	0.144925494403	0.240421047963	0.546147168984	0.767374200391	0.663709334488
-0.0646770216648	0.335281153514	-0.14564054552	-0.301406070826	0.202756409842	0.305726121021	0.694893368967	0.976611213875	0.848749689135
-0.0430820430074	0.25390566477	-0.0966669539764	-0.207858206667	0.15191339999	0.221227031407	0.502944876315	0.706911627157	0.615504399537

Now if we take the first and fourth rows which belong to "human" and "user", we get these:
0.162057973899 0.400498283106 0.378954540321 0.467566261179 0.175953674216 -0.05265494658 -0.115142842816 -0.159101981799 -0.0918382678755
0.258049326846 0.841123434512 0.60571994881 0.697357170797 0.392317949475 0.0331180051639 0.0832449070523 0.121772385778 0.187379725005
These rows are much more similar than they were before and they are more similar than other rows in the matrix.

This is called a rank reduction because the effect of replacing the values with zeros was that you get a matrix with a smaller "rank" which is just a numeric property of matrices.

Dimension reduction

The problem with a rank reduction is that suddenly the matrix becomes full of numbers where it used to be full of zeros. This means that in order to use the matrix you need a lot of processing which is slow. So a slight modification is used instead which has the effect of making the matrix smaller, whilst still exposing the latent co-occurrences of the matrix. After zeroing out the values, rather than multiplying all 3 matrices, only U and S or S and T are multiplied together, depending on whether you want to compare rows or columns.

S[2][2] = 0.0
S[3][3] = 0.0
S[4][4] = 0.0
S[5][5] = 0.0
S[6][6] = 0.0
S[7][7] = 0.0
S[8][8] = 0.0

A = U*S
print A

-0.739507219222	-0.287668746646	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.660310310378	-0.183225579361	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.803383071215	0.109679359776	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-1.34837688543	0.145055532965	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-2.15313661085	-0.425229641788	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.885459377345	0.272367594554	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.885459377345	0.272367594554	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-1.00503192501	-0.359067290462	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.687947636947	0.695529949191	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.0425835158144	1.24584471806	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.120725670868	1.58293385344	0.0	0.0	0.0	0.0	0.0	0.0	0.0
-0.106094203362	1.14505897084	0.0	0.0	0.0	0.0	0.0	0.0	0.0

The columns of zeros on the right of the matrix correspond to the values which were zeroed out in the diagonal of S. We can simply remove these columns.

-0.739507219222	-0.287668746646
-0.660310310378	-0.183225579361
-0.803383071215	0.109679359776
-1.34837688543	0.145055532965
-2.15313661085	-0.425229641788
-0.885459377345	0.272367594554
-0.885459377345	0.272367594554
-1.00503192501	-0.359067290462
-0.687947636947	0.695529949191
-0.0425835158144	1.24584471806
-0.120725670868	1.58293385344
-0.106094203362	1.14505897084

Now we only have only two columns to compare. The rows corresponding to "human" and "user" are:
-0.739507219222 -0.287668746646
-1.34837688543 0.145055532965

This is called a dimension reduction because the vectors being compared will become smaller, which allows for faster computation. The same thing could have been done to compare documents by multiplying S and V instead and then removing the bottom rows instead of the rows on the right.

Proof that the square roots of all non-square numbers are irrational

In a previous post I described the classical way to prove that the square root of 2 is irrational. But that proof doesn't generalize (at least not easily) to the square root of other numbers being irrational. This proof can be applied to any number and any root (cube root, etc.).

This proof uses the Fundamental Theorem of Arithmetic which states that there is only one way to factor a whole number greater than 1 into a product of prime numbers raised to some power. For example 12 = 2^2 x 3^1. There is no other way to factorize 12 into powers of prime numbers other than 2^2 and 3^1. Another example, 15 = 2^0 x 3^1 x 5^1. So the exponent of the first prime number must be 0, the second must be 1 and the third must be 1. If we had to include the fourth prime number we'd give it an exponent of 0 too, that is, 2^0 x 3^1 x 5^1 x 7^0. In other words, for any number "n" greater than 1,

n = 2^i1 x 3^i2 x 5^i3 x ... x Pn^in

where "n" is the number of prime factors used, P1 is the first prime number, P2 is the second, etc. and i1 is the exponent of the first prime factor, i2 of the second, etc.

Proof for the square root of 2

Onto the proof. We'll start from the proof for the square root of 2 and then generalize it.

We start exactly the same way we started in the other proof.

Assume sqrt(2) = a/b
2 = (a/b)^2
2 = a^2 / b^2
2 b^2 = a^2

Now we use the fundamental theorem of arithmetic on "a" and "b".

Let a = 2^i1 x 3^i2 x 5^i3 x ... x Pn^in
Let b = 2^j1 x 3^j2 x 5^j3 x ... x Pm^jm

Therefore,
2 (2^j1 x 3^j2 x 5^j3 x ... x Pm^jm)^2 = (2^i1 x 3^i2 x 5^i3 x ... x Pn^in)^2
2 (2^2j1 x 3^2j2 x 5^2j3 x ... x Pm^2jm) = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in
2 x 2^2j1 x 3^2j2 x 5^2j3 x ... x Pm^2jm = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in
2^(2j1+1) x 3^2j2 x 5^2j3 x ... x Pm^2jm = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in

Now since the number on the left and the number on the right are both equal, then by the fundamental theorem of arithmetic, apart from the number of prime factors being equal, the exponents of their prime factors must also be equal. Therefore,

m = n

and

2j1+1 = 2i1
2j2 = 2i2
2j3 = 2i3
...
2jm = 2in

So then 2j1+1 = 2i1. But one is an odd number whilst the other is an even number. This cannot be the case, therefore "a^2" and "2b^2" cannot be equal, therefore "a/b" cannot equal "sqrt(2)" and therefore "a" and "b" cannot exist.

What happens if the square root is actually rational?

Let's try that again with the square root of 4 this time.

Assume that sqrt(4) = a/b
4 b^2 = a^2
(2^2) (2^j1 x 3^j2 x 5^j3 x ... x Pm^jm)^2 = (2^i1 x 3^i2 x 5^i3 x ... x Pn^in)^2
(2^2)(2^2j1 x 3^2j2 x 5^2j3 x ... x Pm^2jm) = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in
2^(2j1+2) x 3^2j2 x 5^2j3 x ... x Pm^2jm = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in

By the fundamental theorem of arithmetic,
m = n

and

2j1+2 = 2i1
2j2 = 2i2
2j3 = 2i3
2jm = 2in

As you can see, all exponents can be equal this time. 2j1+2 = 2i1 can be true because this time both numbers are even numbers. In fact j1 = 0.

You can also notice that since 4 is a composite number, we had to factor it as well in order to assimilate it into the factors of b.

Square root of 12?

Again, we use the proof on a composite number, this time with no rational square root.

Assume that sqrt(12) = a/b
12 b^2 = a^2
(2^2 x 3^1) (2^j1 x 3^j2 x 5^j3 x ... x Pm^jm)^2 = (2^i1 x 3^i2 x 5^i3 x ... x Pn^in)^2
(2^2 x 3^1)(2^2j1 x 3^2j2 x 5^2j3 x ... x Pm^2jm) = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in
2^(2j1+2) x 3^(2j2+1) x 5^2j3 x ... x Pm^2jm = 2^2i1 x 3^2i2 x 5^2i3 x ... x Pn^2in

By the fundamental theorem of arithmetic,
m = n

and

2j1+2 = 2i1
2j2+1 = 2i2
2j3 = 2i3
2jm = 2in

Looks like this time it although 2j1+2 = 2i1 can be true, 2j2+1 = 2i2 cannot be.

Cube root of 2?

Let's try that again with a cube root instead.

Assume that 2^(1/3) = a/b
2 b^3 = a^3
2 (2^j1 x 3^j2 x 5^j3 x ... x Pm^jm)^3 = (2^i1 x 3^i2 x 5^i3 x ... x Pn^in)^3
2 (2^3j1 x 3^3j2 x 5^3j3 x ... x Pm^3jm) = 2^3i1 x 3^3i2 x 5^3i3 x ... x Pn^3in
2^(3j1+1) x 3^3j2 x 5^3j3 x ... x Pm^3jm = 2^3i1 x 3^3i2 x 5^3i3 x ... x Pn^3in

By the fundamental theorem of arithmetic,
m = n

and

3j1+1 = 3i1
3j2 = 3i2
3j3 = 3i3
3jm = 3in

Can 3j1+1 = 3i1? No, because no multiple of 3 can equal another multiple of 3 plus 1, since any multiple of 3 plus 1 cannot be a multiple of 3.

In general

Now let's try to generalize this to any number "q" and any root "r".

Assume that q^(1/r) = a/b
q b^r = a^r
(2^k1 x 3^k2 x 5^k3 x ... x Pl^kl) (2^j1 x 3^j2 x 5^j3 x ... x Pm^jm)^3 = (2^i1 x 3^i2 x 5^i3 x ... x Pn^in)^3
(2^k1 x 3^k2 x 5^k3 x ... x Pl^kl) (2^rj1 x 3^rj2 x 5^rj3 x ... x Pm^rjm) = 2^ri1 x 3^ri2 x 5^ri3 x ... x Pn^rin

Now since we don't know whether "q" has more factors than "b" or vice versa, the last factor in the assimilated factors will simply be called "Pz^y" where z=max(l,m) and "y" is the exponent of this last prime number.

2^(rj1+k1) x 3^(rj2+k2) x 5^(rj3+k3) x ... x Pz^y = 2^ri1 x 3^ri2 x 5^ri3 x ... x Pn^rin

By the fundamental theorem of arithmetic,
z = n

and

rj1+k1 = ri1
rj2+k2 = ri2
rj3+k3 = ri3
...
y = rin

For rj1+k1 = ri1 to be true, "k1" must be a multiple of "r", otherwise rj1+k1 cannot be a multiple of "r". The same goes for all the other exponents. So this means that every exponent of the prime factors of "q" must be a multiple of "r", that is

q = 2^rh1 x 3^rh2 x 5^rh3 x ... x Pl^rhl

But then this means

q = (2^h1 x 3^h2 x 5^h3 x ... x Pl^hl)^r

which further means that "q" is a number raised to the power of "r". Therefore, for any whole number to have its nth root be a rational number, that number must be equal to another whole number raised to the power of "n". If there aren't any whole numbers which when raised to the nth power equal the number in question, then there cannot be any fractions either.