ads:
Representações Hierárquicas de Vocábulos de
Línguas Indígenas Brasileiras: Modelos
Baseados em Mistura de Gaussianas
Lianet Sepúlveda Torres
Dissertação apresentada à Escola de En-
genharia de São Carlos da Universidade
de São Paulo, como parte dos requisitos
para obtenção do título de Mestre em Ci-
ências, Programa de Engenharia Elétrica
ÁREA DE CONCENTRAÇÃO: Processamento de Sinais e Instrumentação.
ORIENTADOR: Prof. Dr. José Carlos Pereira
São Carlos
2010
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
ii
ads:
iii
iv
Dedicatória
Aos meus pais pelo exemplo e a confiança,
A Lian por todo seu amor.
v
vi
Agradecimentos
A Lian (Mi jevi) por acreditar sempre em nosso amor, por ser minha força, pela paciên-
cia, pelo apoio, pelos momentos difíceis e pelas muitas alegrias. Todas minhas conquitas são
compartilhadas.
Agradeço aos meus pais pelo apoio até nas decisões mais difíceis, pela confiança e a cons-
tante preocupação. Apesar da distância, sempre me acompanham. Por me ensinar o que é
realmente importante na vida e por me incentivar a continuar estudando. A meu irmão que
adoro tanto. Esta conquista é para vocês em troca dos anos não compartidos.
A Esperanza e Felipe por serem meus pais no Brasil. Muito obrigada pela ajuda, a confiança
o carinho e a oportunidade de me reunir com Lian. A Indara e Orieta obrigada pela força, por
assumirem as tarefas domésticas para que eu possa terminar meu trabalho. Muito obrigada!!!
Agradeço ao Prof. José Carlos Pereira pelo apoio, a confiança e a generosidade.
Um agradecimento especial ao pessoal do laboratório “internacional” Eugenia, Edwin, So-
ledad, Anderson, Paulo, Regina, Jamile, Julian e Alan que me receberam e me apoiaram sem-
pre. Obrigada pelo apoio, a amizade, os palpites profissionais, os momentos de descontração e
pela oportunidade de aprender diferentes versões do espanhol e dificilmente o português.
A Eugenia por ser como uma irmã, pelo carinho, pelo exemplo de luta, pela guia durante
estes dois anos, pela preocupação. Agradeço por ter encontrado uma argentina como tu aqui
no Brasil. Obrigada ao Silvio (Chuchu) por me receber em sua casa e me ajudar.
“Aos maricas”!!! Amilcar, Guido e Giovani, obrigada pelos cafés, as largas conversas,
os churrascos e o mais importante pela amizade incondicional. Amilcar, muito obrigada pelas
frases matutinas de português, ainda não aprendi falar “A xícara caiu no chão sujo da chácara...”
A Edwin por ser meu palpiteiro. Agradeço cada um dos conselhos recebidos, tua ajuda foi
crucial neste trabalho.
A Regina (Rejina) e Adilson por seu esforço. Muito obrigada pelo apoio, a preocupação e
as horas falando de tudo e nada. Obrigada pelas aulas de português!!!
Aos cubanos de São Carlos, Karel (Poeta), Katiuska, Peko, Michel, Rosangela, Lita, Mi-
quel e aos argentinos, por tantas madrugadas de salsa, cerveja, risadas e discussões políticas.
vii
Aos professores que contribuíram com minha formação e que me ajudaram nestes anos,
Prof. José Carlos Pereira, Prof. Rodrigo Guido, Prof. Carlos Maciel, Prof. Marcelo BJ, Prof.
Jean Claude M‘Peko, Prof. Suely Oliveira. A professora Sandra por confiar em mim e me dar
a oportunidade de trabalhar com ela.
A CAPES pelo apoio financeiro e ao Programa de Engenharia Elétrica que me aceitou e
ajudou em cada uma de minhas dificuldades.
Agradeço ao pessoal da secretaria, Jussara e Marisa, que sempre estiveram dispostas a me
ajudar. Meu agradecimento ao pessoal de apoio técnico, Roseli e João, por arrumar meus
problemas urgentes na hora. A Vera, pelo café, a Dair, a Rui, e a Zé por sua cordialidade. As
faxineiras, aos seguranças, a todos, meus agradecimentos por fazer nossas vidas mais amenas.
Agradeço a minhas primas Ana, Alicia, Eva e Mariela pela ajuda e a preocupação nestes
anos longe da minha família.
Agradeço a minha família de Cuba, meus avos (Mima, Papi, tia Berta), minhas tias (Sandra,
Elita, Lourdes, Maria) e os meus primos, pela constante preocupação e pelo carinho. Os que já
não estão (Mimi, Pipo e Ferna), minha lembrança. Estão todos no meu coração. A família do
Lian muito obrigada pela preocupação e a Fina por suas soluções alternativas nos momentos
mais complicados.
Um agradecimento especial para meus amigos de Cuba, para esses amigos de tantos anos
que estão sempre no meu coração.
A Alexandra e Walcir muito obrigada pela ajuda e pela amizade incondicional.
A Terezinha por ter me apoiado e recebido na sua casa no primeiro ano em São Carlos.
Enfim, a cada pessoa que encontrei nestes anos, me apoiando, me criticando, me incenti-
vando,
Muito Obrigada
viii
Sumário
Lista de Figuras xi
Lista de Tabelas xv
Lista de Símbolos xvii
Lista de Siglas xix
Resumo xxi
Abstract xxiii
1 Introdução 1
2 Fundamentos Teóricos 5
2.1 Vozes Indígenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Estimativas da função de distribuição de probabilidade (PDF) . . . . . . . . . 11
2.3 Modelo baseado em mistura de gaussianas (GMM) . . . . . . . . . . . . . . . 17
2.3.1 Algoritmo Maximização da Expectância (EM) . . . . . . . . . . . . . 19
2.4 Medidas de Similaridade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5 Divergência Kulback-Leibler (KL) . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.1 Simetrização da divergência KL . . . . . . . . . . . . . . . . . . . . . 25
2.5.2 Estimativa da divergência KL entre GMM . . . . . . . . . . . . . . . 28
2.6 Agrupamento Hierárquico . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.1 Métodos aglomerativos tradicionais . . . . . . . . . . . . . . . . . . . 32
3 Materiais e Métodos 37
3.1 Banco de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.2 Arquitetura do algoritmo proposto . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.1 Experimentos na estimativa de PDF . . . . . . . . . . . . . . . . . . . 49
ix
3.3.2 Experimentos do cálculo da distância entre os modelos . . . . . . . . . 51
4 Resultados e Discussões 55
4.1 Resultados dos sinais simulados . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2 Resultados das palavras das línguas indígenas. . . . . . . . . . . . . . . . . . 59
5 Conclusões e Sugestões 77
5.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Referências Bibliográficas 81
x
Lista de Figuras
FIGURA 2.1 Tronco Linguístico Tupi . . . . . . . . . . . . . . . . . . . . . . . . 7
FIGURA 2.2 Tronco Linguístico macro-jê. . . . . . . . . . . . . . . . . . . . . . . 8
FIGURA 2.3 Família de línguas isoladas. . . . . . . . . . . . . . . . . . . . . . . 9
FIGURA 2.4 Relações entre métricas de distância usadas para simetrizar a diver-
gência KL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
FIGURA 2.5 Exemplo de representação de um dendrograma. . . . . . . . . . . . . 32
FIGURA 3.1 Diferentes etapas do sistema proposto. . . . . . . . . . . . . . . . . . 40
FIGURA 3.2 Operações realizadas no módulo de Pré-processamento. . . . . . . . 41
FIGURA 3.3 Sinal original e sinal pré-processado. . . . . . . . . . . . . . . . . . 41
FIGURA 3.4 Operações realizadas no módulo PDF . . . . . . . . . . . . . . . . . 42
FIGURA 3.5 Operações realizadas no módulo Medida. . . . . . . . . . . . . . . . 46
FIGURA 3.6 Histograma dos sinais gerados a partir de duas distribuições gaussianas. 50
FIGURA 4.1 Estimativa do GMM que representa a PDF, envoltória da mistura e o
histograma dos sinais simulados nos 3 experimentos desenvolvidos. . . . . . . 58
FIGURA 4.2 Critério BIC na seleção do número ótimo de gaussianas que integram
a mistura dos sinais simulados. . . . . . . . . . . . . . . . . . . . . . . . . . . 59
FIGURA 4.3 Estimativa do GMM que representa a PDF da palavra água dita por
10 línguas indígenas brasileiras. . . . . . . . . . . . . . . . . . . . . . . . . . 60
FIGURA 4.4 Estimativa do GMM que representa a PDF da palavra criança dita
por 10 línguas indígenas brasileiras. . . . . . . . . . . . . . . . . . . . . . . . 61
xi
FIGURA 4.5 Estimativa do GMM que representa a PDF da palavra fogo dita por
10 línguas indígenas brasileiras. . . . . . . . . . . . . . . . . . . . . . . . . . 62
FIGURA 4.6 Estimativa do GMM que representa a PDF da palavra olho dita por
10 línguas indígenas brasileiras. . . . . . . . . . . . . . . . . . . . . . . . . . 63
FIGURA 4.7 Estimativa do GMM que representa a PDF da palavra osso dita por
10 línguas indígenas brasileiras. . . . . . . . . . . . . . . . . . . . . . . . . . 64
FIGURA 4.8 Estimativa do GMM que representa a PDF da palavra sangue dita por
10 línguas indígenas brasileiras. . . . . . . . . . . . . . . . . . . . . . . . . . 65
FIGURA 4.9 Dendrograma do lote da palavra água, calculado usando a divergên-
cia KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 4.10 Dendrograma do lote da palavra criança, calculado usando a diver-
gência KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 4.11 Dendrograma do lote da palavra fogo, calculado usando a divergência
KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 4.12 Dendrograma do lote da palavra olho, calculado usando a divergência
KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 4.13 Dendrograma do lote da palavra osso, calculado usando a divergência
KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 4.14 Dendrograma do lote da palavra sangue, calculado usando a diver-
gência KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
FIGURA 4.15 Dendrograma do lote da palavra água, calculado usando a distância
Bhattacharyya. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
FIGURA 4.16 Dendrograma do lote da palavra criança, calculado usando a distância
Bhattacharyya. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
FIGURA 4.17 Dendrograma do lote da palavra fogo, calculado usando a distância
Bhattacharyya. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
FIGURA 4.18 Dendrograma do lote da palavra olho, calculado usando a distância
Bhattacharyya. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
xii
FIGURA 4.19 Dendrograma do lote da palavra osso, calculado usando a distância
Bhattacharyya. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
FIGURA 4.20 Dendrograma do lote da palavra sangue, calculado usando a distância
Bhattacharyya. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
FIGURA 4.21 Dendrograma do lote da palavra água, calculado usando a distância
Chi-quadrado de Pearson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
FIGURA 4.22 Dendrograma do lote da palavra criança, calculado usando a distância
Chi-quadrado de Pearson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
FIGURA 4.23 Dendrograma do lote da palavra fogo, calculado usando a distância
Chi-quadrado de Pearson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
FIGURA 4.24 Dendrograma do lote da palavra olho, calculado usando a distância
Chi-quadrado de Pearson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
FIGURA 4.25 Dendrograma do lote da palavra osso, calculado usando a distância
Chi-quadrado de Pearson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
FIGURA 4.26 Dendrograma do lote da palavra sangue, calculado usando a distância
Chi-quadrado de Pearson. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
FIGURA 4.27 Dendrograma do lote da palavra água, calculado usando a distância
Jensen-Shannon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 4.28 Dendrograma do lote da palavra criança, calculado usando a distância
Jensen-Shannon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 4.29 Dendrograma do lote da palavra fogo, calculado usando a distância
Jensen-Shannon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 4.30 Dendrograma do lote da palavra olho, calculado usando a distância
Jensen-Shannon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 4.31 Dendrograma do lote da palavra osso, calculado usando a distância
Jensen-Shannon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 4.32 Dendrograma do lote da palavra sangue, calculado usando a distância
Jensen-Shannon. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
FIGURA 4.33 Dendrograma do lote da palavra água, calculado usando a distância C2. 73
xiii
FIGURA 4.34 Dendrograma do lote da palavra criança, calculado usando a distância
C2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
FIGURA 4.35 Dendrograma do lote da palavra fogo, calculado usando a distância C2. 73
FIGURA 4.36 Dendrograma do lote da palavra olho, calculado usando a distância C2. 73
FIGURA 4.37 Dendrograma do lote da palavra osso, calculado usando a distância C2. 73
FIGURA 4.38 Dendrograma do lote da palavra sangue, calculado usando a distância
C2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
xiv
Lista de Tabelas
TABELA 2.1 Características das abordagens propostas para estimar a PDF de um
sinal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
TABELA 2.2 Medidas de distância mais comummente empregadas entre GMM. . . 23
TABELA 2.3 Métodos para estimar a divergência KL entre GMM. Cumprimento
das propriedades da KL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
TABELA 3.1 Línguas e dialetos armazenados na base de dados do Museu do Índio. 38
TABELA 3.2 Palavras selecionadas para analisar no presente estudo. . . . . . . . . 38
TABELA 4.1 Parâmetros que descrevem as misturas dos sinais simulados de com-
primento igual a 1000 amostras. . . . . . . . . . . . . . . . . . . . . . . . . . 56
TABELA 4.2 Cálculo do erro quadrático médio, da divergência KL, da distância de
Bhattacharyya, da divergência Chi-quadrado de Pearson, da distância Jensen-
Shannon e da distância C2 entre o histograma dos dados e o GMM. . . . . . . 57
xv
xvi
Lista de Símbolos
p
i
Probabilidade de cada célula i no histograma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
k
i
Número de ocorrências dos pontos do sinal em cada célula do histograma . . . . . 12
F
Família de funções de distribuição de probabilidades . . . . . . . . . . . . . . . . . . . . . . . . 17
k
K-ésimo componente gaussiano que pertence a mistura de gaussianas . . . . . . . . .17
m
k
Média de cada componente gaussiano k . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
σ
k
Desvio padrão de cada componente gaussiano k . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
p
k
Probabilidade de ocorrência de cada componente gaussiano k . . . . . . . . . . . . . . . . 17
Θ
Vetor que contêm os parâmetros da mistura de gaussianas . . . . . . . . . . . . . . . . . . . 17
f(x, Θ)
Definição da função de mistura de gaussianas. . . . . . . . . . . . . . . . . . . . . . . . . .17
Λ(X, Θ)
Função de máxima verossimilhança da mistura. . . . . . . . . . . . . . . . . . . . . . . .18
λ(X, Θ)
Logaritmo da função de máxima verossimilhança da mistura . . . . . . . . . . . 18
Θ
k
Conjunto de parâmetros estimados em uma iteração do EM . . . . . . . . . . . . . . . . . 19
p
(i−1)
k
Probabilidade de ocorrência da gaussiana k, estimada na iteração i − 1 do al-
goritmo EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
m
(i−1)
k
Média da gaussiana k, estimada na iteração i −1 do algoritmo EM . . . . . . . 19
σ
(i−1)
k
Desvio Padrão da gaussiana k, estimado na iteração i − 1 do algoritmo EM 19
p
(i)
(k|n)
Probabilidade de pertinência, passo Expectância do algoritmo EM . . . . . . 19
X
Variável aleatória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
H(X)
Entropia de Shannon da variável aleatória discreta X . . . . . . . . . . . . . . . . . . . . 24
χ
Alfabeto de eventos da variável aleatória discreta X . . . . . . . . . . . . . . . . . . . . . . . . . . 24
D(f||g)
Divergência KL entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
D
α
(f||g)
Entropia de Renyi entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
J(f||g)
J-Divergence entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
W (f||g)
Função weighted average entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . 26
G(f||g)
Média geométrica entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
xvii
H(f||g) Média harmônica entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
R(f||g)
Distância resistor-average entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . .27
T (f||g)
Distância Topsoe entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
C(f, g)
Distância de Chernoff entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
B(f, g)
Distância Bhattacharyya entre duas PDFs f e g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
f
i
Um componente gaussiano dos que integra a mistura. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
f(x)
Mistura de gaussianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
∆ = d(i, j)
Matrix de distância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
C
Conjunto de grupos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
l(Θ
k
)
Estimativa do logaritmo da verossimilhança na iteração k. . . . . . . . . . . . . . . . . . . . . . 43
K
Total de gaussianas na mistura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
N
Comprimento dos sinais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50
ϕ
k
Partições do algoritmo K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
N
ϕ
k
Total de elementos em cada partição do algoritmo K-means . . . . . . . . . . . . . . . . . . . . . 44
xviii
Lista de Siglas
FUNAI
Fundação Nacional do Índio. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
PDF
Função de Distribuição de Probabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
GMM
Mistura de gaussianas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
EM
Maximização da Expectância . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
KL
Kullback Leibler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3
ISA
Instituto Socioambiental . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6
HMM
Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
GGD
Generalized Gamma Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
VAD
Voice Ativity Detenction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
DFT
Transformada discreta de Fourier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
SNR
Relação sinal-ruído . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
EMD
Earth Movers Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
MFCC
Coeficientes ceptrais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
AIC
Akaike information criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26
WAVE
Waveform audio format, um tipo de codificação de áudio sem perdas . . . . . . . . . 38
GSL
GNU Scientific Library . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
MVV
Método dos Valores Verdadeiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
MVA
Método dos Valores Iniciais Aleatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
MM
Método dos Momentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43
EQM
Erro Quadrático Médio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
BIC
Bayesian Information Criterion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
xix
xx
Resumo
Sepúlveda Torres, Lianet. Representações Hierárquicas de Vocábulos de Línguas Indíge-
nas Brasileiras: Modelos Baseados em Mistura de Gaussianas. 2010. 110 f. Dissertação
(Mestrado). Escola de Engenharia de São Carlos, Universidade de São Paulo, São Carlos,
2010.
Apesar da ampla diversidade de línguas indígenas no Brasil, poucas pesquisas estudam estas
línguas e suas relações. Inúmeros esforços têm sido dedicados a procurar similaridades entre
as palavras das línguas indígenas e classificá-las em famílias de línguas. Seguindo a classifi-
cação mais aceita das línguas indígenas do Brasil, esta pesquisa propõe comparar palavras de
10 línguas indígenas brasileiras. Para isso, considera-se que estas palavras são sinais de fala
e estima-se a função de distribuição de probabilidade (PDF) de cada palavra, usando um mo-
delo de mistura de gaussianas (GMM). A PDF foi considerada um modelo para representar as
palavras. Os modelos foram comparados utilizando medidas de distância para construir estru-
turas hierárquicas que evidenciaram possíveis relações entre as palavras. Seguindo esta linha,
a hipótese levantada nesta pesquisa é que as PDFs baseadas em GMM conseguem caracterizar
as palavras das línguas indígenas, permitindo o emprego de medidas de distância entre elas
para estabelecer relações entre as palavras, de forma que tais relações confirmem algumas das
classificações. Os parâmetros do GMM foram calculados utilizando o algoritmo Maximização
da Expectância (em inglês, Expectation Maximization (EM)). A divergência Kullback Leibler
(KL) foi empregada para medir semelhança entre as PDFs. Esta divergência serve de base para
estabelecer as estruturas hierárquicas que ilustram as relações entre os modelos. A estima-
tiva da PDF, baseada em GMM foi testada com o auxílio de sinais simulados, sendo possível
confirmar que os parâmetros obtidos são próximos dos originais. Foram implementadas vá-
rias medidas de distância para avaliar se a semelhança entre os modelos estavam determinadas
xxi
pelos modelos e não pelas medidas adotadas neste estudo. Os resultados de todas as medidas
foram similares, somente foi observada alguma diferença nos agrupamentos realizados pela
distância C2, por isso foi proposta como complemento da divergência KL. Estes resultados
sugerem que as relações entre os modelos dependem das suas características, não das métricas
de distância selecionadas no estudo e que as PDFs baseadas em GMM, conseguem fazer uma
caracterização adequada das palavras. Em geral, foram observados agrupamentos entre pala-
vras que pertenciam a línguas de um mesmo tronco linguístico, assim como se observou uma
tendência a incluir línguas isoladas nos agrupamentos dos troncos linguísticos. Palavras que
pertenciam a determinada língua apresentaram um comportamento padrão, sendo identificadas
por esse tipo de comportamento. Embora os resultados para as palavras das línguas indígenas
sejam inconclusivos, considera-se que o estudo foi útil para aumentar o conhecimento destas
10 línguas estudadas, propondo novas linhas de pesquisas dedicadas à análise destas palavras.
Palavras-chaves: mistura de gaussianas, divergência KL, agrupamento hierárquico, dendro-
grama, línguas indígenas.
xxii
Abstract
Sepúlveda Torres, Lianet. Hierarchical representations of words of Brazilian Indigenous
Languages: Models Based on Gaussian Mixture. 2010. 110 p. Dissertation (Master’s).
School of Engineering-University of São Paulo, São Carlos, 2010.
Although there exists a large diversity of indigenous languages in Brazil, there are few rese-
arches on these languages and their relationships. Numerous efforts have been dedicated to
search for similarities among words of indigenous languages to classify them into families.
Following the most accepted classification of Brazilian indigenous languages, this research
proposes to compare words of 10 Brazilian indigenous languages. The words of the indigenous
languages are considered speech signals and the Probability Distribution Function (PDF) of
each word was estimated using the Gaussian Mixture Models (GMM). This estimation was
considered a model to represent each word. The models were compared using distance mea-
sures to construct hierarchical structures that illustrate possible relationships among words.
The hypothesis in this research is that the estimation of the PDF, based on GMM can charac-
terize the words of indigenous languages, allowing the use of distance measures between the
PDFs to establish relationships among the words and confirm some of the classifications. The
Expectation Maximization algorithm (EM) was implemented to estimate the parameters that
describe the GMM. The Kullback Leibler (KL) divergence was used to measure similarities
between two PDFs. This divergence is the basis to establish the hierarchical structures that
show the relationships among the models. The PDF estimation, based on GMM was tested
using simulated signals, allowing confirming the useful approximation of the original para-
meters. Several distance measures were implemented to prove that the similarities among the
models depended on the model of each word, and not on the distance measure adopted in this
study. The results of all measures were similar, however, as the clustering results of the C2
xxiii
distances showed some differences from the other clusters, C2 distance was proposed to com-
plement the KL divergence. The results suggest that the relationships between models depend
on their characteristics, and not on the distance measures selected in this study, and the PDFs
based on GMM can properly characterize the words. In general, relations among languages
that belong to the same linguistic branch were illustrated, showing a tendency to include iso-
lated languages in groups of languages that belong to the same linguistic branches. As the
GMM of some language families presents a standard behavior, it allows identifying each fa-
mily. Although the results of the words of indigenous languages are inconclusive, this study is
considered very useful to increase the knowledge of these types of languages and to propose
new research lines directed to analyze this type of signals.
Keywords: Gaussian Mixture Models, KL divergence, hierarchical clustering, dendogram, in-
digenous languages.
xxiv
Capítulo 1
Introdução
As línguas dos povos descrevem a história, a cultura, o desenvolvimento natural e as ca-
racterísticas individuais de cada pessoa. O estudo das línguas de nossos antepassados contri-
buem para a compreensão dos fundamentos de nossas origens. Muitas línguas desapareceram,
perdendo-se com elas informações relevantes relacionadas com a espécie humana (Crystal,
2000). O estudo das línguas indígenas ajuda a entender a história migratória da humanidade. A
grande maioria das línguas indígenas faladas atualmente no mundo estão, de fato, ameaçadas
de extinção, devido à globalização dos valores econômicos, sociais e culturais (Maia, 2006).
Segundo a Fundação Nacional do Índio (FUNAI), o Brasil é um dos países em que há maior
diversidade de línguas no mundo. Atualmente, existem cerca de 225 comunidades indígenas,
as quais falam 180 línguas diferentes e estão distribuídas do norte ao sul do território brasileiro.
Estudos linguísticos mostraram que algumas destas línguas são semelhantes entre si, evi-
denciando influências mutuas, origens comuns e processos de diversificação que ocorreram ao
longo do tempo (Nolazco et al., 2005; Rodrigues, 1986). Conhecer o vasto repertório destas
línguas e suas relações tem sido um desafio para os linguistas. Contudo, considerando origens
comuns, os linguistas constroem famílias de línguas, estabelecendo similaridades entre elas. A
classificação mais aceita de troncos linguísticos e famílias de linguísticas para as línguas indí-
genas brasileiras foi publicada em Rodrigues (1986) e mostra diversas relações de semelhanças
entre este tipo de línguas.
Na literatura, uma das técnicas mais comuns para comparar palavras de línguas indígenas
consiste em estudar o comportamento estatístico tanto de vogais como de consoantes (Maia
et al., 1998). Em geral, estes trabalhos se concentram em procurar o conjunto de fonemas com
1
maior ocorrência em cada língua, assim como aqueles fonemas com características articulató-
rias similares entre várias línguas indígenas. Em Maia et al. (1998), foram estudadas algumas
similaridades entre línguas indígenas brasileiras e de outras nações.
A linguística também dedicou e continua dedicando vários estudos ao que chama de clas-
sificação genética das línguas indígenas. Nesta classificação, o linguista compara listas de
palavras de línguas diferentes para ver se pertencem a uma mesma família. Compara também
listas de palavras de uma mesma família com outras palavras que pertencem a outras famílias
para ver se há semelhanças suficientes para considerar que tais famílias pertencem a um mesmo
tronco linguístico (Francheto, 1999).
Embora tais trabalhos apresentem resultados bastante expressivos, ainda há muito a fazer
em termos de estudar as diferentes línguas indígenas. Contudo, à medida que as línguas forem
sendo descritas, novas bases de dados poderão ser construídas, o que propiciará a obtenção
de mais resultados sobre o comportamento dos sons vocálicos e consonantais nas línguas do
mundo (Cândido e Ribeiro, 2007), além de encontrar novas classificações e relações entre este
tipo de línguas.
Seguindo esta linha e motivados pela diversidade linguística existente no Brasil, no pre-
sente trabalho se levanta a seguinte questão de pesquisa: Utilizar métodos de processamento
digital de sinais de fala para analisar similaridades entre línguas indígenas brasileiras serviria
de suporte para as classificações e relações publicadas em Rodrigues (1986)?
Proposta de Solução
Em aplicações dedicadas ao processamento digital de sinais de fala é comum a estimativa
da função de distribuição de probabilidade (PDF) (Gazor e Zhang, 2003b), produzindo uma
representação compacta do sinal, que depende de um reduzido número de parâmetros e pos-
sibilita o uso de medidas de similaridades, com a finalidade de comparar estes modelos. Esta
estimativa constitui uma alternativa muito eficiente para pesquisar as propriedades dos sinais,
além de ser muito utilizada em algoritmos dedicados à classificação (Archambeau e Verleysen,
2003).
Existem basicamente três abordagens para estimar a PDF de um sinal: paramétrica, não-
paramétrica e semiparamétrica (Erdogmus e Principe, 2006). Neste trabalho, propõe-se estimar
a PDF das palavras usando uma abordagem semiparamétrica, baseada em uma mistura de gaus-
sianas (GMM). Os modelos baseados em mistura de gaussianas têm sido muito usados devido
2
à precisão na aproximação dos dados e à simplicidade na estimativa dos parâmetros usando o
algoritmo Maximização da Expectância (EM) (Huber et al., 2008; Lan et al., 2006).
Na literatura, existem diversas alternativas para calcular similaridade entre modelos basea-
dos em PDFs. Uma das medidas de divergência mais usada é a entropia relativa, mais conhe-
cida como divergência Kullback Leibler (KL) (Cover e Thomas, 1991). A divergência KL é um
coeficiente assimétrico que avalia separação ou disparidade entre duas PDFs. Esta divergência
é usada em diferentes sistemas dedicados ao reconhecimento de fala ou de imagem (Hershey e
Olsen, 2007). Segundo Hershey e Olsen (2007) é necessário modificar a divergência KL, com
a finalidade de construir uma medida de distância entre as PDFs. O termo “modificar” se refere
à operação de simetrização da divergência KL. O uso da divergência KL é muito difundido em
diversas áreas da ciência, sendo muito natural a sua utilização entre GMM, em aplicações de
reconhecimento de fala e de imagem (Hershey e Olsen, 2007).
Em Scalassara et al. (2009a) o uso da divergência KL para sinais de fala, considerando
uma abordagem estocástica, obteve resultados muito interessantes na diferenciação de vozes
normais e patológicas. O autor mostrou o uso desta divergência, para medir semelhanças entre
PDFs, como uma medida promissora, mas reporta que seu resultado depende da exatidão na
estimativa da PDF dos sinais.
A hipótese levantada nesta pesquisa é que as PDFs baseadas em GMM conseguem carac-
terizar as palavras das línguas indígenas, permitindo o emprego de medidas de distância entre
elas para estabelecer relações entre as palavras, de forma que tais relações confirmem algumas
das classificações realizadas em Rodrigues (1986).
Objetivos e Resultados Esperados
O principal objetivo deste trabalho é definir um modelo para representar vocábulos perten-
centes a línguas indígenas brasileiras e empregar medidas de distância entre os modelos para
construir estruturas hierárquicas que evidenciem possíveis relações entre os vocábulos a serem
estudadas.
Nossa abordagem considera as palavras das línguas indígenas como sinais de fala e pre-
tende estimar as PDFs destas palavras usando uma mistura de gaussianas. A PDF, baseada em
GMM é o modelo selecionado para representar as palavras das línguas indígenas. A compara-
ção entre estes modelos é realizada empregando a divergência KL.
Mais especificamente, tem-se como objetivos: (a) considerar as limitações do algoritmo
3
EM na sua implementação para obter uma aproximação adequada dos parâmetros da mistura,
(b) propor um método computacional para estimar a divergência KL entre GMM e utilizar uma
função eficiente para simetrizar esta divergência, e (c) verificar se as relações encontradas entre
os modelos dependem da divergência KL ou dos modelos estimados para cada vocábulo.
Dentre as principais contribuições do trabalho, destaca-se a implementação de um algo-
ritmo para comparar as palavras. Primeiramente, as PDFs baseadas em GMM são estimadas
através da implementação do método EM. Este método calcula os parâmetros que descrevem
a mistura. As principais limitações do EM são superadas no desenvolvimento do algoritmo,
dado que se considera que elas influenciam no desempenho do mesmo. Após a estimativa das
PDFs, o sistema calcula a divergência KL entre os modelos para formar a matriz de distância
que será empregada como critério de similaridade. Finalmente, o sistema implementa um al-
goritmo de agrupamento hierárquico, baseado na matriz KL, para construir os dendrogramas.
Estes dendrogramas mostram as principais relações entre os modelos estimados. Estas relações
podem ser consideradas como possíveis associações entre as palavras indígenas utilizadas na
presente pesquisa. As palavras das línguas indígenas selecionadas para análise pertencem a 10
línguas indígenas do Brasil. Estas línguas são faladas atualmente no território brasileiro e a sua
documentação está na base de dados do Museu do Índio do Brasil
1
.
Neste estudo não se espera encontrar relações definitivas entre as palavras indígenas ana-
lisadas. Consideramos esta pesquisa como uma alternativa para encontrar novas ideias que
contribuam com o conhecimento destas línguas, possibilitando a implementação de trabalhos
futuros, em que exista uma integração de profissionais de diversas áreas que dediquem esforços
ao estudo de línguas indígenas brasileiras.
O presente trabalho está organizado em 5 capítulos. O Capítulo 2 descreve os fundamentos
teóricos, que sustentam os métodos implementados, além disso inclui uma revisão bibliográ-
fica, na qual são tratados alguns dos trabalhos que utilizam as técnicas desenvolvidas nesta
pesquisa para diversas aplicações. No Capítulo 3, Materiais e Métodos, é apresentado o banco
de dados que foi analisado e as implementações realizadas, fornecendo uma explicação deta-
lhada do algoritmo. No Capítulo 4, são apresentados e discutidos os resultados alcançados.
Finalmente, no Capítulo 5, se mostram as conclusões obtidas e os trabalhos futuros.
1
http://www.museudoindio.org.br/
4
Capítulo 2
Fundamentos Teóricos
Este capítulo apresenta os fundamentos teóricos necessários para o desenvolvimento do
trabalho. O capítulo é dividido em quatro seções. Na primeira seção é descrito o panorama das
línguas indígenas que existem hoje no Brasil, algumas de suas características e os diferentes
grupos linguísticos identificados. Também se descrevem trabalhos dedicados a resgatar estas
línguas. Depois é apresentada a teoria relacionada com os métodos de estimativa da função
distribuição de probabilidade (PDF), junto com as principais abordagens responsáveis pelo
cálculo da PDF, além disso, são comentados diversos estudos nos quais estes métodos têm sido
empregados. Na terceira parte do capítulo são abordadas algumas das métricas utilizadas para
medir divergência entre modelos, especialmente o uso da divergência Kullback Leibler (KL)
como medida de similaridade e suas características fundamentais. Por último, apresenta-se
uma introdução da teoria relacionada com os métodos de agrupamento hierárquico.
2.1 Vozes Indígenas
A língua é o meio mais eficiente para transmitir nossas culturas. A sociedade em geral
perde quando alguma das línguas de nossos antepassados morre, mas são os membros das dife-
rentes comunidades quem perdem mais quando a língua desaparece. O termo “a língua morre”
se refere a uma língua que desaparece. Segundo Cristófaro-Silva (2002) há pelo menos três
casos concretos de morte de línguas. O primeiro caso está relacionado às situações em que o
pesquisador não pôde investigar o processo de desaparecimento da língua porque havia apenas
um ou simplesmente uns poucos falantes vivos. O segundo caso está relacionado à opressão
política imposta aos falantes de uma determinada língua, os quais deixam de falar a língua com
5
o objetivo de não serem identificados como membros de uma comunidade específica. O último
caso está relacionado com aquela língua que deixa de ser usada coloquialmente e é mantida
apenas em situações de ritual. Nos casos anteriores o processo de desaparecimento das línguas
ocorre em um curto espaço de tempo, impossibilitando a descrição deste processo. Cada povo
tem se adaptado a circunstâncias únicas e as línguas destes povos as expressam (Nolazco et al.,
2005). Por isso, é importante dedicar esforços à preservação e ao estudo das línguas de nossos
antepassados.
Estima-se que existam hoje no mundo pelo menos 5 mil povos indígenas, somando cerca
de 350 milhões de pessoas. O Brasil é um país onde há uma grande diversidade de línguas
indígenas, muitas delas em perigo de extinção. Segundo os dados do Instituto Socioambiental
(ISA)
1
, atualmente no território brasileiro se encontram 233 povos, falantes de mais de 180
línguas diferentes. A maior parte dessa população distribui-se por milhares de aldeias, situadas
no interior de 653 terras indígenas, de norte a sul do território brasileiro.
Dentre as cerca de 180 línguas indígenas que existem no Brasil, algumas são semelhantes
entre si mais do que outras, revelando origens comuns e processos de diversificação ocorridos
ao longo do tempo. Os linguistas expressam as semelhanças e as diferenças entre elas através
da ideia de troncos e famílias linguísticas. Quando se fala em tronco, tem-se em mente línguas
cuja origem comum está situada há milhares de anos, sendo as semelhanças entre elas muito
sutis (Seki, 2000). O termo família se refere a “línguas que têm uma origem comum; em que
houve uma língua-mãe que em tempos antigos, pertencia a uma etnia só” (Francheto, 1999).
No Brasil, a classificação em troncos e famílias linguísticas indígenas mais aceita foi publi-
cada por Rodrigues (1986). O estudo define dois grandes troncos: o tupí e o macro-jê e mais 20
famílias linguísticas que não apresentam um suficiente grau de similaridade para que possam
ser agrupadas em um tronco. Estas 20 famílias são denominadas de línguas isoladas, as quais
não são parecidas com nenhuma outras das línguas conhecidas e integram grupos individuais.
Na Figura 2.1, são mostradas as línguas que integram o tronco tupí, que é o maior e mais
falado. Como se observa na figura, este tronco inclui dez famílias e cada família agrupa várias
línguas; em alguns casos existem diferentes dialetos. A família tupí-guarani caracteriza-se por
grande dispersão geográfica: suas línguas são faladas em diferentes regiões do Brasil e também
em outros países da América do Sul (Bolívia, Peru, Venezuela, Guiana Francesa, Colômbia,
Paraguai e Argentina). As demais famílias do tronco tupí estão todas localizadas no território
1
http://www.socioambiental.org/
6
Figura 2.1: Tronco Linguístico Tupi. (*) Língua Geral Amazônica (Nheengatu). É Amazô-
nica para distinguir da outra Língua Geral, a Paulista, agora já extinta. (**) Puruborá é um
povo para cuja língua há documentos dos anos 20 e dos anos 50. Imagem modificada de
http://pib.socioambiental.org/pt/c/no-brasil-atual/línguas/troncos-e-famílias
brasileiro, ao sul do Rio Amazonas (Seki, 2000).
Na Figura 2.2, é mostrado o tronco macro-jê que está representado por 9 famílias e é
considerado um tronco grande e importante. A família jê é a maior, constituída por várias
línguas e dialetos. Em geral, as línguas deste tronco são faladas no Centro-Oeste, no sul, no
Pará e na Amazônia meridional e são exclusivamente brasileiras (Seki, 2000; Francheto, 1999).
Na Figura 2.3, são ilustradas as famílias de línguas isoladas. Estas famílias não formam
troncos, pois “constituem tipos linguísticos únicos” (Seki, 2000). Cada uma destas famílias
estão integradas por um conjunto de línguas e encontram-se espalhadas por todo o território
brasileiro (Francheto, 1999).
O número existente de línguas indígenas brasileiras representa uma grande diversidade
linguística, que respeita tanto a organização dos sistemas de sons quanto a estrutura gramatical
(Seki, 2000). Atualmente, busca-se no Brasil praticar uma política de preservação e defesa das
línguas indígenas, combatendo o preconceito, incentivando a pesquisa e o estudo destas línguas
(Francheto, 1999).
7
Figura 2.2: Tronco Linguístico macro-jê. Imagem modificada de
http://pib.socioambiental.org/pt/c/no-brasil-atual/linguas/troncos-e-familias
Diversos trabalhos (Olson e Mielke, 2007; Parker, 2007; Nolazco et al., 2005; Kroeker,
2003) têm sido desenvolvidos na procura de resgatar algumas das informações das línguas de
nossos antepassados e de alguns dos povos indígenas que ainda existem em diferentes pontos
do mundo. A maioria dos trabalhos já realizados restringem-se à investigação dos segmentos
vocálicos e, em número menor, são os que tratam dos segmentos consonantais. Em geral, os
trabalhos revisados “constituem-se metodologicamente como tentativas de classificar tipolo-
gicamente os sistemas fonológicos das línguas com base no seu número de séries consoantes
(oclusivas, nasais, fricativas, entre outras) ou de vogais (alta, baixas, anteriores posteriores,
entre outras)”(Cândido e Ribeiro, 2007). Ainda são poucas as pesquisas dedicadas ao conhe-
cimento de línguas indígenas ou aquelas línguas que descrevem o patrimônio linguístico de
determinados povos, mas existem alguns exemplos isolados, mencionados abaixo.
O México é um dos países na América onde atualmente há ainda comunidades indígenas.
As línguas Huestec e Náhuatl são bem conhecidas por serem as línguas do império Azteca e
Maia, respectivamente. Estas línguas originalmente eram escritas como uma mistura de figuras
e quando os espanhóis chegaram ao território mexicano uma das primeiras tarefas foi adaptá-las
ao alfabeto espanhol. Geralmente, as palavras nestes tipos de línguas são extensas, incluindo
8
Figura 2.3: Família de línguas isoladas. Imagem modificada de
http://pib.socioambiental.org/pt/c/no-brasil-atual/linguas/troncos-e-familias.
9
muita informação e o número de palavras não é muito grande. Em Nolazco et al. (2005) foi
criada uma base de dados com frases pertencentes as línguas Huestec e Náhuatl. Um sistema
de reconhecimento automático da fala foi aplicado às palavras inseridas na base de dados,
usando Hidden Markov Models (HMM) como modelo acústico das palavras, construindo um
dicionario de pronunciação e mostrando todos os resultados obtidos para cada uma das línguas
analisadas.
Parker (2007) teve como propósito documentar as principais características acústicas de
uma variedade do Quéchua
2
falado em Cusco, em Peru. O estudo apresenta os resultados de
medição da duração e da intensidade, tanto das consoantes como das vogais, além de obter a
frequência fundamental e os três primeiros formantes de cada uma das vogais que integram a
língua. Um dos resultados principais do trabalho é a geração de um resumo das características
mais interessantes e relevantes da fonética acústica do Quéchua falado em Cusco.
O trabalho de Olson e Mielke (2007) apresenta um estudo preliminar das propriedades
acústicas das vogais que pertencem à língua Kagayanen. Kagayanen é um língua pouco co-
nhecida no mundo, mais comum nas Filipinas (Olson e Mielke, 2007). O trabalho examina a
estrutura dos formantes de cada vogal da língua com a finalidade de avaliar o comportamento
fonético das vogais.
Ainda são muito poucas as línguas indígenas brasileiras que foram documentadas, sendo
que diversos estudos (Kroeker, 2003; Seki, 2000; Maia et al., 1998) têm se dedicado a pesqui-
sar o comportamento fonológico de algumas das línguas. Um dos trabalhos encontrados na
literatura foi o de Kroeker (2003), o qual se dedica a estudar a língua Nambikuara. Esta língua
é classificada como uma língua isolada, e se ilustra na Figura 2.3. No trabalho foi analisado
o problema de condicionamento vocálico na língua Nambikuara examinando se a mudança
de amplitude ou de extensão estimula a mudança do caráter da vogal. Primeiramente, foram
estabelecidas as normas para as vogais Nambikuara, passando depois a observá-las em diver-
sos ambientes para se analisar os fatores responsáveis pelas mudanças notadas no caráter das
mesmas.
Após conhecer as características principais das línguas indígenas brasileiras, além dos es-
tudos que abordam a análise deste tipo de línguas, na próxima seção são apresentados alguns
dos métodos matemáticos e ferramentas propostas na literatura para a modelagem de sinais de
2
Também chamado de Quíchua ou Quéchua, é uma importante língua indígena da América do Sul, ainda hoje
falada por cerca de dez milhões de pessoas de diversos grupos étnicos da Argentina, Bolívia, Chile, Colômbia,
Equador e Peru ao longo dos Andes (Parker, 2007).
10
fala. Também serão comentadas as medidas de semelhanças mais usadas para comparar este
tipo de modelos.
2.2 Estimativas da função de distribuição de probabilidade (PDF)
Atualmente, em aplicações dedicadas ao processamento de sinais de fala, tem sido interes-
sante representar o sinal através de modelos. Em geral, estes modelos fornecem uma represen-
tação compacta do sinal, mantendo as informações mais relevantes dele (Shin et al., 2005). A
estimativa da PDF de um sinal se considera uma parte essencial na eficácia de diversos algo-
ritmos empregados para o processamento da fala (Shin et al., 2005; Gazor e Zhang, 2003b).
Dependendo de um reduzido número de parâmetros, esta função descreve a distribuição de
probabilidade que seguem os sinais. Por isso, modelos probabilísticos baseados na PDF do
sinal são comumente usados para representar sinais de fala. O sucesso destas representações
do sinal depende do modelo que tem sido definido.
Em áreas como aprendizado de máquina e processamento digital de sinais, a estimativa
da PDF representa uma constante preocupação, devido ao fato dela proporcionar uma base
sólida na construção de ferramentas de processamento de dados, contribuindo na seleção das
características dos sinais. Além disso, esta estimativa é crucial em algoritmos de aprendizagem
não supervisionado (em inglês, unsupervised learning), em métodos de inferência Bayesiana e
em diferentes técnicas de classificação (Raykar, 2002).
Existem basicamente três abordagens para estimar a PDF de um sinal: paramétrica, não-
paramétrica e semiparamétrica (Scalassara et al., 2009b; Erdogmus e Principe, 2006; Gray e
Moore, 2003). Estas alternativas são empregadas como soluções de diversos problemas, mas
não existe um consenso universal na escolha destas abordagens para solucionar determinados
problemas, por isso diversos estudos são dedicados ao emprego das alternativas em cada um dos
problemas existentes (Gray e Moore, 2003). A seguir são comentadas as abordagens anteriores,
assim como o uso delas em diversos sistemas dedicadas ao processamento de sinais.
Abordagem não-paramétrica
Os métodos não-paramétricos não fazem nenhuma consideração da distribuição de proba-
bilidade dos dados. Em geral, estes métodos se caracterizam por conseguir uma estimativa ade-
quada para qualquer conjunto de dados que recebem como entrada. Entretanto, essa vantagem
é difícil de se obter, pelo fato do custo computacional ser intratável. A técnica não-paramétrica
11
mais comumente usada é a estimativa da PDF através do histograma das amostras do sinal. Este
método é pobre quando não é suficiente o número de amostras do sinal, neste caso, o método
baseado em Kernel é o mais comumente utilizado (Gray e Moore, 2003). Neste documento o
termo Kernel se refere a uma função simétrica, não necessáriamente positiva e cuja integral em
todo o domínio R é 1.
Na estimativa não-paramétrica existem duas técnicas que são as mais conhecidas, uma
delas é a estimativa do kernel (em inglês, Kernel density estimation) (Gray e Moore, 2003), e
a outra é baseada em histogramas (Scalassara, 2009). Considerando a técnica de histogramas,
pode-se ter células de tamanho fixo ou variável, conforme a distribuição local dos dados ou
obtidas por janelas móveis retangulares. A grande dificuldade da técnica de histogramas é a
determinação do comprimento das células (Ku e Kawasumi, 2008). Se, ao invés de uma janela
retangular, fosse usada uma função diferente, o método passaria a ser chamado de estimativa
do kernel (Erdogmus e Principe, 2006), em que se define uma função com as características
mencionadas no parágrafo anterior.
Em Scalassara et al. (2009b) emprega-se a abordagem não-paramétrica baseada em histo-
gramas, tanto para células de tamanho fixo como para as de tamanho variável, para estimar
a PDF das amostras dos sinais vocálicos. Usando a estimativa do histograma, os autores cal-
culam a entropia empregando diferentes métodos. Para estimar a PDF do sinal estudado em
Scalassara et al. (2009b), divide-se essa função contínua em um reticulado com i células igual-
mente espaçadas. Assim, a probabilidade p
i
, de cada célula i é estimada por
k
i
N
, sendo que k
i
é o número de ocorrências dos pontos do sinal em cada célula, N é o total de amostras do sinal
e ∆x é a largura da célula.
Abordagem Paramétrica
A abordagem paramétrica é geralmente usada quando a distribuição dos dados é conhe-
cida antecipadamente ou quando os dados são simples de forma que permitam ser modelados
usando uma distribuição conhecida, por exemplo gaussiana, Gamma, Laplace, etc (Gray e Mo-
ore, 2003). Para estimar os parâmetros da distribuição selecionada existem vários métodos,
dentre os mais empregados encontram-se a estimativa de máxima verossimilhança e a estima-
tiva Bayesiana (Viola et al., 1996). Esta abordagem às vezes é inapropriada devido ao fato
dela considerar uma forma paramétrica para a distribuição que seguem os dados (Scalassara,
2009); resultando uma estimativa da PDF que somente será satisfatória se a suposição inicial
da distribuição dos dados for correta (Gray e Moore, 2003).
12
Considerando uma abordagem paramétrica, diversos estudos (Gopinath et al., 2008; Chang
et al., 2006; Gazor e Zhang, 2003b) apresentam-se na literatura para estimar a PDF de sinais de
fala. Nos trabalhos, dedicam-se inúmeros esforços na procura da distribuição de probabilidade
que melhor se aproxima aos dados iniciais. Geralmente, a maioria dos algoritmos convencio-
nais de processamento de sinais, que adotam modelos probabilísticos, assumem que a melhor
aproximação do espectro da fala se consegue com a distribuição gaussiana (Shin et al., 2005).
Em Gazor e Zhang (2003b), com o objetivo de procurar a função de distribuição que apro-
ximava os dados de forma mais exata, o sinal de fala foi representado em diversos domínios.
O trabalho realiza alguns ensaios considerando a distribuição gaussiana, a Gamma e a La-
place, alcançando os melhores resultados quando é empregada a distribuição de Laplace. Os
autores notaram que em ambientes em que a fala está combinada com trechos de silêncio a
melhor aproximação da PDF se conseguia utilizando a distribuição Gamma Generalizada (em
inglês, Generalized Gamma Distribution (GGD)) . Esta função combina no mesmo modelo a
distribuição gaussiana, a Laplace e a Gamma.
Em Gopinath et al. (2008) foi proposta uma abordagem paramétrica para estimar a distri-
buição de probabilidade das vogais da língua Índia Malayalam. As funções de distribuição
Normal, a LogNormal, a Gamma e a Weibull foram utilizadas para determinar a melhor esti-
mativa da duração dos fonemas, usando o método Q-Q plot
3
. Diversos ensaios mostraram que
a função Gamma garante a melhor aproximação da PDF dos fonemas.
Em Chang et al. (2006) se apresenta um algoritmo detector de atividade da voz (em in-
glês, Voice Ativity Detenction (VAD))
4
baseado em múltiplos modelos estatísticos. O principal
objetivo do trabalho foi descobrir as propriedades dos modelos estatísticos, que descrevem o
espectro de um sinal de fala com ruído. Sabe-se que quase todos os algoritmos convencionais
de VAD operam no domínio da frequência e assumem que a fala livre de ruído e o ruído são
caracterizados por uma distribuição gaussiana (Chang et al., 2006). Pesquisas recentes (Gazor
e Zhang, 2003a; Martin e Breithaupt, 2003) indicam que a PDF dos coeficientes da transfor-
mada discreta de Fourier (DFT) , do sinal livre de ruído e do ruído são aproximadas de forma
mais eficiente usando a distribuição Gamma e Laplace. No trabalho de Chang et al. (2006)
propõe-se representar a distribuição de cada coeficiente discreto de Fourier usando, além da
3
Q-Q plot, é uma técnica gráfica para determinar se dois conjuntos de dados provêm de populações com distri-
buições comuns.
4
Voice Activity Detector (VAD) , refere-se a o problema clássico de distinguir entre uma fala ativa e momentos
de silencio e é aplicado por muitos sistemas de comunicação como codificação da voz (em inglês, speech coding),
reconhecimento da fala (em inglês, speech recognition) e melhoria do sinal (em inglês, noise speech enhancement).
13
distribuição gaussiana, a Laplace e a Gamma. Os diferentes modelos são avaliados usando o
teste Kolmogorov-Smirnov
5
. Entre os principais resultados do trabalho de Chang et al. (2006)
se destaca a conveniência em aplicar diferentes modelos estatísticos para representar a PDF
dos coeficientes de Fourier de um sinal de fala com ruído, dependendo da relação sinal-ruído
(SNR) que o sinal apresente. Além disso, se o modelo escolhido para aproximar a PDF é para-
métrico, as funções de distribuição que se apresentam como fortes candidatas são a Laplace e
Gamma.
Abordagem semiparamétrica
A abordagem semiparamétrica (misturas ou redes neurais) combina a flexibilidade da abor-
dagem não-paramétrica e a eficiência na avaliação dos parâmetros da abordagem paramétrica
(Ku e Kawasumi, 2008; Raykar, 2002). Estes modelos utilizam um número de funções base
que são sempre menores que o conjunto de treinamento. Em geral, são caracterizados por pro-
cedimentos de otimização não lineares que às vezes encontram soluções localmente ótimas que
dependem dos critérios de partida do algoritmo EM. Os modelos semiparamétricos conseguem
aproximar qualquer tipo de dados, para isso é preciso que o número de componentes tenda ao
infinito, mas se isso acontecer o custo computacional seria muito elevado.
Em Ku e Kawasumi (2008) foi proposta uma abordagem semiparamétrica para analisar
a estacionaridade de um sinal usando o método de estimativa do kernel. A função de dis-
tribuição Gamma é embutida no kernel para estimar a melhor ordem do modelo e os coefi-
cientes que o descrevem. Os parâmetros da função Gamma são estimados usando o método
de máxima verossimilhança. Como resultados importantes do trabalho tem se o uso de uma
abordagem semiparamétrica que reúne as vantagens das outras duas abordagens: paramétrica e
não-paramétrica, obtendo um modelo de ordem inferior e estimando os coeficientes que melhor
descrevem o modelo.
O uso dos modelos semiparamétricos baseados em GMM, tem se apresentado como uma
ferramenta amplamente usada na estimativa da PDF de qualquer sinal. Em comparação com
os conhecidos métodos paramétricos, esta ferramenta se mostra como a mais poderosa para
estimar a família de funções de distribuição. Comparando-a com os métodos não-paramétricos
propostos na literatura, como é o caso da estimativa do Kernel, o custo computacional desta
técnica é menor (Lan et al., 2006). Embora o modelo baseado em GMM demande uma conside-
5
teste Kolmogorov-Smirnov é usado para determinar se duas distribuições de probabilidade subjacentes diferem
uma da outra ou se uma das distribuições de probabilidade subjacentes difere da distribuição em hipótese, em
qualquer dos casos com base em amostras finitas.
14
rável quantidade de parâmetros e, para obter uma estimativa da PDF robusta requer um grande
conjunto de dados, este tem se convertido em uma abordagem muito usada para descrever a
PDF de um sinal de fala de forma semiparamétrica (Shin et al., 2005).
Segundo Dustor e Szware (2009) os modelos baseados em GMM possuem a habilidade de
capturar todas as flutuações ou variações da voz e como resultado podem modelar as propri-
edades fundamentais da fala de qualquer língua. Dustor e Szware (2009) apresentaram uma
abordagem para reconhecimento automático da fala baseada em reconhecimento estatístico de
padrões. Para a pesquisa foram escolhidas várias palavras de dez línguas de diferentes países.
Neste caso, as palavras das línguas selecionadas são representadas como uma combinação li-
near de M funções gaussianas, em que cada distribuição é especificada pelo vetor de médias
m
i
, a matriz de co-variância C
i
e a probabilidade de ocorrência p
i
. O conjunto de parâmetros
que descrevem o modelo é calculado usando o procedimento iterativo EM, que será descrito
na Seção 2.3.1. Os testes foram desenvolvidos a partir das palavras selecionadas, destacando
que o método é adequado para a identificação de cada uma das línguas envolvidas, porém o
número de componentes gaussianas que pertencem à estimativa é decisivo para uma correta
identificação.
Em Nan et al. (2009) apresenta-se uma modificação do algoritmo Tail-fitting
6
. O algoritmo,
em vez de estar baseado no histograma dos dados, toma como base uma mistura de gaussia-
nas. No trabalho, propõe-se calcular o número máximo de componentes da mistura usando o
conceito de curtose
7
, provendo um critério de exatidão entre o modelo aproximado e os dados
reais. Os parâmetros da mistura são estimados usando o algoritmo EM, e em cada iteração, o
algoritmo atualiza o número de componentes gaussianos, assim como o número de parâmetros
de cada componente através da medição da curtose e da máxima verossimilhança.
Em Chen et al. (2001), apresenta-se um método baseado em GMM para identificar diferen-
tes acentos da língua Chinesa Mandarim. No trabalho, o número de componentes da mistura é
treinado para obter a aproximação mais exata da estimativa. Diversos testes realizados indica-
ram que a escolha certa do número de componentes que integram a mistura pode contribuir na
precisão do modelo para uma correta identificação dos diversos acentos das línguas. O estudo
sugere que o modelo construido seja composto por 32 elementos para manter uma compensa-
6
Tail-fitting é um método muito popular para separar o jitter determinístico do jitter aleatório.
7
Curtose é uma medida de dispersão que caracteriza o “achatamento ”da curva da função de distribuição. É
normalmente definida como:
m
4
(µ)
σ
4
− 3. em que m
4
(µ) é o quarto momento central e σ é o desvio-padrão
15
ção entre exatidão da estimativa e custo computacional.
Considerando que a mistura de gaussianas é um modelo capaz de aproximar qualquer dis-
tribuição de probabilidade e que qualquer componente dos que integram a mistura pode re-
presentar o espectro de qualquer falante, Reynolds e Rose (1995) usaram este tipo de modelo
para implementar um algoritmo dedicado à identificação do locutor independente do texto (em
inglês, Text-independent Speaker Identification). Embora o trabalho destaca como crítico no
treinamento do modelo baseado em GMM a escolha do número máximo de componentes que
integram o modelo e a inicialização dos parâmetros, diversos ensaios mostraram que este tipo
de modelo provê uma representação robusta para a difícil tarefa de identificar um falante, sobre
um sinal de fala corrompido ou sem restrições.
Tabela 2.1: Características das diferentes abordagens, Não-Paramétrica, Paramétrica e Semi-
paramétrica, propostas para estimar a PDF de um sinal.
Não-paramétrica Paramétrica Semiparamétrica
Características - Não considera a - É usada quando a - Combina a flexibilidade da
distribuição dos distribuição dos dados é abordagem não-paramétrica
dados; conhecida ou quando os com a eficiência da avaliação
- Consegue uma dados são simples. dos parâmetros da
estimativa abordagem paramétrica;
adequada para - Consegue aproximar
qualquer conjunto qualquer tipo de dados.
de dados.
Funções Janela retangular, Ganma, Laplace, - Misturas
função Ganma e gaussianas e Weibull. - Redes Neurais
gaussianas.
Métodos ou - Histograma; - Estimativa da máxima - Estimativa da máxima
Estimativa dos - Estimativa do verossimilhança; verossimilhança (Algoritmo
parâmetros Kernel. - Estimativa Bayesiana. EM).
Considerações Tamanho das Distribuição que melhor Cálculo dos parâmetros.
células. aproxima os dados.
Aplicações - Estimativa da - PDF das vogais da - Estimar estacionaridade
Entropia língua Índia Malayalam de um sinal (Ku e Kawasumi,
(Scalassara et al., (Gopinath et al., 2008); 2008);
2009b). - Detector da atividade - Reconhecimento automático
da voz (Chang et al., da fala (Dustor e Szware,
2006). 2009);
- Identificação de acentos da
língua chinesa Mandarim
(Chen et al., 2001).
Nesta seção, foram estudadas as três abordagens documentadas na literatura para estimar a
16
PDF de um sinal, assim como vários trabalhos em que estas abordagens foram utilizadas. Na
Tabela 2.1, é apresentado um resumo das principais características das abordagens existentes
para estimar a PDF de um sinal, assim como alguns trabalhos em que estas abordagens têm sido
empregadas. A seguir, é descrito o método para calcular a PDF, usando um modelo baseado em
mistura de gaussianas, pois este é o modelo empregado no presente trabalho para representar
as palavras que integram o vocabulário escolhido para análise.
2.3 Modelo baseado em mistura de gaussianas (GMM)
Considerando um sinal de fala como uma série temporal x
1
, ..., x
N
∈ R de comprimento
N, a PDF do sinal pode ser aproximada por uma família F de funções de distribuição de
probabilidades em R. Em algoritmos dedicados à estimativa da PDF, o problema é encontrar a
função de distribuição f(x) ∈ F que melhor gere os dados de entrada.
A definição da família de funções F adotada neste estudo é proposta por Tomasi (2004). O
autor conseguiu fazer uma representação matemática descritiva que facilitou a implementação
computacional do método. Nesta definição, F é considerada como uma mistura de gaussianas,
em que os componentes que integram a mistura apresentam a mesma estrutura matemática.
Consegue-se identificar cada um dos elementos do GMM através de diferentes valores dos
parâmetros. A Equação 2.1 mostra a forma da mistura de gaussianas
f(x, Θ) =
K
k=1
p
k
g(x, m
k
, σ
k
) (2.1)
na qual f(x, Θ) representa a mistura, p
k
é a probabilidade de ocorrência de cada gaussiana k e
g(x, m
k
, σ
k
) =
1
σ
k
√
2π
e
−
1
2
(
x−m
k
σ
k
)
2
(2.2)
é o k-ésimo componente gaussiano que pertence à mistura, em que Θ = [θ
1
, ..., θ
K
]
= [(p
1
, m
1
, σ
1
), ..., (p
K
, m
K
, σ
K
)] é um vetor de comprimento K que contém a probabilidade
p
k
, a média m
k
e o desvio padrão σ
k
de cada gaussiana (Tomasi, 2004).
A função f na Equação 2.1 representa uma função de distribuição de probabilidade, então
f é positiva e
R
g(x, m
k
, σ
k
)dx = 1, desenvolvendo tem-se (Tomasi, 2004):
17
1 =
R
f(x, Θ)dx =
R
K
k=1
p
k
g(x, m
k
, σ
k
)dx =
K
k=1
p
k
R
g(x, m
k
, σ
k
)dx =
K
k=1
p
k
.
Então p
k
≥ 0 e
K
k=1
p
k
= 1. O principal problema do algoritmo é estimar os parâmetros
Θ que especificam o modelo e que melhor caracterizam o sinal x.
Diversas técnicas estão disponíveis para estimar os parâmetros de uma mistura de Gaus-
sianas (McLachlan e Krishnan, 1997). Em Azzalini e Capitanio (1999) se recomenda usar os
métodos Newton-Raphson ou método quasi-Newton, no entanto o método mais utilizado na li-
teratura e mais estabelecido é o método de máxima verossimilhança (Reynolds e Rose, 1995).
O objetivo deste último método é encontrar, a partir dos dados de entrada, os parâmetros que
maximizam a verossimilhança da mistura Λ(X, Θ) (Nan et al., 2009; Archambeau e Verleysen,
2003; Reynolds e Rose, 1995).
A função de verossimilhança para uma mistura de gaussianas é:
Λ(X, Θ) =
N
n=1
K
k=1
p
k
g(x
n
, m
k
, σ
k
). (2.3)
O logaritmo da função de verossimilhança λ(X, Θ) definida na Equação 2.3 é
λ(X, Θ) =
N
n=1
log
K
k=1
p
k
g(x
n
, m
k
, σ
k
). (2.4)
Infelizmente, a Equação 2.3 é uma função não linear dos parâmetros Θ e não existe uma
expressão analítica para maximizá-la. Desta forma, esta estimativa pode ser obtida de forma
iterativa usando um caso especial do algoritmo EM (Nan et al., 2009; Reynolds e Rose, 1995).
Este algoritmo é considerado a ferramenta padrão para o cálculo da máxima verossimilhança
em GMM (Marques, 2009). A seguir é descrito o algoritmo EM responsável pelo cômputo dos
parâmetros que descrevem a mistura de gaussianas.
18
2.3.1 Algoritmo Maximização da Expectância (EM)
O algoritmo EM (McLachlan e Krishnan, 1997) é um procedimento iterativo para estimar
a máxima verossimilhança em problemas de dados incompletos. O EM se converteu em uma
ferramenta padrão no contexto estatístico (McLachlan e Peel, 2000; McLachlan e Krishnan,
1997) não só envolvendo problemas de dados incompletos, como também problemas que po-
dem ser tratados de forma similar como é o caso de estimativas de misturas. Segundo Nasser
et al. (2006) EM é uma técnica frequentemente empregada para obter as PDF tanto em forma
univariada como multivariada.
Neste trabalho, é descrito o algoritmo EM que foi proposto por Tomasi (2004) para estimar
os parâmetros de uma mistura de gaussianas. Tomasi (2004) desenvolveu um caso especial
deste algoritmo para estimar a PDF, de um conjunto de pontos, baseada em GMM.
A ideia básica do algoritmo EM é começar com um modelo inicial de parâmetros Θ
0
, para
estimar um novo modelo descrito pelo conjunto de parâmetros Θ
1
, de forma que p(x|Θ
1
) ≥
p(x|Θ
0
), incrementando a máxima verossimilhança em cada iteração (Nan et al., 2009). O
modelo inicial Θ
0
se converte no modelo Θ
K
que melhor aproxima a distribuição dos dados
quando a condição de convergência é alcançada.
Cada iteração do algoritmo EM consiste em dois processos: Expectância e Maximização.
No passo Expectância se aproxima a PDF desejada, usando como entrada os parâmetros p
(i−1)
k
,
m
(i−1)
k
e σ
(i−1)
k
. Esta aproximação se consegue através do cálculo da probabilidade de perti-
nência p
(i)
(k|n). Esta operação expressa a probabilidade que um ponto qualquer do vetor de
entrada seja gerado por uma das componentes da mistura f, mostrada na Equação 2.1. Na
Equação 2.5 se observa o cálculo da probabilidade de pertinência.
p
(i)
(k|n) =
p
(i)
k
g(x
n
, m
(i)
k
, σ
(i)
k
)
K
m=1
p
(i)
k
g(x
n
, m
(i)
k
, σ
(i)
k
)
. (2.5)
O objetivo do passo Maximização é maximizar a função de verossimilhança, usando a
Equação 2.3 ou a Equação 2.4. Neste passo, também são estimados novos valores para os parâ-
metros que caracterizem o modelo, o qual foi aproximado no passo Expectância. As Equações
2.6, 2.7 e 2.8 indicam como calcular a média m
(i)
k
, o desvio padrão σ
(i)
k
e a probabilidade de
ocorrência p
(i)
k
, respectivamente. Note que estas operações dependem da estimativa p
(i)
(k|n),
obtida no passo Expectância da mesma iteração. Na equação 2.7, D representa a dimensão dos
19
dados.
m
(i+1)
k
=
N
n=1
p
(i)
(k|n)x
n
N
n=1
p
(i)
(k|n)
. (2.6)
σ
(i+1)
k
=
1
D
N
n=1
p
(i)
(k|n)x
n
− m
(i+1)
k
2
N
n=1
p
(i)
(k|n)
. (2.7)
p
(i+1)
k
=
1
N
N
n=1
p
(i)
(k|n). (2.8)
A função de máxima verossimilhança aumenta em cada iteração garantindo a convergência
do método (Borman, 2004). O procedimento do EM é repetido até chegar a um número máximo
de iterações ou até que a máxima verossimilhança entre duas iterações sucessivas seja menor
que um limiar especificado no começo do algoritmo. Para conseguir uma adequada aproxima-
ção da PDF em poucas iterações é necessário considerar algumas limitações do algoritmo EM.
Em Nan et al. (2009) se recomenda inicializar os parâmetros do modelo próximos dos valores
verdadeiros, devido ao fato de um dos inconvenientes do algoritmo EM ser a possibilidade de
encontrar máximos locais, podendo fazer uma indicação errada da melhor estimativa. Outra
das limitações do algoritmo é a convergência lenta e a necessidade de estabelecer um critério de
parada para detectar se o algoritmo atingiu o máximo global. Estas limitações foram atendidas
na implementação do algoritmo EM e as soluções propostas serão explicadas no capítulo 3.
Depois de calcular a PDF a partir de um modelo baseado em mistura de gaussianas, é
necessário estabelecer um critério de divergência para estimar as semelhanças entre os modelos
construídos. A seguir são descritas algumas das métricas mais utilizadas que se encontram na
literatura, especialmente será comentada a divergência KL, além de suas propriedades mais
importantes.
2.4 Medidas de Similaridade
Empregar GMM para aproximar a PDF de sinais de fala é cada vez mais comum em dife-
rentes áreas do processamento deste tipo de sinais (Dustor e Szware, 2009; Shin et al., 2005;
Reynolds e Rose, 1995). Isto se deve a algumas facilidades que caracterizam estes modelos
como, por exemplo, a simplicidade de aprendizagem na estimativa dos parâmetros e a flexibi-
20
lidade para representar qualquer PDF que descrevem os dados (Moreno et al., 2004). A partir
destas vantagens, em diversos algoritmos de fala dedicados à classificação, à seleção de carac-
terísticas ou ao reconhecimento de padrões é interessante comparar os modelos estimados para
quantificar “quão parecidos” são.
Na literatura, existem diversos coeficientes para calcular semelhanças entre modelos. Es-
tes coeficientes têm sido chamados de distintas formas, (divergência, distância ou medidas)
dependendo de como eles satisfazem as propriedades das métricas de distâncias (Seghouane
e Amari, 2007; Chan e Vasconcelos, 2005). Calcular a distância entre dois modelos significa
avaliar quão distanciados entre si eles estão, enquanto menor seja essa distância mais similares
estes serão.
Tradicionalmente, as métricas mais usadas para estimar a similaridade entre modelos foram
a distância Euclidiana e a distância Mahalanobis. A matriz de distância da primeira métrica é a
identidade e a matriz distância da segunda é a inversa da matriz co-variância dos dados. A dis-
tância Euclidiana é independente da distribuição dos dados, enquanto a distância Mahalanobis
considera uma distribuição global deles (Li e King, 1999). Em algoritmos dedicados a proble-
mas de classificação, têm se definido algumas funções como alternativa para medir similaridade
entre modelos. Entre as mais utilizadas se conhece a função polinomial e a gaussiana (Raykar,
2002). Outras das medidas propostas para estimar distância ou divergência entre GMM foram
a Bhattacharyya, que é um caso especial da distância de Chernoff, e a Chi-quadrado (Johnson e
Sinanovi
´
c, 2001). As métricas descritas neste parágrafo são chamadas no resto do texto como
métricas tradicionais.
As métricas tradicionais, indicadas na literatura como as mais usadas para medir distância
ou similaridade entre modelos, às vezes impõem algumas restrições que se consideram limi-
tações na implementação dos algoritmos. A distância Euclidiana e a Mahalanobis não geram
resultados exatos quando os dados estão caracterizados por diferentes tipos de distribuições
(Li e King, 1999). As métricas Bhattacharyya e Chi-quadrado para certas distribuições im-
põem restrições nas características de distribuição dos dados ou são excessivamente custosas
de computar. Estas limitações servem como motivação para desenvolver novos trabalhos com
o objetivo de introduzir outras métricas ou critérios que estimem a similaridade ou distância
entre os modelos baseados em misturas de gaussianas.
Em Li e King (1999) foi formulado um método para estimar a matriz distância entre mo-
delos baseados em GMM, com o objetivo de identificar grupos entre os dados analisados. O
21
método é baseado na minimização da divergência KL entre as distribuições dos dados. A nova
métrica é comparada com a distância Euclidiana e a Mahalanobis, considerando o desempenho
destas medidas. Depois de desenvolver diversos testes, os autores avaliaram a métrica proposta
como superior.
Em Raykar (2002), foi introduzida uma nova família de kernels probabilísticos baseada nas
medidas de divergência da teoria da informação. No trabalho, um kernel é interpretado como
uma função que mede similaridade entre duas PDF. Entre os kernels propostos no trabalho
encontram-se o kernel KL, Rényi e Jensen-Shannon, demonstrando através dos resultados que
estas métricas apresentam melhor desempenho e exatidão que outras métricas de distância
como a Euclidiana.
Apesar da existência de uma variedade de métricas para estimar a divergência entre mo-
delos baseados em mistura de gaussianas, na atualidade a divergência KL é uma ferramenta
amplamente usada em diferentes campos da ciência. Aplicar a divergência KL entre GMM é
muito natural e frequentemente necessário em campos dedicados ao reconhecimento de fala ou
de imagem (Hershey e Olsen, 2007; Seghouane e Amari, 2007; Goldberger et al., 2003; Do,
2003).
Em Goldberger et al. (2003) é apresentado um algoritmo dedicado à recuperação de ima-
gens. A PDF das imagens é estimada usando uma mistura de gaussianas, em que os parâmetros
da mistura são calculados empregando o algoritmo EM. O trabalho propõe usar a divergência
KL para medir a similaridade entre as misturas de gaussianas que descrevem as PDF das ima-
gens.
Argumentando que a divergência KL se caracteriza por uma base sólida para sistemas es-
tocásticos, em Scalassara et al. (2009a) é usada a divergência KL na diferenciação de vozes
normais e patológicas. O trabalho apresenta resultados interessantes na classificação de dife-
rentes doenças vocais.
Em Jensen et al. (2007) apresenta-se uma comparação entre as medidas de distância KL,
(EMD) (em inglês Earth Movers Distance) e a distância Euclidiana, também conhecida como
L2. O objetivo principal do trabalho foi procurar similaridades entre músicas, além de iden-
tificar os diferentes gêneros, nos quais elas pertencem. Avaliando exatidão na classificação, a
medida KL se mostra ligeiramente superior à L2, mas esta última medida obedece o teorema
de desigualdade triangular, enquanto a KL não (Jensen et al., 2007).
22
No trabalho de Haubold e Kender (2008) utiliza-se a divergência KL como medida de
distância em algoritmos de agrupamento de fala. O vetor de fala foi representado usando um
vetor de coeficientes cepstrais (MFCC). Nesse trabalho, o autor mostrou que o rendimento da
divergência KL diminui quando o comprimento dos segmentos de áudio são muito pequenos
ou quando existem diferenças significativas na extensão deles. É necessário considerar estas
deficiências da divergência para garantir uma adequada classificação dos sinais.
Devido às vantagens tanto teóricas como computacionais da divergência KL (Johnson e
Sinanovi
´
c, 2001), o coeficiente da teoria da informação é, provavelmente, o mais usado para
medir a divergência entre duas PDF (Seghouane e Amari, 2007). Além disso, esta divergência
apresenta uma base sólida para ser aplicada tanto em processos estocásticos como em sistemas
dinâmicos (Scalassara et al., 2009a). Apesar das vantagens mencionadas anteriormente, o cál-
culo da divergência KL não é uma tarefa fácil. Além disso, esta métrica depende da estimativa
da PDF do sinal que está sendo estudado (Scalassara et al., 2009b).
Nesta seção foram comentadas as medidas de distância que tem sido mais utilizadas para
avaliar semelhanças entre mistura de gaussianas. Na Tabela 2.2 é mostrado um resumo destas
medidas, assim como os trabalhos em que elas foram empregadas. Em seguida, define-se a
divergência KL e suas características principais, dado que neste trabalho este coeficiente será
empregado para medir semelhanças entre as palavras.
Tabela 2.2: Medidas de distância mais comummente empregadas para estabelecer semelhanças
entre GMM.
Medidas de distância empregadas entre GMM
Medidas tradicionais Medidas da teoria da informação
Euclidiana ou L2 (Jensen et al,. 2007; Li Divergência KL (Haubold e Kender,
e King, 1999) 2008; Johnson e Sinanovié, 2001;
Scalassara et al., 2009b)
Mahalanobis (Li e King, 1999) Rényi (Raykar, 2002)
Bhattacharyya (Johnson e Sinanovié, 2001) Jensen-Shannon (Raykar, 2002)
Chi-quadrado (Johnson e Sinanovié, 2001)
Earth Movers Distance (EMD) (Jensen et al,. 2007)
2.5 Divergência Kulback-Leibler (KL)
Um dos principais objetivos da teoria da informação é quantificar as incertezas estatísticas
em processos aleatórios, bem como as dependências estatísticas entre múltiplos processos alea-
23
tórios. As duas principais grandezas propostas na teoria da informação, definidas para projetar
mensagens e sistemas, são a entropia e a divergência Kullback-Leibler (Erdogmus e Principe,
2006).
A entropia é uma grandeza usada para medir a incerteza de uma variável aleatória. Esta
define uma medida da quantidade de informação necessária para descrever qualquer variável
(Cover e Thomas, 1991). A entropia H(X) foi originalmente definida por Shannon, como
medida de informação para uma variável aleatória discreta X. Esta grandeza é definida na
Equação 2.9, conforme (Cover e Thomas, 1991).
H(X) = −
X∈χ
f(x)logf (x). (2.9)
Na Equação 2.9, considera-se a variável aleatória X com um alfabeto de eventos χ , sendo
f(x) a PDF associada a essa variável. O logaritmo possui base 2, assim, a entropia é expressa
em bits (Cover e Thomas, 1991).
A entropia relativa ou divergência KL D(f||g) é uma medida de distância entre duas distri-
buições de probabilidade (Hershey e Olsen, 2007). A divergência KL quantifica a ineficiência
em assumir que a distribuição dos dados poderia ser f quando realmente a distribuição é g
(Cover e Thomas, 1991). Considerando f(x) e g(x) duas PDFs, a entropia relativa entre elas é
definida pela Equação 2.10, sendo X uma variável aleatória discreta, e χ o alfabeto de eventos
dessa variável.
D(f||g) =
X∈χ
f(x)log
f(x)
g(x)
. (2.10)
Outra medida da teoria da informação que mede divergência entre modelos é a divergência
de Rényi (Chan e Vasconcelos, 2005). Esta divergência de ordem α é definida com a seguinte
fórmula:
D
α
(f||g) =
1
α − 1
log
X∈χ
f(x)
α
g(x)
1−α
. (2.11)
na qual α > 0. A divergência de Rényi é uma generalização da divergência KL, e elas são
iguais quando α tende a 1. Para α → ∞, o cálculo da divergência de Rényi considera os
eventos de maior probabilidade, enquanto para valores de α próximos de zero considera todos
24
os eventos de forma equitativa e com independência de suas probabilidades. Neste estudo, por
questões de simplicidade, se usará somente a divergência KL (Chan e Vasconcelos, 2005).
A divergência KL satisfaz três propriedades fundamentais (Hershey e Olsen, 2007):
◦ Positiva D(f||g) ≥ 0 para todo f e g
◦ Similaridade D(f||f ) = 0
◦ Identificação D(f||g) = 0 se e somente se f = g
Apesar das vantagens da divergência KL, um dos inconvenientes é a sua propriedade de
assimetria. A matriz de distância baseada na divergência KL realmente não é uma matriz de
distância, pois esta divergência apesar de apresentar algumas características das métricas de
distância entre PDFs, como sendo sempre positiva e igual a zero quando f (x) = g(x), não será
realmente uma distância. Isso porque D(f||g) é diferente de D(g||f), em outras palavras, ela
não é simétrica e não satisfaz a desigualdade triangular (Seghouane e Amari, 2007; Johnson
e Sinanovi
´
c, 2001; Cover e Thomas, 1991), o que constitui um requisito essencial para ser
considerada uma medida de distância.
Motivados por solucionar este problema de simetria em Seghouane e Amari (2007) e em
Johnson e Sinanovi
´
c (2001) são propostas várias funções para simetrizar a KL. Em Johnson e
Sinanovi
´
c (2001) se recomenda como ideal o uso da distância de Chernoff, mas este método é
pouco atrativo devido a sua impossibilidade de ser tratado computacionalmente. Consequente-
mente, para o autor é preferível a simetrização da divergência KL para aproveitar as vantagens
que ela fornece e procurar uma melhor alternativa para avaliar similaridades entre modelos
(Johnson e Sinanovi
´
c, 2001). Na próxima seção, são apresentadas algumas das alternativas
proposta para simetrizar a divergência KL.
2.5.1 Simetrização da divergência KL
Nos últimos anos, diversas funções têm sido propostas para a simetrização da divergência
KL (Seghouane e Amari, 2007; Johnson e Sinanovi
´
c, 2001). Como primeira alternativa, tem-
se a chamada J-divergence
8
, que consiste em calcular a média entre duas divergências KL. A
Equação 2.12 define esta operação:
8
Alguns autores definem a J-divergence como uma soma entre as duas PDFs, no lugar da média entre elas.
25
J(f||g) =
D(f||g) + D(g||f)
2
. (2.12)
Em Seghouane e Amari (2007) a função weighted average é considerada como solução do
problema da simetrização da divergência KL. Esta operação é definida na Equação 2.13:
W (f||g) = ηD(f||g) + (1 − η)D(g||f), η ∈ [0, 1] (2.13)
η = 1/2, é um caso especial na Equação 2.13, e corresponde a função J-Divergence, definida
pela Expressão 2.12.
Para solucionar o problema da simetrização da divergência KL, foram propostas outras
medidas como a média geométrica (Equação 2.14) e a média harmônica (Equação 2.15).
G(f||g) =
D(f||g) ∗ D(g||f). (2.14)
H(f||g) =
2
1
D(f||g)
+
1
D(g||f)
. (2.15)
No trabalho de Seghouane e Amari (2007), o principal objetivo foi procurar medidas de
distância simétricas, baseadas na divergência KL que pudessem ser usadas como critérios de
comparação entre modelos. O trabalho propõe simetrizar a divergência KL usando a função
weighted average, a média Geométrica e a média Harmônica. Concluindo que as três alterna-
tivas empregadas são equivalentes já que todas elas podem ser estimadas usando o critério de
informação AIC
9
.
Em Johnson e Sinanovi
´
c (2001) foi definida uma nova distância entre duas PDFs chamada
resistor-average. Esta nova função é simples de calcular e cumpre todas as propriedades da
divergência KL. Resistor-average é simétrica e é definida a partir da média Harmônica. Na
Equação 2.16 se mostra a operação que descreve esta medida.
9
AIC é o primeiro critério teórico baseado na divergência KL entre duas PDF. Ele é derivado a partir de consi-
derações sobre o comportamento assintótico da divergência KL.
26
1
R(f||g)
=
1
D(f||g)
+
1
D(g||f)
. (2.16)
No estudo de Johnson e Sinanovi
´
c (2001), é comparada a distância resistor-average com
a distância de Chernoff, a J-divergence a Bhattacharyya e a média geométrica. O autor usa
a distância Chernoff, conhecida como a de maior exatidão na estimativa da distância entre
modelos, como uma referência para avaliar o desempenho do resto das métricas propostas.
Considerando exatidão na estimativa e simplicidade na avaliação, a melhor estimativa foi ob-
tida usando a função resistor-average. O mesmo trabalho também apresenta outra abordagem
para criar uma medida simétrica baseada na divergência KL, a distância Topsoe T (f||g). Esta
métrica é equivalente a T(f||p) + T (g||p), em que p =
1
2
(f + g).
A Figura 2.4, modificada de Johnson e Sinanovi
´
c (2001), retrata as relações existentes en-
tre algumas das medidas de distância mais usadas na teoria da informação. O foco na figura
é a função −log(µ(t)), em que µ(t) =
[f
x
]
1−t
[g(x)]
t
dx. A distância Chernoff C(f, g) é
definida como o máximo valor da função anterior no ponto t
∗
. A derivada da curva em t = 0
e t = 1 é D(f||g) e −D(g||f), respectivamente. Os valores destas tangentes correspondem às
distâncias KL. As curvas tangenciais se interceptam no ponto t = t
∗∗
e esta interceptação cor-
responde ao valor da distância resistor-average R(f, g); definida na Equação 2.16. A distância
Bhattacharyya B(f, g) é igual a −logµ(
1
2
). A média geométrica G(f, g), definida na Equação
2.14, está situada entre a distância J-divergence J(f, g), definida na Equação 2.12, e o máximo
valor da divergência KL. C(f, g) representa a distância Chernoff enquanto D(f||g) representa
a divergência KL. Estes testes foram desenvolvidos no trabalho de Johnson e Sinanovi
´
c (2001).
Figura 2.4: Relações entre as métricas de distância, Bhattacharyya, resistor-average, média
geométrica, J-Divergence e Chernoff, usadas para simetrizar a divergência KL. Imagem modi-
ficada de Johnson e Sinanovi
´
c (2001).
27
Em Jensen et al. (2007) foi necessário simetrizar a divergência KL para estabelecer um
critério de comparação entre dois modelos de tipo GMM. A alternativa escolhida para a sime-
trização deste coeficiente foi a função J-divergence; esta mesma opção foi a empregada em
Raykar (2002).
Enquanto a divergência KL ganha aceitação nas comunidades que trabalham com imagem
e som, modelos probabilísticos baseados em GMM são bem conhecidos e empregados nestas
áreas, resultando atrativa a combinação destas abordagens com a finalidade de construir novas
técnicas de classificação e identificação (Moreno et al., 2004).
É simples estimar a divergência KL entre duas funções gaussianas f
i
e g
i
. Na equação 2.17
é mostrada esta operação (Hershey e Olsen, 2007):
D(f
i
||g
i
) =
1
2
[log
|
g
i
|
|
f
i
|
+ T r[
−1
g
i
f
i
] − d + (µ
f
i
− µ
g
i
)
T
−1
g
i
(µ
f
i
− µ
g
i
)]. (2.17)
Considerando que não existe uma expressão para estimar a divergência KL entre modelos
baseados em GMM (Hershey e Olsen, 2007; Jensen et al., 2007; Goldberger et al., 2003), a
literatura sugere diferentes métodos ou funções para estimá-la, de forma eficiente, entre este
tipo de modelos (Hershey e Olsen, 2007). Na próxima seção são abordadas algumas destas
alternativas.
2.5.2 Estimativa da divergência KL entre GMM
Nesta seção são apresentados os métodos mais conhecidos para estimar a divergência KL
entre GMM. Além disso, são mostradas algumas das funções empregadas para substituir a KL,
entre dois modelos baseados em mistura de gaussianas.
O simulador de Monte Carlo é o método mais recomendado para estimar a divergência
KL entre GMM. Ele consegue uma aproximação bem precisa, principalmente quando trabalha
com dados de alta dimensão (Hershey e Olsen, 2007; Goldberger et al., 2003). Neste algo-
ritmo, primeiro é gerado um conjunto de amostras x
i
n
i=1
para cada mistura f(x) e g(x), para
logo estimar, de forma iterativa, a divergência KL para cada amostra gerada x
i
em f(x) e em
g(x). Apesar deste algoritmo ser um dos poucos métodos convergentes, sua execução causa
um significativo incremento na complexidade computacional (Goldberger et al., 2003), sendo
28
esta a principal desvantagem do método. De acordo com Hershey e Olsen (2007), outra das
limitações deste algoritmo é que ele, às vezes, não cumpre a propriedade de positividade da
KL. As propriedades mais importantes da KL, foram detalhadas na Seção 2.5.
Em Hershey e Olsen (2007) são propostos dois novos métodos para aproximar a divergên-
cia KL entre GMMs. Estas técnicas foram comparadas com outras que aparecem na literatura,
a partir dos benefícios que cada uma proporciona. Estes métodos são chamados variational ap-
proximation e variational upper bound. Outra técnica comentada em Hershey e Olsen (2007)
é unscented transformation, a qual é parecida com o método Monte Carlo (Hershey e Olsen,
2007; Goldberger et al., 2003), mas desta vez as amostras do sinal são escolhidas de forma
determinística. Além disso, este método de aproximação é aplicado somente entre mistura de
gaussianas (Goldberger et al., 2003). Segundo Hershey e Olsen (2007) esta abordagem satis-
faz a propriedade de similaridade, mas geralmente as duas outras propriedades, positividade e
identificação, não são mantidas.
Outra alternativa para aproximar a divergência KL entre misturas é o método baseado em
aproximação por casamento (em inglês matching based approximation). Este consiste em assu-
mir que não existe uma expressão para medir a divergência entre duas misturas, mas existe uma
equação para estimar a divergência entre os componentes individuais que a integram. O pri-
meiro passo deste método é definir uma função que case cada um dos componentes gaussianos
que integram a mistura (Goldberger et al., 2003).
Hershey e Olsen (2007) apresentaram uma técnica conhecida como aproximação a uma
gaussiana. Este método é motivado também pela existência de uma expressão para calcular a
KL entre duas funções gaussianas f
i
e g
i
. Usa-se a notação f
i
e g
i
para referir-se somente a uma
gaussiana. O procedimento consiste em substituir cada mistura f(x) e g(x) por um elemento
gaussiano f
i
e g
i
, respectivamente. O trabalho mostra dois critérios para realizar o casamento
das componentes gaussianas. O primeiro método casa as componentes gaussianas, nas quais as
médias e as variâncias coincidem. Enquanto o segundo realiza o casamento procurando o par
mais próximo, através da operação D
min
= min
a,b
D(f
a
||g
b
). O uso deste método constitui
uma solução muito simples, obtendo uma aproximação muito pobre. Este método satisfaz as
propriedades de positividade e similaridade, mas a propriedade de identidade não é mantida.
Em Goldberger et al. (2003) foram apresentados dois métodos para aproximar a divergên-
cia KL entre GMM. O primeiro é baseado no casamento das componentes que integram a
mistura, enquanto o segundo baseia-se na unscented transformation. A eficiência dos métodos
29
de aproximação foi avaliada usando tanto dados reais como simulados. A melhor aproxima-
ção foi alcançada através do método unscented transformation, mas o tempo computacional
foi elevado. O método de casamento proposto foi comparado com um método de casamento
baseado na distância Mahalanobis, mostrando melhor desempenho.
Outros métodos comentados no trabalho de Hershey e Olsen (2007) são aproximação do
produto de gaussianas e matched bound approximation, o último algoritmo não satisfaz ne-
nhuma das propriedades da divergência KL, entretanto o primeiro satisfaz, pelo menos, a pro-
priedade de similaridade. O método de matched bound approximation é uma solução empírica
e a aproximação é ruim, quando as componentes gaussianas que se quer multiplicar apresentam
baixa probabilidade de ocorrência.
As novas estimativas propostas no trabalho de Hershey e Olsen (2007) são variational ap-
proximation e variational upper bound. A primeira alternativa consiste em estimar o limite
inferior da verossimilhança do modelo de forma paramétrica, seguindo um enfoque variacio-
nal. A segunda alternativa, segue o mesmo enfoque, com o diferencial da estimação do limite
superior da divergência KL através de parâmetros. Possivelmente, o melhor limite superior
é alcançado procurando os parâmetros que minimizem a divergência KL (Hershey e Olsen,
2007). Enquanto que a primeira alternativa cumpre, apenas, a propriedade de similaridade, a
segunda cumpre as três propriedades da divergência.
Numerosas alternativas existem para aproximar a divergência KL entre dois modelos ba-
seados em misturas de gaussianas, algumas com melhor desempenho que o resto (Hershey e
Olsen, 2007; Goldberger et al., 2003), mas quando se quer ganhar exatidão na estimativa, o
método de Monte Carlo é o que fornece melhores resultados. Se o interesse for em tempo
computacional, outros métodos como variational approximation e variational upper bound
são preferíveis. Se a simplicidade da expressão for o questionamento, o método indicado é
o variational approximation. Embora os métodos aproximação a uma gaussiana e unscented
transformation representem uma das alternativas mais comuns, estes não são recomendáveis
por existirem outras técnicas que proporcionem melhores soluções (Hershey e Olsen, 2007).
Na Tabela 2.3, é apresentado um resumo dos métodos comentados nesta seção para calcular
a divergência KL entre modelos baseados em mistura de gaussianas. Na tabela observam-se as
principais propriedades de dita divergência e como estes métodos as cumprem ou não.
Nesta seção, foi apresentada a estimativa da divergência KL, além das principais proprie-
dades que a caracterizam. Foram mostrados alguns trabalhos que usam esta divergência como
30
Tabela 2.3: Métodos para estimar a divergência KL entre GMM. Cumprimento das proprieda-
des da divergência KL.
Principais métodos para estimar a divergência KL entre GMM.
Propriedades da divergência KL.
Métodos Positiva Similaridade Identificação
Monte Carlo Não Sim Sim
Variational aproximation Não Sim Não
Variational upper bound Sim Sim Sim
Unscented transformation Não Sim Não
Aproximação por casamento Sim Sim Não
Matched bound approximation Não Não Não
medida de distância na solução de diversos problemas. A simetrização da KL foi comentada,
mostrando algumas das funções propostas como alternativa de simetrização. Por último, o cál-
culo da divergência KL entre modelos baseados em mistura de gaussianas foi abordado nesta
seção. No Capítulo 3 é apresentado o método empregado no presente trabalho para calcular a
divergência KL entre GMM. Na Seção 2.6, são explicados os algoritmos de agrupamento hie-
rárquico, os quais serão usados no nosso trabalho, com a finalidade de procurar relações entre
algumas das palavras que integram o banco de dados selecionado neste estudo.
2.6 Agrupamento Hierárquico
Existem numerosas alternativas para encontrar semelhanças entre elementos e formar gru-
pos (Petridou et al., 2006; Tan et al., 2006; Afifi et al., 2004; Everitt et al., 2001; Kaufman
e Rousseeuw, 1990; Anderberg, 1973). No contexto de análise de agrupamento (em inglês,
Cluster Analysis), o agrupamento hierárquico representa um conjunto de métodos dedicados à
construção de estruturas hierárquicas a partir de um grupo de objetos. O agrupamento hierár-
quico é um dos métodos mais simples. Estes métodos podem ser divididos em aglomerativos e
divisivos. Os métodos aglomerativos começam formando grupos unitários e de forma iterativa
se vão mesclando para formar grupos maiores, enquanto os métodos divisivos começam com
um único grupo, que contém todos os elementos, e se vão dividindo sucessivamente em grupos
menores (Afifi et al., 2004).
Algoritmos hierárquicos são bastante usados na solução de inúmeros problemas práticos.
Na biologia, comumente empregam-se para representar filogenias e taxonomias (Talavera,
31
2007). O agrupamento hierárquico também tem sido utilizado em aplicações Web, em que
a quantidade de informação processada é excessiva, incitando a construção de algoritmos de
agrupamento para organizar a informação seguindo determinados critérios (Tan et al., 2006).
Outras áreas em que o agrupamento hierárquico é apropriado são: museologia, sistemas soci-
ais, biblioteconomia e outros (Talavera, 2007).
Este tipo de agrupamento geralmente produz uma saída gráfica conhecida como dendro-
grama ou árvore binária, que mostra a estrutura hierárquica com as relações entre os grupos e
os subgrupos, além da ordem em que cada grupo foi fundido (Tan et al., 2006). Um exemplo de
dendrograma é mostrado na Figura 2.5, onde as barras verticais representam a distância entre
os grupos e a altura na qual dois grupos foram fundidos.
Figura 2.5: Exemplo da representação de um dendrograma, no qual o eixo vertical representa
as distâncias entre os grupos e o horizontal identifica cada elemento que integra os grupos.
Os métodos hierárquicos são comumente usados, pois na maioria das vezes produzem re-
sultados razoáveis, além de serem fáceis de calcular. Segundo Talavera (2007) os métodos
aglomerativos são atualmente mais usados que os divisivos devido a estes últimos serem com-
putacionalmente exigentes pela enorme quantidade de possíveis divisões que requerem. Neste
trabalho, comentaremos apenas os métodos aglomerativos. A seguir são descritos estes méto-
dos comumente usados em diversas áreas.
2.6.1 Métodos aglomerativos tradicionais
Os métodos aglomerativos são iniciados com n grupos (n = número de elementos), em
que cada elemento é localizado em um grupo diferente. Usando uma métrica de distância se
calcula a matriz de distância entre os elementos individuais. A partir desta matriz, utiliza-se um
critério de similaridade para de forma iterativa fundir o par de grupos que apresentem maior
32
similaridade. O procedimento termina quando todos os elementos são juntados em um mesmo
grupo. Existe uma variedade de métodos aglomerativos que são caracterizados de acordo com
o critério utilizado para medir similaridade entre grupos. Entretanto, a maioria dos métodos
parecem ser formulações alternativas de três grandes métodos de agrupamento aglomerativo
(Anderberg, 1973):
◦ Métodos de ligação (single link, complete link, average link);
◦ Métodos de centróide;
◦ Métodos de soma de erros quadráticos ou variância (método de Ward).
No Algoritmo 1 é descrito o procedimento padrão que os métodos aglomerativos seguem.
Formalmente, dado um conjunto de grupos C = C
1
, C
2
, ..., C
n
, a matriz distância entre os
elementos ∆ = d(i, j) é calculada no passo 2 do algoritmo. A escolha desta matriz distância
depende do tipo de dado e do problema abordado (Everitt et al., 2001), existindo diversas
funções para este cálculo. Na Seção 2.4 são comentadas algumas das métricas mais populares
empregadas para a construção da matriz anterior. O principal passo do algoritmo é definir
as similaridades entre os grupos e isto ocorre no passo 7 do procedimento, em que a função
δ(C
i
, C
j
) é usada para calcular a distância δ(C
ij
, C
w
) entre um novo grupo C
ij
e cada grupo
existente C
w
. Os métodos utilizados para medir a distância entre grupos e algumas de suas
propriedades serão mostradas a seguir.
Algoritmo 1 Algoritmo padrão dos métodos aglomerativos tradicionais.
Entrada: Dados C = C
1
, C
2
, ...C
n
, em que n é o total de elementos;
Função da matriz distância entre os elementos d(i, j) ∈ R;
Função da matriz distância entre os grupos δ(C
i
, C
j
) ∈ R;
Saída: Estrutura hierárquica dos grupos.
1. Inicializa n grupos, contendo cada grupo um elemento;
2. Calcular a matriz distância ∆ = d(i, j), em que i, j ∈ [1, ..., n];
3. Repetir;
4. Localizar os grupos C
i
e C
j
com menor distância na matriz
∆ = d(i, j), usando a função d = (i, j);
5. Fundir os grupos encontrados no passo 4, C
ij
= C
i
∪ C
j
;
6. Atualizar a matriz ∆ = δ(C
i
, C
j
), suprimindo as linhas e as
colunas correspondentes aos grupos fusionados C
i
e C
j
;
7. Atualizar a matriz ∆ = δ(C
i
, C
j
), incorporando a linha e a
coluna correspondente às distâncias δ(C
ij
, C
w
) entre o novo
grupo e cada grupo existente w;
8. Até n − 1 quando todos os elementos estarão em um único grupo.
33
Método de ligação por vizinho mais próximo (em inglês, Single Linkage): Neste mé-
todo, a distância δ(C
ij
, C
w
) entre o grupo fundido C
ij
e qualquer outro grupo existente C
w
é calculada como a mínima distância entre os elementos dos grupos ij e w. A Equação 2.18
mostra o cálculo:
δ(C
ij
, C
w
) = mimδ(ij, w)|i ∈ C
ij
, w ∈ C
w
(2.18)
Entre as principais características deste método estão (Anderberg, 1973):
◦ Permite detectar grupos de formas não-elípticas;
◦ Grupos muito próximos podem não ser identificados;
◦ Pouca tolerância a ruído e
◦ Tendência a formar longas cadeias (encadeamento).
Método de ligação por vizinho mais distante (em inglês, Complete Linkage): Neste mé-
todo, a distância δ(C
ij
, C
w
) entre o grupo fundido C
ij
e qualquer outro grupo C
w
é calculada
como a maior distância entre os elementos ij e w de ambos grupos C
ij
e C
w
. A Equação 2.19
mostra o cálculo:
δ(C
ij
, C
w
) = maxδ(ij, w)|i ∈ C
ij
, w ∈ C
w
(2.19)
Algumas das principais características deste método são (Kaufman e Rousseeuw, 1990):
◦ Tendência a formar grupos compactos;
◦ Os ruídos demoram a ser incorporados ao grupo e
◦ Apresenta bons resultados tanto para distancia Euclidiana quanto para outras.
Método de ligação média (em inglês, Average Linkage): Neste método, a distância
δ(C
ij
, C
w
) entre o grupo fundido C
ij
e qualquer outro grupo C
w
é calculada como a distância
média de ij e w com respeito a w. Este é um método intermediário entre as duas alternativas
anteriores (Tan et al., 2006). A Equação 2.20, mostra o cálculo:
δ(C
ij
, C
w
) =
ij∈C
ij
w∈C
w
δ(C
ij
, C
w
)
|C
ij
| ∗ |C
w
|
(2.20)
34
Algumas das principais características deste método são (Kaufman e Rousseeuw, 1990):
◦ Menor sensibilidade a ruídos que outros métodos de ligação;
◦ Apresenta bons resultados tanto para distâncias Euclidianas quanto para outras e
◦ Tendência a formar grupos com número de elementos similares.
Método de ligação por centróide (em inglês, Centroid Linkage): Este método, calcula a
distância entre o grupo fundido C
ij
e qualquer outro grupo existente C
w
, como sendo a soma
da distância média entre todos os elementos dos grupos. A Equação 2.21, mostra este cálculo:
δ(C
ij
, C
w
) = δ(µ
C
ij
, µ
C
w
)onde : µ
C
ij
=
ij∈C
ij
ij
|C
ij|
(2.21)
Algumas das principais características deste método são (Talavera, 2007):
◦ Tolerância à presença de ruído e
◦ Fenômeno de reversão, isto é, novos grupos podem-se formar em um nível inferior aos
grupos existentes, tornando o dendrograma confuso.
Método de ligação de Ward: Neste método, a distância entre dois grupos se calcula como
o incremento no erro quadrático, que resulta quando dois grupos são fundidos. A distância
entre o grupo fundido C
ij
e qualquer outro grupo existente C
w
se calcula de acordo com a
Equação 2.22:
δ(C
ij
, C
w
) =
|C
ij
| ∗ |C
w
|
|C
ij
| + |C
w
|
||µ
C
ij
− µ
C
w
||. (2.22)
Algumas das principais características deste método são (Talavera, 2007):
◦ Pode apresentar resultados insatisfatórios quando o número de elementos em cada grupo
é significativamente diferente;
◦ Tendência a combinar grupos com poucos elementos e
◦ Sensível a presença de outliers
10
.
10
Outliers são observações numericamente distantes do resto do banco de dados.
35
Os três primeiros métodos discutidos acima podem ser combinados com qualquer função
de distância ou de similaridade para calcular a distância entre os elementos. Dentre as mais uti-
lizadas são conhecidas: a distância Euclidiana, a distância Manhattan, a distância Minkowski,
a correlação de Pearson e a distância cosseno. Os demais métodos comentados calculam so-
mente a distância entre os elementos usando a distância Euclidiana (Afifi et al., 2004).
O êxito de um algoritmo hierárquico, depende fundamentalmente da métrica escolhida para
estabelecer similaridade entre os elementos (Talavera, 2007). A escolha de uma medida de
dissimilaridade que se adeque as propriedades dos dados a analisar é considerada um problema
real. Na prática, as medidas de distância tradicionais, como a distância Euclidiana e a distância
Manhattan, são as de maior uso nesta classe de algoritmos de agrupamento, desconsiderando a
importância de utilizar uma métrica capaz de levar em conta algumas características especiais
dos grupos examinados (Weixiang et al., 2009).
Uma alternativa para solucionar este problema é o uso da divergência KL como medida de
similaridade para agrupar diversos tipos de dados. Em Weixiang et al. (2009), foi apresentado
um algoritmo hierárquico que sugere a divergência KL como medida de distância entre os
elementos dos grupos. A motivação desta abordagem está associada com a não linearidade do
termo f(x)log(
f(x)
g(x)
), na Equação 2.10, que tende a capturar as diferentes características entre
dois vetores (Weixiang et al., 2009). Este algoritmo foi usado em uma aplicação dedicada ao
agrupamento de dados biológicos, mostrando a superioridade da divergência selecionada.
Em Petridou et al. (2006), foi proposto o uso da divergência KL combinada com o algo-
ritmo de agrupamento K-means em um sistema dedicado a mineração Web (em inglês, Web
Mining). No trabalho se compara esta medida de dissimilaridade com outras métricas tra-
dicionais, como a distância Euclidiana e a distância de Manhattan, também conhecida como
distância L
1
, demostrando que o agrupamento obtido empregando a divergência KL é superior
ao alcançado com as outras métricas testadas.
36
Capítulo 3
Materiais e Métodos
Nosso trabalho foi realizado utilizando o banco de vozes do Museu do Índio do Brasil.
Este banco de dados possui um acervo de mais de 2000 vocábulos pertencentes a 9 línguas
indígenas e um dialeto. Atualmente, estas línguas e o dialeto existem no território brasileiro.
Neste capítulo, primeiramente são descritas as palavras selecionadas para serem analisadas,
junto com suas características fundamentais. Para a construção do sistema proposto, foi crucial
a seleção de algumas das técnicas empregadas para modelar, comparar e agrupar sinais de fala.
Após a escolha das palavras para a análise, explica-se o algoritmo implementado, assim como
o processo de desenvolvimento e algumas das considerações realizadas para automatizar os
métodos matemáticos utilizados.
3.1 Banco de dados
Dentre as 180 línguas indígenas que há no território brasileiro, neste trabalho se utilizaram
um dialeto e 9 línguas que estão documentadas na base de dados do Museu do Índio. Na
Tabela 3.1, são observadas estas línguas, além do tronco linguístico ao qual elas pertencem.
Seguindo o agrupamento realizado pelos linguistas, comentado na Seção 2.1, nesta tabela são
mostradas as diferentes famílias e dialetos que existem na base de dados do museu. Na Tabela
3.1, percebe-se que na frente de cada língua ou dialeto há um número, o qual é usado como um
identificador das línguas dentro do algoritmo que foi implementado e que será detalhado nas
próximas seções.
Embora seja significativa a quantidade de palavras armazenadas na base de dados do Museu
37
Tabela 3.1: Línguas e dialetos que estão armazenados na base de dados do Museu do Índio.
Estas serão analisadas neste trabalho.
Tronco Tupí
Famílias Tupi-Guarani Arikém Mundurukú
Línguas (3) Kamaruyá (5) Kayabí (4) Karitiána (8) Mundurukú
Dialetos
Tronco Macro-Jê
Famílias Boróro Karajá Jê
Línguas (9)Umutina (1) Karajá
Dialetos (6) Krahô
Família de Línguas Isoladas
Famílias Aruak Karib Tukano
Línguas (10) Yawalapití (7) Kuikúru (2) Tukano
Dialetos
do Índio, somente existem 6 palavras comuns para as 9 línguas documentadas e o dialeto. No
presente estudo por questões de simplicidade, foram escolhidas estas 6 palavras para a análise.
Desta forma, nosso trabalho se concentrou no estudo de um total de 60 palavras. Na Tabela 3.2
são mostradas as 6 palavras selecionadas para cada uma das línguas.
Tabela 3.2: Palavras selecionadas no estudo. Para cada uma das línguas que pertencem a base
de dados, foram escolhidas estas palavras.
Palavras Selecionadas
Água Olho
Criança Osso
Fogo Sangue
Os sinais retirados do banco de dados foram gravados com o uso de um microfone. Foi
pedido para cada pessoa dizer uma determinada palavra. Cada palavra foi dita por homens
membros das comunidades indígenas, com idades entre 20 e 70 anos. Os sinais de fala foram
quantizados, em amplitude, usando 16 bits com formato WAVE mono-canal e frequência de
amostragem de 22.050 Hz. A duração das palavras é diferente, variando também o compri-
mento dos sinais.
Inicialmente as palavras são agrupadas em 6 grupos diferentes. Estes grupos são chamados
no resto do trabalho como conjunto de palavras. Cada conjunto contém a mesma palavra dita
em diferentes línguas, dessa forma, em cada conjunto estão incluidas 10 palavras. Cada vez
que o algoritmo é executado, ele recebe como entrada um conjunto de palavras, isto é, ele
38
processa a mesma palavra dita pelas 10 línguas que há na base de dados. A seguir, é explicado
o algoritmo implementado para estimar as PDFs dos sinais de fala baseadas em uma mistura
de gaussianas. Além disso, são detalhados os procedimentos para estabelecer as semelhanças
entre as PDFs e finalmente agrupar os modelos obtidos.
3.2 Arquitetura do algoritmo proposto
O sistema proposto para procurar relações entre os sinais de fala foi desenvolvido usando
programação orientada a objeto (em inglês, Object Oriented Programing). O software foi de-
senvolvido empregando C++ e a biblioteca de funções GSL
1
. A GSL é uma biblioteca numérica
para C/C++ que contém funcionalidades embutidas para números randômicos, distribuições es-
tatísticas, matemática de matrizes, números complexos entre outras. Além disto, esta biblioteca
é de código aberto e gratuita. A flexibilidade na construção dos algoritmos e a robustez no de-
sempenho, são as principais motivações do emprego de C++ como linguagem de programação
neste trabalho.
Para organizar a implementação e a execução do processo de agrupamento dos sinais, o
algoritmo foi dividido a partir das diferentes funcionalidades. Foram identificadas quatro etapas
fundamentais:
◦ Pré-processamento dos sinais a serem analisados;
◦ Estimativa da PDF, baseada em uma mistura de gaussianas;
◦ Cálculo da matriz de distância, aplicando a divergência KL como critério de similaridade
entre os modelos;
◦ Agrupamento das misturas que representam cada palavra;
Na Figura 3.1, é ilustrado o procedimento no qual estão envolvidas as quatro funcionalida-
des anteriores. Nesta figura se observam as etapas desenvolvidas para a construção do sistema,
assim como as principais entradas e saídas. Foram criados quatro módulos para a execução das
tarefas do sistema.
O primeiro módulo é o de Pré-processamento, outro para estimar as PDFs das palavras,
chamado de módulo PDF, um módulo Medida, para calcular as divergências entre os modelos,
1
http://www.gnu.org/software/gsl/
39
Figura 3.1: Processo geral do algoritmo proposto para agrupar os modelos baseados em GMM,
que descrevem a PDF dos sinais de fala.
e por último o módulo Agrupamento com a função de construir os dendrogramas que mostram
as relações entre os modelos. O algoritmo recebe como entrada um conjunto de palavras,
definido na Seção 3.1. Este analisa de forma iterativa todas as palavras incluídas no conjunto e
para cada conjunto gera como saída, um dendrograma em que se evidenciam as relações entre
as 10 palavras que o integram.
Os sinais que integram o conjunto, são pré-processados no módulo Pré-processamento.
Neste módulo o sinal é necessariamente preparado para permitir a estimativa da PDF. A saída
do primeiro módulo representa a entrada do módulo PDF, no qual a PDF do sinal é estimada
tomando como base uma mistura de gaussianas. A função do módulo Medida é calcular a
divergência KL entre todas as PDFs estimadas no módulo anterior, para formar a matriz de
distância baseada nesta divergência. Esta matriz representa a entrada do módulo Agrupamento,
encarregado pela construção dos dendrogramas. Estes dendrogramas ilustram as relações entre
os modelos e representam a saída principal do último módulo, além de ser um dos resultados
mais importantes do sistema. A seguir se explicam as operações que integram cada um dos
módulos definidos. O funcionamento de cada módulo é explicado considerando a análise de
um único sinal.
Módulo de Pré-processamento
Este módulo recebe como entrada um vocábulo pertencente ao banco de vozes analisado.
40
O sinal de fala se considera um vetor de N componentes, em que N é o comprimento do
sinal e varia entre um sinal e outro. Na Figura 3.2, são mostradas as operações principais
desenvolvidas neste módulo.
Figura 3.2: Operações realizadas no módulo de Pré-processamento dos sinais de fala.
A operação de normalização, na Figura 3.2 se refere a normalização dos sinais, obtendo
valores de amplitudes na faixa de -1 a 1. Nesta operação, além de normalizar as amplitudes,
são eliminados do sinal, os momentos de silêncio existentes tanto no começo como no final do
vetor. Estes momentos de silêncio são retirados de forma visual, com o objetivo de não perder
amostras com informação relevante para a posterior análise do sinal. A parte a) da Figura 3.3
representa a palavra “água” dita por um membro da comunidade indígena Krahô. Como se
pode observar este sinal é simétrico e apresenta um número significativo de amostras próximas
a zero.
Figura 3.3: Sinal que representa a palavra água dita na língua índigena Kraho.
Após a operação de normalização das amplitudes e a retirada dos momentos de silêncio, é
usada a transforma de Hilbert para obter a envoltória do sinal e consequentemente a sua parte
positiva. Esta operação é mostrada na Figura 3.2. Para o cálculo da transformada de Hilbert foi
empregada a função x = hilbert(x
r
) de Matlab. A saída da função é uma sequência analítica
x = x
r
+ i ∗ x
i
, que tem parte real, x
r
, que é o sinal original, e tem parte imaginaria, x
i
, que
contêm a transformada de Hilbert. A parte imaginaria é uma versão do sinal original defasada
41
90
o
. A serie da transformada de Hilbert tem a mesma amplitude e a mesma frequência que o
sinal original. Esta transformada é comummente usada para calcular os atributos instantâneos
de uma serie de tempo, especialmente a amplitude e a frequência. Na parte b) da Figura 3.3 se
ilustra somente as amostras positivas do vetor de fala, usado como exemplo na parte a). O sinal
resultante já foi pré-processado, sendo normalizadas suas amplitudes e retirando um conjunto
de amostras do início e final do sinal original, para finalmente conseguir um sinal não-simétrico
com amplitudes entre 0 e 1 que constitui a entrada principal do módulo PDF.
Estimativa da função de distribuição de probabilidade (Módulo PDF)
A seguir se apresenta o procedimento para a implementação do algoritmo que estima a
PDF, baseada em uma mistura de gaussianas. Este módulo é considerado o mais importante
do sistema proposto, devido que tanto a estimativa das similaridades entre as PDFs como o
agrupamento dos modelos dependem dele.
Na Figura 3.4, são ilustradas as funcionalidades mais relevantes que conformam o mó-
dulo PDF. Nela se observam as entradas e as saídas requeridas pelo módulo, assim como as
operações executadas.
Figura 3.4: Operações do módulo PDF, no qual a PDF dos sinais de fala são estimadas, basea-
das em GMM.
O algoritmo EM apresentado na Seção 2.3.1, constitui a base dos métodos implementados
neste módulo. Para obter uma boa aproximação da mistura de gaussianas, a partir do método
EM, foi necessário considerar as principais limitações deste método numérico. A desvantagem
do EM é sua convergência lenta, a necessidade de um critério de parada para detectar se o algo-
ritmo atingiu o máximo global, a escolha de valores iniciais para os parâmetros da distribuição
de probabilidade que proporcionem atingir o máximo global em poucas iterações e por último
o número máximo de componentes que melhor descrevam o modelo que se quer aproximar. É
necessário considerar estas limitações para conseguir um desempenho adequado do algoritmo
proposto, assim como a melhor aproximação.
42
A escolha apropriada de um critério de parada tem sido muito discutido na literatura
(McLachlan e Krishnan, 1997). Em geral, estes critérios se basearam na variação da função de
verossimilhança ou do logaritmo dela. A característica comum em todos os critérios propostos
é que o algoritmo interrompe a iteração quando o valor do critério escolhido torna-se menor
que uma constante especificada inicialmente. Quanto menor for essa constante, mais forte será
o critério de parada. Neste trabalho é escolhido como critério de parada a diferença entre duas
estimativas sucessivas do logaritmo da função de verossimilhança λ(Θ
k
), ou seja
|λ(Θ
k+1
) − λ(Θ
k
)| < c,
em que c = 10
−5
, foi adotado depois de observar o comportamento do algoritmo em várias
execuções.
A inicialização do algoritmo EM constitui outro dos fatores de relevância no desempenho
do método. A escolha adequada para os valores iniciais dos parâmetros da mistura influen-
cia fortemente na velocidade de convergência do método e na sua capacidade de localizar o
máximo global (Marques, 2009). Em Marques (2009) se sugere três métodos de inicializa-
ção, Método dos Valores Verdadeiros (MVV), Método dos Valores Iniciais Aleatórios (MVA)
e Método dos Momentos (MM).
O primeiro método considera como valores iniciais os mesmos valores usados para gerar
a amostra. Espera-se que este método ofereça as melhores estimativas, mas não é usado em
um problema real, devido a que, nestes problemas não são conhecidos os parâmetros iniciais
que geraram o sinal. Este método é usado pelo autor como um critério de comparação, para
avaliar a estimativa dos outros dois métodos propostos. Depois de diversos ensaios, Marques
(2009) demonstra que o MM é o método que fornece os melhores resultados. Como alternativa
de inicialização, neste trabalho se propõe usar o método MM, proposto em Marques (2009). A
seguir é comentado este método além de algumas modificações realizadas.
A inicialização dos parâmetros da mistura se realiza dividindo o sinal de entrada x
1
, ..., x
n
em K-partes (número máximo de componentes gaussianos). “Devido a seu desempenho e sua
simplicidade” (Talavera, 2007), o algoritmo K-Means é empregado para fazer o particiona-
mento do sinal. A k-ésima parte da amostra é denotada usando ϕ
k
. Em cada partição ϕ
k
, é
calculada uma estimativa da média e do desvio padrão, como se mostra nas Expressões 3.1.
43
A probabilidade de ocorrência, usada para inicializar cada componente gaussiana, é estimada
empregando a Expressão 3.2. Estes valores calculados em cada partição ϕ
k
, servem para inici-
alizar as componentes gaussianas que integram a mistura.
m
ϕ
k
=
N
ϕ
K
i=0
x
i
N
,
σ
ϕ
k
=
N
ϕ
K
i=0
(x
i
− m
ϕ
k
)
2
N −1
, (3.1)
em que , m
ϕ
k
, σ
ϕ
k
são a estimativa da média e do desvio padrão da partição k e N
ϕ
k
representa
o total de elementos em cada partição.
p
ϕ
k
= 1/K, (3.2)
em que, p
ϕ
k
é a probabilidade de ocorrência de cada gaussiana e K o número máximo de
funções gaussianas na mistura.
Na Figura 3.4, são ilustradas as entradas requeridas por este módulo para o cálculo da PDF
baseada em GMM. O vetor que contém o sinal, o qual foi obtido no módulo Pré-processamento,
representa a entrada principal deste procedimento. Outras entradas consideradas são o número
máximo de componentes gaussianas que vão a integrar a mistura, junto com o critério de parada
que seguirá o algoritmo EM.
No nosso trabalho a estimativa da PDF, empregando uma mistura de gaussianas, é desen-
volvida usando a definição de GMM, comentada na Seção 2.3. Na implementação se considera,
a mistura de gaussianas, a partir da existência de uma ou várias componentes gaussianas. Cada
componente é descrita usando os parâmetros, média, desvio padrão e probabilidade de ocorrên-
cia. Seguindo o método de inicialização proposto anteriormente, o primeiro passo do algoritmo
para estimar a PDF baseado em GMM, concentra-se no cálculo dos valores iniciais dos parâ-
metros da mistura. Uma vez inicializados os parâmetros, de forma iterativa o algoritmo tenta
aproximar o modelo que melhor descreva o sinal, utilizando as Expressões 2.5, 2.6, 2.7 e 2.8,
definidas na Subseção 2.3.1.
No Algoritmo 2, é mostrado o pseudocódigo com os procedimentos básicos criados para a
implementação da estimativa da PDF, usando o algoritmo EM. Neste pseudocódigo se observa
que o algoritmo EM tem sido divido em três funções principais em correspondência com os
44
três passos definidos na Subseção 2.3.1. O primeiro passo corresponde a função Verossimi-
lhança, definida na Equação 2.4. Nós trabalhamos com o logaritmo da verossimilhança, em
detrimento da verossimilhança diretamente. Depois é empregada a função Expectância, defi-
nida pela Equação 2.5, para por último executar a função Maximização. Está última função
inclui a avaliação das Equações 2.6, 2.7 e 2.8. A função Verossimilhança, usando o modelo
aproximado, avalia a qualidade da mistura em cada uma das iterações do algoritmo. Na pri-
meira execução do algoritmo, esta função verifica o modelo resultante da inicialização dos
parâmetros, supõe-se que esta seja a pior aproximação. De forma iterativa o algoritmo es-
tima, usando a função Expectância, um novo modelo da PDF que será maximizado utilizando
a função Maximização. Em cada iteração, é calculada a diferença entre o valor atual do coefi-
ciente de máxima log-verossimilhança e o valor do coeficiente calculado na iteração anterior.
Esta diferença é comparada com o critério de parada dado como entrada. No caso de se obter
uma diferença menor que o limiar indicado como critério de parada, o algoritmo é finalizado,
resultando a aproximação do modelo que melhor descreve o vetor de entrada.
Algoritmo 2 Procedimento proposto para estimar a PDF baseada em GMM, empregando o
método EM.
Entradas: Quantidade de gaussianas (K), Sinal pré-processado x
i
(n), Critério de parada,
Número máximo de iterações.
Saída: Estimativa dos parâmetros das gaussianas θ = (θ
1
, ..., θ
K
),
for sinal pré-processado x
i
(n) do
Passo 1: Inicializar os parâmetros para cada uma das componentes gaussianas.
Usando as Equações 3.1 e 3.2
Passo 2: Iterações
while (Condição de parada ou Número máximo de iterações)
Verossimilhança, Usando a Equação 2.4
Expectância, Usando a Equação 2.5
Mazimização, Usando as Equações 2.6, 2.7 e 2.8.
end while
Passo 3: Construção da PDF avaliando a Equação 2.2 com os parâmetros estimados
θ = (θ
1
, ..., θ
K
).
end for
As principais saídas deste módulo são os valores dos parâmetros que caracterizam cada
função gaussiana, o logaritmo da função de verossimilhança e o número máximo de iterações.
Além disso, este módulo usa Gnuplot
2
para mostrar alguns resultados de forma gráfica, como
é o caso da estimativa da PDF, assim como o resto dos gráficos geradas pelo sistema.
2
http://www.gnuplot.info/
45
A PDF no presente trabalho é estimada usando uma abordagem semiparamétrica baseada
em GMM. Dada a importância da estimativa da PDF é imprescindível verificar esta aproxima-
ção, para ter certeza da veracidade dos resultados. Com a finalidade de verificar a exatidão
e a confiança do cálculo da PDF baseada em GMM, a PDF é também estimada usando uma
abordagem não-paramétrica baseada no cálculo do histograma do sinal.
Uma abordagem computacional é proposta para estimar o histograma com tamanho de
célula fixa. Como se mostra na Figura 3.4, as entradas necessárias para construir o histograma
são o sinal pré-processado e o número de células. A partir do cálculo da frequência de aparição
de cada amostra do sinal é construído, de forma iterativa, o vetor que contém as probabilidades
de ocorrência das amostras. O histograma será normalizado para que a soma sob a curva seja
1.
Neste módulo, também é implementado um procedimento para extrair a envoltória da mis-
tura. Esta aproximação constitui outra das saídas do módulo PDF. Com a finalidade de avaliar
a estimativa da PDF baseada em mistura de gaussianas, a envoltória da mistura é usada para
compará-la com o histograma calculado. Esta comparação se realiza através do cálculo do erro
quadrático médio (EQM). O histograma e o EQM também formam parte das saídas do módulo
PDF, como se ilustra na Figura 3.4.
Módulo Medida
No presente trabalho a divergência KL é proposta para medir similaridade entre modelos
baseados em misturas de gaussianas. O módulo Medida é o encarregado para procurar simila-
ridades ou diferenças entre as misturas, usando este coeficiente. A saída do módulo é a matriz
de distância baseada na divergência KL. A Figura 3.5 mostra o procedimento adotado neste
bloco.
Figura 3.5: Operações do módulo responsável por estimar as similaridades entre as misturas e
construir a matriz de distância.
Estimar a divergência KL entre GMM é um problema que não é analiticamente tratado.
46
Devido a este inconveniente a solução não é trivial. Na Subseção 2.5.2, foram comentadas
algumas das soluções para esta problemática. Neste trabalho, propõe-se construir um método
computacional que estime a divergência KL entre dois modelos baseados em misturas de gaus-
sianas, utilizando a envoltória da mistura.
No módulo PDF, é calculada a envoltória da mistura de gaussianas. Esta envoltória é re-
presentada por um vetor, o qual é empregado para estimar a divergência KL. Os vetores f(x) e
g(x) constituem as envoltórias de duas misturas. Cada um destes vetores são divididos em um
reticulado com i células igualmente espaçadas ∆i. Em cada célula se considera a ocorrência
f(x
i
) e g(x
i
) de cada vetor f(x) e g(x) respectivamente. Reescrevendo a Equação 2.10, a
divergência KL é calculada usando as envoltórias como se mostra na Equação 3.3.
D(f||g) =
N
i=0
f(x
i
)log
f(x
i
)
g(x
i
)
(3.3)
em que N é o número total de células.
Para atender às limitações da divergência KL, comentadas em Haubold e Kender (2008)
todas as envoltórias das misturas foram construídas com o mesmo número de amostras e o
comprimento dos vetores se consideram adequados para realizar este cálculo.
De acordo com a Figura 3.5, a principal entrada deste módulo é um conjunto de vetores
que representam as envoltórias das PDFs, as quais foram estimadas no módulo PDF. Usando
a Equação 3.3, calcula-se a divergência KL entre todos estes vetores de entrada e de forma
iterativa estes valores são agrupados em uma matriz quadrada não simétrica, chamada de ma-
triz KL. O número máximo de linhas e colunas desta matriz corresponde ao total de vetores
recebidos como entrada. O cálculo da divergência KL, utilizando as envoltórias das misturas,
cumpre com as propriedades desta divergência, que foram mencionadas na Seção 2.5, obtendo
uma matriz assimétrica, com todos os valores positivos e os elementos da diagonal principal
iguais a zero.
Na Seção 2.5.1 foram comentados alguns dos trabalhos dedicados a procurar funções
para simetrizar a divergência KL. Comparando as diversas técnicas que têm sido propostas,
é possível distinguir vantagens entre elas, além de identificar algumas limitações. A função
J-divergence, definida na Equação 2.12, é uma das mais comuns na literatura, apesar de cal-
cular uma das piores aproximações. Em Sepúlveda et al. (2010) é utilizada esta função para
simetrizar a divergência, destacando que fixar o valor de η = 1/2 é satisfatório sempre que
47
a matriz KL seja quase simétrica, caso contrário, os resultados de aproximação poderiam ser
inadequados.
Dentre as funções estudadas a única que cumpre com as três propriedades fundamentais
da divergência KL é a função resistor-average, definida pela Equação 2.16. Considerando a
exatidão na estimativa, este método é comparado com a distância de Chernoff, avaliada nos
textos, como o método que consegue a melhor aproximação. Além disso, a operação resistor-
average é simples de calcular em termos computacionais. Por estas razões a adotamos como
critério de simetrização da divergência KL. Neste módulo, após o cálculo da matriz KL, é usada
a função resistor average para simetrizar esta matriz, obtendo finalmente uma verdadeira matriz
de distância, que constitui a saída fundamental do módulo.
Módulo Agrupamento
O objetivo deste módulo é construir uma estrutura que evidencia as possíveis relações entre
as palavras. Para isso, decidiu-se implementar um algoritmo baseado em agrupamento hierár-
quico. Este módulo foi desenvolvido em Matlab, empregando as funções que esta ferramenta
disponibiliza. O algoritmo de agrupamento implementado segue o mesmo procedimento mos-
trado no Algoritmo 1. Seguindo as especificações do Algoritmo 1, neste estudo os elementos
que se desejam agrupar são as PDFs estimadas no módulo PDF e a matriz entre os elementos
é formada mediante a estimativa da divergência KL. Para medir a distância entre os grupos é
usada a função Z = linkage(y, methods) do matlab, em que y é a matriz KL entre as PDFs
e methods é o método de ligação média, comentado na Subseção 2.6. A escolha do método
de ligação média está relacionada ao fato dele ser um método estável que apresenta bons re-
sultados tanto para distância Euclidiana quanto para outros tipos de distância, além de ser uma
alternativa intermediaria entre os métodos de ligação por vizinho mais distante e ligação por
vizinho mais próximo. As relações entre os modelos baseados em mistura de gaussianas são
ilustradas através de dendrogramas.
3.3 Experimentos
Para realizar os experimentos foram construídos sinais simulados com o objetivo de veri-
ficar os métodos implementados. Foi priorizado o planejamento de experimentos para testar o
funcionamento do algoritmo EM e consequentemente a estimativa da PDF, devido a importân-
cia desta aproximação no algoritmo geral. O modelo baseado em GMM também foi testado
48
comparando-o com o histograma, através do EQM, da divergência KL e de outras medidas de
distância que foram propostas. Para avaliar a estimativa da divergência KL foram calculadas as
medidas de distância mais comuns em aplicações dedicadas ao processamento de sinais de fala,
por exemplo, a distância Bhattacharyya. A seguir são detalhados cada um dos experimentos
realizados.
3.3.1 Experimentos na estimativa de PDF
Considerando uma variável aleatória X, que foi gerada a partir da mistura de duas distribui-
ções gaussianas, X−N(m
1
, σ
1
)+N(m
2
, σ
2
), neste estudo foram realizados três experimentos
com o objetivo de avaliar a qualidade da PDF estimada, baseado em GMM e usando EM. O
algoritmo foi testado quando as componentes da mistura estão "bem superpostas", "bem se-
paradas"e "moderadamente separadas". Estes experimentos baseiam-se nos testes realizados
em Marques (2009). O primeiro experimento considerou os seguintes parâmetros para gerar o
sinal simulado,
m
1
= 5, m
2
= 15, σ
1
= 3, σ
2
= 4, p
1
= 0.5, p
2
= 0.5,
O segundo experimento considerou os seguintes parâmetros,
m
1
= 5, m
2
= 40, σ
1
= 3, σ
2
= 4, p
1
= 0.5, p
2
= 0.5,
O último experimento considerou os seguintes parâmetros,
m
1
= 5, m
2
= 20, σ
1
= 3, σ
2
= 4, p
1
= 0.5, p
2
= 0.5.
Cada simulação teve 1000 repetições, no caso de não atingir o critério de parada de 10
−5
.
Os três experimentos foram simulados com amostras de tamanho 500, 1000 e 5000. Na Figura
3.6, são mostrados os histogramas dos sinais com 1000 amostras gerados a partir da mistura de
duas distribuições normais descritas pelos parâmetros especificados anteriormente.
A partir da mistura de duas gaussianas obtida em cada experimento, o método da estimativa
da PDF foi avaliado em 3 aspectos:
1) Analise dos parâmetros calculados, isto foi realizado observando os valores obtidos
para cada parâmetro, média, desvio padrão e probabilidade de ocorrência das gaussianas esti-
49
Figura 3.6: Histograma dos sinais gerados a partir de duas distribuições gaussianas. (a) Histo-
grama do primeiro experimento (Bem Superpostas). (b) Histograma do segundo experimento
(Bem Separadas). (c) Histograma do terceiro experimento (Moderadamente Separadas).
madas em cada um dos experimentos elaborados.
2) Avaliação do número de gaussianas que integram a mistura, aqui se usou o critério
BIC (Bayesian Information Criterion) (Schwarz, 1978). Este critério é proposto para avaliar
a quantidade de componentes gaussianos que deveriam caracterizar a mistura. O modelo que
apresentar maior BIC será aquele que melhor modelará o sinal de fala. O BIC para uma mistura
f(X, Θ) é definido como:
BIC
f(X,Θ)
= 2λ(X, Θ) − Klog(N) (3.4)
em que λ(X, Θ) é o logaritmo da verossimilhança da mistura f(X, Θ), K é o número máximo
de gaussianas presentes no modelo, enquanto N é o comprimento do sinal.
3) Comparação com a PDF estimada usando o método do histograma. A construção
do histograma é outro dos métodos empregados para avaliar a estimativa do GMM. Usando o
EQM as duas aproximações são comparadas. Quanto menor for o valor do erro, melhor serão
as estimativas. Também se propõe comparar o histograma e o GMM calculando a divergência
KL. Espera-se que se as duas estimativas forem bem parecidas, o valor obtido seja próximo
de zero. Usar a KL como critério de validação não só é útil para comprovar a aproximação
dos modelos, como também serve para verificar se o método proposto para o cálculo desta
divergência cumpre com as propriedades de identificação e de similaridade da KL, comentadas
na Subseção 2.5.
50
3.3.2 Experimentos do cálculo da distância entre os modelos
A divergência KL é responsável neste trabalho pela estimativa das similaridades entre os
modelos aproximados. Por esse motivo é necessário ter certeza da qualidade do método pro-
posto. Um dos fatores de interesse para avaliar os resultados gerados a partir do método que
estima a KL é o cumprimento das propriedades desta divergência. Observar a matriz de dis-
tância obtida em cada execução do algoritmo serve para verificar se o método implementado
cumpre com estas propriedades. Outro fator para avaliar o cálculo desta divergência consiste
em comprovar a exatidão dos resultados e consequentemente os agrupamentos obtidos para
cada conjunto de palavras.
No algoritmo de agrupamento, as relações entre os modelos são obtidas a partir da matriz
de distância baseada na divergência KL. Estas relações, mostradas através dos dendrogramas,
poderiam ser produto da métrica de distância empregada para avaliar as semelhanças entre os
modelos, ou poderiam estar sujeitas aos modelos que foram estimados e que representam as
PDFs das palavras. Por isso, propõe-se calcular a distância entre as PDFs baseadas em GMM
empregando algumas das métricas de distância apresentadas na literatura, além da divergência
KL. Desta forma, as relações entre as palavras estariam sujeitas a um conjunto de medidas de
distância e não somente a divergência KL. Estas métricas poderiam confirmar a classificação
realizada pela divergência KL, além de oferecer novas relações. Procura-se empregar medidas
que tenham sido utilizadas em aplicações similares as abordadas no presente trabalho, sem
considerar as medidas tradicionais, cujas limitações foram mencionadas na Seção 2.4.
Embora existam diversas medidas de distância, as métricas mais empregadas para sinais
de fala são a distância Bhattacharyya e a distância KL (Jensen et al., 2007; Sfikas et al., 2005;
Goldberger et al., 2003; Salvi, 2003; Johnson e Sinanovi
´
c, 2001). A distância Bhattacharyya é
um caso particular da distância Chernoff. A distância Chernoff é apontada nos textos (Johnson
e Sinanovi
´
c, 2001) como a medida de distância que consegue as aproximações mais exatas. O
cálculo desta medida é mostrado na Equação 3.5. O principal problema da distância Chernoff
é que ela em termos computacionais é difícil de ser calculada. Por isso, empregam-se outras
alternativas como substituição desta medida, daí o uso da distância Bhattacharyya, a qual é
definida na Equação 3.6. Pode-se observar que na Equação 3.6 o parâmetro t é igual a 1/2. Em
Pereira et al. (2004) as duas métricas anteriores foram testadas quanto à proximidade de seus
resultados e foi verificado, empiricamente, que realmente a Bhattacharyya é uma aproximação
adequada da Chernoff. Em Salvi (2003) a distância de Bhattacharyya é utilizada como critério
51
comparativo para agrupar as diferentes pronúncias da língua sueca. A distância anterior é
também empregada em Sfikas et al. (2005) para medir similaridades entre modelos baseados
em mistura de gaussianas que representam as PDFs de diferentes imagens. Seguindo a utilidade
da distância Bhattacharyya, neste trabalho é proposta como outra alternativa para avaliar as
semelhanças entre as palavras que pertencem às línguas indígenas sob análise.
C(f, g) = max
0≥t≤1
− logµ(t),
onde µ(t) =
[f(x
i
)
1−t
] ∗ [g(x
i
)
t
] (3.5)
B(f, g) = −logµ(
1
2
), (3.6)
em que µ é a função definida na Equação 3.5, que representa a distância de Chernoff.
Além das duas métricas de distância mais comummente empregadas em aplicações de fala,
neste estudo se propõe utilizar outras medidas de distância. Em Cha (2007) são apresentadas
várias medidas de distância aplicadas para medir similaridade entre PDFs. O autor classificou
estas medidas em diferentes grupos seguindo um critério de semelhanças entre as sintaxes das
mesmas. Alguns dos grupos identificados em Cha (2007) são: a família Minkowski, a família
de acordes quadrados (em inglês, Squared-chord family), a família Chi-quadrado e a família
entropia de Shannon. Na família Minkowski estão incluídas a distância Euclidiana e a Manhat-
tan, além de outras funções. A distância Bhattacharyya está incluída na família de acordes
quadrados. A família entropia de Shannon agrupa medidas relacionados com o conceito de
incerteza probabilística de Shannon. Uma das medidas deste grupo é a divergência KL, além
da divergência Jensen-Shannon que será empregada no presente trabalho para medir simila-
ridade entre as PDFs. A divergência de Jensen-Shannon é uma medida simétrica e positiva
que pode ser interpretada como a distância média entre duas PDFs. A Equação 3.7 mostra o
cálculo desta divergência. A outra medida que será empregada neste estudo é a divergência
Chi-quadrado de Pearson que, como seu nome indica, pertence ao grupo Chi-quadrado. As
medidas deste grupo personificam a distância Euclidiana quadrada, sendo a mais importante a
divergência Chi-quadrado de Pearson, dado que o resto das divergências são derivações desta.
A divergência Chi-quadrado de Pearson não é simétrica e seu cálculo é mostrado na Equação
3.8.
52
D
js
(f, g) =
1
2
N
i=1
f(x)log
2f(x)
f(x) + g(x)
+
N
i=1
g(x)log
2g(x)
f(x) + g(x)
(3.7)
D
p
(f, g) =
N
i=1
(f(x) − g(x))
2
g(x)
(3.8)
Finalmente, a última medida que será implementada neste estudo foi proposta por Sfikas
et al. (2005). Em Sfikas et al. (2005) além de utilizar a distância Bhattacharyya e a divergência
KL para comparar GMMs que descreviam as PDFs de várias imagens, o autor definiu uma
nova medida de distância, chamada distância C2 e definida na Equação 3.9. Esta métrica é
zero quando f(x) e g(x) são iguais, é simétrica e positiva. A distância C2 é a última medida de
distância que será utilizada neste estudo para mostrar as relações entre as palavras das línguas
indígenas brasileiras.
C2(f, g) = −log
2
N
i=0
f(x)g(x)
N
i=0
f(x)
2
+ g(x)
2
. (3.9)
As métricas mencionadas anteriormente serão estimadas empregando a envoltória da mis-
tura e seguindo o mesmo procedimento definido para a divergência KL. No caso da divergência
Chi-quadrado de Pearson, que não é simétrica, será simetrizada utilizando a mesma função
definida para a divergência KL. Espera-se que os resultados obtidos com a distância Jensen-
Shannon sejam similares aos da divergência KL, isso pelo fato destas duas medidas pertence-
rem à mesma família. Já os resultados alcançados com as medidas Chi-quadrado de Pearson,
Bhattacharyya e C2 poderiam ser diferentes. Após definidos os critérios de similaridade entre
os modelos, no próximo capítulo serão mostrados os resultados alcançados.
53
54
Capítulo 4
Resultados e Discussões
Neste capítulo, são mostrados os resultados obtidos a partir do algoritmo implementado.
Primeiramente, são apresentados os resultados proporcionados pelos sinais simulados. Estes
sinais junto com os ensaios preparados foram definidos no Capítulo 3. Na segunda parte do
capítulo são apresentados os resultados fornecidos a partir da análise do conjunto de palavras
que pertencem às línguas indígenas brasileiras. Nestes resultados são incluídas as estimativas
da PDF baseada em mistura de gaussianas de cada palavra, além de mostrar as relações en-
contradas entre os diferentes modelos calculados. Estes resultados estão sujeitos ao algoritmo
implementado e se consideram inconclusivos e não refutam nenhuma das classificações feitas
pelos linguistas na literatura. Nosso objetivo é mostrar possíveis relações entre os modelos
estimados.
4.1 Resultados dos sinais simulados
Todas as simulações foram desenvolvidas usando o algoritmo construído no presente tra-
balho. Nos experimentos definidos na Seção 3.3, geraram-se vários sinais aleatórios a partir
de duas misturas de gaussianas, especificadas por diferentes parâmetros. Na Figura 3.6 são
ilustrados os histogramas dos sinais aleatórios com tamanho de 1000 amostras, os quais fo-
ram calculados em cada um dos 3 ensaios. Estes sinais serão empregados nesta seção para
descrever os resultados alcançados. Depois da execução dos experimentos, verificou-se que os
parâmetros estimados utilizando o algoritmo EM são próximos dos parâmetros originais. Na
implementação do algoritmo EM foram consideradas suas principais limitações: a inicialização
dos parâmetros, o critério de convergência e a condição de parada. Em geral, comprovou-se
55
que os melhores resultados foram obtidos com aqueles sinais que apresentavam maior número
de amostras. Mas os ensaios preparados com amostras de tamanho 500, 1000 e 5000, apresen-
taram resultados próximos dos parâmetros reais.
Os parâmetros definidos para descrever cada gaussiana que integra a mistura são a média, o
desvio padrão e a probabilidade de ocorrência. Estes parâmetros, calculados por meio do algo-
ritmo EM, são ilustrados na Tabela 4.1. Nela são observados os parâmetros originais para cada
experimento, seguidos dos valores aproximados para todas as misturas estimadas. Os valores
obtidos são muito próximos dos seus respectivos parâmetros originais, tanto nas amostras me-
nores quanto nas maiores. Após uma análise detalhada, percebe-se que os melhores resultados
foram fornecidos com sinais de comprimento 1000 e 5000. A melhor estimativa foi alcançada
para componentes gaussianas, moderadamente separadas e bem separadas.
Tabela 4.1: Parâmetros (Média, desvio padrão e probabilidade de ocorrência) estimados para
cada gaussiana que integra a mistura dos sinais simulados de comprimento igual a 1000 amos-
tras, nos 3 experimentos desenvolvidos.
Experimento 1
Comprimento m
1
= 5 m
2
= 15 σ
1
= 3 σ
2
= 4 p
1
= 0, 5 p
2
= 0, 5
500 4,91 15,26 3,07 4,56 0,51 0,48
1000 5,13 14,95 2,96 3,96 0,49 0,5
5000 4,98 14,67 2,89 4,09 0,48 0,51
Experimento 2
Comprimento m
1
= 5 m
2
= 40 σ
1
= 3 σ
2
= 4 p
1
= 0, 5 p
2
= 0, 5
500 4,96 39,96 3 4,04 0,5 0,5
1000 4,72 39,95 3,1 3,74 0,5 0,5
5000 5,02 40,13 2,97 3,98 0,5 0,5
Experimento 3
Comprimento m
1
= 5 m
2
= 20 σ
1
= 3 σ
2
= 4 p
1
= 0, 5 p
2
= 0, 5
500 4,79 19,66 2,74 4,24 0,48 0,51
1000 4,7 20,02 3,01 3,99 0,49 0,5
5000 4,89 20,03 2,94 3,86 0,49 0,5
Na parte a) da Figura 4.1, são ilustradas as PDFs, baseadas em mistura de gaussianas,
obtidas para cada um dos sinais simulados, de comprimento 1000 amostras. Estas PDFs foram
construídas a partir dos parâmetros calculados usando o algoritmo EM, os quais se observam
na Tabela 4.1. Cada gráfico desta figura mostra claramente as duas componentes gaussianas
que geraram o sinal original, assim como os parâmetros que as descrevem. Com o objetivo
de verificar visualmente as semelhanças entre o histograma e a envoltória da PDF dos sinais
aleatórios, na parte b) da Figura 4.1, são mostrados os histogramas e as curvas que representam
56
a envoltória dos três modelos estimados. Esta figura indica que as curvas das envoltórias,
ficaram bem ajustadas aos respectivos histogramas.
O cálculo da PDF, baseada em mistura de gaussianas, foi avaliada usando o EQM, a diver-
gência KL, a distância Chi-quadrado de Pearson, a distância Bhattacharyya, a distância C2 e
a divergência Jensen-Shannon. Estas métricas são estimadas entre o histograma e a envoltória
dos sinais simulados com o objetivo de corroborar o ajuste das misturas com seus respectivos
histogramas, além de avaliar o cumprimento da propriedade de similaridade das medidas de
distância propostas. A Tabela 4.2 apresenta o cálculo das medidas de distância e do EQM en-
tre as duas estimativas anteriores. Os melhores ajustes foram alcançados com a distância de
Bhattacharyya, com a divergência KL e com o EQM, enquanto o pior ajuste foi o da diver-
gência Chi-quadrado de Pearson. Os valores obtidos para cada medida indicam que a curva da
envoltória da mistura se ajusta satisfatoriamente ao histograma dos dados, mostrando que as
duas abordagens utilizadas para estimar a PDF dos sinais, geram resultados similares, o que é
confirmado observando a parte b) da Figura 4.1.
Tabela 4.2: Valores do erro quadrático médio, da divergência KL, da distância de Bhatta-
charyya, da divergência Chi-quadrado de Pearson, da distância Jensen-Shannon e da distância
C2 entre o histograma e a envoltória da mistura, obtidos pelo sistema implementado neste
trabalho.
Bem Superpostas Bem Separadas Moderadamente Separadas
EMQ 5,63*e-6 4,91*e-6 4,63*e-6
KL 0,038 0,04 0,041
Bhattacharyya 0,030 0,026 0,027
Chi-quadrado de Pearson 0,17 0,14 0,14
Jensen-Shannon 0,059 0,050 0,052
C2 0,087 0,068 0,084
Com o objetivo de determinar o número ótimo de gaussianas que integram a mistura que
melhor descreve o sinal foi selecionado o critério BIC. A Figura 4.2 mostra a curva do BIC
resultante para as misturas dos sinais simulados, usados como exemplo nesta seção. Nesta
figura, pode-se observar que o máximo valor do BIC correspondente ao modelo gerado a partir
de duas gaussianas é exatamente 2. Este resultado confirma a estimativa da PDF, baseada em
GMM e a eficiência do algoritmo EM na aproximação dos parâmetros.
57
Experimento 1-Bem Superpostas (m
1
= 5, m
2
= 15)
Experimento 2-Bem Separadas (m
1
= 5, m
2
= 40)
Experimento 3-Moderadamente Separadas (m
1
= 5, m
2
= 20)
Figura 4.1: Estimativa da PDF baseada em GMM, envoltória da mistura e o histograma dos
sinais simulados de comprimento 1000 amostras, gerados em cada um dos experimentos de-
senvolvidos. (a)Estimativa da PDF baseada em GMM. (b) Envoltória da mistura e histograma
do sinal gerado.
58
Figura 4.2: Evolução do critério BIC na seleção do número ótimo de gaussianas que integram
a mistura dos sinais simulados.
4.2 Resultados das palavras das línguas indígenas.
Resultados da estimativa da PDF
A PDF das palavras pertencentes às línguas indígenas brasileiras foi estimada usando uma
mistura de gaussianas. Esta mistura é construída mediante o algoritmo EM, que é inicializado
de forma diferente para cada um dos sinais. O número total de gaussianas, que integram a
mistura, é estimado pelo algoritmo para cada palavra, obtendo o modelo que melhor descreve
a PDF do sinal. Em geral, este número está incidindo na faixa de 6 a 15 componentes, tendo
maior ocorrência os modelos caracterizados por 7 ou 9 gaussianas. O algoritmo EM reconhece
o modelo que melhor descreve a PDF do sinal através do cálculo do coeficiente de verossimi-
lhança. Após a estimativa deste modelo é empregado o critério BIC com a finalidade de avaliar
o número total de gaussianas que deve caracterizar o modelo estimado. Desta forma, existe
outra medida para conferir a veracidade da PDF estimada.
Nas Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8, são mostradas as PDFs estimadas para cada uma
das palavras analisadas. Em cada figura se observa a PDF de uma mesma palavra, dita pelas 10
línguas indígenas escolhidas. Por exemplo, a Figura 4.3 mostra a PDF, baseada em GMM, da
palavra água, falada nas 10 línguas diferentes. Nas Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8, percebe-
se que cada mistura é identificada por um número e pelo nome da língua na qual pertence a
palavra. Este número foi definido na Tabela 3.1 e foi utilizado no algoritmo para identificar
cada uma das línguas estudadas. Além das misturas de gaussianas, nestes gráficos, mostram-se
as envoltórias de cada PDF, isso para ter uma ideia geral da forma que segue cada estimativa.
59
Palavra Água
Figura 4.3: Estimativa da PDF baseada em GMM da palavra água, dita em 10 línguas indí-
genas diferentes. Estas línguas estão incluídas na base de dados do Museu do Índio e foram
mencionadas na Seção 3.1. Cada PDF está identificada por um número, que se corresponde
com o número definido no Quadro 3.1 e pelo nome da língua.
60
Palavra Criança
Figura 4.4: Estimativa da PDF baseada em GMM da palavra criança, dita em 10 línguas indí-
genas diferentes. Estas línguas estão incluídas na base de dados do Museu do Índio e foram
mencionadas na Seção 3.1. Cada PDF está identificada por um número, que se corresponde
com o número definido no Quadro 3.1 e pelo nome da língua.
61
Palavra Fogo
Figura 4.5: Estimativa da PDF baseada em GMM da palavra fogo, dita em 10 línguas indí-
genas diferentes. Estas línguas estão incluídas na base de dados do Museu do Índio e foram
mencionadas na Seção 3.1. Cada PDF está identificada por um número, que se corresponde
com o número definido no Quadro 3.1 e pelo nome da língua.
62
Palavra Olho
Figura 4.6: Estimativa da PDF baseada em GMM da palavra olho, dita em 10 línguas indígenas
diferentes. Estas línguas estão incluídas na base de dados do Museu do Índio e foram menci-
onadas na Seção 3.1. Cada PDF está identificada por um número, que se corresponde com o
número definido no Quadro 3.1 e pelo nome da língua.
63
Palavra Osso
Figura 4.7: Estimativa da PDF baseada em GMM da palavra osso, dita em 10 línguas indígenas
diferentes. Estas línguas estão incluídas na base de dados do Museu do Índio e foram menci-
onadas na Seção 3.1. Cada PDF está identificada por um número, que se corresponde com o
número definido no Quadro 3.1 e pelo nome da língua.
64
Palavra Sangue
Figura 4.8: Estimativa da PDF baseada em GMM da palavra sangue, dita em 10 línguas indí-
genas diferentes. Estas línguas estão incluídas na base de dados do Museu do Índio e foram
mencionadas na Seção 3.1. Cada PDF está identificada por um número, que se corresponde
com o número definido no Quadro 3.1 e pelo nome da língua.
65
Além da representação gráfica de cada PDF, outro resultado interessante são os valores dos
parâmetros que descrevem cada uma das componentes gaussianas que integram as misturas,
contudo não serão colocados no texto, para ganhar claridade na representação dos resultados.
Os experimentos desenvolvidos com sinais simulados, na Seção 4.1, confirmam que o método
implementado consegue estimar parâmetros próximos aos originais de cada gaussiana. A partir
deste resultado e supondo que os sinais que descrevem as palavras indígenas foram gerados por
um processo aleatório que combinava um conjunto de funções gaussianas, considera-se que
as estimativas das PDF, dos sinais empregados como análise, também proporcionem valores
próximos dos originais.
Similarmente aos sinais simulados, as PDFs para as palavras analisadas também foram
estimadas usando o método de histograma. Esta última estimativa foi comparada com a envol-
tória da PDF, baseada em GMM. A comparação foi realizada empregando somente, o EQM e
a divergência KL. Estas medidas proporcionaram valores do erro na faixa entre 10
−5
e 10
−6
,
enquanto os valores da divergência KL, foram registrados perto do zero, verificando as simila-
ridades entre as duas estimativas das PDFs.
Resultados das medidas de distância
Respondendo a um dos principais objetivos do presente trabalho, foi necessário definir um
critério para estabelecer as semelhanças entre os modelos estimados. O coeficiente selecio-
nado para medir as similaridades entre os modelos que descrevem um conjunto de palavras
foi a divergência KL. Para isso foi implementado um algoritmo de agrupamento, que através
de um dendrograma mostra as distâncias entre as PDFs estimadas para cada conjunto de pala-
vras. Dada a dificuldade para calcular a divergência KL entre modelos baseados em mistura
de gaussianas, neste trabalho se estima esta métrica usando as envoltórias das misturas. Estas
envoltórias são mostradas nas Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8. O algoritmo de agrupamento
proporciona um dendrograma por cada conjunto de palavras. Lembrando que o conjunto de
palavras está integrado por uma mesma palavra dita em 10 línguas indígenas diferentes e foi
definido na Seção 3.1.
As Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8 mostram as PDFs estimadas para as palavras água,
criança, fogo, olho, osso e sangue, ditas por 10 línguas diferentes. Os dendrogramas que apre-
sentam as semelhanças entre as PDFs, são mostrados nas Figuras 4.9, 4.10, 4.11, 4.12, 4.13
e 4.14, respectivamente. Os dendrogramas anteriores foram cálculados empregrando a diver-
gência KL. Nestes gráficos de agrupamento, deseja-se ilustrar as misturas que se apresentam
66
mais relacionadas, a partir da medida de distância entre elas. As PDFs baseadas em GMM se
identificam nos dendrogramas, mediante números. Na Tabela 3.1 se define um número para
cada língua ou dialeto indígena e os gráficos das misturas utilizam este número para identificar
a língua a qual a palavra pertence.
Observando as Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8 é possível identificar algumas seme-
lhanças ou diferenças entre as PDFs baseadas em misturas de gaussianas. Após o cálculo dos
dendrogramas de cada conjunto de palavras, estas semelhanças e diferenças, são confirmadas.
Considera-se que em geral as relações ilustradas nos dendrogramas estão intimamente relaci-
onadas com as formas das misturas, é dizer, relacionadas com a quantidade de componentes
gaussianas, assim como com as características dos parâmetros que descrevem cada um dos
modelos.
Para avaliar a classificação realizada pelo algoritmo de agrupamento, usando a divergência
KL, neste estudo são empregadas as seguintes medidas: a distância Bhattacharyya, a diver-
gência Chi-quadrado de Pearson, a distância Jensen-Shannon e a distância C2. O objetivo de
empregar estas medidas de distância é obter diferentes classificações para cada um dos critérios
de similaridade propostos que de forma mais robusta permita conhecer se os agrupamentos en-
tre as diferentes palavras dependem das medidas de distância ou dos modelos estimados para
cada palavra. Nas Figuras 4.15, 4.16, 4.17, 4.18, 4.19 e 4.20 se mostram os dendrogramas
obtidos utilizando a distância Bhattacharyya. Nas Figuras 4.21, 4.22, 4.23, 4.24, 4.25 e 4.26
são observados os agrupamentos alcançados empregando a divergência Chi-quadrado de Pear-
son. Nas Figuras 4.27, 4.28, 4.29, 4.30, 4.31 e 4.32 se mostram os agrupamentos realizados
pela distância Jensen-Shannon. Finalmente, nas Figuras 4.33, 4.34, 4.35, 4.36, 4.37 e 4.38 são
mostradas as relações obtidas a partir da distância C2.
Uma observação detalhada dos dendrogramas obtidos para cada uma das medidas de dis-
tância confirma que os agrupamentos são similares aos alcançados a partir da divergência KL.
A distância que mostrou agrupamentos menos similares foi a distância C2. Por exemplo, nos
dendrogramas da palavra criança se identificam semelhanças entre as línguas identificadas pe-
los números 3 e 4, no dendrograma da distância C2 para esta palavra se observa que além de
agrupar as línguas 3 e 4 a língua 5 foi incluída no agrupamento. Este agrupamento se considera
interessante dado que as três línguas pertencem ao mesmo tronco linguístico. Isso também
acontece, no caso da palavra olho, em que a única medida que agrupa as línguas 3, 4 e 5 é a
distância C2. Nos diversos agrupamentos da palavra fogo encontram-se relacionadas as pala-
67
Dendrogramas da divergência KL
Figura 4.9: Dendrograma que ilustra as re-
lações entre os modelos que integram o
lote da palavra água.
Figura 4.10: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra criança.
Figura 4.11: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra fogo.
Figura 4.12: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra olho.
Figura 4.13: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra osso.
Figura 4.14: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra sangue.
68
vras que pertencem à língua 7 e 9. Este agrupamento não é observado no dendrograma obtido a
partir da distância C2 para a mesma palavra. Os resultados alcançados com a distância C2 são
interessantes dado que ela poderia ser considerada como um critério complementar à classifi-
cação da divergência KL. As semelhanças entre os agrupamentos resultantes era esperada para
o caso da distância Jensen-Shannon dado que pertence a mesma família que a divergência KL.
No caso das outras medidas de distância as similaridades dos agrupamentos poderiam estar
relacionados com o método computacional empregado para estimar as distâncias entre os mo-
delos mas de qualquer forma poderia-se afirmar que os agrupamentos dependem dos modelos
estimados e não das métricas de distância utilizadas.
Semelhanças entre as línguas indígenas
A abordagem empregada neste trabalho interessa-se por representar palavras de línguas
indígenas através de um modelo probabilístico que permita estabelecer similaridades e dife-
renças entre os modelos estimados. Segundo nosso critério valorativo é necessário fazer um
estudo, integrando diversas técnicas de processamento digital da fala, para conceber resultados
mais definitivos. Os resultados das línguas indígenas apresentados a seguir estão sujeitos aos
métodos matemáticos implementados e por esse motivo, não refutam nenhuma das classifi-
cações feitas pelos linguistas. Nosso interesse é mostrar relações entre algumas palavras que
pertencem a línguas indígenas no Brasil, obtidas com o algoritmo implementado e sem julgar
as relações já estabelecidas pelos estudos linguísticos.
Uma observação detalhada das Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8 permite identificar al-
guns padrões na forma da mistura de algumas palavras que pertencem a uma determinada
língua. Este é o caso dos modelos que representam as palavras da língua Tukano. As PDFs
destas palavras estão quase sempre caraterizadas por misturas em que os valores dos parâ-
metros (média e desvio padrão) são pequenos e concentrados. Acontece a mesma coisa com
as PDFs das palavras que integram a língua Kayabí, desta vez as misturas destas palavras se
caracterizam por parâmetros com valores mais espalhados, mostrando altos valores de desvio
padrão para cada componente gaussiana. Todas as palavras de outras línguas não evidenciam o
mesmo comportamento padrão, por exemplo as palavras da língua indígena Mundurukú estão
descritas por um comportamento irregular dos parâmetros, em outras palavras não é possível
estabelecer um padrão para os modelos das palavras que integram esta família.
Há algumas famílias de línguas indígenas em que as PDFs das palavras, em geral, se carac-
terizam por misturas com muitos componentes gaussianos. Um exemplo concreto são as PDFs
69
Dendrogramas da distância de Bhattacharyya
Figura 4.15: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra água.
Figura 4.16: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra criança.
Figura 4.17: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra fogo.
Figura 4.18: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra olho.
Figura 4.19: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra osso.
Figura 4.20: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra sangue.
70
Dendrogramas da distância Chi-quadrado de Pearson
Figura 4.21: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra água.
Figura 4.22: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra criança.
Figura 4.23: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra fogo.
Figura 4.24: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra olho.
Figura 4.25: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra osso.
Figura 4.26: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra sangue.
71
Dendrogramas da distância Jensen-Shannon
Figura 4.27: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra água.
Figura 4.28: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra criança.
Figura 4.29: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra fogo.
Figura 4.30: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra olho.
Figura 4.31: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra osso.
Figura 4.32: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra sangue.
72
Dendrogramas da distância C2
Figura 4.33: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra água.
Figura 4.34: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra criança.
Figura 4.35: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra fogo.
Figura 4.36: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra olho.
Figura 4.37: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra osso.
Figura 4.38: Dendrograma que ilustra as
relações entre os modelos que integram o
lote da palavra sangue.
73
das palavras que pertencem a algumas das línguas que integram o tronco Tupí, como é o caso
das línguas Kamaruyá, Kayabí e Karitiana. Nas Figuras 4.3, 4.4, 4.5, 4.6, 4.7 e 4.8 pode-se
observar que a maior parte das vezes as PDFs destas famílias apresentam este comportamento.
Um caso mais interessante ainda é o da língua Tukano, na qual as PDFs estão sempre carateri-
zadas por muitos componentes. Na maior parte das vezes estas estimativas apresentaram entre
11 e 15 gaussianas.
Dado que os agrupamentos das palavras foram similares para todas as métricas de distância,
as relações entre as línguas indígenas comentadas nesta seção serão analisadas considerando
os agrupamentos obtidos com a divergência KL. Dado que a distância C2 mostrou agrupa-
mentos diferentes para algumas palavras, estes agrupamentos serão considerados sempre que
confirmem a classificação dos linguistas. Por isso, a distância C2 será utilizada como outro cri-
tério de classificação, além da divergência KL. Na maioria dos dendrogramas construídos, os
quais mostram relações entre as palavras das línguas indígenas, há uma tendência a formar-se
grupos entre os troncos linguísticos (Figuras 2.1 e 2.2). Em outras palavras, observam-se agru-
pamentos em que estão incluídos modelos que descrevem as palavras das línguas dos troncos
Tupí ou Macro-Jê. Isto pode ser observado nas Figuras 4.10 e 4.11. Na Figura 4.10 se ob-
serva um agrupamento entre as línguas Kamaruyá (3) e Karitiána (4), que pertencem ao tronco
linguístico Tupí e um segundo agrupamento entre as línguas Karajá (1) e Krahô (6), as quais
formam parte do tronco Macro-Jê. Na Figura 4.34 pode-se observar o mesmo agrupamento
que em 4.10, com a diferença que no grupo do tronco Tupí foi incluída a língua Kayabí (5), a
qual pertence a este mesmo tronco, na classificação realizada pelos linguistas. Neste caso, será
considerado o agrupamento da distância C2 no lugar da divergência KL.
Seguindo as classificações obtidas neste trabalho, acontece frequentemente que nos grupos
integrados por palavras de determinado tronco, também são incluídas as palavras que perten-
cem as línguas isoladas. Desta forma, aparecem grupos entre as palavras do tronco Tupí por
exemplo, com alguma palavra pertencente a determinada língua isolada, isso se ilustra no den-
drograma da Figura 4.10, em que no agrupamento do tronco Macro-Jê foi incluída a língua
Tukano (2), a qual é classificada como uma língua isolada.
Outro resultado interessante, proporcionado pelo algoritmo de agrupamento, é que poucas
vezes se mostram grupos em que estejam incluídos somente modelos de palavras que perten-
cem a línguas isoladas. Segundo nosso algoritmo existe uma tendência a formar grupos entre
as palavras das línguas isoladas e as palavras que pertencem a algum dos troncos existentes.
74
Isso pode ser observado na Figura 4.12, em que estão relacionadas as línguas Umutina (9) e
Karajá (1), ambas pertencentes ao tronco Macro-Jê e a língua Kuikúru (7) que é classificada
como uma língua isolada.
Em vários dos agrupamentos realizados se observam que muitas vezes aparecem as lín-
guas Kamaruyá (3), Kayabí (5) e Karitiána (4) no mesmo grupo, segundo a classificação dos
linguistas estas três línguas pertencem ao mesmo tronco linguístico, o Tupí. Isso pode ser ob-
servado nas Figuras 4.11 e 4.12. Outras das famílias de línguas que aparecem com frequência
no mesmo grupos são as línguas Umutina (9) e Kuikúru (7), este resultado é interessante devido
a que ambas línguas pertencem a famílias diferentes, mas acontece de forma repetida o fato de-
las aparecerem juntas. A primeira língua pertence ao tronco Macro-Jê, enquanto a segunda é
classificada como uma língua isolada.
A língua Tukano (2) aparece nos dendrogramas mostrados nas Figuras 4.9, 4.10, 4.11, 4.12,
4.13 e 4.14, em diferentes grupos cada vez. As palavras desta língua, poderiam ser consideradas
as mais parecidas com o resto das palavras. Contrariamente acontece com as palavras da língua
Kayabí (5), que apresentam uma tendência a ficar isolada do resto dos grupos, isso se ilustra
nas Figuras 4.9 e 4.10, ou formar grupos com as línguas que integram seu mesmo tronco
linguístico, observado nas Figuras 4.34 e 4.36.
Os resultados mostrados nesta seção confirmam em alguns momentos as classificações rea-
lizadas pelos linguístas. Além destas relações já conhecidas na literatura, novos agrupamentos
são observados. De qualquer forma todos os agrupamentos aqui mostrados são de interesse
para o presente estudo.
75
76
Capítulo 5
Conclusões e Sugestões
O objetivo principal do presente trabalho foi construir um modelo capaz de caracterizar
determinadas palavras e que possibilitará o emprego de métricas de distância para estabelecer
semelhanças e diferenças entre os modelos estimados. Para isso foi implementado um algo-
ritmo para estimar as PDFs dos sinais, baseadas em GMM, comparar os modelos e estabelecer
relações entre as PDFs que caracterizaram as palavras. Um conjunto de palavras de línguas in-
dígenas brasileiras foram analisadas, através do emprego do algoritmo implementado. A PDF
das palavras indígenas foi estimada usando um modelo baseado em mistura de gaussianas,
enquanto a divergência KL foi escolhida para calcular as semelhanças entre estes modelos.
Diversos testes realizados com sinais simulados confirmaram que o método de estimativa
da PDF baseada em mistura de gaussianas demonstrou a capacidade de gerar as PDFs com
exatidão. Considera-se que a precisão das misturas de gaussianas foi produto da implementa-
ção do algoritmo EM. Providenciar soluções para cada uma das limitações do algoritmo EM,
determinaram o sucesso da estimativa das misturas. O método proposto para inicializar os pa-
râmetros contribuiu para conseguir uma boa e rápida aprendizagem dos modelos, em outras
palavras, obter modelos com verossimilhança alta. Um ponto importante na estimativa da mis-
tura, que melhor modela os dados, foi o emprego do critério BIC. Este critério foi crucial na
determinação do número de componentes que integraram o GMM. Este fator é considerado um
dois mais importantes na exatidão da PDF.
Considera-se que a estimativa da PDF baseada em mistura de gaussianas consegue fazer
uma caracterização adequada de cada palavra. Em geral, a estimativa se mostrou capaz de
caracterizar de forma individual determinadas palavras. Tal é assim, que algumas das PDFs, das
77
palavras analisadas, apresentaram um comportamento padrão, podendo ser identificadas por
este tipo de aproximação. A flexibilidade do número de gaussianas que integraram as misturas,
sugere ser um fator decisivo para ressaltar as características individuais de cada palavra.
A divergência KL se mostrou como uma medida de distância robusta na determinação das
semelhanças entre as PDFs estimadas. O método computacional desenvolvido para calcular
esta divergência, utilizando as envoltórias das misturas, se comportou estável, conseguindo
exatidão na estimativa, além do cumprimento de todas as propriedades da divergência KL.
A função resistor-average, empregada para simetrizar a divergência KL, garantiu precisão e
eficiência na simetrização da matriz KL.
Os dendrogramas construídos a partir da estimativa da divergência KL evidenciaram clara-
mente relações entre as PDFs. Com o cálculo destas estruturas de agrupamento utilizando ou-
tros coeficientes de similaridade, como a distância Bhattacharyya, a divergência Chi-quadrado
de Pearson, a distância Jensen-Shannon e a distância C2, foi comprovado que os agrupamen-
tos obtidos para cada medida foram similares. Este resultado é interessante porque confirma
que as relações entre os modelos dependem das características dos próprios modelos, não das
métricas de distância selecionadas, comprovando-se que o método empregado para o cálculo
da divergência KL, consegue respeitar as estimativas das PDF e que a maioria das relações
ilustradas nos dendrogramas são produto dos parâmetros que descrevem as misturas.
Os agrupamentos obtidos a partir da distância C2 foram os menos similares com respeito
aos outros. Apesar disso, em todos os casos foram consistentes com a classificação realizada
pela divergência KL e em alguns momentos mostrou classificações mais parecidas com as
realizadas pelos linguistas. Por isso, a distância C2 foi considerada como um complemento da
divergência KL. Nesse caso, propomos empregar neste estudo, as duas métricas de distância,
considerando os agrupamentos similares para as duas medidas e aquelas relações que sendo
diferentes, confirmem a classificação realizada pelos linguistas.
Embora os resultados obtidos para as palavras que integram as 10 línguas indígenas bra-
sileiras se consideram inconclusivos, as relações estabelecidas, a partir de nosso algoritmo,
foram interessantes. Para conseguir resultados mais definitivos relacionados com as classifi-
cações das línguas indígenas é necessário um estudo mais detalhado em que sejam integradas
um conjunto de técnicas de processamento de sinais de fala. O objetivo principal de nosso
trabalho foi alcançado, já que se conseguiu construir um modelo probabilístico que descreve
cada palavra das línguas indígenas e que permite estabelecer comparações entre estes modelos,
78
através de métricas de distância.
Encontrar padrões nas PDFs de algumas das palavras que pertencem a determinada famí-
lia de línguas se considera um resultado promissor porque sugere a possibilidade de estudar
diferentes comportamentos para cada uma das famílias. Neste estudo, não é possível genera-
lizar esta ideia, devido ao fato de utilizar um reduzido número de palavras. É válido ressaltar
que em muitas ocasiões, os agrupamentos ilustrados nos dendrogramas incluíam palavras que
pertenciam à mesma família linguística, confirmando a classificação de troncos linguísticos re-
alizada por Rodrigues (1986), além de dar credibilidade ao método matemático e ao algoritmo
proposto neste trabalho.
Outra questão importante é a tendência a formar grupos em que estejam incluídas pa-
lavras dos troncos linguísticos e palavras que pertencem a línguas isoladas. Dificilmente,
encontraram-se grupos em que foram agrupadas palavras pertencentes somente a línguas iso-
ladas. De forma empírica se sugere que estas relações poderiam estar acontecendo pelo fato
de que, as línguas dos troncos linguísticos são mais consolidadas e faladas por maior número
de povos. Esta poderia ser uma influência para que as línguas isoladas sejam cada vez mais
parecidas com aquelas que pertencem a um tronco linguístico mais consolidado.
Todas as afirmações anteriores são consideradas como um conjunto de questões, que ser-
vem de motivação para continuar pesquisando nestas áreas. O presente trabalho se considera
um estudo inicial que abre caminho para inúmeras pesquisas, em que será preciso a integração
de diversas áreas da ciência e a concepção de uma equipe multidisciplinar com o objetivo de
acrescentar conhecimentos a respeito das línguas indígenas brasileiras e do mundo em geral.
5.1 Trabalhos futuros
Este trabalho foi uma das primeiras abordagens na análise de línguas indígenas brasileiras,
portanto existem muitas possibilidades a serem consideradas. Alguma delas são:
◦ Aumentar o número de palavras nas análises para conseguir resultados mais definitivos;
◦ Realizar outro tipo de comparações, por exemplo, entre as palavras que pertencem a
mesma língua;
◦ Realizar um estudo para avaliar a existência de padrões entre os modelos que descrevem
as línguas;
79
◦ Embora o modelo baseado em GMM comportou-se adequado para a estimativa das PDFs
dos sinais, recomenda-se empregar outro tipo de modelo, que se apresentam na literatura
como promissórios na caraterização dos sinais de fala;
◦ Empregar outras medidas de distância entre os modelos baseados em GMM, por exemplo
estimar a informação mutua;
◦ Procurar outros métodos para estimar as distâncias propostas neste trabalho entre GMM;
◦ Realizar uma análise temporal dos sinais, considera-se que esse tipo de análise acrescen-
taria consideravelmente os critérios de classificação das palavras.
80
Referências Bibliográficas
Afifi, A., Clark, V., e May, S. (2004). Cluster Analysis. In Computer-Aided Multivariate
Analysis, Fourth Edition, pp. 417–442. Chapman Hall/CRC, Florida.
Anderberg, M. R. (1973). Cluster Analysis for Applications. New York:Academic.
Archambeau, C. e Verleysen, M. (2003). Fully Nonparametric Probability Density Function
Estimation with Finite Gaussian Mixture Models. In 5th International Conference on Ad-
vances in Pattern Recognition (ICAPR’2003), pp. 81–84.
Azzalini, A. e Capitanio, A. (1999). A Statistical Applications of Themultivariate Skewnormal
Distribution. Journal of the Royal Statistical Society, Serie B, 61:579–602.
Borman, S. (2004). The Expectation Maximization Algorithm - A Short Tutorial. University
of Notre Dame, USA.
Cha, S. (2007). Comprehensive Survey on Distance/Similarity Measures between Probability
Density Functions. International Journal of Mathematical Models and Methods in Applied
Sciences, 1(4):300–307.
Chan, A. e Vasconcelos, N. (2005). A Family of Probabilistic Kernels Based on Information
Divergence. Technical report, University of California., San Diego.
Chang, J. H., Kim, N., e Mitra, S. K. (2006). Voice Activity Detection Based on Multiple
Statistical Models. IEEE Transactions on Signal Processing, 54:1965–1976.
Chen, T., Huang, C., Chang, E., e Wang, J. (2001). Automatic Accent Identification Using
Gaussian Mixture Models. In IEEE Workshop on Automatic Speech Recognition and Un-
derstanding (ASRU 2001), pp. 343–346.
Cover, T. M. e Thomas, J. A. (1991). Elements of Information Theory. John Wiley and Sons,
Inc., New York.
81
Cristófaro-Silva, T. (2002). Morte de Língua ou Mudança Linguística?- Uma Revisão Biblio-
gráfica. Revista do Museu Antropológico, 5-6(1):55–73.
Crystal, D. (2000). Language Death. Cambridge University Press, Cambridge, UK.
Cândido, G. V. e Ribeiro, L. A. A. (2007). O Comportamento Fonológico dos Segmentos
Secundários Vocálicos nas Línguas Indígenas Brasileiras. In II Jornada de Pesquisa e Pós-
Graduação.
Do, M. N. (2003). Fast Approximation of Kullback-Leibler Distance for Dependence Trees
and Hidden Markov Models. IEEE Signal Processing Letters, 10(4):115–118.
Dustor, A. e Szware, P. (2009). Application of GMM Models to Spoken Language Recog-
nition. In 16th International Conference Mixed Desing of Integrated Circuits and Systems
(MIXDES’2009), pp. 603–606.
Erdogmus, D. e Principe, J. C. (2006). From Linear Adaptive Filtering to Nonlinear Informa-
tion Processing. IEEE Signal Processing Magazine, 23(6):14–33.
Everitt, B. S., Landau, S., e Leese, M. (2001). Cluster Analysis, 4
th
edition. Oxford University
Press Inc., New York.
Francheto, B. (1999). As Línguas Indígenas. In Índios no Brasil 2, Coleção Cadernos da TV
Escola, Ministério da Educação, Secretaria de Educação à Distância, pp. 5–20.
Gazor, S. e Zhang, W. (2003a). A Soft Voice Activity Detector Based on a Laplacian Gaussian
Model. IEEE Transactioons on Speech and Audio Processing, 11(5):498–505.
Gazor, S. e Zhang, W. (2003b). Speech Probability Distribution. IEEE Signal Processing
Letters, 10(7):204–207.
Goldberger, J., Gordon, S., e Greenspan, H. (2003). An Efficient Image Similarity Measure
Based on Approximations of KL-Divergence Between Two Gaussian Mixtures. In Ninth
IEEE International Conference on Computer Vision, vol. 1, pp. 487–493.
Gopinath, D. P., Veena, S. G., e Achuthsankar, S. N. (2008). Modeling of Vowel Duration in
Malayalam Speech Using Probability Distribution. In Speech Prosody 2008, pp. 99–102.
Gray, A. G. e Moore, A. W. (2003). Nonparametric Density Estimation: Toward Computational
Tractability. In SIAM International Conference on Data Mining (SDM), pp. 203–211.
82
Haubold, A. e Kender, J. (2008). Accommodating Sample Size Effect on Similarity Measures
in Speaker Clustering. In IEEE International Conference on Multimedia and Expo (ICME
2008), vol. 1-4, pp. 1525–1528.
Hershey, J. R. e Olsen, P. A. (2007). Approximating the Kullback Leibler Divergence between
Gaussian Mixture Models. In IEEE International Conference on Acoustics, Speech and
Signal Processing (ICASSP’2007), vol. 4, pp. 317–320.
Huber, M., Bailey, T., Durrant-Whyte, H., e Hanebeck, U. (2008). On Entropy Approximation
for Gaussian Mixture Random Vectors. In IEEE International Conference on Multisensor
Fusion and Integration for Intelligent Systems (MFI’2008), pp. 181–188.
Jensen, J. H., Ellis, D. P., Christensen, M. G., e Jensen, S. H. (2007). Evaluation of Distance
Measures between Gaussian Mixture Models of MFFCS. Technical report, Autrian Compu-
ter Society (OCG).
Johnson, D. H. e Sinanovi
´
c, S. (2001). Symmetrizing the Kullback-Leibler Distance. IEEE
Transactions on Information Theory.
Kaufman, L. e Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster
Analysis. Wiley, New York.
Kroeker, B. (2003). Aspectos da Língua Nambikuara. Sociedade Internacional de Linguística-
SIL, 2:1–101.
Ku, Y. G. e Kawasumi, M. (2008). Semiparametric Approach to Nonstationary Signal Analysis.
In IEEE International Conference on Signal Processing, Comunications and Networking
(ICAPR’2003), pp. 158–162.
Lan, T., Erdogmus, D., Ozertem, U., e Huang, Y. (2006). Estimating Mutual Information
Using Gaussian Mixture Model for Feature Ranking and Selection. In International Joint
Conference on Neural Networks (IJCNN’06), pp. 5034–5039.
Li, X. Q. e King, I. (1999). Gaussian Mixture Distance for Information Retrieval. In Procee-
dings of the International Joint Conference on Neural Networks, vol. 4, pp. 2544–2549.
Maia, M. (2006). A Revitalização de Línguas Indígenas e seu Desafio para a Educação Inter-
cultural Bilíngue. In VII Congreso Latinoamericano de Educación Intercultural Bilíngue.
83
Maia, M., Franchetto, B., Leite, Y. F., Soares, M. F., e Vieira, M. D. (1998). Comparative As-
pects of Grammar in Brazilian Indigenous Languages. DELTA: Documentação de Estudos
em Linguística Teórica e Aplicada, 14:349–375.
Marques, L. V. (2009). Um Estudo sobre a Inicialização do Algoritmo EM Aplicado à Mis-
turas Finitas de Normais Assimétricas. Dissertação de Mestrado, Universidade Federal do
Amazonas-UFAM, Manaus.
Martin, R. e Breithaupt, C. (2003). Speech Enhancement in the DFT Domain Using Lapla-
cian Speech Priors. In International Workshop on Acoustic Echo and Noise Control (IWA-
ENC2003), pp. 87–90.
McLachlan, G. e Krishnan, T. (1997). The EM Algorithm and Extensions. Wiley-Interscience
Publication, University of Queensland, Brisbane.
McLachlan, G. e Peel, D. (2000). Finite Mixture Models. Wiley-Interscience Publication,
University of Queensland, Brisbane.
Moreno, P., Ho, P., e Vasconcelos, N. (2004). A Kullback-Leibler Divergence Based Kernel
for SVM Classification in Multimedia Applications. In 17th Annual Conference on Neural
Information Processing Systems (NIPS), vol. 16, pp. 1385–1392.
Nan, F., Wang, Y., Li, F., e Yang, W. (2009). A Better Method than Tail-fitting Algorithm for
Jitter Separation Based on Gaussian Mixture Model. Journal of Electronic Testing: Theory
and Applications (JETTA), pp. 1–6.
Nasser, S., Alkhaldi, R., e Vert, G. (2006). A Modified Fuzzy K-means Clustering Using
Expectation Maximization. In IEEE International Conference on Fuzzy Systems, pp. 231–
235.
Nolazco, J. A., Salgado, L. R., e Peña, M. (2005). Speaker Dependent ASRs for Huastec and
Western Huastec Nahuatl Languages. Lecture Notes in Computer Science, II(3523):595–
602.
Olson, K. S. e Mielke, J. (2007). Acoustic Properties of the Kagayanen Vowel Space. In 16th
International Congress of Phonetic Sciences (ICPhS XVI), pp. 845–848.
Parker, S. (2007). An Acoustic Analysis of Cusco Quechua. Revista de la Facultad de Huma-
nidades y Lenguas Modernas, Universidad Ricardo Palma, (3):1–12.
84
Pereira, R. N., Gubitoso, M. D., e Zanotto, P. (2004). BlastPhen Agrupamento por Similaridade
com Genomas Completos. Technical report, Universidade de São Paulo, São Paulo.
Petridou, S. G., Koutsonikola, V., Vakali, A. I., e Papadimitriou, G. I. (2006). A Divergence-
Oriented Approach for Web Users Clustering. Lecture Notes in Computer Science, pp. 1229–
1238.
Raykar, V. C. (2002). Probability Density Function Estimation by Different Methods. Technical
report, University of Maryland., USA.
Reynolds, D. A. e Rose, R. C. (1995). Robust Text-Independent Speaker Identification Using
Gaussian Mixture Models. IEEE Transactions on speech and audio processing, 3(1):72–83.
Rodrigues, A. D. (1986). Línguas Brasileiras – para o Conhecimento das Línguas Indígenas.
Edições Loyola, São Paulo.
Salvi, G. (2003). Accent Clustering in Swedish Using the Bhattacharyya Distance. In Procee-
dings of the International Congress of Phonetic Sciences (ICPhS, pp. 1149–1152.
Scalassara, P. R. (2009). Utilização de Medidas de Previsibilidade em Sinais de Voz para
Discriminação de Patologias de Laringe. Tese de Doutorado, EESC-USP, São Carlos.
Scalassara, P. R., Dajer, M. E., Maciel, C. D., e Guido, R. C. (2009a). Relative Entropy
Measures Applied to Healthy and Pathological Voice Characterization. Applied Mathematics
and Computation, 207:95–108.
Scalassara, P. R., Maciel, C. D., Pereira, J. C., e Oliveira, S. (2009b). Problems with Nonpara-
metric Entropy Estimation of Voice Signals. In 20th International Congress of Mechanical
Engineering (COBEM’2009), vol. 1, p. 1677.
Schwarz, G. (1978). Estimating the Dimension of a Model. Annal of Statistics, 6(1):461–464.
Seghouane, A. K. e Amari, S. I. (2007). The AIC Criterion and Symmetrizing the Kullback-
Leibler Divergence. IEEE Transactions on Neural Networks, 18(1):97–106.
Seki, L. (2000). Línguas Indígenas no Brasil No Limiar do Século XXI. Impulso, 12(27):157–
170.
Sepúlveda, L., Maciel, C., Pereira, J. C., Scalassara, P., e Petronio, A. (2010). Divergence
of Languages Among Brazilian Indigenous Peoples. In 17th International Workshop on
Systems, Signals and Image Processing (IWSSIP 2010), pp. 364–367.
85
Sfikas, G., Constantinopoulos, C., Likas, A., e Galatsanos, N. (2005). An Analytic Distance
Metric for Gaussian Mixture Models with Application in Image Retrieval. In Duch, W.,
Kacprzyk, J., Oja, E., e Zadrozny, S. (Eds.), Artificial Neural Networks: Formal Models
and Their Applications - ICANN 2005, vol. 3697 of Lecture Notes in Computer Science, pp.
835–840. Springer Berlin / Heidelberg.
Shin, J., Chang, J., e Kim, N. S. (2005). Statistical Modeling of Speech Signals Based on
Generalized Gamma Distribution. IEEE Signal Processing Letters, 12(3):258–261.
Talavera, E. V. (2007). Métodos Bayesianos Aplicados em Taxonomia Molecular. Dissertação
de Mestrado, EESC-USP, São Carlos.
Tan, P., Steinbach, M., e Kumar, V. (2006). Cluster Analysis: Basic Concepts and Algorithms.
In Introduction to Data Mining, pp. 361–391. Addison-Wesley, Minnesota.
Tomasi, C. (2004). Estimating Gaussian Mixture Densities with EM - A Tutorial. Technical
report, Duke University.
Viola, P., Schraudolph, N. N., e Sejnowski, T. J. (1996). Empirical Entropy Manipulation for
Real-World Problems. In Advances in Neural Information Processing Systems (NIPS*96),
pp. 851–857.
Weixiang, L., Tianfu, W., Siping, C., e Aifa, T. (2009). Hierarchical Clustering of Gene Ex-
pression Data with Divergence Measure. In 3rd International Conference on Bioinformatics
and Biomedical Engineering (iCBBE 2009), pp. 1–3.
86
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
