Ανάκτηση Πληροφορίας 9 Ανάκτηση Πληροφορίας στον Παγκόσμιο Ιστό Βιβλιογραφία

Κεφάλαιο 10Μετατροπή Ερωτήματος και Ανατροφοδότηση Σχετικότητας

10.1 Εισαγωγή

Στο κεφάλαιο αυτό, θα μελετήσουμε τεχνικές βελτίωσης της ποιότητας των αποτελεσμάτων ανάκτησης, μεταβάλλοντας το αρχικό ερώτημα. Θα εξετάσουμε τις πιο βασικές μεθόδους οι οποίες ανήκουν σε δύο βασικές κατηγορίες: i) τεχνικές επέκτασης του ερωτήματος και ii) τεχνικές ανατροφοδότησης του συστήματος με πληροφορίες που αναφέρονται στη σχετικότητα των αρχικών αποτελεσμάτων. Πολλές φορές, εξαιτίας των φαινομένων της συνωνυμίας και της πολυσημίας, τα αποτελέσματα που λαμβάνει ο χρήστης μπορεί να διαφέρουν σημαντικά από τις πληροφοριακές του ανάγκες. Σε μία τέτοια περίπτωση, θα πρέπει να εκτελεστούν κάποιες ενέργειες με στόχο την επιστροφή πιο σχετικών απαντήσεων. Μία προφανής λύση θα ήταν απλά να ζητήσουμε από το σύστημα περισσότερα αποτελέσματα, ελπίζοντας ότι στις επόμενες απαντήσεις θα υπάρχουν πιο σχετικά έγγραφα. Ωστόσο, η τακτική αυτή δε θα λύσει το πρόβλημά μας, καθώς δεν υπάρχει καμία εγγύηση ότι τα επόμενα έγγραφα θα είναι σχετικά. Επιπλέον, αναμένεται ότι η ακρίβεια των αποτελεσμάτων θα μειωθεί σημαντικά στην προσπάθειά μας να ανακτήσουμε περισσότερα έγγραφα. Οι τεχνικές που μελετούμε στο κεφάλαιο αυτό δίνουν αποτελεσματικές λύσεις στο πρόβλημα. Η διαδικασία επαναπροσδιορισμού του αρχικού ερωτήματος παρουσιάζεται στο Σχήμα 10.1

Σχήμα 10.1: Διαδικασία επαναπροσδιορισμού ερωτήματος.

10.2 Επέκταση Ερωτήματος

Η τεχνική της επέκτασης ή μετατροπής ερωτήματος (query reformulation, query expansion) αναφέρεται στη διαδικασία αλλαγής του αρχικού ερωτήματος του χρήστη, με βασικό στόχο τη βελτίωση της ποιότητας των αποτελεσμάτων. Στην ενότητα αυτή εξετάζουμε τεχνικές οι οποίες προσπαθούν να προσθέσουν νέους όρους στο ερώτημα, ώστε η επεξεργασία του νέου ερωτήματος να φέρει πιο ποιοτικά αποτελέσματα σε σχέση με το προηγούμενο.

Η προσθήκη νέων όρων στο ερώτημα μπορεί να αφορά σε συνώνυμους όρους, σε μετατροπή των λέξεων με βάση τη ρίζα τους, ή σε προσθήκη όρων που έχουν κάποια σχετικά μικρή απόσταση από τους όρους του αρχικού ερωτήματος στα έγγραφα που έχουν επιστραφεί ως αποτελέσματα. Γενικά, υπάρχουν δύο τεχνικές οι οποίες μπορούν να χρησιμοποιηθούν:

•

τοπική ανάλυση, σύμφωνα με την οποία πραγματοποιείται ανάλυση στα εγγραφα που έχουν επιστραφεί μετά την επεξεργασία του συγκεκριμένου ερωτήματος και η προσθήκη ή μετατροπή των όρων στηρίζεται μόνο σε αυτά, και
•

γενικευμένη ανάλυση, σύμφωνα με την οποία πραγματοποιείται ανάλυση σε όλα τα έγγραφα της συλλογής με στόχο την κατασκευή θησαυρού ή άλλων δομών οι οποίες θα μπορεί να χρησιμοποιηθούν για τη μετατροπή ερωτημάτων.

Σημειώνεται ότι και οι δύο τεχνικές είναι αυτοματοποιημένες, με αποτέλεσμα να μην απαιτείται καμία παρέμβαση από το χρήστη. Τεχνικές που επιβάλλουν την ανατροφοδότηση πληροφοριών από το χρήστη εξετάζονται σε επόμενη ενότητα.

10.2.1 Επέκταση Ερωτήματος με Τοπική Ομαδοποίηση

Στην ενότητα αυτή εξετάζουμε συνοπτικά μία τεχνική επέκτασης ερωτήματος που βασίζεται στην ομαδοποίηση (clustering) των όρων που εμφανίζονται στα έγγραφα που έχουν επιστραφεί μετά από την εκτέλεση του αρχικού ερωτήματος. Έστω $A_{q}$ το σύνολο των εγγράφων αυτών. Η μέθοδος που εξετάζουμε βασίζεται στην παρατήρηση ότι όροι που εμφανίζονται συχνά από κοινού στα έγγραφα θα πρέπει να σχετίζονται μεταξύ τους. Επομένως, λαμβάνοντας υπόψη τα έγγραφα του συνόλου $A_{q}$ θα μπορούσαμε να συσχετίσουμε διαφορετικούς όρους μεταξύ τους ώστε το ερώτημα να επεκταθεί κατάλληλα.

Με βάση το συμβολισμό που χρησιμοποιούμε, θυμηθείτε ότι με $f_{i,j}$ συμβολίζουμε τη συχνότητα εμφάνισης του $i$ -οστού όρου, στο $j$ -οστό έγγραφο. Επίσης, έστω $T$ το πλήθος των μοναδικών όρων που υπάρχουν στο σύνολο της απάντησης $A_{q}$ και $D=|A_{q}|$ το πλήθος των εγγράφων της απάντησης. Ορίζουμε τη συσχέτιση μεταξύ του $i$ -οστού και του $k$ -οστού σύμφωνα με τον ακόλουθο τύπο:

c_{i,k}=\sum_{d_{j}\in A_{q}}f_{i,j}\cdot f_{k,j}

(10.1)

Με βάση την έννοια της συσχέτισης μεταξύ όρων μπορούμε να δημιουργήσουμε έναν πίνακα συσχέτισης $S$ ο οποίος καταγράφει τις συσχετίσεις μεταξύ των διαφορετικών όρων. Στην πιο απλή περίπτωση μπορούμε να θέσουμε $s_{i,k}=c_{i,k}$ . Παρατηρήστε ότι η μέθοδος αυτή χρησιμοποιεί μη κανονικοποιημένες τιμές των συχνοτήτων $f_{i,j}$ . Εναλλακτικά, μπορεί να χρησιμοποιηθεί και η κανονικοποιημένη μορφή σύμφωνα με την οποία:

s_{i,k}=\frac{c_{i,k}}{c_{i,i}+c_{k,k}-c_{i,k}}

(10.2)

Με βάση τον πίνακα συσχετίσεων $S$ , για κάθε όρο του ερωτήματος $q$ , προσδιορίζεται ένα σύνολο από $m$ σχετικούς όρους. Για την ακρίβεια, προσδιορίζονται οι $m$ περισσότερο σχετικοί όροι για κάθε όρο που ανήκει στο ερώτημα. Έστω $q_{l}$ ένας όρος από το ερώτημα ο οποίος υποθέτουμε ότι είναι ο $i$ -οστός όρος στον πίνακα $S$ . Για τον όρο αυτόν, δημιουργείται το σύνολο $S_{i}(m)$ επιλέγοντας από την $i$ -οστή γραμμή του πίνακα $S$ τις $m$ μεγαλύτερες τιμές συσχέτισης. Οι αντίστοιχοι όροι σχηματίζουν το σύνολο $S_{i}(m)$ .

Στη συνέχεια ας δούμε με ποιόν τρόπο μπορεί να επεκταθεί το αρχικό ερώτημα $q$ . Για κάθε έναν από τους όρους του ερωτήματος επιλέγονται οι $\zeta$ όροι από το σύνολο $S_{i}(m)$ και στη συνέχεια οι όροι αυτοί προστίθενται στο αρχικό ερώτημα $q$ και έτσι προκύπτει ένα νέο ερώτημα $q^{\prime}$ . Από τη στιγμή που το $q^{\prime}$ περιλαμβάνει νέους όρους, αναμένεται ότι θα υπάρχει διαφοροποίηση ως προς τα αποτελέσματα του $q^{\prime}$ σε σύγκριση με τα αποτελέσματα του $q$ .

10.2.2 Επέκταση Ερωτήματος με Τοπική Ανάλυση Περιεχομένου

Στην προηγούμενη ενότητα, εξετάσαμε μία μέθοδο επέκτασης του ερωτήματος χρησιμοποιώντας την έννοια της συσχέτισης μεταξύ των όρων του ερωτήματος και των όρων που περιέχονται στα έγγραφα της απάντησης. Μία εναλλακτική μέθοδος επέκτασης είναι η χρήση ανάλυσης του περιεχομένου των εγγράφων της απάντησης με στόχο τον εντοπισμό συνδυασμού όρων που εμφανίζονται σχετικά κοντά στα έγγραφα.

Η μέθοδος αυτή βασίζεται στη χρήση των ομάδων ουσιαστικών (noun groups). Οι ομάδες αυτές μπορεί να αποτελούνται από ένα ουσιαστικό, από δύο ουσιαστικά που εμφανίζονται συνεχόμενα ή από τρία ουσιαστικά που εμφανίζονται συνεχόμενα στα έγγραφα της απάντησης. Επίσης, σύμφωνα με τη μέθοδο αυτή, το κάθε έγγραφο της απάντησης χωρίζεται σε τμήματα κειμένου, και η ομοιότητα των όρων προσδιορίζεται με βάση τα τμήματα κειμένου στα οποία οι όροι (ομάδες ουσιαστικών) εμφανίζονται μαζί.

Συνοπτικά, η μέθοδος αποτελείται από τα ακόλουθα βήματα:

•

Στο πρώτο βήμα, τα έγγραφα της απάντησης τμηματοποιούνται σε λογικές ομάδες (για παράδειγμα ενότητες, παραγράφους ή τμήματα που αποτελούνται από μερικές εκατοντάδες λέξεων). Το κάθε λογικό τμήμα έχει το ρόλο του εγγράφου.
•

Στο δεύτερο βήμα, για κάθε λογικό τμήμα προσδιορίζεται το νόημα του τμήματος, που συμβολίζεται με $c$ . Στη συνέχεια, προσδιορίζονται τα λογικά τμήματα με τη μεγαλύτερη ομοιότητα ως προς το ερώτημα $q$ . Η ομοιότητα ενός νοήματος $c$ με το ερώτημα $q$ συμβολίζεται με $Sim(q,c)$ .
•

Στο τρίτο βήμα, υπολογίζονται τα $k$ καλύτερα λογικά τμήματα ως προς τη συνάρτηση ομοιότητας $Sim(q,c)$ και τα αντίστοιχα νοήματα $c$ προστίθενται στο αρχικό ερώτημα.

10.2.3 Επέκταση Ερωτήματος με Γενικευμένη Ανάλυση

Στις προηγούμενες ενότητες εξετάσαμε τεχνικές επαύξησης του αρχικού ερωτήματος, χρησιμοποιώντας τεχνικές ανάλυσης των σχετικών ως προς το ερώτημα εγγράφων. Στη συνέχεια θα εξετάσουμε τεχνικές που χρησιμοποιούν το σύνολο των εγγράφων της συλλογής. Οι τεχνικές αυτές βασίζονται στη χρήση θησαυρού (thesaurus) ο οποίος μπορεί να κατασκευασθεί με διάφορους τρόπους. Εδώ θα εξετάσουμε δύο περιπτώσεις: την κατασκευή θησαυρού που βασίζεται στην ομοιότητα των όρων και στην κατασκευή θησαυρού με στατιστικές τεχνικές.

Ο θησαυρός ομοιοτήτων (similarity thesaurus) κατασκευάζεται με βάση τις συσχετίσεις μεταξύ των όρων που βρίσκονται στα έγγραφα της συλλογής. Αναλυτικότερα, ο κάθε όρος μπορεί να αναπαρασταθεί ως ένα διάνυσμα με βάση τα έγγραφα στα οποία εμφανίζεται. Σύμφωνα με το συμβολισμό του Κεφαλαίου 4, έστω $N$ το σύνολο των εγγράφων της συλλογής, $\cal T$ το σύνολο των μοναδικών όρων που εμφανίζονται στα έγγραφα της συλλογής και $f_{t,d}$ η συχνότητα εμφάνισης του όρου $t$ στο έγγραφο $d$ . Επίσης, έστω $M=|\cal T|$ το πλήθος των μοναδικών όρων και $T_{d}$ το πλήθος των μοναδικών όρων στο έγγραφο $d$ . Ορίζουμε την αντίστροφη συχνότητα όρου (inverse term frequency) $itf_{d}$ του εγγράφου $d$ ως εξής:

itf_{d}=\log\frac{M}{T_{d}}

(10.3)

Για κάθε όρο $t$ της συλλογής, δημιουργείται διάνυσμα $\vec{v_{t}}$ μήκους $N$ (όσα και τα έγγραφα της συλλογής) της μορφής:

\vec{v_{t}}=(w_{t,d_{1}},w_{t,d_{2}},...,w_{t,d_{N}})

(10.4)

Τα βάρη στο παραπάνω διάνυσμα προσδιορίζονται με τρόπο παρόμοιο με αυτόν που χρησιμοποιήθηκε για τον προσδιορισμό των βαρών στα διανύσματα των εγγράφων, σύμφωνα με το διανυσματικό μοντέλο ανάκτησης που εξετάσαμε στο Κεφάλαιο 4. Με βάση τα διανύσματα των όρων η συσχέτιση μεταξύ δύο όρων $x$ και $y$ ορίζεται ως το εσωτερικό γινόμενο των αντίστοιχων διανυσμάτων:

c_{x,y}=\vec{v_{x}}\cdot\vec{v_{y}}=\sum_{i=1}^{N}w_{x,d_{i}}\times w_{y,d_{i}}

(10.5)

Με βάση την προηγούμενη συζήτηση, η επέκταση του αρχικού ερωτήματος πραγματποιείται λαμβάνοντας υπόψη τις συσχετίσεις μεταξύ των όρων του ερωτήματος και των υπόλοιπων όρων που εμφανίζονται στα έγγραφα της συλλογής. Αναλυτικότερα, αρχικά προσδιορίζονται τα διανύσματα των όρων του ερωτήματος, στη συνέχεια εφαρμόζεται μία συνάρτηση ομοιότητας (συνήθως είναι το εσωτερικό γινόμενο) μεταξύ των όρων που συσχετίζονται με τους όρους του ερωτήματος και ολόκληρο το ερώτημα και τέλος το ερώτημα επεαυξάνεται λαμβάνοντας τους $k$ όρους με τη μεγαλύτερη τιμή ομοιότητας.

10.3 Ανατροφοδότηση Σχετικότητας

Στις προηγούμενες ενότητες, εξετάσαμε τεχνικές επέκτασης του αρχικού ερωτήματος με αυτοματοποιημένες τεχνικές, χωρίς την παραμικρή παρέμβαση από το χρήστη. Μία δεύτερη κατηγορία τεχνικών χρησιμοποιεί στοιχεία από το χρήστη ώστε να βελτιωθεί η ποιότητα των αποτελεσμάτων. Γενικότερα, η τεχνική που απαιτεί την παρέμβαση του χρήστη καλείται ανατροφοδότηση ή ανάδραση σχετικότητας (relevance feedback) και συναντάται σε διάφορες μορφές. Στην ενότητα αυτή, θα μελετήσουμε τεχνικές χρήσης επιπρόσθετων πληροφοριών με στόχο την αύξηση της ποιότητας εάν ζητηθεί.

Διαχωρίζουμε μεταξύ τριών διαφορετικών τεχνικών ανατροφοδότησης, ανάλογα με το ποσοστό εμπλοκής του χρήστη στη διαδικασία. Έχουμε λοιπόν:

•

άμεση ανατροφοδότηση, σύμφωνα με την οποία ο χρήστης θα πρέπει να δηλώσει ποια από τα έγγραφα που έχουν επιστραφεί μετά την εκτέλεση του αρχικού ερωτήματος είναι σχετικά,
•

έμμεση ανατροφοδότηση, σύμφωνα με την οποία το σύστημα λαμβάνει πληροφορίες από τη συμπεριφορά του χρήστη, χωρίς να δηλώνεται άμεσα η σχετικότητα των εγγράφων, και
•

ψευδοανατροφοδότηση, σύμφωνα με την οποία το σύστημα λαμβάνει πρωτοβουλία σχετικά με τον προσδιορισμό των σχετικών αποτελεσμάτων και αναπροσδιορίζει με αυτόματο τρόπο το νέο ερώτημα.

Στη συνέχεια εξετάζουμε και τις τρεις μορφές ανατροφοδότησης.

10.3.1 Άμεση Ανατροφοδότηση

Πρώτα μελετούμε την πιο άμεση μορφή ανατροφοδότησης, η οποία απαιτεί από το χρήστη να προσδιορίσει τη σχετικότητα των εγγράφων που έχουν επιστραφεί από την εκτέλεση του αρχικού ερωτήματος. Αναλυτικότερα, εάν ο χρήστης δεν είναι ικανοποιημένος από τη σχετικότητα των εγγράφων της απάντησης, θα πρέπει να προσδιορίσει ποια από το έγγραφα είναι σχετικά με το αρχικό του ερώτημα και ποια όχι. Στην πιο απλή περίπτωση, ο χρήστης επιλέγει τα σχετικά έγγραφα (θετική ανατροφοδότηση) ενώ στην πιο γενική περίπτωση μπορεί να προσδιορίσει και τα έγγραφα που χαρακτηρίζονται ως εντελώς άσχετα με το ερώτημα (αρνητική ανατροφοδότηση).

Η ανατροφοδότηση σχετικότητας χαρακτηρίζεται από μερικά πολύ σημαντικά πλεονεκτήματα τα οποία αναφέρονται συνοπτικά στη συνέχεια:

•

Σε αντίθεση με την τεχνική της επέκτασης ή της αλλαγή του ερωτήματος, η ανατροφοδότηση απαιτεί από το χρήστη μόνο την επιλογή των σχετικών εγγράφων.
•

Κατά την ανατροφοδότηση, ενισχύεται η σημαντικότητα των όρων που περιέχονται σε σχετικά έγγραφα και αντίθετα αποδυναμώνεται η σημαντικότητα των όρων οι οποίοι περιέχονται σε έγγραφα μη σχετικά για το χρήστη.
•

Η διαδικασία της ανατροφοδότησης είναι πολύ απλή στην εκτέλεσή της με αποτέλεσμα να είναι πολύ εκλυστική για τους χρήστες.

Ανατροφοδότηση στο Διανυσματικό Μοντέλο

Σύμφωνα με το διανυσματικό μοντέλο ανάκτησης, το κάθε έγγραφο μπορεί να αναπαρασταθεί με ένα διάνυσμα βαρών. Το ίδιο ισχύει και για το ερώτημα του χρήστη. Στόχος της ανατροφοδότησης είναι ο εκ νέου προσδιορισμός των βαρών του διανύσματος του ερωτήματος έτσι ώστε η γειτονιά του νέου διανύσματος να περιέχει περισσότερα σχετικά ως προς το ερώτημα έγγραφα, σε σχέση με το αρχικό διάνυσμα. Για τη συνέχεια υποθέτουμε ότι το αρχικό ερώτημα είναι το $q_{0}$ και το αντίστοιχο διάνυσμα βαρών είναι το $\vec{q_{0}}$ . Μετά την αναμόρφωση των βαρών θα προκύψει το διάνυσμα $\vec{q_{1}}$ το οποίο θα πρέπει να εκτελεστεί ώστε να προκύψει το νέο σύνολο αποτελεσμάτων.

Έστω $A_{0}$ το σύνολο των αποτελεσμάτων του ερωτήματος $q_{0}$ . Έστω επίσης ότι $n$ είναι το πλήθος των εγγράφων της απάντησης, δηλαδή $n=|A_{0}|$ . Στην άμεση ανατροφοδότηση, ο χρήστης καλείται να επιλέξει ποιά από τα έγγραφα του συνόλου $A_{0}$ είναι σχετικά ως προς τις πληροφοριακές του ανάγκες και ποιά όχι. Η επιλογή των εγγράφων από το χρήστη έχει ως αποτέλεσμα τα έγγραφα να χωριστούν σε δύο σύνολα: $i$ ) το σύνολο $R$ που περιέχει τα έγγραφα τα οποία ο χρήστης έχει επιλέξει ως σχετικά και $i i$ ) το σύνολο $N R$ το οποίο περιλαμβάνει τα έγγραφα τα οποία ο χρήστης έχει επιλέξει ως μη σχετικά. Στην περίπτωση που υποστηρίζεται μόνο θετική ανατροφοδότηση, τότε προφανώς το σύνολο $N R$ είναι το κενό σύνολο.

Ας υποθέσουμε ότι γνωρίζουμε το σύνολο $C$ που περιέχει όλα τα σχετικά ως προς το ερώτημα έγγραφα από όλη τη συλλογή. Είναι προφανές ότι στην πράξη το σύνολο αυτό δεν το γνωρίζουμε, διαφορετικά δε θα υπήρχε λόγος εκτέλεσης του ερωτήματος. Εάν ωστόσο γνωρίζουμε ακριβώς το σύνολο $C$ , το ερώτημα είναι αν μπορούμε να προσδιορίσουμε το βέλτιστο διάνυσμα βαρών. Πράγματι, το βέλτιστο διάνυσμα βαρών για ένα συγκεκριμένο ερώτημα δίδεται από τον ακόλουθο μαθηματικό τύπο:

[\vec{q}_{opt}=\frac{1}{|C|}\sum_{\forall d\in C}\vec{d}-\frac{1}{N-|C|}\sum_{% \forall d\notin C}\vec{d}]

(10.6)

Με βάση την παρατήρηση ότι το σύνολο $C$ δεν είναι γνωστό, θα πρέπει να βρεθεί ένας εναλλακτικός τρόπος προσδιορισμού του βέλτιστου ερωτήματος, έστω και κατά προσέγγιση, με βάση την πληροφορία που παρέχεται από την ανατροφοδότηση. Είναι λογικό επίσης να σκεφθούμε ότι η διαδικασία προσέγγισης του βέλτιστου διανύσματος πρέπει να είναι σταδιακή, καθώς το διάνυσμα μεταβάλλεται κάθε φορά που πραγματοποιείται ένας νέος κύκλος ανατροφοδότησης. Με βάση τηνν προηγούμενη συζήτηση, ο μαθηματικός τύπος μεταβολής του διανύσματος βαρών είναι ο ακόλουθος και αναφέρεται ως τύπος του Rochio:

[\vec{q}_{1}=\alpha\cdot\vec{q}_{0}+\beta\cdot\frac{1}{|R|}\sum_{\forall d\in R% }\vec{d}-\gamma\cdot\frac{1}{|NR|}\sum_{\forall d\in NR}\vec{d}]

(10.7)

Ας αναλύσουμε προσεκτικά τον παραπάνω τύπο. Υπάρχουν τρεις παράμετροι $\alpha$ , $\beta$ και $\gamma$ . Η παράμετρος $\alpha$ ρυθμίζει τη σημαντικότητα του διανύσματος του αρχικού ερωτήματος. Για παράδειγμα αν $\alpha=0$ τότε το αρχικό ερώτημα δε λαμβάνεται υπόψη καθόλου για το σχηματισμό του επόμενου διανύσματος. Στην πράξη βέβαια η τιμή της παραμέτρου $\alpha$ είναι μη μηδενική. Η παράμετρος $\beta$ ρυθμίζει τη συμαντικότητα των όρων που περιέχονται στο σύνολο των σχετικών ως προς το χρήστη έγγραφα (σύνολο $R$ ). Με βάση τον τύπο του Rochio, η ποσότητα $1/|R|\sum_{\forall d\in R}\vec{d}$ είναι στην ουσία το μέσο διάνυσμα που προκύπτει από το μέσο όρο των βαρών των όρων που συμμετέχουν στα σχετικά έγγραφα. Ομοίως, η ποσότητα $1/(N-|C|)\sum_{\forall d\notin C}\vec{d}$ είναι ένα διάνυσμα που περιέχει τους μέσους όρους των βαρών για τους όρους που συμμετέχουν στα έγγραφα τα οποία ο χρήστης έχει επισημάνει ως μη σχετικά. Είναι προφανές, ότι για διαφορετικές τιμές των παραμέτρων $\alpha$ , $\beta$ και $\gamma$ θα υπογιστούν διαφορετικά διανύσματα $\vec{q}_{1}$ .

Σημειώνεται ότι η διαδικασία της ανατροφοδότησης μπορεί να επαναληφθεί περισσότερες από μία φορές. Στην περίπτωση αυτή κάθε φορά παράγεται και ένα νέο διάνυσμα το οποίο στηρίζεται στο προηγούμενο και στα βάρη των όρων που περιέχονται στα σχετικά και μη σχετικά έγγραφα. Εάν συμβολίσουμε με $\vec{q}_{0}$ το διάνυσμα που αναφέρεται στο αρχικό ερώτημα, τότε σταδιακά δημιουργούνται τα διανύσματα $\vec{q}_{1}$ , $\vec{q}_{2}$ , $\vec{q}_{3}$ μέχρι να τερματιστεί η διαδικασία της ανατροφοδότησης. Τονίζεται ότι ο κάθε κύκλος ανατροφοδότησης εξαρτάται μόνο από το προηγούμενο διάνυσμα βαρών και από τα έγγραφα που ο χρήστης έχει σημειώσει ως σχετικά ή ως μη σχετικά.

Παράδειγμα 10.1

Υποθέστε ότι μία φυσική γλώσσα διαθέτει μόνο 8 διαφορετικές λέξεις. Επομένως, όλα τα διανύσματα των ερωτημάτων καθώς επίσης και των εγγράφων θα ορίζονται στις 8 διαστάσεις. Υποθέστε ακόμη ότι το διάνυσμα που αντιστοιχεί στο αρχικό ερώτημα είναι:

\vec{q}_{0}=(0,1,0,0,1,0,0,1)

(10.8)

Έστω ότι το σύστημα ανάκτησης επιστρέφει πέντε έγγραφα σχετικά με το ερώτημα $q_{0}$ , τα οποία προσδιορίζονται από τα ακόλουθα διανύσματα:

$\displaystyle\vec{d}_{1}$	$\displaystyle=$	$\displaystyle(0.5,3,1,0,2,0,0,0)$
$\displaystyle\vec{d}_{2}$	$\displaystyle=$	$\displaystyle(0,5,0,0,2,0,0,0)$
$\displaystyle\vec{d}_{3}$	$\displaystyle=$	$\displaystyle(3,5,0.5,0,1,0,0,2)$
$\displaystyle\vec{d}_{4}$	$\displaystyle=$	$\displaystyle(3,1,0.5,0,1,0,0,2)$
$\displaystyle\vec{d}_{5}$	$\displaystyle=$	$\displaystyle(3,1,0.5,0,1,0,3,3)$

Υποθέστε ότι ο χρήστης επιθυμεί να προχωρήσει στη διαδικασία ανατροφοδότησης και έτσι επιλέγει τα έγγραφα $d_{1}$ , $d_{2}$ και $d_{3}$ ως σχετικά και τα έγγραφα $d_{4}$ και $d_{5}$ ως μη σχετικά. Με βάση την προηγούμενη συζήτηση έχουμε: $R=\{d_{1},d_{2},d_{3}\}$ και $NR=\{d_{4},d_{5}\}$ . Επομένως, έχουν επιλεγεί τρία έγγραφα ως σχετικά και δύο έγγραφα ως μη σχετικά. Ας δούμε στη συνέχεια με ποιον τρόπο επαναπροσδιορίζεται το διάνυσμα του ερωτήματος. Με βάση τον τύπο του Rochio, θα πρέπει πρώτα να αθροίσουμε τα διανύσματα των εγγράφων που έχουν χαρακτηριστεί από το χρήστη ως σχετικά. Αν αθροίσουμε τα διανύσματα αυτά και διαιρέσουμε την κάθε συντεταγμένη με το πλήθος των σχετικών εγγράφων (3) λαμβάνουμε το ακόλουθο διάνυσμα $\vec{v}$

\vec{v}=\frac{1}{3}\cdot(\vec{d}_{1}+\vec{d}_{2}+\vec{d_{3}})=(1.17,4.33,0.5,0% ,1.67,0,0,0.67)

(10.9)

Με όμοιο τρόπο χειριζόμαστε τα διανύσματα των εγγράφων που έχουν χαρακτηριστεί ως μη σχετικά από το χρήστη. Το αντίστοιχο μέσο διάνυσμα των μη σχετικών εγγράφων είναι

\vec{u}=\frac{1}{2}\cdot(\vec{d}_{4}+\vec{d}_{5})=(3,1,0.5,0,1,0,1.5,2.5)

(10.10)

Τέλος, αν υποθέσουμε ότι $\alpha=2$ , $\beta=1$ and $\gamma=1$ , με εφαρμογή του τύπου του Rochio το νέο διάνυσμα $\vec{q}_{1}$ που προκύπτει θα είναι:

\vec{q}_{1}=\alpha\cdot\vec{q}_{0}+\beta\cdot\vec{v}-\gamma\cdot\vec{u}=(-2.17% ,5.33,0,0,2.67,0,-1.5,0.17)

(10.11)

Παρατηρούμε ότι το νέο διάνυσμα είναι διαφορετικό από αυτό του αρχικού ερωτήματος. Στην περίπτωση που υπάρχουν αρνητικές συντεταγμένες αυτές γίνονται μηδενικές, καθώς δεν έχει νόημα το αρνητικό βάρος.

Ανάλογα με την επιλογή του χρήστη και τις τιμές των παραμέτρων $\alpha$ , $\beta$ και $\gamma$ ενδέχεται τα βάρη κάποιων όρων να μειωθούν (ακόμη και να λάβουν αρνητικές τιμές), να αυξηθούν ή να παραμείνουν σταθερά. Επομένως, πραγματοποιείται μία προσαρμογή των βαρών η οποία σχετίζεται άμεσα με τα σύνολα $R$ και $N R$ που έχουν δημιουργηθεί μετά την επιλογή του χρήστη. Μετά τη δημιουργία του νέου διανύσματος ακολουθεί εκτέλεση του ερωτήματος. Ακολουθείται η τυπική διαδικασία επεξεργασίας που βασίζεται στον αντεστραμμένο κατάλογο και λαμβάνονται υπόψη μόνο οι όροι που αντιστοιχούν σε μη μηδενικά βάρη του νέου διανύσματος.

Ανατροφοδότηση στο Πιθανοκρατικό Μοντέλο

Η ανατροφοδότηση στο Πιθανοκρατικό μοντέλο συζητήθηκε στην ενότητα 5.3.2. Ωστόσο, για λόγους πληρότητας του παρόντος κεφαλαίου θα συνοψίσουμε τα βασικότερα σημεία και εδώ. Με βάση τη συζήτηση που έγινε στο Κεφάλαιο 5 σχετικά με την ομοιότητα ενός ερωτήματος $q$ και ενός εγγράφου $d$ έχουμε:

[S_{prob}(q,d)\propto\sum_{\forall i,~{}t_{i}\in{\cal T}_{q,d}}\log\frac{p_{i}% \cdot(1-u_{i})}{u_{i}\cdot(1-p_{i})}=\sum_{\forall i,~{}t_{i}\in{\cal T}_{q,d}% }w_{i}]

(10.12)

όπου ${\cal T}_{d}$ είναι το σύνολο των μοναδικών όρων του εγγράφου $d$ , ${\cal T}_{q}$ το σύνολο των μοναδικών όρων του ερωτήματος $q$ , ${\cal T}_{q,d}$ η τομή των δύο συνόλων, και $w_{i}$ είναι το βάρος του όρου $t_{i}$ . Υπενθυμίζεται επίσης ότι $p_{i}$ = $P(w_{t_{i},d}=1|{\cal R})$ και $u_{i}$ = $P(w_{t_{i},d}=1|\lnot{\cal R})$ ενώ το βάρος ρου κάθε όρου δίνεται από την παρακάτω σχέση:

w_{i}=\log\frac{p_{i}\cdot(1-u_{i})}{u_{i}\cdot(1-p_{i})}=\log\frac{r_{i}\cdot% (N-R-n_{i}-r_{i})}{(n_{i}-r_{i})\cdot(R-r_{i})}

(10.13)

Το βασικό πρόβλημα που πρέπει να λυθεί είναι ο υπολογισμός των πιθανοτήτων $p_{i}=P(w_{t_{i},d}=1|{\cal R})$ και $u_{i}=P(w_{t_{i},d}=1|\lnot{\cal R})$ . Οι πιθανότητες αυτές δεν είναι γνωστές, αφού δεν γνωρίζουμε εκ των προτέρων πιο είναι το σύνολο ${\cal R}$ των σχετικών ως προς ερώτημα εγγράφων. Επομένως, θα πρέπει να εκτιμήσουμε αρχικά με κάποιον τρόπο αυτές τις πιθανότητες και στην συνέχεια να τις προσδιορίσουμε καλύτερα.

Αρχικά, πραγματοποιείται ανάκτηση των εγγράφων που περιέχουν τους όρους του ερωτήματος. Στη συνέχεια, χρησιμοποιούμε τη συνάρτηση ομοιότητας 10.12 για να βαθμολογήσουμε τα έγγραφα που έχουν ανακτηθεί, θέτοντας $p_{i}$ = 0.5 και $u_{i}$ = $n_{i}/N$ ως αρχικές εκτιμήσεις. Στη συνέχεια, από το σύνολο των εγγράφων που έχουν ανακτηθεί και βαθμολογηθεί επιλέγουμε ένα υποσύνολο αυτών (για παράδειγμα τα έγγραφα των οποίων ο βαθμός ομοιότητας είναι πάνω από κάποιο κατώφλι ή τα $R$ έγγραφα με το μεγαλύτερο βαθμό). Στο σημείο αυτό θα μπορούσε να βοηθήσει και ο χρήστης στη διαδικασία επιλογής των εγγράφων. Μετά από αυτό το βήμα, μπορεί να γίνει μία νέα εκτίμηση των ποσοτήτων $p_{i}$ και $u_{i}$ και επομένως της ποσότητας $w_{i}$ με βάση τον τύπο 10.13. Η διαδικασία αυτή εκτελείται είτε για ένα σταθερό αριθμό επαναλήψεων, είτε μέχρι η μεταβολή των αποτελεσμάτων να μην είναι σημαντική.

10.3.2 Άλλες Μορφές Ανατροφοδότησης

Η άμεση ανατροφοδότηση που μελετήσαμε στις προηγούμενες ενότητες απαιτεί από το χρήστη να επιλέξει τα έγγραφα που κατά τη γνώμη του είναι περισσότερο σχετικά ως προς το αρχικό ερώτημα. Ωστόσο, υπάρχουν δύο άλλες μορφές ανατροφοδότησης σύμφωνα με τις οποίες το σύστημα λαμβάνει πληροφορίες για τη σχετικότητα των εγγράφων με έμμεσο τρόπο. Στη συνέχεια θα αναφερθούμε συνοπτικά στις δύο αυτές μορφές οι οποίες είναι: η έμμεση ανατροφοδότηση και η ψευδοανατροφοδότηση.

Κατά την έμμεση ανατροφοδότηση το σύστημα προσπαθεί να αντλήσει πληροφορίες για τη σχετικότητα των εγγράφων χρησιμοποιώντας εναλλακτικές μεθόδους. Πρέπει ωστόσο να τονιστεί ότι τα αποτελέσματα της μεθόδου μπορεί να περιέχουν θόρυβο, επειδή το σύστημα στην ουσία μαντεύει τη σχετικότητα των εγγράφων και δεν τη δηλώνει ρητά ο χρήστης. Η έμμεση ανατροφοδότηση μπορεί να υποστηριχθεί από τις ακόλουθες τεχνικές:

•

Χρησιμοποιώντας πληροφορίες από τα αποτελέσματα στα οποία ο χρήστης έχει ακολουθήσει (clickthrough) τους αντίστοιχους συνδέσμους (links), ο οποίος είναι και ο πιο συχνά χρησιμοποιούμενος τρόπος. Η τεχνική αυτή βασίζεται στο σκεπτικό ότι οι χρήστες τείνουν να ακολουθούν συνδέσμους που αναφέρονται σε σχετικά έγγραφα.
•

Χρησιμοποιώντας το χρόνο που ο χρήστης δαπανά σε κάθε έγγραφο των αποτελεσμάτων. Συνήθως, ένας χρήστης που βρίσκει ένα έγγραφο σχετικό δαπανώ περισσότερο χρόνο σε αυτό για την ανάγνωσή του. Ωστόσο, υπάρχουν και ερευνητές που δε συμφωνούν με αυτήν την υπόθεση.
•

Χρησιμοποιώντας το ιστορικό υποβολής ερωτημάτων του χρήστη (query history) ή χρησιμοποιώντας ολόκληρο το ιστορικό το οποίο περιέχει όλες τις πληροφορίες πλοήγησης. Στη βιβλιογραφία έχουν προταθεί πολλές τεχνικές προς αυτήν την κατεύθυνση.

Η τεχνική της ψευδοανατροφοδότησης επιλέγει αυτόματα κάποια έγγραφα του αποτελέσματος ως περισσότερο σχετικά από τα υπόλοιπα. Η πιο συχνή εκδοχή της τεχνικής αυτής επιλέγει τα $k$ έγγραφα του αποτελέσματος με τη μεγαλύτερη βαθμολογία υποθέτοντας ότι αυτά θα είναι και τα περισσότερο σχετικά.

10.4 Σύνοψη και Περαιτέρω Μελέτη

Η επέκταση ερωτήματος και η ανατροφοδότηση είναι δύο τεχνικές που χρησιμοποιούνται για τη βελτίωση της ποιότητας των αποτελεσμάτων ως προς τη σχετικότητά τους με τις πληροφοριακές ανάγκες των χρηστών. Πολλές φορές, εξαιτίας των φαινομένων της συνωνυμίας και της πολυσημίας, τα αποτελέσματα που λαμβάνει ο χρήστης μπορεί να διαφέρουν σημαντικά από τις πληροφοριακές του ανάγκες. Σε μία τέτοια περίπτωση θα πρέπει ο χρήστης να μπορεί να εκτελεί διορθωτικές κινήσεις ώστε βελτιώσει τη σχετικότητα των εγγράφων της απάντησης. Με την επέκταση του ερωτήματος εισάγονται νέοι όροι στο αρχικό ερώτημα με σκοπό να προσδιοριστούν καλύτερα οι πληροφοριακές ανάγκες. Η διαδκασία αυτή είναι αυτοματοποιημένη και δεν υπάρχει παρέμβαση του χρήστη. Με την (άμεση) ανατροφοδότηση ο χρήστης θα πρέπει να προσδιορίσει επακριβώς ποιά από τα έγγραφα της απάντησης είναι σχετικά και ποιά όχι.

Ο αναγνώστης μπορεί να βρει περισσότερο υλικό για το θέμα σε κεφάλαια βιβλίων. Επιπλέον, υπάρχουν πολλές επιστημονικές εργασίες που μελετούν τη μετατροπή ερωτήματος και την ανατροφοδότηση σχετικότητας, όπως οι [78] και [40]. Τέλος, η εργασία [53] περιέχει μία αναλυτική παρουσίαση της ανατροφοδότησης όπως εφαρμόζεται στα συστήματα Ανάκτησης.

10.5 Ασκήσεις

10.1

Ποιά η χρησιμότητα της επέκτασης του ερωτήματος και της ανατροφότησης;
10.2

Να εξηγήσετε τις διαφορές μεταξύ τοπικής και γενικευμένης ανάλυσης για την επέκτασης ενός ερωτήματος.
10.3

Ποιά η χρησιμότητα του θησαυρού ομοιοτήτων;
10.4

Ποιές είναι οι βασικές μορφές ανατροφοδότησης;
10.5

Να περιγράψετε τη διαδικασία της άμεσης ανατροφοδότησης στο διανυσματικό μοντέλο ανάκτησης.
10.6

Να περιγράψετε τη διαδικασία της άμεσης ανατροφοδότησης στο πιθανοκρατικό μοντέλο ανάκτησης.
10.7

Να αναζητήσετε πληροφορίες σχετικά με την υποστήριξη ανατροφοδότησης από τις σύγχρονες μηχανές αναζήτησης.
10.8

Ποιές τιμές πρέπει να δώσουμε στις παραμέτρους $\alpha$ , $\beta$ και $\gamma$ στον τύπο του Rochio ώστε να πάρουμε σελίδες σχετικές με μία συγκεκριμένη σελίδα των αποτελέσματων;