` DEGLI STUDI DI TRENTO
UNIVERSITA
Facolt`
a 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
2 Strumenti di predizione delle parole
2.1 Introduzione al problema . . . . . . . .
2.2 Utilizzo da parte di utenti con difficolt`a
2.3 Utilizzo da parte di utenti con difficolt`a
2.4 Altri impiegi dei sistemi di predizione .
1
. . . . . . . . . . .
motorie . . . . . .
di apprendimento
. . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3 Definizione del problema, terminologia e Stato Dell’Arte dei
sistemi di Predizione
3.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Definizione del problema e terminologia adottata . . . . . . . . .
3.2.1 Esempio di predizione senza contesto . . . . . . . . . . . .
3.2.2 Esempio di predizione con contesto . . . . . . . . . . . . .
3.3 Sistemi che non fanno uso di contesto . . . . . . . . . . . . . . . .
3.3.1 Lista di parole pesate a dizionario aperto . . . . . . . . .
3.3.2 Lista di parole a dizionario costruito dall’utente . . . . . .
3.3.3 Frequenza di vicinanza fra lettere . . . . . . . . . . . . . .
3.3.4 Utilizzo della cache con dizionario aperto . . . . . . . . . .
3.4 Sistemi di predizione basati sul contesto . . . . . . . . . . . . . .
3.4.1 Lista di parole e di coppie di parole pesate a dizionario
aperto . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2 Utilizzo dei modelli del linguaggio . . . . . . . . . . . . .
3.4.3 Cenni su possibili approcci machine-learning e basati sull’analisi del linguaggio (NLP) . . . . . . . . . . . . . . . .
5
5
8
14
17
19
19
20
23
24
25
26
26
27
28
28
29
30
31
3.5
Principali prodotti destinati all’utente finale
3.5.1 Kurzweil 3000 . . . . . . . . . . . . .
3.5.2 TypingAssistant . . . . . . . . . . .
3.5.3 Click-N-Type . . . . . . . . . . . . .
3.5.4 Chewing Word . . . . . . . . . . . .
3.5.5 DiCOM . . . . . . . . . . . . . . . .
3.5.6 Farfalla Editor . . . . . . . . . . . .
3.5.7 Google Scribe . . . . . . . . . . . . .
3.5.8 Co:Writer . . . . . . . . . . . . . . .
3.5.9 Read&Write . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
32
33
35
36
37
38
39
41
42
43
4 Predizione basata sui Modelli del Linguaggio
4.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Modelli del linguaggio . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Simbologia e convenzioni . . . . . . . . . . . . . . . . . . . . . . .
4.4 La necessit`a dell’approssimazione: Gli N-grammi . . . . . . . . .
4.5 Valutazione di un modello . . . . . . . . . . . . . . . . . . . . . .
4.5.1 Valutazione estrinseca mediante i sistemi di predizione . .
4.5.2 Perplexity . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6 Miglioramenti del modello: Smoothing e Back-Off . . . . . . . . .
4.6.1 Smoothing . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6.2 Back-off ed interpolazione . . . . . . . . . . . . . . . . . .
4.7 Il superamento di un approccio basato soltanto sui modelli del
linguaggio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
47
48
50
50
53
54
57
59
61
63
5 Il sistema di scrittura facilitata PredictEdit
5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Sviluppo del modello del linguaggio . . . . . . . . . . . . . . . .
5.2.1 La costruzione del corpus . . . . . . . . . . . . . . . . . .
5.2.2 Dal corpus al Modello del Linguaggio in formato ARPA . .
5.2.3 Dal modello del linguaggio in formato ARPA alla struttura
dati per la predizione . . . . . . . . . . . . . . . . . . . . .
5.3 Sviluppo dei motori di predizione . . . . . . . . . . . . . . . . . .
5.3.1 L’interfaccia IPredictor . . . . . . . . . . . . . . . . . . . .
5.3.2 Lo sviluppo del predittore locale NGPredictor . . . . . . .
5.3.3 Lo sviluppo del client per Google Scribe (GSPredictor) . .
5.4 Sviluppo dell’editor PredictEdit . . . . . . . . . . . . . . . . . . .
5.5 Il PredictiOnDemand . . . . . . . . . . . . . . . . . . . . . . . .
5.5.1 Terminologia . . . . . . . . . . . . . . . . . . . . . . . . .
5.5.2 PredictiOnDemand, la predizione su richiesta . . . . . . .
67
67
69
69
71
64
73
76
76
76
81
83
89
90
92
5.5.3
5.5.4
5.5.5
Gli appModule ed il modulo per Microsoft Word . . . . .
UIAutomation per i controlli standard di Windows . . . .
Come avviene la previsione e l’immissione . . . . . . . . .
93
95
96
6 Valutazione del PredictEdit
6.1 Misure impiegate . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 La valutazione manuale . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 Esperimenti effettuati . . . . . . . . . . . . . . . . . . . . .
6.2.2 Risultati dei test manuali . . . . . . . . . . . . . . . . . .
6.2.3 Riscontri degli utenti sull’interfaccia grafica . . . . . . . .
6.3 La valutazione automatica . . . . . . . . . . . . . . . . . . . . . .
6.3.1 Esperimenti effettuati . . . . . . . . . . . . . . . . . . . . .
6.3.2 Risultati dei test automatici svolti su documenti di ambito
differente dal modello . . . . . . . . . . . . . . . . . . . . .
6.3.3 Risultati dei test su documenti appartenenti all’europarl .
101
102
104
104
104
106
106
106
7 Conclusioni e sviluppi futuri
113
Ringraziamenti
117
Bibliografia
119
108
109
CAPITOLO 1
Introduzione
Molte persone nel Mondo, grazie all’introduzione delle macchine da scrivere hanno avuto la possibilit`a per la prima volta di sperimentare la comunicazione 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 Computer, che elabora le informazioni in tempo reale, le possibilit`a di offrire un servizio
di scrittura facilitata per aiutare molti pi`
u utenti `e diventato realistico.
Negli anni ’80 si sono diffusi i primi sistemi di scrittura per persone con
disabilit`a 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 contenente 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 per`o 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 mobilit`a minima o che sono soggette ad altre difficolt`a,
come la dislessia.
Comprendendo queste necessit`a, gi`a a partire dalla met`a 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
capacit`a 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 proporre a schermo, evitando che questi lo debba scrivere per intero.
Non `e per`o 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 attivit`a. 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 scriver`a in automatico.
Nel tempo la ricerca in questo ambito ha esplorato varie modalit`a con cui
il problema della previsione delle parole pu`o essere risolto. Al momento gli applicativi commerciali pi`
u diffusi nel Mondo fanno uso dei Modelli del linguaggio o
anche dell’analisi della struttura grammaticale della frase. Sfortunatamente questi 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
difficolt`a 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 persone affette dai diversi problemi che possono trovare utile l’impiego di un software
di previsione delle parole. Discuteremo inoltre dei requisiti richiesti da ciascuna categoria di utenti. Nel capitolo 3, poi, definiremo in maniera pi`
u 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 Linguaggio, come sia possibile impiegarli per l’implementazione di un algoritmo di previsione 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 previsione delle parole studiato ed implementato per l’ambiente Microsoft Windows.
Inizieremo presentando il motore di predizione e l’algoritmo su cui si basa. Sposteremo 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 innovativo, 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 provenienti 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-
pacit`a di inferire la parola successiva grazie al contesto della frase, all’argomento
del testo o della conversazione. Non si `e certi della frase che verr`a detta o della risposta che l’interlocutore dar`a, ma quando questi inizia a pronunciare una
parola, molto spesso `e facile intuirla prima che questi la termini.
Ci si pu`o 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 capacit`a sta anche alla base di una buona velocit`a nella lettura a
prima vista. Se fosse necessario analizzare tutte le lettere attentamente prima di
leggere una parola il processo sarebbe molto pi`
u 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 pi`
u 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 per`o 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 attivit`a.
Questo genere di programma viene utilizzato in abbinamento ad un software di videoscrittura (solitamente a scelta dell’utente). Oltre ai consueti controlli (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 pi`
u avanzati permettono di scegliere fra diversi insiemi di parole da utilizzare per la predizione. Tali insiemi di termini possono essere suddivisi
in base ad ambiti (Archeologia, Animali acquatici ecc.) oppure in base alla persona che far`a 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 necessit`a di chi sta scrivendo.
Alcuni prodotti, poi, adottano l’approccio dell’“open dictionary” (a dizionario 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 pi`
u formale e descriveremo le peculiarit`a
dei principali strumenti di predizione disponibili oggi sul mercato e le tecniche
utilizzate per svolgere il loro compito al meglio coniungando rapidit`a, leggerezza
e precisione nella predizione.
All’interno di questo capitolo, invece, ci occuperemo dell’efficacia di questa categoria di applicativi e del loro impiego per consentire e velocizzare la scrittura in diversi ambiti: dalle disabilit`a motorie alle difficolt`a di apprendimento e
di letto-scrittura ai nuovi ambiti di utilizzo legati alla mobilit`a.
Prima di procedere per`o `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 difficolt`a fisiche e a persone con difficolt`a di apprendimento o di letto-scrittura. Bisogna tenere presente che spesso le categorie di
prodotti impiegate per alleviare il disagio si intersecano e che le problematiche della singola persona possono essere molteplici e spesso difficilmente “incasellabili”
in categorie cos`ı ampie.
Un disabile con un handicap motorio molto grave pu`o necessitare di un
sintetizzatore vocale poich´e, 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 difficolt`a 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.
Strumenti di predizione delle parole
2.2
8
Utilizzo da parte di utenti con difficolt`a 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 pi`
u diverse: dalle 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 disabilit`a 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 molto valida per un’immissione diretta delle parole. Purtroppo essi sono utilizzabili
soltanto da coloro che hanno complete capacit`a di pronuncia e un ottimo coordinamento 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 difficolt`a motorie
privacy di ci`o che si scrive. Tuttavia sono stati effettuati alcuni tentativi di integrazione fra strumenti di predizione delle parole e strumenti di riconoscimento
vocale.1
Un altro ausilio molto impiegato e di seguito non trattato sono i comunicatori simbolici. Essi consentono l’inserimento di parole su tastiera ridotta o,
prevalentemente, mediante elementi simbolici e immagini. Tali tecnologie (tecnicamente chiamate C.A.A. ad immagini) si basano su strumenti parole o concetti
inseriti in “griglie” selezionabili mediante touchscreen, joystick o, nei casi pi`
u
gravi, mediante controlli a scansione. In [THG] `e presente una descrizione molto
dettagliata di uno dei sistemi pi`
u 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
difficolt`a di apprendimento, non `e dipendente dalla complessit`a di ci`o 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 modalit`a di inserimento delle parole.
1
Ulteriori informazioni su http://www.donjohnston.com/products/dragon_
naturally_spkg/index.html
Strumenti di predizione delle parole
10
In base poi al dispositivo di input utilizzato vi sono degli accorgimenti da
porre nello sviluppo del Word Predictor.
L’esempio pi`
u 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 pi`
u grandi di quelle normali, per questo spesso vengono chiamate “tastiere
espanse non programmabili”, ci`o 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 dovr`a 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 motricit`a 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 pi`
u livelli attivabili mediante combinazioni tasti. Le
persone che ne fanno uso possono non necessitare di sistemi di predizione poich´e
mantengono una discreta velocit`a di digitazione. In ogni caso, per essere utile in
2
esempio di tastiera a scudo http://www.superabile.it/web/it/CANALI_
TEMATICI/Ausili/Gli_Ausili_e_le_Aziende/Comunicare_e_ausili_
tecnologici/info465992533.html
3
Esempio di tastiera ridotta http://www.helpicare.com/prodotto/winmini-usb
11
Utilizzo da parte di utenti con difficolt`a motorie
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).
Ci`o `e utile dato che le tastiere di questa categoria non comprendono il tastierino
numerico.
Infine possono essere utilizzate tastiere espanse programmabili. Sono simili alle tastiere con scudo ma presentano tasti aggiuntivi programmabili dall’utente.
Utilizzatori di tastiere virtuali con sistemi di puntamento alternativi
Coloro che non possono utilizzare tastiere fisiche o che trovano troppo lenta 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 esempio 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 libert`a 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).
4
faceMOUSE http://www.aidalabs.com/SitoAIDA2009/FaceMOUSE.html
Strumenti di predizione delle parole
12
Come detto non si pu`o dare per scontato che le tastiere a schermo comprendano tutti i tasti contenuti nelle tastiere tradizionali e dunque non si pu`o
dare per scontato che l’utente possa ricorrere alle shortcut. Oltre a ci`o spesso `e complesso svolgere combinazioni di tasti perch´e esse richiedono puntamenti
multipli.
Ci`o 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 possibilit`a 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 pu`o portare
il puntatore e cliccare.
Alcuni dispositivi di puntamento dedicati (come il faceMOUSE) integrano
gi`a 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 disabilit`a 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
13
Utilizzo da parte di utenti con difficolt`a motorie
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 caratteri 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 difficolt`a della
persona).
Qualora l’utente voglia immettere un simbolo presente in una delle righe dovr`a
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 gi`a integrato nel software
di gestione. Ci`o `e indispensabile perch´e le parole del predittore devono essere
disponibili nella griglia di selezione. L’esigenza di accelerare il processo di inserimento mediante suggerimenti in queste situazioni `e davvero molto sentita. Spesso
l’utente utilizza immagini per esprimere necessit`a, sentimenti o altro. I principali 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
difficolt`a motorie di uno strumento di predizione (Co:Writer) porta un miglioramento nei due casi di persone con velocit`a di scrittura pi`
u lenta: “Van e Sam sono
i due studenti che hanno mostrato i miglioramenti maggiori in termini di parole
5
6
Esempio di software a scansione http://www.ausili.com/caa7.htm
EyeClick http://www.aidalabs.com/SitoAIDA2009/EyeClick.html
Strumenti di predizione delle parole
14
al minuto utilizzando uno programma di predizione delle parole. Dei quattro
studenti che hanno svolto l’esperimento sono quelli con le maggiori difficolt`a fisiche.” [TH04] Nel caso di persone con una buona velocit`a di scrittura il predittore
pu`o rallentare l’utente. Ci`o dimostra che c’`e ancora un margine di miglioramento in questo tipo di strumenti per poterli rendere effettivamente efficaci anche a
persone con difficolt`a motorie lievi.
2.3
Utilizzo da parte di utenti con difficolt`a di apprendimento
Negli ultimi anni gli strumenti informatici per utenti affetti da dislessia,
disgrafia e disturbi specifici dell’apprendimento (DSA) sono aumentati considerevolmente 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 funzionalit`a 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 facilit`a 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 funzionalit`a
15
Utilizzo da parte di utenti con difficolt`a 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 questo 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 disabilit`a 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 “modalit`a 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 proporr`a 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 perch`e il software viene utilizzato in ambito scolastico,
pu`o risultare utile permettere all’utente di combinare diversi dizionari. Ad esempio, ad un bambino di quinta elementare che sta studiando geografia potrebbe
essere utile, in un ipotetico sistema di predizione, il dizionario “scuola elementare secondo ciclo” unitamente al dizionario “citt`a del mondo” ed al dizionario
Strumenti di predizione delle parole
16
“termini geografici”.
Molta attenzione deve essere poi posta in fase di studio e di design dell’applicazione. i sistemi devono essere utilizzabili da bambini ed anche i vocabolari devono tenere conto di questa particolarit`a. 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 ci`o il vocabolario non era adatto agli studenti
poich`e 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’utilit`a dei sistemi di predizione varia da
prodotto a prodotto e da persona a persona. La capacit`a di scrittura degli studenti
che hanno svolto il test `e aumentata in termini di parole totali, fluidit`a dei termini
e delle frasi e velocit`a di composizione del testo di valori diversi a seconda del
prodotto utilizzato. [Evm06]
Dallo studio effettuato si pu`o inoltre dedurre che assieme al programma di predizione delle parole `e importante che sia integrato nell’editor (o opportunamente
attivato) il correttore per errori ortografici e lo strumento di analisi di errori grammaticali nella frase o nel periodo. infatti nel caso di uno studente, `e aumentata
in maniera uguale la velocit`a con tre diversi strumenti di predizione. [...] Non `e
invece cambiata la fluidit`a delle frasi con nessuno dei tre strumenti in uso. La
spiegazione pu`o derivare dal fatto che lo scopo principale di un sistema di predizione delle parole `e quello di colmare difficolt`a nella digitazione e che questo
tipo di strumento pu`o fornire soltanto un aiuto limitato per ci`o che riguarda il
controllo della struttura grammaticale delle frasi. [Evm06].
17
2.4
Altri impiegi dei sistemi di predizione
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 necessit`a di questa categoria di utenti a quella delle persone con difficolt`a 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 men`
u o nelle finestre di
dialogo) si avvicinano pi`
u 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 pi`
u avanzati di predizione e correzione delle parole sono utilizzati durante 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 velocit`a di comunicazione fra client e server
e l’utilizzo del meccanismo della cache per dare una risposta il pi`
u rapidamente
Strumenti di predizione delle parole
18
possibile.
Nelle prossime pagine cercheremo di dare una definizione pi`
u precisa del
problema della predizione delle parole, presenteremo alcune tecniche (dalle pi`
u
semplici alle pi`
u 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 Stato
Dell’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 pu`o essere impiegata. Sono state descritte le categorie di utenti “destinatari” discutendo i loro problemi ed i requisiti che essi richiedono a prodotti
di questo tipo.
In questo capitolo cercheremo di definire in maniera pi`
u formale il problema 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 sicuramente molto precise ma che vincolano l’utente ad impiegare un software sempre
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
20
legato ad un application server addetto al processamento delle richieste.
Nell’ultima parte di questo capitolo, infine, verranno proposti diversi prodotti e
ne verr`a 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, verr`a 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 verr`a fatto riferimento genericamente ad “iniziale” (al singolare e senza alcun aggettivo numerale) si intender`a la prima iniziale. Ogni
qualvolta verr`a utilizzato “iniziali” (al plurale e senza aggettivo numerale)
si intender`a l’intero prefisso.
• Tutto ci`o che precede la parola da prevedere verr`a chiamato predecessore.
Tutto ci`o che segue la parola da predire verr`a chiamato successore.
21
Definizione del problema e terminologia adottata
• Predecessore e successore dovrebbero, in base alla definizione comune, definire il contesto. Per maggior chiarezza, poich´e in generale nessuna tecnica
di predizione analizzata in questo lavoro tiene conto del successore, definiamo 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 potr`a 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” verr`a rappresentata come un termine (w). Cos`ı il contesto
unitamente alla futura parola sar`a 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 terminatore di frase.
• La lista dei termini (o la lista parole) indica la l’elenco di termini che l’algoritmo offre come completamento della radice. Tale lista comprende termini
interi e non suffissi della radice. Nell’esempio, la lista dei termini dovr`a
comprendere “piatto” e non “atto”.
Completata la definizione della terminologia di base possiamo procedere
alla definizione del problema.
La previsione delle parole pu`o 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.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
22
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.
Ci`o 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 pu`o essere
una probabilit`a ma anche una funzione di peso.
In base all’algoritmo scelto la funzione di probabilit`a 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, definiremo in maniera formale una funzione di probabilit`a 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 pu`o 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 perch´e `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 parler`a di dizionario “aperto” (open dictionary)
altrimenti, se il dizionario non consente aggiunte si parler`a di dizionario “chiuso”
(dizionario prefissato o closed dictionary in inglese).
I criteri con cui vengono stabilite le probabilit`a, il contenuto dei vari
vocabolari e la scelta del vocabolario pi`
u 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 pi`
u dizionari.
3.2.1
Esempio di predizione senza contesto
La soluzione pi`
u semplice, riprendendo l’esempio 3.1 sta nel presentare, in
ordine alfabetico, tutte le parole che iniziano con “pi”, l’utente immetter`a un’altra
lettera, ad esempio “pia” e, in tal modo, il filtraggio si far`a pi`
u 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, pi`
u
precisamente, il loro peso (la loro probabilit`a) `e stabilito dall’ordine alfabetico
(una parola che inizia con “A” avr`a un peso maggiore di una che inizia con “B”,
in tal modo `e possibile applicare la formula generica in equazione 3.1).
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
3.2.2
24
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 dizionari, suddividendo i termini in base al proprio valore grammaticale: (sostantivi,
verbi, aggettivi, articoli, preposizioni, congiunzioni, pronomi ecc.). Anche in questo 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. Ci`o pu`o 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 proporr`a, 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 poich´e, prima di restituire 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 algoritmo 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 algoritmi 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 per`o 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 estratti i termini. Nel caso di analisi della frequenza (caso molto comune), se durante
il processamento del documento una parola `e gi`a 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 importanza, invece, la frequenza dei termini (se non dei principali) poich`e questa viene
“limata” facilmente durante l’utilizzo.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
3.3.1
26
Lista di parole pesate a dizionario aperto
` l’esempio pi`
E
u 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
pi`
u 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 probabilit`a) 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 pu`o variare da applicativo
ad applicativo.
Alcuni di questi sistemi aggiungono le nuove parole assegnandovi un valore predefinito, ad esempio 1. Essi non definiscono un valore massimo per il
peso. In questo modo i contatori delle parole pi`
u 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 pu`o
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 pi`
u di frequente disponibili anche in Italiano. Essi vengono distribuiti privi
di vocabolario.
´ compito dell’utente costruire uno (o pi`
E
u) dizionari. Il programma consente infatti 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 caso una parola sia ricorrente, il suo valore di peso viene incrementato in modo
da risultare pi`
u 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 pi`
u ampie in cui questa non `e la funzione principale. Esso
`e utile se il programma viene distribuito in pi`
u lingue. Non `e richiesta infatti la
localizzazione di un vocabolario poich´e `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 pi`
u probabili per comporre le parole.
Analizzeremo nel seguito un esempio di predittore di parole molto particolare che fa uso di questa tecnica al fine di fornire un metodo alternativo ma
efficace di immissione.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
3.3.4
28
Utilizzo della cache con dizionario aperto
La cache solitamente non viene impiegata in modo autonomo ma, piutto-
` molto difficile valutare
sto, fornisce un supporto a molti sistemi di predizione. E
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 per`o osservato se le parole vengano immesse nella stessa frase o in altre
e perci`o 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 pi`
u facile che venga richiesto dall’utente di inserire nello stesso testo delle parole gi`a scritte in precedenza rispetto
alle altre. Per questo la loro probabilit`a `e aumentata di un fattore costante oppure 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 probabilit`a 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 probabilit`a pi`
u 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 illustrato 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.
Ci`o implica per`o il superamento della semplice struttura a vocabolario
e la generazione di basi di dati di dimensioni maggiori. Come avremo modo di
discutere pi`
u approfonditamente nel capitolo 4 anche la procedura di creazione
di queste strutture `e pi`
u 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,
´ quindi errato, in
come “aspettativa” dei futuri testi che l’utente vorr`a scrivere. E
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, ci`o 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 continuit`a 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 pu`o 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 avr`a un’importanza maggiore del dizionario a singoli termini.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
30
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 dizionario 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 dizionario delle coppie essa viene aggiunta. Il primo elemento della coppia sar`a il
termine precedente, il secondo elemento della coppia sar`a la nuova parola inserita.
Gi`a questo semplice metodo ci fa rendere conto che la struttura dati ospitante il dizionario `e molto maggiore rispetto ai sistemi precedenti. Se paragoniamo questo sistema a quello in 3.3.1, nel caso pessimo, difficilmente raggiungibile,
la dimensione sar`a n2 maggiore (con n il numero dei termini del dizionario).
Il limite principale di questa tecnica `e che spesso si `e costretti ad utilizzare dizionari chiusi, non aggiornabili in automatico dall’utente. Questo perch´e si rischierebbe 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 pu`o avere un approccio, per programmi multilingua, 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. Poich`e 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 problemi che l’impiego dei semplici modelli del linguaggio pu`o 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 pu`o essere considerata una classificazione in cui diverse parole
selezionate sono classificate al fine di determinare quella pi`
u adatta in un dato
contesto. [AM06] Il sistema, durante l’analisi del corpus per l’addestramento, utilizza 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
pi`
u 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 pi`
u) elementi del linguaggio quale sia il candidato
successivo pi`
u valido. In particolare uno studio su questo si pu`o trovare in [FH03].
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
32
Ci`o 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 probabilit`a da assegnare ai termini contenuti nei vettori. L’integrazione pu`o avvenire mediante una cache “semantica” o mediante diverse forme di interpolazione. I risultati proposti in [WA07] sono confortanti e dimostrano 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 modalit`a 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 previsione di parole come funzionalit`a 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, poich`e i software a
disposizione sono davvero molti.
33
Principali prodotti destinati all’utente finale
Gli ultimi due prodotti descritti sono quelli pi`
u famosi ed efficaci disponibili 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 societ`a sotto esposti `e di propriet`a
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 funzionalit`a, 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’attivit`a 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 ci`o 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 dizionario dei sinonimi e delle parole simili e gli strumenti di traduzione. Non tutte
queste funzionalit`a sono disponibili in lingua italiana.
Il predittore di parole `e uno degli strumenti messo a disposizione all’interno dell’editor di testi. Si attiva tramite voce di men`
u oppure mediante combinazione di tasti. Esso funziona esclusivamente all’interno dell’editor del Kurzweil e
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
34
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 pu`o 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 numero di elementi `e comunque regolabile tramite la finestra di configurazione del
software. Le combinazioni tasti, comunque, consentono l’inserimento immediato
di non pi`
u 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 possibile una importazione automatica di termini da una selezione di documenti. Il
testo da processare per essere aggiunto al dizionario deve essere aperto nella finestra 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
1
Kurzweil 3000 – Kurzweil Educational Systems – http://http://www.kurzweiledu.
com/. Il distributore per l’Italia `e TifloSystem S.p.A. http://www.tiflosystem.it/
35
3.5.2
Principali prodotti destinati all’utente finale
TypingAssistant
TypingAssistant di SumitSoft `e il primo esempio di software dedicato
` disponibile in pi`
esclusivamente alla predizione. E
u lingue fra cui l’Italiano, `e gi`a
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 applicazioni 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.
Ci`o ci ha suggerito il modo in cui il software opera: esso non `e in grado
di osservare il contesto, poich`e 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.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
TypingAssistant `e un prodotto commerciale di Sumisoft.
3.5.3
36
2
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 touchscreen, joystick, sensori di movimento o switch di selezione, permette infatti l’inserimento di testo non solo mediante click ma anche tramite sistemi a
scansione.
Sono impostabili diversi layout di tastiera dai pi`
u semplici (adatti appunto ai
sistemi a scansione) alle tastiere tradizionali.
Le parole possono essere immesse direttamente in qualunque applicazione o pu`o
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 momento 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 gi`a 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.
2
3
TypingAssistant – SumiSoft http://www.sumitsoft.com/
Click-N-Type – cnt.lakefolks.com
37
Principali prodotti destinati all’utente finale
3.5.4
Chewing Word
Chewing Word4 `e un sistema a tastiera a schermo gratuito sviluppato da
Aristide Grange all’interno dell’Universit`a di Lorraine (Francia). Il software `e
multipiattaforma e consente ad utenti con limitate capacit`a motorie o con disturbi 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 per`o 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 pu`o procedere in due modi: o si seleziona la lettera successiva
ricercandola autonomamente all’interno della tastiera oppure si procede continuando a cliccare sulla radice (illuminata in giallo), il sistema inizier`a a ciclare
fra i possibili completamenti tentando altre lettere.
La predizione seppur molto evoluta `e priva di contesto. Essa fa uso delle statistiche sulla frequenza di vicinanza fra le lettere come spiegato brevemente in 3.3.3.
La qualit`a `e buona poich´e si `e proposta una forma di inserimento innovativa.
Le statistiche relative alla lingua italiana sono liberamente disponibili
` possibile inoltre prelevare l’intero pacchetto per la
ed installabili dall’utente. E
lingua italiana (che localizza anche l’interfaccia utente).
Il programma integra inoltre un client per Google Scribe (oggi non pi`
u funzionante), discusso rapidamente nel seguito. Gli autori non si assumono nessuna respon4
ChewingWord – http://chewingword.wikidot.com/
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
38
Figura 3.1: Screenshot di Chewing Word mentre si sta cercando di inserire la paro` stato scelto il prefisso “per” dal suggerimento di ChewingWord
la “permette”. E
che proporrebbe “Personaggio”.
sabilit`a sulla qualit`a e continuit`a 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.
5
DiCOM `e prelevabile gratuitamente dall’indirizzo: http://recit.cssamares.qc.ca/
IMG/zip/DICOM-2.zip
39
Principali prodotti destinati all’utente finale
`
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 verit`a 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 pi`
u frequentemente utilizzati in base alla radice immessa.
Anche in questo caso il software non `e in grado di determinare la tipologia di controllo focalizzato dall’utente, dunque non sarebbe in grado di determinare 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 difficolt`a 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 gi`a scritto ed il cursore;
6
Farfalla Editor pu`
o essere testato online all’indirizzo http://www.farfalla-project.
it/demo/
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
40
Figura 3.2: L’editor Web Farfalla. Nell’immagine `e possibile distinguere chiaramente 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 pu`o anche notare la staticit`a del dizionario di predizione che, ad ogni spazio
(ad ogni inizio parola), senza avere alcuna lettera a disposizione per effettuare la
predizione suggerisce “ciao” (quale parola pi`
u probabile).
• La finestra di suggerimento, che suggerisce un completamento per la parola
che si sta scrivendo;
` possibile spostarsi fra le
• La tastiera virtuale, contenente tutte le lettere. E
lettere mediante le frecce destra e sinistra e confermare l’inserimento di una
lettera mediante la freccia gi`
u;
• Le istruzioni e suggerimenti per l’utilizzo;
Ogni qualvolta viene inserita una lettera (o viene scelta la parola come completa-
41
Principali prodotti destinati all’utente finale
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 pi`
u 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 sistema offriva un predittore disponibile in moltissime lingue che sfruttava il corpus
gi`a 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 pi`
u alcun riferimento 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 qualit`a delle predizioni offerte dal sistema.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
42
Esso infatti era basato sul contesto e probabilmente sui modelli linguistici (accennati 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 qualit`a molto elevata.
Purtroppo, non essendovi pi`
u interesse o motivo per mantenere attivo il servizio esso `e stato chiuso prima che potessimo impiegarlo per effettuare dei test
comparativi.
I due software che presenteremo di seguito sono gli strumenti pi`
u apprezzati 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 funzionalit`a 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
gi`a con dizionari di parole sia per usi generici che per usi specifici. L’assor7
Co-Writer – http://www.donjohnston.com/products/cowriter/index.html
43
Principali prodotti destinati all’utente finale
timento `e davvero ricchissimo e consente di operare anche con pi`
u 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 ci`o sono individuate le forme verbali pi`
u opportune all’interno della frase
che vengono ordinate nella lista dei termini pi`
u in alto rispetto alle altre.
La predizione avviene mediante una finestra a scomparsa che si colloca nelle
` possibile scevicinanze del punto di inserimento in cui `e presente il cursore. E
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 possibile 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 ci`o che riguarda
gli strumenti per lo studio.
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
44
Read&Write8 `e un prodotto commerciale supportato dai principali produttori di
software.
Non abbiamo avuto modo di eseguire test ma da ci`o che abbiamo potuto leggere
sia all’interno della documentazione che all’interno delle comparazioni sembra il
sistema pi`
u stabile ed utile a persone con difficolt`a 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 funzionalit`a, sia legate alla lettura che
legate alla scrittura.
Esempi di funzioni che aiutano gli utenti nell’attivit`a di lettura sono la possibilit`a
di lettura continua e guidata dei PDF, strumenti per lo studio (evidenziazione,
aggiunta di commenti ecc.), la possibilit`a di leggere libri parlati per dislessici e
non vedenti nel formato DAISY, la disponibilit`a 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, pu`o essere impiegata durante la digitazione. Ad esempio `e possibile leggere l’intera schermata
oppure configurare Read&Write perch´e pronunci ogni parola dopo che questa `e
stata inserita in un editor.
Gli strumenti per la scrittura sono davvero molti. Si integra perfettamente con i principali editor per Windows e per Mac OS ed offre funzionalit`a simili
a quelle presenti in Co:Writer. In pi`
u, rispetto a quest’ultimo, presenta l’inserimento 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.
8
Read&Write
Readwrite
di
TextHelp
http://www.texthelp.com/UK/Our-products/
45
Principali prodotti destinati all’utente finale
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 et`a 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` possibile scegliere il termine da
stra a scomparsa alla posizione del cursore. E
inserire, all’interno della lista, mediante click, mediante combinazione tasti ma
non `e presente la possibilit`a di utilizzo dei sistemi a scansione. Questo `e dovuto
probabillmente al fatto che questo prodotto `e rivolto in particolar modo a persone con DSA (disponendo anche molti strumenti di supporto alla lettura ed allo
studio).
Definizione del problema, terminologia e Stato Dell’Arte dei sistemi di
Predizione
46
CAPITOLO 4
Predizione basata sui Modelli del Linguaggio
4.1
Introduzione
Nello scorso capitolo abbiamo illustrato le varie modalit`a in cui viene
svolta la previsione delle parole. Abbiamo dato una definizione formale del problema, abbiamo mostrato come l’ordinamento delle parole all’interno della lista
dei termini sia centrale per giudicare la qualit`a di un sistema di predizione. Sono poi stati illustrati alcuni esempi di sistemi di predizione, sia commerciali che
gratuiti. Abbiamo notato che gli strumenti pi`
u 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 qualit`a. Contestualmente, negli esempi e nelle definizioni, cercheremo 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
qualit`a 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 probabilit`a 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
possibilit`a di formalizzare il problema della previsione delle parole descrivendolo
come la capacit`a di predire una parola wn date le N − 1 parole precedenti. Un
modello del linguaggio (o modello ad n-grammi) `e una distribuzione di probabilit`a
sulle possibili sequenze di termini.
Facciamo un esempio:
Esempio 4.1. In un modello del linguaggio italiano, addestrato su testi di narrativa per l’infanzia c’`e una possibilit`a non nulla di trovare una sequenza del
tipo:
[...]nel cielo azzurro dove volano i gabbiami[...]
La probabilit`a 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 suddividere 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 documenti impiegati per l’addestramento del modello del linguaggio. Sar`a in base
a questi documenti che il nostro modello calcoler`a le probabilit`a delle sequenze di termini. Maggiore `e il numero di documenti destinato a questo
compito, meglio il modello si former`a rispetto all’insieme di documenti che
vogliamo valutare;
Test set: Questo insieme di documenti `e quello che fa uso del linguaggio. Solitamente `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 quantit`a di dati pu`o essere utile. Ci potr`a 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 pi`
u modelli) pu`o risultare utile
nello svolgimento di una gran quantit`a di compiti come la correzione automatica 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 pi`
u 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 probabilit`a:
Predizione basata sui Modelli del Linguaggio
P (wn |w1 , . . . wn−1
50
(4.1)
Prima di procedere per`o `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 unit`a 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 considerate;
• 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 necessit`a dell’approssimazione: Gli N-grammi
Per definire la funzione di probabilit`a in equazione 4.1 possiamo fare uso
della formula di base per il calcolo della probabilit`a condizionata.
P (B|A) =
P (A ∩ B)
P (A)
51
La necessit`a dell’approssimazione: Gli N-grammi
In particolare potremmo ottenere la probabilit`a 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 probabilit`a condizionata 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 probabilit`a come:
P (t|c1 . . . cn ) =
C(c1 , . . . , cn , t)
C(c1 . . . cn )
• Infine si ordinano in base alla probabilit`a decrescente;
Formalmente, come abbiamo detto, un modello del linguaggio viene utilizzato per prevedere la probabilit`a di una sequenza di termini. Adottando un
modello di questo tipo potremmo dire che
Predizione basata sui Modelli del Linguaggio
52
P (< s > La minestra `e nel piatto) =
P (La| < s >) · P (minestra| < s > La) · . . . · P (piatto| < s > La minestra `e nel )
In generale la probabilit`a di avere una sequenza w1 , . . . , wn sar`a data da:
P (w1 , ..., wn ) =
n
Y
P wk |w1k−1
(4.3)
k=1
Il problema, come intuibile, risiede nel fatto che pi`
u si allunga la sequenza
(pi`
u 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 probabilit`a dall’intera sequenza del
contesto, semplicemente all’ultimo stato “visitato”. A questo punto possiamo
calcolare la probabilit`a 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 pu`o approssimare
il modello del linguaggio di base.
` possibile formalizzare questo concetto in modo generico. Dato N il
E
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 ) =
n−1
P wn |w1n−1 ≈ P wn |wn−N
+1
(4.5)
n−1
Dove P (wn |wn−N
o essere stimato con la funzione Count sopra
+1 ) pu`
definita quindi:
P
n−1
wn |wn−N
+1
n−1
C wn−N
+1 , wn
=
n−1
C wn−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 qualit`a di un
modello a bigrammi piuttosto che a trigrammi ecc.
La premessa importante da fare `e che, in questo caso, stiamo parlando di valutazione di modelli diversi (a bigrammi, a trigrammi, ma anche pi`
u 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 qualit`a 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
Predizione basata sui Modelli del Linguaggio
54
pu`o valutare la qualit`a impiegando, all’interno dell’applicazione, i diversi
modelli da confrontare;
` costituito da una metrica, da una misura. Esso `e assai
Metodo intrinseco: E
pi`
u generico ma `e pi`
u rapido da utilizzare.
La misura intrinseca per la valutazione di un modello linguistico `e la perplexity
(tradotto in italiano con “perplessit`a”) di cui discuteremo in seguito nel paragrafo
4.5.2.
Prima di ci`o, dato che questo lavoro riguarda in modo particolare i sistemi
di predizione, vogliamo proporre un approccio, adottato nel seguito per valutare
la qualit`a del nostro applicativo.
4.5.1
Valutazione estrinseca mediante i sistemi di predizione
Al fine di poter valutare la qualit`a della predizione di diversi modelli del
linguaggio `e possibile adottare diverse misurazioni.
In primo luogo si pu`o 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:
55
Valutazione di un modello
1 oltre
2 oggi
3 ogni
(a)
1 passa
2 pare
3 penso
(b)
Figura 4.1: (a) immagine della lista di parole con relativi rank della previsione
di “oggi” dato “o”. (b) La lista di parole con relativi rank della previsione di
“piove” dato “p”
|R|
1 X 1
MRR =
|R| k=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 restittuir`a 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 pu`o 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 qualit`a di differenti modelli.
Il problema sorge poich´e questa tecnica non permette di rispecchiare la
reale necessit`a di un software di predizione delle parole. Infatti nel momento in
Predizione basata sui Modelli del Linguaggio
56
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 semplicemente 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
affinch´e 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 per`o 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 pi`
u 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 “dicendo”. Scriver`a 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
57
Valutazione di un modello
lettere ed il tasto di selezione. L’utente ha risparmiato 3 battiture.
In seguito alla parola “dicendo” l’utente vuole scrivere “di”. Inizia quindi scrivendo 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].
` possibile utilizzare altre modalit`a di valutazione pi`
E
u 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 difficolt`a 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 qualit`a 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 pi`
u
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
Predizione basata sui Modelli del Linguaggio
58
meglio i dettagli dei dati di test).
` possibile misurare la predizione migliore osservando la probabilit`a che viene
E
assegnata da un modello ai dati di test. Il modello migliore `e quello che assegna
una probabilit`a pi`
u alta a questo tipo di dati.
Come spiegato anche in [HT09], si definisce la misura della perplexity
(o P P in formula) di un modello del linguaggio su un insieme di test, la funzione
di probabilit`a 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 pu`o essere riscritta come in equazione 4.9.
1
P P (W ) = P (w1 , w2 . . . wn )− n
s
=
n
1
P (w1 , w2 , . . . wn )
v
u
u
= u
n
n
Q
t
1
(4.8)
(4.9)
(4.10)
P (wk |w1 , . . . , wk−1 )
k=1
` possibile ottenere la 4.10 applicando l’equazione 4.3.
E
Come abbiamo detto, nel caso degli N-Grammi si pu`o avere una approssimazione. Il contenuto del denominatore nella formula 4.10 verr`a 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
v
u
u
u
u
n 
P Pbigram (w1 , . . . wn ) = u
n
t Q

1
P (wk |wk−1 )



k=1
Come si pu`o notare dalle equazioni 4.9 e 4.10, la probabilit`a calcolata appare
sempre al denominatore della frazione. Questo porta ad affermare che maggiore
`e la probabilit`a, minore `e la misura della perplexity.
Dall’intuizione descritta in precedenza, quindi, il modello migliore `e quello
con una misura di perplexity pi`
u bassa. Per [HT09], infatti, minimizzare la
perplexity `e equivalente a massimizzare la probabilit`a 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). Ci`o va per`o
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
pu`o 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.
Predizione basata sui Modelli del Linguaggio
60
Si `e visto che mano a mano che li numero N aumentava (aumentavano le
parole da cui dipendeva la probabilit`a 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, potremmo dire in maniera generica che pi`
u grande `e N (pi`
u ci guardiamo indietro all’interno del contesto), pi`
u la nostra predizione sar`a esatta a patto che una frase
simile, a quella che vogliamo scrivere compaia nel corpus di addestramento.
Ci`o per`o 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 pi`
u probabile che succede alla precedente. Al contrario, se scegliamo un N
troppo grande rischiamo di non avere la possibilit`a di predire nulla, poich´e non `e
detto che la frase che vogliamo scrivere sia contenuta nel corpus e ci avviciniamo
sempre di pi`
u 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 probabilit`a poich´e delle
sequenze che compaiono raramente nel corpus (che hanno una probabilit`a
bassa) potrebbero essere comunque valide. Oltre a questo c’`e il problema
che nessun corpus `e abbastanza grande per contenere tutte le possibili sequenze, e ci potrebbero essere delle sequenze di parole accettabili che hanno
probabilit`a 0.
Back-off ed Interpolazione : Se una determinata sequenza ha probabilit`a 0
(o molto vicina allo 0), al posto di restituire questa probabilit`a si analizza
l’(N − 1)-gram. Ad esempio, se un trigramma ha una probabilit`a di 0 (o
molto bassa) si passa ad analizzare il bigramma costruito sulle ultime due
61
Miglioramenti del modello: Smoothing e Back-Off
componenti del trigramma. Parlando in maniera generale possiamo dire
che “dimentichiamo” una parte del contesto.
Un ultimo problema `e quello dell’underflow. Poich`e la probabilit`a di una
sequenza di parole `e data dal prodotto delle probabilit`a, 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 probabilit`a, 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 probabilit`a dalle sequenze pi`
u probabili verso quelle meno frequenti nel
corpus di test (o a probabilit`a 0). Questo, come detto, `e utile per evitare che
sequenze di parole perfettamente lecite risultino avere probabilit`a nulla.
Un altro problema delle sequenze a probabilit`a 0 `e quello della misura di
Perplexity. Come riportato in [HT09], la definizione data di Perplexity richiede
che venga calcolata la probabilit`a di ogni frase nell’insieme di test. Ma se una
frase ha un N-Gram che non appare (poich´e la probabilit`a viene moltiplicata)
essa risulta avere probabilit`a 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 ) =
Add-one → P (wk ) =
ck
n
ck + 1
n+V
Predizione basata sui Modelli del Linguaggio
62
Ci`o per`o aumenta troppo le probabilit`a 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 cardinalit`a `e I), in base alla loro occorrenza. Ad
esempio definisce l’insieme di cardinalit`a 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 smoothing 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 pi`
u volte il nuovo contatore `e
definito come c∗ = (c + 1) Ic+1
. Se invece l’N-Gramma compare 0 volte
Ic
`e necessario sostituire l’intera probabilit`a. Ad esempio (per mantenere le
convenzioni di lettere), nel caso gli 1-grammi
PGT (termine occorra 0 volte) =
I1
n
[HT09] riporta che lo smoothing cos`ı ottenuto `e molto pi`
u 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 pi`
u moderne, secondo 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].
63
Miglioramenti del modello: Smoothing e Back-Off
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 probabilit`a 0 poich´e essa non `e contenuta nel training corpus. Ad esempio il corpus non contiene alcuna occorrenza
de “`e nel piatto” quando vogliamo valutare P (piatto|`e nel). Magari per`o il nostro corpus contiene un trigram del tipo “sono nel piatto”. Vorremmo poter
ricalcolare la probabilit`a ed analizzare i bigrammi (“nel piatto”).
Esistono due modi distinti per fare ci`o
• Back-off, come riportato da [HT09], si torna indietro all’N-Gramma precedente soltanto se la probabilit`a della sequenza `e 0;
• Interpolazione, si mescolano sempre le probabilit`a derivanti dalle diverse
stime di N-Grammi (dalla massima alle minori).
L’interpolazione consiste nell’assegnare dei coefficienti moltiplicativi (definiti in [HT09] come λ) alle varie probabilit`a di ciascuna classe di N-grammi che
viene combinata. Riprendendo l’esempio precedente, verranno sommate le probabilit`a di unigrammi, bigrammi e trigrammi. Ad ognuna di queste probabilit`a
verr`a 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 probabilit`a finale
minore di 1. Una seconda possibilit`a `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 pi`
u piccoli fino a quando si raggiungono
gli unigrammi oppure fino a quando si trova una probabilit`a maggiore di 0. Ad
ogni passo vengono aggiunte delle costanti che variano a seconda della tecnica
Predizione basata sui Modelli del Linguaggio
64
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 modelli 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 pu`o rappresentare solo il primo passo. Riteniamo per`o che esso sia
indispensabile per la costruzione di un predittore di buona qualit`a.
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 gi`a abbiamo sottolineato in queste pagine, l’estrema
fragilit`a delle applicazioni se utilizzate in domini differenti da quelli dei documenti
di training. In aggiunta, come viene riportato da [Ros00], questa fragilit`a 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 modelli del linguaggio vengono spesso sottoposti a delle assunzioni di indipendenza,
ad esempio nel caso di un modello ad N-Grammi si presuppone che la probabilit`a
di una parola in una frase dipenda soltanto dalle precedenti (n − 1) parole. Eppure, 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 dar`a 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 influenzer`a 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. Ci`o presenta dei problemi in quanto le varie forme dei verbi, i diversi
tempi e modi, portano ad una sparsit`a dei dati partendo da qualnuque corpus
letterario.
Una possibile soluzione proposta in [ACD+ 07] `e l’utilizzo di tecniche combinate. 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 combinazione lineare fa uso di trigrammi POS (un language model costruito sul POS
anzich´e 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 secondo modello ad n-grammi basato su parole opportunamente taggate [ACD+ 07].
L’ultimo problema che riportiamo, evidenziato in [WA07] `e la difficolt`a
nell’adattamento di un predittore basato soltanto su modelli del linguaggio ad un
contesto di utilizzo che pu`o 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 language model utilizzando l’LSA. Molte sono le tecniche descritte in cui viene interpolato il risultato derivante dall’LSA con le predizioni ottenute dai language
Predizione basata sui Modelli del Linguaggio
66
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 fanno 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 scrittura facilitata di testi adatto a persone con disabilit`a 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 semplicit`a 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’algoritmo di predizione;
• La costruzione dell’interfaccia per i motori di predizione (IPredictor) e l’implementazione della classe del predittore basato sui modelli del linguaggio
(NGPredictor);
• L’implementazione di IPredictor per costruire un motore di predizione basato su Google Scribe (GSPredictor);
• La costruzione dell’interfaccia grafica e dell’editor (il PredictEdit);
• La costruzione dell’interfaccia integrata con altre applicazioni (PredictiOndemand)
Il linguaggio di programmazione per lo sviluppo dell’applicativo (PredictEdit, PredictiOnDemand e Predictors) `e stato Microsoft Visual C# con librerie
Microsoft .NET versione 3.5 (in modo da garantire la compatibilit`a anche con il
passato Windows 2k). Si `e comunque mantenuta una completa compatibilit`a 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
5.2
Sviluppo del modello del linguaggio
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
dovr`a riuscire ad accedere ai dati nel modo pi`
u rapido e logico possibile.
Nel progettare tale struttura terremo conto di requisiti di memoria e di rapidit`a
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 pu`o modificare il modello che rimane quindi statico.
Le statistiche del modello non vengono modificate dai testi che, giorno per giorno,
l’utente scriver`a.
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
semplicit`a.
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 documenti fra training set e test set. Come training set abbiamo scelto tutti i
Il sistema di scrittura facilitata PredictEdit
70
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 corpus.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 ci`o che si trova fra parentesi quadre,
tonde ed angolari;
• Il testo viene tokenizzato manualmente. La punteggiatura viene “spaziata” 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 pu`o significare sia aperte che chiuse virgolette. Le aperte virgolette vengono convertite in ’’, mentre le chiuse restano ¨. Tale funzione
verr`a impiegata per usi futuri ma ci sembrava utile partire da un corpus
processato al meglio delle nostre possibilit`a.
• Sono eliminati i \n. Le parole ., ?, !, :, le chiuse virgolette seguite da un
punto e le chiuse virgolette precedute da un punto vengono considerati fine
71
Sviluppo del modello del linguaggio
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).
• Poich´e `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 ambiguit`a della lingua inglese (o italiana), abbiamo
ritenuto comunque interessante procedere alla costruzione di un modello. Proprio
perch`e 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].
Il sistema di scrittura facilitata PredictEdit
72
Inizialmente si era impiegato il CMU toolkit ma, poich´e esso risulta non sviluppato da diverso tempo e non comprende tecniche di smoothing moderne (come il
Kneser-Ney), si `e pensato di impiegare il pi`
u recente SRI LM Toolkit (SRILM).
Per prima cosa, come detto, viene costruito il vocabolario a partire dal
file di corpus. Per fare ci`o 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 manualmente 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 sconosciuti (<unk> ma vengano semplicemente ignorati in ogn N-Gramma;
Con pi`
u di un N-Gramma: Nel nostro caso abbiamo utilizzato un modello
a 4-Grammi
Con Smoothing: (Kneser-Ney) affinch´e tutte le parole all’interno del vocabolario abbiano una probabilit`a maggiore di 0 di comparire e perch´e il valore
di probabilit`a venga “normalizzato”. Ci`o `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 vogliamo che i 4-Grammi, ove presenti, mantengano le loro probabilit`a originali
(opportunamente aggiustate mediante smoothing). Indispensabile `e invece
73
Sviluppo del modello del linguaggio
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 probabilit`a. 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 pi`
u grande di
100MB pu`o risultare lenta. Gli accessi che dovremmo fare sono davvero molti.
` quindi necessario pensare ad una struttura in grado di ospitare il
E
modello del linguaggio e di restituirne i dati in maniera semplice e veloce.
Il sistema di scrittura facilitata PredictEdit
74
I primi tentativi che abbiamo svolto sono stati di inserire l’intero modello
del linguaggio in memoria. In tal modo per`o 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 pi`
u 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
probabilit`a;
• ng2(rowId,w1,w2,p,b) – Contiene le sequenze di bigrammi con le loro
probabilit`a;
• ng3(rowId,w1,w2,w3,p,b) – Contiene le sequenze di 3-grammi con le
loro probabilit`a;
• ng4(rowId,w1,w2,w3,w4,p,b) – Contiene le sequenze di 4-grammi
con le loro probabilit`a,
In cui w1,w2,w3,w4 rappresentano i rowId delle varie parole, p rappresenta la probabilit`a della sequenza (dell’n-Gramma) mentre b rappresenta
una probabilit`a aggiuntiva utile per il calcolo del back-off.
75
Sviluppo del modello del linguaggio
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.
Ci`o 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 pu`o essere
impiegato senza nessuna difficolt`a 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 perch´e,
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 sar`a 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 verr`a
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 gi`a
implementato in automatico da SQLite.
Il sistema di scrittura facilitata PredictEdit
5.3
76
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 PredictEdit). Tale progetto viene incluso in quello del PredictEdit sottoforma di
libreria (DLL).
I motori di predizione devono implementare l’interfaccia IPredictor che garantisce
uniformit`a di metodi e di comportamento.
5.3.1
L’interfaccia IPredictor
L’interfaccia IPredictor contiene soltanto un metodo ed una Propriet`a
(Property). La propriet`a `e PredictionSize e stabilisce la dimensione della
lista parole che il predittore dovr`a 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 processamento del corpus, sono aggiunti i simboli di inizio frase, eventualmente il
vettore contenente il contesto viene ingrandito (ad esempio se esso conteneva qualche carattere di punteggiatura che diventer`a una parola a se stante),
vengono applicate le stesse modifiche gi`a 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 probabilit`a modificata (viene aggiunto il back-off).
5. Si ordinano i primi k elementi (dove k `e PredictionSize) in base alle loro
probabilit`a 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 sistema di scrittura facilitata PredictEdit
78
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 risulter`a pi`
u semplice comprendere le migliorie. L’utente la prima volta passer`a all’algoritmo “La minestra `e
nel p”.
L’algoritmo osserva il contesto, “minestra `e nel” e la radice “p” (4 parole perch´e
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 inferiore alla PredictionSize.
Si pu`o ancora tornare indietro e si procede al back-off. Considerando semplicemente “`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 probabilit`a (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 per`o osserviamo che il contesto `e rimasto invariato e che la radice
79
Sviluppo dei motori di predizione
inizia con la radice precedente. Possiamo quindi gi`a produrre la lista dei termini
provenienti dai quadrigrammi e dai trigrammi che inizia con “pi”, dato il contesto,
senza la necessit`a di interrogare il database.
Infatti se prima abbiamo richiesto ed ordinato tutti i termini dei quadrigrammi 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 probabilit`a 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 probabilit`a. Il
procedimento continua fino a quando il contesto non `e pi`
u uguale al precedente
o la radice salvata non `e pi`
u 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 probabilit`a 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.
Il sistema di scrittura facilitata PredictEdit
80
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 sequenze 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 probabilit`a.
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 procede alla ricerca sul database ed al back-off. I nuovi termini vengono
aggiunti alla lista e questa viene riordinata in base alle probabilit`a.
6. Vengono restituiti, al pi`
u, i primi k elementi della lista, con k = P redictionSize.
Per i dettagli implementativi si rimanda al codice, `e importante per`o
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 probabilit`a (con il back-
81
Sviluppo dei motori di predizione
off gi`a 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 ngrammi disponibili nel database SQLite. Ci`o potr`a 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 automatiche, avevamo proceduto a costruire un client Google Scribe che implementasse
l’interfaccia IPredictor.
Si `e descritto GoogleScribe all’interno del paragrafo 3.5.7.
Il sistema di scrittura facilitata PredictEdit
82
Purtroppo, come abbiamo detto, questo prodotto non `e stato pi`
u 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 poich´e 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 maniera 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 pi`
u di 40 caratteri. Tuttavia questo
non costituiva un problema in quanto, come riportato in
1
la parola considerata
la pi`
u lunga in lingua italiana `e costituita da meno di 30 caratteri.
Non sapendo esattamente come fosse svolto il processo di predizione era impossibile 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 contesto. Si ricercava, quindi, il primo carattere di spazio (per evitare di passare al
1
Vocabolario
Treccani
precipitevolissimevolmente/
http://www.treccani.it/vocabolario/
83
Sviluppo dell’editor PredictEdit
server finali di qualche parola). Veniva quindi inviata nella richiesta la sottostringa 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
` stato quindi implementato un editor, il PredictEditor
renda semplice l’impiego. E
che contenesse anche una funzionalit`a 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
Il sistema di scrittura facilitata PredictEdit
84
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 men`
u, 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 pi`
u
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 predittore propone. Esso viene aggiornato ogni volta che il testo, all’interno della
finestra principale, viene modificato.
Come si pu`o 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 funzionalit`a molto importante poich´e non `e detto che un utente voglia sempre aggiungere parole a fine testo. Per essere implementata essa richiede,
oltre all’analisi del contesto (i termini precedenti alla radice), anche il tracciamento in tempo reale della posizione del cursore. Data la posizione del cursore,
si prender`a in considerazione il testo che lo precede, ignorando il successivo. Tale
porzione di testo sar`a poi passata al motore di predizione che fornir`a la lista dei
termini che popolano la Word List.
85
Sviluppo dell’editor PredictEdit
Figura 5.1: Finestra del PredictEdit in cui si vede l’immissione della parola “strumento” inserita fra altre due parole. L’utente sta procedendo cliccando sopra alla
parola desiderata all’interno della lista. Si vedono inoltre i font personalizzati sia
della 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, pu`o immettere uno dei termini suggeriti semplicemente cliccandoci sopra o premendo il pulsante relativo con il mouse.
` anche possibile utilizzare le combinazioni di tasti in due modi:
E
• Il modo tradizionale di Windows, portandosi sulla finestra dell’elenco termini (Word List) mediante la combinazione tasti CTRL+TAB quiindi spo-
Il sistema di scrittura facilitata PredictEdit
86
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 finestra 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 modalit`a di immissione, che non richiedono di richiamare esplicitamente la finestra “Word List”, poich´e 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’interno della Word List `e presente il termine desiderato, legge il numero relativo e
preme l’opportuno pulsante.
Tale molteplicit`a di sistemi di immissione `e stata sviluppata in modo da
venire incontro alle esigenze di utenti con difficolt`a 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 ridottache fanno uso, appunto, di tastiere ridotte. Il sistema a tastierino numerico,
invece, `e indicato per persone con mobilit`a ridotta ma con una buona escursione
che fanno uso di tastiere standard o con scudo.
87
Sviluppo dell’editor PredictEdit
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 possibilit`a
di cliccare, oltre che sul pulsante numerato, anche sul testo della parola che si
vuole inserire, rende pi`
u 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 mediante uno schermo a tocco. Si possono immettere le singole lettere mediante la
tastiera 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 software non presenta alcun problema particolare. Il sistema non `e invece predisposto
per l’utilizzo di strumenti di selezione a scansione.
Alcune funzionalit`a sono poi state aggiunte in modo da rendere pi`
u agevole l’impiego del PredictEdit.
Il sistema di scrittura facilitata PredictEdit
88
` possibile scegliere il motore di predizione (fra quelli implementanti l’interfaccia
E
IPredictor) mediante l’apposita funzione di men`
u. Questo ci ha consentito, durante la valutazione dell’interfaccia utente, di lasciare alle persone la scelta se utilizzare l’NGPredictor o il predittore di Google Scribe (ora non pi`
u
funzionante).
I font, come detto sono completamente personalizzabili e la finestra di
predizione riadatta le proprie dimensioni nel caso il carattere sia troppo grande
` possibile inoltre, sempre tramite il men`
e le parole vengano tagliate. E
u, personalizzare il colore del testo e dello sfondo nella finestra di predizione. Questo
permette di lavorare in maniera pi`
u confortevole anche a persone con particolari
disturbi visivi.
Un’ulteriore caratteristica della word list `e la sua capacit`a 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 difficolt`a degli utenti ai quali il software si rivolge.
Spesso, infatti, pu`o risultare difficile l’impiego del mouse per spostare una finestra.
` molto pi`
E
u 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 flessibilit`a della
finestra di predizione. Anche se al momento non `e data all’utente alcuna possibilit`a di modifica del numero di voci in essa contenute, questa funzionalit`a `e
molto facile da implementare poich´e 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
5.5
Il PredictiOnDemand
Il PredictiOnDemand
Il PredictEdit `e sicuramente un software destinato ad evolvere e a miglio-
rare offrendo agli utenti molte nuove funzioni, adatte alle specifiche necessit`a, che
potranno aumentare nel tempo.
L’esigenza di molte persone per`o `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 potenzialit`a 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 gi`a disponibile all’interno del PredictEdit in moltissime applicazioni
Windows. Gi`a ora sono supportate parzialmente o totalmente alcuni fra i pi`
u noti
programmi Windows come Microsoft Word, WordPad, Blocco Note e Firefox.
Il PredictiOnDemand `e rivoluzionario perch´e non assilla l’utente con finestre 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, sviluppati per consentire l’utilizzo in maniera ottimale di una singola applicazione,
sia di adeguarsi al controllo focalizzato al momento, mediante le API standard
dell’accessibilit`a UIAutomation [Mica].
Al momento, l’unico modulo specifico disponibile `e stato sviluppato per Microsoft
Word, il pi`
u utilizzato elaboratore di testi in ambiente Windows.
Questa innovazione consente di arricchire l’esperienza d’uso di chi desidera la predizione con gli altri importanti servizi gi`a presenti in editor di testi
molto evoluti. Ad esempio `e possibile impiegare il predittore all’interno di Microsoft Word, che contiene uno straordinario strumento per la segnalazione e la
correzione degli errori ortografici e grammaticali.
Il sistema di scrittura facilitata PredictEdit
90
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 UIAutomation in combinazione con la tecnica dei System hooks [Micc].
Tutto ci`o consente di intercettare controlli, eventi e processi estranei alla nostra
applicazione. Per presentare in modo ordinato le varie funzionalit`a abbiamo deciso 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 compatibilit`a con molte applicazioni Windows. Infine illustreremo il funzionamento e la gestione della finestra mobile di predizione, le varie modalit`a di
immissione dei termini ed alcune peculiarit`a 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 pi`
u semplicemente hook) sono registrati ed ottenuti mediante 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 pulsante 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 rilasciato. Gli Hook funzionano a catena. Quando un hook `e terminato pu`o
91
Il PredictiOnDemand
decidere di passare (o meno) l’evento che ha intercettato all’Hook successivo. A meno che non abbia impostato anch’essa un hook, la finestra in
primo piano rappresenta l’ultimo anello della catena.
` quindi possibile “consumare” un evento in modo tale che non arrivi mai
E
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 compiti 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 intercettare ed interagire con il contenuto dello schermo. I due oggetti pi`
u 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 riguardano comportamenti che avvengono all’interno dell’applicazione ma,
` possibile, ad esempio,
invece, comportamenti che avvengono all’esterno. E
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
Il sistema di scrittura facilitata PredictEdit
92
RootElement (che `e un AutomationElement) `e sempre il desktop. I suoi
figli sono le applicazioni aperte, nel nostro caso quindi, solo la nostra applicazione. L’applicazione viene identificata come finestra (Window). La
Window avr`a 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 informazioni comuni a tutti gli elementi oppure, per svolgere delle azioni `e possibile
ottenere uno o pi`
u AutomationPattern. In base alla tipologia del controllo
esso potr`a 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’icona oppure premere due volte il tasto Control sulla tastiera. Questa seconda
modalit`a, rivolta in particolar modo ad utenti con difficolt`a nell’utilizzo del mouse, `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 sar`a 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
93
Il PredictiOnDemand
control comparir`a la finestra di elenco parole, altrimenti comparir`a un messaggio che informa l’utente della impossibilit`a di svolgere la predizione.
Al successivo AutomationFocusChangedEvent, se la finestra di predizione `e aperta, 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 componenti testuali o personalizzare le modalit`a con cui i dati vengono letti o scritti
all’interno dell’applicazione. Per questo `e stata sviluppata una struttura a moduli (contenuta all’interno del namespace PredictiOnDemand.appModules.
Ogni modulo corrisponde ad un processo, il modulo si occupa di garantire la
qualit`a 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 propriet`a
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) serve nel caso in cui l’applicazione contenga diversi componenti per stabilire all’interno di quali sia possibile o meno svolgere la predizione. Ad
Il sistema di scrittura facilitata PredictEdit
94
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 propriet`a SupportedVersion che serve a stabilire quale sia la versione 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 caratteristiche:
• 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 bisogno di altri interventi nel codice. Essi possono anche essere aggiunti come referenza esterna (Assembly .NET Dll) purch´e 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 delle 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` quindi possibile immettere testo non solo
ganciando il punto di inserimento. E
95
Il PredictiOnDemand
al termine del documento ma anche nel mezzo. Per maggior comodit`a vengono
tenuti in considerazione soltanto gli ultimi 150 caratteri antecedenti alla posizione del cursore. Questo perch´e, molto spesso, un documento di Word `e composto
da diverse pagine. Risulterebbe del tutto inutile, quindi, appesantire l’applicativo “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 pi`
u 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 controlli standard di Windows. Questo consente un immediato accesso di base anche
in assenza di moduli specifici. Ci`o pu`o essere svolto grazie alle API per l’accessibilit`a 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 modulo 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’interno del PredictEdit, o come nel modulo per Microsoft Word. Viene individuata
2
TextPattern – http://msdn.microsoft.com/en-us/library/system.windows.
automation.textpattern.aspx
Il sistema di scrittura facilitata PredictEdit
96
la posizione del cursore e la stringa passata all’applicativo `e il testo antecedente
` possibile quindi inserire il testo anche all’interno del documento o
ad esso. E
dell’area di testo senza troppe difficolt`a.
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 applicativo 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 funzionalit`a di predizione, il PredictiOnDemand si rifiuta di
mostrare direttamente la finestra di WordList, esso presenta invece un avviso per
informare che la previsione pu`o essere effettuata soltanto al termine dell’area di
testo e non all’interno. L’utente pu`o 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 f`a 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. Qualora 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’interno della WordList) `e creato internamente al PredictiOnDemand utilizzando gli
hook. Poich´e non esiste, n´e all’interno delle API di Microsoft Office Automation,
n´e 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-
97
Il PredictiOnDemand
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 alfabetico (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 pu`o 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 dovr`a riportarsi nella finestra principale dell’applicativo in uso. Questo verr`a 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.
Il sistema di scrittura facilitata PredictEdit
98
Alcune particolarit`a sono state sviluppate per evitare possibili problemi
e migliorare l’esperienza d’uso:
• Se il cursore si trova in una met`a dello schermo la finestra di predizione `e
sempre nell’altra met`a. In questo modo si evita che la finestra possa sovrapporsi al cursore stesso. Ci`o 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
` possibile modello sfondo, del testo e nel tipo e dimensione dei caratteri. E
dificare queste impostazioni grazie al men`
u 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 chiuder`a automaticamente per evitare problemi. E
possibile sempre richiamarla attraverso le modalit`a 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 poich´e
questo servizio ha smesso di funzionare durante la stesura di questo lavoro.
99
Il PredictiOnDemand
(a)
(b)
Figura 5.3: (a) La predizione in Microsoft Word. Viene inserito il termine “definire” all’interno del testo. Il tondino giallo rappresenta il click del mouse o dello
strumento di puntamento. I caratteri e i colori sono personalizzati. (b) Messaggio
di 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.
Il sistema di scrittura facilitata PredictEdit
100
(a)
(b)
Figura 5.4: (a) Il messaggio che avvisa l’utente di essere all’interno di un campo
editazione supportato soltanto quando il cursore si trova a fine stringa. (b) La
predizione durante l’uso del servizio online “Google Translator”. L’utente sta
per inserire la parola “previsione” premendo il tasto 1 nel tastierino numerico o
cliccando 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 qualit`a 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 per`o iniziare questo capitolo presentando le misure che abbiamo
utilizzato.
Valutazione del PredictEdit
6.1
102
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 pi`
u 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 gi`a 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 unit`a 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 pi`
u di tre caratteri). Questo presenta dei vantaggi, come spiegato nel paragrafo 4.5, ma non permette di
renderci conto della qualit`a complessiva del predittore. Nel caso di parole brevi 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 appare invece molto efficiente nel caso di una valutazione dei caratteri risparmiati
sull’intero testo. Per questo, all’interno delle prove automatiche svolte, tale metrica `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.
Valutazione del PredictEdit
6.2
La valutazione manuale
6.2.1
Esperimenti effettuati
104
La valutazione manuale `e stata svolta da due volontari utilizzando l’editor
PredictEdit. Ad ognuna delle due persone, entrambe affette da disabilit`a 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’attivit`a degli utenti, previo il consenso, `e stata tracciata per fini statistici. 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’utente avesse immesso (quanta parte della parola fosse gi`a 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’inserimento 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’analisi che gli utenti, di tanto in tanto, hanno aggiunto qualche lettera prima di
105
La valutazione manuale
` successo pi`
accorgersi della presenza della parola. E
u di una volta che l’utente abbia 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, pi`
u alto `e il valore (pi`
u 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 parole preso in esame `e piuttosto ristretto, questo dato conferma la nostra ipotesi.
Utilizzando un testo a piacere, distante quindi dall’ambito e dal lessico impiegato 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 qualit`a 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 pi`
u brevi? Nell’86% dei casi `e proprio
cos`ı, considerando come brevi le parole di non pi`
u di 3 caratteri. Questo `e un
dato molto utile per studiare futuri miglioramenti.
Come si pu`o vedere dalla figura 6.1(b) anche la misura KS sulle diverse
parole `e piuttosto bassa. Le parole a zero sono aumentate perch´e a molti termini
mancava una sola lettera per essere completati. Non `e per`o affatto male un valore
di 5/81 sui termini completati risparmiando cimque battiture.
Infine in figura 6.1(c) si pu`o vedere la percentuale di completamento rapportata 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 pi`
u 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
Valutazione del PredictEdit
106
predittore quando “capisce” la parola ne completa circa la met`a. 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 possibilit`a 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 funzionalit`a di personalizzazione
dei caratteri e dei colori. In questo modo ora l’utente pu`o decidere di visualizzare
l’elenco parole con una dimensione dei caratteri pi`
u grande ed uno schema colori
di suo gradimento.
Gli utenti, in generale, hanno espresso un parere positivo sul programma, sottolineando la velocit`a 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 pu`o 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
30
35
25
30
20
25
20
15
15
10
10
5
5
0
0
1/2
1/3
1/4
1/5
0
1
0
(a)
1
2
3
4
5
(b)
30
25
20
15
10
5
0
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’analisi
del reciproco del rank. I risultati sono ordinati dai peggiori (non trovato, 10
tentativi, 9 tentativi ecc.) ai migliori (1 solo tentativo) Le barre rappresentano
la frequenza. (b) Analisi della misura KS parola per parola nel testo. Pi`
u ci si
sposta verso destra pi`
u lettere sono state completate per una certa parola. Le
barre rappresentano la frequenza. (c) Analisi della percentuale di completamento
della parola. Le barre rappresentano la frequenza delle parole. Nell’asse delle
ascisse troviamo le varie percentuali. Pi`
u ci si sposta lungo l’asse delle x pi`
u alta
`e la percentuale di parola che viene completata.
Valutazione del PredictEdit
108
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 documento appartiene alla medesima collezione (europarl corpus) di quelli gi`a utilizzati 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”. Poich`e questi non vengono divulgati n´e parzialmente
n´e 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 differente dal modello
Il numero totale di parole processate `e pari a 5400. Ad esse sono stati gi`a
sottratti i caratteri di punteggiatura e le parole di dimensione 1.
Come si pu`o vedere anche dalla figura 6.2(a) i risultati dei reciprocal
rank sono molto soddisfacenti. Ci`o 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. Ci`o 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
109
La valutazione automatica
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 predittore `e riuscito a far risparmiare il 64% nei vari termini. Se estendessimo la
proporzione anche agli spazi, in totale per scrivere l’intero documento sarebbero state necessarie 48010 digitazioni. Considerando quindi tutti i possibili tasti,
utilizzando il nostro tool `e possibile risparmiare durante la digitazione del documento 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 pi`
u. 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 pi`
u 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 pu`o 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.
Valutazione del PredictEdit
110
Anche la percentuale di completamento per parola (visibile in figura
6.3(b)) mostra un sensibile miglioramento in questo documento rispetto al pre` molto frequente, infatti, che le parole vengano completate tra il 50 e
cedente. E
il 69% ma `e ancor pi`
u 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 paragrafo 5.2.1 dovremmo comunque scartare moltissime informazioni strutturate.
Tali dati vengono eliminati in fase di preprocessamento, le punteggiature vengono 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%.
111
La valutazione automatica
2000
1800
1600
1400
1200
1000
800
600
400
200
0
0
1/10
1/9
1/8
1/7
1/6
1/5
1/4
1/3
1/2
1
(a)
1600
1400
1200
1000
800
600
400
200
0
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 di
articoli de “LaStampa.it”. (a) Risultati dell’analisi del reciproco del rank. I
risultati sono ordinati dai peggiori (non trovato, 10 tentativi, 9 tentativi ecc.) ai
migliori (1 solo tentativo) Le barre rappresentano la frequenza. (b) Analisi della
percentuale di completamento della parola. Le barre rappresentano la frequenza
delle parole. Nell’asse delle ascisse troviamo le varie percentuali. Pi`
u ci si sposta
lungo l’asse delle x pi`
u alta `e la percentuale di parola completata dal Predittore.
Valutazione del PredictEdit
112
12000
10000
8000
6000
4000
2000
0
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)
6000
5000
4000
3000
2000
1000
0
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 di
test del corpus europarl. (a) Risultati dell’analisi del reciproco del rank. I
risultati sono ordinati dai peggiori (non trovato, 10 tentativi, 9 tentativi ecc.) ai
migliori (1 solo tentativo) Le barre rappresentano la frequenza. (b) Analisi della
percentuale di completamento della parola. Le barre rappresentano la frequenza
delle parole. Nell’asse delle ascisse troviamo le varie percentuali. Pi`
u ci si sposta
lungo l’asse delle x pi`
u 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 completo 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 garantire la massima qualit`a 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 pi`
u opportuno da immettere.
Viene inoltre implementato un meccanismo di back-off e di smoothing per migliorare la qualit`a del modello di base. Il risultato per`o era di dimensioni molto
grandi, perci`o si `e studiata una struttura di database relazionale su file che coniugasse un risparmio di spazio sul disco con la rapidit`a 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 qualit`a
grammaticale nelle parole che sono proposte all’utente come suggerimento.
Per ci`o 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 pu`o 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 sistema a moduli che rende disponibile il servizio di predizione in tantissime applicazioni Windows.
Il PredictiOnDemand `e rivoluzionario perch´e non assilla l’utente con finestre 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 qualit`a in una singola applicazione (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 pu`o scegliere una delle parole presenti, sia con il mouse che tramite
115
il tastierino. La previsione, in moltissimi casi, pu`o avvenire anche se l’utente
desidera immettere delle parole all’interno di testo gi`a presente e non necessariamente 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 leggibilit`a durante l’impiego del programma.
Dalle valutazioni effettuate abbiamo potuto osservare un’ottima qualit`a
del nostro applicativo che `e in grado di ridurre di pi`
u 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 applicato al motore di predizione: la costruzione dinamica del corpus. Analizzando
i documenti proposti dall’utente sar`a possibile costruire uno (o pi`
u) modelli che
poi potranno essere impiegati per una predizione di maggiore qualit`a.
Inoltre dai test `e emerso che le parole che pi`
u spesso non vengono predette in
tempo sono le pi`
u brevi. Si potrebbero aumentare le probabilit`a delle parole
pi`
u corte, soprattutto quando il predittore sta impiegando gli unigrammi (cio´e
quando non ha trovato alcuna sequenza di parole compatibile con il contesto in
cui l’utente sta lavorando).
Come abbiamo gi`a 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 analizzatore 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 pi`
u appropriato (e quindi contenente termini pi`
u probabili).
Inoltre potrebbe essere implementato un meccanismo di cache in grado di aumentare, in base ad una funzione, la probabilit`a dei termini che sono stati richiesti di
recente.
Spostando poi la nostra attenzione sulle applicazioni lato utente, sarebbe 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 funzionalit`a di
lettura tramite sintesi vocale sia all’interno del PredictEdit, che all’interno del
PredictiOnDemand. Esse sono piuttosto semplici da realizzare poich´e l’applicativo 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
pu`o 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 aperta e che il lavoro fin’ora fatto ci d`a 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. Ronchetti
che mi ha sempre supportato, non solo nel lavoro di tesi ma in tutto il mio
percorso in Laurea Magistrale. Ha sempre dimostrato una grande disponibilit`a
fornendomi sempre una possibilit`a di confronto. Oltre a ci`o mi ha supportato
con idee, suggerimenti e consigli durante il lavoro di progetto come nella stesura
della Tesi.
Un grazie alla mia famiglia, che mi ha aiutato, sostenuto e ben consigliato
durante i momenti di maggior tensione ed ansia, come spinto ad andare avanti
nei momenti pi`
u di stanchezza, fatica e noia.
Sincera gratitudine la devo al Sig. Gianni Morelli, responsabile del servizio disabilit`a dell’Opera Universitaria e al Prof. Alberto Montresor. Senza queste
due persone, sempre disponibili e pronte a dare una mano, il mio percorso di studi
dal primo anno di Laurea Triennale alla fine della Laurea Magistrale stato ben
pi`
u arduo e pieno di ostacoli.
Ringrazio per la cordialit`a e la disponibilt`a l’Ing. Raffaele Di Vaio di
TifloSystem S.p.A. che mi ha fornito tutto il materiale ed supporto necessario
per 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 durante
lo svolgimento del progetto. Anche se una riga di codice sotto Windows non la
scriverebbe mai, per tutto ci`o che `e multipiattaforma come SQLite `e proprio un
drago!
Grazie a Stefano e Stella che negli ultimi due anni hanno fatto si che potessi seguire le lezioni in tranquillit`a, autonomia e con la disponibilit`a e simpatia
di due buoni amici. Grazie a Francesco, che spera ancora che non gli tolgano la
Provincia di Belluno, anche se di fatto `e emigrato a Udine.
Un simpatico ringraziamento a Luca per il supporto, l’aiuto durante la
tesi, le chiacchiere, forse anche per gli orari. . . no per quelli no, ho deciso! So-
Ringraziamenti
118
prattutto per`o per l’amicizia, per le ciaccolate e gli incoraggiamenti nel periodo
di tesi.
Non dimentico i pi`
u simpatici fra i ragazzi del servizio di accompagnamento (quelli che mi odiano ancora per le assistenze a Borino alle 7 e 45), senza
di loro... sarei col naso piantato sul ghiaccio!
Davvero grazie, `e stato un piacere ricevere aiuto e simpatia . . . anche se
`e vero che non leggerete mai questa pagina!
In conclusione `e doveroso un particolare ringraziamento all’Assessorato
per le Politiche Sociali della Provincia di Treviso e a tutte le persone che hanno
seguito l’assistenza scolastica dei ciechi e dei sordi negli ultimi 18 anni.
` davvero difficile ricordarsi di tutti, di certo non dimentico il prezioso lavoro
E
del Sig. Carnio e la fiducia che mi `e stata data dalla Dott.sa Boccaletto e dalla
Dott.sa Melocco. Grazie a loro ho potuto concludere i miei studi senza intoppi,
sicuro di avere sempre un supporto per le mie necessit`a 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 word
prediction.
[Evm06]
Anna Evmenova, Word prediction software for students with writing
difficulties.
[FH03]
Afsaneh Fazly and Graeme Hirst, Testing the efficacy of part-of-speech
information inword completion.
[GVA06]
Nestor Garay-Vitoria and Julio Abascal, Text prediction systems: a
survey, 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, technology
and 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 introduction to natural language processing, computational linguistics, and
speech recognition, second ed. ed., ch. Ch. 4 NGrams, Pearson Prentice
Hall, 2009.
[Koe05]
Philipp Koehn, Europarl: A parallel corpus for statistical machine
translation.
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 and
its use in the 1994 arpa csr evaluation, ARPA Spoken Language
Technology Workshop, Austin, TX (1995).
[Ros00]
Ronald Rosenfeld, Two decades of statistical language modeling:
Where do we go from here.
[spe]
Word
prediction
software
comparison
http://www.spectronicsinoz.com/article/
word-prediction-software-comparison-chart/.
chart,
[SPPC06] Simone Soria, Emanuele Perini, Andrea Prati, and Rita Cucchiara, Facemouse: A human-computer interface for tetraplegic people,
Computer Vision in Human-Computer Interaction, Lecture Notes in
Computer 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 prediction software to increase typing fluency with students with physical
disabilities.
[THG]
The grid 2, user manual.
[Voo99]
E.M. Voorhees, The trec-8 question answering track report, The
Eighth Text REtrieval Conference (TREC 8) (1999), 77–82.
121
BIBLIOGRAFIA
[WA07]
Tonio Wandmacher and Jean-Yves Antoine, Methods to integrate
a language model with semantic information for a word prediction
component, 506–513.
[WEB]
Sito web unione italiana lotta alla distrofia muscolare - padova, http:
//digilander.libero.it/uildmpadova/ausili.htm.

- I.C."Fratelli Linguiti"

Liste e candidati - Home | IC VAZZOLA

graduatoria asilo nido crescere 2014-2015

Importante, lettera di presentazione della nostra lista

Commissione Elettorale Elezioni RSU del 3 – 5 / marzo 2015

Documento PDF

Il Manifesto elettorale

QUESITO 1 - Provincia di Rimini

Proclamazione eletti R.S.U. triennio 2015/2018

epatite c, una campagna informativa nazionale firmata da abbvie

listino 2014 - Buca Harpsichords