Τμήμα Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών


Πανεπιστήμιο Θεσσαλίας (Βόλος)

Διδάσκων

Δημήτριος Κατσαρός

Ανάκληση Πληροφορίας (Information Retrieval)

Περίληψη

  1. Το μάθημα θα διαπραγματευτεί:
    Ανάκτηση Πληροφορίας στον σύγχρονο Παγκόσμιο Ιστό, δηλαδή θα πραγματευτεί την Επιστήμη και Τεχνολογία των Μηχανών Αναζήτησης
  2. Λέξεις-κλειδιά του μαθήματος:
    • Boolean model, dictionary and postings lists, tolerant retrieval, index construction, index compression
      scoring and term weighting, vector space retrieval, recall and precision measures
    • Web crawling and indexes, link analysis ranking, summation formula for PageRank, problems with the iterative process
    • spectrum of the Google matrix, parameters in the PageRank model, sensitivity of PageRank
    • the PageRank problem as a linear system, proof of the PageRank as a sparse linear system
    • large-scale implementation of PageRank, back button modeling, adaptive power method, extrapolation, aggregation, updating the PageRank vector
    • HITS method for ranking Webpages, HITS implementation, HITS convergence, HITS's relationship to bibliometrics, query-independent HITS, HITS sensitivity
    • SALSA, BrowseRank
    • content spam, link spam, spam farms, Search Engine Optimization (SEO)

Κύρια βιβλιογραφία

Βιβλίο
Τίτλος Η Μέθοδος PageRank της Google και άλλα Συστήματα Κατάταξης
Google's PageRank and Beyond: The Science of Search Engine Rankings
Τοπικό αντίγραφο εδώ 		Introduction to Information Retrieval
Εισαγωγή στην Aνάκτηση Πληροφοριών
Δωρεάν εδώ
Τοπικό αντίγραφο εδώ 		Ιnformation Retrieval: Implementing and Evaluating Search Engines
Τοπικό αντίγραφο εδώ 		Search Engines: Information Retrieval in Practice
Δωρεάν εδώ
Τοπικό αντίγραφο εδώ
Συγγραφείς Amy N. Langville and Carl D. Meyer Christopher D. Manning, Prabhakar Raghavan and Hinrich Schutze Stefan Buttcher, Charles L. A. Clarke and Gordon V. Cormack Bruce Croft, Donald Metzler and Trevor Strohman
Έκδοση Πρώτη Ελληνική 2010 (Πρώτη Αγγλική 2006)
Πανεπιστημιακές Εκδόσεις Κρήτης (Princeton University Press) 		Πρώτη Αγγλική 2008 (Πρώτη Ελληνική 2012)
Cambridge University Press (Κλειδάριθμος) 		Πρώτη Αγγλική 2010
The MIT Press 		Πρώτη Αγγλική 2009
Addison Wesley

Συμπληρωματική βιβλιογραφία

Βιβλίο
Τίτλος Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining Modern Information Retrieval - Τhe Concepts and Technology Behind Search
Ανάκτηση Πληροφορίας 		Understanding Search Engines: Mathematical Modeling and Text Retrieval Managing Gigabytes: Compressing and Indexing Documents and Images
Συγγραφείς ChengXiang Zhai and Sean Massung Ricardo Baeza-Yates and Berthier Ribeiro-Neto Michael W. Berry and Murray Browne Ian H. Witten, Alistair Moffat and Timothy C. Bell
Έκδοση Πρώτη Αγγλική 2016
ACM and Morgan & Claypool 		Δεύτερη Αγγλική 2011 (Πρώτη Ελληνική 2014)
Addison Wesley (Εκδόσεις Τζιόλα) 		Δεύτερη Αγγλική 2005
SIAM 		Δεύτερη Αγγλική 1999
Morgan Kaufmann

Χρήσιμα άρθρα

  1. A. Moffat, J. Zobel, D. Hawking, Recommended reading for IR research students, ACM SIGIR Forum, vol. 39, no. 2, pp. 3-14, 2005.
  2. D. Blank, N. Fuhr, A. Henrich, T. Mandl, T. Roelleke, H. Schόtze, B. Stein, Teaching IR: Curricular considerations, chapter in Teaching and Learning in Information Retrieval, vol. 31, The Information Retrieval Series, pp. 31-46, 2011.
  3. M.W. Berry, S.T. Dumais, G.W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, vol. 37, no. 4, pp. 573-595, 1995.
  4. M.W. Berry, Z. Drmac, E.R. Jessup, Matrices, vector spaces and information retrieval, SIAM Review, vol. 41, no. 2, pp. 335-362, 1999.
  5. A. Moffat and J. Zobel, Self-indexing inverted files for fast text retrieval, ACM Transactions on Information Systems, vol. 14, no. 6, pp. 349-379, 1996.
  6. J. Zobel and A. Moffat, Inverted files for text search engines, ACM Computing Surveys, vol. 38, no. 2, 2006.
  7. S. Melnik, S. Raghavan, B. Yang, H. Garcia-Molina, Building a distributed full-text index for the Web, ACM Transactions on Information Systems, vol. 19, no. 3, pp. 217-241, 2001.
  8. Jon Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM, vol. 46, no. 5, pp. 604-632, 1999.
  9. Sergey Brin, Larry Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, vol. 30, no. 1-7, pp. 107-117, 1998.
  10. Monica Bianchini, Marco Gori, Franco Scarselli, Inside PageRank, ACM Transactions on Internet Technology, vol. 5, no. 1, pp. 92-128, 2005.
  11. Pavel Berkhin, A Survey on PageRank Computing, Internet Mathematics, vol. 2, no. 1, pp. 73-120, 2005-2006.
  12. Zoltan Gyongyi, Hector Garcia-Molina, Web Spam Taxonomy, Workshop on Adversarial Information Retrieval on the Web, pp. 39-47, 2005. MUST READ
  13. Zoltan Gyongyi, Hector Garcia-Molina, Link Spam Alliances, Conference on Very Large Data Bases, pp. 517-528, 2005.
  14. Carlos Castillo and Brian D. Davison, Adversarial Web Search, Foundations and Trends in Information Retrieval, vol. 4, no. 5, pp. 377-486, 2010.
  15. Nikita Spirin and Jiawei Han, Survey on Web spam detection: Principles and algorithms, ACM SIGKDD Explorations, vol. 13, no. 2, pp. 50-64, 2011.
  16. Christopher Olston and Marc Najork, Web Crawling, Foundations and Trends in Information Retrieval, vol. 4, no. 3, pp. 175-246, 2010.

Videos

Πώς δουλεύει η μηχανή αναζήτησης της Google
Η εξέλιξη της μηχανής αναζήτησης της Google

Ωρες/ημέρες διαλέξεων

Δευτέρα 19:00-21:00 Αίθουσα Γ1 (3ος όροφος κτηρίου Γκλαβάνη)
Παρασκευή 13:00-15:00 Αίθουσα Συνεδριάσεων (4ος όροφος κτηρίου Γκλαβάνη)

Απαιτήσεις μαθήματος:

Εξεταστέα ύλη

Τα κεφάλαια από:
(ΒΙΒΛΙΟ) Η Μέθοδος PageRank της Google: 4,5,6,7,8,9,10,11,12
(ΒΙΒΛΙΟ) INTRO TO IR: 1,2,3,4,5,6,7,8

Εκφώνηση Προγραμματιστικής Εργασίας 2 ατόμων

Η εκφώνηση βρίσκεται εδώ,

1η Σειρά Προβλημάτων

Η εκφώνηση βρίσκεται εδώ.

2η Σειρά Προβλημάτων

Η εκφώνηση βρίσκεται εδώ.

3η Σειρά Προβλημάτων

Η εκφώνηση βρίσκεται εδώ.
Υλικό διάλεξης 2020-03-27
Υλικό διάλεξης 2020-03-30
Υλικό διάλεξης 2020-04-03
Υλικό διάλεξης 2020-04-06 και ολόκληρη η καταγεγραμμένη διάλεξη
Υλικό διάλεξης 2020-04-10 και ολόκληρη η καταγεγραμμένη διάλεξη
2020-05-04 ολόκληρη η καταγεγραμμένη διάλεξη
Υλικό διάλεξης 2020-05-08 και ολόκληρη η καταγεγραμμένη διάλεξη
Υλικό διάλεξης 2020-05-11 και ολόκληρη η καταγεγραμμένη διάλεξη
2020-05-15 η διάλεξη περιλάμβανε την θεωρία των διαφανειών. Δεν καταγράφηκε
Υλικό διάλεξης 2020-05-18 και ολόκληρη η καταγεγραμμένη διάλεξη
Υλικό διάλεξης 2020-05-22 και ολόκληρη η καταγεγραμμένη διάλεξη
Υλικό διάλεξης 2020-05-25 και ολόκληρη η καταγεγραμμένη διάλεξη
Ενδεικτικές παλαιοτέρων ετών εξετάσεις
Λόγω της ιδιαζούσης εξελίξεως του φετινού εαρινού εξαμήνου
(δεν κατέστη εφικτή η πραγματοποίηση της ενδιαμέσου γραπτής εξετάσεως και δεν μπορεί να γίνει η τελική γραπτή εξέταση δια ζώσης)
θα υπάρξει "εργασία στο σπίτι με χρονικό περιορισμό"
η οποία θα μετράει για 20% του συνολικού βαθμού και η εργασία (ή problem-sets) για 80%.
Αυτή η εξέταση θα πραγματοποιηθεί Τετάρτη 3 Ιουνίου.
Θα αναρτηθούν τα θέματα ακριβώς στις 9:00 και θα πρέπει να επιστραφούν με email (scanned ή ως ευκρινής φωτό) μέχρι 12:00.
[Κρατήστε στο sent-mail ένα αντίγραφο του μηνύματος αποστολής των λύσεων, ώστε σε περίπτωση καθυστέρησης άφιξής του να μπορεί να αποδειχθεί η εγκυρότητα αποστολής εντός του χρονικού περιθωρίου.]
Τετάρτη 03/06/2020 στις 09:00 να κατεβάσετε την 'Γραπτή Εξέταση εν οίκω' σ' αυτόν τον σύνδεσμο Βαθμολογία Τελικής Εξέτασης εδώ.
Δείτε την Αξιολόγηση (Ανοιξ.2018) του Μαθήματος και του Διδάσκοντα από τους φοιτητές.

Πρόγραμμα διαλέξεων

Οι διαλέξεις του μαθήματος θα ξεκινήσουν την εβδομάδα 10/02/2020.
Εβδομάδα Ημερομηνία Αντικείμενο διάλεξης Διαφάνειες (1ο μέρος) Διαφάνειες (2ο μέρος)
1 10-14/02/2020 α) Εισαγωγή στην Ανάκτηση Πληροφορίας (Introduction to IR)
β) Βασικές έννοιες στο Αντεστραμμένο Ευρετήριο (Basic concepts in Inverted Index) 		Διάλεξη 1 Διάλεξη 2
2 17-21/02/2020 α) Ασκήσεις
β1) Λεξικό και Λίστα των postings (Dictionary and Posting)
β2) Βελτιστοποιημένο αντεστραμμένο ευρετηρίο με Δείκτες Παράκαμψης (Skip pointers) 		Διάλεξη 3
3 24-28/02/2020 α) Ερωτήματα φράσης (Phrase queries)
β) Ερωτήματα με χαρακτήρες wild-card (Wild-card queries) 		Διάλεξη 4 Διάλεξη 5
3.5 02-06/03/2020 α) ΑΡΓΙΑ
β) Διόρθωση πληκτρολόγησης (Spelling correction) 		Διάλεξη 6
4.5 09-13/03/2020 α) Κατασκευή του Αντεστραμμένου Ευρετηρίου (Inverted Index construction)
β) Συμπίεση του Αντεστραμμένου Ευρετηρίου (Inverted Index compression) 		Διάλεξη 7 Διάλεξη 8
5.5 16-20/03/2020 α) Μοντέλο ανάκτησης διανυσματικού χώρου (Vector space retrieval model)
β) Αποτίμηση συστημάτων ανάκτησης πληροφορίας (Evaluation of IR systems) 		Διάλεξη 9 Διάλεξη 10
6.5 23-27/03/2020 α) Ασκήσεις στην συμπίεση, μοντέλο διανυσματικού χώρου (Exercices on index compression, on vector space retrieval)
β) Ασκήσεις στην αποτίμηση συστημάτων ανάκτησης πληροφορίας (Exercices on the evaluation of IR systems) 		Ζητήματα εξειδίκευσης
7.5 30/03-03/04/2020 α) Ενδιάμεση εξέταση (Midterm examination) (Να φέρετε υπολογιστήρα με δυνατότητα υπολογισμού λογαρίθμων)
β) Τα μαθηματικά του Google PageRank (The mathematics of Google's PageRank) 		Διάλεξη 11
8.5 06-10/04/2020 α) Ερπυστές στον Παγκόσμιο Ιστό Ι (Crawlers for the Web Ι)
β) Ερπυστές στον Παγκόσμιο Ιστό ΙΙ (Crawlers for the Web ΙΙ) 		Διάλεξη 12 Διάλεξη 13
9 27/04-01/05/2020 α) Ο PageRank ως γραμμικό σύστημα (The PageRank problem as a linear system)
β) ΑΡΓΙΑ 		Διάλεξη 14
10 04-08/05/2020 α1) Παράμετροι του μοντέλου PageRank (Parameters in the PageRank model)
α2) Ανάλυση ευαισθησίας του PageRank (The sensitivity of PageRank)
β) Ζητήματα υλοποίησης μεγάλης κλίμακας του PageRank (Issues in large-scale implementation of PageRank) 		Διάλεξη 15 Διάλεξη 16
11 11-15/05/2020 α) Οι αλγόριθμοι διάταξης HITS και SALSA (The HITS and SALSA ranking algorithms)
β1) Ρυποδιαφήμιση στις Μηχανές Αναζήτησης (Spamming Search Engines). Διαβάστε το εξής
β2) Ρυποδιαφήμιση στον PageRank (Spamming PageRank) 		Διάλεξη 17 Διάλεξη 18
12 18-22/05/2020 α) Ο αλγόριθμος BrowseRank (The BrowseRank ranking algorithm)
β) Ασκήσεις 		Διάλεξη 19 άσκηση για HITS
13 25-29/05/2020 α) Ασκήσεις
β) Τελική εξέταση (Final exam) στην Αίθουσα Γ1 (κτήριο Γκλαβάνη) ??:00-??:00

dkatsar AT e-ce DOT uth DOT gr
Τελευταία ενημέρωση: Παρ. 29 Μαϊου 2020