Introdução à Análise de Componentes Independentes e suas
Transcrição
Introdução à Análise de Componentes Independentes e suas
Introdução à Análise de Componentes Independentes e suas Aplicações Facilitador: Eduardo Simas [email protected] Sumário • Introdução • O Modelo da Análise de Componentes Independentes. • Breve histórico. • Independência estatística • Como estimar a independência? • Principais Algoritmos • Pré-processamento dos sinais • Extensões ao modelo básico • Aplicações • Conclusões • Bibliografia Introdução à ICA e Aplicações 2 Introdução • Em diversos problemas de processamento de sinais multidimensionais (MIMO – Multiple Inputs Multiple Outputs) é desejável encontrar uma transformação dos dados de modo que sua estrutura esteja mais acessível. • No caso mais geral não existem muitas informações a respeito dos dados e o aprendizado deve ser efetuado de modo não-supervisionado (cego). • Principais técnicas lineares de processamento de sinais MIMO: – Análise de Componentes Principais (PCA – Principal Component Analysis); – Análise de Fatores (Factor Analysis); – Análise de Componentes Independentes (ICA – Independent Component Analysis); – Separação Cega de Fontes (BSS – Blind Source Separation). Introdução à ICA e Aplicações 3 Introdução Processamento Cego: • O meio de propagação e os sinais originais são desconhecidos. • Apenas os sinais x são medidos. sN(t) Meio de propagação linear x1 (t) x2(t) ... ... s1(t) s2(t) xN(t) Sinais Observados (Medidos) Fontes de Sinal Introdução à ICA e Aplicações 4 Introdução - Aplicações Exemplos de sinais multidimensionais comuns: – Sinais de áudio (música, voz) gravados com mais de um microfone; – Sinais de imagem (fotografias, video); – Séries Temporais de Bolsas de Valores; – Sistemas sem fio com múltiplos usuários; – Sinais de inspeção acústica de máquinas; – Sinais de instrumentação de exames médicos (ECG, EEG, Ultra-som, etc). Introdução à ICA e Aplicações Introdução - Aplicações Cocktail-party problem: Magneto-Encefalograma Sistema sem-fio multi-usuário 6 O Modelo da ICA • O modelo da Análise de Componentes Independentes (ICA) assume que um conjunto de sinais observados (medidos) x = [x1 , ..., xN ]T é formado por uma combinação linear de fontes desconhecidas s = [s1 , ..., sN ]T : N xi = ∑ a j s j onde i = 1,..., N j =1 • Para N=2: x1 = a11s1 + a12 s2 x2 = a21s1 + a22 s2 Número de fontes igual ao de sinais observados • Na forma matricial pode-se escrever: sendo: a11 a12 A= a a 21 22 Matriz de mistura x1 a11 a12 s1 × x = a 2 21 a22 s2 Introdução à ICA e Aplicações x = As 7 O Modelo da ICA • O modelo da ICA não restringe a natureza dos sinais que podem ser variáveis aleatórias, imagens, ondas acústicas, sinais elétricos, etc. • O modelo anterior foi simplificado para uma visualização mais fácil, mas na prática, os sinais xi e si são vetores aleatórios ou seja: xi = xi (k) e si = si (k): x1 (k ) = a11s1 (k ) + a12 s2 (k ) x2 (k ) = a21s1 (k ) + a22 s2 (k ) x(k) = As(k) Onde k é o índice dos vetores • Se os sinais xi e si apresentam estrutura temporal (sinais dependentes do tempo), o índice k representa o tempo discreto. • Os modelos apresentados podem ser facilmente estendidos para N>2. Introdução à ICA e Aplicações 8 O Modelo da ICA • O objetivo para o qual o método foi inicialmente desenvolvido é recuperar as fontes si utilizando para isso apenas os sinais observados xi. • O modelo inverso é então definido por: N sˆ = Wx sˆi = ∑ w j x j onde i = 1,..., N j =1 Onde: W=A-1 e Sˆ ≅ S • Utilizada com esse objetivo a ICA é também chamada de Separação Cega de Sinais (BSS - Blind Signal Separation). Introdução à ICA e Aplicações 9 O Modelo da ICA • O problema proposto pela ICA se resume a encontrar a matriz de separação W, ou seus coeficientes wij. x1 x2 Transformação por ICA W s^ N xN A Fontes de Sinal ^s 1 ^s ... sN Meio de propagação linear ... ... s1 s2 Sinais Observados (Misturados) 2 Fontes Recuperadas Sendo Introdução à ICA e Aplicações Sˆ ≅ S 10 O Modelo da ICA • Uma forma de resolver o problema da ICA é assumir que as fontes de sinal são estatisticamente independentes (o que é uma consideração razoável e que, na prática, não precisa ser totalmente exata). • Então, a ICA (ou BSS) se resume a buscar uma transformação linear (representada pela matriz W) que torna os dados independentes. • Definição- Independência Estatística: diz-se que duas variáveis aleatórias são independentes se e somente se o conhecimento de uma delas não traz nenhuma informação a respeito da outra. • Um sinal musical e um ruído sonoro originado de uma máquina elétrica são exemplos de variáveis independentes. Introdução à ICA e Aplicações 11 O Modelo da ICA - Exemplo Fontes Sinais observados Fontes recuperadas Comparando s e y percebe-se que podem existir modificações no sinal e na amplitude (fator multiplicativo). Introdução à ICA e Aplicações 12 Breve Histórico da ICA • Início dos anos 80 - a técnica é desenvolvida (Hérault, Jutten & Ans). • Década de 1980 - a técnica fica restrita aos pesquisadores franceses. • 1989 - alguns trabalhos importantes são publicados (Cardoso e Comon). • Início dos anos 90 - é desenvolvida o algoritmo PCA não linear (Hyvarinen, Karhunen & Oja). • Meados dos anos 90 - o interesse geral em ICA cresceu após a publicação do trabalho de Bell & Sejnowski. • Janeiro de 1999 - é realizado o primeiro workshop internacional sobre o assunto. • 2004/2005 – cursos de ICA começam a ser ministrados em programas de pósgraduação em Engenharia Elétrica no Brasil (COPPE-UFRJ / UNICAMP) Introdução à ICA e Aplicações 13 Independência Estatística • Sendo px(x) e py(x) as funções densidade de probabilidade de x e y, pxy(x,y) a função de probabilidade conjunta e py/x(y/x) e px/y(x/y) as probabilidades condicionais pode-se escrever: p x , y ( x, y ) = p x / y ( x / y ) p y ( y ) = p y / x ( y / x ) p x ( x ) • Matematicamente diz-se que duas variáveis aleatórias x e y são independentes se e somente se : p x , y ( x, y ) = p x ( x ) p y ( y ) Ou seja: p x / y ( x / y ) = p x ( x), p y / x ( y / x) = p y ( y ) • OBS: A função densidade de probabilidade (pdf - probability density function) f(z) da variável aleatória z é tal que: b P(a < z < b) = ∫ f ( z )dz a ∞ ∫ f ( z)dz = 1 −∞ Introdução à ICA e Aplicações 14 Exemplos de funções densidade de probabilidade: • Gaussiana ou Normal pdf: ( x − µ )2 1 f ( x) = exp − 2 2σ σ 2π Onde: µ - média 1 N µ = ∑ xi N i =1 σ- desvio padrão (σ2 – variância) ( xi − µ ) 2 σ= N −1 Introdução à ICA e Aplicações 15 Exemplos de funções densidade de probabilidade: • Laplaciana (ou exponencial dupla) pdf: 1 | x − µ | f ( x) = exp − 2b b Média Variância= 2b2 Introdução à ICA e Aplicações 16 Exemplos de funções densidade de probabilidade: • Uniforme: 1 a≤ x≤b f ( x) = b − a 0 a > x ou x > b Introdução à ICA e Aplicações 17 Como buscar a independência estatística? • Conforme dito anteriormente, duas variáveis aleatórias x e y são independentes se e somente se: p x ,y ( x , y ) = p x ( x ) p y ( y ) • Em problemas onde as fontes a serem estimados (neste caso x e y) são desconhecidas não há como estimar diretamente suas pdf. • Dois princípios matemáticos são utilizados para estimar a independência estatística sem utilizar a condição acima: – Descorrelação não-linear; – Maximização da não-gaussianidade Introdução à ICA e Aplicações 18 Princípio 1: Descorrelação Não-linear • Uma condição equivalente à mostrada anteriormente pode ser obtida se para todas as funções não-lineares g(.) e h(.) vale a igualdade: E { g ( x )h( y )} = E { g ( x )} E { h( y )} onde ∞ E{x} = ∫ x p x ( x)dx é o operador esperança matemática. −∞ • O resultado acima é obtido de: Introdução à ICA e Aplicações 19 Princípio 1: Descorrelação Não-linear • Na prática não é possível testar todas as funções g(.) e h(.). • Em algoritmos que utilizam esse critério, algumas funções específicas são utilizadas. • O principal problema em utilizar o método de descorrelação não-linear para estimar as componentes independentes é a escolha adequada das funções não-lineares utilizadas. • Uma escolha inadequada pode levar o algoritmo à divergência (ou seja, não encontrar as componentes independentes). Introdução à ICA e Aplicações 20 Princípio 2: Maximização da Não-gaussianidade • Do teorema do limite central vem o segundo princípio utilizado para estimar as componentes independentes. • Teorema do limite central: “A pdf da soma de duas variáveis aleatórias é sempre mais próxima de uma distribuição Gaussiana do que as pdf das variáveis originais”. • Então, como os sinais observados são uma combinação linear das fontes, podese concluir que as fontes são as componentes com pdf mais distante da Gaussiana. • Esse princípio não pode ser aplicado se uma ou mais fontes forem Gaussianas ! Introdução à ICA e Aplicações 21 Princípio 2: Maximização da Não-gaussianidade • Para estimar se uma distribuição é ou não gaussiana, são utilizados parâmetros estatísticos como a divergência de Kullback-Leiber e a curtose: • A divergência (ou distância) de Kullback-Leiber mede a distância entre duas pdfs: C KL (Q, P) = ∫ Qx ( X ) log Qx ( X ) dx Px ( X ) • Se uma das distribuições (Qx ou Px) é escolhida como a Gaussiana, então as componentes independentes são obtidas pela maximização de CKL. • Como, em geral, as pdf das fontes são desconhecidas, foram propostos parâmetros equivalentes a CKL utilizando princípios da teoria da informação como a Entropia. Introdução à ICA e Aplicações 22 Princípio 2: Maximização da Não-gaussianidade • A curtose (kurt) é um parâmetro estatístico de quarta-ordem que fornece informações sobre a gaussianidade de uma variável aleatória. • A curtose pode ser facilmente estimada a partir dos dados (considerando média nula e variância unitária) usando: κurt = E{x 4 } − 3[ E{x 2 }]2 • O melhor estimador para E{x} a partir dos dados observados é a média de x. Introdução à ICA e Aplicações 23 Princípio 2: Maximização da Não-gaussianidade • A curtose é igual a zero para distribuições Gaussianas, valores positivos indicam super-gaussianidade e negativos, sub-gaussianidade. Introdução à ICA e Aplicações 24 Principais Algoritmos • Inúmeros algoritmos, utilizando um dos princípios mostrados, propostos para o problema da ICA. foram Boa precisão, porém o desempenho depende de parâmetros do algoritmo (i.e. taxa de aprendizagem) • Dentre as rotinas mais utilizadas pode-se citar: – Descorrelação Não-linear (Cichocki & Unbehauen, 1996) [Princ. 1]; – NL-PCA utilizando redes neurais (Karhunen et al., 1997) [Princ. 1]; Rápido e eficaz na estimação de um grande número de fontes – FastICA (Hyvarinen, 1999) [Princ. 2]; – JADE (Cardoso &Souloumiac, 1993) [Princ. 2]. Robusto a ambientes com ruído • Cada um dos algoritmos tem características próprias que o tornam mais indicados para uma dada aplicação. Introdução à ICA e Aplicações 25 Pré-Processamento • Para uma estimação acurada das componentes independentes, na maioria dos casos, os sinais observados precisam ser pré-processados. • As formas mais comuns de pré-processamento são: – Redução do ruído; – Redução de dimensão. • A realização de um pré-processamento adequado é importante para o bom desempenho dos algoritmos de ICA. Introdução à ICA e Aplicações 26 Pré-Processamento: Redução de Ruído • O modelo da ICA não considera ruído adicionado aos sinais observados. • A qualidade das componentes estimadas é deteriorada quanto maior for o nível de ruído. • Técnicas de redução de ruído como filtragem no domínio da freqüência e filtragem wavelet devem ser utilizadas para otimizar o desempenho dos algoritmos de ICA: xN Introdução à ICA e Aplicações ^s 1 ^s Transformação por ICA ... xN+rN Redução do ruído x1 x2 ... ... x1+r1 x2+r2 W ^sN 2 27 Pré-Processamento: Redução de Ruído Exemplo: • Sabendo-se que os sinais estão contaminados por ruído de alta freqüência, pode-se realizar uma filtragem passa-baixas antes da estimação das componentes independentes: xN Introdução à ICA e Aplicações ^s 1 ^s Transformação por ICA ... xN+rN Filtragem passa-baixas x1 x2 ... ... x1+r1 x2+r2 W ^sN 2 28 Pré-Processamento: Redução de Dimensão • Em aplicações práticas nem sempre o número N de fontes de sinal é conhecido. • Em alguns casos o número de sensores (K) pode ser maior que o de fontes, então para estimar corretamente as componentes independentes precisa-se eliminar a informação redundante. D (KxN) Transformação por ICA zN W (NxN) ^s 1 ^s 2 ... xK Redução de dimensão z1 z2 ... ... x1 x2 ^sN • A técnica mais utilizada para efetuar a redução de dimensão é a Análise de Componentes Principais (PCA - Principal Component Analysis), que retém as componentes de maior energia. Introdução à ICA e Aplicações 29 Pré-Processamento: Redução de Dimensão • Em alguns problemas onde a ICA é aplicada para extração de características, o uso da PCA pode ser prejudicial. • A PCA retém as componentes mais energéticas. • Nem sempre essas componentes carregam a informação desejada (que pode estar contida em componentes de baixa energia). • Nestes casos pode-se tentar o uso de outras formas de compactação como a Análise de Componentes Discriminantes. Introdução à ICA e Aplicações 30 Extensões ao modelo básico da ICA • O modelo básico da ICA é simplista , assumindo que as misturas são lineares e instantâneas (não há atraso de propagação). • Extensões ao modelo linear da ICA proporcionam uma descrição mais detalhada dos ambientes reais. • Entre as principais extensões pode-se mencionar: – ICA para misturas convolutivas; – ICA não-linear. Introdução à ICA e Aplicações 31 Extensões: Misturas Convolutivas • Na maioria das aplicações práticas, existem múltiplos caminhos de propagação, então os sinais observados são compostos por versões atrasadas das fontes: • O modelo convolutivo pode ser expresso por: Onde k é o número de atrasos n • E o modelo inverso: si (t ) = ∑∑ wikj x j (t − k ) j =1 k Introdução à ICA e Aplicações 32 Extensões: Misturas Convolutivas • Uma forma de solucionar o problema das misturas convolutivas é realizar a estimação da matriz de separação no domínio da freqüência (convolução temporal se reduz a multiplicações na freqüência): n S i (ω ) = ∑ Wij (ω ) X i (ω ) j =1 • Existem também algoritmos que operam do domínio do tempo. • Se o número de múltiplos caminhos for pequeno e seus coeficientes de baixa amplitude, o modelo sem atrasos pode ser utilizado sem perda significativa de precisão. • Caso isso não ocorra, serão necessários algoritmos específicos para o problema convolutivo. Introdução à ICA e Aplicações 33 Extensões: ICA Não-linear • Aplicada quando o meio de propagação tem características não lineares, o modelo não-linear da ICA pode ser representado por: x = F (s) onde F é um mapeamento não-linear, x = [x1 , ..., xN ]T o vetor de sinais observados e s = [s1 , ..., sN ]T as fontes independentes. sˆ = G (x) • O modelo inverso é expresso por: sendo G(.)=F-1(.) • As funções não-lineares G(.) são estimadas utilizando redes neurais treinadas para maximizar a independência das fontes : F x1 x2 xN Introdução à ICA e Aplicações Rede neural ^s 1 ^s 2 ... sN Meio de propagação não-linear ... ... s1 s2 ^sN 34 Extensões: ICA Não-linear • Na ICA não-linear as soluções não são únicas e é necessário fazer restrições aos mapeamentos F(.) e G(.), como é o caso do modelo pós não-linear (PNL): • No modelo PNL, os sinais observados são formados por uma combinação linear das fontes (matriz A), seguida de funções não-lineares aplicadas a cada componente intermediária ei (não existem funções utilizando mais de uma componente): Introdução à ICA e Aplicações 35 Aplicação: Análise acústica de máquinas rotativas • Dois acelerômetros (sensores de vibração) foram utilizados para medir os sinais acústicos de dois motores elétricos distintos. Fonte: Rhabi et al. “Blind Separation of rotating machine signals using Penalized Mutual Information criterion and Minimal Distortion Principle” . Mechanical Systems and Signal Processing 19 (2005) 1282–1292. Introdução à ICA e Aplicações 36 Aplicação: Análise acústica de máquinas rotativas Sinais medidos Fontes estimadas As freqüências marcadas indicam falhas nos motores, porém elas estavam presentes nos dois sinais. Após a ICA, houve a separação das freqüências nos sinais correspondentes. Introdução à ICA e Aplicações 37 Aplicação: Extração de características em séries temporais de ações em bolsas de valores • A ICA foi aplicada em um conjunto de séries temporais das cotações de 5 ações na bolsa de valores em 140 semanas. • O objetivo é extrair informações ocultas no conjunto de sinais que possam ser úteis para prever o comportamento da bolsa. Séries originais Componentes independentes Introdução à ICA e Aplicações 38 Aplicação: Extração de características em séries temporais de ações em bolsas de valores • Mudanças bruscas indicam ocorrência de feriados. • Tendência de variação lenta. • Tendências de variação mais rápida • As informações extraídas podem ser utilizadas para fazer previsões das cotações futuras, em termos de tendências e mudanças bruscas. Fonte: “Independent component analysis for financial time series”. Oja, E.; Kiviluoto, K.; Malaroiu, S.; IEEE Symposium on Adaptive System for Signal e Aplicações Processing Communications andIntrodução Control,à ICA 2000. 39 Aplicações: Extração de características em Física de Partículas • A ICA foi aplicada para extrair características de sinais de energia do detector de partículas ATLAS. • O ATLAS entrará em funcionamento em 2008, juntamente com o acelerador de partículas LHC no Centro Europeu de Pesquisa Nuclear (CERN). • O detector tem formato cilíndrico e é formado de uma seqüencia de camadas sensoras. • A taxa de eventos será muito elevada, mas as assinaturas de interesse serão raras. • Neste contexto é muito importante garantir a eficiência do sistema de seleção (filtragem) de eventos. Introdução à ICA e Aplicações 40 Aplicações: Extração de características em Física de Partículas Cada colisão 1,5MB de informação 40x106 colisões por segundo LHC em plena capacidade Resultado: aproximadamente 60TB/S • Considerando o cenário exposto: – não é possível armazenar tamanha quantidade de informação; – a filtragem de eventos deve ser realizada de modo online; – sob severas restrições de tempo de processamento. Introdução à ICA e Aplicações 41 Aplicações: Extração de características em Física de Partículas • Sistema online de filtragem de eventos do detector ATLAS: Filtragem de elétrons !! Introdução à ICA e Aplicações 42 Aplicações: Extração de características em Física de Partículas Sinais de energia: Formatação dos sinais Introdução à ICA e Aplicações 43 Aplicações: Extração de características em Física de Partículas • Neste trabalho, os sinais do detector (que totalizam 1000 componentes) são processados inicialmente por PCA para redução de dimensão de depois por ICA para extração de características. • O objetivo é obter informações relevantes para serem utilizadas no processo de discriminação de elétrons. • Os sinais de 7 camadas sensoras distintas são utilizadas no processo de discriminação. • Considerando que as características físicas das camadas são distintas o processamento dos sinais é feito de modo segmentado. • Uma rede neural é utilizada para realizar a classificação dos sinais. Introdução à ICA e Aplicações 44 Aplicações: Extração de características em Física de Partículas • Compactação por PCA: • Características realçadas pela ICA: Elétron Jato Introdução à ICA e Aplicações 45 Aplicações: Extração de características em Física de Partículas A extração de características por ICA proporcionou um melhor desempenho de discriminação e consequentemente menor quantidade de dados sem importancia gravados Introdução à ICA e Aplicações 46 Conclusões • A análise de componentes independentes tem se mostrado uma técnica muito eficiente tanto para a separação cega de sinais como para a extração de características. • Como a área de pesquisa ainda é recente, existe muito trabalho para ser realizado, tanto para melhorar o desempenho de métodos de estimação como para buscar novos campos de aplicação. OBS: em 2009 o congresso mundial de ICA (International Conference on Independent Component Analysis and Source Separation) será realizado em Parati-RJ, proporcionando um intercâmbio internacional e a consolidação da área no Brasil Introdução à ICA e Aplicações 47 Bibliografia Básica • A. Hyvarinen, J. Karhunen, and E. Oja, Independent Component Analysis. Wiley, 2001. • A. Cichocki and S. Amari, Adaptive Blind Signal and Image Processing. Willey, 2002. • A. Hyvarinen, “Fast and robust fixed-point algorithms for independent component analysis,” IEEE Transactions on Neural Networks, vol. 10, no. 3, pp. 626-634, 1999. • A. Hyvarinen and E. Oja, “Independent component analysis: Algorithms and applications,” Neural Networks, no. 13, pp. 411-430, 2000. • J.-F. Cardoso and A. Souloumiac, “Blind beamforming for non-gaussian signals,” IEE Proceedings- F, vol. 140, pp. 362-370, November 1993 Introdução à ICA e Aplicações 48