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

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

themata5.pdf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Προσοχή

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

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

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

Θέμα 1

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

α. Στο μοντέλο διανυσματικού χώρου ένα κείμενο και ένα ερώτημα παριστάνονται ως διανύσματα όρων, π.χ. \(d\) και \(q\), και η συνάφεια υπολογίζεται συνήθως με συνημίτονο ή εσωτερικό γινόμενο. Για εξατομίκευση, ορίζουμε επιπλέον ένα προφίλ χρήστη \(u\) στον ίδιο χώρο όρων (ή σε μικρότερο λανθάνοντα χώρο), π.χ. \(u=(u_1,\dots,u_{|V|})\). Το προφίλ μπορεί να προκύπτει ρητά (προτιμήσεις, κατηγορίες, δημογραφικά) ή έμμεσα (ιστορικό αναζητήσεων, κλικ, χρόνος παραμονής, αγορές, αποθηκευμένα κείμενα, ανατροφοδότηση συνάφειας). Ως αναπαράσταση μπορεί να χρησιμοποιηθεί: σταθμισμένο διάνυσμα όρων από τα κείμενα που επέλεξε ο χρήστης, κέντρο συστάδας ενδιαφερόντων, διάνυσμα κατηγοριών/topics, ή λανθάνον διάνυσμα από παραγοντοποίηση/ενσωματώσεις.

Η ενσωμάτωση γίνεται συνήθως με τροποποίηση του ερωτήματος ή της βαθμολόγησης: $\(q_u = q+\lambda u, \qquad \text{score}(d,q_u)=\cos(d,q_u)\)$ ή με κανόνα Rocchio: $\(q_u=\alpha q+\beta\frac{1}{|R|}\sum_{d\in R}d-\gamma\frac{1}{|N|}\sum_{d\in N}d,\)$ όπου \(R,N\) είναι σχετικά/μη σχετικά κείμενα του χρήστη. Εναλλακτικά, το προφίλ μπορεί να επηρεάζει τα βάρη των όρων, το φιλτράρισμα/επανακατάταξη των αποτελεσμάτων ή τον υπολογισμό ομοιότητας με όρους χρήστη. Έτσι η τελική διάταξη εξαρτάται από το \(u\).

β. Μία δομή ανεστραμμένου αρχείου αποτελείται από λεξικό όρων και, για κάθε όρο, μία λίστα εγγραφών (postings) με αύξοντα αναγνωριστικά κειμένων (docIDs), συχνότητες και θέσεις. Για εισαγωγή νέου κειμένου: του ανατίθεται docID, εξάγονται οι όροι του και για κάθε όρο ενημερώνεται το λεξικό και η postings list (προστίθεται το docID στη σωστή θέση ώστε να διατηρείται η ταξινόμηση, ή γράφεται σε buffer και γίνεται περιοδική συγχώνευση με το κύριο ευρετήριο). Για διαγραφή: είτε αφαιρείται το docID από όλες τις λίστες (χρειάζεται συχνά αντίστροφο ευρετήριο docID \(\to\) όροι), είτε χρησιμοποιείται σημαία διαγραφής/tombstone και αργότερα συμπίεση/ανασυγκρότηση. Πρέπει να ενημερώνονται συχνότητες συλλογής, \(df\), και ενδεχομένως \(idf\).

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

Θέμα 2

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

α. Έστω \(n=10\) και \(N=\binom{10}{2}=45\) ζεύγη. Για το Kendall tau, αν \(D\) είναι το πλήθος αντιστροφών ως προς την ιδανική σειρά και \(C=N-D\) οι συμφωνίες, τότε $\(\tau=\frac{C-D}{N}=1-\frac{2D}{N}.\)$ Για το Spearman: $\(\rho=1-\frac{6\sum_i d_i^2}{n(n^2-1)},\)$ όπου \(d_i\) η διαφορά ιδανικής και πραγματικής κατάταξης για το κείμενο \(d_i\).

  • Μηχανή M1: Η σειρά ιδανικών κατατάξεων των κειμένων όπως εμφανίζονται στη λίστα είναι $\([2,3,4,5,1,7,6,8,9,10].\)$ Έχουμε \(D=5\) αντιστροφές, άρα $\(\tau_{M1}=1-\frac{2\cdot5}{45}=\frac{7}{9}\approx 0.778.\)$ Οι διαφορές κατάταξης ανά κείμενο δίνουν \(\sum d_i^2=22\), άρα $\(\rho_{M1}=1-\frac{6\cdot22}{10(100-1)} =1-\frac{132}{990} =\frac{13}{15}\approx 0.867.\)$

  • Μηχανή M2: Η λίστα δίνει ιδανικές κατατάξεις $\([9,4,5,1,2,7,6,8,10,3].\)$ Έχουμε \(D=19\) αντιστροφές, άρα $\(\tau_{M2}=1-\frac{2\cdot19}{45} =\frac{7}{45}\approx 0.156.\)$ Οι διαφορές κατάταξης δίνουν \(\sum d_i^2=142\), άρα $\(\rho_{M2}=1-\frac{6\cdot142}{10(100-1)} =1-\frac{852}{990} =\frac{23}{165}\approx 0.139.\)$

Και με τις δύο μετρικές η M1 είναι πολύ πιο κοντά στην ιδανική λίστα από την M2, αφού έχει μεγαλύτερα \(\tau\) και \(\rho\).

β. Βασικές τεχνικές μείωσης διαστατικότητας στον διανυσματικό χώρο είναι:

  1. SVD / LSI / PCA: Κατασκευάζεται ο πίνακας όρων–κειμένων \(A\) (συχνά με βάρη tf-idf) και υπολογίζεται η αποδόμηση $\(A\approx U_k\Sigma_k V_k^T.\)$ Τα κείμενα και οι όροι αναπαρίστανται σε \(k\) λανθάνοντες διαστάσεις. Είναι τεχνική εξαρτώμενη από τα δεδομένα, βέλτιστη ως προς τετραγωνικό σφάλμα ανακατασκευής, αλλά υπολογιστικά ακριβή και δύσκολη στη δυναμική ενημέρωση.
  2. Random projection: Πολλαπλασιασμός με τυχαίο πίνακα μικρής τάξης. Είναι ανεξάρτητη από τα δεδομένα, φθηνή και διατηρεί προσεγγιστικά τις αποστάσεις (Johnson–Lindenstrauss), αλλά δίνει λιγότερο ερμηνεύσιμες διαστάσεις.
  3. Επιλογή όρων/χαρακτηριστικών: Αφαίρεση stopwords, stemming, φίλτρα συχνότητας, chi-square, mutual information. Μειώνει διαστάσεις χωρίς να συνδυάζει όρους, αλλά μπορεί να χάσει χρήσιμη πληροφορία.
  4. Ομαδοποίηση όρων/κειμένων και πιθανοτικά μοντέλα θεμάτων (π.χ. LSA, PLSA, LDA): Οι αρχικές διαστάσεις αντικαθίστανται από ομάδες ή θέματα. Διαφέρουν ως προς το αν είναι γραμμικές/μη γραμμικές, αν είναι πιθανοτικές, το κόστος και την ερμηνευσιμότητα.

Θέμα 3

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

Η ανάθεση αναγνωριστικών κειμένων (Document Identifier Assignment) αντιστοιχίζει τίτλους/URL σε ακέραιους docIDs, ώστε κάθε postings list να περιέχει ακεραίους. Η σχέση με την αποδοτική τομή δύο λιστών είναι άμεση: για ερώτημα τομής δύο όρων, θέλουμε τα κείμενα που εμφανίζονται και στις δύο αντίστοιχες ανεστραμμένες λίστες. Αν οι λίστες είναι ταξινομημένες κατά docID, η τομή γίνεται με συγχώνευση (merge) σε χρόνο \(O(m+n)\) και με μικρή χρήση μνήμης, συγκρίνοντας ακεραίους και προωθώντας τον μικρότερο δείκτη.

Η επιλογή των docIDs επηρεάζει την απόδοση γιατί: - πρέπει να είναι μοναδικά και συνεπή σε όλες τις λίστες, ώστε να ταιριάζουν τα ίδια κείμενα· - μικρά, πυκνά και διατεταγμένα ακέραια IDs επιτρέπουν δυαδική αναζήτηση, skip pointers, bitmaps και καλύτερη τοπικότητα μνήμης/cache· - βοηθούν τη συμπίεση των postings (π.χ. delta encoding, Golomb/Rice), ιδίως αν τα IDs που εμφανίζονται μαζί σε λίστες έχουν μικρές διαφορές· - αν τα IDs ανατίθενται τυχαία, η τομή παραμένει ορθή αλλά χάνεται συχνά συμπίεση και τοπικότητα· αν ανατίθενται με κάποια ομαδοποίηση/σειρά που ακολουθεί τη συλλογή, μπορεί να βελτιωθεί η αποδοτικότητα.

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

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

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