TL;DR
This paper introduces a novel method using m-th order Markov models to detect and correct three types of character errors (substitution, deletion, insertion) in Japanese "bunsetsu" (syntactic units) and English words. The approach leverages the assumption that correct character sequences have higher Markov probabilities than erroneous ones, demonstrating effectiveness particularly for substitution and insertion errors in Japanese.
What Problem Does This Paper Address?
Inputting natural language into computers, whether through optical character recognition (OCR) or speech recognition, often results in errors. These errors can manifest as characters being wrongly substituted, deleted, or inserted. While existing methods have focused on substitution errors, detecting and correcting deletions and insertions, especially in languages like Japanese with complex character sets and non-segmented sentence structures, remains a significant challenge. This paper aims to bridge this gap by proposing a unified approach for all three error types.
Methods
The core of the proposed method relies on m-th order Markov models. The fundamental assumption is that the probability of a sequence of characters belonging to a correct "bunsetsu" or word is significantly higher than that of an erroneous sequence.
- Error Detection: The method identifies potential error locations and lengths by looking for sequences where the Markov probability drops below a critical threshold ($T$). Different procedures are outlined for detecting substitutions/insertions and deletions, leveraging the properties of Markov probabilities around the erroneous segment.
- Error Correction: Once errors are detected, the method attempts to correct them by comparing the Markov probabilities of potential correct replacements. For substitution and insertion errors, it replaces the erroneous segment with a candidate that yields the highest Markov probability. For deletion errors, it identifies the deleted segment and then uses a similar Markov probability comparison to find the best replacement.
- Language Specifics: The approach is applied to Japanese "kanji-kana" character chains (termed "J-bunsetsu") and English alphabet chains ("E-word"). For Japanese, it uses 2nd-order Markov models, while for English, it explores both 2nd and 3rd-order models.
Datasets
The paper does not explicitly mention specific datasets for training Markov models. However, the experimental evaluation uses:
- Japanese Newspaper Articles: 70 issues of a daily Japanese newspaper were used for evaluating the methods on "bunsetsu."
- English Newspaper Articles: 5 issues of a daily English newspaper were used for evaluating the methods on English words.
- Prepared Error Corpora: For experimental evaluation, 800 "bunsetsu" were prepared for each of the different error types (substitution, deletion, insertion) in Japanese.
Key Insights and Ideas
- Unified Approach for Error Types: The paper successfully proposes a framework that can handle substitution, deletion, and insertion errors within a single Markov model-based approach, which was a limitation of prior work.
- Markov Probability as an Error Indicator: The core insight is that erroneous character sequences exhibit a statistically lower Markov probability compared to correct ones. This principle is effectively used to pinpoint error locations and assess correction candidates.
- Japanese vs. English Performance: The method shows particularly strong performance for substitution and insertion errors in Japanese "bunsetsu." This suggests that the non-segmented nature and character complexity of Japanese might be more amenable to this Markov-based approach for these error types.
- Combinatorial Approach for English: For English words, a purely Markov-model-based approach showed limitations, especially for deletion errors. The paper highlights the effectiveness of combining the proposed Markov model correction with a traditional spell checker (Ispell) to achieve better overall error detection and correction.
Key Results
- Detection Accuracy: The maximum "Relevance Factor" (P) and "Recall Factor" (R) for detecting erroneous characters wrongly inserted or substituted in Japanese "bunsetsu" were high (97-99%). Detection of deleted characters was less accurate (38-49%).
- Correction Accuracy: For Japanese "bunsetsu," correction accuracy for insertion and substitution errors reached 92-98% (P) and 91-97% (R). Correction of deleted characters was less effective.
- English Word Performance: The method showed moderate results for English words, with detection of insertions/substitutions being better than deletions.
- Combinatorial English Improvement: Combining the Markov model correction with Ispell significantly improved error detection and correction for English words, especially when using a 3rd-order Markov model.
- Efficiency: The paper notes that it takes about 10 milliseconds for error detection and 6 seconds for error correction of "bunsetsu" on average.
Limitations and Future Work
- Deletion Error Correction: The paper acknowledges that the proposed method is not as effective for detecting and correcting deleted characters in Japanese "bunsetsu." More efficient methods are suggested for this specific error type.
- English Word Limitations: While the combinatorial approach with Ispell improved English word correction, the standalone Markov model approach had limitations, particularly for deletion errors.
- Critical Value Tuning: The accuracy of both detection and correction is dependent on the critical value ($T$) of Markov probabilities, which needs to be carefully tuned.
- Future Work: The authors suggest exploring more efficient methods for deletion error correction in Japanese and further investigating the combinatorial approach for English. The evaluation was primarily conducted for cases of length k=1,2, implying a need for broader evaluation across different error lengths.
Summary updated