On clustering, classification and dictionary learning: a theoretical revisit of robust kmeans, nearest-neighbour classification and dictionary learning with Moreau envelopes

Abstract

The problem of risk minimization on the basis of empirical data is rather general and includes as particular cases three basic statistical problems: i) the problem of classification, ii) the problem of clustering, and iii) the problem of dictionary learning. Classification and clustering have a long history while dictionary learning is a recent branch of machine learning that aims at finding a matrix, or else dictionary, which provides sparse representations for the data points of a problem. This thesis consists of three parts and is specifically concerned with statistical properties of algorithms that solve these three fundamental data analysis problems.The first part presents new results regarding a popular variant of the k-means clustering procedure, robust k-means. While, in many cases, ordinary Euclidean k-means yields informative cluster structures, there exist cases where its performance dramatically deteriorates in the presence of arbitrary perturbations of input data. Robust k-means tries to resolve known robustness weaknesses of ordinary Euclidean k-means using a bounded loss function. In the second part, we study the asymptotic properties of special nearest-neighbor classification rules. These rules use variants of the k-means clustering procedure to generate a set of properly labeled vectors in which the nearest neighbor rule will search for neighbors of a query point. The third part concerns a variant of the dictionary learning problem with a special type of reconstruction loss which replaces the ordinary Euclidean squared loss. In this part, we derive generalization bounds for the dictionary learning problem when the empirical loss function is a Moreau envelope, a well studied function transformation with origins in variational analysis. A new sample complexity result, concerning the case of k-sparse representation vectors, removes a redundant condition regarding the coherence of dictionaries appearing in previous works.

Το πρόβλημα της ελαχιστοποίησης κόστους με βάση εμπειρικά δεδομένα είναι αρκετά γενικό και περιλαμβάνει ως ειδικές περιπτώσεις τρία βασικά στατιστικά προβλήματα: i) το πρόβλημα της ταξινόμησης προτύπων, ii) το πρόβλημα της ομαδοποίησης/συσταδοποίησης δεδομένων και iii) το πρόβλημα της εκμάθησης λεξικών από δεδομένα. Η ταξινόμηση και η συσταδοποίησης έχουν μακρά ιστορία, ενώ η εκμάθηση λεξικών είναι ένας πρόσφατος κλάδος της μηχανικής μάθησης που στοχεύει στην εύρεση ενός πίνακα, ή αλλιώς λεξικού, που παρέχει αραιές αναπαραστάσεις για τα δεδομένα ενός υπο-μελέτη προβλήματος. Η παρούσα Διδακτορική Διατριβή αποτελείται από τρία μέρη και ασχολείται με στατιστικές ιδιότητες αλγορίθμων που επιλύουν τα τρία προαναφερθέντα θεμελιώδη προβλήματα ανάλυσης δεδομένων.Το πρώτο μέρος παρουσιάζει νέα αποτελέσματα σχετικά με μια δημοφιλή παραλλαγή του αλγορίθμου συσταδοποίησης k-μέσων, την εύρωστη παραλλαγή k-μέσων. Ενώ, σε πολλές περιπτώσεις, η κλασσική εκδοχή του αλγορίθμου k-μέσων παράγει αποδεκτές διασπάσεις/συστάδες, υπάρχουν περιπτώσεις όπου η απόδοσή του επιδεινώνεται δραματικά, ειδικότερα όταν υπάρχει παρουσία αυθαίρετων διαταραχών στα δεδομένων εισόδου. Αυτή η εύρωστη παραλλαγή των k-μέσων προσπαθεί να επιλύσει τις γνωστές αδυναμίες ευρωστίας του κλασσικής εκδοχής χρησιμοποιώντας φραγμένες συνάρτησεις κόστους, αντί της τετραγωνικής συνάρτησης. Στο δεύτερο μέρος της διατριβής, μελετάμε τις ασυμπτωτικές ιδιότητες κανόνων ταξινόμησης πλησιέστερου γείτονα. Αυτοί οι κανόνες χρησιμοποιούν παραλλαγές του αλγορίθμου ομαδοποίησης k-μέσων για να δημιουργήσουν ένα σύνολο από κατάλληλα επιλεγμένα διανύσματα στα οποία ο κανόνας πλησιέστερου γείτονα θα αναζητήσει πλησιέστερους γείτονες. Το τρίτο μέρος αφορά μια παραλλαγή του προβλήματος εκμάθησης λεξικού με έναν ειδικό τύπο συνάρτησης κόστους/ανακατασκευής που αντικαθιστά το συνηθισμένο Ευκλείδειο τετραγωνικό κόστος. Σε αυτό το μέρος, παρουσιάζονται αποτελέσματα γενίκευσης (generalization bounds) για το πρόβλημα εκμάθησης λεξικού όταν η συνάρτηση κόστους είναι μια περιβάλλουσα Moreau. Οι περιβάλλουσες Moreau είναι ένας καλά μελετημένος μετασχηματισμός στον κλάδο της πραγματικής και κυρτής ανάλυσης.