Κατάλογος Εκδηλώσεων

ΠΟΛΥΤΕΧΝΕΙΟ ΚΡΗΤΗΣ
Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών
Πρόγραμμα Προπτυχιακών Σπουδών

ΠΑΡΟΥΣΙΑΣΗ ΔΙΠΛΩΜΑΤΙΚΗΣ ΕΡΓΑΣΙΑΣ

Χαράλαμπου Χούλη 

με θέμα

Αλγόριθμοι Επιγραμμικής Μάθησης για τη Βελτιστοποίηση Συστάσεων σε Περιβάλλοντα Πολυεκπομπής Περιεχομένου 

Online Learning Algorithms for Recommendation Optimization in Multicast Content Environments

Εξεταστική Επιτροπή
Καθηγητής Θρασύβουλος Σπυρόπουλος (επιβλέπων)
Καθηγητής Μιχαήλ Γ. Λαγουδάκης
Δρ Ιωάννης Πευκιανάκης, Αρχιτέκτων Ασύρματων Συστημάτων στην Apple 

Περίληψη

Το ζωντανό περιεχόμενο και το περιεχόμενο συνεχούς ροής αποτελούν έναν από τους κυρίαρχους φόρτους εργασίας των σύγχρονων υποδομών επικοινωνιών. Στα συστήματα κοινόχρηστης διανομής, σημαντικό μέρος του λειτουργικού κόστους δεν συνδέεται με τον όγκο της κίνησης, αλλά με το πλήθος των διακριτών ροών που πρέπει να διατηρούνται ενεργές: μία και μόνη ροή μπορεί να μοιράζεται μεταξύ πολλών ταυτόχρονων θεατών, ενώ κάθε πρόσθετη ενεργή ροή καταναλώνει σπάνιους πόρους, όπως η χωρητικότητα μετακωδικοποίησης (transcoding) και η αντιγραφή στους εξυπηρετητές άκρης (edge replication). Τα συστήματα συστάσεων, τα οποία παραδοσιακά αντιμετωπίζονται ως μηχανισμοί εξατομίκευσης προς τον χρήστη, διαμορφώνουν επίσης τον τρόπο με τον οποίο κατανέμεται η ζήτηση μεταξύ των ροών και λειτουργούν συνεπώς ως μοχλός ελέγχου του δικτύου: κατευθύνοντας έναν αφικνούμενο χρήστη προς ένα ήδη ενεργό κανάλι, το σύστημα συστάσεων μπορεί να συγκεντρώσει τη ζήτηση και να μειώσει το πλήθος των ενεργών ροών, υπό την προϋπόθεση ότι διατηρείται η ποιότητα εμπειρίας του χρήστη. Η παρούσα διπλωματική εργασία μελετά το προκύπτον πρόβλημα συστάσεων φιλικών προς την πολυεκπομπή (multicast-friendly), το οποίο διατυπώνεται ως ελαχιστοποίηση υπό περιορισμούς του χρονικά μέσου πλήθους ενεργών καναλιών, με κάτω φράγμα στη μέση χρησιμότητα που παρέχεται ανά άφιξη. Το κεντρικό ερώτημα σε όλη την εργασία είναι κατά πόσον μια επιγραμμική (online) πολιτική με επίγνωση της κατάστασης του συστήματος μπορεί να ικανοποιεί αυτό το κατώφλι ποιότητας εμπειρίας, διατηρώντας ταυτόχρονα αυστηρά λιγότερα ενεργά κανάλια από μια ισχυρή στατική πολιτική αναφοράς.
Το πρόβλημα διατυπώνεται ως δεσμευμένη μαρκοβιανή διαδικασία αποφάσεων (Constrained Markov Decision Process, CMDP) επάνω σε ένα μοντέλο δραστηριότητας χρηστών ON/OFF συνεχούς χρόνου, και αναπτύσσεται μια ακολουθία δυναμικών πολιτικών αυξανόμενης κλίμακας έναντι δύο στατικών πολιτικών αναφοράς: μιας άπληστης ευρετικής κάλυψης συνόλου (greedy set-cover) και μιας αναλυτικά βελτιστοποιημένης πολιτικής κατωφλίου α, οι παράμετροι της οποίας προκύπτουν εκτός γραμμής (offline) μέσω μιας προσέγγισης μέσου πεδίου (mean-field). Το πρόβλημα μικρής κλίμακας επιλύεται αρχικά με ακρίβεια μέσω επανάληψης τιμών (Value Iteration), απομονώνοντας τον μηχανισμό, επαναχρησιμοποίηση των ενεργών καναλιών και αποφυγή πρόωρων ενεργοποιήσεων, μέσω του οποίου η προνοητικότητα μειώνει το κόστος. Για την επίτευξη ρεαλιστικών κλιμάκων, η πινακοποιημένη λύση αντικαθίσταται από ένα βαθύ δίκτυο Q (Deep Q-Network, DQN) που εκπαιδεύεται απευθείας στη δυναμική της δραστηριότητας των χρηστών, με τον περιορισμό ποιότητας εμπειρίας να επιβάλλεται εντός του αλγορίθμου μάθησης μέσω λαγκρανζιανής, βελτιστοποιούμενης με δυϊκή ανάβαση (dual ascent). Σημαντικό μέρος της εργασίας είναι διαγνωστικό: στο ομοιογενές, συμμετρικό καθεστώς αποδεικνύεται ότι υπάρχει εφικτή μαθημένη (learned)  πολιτική που υπερτερεί της στατικής πολιτικής αναφοράς και ότι είναι αναπαραστάσιμη από το δίκτυο, ωστόσο η εκπαίδευση από ψυχρή εκκίνηση (cold start) αδυνατεί να τη φθάσει. Το εμπόδιο αυτό εντοπίζεται, δι' αποκλεισμού, στην κλάση των ντετερμινιστικών πολιτικών argmax, η οποία δεν μπορεί να διατηρήσει τη μεικτή πολιτική που απαιτεί το βέλτιστο σημείο μείωσης κόστους επάνω σε εναλλάξιμες καταστάσεις. Η άρση αυτής της εναλλαξιμότητας μέσω ετερογένειας στους ρυθμούς δραστηριότητας, σε συνδυασμό με μια αρχιτεκτονική ανά κανάλι (channel-wise architecture) αναλλοίωτη σε μεταθέσεις, ένα χαρακτηριστικό επιμονής (persistence) ανά κανάλι και έναν διαβαθμισμένο περιορισμό, επιτρέπει στη μαθημένη πολιτική να βελτιώνει αυστηρά τη στατική πολιτική αναφοράς, παραμένοντας εφικτή από ψυχρή εκκίνηση. Μια ανάλυση ανά απόφαση αποδίδει το κέρδος στην εξαρτώμενη από την κατάληψη επαναχρησιμοποίηση μακρόβιων καναλιών, την οποία ο στατικός κανόνας δεν μπορεί να αναπαραστήσει, χωρίς καμία θυσία στη χρησιμότητα του χρήστη. Ένας έλεγχος με μυωπική πολιτική δείχνει ότι το πλεονέκτημα διατηρείται και με μηδενικό συντελεστή έκπτωσης, εντοπίζοντάς το στην αναπαράσταση της κατάστασης και όχι στο βάθος σχεδιασμού. Το πλεονέκτημα είναι υπό συνθήκη και όχι καθολικό: φέρεται από την ετερογένεια των ρυθμών δραστηριότητας, μια δομή που η στατική πολιτική αναφοράς δεν μπορεί να αναπαραστήσει αλλά η μαθημένη πολιτική μπορεί να εκμεταλλευθεί, ενώ η ασυμμετρία δημοτικότητας απορροφάται απευθείας στο βέλτιστο της ίδιας της πολιτικής αναφοράς. Η εργασία, συνεπώς, τεκμηριώνει ότι ένα μαθημένο σύστημα συστάσεων που σέβεται τον περιορισμό μπορεί να υπερτερεί μιας ισχυρής στατικής πολιτικής αναφοράς, και προσδιορίζει την αναπαραστατική ασυμμετρία που απαιτεί αυτή η βελτίωση.

Abstract 

Live and streamed content constitutes one of the dominant workloads of modern communication infrastructure. In shared delivery systems a substantial part of the operating cost is tied not to the volume of traffic but to the number of distinct streams that must be kept active: a single stream can be shared across many co-viewers while each additional active stream draws on scarce resources such as transcoding capacity and edge replication. Recommendation systems, traditionally treated as user-facing personalisation mechanisms, also shape how demand is distributed across streams and therefore act as a network-control lever: by steering an arriving user toward an already-active channel, the recommender can consolidate demand and reduce the number of active streams, provided the user's quality of experience is preserved. This thesis studies the resulting multicast-friendly recommendation problem, formalised as the constrained minimisation of the time-averaged number of active channels subject to a lower bound on the mean utility delivered per arrival. The central question throughout is whether an online, state-aware policy can meet this
quality-of-experience floor while sustaining strictly fewer active channels than a strong static benchmark.
The problem is cast as a constrained Markov decision process over a continuous-time ON/OFF user-activity model, and a sequence of dynamic policies of increasing scale is developed against two static baselines: a greedy set-cover heuristic and an analytically optimised α-threshold policy whose parameters are derived offline through a mean-field approximation. The small-scale problem is first solved exactly by value iteration, isolating the mechanism, reuse of active channels and avoidance of premature activations, by which foresight reduces cost. To reach realistic scales the tabular solution is replaced by a deep Q-network trained directly against the activity dynamics, with the quality-of-experience constraint enforced inside the learner through a Lagrangian relaxation optimised by dual ascent. A substantial part of the work is diagnostic: in the homogeneous, symmetric regime a feasible learned policy that beats the static benchmark is shown to exist and to be representable by the network, but cold-start training cannot reach it, and this obstruction is traced by elimination to a deterministic-argmax policy class that cannot hold the mixing policy the cost-improving optimum requires over exchangeable states. Breaking this exchangeability through activity-rate heterogeneity, together with a permutation-invariant channel-wise architecture, a per-channel persistence feature, and a graded constraint, enables the learned policy to strictly improve on the static benchmark while remaining feasible from a cold start. A per-decision analysis attributes the gain to occupancy-conditioned reuse of long-lived channels that the static rule cannot represent, delivered without any sacrifice in user utility. A myopic-policy control shows the advantage survives with the discount removed, locating it in the state representation rather than planning depth. The advantage is conditional rather than universal: it is carried by activity-rate heterogeneity, a structure the static benchmark cannot represent but the learned policy can exploit, whereas popularity skew is absorbed directly into the benchmark's own optimum. The thesis therefore establishes that a learned, constraint-respecting recommender can outperform a strong static benchmark  and identifies the representational asymmetry that this improvement requires.

Meeting ID: 92187241010
Password: 457753