Learning vector quantization: Difference between revisions

Revision as of 00:04, 23 May 2025

Latest revision as of 22:46, 19 June 2025

(13 intermediate revisions by 3 users not shown)

Line 12:

==Algorithm==

The algorithms are presented as in.<ref>{{Citation |last=Kohonen |first=Teuvo |title=Learning Vector Quantization |date=2001 |work=Self-Organizing Maps |volume=30 |pages=245–261 |url=http://link.springer.com/10.1007/978-3-642-56927-2_6 |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-56927-2_6 |isbn=978-3-540-67921-9|url-access=subscription }}</ref>

The algorithm consists of three basic steps. The algorithm's input is:

* how many neurons the system will have <math>M</math> (in the simplest case it is equal to the number of classes)

* what weight each neuron has <math>\vec{w_i}</math> for <math>i = 0,1,...,M - 1 </math>

* the corresponding label <math>c_i</math> to each neuron <math> \vec{w_i} </math>

* how fast the neurons are learning <math> \eta </math>

* and an input list <math> L </math> containing all the vectors of which the labels are known already (training set).

Set up:

The algorithm's flow is:

# For next input <math>\vec{x}</math> (with label <math>y</math>) in <math> L </math> find the closest neuron <math>\vec{w_m}</math>, <br>i.e. <math>d(\vec{x},\vec{w_m}) = \min\limits_i {d(\vec{x},\vec{w_i})} </math>, where <math>\, d</math> is the metric used ( [[Euclidean distance|Euclidean]], etc. )

* Let the data be denoted by <math>x_i \in \R^D</math>, and their corresponding labels by <math>y_i \in \{1, 2, \dots, C\}</math>.

* The complete dataset is <math>\{(x_i, y_i)\}_{i=1}^N</math>.

* The set of code vectors is <math>w_j \in \R^D</math>.

* The learning rate at iteration step <math>t</math> is denoted by <math>\alpha_t</math>.

* The hyperparameters <math>w</math> and <math>\epsilon</math> are used by LVQ2 and LVQ3. The original paper suggests <math>\epsilon \in [0.1, 0.5]</math> and <math>w \in [0.2, 0.3]</math>.

=== LVQ1 ===

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

# Sample a datum <math>x_i</math>, and find out the code vector <math>w_j</math>, such that <math>x_i</math> falls within the [[Voronoi diagram|Voronoi cell]] of <math>w_j</math>.

# If its label <math>y_i</math> is the same as that of <math>w_j</math>, then <math>w_j \leftarrow w_j + \alpha_t(x_i - w_j)</math>, otherwise, <math>w_j \leftarrow w_j - \alpha_t(x_i - w_j)</math>.

=== LVQ2 ===

LVQ2 is the same as LVQ3, but with this sentence removed: "If <math>w_j</math> and <math>w_k</math> and <math>x_i</math> have the same class, then <math>w_j \leftarrow w_j - \alpha_t(x_i - w_j)</math> and <math>w_k \leftarrow w_k + \alpha_t(x_i - w_k)</math>.". If <math>w_j</math> and <math>w_k</math> and <math>x_i</math> have the same class, then nothing happens.

=== LVQ3 ===

[[File:Apollonian_circles.svg|thumb|Some Apollonian circles. Every blue circle intersects every red circle at a right angle. Every red circle passes through the two points ''{{mvar|C, D}}'', and every blue circle separates the two points.]]

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

# Sample a datum <math>x_i</math>, and find out two code vectors <math>w_j, w_k</math> closest to it.

# Let <math>d_j := \|x_i - w_j\|, d_k := \|x_i - w_k\|</math>.

# If <math>\min \left(\frac{d_j}{d_k}, \frac{d_k}{d_j}\right)>s </math>, where <math>s=\frac{1-w}{1+w}</math>, then

#* If <math>w_j</math> and <math>x_i</math> have the same class, and <math>w_k</math> and <math>x_i</math> have different classes, then <math>w_j \leftarrow w_j + \alpha_t(x_i - w_j)</math> and <math>w_k \leftarrow w_k - \alpha_t(x_i - w_k)</math>.

#* If <math>w_k</math> and <math>x_i</math> have the same class, and <math>w_j</math> and <math>x_i</math> have different classes, then <math>w_j \leftarrow w_j - \alpha_t(x_i - w_j)</math> and <math>w_k \leftarrow w_k + \alpha_t(x_i - w_k)</math>.

#* If <math>w_j</math> and <math>w_k</math> and <math>x_i</math> have the same class, then <math>w_j \leftarrow w_j - \epsilon\alpha_t(x_i - w_j)</math> and <math>w_k \leftarrow w_k + \epsilon\alpha_t(x_i - w_k)</math>.

#* If <math>w_k</math> and <math>x_i</math> have different classes, and <math>w_j</math> and <math>x_i</math> have different classes, then the original paper simply does not explain what happens in this case, but presumably nothing happens in this case.

# Otherwise, skip.

Note that condition <math>\min \left(\frac{d_j}{d_k}, \frac{d_k}{d_j}\right)>s </math>, where <math>s=\frac{1-w}{1+w}</math>, precisely means that the point <math>x_i</math> falls between two [[Apollonian circles|Apollonian spheres]].

== References ==

Line 26 ⟶ 49:

== Further reading ==

* {{cite journal |last1=Somervuo |first1=Panu |last2=Kohonen |first2=Teuvo |date=1999 |title=Self-organizing maps and learning vector quantization for feature sequences |journal=Neural Processing Letters |volume=10 |issue=2 |pages=151–159 |doi=10.1023/A:1018741720065}}

* [http://www.cis.hut.fi/panus/papers/dtwsom.pdf Self-Organizing Maps and Learning Vector Quantization for Feature Sequences, Somervuo and Kohonen. 2004] (pdf)

* {{Cite journal |last=Nova |first=David |last2=Estévez |first2=Pablo A. |date=2014-09-01 |title=A review of learning vector quantization classifiers |url=https://link.springer.com/article/10.1007/s00521-013-1535-3 |journal=Neural Computing and Applications |language=en |volume=25 |issue=3 |pages=511–524 |doi=10.1007/s00521-013-1535-3 |issn=1433-3058|arxiv=1509.07093 }}

== External links ==