Κατανεμημένη τανυστική αποδόμηση στη μηχανική μάθηση για πλήρως ή μερικώς παρατηρούμενα πολυδιάστατα δεδομένα μεγάλου όγκου

Abstract

In this dissertation, we propose a basic algorithm (GenProxSGD) for calculating a CANDECOMP/PARAFAC (CP) decomposition from partially observed data, which is based on the proximal operator. This algorithm deals with the decomposition’s optimization problem by solving local optimization problems, in the sense that in each iteration a proximal to the previous point is calculated that leads to the minimum of the objective function. Furthermore, we propose two distributed algorithms (ParallelProxSGD and StrProxSGD) that are based on the proximal operator and GenProxSGD for calculating a CP decomposition from data with missing entries. These algorithms are suitable for big data. These algorithms are assessed on big data and by experiments we show that possess great scaling properties in respect to different parameters like dimensionality, decomposition rank, speed-up etc. Subsequently, we propose a classification algorithm for Multiple Instance Learning (MIL) called TensMIL. In TensMIL we propose a new representation of instances by a tensor of order 3 and a method for instance-level features extraction by a CP decomposition, from fully or partially observed data. TensMIL is developed in two phases. In the first phase, we calculate the responses of the instances by a non-linear regression and in the second phase the distributions of the instances’ responses, within each bag, are calculated and a QDA classifier is trained. By TensMIL we solved two problems that are of totally different nature: (1) classification of histopathological colour images in benign and malignant and (2) estimation of the frailty index of elderly people by using multidimensional monitoring physiological signals of all day activities, that comprise signals from accelerometers, electrocardiogram (ECG) and breath monitoring. In both situations we assessed our algorithm in fully and partially (90% missing values) observed data. Our experiments showed, that our method achieved comparable performance when compared with state-of-the-art MIL algorithms. Furthermore, we extended and improved TensMIL by adding non-negativity constraints in the CP decomposition and by adding a phase of instance selection based on the confidence intervals of the responses of the non-linear regression. This new algorithm was assessed in the problem of the classification of natural images of wild animals, in the dataset Tiger, Fox, Elephant, a benchmark dataset in the literature of Multiple Instance Learning. By experiments, we showed that TensMIL2 has better performance than other state-of-the-art Multiple Instance Learning algorithms, as well as from Multiple Instance Learning algorithms that are based on deep learning algorithms. We assessed TensMIL2 on fully and partially observed data (90% missing values). By experiments, we showed that, in the majority of the cases investigated, TensMIL2, when applied to partially observed data, had a better or comparable performance we compared with state-of-the-art algorithms applied on fully observed data. Furthermore, we propose different techniques for instance selection for Multiple Instance Learning Algorithms. We propose a technique based on the information entropy measure and a technique based on the quality of clustering that is incorporated in JC2MIL algorithm, which was not equipped with an instance selection phase in the first place. Finally, we propose a new process for extracting multi-scale instances and features by a series of CP decompositions. The assessment of these techniques was done by using as reference algorithm JC2MIL. By experiments, we showed that in the majority of the investigated settings, the proposed techniques for instance selection have increased the classification performance of JC2MIL.

Στην παρούσα διδακτορική διατριβή προτείνουμε έναν βασικό αλγόριθμο, τον GenProxSGD, για τον υπολογισμό μιας CANDECOM/PARAFAC (CP) αποδόμησης από μερικώς παρατηρούμενα δεδομένα, ο οποίος βασίζεται στον τελεστή εγγύτητας και αντιμετωπίζει το πρόβλημα βελτιστοποίησης λύνοντας τοπικά προβλήματα βελτιστοποίησης, με την έννοια ότι σε κάθε επανάληψη υπολογίζεται ένα σημείο το οποίο να είναι σε εγγύτητα με το προηγούμενο σημείο, αλλά να οδηγεί προς το ελάχιστο της αντικειμενικής συνάρτησης. Επιπλέον, προτείνουμε δύο κατανεμημένους αλγορίθμους, τους ParallelProxSGD και StrProxSGD, που βασίζονται στον τελεστή εγγύτητας και στην παραπάνω ιδέα, για τον υπολογισμό μιας CP αποδόμησης από μερικώς παρατηρούμενα δεδομένα. Οι αλγόριθμοι αυτοί είναι κατάλληλοι και αξιολογήθηκαν σε δεδομένα μεγάλου όγκου. Δείξαμε πειραματικά ότι οι αλγόριθμοι αυτοί έχουν πολύ καλές ιδιότητες κλιμάκωσης ως προς διάφορες παραμέτρους (διαστατικότητα, βαθμός αποδόμησης, επιτάχυνση (speed-up) κ.τ.λ.). Στη συνέχεια, προτείνουμε έναν αλγόριθμο κατηγοριοποίησης για Μάθηση Πολλαπλών Στιγμιότυπων, τον TensMIL. Στον TensMIL προτείνουμε μια νέα αναπαράσταση των δεδομένων με τανυστές 3ης τάξης, και μια μέθοδο για τον υπολογισμό χαρακτηριστικών με CP αποδόμηση σε επίπεδο στιγμιότυπων, τόσο από πλήρως όσο και από μερικώς παρατηρούμενα δεδομένα. Ο TensMIL αναπτύσσεται σε δύο φάσεις. Στην πρώτη φάση, μια μη γραμμική παλινδρόμηση υπολογίζει την απόκριση των στιγμιότυπων, ενώ στη δεύτερη φάση υπολογίζονται οι κατανομές των αποκρίσεων ανά αντικείμενο και εκπαιδεύεται ένας QDA ταξινομητής. Με τη βοήθεια του TensMIL, επιλύσαμε δύο προβλήματα με εντελώς διαφορετική φύση μεταξύ τους: την κατηγοριοποίηση ιστοπαθολογικών εικόνων καρκίνου του μαστού σε κακοήθεις και καλοήθεις, καθώς και την εκτίμηση της ευθραυστότητας (frailty) ηλικιωμένων ατόμων από πολυδιάστατα σήματα παρακολούθησης, που περιλαμβάνουν επιταχυνσιόμετρα, καρδιογράφημα και παρακολούθηση της αναπνευστικής λειτουργίας. Και στις δύο περιπτώσεις, αξιολογήσαμε τον αλγόριθμο τόσο από πλήρως όσο και από μερικώς (10% των δεδομένων) παρατηρούμενα δεδομένα με συγκρίσιμα αποτελέσματα σε σχέση με αλγορίθμους αιχμής. Στη συνέχεια, επεκτείναμε και βελτιώσαμε τον αλγόριθμο TensMIL, προσθέτοντας περιορισμούς μη αρνητικότητας στην αποδόμηση CP καθώς και μια φάση επιλογής στιγμιότυπων, βασισμένη στα διαστήματα εμπιστοσύνης των αποκρίσεων της μη γραμμικής παλινδρόμησης. Ο νέος αυτός αλγόριθμος, TensMIL2, αξιολογήθηκε στην κατηγοριοποίηση φυσικών εικόνων άγριων ζώων, ένα σύνολο αναφοράς στη βιβλιογραφία της Μάθησης Πολλαπλών Στιγμιότυπων. Κατά τη πειραματική διαδικασία, συμπεράναμε ότι ο TensMIL2 έχει καλύτερη απόδοση από αλγόριθμους Μάθησης Πολλαπλών Στιγμιότυπων αιχμής καθώς και καλύτερη απόδοση από αλγόριθμους Μάθησης Πολλαπλών Στιγμιότυπων που βασίζονται στη βαθιά μηχανική μάθηση (deep learning). Η αξιολόγηση του TensMIL2 έγινε τόσο από πλήρως όσο και από μερικώς (10% των δεδομένων) παρατηρούμενα δεδομένα. Η πειραματική διαδικασία έδειξε, ότι στις περισσότερες των περιπτώσεων ο TensMIL2, όταν εφαρμόστηκε σε μερικώς παρατηρούμενα δεδομένα (10% παρατηρούμενες τιμές), είχε καλύτερη ή συγκρίσιμη απόδοση, σε σχέση με τους αλγορίθμους αιχμής όταν εφαρμοζόταν σε πλήρη δεδομένα. Επιπλέον, προτείνουμε μια τεχνική επιλογής στιγμιότυπων για αλγόριθμους Μάθησης Πολλαπλών Στιγμιότυπων που βασίζεται στο μέτρο της εντροπίας καθώς και μια τεχνική που βασίζεται στην ποιότητα της συσταδοποίησης, τις οποίες ενσωματώσαμε στον αλγόριθμο JC2MIL, ο οποίος δεν διέθετε κάποια διαδικασία επιλογής στιγμιότυπων. Τέλος, προτείνουμε και μια νέα διαδικασία εξαγωγής στιγμιότυπων και χαρακτηριστικών πολλαπλής κλίμακας, μέσω της αποδόμησης CP. Η αξιολόγηση όλων των προτεινόμενων τεχνικών έγινε χρησιμοποιώντας ως αλγόριθμο αναφοράς τον JC2MIL. Η πειραματική διαδικασία έδειξε ότι στις περισσότερες των περιπτώσεων, οι προτεινόμενες τεχνικές επιλογής στιγμιότυπων βελτίωσαν την απόδοση του JC2MIL.