Distributed algorithms for support vector machine training in wireless sensor networks

Abstract

Advancements in low-power electronic devices integrated with wireless communication capabilities and sensors have opened up an exciting new field in computer science. Wireless sensor networks (WSN) can be developed at a relatively low-cost and can be deployed in a variety of different settings. The emergence of WSNs, has brought a significant interest towards decentralized detection, estimation and classification for use in monitoring, surveillance, location sensing, and distributed learning applications. Processing sensor data locally requires considerably less energy than communicating it to a distant node, yielding an interesting communication-computation tradeoff. To reduce global communication requirements, one needs to perform signal processing to extract key information in a distributed fashion and without losing fidelity. In this dissertation, we focus on the distributed training of Support Vector Machine (SVM) classifiers by taking advantage of the sparseness representation of their decision boundary determined only by a small subset of the training samples, the so-called support vectors. First, we present two incremental algorithms for distributed SVM training where the updates of the classifier are diffused sequentially in the network. We show that after a single complete pass through all the clusters, a good approximation of the optimal separating hyperplane is achieved. Then, we present two gossip-based algorithms that are robust to unexpected failures of nodes and to changes in the network topology. In the first scheme, each sensor updates its hyperplane at every iteration by combining its support vectors with the support vectors communicated by the neighbors, resulting in a close-to-optimal efficient distributed scheme. In the second approach, the information exchanged between sensors describes uniquely and completely the convex hulls of the two classes. This approach guarantees convergence to the optimal classifier at the expense of increased complexity associated with the construction of the convex hulls. Finally, by exploiting notions of convex optimization and duality theory, we derive a novel mathematical characterization for the sparse representation of the most important measurements that neighboring sensors should exchange in order to reach an agreement to the optimal linear classifier. We propose a function which ranks the training vectors in order of importance in the learning process. The amount of information to be exchanged is controlled by a user defined threshold, depending on the desired tradeoff between classification accuracy and power consumption. We prove that a threshold value exists for which the proposed algorithm converges to the optimal classifier. We explore the effect of the network topology to the convergence and we study the performance through simulation experiments.

Η πρόοδος της μικροηλεκτρονικής και των υλικών επέτρεψε την κατασκευή πολύ μικρών αισθητήρων διευρύνοντας τους ορίζοντες για έρευνα στις περιοχές των τηλεπικοινωνιών και της πληροφορικής. Τα ασύρματα δίκτυα αισθητήρων είναι μια συνεχώς αναπτυσσόμενη, χαμηλού πλέον κόστους τεχνολογία, η οποία έχει αλλάξει τον τρόπο με τον οποίο ο άνθρωπος αλληλεπιδρά με το περιβάλλον. Οι απαιτήσεις αυτών των δικτύων έχουν οδηγήσει στην ανάγκη για ανάπτυξη κατανεμημένων αλγορίθμων για την ανίχνευση σημάτων, την εκτίμηση παραμέτρων, και την ταξινόμηση δεδομένων σε πλειάδα εφαρμογών όπως η περιβαλλοντική παρακολούθηση και ο προσδιορισμός της θέσης αντικειμένων. Συνήθως, η τοπική επεξεργασία δεδομένων στους αισθητήρες απαιτεί χαμηλότερα ποσά ενέργειας από ό,τι θα καταναλώνονταν εάν όλοι οι αισθητήρες μετέδιδαν ασύρματα τα δεδομένα τους σε έναν κεντρικό κόμβο. Η ελαχιστοποίηση της κατανάλωσης ενέργειας σε ένα δίκτυο αισθητήρων είναι μείζονος σημασίας, επομένως απαιτείται τόσο η τοπική επεξεργασία δεδομένων όσο και η ανάπτυξη απλών αποδοτικών αλγορίθμων συνάθροισης και συμπίεσης, καθώς οι κόμβοι χαρακτηρίζονται από μικρή υπολογιστική δύναμη και περιορισμένη μνήμη. Στη παρούσα διδακτορική διατριβή μελετούμε και σχεδιάζουμε κατανεμημένους αλγόριθμους για την εκπαίδευση ταξινομητών Μηχανών Εδραίων Διανυσμάτων (SVMs), εκμεταλλευόμενοι την ιδιότητά τους ότι η επιφάνεια απόφασης κατασκευάζεται από ένα πολύ μικρό υποσύνολο των δεδομένων, τα λεγόμενα εδραία διανύσματα. Αρχικά, παρουσιάζουμε δύο αυξητικούς αλγόριθμους για κατανεμημένη εκπαίδευση ενός SVM, στους οποίους η ανανέωση της εκτίμησης του υπερεπιπέδου απόφασης πραγματοποιείται διαδοχικά στους κόμβους του δικτύου. Δείχνουμε με εκτενείς προσομοιώσεις ότι μόνο με ένα πέρασμα από κάθε κόμβο, καταλήγουμε σε μια καλή εκτίμηση του βέλτιστου ταξινομητή. Έπειτα, παρουσιάζουμε δύο επαναληπτικούς αλγόριθμους που βασίζονται σε τεχνικές "Gossip", ώστε να αποφεύγονται προβλήματα που προκαλούνται από μη προβλεπόμενες αλλαγές στην τοπολογία του δικτύου. Ο πρώτος προτεινόμενος αλγόριθμος επιτρέπει σε κάθε επανάληψη την ανανέωση του ταξινομητή με την διάδοση μόνο των εδραίων διανυσμάτων μέσω γειτονικών κόμβων, συγκλίνοντας σε μια προσέγγιση του βέλτιστου ταξινομητή. Σύμφωνα με τον δεύτερο αλγόριθμο, οι γειτονικοί κόμβοι ανταλλάσσουν τα δεδομένα τα οποία χαρακτηρίζουν μοναδικά τα κυρτά περιγράμματα που δημιουργούνται σε κάθε κόμβο. Ο αλγόριθμος αυτός εγγυάται σύγκλιση στον βέλτιστο ταξινομητή, με κόστος την αυξημένη πολυπλοκότητα που απαιτείται για τον προσδιορισμό των κυρτών περιγραμμάτων. Τέλος, θεωρούμε την εκπαίδευση ενός SVM ως ένα πρόβλημα βελτιστοποίησης υπό περιορισμούς και χρησιμοποιούμε στοιχεία από τη δυαδική θεωρία για να προτείνουμε ένα συστηματικό τρόπο για την βέλτιστη επιλογή των δεδομένων που πρέπει να ανταλλάσσουν οι κόμβοι του δικτύου ώστε να επέλθει κοινή σύγκλιση στη βέλτιστη λύση. Προτείνουμε μια συνάρτηση η οποία ταξινομεί τα δεδομένα κατά σειρά σπουδαιότητας στην διαδικασία εκμάθησης. Το πλήθος των δεδομένων που ανταλλάσσουν οι γειτονικοί κόμβοι καθορίζεται από ένα κατώφλι, ανάλογα με την επιθυμητή εξισορρόπηση ανάμεσα στην ακρίβεια της ταξινόμησης και την καταναλισκόμενη ενέργεια. Αποδεικνύουμε ότι υπάρχει ένα κατώφλι, ώστε ο προτεινόμενος αλγόριθμος να εγγυάται σύγκλιση στο βέλτιστο ταξινομητή. Ερευνούμε την επιρροή της τοπολογίας του δικτύου στην ταχύτητα σύγκλισης του αλγόριθμου και μελετούμε την απόδοση του αλγορίθμου με εκτεταμένες προσομοιώσεις.