CS671 - Natural Language Processing - Assignment 1

Corpus

The corpus used for this was a concatenation of the corpora available on the website. An initial attempt to scrape hi.wikipedia.org led to an unclean corpus that was discarded for this assignment. The concatenation of the corpora.heliohost.org Hindi corpora and the CFILT, IIT Bombay corpora gave a 218 MB file that was used as the training corpus.

The merging was done using the following command:

cat ./Data/*.txt > corpus.txt

This corpus was very unclean, and required many steps before it could be usable.

All English words and special characters were removed, along with most punctuation symbols. One glaring hole in this process was the । symbol (used as sentence endings in Hindi). The reason for this hole is that for some reason, removing it also seems to remove a lot of the other Hindi characters for some reason.
```
tr "[a-zA-Z\:\;\.\,\'\"\`\-]" " " < corpus.txt > stage1.txt
```
This was then converted into a frequency list using the following command:
```
cat stage1.txt | tr " " "\n" | sort | uniq -c | sort -gr > stage2.txt
```
The \n lines led to the most frequent entry being a frequency followed by an EOL. This, and other spurious lines were removed using the following sed command:
```
cat stage2.txt | sed -r '/^\ *[0-9]*\ \t/d' | sed -r '/^\ *[0-9]+$/d' > stage3.txt
```
The following two sed commands get rid of the short words (less than 4 unicode characters in length) and the infrequent words (less than 3 occurrences)
```
sed -r '/^\ *[0-9]*\ .{1,3}$/d' < stage3.txt > stage4.txt
sed -r '/^\ *[1-2]\ /d' < stage4.txt > stage5.txt
```
One major problem that prevented me from going any further for many days was that I was trying to feed this file into the UnDivide++ stemmer. According to the documentation (Guidelines.txt), the input file had to be of the form
```
[freq_of_the_word_in_a_corpus] [word_itself]
```
Despite my input being in that format, the tool did not give me any results. The problem was the spaces at the beginning of the sentences (used by the sort command to right-align all the frequency values. Once these were removed, the output was non-empty.
```
sed -r 's/^\ +//' < stage5.txt > final.txt
```
This gave me the final frequency file to use in the UnDivide++ tool.

Stemming/Segmentation

The input given to Undivide++ returned the segmentation of each word in the corpus (finalSegmentation.txt). This file was searched for the entries in the 300 word list selected for manual segmentation. These entries, if found, were saved in a new text file. The program was unable to find 54 words of the list in the original corpus. There are two possible reasons for this: Firstly, the word doesn't appear in the corpus. Secondly, the word exists in the corpus with some character (not deleted in the cleaning process) prepended/appended to it. The results for the remaining 246 words were analyzed manually for correctness. This was not done using any program, despite the fact that a manually segmented list had been created. The reason for this is that a language like Hindi can be split at multiple points while not really altering the segmentation.
For example, हत्याकाण्ड can be segmented as हत्या+का+ण+्ड (which is what UnDivide++ returned), and equally accurately as हत्या+का+ण्+ड. Technically, these two segmentations are different; ideologically, they are not. Given the limited size of the test set, not looking at the individual results would lead to inaccuracies that can easily be prevented in this particular assignment.

All the results are given in the Results tab of the Excel file, along with the segmentation generated at each set of parameters.

The parameters that can be modified in Undivide++ are the following:

#define SMALL_ROOT_LENGTH 4*
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 5
#define SUFFIX_CUTOFF_THRESHOLD 50
#define PREFIX_CUTOFF_THRESHOLD 70
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10
#define WRFR_PREFIX_THRESHOLD 1.5
#define SLS_NORMALIZATION_CONSTANT 7
#define ALLOMORPH_REPLACEMENT_THRESHOLD 4
#define ALLOMORPH_DELETION_THRESHOLD 4
#define ALLOMORPH_ADDITION_THRESHOLD 4
#define PROMOTE_LONG_SEGMENTATION 1*
#define PROMOTE_LONG_SEGMENTATION_LENGTH 30*
#define INDUCE_OUTOFVOCABULARY_ROOTS 1
#define INDUCE_OUTOFVOCABULARY_ROOTS_THRESHOLD 5

./a.out wordlist.eng 1 1 0 1 0

Of these parameters, the ones marked with the asterisk (*) have been modified systematically, to try to achieve an optimal result. This was a slightly slow process, since the segments were checked manually, but enough values were tested to reach a conclusion. The best combination of these parameters (according to the trials) is given above.

Results

Summary

Seven sets of parameters were tested.
Here, the test data has been classified into two mutually exclusive categories: Proper test cases, and Improper test cases. Improper test cases is a manual classification for test cases where I have placed words like होर्डिंग्स, आर्मस्ट्रॉन्ग, and रेटिनोपैथी. These words are either derived from a different language, and translated into Hindi, or refer to proper nouns with no standard segmentation. These test cases do not follow the standard structure of Hindi, and hence do not have the same affixes as Hindi words.

Parameters		Results
SMALL_ROOT_LENGTH	PROMOTE_LONG_SEGMENTATION_LENGTH	Accuracy of Segmentation (All test cases)	Accuracy of Segmentation (Proper test cases)	Accuracy of Segmentation (Improper test cases)
3	15	23.17%	28.9%	9.59%
4	20	40.24%	47.98%	21.92%
5	20	39.43%	47.40%	20.55%
4	25	43.90%	52.02%	24.65%
4	30	45.53%	53.18%	27.40%
4	40	44.31%	50.29%	30.14%
4	Infinity (Setting `PROMOTE_LONG_SEGMENTATION` to 0)	43.90%	48.55%	32.88%

Proper test case accuracy

The parameter SMALL_ROOT_LENGTH sets the length of the smallest root during segmentation. A value of 3 does surprisingly badly, which is to be expected, since every matra in Hindi is technically one character. Hence, a value of 3 basically allows tiny roots, leading to over-segmentation. A value of 5 shows no appreciable advantage over a value of 4, and in fact leads to a tiny amount of test cases failing.
In the following examples, we see that increasing the root length prevents the formation of tiny roots, that cause the word to segment a great deal.
Ex. 1:
    SRL = 4: अवश्यंभावी:अवश्य+ं+भाव+ी
    SRL = 3: अवश्यंभावी:अव+श+्य+ं+भाव+ी
Ex. 2:
    SRL = 4: चुनौतीपूर्ण:चुनौती+पूर्ण
    SRL = 3: चुनौतीपूर्ण:चु+नौ+ती+पूर्ण

Increasing the PROMOTE_LONG_SEGMENTATION_LENGTH parameter will forcefully segment a word above the set length. Again, the default length of 15 is too tiny for most big Hindi words, and increasing it seems to give good results. At around a length of 30 characters, the accuracy of proper test case segmentation begins to drop. Since, it is my opinion that this is a more important parameter than the others, this combination of parameters seems efficient.
The following examples show places where the length has made a difference.
Ex. 1: A larger Segmentation Length leads to a long word not giving its correct segments
    LSL = 40: मेट्रोपालिटन:मेट्रोपालिटन
    LSL = 30: मेट्रोपालिटन:मेट्रो+पाल+ि+टन
Ex. 2: A smaller Segmentation Length gives unnecessarily short segments
    LSL = 25: अव्यावसायिक:अ+व्यावसाय+िक
    LSL = 20: अव्यावसायिक:अ+व्या+व+सा+य+िक

Improper test case accuracy

As can be seen in the table above, there seem to be two trends in the results. The first one is the one we have just explored: the fact that the proper test case segmentation accuracy peaks at SMALL_ROOT_LENGTH = 4 and PROMOTE_LONG_SEGMENTATION_LENGTH = 30. The second trend visible in the results is in the improper test case segmentation accuracy, that seems to increase with the PROMOTE_LONG_SEGMENTATION_LENGTH parameter, and seems to take the maximum when PROMOTE_LONG_SEGMENTATION is set to 0 (effectively making the PROMOTE_LONG_SEGMENTATION_LENGTH equal to infinity).
If I was to select a set of parameters to accurately segment English words translated into Hindi, I would definitely choose SMALL_ROOT_LENGTH = 4 and PROMOTE_LONG_SEGMENTATION = 0. This result seems perfectly intuitive. Most modifications in words translated into Hindi from another language will be superficial and commonplace. Any uncommon affix would probably not be applied to the word. This would mean that most of the word should stay intact, and only the most common affixes should be applicable for its segmentation. This is exactly the kind if behaviour one would expect from PROMOTE_LONG_SEGMENTATION being set to false.
The following examples show words where this set of parameters did better than SRL = 4, LSL = 30.
Ex. 1:
    LSL = 25: न्यूक्लीयर:न्यू+क्लीयर
    LSL = 40: न्यूक्लीयर:न्यूक्लीय+र
Ex. 2:
    LSL = 30: मेटास्टेसिस:मेटा+स्टे+स+िस
    LSL = Inf: मेटास्टेसिस:मेटास्टेसिस

Precision and Recall

If we have a case where either the result of a test case is valid, or it isn't, it really isn't possible to calculate Precision and Recall. Sajib Dasgupta and Vincent Ng have given this interesting way to use morpheme boundaries for calculating Precision and Recall. Unfortunately, the way I'm checking the segmentation doesn't really let me calculate precision the way they do. Luckily for us, there is a quantity that can be judged on the basis of false positives and false negatives. This quantity is closely connected to the two parameters we have discussed earlier. There are many words in the test set that, for various reasons, are not segmented, even in the manually created, ground-truth segmentation. Examples include एप्टीट्यूड, कॉलेस्टरॉल, and च्यवनप्राश. If we look at the results of UnDivide++ and classify a positive result as an unsegmented result, we get the following results:

SMALL_ROOT_LENGTH = 3
PROMOTE_LONG_SEGMENTATION_LENGTH = 15

True Positive	False Positive
7	57
False Negative	True Negative
22	160

Precision	0.109
Recall	0.241
Specificity	0.737
Accuracy	0.679
F1-Score	0.151

SMALL_ROOT_LENGTH = 4
PROMOTE_LONG_SEGMENTATION_LENGTH = 20

True Positive	False Positive
6	23
False Negative	True Negative
23	194

Precision	0.207
Recall	0.207
Specificity	0.894
Accuracy	0.813
F1-Score	0.207

SMALL_ROOT_LENGTH = 5
PROMOTE_LONG_SEGMENTATION_LENGTH = 20

True Positive	False Positive
5	24
False Negative	True Negative
24	193

Precision	0.172
Recall	0.172
Specificity	0.889
Accuracy	0.805
F1-Score	0.172

SMALL_ROOT_LENGTH = 4
PROMOTE_LONG_SEGMENTATION_LENGTH = 25

True Positive	False Positive
3	14
False Negative	True Negative
26	203

Precision	0.176
Recall	0.103
Specificity	0.935
Accuracy	0.837
F1-Score	0.130

SMALL_ROOT_LENGTH = 4
PROMOTE_LONG_SEGMENTATION_LENGTH = 30

True Positive	False Positive
3	13
False Negative	True Negative
26	204

Precision	0.188
Recall	0.103
Specificity	0.940
Accuracy	0.841
F1-Score	0.133

SMALL_ROOT_LENGTH = 4
PROMOTE_LONG_SEGMENTATION_LENGTH = 40

True Positive	False Positive
9	44
False Negative	True Negative
20	173

Precision	0.170
Recall	0.310
Specificity	0.797
Accuracy	0.740
F1-Score	0.220

SMALL_ROOT_LENGTH = 4
PROMOTE_LONG_SEGMENTATION_LENGTH = Infinite

True Positive	False Positive
11	47
False Negative	True Negative
18	170

Precision	0.190
Recall	0.379
Specificity	0.783
Accuracy	0.736
F1-Score	0.253

These values fit completely with what we have seen so far. The Specificity hits a peak for LSL = 30 as is expected. This implies that LSL = 30 is good for finding/identifying negative results. In this case, that translates to being good at getting segmented results. Also, high recall and F1-score values for LSL = Infinite tell us that this set of parameters is the best among these at finding the Positive cases, that is, identifying the single segment results. This fits well with the theory covered earlier, and with the concepts mentioned above.

Interesting Error Cases

Here, we see that the segmenter has recognized -ing in English words. The parses are both wrong, but the suffix is correctly recognized.
प्रोविजनिंग:प्रो+वि+जन+िंग
ब्लास्टिंग:ब्ला+स्ट+िंग
एक्साइटिंग:एक्+साइट+िंग

Using LSL = Inf, we get स्टिंग in place of िंग, showing that quite a few English translated words are present in the corpus (since the only reason स्टिंग would be preferred is if it exists often enough to be the root word.)
ब्लास्टिंग:ब्ला+स्टिंग

The ग्रा affix seems to be popular enough for it to override the ग्राफ it has already added to the segment list in the example below.
फोटोग्राफर:फोटो+ग्राफ+र
फोटोग्राफी:फोटो+ग्राफ+ी
फोटोग्राफरों:फोटो+ग्रा+फरों

Comparing with this output from SW = 3, LSL = 15, we see that ग्रा still exists, while the rest of the parses have vanished.
फोटोग्राफर:फोटोग्राफर
फोटोग्राफी:फोटोग्राफी
फोटोग्राफरों:फोटो+ग्रा+फरों

Files

A set of all shell commands used for extraction, cleaning, and input-file creation. (This shell file was not used by me directly to create the files, but every command I used is in it)
The MS Excel file containing the results of all the experiments, the segmentation created at each result, the calculations, and the manual segmentation.
The final.txt input file for UnDivide++
The input test case list.