Machine learning and data mining 

Machinelearning venues 
In signal processing, independent component analysis (ICA) is a computational method for separating a multivariate signal into additive subcomponents. This is done by assuming that the subcomponents are nonGaussian signals and that they are statistically independent from each other. ICA is a special case of blind source separation. A common example application is the "cocktail party problem" of listening in on one person's speech in a noisy room.
YouTube Encyclopedic

1/5Views:87 14817 681112 30233 0203 909

✪ Lecture 15  Machine Learning (Stanford)

✪ 19. Principal Component Analysis

✪ Example of Principal Component Analysis (PCA).mp4

✪ Principal Component Regression

✪ PCA vs ICA Quiz  Georgia Tech  Machine Learning
Transcription
Contents
Introduction
Independent component analysis attempts to decompose a multivariate signal into independent nonGaussian signals. As an example, sound is usually a signal that is composed of the numerical addition, at each time t, of signals from several sources. The question then is whether it is possible to separate these contributing sources from the observed total signal. When the statistical independence assumption is correct, blind ICA separation of a mixed signal gives very good results.^{[citation needed]} It is also used for signals that are not supposed to be generated by mixing for analysis purposes.
A simple application of ICA is the "cocktail party problem", where the underlying speech signals are separated from a sample data consisting of people talking simultaneously in a room. Usually the problem is simplified by assuming no time delays or echoes. Note that a filtered and delayed signal is a copy of a dependent component, and thus the statistical independence assumption is not violated.
An important note to consider is that if sources are present, at least observations (e.g. microphones if the observed signal is audio) are needed to recover the original signals. This constitutes the case where the matrix is square ( , where is the number of observed signals and is the number of source signals hypothesized by the model). Other cases of underdetermined () and overdetermined () have been investigated.
That the ICA separation of mixed signals gives very good results is based on two assumptions and three effects of mixing source signals. Two assumptions:
 The source signals are independent of each other.
 The values in each source signal have nonGaussian distributions.
Three effects of mixing source signals:
 Independence: As per assumption 1, the source signals are independent; however, their signal mixtures are not. This is because the signal mixtures share the same source signals.
 Normality: According to the Central Limit Theorem, the distribution of a sum of independent random variables with finite variance tends towards a Gaussian distribution.
Loosely speaking, a sum of two independent random variables usually has a distribution that is closer to Gaussian than any of the two original variables. Here we consider the value of each signal as the random variable.  Complexity: The temporal complexity of any signal mixture is greater than that of its simplest constituent source signal.
Those principles contribute to the basic establishment of ICA. If the signals we happen to extract from a set of mixtures are independent like sources signals, and have nonGaussian histograms or have low complexity like source signals, then they must be source signals.^{[2]}^{[3]}
Defining component independence
ICA finds the independent components (also called factors, latent variables or sources) by maximizing the statistical independence of the estimated components. We may choose one of many ways to define a proxy for independence, and this choice governs the form of the ICA algorithm. The two broadest definitions of independence for ICA are
 Minimization of mutual information
 Maximization of nonGaussianity
The MinimizationofMutual information (MMI) family of ICA algorithms uses measures like KullbackLeibler Divergence and maximum entropy. The nonGaussianity family of ICA algorithms, motivated by the central limit theorem, uses kurtosis and negentropy.
Typical algorithms for ICA use centering (subtract the mean to create a zero mean signal), whitening (usually with the eigenvalue decomposition), and dimensionality reduction as preprocessing steps in order to simplify and reduce the complexity of the problem for the actual iterative algorithm. Whitening and dimension reduction can be achieved with principal component analysis or singular value decomposition. Whitening ensures that all dimensions are treated equally a priori before the algorithm is run. Wellknown algorithms for ICA include infomax, FastICA, JADE, and kernelindependent component analysis, among others. In general, ICA cannot identify the actual number of source signals, a uniquely correct ordering of the source signals, nor the proper scaling (including sign) of the source signals.
ICA is important to blind signal separation and has many practical applications. It is closely related to (or even a special case of) the search for a factorial code of the data, i.e., a new vectorvalued representation of each data vector such that it gets uniquely encoded by the resulting code vector (lossfree coding), but the code components are statistically independent.
Mathematical definitions
Linear independent component analysis can be divided into noiseless and noisy cases, where noiseless ICA is a special case of noisy ICA. Nonlinear ICA should be considered as a separate case.
General definition
The data are represented by the observed random vector and the hidden components as the random vector The task is to transform the observed data using a linear static transformation as into an observable vector of maximally independent components measured by some function of independence.
Generative model
Linear noiseless ICA
The components of the observed random vector are generated as a sum of the independent components , :
weighted by the mixing weights .
The same generative model can be written in vector form as , where the observed random vector is represented by the basis vectors . The basis vectors form the columns of the mixing matrix and the generative formula can be written as , where .
Given the model and realizations (samples) of the random vector , the task is to estimate both the mixing matrix and the sources . This is done by adaptively calculating the vectors and setting up a cost function which either maximizes the nongaussianity of the calculated or minimizes the mutual information. In some cases, a priori knowledge of the probability distributions of the sources can be used in the cost function.
The original sources can be recovered by multiplying the observed signals with the inverse of the mixing matrix , also known as the unmixing matrix. Here it is assumed that the mixing matrix is square (). If the number of basis vectors is greater than the dimensionality of the observed vectors, , the task is overcomplete but is still solvable with the pseudo inverse.
Linear noisy ICA
With the added assumption of zeromean and uncorrelated Gaussian noise , the ICA model takes the form .
Nonlinear ICA
The mixing of the sources does not need to be linear. Using a nonlinear mixing function with parameters the nonlinear ICA model is .
Identifiability
The independent components are identifiable up to a permutation and scaling of the sources. This identifiability requires that:
 At most one of the sources is Gaussian,
 The number of observed mixtures, , must be at least as large as the number of estimated components : . It is equivalent to say that the mixing matrix must be of full rank for its inverse to exist.
Binary ICA
A special variant of ICA is binary ICA in which both signal sources and monitors are in binary form and observations from monitors are disjunctive mixtures of binary independent sources. The problem was shown to have applications in many domains including medical diagnosis, multicluster assignment, network tomography and internet resource management.
Let be the set of binary variables from monitors and be the set of binary variables from sources. Sourcemonitor connections are represented by the (unknown) mixing matrix , where indicates that signal from the ith source can be observed by the jth monitor. The system works as follows: at any time, if a source is active () and it is connected to the monitor () then the monitor will observe some activity (). Formally we have:
where is Boolean AND and is Boolean OR. Note that noise is not explicitly modelled, rather, can be treated as independent sources.
The above problem can be heuristically solved ^{[4]} by assuming variables are continuous and running FastICA on binary observation data to get the mixing matrix (real values), then apply round number techniques on to obtain the binary values. This approach has been shown to produce a highly inaccurate result.^{[citation needed]}
Another method is to use dynamic programming: recursively breaking the observation matrix into its submatrices and run the inference algorithm on these submatrices. The key observation which leads to this algorithm is the submatrix of where corresponds to the unbiased observation matrix of hidden components that do not have connection to the th monitor. Experimental results from ^{[5]} show that this approach is accurate under moderate noise levels.
The Generalized Binary ICA framework ^{[6]} introduces a broader problem formulation which does not necessitate any knowledge on the generative model. In other words, this method attempts to decompose a source into its independent components (as much as possible, and without losing any information) with no prior assumption on the way it was generated. Although this problem appears quite complex, it can be accurately solved with a branch and bound search tree algorithm or tightly upper bounded with a single multiplication of a matrix with a vector.
Methods for blind source separation
Projection pursuit
Signal mixtures tend to have Gaussian probability density functions, and source signals tend to have nonGaussian probability density functions. Each source signal can be extracted from a set of signal mixtures by taking the inner product of a weight vector and those signal mixtures where this inner product provides an orthogonal projection of the signal mixtures. The remaining challenge is finding such a weight vector. One type of method for doing so is projection pursuit.^{[7]}^{[8]}
Projection pursuit seeks one projection at a time such that the extracted signal is as nonGaussian as possible. This contrasts with ICA, which typically extracts M signals simultaneously from M signal mixtures, which requires estimating a M × M unmixing matrix. One practical advantage of projection pursuit over ICA is that fewer than M signals can be extracted if required, where each source signal is extracted from M signal mixtures using an Melement weight vector.
We can use kurtosis to recover the multiple source signal by finding the correct weight vectors with the use of projection pursuit.
The kurtosis of the probability density function of a signal, for a finite sample, is computed as
where is the sample mean of , the extracted signals. The constant 3 ensures that Gaussian signals have zero kurtosis, SuperGaussian signals have positive kurtosis, and SubGaussian signals have negative kurtosis. The denominator is the variance of , and ensures that the measured kurtosis takes account of signal variance. The goal of projection pursuit is to maximize the kurtosis, and make the extracted signal as nonnormal as possible.
Using kurtosis as a measure of nonnormality, we can now examine how the kurtosis of a signal extracted from a set of M mixtures varies as the weight vector is rotated around the origin. Given our assumption that each source signal is supergaussian we would expect:
 the kurtosis of the extracted signal to be maximal precisely when .
 the kurtosis of the extracted signal to be maximal when is orthogonal to the projected axes or , because we know the optimal weight vector should be orthogonal to a transformed axis or .
For multiple source mixture signals, we can use kurtosis and GramSchmidt Orthogonalization (GSO) to recover the signals. Given M signal mixtures in an Mdimensional space, GSO project these data points onto an (M1)dimensional space by using the weight vector. We can guarantee the independence of the extracted signals with the use of GSO.
In order to find the correct value of , we can use gradient descent method. We first of all whiten the data, and transform into a new mixture , which has unit variance, and . This process can be achieved by applying Singular value decomposition to ,
Rescaling each vector , and let . The signal extracted by a weighted vector is . If the weight vector w has unit length, that is , then the kurtosis can be written as:
The updating process for is:
where is a small constant to guarantee that converge to the optimal solution. After each update, we normalized , and set , and repeat the updating process till it converges. We can also use another algorithm to update the weight vector .
Another approach is using negentropy^{[9]} instead of kurtosis. Negentropy is a robust method for kurtosis, as kurtosis is very sensitive to outliers. The negentropy method are based on an important property of Gaussian distribution: a Gaussian variable has the largest entropy among all continuous random variables of equal variance. This is also the reason why we want to find the most nongaussian variables. A simple proof can be found in Differential entropy.
y is a Gaussian random variable of the same covariance matrix as x
An approximation for negentropy is
A proof can be found on page 131 in the book Independent Component Analysis written by Aapo Hyvärinen, Juha Karhunen, and Erkki Oja (They contribute great works to ICA)^{[10]} This approximation also suffers the same problem as kurtosis (sensitive to outliers). Other approaches were developed.^{[11]}
A choice of and are
 and
Based on infomax
Infomax ICA^{[12]} is essentially a multivariate, parallel version of projection pursuit. Whereas projection pursuit extracts a series of signals one at a time from a set of M signal mixtures, ICA extracts M signals in parallel. This tends to make ICA more robust than projection pursuit.^{[13]}
The projection pursuit method uses GramSchmidt orthogonalization to ensure the independence of the extracted signal, while ICA use infomax and maximum likelihood estimate to ensure the independence of the extracted signal. The NonNormality of the extracted signal is achieved by assigning an appropriate model, or prior, for the signal.
The process of ICA based on infomax in short is: given a set of signal mixtures and a set of identical independent model cumulative distribution functions(cdfs) , we seek the unmixing matrix which maximizes the joint entropy of the signals , where are the signals extracted by . Given the optimal , the signals have maximum entropy and are therefore independent, which ensures that the extracted signals are also independent. is an invertible function, and is the signal model. Note that if the source signal model probability density function matches the probability density function of the extracted signal , then maximizing the joint entropy of also maximizes the amount of mutual information between and . For this reason, using entropy to extract independent signals is known as infomax.
Consider the entropy of the vector variable , where is the set of signals extracted by the unmixing matrix . For a finite set of values sampled from a distribution with pdf , the entropy of can be estimated as:
The joint pdf can be shown to be related to the joint pdf of the extracted signals by the multivariate form:
where is the Jacobian matrix. We have , and is the pdf assumed for source signals , therefore,
therefore,
We know that when , is of uniform distribution, and is maximized. Since
where is the absolute value of the determinant of the unmixing matix . Therefore,
so,
since , and maximizing does not affect , so we can maximize the function
to achieve the independence of extracted signal.
If there are M marginal pdfs of the model joint pdf are independent and use the commonly supergaussian model pdf for the source signals , then we have
In the sum, given an observed signal mixture , the corresponding set of extracted signals and source signal model , we can find the optimal unmixing matrix , and make the extracted signals independent and nongaussian. Like the projection pursuit situation, we can use gradient descent method to find the optimal solution of the unmixing matrix.
Based on maximum likelihood estimation
Maximum likelihood estimation (MLE) is a standard statistical tool for finding parameter values (e.g. the unmixing matrix ) that provide the best fit of some data (e.g., the extracted signals ) to a given a model (e.g., the assumed joint probability density function (pdf) of source signals).^{[13]}
The ML "model" includes a specification of a pdf, which in this case is the pdf of the unknown source signals . Using ML ICA, the objective is to find an unmixing matrix that yields extracted signals with a joint pdf as similar as possible to the joint pdf of the unknown source signals .
MLE is thus based on the assumption that if the model pdf and the model parameters are correct then a high probability should be obtained for the data that were actually observed. Conversely, if is far from the correct parameter values then a low probability of the observed data would be expected.
Using MLE, we call the probability of the observed data for a given set of model parameter values (e.g., a pdf and a matrix ) the likelihood of the model parameter values given the observed data.
We define a likelihood function of :
This equals to the probability density at , since .
Thus, if we wish to find a that is most likely to have generated the observed mixtures from the unknown source signals with pdf then we need only find that which maximizes the likelihood . The unmixing matrix that maximizes equation is known as the MLE of the optimal unmixing matrix.
It is common practice to use the log likelihood, because this is easier to evaluate. As the logarithm is a monotonic function, the that maximizes the function also maximizes its logarithm . This allows us to take the logarithm of equation above, which yields the log likelihood function
If we substitute a commonly used highKurtosis model pdf for the source signals then we have
This matrix that maximizes this function is the maximum likelihood estimation.
History and background
The early general framework for independent component analysis was introduced by Jeanny Hérault and Bernard Ans from 1984,^{[14]} then rejoined by Christian Jutten from 1985^{[15]}^{[16]}^{[17]} and was most clearly stated by Pierre Comon in 1994.^{[18]} In 1995, Tony Bell and Terry Sejnowski introduced a fast and efficient ICA algorithm based on infomax, a principle introduced by Ralph Linsker in 1987.
There are many algorithms available in the literature which do ICA. A largely used one, including in industrial applications, is the FastICA algorithm, developed by Aapo Hyvärinen and Erkki Oja, which uses the kurtosis as cost function. Other examples are rather related to blind source separation where a more general approach is used. For example, one can drop the independence assumption and separate mutually correlated signals, thus, statistically "dependent" signals. Sepp Hochreiter and Jürgen Schmidhuber showed how to obtain nonlinear ICA or source separation as a byproduct of regularization (1999).^{[19]} Their method does not require a priori knowledge about the number of independent sources.
Applications
ICA can be extended to analyze nonphysical signals. For instance, ICA has been applied to discover discussion topics on a bag of news list archives.
Some ICA applications are listed below:^{[2]}
 optical Imaging of neurons^{[20]}
 neuronal spike sorting^{[21]}
 face recognition^{[22]}
 modelling receptive fields of primary visual neurons^{[23]}
 predicting stock market prices^{[24]}
 mobile phone communications ^{[25]}
 colour based detection of the ripeness of tomatoes^{[26]}
 removing artifacts, such as eye blinks, from EEG data.^{[27]}
 analysis of changes in gene expression over time in single cell RNAsequencing experiments.^{[28]}
 studies of the resting state network of the brain.^{[29]}
See also
Notes
 ^ Isomura, Takuya; Toyoizumi, Taro (2016). "A local learning rule for independent component analysis". Scientific Reports. 6: 28073. doi:10.1038/srep28073. PMC 4914970. PMID 27323661.
 ^ ^{a} ^{b} Stone, James V. (2004). Independent component analysis : a tutorial introduction. Cambridge, Massachusetts: MIT Press. ISBN 9780262693158.
 ^ Hyvärinen, Aapo; Karhunen, Juha; Oja, Erkki (2001). Independent component analysis (1st ed.). New York: John Wiley & Sons. ISBN 9780471221319.
 ^ Johan Himbergand 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.
 ^ Huy Nguyen and Rong Zheng, Binary Independent Component Analysis With or Mixtures, IEEE Transactions on Signal Processing, Vol. 59, Issue 7. (July 2011), pp. 3168–3181.
 ^ Painsky, Amichai; Rosset, Saharon; Feder, Meir (2014). Generalized Binary Independent Component Analysis. IEEE International Symposium on Information Theory (ISIT), 2014. pp. 1326–1330. doi:10.1109/ISIT.2014.6875048. ISBN 9781479951864.
 ^ James V. Stone(2004); "Independent Component Analysis: A Tutorial Introduction", The MIT Press Cambridge, Massachusetts, London, England; ISBN 0262693151
 ^ Kruskal, JB. 1969; "Toward a practical method which helps uncover the structure of a set of observations by finding the line transformation which optimizes a new "index of condensation", Pages 427–440 of: Milton, RC, & Nelder, JA (eds), Statistical computation; New York, Academic Press
 ^ Hyvärinen, Aapo; Erkki Oja (2000). "Independent Component Analysis:Algorithms and Applications". Neural Networks. 45. 13 (4–5): 411–430. CiteSeerX 10.1.1.79.7003. doi:10.1016/s08936080(00)000265. PMID 10946390.
 ^ Hyvärinen, Aapo; Karhunen, Juha; Oja, Erkki (2001). Independent component analysis (Reprint ed.). New York, NY: Wiley. ISBN 9780471405405.
 ^ Hyvärinen, Aapo (1998). "New approximations of differential entropy for independent component analysis and projection pursuit". Advances in Neural Information Processing Systems. 10: 273–279.
 ^ Bell, A. J.; Sejnowski, T. J. (1995). "An InformationMaximization Approach to Blind Separation and Blind Deconvolution", Neural Computation, 7, 11291159
 ^ ^{a} ^{b} James V. Stone (2004). "Independent Component Analysis: A Tutorial Introduction", The MIT Press Cambridge, Massachusetts, London, England; ISBN 0262693151
 ^ Hérault, J.; Ans, B. (1984). "Réseau de neurones à synapses modifiables : Décodage de messages sensoriels composites par apprentissage non supervisé et permanent". Comptes Rendus de l'Académie des Sciences, Série III. 299: 525–528.
 ^ Ans, B., Hérault, J., & Jutten, C. (1985). Architectures neuromimétiques adaptatives : Détection de primitives. Cognitiva 85 (Vol. 2, pp. 593597). Paris: CESTA.
 ^ Hérault, J., Jutten, C., & Ans, B. (1985). Détection de grandeurs primitives dans un message composite par une architecture de calcul neuromimétique en apprentissage non supervisé. Proceedings of the 10th Workshop Traitement du signal et ses applications (Vol. 2, pp. 10171022). Nice (France): GRETSI.
 ^ Hérault, J., & Jutten, C. (1986). Space or time adaptive signal processing by neural networks models. Intern. Conf. on Neural Networks for Computing (pp. 206211). Snowbird (Utah, USA).
 ^ Pierre Comon (1994) Independent component analysis, a new concept? http://www.ece.ucsb.edu/wcsl/courses/ECE594/594C_F10Madhow/comon94.pdf
 ^ Hochreiter, Sepp; Schmidhuber, Jürgen (1999). "Feature Extraction Through LOCOCODE" (PDF). Neural Computation. 11 (3): 679–714. doi:10.1162/089976699300016629. ISSN 08997667. PMID 10085426. Retrieved 24 February 2018.
 ^ Brown, GD; Yamada,S; Sejnowski, TJ (2001). "Independent components analysis at the neural cocktail party". Trends in Neurosciences. 24 (1): 54–63. doi:10.1016/s01662236(00)016830. PMID 11163888.
 ^ Lewicki, MS (1998). "Areview of methods for spike sorting: detection and classification of neural action potentials". Network: Computation in Neural Systems. 9 (4): 53–78. doi:10.1088/0954898X_9_4_001.
 ^ Barlett, MS (2001). Face image analysis by unsupervised learning. Boston: Kluwer International Series on Engineering and Computer Science.
 ^ Bell, AJ; Sejnowski, TJ (1997). "The independent components of natural scenes are edge filters". Vision Research. 37 (23): 3327–3338. doi:10.1016/s00426989(97)001211. PMC 2882863. PMID 9425547.
 ^ Back, AD; Weigend, AS (1997). "A first application of independent component analysis to extracting structure from stock returns". International Journal of Neural Systems. 8 (4): 473–484. doi:10.1142/s0129065797000458. PMID 9730022.
 ^ Hyvarinen, A, Karhunen,J & Oja,E (2001a). Independent component analysis. New York: John Wiley and Sons.
 ^ Polder, G; van der Heijen, FWAM (2003). "Estimation of compound distribution in spectral images of tomatoes using independent component analysis". Austrian Computer Society: 57–64.
 ^ Delorme, A; Sejnowski, T; Makeig, S (2007). "Enhanced detection of artifacts in EEG data using higherorder statistics and independent component analysis". NeuroImage. 34 (4): 1443–1449. doi:10.1016/j.neuroimage.2006.11.004. PMC 2895624. PMID 17188898.
 ^ Trapnell, C; Cacchiarelli, D; Grimsby, J (2014). "The dynamics and regulators of cell fate decisions are revealed by pseudotemporal ordering of single cells". Nature Biotechnology. 32 (4): 381–386. doi:10.1038/nbt.2859. PMC 4122333. PMID 24658644.
 ^ Kiviniemi, Vesa J.; Kantola, JuhaHeikki; Jauhiainen, Jukka; Hyvärinen, Aapo; Tervonen, Osmo (2003). "Independent component analysis of nondeterministic fMRI signal sources". NeuroImage. 19 (2): 253–260. doi:10.1016/S10538119(03)000971. PMID 12814576.
References
 Comon, Pierre (1994): "Independent Component Analysis: a new concept?", Signal Processing, 36(3):287–314 (The original paper describing the concept of ICA)
 Hyvärinen, A.; Karhunen, J.; Oja, E. (2001): Independent Component Analysis, New York: Wiley, ISBN 9780471405405 ( Introductory chapter )
 Hyvärinen, A.; Oja, E. (2000): "Independent Component Analysis: Algorithms and Application", Neural Networks, 13(45):411430. (Technical but pedagogical introduction).
 Comon, P.; Jutten C., (2010): Handbook of Blind Source Separation, Independent Component Analysis and Applications. Academic Press, Oxford UK. ISBN 9780123747266
 Lee, T.W. (1998): Independent component analysis: Theory and applications, Boston, Mass: Kluwer Academic Publishers, ISBN 0792382617
 Acharyya, Ranjan (2008): A New Approach for Blind Source Separation of Convolutive Sources  Wavelet Based Separation Using Shrinkage Function ISBN 3639077970 ISBN 9783639077971 (this book focuses on unsupervised learning with Blind Source Separation)
External links
 What is independent component analysis? by Aapo Hyvärinen
 Independent Component Analysis: A Tutorial by Aapo Hyvärinen
 A Tutorial on Independent Component Analysis
 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
 ICA toolbox Matlab tools for ICA with BellSejnowski, MolgedeySchuster and mean field ICA. Developed at DTU.
 Demonstration of the cocktail party problem
 EEGLAB Toolbox ICA of EEG for Matlab, developed at UCSD.
 FMRLAB Toolbox ICA of fMRI for Matlab, developed at UCSD
 MELODIC, part of the FMRIB Software Library.
 Discussion of ICA used in a biomedical shaperepresentation context
 FastICA, CuBICA, JADE and TDSEP algorithm for Python and more...
 Group ICA Toolbox and Fusion ICA Toolbox
 Tutorial: Using ICA for cleaning EEG signals