CS671: Homework 1

Morphological Structure Discovery for Hindi Language

(A)

• Corpus pruning trials and Effects

The downloaded corpora has approx. 6.5 million words. This data contains a lot of noise like alphanumeric characters like: "॰॰॰" , "¼dedicate½," "१.२७e२२", "ऽइश्क़्" , some punjabi and tamil words also. So these words were removed from the corpora. Then the words with less than 3 unicode character were removed using a simple python script. We then removed the words with frequency 1 (259029 words left). This reduced the size of corpora to approx 3 million. furter, the words with frequency 2 were removed leaving 180857 words and frequency 3 words removed leaving 144720 words. These words are not relevant for segmentation because the Undivided++ uses the frequency of words to determine the morphemes and the low frequency words lead to over-segmentation/are not relevant. The final corpora has approx 1.5 million unique words each with more than 3 unicode charscters and frequency greater than 3.

• Undivided++ parameters used and corresponding precision, recall and F-score

Many attempts have been made with various parameter changes to get the best F-score. The changes in both the external and internal parameters were made to notice the effectes.
The program takes following as external input arguments (0 or 1 to switch them on/off):

1. Induce Prefixes/Suffixes/Roots
2. Detecting Incorrect Attachments Using Relative Frequency
3. Applying Suffix Level Similarity
4. Inducing Orthographic Rules and Allomorphs
5. Handle Small Roots.

The 1st switch is always kept ON as this is what we aim in this assignment. Two configurations were tried by looking because some switches are necessary and improcve performance as mentioned by the author. Following are the results of the attempts (where I-> number of insertions and D-> number of deletions to make proposed segmentation of word same ads the correct segmentation and H -> denotes the correct boundary hits from the start of the word):

ATTEMPT1: 1 1 0 1 0
I: 316.0 D: 484.0
Precision: 0.479406919275
Recall: 0.375483870968

ATTEMPT2: 1 1 1 0 1
I: 318.0 D: 489.0
Precision: 0.47868852459
Recall: 0.373879641485

The observation is that Step-3 detects incorrect attachments using suffix level similarity. However, it's often not as significant performance-improver as compared to 4th step which is used to learn the character-change rules by a single character replacement, addition and deletion at the segmentation boundary. So the attempt 1 parameters are used as input arguments in all further attempts.

The internal parameters that determine various segmentation properties like smallest root length, suffix length were changed and following observations have been ontained: (Here '->' shows the change made):

3rd ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3
#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 -> 8
#define WRFR_PREFIX_THRESHOLD 1.5 -> 1

The corresponding precision/recall and F-score are:
I: 316.0 D: 484.0 H: 291.0
Precision: 0.479406919275
Recall: 0.375483870968

This shows changing the WRFR suffix threshold doesn't imapct the segmentation.

4th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3
#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 -> 1

I: 316.0 D: 484.0 H: 291.0
Precision: 0.479406919275
Recall: 0.375483870968
F-Score: 0.421128799

This indicates decreasing the WRFR prefix threshold doesn't impact the segmentation much either.

5th ATTEMPT 1 1 0 1 0
#define WRFR_SUFFIX_THRESHOLD 10
#define WRFR_PREFIX_THRESHOLD 1.5 -> 2 -SUDDEN IMPROVEMENT DUE TO WRFR INCREASE

I: 310.0 D: 412.0 H: 284.0
Precision: 0.478114478114
Recall: 0.408045977011
F-Score: 0.440310078

Increasing the WRFR prefix threshold i.e. relaxing the prefix segmentation has sudden impact in the increase of the precision and recall.

6th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3 -> 5 ----SMALL IMPROVEMNT DUE TO ROOT LENGTH INCREASE
#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 -> 2

I: 310.0 D: 391.0 H: 281.0
Precision: 0.475465313029
Recall: 0.418154761905
F-Score: 0.444972288203

Increasing the small rootlength leads to small increase in the precision and recall. This may be probably because the ी, ा etc. in Hindi ocur a lot and account for a unicode character so it is reasonable to keep the root length high.

7th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3 -> 5
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 1
#define SUFFIX_CUTOFF_THRESHOLD 70 //CRITICAL
#define PREFIX_CUTOFF_THRESHOLD 60 //CRITICAL
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10 -> 5 ---> no change dUE TO WRFR IN SUFFIX
#define WRFR_PREFIX_THRESHOLD 2
#define SLS_NORMALIZATION_CONSTANT 5

I: 310.0 D: 391.0 H: 281.0
Precision: 0.475465313029
Recall: 0.418154761905
F-Score: 0.444972288203

There was no change due to the decrease in the WRFR suffix threshold.

8th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3 -> 4 ->LITTLE DECREMENT IN PERFORMANCE
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 1
#define SUFFIX_CUTOFF_THRESHOLD 70 //CRITICAL
#define PREFIX_CUTOFF_THRESHOLD 60 //CRITICAL
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10 -> 5
#define WRFR_PREFIX_THRESHOLD 2
#define SLS_NORMALIZATION_CONSTANT 5

I: 309.0 D: 397.0 H: 282.0
Precision: 0.477157360406
Recall: 0.415316642121
F-Score: 0.444094488189

There was little decrease in the performace due to the decrease in small root length. SO it is advised to keep it high.

9th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3 -> 5 -> Overall all changes Led to decrease
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 1
#define SUFFIX_CUTOFF_THRESHOLD 70 //CRITICAL
#define PREFIX_CUTOFF_THRESHOLD 60 //CRITICAL
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10 -> 12
#define WRFR_PREFIX_THRESHOLD 2 -> 3
#define SLS_NORMALIZATION_CONSTANT 5

I: 312.0 D: 399.0 H: 282.0
Precision: 0.474747474747
Recall: 0.4140969163
F-Score: 0.442352941176

The increase in the the WRFR suffix led to the decrease in the performance.


10th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3 -> 5
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 1
#define SUFFIX_CUTOFF_THRESHOLD 70 //CRITICAL
#define PREFIX_CUTOFF_THRESHOLD 30 //CRITICAL -> Led to great improvement
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10 -> 10
#define WRFR_PREFIX_THRESHOLD 2 -> 2
#define SLS_NORMALIZATION_CONSTANT 5

I: 303.0 D: 399.0 H: 288.0
Precision: 0.48730964467
Recall: 0.419213973799
F-Score: 0.450704225352

The decrease in the PREFIX cut-off parameter led to great increase in the performace, so it is advised to keep it low.


11th ATTEMPT 1 1 0 1 0
#define SMALL_ROOT_LENGTH 3 -> 5
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 1
#define SUFFIX_CUTOFF_THRESHOLD 30 //CRITICAL
#define PREFIX_CUTOFF_THRESHOLD 30 //CRITICAL -> Led to great improvement
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10 -> 10
#define WRFR_PREFIX_THRESHOLD 2 -> 2
#define SLS_NORMALIZATION_CONSTANT 5

I: 288.0 D: 397.0 H: 292.0
Precision: 0.503448275862
Recall: 0.423802612482
F-Score: 0.460204885737


12th ATTEMPT 1 1 0 1 0 (BEST RESULTS)
#define SMALL_ROOT_LENGTH 3 -> 5
#define LOW_FREQUENCY_DROPOUTS 1
#define LOW_FREQUENCY_DROPOUTS_LEARNING 1
#define SUFFIX_CUTOFF_THRESHOLD 30 //CRITICAL
#define PREFIX_CUTOFF_THRESHOLD 30 //CRITICAL -> Led to great improvement
#define COMPOSITE_SUFFIX_THRESHOLD 0.65
#define WRFR_SUFFIX_THRESHOLD 10 -> 10
#define WRFR_PREFIX_THRESHOLD 2 -> 2
#define SLS_NORMALIZATION_CONSTANT 5
#define ALLOMORPH_REPLACEMENT_THRESHOLD 3
#define ALLOMORPH_DELETION_THRESHOLD 3
#define ALLOMORPH_ADDITION_THRESHOLD 3
#define PROMOTE_LONG_SEGMENTATION 1 -> 0 --- a BIG JUMP
#define PROMOTE_LONG_SEGMENTATION_LENGTH 15
#define INDUCE_OUTOFVOCABULARY_ROOTS 0
#define INDUCE_OUTOFVOCABULARY_ROOTS_THRESHOLD 5

By switching off the segmentation only when the word length is long, sudden increase in precision is seen. It may be because in Hind ि, ी, ो, etc. contribute to the unicode length equally and by allowing splitting of only longer words, there were greater restrictions.

I: 251.0 D: 218.0 H: 287.0
Exact Accuracy:19.28 (EXACT MATCHING SPLIT)
Precision: 0.533457249071
Recall: 0.568316831683
F-Score: 0.55033557047



• Discussion of error cases

The code gives good splitting for the longer words like "धर्म+ग्रन्थ", "क्षुद्र+ग्रह" , "गिरफ्त+ारियाँ", "विधान+सभा+ओं" etc. But the accuracy is still low because of te wrong prefix prediction by it on the basis of WRFR ratio=2. Consider for example "देंखे", "देंगे", in this the prefix is recognized as "दे" by the code because it occurs with a lot of different root words comparable number of times and hence it predicts "दे" as the prefix. If these type of error could be removed, then accuracy is likely to increase a lot. Also there are some words for which the code doesn't do any segmentation because it didn't have enough instance in the dictionary to do the split. e.g. "परिस्थियों" is not segmented by the code at all.

(B) Hand Annotated Dataset

The hand annotated dataset is available here and the original list is available here.

(C) CODE for handling the corpus and Metrics Evaluation