Ανάλυση ανεξάρτητων συνιστωσών

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Ανάλυση Ανεξάρτητων Συνιστωσών
Ταξινόμηση
Dewey 004
MSC2010 14-XX

H Aνάλυση ανεξάρτητων συνιστωσών (Independent Component Analysis) είναι μια υπολογιστική μέθοδος για το διαχωρισμό ενός πολυμεταβλητού σήματος σε προσθετικές υποσυνιστώσες υποθέτοντας την κοινή στατιστική ανεξαρτησία της μη-Γκαουσιανής πηγής σημάτων. Είναι μια ειδική περίπτωση τυφλού χωρισμού πηγής (blind source separation).

Εισαγωγή[Επεξεργασία | επεξεργασία κώδικα]

Όταν η υπόθεση ανεξαρτησίας είναι σωστή, ο τυφλός χωρισμός (με την Ανάλυση Ανεξάρτητων Συνιστωσών) ενός σύνθετου σήματος δίνει πολύ καλά αποτελέσματα. Επίσης χρησιμοποιείται για σήματα τα οποία υποτίθεται ότι δεν παράγονται από μίξη κάποιων σημάτων για τον σκοπό της Ανάλυσης Ανεξάρτητων Συνιστωσών. Μια απλή εφαρμογή Ανάλυσης Ανεξάρτητων Συνιστωσών είναι το πρόβλημα κοκτέιλ πάρτυ, όπου τα υποβόσκοντα σήματα ομιλίας διαχωρίζονται από δείγματα δεδομένων που αποτελούνται από ανθρώπους που μιλάνε ταυτόχρονα σε ένα δωμάτιο. Συνήθως το πρόβλημα απλοποιείται υποθέτοντας μη χρονικές καθυστερήσεις ή ηχώ. Μια σημαντική παρατήρηση για σκέψη είναι όταν Ν πηγές είναι παρούσες, χρειάζονται τουλάχιστον Ν παρατηρητές (π.χ. μικρόφωνα) για να πάρουμε τα πραγματικά σήματα. Αυτό αποτελεί την τετράγωνη περίπτωση (J = D, οπού D είναι η εισερχόμενη διάσταση δεδομένων και J η διάσταση του μοντέλου). Έχουν επίσης ερευνηθεί και περιπτώσεις όπου έχουμε υποκαθορισμό (J <  D) ή υπερκαθορισμό (J > D).

Καθορίζοντας την συνιστώσα ανεξαρτησίας[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση ανεξάρτητων συνιστωσών βρίσκει τις ανεξάρτητες συνιστώσες (όπως παράγοντες, λανθάνουσες μεταβλητές, πηγές) μεγιστοποιώντας τη στατιστική ανεξαρτησία των εκτιμώμενων συνιστωσών. Μπορούμε να επιλέξουμε μεταξύ πολλών τρόπων καθορισμού της ανεξαρτησίας, και αυτή η επιλογή διέπει τη μορφή του ICA αλγόριθμου. Οι δύο πιο γνωστοί καθορισμοί της ανεξαρτησίας για το ICA είναι

1) Ελαχιστοποίηση της Κοινής Πληροφορίας

2) Μεγιστοποίηση της μη-Κανονικότητας

Η ελαχιστοποίηση των Mη κοινών Πληροφοριών (Minimization of Mutual Information, MMI) αποτελεί μια οικογένεια του ICA αλγόριθμου ποι χρησιμοποιεί μετρήσεις όπως η Απόκλιση Κουλμπακ-Λάιμπερ (Kullback-Leibler) και η μέγιστη εντροπία. Η οικογένεια της Μη-Κανονικότητας (non-Gaussianity) του ICA αλγόριθμου, έχοντας παρακινηθεί από το κεντρικό οριακό θεώρημα, χρησιμοποιεί κύρτωση και αρνητική εντροπία.

Τυπικοί αλγόριθμοι για την ανάλυση ανεξάρτητων συνιστωσών χρησιμοποιούν κεντροποίηση, θορυβοποίηση (συνήθως με την αποσύνθεση ιδιοτιμών (eigenvalue decomposition)), και μείωση διάστασης (dimensionality reduction) ως βήματα προεπεξεργασίας με σκοπό να απλουστευτεί και να μειωθεί η πολυπλοκότητα του προβλήματος για πραγματικούς επαναληπτικούς αλγορίθμους. Η θορυβοποίηση και η μείωση διάστασης μπορούν να επιτευχθούν με την ανάλυση βασικών συνιστωσών (principal component analysis) ή με την Αποσύνθεση μοναδικής τιμής (singular value decomposition). Η θορυβοποίηση εξασφαλίζει την 'a priori' ίση μεταχείριση όλων των διαστάσεων πριν την εκτέλεση του αλγορίθμου. Στους αλγορίθμους ανάλυσης ανεξάρτητων συνιστωσών συμπεριλαμβάνονται οι infomax, FastICA και JADE, αλλά υπάρχουν κι άλλοι. Γενικά, η ανάλυση ανεξάρτητων συνιστωσών δεν μπορεί να εντοπίσει τον πραγματικό αριθμό των πηγαίων σημάτων, τη μοναδική σωστή σειρά των πηγαίων σημάτων, ούτε τη σωστή κλιμάκωση (συμπεριλαμβανόμενου του προσήμου) των πηγαίων σημάτων.

Η ανάλυση ανεξάρτητων συνιστωσών είναι σημαντική για τον τυφλό διαχωρισμό σήματος και έχει πολλές πρακτικές εφαρμογές. Είναι στενά συνδεδεμένη με την έρευνα για την παραγωγή ενός παραγοντικού κώδικα (factorial code) των δεδομένων, δηλ. μια καινούρια διανυσματική αναπαράσταση κάθε διανύσματος δεδομένων έτσι ώστε αυτό να κωδικοποιείται μοναδικά από το αντίστοιχο διάνυσμα κώδικα (code vector) (loss-free coding), αλλά οι συνιστώσες του κώδικα να είναι στατιστικά ανεξάρτητες.

Μαθηματικοί ορισμοί[Επεξεργασία | επεξεργασία κώδικα]

Η γραμμική ανάλυση ανεξάρτητων συνιστωσών μπορεί να διαιρεθεί σε αθόρυβες και θορυβώδεις περιπτώσεις, όπου οι αθόρυβες ICA είναι ειδικές περιπτώσεις των θορυβωδών ICA. Η μη γραμμική ICA θα πρέπει να θεωρείται ξεχωριστή περίπτωση.

Γενικοί ορισμοί[Επεξεργασία | επεξεργασία κώδικα]

Τα δεδομένα αναπαριστώνται από το τυχαίο διάνυσμα (random vector) x=(x_1,\ldots,x_m)^T και οι συνιστώσες από το τυχαίο διάνυσμα s=(s_1,\ldots,s_n)^T . Ο σκοπός είναι ο μετασχηματισμός των παρατηρούμενων δεδομένων x, χρησιμοποιώντας ένα γραμμικό στατικό μετασχηματισμό W της μορφής

 
s = W x
 \,

για τη μεγιστοποίηση των ανεξάρτητων συνιστωσών s μετρουμένων από κάποια συνάρτηση ανεξαρτησίας F(s_1,\ldots,s_n).

Γενετήριο μοντέλο[Επεξεργασία | επεξεργασία κώδικα]

Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών χωρίς θόρυβο[Επεξεργασία | επεξεργασία κώδικα]

Οι συνιστώσες x_i του παρατηρουμένου τυχαίου διανύσματος x=(x_1,\ldots,x_m)^T παράγονται ως άθροισμα των ανεξάρτητων συνιστωσών s_k, k=1,\ldots,n:

x_i = a_{i,1} s_1 + \ldots + a_{i,k} s_k + \ldots + a_{i,n} s_n

σταθμισμένων από τα βάρη μίξης a_{i,k}.

Το ίδιο μοντέλο παραγωγής μπορεί να γραφεί σε διανυσματική μορφή ως x=\sum_{k=1}^{n} s_k a_k, οπού το παρατηρούμενο τυχαίο διάνυσμα x παρίσταται από τα διανύσματα βάσης a_k=(a_{1,k},\ldots,a_{m,k})^T. Η βάση διανυσμάτων a_k σχηματίζει τις στήλες του πίνακα μίξης A=(a_1,\ldots,a_n) και η γενετήρια φόρμουλα μπορεί να γραφτεί ως x=As, όπου s=(s_1,\ldots,s_n)^T.

Δοθέντων του μοντέλου και των συσχετισμών (δείγματα) x_1,\ldots,x_N του τυχαίου διανύσματος x, ο στόχος είναι να εκτιμηθούν ο πίνακας μίξης A και οι πηγές s. Αυτό γίνεται με προσαρμοστικό υπολογισμό των διανυσμάτων w και θέτοντας μια συνάρτηση κόστους η οποία είτε θα μεγιστοποιεί τη μη κανονικότητα (non-gaussianity) του υπολογισθέντος s_k = (w^T*x) ή θα ελαχιστοποιεί την κοινή πληροφορία. Σε μερικές περιπτώσεις μια 'a priori' γνώση της κατανομής πιθανοτήτων των πηγών μπορούν να χρησιμοποιηθούν στη συνάρτηση κόστους.

Οι αρχικές πηγές μπορούν να ανακτηθούν πολλαπλασιάζοντας τα παρατηρούμενα σήματα x με τον αντίστροφο πίνακα μίξης W=A^{-1}. Εδώ θεωρείται ότι ο συμπτυγμένος πίνακας είναι τετράγωνος (n=m). Αν ο αριθμός των διανυσμάτων βάσης είναι μεγαλύτερος από τη διάσταση των παρατηρούμενων διανυσμάτων, n>m, ο σκοπός υπερκαλύπτεται άλλα και πάλι το πρόβλημα είναι επιλύσιμο με ψευδοαντιστροφή.

Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών με θόρυβο[Επεξεργασία | επεξεργασία κώδικα]

Με την επιπρόσθετη υπόθεση του μηδενικού μέσου και τον ασυσχετιστικο Γκαουσιανό θόρυβο n\sim N(0,\operatorname{diag}(\Sigma)), η Ανάλυση Ανεξάρτητων Συνιστωσών παίρνει τη μορφή x=As+n.

Μη Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών[Επεξεργασία | επεξεργασία κώδικα]

Η μίξη των πηγών δε χρειάζεται να είναι γραμμική. Χρησιμοποιώντας μια μη γραμμική συμπτυγμένη συνάρτηση f(\cdot|\theta) με παραμέτρους \theta το μη γραμμικό ICA μοντέλο είναι x=f(s|\theta)+n.

Ταυτοποίηση[Επεξεργασία | επεξεργασία κώδικα]

Οι ανεξάρτητες συνιστώσες είναι αναγνωρίσιμες σε μια μετάθεση και κλίμακα των πηγών. Αυτή η αναγνώριση απαιτεί:

  • Το πολύ μια πηγή s_k να είναι Γκαουσιανή.
  • Ο αριθμός των παρατηρούμενων μίξεων, m, πρέπει να είναι τουλάχιστον τόσο μεγάλος όσο το πλήθος των εκτιμώμενων συνιστωσών n: m \ge n. Ισοδύναμα, θα πρέπει ο πίνακας μίξης A να έχει πλήρη βαθμό (rank), ώστε να υπάρχει ο αντίστροφος.

Δυαδική ανάλυση ανεξάρτητων συνιστωσών[Επεξεργασία | επεξεργασία κώδικα]

Μια ειδική παραλλαγή της Ανάλυσης Ανεξάρτητων Συνιστωσών είναι η Δυαδική Ανάλυση Ανεξάρτητων Συνιστωσών, στην οποία τόσο οι πηγές σημάτων όσο και οι παρατηρητές είναι δυαδικής μορφής, ενώ παράλληλα οι παρατηρητές είναι διαζευκτικές μίξεις ανεξάρτητων δυαδικών πηγών. Το πρόβλημα αυτό αποδείχτηκε ότι έχει εφαρμογή σε πολλούς τομείς, συμπεριλαμβανομένων των κλινικών διαγνώσεων, της πολυ-συσταδικής ανάθεσης (multi-cluster assignment), των δικτυακών τομογράφων και της διαχείρισης πόρων διαδικτύου.

Έστω {x_1, x_2, \ldots, x_m} το σύνολο των δυαδικών μεταβλητών από m παρατηρητές και {y_1, y_2, \ldots, y_n} το σύνολο των δυαδικών μεταβλητών από n πηγές. Οι συνδέσεις μεταξύ πηγών και παρατηρητών παρίστανται από τον (άγνωστο) πίνακα μίξης G, όπου g_{ij} = 1 και δείχνει ότι το σήμα από την i-στή πηγή μπορεί να παρατηρηθεί από τον j-στό παρατηρητή. Το σύστημα δουλεύει ως ακολούθως: οποιαδήποτε στιγμή, αν μια πηγή i είναι ενεργή (y_i=1) και συνδεθεί σε έναν παρατηρητή j (g_{ij}=1) τοτε ο παρατηρητής j θα δώσει κάποια δραστηριότητα (x_j=1). Τυπικά έχουμε:


x_i = \bigvee_{j=1}^{n}{(g_{ij}\wedge y_j)}, i = 1, 2, \ldots, m,

οπού \wedge είναι το λογικό AND και \vee είναι το λογικό OR. Σημειώστε ότι ο θόρυβος δεν μοντελοποιείται ρητά ενώ μπορεί κάλλιστα να αντιμετωπιστεί σαν ανεξάρτητες πηγές.

Το παραπάνω πρόβλημα μπορεί να λυθεί με ευριστικό τρόπο [1] υποθέτοντας ότι οι μεταβλητές είναι συνεχείς και τρέχοντας τον αλγόριθμο FastICA σε δυαδικά δεδομένα παρατήρησης ώστε να πάρουμε τον πίνακα μίξης G (πραγματικές τιμές) και εφαρμόζοντας έπειτα round number τεχνικές στο G ώστε να λάβουμε τις δυαδικές τιμές. Αυτή η προσέγγιση έδειξε ότι δίνει πολύ ανακριβή αποτελέσματα.

Μια άλλη μέθοδος είναι να χρησιμοποιήσουμε δυναμικό προγραμματισμό: σπάμε αναδρομικά τον παρατηρούμενο πίνακα X σε υποπίνακες και τρέχουμε ένα συμπερασματικό αλγόριθμο σε αυτούς τους υποπινακες. Η βασική παρατήρηση η οποία οδηγεί σε αυτό τον αλγόριθμο είναι ο X^0 του X όπου x_{ij} = 0, \forall j αντιστοιχεί στον χωρίς βάρυ παρατηρούμενο πινάκα των κρυμμένων συστατικών τα οποία δεν έχουν σύνδεση με την i-στη οθόνη. Πειραματικά αποτελέσματα από το [2] δείχνουν ότι αυτή η προσέγγιση είναι ακριβής κάτω από μέτρια επίπεδα θορύβου.

Εφαρμογές[Επεξεργασία | επεξεργασία κώδικα]

Η ανάλυση ανεξάρτητων συνιστωσών μπορεί να επεκταθεί στην ανάλυση μη φυσικών σημάτων (non-physical signals). Για παράδειγμα η ανάλυση ανεξάρτητων συνιστωσών, έχει εφαρμοστεί να ανακαλύψει τα θέματα συζητήσεων σε μια λίστα φακέλων.

Δείτε επίσης[Επεξεργασία | επεξεργασία κώδικα]

Πηγές[Επεξεργασία | επεξεργασία κώδικα]

  1. Johan Himberg and Aapo Hyvärinen, Independent Component Analysis For Binary Data: An Experimental Study, Proc. Int. Workshop on Independent Component Analysis and Blind Signal Separation (ICA2001), San Diego, California, 2001.
  2. Huy Nguyen and Rong Zheng, Binary Independent Component Analysis With or Mixtures, IEEE Transactions of Signal Processing, Vol. 59, Issue 7. (July 2011), pp. 3168–3181.

Αναφορές[Επεξεργασία | επεξεργασία κώδικα]

Εξωτερικοί σύνδεσμοι[Επεξεργασία | επεξεργασία κώδικα]