Introdução à Análise de Componentes Independentes e suas

Transcrição

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).
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
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 - 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 
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.
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).
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
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.
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).
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)
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
−∞
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
15
• Laplaciana
(ou exponencial dupla)
pdf:
1
 | x − µ |
f ( x) = exp −

2b
b 

Média
Variância= 2b2
16
• Uniforme:
 1

a≤ x≤b
f ( x) =  b − a
0 a > x ou x > b
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
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:
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).
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 !
21
• 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.
22
• 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.
23
• A curtose é igual a zero para distribuições Gaussianas, valores positivos
indicam super-gaussianidade e negativos, sub-gaussianidade.
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.
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.
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
^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
^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.
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.
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.
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
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.
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
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):
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.
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.
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
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.
40
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.
41
• Sistema online de filtragem de eventos do detector ATLAS:
Filtragem de
elétrons !!
42
Sinais de energia:
Formatação dos sinais
43
• 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.
44
• Compactação por PCA:
• Características realçadas pela ICA:
Elétron
Jato
45
A extração de características
por ICA proporcionou um
melhor desempenho de discriminação e consequentemente menor quantidade
de dados sem importancia
gravados
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
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
48

Introdução à Análise de Componentes Independentes e suas

Transcrição

Documentos relacionados

deserto sagrado 4d/3n

Gauss, Carl Friedrich (1777--1855) Gauss nasceu em Brunswick

08`6 J5 -

Decreto de Aprovação

Euler, Leonhard (1707--1783) Nascido na Basiléia, Suíça, Leonhard

Planejamento estratégico

A Teoria da Tect ica de Placas

pdf - Conarq

a introdução da informática na prática pedagógica dos professores

plano de governo

Junho 2015 - Associação de Amigos – Jardim Botânico

Estudos Avançados - CENTRO FILOSOFICO DO KUNG FU