Γενικευμένο Λογικό Μοντέλο (Generalized Boolean Model)


Στο απλό μοντέλο διανυσματικού χώρου όπως είπαμε κάθε όρος, του ευρετηρίου παρίσταται με ένα διάνυσμα, ti, στο χώρο των n-διαστάσεων όπου n είναι το πλήθος των διακριτών όρων στη συλλογή. Τα διανύσματα T={Τ1, Τ2, ...,Τn} θεωρούνται ότι είναι ανεξάρτητα και ότι σχηματίζουν μια βάση στο χώρο Rn. Τα διανύσματα είναι ανά δύο ορθογώνια και ως εκ τούτου οι όροι θεωρούνται μεταξύ τους ανεξάρτητοι. Τα κείμενα και τα ερωτήματα παρίστανται ως γραμμικοί συνδυασμοί των διανυσμάτων T. Προφανώς η υπόθεση αυτή είναι απλουστευμένη και γίνεται για πρακτικούς λόγους. Το 1985 ο Wong et al. πρότεινε μια γενίκευση του μοντέλου του διανυσματικού χώρου έτσι ώστε τα διανύσματα των όρων είναι γραμμικώς ανεξάρτητα αλλά δεν είναι ανά δύο ορθογώνια. Στο γενικευμένο αυτό διανυσματικό μοντέλο το εσωτερικό γινόμενο δύο όρων του λεξιλογίου είναι διάφορο του μηδενός, δηλαδή οι όροι δεν είναι ορθογώνιοι ή ανεξάρτητοι μεταξύ τους αλλά το γινόμενό τους εκφράζει την μεταξύ τους συσχέτιση. Η συσχέτιση μεταξύ δύο όρων εκφράζεται με βάση τη συχνότητα συνεμφάνισής τους στα κείμενα της συλλογής αλλά και των βαρών τους. Έστω {t1, t2,…,tn} το σύνολο των όρων μιας συλλογής και wij είναι το βάρος του όρου ti στο κείμενο dj.
ms

Αν οι όροι ενός κειμένου έχουν δυαδικά βάρη που δηλώνουν την ύπαρξη ή όχι του αντίστοιχου όρου στο κείμενο τότε μπορούμε να δούμε το κείμενο ως σύζευξη των μεταβλητών t1, …, tn. Αν έχουμε n όρους τότε έχουμε 2n δυνατούς συνδυασμούς (συζεύξεις όρων). Τα διανύσματα αυτά αναφέρονται ως minterms και θα τα συμβολίζουμε με mk k=1,…2n. Τα διανύσματα αυτά ουσιαστικά ειναι τα δομικά στοιχεία μιας Boolean άλγεβρας B2n. Μια λογική παράσταση (ένα κείμενο ή ένας όρος) μπορεί να γραφτεί ως μια διαζευκτική κανονική μορφή, δηλαδή ως άθροισμα τέτοιων minterm διανυσμάτων. Συνεπώς έχουμε:
docs

Το m7 για παράδειγμα παριστά τα κείμενα τα οποία περιέχουν μόνο τους όρους t2 και t3. Όταν υπάρχει ένα τέτοιο κείμενο στη συλλογή, που περιέχει δηλαδή, μόνο τους όρους t2 και t3 λέμε ότι το αντίστοιχο minterm είναι ενεργό και ότι υπάρχει μια εξάρτηση (συσχέτιση) μεταξύ των δύο όρων. Ορίζεται έτσι ο συντελεστής συσχέτισης
docs

Ο συντελεστής αυτός ουσιαστικά δηλώνει το πλήθος των εμφανίσεων κάθε όρου στα ενεργά minterms ή στη περίπτωση που οι όροι έχουν βάρη στο διάστημα [0, 1] τότε ο συντελεστής συσχέτισης ισούται με το άθροισμα των βαρών αυτών. Σε διανυσματική μορφή τα 2n minterms της άλγεβρας B2n παρίστανται μοναδικά από τα 2n μοναδιαία διανύσματα ei στο χώρο των πραγματικών αριθμών διάστασης 2n.
docs

Κατασκευάζουμε τα διανύσματα των όρων από τα διανύσματα της βάσης (ej) που αντιστοιχούν στα minterms τα οποία έχουν μη μηδενικό συντελεστή συσχέτισης για ένα συγκεκριμένο όρο.
docs

Από τη σχέση αυτή προκύπτει ότι:
docs

Δηλαδή τα ti και tj δεν είναι ορθογώνια αλλά αντανακλούν την συσχέτιση που υπάρχει μεταξύ των δύο όρων ανάλογα με τη συχνότητα συνεμφανίσεών τους αλλά του βάρους τους στα αρχικά κείμενα. Έτσι, όταν υπολογιστούν τα διανύσματα των όρων μπορούμε να «μεταφράσουμε» τα ερωτήματα και τα κείμενα σε minterm διανύσματα και να υπολογίσουμε τις ομοιότητες των. Ισχύει ότι: Τα διανύσματα των κειμένων γράφονται τώρα με βάση τα διανύσματα ως εξής:
docs

Ομοίως το ερώτημα γράφεται ως:
docs

. Για την αξιολόγηση των κειμένων σε σχέση με το ερώτημα, q, υπολογίζουμε το σκορ των κειμένων σύμφωνα με τη μετρική του συνημιτόνου για τα κείμενα και το ερώτημα . Παράδειγμα: Έστω ότι έχουμε μια συλλογή 10 κειμένων και το λεξιλόγιο περιλαμβάνει τρεις όρους {t1, t2, t3}:
vocabulary

Υπολογίζουμε τους συντελεστές συσχέτισης:
vocabulary

Τα διανύσματα των όρων (tj) μπορούν να γραφτούν ως γραμμικός συνδυασμός των διανυσμάτων της βάσης (ej) όπου ej είναι τα μοναδιαία διανύσματα στο χώρο των 2^3=8 διαστάσεων. Θα θεωρήσουμε τα διανύσματα αυτά νορμαλισμένα με την Ευκλείδια νόρμα.
docs

Έστω ότι έχουμε το ερώτημα: q=(t1, t2). Τότε στα διανύσματα των κειμένων γράφονται ως εξής:
docs

Αντικαθιστώντας τα tj από τις σχέσεις (1) παραπάνω υπολογίζουμε το :
docs

Ομοίως τα κείμενα της βάσης γράφονται:
docs

Η αξιολόγηση των κειμένων γίνεται με την συνάρτηση cosine:
sims

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

Αναφορές

  1. Wong, S. K. M., Ziarko, W., Wong, P. C. N. Generalized vector space model on information retrieval. In Proceedings of the 8 th Annual Int'l ACM-SIGIR Conference, New York, 18--25, June 1985.