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.

Tower of Hanoi

The Tower of Hanoi is a simple puzzle with an interesting pattern as a solution. You have 3 pegs with 3 discs of different sizes set at the first peg in ascending order like this:



The puzzle is to move all the disks one by one to the last peg with the two rules that every disc must be set at a peg and that no disc be placed on a smaller disc. The puzzle is made harder by the addition of more discs.

The minimal number of moves needed to move all 3 discs is 7 as follows:















So how do we know that there is no shorter way to move them all to the other side? Let's ignore the number of discs and just focus on how to reach the goal.

There are three sub goals required to reach the final goal:

1. Move all the discs except the largest one out of the way, allowing the largest disc to be set at the destination peg.
   
   
   
2. Move the largest disc to the destination peg.
   
   
3. Move the rest of the discs on the largest disc.
   
   

The crucial point of this puzzle is that the movement of the smaller discs is independent of the largest disc. This means that the number of steps needed to move the smaller discs to the middle peg is the same as the number of steps needed to solve the Tower of Hanoi with one less disc.

It also doesn't matter which peg is the destination peg since the number of moves would be equivalent regardless of where the pegs need to go. All that matters is that all the discs move from one peg to another with just another peg to move around on.

So the formula for finding the smallest number of steps needed to move "n" discs is

steps(n) = steps(n-1) + 1 + steps(n-1)

where the first "steps(n-1)" is the number of steps to move the smaller discs to the other peg, the "1" is the number of steps to move the largest disc to the destination peg and the last "steps(n-1)" is the number of steps needed to move the smaller discs on top of the largest disc.

Let's see an example.

steps(3) =


The first thing we want to do is to move the 2 smaller discs off the largest disc so the the largest disc can be placed on the destination peg like this:

steps(3-1)


Then we need to move the largest disc to the destination peg like this:

+ 1


Finally we need to move the smaller disc to the destination peg as well like this:

+ steps(3-1)


How many steps will it take to move the smaller discs though? It will take the same number of steps as solving the Tower of Hanoi with 2 discs only like this:

steps(2) =


steps(2-1)


+ 1


+ steps(2-1)


Which is the same as when moving smaller 2 discs in the the 3 disc version, except that the destination peg was the middle rather than the last:

steps(3-1) =


steps(3-1-1)


+ 1


+ steps(3-1-1)


Anything other than this strategy will increase the number of steps needed to reach the goal because it means that at some point a disc was placed at a peg in which a larger disc needs to be placed and hence you will need to bring that smaller disc back to its original place.

So we go back to the proposed formula:

steps(n) = steps(n-1) + 1 + steps(n-1)

The recursion of the formula can keep on going until it turns into the number of steps to move 1 disc which is:

steps(1) = 1

Now the formula can be simplified into:

steps(n) = 2 steps(n-1) + 1

Can we solve the recurrence relation into a simple closed form? Without loss of generalization, let's try to decompose it iteratively for n=4:

steps(4) = 2 steps(3) + 1
steps(4) = 2(2 steps(2) + 1) + 1
steps(4) = 2(2(2 steps(1) + 1) + 1) + 1
steps(4) = 2(2(2(1) + 1) + 1) + 1
steps(4) = 2(2(2 + 1) + 1) + 1

Expanding the expression we get:

steps(4) = 2(2(2 + 1) + 1) + 1
steps(4) = 2(2(2) + 2 + 1) + 1
steps(4) = 2(2(2)) + 2(2) + 2 + 1

So it seems we have a sum of powers of 2, which is:

steps(4) = 2^3 + 2^2 + 2^1 + 2^0

A quick look at binary numbers (or just geometric series) lets you quickly notice that this is equivalent to:

steps(4) = 2^4 - 1

Thus, returning back to "n" instead of "4",

steps(n) = 2^n - 1

So the number of steps needed to move "n" discs is "2^n - 1" which means that in the case of 3 discs that is "2^3 - 1" that is, 7.

Python N-gram Map

I have developed a data structure in Python to store and query n-grams which is released as open source here. This blog post shall give examples on how to use it.

To add n-grams

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) which map to None

x = NGramMap()
x[('a','a','a')] = None
x[('a','a','b')] = None
x[('a','b','a')] = None
x[('b','a','a')] = None

To count n-gram frequency

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) several times which map to the number of times they were encountered.

ngrams = [ ('a','a','a'), ('a','a','b'), ('a','a','a'), ('a','a','b'), ('a','b','a'), ('b','a','a'), ('a','b','a'), ('b','a','a'), ('a','b','a'), ('a','b','a') ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for ngram in x.ngrams():
    print(ngram, x[ngram])

To find n-grams which contain particular elements

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) several times which map to the number of times they were encountered.

ngrams = [ ('a','x','y'), ('x','a','y'), ('a','x','y'), ('b','x','y'), ('c','x','z')  ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for ngram in x.ngrams_with_eles({ 'a', 'y' }):
    print(ngram, x[ngram])

To find n-grams which follow a particular pattern

Adding the n-grams (a,a,a), (a,a,b), (a,b,a), (b,a,a) several times which map to the number of times they were encountered.

ngrams = [ ('a','x','y'), ('x','a','y'), ('a','x','y'), ('b','x','y'), ('c','x','z')  ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for ngram in x.ngrams_by_pattern(( None, 'x', 'y' ), { 0 }):
    print(ngram, x[ngram])

To find elements which share similar contexts

You can find elements which occur in the same context in their n-grams, for example 'a' and 'b' share a context in the n-grams (a, x, y) and (b, x, y) as do 'p' and 'q' in the n-grams (x, p, y) and (x, q, y).

ngrams = [ ('a','x','y'), ('x','a','y'), ('a','x','y'), ('b','x','y'), ('c','x','z')  ]

x = NGramMap()
for ngram in ngrams:
    if ngram not in x:
        x[ngram] = 0
    x[ngram] += 1

for element in x.elements():
    print(element)
    for ngram in x.ngrams_with_eles({ element }):
        ele_index = ngram.index(element)
        for ngram_ in x.ngrams_by_pattern(ngram, { ele_index }):
            if ngram_[ele_index] != element:
                print("\t", ngram_[ele_index])

Summary of research paper "Automatic Word Sense Discrimination" by Hinrich Schütze

This is a summary of the research paper http://delivery.acm.org/10.1145/980000/972724/p97-schutze.pdf. This paper describes a way to automatically identify different senses (meanings) for words with multiple senses and to disambiguate the sense of a word in context according to these identified senses.

Overview

We start by creating word vectors for each word by counting how often certain other words occur close to it. These other words are called the dimensions of the vector. This vector space is called the word space.

For example, if the word "judge" is to be projected into a word space with dimensions being "legal" and "clothes", then we go through a corpus and count the number of times the words "legal" and "clothes" occur close to "judge" and record these frequencies in a vector. This vector would represent the meaning of "judge" and we'd expect the count for "legal" to be higher than the count for "clothes". On the other hand the word vector for "robe" using the same dimensions would have a higher count for "clothes" than for "legal". The problem is that, in a corpus, an ambiguous word like "suit" would have both the legal sense and the clothes sense so its vector would not give a good indication of its meaning.

In order to disambiguate the sense of an ambiguous word like "suit", the sentence in which it occurs is used as a context to see what that particular instance of the word means. Words are chosen from the sentence, called features, in order to be used as cues to identify in which sense the ambiguous word is being used. For example, if in the sentence with the word "suit" the words "law", "judge" and "statute" are found, then we can be confident that the sense of "suit" in that context is the legal sense, since all of these words have a high count for the "legal" dimension in their word vector. In practice, centroid of the word vectors of these features is calculated and this centroid is then used to see in which dimension the word vectors of the features are generally pointing. This centroid is called the context vector of the ambiguous word.

Of course in practice there will be a lot of dimensions in the word space so senses will not be limited to a single dimension but to combinations of dimensions. This means that in order to establish what the senses of an ambiguous word are, the context vectors of each instance of the word must be clustered such that similar context vectors are clustered as sharing the same sense and each cluster will be a sense of the ambiguous word. The centroid of each cluster is called a sense vector and when an ambiguous word is to be disambiguated into a sense, the sense vector which is most similar to the word's context vector would be considered its sense.

Nitty gritty

Since there must be of a fixed amount of dimensions of the word space and the feature words which can be used for context vectors, a method to select them must be used. Two methods were tested: local and global selection. In local selection the feature and dimension words are exactly the same and different dimensions/features are used for each ambiguous word; so the system will only disambiguate ambiguous words for which dimensions and features were already determined. In global selection the dimension and feature words are different from each other and are selected once such that all ambiguous words are disambiguated using these same dimensions and features.

Local selection works by simply checking all words which are not stop words and which occur within 25 words of the ambiguous word and accepting as dimensions/features only the 1000 most important words. Importance is measured using one of two criteria: the number of times the dimension/feature occurs near the word in question and the chi-squared test of how much the ambiguous word and the dimension/feature word correlate together.

Global selection on the other hand uses the 20,000 most frequent non-stop words in the corpus as features and the 2,000 most frequent words as dimensions.

Once the dimensions and features are collected, they are arranged into a matrix such that the rows represent the dimensions and the columns the features. In this way the columns of the matrix are the word vectors of the different features. In order to disambiguate an ambiguous word, either these word vectors are used as is or they are reduced using Singular Value Decomposition (SVD) in order to reduce the size of the word vectors (number of rows) to 100 (which means that the word vectors will not correspond to frequencies of neighbouring words anymore but to abstract dimensions). Global selection was not tested with SVD.

Context vector elements are normalized and weighted by inverse document frequency.

Similarity between vectors is calculated using cosine similarity and clustering is done using the Buckshot algorithm.

Evaluation

In order to evaluate the system, pseudowords were created by taking two different words and replacing them with the same invented word. If we have two sentences "The boy peeled the banana." and "The boy opened the door.", and the words "banana" and "door" are replaced with the pseudoword "banana/door" such that the sentences are now "The boy peeled the banana/door." and "The boy opened the banana/door.", then the pseudoword is now an ambiguous word with two senses: the banana sense and the door sense. The system is now to attempt to identify these two senses and identify when it is used in the banana sense and when it is used in the door sense. This is easy to evaluated since we already know how each instance should be disambiguated and there is no need for prior manual identification of the senses.

The following is the average percent correct disambiguation for 20 pseudo words for different experimental conditions:

Condition	%
Local-Frequency-no SVD:	77.8
Local-Frequency-SVD:	82.9
Local-Chi squared-no SVD:	72.1
Local-Chi squared-SVD:	84.1
Global-Frequency-SVD:	89.7