Revisão Bibliográfica: Learning Vector Quantization 28/04/2003
Quantização hierárquica de vetores
Download 488.92 Kb.
|
- Navigate this page:
- Learning Vector Quantization
Palavras chaves: quantização de vetores Um dos problemas de se aplicar a quantização de vetores em situações reais é o enorme tempo consumido na fase de codificação. Isto ocorre porque para cada vetor de entrada x é necessário encontrar o vetor de reconstrução que minimize o erro (diferença entre x e x’). Conseqüentemente, um quantizador de vetores que possua uma ordem de N vetores de reconstrução, fará N comparações para identificar o melhor vetor de reconstrução. Uma maneira de reduzir este tempo de comparação é utilizar camadas de quantizadores de vetor. Desta maneira, o codebook dos quantizadores de vetor é reduzido, aumentado a velocidade da busca pelas tabelas de vetores de reconstrução. A figura abaixo ilustra este caso: Quantização de vetor com uma única camada Quantização de vetor hierárquica (duas camadas) Saida
Saida
de vetor
Quantizadores de vetor (1a camada)  
8 entradas  
8 entradas Figura 3. Exemplo quantização hierárquica de vetor Neste processo de separação em camadas existe uma perda de qualidade na restauração. Entretanto, esta perda pode ser controlada pelos algoritmos de treinamento de cada quantizador de vetor e, dependendo do número de entradas da aplicação, o ganho em velocidade de codificação pode ser bastante vantajoso. 2.1. Principal referência: 1) Luttrell, S.P., “Hierarchical vector quantization.” IEEE Proceedings (London) 136 (Part I), 405-413, 1989.
Palavras chaves: quantização de vetores, quantização hierárquica de vetores, treinamento não-supervisionado, treinamento supervisionado, self organizing maps, auto-organização, vetor de Voronoi, célula de Voronoi O conceito de learning vector quatization (LVQ) iniciou com Kohonen (1986). LVQ é uma técnica de treinamento supervisionado que usa informações de classe para mover moderadamente os vetores de Voronoi, buscando melhorar a qualidade das regiões de decisão do classificador. Seja x um vetor de entrada escolhido aleatoriamente. Seja wc o vetor de Voronoi mais próximo de x. Se a classe do vetor x for idêntica à classe do vetor de Voronoi wc, o vetor wc é movido na direção de x. Se a classe de wc for distinta da classe de x, wc é movido na direção oposta de x. Resumo do algoritmo LVQ1 (Kohonen ,1990): 1. Escolher um vetor de entrada x aleatoriamente. 2. Encontrar o vetor de Voronoi wc mais próximo de x. 3.1. Se a classe de wc for igual à de x, fazer: wc(n+1) = wc(n) + [x – wc] 3.2. Se a classe de wc for diferente da classe de x, fazer: wc(n+1) = wc(n) - [x – wc] 4. Não altere nenhum dos outros vetores de Voronoi. 5. Volte ao passo 1 e pare quando o número de épocas for superior ao máximo estipulado. É recomendável iniciar a taxa de aprendizado com valores da ordem de 0.1 e decrescê-la linear com a quantidade de iterações. Um estudo sobre a convergência deste algoritmo é encontrada em Baras e La Vigna (1990). 3.1. Principais referências: 1) Kohonen, T., “Learning vector quantization for pattern recognition” Technical Report TKK-F-A601. Helsinki University of Technology, Finland, 1986. 2) Kohonen, T., “Improved versions of learning vector quantization” International Joint Conference on Neural Networks, Vol.1, pp. 545-550, San Diego, CA, 1990. 3) Kohonen, T., Kangas J., Laaksonen J., Torkkola K., “LVQ-PAK: The learning vector quantization Program Package.” Helsinki University of Technology, Finland, 1992. Observação: Em Kohonen (1990) são apresentados três algoritmos de learning vector quantization. Kohonen et al. (1992) descreve um pacote de programas de computador para uma implementação bem sucedida de uma versão do algoritmo (LVQ1) de Kohonen (1990). 4) Baras, J.S., La Vigna A., “Convergence of Kohonen’s learning vector quantization.” International Joint Conference on Neural Networks, vol. 3, pp17-20, San Diego, CA, 1990.
|
