Scalable and Ensemble Learning for Big Data

Abstract

The turn of the decade has trademarked society and computing research with a ``data deluge.'' As the number of smart, highly accurate and Internet-capable devices increases, so does the amount of data that is generated and collected. While this sheer amount of data has the potential to enable high quality inference, and mining of information, it introduces numerous challenges in the processing and pattern analysis, since available statistical inference and machine learning approaches do not necessarily scale well with the number of data and their dimensionality. In addition to the challenges related to scalability, data gathered are often noisy, dynamic, contaminated by outliers or corrupted to specifically inhibit the inference task. Moreover, many machine learning approaches have been shown to be susceptible to adversarial attacks. At the same time, the cost of cloud and distributed computing is rapidly declining. Therefore, there is a pressing need for statistical inference and machine learning tools that are robust to attacks and scale with the volume and dimensionality of the data, by harnessing efficiently the available computational resources. This thesis is centered on analytical and algorithmic foundations that aim to enable statistical inference and data analytics from large volumes of high-dimensional data. The vision is to establish a comprehensive framework based on state-of-the-art machine learning, optimization and statistical inference tools to enable truly large-scale inference, which can tap on the available (possibly distributed) computational resources, and be resilient to adversarial attacks. The ultimate goal is to both analytically and numerically demonstrate how valuable insights from signal processing can lead to markedly improved and accelerated learning tools. To this end, the present thesis investigates two main research thrusts: i) Large-scale subspace clustering; and ii) unsupervised ensemble learning. The aforementioned research thrusts introduce novel algorithms that aim to tackle the issues of large-scale learning. The potential of the proposed algorithms is showcased by rigorous theoretical results and extensive numerical tests.

Η αλλαγή της δεκαετίας έχει χαρακτηρίσει την κοινωνία και την ερευνητική κοινότητα της πληροφορικής με έναν «κατακλυσμό δεδομένων». Καθώς αυξάνεται ο αριθμός των έξυπνων, υψηλής ακρίβειας και με δυνατότητα σύνδεσης στο Διαδίκτυο συσκευών, αυξάνεται αντίστοιχα και ο όγκος των δεδομένων που παράγονται και συλλέγονται. Παρόλο που αυτή η τεράστια ποσότητα δεδομένων έχει τη δυνατότητα να επιτρέψει ποιοτική εξαγωγή συμπερασμάτων και εξόρυξη πληροφορίας, εισάγει πληθώρα προκλήσεων στην επεξεργασία και ανάλυση προτύπων, καθώς οι υπάρχουσες μέθοδοι στατιστικής συμπερασματολογίας και μηχανικής μάθησης δεν κλιμακώνονται απαραίτητα αποτελεσματικά με τον αριθμό και τη διαστασιμότητα των δεδομένων. Πέρα από τις προκλήσεις της κλιμακωσιμότητας, τα συλλεγόμενα δεδομένα είναι συχνά θορυβώδη, δυναμικά, μολυσμένα με ακραίες τιμές ή αλλοιωμένα με στόχο την παρεμπόδιση της διαδικασίας συμπερασμού. Επιπλέον, πολλές προσεγγίσεις της μηχανικής μάθησης έχουν αποδειχθεί ευάλωτες σε επιθέσεις. Παράλληλα, το κόστος του υπολογιστικού νέφους και της κατανεμημένης υπολογιστικής ισχύος μειώνεται ραγδαία. Συνεπώς, υπάρχει επιτακτική ανάγκη για εργαλεία στατιστικής συμπερασματολογίας και μηχανικής μάθησης που να είναι ανθεκτικά σε επιθέσεις και να κλιμακώνονται με τον όγκο και τη διαστασιμότητα των δεδομένων, αξιοποιώντας αποτελεσματικά τους διαθέσιμους υπολογιστικούς πόρους. Η παρούσα διατριβή επικεντρώνεται στα αναλυτικά και αλγοριθμικά θεμέλια που στοχεύουν στην υλοποίηση στατιστικού συμπερασμού και ανάλυσης δεδομένων από μεγάλα σύνολα υψηλής διαστασιμότητας. Το όραμα είναι η δημιουργία ενός ολοκληρωμένου πλαισίου βασισμένου σε τεχνολογίες αιχμής της μηχανικής μάθησης, της βελτιστοποίησης και της στατιστικής, το οποίο να επιτρέπει πραγματικά μεγάλης κλίμακας συμπερασμό, αξιοποιώντας τους διαθέσιμους (ενδεχομένως κατανεμημένους) υπολογιστικούς πόρους και να είναι ανθεκτικό σε επιθέσεις. Ο απώτερος στόχος είναι να παρουσιαστεί, τόσο αναλυτικά όσο και αριθμητικά, πώς πολύτιμες έννοιες από την επεξεργασία σήματος μπορούν να οδηγήσουν σε σημαντικά βελτιωμένα και ταχύτερα εργαλεία μάθησης. Για τον σκοπό αυτό, η παρούσα διατριβή διερευνά δύο βασικούς άξονες έρευνας: i) Ομαδοποίηση σε υποχώρους μεγάλης κλίμακας (large-scale subspace clustering) καιii) μη εποπτευόμενη συνδυαστική μάθηση (unsupervised ensemble learning). Οι παραπάνω άξονες έρευνας εισάγουν καινοτόμους αλγορίθμους που αποσκοπούν στην αντιμετώπιση των προκλήσεων της μάθησης μεγάλης κλίμακας. Η δυναμική των προτεινόμενων αλγορίθμων αποδεικνύεται μέσα από αυστηρά θεωρητικά αποτελέσματα και εκτενείς αριθμητικές δοκιμές.