# Classification of descriptions and summary using multiple passes of
statistical and natural language toolkits

Saumya Banthia
Synechron Innovation Lab
<EMAIL_ADDRESS>
Anantha Sharma
Synechron Innovation Lab
<EMAIL_ADDRESS>

###### Abstract

This document describes a possible approach that can be used to check the
relevance of a summary / definition of an entity with respect to its name.
This classifier focuses on the relevancy of an entity’s name to its summary /
definition, in other words, it is a name relevance check. The percentage score
obtained from this approach can be used either on its own or used to
supplement scores obtained from other metrics to arrive upon a final
classification; at the end of the document, potential improvements have also
been outlined. The dataset that this document focuses on achieving an
objective score is a list of package names and their respective summaries
(sourced from pypi.org [1]).

_Keywords_ summary classification $\cdot$ definition classification $\cdot$
name relevance

##  1 Introduction

The dataset we set out to work with, contains 982 entries (982 sets of names
and their summaries). The data was sourced from PyPi [1], which is a popular
python package repository.

This dataset had the following challenges:

  * •

In many cases word abbreviations and acronyms were used in the package names,
while their full forms in the summary text.

  * •

Quantum of the summary text did not automatically mean a good summary.

  * •

Some of the entries also have partial text or misspelling(s).

##  2 About the data

The Python Package Index (PyPi) [1] is a popular python programming language
repository with each package having a relatively detailed summary.

The characteristics of the summary can contain description of the package
along with technical keywords (which may be relevant), which are sometimes
directly mentioned in the name, but in other instances, are either absent or
present in abbreviated forms or as partial words.

The quantum of text (number of word / lines of text) does not necessarily
reflect the quality of the summary. Therefore, performing a broad
summarization on the complete list of entities might not be the best approach.
Although, it can be used to deduce some basic characteristics of the dataset.

Therefore, we decided on an approach, which could take these inconsistencies
into account and produce a viable score.

###  2.1 Introduction to the tools

The use of pre-existing tools has been done, so as not to re-invent the wheel.

The following techniques were used:

  * •

Statistical splitting of concatenated words – wordninja [2]: This package
probabilistically splits concatenated words using NLP based on English
Wikipedia unigram frequencies.

  * •

Lemmatization and Stopwords removal – NLTK [3]

  * •

Fuzzy matching – FuzzyWuzzy [4]: It uses Levenshtein Distance to calculate the
differences between sequences.

Figure 1: Incremental changes across consecutive attempts.

Similar techniques from other libraries can be used as a substitute for some
of the libraries used in this case.

Basic functionality (in the context of the use case) of each package is
explained below in brief.

Since the package names were mostly concatenated into a single string
(pytracks -> py + tracks, parsejson -> parse + json, etc), therefore they had
to be broken down into separate words. For this purpose, wordninja [2] was
quite useful.

Stop-Words (like “a”, “an”, “the”, etc) had be removed from the summary and
package names for 2 main reasons:

  * •

To improve loss in accuracy caused due to presence / absence of these in
either the package name or summary (i.e. presence in one and absence in
another or vice-versa).

  * •

To improve compute times while doing membership checks.

The WordNetLemmatizer stems the words to further improve matches (for
instance, “loving” which is a verb can be stemmed to “love”) by converting
words into their base form (Lemmatized versions).

FuzzyWuzzy [4] is used as the fuzzy matching library, which can return the
closest match to a string (and its score). This can be used to improve the
matching in case of partial / misspelled strings.

##  3 The Approach

Several attempts were made, with each attempt building on top of the previous
one. We will also go over the cons of each attempt (until the last one) to
grasp a better understanding of the changes that were introduced with each new
attempt.

###  3.1 1st Attempt (Baseline)

To establish a baseline, a vanilla membership check was performed (only
checking if a specific word from the package name occurs in the summary text).

The transformations applied at this stage were the removal of common words (in
our case there were 2 [“py”, “python”], which we determined by obtaining
summary statistics on the 2 columns - namely, package name and summary),
removal of stop words, lemmatization of the words in the summary and splitting
the concatenated package names using wordninja [2].

Figure 2: Baseline attempt pipeline.

This produced 362 entries marked with a score of 0 (out of 100), and 236
entries scoring 100. This meant there was a huge scope for improvement.
[Figure 3] shows a better summary, from the baseline attempt.

Figure 3: Scores from Baseline Attempt

####  3.1.1 Cons

The Baseline attempt had the following cons:

  * •

"wordninja" [2] library produced incorrectly split words in some instances,
which caused bad matches. This remained a constant, due to lack of a better
statistical string splitting tool.

  * •

In many cases acronyms were used in the package names, while their full forms
in the summary text.

###  3.2 2nd Attempt

Addition of a dynamic n-gram generating function improved the score in some
cases.

This addition reduced the number of zero scoring entries from 362 to 334 and
brought up the number of entries scoring a 100 from 236 to 251.

Figure 4: 2nd attempt pipeline.

These were not huge improvements, therefore there still was scope for
improvement. [Figure 5] shows a better summary, from the 2nd attempt.

Figure 5: Scores from 2nd Attempt

####  3.2.1 Cons

The 2nd attempt had the following cons:

  * •

Many words were not getting matched due to lemmatization inconsistencies (for
instance “logging” has a lemmatized version “log”).

  * •

Some words had spelling error(s), while others were partial words, which was
leading to elements not getting matched.

###  3.3 3rd Attempt

The 3rd attempt added a Lemmatization check and a Fuzzy matching check with a
threshold greater than 25% (anything below 25% would not be considered a good
fuzzy match, hence would not affect the final score).

Figure 6: 3rd attempt pipeline.

These changes introduced by far the most drastic delta in scores. The total
number of zero scoring entries got down to 50 (from 334) although there was
not a huge improvement in the number of 100 scoring entries, which increased
to 256 (from 251). [Figure 7] shows a better summary, from the 3rd attempt.

Figure 7: Scores from 3rd Attempt

###  3.4 Comparing the 3 Attempts

The bottom 50% scores (scores less than 50) accounted for almost 50% of the
entries, which got shaved down by more than half its original amount to about
21%.

Figure 8: Comparison of scores among the 3 attempts

To validate the scores, a manual review of package name-summary pairs was
performed. A set of 101 entries were manually scored. The labels used are
described below:

  * •

(0: Unknown -> Range: 0-25)

  * •

(1: Poor -> Range: 25-50)

  * •

(2: Good -> Range: 50-75)

  * •

(3: Perfect -> Range: 75-100)

The following rules were kept in mind while scoring

  * •

If the name of package occurs in the summary, a perfect or good score was
given.

  * •

A “0” was given only if the summary is either too generic, or not present.

  * •

If the package has a non-English vocabulary (but contains elements from the
package name) score it either perfect or good.

Each package name-summary pair was allotted 2 scores (one primary, one
secondary), if the predicted score is equal to the primary score, a validation
score of 1 was given, if it was equal to the secondary score, then 0.5, else,
0 (i.e. if the predicted score was different from both primary and secondary
scores).

Through the manual review, the 3rd attempt stood out, in comparison to the
baseline and 2nd attempt scores. [Figure 9] shows the validation scores across
the 3 attempts.

Figure 9: Comparison of validation scores among the 3 attempts

A large chunk of the scores improved in the 3rd attempt, this was partly due
to the addition of a Lemmatization check added to the package names (earlier
only summary words were getting lemmatized) but, can be majorly attributed to
fuzzy matching check, as it helped deal with cases of partial matches and
misspelled words.

##  4 Conclusion

The final attempt mentioned in this document seems to produce the most
accurate results. This approach can not only be used directly, but also to
supplement results generated from other approaches for a better final
classification (which is also a recommended way to use it).

All of this is considering the following factor(s):

  * •

The dataset had not much contributed to it in terms of pre-processing /
cleaning.

These were only a small proportion of the approaches that could be applied to
solve a problem like this. There is scope for improvement in these approaches,
some of which have been outlined in the next section.

##  5 Recommendations

  * •

Use better data pre-processing pipelines to improve accuracy of results
obtained.

  * •

"wordninja" [2] was trained on data from Wikipedia. The library has the
capability to integrate custom language models which could be more
contextually relevant. This in turn can be used to improve splitting accuracy
and therefore reduce matching complexity.

  * •

Algorithms to deduce data types, as well as intent (in case of input fields
and their definitions) can be used to supplement scores obtained from the
current approach.

  * •

Using tf-idf approach to find key words to focus on might further improve
accuracy.

## References

  * [1] PyPi, The Python Package Index (PyPI) is a repository of software for the Python programming language., 2000.  https://pypi.org/.
  * [2] Derek Anderson.  wordninja, Probabilistically split concatenated words using NLP based on English Wikipedia uni-gram frequencies., 2017.  https://github.com/keredson/wordninja.
  * [3] Edward Loper Bird, Steven and Ewan Klein.  NLTK, Natural Language Processing with Python. O’Reilly Media Inc., 2009\.  https://github.com/nltk/nltk.
  * [4] Adam Cohen.  fuzzywuzzy, Fuzzy string matching in python., 2011.  https://github.com/seatgeek/fuzzywuzzy.


* Rudin, (1962) Rudin, W. (1962).  Fourier analysis on groups, volume 121967.  Wiley Online Library.
  * Schaefer et al., (2003) Schaefer, A. T., Larkum, M. E., Sakmann, B., and Roth, A. (2003).  Coincidence detection in pyramidal neurons is tuned by their dendritic branching pattern.  Journal of neurophysiology, 89(6):3143–3154.
  * Schindler and Rahimi, (2021) Schindler, K. A. and Rahimi, A. (2021).  A primer on hyperdimensional computing for iEEG seizure detection.  Frontiers in Neurology, pages 1–12.
  * Schölkopf et al., (2002) Schölkopf, B., Smola, A. J., Bach, F., et al. (2002).  Learning with kernels: support vector machines, regularization, optimization, and beyond.  MIT press.
  * Shannon, (1949) Shannon, C. E. (1949).  Communication in the Presence of Noise.  Proceedings of the IRE, 37(1):10–21.
  * Smith and Stanford, (1990) Smith, D. and Stanford, P. (1990).  A random walk in Hamming space.  In International Joint Conference on Neural Networks (IJCNN), volume 2, pages 465–470.
  * Smolensky, (1990) Smolensky, P. (1990).  Tensor product variable binding and the representation of symbolic structures in connectionist systems.  Artificial Intelligence, 46(1-2):159–216.
  * Snaider and Franklin, (2014) Snaider, J. and Franklin, S. (2014).  Modular composite representation.  Cognitive Computation, 6:510–527.
  * Thomas et al., (2020) Thomas, A., Dasgupta, S., and Rosing, T. (2020).  Theoretical foundations of hyperdimensional computing.  arXiv:2010.07426, pages 1–32.
  * Van Rijsbergen, (2004) Van Rijsbergen, C. J. (2004).  The geometry of information retrieval.  Cambridge University Press.
  * Voelker, (2020) Voelker, A. R. (2020).  A short letter on the dot product between rotated fourier transforms.  arXiv:2007.13462, pages 1–4.
  * Voelker et al., (2021) Voelker, A. R., Blouw, P., Choo, X., Dumont, N. S.-Y., Stewart, T. C., and Eliasmith, C. (2021).  Simulating and predicting dynamical systems with spatial semantic pointers.  Neural Computation, 33(8):2033–2067.
  * Weiss et al., (2016) Weiss, E., Cheung, B., and Olshausen, B. A. (2016).  A neural architecture for representing and reasoning about spatial relationships.  In International Conference on Learning Representations (ICLR), pages 1–4.
  * Widdows, (2004) Widdows, D. (2004).  Geometry and meaning.  Stanford: CSLI publications.
  * Widdows and Cohen, (2015) Widdows, D. and Cohen, T. (2015).  Reasoning with vectors: A continuous model for fast robust inference.  Logic Journal of the IGPL, 23(2):141–173.
  * Ye and Entezari, (2011) Ye, W. and Entezari, A. (2011).  A geometric construction of multivariate sinc functions.  IEEE Transactions on Image Processing, 21(6):2969–2979.
  * Yerxa et al., (2018) Yerxa, T., Anderson, A., and Weiss, E. (2018).  The hyperdimensional stack machine.  In Cognitive Computing, pages 1–2.

Supplemental material

##  Appendix A Multi-dimensional Hadamard FPE

In Section 5.3 we describe how the binding operation can be used to construct
LPEs for multi-dimensional FPE from individual one-dimensional FPEs. Here we
describe and analyze in more detail the Hadamard FPE for multi-dimensional
data. The following interactions between inner product and Hadamard binding
simplify the notation:

$\displaystyle\left[\mathbf{x}\odot\mathbf{y}\right]^{\top}\overline{\mathbf{u}\odot\mathbf{v}}$
$\displaystyle=$
$\displaystyle\sum_{i}x_{i}y_{i}\overline{u_{i}}\overline{v_{i}}$ (61)
$\displaystyle\left[\odot_{j=1}^{m}\mathbf{x}^{j}\right]^{\top}\overline{\left[\odot_{j^{\prime}=1}^{m}\mathbf{y}^{j^{\prime}}\right]}$
$\displaystyle=$
$\displaystyle\sum_{i}\prod_{j=1}^{m}x^{j}_{i}\overline{y^{j}_{i}}$ (62)

In a Cartesian multi-dimensional Hadamard FPE, individual data dimensions are
encoded by one-dimensional FPEs and then combined via the binding operations:

$\displaystyle\mathbf{z}(\mathbf{x})$ $\displaystyle=$
$\displaystyle\odot_{j=1}^{m}\mathbf{z}^{j}(x_{j})$ (63)
$\displaystyle\mathbf{z}^{j}(x_{j})$ $\displaystyle=$
$\displaystyle(^{j}\mathbf{z})^{x_{j}}=(e^{\imath
x_{j}\phi^{j}_{1}},...,e^{\imath x_{j}\phi^{j}_{n}})$ (64)

with base vectors of the one-dimensional FPEs
${}^{j}\mathbf{z}=(e^{\imath\phi^{j}_{1}},...,e^{\imath\phi^{j}_{n}})$ chosen
independently for all $j$. The following theorem shows that this FPE induces a
VFA.

Theorem 3: Using Hadamard binding to construct a multi-dimensional LPE
encoding method from one-dimensional Hadamard FPEs (63) yields an inner
product kernel:

$\mathbf{z}(\mathbf{x})^{\top}\overline{\mathbf{z}(\mathbf{y})}=\sum_{i=1}^{n}e^{\imath\sum_{j=1}^{m}\phi^{j}_{i}(x_{j}-y_{j})}\to
K_{\odot}(\mathbf{x}-\mathbf{y}),$ (65)

which is translation invariant and positive definite. Thus, the multi-
dimensional Hadamard FPE induces a VFA, representing functions with multi-
dimensional domains, even if the dimension $n$ is not large enough so that the
inner product closely approximates the multi-dimensional sinc kernel.

Proof: Using (62) and (64), the inner product between representations of data
points can be written:

$\mathbf{z}(\mathbf{x})^{\top}\overline{\mathbf{z}(\mathbf{y})}=\sum_{i=1}^{n}\prod_{j=1}^{m}(^{j}z_{i})^{x_{j}}\;\overline{(^{j}z_{i})^{y_{j}}}=\sum_{i=1}^{n}\prod_{j=1}^{m}(^{j}z_{i})^{x_{j}-y_{j}}=\sum_{i=1}^{n}e^{\imath\sum_{j=1}^{m}\phi^{j}_{i}(x_{j}-y_{j})}$
(66)

An element of the Gram matrix between two data points $\mathbf{x}^{l}$ and
$\mathbf{x}^{l^{\prime}}$ can be transformed as follows:

$\displaystyle
M_{ll^{\prime}}=\mathbf{z}(\mathbf{x}^{l})^{\top}\overline{\mathbf{z}(\mathbf{x}^{l^{\prime}})}=\sum_{i=1}^{n}e^{\imath\sum_{j=1}^{m}\phi^{j}_{i}(x^{l}_{j}-x^{l^{\prime}}_{j})}=\sum_{i=1}^{n}\overline{e^{\imath\sum_{j=1}^{m}\phi^{j}_{i}(x^{l^{\prime}}_{j}-x^{l}_{j})}},=\overline{M_{l^{\prime}\;l}}$
(67)

which shows that the Gram matrix is Hermitian, an, thus, its eigenvalues are
real-valued. As for inner product kernels in general, the Gram matrix is
positive definite (Hofmann et al.,, 2008). Because of these conditions, the
multi-dimensional Hadamard LPE induces a function space.

$\Box$

In the resulting VFA, the vector representation of functions over the multi-
dimensional data space (43) is given by:

$\displaystyle(y_{f})_{i}$ $\displaystyle=$
$\displaystyle\sum_{k}\frac{\alpha_{k}}{n}z^{1}_{i}(r^{k}_{1})\;z^{2}_{i}(r^{k}_{2})\;...\;z^{m}_{i}(r^{k}_{m})=\sum_{k}\frac{\alpha_{k}}{n}e^{\imath\sum_{j=1}^{m}r^{k}_{j}\phi^{j}_{i}}$
(68)

and function evaluation at a point $\mathbf{s}$ is:

$f(\mathbf{s})=(\mathbf{y}_{f})^{\top}\overline{\mathbf{z}(\mathbf{s})}=\sum_{k}\frac{\alpha_{k}}{n}\sum_{i=1}^{n}\prod_{j=1}^{m}z^{j}_{i}(r^{k}_{j})\overline{z^{j}_{i}(s_{j})}=\sum_{k}\frac{\alpha_{k}}{n}\sum_{i=1}^{n}e^{\imath\sum_{j=1}^{m}(r^{k}_{j}-s_{j})\phi^{j}_{i}}.$
(69)

One might question that (63) is the best way to form a multi-dimensional FPE
from combining one-dimensional FPEs. As known from classical VSAs, Hadamard
binding provides a reduced, lossy representation of tensor product binding
(Frady et al.,, 2021). To avoid this loss, one could alternatively combine the
one-dimensional FPEs with Smolensky’s tensor product (Smolensky,, 1990). For
$m=2$ input dimensions, the representation tensor is the outer-product matrix:

$\mathbf{Z}(\mathbf{x})=\mathbf{z}^{1}(x_{1})\overline{\mathbf{z}^{2}(x_{2})}^{\top}=(^{1}\mathbf{z})^{x_{1}}\overline{(^{2}\mathbf{z})^{x_{2}}}^{\top}$
(70)

Here the Frobenius inner product of tensors (Hadamard product of the matrices
and addition of all matrix elements) converges to the exact Cartesian sinc
kernel:

$\mathbf{Z}(\mathbf{x})^{\top}\overline{\mathbf{Z}(\mathbf{y})}\to
K_{sinc}(x_{1}-y_{1})\times K_{sinc}(x_{2}-y_{2})$ (71)

This construction with the tensor product does indeed accelerate the
convergence to the ideal 2-D sinc kernel with increasing $n$, see Figure 5.
However, this improvement comes at the expense of requiring for the
representation of 2-D points a dimension of $n^{2}$, whereas with the Hadamard
product the representations of multi-dimensional points are always just $n$.
Figure 5D compares the two methods for 2-D points represented in a vector
space of the same dimension. This comparison shows that representations formed
by Hadamard product approximate the sinc kernel at nearly the same rate as the
tensor product.

##  Appendix B Other methods for generating hexagonal kernels

Komer and Eliasmith, (2020) propose an alternative construction of kernels
with hexagonal symmetry. They do so by projecting a 3-D Cartesian kernel to
form a 2-D hexagonal grid. The 3-D Cartesian grid uses three random unitary
vectors $z_{1},z_{2},z_{3}$. The coordinate in a 2-D space $\textbf{x}=(x,y)$
is then represented by the vector

$\mathbf{z}(\mathbf{x})=\mathbf{z}_{1}^{cc}(\mathbf{\xi}_{1}^{\top}\mathbf{x})\circledast\mathbf{z}_{2}^{cc}(\mathbf{\xi}_{2}^{\top}\mathbf{x})\circledast\mathbf{z}_{3}^{cc}(\mathbf{\xi}_{3}^{\top}\mathbf{x})$
(72)

where ${\xi_{1},\xi_{2},\xi_{3}}$ are the hexagonal basis vectors defined for
equation (45). Though Komer and Eliasmith, (2020) opt for unitary vectors with
binding via circular convolution, in principle other types of VFA could also
be used.

This 3-D system can be reconfigured to be a 2-D system by forming base phasor
vectors that do not have independently uniform phases. We can form the vectors
$\mathbf{z}_{x}=\mathbf{z}_{1}^{cc}(\mathbf{\xi}_{1}[0])\circledast\mathbf{z}_{2}^{cc}(\mathbf{\xi}_{2}[0])\circledast\mathbf{z}_{3}^{cc}(\mathbf{\xi}_{3}[0])$,
and
$\mathbf{z}_{y}=\mathbf{z}_{1}^{cc}(\mathbf{\xi}_{1}[1])\circledast\mathbf{z}_{2}^{cc}(\mathbf{\xi}_{2}[1])\circledast\mathbf{z}_{3}(\mathbf{\xi}_{3}^{cc}[1])$.
Now the coordinate $(r,s)$ is expressed naturally by

$\mathbf{z}(r,s)=\mathbf{z}_{x}^{cc}(r)\circledast\mathbf{z}_{y}^{cc}(s)$ (73)

Note that although this kernel exhibits hexagonal symmetry, it does not
converge to the hexagonal sinc function kernel. Thus, it is not equivalent to
(46), which does converge to the sinc function for large dimensionality.
Figure 14 shows some of the differences. In particular, while the power
spectrum is roughly uniform within the spectra of the hexagonal sinc function
kernel, for (72) the lower frequencies have higher power.

Figure 14:  Example of kernel generated using the method of Komer and
Eliasmith, (2020) and its respective power spectrum ($n=5,000$). (Power
spectrum is normalized such that total power equals 1.)

##  Appendix C Other types of LPE and their kernels

In order to process subsymbolic data in VSA, such as in machine learning
problems (Rachkovskij,, 2007; Räsänen and Saarinen,, 2016; Kleyko et al.,
2018a, ; Rahimi et al.,, 2019; Schindler and Rahimi,, 2021), previous work
combined VSAs with different kinds of LPEs for representing subsymbolic data
with vectors. Here we briefly review the LPE methods that have been used in
the past and assess whether or not they induce a VFA. The encoding methods use
either real (Section C.5) or binary/bipolar (elsewhere in this section) vector
spaces.

###  C.1 The thermometer code

Figure 15:  Similarity kernel of the thermometer code shown for several
levels; $n$ was set to $50$.

The thermometer code (Penz,, 1987; Rachkovskij et al.,, 2005; Buckman et al.,,
2018; Kleyko et al., 2020b, ) is a simple and structured way to form an LPE
for a range of discrete levels $s$, $s\in[0,n]$. The first code
$\mathbf{z}(0)$ consists of all -1s. For other levels the components of
$\mathbf{z}(s)$ are determined as:

$z_{i}(s)=\begin{cases}+1,&i\leq s\\\ -1,&\text{otherwise}\end{cases}$ (74)

Thus, the last code $\mathbf{z}(n)$ consists of all +1s. So in total the
thermometer code can represent $n+1$ levels. Figure 15 shows how the cosine
similarity looks like for several different levels when $n=50$. Thermometer
codes produce a translation-invariant kernel which is triangular and has a
width of $2n+1$ levels. It is thus a nonlocal kernel, that is, there are no
two points in the encoding range that have a similarity of zero. In practice,
thermometer codes are used commonly when applying VSAs to classification
problems.

###  C.2 The float code

Figure 16:  Similarity kernel of the float code shown for several levels; $n$
was set to $60$ while $w$ was set to $10$.

The float code, also known as the sliding code, (Goltsev,, 1996; Rachkovskij
et al.,, 2005) addresses the issue of the thermometer code, i.e., that the
similarity decay is not local. This is done by using $w$ consecutive +1
components (“float”) where the size of $w$ regulates similarity
characteristics of the code. For the binary case, the similarity kernel of the
float code is the triangular kernel of width $2w+1$ levels. To encode the
lowest value $\mathbf{z}(0)$, the first $w$ components of the vector are set
to +1s while the rest of the components are 0s. In general, the components of
$\mathbf{z}(s)$ are determined as:

$z_{i}(s)=\begin{cases}+1,&s\leq i<s+w\\\ 0,&\text{otherwise}\end{cases}$ (75)

Figure 16 depicts how similarity (inner product normalized by $w$) decays for
several levels in the float code for $n=60$, $w=10$. The float code also
produces a triangular kernel, but in contrast to the thermometer code, it
allows controlling the width of the triangular kernel. The number of levels it
could encode is still limited and equals to $n-w+1$. Thus, the float code
induces an RKHS which can represent functions composed from its triangular
kernel, but it cannot induce a VFA since there is no VSA binding operation
known that the float code would be compatible with (10).

###  C.3 Encoding by concatenation of parts of reference vectors

Figure 17:  Similarity kernel for the encoding by concatenation; $n$ was set
to $1000$. The values of similarities were averaged over $50$ random
initializations of the code.

When encoding by concatenation of parts of reference vectors (Rachkovskij et
al.,, 2005), we have to choose some “anchor” levels (e.g., integers in the
range $[0,100]$). These “anchor” levels are assigned with randomly chosen
vectors. Values $x$ between two “anchor” levels $s$ and $s+1$ ($s<x<s+1$) are
represented by concatenating the proportional amount from the corresponding
vectors $\mathbf{z}(s)$ and $\mathbf{z}(s+1)$:

$z_{i}(x)=\begin{cases}z_{i}(s+1),&i\leq\lfloor(x-s)n\rceil\\\
z_{i}(s),&\text{otherwise}\end{cases}$ (76)

Figure 17 shows how the cosine similarity looks for several different “anchor”
levels. As we can see, the similarity within two neighboring “anchor” levels
decays according to the triangular kernel. The advantage of the encoding by
concatenation is that the number of “anchor” levels can be very large even for
relatively small $n$ as “anchor” levels are represented by random vectors,
however, the disadvantage is that the similarity is only preserved between
nearby “anchor” levels. As for the float code, the concatenation method
induces the RKHS with trianglular kernels but it does not induce VFA due to
the absence of the proper binding operation to satisfy (10).

###  C.4 Scatter code

Figure 18:  Similarity kernel of a scatter code; $n$ was set to $1000$, $p$
was $0.05$. The values of similarities were averaged over $50$ random
initializations of the code.

Scatter codes (Smith and Stanford,, 1990; Rachkovskij et al.,, 2005; Kleyko et
al., 2018b, ) are another alternative to form an LPE where similarity decays
nonlinearly. In scatter codes, the code for the first level $\mathbf{z}(0)$ is
chosen randomly while each subsequent code is obtained from the previous one
by randomly swapping its components with some probability $p$:

$z_{i}(s)=\begin{cases}-z_{i}(s-1),&r_{i}\leq p\\\
z_{i}(s-1),&\text{otherwise}\end{cases}$ (77)

where $r_{i}$ is a random value for $i$th component of $\mathbf{z}(s)$ chosen
from the uniform distribution. Note that potentially there is no limitation on
how many levels can be created with the scatter codes.

Figure 18 shows how the cosine similarity looks for several different levels
formed with the scatter code. Interestingly, the kernels are ‘bell-shaped”
with the exact shape depending on the parameter settings. To better figure out
which standard kernel will correspond to this similarity, we have empirically
fitted three kernels: exponentiated triangular:

$K(s_{1},s_{2})=(1-\gamma|s_{2}-s_{1}|)^{\alpha};$ (78)

squared exponential:

$K(s_{1},s_{2})=e^{-\frac{(s_{2}-s_{1})^{2}}{2l^{2}}};$ (79)

and rational quadratic:

$K(s_{1},s_{2})=\left(1+\frac{(s_{2}-s_{1})^{2}}{2\alpha
l^{2}}\right)^{-\alpha};$ (80)

The parameters of the kernels were chosen using the mean squared error as the
fit criterion. Figure 18 shows that the scatter code can induce an RKHS with
kernels that are approximately exponentiated triangular but similar to all
previous LPEs there is no known VSA binding operation the scatter code would
be compatible with (10).

###  C.5 Random projection encoding

For a $d$-dimensional vector of real-valued input data $\mathbf{r}$, the
random projection (RP) encoding is given by:

$\mathbf{z}(\mathbf{r})=g(\mathbf{M}\mathbf{r})$ (81)

where $\mathbf{M}\in[n\times d]$ is a random matrix with its valued being
drawn from, e.g., normal distribution and $g(\mathbf{x})$ a point-wise
nonlinearity (e.g., $\mbox{sign}(\mathbf{x})$ can be used). Such a combination
of a linear RP, followed by a (often sparsifying) nonlinearity, have been
proposed in many different contexts, for example, to activate the locations in
an associative memory model (Kanerva,, 1988), for neuro-biology inspired
olfactory encoding (Dasgupta et al.,, 2017), and for LPE in VSAs (Rachkovskij
et al.,, 2012; Thomas et al.,, 2020). Note that without nonlinearity, the
inner product of the representations is the same as the inner product between
the data vectors:

$K(\mathbf{r}_{1},\mathbf{r}_{2})=(n/2)(|\mathbf{r}_{1}|_{2}^{2}+|\mathbf{r}_{2}|_{2}^{2}-|\mathbf{r}_{1}-\mathbf{r}_{2}|_{2}^{2}),$
(82)

where $|\mathbf{r}|_{2}^{2}$ is the squared L2 norm of vector $\mathbf{r}$.
For such encoding functions, which preserve the inner product, the resulting
kernel is not translation-invariant as it depends not only on the difference
vector but on the individual vectors’ norms. It is, however, possible to from
translation-invariant kernels with RP if proper point-wise nonlinearity is
used. As it was shown in (Rahimi and Recht,, 2007), the use of cosine function
and proper distribution of values of $\mathbf{M}$ will lead to distributed
representations corresponding forming inner product kernels:

$\mathbf{z}(\mathbf{r})=\cos(\mathbf{M}\mathbf{r}+\mathbf{b}),$ (83)

where values of $\mathbf{b}$ are chosen uniformly from $[-\pi,\pi]$ while
values of $\mathbf{M}$ are chosen from the Fourier transform of the desired
kernel in the same way as described in Section 5.2. However, we are not aware
of any VSA binding operation that would make RP compatible with (10).