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

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

Εισαγωγή

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

Καθορίζοντας την συνιστώσα ανεξαρτησίας

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

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

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

Η ελαχιστοποίηση των Μη κοινών Πληροφοριών (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) ${\displaystyle x=(x_{1},\ldots ,x_{m})^{T}}$ και οι συνιστώσες από το τυχαίο διάνυσμα ${\displaystyle s=(s_{1},\ldots ,s_{n})^{T}}$ . Ο σκοπός είναι ο μετασχηματισμός των παρατηρούμενων δεδομένων ${\displaystyle x}$, χρησιμοποιώντας ένα γραμμικό στατικό μετασχηματισμό W της μορφής

${\displaystyle s=Wx\,}$

για τη μεγιστοποίηση των ανεξάρτητων συνιστωσών ${\displaystyle s}$ μετρουμένων από κάποια συνάρτηση ανεξαρτησίας ${\displaystyle F(s_{1},\ldots ,s_{n})}$.

Γενετήριο μοντέλο

Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών χωρίς θόρυβο

Οι συνιστώσες ${\displaystyle x_{i}}$ του παρατηρουμένου τυχαίου διανύσματος ${\displaystyle x=(x_{1},\ldots ,x_{m})^{T}}$ παράγονται ως άθροισμα των ανεξάρτητων συνιστωσών ${\displaystyle s_{k}}$, ${\displaystyle k=1,\ldots ,n}$:

${\displaystyle x_{i}=a_{i,1}s_{1}+\ldots +a_{i,k}s_{k}+\ldots +a_{i,n}s_{n}}$

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

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

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

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

Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών με θόρυβο

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

Μη Γραμμική Ανάλυση Ανεξάρτητων Συνιστωσών

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

Ταυτοποίηση

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

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

Δυαδική ανάλυση ανεξάρτητων συνιστωσών

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

Έστω ${\displaystyle {x_{1},x_{2},\ldots ,x_{m}}}$ το σύνολο των δυαδικών μεταβλητών από ${\displaystyle m}$ παρατηρητές και ${\displaystyle {y_{1},y_{2},\ldots ,y_{n}}}$ το σύνολο των δυαδικών μεταβλητών από ${\displaystyle n}$ πηγές. Οι συνδέσεις μεταξύ πηγών και παρατηρητών παρίστανται από τον (άγνωστο) πίνακα μίξης ${\displaystyle G}$, όπου ${\displaystyle g_{ij}=1}$ και δείχνει ότι το σήμα από την i-στή πηγή μπορεί να παρατηρηθεί από τον j-στό παρατηρητή. Το σύστημα δουλεύει ως ακολούθως: οποιαδήποτε στιγμή, αν μια πηγή ${\displaystyle i}$ είναι ενεργή (${\displaystyle y_{i}=1}$) και συνδεθεί σε έναν παρατηρητή ${\displaystyle j}$ (${\displaystyle g_{ij}=1}$) τοτε ο παρατηρητής ${\displaystyle j}$ θα δώσει κάποια δραστηριότητα (${\displaystyle x_{j}=1}$). Τυπικά έχουμε:

${\displaystyle x_{i}=\bigvee _{j=1}^{n}{(g_{ij}\wedge y_{j})},i=1,2,\ldots ,m,}$

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

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

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

Εφαρμογές

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

Δείτε επίσης

• Blind deconvolution
• Blind signal separation (BSS)
• Factor analysis
• Factorial codes
• Hilbert spectrum
• Image processing
• Non-negative matrix factorization (NMF)
• Nonlinear dimensionality reduction
• Principal component analysis (PCA)
• Projection pursuit
• Redundancy reduction
• Signal processing
• Singular value decomposition (SVD)
• Varimax rotation

Πηγές

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.

Αναφορές

• Pierre Comon (1994): Independent Component Analysis: a new concept?, Signal Processing, Elsevier, 36(3):287–314 (The original paper describing the concept of ICA)
• A. Hyvärinen, J. Karhunen, E. Oja (2001): Independent Component Analysis, New York: Wiley, ISBN 978-0-471-40540-5
  • Introductory chapter
• A. Hyvärinen, E. Oja (2000): Independent Component Analysis: Algorithms and Application, Neural Networks, 13(4-5):411-430, 2000. (Technical but pedagogical introduction).

• J.V. Stone, (2004): Independent Component Analysis: A Tutorial Introduction

• J.V. Stone, (2005): A Brief Introduction to Independent Component Analysis in Encyclopedia of Statistics in Behavioral Science, Volume 2, pp. 907–912, Editors Brian S. Everitt & David C. Howell, John Wiley & Sons, Ltd, Chichester, 2005 ISBN 978-0-470-86080-9
• T.-W. Lee (1998): Independent component analysis: Theory and applications, Boston, Mass: Kluwer Academic Publishers, ISBN 0 7923 8261 7
• Ranjan Acharyya (editors) (2008): A New Approach for Blind Source Separation of Convolutive Sources ISBN 3639077970 ISBN 978-3639077971 (this book focuses on unsupervised learning with Blind Source Separation)

Εξωτερικοί σύνδεσμοι

• What is independent component analysis? by Aapo Hyvärinen
• Independent Component Analysis: A Tutorial by Aapo Hyvärinen
• Nonlinear ICA, Unsupervised Learning, Redundancy Reduction by Jürgen Schmidhuber, with links to papers
• FastICA as a package for Matlab, in R language, C++
• ICALAB Toolboxes for Matlab, developed at RIKEN
• High Performance Signal Analysis Toolkit provides C++ implementations of FastICA and Infomax
• Free software for ICA by JV Stone.
• ICA toolbox Matlab tools for ICA with Bell-Sejnowski, Molgedey-Schuster and mean field ICA. Developed at DTU.
• Demonstration of the cocktail party problem Αρχειοθετήθηκε 2010-03-13 στο Wayback Machine.
• EEGLAB Toolbox ICA of EEG for Matlab, developed at UCSD.
• FMRLAB Toolbox ICA of fMRI for Matlab, developed at UCSD
• Discussion of ICA used in a biomedical shape-representation context
• FastICA, CuBICA, JADE and TDSEP algorithm for Python and more...
• Group ICA Toolbox and Fusion ICA Toolbox