Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 4)¶
themata412.pdf¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΥ 2021 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30 (ΟΜΑΔΑ 4)
ΘΕΜΑ 1 ( Μονάδες 3.5 )
α. Εξηγήστε πως το μοντέλο διανυσματικού χώρου θα μπορούσε να ενσωματώσει τεχνικές εξατομίκευσης έτσι ώστε το αποτέλεσμα (τελική ταξινομημένη λίστα κειμένων) στη διατύπωση ενός ερωτήματος να εξαρτάται και από τον χρήστη που διατύπωσε το ερώτημα. Πιο συγκεκριμένα προτείνετε τρόπους αναπαράστασης του προφίλ του χρήστη, και ενσωμάτωσης του προφίλ αυτού κατά την διατύπωση του ερωτήματος.
β, Ένα σημαντικό πρόβλημα στο μοντέλο διανυσματικού χώρου είναι η μεγάλη διάσταση του χώρου που παράγεται καθώς το πλήθος των όρων, που αποτελεί και το μέγεθος του χώρου είναι γενικά μεγάλο. Το πρόβλημα αυτό μπορεί να αντιμετωπιστεί με τη χρήση τεχνικών μείωσης διαστατικότητας που αναπαριστούν και κείμενα και όρους σε χώρους αρκετά μικρότερης τάξεως. Αναφέρετε ποιες είναι οι βασικές τεχνικές μείωσης διαστατικότητας και ποιες οι διαφορές μεταξύ τους.
ΘΕΜΑ 2 ( Μονάδες 3.5 )¶
α. Θεωρήστε ότι έχουμε να χειριστούμε 10 κείμενα {d1, d2, …, d10} σε μια συλλογή κειμένων, και θέλουμε να συγκρίνουμε δύο μηχανές ως προς το ιδανικό αποτέλεσμα, χρησιμοποιώντας τις μετρικές Kendal Tau και τον συντελεστή spearman. Έστω ότι έχουμε τις εξής λίστες αποτελεσμάτων:
- Μηχανή M1 Λίστα: d10 , d3, d4, d5, d1, d2, d7, d6, d8, d9
- Μηχανή M2 Λίστα: ,d3, d4, d5, d1, d2, d7, d6, d8, d9, d10
- Ιδανική Μηχανή Λίστα: d1, d2, d3, d4, d5, d6, d7, d8, d9, d10
Συγκρίνετε τις δύο μηχανές χρησιμοποιώντας τις μετρικές Kendal Tau και τον συντελεστή Spearman.
β. Μία μεταμηχανή αναζήτησης διαχειρίζεται ερωτήματα χρησιμοποιώντας άλλες μηχανές και συγχωνεύοντας (με κάποια πολιτική) τα αποτελέσματά τους. Έστω λοιπόν μία μεταμηχανή που για ένα ερώτημα ρωτάει k μηχανές αναζήτησης και συγχωνεύει τις λίστες αποτελεσμάτων τους. Παρουσιάστε κατάλληλες πολιτικές συγχώνευσης για την παραγωγή του τελικού αποτελέσματος, αξιοποιώντας και ύπαρξη συστάδων ανάμεσα στα κείμενα.
ΘΕΜΑ 3 ( Μονάδες 3 )¶
Στο πρόβλημα του Document Identifier Assignment (ανάθεση αναγνωριστικών σε κείμενα) θέλουμε να απεικονίσουμε τίτλους (ή url) κειμένων σε ακέραιους αριθμούς, ώστε να υλοποιηθούν οι ανεστραμμένες λίστες του ανεστραμμένου αρχείου της συλλογής. Δηλαδή σε κάθε ανεστραμμένη λίστα μίας λέξης θα αναγράφονται ακέραιοι αριθμοί που θα αντιστοιχούν στα κείμενα στα οποία η λέξη εμφανίζεται. Εξηγήστε την σχέση που έχει η ανάθεση αυτή με τον αποδοτικό υπολογισμό της τομής δύο
λιστών του ανεστραμμένου αρχείου όταν θέλουμε να απαντήσουμε σε ερωτήματα τομής δύο όρων.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (διπλότυπο της ίδιας σελίδας, ελέγχθηκε ότι είναι πανομοιότυπο με το τμήμα
themata412.pdf· λύσεις →2021-02-d.solutions.md):exams_2021/Çñßí½₧⌐₧ ö£Ö exams 2021/themata4.pdf
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02-d¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
α. Στο διανυσματικό μοντέλο, το προφίλ χρήστη μπορεί να αναπαρασταθεί ως διάνυσμα βαρών όρων \(\vec{u}=(u_1,\ldots,u_V)\), αντίστοιχο με τα διανύσματα κειμένων και ερωτημάτων. Κατασκευάζεται από το ιστορικό του χρήστη (ερωτήματα, κλικ, αξιολογήσεις, αγορές κ.λπ.), π.χ. ως σταθμισμένο άθροισμα TF-IDF διανυσμάτων των κειμένων που επέλεξε, με χρονική εξασθένηση και με αφαίρεση/αρνητικά βάρη για κείμενα που απέρριψε. Εναλλακτικά, το προφίλ μπορεί να είναι σύνολο διανυσμάτων (βραχυπρόθεσμο και μακροπρόθεσμο), διάνυσμα σε μειωμένο χώρο (LSI/topics) ή σύνολο κατηγοριών/λέξεων-κλειδιών με βάρη.
Η ενσωμάτωση στο ερώτημα μπορεί να γίνει με: 1. Διεύρυνση ερωτήματος Rocchio: \(\vec{q}'=\alpha \vec{q}+\beta \vec{u}_{+}-\gamma \vec{u}_{-}\), όπου \(\vec{u}_{+},\vec{u}_{-}\) είναι θετικά/αρνητικά μέρη του προφίλ· έπειτα ταξινόμηση με \(\cos(\vec{d},\vec{q}')\). 2. Γραμμικό συνδυασμό ομοιοτήτων: \(\mathrm{score}(d,q,u)=\lambda \cos(\vec{d},\vec{q})+(1-\lambda)\cos(\vec{d},\vec{u})\), με κανονικοποίηση και κατάλληλο \(\lambda\). 3. Επανακατάταξη κορυφαίων αποτελεσμάτων με βάση την ομοιότητα με το προφίλ ή/και ανάθεση μεγαλύτερων βαρών σε όρους του προφίλ κατά τον υπολογισμό του ερωτήματος.
β. Βασικές τεχνικές μείωσης διαστατικότητας: - SVD/LSI (Latent Semantic Indexing): αποσύνθεση του πίνακα όρων-κειμένων και διατήρηση των \(k\) μεγαλύτερων ιδιαζουσών τιμών· mappάρει και κείμενα και όρους σε χώρο \(k\) διαστάσεων. Είναι τεχνική εξαρτώμενη από τα δεδομένα, βέλτιστη ως προς το σφάλμα Frobenius/L2 για δεδομένο \(k\), αλλά υπολογιστικά ακριβή και λιγότερο ερμηνεύσιμη. - PCA: ουσιαστικά συγγενής του SVD (σε κεντραρισμένα δεδομένα) και βρίσκει ορθογώνιες διευθύνσεις μέγιστης διακύμανσης. - Random Projection: πολλαπλασιασμός με τυχαίο πίνακα μικρής διάστασης· βασίζεται στο λήμμα Johnson–Lindenstrauss, είναι γρήγορη και ανεξάρτητη από τα δεδομένα, αλλά δίνει προσεγγιστική διατήρηση αποστάσεων και όχι σαφή σημασιολογική ερμηνεία. - LDA/topic models: προβολή κειμένων σε κατανομές θεμάτων και όρων σε κατανομές πάνω σε θέματα· πιθανοτικό μοντέλο, ερμηνεύσιμο, αλλά επαναληπτικό και με υποθέσεις. - NMF: παραγοντοποίηση με μη αρνητικούς παράγοντες, δίνει πιο ερμηνεύσιμες/αραιές διαστάσεις από το SVD, αλλά απαιτεί επαναληπτική βελτιστοποίηση.
Κύριες διαφορές: εξαρτώμενες από τα δεδομένα (SVD/PCA/LDA/NMF) έναντι ανεξάρτητης (random projection), γραμμικές/φασματικές έναντι πιθανοτικών ή μη αρνητικών, βέλτιστη προσέγγιση χαμηλού βαθμού έναντι προσεγγιστικής διατήρησης αποστάσεων, και διαφορετικό κόστος/ερμηνευσιμότητα.
Θέμα 2¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: υψηλή
α. Η ιδανική κατάταξη είναι \(d_1,d_2,\ldots,d_{10}\), άρα η ιδανική θέση του \(d_i\) είναι \(i\).
Για τη μηχανή \(M_1\), οι θέσεις των \(d_1,\ldots,d_{10}\) είναι: [ (5,6,2,3,4,8,7,9,10,1). ] Οι διαφορές από την ιδανική κατάταξη είναι [ (4,4,-1,-1,-1,2,0,1,1,-9), ] άρα [ \sum d_i^2=4^2+4^2+(-1)^2+(-1)^2+(-1)^2+2^2+0^2+1^2+1^2+(-9)^2=122. ] Έτσι [ \rho_{S,M1}=1-\frac{6\cdot122}{10(10^2-1)} =1-\frac{732}{990} =\frac{43}{165}\approx 0.2606. ] Για Kendall, στη σειρά του \(M_1\) οι ιδανικές θέσεις είναι [ (10,3,4,5,1,2,7,6,8,9). ] Οι αντιστροφές είναι \(16\), άρα \(C=45-16=29\), \(D=16\) και [ \tau_{M1}=\frac{C-D}{45}=\frac{29-16}{45} =\frac{13}{45}\approx 0.2889. ]
Για τη μηχανή \(M_2\), με τη λίστα \(d_3,d_4,d_5,d_1,d_2,d_7,d_6,d_8,d_9,d_{10}\), οι θέσεις των \(d_1,\ldots,d_{10}\) είναι: [ (4,5,1,2,3,7,6,8,9,10). ] Οι διαφορές είναι [ (3,3,-2,-2,-2,1,-1,0,0,0), ] και [ \sum d_i^2=3^2+3^2+(-2)^2+(-2)^2+(-2)^2+1^2+(-1)^2=32. ] Άρα [ \rho_{S,M2}=1-\frac{6\cdot32}{990} =1-\frac{192}{990} =\frac{133}{165}\approx 0.8061. ] Για Kendall, οι ιδανικές θέσεις στη σειρά του \(M_2\) είναι [ (3,4,5,1,2,7,6,8,9,10), ] με \(7\) αντιστροφές. Άρα \(C=38\), \(D=7\) και [ \tau_{M2}=\frac{38-7}{45}=\frac{31}{45}\approx 0.6889. ]
Συμπέρασμα: η \(M_2\) είναι πολύ πιο κοντά στην ιδανική κατάταξη, τόσο με Kendall (\(\tau_{M2}=0.6889>\tau_{M1}=0.2889\)) όσο και με Spearman (\(\rho_{S,M2}=0.8061>\rho_{S,M1}=0.2606\)).
β. Για μεταμηχανή που συγχωνεύει \(k\) λίστες \(L_j\), πρώτα κανονικοποιούμε τις θέσεις/βαθμολογίες. Χρήσιμες πολιτικές: - CombSUM: \(\mathrm{score}(d)=\sum_j s_j(d)\), όπου \(s_j(d)=0\) αν το \(d\notin L_j\). - CombMNZ: \(\mathrm{score}(d)=|\{j:d\in L_j\}|\cdot \sum_j s_j(d)\), ώστε να επιβραβεύονται έγγραφα που βρίσκονται σε πολλές μηχανές. - Σταθμισμένη ψηφοφορία/Borda ή Reciprocal Rank Fusion: \(\mathrm{score}(d)=\sum_j w_j (N_j-r_j(d)+1)\) ή \(\sum_j w_j/(k+r_j(d))\), με βάρη αξιοπιστίας μηχανών. - Συγχώνευση με συστάδες: ομαδοποιούμε τα retrieved έγγραφα (προϋπολογισμένες συστάδες συλλογής ή δυναμική ομαδοποίηση με βάση ομοιότητα κειμένων/συνερμφάνιση στις λίστες). Για κάθε συστάδα \(C\) και μηχανή \(j\) ορίζουμε βαθμολογία συστάδας, π.χ. [ S_j(C)=\max_{d\in C}s_j(d)\quad\text{ή}\quad S_j(C)=\frac{1}{|C|}\sum_{d\in C}s_j(d), ] και συνολική βαθμολογία συστάδας \(S(C)=\sum_j w_j S_j(C)\) ή με CombMNZ ανά πλήθος μηχανών που την υποστηρίζουν. Στη συνέχεια κατανέμουμε θέσεις στις κορυφαίες συστάδες (π.χ. quotas ή round-robin), ώστε να αξιοποιείται η συνοχή τους και να αποφεύγεται υπερεκπροσώπηση μίας μόνο περιοχής. Εντός κάθε συστάδας ταξινομούμε τα έγγραφα με το κατάλληλο fusion score (CombSUM/CombMNZ/RRF). Μια πρακτική μορφή είναι [ \mathrm{final}(d)=\alpha\, S(C(d))+(1-\alpha)\,\mathrm{score}_{\text{fusion}}(d), ] με πιθανή ποινή για διπλότυπα/σχεδόν διπλότυπα έγγραφα ή για πολλά έγγραφα από την ίδια συστάδα, ώστε να βελτιωθεί και η ποικιλομορφία.
Θέμα 3¶
Αξιοπιστία: δύο ανεξάρτητες λύσεις συμφωνούν · εμπιστοσύνη λύτη: μέτρια
Η ανάθεση document identifiers είναι μια συνάρτηση που απεικονίζει κάθε κείμενο (τίτλο/URL) σε έναν μονοσήμαντο ακέραιο, π.χ. \(\mathrm{ID}:\text{document}\to\mathbb{N}\). Στο ανεστραμμένο αρχείο, κάθε λίστα μετεμφανίσεων ενός όρου αποθηκεύεται συνήθως ταξινομημένη ως προς αυτούς τους ακέραιους. Έτσι, για ερώτημα τομής δύο όρων \(t_1\) και \(t_2\), θέλουμε να βρούμε τα κοινά IDs στις δύο ταξινομημένες λίστες \(L(t_1)\) και \(L(t_2)\). Η τομή μπορεί να υπολογιστεί αποδοτικά με συγχώνευση δύο ταξινομημένων ακολουθιών με δύο δείκτες, ή με skip pointers/binary search, σε χρόνο ανάλογο του μήκους των λιστών (ή καλύτερα με άλματα).
Η ανάθεση IDs είναι κρίσιμη γιατί καθορίζει τη διάταξη των postings και άρα την δυνατότητα ταξινομημένης τομής. Πρέπει να είναι σταθερή και συνεπής, ώστε οι λίστες να μπορούν να αποθηκευτούν αύξουσες. Επιπλέον, μια «καλή» ανάθεση μπορεί να βελτιώσει την απόδοση: - πυκνά/διαδοχικά IDs ή IDs με μικρές διαφορές βοηθούν στη συμπίεση των αποστάσεων (delta encoding), στη χρήση bitmaps και skip lists· - αν κείμενα που σχετίζονται (π.χ. ίδιο URL-prefix ή ίδια συστάδα) πάρουν γειτονικά IDs, οι λίστες τείνουν να έχουν τοπικότητα και καλύτερη συμπεριφορά cache· - αντίθετα, τυχαία ή πολύ αραιά IDs αυξάνουν τα κενά και μπορούν να κάνουν την κωδικοποίηση και την ανάγνωση/τομή λιγότερο αποδοτικές.
Επομένως, η ανάθεση IDs δεν αλλάζει απλώς την ονοματοδοσία· επηρεάζει άμεσα την αναπαράσταση και την ταχύτητα εκτέλεσης πράξεων τομής στο ανεστραμμένο αρχείο, επειδή οι αλγόριθμοι τομής βασίζονται στην ταξινομημένη σειρά των IDs και επωφελούνται από συμπαγείς, τοπικές και συμπιέσιμες αριθμήσεις.