Generalized Hebbian Algorithm for Incremental Singular Value Decomposition in Natural Language Processing

Generalized Hebbian Algorithm for Incremental Singular Value Decomposition in Natural Language Processing Genevieve Gorrell Department of Computer and Information Science Link¨oping University 581 83 LINK¨OPING Sweden gengo@ida.liu.se Abstract An algorithm based on the Generalized Hebbian Algorithm is described that allows the singular value decomposition of a dataset to be learned based on single observation pairs presented seri- ally. The algorithm has minimal mem- ory requirements, and is therefore in- teresting in the natural language do- main, where very large datasets are of- ten used, and datasets quickly become intractable. The technique is demon- strated on the task of learning word and letter bigram pairs from text. 1 Introduction Dimensionality reduction techniques are of great relevance within the field of natural lan- guage processing. A persistent problem within language processing is the over-specificity of language, and the sparsity of data. Corpus- based techniques depend on a sufficiency of examples in order to model human language use, but the Zipfian nature of frequency be- haviour in language means that this approach has diminishing returns with corpus size. In short, there are a large number of ways to say the same thing, and no matter how large your corpus is, you will never cover all the things that might reasonably be said. Language is often too rich for the task being performed; for example it can be difficult to establish that two documents are discussing the same topic. Likewise no matter how much data your sys- tem has seen during training, it will invari- ably see something new at run-time in a do- main of any complexity. Any approach to au- tomatic natural language processing will en- counter this problem on several levels, creat- ing a need for techniques which compensate for this. Imagine we have a set of data stored as a matrix. Techniques based on eigen decomposi- tion allow such a matrix to be transformed into a set of orthogonal vectors, each with an asso- ciated “strength”, or eigenvalue. This trans- formation allows the data contained in the ma- trix to be compressed; by discarding the less significant vectors (dimensions) the matrix can be approximated with fewer numbers. This is what is meant by dimensionality reduction. The technique is guaranteed to return the clos- est (least squared error) approximation possi- ble for a given number of numbers (Golub and Reinsch, 1970). In certain domains, however, the technique has even greater significance. It is effectively forcing the data through a bot- tleneck; requiring it to describe itself using an impoverished construct set. This can al- low the critical underlying features to reveal themselves. In language, for example, these features might be semantic constructs. It can also improve the data, in the case that the de- tail is noise, or richness not relevant to the task. Singular value decomposition (SVD) is a near relative of eigen decomposition, appro- priate to domains where input is asymmetri- cal. The best known application of singular value decomposition within natural language processing is Latent Semantic Analysis (Deer- …

Content truncated to 500 words