# SHELBRS: Location Based Recommendation Services using Switchable Homomorphic
Encryption

Mishel Jain, Priyanka Singh, Balasubramanian Raman  Dhirubhai Ambani Institute
of Information And Communication Technology
Gandhinagar, Gujarat, India
Indian Institute of Technology, Roorkee, Utharakhand, India
Email:{201911052<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Location-Based Recommendation Services (LBRS) has seen an unprecedented rise
in its usage in recent years. LBRS facilitates a user by recommending services
based on his location and past preferences. However, leveraging such services
comes at a cost of compromising one’s sensitive information like their
shopping preferences, lodging places, food habits, recently visited places,
etc. to the third-party servers. Losing such information could be crucial and
threatens one’s privacy. Nowadays, the privacy-aware society seeks solutions
that can provide such services, with minimized risks. Recently, a few privacy-
preserving recommendation services have been proposed that exploit the fully
homomorphic encryption (FHE) properties to address the issue. Though, it
reduced privacy risks but suffered from heavy computational overheads that
ruled out their commercial applications. Here, we propose SHELBRS, a
lightweight LBRS that is based on switchable homomorphic encryption (SHE),
which will benefit the users as well as the service providers. A SHE exploits
both the additive as well as the multiplicative homomorphic properties but
with comparatively much lesser processing time as it’s FHE counterpart. We
evaluate the performance of our proposed scheme with the other state-of-the-
art approaches without compromising security.

##  I Introduction

Location-Based Recommendation Services (LBRS) grant users access to relevant
information about their surroundings based on their location and history. For
instance, a person searching for a coffee shop nearby his/her location. The
service providers would provide the best search results considering his/her
present location and previous history. However, availing of such services
risks the user’s privacy as the shared sensitive information could be misused
by these third-party servers to their advantage, causing serious losses to the
user [1]. This fact kind of delimits the privacy-aware society rushing to
leverage such services and creates an urgent need for privacy-preserving
recommendation services.

The real-time location information of the user is handled by location based
services(LBS). It also provides recommendation over encrypted history
preferences which ensures the user’s privacy. Lyu et al. proposed one such
state-of-the-art protocol. They adopt the Hilbert curve [2] as a mapping tool,
collaborative filtering recommender based on the co-occurrence matrix as a
recommendation technique [3] [4], and Brakerski-Gentry-Vaikuntanathan (BGV)
fully homomorphic encryption (FHE) as an encryption scheme [5]. However, it is
still infeasible for the use of commercial recommendation services due to the
high processing time.

In this paper, we propose SHELBRS, a lightweight LBRS that will benefit the
users as well as the service providers. Instead of FHE, we employ switchable
homomorphic encryption (SHE) that securely switches between partially
homomorphic encryption (PHE) schemes. Specifically, Paillier Homomorphic
Encryption and ElGamal Homomorphic Encryption for performing additions and
multiplications on the encrypted data. PHE evaluates arithmetic operations
more efficiently at least 2-3 order of magnitude compared to FHE. SHE supports
an arbitrary number of additions and multiplications over encrypted data and
serves the principle of FHE with better efficiency. The overall computation
and communication cost required in switching between the PHE’s is reasonable
for real-life applications. It overall reduces the processing time without
compromising the security.

The remainder of this paper is structured as follows: Section II discusses
some of the related works. Section III gives an overview of the Hilbert curve,
collaborative filtering based on Co-occurrence Matrix (CM), PHE, and the SHE
schemes. Section IV presents the LBRS using FHE [6] while Section V details
the proposed SHELBRS scheme. Section VI discusses the experimental results and
the security analysis of the proposed scheme. Section VII concludes the work
along with some future directions.

##  II Related work

Lattice-based FHE scheme introduced by Craig Gentry in 2009, is a milestone
research that opened doors for proposing possible solutions for encrypted
data. It was made possible as this scheme supported computation of arbitrary
functions and operations on the ciphertext, without the need of actually
decrypting it [7].

Many LBS were proposed in the literature to search nearest Point of Interests
(POI)’s to the user’s private location. In 2003, K-anonymous based technique
was introduced which adopts temporal and spatial cloaking [8]. It acquires
accuracy but requires a trusted third party to hide the user’s location.
Private Information Retrieval (PIR) [9], Private Circular Query Protocol
(PCQP) [10] and Lightweight Private Circular Query Protocol (LPCQP) [11] are
the LBS based on the cryptography methods. In PIR scheme, the user receives
POI from the server’s database based on Quadratic Residuosity Assumption (QRA)
without server’s knowledge of which POI a user is interested in. It provides
security but takes high execution time for searching POIs. PCQP proposed by
Lien et al. is an effective k-NN search algorithm based on paillier
cryptosystem and hilbert curve. It secretly shifts the POI-info circularly
which is stored on the server. LPCQP, proposed by Utsunomiya et al. is a
lightweight protocol that removes unnecessary POI information from the
requesting user to reduce computational cost. PIR, PCQP, and LPCQP secure
against single point failures and Denial of Service (DOS) attacks. In 2012,
Pingley et al. proposed a context-aware scheme for privacy-preserving LBS
[12]. It projects the user’s location on various-grid-length Hilbert curve and
uses location perturbation technique to prevent user’s privacy from the LBS
server. It ensures protection for data privacy. Gang et al. proposed location-
based social network (LBSN) towards privacy preservation for "check-in"
services in 2019 [13]. It designs the framework using k-anonymity based
algorithms without using a trusted third-party server. It guarantees secure
access and preserves user’s location privacy.

The detail of recommender systems and discussion about different
recommendation algorithms based on traditional and network approaches was
studied by Lu et al. in 2012. [14]. It compares the performance of different
recommendation algorithms. Badsha et al. introduced an Elgamal cryptosystem
based privacy-preserving item-based Collaborative Filtering (CF) in 2016 [15].
It provides recommendations based on the user’s average ratings and the
similarities between the items. Zhang et al. proposed Factorization
Machines(FM) based recommendation algorithm for Rural Tourism in 2018 [16]. It
provides recommendations based on geographical distribution and seasonal
features such as the user’s best suitable season for traveling, how many
kilometers is the traveling spot away from the city, and other user’s reviews
or comments for the particular location. In 2018, Horowitz et al. proposed a
mobile recommender system named "EventAware" for the events [17]. It provides
recommendations on the basis of both context-aware and tag-based algorithms.
In 2019, Qi et al. proposed a time-aware and privacy-preserving distributed
recommendation service based on a locality-sensitive hashing (LSH) to provide
most accurate recommended results [18]. Papakyriakopoulos et al. analyzed the
political networks based on hybrid collaborative filtering and deep learning
recommender algorithms in 2020 [19]. It shows how hyperactive users influence
recommendations. It also compares the results based on likes and comments with
and without the inclusion of the hyperactive users along with the rest of the
users in the datasets.

Combining both location privacy and privacy-preserving recommendations, Lyu et
al. proposed privacy-preserving recommendations for LBS in 2019. It provides
suggestions over encrypted previous histories considering user’s live location
data. This protocol uses one trusted third party server where sensitive data
such as crypto keys are stored and one honest but curious server where all the
computations are performed.

##  III Preliminaries

###  III-A Hilbert Curve

Hilbert curve is a mapping tool that is used to transform 2-D space into 1-D
space. It preserves the adjacency of the neighboring points and has best
clustering properties. In order to preserve the adjacency property, the
orientation is not retained [2] [4]. As we increase the order of a pseudo-
Hilbert curve, a given point on the line converges to a specific point. The
two data points which are close to each other in 2-D space are also close to
each other after mapping into 1-D space.

Figure 1: The combination of Continuous Hilbert space-filling curve and
Location-based services

Fig. 1 shows a Hilbert curve over the landscape, storing the POI look-up table
at the user end and the POI information table at the server end. The user $p3$
is located on cell 7 and he/she is requesting POIs from the server. At the
user’s side, p3 is located at Index-3 and after sending index information to
the server, the server sends nearby POIs i.e. p2, p3, p4 corresponding to the
current index back to the user. This is how the nearest POIs to the user’s
location is suggested when the landscape is mapped on the Hilbert curve.
However, sending such information in plaintext does not ensure the user’s
privacy.

###  III-B Collaborative filtering (CF) Recommender based on Co-occurrence
Matrix (CM)

CF Recommender consists of two well-known algorithms: user-based CF and item-
based CF. We used an item-based CF recommender as similarities between items
are more stable than that of users. It finds the similarity between items and
provides the best recommendation. Some E-commerce websites such as Amazon
provides recommendation such as "A person bought product A also bought product
B" or "A person liked the cafe A also liked cafe B".

CM contains the visited POIs information. It computes the number of times each
pair of items occurs together in the user-item inversion list. To generate CM,
the first step is to generate a user-item inversion list and the second step
is to traverse the list and follow the algorithm as described:

  * •

$CM[i][j](i!=j)$ is increased by 1 if item $i$ and the item $j$ are in the
same user’s inversion list.

  * •

$CM[i][j](i==j)$ is increased by $1$ for every item $i$.

Figure 2: Formation of the final CM [6]

Fig. 2 shows the formation of CM based on the user-item inversion list.
According to the user-item inversion list, $User_{1}$ has the preference for
indices $2$, $3$, $5$, $6$. The value at all possible pairs of indices in $CM$
such as $CM[2][3]$, $CM[2][5]$, $CM[2][6]$, $CM[3][2]$, $CM[3][5]$,
$CM[3][6]$, $CM[5][2]$, $CM[5][3]$, $CM[5][6]$, $CM[6][2]$, $CM[6][3]$,
$CM[6][5]$ is incremented by $1$. Every time an item occurs in the list, the
value in $CM$ such as $CM[2][2]$, $CM[3][3]$, $CM[5][5]$, and $CM[6][6]$ is
incremented by $1$. Likewise for all the users, the above algorithm is
performed to get the final $CM$.

###  III-C Partially homomorphic Encryption (PHE)

PHE schemes are a kind of encryption schemes that allow only certain types of
operations on the encrypted data. If we decrypt the processed encrypted data,
the results would be the same as if calculated over the corresponding
plaintext values. Based on the type of operations supported, it can be
categorized as additive PHE or multiplicative PHE. For instance, Paillier is
an example of additive PHE and ElGamal, an example of multiplicative PHE. We
will briefly describe each of them along with their homomorphic properties.

Paillier Encryption as additive PHE :

  * •

KeyGen($1^{n},+$): On input a security parameter $1^{n}$, the algorithm
chooses $(N,p,q)$ where $N=p*q$, $p$ and $q$ are $n$ bit primes, and
$\phi(N)=(p-1)*(q-1)$. The Paillier ADD scheme public-private key pair:

$\left\langle pk^{+},sk^{+}\right\rangle=\left\langle
N,(N,\phi(N))\right\rangle$ (1)

  * •

Enc($pk^{+},m$): The algorithm takes a plaintext $m$ and a public key $N$ as
input. It chooses a random $r$ $\in\,\,Z_{N}^{*}$ and outputs the ciphertext:

$c^{+}=(1+N)^{m}.(r)^{N}\mod N^{2}$ (2)

  * •

Dec($sk^{+},c^{+}$): The algorithm takes a ciphertext $c^{+}$ and a private
key $(N,\phi(N))$ as input and outputs the message:

$m=\dfrac{((c^{+})^{\phi(N)}\mod N^{2})-1}{N}.\phi(N)^{-1}\mod N$ (3)

  * •

Paillier homomorphic properties:

    1. 1.

Addition: The product of two encrypted ciphertexts results in the sum or
addition of their corresponding plaintexts:

$\footnotesize Dec(E^{+}(m_{1})*E^{+}(m_{2})\mod N^{2})=(m_{1}+m_{2})\mod N$
(4)

    2. 2.

Scalar Multiplication: Raising a scalar to the power of encrypted ciphertext
results in the product of the scalar and the corresponding plaintext:

$Dec(E^{+}(m_{1})^{k})\mod N^{2})=(k*m_{1})\mod N$ (5)

ElGamal Encryption as multiplicative PHE:

  * •

KeyGen($1^{n},*$): On input a security parameter $1^{n}$, the algorithm
chooses $(N,p,q)$ where $N=p*q$, $p$ and $q$ are $n$ bit primes, considers $g$
as square value and sets $g=16$. It also chooses a random odd number $x$, and
sets $h=g^{x}\mod N$. The ElGamal MUL scheme public-private key pair:

$\left\langle
pk^{*},sk^{*}\right\rangle=\left\langle(N,g,h),(N,g,x)\right\rangle$ (6)

  * •

Enc($pk^{*},m$): The algorithm takes a plaintext $m$ and a public key
$(N,g,h)$ as input. It chooses a random $r$ $\in\,\,Z_{N}^{*}$ and outputs the
ciphertext:

$c^{*}=\left\langle c_{1}^{*},c_{2}^{*}\right\rangle=\left\langle
mh^{r},g^{r}\mod N\right\rangle$ (7)

  * •

Dec($sk^{*},c^{*}$): The algorithm takes a ciphertext $c^{*}$ and a private
key $(N,g,x)$ as input and outputs the message:

$m=\dfrac{c_{1}^{*}}{(c_{2}^{*})^{x}}\mod N$ (8)

  * •

ElGamal homomorphic properties:

    1. 1.

Multiplication: The product of two encrypted ciphertexts results in the
multiplication of their corresponding plaintexts:

$\footnotesize Dec(E^{*}(m_{1})*E^{*}(m_{2})\mod N^{2})=(m_{1}*m_{2})\mod N$
(9)

###  III-D Switchable homomorphic Encryption (SHE)

We work with a variant of ElGamal MUL scheme $E^{*}$ and Paillier ADD scheme
$E^{+}$. ElGamal MUL scheme uses a large composite modulus i.e., $N=p*q$,
where $p$ and $q$ are large primes. Both the partially homomorphic schemes
share the same modulus. We consider two servers, say a server and a proxy.

The algorithms used in the SHE scheme are described as follows:

  * •

KeyGen($1^{n}$): On input a security parameter $1^{n}$, the algorithm outputs
$(N,p,q)$, where $N=p*q$, $p$ and $q$ are $n$ bit primes, and
$\phi(N)=(p-1)(q-1)$. The Paillier ADD scheme public-private key pair:

$\left\langle pk^{+},sk^{+}\right\rangle=\left\langle
N,(N,\phi(N),p,q)\right\rangle$ (10)

It also chooses the generator $g=16$, two random odd numbers
$x_{0},x_{1}\in\,\,Z_{N}^{*}$ where
$\left|x_{0}\right|\approx\left|x_{1}\right|<1/2\left|N\right|$. It sets
$x=x_{0}x_{1}$ and $h=g^{x}$. The ElGamal MUL scheme public-private key pair:

$\left\langle
pk^{*},sk^{*}\right\rangle=\left\langle(N,g,h),(N,g,x_{0},x_{1})\right\rangle$
(11)

  * •

Enc($pk^{o}$, $m$): The algorithm runs $E^{+}$ encryption scheme if o is ’+’
else runs $E^{*}$ encryption scheme.

  * •

Dec($sk^{o},c^{o}$): The algorithm runs $E^{+}$ decryption scheme if o is ’+’
else runs $E^{*}$ decryption scheme.

  * •

KeyShaGen($sk^{+}$): The algorithm sets both the secret key shares $k_{0}^{+}$
(proxy) and $k_{1}^{+}$ (server) to NULL.

  * •

KeyShaGen($sk^{*}$): The algorithm sets both the secret key shares $k_{0}^{*}$
(proxy) and $k_{1}^{*}$ (server) to $x_{0}$ and $x_{1}$ respectively.

  * •

AddToMul($c^{+},pk^{*}$): The algorithm is run locally by the server. Given an
ADD ciphertext of the form:

$E^{+}(m)=(1+N)^{m}.(r^{\prime})^{N}\mod N^{2}$ (12)

and the MUL public key $pk^{*}=(N,g,h)$, the algorithm chooses a random $r$
$\in\,\,Z_{N}^{*}$ and outputs the encrypted MUL ciphertext:

$E^{+}(E^{*}(m))=\left\langle(1+N)^{mh^{r}}.(r^{\prime})^{Nh^{r}}\mod
N^{2},g^{r}\right\rangle$ (13)

  * •

MulToAdd($c^{+},k_{0}^{*},k_{1}^{*}$): The algorithm is jointly run by a
server and a proxy. On input an encrypted MUL ciphertext of the form (13) the
server chooses a random $s$ $\in\,\,Z_{N}^{*}$, computes

$c^{\prime}=(g^{r+s})^{k_{1}^{*}},R=g^{s}$ (14)

and forwards (13) and (14) to the proxy.

The proxy then using its key shares $k_{0}^{*}$, computes
$(c^{\prime})^{k_{0}^{*}}=h^{r+s}$ and finds its inverse $(h^{r+s})^{-1}$. It
also computes and returns

$\displaystyle c^{\prime\prime}$
$\displaystyle=((1+N)^{m{h^{r}}}.(r^{\prime})^{N{h^{r}}})^{{h^{r+s}}^{-1}}\mod
N^{2}$ $\displaystyle=(1+N)^{m{h^{-s}}}.(r^{\prime})^{N{h^{-s}}}\mod N^{2}$
(15) $\displaystyle=E^{+}(mh^{-s})$

and $R^{\prime}:=R^{k_{0}^{*}}$ to the server.

Finally, the server computes $(R^{\prime})^{k_{1}^{*}}=h^{s}$ and recovers the
corresponding ADD ciphertext $E^{+}(m)$ by homomorphically removing $h^{-s}$
from $c^{\prime\prime}$.

##  IV Lyu et al.’s Protocol

In this section, we give an overview of Lyu et al. protocol which was meant to
recommend services based on the current location of a user and his past
behavior without compromising his privacy [6]. It solved the problems existing
in the state-of-the-art privacy-preserving algorithms that were based on k-NN
technique for searching POI’s [10]. The major bottleneck was that the
recommendation service didn’t consider the user’s past behavior while
recommending any services that ultimately resulted in failing to attract the
user’s usage of the recommendation system. Another major demerit was it lacked
any benefits for the service providers facilitating such services as the
private keys were available only to the user and hence, the service providers
could not extract any information from the user’s data towards making their
profits.

Lyu et al. resolved the aforementioned issues using collaborative filtering
technique that works on top of database encrypted using FHE, besides
encrypting the user’s location and preferences. Also, it allowed the service
providers to extract some aggregate information based on the user’s data via
an introduction of a Privacy Service Provider (PSP) that generates and holds
the private keys. This increased the commercial value of the recommendation
service but still the need of heavy computational resources required for FHE
restricts the usage.

Figure 3: An overview of Lyu et al.’s protocol

###  IV-A System Model

An overview of the protocol is shown in Fig. 3. It involves three main
components:

  * •

Privacy-Preserving Recommendation Server (PPRS): PPRS is a semi-trusted i.e
honest but curious entity that is responsible for finding the nearest POIs to
the user, by considering the similarity between the POIs near the user and his
current location. It performs two main tasks: The first task is to calculate
the recommendation list based on preference vector $PV$ and co-occurrence
matrix $CM$. Here, $PV$ provides a rating of a user for a particular item and
$CM$ describes the similarities between the items. The second task is to
calculate the aggregated user behavior over the encrypted database ($ED$).

  * •

Privacy Service Provider (PSP): PSP is a trusted third party which makes a
profit from user’s behavior statistics. It holds and generates the private and
public key pairs. It is responsible for providing public keys to users, ED and
PPRS whenever the requests arrive. It generates partial recommendation list
based on user’s location information.

  * •

Encrypted Database (ED): It stores $CM$ encrypted by FHE.

###  IV-B Description of Lyu et al.’s Protocol

This section describes Lyu et al.’s protocol. First, we describe briefly the
three main phases of the protocol and then go for a detailed step-by-step
description. The three main phases are as follows:

Initialization Phase: Personal co-occurrence matrix ($CM_{u}$), which contains
the information of visited POIs, is generated by the user on the basis of
his/her preferences. Each user sends his/her encrypted $CM_{u}$ to the PPRS.
PPRS constructs the final $CM$ by combining these $CM_{u}^{\prime}s$. The
operation performed here is exploiting the homomorphic addition property of
FHE operation. This combined matrix $CM$ is stored in the $ED$.

Recommendation Phase: For computing full recommendation list for the user,
each item’s prediction value is computed by performing homomorphic addition
and multiplication property of FHE. Prediction value is derived as

$P_{u.i}=\sum_{j\in N(u)}(w_{ij}*r_{uj})$ (16)

where,

$N(u)$ denotes all the items, $w_{ij}$ is the similarity between item $i$ and
$j$, and $r_{uj}$ is the rating of user u for item j.

ED Updation Phase: ED stores the $CM$ and it needs to be updated according to
the user’s new behaviors. The updation occurs as follows:

  * •

After receiving recommendation results from PSP in plain text, the target user
selects any POI of his/her choice.

  * •

He/She then sends the encrypted results to the ED for further updated
recommendation.

  * •

Instead of sending the whole $CM$, each user sends only the difference from
its original $CM$ to update the matrix with the latest information. It
protects the privacy of the user from PPRS by sending the matrix in an
encrypted FHE domain.

The detailed step-by-step description of the Lyu et al.’s protocol is as
follows:

Step 1: Initially, the public key ($p_{k}$) is distributed by the PSP to a
user and PPRS. The target user sends her/his encrypted location to PSP.
Step 2: The target user also sends encrypted preference vector to PPRS at the
same time.
Step 3: PPRS generates and sends the encrypted full recommendation list to
PSP.
Step 4: After PSP decrypts both the target user’s location and the full
recommendation list, it scans the whole list and generates the partial
recommendation list according to the user’s location information. It ensures
user’s privacy by sending it through an encrypted channel to the target user.
Step 5: The target user selects the POI from the partial recommendation list.
Step 6: She/he sends the encrypted result to the PPRS.
Step 7: PPRS then updates the ED for providing the best recommendation.

##  V Proposed SHELBRS Protocol

In our proposed framework, we replace the FHE component with SHE to minimize
the overall computational complexity and also, speed up the entire process so
that it could be better suited for real-life scenarios. The security of the
proposed protocol is kept at par with the corresponding FHE based protocol.
Our protocol does not make use of any trusted third party server to store
crypto keys. It simply sends the secret key shares between the servers so that
an individual server cannot leak any user’s sensitive information.

Figure 4: Secure computation via two servers

The details of each stage of SHELBRS protocol is discussed as follows:

###  V-A Setup Stage

The setup of SHELBRS is based on a client-server architecture. We consider two
servers, say server $X$ and server $Y$, and the interaction between the
servers or a server and a client is shown in Fig. 4. Security holds as long as
atleast one of the servers is honest i.e. they do not collude by sharing
cryptographic keys. Let us assume that the landscape $I$ is mapped on a
Hilbert curve and divided into indices $I_{1},I_{2},\ldots I_{n}$. Based on a
client-server model, a client is located on one of the indices and has its own
preference vector. The encrypted database of $CM$ is already stored at server
$Y$. A client generates a public-private key pairs using (10) (11) and sends
public keys $pk^{+}$ and $pk^{*}$ to both the servers. Clients uses
KeyShaGen($sk^{*}$) and KeyShaGen($sk^{+}$) algorithms as described in Section
III-D and sends $k_{0}^{*}$ and $k_{0}^{+}$ to server X and $k_{1}^{*}$ and
$k_{1}^{+}$ to server $Y$. The POIs nearby user’s location is recommended by
the computations which are being performed on the servers.

###  V-B Initialization Stage

This stage describes the steps which needs to be computed before the client
starts executing his/her role.

Figure 5: SHELBRS: Proposed Recommendation

  * •

Personal co-occurrence matrix ($CM_{u}$) contains the information of visited
POIs. During the initialization stage, each user generates his/her personal
$CM_{u}$ based on initial users’ preference.

  * •

An user $u$ sends $CM_{u}$, which is encrypted by the public key $pk^{+}$, to
the server $Y$.

  * •

The end task is to merge all $CM_{u}$ to generate the final $CM$. This
requires paillier homomorphic Addition property as described in (4) and
AddToMul algorithm as discussed in Section III-D.

  * •

The encrypted CM is stored at server Y.

Algorithm 1 Recommendation

1:$CM^{*}$, $PV^{*}$, Item Index set $I^{*}$

2:Recommendation list $RL$ for all items

3:

  1. 1.

$CM^{*}$ is ElGamal encrypted co_occurrence matrix

  2. 2.

$PV^{*}$ is ElGamal encrypted history preference vector

  3. 3.

RL[i] is item $i^{\prime}s$ recommendation score

4:procedure recommend($CM^{*}$ , $PV^{*}$ , $I^{*}$, size)

5: Assign $RL^{+}[1\cdots size]=0$

6: for $i=1;$ i <= size; $i=i+1$ do

7: for $j=1;\ j<=size;\ j=j+1$ do $\displaystyle ctotal$
$\displaystyle=\textbf{elGamalMultiplication}(CM[i][j]^{*},PV[j]^{*})$
$\displaystyle c1$ $\displaystyle=\textbf{pallierEncryption}(pkadd,ctotal[0])$
$\displaystyle temp$
$\displaystyle=\textbf{MulToAdd}([c1,ctotal[1]],k_{1}^{*},k_{0}^{*})$
$\displaystyle RL[i]^{+}$
$\displaystyle=\textbf{paillierAddition}(RL[i]^{+},temp)$

8: end for

9: end for

10: return $RL^{+}$

11:end procedure

###  V-C Protocol Operation stage

The detailed process of how the recommendation is being generated is shown in
Fig. 5. The client and the servers interact in the following manner:

Step 1: The client encrypts history preference vector $PV$ using
$Enc(pk^{*},PV)$ and location info using $Enc(pk^{*},Location\\_info)$ and
sends it to server $Y$.

Step 2: The client computes each item’s prediction value $P$ using (16) to
generate a recommendation list. The prediction is generated using Algorithm 1.

To calculate each index’s recommendation score, ElGamal encrypted $CM^{*}$ and
$PV^{*}$ are elementwise multiplied using the multiplicative property of
ElGamal Encryption. The corresponding result is transformed into encrypted
ElGamal ciphertext using Paillier Encryption scheme in Section III-C.

Step 3: It is further converted into paillier encrypted ciphertext using
MulToAdd algorithm in Section III-D. The corresponding result is finally added
using additive property of Paillier Encryption to generate the corresponding
recommendation score.

Likewise, the above steps 2 and 3 are executed for each index to generate the
final recommendation list.

Step 4: According to the target user’s location, the final recommendation list
is filtered out.

The server $Y$ performs paillier homomorphic subtraction property
corresponding to the indices stored in the recommendation list and user’s
location. It appends the result to the recommendation list and the updated
list is sent to the client.

Step 5: The client then decrypts it using paillier decryption algorithm and
filters out the records corresponding to the value ‘0’. The client chooses one
of the locations(indices) from the recommendation list according to his/her
choice and update his/her behavior in the inversion list. Each client sends
only his/her new paillier encrypted $CM_{u}$ to server Y which is the
difference between the current $CM_{u}$ and the client’s original $CM_{u}$
before the recommendations.

##  VI Experimental Results

To validate the proposed protocol based on SHE, the experiment is executed on
Ubuntu 20.04.2 LTS powered by Intel® Core™ i5-6200U CPU @ 2.30GHz × 4
processor and RAM 8 GB. We have considered a client and two servers on the
same machine. In this experiment, we considered the artificial dataset with
POIs in range {10, 20, 40, 80, 100, 1000, 2000, 3000, 4000, 5000}.

The $CM$ is already stored on the server $Y$ and then, the client starts
executing his/her behavior. So, the execution time taken for the computations
during initialization phase to generate $CM$ is not considered in the total
computation cost taken by the client. The time taken to generate public-
private keypair is constant. The updation of $ED$ can be performed even when a
user is offline, so it does not affect the efficiency of the system.

Total Elements |  Encryption Time[s] |  Recommendation Time[s] |  Decryption Time[s]
---|---|---|---
10 |  0.001 |  0.022 |  0.001
20 |  0.001 |  0.081 |  0.001
40 |  0.001 |  0.299 |  0.002
80 |  0.003 |  1.142 |  0.004
100 |  0.004 |  1.923 |  0.006
1000 |  0.04 |  197.99 |  0.058
2000 |  0.066 |  732.107 |  0.104
3000 |  0.138 |  1668.944 |  0.157
4000 |  0.164 |  2888.376 |  0.232
5000 |  0.17 |  4355.451 |  0.3
Table I: Computation Cost

The total computation cost involves encryption of a client’s preference
vector, computation of recommendation list and decryption of recommendation
list. In Table I, we measured encryption time, recommendation time,and
decryption time for the indices in an encrypted domain. We have run the
experiment five times for each index and taken an average of it.

The experiment uses encryption which adds extra computation cost over
plaintext. So, we calculated and compared the total computation cost for the
plaintext and encrypted domain up to 1000 indices as shown in Table II.

Total Elements |  Plaintext Domain |  Encrypted Domain
---|---|---
10 |  0.001 |  0.024
20 |  0.001 |  0.083
40 |  0.002 |  0.302
80 |  0.005 |  1.149
100 |  0.007 |  1.933
1000 |  1.32 |  198.088
Table II: Comparison of total execution time in plaintext domain and encrypted
domain

We also plotted the graph comparing the total execution time taken by SHELBRS
scheme and Lyu et al. protocol in Table III.

Total Elements |  Proposed SHELBRS Scheme |  Lyu et al. [6]
---|---|---
10 |  0.024 |  2.79
20 |  0.083 |  5.48
40 |  0.302 |  11.13
80 |  1.149 |  22.32
100 |  1.933 |  28.03
1000 |  198.088 |  269.47
Table III: Comparison of total execution time taken by proposed SHELBRS scheme
and Lyu et al. [6] Figure 6: Comparison of total execution time taken by
proposed SHELBRS scheme and Lyu et al. [6]

###  VI-A Security Analysis

Our protocol aims to provide data confidentiality. It does not leak any
meaningful information throughout the protocol. The security of the scheme is
based on the following assumptions:

  * •

The ElGamal and Paillier schemes are secure.

  * •

At least one of the servers is honest i.e. if one of the servers is malicious,
the other server remains honest.

  * •

None of the servers collude.

Let us assume an Adversary $A$ plays the role of either a malicious server $Y$
or a malicious server $X$. Initially, $A$ is given the public keys and private
key shares to perform paillier encryption $E^{+}$, elGamal encryption $E^{*}$,
AddToMul and MulToAdd algorithms. $A$ is also given access to choose any
arbitrary plaintext and can perform encryption to get the corresponding
ciphertext. A user sends $E^{*}(m_{0})$ to the server $Y$ where $m_{0}$ is an
integer except a value $0$. Now, A’s goal is to find a challenge
$m^{\prime}_{0}$ such that $m^{\prime}_{0}=m_{0}$. If A’s goal is achieved,
the security is broken. To prove $m_{0}^{\prime}s$ security, given below are
some lemmas.

Lemma1: If Server $Y$ is a malicious server and $A$ chooses to attack AddToMul
algorithm, it has access to $E^{*}(m_{0})$, $E^{+}(m_{0})$ and
$E^{+}(E^{*}(m_{0}))$. Paillier encrypted $E^{+}(m_{0})$ and
$E^{+}(E^{*}(m_{0}))$ terms are semantically secure and no decryption key
$sk^{+}$ is associated with any server, so, no information regarding $m_{0}$
is leaked through these terms. Server $Y$ has key share $k_{1}^{*}=x_{1}$ and
$E^{*}(m_{0})$ = $(m_{0}h^{r},g^{r})$ where $r$ is randomly chosen from the
group $Z_{N}^{*}$. The security of $E^{*}(m_{0})$ is based on SHE security
proof[20] is perfectly secure. So, $A$ cannot learn anything about $m_{0}$ in
the protocol.

Lemma2: If Server $Y$ is a malicious server and $A$ chooses to attack MulToAdd
algorithm, it has access to $k_{1}^{*}=x_{1}$. $E^{*}(m_{0})$,
$E^{+}(E^{*}(m_{0}))$, $R^{\prime}=g^{sx_{0}}$ and $c"=E^{+}(m_{0}h^{-s})$.
$E^{*}(m_{0})$, $E^{+}(E^{*}(m_{0}))$ and $c"$ are secure according to lemma1.
$A$ cannot learn about secret key share $x_{0}$ from $R^{\prime}$ as $s$ is
randomly chosen from the group $Z_{N}^{*}$. Therefore, the proposed scheme is
secure against the malicious activity performed by server $Y$ itself.

Likewise, we can prove the data confidentiality using lemma1 and lemma2 when
Server $X$ acts as an adversary $A$.

Now, we will handle the case when the client performs elGamal encryption on a
message $m_{0}$ where $m_{0}=0$. The ElGamal Encryption of $m_{0}$ plaintext
results into one of the ciphertexts as "zero". This is not secure as it leaks
information regarding plaintext data. To handle such problems, we can
represent "zero" in the form

$\footnotesize\textbf{MulToAdd}(E^{+}(E^{*}(n_{1})))*\textbf{MulToAdd}(E^{+}(E^{*}(n_{1})))^{-1}=E^{+}(0)$
(17)

##  VII Conclusions and Future Work

A lightweight privacy-preserving recommendation protocol for LBS was proposed
in this paper. It incorporated Hilbert curve, collaborative filtering
recommender based on co-occurrence matrix and SHE to recommend the services.
Based on the simulation and experiments, we found that the computation cost
for $5000$ POIs is $4355.921$ seconds. Compared with the state-of-the-art
protocol, the proposed protocol takes less computation time and reduces
complexity, providing at par security. As the future direction of the work, we
would like to extend our protocol for the larger geographical area as we
focused herein only on item-based filtering on a single geographical area.

## References

  * [1] Mark Ingle Rhys Fenwick, Mike Hittle and Oliver White.  Fitness app strava lights up staff at military bases. https://www.bbc.com/news/technology-42853072.  BBC Journal Archive, 2018.
  * [2] Hans Sagan.  Space-filling curves.  Springer Science & Business Media, 2012.
  * [3] Badrul Sarwar, George Karypis, Joseph Konstan, and John Riedl.  Item-based collaborative filtering recommendation algorithms.  In Proceedings of the 10th international conference on World Wide Web, pages 285–295, 2001.
  * [4] Bongki Moon, Hosagrahar V Jagadish, Christos Faloutsos, and Joel H. Saltz.  Analysis of the clustering properties of the hilbert space-filling curve.  IEEE Transactions on knowledge and data engineering, 13(1):124–141, 2001.
  * [5] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.  (leveled) fully homomorphic encryption without bootstrapping.  ACM Transactions on Computation Theory (TOCT), 6(3):1–36, 2014\.
  * [6] Qiuyi Lyu, Yu Ishimaki, and Hayato Yamana.  Privacy-preserving recommendation for location-based services.  In 2019 IEEE 4th International Conference on Big Data Analytics (ICBDA), pages 98–105. IEEE, 2019.
  * [7] Craig Gentry.  Fully homomorphic encryption using ideal lattices.  In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 169–178, 2009.
  * [8] Marco Gruteser and Dirk Grunwald.  Anonymous usage of location-based services through spatial and temporal cloaking.  In Proceedings of the 1st international conference on Mobile systems, applications and services, pages 31–42, 2003.
  * [9] Carlos Aguilar Melchor and Philippe Gaborit.  A fast private information retrieval protocol.  In 2008 IEEE International Symposium on Information Theory, pages 1848–1852. IEEE, 2008.
  * [10] I-Ting Lien, Yu-Hsun Lin, Jyh-Ren Shieh, and Ja-Ling Wu.  A novel privacy preserving location-based service protocol with secret circular shift for k-nn search.  IEEE Transactions on Information Forensics and Security, 8(6):863–873, 2013.
  * [11] Yasuhito Utsunomiya, Kentaroh Toyoda, and Iwao Sasase.  Lpcqp: Lightweight private circular query protocol for privacy-preserving k-nn search.  In 2015 12th Annual IEEE Consumer Communications and Networking Conference (CCNC), pages 59–64. IEEE, 2015.
  * [12] Aniket Pingley, Wei Yu, Nan Zhang, Xinwen Fu, and Wei Zhao.  A context-aware scheme for privacy-preserving location-based services.  Computer Networks, 56(11):2551–2568, 2012.
  * [13] Gang Sun, Liangjun Song, Dan Liao, Hongfang Yu, and Victor Chang.  Towards privacy preservation for “check-in” services in location-based social networks.  Information Sciences, 481:616–634, 2019.
  * [14] Linyuan Lü, Matúš Medo, Chi Ho Yeung, Yi-Cheng Zhang, Zi-Ke Zhang, and Tao Zhou.  Recommender systems.  Physics reports, 519(1):1–49, 2012.
  * [15] Shahriar Badsha, Xun Yi, and Ibrahim Khalil.  A practical privacy-preserving recommender system.  Data Science and Engineering, 1(3):161–177, 2016.
  * [16] Xiaojian Zhang, Limin Yu, Minjuan Wang, and Wanlin Gao.  Fm-based: Algorithm research on rural tourism recommendation combining seasonal and distribution features.  Pattern Recognition Letters, 2018.
  * [17] Daniel Horowitz, David Contreras, and Maria Salamó.  Eventaware: A mobile recommender system for events.  Pattern Recognition Letters, 105:121–134, 2018.
  * [18] Lianyong Qi, Ruili Wang, Chunhua Hu, Shancang Li, Qiang He, and Xiaolong Xu.  Time-aware distributed service recommendation with privacy-preservation.  Information Sciences, 480:354–364, 2019.
  * [19] Orestis Papakyriakopoulos, Juan Carlos Medina Serrano, and Simon Hegelich.  Political communication on social media: A tale of hyperactive users and bias in recommender systems.  Online Social Networks and Media, 15:100058, 2020.
  * [20] Hoon Wei Lim, Shruti Tople, Prateek Saxena, and Ee-Chien Chang.  Faster secure arithmetic computation using switchable homomorphic encryption.  IACR Cryptol. ePrint Arch., 2014:539, 2014.


# Dendritic Self-Organizing Maps for Continual Learning

Kosmas Pinitas, Spyridon Chavlis, and Panayiota Poirazi2 K. Pinitas was with
the School of Electrical & Computer Engineering, Technical University of
Crete, Greece.
E-mail<EMAIL_ADDRESS>S. Chavlis and P. Poirazi are with the Institute
of Molecular Biology and Biotechnology, Foundation for Research and
Technology-Hellas, Greece.
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>2: Corresponding
authorManuscript received October 2020 0000-0003-0938-682X 0000-0002-1046-1201
0000-0001-6152-595X

###### Abstract

Current deep learning architectures show remarkable performance when trained
in large-scale, controlled datasets. However, the predictive ability of these
architectures significantly decreases when learning new classes incrementally.
This is due to their inclination to forget the knowledge acquired from
previously seen data, a phenomenon termed catastrophic-forgetting. On the
other hand, Self-Organizing Maps (SOMs) can model the input space utilizing
constrained k-means and thus maintain past knowledge. Here, we propose a novel
algorithm inspired by biological neurons, termed Dendritic-Self-Organizing Map
(DendSOM). DendSOM consists of a single layer of SOMs, which extract patterns
from specific regions of the input space accompanied by a set of hit matrices,
one per SOM, which estimate the association between units and labels. The
best-matching unit of an input pattern is selected using the maximum cosine
similarity rule, while the point-wise mutual information is employed for class
inference. DendSOM performs unsupervised feature extraction as it does not use
labels for targeted updating of the weights. It outperforms classical SOMs and
several state-of-the-art continual learning algorithms on benchmark datasets,
such as the Split-MNIST and Split-CIFAR-10. We propose that the incorporation
of neuronal properties in SOMs may help remedy catastrophic forgetting.

###### Index Terms:

self-organizing maps, neuro-inspired algorithms, dendrites, image
classification, continual learning

##  1 Introduction

Deep Learning (DL) architectures have achieved state-of-the-art performance in
several fields such as speech recognition [1], computer vision [2], and
disease diagnosis [3]. However, they are not as successful for learning
multiple tasks sequentially [4]. Most deep neural networks (DNNs) can only be
trained when the entire labeled dataset is at one’s disposal. Re-training is
often required when new data becomes available, due to catastrophic-
forgetting. On the other hand, by leveraging their past experiences, humans
can adapt to environments where new tasks emerge continuously and achieve
impressive performance on real-world problems. Consequently, humans can
continuously acquire new knowledge without forgetting previously learned
information, which is not the case for DNNs.

While extensively applied to numerous fields, DNNs remain vaguely inspired by
biological neural networks since the computational unit (node) of a DNN is a
simplistic model of a biological neuron. However, unlike typical nodes used in
DNNs, biological neurons have dendrites: thin processes that are specialized
for receiving and locally transforming information from other neurons [5].
Incoming signals arrive in the form of synaptic activity, the effect of which
is determined by the weight of the activated inputs and their ability to open
voltage-gated ionic mechanisms that lie across the neuronal membrane. The
opening of such mechanisms results in the nonlinear transformation of the
original signal. As a consequence, input at a given synapse can affect its
neighboring synapses in nonlinear ways. Moreover, unlike typical DNNs,
biological networks are not fully connected. Each neuron receives synaptic
input that projects on its dendrites solely and not from the dendrites of
other neurons, thus creating a sparsely connected, tree-like network
structure. In such biological networks, each neuron samples the environment in
a restricted manner - through its dendrites.

Notably, biological neural networks can change throughout life, a process
known as plasticity. This plasticity is not limited to weight updates, as in
most DNNs. It can also include changes in the spatial organization of
synapses, the coupling strength between dendrites and their somata, as well as
changes in the nonlinear mechanisms within dendrites [6, 7, 8, 9]. Because of
these properties, dendrites are considered the basic computational unit for
integrating synaptic input, undergoing synaptic plasticity, and storing
multiple complex features of the synaptic input. Thus, the incorporation of
dendrites is likely to assist current DL models in obtaining greater
information processing power [10], and recent findings (see Section 2) support
this notion.

Drawing inspiration from the structure and properties of dendrites, we
introduce a SOM-based architecture that models the dendritic nonlinearities
and permits local, parallel computations. The DendSOM map model consists of a
single layer of SOMs. Each SOM is treated as a set of dendrites, and its units
are connected to a single soma. In particular, SOMs receive and model
different subregions of the input space, and the somata estimate the
association between the best-matching units and class labels. We test our
model on classification and continual learning (CL) scenarios and show that
DendSOM can alleviate the effects of catastrophic forgetting. The rest of this
paper is organized as follows. In the next section, we provide the essential
literature review, and in section 3, we revisit the SOM algorithm. Sections 4
and 5 describe the proposed architecture in detail and present the
experimental setup and results.

##  2 Related Work

In CL, the term "catastrophic forgetting" refers to the propensity of a model
to forget the previously learned tasks when re-trained on a new, unseen task
[11]. Over the last years, several models have managed to deal with this
problem to some extent. Context-dependent Gating (XdG) [12] does so by
deactivating a random subset of units on each layer for each task. Therefore,
XdG forces other network parts to learn the subsequent tasks, partially
avoiding overwriting. However, this method can only be utilized for learning
problems in which the task is known since it requires a unique signal for each
given task.

The Learning without Forgetting (LwF) algorithm [13] tries to address
catastrophic forgetting by forcing predictive stability. It contains shared
and task-specific parameters. The goal is to add task-specific parameters for
any new task while learning the shared parameters that work well on all tasks,
using only data and labels from the new task. The Deep Generative Replay (DGR)
model [14], on the other hand, consists of a classifier and a generator
network. The goal of the classifier is to learn a mapping from the input to
the output space, while the generator aims to learn the distribution of the
data in order to sample data based on previous experience. Both algorithms are
trained on the first batch of input data, but when the next batch arrives, the
generator produces the replay data mixed with the training data of the current
batch, and both models are trained in the new, up-sampled dataset.

Elastic Weight Consolidation (EWC) [15] is a prior-focused regularization-
based algorithm which penalizes updates on important weights by adding a
regularization term to the loss function. In this method, the critical
parameters must remain stable since a slight change can cause a dramatic
increase in the loss, due to the high curvature of the loss surface towards
their direction. A neuro-inspired algorithm called Synaptic Intelligence (SI)
[16], allows weights (synapses) to estimate their importance on previous tasks
and penalizes changes to the most vital weights. SI differs from EWC because
it computes the weight importance during stochastic gradient descent (SGD),
unlike EWC, which computes the Fisher Information Matrix at the end of the
training on the batch.

Copy Weight with Reinit (CWR) [17] is considered a baseline technique for
learning from sequential batches in each CL scenario. When the task label is
given, the algorithm freezes the shared weights $\bar{\Theta}$ after the
completion of a task and extends the output layer with new randomly
initialized neurons for the new task. However, when the environment can not
provide information about the task boundaries due to the unavailability of the
task label, the algorithm still follows the same procedure, though, in this
case, the architecture is extended for each training batch. This model has two
sets of weights for the output layer, the consolidated $cw$ weights that are
initialized to zero and used for inference, and the temporary weights $tw$,
which are randomly re-initialized before each batch in order to be used for
batch training. At the end of the batch training, $tw$ is scaled and copied to
$cw$.

The Copy Weight with Reinit+ (CWR+) [17] is a modified version of CWR. The
modifications include the global mean-shift of $tw$ and the zero-
initialization of the output layer. Additionally, the Architectural and
Regularization approach (AR1) [17] is a hybrid algorithm that utilizes both
parameter isolation and regularization. In particular, AR1 is similar to the
CWR+ algorithm since it follows an almost identical training process. However,
this algorithm employs SI to introduce the concept of parameter importance and
thus tune the shared weights $\bar{\Theta}$ across the entire dataset.
Finally, in generative classification [18], a separate variational autoencoder
(VAE) is trained in order to learn the data distribution for each class. Next,
importance sampling is employed to estimate the likelihood of a test sample
$x$ under the VAE model of class $y$ denoted as $p(x|y)$, while $p(y)$ can
either be assumed to follow a normal distribution or is calculated by counting
sample observations, where the Bayesian rule is used for inference. Last but
not least, a method closer to ours, the Self-Organized Multi-Layer Perceptron
(SOMLP) [19] utilizes a SOM to control the activation of the units on the
hidden layer of a Multilayer Perceptron to avoid overwriting of the previously
learned information, which leads to catastrophic forgetting.

The main challenge of the algorithms that have alleviated the effects of
catastrophic forgetting is that they can only be trained when all classes are
known before training. This prerequisite is not realistic in real-world
scenarios, where new classes emerge continuously. We propose a novel, semi-
unsupervised learning algorithm based on the SOM architecture, which
incorporates features discovered in biological dendrites to address this
challenge. Specifically, the DendSOM is a shallow network that performs
classification and incorporates the following biological properties: i)
sparse/restricted sampling of the input space via the use of receptive fields,
ii) restricted connectivity through the implementation of soma-specific SOMs
(akin to dendrites), iii) local, nonlinear computations mimicking the signal
integration properties of biological dendrites and iv) the use of spatially
organized memory images (prototypes) to learn information about the input
space. We evaluate this architecture on three incremental learning scenarios
[20] using the split protocol on the MNIST and CIFAR-10 benchmark datasets. We
show that our model performs favorably compared to other state-of-the-art
architectures, suggesting that incorporating properties found in real neurons
can be beneficial for complex machine learning problems.

##  3 Self-Organizing Map

The SOM is an unsupervised learning algorithm that non-linearly projects high-
dimensional input data to a space of lower dimensions (typically two-
dimensional). The SOM applies competitive learning to construct the map’s
topology such that the more similar the input data, the shorter their distance
on the map [21].

###  3.1 Learning Algorithm

The SOM consists of a grid of units. Each unit $i$ has a predetermined
position $\mathbf{p_{i}}$ on the grid, where
$\mathbf{p_{i}}\in\mathbb{N}^{+^{m}}$ and $m$ is the grid’s dimensions.
Furthermore, the $i$-th unit maintains a weight vector
$\mathbf{w_{i}}\in\mathbb{R}^{k}$ where $k$ is the number of dimensions of the
input vector $\mathbf{x_{n}}$ with $n=1,2,\dots,N$, where $N$ denotes the
number of samples. The weight vectors are initialized to small random values.

The SOM is trained iteratively, and at each iteration $t$, the learning
process performs the following steps:

  1. 1.

Select a sample vector $\mathbf{x}$ randomly from the input dataset $X$

  2. 2.

Identify the Best-Matching Unit (BMU) that satisfies:

$BMU=\operatorname*{arg\,min}_{i}||\mathbf{x}-\mathbf{w}_{i}||^{2}_{2}$ (1)

where $||\cdot||_{2}$ denotes the 2-norm (so-called Euclidean norm).

  3. 3.

Update each weight vector $i$ using the following equation:

$\mathbf{w}_{i}(t+1)=\mathbf{w}_{i}(t)+a(t)h^{BMU}_{i}(t)\bigg{(}\mathbf{x}-\mathbf{w_{i}(t)}\bigg{)}$
(2)

The learning rate $a(t)$ at training step $t$ is calculated by:

$a(t)=a_{0}\exp\bigg{(}-\frac{t}{\lambda}\bigg{)}$ (3)

Moreover, the neighborhood function $h^{BMU}_{i}(t)$ at iteration $t$ is
calculated as follows:

$h^{BMU}_{i}(t)=\exp\bigg{(}-\frac{||\mathbf{p}_{i}-\mathbf{p}_{BMU}||^{2}_{2}}{2\sigma(t)}\bigg{)}$
(4)

where $\mathbf{p}_{BMU}$ denote the position of the BMU on the grid, and
$\sigma(t)$ corresponds to the neighborhood radius at step $t$ and it can be
calculated by:

$\sigma(t)=\sigma_{0}\exp\bigg{(}-\frac{t}{\lambda}\bigg{)}$ (5)

During the update step, the BMU and its topological neighbors move closer to
the input vector while $a(t)$, $\sigma(t)$ and $h^{BMU}_{i}(t)$ decrease
exponentially over time (a schematic representation is depicted in Figure 1.
Moreover, $a_{0}$ and $\sigma_{0}$ are the initial values of the learning rate
and neighborhood radius, respectively, while $\lambda$ is a hyperparameter
that controls the decrease rate for both $\sigma(t)$ and $a(t)$.

Figure 1: Training process of SOM. In this example, the unit in position
$(2,2)$ is selected as the BMU for the input vector $x$.

##  4 Dendritic Self-Organizing Map

Unlike other SOM-based deep learning architectures such as Deep SOM, Deep
Convolutional SOM, and Layered-SOM [22, 23, 24], the DendSOM proposed here is
a shallow neural network that can be trained using unsupervised competitive
learning algorithms. Hence, it can be applied to classification and CL tasks.
DendSOM employs multiple SOMs to model different subregions of the input space
(receptive fields). Like dendrites in biological neurons, each SOM receives
spatially-restricted input information and estimates the positional vector of
the BMU, which it subsequently propagates to its respective soma, where the
association between labels and BMUs is calculated. The incorporation of
receptive fields allows for more accurate modeling of the input space since it
considers the temporal evolution of the images. However, introducing the
notion of receptive fields without restricted connectivity (i.e., computing
the BMU solely for the receptive field of each SOM) can significantly increase
the training time due to the lack of computational parallelism.

###  4.1 Architecture

As mentioned above, the DendSOM uses multiple SOMs to model the input pattern
from different subregions of the input space. Consequently, for an input
$\mathbf{x}$ of size $N_{1}\times N_{2}$ and SOMs that extract patterns of
size $P_{1}\times P_{2}$ we need $S_{1}\times S_{2}$ SOMs in order to properly
model the input space. Assuming the stride $s_{1}$, $s_{2}$ respectively, then
$S_{1}$ and $S_{2}$ can be calculated by:

$\begin{split}S_{i}=\bigg{\lfloor}\frac{N_{i}-P_{i}}{s_{i}}\bigg{\rfloor}+1,\>\>\>i\in\\{1,2\\}\end{split}$
(6)

where $\lfloor\cdot\rfloor$ denotes the floor operation.

In our implementation $s_{1}=s_{2}$, $N_{1}=N_{2}$, $P_{1}=P_{2}$ and thus
$S_{1}=S_{2}$.

###  4.2 Best Matching Unit

In the original SOM algorithm, the BMU is defined as the unit whose weight
vector has the minimum Euclidean distance from the input vector, as shown in
equation (1). The Euclidean distance corresponds to the L2 norm of a
difference between vectors. Thus, the Euclidean distance estimates the
similarity between patterns by measuring how close the images are with respect
to their pixel intensity. The cosine similarity is a different metric, which
is proportional to the dot product of two vectors and inversely proportional
to the product of their magnitudes. Patterns with high cosine similarity are
located in the same general direction from the origin (Figure 2). In this
work, we used the cosine similarity to express the BMU selection objective:

$BMU=\operatorname*{arg\,max}_{i}\>\>\cos(\theta_{x,w_{i}})$ (7)

where $\theta_{x,w_{i}}$ is the angle between the input vector $\mathbf{x}$
and the weight vector of the $i$-th unit $\mathbf{w_{i}}$. The cosine
similarity between two vectors $\mathbf{v}$, $\mathbf{u}$ can be calculated
by:

$\cos(\theta_{v,u})=\frac{\mathbf{v}^{\text{T}}\mathbf{u}}{||\mathbf{v}||_{2}\>||\mathbf{u}||_{2}}$
(8)

Figure 2: This diagram shows the 2D vectors $x$ (input vector) $w_{1}$ and
$w_{2}$ (weight vectors). According to the minimum euclidean distance rule,
the unit that contains $w_{1}$ is the best matching unit since
$euc(x,w_{1})<euc(x,w_{2})$. However, the angle between $x$ and $w_{2}$ is
smaller than the the angle between $x$ and $w_{1}$ and consequently
$\cos(x,w_{2})>\cos(x,w_{1})$. Hence the maximum cosine rule indicates that
the best matching unit is the unit with weight vector $w_{2}$. The cosine
similarity rule is a scale invariant rule since it depends only from the
inter-pixel relations and not from the exact pixel values.

###  4.3 Learning Algorithm

Each SOM can be trained independently by utilizing equation 7 for BMU
identification, and equations 2-5 for adjusting the weight vectors. Apart from
that, a hit matrix has been assigned to each SOM to assist in measuring the
association between SOM units and labels. This association corresponds to the
number of times a unit was selected as a BMU for a specific label (Figure 3
and Algorithm 1). Notably, the learning procedure is the same for both
classification and CL. However, in CL we feed the data of each class
sequentially instead of sampling a random input vector from the entire
dataset.

Algorithm 1 DendSOM training algorithms

Input: $X_{train}$, $y_{train}$, $model$
Parameters: $\alpha_{0}$, $\sigma_{0}$, $\lambda$, $\alpha_{crit}$, $r_{exp}$,
$n_{iter}$, $iter\\_crit$
Output: $model$, $H$

1:

2:$model.random\\_init()$ $\triangleright$ Random initialization

3:$H\leftarrow zeros(n\\_labels,S_{1}\times S_{2},U_{1}\times U_{2})$

4:$t\leftarrow 0$

5:$iter\\_crit\leftarrow\log\big{\lfloor}\lambda\frac{\alpha_{0}}{\alpha_{crit}}\big{\rfloor}$

6:for $i\leftarrow 1$ to $n_{iter}$ do

7: $sample,label\leftarrow X_{train}[i],y_{train}[i]$

8: $rfs\leftarrow create\\_receptive\\_fields(sample)$

9: $bmus\leftarrow identify\\_bmus(rfs,model)$

10: $model\leftarrow model\\_update(model,bmus,\alpha_{0},\sigma_{0},\lambda)$

11: $H[label,bmus]\leftarrow H[label,bmus]+1$

12: if $i\mathbin{\%}iter\\_crit==0$ then

13: $t\leftarrow\big{\lfloor}\frac{t}{r_{exp}}\big{\rfloor}$

14: end if

15:end for

16:$t=t+1$

We set $r_{exp}=1$ for classification or clustering. The $iter\\_crit$
parameter can be derived as follows:

$\begin{split}\alpha_{crit}=\alpha_{0}\text{exp}\bigg{(}-\frac{iter\\_crit}{\lambda}\bigg{)}\end{split}$
$\begin{split}\frac{\alpha_{0}}{\alpha_{crit}}&=\text{exp}\bigg{(}\frac{iter\\_crit}{\lambda}\bigg{)}\end{split}$
$\begin{split}iter\\_crit&=\lambda\log\frac{\alpha_{0}}{\alpha_{crit}}.\end{split}$

Applying the floor operation, we obtain:

$iter\\_crit=\bigg{\lfloor}\lambda\log\frac{\alpha_{0}}{\alpha_{crit}}\bigg{\rfloor},iter\\_crit\in\mathbb{N}$
(9)

###  4.4 Decision Rule

Point-wise mutual information (PMI) is a measure of the association between a
pattern and an action. The PMI of two outcomes $x_{o},\>y_{o}$ can take
positive values when $x_{o},\>y_{o}$ co-occur more frequently than expected
under an independence assumption, negative values when the outcomes co-occur
less frequently than expected, and it can be equal to $0$ when the outcomes
are statistically independent. Given a hit matrix, we can calculate the PMI
between a label $(l)$ and a BMU as follows:

$\begin{split}PMI(l;BMU)=\log{\frac{P(l|BMU)}{P(l)}}\end{split}$ (10)

where $P(l|BMU)$ corresponds to the conditional probability of a class label
given a BMU and it can be calculated using the hit matrix, i.e., $H$:

$\begin{split}P(l|BMU)=\frac{H[l,BMU]}{\sum_{i\in Labels}H[i,BMU]}\end{split}$
(11)

Moreover, the prior probability $P(l)$ can be calculated by:

$\begin{split}P(l)=\frac{\sum_{u\in Units}H[l,u]}{\sum_{u\in Units}\sum_{i\in
Labels}H[i,u]}\end{split}$ (12)

According to Section 3.1, in the case of DendSOM, we have more than one BMU.
In fact, we have a BMU for each dendritic SOM, hence the problem of class
prediction can be formulated in the following way. Let $I$ be an input image
of unknown label and $BMU=\\{bmu_{1},\>bmu_{2},\dots,bmu_{n}\\}$ a set that
contains the BMUs of $I$. Thus, we can express the objective of the label
prediction problem as:

$\begin{split}prediction=\operatorname*{arg\,max}_{l\in
Labels}\sum_{i=1}^{n}PMI(l;bmu_{i})\end{split}$ (13)

Figure 3: The input image is divided into subregions. Each subregion of the
input space is modeled from the corresponding SOM. The SOMs identify the BMUs
whose indices are then propagated to the appropriate hit matrices. These
matrices estimate the association between the BMUs and the class labels.

###  4.5 Addressing the challenges of CL

The challenges that can arise during a CL task and how DendSOM addresses these
challenges are described below:

####  4.5.1 Catastrophic Forgetting

As previously mentioned, catastrophic forgetting refers to a model’s inability
to retain the knowledge acquired from previous concepts when trained
incrementally on learning new ones. Given that DendSOM performs constrained
k-means (it preserves the topological structure [25]), similar samples are
matched to the same or neighboring units, while dissimilar samples are matched
to different units. This strategy inherently minimizes the interference
between samples and consequently reduces catastrophic forgetting.

####  4.5.2 Memory Management

Retaining knowledge is crucial for avoiding catastrophic forgetting during
training in CL settings. Hence, many algorithms utilize memory mechanisms to
store and replay information about past tasks [26, 27]. An efficient memory
management system should only save valuable information that can be
transferred to future tasks. The trade-off problem, also known as the
plasticity-stability [28] problem, states that an algorithm should balance the
information saved and forgotten. The DendSOM is a memoryless architecture with
respect to example data, and thus, memory management has no impact on the
performance of our algorithm. However, minor memory usage is required for
storing the hit matrices and the DendSOM’s units.

####  4.5.3 Concept Drift

Distribution Shifts are caused by distribution changes that may lead to
catastrophic interference and consequently to catastrophic forgetting. Hence,
a model has to detect and adapt to these changes to alleviate the effects of
distributional shifts. There are two types of concept drifts [29]. Changes in
the input distribution cause the virtual concept drift, and the actual concept
drift is prompted by novelty in the data. The DendSOM model accounts for both
real and virtual concept drifts. It does so by estimating the prior and
posterior probabilities and utilizing PMI as a decision rule since it is only
affected by the ratio of the posterior and prior probabilities and not by
their exact values.

##  5 Benchmark Datasets & The Split Protocol

We evaluated our network on the MNIST, the MNIST-FASHION, and the CIFAR-10
datasets, all of which are used to benchmark CL problems.

Figure 4: Example images for the different classes of the A. MNIST dataset, B.
MNIST-FASHION dataset and C. CIFAR-10 dataset.

###  5.1 MNIST

The MNIST dataset [30] contains images of handwritten digits and consists of a
training set with 60,000 samples and a test set with 10,000 samples. Each
image is centered and size-normalized to $28\times 28$ pixels with 256 gray
levels and is associated with a label from 10 classes (i.e., 0-9 digits)
(Figure 4A).

###  5.2 MNIST-FASHION

The MNIST-FASHION dataset [31] contains images of clothes and serves as a
replacement of the original MNIST dataset. In particular, these datasets share
the same image size, labeling, and structure of training and testing splits
(Figure 4B).

###  5.3 CIFAR-10

The CIFAR-10 dataset [32] consists of 60,000 $32\times 32$ color images in 10
classes, with 6,000 images per class. The training set consists of 50,000
samples, while there are 10,000 test images. In our implementation, each image
is turned into gray-scale since our model can not yet process color images
(i.e., three-dimensional images) (Figure 4C).

###  5.4 The Split protocol

The split protocol operates on the entire dataset by splitting the given
dataset into clearly separated tasks (Figure 5). The Split MNIST is a typical
dataset that is utilized for benchmarking CL methods. It was introduced in a
five-task form where the ten classes are split into five binary classification
problems. We also apply the split protocol to the CIFAR-10 dataset, which is
significantly more challenging.

Figure 5: Tasks of the Split-MNIST protocol. The digits in parenthesis below
each image denote the original label, while the digits not in parenthesis
denote the label with respect to a given task, i.e., binary classification.

##  6 CL scenarios

Although several machine learning scenarios permit models to operate on the
entire dataset, in CL, data arrive incrementally as subsets of samples.
According to [20], CL cases are categorized into three main scenarios. Using
the Split-MNIST as an example, we summarize the objective of each scenario in
Table I:

Table I: Objective of each CL scenario. The scenarios are shown from the easiest to the most difficult one. Scenario | Objective
---|---
Task-IL | Is it 0 or 1? (Task given)
Domain-IL | Is it 0 or 1? (Task unknown)
Class-IL | Which digit is it? (0-9)
|

###  6.1 Task-Incremental Learning

Task-Incremental Learning (Task-IL) is the easiest CL scenario since the model
can utilize task-related information. The dataset is permuted into non-
overlapping tasks, and during training, only data from the current task is
available (Figure 6A).

Figure 6: Illustration of the different CL scenarios using the split-MNIST
dataset. A. Task-IL scenario. B. Domain-IL scenario. C. Class-IL scenario. At
bottom of each image the target class is given. Notice that in B and C the
task is not given to the model.

###  6.2 Domain-Incremental Learning

Domain-Incremental Learning (Domain-IL) is similar to Task-IL except that the
model cannot access information related to the task. Thus, for a given set
$D=\\{x_{i},y_{i}\\}_{i=1...2}$, the model has to solve the task at hand
(Figure 6B).

###  6.3 Class-Incremental Learning

The goal of Class-Incremental Learning (Class-IL) is to learn, given a dataset
$D=\\{x_{i},y_{i}\\}_{i=1...n}$, a unified classifier. Similar to Domain-IL,
the model can not utilize task information in this scenario (Figure 6C and 7).

Figure 7: Class-IL scenario on the Split-CIFAR-10 dataset. On bottom of each
image the target class is given.

##  7 Parameter Settings

To diminish the non-deterministic effect of the initialization phase (random
initial weights), we repeated each experiment 10 times (i.e., trials). This
number of trials is sufficient to illustrate the behavior of our proposed
algorithm. We selected the architecture and training parameters for the
network models through a trial-and-error process. It is worth noting that
$U_{1}$ and $U_{2}$ correspond to the number of units in each SOM. For
comparison purposes, we report the performance of DendSOM against the one
achieved by a traditional SOM network with a similar number of trainable
parameters.

###  7.1 Training Parameters

The DendSOM training hyperparameters for both SOM vs. DendSOM comparison and
incremental-learning experiments are depicted in Table II. Note that only the
hyperparameter $r_{exp}$ changes in the case of incremental learning
experiments since it prevents the algorithm from converging before the
completion of the training process.

Table II: Training hyperparameters for the classification task, i.e., SOM vs. DendSOM. Dataset | $\mathbf{\alpha_{0}}$ | $\mathbf{\sigma_{0}}$ | $\mathbf{\lambda}$ | $\mathbf{r_{exp}}$
---|---|---|---|---
MNIST | $0.95$ | $4$ | $1\text{e}3$ |  $1^{\dagger}$, $2^{\ddagger}$
MNIST-FASHION | $0.95$ | $5$ | $1\text{e}3$ |  $1^{\dagger}$, $2^{\ddagger}$
CIFAR-10 | $0.95$ | $6$ | $1\text{e}3$ |  $1^{\dagger}$, $2^{\ddagger}$
† classification task.
‡ incremental learning task.

###  7.2 Architecture Parameters

The architecture parameters used on the MNIST, MNIST-FASHION, and CIFAR-10
datasets are shown in Table III. We used the same DendSOM architecture in all
of the reported experiments.

Table III: Architecture parameters for each architecture and dataset. MNIST
---
Model | $\mathbf{S_{1}}$ | $\mathbf{S_{2}}$ | $\mathbf{U_{1}}$ | $\mathbf{U_{2}}$ | $\mathbf{P_{1}}$ | $\mathbf{P_{2}}$ | $\mathbf{s_{1}}$ | $\mathbf{s_{2}}$
DendSOM | $7$ | $7$ | $8$ | $8$ | $10$ | $10$ | $3$ | $3$
SOM | $1$ | $1$ | $21$ | $21$ | $28$ | $28$ | $-$ | $-$
|  |  |  |  |  |  |  |
MNIST-FASHION
Model | $\mathbf{S_{1}}$ | $\mathbf{S_{2}}$ | $\mathbf{U_{1}}$ | $\mathbf{U_{2}}$ | $\mathbf{P_{1}}$ | $\mathbf{P_{2}}$ | $\mathbf{s_{1}}$ | $\mathbf{s_{2}}$
DendSOM | $6$ | $6$ | $10$ | $10$ | $8$ | $8$ | $4$ | $4$
SOM | $1$ | $1$ | $18$ | $18$ | $28$ | $28$ | $-$ | $-$
|  |  |  |  |  |  |  |
CIFAR-10
Model | $\mathbf{S_{1}}$ | $\mathbf{S_{2}}$ | $\mathbf{U_{1}}$ | $\mathbf{U_{2}}$ | $\mathbf{P_{1}}$ | $\mathbf{P_{2}}$ | $\mathbf{s_{1}}$ | $\mathbf{s_{2}}$
DendSOM | $15$ | $15$ | $12$ | $12$ | $4$ | $4$ | $2$ | $2$
SOM | $1$ | $1$ | $29$ | $29$ | $32$ | $32$ | $-$ | $-$
|  |  |  |  |  |  |  |

###  7.3 Computational resources and Statistical tests

The experiments presented in the following section and the respective analysis
are implemented in python (version 3.8.8) programming language using custom-
based software. The scripts and derived data supporting the findings of this
study are available from the corresponding author [P.P] on request. All
experiments were performed on a desktop equipped with an Intel${\circledR}$
Core${}^{\text{TM}}$ i7-9700 CPU, a GeForce RTX 2080 Ti GPU, 32 GB RAM, and
CentOS Linux (version 7.9) operating system. To compare the algorithms, we
performed Welch’s ANOVA test. The $\alpha$ was set to $0.05$ ($95\%$
confidence interval). To account for multiple comparisons, we performed a
Dunnett’s T3 test.

##  8 Experiments

###  8.1 SOM vs. DendSOM

####  8.1.1 Experiment Objective

In this experiment, we test the hypothesis that the DendSOM algorithm allows
for improved classification performance compared to the original SOM
algorithm. To do so, we compare the two algorithms in terms of the accuracy
score on three publicly available datasets.

Table IV: Classification accuracy scores obtained by each architecture on three benchmark datasets. Performance accuracy is listed as mean $\pm$ standard deviation over $N=10$ trials. All comparisons amongst all algorithms are statistically significant ($p<10^{-3}$, Dunnett’s T3 multiple comparisons test) for MNIST, MNIST-FASHION, and CIFAR-10 datasets, respectively. Model | MNIST | MNIST-FASHION | CIFAR-10
---|---|---|---
SOM† | $84.94\pm 0.58$ | $73.94\pm 0.34$ | $26.45\pm 0.13$
SOM‡ | $87.26\pm 1.07$ | $76.09\pm 0.29$ | $27.13\pm 0.15$
DendSOM† | $\mathbf{94.93\pm 0.18}$ | $\mathbf{77.84\pm 0.11}$ | $\mathbf{37.97\pm 0.11}$
DendSOM‡ | $\mathbf{95.28\pm 0.02}$ | $\mathbf{80.88\pm 0.26}$ | $\mathbf{46.79\pm 0.10}$
† Euclidean distance was used for BMU identification.
‡ Cosine similarity was used for BMU identification.

####  8.1.2 Results

As evident from the results in Table IV, both the architecture and the
distance used for BMU identification affect performance. Specifically,
utilizing multiple SOMs to map different regions of the image (DendSOM)
improves the performance of the original algorithm (SOM) since the final
matching pattern is not just a weighted average of similar images but consists
of several informative features. Furthermore, using the cosine similarity as
opposed to the Euclidean distance for the identification of the BMU allows for
improved performance as the former is only influenced by the inter-pixel
relation between the weight vector and the corresponding receptive field. In
contrast, the Euclidean distance takes into account the average difference
between pixel values. Specifically, the DendSOM that employs cosine-similarity
for BMU identification achieves the highest accuracy score on all datasets.
Finally, all algorithms achieve their highest and lowest scores on the MNIST
and CIFAR-10 datasets, respectively, which is expected because the MNIST
dataset consists of handwritten digits in a static background (and therefore
is the simplest task), while the CIFAR-10 dataset consists of 10 real-world
classes in a dynamic background. Due to this complexity, the geometrical
properties of the input space cannot be described appropriately neither by the
cosine-similarity nor by the Euclidean distance.

###  8.2 Task-IL scenario

####  8.2.1 Experiment Objective

The performance of our algorithm is also evaluated and compared to other
state-of-the-art architectures [20] on the Split-MNIST protocol under the
Task-IL scenario. The results are shown in Table V, and the comparison of the
different models in Figure 8A.

Table V: Accuracy scores for all compared algorithms on the Split-MNIST protocol under the Task-IL scenario. Performance accuracy is listed as mean $\pm$ standard deviation over $N=10$ (SOM, DendSOM) and $N=20$ (for the other algorithms) trials. All comparisons between DendSOM and the other algorithms are statistically significant ($p<10^{-4}$, Dunnett’s T3 multiple comparisons test). Model | MNIST
---|---
SOM† | $91.87\pm 0.58$
SOM‡ | $92.82\pm 0.36$
DendSOM‡ | $\mathbf{97.73\pm 0.25}$
EWC | $98.64\pm 0.22$
SI | $99.09\pm 0.15$
XdG | $99.10\pm 0.08$
Online EWC | $99.12\pm 0.11$
DGR | $99.50\pm 0.03$
LwF | $99.57\pm 0.02$
DGR+ distill | $99.61\pm 0.02$
† Euclidean distance was used for BMU identification.
‡ Cosine similarity was used for BMU identification.

####  8.2.2 Results

As shown in Table V, most models perform well in this scenario, except for the
SOM algorithm. Notably, the DendSOM algorithm achieves a higher accuracy score
than the SOM algorithm because the latter process the whole image at once.
Importantly, unlike other methods, neither the SOM nor the DendSOM can use the
task information to learn task-specific features by freezing or regularizing
their weight vectors. In contrast, they utilize this information only to
estimate the appropriate probability distributions. In addition, when the
Euclidean distance is used as a BMU selection rule, the algorithm does not
consider the temporal evolution of the images.

###  8.3 Domain-IL scenario

####  8.3.1 Experiment Objective

This experiment is similar to the one mentioned above except that the models
operate under Domain-IL constraints [20].

####  8.3.2 Results

As shown in Table VI and in Figure 8B, the $DendSOM_{cos}$ algorithm achieves
an accuracy score of $89.70$, ranking among the top 3 models for Domain-IL on
the Split-MNIST dataset. However, the other algorithms perform multiple
training epochs per task and are trained in batch mode. On the contrary, there
is only one stream of samples, and each sample is presented only once in both
the SOM and DendSOM algorithms. While the SOM algorithm using the Euclidean
distance ranks fifth with respect to performance accuracy, its performance is
inferior to the DendSOM algorithm with cosine similarity. The superiority of
the DendSOM algorithm can be explained by its architecture and the BMU
selection rule, as mentioned in the previous experiments.

Table VI: Accuracy scores for all compared algorithms on the Split-MNIST protocol under the Domain-IL scenario. Performance accuracy is listed as mean $\pm$ standard deviation over $N=10$ (SOM, DendSOM) and $N=20$ (for the other algorithms) repetitions. All comparisons between DendSOM and the other algorithms are statistically significant ($p<10^{-4}$, Dunnett’s T3 multiple comparisons test). Model | MNIST
---|---
SOM† | $78.69\pm 1.28$
SOM‡ | $81.90\pm 1.04$
DendSOM‡ | $\mathbf{89.70\pm 0.27}$
EWC | $63.95\pm 1.90$
Online EWC | $64.32\pm 1.90$
SI | $65.36\pm 1.57$
LwF | $71.50\pm 1.63$
DGR | $95.72\pm 0.25$
DGR+ distill | $96.83\pm 0.20$
† Euclidean distance was used for BMU identification.
‡ Cosine similarity was used for BMU identification.

###  8.4 Class-IL scenario

####  8.4.1 Experiment Objective

Finally, we compare the performance of our algorithm to the state-of-the-art
models [18] in Class-IL scenario, on both Split-MNIST (Figure 8C) and Split-
CIFAR-10 (Figure 8D) datasets.

####  8.4.2 Results

As shown in Table VII, DendSOM with cosine similarity outperforms most of the
other algorithms for both datasets. The DendSOM algorithm achieved accuracy
scores of $92.82$ and $45.97$ on the Split-MNIST and Split-CIFAR-10 datasets,
respectively, corresponding to the second-highest scoring algorithm.
Furthermore, unlike the other models, the DendSOM with cosine similarity was
trained online since the tasks were presented sequentially and only once,
while the batch size was equal to 1. Once again, the SOM-based algorithms are
proven to be simple yet effective algorithms in CL that perform comparably
with several leading-edge regularization and hybrid algorithms. However, the
DendSOM with cosine similarity achieves a significantly higher accuracy score
than the SOM with euclidean distance because the cosine similarity rule does
not consider the sum of individual pixel intensity differences is the case
when euclidean distance is used. Moreover, the restrictive connectivity
introduced in the DendSOM algorithm with cosine similarity allows for a more
detailed mapping of the input space, which, in turn, accounts for capturing
the temporal changes in the input data (images).

Table VII: Accuracy scores for all compared algorithms on the Split-MNIST and Split-CIFAR-10 protocols under the Class-IL scenario. Performance accuracy is listed as mean $\pm$ standard deviation over $N=10$ trials. All comparisons between DendSOM and the other algorithms are statistically significant ($p<10^{-4}$, Dunnett’s T3 multiple comparisons test) for both Split-MNIST and Split-CIFAR-10 protocols. Model | MNIST | CIFAR-10
---|---|---
SOM† | $59.61\pm 0.67$ | $25.55\pm 0.36$
SOM‡ | $62.92\pm 0.85$ | $26.43\pm 0.24$
DendSOM‡ | $\mathbf{92.82\pm 0.12}$ | $\mathbf{45.97\pm 0.07}$
DGR | $91.30\pm 0.60$ | $17.21\pm 1.88$
EWC | $19.95\pm 0.05$ | $18.63\pm 0.29$
SI | $19.95\pm 0.11$ | $18.14\pm 0.36$
CWR | $32.48\pm 2.64$ | $18.37\pm 1.61$
CWR+ | $37.21\pm 3.11$ | $22.32\pm 1.08$
AR1 | $48.84\pm 2.55$ | $24.44\pm 2.55$
GC | $93.79\pm 0.08$ | $56.03\pm 0.04$
† Euclidean distance was used for BMU identification.
‡ Cosine similarity was used for BMU identification.
Figure 8: Illustration of the model performance for different CL scenarios
using the split-MNIST and Split-CIFAR-10 datasets over 3 repetitions per
scenario and model. y-axis shows the Top-1 Accuracy, i.e., the conventional
accuracy, while x-axis denote the number of tasks. (blue) DendSOM, (orange)
SOM with Euclidean distance for BMU identification, (green) SOM with cosine
similarity for BMU identification. A. Task-IL scenario. B. Domain-IL scenario.
C. Class-IL scenario using the Split-MNIST. D. Class-IL scenario using the
Split-CIFAR-10.

##  9 Conclusion

In this work, we proposed a new SOM-based architecture (DendSOM) that utilizes
neuroscience and information theory concepts to address the long-standing
problem of catastrophic-forgetting, which is crucial for avoiding model re-
training when new data are presented. We showed that DendSOM consistently
outperforms the original SOM algorithm on several benchmark classification
tasks. Thus, mimicking the dendritic processing observed in biological neurons
(i.e., receptive fields and local computation of BMU) plays a significant role
in improving the predictive power of classical SOM architectures. Importantly,
DendSOM is a memory-efficient algorithm, trained for just a single epoch,
using only one input stream -equivalent to a batch size of one- which further
improves implementation efficiency compared to other algorithms. Finally, we
showed that DendSOM performs on par with the current state-of-the-art methods
on many continual learning tasks while achieving higher performance than most
leading-edge architectures on the Domain-IL and Class-IL scenarios. Overall,
DendSOM has several advantages in its architecture and performance accuracy,
which can help address the problem of catastrophic forgetting for real-world
applications.

## Author contributions

K.P. designed, implemented and performed the experiments and the data
analysis. K.P., S.C. and P.P. conceived and wrote the paper. P.P. supervised
the project.

## Conflict of interest

The authors declare no conflict of interest.

## Acknowledgment

We thank Grigorios Tsagkatakis, PhD for his critical and constructive feedback
on our manuscript. This work was supported by the
H2020-FETOPEN-2018-2019-2020-01, FET-Open Challenging Current Thinking, grant
NEUREKA: GA-863245 and the NIH grant No 1R01MH124867-01.

## Hyperparameter-tuning Analysis

Several training hyperparameters control the behavior of the DendSOM. The
ultimate goal is to find an optimal combination of these hyperparameters that
increases the predictive power of our model and thus gives better results.
Hence, additional experiments have been performed to determine how the
training hyperparameters affect the performance of our model individually. In
fact, we discovered a good set of hyperparameters through a trial-and-error
process (Tables II and III) based on which we carried out the following
experiments.

As Figure 9 shows, a higher $\alpha_{0}$ usually results in a higher accuracy
score. However, the original SOM algorithm requires that $0<\alpha_{0}<1$, and
the maximum cosine similarity rule for BMU identification is a scale-invariant
rule. Thus, this experiment can be extended for $\alpha_{0}>1$. For
$\alpha_{0}=0.1$, the DendSOM model has an accuracy score of $0.936$, which
suggests that it is possible to make accurate predictions without updating the
map during the training process, but this hypothesis has to be tested.

Figure 9: Initial learning rate affects the classification accuracy of the
DendSOM algorithm on the MNIST dataset. As the initial learning rate
($\alpha_{0}$) increases, the accuracy of the model is improved.

We initialized the $\sigma_{0}$ using the following heuristic:

$\sigma_{0}=\frac{\max\\{U_{1},U_{2}\\}}{2}$

where $U_{1}$ and $U_{2}$ correspond to the number of units across the
horizontal and vertical axis respectively

Figure 10: The behavior of $h$ functions for $r_{exp}=1$ as function of the
distance from the BMU. Colors denote different values of $t$.

Figure 11: Behavior of $a$ (top) and $\sigma$ (bottom) as functions of the
training steps. Colors denote different values of the $\lambda$ parameter.

Figure 12: (top) Influence of $\alpha_{crit}$ and (bottom) $r_{exp}$
hyperparammeters over the DendSOM algorithm tested on CIFAR-10 (blue filled
circles) and MNIST (green filled circles). Notice that the x-axis in the top
panel is in logarithmic scale since
$\alpha_{crit}\in\\{5\text{e-}1,5\text{e-}2,5\text{e-}3,5\text{e-}4,5\text{e-}5,5\text{e-}6\\}$.

Figure 13: (top) Receptive field size affects the DendSOM algorithm. The
accuracy is a non-monotonic function of the receptive field size. The accuracy
drops for small or large sizes, whereas for intermediate values, the model
achieves its best performance. (bottom) Influence of number of units per map
over the DendSOM (blue) and SOM (green) algorithms.

The neighborhood function (Figure 10) is a Gaussian function whose variance
decreases over time due to the decrease of $\sigma$ function. Thus for
$r_{exp}=2$, the variance of the $h$ Gaussian function doubles every
$iter\\_crit$ training steps, which allow for better mapping of the input
space in the case of CL since the input space is not entirely presented to the
model before the completion of the training process.

As shown in Figure 11, for $\lambda=1\text{e}3$, both $\alpha$ and $\sigma$
tend to zero after almost 1,000 time steps, and thus the DendSOM can not
properly map the input space due to an insufficient number of input samples.
However, for higher $\lambda$ values, the mapping process requires several
epochs to be completed, which increases the training time of the algorithm. In
the case of the DendSOM model, $\lambda=1\text{e}3$ is a good choice since
incorporating the receptive fields allows for averaging in smaller regions of
the input space and thus extracting simpler patterns.

What is more, Figure 12 indicates that high $a_{crit}$ values tend to decrease
the performance of the algorithm, while relatively low $r_{exp}$ values tend
to improve the predictive ability of our model. Either high $r_{exp}$ or high
$\alpha_{crit}$ values tend to increase both $\alpha$ and $\sigma$
dramatically, which in turn leads to weight vector overwriting. It is worth
noting that the algorithm marks the highest accuracy score on MNIST and
CIFAR-10 datasets for $\alpha_{crit}=0.005$ and $\alpha_{crit}=0.00005$,
respectively.

Moreover, Figure 13 (top) indicates that the accuracy score of our model
increases for receptive field sizes smaller than $10$ since the patterns
extracted from the input space are most likely to be informative patterns and
thus non-typical patterns. On the other hand, when the receptive field size is
greater than $10$, the DendSOM is reduced to a SOM, and therefore, the
accuracy score decreases. It is worth to be mentioned that for receptive field
size equal to $1$, the accuracy score is $9\%$.

Finally, Figure 13 (bottom) shows that increasing the number of units improves
the performance of the SOM algorithm. However, this does not seem to be the
case for the DendSOM model since increasing the number of units above 100
decreases the model’s predictive ability. This result is counter-intuitive,
and thus, additional experiments have to be conducted to draw clear
conclusions.

## References

  * [1] D. Kiela, H. Firooz, A. Mohan, V. Goswami, A. Singh, P. Ringshia, and D. Testuggine, “The hateful memes challenge: Detecting hate speech in multimodal memes,” arXiv preprint arXiv:2005.04790, 2020.
  * [2] A. Borji and L. Itti, “Human vs. computer in scene and object recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 113–120, 2014.
  * [3] J. Shen, C. J. Zhang, B. Jiang, J. Chen, J. Song, Z. Liu, Z. He, S. Y. Wong, P.-H. Fang, and W.-K. Ming, “Artificial intelligence versus clinicians in disease diagnosis: systematic review,” JMIR medical informatics, vol. 7, no. 3, p. e10010, 2019.
  * [4] A. Awasthi and S. Sarawagi, “Continual learning with neural networks: A review,” in Proceedings of the ACM India Joint International Conference on Data Science and Management of Data, pp. 362–365, 2019.
  * [5] G. Stuart, N. Spruston, and M. Häusser, Dendrites.  Oxford University Press, 2016.
  * [6] T. Branco and M. Häusser, “The single dendritic branch as a fundamental functional unit in the nervous system,” Current opinion in neurobiology, vol. 20, no. 4, pp. 494–502, 2010.
  * [7] A. Losonczy, J. K. Makara, and J. C. Magee, “Compartmentalized dendritic plasticity and input feature storage in neurons,” Nature, vol. 452, no. 7186, pp. 436–441, 2008.
  * [8] M. London and M. Häusser, “Dendritic computation,” Annu. Rev. Neurosci., vol. 28, pp. 503–532, 2005.
  * [9] N. Spruston, “Pyramidal neurons: dendritic structure and synaptic integration,” Nature Reviews Neuroscience, vol. 9, no. 3, pp. 206–221, 2008.
  * [10] S. Chavlis and P. Poirazi, “Drawing inspiration from biological dendrites to empower artificial neural networks,” Current Opinion in Neurobiology, vol. 70, pp. 1–10, 2021.
  * [11] C. V. Nguyen, A. Achille, M. Lam, T. Hassner, V. Mahadevan, and S. Soatto, “Toward understanding catastrophic forgetting in continual learning,” arXiv preprint arXiv:1908.01091, 2019.
  * [12] N. Y. Masse, G. D. Grant, and D. J. Freedman, “Alleviating catastrophic forgetting using context-dependent gating and synaptic stabilization,” Proceedings of the National Academy of Sciences, vol. 115, no. 44, pp. E10467–E10475, 2018.
  * [13] Z. Li and D. Hoiem, “Learning without forgetting,” IEEE transactions on pattern analysis and machine intelligence, vol. 40, no. 12, pp. 2935–2947, 2017\.
  * [14] H. Shin, J. K. Lee, J. Kim, and J. Kim, “Continual learning with deep generative replay,” arXiv preprint arXiv:1705.08690, 2017.
  * [15] J. Kirkpatrick, R. Pascanu, N. Rabinowitz, J. Veness, G. Desjardins, A. A. Rusu, K. Milan, J. Quan, T. Ramalho, A. Grabska-Barwinska, et al., “Overcoming catastrophic forgetting in neural networks,” Proceedings of the national academy of sciences, vol. 114, no. 13, pp. 3521–3526, 2017.
  * [16] F. Zenke, B. Poole, and S. Ganguli, “Continual learning through synaptic intelligence,” in International Conference on Machine Learning, pp. 3987–3995, PMLR, 2017.
  * [17] D. Maltoni and V. Lomonaco, “Continuous learning in single-incremental-task scenarios,” Neural Networks, vol. 116, pp. 56–73, 2019.
  * [18] G. M. van de Ven, Z. Li, and A. S. Tolias, “Class-incremental learning with generative classifiers,” arXiv preprint arXiv:2104.10093, 2021.
  * [19] P. Bashivan, M. Schrimpf, R. Ajemian, I. Rish, M. Riemer, and Y. Tu, “Continual learning with self-organizing maps,” arXiv preprint arXiv:1904.09330, 2019.
  * [20] G. M. Van de Ven and A. S. Tolias, “Three scenarios for continual learning,” arXiv preprint arXiv:1904.07734, 2019.
  * [21] T. Kohonen, “Essentials of the self-organizing map,” Neural networks, vol. 37, pp. 52–65, 2013.
  * [22] N. Liu, J. Wang, and Y. Gong, “Deep self-organizing map for visual classification,” in 2015 international joint conference on neural networks (IJCNN), pp. 1–6, IEEE, 2015.
  * [23] S. Aly and S. Almotairi, “Deep convolutional self-organizing map network for robust handwritten digit recognition,” IEEE Access, vol. 8, pp. 107035–107045, 2020.
  * [24] A. Nakagawa and A. Kutics, “Classification in big image datasets using layered-som,” in 2017 13th International Conference on Signal-Image Technology & Internet-Based Systems (SITIS), pp. 143–150, IEEE, 2017.
  * [25] M. Cottrell, M. Olteanu, F. Rossi, and N. Villa-Vialaneix, “Theoretical and applied aspects of the self-organizing maps,” in Advances in self-organizing maps and learning vector quantization, pp. 3–26, Springer, 2016\.
  * [26] D. Rolnick, A. Ahuja, J. Schwarz, T. P. Lillicrap, and G. Wayne, “Experience replay for continual learning,” arXiv preprint arXiv:1811.11682, 2018.
  * [27] A. Chaudhry, M. Rohrbach, M. Elhoseiny, T. Ajanthan, P. K. Dokania, P. H. Torr, and M. Ranzato, “Continual learning with tiny episodic memories,” in Proceedings of the 36th International Conference on Machine Learning, Long Beach, California, PMLR 97, 2019.
  * [28] M. Mermillod, A. Bugaiska, and P. Bonin, “The stability-plasticity dilemma: Investigating the continuum from catastrophic forgetting to age-limited learning effects,” Frontiers in psychology, vol. 4, p. 504, 2013.
  * [29] R. S. M. Barros and S. G. T. C. Santos, “A large-scale comparison of concept drift detectors,” Information Sciences, vol. 451, pp. 348–370, 2018.
  * [30] Y. LeCun, “The mnist database of handwritten digits,” http://yann. lecun. com/exdb/mnist/, 1998.
  * [31] H. Xiao, K. Rasul, and R. Vollgraf, “Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms,” arXiv preprint arXiv:1708.07747, 2017.
  * [32] A. Krizhevsky and G. Hinton, Learning multiple layers of features from tiny images.  University of Toronto, 2009.