Techniques for learning constraint satisfaction problems with applications in telecommunications

Abstract

Constraint Programming (CP) is considered as one of the foremost paradigms for solving combinatorial problems in Artificial Intelligence. However, there are still challenges to be faced in order to make CP technology even more widely used, with the main bottleneck being the expertise required for the modelling of the problem. Constraint acquisition systems can assist non-expert users to model their problems as constraint networks by classifying examples as positive or negative. Two important bottlenecks of the acquisition process, where the state-of-the-art algorithms encounter problems, are the large number of queries required, and the high cpu times needed to generate queries, especially near convergence. This problem is even bigger when the problem contains certain classes of constraints, like linear constraints, as there are no methods to handle specific classes of constraints efficiently. In addition, there are some significant shortcomings regarding the applicability of constraint acquisition systems in real problems, such as the assumption that the user can answer all queries posted with absolute certainty and the fact that there is no active constraint acquisition method for learning soft constraints, to capture preferences of the user in optimization problems. In this dissertation, we propose algorithmic and heuristic methods to deal with the above issues. We first propose an algorithm, called MQuAcq, blending ideas from state-of-the-art algorithms, alleviating to a large extent the above issues regarding the number of queries and cpu time. We also present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly. Then, we turn our attention to query generation, which is a significant but rather overlooked part of the acquisition process. We describe query generation in detail and we propose heuristics for improving its efficiency, alleviating some important problems of constraint acquisition systems, like premature convergence. Next, we improve MQuaAcq by proposing MQuAcq-2, a new algorithm that exploits the structure of the learned problem in the learning process and is by far faster in large problems than MQuAcq. We then focus on the important class of linear inequality constraints and propose a method to learn them efficiently, showing that specific handling of certain constraints can speed up the acquisition process significantly. We also present two algorithms for handling cases where the user cannot answer all queries posted with absolute certainty. We focus on the case where the user is uncertain whether some assignments are solutions or not of the problem, and we give methods that allow the user to omit some queries. Importantly, our second algorithm can not only learn (a part of) the target network, but also the constraints that cause the user’s uncertainty. Finally, we deal with the problem of learning soft constraints in the context of Max-CSPs via active constraint acquisition, for the first time. We first introduce a new type of queries in Constraint Acquisition, namely (partial) preference queries, and then we propose a novel algorithm that can find the soft constraints that represent the preferences of the user, driven by the user’s answers. We present experimental results and detailed theoretical analysis of all the proposed algorithms. Our proposed methods are shown to boost the performance of active constraint acquisition systems significantly in the most important metrics. Importantly, in this dissertation we have also alleviated a lot of the issues regarding the applicability of constraint acquisition systems in real problems. It is now not assumed that the user is able to answer all the queries posted, and also possible preferences can be captured and modelled by constraint acquisition. Dealing with cases that can appear in real world applications for the first time, our work brings closer the utilization of active constraint acquisition in practice, which is now the next step.

Ο Προγραμματισμός με Περιορισμούς (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) με ενεργητική μάθηση, για πρώτη φορά. Πρώτα, περιγράφουμε έναν νέο τύπο ερωτημάτων για τα συστήματα απόκτησης περιορισμών, δηλαδή ερωτήματα προτιμήσεων, που παρουσιάζουν δύο παραδείγ-ματα στον χρήστη και η ερώτηση είναι ποιό από τα δύο ικανοποιεί τις προτιμήσεις του περισσότερο. Στη συνέχεια, προτείνουμε έναν νέο αλγόριθμο που μπορεί να βρει τους ελαστικούς περιορισμούς που αντιπροσωπεύουν τις προτιμήσεις του χρήστη, καθοδηγούμενοι από τις απαντήσεις του. Στη διατριβή δίνουμε πειραματικά αποτελέσματα και λεπτομερή θεωρητική ανάλυση όλων των προτεινόμενων αλγορίθμων. Οι προτεινόμενες μέθοδοι μας ενισχύουν σημαντικά την απόδοση των συστημάτων απόκτησης ενεργών περιορισμών στις πιο σημαντικές μετρικές, όπως ο αριθμός των ερωτημάτων και ο χρόνος που απαιτείται. Πολύ σημαντικό είναι πως με τις μεθόδους που προτείνουμε, ξεπερνάμε πολλά από τα ζητήματα σχετικά με την πρακτική εφαρμογή των συστημάτων απόκτησης περιορισμών σε πραγματικά προβλήματα. Παρουσιάζουμε μεθόδους που αντιμετωπίζουν περιπτώσεις που μπορούν να εμφανιστούν σε εφαρμογές πραγματικού κόσμου για πρώτη φορά, φέρνοντας πιο κοντά τη χρήση της ενεργού απόκτησης περιορισμών στην πράξη, η οποία είναι το επόμενο βήμα.