Separação Cega de Fontes Baseada em Medidas de Complexidade
Patrick F. Coutinho1, Filipe I. Fazanaro2, Diogo C. Soriano2, Romis Attux1
1 - Departamento de Engenharia de Computação e Automação (DCA)
Faculdade de Engenharia de Computação e Automação Industrial (FEEC)
Universidade Estadual de Campinas (Unicamp)
Caixa Postal 6101, CEP 13083-970 – Campinas, SP, Brasil
2 - Centro de Engenharia, Modelagem e Ciências Sociais Aplicadas (CECS)
Universidade Federal do ABC (UFABC)
Avenida dos Estados, 5001, CEP 09210-580 – Santo André, SP, Brasil
patrickfcoutinho@gmail.com, {filipe.fazanaro, diogo.soriano}@ufabc.edu.br,
attux@dca.fee.unicamp.br
Abstract – In this work, an alternative approach to the blind source separation based on an estimate of the algorithmic
complexity of the involved signals is presented. In doing so, concepts of recurrence quantification analysis by means of the
construction of recurrence plots are used. The relationship between the sizes of two files of the recurrence plot, one file
compressed and another with no compression, is the complexity measure, which is taken as the cost function to be minimized.
Numerical experimental results show that if the mixture models are invertible, then an effective source recovery is possible.
Keywords – algorithmic complexity, blind source separation, recurrence plot
1. Introdução
Em processamento de sinais, a separação
cega de fontes (BSS, do inglês Blind Source
Separation) é um problema clássico e de grande
relevância prática. Tal problema pode ser
explicado como se segue, em sua vertente linear e
instantânea.
Considere que dois sinais, 1 () e 2 (),
são misturados de acordo com a equação
() = (),
(1)
sendo  a matriz de mistura, considerada de posto
completo, e () = [1 () 2 ()] é o vetor de
sinais misturados. Deseja-se, então, com o mínimo
possível de informação a priori, recuperar as
fontes originais a menos de indeterminações
aceitáveis (de escala e permutação).
A recuperação das fontes passa por
encontrar uma matriz de separação , de tal
forma que o vetor de sinais recuperados, () =
[1 () 2 ()] , seja obtido conforme
() = ().
(2)
Quando as fontes são mutuamente
independentes, é possível resolver este problema
por meio de uma metodologia denominada Análise
de Componentes Independentes (ICA, do inglês
Independent Component Analysis). Os algoritmos
que implementam a ICA lidam com métricas
relacionadas à informação mútua, a qual se
procura minimizar, e ao conceito de nãogaussianidade, formalizado via kurtosis e
negentropia.
Neste trabalho, é apresentada uma
abordagem distinta para o problema mencionado.
Tomam-se como base os artigos de Pajunen [3] e
Soriano et al. [4,5]. A metodologia proposta adota
como métrica para realizar a BSS a complexidade
algorítmica relativa aos sinais do sistema. A
complexidade será aproximada por meio de um
processo de compressão sem perdas.
O artigo está estruturado da seguinte
maneira: a seção 2 elucida brevemente os
conceitos de mapa de retorno e complexidade
algorítmica no escopo deste trabalho, além de
relacionar o problema da BSS com a abordagem
sugerida; a seção 3 traz alguns resultados obtidos
ao se realizar a BSS para duas fontes distintas em
misturas com sinais aleatórios; por fim, a seção 4
apresenta as discussões finais e perspectivas
futuras do trabalho.
2. Proposta
A seguir, uma exposição sumária dos
conceitos de mapas de retorno e complexidade
algorítmica é feita. Logo após, o problema da BSS
é relacionado a estes conceitos.
2.1 Mapas de Retorno
Mapa de retorno é uma ferramenta gráfica
de análise de dados não-lineares amplamente
utilizada na área de sistemas dinâmicos. De acordo
com Soriano et al. [5], o mapa pode ser visto como
uma matriz de pontos claros (brancos) e escuros
(pretos) na qual o ponto (, ) da matriz será um
Figura 1. As imagens acima apresentam mapas de retorno para um sinal periódico - sin⁡(5) -, um
caótico e um aleatório, em sequência. Nos três mapas foram utilizados número de amostras por fonte N =
200, dimensão de imersão  = 2, distância entre amostras  = 2 e limiar  = 0.3.
ponto escuro sempre que a distância entre dois
vetores de estados for menor que um certo limiar,
i.e., ‖() − ()‖ < . O vetor de estados () é
definido como () = [()⁡⁡( − )⁡… ⁡⁡⁡( −
( − 1)], onde  representa a dimensão de
imersão e  o atraso entre as amostras.
Nos mapas de retorno, características
intrínsecas dos sinais analisados são facilmente
observáveis, como pode ser visto na Figura 1.
Nela são exibidos mapas de retorno para três sinais
distintos: um sinal determinístico periódico, um
sinal caótico obtido a partir de um mapa de Hénon
(sistema dinâmico em tempo discreto), e um sinal
aleatório com distribuição uniforme no intervalo
(0,1).
Na referida figura, o primeiro mapa possui
linhas diagonais que se repetem e são paralelas à
diagonal principal, caracterizando a periodicidade
do sinal que representa; o segundo mapa tem
diagonais menores paralelas ao eixo principal, um
indício de que o sinal é caótico [5]; por fim, o
terceiro mapa exibe uma distribuição homogênea
de pontos claros e escuros, de acordo com o sinal
ruidoso utilizado.
2.2 Complexidade Algorítmica e Compressão
de Informação
A complexidade algorítmica, também
conhecida como complexidade de Kolmogorov –
Chaitin, pode ser definida em relação a uma
sequência binária  como o tamanho  do menor
programa  que, fornecido a uma máquina
universal , produz como saída a sequência s
quando nenhuma entrada é fornecida [2,3]. De
acordo com Cover et al. [1], esta definição é
descrita matematicamente pela função:
 () =
min (),
:()=
(3)
Essencialmente,
não
existe
um
procedimento mecânico e finito capaz de
determinar a complexidade algorítmica de
qualquer sequência binária, i.e., a função de
complexidade não é computável [1]. Assim, uma
alternativa é adotar o tamanho do arquivo
comprimido da sequência binária como medida da
complexidade algorítmica daquela sequência, o
que se configuraria como um limitante superior da
complexidade de Kolmogorov.
Na Figura 1, as três imagens obtidas têm
resolução de 200⁡⁡200 pixels e foram
armazenadas em disco em formato Tiff (dados
raster). A compressão dos arquivos foi feita com o
algoritmo Lempel-Ziv-Welch, portanto é uma
compressão sem perdas. Quanto ao tamanho dos
arquivos comprimidos, constata-se que se
consegue uma compressão maior das imagens dos
mapas de retorno quando estes apresentam
estruturas que se repetem, como é visto na Tabela
1. Sem compressão, os arquivos das imagens
apresentam todos o mesmo tamanho devido ao
formato de arquivo utilizado (40238 bytes).
Fonte
periódica caótica aleatória
Tamanho
2792
3576
5636
(bytes)
Tabela 1. Tamanho dos arquivos comprimidos
referentes às imagens dos mapas de recorrência
das fontes periódica, caótica e aleatória ilustradas
na Figura 1.
Da Tabela 1, portanto, é possível concluir
que algoritmos de compressão são mais eficientes
em conjuntos de dados que apresentam
regularidades. A diferença notável entre os
tamanhos dos arquivos comprimidos conjura uma
propriedade subjacente às sequências binárias:
como teorizado por Chaitin [2], quanto mais
aleatória uma sequência binária, maior o programa
necessário para computá-la.
2.3 Compressão dos Mapas de Retorno e BSS
Em seus artigos, Pajunen [3] e Soriano et
al. [5] identificam alguns fatores limitantes
relacionados ao uso exclusivo de informação a
priori baseada em independência dos sinais, como
por exemplo a necessidade de conhecimento ou
estimação do sinal da kurtosis e não-gaussianidade
das fontes. Visando contornar essas limitações na
BSS, ambos os autores propõem métricas baseadas
em medidas de complexidade.
Pajunen [3] argumenta que “sinais
naturais” tendem a ter uma complexidade de
descrição relativamente limitada se comparados,
por exemplo, a sinais estocásticos. Então, presume
que uma mistura de dois ou mais sinais tem uma
complexidade maior que a de qualquer um dos
sinais individuais e, portanto, a complexidade dos
sinais pode ser tomada como função custo a ser
minimizada (sutilmente, evoca-se o princípio
minimum description length, MDL).
Soriano et al. [5] fazem uso de uma
metodologia chamada análise de quantificação de
recorrência (recurrence quantification analysis,
em inglês), cujas métricas permitem, em alguma
medida, por meio da construção de mapas de
retorno, discriminar sinais periódicos, caóticos e
estocásticos. A separação é realizada por meio de
métricas derivadas dos mapas de retorno das séries
estimadas.
Neste trabalho, é apresentada uma
proposta na mesma linha das abordagens
supracitadas. Considerando uma mistura linear
conforme descrita pela equação (1), a separação
cega pode ser realizada buscando-se minimizar a
complexidade relativa ao mapa de retorno do sinal
recuperado.
Então, no primeiro cenário, foi empregada
uma fonte periódica senoidal, sin⁡(0.25).
Realizamos a separação utilizando como
parâmetros do mapa de recorrência os valores
 = 1,  = 1, variando  entre 0.1 e 0.9 a uma
taxa de 0.2. Dessa maneira, foi possível obter o
mapa de retorno do sinal recuperado para diversas
combinações de  e . A relação entre o tamanho
dos arquivos com e sem compressão do mapa de
retorno do sinal recuperado foi tomada como
medida de complexidade, definindo-a como a
função custo a ser minimizada.
Os sinais misturados e o sinal recuperado
são exibidos na Figura 2. A Figura 3 mostra o
gráfico da função custo em função de  para cada
 analisado.
Figura 2. Gráficos superiores, sinais de mistura;
em azul, abaixo, o sinal periódico recuperado.
3. Resultados
A separação cega de fontes é realizada em
dois cenários semelhantes: adota-se uma fonte
periódica no primeiro e uma fonte caótica obtida a
partir de um mapa de Hénon no segundo. Em
conformidade com a equação (1) mencionada
acima, os sinais gerados por estas fontes foram
misturados linearmente a sinais aleatórios de
distribuição normal (0,1) originários de fontes
estocásticas. Seguindo os procedimentos na Ref.
[5], utilizou-se no processo de mistura uma matriz
 ortogonal. Desta maneira, a matriz de separação
 pôde ser parametrizada em relação a uma única
cos⁡() −sin⁡()
variável ,  = [
].
sin⁡() cos⁡()
Figura 3. Gráfico da função custo no processo de
recuperação da fonte determinística.
O experimento numérico foi repetido no
segundo cenário, em que se substituiu a fonte
periódica por uma fonte caótica. Foram adotados
os valores  = 2,  = 1 e  variando entre 0.4 e
2.0 a uma taxa de 0.2. Os sinais misturados e o
sinal recuperado são mostrados na Figura 4, e a
Figura 5 exibe o gráfico da função custo em
função de  para os diversos valores de .
possível recuperar as fontes – no segundo caso, o
sinal recuperado está invertido em relação ao sinal
original, mas esta é uma diferença aceitável.
Durante a construção dos mapas de
retorno, observou-se que os valores de 
influenciam severamente na qualidade dos
resultados obtidos. Valores muito baixos ou muito
altos comprometem a construção dos mapas, uma
vez que não é possível capturar nos mapas
características próprias dos sinais; como, por
exemplo, periodicidade.
Perspectivas futuras para este trabalho
envolvem o estudo de outras estimativas de
complexidade e a análise do método no caso em
que a mistura não é invertível. Além disso, a
eficiência da abordagem proposta precisa ser
examinada em comparação tanto com os métodos
clássicos de ICA quanto com aqueles propostos
por Pajunen [3] e Soriano et al. [5].
Agradecimentos
Os autores agradecem ao CNPq (PIBIC e
processos 302890/2012-2, 449699/2014-5 e
449467/2014-7) o apoio financeiro.
Figura 4. Nas figuras superiores, tem-se os sinais
misturados. Em seguida, o sinal original, 1 (), e
o sinal recuperado, 1 (), o qual está invertido em
relação ao sinal original.
Figura 5. Gráfico da função custo no processo de
recuperação da fonte caótica.
4. Conclusões
O método proposto apresenta excelentes
resultados no contexto da separação cega de fontes
quando os modelos de mistura são invertíveis. Nos
dois cenários considerados, partindo-se de um
processo de mistura perfeitamente reversível, foi
Referências
[1] T. M Cover, P. Gacs, R. M. Gray,
“Kolmogorov’s Contributions to Information
Theory and Algorithmic Complexity”, The
Annals of Probability, Vol. 17, No. 3, pp. 840865, 1989.
[2] G. J. Chaitin, Thinking About Gödel and
Turing: Essays on Complexity, 1970 – 2007,
World Scientific Publishing Company, 2007.
[3] P. Pajunen, “Blind Source Separation Using
Algorithmic
Information
Theory”,
Neurocomputing, Vol. 22, Nos. 1 – 3, pp. 35 48, 1998.
[4] D. C. Soriano, F. I. Fazanaro, R. Attux, R.
Suyama, “Estimating Algorithmic Complexity
of Dynamical Systems and Time Series Using
Recurrence Plots”, Aceito para Apresentação
no Sixth International Symposium on
Recurrence Plots, Grenoble, França, 2015.
[5] D. C. Soriano, R. Suyama, R. Attux, “Blind
Extraction of Chaotic Sources from Mixtures
with Stochastic Signals Based on Recurrence
Quantification Analysis”, Digital Signal
Processing, Vol. 21, No. 3, pp. 417 – 426,
2011.
Download

Separação Cega de Fontes Baseada em - FEEC