# The Devil is in the Details: Complexity Powered Machine Intelligent
Classification of Quantum Many-Body Dynamics

Zhaoran Feng  Center for Phononics and Thermal Energy Science, China-EU Joint
Lab on Nanophononics, Shanghai Key Laboratory of Special Artificial
Microstructure Materials and Technology, School of Physics Science and
Engineering, Tongji University, Shanghai 200092, China  Jiangzhi Chen  Center
for Phononics and Thermal Energy Science, China-EU Joint Lab on Nanophononics,
Shanghai Key Laboratory of Special Artificial Microstructure Materials and
Technology, School of Physics Science and Engineering, Tongji University,
Shanghai 200092, China  Ce Wang<EMAIL_ADDRESS>Center for Phononics and
Thermal Energy Science, China-EU Joint Lab on Nanophononics, Shanghai Key
Laboratory of Special Artificial Microstructure Materials and Technology,
School of Physics Science and Engineering, Tongji University, Shanghai 200092,
China  Jie Ren<EMAIL_ADDRESS>Center for Phononics and Thermal Energy
Science, China-EU Joint Lab on Nanophononics, Shanghai Key Laboratory of
Special Artificial Microstructure Materials and Technology, School of Physics
Science and Engineering, Tongji University, Shanghai 200092, China  Shanghai
Research Institute for Intelligent Autonomous Systems, Tongji University,
Shanghai 200092, P. R. China

###### Abstract

Identifying and classifying quantum phases from measurable time series in
many-body dynamics have significant values, yet face formidable challenges,
requiring profound knowledge of physicists. Here, to achieve a pure data-
driven machine intelligent classification, we introduce a complexity boosted
distance measure that captures the inherent complexity of dynamic evolution
series in different quantum many-body phases. Significantly, the introduction
of complexity-boosted distance leads to remarkable improvements of
unsupervised manifold learning of quantum many-body dynamics, which are
exemplified in discrete time crystal model, Aubry-André model, and quantum
east model. Our method does not require any prior knowledge and exhibits
effectiveness even in imperfect, disordered, and noisy situations that are
challenging for human scientists. Successful classification of dynamic phases
in many-body systems holds the potential to enable crucial applications,
including identification of tsunamis, earthquakes, catastrophes and future
trends in finance.

Introduction— Non-equilibrium quantum many-body systems have always incited
great interest, encompassing active fields such as Floquet evolution [1, 2, 3,
4, 5], quench dynamics [6, 7, 8, 9, 10], and quantum open systems [11, 12, 13,
14]. The dynamical processes of these systems lead to a variety of fascinating
quantum phenomena, such as discrete time crystals (DTC) [15, 16, 17, 18],
many-body localization (MBL) [19, 20, 21, 22, 23], and prethermalization [24,
25, 26, 27]. However, the theoretical study of these processes poses a
significant challenge as analytical and numerical tools quickly reach their
limits with increasing system size. Even for non-interacting system, the
classification of phases become highly complicate, such as the 54 non-
equivalent topological class for open system [28]. Facing these challenges, we
aimed to explore the use of artificial intelligence for identifying and
classifying quantum many-body dynamical phases through a purely data-driven
approach.

Recently, machine learning has demonstrated its potential in condensed matter
physics [29, 30], quantum domains [31, 32], and topological physics [33, 34].
For instance, it has been used for the classification of topological phononics
[35], the inverse design of topological optics [36], and the optimization of
metamaterial devices [37]. However, the majority of these studies emphasize
supervised learning, which depends on a large number of samples with clear
labels. For those systems that are not well-understood by human scientists,
unsupervised machine learning offers a valuable and effective method for
identifying and classifying patterns in data without the need for prior
knowledge [38, 39, 40, 41]. Lots of efforts have been made along this
direction, from the principal component analysis for classical statistical
models [42, 43, 44, 45, 46, 47] to the diffusion mapping for the topological
transition [48, 49, 50, 51, 52]. In these works, the dataset includes only the
static features of the system, such as the micro configuration of statistical
models or the ground-state wave functions. However, for dynamic processes that
involve time series data, one needs to find new paradigms that is compatible
with the temporal characteristics of the data.

Figure 1: Schematic diagram illustrating the effect of complexity power: (a)
Time series: Quantum many-body dynamics process depicting feature quantities
evolving over time; (b) How to measure complexity: Quantum many-body dynamics
complexity measured by stretching ; (c) The impact of the frequency of dynamic
processes on complexity. The larger the proportion of high-frequency
components, the higher the complexity of the time series; (d) The impact of
the frequency of distance on boosted power. The complexity can amplify
frequency differences between time series while the boosted power can further
enhance this difference; (e) Classification of observable quantities based on
boosted power. As $\beta$ increases, the classification results gradually
transition from incorrect to accurate.

In this letter, we introduce the complexity [53, 54, 55, 56] of time series,
successfully extracting dynamic features from time series and innovatively
proposing a complexity-powered distance to measure the similarity between the
time series of physical quantities. When combined with the widely-used
diffusion mapping algorithm, we find this complexity-powered distance
accurately determines the position of phase transitions, a task at which the
Euclidean distance fails. We check the benefits of this complexity-powered
distance on various dynamical processes, including the evolution of DTC, the
quench dynamics of Aubry-André model, and the quench dynamics of quantum east
model, across different physical quantities.

Complexity enhancement— We first define the general form of time series data
as $\mathbf{D}\equiv[\mathbf{O}(t_{0}),\mathbf{O}(t_{0}+\delta
t),...,\mathbf{O}(t_{h})]$. This represents a set of values for one or more
physical quantities at equally spaced time intervals. The halting time
$t_{h}=t_{0}+(L_{s}-1)\delta t$ such that $\mathbf{D}$ is a sequence of length
$L_{s}$ and we shorten $\mathbf{O}(t_{0}+(l-1)\delta t)$ as $\mathbf{O}_{l}$ .
Different indexes $i$ are then assigned to data $\mathbf{D}_{i}$ collected
under various system parameters.

A crucial step in using unsupervised learning methods to cluster data and
identify phase transition is to define the distance between different data
sets. One natural choice is to use the Euclidean distance as
$M_{ij}=\lVert\mathbf{D}_{i}-\mathbf{D}_{j}\rVert_{2}$ which is widely used in
previous papers. However, the similarity between two sequences is determined
not only by their distance at corresponding time, but also by their
fluctuation patterns. As shown in Fig. 1(a), two sequences with a small
Euclidean distance might have very different fluctuation patterns. Conversely,
two sequences displaying similar patterns may have a large Euclidean distance.
Therefore, we need to propose a distance definition that balances the
Euclidean distance and the similarity of fluctuation patterns between
sequences.

Here, we use the “complexity” to quantitatively describe the fluctuation
patterns of sequences [56]. The complexity for data $\mathbf{D}$ is defined as

$C(\mathbf{D})=\sqrt{\sum_{l=1}^{L_{s}-1}\left\Arrowvert\mathbf{O}_{l}-\mathbf{O}_{l-1}\right\Arrowvert^{2}_{2},}$
(1)

which can be visualized as the stretching length of the temporal sequence as
illustrated in Fig. 1(b) . According to Fig. 1(c), as the frequency of the
major oscillating pattern in the time series increases, the complexity also
increases. The complexity of the time series thus highlights the high-
frequency features of the sequences.

We apply complexity to measure distances between sequences. The complexity-
powered distance is given by the following formula [57]:

$\tilde{M}_{ij}=E^{\beta}_{ij}M_{ij}$ (2)

where the complexity boosted factor
$E_{ij}=\text{max}\\{C_{i}+\delta,C_{j}+\delta\\}/\text{min}\\{C_{i}+\delta,C_{j}+\delta\\}$,
$\delta$ is a cutoff to avoid the divergence when the complexity is zero and
$\beta\geq 0$ is the boosted power to adjust the weight of the complexity
enhancement.

For a non-zero $\beta$, when two sequences $\mathbf{D}_{i},\mathbf{D}_{j}$
have similar complexities, $E^{\beta}_{ij}$ is close to unitary, meaning that
their distance $\tilde{M}_{ij}$ is approximately the original Euclidean
distance $M_{ij}$. However, when the complexities of the two sequences differ
greatly, $E^{\beta}_{ij}$ will be much larger than one, significantly
increasing the distance $\tilde{M}_{ij}$ compared to $M_{ij}$. Specifically,
we can intuitively consider an dataset in which each sequence is a sine wave
oscillating with the same amplitude but different frequencies. Their
complexity-powered distances from a reference sequence whose elements are all
zeros at different $\beta$ are shown in Fig. 1(d). All different sequences
have the same Euclidean distances ($\beta=0$) from the reference sequence (the
original point). However, for $\beta>0$, the complexity-powered distances
increase as the frequency increases, and this amplification becomes more
significant for larger $\beta$.

For more general data such as the ones in Fig. 1(a), we obtain
$C(\mathbf{D_{1}})<C(\mathbf{D_{2}})\approx C(\mathbf{D_{3}})$ since the
amplitude of high-frequency components in $\mathbf{D_{1}}$ differs greatly
from $\mathbf{D_{2}},\mathbf{D_{3}}$. As shown in Fig. 1(e), $\mathbf{D_{2}}$
is closer to $\mathbf{D_{1}}$ measured by the Euclidean distances. When
$\beta$ increases from zero, $\mathbf{D_{2}}$ gradually becomes distant from
$\mathbf{D_{1}}$ and gets closer to $\mathbf{D_{3}}$, indicating a very
different classification can be obtained with the complexity-powered distance
at large $\beta$.

Meanwhile, Euclidean distance is equally crucial, relying solely on $E_{ij}$
for classification also not achieve optimal results. Regarding this point, we
will incorporate specific examples and present the results in the
supplementary materials [58].

Figure 2: The unsupervised phase classification of DTC model: (a) Floquet
evolution of DTC model. Two Hamiltonians are applied sequentially in time: a
system-wide rotation($\hat{H}_{1}$) and nearest disorded interactions
($\hat{H}_{2}$). (b) The time-dependent evolution of the expectation for the
$Z$ operator on the first site. (c) The two-dimensional phase diagram is
obtained by clustering dataset consists of sequences collected at different
$g$ and $J_{\text{tpy}}$ based on complexity-boosted distance. The cluster
boundaries marked by the black crosses is consistent with the theoretical
phase diagram (the orange / red / green / blue region represents the $0\pi$
paramagnetic / ferromagnetic / paramagnetic / $\pi$ ferromagnetic phase). (d)
The LE data collected at $g=0.145\pi$, $g=0.185\pi$ and $g=0.325\pi$ for
$J_{\text{typ}}=0.3\pi$, they are marked as red square, red diamond and blue
triangle in (c), respectively. (e) The low-dimensional representation by the
linear combination of the second and third eigenstates of the transfer matrix,
$\bar{\phi}_{2}=\cos\alpha\phi_{2}-\sin\alpha\phi_{3}$ and
$\bar{\phi}_{3}=\sin\alpha\phi_{2}+\cos\alpha\phi_{3}$ based on $\log(\beta)$
from $-\infty$ to $2$. The data set is collected for varies $g$ at
$J_{\text{tpy}}=0.3\pi$ (blue dotted line in (e)) and the illustration
displays the first six eigenvalues of the transfer matrix.

Diffusion map\- Once the distance between the data is defined, we can discover
the underlying manifold for a given dataset by the diffusion map algorithm
[59, 60, 61, 62, 63], thereby achieving dimension reduction and clustering.
The similarity matrix is then given by a Gaussian kernel,

$K_{ij}={\rm exp}\left(-\frac{\tilde{M}_{ij}}{2\epsilon L_{s}^{2}}\right),$
(3)

where $\epsilon$ is the Gaussian kernel coefficient. Using Eq. (3), we obtain
the similarity matrix of $N$ randomly sampled Hamiltonians in the parameters
space, i.e., $K_{ij}\xrightarrow{}1$ if two samples are similar, otherwise,
$K_{ij}\xrightarrow{}0$. The probability transition matrix is defined as
$P_{ij}=K_{ij}/\sum_{j=1}^{N}K_{ij}$ to describe the diffusion progress. After
$t$ steps, the diffusion distance between sample $i$ and $j$ on the manifold
is
$d^{t}_{ij}=\sum_{n}[(P_{in}^{t}-P_{jn}^{t})^{2}/\sum_{n^{\prime}}K_{nn^{\prime}}]=\sum_{n=1}^{N-1}\lambda_{n}^{2t}[(\phi_{n})_{i}-(\phi_{n})_{j}]^{2}$,
where $\phi_{n}$ is the $n$-th right eigenvectors of $\hat{\mathbf{P}}$ and
$\lambda_{n}$ is the $n$-th eigenvalue, $n=0,1,...,N-1$. After long time
diffusion, the first few components $\phi_{n}$ that have the largest
eigenvalues $\lambda_{n}\approx 1$ will dominate in the manifold diffusion
process. Consequently, the prime information of the manifold diffusion
distance is encoded within these few components and they form a low-
dimensional representation of the original sequential data. The phase
classification can be obtained by clustering those low-dimensional
representation. Next, we will apply this diffusion map algorithm based on
complexity-boosted distance to different dynamical quantum systems.

Figure 3: The unsupervised clustering of AA model: (a)The LE data collected at
$h=1.85$, $h=2.05$ and $h=2.35$ for $V=0$, they are marked as blue square, red
diamond and red triangle respectively. (b) The first six eigenvalues of the
transfer matrix $P$ with Euclidean distance (above) and complexity-boosted
distance (below). (c) The low-dimensional representation, captured by the
second eigenstates of the transfer matrix, is denoted by blue and red points
using both Euclidean (lighter shade) and complexity-boosted distances (darker
shade). The silhouette coefficient of the classification with $h$ images,
represented by orange lines, shows results under both Euclidean (lighter
shade) and complexity-boosted distances (darker shade); (d) At $V=0.75$, the
first six eigenvalues of the transfer matrix $P$ with complexity-boosted
distance (high). The low-dimensional representation, captured by the third
eigenstates of the transfer matrix, is denoted by blue , green and red points
using complexity-boosted distances with the The silhouette coefficient of the
classification with $h$ images, represented by orange lines; (e) The two-
dimensional phase diagram is obtained from time sequences using the time-
dependent density matrix renormalization group (DMRG) based on obtained
complexity-powered distance .

Discrete time crystal model— The spontaneous breaking of time-translation
symmetry is a dynamic phenomenon that only occurs in non-equilibrium systems
[64, 65, 66, 67, 68, 69]. In order to realize the breaking of time symmetry,
periodically driven Floquet systems are widely concerned [15, 70, 71, 16, 17,
72, 18]. In these systems, discrete time-translation symmetry may be further
broken, manifested as double period oscillation for some physical quantities.
We consider the Floquet quantum dynamics of 1D disorder spin chains, which is
described by the following Floquet Hamiltonian [72],

$\hat{H}_{\text{DTC}}(t)=\begin{cases}\hat{H}_{1}=g\sum_{j=1}^{L}\hat{\sigma}_{j}^{x},\quad&0\leq
t\leq t_{1}\\\
\hat{H}_{2}=\sum_{j=1}^{L-1}J_{j}\hat{\sigma}_{j}^{z}\hat{\sigma}_{j+1}^{z}.\quad&t_{1}\leq
t\leq t_{1}+t_{2}\end{cases}$ (4)

Here, $\hat{\sigma}_{j}^{\gamma}(\gamma=x,y,z)$ is the Pauli operator acting
on the $j^{\text{th}}$ spin, $g$ is the Rabi frequency, and $J_{j}$ is the
random coupling strength between spins $j$ and $j+1$. The distribution of
$J_{j}$ is described by a typical strength $J_{\text{typ}}$ as $\ln
J_{\text{typ}}=\frac{1}{L}\ln J_{j}$ ,where their logarithms have a standard
deviation $\sigma_{J}=0.02\pi$. We choose $t_{1}=t_{2}=1$ such that the
Floquet driven has a period of $T=2$. The so-called discrete time symmetry
broken can be realized by setting $g=\frac{\pi}{2}$, where a product state
with all the spins parallel to $z$-direction will return back to itself after
two Floquet periods. Interestingly, under the random interacting process
captured by $\hat{H}_{2}$, this double period temporal pattern is stable even
when $g$ is deviated from $\pi/2$.

Fig. 2(a) depicts the Floquet evolution of a spin chain, where two
Hamiltonians are sequentially applied over time: a nearly $\pi$ global spin
flip (H1) followed by disorder interactions (H2). The varying time-evolved
magnetizations of spins $\left\langle\sigma_{i}^{z}(t)\right\rangle$ exhibit
different sub-harmonic responses of the system to the Floquet Hamiltonian in
Fig. 2(b). A complete phase diagram for this Floquet process contains four
different phases as shown in Fig. 2(c) [73]. The ferromagnetic ($FM$) phase
exhibits long-range order and spontaneous Ising symmetry breaking, while the
$\pi$ferromagnetic ($\pi FM$) phase shows stable long-range order independent
of Ising symmetry. The $0\pi$paramagnetic ($0\pi PM$) phase lacks long-range
order but includes non-trivial edge modes and the potential for time-
translation symmetry breaking. Conversely, the paramagnetic ($PM$) phase lacks
both long-range order and spontaneous symmetry breaking.

Here, we employ the Loschmidt echo (LE) as the temporal feature [74, 75, 76,
77]. The LE is defined by the overlap between the initial state
$|\psi_{0}\rangle$ and the state $|\psi_{t}\rangle$ at time $t$ as
$\mathcal{L}(t)=|\langle\psi_{0}|\psi_{t}\rangle|^{2}$. Notice this model is
solvable under Jordan-Wigner transformation, we are able to obtain the LE
exactly for a sufficiently large system. The input sequential data is then
collected at each Floquet period as $\mathbf{O}_{l}=\mathcal{L}(2l)^{1/L}$
where the exponential factor $1/L$ is introduced to eliminate the effect of
the Anderson’s orthogonal catastrophe. The dataset consists of sequences
collected at different $g$ for fixed $J_{\text{typ}}$. By applying the
diffusion map based on complexity enhanced distance to the dataset, we find
the first three eigenvalues $\lambda_{n}\approx 1$, indicating three different
phases are recognized by the algorithm. The phase transition points are then
determined by the clustering with largest silhouette-coefficient [58]. By
varying $J_{\text{typ}}$ for the dataset, we obtain a phase diagram which is
consistent with the theoretical result as shown in Fig. 2(c).

To illustrate the essential role of complexity enhancement, we compare the
result with the diffusion map based on increase boosted power $\beta$ for the
dataset with $J_{\text{typ}}=0.3\pi$. As shown in Fig. 2(e), the diffusion map
base on $\beta=0$ fails to distinguish those three phases. As the $\beta$
increase, we find the diffusion map based on the complexity enhanced distance
gradually identifies all three phases correctly. To be more clear, we select
three data points marked in Fig. 2(c) for $J_{\text{typ}}=0.3\pi$ with the LE
sequences shown in Fig. 2(d). These are labelled by a blue triangle at
$g=0.325\pi$ in the $\pi$ ferromagnetic phase and a red diamond/square at
$g=0.185\pi/0.145\pi$ in the ferromagnetic phase. When measured only by the
Euclidean distance, the LE sequence for the red diamond appears more similar
to the blue triangle than the red square. As a result, it gets mixed up at
$\beta=0$ with the $\pi$ ferromagnetic phase data. However, by increasing
$\beta$, the distance between the blue triangle and the red diamond increases
due to the complexity difference. When $\beta=10$, the dataset is classified
into three well-separated clusters. The process of identifying is shown in
Fig. 2(e). The details of the hyperparameters for this model are included in
the Supplementary Material [58]. Moreover, to further verify the results, the
cases with quantum Ising model are listed in the Supplemental Material [58].

Aubry-André model—To further demonstrate the universality of our method, we
consider the dynamic process for the Aubry-André (AA) model[78]. The
Hamiltonian of the AA model is given by:

$\hat{H}_{AA}=\sum_{j=0}^{L-1}\left[h_{j}\hat{n}_{j}+J(\hat{c}_{j}^{\dagger}\hat{c}_{j+1}+\hat{c}_{j+1}^{\dagger}\hat{c}_{j})+V\hat{n}_{j}\hat{n}_{j+1}\right].$
(5)

Here, $c_{j}(c_{j}^{\dagger})$ represents the fermion annihilation (creation)
operator on site $j$, and $n_{j}=c_{j}^{\dagger}c_{j}$ denotes the
corresponding density operator. The quasi-periodic onsite potential is denoted
by $h_{j}=h\cos(2\pi kj+\delta)$, where $k=\frac{\sqrt{5}-1}{2}$. The terms
$J$ is the nearest-neighbor hopping and set to be $1$ as the energy unit,
while $V$ represent the nearest-interaction. In the non-interacting limit,
where $V=0$, the system is known to undergo a localization-delocalization
transition for the single particle eigen-state at the self-dual point $h=2$.
In the interacting case with $V>0$, a transition from the thermal phase to the
MBL phase also occurs, however, there are still different conclusions about
the specific position of the phase transition according to our best knowledge
[79, 80].

We then investigate the phase transition in AA model with our method. We
consider the dynamical process given by the evolution from fixed initial state
$|\psi_{0}\rangle$ under $\hat{H}_{AA}$, specially, we set the initial state
$|\psi_{0}\rangle$ to be a product state at $1/4$ filling, where particles are
evenly localized on the $j$-th site with $j=0\pmod{4}$. Each element of the
input sequential data is the LE collected at different times $t=(l-1)\delta
t$, represented as $\mathbf{O}_{l}=\mathcal{L}(t)^{1/N_{p}}$. Here, $N_{p}$ is
the total particle number, and we introduce an exponential factor of $1/N_{p}$
to mitigate the effect of Anderson’s Orthogonality Catastrophe. The dataset
comprises LE sequences for various $h$ at fixed $V$.

For the non-interacting case, three LE sequences near both sides of the
transition point $h=2$ are illustrated in Fig. 3(a) and no significant
differences can be found by human eyes. Thus, it’s reasonable to expect that
clustering based on Euclidean distance can not identify the transition point
accurately. As depicted in Fig. 3 (b), the transition matrix for $\beta=0$ has
only one eigenvalue closed to one, indicating the diffusion map cannot
distinguish the two phases. However, with $\beta=10$, we find two eigenvalues
near to one. Plotting the elements of $\phi_{2}$ as function of $h$ and the
silhouette coefficient for clustering as in Fig. 3 (c), we notice a
significant leap at $h=2$, which coincides perfectly with the theoretical
phase transition point [79].

For the interacting case, we generate the LE data with the time-dependent
density matrix renormalization group (t-DMRG) method at $V=0.75$.
Interestingly, three different phases are recognized by the complexity
enchanced diffusion map in Fig. 3 (d). This result matches the three phases
obtained in a previous paper [80]. Based on $\beta=10$, we obtained the phase
diagram of the AA model, illustrating the thermal phase, slow dynamics phase,
and many-body localized phase, as depicted in Fig. 3 (e). More details with
interactions are presented in the supplementary material [58].

Quantum east model— The LE has demonstrated excellent results in the previous
two models. However, it may not always be the right feature capturing the
information about phase transition. Hence, we illustrate that the complexity
enhancement can also uncover phase transition from other temporal features by
studying the dynamics of quantum east model.

Figure 4: The unsupervised clustering of QE model: Under the parameters $L=10$
, $s=-0.94:0.04:1$ , $L_{s}=20$, $\delta_{t}=1$ (a) The first ten eigenvalues
of the transfer matrix $P$ with Euclidean distance (higher) and complexity-
boosted distance (lower); (b) The LE data collected at $s=-0.18$, $s=-0.06$
and $s=0.06$ , they are marked as blue square, blue diamond and red triangle
respectively. The corresponding complexities are: $C(s=-0.18)=7.1813$,
$C(s=-0.06)=7.3248$, $C(s=0.06)=8.5084$; (c,d)The low-dimensional
representation, captured by the second eigenstates of the transfer matrix, is
denoted by blue and red points using both (c) Euclidean (lighter shade) and
(d) complexity-boosted distances (darker shade). The silhouette coefficient of
the classification with $s$ images, represented by orange lines, shows results
under both Euclidean (lighter shade) and complexity-boosted distances (darker
shade).

The quantum East (QE) model is an interacting quantum spin chain inspired by
simple kinetically constrained models of classical glasses. QE model has a
transition from a thermalizing phase where relaxation is fast to a phase of
slow relaxation, where dynamics retains the memory of initial conditions for
long times,indicating the possible absence of ergodicity [81]. It displays the
breakdown of ergodicity at long times, slow thermalization and nonergodicity
more generally with constraints and explores the phenomenon of slow quantum
dynamics reminiscent of (quasi-)many-body localization (MBL) in disorder-free
systems [82].

Involving spin-1/2 degrees of freedom arranged on a one-dimensional lattice,
this model introduce kinetic constraints as the driving force behind the
observed gradual evolution, controlled by Hamiltonian

$\hat{H}_{E}=\frac{1}{2}\sum_{j=0}^{N}n_{j}(e^{-s}\sigma_{j+1}^{x}-1)$ (6)

where $\sigma_{j}^{x}$ is the Pauli operator acting on the $j^{th}$ spin Pauli
operators and the operator $n_{i}=(1-\sigma_{i}^{z})/2$ corresponds to a
projection onto the state $\left|{1}\right\rangle$ in the local $z$ basis. $s$
is the site coupling strength, significantly impacting the dynamic behavior of
the model.

We select Out-of-Time-Ordered Correlator (OTOC) as the basis of dataset with
the different $s$. OTOC plays a pivotal role in exploring diagnosing the
chaotic behavior of many-body quantum systems and characterizing the process
of information scrambling [83, 84, 85], which is given by
$\mathcal{O}_{j}(t)=\langle\psi_{0}|\hat{Z}_{j}(t)\hat{Z}_{j}(0)\hat{Z}_{j}(t)\hat{Z}_{j}(0)|\psi_{0}\rangle_{.}$
Here, $\hat{Z}_{j}(t)=e^{iH_{E}t}\hat{Z_{j}}(0)e^{-iH_{E}t}$, and
$|\psi_{0}\rangle$ is the initial state. Each element of the input sequential
data is the OTOC collected at different time $t=(l-1)\delta t$ and different
z-site, represented as
$\mathbf{O}_{l}=[\mathcal{O}_{1}(t);\mathcal{O}_{1}(t);\dots\mathcal{O}_{j}(t)]$.

We selected alternative spin up and spin down as the initial
state$|\psi_{0}\rangle=|\uparrow\downarrow\uparrow\downarrow\cdots\rangle$.
Three sequences of QE models are displays in Fig. 4(a) represented by blue
square, blue diamond and red triangle respectively. In the context of
Euclidean distance, Fig. 4(b) higher illustrates only one eigenvalue near 1,
with a continuous second eigenstate in Fig. 4(c) , suggesting the dataset are
classify to one cluster. In contrast, Fig. 4(b) lower displays two eigenvalues
nearing 1, with a gap between their second eigenstate proof the dataset in
Fig. 4(c) is divided into two clusters. The three dynamic processes from Fig.
4(a) are labeled in Fig. 4(c) and Fig. 4(d). They are merged into one cluster
in the absence of considering complexity, while being well separated when
complexity is imported. Further, by computing the silhouette coefficient, we
get the phase transition occurring at $s=0$.

Discussions— We propose a complexity-powered distance based on the Euclidean
distance by introducing the complexity of time series. In this distance, the
complexity boosted factor emphasizes differences in high-frequency patterns
between time series, while the boosted power non-linearly amplifies these
differences, providing a natural advantage in classifying periodic time
series. Combined with machine intelligence, we demonstrate the effectiveness
of this distance across three quantum many-body dynamics models. The results
showed that the classifications were poor and inaccurate based on Euclidean
distance. However, by adjusting the boosted power in the complexity-powered
distance, the classifications were significantly improved and the results are
correct and distinct.

The application of the complexity boosted distances will provide new methods
to identify and classify time series in the future. Moreover, it holds great
potential for diverse time-dependent systems such as stock analysis, tsunami
prediction, weather forecasting, and beyond.

###### Acknowledgements.

Acknowledgement—We acknowledge the support from the National Natural Science
Foundation of China (No. 11935010), the Natural Science Foundation of Shanghai
(No. 23ZR1481200), the Program of Shanghai Academic Research Leader (No.
23XD1423800), and the Opening Project of Shanghai Key Laboratory of Special
Artificial Microstructure Materials and Technology.

## References

  * Y.H.Wang  _et al._ [2013] Y.H.Wang, H.Steinberg, P. Jarillo-Herrero, and N. Gedik, Observation of floquet-bloch states on the surface of a topological insulator, Science 342, 453 (2013).
  * Bukov  _et al._ [2015] M. Bukov, L. D’Alessio, and A. Polkovnikov, Universal high-frequency behavior of periodically driven systems: from dynamical stabilization to floquet engineering, Adv. Phys. 64, 139 (2015).
  * Else  _et al._ [2016] D. V. Else, B. Bauer, and C. Nayak, Floquet time crystals, Phys. Rev. Lett. 117, 090402 (2016).
  * Rudner and Lindner [2020] M. S. Rudner and N. H. Lindner, Band structure engineering and non-equilibrium dynamics in floquet topological insulators, Nat. Rev. Phys. 2, 229 (2020).
  * Lerose  _et al._ [2021] A. Lerose, M. Sonner, and D. A. Abanin, Influence matrix approach to many-body floquet dynamics, Phys. Rev. X 11, 021040 (2021).
  * Calabrese and Cardy [2006] P. Calabrese and J. Cardy, Time dependence of correlation functions following a quantum quench, Phys. Rev. Lett. 96, 136801 (2006).
  * Kollath  _et al._ [2007] C. Kollath, A. M. Läuchli, and E. Altman, Quench dynamics and nonequilibrium phase diagram of the bose-hubbard model, Phys. Rev. Lett. 98, 180601 (2007).
  * Schiró and Fabrizio [2010] M. Schiró and M. Fabrizio, Time-dependent mean field theory for quench dynamics in correlated electron systems, Phys. Rev. Lett. 105, 076401 (2010).
  * Mitra [2018] A. Mitra, Quantum quench dynamics, Annu. Rev. Condens. Matter Phys. 9, 245 (2018).
  * Guardado-Sanchez  _et al._ [2021] E. Guardado-Sanchez, B. M. Spar, P. Schauss, R. Belyansky, J. T. Young, P. Bienias, A. V. Gorshkov, T. Iadecola, and W. S. Bakr, Quench dynamics of a fermi gas with strong nonlocal interactions, Phys. Rev. X 11, 021036 (2021).
  * Yu and Eberly [2006] T. Yu and J. H. Eberly, Quantum open system theory: Bipartite aspects, Phys. Rev. Lett. 97, 140403 (2006).
  * Breuer  _et al._ [2009] H.-P. Breuer, E.-M. Laine, and J. Piilo, Measure for the degree of non-markovian behavior of quantum processes in open systems, Phys. Rev. Lett. 103, 210401 (2009).
  * Breuer  _et al._ [2016] H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini, Colloquium: Non-markovian dynamics in open quantum systems, Rev. Mod. Phys. 88, 021002 (2016).
  * De Vega and Alonso [2017] I. De Vega and D. Alonso, Dynamics of non-markovian open quantum systems, Rev. Mod. Phys. 89, 015001 (2017).
  * Wilczek [2012] F. Wilczek, Quantum time crystals, Phys. Rev. Lett. 109, 160401 (2012).
  * Zhang  _et al._ [2017] J. Zhang, P. W. Hess, A. Kyprianidis, P. Becker, A. Lee, J. Smith, G. Pagano, I.-D. Potirniche, A. C. Potter, A. Vishwanath, N. Y. Yao, and C. Monroe, Observation of a discrete time crystal, Nature 543, 217 (2017).
  * Yao  _et al._ [2017] N. Y. Yao, A. C. Potter, I.-D. Potirniche, and A. Vishwanath, Discrete time crystals: Rigidity, criticality, and realizations, Phys. Rev. Lett. 118, 030401 (2017).
  * Chen and Zhang [2023] Y.-H. Chen and X. Zhang, Realization of an inherent time crystal in a dissipative many-body system, Nat. Commun. 14, 6161 (2023).
  * Bauer and Nayak [2014] B. Bauer and C. Nayak, Analyzing many-body localization with a quantum computer, Phys. Rev. X 4, 041021 (2014).
  * Nandkishore and Huse [2015] R. Nandkishore and D. A. Huse, Many-body localization and thermalization in quantum statistical mechanics, Annu. Rev. Condens. Matter Phys. 6, 15 (2015).
  * Abanin  _et al._ [2019] D. A. Abanin, E. Altman, I. Bloch, and M. Serbyn, Colloquium: Many-body localization, thermalization, and entanglement, Rev. Mod. Phys. 91, 021001 (2019).
  * Altman [2018] E. Altman, Many-body localization and quantum thermalization, Nat. Phys. 14, 979 (2018).
  * Guo  _et al._ [2021] Q. Guo, C. Cheng, Z.-H. Sun, Z. Song, H. Li, Z. Wang, W. Ren, H. Dong, D. Zheng, Y.-R. Zhang, R. Mondaini, H. Fan, and H. Wang, Observation of energy-resolved many-body localization, Nat. Phys. 17, 234 (2021).
  * Berges  _et al._ [2004] J. Berges, S. Borsányi, and C. Wetterich, Prethermalization, Phys. Rev. Lett. 93, 142002 (2004).
  * Mallayya  _et al._ [2019] K. Mallayya, M. Rigol, and W. De Roeck, Prethermalization and thermalization in isolated quantum systems, Phys. Rev. Lett. 122, 180601 (2019).
  * Ueda [2020] M. Ueda, Quantum equilibration, thermalization and prethermalization in ultracold atoms, Nat. Rev. Phys. 2, 669 (2020).
  * Le  _et al._ [2023] Y. Le, Y. Zhang, S. Gopalakrishnan, M. Rigol, and D. S. Weiss, Observation of hydrodynamization and local prethermalization in 1d bose gases, Nature 618, 494 (2023).
  * Gong  _et al._ [2018] Z. Gong, Y. Ashida, K. Kawabata, K. Takasan, S. Higashikawa, and M. Ueda, Topological phases of non-hermitian systems, Phys. Rev. X 8, 031079 (2018).
  * Carrasquilla and Melko [2017] J. Carrasquilla and R. G. Melko, Machine learning phases of matter, Nat. Phys. 13, 431 (2017).
  * Bedolla  _et al._ [2020] E. Bedolla, L. C. Padierna, and R. Castaneda-Priego, Machine learning for condensed matter physics, J. Condens. Matter Phys. 33, 053001 (2020).
  * Havlíček  _et al._ [2019] V. Havlíček, A. D. Córcoles, K. Temme, A. W. Harrow, A. Kandala, J. M. Chow, and J. M. Gambetta, Supervised learning with quantum-enhanced feature spaces, Nature 567, 209 (2019).
  * Dunjko and Briegel [2018] V. Dunjko and H. J. Briegel, Machine learning & artificial intelligence in the quantum domain: a review of recent progress, Rep. Prog. Phys. 81, 074001 (2018).
  * Mozos and Burgard [2006] O. M. Mozos and W. Burgard, Supervised learning of topological maps using semantic information extracted from range data, in  _2006 IEEE/RSJ International Conference on Intelligent Robots and Systems_ (IEEE, 2006) pp. 2772–2777.
  * Holanda and Griffith [2020] N. Holanda and M. Griffith, Machine learning topological phases in real space, Phys. Rev. B 102, 054107 (2020).
  * Yang  _et al._ [2020] L. Yang, J. Ren, and H. Chen, Unsupervised manifold clustering of topological phononics, Phys. Rev. Lett. 124, 165502 (2020).
  * Long  _et al._ [2019] Y. Long, J. Ren, Y. Li, and H. Chen, Inverse design of photonic topological state via machine learning, Appl. Phys. Lett. 114, 181105 (2019).
  * Liu  _et al._ [2018] Z. Liu, D. Zhu, S. P. Rodrigues, K.-T. Lee, and W. Cai, Generative model for the inverse design of metasurfaces, Nano Lett. 18, 6570 (2018).
  * Torlai and Melko [2017] G. Torlai and R. G. Melko, Analyzing nonequilibrium quantum states through snapshots with artificial neural networks, Phys. Rev. Lett. 119, 030501 (2017).
  * van Nieuwenburg  _et al._ [2017] E. P. L. van Nieuwenburg, Y.-H. Liu, and S. D. Huber, Learning phase transitions by confusion, Nat. Phys. 13, 435 (2017).
  * Rodriguez-Nieva and Scheurer [2019a] J. F. Rodriguez-Nieva and M. S. Scheurer, Identifying topological order through unsupervised machine learning, Nat. Phys. 15, 790 (2019a).
  * Lu  _et al._ [2020] P. Y. Lu, S. Kim, and M. Soljačić, Extracting interpretable physical parameters from spatiotemporal systems using unsupervised learning, Phys. Rev. X 10, 031056 (2020).
  * Abdi and Williams [2010] H. Abdi and L. J. Williams, Principal component analysis, Wiley Interdiscip. Rev. Comput. Stat. 2, 433 (2010).
  * Wang [2016] L. Wang, Discovering phase transitions with unsupervised learning, Phys. Rev. B 94, 195105 (2016).
  * Jolliffe and Cadima [2016] I. T. Jolliffe and J. Cadima, Principal component analysis: a review and recent developments, Philos. Transact. A Math. Phys. Eng. Sci. 374 (2016).
  * Hu  _et al._ [2017] W. Hu, R. R. P. Singh, and R. T. Scalettar, Discovering phases, phase transitions, and crossovers through unsupervised machine learning: A critical examination, Phys. Rev. E 95, 062122 (2017).
  * Wang and Zhai [2017] C. Wang and H. Zhai, Machine learning of frustrated classical spin models. i. principal component analysis, Phys. Rev. B 96, 144432 (2017).
  * Wang and Zhai [2018] C. Wang and H. Zhai, Machine learning of frustrated classical spin models (ii): Kernel principal component analysis, Front. Phys. 13, 130507 (2018).
  * Rodriguez-Nieva and Scheurer [2019b] J. F. Rodriguez-Nieva and M. S. Scheurer, Identifying topological order through unsupervised machine learning, Nat. Phys. 15, 790 (2019b).
  * Lidiak and Gong [2020a] A. Lidiak and Z. Gong, Unsupervised machine learning of quantum phase transitions using diffusion maps, Phys. Rev. Lett. 125, 225701 (2020a).
  * Scheurer and Slager [2020] M. S. Scheurer and R.-J. Slager, Unsupervised machine learning and band topology, Phys. Rev. Lett. 124, 226401 (2020).
  * Che  _et al._ [2020] Y. Che, C. Gneiting, T. Liu, and F. Nori, Topological quantum phase transitions retrieved through unsupervised machine learning, Phys. Rev. B 102, 134213 (2020).
  * Yu and Deng [2021] L.-W. Yu and D.-L. Deng, Unsupervised learning of non-hermitian topological phases, Phys. Rev. Lett. 126, 240402 (2021).
  * Prigogine [1987] I. Prigogine, Exploring complexity, Eur. J. Oper. Res. 30, 97 (1987).
  * Oliveto  _et al._ [2007] P. S. Oliveto, J. He, and X. Yao, Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results, Int. J. Autom. Comput. 4, 281 (2007).
  * Goldreich [2008] O. Goldreich, Computational complexity: a conceptual perspective, ACM Sigact News 39, 35 (2008).
  * Batista  _et al._ [2011] G. E. Batista, X. Wang, and E. J. Keogh, A complexity-invariant distance measure for time series, in  _Proceedings of the 2011 SIAM international conference on data mining_ (SIAM, 2011) pp. 699–710.
  * [57] For simplicity, we now use subscripts $ij$ to represent data sets $\mathbf{D}_{i},\mathbf{D}_{j}$, for example, $M_{ij}$ means $M(\mathbf{D}_{i},\mathbf{D}_{j})$ and $C_{i}$ means $C(\mathbf{D}_{i})$.
  * [58] Please see the Supplemental Material for details about the hyperparameter settings of the three models, the performance of complexity boost, the definition of the silhouette coefficient, further verification of the DTC model (the classification of the quantum Ising model), detailed classification results for interacting AA models.
  * Coifman  _et al._ [2005a] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Diffusion maps, PNAS 102, 7426 (2005a).
  * Coifman  _et al._ [2005b] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, Geometric diffusions as a tool for harmonic analysis and structure definition of data: Multiscale methods, PNAS 102, 7432 (2005b).
  * Coifman and Lafon [2006] R. R. Coifman and S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal. 21, 5 (2006).
  * De la Porte  _et al._ [2008] J. De la Porte, B. Herbst, W. Hereman, and S. Van Der Walt, An introduction to diffusion maps, in  _Proceedings of the 19th symposium of the pattern recognition association of South Africa (PRASA 2008), Cape Town, South Africa_ (2008) pp. 15–25.
  * Lidiak and Gong [2020b] A. Lidiak and Z. Gong, Unsupervised machine learning of quantum phase transitions using diffusion maps, Phys. Rev. Lett. 125, 225701 (2020b).
  * Peskin [1995] M. E. Peskin,  _An Introduction to Quantum Field Theory_, 1st ed. (CRC Press, Boca Raton, 1995) p. 866.
  * Bruno [2013] P. Bruno, Impossibility of spontaneously rotating time crystals: A no-go theorem, Phys. Rev. Lett. 111, 070402 (2013).
  * Watanabe and Oshikawa [2015] H. Watanabe and M. Oshikawa, Absence of quantum time crystals, Phys. Rev. Lett. 114, 251603 (2015).
  * Ponte  _et al._ [2015] P. Ponte, Z. Papić, F. m. c. Huveneers, and D. A. Abanin, Many-body localization in periodically driven systems, Phys. Rev. Lett. 114, 140401 (2015).
  * Lazarides  _et al._ [2015] A. Lazarides, A. Das, and R. Moessner, Fate of many-body localization under periodic driving, Phys. Rev. Lett. 115, 030402 (2015).
  * Khemani  _et al._ [2016] V. Khemani, A. Lazarides, R. Moessner, and S. Sondhi, Phase structure of driven quantum systems, Phys. Rev. Lett. 116, 250401 (2016).
  * Li  _et al._ [2012] T. Li, Z.-X. Gong, Z.-Q. Yin, H. T. Quan, X. Yin, P. Zhang, L.-M. Duan, and X. Zhang, Space-time crystals of trapped ions, Phys. Rev. Lett. 109, 163001 (2012).
  * Wilczek [2013] F. Wilczek, Superfluidity and space-time translation symmetry breaking, Phys. Rev. Lett. 111, 250402 (2013).
  * Zhang  _et al._ [2023] W. Zhang, Y. Wu, X. Qiu, J. Nan, and X. Li, Subexponential critical slowing-down at a floquet time-crystal phase transition, Phys. Rev. B 108, 014307 (2023).
  * Moessner and Sondhi [2017] R. Moessner and S. L. Sondhi, Equilibration and order in quantum floquet matter, Nat. Phys. 13, 424 (2017).
  * Cucchietti  _et al._ [2003] F. M. Cucchietti, D. A. Dalvit, J. P. Paz, and W. H. Zurek, Decoherence and the loschmidt echo, Phys. Rev. lett. 91, 210403 (2003).
  * Quan  _et al._ [2006] H. T. Quan, Z. Song, X. F. Liu, P. Zanardi, and C. P. Sun, Decay of loschmidt echo enhanced by quantum criticality, Phys. Rev. Lett. 96, 140604 (2006).
  * Gorin  _et al._ [2006] T. Gorin, T. Prosen, T. H. Seligman, and M. Žnidarič, Dynamics of loschmidt echoes and fidelity decay, Phys. Rep. 435, 33 (2006).
  * Yan  _et al._ [2020] B. Yan, L. Cincio, and W. H. Zurek, Information scrambling and loschmidt echo, Phys. Rev. lett. 124, 160603 (2020).
  * Aubry and André’ [1980] S. Aubry and G. André’, Localization in one-dimensional lattice structures, Ann. Isr. Phys. Soc. 3, 133 (1980).
  * Iyer  _et al._ [2013] S. Iyer, V. Oganesyan, G. Refael, and D. A. Huse, Many-body localization in a quasiperiodic system, Phys. Rev. B 87, 134202 (2013).
  * Xu  _et al._ [2019] S. Xu, X. Li, Y.-T. Hsu, B. Swingle, and S. Das Sarma, Butterfly effect in interacting aubry-andre model: Thermalization, slow scrambling, and many-body localization, Phys. Rev. Res. 1, 032039 (2019).
  * van Horssen  _et al._ [2015] M. van Horssen, E. Levi, and J. P. Garrahan, Dynamics of many-body localization in a translation-invariant quantum glass model, Phys. Rev. B 92, 100305(R) (2015).
  * Pancotti  _et al._ [2020] N. Pancotti, G. Giudice, J. I. Cirac, J. P. Garrahan, and M. C. Bañuls, Quantum east model: Localization, nonthermal eigenstates, and slow dynamics, Phys. Rev. X 10, 021051 (2020).
  * Li  _et al._ [2017] J. Li, R. Fan, H. Wang, B. Ye, B. Zeng, H. Zhai, X. Peng, and J. Du, Measuring out-of-time-order correlators on a nuclear magnetic resonance quantum simulator, Phys. Rev. X 7, 031011 (2017).
  * Fan  _et al._ [2017] R. Fan, P. Zhang, H. Shen, and H. Zhai, Out-of-time-order correlation for many-body localization, Sci. Bull. 62, 707 (2017).
  * Swingle [2018] B. Swingle, Unscrambling the physics of out-of-time-order correlators, Nat. Phys. 14, 988 (2018).


# Complexity Reduction in the Negotiation of New Lexical Conventions

William Schueller<EMAIL_ADDRESS>University of Bordeaux,
Bordeaux, France  INRIA Bordeaux Sud-Ouest/ Ensta ParisTech : Flowers Project-
team, Bordeaux, France  Vittorio Loreto SONY Computer Science Lab, Paris,
France  Physics Dpt., Sapienza University of Rome, Rome, Italy  Complexity
Science Hub Vienna (CSHV), Vienna, Austria  Pierre-Yves Oudeyer INRIA Bordeaux
Sud-Ouest/ Ensta ParisTech : Flowers Project-team, Bordeaux, France

###### Abstract

In the process of collectively inventing new words for new concepts in a
population, conflicts can quickly become numerous, in the form of synonymy and
homonymy. Remembering all of them could cost too much memory, and remembering
too few may slow down the overall process. Is there an efficient behavior that
could help balance the two? The Naming Game is a multi-agent computational
model for the emergence of language, focusing on the negotiation of new
lexical conventions, where a common lexicon self-organizes but going through a
phase of high complexity. Previous work has been done on the control of
complexity growth in this particular model, by allowing agents to actively
choose what they talk about. However, those strategies were relying on ad hoc
heuristics highly dependent on fine-tuning of parameters. We define here a new
principled measure and a new strategy, based on the beliefs of each agent on
the global state of the population. The measure does not rely on heavy
computation, and is cognitively plausible. The new strategy yields an
efficient control of complexity growth, along with a faster agreement process.
Also, we show that short-term memory is enough to build relevant beliefs about
the global lexicon.

Keywords: language emergence, active learning, multi-agent model, control of
complexity growth

## Motivations

Lexical conventions constitute an important element of social interactions.
They can emerge, evolve, or be learnt within a population, without necessarily
having a centralized control. In other words, they can be negotiated through
local interactions between individuals. In practice, this happens continuously
in human societies, being the spread of new words and conventions, the
acquisition of those conventions by infants or other learners, or even the
emergence of new forms of communication. Despite the high complexity of the
processes involved, humans deal with these issues quite efficiently.

Learning of high complexity tasks in individuals can in general be facilitated
by an active control of the complexity of learning situations , often driven
by intrinsic motivation, like for example maximization of the learning
progress (?, ?, ?, ?, ?). This type of mechanism is also argued to be an
evolutionary advantage for cognitive abilities (?, ?), and can also be found
in lexicon acquisition at the individual level (?, ?). But does it have a
significant impact on population-wide learning and conventions negotiation
dynamics?

The Naming Game (?, ?, ?, ?, ?) is an adapted framework to test this
hypothesis. It is a class of multi-agent models of language emergence and
evolution, where pairs of randomly selected individuals try to communicate by
referring to some pre-defined meanings using words. At the beginning, they do
not share any convention about word-meaning associations. Through repeated
decentralized interactions, a common lexicon self-organizes. However, the
process can be slow and pass through a high-complexity phase where agents
memorize a lot of conflictual information, in the form of synonyms and
homonyms.

It has already been shown that active learning mechanisms can increase
convergence speed towards a shared lexicon in different language emergence
models (?, ?, ?). The main idea behind those mechanisms is to allow agents to
actively choose the topic of their communication, based on information
collected during their past interactions and driven by control of complexity
growth. However, the algorithms used so far are based on ad hoc heuristics,
constrained interaction scenarios and can depend heavily on fine-tuning of
parameters themselves depending on population size and number of words and
meanings.

In previous work, an approximation of the global state is built by each agent
using the information of past interactions, in the form of an average
vocabulary of the population (?, ?, ?). Is it possible to design a new
principled algorithm for an active topic choice based on such a
representation? Could decisions be driven by both the compatibility of an
agent’s own lexicon with this average vocabulary, and a reduction of both
their complexities? Such an algorithm should rely on a time scale for the
memory of past interactions: Indeed, in the case of uncentralized negotiation
of a lexicon, conflictual conventions will necessarily appear and have to be
forgotten in order to converge to a functional global vocabulary. Remembering
them could slow down the self-organization process.

In this work, we define a principled measure of correlation between an agent’s
lexicon and a local approximation of the average lexicon of the population. We
build a strategy driven by the maximization of this value without being
computationally hard, to be cognitively plausible. We study and discuss the
impact of this strategy on convergence time and complexity growth, depending
on a time scale used for memory.

## Methods

### The Naming Game

We define here precisely the Naming Game model that we used (see fig.1 for an
overview). We need to explicit:

  * -

The interaction scenario itself

  * -

How agents represent their lexicon

  * -

How they update their lexicon at the end of each interaction

It is a simple modification of the standard Naming Game scenario (?, ?, ?).

Figure 1: Illustration of the Naming Game model. Out of a population of
simulated agents, two are picked and try to communicate, using/inventing words
to refer to meanings. After repeated such interactions, a common lexicon self-
organizes. In this example, there are $M$=$2$ possible meanings, $W$=$4$
possible words and $N$=$12$ agents.

#### Interaction process

We re-use a previously defined interaction process called Speaker’s Choice (?,
?). It allows one of the interacting agents, called the speaker, choose
actively the topic of the interaction.

Each interaction involves two agents, that are picked randomly from the
population. One of them is assigned the role speaker, and the other the role
hearer. The speaker chooses a topic and picks up a word for this topic. If it
does not have a word associated so far to the meaning used as topic, it just
invents a new meaning-word association. It utters this word, which is
interpreted by the hearer as a meaning, if it knows this word. If the
interpreted meaning is the same as the topic, i.e. the meaning intended by the
speaker, the communication is considered successful. Otherwise, it is
considered a failure. See fig.2 for a detailed illustration of the interaction
process.

Figure 2: Interaction process: Beforehand, 2 individuals have been randomly
selected among a population, an designated as speaker (S) and hearer (H). 1. S
chooses a topic, 2. S checks its vocabulary to find or invent an associated
word, 3. S utters the word, 4. H guesses the intended meaning, 5. S indicates
the intended meaning.

#### Vocabulary Representation

Vocabularies, or lexicons, are a set of associations between meanings and
words. In this work, we consider only a finite set of meanings $M$ and a
finite set of words $W$. In this context, vocabularies can be represented as
associations matrices, where each row corresponds to a meaning, and each
column to a word. This representation has been extensively used in related
work (?, ?, ?, ?). Two parts of the lexicon are distinguished, the coding or
production part, which maps a meaning to a set of words weighted by
probabilities of usage, and a decoding or interpretation part, mapping a word
to a set of meanings that can be interpretated from this word, also weighted
by probabilities.

We represent the vocabulary of an agent $A$ as a matrix $V(A)$ of size
$M\times W$, with values of $1$ for each word-meaning association used by the
agent. Each agent starts with an empty vocabulary, a matrix filled with zeros.
The coding matrix $V^{c}(A)$ and decoding matrix $V^{d}(A)$ are derived from
$V(A)$ by normalizing respectively over rows and columns:

$V^{c}(A)_{mw}=\frac{V(A)_{mw}}{\sum\limits_{w^{\prime}}V(A)_{mw^{\prime}}}\hskip
22.76228ptV^{d}(A)_{mw}=\frac{V(A)_{mw}}{\sum\limits_{m^{\prime}}V(A)_{m^{\prime}w}}$
(1)

Normalization factors are used only if $V(A)_{mw}\neq 0$. In practice, when
coding a meaning $m$, a word $w_{i}$ is sampled using the distribution
$\left(V^{c}(A)_{mw}\right)_{w\in W}$. When decoding a word $w$, a meaning
$m_{j}$ is interpreted, sampled from the distribution
$\left(V^{d}(A)_{mw}\right)_{m\in M}$. In our case, these distributions are
uniform either on the set of words associated to $m$ for coding, or on the set
of meanings associated to $w$ for decoding. Those 2 sets change over time,
during the vocabulary update.

#### Vocabulary Update Policy

At the end of each interaction, each agent takes into account the result of
the interaction by modifying its lexicon. There exists various policies that
have been described and studied in previous work (?, ?). We are using the one
called Minimal Naming Game.

In this policy, updates work this way: when the communication fails, both
agents add the used word-meaning association (meaning used as a topic by the
speaker, and word uttered by the speaker) to their lexicon, and do nothing if
they already had it. If the communication is successful, not only do they add
this association to their respective lexicons, they also remove any
conflicting synonyms and homonyms. See fig.3 for an illustration of the update
policy in both cases.

Typically, among existing policies, Minimal NG and another one called Basic
Lateral Inhibition are used: they are more realistic as they allow
synonymy/homonymy and yield faster agreement. Moreover, Minimal NG has been
shown to yield similar dynamics as Basic Lateral Inhibition, yet being simple
and not depending on any parameter, while the latter depends on 3. This is the
reason why we are using the Minimal NG as vocabulary update policy.

Figure 3: Vocabulary update (Minimal NG). Failure (when the hearer interpreted
the word as another meaning than the topic): the word-meaning association used
by the speaker is added to the hearer’s vocabulary. The speaker adds it as
well if it was just invented. Success (when the hearer interpreted correctly
the word as the topic): both hearer and speaker remove synonyms/homonyms in
conflict with the word-meaning association used during the interaction. In
both examples the topic is the apple, and the word rimi.

### Measures

The self-organization process happening while simulating the Naming Game has
complex dynamics, and goes through various states before reaching global
consensus. We talk about those dynamics as a convergence process, towards the
state where all agents share the exact same lexicon, with exactly one word for
each meaning without synonymy and homonymy. This state is stable, lexicons
will not change anymore whatever are the modalities of the interaction – which
agent is the speaker, which is the hearer, and which meanings and words are
used. Convergence and stability for different types of Naming Games has been
proved analytically (?, ?). In this paper, we do not focus on whether the
model converges or not, but on the speed and complexity properties of the
dynamics before convergence. Measures for each of those aspects, used to
describe the system while in this intermediate state, were defined in previous
work (?, ?). We distinguish local measures –accessible to each agent– from
global measures, computed on the whole population.

#### TCS: Theoretical Communicative Success

The Theoretical Communicative Success is a measure of distance to the fully
converged state. First, for each meaning, we can consider the probability of
having a successful communication when using this meaning as a topic, given a
state of the population. The TCS is the average of those probabilities, over
all possible meanings. In the case of Random Topic Choice, this measure
coincides with the general probability of having a successful interaction. By
definition, it is a global measure, not accessible to individual agents. To
retrieve its value, we can either estimate it using a snapshot of the
population and a Monte Carlo method with random topic choice, or compute it.
To detail the exact computation formula, we need to first define the
probability of success between two given vocabularies of agents $A$ and $B$.
As detailed in the previous section, a vocabulary has 2 components: a coding
part, used to find words associated to a meaning, and a decoding part, used to
find meanings associated to a word. For vocabulary $V(A)$, we would then have
the 2 matrices $V^{c}(A)$ and $V^{d}(A)$. If A is the speaker and B the
hearer, A is coding and B decoding, hence the formula of the probability of
success in this case, averaged over all possible meanings:

$TCS_{s}(A,B)=\frac{1}{M}\sum\limits_{m}\sum\limits_{w}V^{c}(A)_{m,w}\cdot
V^{d}(B)_{m,w}$ (2)

Because before an interaction we do not necessarily know which agent will be
the speaker and which will be the hearer, the 2 situations (A speaker and B
hearer / B speaker and A hearer) are to be considered, as equiprobable. The
final value $TCS(A,B)$ is the mean of $TCS_{s}(A,B)$ and $TCS_{s}(B,A)$.

To scale up to population level, one can compute an average vocabulary for the
whole population $V(P)$, and then the probability of success for an
interaction between this lexicon and itself. For a large enough population,
this value is indeed a good approximation of the probability of success.
$V(P)$ is an element-wise average of the lexicon matrices of all agents.

When using random topic choice, this value abruptly goes from 0 to 1 after a
certain number of interactions. These dynamics can be seen on fig.4, where the
random topic choice is represented – among active strategies that are
explained in a following section. In practice, we use Monte Carlo estimation
for the values at population level over time, and the exact computation for
the active topic choice strategy (see following section), as it requires more
precision and the population vocabulary is already built.

#### Local Complexity

The starting state of an agent’s vocabulary is empty (all-zero matrices), and
the end state is identical coding and decoding matrices, with exactly one
distinct word per meaning. But between those 2 situations, through which
states goes the vocabulary? How much conflictual information (synonymy and
homonymy) has to be considered?

For each agent, we can define a local complexity measure, by counting the
number of distinct associations present in the vocabulary. In our case, this
is exactly the sum of all elements of the matrix $V(A)$. At the beginning of a
simulation, while the vocabulary is empty, this measure equals 0. At the end,
its value is the number of meanings $M$. When using random topic choice, there
is a fast growth to a maximum, before a slow decrease to the final value $M$
(can be seen in fig.4). This measure is nearly proportional to the minimal
memory needed to represent the lexicon (as a sparse matrix or a list of word-
meaning associations), and therefore should remain low in a cognitively
plausible situation.

### Active Topic Choice Strategy

The main contribution of this work is the definition of an active strategy for
the choice of the topic in each interaction, by comparison to the usual choice
of picking meanings randomly (with a uniform distribution over the space of
meanings). The strategy has to be local, i.e. use only information available
to the agent, namely its own vocabulary and results of past interactions it
was involved in.

To both converge quickly and control complexity, behavior should be driven by
maximization at each interaction of the Theoretical Communicative Success.
However, this value is a global measure, therefore not accessible at agent
level. Agents only sample information about the global state of the
population, or the average vocabulary $V(P)$, through their interactions as
hearer or speaker.

The strategies for active topic choice found in previous work are separated in
two levels of decision (?, ?). First, a decision between exploring a new
meaning (that is associated to no words in the vocabulary so far) and choosing
(exploiting) a meaning among those already used before. Then, if exploiting,
deciding which known meaning to use depending on past interaction results.

The strategy introduced in this work keeps those two levels, while basing both
decisions on a new measure called Local Approximated Probability of Success
(LAPS), using a local representation of $V(P)$.

#### LAPS: Local Approximated Probability of Success

Here, we define an approximation of $V(P)$, $\widetilde{V}(P)$, using
information sampled by agents during their interactions. We construct
independently the coding and decoding parts $\widetilde{V}^{c}(P)$ and
$\widetilde{V}^{d}(P)$. For every meaning $m$ (and every word $w$), we use a
sliding window over the recent past interactions – of maximal length $\tau$,
the time scale parameter– and count the number of times it is associated to
each word $w^{\prime}$ (or meaning $m^{\prime}$). This value divided by $\tau$
is the local estimation of the probability of an other agent coding $m$ using
$w^{\prime}$ (or decoding $w$ as $m^{\prime}$). With this, we retrieve the
values of both matrices $\widetilde{V}^{c}(P)$ and $\widetilde{V}^{d}(P)$.

Let $M^{c}(m)$ be the memory of the past interactions where $m$ was the topic,
if there has been $T_{m}$ such interactions. $w_{t}$ denotes the word used
during the $t^{th}$ interaction of the agent using the meaning $m$. We can now
build $\widetilde{V}^{c}(P)$:

$M^{c}(m)=\left(w_{t}\right)_{1\leq t\leq T_{m}}\hskip
17.07182pt\widetilde{V}^{c}(P)_{mw}=\frac{\sum\limits_{t=T_{m}-\tau+1}^{T_{m}}\delta_{w,w_{t}}}{\tau}$
(3)

Similarly, by defining $M^{d}(w)$ be the memory of the past interactions where
$w$ was the topic, with $T_{w}$ such interactions, we can build
$\widetilde{V}^{d}(P)$:

$M^{d}(w)=\left(m_{t}\right)_{1\leq t\leq T_{w}}\hskip
17.07182pt\widetilde{V}^{d}(P)_{mw}=\frac{\sum\limits_{t=T_{w}-\tau+1}^{T_{w}}\delta_{m,m_{t}}}{\tau}$
(4)

Until $\tau$ interactions have been done with a given meaning or word,
$\sum\limits_{w}\widetilde{V}^{c}(P)_{mw}$ and
$\sum\limits_{m}\widetilde{V}^{d}(P)_{mw}$ do not sum to $1$. The remaining
probability weight is assumed to be associated with failure. If we would
normalize to $1$, with a single interaction an agent would already estimate as
100% sure that the same word-meaning association would be used again with the
same topic for example. Without the normalization, this happens only after
$\tau$ interactions. In other words, this reflects lack of information due to
small sample size. We define a Local Approximated Probability of Success, or a
local equivalent of the Theoretical Communicative Success for an agent $A$
with vocabulary $V(A)$:

$LAPS_{A}=TCS(V(A),\widetilde{V}(P)_{A})$ (5)

For some vocabulary update policies called lateral inhibition, similar
matrices are computed, but used directly as an agent’s own representation of
the lexicon. This usage does not prevent the complexity burst (?, ?).

#### Exploration vs. Exploitation

The first choice of our new strategy is between exploring new meanings or
exploiting already known ones. Exploration should happen when agents are
confident enough about their agreement with the rest of the population over
their known meanings (?, ?). The LAPS measure in itself is a measure of
confidence, and the simplest way to take this into account is to only explore
when reaching the maximum value $\frac{K}{M}$ where $K$ is the number of known
meanings and $M$ the total number of meanings in the world. This value can
actually be reached, thanks to the sliding window of parameter $\tau$.

#### Multi-Armed Bandit

The second decision process concerns the exploitation part, when picking the
topic among the known meanings. We designed a behavior driven by the increase
of the LAPS measure. In other words, agents seek the meaning that would yield
the greatest increase of LAPS. However, computing the expectancy of this value
$\Delta LAPS$ is hard computationally speaking, and therefore not suitable for
a model of a cognitive process. We can only consider the process a black box,
where following a decision between a finite set of options, a reward value is
obtained. This is exactly the definition of the Multi-Armed Bandit problem,
associated to a class of reinforcement learning algorithms that have been
extensively studied (?, ?). The name comes from an analogy with a person
trying to maximize their gain while facing a set of slot-machines (also called
one armed bandit), and being able to use only one at a time. The probability
distribution of the reward of each machine is unknown, and the player has to
both collect information by playing and exploit the highest rewarding machine
– with limited knowledge of its reward distribution – hence keep balance
between exploration and exploitation. In our problem, we can see known
meanings as the possible arms, and the reward $\Delta LAPS$. Our case is quite
specific, as: 1) distributions are non stationary, 2) they depend on past
choices, 3) and the number of arms grows over time (and starts at 0). This
specific situation led us to choose an algorithm, where weights associated to
each arm undergo a decay over time, which let them stay at the same order of
magnitude of the initial weights of new arms (?, ?). Our algorithm depends on
2 parameters: integrated balance between reward-driven exploitation and random
exploration between arms through the parameter $\gamma$, and time scale $n$
for the decay of weights. As a reward, we consider the increase of LAPS
yielded by the interaction, $\Delta LAPS$, or $0$ if the latter is negative in
order to avoid negative weights. See algorithm 1.

Algorithm 1 LAPSmax Bandit Multi-Armed Bandit algorithm used as a topic choice
strategy maximizing the LAPS measure. New arms are created with weights
$w_{a}$ equal to the reward $r_{i}$ obtained at the end of an interaction with
a new meaning.

0: $\gamma$ rate of exploration for bandit

0: $n$ time scale for weights decay

0: vocabularies $V$ and $\widetilde{V}$, #meanings $M$

$K\leftarrow\left|V.known\\_meanings()\right|$

if $LAPS_{A}=\frac{K}{M}$ then

$m\leftarrow random\left(V.unknown\\_meanings()\right)$

else

for $a\in Arms$ do

$\tilde{w}_{a}=\frac{w_{a}}{\sum_{j}w_{j}}$

$p_{a}=(1-\gamma)\cdot\tilde{w}_{a}+\frac{\gamma}{K}$

end for

Sample $m\in Arms$ using distribution $(p_{a})_{a\in Arms}$

end if

return $m$

{Interact using topic $m$ and compute reward $r$}

if $m\in Arms$ then

$w_{m}\leftarrow\frac{n}{n+1}\cdot w_{m}+r$

else

Add $m$ to $Arms$ with $w_{m}=r$

end if

Figure 4: Theoretical success rate over time and Local Complexity for Random
Topic Choice and Active Topic Choice with several values of the time scale
$\tau$ used in the LAPS measure. $N$=$M$=$W$=$40$, $\gamma$=$0.01$, mean over
8 trials.

## Results

For all simulations, we set $N$=$M$=$W$=$40$, compute up to 80,000
interactions and take the mean over 8 trials. The situation $M$=$W$ is the
most constrained and complex to solve, as synonymy and homonymy are more
probable. We ran simulations for $1\leq\tau\leq 50$, and set $n$=$\tau$. For
the exploration rate, if the condition $0<\gamma\ll 1$ is respected, the
actual value of $\gamma$ does not matter much, as its only function is to
avoid rare cases where some weights reach a value of 0 and cannot be selected
anymore. We set $\gamma$=$0.01$. However, we also ran simulations with pure
random choices at the bandit level, to be able to study the influence of each
level of our algorithm. This case identifies as $\gamma$=$1$.

The evolution of the TCS and complexity over time is represented on fig.4, for
several values of the time scale $\tau$. They are compared on the same plots
with Random Topic Choice. We can see that convergence is faster for low values
of $\tau$, the fastest being for $\tau$=$2$, which is 4 times faster than
Random Topic Choice. As for complexity, for all configurations excepted
$\tau$=$1$ values stay below the final level 40. After reaching a first
threshold, they increase linearly with time, the slope being smaller for
higher values of $\tau$. For $\tau$=$1$, the maximum value is only half of the
maximum reached by Random Topic Choice. It is understandable that $\tau$=$1$
is an outlier: in this case LAPS is an autocorrelation with the current
interaction, by definition older interactions are not taken into account.

On fig.5, we can see the dependency of convergence time on the parameter
$\tau$, plotted for configurations $\gamma$=$0.01$, $\gamma$=$1$ and the value
for Random Topic Choice as a reference. Both have dynamics consistently faster
than Random Topic Choice for low values of $\tau$, however $\gamma$=$0.01$
performs better. Excepted for $\tau$=$1$, convergence time increases linearly
with $\tau$ for both, with a minimum at $\tau$=$2$, and a smaller slope for
$\gamma$=$0.01$.

Figure 5: Convergence time depending on time scale $\tau$ used in LAPS
measure, for both $\gamma$=$0.01$ and $\gamma$=$1$, compared with Random Topic
Choice. $N$=$M$=$W$=$40$, mean over 8 trials.

## Discussion

Results show that the new strategy presented in this paper 1) allows fast
convergence, 2) controls efficiently complexity growth, 3) its dynamics are
consistent and highly correlated with parameter change, 4) the 2 levels of the
algorithm each contribute to the increased performance.

With $\tau$=2, each agent on average only speaks 15 times about each meaning
before convergence (i.e. less than half the population), and information has
already been both conveyed between all agents and disambiguated. The linearity
of the evolution of TCS and complexity lets think that this algorithm may as
well scale efficiently to other values of $N$, $M$ and $W$. Compared to
previous work, this topic choice algorithm is more robust, and optimal
parameters are easier to find. It generalized well to Minimal Naming Game and
can be used for all other Naming Game models.

LAPS is coherent from a cognitive point of view, and corresponds to an actual
internal confidence about quality of communication with the rest of the
population. As stated in the results section, the case $\tau$=$1$ is an
outlier, being a simple autocorrelation with the current interaction. The
optimal value $\tau$=$2$ is then the lowest possible value taking into account
past interactions, i.e. $\widetilde{V}(P)$ takes the lowest possible memory,
which is therefore credible for humans. Further work will be needed to
determine for which values of N, M and W $\tau$=2 stays the optimal value.

## Acknowledgments

The IdEx program (Univ. de Bordeaux) allowed W. Schueller to visit V. Loreto.
We thank Miguel Ibañez Berganza and Benjamin Clément for the fruitful
discussions.

#### Source code

The Python code used for the simulations of this paper is available as open
source software: https://github.com/wschuell/notebooks_cogsci2018

## References

  * Baldassarre MirolliBaldassarre Mirolli Baldassarre, G., Mirolli, M.  (2013).  Intrinsically motivated learning systems: an overview.  In _Intrinsically motivated learning in natural and artificial systems_ (pp. 1–14).  Springer.
  * BartoBarto Barto, A. G.  (2013).  Intrinsic motivation and reinforcement learning.  In _Intrinsically motivated learning in natural and artificial systems_ (pp. 17–47).  Springer.
  * Bubeck, Cesa-Bianchi, et al.Bubeck et al. Bubeck, S., Cesa-Bianchi, N., et al.  (2012).  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations and Trends® in Machine Learning_ , _5_(1), 1–122.
  * Clement, Roy, Oudeyer, LopesClement et al. Clement, B., Roy, D., Oudeyer, P.-Y., Lopes, M.  (2015).  Multi-Armed Bandits for Intelligent Tutoring Systems.  _Journal of Educational Data Mining (JEDM)_ , _7_(2), 20–48.
  * Cornudella, Van Eecke, Van TrijpCornudella et al. Cornudella, M., Van Eecke, P., Van Trijp, R.  (2015).  How intrinsic motivation can speed up language emergence.  In _Proceedings of the european conference on artificial life_ (pp. 571–578).
  * De VylderDe Vylder De Vylder, B.  (2007).  _The evolution of conventions in multi-agent systems_.  Unpublished doctoral dissertation, Vrije Universiteit Brussel, Brussels.
  * Gottlieb, Oudeyer, Lopes, BaranesGottlieb et al. Gottlieb, J., Oudeyer, P.-Y., Lopes, M., Baranes, A.  (2013).  Information-seeking, curiosity, and attention: computational and neural mechanisms.  _Trends in cognitive sciences_ , _17_(11), 585–593.
  * Ke, Minett, Au, WangKe et al. Ke, J., Minett, J. W., Au, C.-P., Wang, W. S.-Y.  (2002).  Self-organization and selection in the emergence of vocabulary.  _Complexity_ , _7_(3), 41–54.
  * Loreto, Baronchelli, Mukherjee, Puglisi, TriaLoreto et al. Loreto, V., Baronchelli, A., Mukherjee, A., Puglisi, A., Tria, F.  (2011).  _Statistical physics of language dynamics_ (Vol. 2011) (No. 04).
  * Oliphant BataliOliphant Batali Oliphant, M., Batali, J.  (1997).  Learning and the emergence of coordinated communication.  _Center for research on language newsletter_ , _11_(1), 1–46.
  * Oudeyer, Kaplan, HafnerOudeyer et al. Oudeyer, P.-Y., Kaplan, F., Hafner, V. V.  (2007).  Intrinsic motivation systems for autonomous mental development.  _Evolutionary Computation, IEEE Transactions on_ , _11_(2), 265–286.
  * Oudeyer SmithOudeyer Smith Oudeyer, P.-Y., Smith, L.  (2014).  How evolution may work through curiosity-driven developmental process.  _Topics Cogn. Sci_.
  * Partridge, McGovern, Yung, KiddPartridge et al. Partridge, E., McGovern, M., Yung, A., Kidd, C.  (2015).  Young Children’s Self-Directed Information Gathering on Touchscreens.  In _Proceedings of the 37th annual meeting of the cognitive science society._
  * Schueller OudeyerSchueller Oudeyer Schueller, W., Oudeyer, P.-Y.  (2016).  Active control of complexity growth in naming games: Hearer’s choice.  In _The evolution of language: Proceedings of the 11th international conference (evolangx11)._
  * Steels KaplanSteels Kaplan Steels, L., Kaplan, F.  (1998).  Stochasticity as a source of innovation in language games.  In _Proceedings of artificial life vi_ (pp. 368–376).
  * WellensWellens Wellens, P.  (2012).  _Adaptive Strategies in the Emergence of Lexical Systems_.  Unpublished doctoral dissertation, Vrije Universiteit Brussel, Brussels.