Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 7)¶
themata7.pdf¶
ΤΜΗΜΑ ΜΗΧΑΝΙΚΩΝ Η/Υ ΚΑΙ ΠΛΗΡΟΦΟΡΙΚΗΣ ΠΑΝΕΠΙΣΤΗΜΙΟ ΠΑΤΡΑΣ ΑΝΑΚΤΗΣΗ ΠΛΗΡΟΦΟΡΙΑΣ ΕΞΕΤΑΣΕΙΣ ΦΕΒΡΟΥΑΡΙΟΥ 2021 Διδάσκων: [όνομα παραλείπεται] ΔΙΑΡΚΕΙΑ 1:30 (ΟΜΑΔΑ 7)
ΘΕΜΑ 1 ( Μονάδες 3.5 )¶
α. Λόγω του μεγάλου όγκου δεδομένων που έχουν να χειριστούν οι μηχανές ψαξίματος στον παγκόσμιο ιστό, συχνά διατηρούν δύο ανεστραμμένα αρχεία, ένα που περιέχει πληροφορία για όλα τα κείμενα και αποθηκεύεται στο δίσκο και ένα μικρότερου μεγέθους που περιέχει ένα υποσύνολο της συνολικής πληροφορίας και αποθηκεύεται στην κύρια μνήμη. Τα δύο αυτά ανεστραμμένα αρχεία λειτουργούν με τη λογική ότι σε δοθέν ερώτημα, πρώτα θα ερωτηθεί η δομή στην κύρια μνήμη και αν η απάντηση δεν είναι ικανοποιητική θα ερωτηθεί και η δομή στον δίσκο. Προτείνετε πολιτικές δημιουργίας και ενημέρωσης της δομής ανεστραμμένων αρχείων της κύριας μνήμης, υποθέτοντας ότι η μηχανή ακολουθεί ένα συνδυασμό μοντέλου διανυσματικού χώρου, και μίας link μετρικής (ανεξάρτητης περιεχομένου), στη βαθμολόγηση των ιστοσελίδων.
β. Καταγράψτε τους βασικούς αλγορίθμους συμπίεσης ανεστραμμένων αρχείων, και συγκρίνετέ τους μεταξύ τους.
ΘΕΜΑ 2 ( Μονάδες 3.5 )¶
α. Θεωρώντας ότι ο αριθμός των επιστρεφόμενων κειμένων είναι 30, θεωρήστε τις ακόλουθες δύο μηχανές που απαντάνε στο ίδιο ερώτημα (δίνονται ο αριθμός των σχετικών κειμένων και η θέση τους στο αποτέλεσμα) :
Μηχανή1 Αριθμός: 10, Θέση: 1, 2, 5, 8, 11, 18, 22, 27, 28, 30 Μηχανή2 Αριθμός: 10, Θέση: 1, 2, 3, 7, 10, 19, 22, 25, 27, 30.
Θεωρήστε ότι οι εμπειρογνώμονες εκτός από το αν ένα κείμενο είναι σχετικό ή όχι δίνουν και βαρύτητα σχετικότητας : 1 (αρκετά σχετικό), και 2 (πολύ σχετικό), και υποθέστε ότι στις δύο ανωτέρω μηχανές συμβαίνει κατά την ανάκτηση τα πέντε πρώτα σχετικά κείμενα να έχουν βαρύτητα σχετικότητας 2, και τα επόμενα έχουν βαρύτητα σχετικότητας 1.
ΣΥΓΚΡΙΝΕΤΕ ΤΙΣ ΔΥΟ ΜΗΧΑΝΕΣ χρησιμοποιώντας τη μετρική NDCG (ξεκινήστε να υπολογίζετε τον τύπο, και φθάστε το μέχρι το σημείο που μπορεί να γίνει η σύγκριση).
β. Εξηγήστε πως ο αλγόριθμος βαθμολόγησης σελίδων Pagerank του Google και HITS του CLEVER μπορεί να επεκταθεί έτσι ώστε να ενσωματώνει πληροφορίες σχετικά με τη δεδομένα κίνησης πληροφορίας στο διαδίκτυο και προσπελασιμότητας των ιστοσελίδων από τους χρήστες.
ΘΕΜΑ 3 ( Μονάδες 3)¶
Υποθέστε ότι το γράφημα του Web είναι αποθηκευμένο στον δίσκο ενός υπολογιστικού συστήματος, με τη μορφή adjacency lists (λίστες γειτνιάσεων) που είναι βασικά λίστες που περιέχουν για κάθε κορυφή v του γραφήματος τη λίστα των άμεσα προσβάσιμων κορυφών από τον κόμβο v . Με τον τρόπο αυτό μπορούμε να
ρωτήσουμε για τους γείτονες που έχει ένας συγκεκριμένος κόμβος και να τους προσπελάσουμε σαν μία λίστα ΑΜΕΣΑ από τον δίσκο.
α. Περιγράψτε τα βασικά βήματα του αλγορίθμου που υπολογίζει το PageRank στο σενάριο αυτό.
β. Υποθέστε ότι σε κάθε σελίδα απεικονίζουμε ένα ακέραιο αριθμό από 1 έως Ν ( Ν το πλήθος των σελίδων). Πως μπορεί να συμπιεστεί η αναπαράστασή μας του γραφήματος στο σχήμα αυτό;
γ. Εξηγήστε γιατί η λεξικογραφική διάταξη των αλφαριθμητικών των URLs των σελίδων και η ανάθεση αυξόντων αριθμών σε αυτές οδηγεί σε καλή συμπίεση του γραφήματος.
Επιπλέον πηγές χωρίς μεταγραφή εδώ (λύσεις →
2021-02-g.solutions.md, ή διπλότυπες φωτογραφίες της ίδιας σελίδας):137380356_2841797582757362_4165966939869312338_n.jpg,139702724_744245149825695_1380149947151384089_n.jpg
Λύσεις (🟡 community)
Κατάσταση: 🟡 community Πηγή: χειρόγραφες λύσεις φοιτητή σε φωτογραφίες (πηγή δεν ορίζεται)
Προσοχή
Η λύση HITS και PageRank (137380356) απαντά στη βασική λειτουργία των αλγορίθμων· το ΘΕΜΑ 2 β της Ομάδας 7 ζητά την επέκτασή τους με δεδομένα κίνησης και προσπελασιμότητας, άρα δεν είναι η ίδια ερώτηση. Η λύση 137380356 ξεκινά από την απάντηση χωρίς το ερώτημα και παραπέμπει σε σχήμα και τύπο σελίδων (51 και 55) που δεν μεταγράφονται. Η λύση 139702724 απαντά σε ερωτήσεις για stemming, ανάδραση συνάφειας, crawler και BM25· αυτές δεν υπάρχουν στο ΘΕΜΑ 3 της Ομάδας 7, και η ερώτηση BM25 μένει χωρίς απάντηση.
Λύσεις — Ανάκτηση Πληροφορίας — Φεβρουάριος 2021 (Ομάδα 7)¶
Λύσεις που δεν είναι βέβαιο ότι αντιστοιχούν στην Ομάδα 7· τα ερωτήματα των φωτογραφιών σημειώνονται στα warnings.
137380356_2841797582757362_4165966939869312338_n.jpg¶
Απάντηση: Ο αλγόριθμος HITS δημιουργεί ένα αρχικό σύνολο \(R_\sigma\), το οποίο περιέχει τις πρώτες t σελίδες που δίνει σαν αποτέλεσμα μία term based μηχανή αναζήτησης, όπως για παράδειγμα η AltaVista δίνοντας της σαν είσοδο τον όρο σ. Αυτό το σύνολο είναι εμφανές ότι ικανοποιεί την απαίτηση το σύνολο των σελίδων \(S_\sigma\) να είναι σχετικά μικρό καθώς το μέγεθος του μπορεί εύκολο να καθοριστεί από την παράμετρο t. Επίσης, είναι και πλούσιο σε σχετικές με το θέμα σελίδες καθώς το \(R_\sigma\) είναι ένα υποσύνολο του \(Q_\sigma\) που είναι η συλλογή όλων των σελίδων που περιέχουν τον όρο σ. Η τεχνική βαθμολόγησης του HITS γίνεται με την χρήση σελίδων hubs και authorities (να σχεδιαστεί το σχήμα 2 σελίδας 51) που υποδηλώνουν ένα είδος σχέσης αμοιβαίας ενίσχυσης, καθώς ένα καλό hub είναι μια σελίδα που δείχνει σε πολλά authorities και ένα καλό authority είναι μια σελίδα που δείχνει σε πολλά hubs. Η μηχανή αναζήτησης Google χρησιμοποιεί την μέθοδο βαθμολόγησης pagerank «να περιγραφεί ο τύπος του πλαισίου της σελίδας 55». Μπορεί να θεωρηθεί ως ένα μοντέλο της συμπεριφοράς των χρηστών. Θεωρείται ότι υπάρχει ένας τυχαίος χρήστης που κινείται μέσα στον παγκόσμιο ιστό, ο οποίος ξεκινά από μια τυχαία σελίδα που του δίνεται και συνεχίζει επιλέγοντας διασυνδέσεις, χωρίς όμως ποτέ να επιστρέψει σε προηγούμενη σελίδα. Η πιθανότητα να επισκεφτεί μια σελίδα ο χρήστης αυτός είναι το pagerank της σελίδας αυτής και ο παράγοντας απόσβεσης d είναι η πιθανότητα ο χρήστης να βαρεθεί την σελίδα που βρίσκεται και να ζητήσει μια άλλη τυχαία. Ένας top focused crawler αποτελεί ένα web crawler που συλλέγει ιστοσελίδες που ικανοποιούν μια συγκεκριμένη ιδιότητα, με την προσεκτική ιεράρχηση των συνόρων ανίχνευσης και την διαχείριση της διαδικασίας υπερσύνδεσης. Οι αλγόριθμοι HITS και page rank θα μπορούσαν να χρησιμοποιηθούν για την δημιουργία ενός τέτοιου crawler γιατί δίνουν έμφαση σε συγκεκριμένα χαρακτηριστικά που χρειάζονται οι χρήστες.
Σημείωση: η φωτογραφία ξεκινά από την απάντηση χωρίς το ερώτημά της (το ερώτημα βρίσκεται σε προηγούμενη σελίδα).
ΘΕΜΑ 3 – Α
Ερώτηση: Η διαδικασία του stemming (στελεχοποίησης) βελτιώνει ανάκληση, ακρίβεια ή και τα δύο;
Απάντηση: Η διαδικασία του stemming (στελεχοποίησης ή απομάκρυνσης καταλήξεων) μπορεί να χρησιμοποιηθεί για να κρατήσει μόνο τη ρίζα ορισμένων λέξεων με κοινή ρίζα και να απομακρύνει τις διαφορετικές καταλήξεις τους, π.χ. η λέξη connect ομαδοποιεί τις λέξεις: connecting, connection, connections. Με τον τρόπο αυτό κατασκευάζονται όροι ευρετηρίου (σε συνδυασμό βέβαια και με άλλες τεχνικές όπως είναι η απομάκρυνση των stopwords ενός κειμένου) και έτσι αναπαριστώνται τα πλήρη κείμενα με όρους δεικτοδότησης. Αναφορικά με την ανάκτηση πληροφορίας, η χρήση του stemming βελτιώνει την ακρίβεια (precision) διότι αυξάνει τον αριθμό των σχετικών ανακτημένων εγγράφων.
Ερώτηση: Η ανάδραση συνάφειας (relevance feedback) βελτιώνει ανάκληση, ακρίβεια ή και τα δύο;
Απάντηση: Η τροποποίηση της διαδικασίας αναζήτησης για τη βελτίωση της αποτελεσματικότητας ενός συστήματος IR
• Περιλαμβάνει πληροφορίες που προκύπτουν από προηγούμενες κρίσιμες ενδείξεις
139702724_744245149825695_1380149947151384089_n.jpg¶
• Βασική ιδέα είναι να κάνουμε ένα αρχικό ερώτημα, να λάβουμε ανατροφοδότηση από το χρήστη (ή αυτόματα) σχετικά με τα σχετικά έγγραφα και στη συνέχεια να προσθέσουμε όρο από γνωστά σχετικά έγγραφα στα ερωτήματα.
Η ανατροφοδότηση (ανάδραση) σχετικότητας βελτιώνει συνήθως τη μέση ακρίβεια αυξάνοντας τον αριθμό των καλών όρων στο ερώτημα (γενικά 10-15% βελτίωση στην παραδοσιακή αναζήτηση IR)
Ερώτηση: Εξηγήστε τον τρόπο λειτουργίας του Crawler;
Απάντηση:
spider ή robot. Ο crawler αρχικά κοιτάει ένα προς ένα τα URL που βρίσκονται στο Διαδίκτυο (Internet) και συλλέγει λέξεις και φράσεις για κάθε ένα από αυτά. Στην συνέχεια τα αποθηκεύει στην βάση δεδομένων που χρησιμοποιείται για να δίνει ζωή στην μηχανή αναζήτησης (Search Engine) (σύμφωνα με [25]).
Ένας Web Crawler είναι ένα είδος πράκτορα λογισμικού. Γενικά, ξεκινάει από μια λίστα με URLs τα οποία επισκέπτεται. Καθώς επισκέπτεται αυτα τα URLs προσδιορίζει όλους τους συνδέσμους υπερ-κειμένου (hyperlinks) που βρίσκει στην κάθε σελίδα και στην συνέχεια προσθέτει αυτούς τους συνδέσμους στην λιστα με τα URLs που πρέπει να επισκεπτεί. Όλη αυτή την λίστα με τα URLs την επισκέπτεται επαναληπτικά σύμφωνα με ένα σύνολο πολιτικών. Υπάρχουν σημαντικά χαρακτηριστικά του World Wide Web τα οποία κάνουν το crawling πολύ δύσκολο, όπως είναι το μεγάλο του μέγεθος, ο γρήγορος ρυθμος των αλλαγών που συντελούνται και η δυναμική δημιουργία σελίδων.
Γενικά, η συμπεριφορά του Web Crawler είναι η έκβαση από έναν συνδυασμό πολιτικών.
Α) Πολιτική Επιλογής, η οποία δηλώνει ποιές σελίδες να κατεβούν
Β) Πολιτική Νέας Επίσκεψης, η οποία δηλώνει πότε να ελεγχθούν για αλλαγές οι σελίδες
Γ) Πολιτική Ευγενείας, η οποία δηλώνει πως να αποφευχθεί η υπερφορτωση ιστοσελίδων
Δ) Πολιτική Παραλληλισμού, η οποία δηλώνει τον τρόπο συντονισμού των κατανεμημένων Web Crawlers
Ερώτηση: Περιγράψτε τις βασικές ιδέες πίσω από τη μετρική ομοιότητας BM25;
[κάτω μέρος σελίδας: 8]