Techniques for learning constraint satisfaction problems with applications in telecommunications
Authors: Τσούρος Δημοσθένης 
Published: May 2022

Ο Προγραμματισμός με Περιορισμούς (Constraint Programming - CP) θεωρείται ως μια από τις πιο επιτυχημένες τεχνολογίες για την επίλυση συνδυαστικών προβλημάτων σε εφαρμογές Τεχνητής Νοημοσύνης (ΤΝ). Ωστόσο, υπάρχουν ακόμη προκλήσεις που πρέπει να αντιμετωπιστούν για να γίνει ακόμη ευρύτερα χρησιμοποιούμενη η τεχνολογία CP, με βασικό εμπόδιο να αποτελεί η απαίτηση για μεγάλη εξειδίκευση για τη μοντελοποίηση του προβλήματος και την αναπαράστασή του ως δίκτυο περιορισμών, πριν την επίλυσή του. Επομένως, η ανάπτυξη μεθόδων αυτοματοποιημένης μοντελοποίησης θεωρείται πολύ μεγάλης σημασίας, με την έρευνα για ανάπτυξη συστημάτων Απόκτησης Περιορισμών (Constraint Acquisition - CA) να έχει τραβήξει πολύ προσοχή. Τα συστήματα Απόκτησης Περιορισμών μπορούν να βοηθήσουν μη εξειδικευμένους χρήστες να μοντελοποιήσουν τα προβλήματά τους ως δίκτυα περιορισμού είτε χρησιμοποιώντας ένα σύνολο δεδομένων που περιέχει διαφορετικά παραδείγματα λύσεων και μη λύσεων του προβλήματος (παθητική μάθηση - passive learning) ή ταξινομώντας ένα σύνολο από παραδείγματα ως λύσεις ή μη λύσεις του προβλήματος (ενεργητική μάθηση - active learning). Δύο σημαντικά μειονεκτήματα τέτοιων διαδραστικών συστημάτων, όπου και οι πιο σύγχρονοι αλγόριθμοι αντιμετωπίζουν προβλήματα, είναι ο μεγάλος αριθμός ερωτημάτων που πρέπει να απαντήσει ο χρήστης, αλλά και οι υψηλοί χρόνοι που απαιτούνται για να βρει κατάλληλα ερωτήματα το σύστημα, ιδιαίτερα κοντά στο τέλος της διαδικασίας. Αυτό το ελάττωμα είναι ακόμη μεγαλύτερο όταν το πρόβλημα περιέχει ορισμένες κατηγορίες περιορισμών, όπως περιορισμούς γραμμικών ανισοτήτων, καθώς δεν υπάρχουν μέθοδοι για τον αποτελεσματικό χειρισμό συγκεκριμένων κατηγοριών περιορισμών. Επιπλέον, υπάρχουν ορισμένα ακόμα σημαντικά ζητήματα όσον αφορά την εφαρμογή των συστημάτων απόκτησης περιορισμών σε πραγματικά προβλήματα, όπως η υπόθεση ότι ο χρήστης μπορεί να απαντήσει σε όλα τα ερωτήματα του συστήματος με απόλυτη βεβαιότητα αλλά και το γεγονός ότι δεν 3 υπάρχει τρόπος απόκτησης περιορισμών με ενεργητική μάθηση για την εκμάθηση ελαστικών περιορισμών (soft constraints), που χρησιμοποιούνται σε πολλά προβλήματα μοντελοποιώντας προτιμήσεις του χρήστη σε προβλήματα βελτιστοποίησης. Σε αυτή τη διατριβή, προτείνουμε αλγοριθμικές και ευρετικές μεθόδους για την αντιμετώπιση των παραπάνω ζητημάτων. Αρχικά, προτείνουμε έναν αλγόριθμο, ονόματι MQuAcq, συνδυάζοντας ιδέες από αλγόριθμους τελευταίας τεχνολογίας, βελτιώνοντας σε μεγάλο βαθμό τη διαδικασία απόκτησης περιορισμών, σχετικά με τον αριθμό των ερωτημάτων και τον απαιτούμενο χρόνο. Παρουσιάζουμε επίσης μια τεχνική που, αποφεύγοντας να παρουσιάζει μη ανακαία ερωτήματα στον χρήστη, μειώνει σημαντικά τον αριθμό των ερωτημάτων στη διαδικασία εύρεσης του πεδίου εφαρμογής κάθε περιορισμού. Στη συνέχεια, στρέφουμε την προσοχή μας στη διαδικασία δημιουργίας ερωτημάτων από το σύστημα, η οποία είναι ένα πολύ σημαντικό μέρος των συστημάτων απόκτησης περιορισμών. Περιγράφουμε λεπτομερώς το πως δημιουργούνται τα ερωτήματα και προτείνουμε ευρετικές μεθόδους για τη βελτίωση της απόδοσης. Ιδιαίτερα σημαντικό είναι το γεγονός πως οι προτεινόμενες μέθοδοι ξεπερνάνε ορισμένα πολύ σημαντικά προβλήματα των συστημάτων απόκτησης περιορισμών, όπως ο πρόωρος τερματισμός του συστήματος. Στη συνέχεια, βελτιώνουμε τον αλγόριθμο MQuaAcq, προτείνοντας τον MQuAcq2, έναν νέο αλγόριθμο που αξιοποιεί τη δομή του μέρους του προβλήματος που έχει μάθει κατά τη διάρκεια της εκμάθησης και συνεπώς είναι πολύ πιο γρήγορος σε μεγάλα προβλήματα σε σχέση με τον MQuAcq. Στη συνέχεια, επικεντρωνόμαστε σε μια σημαντική κατηγορία περιορισμών, αυτή των γραμμικών ανισοτήτων, και προτείνουμε μια μέθοδο για την αποτελεσματική εκμάθησή τους, δείχνοντας ότι ο εξειδικευμένος χειρισμός ορισμένων περιορισμών μπορεί να επιταχύνει σημαντικά τη διαδικασία αυτοματοποιημένης μοντελοποίησης. Παρουσιάζουμε επίσης δύο αλγόριθμους για τον χειρισμό περιπτώσεων όπου ο χρήστης δεν μπορεί να απαντήσει σε όλα τα ερωτήματα του συστήματος με απόλυτη βεβαιότητα, κάτι που είναι πολύ πιθανό να συμβεί σε πραγματικές εφαρμογές των συστημάτων απόκτησης περιορισμών. Επικεντρωνόμαστε στην περίπτωση που ο χρήστης είναι αβέβαιος εάν ορισμένα παραδείγματα είναι λύσεις ή όχι του προβλήματος, και προτείνουμε μεθόδους που επιτρέπουν στον χρήστη να προσπεράσει ορισμένα ερωτήματα, χωρίς να τα απαντήσει. Επιπλέον, σημαντικό είναι πως 4 ο δεύτερος αλγόριθμός μας δε βρίσκει μόνο το μέρος του δικτύου περιορισμών του προβλήματος που μπορεί, αλλά και τους περιορισμούς που προκαλούν την αβεβαιότητα του χρήστη. Τέλος, η προσοχή μας επικεντρώνεται στο πρόβλημα της εκμάθησης ελαστικών περιορισμών στο πλαίσιο των προβλημάτων μέγιστης ικανοποίησης περιορισμών (Maximum Constraint Satisfaction Problems - Max-CSPs) με ενεργητική μάθηση, για πρώτη φορά. Πρώτα, περιγράφουμε έναν νέο τύπο ερωτημάτων για τα συστήματα απόκτησης περιορισμών, δηλαδή ερωτήματα προτιμήσεων, που παρουσιάζουν δύο παραδείγ-ματα στον χρήστη και η ερώτηση είναι ποιό από τα δύο ικανοποιεί τις προτιμήσεις του περισσότερο. Στη συνέχεια, προτείνουμε έναν νέο αλγόριθμο που μπορεί να βρει τους ελαστικούς περιορισμούς που αντιπροσωπεύουν τις προτιμήσεις του χρήστη, καθοδηγούμενοι από τις απαντήσεις του. Στη διατριβή δίνουμε πειραματικά αποτελέσματα και λεπτομερή θεωρητική ανάλυση όλων των προτεινόμενων αλγορίθμων. Οι προτεινόμενες μέθοδοι μας ενισχύουν σημαντικά την απόδοση των συστημάτων απόκτησης ενεργών περιορισμών στις πιο σημαντικές μετρικές, όπως ο αριθμός των ερωτημάτων και ο χρόνος που απαιτείται. Πολύ σημαντικό είναι πως με τις μεθόδους που προτείνουμε, ξεπερνάμε πολλά από τα ζητήματα σχετικά με την πρακτική εφαρμογή των συστημάτων απόκτησης περιορισμών σε πραγματικά προβλήματα. Παρουσιάζουμε μεθόδους που αντιμετωπίζουν περιπτώσεις που μπορούν να εμφανιστούν σε εφαρμογές πραγματικού κόσμου για πρώτη φορά, φέρνοντας πιο κοντά τη χρήση της ενεργού απόκτησης περιορισμών στην πράξη, η οποία είναι το επόμενο βήμα.