Μετάβαση στο περιεχόμενο

Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 6)

themata6.pdf

ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΥ 2021 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30 (ΟΜΑΔΑ 6)

ΘΕΜΑ 1 ( Μονάδες 3,5 )

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

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

ΘΕΜΑ 2 ( Μονάδες 3.5 )

α. Θεωρήστε ότι έχουμε να χειριστούμε 10 κείμενα {d1, d2, …, d10} σε μια συλλογή κειμένων, και θέλουν να συγκρίνουμε δύο μηχανές ως προς το ιδανικό αποτέλεσμα, χρησιμοποιώντας τις μετρικές Kendal Tau και τον συνtτελεστή spearman. Έστω ότι έχουμε τις εξής λίστες αποτελεσμάτων:

  • Μηχανή M1 Λίστα: d8, d6, d3, d4, d5, d1, d2, d7, d9, d10
  • Μηχανή M2 Λίστα: d10 , d6, d4, d5, d1, d2, d7, d8, d9, d3
  • Ιδανική Μηχανή Λίστα: d1, d2, d3, d4, d5, d6, d7, d8, d9, d10

[sic: «συνtτελεστή» — το «t» είναι λατινικό στην εκφώνηση]

Συγκρίνετε τις δύο μηχανές χρησιμοποιώντας τις μετρικές Kendal Tau και τον συντελεστή Spearman.

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

ΘΕΜΑ 3 ( Μονάδες 3 )

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

Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις → 2021-02-f.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας): exams_2021/Çñßí½₧⌐₧ ö£Ö exams 2021/themata6.pdf

Λύσεις (⚪ AI, μη επαληθευμένο)

Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο

Προσοχή

Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.

AI λύσεις — 2021-02-f

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

Θέμα 1

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

α. Στο διανυσματικό μοντέλο, οι βασικές τεχνικές μείωσης διαστατικότητας είναι κυρίως οι εξής:

  1. Latent Semantic Indexing (LSI) / SVD / PCA. Γίνεται αποσύνθεση του πίνακα όρων-κειμένων \(X \approx U_k \Sigma_k V_k^T\), κρατώντας τις \(k\) μεγαλύτερες ιδιάζουσες τιμές. Οι όροι και τα κείμενα αναπαριστώνται σε \(k\)-διάστατο λανθάνοντα σημασιολογικό χώρο. Πλεονεκτεί στη σύλληψη συνωνυμίας/πολυσημίας, αλλά είναι υπολογιστικά ακριβή μέθοδος, δύσκολη σε ενημερώσεις και λιγότερο ερμηνεύσιμη.
  2. Random Projection / Random Indexing. Χρησιμοποιείται τυχαίος πίνακας προβολής για απεικόνιση σε μικρότερο χώρο, με βάση το λήμμα Johnson–Lindenstrauss που διατηρεί κατά προσέγγιση τις αποστάσεις. Είναι ανεξάρτητη από τα δεδομένα, φθηνή και φιλική σε ενημερώσεις, αλλά δεν δίνει σημασιολογικά ερμηνεύσιμες διαστάσεις και είναι προσεγγιστική.
  3. Συσταδοποίηση όρων ή/και κειμένων. Όμοιοι όροι ή όμοια κείμενα ομαδοποιούνται και κάθε ομάδα λειτουργεί ως μία διάσταση. Μειώνει τη διάσταση και είναι πιο ερμηνεύσιμη, αλλά χάνει λεπτομέρειες και εξαρτάται από τον αλγόριθμο συσταδοποίησης.
  4. Επιλογή χαρακτηριστικών/όρων (term selection/pruning). Κρατούνται μόνο οι πιο πληροφοριακοί όροι, π.χ. με βάση συχνότητα, \(idf\), πληροφοριακό κέρδος. Είναι απλή και γρήγορη, αλλά δεν δημιουργεί νέες λανθάνουσες διαστάσεις και μπορεί να απορρίψει χρήσιμη πληροφορία.
  5. Πιθανοτικά/λανθάνοντα μοντέλα θεμάτων (NMF, PLSA, LDA). Αναπαριστούν κείμενα και όρους μέσω \(k\) θεμάτων. Είναι ερμηνεύσιμα, αλλά απαιτούν επαναληπτική εκπαίδευση και είναι πιο πολύπλοκα.

Κύριες διαφορές: οι προβολικές μέθοδοι όπως LSI και Random Projection παράγουν νέες συνεχείς διαστάσεις, ενώ επιλογή/συσταδοποίηση είτε διατηρούν υποσύνολο χαρακτηριστικών είτε ομαδοποιούν υπάρχοντα. LSI είναι data-dependent και ακριβή αλλά σημασιολογικά ισχυρή· Random Projection είναι data-independent και φθηνή αλλά χωρίς άμεση ερμηνεία. Τα topic models δίνουν πιθανοτική ερμηνεία, ενώ οι SVD/PCA είναι αλγεβρικές μέθοδοι.

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

  • Εισαγωγή νέου κειμένου: Για κάθε όρο του νέου κειμένου προστίθεται το νέο docID στην αντίστοιχη λίστα. Αν τα docID εκχωρούνται αύξοντα, η εισαγωγή γίνεται στο τέλος των λιστών· διαφορετικά απαιτείται εισαγωγή σε ταξινομημένη θέση. Αν εμφανιστεί νέος όρος, δημιουργείται νέα καταχώριση στο λεξικό.
  • Διαγραφή κειμένου: Συνήθως δεν αφαιρείται αμέσως η εγγραφή από κάθε λίστα, αλλά χρησιμοποιείται tombstone/σημάδι διαγραφής και ένα ενεργό διάνυσμα εγκυρότητας. Η φυσική διαγραφή γίνεται αργότερα με αναδιοργάνωση/συμπίεση (garbage collection).
  • Βοηθητικές δομές: Λεξικό με B-tree/trie/hash, λίστες με blocks/overflow pages, B-trees ή LSM-style δομές, ή διατήρηση μικρού δυναμικού ευρετηρίου που κατά περιόδους συγχωνεύεται με το στατικό.

Προβλήματα δυναμοποίησης: - Οι μεταθέσεις είναι συνήθως συμπιεσμένες και ταξινομημένες· μια εισαγωγή/διαγραφή στη μέση απαιτεί αποσυμπίεση, μετατόπιση και επανασυμπίεση, άρα πολλαπλές εγγραφές δίσκου. - Κατακερματισμός χώρου, overflow pages και υποβάθμιση τοπικότητας. - Οι διαγραφές αφήνουν «τρύπες» ή έγκυρα/μη έγκυρα docID· αν δεν γίνει συμπίεση, τα ερωτήματα επιβαρύνονται. - Πρέπει να ενημερώνονται συνεπώς τα στατιστικά \(df\), \(N\), μήκη κειμένων και τα βάρη/κανόνες κατάταξης. - Τα skip pointers και οι δομές φραγμάτων χρειάζονται συντήρηση. - Απαιτείται έλεγχος ταυτοχρονισμού, συνέπειας και απομόνωσης (locking/versioning/snapshots), ενώ οι μαζικές αναδιοργανώσεις μπορούν να προκαλέσουν καθυστερήσεις.

Θέμα 2

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

α. Συγκρίνουμε κάθε μηχανή με την ιδανική λίστα \(d_1,d_2,\dots,d_{10}\). Η ιδανική κατάταξη δίνει στους όρους/κείμενα θέσεις \(1,2,\dots,10\).

Για τη μηχανή \(M_1\), οι θέσεις των \(d_1,\dots,d_{10}\) είναι [ (6,7,3,4,5,2,8,1,9,10). ] Για τη μηχανή \(M_2\), οι θέσεις είναι [ (5,6,10,3,4,2,7,8,9,1). ]

Με τον Kendall \(\tau\): [ \tau=\frac{C-D}{n(n-1)/2}, ] όπου \(C\) τα συμφωνούντα και \(D\) τα ασύμφωνα ζεύγη. Ισχύει \(C+D=45\).

  • Για \(M_1\): \(D=18\), άρα \(C=27\), οπότε [ \tau_1=\frac{27-18}{45}=0.2. ]
  • Για \(M_2\): \(D=23\), άρα \(C=22\), οπότε [ \tau_2=\frac{22-23}{45}=-\frac{1}{45}\approx -0.0222. ]

Με τον συντελεστή Spearman: [ \rho=1-\frac{6\sum_i d_i^2}{n(n^2-1)},\quad n=10,\quad n(n^2-1)=990. ]

  • Για \(M_1\): [ \sum_i d_i^2=(6-1)^2+(7-2)^2+(3-3)^2+\cdots+(10-10)^2=116, ] άρα [ \rho_1=1-\frac{6\cdot116}{990} =1-\frac{696}{990} =\frac{294}{990} =\frac{49}{165}\approx 0.2970. ]
  • Για \(M_2\): [ \sum_i d_i^2=180, ] άρα [ \rho_2=1-\frac{6\cdot180}{990} =1-\frac{1080}{990} =-\frac{90}{990} =-\frac{1}{11}\approx -0.0909. ]

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

β. Για μεταμηχανή που συγχωνεύει \(k\) λίστες αποτελεσμάτων, κατάλληλες πολιτικές είναι:

  1. Συγχώνευση με βάση βαθμούς (score fusion). Κανονικοποιούνται οι βαθμοί κάθε μηχανής, π.χ. min-max ή z-score, και υπολογίζεται [ s(d)=\sum_{j=1}^k w_j\, \hat s_j(d), ] όπου \(w_j\) δείχνει την αξιοπιστία της μηχανής \(j\). Παραλλαγές είναι τα CombSUM και CombMNZ, όπου το άθροισμα πολλαπλασιάζεται με το πλήθος μηχανών που επέστρεψαν το κείμενο.
  2. Συγχώνευση με βάση θέσεις/κατάταξη. Χρήση Borda count: [ s(d)=\sum_j (N-r_j(d)+1) ] ή Reciprocal Rank Fusion: [ s(d)=\sum_j \frac{1}{k+r_j(d)}. ] Η RRF είναι ανθεκτική όταν οι βαθμοί των μηχανών δεν είναι συγκρίσιμοι.
  3. Αθροιστική ψήφος/πλειοψηφία ή Condorcet. Γίνονται συγκρίσεις ζευγών κειμένων με βάση τις κατατάξεις των μηχανών και επιλέγεται η κατάταξη που κερδίζει τις περισσότερες pairwise αναμετρήσεις.
  4. Cluster-based συγχώνευση. Εκμεταλλευόμαστε συστάδες κειμένων είτε γνωστές εκ των προτέρων (π.χ. ίδιο site/topic) είτε παραγόμενες από τη σύμπτωση των κειμένων στις λίστες των μηχανών. Υπολογίζεται βαθμός συστάδας [ S(C)=\underset{d\in C}{\operatorname{agg}}\; s(d) ] π.χ. max ή άθροισμα κορυφαίων μελών ή πυκνότητα/συνοχή. Πρώτα κατατάσσονται οι συστάδες και μετά τα κείμενα εντός κάθε συστάδας, ή εφαρμόζεται ποινή σε πολλά κείμενα της ίδιας συστάδας ώστε να αυξηθεί η ποικιλομορφία: [ s'(d)=s(d)+\lambda S(C(d)), ] ή χρήση MMR/round-robin ανά συστάδα. Έτσι αποφεύγονται επαναλαμβανόμενα σχεδόν ίδια αποτελέσματα και αξιοποιείται η πληροφορία ότι ορισμένα κείμενα ανήκουν στην ίδια ομάδα.

Θέμα 3

Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή

Η ανάθεση αναγνωριστικών κειμένων (Document Identifier Assignment) είναι η επιλογή μιας σταθερής αμφιμονοσήμαντης απεικόνισης από κάθε τίτλο/URL σε έναν ακέραιο, π.χ. [ \phi:{\text{τίτλος/URL}}\to{1,\dots,N}. ] Οι ανεστραμμένες λίστες ενός όρου \(t\) αποθηκεύουν ταξινομημένα τα \(\phi(d)\) για όσα κείμενα \(d\) περιέχουν τον \(t\).

Η σχέση με την αποδοτική τομή δύο λιστών είναι άμεση:

  • Η τομή δύο λιστών \(L_a\) και \(L_b\) γίνεται με συγχώνευση/δύο δείκτες, αν οι λίστες είναι ταξινομημένες κατά docID. Σε κάθε βήμα συγκρίνονται ακέραιοι και προχωρά ο δείκτης της μικρότερης τιμής· όταν οι τιμές είναι ίσες, το κείμενο ανήκει στην τομή. Έτσι η τομή κοστίζει \(O(|L_a|+|L_b|)\) συγκρίσεις.
  • Η απεικόνιση σε μικρούς ακέραιους αντί για μεγάλες συμβολοσειρές (τίτλους/URL) κάνει τις συγκρίσεις φθηνές, επιτρέπει αριθμητική ταξινόμηση και υποστηρίζει δομές όπως skip pointers, galloping search και δυαδική αναζήτηση στη μεγαλύτερη λίστα.
  • Αν τα docID είναι πυκνά και συνεχή, μπορούν να χρησιμοποιηθούν και bitmaps: κάθε λίστα παριστάνεται ως διάνυσμα bits μήκους \(N\), και η τομή γίνεται με bitwise AND, πολύ αποδοτικά για συχνούς όρους. Επίσης, η κωδικοποίηση διαφορών (gap/delta encoding) γίνεται αποδοτικότερη.
  • Για να είναι σωστή και γρήγορη η τομή, η ανάθεση πρέπει να είναι συνεπής και σταθερή. Αν αλλάζουν συνεχώς τα docID, πρέπει να ενημερώνονται όλες οι λίστες και χάνονται τα πλεονεκτήματα της ταξινομημένης/συμπιεσμένης αναπαράστασης.
  • Μια καλή ανάθεση μπορεί να είναι απλώς αύξουσα/πυκνή, ή ακόμη και να ομαδοποιεί παρόμοια κείμενα ώστε να μειώνονται κατά μέσο όρο τα gaps στις λίστες και να βελτιώνεται η συμπίεση και η τοπικότητα κατά την ανάκτηση.

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

✔ Επιβεβαίωσε · ✖ Βρήκα λάθος

✖ Βρήκα λάθος στη μεταγραφή