Πιθανοτικό Μοντέλο Ανάκτησης (Probabilistic Model of Retrieval)


Η βασική διαφορά μεταξύ ενός συστήματος ανάκτησης πληροφοριών και οποιουδήποτε άλλου συστήματος είναι το χαρακτηριστικό της αβεβαιότητας. Εδώ δεν υπάρχει ένα μοναδικό ερώτημα το οποίο να παριστά κατά μοναδικό τρόπο μια πληροφοριακή ανάγκη ούτε υπάρχει σαφής διάκρισης αν μια απάντηση ενός τέτοιου συστήματος είναι η σωστή ή όχι. Για να προσεγγίσουμε αυτή την αβεβαιότητα που υπάρχει όσο αφορά την παράσταση της πληροφορίας έχουν αναπτυχθεί διάφορα πιθανοτικά μοντέλα. Με τη προσέγγιση αυτή, που ξεκίνησε από το Cambridge University τη δεκαετία του 70, υπολογίζονται στατιστικά στοιχεία των συχνοτήτων, λέξεων και κειμένων, τα οποία δίνονται ως παράμετροι εισόδου σ’ ένα Bayesian μοντέλο και έτσι υπολογίζεται πόσο σχετικό είναι ένα κείμενο σε ένα ερώτημα. Η έρευνα αυτή είχε ως αποτέλεσμα την κατασκευή μηχανών αναζήτησης όπως είναι το σύστημα Okapi (City University) και το IN-QUERY (University of Massachusett). Αν και οι μέθοδοι ανάκτησης κειμένων, όπως για παράδειγμα το Διανυσματικό Μοντέλο Ανάκτησης, βασίζονται σε συχνότητες λέξεων, το μέγεθος (score) ομοιότητας που αποδίδεται σε ένα κείμενο δεν είναι πιθανότητα σχετικότητας του κειμένου προς το ερώτημα αλλά απλά είναι ένα «βάρος» που δίδει μια ένδειξη αν το κείμενο είναι σχετικό ή όχι. Το πιθανολογικό μοντέλο ανάκτησης βασίζεται στον υπολογισμό της πιθανότητας ένα κείμενο να είναι σχετικό με ένα ερώτημα δοθέντων κάποιων χαρακτηριστικών ή ιδιοτήτων του κειμένου. Τα χαρακτηριστικά αυτά είναι λέξεις ή φράσεις που περιέχει το κείμενο. Με το πιθανολογικό μοντέλο κάνουμε δύο βασικές υποθέσεις:
  1. Κάθε κείμενο είναι είτε σχετικό είτε μη σχετικό με ένα δοθέν ερώτημα και
  2. Η σχετικότητα ή μη ενός κειμένου δεν μας λέει τίποτα για τη σχετικότητα ή μη ενός άλλου κειμένου, δηλαδή δεν έχουμε «βαθμό σχετικότητας» για τα κείμενα καθώς επίσης το γεγονός ότι ένα κείμενο είναι σχετικό σ’ ένα ερώτημα δεν σημαίνει ότι μπορούμε να εξαγάγουμε κάποια πληροφορία της σχετικότητας για ένα άλλο κείμενο.
Ο υπολογισμός της πιθανότητας σχετικότητας ενός κειμένου μας βοηθά ώστε να ταξινομήσουμε τα κείμενα σύμφωνα με το πόσο χρήσιμα μπορεί να είναι στον χρήστη. Ας υποθέσουμε ότι η σχετικότητα ενός κειμένου σε ένα ερώτημα είναι ανεξάρτητη από τ' άλλα κείμενα τη συλλογής. Αν η απάντηση ενός συστήματος σ' ένα ερώτημα είναι μια διατεταγμένη σε φθίνουσα σειρά λίστα κειμένων ως προς την πιθανότητα σχετικότητας, όπου οι πιθανότητες υπολογίζονται όσο το δυνατόν καλύτερα με βάση κάποια δεδομένα τότε η αποτελεσματικότητα του συστήματος θα είναι η καλύτερη δυνατή με βάση αυτά τα δεδομένα. Η υπόθεση ότι η σχετικότητα ενός κειμένου είναι ανεξάρτητη από τα υπόλοιπα κείμενα δεν ισχύει όπως προκύπτει αν έχουμε ομαδοποίηση των κειμένων. Εν πάσει περιπτώσει πάνω σ' αυτές τις αρχές βασίζεται το πιθανολογικό μοντέλο ανάκτησης. Για να υπολογίσουμε την πιθανότητα ένα κείμενο να είναι σχετικό δεν είναι απλό πράγμα γιατί δεν γνωρίζουμε ποια είναι τα σχετικά κείμενα ούτε πόσα είναι και έτσι δεν έχουμε ένα τρόπο να υπολογίσουμε την πιθανότητα αυτή. Εκείνο το οποίο μπορούμε να κάνουμε είναι να υποθέσουμε την πιθανότητα και μετά να την βελτιώσουμε με μια επαναληπτική διαδικασία. Στα επόμενα θα υποθέσουμε ότι τα στατιστικά δεδομένα για τα σχετικά και τα μη σχετικά είναι διαθέσιμα. Ωστόσο θα πρέπει να μας ανησυχεί το γεγονός ότι σε μια πραγματική περίπτωση οι πληροφορίες σχετικότητας θα πρέπει να τις υποθέσουμε ή με κάποιο τρόπο να τις προσεγγίσουμε. Παρακάτω θα υπολογίσουμε την πιθανότητα ένα κείμενο να είναι σχετικό χρησιμοποιώντας το θεώρημα του Bayes το οποίο συνδέει μια πιθανότητα σχετικότητας με μια προγενέστερη πιθανότητα σχετικότητας και την πιθανότητα σχετικότητας αφού παρατηρήσουμε ένα κείμενο. Έστω το ενδεχόμενο Α το οποίο μπορεί να συμβαίνει μόνο σε συνδυασμό με ένα από τα n ενδεχόμενα Β1,Β2,...,Βn τα οποία είναι ξένα μεταξύ τους, δηλαδή tomi. Tότε το θεώρημα του Bayes δίδεται από την σχέση:
tomi

H P(Bi) ονομάζεται εκ των προτέρων πιθανότητα (a priori) του Βi, ενώ η P(Bi|A) ονομάζεται εκ των υστέρων (a posteriori) πιθανότητα του Bi. Στο βασικό πιθανολογικό μοντέλο το σύνολο των όρων που υπάρχουν σ' ένα κείμενο di παρίσταται μ' ένα δυαδικό διάνυσμα x=(x1,x2,...,xn) όπου xi=1 αν ti ∈ di και xi=0 αν ti ∈ di. Έστω τώρα τα ενδεχόμενα: B1: το κείμενο είναι σχετικό B2: το κείμενο δεν είναι σχετικό. Εκείνο που θέλουμε να υπολογίσουμε είναι το P(B1|x) ή το P(B2|x). Επειδή δεν μπορούμε να υπολογίσουμε το P(B1|x) ή το P(B2|x) απ' ευθείας θα πρέπει να βρούμε ένα τρόπο να το προσεγγίσουμε χρησιμοποιώντας ποσότητες για τις οποίες γνωρίζουμε κάτι. Για τον υπολογισμό των P(Bi|x) χρησιμοποιούμε το θεώρημα του Bayes
bayes

όπου P(Bi) είναι η πιθανότητα σχετικότητας και το P(x|Bi) είναι ανάλογο αυτού που λέμε πιθανότητα σχετικότητας δοθέντος του x και
typos4

είναι η πιθανότητα να πάρουμε το x σε τυχαία βάση. Η απόφαση αν ένα κείμενο είναι σχετικό ή όχι γίνεται από τον εξής κανόνα απόφασης (decision rule): Aν P(B1|x) > P(B2|x) τότε το x είναι σχετικό διαφορετικά δεν είναι σχετικό. Η περίπτωση P(B1|x) = P(B2|x) αντιμετωπίζεται αυθαίρετα, έστω για παράδειγμα ότι το x δεν είναι σχετικό. Παρακάτω αντί να χρησιμοποιήσουμε τις πιθανότητες P(Bi|x) θα χρησιμοποιήσουμε τα odds που ορίζονται από:
odds

Για να υπολογίσουμε όμως τη σχέση (P(x|Bi) απαιτούνται και άλλες υποθέσεις. Και μια τέτοια υπόθεση είναι η ανεξαρτησία των όρων ενός κειμένου. Οπωσδήποτε η σχέση αυτή δεν ισχύει στη πράξη αλλά μπορεί να θεωρηθεί ως μια πρώτη προσέγγιση. Μια τέτοια υπόθεση ορίζεται από τη σχέση:
indepedence

Στα επόμενα θα συμβολίζουμε το Β1 με R και το Β2 με . Έτσι έχουμε:
odds7

ή
odds8

Έστω pi και bayes. Επιπλέον, υποθέτουμε ότι pi=qi για όλους τους όρους που δεν ανήκουν στο ερώτημα. Με αυτές τις απλοποιήσεις καταλήγουμε στη σχέση:
odds11

Στη χρησιμοποίηση της σχέσης αυτής εκείνο που έχει σημασία είναι η διάταξη των κειμένων ως προς το ερώτημα και όχι η ακριβής τιμή των πιθανοτήτων σχετικότητας. Για το λόγο αυτό επειδή το δεύτερο γινόμενο και το O(R) είναι σταθερά για κάποιο ερώτημα εκείνο που θέλουμε να υπολογίσουμε είναι το πρώτο γινόμενο. Λαμβάνοντας τον λογάριθμο του γινομένου αυτού έχουμε ότι τιμή ανάκτησης (Retrieval Status Value) του κειμένου D για το ερώτημα Q είναι:
rsv όπου ci

Έτσι τα κείμενα διατάσσονται ως προς το RSV σε φθίνουσα σειρά. Για να χρησιμοποιήσουμε τη μέθοδο που περιγράψαμε, βασικό πιθανολογικό μοντέλο, (Binary Independence Retrieval Model) αρκεί να υπολογίσουμε τις παραμέτρους pi και qi για τους όρους ti ∈ Q. Αυτό μπορεί να γίνει με τη διαδικασία της ανάδρασης σχετικότητας (Relevance Feedback). Έστω ότι το σύστημα έχει ανακτήσει μερικά κείμενα για το ερώτημα Q. Τότε ο χρήστης ερωτάται να δώσει κάποια αξιολόγηση σχετικότητας για τα κείμενα αυτά. Από αυτή την αξιολόγηση υπολογίζουμε τις παραμέτρους του μοντέλου. Έστω ότι το σύστημα ανάκτησε f κείμενα εκ των οποίων τα r αξιολογήθηκαν από τον χρήστη ως σχετικά. Για κάποιο όρο ti, έστω fi είναι το πλήθος των κειμένων που περιέχουν τον όρο και ri το πλήθος των σχετικών κειμένων που τον περιέχουν. Τότε έχουμε:
res

Παράδειγμα Έστω Qt=(t1,t2) και έστω ότι έχουμε 20 κείμενα όπως φαίνονται στο παρακάτω πίνακα. Τότε έχουμε:
res15


res16


example


example

Tα RSV υπολογίζονται λαμβάνοντας ως O(R)=12/8 όπως φαίνεται από τον πίνακα. Με τα βάρη αυτά τα κείμενα διατάσσονται σε σχέση με το αντίστοιχό τους δυαδικό διάνυσμα x ως εξής: (1,1) - (1,0) - (0,1) - (0,0) Προφανώς η διάταξη αυτή είναι και η ορθή για το παράδειγμά μας.