Σεμινάριο Τμήματος & CEID social hour
Ημερομηνία-χώρος: Παρασκευή 23 Νοεμβρίου, 3-5μμ, Κτίριο Β (Αίθουσα ΑΣ)
Ομιλητής: Γιώργος Λαγογιάννης*, Επίκ. Καθηγητής στο τμήμα Αγροτικής Οικονομίας και Ανάπτυξης του Γεωπονικού Πανεπιστημίου Αθηνών
Τίτλος: “On the randomness that generates biased samples: The limited randomness approach”
Περίληψη: Στο διαδίκτυο παράγονται κάθε δευτερόλεπτο τεράστιοι όγκοι δεδομένων (αρχεία κλήσεων, επισκέψεις σε ιστοσελίδες, ενδείξεις αισθητήρων κλπ). Για τη θεωρητική μελέτη των προβλημάτων που σχετίζονται με τα δεδομένα αυτά, χρησιμοποιούμε το υπολογιστικό μοντέλο ροής δεδομένων (data stream model) σύμφωνα με το οποίο τα δεδομένα φτάνουν συνεχώς μέσω μίας πιθανώς ατελείωτης ροής (stream). Ο μεγάλος όγκος των δεδομένων αυτών και η περιορισμένη κύρια μνήμη που διαθέτουμε, επιβάλλουν να αποθηκευτεί ένα μικρό μόνο τμήμα τους που το ονομάζουμε σύνοψη ή δείγμα της ροής. Το δείγμα αυτό μπορεί να χρησιμοποιηθεί για την εκπαίδευση μοντέλων μηχανικής μάθησης (Machine Learning models) που θα αναλάβουν στη συνέχεια να επεξεργάζονται τα εισερχόμενα στοιχεία της ροής με στόχο την εξαγωγή πληροφοριών (στα πλαίσια εφαρμογών ασφάλειας, marketing, διαχείρισης δεδομένων κλπ).
Τα δεδομένα όμως ενδεχομένως αλλάζουν στο χρόνο και έτσι η επιτυχία αυτών των μοντέλων εξαρτάται σε μεγάλο βαθμό από την ικανότητά τους να προσαρμόζονται ανάλογα. Μία ιδέα είναι να τα επανεκπαιδεύουμε ανά τακτά χρονικά διαστήματα, με τη βοήθεια του δείγματος. Αν το δείγμα περιέχει σε αρκούντως μεγάλο ποσοστό, στοιχεία της πρόσφατης ιστορίας της ροής, αναμένουμε ότι αυτό μπορεί να χρησιμοποιηθεί επιτυχώς για την επανεκπαίδευση των μοντέλων μας.
Απλοϊκά, και υποθέτωντας ότι η μνήμη χωράει n στοιχεία της ροής, θα μπορούσε κανείς να αποθηκεύσει στο δείγμα μόνο τα n πιο πρόσφατα στοιχεία. Όμως τότε αγνοεί εντελώς το πιο μακρινό παρελθόν και αυτό είναι ίσως ακραίο. Μία πιο μέση λύση, είναι να δημιουργήσουμε ένα χρονικά μεροληπτικό (temporally biased) δείγμα στο οποίο το στοιχείο της ροής που έφτασε τη χρονική στιγμή r, “επιβιώνει” στο δείγμα τη χρονική στιγμή t (όπου t ≥ r) με πιθανότητα p(r, t) η οποία θα πρέπει να μειώνεται καθώς αυξάνεται η διαφορά t-r. Προς χάρην της συζήτησης, θα λέμε ότι ένα τέτοιο δείγμα υπακούει στη συνάρτηση p(r, t).
Στην εργασία [1] παρουσιάζεται ένας αλγόριθμος που δημιουργεί ένα δείγμα το οποίο υπακούει στην εκθετική συνάρτηση. Ο αλγόριθμος αυτός είναι απλός και διατηρεί σταθερό το μέγεθος του δείγματος ενώ κοστίζει Ο(1) χρόνο και χρησιμοποιεί Ο(logn) τυχαία bits για κάθε εισερχόμενο στοιχείο της ροής. Στην εργασία που θα παρουσιαστεί, πετυχαίνουμε το ίδιο αποτέλεσμα αλλά με Ο(1) τυχαία bits ανά εισερχόμενο στοιχείο ροής, βελτιώνοντας έτσι τον αλγόριθμο της εργασίας [1].
Για να καταλάβει κανείς σε βάθος όσα θα ειπωθούν, καλό θα είναι να έχει μία ιδέα για το τι είναι μία Μαρκοβιανή αλυσίδα, και η στάσιμη κατανομή της. Στη βιβλιογραφία δίνονται ενδεικτικά δύο πηγές ([2], [3]) για μία γρήγορη ενημέρωση.
(*) Η έρευνα στην οποία στηρίζεται η ομιλία είναι προϊόν συνεργασίας του ομιλητή με τους κκ. Σταύρο Κοντόπουλο και Χρήστο Μακρή (ΤΜΗΥΠ).
Βιβλιογραφία
[1] Charu C. Aggarwal, On biased reservoir sampling in the presence of stream evolution. VLDB ’06 Proceedings of the 32nd international conference on Very large data bases, pp. 607–618.
[2] https://www.youtube.com/watch?v=4zg5bNlHZRg
[3] https://www.youtube.com/watch?v=sXAknaqkZSs
Σχετικά με τον ομιλητή: O Γιώργος Λαγογιάννης γεννήθηκε το 1972. Αποφοίτησε το 1995 από το Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής του Πανεπιστημίου Πατρών. Το 2003 ανακηρύχθηκε Διδάκτορας του Τμήματος Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής του Πανεπιστημίου Πατρών. Είναι Επίκουρος Καθηγητής στο τμήμα Αγροτικής Οικονομίας και Ανάπτυξης του Γεωπονικού Πανεπιστημίου Αθηνών. Το γνωστικό του αντικείμενο είναι “Δομές Δεδομένων και Αλγόριθμοι”. Τα ερευνητικά του ενδιαφέροντα εστιάζονται σε προβλήματα δυναμικών γράφων, προβλήματα βελτιστοποίησης ερωτημάτων σε Βάσεις Δεδομένων καθώς και σε άλλα θεωρητικά προβλήματα της περιοχής των αλγορίθμων και δομών δεδομένων.
http://www.aoa.aua.gr/staff_details.aspx?mn=mn3&staff_id=77