Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 1)¶
themata1.pdf¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΣ 2021 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30
(ΟΜΑΔΑ 1)
ΘΕΜΑ 1 ( Μονάδες 3,5 )
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 30, σχεδιάστε τα γραφήματα ανάκλησης ακρίβειας, για τα ακόλουθα ερωτήματα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα) :
- Μηχανή1 Αριθμός: 10, Θέση: 2, 3, 7, 9, 10, 13, 17, 20, 27, 29
- Μηχανή2 Αριθμός: 10, Θέση: 1, 2, 4, 8, 11, 12, 15, 16, 28, 30
Με βάση τα δύο προκύπτοντα γραφήματα ανάκλησης ακρίβειας συγκρίνετε μεταξύ τους τις δύο μηχανές.
Στη συνέχεια συγκρίνετε τις δύο μηχανές με χρήση των μετρικών P@5, MRR (Mean Reciprocal Rank – Μέσος Όρος Ανάστροφος Βαθμός) και MAP (Mean Average Precision – Μέσος Όρος Μέσης Ακρίβειας).
β. . Εξηγήστε πως μία δομή ανεστραμμένων αρχείων θα μπορούσε να χρησιμοποιηθεί για να χειριστεί κείμενα τα οποία δεν είναι χωρισμένα σε λέξεις αλλά ακολουθία χαρακτήρων όπου κάθε δυνατό πρότυπο που είναι υποσυμβολοσειρά της ακολουθίας μπορεί να αποτελέσει αντικείμενο ερώτησης. Τέτοια κατηγορία κειμένων είναι τα κείμενα των CJK γλωσσών (Chinese, Japanese, Korean).
ΘΕΜΑ 2 ( Μονάδες 3,5)¶
α.Σύμφωνα με την cluster hypothesis ( υπόθεση ομαδοποίησης ), κείμενα που ανήκουν στην ίδια συστάδα ομαδοποίησης είναι και σχετικά για παρόμοιες αιτήσεις. Μία ερμηνεία αυτής της υπόθεσης είναι ότι κείμενα που είναι σχετικά ψηλά στην αξιολόγηση σε ένα ερώτημα πρέπει να παρασύρουν και κείμενα της ίδιας ομάδας, ώστε να είναι αντίστοιχα ψηλά. Εξηγήστε πως το μοντέλο διανυσματικού χώρου θα μπορούσε να τροποποιηθεί ώστε να ενσωματώσει την πληροφορία αυτή. β. Θεωρήστε ότι έχουμε μία συλλογή κειμένων και όρων που περιγράφεται από τον ακόλουθο πίνακα:
| όρος1 | όρος2 | όρος3 | όρος4 | όρος5 | |
|---|---|---|---|---|---|
| Κειμ1 | 0 | 1 | 2 | 2 | 0 |
| Κειμ2 | 0 | 1 | 2 | 0 | 1 |
| Κειμ3 | 0 | 1 | 0 | 1 | 0 |
| Κειμ4 | 1 | 0 | 2 | 0 | 0 |
| Κειμ5 | 0 | 2 | 1 | 0 | 0 |
| Κειμ6 | 2 | 2 | 0 | 1 | 0 |
| Κειμ7 | 3 | 1 | 0 | 2 | 1 |
| Κειμ8 | 0 | 2 | 0 | 4 | 0 |
Αναπαραστήστε τη συγκεκριμένη συλλογή χρησιμοποιώντας το μοντέλο διανυσματικού χώρου, και αποθηκεύστε αυτή σε ένα ανεστραμμένο αρχείο. Εξηγήστε πως με χρήση του ανεστραμμένου αρχείου, το μοντέλο διανυσματικού χώρου θα απαντήσει το ερώτημα Q={όρος1, όρος2, όρος4}.
ΘΕΜΑ 3 ( Μονάδες 3)¶
Στο πρόβλημα του Document Identifier Assignment (ανάθεση αναγνωριστικών σε κείμενα) θέλουμε να απεικονίσουμε τίτλους (ή url) κειμένων ΣΕ ακέραιους αριθμούς, ώστε να υλοποιηθούν οι ανεστραμμένες λίστες του ανεστραμμένου αρχείου της συλλογής. Δηλαδή σε κάθε ανεστραμμένη λίστα μίας λέξης θα αναγράφονται ακέραιοι αριθμοί που θα αντιστοιχούν στα κείμενα στα οποία η λέξη εμφανίζεται.
Εξηγήστε την σχέση που έχει η ανάθεση αυτή με την αποδοτική ΣΥΜΠΙΕΣΗ του αντίστοιχου ανεστραμμένου αρχείου και προτείνετε τεχνικές αποτελεσματικής απεικόνισης ώστε η συμπίεση που προκύπτει να είναι αποδοτική.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-02-a.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):Anaktisi_Themata_Feb21.rar,exams_2021.zip,exams_2021/Çñßí½₧⌐₧ ö£Ö exams 2021/themata1.pdf
Λύσεις (⚪ AI, μη επαληθευμένο)
Κατάσταση: ⚪ AI, μη επαληθευμένο Πηγή: λύσεις AI (deepseek-flash), ανεξάρτητη επανάληψη και αντιπαραβολή· καμία δεν έχει ελεγχθεί από άνθρωπο
Προσοχή
Λύση από AI — ελέγξτε την· δεν έχει επαληθευτεί από άνθρωπο. Η ένδειξη «δύο λύσεις συμφωνούν» δεν σημαίνει ότι η απάντηση είναι σωστή.
AI λύσεις — 2021-02-a¶
Οι λύσεις γράφτηκαν από μοντέλα AI και δεν έχουν ελεγχθεί από άνθρωπο. Η αρίθμηση ακολουθεί το αρχείο θεμάτων.
Θέμα 1¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Έστω ότι για κάθε μηχανή υπάρχουν \(R=10\) σχετικά έγγραφα και επιστρέφονται συνολικά \(30\) έγγραφα. Σε θέση \(k\) με \(r_k\) σχετικά έως εκείνη τη θέση: [ \text{Recall}=\frac{r_k}{10},\qquad \text{Precision}=\frac{r_k}{k}. ] Τα σημεία των καμπυλών precision-recall είναι:
| Recall | Precision Μηχανής 1 | Precision Μηχανής 2 |
|---|---|---|
| 0.1 | \(1/2=0.500\) | \(1/1=1.000\) |
| 0.2 | \(2/3\approx0.667\) | \(2/2=1.000\) |
| 0.3 | \(3/7\approx0.429\) | \(3/4=0.750\) |
| 0.4 | \(4/9\approx0.444\) | \(4/8=0.500\) |
| 0.5 | \(5/10=0.500\) | \(5/11\approx0.455\) |
| 0.6 | \(6/13\approx0.462\) | \(6/12=0.500\) |
| 0.7 | \(7/17\approx0.412\) | \(7/15\approx0.467\) |
| 0.8 | \(8/20=0.400\) | \(8/16=0.500\) |
| 0.9 | \(9/27\approx0.333\) | \(9/28\approx0.321\) |
| 1.0 | \(10/29\approx0.345\) | \(10/30\approx0.333\) |
Για τη Μηχανή 1, μετά το τελευταίο σχετικό στη θέση 29 και την επιστροφή του 30ού μη σχετικού, στο recall \(=1\) η precision πέφτει σε \(10/30=0.333\).
Σύγκριση: η Μηχανή 2 υπερέχει στα πρωταρχικά αποτελέσματα (πρώτο σχετικό στη θέση 1 έναντι 2) και γενικά βρίσκεται ψηλότερα στην καμπύλη στα χαμηλά/μεσαία επίπεδα ανάκλησης. Η Μηχανή 1 έχει οριακά καλύτερη precision σε μεμονωμένα σημεία, π.χ. στο recall \(0.5\) και στο recall \(0.9\), αλλά συνολικά η Μηχανή 2 είναι καλύτερη.
Υπολογισμός μετρικών: [ P@5_1=\frac{2}{5}=0.4,\qquad P@5_2=\frac{3}{5}=0.6. ] [ RR_1=\frac{1}{2}=0.5,\qquad RR_2=\frac{1}{1}=1. ] Επειδή έχουμε ένα ερώτημα, \(MRR=RR\) για κάθε μηχανή.
[ \begin{aligned} AP_1&=\frac{1}{10}\left(\frac12+\frac23+\frac37+\frac49+\frac5{10} +\frac6{13}+\frac7{17}+\frac8{20}+\frac9{27}+\frac{10}{29}\right)\ &\approx 0.4491. \end{aligned} ] [ \begin{aligned} AP_2&=\frac{1}{10}\left(1+1+\frac34+\frac48+\frac5{11} +\frac6{12}+\frac7{15}+\frac8{16}+\frac9{28}+\frac{10}{30}\right)\ &\approx 0.5826. \end{aligned} ] Άρα, αφού υπάρχει ένα ερώτημα, \(MAP_1\approx0.4491\) και \(MAP_2\approx0.5826\). Η Μηχανή 2 υπερέχει σε \(P@5\), \(MRR\) και \(MAP\).
β. Όταν τα κείμενα δεν είναι χωρισμένα σε λέξεις, όπως σε CJK γλώσσες, μπορούμε να χρησιμοποιήσουμε ανεστραμμένο αρχείο χαρακτήρων ή \(n\)-γραμμάτων (character \(n\)-grams). Κάθε όρος του ευρετηρίου είναι υποσυμβολοσειρά μήκους \(n\), π.χ. bigram/trigram χαρακτήρων, και κάθε καταχώριση περιέχει τα έγγραφα και τη θέση εμφάνισης. Για ερώτημα που είναι αυθαίρετη υποσυμβολοσειρά, διασπούμε το πρότυπο σε επικαλυπτόμενα \(n\)-grams, ανακτούμε τις αντίστοιχες λίστες, τις συναρμόζουμε με βάση τη θέση και επαληθεύουμε ότι τα \(n\)-grams εμφανίζονται συνεχόμενα. Αν θέλουμε άμεση αναζήτηση οποιουδήποτε υποσυμβολοσειράς χωρίς επαλήθευση, μπορεί να χρησιμοποιηθεί ευρετήριο όλων των υποσυμβολοσειρών ή δομή suffix array/suffix tree· το κόστος χώρου είναι μεγαλύτερο, γι’ αυτό συνήθως προτιμώνται positional \(n\)-gram ευρετήρια.
Θέμα 2¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
α. Στο μοντέλο διανυσματικού χώρου η αρχική ομοιότητα είναι συνήθως [ s_0(d,q)=\cos(d,q). ] Για να ενσωματώσουμε την υπόθεση ομαδοποίησης, μπορούμε να επαυξήσουμε το διάνυσμα κάθε εγγράφου με πληροφορία από το κέντρο της συστάδας του. Έστω \(C(d)\) η συστάδα του \(d\) και \(c_{C(d)}\) το centroid της. Ορίζουμε [ \tilde d=d+\lambda\,c_{C(d)},\qquad \lambda\ge0, ] και ταξινομούμε με [ s(d,q)=\cos(\tilde d,q). ] Ισοδύναμα, μπορούμε να προσθέτουμε στο score ενός εγγράφου την ομοιότητα του ερωτήματος με το centroid της συστάδας του: [ s(d,q)=(1-\lambda)\cos(d,q)+\lambda\cos(c_{C(d)},q). ] Έτσι, αν ένα έγγραφο μιας συστάδας είναι σχετικό, ευνοούνται και τα υπόλοιπα έγγραφα της ίδιας συστάδας, υλοποιώντας την ιδέα ότι έγγραφα της ίδιας συστάδας «παρασύρονται» προς τα πάνω.
β. Χρησιμοποιώ κλασικά tf-idf βάρη [ w_{t,d}=(1+\log_2 tf_{t,d})\log_2\frac{N}{df_t} ] για \(tf_{t,d}>0\), αλλιώς \(0\), με \(N=8\). Οι συχνότητες εγγράφων είναι: [ df_1=3,\quad df_2=7,\quad df_3=4,\quad df_4=5,\quad df_5=2. ] Άρα [ idf_1\approx1.415,\quad idf_2\approx0.193,\quad idf_3=1,\quad idf_4\approx0.678,\quad idf_5=2. ] Η μήτρα βαρών του VSM είναι κατά προσέγγιση:
| τ1 | τ2 | τ3 | τ4 | τ5 | |
|---|---|---|---|---|---|
| D1 | 0 | 0.193 | 2.000 | 1.356 | 0 |
| D2 | 0 | 0.193 | 2.000 | 0 | 2.000 |
| D3 | 0 | 0.193 | 0 | 0.678 | 0 |
| D4 | 1.415 | 0 | 2.000 | 0 | 0 |
| D5 | 0 | 0.385 | 1.000 | 0 | 0 |
| D6 | 2.830 | 0.385 | 0 | 0.678 | 0 |
| D7 | 3.658 | 0.193 | 0 | 1.356 | 2.000 |
| D8 | 0 | 0.385 | 0 | 2.034 | 0 |
Αντίστοιχο ανεστραμμένο αρχείο, με καταχωρίσεις \((D_i,tf,w)\): [ \begin{aligned} \tau_1 &: (D4,1,1.415),(D6,2,2.830),(D7,3,3.658),\ \tau_2 &: (D1,1,0.193),(D2,1,0.193),(D3,1,0.193),(D5,2,0.385),\ &\quad (D6,2,0.385),(D7,1,0.193),(D8,2,0.385),\ \tau_3 &: (D1,2,2.000),(D2,2,2.000),(D4,2,2.000),(D5,1,1.000),\ \tau_4 &: (D1,2,1.356),(D3,1,0.678),(D6,1,0.678),(D7,2,1.356),(D8,4,2.034),\ \tau_5 &: (D2,1,2.000),(D7,1,2.000). \end{aligned} ]
Για \(Q=\{\text{όρος1},\text{όρος2},\text{όρος4}\}\) και \(tf=1\) για κάθε όρο, το διάνυσμα ερωτήματος είναι [ q=(idf_1,idf_2,0,idf_4,0)\approx(1.415,0.193,0,0.678,0), ] με [ |q|=\sqrt{1.415^2+0.193^2+0.678^2}\approx1.581. ] Ανακτούμε μόνο τις λίστες των \(\tau_1,\tau_2,\tau_4\), υπολογίζουμε για κάθε υποψήφιο έγγραφο το εσωτερικό γινόμενο \(d\cdot q\) και κανονικοποιούμε με \(\|d\|\|q\|\). Προκύπτει:
| Έγγραφο | \(d\cdot q\) | \(\|d\|\) | \(\cos(d,q)\) |
|---|---|---|---|
| D1 | 0.957 | 2.424 | 0.250 |
| D2 | 0.037 | 2.835 | 0.008 |
| D3 | 0.497 | 0.705 | 0.446 |
| D4 | 2.002 | 2.450 | 0.517 |
| D5 | 0.074 | 1.072 | 0.044 |
| D6 | 4.539 | 2.936 | 0.978 |
| D7 | 6.133 | 4.388 | 0.884 |
| D8 | 1.454 | 2.070 | 0.444 |
Άρα η κατάταξη είναι: [ D6 > D7 > D4 > D3 > D8 > D1 > D5 > D2. ]
Θέμα 3¶
Αξιοπιστία: μία λύση AI, δεν έχει αντιπαραβληθεί με δεύτερη · εμπιστοσύνη λύτη: υψηλή
Οι ανεστραμμένες λίστες αποθηκεύουν συνήθως τα docIDs ταξινομημένα. Η συμπίεση γίνεται με κωδικοποίηση διαφορών/gaps: [ d_1,\ d_2-d_1,\ d_3-d_2,\ldots ] και στη συνέχεια με κώδικες μεταβλητού μήκους, π.χ. variable-byte, γκρίζο/δυαδικό ή Golomb/Rice/Elias-Fano. Το μέγεθος της συμπιεσμένης λίστας εξαρτάται άμεσα από το μέγεθος αυτών των διαφορών. Αν τα σχετικά ή παρόμοια έγγραφα πάρουν γειτονικά αναγνωριστικά, τότε για τους όρους που μοιράζονται οι λίστες περιέχουν μικρά gaps, άρα κωδικοποιούνται με λιγότερα bits. Αντίθετα, μια τυχαία ανάθεση docIDs παράγει μεγάλα και λιγότερο προβλέψιμα gaps και χειροτερεύει τη συμπίεση.
Τεχνικές αποδοτικής απεικόνισης εγγράφων σε ακεραίους: - Ανάθεση συνεχόμενων IDs σε έγγραφα που ανήκουν στην ίδια συστάδα ή είναι όμοια ως προς το διάνυσμα όρων (clustering, minhash/LSH, spectral clustering), και διάταξη των συστάδων ώστε τα κοινά terms να εμφανίζονται σε γειτονικά IDs. - Ταξινόμηση κατά URL/domain/host ή κατά προέλευση, ώστε σε συλλογές web να υπάρχει τοπικότητα και κοινό λεξιλόγιο γειτονικών εγγράφων. - Χρήση τεχνικών graph partitioning / minimum linear arrangement ή ευρετικών (π.χ. nearest-neighbor ordering, simulated annealing) με στόχο την ελαχιστοποίηση του συνολικού μήκους των gaps στις λίστες όρων. - Χρήση πυκνής αρίθμησης από \(1\) έως \(N\) χωρίς μεγάλα κενά· τα κενά και τα άσκοπα μεγάλα IDs αυξάνουν τα deltas. - Συνδυασμός της ανάθεσης με κατάλληλο gap encoding και συμπίεση με variable-byte/Golomb/Elias-Fano· η ανάθεση βελτιστοποιεί τα δεδομένα πριν την κωδικοποίηση, δεν αντικαθιστά τον κώδικα συμπίεσης.
Με αυτόν τον τρόπο η ανάθεση docIDs δεν είναι απλή τεχνική λεπτομέρεια: επηρεάζει πόσο μικρά είναι τα gaps στις ανεστραμμένες λίστες και επομένως πόσο αποδοτικά συμπιέζεται ολόκληρο το ανεστραμμένο αρχείο.