Home Work 1

MORPHOLOGICAL STRUCTURE DISCOVERY (Hindi)

Mohit Sharma (11434)

Part A

Corpus Pruning Trials and Effects

Corpus Used: Hindi HC Corpora at www.corpora.heliohost.org/

The raw corpus had english alphabets, numeric characters and other special characters. Used a python script (given in Part-C) to prune out the non-Hindi characters, tokenize Hindi words, manage white spaces and then to count the number of occurences of each such tokenized word and sort the words according to their frequency in decreasing order.
The resultant output file had the format required by undivided++ as input ("frequency of the word", "word itself" in each new line). The resultant file however proved to contain large number of words and undivided++ crashed on the 4GB RAM machine while processing the same. Hence infrequent words were removed ( frequency less than or equal to 2 ). This reduced the dataset to a manageable size of approximately 80,000 unique words and their frequency.
The pruning of corpus was done in an incremental manner to start with. As expected, with non-hindi characters present in corpus, the results of undivided++ were very disappointing. Final script was written after this incremental understanding of the corpus.
On first run of undivided++ on cleaned corpus with default parameters, accuracy for "list 30" (assigned test dataset) was found to be less than 10%
The dataset contained words with high wordlength and undivided++ broke the word into many pieces unnecessarily ( over-segmentation ). Then after a long process of understanding undivided++ parameters, reading the guidelines and a lot of trial-error, following parameters suited the Hindi-corpus decently well.

Final Undivided++ Parameters Used

The parameters used for Undivided++ which gave the best tested accuracy were as follows:
#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 2
#define SLS_NORMALIZATION_CONSTANT 5
#define ALLOMORPH_REPLACEMENT_THRESHOLD 4
#define ALLOMORPH_DELETION_THRESHOLD 4
#define ALLOMORPH_ADDITION_THRESHOLD 4
#define PROMOTE_LONG_SEGMENTATION 0
#define PROMOTE_LONG_SEGMENTATION_LENGTH 15
#define INDUCE_OUTOFVOCABULARY_ROOTS 3
#define INDUCE_OUTOFVOCABULARY_ROOTS_THRESHOLD 5

Also the compilation was done with all parameters in "ON" state as "./a.out input_file 1 1 1 1 1 "

Main parameters which proved to play an important role were:

  • WRFR_SUFFIX_THRESHOLD
  • WRFR_PREFIX_THRESHOLD
  • PROMOTE_LONG_SEGMENTATION
  • SUFFIX_CUTOFF_THRESHOLD
  • PREFIX_CUTOFF_THRESHOLD

    > The first two parameters are used in Step-2 i.e. Detecting Incorrect Attachments Using Relative Frequency. Tuned the thresholds to prevent prefixal/suffixal incorrect attachment i.e., over-segmentations. Decreasing the threshold gradually leads to preventing more and more over-segmentation.
    > The PROMOTE_LONG_SEGMENTATION is used to promote the segmentation of high-length words. The higher the length the more likely the words are going to be segmented. It can be On or Off by setting it to 1 or 0. Since in the initial cases long words were getting over-segmented, this parameter was turned off and that significantly improved the results especially for the 300 test words as most of them were long words.
    > Increasing the last two thresholds downsize the prefix/suffix list whereas decreasing the corresponding threshold, expands the suffixes/prefixes learned. They too have a role in checking over-segmentation as more the number of prefix-suffix learnt, more probable is a word's segmentation.

    The parameters LOW_FREQUENCY_DROPOUTS and LOW_FREQUENCY_DROPOUTS_LEARNING improve the performance and running time of the algorithm by managing the total number of words that should be used for training phase and segmenting phase.

    Results

    H: 235
    I: 61
    D: 121
    RECALL :.66
    PRECISION : .79
    F-SCORE : .72

    Discussion of Error Cases

     Broadly, there are four categories of error that is seen in the output of undivided++.

    1. Over-segmentation - Most of the words given in test list are long words and thus are prone to over-segmentation. The word is often unnecessarily broken down into many common prefixes and suffixes. For eg.
    --> कारोबारी: क+ार+ो+बारी instead of कारोबार+ई
    --> अपराधियों: अ+पर+ा+ध+ियों instead of अपराध + इयों
    This is the most common error that is encountered. Over-segmentation is avoided by setting PROMOTE_LONG_SEGMENTATION to 0 and by decreasing the parameters WRFR_SUFFIX_THRESHOLD and WRFR_PREFIX_THRESHOLD


    2. Under-segmentation - Once you set parameters to check over-segmentation, another kind of error that starts surfacing is under-segmentation. This is mainly because PROMOTE_LONG_SEGMENTATION is set to 0 and segmentation is now often avoided. This is also because lesser number of affixes are recognised due to comparatively higher values of SUFFIX_CUTOFF_THRESHOLD and PREFIX_CUTOFF_THRESHOLD. For eg.

    --> आधिकारिक: आधिकारिक instead of अधिकार + इक
    --> अनुसूचित: अनुसूचित instead of अनु+सूचित


    3. Segmentation at the wrong place- Some words are segmented at the wrong place. Consider the following example:
    --> बालकृष्ण: बालकृष्+ण instead of बाल+कृष्ण
    This again, is by and large related to 'what all' and 'how much' affixes are learnt by the algorithms controlled by SUFFIX_CUTOFF_THRESHOLD and PREFIX_CUTOFF_THRESHOLD. Words are broken keeping the most frequent affixes in consideration.


    4. Addition of characters - The word joining or संधी in Hindi is much more complicated than in say languages like English. Consider for example the word सतीश. The word breaks down as सती + ईश. Note the fact that the when the word is broken, the number of characters used in its parts is more than the number of characters in the original word. These type of cases are rarely seen to be handled by undivided++.

    The non-hindi words were mostly coming under error cases of under-segmentation or misplaced segmentation.

    Part B

    Hand annotated Test-Data

     Please find the hand-annotated data here (Download the txt file directly from directory if the characters are not clear).
    The output of undivided++ with H,I,D calculated can be found here .
    '1' before the word signifies that it was segmented correctly and a '0' stands for an error in the segmentation. The triplet in paranthesis is (HID) for each word.

    Part C

    Scripts

     Various scripts used for the assignment could be found here ( will be activated on 18th Aug) .
    It contains a script to prune the corpus and few others which were written to do some mechanical repetitive tasks. The "ReadMe" file has all the relevant information.