Sistemi intelligenti per internet

Studio, implementazione e sperimentazione di un algoritmo di

classificazione delle domande basato sull’algoritmo di Winnow

Marco Giannone & Marco Bontempi

AA 2009/2010

Sistemi Intelligenti per Internet

giovedì 15 luglio 2010

Algoritmo di WinnowAlgoritmo on-line di comitato.

In questo studio viene applicato alla Q.A.

Un insieme di “esperti” (classificatori), ai quali è associato un peso, vengono interpellati all’arrivo dell’oggetto da classificare.

Ogni “esperto” classifica l’oggetto (ovvero assume valore 1 o 0). La somma dei pareri degli esperti (moltiplicati per il peso dell’esperto stesso) viene confrontata con una soglia (in genere N = numero degli esperti). Se questa somma supera la soglia si ha un parere positivo, altrimenti negativo.

In caso di predizione corretta non viene modificato il peso degli esperti. In caso di predizione errata si modifica il peso degli esperti che hanno dato parere positivo: se il parere positivo è corretto allora viene raddoppiato il peso, mentre se il parere avrebbe dovuto essere negativo viene dimezzato.


Vengono costruiti tanti comitati quante sono le categorie di domande.

Ciascun termine di ogni domanda diventa un “esperto” della propria categoria.

Quando si deve classificare una nuova domanda, questa viene sottoposta a tutti i comitati. I risultati che possiamo ottenere sono i seguenti:

Nessun comitato ha dato parere positivo: la domanda non viene classificata.

Più di un comitato fornisce parere positivo: la domanda non viene classificata.

Un solo comitato fornisce parere positivo: la domanda viene ritenuta appartenente alla categoria del comitato.

Winnow per la Q.A.


È stato usato un training set composto da 5452 domande e 6 categorie: ENTITY, DESCRIPTION, NUMBER, ABBREVIATION, LOCATION, HUMAN.

Se non è stato ancora costituito alcun comitato si prendono tutti i termini della domanda e si costruisce il primo.

Se esistono già dei comitati, la domanda viene sottoposta a tutti i comitati esistenti, aggiornando (se necessario) i pesi degli esperti. Se il comitato della categoria esiste allora tutti i termini della nuova domanda si aggiungono agli esperti di quel comitato; in caso contrario si costruisce un nuovo comitato.

Fase di Training


È stato usato un test set composto da 500 domande, appartenenti, ovviamente, alle medesime categorie della fase di training.

Ogni domanda viene sottoposta a tutti i comitati: il responso dell’algoritmo per ogni domanda può essere:

Domanda classificata in una delle sei categorie.

Domanda non classificata.

Fase di Test


Veri positivi, falsi positivi, falsi negativi, veri negativi.

Error rate: (FP + FN) / n

Accuracy: 1 - Error Rate

Precision: VP / ( VP + FP )

Recall: VP / ( VP + FN )

Break-Even: (Precision + Recall) / 2

F1-Measure: 2 (Precision * Recall) / (Precision + Recall)

Nella fase di training: per ogni domanda, per ogni categoria.

Nella fase di test: globalmente.

Misure raccolte


È stato notato che l’algoritmo da risposte migliori moltiplicando la soglia per un coefficiente pari a 0.01. Probabilmente la soglia potrebbe essere ulteriormente raffinata, ma c’è il rischio concreto di cadere in overfitting.

Winnow semplice: 244 istanze classificate correttamente, 65 classificate non correttamente, 191 non classificate.

Stemmer: sia il Porter Stemmer che lo stemmer di Wordnet sono stati inseriti nei diversi esperimenti, ma non hanno contribuito in maniera significativa.

Bi-words: oltre ai termini singoli sono state raccolte anche le coppie di termini. Le istanze classificate correttamente salgono a 274 (179 non classificate).

Tri-words: triple di termini. Risultati scarsi (208 istanze classificate correttamente).

Bi-words e Tri-words: sia coppie che triple di termini. Risultati analoghi al solo uso di tri-words.

Esperimenti 1/2


Uso del Tf-Idf per gli esperti: più un esperto ha un peso alto per molte categorie e meno è rilevante. L’algoritmo di Winnow non ne trae giovamento in quanto, dopo la fase di training, ha già attribuito dei pesi corretti per gli esperti.

Wordnet Sense (più bi-words): grazie a Wordnet è stato provato a sostituire ogni termine con il nome del suo Synset (“Noun”, “Verb”, “Adjective”, “Adverb”). I risultati sono migliorati(280 classificazioni corrette), ma è difficile scegliere correttamente il Synset giusto, poiché un termine potrebbe averne molteplici. Ad esempio: “Mouse” è “noun.animal” o “noun.artifact”?

Wordnet iperonimi (più bi-words): in questo esperimento ogni termine è stato sostituito con una sua iperonimia. Ad esempio il termine “Rome” viene sostituito con “City”. I risultati sono analoghi all’esperimento dei Synset (281 istanze classificate correttamente). Anche qui c’è il problema di saper distinguere correttamente iperonimi multipli.

Esperimenti 2/2


Osservando i risultati della fase di Test si evince che la difficoltà più grande è quella di classificare correttamente la classe DESCRIPTION. In particolare:

Molte domande appartenenti a questa categoria non riescono ad essere classificate, in quanto il proprio comitato non le riconosce (non fornisce parere positivo).

Mo lte a lt re doman de (sempre appartenent i a DESCRIPTION) vengono scambiate per appartenenti alla classe ENTITY.

Considerazioni


Misurazioni

Notare come le difficoltà più grandi si riscontrano nella classe DESCRIPTION e, in misura minore, nella classe ENTITY. La matrice di confusione riporta dei risultati positivi, perché ovviamente fa riferimento alle sole istanze classificate: questo ci da la conferma che molte istanze di DESCRIPTION non vengono riconosciute dal proprio comitato.


L’incremento maggiore di istanze classificate correttamente è stato ottenuto grazie all’introduzione delle Bi-words.

Alcune categorie in particolare ne hanno beneficiato:

ABBREVIATION: grazie alla Bi-word “stands-for”

NUMBER: grazie alle Bi-word “how-much” e “how-many”

L’introduzione di Wordnet non ha portato invece ad un incremento significativo di istanze classificate correttamente, a causa dell’impossibilità (allo stato attuale dello studio) di disambiguare i termini in maniera efficiente.

Riuscire a distinguere la classe DESCRIPTION da quella ENTITY è spesso difficile anche per un essere umano!!

Ogni esperimento è riuscito a migliorare solamente il riconoscimento di categorie che già venivano riconosciute sufficientemente bene.

Conclusioni


Sistemi intelligenti per internet

Education

Transcript of Sistemi intelligenti per internet