# Difficulty in understanding a vector quantization algorithm

Neural gas for vector quantizationpaper explains a technique for symbolizing or quantizing data. Algorithm presents the algorithm in Section 4. An application in EEG data symbolization is presented Application. In the Application it is shown that an n- dimensional data like EEG recordings is vectorized to 1D. But Neural gas is basically an unsupervised clustering algorithm where data can be assigned to more than one cluster.

The definition of Vector Quantization (VQ) is the process of quantizing n-dimensional input vectors to a limited set of n-dimensional output vectors referred to as code-vectors. The set of possible code-vectors is called the codebook. The codebook is usually generated by clustering a given set of training vectors (called training set), the codebook is then used to quantize input vectors.

What I do not understand is that how a multi dimensional data is converted to single dimension as in the Application paper and the module where the symbols are assigned. In the Algorithm, I did not understand what is "reference vector $w_{c_i}$, the set $A$ and Step 3 where it says to order all elements of $A$ according to distance. What is the distance measure here?

Can somebody please explain the algorithm in simple terms how the symbolization is done? Thank you

Neural Gas is just a soft version of k-means clustering. in k-means , you just move the closest reference vector towards your training pattern, in neural gas, you are also moving the other reference vectors ( weighted according to their "closeness" , ie 1 -nearest, ...,k kth-nearest refence vector).

the point is that this soft version can [potentially/and more slowly] find better clusters because it avoids getting stuck in local minima... so after training you are just using the nearest reference vector to symbolise the data

reference vector w_{c_i} is then one of the reference vectors (code-vectors), in order of closeness ( just Euclidean distance) to the current training vector.

so "where it says to order all elements of A according to distance. What is the distance measure here?" -. A is just your codebook (of refence vectors). for each training pattern you rank the refence vectors according to how close they are to that training pattern, and apply the training rule. the distance measure is just euclidean distance.

symbolisation is done by just returning the index into your codebook of vectors... it is not turning it into a 1 dimensional space . its just like reading off the position in a dictionary - the position does not encode any "useful" information (ie about the meaning off the word)

• Thank you for your reply.(A)I thought the code vectors are the number of symbols used to represent the data say symbols from 1-10 range.Reference vector is still unclear.(B)If symbolization does not provide any useful information then how is it used in the Application paper for activity recognition.There is another symbolization method saxproject.org (symbolic aggregate) which has been used in dimensional reduction,anomaly detection etc.All these are basically clustering algo.Could you please let me know of the applications of using neural gas or any other clustering algorithm. – SKM Aug 1 '13 at 15:45
• code vectors=reference vectors is the multi dimensional "prototype"...eg you have a salesman travelling around america, and your vector is the geographical position the salesman is each night ( x,y coordinates say). then your codebook vectors may well end up being the geographic position of the major cities. your symbol is then the city name. then each element in your codebook is a city, and the code vector is the x,y coordinates of the city, and the symbolisation is the city name. so the "1-d" sequence is New York, Boston, LA, Chicago... – seanv507 Aug 1 '13 at 19:25
• symbolisation: a) clearly the name "New York" doesn't tell you anything about geographic position,distance between cities etc (or anything else). however, the sequence of names is still providing useful information... – seanv507 Aug 1 '13 at 19:31
• Thank you for your clarification,shall be grateful for few more(A)size of code vectors = size of input data?(B)How does the algorithm decide upon the number of symbols to represent the data?So,let a sequence be 12145, then both the 1's would refer to the same information in the code vector?(C)I read that neural gas assigns index of the nearest winning code vector, but in this case there will be ambiguity.If vectorization does not help in dimension reduction and it just gives information about temporal ordering, then how come it is used in data mining when the actual info abt "data" is lost? – SKM Aug 1 '13 at 23:38
• each code vector corresponds to a centre around which the data cluster, a prototypical point[eg New Yok City Centre coordinates], so yes is exactly the same dimension as the input patterns. B) you have to decide the number of codebook vectors before hand, then you run neural gas [ ie trial and error!] . You are replacing vectors (eg x,y coordinates) by a symbol, eg New York, Boston,... so the symbols 1,2,1,4,5 = New York, Boston, New York, LA, Chicago... no ambiguity... and in terms of categorising sequences/machine learning, the symbol description may be sufficient – seanv507 Aug 2 '13 at 8:43