Technical University of Crete (TUC)
On clustering, classification and dictionary learning: a theoretical revisit of robust kmeans, nearest-neighbour classification and dictionary learning with Moreau envelopes
Abstract
dc:descriptionThe 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.
Degree
thesis:*- Grantor dc:publisher
- Technical University of Crete (TUC)
- Year dc:date
- 2022
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Georgogiannis, Alexandros
- Γεωργογιάννης, Αλέξανδρος
Subjects
dc:subject × 22- Μηχανική μάθηση
- Επιβλεπόμενη μάθηση
- Μη επιβλεπόμενη μάθηση
- Στατιστική θεωρία μάθησης
- Θεωρία Vapnik–Chervonenkis
- Ομαδοποίηση k-means
- Αλγόριθμος κ κοντινότερων γειτόνων
- Πρόβλημα εκμάθησης λεξικού
- Machine learning
- Supervised learning
- Unsupervised learning
- Statistical learning theory
- Vapnik–Chervonenkis theory
- K-means clustering
- K-nearest neighbor algorithm
- Dictionary learning
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Επιστήμες Μηχανικού και Τεχνολογία
- Ρομποτική
- Electrical Engineering, Electronic Engineering, Information Engineering
- Engineering and Technology
- Robotics
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/52159