Universidade Federal do Rio Grande do Norte Programa de pós-graduação em Engenharia Elétrica e...

Separação cega de fontes lineares e não lineares usando Algoritmos Genéticos, Redes Neurais RBF e

Negentropia de Rényi como medida de independência

Universidade Federal do Rio Grande do Norte

Programa de pós-graduação em Engenharia Elétrica e de Computação

Aluno: Nielsen Castelo Damasceno

Orientador: Allan de Medeiros Martins

Co-Orientador: Adrião Duarte Dória Neto

Defesa de Mestrado

Introdução Análise de Componentes Independentes Separação de fontes usando Negentropia Algoritmo Genéticos RBF Método proposto Resultados experimentais Considerações finais

AGENDA

Surgimento de novas técnicas de separação de sinais; Algoritmos ICA que utilizam medida de Independência:

estatística de ordem superior e teoria da informação; Contribuições de Alfred Rényi; Na década de 90 deram os passos iniciais para utilização

da entropia de Rényi; Algoritmos que utilizam entropia de Rényi com kernel

gaussiano e janelamento de Parzen.

INTRODUÇÃO

OBJETIVO

Separações cega de fontes para o caso de misturas lineares

e não-lineares. Utilizando RBF , Algoritmos Genéticos e a

Negentropia de Rényi.

Encontrar um matriz de separação W.

Encontrar uma função G não linear.

ANÁLISE DE COMPONENTES INDEPENDENTES

Dado um problema de resolução de um sistema de equação linear

Solução: atribuir algumas propriedades estáticas sobre os sinais.

Motivado pelo problema do Cocktail-party

Fonte: s

Coeficientes: A

Misturas: x

ANÁLISE DE COMPONENTES INDEPENDENTES

Definição de ICA: A ICA de um vetor aleatório consiste na

determinação de uma transformação linear.

𝒚=𝑊 𝒙

minimize uma função custo , chamada de função contraste,

ANÁLISE DE COMPONENTES INDEPENDENTES

Considere os sinais de misturas , sendo formados por um modelo de misturas instantâneo não linear dado por:

A proposta é estimar a inversa da transformação (sistema separador), tal que:

Varios métodos NLICA impõe restrições ao modelo de mistura Mapeamentos não-linear que preserva a Independência é

chamada de trivial.

ANÁLISE DE COMPONENTES INDEPENDENTES

NEGENTROPIA

Conceito base: Entropia

Teoria da informação: Uma variável gaussiana tem o maior valor da entropia

𝐽 (𝑥 )=𝐻 (𝑥𝑔𝑎𝑢𝑠𝑠 )−𝐻 (𝑥 ) Medida de não-gaussianidade

𝐽 (𝑥 )≈ 112𝐸 {𝑦3 }2

+1

48𝐾 (𝑦 )2

Método clássico

Substituir momentos polinomiais

𝐺1 (𝑦 )= 1𝑎1

𝑙𝑜𝑔(cosh (𝑎1𝑦 ))

𝐺2 (𝑦 )=𝑒𝑥𝑝 (− 𝑦2

2 )𝐺3 ( 𝑦 )= 𝑦 4

4𝐽 (𝑥 )≈∑

𝑖=1

𝑛

𝑘𝑖 [𝐸 (𝐺𝑖 (𝑥))−𝐸 (𝐺𝑖(𝑥𝑔)) ]2

SEPARAÇÃO DE FONTES USANDO NEGENTROPIA

ALGORITMOS GENÉTICOS

Baseado nos mecanismo de seleção e evolução natural;

Problemas de otimizaçãoInicio

RepresentaçãoCromossômica

InicializaçãoPopulação

(Geração = 1)

Avaliação

AtendeuCondição de

Parada?

Fim

Sim

Seleção

Reprodução(Geração = Geração +1)

Não

ALGORITMOS GENÉTICOS

Representação

0 0 0 0 0 0 0 0 0 0

𝑝𝑜𝑝𝑢𝑙𝑎çã 𝑜=[ 𝑐𝑟𝑜𝑚1

𝑐𝑟𝑜𝑚2

⋮𝑐𝑟𝑜𝑚𝑁

]=[ 𝑔11 𝑔12 ⋯ 𝑔1𝑀

𝑔21 𝑔22 ⋯ 𝑔2𝑀

⋮ ⋮ ⋱ ⋮𝑔𝑁 1 𝑔𝑁 2 ⋯ 𝑔𝑁𝑀

] Inicialização da população

Avaliação

Negentropia de Rényi

ALGORITMOS GENÉTICOS

Seleção

Reprodução

Pai B

Pai A 1 0 00 1111 0 1 0

0 0 11 1100 1 0 0

11 00 11 1100 00 11 00

00 00 00 1111 11 00 00

a) Ponto do corte 

b) Resultado da recombinação

24%Cromossomo A

32%Cromossomo B

16%Cromossomo

D

28%Cromossomo C

Filho

Pai 1 0 00 1111 0 1 0

1 0 00 1100 0 1 0

RBF (Radial Basis Functions)

REDES NEURAIS ARTIFICIAIS

Neurônio artificial;

Arquiteturas: Recorrentes e Multicamadas

𝜑 (𝜉 )=𝑒𝑥𝑝(− 𝜉 2

2𝜎 2 )

MÉTODO PROPOSTO

Modelo geral estratégia linear

Armazenando essas matrizes que resultou na maior independência

s A x W y

AG(W,x,y)

A3)

Parâmetros desconhecidos

MÉTODO PROPOSTO

Modelo geral estratégia não linear

Gera novamente outro e assim armazenar o que deu maior independência.

s x𝑾 𝑒𝑥𝑝(−‖𝒔−𝑪‖2

2𝜎 2 ) 𝑾 𝑒𝑥𝑝(−‖𝒙− �̂�‖2

2𝜎2 ) y

AG(W,C,x,y)

Parâmetros desconhecidos

𝐻𝛼=1

1−𝛼𝑙𝑜𝑔¿

Entropia de Rényi para um v.a. X :

𝑘=1

√¿¿¿𝑦=𝑥−𝜇

𝐻𝛼=1

1−𝛼𝑙𝑜𝑔¿

Σ=𝛼 Σq

𝐻𝛼=1

1−𝛼𝑙𝑜𝑔¿

𝐻𝛼=1

1−𝛼𝑙𝑜𝑔¿

𝐻𝛼=1

1−𝛼log ¿

MÉTODO PROPOSTO

𝐻𝛼=1

1−𝛼𝑙𝑜𝑔¿

𝐻𝛼=1

1−𝛼log ¿

𝐻𝛼=1

1−𝛼log ¿

𝐻𝛼=1

1−𝛼log ¿

𝐻𝛼=1

1−𝛼log ¿ ¿

𝐻𝛼=0,51

1−𝛼[−d log (𝛼 )+(1−𝛼 )𝑑𝑙𝑜𝑔 (2𝜋 )+ (1−𝛼 ) log(|Σ|)]

𝐻𝛼=0,5 [−d log (𝛼 )1−𝛼

+𝑑 𝑙𝑜𝑔 (2𝜋 )+log (|Σ|)]𝐻2 (𝑋𝑔)=0,5 (𝑑𝑙𝑜𝑔 (4 𝜋 )+ 𝑙𝑜𝑔|∑|)

MÉTODO PROPOSTO

Σ≈1𝑁 ∑

𝑖(𝑠𝑖−𝑠)𝑡 (𝑠𝑖−𝑠)

Entropia quadrática de Rényi

𝐺 (𝑥 ,𝜎2 )= 1√2𝜋𝜎 𝑁

∑𝑖=1

𝑁

𝑒𝑥𝑝(−‖𝑥−𝑥𝑖‖2

2𝜎2 )

𝑓 (𝑥 )= 1𝑁 ∑

𝑖=1

𝑁

𝐺 (𝑥−𝑥 𝑖 ,𝜎2 )

MÉTODO PROPOSTO

𝑉=− log ¿

𝑉=− log ¿𝑉=− log(∫

−∞

∞ { 1𝑁∑

𝑖=1

𝑁

𝐺 (𝑥−𝑥𝑖 ,𝜎 2 )}{ 1𝑁 ∑

𝑗=1

𝑁

𝐺 (𝑥−𝑥 𝑗 ,𝜎2)}𝑑𝑥)

𝑉=− log( 1𝑁 2 ∑

𝑖=1

𝑁

∑𝑗=1

𝑁

∫−∞

∞

𝐺 (𝑥−𝑥𝑖 ,𝜎 2 )𝐺 (𝑥−𝑥 𝑗 ,𝜎2 )𝑑𝑥 )

𝑉=− log( 1𝑁 2 ∑

𝑖=1

𝑁

∑𝑗=1

𝑁

𝐺 (𝑥 𝑖−𝑥 𝑗 ,2𝜎2 ))

MÉTODO PROPOSTO

𝐽 (𝑥 )=12

(𝑑 log (4 𝜋 )+ 𝑙𝑜𝑔 (|Σ|) )−𝑙𝑜𝑔∑𝑖∑𝑗

𝐺 (𝑥 𝑖− 𝑥 𝑗 ,2𝜎2 )

Negentropia de Rényi

RESULTADOS EXPERIMENTAIS

65536 amostras

População com 16 bits para cada gene

População com 144 bits

Separação cega de fontes lineares

RESULTADOS EXPERIMENTAIS

RESULTADOS EXPERIMENTAIS

0 5 10 15 20 25 30 35 40 45 50-5

0

5x 10

-3 Fonte 1

0 5 10 15 20 25 30 35 40 45 50-0.01

0

0.01Fonte 2

0 5 10 15 20 25 30 35 40 45 50-5

0

5x 10

-3 Fonte 3

0 5 10 15 20 25 30 35 40 45 50-0.01

0

0.01Mistura 1

0 5 10 15 20 25 30 35 40 45 50-0.01

0

0.01Mistura 2

0 5 10 15 20 25 30 35 40 45 50-0.01

0

0.01Mistura 3

0 5 10 15 20 25 30 35 40 45 50-0.01

0

0.01Negentropia 1

0 5 10 15 20 25 30 35 40 45 50-5

0

5x 10

-3 Negentropia 2

0 5 10 15 20 25 30 35 40 45 50-5

0

5x 10

-3 Negentropia 3

RESULTADOS EXPERIMENTAIS

Experimento Amostras/Utilizados População Erro AG Erro P-ICA Erro FastICA

1 50/50 50 5.1818e-007 4.9440e-006 9.9365e-006

2 50/50 100 1.8315e-007 2.6616e-007 1.0328e-005

3 50/50 200 1.0785e-007 8.7361e-006 4.8179e-006

4 50/50 500 2.6961e-006 1.4256e-006 1.2347e-005

5 100/100 50 7.0970e-009 4.0143e-008 4,9859e-008

6 100/100 100 3.2528e-008 1.1351e-006 2.0106e-007

7 100/100 200 2.1759e-008 1.0717e-006 1.1719e-006

8 100/100 500 6.6869e-009 5.9524e-007 1.0514e-007

9 1000/100 50 9.0989e-013 6.8629e-010 2.8732e-010

10 1000/100 100 9.6552e-013 7.0855e-010 8.9876e-010

11 1000/67 200 1.2564e-011 6.4485e-010 4.1369e-010

12 1000/34 500 4.6911e-012 6.9532e-010 7.7314e-010

13 1000/20 500 2.6968e-011 1.5474e-011 9.0227e-010

Comparação entre modelo linear e outras abordagens

Separação cega de fontes não lineares

RESULTADOS EXPERIMENTAIS

0 20 40 60-0.2

0

0.2Fonte 1

0 20 40 60-0.5

0

0.5Fonte 2

0 20 40 602

3

4Mistura 1

0 20 40 602

3

4Mistura 2

0 20 40 60-0.5

0

0.5Negentropia 1

0 20 40 60-0.2

0

0.2Negentropia 2

0 50 100 150 200-1

-0.5

0

0.5

1x 10

-3 Mistura 1

0 50 100 150 200-1

-0.5

0

0.5

1x 10

-3 Mistura 2

0 50 100 150 200-1

-0.5

0

0.5

1x 10

-3 Negentropia 1

0 50 100 150 200-5

0

5x 10

-4 Negentropia 2

0 50 100 150 200-5

0

5x 10

-4 Negentropia e Fonte 1

0 50 100 150 200-1

-0.5

0

0.5

1x 10

-3 Negentropia e Fonte 2

População com 16 bits para cada gene

População com 640 bits𝒚=𝑾 𝑒𝑥𝑝(−‖𝒙−𝑪‖2

2𝜎2 )

RESULTADOS EXPERIMENTAIS

65536 amostras

População com 16 bits para

cada gene

População com 640 bits

𝒚=𝑾 𝑒𝑥𝑝(−‖𝒙−𝑪‖2

2𝜎2 )

0 1000 2000 3000 4000 5000-2

0

2x 10

-5 Fonte 1

0 1000 2000 3000 4000 5000-1

0

1

2x 10

-5 Fonte 2

0 1000 2000 3000 4000 5000-2

0

2x 10

-5 MIstura 1

0 1000 2000 3000 4000 5000-2

0

2x 10

-5 Mistura 2

0 1000 2000 3000 4000 5000-2

0

2x 10

-5 Negentropia 1

0 1000 2000 3000 4000 5000-1

0

1

2x 10

-5 Negentropia 2

RESULTADOS EXPERIMENTAIS

População com 16 bits para

cada gene

120 genes

População de 1920 bits

 Experimento

 Amostras

 População Nº de

centros e pesos

Kernel Entropia

Sigma base radial

Erro AG

1 3500 50 10 0,5 0,5 1,7854e-005

2 80 100 10 0,5 1 3.0396e-006

3 3500 200 10 0,5 0,5 5,7138e-004

4 16384 200 10 0,5 0,5 3,7154e-017

5 200 100 10 0,5 0,5 1,3490e-007

6 334 100 10 0,5 5 8,2305e-012

7 65536 100 10 0,5 0,5 4.0027e-017

8 5000 100 30 0,5 1 6,9189e-012

RESULTADOS EXPERIMENTAIS

Separação cega de fontes com adição de ruído

A Σ W

𝑟 (𝑛)

𝒚 (𝑛)𝒔 (𝑛)

RESULTADOS EXPERIMENTAIS

0 10 20 30-0.01

0

0.01fonte 1

0 10 20 30-0.01

0

0.01

0.02fonte 2

0 10 20 30-0.01

0

0.01fonte 3

0 10 20 30-0.02

0

0.02mistura 1

0 10 20 30-0.01

0

0.01

0.02mistura 2

0 10 20 30-0.02

0

0.02mistura 3

0 10 20 30-0.02

0

0.02negentropia 1

0 10 20 30-0.01

0

0.01negentropia 2

0 10 20 30-0.01

0

0.01negentropia 3

0 100 200 300 400-5

0

5

10x 10

-5 Fonte 1

0 100 200 300 400-4

-2

0

2

4x 10

-5 Fonte 2

0 100 200 300 400-5

0

5x 10

-5 Mistura 1

0 100 200 300 400-5

0

5x 10

-5 Mistura 2

0 100 200 300 400-5

0

5

10x 10

-5 Negentropia 1

0 100 200 300 400-4

-2

0

2

4x 10

-5 Negentropia 2

RESULTADOS EXPERIMENTAIS

𝒚=𝒙𝜎 𝒓

CONSIDERAÇÕES FINAIS Neste trabalho, propomos a aplicação GA para maximizar a Negentropia

de Rényi das misturas.

Modelo linear deve-se ajustar o parâmetro da Negentropia.

Quantidade de amostras no sinal de fontes.

No modelo não linear deve-se ajustar o parâmetro da Negentropia e da

função de base radial.

Adição de ruído gaussiano no modelo linear e não linear.

Fazer uma análise no parâmetro da Negentropia.

Testes em cenários práticos em tempo real.

Experimentos em ambientes sobre-determinados e sub-determinados.

Prova da separabilidade do modelo.

MUITO OBRIGADO!