Workshop on SNL (CC-BY-SA 4.0)

Distributed Representations ofCompositional Structures
Methods using Circular Convolution
Katsuhiko Hayashi
Hokkaido University
Faculty of Information Science and Technology
katsuhiko-h@ist.hokudai.ac.jp

2023-06-29
1 / 32TODAY’S AGENDA▶ Background▶ Representation Learning with HRR▶ Circular HRR and Binary Spatter Codes

2 / 32TODAY’S AGENDA▶ Background▶ Representation Learning with HRR▶ Circular HRR and Binary Spatter Codes

2 / 32

Background: Structured Data(a) Sequence
bar.c
bar.h
foo.c
foo.txt(b) Tree(c) Graph
P

a

P

u

a a c c c u uDistributed Representations are attractive for modeling structured data:▶ Similarity: Convolution Kernel, Representation Learning, Semantic Hashing▶ Classiﬁcation: Multi-label Classiﬁcation, Structured Prediction
3 / 32

(1) Feature Extraction from Trees
S
NP
NNP

VBD

Federer won

VP

NP

VP
PP
IN

NP

against NNP
Nadal

=⇒

NNP

VBD

Federerwon

PP

0 1 0 0 0 0 1 0 0 ...
High Dimension

Trees are fundamental data structures used to represent very different objects
such as proteins, HTML documents, or NL utterances
Tree Kernel [NIPS2001] requires extracting all tree fragments that occur in a tree
▶ Dynamic Programming, Distributed Tree Kernel [ICML2011]
4 / 32

(2) Multi-label Classiﬁcation
1

Animalia

0
..
.

..
.

..
.

Mammalia
1..
.
0 Japanese macaque

..
.

1
Input

Macaca nigra

OutputHigh Dimension

5 / 32

(3) Representation Learning on Graphs
xT
u
u

=⇒
Rd
Feature Representation
Embeddings

Graph Representation Learning is to construct a set of features(“embeddings”) representing the structure (nodes/edges) of the graph▶ node classiﬁcation, link prediction, etc.

6 / 32

Holographic Reduced Representations
HRR is a method for representing compositional structure in distributed representation [IJCAI1991]
Eg.: Frame Structure “Mark eats the ﬁsh”
f = eat + agteat ∗ Mark + objeat ∗ Fishwhere ∗ is an encoding operator
HRR has a decoding operator
agteat ⋆ f ≈ Mark
7 / 32

HRR Encoding Operator ∗
[a]0

[a]1

[a]2

[b]0

[b]1

Circulant Matrix of a vector:[a]0 [a]2 [a]1circ(a) =  [a]1 [a]0 [a]2 
[a]2 [a]1 [a]0
Circulant Matrix circ(a) ∈ Rd×d can be
written as F−1
d diag (Fd a)Fd where Fd isthe d × d Fourier matrix[b]2[a ∗ b]j =d−1∑ [a]k[b](j−k)

k=0(for j = 0, . . . , d − 1)

Circular Convolution ∗:a ∗ b = circ(a)b = F−1
d (Fd a ⊙ Fd b)
8 / 32

HRR Decoding Operator ⋆
[a]0

[a]1

[a]2

[b]0

[b]1

The transpose of a circulant matrix of a vector:[a]0 [a]1 [a]2circ(a)T =  [a]2 [a]0 [a]1 
[a]1 [a]2 [a]0
Circular Correlation ⋆:[b]2a ⋆ b = circ(a)T b = F−1
d (Fd a ⊙ Fd b)
d−1[a ⋆ b]j =∑ [a]k[b](k+j)

k=0

z represents the complex conjugate of acomplex vector z(for j = 0, . . . , d − 1)
9 / 32

Why Correlation decodes Convolution?
Consider 3-dim. vectors c = [c0 , c1 , c2 ]T and x = [x0 , x1 , x2 ]T where ci and xi are
independently drawn from N(0, 1d ) (here, d = 3). The convolution of x and c is
c0 x0 + c1 x2 + c2 x1
m = c ∗ x =  c0 x1 + c1 x0 + c2 x2 
c0 x2 + c1 x1 + c2 x0
We could reconstruct x from this trace m by correlating with the cue c
x0 (1 + ζ ) + η0dd)c ⋆ c ∗ x =  x1 (1 + ζ ) + η1  ≈ x where ζ = N(0, 2d ) and ηi = N(0, d−1d2x2 (1 + ζ ) + η2
10 / 32

Multi-label Learning with HRR (1/4)
1Animalia

0
..
.

..
.

..
.

Mammalia
1..
.
0 Japanese macaque

..
.

1
Input

Macaca nigra

OutputHigh Dimension

11 / 32

Multi-label Learning with HRR (2/4)“Learning with Holographic Reduced Representations”,
Ganesan et. al., NeurIPS, 2021.
We begin by converting each class label into a label vector y ∈ Rd
▶ d is much smaller than the size of the set of output classes: d ≪ L▶ All vector elements are sampled according to N(0, 1d )AnimaliayA...

Mammalia
yMamma...

Japanese macaqueyJ

Macaca nigra
yMacaca

11 / 32

Multi-label Learning with HRR (3/4)“Learning with Holographic Reduced Representations”,
Ganesan et. al., NeurIPS, 2021.
Using the HRR framework, we construct a label vector yx for a given data x

yx= yP ∗ (yA + yMamma + · · · + yMacaca ) +yN ∗ (· · · + yJ )|{z}
| {z }
tP

tN

11 / 32

Multi-label Learning with HRR (4/4)“Learning with Holographic Reduced Representations”,
Ganesan et. al., NeurIPS, 2021.
Training Phase:Label vector yx

..
.

..
.

..
.

11 / 32

Multi-label Learning with HRR (4/4)“Learning with Holographic Reduced Representations”,
Ganesan et. al., NeurIPS, 2021.
Inference Phase:..
.

Key vector yP

..
.

..
.

⋆

≈ tP
t ≤ yT
A tP ?

11 / 32

Why Addition Memories work well?
One way to store k vectors is to add them together: t = a + b + c (k = 3)
Such storage does allow for determining whether an item has been stored or not
To test whether a vector x is in the tracet, we compute the dot product:sAccept = aT tsReject = dT t

x=a
x=d

sAccept and sReject are distributed as:
dsAccept = N(1, (k+1)
d )dksReject = N(0, d )k = 3 and d = 64
RejectAccept

2
1.5
1
0.5
0
−1

0

1

2
12 / 32

TODAY’S AGENDA▶ Background▶ Representation Learning with HRR▶ Circular HRR and Binary Spatter Codes

13 / 32

Deﬁnition: RDF Knowledge Base
SpockplayedSciFicharacterIn

genre

starredIn
Leonard Nimoy
Star Trek

Obi-Wan Kenobi

genre

characterInplayedstarredInStar Wars
Alec Guinness

KB K is a set of facts▶ fact: a triple of the form (s, r, o) (alternative notation r(s, o))▶ s/o is the subject/object, r is the relation (or predicate)
14 / 32

KB Example: DBPedia
DBPedia [Semantic Web2013]: A project aiming to extract structured content from
Wikipedia information

https://www.dbpedia.org/
15 / 32

Open Knowledge Bases
The research on Semantic Web and Linked Data led to many open datasets
These open datasets are rebranded as “Knowledge Graphs”▶ DBPedia, Freebase, YAGO, NELL, Wikidata, KBPedia, Datacommons.org
Many open Knowledge Bases are sourced from Wikipedia and also beneﬁted from
unstructured corpus for their building process
Problem: KBs are imcomplete and have many missing links▶ 93.8% of persons from Freebase have no place of birth and 78.5% have nonationality

16 / 32

Representation Learning on KBs
SignalOutputy = Japan0 0 0 ... 0 0 1 ... 0 0 0...

Learning: minimize errors
between signal and output
Loss Function:e.g. Cross-Entropy Loss

...
− log

HiddenInput
x = Tokyo / isCapitalOf

exp (fθ (x, y))∑y′ ∈Y exp (fθ (x, y′ ))“Knowledge Graph Embedding: A
Survey of Approaches andApplications”,
Wang et. al., IEEE TKDE, 2017.
17 / 32

Our work: Loss Functions
We also have studied loss functions for Knowledge Graph Embeddings:
1. “Uniﬁed Interpretation of Softmax Cross-Entropy and Negative Sampling: With
Case Study for Knowledge Graph Embedding”,
Hidetaka Kamigaito and Katsuhiko Hayashi, ACL, 2021.
2. “Comprehensive Analysis of Negative Sampling in Knowledge Graph
Representation Learning”,
Hidetaka Kamigaito and Katsuhiko Hayashi, ICML, 2022.
For the details, refer to a tutorial by Hidetaka Kamigaito▶ https://stair.center/archives/3111
18 / 32

Scoring Functions
SignalOutputy = Japan
.
.
.
0 0 0
0 0 1 ... 0 0 0
...

...

Scoring Function fθ (x, y):designed to measure the plausibilityof triples
e.g. RESCAL model [ICML2011]fθ (x = s/r, y = o) = eTs Wr eo

HiddenInput
x = Tokyo / isCapitalOf“Knowledge Graph Embedding: A
Survey of Approaches andApplications”,
Wang et. al., IEEE TKDE, 2017.

19 / 32RESCAL Model [ICML2011]
Each relation is represented as a matrix
which models pairwise interactions
between latent factors:

fRESCAL (s, r, o)

fRESCAL (s, r, o) = eTs Wr eoWr
eseo“A Three-Way Model for Collective
Learning on Multi-Relational Data”,
Nickel et. al., ICML, 2011.

RESCAL requires O(d2 ) parameters per
relation
RESCAL is fully expressive: If given any
ground truth, there exists an assignment ofvalues to the embeddings of the entities andrelations that accurately separates thecorrect triples from incorrect ones
20 / 32

HolE Model [AAAI2016]
HolE requires only O(d) parameters per
relation

fHolE (s, r, o)fHolE (s, r, o) = wTr (es ⋆ eo )
wr
es

eo

“Holographic Embeddings ofKnowledge Graphs”,
Nickel et. al., AAAI, 2016.

Since circular correlation ⋆ is notcommutative, i.e., x ⋆ y ̸= y ⋆ x, HolE is able
to handle asymmetric relations as RESCAL
does (fully expressive)
HRR memory: eo = ∑r′ (s′ ,o)∈K es′ ∗ wr′
acts as a memory m that stores the set of all
s-r pairs for which r′ (s′ , o) is true
21 / 32

Circular Correlation
[a]0

[a]1

[a]2

[b]0

Circular correlation via the Discrete Fourier
Transform can be computed in O(d log d) time[b]1

fHolE (s, r, o) = wTr (ys ⋆ yo )−1
= wT
r F (F(ys ) ⊙ F(yo ))

[b]2

d−1

[a ⋆ b]j =∑ [a]k[b](k+j)

where F is the discrete Fouriertransform (DFT) and F−1 is the inverse DFT

k=0(for j = 0, . . . , d − 1)
22 / 32

Spectral HolE Model [ACL2017]“On the Equivalence of Holographic and Complex Embeddings for Link Prediction”,
Hayashi and Shimbo, ACL, 2017.
operation timescalar mult.
αxsummation x + y
ﬂip ﬂip(x)convolution x ∗ ycorrelation x ⋆ y
dot product xT y

↔
↔
↔
↔
↔
=

frequency
α F(x)
F(x) + F(y)F(x)F(x) ⊙ F(y)F(x) ⊙ F(y)1Tn F(x) F(y)We proposed a method how to train
HolE solely in the frequency domain
fHolE (s, r, o) = wrT (ys ⋆ yo )1 T=
ω (ε s ⊙ ε o )n rwhere ω r = F(wr ), ε s = F(es ) andε o = F(eo ) are d-dim. complex
vectors
23 / 32

ComplEx Model [ICML2016]
Embedding space = complex space (notreal space)

fComplEx (s, r, o)d−1

fComplEx (s, r, o) = ℜ( ∑ [es ]i [wr ]i [eo ]i )

wr
es

i=0

eo

“Complex Embeddings for Simple Link
Prediction”,
Trouillon et. al., ICML, 2016.

where ℜ(·) means taking the real partof a complex value
ComplEx = HolE [Hayashi, ACL2017]
2
fHolE (s, r, o) = fComplEx (s, r, o)d
24 / 32

ComplEx is Simple but Tough to Beatmean reciprocal rank (MRR)

KGC performance on FB15k-237
36

36
34.6
33.6 33.8

34
32.9

FB15k-237: KGC benchmark dataset
RotatE [ICLR2019] andHAKE [AAAI2020] are current SoTamodels

32
29.6

30

C atE KEult plEx tARGES
KG Rot HA
-K
m
m
N
Si
Co
kN

M
ist

D

29.6

ComplEx also achieves comparable
results with StAR [TACL2021],
SimKGC [ACL2022] andkNN-KGE [2023], which are KGC
models based on LLMs

25 / 32

TODAY’S AGENDA▶ Background▶ Representation Learning with HRR▶ Circular HRR and Binary Spatter Codes

26 / 32

HRR (Notify Again)
HRR is a method for representing compositional structure in distributed representation [IJCAI1991]
Eg.: Frame Structure “Mark eats the ﬁsh”
f = eat + agteat ∗ Mark + objeat ∗ Fishwhere ∗ is an encoding operator
HRR has a decoding operator
agteat ⋆ f ≈ Mark
27 / 32

Complex-valued HRR System
It might be possible to work with complex numbers and avoid convolution andFourier transforms altogether
Initialization of HRR vectors:
operation timescalar mult.
αxsummation x + y
ﬂip ﬂip(x)convolution x ∗ ycorrelation x ⋆ y
dot product xT y

↔
↔
↔
↔
↔
=

frequency
α F(x)
F(x) + F(y)F(x)F(x) ⊙ F(y)F(x) ⊙ F(y)1Tn F(x) F(y)x′ = F(x = [x0 , . . . , xd−1 ]T )dwhere xi = N(0, 1d )We have correspondence between
operations in time and frequency
domains

28 / 32

Circular HRR System
Tony A. Plate proposed circular HRR system in his thesis [1994]:
The polar form of a complex
number:operation
vectorϕ̄ = [ϕ0 , . . . , ϕd−1 ] wheredϕi = U(−π , π )dot product ϕ̄ · θ̄ = 1d ∑i cos (ϕi − θi )bindingϕ̄ ⊙ θ̄ = [(ϕ0 + θ0 )mod2π , . . . ,(ϕd−1 + θd−1 )mod2π ]decoding−ϕ̄ ⊙ θ̄
additionϕ̄ ⊕ θ̄ = [ζ0 , . . . , ζd−1 ] wherecos (ζi ) = cos(ϕi ) + cos(θi ) andsin(ζi ) = sin(ϕi ) + sin(θi )Im(cos ϕ , sin ϕ )ϕRe

29 / 32

Relationship to Binary Spatter Coding
Binary spatter codes (BSC) [Kanerva,1996] are identical to the circular HRR
system working on unitary vectors with phase angles quantized to 0 and π▶ The two possible values 1 + 0i and −1 + 0i
BSC use exclusive-OR (XOR) for binding binary vectors▶ Elementwise multiplication of complex vectors whose elements can be 1 + 0i or−1 + 0i is equivalent to XOR (more strictly, the logical complement of
XOR (XNOR))
BSC use the majority rule for the addition of a set of vectors▶ the sum of such vectors followed by elementwise quantization to 1 + 0i or−1 + 0i is equivalent to computing the elementwise majority
30 / 32

Our work: Binarized Embeddings
Other papers:

fBinary (s, r, o)
wr
es

eo

“Binarized Knowledge Graph Embeddings”, Kishimoto et. al., ECIR, 2019.
▶ Scoring Function fBinary (s, r, o):−Ham(es , XNOR(eo , wr ))▶ “A Greedy Bit-ﬂip Training Algorithm
for Binarized Knowledge Graph
Embeddings”,
Katsuhiko Hayashi, Koki Kishimoto,
Masashi Shimbo, Findings of EMNLP,
2020.
▶ “Binarized Embeddings for Fast,
Space-Efﬁcient Knowledge Graph
Completion”,
Katsuhiko Hayashi, Koki Kishimoto,
Masashi Shimbo, IEEE TKDE, 2023.
31 / 32

Conclusion
I introduced a method using circular convolution for encoding compositional
structured data into low-dimensional vector space▶ Multi-label Learning with HRR▶ Graph Representation Learning with HRR▶ Complex/Binary-valued HRR Systems
I am now interested in designing more effective vector symbolic architechtures
I seek a research collaborator▶ Please feel free to contact me: katsuhiko-h@ist.hokudai.ac.jp

32 / 32