Difference between revisions of "User:Dmin1/Final project"
(→Coverage of corpora) |
(→Repository) |
||
| (47 intermediate revisions by the same user not shown) | |||
| Line 9: | Line 9: | ||
=Overview= | =Overview= | ||
| + | The development of this transducer largely consisted of two parts. The first challenge I encountered was to make the apertium pipeline work for Hangul(Decompose-Compose Step). This is the same problem I had while working on Jeju. While I only bypassed the problem in Jeju transducer, this issue is completely solved in this project. The second part consists of normal transducer development tasks: writing rules, adding lemmas, preparing corpora, evaluating, and repeating. Also, note that due to the large size of hangul.lexc, it is recommended that the user compiles it in a machine with at least 16gb of RAM or enable swap partition. | ||
| + | |||
==Decompose-Compose Step== | ==Decompose-Compose Step== | ||
| − | + | Hangul, writing system for Korean, blocks 2 or 3 letters into a syllable-block, where each letter occupies the position of onset, nucleus, and optionally, coda. While Hangul is an alphabet, this blocking system requires that all legal combination of Hangul letters into a syllable encoded in a separate Unicode. | |
| + | |||
| + | While developing a transducer for Jeju, this meant that I had to six thousands of Unicode letters to my lexc file. Not only did this make compiling very slow, but it did also led to restriction of morphological analysis. For instance, consider the following case: | ||
| + | *Vowel Ending + (Topic Marker) -> 는 | ||
| + | *Consonant Ending + (Topic Marker) -> 은 | ||
| + | To properly analyze this, it would be necessary to look at the last sound of the previous word. However, since this information is always encoded with extra information about the other letters that contain one syllable. Thus, it results in a massive explosion of matchings needed to capture the whole set. | ||
| + | |||
| + | However, in the new approach I matched a syllable to its decomposed letters. Although I needed still have one large separate hangul.lexc file with all such possible matchings, I only needed to compile once. More importantly, I allowed me to refer to the last letter of the decomposition, making writing matching rules much easier and natural. An important implementation detail is that in the hangul.lexc file each syllable, based on the number of letters constructing it, was given a carefully chosen weight. 1-letter syllable is given weight 0.8, 2-letter 1.4 3-letter 2.1. The weights are chosen so that larger syllables are preferred. | ||
| + | |||
| + | This was to ensure that in the compose step, only the correct composition is applied. For instance, 가나 will be flattened to ㄱㅏㄴㅏ, and there are many ways to arrange this: 간ㅏ,ㄱ ㅏ나ㅡ,ㄱㅏ나, etc. Now we see that ㄱㅏㄴㅏ has the unique minimum weight of 2.8, and is chosen in the decompose step. Since incorrect forms necessarily break up a larger composition into smaller ones, they have larger weight than the unique correct form. | ||
| − | ==Structure== | + | *Is Hangul a [https://en.wikipedia.org/wiki/Variable-length_code#Uniquely_decodable_codes uniquely decodable code? ] |
| − | Most of the morphology was | + | |
| + | ==Structure and Development== | ||
| + | Finding corpora was easy. In particular, I processed Korean Wikipedia dump into a large | ||
| + | corpus, from which I drew several random samples. | ||
| + | |||
| + | Most of the morphology was implemented in lexc and twol file. In this implementation of Korean POS analyzer, I was able to analyze most of noun morphology correctly. However, as there were multiple level of suffixes that attaches to verbs in Korean, the analysis and construction of verb alteration was not easy, as it involved multiple levels of suffixing and vowel harmony. | ||
=Evaluation= | =Evaluation= | ||
| − | + | This section contains the results of the first evaluation I conducted after a preliminary development. | |
| − | |||
| − | I | ||
==Coverage of corpora== | ==Coverage of corpora== | ||
Trained Corpora refers to the hand-assembled corpora that I used during development cycle to find out which forms were not analyzed by the transducer. Thus, coverage for them is not a good measure of the transducer's performance.(because I have changed the transducer so that their coverages improves.) | Trained Corpora refers to the hand-assembled corpora that I used during development cycle to find out which forms were not analyzed by the transducer. Thus, coverage for them is not a good measure of the transducer's performance.(because I have changed the transducer so that their coverages improves.) | ||
| − | On the other hand, each test corpus is a set of 1200 words that I have fetched randomly from Korean Wikipedia. There might be some overlaps between them, but it is unlikely that they are significantly correlated to each other. They provide a more reliable estimate of the transducer's performance as a result. | + | On the other hand, each test corpus is a set of 1200 words that I have fetched randomly from Korean Wikipedia.(I ran $cat corpus/wiki.txt |sort -Ru | head -n 1200 > sample.txt |
| + | ) There might be some overlaps between them, but it is unlikely that they are significantly correlated to each other. They provide a more reliable estimate of the transducer's performance as a result. | ||
| + | Both training and test corpora can be accessed [https://github.swarthmore.edu/dmin1/ling073-kor/tree/master/corpus here]. | ||
===Trained Corpora=== | ===Trained Corpora=== | ||
| − | *kor.phrases.COURT.txt: | + | *kor.phrases.COURT.txt: 35.71% |
| − | *kor.phrases.GENESIS.txt: | + | *kor.phrases.GENESIS.txt: 38.10% |
| − | *kor.phrases.HIROHITO.txt: | + | *kor.phrases.HIROHITO.txt: 44.27% |
| − | *kor.phrases.ROH.txt: | + | *kor.phrases.ROH.txt: 83.12% |
| − | *kor.phrases.STALIN.txt: | + | *kor.phrases.STALIN.txt: 24.89% |
| − | *kor.phrases.WIKI.txt: | + | *kor.phrases.WIKI.txt: 28.15% |
===Test Corpora=== | ===Test Corpora=== | ||
| − | * | + | *Sample (0): 18.65% |
| − | * | + | *Sample (1): 18.49% |
| − | * | + | *Sample (2): 18.53% |
| − | * | + | *Sample (3): 17.96% |
| − | + | *Sample (4): 18.20% | |
| + | |||
| + | It seems that the low coverage rate of random wikipedia samples largely come from one letter words that are erroneously | ||
| + | regarded as an independent morpheme. For instance, consider the following result of sample0.txt Also, | ||
| + | the use of hangul.lexc resulted in numerals and other characters to be unrecognized by the transducer, decreasing coverage. I am working to fix this issue. | ||
| + | |||
| + | |||
| + | <pre> | ||
| + | Number of tokenised words in the corpus: 34831 | ||
| + | |||
| + | Coverage: 18.65% | ||
| + | |||
| + | Top unknown words in the corpus: | ||
| + | |||
| + | |||
| + | 102 는 | ||
| + | |||
| + | 91 은 | ||
| + | |||
| + | 77 의 | ||
| + | |||
| + | 65 되었다 | ||
| + | |||
| + | 56 을 | ||
| + | |||
| + | 55 때문에 | ||
| + | |||
| + | 49 후 | ||
| + | |||
| + | 46 했다 | ||
| + | |||
| + | 46 위해 | ||
| + | |||
| + | 45 1 | ||
| + | |||
| + | 44 하였다 | ||
| + | |||
| + | 44 또는 | ||
| + | |||
| + | 40 두 | ||
| + | |||
| + | 40 에 | ||
| + | |||
| + | 39 일본 | ||
| + | |||
| + | 38 하는 | ||
| + | |||
| + | 36 가 | ||
| + | |||
| + | 35 첫 | ||
| + | |||
| + | 35 약 | ||
| + | |||
| + | 34 로 | ||
| + | |||
| + | Translation time: 1.5711495876312256 seconds | ||
| + | </pre> | ||
==Precision and Recall== | ==Precision and Recall== | ||
| − | ===Using | + | The annotated set(wiki-samples/annotatedcorpus.txt) can be found [https://github.swarthmore.edu/dmin1/ling073-kor/blob/master/corpus/wiki-samples/hand_annotated.txt here]. |
| − | *Precision: | + | |
| − | *Recall: | + | ===Using An Annotated Sample from Wikiepedia Dump=== |
| + | *Precision: 95.00000% | ||
| + | *Recall: 24.35897% | ||
| + | |||
| + | ==Discussion== | ||
| + | I observed that most of the errors come from either (1) lemmas not yet added or (2) failure to analyze different verb forms and alterations. While (1) is a task that can be automated, (2) means that an improved analysis of alternating verb forms are required. | ||
| + | |||
| + | =Post-Evaluation Steps= | ||
| + | Here, I document steps I took to improve the transducer after the first evaluation. Also, I include the results of the second round of evaluation. | ||
| + | |||
| + | ==Resolving twol rule conflicts== | ||
| + | Because many of the morphological change I tried to implement had similar patterns, adding them one by one resulted in a set of rules that had many overlaps and conflicts. I trimmed the unnecessary ones so that there is no conflict. | ||
| + | |||
| + | ==Analysis of Failure Patterns== | ||
| + | The following is an output after I ran aq-covtest on a randomly chosen 30000 word corpus(from Wiki dump). | ||
| + | <pre> | ||
| + | Number of tokenised words in the corpus: 49353 | ||
| + | Coverage: 22.11% | ||
| + | Top unknown words in the corpus: | ||
| + | 103 formula | ||
| + | 83 는 | ||
| + | 77 의 | ||
| + | 77 두 | ||
| + | 71 은 | ||
| + | 68 위해 | ||
| + | 68 을 | ||
| + | 65 했다 | ||
| + | 63 하는 | ||
| + | 60 에 | ||
| + | 55 하지만 | ||
| + | 55 의해 | ||
| + | 55 통해 | ||
| + | 53 있으며 | ||
| + | 53 후 | ||
| + | 49 이러한 | ||
| + | 47 1 | ||
| + | 45 가 | ||
| + | 45 한편 | ||
| + | 42 기원전 | ||
| + | Translation time: 2.276514768600464 seconds | ||
| + | </pre> | ||
| + | "Formula" is unrecognized as English alphabet is not supported by the transducer. Also, the top 2nd, 3rd and 5th words are | ||
| + | particles that attach to nouns. Since I have added them all to the lexicon, and they have no alternation beside simple vowel vs consonant ending contrast, it must be that the noun is not analyzed properly. I suspect that the noun is written in foreign alphabets(English, Katakana or Hiragana, Chinese Characters, Arabic numerals and etc), and the mixture of Hangul and foreign alphabet prompts the transducer to separate the noun and the particle, which leads to the particle(while not recognized as a particle because the transducer is able to analyze it only when it comes after a known noun.) | ||
| + | |||
| + | I have added Arabic numerals in the hangul.lexc file and recompiled to address issue, but the analysis remains largely the same. I am in the process of figuring out what might be the issue here. | ||
=Repository= | =Repository= | ||
| − | [https://github.swarthmore.edu/dmin1/ling073-kor | + | [https://github.com/numeric1/kor-transducer Public Repository] |
| + | |||
| + | [https://github.swarthmore.edu/dmin1/ling073-kor Swarthmore Github] | ||
[[Category:sp17_FinalProjects]] | [[Category:sp17_FinalProjects]] | ||
Latest revision as of 03:40, 13 May 2017
This page provides an overview and an evaluation of Korean Finite State Transducer I developed.
Motivation
For the final project, I decided to work on Finite State Transducer for Korean. Although there are several open-sourced POS tagger(Kkoma, HanNanum, and Komoran), none of them are purely rule-based; HanNanum and Komoran uses Hidden Markov Models(statistical method for making inferences about sequential data), and Kkoma requires the usage of a custom relational database.
Although the techniques employed in the aforementioned systems are crucial in achieving state-of-the-art performance, they have certain drawbacks. First, even after achieving extremely high performance, the probabilistic nature of such techniques make it very hard to identify what aspect of the system actually encodes the linguistic pattern. Thus, when an error occurs, it is usually impossible to correct the system manually. On the other hand, this is the development scheme for rule-based systems.
Also, apertium module for Korean has not been developed yet. Therefore, I decided to implement a transducer for Korean.
Overview
The development of this transducer largely consisted of two parts. The first challenge I encountered was to make the apertium pipeline work for Hangul(Decompose-Compose Step). This is the same problem I had while working on Jeju. While I only bypassed the problem in Jeju transducer, this issue is completely solved in this project. The second part consists of normal transducer development tasks: writing rules, adding lemmas, preparing corpora, evaluating, and repeating. Also, note that due to the large size of hangul.lexc, it is recommended that the user compiles it in a machine with at least 16gb of RAM or enable swap partition.
Decompose-Compose Step
Hangul, writing system for Korean, blocks 2 or 3 letters into a syllable-block, where each letter occupies the position of onset, nucleus, and optionally, coda. While Hangul is an alphabet, this blocking system requires that all legal combination of Hangul letters into a syllable encoded in a separate Unicode.
While developing a transducer for Jeju, this meant that I had to six thousands of Unicode letters to my lexc file. Not only did this make compiling very slow, but it did also led to restriction of morphological analysis. For instance, consider the following case:
- Vowel Ending + (Topic Marker) -> 는
- Consonant Ending + (Topic Marker) -> 은
To properly analyze this, it would be necessary to look at the last sound of the previous word. However, since this information is always encoded with extra information about the other letters that contain one syllable. Thus, it results in a massive explosion of matchings needed to capture the whole set.
However, in the new approach I matched a syllable to its decomposed letters. Although I needed still have one large separate hangul.lexc file with all such possible matchings, I only needed to compile once. More importantly, I allowed me to refer to the last letter of the decomposition, making writing matching rules much easier and natural. An important implementation detail is that in the hangul.lexc file each syllable, based on the number of letters constructing it, was given a carefully chosen weight. 1-letter syllable is given weight 0.8, 2-letter 1.4 3-letter 2.1. The weights are chosen so that larger syllables are preferred.
This was to ensure that in the compose step, only the correct composition is applied. For instance, 가나 will be flattened to ㄱㅏㄴㅏ, and there are many ways to arrange this: 간ㅏ,ㄱ ㅏ나ㅡ,ㄱㅏ나, etc. Now we see that ㄱㅏㄴㅏ has the unique minimum weight of 2.8, and is chosen in the decompose step. Since incorrect forms necessarily break up a larger composition into smaller ones, they have larger weight than the unique correct form.
- Is Hangul a uniquely decodable code?
Structure and Development
Finding corpora was easy. In particular, I processed Korean Wikipedia dump into a large corpus, from which I drew several random samples.
Most of the morphology was implemented in lexc and twol file. In this implementation of Korean POS analyzer, I was able to analyze most of noun morphology correctly. However, as there were multiple level of suffixes that attaches to verbs in Korean, the analysis and construction of verb alteration was not easy, as it involved multiple levels of suffixing and vowel harmony.
Evaluation
This section contains the results of the first evaluation I conducted after a preliminary development.
Coverage of corpora
Trained Corpora refers to the hand-assembled corpora that I used during development cycle to find out which forms were not analyzed by the transducer. Thus, coverage for them is not a good measure of the transducer's performance.(because I have changed the transducer so that their coverages improves.)
On the other hand, each test corpus is a set of 1200 words that I have fetched randomly from Korean Wikipedia.(I ran $cat corpus/wiki.txt |sort -Ru | head -n 1200 > sample.txt ) There might be some overlaps between them, but it is unlikely that they are significantly correlated to each other. They provide a more reliable estimate of the transducer's performance as a result.
Both training and test corpora can be accessed here.
Trained Corpora
- kor.phrases.COURT.txt: 35.71%
- kor.phrases.GENESIS.txt: 38.10%
- kor.phrases.HIROHITO.txt: 44.27%
- kor.phrases.ROH.txt: 83.12%
- kor.phrases.STALIN.txt: 24.89%
- kor.phrases.WIKI.txt: 28.15%
Test Corpora
- Sample (0): 18.65%
- Sample (1): 18.49%
- Sample (2): 18.53%
- Sample (3): 17.96%
- Sample (4): 18.20%
It seems that the low coverage rate of random wikipedia samples largely come from one letter words that are erroneously regarded as an independent morpheme. For instance, consider the following result of sample0.txt Also, the use of hangul.lexc resulted in numerals and other characters to be unrecognized by the transducer, decreasing coverage. I am working to fix this issue.
Number of tokenised words in the corpus: 34831 Coverage: 18.65% Top unknown words in the corpus: 102 는 91 은 77 의 65 되었다 56 을 55 때문에 49 후 46 했다 46 위해 45 1 44 하였다 44 또는 40 두 40 에 39 일본 38 하는 36 가 35 첫 35 약 34 로 Translation time: 1.5711495876312256 seconds
Precision and Recall
The annotated set(wiki-samples/annotatedcorpus.txt) can be found here.
Using An Annotated Sample from Wikiepedia Dump
- Precision: 95.00000%
- Recall: 24.35897%
Discussion
I observed that most of the errors come from either (1) lemmas not yet added or (2) failure to analyze different verb forms and alterations. While (1) is a task that can be automated, (2) means that an improved analysis of alternating verb forms are required.
Post-Evaluation Steps
Here, I document steps I took to improve the transducer after the first evaluation. Also, I include the results of the second round of evaluation.
Resolving twol rule conflicts
Because many of the morphological change I tried to implement had similar patterns, adding them one by one resulted in a set of rules that had many overlaps and conflicts. I trimmed the unnecessary ones so that there is no conflict.
Analysis of Failure Patterns
The following is an output after I ran aq-covtest on a randomly chosen 30000 word corpus(from Wiki dump).
Number of tokenised words in the corpus: 49353 Coverage: 22.11% Top unknown words in the corpus: 103 formula 83 는 77 의 77 두 71 은 68 위해 68 을 65 했다 63 하는 60 에 55 하지만 55 의해 55 통해 53 있으며 53 후 49 이러한 47 1 45 가 45 한편 42 기원전 Translation time: 2.276514768600464 seconds
"Formula" is unrecognized as English alphabet is not supported by the transducer. Also, the top 2nd, 3rd and 5th words are particles that attach to nouns. Since I have added them all to the lexicon, and they have no alternation beside simple vowel vs consonant ending contrast, it must be that the noun is not analyzed properly. I suspect that the noun is written in foreign alphabets(English, Katakana or Hiragana, Chinese Characters, Arabic numerals and etc), and the mixture of Hangul and foreign alphabet prompts the transducer to separate the noun and the particle, which leads to the particle(while not recognized as a particle because the transducer is able to analyze it only when it comes after a known noun.)
I have added Arabic numerals in the hangul.lexc file and recompiled to address issue, but the analysis remains largely the same. I am in the process of figuring out what might be the issue here.
