Αλγοριθμικές Μέθοδοι στην Τεχνητή Νοημοσύνη

Στοχος

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

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

Περιεχομενα

• Στοιχεία Κυρτής Βελτιστοποίησης
• Αλγόριθμοι Ελαχιστοποίησης Κυρτών Συναρτήσεων

Gradient Descent,Newton-Raphson, Conjugate Gradient, Εφαρμογές στη Μηχανική Μάθηση

• Γραμμικός Προγραμματισμός

Βασική Θεωρία, Αλγόριθμος Simplex, Δυϊκότητα, Ενδεικτικά Προβλήματα

• Ακέραιος Προγραμματισμός

Παραδείγματα Μοντελοποίησης, Γραμμική Χαλάρωση, Αλγόριθμοι Καθολικής Βελτιστοποίησης

• Στοιχεία Προσεγγιστικών Αλγορίθμων

NP-hard Προβλήματα, Προσέγγιση μέσω Γραμμικού Προγραμματισμού, Στρογγυλοποίηση, Προσέγγιση μέσω Δυϊκού Γραμμικής Χαλάρωσης

• Άμεσοι Αλγόριθμοι Λήψης Αποφάσεων με Στατιστική Πληροφορία

Άμεσοι αλγόριθμοι, Secretary Problem, Prophet Inequalities, άλλα σχετικά μοντέλα

• Άμεσοι Αλγόριθμοι Μηχανικής Μάθησης

No-Regret Learning, Experts Learning, Bandits Learning

Ενδεικτικη βιβλιογραφια

Προτεινόμενη Βιβλιογραφία:

• S. Boyd, L. Vanderberghe. Convex Optimization. Cambridge University Press, 2004.
• M. Mohri, A. Rostamizadeh, A. Talwalkar. Foundations of Machine Learning. MIT Press, 2018.
• D. Bertsimas, J. Tsitsiklis. Introduction to Linear Optimization. Athena Scientific, 1997.
• D. P. Williamson, D. B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011.
• C. H. Papadimitriou, K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.
• N. Cesa-Bianchi, G. Lugosi, Prediction, Learning, and Games. Cambridge University Press, 2006.
• T. Lattimore, C. Szepesvari. Bandit Algorithms. Cambridge University Press, 2020.

Συναφή επιστημονικά περιοδικά:

• SIAM Journal on Computing, SIAM
• Journal of the ACM, ACM
• Theory of Computing
• Journal of Machine Learning Research
• Journal of Artificial Intelligence Research
• Theoretical Computer Science, Elsevier