UNIVERSITA DEGLI STUDI DI TRENTO - Marco Ronchettilatemar.science.unitn.it/pod/docs/tesi.pdf · gli...

UNIVERSITA DEGLI STUDI DI TRENTOFacolta di Scienze Matematiche, Fisiche e Naturali

Corso di Laurea in INFORMATICA

TESI

ANALISI E SVILUPPO DI UN SISTEMA DI

SCRITTURA FACILITATA PER UTENTI DISABILI

BASATO SU MODELLI DEL LINGUAGGIO

RELATORE: LAUREANDO:

prof. Marco Ronchetti Alberto Zanella

anno accademico 2011 - 2012

Indice

1 Introduzione 1

2 Strumenti di predizione delle parole 52.1 Introduzione al problema . . . . . . . . . . . . . . . . . . . . . . . 52.2 Utilizzo da parte di utenti con difficolta motorie . . . . . . . . . . 82.3 Utilizzo da parte di utenti con difficolta di apprendimento . . . . 142.4 Altri impiegi dei sistemi di predizione . . . . . . . . . . . . . . . . 17

3 Definizione del problema, terminologia e Stato Dell’Arte deisistemi di Predizione 193.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Definizione del problema e terminologia adottata . . . . . . . . . 20

3.2.1 Esempio di predizione senza contesto . . . . . . . . . . . . 233.2.2 Esempio di predizione con contesto . . . . . . . . . . . . . 24

3.3 Sistemi che non fanno uso di contesto . . . . . . . . . . . . . . . . 253.3.1 Lista di parole pesate a dizionario aperto . . . . . . . . . 263.3.2 Lista di parole a dizionario costruito dall’utente . . . . . . 263.3.3 Frequenza di vicinanza fra lettere . . . . . . . . . . . . . . 273.3.4 Utilizzo della cache con dizionario aperto . . . . . . . . . . 28

3.4 Sistemi di predizione basati sul contesto . . . . . . . . . . . . . . 283.4.1 Lista di parole e di coppie di parole pesate a dizionario

aperto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.4.2 Utilizzo dei modelli del linguaggio . . . . . . . . . . . . . 303.4.3 Cenni su possibili approcci machine-learning e basati sul-

l’analisi del linguaggio (NLP) . . . . . . . . . . . . . . . . 31

3.5 Principali prodotti destinati all’utente finale . . . . . . . . . . . . 323.5.1 Kurzweil 3000 . . . . . . . . . . . . . . . . . . . . . . . . . 333.5.2 TypingAssistant . . . . . . . . . . . . . . . . . . . . . . . 353.5.3 Click-N-Type . . . . . . . . . . . . . . . . . . . . . . . . . 363.5.4 Chewing Word . . . . . . . . . . . . . . . . . . . . . . . . 373.5.5 DiCOM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.5.6 Farfalla Editor . . . . . . . . . . . . . . . . . . . . . . . . 393.5.7 Google Scribe . . . . . . . . . . . . . . . . . . . . . . . . . 413.5.8 Co:Writer . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.5.9 Read&Write . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 Predizione basata sui Modelli del Linguaggio 474.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.2 Modelli del linguaggio . . . . . . . . . . . . . . . . . . . . . . . . 484.3 Simbologia e convenzioni . . . . . . . . . . . . . . . . . . . . . . . 504.4 La necessita dell’approssimazione: Gli N-grammi . . . . . . . . . 504.5 Valutazione di un modello . . . . . . . . . . . . . . . . . . . . . . 53

4.5.1 Valutazione estrinseca mediante i sistemi di predizione . . 544.5.2 Perplexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.6 Miglioramenti del modello: Smoothing e Back-Off . . . . . . . . . 594.6.1 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.6.2 Back-off ed interpolazione . . . . . . . . . . . . . . . . . . 63

4.7 Il superamento di un approccio basato soltanto sui modelli dellinguaggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

5 Il sistema di scrittura facilitata PredictEdit 675.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 675.2 Sviluppo del modello del linguaggio . . . . . . . . . . . . . . . . 69

5.2.1 La costruzione del corpus . . . . . . . . . . . . . . . . . . 695.2.2 Dal corpus al Modello del Linguaggio in formato ARPA . . 715.2.3 Dal modello del linguaggio in formato ARPA alla struttura

dati per la predizione . . . . . . . . . . . . . . . . . . . . . 735.3 Sviluppo dei motori di predizione . . . . . . . . . . . . . . . . . . 76

5.3.1 L’interfaccia IPredictor . . . . . . . . . . . . . . . . . . . . 765.3.2 Lo sviluppo del predittore locale NGPredictor . . . . . . . 765.3.3 Lo sviluppo del client per Google Scribe (GSPredictor) . . 81

5.4 Sviluppo dell’editor PredictEdit . . . . . . . . . . . . . . . . . . . 835.5 Il PredictiOnDemand . . . . . . . . . . . . . . . . . . . . . . . . 89

5.5.1 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . . 905.5.2 PredictiOnDemand, la predizione su richiesta . . . . . . . 92

5.5.3 Gli appModule ed il modulo per Microsoft Word . . . . . 935.5.4 UIAutomation per i controlli standard di Windows . . . . 955.5.5 Come avviene la previsione e l’immissione . . . . . . . . . 96

6 Valutazione del PredictEdit 1016.1 Misure impiegate . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026.2 La valutazione manuale . . . . . . . . . . . . . . . . . . . . . . . . 104

6.2.1 Esperimenti effettuati . . . . . . . . . . . . . . . . . . . . . 1046.2.2 Risultati dei test manuali . . . . . . . . . . . . . . . . . . 1046.2.3 Riscontri degli utenti sull’interfaccia grafica . . . . . . . . 106

6.3 La valutazione automatica . . . . . . . . . . . . . . . . . . . . . . 1066.3.1 Esperimenti effettuati . . . . . . . . . . . . . . . . . . . . . 1066.3.2 Risultati dei test automatici svolti su documenti di ambito

differente dal modello . . . . . . . . . . . . . . . . . . . . . 1086.3.3 Risultati dei test su documenti appartenenti all’europarl . 109

7 Conclusioni e sviluppi futuri 113

Ringraziamenti 117

Bibliografia 119

CAPITOLO 1

Introduzione

Molte persone nel Mondo, grazie all’introduzione delle macchine da scri-

vere hanno avuto la possibilita per la prima volta di sperimentare la comunica-

zione scritta. Per molti, infatti, e impossibile raggiungere un livello di precisione

nell’uso della mano tale da renderli capaci di utilizzare una penna.

Grazie all’evoluzione della tecnologia ed alla nascita del Personal Compu-

ter, che elabora le informazioni in tempo reale, le possibilita di offrire un servizio

di scrittura facilitata per aiutare molti piu utenti e diventato realistico.

Negli anni ’80 si sono diffusi i primi sistemi di scrittura per persone con

disabilita gravi che facevano uso di sensori a switch (acceso o spento). Essi

mostrano sullo schermo la frase che l’utente sta componendo ed una griglia con-

tenente le diverse lettere. Un selettore si sposta di continuo fra le varie celle della

griglia. Quando il cursore arriva alla lettera desiderata l’utente attiva lo switch

(mediante le palpebre, il fiato, la pressione di un pulsante o altro) ed il carattere

viene aggiunto.

Tali sistemi sono pero laboriosi e scomodi se non viene offerta all’utente una

Introduzione 2

qualche forma di completamento automatico. Inoltre vi sono altre categorie di

persone che hanno una mobilita minima o che sono soggette ad altre difficolta,

come la dislessia.

Comprendendo queste necessita, gia a partire dalla meta degli anni ’70, con la

diffusione dei primi Personal Computer, si e cercato di sviluppare dei programmi

che offrissero un servizio di previsione delle parole.

Quando legge oppure quando ascolta una conversazione, l’Uomo ha la

capacita di inferire la parola successiva grazie al contesto della frase, all’argomento

del testo o della conversazione. Con un sistema di previsione delle parole si cerca

di far svolgere alla macchina un compito simile.

Lo scopo e quello di indovinare il termine pensato dall’utente, per poterlo pro-

porre a schermo, evitando che questi lo debba scrivere per intero.

Non e pero facile per un software “indovinare” le parole che l’utente vorrebbe

immettere. Come nel caso del riconoscimento vocale non e il computer che non

e bravo a svolgere questo compito ma e l’uomo che e tremendamente capace in

questa attivita. Cosı i programmi di previsione delle parole propongono una lista

dei possibili termini da inserire. Se l’utente trova la parola pensata all’interno

della lista, egli la seleziona ed il computer la scrivera in automatico.

Nel tempo la ricerca in questo ambito ha esplorato varie modalita con cui

il problema della previsione delle parole puo essere risolto. Al momento gli appli-

cativi commerciali piu diffusi nel Mondo fanno uso dei Modelli del linguaggio o

anche dell’analisi della struttura grammaticale della frase. Sfortunatamente que-

sti software sono disponibili soltanto per la lingua inglese ed hanno un supporto

minimo all’Italiano.

Per questo noi proponiamo PredictEdit, uno strumento per la scrittura

facilitata mediante la previsione delle parole. Esso e disponibile in lingua Italiana

ed impiega, per suggerire i termini, un algoritmo basato sui modelli del linguaggio.

3

Tale sistema e stato sviluppato per venire incontro, primariamente, ad utenti con

difficolta nell’uso delle mani che impiegano per l’immissione del testo tastiere

speciali (ridotte o con scudo), strumenti di puntamento alternativi come trackball,

joystick o sensori e tastiere virtuali. I secondi destinatari del nostro software sono

gli utenti affetti da disturbi specifici di apprendimento (DSA) ed in particolare

le persone dislessiche e disfrasiche che necessitano di un aiuto per la corretta

digitazione delle parole.

All’interno del capitolo 2 presenteremo le tecnologie impiegate dalle per-

sone affette dai diversi problemi che possono trovare utile l’impiego di un software

di previsione delle parole. Discuteremo inoltre dei requisiti richiesti da ciascu-

na categoria di utenti. Nel capitolo 3, poi, definiremo in maniera piu formale

il problema della previsione delle parole e le tecniche impiegate per risolverlo.

Forniremo inoltre un quadro generale sugli strumenti disponibili, sia in Italiano

che in Inglese, e sugli approcci impiegati per fornire la predizione.

Nel capitolo 4 descriveremo nel dettaglio i Modelli statistici del Linguag-

gio, come sia possibile impiegarli per l’implementazione di un algoritmo di pre-

visione delle parole e come si possano valutare e migliorare gli strumenti basati

su di essi. Concluderemo il capitolo riportando i limiti di cui sono afflitti gli

strumenti di predizione basati soltanto su questi modelli ed i nuovi rami in cui si

sta concentrando la ricerca.

All’interno del capitolo 5 introdurremo il PredictEdit, un software di pre-

visione delle parole studiato ed implementato per l’ambiente Microsoft Windows.

Inizieremo presentando il motore di predizione e l’algoritmo su cui si basa. Spo-

steremo poi la nostra attenzione sulle due applicazioni lato utente. La prima,

il PredictEdit appunto, e un editor di testi molto semplice che offre la funzione

di previsione delle parole. Procederemo poi presentando il secondo servizio in-

novativo, il PredictiOnDemand. Esso porta il predittore fuori da un programma

Introduzione 4

dedicato e lo rende disponibile in tantissimi applicativi Windows come Microsoft

Word, WordPad, Notepad, Internet Explorer e Firefox.

Nel capitolo 6 illustreremo le valutazioni, sia automatiche che manuali, svolte

sul PredictEdit e ne discuteremo i risultati aiutandoci con grafici e dati prove-

nienti dai rilevamenti. Concluderemo descrivendo quali potrebbero essere i futuri

miglioramenti sia del motore di predizione che dell’interfaccia utente.

CAPITOLO 2

Strumenti di predizione delle parole

2.1 Introduzione al problema

Quando legge oppure quando ascolta una conversazione l’Uomo ha la ca-

pacita di inferire la parola successiva grazie al contesto della frase, all’argomento

del testo o della conversazione. Non si e certi della frase che verra detta o del-

la risposta che l’interlocutore dara, ma quando questi inizia a pronunciare una

parola, molto spesso e facile intuirla prima che questi la termini.

Ci si puo rendere facilmente conto di questo lavoro, che inconsciamente

ciascuno di noi compie, quando riusciamo a cogliere frammenti di discorsi anche

da sorgenti molto disturbate oppure distanti da noi.

Questa capacita sta anche alla base di una buona velocita nella lettura a

prima vista. Se fosse necessario analizzare tutte le lettere attentamente prima di

leggere una parola il processo sarebbe molto piu lento. Come riportato in [log],

“la percezione e la selezione delle corrispondenze auditive o grafiche si basa sul

co-testo e sul contesto in cui la parola occorre: possono anche in questo caso

Strumenti di predizione delle parole 6

intervenire correzioni basate sull’esperienza enciclopedica del lettore. Se, per

esempio, in un libro di cucina si incontra la parola �astronomia�, l’esperienza

del lettore propende per una correzione mentale della parola in �gastronomia�,

la cui occorrenza in quel contesto e assai piu probabile.”[ [log]]

Un software di predizione delle parole (o Word Predictor, in inglese) cerca

di simulare questo tipo di comportamento per velocizzare l’immissione del testo

a particolari categorie di utenti.

Non e pero facile per un software “indovinare” le parole che l’utente

vorrebbe scrivere. Come nel caso del riconoscimento vocale non e il computer che

non e bravo a svolgere questo compito ma e l’uomo che e tremendamente capace

in questa attivita.

Questo genere di programma viene utilizzato in abbinamento ad un soft-

ware di videoscrittura (solitamente a scelta dell’utente). Oltre ai consueti con-

trolli (la pagina, il cursore, le varie barre degli strumenti ecc.), sullo schermo

appare una finestra che elenca una lista di parole suggerite.

Come riportato in [HT02], ogni volta che l’utente inizia a scrivere una

parola, immettendo la prima lettera, il software filtra l’elenco scartando le parole

con iniziali diverse. L’elenco di termini viene quindi aggiornato. Se la parola

che si desidera immettere e presente nella lista, l’utente la seleziona, altrimenti

immette un altro carattere e la lista dei termini cambia. Questo processo continua

fino a che la parola e presente nella lista, oppure fino a che non sia stata digitata

completamente.

Strumenti piu avanzati permettono di scegliere fra diversi insiemi di paro-

le da utilizzare per la predizione. Tali insiemi di termini possono essere suddivisi

in base ad ambiti (Archeologia, Animali acquatici ecc.) oppure in base alla per-

sona che fara uso dello strumento (Primo ciclo scuola elementare, secondo ciclo

scuola elementare, medie, dizionario avanzato). Queste suddivisioni sono utili

7 Introduzione al problema

per adattare al meglio lo strumento alle specifiche necessita di chi sta scrivendo.

Alcuni prodotti, poi, adottano l’approccio dell’“open dictionary” (a di-

zionario aperto) permettendo di costruire ed arricchire un dizionario ausiliario di

termini personalizzati.

Nel prossimo capitolo discuteremo in maggior dettaglio gli aspetti tecnici

del problema, ne daremo una definizione piu formale e descriveremo le peculiarita

dei principali strumenti di predizione disponibili oggi sul mercato e le tecniche

utilizzate per svolgere il loro compito al meglio coniungando rapidita, leggerezza

e precisione nella predizione.

All’interno di questo capitolo, invece, ci occuperemo dell’efficacia di que-

sta categoria di applicativi e del loro impiego per consentire e velocizzare la scrit-

tura in diversi ambiti: dalle disabilita motorie alle difficolta di apprendimento e

di letto-scrittura ai nuovi ambiti di utilizzo legati alla mobilita.

Prima di procedere pero e utile un’ultima precisazione: per esigenze di

chiarezza e di sintesi verranno di seguito poste delle differenze di paragrafo fra

tecnologie adatte a persone con difficolta fisiche e a persone con difficolta di ap-

prendimento o di letto-scrittura. Bisogna tenere presente che spesso le categorie di

prodotti impiegate per alleviare il disagio si intersecano e che le problematiche del-

la singola persona possono essere molteplici e spesso difficilmente “incasellabili”

in categorie cosı ampie.

Un disabile con un handicap motorio molto grave puo necessitare di un

sintetizzatore vocale poiche, non essendo in grado di parlare comunica oralmente

tramite questa tecnologia. Un altro esempio potrebbe essere quello delle tastiere

ingrandite (solitamente utilizzate per consentire un miglior accesso ai tasti anche

a persone con difficolta motorie). Spesso queste vengono impiegate per persone

con disturbi nell’apprendimento: caratteri grandi e colori diversi per vocali e

consonanti possono essere d’aiuto nel velocizzare l’immissione.


2.2 Utilizzo da parte di utenti con difficolta motorie

Come descritto da [TH04] i primi sistemi di predizione delle parole furono

costruiti proprio per agevolare le persone che, a causa di problemi motori erano

impossibilitate a scrivere con la penna e dovevano quindi ricorrere alla battitura

a macchina o a videoterminale.

I progressi tecnologici hanno portato oggi alla presenza sul mercato di

prodotti che consentono la scrittura nelle situazioni di handicap piu diverse: dal-

le tastiere adattate agli strumenti per il puntamento oculare (Eye-tracker), dai

joystick ai software di riconoscimento vocale.

Abbiamo pensato di descrivere i benefici di un sistema di predizione nei

seguenti tre casi:

• Utilizzatori di tastiere fisiche

• Utilizzatori di tastiere virtuali con sistemi di puntamento alternativi

• Utilizzatori di software a scansione temporale

Alle prime due categorie appartengono persone con disabilita da lievi

a molto gravi, la terza categoria di utenti, solitamente, e costituita da persone

affette da SLA (Sclerosi Laterale Amiotrofica) o da sindromi Locked-In, situazioni

quindi molto difficili.

In questo breve escursus sono state volutamente omesse le tecnologie di

riconoscimento vocale. Tale categoria di prodotti rappresenta una soluzione mol-

to valida per un’immissione diretta delle parole. Purtroppo essi sono utilizzabili

soltanto da coloro che hanno complete capacita di pronuncia e un ottimo coor-

dinamento vocale. Essi non possono inoltre essere impiegati in ambito scolastico

(per ovvi motivi), in ambienti rumorosi o qualora sia necessario preservare la

9 Utilizzo da parte di utenti con difficolta motorie

privacy di cio che si scrive. Tuttavia sono stati effettuati alcuni tentativi di in-

tegrazione fra strumenti di predizione delle parole e strumenti di riconoscimento

vocale.1

Un altro ausilio molto impiegato e di seguito non trattato sono i comu-

nicatori simbolici. Essi consentono l’inserimento di parole su tastiera ridotta o,

prevalentemente, mediante elementi simbolici e immagini. Tali tecnologie (tecni-

camente chiamate C.A.A. ad immagini) si basano su strumenti parole o concetti

inseriti in “griglie” selezionabili mediante touchscreen, joystick o, nei casi piu

gravi, mediante controlli a scansione. In [THG] e presente una descrizione molto

dettagliata di uno dei sistemi piu avanzati di questo tipo. In questo caso specifico,

il software include uno strumento di predizione a dizionario manuale di base.

Utilizzatori di tastiere fisiche

Come riportato in [TH04] l’utilizzo di una tastiera da parte di una persona

con handicap motori e vincolata da un problema fisico e dunque, a differenza delle

difficolta di apprendimento, non e dipendente dalla complessita di cio che si vuole

scrivere ma dal numero di tasti che devono essere premuti.

Un sistema di predizione delle parole, in questa situazione, porta dei

miglioramenti solo se consente di ridurre in ogni situazione, anche in fase di

inserimento, il numero dei movimenti da compiere, siano essi tasti da premere o

spostamenti e click del mouse.

Spesso infatti anche il mouse viene sostituito da simulatori a tasti (tramite

frecce) o da trackball dato che l’utente non e in grado di dirigere il puntatore con

precisione tramite la periferica standard. Per questo e indispensabile predisporre

differenti modalita di inserimento delle parole.

1Ulteriori informazioni su http://www.donjohnston.com/products/dragon_naturally_spkg/index.html

http://www.donjohnston.com/products/dragon_naturally_spkg/index.html

http://www.donjohnston.com/products/dragon_naturally_spkg/index.html


In base poi al dispositivo di input utilizzato vi sono degli accorgimenti da

porre nello sviluppo del Word Predictor.

L’esempio piu classico di adattamento alle tastiere che viene proposto per aiutare

una persona con problemi motori e la tastiera a scudo. 2 Le tastiere di questo tipo

sono piu grandi di quelle normali, per questo spesso vengono chiamate “tastiere

espanse non programmabili”, cio permette all’utilizzatore di appoggiare il polso

e di “cadere” sui tasti.

Lo scudo e una “barriera” che viene inserita fra un tasto e l’altro e che evita

pressioni involontarie di un secondo tasto durante la digitazione. Le tastiere con

scudo solitamente sono dotate anche di un meccanismo anti ripetizione che evita

immissione continuata di una lettera nel caso di tremolii o spasmi della mano.

In questo caso il sistema di predizione delle parole dovra presentare un modo facile

per inserire i termini proposti, ad esempio permettendo l’immissione diretta dei

termini in lista tramite il tastierino numerico.

Altri esempi di adattamenti di tastiere sono le tastiere ridotte 3, di piccole

dimensioni, con tasti minuscoli e ravvicinati, molto sensibili alla pressione. Sono

adatte a soggetti affetti da distrofia muscolare o a quei disabili motori che hanno

conservato un buon controllo della motricita fine di una mano, ma che non sono

in grado di compiere con gli arti superiori movimenti sufficientemente ampi per

raggiungere i tasti di una tastiera normale o di esercitare pressioni che richiedano

una certa forza.[ [WEB]].

Spesso sono costituite da piu livelli attivabili mediante combinazioni tasti. Le

persone che ne fanno uso possono non necessitare di sistemi di predizione poiche

mantengono una discreta velocita di digitazione. In ogni caso, per essere utile in

2esempio di tastiera a scudo http://www.superabile.it/web/it/CANALI_TEMATICI/Ausili/Gli_Ausili_e_le_Aziende/Comunicare_e_ausili_tecnologici/info465992533.html

3Esempio di tastiera ridotta http://www.helpicare.com/prodotto/winmini-usb

http://www.superabile.it/web/it/CANALI_TEMATICI/Ausili/Gli_Ausili_e_le_Aziende/Comunicare_e_ausili_tecnologici/info465992533.html



http://www.helpicare.com/prodotto/winmini-usb


questi casi, il word predictor deve consentire delle shortcut combinate (ad esempio

con il tasto Ctrl+ il numero della parola presente nella finestra della lista parole).

Cio e utile dato che le tastiere di questa categoria non comprendono il tastierino

numerico.

Infine possono essere utilizzate tastiere espanse programmabili. Sono si-

mili alle tastiere con scudo ma presentano tasti aggiuntivi programmabili dall’u-

tente.

Utilizzatori di tastiere virtuali con sistemi di puntamento alternativi

Coloro che non possono utilizzare tastiere fisiche o che trovano troppo len-

ta questa situazione ricorrono alle cosiddette tastiere virtuali (tastiere a schermo

o Virtual Keyboard in inglese).

Tali software possono contenere un numero ridotto di caratteri (ad esem-

pio soltanto le lettere), ma solitamente sono una rappresentazione fedele delle

tastiere tradizionali. Esse possono essere impiegate mediante mouse o tramite

qualunque strumento di facile uso per l’utente in grado di spostare e gestire il

puntatore sullo schermo.

Esempi di dispositivi speciali che svolgono questo compito sono touch screen,

joystick, sensori e software a controllo facciale e molti altri. Degno di nota e il

rivoluzionario prodotto italiano faceMOUSE [SPPC06]4.

In quest’ultimo caso, ad esempio, tramite spostamenti di una parte del corpo

di cui l’utente ha liberta di movimenti (un esempio potrebbero essere piccoli

movimenti facciali) e possibile spostare il puntatore sullo schermo nelle quattro

direzioni.

Spesso in questi casi il click (la conferma) e temporizzato (ossia si attiva se l’utente

non sposta il cursore per un certo tempo).

4faceMOUSE http://www.aidalabs.com/SitoAIDA2009/FaceMOUSE.html

http://www.aidalabs.com/SitoAIDA2009/FaceMOUSE.html


Come detto non si puo dare per scontato che le tastiere a schermo com-

prendano tutti i tasti contenuti nelle tastiere tradizionali e dunque non si puo

dare per scontato che l’utente possa ricorrere alle shortcut. Oltre a cio spes-

so e complesso svolgere combinazioni di tasti perche esse richiedono puntamenti

multipli.

Cio che e necessario ridurre, in questo caso, tramite il predittore e lo sforzo ed

il tempo di puntamento in una determinata zona dello schermo. Per questo il

predittore di parole deve prevedere la possibilita di “cliccando” in zone vicine alla

parola che si vuole scegliere, quando presente nella lista dei termini, e di rendere

ben visibile l’area entro la quale portare il puntatore per effettuare la selezione.

Molti word predictor presentano finestre suddivise in “zone”, a ciascun

termine nella lista di predizione corrisponde una zona su cui l’utente puo portare

il puntatore e cliccare.

Alcuni dispositivi di puntamento dedicati (come il faceMOUSE) integrano

gia una tastiera virtuale ed un predittore di base nel prodotto per consentire di

operare immediatamente.

Utilizzatori di software a scansione temporale

Fino ad ora abbiamo considerato utenti che potevano, grazie a diverse

tecnologie, adoperare programmi standard del sistema operativo Windows. Un

buon predittore integrato ad un editor di testi poteva essere indipendente e non

disegnato appositamente per gli utenti.

Nel caso dei sistemi a scansione questo non e possibile. Un sistema a

scansione e simile ad una tastiera virtuale ma con la differenza che l’utente, a

causa di una disabilita grave, non e in grado di spostare il cursore ma solo di

compiere una scelta di tipo acceso/spento (si/no) tramite uno switch di vario


genere (a pressione palmare, a soffio, a battito degli occhi, a emissione tonale

ecc.). 5

La tastiera a schermo (solitamente minimale e contenente soltanto i ca-

ratteri alfabetici, lo spazio e l’enter) si presenta all’utente in forma di griglia.

Una per volta le righe continuano a venire selezionate a scansione temporale

(ad esempio una ogni 2 secondi o una ogni 5 secondi in base alle difficolta della

persona).

Qualora l’utente voglia immettere un simbolo presente in una delle righe dovra

compiere il gesto convenuto (battito di palpebre, soffio ecc.). A questo punto

la scansione procede per ognuno degli elementi contenuti all’interno della riga.

Quando sullo schermo viene evidenziato il controllo desiderato l’utente ripete il

comando di selezione ed in tal modo avviene l’inserimento.

In questa situazione il predittore deve essere gia integrato nel software

di gestione. Cio e indispensabile perche le parole del predittore devono essere

disponibili nella griglia di selezione. L’esigenza di accelerare il processo di inseri-

mento mediante suggerimenti in queste situazioni e davvero molto sentita. Spesso

l’utente utilizza immagini per esprimere necessita, sentimenti o altro. I princi-

pali software a scansione integrano qualche forma di predizione. Un esempio lo

troviamo in EyeClick 6 prodotto dagli stessi autori di faceMOUSE. I sistemi a

scansione integrano quasi sempre un motore di sintesi vocale che legge i messaggi

dell’utente.

Secondo quanto riportato in [TH04] l’utilizzo da parte di persone con

difficolta motorie di uno strumento di predizione (Co:Writer) porta un migliora-

mento nei due casi di persone con velocita di scrittura piu lenta: “Van e Sam sono

i due studenti che hanno mostrato i miglioramenti maggiori in termini di parole

5Esempio di software a scansione http://www.ausili.com/caa7.htm6EyeClick http://www.aidalabs.com/SitoAIDA2009/EyeClick.html

http://www.ausili.com/caa7.htm

http://www.aidalabs.com/SitoAIDA2009/EyeClick.html


al minuto utilizzando uno programma di predizione delle parole. Dei quattro

studenti che hanno svolto l’esperimento sono quelli con le maggiori difficolta fisi-

che.” [TH04] Nel caso di persone con una buona velocita di scrittura il predittore

puo rallentare l’utente. Cio dimostra che c’e ancora un margine di miglioramen-

to in questo tipo di strumenti per poterli rendere effettivamente efficaci anche a

persone con difficolta motorie lievi.

2.3 Utilizzo da parte di utenti con difficolta di apprendimen-

to

Negli ultimi anni gli strumenti informatici per utenti affetti da dislessia,

disgrafia e disturbi specifici dell’apprendimento (DSA) sono aumentati conside-

revolmente di numero, soprattutto nel mercato americano.

Questo tipo di prodotti, e spesso costituito da una “collezione” di software oppure

da un software che svolge diverse funzioni. Ad esempio vi e uno strumento per la

lettura accompagnata dalla sintesi vocale e l’estrapolazione di concetti, l’editor

per immagini che “decora” le parole con figure che ne rappresentano il significato,

strumenti per la costruzione di mappe concettuali, dizionari ecc.

Una delle principali funzionalita di questi applicativi e un apposito editor

“parlante”. Esso agisce come una macchina da scrivere ma ogni parola immessa

viene anche pronunciata da una voce sintetica.

Spesso e possibile accedere con una certa facilita a funzioni simili a quelle degli

screen reader nel trattamento dei testi. Ad esempio consente di rileggere frasi o

periodi precedenti / successivi, leggere l’intero testo a partire da dove si trova il

cursore o fino alla posizione dello stesso.

Versioni recenti di questo tipo di software possono integrare queste funzionalita

15 Utilizzo da parte di utenti con difficolta di apprendimento

all’interno di un editor di uso comune (come Microsoft Word oppure OpenOffice

Write).

Lo strumento di predizione delle parole solitamente si integra in que-

sto tipo di software e viene attivato, in accordo con l’insegnante di sostegno o

il personale di supporto, per l’aiuto nell’immissione di parole particolarmente

difficili.

A differenza del caso delle disabilita fisiche, in questa situazione il predittore aiuta

a ricordare l’esistenza delle parole, il loro corretto uso, la loro corretta grafia ed

aiuta a prevenire errori ortografici durante la loro digitazione.

Inoltre in lingue, come l’inglese, dove il modo di scrivere una parola e diverso da

come viene pronunciata, gli strumenti di Word Prediction per questa categoria

di utenti servono a ricordare la corretta “modalita di scrittura” delle parole.

Grazie ad appositi “filtri correttivi” che vengono applicati alla lista dei termini

predetti, alcuni software consentono di selezionare non solo i termini che iniziano

con il pattern scritto dall’utente ma anche quelli che iniziano con un pattern

diverso ma che si pronuncia nello stesso modo. Un esempio potrebbe essere la

parola “Universe”, il predittore la proporra anche se l’utente inizia a scrivere

“You”, in quanto il suono della “U” e il suono del dittongo “You” sono simili.

Uno strumento di predizione standard non risponderebbe a queste caratteristiche.

Nella lingua italiana questo problema viene meno e l’esigenza resta quella

di consentire all’utente di inserire rapidamente la parola pensata osservando ed

ascoltando come essa deve essere scritta e letta in maniera corretta.

Inoltre, proprio perche il software viene utilizzato in ambito scolastico,

puo risultare utile permettere all’utente di combinare diversi dizionari. Ad esem-

pio, ad un bambino di quinta elementare che sta studiando geografia potrebbe

essere utile, in un ipotetico sistema di predizione, il dizionario “scuola elemen-

tare secondo ciclo” unitamente al dizionario “citta del mondo” ed al dizionario


“termini geografici”.

Molta attenzione deve essere poi posta in fase di studio e di design del-

l’applicazione. i sistemi devono essere utilizzabili da bambini ed anche i voca-

bolari devono tenere conto di questa particolarita. Come descritto ad esempio

in [Evm06] il problema principale con il programma WriteAssist era la finestra

di grandi dimensioni che “non si muoveva e copriva le parole.” Gli studenti e

gli insegnanti hanno inoltre trovato in WriteAssist meno scelta di parole [rispetto

agli altri prodotti n.d.t.]. Oltre a cio il vocabolario non era adatto agli studenti

poiche offriva “bad words”, come riportato da studenti e docenti.

Come vedremo nel prossimo capitolo i software di buon livello (purtroppo

oggi non disponibili in lingua italiana) offrono queste importanti caratteristiche.

Come riportato in [Evm06], l’utilita dei sistemi di predizione varia da

prodotto a prodotto e da persona a persona. La capacita di scrittura degli studenti

che hanno svolto il test e aumentata in termini di parole totali, fluidita dei termini

e delle frasi e velocita di composizione del testo di valori diversi a seconda del

prodotto utilizzato. [Evm06]

Dallo studio effettuato si puo inoltre dedurre che assieme al programma di pre-

dizione delle parole e importante che sia integrato nell’editor (o opportunamente

attivato) il correttore per errori ortografici e lo strumento di analisi di errori gram-

maticali nella frase o nel periodo. infatti nel caso di uno studente, e aumentata

in maniera uguale la velocita con tre diversi strumenti di predizione. [...] Non e

invece cambiata la fluidita delle frasi con nessuno dei tre strumenti in uso. La

spiegazione puo derivare dal fatto che lo scopo principale di un sistema di pre-

dizione delle parole e quello di colmare difficolta nella digitazione e che questo

tipo di strumento puo fornire soltanto un aiuto limitato per cio che riguarda il

controllo della struttura grammaticale delle frasi. [Evm06].

17 Altri impiegi dei sistemi di predizione

2.4 Altri impiegi dei sistemi di predizione

I nuovi dispositivi mobili, non dotati di tastiera tradizionale ma utiliz-

zabili mediante tastiere a schermo, fanno uso di sistemi avanzati di predizione.

Potremmo paragonare le necessita di questa categoria di utenti a quella del-

le persone con difficolta motorie. Tasti virtuali piccoli, dispositivi utilizzati in

momenti e situazioni diverse possono portare l’utente a necessitare di un aiuto

nell’immissione del testo.

Molti fra i sistemi impiegati (ad esempio nei menu o nelle finestre di

dialogo) si avvicinano piu ad un autocompletamento che ad una predizione con

molte scelte. Il loro dizionario e spesso composto da un insieme di termini (ad

esempio le applicazioni o le impostazioni) per le quali e necessario un filtro di

ricerca.

Software piu avanzati di predizione e correzione delle parole sono utilizzati duran-

te la digitazione di messaggi (ad esempio email) e spesso non ricorrono a database

di parole contenute nel dispositivo. In questo caso il cuore del predittore sta in

un server remoto mentre l’utente richiede le informazioni mediante un client. La

comunicazione avviene tramite web service o altra tecnologia web.

Un ultimo ambito in cui si e potuta notare la presenza di predittori e

il motore di ricerca. Google, ad esempio, durante la ricerca di alcune parole

“suggerisce” un possibile proseguimento o completamento della parola o della

frase.

Anche in questo caso il database, che deriva da ricerche precedenti e dal contenuto

indicizzato all’interno delle pagine web, e residente in un server remoto e l’utente

ottiene i suggerimenti mediante un’interfaccia AJAX presente nella pagina.

In tutti questi casi e indispensabile la velocita di comunicazione fra client e server

e l’utilizzo del meccanismo della cache per dare una risposta il piu rapidamente


possibile.

Nelle prossime pagine cercheremo di dare una definizione piu precisa del

problema della predizione delle parole, presenteremo alcune tecniche (dalle piu

semplici alle piu complesse) con cui questo processo viene svolto e daremo alcuni

esempi di applicativi, commerciali o utilizzabili gratuitamente, che fanno uso delle

diverse tecniche esposte per offrire questo servizio.

CAPITOLO 3

Definizione del problema, terminologia e StatoDell’Arte dei sistemi di Predizione

3.1 Introduzione

Nel precedente capitolo e stato definito in maniera informale il problema

della previsione di parole ed abbiamo presentato i principali ambiti in cui questa

tecnologia puo essere impiegata. Sono state descritte le categorie di utenti “de-

stinatari” discutendo i loro problemi ed i requisiti che essi richiedono a prodotti

di questo tipo.

In questo capitolo cercheremo di definire in maniera piu formale il proble-

ma della predizione e di presentare gli algoritmi che, ad oggi, vengono impiegati

per svolgere questo compito in applicazioni dedicate all’utente finale.

Non approfondiremo, in questo lavoro, tecnologie ed algoritmi legati a prodotti

funzionanti su server (come la computazione parallela o la consultazione di basi

di dati clusterizzate di grandi dimensioni) in grado di dare delle risposte sicura-

mente molto precise ma che vincolano l’utente ad impiegare un software sempre

Definizione del problema, terminologia e Stato Dell’Arte dei sistemi diPredizione 20

legato ad un application server addetto al processamento delle richieste.

Nell’ultima parte di questo capitolo, infine, verranno proposti diversi prodotti e

ne verra descritto il loro funzionamento, il tipo di approccio utilizzato per predire

le parole, i loro vantaggi ed i loro svantaggi.

3.2 Definizione del problema e terminologia adottata

Per poter definire meglio il problema e utile cominciare da un esempio

pratico. Ad un qualunque sistema di predizione, in input, verra passato un

qualcosa di simile a:

Esempio 3.1.

La minestra e nel pi

L’utente desidererebbe completare “pi” con la parola “piatto”.

• L’iniziale (o le iniziali) della parola da completare vengono chiamate radice

o prefisso. Le lettere che compongono la radice vengono appunto chiamate

iniziali. Le iniziali verranno numerate. Nell’esempio “p” e la prima iniziale

ed “i” e la seconda iniziale.

Ogni volta che verra fatto riferimento genericamente ad “iniziale” (al singo-

lare e senza alcun aggettivo numerale) si intendera la prima iniziale. Ogni

qualvolta verra utilizzato “iniziali” (al plurale e senza aggettivo numerale)

si intendera l’intero prefisso.

• Tutto cio che precede la parola da prevedere verra chiamato predecessore.

Tutto cio che segue la parola da predire verra chiamato successore.

21 Definizione del problema e terminologia adottata

• Predecessore e successore dovrebbero, in base alla definizione comune, defi-

nire il contesto. Per maggior chiarezza, poiche in generale nessuna tecnica

di predizione analizzata in questo lavoro tiene conto del successore, definia-

mo il contesto quale sinonimo di predecessore. Nell’esempio il contesto e

“La minestra e nel [spazio]”. Come viene fatto notare esplicitamente, anche

lo spazio prima della parola da prevedere e considerato contesto.

• Il contesto potra essere rappresentato anche da un vettore denotato dalla

lettera c (ad esempio c1 . . . cn).

• Quando descriveremo in generale la frase all’interno di formule anche la

“futura parola” verra rappresentata come un termine (w). Cosı il contesto

unitamente alla futura parola sara w1 . . . wn in cui w1 . . . wn−1 rappresentano

il contesto mentre wn rappresenta la parola da predire.

• Ove necessario ¡s¿ indica il simbolo di inizio frase. ¡/s¿ e invece il termina-

tore di frase.

• La lista dei termini (o la lista parole) indica la l’elenco di termini che l’algo-

ritmo offre come completamento della radice. Tale lista comprende termini

interi e non suffissi della radice. Nell’esempio, la lista dei termini dovra

comprendere “piatto” e non “atto”.

Completata la definizione della terminologia di base possiamo procedere

alla definizione del problema.

La previsione delle parole puo essere definito come una funzione che, data in input

la concatenazione di contesto e radice, restituisce in output l’elenco dei termini

che hanno inizio con il prefisso dato. Possiamo considerare come dato in ingresso

anche il massimo numero di termini che devono essere contenuti nella lista delle

parole in uscita.


Se ci limitassimo a questo, ed impostassimo il massimo numero di termini a +∞

il problema si ridurrebbe alla ricerca e al filtraggio da un dizionario.

Cio che caratterizza i sistemi di predizione e l’ordine con cui le parole

vengono presentate all’utente.

In termini generali potremmo definire l’ordinamento (in ogni posizione i della

lista) come:

P (wi|c1 . . . cn) > P (wk|c1 . . . cn) (3.1)

per ogni wk presente nel vocabolario e non ancora ordinato. Dove P puo essere

una probabilita ma anche una funzione di peso.

In base all’algoritmo scelto la funzione di probabilita viene calcolata in

modo differente tenendo conto di differenti fattori. Alcuni algoritmi considerano il

contesto (e in questo caso si parla di predizione con contesto), altri invece ignorano

tale caratteristica ed utilizzano per la predizione soltanto la radice inserita (ed in

questo caso si parla di predizione senza contesto). Nel caso in cui il contesto non

sia preso in esame la condizione nell’equazione 3.1 si semplifica in questo modo:

P (wi) > P (wk), ∀wk ∈ V (3.2)

Con V l’insieme dei termini nel vocabolario non ancora ordinati.

Nel prossimo capitolo, in cui discuteremo dei modelli del linguaggio, de-

finiremo in maniera formale una funzione di probabilita adatta all’equazione

3.1.

Un elemento sempre presente e comune a tutte le tecniche di predizione

e il dizionario (o vocabolario) dei termini. Un sistema puo fare uso di un solo

dizionario (a dizionario singolo) o classificare le parole in base a diversi dizionari

(per offrire vocabolari di termini specifici oppure perche e richiesto dalla logica

23 Definizione del problema e terminologia adottata

dell’algoritmo utilizzato). Se il programma prevede che l’utente possa inserire (in

un qualche modo) dei termini si parlera di dizionario “aperto” (open dictionary)

altrimenti, se il dizionario non consente aggiunte si parlera di dizionario “chiuso”

(dizionario prefissato o closed dictionary in inglese).

I criteri con cui vengono stabilite le probabilita, il contenuto dei vari

vocabolari e la scelta del vocabolario piu opportuno differiscono da algoritmo ad

algoritmo.

Qui di seguito presentiamo due esempi: il primo non fa uso del contesto,

il secondo, invece lo considera. Il primo, inoltre, e a dizionario singolo, il secondo

richiede piu dizionari.

3.2.1 Esempio di predizione senza contesto

La soluzione piu semplice, riprendendo l’esempio 3.1 sta nel presentare, in

ordine alfabetico, tutte le parole che iniziano con “pi”, l’utente immettera un’altra

lettera, ad esempio “pia” e, in tal modo, il filtraggio si fara piu stringente. In

questo caso l’approccio e a dizionario singolo dove tutte le parole hanno lo stesso

peso.

Questo e un esempio di soluzione senza contesto ovvero in cui non vengono

tenute in considerazione le parole precedenti (o successive) alla parola che deve

essere predetta. In questo esempio, inoltre, le parole sono equiprobabili o, piu

precisamente, il loro peso (la loro probabilita) e stabilito dall’ordine alfabetico

(una parola che inizia con “A” avra un peso maggiore di una che inizia con “B”,

in tal modo e possibile applicare la formula generica in equazione 3.1).


3.2.2 Esempio di predizione con contesto

Un possibile miglioramento che potremmo apportare alla soluzione sopra

esposta e quello di costruire, a partire dal vocabolario precedente, diversi dizio-

nari, suddividendo i termini in base al proprio valore grammaticale: (sostantivi,

verbi, aggettivi, articoli, preposizioni, congiunzioni, pronomi ecc.). Anche in que-

sto caso assegnamo a ciascun termine pesi opportuni in modo da poterli ordinare

alfabeticamente.

Riprendendo l’Esempio 3.1, l’input dell’utente viene quindi convertito (ad

esempio mediante un POS-tagger) in qualcosa di simile a questo:

Esempio 3.2.

articolo sostantivo verbo preposizione art. (su + il) prev start(pi)

dove prev start(pi) indica una radice la cui prima iniziale e una p e la

seconda e una i.

L’input cosı convertito viene processato da una funzione che individua in

sostantivi o pronomi i successori di una preposizione ed un articolo. Cio puo essere

svolto in base ad un insieme di regole (o grazie ad un precedente addestramento).

La nostra funzione di esempio individua che:

P (wsostantivo|c1 . . . cn) = 0, 6

P (wpronome|c1 . . . cn) = 0, 4

L’algoritmo proporra, quindi, in ordine alfabetico soltanto i risultati di queste

due categorie di termini (prima i sostantivi e poi i pronomi).

25 Sistemi che non fanno uso di contesto

Questo e un esempio di previsione con contesto poiche, prima di resti-

tuire la lista delle parole in output, l’algoritmo osserva parte del contesto (i due

elementi precedenti) e non soltanto le iniziali.

Nei prossimi paragrafi passeremo in rassegna diverse tipologie di algo-

ritmo per la previsione delle parole. Verranno prese in esame prima le tecniche

senza contesto e poi quelle che fanno uso di contesto.

Bisogna ricordare che molti software utilizzano combinazioni dei vari al-

goritmi in modo da sfruttare diverse metriche per ordinare le parole ed ottenere

risultati migliori.

3.3 Sistemi che non fanno uso di contesto

Questo tipo di tecniche sono impiegate in sistemi di piccole dimensioni.

Non e escluso pero che alcuni dei metodi descritti in questa sezione vengano

impiegate come “appoggio” ai modelli di predizione con contesto.

La costruzione del vocabolario e piuttosto semplice sia che questo sia lasciato

all’utente sia che sia generato dagli sviluppatori del software.

Si procede processando un determinato numero di testi da cui sono estrat-

ti i termini. Nel caso di analisi della frequenza (caso molto comune), se durante

il processamento del documento una parola e gia contenuta nel dizionario viene

incrementato il contatore relativo.

I risultati migliori si ottengono scegliendo documenti contenenti un lessico

molto vicino a quello adottato dall’utente finale. Non assume molta importan-

za, invece, la frequenza dei termini (se non dei principali) poiche questa viene

“limata” facilmente durante l’utilizzo.


3.3.1 Lista di parole pesate a dizionario aperto

E l’esempio piu tipico di sistema di predizione. Come avremo modo di

discutere nella sezione 3.5 e utilizzato da moltissime applicazioni.

Il sistema e strutturato con un dizionario singolo. Possono essere presenti

piu dizionari ma in questo caso e l’utente che manualmente sceglie quello che

desidera utilizzare. Il file di vocabolario solitamente e in una struttura molto

semplice (di tipo CSV) in cui il primo elemento e il termine ed il secondo e un

valore di “peso” (oppure di probabilita) variabile e positivo.

L’utente inizia ad immettere la radice e la lista di termini viene costruita

ed ordinata in base ai “pesi” contenuti nel file di dizionario.

Qualora la parola non sia compresa nella lista, essa viene aggiunta al file di

dizionario e le viene assegnato un valore di peso che puo variare da applicativo

ad applicativo.

Alcuni di questi sistemi aggiungono le nuove parole assegnandovi un va-

lore predefinito, ad esempio 1. Essi non definiscono un valore massimo per il

peso. In questo modo i contatori delle parole piu frequentemente impiegate, in

base ad euristiche interne, possono venire incrementati durante l’utilizzo. Cosı

anche un nuovo termine incluso nel vocabolario ed impiegato molto spesso puo

crescere rapidamente di peso.

3.3.2 Lista di parole a dizionario costruito dall’utente

Questi sistemi sono simili a quelli descritti nel paragrafo precedente. Essi

sono piu di frequente disponibili anche in Italiano. Essi vengono distribuiti privi

di vocabolario.

E compito dell’utente costruire uno (o piu) dizionari. Il programma consente in-

fatti l’importazione dei testi per l’addestramento sia in formato txt che mediante

27 Sistemi che non fanno uso di contesto

il copia/incolla. Ogni documento individuato dall’utente per l’addestramento

viene analizzato e ne vengono estratte le parole. Esse sono poi aggiunte al file di

dizionario.

Come per l’inserimento svolto dall’utente nel sistema precedente, nel ca-

so una parola sia ricorrente, il suo valore di peso viene incrementato in modo

da risultare piu probabile rispetto alle altre. La predizione avviene in maniera

analoga alla precedente.

A questa categoria appartiene la maggior parte dei sistemi di predizione

integrati in applicazioni piu ampie in cui questa non e la funzione principale. Esso

e utile se il programma viene distribuito in piu lingue. Non e richiesta infatti la

localizzazione di un vocabolario poiche e sufficiente tradurre l’interfaccia.

3.3.3 Frequenza di vicinanza fra lettere

Solitamente questo sistema viene impiegato nelle tastiere a schermo ri-

dotte, in cui e necessario stabilire quali tasti siano “importanti” e quali meno. In

questo caso non viene creato un vocabolario ma viene analizzata, all’interno dei

testi utilizzati come addestramento, la frequenza di vicinanza fra le lettere invece

che fra le parole. Sistemi evoluti basati su questa tecnica arrivano a costruire dei

veri e propri n-grammi (analizzati nel prossimo capitolo) sulle lettere invece che

sulle parole.

Il predittore, per ogni lettera immessa, suggerisce le lettere successive piu proba-

bili per comporre le parole.

Analizzeremo nel seguito un esempio di predittore di parole molto par-

ticolare che fa uso di questa tecnica al fine di fornire un metodo alternativo ma

efficace di immissione.


3.3.4 Utilizzo della cache con dizionario aperto

La cache solitamente non viene impiegata in modo autonomo ma, piutto-

sto, fornisce un supporto a molti sistemi di predizione. E molto difficile valutare

quanti di essi ne facciano uso.

Il sistema che la implementa aggiunge, oltre alla struttura del vocabolario,

quella di un vettore pesato (la cache appunto). Questo contiene gli ultimi termini

immessi ed il peso di ciascun termine varia a seconda di specifiche funzioni.

Non viene pero osservato se le parole vengano immesse nella stessa frase o in altre

e percio si e deciso di includere questa tecnica fra quelle che non considerano il

contesto.

Come riportato in [WA07] i modelli basati sulla Cache (o parole recenti)

hanno dimostrato di portare un piccolo ma costante aiuto ad altre tecniche.

L’idea alla base della cache e che sia piu facile che venga richiesto dall’u-

tente di inserire nello stesso testo delle parole gia scritte in precedenza rispetto

alle altre. Per questo la loro probabilita e aumentata di un fattore costante oppu-

re di un fattore di decadimento esponenziale (a seconda della posizione occupata

dalla parola all’interno della cache).

Il concetto di una funzione di cache a decadimento e che la probabilita di

ricorrenze di una certa parola presente in cache dipende dalla distanza, in [WA07]

si utilizza la distanza del coseno (cosine similarity) della parola contenuta nella

cache rispetto a quella che deve essere predetta. In media la probabilita piu alta

di ricorrenza di un termine si raggiunge dopo 15-20 parole. [WA07]

3.4 Sistemi di predizione basati sul contesto

La ricerca nel tempo si e concentrata sui predittori di parole che conside-

rano il contesto. Si e infatti presto compreso che non e trascurabile la posizione

29 Sistemi di predizione basati sul contesto

all’interno della frase in cui un determinato termine viene inserito. Come illustra-

to nell’esempio in 3.2.2, l’utilizzo del contesto ci permette di migliorare i risultati

rispetto all’esempio in cui non ne veniva fatto uso.

Cio implica pero il superamento della semplice struttura a vocabolario

e la generazione di basi di dati di dimensioni maggiori. Come avremo modo di

discutere piu approfonditamente nel capitolo 4 anche la procedura di creazione

di queste strutture e piu lunga e complessa.

In questo caso e necessario selezionare dei testi, non solo che contengano

un insieme di parole simile a quello usato dall’utente finale, ma anche con uno stile

ed una struttura lessicale simile. I documenti vengono usati come addestramento,

come “aspettativa” dei futuri testi che l’utente vorra scrivere. E quindi errato, in

generale, pensare di poter impiegare un insieme di articoli di giornale come base

di addestramento per sviluppare un modello linguistico adatto ad un ragazzo di

scuola superiore, cio anche se il lessico (il vocabolario) e simile.

3.4.1 Lista di parole e di coppie di parole pesate a dizionario aperto

La prima soluzione e in continuita con quelle proposte nel paragrafo

precedente, che non tengono conto del contesto.

Essa sviluppa un modello a partire dai singoli termini (come nel caso di 3.3.1). In

aggiunta viene mantenuto anche un dizionario parallelo di coppie di due termini

vicini fra loro. Ognuno degli elementi all’interno del dizionario delle coppie (come

nel caso del dizionario a singolo termine) ha un valore di peso che puo aumentare

in base alla frequenza di utilizzo della coppia stessa.

Ogni qualvolta si renda necessario predire un termine viene controllato se

la parola precedente compare come primo elemento di una coppia. Tutti i secondi

elementi delle coppie che rispettano questo criterio vengono aggiunti ad una lista.

Tale lista avra un’importanza maggiore del dizionario a singoli termini.


Sono quindi presentati in output i risultati, le cui iniziali corrispondono al prefisso

fornito dall’utente, pesati secondo il peso attribuito a ciascun termine e a seconda

della provenienza (elementi di coppie o dizionario a singoli termini).

Nel caso in cui una parola inserita dall’utente non sia presente nel dizio-

nario dei singoli termini essa viene aggiunta e, in unione con la precedente, viene

inserita anche nel dizionario delle coppie.

Nel caso in cui una parola inserita dall’utente non sia presente nel di-

zionario delle coppie essa viene aggiunta. Il primo elemento della coppia sara il

termine precedente, il secondo elemento della coppia sara la nuova parola inserita.

Gia questo semplice metodo ci fa rendere conto che la struttura dati ospi-

tante il dizionario e molto maggiore rispetto ai sistemi precedenti. Se paragonia-

mo questo sistema a quello in 3.3.1, nel caso pessimo, difficilmente raggiungibile,

la dimensione sara n2 maggiore (con n il numero dei termini del dizionario).

Il limite principale di questa tecnica e che spesso si e costretti ad utilizzare dizio-

nari chiusi, non aggiornabili in automatico dall’utente. Questo perche si rischie-

rebbe di inserire un elevatissimo numero di coppie con valori di peso molto bassi

(inserimenti occasionali). Non utilizzando una struttura dati specifica (Hash,

B-Tree o altro) la ricerca in un file di testo potrebbe quindi risultare molto lunga.

Anche in questo caso si puo avere un approccio, per programmi multi-

lingua, simile a quello esposto in 3.3.2. In questo caso anche il dizionario delle

coppie viene generato a partire dai file di addestramento.

3.4.2 Utilizzo dei modelli del linguaggio

Progredendo nel miglioramento della tecnica precedente troviamo l’impie-

go di modelli del linguaggio. Poiche tale metodo e alla base del sistema esposto

nei capitoli successivi, abbiamo ritenuto utile approfondire algoritmi e metodi per

la predizione basati su questo tipo di modelli nel prossimo capitolo.

31 Sistemi di predizione basati sul contesto

In tale sede, inoltre, offriremo una breve panoramica dei principali proble-

mi che l’impiego dei semplici modelli del linguaggio puo portare e descriveremo

alcuni approcci innovativi.

3.4.3 Cenni su possibili approcci machine-learning e basati sull’analisi

del linguaggio (NLP)

In [AM06] viene descritto come il problema della predizione delle parole

possa essere ricondotto ad un problema di classificazione di parole. Si spiega

che la predizione puo essere considerata una classificazione in cui diverse parole

selezionate sono classificate al fine di determinare quella piu adatta in un dato

contesto. [AM06] Il sistema, durante l’analisi del corpus per l’addestramento, uti-

lizza tecniche descritte come innovative per estrarre le diverse parole unitamente

ad un insieme di caratteristiche. L’addestramento alla categorizzazione viene

poi svolto mediante SVM. Gli strumenti di categorizzazione delle parole vengono

infine impiegati dal motore per la predizione. [AM06]

Gli autori in [AM06] sostengono che il sistema richiede un contesto di non

piu di 3 parole precedenti alla radice data e che, in taluni casi, questo metodo ha

raggiunto una precisione vicina al 90% surclassando la maggior parte delle altre

tecniche (lo studio risale al 2006).

La ricerca si sta muovendo anche a partire dalla cosiddetta NLP (Analisi

del linguaggio naturale).

Si sono ottenuti buoni risultati combinando le tecniche degli n-grammi con il

POS-Tagging arrivando a costruire dei modelli che, al posto delle parole, sono in

grado di prevedere dato uno (o piu) elementi del linguaggio quale sia il candidato

successivo piu valido. In particolare uno studio su questo si puo trovare in [FH03].


Cio consente di costruire dei vocabolari in base agli elementi del linguaggio e

di filtrare con maggior precisione termini che, seppur usati frequentemente, non

sono grammaticalmente corretti nel contesto corrente.

Riprenderemo brevemente questo miglioramento all’interno del paragrafo 4.7.

Un altro tentativo di integrazione mediante strumenti tipici dell’ NLP

e descritto in [WA07] in cui si cercano di integrare i modelli del linguaggio con

vettori di termini derivanti dall Latent Semantic Analysis (LSA). Come riportato,

nello studio si assume che il testo che si vuole scrivere sia semanticamente coerente

(i concetti trattati siano semanticamente “vicini”).

Gli autori si aspettano che i vettori di parole siano simili al vettore del contesto.

Partendo da questo assunto, l’approccio proposto e quello di convertire i

dati risultanti dall’LSA in probabilita da assegnare ai termini contenuti nei vet-

tori. L’integrazione puo avvenire mediante una cache “semantica” o mediante di-

verse forme di interpolazione. I risultati proposti in [WA07] sono confortanti e di-

mostrano che tutte le tecniche di integrazione portano ad un certo miglioramento

rispetto all’impiego dei semplici modelli del linguaggio.

3.5 Principali prodotti destinati all’utente finale

Nelle precedenti sezioni abbiamo preso in esame tecniche e modalita di

costruzione di algoritmi per i sistemi di predizione. Alcune di queste sono ormai

superate, altre sono in fase di sperimentazione.

Di seguito presenteremo alcuni fra i principali prodotti che svolgono la previ-

sione di parole come funzionalita principale o di rilievo del programma. Ci

concentreremo su quelli disponibili anche in lingua italiana.

Tale rassegna non vuole avere la pretesa di essere completa, poiche i software a

disposizione sono davvero molti.

33 Principali prodotti destinati all’utente finale

Gli ultimi due prodotti descritti sono quelli piu famosi ed efficaci dispo-

nibili in lingua inglese ed altre lingue estere ma non ancora disponibili per il

mercato italiano (non localizzati).

Prima di procedere e necessario ricordare che ciascuno dei nomi o dei

marchi eventualmente registrati di prodotti o di societa sotto esposti e di proprieta

dei rispettivi autori.

3.5.1 Kurzweil 3000

Il Kurzweil 3000, prodotto da Kurzweil Educational Systems di Cambium

Technology, e un completo sistema di lettura e scrittura adatto a persone con

disturbi specifici dell’apprendimento, in particolare ad utenti affetti da dislessia

(e/o disgrafia).

Esso e davvero molto ricco di funzionalita, storicamente e suddiviso in

due componenti principali: lo strumento di lettura e l’editor di testi. Noi ci

concentreremo su quest’ultimo

L’editor di testi assmiglia ad un word processor standard. L’attivita di

scrittura viene semplificata da strumenti avanzati come il sistema di predizione,

il thesaurus o il correttore ortografico. Inoltre e possibile utilizzare la sintesi

vocale per rileggere cio che si sta scrivendo sia interamente (dall’inizio alla fine)

sia durante la digitazione (parola per parola o carattere per carattere).

Molte sono le funzioni di supporto alla scrittura come il dizionario ad immagini

(che permette all’utente di inserire parole o concetti mediante immagini), il di-

zionario dei sinonimi e delle parole simili e gli strumenti di traduzione. Non tutte

queste funzionalita sono disponibili in lingua italiana.

Il predittore di parole e uno degli strumenti messo a disposizione all’inter-

no dell’editor di testi. Si attiva tramite voce di menu oppure mediante combina-

zione di tasti. Esso funziona esclusivamente all’interno dell’editor del Kurzweil e


si basa su dizionario a singolo termine e dizionario delle coppie (tipologia descritta

in 3.4.1).

Una finestra spostabile contiene la lista dei termini ed indica in modo chiaro

le scelte possibili. Essa puo essere liberamente sovrapposta o affiancata alla

finestra in cui l’utente sta scrivendo. L’inserimento della parola desiderata si

effettua cliccando sul relativo pulsante indicante il numero di scelta, mediante

combinazioni tasti oppure, opzionalmente, tramite i tasti presenti nel tastierino

numerico.

Il numero di termini contenuti nella lista a schermo e di dieci elementi. Il nu-

mero di elementi e comunque regolabile tramite la finestra di configurazione del

software. Le combinazioni tasti, comunque, consentono l’inserimento immediato

di non piu di 10 elementi.

Nella versione inglese il programma viene fornito di una lista di termini

e di coppie piuttosto corposo. Nella versione italiana, invece, come per altre

funzioni di questo programma, non e disponibile alcun dizionario al momento

dell’installazione.

Esso deve essere costruito a partire da testi acquisiti singolarmente. Non e pos-

sibile una importazione automatica di termini da una selezione di documenti. Il

testo da processare per essere aggiunto al dizionario deve essere aperto nella fine-

stra dell’editor, deve essere selezionato e quindi e necessario utilizzare la specifica

funzione di addestramento.

Il Kurzweil 3000 e un prodotto commerciale, per ulteriori dettagli 1

1Kurzweil 3000 – Kurzweil Educational Systems – http://http://www.kurzweiledu.com/. Il distributore per l’Italia e TifloSystem S.p.A. http://www.tiflosystem.it/

http://http://www.kurzweiledu.com/

http://http://www.kurzweiledu.com/

http://www.tiflosystem.it/


3.5.2 TypingAssistant

TypingAssistant di SumitSoft e il primo esempio di software dedicato

esclusivamente alla predizione. E disponibile in piu lingue fra cui l’Italiano, e gia

dotato di un proprio dizionario dei termini al momento dell’installazione.

Una volta attivato il programma, l’icona relativa compare nella barra di

notifica di Windows.

Scegliendo questa icona e possibile regolare diverse opzioni fra cui: in quali ap-

plicazioni si desidera attivare/disattivare la predizione, dopo quante lettere far

apparire la finestra della lista parole, il numero di elementi all’interno della lista

ed altro.

Il software presenta molti strumenti facilitativi addizionali fra cui il sistema per

la correzione delle parole, sistemi a macro (ad esempio e possibile registrare la

parola “firma” in modo che il software inserisca un determinato testo), strumenti

semplificati per la gestione degli appunti di Windows (copia/incolla).

Anche se il programma lavora con le diverse applicazioni esso non pare riconoscere

le varie tipologie di controlli (ad esempio editBox, panel ecc.). Esso infatti offre

predizione anche in assenza di un campo di testo. Ad esempio in Paint, premendo

lettere sulla tastiera come fossimo nella finestra di un qualche editor, compare

comunque la lista delle parole.

Cio ci ha suggerito il modo in cui il software opera: esso non e in grado

di osservare il contesto, poiche non e in grado di “intercettare” il contenuto della

finestra attiva.

Da una rapida analisi, seppur non siamo stati in grado di aprire esplicitamente

i file di vocabolario, ci pare che venga utilizzato un dizionario aperto a singolo

termine simile a quanto descritto in 3.3.1. Inoltre non ci sembra che il dizionario

delle parole sia pesato secondo la frequenza ma, piuttosto, che venga utilizzato

l’ordinamento alfabetico.


TypingAssistant e un prodotto commerciale di Sumisoft. 2

3.5.3 Click-N-Type

Click-N-Type3 e un software completamente gratuito di tastiera a scher-

mo molto potente e flessibile.

Esso consente l’accesso al computer a persone che fanno uso di tou-

chscreen, joystick, sensori di movimento o switch di selezione, permette infat-

ti l’inserimento di testo non solo mediante click ma anche tramite sistemi a

scansione.

Sono impostabili diversi layout di tastiera dai piu semplici (adatti appunto ai

sistemi a scansione) alle tastiere tradizionali.

Le parole possono essere immesse direttamente in qualunque applicazione o puo

essere impiegato un buffer.

In questo caso, come nelle macchine da scrivere elettriche, si possono inserire

un certo numero di lettere all’interno di un buffer prima di rilasciarlo. Al mo-

mento del rilascio il contenuto del buffer viene inviato mediante copia/incolla

all’applicazione in primo piano.

Il software integra un sistema di predizione delle parole privo di contesto

del tutto simile a quello descritto nel nostro primo esempio (vedi 3.2.1). Esso

consente una rapida aggiunta e rimozione delle parole grazie al dizionario che e

costituito da un elenco di termini contenuto in un file in formato solo testo (txt).

Al momento dell’installazione e gia disponibile un vocabolario italiano di base.

Quando viene immessa una radice di almeno tre lettere la predizione ha inizio ed

il sistema propone le scelte in ordine alfabetico.

2TypingAssistant – SumiSoft http://www.sumitsoft.com/3Click-N-Type – cnt.lakefolks.com

http://www.sumitsoft.com/

cnt.lakefolks.com


3.5.4 Chewing Word

Chewing Word4 e un sistema a tastiera a schermo gratuito sviluppato da

Aristide Grange all’interno dell’Universita di Lorraine (Francia). Il software e

multipiattaforma e consente ad utenti con limitate capacita motorie o con distur-

bi di apprendimento di comporre parole e frasi mediante una tastiera virtuale

interattiva.

La tastiera e composta da un certo numero di lettere distribuite in ordine

sparso sullo schermo. Una volta posizionato il cursore sopra una lettera iniziale

di una parola si ha subito un suggerimento. Se l’intero suggerimento e esatto lo

si seleziona, proprio come avverrebbe con un normale predittore (con lunghezza

lista di parole 1). Se pero il termine non e quello desiderato ma parte di esso

e comunque valida (ad esempio l’utente desidera immettere “permette” ed il

sistema suggerisce “personaggio”) si procede selezionando solo la parte di parola

corretta (vedi figura 3.1).

A questo punto si puo procedere in due modi: o si seleziona la lettera successiva

ricercandola autonomamente all’interno della tastiera oppure si procede conti-

nuando a cliccare sulla radice (illuminata in giallo), il sistema iniziera a ciclare

fra i possibili completamenti tentando altre lettere.

La predizione seppur molto evoluta e priva di contesto. Essa fa uso delle statisti-

che sulla frequenza di vicinanza fra le lettere come spiegato brevemente in 3.3.3.

La qualita e buona poiche si e proposta una forma di inserimento innovativa.

Le statistiche relative alla lingua italiana sono liberamente disponibili

ed installabili dall’utente. E possibile inoltre prelevare l’intero pacchetto per la

lingua italiana (che localizza anche l’interfaccia utente).

Il programma integra inoltre un client per Google Scribe (oggi non piu funzionan-

te), discusso rapidamente nel seguito. Gli autori non si assumono nessuna respon-

4ChewingWord – http://chewingword.wikidot.com/


Figura 3.1: Screenshot di Chewing Word mentre si sta cercando di inserire la paro-la “permette”. E stato scelto il prefisso “per” dal suggerimento di ChewingWordche proporrebbe “Personaggio”.

sabilita sulla qualita e continuita del servizio del predittore di Google ma hanno

deciso comunque di integrarlo per garantire un’alternativa (anche per lingue non

supportate).

Il software consente l’immissione soltanto all’interno della finestra del

proprio editor (la tastiera virtuale non si integra con gli altri programmi installati

nel computer).

3.5.5 DiCOM

Dicom5 (DictionairelCOM) e il primo esempio di software qui discusso

non disponibile in italiano. Esso e un programma gratuito di predizione delle

parole.

5DiCOM e prelevabile gratuitamente dall’indirizzo: http://recit.cssamares.qc.ca/IMG/zip/DICOM-2.zip

http://recit.cssamares.qc.ca/IMG/zip/DICOM-2.zip

http://recit.cssamares.qc.ca/IMG/zip/DICOM-2.zip


Pur non essendo ad oggi localizzato in Italiano, esso e facilmente traducibile. E

infatti sufficiente aggiungere un file di dizionario italiano e tradurne l’interfaccia

(per la verita non molto ricca).

Il sistema funziona tramite dizionario pesato a singolo termine aperto (vedi 3.3.1).

Presenta un vocabolario in formato .dic che altro non e se non un file di testo

dove, ad ogni termine, viene fatto corrispondere un vettore di peso.

Il programma, all’avvio, si posiziona sulla barra delle notifiche di Windows.

Cliccando sull’icona relativa e possibile configurarne le opzioni.

Ogni volta che viene premuto un tasto compare la finestra di predizione che

suggerisce i termini piu frequentemente utilizzati in base alla radice immessa.

Anche in questo caso il software non e in grado di determinare la tipo-

logia di controllo focalizzato dall’utente, dunque non sarebbe in grado di deter-

minare il contesto. L’inserimento nell’applicazione della parola avviene mediante

copia/incolla.

3.5.6 Farfalla Editor

Farfalla e un progetto italiano nato per costruire una interfaccia web di

aiuto alle persone disabili nell’immissione e nella lettura di contenuti sul Web.

Esso comprende anche un semplice editor completamente web-based destinato ad

utenti con difficolta motorie.

L’applicativo prende il nome di Farfalla Editor6 . Esso e completamente

gestibile mediante un tastierino 10 pulsanti (o anche dal classico tastierino a 17

tasti), un joystick o una tastiera ridotta.

Come si vede in figura 3.2, la pagina e suddivisa in tre zone fondamentali:

• Il box di inserimento, in cui e presente il testo gia scritto ed il cursore;

6Farfalla Editor puo essere testato online all’indirizzo http://www.farfalla-project.it/demo/

http://www.farfalla-project.it/demo/

http://www.farfalla-project.it/demo/


Figura 3.2: L’editor Web Farfalla. Nell’immagine e possibile distinguere chiara-mente le diverse zone: il box di inserimento, il suggerimento, la tastiera a schermo(in cui e selezionata la lettera “B” ma non e ancora stata immessa), le istruzioni.Si puo anche notare la staticita del dizionario di predizione che, ad ogni spazio(ad ogni inizio parola), senza avere alcuna lettera a disposizione per effettuare lapredizione suggerisce “ciao” (quale parola piu probabile).

• La finestra di suggerimento, che suggerisce un completamento per la parola

che si sta scrivendo;

• La tastiera virtuale, contenente tutte le lettere. E possibile spostarsi fra le

lettere mediante le frecce destra e sinistra e confermare l’inserimento di una

lettera mediante la freccia giu;

• Le istruzioni e suggerimenti per l’utilizzo;

Ogni qualvolta viene inserita una lettera (o viene scelta la parola come completa-


mento) la pagina subisce un refresh ed il box di inserimento viene opportunamente

aggiornato.

Purtroppo il sistema di predizione non ci pare essere molto avanzato. Il

modello adottato e quello di dizionario pesato a singolo termine, come descritto

in 3.3.1.

L’aspetto negativo risiede nel fatto che, offrendo soltanto un suggerimento (la

lista dei termini comprende 1 elemento), e fortemente improbabile che questo

riesca a ridurre di molto il numero delle lettere immesse.

In piu c’e da notare che, dai test effettuati, non ci risulta che le parole completate

dall’utente e non contenute nel dizionario vengano aggiunte. Non siamo stati in

grado di osservare se i pesi all’interno del vocabolario vengano modificati con

l’utilizzo oppure siano statici.

3.5.7 Google Scribe

Google Scribe e stato un altro esempio gratuito di servizio online. Se nel

caso precedente si poteva parlare di servizio disponibile sul web, in questo caso

si ha un web service.

Scribe e stato un servizio offerto da Google all’interno dei Google Labs. Il siste-

ma offriva un predittore disponibile in moltissime lingue che sfruttava il corpus

gia indicizzato ed utilizzato da Google per altri servizi legati alle lingue come

l’autocompletamento durante la ricerca ed il servizio di traduzione.

Seppur ufficialmente abbandonato da tempo, non vi e piu alcun riferimen-

to ufficiale al progetto, e stato possibile fino a poco prima del termine della stesura

di questo lavoro interrogare il servizio mediante web service JSON con API non

ufficiali. Questo e stato sfruttato da molti progetti, specialmente open-source,

data l’elevatissima qualita delle predizioni offerte dal sistema.


Esso infatti era basato sul contesto e probabilmente sui modelli linguistici (ac-

cennati in 3.4.2 e discussi nel prossimo capitolo).

Scribe era l’unico sistema di predizione, individuato durante la stesura di

questo Lavoro, che fosse disponibile in Italiano, gratuito, liberamente utilizzabile

e di qualita molto elevata.

Purtroppo, non essendovi piu interesse o motivo per mantenere attivo il servi-

zio esso e stato chiuso prima che potessimo impiegarlo per effettuare dei test

comparativi.

I due software che presenteremo di seguito sono gli strumenti piu apprez-

zati per persone con disturbi specifici dell’apprendimento disponibili nel mercato

americano. I dati relativi alla loro completezza sono stati riportati nel dettaglio

in [spe]. Entrambi non sono disponibili in Italiano e per questo motivo li poniamo

al termine della trattazione.

Malgrado questo sono strumenti molto completi che presentano molteplici fun-

zionalita fra le quali la previsione del testo. Per un confronto dettagliato su tutte

le altre funzioni si invita a consultare [spe].

3.5.8 Co:Writer

Co-Writer7 e un prodotto commerciale di DonJohnston Technologies, un

evoluto sistema di predizione delle parole che si integra perfettamente con le

principali applicazioni. Oltre che per Windows esso e disponibile anche per il

sistema operativo Mac OS X.

Co:Writer supporta una predizione basata sul contesto. Viene fornito

gia con dizionari di parole sia per usi generici che per usi specifici. L’assor-

7Co-Writer – http://www.donjohnston.com/products/cowriter/index.html

http://www.donjohnston.com/products/cowriter/index.html


timento e davvero ricchissimo e consente di operare anche con piu dizionari

simultaneamente durante la costruzione di un testo.

Il software fa uso di language model (vedi 3.4.2) e di analisi sintattica della frase

inserita (secondo quanto dichiarato dallo stesso produttore). La configurazione

e ricca e permette una rapida creazione di nuovi dizionari a partire da testi

scelti dall’utente, consente di modificare i dizionari specifici esistenti, permette

di scegliere quante parole del contesto considerare.

Oltre a questo presenta delle funzioni molto interessanti per gli utenti di lingua

inglese come la correzione fonetica (vedi paragrafo 2.3) che consente di correggere

immediatamente errori derivanti dalle differenze fra i fonemi scritti e quelli parlati.

Oltre a cio sono individuate le forme verbali piu opportune all’interno della frase

che vengono ordinate nella lista dei termini piu in alto rispetto alle altre.

La predizione avviene mediante una finestra a scomparsa che si colloca nelle

vicinanze del punto di inserimento in cui e presente il cursore. E possibile sce-

gliere la parola da inserire mediante il click del mouse, tramite combinazione

di tasti oppure utilizzando un sistema a switch (supporto per l’inserimento con

scansione).

Co:Writer dispone inoltre di una sintesi vocale interna, mediante la quale e possi-

bile rileggere il testo inserito o pronunciare ciascuna parola ogni volta che questa

viene inserita.

3.5.9 Read&Write

Da quello che abbiamo potuto cogliere leggendo le caratteristiche, Read&Write,

prodotto da TextHelp Ltd. e il principale rivale di Co:Writer dal punto di vista

dell’integrazione con altre applicazioni e del Kurzweil 3000 per cio che riguarda

gli strumenti per lo studio.


Read&Write8 e un prodotto commerciale supportato dai principali produttori di

software.

Non abbiamo avuto modo di eseguire test ma da cio che abbiamo potuto leggere

sia all’interno della documentazione che all’interno delle comparazioni sembra il

sistema piu stabile ed utile a persone con difficolta di letto-scrittura.

L’interfaccia del programma e incentrata intorno alla barra degli strumenti Read&Write,

collocata nella parte alta dello schermo e sempre in primo piano.

Da questa e possibile scegliere molteplici funzionalita, sia legate alla lettura che

legate alla scrittura.

Esempi di funzioni che aiutano gli utenti nell’attivita di lettura sono la possibilita

di lettura continua e guidata dei PDF, strumenti per lo studio (evidenziazione,

aggiunta di commenti ecc.), la possibilita di leggere libri parlati per dislessici e

non vedenti nel formato DAISY, la disponibilita di strumenti per la scuola come

la calcolatrice ed il dizionario.

Anche in questo caso e pienamente integrato il supporto della sintesi

vocale. Questa, oltre che negli strumenti di lettura sopra descritti, puo essere im-

piegata durante la digitazione. Ad esempio e possibile leggere l’intera schermata

oppure configurare Read&Write perche pronunci ogni parola dopo che questa e

stata inserita in un editor.

Gli strumenti per la scrittura sono davvero molti. Si integra perfettamen-

te con i principali editor per Windows e per Mac OS ed offre funzionalita simili

a quelle presenti in Co:Writer. In piu, rispetto a quest’ultimo, presenta l’inseri-

mento guidato parole (WordWizard) che guida l’utente nella scelta di termini che

“suonano” simili (appaiono simili quando vengono pronunciati). Inoltre presenta

un dizionario dei sinonimi ed uno strumento di traduzione.

8Read&Write di TextHelp http://www.texthelp.com/UK/Our-products/Readwrite

http://www.texthelp.com/UK/Our-products/Readwrite

http://www.texthelp.com/UK/Our-products/Readwrite


La predizione viene effettuata con lo strumento WordPredictor che offre

il supporto al contesto (considerando fino a 3 parole precedenti alla parola che

si sta scrivendo). L’approccio e basato sull’analisi della frase e sui modelli del

linguaggio (discussi in 3.4.2).

I dizionari offerti sono specifici per le varie eta dell’utente ed e possibile costruire

nuovi vocabolari. Sono scaricabili dal sito del produttore dizionari specifici anche

se in numero minore rispetto a quelli offerti dal Co:Writer.

La predizione, come nel caso di Co:Writer viene presentata in una fine-

stra a scomparsa alla posizione del cursore. E possibile scegliere il termine da

inserire, all’interno della lista, mediante click, mediante combinazione tasti ma

non e presente la possibilita di utilizzo dei sistemi a scansione. Questo e dovuto

probabillmente al fatto che questo prodotto e rivolto in particolar modo a perso-

ne con DSA (disponendo anche molti strumenti di supporto alla lettura ed allo

studio).

CAPITOLO 4

Predizione basata sui Modelli del Linguaggio

4.1 Introduzione

Nello scorso capitolo abbiamo illustrato le varie modalita in cui viene

svolta la previsione delle parole. Abbiamo dato una definizione formale del pro-

blema, abbiamo mostrato come l’ordinamento delle parole all’interno della lista

dei termini sia centrale per giudicare la qualita di un sistema di predizione. So-

no poi stati illustrati alcuni esempi di sistemi di predizione, sia commerciali che

gratuiti. Abbiamo notato che gli strumenti piu validi ed utilizzati fanno uso dei

modelli del linguaggio (o language model o LM, in inglese).

In questo capitolo definiremo i modelli del linguaggio, spiegheremo come

questi modelli vengono costruiti e come vengono approssimati al fine di ottenere

buoni risultati. Descriveremo inoltre alcuni accorgimenti adottati nel tempo per

migliorarne la qualita. Contestualmente, negli esempi e nelle definizioni, cerchere-

mo sempre di tenere presente il nostro scopo: costruire un algoritmo di predizione

basato su questi modelli.

Predizione basata sui Modelli del Linguaggio 48

Infine descriveremo i problemi principali che affliggono questo tipo di tecnica e

proporremo brevemente alcuni studi che mostrano come e possibile migliorare la

qualita della predizione.

4.2 Modelli del linguaggio

Come riportato in [Hie] un modello del linguaggio e uno strumento in

grado di assegnare un valore di probabilita ad una porzione di testo non vista

basandosi sulle informazioni ricevute durante l’addestramento.

Il termine modello del linguaggio deriva dai modelli probabilistici per

la geneerazione del linguaggio sviluppati per il riconoscimento automatico della

voce all’inizio degli anni ’80. Come riportato anche in [HT09] si e trovata la

possibilita di formalizzare il problema della previsione delle parole descrivendolo

come la capacita di predire una parola wn date le N − 1 parole precedenti. Un

modello del linguaggio (o modello ad n-grammi) e una distribuzione di probabilita

sulle possibili sequenze di termini.

Facciamo un esempio:

Esempio 4.1. In un modello del linguaggio italiano, addestrato su testi di nar-

rativa per l’infanzia c’e una possibilita non nulla di trovare una sequenza del

tipo:

[...]nel cielo azzurro dove volano i gabbiami[...]

La probabilita di trovare la stessa sequenza su un modello di linguaggio allenato

su una collezione di articoli scientifici, sempre in lingua italiana, e decisamente

inferiore.

Come abbiamo visto da questi primi esempi il modello del linguaggio si

basa su testi “conosciuti” per poter prevedere sequenze di parole in testi “sco-

49 Modelli del linguaggio

nosciuti”. Durante lo sviluppo di un modello del linguaggio possiamo suddivi-

dere i documenti appartenenti ad uno stesso ambito in tre insiemi disgiunti (un

documento appartiene solo ad uno degli insiemi):

Training set (o insieme di addestramento): questo e l’insieme dei documen-

ti impiegati per l’addestramento del modello del linguaggio. Sara in base

a questi documenti che il nostro modello calcolera le probabilita delle se-

quenze di termini. Maggiore e il numero di documenti destinato a questo

compito, meglio il modello si formera rispetto all’insieme di documenti che

vogliamo valutare;

Test set: Questo insieme di documenti e quello che fa uso del linguaggio. So-

litamente e di dimensione inferiore rispetto al training set. Proprio al fine

della valutazione di un modello risulta fondamentale che training set e test

set non coincidano in nessuna parte.

Held-out set: Come riportato in [HT09] in aggiunta a training e test set un’altra

piccola quantita di dati puo essere utile. Ci potra essere utile una sorgente

aggiuntiva di dati per arricchire il nostro insieme di training. Tali dati

aggiuntivi si chiamano Held-out.

L’impiego di un modello del linguaggio (o piu modelli) puo risultare utile

nello svolgimento di una gran quantita di compiti come la correzione automa-

tica delle parole, la generazione di frasi da parte del computer, la traduzione.

Lo strumento inoltre e di aiuto in compiti di riconoscimento come nel caso del

riconoscimento vocale del riconoscimento ottico dei caratteri (OCR), al fine di

individuare le sequenze piu probabili per segmenti rilevati in maniera incerta.

Noi vogliamo invece impiegare i modelli del linguaggio per la predizione

delle parole. Ripartendo dall’equazione 3.1, vorremmo poter calcolare, basandoci

su un modello del linguaggio, la probabilita:


P (wn|w1, . . . wn−1 (4.1)

Prima di procedere pero e necessario definire una terminologia ed una simbologia

che utilizzeremo all’interno di questo capitolo.

4.3 Simbologia e convenzioni

• Una frase (o sentence) in inglese e una unita costitutiva del linguaggio

scritto;

• Il vocabolario (V) in inglese Types e il numero di parole distinte all’interno

del corpus (di training);

• Le istanze (n) in inglese tokens e il numero totale delle parole (anche

ripetute);

• N-gramma e una sequenza di parole dove (N) e il numero di parole consi-

derate;

• C(x) e la counting function, una funzione che conta il numero di volte in

cui appare un determinato input x nel corpus (di training);

4.4 La necessita dell’approssimazione: Gli N-grammi

Per definire la funzione di probabilita in equazione 4.1 possiamo fare uso

della formula di base per il calcolo della probabilita condizionata.

P (B|A) =P (A ∩B)

P (A)

51 La necessita dell’approssimazione: Gli N-grammi

In particolare potremmo ottenere la probabilita dell’intersezione A ∩ B

contando il numero di volte in cui all’interno del corpus appare il contesto (A)

seguito dal lemma (w preso in esame (B).

Divideremmo poi per il numero di volte in cui il contesto e seguito da qualunque

altra cosa (ossia il numero di volte in cui il contesto appare).

Riprendendo l’esempio refesempio possiamo definire la probabilita condi-

zionata mediante la funzione Count come segue:

P (piatto|<s>la minestra e nel) =C(< s > la minestra e nel piatto)

< s > C(la minestra e nel)(4.2)

Utilizzando i termini abituali definiti nel capitolo precedente potremmo

dire che un primo algoritmo per la predizione basato sugli n-grammi funziona in

questo modo:

• Si inseriscono in una lista tutti i termini che iniziano con la radice (lista

possibili);

• Si considera come contesto l’intera frase corrente;

• Per ognuno dei termini t nella “lista possibili” si calcola la probabilita come:

P (t|c1 . . . cn) =C(c1, . . . , cn, t)

C(c1 . . . cn)

• Infine si ordinano in base alla probabilita decrescente;

Formalmente, come abbiamo detto, un modello del linguaggio viene uti-

lizzato per prevedere la probabilita di una sequenza di termini. Adottando un

modello di questo tipo potremmo dire che


P (< s > La minestra e nel piatto) =

P (La| < s >) · P (minestra| < s > La) · . . . · P (piatto| < s > La minestra e nel )

In generale la probabilita di avere una sequenza w1, . . . , wn sara data da:

P (w1, ..., wn) =n∏

k=1

P(wk|wk−1

1

)(4.3)

Il problema, come intuibile, risiede nel fatto che piu si allunga la sequenza

(piu grande e il contesto), meno e probabile che vi siano dei documenti nel training

set che contengano delle frasi identiche a quella che si vuole valutare nel test set.

Per questo si fa uso dell’approssimazione. Ad esempio potremmo dire che:

P (wn|w1 . . . wn−1) ≈ P (wn|wn−1) (4.4)

In tal modo riduciamo la condizione della probabilita dall’intera sequenza del

contesto, semplicemente all’ultimo stato “visitato”. A questo punto possiamo

calcolare la probabilita di una intera frase percorrendola, come fosse una catena

di Markov.

Il modello definito nell’equazione 4.4 si chiama modello a bigrammi (o a

2-grammi o di “classe 2”) in quanto considera soltanto la parola corrente ed una

parola del contesto. Un modello a 3-grammi considera soltanto la parola corrente

e le 2 parole precedenti nel contesto. Per questo un modello ad N-grammi, dove N

e inferiore al totale delle parole nella sequenza, e un modello che puo approssimare

il modello del linguaggio di base.

E possibile formalizzare questo concetto in modo generico. Dato N il

parametro che identifica la classe del modello ad N-grammi possiamo definire

l’equazione in 4.1 come:

53 Valutazione di un modello

P (wn|w1, . . . wn−1) =

P(wn|wn−1

1

)≈ P

(wn|wn−1

n−N+1

) (4.5)

Dove P (wn|wn−1n−N+1) puo essere stimato con la funzione Count sopra

definita quindi:

P(wn|wn−1

n−N+1

)=

C(wn−1

n−N+1, wn

)C(wn−1

n−N+1

) (4.6)

Questa stima e simile a quanto avevamo fatto nell’esempio con l’approccio privo

di appprossimazione in equazione 4.2. La stima definita nell’equazione 4.6 viene

chiamata MLE (Maximum Likelihood Extimation).

4.5 Valutazione di un modello

Con il procedimento sopra descritto e possibile costruire diversi modelli

per diverse classi di N-grammi e valutare, tramite il test set, la qualita di un

modello a bigrammi piuttosto che a trigrammi ecc.

La premessa importante da fare e che, in questo caso, stiamo parlando di valuta-

zione di modelli diversi (a bigrammi, a trigrammi, ma anche piu avanzati come

vedremo nel seguito), modelli che sono costruiti a partire dallo stesso training set

e testati mediante lo stesso testset.

In generale, per valutare la qualita dei modelli del linguaggio ci sono due

metodologie come riportato in [HT09].

Metodo estrinseco: che consiste nella costruzione di un algoritmo che faccia

uso di modelli del linguaggio per risolvere un problema. In tal modo si


puo valutare la qualita impiegando, all’interno dell’applicazione, i diversi

modelli da confrontare;

Metodo intrinseco: E costituito da una metrica, da una misura. Esso e assai

piu generico ma e piu rapido da utilizzare.

La misura intrinseca per la valutazione di un modello linguistico e la perplexity

(tradotto in italiano con “perplessita”) di cui discuteremo in seguito nel paragrafo

4.5.2.

Prima di cio, dato che questo lavoro riguarda in modo particolare i sistemi

di predizione, vogliamo proporre un approccio, adottato nel seguito per valutare

la qualita del nostro applicativo.

4.5.1 Valutazione estrinseca mediante i sistemi di predizione

Al fine di poter valutare la qualita della predizione di diversi modelli del

linguaggio e possibile adottare diverse misurazioni.

In primo luogo si puo adottare il Mean Reciprocal Rank (MRR). Nella

sua forma basilare questa statistica restituisce il valore medio dei reciproci dei

“rank” di una serie di query.

In [Voo99], L’MRR viene descritto nel modo seguente: Data la lista ordinata di

risposte di una query, una singola query riceve un punteggio uguale al reciproco

della posizione (rank) della lista in cui si trova la prima risposta esatta oppure 0

se nessuna delle risposte nella lista sono corrette. Il valore complessivo dell’MRR

per l’insieme di query e quindi la media (matematica) dei punteggi di ciascuna

delle query.

Definendo come R l’insieme che contiene, per ciascuna query, la posizione

nella lista (il rank) in cui si trova il primo risultato valido ed utilizzando la

definizione di media possiamo definire l’MRR come:


1 oltre2 oggi3 ogni

1 passa2 pare3 penso

(a) (b)

Figura 4.1: (a) immagine della lista di parole con relativi rank della previsionedi “oggi” dato “o”. (b) La lista di parole con relativi rank della previsione di“piove” dato “p”

MRR =1

|R|

|R|∑k=1

1

rankk

(4.7)

Nel caso specifico del problema della predizione, se volessimo l’MRR di un qualche

modello nel corpus di test composto esclusivamente dalle due parole “oggi piove”

potremmo procedere in un modo simile al seguente:

Passiamo all’algoritmo (che ha caricato il modello in esame) il primo elemento del

contesto “<s>” e l’iniziale “o”. Impostiamo la lunghezza della lista dei termini

a 3.

Esso, in base al modello, ci restittuira un elenco di scelte come in figura 4.1(a)

L’inverso del rank di “oggi” e 1/2

Ora ripetiamo la stessa cosa passando all’algoritmo il contesto “<s >oggi ” e

l’iniziale “p”. La lista dei termini si puo vedere in figura 4.1(b).

In questo caso abbiamo come reciproco del rank 0 (in quanto anche il rank e 0).

Calcoliamo quindi la media:

(1/2 + 0)/2 = 1/4 = 0, 25

In tal modo e semplice valutare la qualita di differenti modelli.

Il problema sorge poiche questa tecnica non permette di rispecchiare la

reale necessita di un software di predizione delle parole. Infatti nel momento in


cui una parola appare nell’elenco fornito all’utente, poco importa che essa sia in

prima, in seconda o in decima posizione. L’unica cosa che conta e che l’utente la

veda e la possa inserire.

Per questo sarebbe necessario modificare il meccanismo di rank ponendo sempli-

cemente un peso 1 se la parola e all’interno della lista o un peso 0 se essa non

appare.

Un secondo problema che affligge questa metrica e relativa al numero di

iniziali che vengono passate all’algoritmo. Per come abbiamo definito la query e

necessario mantenere un valore costante fra le diverse parole e fra i diversi modelli

affinche la misura abbia un significato.

Modificando la query potremmo decidere di procedere in questo modo:

assegnamo peso 1 se l’utente visualizza nella lista delle parole il termine desiderato

inserendo una sola lettera, assegnamo peso 2 se l’utente visualizza nella lista delle

parole il termine desiderato inserendo due lettere, ecc. Se l’utente e costretto a

scrivere l’intera parola, assegneremo peso 0.

Abbiamo pero descritto come, i sistemi di predizione, debbano venire

incontro a taluni utenti riducendo il numero di tasti da premere.

Questa misurazione non tiene conto di tale requisito. Infatti e piu importante

che un sistema di predizione riesca a predire in tempo parole lunghe piuttosto

che parole brevi.

Ecco due esempi: Poniamo che l’utente desideri inserire la parola “di-

cendo”. Scrivera il prefisso “d”. All’interno della lista dei termini non compare

dicendo. L’utente immette “di”, neanche questa volta la parola appare, l’utente

immette “dic”, questa volta la parola dicendo e in lista.

Secondo la misurazione MRR, che abbiamo modificato, l’utente ha un

rank di 3, non bene ma neanche troppo male.

Osservando la cosa da un altro punto di vista, l’utente ha premuto 4 tasti: le tre


lettere ed il tasto di selezione. L’utente ha risparmiato 3 battiture.

In seguito alla parola “dicendo” l’utente vuole scrivere “di”. Inizia quindi scri-

vendo la prima iniziale “d”. “di” appare immediatamente nella lista dei termini.

Apparentemente e una cosa utile, la nostra metrica MRR lo premierebbe con un

rank di 1, ma lo e davvero? Per selezionare la “i” sulla tastiera l’utente preme

un tasto, per scegliere la parola l’utente compie sempre una battitura.

Il valore del predittore (e del modello che ne fa uso nel caso si confronti

lo stesso algoritmo che fa uso di LM con modelli diversi) e molto maggiore nel

primo caso anche se, per ben tre volte, la parola non e comparsa all’interno della

lista dei termini. Tale misura viene chiamata “battiture risparmiate” Keystroke

Saving (KS) come riportato in [GVA06].

E possibile utilizzare altre modalita di valutazione piu avanzate. Ad

esempio il tempo impiegato da un utente per la selezione, la differenza fra il tempo

impiegato per immettere una parola mediante il predittore o tramite il dispositivo

di input in uso. [GVA06] Tuttavia riteniamo tali misure troppo soggettive e troppo

legate alle difficolta di un singolo utente. Per questo nel seguito ci limiteremo ad

impiegare queste metriche.

4.5.2 Perplexity

La misura della perplexity serve, in generale, per valutare la qualita di

differenti language model dato un insieme di test.

Come abbiamo detto essa e una metrica (una misura intrinseca). Non necessita

di riprodurre particolari problemi per effettuare una comparazione fra due o piu

linguaggi con uno stesso insieme di test o dello stesso linguaggio allenato su

training set diversi.

Come riportato in [HT09], dati due modelli probabilistici il migliore fra

i due e quello che si adatta meglio all’insieme di test (o che e in grado di predire


meglio i dettagli dei dati di test).

E possibile misurare la predizione migliore osservando la probabilita che viene

assegnata da un modello ai dati di test. Il modello migliore e quello che assegna

una probabilita piu alta a questo tipo di dati.

Come spiegato anche in [HT09], si definisce la misura della perplexity

(o PP in formula) di un modello del linguaggio su un insieme di test, la funzione

di probabilita che il modello assegna alla sequenza di termini dell’insieme di test

normalizzata sul numero di termini. Essa si esprime come in formula 4.8. La

formula puo essere riscritta come in equazione 4.9.

PP (W ) = P (w1, w2 . . . wn)−1n (4.8)

= n

√1

P (w1, w2, . . . wn)(4.9)

=n

√√√√√ 1n∏

k=1

P (wk|w1, . . . , wk−1)(4.10)

E possibile ottenere la 4.10 applicando l’equazione 4.3.

Come abbiamo detto, nel caso degli N-Grammi si puo avere una approssi-

mazione. Il contenuto del denominatore nella formula 4.10 verra opportunamente

sostituito in base all’equazione 4.5.

Ad esempio, se volessimo stimare la perplexity di un modello basato sui bigrammi,

sostituendo nell’equazione 4.10 quanto previsto nella formula 4.4 procederemo in

questo modo:

59 Miglioramenti del modello: Smoothing e Back-Off

PPbigram(w1, . . . wn) = n

√√√√√√√ 1

n∏k=1

P (wk|wk−1)

Come si puo notare dalle equazioni 4.9 e 4.10, la probabilita calcolata appare

sempre al denominatore della frazione. Questo porta ad affermare che maggiore

e la probabilita, minore e la misura della perplexity.

Dall’intuizione descritta in precedenza, quindi, il modello migliore e quello

con una misura di perplexity piu bassa. Per [HT09], infatti, minimizzare la

perplexity e equivalente a massimizzare la probabilita dell’insieme di test in base

al modello del linguaggio dato.

Vi e una stretta relazione fra la misura della perplexity ed il concetto di

entropia dell’informazione e di entropia incrociata (cross-entropy). Cio va pero

oltre gli scopi di questo capitolo.

Per ulteriori dettagli e per una definizione della perplexity anche come branching

factor di un linguaggio si invita a consultare la bibliografia in [HT09].

4.6 Miglioramenti del modello: Smoothing e Back-Off

Riprendiamo il modello ad N-grammi descritto in 4.4.

Come riportato in [HT09], mano a mano che il numero N degli n-grammi

analizzati e grande (per N = 2, 3, 4, . . . ecc.), migliori sono i risultati che il sistema

puo dare. Per spiegare questo, in [HT09] si riportano alcuni esperimenti svolti

da Shannon prima e da Miller e Selfridge poi. Lo scopo era quello di costruire

dei sistemi di generazione automatica di sequenze di parolem basate su modelli

del linguaggio addestrati in un corpus contenente opere di Shakespire.


Si e visto che mano a mano che li numero N aumentava (aumentavano le

parole da cui dipendeva la probabilita della successiva), di pari passo aumentava

e migliorava anche il significato delle sequenze generate. Con N troppo piccoli, le

parole erano casuali (come estratte a caso da un’urna).

Riportando per un momento l’attenzione sul problema della predizione, potrem-

mo dire in maniera generica che piu grande e N (piu ci guardiamo indietro al-

l’interno del contesto), piu la nostra predizione sara esatta a patto che una frase

simile, a quella che vogliamo scrivere compaia nel corpus di addestramento.

Cio pero ci porta ad un problema: Se viene scelto un N troppo piccolo

la predizione si avvicina molto al limite di ‘N = 1, in cui e un “tirare a sorte” la

parola piu probabile che succede alla precedente. Al contrario, se scegliamo un N

troppo grande rischiamo di non avere la possibilita di predire nulla, poiche non e

detto che la frase che vogliamo scrivere sia contenuta nel corpus e ci avviciniamo

sempre di piu alla situazione di base (senza approssimazione).

Le soluzioni che possiamo utilizzare sono di due tipi (da impiegare anche in

combinazione fra loro):

Smoothing (discounting): si cerca di “normalizzare” le probabilita poiche delle

sequenze che compaiono raramente nel corpus (che hanno una probabilita

bassa) potrebbero essere comunque valide. Oltre a questo c’e il problema

che nessun corpus e abbastanza grande per contenere tutte le possibili se-

quenze, e ci potrebbero essere delle sequenze di parole accettabili che hanno

probabilita 0.

Back-off ed Interpolazione : Se una determinata sequenza ha probabilita 0

(o molto vicina allo 0), al posto di restituire questa probabilita si analizza

l’(N − 1)-gram. Ad esempio, se un trigramma ha una probabilita di 0 (o

molto bassa) si passa ad analizzare il bigramma costruito sulle ultime due


componenti del trigramma. Parlando in maniera generale possiamo dire

che “dimentichiamo” una parte del contesto.

Un ultimo problema e quello dell’underflow. Poiche la probabilita di una

sequenza di parole e data dal prodotto delle probabilita, e queste sono sempre

numeri compresi fra 0 e 1, ci potremmo trovare a lavorare con numeri molto

piccoli. Per questo i tool, al posto di moltiplicare le probabilita, sommano i

relativi logaritmi.

Ora diamo un rapido sguardo a ciascuno dei due miglioramenti alla stima

MLE proposti in [HT09].

4.6.1 Smoothing

Come abbiamo detto lo smoothing viene utilizzato per spostare parte

della probabilita dalle sequenze piu probabili verso quelle meno frequenti nel

corpus di test (o a probabilita 0). Questo, come detto, e utile per evitare che

sequenze di parole perfettamente lecite risultino avere probabilita nulla.

Un altro problema delle sequenze a probabilita 0 e quello della misura di

Perplexity. Come riportato in [HT09], la definizione data di Perplexity richiede

che venga calcolata la probabilita di ogni frase nell’insieme di test. Ma se una

frase ha un N-Gram che non appare (poiche la probabilita viene moltiplicata)

essa risulta avere probabilita 0.

Laplace o Add-one Smoothing : L’idea e quella di aggiungere una costante

1 ad ogni count. Ad esempio nel caso di un unigramma

MLE→ P (wk) =ckn

Add-one→ P (wk) =ck + 1

n+ V


Cio pero aumenta troppo le probabilita che prima erano a 0. Si potrebbe

usare un fattore decimale ma la tecnica non e molto impiegata.

Good-Turing : Come descritto in [HT09] si procede suddividendo gli N-Grammi

in diversi insiemi (la cui cardinalita e I), in base alla loro occorrenza. Ad

esempio definisce l’insieme di cardinalita I0 degli N-Grammi che occorrono

0 volte, I1 di quelli che occorrono nel corpus una sola volta, generalizzando

Ic il numero di N-Grammi che compaiono c volte. Il Good-Turing smoo-

thing sostituisce il contatore standard della stima MLE con un contatore

che guarda Ic+1 dove c e il numero di volte in cui compare l’N-Gram in

esame (il contatore di base dell’MLE).

Per gli N-Grammi che compaiono una o piu volte il nuovo contatore e

definito come c∗ = (c + 1) Ic+1

Ic. Se invece l’N-Gramma compare 0 volte

e necessario sostituire l’intera probabilita. Ad esempio (per mantenere le

convenzioni di lettere), nel caso gli 1-grammi

PGT (termine occorra 0 volte) =I1n

[HT09] riporta che lo smoothing cosı ottenuto e molto piu efficacie rispetto

al metodo di Laplace tuttavia vi sono diversi problemi. Ad esempio cosa

sucede se l’insieme Ic+1 non contiene elementi? Per ulteriori dettagli si

invita a consultare [HT09].

La tecnica frequentemente utilizzata nelle applicazioni piu moderne, se-

condo quanto riportato in [HT09], e chiamata Knesser-Ney Smooting. Essa si

basa sull’absolute Discounting che lavora eliminando una parte (fissata) da ogni

count. Per ulteriori dettagli si veda [HT09].


4.6.2 Back-off ed interpolazione

Come abbiamo descritto, e possibile che un modello venga costruito su

trigrammi ma che la sequenza cercata abbia probabilita 0 poiche essa non e con-

tenuta nel training corpus. Ad esempio il corpus non contiene alcuna occorrenza

de “e nel piatto” quando vogliamo valutare P (piatto|e nel). Magari pero il no-

stro corpus contiene un trigram del tipo “sono nel piatto”. Vorremmo poter

ricalcolare la probabilita ed analizzare i bigrammi (“nel piatto”).

Esistono due modi distinti per fare cio

• Back-off, come riportato da [HT09], si torna indietro all’N-Gramma pre-

cedente soltanto se la probabilita della sequenza e 0;

• Interpolazione, si mescolano sempre le probabilita derivanti dalle diverse

stime di N-Grammi (dalla massima alle minori).

L’interpolazione consiste nell’assegnare dei coefficienti moltiplicativi (de-

finiti in [HT09] come λ) alle varie probabilita di ciascuna classe di N-grammi che

viene combinata. Riprendendo l’esempio precedente, verranno sommate le pro-

babilita di unigrammi, bigrammi e trigrammi. Ad ognuna di queste probabilita

verra moltiplicata una costante λ1, λ2, λ3.

Tali costanti moltiplicative possono essere assegnate staticamente (in base ad una

proporzione o ad un fattore costante) tali da far risultare la probabilita finale

minore di 1. Una seconda possibilita e di costruire dinamicamente le costanti

moltiplicative basandosi sull’held-out corpus.

Il Back-off implementativamente si basa su una funzione ricorsiva che

procede esplorando gli (N − 1)-grammi piu piccoli fino a quando si raggiungono

gli unigrammi oppure fino a quando si trova una probabilita maggiore di 0. Ad

ogni passo vengono aggiunte delle costanti che variano a seconda della tecnica


di Back-off utilizzata. Un esempio e il Katz backoff descritto in [HT09] che

integra il Good-Turing Discounting.

4.7 Il superamento di un approccio basato soltanto sui mo-

delli del linguaggio

Seppur il nostro lavoro ha portato alla costruzione di un predittore di

parole, al momento basato soltanto sui modelli del linguaggio, siamo ben consci

che questo puo rappresentare solo il primo passo. Riteniamo pero che esso sia

indispensabile per la costruzione di un predittore di buona qualita.

In [Ros00], l’autore riporta in maniera dettagliata quali siano i problemi

di cui sono afflitti i moderni sistemi basati soltanto su modelli del linguaggio ad

N-Grammi.

In primo luogo c’e, come gia abbiamo sottolineato in queste pagine, l’estrema

fragilita delle applicazioni se utilizzate in domini differenti da quelli dei documenti

di training. In aggiunta, come viene riportato da [Ros00], questa fragilita si nota

molto anche per delle variazioni che sembrano scontate ad un essere umano. Un

modello del linguaggio allenato su documenti provenienti da news di Dow-Jones

vede la sua perplexity raddoppiare quando viene testato su documenti simili

provenienti dall’Associated Press.

Un secondo problema presentato e la cosiddetta assunzione errata di

indipendenza (false indipendence assumption). Per poter essere gestibili, i mo-

delli del linguaggio vengono spesso sottoposti a delle assunzioni di indipendenza,

ad esempio nel caso di un modello ad N-Grammi si presuppone che la probabilita

di una parola in una frase dipenda soltanto dalle precedenti (n− 1) parole. Ep-

pure, come riporta Rosenfeld, anche un rapido sguardo a questo testo dimostra

65 Il superamento di un approccio basato soltanto sui modelli del linguaggio

come questo assunto sia completamente falso.

Partendo da un assunto falso, e evidente che un modello statistico ci dara dei

risultati in cui l’errore e lontano dallo 0.

Se ci concentriamo nello specifico sull’analisi dei problemi presenti in

un sistema di predizione basato soltanto sui language model, dobbiamo tenere

presente che anche il grado di inflessione di una lingua ne influenzera il risultato.

Come riportato in [ACD+07], infatti, se l’Inglese e una lingua con scarse

inflessioni, lingue come l’Italiano sono al contrario lingue contenenti moltissime

forme flesse. Cio presenta dei problemi in quanto le varie forme dei verbi, i diversi

tempi e modi, portano ad una sparsita dei dati partendo da qualnuque corpus

letterario.

Una possibile soluzione proposta in [ACD+07] e l’utilizzo di tecniche com-

binate. Gli autori si propongono di combinare il risultato derivante dai Language

model con un POS-Tagger.

L’algoritmo proposto si basa sulla combinazione lineare. L’approccio della com-

binazione lineare fa uso di trigrammi POS (un language model costruito sul POS

anziche sui termini), affiancati ad un semplice modello di parole a bigrammi.

L’algoritmo da noi proposto estende questa tecnica e la adatta alle lingue inflesse

come l’Italiano. Esso combina un modello basato su n-grammi POS con un se-

condo modello ad n-grammi basato su parole opportunamente taggate [ACD+07].

L’ultimo problema che riportiamo, evidenziato in [WA07] e la difficolta

nell’adattamento di un predittore basato soltanto su modelli del linguaggio ad un

contesto di utilizzo che puo variare. In [WA07] si propone un predittore per la

lingua francese (anch’essa lingua fortemente inflessa).

Gli autori si propongono di combinare e migliorare la predizione offerta dai lan-

guage model utilizzando l’LSA. Molte sono le tecniche descritte in cui viene in-

terpolato il risultato derivante dall’LSA con le predizioni ottenute dai language


model. Ci e sembrato interessante che la semplice aggiunta di un meccanismo di

“semantic cache” possa portare ad un miglioramento complessivo del sistema.

Come si vede le soluzioni ai problemi posti sono diverse. La ricerca e

attiva in diversi fronti, tuttavia alla base di molti dei moderni sistemi di predizione

vi sono i modelli del linguaggio. L’affinamento, l’adattamento e l’integrazione con

altre tecniche di questi modelli rappresenta il futuro di questo settore.

CAPITOLO 5

Il sistema di scrittura facilitata PredictEdit

5.1 Introduzione

Nel capitolo 2 abbiamo analizzato in maniera lineare quali siano le esi-

genze e le aspettative degli utenti per un buon sistema di predizione delle parole.

Nel capitolo 3 abbiamo poi presentato le moderne tecniche con cui questi prodotti

vengono sviluppati ed abbiamo raffrontato vari software, sia commerciali che a

pagamento, disponibili per il mercato italiano ed internazionale.

Ci siamo resi conto che i prodotti che riscuotono maggior successo all’estero fan-

no uso dei modelli del linguaggio. Abbiamo quindi dedicato l’intero capitolo 4

alla presentazione di questo genere di modelli statistici sempre nell’ottica della

costruzione di un moderno sistema di predizione delle parole.

In questo capitolo presenteremo il PredictEdit, un software per la scrit-

tura facilitata di testi adatto a persone con disabilita fisiche o affetti da disturbi

specifici dell’apprendimento.

Durante la progettazione dell’applicazione ci siamo resi conto che era

Il sistema di scrittura facilitata PredictEdit 68

necessario sviluppare, complementarmente, due parti distinte.

Da un lato infatti era necessario un motore per la predizione, nel nostro caso

basata sui modelli del linguaggio, al fine di poter mettere alla prova l’interfaccia

utente in sviluppo.

Daltronde, senza un’interfaccia utente, sarebbe stato difficile effettuare con sem-

plicita dei test sul motore di predizione che volevamo creare.

In questo capitolo illustreremo nel dettaglio:

• Come e stato costruito il modello del linguaggio su cui si appoggia l’algo-

ritmo di predizione;

• La costruzione dell’interfaccia per i motori di predizione (IPredictor) e l’im-

plementazione della classe del predittore basato sui modelli del linguaggio

(NGPredictor);

• L’implementazione di IPredictor per costruire un motore di predizione ba-

sato su Google Scribe (GSPredictor);

• La costruzione dell’interfaccia grafica e dell’editor (il PredictEdit);

• La costruzione dell’interfaccia integrata con altre applicazioni (PredictiOn-

demand)

Il linguaggio di programmazione per lo sviluppo dell’applicativo (Predic-

tEdit, PredictiOnDemand e Predictors) e stato Microsoft Visual C# con librerie

Microsoft .NET versione 3.5 (in modo da garantire la compatibilita anche con il

passato Windows 2k). Si e comunque mantenuta una completa compatibilita dei

sorgenti con il moderno Microsoft.NET 4.5.

Differente invece e il linguaggio con cui sono stati scritti gli script per il

processamento del corpus per i quali si e scelto Python2.

69 Sviluppo del modello del linguaggio

5.2 Sviluppo del modello del linguaggio

In questa sezione analizzeremo tutti i passi necessari per costruire il mo-

dello del linguaggio e la struttura adatta ad ospitarlo. Il motore di predizione

dovra riuscire ad accedere ai dati nel modo piu rapido e logico possibile.

Nel progettare tale struttura terremo conto di requisiti di memoria e di rapidita

richiesta dal sistema.

5.2.1 La costruzione del corpus

Per la costruzione del motore di predizione, in questa fase, si e deciso

di utilizzare un approccio a “dizionario chiuso”. Il modello del linguaggio viene

costruito a partire da un dizionario dato e successivamente allenato con un insieme

di documenti. L’utente non puo modificare il modello che rimane quindi statico.

Le statistiche del modello non vengono modificate dai testi che, giorno per giorno,

l’utente scrivera.

Per la costruzione del modello si e scelto di procedere utilizzando il corpus del

Parlamento Europeo (europarl) [Koe05]. Si e operata questa scelta dato che tale

corpus e disponibile sia in lingua inglese che in italiano. In tal modo e possibile

confrontare i risultati della predizione anche in diverse lingue con una relativa

semplicita.

Per prima cosa abbiamo analizzato il corpus per osservare come fosse

strutturato il contenuto. All’interno di ogni file vi erano gli atti del parlamento

europeo (raggruppati per mesi). Tali atti erano opportunamente taggati per

spiegare chi fosse l’oratore e altre informazioni strutturate.

Il primo passo che abbiamo compiuto e stato quello di suddividere i do-

cumenti fra training set e test set. Come training set abbiamo scelto tutti i


documenti a parte quelli dell’anno 2000 (che sono stati dedicati al test set per i

test automatizzati).

I testi destinati al training vengono inseriti all’interno della directory trainingset,

al contrario i documenti per il test vengono inseriti all’interno di testset.

Si e proceduto poi alla scrittura dello script Python (mkcorpus.py) per

la costruzione del documento di training da passare al software per la creazione

dei modelli del linguaggio.

Tale script applica le azioni sotto descritte per ogni file contenuto nelle due cartelle

trainingset e testset.

I vari documenti vengono, contestualmente, concatenati creando i due file cor-

pus.txt (da usare per il training) e test.txt (da usare per il test).

• Dal testo vengono eliminate tutte le informazioni strutturate, come i nomi

dei vari relatori, i ruoli ecc. Vengono inoltre eliminati i riferimenti. Questo

lavoro viene svolto eliminando tutto cio che si trova fra parentesi quadre,

tonde ed angolari;

• Il testo viene tokenizzato manualmente. La punteggiatura viene “spazia-

ta” in modo tale che anche le virgole, i simboli, i trattini ecc. vengano

considerati come delle parole;

• Le virgolette vengono disambiguate. La parola composta dal simbolo ¨

infatti puo significare sia aperte che chiuse virgolette. Le aperte virgolet-

te vengono convertite in ’’, mentre le chiuse restano ¨. Tale funzione

verra impiegata per usi futuri ma ci sembrava utile partire da un corpus

processato al meglio delle nostre possibilita.

• Sono eliminati i \n. Le parole ., ?, !, :, le chiuse virgolette seguite da un

punto e le chiuse virgolette precedute da un punto vengono considerati fine


frase. Vengono quindi aggiunti gli identificatori di fine frase dopo di essi,

il carattere nuova riga e il carattere di inizio frase. Ad esempio il . viene

sostituito con . </s> \n <s> ;

• Viene svolto un piccolo clustering per quello che riguarda le date (che

sono convertite in #DATE), gli anni (#YEAR), le ore (#HOURS), i gradi

(#DEGREE).

• Poiche e inutile mantenere delle statistiche sui numeri (sulle cifre) dato che

e fortemente improbabile che un utente voglia inserire lo stesso numero che

viene riportato in un testo del corpus, si e deciso di sostituire tutti i numeri

con #NUMBERS;

• Vengono poi svolte conversioni minori;

• Infine sono tenute in considerazione per il corpus solo frasi composte da

almeno k termini, dove k e impostato, di default, ad 8.

Seppure siamo consci che questo script sia ben lontano dal risolvere o

coprire i molti problemi di ambiguita della lingua inglese (o italiana), abbiamo

ritenuto comunque interessante procedere alla costruzione di un modello. Proprio

perche siamo convinti che tale script sia ancora migliorabile, al momento non e

consentito all’utente di costruire un proprio modello partendo da documenti scelti

o ricercati dal programma all’interno del computer.

5.2.2 Dal corpus al Modello del Linguaggio in formato ARPA

Terminato di processare il corpus si procede alla costruzione del vocabo-

lario ed in seguito del modello del linguaggio.

Per questo scopo si sono trovati e testati due tool differenti: il CMU Language

Modeling Toolkit [Ros95] e lo SRI LM Toolkit [Sto02].


Inizialmente si era impiegato il CMU toolkit ma, poiche esso risulta non svilup-

pato da diverso tempo e non comprende tecniche di smoothing moderne (come il

Kneser-Ney), si e pensato di impiegare il piu recente SRI LM Toolkit (SRILM).

Per prima cosa, come detto, viene costruito il vocabolario a partire dal

file di corpus. Per fare cio si procede con l’istruzione

./bin/ngram-count -text corpus.txt

-write-vocab vocab1.txt

In questo modo nel file vocab1.txt viene creata una lista senza ripetizione

di tutte le parole contenute nel corpus. Tale vocabolario viene controllato ma-

nualmente al fine di togliere gli eventuali refusi non eliminati in automatico dal

tool per la costruzione del corpus.

Il modello che desideriamo ottenere deve essere

Closed Dictionary: in modo tale che eventuali termini fuori dal dizionario,

che abbiamo controllato manualmente, non vengano taggati come scono-

sciuti (<unk> ma vengano semplicemente ignorati in ogn N-Gramma;

Con piu di un N-Gramma: Nel nostro caso abbiamo utilizzato un modello

a 4-Grammi

Con Smoothing: (Kneser-Ney) affinche tutte le parole all’interno del vocabo-

lario abbiano una probabilita maggiore di 0 di comparire e perche il valore

di probabilita venga “normalizzato”. Cio e necessario soprattutto in lingue

flesse come l’Italiano, dove la distribuzione e particolarmente sparsa;

Con Back-Off: Non siamo interessati ad una interpolazione in quanto voglia-

mo che i 4-Grammi, ove presenti, mantengano le loro probabilita originali

(opportunamente aggiustate mediante smoothing). Indispensabile e invece


il Back-Off in modo tale che, nell’assenza di un 4-Gramma sia possibile

“retrocedere” al trigramma relativo e cosı via.

Dopo aver compiuto questa analisi ci basta ricercare, all’interno delle

pagine del manuale di SRILM, i parametri necessari all’applicazione delle opzioni

da noi desiderate. Per la costruzione del modello del linguaggio utilizzeremo

quindi la stringa:

./bin/ngram-count -text corpus.txt

-order 4 -vocab vocab1.txt -lm language.arpa -kndiscount

Al termine del processo otterremo un file language.arpa contenente il

nostro modello del linguaggio in un formato lineare. Tale formato contiene prima

tutti gli 1-grammi, poi tutti i 2-grammi, poi tutti i 3-grammi ed infine tutti i

4-grammi con le relative probabilita. Come vedremo fra un momento questo

formato e utile per la generazione del modello ma risulta difficile e poco efficace

da utilizzare senza essere processato. Per maggiori dettagli su ARPA si invita a

consultare [Pro].

5.2.3 Dal modello del linguaggio in formato ARPA alla struttura dati per

la predizione

Per la costruzione del motore di predizione potremmo impiegare diretta-

mente il file ARPA generato dal tool.

Il problema sorge quando si ha a che fare con un modello piuttosto grande (come

il nostro). In questo caso la ricerca all’interno di un file di testo piu grande di

100MB puo risultare lenta. Gli accessi che dovremmo fare sono davvero molti.

E quindi necessario pensare ad una struttura in grado di ospitare il

modello del linguaggio e di restituirne i dati in maniera semplice e veloce.


I primi tentativi che abbiamo svolto sono stati di inserire l’intero modello

del linguaggio in memoria. In tal modo pero l’applicativo finale risultava molto

pesante.

Se pensiamo che il file ARPA pesa oltre 150MB, memorizzare i dati all’interno

di strutture quali array e tabelle di Hash richiede molto piu spazio.

L’applicativo di test che avevamo implementato occupava oltre 600MB di RAM,

decisamente troppo.

Per questo si e deciso di ricorrere ad un’altra tecnica: quella dei database

su file. Si e utilizzato SQLite cercando di ottimizzare al massimo sia la struttura

(mediante indici) sia le query che vengono lanciate dal sistema di predizione.

Le relazioni contenute all’interno del database, supponendo di avere un

modello a 4-Grammi sono le seguenti:

• vocab(rowId,word) – Rappresenta il vocabolario e contiene l’elenco

delle parole;

• ng1(rowId,w1,p,b) – Contiene le sequenze di unigrammi con le loro

probabilita;

• ng2(rowId,w1,w2,p,b) – Contiene le sequenze di bigrammi con le loro

probabilita;

• ng3(rowId,w1,w2,w3,p,b) – Contiene le sequenze di 3-grammi con le

loro probabilita;

• ng4(rowId,w1,w2,w3,w4,p,b) – Contiene le sequenze di 4-grammi

con le loro probabilita,

In cui w1,w2,w3,w4 rappresentano i rowId delle varie parole, p rappre-

senta la probabilita della sequenza (dell’n-Gramma) mentre b rappresenta

una probabilita aggiuntiva utile per il calcolo del back-off.


rowId e un campo inserito in automatico da SQLite per garantire comunque la

presenza di una chiave univoca per riga. Il rowid della tabella vocab viene

impiegato come identificatore univoco di una parola per evitare di riscriverla

all’interno delle tabelle ng#. In questo modo gli N-grammi sono composti da

una sequenza di interi, i rowId corrispondenti alle parole nella tabella vocab.

Cio consente un notevole risparmio di spazio.

Il progetto dedicato alla conversione del file ARPA in questa struttura,

alla costruzione e all’inserimento dei dati nel database file e scritto in Visual C#

ed e chiamato Sqlitegen.

Tale software non e dipendente dal modello del linguaggio utilizzato e puo essere

impiegato senza nessuna difficolta anche per il processamento di modelli di classe

diversa da quello a 4-grammi attualmente testato.

Il programma si occupa anche della costruzione degli indici (indexes)

utili per garantire maggiori performance nel database su file. Il sistema viene

implementato in SQLite3 tramite alberi binari di ricerca.

Anzitutto va detto che la ricerca mediante rowId e molto veloce proprio perche,

di default, viene creato un indice su questo campo. Inoltre sono creati in modo

automatico indici anche per le chiavi primarie.

Seppur non siamo ancora entrati nel dettaglio dell’algoritmo di predizione, e facile

intuire che la chiave di ricerca utilizzata di frequente sara la sequenza di n − 1

termini del contesto (nel caso delle tabelle ng#). Tale sequenza costituisce un

indice per queste tabelle. Nel caso invece della tabella del vocabolario verra

creato un indice per le parole (word) in modo da poter risalire a partire da una

parola, in maniera molto rapida al suo indice. Come detto il vice-versa e gia

implementato in automatico da SQLite.


5.3 Sviluppo dei motori di predizione

Tutti i motori di predizione al momento compatibili con il PredictEdit

sono contenuti all’interno del progetto Predictors (sempre nella soluzione Pre-

dictEdit). Tale progetto viene incluso in quello del PredictEdit sottoforma di

libreria (DLL).

I motori di predizione devono implementare l’interfaccia IPredictor che garantisce

uniformita di metodi e di comportamento.

5.3.1 L’interfaccia IPredictor

L’interfaccia IPredictor contiene soltanto un metodo ed una Proprieta

(Property). La proprieta e PredictionSize e stabilisce la dimensione della

lista parole che il predittore dovra generare.

Il metodo predict, unico metodo presente, prende in input una stringa che

contiene il contesto e la radice. In output restituisce un vettore di stringhe. Il

vettore contiene la lista parole ed ha dimensione PredictionSize.

Come si vede la struttura e molto semplice e rispecchia i compiti, visti

come black-box, che il predittore svolge. Si e preferito fare uso di tipi primitivi

in quanto richiedono un minor dispendio di memoria per la loro allocazione.

5.3.2 Lo sviluppo del predittore locale NGPredictor

Il motore di predizione interamente implementato da noi si chiama NG-

Predictor.

Tale predittore fa uso del modello del linguaggio descritto nel paragrafo 5.2.

NGPredictor implementa l’interfaccia IPredictor e dunque il metodo principale

esposto e predict. In fase di inizializzazione, e necessario specificare al costrut-

77 Sviluppo dei motori di predizione

tore il percorso in cui e memorizzato il file SQLite contenente il database del

modello del linguaggio.

Procediamo ora per passi nell’illustrare come l’NGPredictor lavori.

Inizialmente siamo partiti da un algoritmo piuttosto semplice:

1. Si spezza la stringa in ingresso in base agli spazi. Le prime n − 1 parole

sono il contesto, l’ultima parte e la radice;

2. Si applica un filtro al contesto simile a quello impiegato per il processa-

mento del corpus, sono aggiunti i simboli di inizio frase, eventualmente il

vettore contenente il contesto viene ingrandito (ad esempio se esso contene-

va qualche carattere di punteggiatura che diventera una parola a se stante),

vengono applicate le stesse modifiche gia fatte nel corpus;

3. Si procede interrogando il database richiedendo quali siano i successori delle

ultime tre parole del contesto che iniziano con la radice;

4. Se non ve ne sono si calcola il back-off a partire dal contesto e si interroga la

tabella contenente la classe inferiore di N-grammi. Tutti i termini estratti da

questa tabella avranno la probabilita modificata (viene aggiunto il back-off).

5. Si ordinano i primi k elementi (dove k e PredictionSize) in base alle loro

probabilita e si restituiscono.

L’algoritmo cosı creato ha a nostro avviso due lacune:

• Anzitutto non viene considerato il caso in cui il numero di termini proposti,

dato un contesto, sia inferiore a PredictionSize.

• In secondo luogo ad ogni lettera immessa dall’utente viene lanciata una

nuova query.


Il secondo problema, in particolare, porta a dei ritardi nella predizione in

quanto sono necessari molteplici (ed in parte inutili) accessi al disco.

Per risolvere questi problemi si e deciso di modificare l’algoritmo precedente.

Per capire meglio i cambiamenti apportati, prima di descrivere i passi

preferiamo riprendere l’esempio 3.1. In tal modo risultera piu semplice compren-

dere le migliorie. L’utente la prima volta passera all’algoritmo “La minestra e

nel p”.

L’algoritmo osserva il contesto, “minestra e nel” e la radice “p” (4 parole perche

usiamo i 4-grammi). Procede quindi ricercando all’interno del database tutti i

possibili risultati. Supponiamo che la PredictionSize sia impostata a 10 ma che

vi siano solo 8 quadrigrammi di sequenze “minestra, e, nel,start(p)”.

In questo caso il sistema osserva che il numero di termini che si vogliono restituire

e inferiore alla PredictionSize e che e possibile ancora fare back-off (non siamo

ancora arrivati agli unigrammi).

Se fossimo arrivati agli unigrammi si arrenderebbe e restituirebbe una lista infe-

riore alla PredictionSize.

Si puo ancora tornare indietro e si procede al back-off. Considerando semplice-

mente “e, nel, start(p)” (trigrammi) abbiamo 22 risultati.

Inseriamo anche questi ultimi nella lista precedente ottenendo cosı un insieme di

30 risultati, molto maggiore di quanto richiesto dalla PredictionSize.

Ordiniamo quindi la lista in base alle probabilita (ricalcolando quelle dei termini

che hanno subito il processo di back-off). Restituiamo quindi i primi 10 elementi

della lista.

L’utente non trova il termine desiderato (“piatto”) in lista e procede

scrivendo una nuova lettera (la “i”). L’algoritmo riceve di nuovo tutta la stringa:

“La minestra e nel pi”.

Questa volta pero osserviamo che il contesto e rimasto invariato e che la radice


inizia con la radice precedente. Possiamo quindi gia produrre la lista dei termini

provenienti dai quadrigrammi e dai trigrammi che inizia con “pi”, dato il contesto,

senza la necessita di interrogare il database.

Infatti se prima abbiamo richiesto ed ordinato tutti i termini dei quadri-

grammi e dei trigrammi che iniziano con “p” dato il contesto, quello che possiamo

ottenere richiedendo tutti i termini che iniziano con “pi” e un sottoinsieme del

risultato della query precedente.

Supponiamo ora che la lista cosı filtrata abbia ancora solo 8 risultati.

Quello che facciamo e retrocedere direttamente ai bigrammi. La probabilita di

back-off va sommata alla precedente (che ci ha fatto passare dai 4-grammi ai

3-grammi). Produciamo quindi la nuova lista e aggiorniamo le probabilita. Il

procedimento continua fino a quando il contesto non e piu uguale al precedente

o la radice salvata non e piu una sottostringa della nuova radice.

In questi casi la predizione ricomincia e tutti i dati salvati vengono azzerati.

Nell’istanza della classe NGPredictor sono quindi contenute, fra le altre,

le variabili private:

string[] ctx – che contiene il vecchio contesto;

string start – che contiene la vecchia radice;

ushort toExplore – che contiene la classe di N-Grammi da visitare;

double backoff – che contiene l’attuale back-off eventualmente da sommare

alla probabilita originale dei termini;

List<Ngram> predicted – che contiene la lista completa dei (nell’esempio i

30) termini predetti.

Riprendiamo quindi i passaggi dell’algoritmo precedente. I passi 1 e 2

restano invariati.


3. Si controlla se il contesto corrente corrisponde al contesto memorizzato e

se l’ultima radice inizia con la radice memorizzata. Se questo non e vero si

seguono i passaggi in 4 e poi in 6, altrimenti si seguono quelli in 5 e poi in

6;

4. (a) Vengono reinizializzate tutte le variabili sopra descritte;

(b) Viene effettuata una prima ricerca all’interno del database sulle se-

quenze di 4-grammi come nell’algoritmo precedente.

(c) Se il numero dei risultati e inferiore a PredictionSize viene calcolato

il back-off ed aggiornata la relativa variabile d’istanza. Si continua in

questo modo fino a che si raggiunge (o si supera) la PredictionSize o

fino a che non si arriva alla classe 1;

(d) Si ordina la lista dei termini in base alle relative probabilita.

5. (a) Si filtra la lista predicted in base al nuovo prefisso.

(b) Se la lista e di dimensioni minori di PredictionSize, se toExplore e

maggiore di 1, e quindi non si e ancora arrivati agli unigrammi, si pro-

cede alla ricerca sul database ed al back-off. I nuovi termini vengono

aggiunti alla lista e questa viene riordinata in base alle probabilita.

6. Vengono restituiti, al piu, i primi k elementi della lista, con k = PredictionSize.

Per i dettagli implementativi si rimanda al codice, e importante pero

evidenziare alcuni punti:

• Il filtraggio iniziale (al punto 2) viene svolto da un metodo statico della

classe Filter;

• Il tipo di dato Ngram e stato creato per maggior chiarezza, esso contiene una

stringa (l’ultimo termine dell’n-gramma) ed una probabilita (con il back-


off gia calcolato). Esso implementa anche l’interfaccia IComparable per

permettere il semplice riordino della lista predicted mediante il metodo

Sort()

• La query impiegata per la ricerca all’interno del database e dinamica (e varia

in funzione della classe utilizzata). Ad esempio per ricercare all’interno dei

3-grammi essa e:

SELECT word,p FROM ng3 INNER JOIN vocab

ON ng3.w3 = vocab.rowid WHERE

w1 = (SELECT rowid FROM vocab WHERE word = @par{0}) AND

w2 = (SELECT rowid FROM vocab WHERE word = @par{1}) AND

word LIKE "@par{2}\%"

• Il motore di predizione NGPredictor funziona con qualunque modello creato

da Sqlitegen. Esso individua in automatico la massima classe degli n-

grammi disponibili nel database SQLite. Cio potra essere impiegato per

futuri sviluppi o test con modelli di classi diverse.

All’interno di questo testo, come nella descrizione generica dell’algoritmo,

si e sempre supposto di lavorare con un modello a 4-grammi.

5.3.3 Lo sviluppo del client per Google Scribe (GSPredictor)

Per poter offrire agli utenti un motore di predizione alternativo e con-

frontabile nei test manuali e per poter svolgere le diverse valutazioni automati-

che, avevamo proceduto a costruire un client Google Scribe che implementasse

l’interfaccia IPredictor.

Si e descritto GoogleScribe all’interno del paragrafo 3.5.7.


Purtroppo, come abbiamo detto, questo prodotto non e stato piu disponibile.

Lo abbiamo impiegato, in parte, durante le valutazioni manuali per mostrare un

altro esempio di motore di predizione agli utenti volontari. Non e invece stato

possibile svolgere alcuna valutazione automatica poiche il servizio e stato chiuso

prima che queste venissero svolte.

Il GSPredictor svolgeva la predizione mediante alcune chiamate JSON

per ottenere la predizione dai server di Google. Tali comandi, disponibili in ma-

niera non ufficiale su internet, erano stati estrapolati da alcuni utenti osservando

il traffico HTTP in uscita dal computer durante l’utilizzo del client AJAX nel

servizio originale. Il risultato, in termini di predizione, era davvero notevole.

Mediante diversi parametri era possibile impostare la lingua in cui si desiderava

che fosse svolta la predizione e definire la tipologia di caratteri (nel caso di lingue

orientali) che si volevano impiegare.

Il client e molto semplice.

Dopo alcune prove abbiamo osservato che il server accettava che venissero passati

come testo, all’interno della richiesta, non piu di 40 caratteri. Tuttavia questo

non costituiva un problema in quanto, come riportato in 1 la parola considerata

la piu lunga in lingua italiana e costituita da meno di 30 caratteri.

Non sapendo esattamente come fosse svolto il processo di predizione era impos-

sibile per noi effettuare un servizio di cache lato client. Ad ogni lettera digitata

dall’utente, quindi, veniva inviata una nuova richiesta al server.

Per migliorare i risultati era stata in ogni caso studiata una funzione di

preprocessamento del testo che in seguito veniva inviato al server.

Si procedeva, innanzitutto, considerando soltanto gli ultimi 40 caratteri del con-

testo. Si ricercava, quindi, il primo carattere di spazio (per evitare di passare al

1Vocabolario Treccani http://www.treccani.it/vocabolario/precipitevolissimevolmente/

http://www.treccani.it/vocabolario/precipitevolissimevolmente/

http://www.treccani.it/vocabolario/precipitevolissimevolmente/

83 Sviluppo dell’editor PredictEdit

server finali di qualche parola). Veniva quindi inviata nella richiesta la sottostrin-

ga che iniziava dal primo spazio (se presente) del contesto e terminava alla fine

della radice.

I dati erano trasmessi in maniera cifrata al server utilizzando il protocollo HTTPS.

Il servizio restituiva i risultati all’interno di un vettore in una risposta

JSON. Tale vettore, data la sua struttura semplice, veniva processato senza l’uso

di particolari librerie. Erano quindi restituiti solo i primi k risultati, con k la

dimensione di PredictionSize. Se PredictionSize era maggiore di 20, venivano

restituiti comunque soltanto 20 risultati (il massimo che il web service, a quanto

sappiamo, fosse in grado di offrire).

5.4 Sviluppo dell’editor PredictEdit

Nei prossimi paragrafi ci occuperemo del PredictEdit, un editor per l’am-

biente Microsoft Windows. Successivamente discuteremo del PredictiOnDemand.

Entrambi costituiscono la seconda parte del nostro progetto: l’interfaccia utente.

Se fino ad ora abbiamo discusso della costruzione di un motore per la previsione

delle parole, esso e difficilmente testabile da utenti con una conoscenza di base

dell’informatica, a meno che non venga costruita un’interfaccia grafica che ne

renda semplice l’impiego. E stato quindi implementato un editor, il PredictEditor

che contenesse anche una funzionalita di previsione delle parole. Nel paragrafo 5.5

ci occuperemo invece del PredictiOnDemand, un servizio innovativo che porta la

previsione delle parole al di fuori di una singola applicazione standalone. I servizi

di predizione sono offerti mediante i predittori che implementano l’interfaccia

IPredictor.

Il risultato e stato cosı soddisfacente dal portarci a definire la soluzione come un

sistema di scrittura semplificata. Esso e necessariamente composto di due moduli


complementari fra loro: senza un’interfaccia utente sarebbe stato impossibile

utilizzare in modo opportuno i motori di predizione, ma senza motori di predizione

l’editor sarebbe risultato inutile.

Il PredictEdit e un’applicazione Windows sviluppata utilizzando il .NET

Framework mediante il linguaggio di programmazione Visuali C#, e contenuto

all’interno della soluzione PredictEdit. Esso appare all’utente come una finestra a

tutto schermo. Tale finestra, visibile in figura 5.1, e composta principalmente da

due parti: in alto possiamo trovare la barra dei menu, mentre lo spazio restante

e occupato da una RichTextBox multilinea utilizzata dall’utente per inserire il

testo.

Oltre alla finestra principale ne troviamo una seconda, di dimensioni piu

piccole, che resta sempre in primo piano quando il programma e attivo e che e

spostabile a piacere dall’utente sullo schermo.

Questo secondo form, il “Word List”, contiene l’elenco delle parole che il pre-

dittore propone. Esso viene aggiornato ogni volta che il testo, all’interno della

finestra principale, viene modificato.

Come si puo vedere anche dalla figura, abbiamo sviluppato il software

in modo da consentire all’utente di completare le parole non solo quando queste

vengono inserite al termine del testo corrente ma anche quando il cursore viene

posizionato nel mezzo del testo.

Questa e una funzionalita molto importante poiche non e detto che un utente vo-

glia sempre aggiungere parole a fine testo. Per essere implementata essa richiede,

oltre all’analisi del contesto (i termini precedenti alla radice), anche il traccia-

mento in tempo reale della posizione del cursore. Data la posizione del cursore,

si prendera in considerazione il testo che lo precede, ignorando il successivo. Tale

porzione di testo sara poi passata al motore di predizione che fornira la lista dei

termini che popolano la Word List.


Figura 5.1: Finestra del PredictEdit in cui si vede l’immissione della parola “stru-mento” inserita fra altre due parole. L’utente sta procedendo cliccando sopra allaparola desiderata all’interno della lista. Si vedono inoltre i font personalizzati siadella finestra dell’editor che della Word List.

Il form “Word List” e costituito da dieci campi editazione, ognuno dei

quali contiene uno dei termini suggeriti e da 10 pulsanti numerati, da 1 a 10, uno

per ciascun termine.

L’utente, durante la digitazione, puo immettere uno dei termini suggeriti sempli-

cemente cliccandoci sopra o premendo il pulsante relativo con il mouse.

E anche possibile utilizzare le combinazioni di tasti in due modi:

• Il modo tradizionale di Windows, portandosi sulla finestra dell’elenco ter-

mini (Word List) mediante la combinazione tasti CTRL+TAB quiindi spo-


standosi con TAB fino ad arrivare al pulsante corrispondente al termine

desiderato ed, infine, premendo INVIO;

• mediante le combinazioni tasti CTRL+ i numeri dall’1 allo 0 che inseriscono,

rispettivamente, i termini dall’1 al 10.

Inoltre e previsto un meccanismo di immissione mediante il tastierino numerico.

e sufficiente premere uno dei numeri dall’1 allo 0 del tastierino per immettere i

vocaboli dall’1 al 10 (lo 0 immette il decimo termine).

Si e lavorato molto per ridurre al minimo il numero di tasti o di operazioni

richieste all’utente. Una volta selezionato un termine mediante il mouse, la fine-

stra principale acquisisce il focus in modo automatico. All’utente non e richiesto

di premere alcun tasto virtuale o fisico per ritornare con il punto di inserimento

all’interno della finestra dell’editor.

Le ultime due modalita di immissione, che non richiedono di richiamare espli-

citamente la finestra “Word List”, poiche fanno uso di combinazioni tasti, non

necessitano nemmeno che questa abbia il focus (non e necessaria la pressione dei

tasti CTRL+TAB o il click del mouse). L’utente semplicemente osserva che all’in-

terno della Word List e presente il termine desiderato, legge il numero relativo e

preme l’opportuno pulsante.

Tale molteplicita di sistemi di immissione e stata sviluppata in modo da

venire incontro alle esigenze di utenti con difficolta molto diverse fra loro.

L’inserimento mediante puntatore e stato pensato per persone affetti da disturbi

di apprendimento che non hanno alcun problema nell’impiego di un mouse. Le

combinazioni tasti con il CTRL sono state pensate per utenti con escursione ri-

dottache fanno uso, appunto, di tastiere ridotte. Il sistema a tastierino numerico,

invece, e indicato per persone con mobilita ridotta ma con una buona escursione

che fanno uso di tastiere standard o con scudo.


Anche gli utenti che riescono ad utilizzare il computer mediante tastiere a

schermo con joystick, touchscreen, trackball o sistemi di puntamento alternativi,

troveranno molto utile la funzione di click allargata. In particolare, la possibilita

di cliccare, oltre che sul pulsante numerato, anche sul testo della parola che si

vuole inserire, rende piu facile ed agevole il l’immissione delle parole presenti

in WordList anche quando si utilizza una dimensione dei caratteri non troppo

grande.

Figura 5.2: Utilizzo del PredictEdit con la tastiera a schermo di Windows me-diante uno schermo a tocco. Si possono immettere le singole lettere mediante latastiera a schermo e completarle tramite la finestra di Word List.

Come e possibile vedere in figura 5.2, l’impiego di tastiere virtuali abbinate al soft-

ware non presenta alcun problema particolare. Il sistema non e invece predisposto

per l’utilizzo di strumenti di selezione a scansione.

Alcune funzionalita sono poi state aggiunte in modo da rendere piu age-

vole l’impiego del PredictEdit.


E possibile scegliere il motore di predizione (fra quelli implementanti l’interfaccia

IPredictor) mediante l’apposita funzione di menu. Questo ci ha consenti-

to, durante la valutazione dell’interfaccia utente, di lasciare alle persone la scel-

ta se utilizzare l’NGPredictor o il predittore di Google Scribe (ora non piu

funzionante).

I font, come detto sono completamente personalizzabili e la finestra di

predizione riadatta le proprie dimensioni nel caso il carattere sia troppo grande

e le parole vengano tagliate. E possibile inoltre, sempre tramite il menu, per-

sonalizzare il colore del testo e dello sfondo nella finestra di predizione. Questo

permette di lavorare in maniera piu confortevole anche a persone con particolari

disturbi visivi.

Un’ulteriore caratteristica della word list e la sua capacita di spostarsi

automaticamente nel momento in cui il cursore si trova sotto ad essa e per l’utente

sarebbe impossibile visualizzare il testo immesso. Anche tale funzione e studiata

per venire incontro alle difficolta degli utenti ai quali il software si rivolge.

Spesso, infatti, puo risultare difficile l’impiego del mouse per spostare una finestra.

E molto piu comodo che essa si muova in modo automatico quando e chiaro che

la sua presenza in un punto crea un qualche problema.

Un’ultima caratteristica che desideriamo evidenziare e la flessibilita della

finestra di predizione. Anche se al momento non e data all’utente alcuna pos-

sibilita di modifica del numero di voci in essa contenute, questa funzionalita e

molto facile da implementare poiche il design dell’interfaccia viene svolto in modo

automatico e parametrico. Tutte le textBox ed i relativi pulsanti sono inseriti

in un pannello a tabella (TableLayoutPane). In questo modo e molto facile

modificarne il numero, e sufficiente impostare il parametro desiderato.

89 Il PredictiOnDemand

5.5 Il PredictiOnDemand

Il PredictEdit e sicuramente un software destinato ad evolvere e a miglio-

rare offrendo agli utenti molte nuove funzioni, adatte alle specifiche necessita, che

potranno aumentare nel tempo.

L’esigenza di molte persone pero e diversa. Non occorre un servizio inglobato

in una applicazione a se stante ma un servizio disponibile in situazioni diverse

ed in programmi diversi. Per offrire la potenzialita della predizione nelle tante

applicazioni di Windows e stato studiato ed implementato il PredictiOnDemand.

Il PredictiOnDemand consente agli utenti di avere lo stesso servizio di

predizione gia disponibile all’interno del PredictEdit in moltissime applicazioni

Windows. Gia ora sono supportate parzialmente o totalmente alcuni fra i piu noti

programmi Windows come Microsoft Word, WordPad, Blocco Note e Firefox.

Il PredictiOnDemand e rivoluzionario perche non assilla l’utente con fine-

stre di predizione che compaiono e scompaiono di continuo. Esso si attiva, come

dice il nome, soltanto quando l’utente lo desidera.

Il PredictiOnDemand supporta sia la costruzione di moduli specifici, svi-

luppati per consentire l’utilizzo in maniera ottimale di una singola applicazione,

sia di adeguarsi al controllo focalizzato al momento, mediante le API standard

dell’accessibilita UIAutomation [Mica].

Al momento, l’unico modulo specifico disponibile e stato sviluppato per Microsoft

Word, il piu utilizzato elaboratore di testi in ambiente Windows.

Questa innovazione consente di arricchire l’esperienza d’uso di chi desi-

dera la predizione con gli altri importanti servizi gia presenti in editor di testi

molto evoluti. Ad esempio e possibile impiegare il predittore all’interno di Mi-

crosoft Word, che contiene uno straordinario strumento per la segnalazione e la

correzione degli errori ortografici e grammaticali.


Il PredictiOnDemand e sviluppato utilizzando il framework Microsoft.NET

e chiamate dirette alle API di Windows (Win32 API). La scelta non e stata

casuale. Grazie a questa e infatti possibile impiegare l’innovativa libreria UIAu-

tomation in combinazione con la tecnica dei System hooks [Micc].

Tutto cio consente di intercettare controlli, eventi e processi estranei alla nostra

applicazione. Per presentare in modo ordinato le varie funzionalita abbiamo de-

ciso di dividere questo paragrafo in diverse parti: nella prima discuteremo del

funzionamento generale del PredictiOnDemand, nella seconda discuteremo della

struttura a moduli e del modulo per Microsoft Word. In seguito mostreremo

come abbiamo impiegato gli elementi standard di UIAutomation per garantire

la compatibilita con molte applicazioni Windows. Infine illustreremo il funzio-

namento e la gestione della finestra mobile di predizione, le varie modalita di

immissione dei termini ed alcune peculiarita dell’applicativo.

Prima di procedere spieghiamo brevemente che cosa sono gli hook, gli

AutomationEvents e gli AutomationElements. Per i dettagli si rimanda alla

bibliografia.

5.5.1 Terminologia

Gli events hook (o piu semplicemente hook) sono registrati ed ottenuti me-

diante chiamate di sistema svolte tramite API di Windows (Win32API).

Essi consentono di intercettare diversi eventi anche ad applicazioni che non

si trovano attualmente focalizzate (in primo piano).

In particolare e possibile intercettare la pressione o il rilascio di un pulsan-

te della tastiera o del mouse. Gli hook possono quindi consentire ad un

processo, non in primo piano, di intercettare una determinata sequenza di

tasti, il fatto che in generale un tasto sia stato premuto o che venga rila-

sciato. Gli Hook funzionano a catena. Quando un hook e terminato puo


decidere di passare (o meno) l’evento che ha intercettato all’Hook succes-

sivo. A meno che non abbia impostato anch’essa un hook, la finestra in

primo piano rappresenta l’ultimo anello della catena.

E quindi possibile “consumare” un evento in modo tale che non arrivi mai

all’applicazione in primo piano. Questo e molto utile qualora si desideri che

una applicazione in background reagisca ad una combinazione tasti senza

tuttavia che l’applicazione in foreground si accorga di nulla. Per aumentare

le performance spesso una applicazione impiega un unico hook per com-

piti molto diversi fra loro. Questo e anche il caso del PredictiOnDemand.

Quando ci riferiremo ad “un hook”, intenderemo sempre lo stesso e non

molti hook diversi.

La libreria UIAutomation disponibile all’interno del .NET Framework a partire

dalla versione 3.0, mette a disposizione un insieme di oggetti e di metodi per inter-

cettare ed interagire con il contenuto dello schermo. I due oggetti piu importanti

che saranno nominati all’interno di questo testo sono:

Gli AutomationEvent , simili agli eventi che normalmente le applicazioni si

trovano ad intercettare. L’importante differenza sta nel fatto che non ri-

guardano comportamenti che avvengono all’interno dell’applicazione ma,

invece, comportamenti che avvengono all’esterno. E possibile, ad esempio,

intercettare l’evento AutomationFocusChangedEvent che viene richiamato

ogni qualvolta il focus (il cursore di sistema, non il mouse) si sposta o

cambia controllo selezionato.

Gli AutomationElements: rappresentano qualunque controllo di Windows.

Essi sono organizzati ad albero. Per capirli in breve facciamo l’esempio

seguente: supponiamo di aver avviato Windows e di avere in esecuzione

soltanto una applicazione con una finestra che contiene un pulsante. Il


RootElement (che e un AutomationElement) e sempre il desktop. I suoi

figli sono le applicazioni aperte, nel nostro caso quindi, solo la nostra ap-

plicazione. L’applicazione viene identificata come finestra (Window). La

Window avra tre figli: un AutomationElement che e la barra del titolo, un

secondo AutomationElement che e il pulsante ed infine la barra di stato. In

base all’elemento utilizzato e possibile ottenere un insieme di informazio-

ni comuni a tutti gli elementi oppure, per svolgere delle azioni e possibile

ottenere uno o piu AutomationPattern. In base alla tipologia del controllo

esso potra implementare o meno i vari Pattern disponibili.

5.5.2 PredictiOnDemand, la predizione su richiesta

Il PredictiOnDemand non e una applicazione dotata di una finestra prin-

cipale. Essa risiede, come molti altri servizi, nella barra di notifiche di Windows.

Per attivarla all’interno di un programma e sufficiente fare click due volte sull’i-

cona oppure premere due volte il tasto Control sulla tastiera. Questa seconda

modalita, rivolta in particolar modo ad utenti con difficolta nell’utilizzo del mou-

se, e stata implementata grazie all’hook presente sull’input tastiera. Non vi sono

intervalli di tempo entro cui premere le due volte il tasto Control, tuttavia se

viene premuto un qualunque altro pulsante (anche del mouse sara necessario

ripetere l’operazione.

Il PredictiOnDemand monitora in tempo reale le varie applicazioni ed i

vari controlli che, volta per volta, acquisiscono il focus. Quando viene inviato

l’evento AutomationFocusChangedEvent, il software controlla se sia presente un

modulo (AppModule) compatibile con l’applicazione in primo piano (si veda il

paragrafo 5.5.3). Se questo non e presente, esso prova ad intercettare il controllo

per analizzare se e un controllo di testo standard (si veda il paragrafo 5.5.4). Se

una di queste condizioni e verificata, nel caso in cui l’utente prema due volte


control comparira la finestra di elenco parole, altrimenti comparira un mes-

saggio che informa l’utente della impossibilita di svolgere la predizione.

Al successivo AutomationFocusChangedEvent, se la finestra di predizione e aper-

ta, essa viene chiusa ed il processo riprende.

5.5.3 Gli appModule ed il modulo per Microsoft Word

Talune applicazioni non fanno uso di controlli standard di Windows op-

pure i campi di testo non sono immediatamente focalizzati ma vi sono elementi

“proprietari” intermedi. In altri casi si vuole migliorare l’accesso di base ai com-

ponenti testuali o personalizzare le modalita con cui i dati vengono letti o scritti

all’interno dell’applicazione. Per questo e stata sviluppata una struttura a mo-

duli (contenuta all’interno del namespace PredictiOnDemand.appModules.

Ogni modulo corrisponde ad un processo, il modulo si occupa di garantire la

qualita dei dati letti e scritti all’interno del processo stesso.

Per uniformare i moduli e poterli istanziare dinamicamente quando servnono e

stata sviluppata l’interfaccia IAppModule contenente tre metodi e due proprieta

di sola lettura.

• Il metodo string read() e utilizzato dal PredictiOnDemand per leggere

il testo proveniente dall’applicazione. Il metodo read deve riportare il testo

solo fino alla posizione del cursore;

• il metodo void write(string) e utilizzato dall’applicativo principale

per scrivere nel controllo specifico. Il metodo write deve aggiungere il

testo non a fine stringa ma a partire dalla posizione del cursore;

• Il metodo bool setFocusedControl(AutomationElement e) ser-

ve nel caso in cui l’applicazione contenga diversi componenti per stabi-

lire all’interno di quali sia possibile o meno svolgere la predizione. Ad


esempio, in Microsoft Word, questo metodo restituisce true solo se ci si

trova effettivamente all’interno del documento e non in altre finestre del

programma;

• La proprieta SupportedVersion che serve a stabilire quale sia la ver-

sione del processo supportata dall’appModule.

• Infine e presente SupportedGreater che serve a stabilire se le versioni

successive alla SupportedVersion sono supportate oppure no.

Gli appModule, per convenzione, devono rispettare le seguenti tre carat-

teristiche:

• La classe deve essere chiamata AppModule;

• Il namespace deve essere PredictiOnDemand.appModule.nomeprocesso

con nomeprocesso il nome del processo per il quale si sta sviluppando il

modulo (ad esempio winword);

• Devono implementare l’interfaccia IAppModule

I moduli cosı costruiti vengono autocaricati dall’applicativo senza biso-

gno di altri interventi nel codice. Essi possono anche essere aggiunti come refe-

renza esterna (Assembly .NET Dll) purche questa sia inclusa al momento della

compilazione del progetto.

Il modulo per Microsoft Word e stato costruito utilizzando l’interfaccia

di comunicazione COM (Component Object Model) disponibile all’interno del-

le Microsoft Word Automation API [Micb]. Dopo alcuni test abbiamo stabilito

che la versione minima di winword supportata sia la 11.0 (Microsoft Office Word

2003). La lettura e la scrittura avvengono, come nel caso del PredictEdit ag-

ganciando il punto di inserimento. E quindi possibile immettere testo non solo


al termine del documento ma anche nel mezzo. Per maggior comodita vengono

tenuti in considerazione soltanto gli ultimi 150 caratteri antecedenti alla posizio-

ne del cursore. Questo perche, molto spesso, un documento di Word e composto

da diverse pagine. Risulterebbe del tutto inutile, quindi, appesantire l’applicati-

vo “passando” come contesto svariate pagine di documento. I caratteri speciali

(come i fine righe, fine paragrafi, fine pagina) vengono eliminati direttamente

dall’appModule. La scrittura e svolta simulando la pressione dei tasti (grazie alla

funzione SendKeys) e non tramite le API di Office. Questo al fine di rendere

il piu stabile possibile il modulo: ci possono essere problemi nelle comunicazioni

con COM che quindi abbiamo impiegato solo dove strettamente necessario.

5.5.4 UIAutomation per i controlli standard di Windows

Molti applicativi che fanno uso del .NET framework, applicazioni di sem-

plice struttura oppure software di nuova concezione utilizzano o estendono con-

trolli standard di Windows. Questo consente un immediato accesso di base anche

in assenza di moduli specifici. Cio puo essere svolto grazie alle API per l’accessi-

bilita e l’automazione UIAutomation ed in particolare grazie alle componenti che

implementano il TextPattern 2.

Il PredictiOnDemand e in grado di individuare in tempo reale, come

detto, i controlli su cui si posiziona il cursore. Nel caso non esista alcun mo-

dulo specifico per il processo in foreground, viene avviato uno speciale modulo

chiamato UIAModule.

Qualora sia disponibile un componente che supporta il TextPattern,

per l’utente non vi sono particolari problemi. La predizione avviene come all’in-

terno del PredictEdit, o come nel modulo per Microsoft Word. Viene individuata

2TextPattern – http://msdn.microsoft.com/en-us/library/system.windows.automation.textpattern.aspx

http://msdn.microsoft.com/en-us/library/system.windows.automation.textpattern.aspx

http://msdn.microsoft.com/en-us/library/system.windows.automation.textpattern.aspx


la posizione del cursore e la stringa passata all’applicativo e il testo antecedente

ad esso. E possibile quindi inserire il testo anche all’interno del documento o

dell’area di testo senza troppe difficolta.

Il problema e che non sono molti i controlli di testo che ad oggi supportino

il TextPattern. Moltissimi implementano soltanto il ValuePattern e quindi

non offrono l’informazione di dove si trovi effettivamente il punto di inserimento.

In questi casi non e possibile considerare il testo fino alla posizione del cursore.

Il problema si presenta quando il focus e contenuto in un controllo di un applica-

tivo per cui non e disponibile alcun appModule ed il componente non implementa

il TextPattern ma utilizzi soltanto il ValuePattern. In questo caso, qualora

l’utente richiami la funzionalita di predizione, il PredictiOnDemand si rifiuta di

mostrare direttamente la finestra di WordList, esso presenta invece un avviso per

informare che la previsione puo essere effettuata soltanto al termine dell’area di

testo e non all’interno. L’utente puo scegliere se procedere comunque o meno (Si

veda figura 5.4).

5.5.5 Come avviene la previsione e l’immissione

Nel momento in cui l’utente preme due volte control o fa doppio click

sull’icona nella barra di notifica, se l’applicativo e supportato (figura 5.3(a))

compare la finestra Word List, del tutto simile a quella del PredictEdit. Qua-

lora l’applicazione non sia supportata (figura 5.3 (b)) compare un messaggio a

schermo.

L’evento che “provoca” la previsione (e l’aggiornamento dei termini all’in-

terno della WordList) e creato internamente al PredictiOnDemand utilizzando gli

hook. Poiche non esiste, ne all’interno delle API di Microsoft Office Automation,

ne all’interno delle API del TextPattern un evento TextChanged (o simili) si e

pensato di implementarlo manualmente. Qualora l’utente si trovi con il focus al-


l’interno del controllo dove e possibile effettuare la predizione e qualora la finestra

WordList sia visibile a schermo, se l’hook rileva la pressione di un tasto alfabe-

tico (quindi una lettera) o un tasto simbolico (prevalentemente punteggiatura),

viene lanciato un evento interno.

Tale evento viene intercettato da un metodo che provvede a richiamare

read per l’appModule in uso. A questo punto il testo letto viene passato al

motore di predizione, i risultati vengono poi scritti nella WordList.

Si procede in questo modo fino a che l’utente non sceglie una voce all’interno

della WordList. Tale scelta puo essere compiuta in tre modi diversi per venire

incontro, come sempre, alle diverse esigenze degli utenti:

• Nel modo standard di Windows, focalizzandosi sull’applicazione WordList,

utilizzando la combinazione tasti ALT+Tab, quindi premendo TAB fino ad

arrivare al pulsante relativo alla scelta desiderata;

• Utilizzando il tastierino numerico dall’1 allo 0. Ogni numero corrisponde

ad uno dei termini (dall’uno al dieci rispettivamente);

• Utilizzando il puntatore del mouse e cliccando sopra al termine o al pulsante

numerato relativo al termine stesso.

Nel momento in cui si clicca con il mouse sopra alla parola, o si sceglie il

termine con il primo metodo, l’utente non dovra riportarsi nella finestra princi-

pale dell’applicativo in uso. Questo verra svolto dal PredictiOnDemand in modo

automatico, mediante chiamate di sistema.

Nel caso della scelta con il tastierino numerico non e necessario focalizzare

(selezionare, cliccare o spostarsi con ALT+TAB) la finestra WordList. I tasti del

tastierino sono gestiti mediante hook e, quando e attiva la finestra del predittore,

sono riservati al PredictiOnDemand.


Alcune particolarita sono state sviluppate per evitare possibili problemi

e migliorare l’esperienza d’uso:

• Se il cursore si trova in una meta dello schermo la finestra di predizione e

sempre nell’altra meta. In questo modo si evita che la finestra possa sovrap-

porsi al cursore stesso. Cio si e ottenuto mediante un insieme di chiamate

di sistema. L’eventuale spostamento avviene con la stessa chiamata che

l’hook utilizza per aggiornare l’elenco parole;

• La finestra della predizione e completamente personalizzabile nel colore

dello sfondo, del testo e nel tipo e dimensione dei caratteri. E possibile mo-

dificare queste impostazioni grazie al menu contestuale presente nell’icona

di notifica del PredictiOnDemand ;

• Nel momento in cui ci si sposta con il focus da un controllo ad un altro la

finestra di predizione si chiudera automaticamente per evitare problemi. E

possibile sempre richiamarla attraverso le modalita sopra descritte.

Nel prossimo capitolo presenteremo una valutazione del PredictEdit

dal punto di vista del motore di predizione (NGPredictor). Come detto non siamo

stati in grado di confrontare i risultati cosı ottenuti con Google Scribe poiche

questo servizio ha smesso di funzionare durante la stesura di questo lavoro.


(a)

(b)

Figura 5.3: (a) La predizione in Microsoft Word. Viene inserito il termine “defi-nire” all’interno del testo. Il tondino giallo rappresenta il click del mouse o dellostrumento di puntamento. I caratteri e i colori sono personalizzati. (b) Messaggiodi avviso quando si cerca di richiamare la predizione all’interno di Adobe Reader,il focus non si trova all’interno di un campo di testo.


(a)

(b)

Figura 5.4: (a) Il messaggio che avvisa l’utente di essere all’interno di un campoeditazione supportato soltanto quando il cursore si trova a fine stringa. (b) Lapredizione durante l’uso del servizio online “Google Translator”. L’utente staper inserire la parola “previsione” premendo il tasto 1 nel tastierino numerico ocliccando nell’area dove e presente il tondino giallo, il font e personalizzato.

CAPITOLO 6

Valutazione del PredictEdit

Nel capitolo precedente e stato introdotto il PredictEdit, uno strumento

in grado di facilitare la scrittura grazie ad un avanzato sistema di previsione delle

parole e di inserimento facilitato delle stesse. Esso funziona sia all’interno di

uno specifico elaboratore di testi, il PredictEdit appunto, sia all’interno di altre

applicazioni (PredictiOnDemand).

In questo capitolo presenteremo i test effettuati per valutare la qualita del lavoro

svolto. Essi sono stati eseguiti in modo manuale (grazie a due volontari che si sono

offerti di testare l’applicazione nel suo insieme), sia in modo automatico grazie

al tool AutoTest (presente insieme agli altri progetti all’interno della soluzione

PredictEdit).

Vogliamo pero iniziare questo capitolo presentando le misure che abbiamo

utilizzato.

Valutazione del PredictEdit 102

6.1 Misure impiegate

Come abbiamo avuto modo di discutere nel paragrafo 4.5 esistono varie

metriche per la valutazione di tecnologie basate sui modelli del linguaggio. Noi

abbiamo deciso di non valutare in modo intrinseco i modelli (utilizzando la misura

di Perplexity). Abbiamo preferito, invece, impiegare alcune metriche piu adatte

al problema che si voleva risolvere.

Ecco le misure da noi effettuate e l’uso e l’interpretazione che ne daremo:

• Reciprocal Rank . Consideriamo come rank il numero di tentativi (di

lettere) dopo i (le) quali all’interno della lista delle parole appare il lemma

desiderato. Il rank e una misura interessante che ci aiuta a comprendere

dopo quante lettere il predittore suggerisce la giusta parola. Tale modo

di valutare il rank e anche definito come Keystroke until Prediction

(KuP) measure. Il reciprocal rank e reciproco del rank ossia 1/rank. Il

Mean Reciprocal Rank e la media matematica del reciprocal rank per

le parole dell’intero documento di test. Non e possibile stabilire con questa

misura quale sia il vantaggio reale per l’utente nell’impiego del sistema di

predizione e del modello in uso. Abbiamo gia discusso dei difetti di questa

metrica all’interno del paragrafo 4.5.

• Keystroke Saving Measure (o misura KS) stima quanti tasti (virtuali o

fisici) si risparmino grazie all’impiego del sistema di predizione delle parole.

La misura, nel nostro caso, e data dalla differenza tra la lunghezza totale

della parola da immettere ed il numero di caratteri immessi dall’utente. A

tale valore viene inoltre sottratto una ulteriore unita corrispondente al fatto

che l’utente, per scegliere la parola, deve effettuare una selezione mediante

un pulsante (virtuale o fisico). Tale misura e in grado di mostrare quale

103 Misure impiegate

sia il vantaggio per l’utente nell’impiego di un sistema di previsione (o

nell’utilizzo di un particolare modello).

Tuttavia questa metrica, analizzata parola per parola, non tiene conto del fatto

che vi possono essere delle parole molto brevi (di non piu di tre caratteri). Que-

sto presenta dei vantaggi, come spiegato nel paragrafo 4.5, ma non permette di

renderci conto della qualita complessiva del predittore. Nel caso di parole bre-

vi il valore massimo raggiungibile con questa misurazione sarebbe 1, anche se il

predittore fosse in grado di “indovinare” subito la risposta esatta. Poniamo ad

esempio il caso di voler scrivere “del”, immettiamo la d, “del” compare in lista.

Lo scegliamo ed in questo modo abbiamo premuto due tasti (“d selezione”

che e equivalente a “d e”), l’unico carattere “salvato” e la l. Questa misura ap-

pare invece molto efficiente nel caso di una valutazione dei caratteri risparmiati

sull’intero testo. Per questo, all’interno delle prove automatiche svolte, tale me-

trica e stata presa in considerazione come rapporto fra tasti risparmiati su tasti

totali nell’intero documento di test.

• Percentuale di completamento per parola : questa misura l’abbiamo

effettuata rapportando il numero di caratteri completati dal predittore (la

differenza fra il numero di caratteri totali ed il numero di caratteri immessi

manualmente dall’utente) con la dimensione della stringa. Abbiamo poi

convertito il valore in percentuale. Tale metrica, a nostro avviso, e molto

valida per capire “quanta “parte” delle parole il nostro predittore e in grado

di completare in un determinato testo.


6.2 La valutazione manuale

6.2.1 Esperimenti effettuati

La valutazione manuale e stata svolta da due volontari utilizzando l’editor

PredictEdit. Ad ognuna delle due persone, entrambe affette da disabilita motoria

con una buona escursione nell’impiego degli arti superiori, e stato chiesto di

scrivere alcune frasi a piacere utilizzando il servizio di previsione delle parole

come aiuto durante l’immissione.

L’attivita degli utenti, previo il consenso, e stata tracciata per fini statisti-

ci. In particolare e stato salvato il testo immesso e, per ogni termine completato

utilizzando le parole presenti nella WordList, e stato loggato quale prefisso l’uten-

te avesse immesso (quanta parte della parola fosse gia stata scritta dall’utente) e

quale fosse la parola desiderata.

Entrambi i volontari hanno impiegato una tastiera fisica per immettere i

termini. Il primo utente ha preferito utilizzare le scorciatoie tastiera per l’inse-

rimento dei termini della WordList mentre il secondo ha preferito avvalersi del

mouse.

6.2.2 Risultati dei test manuali

Gli utenti, in totale, hanno immesso 99 termini. Se eliminiamo la pun-

teggiatura e le parole composte da una sola lettera (che non sono predicibili)

il totale delle parole scende a 81. Di questi, si e impiegato il completamento

mediante predizione 56 volte.

Passiamo ora alla valutazione. Teniamo presente che questi dati non

sono provenienti da fonti automatiche ma manuali. Abbiamo notato durante l’a-

nalisi che gli utenti, di tanto in tanto, hanno aggiunto qualche lettera prima di

105 La valutazione manuale

accorgersi della presenza della parola. E successo piu di una volta che l’utente ab-

bia terminato l’inserimento della parola senza sceglierla anche se essa compariva

nell’elenco.

In figura 6.1(a) e possibile vedere un grafico riassuntivo dei reciprocal

rank. Ricordiamo che, essendo il dato reciproco, piu alto e il valore (piu a destra)

migliore e il risultato (e stata indovinata con un numero inferiore di lettere)

L’MRR non e molto alto ed e pari a 0, 29. Seppur il campione di paro-

le preso in esame e piuttosto ristretto, questo dato conferma la nostra ipotesi.

Utilizzando un testo a piacere, distante quindi dall’ambito e dal lessico impiega-

to all’interno dei documenti di addestramento, si ottengono dei risultati molto

variabili. La dimensione ridotta del testo, inoltre, fa emergere in modo chiaro

il difetto principale del nostro programma: la scarsa qualita di predizione nelle

parole molto brevi.

Possiamo infatti dare uno sguardo a quali siano le parole che di frequente

non sono state predette. Sono per caso le piu brevi? Nell’86% dei casi e proprio

cosı, considerando come brevi le parole di non piu di 3 caratteri. Questo e un

dato molto utile per studiare futuri miglioramenti.

Come si puo vedere dalla figura 6.1(b) anche la misura KS sulle diverse

parole e piuttosto bassa. Le parole a zero sono aumentate perche a molti termini

mancava una sola lettera per essere completati. Non e pero affatto male un valore

di 5/81 sui termini completati risparmiando cimque battiture.

Infine in figura 6.1(c) si puo vedere la percentuale di completamento rap-

portata alla dimensione della parola. Come si vede, se escludiamo le parole non

predette (con percentuale di completamento pari a 0) abbiamo un’ottima idea dei

valori percentuali piu frequenti. In particolare e molto frequente una predizione

che completa dal 40 al 60% di una parola.

Commentando questo test potremmo dire, in modo generico, che il nostro


predittore quando “capisce” la parola ne completa circa la meta. Non male.

6.2.3 Riscontri degli utenti sull’interfaccia grafica

I riscontri degli utenti sono stati raccolti in forma di parere, mediante

un’intervista, ed osservando come lavoravano durante il test.

Prima dell’inizio delle valutazioni, ai volontari e stata data la possibilita di

prendere mano con lo strumento utilizzando il GSPredictor oppure l’NGPredictor.

Alla luce del fatto che spesso gli utenti non sono riusciti ad individuare le parole

presenti all’interno della lista abbiamo inserito la funzionalita di personalizzazione

dei caratteri e dei colori. In questo modo ora l’utente puo decidere di visualizzare

l’elenco parole con una dimensione dei caratteri piu grande ed uno schema colori

di suo gradimento.

Gli utenti, in generale, hanno espresso un parere positivo sul programma, sotto-

lineando la velocita con cui la previsione viene svolta. Ci e stato suggerito, nel

momento in cui interveniamo per muovere la “Word List” che si sovrappone al

cursore, di spostare leggermente la finestra verso il basso, in modo da rendere

visibile l’intera riga che si sta scrivendo.

Una soluzione di questo tipo e allo studio ma essa e condizionata da molti fattori,

in primo piano la dimensione della WordList stessa che puo occupare, in altezza,

tutto lo schermo.

6.3 La valutazione automatica

6.3.1 Esperimenti effettuati

Abbiamo sviluppato un applicativo che simuli la scrittura di alcuni te-

sti. Mano a mano che si procede all’inserimento delle lettere, viene richiamato

107 La valutazione automatica

0

5

10

15

20

25

30

0 1/2 1/3 1/4 1/5 10

5

10

15

20

25

30

35

0 1 2 3 4 5

(a) (b)

0

5

10

15

20

25

30

0% 10-19% 20-29% 30-39% 40-49% 50-59% 60-69% 70-79% 80-89% 90-99%

(c)

Figura 6.1: Analisi dei risultati sui test manuali. (a) Risultati dell’analisidel reciproco del rank. I risultati sono ordinati dai peggiori (non trovato, 10tentativi, 9 tentativi ecc.) ai migliori (1 solo tentativo) Le barre rappresentanola frequenza. (b) Analisi della misura KS parola per parola nel testo. Piu ci sisposta verso destra piu lettere sono state completate per una certa parola. Lebarre rappresentano la frequenza. (c) Analisi della percentuale di completamentodella parola. Le barre rappresentano la frequenza delle parole. Nell’asse delleascisse troviamo le varie percentuali. Piu ci si sposta lungo l’asse delle x piu altae la percentuale di parola che viene completata.


l’NGPredictor. Qualora, all’interno della lista parole, sia contenuto il termine

desiderato esso viene inserito. Vengono poi calcolate, per ogni parola, le tre

metriche prese in esame.

Con questo sistema abbiamo valutato due documenti diversi: il primo do-

cumento appartiene alla medesima collezione (europarl corpus) di quelli gia uti-

lizzati per il training (un documento dell’insieme di test). Il secondo documento

analizzato e composto da una collezione di articoli tratti dall’area pubblica del

sito web “LaStampa.it”. Poiche questi non vengono divulgati ne parzialmente

ne totalmente, le informazioni qui di seguito contenute non si possono intendere

come una violazione del Diritto d’Autore.

6.3.2 Risultati dei test automatici svolti su documenti di ambito differen-

te dal modello

Il numero totale di parole processate e pari a 5400. Ad esse sono stati gia

sottratti i caratteri di punteggiatura e le parole di dimensione 1.

Come si puo vedere anche dalla figura 6.2(a) i risultati dei reciprocal

rank sono molto soddisfacenti. Cio alla luce del fatto che il corpus su cui si e

addestrato il predittore e molto diverso da quello impiegato per svolgere questo

test. Notiamo una previsione positiva al primo tentativo maggiore rispetto al

numero di parole inserite senza che il termine desiderato comparisse all’interno

della lista (con rank pari a 0). Il valore di MRR e pari a 0,47. Esso e molto

maggiore rispetto a quello ottenuto nei test manuali. Cio probabilmente e dovuto

alla dimensione del documento, molto maggiore, ed all’individuazione automatica

delle parole all’interno della lista (che non commette alcun errore).

Spostandoci nella seconda parte della figura (6.2(b)) possiamo vedere

la percentuale di completamento per i diversi termini. A parte i termini non


completati (con percentuale fra lo 0 e il 9%), possiamo notare che, in generale,

la frequenza maggiore e un completamento che oscilla fra il 50 e il 69%, molto

frequente e anche un completamento fra l’80 e l’89%.

Tale risultato positivo e confermato anche dalla misura KS sull’intero

documento. Per scrivere le diverse parole (escludendo gli spazi) sarebbero state

necessarie 40531 battiture di tasti (fisici o virtuali). Grazie al nostro predittore

e stato possibile risparmiare 26114 azioni. Nel complesso, quindi, il nostro pre-

dittore e riuscito a far risparmiare il 64% nei vari termini. Se estendessimo la

proporzione anche agli spazi, in totale per scrivere l’intero documento sarebbe-

ro state necessarie 48010 digitazioni. Considerando quindi tutti i possibili tasti,

utilizzando il nostro tool e possibile risparmiare durante la digitazione del docu-

mento il 54% delle battiture. Davvero un risultato molto positivo, se pensiamo

che il predittore e stato addestrato su un insieme di documenti appartenenti ad

un dominio differente.

6.3.3 Risultati dei test su documenti appartenenti all’europarl

Le valutazioni condotte su un documento appartenente all’insieme di test

del corpus europarl era forse l’esperimento che ci premeva di piu. Infatti siamo

convinti che, addestrando il nostro tool su documenti simili a quelli che l’utente

vuole scrivere, riusciremo in futuro a migliorare ancora di piu la previsione. Come

e possibile vedere in 6.3(a) il risultato e molto soddisfacente e conferma la nostra

ipotesi iniziale. Anche con gli articoli de “La Stampa” si erano ottenuti degli

ottimi risultati, tuttavia il numero di parole non previste (con rank pari a 0) era

abbastanza alto. Come si puo vedere dall’immagine, in questo caso il numero e

molto ridotto. Il valore di MRR misurato e pari a 0,67. Il numero totale di parole

prese in considerazione all’interno di questo documento e stato pari a 20181.


Anche la percentuale di completamento per parola (visibile in figura

6.3(b)) mostra un sensibile miglioramento in questo documento rispetto al pre-

cedente. E molto frequente, infatti, che le parole vengano completate tra il 50 e

il 69% ma e ancor piu frequente che esse vengano completate per una parte che

oscilla fra l’80 e l’89%.

Questo dato e confermato anche dalla misura di Keystroke Saving (KS).

Le parole considerate, in totale, comportavano 134141 pressioni di tasti (virtuali

o fisici). Grazie al nostro tool se ne sono potute risparmiare 96366, corrispondenti

al 71,8%. Un risultato davvero importante. Non ci e possibile, in questo caso,

svolgere una valutazione precisa ed accurata sul testo completo comprensivo di

punteggiatura. Se considerassimo il documento originale, come descritto nel pa-

ragrafo 5.2.1 dovremmo comunque scartare moltissime informazioni strutturate.

Tali dati vengono eliminati in fase di preprocessamento, le punteggiature vengo-

no staccate (aggiungendo spazi e quindi aggiungendo battiture). Inoltre vengono

inseriti tag di vario tipo. Stimiamo comunque che, in tutti i casi, la percentuale

non scenderebbe sotto il 65%.


0

200

400

600

800

1000

1200

1400

1600

1800

2000

0 1/10 1/9 1/8 1/7 1/6 1/5 1/4 1/3 1/2 1

(a)

0

200

400

600

800

1000

1200

1400

1600

0-9 10-19 20-29 30-39 40-49 50-59 60-69 70-79 80-89 90-99

(b)

Figura 6.2: Analisi dei risultati sui test automatici svolti su insieme diarticoli de “LaStampa.it”. (a) Risultati dell’analisi del reciproco del rank. Irisultati sono ordinati dai peggiori (non trovato, 10 tentativi, 9 tentativi ecc.) aimigliori (1 solo tentativo) Le barre rappresentano la frequenza. (b) Analisi dellapercentuale di completamento della parola. Le barre rappresentano la frequenzadelle parole. Nell’asse delle ascisse troviamo le varie percentuali. Piu ci si spostalungo l’asse delle x piu alta e la percentuale di parola completata dal Predittore.


0

2000

4000

6000

8000

10000

12000

0 1/12 1/11 1/10 1/9 1/8 1/7 1/6 1/5 1/4 1/3 1/2 1

(a)

0

1000

2000

3000

4000

5000

6000

0-9 10-19 20-29 30-39 40-49 50-59 60-69 70-79 80-89 90-99

(b)

Figura 6.3: Analisi dei risultati sui test automatici svolti sull’insieme ditest del corpus europarl. (a) Risultati dell’analisi del reciproco del rank. Irisultati sono ordinati dai peggiori (non trovato, 10 tentativi, 9 tentativi ecc.) aimigliori (1 solo tentativo) Le barre rappresentano la frequenza. (b) Analisi dellapercentuale di completamento della parola. Le barre rappresentano la frequenzadelle parole. Nell’asse delle ascisse troviamo le varie percentuali. Piu ci si spostalungo l’asse delle x piu alta e la percentuale di parola completata dal Predittore.

CAPITOLO 7

Conclusioni e sviluppi futuri

Il progetto ha portato allo sviluppo di PredictEdit, uno strumento com-

pleto di scrittura facilitata per l’ambiente Microsoft Windows. Esso e costituito

da due parti principali.

Da un lato vi e il motore di predizione NGPredictor che fa uso di un

modello del linguaggio addestrato su un corpus del Parlamento Europeo.

Abbiamo sviluppato dei tool per preprocessare il corpus in modo da ga-

rantire la massima qualita del modello da esso generato. Sono stati eliminati i

dati superflui, i numeri e le cifre sono stati contrassegnati ed informazioni come

le date, gli anni, le ore ed i gradi sono stati clusterizzati.

Il modello e strutturato ad N-Grammi e tiene conto del contesto (fino a tre parole

precedenti) per suggerire all’utente il termine piu opportuno da immettere.

Viene inoltre implementato un meccanismo di back-off e di smoothing per mi-

gliorare la qualita del modello di base. Il risultato pero era di dimensioni molto

grandi, percio si e studiata una struttura di database relazionale su file che co-

niugasse un risparmio di spazio sul disco con la rapidita nel fornire le risposte

Conclusioni e sviluppi futuri 114

alle particolari query utilizzate.

Il modello cosı ottenuto viene impiegato in un motore di predizione. Per l’accesso

ai dati sono state testate diverse query in modo da poter ridurre al minimo il

tempo fra l’immissione di un carattere svolta dall’utente e la restituzione della

lista dei suggerimenti aggiornata. Il programma inoltre lavora cercando di ridurre

al minimo gli accessi alla base di dati in uso, sfruttando meccanismi di cache dei

dati interna, analizzando e tenendo traccia della radice e del contesto passati in

precedenza per richiedere alla base di dati soltanto le informazioni indispensabili.

Viene inoltre applicato un meccanismo di filtro per garantire un’ottima qualita

grammaticale nelle parole che sono proposte all’utente come suggerimento.

Per cio che riguarda l’interfaccia utente sono stati sviluppati due software:

Il PredictEdit e un elaboratore di testi che offre il servizio di predizione grazie ad

una finestra che suggerisce, in tempo reale, le possibili parole da inserire.

L’utente puo immettere i termini presenti in lista tramite il puntatore del mouse,

tramite combinazioni tasti oppure impiegando il tastierino numerico.

Abbiamo poi studiato ed implementato il PredictiOnDemand. Questo e un siste-

ma a moduli che rende disponibile il servizio di predizione in tantissime applica-

zioni Windows.

Il PredictiOnDemand e rivoluzionario perche non assilla l’utente con fine-

stre di predizione che compaiono e scompaiono di continuo. Esso si attiva, come

dice il nome, soltanto quando l’utente lo desidera.

Ogni modulo garantisce una predizione di qualita in una singola appli-

cazione (come Microsoft Word). Esiste poi un modulo che interagisce con le

componenti standard di Windows rendendo disponibile la predizione in tutte

quelle applicazioni che fanno uso di tali componenti. I suggerimenti delle parole

vengono offerti mediante una finestrella, simile a quella presente nel PredictEdit.

L’utente puo scegliere una delle parole presenti, sia con il mouse che tramite

115

il tastierino. La previsione, in moltissimi casi, puo avvenire anche se l’utente

desidera immettere delle parole all’interno di testo gia presente e non necessaria-

mente alla fine del documento. Questo e possibile grazie ad un avanzato sistema

di tracciamento del cursore.

I tipi di carattere come anche i colori del testo e dello sfondo nella finestra di

predizione possono essere personalizzati a piacere dall’utente per garantire la

massima leggibilita durante l’impiego del programma.

Dalle valutazioni effettuate abbiamo potuto osservare un’ottima qualita

del nostro applicativo che e in grado di ridurre di piu del 50% delle digitazioni

in un testo di dominio simile (ma differente) rispetto a quello in cui e stato

addestrato. Se esso viene impiegato all’interno di testi appartenenti al medesimo

dominio (su documenti diversi) la percentuale aumenta fino a superare il 70%.

Questo ci riporta al primo dei miglioramenti che potrebbe essere appli-

cato al motore di predizione: la costruzione dinamica del corpus. Analizzando

i documenti proposti dall’utente sara possibile costruire uno (o piu) modelli che

poi potranno essere impiegati per una predizione di maggiore qualita.

Inoltre dai test e emerso che le parole che piu spesso non vengono predette in

tempo sono le piu brevi. Si potrebbero aumentare le probabilita delle parole

piu corte, soprattutto quando il predittore sta impiegando gli unigrammi (cioe

quando non ha trovato alcuna sequenza di parole compatibile con il contesto in

cui l’utente sta lavorando).

Come abbiamo gia detto siamo consci dei limiti che un approccio basato

soltanto sui modelli del linguaggio presenta, tuttavia riteniamo che questa sia la

base su cui procedere per integrare altre metriche e tecniche migliorative.

Una strada da esplorare, ad esempio, e quella dell’integrazione di un analizza-

tore della grammatica. In particolare si potrebbe impiegare una combinazione

fra modelli ad N-Grammi basati sui termini ed altri basati sui POS. In questo

Conclusioni e sviluppi futuri 116

modo si riuscirebbero a filtrare maggiormente le parole ed a proporre un elenco

grammaticalmente piu appropriato (e quindi contenente termini piu probabili).

Inoltre potrebbe essere implementato un meccanismo di cache in grado di aumen-

tare, in base ad una funzione, la probabilita dei termini che sono stati richiesti di

recente.

Spostando poi la nostra attenzione sulle applicazioni lato utente, sareb-

be sicuramente interessante aggiungere nuovi moduli per il PredictiOnDemand

rendendolo compatibile con altre applicazioni oggi non supportate ma molto

diffuse.

Molto utile agli utenti affetti da DSA sarebbe l’inserimento di funzionalita di

lettura tramite sintesi vocale sia all’interno del PredictEdit, che all’interno del

PredictiOnDemand. Esse sono piuttosto semplici da realizzare poiche l’applica-

tivo fa uso di librerie standard e queste componenti sono disponibili per essere

impiegate all’interno del framework .NET.

Infine si potrebbe studiare il modo per spostare la finestra di previsione delle

parole oltre che da un lato all’altro dello schermo anche in verticale (in alto o in

basso) in modo da rendere visibile la riga che al momento si sta editando.

Da tutto questo e chiaro che il progetto e lontano dall’essere concluso.

Tuttavia molti accorgimenti come l’implementazione di interfacce, l’utilizzo di

pattern e la parametrizzazione (ove possibile) sia del motore di predizione, che

puo produrre e processare un modello ad N-Grammi di qualunque classe, sia

dell’interfaccia utente non possono che aiutare lo sviluppo futuro. In quest’ottica

va anche l’attenzione rivolta nell’utilizzo di tecnologie standard.

Confortati dai risultati ottenuti possiamo quindi dire che la strada e aper-

ta e che il lavoro fin’ora fatto ci da modo di disporre di una base funzionante,

testata e solida su cui progredire per migliorare le diverse componenti del nostro

progetto.

Ringraziamenti

Un sentito ringraziamento va, anzitutto, al mio relatore, Prof. Ronchettiche mi ha sempre supportato, non solo nel lavoro di tesi ma in tutto il miopercorso in Laurea Magistrale. Ha sempre dimostrato una grande disponibilitafornendomi sempre una possibilita di confronto. Oltre a cio mi ha supportatocon idee, suggerimenti e consigli durante il lavoro di progetto come nella stesuradella Tesi.

Un grazie alla mia famiglia, che mi ha aiutato, sostenuto e ben consigliatodurante i momenti di maggior tensione ed ansia, come spinto ad andare avantinei momenti piu di stanchezza, fatica e noia.

Sincera gratitudine la devo al Sig. Gianni Morelli, responsabile del servi-zio disabilita dell’Opera Universitaria e al Prof. Alberto Montresor. Senza questedue persone, sempre disponibili e pronte a dare una mano, il mio percorso di studidal primo anno di Laurea Triennale alla fine della Laurea Magistrale stato benpiu arduo e pieno di ostacoli.

Ringrazio per la cordialita e la disponibilta l’Ing. Raffaele Di Vaio diTifloSystem S.p.A. che mi ha fornito tutto il materiale ed supporto necessarioper svolgere i test sul predittore presente all’interno del Kurzweil 3000.

Un grazie ad Igor(e) per l’aiuto e il supporto che mi ha dato durantelo svolgimento del progetto. Anche se una riga di codice sotto Windows non lascriverebbe mai, per tutto cio che e multipiattaforma come SQLite e proprio undrago!

Grazie a Stefano e Stella che negli ultimi due anni hanno fatto si che po-tessi seguire le lezioni in tranquillita, autonomia e con la disponibilita e simpatiadi due buoni amici. Grazie a Francesco, che spera ancora che non gli tolgano laProvincia di Belluno, anche se di fatto e emigrato a Udine.

Un simpatico ringraziamento a Luca per il supporto, l’aiuto durante latesi, le chiacchiere, forse anche per gli orari. . . no per quelli no, ho deciso! So-

Ringraziamenti 118

prattutto pero per l’amicizia, per le ciaccolate e gli incoraggiamenti nel periododi tesi.

Non dimentico i piu simpatici fra i ragazzi del servizio di accompagna-mento (quelli che mi odiano ancora per le assistenze a Borino alle 7 e 45), senzadi loro... sarei col naso piantato sul ghiaccio!

Davvero grazie, e stato un piacere ricevere aiuto e simpatia . . . anche see vero che non leggerete mai questa pagina!

In conclusione e doveroso un particolare ringraziamento all’Assessoratoper le Politiche Sociali della Provincia di Treviso e a tutte le persone che hannoseguito l’assistenza scolastica dei ciechi e dei sordi negli ultimi 18 anni.E davvero difficile ricordarsi di tutti, di certo non dimentico il prezioso lavorodel Sig. Carnio e la fiducia che mi e stata data dalla Dott.sa Boccaletto e dallaDott.sa Melocco. Grazie a loro ho potuto concludere i miei studi senza intoppi,sicuro di avere sempre un supporto per le mie necessita di studio.

Bibliografia

[ACD+07] Carlo Aliprandi, Nicola Carmignani, Nedjma Deha, Paolo Mancarella,and Michele Rubino, Advances in nlp applied to word prediction.

[AM06] Hisham Al-Mubaid, A learning-classification based approach for wordprediction.

[Evm06] Anna Evmenova, Word prediction software for students with writingdifficulties.

[FH03] Afsaneh Fazly and Graeme Hirst, Testing the efficacy of part-of-speechinformation inword completion.

[GVA06] Nestor Garay-Vitoria and Julio Abascal, Text prediction systems: asurvey, Universal Access in the Information Society 4 (2006), no. 3.

[Hie] Djoerd Hiemstra, Language models.

[HT02] P. Henderson and T. Trust, Access all areas: disability, technologyand learining, ch. Ch. 7 Physical disability and technology, pp. 29–32,TechDis with the Association for Learning Technology, 2002.

[HT09] Henderson and Trust, Speech and language processing - an introduc-tion to natural language processing, computational linguistics, andspeech recognition, second ed. ed., ch. Ch. 4 NGrams, Pearson PrenticeHall, 2009.

[Koe05] Philipp Koehn, Europarl: A parallel corpus for statistical machinetranslation.

BIBLIOGRAFIA 120

[log] Logos - la lettura, http://courses.logos.it/IT/1_6.html.

[Mica] Microsoft, Pagine msdn su microsoft ui automation, http://msdn.microsoft.com/en-us/library/ms753388%28v=vs.90%29.

[Micb] , Pagine msdn su word object model overview, http://msdn.microsoft.com/en-us/library/kw65a0we.aspx.

[Micc] , Pagine msdn sull’impiego degli hooks, http://msdn.microsoft.com/en-us/library/windows/desktop/ms632589.aspx.

[Pro] SRILM Project, ngram-format man page, http://www.speech.sri.com/projects/srilm/manpages/ngram-format.5.html.

[Ros95] Roni Rosenfield, The cmu statistical language modeling toolkit andits use in the 1994 arpa csr evaluation, ARPA Spoken LanguageTechnology Workshop, Austin, TX (1995).

[Ros00] Ronald Rosenfeld, Two decades of statistical language modeling:Where do we go from here.

[spe] Word prediction software comparison chart,http://www.spectronicsinoz.com/article/word-prediction-software-comparison-chart/.

[SPPC06] Simone Soria, Emanuele Perini, Andrea Prati, and Rita Cucchia-ra, Facemouse: A human-computer interface for tetraplegic people,Computer Vision in Human-Computer Interaction, Lecture Notes inComputer Science 3979/2006 (2006), 99–108.

[Sto02] Andreas Stolcke, Srilm - an extensible language modeling toolkit, 2002,pp. 901–904.

[TH04] Jennifer Tumlin and Kathryn Wolff Heller, Using word predic-tion software to increase typing fluency with students with physicaldisabilities.

[THG] The grid 2, user manual.

[Voo99] E.M. Voorhees, The trec-8 question answering track report, TheEighth Text REtrieval Conference (TREC 8) (1999), 77–82.

http://courses.logos.it/IT/1_6.html

http://msdn.microsoft.com/en-us/library/ms753388%28v=vs.90%29



http://msdn.microsoft.com/en-us/library/kw65a0we.aspx

http://msdn.microsoft.com/en-us/library/kw65a0we.aspx

http://msdn.microsoft.com/en-us/library/windows/desktop/ms632589.aspx



http://www.speech.sri.com/projects/srilm/manpages/ngram-format.5.html



http://www.spectronicsinoz.com/article/word-prediction-software-comparison-chart/

http://www.spectronicsinoz.com/article/word-prediction-software-comparison-chart/

121 BIBLIOGRAFIA

[WA07] Tonio Wandmacher and Jean-Yves Antoine, Methods to integratea language model with semantic information for a word predictioncomponent, 506–513.

[WEB] Sito web unione italiana lotta alla distrofia muscolare - padova, http://digilander.libero.it/uildmpadova/ausili.htm.

http://digilander.libero.it/uildmpadova/ausili.htm

http://digilander.libero.it/uildmpadova/ausili.htm

UNIVERSITA DEGLI STUDI DI TRENTO - Marco Ronchettilatemar.science.unitn.it/pod/docs/tesi.pdf · gli...

Documents

Transcript of UNIVERSITA DEGLI STUDI DI TRENTO - Marco Ronchettilatemar.science.unitn.it/pod/docs/tesi.pdf · gli...