Μοντέλο Διανυσματικού Χώρου (Vector Space Model)


Μια άλλη τεχνική ανάκτησης χρησιμοποιεί το μοντέλο του διανυσματικού χώρου, που προτάθηκε από τον Gerard Salton στις αρχές του 1960, ως εναλλακτική προσέγγιση του προβλήματος της ανάκτησης με σκοπό να ξεπεράσει τα προβλήματα του Boolean μοντέλου. Το μοντέλο βασίζεται στο μετασχηματισμό των κειμένων σε διανύσματα με συντεταγμένες πραγματικούς αριθμούς χρησιμοποιώντας την έννοια του διανυσματικού χώρου από τη γραμμική άλγεβρα. Δύο από τα πλεονεκτήματα του μοντέλου είναι η διάταξη των κειμένων της απάντησης σε φθίνουσα σειρά ως προς την σχετικότητά τους με το ερώτημα (relevance scoring) και επιπλέον ο μηχανισμός βελτίωσης των αποτελεσμάτων με ανάδραση (relevance feedback). Το μοντέλο επίσης επιτρέπει τη μερική αξιολόγηση των κειμένων εκχωρώντας σε κάθε κείμενο ένα αριθμό στο [0,1] ο οποίος μπορεί να θεωρηθεί ως η πιθανότητα ένα κείμενο να είναι σχετικό με το ερώτημα. Πολλές μηχανές αναζήτησης που βασίζονται στο μοντέλο επιστρέφουν το ποσοστό συνάφειας του κειμένου με το ερώτημα, π.χ. 90%. Τα μειονεκτήματα του μοντέλου είναι το υψηλό υπολογιστικό του κόστος και η επεκτασιμότητά του. Την ώρα που υποβάλλεται ένα ερώτημα θα πρέπει να υπολογιστεί το μέτρο της απόστασης (similarity measure) μεταξύ του ερωτήματος και όλων των κειμένων που περιέχουν όρους του ερωτήματος. Θα ξεκινήσουμε την περιγραφή του μοντέλου με ένα απλό παράδειγμα. Έστω μια βάση δεδομένων μιας υποθετικής βιβλιοθήκης. Τα βιβλία ξεχωρίζουν από τις λέξεις κλειδιά που καθορίζουν το περιεχόμενο κάθε βιβλίου, π.χ. {Μαθηματικά, Φυσική, Ιστορία, κλπ}. Για λόγους διαγραμματικής αναπαράστασης του μοντέλου θα περιοριστούμε σε τρία μόνο αντικείμενα: {Μαθηματικά, Φυσική, και Πληροφορική}. Έστω ότι ένα βιβλίο αναφέρεται μόνο σε μαθηματικά (κείμενο d1), ένα άλλο βιβλίο αποκλειστικά σε Φυσική (κείμενο d2) και ένα τρίτο αναφέρεται κατά 30% για μαθηματικά και κατά 70% σε πληροφορική (κείμενο d3). Τα κείμενα αυτά στις τρεις διαστάσεις (Μαθηματικά, Φυσική, Πληροφορική) μπορούν να παρασταθούν με διανύσματα ως εξής:
docvectors

Δηλαδή ταυτίζουμε κάθε διάσταση με μια έννοια (concept) και έτσι σχηματίζουμε ένα ορθογώνιο χώρο στον οποίο κάθε διάσταση παριστά και μία έννοια. Όπως βλέπουμε από το σχήμα οι έννοιες «Μαθηματικά» και «Πληροφορική» είναι κάθετες μεταξύ τους κάτι το οποίο μπορεί να ερνηνευτεί ότι οι δύο έννοιες είναι ξένες μεταξύ τους. Αυτό βέβαια δεν ισχύει γιατί, όπως γνωρίζουμε, μεταξύ των «Μαθηματικών» και «Πληροφορικής» υπάρχει πολύ μεγάλη σχέση αλλά είναι μια υπόθεση που μπορεί να μας βοηθήσει για την κατανόηση του μοντέλου. Τα παραπάνω διανύσματα αυτά στον χώρο των τριών διαστάσεων παρίστανται ως εξής:
vsm
Σχήμα 1. Αναπαράσταση των διανυσμάτων di στο χώρο 3 διαστάσεων. Παρατηρούμε ότι η γωνία μεταξύ του q και του d3 είναι η μικρότερη.

Όλα τα διανύσματα των βιβλίων αποτελούν τη βάση δεδομένων της βιβλιοθήκης – δηλαδή, ένα πίνακα, D (3xΝ), term-document matrix όπου 3 είναι το πλήθος των όρων και Ν το πλήθος των κειμένων. Έστω τώρα ότι αναζητούμε ένα βιβλίο το οποίο αναφέρεται κατά 50% σε Μαθηματικά και 50% σε πληροφορική. Αυτό είναι ένα ερώτημα το οποίο με όμοιο τρόπο μπορεί να εκφραστεί με ένα διάνυσμα, q, όπως φαίνεται στο σχήμα 5-1. Για κάθε διάνυσμα της βάσης δεδομένων μπορούμε να μετρήσουμε την απόσταση μεταξύ των διανυσμάτων των βιβλίων και του ερωτήματος, q, από την γωνία την οποία σχηματίζουν. Το συνημίτονο της γωνίας μεταξύ δύο μη μηδενικών διανυσμάτων x, y ορίζεται από τη σχέση
similarity

όπου ||x||2 είναι η Ευκλείδια νόρμα:
norm

Αν το συνημίτονο της γωνίας είναι 1, τότε η γωνία μεταξύ του διανύσματος ενός κειμένου (εγγράφου της βάσης) και του ερωτήματος είναι 0ο που σημαίνει ότι τα δύο διανύσματα έχουν την ίδια κατεύθυνση. Αν το συνημίτονο είναι 0 τότε τα διανύσματα είναι κάθετα. Συνεπώς όσο το συνημίτονο είναι πιο κοντά στο 1 τόσο πιο κοντά είναι τα δύο διανύσματα και τόσο πιο σχετικά θεωρούνται τα αντικείμενα της βάσης με το ερώτημα. Για το παραπάνω παράδειγμα έχουμε:
results

Συνεπώς το πλέον σχετικό με το ερώτημα κείμενο είναι το d3, το αμέσως επόμενο είναι το d2 και το d1 δεν είναι σχετικό. Συνοψίζοντας ο αλγόριθμος του μοντέλου του διανυσματικού χώρου περιγράφεται ως εξής:
for each di ∈ D
calculate cos(di, q);
sort di by cos(di,q);
Για πρακτικά προβλήματα όπου το πλήθος των κειμένων (|D|) είναι μερικές εκατοντάδες εκατομμύρια ο υπολογισμός των cos από τον παραπάνω αλγόριθμο είναι απαγορευτικός. Επιπλέον το μεγαλύτερο ποσοστό των κειμένων, di, δεν έχουν κοινά στοιχεία με το ερώτημα, q, επομένως για όλα αυτά τα κείμενα το cos(di, q)=0. Στις επόμενες παραγράφους θα δούμε περισσότερο αποτελεσματικούς αλγόριθμους για την αξιολόγηση των κειμένων σε σχέση με ένα ερώτημα.