24
1 Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN ANÁLISE DE COMPONENTES INDEPENDENTES Tutorial Nielsen Castelo Damasceno 1 INTRODUÇÃO Em linhas gerais, podemos dizer que a motivação do uso de Análise de Componentes Independentes (ACI) ou do inglês: Independent Componente Analysis (ICA) é o BSS (Blind Source Separation ou Separação Cega de Fontes) (HYVÄRINEN, OJA, 1999). Todavia, vamos utilizar ACI e ICA, doravante, para representar a mesma entidade. Sobretudo, um dos problemas típicos investigados pela técnica de separação cega de fontes é motivado por um problema chamado cocktail party” ou separação de sinais de áudio. Considere duas pessoas conversando em uma sala fechada utilizando sensores (microfones) para capturar suas vozes. Esta situação é representada na Figura 1. O problema consiste em separar os sinais captados pelos microfones sabendo que os sinais estão agora correlacionados. A particularidade da separação cega de fontes perante as outras técnicas de filtragens é que, nesse caso, não precisamos conhecer precisamente os sinais de fontes (HYVÄRINEN, 1999a). Figura 1: O problema do cocktail-party. O problema do cocktail-party pode ser representado da seguinte forma: x = 2 1 x x , A= 22 21 12 11 a a a a e s = 2 1 s s , ou seja,

Implementação ICA - Separação Cega de Fontes

Embed Size (px)

DESCRIPTION

Artigo que trata sobre a separação cega de fontes e a ICA

Citation preview

Page 1: Implementação ICA - Separação Cega de Fontes

1

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

ANÁLISE DE COMPONENTES INDEPENDENTES

Tutorial

Nielsen Castelo Damasceno

1 INTRODUÇÃO

Em linhas gerais, podemos dizer que a motivação do uso de Análise de

Componentes Independentes (ACI) ou do inglês: Independent Componente Analysis

(ICA) é o BSS (Blind Source Separation ou Separação Cega de Fontes)

(HYVÄRINEN, OJA, 1999). Todavia, vamos utilizar ACI e ICA, doravante, para

representar a mesma entidade. Sobretudo, um dos problemas típicos investigados

pela técnica de separação cega de fontes é motivado por um problema chamado

“cocktail party” ou separação de sinais de áudio.

Considere duas pessoas conversando em uma sala fechada utilizando

sensores (microfones) para capturar suas vozes. Esta situação é representada na

Figura 1. O problema consiste em separar os sinais captados pelos microfones

sabendo que os sinais estão agora correlacionados. A particularidade da separação

cega de fontes perante as outras técnicas de filtragens é que, nesse caso, não

precisamos conhecer precisamente os sinais de fontes (HYVÄRINEN, 1999a).

Figura 1: O problema do cocktail-party.

O problema do cocktail-party pode ser representado da seguinte forma: x =

2

1

x

x, A=

2221

1211

aa

aae s =

2

1

s

s, ou seja,

Page 2: Implementação ICA - Separação Cega de Fontes

2

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

=x

=

2

1

2221

1211

2

1

s

s

aa

aa

x

x (1)

ou pode-se reescrever a Equação 1 utilizando a notação matricial, que tornar-se-á:

Asx = (2)

Denota-se x pelo vetor aleatório cujos elementos representam as misturas

ou sensores, a matriz A com elementos ija representam a atenuação ou

amplificação sobre o vetor aleatório s que representam o sinal de fontes 1s e 2s .

Por enquanto, deixemos de lado qualquer momento de atraso e outros

fatores extras a partir de nosso modelo simplificado de mistura. Como ilustração,

considere os sinais representados na Figura 2 e 3.

Figura 2: Dois sinais do discurso original.

Os sinais do discurso original é semelhante aos sinais representado na

Figura 2 e as misturas poderiam se parecer com os sinais na Figura 3. Nos gráficos

acima as coordenadas abscissas representam o número de amostra do sinal em

cada período de tempo e a ordenada representa a amplitude do sinal. O problema

consiste em recuperar os dados na Figura 2 utilizando apenas os dados da Figura 3.

0 2 4 6 8 10 12 14 16 18 20-0.02

-0.01

0

0.01

0.02

Sin

al d

e fo

nte

1 (A

mpl

itude

)

Tempo (ms)

0 2 4 6 8 10 12 14 16 18 20-0.04

-0.02

0

0.02

Sin

al d

e fo

nte

2 (A

mpl

itude

)

Tempo (ms)

Page 3: Implementação ICA - Separação Cega de Fontes

3

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Figura 3: Sinais dos discursos misturados.

Na verdade, se soubéssemos os parâmetros ��� poderíamos resolver o

sistema na Equação 1 pelos métodos clássicos. O ponto, porém, é que não

sabemos o valor de ���, de forma que o problema se torna consideravelmente difícil.

Uma abordagem para resolver este problema seria usar alguma informação

estatística sobre as propriedades dos sinais ����� para estimar a todos. Na verdade,

e talvez surpreendentemente, verifica-se que ela seja suficiente para presumir que

����� e ���� a cada instante de tempo � são estatisticamente independentes. A

técnica recentemente desenvolvida conhecida como ICA pode ser usado para

estimar os valores de ��� baseado nas informações de sua independência, o que

permite recuperar ou estimar o sinal original ����� e ���� a partir de suas misturas

���� e ���.

A Figura 4 representa os sinais de fontes estimados por ICA usando

abordagem PCA (KUN; CHAN, 2006).

Na Figura 5 ilustra um diagrama esquemático do problema, onde um conjunto

de sinais de fontes são submetidos à ação de um sistema misturador, cujas saídas

correspondem a misturas de tais fontes. Devemos de alguma forma, projetar um

sistema separador que seja capaz de estimar as fontes, ou seja, inverter a ação do

0 2 4 6 8 10 12 14 16 18 20-10

-5

0

5x 10

-3

Mis

tura

1 (

Am

plitu

de)

Tempo (ms)

0 2 4 6 8 10 12 14 16 18 20-0.02

-0.01

0

0.01M

istu

ra 2

(A

mpl

itude

)

Tempo (ms)

Page 4: Implementação ICA - Separação Cega de Fontes

4

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

sistema misturador. Este problema é dito cego em razão da falta de informação que

temos sobre as misturas e as fontes.

Figura 4: Sinais de fonte estimados a partir das misturas.

Figura 5: Diagrama esquemático do problema de separação cega linear.

Podemos também representar de forma simples o processo de misturas das

fontes pela seguinte expressão:

x ( ) Fn = ( s ( )n , s ( )1−n ,L , s ( )Ln − , ( )nr ) (3)

onde o ( )⋅F corresponde a ação do sistema misturador, L é associado às memórias

(amostras atrasadas) no sistema e o vetor r representa o ruído presente nas fontes.

Um sistema misturador é dito linear se o mapeamento ( )⋅F atende o principio da

superposição, caso contrário é dito não linear.

0 2 4 6 8 10 12 14 16 18 20-2

-1

0

1

2

Sin

al e

stim

ado

1 (A

mpl

itude

)

Tempo (ms)

0 2 4 6 8 10 12 14 16 18 20-4

-2

0

2

Sin

al e

stim

ado

2 (A

mpl

itude

)

Tempo (ms)

Page 5: Implementação ICA - Separação Cega de Fontes

5

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Nas situações em que o sistema misturador depende das amostras passadas

(L > 0) é dito que o sistema misturador é convolutivo (com memória). Entretanto, há

situações em que (L = 0) o sistema é chamado de instantâneo (COMON, 1994).

Em outras situações onde o número de sensores podem ser maiores que o

número de sinais de fontes, tem-se o caso sobre determinado. Analogamente,

temos o caso subdeterminado quando o número de sensores é menor que os sinais

de fontes.

2 RELAÇÃO ENTRE ICA E PCA

O ICA procura transformar a mistura de sinais num número de componentes

independentes (ICs), sem reduzir as dimensões da mistura. Mas, quando é

necessário a redução da informação, então efetua-se um pré-processamento da

mistura com PCA (Principal Componentes Analysis).

A principal diferença entre o ICA e o PCA é que o PCA usa, unicamente, a

estatística de 2ª ordem (média e variância), enquanto o ICA utiliza a estatística de

ordens superiores (kurtosis). Por isso, o PCA é usado para variáveis Gaussianas

que são de estatística de 2ª ordem. Mas, como a maioria dos sinais são não-

gassianos e com ordens estatísticas elevadas, logo o ICA é uma melhor opção.

3 INDEPENDÊNCIA E NÃO-CORRELAÇÃO

ICA consiste em recuperar os sinais originais a partir de uma mistura. Um

princípio bastante utilizado para determinar ou inferir nas misturas tem sido a

independência estatística, ou seja, o valor de qualquer um dos componentes não

fornece nenhuma informação sobre os valores dos outros componentes.

Normalmente, uma distribuição de probabilidade é caracterizada em termos

de sua função de densidade ao invés de cdf (função de distribuição cumulativa ou

do inglês: cumulative distribution function). Formalmente, a função de densidade de

probabilidade é obtida derivando cdf. ICA está intimamente ligado à independência

estatística. Matematicamente, a independência estatística é definida em termos de

densidade de probabilidade (PAPOULIS, 1991), por exemplo. As variáveis

aleatórias x e y são ditas independentes, se e somente se,

� ,��, �� � � ������� (4)

Page 6: Implementação ICA - Separação Cega de Fontes

6

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Em outras palavras, a densidade conjunta � ,��, �� de x e y devem fatorar no

produto das suas densidades marginais � �� e �����. Equivalente à independência,

esta pode ser definida pela substituição das funções de densidade de probabilidade

na Equação 4 pelas respectivas funções de distribuição cumulativa, que também

deve ser fatoráveis.

Duas variáveis, x e y, são não-correlacionadas se a sua covariância for zero:

0}{}{}{),cov( =−= yExExyEyx (5)

Assume-se que a média é zero para todas as variáveis aleatórias. Logo a

covariância é igual à correlação:

0}{),(),cov( === xyEyxcorryx (6)

Se as variáveis, x e y, são independentes, então são não-correlacionadas, ou

seja,

}{}{}{ yExExyE = , (7)

x e y são independentes. Substitui-se (7) em (5) obtém-se:

0}{}{}{}{),cov( =−= yExEyExEyx (8)

Porém, se duas variáveis aleatórias forem não-correlacionadas, não implica

que sejam independentes. Por isso, a independência é mais forte que a não-

correlação. Daí que os sinais a separar duma mistura tenham que ser mutuamente

independentes.

4 MODELO GENERATIVO

O modelo generativo descreve como os sinais misturados são produzidos e

trata-se da base do ICA. Este modelo afirma que os sinais misturados são o produto

da combinação linear dos sinais originais (componentes independentes). Para a

simplificação do método, não se considera a presença de ruído, diferente de

situações reais ou práticas.

Page 7: Implementação ICA - Separação Cega de Fontes

7

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

4.1 MATRIZ DE MISTURA, VARIÁVEIS OBSERVÁVEIS E VARIÁVEIS LATENTES

Matematicamente, o modelo generativo foi apresentado na seção 1. A

variável s é um vetor composto por todos os sinais originais (componentes

independentes). Note-se que os sinais originais, só por si, são também vetores.

Assim, nesta notação, as componentes independentes são os elementos de um

único vector de sinais originais, s. Neste vetor encontram-se então as variáveis

latentes, uma vez que, não são diretamente observáveis. Ou seja, estão escondidas

ou latentes, no vector x.

As técnicas usadas no ICA pretendem usar a matriz inversa de A, de forma a

estimar as componentes independentes, s, da seguinte forma:

xAs 1−= (9)

Em situações que a matriz A é conhecida basta utilizar a Equação 9 para

estimar s. Quando a matriz A não é conhecida devemos inicialmente assumir que, a

mistura, x, estão relacionados com os sinais latentes, s, através de uma

transformação linear (rotação e scaling). Logo, alguma transformação inversa

(rotação/scaling) pode ser encontrada de forma a se obter os sinais originais.

Note-se que as transformações podem também ser não-lineares. Desta

forma, a separação das componentes independentes complica-se. A Equação 10 e

11 descrevem, sucintamente, que existe uma função de mistura, F, também

desconhecida:

)(xFx = (10)

= ∑

=

n

jjijui saFx

1

, (11)

onde, ni ,,1L= e nj ,,1L= .

Page 8: Implementação ICA - Separação Cega de Fontes

8

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

5 RESTRIÇÕES AO MODELO

Para estimar a matriz de mistura A é preciso admitir algumas restrições:

1. As variáveis latentes, s, têm que ser mutuamente independentes.

2. As componentes independentes tem que ser distribuições não-gaussianas.

Isto deve-se ao fato do ICA permitir estimar ICs com ordem de estatística

elevada. Para sinais gaussianos, a ordem de estatística elevada é igual a

zero. Portanto, ICA não requer que seja conhecida a distribuição das

variáveis, basta que elas não sejam gaussianas. Pode-se notar (Figura 6)

que não é possível estimar a matriz de mistura, A, porque a distribuição de

probabilidades não possui informação sobre as direções das colunas desta

matriz. Assim, se a mistura possuir sinais originais não-gaussianos e sinais

originais gaussianos, então as componentes gaussianas não são separadas

pelo ICA e surgem misturadas.

Figura 6: Distribuição conjunta de duas variáveis aleatórias gaussianas.

3. A matriz de mistura A deve ser quadrada. Ou seja, o número de ICs deve ser

igual ao número de variáveis observadas (ou misturas). Assim, após o cálculo

da matriz A, pode-se usar a sua inversa, matriz B, para obter as ICs:

BxsAsAxAAsx =⇔=⇔= −− 11 (12)

Se a matriz A não for quadrada, então não terá inversa.

Page 9: Implementação ICA - Separação Cega de Fontes

9

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Observe que, se aplicarmos o PCA para reduzir a dimensão de x igual a

dimensão de s, o problema das matrizes de mistura singulares fica resolvido.

6 AMBIGUIDADES

Em ICA, a única informação disponível é relativa às misturas, x. Nada se

sabe sobre a matriz de mistura, A, e as variáveis latentes, s. Por essa razão,

existem determinadas ambiguidades nas componentes estimadas.

1. Escalamento: É impossível determinar as variâncias das ICs. Em

consequência, também não é possível calcular as energias ou as amplitudes

dos sinais. Esta ambiguidade verifica-se no problema do ‘cocktail party’,

porque não se sabe a localização das pessoas, nem dos microfones e nem

informação sobre as vozes. Como a amplitude do sinal não é conhecida,

então é usual fixar as amplitudes. Com isso, a variância dos sinais originais é

igual a um. No entanto, por inúmeras razões, é impossível determinar o sinal

das ICs. Por isso, os sinais originais quando separados, podem surgir

invertidos. Assim, se uma IC for multiplicada por -1, o modelo não é afetado.

Esta ambiguidade, felizmente, não apresenta grande problema na maioria

dos casos.

2. Permutação: É impossível determinar a ordem das ICs. Para saber a ordem

das componentes independentes, é necessário alguma informação sobre a

matriz de mistura. No entanto, por definição, esta matriz é desconhecida.

Assim sendo, pode-se alterar livremente a ordem dos termos na Equação 12

e definir qualquer uma das ICs como sendo a primeira. Uma matriz de

permutação P e a sua inversa podem ser substituídas no modelo de modo a

obter a Equação 13. Assim, os elementos Ps são as ICs originais s j numa

ordem diferente e a matriz AP-1 é uma nova matriz de mistura.

PsAPx 1−= (13)

Observe que uma matriz de permutação, P, é uma matriz quadrada

constituída unicamente por 0’s e 1’s e que possui em cada linha e em cada coluna

apenas um elemento igual a 1 (sendo os restantes elementos iguais a zero). Esta

ambiguidade não constitui um grande problema.

Page 10: Implementação ICA - Separação Cega de Fontes

10

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

=010

100

001

P

7 PRÉ-PROCESSAMENTO

A correlação é considerada uma medida “fraca”. Todavia, pode-se verificar

que este procedimento permite a determinação de uma transformação linear sobre a

mistura. À luz deste paradigma, conclui-se que a PCA considera apenas estatística

de segunda ordem, diferentemente de ICA, que considera estatística de ordem

superior, discutido anteriormente. Assim, utiliza-se a PCA como um pré-

processamento ao ICA que chamamos de branqueamento (POBLADOR; MORENO

et. al., 2004). Este método será detalhado na próxima seção.

Para ilustrar a tentativa de recuperar as fontes usando branqueamento,

representamos duas fontes independentes, �� e �, uniformemente distribuídas em

um quadrado (Figura 7). Usou-se uma matriz quadrada 2x2 para gerar as misturas

dadas pela Equação 2. O resultado desta mistura é apresentado na Figura 8 e por

fim suas estimativas obtidas pelo processo de branqueamento são ilustradas na

Figura 9.

Considerando o efeito do sistema misturador linear, verifica-se a dificuldade

da recuperação das fontes (Figura 9) usando estatística de segunda ordem.

Claramente, o método consegue recuperar as escalas das fontes, mas é incapaz de

recuperar a rotação, pois existe uma indeterminação referente a uma matriz

ortogonal cujo efeito é a rotação dos dados (HYVÄRINEN; OJA, 1999).

Intuitivamente, percebe-se que a utilização dessa ideia para um pré-

processamento no algoritmo ICA dito anteriormente é obrigatório na utilização do

branqueamento para a separação das fontes, visto que em distribuições gaussianas

conhecemos apenas duas características, a média e variância. Percebe-se com

este resultado a ineficácia da estatística de segunda ordem, no que tange a

impossibilidade de recuperar fontes gaussianas e este resultado foi provado por

Comon (1994).

Page 11: Implementação ICA - Separação Cega de Fontes

11

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Figura 7: Distribuição conjunta é uniforme em um quadrado.

Figura 8: Distribuição das misturas dos componentes.

Figura 9: Distribuições conjuntas das estimativas usando PCA.

Page 12: Implementação ICA - Separação Cega de Fontes

12

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Em primeiro lugar, para se determinar as componentes independentes,

remove-se a média dos valores das variáveis, num processo chamado centering ou

centralização das variáveis.

Em seguida, as variáveis aleatórias são transformadas em variáveis não-

correlacionadas através do processo chamado whitening ou branqueamento.

Ambos os processos podem ser usados pelo PCA, uma vez que, este método

descorrelaciona as variáveis e fornece, ainda, informação sobre a variância das

variáveis descorrelacionadas na forma de vetores próprios.

7.1 CENTRALIZAÇÃO (CENTERING)

Admite-se que as ICs e as variáveis observadas possuem médias iguais a

zero de forma a simplificar o modelo. Ou seja, subtrai-se a média das variáveis

observadas a todos os valores do vector x’ (vector original das variáveis

observadas):

}{' xExx −= (14)

As ICs vão também possuir média igual a zero pois:

}{}{ '1 xEAsE −= (15)

Após este processo a matriz A permanece igual, logo a estimativa da matriz

A não é afetada. Após esta estimativa da matriz de mistura e das ICs a partir dos

dados com média zero, adiciona-se o fator }{ '1 xEA− às ICs de forma a compensar o

processo de centralização.

7.2 BRANQUEAMENTO (WHITERING)

Se duas variáveis aleatórias são descorrelacionadas e têm variância igual a 1

então elas são chamadas de brancas (POBLADOR; MORENO et. al., 2004), ou

melhor, a matriz de covariância é igual à identidade conforme a equação a seguir:

{ }tzzE = I (16)

Podemos obter variáveis brancas a partir de uma transformação linear qual

seja:

z = Vx (17)

Page 13: Implementação ICA - Separação Cega de Fontes

13

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

O branqueamento de x pode ser feito pela matriz V tal que,

� � ����/����, (18)

onde, � é uma matriz ortogonal cujas colunas são os autovetores de ������ e � é

uma matriz diagonal com os autovalores correspondentes:

������ � ���� (19)

Assim, o branqueamento transforma a matriz � em uma nova matriz ��, de

forma que agora temos:

� � ��� � � � (20)

Vamos agora fazer uma transformação ortogonal em � fazendo:

! � "� (21)

Em razão à ortogonalidade de ", ! também é branco como mostra a seguinte

expressão:

��!!�� � ��"���"�� � "I"� � I (22)

Portanto, mostrou-se que o branqueamento é um pré-processamento para o

ICA, pois ele não é suficiente para que se estimem as fontes independentes, e

fornecendo apenas uma transformação ortogonal em �. O que precisamos agora é

de uma estratégia elaborada para rotacionar os dados das misturas.

8 MÉTODO DE ESTIMAÇÃO ICA

As componentes independentes são determinadas através da aplicação de

uma transformação na matriz de mistura ortogonal, após o processo de whitening.

Uma vez que, as misturas são uma combinação linear das ICs, então é possível

reconstrui-las a partir duma transformação linear inversa sobre as variáveis de x.

Assim sendo, a Equação 23 mostra a transformação, a partir da qual, se obtém as

ICs:

xbic tii = (23)

Page 14: Implementação ICA - Separação Cega de Fontes

14

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

O elemento $% da Equação 23 é uma componente independente e trata-se

duma estimativa do sinal original. O elemento b é o vetor apropriado que reconstrói

cada componente independente.

Existem inúmeras e diferentes abordagens para estimar b que, se baseiam

numa função objetivo relacionada com a independência das variáveis. Essa função

é maximizada ou minimizada através de algoritmos de optimização.

As várias abordagens diferem entre si, na definição da função objetivo que é

optimizada e, no método de optimização a usar. Alguns métodos são: Maximização

da não-gaussianidade; estimativa da máxima probabilidade; minimização da

Informação mútua; métodos tensoriais, método usando PCA, entre outros.

8.1 ALGORITMO ICA UTILIZANDO PCA

Um dos algoritmos que foi desenvolvido recentemente provou ser superior a

algumas abordagens ICA (KUN, CHAN, 2006). Conhecido como P-ICA, esta

abordagem basicamente resolve o problema de BSS linear aplicando PCA e

posteriormente usa uma transformação para recuperar os sinais de fontes.

Considerando os dados observados representados por x, PCA e ICA visam à

transformação linear dado pela Equação 2. No entanto, elas exploram os dados de

formas diferentes. O PCA visa encontrar uma transformação ortogonal em W que dá

resultados não correlacionados (vale lembrar que se mostrou anteriormente que

PCA considera apenas estatística de segunda ordem). Porém, o PCA utiliza a

distribuição conjunta gaussiana para ajustar os dados e encontrar uma

transformação ortogonal que faz a distribuição conjunta gaussiana fatorável

independente da verdadeira distribuição dos dados. Neste contexto, a ICA tenta

encontrar uma transformação linear que faz a verdadeira distribuição conjunta dos

dados transformados fatorável, de modo que as saídas são mutuamente

independentes.

Grande parte dos algoritmos ICA requerem o branqueamento das misturas

como descrito na seção 7.2, podemos citar como exemplo o FastICA (HYVÄRIEN,

1999c) e o JADE (CARDOSO, 1999). Discorremos na mesma seção que o processo

de branqueamento pode ser feito a partir de PCA, bem como usar decomposição de

autovalores e autovetores.

Page 15: Implementação ICA - Separação Cega de Fontes

15

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Em linhas gerais, Kun e Chan (2006) mostrou e provou que as componentes

independentes têm diferentes kurtosis, no qual se tem o seguinte teorema: Dado s,

&, e � vetores aleatórios tal que & � '�, onde W é uma matriz ortogonal e � �

‖&‖&. Suponha que s tem média zero e que as componentes independentes têm

diferentes kurtosis. Então, a matriz ortogonal " que é dado pela componente

principal de � (� não é centralizado) realiza ICA em &.

O método P-ICA se resume nos seguintes procedimentos que consiste em

quatros etapas:

1. Branqueamento de x usando a Equação 17;

2. Faça uma transformação � � ‖&‖&;

3. Encontre " usando PCA em �;

4. Depois de encontrar a matriz ortogonal " finalmente a matriz de separação

pode ser estimada usando a expressão ' � "�.

8.2 FASTICA POR KURTOSIS E NEGENTROPIA

Para encontrar o máximo da não-gaussianidade, é necessário usar o método

do gradiente. No entanto, a convergência para o máximo local é lento. Assim, para

tornar esse processo mais rápido, os algoritmos iterativos de pontos-fixos (FastICA)

tornaram-se uma boa alternativa. A convergência rápida deve-se ao fato de se tratar

de algoritmos cúbicos.

Como a não-gaussianidade pode ser medida através da kurtosis ou da

negentropia, existe então o FastICA que usa a kurtosis e o FastICA por base na

negentropia. No entanto, é importante salientar que existem versões mais

sofisticadas deste algoritmo.

8.2.1 UTILIZANDO KURTOSIS

No FastICA que usa a kurtosis, o ponto estável (máximo) deve apontar na

direção de W, ou seja, o gradiente deve ser igual a W multiplicado por um escalar

constante. A equação do gradiente da kurtosis com W é a seguinte:

[ ]WWxWxEW t 23 ||||3})({ −=

Page 16: Implementação ICA - Separação Cega de Fontes

16

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Sendo um processo iterativo, um novo valor de W é dado por:

3})({[ 3 −= xWxEW t

No final, o vector W fornece uma das componentes independentes como uma

combinação (Equação 24). Mas para tal acontecer, é necessário que os valores old

and new de W apontem na mesma direção.

xWic t= (24)

8.2.2 UTILIZANDO NEGENTROPIA

O algoritmo FastICA foi primeiramente publicado por Hyvärinen (1999b). O

objetivo do algoritmo é encontrar uma matriz W e ajustar as suas linhas denotadas

por )��, de modo que !� � )�

�� resulte numa estimativa das fontes, lembrando que a

maximização da Negentropia é baseada nos momentos polinomiais (HYVÄRINEN,

1999a). Utilizando a aproximação da Negentropia e considerando que os dados

foram branqueados, a maximização da Negentropia se resume em encontrar uma

matriz W que é descrito pelo seguinte problema de otimização (HYVÄRINEN, 2000):

)*� � �+,-�./

0��1����� 2 ��1�3��4

Fazendo uma restrição na etapa de adaptação, temos que restringir a

potência de cada uma das estimativas assumindo que:

����� � ��)���� � 1

O máximo da função )*� é quando encontramos certo valor ótimo de ��1�����

em razão ao ��1034� ser constante. Assim, considerando o primeiro termo da

equação, o problema de maximizar e otimizar são equivalentes. Podemos mostrar

que o problema de otimização é resolvido usando o método de Lagrange, quando a

seguinte condição é satisfatória (HYVÄRINEN, 1999):

���16�)����� 7 8)� � 0,

onde 8 é uma constante.

Considerando que as misturas estejam branqueadas, aplica-se o método de

Newton para a solução da expressão anterior e assim se obtêm a seguinte regra de

atualização:

Page 17: Implementação ICA - Separação Cega de Fontes

17

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

)� ← ���1�)����� 2 ��16�)�

����)�

)� ←./

‖./‖,

onde G é uma função não quadrática e 16 é sua derivada. A expressão a seguir

poderia representar 1 e sua derivada, respectivamente:

1�;� �1��

log ?@�A� ��B�

16�;� � C��A���B�

Para recuperar várias fontes a partir da regra de atualização (ou regra de ajuste),

se faz necessário executá-la para vários vetores )�. Frequentemente, se tem um

problema em que o algoritmo sempre encontra a mesma fonte, ou seja, converge

para o mesmo ótimo. Neste caso, o problema é contornado da seguinte maneira:

Considere um problema de separação de três fontes distintas feita a extração da

primeira fonte. A extração da segunda fonte é feita aplicando a regra de ajuste.

Entretanto, a cada iteração se retira do vetor em processo de estimação a

contribuição do vetor referente à primeira fonte, de modo que esses dois vetores

sejam ortogonais. Podemos usar esta mesma estratégia para extrair a terceira fonte.

Deve-se, em cada iteração, retirar a contribuição dos dois vetores estimados e

assim por diante. Finalmente, a regra de aprendizagem do FastICA é descrito:

1. Centralizar e branquear as misturas;

2. Definir aleatoriamente valores iniciais para )� (colunas de W) e ortogonalizar

W de acordo com passo 5;

3. Para todo D faça )� ← ���1�)����� 2 ��16�)�

����)�;

4. Divida )� por sua norma;

5. Ortogonalizar ' ← �''����/';

6. Caso não convirja, volta para o passo 3.

Page 18: Implementação ICA - Separação Cega de Fontes

18

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

8.3 JADE (JOINT APPROXIMATE DIAGONALIZATION OF EIGENMATRICES)

Um tensor cumulante de quarta ordem é uma matriz com quatro dimensões

cujas entradas são originadas pelo cruzamento de cumulantes de quarta ordem dos

dados.

Um tensor cumulante pode ser decomposto em valores próprios originando

uma matriz de valores próprios:

MMF λ=)(

Este algoritmo é baseado na decomposição em valores próprios, ou seja,

pode ser visto como uma diagonalização da matriz EEEE através da sua multiplicação

pela matriz W (matriz de mistura ortogonal, após o processo do branqueamento): tWMWFQ )(=

A matriz Q é diagonal porque F é uma combinação linear de M. Usam-se,

então, diferentes matrizes M para tentar tornar a matriz Q o mais diagonal possível

(porque, idealmente, esta matriz não pode ser exatamente diagonal).

A diagonalidade da matriz Q pode ser medida como a soma dos quadrados

dos elementos não pertencentes à sua diagonal: ∑≠ lk

klq 2 . Como a matriz W é

ortogonal, ao ser multiplicada por outra matriz, não altera a soma total dos

quadrados dos elementos dessa matriz, então minimizar a soma dos quadrados dos

elementos fora da diagonal é equivalente a maximizar a soma dos quadrados dos

elementos da diagonal.

Então, este algoritmo tem como objetivo maximizar a seguinte equação:

∑=i

ti WMWFdiagWJade 2|))((|)(

As matrizes Mi são escolhidas segundo as matrizes dos valores próprios do

tensor cumulante, ou seja, são matrizes que dão informação importante aos

cumulantes, pois partilham o mesmo espaço que o tensor cumulante.

Neste método as correlações não lineares entre as variáveis observadas e as

variáveis independentes são minimizadas. O algoritmo JADE não é muito eficiente

para dimensões elevadas, mas funciona corretamente quando o número de

variáveis é pequeno.

Page 19: Implementação ICA - Separação Cega de Fontes

19

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

9 APLICAÇOES ICA

Um dos grandes desafios da engenharia biomédica é na avaliação das

alterações fisiológicas que ocorrem em diversos órgãos internos do corpo humano.

Existem problemas nas extrações das informações relevantes para diagnósticos, ou

seja, sinais de fontes biomédicos são geralmente fracos, não estacionários, com

ruídos e interferências (CICHOCKI; AMARI, 2002). A seguir têm-se algumas

aplicações da ICA em problemas de separação cega de fontes.

9.1 MONITORAMENTO DE BATIMENTOS CARDÍACOS

A ação mecânica dos músculos do coração é estimulada por sinais elétricos.

Estes níveis de sinais podem ser medidos e visualizados como funções de tempo

usando eletrocardiograma (ECG) (CICHOCKI; AMARI, 2002). Tal como para adultos

também seria possível medir a atividade elétrica do coração de um feto. As

características de um eletrocardiograma fetal (FECG) podem ser muito úteis para

determinar se um feto está se desenvolvendo corretamente, por exemplo. Estas

características incluem uma elevação da frequência cardíaca fetal que indica

estresse, arritmias. Obter uma informação fiel do FEGC é uma tarefa não trivial.

Problemas podem acontecer em virtude de que o eletrocardiograma também

contém informações dos batimentos cardíacos materno (MECG) (JAHN; AMARI et

al., 1999). Além disso, o FECG irá ocasionalmente sobrepor sinais ao MECG e

torná-lo normalmente difícil de detectar (CARDOSO, 1998). Também juntamente

com o MECG ruídos extensivos nestes sensores interferem no FECG e podem

mascarar completamente este. A separação destes sinais de fontes fetal e materno

de uma mulher grávida pode ser modelado como um problema BSS (HAYKIN,

2001a).

9.2 CANCELAMENTO DE RUÍDO E INTERFERÊNCIA

O sistema nervoso dos seres humanos e dos animais deve codificar e

processar informações sensoriais. Dentro deste contexto, os sinais codificados (as

imagens, sons) têm propriedades muito específicas. Uma das tarefas desafiadoras é

a de saber como fielmente detectar, localizar e melhorar os sinais cerebrais em que

Page 20: Implementação ICA - Separação Cega de Fontes

20

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

muitas vezes as fontes são corrompidas. ICA e Análise Fatorial Adaptativo (AFA)

são abordagens promissoras para a eliminação de artefatos e ruídos provenientes

dos EEG / MEG (HE; REED, 1996) (JAHN; AMARI et al., 1999).

9.3 SISTEMAS DE COMUNICAÇÃO DIGITAL

Considere um sistema onde se têm múltiplos sinais de uma propagação de

comunicação sem fio, bem como um número de usuários difundidos em sinais

modulados digitalmente para uma estação base em um ambiente de vários

usuários. A transmissão destes sinais interage com diversos objetos físicos na

região antes de chegar à antena ou estação de base. Cada sinal segue caminhos

diferentes com atraso e atenuação. Este é um típico problema que é conhecido

como “multi-path fading” (CARDOSO, 1998). Além disto, em algumas redes de

celulares existem outras fontes adicionais de distorções. Estas interferências podem

ser causadas por vários utilizadores que partilham a mesma frequência e tempo.

Um problema desafiador é a separação e processamento de sinais cegos conjunta

de espaço-tempo e equalização dos sinais transmitidos, isto é, para estimar a fonte

de sinais e seus canais na presença de outros sinais e ruído (HAYKIN, 2001a).

10 EXEMPLO DA APLICAÇÃO ICA UTILIZANDO MATLAB

Neste experimento utilizamos 3 sinais de fontes que são misturados por uma

matriz 3x3 gerado aleatoriamente e finalmente estimado pelo P-ICA. Vamos

primeiramente descrever o método P-ICA dado pelo pca_ica.m. E o método utilizado

para realizar o branqueamento é dado por branqueamento.m.

% A seguinte função implementa o P-ICA linear % % Entrada: x é mistura uma matriz(dxn) % % y é os sinais estimados % w é a matriz de mistura (inversa de A) % % % Autor: Nielsen C. Damasceno % Data: 20.12.2010 function [y,w] = pca_ica(x) n = size(x,1);

Page 21: Implementação ICA - Separação Cega de Fontes

21

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

[E, D] = eig(cov(x')); v = E*D^(-0.5)*E' * x; z = repmat(sqrt(sum(v.^2)),n,1).*v; [EE, DD] = eig(cov(z')); y = EE'*v; w = EE'; end % A seguinte função implementa o branqueamento % % Entrada: x é mistura uma matriz(dxn) % % y é uma matriz (dxn)que é o resultado d o branqueamento % % % Autor: Nielsen C. Damasceno % Data: 20.12.2010 function [y] = branqueamento(x) [E, D] = eig(cov(x')); y = E*D^(-0.5)*E' * x; end

O codigo-fonte a seguir descreve a estimação de 3 fontes independentes, a

Figura 10, 11 e 12 representa os sinais de fontes, as misturas e os sinais estimados,

respectivamente.

clear all ; close all ;clc; N = 1000; % Número de pontos (correspondem a 4 segundos de da dos) fs = 500; % Frequência de amostragem w = (1:N)*2*pi/fs; % Normalização do vector da frequência t = (1:N); % Vector do tempo % Criação dos três sinais com ruído s1 = 0.75*sin(w*12)+0.1*randn(1,N); % Seno duplo s2 = sawtooth(w*5,0.5)+0.1*randn(1,N); % Onda triangular s3 = pulstran((0:999),(0:5)'*180,kaiser(100,3))+ 0. 07*randn(1,N); % Onda periódica %Elementos da matriz de mistura a = rand(3); s =[s1; s2; s3]; % Matriz das fontes originais x = a * s; % Sinais misturados/observados % Branqueamento da mistura x = branqueamento(x); % Método ICA (usando o algoritmo P-ICA) y = pca_ica(x); % Gráfico dos resultados

Page 22: Implementação ICA - Separação Cega de Fontes

22

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

figure; subplot(3,1,1); plot(t,s1);xlabel( 'Tempo (s)' ); ylabel( 's_1(t)' ); subplot(3,1,2); plot(t,s2);xlabel( 'Tempo (s)' ); ylabel( 's_2(t)' ); subplot(3,1,3); plot(t,s3);xlabel( 'Tempo (s)' ); ylabel( 's_3(t)' ); figure; subplot(3,1,1); plot(t,x(1,:));xlabel( 'Tempo (s)' ); ylabel( 'x_1(t)' ); subplot(3,1,2); plot(t,x(2,:));xlabel( 'Tempo (s)' ); ylabel( 'x_2(t)' ); subplot(3,1,3); plot(t,x(3,:));xlabel( 'Tempo (s)' ); ylabel( 'x_3(t)' ); figure; subplot(3,1,1); plot(t,y(1,:));xlabel( 'Tempo (s)' ); ylabel( 'y_1(t)' ); subplot(3,1,2); plot(t,y(2,:));xlabel( 'Tempo (s)' ); ylabel( 'y_2(t)' ); subplot(3,1,3); plot(t,y(3,:));xlabel( 'Tempo (s)' ); ylabel( 'y_3(t)' );

Figura 10: Sinais de originais.

0 100 200 300 400 500 600 700 800 900 1000-1

0

1

Tempo (s)

s 1(t)

0 100 200 300 400 500 600 700 800 900 1000-2

0

2

Tempo (s)

s 2(t)

0 100 200 300 400 500 600 700 800 900 1000-2

0

2

Tempo (s)

s 3(t)

Page 23: Implementação ICA - Separação Cega de Fontes

23

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

Figura 11: Sinais de misturas utilizando uma matriz 3x3.

Figura 11: Sinais estimados utilizando P-ICA.

OBS.: O código-fonte pode ser baixado no meu site em http://www.ncdd.com.br. E tutorial é baseado no texto de apoio e Taíssa Pereira e Sónia Ferreira. Algoritmo de Diagnóstico e de Auto-Regulação. Engenharia Biomédica 2010.

0 100 200 300 400 500 600 700 800 900 1000-5

0

5

Tempo (s)

x 1(t)

0 100 200 300 400 500 600 700 800 900 1000-5

0

5

Tempo (s)

x 2(t)

0 100 200 300 400 500 600 700 800 900 1000-5

0

5

Tempo (s)

x 3(t)

0 100 200 300 400 500 600 700 800 900 1000-2

0

2

Tempo (s)

y 1(t)

0 100 200 300 400 500 600 700 800 900 1000-5

0

5

Tempo (s)

y 2(t)

0 100 200 300 400 500 600 700 800 900 1000-5

0

5

Tempo (s)

y 3(t)

Page 24: Implementação ICA - Separação Cega de Fontes

24

Prof. M.Sc. Nielsen Castelo Damasceno – www.ncdd.com.br – E-mail: [email protected] – UFRN

REFERÊNCIAS

CARDOSO J., “Blind signal separation: statistical principles” , Proc. IEEE 86 (10) 1998.

CARDOSO J., “ High-order contrasts for independent component anal ysis” , Neural Computation, pag. 157-192, 1999.

CICHOCKI A., AMARI S., “Adaptive Blind Signal and Image Processing: Learning Algorithms and Applications” , John Wiley, New York, USA, 2002.

COMON P., “Independent component analysis, a new concept?” , Signal Process,1994.

HAYKIN S., “Redes Neurais: Princípios e prática” . 2ª ed. Porto Alegre: Bookman,

2001a.

HE R., J. REED. “A robust co-channel interference rejection techniqu e for current mobile phone system” . In Proc. IEEE VTC, pag. 1195–1199 vol.2, Atlanta, GA, 1996.

HYVÄRINEN A., E.OJA. “Independent component analysis: A tutorial” . Technical report, 1999.

HYVÄRINEN A., “Survey on independent component analysis”, Neural Computer Surveys 2, 1999a.

HYVÄRINEN A., “Fast and robust Fixed-point algorithms for independ ent component analysis” , IEEE Trans. Neural Networks 10, 1999c.

HYVÄRINEN A., E. OJA. “Independent Component Analisys: Algorithms and applications. Neural Networks” , 2000.

JAHN O., A. CICHOCKI, A. IOANNIDES, S. AMARI. “Identification and elimination of artifacts from MEG signals using efficient indep endent components analysis” , In Proc. of th 11th Int. Conference on Biomagentism BIOMAG-98, pag. 224–227, Sendai, Japan, 1999.

KUN Z, Lai-WAN CHAN, "ICA by PCA Approach: Relating Higher-Order Statistics to Second-Order Moments" , 2006.

PAPOULIS, A. “Probability, Random Variables, and Stochastic Proce sses” , McGraw-Hill, 3rd edition, 1991.

POBLADOR S., V., MONTE-MORENO, E. & SOLÉ-CASAL, J. “ICA as a Preprocessing Technique for Classification” , In Proceedings of the Fifth International Workshop on Independent Component Analysis and Blind Signal Separation, ICA 2004, pag. 1165-1172, Granada, Espanha, 2004.