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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Μετάβαση σε: πλοήγηση, αναζήτηση
Ανάλυση Ανεξάρτητων Συνιστωσών
Ταξινόμηση
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η κοινών Πληροφοριών (MMI) οικογένεια του ICA αλγόριθμου χρησιμοποιεί μετρήσεις σαν τις μετρήσεις Κουλμπακ-Λάιμπερ (Kullback-Leibler) απόκλιση και μέγιστη εντροπία. Η Μη-Γκαουσιανη του 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) και οι συνιστώσες από τον τυχαίο διάνυσμα s=(s_1,\ldots,s_n) . Ο σκοπός είναι ο μετασχηματισμός των παρατηρούμενων δεδομένων 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 διανύσματα και θέτοντας μια συνάρτηση κόστους η οποία είτε θα μεγιστοποιεί την μη γκαουσινότητα (nongaussianity) του υπολογισθέντος s_k = (w^T*x) η ελαχιστοποιώντας την κοινή πληροφορία. Σε μερικές περιπτώσεις μια 'a priori' γνώση της κατανομής πιθανοτήτων των πηγών μπορούν να χρησιμοποιηθούν στην συνάρτηση κόστους. Οι αρχικές πηγές μπορούν να ανακτηθούν πολλαπλασιάζοντας τα παρατηρούμενα σήματα x με τον ανάστροφο συμπτυγμένο πινάκα W=A^{-1}, γνωστό επίσης και σαν μη αναμιγμένο (unmixing ) πίνακα. Εδώ θεωρείται ότι ο συμπτυγμένος πινάκας είναι τετράγωνος (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 πρέπει να είναι πλήρης τάξεως, ώστε να υπάρχει ο αντίστροφος.

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

Μια ειδική μεταβλητή της Ανάλυση Ανεξάρτητων Συνιστωσών είναι η Δυαδική Ανάλυση Ανεξάρτητων Συνιστωσών, στην οποία και οι δυο πηγές σημάτων από τις οθόνες είναι δυαδικής μορφής και οι παρατηρήσεις από τις οθόνες είναι διαζευκτικά μείγματα των δυαδικών ανεξάρτητων πηγών. Το πρόβλημα έδειξε να μην έχει εφαρμογές σε πολλούς τομείς συμπεριλαμβανόμενων των κλινικών διαγνώσεων, των πολυ-δεσμων εκχωρησεων (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.

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

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