Learning vector quantization

Algorithm

The algorithms are presented as in.

Set up:

• Let the data be denoted by ${\displaystyle x_i\in {\mathbb{R}}^D}$, and their corresponding labels by ${\displaystyle y_i\in \{1,2,\dots ,C\}}$.
• The complete dataset is ${\displaystyle \{(x_i,y_i){\}}_{i=1}^N}$.
• The set of code vectors is ${\displaystyle w_j\in {\mathbb{R}}^D}$.
• The learning rate at iteration step ${\displaystyle t}$ is denoted by ${\displaystyle {\alpha }_t}$.
• The hyperparameters ${\displaystyle w}$ and ${\displaystyle ϵ}$ are used by LVQ2 and LVQ3. The original paper suggests ${\displaystyle ϵ\in [0.1,0.5]}$ and ${\displaystyle w\in [0.2,0.3]}$.

LVQ1

Initialize several code vectors per label. Iterate until convergence criteria is reached.

1. Sample a datum ${\displaystyle x_i}$, and find out the code vector ${\displaystyle w_j}$, such that ${\displaystyle x_i}$ falls within the Voronoi cell of ${\displaystyle w_j}$.
2. If its label ${\displaystyle y_i}$ is the same as that of ${\displaystyle w_j}$, then ${\displaystyle w_j\leftarrow w_j+{\alpha }_t(x_i-w_j)}$, otherwise, ${\displaystyle w_j\leftarrow w_j-{\alpha }_t(x_i-w_j)}$.

LVQ2

LVQ2 is the same as LVQ3, but with this sentence removed: "If ${\displaystyle w_j}$ and ${\displaystyle w_k}$ and ${\displaystyle x_i}$ have the same class, then ${\displaystyle w_j\leftarrow w_j-{\alpha }_t(x_i-w_j)}$ and ${\displaystyle w_k\leftarrow w_k+{\alpha }_t(x_i-w_k)}$.". If ${\displaystyle w_j}$ and ${\displaystyle w_k}$ and ${\displaystyle x_i}$ have the same class, then nothing happens.

LVQ3

Initialize several code vectors per label. Iterate until convergence criteria is reached.

1. Sample a datum ${\displaystyle x_i}$, and find out two code vectors ${\displaystyle w_j,w_k}$ closest to it.
2. Let ${\displaystyle d_j:=\Vert x_i-w_j\Vert ,d_k:=\Vert x_i-w_k\Vert }$.
3. If ${\displaystyle min\left(\frac{d_j}{d_k},\frac{d_k}{d_j}\right)>s}$, where ${\displaystyle s=\frac{1-w}{1+w}}$, then
   • If ${\displaystyle w_j}$ and ${\displaystyle x_i}$ have the same class, and ${\displaystyle w_k}$ and ${\displaystyle x_i}$ have different classes, then ${\displaystyle w_j\leftarrow w_j+{\alpha }_t(x_i-w_j)}$ and ${\displaystyle w_k\leftarrow w_k-{\alpha }_t(x_i-w_k)}$.
   • If ${\displaystyle w_k}$ and ${\displaystyle x_i}$ have the same class, and ${\displaystyle w_j}$ and ${\displaystyle x_i}$ have different classes, then ${\displaystyle w_j\leftarrow w_j-{\alpha }_t(x_i-w_j)}$ and ${\displaystyle w_k\leftarrow w_k+{\alpha }_t(x_i-w_k)}$.
   • If ${\displaystyle w_j}$ and ${\displaystyle w_k}$ and ${\displaystyle x_i}$ have the same class, then ${\displaystyle w_j\leftarrow w_j-ϵ{\alpha }_t(x_i-w_j)}$ and ${\displaystyle w_k\leftarrow w_k+ϵ{\alpha }_t(x_i-w_k)}$.
   • If ${\displaystyle w_k}$ and ${\displaystyle x_i}$ have different classes, and ${\displaystyle w_j}$ and ${\displaystyle x_i}$ have different classes, then the original paper simply does not explain what happens in this case, but presumably nothing happens in this case.
4. Otherwise, skip.

Note that condition ${\displaystyle min\left(\frac{d_j}{d_k},\frac{d_k}{d_j}\right)>s}$, where ${\displaystyle s=\frac{1-w}{1+w}}$, precisely means that the point ${\displaystyle x_i}$ falls between two Apollonian spheres.