|
}}
H '''Aνάλυση ανεξάρτητων συνιστωσών''' (''Independent Component Analysis'') είναι μια υπολογίσιμηυπολογιστική μέθοδος για τοντο διαχωρισμό ενός πολυμετάβλητουπολυμεταβλητού σήματος σε προσθετικές υποσυνιστώσες υποθέτοντας την κοινή [[στατιστική ανεξαρτησία]] της μη-Γκαουσιανής πηγής σημάτων. Είναι μια ειδική περίπτωση [[τυφλού χωρισμού πηγής]] (blind source separation).
== Εισαγωγή ==
Όταν η υπόθεση ανεξαρτησίας είναι σωστή, ο τυφλός χωρισμός (με την Ανάλυση Ανεξάρτητων Συνιστωσών) ενός σύνθετου σήματος δίνει πολύ καλά αποτελέσματα. Επίσης χρησιμοποιείται για σήματα τα οποία υποτίθεται ότι δεν παράγονται από μίξη κάποιων σημάτων για τον σκοπό της Ανάλυσης Ανεξάρτητων Συνιστωσών. Μια απλή εφαρμογή Ανάλυσης Ανεξάρτητων Συνιστωσών είναι το [[πρόβλημα κοκτέιλ πάρτυ]], όπου τα υποβόσκονυποβόσκοντα σήματα ομιλίας είναι χωρισμέναδιαχωρίζονται από τα δείγματα δεδομένων που αποτελούνται από ανθρώπους που μιλάνε ταυτόχρονα σε ένα δωμάτιο. Συνήθως το πρόβλημα απλοποιείται υποθέτοντας μη χρονικές καθυστερήσεις ή ηχώ. Μια σημαντική παρατήρηση για σκέψη είναι όταν ''Ν'' πηγές είναι παρούσες, χρειάζονται τουλάχιστον ''Ν'' παρατηρήσειςπαρατηρητές (π.χ. μικρόφωνα) χρειάζονται για να πάρουμε τα πραγματικά σήματα. Αυτό Αυτάαποτελεί αποτελούντην τετράγωνη υπόθεσηπερίπτωση (''J'' = ''D'', οπού ''D'' είναι η εισερχόμενη διάσταση δεδομένων και ''J'' είναι η διάσταση του μοντέλου). ΆλλεςΈχουν υποθέσειςεπίσης πουερευνηθεί και περιπτώσεις όπου έχουμε υποκαθορίζονταιυποκαθορισμό (''J'' < ''D'') καιή υπερκαθορίζονταιυπερκαθορισμό (''J'' > ''D'') ερευνούνται.
== Καθορίζοντας την συνιστώσα ανεξαρτησίας ==
Η ανάλυση ανεξάρτητων συνιστωσών βρίσκει τις ανεξάρτητες συνιστώσες (όπως παράγοντες, λανθάνουσες μεταβλητές, πηγές) μεγιστοποιώντας τηντη στατιστική ανεξαρτησία των εκτιμώμενων συνιστωσών . Μπορούμε να επιλέξουμε μεταξύ πολλών τρόπων καθορισμού της ανεξαρτησίας, και αυτή η επιλογή διέπει τη μορφή του ICA αλγόριθμου. Οι δύο πιο γνωστοί καθορισμοί της ανεξαρτησίας για το ICA είναι
1) Ελαχιστοποίηση της [[Κοινής Πληροφορίας]]
2) Μεγιστοποίηση της μη-Γκαουσιανής ▼
▲2) Μεγιστοποίηση της μη- ΓκαουσιανήςΚανονικότητας
Η ελαχιστοποίηση των -Mη κοινών Πληροφοριών (MMI) οικογένεια του ICA αλγόριθμου χρησιμοποιεί μετρήσεις σαν τις μετρήσεις [[Κουλμπακ-Λάιμπερ]] (Kullback-Leibler) απόκλιση και μέγιστη εντροπία. Η Μη-Γκαουσιανη του ICA αλγόριθμου, έχοντας παρακινηθεί από το [[κεντρικό οριακό θεώρημα]], χρησιμοποιεί [[κύρτωση]] και [[αρνητική εντροπία]]. ▼
▲Η ελαχιστοποίηση των -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, αλλά υπάρχουν και άλλοι επίσης. ▼Γενικά, η ανάλυση ανεξάρτητων συνιστωσών δεν μπορεί να βρεθεί από τον πραγματικό αριθμό των πηγών σημάτων, μια μοναδική σωστή σειρά των πηγών σημάτων, ούτε από την σωστή διαβάθμιση (συμπεριλαμβανόμενου του σήματος) των πηγών σημάτων.
▲ΤυπικήΤυπικοί αλγόριθμοι για την ανάλυση ανεξάρτητων συνιστωσών χρησιμοποιείχρησιμοποιούν κεντροποίηση, [[θορυβοποίηση]] (συνήθως με την [[αποσύνθεση ιδιοτιμών]] (eigenvalue decomposition)), και [[μείωση διάστασης]] (dimensionality reduction) σανως βήματα προεπεξεργασίας με σκοπό να απλουστευτεί και να μειωθεί η πολυπλοκότητα του προβλήματος για πραγματικούς επαναληπτικούς αλγορίθμους. Η θορυβοποίηση και η μείωση διάστασης μπορούν να επιτευχθούν με την [[ανάλυση βασικών συνιστωσών]] (principal component analysis) ή με την [[Αποσύνθεση μοναδικής τιμής]] (singular value decomposition). Η θορυβοποίηση καθίσταεξασφαλίζει ότιτην όλες'a οιpriori' διαστάσειςίση χειρίζονταιμεταχείριση ίσαόλων 'aτων priori'διαστάσεων πριν τρέξειτην οεκτέλεση αλγόριθμοςτου αλγορίθμου. ΑλγόριθμοιΣτους γιααλγορίθμους την ανάλυσηανάλυσης ανεξάρτητων συνιστωσών συμπεριλαμβάνουνσυμπεριλαμβάνονται τουςοι infomax, FastICA , και JADE, αλλά υπάρχουν καικι άλλοι . Γενικά, η ανάλυση ανεξάρτητων συνιστωσών δεν μπορεί να εντοπίσει τον πραγματικό αριθμό των πηγαίων σημάτων, τη μοναδική σωστή σειρά των πηγαίων σημάτων, ούτε τη σωστή κλιμάκωση (συμπεριλαμβανόμενου του προσήμου) των πηγαίων επίσηςσημάτων.
Η ανάλυση ανεξάρτητων συνιστωσών, είναι σημαντική για τον [[τυφλό διαχωρισμό σήματος]] και έχει πολλές πρακτικές εφαρμογές. Είναι στενά συνδεμένη με (η ακόμη με μια ειδική περίπτωση) την ερεύνα για ένα [[παραγοντικό κώδικα]] (factorial code) δεδομένων π.χ, μια καινούρια αναπαράστασης της διανυσματικής εκτίμησης των κάθε διανυσμάτων δεδομένων έτσι ώστε να κωδικοποιείται μοναδικά από το αποτέλεσμα του κώδικα διανύσματος (code vector) (loss-free coding), αλλά οι συνιστώσες του κώδικα να είναι στατιστικά ανεξάρτητες. ▼
▲Η ανάλυση ανεξάρτητων συνιστωσών , είναι σημαντική για τον [[τυφλό διαχωρισμό σήματος]] και έχει πολλές πρακτικές εφαρμογές. Είναι στενά συνδεμένησυνδεδεμένη με (ητην ακόμηέρευνα με μια ειδική περίπτωση)για την ερεύνα γιαπαραγωγή έναενός [[παραγοντικό κώδικα|παραγοντικού κώδικα]] (factorial code) των δεδομένων , πδηλ. χ, μια καινούρια αναπαράστασηςδιανυσματική της διανυσματικής εκτίμησης τωναναπαράσταση κάθε διανυσμάτωνδιανύσματος δεδομένων έτσι ώστε αυτό να κωδικοποιείται μοναδικά από το αντίστοιχο αποτέλεσμα τουδιάνυσμα κώδικα διανύσματος (code vector) (loss-free coding), αλλά οι συνιστώσες του κώδικα να είναι στατιστικά ανεξάρτητες.
== Μαθηματικοί ορισμοί ==
ΓραμμικήΗ ανεξαρτησίαγραμμική ανάλυση ανεξάρτητων συνιστωσών μπορεί να διαιρεθεί σε αθόρυβες και θορυβώδεις περιπτώσεις, οπούόπου οι αθόρυβες ICA είναι ειδικές περιπτώσεις των θόρυβωνθορυβωδών ICA. ΜηΗ γραμμικέςμη γραμμική ICA θα πρέπει να θεωρείται ξεχωριστή υπόθεσηπερίπτωση.
=== Γενικοί ορισμοί ===
Τα δεδομένα αναπαριστώνται από το [[τυχαίο διάνυσμα]] (random vector) <math>x=(x_1,\ldots,x_m)^T</math> και οι συνιστώσες από τοντο τυχαίο διάνυσμα <math>s=(s_1,\ldots,s_n)^T</math> . Ο σκοπός είναι ο μετασχηματισμός των παρατηρούμενων δεδομένων <math>x</math>, χρησιμοποιώντας ένα γραμμικό στατικό μετασχηματισμό ''W'' σαντης μορφής
:<math>
s = W x
\,</math>,
μεγια τη μεγιστοποίηση των ανεξάρτητων συνιστωσών <math>s</math> μετρουμένων από κάποια συνάρτηση ανεξαρτησίας <math>F(s_1,\ldots,s_n)</math> ανεξαρτησίας.
=== Γενετήριο μοντέλο ===
==== Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών χωρίς θόρυβο ====
Οι συνιστώσες <math>x_i</math> του παρατηρουμένου τυχαίου διανύσματος <math>x=(x_1,\ldots,x_m)^T</math> παράγονται σανως άθροισμα των ανεξάρτητων συνιστωσών <math>s_k</math>, <math>k=1,\ldots,n</math>:
<math>x_i = a_{i,1} s_1 + \ldots + a_{i,k} s_k + \ldots + a_{i,n} s_n</math>
σταθμισμένων από τηντα μίξηβάρη βαρώνμίξης <math>a_{i,k}</math>.
Το ίδιο μοντέλο παραγωγής μπορεί να γραφεί σε διανυσματική μορφή ως <math>x=\sum_{k=1}^{n} s_k a_k</math>, οπού το παρατηρούμενο τυχαίο διάνυσμα <math>x</math> παρίσταται από τα διανύσματα βάσης <math>a_k=(a_{1,k},\ldots,a_{m,k})^T</math>. Η βάση διανυσμάτων <math>a_k</math> σχηματίζεται απόσχηματίζει τις στήλες τωντου συμπτυγμένωνπίνακα πινάκωνμίξης <math>A=(a_1,\ldots,a_n)</math> και η γενετήρια φόρμουλα μπορεί να γραφτεί σανως <math>x=As</math>, όπου <math>s=(s_1,\ldots,s_n)^T</math>. ▼
Δοθέντων του μοντέλου και των συσχετισμών (δείγματα) <math>x_1,\ldots,x_N</math> του τυχαίου διανύσματος <math>x</math>, ο στόχος είναι να εκτιμηθούν , ο συμπτυγμένος πινάκαςπίνακας μίξης <math>A</math> και οι πηγές <math>s</math>. Αυτό γίνεται προσαρμόζονταςμε υπολογιστικάπροσαρμοστικό ταυπολογισμό των διανυσμάτων <math>w</math> διανύσματα και θέτοντας μια συνάρτηση κόστους η οποία είτε θα μεγιστοποιεί τηντη μη γκαουσινότητακανονικότητα ( nongaussianitynon-gaussianity) του υπολογισθέντος <math>s_k = (w^T*x)</math> ηή θα ελαχιστοποιώνταςελαχιστοποιεί την κοινή πληροφορία. Σε μερικές περιπτώσεις μια 'a priori' γνώση της κατανομής πιθανοτήτων των πηγών μπορούν να χρησιμοποιηθούν στηνστη συνάρτηση κόστους. ▼το ίδιο μοντέλο παραγωγής μπορεί να γραφεί σε διανυσματική μορφή σαν
<math>x=\sum_{k=1}^{n} s_k a_k</math>,
οπού το παρατηρούμενο τυχαίο διάνυσμα <math>x</math> παρίσταται από τα διανύσματα βάσης
▲<math>a_k=(a_{1,k},\ldots,a_{m,k})^T</math>.Η βάση διανυσμάτων <math>a_k</math> σχηματίζεται από τις στήλες των συμπτυγμένων πινάκων <math>A=(a_1,\ldots,a_n)</math> και η γενετήρια φόρμουλα μπορεί να γραφτεί σαν <math>x=As</math>, όπου <math>s=(s_1,\ldots,s_n)^T</math>.
Οι αρχικές πηγές μπορούν να ανακτηθούν πολλαπλασιάζοντας τα παρατηρούμενα σήματα <math>x</math> με τον ανάστροφοαντίστροφο συμπτυγμένοπίνακα πινάκαμίξης <math>W=A^{-1}</math> , γνωστό επίσης και σαν μη αναμιγμένο (unmixing ) πίνακα. Εδώ θεωρείται ότι ο συμπτυγμένος πινάκαςπίνακας είναι τετράγωνος (<math>n=m</math>). Αν ο αριθμός των διανυσμάτων βάσης είναι μεγαλύτερος από τηντη διάσταση των παρατηρούμενων διανυσμάτων, <math>n>m</math>, ο σκοπός υπερκαλύπτεται άλλα και πάλι το πρόβλημα είναι επιλύσιμο με την ψευδοαντιστροφή. ▼▲Δοθέντων του μοντέλου και των συσχετισμών (δείγματα) <math>x_1,\ldots,x_N</math> του τυχαίου διανύσματος <math>x</math>, ο στόχος είναι να εκτιμηθούν, ο συμπτυγμένος πινάκας <math>A</math> και οι πηγές <math>s</math>. Αυτό γίνεται προσαρμόζοντας υπολογιστικά τα <math>w</math> διανύσματα και θέτοντας μια συνάρτηση κόστους η οποία είτε θα μεγιστοποιεί την μη γκαουσινότητα (nongaussianity) του υπολογισθέντος <math>s_k = (w^T*x)</math> η ελαχιστοποιώντας την κοινή πληροφορία. Σε μερικές περιπτώσεις μια 'a priori' γνώση της κατανομής πιθανοτήτων των πηγών μπορούν να χρησιμοποιηθούν στην συνάρτηση κόστους.
▲Οι αρχικές πηγές μπορούν να ανακτηθούν πολλαπλασιάζοντας τα παρατηρούμενα σήματα <math>x</math> με τον ανάστροφο συμπτυγμένο πινάκα <math>W=A^{-1}</math>, γνωστό επίσης και σαν μη αναμιγμένο (unmixing ) πίνακα. Εδώ θεωρείται ότι ο συμπτυγμένος πινάκας είναι τετράγωνος (<math>n=m</math>). Αν ο αριθμός των διανυσμάτων βάσης είναι μεγαλύτερος από την διάσταση των παρατηρούμενων διανυσμάτων, <math>n>m</math>, ο σκοπός υπερκαλύπτεται άλλα και πάλι είναι επιλύσιμο με την ψευδοαντιστροφή.
==== Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών με θόρυβο ====
Με την προστιθέμενηεπιπρόσθετη υπόθεση του μηδενικού μέσου και τον ασυσχετιστικο Γκαουσιανό θόρυβο <math>n\sim N(0,\operatorname{diag}(\Sigma))</math>, η Ανάλυση Ανεξάρτητων Συνιστωσών παίρνει τη μορφή <math>x=As+n</math>.
==== Μη Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών ====
Η σύμπτυξημίξη των πηγών δενδε χρειάζεται να είναι γραμμική. Χρησιμοποιώντας μια μη γραμμική συμπτυγμένη συνάρτηση <math>f(\cdot|\theta)</math> με παραμέτρους <math>\theta</math> το μη γραμμικό ICA μοντέλο είναι <math>x=f(s|\theta)+n</math>.
<math>x=f(s|\theta)+n</math>.
=== Ταυτοποίηση ===
Οι ανεξάρτητες συνιστώσες είναι αναγνωρίσιμες σε μια μετάθεση και κλίμακα των πηγών. Αυτή η αναγνώριση απαιτεί:
*Το πολύ μια πηγή <math>s_k</math> να είναι ΓκαουσιανηΓκαουσιανή.
*Ο αριθμός των παρατηρούμενων μίξεων, <math>m</math>, πρέπει να είναι τουλάχιστον τόσο μεγάλος όσο το πλήθος των εκτιμώμενων συνιστωσών <math>n</math>: <math>m \ge n</math>. ΕίναιΙσοδύναμα, τοθα ίδιο να λέμε ότιπρέπει ο συμπτυγμένοςπίνακας πινάκαςμίξης <math>A</math> πρέπει να είναιέχει πλήρη πλήρηςβαθμό τάξεως(rank), ώστε να υπάρχει ο αντίστροφος.
== Δυαδική ανεξαρτησία ανάλυση ανεξάρτητων συνιστωσών ==
Μια ειδική μεταβλητήπαραλλαγή της ΑνάλυσηΑνάλυσης Ανεξάρτητων Συνιστωσών είναι η Δυαδική Ανάλυση Ανεξάρτητων Συνιστωσών, στην οποία καιτόσο οι δυο πηγές σημάτων απόόσο τιςκαι οθόνεςοι παρατηρητές είναι δυαδικής μορφής, καιενώ παράλληλα οι παρατηρήσεις από τις οθόνεςπαρατηρητές είναι διαζευκτικάδιαζευκτικές μείγματαμίξεις τωνανεξάρτητων δυαδικών ανεξάρτητων πηγών. Το πρόβλημα έδειξεαυτό νααποδείχτηκε μηνότι έχει εφαρμογέςεφαρμογή σε πολλούς τομείς, συμπεριλαμβανόμενωνσυμπεριλαμβανομένων των κλινικών διαγνώσεων, τωντης πολυ-δεσμωνσυσταδικής εκχωρησεωνανάθεσης (multi-cluster assignment), των [[δικτυακών τομογράφων]] και της [[διαχείριση πόρων διαδικτύου|διαχείρισης πόρων διαδικτύου]].
ΑφήνουμεΈστω <math>{x_1, x_2, \ldots, x_m}</math> να τεθούντο σύνολο δυαδικέςτων δυαδικών μεταβλητέςμεταβλητών από <math>m</math> οθόνεςπαρατηρητές και <math>{y_1, y_2, \ldots, y_n}</math> νατο τεθούνσύνολο απότων δυαδικέςδυαδικών μεταβλητέςμεταβλητών από <math>n</math> πηγές. Οι Πηγές-οθόνες συνδέσεις μεταξύ πηγών και παρατηρητών παρίστανται από τον (άγνωστο) συμπτυγμένοπίνακα μίξης πινάκα <math>G</math>, οπούόπου <math>g_{ij} = 1</math> και δείχνει ότι το σήμα από την ''i''-στηστή πηγή μπορεί να παρατηρηθεί από τηντον ''j''-στηστό οθόνηπαρατηρητή. Το σύστημα δουλεύει όπωςως ακολούθως: οποιαδήποτε στιγμή, αν μια πηγή <math>i</math> είναι ενεργή (<math>y_i=1</math>) και συνδεθεί σε μιαέναν οθόνηπαρατηρητή <math>j</math> (<math>g_{ij}=1</math>) τοτε ηο οθόνηπαρατηρητής <math>j</math> θα δώσει κάποια δραστηριότητα (<math>x_j=1</math>). Τυπικά έχουμε:
:<math>
</math>
οπού <math>\wedge</math> είναι το λογικό AND και <math>\vee</math> είναι το λογικό OR. Σημειώστε ότι ο θόρυβος δεν μοντελοποιείται ρητά ενώ μπορεί κάλλιστα να χειριστείαντιμετωπιστεί σαν ανεξαρτησίαανεξάρτητες πηγήπηγές.
Το παραπάνω πρόβλημα μπορεί εμπειρικά να λυθεί με ευριστικό τρόπο <ref name="Hyvärinen">[[Johan Himberg and Aapo Hyvärinen]], ''[http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8895 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.</ref> υποθέτοντας ότι οι μεταβλητές είναι συνεχόμενεςσυνεχείς και τρέχοντας τον αλγόριθμο FastICA σε δυαδικά παρατηρούμενα δεδομένα, παρατήρησης ώστε να πάρουμε τον συμπτυγμένοπίνακα μίξης πινάκα <math>G</math> (πραγματικές τιμές ), τότεκαι εφαρμόζουμεεφαρμόζοντας έπειτα round number τεχνικές στο <math>G</math> ώστε να συμπεριλάβουμελάβουμε τις δυαδικές τιμές. Αυτή η προσέγγιση έδειξε ότι δίνει πολύ ανακριβή αποτελέσματα.
Μια άλλη μέθοδος είναι να χρησιμοποιήσουμε δυναμικό προγραμματισμό: σπάμε αναδρομικά σπάζοντας τον παρατηρούμενο πινάκαπίνακα <math>X</math> σε υποπινακεςυποπίνακες και να τρέξουμετρέχουμε ένα συμπερασματικό αλγόριθμο σε αυτούς τους υποπινακες. Η βασική παρατήρηση η οποία οδηγεί σε αυτό τον αλγόριθμο είναι ο <math>X^0</math> του <math>X</math> όπου <math>x_{ij} = 0, \forall j</math> αντιστοιχεί στον χωρίς βάρυ παρατηρούμενο πινάκα των κρυμμένων συστατικών τα οποία δεν έχουν σύνδεση με την i-στη οθόνη. Πειραματικά αποτελέσματα από το <ref name="Huyna">[[Huy Nguyen and Rong Zheng]], ''[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5753957 Binary Independent Component Analysis With or Mixtures]'', IEEE [[Transactions of Signal Processing]], Vol. 59, Issue 7. (July 2011), pp. 3168–3181.</ref> δείχνουν ότι αυτή η προσέγγιση είναι ακριβής κάτω από μέτρια επίπεδα θορύβου.
== Εφαρμογές ==
| 