# Calculated Attributes of Synonym Sets

Andrew Krizhanovsky, Alexander Kirillov  Institute of Applied Mathematical
Research of the Karelian Research Centre of the Russian Academy of Sciences
Petrozavodsk, Karelia, Russia
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

The goal of formalization, proposed in this paper, is to bring together, as
near as possible, the theoretic linguistic problem of synonym conception and
the computer linguistic methods based generally on empirical intuitive
unjustified factors. Using the word vector representation we have proposed the
geometric approach to mathematical modeling of synonym set (synset). The word
embedding is based on the neural networks (Skip-gram, CBOW), developed and
realized as word2vec program by T. Mikolov. The standard cosine similarity is
used as the distance between word-vectors. Several geometric characteristics
of the synset words are introduced: the interior of synset, the synset word
rank and centrality. These notions are intended to select the most significant
synset words, i.e. the words which senses are the nearest to the sense of a
synset. Some experiments with proposed notions, based on RusVectores
resources, are represented.

##  I Introduction

The notion of synonym, though it is in common use, has no rigorous definition
and is characterized by different approaches. The descriptive definition runs
as follows: the synonyms are the words expressing the same notion, identical
or close in the sense, differing from each other in shades of meanings,
belonging to different linguistic levels, having their own specific expressive
tone.

This definition immediately raises several questions: what are the meanings of
notion, sense and so on. Hence it is necessary to develop and introduce a
formalization, which would enable to use quantitative analysis and
characteristics for description of the relations between words. Such
formalization is particularly significant in the natural language processing
problems.

In this paper, the approach to a synset mathematical modeling is proposed. The
notion of synset (a set of synonyms) owes its occurrence to WordNet where
different relations (synonymy, homonymy) are indicated between synsets but not
between individual words [12]. For this research the synonyms presented by
Russian Wiktionary have been used. Russian Wiktionary is a freely updated
collaborative multifunctional multilingual online dictionary and thesaurus.
Machine-readable Wiktionary, which we use in this paper, is regularly updated
with the help of wikokit111https://github.com/componavt/wikokit software on
the base of Russian Wiktionary data [5].

The authors of this paper represent the approach to the partial solution of
the following problems:

  * •

the automatic ordering of the synonyms in a synset according to the proximity
of the words to the sense represented by synset;

  * •

the developing of mathematical tool for analysis, characterization and
comparison of synsets and its experimental verification using the online-
dictionary data (Russian Wiktionary);

  * •

the detection, on the basis of the developed mathematical tool (in future
investigation), of the "weak" synsets in order to improve the dictionaries;

  * •

the significant problem, which has incented the authors to turn to this paper,
is the word sense disambiguation (WSD). Our main task is to combine the neural
networks and the proposed methods to solve the WSD problem at more qualitative
level in comparison with existing methods [1].

##  II The word vector representation: the brilliance and the poverty of NN-
models construction by word2vec tool

The idea of a word representation, using neural networks (NN), as a vector in
some vector space has enjoyed wide popularity due to Skip-gram and CBOW
constructions, proposed by T. Mikolov and his colleagues [9, 10, 11]. The main
advantage of these NN-models is their simplicity and possibility of their
usage with the help of such available instrument as word2vec developed also by
T.Mikolov’s group on the basis of text corpora. It is worth to note, from our
point of view, that the significant contribution to this field of computer
linguistics has been made by the Russian scientists – A. Kutuzov and E.
Kuzmenko, who have developed, by the aid of word2vec, the NN-models for
Russian language, using several corpora. They called the proposed tool
RusVectores [6].

The "poverty" of Mikolov’s approach consists in rather confined possibilities
of its applicability to finding out the meaningful pairs of semantic
relations. One of the most bright examples of word2vec is the well-known
($queen-woman+man\approx king$) is not supported by other expressive
relations. The slightest deviations from the examples, representing
satisfactory illustrations of the Mikolov’s approach, lead to poor results.
The lack of a formal justification of the Mikolov’ approach was pointed out in
the recent paper of Goldberg and Levy [2], which ends with the following
appeal to researchers

> "Can we make this intuition more precise? We’d really like to see something
> more formal" [2].

The presented paper, to some degree, is the partial response to this challenge
of the well-known researchers in the computer linguistics.

Let us consider the main idea of the word vector representation. Denote by $D$
some dictionary and enumerate in some way its words. Let $|D|$ be the number
of the words in $D$, $i$ — the index number of a word in the dictionary.

###### Definition 1

The vector dictionary is the set $D=\\{w_{i}\in\mathbb{R}^{|D|}\\}$, where the
$i$-th component of a vector $w_{i}$ equals 1, while the other components are
zeros.

Thus, $w_{i}$ is the image of the $i$-th word in $D$. The problem of the word
vector representation, as it is understood at present, is to construct a
linear mapping $L:D\rightarrow\mathbb{R}^{N}$, where $N<<|D|$, and vector
$v=L(w),w\in D$, $v$ has components $v_{j}\in\mathbb{R}$. These procedure is
called the distributed word vector representation. Its goal is to replace very
thin set $D\in\mathbb{R}^{|D|}$, consisting of vectors with zero mutual inner
(scalar) product, by some subset of $\mathbb{R}^{N}$, where $N<<|D|$, with the
following property: the inner products of vectors from $\mathbb{R}^{N}$ may be
used as a measure of the words similarity, which is currently accepted in the
corresponding problems of nature language processing. If $W$ is a matrix of
such linear mapping $L$ then $v=Ww$ for $v\in\mathbb{R}^{N}$. In addition
several methods, particularly based on neural networks, are used to construct
$W$. Recently, CBOW and Skip-gram methods has become widely used. Their
mathematical basis is the modified maximum likelihood method.

For instance, the Skip-gram NN-model provides the matrix $W$, mentioned above,
as the matrix which maximizes the following function $F(W)$

$F(W)=\frac{1}{T}\sum_{t=1}^{T}\sum_{-c\leq j\leq c,j\neq 0}\ln
p(w_{t+j}|w_{t})$ $p(w_{t+j}|w_{t})=\frac{\exp u_{t+j}}{\sum_{i=1}^{|D|}\exp
u_{i}},\qquad u_{i}=(Ww_{i},Ww_{t})$

where $(\cdot,\cdot)$ — the symbol of inner product, $T$ — the volume of
training context. Here, a word $w_{t}$ is given in order to find out the
appropriate context, containing this word and having the size $2c$ (the size
of the "window"). The CBOW (continuous bag of words) NN-model, on the
contrary, operates with some given context and provide an appropriate word.
These model take into account only local context. There exist some attempts to
use global context (the whole document) [4]. Such approach would be useful for
solving the problems of WSD.

##  III The synset geometry

###  III-A The synset interior: IntS

The distance between word-vectors (normalized) is measured by their inner
product, i.e. by the angle between them, as in the theory of projective
spaces. Thus, the increasing of inner product corresponds to decreasing of the
distance $sim\\{a,b\\}$ (similarity) between vector-words
$a,b\in\mathbb{R}^{N}$. Hence, $sim\\{a,b\\}=\frac{(a,b)}{||a||\cdot||b||}$,
where $(a,b)$ is the inner product of vectors $a$ and $b$, $||\cdot||$ is the
norm symbol. There are proposed some other measures of a distance between the
vectors but they are based on the inner product [7], [8], [13].

Let us introduce designations for normalized sum of vectors:
$M((a_{i}),n)=\frac{\sum_{i=1}^{n}a_{i}}{||\sum_{i=1}^{n}a_{i}||}$. In what
follows, the distance between the sets of vectors will be measured by the
distance between normalized mean vectors of the sets. Thus, if
$A=\\{a_{1},...,a_{n}\\}$ and $B=\\{b_{1},...,b_{m}\\}$,
$a_{i},b_{j}\in\mathbb{R}^{N}$, then
$sim\\{A,B\\}=(M((a_{i}),n),(M((b_{j}),m)))$.

Consider a synset $S=\\{v_{k},k=1,...,|S|\\}$. Let us remove any word $v$ from
$S$ (the index of a word is omitted for brevity). Divide the set
$S\setminus\\{v\\}$ into two disjunctive subsets:
$S\setminus\\{v\\}=\\{v_{i_{s}}\\}\sqcup\\{v_{j_{p}}\\},$ $s=1,...,q,$
$p=1,...,r,$ $q+r=|S|-1,\ i_{s}\neq j_{p}$. Denote
$S_{1}=\\{v_{i_{s}}\\},S_{2}=\\{v_{j_{p}}\\}$. Then
$S\setminus\\{v\\}=S_{1}\cup S_{2}$.

###### Definition 2

The interior $IntS$ of a synset $S$ is the set of all vectors $v\in S$
satisfying the following condition

$\begin{split}IntS=\\{v\in S:\ &sim\\{S_{1},S_{2}\\}<sim\\{S_{1}\cup
v,S_{2}\\}\ \bigwedge\\\ &sim\\{S_{1},S_{2}\\}<sim\\{S_{1},S_{2}\cup
v\\}\\}\end{split}$ (1)

for all disjunctive partitions $S\setminus\\{v\\}=S_{1}\sqcup S_{2}$, where
$S_{1}\neq\varnothing,\ S_{2}\neq\varnothing$.

The sense of this definition: the addition of the vector $v\in IntS$ to any of
two subsets of $S\setminus\\{v\\}$, forming its disjunctive partition,
decreases the distance between these subsets (i.e. increases the similarity).

To illustrate the notion of $IntS$, consider two-dimensional vectors. In Fig.
1 vector $v$ (conditionally shown as a circle), added to $S_{1}$ or $S_{2}$,
decreases the distance between $S_{1}$ and $S_{2}$.

Figure 1: Vector $v$ decreases the distance between $S_{1}$ and $S_{2}$. If it
occurs for all disjunctive partitions of $S\setminus\\{v\\}$ then $v\in IntS$

###  III-B Rank and centrality of a word in synset

Let us introduce the notion of the rank of a synonym $v\in S$. In what follows
we consider only disjunctive partitions and thus, for brevity, the disjunctive
partition into two subsets, the elements of partition, we shall call the
partition. Let $P_{v}=\\{p_{i},i=1,...,2^{n-2}-1\\}$ be the set of all
enumerated in some way partitions $p_{i}$ of the set $S\setminus\\{v\\}$,
where $|S|=n$. Here $|S|$ is the power (the number of elements) of $S$.
Suppose $n>2$. Consider any partition $p_{i}$ of the set $S\setminus\\{v\\}$:
$S\setminus\\{v\\}=S_{1}\sqcup S_{2}$. Denote $sim_{i}=sim\\{S_{1},S_{2}\\}$,
$sim^{1}_{i}=sim\\{S_{1}\cup v,S_{2}\\}$, $sim^{2}_{i}=sim\\{S_{1},S_{2}\cup
v\\}$. Using these designations, we obtain

$IntS=\\{v\in S:sim_{i}<sim^{1}_{i}\ \wedge\ sim_{i}<sim^{2}_{i}\\}$ (2)

Introduce the function $r_{v}:P_{v}\rightarrow\\{-1,0,1\\}$ such that

$r_{v}(p_{i})=\begin{dcases}\ \ -1,&sim^{1}_{i}<sim_{i}\bigwedge
sim^{2}_{i}<sim_{i},\\\ &v\ \text{moving apart of}\ S_{1}\ \text{from}\
S_{2}\\\\[8.61108pt] \ \ 1,&sim^{1}_{i}>sim_{i}\bigwedge
sim^{2}_{i}>sim_{i},\\\ &v\ \text{approaching of}\ S_{1}\ \text{and}\
S_{2}\\\\[8.61108pt] \ \
0,&(sim^{1}_{i}-sim_{i})\cdot(sim^{2}_{i}-sim_{i})<0.\\\
&\text{approaching}-\text{moving apart}\end{dcases}$ (3)

The function $r_{v}$ is determined for each partition and gives,
metaphorically speaking, the "bricks" which will below compose the rank of a
synonym. Let us briefly explain approaching-moving apart line of the above
definition of $r_{v}$. The expression
$(sim^{1}_{i}-sim_{i})\cdot(sim^{2}_{i}-sim_{i})<0$ is equivalent to
$(sim^{1}_{i}<sim_{i}\wedge
sim^{2}_{i}>sim_{i})\bigvee(sim^{1}_{i}>sim_{i}\wedge sim^{2}_{i}<sim_{i})$.
In other words, the function $r_{v}(p_{i})$ has the value $0$, if the adding
of a word $v$ to one of the elements of a partition $p_{i}$ decreases
(increases) the distance $sim_{i}$, but the adding to another element
increases (decreases), on the contrary, the distance $sim_{i}$. In Fig. 2 this
is 3 partition.

###### Definition 3

The rank of a synonym $v\in S$, where $|S|>2,$ is the integer of the form

$rank\ (v)=\sum_{i=1}^{|P_{v}|}r_{v}(p_{i}).$ (4)

The definition implies that if $v\in IntS$ then $rank\ (v)=2^{|S|-2}-1$ is the
number of all nonempty disjunctive partitions of $S\setminus\\{v\\}$ into two
subsets, where $|S\setminus\\{v\\}|=|S|-1$, i.e. $rank\ (v)$ has maximum and
equals to the Stirling number of the second kind: $\textstyle\\{{n\atop
k}\\}=\\{{|S|\atop 2}\\}$, where $n$ is the number of elements in the set and
$k$ is the number of the subsets in a partition, here $k=2$ [3, p. 244].

The relation between $IntS$ and $rank\ (v)$ is given by the following

######  Theorem III.1 (IntS theorem)

Assume $|S|>2$. Then $v\in IntS$ if and only if the rank of a word $v$ is
maximal in a given synset and equals to the Stirling number of the second kind
for partition of $S$ into two nonempty subsets, i.e.

$v\in IntS\Leftrightarrow rank\ (v)=2^{|S|-2}-1,\ \ \text{where}\ |S|\geqslant
3,$

###### Proof:

$v\in IntS\mathrel{\mathop{\Leftrightarrow}^{\mathrm{(2)}}}\forall
p_{i}:IntS=\\{v\in S:sim^{1}_{i}>sim_{i}\\\ \wedge\ sim^{2}_{i}>sim_{i}\\}\ \
(v\ \text{approaching of}\ S_{1}\ \text{and}\ S_{2})\ \
\mathrel{\mathop{\Leftrightarrow}^{\mathrm{(3)}}}\\\ \forall
p_{i}:r_{v}(p_{i})=1\mathrel{\mathop{\Leftrightarrow}^{\mathrm{(4)}}}\\\ rank\
(v)=\sum_{i=1}^{|P_{v}|}1=|P_{v}|=2^{|S|-2}-1.$ (5)

since $2^{|S|-2}-1$ — is the maximal number of nonempty disjunctive partitions
into two subsets. ∎

###### Definition 4

The centrality of a synonym $v\in S$ under a partition $p_{i}$ of
$S\setminus\\{v\\}$ is the following value

$centrality(v,p_{i})=(sim^{1}_{i}(v)-sim_{i})+(sim^{2}_{i}(v)-sim_{i})$

###### Definition 5

The centrality of a synonym $v\in S$ is the following value

$centrality(v)=\sum_{i=1}^{|P_{v}|}centrality(v,p_{i})$

Hypothesis 1: it is worth to note, that the word $v$, belonging to $IntS$, has
the greater rank and centrality than the other words of a synset $S$. It is
likely that the rank and the centrality show the measure of significance of a
word in a synset, i.e. the measure of proximity of this word to the synset
sense. Since the centrality is a real number it gives more precise
characteristic of a word significance in a synset than the rank which is
integer (see the table 1).

Figure 2: The values of rank and centrality for the word "combat" in synset
$S=\\{battle,engagement,fight,combat\\}$. Three possible partitions of the set
$S\setminus\\{combat\\}=\\{battle,engagement,fight\\}$ into two nonempty
subsets, $S_{1}^{i},S_{2}^{i},i=1,2,3$, are presented. For the brevity,
$S_{1}^{i},S_{2}^{i}$ are denoted as $S_{1},S_{2}$ respectively. The values of
$rank(v)$ and $centrality(v)$, $v=\\{combat\\}$ are calculated as the sums of
appropriate $\Delta rank_{i}:=rank(v,p_{i})$ and $\Delta
centrality_{i}:=centrality(v,p_{i})$.

###  III-C Rank and centrality computations

The definition of centrality implies the following centrality computation
Procedures 1 and 2.

Hypothesis 2: the more meanings has the word the less is its rank and
centrality in different synsets.

The following example and table 1 support this hypothesis. It is worth to note
that this example is not exclusive. The verification of the hypothesis on the
large amount of data is the substance of future research.

Procedure 1 Computation of rank $r_{v}(p_{i})$ and $centrality(v,p_{i})$ of a
word $v$ and a correspondent partition $p_{i}$ of the synset $S$

0: a synset $S$, a word $v\in S$ and any correspondent partition $p_{i}$ of
$S\setminus\\{v\\}$;

0: $S\setminus\\{v\\}=S_{1}\sqcup S_{2}$;

0: $r_{v}(p_{i})$, $centrality(v,p_{i})$.

1: $sim_{i}\leftarrow sim\\{S_{1},S_{2}\\}$

2: $sim^{1}_{i}(v)\leftarrow sim\\{S_{1}\cup v,S_{2}\\}$ // adding of a word
$v$ to $S_{1}$

3: $sim^{2}_{i}(v)\leftarrow sim\\{S_{1},S_{2}\cup v\\}$ // adding of a word
$v$ to $S_{2}$

4:
$centrality(v,p_{i})\leftarrow(sim^{1}_{i}(v)-sim_{i})+(sim^{2}_{i}(v)-sim_{i})$

5: $r_{v}(p_{i})\leftarrow 1/2\cdot(\text{sgn}(sim^{1}_{i}(v)-sim_{i})+$
$\phantom{r_{v}(p_{i})\leftarrow
1/2\cdot(}\text{sgn}(sim^{2}_{i}(v)-sim_{i}))$, where
$\text{sgn}(x)=\begin{cases}\ \ 1,&x>0\\\ \ \ 0,&x=0\\\ -1,&x<0\end{cases}$

6: return $r_{v}(p_{i})$, $centrality(v,p_{i})$

Procedure 2 Computation of $rank(v)$ and $centrality(v)$ of a word $v$ of the
synset $S$

0: a synset $S$, a word $v\in S$;

0: $rank(v)$, $centrality(v)$.

1: $centrality(v)\leftarrow\sum_{i=1}^{|P_{v}|}centrality(v,p_{i})$,

2: $rank(v)\leftarrow\sum_{i=1}^{|P_{v}|}r_{v}(p_{i})$.

3: return $rank(v)$, $centrality(v)$

###### Example 1

Let us consider the synset $S$ = (battle, combat, fight, engagement). Let us
find out $IntS$ and calculate the rank and the centrality of each word in
synset.

The example of calculating of rank and centrality of the word "combat" in this
synset is shown in Fig. 2. The set of power $|S\setminus\\{v\\}|=3$ may be
decomposed in three ways into two nonempty subsets. Each partition may add 1,
0 or -1 to $rank(v)$ (Fig. 2). The values of rank and centrality equals 2 and
0,36, respectively.

In table. 1 the rank, the centrality and $IntS$ for the words of the synset
are shown.

Table I: Rank and centrality of each word in synset, the belongings of synonym
to IntS is shown

Russian synset
---

баталия & бой битва сражение Transliteration batálija boj bítva sražénije
Translation fight combat battle engagement Centrality -0.12 0.34 0.45 0.6 Rank
-3 2 3 3 IntS — — + +  Note. The precise translation of the synset’ words is a
rather difficult task. The translation serves only to illustrate the model.

According to above Theorem III.1, the rank of the synonyms belonging to the
synset interior, $IntS$, equals 2^|S|-2-1 = 2^|4|-2-1 = 3 Table 1 shows that
the words "battle" and "engagement" have the largest rank (3) and centrality.
Thus, $Int$ (battle, engagement, fight, combat) = (battle, engagement). It
means that this pair, battle and engagement, is the most close in sense to all
words of the synset.

Rank and centrality in this example were calculated on the basis of data from
Russian National Corpus.

##  IV Experiments

Table II: Examples of synsets with empty IntS. The synsets were taken from Russian Wiktionary. The words in synsets are ordered by rank and centrality. Two Russian corpora from the project $RusVect\bar{o}r\bar{e}s$ were used to construct NN-models. These models were used to find out $IntS$, here $OutS=S\setminus IntS$ | Russian
---
Wiktionary
article
Synset (from article) | $||S||$ | $||IntS||$ | Corpus
Adverb
| beautifully
---
(прекрасно)
|  $IntS=\varnothing$,
---
$OutS=\\{wonderfully,remarkably,excellently,perfectly,beautifully\\}$
5 | 0 | RNC
| beautifully
---
(прекрасно)
|  $IntS=\\{perfectly,remarkably\\}$,
---
$OutS=\\{wonderfully,beautifully,excellently\\}$
5 | 2 | News
Adjective
| stony
---
(каменный)
|  $IntS=\varnothing$,
---
$OutS=\\{stony,heartless,hard,cruel,pitiless\\}$
5 | 0 | RNC
| stony
---
(каменный)
|  $IntS=\\{pitiless\\}$,
---
$OutS=\\{stony,heartless,hard,cruel\\}$
5 | 1 | News

In this paper we use the NN-models, created by the authors of the project
$RusVectores$ [6], namely, the model constructed on the basis of the texts of
the Russian National Corpus (RNC), and the model, constructed on the basis of
the texts of the Russian news sites (News corpus). These model are available
on the site of the project $RusVectores$ [6].

The authors of $RusVectores$, A. Kutuzov and E. Kuzmenko, pay attention to
such peculiarities of RNC as hand typesetting of the texts for the corpus
updating, the regulation of the different genres text relations, the small
size of the main corpus, approximately, 107 million of words (for example, the
News corpus consists of 2,4 billion of tokens).

In [6] the notion of corpus representativeness is introduced. The sense of
this notion is the ability of the corpus to reflect (to point at) those
association for a word which will be accepted by the majority of the native
language speakers. The associations generated by NN-models according to the
data from RNC and Web-corpus are just used in this paper. The problem of
comparison is reduced to finding out the words which meanings in Web-corpus
essentially differ from that in RNC. Let us take into account that for each
word in corpus, via NN-model, we can obtain the list of $N$ nearest words
(remind: a word is a vector). Then, the result of the corpora comparison is as
follows: for more than a half of all the words (the common words in two
corpora) not less than three words of the nearest ten words were the same [6].
It means that the linguistic world images, created on the basis of RNC and
Internet texts, have a lot in common. But the opposite estimation is also
necessary: what is the measure of discrepancy of the NN-models?

Let us note that the notion of corpus representativeness acquires the new
significance in view of the NN-models created on the basis of the corpus. An
unbalanced sample results in excess weight of some corpus topics and as
consequence to a less exact NN-model.

It is significant for future experiments the following observation in [6]. For
the rare words, presented by the small set of contexts related to this word,
the associative words, generated by NN-models, will be inexact and doubtful.

We have conducted the experiments for testing the proposed synset model. We
have used two NN-models, constructed by the authors of $RusVectores$ on the
basis of RNC and News corpus. While operating with NN-models we used the
program gensim222http://radimrehurek.com/gensim/, because it contains the
realization of word2vec in Python language. The gensim program is presented in
[14]. The authors of $RusVectores$ used the gensim program for the NN-models
constructing as well [6].

We developed the number of scripts on the basis of gensim for operating with
NN-models, for calculation of the rank and the centrality and for
determination of $IntS$. These script are available
online333https://github.com/componavt/piwidict/tree/master/lib_ext/gensim_wsd.

For the several thousands of synsets extracted from the Russian Wiktionary the
rank, the centrality and $IntS$ were calculated on the basis of RNC and News
corpus. The experiments have showed that the rare words in corpora have, as a
rule, empty $IntS$. The same word in different NN-models constructed according
to different corpora is presented by different vectors. The different corpora
and NN-models give different word vector representations. Thus, the synset
interior ($IntS$) for the same word could be different (Table II).

##  V Conclusion

The world of modern linguistics may be represented, tentatively speaking, as
the union of two domains, attracting each other but nevertheless weakly bound
nowadays: the traditional, more qualitative, and computational linguistics.
The strict formalization of the base notions is necessary for further
development of linguistics as exact science. The formal definition of such
notions as word meaning, synonymy and others will permit to base, to the right
degree, upon the methods and algorithms of computational linguistics (corpora
linguistics, neural networks, etc.), discrete mathematics, probability theory.

In this paper we present an approach to some formal characterizations ($IntS$,
rank, centrality) of such significant for machine-readable dictionaries and
thesauri notion as the set of synonyms — the synset. The proposed formal tool
permits to analyse the synsets, to compare them, to determine the significance
of the words in a synset.

In future investigations we will use the developed tool to the problem of word
sense disambiguation (WSD problem).

## Acknowledgment

This paper is supported by grant N 18-012-00117 from the Russian Foundation
for Basic Research.

## References

  * [1] T. V. Kaushinis, A. N. Kirillov, N. I. Korzhitsky, A. A. Krizhanovsky, A. V. Pilinovich, I. A. Sikhonina, A. M. Spirkova, V. G. Starkova, T. V. Stepkina, S. S. Tkach, Ju. V. Chirkova, A. L. Chuharev, D. S. Shorets, D. Yu. Yankevich, E. A. Yaryshkina, “A review of word-sense disambiguation methods and algorithms: Introduction”, _Transactions of Karelian Research Centre of Russian Academy of Science, series Mathematical Modeling and Information Technologies_ , 2015, pp. 69–98, doi: 10.17076/mat135, Web: http://journals.krc.karelia.ru/index.php/mathem/article/view/135.
  * [2] Y. Goldberg, O. Levy, “word2vec explained: Deriving Mikolov et al.’s negative-sampling word-embedding method”, _arXiv preprint arXiv:1402.3722_ , 2014, pp. 1–5.
  * [3] R. L. Graham, E. K. Donald and O. Patashnik, _Concrete mathematics_. Addison–Wesley, 1994.
  * [4] E. H. Huang, R. Socher, C. D. Manning, A. Y. Ng, “Improving word representations via global context and multiple word prototypes”, _in Proc. of the ACL ’12_ , Jeju Island, Korea, 2012, pp. 873–882, Web: http://dl.acm.org/citation.cfm?id=2390524.2390645.
  * [5] A. A. Krizhanovsky, A. V. Smirnov, “An approach to automated construction of a general-purpose lexical ontology based on Wiktionary”, _Journal of Computer and Systems Sciences International_ , 2013, N 2, pp. 215–225, doi: 10.1134/S1064230713020068, Web: http://scipeople.com/publication/113533/.
  * [6] A. Kutuzov, E. Kuzmenko, “Comparing neural lexical models of a classic national corpus and a web corpus: the case for Russian”, _Computational Linguistics and Intelligent Text Processing_ , 2015, pp. 47–58, doi: 10.1007/978-3-319-18111-0_4, Web: https://www.academia.edu/11754162/Comparing_neural_lexical_models_of_a_classic_national_corpus_and_a_web_corpus_the_case_for_Russian.
  * [7] O. Levy, Y. Goldberg, I. Dagan, “Improving distributional similarity with lessons learned from word embeddings”, _Transactions of the Association for Computational Linguistics_ , 2015, vol. 3, pp. 211–225.
  * [8] S. Mahadevan, S. Chandar, “Reasoning about linguistic regularities in word embeddings using matrix manifolds”, _arXiv preprint arXiv:1507.07636_ , 2015, pp. 1–9.
  * [9] T. Mikolov, S. Kombrink, L. Burget, J. Cernocky, S. Khudanpur, “Extensions of recurrent neural network language model”, _in Proc. of the 2011 IEEE International Conf. on Acoustics Speech and Signal Processing (ICASSP)_ , 2011, doi: 10.1109/icassp.2011.5947611.
  * [10] T. Mikolov, G. Zweig, “Context dependent recurrent neural network language model”, _in Proc. of the 2012 IEEE Spoken Language Technology Workshop (SLT)_ , 2012, doi: 10.1109/slt.2012.6424228.
  * [11] T. Mikolov, K. Chen, G. Corrado, J. Dean, “Efficient estimation of word representations in vector space”, _arXiv preprint arXiv:1301.3781_ , 2013, Web: http://arxiv.org/abs/1301.3781.
  * [12] Princeton University website, What is WordNet? Web: http://wordnet.princeton.edu.
  * [13] G. Sidorov, A. Gelbukh, H. Gómez-Adorno, D. Pinto, “Soft similarity and soft cosine measure: Similarity of features in vector space model”, _Computación y Sistemas_ , 2014, vol. 18, N 3, pp. 491–504, Web: http://www.scielo.org.mx/pdf/cys/v18n3/v18n3a7.pdf.
  * [14] R. Řehůřek, P. Sojka, “Software framework for topic modelling with large corpora”, _in Proc. of the LREC 2010 Workshop on New Challenges for NLP Frameworks_ , Valletta, Malta: University of Malta, 2010, pp. 45–50, Web: http://is.muni.cz/publication/884893/en.


Pre-print

# Prospect Theory-inspired Automated P2P Energy Trading with Q-learning-based
Dynamic Pricing

Ashutosh Timilsina  Department of Computer Science
University of Kentucky
Lexington, USA
<EMAIL_ADDRESS>Simone Silvestri  Department of Computer Science
University of Kentucky
Lexington, USA
<EMAIL_ADDRESS>
###### Abstract

The widespread adoption of distributed energy resources, and the advent of
smart grid technologies, have allowed traditionally passive power system users
to become actively involved in energy trading. Recognizing the fact that the
traditional centralized grid-driven energy markets offer minimal profitability
to these users, recent research has shifted focus towards decentralized peer-
to-peer (P2P) energy markets. In these markets, users trade energy with each
other, with higher benefits than buying or selling to the grid. However, most
researches in P2P energy trading largely overlook the user perception in the
trading process, assuming constant availability, participation, and full
compliance. As a result, these approaches may result in negative attitudes and
reduced engagement over time. In this paper, we design an automated P2P energy
market that takes user perception into account. We employ prospect theory to
model the user perception and formulate an optimization framework to maximize
the buyer’s perception while matching demand and production. Given the non-
linear and non-convex nature of the optimization problem, we propose
Differential Evolution-based Algorithm for Trading Energy called $DEbATE$.
Additionally, we introduce a risk-sensitive Q-learning algorithm, named
Pricing mechanism with Q-learning and Risk-sensitivity ($PQR$), which learns
the optimal price for sellers considering their perceived utility. Results
based on real traces of energy consumption and production, as well as
realistic prospect theory functions, show that our approach achieves a $26\%$
higher perceived value for buyers and generates $7\%$ more reward for sellers,
compared to a recent state of the art approach.

###### Index Terms:

Peer-to-peer energy trading, differential evolution, dynamic pricing,
prosumer, prospect theory, Q-learning.

††publicationid: pubid:  978-1-6654-3540-6/22/$31.00 © 2022 IEEE

##  I Introduction

Distributed Energy Resources (DER), such as rooftop solar and wind turbine,
have seen widespread proliferation among consumers in recent years[1]. In
addition, the advent of Smart Grid (SG) technologies, Advanced Metering
Infrastructures (AMI), and home energy management systems, have added
flexibility in energy generation/consumption for consumers. This, in turn, has
allowed traditionally passive consumers to become actively involved in energy
trading by sharing the excess energy generated at their premise to either grid
or other buyers [2, 3]. These active consumers with energy production
capabilities have been referred to as prosumers [3], as a portmanteau of
“producers” and “consumers”. The role of prosumers in energy market has been
recognized to some extent with the adoption of incentive schemes like Feed-in-
Tariff (FiT) mechanism [4, 5]. FiT allows prosumers to sell excess energy to
the grid and buy from grid when required [5]. However, existing energy trading
modalities offer limited benefits to participating prosumers. This is due to
the minimal prices at which energy is purchased by grid, as well as the low
limits on the amount of energy that can be purchased [4, 5, 3].

###  I-A Literature Review and Motivation

Peer-to-peer (P2P) energy trading is a recently proposed decentralized
modality for energy sharing aiming at solving limitations of centralized
techniques. This modality has been gaining significant traction recently [5,
4]. Specifically, P2P energy trading allows prosumers to trade energy among
each other at a negotiated price with or without the involvement of the grid
[4]. It generates better monetary incentives for prosumers compared to
existing mechanisms while also reducing their grid dependency [5].
Additionally, increased local energy generation/consumption resulting from P2P
trading leads to the minimization of overall system energy loss while
providing an effective way to achieve demand side management[6]. Benefits
extend also to the grid operator, by providing savings in investments that
would have been otherwise required to develop/maintain transmission
infrastructure in a centralized power distribution architecture [3, 4].

P2P energy trading has received attention from the research community in
recent years. The works in [7, 8] present game theoretic approaches in a P2P
setting, while a greedy rule-based P2P mechanism to assign energy among
prosumers is proposed in [9] that includes mid-market pricing. Similarly, the
physical aspects of P2P energy trading, such as power loss minimization and
voltage regulation, have been explored in [10, 11]. These works, however,
largely overlook the user behavior in designing their solutions. As
established in [3, 5, 2], accommodating the user behavioral modeling in P2P
energy trading ensures sustained participation from prosumers while
incentivizing their contribution. In fact, the papers [7, 8] consider
prosumers to be actively involved and fully compliant with the system as
rational decision-makers. First concern with this assumption is that the
continuous online presence of participating prosumers with the system might
not always be possible in real-world application. Secondly, research on user
behavioral models and decision making [12, 13] have found users to have
bounded rationality. Therefore, requiring constant active participation
overwhelms the users and incentivizes non-rational decisions [14]. In the
worst case, it might even result in users opting to terminate their
participation altogether [13, 2]. In that light, the works in [2, 15]
incorporates bounded rationality and user preferences into P2P energy trading.
However, it requires continuous human participation and assumes a simplistic
linear model for user perception. Conversely, the authors of [5] limit their
focus on coalition formation in game theoretic setting and do not explicitly
consider user behavioral modeling.

As a result, a prosumer-centric P2P energy trading model, that effectively
incorporates the prosumers’ decision-making behavior and their perceived
loss/gain value from trading, is still lacking in the existing literature.
Such a trading modality is expected to require minimal active participation
from users while also ensuring their sustained involvement through the
adoption of user behavioral modeling. To this end, the framework of Prospect
Theory (PT) [16] can be used to model the non-rational user behavior in the
face of uncertain decision-making. It is often regarded as fairly accurate
mathematical representation of human behavior [16, 17, 18].

Recently, there has been few efforts in integrating PT in energy related
applications as well to capture the irrationality of users [19, 18, 20, 21].
In relation to P2P energy trading, the authors in [21] have proposed a PT-
based distributed energy trading model to optimize trading decisions for
prosumers in a competitive market. Although these papers model the user
behavior in some ways, they require active participation from users and also
assume that such behavior (e.g., the parameters of PT) is homogeneous for all
the users. Social science studies, such as the one conducted in Italy [22] to
investigate the social acceptance of nuclear energy using an online survey,
show that users exhibit significant heterogeneity in their preferences for the
sources of energy. Neuroscience studies have also stressed the heterogeneity
of humans in reference to PT parameters [23]. Not capturing such heterogeneity
provides little benefits in terms of user behavioral modeling.

###  I-B Paper Contributions

In this paper, we design a PT-based optimization framework for prosumer-
centric P2P energy trading as shown in Fig. 1. The framework aims at matching
energy production and consumption (step $1$ in Fig. 1) to maximize the
perceived utility of individual buyers while taking into account the intrinsic
heterogeneity of human perception. Given that the optimization problem is non-
linear and non-convex, we further devise a Differential Evolution-based [24]
metaheuristic algorithm called $DEbATE$ to solve the problem (energy
allocation, step $2$). In order to ensure minimal active participation of
prosumers, we employ a Reinforcement Learning (RL) framework, called $PQR$, in
tandem with $DEbATE$ to automate the pricing mechanism for sellers (pricing
mechanism, step $3$). In doing so, $PQR$ learns the selling price for each
sellers using a PT-based risk-sensitive Q-learning algorithm [25]. The output
of the algorithms is then returned to the prosumers for executing the physical
energy transactions (step $4$). Using real datasets for energy production and
consumption, paired with recent survey data for PT perception modeling,
results show that $DEbATE$ performs $25\%$ higher in buyer’s perception and
$7\%$ higher in seller’s reward compared to state-of-the-art approach.

The major contributions of the paper are the following:

  * •

We develop a PT-inspired optimization framework for P2P energy trading;

  * •

We design a metaheuristic algorithm $DEbATE$ to solve the non-linear energy
allocation problem;

  * •

We design dynamic pricing mechanism with $PQR$ algorithm using risk-sensitive
Q-learning approach;

  * •

Experiments using real data show the superiority of proposed approach compared
to the state-of-the-art;

Figure 1: P2P Energy Trading System Overview.

##  II System Model and Problem Formulation

We consider a P2P energy trading system as shown in Fig. 1. The system
consists of prosumers that can exchange energy among each other through an
existing distribution network. The grid serves as backup for prosumers to
either buy or sell energy, if the local energy trading is insufficient or not
possible. Let $P$ be the set of all prosumers participating in the P2P energy
market. We refer to $B_{t}\subset P$ as the set of Buyers, i.e. the set of
prosumers that have higher self-consumption than generation at a timeslot $t$,
and consumers without energy generation capabilities. Similarly, $S_{t}\subset
P$ is the set of Sellers, i.e., prosumers that have excess generation at a
timeslot $t$. For simplicity of notation, we drop the subscript $t$ in the
following.

We model the perceived loss and gain of prosumers using the prospect theory
(PT) value function to capture user perception on gains and losses.
Specifically, consider the excess energy generation of seller $i\in S$ be
$r_{i}$ and demand of buyer $j\in B$ be $w_{j}$. Then, let $x_{ij}\in[0,1]$
represent the fraction of $w_{j}$ that a buyer $j$ is willing to buy from
seller $i$ at $\rho_{i}$ price per $kWh$ amount of energy. There is an energy
loss during the physical energy transfer through wires [6], which depends on
the wire-length between $i$ and $j$ and directly proportional to the amount of
energy exchanged. The loss is modeled as a fraction $l_{ij}\in[0,1]$ of the
energy exchanged. Assume $\rho_{gs},\rho_{gb}$ be the energy selling and
purchasing prices from the grid. We adopt a modified PT value function to
model realistic user perception in an energy market [16]. The function
quantifies perceived utility of humans towards gain and loss based on degree
of deviation from a reference point. Particularly, in our problem, it captures
the difference of total actual buying cost $y_{j}$ from the buyer’s desired
total reference cost $\rho_{j}w_{j}$ where $\rho_{j}$ is the reference price
of buyer $j$ for purchasing energy. This utility function is formulated as

$v(y_{j})=\begin{cases}k_{+,j}(\rho_{j}w_{j}-y_{j})^{\zeta_{+,j}},&y_{j}<\rho_{j}w_{j}\\\
-k_{-,j}(y_{j}-\rho_{j}w_{j})^{\zeta_{-,j}},&y_{j}\geq\rho_{j}w_{j}\end{cases}$
(1)

where $k_{+,.},k_{-.},\zeta_{+,.},\zeta_{-,.}$ are the parameters that control
the degree of loss-aversion and risk-sensitivity. These parameters are found
to be highly heterogeneous and vary from person to person based on factors
like gender and age group [26, 27]. $y_{j}$ is the total actual cost of buying
energy for $j^{th}$ buyer s.t.

$y_{j}=\sum_{i\in S}\rho_{i}x_{ij}w_{j}+\rho_{gs}(1-\sum_{i}x_{ij})w_{j}$

Note that, similar to the PT value function in [16], the utility function in
Eq. (1) is concave in the gain domain (i.e. case $y_{j}<\rho_{j}w_{j}$) while
convex in loss domain (i.e. case $y_{j}\geq\rho_{j}w_{j}$).

The problem of matching demand and production of heterogeneous prosumers is
formalized as follows.

maximize $\displaystyle f(y):\sum_{j\in B}v(y_{j})$ (2) s.t.
$\displaystyle\sum_{j\in B}(1+l_{ij})x_{ij}w_{j}\leq r_{i},$
$\displaystyle\forall i$ (2a) $\displaystyle\sum_{i\in S}x_{ij}\leq 1,$
$\displaystyle\forall j$ (2b) $\displaystyle x_{ij}=0\text{, if }l_{ij}\geq
l_{max},$ $\displaystyle\forall i$ (2c)
$\displaystyle\rho_{gb}\leq\rho_{i},\rho_{j}\leq\rho_{gs},$
$\displaystyle\forall i$ (2d) $\displaystyle x_{ij}\in[0,1],$
$\displaystyle\forall i,j$ (2e)

The problem maximizes the sum of perceived utility for buyers in Eq. (2).
Constraint in Eq. (2a) prevents the problem from exceeding the amount of
energy being sold by each sellers while incorporating the losses in electric
lines. The constraint in Eq. (2b) ensures that the energy demand for each
buyers is not exceeded, while constraint (2c) limits the loss between sellers
and buyers to be within the loss threshold $l_{max}$. Finally, the constraint
(2d) limits upper and lower bound for energy price to the selling and buying
price of the grid.

It is to be noted that the problem in Eq. (2) is non-linear, non-convex
optimization problem. Hence, we propose a heuristic based on Differential
Evolution Algorithm (DEA) [24] described in the following section.
Additionally, in the above problem, the selling price is considered as a fixed
amount for a trading period. However, the reference price $\rho_{j}$ of buyer
$j$ is a personal value which may under- or over-estimate the competitiveness
of market. In order to maximize the sellers’ perceived objectives through
prospect theory, we resort to the risk-sensitive Q-learning algorithm [25].

Input : set of buyers $B$, sellers $S$, fitness function $f(.)$, max
iterations $G_{max}$, population size $NP$, crossover probability $CR$,
differential weight $F$

Output : best identified feasible solution $\mathbf{x^{*}}$

1 Update set of buyers $B$ and sellers $S$, $count=0$;

2 Generate initial population $\mathcal{X}=\\{\mathbf{x_{k}}|\mbox{
}k=1,\dots,NP\\}$;

3 while  _$count <G_{max}$_ do

4 for  _each $\mathbf{x_{k}}\in\mathcal{X}$_ do

5 Choose $3$ different vectors
$\\{\mathbf{x_{a}},\mathbf{x_{b}},\mathbf{x_{c}}\\}\in\mathcal{X}$ at random
and $R\sim U(1,|S|\times|B|)$;

6 Create mutated solution $\mathbf{\bar{x}_{k}}=\mathbf{x_{k}}$;

/* Mutation and Crossover */

7 for  _each $i\in|S|$, $j\in|B|$_ do

8 Select $u\sim U(0,1)$ ;

9 if  _$u <CR||(i\times j)==R$_ then

10 $\bar{x}_{ij}^{(k)}=x_{ij}^{(a)}+F\times(x_{ij}^{(b)}-x_{ij}^{(c)})$;

11 $\bar{x}_{ij}^{(k)}=\min(1,\max(0,\bar{x}_{ij}^{(k)}))$

12

13 end for

/* Check Constraints */

14 $\forall i,j$, if  _$l_{ij}\geq l_{max}$_ then $\bar{x}_{ij}=0$;

15 $\forall i$, if  _$\sum_{j}(1+l_{ij})\bar{x}_{ij}w_{j} >r_{i}$_ then
$\bar{x}_{ij}=\frac{\bar{x}_{ij}r_{i}}{\sum_{\hat{j}}\bar{(}1+l_{i\hat{j}})\bar{x}_{i\hat{j}}w_{\hat{j}}}$;

16 $\forall j$, if  _$\sum_{i}\bar{x}_{ij} >1$_ then
$\bar{x}_{ij}=\frac{\bar{x}_{ij}}{\sum_{\hat{i}}\bar{x}_{\hat{i}j}}$;

/* Compare fitness */

17 if  _$f(\mathbf{\bar{x}_{k}}) >f(\mathbf{x_{k}})$_ then
$\mathcal{X}=(\mathcal{X}\setminus\\{\mathbf{x_{k}}\\})\cup\\{\mathbf{\bar{x}_{k}}\\}$;

18

19 end for

20 count = count++;

21

22 end while

/* Find the best solution to execute trading */

23 Let
$\mathbf{x^{*}}=\arg\max\limits_{\mathbf{x_{k}}\in\mathcal{X}}f(\mathbf{x_{k}})$;

24

25Execute transactions for each prosumers to $\mathbf{x^{*}}$ ;

Algorithm 1 DEbATE

##  III The DEbATE and PQR Heuristics

In this section, we describe the Differential Evolution-based Algorithm for
Trading Energy (DEbATE) (Alg. 1), designed for the problem presented in
Section II, and the Pricing mechanism with Q-learning and Risk-sensitivity
(PQR), designed to dynamically adjust the sellers’ prices.

###  III-A DEbATE

$DEbATE$ is executed at each trading period (e.g., 12 hours) to solve the non-
linear optimization problem in Eq. (2). It uses differential evolution to
determine an optimal amount of energy to be traded between prosumers that
maximizes the perceived utility of buyers. DEbATE initially updates the list
of buyers ($B$) and sellers ($S$) based on the expected production and
consumption for current trading period. These can be predicted accurately with
recent approaches [28, 29]. The differential evolution-based optimization
begins on line $2$ where an initial population $\mathcal{X}$ is generated with
population size of $NP$. An element $\mathbf{x_{k}}\in\mathcal{X}$, with
$k=1,2,\dots,NP$ is a candidate solution vector of variables $x_{ij}$
representing the amount of energy to be traded between each seller $i$ and
buyer $j$ . These variables correspond to the decision variables of our
optimization problem.

The $while-$loop (line $3-19$) is the differential evolution loop that aims at
finding solution to the non-linear optimization problem with Eq. (2) as the
fitness function. The loop is executed for $G_{max}$ iterations. At each
iteration, for each candidate solution $\mathbf{x}_{k}\in\mathcal{X}$, the
algorithm creates a mutated solution $\mathbf{\bar{x}_{k}}$. Initially,
$\mathbf{\bar{x}_{k}}=\mathbf{x_{k}}$. The mutated solution is subsequently
updated through mutation and crossover with $3$ random candidates
$\mathbf{x}_{a},\mathbf{x}_{b},\mathbf{x}_{c}\in\mathcal{X}$ (line $5$). A
value $R\in[1,|S|\times|B|]$ is selected at random. $R$ will be used in the
following $for-$loop to ensure a minimum mutation. The for loop in line $7$
iterates over the components (dimensions in evolutionary terms) of
$\mathbf{\bar{x}_{k}}$. During each iteration, a value $u\in[0,1]$ is sampled
at random as mutation probability (line $8$). Subsequently, a mutation occurs
for the component $ij$ of $\mathbf{\bar{x}_{k}}$ with crossover probability
$CR$ (line $9$). The mutation occurs irrespective of the probability if
$(i\times j)=R$ (to ensure at least one minimum mutation). A mutation is
executed by combining the corresponding component of $\mathbf{x_{a}}$,
$\mathbf{x_{b}}$, and $\mathbf{x_{c}}$ with the differential weight parameter
$F\in[0,2]$ as in line $10$. The mutated component
$\mathbf{\bar{x}_{ij}^{(k)}}$ is clipped to ensure that it falls within
$[0,1]$ as minimum and maximum threshold to satisfy constraint Eq. (2e) in
line $11$ of the algorithm.

After the mutated solution is finalized, it is checked, and adjusted if
needed, to meet the constraints in Eqs. (2a)-(2c) of the optimization problem.
Specifically, line $13$ ensures that no exchange occurs (i.e.,
$\mathbf{\bar{x}_{ij}^{(k)}}=0$) between users having a loss higher than
$l_{max}$. Lines $14-15$ ensure that the production of a seller and the demand
of each buyer are not exceeded, respectively. Finally, in line $16$, the
fitness function $f(.)$ of the mutated solution $\mathbf{\bar{x}_{k}}$ is
compared against the original candidate solution $\mathbf{x_{k}}$. If
$f(\mathbf{\bar{x}_{k}})>f(\mathbf{{x}_{k}})$, then $\mathbf{\bar{x}_{k}}$
replaces $\mathbf{{x}_{k}}$ in the set of candidate solutions $\mathcal{X}$.
At the end of the while loop, $DEbATE$ selects the best solution
$\mathbf{{x}^{*}}$ in $\mathcal{X}$ (line $20)$ and executes the transactions
accordingly (line $21$). In the following theorem 1, we show that the $DEbATE$
has polynomial complexity and hence, computationally efficient.

######  Theorem 1.

The complexity of the $DEbATE$ algorithm is $O(G_{max}\times NP\times|S||B|)$.

###### Proof.

The complexity is dominated by the $while$ loop (lines $3-19$), which is
executed $G_{max}$ times. Within this loop, the $for-$loop (lines $4-17$) does
$|\mathcal{X}|=NP$ total iterations. In each iteration, the inner $for-$loop
(lines $7-12$) iterates over the sets $S$ and $B$, and only contains constant
operations. Similarly, checking the constraints (lines $13-15$) requires to
iterate over the same sets. Finally, calculating the function $f(.)$ (line
$16$) has cost $|B|$. Overall, the complexity is $O(G_{max}\times
NP\times(|S||B|+3|S||B|+|B|))=O(G_{max}\times NP\times|S||B|)$ ∎

/* Pricing with Risk-sensitive Q-learning */

1 Collect transaction information for each prosumers from $DEbATE$ (Alg. 1)
for current timestep $t$;

2 for  _each $i\in S$_ do

3 Select an action, $a\in\\{+\delta,-\delta,0\\}$ based on exploration and
exploitation ;

4 $s=\rho_{i};s_{new}=s+a;R_{i}=(\rho_{i}+a)\sum\limits_{j\in B}x_{ij}$;

5 Update $Q(s,a)$ as in Eq. (3);

6 $\rho_{i}=s_{new}$;

7 Send information on updated price $\rho_{i}$ to seller $i$;

8

9 end for

Algorithm 2 PQR

###  III-B PQR

After determining the solution to the energy allocation problem in $DEbATE$,
the selling price for sellers is then updated through the $PQR$ algorithm. In
order to learn the optimal selling price dynamically over time, we model the
sellers as independent learning agents. Note that, to preserve the privacy and
avoid the conflict between prosumers, these agents do not have access to
information about other sellers or buyers. The state space in the Q-learning
formulation consists of the prices between the grid buying ($\rho_{gb}$) and
selling ($\rho_{gs}$), discretized by a step size, $\delta$, i.e.,
$\rho_{i}\in\\{\rho_{gb},\ \rho_{gb}+\delta,\ \rho_{gb}+2\delta,\ ...,\
\rho_{gb}+\big{(}\frac{\rho_{gs}-\rho_{gb}}{\delta}-1\big{)}\delta,\
\rho_{gs}\\}.$

The action space consists of a price increasing action, price decreasing
action, and no change action, i.e. $a\in\\{+\delta,-\delta,0\\}$, where
$\delta$ is the amount by which price is increased or decreased. Seller $i$
reward function is the total revenue generated at the current trading period
i.e. $R_{i}=(\rho_{i}+a)\sum_{j\in B}x_{ij}w_{j}$. For updating Q-values, we
modify the approach proposed in [25] by considering the following Q-learning
update rule that includes the PT-based perceived utility of sellers.

$Q^{(new)}(s,a)=Q^{(old)}(s,a)+\alpha v(y_{i})$ (3)

$v(y_{i})=\begin{cases}k_{+,i}(y_{i})^{\zeta_{+,i}},&y_{i}>0\\\
-k_{-,i}(-y_{i})^{\zeta_{-,i}},&y_{i}\leq 0\end{cases}$ (4)

where, $y_{i}=R_{i}+\gamma\max_{a}Q(s_{new},a)-Q(s,a)$ is the Temporal
Difference (TD) error of $i^{th}$ seller for current iteration, and $v(y_{i})$
is transformation of TD error to capture each seller’s personalized perceived
utility on loss and gain. $\alpha$ refers to the learning rate for updating
Q-values in Eq. (3). The action is selected based on an $\epsilon$-greedy
exploration-exploitation strategy [30]. Specifically, $\epsilon$ refers to the
probability of exploration and it is initially set to $1$. It is then
decreased over time using an $\epsilon-$decay value, as the system learns the
optimal policy. Based on the selected action, the new selling price, reward,
and Q-value are updated as per Eqs. (3) and (4). Updated selling price is then
sent to the respective seller $i$ for next trading period.

The system runs both $DEbATE$ and $PQR$ sequentially at every trading period.
Input of $DEbATE$ is updated based on the prices computed by $PQR$. $PQR$ then
takes as input the reward from executing energy transactions by $DEbATE$.

##  IV Experimental Results

###  IV-A Experimental Setup

Figure 2: Normalized objective value vs. number of iterations.

Figure 3: Buyers’ perceived values.

Figure 4: Sellers’ cumulative reward.

Figure 5: Individual prices.

In this section, we evaluate the performance of DEbATE and PQR, hereafter
jointly referred as $DEbATE-PQR$, against a recent state-of-the-art approach
referred to as Rule [9]. $Rule$ allocates energy using a greedy heuristic that
assigns cheapest sellers to buyers based on their registration order in the
system, while final price of each transaction follows mid-market pricing,
i.e., mid value of seller’s and buyer’s asking price. We consider a system
with $40$ prosumers, split evenly as buyers and sellers. This is considered a
representative number of prosumers in a microgrid or set of houses supplied by
a single distribution transformer. We use a realistic dataset for buyers’
energy consumption obtained from [31]. Similarly, we consider sellers equipped
with $4kW$ rooftop solar located in Lexington, Kentucky, USA. The energy
generated is estimated using NREL’s PVWatts Calculator [32] given the solar
irradiance in Lexington and size of solar panels. Losses are assigned
uniformly at random from set $\\{1\%,2\%,3\%,4\%\\}$ and maximum loss
threshold $L_{max}=2.5\%$.

We assume that prosumers complete a survey before joining the system to
estimate their individual prospect theory parameters, similar to [27, 26, 23],
and use realistic prospect theory parameters determined by them. Specifically,
we sample the risk-averting parameter for gains $(\zeta_{+})\in[0.60,0.88]$,
the risk-seeking parameter for losses $(\zeta_{-})\in[0.52,1.0]$, the loss-
aversion parameters for gain and loss $(k_{+}),(k_{-})\in[2.10,2.61]$ for each
individual prosumers. The grid energy buying price is set to
$\rho_{gb}=\$0.06$ and the selling price to $\rho_{gs}=\$0.12$. The reference
price for each sellers is initially randomly sampled from range $[0.09,0.12]$.
It is then updated using $PQR$ at each iteration. The reference price for each
buyer is selected in the range $[0.06,0.10]$ and considered static for the
duration of experiments, which is $365$ days. The parameters for $PQR$
algorithm are set as follows: learning rate $\alpha=10^{-4}$, step size for
discretizing state space $\delta=\$0.001$, and $\epsilon-$decay $=0.965$.

###  IV-B Results

We consider several experimental scenarios and performance metrics, as
discussed in the following.

Experimental Scenario 1: We first run experiments to study the convergence of
DEbATE. We considered different system size by scaling the number of sellers
and buyers. Fig. 2 shows the normalized objective value as a function of the
number of iterations using a population size $NP=20$. The plot averaged over
10 runs shows that $10,000$ iterations are sufficient for the algorithm to
converge in the considered settings. As a result, in the following scenarios
we set $G_{max}=10,000$ and the population size $NP=20$.

Experimental Scenario 2: In the second experimental scenario we study the
performance of the considered approaches over time. Two performance metrics
are considered, namely the buyers’ objective value and the sellers’ cumulative
reward. These are represented in Figs. 5 and 5, respectively, with a moving
average of $10$ days. In this experiments we consider $15$ buyers and $15$
sellers. The benefits of $DEbATE-PQR$ over $Rule$ are more prominent from
April through October, when the energy demand and production is higher. The
greedy nature of $Rule$ penalizes the quality of the resulting matching,
significantly reducing the buyers’ perceived value. Note that, the buyers’
objective values are negative because they are paying higher prices than their
reference purchase price. Therefore, transactions are seen as loss from a
prospect theory perspective. Nevertheless, our approach optimizes the energy
assignment to maximize the buyers perceived value. Additionally, our approach
is able to generate higher rewards than $Rule$ by dynamically learning the
prices for sellers through the $PQR$ algorithm. The the sellers’ reward
decreases after mid-september for both the approaches due to the reduced
energy production during winter.

Figure 6: Obj. values for buyer vs. network size.

Figure 7: Total rewards for sellers vs. network size.

We further study the performance over time by considering the evolution of
average and individual sellers’ prices. We consider a smaller system of $5$
sellers and $5$ buyers for ease of representation of the results. Fig. 5 shows
the individual prices. $DEbATE-PQR$ is able to learn and adjust the price over
time to improve the buyers’ perceived value considering their competitiveness.
The competitiveness is a function of a buyer’s reference price, their
production, and their location in the system (e.g., loss w.r.t. sellers). As a
result, our approach is able to improve the perception of both buyers and
sellers while ensuring the competitiveness of the market.

Experimental Scenario 3: In this scenario we test the scalability with respect
to the system size. Specifically, we increase the system proportionately from
$5$ sellers and $5$ buyers to $20$ sellers and $20$ buyers. Figs. 7-7 show the
buyers’ total perceived value and the sellers’ reward, respectively, over a
year. By considering the loss-averse and risk-seeking PT-value functions,
$DEbATE-PQR$ achieves an increasing advantage as the system size increases
compared to $Rule$, for both sellers and buyers. As a numerical example,
$DEbATE-PQR$ achieves as much as $26\%$ increase in buyers’ perceived value
while ensuring $7\%$ profit improvement for sellers.

##  V Concluding Remarks

In this paper, we bring together the concept of perceived utility from
behavioral economics and reinforcement learning into the P2P energy trading
scene. Unlike existing literature, we propose an automated and dynamic P2P
energy trading problem that maximizes the perceived value for buyers while
simultaneously learning the optimal selling price. Given the non-linear and
non-convex nature of the problem, we propose a novel differential evolution-
based metaheuristic algorithm, called $DEbATE$. $DEbATE$ is paired with a
prospect theory enhanced Q-learning algorithm, called $PQR$, to adjust the
selling price over time. Results show the advantages of the proposed
approaches with respect to a state of the art solution using real energy
consumption and production data.

## Acknowledgment

This work is supported by the NSF grant EPCN-1936131 and NSF CAREER grant
CPS-1943035.

## References

  * [1] “Iea org,” https://www.iea.org/reports/electricity-information-overview/.
  * [2] A. Timilsina, A. R. Khamesi, V. Agate, and S. Silvestri, “A reinforcement learning approach for user preference-aware energy sharing systems,” _IEEE Transactions on Green Communications and Networking_ , vol. 5, no. 3, pp. 1138–1153, 2021.
  * [3] Y. Parag and B. Sovacool, “Electricity market design for the prosumer era,” _Nature Energy_ , vol. 1, p. 16032, March 2016.
  * [4] W. Tushar, T. K. Saha, C. Yuen _et al._ , “Peer-to-peer trading in electricity networks: an overview,” _IEEE Transactions on Smart Grid_ , 2020\.
  * [5] W. Tushar, T. K. Saha, C. Yuen, P. Liddell, R. Bean, and H. V. Poor, “Peer-to-peer energy trading with sustainable user participation: A game theoretic approach,” _IEEE Access_ , vol. 6, pp. 62 932–62 943, 2018.
  * [6] T. Zhu, Z. Huang, A. Sharma, J. Su, D. Irwin, A. Mishra, D. Menasche, and P. Shenoy, “Sharing renewable energy in smart microgrids,” in _ACM/IEEE ICCPS_ , 2013.
  * [7] W. Tushar, C. Yuen, H. Mohsenian-Rad, T. Saha, H. V. Poor, and K. L. Wood, “Transforming energy networks via peer-to-peer energy trading: The potential of game-theoretic approaches,” _IEEE Signal Processing Magazine_ , vol. 35, no. 4, pp. 90–111, 2018.
  * [8] W. Tushar, T. K. Saha, C. Yuen, T. Morstyn, H. V. Poor, R. Bean _et al._ , “Grid influenced peer-to-peer energy trading,” _IEEE Transactions on Smart Grid_ , vol. 11, no. 2, pp. 1407–1418, 2019.
  * [9] M. I. Azim, S. Pourmousavi, W. Tushar _et al._ , “Feasibility study of financial p2p energy trading in a grid-tied power network,” in _IEEE PESGM_ , 2019.
  * [10] M. Nasimifar, V. Vahidinasab, and M. S. Ghazizadeh, “A peer-to-peer electricity marketplace for simultaneous congestion management and power loss reduction,” in _IEEE Smart Grid Conference_ , 2019.
  * [11] A. Paudel, L. Sampath, J. Yang, and H. B. Gooi, “Peer-to-peer energy trading in smart grid considering power losses and network fees,” _IEEE Transactions on Smart Grid_ , vol. 11, no. 6, pp. 4727–4737, 2020.
  * [12] G. Gigerenzer and R. Selten, _Bounded rationality: The adaptive toolbox_. MIT press, 2002.
  * [13] D. E. Agosto, “Bounded rationality and satisficing in young people’s web-based decision making,” _Journal of the American society for Information Science and Technology_ , vol. 53, no. 1, pp. 16–27, 2002.
  * [14] P. E. Earl, “Bounded rationality in the digital age,” in _Minds, Models and Milieux_. Springer, 2016, pp. 253–271.
  * [15] V. Agate, A. R. Khamesi, S. Silvestri, and S. Gaglio, “Enabling peer-to-peer user-preference-aware energy sharing through reinforcement learning,” in _IEEE ICC_ , 2020.
  * [16] D. Kahneman and A. Tversky, “Prospect theory: An analysis of decision under risk,” in _Handbook of the fundamentals of financial decision making: Part I_. World Scientific, 2013, pp. 99–127.
  * [17] G. El Rahi, W. Saad, A. Glass _et al._ , “Prospect theory for prosumer-centric energy trading in the smart grid,” in _IEEE PES ISGT_ , 2016\.
  * [18] G. El Rahi, S. R. Etesami, W. Saad, N. B. Mandayam, and H. V. Poor, “Managing price uncertainty in prosumer-centric energy trading: A prospect-theoretic stackelberg game approach,” _IEEE Transactions on Smart Grid_ , vol. 10, no. 1, pp. 702–713, 2017.
  * [19] W. Saad, A. L. Glass, N. B. Mandayam, and H. V. Poor, “Toward a consumer-centric grid: A behavioral perspective,” _Proceedings of the IEEE_ , vol. 104, no. 4, pp. 865–882, 2016.
  * [20] Y. Wang, L. Zhang, Q. Ding, and K. Zhang, “Prospect theory-based optimal bidding model of a prosumer in the power market,” _IEEE Access_ , vol. 8, pp. 137 063–137 073, 2020.
  * [21] Y. Yao, C. Gao, T. Chen _et al._ , “Distributed electric energy trading model and strategy analysis based on prospect theory,” _International Journal of Electrical Power & Energy Systems_, vol. 131, p. 106865, 2021.
  * [22] D. Contu, E. Strazzera, and S. Mourato, “Modeling individual preferences for energy sources: The case of iv generation nuclear energy in italy,” _Ecological Economics_ , vol. 127, pp. 37–58, 2016.
  * [23] C. R. Fox and R. A. Poldrack, “Prospect theory and the brain,” in _Neuroeconomics_. Elsevier, 2009, pp. 145–173.
  * [24] R. Storn and K. Price, “Differential evolution–a simple and efficient heuristic for global optimization over continuous spaces,” _Journal of global optimization_ , vol. 11, no. 4, pp. 341–359, 1997.
  * [25] Y. Shen, M. J. Tobia, T. Sommer, and K. Obermayer, “Risk-sensitive reinforcement learning,” _Neural computation_ , vol. 26, no. 7, 2014.
  * [26] V. Baláž, V. Bačová, E. Drobná _et al._ , “Testing prospect theory parameters,” _Ekonomicky časopis_ , vol. 61, 2013.
  * [27] M. O. Rieger, M. Wang, and T. Hens, “Estimating cumulative prospect theory parameters from an international survey,” _Theory and Decision_ , vol. 82, no. 4, pp. 567–596, 2017.
  * [28] W. Kong, Z. Y. Dong, Y. Jia, D. J. Hill, Y. Xu, and Y. Zhang, “Short-term residential load forecasting based on lstm recurrent neural network,” _IEEE Transactions on Smart Grid_ , vol. 10, no. 1, pp. 841–851, 2017.
  * [29] E. Casella, E. Sudduth, and S. Silvestri, “Dissecting the problem of individual home power consumption prediction using machine learning,” in _IEEE SMARTCOMP_ , 2022.
  * [30] R. S. Sutton and A. G. Barto, _Reinforcement learning: An introduction_. MIT press, 2018.
  * [31] Pecan street inc. [Online]. Available: www.pecanstreet.org
  * [32] Solar Resource Data. [Online]. Available: pvwatts.nrel.gov/pvwatts.php


# Deep Heterogeneous Autoencoders
for Collaborative Filtering

Tianyu Li1, Yukun Ma2, Jiu Xu1, Björn Stenger1, Chen Liu1, Yu Hirate1
Correspondence to<EMAIL_ADDRESS>1Rakuten Institute of Technology
2Nanyang Technological University

###### Abstract

This paper leverages heterogeneous auxiliary information to address the data
sparsity problem of recommender systems. We propose a model that learns a
shared feature space from heterogeneous data, such as item descriptions,
product tags and online purchase history, to obtain better predictions. Our
model consists of autoencoders, not only for numerical and categorical data,
but also for sequential data, which enables capturing user tastes, item
characteristics and the recent dynamics of user preference. We learn the
autoencoder architecture for each data source independently in order to better
model their statistical properties. Our evaluation on two MovieLens datasets
and an e-commerce dataset shows that mean average precision and recall improve
over state-of-the-art methods.

###### Index Terms:

Deep Autoencoder, Heterogeneous Data, Shared Representation, Sequential Data
Modeling, Collaborative Filtering

##  I Introduction

Although Collaborative Filtering (CF) techniques achieve good performance in
many recommender systems [1], their performance degrades significantly when
historical data is sparse. In order to alleviate this problem, features from
auxiliary data sources that reflect user preference have been extracted [2,
5], as shown in Fig. 1. How to represent data from different sources is still
a research problem, and it has been shown that the representation itself
substantially impacts performance [6, 20]. Recently, representation learning
that automatically discovers hidden factors from raw data has become a popular
approach to remedy the data sparsity issue of recommender systems [10, 14].

Many online shopping platforms gather not only user profiles and item
descriptions, but various other types of data, such as product reviews, tags
and images. Recent research has added textual and visual information to
recommender systems [3, 4]. However, in many cases sequential data, such as
user purchase and browsing history, which carries information about trends in
user tastes, have largely been neglected in CF-based recommender systems.

Figure 1: Auxiliary information usage in recommender systems. Item
descriptions and user profiles are typically being used for feature extraction
to alleviate the data sparsity problem. Our proposal also leverages sequential
data, such as purchase histories, to reflect user preferences.

In this paper we propose Deep Heterogeneous Autoencoders (DHA) for
Collaborative Filtering to combine information from multiple domains. We use
Stacked Denoising Autoencoders (SDAE) to extract latent features from non-
sequential data, and Recurrent Neural Network Encoder-Decoders (RNNED) to
extract features from sequential data. The model is able to capture both user
preferences and potential shifts of interest over time. Each data source is
modeled using an independent encoder-decoder mechanism. Different encoders can
have different number of hidden layers and an arbitrary number of hidden units
in order to deal with the intrinsic difference of data sources. For instance,
user demographic data and item content are typically categorical, while user
comments or item tags are textual. After pre-processing, such as one hot
encoding, bag-of-words and word2vec computation, representation vectors are on
a different level of abstraction. Owing to its flexible structure, our model
is able to learn suitable latent feature vectors for each component. These
local representations from each data source are joined to form a shared
feature space, which couples the joint learning of the representation from
heterogeneous data and the collaborative filtering of user-item relationships.

The contributions of this paper are summarized as follows:

  1. 1.

A method for modeling both static and sequential data in a consistent way for
recommender systems in order to capture the trend in user tastes, and

  2. 2.

Adaptation of the autoencoder architecture to accurately model each data
source by considering their distinct abstraction levels.

We show improvements in terms of mean average precision and recall on three
different datasets.

##  II Related work

###  II-A Incorporating side information into recommender systems

In order to improve recommendation performance, research has been focusing on
using side information, such as user profiles and reviews [3, 5]. In
particular, deep learning models have been widely studied [13, 15]. AutoRec
first proposed the use of autoencoders for recommender systems [17]. In more
recent work, representations are learned via stacked autoencoders (SAE), and
fed into conventional CF models, either loosely or tightly coupled [18, 7].
Deep models that integrate autoencoders into collaborative filtering have
shown state-of-the-art performance.

###  II-B Recurrent Neural Network Encoder-Decoder

Recurrent neural networks (RNNs) process sequential data one element at each
step to capture temporal dynamics. The encoder-decoder mechanism was initially
applied to RNN for machine translation [11]. Recently, RNN encoder-decoders
(RNNED) have been used to learn features from a series of actions and have
successfully been applied in other areas. It was shown that Long Short-Term
Memory (LSTM) networks have the ability to learn on data with long range
temporal dependencies, and we adopt LSTMs for modeling sequential data.

Figure 2: Deep Heterogeneous Autoencoders and the integration with
collaborative filtering. The proposed model extracts a shared feature space
from multiple sources of auxiliary information. It models non-sequential and
sequential data to capture user preferences, item properties as well as
temporal dynamics. It adopts independent encoder-decoder architectures for
different data sources in order to better model their statistical properties.
The product of $U\in\mathbb{R}^{m\times d}$ and $V\in\mathbb{R}^{n\times d}$
approximates the user-item interaction matrix.

##  III Deep Heterogeneous Autoencoders for Collaborative Filtering

###  III-A Overview

We propose a model that learns a joint representation from heterogeneous
auxiliary information to mitigate the data sparsity problem of recommender
systems. SDAEs are applied to numerical and categorical data for modeling the
static tastes of users for items. We use RNNEDs to extract features from
sequential data to reveal interest shifts over time.

The model adopts an independent autoencoder architecture for each data source
since the inputs are generally on a different level of abstraction, see Fig. 2
for an overview. In order to discover the distinct statistical properties of
every data source, our model takes the existing disparity of input abstraction
levels into consideration, and applies autoencoders to each source
independently by allowing distinct hidden layer numbers and arbitrary hidden
units at every layer.

###  III-B Deep Heterogeneous Autoencoders

We define each source of auxiliary data as a component indexed by
$c\in\\{1,...,C\\}$. $S_{c}$ denotes the input of component $c$. We pre-
process non-sequential data like textual item descriptions by generating
fixed-length embedding vectors. For sequential data, an embedding vector is
learned for every time step after tokenization. We seperately describe the
encoding-decoding outputs of the above two types of embedding vectors.

As shown in Fig. 2, SDAE is applied to fixed-length embedding vectors. Each
component encoder takes the input $S_{c}$, generates a corrupted version of
it, $\hat{S_{c}}$, and the first layer maps it to a hidden representation
$h_{c}$, which captures the main factors of variation in the input data
distribution[8, 9]. More importantly, the number of component hidden layers in
our model can differ from each other. The architecture is unique for each data
source, where the number of layers of component $c$ is denoted as $L_{c}$. The
representation at every layer is $S_{c,l}$. For the encoder of each component,
given $l_{c}\in\\{1,...,L_{c}/2\\}$ and $c\in C$, the hidden representation
$h_{c,l}$ is derived as:

$h_{c,l}=f\left(W_{c,l}h_{c,l-1}+b_{c,l}\right).$ (1)

The decoder reconstructs the data at layer $L$ as follows:

$\bar{S}_{c}=g\left(W^{\prime}_{c}h_{c,L}+b^{\prime}_{c}\right).$ (2)

The proposed model leverages sequential data by using two LSTMs for encoding
and decoding one sequential data source. Specifically, the encoder reads a
sequence with $T$ time steps. At the last time step, the hidden state $h_{T}$
is mapped to a context vector $c$, as a summary of the whole input
sequence[11]. The decoder generates the output sequence by predicting the next
action $y_{t}$ given $h_{t}$. Both $y_{t}$ and $h_{t}$ are also conditioned on
$y_{t-1}$ and the context vector $c$.

To combine them, as shown in Fig. 2, the first part of our model encodes all
components to generate hidden representations $S_{c,L_{c}/2}$ of non-
sequential data and $h_{T}$ of sequential data across all sources. These are
merged to generate a joint latent representation, denoted as $h_{+,0}$.
Analogous to the hidden layers of each component, the fusion model can have
multiple hidden layers, the total number denoted as $L_{+}$. The
representation of the first fusion hidden layer is

$h_{+,0}=f\left(\sum_{c\in C}W_{c,+}h_{c,L_{c}/2}+b_{+,0}\right).$ (3)

The first hidden layer $h_{+,0}$ of the fused model is fed into the
collaborative filtering model. After joint training, $h_{+,0}$ is the latent
vector to generate recommendation results.

###  III-C DHA-based Collaborative Filtering

All data is fed into two DHAs for users and items, respectively. Fig. 2 shows
the process for items, and it is analogous for user data. Let
$R\in\mathbb{R}^{m\times n}$ denote the rating matrix of users to items,
$S_{c}^{\left(u\right)}$ being the component $c$ input for users and
$S_{c}^{\left(v\right)}$ that for items. Then, $h_{+,0}^{\left(u\right)}$ and
$h_{+,0}^{\left(v\right)}$ are the latent factors. The loss function of the
proposed DHA based collaborative filtering is defined as:

$\displaystyle\begin{split}L=&\sum_{i,j}c_{i,j}\left(r_{i,j}-u_{i}v_{j}\right)^{2}+\lambda_{f}(\sum_{i}||u_{i}||^{2}+\sum_{j}||v_{j}||^{2})\\\
&+\lambda_{m}\sum_{c\in
C_{u}}\emph{loss}(S_{c}^{\left(u\right)},\bar{S}_{c}^{\left(u\right)})+\lambda_{n}\sum_{c\in
C_{i}}\emph{loss}(S_{c}^{\left(v\right)},\bar{S}_{c}^{\left(v\right)})\\\
&+\lambda_{u}\sum_{i}||u_{i}-h_{+,0}^{u_{i}}||^{2}+\lambda_{v}\sum_{j}||v_{j}-h_{+,0}^{v_{j}}||^{2}\\\
&+\lambda_{w}(\sum_{c}\sum_{l}\left(||W_{c,l}^{(u)}||^{2}+||b_{c,l}^{(u)}||^{2}\right)\\\
&\qquad+\sum_{c}\sum_{l}\left(||W_{c,l}^{(v)}||^{2}+||b_{c,l}^{(v)}||^{2}\right)).\end{split}$
(4)

The loss function includes reconstruction costs of user and item information
sets, the error to predict $r_{i,j}$, and the approximation error between
latent factor vectors of feature learning and collaborative filtering. The
loss function is minimized to obtain parameters for the DHAs and the CF model.
The mean squared error and the negative log-likelihood are used as cost
functions for non-sequential and sequential data, separately. We use
$\lambda_{m}$, $\lambda_{n}$, $\lambda_{u}$ and $\lambda_{v}$ to balance
losses between users and items, $\lambda_{f}$, and $\lambda_{w}$ to regularize
the weight matrix and bias vectors.

###  III-D Parameter learning

We apply coordinate descent to alternate the optimization between
representation learning of heterogeneous data and user-item interaction,
similar to [7, 16]. Given $W$s and $b$s, the gradients of the loss function
$L$ with respect to $u_{i}$ and $v_{j}$ are computed and set to 0, leading to
the following updates:

$\displaystyle u_{i}$
$\displaystyle\leftarrow(V^{T}C_{i}V+\lambda_{f}I+\lambda_{u}I)^{-1}(V^{T}C_{i}R_{i}+\lambda_{u}h_{+,0}^{u_{i}}),$
(5) $\displaystyle v_{j}$
$\displaystyle\leftarrow(U^{T}C_{j}U+\lambda_{f}I+\lambda_{v}I)^{-1}(U^{T}C_{j}R_{j}+\lambda_{v}h_{+,0}^{v_{j}}),$
(6)

where $U\in\mathbb{R}^{m\times d}$ and $V\in\mathbb{R}^{n\times d}$ contain
the user and item latent factor vectors, and $d$ is the vector dimensionality.
Given $U$ and $V$, the weight matrix and bias vectors of every layer are
learned by backpropagation with stochastic gradient descent (SGD). Gradients
of $W$ and $b$ are calculated as follows:

$\displaystyle\frac{\partial L}{\partial W^{u}}=$
$\displaystyle\lambda_{w}W^{u}+\lambda_{m}\frac{\partial\bar{S}_{c}}{\partial
W^{u}}\sum_{c}\emph{loss}(S_{c}^{u},\bar{S}_{c}^{u})+\lambda_{u}\frac{\partial
h_{+,0}^{u}}{\partial W^{u}}(U-h_{+,0}^{u}),$ (7) $\displaystyle\frac{\partial
L}{\partial b^{u}}=$
$\displaystyle\lambda_{w}b^{u}+\lambda_{m}\frac{\partial\bar{S}_{c}}{\partial
b^{u}}\sum_{c}\emph{loss}(S_{c}^{u},\bar{S}_{c}^{u})+\lambda_{u}\frac{\partial
h_{+,0}^{u}}{\partial b^{u}}(U-h_{+,0}^{u}).$ (8)

A learning rate $\alpha$ is adopted to update all parameters using calculated
gradients.

##  IV Experiments

Experiments are conducted on three real world datasets, MovieLens-100k
(ml-100k), MovieLens-10M (ml-10m), and one dataset from an e-commerce company
(OfflinePay). We first investigate whether the flexible autoencoder
architecture of our model can generate more accurate latent representations on
non-sequential data. Experiments on OfflinePay evaluate the effectiveness of
sequential data modeling.

###  IV-A Datasets and preprocessing

The first dataset, ml-100k, contains ratings from 943 users on 1,682 movies.
It has demographic data for users and descriptions for movies. The second
dataset, ml-10m, contains 10,000,054 ratings and 95,580 tags from 71,567 users
for 10,681 movies. It contains item content information, but no demographic
data. We employ user-added tags as an information source for users as well as
for movies.

OfflinePay is a dataset of user purchases in (offline) shops, paying with a
plastic e-money card. The dataset contains a total of 67M transaction records
from a four-month period. The goal of using the OfflinePay dataset is to
recommend new shop genres to users, not individual products. After aggregating
all transaction data into the format of (user $i$, shop genre $j$, number of
transactions $r_{ij}$), and removing shoppers who used only one shop genre,
the number of $r_{ij}$ values is 7,150,833 with 961,992 unique users and 105
shop genres. The auxiliary data sources include user registered information
and shop genre textual descriptions. Additionally, we collect user purchase
history on an e-commerce platform during the same time period. The sequence
data contains the genres of purchased items online.

The datasets are preprocessed to fixed-length embeddings for non-sequential
data, and sequences of embedding vectors for sequential data, respectively.
For ml-100k, we discretize continuous features like age to discrete values,
compute a bag-of-words vector for each user and item. The vector dimensions
are 821 for users, 2,482 for movies, respectively. For ml-10m, movie content
description and tags that users give to items are textual information. We
first tokenize texts, then train Doc2vec vectors for every data source with
the embedding vector length set to 500.

To generate shop genre embedding vectors for the OfflinePay dataset, all shop
names that belong to same genre are grouped together and Doc2vec is applied to
generate a 300-dimensional vector for each shop genre. User registered
information is preprocessed the same way as ml-100k, and the vector length is
189. For the sequence of genre purchase history, Word2vec is adopted to build
100-d embedding vectors after tokenization. Genres in each sequence are mapped
to the corresponding embedding vectors.

In experiments, we rank predicted ratings of candidate items and recommend the
top $M$ to each user. Mean average precision (MAP) and recall are used as
evaluation metrics.

Figure 3: Recall@M comparison on ml-100k, ml-10m. Results are shown for
I-AutoRec, CDL, DCF, aSDAE and DHA. The dimension $d$ of the latent factor
vector is set to 50, 100 and 150, respectively.

###  IV-B Experimental setting

The number of hidden layers of each model is optimized on a validation
dataset. The first fusion hidden layer of DHA is used to bridge the joint
training between feature space learning and collaborative filtering. For other
models, if the total number of hidden layers is $L$, we connect layer $L/2$
for joint training. The number of units in each hidden layer is incremented by
$K$ from the middle of the autoencoder to both sides. For sequential data
modeling, recent $T$ purchases is used in the experiments, and values
$T\in\\{5,10\\}$ are evaluated in our experiments.

The mini-batch size is set to 50 and 1,000 for ml-100k and ml-10m,
respectively. For the OfflinePay dataset, since the numbers of unique users
and items differ significantly, it is set to 20 for items and 10,000 for
users, separately. The model is implemented using the Theano library.

###  IV-C Experiments on MovieLens datasets

We compare our model with the following algorithms. Note that experiments on
MovieLens do not include sequential data.

  * •

AutoRec[17]: I-AutoRec takes a partial item feedback vector as input and
reconstructs at the output layer.

  * •

CDL[7]: a hierarchical Bayesian model that jointly performs deep
representation learning for content information and collaborative filtering
for the ratings matrix.

  * •

DCF[12]: a model that combines matrix factorization with marginalized
denoising stacked autoencoders. We concatenate side information as input to
DCF.

  * •

aSDAE[19]: a hybrid model that integrates side information by an additional
denoising autoencoder into the matrix factorization model.

  * •

DHA: the proposed model that applies independent autoencoder architecture to
heterogeneous data sources.

To compare different models, we repeat 80-20 splits of the data 5 times, run
5-fold cross validation and report average performance. Grid search is applied
to find optimal hyperparameters for all models. We search the learning rate of
SGD, $\alpha\in\\{0.1,0.05,0.01,0.001\\}$, the regularization of learned
parameters, $\lambda_{f}$ and $\lambda_{w}$ of our model
$\in\\{2.0,0.1,0.01,0.001\\}$, the corruption level of masking noise
$\in\\{0.1,0.3\\}$, the activation function $\in\\{sigmoid,relu\\}$, and the
number of fusion hidden layers $\in\\{1,2\\}$. The parameters used to balance
loss between user and item, $\lambda_{m},\lambda_{n},\lambda_{u},\lambda_{v}$
are set to 1. For CDL, DCF and aSDAE, we search hidden layer number from 4 and
6. The joint training is alternated 5 times, and we run 5 epochs for learning
features in each alteration. Before the joint training, layer-wise pretraining
is conducted to initialize network weights.

For the experiment on ml-100k, we input rating vectors, item content
information and user demographic data to DHA and aSDAE. Rating vectors are not
used in DCF and only item content information is used in CDL. I-AutoRec
leverages no side information. After grid search, the adopted hidden layer
number of CDL, DCF and aSDAE is 4. The number of fusion hidden layer is set to
1 for DHA. The parameter for regularizing learned parameters is set to 0.01 in
DHA, 0.001 in CDL and aSDAE, and 0.1 in DCF, respectively. The optimal
performance is found when the learning rate is set to 0.001 for CDL, DCF, 0.01
for aSDAE and DHA, and 0.1 for I-Autorec.

TABLE I: MAP@100 comparison on ml-100k and ml-10m datasets. Results are shown for three different settings of user and item latent factor vectors, $d$=50, 100, and 150. | ml-100k | ml-10m
---|---|---
Model |  | d=50 | d=100 | d=150 |  | d=50 | d=100 | d=150
I-AutoRec |  | 0.0573 | 0.0568 | 0.0572 |  | 0.0325 | 0.0323 | 0.0326
CDL |  | 0.1896 | 0.1825 | 0.1685 |  | 0.1458 | 0.1532 | 0.1612
DCF |  | 0.2012 | 0.2028 | 0.2069 |  | 0.1591 | 0.1620 | 0.1566
aSDAE |  | 0.2161 | 0.2228 | 0.2142 |  | 0.1602 | 0.1560 | 0.1642
DHA |  | 0.2236 | 0.2304 | 0.2258 |  | 0.1793 | 0.1774 | 0.1824

As shown in Fig. 3, all models achieve better recall than I-AutoRec, showing
the advantage of using side information. DHA and aSDAE perform better than CDL
which only incorporates item content description. DHA outperforms aSDAE which
integrates raw side information at every hidden layer. The MAP comparison in
Table I shows our model obtains more precise results for all dimension
settings.

There are five sets of available inputs for the experiment on the ml-10m
dataset. Users and movies have rating and tag vectors, movies also have
content vectors. For CDL, DCF and aSDAE, different information vectors are
concatenated as input. Our model uses all components, i.e. two components for
users and three components for movies. In the experiment, the best performance
is obtained when the number of hidden layers is set to 4 for CDL, aSDAE and to
6 for DCF. In our model, we use 2 fusion hidden layers and different layer
numbers for components. The number of hidden layers, $L_{c}$, is set to 4 for
users and movie rating vectors and to 2 for tag and content vectors. As shown
in Fig. 3, DHA obtains better recall performance compared to other algorithms.
aSDAE is competitive and outperforms both DCF and CDL in three dimension
settings. The MAP comparison in Table I indicates that in addition to
producing recommendation with better recall, our model also achieves better
precision results.

Figure 4: Recall@M comparison on OfflinePay dataset. Results are shown for
implicit-CF, CDL, DCF, DHA-RNNED-s10, DHA-RNNED-s5, DHA-RNNED-item and DHA-
all. The dimension of the latent factor vector is set to 50, 100 and 150,
respectively.

###  IV-D Experiments on OfflinePay dataset

Since the OfflinePay dataset involves user online purchase histories, we use
the first 3-month data as training data, the following half month’s data as
validation dataset to find optimal parameters, and data from the remaining
half-month as test set. We compare the following algorithms:

  * •

implicit-cf[1]: a matrix factorization model for implicit datasets.

  * •

CDL[7]: a Bayesian model that learns a feature space from item information and
jointly trains with CF.

  * •

DCF[12]: a model that incorporates side information by marginalized denoising
stacked autoencoders with a matrix factorization model.

  * •

DHA-RNNED-s10: our model that learns a latent representation only from the
sequence of online purchases. The number of time steps in each sequence is 10.

  * •

DHA-RNNED-s5: our model with the same modeling process as DHA-RNNED-s10, but
using 5 time steps in each sequence.

  * •

DHA-RNNED-item: our model extracts features from sequential online purchases
at user side, and from shop genre descriptions at item side.

  * •

DHA-all: the proposed model that leverage non-sequential side information sets
and sequential online purchase activities simultaneously. The used time step
number of the purchase sequence is 10.

In the experiment, the joint learning is alternated 3 times, and we run 3
epochs for feature extraction every time. The number of hidden layers for CDL,
DCF and our model is set to 4, and 1 fusion hidden layer is used in DHA
models. For the sequential modeling, we set the hidden units of LSTMs to be
the same as the dimension of the user and item latent factor vector. The SGD
learning rate and regularization parameters for each model are found by grid
search on the validation set. We set the learning rate to 0.1 for implicit-cf
and CDL, to 0.001 for DCF and to 0.01 for the other models. The parameter to
regularize learned parameters is set to 2.0 for CDL, and 0.1 for DCF and DHA-
all. There is no training alteration for implicit-cf, but we run 25 iterations
to learn user and item latent factor vectors.

TABLE II: MAP@100 comparison on OfflinePay dataset. Results are shown for
different dimensions of the latent factor vector, $d$=50, 100, 150.

Models | d=50 | d=100 | d=150
---|---|---|---
implicit-cf | 0.0155 | 0.0178 | 0.0177
CDL | 0.0296 | 0.0336 | 0.0333
DCF | 0.0237 | 0.0311 | 0.0306
DHA-RNNED-s10 | 0.0327 | 0.0333 | 0.0339
DHA-RNNED-s5 | 0.0307 | 0.0343 | 0.0367
DHA-RNNED-item | 0.0394 | 0.0402 | 0.0345
DHA-all | 0.0424 | 0.0403 | 0.0361

DCF integrates both user registration information and shop genre descriptions,
while CDL uses only the latter one. DHA-RNNED-s10 and DHA-RNNED-s5 do not
include any side information except user online purchases. DHA-RNNED-item
adopts sequential data and shop genre descriptions, and DHA-all utilizes all
of the data. Note that since ratings are not used in any models, aSDAE is not
applied on OfflinePay dataset.

From Fig. 4, we observe that models taking advantage of side information have
better recall than the baseline implicit-cf. CDL outperforms DCF which, in
fact, uses more information sets. This may be due to the fact that many user
registration records have outdated or missing values, making the feature
extraction less accurate. Compared to CDL and DCF, the proposed models with
sequential data modeling achieve better recall. This is due to the fact that
offline shop genres in the dataset are included in the online purchased
genres. This also indicates that the latent features is able to be extracted
from recent online purchases accurately, and reflect the trends of user
interests, then lead to better recommendations for offline products, as well.
The MAP comparison in Table II shows that the models involving sequential
modeling achieve higher precision. This consistently shows that the modeling
of online purchases helps with offline product recommendation.

The recall comparison in Fig. 4 shows that DHA-RNNED-s10 and DHA-RNNED-s5 have
a similar trend as recommended item $M$ increases. These two models use only
the sequence of purchased genres from an online e-commerce platform, but with
different time steps in the sequence. it is also shown that DHA-all and DHA-
RNNED-item have similar recalls. The difference between these two models is
that the latter model does not include user registered data. Linking to the
previous observation that CDL outperforms DCF, user data does not
significantly contribute to the recommendation results.

In order to compare the effect of purchase recency of the input sequence, we
apply DHA-RNNED-s10 and DHA-RNNED-s5 to encode the recent ten and five
purchases, respectively. Our hypothesis is that more recent online purchases
are more representative of current user interests. Although the difference is
not big, the recall and MAP comparisons support our hypothesis. The
experiments demonstrate that with the independent autoencoder structure for
user and item side information and the modeling of user online activities, our
model is able to achieve competitive recall and MAP results.

##  V Conclusions

We proposed a model that incorporates multiple sources of heterogeneous
auxiliary information in a consistent way to alleviate the data sparsity
problem of recommender systems. It takes static and sequential data as input
and captures both the inherent tastes of users as well as the dynamics of user
preference. The model uses a flexible autoencoder structure for integrating
different data sources leading to significant performance gains.

## References

  * [1] Y. Hu, Y. Koren, and C. Volinsky, ”Collaborative filtering for implicit feedback datasets,” In Proc. Eighth IEEE ICDM, pages 263-–272, 2008.
  * [2] A. V. D. Oord, S. Dieleman, and B. Schrauwen, ”Deep content-based music recommendation,” In Proc. 26th International Conference on NIPS, Vol. 2, pp. 2643–2651, 2013.
  * [3] F. Zhang, N. J. Yuan, D. Lian, X. Xie, and W. Y. Ma, ”Collaborative knowledge base embedding for recommender systems,” In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 353–362, 2016.
  * [4] S. Oramas, O. Nieto, M. Sordo, and X. Serra, ”A deep multimodal approach for cold-start music recommendation” In Proceedings of the 2nd Workshop on Deep Learning for Recommender Systems, 2017.
  * [5] I. Porteous, A. Asuncion, and M. Welling, ”Bayesian matrix factorization with side information and dirichlet process mixtures,” In Proc. 24th AAAI, pp. 563–568, 2010.
  * [6] P. Loyola, C. Liu, and Y. Hirate, ”Modeling user session and intent with an attention-based encoder-decoder architecture,” In Proc. of 11th ACM Conference on Recommender Systems, pp. 147–151, 2017.
  * [7] H. Wang, N. Wang, and D. Y. Yeung, ”Collaborative deep learning for recommender systems,” In Proc. 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1235–1244, 2015.
  * [8] P. Vincent, H. Larochelle Y. Bengio and P.A. Manzagol, ”Extracting and composing robust features with denoising autoencoders,” In Proc. Twenty-fifth ICML, pp. 1096–1103, 2008.
  * [9] P. Vincent, H. Larochelle, I. Lajoie, Y. Bengio, and P. A. Manzagol, ”Stacked denoising autoencoders: learning useful representations in a deep network with a local denoising criterion,” JMLR, Vol. 11, pp. 3371–3408, 2010.
  * [10] W. Wang, R. Arora, K. Livescu, and J. Bilmes, ”On deep multi-view representation learning”, In Proc. 32nd ICML, Vol. 37, pp. 1083–1092, 2015.
  * [11] K. Cho, B. V. M, and C. Gulcehre, ”Learning phrase representations using RNN encoder–decoder for statistical machine translation,” In Proc. 2014 Conference on Empirical Methods in Natural Language Processing, pp. 1724–1734, 2014.
  * [12] S. Li, J. Kawale, and Y. Fu, ”Deep collaborative filtering via marginalized denoising auto-encoder,” In Proc. 24th ACM CIKM, pp. 811–-820, 2015.
  * [13] X. He, L. Liao, H. Zhang, L. Nie, X. Hu, and T. S. Chua, ”Neural collaborative filtering,” In Proc. 26th International Conference on WWW, pp. 173–182, 2017.
  * [14] L. Zheng, V. Noroozi, and P. S. Yu, ”Joint deep modeling of users and items using reviews for recommendation,” In Proc. Tenth ACM ICWDM, pp. 425–434, 2017.
  * [15] C. Y. Wu, A. Ahmed, A. Beutel, A. J. Smola, and H. Jing, ”Recurrent recommender networks,” In Proc. Tenth ACM ICWDM, pp. 495–-503, 2017.
  * [16] C. Wang, and D. M. Blei, ”Collaborative topic modeling for recommending scientific articles,” In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 448–456, 2011.
  * [17] S. Sedhain, A. K. Menon, S. Sanner, and L. Xie, ”AutoRec: autoencoders meet collaborative filtering,” In Proc. 24th International Conference on WWW, pp. 111–112, 2015.
  * [18] S. Zhang, L. Yao, and X. Xu, ”AutoSVD++: an efficient hybrid collaborative filtering model via contractive autoencoders,” In Proc. 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 957–960, 2017.
  * [19] X. Dong, L. Yu, Z. Wu, Y. Sun, L. Yuan, and F. Zhang, ”A hybrid collaborative filtering model with deep structure for recommender systems,” AAAI, 2017.
  * [20] I. Goodfellow, Y. Bengio, and A. Courville, ”Deep Learning,” MIT Press, 2016.