Ανάκτηση Πληροφορίας 4 Το Διανυσματικό Μοντέλο 6 Ο Αντεστραμμένος Κατάλογος

Κεφάλαιο 5Το Πιθανοκρατικό Μοντέλο

5.1 Εισαγωγή

Στο κεφάλαιο αυτό, εξετάζουμε το τρίτο μοντέλο ανάκτησης της κατηγορίας των Κλασικών μοντέλων το οποίο χαρακτηρίζεται από τη μαθηματική του θεμελίωση με τη βοήθεια της Θεωρίας Πιθανοτήτων. Αυτός είναι και ο βασικός λόγος για τον οποίο καλείται Πιθανοκρατικό (probabilistic) μοντέλο ανάκτησης. Είναι το πρώτο προτεινόμενο μοντέλο ανάκτησης που στηρίζεται σε πιθανότητες. Η χρήση της Θεωρίας Πιθανοτήτων στην ανάκτηση πληροφορίας προτάθηκε για πρώτη φορά από τους Maron και Kuhns το 1960 [42], ενώ η εργασία των Robertson και Sparck Jones [50] θεωρείται σταθμός για την πιθανοκρατική ανάκτηση πληροφορίας (probabilistic information retrieval).

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

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

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

5.2 Βασικές Έννοιες Θεωρίας Πιθανοτήτων

Στο σημείο αυτό θεωρείται σκόπιμο να παρατεθεί μία συνοπτική παρουσίαση των βασικών αρχών της Θεωρίας Πιθανοτήτων, οι οποίες θα χρησιμοποιηθούν για την περιγραφή του Πιθανοκρατικού μοντέλου. Αν $a$ είναι κάποιο γεγονός, τότε η πιθανότητα να συμβεί το γεγονός αυτό συμβολίζεται με $P(a)$ . Με βάση τη Θεωρία Πιθανοτήτων ισχύει: $0\leq P(a)\leq 1$ . Ακολουθούν δύο σημαντικοί ορισμοί:

Ορισμός 5.1.

(ανεξάρτητα γεγονότα)
Δύο γεγονότα θεωρούνται ανεξάρτητα όταν η εμφάνιση του ενός δεν επηρεάζεται από την εμφάνιση ή μη εμφάνιση του άλλου.

Ορισμός 5.2.

(υπό συνθήκη πιθανότητα)
Η υπό συνθήκη πιθανότητα του γεγονότος $a$ ως προς το γεγονός $b$ συμβολίζεται με $P(a|b)$ και εκφράζει την πιθανότητα να συμβεί το γεγονός $a$ δεδομένου ότι έχει συμβεί το γεγονός $b$ .

Θεώρημα 5.1.

Δύο γεγονότα $a$ και $b$ είναι ανεξάρτητα αν και μόνο αν $P(a\cap b)$ = $P(a)\cdot P(b)$ .

Θεώρημα 5.2.

Τα γεγονότα $a_{1}$ , $a_{2}$ , …, $a_{n}$ είναι υπο συνθήκη ανεξάρτητα αν και μόνο αν $\forall a_{i},a_{j}$ , $P(a_{i}|a_{j})$ = $P(a_{i})$ .

Παράδειγμα 5.1

Στο Σχήμα 5.1 δίνονται τα γεγονότα $a$ και $b$ . Με $\lnot a$ και $\lnot b$ συμβολίζονται οι αρνήσεις των γεγονότων αυτών. Προφανώς ισχύει ότι $P(\lnot a)$ = 1 - $P(a)$ και $P(\lnot b)$ = 1 - $P(b)$ . Έστω $\gamma_{1}$ , $\gamma_{2}$ , $\gamma_{3}$ και $\gamma_{4}$ τα γεγονότα που σχηματίζονται όπως φαίνεται στο Σχήμα 5.1. Αν συμβολίσουμε με $n(\gamma_{i})$ το πλήθος των στοιχείων που ικανοποιούν το γεγονός $\gamma_{i}$ και $N$ ο συνολικός αριθμός των στοιχείων, τότε έχουμε: $P(a)$ = $(n(\gamma_{2})+n(\gamma_{3}))/N$ , $P(b)$ = $(n(\gamma_{1})+n(\gamma_{2}))/N$ . Είναι προφανές ότι τα γεγονότα $a$ και $b$ δεν είναι ανεξάτητα. Για να το δούμε αυτό θα υπολογίσουμε την υπό συνθήκη πιθανότητα να συμβεί το γεγονός $a$ δεδομένου ότι έχει συμβεί το γεγονός $b$ . Σύμφωνα με την προηγούμενη συζήτηση, η ποσότητα αυτή συμβολίζεται με $P(a|b)$ . Είναι προφανές ότι: $P(a|b)=n(\gamma_{2})/(n(\gamma_{1})+n(\gamma_{2}))$ . Από την τελευταία σχέση έχουμε: $P(a|b)\cdot(n(\gamma_{1})+n(\gamma_{2}))=n(\gamma_{2})$ και επομένως ισχύει ότι $P(a|b)\cdot P(b)$ = $P(a\cap b)$ .

Σχήμα 5.1: Γεγονότα που δεν είναι ανεξάρτητα.

$\square$

Παράδειγμα 5.2

Έστω ότι έχουμε στη διάθεσή μας δύο δίκαια ζάρια (η πιθανότητα να φέρουμε ένα από τα 6 νούμερα είναι ίδια). Είναι προφανές, ότι αν ρίξουμε διαδόχικά τα ζάρια, η τιμή του δεύτερου ζαριού δεν εξαρτάται από την τιμή του πρώτου. Για παράδειγμα, αν συμβολίσουμε τα ζάρια με $\zeta_{1}$ και $\zeta_{2}$ τότε η πιθανότητα το δεύτερο ζάρι να φέρει 6 δεδομένου ότι το πρώτο ζάρι έφερε 4 είναι $P(\zeta_{2}=6|\zeta_{1}=4)$ = $P(\zeta_{2}=6)$ = 1/6, εφόσον τα δύο γεγονότα είναι ανεξάρτητα. Έστω τώρα $\zeta=\zeta_{1}+\zeta_{2}$ το άθροισμα των τιμών των δύο ζαριών. Η πιθανότητα το άθροισμα των τιμών να είναι 6 δεδομένου ότι το πρώτο ζάρι έχει φέρει 4 είναι $P(\zeta=6|\zeta_{1}=4)$ = 1/6, αφού για να πάρουμε το επιθυμητό άθροισμα θα πρέπει το δεύτερο ζάρι να φέρει 2. Ομοίως έχουμε $P(\zeta=4|\zeta_{1}=3)$ = 1/6 ενώ $P(\zeta=9|\zeta_{1}=2)$ = 0. $\square$

Θεώρημα 5.3.

Έστω $a$ και $b$ δύο γεγονότα. Τότε οι ποσότητες $P(a|b)$ , $P(b|a)$ , $P(a)$ και $P(b)$ συνδέονται με την ακόλουθη σχέση που είναι γνωστή και ως νόμος ή κανόνας του Bayes:

P(a|b)=\frac{P(b|a)\cdot P(a)}{P(b)}

(5.1)

Σε περίπτωση που ο χώρος γεγονότων μπορεί να διαμεριστεί στα γεγονότα $\gamma_{1}$ , $\gamma_{2}$ , …, $\gamma_{n}$ τότε ο κανόνας του Bayes παίρνει την ακόλουθη μορφή:

P(\gamma_{i}|b)=\frac{P(b|\gamma_{i})\cdot P(\gamma_{i})}{\sum_{j=1}^{n}(P(b|% \gamma_{j})\cdot P(\gamma_{j}))}

(5.2)

5.3 Υπολογισμός Σχετικότητας Εγγράφων

Η βαθμολόγηση των εγγράφων με βάση το Πιθανοκρατικό μοντέλο ανάκτησης βασίζεται στην Αρχή Πιθανοκρατικής Βαθμολόγησης (probability ranking principle)³³Θεωρουμε σκόπιμο να δώσουμε και τον αρχικό ορισμό της αρχής, όπως παρουσιάζεται στην εργασία [52], και η οποία αποδίδεται στον W.S. Cooper αν και έχει διατυπωθεί νωρίτερα από τον Maron [43]. Η αρχή αναφέρει ότι: ”If a reference retrieval system’s response to each request is a ranking of the documents in the collection in order of decreasing probability of relevance to the user who submitted the request, where the probabilities are estimated as accurately as possible on the basis of whatever data have been made available to the system for this purpose, the overall effectiveness of the system to its user will be the best that is obtainable on the basis of those data”. η οποία αναφέρει ότι: εάν η απάντηση ενός συστήματος ανάκτησης σε κάθε ερώτημα είναι μία λίστα εγγράφων ταξινομημένη με φθίνουσα διάταξη ως προς την πιθανότητα σχετικότητας του κάθε εγγράφου ως προς το χρήστη, όπου οι πιθανότητες υπολογίζονται όσο γίνεται ακριβέστερα με βάση τα δεδομένα που είναι διαθέσιμα, η συνολική αποτελεσματικότητα του συστήματος θα είναι η καλύτερη δυνατή.

Δοθέντος ενός ερωτήματος $q$ , η μέθοδος επεξεγασίας του ερωτήματος προσπαθεί να εντοπίσει έγγραφα που είναι σχετικά ως προς το $q$ και να αγνοήσει τα υπόλοιπα. Συμβολίζουμε με $\cal R$ το σύνολο των σχετικών εγγράφων ως προς κάποιο ερώτημα $q$ και με $\lnot{\cal R}$ το σύνολο των μη σχετικών εγγράφων. Βασικός στόχος του Πιθανοκρατικού μοντέλου είναι ο προσδιορισμός της πιθανότητας ένα έγγραφο $d$ να ανήκει στο σύνολο των σχετικών εγγράφων $R$ . Την πιθανότητα αυτή μπορούμε να την εκφράσουμε ως $P({\cal R}|d)$ που δηλώνει την πιθανότητα το έγγραφο $d$ να ανήκει στο σύνολο των σχετικών εγγράφων. Ομοίως ορίζεται η πιθανότητα $P(\lnot{\cal R}|d)$ . Προφανώς ισχύει ότι $P(\lnot{\cal R}|d)=1-P({\cal R}|d)$ . Στη συνέχεια, αναφέρουμε μερικές παραδοχές που απαιτούνται για τη λειτουργία του Πιθανοκρατικού μοντέλου:

•

Η πιθανότητα ένα έγγραφο να είναι σχετικό ως προς το ερώτημα θεωρείται ότι εξαρτάται μόνο από τους όρους που περιέχονται στο έγγραφο και από τους όρους που περιέχονται στο ερώτημα.
•

Η σχετικότητα ενός εγγράφου $d$ ως προς το ερώτημα $q$ δεν εξαρτάται από τη σχετικότητα άλλων εγγράφων της συλλογής.
•

Για κάποιο ερώτημα $q$ το σύνολο των σχετικών εγγράφων ${\cal R}$ είναι το ιδανικό σύνολο που μπορούμε να έχουμε ως απάντηση.

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

σύμβολο	περιγραφή
$N$	πλήθος εγγράφων της συλλογής
${\cal R}$	σύνολο σχετικών εγγράφων ως προς το ερώτημα $q$
$R$	πλήθος σχετικών εγγράφων ( $R=\|\cal R\|$ )
$t$ , $t_{i}$	ο όρος $t$ , ο $i$ -οστός όρος ( $t_{i}$ )
$d$ , $d_{j}$	το έγγραφο $d$ , το $j$ -οστό έγγραφο της συλλογής ( $d_{j}$ )
$q$	έγγραφο ερωτήματος
$r_{i}$	πλήθος σχετικών εγγράφων που περιέχουν τον όρο $t_{i}$
$n_{i}$	πλήθος εγγράφων που περιέχουν τον όρο $t_{i}$
$f_{t,d}$	αριθμός εμφανίσεων του όρου $t$ στο έγγραφο $d$
$f_{t,q}$	αριθμός εμφανίσεων του όρου $t$ στο ερώτημα $q$
$P(a)$	πιθανότητα να συμβεί το γεγονός $a$
$P(a\|b)$	πιθανότητα να συμβεί το $a$ δεδομένου του $b$
$P({\cal R}\|d)$	πιθανότητα το έγγραφο $d$ να είναι σχετικό
$P(\lnot{\cal R}\|d)$	πιθανότητα το έγγραφο $d$ να μην είναι σχετικό
$P(d\|{\cal R})$	πιθανότητα τυχαίας επιλογής του $d$ από το σύνολο ${\cal R}$
$P(d\|\lnot{\cal R})$	πιθανότητα τυχαίας επιλογής του $d$ από το σύνολο $\lnot{\cal R}$
$L_{q}$ , $L_{d}$	μήκος ερωτήματος και εγγράφου της συλλογής
$C$ , $C_{1}$ , $C_{2}$ , $C_{3}$ , $b$	σταθερές
$S_{prob}(q,d)$	συνάρτηση ομοιότητας απλού πιθανοκρατικού μοντέλου
$S_{BM25}(q,d)$	συνάρτηση ομοιότητας κατά BM25
$S_{infer}(q,d)$	συνάρτηση ομοιότητας μοντέλου δικτύου συμπερασμάτων
$S_{belief}(q,d)$	συνάρτηση ομοιότητας μοντέλου δικτύου πίστης

Πίνακας 5.1: Σύμβολα και περιγραφές.

5.3.1 Μέτρο Ομοιότητας

Ο βαθμός ομοιότητας μεταξύ ενός εγγράφου $d$ και ενός ερωτήματος $q$ ορίζεται ως ο λόγος των πιθανοτήτων το $d$ να είναι σχετικό προς την πιθανότητα το $d$ να μην είναι σχετικό. Ο λόγος χρησιμοποιείται για να αμβλύνει τα αποτελέσματα κάποιας λανθασμένης πρόβλεψης [27, 75]. Πιο συγκεκριμένα, αν συμβολίσουμε με $S_{prob}(q,d)$ τη συνάρτηση που επιστρέφει την ομοιότητα μεταξύ $q$ και $d$ τότε:

S_{prob}(q,d)=\frac{\mbox{πιθανότητα το $d$ να είναι σχετικό}}{\mbox{πιθανότητ% α το $d$ να είναι μη σχετικό}}=\frac{P({\cal R}|d)}{P(\lnot{\cal R}|d)}

(5.3)

Με εφαρμογή του θεωρήματος του Bayes στον αριθμητή και παρονομαστή του κλάσματος της παραπάνω σχέσης, η συνάρτηση ομοιότητας γράφεται ως εξής:

[S_{prob}(q,d)=\frac{P(d|{\cal R})\cdot P({\cal R})}{P(d|\lnot{\cal R})\cdot P% (\lnot{\cal R})}]

(5.4)

όπου $P(d|{\cal R})$ είναι η πιθανότητα να διαλέξουμε τυχαία το $d$ μέσα από το σύνολο των σχετικών εγγράφων ${\cal R}$ . Με μία προσεκτική ματιά στην εξίσωση 5.4 παρατηρούμε ότι το κλάσμα $P({\cal R})/P(\lnot{\cal R})$ έχει τιμή σταθερή για κάθε ερώτημα, και εφόσον δεν επηρεάζει την τελική κατάταξη των εγγράφων δεν είναι απαραίτητο να υπολογιστεί. Επομένως, η συνάρτηση ομοιότητας επαναπροσδιορίζεται ως εξής:

S_{prob}(q,d)\propto\frac{P(d|{\cal R})}{P(d|\lnot{\cal R})}

(5.5)

Αρχικά το Πιθανοκρατικό μοντέλο βασίστηκε στο συνδυασμό της Αρχής Πιθανοκρατικής Βαθμολόγησης και της Ανάκτησης Δυαδικής Ανεξαρτησίας (binary independence retrieval). Η δεύτερη αναφέρει ότι τα βάρη των όρων είναι δυαδικά και ότι οι όροι είναι ανεξάρτητοι μεταξύ τους (η παρουσία ή μη κάποιου όρου δεν επηρεάζει τους υπόλοιπους). Στην ουσία, αυτός είναι και ο τρόπος θεώρησης του απλού Λογικού μοντέλου. Το βάρος ενός όρου σε ένα έγγραφο είναι είτε 1 (αν ο όρος περιέχεται στο έγγραφο) είτε 0 (σε διαφορετική περίπτωση). Επομένως, ένα έγγραφο $d$ μπορεί να εκφραστεί ως διάνυσμα βαρών, όπου η κάθε συνιστώσα αναφέρεται στην παρουσία ή απουσία του όρου στο έγγραφο. Έτσι, αν συμβολίσουμε με $\vec{d}$ το διάνυσμα των βαρών του εγγράφου $d$ , με $M$ το πλήθος των μοναδικών όρων της συλλογής εγγράφων και με $w_{t_{i},d}$ το βάρος του όρου $t_{i}$ στο έγγραφο $d$ , τότε έχουμε:

\vec{d}=(w_{t_{1},d},w_{t_{2},d},...,w_{t_{M},d})

(5.6)

Το διάνυσμα $\vec{d}$ μπορεί να χρησιμοποιηθεί ως προσέγγιση της πληροφορίας που περιέχεται στο έγγραφο $d$ και προσφέρει ένα βολικό τρόπο για να εκτιμήσουμε την ποσότητα $P(d|{\cal R})$ με χρήση της ποσότητας $P(\vec{d}|{\cal R})$ . Από τη σχέση 5.7 έχουμε:

S_{prob}(q,d)\propto\frac{P(\vec{d}|{\cal R})}{P(\vec{d}|\lnot{\cal R})}

(5.7)

Λαμβάνοντας υπόψη την ανεξαρτησία των όρων ισχύει ότι $P(\vec{d}|{\cal R})$ = $P(w_{t_{1},d}|{\cal R})$ $\cdot$ $P(w_{t_{2},d}|{\cal R})$ $\cdot$ , …, $\cdot$ $P(w_{t_{M},d}|{\cal R})$ . Ο τύπος υπολογισμού της ομοιότητας γίνεται:

S_{prob}(q,d)\propto\prod_{i=1}^{M}\frac{P(w_{t_{i},d}|{\cal R})}{P(w_{t_{i},d% }|\lnot{\cal R})}

(5.8)

Διαχωρίζουμε τους όρους από $t_{1}$ έως $t_{M}$ σε δύο κατηγορίες, αυτούς που περιέχονται στο έγγραφο $d$ και σε αυτούς που δεν περιέχονται στο έγγραφο $d$ . Αντικαθιστώντας στην εξίσωση 5.8 παίρνουμε:

S_{prob}(q,d)\propto\prod_{\forall i,w_{t_{i},d}=1}\frac{P(w_{t_{i},d}=1|{\cal R% })}{P(w_{t_{i},d}=1|\lnot{\cal R})}\cdot\prod_{\forall i,w_{t_{i},d}=0}\frac{P% (w_{t_{i},d}=0|{\cal R})}{P(w_{t_{i},d}=0|\lnot{\cal R})}

(5.9)

Υποθέτουμε ότι οι όροι που δεν εμφανίζονται στο ερώτημα $q$ έχουν την ίδια πιθανότητα να βρίσκονται ή όχι στα έγγραφα του ${\cal R}$ (σχετικά έγγραφα). Χρησιμοποιώντας την υπόθεση αυτή το μέτρο ομοιότητας γίνεται:

S_{prob}(q,d)\propto\prod_{\begin{subarray}{c}\forall i,\\ w_{t_{i},d}=1~{}\land\\ w_{t_{i},q}=1\end{subarray}}\frac{P(w_{t_{i},d}=1|{\cal R})}{P(w_{t_{i},d}=1|% \lnot{\cal R})}\cdot\prod_{\begin{subarray}{c}\forall i,\\ w_{t_{i},d}=0~{}\land\\ w_{t_{i},q}=1\end{subarray}}\frac{1-P(w_{t_{i},d}=1|{\cal R})}{1-P(w_{t_{i},d}% =1|\lnot{\cal R})}

(5.10)

Για να απλούστευση της συνάρτησης ομοιότητας πραγματοποιούνται οι αντικαταστάσεις $p_{i}$ = $P(w_{t_{i},d}=1|{\cal R})$ και $u_{i}$ = $P(w_{t_{i},d}=1|\lnot{\cal R})$ , οπότε η συνάρτηση ομοιότητας παίρνει την ακόλουθη μορφή:

S_{prob}(q,d)\propto\prod_{\begin{subarray}{c}\forall i,\\ w_{t_{i},d}=1~{}\land\\ w_{t_{i},q}=1\end{subarray}}\frac{p_{i}}{u_{i}}\cdot\prod_{\begin{subarray}{c}% \forall i,\\ w_{t_{i},d}=0~{}\land\\ w_{t_{i},q}=1\end{subarray}}\frac{1-p_{i}}{1-u_{i}}

(5.11)

Από το δεύτερο γινόμενο διαγράφουμε τους όρους που δε βρίσκονται στο έγγραφο $d$ ενώ βρίσκονται στο ερώτημα $q$ . Αν γίνει αυτό, τότε στο γινόμενο θα συμμετέχουν κλάσματα της μορφής $(1-p_{i})/(1-u_{i})$ και για τους όρους που περιέχονται στο έγγραφο $d$ και για τους όρους που δεν περιέχονται. Επειδή όμως το πρώτο γινόμενο περιλαμβάνει τις περιπτώσεις που οι όροι εμφανίζονται στο έγγραφο, θα πρέπει να μεταβληθεί το πρώτο γινόμενο όπως φαίνεται στην παρακάτω σχέση:

S_{prob}(q,d)\propto\prod_{\begin{subarray}{c}\forall i,\\ w_{t_{i},d}=1~{}\land\\ w_{t_{i},q}=1\end{subarray}}\frac{p_{i}\cdot(1-u_{i})}{u_{i}\cdot(1-p_{i})}% \cdot\prod_{\begin{subarray}{c}\forall i,\\ w_{t_{i},q}=1\end{subarray}}\frac{1-p_{i}}{1-u_{i}}

(5.12)

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

S_{prob}(q,d)\propto\log\left(\prod_{\begin{subarray}{c}\forall i,\\ w_{t_{i},d}=1~{}\land\\ w_{t_{i},q}=1\end{subarray}}\frac{p_{i}\cdot(1-u_{i})}{u_{i}\cdot(1-p_{i})}% \right)\Rightarrow\\

(5.13)

S_{prob}(q,d)\propto\sum_{\begin{subarray}{c}\forall i,\\ w_{t_{i},d}=1~{}\land\\ w_{t_{i},q}=1\end{subarray}}\log\frac{p_{i}\cdot(1-u_{i})}{u_{i}\cdot(1-p_{i})}

(5.14)

Το άθροισμα της σχέσης 5.14 αφορά σε όλους τους όρους που εμφανίζονται και στο έγγραφο και στο ερώτημα. Αν συμβολίσουμε με ${\cal T}_{d}$ το σύνολο των μοναδικών όρων του εγγράφου $d$ , με ${\cal T}_{q}$ το σύνολο των μοναδικών όρων του ερωτήματος $q$ και με ${\cal T}_{q,d}$ την τομή των δύο συνόλων, τότε παίρνουμε την παρακάτω σχέση όπου $w_{i}$ είναι το βάρος του όρου $t_{i}$ :

[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}]

(5.15)

5.3.2 Υπολογισμός της Ομοιότητας

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

	πλήθος σχετικών	πλήθος μη σχετικών	σύνολο
	εγγράφων	εγγράφων
πλήθος εγγράφων που
περιέχουν τον όρο $t_{i}$	$r_{i}$	$n_{i}-r_{i}$	$n_{i}$
πλήθος εγγράφων που δεν
περιέχουν τον όρο $t_{i}$	$R-r_{i}$	$(N-R)-(n_{i}-r_{i})$	$N-n_{i}$
σύνολο	$R$	$N-R$	$N$

Πίνακας 5.2: Πίνακας περιπτώσεων σχετικότητας εγγράφων.

Ο Πίνακας 5.2 περιέχει όλες τις δυνατές περιπτώσεις σχετικά με το αν ένα έγγραφο είναι σχετικό ή μή σχετικό, και αν το έγγραφο περιέχει ή όχι το συγκεκριμένο όρο $t_{i}$ . Με $N$ συμβολίζουμε το πλήθος των εγγράφων της συλλογής, $R$ είναι το πλήθος των σχετικών ως προς το ερώτημα εγγράφων ( $R$ = $|\cal R|$ ), $r_{i}$ είναι το πλήθος των σχετικών εγγράφων που περιέχουν τον όρο $t_{i}$ , και $n_{i}$ είναι το πλήθος των συνολικών εγγράφων (σχετικών και μή σχετικών) που περιέχουν τον όρο $t_{i}$ . Με βάση τον Πίνακα 5.2 μπορούμε να εκτιμήσουμε τις ποσότητες $p_{i}$ και $u_{i}$ ως εξής: $p_{i}$ = $r_{i}/R$ και $u_{i}$ = $(n_{i}-r_{i})/(N-R)$ . Οι δύο αυτές σχέσεις προϋποθέτουν ότι [56]: (α) η κατανομή των όρων στα έγγραφα που έχουν ανακτηθεί είναι ίδια με την κατανομή των όρων στο σύνολο των σχετικών εγγράφων, και (β) όλα τα έγγραφα που δεν έχουν ανακτηθεί θεωρούνται μή σχετικά ως προς το ερώτημα. Με αντικατάσταση των τιμών $p_{i}$ και $u_{i}$ στη σχέση που δίνει το $w_{i}$ έχουμε:

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})}

(5.16)

Παρατηρήστε ότι η σχέση 5.16 είναι προβληματική σε ορισμένες περιπτώσεις, π.χ., όταν $R$ = $r_{i}$ όπου έχουμε μηδενισμό του παρονομαστή. Για την αποφυγή των παθολογικών καταστάσεων έχει προταθεί ή χρήση κάποιας σταθεράς $C$ η οποία προστίθεται [50]. Η τιμή αυτή είναι συνήθως το 0.5 ή το $n_{i}/N$ . Με την προσθήκη της σταθεράς η σχέση υπολογισμού της ποσότητας $w_{i}$ γίνεται:

w_{i}=\log\frac{(r_{i}+C)\cdot(N-R-n_{i}-r_{i}+C)}{(n_{i}-r_{i}+C)\cdot(R-r_{i% }+C)}

(5.17)

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

5.3.3 Μέθοδος Okapi ΒΜ25

Το Okapi είναι ένα σύστημα ανάκτησης πληροφορίας που αναπτύχθηκε στο Πανεπιστήμιο City του Λονδίνου από τον Robertson και τους συνεργάτες του και που έχει χρησιμοποιηθεί ως πλατφόρμα για τη μελέτη της αποτελεσματικότητας διαφόρων μεθόδων προσδιορισμού της ομοιότητας. Μία από τις πιο αποτελεσματικές μεθόδους υπολογισμού της ομοιότητας που έδωσε πολύ καλά αποτελέσματα στις συλλογές εγγράφων TREC είναι η μέθοδος BM25 ⁴⁴Το BM προκύπτει από τις λέξεις Best Match. που μελετάται στην εργασία [49]. Στην ουσία, πρόκειται για συνδυασμό των συναρτήσεων ομοιότητας BM11 και BM15 που είχαν μελετηθεί στην εργασία [51]. Ακολουθεί μία συνοπτική περιγραφή της μεθόδου BM25.

Η μέθοδος BM25 στηρίζεται στη χρήση δύο κατανομών Poisson. Σύμφωνα με αυτήν, ένα έγγραφο θεωρείται ως μία τυχαία ροή εμφανίσεων όρων. Κάθε εμφάνιση ενός όρου $t$ θεωρείται ένα γεγονός που αφορά στον όρο $t$ . Θεωρούμε ότι ο επόμενος όρος του εγγράφου θα είναι ο όρος $t$ με πιθανότητα $p$ (επομένως 1- $p$ είναι η πιθανότητα ο επόμενος όρος του εγγράφου να είναι διαφορετικός του $t$ ). Αν συμβολίσουμε με $\mathbb{X}$ την τυχαία μεταβλητή που μας δίνει τον αριθμό των εμφανίσεων του όρου $t$ στο έγγραφο, τότε η πιθανότητα να συμβούν $x$ εμφανίσεις του όρου $t$ σε ένα έγγραφο που αποτελείται από $k$ όρους προσδιορίζεται από την διωνυμική κατανομή, σύμφωνα με τον τύπο:

P[\mathbb{X}=x]={\left({{k}\atop{x}}\right)}\cdot p^{x}\cdot(1-p)^{k-x}

(5.18)

Για πολύ μικρές τιμές της πιθανότητας $p$ και πολύ μεγάλες τιμές του $k$ , η διωνυμική κατανομή προσεγγίζεται με ικανοποιητική ακρίβεια από την κατανομή Poisson. Αν $\mu$ είναι η μέση τιμή της τυχαίας μεταβλητής $\mathbb{X}$ , τότε έχουμε:

P[\mathbb{X}=x]\approx\frac{e^{-\mu}\cdot\mu^{x}}{x!}

(5.19)

Για τη χρήση της συχνότητας εμφάνισης των όρων στα έγγραφα γίνεται η υπόθεση ότι η συχνότητα εμφάνισης ενός όρου $t$ ακολουθεί επίσης την κατανομή Poisson. Τα έγγραφα που περιέχουν τον όρο $t$ διαχωρίζονται σε δύο κατηγορίες: στα έγγραφα που θεωρούνται εκλεκτά ως προς τον όρο $t$ (δηλαδή αναφέρονται στο θέμα στο οποίο αναφέρεται και ο $t$ ) και στα έγγραφα που θεωρούνται μη εκλεκτά ως προς τον όρο $t$ . Υποθέτουμε λοιπόν ότι η συχνότητα εμφάνισης του όρου $t$ στις δύο κατηγορίες εγγράφων ακολουθεί την κατανομή Poisson αλλά με διαφορετικές μέσες τιμές για την κάθε περίπτωση. Έστω $\mathbb{Y}$ η τυχαία μεταβλητή που μας δίνει τη συχνότητα εμφάνισης του όρου $t$ . Τότε έχουμε:

P[\mathbb{Y}=y]=\frac{e^{\lambda_{1}}\cdot\lambda_{1}^{y}}{y!}

(5.20)

P[\mathbb{Y}=y]=\frac{e^{\lambda_{2}}\cdot\lambda_{2}^{y}}{y!}

(5.21)

όπου $\lambda_{1}$ και $\lambda_{2}$ είναι η μέση τιμή της πιθανότητας για την περίπτωση των εκλεκτών και μή εκλεκτών εγγράφων αντίστοιχα. Με βάση τη μελέτη της εργασίας [49], δίνουμε στη συνέχεια τη συνάρτηση που υπολογίζει το βαθμό ομοιότητας μεταξύ ενός ερωτήματος $q$ και ενός εγγράφου της συλλογής $d$ .

S_{BM25}(q,d)=\sum_{\forall i,t_{i}\in{\cal T}_{q}}\log\frac{(r_{i}+0.5)\cdot(% N-R-n_{i}-r_{i}+0.5)}{(n_{i}-r_{i}+0.5)\cdot(R-r_{i}+0.5)}\cdot

(5.22)

\cdot\frac{(C_{1}+1)\cdot f_{t_{i},d}}{C_{4}+f_{t_{i},d}}\cdot\frac{(C_{3}+1)% \cdot f_{t_{i},q}}{C_{3}+f_{t_{i},q}}+C_{2}\cdot|q|\cdot\frac{avdl-dl_{d}}{% avdl+dl_{d}}

(5.23)

Στον παραπάνω τύπο, οι $C_{1}$ , $C_{2}$ , $C_{3}$ και $C_{4}$ είναι σταθερές ρύθμισης. Η σταθερά $C_{4}$ ισούται με $C_{4}$ = $C_{1}\cdot((1-b)+b\cdot(dl/avdl))$ , όπου $b$ είναι μία άλλη ρυθμιστική σταθερά. Επίσης, $dl_{d}$ είναι το μήκος του εγγράφου $d$ και $a v d l$ είναι το μέσο μήκος των εγγράφων της συλλογής. Παρατηρήστε ότι η συνάρτηση ομοιότητας περιέχει αρκετές ρυθμιστικές σταθερές. Για τον τρόπο παραγωγής της μεθόδου BM25 καθώς και για τις τιμές των σταθερών που έχουν μελετηθεί παραπέμπουμε τον αναγνώστη στις εργασίες [51, 49] όπου υπάρχουν όλες οι σχετικές πληροφορίες, καθώς και πειραματικά αποτελέσματα αποτελεσματικότητας συγκριτικά με παλαιότερες προσεγγίσεις.

5.4 Ανάκτηση με Χρήση Δικτύων Bayes

Η χρήση των δικτύων Bayes (Bayesian networks) στην ανάκτηση πληροφορίας προτάθηκε για πρώτη φορά από τους Turtle και Croft το 1990 [74]. Σύμφωνα με το μοντέλο αυτό, οι όροι, τα έγγραφα της συλλογής και τα ερωτήματα χαρακτηρίζονται ως γεγονότα και αναπαριστώνται ως κόμβοι ενός δικτύου Bayes. Το μοντέλο αυτό καλείται μοντέλο δικτύου συμπερασμάτων (inference network model), και σύμφωνα με τα πειραματικά αποτελέσματα έχει καλύτερη επίδοση από άλλα πιθανοκρατικά μοντέλα ανάκτησης. Αργότερα, οι Ribeiro-Neto και Muntz [48] γενίκευσαν την προσέγγιση των Turtle και Croft με αποτέλεσμα να προκύψει ένα νέο μοντέλο, το οποίο καλείται μοντέλο δικτύου πίστης (belief network model). Τα δύο αυτά μοντέλα βασίζονται στη θεωρία των δικτύων Bayes η οποία περιγράφεται συνοπτικά στη συνέχεια.

Ένα δίκτυο Bayes είναι ένας κατευθυνόμενος άκυκλος γράφος (directed acyclic graph - DAG) όπου οι κόμβοι είναι τυχαίες μεταβλητές ενώ οι ακμές δηλώνουν εξάρτηση μεταξύ των τυχαίων μεταβλητών. Κάθε ακμή του γράφου έχει ένα βάρος που πρισδιορίζει το βαθμό εξάρτησης της μίας τυχαίας μεταβλητής από την άλλη. Εφόσον ο γράφος είναι κατευθυνόμενος και χωρίς κύκλους, δημιουργείται μία ιεραρχία από κόμβους. Υπάρχουν κόμβοι που δεν έχουν κανένα πρόγονο (άρα οι αντίστοιχες τυχαίες μεταβλητές δεν εξαρτώνται από άλλες) και κόμβοι που έχουν έναν ή περισσότερους προγόνους.

Ορισμός 5.3.

Έστω $v_{i}$ και $v_{j}$ δύο κόμβοι ενός δικτύου Bayes. Αν υπάρχει ακμή από τον $v_{i}$ στον $v_{j}$ τότε ο $v_{i}$ καλείται άμεσος πρόγονος του $v_{j}$ , ενώ ο $v_{j}$ καλείται άμεσος απόγονος του $v_{i}$ .

Έστω $\Pi(v_{i})$ το σύνολο των άμεσων προγόνων του κόμβου $v_{i}$ . Η επίδραση των κόμβων $\Pi(v_{i})$ στον κόμβο $v_{i}$ μπορεί να προσδιοριστεί χρησιμοποιώντας μία συνάρτηση $\Phi_{i}(v_{i},\Pi(v_{i}))$ η οποία έχει τις ακόλουθες ιδιότητες:

0\leq\Phi_{i}(v_{i},\Pi(v_{i}))\leq 1

(5.24)

\sum_{\forall v_{i}}\Phi_{i}(v_{i},\Pi(v_{i}))=1

(5.25)

Αν έχουμε $n$ τυχαίες μεταβλητές, τότε η κοινή συνάρτηση πυκνότητας πιθανότητας $P(v_{1},...,v_{n})$ δίνεται από τον ακόλουθο τύπο:

P(v_{1},...,v_{n})=\prod_{i=1}^{n}\Phi_{i}(v_{i},\Pi(v_{i}))

(5.26)

Παράδειγμα 5.3

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

P(v_{1},v_{2},v_{3},v_{4},v_{5},v_{6})=P(v_{1})\cdot P(v_{2})\cdot P(v_{3}|v_{% 1})\cdot P(v_{4}|v_{1})\cdot P(v_{5}|v_{1},v_{2})\cdot P(v_{6}|v_{4},v_{5})

(5.27)

Σχήμα 5.2: Παράδειγμα δικτύου Bayes με έξι τυχαίες μεταβλητές.

$\square$

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

5.4.1 Μοντέλο Δικτύου Συμπερασμάτων

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

Στο Σχήμα 5.3 δίνεται ένα παράδειγμα ενός απλοποιημένου δικτύου συμπερασμάτων. Σύμφωνα με τον Turtle [73] το δίκτυο συμπερασμάτων περιέχει περισσότερες κατηγορίες κόμβων, ωστόσο χρησιμοποιείται συνηθέστερα στην απλοποιημένη του μορφή. Οι κόμβοι $d_{1}$ έως $d_{N}$ αναφέρονται στα έγγραφα της συλλογής, ενώ οι κόμβοι $t_{1}$ έως $t_{M}$ στους όρους που χρησιμοποιούνται για την αναπαράσταση των εγγράφων. Ο κόμβος $I$ προσδιορίζει την πληροφοριακή ανάγκη του χρήστη, η αναπαράσταση της οποίας πραγματοποιείται με τη χρήση του ερωτήματος $q$ . Συνήθως, ο κόμβος του ερωτήματος είναι ένας, αλλά αν υπάρχουν πολλές αναπαραστάσεις τότε μπορούν να χρησιμοποιηθούν και αυτές.

Σχήμα 5.3: Παράδειγμα δικτύου συμπερασμάτων.

Ο κάθε κόμβος του δικτύου αναπαριστά μία τυχαία μεταβλητή. Η τυχαία μεταβλητή που σχετίζεται με ένα έγγραφο $d_{j}$ αναπαριστά το γεγονός ότι παρατηρούμε το συγκεκριμένο έγγραφο (το μοντέλο θεωρεί ότι τα έγγραφα παρατηρούνται κατά την αναζήτηση των σχετικών εγγράφων). Η παρατήρηση ενός εγγράφου θέτει ένα βαθμό εμπιστοσύνης στις τυχαίες μεταβλητές που σχετίζονται με τους όρους που περιέχονται στο έγγραφο. Επομένως, η παρατήρηση του εγγράφου είναι το αίτιο για αύξηση της εμπιστοσύνης στις τυχαίες μεταβλητές που σχετίζονται με τους όρους. Όπως παρατηρούμε στο Σχήμα 5.3, οι ακμές κατευθύνονται από τους κόμβους των εγγράφων προς τους κόμβους των όρων. Μία τυχαία μεταβλητή που σχετίζεται με ένα ερώτημα αναπαριστά το γεγονός ότι η πληροφοριακή ανάγκη του χρήστη έχει ικανοποιηθεί. Η εμπιστοσύνη του κόμβου του ερωτήματος είναι συνάρτηση της εμπιστοσύνης των όρων που περιέχονται στο ερώτημα. Οι ακμές κατευθύνονται από κόμβους όρων προς τον κόμβο του ερωτήματος.

Μία βασική υπόθεση που γίνεται είναι ότι όλες οι τυχαίες μεταβλητές του μοντέλου είναι δυαδικές, λαμβάνουν δηλαδή είτε την τιμή 0 (false) είτε την τιμή 1 (true). Αν και η υπόθεση αυτή είναι αυθαίρετη, βοηθάει σημαντικά στην απλοποίηση του μοντέλου ενώ ταυτόχρονα φαίνεται να μην βλάπτει τη διαδικασία της ανάκτησης.

Στη συνέχεια, εξετάζουμε συνοπτικά τον τρόπο χρήσης ενός δικτύου συμπερασμάτων. Βασικός στόχος είναι η βαθμολόγηση των εγγράφων της συλλογής ως προς το βαθμό ικανοποίησης της πληροφοριακής ανάγκης του χρήστη. Για την επίτευξη του στόχου αυτού θα πρέπει να δώσουμε τιμές στις πιθανότητες που σχετίζονται με τα έγγραφα και στις υπό συνθήκη πιθανότητες του δικτύου. Εάν κάποια στιγμή η τιμή μίας τυχαίας μεταβλητής γίνει γνωστή, τότε μπορούμε να υπολογίσουμε εκ νέου το βαθμό των εγγράφων λαμβάνοντας υπόψη τα νέα δεδομένα. Έστω ότι έχουμε ένα ερώτημα $q$ που αναπαριστά την πληροφοριακή ανάγκη ενός χρήστη. Αρχικά, προσδιορίζεται ο βαθμός εμπιστοσύνης του κάθε κόμβου του υποδικτύου ερωτήματος. Η αρχική τιμή του κόμβου $I$ είναι η πιθανότητα ικανοποίησης της πληροφοριακής ανάγκης δεδομένου ότι κανένα από τα έγγραφα δεν έχει παρατηρηθεί και όλα τα έγγραφα είναι ισοπίθανα. Εάν τώρα παρατηρήσουμε ένα έγγραφο $d_{j}$ και θέσουμε την τιμή του αντίστοιχου κόμβου σε 1 (true), ενώ οι τιμές των άλλων εγγράφων είναι 0 (false), μπορούμε να υπολογίσουμε μία νέα τιμή για κάθε κόμβο γνωρίζοντας ότι $d_{j}$ = true. Πιο συγκεκριμένα, μπορούμε να υπολογίσουμε την πιθανότητα να ικανοποιείται η πληροφοριακή ανάγκη δεδομένου ότι το έγγραφο $d_{j}$ έχει παρατηρηθεί. Στη συνέχεια, διαλέγουμε κάποιο άλλο έγγραφο $d_{i}$ και επαναλαμβάνεται η ίδια διαδικασία, έως ότου βαθμολογηθούν όλα τα έγγραφα. Για να αποφύγουμε τον έλεγχο όλων των εγγράφων, θα μπορούσαμε να χρησιμοποιήσουμε ένα υποσύνολο των εγγράφων που μεγιστοποιούν την πιθανότητα ικανοποίησης της πληροφοριακής ανάγκης. Επειδή το πρόβλημα έχει μεγάλη πολυπλοκότητα, στη βιβλιογραφία έχουν προταθεί ευριστικές μέθοδοι για το σκοπό αυτό. Εδώ θεωρούμε ότι δε χρησιμοποιείται κάποια τέτοια τεχνική.

Ορισμός 5.4.

Έστω $\vec{t}$ ένα διάνυσμα με $M$ συνιστώσες, όπου $\vec{t}$ = $(t_{1},t_{2},...,t_{M})$ . Η κάθε συνιστώσα $t_{i}$ ⁵⁵Χρησιμοποιούμε το ίδιο σύμβολο για να δηλώσουμε τον όρο και την τυχαία μεταβλητή που σχετίζεται με αυτόν. Το ίδιο θεωρούμε για τα έγγραφα και τα ερωτήματα. Από τα συμφραζόμενα θα γίνεται κατανοητό αν αναφερόμαστε στο αντικείμενο η στην τυχαία μεταβλητή που σχετίζεται με αυτό. αναπαριστά μία δυαδική τυχαία μεταβλητή ( $t_{i}\in\{0,1\}$ ). Οι τυχαίες μεταβλητές ορίζουν τις $2^{M}$ διαφορετικές καταστάσεις του διανύσματος $\vec{t}$ . H $i$ -οστή θέση του διανύσματος $\vec{t}$ συμβολίζεται με $g_{i}(\vec{t})$ .

Ορισμός 5.5.

Στο μοντέλου δικτύου συμπερασμάτων η συνάρτηση ομοιότητας ενός εγγράφου $d$ και ενός ερωτήματος $q$ συμβολίζεται με $S_{infer}(q,d)$ και προσδιορίζεται με την πιθανότητα του γεγονότος $q\land d$ , δηλαδή την πιθανότητα η τυχαία μεταβλητή $q$ να είναι 1 και η τυχαία μεταβλητή $d$ να είναι επίσης 1. Η πιθανότητα αυτή συμβολίζεται με $P(q\land d)$ .

Η πιθανότητα $P(q\land d)$ υπολογίζεται ως εξής:

$\displaystyle P(q\land d)$	$\displaystyle=$	$\displaystyle\sum_{\forall\vec{t}}P(q\land d\|\vec{t})\cdot P(\vec{t})$	(5.28)
	$\displaystyle=$	$\displaystyle\sum_{\forall\vec{t}}P(q\land d\land\vec{t})$
	$\displaystyle=$	$\displaystyle\sum_{\forall\vec{t}}P(q\|d\cdot\vec{t})\cdot P(d\cdot\vec{t})$
	$\displaystyle=$	$\displaystyle\sum_{\forall\vec{t}}P(q\|\vec{t})\cdot P(\vec{t}\|d)\cdot P(d)$

Έστω ότι ενεργοποιούμε τον κόμβο που αναφέρεται σε ένα έγγραφο $d$ της συλλογής. Αυτό ισοδυναμεί με την παρατήρηση (εξέταση) του συγκεκριμένου εγγράφου. Η παρατήρηση του $d$ έχει ως αποτέλεσμα την ανεξαρτησία των όρων που σχετίζονται με το $d$ . Επομένως, ο βαθμός εμπιστοσύνης που προσφέρει η παρατήρηση του εγγράφου σε κάθε όρο μπορεί να υπολογιστεί για κάθε όρο ξεχωριστά (λόγω της ανεξαρτησίας). Άρα, η ποσότητα $P(\vec{t}|d)$ μπορεί να υπολογιστεί ως εξής:

P(\vec{t}|d)=\prod_{\forall i,g_{i}(\vec{t})=1}P(t_{i}|d)\cdot\prod_{\forall i% ,g_{i}(\vec{t})=0}P(\lnot t_{i}|d)

(5.29)

Από τις δύο προηγούμενες σχέσεις έχουμε:

[P(q\land d)=\sum_{\forall\vec{t}}P(q|\vec{t})\cdot\left(\prod_{\forall i,g_{i% }(\vec{t})=1}P(t_{i}|d)\cdot\prod_{\forall i,g_{i}(\vec{t})=0}P(\lnot t_{i}|d)% \right)\cdot P(d)]

(5.30)

Είναι προφανές ότι για τον υπολογισμό της πιθανότητας $P(q\land d)$ θα πρέπει να δώσουμε κατάλληλες τιμές στις πιθανότητες $P(q|\vec{t})$ , $P(t_{i}|d)$ και $P(d)$ . Χρησιμοποιώντας διαφορετικούς τρόπους υπολογισμού των παραπάνω ποσοτήτων παίρνουμε και διαφορετικές εκφράσεις για τον προσδιορισμό του βαθμού ομοιότητας του εγγράφου $d$ ως προς το ερώτημα $q$ . Επειδή οι κόμβοι των εγγράφων στο δίκτυο συμπερασμάτων δεν έχουν εισερχόμενες ακμές, μπορούμε να ορίσουμε αυθαίρετα την πιθανότητα $P(d)$ για κάθε έγγραφο $d$ . Επειδή δεν έχουμε προηγούμενη πληροφορία σχετικά με την πιθανότητα παρατήρησης του κάθε εγγράφου, συνήθως χρησιμοποιείται η ομοιόμορφη κατανομή $P(d)=1/N$ , όπου $N$ είναι το πλήθος των εγγράφων της συλλογής. Ωστόσο, είναι σημαντικό να θέσουμε τις πιθανότητες $P(d)$ με τέτοιο τρόπο έτσι ώστε να εκμεταλλευτούμε την οποιαδήποτε εκ των προτέρων γνώση υπάρχει σχετικά με την συγκεκριμένη εφαρμογή.

Στη συνέχεια, περιγράφουμε τον τρόπο προσδιορισμού των πιθανοτήτων με σκοπό το δίκτυο συμπερασμάτων να χρησιμοποιηθεί για τη βαθμολόγηση των εγγράφων ως προς το Λογικό μοντέλο ανάκτησης. Θεωρούμε ότι η πιθανότητα $P(d)$ υπολογίζεται με βάση την ομοιόμορφη κατανομή:

P(d)=\frac{1}{N}~{}~{}~{}~{}\mbox{και}~{}~{}~{}~{}P(\lnot d)=1-P(d)

(5.31)

Για τον υπολογισμό της υπό συνθήκης πιθανότητας $P(t_{i}|d)$ έχουμε:

P(t_{i}|d)=\left\{\begin{array}[]{ll}1&\mbox{εάν $g_{i}(\vec{d})=1$}\\ 0&\mbox{διαφορετικά}\end{array}\right.

(5.32)

P(\lnot t_{i}|d)=1-P(t_{i}|d)

(5.33)

Ο τρόπος ορισμού της πιθανότητας $P(t_{i}|d)$ δηλώνει ότι η παρατήρηση ενός εγγράφου $d$ έχει ως αποτέλεσμα την ενεργοποίηση των κόμβων του δικτύου που σχετίζονται με τους όρους που περιέχονται στο $d$ . Στη συνέχεια, δίνεται ο τρόπος υπολογισμού της πιθανότητας $P(q|\vec{t})$ που δηλώνει το κατά πόσον οι όροι που περιέχονται στο υπό παρατήρηση έγγραφο ικανοποιούν την πληροφοριακή ανάγκη του χρήστη:

P(q|\vec{t})=\left\{\begin{array}[]{ll}1&\mbox{εάν}~{}\exists\vec{q_{cc}}\in q% _{dnf}|\forall t_{i},g_{i}(\vec{t})=g_{i}(\vec{q_{cc}})\\ 0&\mbox{διαφορετικά}\end{array}\right.

(5.34)

P(\lnot q|\vec{t})=1-P(q|\vec{t})

(5.35)

Αντικαθιστώντας τις τιμές για τις ποσότητες $P(d)$ , $P(t_{i}|d)$ και $P(q|\vec{t})$ στην εξίσωση 5.30 παίρνουμε μία συνάρτηση υπολογισμού ομοιότητας των εγγράφων ως προς το ερώτημα που είναι ή ίδια με αυτήν του Λογικού μοντέλου. Υπενθυμίζεται ότι $q_{dnf}$ είναι η διαζευκτική κανονική μορφή (disjunctive normal form) του ερωτήματος $q$ ενώ $q_{cc}$ είναι μία συζευκτική συνιστώσα (conjunctive component) της διαζευκτικής κανονικής μορφής. Οι έννοιες αυτές έχουν περιγραφεί στο Κεφάλαιο 3. Το μοντέλο δικτύου συμπερασμάτων αν και μπορεί να παραμετροποιηθεί έτσι ώστε να χρησιμοποιεί συναρτήσεις βαθμολόγησης τύπου TF-IDF, δεν μπορεί να προσαρμοστεί ώστε να πραγματοποιεί βαθμολόγηση εγγράφων ακριβώς όπως το Διανυσματικό μοντέλο.

5.4.2 Μοντέλο Δικτύου Πίστης

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

Το κάθε έγγραφο αναπαρίσταται από ένα σύνολο όρων. Ο κάθε όρος $t_{i}$ θεωρείται ως βασική, ενώ το σύνολο ${\cal T}$ = $\{t_{1},t_{2},...,t_{M}\}$ όλων των όρων που χρησιμοποιούνται για την αναπαράσταση των εγγράφων αποτελεί το δειγματοχώρο (sample space) και χαρακτηρίζεται ως χώρος εννοιών (concept space). Ένα υποσύνολο ${\cal E}$ του συνόλου ${\cal T}$ είναι μία έννοια (concept) που μπορεί να αναπαριστά ένα έγγραφο της συλλογής ή κάποιο ερώτημα. Σε κάθε όρο $t_{i}$ αντιστοιχεί μία δυαδική τυχαία μεταβλητή $v_{i}$ . Εάν $v_{i}$ = 1 τότε θεωρούμε ότι ο αντίστοιχος όρος $t_{i}$ ανήκει στην έννοια ${\cal E}\subseteq{\cal T}$ . Συμβολίζουμε με $g_{i}({\cal E})$ την τιμή της τυχαίας μεταβλητής $v_{i}$ σε σχέση με την παρουσία ή απουσία του όρου $t_{i}$ στην έννοια ${\cal E}$ . Αν $M$ είναι το πλήθος των όρων ( $M$ = ${\cal T}$ ) τότε υπάρχουν $2^{M}$ έννοιες (υποσύνολα του ${\cal T}$ ).

Τα έγγραφα της συλλογής και τα ερωτήματα μπορούν να θεωρηθούν ως έννοιες (υποσύνολα όρων) που ορίζονται στο χώρο εννοιών. Ένα έγγραφο $d$ αναπαρίσταται ως μία έννοια (χρησιμοποιούμε το ίδιο σύμβολο $d$ ) που ορίζεται ως $d$ = $\{v_{1},v_{2},...,v_{M}\}$ , όπου το $v_{i}$ αναφέρεται στην τυχαία μεταβλητή που σχετίζεται με τον όρο $t_{i}$ o οποίος σχετίζεται με το έγγραφο $d$ . Ομοίως, ένα ερώτημα $q$ αναπαρίσταται ως μία έννοια (συμβολίζεται με $q$ ), που στην ουσία πρόκειται για ένα υποσύνολο των όρων. Εάν ένας όρος $t_{i}$ χρησιμοποιείται για την περιγραφή του εγγράφου $d$ τότε προφανώς $g_{i}(d)$ = 1 ενώ αν περιγράφει ένα ερώτημα $q$ τότε $g_{i}(q)$ = 1. Εφόσον στόχος της διαδικασίας ανάκτησης είναι ο προσδιορισμός των πιο σχετικών εγγράφων ως προς την πληροφοριακή ανάγκη του χρήστη, για να επιτευχθεί ο στόχος αυτός θα πρέπει να βρεθεί μία μέθοδος συνδυασμού των εννοιών που αναφέρονται στα έγγραφα της συλλογής και και των εννοιών που αναφέρονται στα ερωτήματα.

Ορίζουμε μία συνάρτηση πυκνότητας πιθανότητας στο χώρο ${\cal T}$ ως εξής. Έστω ${\cal E}$ μία έννοια του χώρου ${\cal T}$ που αναπαριστά ένα έγγραφο ή ένα ερώτημα. Τότε έχουμε:

P({\cal E})=\sum_{\forall~{}{\cal C}\subseteq{\cal T}}P({\cal E}|{\cal C})% \cdot P({\cal C})

(5.36)

P({\cal C})=\frac{1}{2^{M}}

(5.37)

Οι πιθανότητα $P({\cal E})$ εκφράζει το βαθμό κάλυψης του χώρου $\cal T$ από την έννοια $\cal E$ . Η κάλυψη αυτή υπολογίζεται με τη βοήθεια των υπό συνθήκη πιθανοτήτων $P({\cal E}|{\cal C})$ για κάθε έννοια $\cal C$ . Εφόσον αρχικά το σύστημα δεν μπορεί να γνωρίζει την πιθανότητα εμφάνισης μίας έννοιας, υποθέτουμε ότι κάθε έννοια $\cal C$ έχει την ίδια πιθανότητα εμφάνισης. Αφού το συνολικό πλήθος των εννοιών είναι $2^{M}$ , η πιθανότητα εμφάνισης της κάθε έννοιας είναι $1/2^{M}$ .

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

Ορισμός 5.6.

Στο μοντέλο δικτύου πίστης η συνάρτηση ομοιότητας ενός εγγράφου $d$ σε σχέση με ένα ερώτημα $q$ συμβολίζεται με $S_{belief}(q,d)$ και ορίζεται ως η πιθανότητα $P(d|q)$ .

Με εφαρμογή του κανόνα του Bayes, έχουμε ότι $P(d|q)$ = $P(d\land q)/P(q)$ . Η τιμή $P(q)$ είναι ανεξάρτητη από τα έγγραφα της συλλογής, οπότε ο βαθμός ομοιότητας του εγγράφου $d$ ως προς το ερώτημα $q$ είναι ανάλογος της ποσότητας $P(d\land q)$ , και γράφουμε $P(d|q)$ $\propto$ $P(d\land q)$ . Με εφαρμογή του τύπου 5.36 για την πιθανότητα $P(d\land q)$ παίρνουμε:

P(d|q)\propto\sum_{\forall~{}{\cal C}\subseteq{\cal T}}P(d\land q|{\cal C})% \cdot P({\cal C})

(5.38)

Χρησιμοποιώντας την ιδιότητα της ανεξαρτησίας των κόμβων των εγγράφων και των κόμβων των ερωτημάτων, έχουμε:

[P(d|q)\propto\sum_{\forall~{}{\cal C}\subseteq{\cal T}}P(d|{\cal C})\cdot P(q% |{\cal C})\cdot P({\cal C})]

(5.39)

Εάν στον τύπο 5.39 θέσουμε τις τιμές των πιθανοτήτων $P(d|{\cal C})$ και $P(q|{\cal C})$ τότε μπορούμε να προσδιορίσουμε το βαθμό ομοιότητας του εγγράφου $d$ ως προς το ερώτημα $q$ . Προσδιορίζοντας με διαφορετικό τρόπο τις πιθανότητες αυτές υποστηρίζεται μία πληθώρα διαφορετικών μεθόδων βαθμολόγησης των εγγράφων. Ως παράδειγμα, θα μελετηθεί ο τρόπος υπολογισμού των πιθανοτήτων ώστε το μοντέλο δικτύου πίστης να προσομοιώσει το Διανυσματικό μοντέλο.

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

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

Τα μοντέλα ανάκτησης που βασίζονται σε πιθανοκρατική θεώρηση εγγράφων, όρων και ερωτημάτων έχουν μελετηθεί διεξοδικά στη βιβλιογραφία. Παραπέμπουμε τον αναγνώστη που θέλει να εμβαθύνει περισσότερο στο χώρο στο βιβλίο του Rijbergen [75] που αποτελεί ένα πολύ βασικό σύγγραμα, στο βιβλίο των Baeza-Yates και Ribeiro-Neto [3] και στο πιο σύγχρονο βιβλίο των Manning, Raghavan και Schutze [41]. Περισσότερες λεπτομέρειες σχετικά με το απλό Πιθανοκρατικό μοντέλο υπάρχουν στις ερευνητικές εργασίες [27, 42, 43, 50, 56] ενώ στις εργασίες [51, 49] αναλύεται ο τρόπος προσδιορισμού της ομοιότητας που χρησιμοποιείται στο σύστημα Okapi. Επίσης, εξαιρετικό ενδιαφέρον παρουσιάζουν η εργασία των Turtle και Croft [74] που αναλύει το μοντέλο δικτύου συμπερασμάτων και η εργασία των Ribeiro-Neto και Muntz [48] που εστιάζει στο μοντέλο δικύου πίστης.

5.6 Ασκήσεις

5.1

Να δώσετε τον κανόνα του Bayes και να σχολιάσετε το τι ακριβώς αναφέρει.
5.2

Από ποιόν μαθηματικό τύπο δίνεται ο βαθμός ομοιότητας μεταξύ ενός ερωτήματος $q$ και ενός εγγράφου $d$ ;
5.3

Να διατυπώσετε την Αρχή Πιθανοκρατικής Βαθμολόγησης και την Αρχή της Ανάκτησης Δυαδικής Ανεξαρτησίας.
5.4

Ποιά κατά τη γνώμη σας πιστεύετε ότι είναι τα βασικά μειονεκτήματα του απλόυ Πιθανοκρατικού μοντέλου;
5.5

Να περιγράψετε τα βασικά χαρακτηριστικά ενός δικτύου συμπερασμάτων και ενός δικτύου πίστης. Ποιές είναι οι βασικές τους διαφορές;