After reading this paper, I was confused by Algorithm 1 (page 2) as it did not really match parts of the text. So I contacted the author and would now like to clarify it for everyone else.
The paper describes a generative adversarial network which generates images that are hard to classify in order to augment a training set for a second classifier. This is done by attaching a classifier to the generator (apart from the discriminator) which learns to classify the generated data with a gradient reversal layer between the classifier and the generator. The gradient reversal layer forces the generator to generate examples which are difficult to classify by negating the gradient signal coming from the classifier loss before passing it to the generator. This makes the generator learn to maximise the classifier loss whilst the classifier is learning the minimise it, resulting in adversarial learning. The author does not give a reason for why the same kind of adversarial learning is not applied to both parts of the model.
What confused me is how would you know what class the difficult to classify examples produced by the generator would be when training the target classifier with the augmented training set. The reason I was confused is because I did not realise that this is not a GAN, but a CGAN, a conditional generative adversarial network. A CGAN works by feeding both the generator and the discriminator a class label. The label would be the label of the real data and a random label in generated data. Since the labels are the same for both the generator and the discriminator, the discriminator learns to discriminate the fake data by matching it to the label and seeing if it looks like what is expected given the label whilst the generator produce images which match the given label in order to fool the discriminator.
By combining this with the gradient reversal layer, the generated images would be both similar to real data of the given label and also difficult to classify. These two properties would be contradictory except for the fact that the effect of the classifier is scaled down due to the lambda hyperparameter of the gradient reversal layer, making the discriminator take precedence.
Showing posts with label scientific paper summary. Show all posts
Showing posts with label scientific paper summary. Show all posts
Sunday, November 29, 2020
Wednesday, March 12, 2014
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.
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.
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.
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).
Friday, September 6, 2013
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.
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.
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.
The following is the average percent correct disambiguation for 20 pseudo words for different experimental conditions:
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 |
Saturday, January 12, 2013
Summary of research paper "Discovering Word Senses from Text" by Patrick Pantel and Dekang Lin
This is a summary of the research paper http://webdocs.cs.ualberta.ca/~lindek/papers/kdd02.pdf. This paper describes a way to group together similar words according to the different meanings of each word and all by just using the contexts of the words. You should also check the PhD thesis of the algorithm used in this paper by Panten at http://www.patrickpantel.com/download/papers/2003/cbc.pdf. You might also be interested in seeing this Java implementation of the algorithm at https://github.com/fozziethebeat/S-Space/blob/master/src/main/java/edu/ucla/sspace/clustering/ClusteringByCommittee.java.
In order to judge the similarity between two words, the grammatical relations between those words and other words as used in a corpus were used. For example, US state names can be recognized as similar because they all share the following contexts:
___ appellate court
campaign in ___
___ capital
governor of ___
___ driver's license
illegal in ___
primary in ___
___'s sales tax
senator for ___
So, for example, by counting the number of times the verb "campaign" is grammatically related to each word in a corpus, that count can be used to find other words which are similar because they have similar counts. The grammatically related word is called a feature of the word. By finding all the different features of each word in a corpus, we can give each word a list of its features and the number of times that feature was encountered as a context of the word. For example, we can find the number of times the word "campaign" appears as a feature of "California", as well as the word "capital", "governor", etc. All these features when grouped together are called a feature vector of the word.
However, in this paper, it is not the counts, or frequencies, that are associated with the features. Using raw counts to judge the importance of a feature is misleading as the feature might just be a common feature in general and not useful to find similar words by checking if they have features in common. So instead the pointwise mutual information is used. This compares the probability of the two word co-occurring together with the probability that they do so by coincidence (independently). In this paper it is calculated as:
However the pointwise mutual information gives bigger values to rare words and contexts so it is made fair by being multiplied by a discounting factor:
In order to measure the similarity between two words, the cosine coefficient is used:
Words with different meanings, or senses, are called polysemous words. In order to cluster the words together according to their senses, using a different cluster for each sense, three phases are used.
In the first phase, the top 10 similar words for each word were found. In order to speed up the search, the feature vectors were indexed by their features, such that you can find all the feature vectors that have a given feature. The index is then used to find feature vectors that share features in common with the word we are finding similar words to. In this way you skip all the words which share nothing in common with the word of interest. In order to further speed things up, only some of the word's features are considered. The features which have a small value (pointwise mutual information) are ignored when looking for similar words. So only words which share these high valued features are retrieved from the index. So if we are looking for similar words to a word with the following feature vector:
In the second phase, a clustering algorithm called "clustering by committee" is applied to the words using the similarity lists of the first phase. The clustering algorithm tries to assign the words into small clusters called "committees". Words which don't fit into any committee are called "residue". The point of these small clusters is to obtain centroids from which to cluster all the words, just like the randomly chosen centroids for k-means clustering, but instead the centroids are chosen intelligently. These centroids would originate from committees of words all of which mean a particular word sense. In this way the committee would decide whether to allow a word in the cluster or not. The way each committee is chosen is such that it is composed of words which do not have multiple meanings as used in the corpus. This makes the centroid of its feature vectors tend to only have features which belong to a particular word sense rather than to multiple senses, which leads to purer clusters of word senses. For example, when clustering USA state names, state names which are also names of cities (such as New York) are not included in the committee and only state names which mean nothing else are included which would avoid clustering city names in with the state name cluster when full clustering is performed. This is the clustering algorithm:
In order to judge the similarity between two words, the grammatical relations between those words and other words as used in a corpus were used. For example, US state names can be recognized as similar because they all share the following contexts:
___ appellate court
campaign in ___
___ capital
governor of ___
___ driver's license
illegal in ___
primary in ___
___'s sales tax
senator for ___
So, for example, by counting the number of times the verb "campaign" is grammatically related to each word in a corpus, that count can be used to find other words which are similar because they have similar counts. The grammatically related word is called a feature of the word. By finding all the different features of each word in a corpus, we can give each word a list of its features and the number of times that feature was encountered as a context of the word. For example, we can find the number of times the word "campaign" appears as a feature of "California", as well as the word "capital", "governor", etc. All these features when grouped together are called a feature vector of the word.
However, in this paper, it is not the counts, or frequencies, that are associated with the features. Using raw counts to judge the importance of a feature is misleading as the feature might just be a common feature in general and not useful to find similar words by checking if they have features in common. So instead the pointwise mutual information is used. This compares the probability of the two word co-occurring together with the probability that they do so by coincidence (independently). In this paper it is calculated as:
mi(w,c) = p(w,c) / (p(w) × p(c))where "w" is the word, "c" is a context of "w", "p(w,c)" is the probability of finding "c" as a context of "w", "p(w)" is the probability of finding the word "w" in some context and "p(c)" is the probability of finding "c" as a context of some word. These probabilities are calculated as follows:
p(w,c) = f(w,c) / N p(w) = sum(f(w,c) for c in contexts) / N p(c) = sum(f(w,c) for w in words) / N N = sum(sum(f(w,c) for w in words) for c in contexts)where "f(w,c)" is the number of times "c" is a context of "w" and "N" is the total number of word-context combinations.
However the pointwise mutual information gives bigger values to rare words and contexts so it is made fair by being multiplied by a discounting factor:
df(w,c) = f(w,c) / (f(w,c)+1) × min(f(w), f(c)) / min(f(w), f(c))where
f(w) = sum(f(w,c) for c in contexts) f(c) = sum(f(w,c) for w in words)
In order to measure the similarity between two words, the cosine coefficient is used:
sim(a,b) = sum(mi(a,c) × mi(b,c) for c in contexts) / sqrt(sum(mi(a,c)^2 for c in contexts) × sum(mi(b,c)^2 for c in contexts))
Words with different meanings, or senses, are called polysemous words. In order to cluster the words together according to their senses, using a different cluster for each sense, three phases are used.
In the first phase, the top 10 similar words for each word were found. In order to speed up the search, the feature vectors were indexed by their features, such that you can find all the feature vectors that have a given feature. The index is then used to find feature vectors that share features in common with the word we are finding similar words to. In this way you skip all the words which share nothing in common with the word of interest. In order to further speed things up, only some of the word's features are considered. The features which have a small value (pointwise mutual information) are ignored when looking for similar words. So only words which share these high valued features are retrieved from the index. So if we are looking for similar words to a word with the following feature vector:
{
("object of", "carry") : 5.118,
("object of", "bring") : 3.364,
("object of", "look at") : 2.753,
("object of", "have") : 1.353
}and we only consider features with a value higher than 3.0 then we will use the index to find all the words which have a feature vector with the features{
("object of", "carry") : 5.118,
("object of", "bring") : 3.364
}This narrows down the number of words to check the similarity of (using the sim function) and so speeds up the search greatly. The top 10 most similar words are then retrieved. The fact that words which don't share high valued features are ignored did not seem to affect the result.In the second phase, a clustering algorithm called "clustering by committee" is applied to the words using the similarity lists of the first phase. The clustering algorithm tries to assign the words into small clusters called "committees". Words which don't fit into any committee are called "residue". The point of these small clusters is to obtain centroids from which to cluster all the words, just like the randomly chosen centroids for k-means clustering, but instead the centroids are chosen intelligently. These centroids would originate from committees of words all of which mean a particular word sense. In this way the committee would decide whether to allow a word in the cluster or not. The way each committee is chosen is such that it is composed of words which do not have multiple meanings as used in the corpus. This makes the centroid of its feature vectors tend to only have features which belong to a particular word sense rather than to multiple senses, which leads to purer clusters of word senses. For example, when clustering USA state names, state names which are also names of cities (such as New York) are not included in the committee and only state names which mean nothing else are included which would avoid clustering city names in with the state name cluster when full clustering is performed. This is the clustering algorithm:
def clustering_by_committee(words, simlists, committeeSimilarityThreshold, residueSimilarityThreshold):
highest_scoring_clusters = []
#STEP 1.1
for word in words:
#STEP 1.2
clusters = averagelink_cluster(simlists[word]) #use average link hierarchical agglomerative clustering to cluster the words into similarity clusters such that clusters can only be merged if their similarity is below a minimum similarity threshold
#STEP 1.3
for cluster in clusters:
scores[cluster] = size(cluster) * average_pairwise_similarity(cluster)
#STEP 1.4
highest_scoring_clusters.append(arg_max(scores)) #append the highest scoring cluster
#STEP 2.1
sort_descending(highest_scoring_clusters) #sort highest_scoring_clusters in descending order of score
#STEP 3.1
committees = []
#STEP 3.2
for cluster in highest_scoring_clusters:
#STEP 3.3
centroid = compute_centroid(cluster) #the centroid is computed by averaging the frequencies (not the pointwise mutual information) of the features of each word in the cluster. these average frequencies are used to compute the pointwise mutual information which will be used to create the centroid vector (just as the feature vectors were constructed).
#STEP 3.4
if similarity(centroid, any committee in committees) < committeeSimilarityThreshold: #a committee cannot be very similar to other committees
committees.append(cluster)
#STEP 4.1
if committees == []:
return committees
residues = []
#STEP 5.1
for word in words:
#STEP 5.2
if similarity(word, any committee in committees) < residueSimilarityThreshold: #if a word is not sufficiently close to any committee then it is a residue and more committees are needed for this word to belong to. otherwise the word is "covered" by a committee.
residues.append(word)
#STEP 6.1
if residues == []:
return committees
#STEP 6.2
else:
return committes + clustering_by_committee(residues, simlists, threshold1, threshold2)
In the third phase, the committees discovered in the second phase are used to actually cluster words by their different senses. The words are not added to committees themselves, rather to clusters each of which is represented by its own committee. The similarity of a word to a cluster is the similarity between the word's feature vector and the centroid of the cluster's committee (which remains the same regardless of which words are added to the cluster). If hard clustering is used then words are only added to the most similar cluster, but if soft clustering is used, as is the case here, then the same word can be added to more than one cluster, one for each sense of the word. Here is the algorithm which assigns words to clusters:
def assign_word_to_clusters(word, committeeClusters, minWordSimilarity, maxClusterSimilarity):
clusters = []
similar_clusters = top_200_most_similar(committeeClusters, word) #find the top 200 clusters whose committee's centroid is most similar to the word
while similar_clusters != []:
best_cluster = get_most_similar_cluster(similar_clusters, word)
if similarity(word, best_cluster) < minWordSimilarity:
break #there is no cluster left that is similar enough to assign the word to
else if similarity(best_cluster, any cluster in similar_clusters) < maxClusterSimilarity: #a word cannot be assigned to a cluster whose committee's centroid is similar to another cluster's committee's centroid
best_cluster.add(word)
remove_common_features(word, best_cluster) #remove the features from the word's feature vector which are also found in best_cluster's committee's centroid
similar_clusters.remove(best_cluster)
The fact that the features in the word which are also found in the cluster's committee's centroid are removed before it is assigned to another cluster is important to allow it to be assigned to other less common sense clusters. For example, the word "plant" would first be assigned to the "factory" sense cluster in a newspaper corpus because that is the meaning of the word most of the time in such a corpus. After it is assigned to the factory sense cluster, the features which have to do with this sense are removed (or their values are set to 0) from the feature vector of "plant". Without these features, the remaining features would be of a different sense such as of living plant and so now it can be easily assigned to the living plant sense as these features are not overshadowed anymore.
So this system will output a list of clusters to which each sense of every word will belong. In order to evaluate it, the sense clusters are compared to WordNet synonym groups called synsets. This is how the comparison is made:
First, the similarity measure proposed by Lin which measures the similarity between two WordNet synsets is used. This is described in another post here.
sim_synset(s1, s2) = 2 log P(most_specific_common_synset(s1, s2)) / (log P(s1) + log P(s2))The similarity between a word and a synset is the maximum similarity between the synset and one of the synsets in which the word belongs:
sim_synset_word(s, w) = max(sim_synset(s, t) for t in synsets_of(w))Let "top_words(c, k)" be the top "k" most similar words in a sense cluster "c" to the committee which the cluster was based on. The similarity between a synset and a sense cluster is the average similarity between the synset and "top_words(c, k)".
sim_synset_cluster(s, c, k) = sum(sim_synset_word(s, w) for w in top_words(c, k)) / kWe can check if a word belongs to a correct sense cluster by checking the similarity of the sense cluster to all the synsets of the word. If the maximum similarity found is greater than a threshold, then it is considered to be a correct sense cluster.
is_correct_sense_cluster(w, c, k, threshold) = max(sim_synset_cluster(s, c, k) for s in synsets_of(w)) >= threshold"k" was set to 4 and the threshold was varied in the experiments. By checking for which synset is most similar to the cluster, we can find the WordNet sense that corresponds to the cluster. If more than one cluster corresponds to the same WordNet sense, then only one of them is considered correct. The precision of the system's assignment of a particular word is the percentage of clusters the word is assigned to that are a correct sense. The precision of the system in general is the average precision of all words. The recall of the system's assignment of a particular word is the percentage of correct clusters the word is assigned to out of all the actual correct senses of the word which are found in the corpus. Since the corpus was not sense tagged this is a tricky situation. So the next best thing was to use several clustering methods to extract as many correct sense clusters (as defined above) for the words as possible. The union of all these correct senses are used as the number of different senses each word has in the corpus. The overall recall of the system is the average recall of every word. The precision and recall scores are combined into an F measure:
F = 2 × precision × recall / (precision + recall)In order to do the evaluation, 144 million words were parsed using Minipar in order to extract the grammatical relations between words. The intersection of words which are found in WordNet with those which in the corpus have a pointwise mutual information with all their features greater than 250 was used for evaluation. 13403 words met the criteria and the average number of features per word was 740.8. As was already mentioned, the threshold described in "is_correct_sense_cluster" was varied during the experiment. Here are the results of the F measure using different thresholds with different clustering algorithms. The clustering algorithms were modified to just give the centroids of the clusters and then associated all words which have a similarity greater than 0.18. This is in order to associate the same word with different clusters for each sense. The system described is "CBC" which stands for "Clustering By Committee" which outperformed all the other clustering methods for all thresholds.
Wednesday, December 26, 2012
Summary of research paper "Automatic Retrieval and Clustering of Similar Words" by Dekang Lin
This is a summary of the research paper http://webdocs.cs.ualberta.ca/~lindek/papers/acl98.pdf. This paper describes a way to measure the similarity between words using their contexts. It also describes a way to evaluate the similarities by comparing with existing thesauruses.
The way similarity between two words is calculated is by checking how the words are used in a corpus. To check how a word is used, the grammatical relations between the word and other words in the same sentences it is found are used. For example, these are the grammatical relations for the word "dog" in the sentence "I have a brown dog":
(dog obj-of have): it is an object of the verb "have"
(dog adj-mod brown): it is modified by the adjective "brown"
(dog det a): it takes the determiner "a"
The way the relations are represented is called "dependency triples". By counting these dependency triples for every word in a corpus, the frequencies of each relation can be used to determine if two words are used in the same way and by extension if they mean the same thing. This is called the Distributional Hypothesis which says that words that words that appear in similar contexts are semantically similar. These dependency triples are collected using a broad coverage dependency parser.
In order to describe how these frequencies are used in calculations, the following notation is used: ||w,r,w'|| which is the frequency of the dependency triple (w r w'), that is, that word "w" is related to word "w'" with the relation "r". For example, ||cell, subj-of, absorb|| is the number of times the word "cell" is used as a subject of the word "absorb" in the corpus. Asterisks are used a wild cards, that is, to say that that it doesn't matter what is instead of the asterisks. For example, ||cell, subj-of, *|| is the number of times the word "cell" is used as a subject of some other word, ||cell, *, absorb|| is the number of times the word "cell" is somehow related to the word "absorb", ||*, subj-of, absorb|| is the number of times a word is used as a subject of the word "absorb" and ||*, *, *|| is total number of dependency triples of any kind.
In order to determine how similar two words are based on the frequency of their relations, a formula from another paper by the same author called Using Syntactic Dependency as Local Context to Resolve Word Sense Ambiguity (http://aclweb.org/anthology-new/P/P97/P97-1009.pdf) is used which says that
similarity(A, B) = log P(common(A, B)) / log P(describe(A, B))
This means that the similarity between two words A and B is the amount of information needed to describe what is in common between both words divided by the amount of information needed to describe both words. The less the words have information in common, the less similar they are.
The amount of information needed to describe a word is the sum of the information in each of its dependency triples. The amount of information needed to describe a dependency triple (w, r, w') is -log(actual probability that a randomly selected dependency triple is (w, r, w')) - -log(expected probability that a randomly selected dependency triple is (w, r, w')).
The actual probability of (w, r, w') is ||w, r, w'|| / ||*, *, *||.
The expected probability of (w, r, w') can be estimated using the probability that a randomly selected relation is "r", that a randomly selected word is "w" given that the relation is "r" and that another randomly selected word is "w'" given that the relation is "r". These probabilities are assumed to be independent and are simply multiplied together to find the probability of the whole dependency triple. This probability is P(r)P(w|r)P(w'|r) which equals (||*, r, *|| / ||*, *, *||) × (||w, r, *|| / ||*, r, *||) × (||*, r, w'|| / ||*, r, *||).
So the amount of information needed to describe a dependency triple is I(w,r,w') = log((||w,r,w'|| × ||*,r,*||) / (||w,r,*|| × ||*,r,w'||))
We can now finally define the function which gives the similarity between two words.
Let "T(w)" be a function which when given a word "w" will return the set of pairs "(r, w')" which make I(w,r,w') positive.
The similarity between 2 words, "w1" and "w2" is given by the function sim(w1, w2) = sum(I(w1, r, w) + I(w2, r, w) for (r,w) in (T(w1) ∩ T(w2))) / (sum(I(w1, r, w) for (r,w) in T(w1)) + sum(I(w2, r, w) for (r,w) in T(w2)))
With our function sim(w1, w2) we can now start measuring how similar two words are based on their relations to other words.
A 64 million word corpus was parsed using a broad coverage dependency parser which extracted 56.5 million dependency triples. For each noun, verb, adjective and adverb, the top 200 most similar words were found. The resulting thesaurus of similar words consists of these 200 most similar words for each word sorted in descending order of their similarity together with their similarity, for example:
In order to determine the quality of the similarity measure, its values were compared to existing thesauruses Roget and WordNet in order to see if the similar words determined by the measure are the same as the similar words in the thesauruses. Other similarity measures were also used in order to compare them all together.
These other similarity measures were:
Cosine similarity:
sim_cos(w1, w2) = |T(w1) ∩ T(w2)| / sqrt(|T(w1)| × |T(w2)|)
Hindle similarity which is the same as that proposed in a paper called NOUN CLASSIFICATION FROM PREDICATE ARGUMENT STRUCTURES except that it does not use dependency triples which have negative information (the measure only uses dependency triples whose relation is of subject of and object of):
sim_hindle(w1, w2) = sum(min(I(w1, r, w), I(w2, r, w)) for (r,w) in (T(w1) ∩ T(w2)) if r in {subj-of, obj-of})
and Hindle_r which is the same as Hindle except that all dependency relations are used:
sim_hindle_r(w1, w2) = sum(min(I(w1, r, w), I(w2, r, w)) for (r,w) in (T(w1) ∩ T(w2)))
In order to compare the similarities given by these measures with the thesauruses, the thesauruses needed to have a quantified similarity associated between their similar words. For this reason a similarity measure which gives the similarity between two words according to the thesauruses were developed.
For WordNet, the similarity measures use super classes of the different senses of words. Every word in WordNet belongs to some category of words called a class, here is an example:
Next to each class is the probability that a randomly selected word belongs to that class, which is done by counting the number of words in each class. In order to quantify the similarity between words in WordNet, the most specific class which is common between the two words is used, which in the case of "hill" and "coast" would be "geological formation". By finding the probability of this class for every different sense (meaning) of the two words, converting the probabilities of those classes into information and taking the maximum of the informations, the similarity of the two words would be computed. Formally, this is as follows:
sim_WN(w1, w2) = max(2 log(P(most_specific_common_class(s1, s2))) / (log(P(s1)) + log(P(s2))) for s1 in senses(w1) for s2 in senses(w2))
For Roget, the Roget categories of the words are used. The more words are in common of both categories, the more similar the words are. This is measured as such:
sim_Roget(w1, w2) = 2|RogetCategory(w1) ∩ RogetCategory(w2)| / (|RogetCategory(w1)| + |RogetCategory(w2)|)
Once these measures were defined, the thesauruses were transformed into a form similar to the generated ones. Here is an example:
In order to determine the similarity between each set of similar words, the following formula was used:
entries_similarity(entries1, entries2) = sum(entry1.similarity × entry2.similarity for entry1 in entries1 for entry2 in entries2 if entry1.word == entry2.word) / sqrt(sum(entry1.similarity^2 for entry1 in entries1) × sum(entry2.similarity^2 for entry2 in entries2))
For example, the similarity between the entries for "brief" using "sim" thesaurus and using "sim_WN" thesaurus is:
sum(0.13 × 0.80, 0.05 × 0.80) / sqrt(sum(0.13^2, 0.05^2, 0.05^2, 0.05^2, 0.05^2, 0.05^2, 0.05^2, 0.04^2, 0.04^2, 0.04^2) × sum(0.96^2, 0.84^2, 0.84^2, 0.80^2, 0.80^2, 0.77^2, 0.74^2, 0.74^2, 0.74^2, 0.74^2)) = 0.297215762
The thesauruses were compared and only words which occurred more than 100 times and which were found in all thesauruses were used to evaluate. The average similarity between entries in the thesauruses was calculated.
When compared to WordNet entries:
sim 0.212199
Hindle 0.204179
cosine 0.199402
Roget 0.178397
Hindle_r 0.164716
When compared to Roget entries:
WordNet 0.178397
sim 0.149045
Hindle 0.14663
cosine 0.135697
Hindle_r 0.115489
It can be seen that the "sim" thesuarus is always better than the other generated thesauruses, but WordNet is closer to Roget than the "sim" thesaurus.
The way similarity between two words is calculated is by checking how the words are used in a corpus. To check how a word is used, the grammatical relations between the word and other words in the same sentences it is found are used. For example, these are the grammatical relations for the word "dog" in the sentence "I have a brown dog":
(dog obj-of have): it is an object of the verb "have"
(dog adj-mod brown): it is modified by the adjective "brown"
(dog det a): it takes the determiner "a"
The way the relations are represented is called "dependency triples". By counting these dependency triples for every word in a corpus, the frequencies of each relation can be used to determine if two words are used in the same way and by extension if they mean the same thing. This is called the Distributional Hypothesis which says that words that words that appear in similar contexts are semantically similar. These dependency triples are collected using a broad coverage dependency parser.
In order to describe how these frequencies are used in calculations, the following notation is used: ||w,r,w'|| which is the frequency of the dependency triple (w r w'), that is, that word "w" is related to word "w'" with the relation "r". For example, ||cell, subj-of, absorb|| is the number of times the word "cell" is used as a subject of the word "absorb" in the corpus. Asterisks are used a wild cards, that is, to say that that it doesn't matter what is instead of the asterisks. For example, ||cell, subj-of, *|| is the number of times the word "cell" is used as a subject of some other word, ||cell, *, absorb|| is the number of times the word "cell" is somehow related to the word "absorb", ||*, subj-of, absorb|| is the number of times a word is used as a subject of the word "absorb" and ||*, *, *|| is total number of dependency triples of any kind.
In order to determine how similar two words are based on the frequency of their relations, a formula from another paper by the same author called Using Syntactic Dependency as Local Context to Resolve Word Sense Ambiguity (http://aclweb.org/anthology-new/P/P97/P97-1009.pdf) is used which says that
similarity(A, B) = log P(common(A, B)) / log P(describe(A, B))
This means that the similarity between two words A and B is the amount of information needed to describe what is in common between both words divided by the amount of information needed to describe both words. The less the words have information in common, the less similar they are.
The amount of information needed to describe a word is the sum of the information in each of its dependency triples. The amount of information needed to describe a dependency triple (w, r, w') is -log(actual probability that a randomly selected dependency triple is (w, r, w')) - -log(expected probability that a randomly selected dependency triple is (w, r, w')).
The actual probability of (w, r, w') is ||w, r, w'|| / ||*, *, *||.
The expected probability of (w, r, w') can be estimated using the probability that a randomly selected relation is "r", that a randomly selected word is "w" given that the relation is "r" and that another randomly selected word is "w'" given that the relation is "r". These probabilities are assumed to be independent and are simply multiplied together to find the probability of the whole dependency triple. This probability is P(r)P(w|r)P(w'|r) which equals (||*, r, *|| / ||*, *, *||) × (||w, r, *|| / ||*, r, *||) × (||*, r, w'|| / ||*, r, *||).
So the amount of information needed to describe a dependency triple is I(w,r,w') = log((||w,r,w'|| × ||*,r,*||) / (||w,r,*|| × ||*,r,w'||))
We can now finally define the function which gives the similarity between two words.
Let "T(w)" be a function which when given a word "w" will return the set of pairs "(r, w')" which make I(w,r,w') positive.
The similarity between 2 words, "w1" and "w2" is given by the function sim(w1, w2) = sum(I(w1, r, w) + I(w2, r, w) for (r,w) in (T(w1) ∩ T(w2))) / (sum(I(w1, r, w) for (r,w) in T(w1)) + sum(I(w2, r, w) for (r,w) in T(w2)))
With our function sim(w1, w2) we can now start measuring how similar two words are based on their relations to other words.
A 64 million word corpus was parsed using a broad coverage dependency parser which extracted 56.5 million dependency triples. For each noun, verb, adjective and adverb, the top 200 most similar words were found. The resulting thesaurus of similar words consists of these 200 most similar words for each word sorted in descending order of their similarity together with their similarity, for example:
brief (noun): affidavit 0.13, petition 0.05, memorandum 0.05, motion 0.05, lawsuit 0.05, deposition 0.05, slight 0.05, prospectus 0.04, document 0.04, paper 0.04 ...
In order to determine the quality of the similarity measure, its values were compared to existing thesauruses Roget and WordNet in order to see if the similar words determined by the measure are the same as the similar words in the thesauruses. Other similarity measures were also used in order to compare them all together.
These other similarity measures were:
Cosine similarity:
sim_cos(w1, w2) = |T(w1) ∩ T(w2)| / sqrt(|T(w1)| × |T(w2)|)
Hindle similarity which is the same as that proposed in a paper called NOUN CLASSIFICATION FROM PREDICATE ARGUMENT STRUCTURES except that it does not use dependency triples which have negative information (the measure only uses dependency triples whose relation is of subject of and object of):
sim_hindle(w1, w2) = sum(min(I(w1, r, w), I(w2, r, w)) for (r,w) in (T(w1) ∩ T(w2)) if r in {subj-of, obj-of})
and Hindle_r which is the same as Hindle except that all dependency relations are used:
sim_hindle_r(w1, w2) = sum(min(I(w1, r, w), I(w2, r, w)) for (r,w) in (T(w1) ∩ T(w2)))
In order to compare the similarities given by these measures with the thesauruses, the thesauruses needed to have a quantified similarity associated between their similar words. For this reason a similarity measure which gives the similarity between two words according to the thesauruses were developed.
For WordNet, the similarity measures use super classes of the different senses of words. Every word in WordNet belongs to some category of words called a class, here is an example:
Next to each class is the probability that a randomly selected word belongs to that class, which is done by counting the number of words in each class. In order to quantify the similarity between words in WordNet, the most specific class which is common between the two words is used, which in the case of "hill" and "coast" would be "geological formation". By finding the probability of this class for every different sense (meaning) of the two words, converting the probabilities of those classes into information and taking the maximum of the informations, the similarity of the two words would be computed. Formally, this is as follows:
sim_WN(w1, w2) = max(2 log(P(most_specific_common_class(s1, s2))) / (log(P(s1)) + log(P(s2))) for s1 in senses(w1) for s2 in senses(w2))
For Roget, the Roget categories of the words are used. The more words are in common of both categories, the more similar the words are. This is measured as such:
sim_Roget(w1, w2) = 2|RogetCategory(w1) ∩ RogetCategory(w2)| / (|RogetCategory(w1)| + |RogetCategory(w2)|)
Once these measures were defined, the thesauruses were transformed into a form similar to the generated ones. Here is an example:
brief (noun) according to "sim" thesaurus: affidavit 0.13, petition 0.05, memorandum 0.05, motion 0.05, lawsuit 0.05, deposition 0.05, slight 0.05, prospectus 0.04, document 0.04, paper 0.04 brief (noun) according to "sim_WN" thesaurus: outline 0.96, instrument 0.84, summary 0.84, affidavit 0.80, deposition 0.80, law 0.77, survey 0.74, sketch 0.74, resume 0.74, argument 0.74 brief (noun) according to "sim_Roget" thesaurus: recital 0.77, saga 0.77, autobiography 0.77, anecdote 0.77, novel 0.77, novelist 0.77, tradition 0.70, historian 0.70, tale 0.64
In order to determine the similarity between each set of similar words, the following formula was used:
entries_similarity(entries1, entries2) = sum(entry1.similarity × entry2.similarity for entry1 in entries1 for entry2 in entries2 if entry1.word == entry2.word) / sqrt(sum(entry1.similarity^2 for entry1 in entries1) × sum(entry2.similarity^2 for entry2 in entries2))
For example, the similarity between the entries for "brief" using "sim" thesaurus and using "sim_WN" thesaurus is:
sum(0.13 × 0.80, 0.05 × 0.80) / sqrt(sum(0.13^2, 0.05^2, 0.05^2, 0.05^2, 0.05^2, 0.05^2, 0.05^2, 0.04^2, 0.04^2, 0.04^2) × sum(0.96^2, 0.84^2, 0.84^2, 0.80^2, 0.80^2, 0.77^2, 0.74^2, 0.74^2, 0.74^2, 0.74^2)) = 0.297215762
The thesauruses were compared and only words which occurred more than 100 times and which were found in all thesauruses were used to evaluate. The average similarity between entries in the thesauruses was calculated.
When compared to WordNet entries:
sim 0.212199
Hindle 0.204179
cosine 0.199402
Roget 0.178397
Hindle_r 0.164716
When compared to Roget entries:
WordNet 0.178397
sim 0.149045
Hindle 0.14663
cosine 0.135697
Hindle_r 0.115489
It can be seen that the "sim" thesuarus is always better than the other generated thesauruses, but WordNet is closer to Roget than the "sim" thesaurus.
Monday, October 8, 2012
Summary of research paper "Putting it Simply: a Context-Aware Approach to Lexical Simplification" by Or Biran, Samuel Brody and Nomie Elhadad
This is a summary of the research paper www.aclweb.org/anthology/P11-2087. This paper describes a way to lexically simplify text using unsupervised methods. Lexical simplification is the process of replacing difficult words with simpler words which approximately mean that same thing in context. The method described in this papers does not require a parallel corpus and instead only requires text from complex and simplified documents in order to compare the word counts in each.
The first thing that was done was to download Wikipedia and Simple English Wikipedia articles (3,266,245 articles and 60,100 articles respectively) the following preprocessing tasks were performed on them:
The last 3 steps were carried out using the Stanford NLP Package.
The system consists of first learning simplification rules (finding pairs of difficult/simpler words) and then applying them by finding which is the best word to replace a difficult word. We shall now look at each of these stages.
To learn the simplification rules, a 10-token window (10 tokens on each side) which crosses sentence boundaries (confirmed through private communication with the authors) was used to construct a context vector of each token (excluding stop words, numbers and punctuation) in the English Wikipedia corpus. All numbers were represented with an artificial token such as "<number>" which allows you to count all instances of any number next to a token. Only frequencies greater than 2 were kept in the context vector.
In order to create a list of possible word substitutions, first a Cartesian product of all words in the English Wikipedia corpus was created which was then filtered in the following ways in order to keep only word pairs which are simplification replacements:
Now we have the substitution list. In order to make the list more practical, each word pair's similarity in meaning is computed by using cosine similarity on their context vectors. This allows the choosing of the most similar simplified word to replace a difficult word with.
Also each word pair is replaced with a list of all morphological variants of the two words which are consistent with each other. All nouns are replaced with plural and singular versions (so that if the word to replace is in plural, than the simplified word will also be in plural) and all verbs are replaced with all variants of tenses and persons. The variants keep the same similarity score of the original pairs.
In order to simplify a sentence (which must have at least 7 content words), every word in the sentence, which is not inside quotation marks or parenthesis, is checked for possible simplification.
For every word in the sentence, its context vector inside the sentence is computed just as described above. Now the word is checked for whether it is used precisely because it is difficult, for example when defining a difficult word. An example given in the paper is "The history of the Han ethnic group is closely tied to that of China" in which the word "Han" should not be replaced with "Chinese" as that would make the sentence lose its meaning. In order to detect these cases, the word is checked if it is used in a way that it is commonly used. This is done by checking if the cosine similarity of the word's context vector in the corpus with the word's context vector in the sentence is greater than 0.1 and if so then the word is not simplified.
Next, for every word pair in the substitution list whose first word is the word to simplify, only those whose second word is not in the sentence already are considered. With the remaining substitution candidates, the simpler word is checked for whether it has the same sense as the word it will replace since the same word might have different meanings. To do this, a common context vector is created for both the difficult and simple word. This is done by comparing the value for each word in the corpus context vectors of both words and keeping only the smallest one. This would be the common context vector. Now the cosine similarity of the common context vector with the difficult word's context vector in the sentence is checked for whether it is less than 0.01 and if so then the simple word is not used. Out of all the remaining possible simple words to replace with, the one with the highest similarity is used.
In order to evaluate the simplification system, a baseline was used which just replaces words with their most frequent synonym (assumed to be simpler). Test sentences were found for simplification by searching through the English Wikipedia corpus for all sentences that the system determined that only one word can be simplified, that this word had a more frequent synonym (to allow the baseline to simplify also) and that the replaced word by the system and the baseline were different. Out of these, the sentences were grouped according to the substitution pair that was used to simplify them and then only a random sentence from each group was used in the evaluation. 65 such sentences were found and these were simplified both by the system and by the baseline, resulting in 130 complex/simplified sentences.
Since the groups from which a random sentence was selected were of different sizes, different substitution pairs are applied more frequently than others. In order to see how the frequency of use of the pairs affects the performance of the system, the sentences were grouped into 3 "frequency bands" of roughly equal frequency of use (size of group): 46 in the "high" band, 44 in the "med" band and 40 in the "low".
In order to be evaluated, the complex/simplified sentence pairs (both system and baseline) were given to 3 human judges (native English speakers who are not the authors) who would determine the grammaticality of the simplified sentence (is it still grammatical?) as "bad", "ok" or "good", the meaning of the simplified sentence (does it still mean the same thing?) as "yes" or "no" and the simplification of the simplified sentence (is it simpler?) as "yes" or "no". No two annotators were given both a system and baseline complex/simplified pair and a small portion of the pairs were given to more than one judge in order to check if they agree with each other.
Here is a table showing all the results. Under grammaticality, the percentage in brackets is the percentage of "ok" ratings and the percentage outside the brackets is the percentage of "good" ratings.
Grammaticality is the same because the form of the word is determined using a morphological engine rather than using context. Meaning preservation is affected by the low frequency band because there are less examples to create a quality context vector in order to determine when a particular word can be used in a particular context. Simplification consistently outperforms the baseline.
The first thing that was done was to download Wikipedia and Simple English Wikipedia articles (3,266,245 articles and 60,100 articles respectively) the following preprocessing tasks were performed on them:
- Comments were removed
- HTML tags were removed
- Links were removed
- Tables and figures were removed (with associated text)
- Text was tokenized
- All word were turned to lower case
- Sentences were split
The last 3 steps were carried out using the Stanford NLP Package.
The system consists of first learning simplification rules (finding pairs of difficult/simpler words) and then applying them by finding which is the best word to replace a difficult word. We shall now look at each of these stages.
To learn the simplification rules, a 10-token window (10 tokens on each side) which crosses sentence boundaries (confirmed through private communication with the authors) was used to construct a context vector of each token (excluding stop words, numbers and punctuation) in the English Wikipedia corpus. All numbers were represented with an artificial token such as "<number>" which allows you to count all instances of any number next to a token. Only frequencies greater than 2 were kept in the context vector.
In order to create a list of possible word substitutions, first a Cartesian product of all words in the English Wikipedia corpus was created which was then filtered in the following ways in order to keep only word pairs which are simplification replacements:
- All morphological variants where removed by checking their lemma with MorphAdorner.
- In order to find more morphological variants which are not handled by MorphAdorner, all words were one is a prefix of the other followed by the suffixes "s", "es", "ed", "ly", "er", "ing" were also removed.
- WordNet was used to remove all word pairs where the first word is not a synonym or hypernym of each second.
- In order to keep only word pairs where the second word is simpler than the first, lexical complexity is measured as the frequency of the word in the English Wikipedia corpus is divided by the frequency of the word in the Simple English Wikipedia corpus and the ratio is multiplied by the length of the word. The reasoning is that the more often a word appears in the Simple English Wikipedia than it does in English Wikipedia and the shorter the word is, the simpler it is and so the smaller it's complexity measure. All word pairs where the second word is harder than the first are removed.
Now we have the substitution list. In order to make the list more practical, each word pair's similarity in meaning is computed by using cosine similarity on their context vectors. This allows the choosing of the most similar simplified word to replace a difficult word with.
Also each word pair is replaced with a list of all morphological variants of the two words which are consistent with each other. All nouns are replaced with plural and singular versions (so that if the word to replace is in plural, than the simplified word will also be in plural) and all verbs are replaced with all variants of tenses and persons. The variants keep the same similarity score of the original pairs.
In order to simplify a sentence (which must have at least 7 content words), every word in the sentence, which is not inside quotation marks or parenthesis, is checked for possible simplification.
For every word in the sentence, its context vector inside the sentence is computed just as described above. Now the word is checked for whether it is used precisely because it is difficult, for example when defining a difficult word. An example given in the paper is "The history of the Han ethnic group is closely tied to that of China" in which the word "Han" should not be replaced with "Chinese" as that would make the sentence lose its meaning. In order to detect these cases, the word is checked if it is used in a way that it is commonly used. This is done by checking if the cosine similarity of the word's context vector in the corpus with the word's context vector in the sentence is greater than 0.1 and if so then the word is not simplified.
Next, for every word pair in the substitution list whose first word is the word to simplify, only those whose second word is not in the sentence already are considered. With the remaining substitution candidates, the simpler word is checked for whether it has the same sense as the word it will replace since the same word might have different meanings. To do this, a common context vector is created for both the difficult and simple word. This is done by comparing the value for each word in the corpus context vectors of both words and keeping only the smallest one. This would be the common context vector. Now the cosine similarity of the common context vector with the difficult word's context vector in the sentence is checked for whether it is less than 0.01 and if so then the simple word is not used. Out of all the remaining possible simple words to replace with, the one with the highest similarity is used.
In order to evaluate the simplification system, a baseline was used which just replaces words with their most frequent synonym (assumed to be simpler). Test sentences were found for simplification by searching through the English Wikipedia corpus for all sentences that the system determined that only one word can be simplified, that this word had a more frequent synonym (to allow the baseline to simplify also) and that the replaced word by the system and the baseline were different. Out of these, the sentences were grouped according to the substitution pair that was used to simplify them and then only a random sentence from each group was used in the evaluation. 65 such sentences were found and these were simplified both by the system and by the baseline, resulting in 130 complex/simplified sentences.
Since the groups from which a random sentence was selected were of different sizes, different substitution pairs are applied more frequently than others. In order to see how the frequency of use of the pairs affects the performance of the system, the sentences were grouped into 3 "frequency bands" of roughly equal frequency of use (size of group): 46 in the "high" band, 44 in the "med" band and 40 in the "low".
In order to be evaluated, the complex/simplified sentence pairs (both system and baseline) were given to 3 human judges (native English speakers who are not the authors) who would determine the grammaticality of the simplified sentence (is it still grammatical?) as "bad", "ok" or "good", the meaning of the simplified sentence (does it still mean the same thing?) as "yes" or "no" and the simplification of the simplified sentence (is it simpler?) as "yes" or "no". No two annotators were given both a system and baseline complex/simplified pair and a small portion of the pairs were given to more than one judge in order to check if they agree with each other.
Here is a table showing all the results. Under grammaticality, the percentage in brackets is the percentage of "ok" ratings and the percentage outside the brackets is the percentage of "good" ratings.
| Type | Frequency | Grammaticality | Meaning | Simplification |
|---|---|---|---|---|
| Baseline | High | 63.33(+20)% | 46.67% | 50% |
| System | High | 76.67(+6.66)% | 63.33% | 73.33% |
| Baseline | Med | 75(+7.14)% | 67.86% | 42.86% |
| System | Med | 72.41(+17.25)% | 75.86% | 82.76% |
| Baseline | Low | 73.08(+11.54)% | 53.85% | 46.15% |
| System | Low | 85.19(+0)% | 48.15% | 70.37% |
Grammaticality is the same because the form of the word is determined using a morphological engine rather than using context. Meaning preservation is affected by the low frequency band because there are less examples to create a quality context vector in order to determine when a particular word can be used in a particular context. Simplification consistently outperforms the baseline.
Tuesday, June 26, 2012
Summary of research paper "Simple EnglishWikipedia: A New Text Simplification Task" by William Coster and David Kauchak
This is a summary of the research paper http://www.aclweb.org/anthology-new/P/P11/P11-2117.pdf. This paper describes a way to automatically create a parallel corpus that pairs sentences with a simpler version of the sentences which will be useful for training text simplification systems. The sentences for the corpus come from articles in Wikipedia and Simple English Wikipedia. Simple English Wikipedia is a version of Wikipedia which is edited with the aim of being understandable by children and English learners by encouraging the use of simple vocabulary and grammar. By pairing up equivalent sentences in Wikipedia and Simple English Wikipedia, it was possible to build a 137,000 sentence parallel corpus.
In order to build such a corpus, both Wikipedia sites were downloaded, the articles were paired by title, all pairs that contained an unusable article (e.g. stubs, disambiguation pages, etc.) were removed, the equivalent paragraphs in the article pairs were paired up and finally the equivalent sentences in the paragraph pairs were paired up.
To align paragraphs in the article pairs, where a single paragraph in Simple English Wikipedia could correspond to multiple paragraphs in Wikipedia but not the other way round, the words in each paragraph from the Simple English Wikipedia article were used as a set of keywords to search for all corresponding paragraphs in the Wikipedia article. This was done by using TF-IDF and keeping only those paragraphs which resulted in a vector with cosine similarity to the Simple English Wikipedia paragraph of 0.5 or more. In this way, each paragraph in the Simple English Wikipedia article is paired up with a list of paragraphs in the Wikipedia article which are similar to it.
Once the paragraph pairs were found in each article pair, the next step was to pair up the sentences in the paragraph pairs such that in each pair you get a Wikipedia sentence and its simplified counterpart from Simple English Wikipedia. Such a pairing of sentences is called an "alignment". This was less simple than how the paragraphs were paired because now there could be multiple sentences in Simple English Wikipedia that correspond to multiple sentences in Wikipedia. Instead, the sentences in the paragraph pairs are paired up in many different ways and the alignment which gives the maximum sum of similarities in each sentence pair was used. The similarity of two sentences in a pair is found by using TF-IDF with cosine similarity. The paragraph pairing was important in order to limit the number of different ways to attempt to align the sentences.
Following some clarifications via email with the author, here is how the sentence alignment algorithm works:
Let "n" be the number of Wikipedia sentences in a paragraph pair
Let "m" be the number of Simple English Wikipedia sentences in a paragraph pair
Let "sim(i,j)" be a function which measures the similarity between the "i"th Wikipedia sentence and the "j"th Simple English Wikipedia sentence (using TF-IDF with cosine similarity) in a paragraph pair
I shall now introduce a new function "align(n,m)" which is not mentioned in the paper but which will help explain the whole sentence alignment concept.
The function "align(n,m)" gives the best sentence alignment such that the sum of the similarity between each sentence pair is maximized. In order to align the sentences, 6 operations are successively applied to the sentences in the paired paragraphs. The operations are:
These operations are applied successively using dynamic programming in order to find the alignment with the maximum sum of similarities.
We shall first see the function "a(n,m)" which calculates this maximal similarity and then we shall see "align(n,m)". "a(n,m)" will also be applying the operations using dynamic programming, but it will only be calculating the sum of the similarities of the sentence pairs rather then the actual pairs. Having initial arguments being the number of sentences in each paragraph in the paragraph pair, "a(n,m)" will recursively call itself on less and less sentences until it reaches a base case of having no sentences to align. In accordance with the paper, the "i"th sentence is not 0 based like in arrays but 1 based. So the first sentence is in position 1, the second is in position 2, etc.
This is "a(i,j)" in Python without using dynamic programming (for simplicity):
"skip_penalty" is a constant (the authors set it to 0.0001) which is used to reduce the total similarity every time a sentence is skipped. This is to discourage skipping too many sentences.
Now "align(n,m)" would be very similar to "a(n,m)". Every "sim(x,y)" there is in "a(n,m)" represents a pairing of the "x"th Wikipedia sentence with the "y"th Simple English Wikipedia sentence. So in "align(n,m)", every time we compute "sim(x,y)" we would add the pair "(x,y)" to our alignment. We still need to know what the maximum similarity of the alignment will be after applying each operation so "align(n,m)" needs to return both the similarity and the alignment.
This is "align(i,j)" in Python without using dynamic programming (for simplicity):
And here is the same algorithm using dynamic programming:
This function will return the best alignment and its total similarity. The alignment will be a list of sentence position pairs and not the sentence pairs themselves.
Once the sentences in each paragraph were aligned, the sentence pairs were then filtered such that if any sentence pairs were less similar than 0.5 then they would be discarded. The filtering went from 10,000 article pairs to 75,000 paragraph pairs to 137,000 sentence pairs. Out of a sample of 100 sentence pairs, human judges determined that 91 of them were correct sentence simplifications. They were also tested on a phrase based translation system called Moses which simplified test sentences with statistically significant improvement.
The final parallel corpus is available at http://www.cs.pomona.edu/~dkauchak/simplification/.
In order to build such a corpus, both Wikipedia sites were downloaded, the articles were paired by title, all pairs that contained an unusable article (e.g. stubs, disambiguation pages, etc.) were removed, the equivalent paragraphs in the article pairs were paired up and finally the equivalent sentences in the paragraph pairs were paired up.
To align paragraphs in the article pairs, where a single paragraph in Simple English Wikipedia could correspond to multiple paragraphs in Wikipedia but not the other way round, the words in each paragraph from the Simple English Wikipedia article were used as a set of keywords to search for all corresponding paragraphs in the Wikipedia article. This was done by using TF-IDF and keeping only those paragraphs which resulted in a vector with cosine similarity to the Simple English Wikipedia paragraph of 0.5 or more. In this way, each paragraph in the Simple English Wikipedia article is paired up with a list of paragraphs in the Wikipedia article which are similar to it.
Once the paragraph pairs were found in each article pair, the next step was to pair up the sentences in the paragraph pairs such that in each pair you get a Wikipedia sentence and its simplified counterpart from Simple English Wikipedia. Such a pairing of sentences is called an "alignment". This was less simple than how the paragraphs were paired because now there could be multiple sentences in Simple English Wikipedia that correspond to multiple sentences in Wikipedia. Instead, the sentences in the paragraph pairs are paired up in many different ways and the alignment which gives the maximum sum of similarities in each sentence pair was used. The similarity of two sentences in a pair is found by using TF-IDF with cosine similarity. The paragraph pairing was important in order to limit the number of different ways to attempt to align the sentences.
Following some clarifications via email with the author, here is how the sentence alignment algorithm works:
Let "n" be the number of Wikipedia sentences in a paragraph pair
Let "m" be the number of Simple English Wikipedia sentences in a paragraph pair
Let "sim(i,j)" be a function which measures the similarity between the "i"th Wikipedia sentence and the "j"th Simple English Wikipedia sentence (using TF-IDF with cosine similarity) in a paragraph pair
I shall now introduce a new function "align(n,m)" which is not mentioned in the paper but which will help explain the whole sentence alignment concept.
The function "align(n,m)" gives the best sentence alignment such that the sum of the similarity between each sentence pair is maximized. In order to align the sentences, 6 operations are successively applied to the sentences in the paired paragraphs. The operations are:
- Skip the next sentence in the Wikipedia paragraph (it does not correspond to any of the sentences in the Simple English Wikipedia paragraph)
- Skip the next sentence in the Simple English Wikipedia paragraph (it does not correspond to any of the sentences in the Wikipedia paragraph)
- Pairing the next Wikipedia sentence to the next Simple English Wikipedia sentence
- Pairing the next Wikipedia sentence to the next two Simple English Wikipedia sentences
- Pairing the next two Wikipedia sentences to the next Simple English Wikipedia sentence
- Pairing the next two Wikipedia sentences to the next two Simple English Wikipedia sentences crossed up (for example, if the Wikipedia sentences are [a, b] and the Simple English Wikipedia sentences are [x, y] then the pairing would be [(a,y), (b,x)])
These operations are applied successively using dynamic programming in order to find the alignment with the maximum sum of similarities.
We shall first see the function "a(n,m)" which calculates this maximal similarity and then we shall see "align(n,m)". "a(n,m)" will also be applying the operations using dynamic programming, but it will only be calculating the sum of the similarities of the sentence pairs rather then the actual pairs. Having initial arguments being the number of sentences in each paragraph in the paragraph pair, "a(n,m)" will recursively call itself on less and less sentences until it reaches a base case of having no sentences to align. In accordance with the paper, the "i"th sentence is not 0 based like in arrays but 1 based. So the first sentence is in position 1, the second is in position 2, etc.
This is "a(i,j)" in Python without using dynamic programming (for simplicity):
def a(i, j):
if i == 0 or j == 0: #Base case: if there are no more sentences to align in the paragraphs then the similarity is 0
return 0
else: #Recursive case: if there are sentences to align then check what the maximum similarity achieved will be after applying each operation and return the maximum of the similarities
alternatives = []
#Max similarity after skipping next Simple English Wikipedia sentence
alternatives.append(a(i, j-1) - skip_penalty)
#Max similarity after skippin next Wikipedia sentence
alternatives.append(a(i-1, j) - skip_penalty)
#Max similarity after pairing next Wikipedia sentence with next Simple English Wikipedia sentence
alternatives.append(a(i-1, j-1) + sim(i, j))
if j >= 2: #If there are more than one Simple English Wikipedia sentences then try pairing up two such sentences
#Max similarity after pairing next Wikipedia sentence with next two Simple English Wikipedia sentences
alternatives.append(a(i-1, j-2) + sim(i, j-1) + sim(i, j))
if i >= 2: #If there are more than one Wikipedia sentences then try pairing up two such sentences
#Max similarity after pairing next two Wikipedia sentences with next Simple English Wikipedia sentence
alternatives.append(a(i-2, j-1) + sim(i-1, j) + sim(i, j))
if i >= 2 and j >= 2: #If there are more than one sentences in both paragraphs then try pairing up two of each
#Max similarity after pairing next two Wikipedia sentences with next two Simple English Wikipedia sentences crossed up
alternatives.append(a(i-2, j-2) + sim(i-1, j) + sim(i, j-1))
return max(alternatives) #Return the maximum of the similarities
"skip_penalty" is a constant (the authors set it to 0.0001) which is used to reduce the total similarity every time a sentence is skipped. This is to discourage skipping too many sentences.
Now "align(n,m)" would be very similar to "a(n,m)". Every "sim(x,y)" there is in "a(n,m)" represents a pairing of the "x"th Wikipedia sentence with the "y"th Simple English Wikipedia sentence. So in "align(n,m)", every time we compute "sim(x,y)" we would add the pair "(x,y)" to our alignment. We still need to know what the maximum similarity of the alignment will be after applying each operation so "align(n,m)" needs to return both the similarity and the alignment.
This is "align(i,j)" in Python without using dynamic programming (for simplicity):
def align(i, j):
if i == 0 or j == 0: #Base case: if there are no more sentences to align in the paragraphs then the similarity is 0
return (0, [])
else: #Recursive case: if there are sentences to align then check what the maximum similarity achieved will be after applying each operation and return the maximum of the similarities
alternatives = []
#Best alignment after skipping next Simple English Wikipedia sentence
(similarity, alignment) = align(i, j-1)
alternatives.append((similarity - skip_penalty, alignment))
#Best alignment after skippin next Wikipedia sentence
(similarity, alignment) = align(i-1, j)
alternatives.append((similarity - skip_penalty, alignment))
#Best alignment after pairing next Wikipedia sentence with next Simple English Wikipedia sentence
(similarity, alignment) = align(i-1, j-1)
alternatives.append((similarity + sim(i, j), alignment + [(i, j)]))
if j >= 2: #If there are more than one Simple English Wikipedia sentences then try pairing up two such sentences
#Best alignment after pairing next Wikipedia sentence with next two Simple English Wikipedia sentences
(similarity, alignment) = align(i-1, j-2)
alternatives.append((similarity + sim(i, j-1) + sim(i, j), alignment + [(i, j-1), (i, j)]))
if i >= 2: #If there are more than one Wikipedia sentences then try pairing up two such sentences
#Best alignment after pairing next two Wikipedia sentences with next Simple English Wikipedia sentence
(similarity, alignment) = align(i-2, j-1)
alternatives.append((similarity + sim(i-1, j) + sim(i, j), alignment + [(i-1, j), (i, j)]))
if i >= 2 and j >= 2: #If there are more than one sentences in both paragraphs then try pairing up two of each
#Best alignment after pairing next two Wikipedia sentences with next two Simple English Wikipedia sentences crossed up
(similarity, alignment) = align(i-2, j-2)
alternatives.append((similarity + sim(i-1, j) + sim(i, j-1), alignment + [(i-1, j), (i, j-1)]))
return max(alternatives, key=lambda p:p[0]) #Return the maximum of the similarities (the similarity is the first element of each similarity/alignment pair)
And here is the same algorithm using dynamic programming:
def align(i, j):
memo = dict()
for x in range(0, i+1):
memo[(x, 0)] = (0.0, [])
for y in range(0, j+1):
memo[(0, y)] = (0.0, [])
for y in range(1, j+1):
for x in range(1, i+1):
alternatives = []
#Best alignment after skipping next Simple English Wikipedia sentence
(similarity, alignment) = memo[(x, y-1)]
alternatives.append((similarity - skip_penalty, alignment))
#Best alignment after skippin next Wikipedia sentence
(similarity, alignment) = memo[(x-1, y)]
alternatives.append((similarity - skip_penalty, alignment))
#Best alignment after pairing next Wikipedia sentence with next Simple English Wikipedia sentence
(similarity, alignment) = memo[(x-1, y-1)]
alternatives.append((similarity + sim(x, y), alignment + [(x, y)]))
if y >= 2: #If there are more than one Simple English Wikipedia sentences then try pairing up two such sentences
#Best alignment after pairing next Wikipedia sentence with next two Simple English Wikipedia sentences
(similarity, alignment) = memo[(x-1, y-2)]
alternatives.append((similarity + sim(x, y-1) + sim(x, y), alignment + [(x, y-1), (x, y)]))
if x >= 2: #If there are more than one Wikipedia sentences then try pairing up two such sentences
#Best alignment after pairing next two Wikipedia sentences with next Simple English Wikipedia sentence
(similarity, alignment) = memo[(x-2, y-1)]
alternatives.append((similarity + sim(x-1, y) + sim(x, y), alignment + [(x-1, y), (x, y)]))
if x >= 2 and y >= 2: #If there are more than one sentences in both paragraphs then try pairing up two of each
#Best alignment after pairing next two Wikipedia sentences with next two Simple English Wikipedia sentences crossed up
(similarity, alignment) = memo[(x-2, y-2)]
alternatives.append((similarity + sim(x-1, y) + sim(x, y-1), alignment + [(x-1, y), (x, y-1)]))
memo[(x,y)] = max(alternatives, key=lambda p:p[0]) #Return the maximum of the similarities (the similarity is the first element of each similarity/alignment pair)
return memo[(i,j)]
This function will return the best alignment and its total similarity. The alignment will be a list of sentence position pairs and not the sentence pairs themselves.
Once the sentences in each paragraph were aligned, the sentence pairs were then filtered such that if any sentence pairs were less similar than 0.5 then they would be discarded. The filtering went from 10,000 article pairs to 75,000 paragraph pairs to 137,000 sentence pairs. Out of a sample of 100 sentence pairs, human judges determined that 91 of them were correct sentence simplifications. They were also tested on a phrase based translation system called Moses which simplified test sentences with statistically significant improvement.
The final parallel corpus is available at http://www.cs.pomona.edu/~dkauchak/simplification/.
Saturday, June 23, 2012
Summary of research paper "Readability Assessment for Text Simplification" by Sandra Aluisio, Lucia Specia, Caroline Gasperin and Carolina Scarton
This is a summary of the research paper http://aclweb.org/anthology-new/W/W10/W10-1001.pdf. This paper is about a program which classifies text into one of three difficulty of reading levels: "rudimentary", "basic" and "advanced". These difficulty levels are defined by INAF (Portuguese document at http://www.ibope.com.br/ipm/relatorios/relatorio_inaf_2009.pdf), the National Indicator of Functional Literacy. The aim is to use this program to assist authors to detect parts of their writing which can be simplified. The program is designed to work with Portuguese rather than English.
The following list of features is extracted from the Portuguese text to assess using various tools and resources described in the paper (copied directly from the paper):
The features from 1 to 42 are the "Coh-Metix PORT" feature group and were derived from the Coh-Metrix-PORT tool, which is a Portuguese adaptation of the Coh-Metrix.
The features from 43 to 49 are the "Syntactic" feature group and were added to analyse syntactic constructions which are useful for automatic simplification.
The features from 50 to 59 are the "Language model" feature group and are derived by comparing n-grams in the input text to n-gram frequencies in the language (Portuguese) as well as their perplexity and scores for any words which are not listed in the system's vocabulary.
The features from 1 to 3 and 9 to 11 are also called the "Basic" feature group because they require no linguistic knowledge. Feature 12 is also put into a feature group on its own called "Flesch".
Experiments were performed to check if it is possible to use machine learning techniques to learn to detect the INAF difficulty of reading levels and to discover which features are best to use for complexity detection.
Three types of machine learning algorithms in Weka were evaluated:
Manually simplified corpora were used as training data for the algorithms. The corpora were simplified into each of the difficulty levels. Using these simplified corpora it was possible to check if the system could predict that the original corpora are of "advanced" difficulty level, the lightly simplified corpora are of "basic" difficulty level and the heavily simplified corpora are of "rudimentary" difficulty level.
In order to determine the importance of each feature described, the absolute Pearson correlation between each feature of each corpora and how well it predicts the corpora's difficulty level is computed. The results for the best features below are copied from the paper (1=highly correlated, 0=not correlated):
In order to determine which machine learning algorithm is better at classifying the corpora into correct difficulty levels using the features mentioned earlier, the Pearson correlation with true score was used on how the corpora were classified. The experiments were also run using the sub-groups of features which were mentioned to see how important each group was. Here are the results, summarized from the paper:
Standard classification
Ordinal classification
Regression
It is clear that it is better to use all the features together than any sub-group of them, but the syntactic features, followed by the Coh-Metrix-PORT features are the most useful feature groups and the language model feature group was the worst.
The simple classification algorithm was chosen as the best because although it is the simplest algorithm, its results are comparable to the other algorithms' results.
The following list of features is extracted from the Portuguese text to assess using various tools and resources described in the paper (copied directly from the paper):
- Number of words
- Number of sentences
- Number of paragraphs
- Number of verbs
- Number of nouns
- Number of adjectives
- Number of adverbs
- Number of pronouns
- Average number of words per sentence
- Average number of sentences per paragraph
- Average number of syllables per word
- Flesch index for Portuguese
- Incidence of content words
- Incidence of functional words
- Raw Frequency of content words
- Minimal frequency of content words
- Average number of verb hypernyms
- Incidence of NPs
- Number of NP modifiers
- Number of words before the main verb
- Number of high level constituents
- Number of personal pronouns
- Type-token ratio
- Pronoun-NP ratio
- Number of “e” (and)
- Number of “ou” (or)
- Number of “se” (if)
- Number of negations
- Number of logic operators
- Number of connectives
- Number of positive additive connectives
- Number of negative additive connectives
- Number of positive temporal connectives
- Number of negative temporal connectives
- Number of positive causal connectives
- Number of negative causal connectives
- Number of positive logic connectives
- Number of negative logic connectives
- Verb ambiguity ratio
- Noun ambiguity ratio
- Adverb ambiguity ratio
- Adjective ambiguity ratio
- Incidence of clauses
- Incidence of adverbial phrases
- Incidence of apposition
- Incidence of passive voice
- Incidence of relative clauses
- Incidence of coordination
- Incidence of subordination
- Out-of-vocabulary words
- LM probability of unigrams
- LM perplexity of unigrams
- LM perplexity of unigrams, without line break
- LM probability of bigrams
- LM perplexity of bigrams
- LM perplexity of bigrams, without line break
- LM probability of trigrams
- LM perplexity of trigrams
- LM perplexity of trigrams, without line break
The features from 1 to 42 are the "Coh-Metix PORT" feature group and were derived from the Coh-Metrix-PORT tool, which is a Portuguese adaptation of the Coh-Metrix.
The features from 43 to 49 are the "Syntactic" feature group and were added to analyse syntactic constructions which are useful for automatic simplification.
The features from 50 to 59 are the "Language model" feature group and are derived by comparing n-grams in the input text to n-gram frequencies in the language (Portuguese) as well as their perplexity and scores for any words which are not listed in the system's vocabulary.
The features from 1 to 3 and 9 to 11 are also called the "Basic" feature group because they require no linguistic knowledge. Feature 12 is also put into a feature group on its own called "Flesch".
Experiments were performed to check if it is possible to use machine learning techniques to learn to detect the INAF difficulty of reading levels and to discover which features are best to use for complexity detection.
Three types of machine learning algorithms in Weka were evaluated:
- "Standard classification" (SMO): A standard classifier (support vector machines) which assumes that there is no relation between the difficulty levels
- "Ordinal classification" (OrdinalClassClassifier): An ordinal classifier which assumes that the difficulty levels are ordered
- "Regression" (SMO-reg): A regressor which assumes that the difficulty levels are continuous
Manually simplified corpora were used as training data for the algorithms. The corpora were simplified into each of the difficulty levels. Using these simplified corpora it was possible to check if the system could predict that the original corpora are of "advanced" difficulty level, the lightly simplified corpora are of "basic" difficulty level and the heavily simplified corpora are of "rudimentary" difficulty level.
In order to determine the importance of each feature described, the absolute Pearson correlation between each feature of each corpora and how well it predicts the corpora's difficulty level is computed. The results for the best features below are copied from the paper (1=highly correlated, 0=not correlated):
- Words per sentence: 0.693
- Incidence of apposition: 0.688
- Incidence of clauses: 0.614
- Flesch index: 0.580
- Words before main verb: 0.516
- Sentences per paragraph: 0.509
In order to determine which machine learning algorithm is better at classifying the corpora into correct difficulty levels using the features mentioned earlier, the Pearson correlation with true score was used on how the corpora were classified. The experiments were also run using the sub-groups of features which were mentioned to see how important each group was. Here are the results, summarized from the paper:
Standard classification
| Feature group | Pearson correlation |
|---|---|
| All | 0.84 |
| Language model | 0.25 |
| Basic | 0.76 |
| Syntactic | 0.82 |
| Coh-Metrix-PORT | 0.79 |
| Flesch | 0.52 |
Ordinal classification
| Feature group | Pearson correlation |
|---|---|
| All | 0.83 |
| Language model | 0.49 |
| Basic | 0.73 |
| Syntactic | 0.81 |
| Coh-Metrix-PORT | 0.8 |
| Flesch | 0.56 |
Regression
| Feature group | Pearson correlation |
|---|---|
| All | 0.8502 |
| Language model | 0.6245 |
| Basic | 0.7266 |
| Syntactic | 0.8063 |
| Coh-Metrix-PORT | 0.8051 |
| Flesch | 0.5772 |
It is clear that it is better to use all the features together than any sub-group of them, but the syntactic features, followed by the Coh-Metrix-PORT features are the most useful feature groups and the language model feature group was the worst.
The simple classification algorithm was chosen as the best because although it is the simplest algorithm, its results are comparable to the other algorithms' results.
Tuesday, May 1, 2012
Summary of research paper "Chargaff’s “Grammar of Biology”: New Fractal-like Rules" by Yamagishi & Herai
This is a summary of the research paper http://arxiv.org/ftp/arxiv/papers/1112/1112.1528.pdf. Although it has "grammar of biology" in its title, it's basically about patterns in the frequencies of the 4 nucleotides in DNA: Adenine, Thymine, Cytosine and Guanine.
In case you don't know about it, DNA is a chain of these 4 types of molecules called nucleotides. Each nucleotide is represented by single letter which is the first letter of their name. So "TATA" can be a part of a DNA sequence for example. The DNA is made of 2 strands twisted around each other into a double helix. The two stands must be "complementary" such that if the first nucleotide on one strand is an "A" then the other strand must start with a "T", if it is a "T" then other must be an "A", if it is a "C" then the other must be a "G" and if it is a "G" then the other must be a "C", and the same goes for each nucleotide position in each strand.
Erwin Chargaff had discovered 2 simple patterns regarding the frequencies of the nucleotides in most organisms.
Chargaff's first parity rule says that if you count the number of each nucleotide on each strand, you'll find that the number of A nucleotides on one strand is equal to the number of T nucleotides on the other strand and so on for each complementary nucleotide. This is because of what was said in the previous paragraph.
The second parity rule says that the first rule also applies to the same strand, but only approximately. So the number of A nucleotides on a strand is approximately equal to the number of T nucleotides on the same strand and so on for each complementary nucledotide. It is less understood why this should happen. The problem is that if it were because the number of nucleotides is uniformly random, then the number of A and T nucleotides and the number of G and C nucleotides should not only be approximately equal, but the two groups should also be equal to each other, which is not the case. So the number of A nucleotides is approximately equal to the number of T nucleotides but not to the number of C or G nucleotides.
The second parity rule was later discovered to be a special case of a more general rule which says that on a given strand of DNA, the frequency of a sequence of nucleotides is approximately equal to the frequency of the reverse of the complement of that sequence. For example the number of time that "TAG" appears in a strand of DNA is approximately equal to the number of times that "CTA" appears in the same strand.
The research paper being discussed adds some new rules about the frequencies of the nucleotides.
Let's start from some notation.
Using this notation, Chargaff's rules can be represented as:
1: F(w, S) = F(C(w), S')
2: F(w, S) ≈ F(R(C(w)), S) (generalized version)
What the authors of the paper did was that they organized all possible words of a certain length into a table which they called a "Math table" such that each row will have a new word, its complement, its reverse and its reverse complement, but each word can only be used once in the table. Since each element of the table is unique, the words in the first column which generate the other columns are called a "generating set" or "G", and each word in "G" is labelled "g". According to the authors of the paper, there is no special way how to determine which words go into G.
For example here is a Math table for words of length 2:
By summing the frequencies of each column in the table it was determined that:
Eq1: SUM(F(g, S) for g in G) ≈ SUM(F(C(g), S) for g in G)
Eq2: SUM(F(R(g), S) for g in G) ≈ SUM(F(C(R(G)), S) for g in G)
Note: I'm not sure if the way G is chosen makes a difference or if the blanks in the Math table affect the summation.
The authors of the paper say that there are other identities were discovered using the Math table, but don't mention them.
Since SUM(F(g, S) + F(C(g), S) + F(R(g), S) + F(C(R(g)), S) for g in G) = 100% (assuming R(g) returns blank and hence F(R(g), S) and F(C(R(g), S) give 0 if R(g) is blank in the Math table),
SUM(F(g, S) + F(C(g), S) for g in G) + SUM(F(R(g), S) + F(C(R(g)), S) for g in G) = 100%
Using Eq1 and Eq2, we can turn this equation into
SUM(2F(g, S) for g in G) + SUM(2F(R(g), S) for g in G) ≈ 100%
2SUM(F(g, S) for g in G) + 2SUM(F(R(g), S) for g in G) ≈ 100%
Eq3: SUM(F(g, S) for g in G) + SUM(F(R(g), S) for g in G) ≈ 50%
Or
Eq4: SUM(F(C(g), S) for g in G) + SUM(F(C(R(g)), S) for g in G) ≈ 50%
Eq3 was confirmed with a variety of different species DNA.
In case you don't know about it, DNA is a chain of these 4 types of molecules called nucleotides. Each nucleotide is represented by single letter which is the first letter of their name. So "TATA" can be a part of a DNA sequence for example. The DNA is made of 2 strands twisted around each other into a double helix. The two stands must be "complementary" such that if the first nucleotide on one strand is an "A" then the other strand must start with a "T", if it is a "T" then other must be an "A", if it is a "C" then the other must be a "G" and if it is a "G" then the other must be a "C", and the same goes for each nucleotide position in each strand.
Erwin Chargaff had discovered 2 simple patterns regarding the frequencies of the nucleotides in most organisms.
Chargaff's first parity rule says that if you count the number of each nucleotide on each strand, you'll find that the number of A nucleotides on one strand is equal to the number of T nucleotides on the other strand and so on for each complementary nucleotide. This is because of what was said in the previous paragraph.
The second parity rule says that the first rule also applies to the same strand, but only approximately. So the number of A nucleotides on a strand is approximately equal to the number of T nucleotides on the same strand and so on for each complementary nucledotide. It is less understood why this should happen. The problem is that if it were because the number of nucleotides is uniformly random, then the number of A and T nucleotides and the number of G and C nucleotides should not only be approximately equal, but the two groups should also be equal to each other, which is not the case. So the number of A nucleotides is approximately equal to the number of T nucleotides but not to the number of C or G nucleotides.
The second parity rule was later discovered to be a special case of a more general rule which says that on a given strand of DNA, the frequency of a sequence of nucleotides is approximately equal to the frequency of the reverse of the complement of that sequence. For example the number of time that "TAG" appears in a strand of DNA is approximately equal to the number of times that "CTA" appears in the same strand.
The research paper being discussed adds some new rules about the frequencies of the nucleotides.
Let's start from some notation.
- Let w be a nucleotide sequence such as "ATCGAT", S be a DNA strand and S' be the other strand of the DNA.
- |p| is the length of the string p (could be a word or a strand). For example |"ATA"| = 3.
- F(w, S) is the fraction of the number of times w occurs in S over |S|-|w|+1. In other words, it is calculated using a sliding window and the number of times the word is found is divided by the number of times the window is moved. For example F("AA", "AATAAA") = 3/5. (This was confirmed in private conversation with the authors of the paper)
- C(w) is the complementary word of w nucleotide to nucleotide. For example C("ATCG") = "TAGC".
- R(w) is the reverse of w. For example R("ATCG") = "GCTA".
Using this notation, Chargaff's rules can be represented as:
1: F(w, S) = F(C(w), S')
2: F(w, S) ≈ F(R(C(w)), S) (generalized version)
What the authors of the paper did was that they organized all possible words of a certain length into a table which they called a "Math table" such that each row will have a new word, its complement, its reverse and its reverse complement, but each word can only be used once in the table. Since each element of the table is unique, the words in the first column which generate the other columns are called a "generating set" or "G", and each word in "G" is labelled "g". According to the authors of the paper, there is no special way how to determine which words go into G.
For example here is a Math table for words of length 2:
| g | C(g) | R(g) | C(R(g)) |
|---|---|---|---|
| AA | TT | - | - |
| AT | TA | - | - |
| CC | GG | - | - |
| CG | GC | - | - |
| AC | TG | CA | GT |
| AG | TC | GA | CT |
By summing the frequencies of each column in the table it was determined that:
Eq1: SUM(F(g, S) for g in G) ≈ SUM(F(C(g), S) for g in G)
Eq2: SUM(F(R(g), S) for g in G) ≈ SUM(F(C(R(G)), S) for g in G)
Note: I'm not sure if the way G is chosen makes a difference or if the blanks in the Math table affect the summation.
The authors of the paper say that there are other identities were discovered using the Math table, but don't mention them.
Since SUM(F(g, S) + F(C(g), S) + F(R(g), S) + F(C(R(g)), S) for g in G) = 100% (assuming R(g) returns blank and hence F(R(g), S) and F(C(R(g), S) give 0 if R(g) is blank in the Math table),
SUM(F(g, S) + F(C(g), S) for g in G) + SUM(F(R(g), S) + F(C(R(g)), S) for g in G) = 100%
Using Eq1 and Eq2, we can turn this equation into
SUM(2F(g, S) for g in G) + SUM(2F(R(g), S) for g in G) ≈ 100%
2SUM(F(g, S) for g in G) + 2SUM(F(R(g), S) for g in G) ≈ 100%
Eq3: SUM(F(g, S) for g in G) + SUM(F(R(g), S) for g in G) ≈ 50%
Or
Eq4: SUM(F(C(g), S) for g in G) + SUM(F(C(R(g)), S) for g in G) ≈ 50%
Eq3 was confirmed with a variety of different species DNA.
Subscribe to:
Posts (Atom)