Algorithmic approaches for efficiency and explainability in learning problems

Abstract

This doctoral dissertation focuses on the development of supervised and unsupervised machine learning algorithms with an emphasis on two fundamental aspects: computational efficiency and explainability. The need for efficient and explainable models is particularly crucial in high-stakes domains such as healthcare, education, and finance, where automated decisions can directly impact human lives. Within this context, the dissertation addresses three core problems. (1) In the label ranking problem, which generalizes multiclass classification, the task is modeled as a nonparametric regression problem. Interpretable algorithms based on decision trees and random forests are proposed, accompanied by new theoretical guarantees and extensions of existing statistical bounds to noisy and incomplete data. (2) For global counterfactual explanations, the problem is formulated as a multi-objective optimization balancing interpretability, cost, and effectiveness. Its computational hardness is formally established, and efficient clustering-based algorithms are introduced, achieving improved trade-offs across the competing criteria compared to existing approaches. (3) In the time series clustering problem, a two-phase algorithm is proposed that first applies Sparse Gaussian Process Regression to reduce the dimensionality of time series before clustering, significantly improving computational and memory efficiency while preserving clustering quality and enhancing interpretability. Overall, the dissertation makes both theoretical and practical contributions, providing new computational and statistical guarantees for fundamental learning problems and offering scalable, interpretable algorithms applicable to large-scale, real-world datasets in socially impactful domains.

Η παρούσα διδακτορική διατριβή πραγματεύεται την ανάπτυξη αλγορίθμων επιβλεπόμενης και μη επιβλεπόμενης μηχανικής μάθησης, δίνοντας έμφαση σε δύο βασικούς άξονες, την υπολογιστική αποδοτικότητα και την ερμηνευσιμότητα. Η ανάγκη για αποδοτικούς και ερμηνεύσιμους αλγορίθμους είναι ιδιαίτερα κρίσιμη σε τομείς υψηλού κινδύνου, όπως η υγεία, η εκπαίδευση και η οικονομία, όπου οι αποφάσεις που λαμβάνονται από συστήματα μηχανικής μάθησης έχουν άμεσο αντίκτυπο στις ανθρώπινες ζωές. Στο πλαίσιο αυτό, εξετάζονται τρία θεμελιώδη προβλήματα: (1) Στην κατάταξη ετικετών (label ranking), μοντελοποιούμε το πρόβλημα ως μη παραμετρική παλινδρόμηση. Προτείνονται ερμηνεύσιμοι αλγόριθμοι βασισμένοι σε δέντρα απόφασης και τυχαία δάση, οι οποίοι συνοδεύονται από νέες θεωρητικές εγγυήσεις. Επιπλέον, δίνονται επεκτάσεις υπαρχόντων στατιστικών εγγυήσεων σε θορυβώδη και ελλιπή δεδομένα. (2) Στις καθολικές επεξηγήσεις με ανταπαραδείγματα (global counterfactual explanations), το πρόβλημα διατυπώνεται ως πολυκριτηριακή βελτιστοποίηση, με αντικρουόμενα κριτήρια βελτιστοποίησης την ερμηνευσιμότητα, το κόστος και την αποτελεσματικότητα. Αποδεικνύεται η υπολογιστική δυσκολία του προβλήματος και προτείνονται αποδοτικοί αλγόριθμοι βασισμένοι στην ομαδοποίηση, επιτυγχάνοντας καλύτερη ισορροπία (trade-offs) μεταξύ των αντικρουόμενων κριτηρίων σε σύγκριση με υπάρχουσες προσεγγίσεις. (3) Στην ομαδοποίηση χρονοσειρών (time series clustering), προτείνεται νέος αλγόριθμος δύο φάσεων που χρησιμοποιεί την Αραιή Παλινδρόμηση με Γκαουσιανές Διεργασίες (Sparse Gaussian Process Regression) για τη μείωση της διαστατικότητας των χρονοσειρών πριν την ομαδοποίηση, βελτιώνοντας σημαντικά την υπολογιστική αποδοτικότητα και τη διαχείριση μνήμης, διατηρώντας παράλληλα την ποιότητα της ομαδοποίησης και ενισχύοντας την ερμηνευσιμότητα. Συνολικά, η διατριβή συνεισφέρει τόσο σε θεωρητικό όσο και σε πρακτικό επίπεδο, παρέχοντας νέες υπολογιστικές και στατιστικές εγγυήσεις για θεμελιώδη προβλήματα μάθησης και προσφέροντας κλιμακώσιμους, ερμηνεύσιμους αλγορίθμους εφαρμόσιμους σε πραγματικά σύνολα δεδομένων μεγάλης κλίμακας σε τομείς με υψηλό κοινωνικό αντίκτυπο.