Word prediction using language models

• Thesis title in Czech: Word prediction using language models
• Thesis title in English: Word prediction using language models
• Key words: word prediction, language model, autocompletion, assistive technology
• English key words: word prediction, language model, autocompletion, assistive technology
• Academic year of topic announcement: 2011/2012
• Thesis type: Bachelor's thesis
• Thesis language: angličtina
• Department: Institute of Formal and Applied Linguistics (32-UFAL)
• Supervisor: Mgr. Martin Popel, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 08.11.2011
• Date of assignment: 10.11.2011
• Confirmed by Study dept. on: 01.12.2011
• Date and time of defence: 06.09.2012 10:00
• Date of electronic submission: 03.08.2012
• Date of submission of printed version: 03.08.2012
• Date of proceeded defence: 06.09.2012
• Opponents: Mgr. Michal Novák, Ph.D.

Guidelines

The motivation is to reduce the number of keystrokes and the time needed for writing a text in a given natural language. The software should be modular, so it could be used for various keyboard models (phone keypad, QWERTY) and purposes (text editors, mobile devices, special devices for people with disabilities). The implementation will be based on large language models (n-gram based or trigger based with various smoothing techniques) combined with user-defined dictionaries. A simple GUI component will be implemented to allow testing the word prediction. The thesis should contain an analysis of the problem and possible approaches as well as an evaluation (showing keystrokes per character, LM perplexity, or empirical speedup).

References

Christopher D. Manning, Hinrich Schütze. Foundations of Statistical Natural Language Processing. Cambridge, Mass.: MIT Press, 1999.

Hisham Al-Mubaid, Ping Chen. Application of word prediction and disambiguation to improve text entry for people with physical disabilities (assistive technology). International Journal of Social and Humanistic Computing 2008 -- Volume 1, Number 1, 10--27.

Keith Trnka, John McCaw, Debra Yarrington, Kathleen F. McCoy, and Christopher Pennington. 2009. User Interaction with Word Prediction: The Effects of Prediction Quality. ACM Trans. Access. Comput. 1, 3, Article 17 (February 2009), 34 pages. DOI=10.1145/1497302.1497307 http://doi.acm.org/10.1145/1497302.1497307

Preliminary scope of work

Základní ideou je minimalizovat počet úhozů pro napsání textu v daném jazyce na daném modelu klávesnice (devítitlačítková z mobilních telefonů či počítačová Qwerty), tedy naimplementovat systém podobný T9 či spíše iTap. Systémy používané v současnosti (včetně T9 a iTap) jsou navržené spíše jednoduše a mají paměťová omezení, aby se vešly i do (starších) mobilů. Krom většího slovníku s přidruženými pravděpodobnostmi se nabízí i další možná vylepšení: opravy překlepů, návrh slova, i pokud není obsaženo ve slovníku (dle pravděpodobností dvojic a trojic písmen), využití následujícího kontextu, pokud se edituje uprostřed již napsaného textu, atd. Součástí bakalářské práce bude i vyhodnocení podle několika metrik – krom průměrného počtu úhozů na písmeno a dalších automatických metrik by se měla zhodnotit i uživatelská přívětivost a skutečný čas psaní (příliš mnoho nabízených doplnění lidi spíš zpomaluje, průměrným uživatelům vyhovuje spíše jednodušší byť pomalejší systém atd.). Podle zájmu může být projekt cílen na použití v mobilech, chytrých textových editorech či jako pomůcka pro tělesně postižené (píšící jedním prstem, pohyby očí apod.). Program bude využívat statistických metod (vyhlazování) a jazykových modelů natrénovaných na velkém množství textu v daném jazyce.

* Předpokládá se modulární návrh s dobře definovaným API. Některé moduly (např. optimalizace na konkrétní klávesnici, GUI či zakomponování do existujícího textového editoru) není nutné zpracovávat do detailu, hlavní je vnitřní logika nabízení nejpravděpodobnějších pokračování (optimální počet nabízených variant a jejich délek).
* Projekt je možné koncipovat
o buď spíše prakticky – vybrat si cílovou skupinu uživatelů a vytvořit kompletní software, který by jim pomohl,
o nebo spíše teoreticky – porovnat různé jazykové modely, prozkoumat korelaci perplexity a počtu úhozů na písmeno či dalších metrik.