Επεξεργασία Σημάτων, θεωρία Γραφημάτων και Μάθηση

Επίσημο περίγραμμα μαθήματος του ΤΜΗΥΠ (Πανεπιστήμιο Πατρών), όπως δημοσιεύεται στη σελίδα του μαθήματος και στο συνημμένο αρχείο «Περίγραμμα Μαθήματος». Το κείμενο παρατίθεται αυτούσιο, χωρίς τα πρότυπα οδηγιών του εντύπου.

Στόχοι

Σκοπός του μαθήματος είναι η απόκτηση των γνώσεων που απαιτούνται για τη δημιουργία ενός κατάλληλου υποβάθρου να αναλύσουν και να ορίσουν προβλήματα επεξεργασίας σημάτων με χρήση γραφημάτων αναπαριστώντας με φυσικό τρόπο την δομή των σημάτων όπως π.χ. την πολυτροπικότητα (λήψη από διαφορετικά είδη αισθητήρα), την τοποθεσία λήψης και επεξεργασίας της πληροφορίας ή τις χρονικές εξαρτήσεις. Οι φοιτητές επίσης θα είναι σε θέση να εμπεδώσουν και στη συνέχεια να μεταφέρουν και να γενικεύσουν τις βασικές αρχές της επεξεργασίας σημάτων σε προβλήματα στα οποία μπορεί να αναπαρασταθούν τα δεδομένα με χρήση γραφημάτων. Τέτοια προβλήματα είναι τα προβλήματα που εμπεριέχουν την απόκτηση δεδομένων μέσω δικτύων αισθητήρων, κατανεμημένων επεξεργαστών, κοινωνικών δικτύων, χρονοσειρών, κ.λπ. Με την επιτυχή ολοκλήρωση του μαθήματος ένας φοιτητής θα είναι σε θέση να: εφαρμόσει τα βασικά στοιχεία της θεωρίας των γραφημάτων σε σήματα κατανοήσει τη φυσική σημασία της αναπαράστασης σημάτων με γραφήματα (πολυτροπικότητα, χρονική/χωρική εγγύτητα κλπ) κατανοήσει τον ορισμό συστημάτων σε γραφήματα και την γενίκευσή τους από την κλασσική θεωρία σημάτων και συστημάτων (τύποι συστημάτων, μετασχηματισμός Ζ, σχεδίαση φίλτρων) κατανοήσει την μαθηματική αλλά και την φυσική σημασία των σημάτων που αναπαρίστανται με γραφήματα, τόσο στο πεδίο των κόμβων όσο και στο πεδίο των συχνοτήτων να γενικεύσει τις έννοιες των στοχαστικών διαδικασιών σε γραφήματα να είναι σε θέση να αντιληφθεί τις έννοιες της δειγματοληψίας και της ανακατασκευής σε γραφήματα να αντιλαμβάνεται την λειτουργία νευρωνικών δικτύων σε γραφήματα να μπορεί να αναπτύξει τα κατάλληλα γραφήματα από σήματα. να μπορεί να αναπτύσσει εφαρμογές που κάνουν χρήση γραφημάτων με εργαλεία λογισμικού.

Περιεχόμενο (ύλη)

1.Ανασκόπηση Θεωρίας Γραφημάτων: Βασικοί ορισμοί, Ιδιότητες των Γραφημάτων και των συναναστρεφόμενων μητρώων, Μητρώο Γειτνίασης και Λαπλασιανό (Laplacian) και η αποσύνθεση ιδιοτιμών των, ταξινόμηση, χρωματισμός και κατάτμηση του συνόλου κορυφών ενός γραφήματος, παραδείγματα, κ.α.

2.0. Θεμελίωση της Κλασσικής Επεξεργασίας Γραφημάτων: Απεικόνιση ενός σήματος διακριτού χρόνου σε μορφή γραφήματος, ολίσθηση σήματος πάνω σε γράφημα, από ένα προς ένα απεικονίσεις σε ένα προς πολλά

2.1. Μετασχηματισμός Fourier σε γραφήματα (GFT): Από τον DFT στον GFT και πάλι στον DFT ως ειδική περίπτωσή του, Φάσμα Γραφήματος, ο αντίστροφος μετασχηματισμός (IGFT)

2.2. .Ορισμός Συστήματος σε Γραφήματα: Γραμμικά Αμετάβλητα σε Ολισθήσεις Συστήματα, Συνέλιξη, Μετασχηματισμός-Ζ Γραφήματος, Συνάρτηση Μεταφοράς Συστήματος, Σχεδίαση Φίλτρων και φιλτράρισμα σημάτων σε γραφήματα

1. Δειγματοληψία στον χώρο των κόμβων. Δειγματοληψία στον χώρο συχνοτήτων του γραφήματος. Ανακατασκευή γραφήματος.
2. Στατιστική Επεξεργασία Γραφημάτων: Βασικές Έννοιες Στοχαστικών Διαδικασιών, Ορισμός της Στασιμότητας με βάση το Μητρώο Γειτνίασης και το Laplacian, Ορισμός των Στάσιμων με την ευρεία έννοια Γραφημάτων, Φίλτρα Wiener σε Γραφήματα, Περιοδόγραμμα, Μοντέλα Κινητού Μέσου, Αυτοπαλινδρόμησης, Αυτοπαλινδρόμησης και Κινητού Μέσου
3. Ανάπτυξη γραφημάτων από δεδομένα. Προσεγγίσεις βασισμένες σε μοντέλα φυσικού κόσμου. Παρουσίαση στατιστικών προσεγγίσεων (Markov Random Fields, δίκτυα Bayes). Μοντέλα βασισμένα στον περιορισμό της συνέχειας.
4. Συνελικτικά νευρωνικά δίκτυα με χρήση γραφημάτων. Συναρτήσεις ενεργοποίησης. Πολυεπίπεδα δίκτυα.
5. Εφαρμογές. Τοποθέτηση αισθητήρων. Συμπλήρωση πίνακα. Δειγματοληψία 3Δ νέφους σημείων. Αναπαράσταση εικόνων και χρονοσειρών.

Αξιολόγηση

Η αξιολόγηση γίνεται στην Ελληνική γλώσσα και χωρίζεται σε δύο ανεξάρτητα μέρη. Η αξιολόγηση σχετικά με την εμπέδωση της θεωρίας γίνεται μέσω τελικής γραπτής και προφορικής εξέτασης. Συγκεκριμένα η γραπτή εξέταση περιλαμβάνει ερωτήσεις πολλαπλής επιλογής και επίλυσης προβλημάτων. Η προφορική εξέταση περιλαμβάνει ερωτήσεις σύντομης απάντησης σε θέματα που έχουν να κάνουν με την εργαστηριακή άσκηση. Μετά το πέρας της εξέτασης ανακοινώνονται και αναρτώνται τα αποτελέσματα. Μετά την ανάρτηση των αποτελεσμάτων οι φοιτητές μπορούν να ερωτήσουν για οποιαδήποτε σχετικά απορία έχουν για την βαθμολογία τους και μπορούν ακόμα και να αμφισβητήσουν το βαθμό τους.

Βιβλιογραφία

Vertex-Frequency Analysis of Graph Signals by Ljubiša Stanković (Editor), Ervin Sejdić (Editor), Springer 2019

Cooperative and Graph Signal Processing Principles and Applications Edited by Petar M. Djuric Cιdric Richard, Academic Press, 2018

William L. Hamilton, Graph Representation Learning Book, McGill University, (online) 2021

-Συναφή επιστημονικά περιοδικά και συνέδρια: IEEE Transactions on Signal Processing IEEE Transactions on Image Processing IEEE Transactions on Communications IEEE Transactions on Circuits and Systems Elsevier Signal Processing ICASSP Eusipco