Assignment 1

Morphological Structure Discovery

Observations

Part A

Corpus Pruning Trials and Effects

The initial corpus (from Heliohost, data from blogs and newspapers) had alphanumeric and other special characters, which needed to be removed, to prune it. Initially I used a python script to prune out the characters which were different from the Hindi characters; then to trim the extra spaces; and then used another script to count the occurences of a word in the given corpus and sort it according to their frequency (decreasing order). The output (the frequency of the word, followed by the word itself) was stored in a .csv file which was then used as an input to the program "UnsupervisedWordSegmentation.cpp".

The parameters used to clean up the corpus were
a) Drop the words with frequency less than or equal to 1 (second and third parameter) and
b) The smallest-root length of words to be taken as 3 (first parameter).
These parameters were changed, and it was observed that increasing the minimum frequency pruned the dataset but did not significantly improve the segmentation accuracy.

Initially, the trials were giving around 30% (92/300) accuracy, when used with the default parameters given in Undivided++. Then as the parameters were changed according to the corpus, the accuracy increased to 54% (161/300).

Undivided++ Parameters Used

The parameters used for Undivided++ which gave the best accuracy were.
#define SMALL_ROOT_LENGTH 3
#define LOW_FREQUENCY_DROPOUTS 2
#define LOW_FREQUENCY_DROPOUTS_LEARNING 3
#define SUFFIX_CUTOFF_THRESHOLD 70
#define PREFIX_CUTOFF_THRESHOLD 50
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 6
#define WRFR_PREFIX_THRESHOLD 1.5
#define SLS_NORMALIZATION_CONSTANT 5
#define ALLOMORPH_REPLACEMENT_THRESHOLD 3
#define ALLOMORPH_DELETION_THRESHOLD 3
#define ALLOMORPH_ADDITION_THRESHOLD 3
#define PROMOTE_LONG_SEGMENTATION 0
#define PROMOTE_LONG_SEGMENTATION_LENGTH 15
#define INDUCE_OUTOFVOCABULARY_ROOTS 0
#define INDUCE_OUTOFVOCABULARY_ROOTS_THRESHOLD 5

The parameters used while compiling were
./a.out file_name.csv 1 1 0 1 0
The parameter which had the maximum positive effect was setting PROMOTE_LONG_SEGMENTATION to 0, which reduced a lot of cases of segmentation of long words when none was needed.
The parameter LOW_FREQUENCY_DROPOUTS and LOW_FREQUENCY_DROPOUTS_LEARNING largely reduced the number of words considered and improved the performance.

Discussion of Error Cases

 All errors can be categorized into mainly two types of errors (or a combination of these) :-

1. Over-segmentation - Most long words are prone to over-segmentation, where any segmentation is not necessary. Mostly these are words which are not part of the Hindi language, but derived from other languages. Also, it is the case when common prefixes and suffixes are found in a word and extracted. But over-segmentation is reduced to a great extent when PROMOTE_LONG_SEGMENTATION is set to 0, as expected. An example of error from the results that I got is

-- इनसाइक्लोपीडिया : इनसाइक्लोपीडि+या

-- प्रतिरोपित - प्रति + रो +पि+त
In most cases, where an extra alphabet is to be introduced, it fails, like in the above. (The correct segmentation would be)
-- प्रतिरोपित - प्रति + आरोपित

2. Under-segmentation - Some words are prone to under-segmentation, when the parameter PROMOTE_LONG_SEGMENTATION is set to 0. This is because the suffixes are not recognized sufficiently. eg.

अफ्रीकियों - अफ्रीकियों

where the correct segmentation would be

अफ्रीकियों ---- अफ्रीकी + यों

3. Most cases of incorrect segmentation are cases of over-segmentation itself. But in some cases like

प्रबुद्धनगर -प्र +बुद्धनगर

Here, it is segmented at the wrong place, and not segmented where it was supposed to be. This is due to identification of prefixes and suffixes and it usage at every place. Increasing/Decreasing the threshold of SUFFIX_CUTOFF_THRESHOLD adversely affects the whole test data, and create more false positives/negatives so this was the optimum amount.

Part B

Hand Annotated Test Data

 For the hand-annotated test data, the link is Download Hand annotated test data.
The test data contains markers as to the error. The words starting with * mark, are the ones that have been correctly segmented by Undivide++, and the others are incorrect. The output of the program Undivide++ is included in the next part.

Part C

Code for handling the corpus

 For the code for handling the corpus (pruning the corpus), the link is Download all code