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

Κεφάλαιο 3Το Λογικό Μοντέλο

3.1 Εισαγωγή

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

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

3.2 Το Απλό Λογικό Μοντέλο

Τόσο στο Λογικό μοντέλο όσο και στα άλλα δύο μοντέλα που απαρτίζουν την οικογένεια των κλασικών μοντέλων ανάκτησης τα έγγραφα της συλλογής αναπαρίστανται με όρους (terms) ή αλλιώς λέξεις-κλειδιά (key-words). Στη γενικότερη περίπτωση, χρησιμοποιούνται όλοι οι όροι των εγγράφων. Ωστόσο, λαμβάνοντας υπόψη ότι πολλοί από τους όρους ενός εγγράφου δεν προσφέρουν σημαντική πληροφορία (όπως για παράδειγμα τα άρθρα και τα επίθετα) σε πολλές περιπτώσεις πραγματοποιείται προ-επεξεργασία των εγγράφων με στόχο τη διατήρηση των λέξεων που περιέχουν σημαντική πληροφορία. Οι όροι με το περισσότερο πληροφοριακό περιεχόμενο είναι τα ουσιαστικά, ενώ άρθρα, ρήματα και επιρρήματα συνήθως δεν χρησιμοποιούνται για την αναπαράσταση των εγγράφων. Συνήθως, στις μηχανές αναζήτησης που χρησιμοποιούνται στον παγκόσμιο ιστό όπως και σε πολλά άλλα συστήματα χρησιμοποιούνται όλοι οι όροι για την αναπαράσταση των εγγράφων, οπότε στην περίπτωση αυτή έχουμε αναπαράσταση πλήρους κειμένου (full text). Για τις ανάγκες αυτού του κεφαλαίου θα χρησιμοποιήσουμε τη μικρή συλλογή εγγράφων του Κεφαλαίου 1, η οποία παρουσιάζεται εκ νέου στο Σχήμα 3.1 για τη διευκόλυνση του αναγνώστη.

$d_{1}$ :	Ο κομήτης του Χάλλεϋ μας επισκέπτεται περίπου κάθε εβδομήντα έξι χρόνια.
$d_{2}$ :	Ο κομήτης του Χάλλεϋ ανακαλύφθηκε από τον αστρονόμο Έντμοντ Χάλλεϋ.
$d_{3}$ :	Ένας κομήτης διαγράφει ελλειπτική τροχιά.
$d_{4}$ :	Ο πλανήτης Άρης έχει δύο φυσικούς δορυφόρους, το Δείμο και το Φόβο.
$d_{5}$ :	Ο πλανήτης Δίας έχει εξήντα τρεις γνωστούς φυσικούς δορυφόρους.
$d_{6}$ :	Ο Ήλιος είναι ένας αστέρας.
$d_{7}$ :	Ο Άρης είναι ένας πλανήτης του ηλιακού μας συστήματος.

Σχήμα 3.1: Συλλογή εγγράφων.

3.2.1 Βασικές Έννοιες

Το απλό Λογικό μοντέλο ανάκτησης είναι από τα πρώτα μοντέλα που χρησιμοποιήθηκαν στα συστήματα ανάκτησης πληροφορίας κυρίως λόγω του ότι στηρίζεται στη θεωρία συνόλων και επομένως χαρακτηρίζεται από απλότητα. Τα ερωτήματα αναπαρίστανται με λογικές εκφράσεις της άλγεβρας Boole χρησιμοποιώντας τους τελεστές AND (σύζευξη), OR (διάζευξη) και NOT (άρνηση). Εναλλακτικά χρησιμοποιούμε τα σύμβολα $\land$ για τον τελεστή AND, $\lor$ για τον τελεστή OR και $\lnot$ για τον τελεστή NOT. Μεγαλύτερη προτεραιότητα έχει ο τελεστής NOT, στη συνέχεια ο τελεστής AND και τέλος ο τελεστής OR. Σε περιπτώσεις που θέλουμε να αλλάξουμε την προτεραιότητα των τελεστών σε μία λογική έκφραση χρησιμοποιούνται παρενθέσεις. Στο Σχήμα 3.2 δίνονται μερικές βασικές λογικές εκφράσεις με τη μορφή διαγραμμάτων Venn.

Σχήμα 3.2: Αναπαράσταση λογικής έκφρασης με χρήση διαγραμμάτων Venn.

Το βασικό χαρακτηριστικό του Λογικού μοντέλου είναι ότι υποστηρίζει την επακριβή ταύτιση (exact match). Αυτό σημαίνει ότι τα έγγραφα του αποτελέσματος θα πρέπει να ικανοποιούν πλήρως τη λογική έκφραση του ερωτήματος, δηλαδή η λογική έκφραση θα πρέπει να είναι αληθής για κάθε έγγραφο. Στον Πίνακα 3.1 δίνονται μερικά ερωτήματα με τη μορφή λογικών εκφράσεων και οι αντίστοιχες επεξηγήσεις. Αν συμβολίσουμε με $A_{k}$ το σύνολο των εγγράφων που περιέχονται στην απάντηση του ερωτήματος $q_{k}$ τότε έχουμε: $A_{1}$ = $\{d_{1},d_{2},d_{3},d_{6}\}$ , $A_{2}$ = $\{d_{1},d_{2}\}$ , $A_{3}$ = $\{d_{5},d_{6}\}$ , $A_{4}$ = $\{d_{6}\}$ και $A_{5}$ = $\{d_{1},d_{2},d_{3},d_{4},d_{5},d_{6},d_{7}\}$ .

ερώτημα	λογική	αναζήτηση εγγράφων
	έκφραση	που περιέχουν τους όρους:
$q_{1}$	κομήτης	κομήτης
$q_{2}$	κομήτης AND Χάλλεϋ	κομήτης και Χάλλεϋ
$q_{3}$	πλανήτης AND NOT Άρης	πλανήτης αλλά όχι Άρης
$q_{4}$	(κομήτης OR Χάλλεϋ) AND πλανήτης	πλανήτης και κομήτης
		ή πλανήτης και Χάλλεϋ
$q_{5}$	πλανήτης OR κομήτης	πλανήτης ή κομήτης

Πίνακας 3.1: Παραδείγματα λογικών ερωτημάτων.

Στη γενική περίπτωση, ένα ερώτημα προσδιορίζει έναν ή περισσότερους όρους που μαζί με τους λογικούς τελεστές σχηματίζουν τη λογική έκφραση του ερωτήματος. Σύμφωνα με το Λογικό μοντέλο, ένας όρος είτε θα βρίσκεται σε ένα έγγραφο είτε όχι. Αυτό σημαίνει ότι για κάθε έγγραφο $d_{j}$ και κάθε όρο του ερωτήματος $t_{i}$ μπορούμε να αντιστοιχήσουμε μία τιμή $w_{ij}$ που μπορεί να λάβει μόνο τις τιμές 0 και 1. Αν $w_{ij}$ =0 τότε ο όρος $t_{i}$ δεν βρίσκεται στο έγγραφο $d_{j}$ , ενώ αν $w_{ij}$ =1 τότε ο όρος $t_{i}$ υπάρχει στο έγγραφο $d_{j}$ .

Εφόσον ένα ερώτημα ουσιαστικά αποτελεί μία λογική έκφραση, σύμφωνα με τη μεθοδολογία της άλγεβρας Boole μπορεί να κανονικοποιηθεί στη διαζευκτική κανονική μορφή (disjunctive normal form).

Ορισμός 3.1.

Η διαζευκτική κανονική μορφή ενός λογικού ερωτήματος $q$ συμβολίζεται με $q_{dnf}$ και έχει τη μορφή $(x_{1,1}\land x_{1,2}\land...\land x_{1,m})\lor(x_{2,1}\land x_{2,2}\land...% \land x_{2,m})\lor...\lor(x_{m,1}\land x_{m,2}\land...\land x_{k,m})$ , όπου το κάθε $x_{i,j}$ ισούται είτε με $t_{i}$ είτε με $\lnot t_{i}$ , $m$ είναι το πλήθος των όρων του ερωτήματος και $k$ είναι το πλήθος των συζευκτικών συνιστωσών. Η $i$ -οστή συζευκτική συνιστώσα του ερωτήματος συμβολίζεται με $q_{cc_{i}}$ .

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

q=(t_{1}~{}~{}{\sf\small OR}~{}~{}t_{2})~{}~{}{\sf\small AND}~{}~{}t_{3}

(3.1)

$t_{1}$	$t_{2}$	$t_{3}$	διάνυσμα	έκφραση	απάντηση
0	0	0	(0, 0, 0)	$\lnot t_{1}\land\lnot t_{2}\land\lnot t_{3}$	0
0	0	1	(0, 0, 1)	$\lnot t_{1}\land\lnot t_{2}\land t_{3}$	0
0	1	0	(0, 1, 0)	$\lnot t_{1}\land t_{2}\land\lnot t_{3}$	0
0	1	1	(0, 1, 1)	$\lnot t_{1}\land t_{2}\land t_{3}$	1
1	0	0	(1, 0, 0)	$t_{1}\land\lnot t_{2}\land\lnot t_{3}$	0
1	0	1	(1, 0, 1)	$t_{1}\land\lnot t_{2}\land t_{3}$	1
1	1	0	(1, 1, 0)	$t_{1}\land t_{2}\land\lnot t_{3}$	0
1	1	1	(1, 1, 1)	$t_{1}\land t_{2}\land t_{3}$	1

Πίνακας 3.2: Πίνακας αληθείας.

Σχήμα 3.3: Αναπαράσταση λογικής έκφρασης με χρήση διαγραμμάτων Venn.

Με βάση το ερώτημα $q$ τα έγγραφα που θα επιστραφούν ως απάντηση πρέπει οπωσδήποτε να περιέχουν τον όρο $t_{3}$ και τουλάχιστον έναν από τους όρους $t_{1}$ και $t_{2}$ . Στον Πίνακα 3.2 δίνεται ο πίνακας αληθείας (truth table) για το ερώτημα $q$ , από όπου φαίνεται ότι η λογική έκφραση του ερωτήματος γίνεται αληθής για τους συνδυασμούς: (0, 1, 1), (1, 0, 1) και (1, 1, 1), όπου στο κάθε διάνυσμα η πρώτη τιμή αφορά στον όρο $t_{1}$ , η δεύτερη στον όρο $t_{2}$ και η τρίτη στον όρο $t_{3}$ . Στο Σχήμα 3.3 δίνεται ένα ενδεικτικό διάγραμμα Venn μαζί με τα αντίστοιχα διανύσματα. Η περιοχή του διαγράμματος που αντιστοιχεί στο ερώτημα δίνεται από τα διανύσματα που επαληθεύουν τη λογική έκφραση του ερωτήματος. Με βάση τα προηγούμενα, η διαζευκτική κανονική μορφή του ερωτήματος έχει τη μορφή:

q_{dnf}=(\lnot t_{1}\land t_{2}\land t_{3})\lor(t_{1}\land\lnot t_{2}\land t_{% 3})\lor(t_{1}\land t_{2}\land t_{3})

(3.2)

Το ερώτημα αποτελείται από τρεις συζευκτικές συνιστώσες $q_{cc_{1}}$ , $q_{cc_{2}}$ και $q_{cc_{3}}$ , όπου $q_{cc_{1}}$ = $\lnot t_{1}\land t_{2}\land t_{3}$ , $q_{cc_{2}}$ = $t_{1}\land\lnot t_{2}\land t_{3}$ και $q_{cc_{3}}$ = $t_{1}\land t_{2}\land t_{3}$ . Τα αντίστοιχα διανύσματα είναι: $\vec{q}_{cc_{1}}$ = $(0,1,1)$ , $\vec{q}_{cc_{2}}$ = $(1,0,1)$ και $\vec{q}_{cc_{3}}$ = $(1,1,1)$ . Επομένως, η διανυσματική αναπαράσταση της διαζευκτικής κανονικής μορφής είναι:

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

(3.3)

Ένα έγγραφο θα βρίσκεται στην απάντηση αν επαληθεύει έναν από τους όρους της διαζευκτικής κανονικής μορφής. Για παράδειγμα, με βάση την διαζευκτική κανονική μορφή του ερωτήματος $q$ , ένα έγγραφο με διάνυσμα (1,1,1) σίγουρα θα ανήκει στην απάντηση.

3.2.2 Τελεστές Γειτονικότητας Όρων

Με τη χρήση των βασικών τελεστών AND, OR και NOT ο χρήστης μπορεί να προσδιορίσει την περιεκτικότητα ή όχι των όρων σε ολόκληρο το έγγραφο. Πολλές φορές όμως ενδιαφερόμαστε για την εμφάνιση κάποιων λέξεων που βρίσκονται συνεχόμενες ή που βρίσκονται στην ίδια πρόταση ή παράγραφο. Αν και το απλό Boolean μοντέλο δεν προσφέρει την περιγραφή τέτοιων ερωτημάτων, τα περισσότερα συστήματα που στηρίζονται στο μοντέλο αυτό υλοποιούν και μερικούς επιπλέον τελεστές αναγνωρίζοντας τις σχετικές ανάγκες των χρηστών. Οι τελεστές αυτοί αυξάνουν την εκφραστικότητα της γλώσσας ερωτημάτων και δίνουν τη δυνατότητα στους χρήστες να περιορίσουν κατά πολύ το σύνολο των εγγράφων της απάντησης.

Από τους πιο σημαντικούς τελεστές που έχουν χρησιμοποιηθεί με το Λογικό μοντέλο είναι οι εξής:

•

ADJ. Ο τελεστής αυτός χρησιμοποιείται για να δηλώσει ότι δύο όροι πρέπει να εμφανίζονται συνεχόμενοι μέσα στο έγγραφο της απάντησης (π.χ. πλανήτης ADJ Άρης).
•

NEAR/ $x$ . Ο τελεστής χρησιμοποιείται για να δηλώσει την επιθυμία του χρήστη ότι δύο όροι θα πρέπει να έχουν απόσταση το πολύ $x$ μεταξύ τους, όπου $x$ είναι ο αριθμός των όρων (π.χ. πλανήτης NEAR/2 Άρης).
•

WITH. Με αυτόν τον τελεστή ο χρήστης μπορεί να δηλώσει ότι οι δύο όροι πρέπει να βρίσκονται στην ίδια πρόταση (π.χ. πλανήτης WITH Άρης).
•

SAME. Εδώ δηλώνουμε ότι οι όροι θέλουμε να βρίσκονται στην ίδια παράγραφο (π.χ. πλανήτης SAME Άρης).

Οι συμβολισμοί των τελεστών συνήθως διαφέρουν από σύστημα σε σύστημα. Για παράδειγμα, στο σύστημα WestLaw [76], που αποτελεί μία από τις μεγαλύτερες υπηρεσίες για την αναζήτηση νομικών πληροφοριών με πολύ μεγάλο αριθμό συνδρομητών, ο τελεστής WITH συμβολίζεται με /s, ο τελεστής SAME συμβολίζεται με /p ενώ ο τελεστής NEAR/ $x$ με / $x$ . Στο σύστημα CiteSeer [9], που αποτελεί έναν από τους μεγαλύτερους ιστότοπους παροχής βιβλιογραφικών πληροφοριών για την Πληροφορική επιστήμη, ο τελεστής NEAR/ $x$ συμβολίζεται με w/ $x$ . Σημειώνεται ότι η προτεραιότητα των τελεστών ADJ, NEAR/ $x$ , WITH και SAME είναι μεγαλύτερη από τους υπόλοιπους λογικούς τελεστές. Στον Πίνακα 3.3 δίνονται μερικά ερωτήματα χρησιμοποιώντας και τους επιπλέον τελεστές. Για κάθε ερώτημα δίνεται και το σύνολο των εγγράφων της απάντησης, με βάση τη συλλογή εγγράφων του Σχήματος 3.1.

ερώτημα	σύνολο απάντησης
κομήτης ADJ Χάλλεϋ	{ }
κομήτης NEAR/2 Χάλλεϋ	{ $d_{1}$ , $d_{2}$ }
πλανήτης ADJ Άρης	{ $d_{4}$ }
Δίας AND φυσικούς ADJ δορυφόρους	{ $d_{5}$ }

Πίνακας 3.3: Παραδείγματα λογικών ερωτημάτων.

3.2.3 Επεξεργασία Ερωτημάτων

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

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

Σχήμα 3.4: Τμήμα αντεστραμμένου καταλόγου για τα έγγραφα του Σχήματος 3.1.

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

Ο τρόπος χρήσης του αντεστραμμένου καταλόγου εξαρτάται από το ερώτημα. Για παράδειγμα, για ερωτήματα που προσδιορίζουν μόνο έναν όρο, το μόνο που χρειάζεται είναι να εντοπιστεί ο όρος στο λεξικό και στη συνέχεια να διαβαστεί η αντίστοιχη λίστα εμφανίσεων για το συγκεκριμένο όρο. Έστω το ερώτημα $q_{1}$ = κομήτης. Από τη λίστα εμφανίσεων του όρου κομήτης είναι προφανές ότι τα σχετικά έγγραφα ως προς το ερώτημα αυτό είναι τα $d_{1}$ , $d_{2}$ , $d_{3}$ και $d_{6}$ , επομένως η απάντηση στο ερώτημα $q_{1}$ είναι:

A_{1}=\{d_{1},d_{2},d_{3},d_{6}\}

(3.4)

Μεγαλύτερο ενδιαφέρον παρουσιάζει η επεξεργασία ερωτημάτων που περιέχουν περισσότερους όρους και χρησιμοποιούν τελεστές. Έστω το ερώτημα $q_{2}$ = πλανήτης $\lor$ Άρης. Τα σχετικά έγγραφα ως προς το ερώτημα $q_{2}$ είναι αυτά που περιέχουν είτε τον όρο πλανήτης είτε τον όρο Άρης ή και τις δύο. Στην περίπτωση αυτή, αφού πρώτα εντοπισθούν οι λίστες εμφανίσεων των δύο λέξεων, στην συνέχεια υπολογίζεται η ένωση των συνόλων των εγγράφων. Από τον αντεστραμμένο κατάλογο έχουμε ότι τα έγγραφα που περιέχουν τον όρο πλανήτης είναι τα $d_{4}$ , $d_{5}$ , $d_{6}$ , $d_{7}$ , ενώ τα έγγραφα που περιέχουν τον όρο Άρης είναι τα $d_{4}$ , $d_{7}$ . Τα σχετικά έγγραφα ως προς το ερώτημα $q_{2}$ αντιστοιχούν στην ένωση των επιμέρους αποτελεσμάτων. Άρα, η απάντηση στο ερώτημα $q_{2}$ είναι:

A_{2}=\{d_{4},d_{5},d_{6},d_{7}\}\cup\{d_{4},d_{7}\}=\{d_{4},d_{5},d_{6},d_{7}\}

(3.5)

Στη συνέχεια εξετάζουμε τον τρόπο επεξεργασίας ενός ερωτήματος που χρησιμοποιεί τη σύζευξη. Έστω το ερώτημα $q_{3}$ = πλανήτης $\land$ Άρης. Τα σχετικά έγγραφα ως προς το ερώτημα αυτό είναι αυτά που περιέχουν και τους δύο όρους. Με βάση τις λίστες εμφανίσεων για την κάθε όρο για να υπολογίσουμε την ολοκληρωμένη απάντηση θα πρέπει να υπολογίσουμε την τομή των επιμέρους αποτελεσμάτων. Επομένως:

A_{3}=\{d_{4},d_{5},d_{6},d_{7}\}\cap\{d_{4},d_{7}\}=\{d_{4},d_{7}\}

(3.6)

Στην περίπτωση της σύζευξης θα μπορούσαμε να εφαρμόσουμε και μία άλλη τεχνική αν το επιτρέπει ο τρόπος οργάνωσης του αντεστραμμένου καταλόγου. Αν μπορούμε να εκτελέσουμε τυχαία προσπέλαση (random access) σε μία λίστα εμφανίσεων, τότε ίσως μία καλύτερη λύση είναι να χρησιμοποιήσουμε τους κωδικούς των εγγράφων που εντοπίσαμε για τον όρο Άρης και να εκτελέσουμε τυχαίες προσπελάσεις στη λίστα εμφανίσεων του όρου πλανήτης. Όσα έγγραφα εντοπισθούν στη δεύτερη λίστα ανήκουν στην απάντηση του ερωτήματος. Επίσης, σε περίπτωση που το ερώτημα περιέχει περισσότερους όρους οι οποίοι συνδέονται με σύζευξη (λογικό ΚΑΙ), η εκτέλεση της πράξης της τομής αρχίζει από τις λίστες εμφανίσεων που έχουν το μικρότερο μήκος. Η εφαρμογή του κανόνα αυτού έχει ως αποτέλεσμα να απαιτούνται στη γενική πρίπτωση λιγότερες πράξεις για την εκτέλεση του ερωτήματος στο σύνολο του. Αν και η χρήση μεθόδων βελτιστοποίησης είναι πολύ σημαντική για την ταχύτητα επεξεργασίας των ερωτημάτων, δεν θα εμβαθύνουμε περισσότερο στο θέμα αυτό.

Ενώ για τις πράξεις της διάζευξης και της σύζευξης απαιτούνται μόνο οι κωδικοί των εγγράφων για τον προσδιορισμό της απάντησης, για την υποστήριξη των τελεστών ADJ, NEAR/ $x$ , WITH και SAME απαιτείται ιδιαίτερη μεταχείριση των λιστών εμφάνισης. Στη συνέχεια ας εξετάσουμε ένα παράδειγμα ερωτήματος που χρησιμοποιεί τον τελεστή ADJ. Έστω το ερώτημα $q_{4}$ = πλανήτης ADJ (Άρης $\lor$ Δίας). Τα σχετικά έγγραφα περιέχουν τον όρο πλανήτης και συνεχόμενα τον όρο Άρης ή τον όρο Δίας. Εναλλακτικά το ερώτημα γράφεται και ως: $q_{4}$ = πλανήτης ADJ Άρης $\lor$ πλανήτης ADJ Δίας. Για την επεξεργασία αυτού του ερωτήματος ακολουθούμε την εξής τακτική:

: Βήμα 1: Στο πρώτο βήμα βρίσκουμε τις λίστες εμφανίσεων των λέξεων πλανήτης, Άρης και Δίας, απευθείας από τον αντεστραμμένο κατάλογο. Οι λίστες εμφανίσεων των λέξεων αυτών έχουν ως εξής:
Λίστα_Εμφανίσεων(πλανήτης) = [ $d_{4}$ , 3], [ $d_{5}$ , 3], [ $d_{6}$ , 51], [ $d_{7}$ , 19]
Λίστα_Εμφανίσεων(Άρης) = [ $d_{4}$ , 12], [ $d_{7}$ , 3]
Λίστα_Εμφανίσεων(Δίας) = [ $d_{5}$ , 12]
: Βήμα 2: Προσδιορίζουμε σε ποια έγγραφα οι όροι πλανήτης και Άρης εμφανίζονται μαζί. Επαναλαμβάνουμε τη διαδικασία για τους όρους πλανήτης και Δίας. Είναι εύκολο να διαπιστώσουμε ότι τα έγγραφα που περιέχουν και τους δύο όρους πλανήτης και Άρης είναι τα $d_{4}$ και $d_{7}$ . Ομοίως διαπιστώνουμε ότι το $d_{5}$ είναι το μοναδικό έγγραφο που περιέχει τους όρους πλανήτης και Δίας.
: Βήμα 3: Με βάση την πληροφορία για τη θέση εμφάνισης του κάθε όρου μέσα στο έγγραφο, προσδιορίζουμε αν οι όροι εμφανίζονται συνεχόμενες μέσα στο έγγραφο. Εξετάζοντας τα έγγραφα που περιέχουν τους όρους πλανήτης και Άρης διαπιστώνουμε ότι το έγγραφο $d_{7}$ δεν είναι δυνατόν να ικανοποιεί τη συνθήκη πλανήτης ADJ Άρης, διότι ο όρος πλανήτης εμφανίζεται στη θέση 19. ενώ ο όρος Άρης στη θέση 3, δηλαδή πριν τον όρο πλανήτης. Επομένως, απορρίπτουμε το έγγραφο $d_{7}$ . Εξετάζοντας το έγγραφο $d_{4}$ διαπιστώνουμε ότι ικανοποιεί τη συνθήκη πλανήτης ADJ Άρης. Πράγματι, ο όρος πλανήτης εμφανίζεται στη θέση 3 ενώ ο όρος Άρης στη θέση 12. Εφόσον το πλήθος των χαρακτήρων του όρου πλανήτης είναι 8 και προσμετρώντας τον κενό χαρακτήρα, τότε δεν υπάρχει περίπτωση μεταξύ των λέξεων πλανήτης και Άρης να παρεμβάλλεται κάποιος άλλος όρος. Επομένως, το έγγραφο $d_{4}$ συμπεριλαμβάνεται στην απάντηση. Με το ίδιο σκεπτικό προσδιορίζουμε ότι το έγγραφο $d_{5}$ ανήκει στην απάντηση. Με βάση τα προηγούμενα, η απάντηση στο ερώτημα αποτελείται από τα έγγραφα $d_{4}$ και $d_{5}$ .

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

3.2.4 Πλεονεκτήματα και Μειονεκτήματα

Το βασικό πλεονέκτημα του απλού Λογικού μοντέλου είναι το ότι στηρίζεται στη Θεωρία Συνόλων και επομένως μπορεί να γίνει εύκολα αντιληπτό. Η απλότητα του μοντέλου ήταν και ο σημαντικότερος λόγος για την ευρεία αποδοχή του από τους κατασκευαστές συστημάτων. Ωστόσο, υπάρχουν αρκετά αδύνατα σημεία που μπορεί να δημιουργήσουν προβλήματα στη διαδικασία ανάκτησης. Μερικά από αυτά εξετάζουμε στη συνέχεια.

Ένα από τα σημαντικότερα μειονεκτήματα του μοντέλου είναι ότι δεν υποστηρίζει τη βαθμολόγηση των αποτελεσμάτων ως προς τη σχετικότητα με το ερώτημα. Αυτό σημαίνει ότι ένα έγγραφο είτε θα ανήκει στην απάντηση είτε όχι. Αυτή η ιδιότητα του μοντέλου είναι αρκετά περιοριστική καθώς έγγραφα που σχετίζονται μερικώς με το ερώτημα δεν ανακτώνται. Αν συμβολίσουμε με $S_{boolean}(q,d)$ την ομοιότητα ενός ερωτήματος $q$ και ενός εγγράφου $d$ τότε έχουμε:

S_{boolean}(q,d)=\left\{\begin{array}[]{ll}0&\textrm{εάν το $d$ δεν ικανοποιεί% τις συνθήκες του $q$}\\ 1&\textrm{εάν το $d$ ικανοποιεί τις συνθήκες του $q$}\end{array}\right.

(3.7)

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

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

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

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

3.3 Το Εκτεταμένο Λογικό Μοντέλο

Το εκτεταμένο Λογικό μοντέλο (extended Boolean model) προτάθηκε από τους Salton, Fox και Wu το 1983 [57] για να αντιμετωπίσει μερικά βασικά προβλήματα που εμφανίζει το απλό Λογικό μοντέλο. Σύμφωνα με την κατηγοριοποίηση των μοντέλων Ανάκτησης Πληροφορίας που περιγράφεται στο βιβλίο [3], το εκτεταμένο Λογικό μοντέλο ανήκει στην κατηγορία των εναλλακτικών συνολοθεωρητικών μοντέλων (alternative set-theoretic models). Το δεύτερο μοντέλο που συμπληρώνει την κατηγορία αυτή είναι το μοντέλο Ασαφούς λογικής (fuzzy model).

Έστω το ερώτημα $q_{and}$ = $t_{a}$ $\land$ $t_{b}$ που χρησιμοποιεί τους όρους $t_{a}$ και $t_{b}$ και το λογικό τελεστή σύζευξης $\land$ . Με βάση το απλό Λογικό μοντέλο, ένα έγγραφο $d_{j}$ της συλλογής χαρακτηρίζεται ως σχετικό αν και μόνο αν περιέχει και τους δύο όρους $t_{a}$ και $t_{b}$ . Σε διαφορετική περίπτωση το έγγραφο χαρακτηρίζεται μη σχετικό και επομένως ο βαθμός ομοιότητας του εγγράφου ως προς το ερώτημα θα είναι $S_{boolean}(q_{and},d_{j})$ = 0. Αυτό σημαίνει ότι δεν γίνεται καμία διάκριση σε περίπτωση που το $d_{j}$ περιέχει έναν από τους δύο όρους. Άρα είτε το $d_{j}$ περιέχει μόνο έναν από τους όρους είτε δεν περιέχει κάποιον όρο, ο βαθμός ομοιότητας παραμένει 0. Αυτό το φαινόμενο παρουσιάζεται στον Πίνακα 3.4 ο οποίος συνοψίζει όλες τις δυνατές περιπτώσεις σχετικά με την εμφάνιση ή όχι των όρων στο έγγραφο. Παρατηρούμε ότι για τις τρεις τελευταίες περιπτώσεις η ομοιότητα του $d_{j}$ ως προς το $q_{and}$ είναι 0. Ωστόσο, θα περίμενε κάποιος η ομοιότητα να είναι μεγαλύτερη σε περίπτωση που ένας εκ των δύο όρων εμφανίζεται στο έγγραφο. Το φαινόμενο αυτό γίνεται εντονότερο στην περίπτωση που έχουμε περισσότερους όρους που συνδέονται με λογική σύζευξη.

Πίνακας 3.4: Ομοιότητα εγγράφου για τις περιπτώσεις εμφάνισης ή όχι των όρων $t_{a}$ , $t_{b}$ .

Παρόμοια παρατήρηση μπορεί να γίνει και στην περίπτωση που το ερώτημα περιέχει διάζευξη. Έστω το ερώτημα $q_{or}$ = $t_{a}$ $\lor$ $t_{b}$ . Σύμφωνα με το απλό Boolean μοντέλο, ένα έγγραφο $d_{j}$ είτε περιέχει έναν από τους δύο όρους είτε και τους δύο έχει βαθμό ομοιότητας $S_{boolean}(q_{or},d_{j})$ = 1. Θα περίμενε κάποιος, το έγγραφο που περιέχει και τους δύο όρους να έχει μεγαλύτερο βαθμό ομοιότητας από ένα έγγραφο που περιέχει τον έναν από τους δύο όρους του ερωτήματος.

Σχήμα 3.5: Απεικόνιση εγγράφων στο επίπεδο.

Σύμφωνα με το εκτεταμένο Λογικό μοντέλο, το κάθε έγγραφο αναπαρίσταται με τη βοήθεια ενός διανύσματος βαρών. Στο Σχήμα 3.5 παρουσιάζεται η αναπαράσταση δύο εγγράφων $d_{j}$ και $d_{k}$ στην περίπτωση που έχουμε δύο όρους. Αν συμβολίσουμε με $\vec{d_{j}}$ και $\vec{d_{k}}$ τα αντίστοιχα διανύσματα των εγγράφων, τότε έχουμε $\vec{d_{j}}$ = $(w_{a,j},w_{b,j})$ και $\vec{d_{k}}$ = $(w_{a,k},w_{b,k})$ , όπου $w_{a,j}$ και $w_{b,j}$ είναι οι συντεταγμένες (βάρη) του εγγράφου $d_{j}$ , και $w_{a,k}$ , $w_{b,k}$ οι συντεταγμένες του εγγράφου $d_{k}$ . Οι τιμές των βαρών φροντίζουμε να είναι κανονικοποιημένες στο διάστημα τιμών [0,1].

Το βάρος $w_{x,j}$ όπου ενός όρου $t_{x}$ σε ένα έγγραφο $d_{j}$ δηλώνει το πόσο σημαντικός είναι ο όρος για το έγγραφο. Υπάρχουν διάφοροι τρόποι προσδιορισμού της σημαντικότητας ενός όρου. Εδώ θα χρησιμοποιήσουμε μία από τις τεχνικές προσδιορισμού βαρών που χρησιμοποιείται και από πολλά συστήματα που βασίζονται στο Διανυσματικό μοντέλο ανάκτησης και αναλύεται σε επόμενο κεφάλαιο. Συμβολίζουμε με $nf_{x,j}$ την κανονικοποιημένη συχνότητα εμφάνισης (normalized frequency) του όρου $t_{x}$ στο έγγραφο $d_{j}$ , που δίνεται από τον εξής μαθηματικό τύπο:

nf_{x,j}=\frac{f_{x,j}}{\max_{y}\{f_{y,j}\}}

(3.8)

όπου $f_{x,j}$ είναι ο αριθμός των εμφανίσεων του όρου $t_{x}$ στο έγγραφο $d_{j}$ , ενώ $\max_{y}\{f_{y,j}\}$ είναι ο αριθμός εμφανίσεων του όρου με τις περισσότερες εμφανίσεις μέσα στο έγγραφο $d_{j}$ . Επομένως, η τιμή $nf_{x,j}$ είναι κανονικοποιημένη στο διάστημα τιμών [0,1].

Έστω τώρα ότι συμβολίζουμε με $idf_{x}$ την ανάστροφη συχνότητα εγγράφων (inverse document frequency) που μας δίνει τον αριθμό των εγγράφων που περιέχουν τον όρο $t_{x}$ . Για τον προσδιορισμό της τιμής αυτής χρησιμοποιείται ο ακόλουθος τύπος:

idf_{x}=\log{\frac{N}{n_{x}}}

(3.9)

όπου $N$ είναι ο συνολικός αριθμός εγγράφων της συλλογής και $n_{x}$ είναι ο αριθμός εγγράφων που περιέχουν τον όρο $t_{x}$ . Η κανονικοποιημένη μορφή $nidf_{x}$ δίνεται από τον τύπο:

nidf_{x}=\frac{idf_{x}}{\max_{y}\{idf_{y}\}}

(3.10)

όπου $\max_{y}\{idf_{y}\}$ είναι η μέγιστη τιμή $i d f$ που οφείλεται σε κάποιον όρο $t_{y}$ . Είναι προφανές ότι το $nidf_{x}$ παίρνει τιμές άπό το διάστημα [0,1]. Με βάση τις εξισώσεις 3.8 και 3.10 η τιμή του βάρους $w_{x,j}$ υπολογίζεται ως εξής [26, 60]:

w_{x,j}=nf_{x,j}\cdot nidf_{x}

(3.11)

Η Εξίσωση 3.11 στην ουσία αναφέρει ότι όσο περισσότερες φορές εμφανίζεται ο όρος $t_{x}$ στο έγγραφο $d_{j}$ , τόσο πιο σημαντικός γίνεται ο όρος για το έγγραφο. Ωστόσο, σε όσο περισσότερα έγγραφα εμφανίζεται ο όρος $t_{x}$ , τόσο μειώνεται η σημαντικότητά του. Για παράδειγμα, έστω ότι ο όρος ένας αναφέρεται πολλές φορές μέσα σε ένα έγγραφο. Άρα θα υπέθετε κάποιος η σημαντικότητα του όρου να είναι μεγάλη. Όμως, ο όρος αυτός βρίσκεται σχεδόν σε όλα τα έγγραφα, με αποτέλεσμα η σημαντικότητά της να μειώνεται.

Εφόσον έχουμε καθορίσει τον τρόπο αναπαράστασης του κάθε εγγράφου, στη συνέχεια περιγράφουμε τον τρόπο βαθμολόγησης του κάθε εγγράφου με βάση το ερώτημα. Αρχικά δίνεται η μέθοδος βαθμολόγησης στην περίπτωση του ερωτήματος $q_{and}$ . Ο καλύτερος βαθμός για ένα έγγραφο $d_{j}$ σύμφωνα με το ερώτημα σύζευξης αντιστοιχεί στην περίπτωση που και οι δύο όροι $t_{a}$ και $t_{b}$ περιέχονται στο έγγραφο. Σύμφωνα με το Σχήμα 3.5(α) η περίπτωση αυτή αντιστοιχεί στην επάνω-δεξιά γωνία του επιπέδου. Άρα, όσο πιο κοντά στη γωνία αυτή βρίσκεται το σημείο που αντιστοιχεί στο έγγραφο, τόσο μεγαλύτερος ο βαθμός του εγγράφου. Αν οι αποστάσεις μετρώνται χρησιμοποιώντας την Ευκλείδεια απόσταση, τότε η ομοιότητα του εγγράφου $d_{j}$ ως προς το ερώτημα $q_{and}$ δίνεται από τον ακόλουθο τύπο:

[S_{xboolean}(q_{and},d_{j})=1-\sqrt{\frac{(1-w_{a,j})^{2}+(1-w_{b,j})^{2}}{2}}]

(3.12)

Για την περίπτωση του ερωτήματος διάζευξης $q_{or}$ , το σημείο που πρέπει να αποφύγουμε είναι η κάτω-αριστερή γωνία στο επίπεδο του Σχήματος 3.5(β). Επομένως, η ομοιότητα του εγγράφου $d_{j}$ ως προς το ερώτημα $q_{or}$ δίνεται από τον τύπο:

[S_{xboolean}(q_{or},d_{j})=\sqrt{\frac{w_{a,j}^{2}+w_{b,j}^{2}}{2}}]

(3.13)

Παράδειγμα 3.1

Στη συνέχεια παραθέτουμε ένα παράδειγμα υπολογισμού των βαρών και της ομοιότητας στο εκτεταμένο Λογικό μοντέλο με βάση τη μικρή συλλογή του Σχήματος 3.1. Θεωρούμε ότι $t_{a}$ = κομήτης και $t_{b}$ = Χάλλεϋ. Επομένως, τα ερωτήματα $q_{and}$ και $q_{or}$ διατυπώνονται ως εξής: $q_{and}$ = κομήτης $\land$ Χάλλεϋ και $q_{or}$ = κομήτης $\lor$ Χάλλεϋ. Αρχικά πρέπει να υπολογίσουμε τα βάρη των όρων του ερωτήματος σε σχέση με τα έγγραφα που μας ενδιαφέρουν. Έστω ότι θέλουμε να υπολογίσουμε το βαθμό ομοιότητας των εγγράφων $d_{1}$ , $d_{2}$ , $d_{3}$ και $d_{4}$ . Στο έγγραφο $d_{1}$ ο όρος κομήτης εμφανίζεται μία φορά, επομένως $f_{a,1}$ = 1. Η μεγαλύτερη συχνότητα εμφάνισης στο έγγραφο είναι 1, αφού κανένας όρος του εγγράφου δεν εμφανίζεται περισσότερες από μία φορά. Επομένως, με βάση την Εξίσωση 3.8 η κανονικοποιμένη συχνότητα εμφάνισης του όρου κομήτης στο έγγραφο $d_{1}$ είναι $nf_{a,1}$ = 1. Με τη βοήθεια του τύπου 3.9 υπολογίζουμε την ανάστροφη συχνότητα εγγράφων. Ο όρος κομήτης εμφανίζεται σε $n_{a}$ = 4 έγγραφα. Εφόσον ο συνολικός αριθμός των εγγράφων της συλλογής είναι $N$ = 7, τότε σύμφωνα με την Εξίσωση 3.9 έχουμε $idf_{a}$ = 0.243. Η μέγιστη ανάστροφη συχνότητα εγγράφων αντιστοιχεί στον όρο που εμφανίζεται στα λιγότερα έγγραφα της συλλογής. Υπάρχουν όροι που εμφανίζονται σε ένα μόνο έγγραφο, όπως για παράδειγμα ο όρος τροχιά. Επομένως, η μέγιστη ανάστροφη συχνότητα εγγράφων είναι 0.845. Άρα, με βάση την Εξίσωση 3.10 έχουμε $nidf_{a}$ = 0.243/0.845 = 0.288. Αντικαθιστώντας τις αντίστοιχες τιμές που υπολογίσαμε προηγουμένως στον τύπο 3.11, προσδιορίζουμε το βάρος του όρου κομήτης στο έγγραφο $d_{1}$ . Άρα $w_{a,1}$ = 1 $\cdot$ 0.288 = 0.288. Η ίδια διαδικασία εφαρμόζεται και για τα υπόλοιπα έγγραφα. $\square$

Η προηγούμενη προσέγγιση γενικεύεται εύκολα και για περιπτώσεις περισσότερων όρων στο ερώτημα. Ωστόσο, μία πιο γενική προσέγγιση που υποστηρίζει πολλές μετρικές απόστασης (και όχι μόνο την Ευκλείδεια) μελετήθηκε στις εργασίες [57, 25]. Η προσέγγιση αυτή στηρίζεται στη χρήση $p$ -νορμών ( $p$ -norms) και προσφέρει μεγάλη ευελιξία στον ορισμό της ομοιότητας.

Έστω ότι ένα ερώτημα περιέχει $m$ όρους, $t_{1}$ , …, $t_{m}$ . Σύμφωνα με το μοντέλο $p$ -νόρμας, όπου $1\leq p\leq\infty$ , τα ερωτήματα σύζευξης και διάζευξης ορίζονται ως εξής:

q_{and}=t_{1}\land^{p}t_{2}\land^{p}...\land^{p}t_{m}

(3.14)

q_{or}=t_{1}\lor^{p}t_{2}\lor^{p}...\lor^{p}t_{m}

(3.15)

όπου $\land^{p}$ και $\lor^{p}$ είναι οι γενικευμένοι τελεστές για τη σύζευξη και τη διάζευξη αντίστοιχα με βάση το μοντέλο $p$ -νόρμας. Αν συμβολίσουμε με $w_{i,j}$ το βάρος του όρου $t_{i}$ στο έγγραφο $d_{j}$ τότε η ομοιότητα του εγγράφου $d_{j}$ με βάση τα ερωτήματα $q_{and}$ και $q_{or}$ προσδιορίζεται από τους εξής τύπους:

[S_{xboolean}(q_{and},d_{j})=1-\sqrt[p]{\frac{\sum_{i=1}^{m}(1-w_{i,j})^{p}}{m% }}]

(3.16)

[S_{xboolean}(q_{or},d_{j})=\sqrt[p]{\frac{\sum_{i=1}^{m}w_{i,j}^{p}}{m}}]

(3.17)

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

S_{xboolean}(q_{and},d_{j})=S_{xboolean}(q_{or},d_{j})=\frac{\sum_{i=1}^{m}w_{% i,j}}{m}

(3.18)

Αν θέσουμε $p$ = $\infty$ τότε η ομοιότητα ενός εγγράφου ως προς τα ερωτήματα σύζευξης και διάζευξης ταυτίζεται με την ομοιότητα όπως προσδιορίζεται από το μοντέλο Ασαφούς λογικής, δηλαδή:

S_{xboolean}(q_{and},d_{j})=\min_{i}\{w_{i,j}\}~{}~{}~{}\mbox{και}~{}~{}~{}S_{% xboolean}(q_{or},d_{j})=\max_{i}\{w_{i,j}\}

(3.19)

Ο μαθηματικός τύπος της ομοιότητας για ένα τυχαίο ερώτημα που περιέχει πολλούς τελεστές $\land^{p}$ και $\lor^{p}$ προσδιορίζεται εύκολα. Για παράδειγμα, έστω το ερώτημα $q$ = $t_{1}$ $\land^{p}$ ( $t_{2}$ $\lor^{p}$ $t_{3}$ ). Παρατηρούμε ότι η πράξη $\lor^{p}$ προηγείται της πράξης $\land^{p}$ . Η ομοιότητα ενός εγγράφου $d_{j}$ ως προς το $q$ είναι:

temp=\sqrt[p]{\frac{w_{2,j}^{p}+w_{3,j}^{p}}{2}}

(3.20)

	$\displaystyle S_{xboolean}(q,d_{j})$	$\displaystyle=$	$\displaystyle 1-\sqrt[p]{\frac{(1-w_{1,j})^{p}+(1-temp)^{p}}{2}}$		(3.21)
		$\displaystyle=$	$\displaystyle 1-\sqrt[p]{\frac{(1-w_{1,j})^{p}+\left(1-\sqrt[p]{\frac{w_{2,j}^% {p}+w_{3,j}^{p}}{2}}\right)^{p}}{2}}$		(3.21)

Παρατηρούμε ότι ο τύπος εφαρμόζεται αναδρομικά με βάση τον αριθμό των πράξεων $\land^{p}$ και $\lor^{p}$ που περιέχονται στο ερώτημα. Η παράμετρος $p$ καθορίζεται από το χρήστη, ενώ η βέλτιστη τιμή της παραμέτρου καθορίζεται πειραματικά και εξαρτάται κατά κύριο λόγο από τη συλλογή εγγράφων. Συνήθως χρησιμοποιείται μία τιμή του $p$ από το διάστημα [2,5] [31]. Επίσης, είναι δυνατή η χρήση διαφορετικών τιμών της παραμέτρου $p$ μέσα στο ίδιο ερώτημα, κάτι που προσφέρει ακόμη μεγαλύτερη ευελιξία στον τρόπο διατύπωσης των ερωτημάτων. Για παράδειγμα, ο χρήστης μπορεί να διατυπώσει ερωτήματα όπως: $t_{1}$ $\land^{\infty}$ ( $t_{2}$ $\lor^{3}$ $t_{3}$ ).

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

Το απλό Λογικό μοντέλο είναι από τα πρώτα μοντέλα ανάκτησης που έχουν χρησιμοποιηθεί, λόγω της απλότητάς του. Το μοντέλο στηρίζεται στη Θεωρία Συνόλων και τα ερωτήματα διατυπώνονται με τη βοήθεια λογικών εκφράσεων που περιέχουν όρους και τους βασικούς λογικούς τελεστές $\land$ (σύζευξη), $\lor$ (διάζευξη) και $\lnot$ (άρνηση). Για την αλλαγή της προτεραιότητας των τελεστών χρησιμοποιούνται παρενθέσεις.

Δύο από τα βασικά μειονεκτήματα του απλού Λογικού μοντέλου είναι η απουσία βαθμολόγησης των εγγράφων ως προς ερώτημα και το γεγονός ότι το πλήθος των εγγράφων της απάντησης είναι είτε πολύ μικρό είτε πολύ μεγάλο. Επομένως, οι ερευνητές στράφηκαν προς εναλλακτικά μοντέλα με στόχο την απαλοιφή των προβλημάτων του απλού Λογικού μοντέλου. Μία από τις σημαντικότερες επεκτάσεις οδήγησε στο εκτεταμένο Λογικό μοντέλο με χρήση $p$ -νορμών που περιγράφεται αναλυτικά στην εργασία [57] καθώς επίσης και στη διδακτορική διατριβή του Fox [25].

Ο ενδιαφερόμενος αναγνώστης μπορεί να ανατρέξει επίσης και σε ένα πλήθος άλλων ερευνητικών εργασιών στις οποίες μελετάται η συμπεριφορά του απλού και του εκτεταμένου Λογικού μοντέλου και συγκρίνεται η απόδοσή του με άλλα μοντέλα ανάκτησης. Χαρακτηριστικά αναφέρουμε την εργασία [62] όπου παρουσιάζονται οι μέθοδοι προσδιορισμού ομοιότητας εγγράφων σε συστήματα που χρησιμοποιούν Λογικά μοντέλα και την εργασία [31] όπου γίνεται μία ανασκόπηση των μοντέλων ανάκτησης που χρησιμοποιούνται στον παγκόσμιο ιστό.

3.5 Ασκήσεις

3.1

Ποιά είναι κατά τη γνώμη σας τα πλεονεκτήματα και τα μειονεκτήματα του απλού Λογικού μοντέλου;
3.2

Ποιές είναι οι επεκτάσεις που προσφέρει το εκτεταμένο Λογικό μοντέλο;
3.3

Να περιγράψετε τον τρόπο προσδιορισμού της ομοιότητας ενός εγγράφου με ένα ερώτημα με βάση τον τελεστή OR ( $q_{or}$ ) και τον τελεστή AND ( $q_{and}$ ).
3.4

Να διατυπώσετε τον μαθηματικό τύπο που δίνει την ομοιότητα μεταξύ ενός εγγράφου της συλλογής και του ερωτήματος $q$ = $t_{1}$ $\land^{p}$ ( $t_{2}$ $\lor^{p}$ $t_{3}$ ).
3.5

Ποιά είναι η χρησιμότητα της ανάστροφης συχνότητας εγγράφων ( $i d f$ );
3.6

Για ποιό λόγο πιστεύετε ότι χρησιμοποιείται ο λογάριθμος στον ορισμό της ποσότητας $i d f$ ; Δεν θα μπορούσε το μοντέλο να λειτουργήσει χωρίς λογαρίθμηση;
3.7

Να αναφέρετε εφαρμογές όπου το απλό Λογικό μοντέλο είναι αρκετό και περιπτώσεις όπου το εκτεταμένο Λογικό μοντέλο είναι προτιμότερο.
3.8

Για τη συλλογή εγγράφων του Σχήματος 3.1 να κατασκευάσετε έναν αντεστραμμένο κατάλογο και να τον χρησιμοποιήσετε για την απάντηση των ερωτημάτων: (i) Χάλλεϋ OR αστρονόμος, (ii) πλανήτης AND Δίας, (iii) Άρης OR δορυφόρους. Σχολιάστε για την απόδοση στην εκτέλεση των ερωτημάτων αυτών απουσία καταλόγου.
3.9

Να κατασκευαστεί πρόγραμμα που να διαβάζει τη συλλογή εγγράφων CRAN και στη συνέχεια να δίνει στο χρήστη τη δυνατότητα να χρησιμοποιεί είτε το απλό Λογικό μοντέλο είτε το εκτεταμένο Λογικό μοντέλο για την επεξεργασία των ερωτημάτων. Θεωρήστε ότι δεν μας ενδιαφέρει ο κατάλογος.
3.10

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

Δίνεται το ερώτημα $q=t_{1}\land t_{2}\land(t_{3}\lor\lnot t_{4})$ . Να διατυπώσετε το ερώτημα σε διαζευκτική κανονική μορφή και να βρείτε έναν αλγόριθμο υπολογισμού της διαζευκτικής κανονικής μορφής για κάθε λογική έκφραση.
3.12

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