Dictionary sparsification for kernel methods
| Autor: | André Amaro Bueno |
|---|---|
| Přispěvatelé: | Magno Teófilo Madeira da Silva, José Carlos Moreira Bermudez, Aline de Oliveira Neves Panazio |
| Jazyk: | portugalština |
| Rok vydání: | 2020 |
| Zdroj: | Biblioteca Digital de Teses e Dissertações da USP Universidade de São Paulo (USP) instacron:USP |
| Popis: | Métodos baseados em núcleo (kernel) são capazes de resolver problemas não lineares, projetando o vetor de entrada em um espaço de dimensão mais alta, onde se utiliza um método linear. Esses métodos têm sido amplamente utilizados em conjunto com diferentes técnicas de processamento de sinais e aprendizado de máquina, como máquinas de vetores de suporte, análise de componentes principais, filtragem adaptativa, entre outras. Uma das maiores dificuldades encontradas nesses métodos é a necessidade de armazenar um conjunto de vetores de entrada, denominado dicionário. Muitas vezes, o dicionário pode se tornar grande demais o que causa um aumento exagerado no custo computacional. Para evitar um crescimento muito grande do dicionário, surgiram na literatura diferentes técnicas de esparsificação. Neste trabalho, é proposta uma técnica de esparsificação de dicionários para métodos kernel baseada no processo de ortogonalização de Gram-Schmidt. Ela projeta os vetores mapeados pelo kernel em um subespaço de dimensão finita gerado por uma base ortonormal e pode ser usada com qualquer kernel de Mercer. Em particular, a técnica proposta é aplicada a um algoritmo do tipo LMS (least-mean-square). Resultados de simulação mostram que o algoritmo proposto consegue manter um bom desempenho em termos de erro quadrático médio e apresenta um custo computacional menor quando comparado com o algoritmo kernel LMS implementado com outras técnicas de esparsificação. Por fim, também se propõe uma forma de retirar vetores do dicionário, o que é particularmente interessante quando há alterações no ambiente em que o algoritmo é empregado. Kernel based methods are capable of solving nonlinear problems by projecting the input vectors in a higher dimensional space where a linear method is used. These methods have been widely used in conjunction with different techniques of signal processing and machine learning, as support vector machines, principal component analysis, adaptive filtering among others. One of the main drawbacks of these methods is that a set of input vectors, known as dictionary, needs to be stored in memory. In certain situations, the dictionary may become too big, which leads to a high computational cost. To avoid an exagerated growth of the dictionary, different sparsification techniques were proposed in the literature. In this work, we propose a sparsification technique for kernel methods based on the Gram-Schmidt orthogonalization process. It projects the vectors mapped by the kernel into a finite-dimensional subspace spanned by an orthonormal basis and can be used with any Mercer kernel. In particular, the proposed technique is applied to a least-mean-square-type (LMS) algorithm. Simulation results show that the proposed algorithm mantains a good mean-square-error performance and presents a smaller computational cost, when compared with the kernel LMS algorithm using other sparsification techniques. Furthermore, we also propose a method for removing vectors from the dictionary, which is particularly interesting when there are changes the environment where the algorithm is used. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|