ifaamas [AAMAS ’22]Proc. of the 21st International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2022)May 9–13, 2022 Auckland, New
ZealandP. Faliszewski, V. Mascardi, C. Pelachaud, M.E. Taylor (eds.) 2022 2022
??? Zenseact AB Gothenburg Sweden Scool, INRIA Lille- Nord Europe Lille France
Zenseact AB Gothenburg Sweden University of Oslo Oslo Norway

# Risk-Sensitive Bayesian Games for Multi-Agent Reinforcement Learning under
Policy Uncertainty

Hannes Eriksson<EMAIL_ADDRESS>,  Debabrota Basu  ,  Mina
Alibeigi  and  Christos Dimitrakakis

###### Abstract.

In stochastic games with incomplete information, the uncertainty is evoked by
the lack of knowledge about a player’s own and the other players’ types, i.e.
the utility function and the policy space, and also the inherent stochasticity
of different players’ interactions. In existing literature, the risk in
stochastic games has been studied in terms of the inherent uncertainty evoked
by the variability of transitions and actions. In this work, we instead focus
on the risk associated with the uncertainty over types. We contrast this with
the multi-agent reinforcement learning framework where the other agents have
fixed stationary policies and investigate risk-sensitiveness due to the
uncertainty about the other agents’ adaptive policies. We propose risk-
sensitive versions of existing algorithms proposed for risk-neutral stochastic
games, such as Iterated Best Response (IBR), Fictitious Play (FP) and a
general multi-objective gradient approach using dual ascent (DAPG). Our
experimental analysis shows that risk-sensitive DAPG performs better than
competing algorithms for both social welfare and general-sum stochastic games.

###### Key words and phrases:

Bayesian Games, Reinforcement Learning, Risk-Sensitivity, AI Safety

##  1\. Introduction

A Bayesian game (Harsanyi, 1967) is a game of incomplete information in which
multiple players or agents act simultaneously and the corresponding
uncertainty is modelled using Bayesian posterior updates. The goal of the game
is to identify a set of _strategies_ or _policies_ that determine how each of
the agents will interact with the environment while optimising the
corresponding utility functions. We delineate between _pure_ , i.e.
deterministic, and _mixed_ , i.e. stochastic, strategies. Upon fixing the set
of strategies that the agents will use, the game can be evaluated and the
utility of each of the players can be measured. Bayesian game formalism has
been used to model threats in the defence industry (Brynielsson and Arnborg,
2004), autonomous driving (Peng and Tomizuka, 2019), intrusion detection in
wireless networks (Liu et al., 2006), auctions (Naroditskiy and Greenwald,
2007) and more.

Depending on what their individual goals are, the players could act in a
cooperative (Oliehoek et al., 2010), adversarial (Huang and Zhu, 2019) or
individual manner. In the case where all of the players have identical utility
functions, we call the game _cooperative_. If instead, the goal of all the
agents is to maximise the joint utility, we term the game a _social welfare_
game. Further, some agents could attempt to minimise the utility of others, in
that case, we have an _adversarial_ game. Finally, if there is no restriction
on the utility functions, we have a _general_ game. The flexibility of the
framework of the Bayesian game allows for the optimisation of any of these
goals by specifying utility functions for each of the agents. Thus, the risk-
sensitive Bayesian game formulation and the corresponding algorithms that we
propose are independent of the choice of the utility function. Due to brevity
of space, we perform experimental evaluations only for social welfare and
general games.

#### Related Works: Formulations.

A line of research reduces multi-agent reinforcement learning (MARL) to the
stochastic game setting where the agents aim to maximise their own utility
functions (Chalkiadakis and Boutilier, 2003; Heinrich and Silver, 2016;
Lanctot et al., 2017). Under the assumption that all players except one have
fixed stationary strategies, the problem is formulated as a partially
observable Markov decision process (POMDP) and solved using traditional
reinforcement learning (RL) techniques.

Mansour et al. (2021) studied Bayesian games with a focus on incentivising
exploration which induces risk-seeking behaviour in order to learn more about
the task at hand. Tian et al. (2021) investigated the risk inherent to a
stochastic game and provide algorithms for risk-averse agents. The risk
studied in (Capponi et al., 2017; Tian et al., 2021) is more akin to
_aleatory_ , i.e. inherent, risk encountered in RL previously (Mihatsch and
Neuneier, 2002).

In contrast, our work considers the risk associated the incomplete information
about types, i.e. the utility function and policy space. The risk in Bayesian
games due to type uncertainty is connected to the works in RL considering
_epistemic_ risk (Depeweg et al., 2018; Eriksson and Dimitrakakis, 2020) as
the Bayesian game can be considered a multi-task RL problem where multiple
agents are optimised simultaneously. In the case with only one adaptive agent,
this reduces to doing epistemic risk-sensitive RL.

#### Related Works: Algorithms.

A multitude of approaches are proposed to optimise the behaviour of the agents
in Bayesian games. One of the approaches is _Iterated Best Response_ (IBR),
where the algorithm optimises every player’s strategies iteratively by
selecting the best response for one agent given all the other agents. Ho et
al. (1998) used this approach to study problems where multiple developers are
to construct resorts near natural attractions, where each developer is acting
egotistically. In (Naroditskiy and Greenwald, 2007), the authors apply IBR to
identify Bayesian Nash equilibria in auctions. The obtained best-response
strategy in this setting is identical among bidders.

Another approach is _Fictitious Play_ (FP) (Brown, 1951), where one agent is
playing fictitiously against the other. Typically, this is done by letting one
agent play against a combination of the other agent’s past behaviour. For
instance, assuming the other agent’s strategy is an average over all of the
actions it has taken so far. Shapley (1964) shows that for problems with more
players and more strategies per player, as in a Bayesian game, there can exist
solutions without convergence. But in cooperative setting, the fictitious play
demonstrated convergence guarantees Monderer and Shapley (1996). In this work,
we use a variant of FP that is a rolling average over the past weights of the
other agent.

Finally, one can simply optimise all agents simultaneously by updating all of
their strategies by ascending according to each of their objectives. This
approach (for the two-player case) is called _Dual Ascent Policy Gradient_
(DAPG) henceforth in this work. Multi-objective policy gradients have been
studied before in the field of MARL, Lu et al. (2021) propose a safe gradient
descent ascent approach for multiple decentralised agents. A crucial
difference between their and our work is the MARL setting, while our work is
in a Bayesian game. Further, the risk studied in their work is the inherent
(aleatory) risk. Another recent contribution by Kyriakis et al. (2021) involve
multi-objective policy gradients used to identify Pareto optimal solutions
with unknown and linear utility functions for RL. The setting is notably
different as our work focuses on the Bayesian game setting. Likewise, if the
problems is cast as a multi-task setting, something that does not apply to the
general Bayesian game setting, then Sener and Koltun (2018) propose an
applicable solution to identify Pareto optimal solutions using gradient-based
multi-objective learning.

There exist also attempts to unify these frameworks, for instance, Lanctot et
al. (2017) generalises previous approaches, such as IBR, FP and more to a
general framework. From this, they propose a new algorithm, _Policy-Space
Response Oracles_ , which constructs a meta-strategy taking all of the
players’ utilities into account. Another work, by Heinrich and Silver (2016)
develop _Neural Fictitious Self-Play_ , an extension of _Fictitious Self-Play_
(Heinrich et al., 2015), where agents play against themselves, fictitiously.
These strategies are then compared to classical RL algorithms.

Contribution: We propose a novel framework for managing risk due to type
uncertainty in Bayesian games. To the best of our knowledge, this has not been
done before. We relate the risk that arises due to type uncertainty to the
risk of not knowing the policies of the other players in MARL. Finally, we
demonstrate the superiority of the framework of handling this risk
experimentally by introducing three risk-sensitive versions of commonly used
algorithms for solving stochastic games and evaluating them on toy problems.
These are risk-sensitive iterated best response (RS-IBR), risk-sensitive
fictitious play (RS-FP) and risk-sensitive dual ascent policy gradient (RS-
DAPG).

##  2\. Background

A Bayesian game can be defined in a multitude of ways. In this work, we adopt
the framework given by Harsanyi (1967) where a set of players act in an
imperfect information game with a common prior over types.

######  Definition 1 (Bayesian Game).

A Bayesian game can be formulated as
$\mathcal{G}=(N,K,\mathcal{S},\mathcal{A}^{N},\mathcal{R}^{N\times
K},\mathcal{T},\xi,\gamma)$, where $N$ is the number of players, $K$ the
number of possible types, $\mathcal{S}$ the state space of the problem,
$\mathcal{A}_{i}$ the action space of player $i$, $\mathcal{R}_{i}^{j}$ the
reward function of player $i$ for type $j$,
$\mathcal{T}:\mathcal{S}\times\mathcal{A}^{N}\rightarrow\Delta(\mathcal{S})$
the transition distribution of the problem, $\xi$ a common prior over types
and $\gamma$ a common discount factor.

In particular, a Bayesian game $\mathcal{G}$ is equipped with a set of _types_
, $\tau_{1},\tau_{2}$, where each type uniquely specifies the utility function
and behaviour of a player. Thusly, part of the uncertainty associated with a
Bayesian game comes from each player not knowing which type they will be and
what type the other players will be. An agent must then prepare itself for all
possible player and type configurations and arrive at strategies that can
perform well in each scenario.

To evaluate a game $\mathcal{G}$, it needs to commit to a set of policies
$\Pi^{N\times K}$, one policy per player and type combination. We denote the
policies by
$\\{\pi_{1}^{1},\ldots,\pi_{1}^{K},\pi_{2}^{1},\ldots,\pi_{2}^{K}\\}\in\Pi$
for a two-player game with $K$ types. The expected utility $U_{1}^{j,k}$
associated with player $1$, when player $1$ has type $j$ and player $2$ has
type $k$, can be defined in the following way,

$U_{1}^{j,k}(\mathcal{G})\triangleq\mathbb{E}_{\mathcal{G}}^{\pi_{1}^{j},\pi_{2}^{k}}\Big{[}\sum_{t=0}^{\infty}\gamma^{t}r_{1,t}^{j}\,|\,s_{0}=s\Big{]}.$
(1)

Note that the utility associated with type $j$ for player $1$ depends not only
on the policy of player $2$ for type $j$ but for all combinations of types.
Combining all the utilities for a particular player by marginalising over the
prior $\xi$ can be done in the following way,

######  Definition 2 (Expected Utility of a game $\mathcal{G}$).

The expected utility marginalised over the prior $\xi$ for a given game
$\mathcal{G}$ is

$\displaystyle U_{1},U_{2}$
$\displaystyle\triangleq\mathbb{E}_{\xi}\Big{[}U_{1}^{j,k}(\mathcal{G}),U_{2}^{j,k}(\mathcal{G})\Big{]}$
(2)
$\displaystyle=\sum_{j=1}^{K}\sum_{k=1}^{K}\xi(\tau_{1}=j,\tau_{2}=k)(U_{1}^{j,k}(\mathcal{G}),U_{2}^{j,k}(\mathcal{G})).$
(3)

##  3\. Risk in Bayesian games

In this work, the risk associated with the uncertainty about types is studied.
That is, $\xi$, combined with the utility of each of the individual players
for that particular type configuration. $U_{1}^{.,.}$ and $U_{2}^{.,.}$ are
thus discrete probability distributions with mass equal to
$\xi(\tau_{1}=j,\tau_{2}=k)$ and values $U_{1}^{j,k}$ and $U_{2}^{j,k}$. By
considering all possible combinations of types we get the following
probability mass function,

$p_{U_{1}}(U)=\begin{cases}U_{1}^{1,1},&\xi(\tau_{1}=1,\tau_{2}=1)\\\
U_{1}^{1,2},&\xi(\tau_{1}=1,\tau_{2}=2)\\\ &\vdots\\\
U_{1}^{K,K},&\xi(\tau_{1}=K,\tau_{2}=K),\end{cases}$ (4)

and similarly for the other agent, $p_{U_{2}}(U)$. In this work, we consider
conditional value-at-risk (CVaR), studied for instance by Artzner et al.
(1999), which is a risk measure that focuses on the $\alpha\%$ worst-case
outcomes of the distribution. CVaR can be defined as follows,
$CVaR_{\alpha}(U)\triangleq\mathbb{E}[U\,|\,U\leq\nu_{\alpha}\land\mathbb{P}(U\geq\nu_{a})=1-\alpha]$.

Earlier works (Eriksson et al., 2021; Rigter et al., 2021) have shown that
coherent risk measures, like CVaR, can be written as perturbed distribution
functions, and expectation is taken w.r.t the perturbed distribution yields
risk-adjusted utilities.

##  4\. Algorithms

In this section, we describe the basis of the risk-sensitive algorithms
proposed in this work. They are, IBR, FP and DAPG with respective risk-
sensitive versions RS-IBR, RS-FP and RS-DAPG. All algorithms use softmax
policies

$\pi_{1}^{j}(a\,|\,s)=\frac{e^{\theta_{1,s}^{j,a}}}{\sum_{a^{\prime}\in\mathcal{A}_{1}}e^{\theta_{1,s}^{j,a^{\prime}}}},$
(5)

for type $\tau_{1}=j$ and player $1$. $\theta\in\mathbb{R}^{N\times
K\times|\mathcal{S}|\times|\mathcal{A}|}$ is thus the full parameter set.

###  4.1. Iterated Best Response

IBR (Ho et al., 1998; Naroditskiy and Greenwald, 2007; Bopardikar et al.,
2017) is an algorithm that iteratively identifies the optimal policy for a
given player, keeping the policies of all other players fixed. Since IBR also
only updates a subset of the available parameters at each iteration, it might
have convergence problems for the general setting. The IBR procedure can be
seen in Algorithm 1.

###  4.2. Fictitious Play

One application of the FP (Brown, 1951; Shapley, 1964; Monderer and Shapley,
1996) framework can be seen in Algorithm 1. The setup is similar to that of
IBR but with the important distinction that the objective is taken w.r.t a
rolling average of the previous parameters of agent one for agent two, where
$\bar{\theta}_{1,i+1}\triangleq\frac{1}{i+1}\sum_{j=0}^{i+1}\theta_{{1,j}}$.

###  4.3. Dual Ascent Policy Gradient

The final algorithm uses the utilities from multiple objectives to compute a
gradient step over the whole parameter set. As there are only two agents, with
one objective respectively, the algorithm is termed dual ascent and is
ascending simultaneously using both objectives. Note that the gradient
$\nabla_{\theta_{1}^{j}}[U_{1}\,|\,\mathcal{G},\theta]$ is non-zero for the
type selections $\\{\tau_{1}=j,\tau_{2}=1\ldots K\\}$ for both objective
$U_{1}$ and $U_{2}$. The algorithm is displayed in Algorithm 2.

Algorithm 1 Risk-Sensitive Iterated Best Response/Fictitious Play (RS-IBR/FP)

1: input : Game $\mathcal{G}$, learning rates $\eta_{1},\eta_{2}$, risk
measure $\rho_{\alpha}$

2: for $i=0\ldots\,$ convergence do

3: for $t=0\ldots\,$ convergence do

4:
$\theta_{1,i}^{t+1}=\theta_{1,i}^{t}+\eta_{1}\nabla_{\theta_{1}}\big{[}\rho_{\alpha}(U_{1})\,|\,\mathcal{G},\theta_{1,i}^{t},\theta_{2,i}\big{]}$

5: end for

6: $\theta_{1,i+1}=\theta_{1,i}^{t}$

7: for $t=0\ldots\,$ convergence do

8: if IBR then

9:
$\theta_{2,i}^{t+1}=\theta_{2,i}^{t}+\eta_{2}\nabla_{\theta_{2}}\big{[}\rho_{\alpha}(U_{2})\,|\,\mathcal{G},\theta_{1,i+1},\theta_{2,i}^{t}\big{]}$

10: end if

11: if FP then

12:
$\theta_{2,i}^{t+1}=\theta_{2,i}^{t}+\eta_{2}\nabla_{\theta_{2}}\big{[}\rho_{\alpha}(U_{2})\,|\,\mathcal{G},\bar{\theta}_{1,i+1},\theta_{2,i}^{t}\big{]}$

13: end if

14: end for

15: $\theta_{2,i+1}=\theta_{2,i}^{t}$

16: end for

Algorithm 2 Risk-Sensitive Dual Ascent Policy Gradient (RS-DAPG)

1: input : Game $\mathcal{G}$, learning rates $\eta_{1},\eta_{2}$, risk
measure $\rho_{\alpha}$

2: for $i=0\ldots\,$ convergence do

3: for $j=1\ldots K$ do

4:
$\theta_{1,i+1}^{j}=\theta_{1,i}^{j}+\eta_{1}\nabla_{\theta_{1}^{j}}\Big{(}\big{[}\rho_{\alpha}(U_{1})\,|\,\mathcal{G},\theta_{i}\big{]}+\big{[}\rho_{\alpha}(U_{2})\,|\,\mathcal{G},\theta_{i}\big{]}\Big{)}$

5:
$\theta_{2,i+1}^{j}=\theta_{2,i}^{j}+\eta_{2}\nabla_{\theta_{2}^{j}}\Big{(}\big{[}\rho_{\alpha}(U_{1})\,|\,\mathcal{G},\theta_{i}\big{]}+\big{[}\rho_{\alpha}(U_{2})\,|\,\mathcal{G},\theta_{i}\big{]}\Big{)}$

6: end for

7: end for

##  5\. Experiments

Table 1. Social welfare setting, evaluated over $100$ toy experiments. The first column indicates the algorithm evaluated. If the algorithm is prefixed by RS-, then it uses a risk-sensitive objective. The second column is the social welfare objective $(U_{1}+U_{2})/2$. An algorithm with higher social welfare performed better. The third column displays the risk-adjusted social welfare objective, using CVaR with threshold parameter $\alpha=0.25$. All results are averaged over $100$ different games and the mean and standard deviation is reported. Agent |  Social Welfare $\pm\sigma$ |  CVaRα=0.25 Social Welfare $\pm\sigma$
---|---|---
MMBI (Dimitrakakis, 2011) | $5.69\pm 3.10$ | $-5.54\pm 10.56$
IBR (Ho et al., 1998; Naroditskiy and Greenwald, 2007; Bopardikar et al., 2017) | $2.57\pm 2.65$ | $-1.10\pm 7.30$
FP (Brown, 1951; Shapley, 1964; Monderer and Shapley, 1996) | $2.60\pm 2.64$ | $-1.11\pm 7.35$
DAPG | $\mathbf{6.01\pm 3.04}$ | $-9.40\pm 9.58$
RS-MMBI (Eriksson and Dimitrakakis, 2020) | $-4.41\pm 3.97$ | $22.84\pm 14.02$
RS-IBR | $-1.79\pm 3.10$ | $12.67\pm 10.13$
RS-FP | $-1.77\pm 3.11$ | $12.6\pm 10.17$
RS-DAPG | $-4.21\pm 3.13$ | $\mathbf{23.73\pm 13.18}$
Table 2. General setting, evaluated over $100$ toy experiments. The first column indicates the algorithm evaluated. If the algorithm is prefixed by RS-, then it uses a risk-sensitive objective. The second and third columns are the individual utilities of the agents, $U_{1},U_{2}$. The fourth and fifth columns display the risk-adjusted individual utility for the respective player, using CVaR with threshold parameter $\alpha=0.25$. All results are averaged over $100$ different games and the mean and standard deviation is reported. Agent | Utility${}_{1}\pm\sigma$ | Utility${}_{2}\pm\sigma$ |  CVaRα=0.25 Utility${}_{1}\pm\sigma$ |  CVaRα=0.25 Utility${}_{2}\pm\sigma$
---|---|---|---|---
MMBI (Dimitrakakis, 2011) | $5.50\pm 5.03$ | $5.88\pm 5.31$ | $-3.73\pm 14.93$ | $-2.64\pm 17.16$
IBR (Ho et al., 1998; Naroditskiy and Greenwald, 2007; Bopardikar et al., 2017) | $3.98\pm 3.92$ | $0.13\pm 3.81$ | $-3.50\pm 11.25$ | $8.67\pm 12.93$
FP (Brown, 1951; Shapley, 1964; Monderer and Shapley, 1996) | $3.86\pm 3.78$ | $0.21\pm 3.74$ | $-3.16\pm 9.89$ | $8.72\pm 12.84$
DAPG | $\mathbf{5.93}\pm\mathbf{4.74}$ | $\mathbf{6.09}\pm\mathbf{4.71}$ | $-6.19\pm 14.13$ | $-5.81\pm 14.04$
RS-MMBI (Eriksson and Dimitrakakis, 2020) | $-4.45\pm 6.11$ | $-4.37\pm 5.66$ | $22.48\pm 18.15$ | $24.63\pm 22.04$
RS-IBR | $-2.74\pm 4.90$ | $0.68\pm 4.24$ | $18.04\pm 14.88$ | $6.19\pm 12.14$
RS-FP | $-1.98\pm 4.87$ | $2.43\pm 3.09$ | $18.35\pm 9.99$ | $1.30\pm 8.70$
RS-DAPG | $-4.76\pm 5.80$ | $-4.50\pm 5.37$ | $\mathbf{25.60}\pm\mathbf{18.47}$ | $\mathbf{26.53}\pm\mathbf{22.03}$

We investigate randomly generated toy problems, where $\mathcal{T}$ is
generated from a product of Dirichlet distributions, all with parameter
$\alpha=1$. The individual reward functions for the players and types are also
randomly generated, where $\mathcal{R}$ is generated from a product of normal
distributions with parameters $\mu=0,\sigma=1$. Performance of the algorithms
is then evaluated in two distinct settings, one where the social welfare is
maximised and the other in a general multi-objective setting.

The metrics of interest in the social welfare setting is the average utility
$(U_{1}+U_{2})/2$ among the players and a risk-adjusted version of it,
$CVaR_{\alpha}[(U_{1}+U_{2})/2]$, where $\alpha\in(0,1]$ is a parameter that
controls for the sensitivity to risk. Larger values of utility are better and
likewise larger risk-adjusted utilities are preferred.

In the general setting with multiple objectives, we study the individual
utilities among the agents and the algorithms with the best performance is the
set of non-dominated algorithms in a Pareto optimality sense.

###  5.1. Social Welfare

A stochastic game consisting of multiple players with a common goal to
maximise the social welfare can be re-instantiated as a Bayesian MDP, which
can be solved approximately using backward induction, see MMBI in Dimitrakakis
(2011) for the risk-neutral case and RS-MMBI in Eriksson and Dimitrakakis
(2020) for the risk-sensitive case. The results acquired from evaluating the
social welfare setting is summarised in Table 1.

###  5.2. General Case

In the general case, there are multiple objectives, one for each agent. We,
therefore, study the concept of Pareto optimality (Banerjee and Sen, 2007) to
determine which algorithms produce the best results. Figure 1 displays the
Pareto front by the non-shaded region. The points in the shaded region are all
dominated by points in the non-shaded region. The Pareto front of dominating
algorithms, $P(\mathbf{A})$, can be defined as,

$P(\mathbf{A})\triangleq\\{A_{1}\in\mathbf{A}:\\{A_{2}\in\mathbf{A}:A_{2}\succ
A_{1},A_{1}\neq A_{2}\\}=\emptyset\\},$ (6)

that is, the set of non-dominated algorithms in $\mathbf{A}$. The Pareto
fronts of the risk-neutral and risk-sensitive objectives as seen in Figure 1
seem to indicate the general gradient approach in Algorithm 2 is superior to
the IBR and FP approaches. In Table 2 we can see that the risk-sensitive
algorithms outperform the risk-neutral algorithms when optimising for the
risk-sensitive objective as one would expect. Likewise, for the risk-neutral
objective, the risk-neutral algorithms outperform. We can see that the pure
strategies generated by MMBI and RS-MMBI perform well, although they are
bested by the dual ascent approach in both settings.

Figure 1. Pareto front the utilities in the toy experiment averaged over $100$
experiments. The shaded region indicates non-domination and the points in the
non-shaded region are admissible solutions that are considered equivalent.

##  6\. Discussion and Future Work

Extensions of this work would include evaluation of the algorithms in the
cooperative settings described in Dimitrakakis et al. (2017), they are,
Multilane Highway and Food and Shelter which would be interesting testbeds for
the algorithms. Another setting to consider is given by Tian et al. (2021)
which is a navigation task evaluated for risk-sensitive games. In their work,
they also describe another interesting risk measure.

Proper convergence analysis of the dual ascent policy gradient algorithm for
Bayesian games is also something worth looking into as well as the
identification of the Pareto optimal set of solutions in order to study
Bayesian Nash equilibria in this setting.

This work was partially supported by the Wallenberg AI, Autonomous Systems and
Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation and
the computations were performed on resources at Chalmers Centre for
Computational Science and Engineering (C3SE) provided by the Swedish National
Infrastructure for Computing (SNIC).

## References

  * (1)
  * Artzner et al. (1999) Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath. 1999.  Coherent measures of risk.  _Mathematical finance_ 9, 3 (1999), 203–228.
  * Banerjee and Sen (2007) Dipyaman Banerjee and Sandip Sen. 2007.  Reaching pareto-optimality in prisoner’s dilemma using conditional joint action learning.  _Autonomous Agents and Multi-Agent Systems_ 15, 1 (2007), 91–108.
  * Bopardikar et al. (2017) Shaunak D Bopardikar, Alberto Speranzon, and Cédric Langbort. 2017.  Convergence analysis of Iterated Best Response for a trusted computation game.  _Automatica_ 78 (2017), 88–96.
  * Brown (1951) George W Brown. 1951\.  Iterative solution of games by fictitious play.  _Activity analysis of production and allocation_ 13, 1 (1951), 374–376.
  * Brynielsson and Arnborg (2004) Joel Brynielsson and Stefan Arnborg. 2004.  Bayesian games for threat prediction and situation analysis. Citeseer.
  * Capponi et al. (2017) Agostino Capponi, Reza Ghanadan, and Matt Stern. 2017\.  Risk-Sensitive Cooperative Games for Human-Machine Systems.  _arXiv preprint arXiv:1705.09580_ (2017).
  * Chalkiadakis and Boutilier (2003) Georgios Chalkiadakis and Craig Boutilier. 2003.  Coordination in multiagent reinforcement learning: A Bayesian approach. In _Proceedings of the second international joint conference on Autonomous agents and multiagent systems_. 709–716.
  * Depeweg et al. (2018) Stefan Depeweg, Jose-Miguel Hernandez-Lobato, Finale Doshi-Velez, and Steffen Udluft. 2018\.  Decomposition of Uncertainty in Bayesian Deep Learning for Efficient and Risk-sensitive Learning. In _International Conference on Machine Learning_. 1192–1201.
  * Dimitrakakis (2011) C. Dimitrakakis. 2011\.  Robust Bayesian reinforcement learning through tight lower bounds. In _European Workshop on Reinforcement Learning (EWRL 2011)_. 177–188.
  * Dimitrakakis et al. (2017) Christos Dimitrakakis, David C Parkes, Goran Radanovic, and Paul Tylkin. 2017.  Multi-view decision processes: the helper-ai problem.  _Advances in Neural Information Processing Systems_ 30 (2017).
  * Eriksson et al. (2021) Hannes Eriksson, Debabrota Basu, Mina Alibeigi, and Christos Dimitrakakis. 2021.  Sentinel: Taming uncertainty with ensemble-based distributional reinforcement learning.  _arXiv preprint arXiv:2102.11075_ (2021).
  * Eriksson and Dimitrakakis (2020) Hannes Eriksson and Christos Dimitrakakis. 2020.  Epistemic Risk-Sensitive Reinforcement Learning. In _ESANN_.
  * Harsanyi (1967) John C Harsanyi. 1967\.  Games with incomplete information played by “Bayesian” players, I–III Part I. The basic model.  _Management science_ 14, 3 (1967), 159–182.
  * Heinrich et al. (2015) Johannes Heinrich, Marc Lanctot, and David Silver. 2015\.  Fictitious self-play in extensive-form games. In _International conference on machine learning_. PMLR, 805–813.
  * Heinrich and Silver (2016) Johannes Heinrich and David Silver. 2016.  Deep reinforcement learning from self-play in imperfect-information games.  _arXiv preprint arXiv:1603.01121_ (2016).
  * Ho et al. (1998) Teck-Hua Ho, Colin Camerer, and Keith Weigelt. 1998\.  Iterated dominance and iterated best response in experimental” p-beauty contests”.  _The American Economic Review_ 88, 4 (1998), 947–969.
  * Huang and Zhu (2019) Linan Huang and Quanyan Zhu. 2019.  Dynamic bayesian games for adversarial and defensive cyber deception.  In _Autonomous cyber deception_. Springer, 75–97.
  * Kyriakis et al. (2021) Panagiotis Kyriakis, Jyotirmoy Deshmukh, and Paul Bogdan. 2021\.  Pareto Policy Adaptation. In _International Conference on Learning Representations_.
  * Lanctot et al. (2017) Marc Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. 2017.  A unified game-theoretic approach to multiagent reinforcement learning.  _Advances in neural information processing systems_ 30 (2017).
  * Liu et al. (2006) Yu Liu, Cristina Comaniciu, and Hong Man. 2006\.  A Bayesian game approach for intrusion detection in wireless ad hoc networks. In _Proceeding from the 2006 workshop on Game theory for communications and networks_. 4–es.
  * Lu et al. (2021) Songtao Lu, Kaiqing Zhang, Tianyi Chen, Tamer Basar, and Lior Horesh. 2021.  Decentralized policy gradient descent ascent for safe multi-agent reinforcement learning. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 35. 8767–8775.
  * Mansour et al. (2021) Yishay Mansour, Alex Slivkins, Vasilis Syrgkanis, and Zhiwei Steven Wu. 2021.  Bayesian exploration: Incentivizing exploration in bayesian games.  _Operations Research_ (2021).
  * Mihatsch and Neuneier (2002) O. Mihatsch and R. Neuneier. 2002.  Risk-sensitive reinforcement learning.  _Machine learning_ 49, 2-3 (2002), 267–290.
  * Monderer and Shapley (1996) Dov Monderer and Lloyd S Shapley. 1996.  Fictitious play property for games with identical interests.  _Journal of economic theory_ 68, 1 (1996), 258–265.
  * Naroditskiy and Greenwald (2007) Victor Naroditskiy and Amy Greenwald. 2007.  Using iterated best-response to find Bayes-Nash equilibria in auctions. In _PROCEEDINGS OF THE NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE_ , Vol. 22. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 1894\.
  * Oliehoek et al. (2010) Frans A Oliehoek, Matthijs TJ Spaan, Jilles Steeve Dibangoye, and Christopher Amato. 2010\.  Heuristic search for identical payoff Bayesian games.. In _AAMAS_. 1115–1122.
  * Peng and Tomizuka (2019) Cheng Peng and Masayoshi Tomizuka. 2019.  Bayesian persuasive driving. In _2019 American Control Conference (ACC)_. IEEE, 723–729.
  * Rigter et al. (2021) Marc Rigter, Bruno Lacerda, and Nick Hawes. 2021\.  Risk-averse bayes-adaptive reinforcement learning.  _Advances in Neural Information Processing Systems_ 34 (2021).
  * Sener and Koltun (2018) Ozan Sener and Vladlen Koltun. 2018.  Multi-task learning as multi-objective optimization.  _Advances in neural information processing systems_ 31 (2018).
  * Shapley (1964) Lloyd Shapley. 1964\.  Some topics in two-person games.  _Advances in game theory_ 52 (1964), 1–29.
  * Tian et al. (2021) Ran Tian, Liting Sun, and Masayoshi Tomizuka. 2021.  Bounded risk-sensitive markov games: Forward policy design and inverse reward learning with iterative reasoning and cumulative prospect theory. In _AAAI Conference on Artificial Intelligence_.


# An Extension to Basis-Hypervectors for Learning from Circular Data in
Hyperdimensional Computing

Igor Nunes, Mike Heddes, Tony Givargis and Alexandru Nicolau  Department of
Computer Science, University of California, IrvineIrvineCaliforniaUnited
States of America igord,mheddes, givargis<EMAIL_ADDRESS>
(2018)

###### Abstract.

Hyperdimensional Computing (HDC) is a computation framework based on
properties of high-dimensional random spaces. It is particularly useful for
machine learning in resource-constrained environments, such as embedded
systems and IoT, as it achieves a good balance between accuracy, efficiency
and robustness. The mapping of information to the hyperspace, named encoding,
is the most important stage in HDC. At its heart are basis-hypervectors,
responsible for representing the smallest units of meaningful information. In
this work we present a detailed study on basis-hypervector sets, which leads
to practical contributions to HDC in general: 1) we propose an improvement for
level-hypervectors, used to encode real numbers; 2) we introduce a method to
learn from circular data, an important type of information never before
addressed in machine learning with HDC. Empirical results indicate that these
contributions lead to considerably more accurate models for both
classification and regression with circular data.

hyperdimensional computing, basis-hypervectors, circular data, machine
learning, information theory.

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06††ccs: Computing methodologies Machine
learning††ccs: Computing methodologies Parallel computing methodologies††ccs:
Mathematics of computing Information theory

##  1\. Introduction

For some time now, machine learning has largely dictated not just academic
research and industrial applications, but aspects of modern society in
general. Such aspects range from the widespread recommendation systems, which
influence the way we consume products, news and entertainment, to social
networks that impact the way we behave and relate. Given such broad
importance, the demand for devices capable of learning has spread to resource
constrained platforms such as embedded systems and internet of things (IoT)
devices (Kaelbling, 1993; Branco et al., 2019). Such scenarios present
obstacles to established methods, designed primarily to operate on powerful
servers.

The most notable class of such methods is Deep Learning, which has achieved
superhuman performance on certain tasks (Schmidhuber, 2015). Although
initially inspired by the remarkably efficient animal brain, Deep Learning
owes much of its high energy and computational cost to neurally implausible
design choices (Crick et al., 1989; Marblestone et al., 2016; Whittington and
Bogacz, 2019). The dilemma is that these choices, especially error back-
propagation and large depth, are also key drivers of its success (LeCun et
al., 2015). In this context, the search for alternatives has received
significant attention from the scientific community (James et al., 2017;
Denève et al., 2017; Kanerva, 1988).

One emerging alternative is Hyperdimensional Computing (HDC) (Kanerva, 2009).
Like Deep Learning, HDC is also inspired by neuroscience, but the central
observation is that large circuits are fundamental to the brain’s computation.
Therefore, information in HDC is represented using hypervectors, typically
10,000-bit words where each bit is independently and identically distributed
(i.i.d). The i.i.d relationship between bits, also known as holographic
information representation, provides inherent robustness since each bit
carries exactly the same amount of information. Furthermore, the arithmetic in
HDC, as detailed in Section 2, is generally dimension-independent, which opens
up the opportunity for massive parallelism, providing the efficiency sought in
HDC.

HDC has already proven to be useful in several applications, including both
learning problems, such as classification (Ge and Parhi, 2020) and regression
(Hersche et al., 2020), and classical problems, such as consistent hashing
(Heddes et al., 2022). Regardless of the application, the most fundamental
step in HDC is mapping objects in the input space to the hyperspace, a process
called encoding. Useful encoding functions have already been proposed for
several different types of data, such as time series (Rahimi et al., 2016a),
text (Rahimi et al., 2016b), images (Manabat et al., 2019) and graphs (Nunes
et al., 2022). All these encodings have one thing in common: they start by
encoding simple information (e.g. pixel values, vertices and edges, letters,
amplitudes of a signal), which are then combined to represent something
complex. In this work we study basis-hypervectors, the encoding of these
atomic pieces of information.

Basis-hypervectors are a cornerstone of HDC and directly effect the accuracy
of learned HDC models, as will be evident from the results in Section 6.
Nevertheless, to the best of our knowledge, this is the first work with a
primary focus on the study of basis-hypervectors. We start with a comparative
study of the two existing types of basis-hypervectors, random and level-
hypervectors, used respectively to represent uncorrelated and linearly-
correlated data. Inspired by information theory, our first contribution is an
improved method to create level-hypervectors.

Based on the improved level-hypervectors, our main contribution is a basis-
hypervector set for circular data in a learning setting. Circular data are
derived from the measurement of directions, usually expressed as an angle from
a fixed reference direction. In addition, it is common to convert time
measurements, such as the hours of a day, to angles. As we will discuss in
more detail in Section 5, circular data is present in many fields of research,
including astronomy, medicine, engineering, biology, geology and meteorology
(Fisher, 1995; Lee, 2010; Mardia et al., 2000). Embedded systems and IoT also
deal with a wide variety of circular data, such as in robotics where the
joints generate angular data (Gao et al., 2014), and satellites that fly in
elliptical orbits (Lucas and Boumghar, 2017). The importance is such that the
study and interpretation of this type of data gave rise to a subdiscipline of
statistics called directional statistics (also known as circular or spherical
statistics) (Mardia et al., 2000; Pewsey and García-Portugués, 2021). Despite
this great relevance, our work is the first to address learning from circular
data in HDC.

To assess the practical impact of these contributions, we conducted
experiments with publicly available datasets that contain circular data
relevant to real-world applications. We compared the proposed basis set with
the two existing ones in both regression and classification tasks. We obtained
an improvement of 7.2% in the classification of 15 types of surgical gestures.
In regression, the error is reduced by 67.7% in temperature and power level
prediction tasks.

##  2\. Hyperdimensional Computing

Hyperdimensional Computing (HDC) is a computation model that relies on very
high dimensionality and randomness. Inspired by neuroscience, it seeks to
mimic and exploit important characteristics of the animal brain while
balancing accuracy, efficiency and robustness (Kanerva, 2009). The central
idea is to represent inputs $x\in\mathcal{X}$ by projecting them onto a
hyperspace $\mathcal{H}=\\{0,1\\}^{d}$, with $d\approx 10{,}000$ dimensions.
This mapping $\phi:\mathcal{X}\to\mathcal{H}$ is called encoding, and the
resulting representations $\phi(x)$ are named hypervectors.

The intuitive principle that guides the design of encoding functions is that
similar objects in input space need to be mapped to similar hypervectors in
hyperspace. We use the normalized Hamming distance as a measure of distance
between hypervectors, which takes the form:

$\displaystyle\delta:\mathcal{H}\times\mathcal{H}\to\\{\sigma\in\mathbb{R}\mid
0\leq\sigma\leq 1\\}$

We then define the hypervector similarity to be $1-\delta$. All cognitive
tasks in HDC are ultimately based on similarity. Predictions or decisions are
inferred from a model which is created by transforming and combining
information using HDC arithmetic.

###  2.1. Operations

The arithmetic in HDC is based on a simple set of two element-wise, dimension-
independent, operations in addition to a permutation operator (Kanerva, 2009).
The three operations, binding, bundling, and permuting are illustrated in
Figure 1.

#### Binding

The binding operation is used to “associate” information. The function
$\otimes:\mathcal{H}\times\mathcal{H}\to\mathcal{H}$ multiplies two input
hypervectors to produces a third vector dissimilar to both the operands. The
binding operator is commutative and distributive over bundling and serves at
its own inverse, i.e., $A\otimes(A\otimes B)=B$. The binding operation is
efficiently implemented as element-wise XOR.

#### Bundling

The bundling operation is used to represent a set of information. The function
$\oplus:\mathcal{H}\times\mathcal{H}\to\mathcal{H}$ performs addition on its
inputs to produce an output hypervector that is similar to its operands.
Bundling is implemented as an element-wise majority operation. The output then
represents the mean-vector of its inputs.

#### Permuting

The permutation operator is often used to establish an order, that is, to
differentiate permutations of a sequence. The function takes the form
$\Pi:\mathcal{H}\to\mathcal{H}$, whose output hypervector is dissimilar to the
input. The exact input can be retrieved with the inverse operation. The
operator performs multiplication with a permutation matrix and the most common
is a cyclic shift. With $\Pi^{i}(A)$ we denote a cyclic shift of the elements
of $A$ by $i$ coordinates.

$\dots$

M

M

$\dots$

M

$\dots$$\dots$$A^{1}$$A^{2}$$A^{d}$$B^{1}$$B^{2}$$B^{d}$$A^{1}$$A^{2}$$A^{d}$$B^{1}$$B^{2}$$B^{d}$$A^{1}$$A^{2}$$A^{d-1}$$A^{d}$$C^{1}$$C^{2}$$C^{d}$$C^{1}$$C^{2}$$C^{d}$$C^{1}$$C^{2}$$C^{3}$$C^{d}$
Figure 1.  Binding, bundling, and cyclic shift permutation operations
illustrated on binary hypervectors $A$ and $B$ where the superscript denotes
the element index of the hypervector. The logical gates in the bundling
operation are majority gates.

Much of HDC’s ability to learn comes from the fact that the very high
dimension of the $\mathcal{H}$-space allows combining information with these
operations while preserving the information of the operands with high
probability, due to the existence of a huge number of quasi-orthogonal vectors
in the space. For a more theoretical analysis of these properties see the work
by Thomas et al. (Thomas et al., 2021).

###  2.2. Classification

Once the encoding function $\phi$ is defined, the training of a classification
model with HDC is quite intuitive. An overview of the standard HDC
classification framework is illustrated in Figure 2. For each class
$i\in\\{1,\dots,k\\}$ in the training set, we construct a hypervector $M_{i}$
as follows:

$\displaystyle M_{i}=\bigoplus_{j:\ell(x_{j})=i}\phi(x_{j})$

where each $x_{j}\in{\mathcal{X}}$ is a training sample and
$\ell(x_{j})\in\\{1,\dots,k\\}$ its respective label. The $\bigoplus$ symbol
represents the bundling of hypervectors. The hypervector $M_{i}$ has the
smallest average distance to the hypervectors obtained by encoding the
training samples of class $i$. For this reason, each of these hypervectors is
used as a “prototype” of its respective class and is referred to as a class-
vector. A trained HDC classification model is therefore denoted by
$\mathcal{M}=\\{M_{i},\dots,M_{k}\\}$, and simply consists of a class-vector
for each class.

Y1.0e0]ptTestdataTraindataEncoderTrainingModel$M_{1}$$M_{2}$$...$$M_{k}$Query
vectorSimilarities Figure 2.  Overview of the Hyperdimensional Computing
classification framework. Solid lines indicate training steps, dashed lines
indicate inference steps.

Given an unlabeled input $\hat{x}\in\mathcal{X}$, i.e., a test sample, and a
trained model $\mathcal{M}$, we simply compare $\phi(\hat{x})$, the query-
vector, with each class-vector and infer that the label of $\hat{x}$ is the
one that corresponds to the most similar class-vector:

$\displaystyle\ell^{\star}(\hat{x})=\underset{i\in\\{1,\dots,k\\}}{\arg\min}\;\delta\left(\phi(\hat{x}),M_{i}\right)$

where $\ell^{\star}(\hat{x})\in\\{1,\dots,k\\}$ is the predicted class for
$\hat{x}$.

###  2.3. Regression

In a regression setting, the model $\mathcal{M}$ consists of a single
hypervector, which memorizes training samples with their associated label.
This is different from the classification setting where a sample’s class is
implicitly stored as the index of the class-vector. The label of each sample
in a regression setting is a real number $\ell(x)\in\mathbb{R}$. To encode a
label, an invertible encoding function $\phi_{\ell}$, which maps real numbers
to hypervectors, needs to be introduced. The invertibility property is needed
to allow labels to be determined during inference. The function’s output is a
finite subset $\mathbf{L}=\\{L_{1},\dots,L_{k}\\}$ of all hypervectors in
$\mathcal{H}$ whose generation is discussed in Section 4. The hypervectors in
$\mathbf{L}$ are linearly correlated such that the closer the real numbers
they represent, the more similar the hypervectors are. A model is then
obtained as follows:

$\displaystyle\mathcal{M}=\bigoplus_{i}\phi(x_{i})\otimes\phi_{\ell}(\ell(x_{i}))$

A prediction can be made given a trained model $\mathcal{M}$ and an unlabeled
input $\hat{x}\in\mathcal{X}$. First the approximate label hypervector is
obtained by binding the model with the encoded sample
$\mathcal{M}\otimes\phi(\hat{x})\approx\phi_{\ell}(\ell(\hat{x}))$ which
exploits the self-inverse property of binding. The remaining terms add noise,
making it approximately equal (Kanerva, 2009; Thomas et al., 2021). The
precise label hypervector is then the most similar label hypervector $L_{l}$,
where:

$\displaystyle
l=\underset{i\in\\{1,\dots,k\\}}{\arg\min}\;\delta\left(\mathcal{M}\otimes\phi(\hat{x}),L_{i}\right)$

Finally, the label is obtained by decoding the label hypervector using the
inverse of the label encoding function:

$\displaystyle\ell^{\star}(\hat{x})=\phi_{\ell}^{-1}(L_{l})$

The encoding functions $\phi$ and $\phi_{\ell}$, used in both classification
and regression, are domain specific and use the HDC operations to encode
complex information (e.g., a word) by combining simpler, atomic pieces of
information (e.g., the letters of a word). An example encoding for words is
discussed in Section 3.1. The first important decision in designing an HDC
encoding is how to represent atomic information as hypervectors. These
hypervectors represent the smallest pieces of meaningful information and are
referred to as basis-hypervectors. These sets are the central subject in this
paper. Our main goal is to show that a special set of basis-hypervectors
(described in Section 5) is more appropriate for dealing with circular data.

##  3\. Basis-Hypervectors

In this section we describe the two existing basis-hypervector sets. These are
stochastically created hypervector sets used to encode the smallest units of
meaningful information. Their main feature is the pairwise distance as
illustrated in Figure 3. This section serves as background for Section 5,
where we present another basis set never before applied to learning.

Figure 3.  Pairwise similarity of each $i$-th and $j$-th hypervector within a
basis-hypervector set of size 12. Comparing between random, level and circular
basis-hypervectors.

###  3.1. Encoding symbols

Early applications in HDC were learning from sequences of symbols such as text
data (Rahimi et al., 2016b). The units of information, in this case
characters, were mapped (one-to-one) to hypervectors
$\mathbf{R}=\\{R_{1},\dots,R_{m}\\}$ sampled uniformly at random from the
hyperspace $\mathcal{H}$, called random-hypervectors. From this, a word
$w=\\{\alpha_{1},\dots,\alpha_{n}\\}$ is typically encoded as:

$\displaystyle\phi(w)=\bigoplus_{i=1}^{n}\Pi^{i}\big{(}\phi_{\mathbf{R}}(\alpha_{i})\big{)}$

where $\phi_{\mathbf{R}}(\alpha_{i})\in\mathbf{R}$ maps the character
$\alpha_{i}$ to its corresponding random-hypervector $R_{i}$, and $\Pi$ is the
permutation operation which ensures that information about the location of
each character in the word is preserved. In general, any sequence or set
comprised of symbolic or categorical data can be encoded using random-
hypervectors.

Because of the high dimensionality of $\mathcal{H}$, each pair of symbols
$R_{i}$ and $R_{j}$ in $\mathbf{R}$ (with $i\neq j$) is quasi-orthogonal with
high probability (Kanerva, 1988). In other words, there is no correlation
between the hypervectors in the $\mathbf{R}$ basis set. While this seems
suitable for encoding letters, which to some extent represent unrelated
information, clearly it is not as adequate for other kinds of unitary
information, such as real numbers.

###  3.2. Encoding real numbers

Many domains use real numbers to represent information such as distance, time,
energy and velocity. Representing these values in $\mathcal{H}$-space requires
a mapping to a discrete set of hypervectors
$\mathbf{L}=\\{L_{1},\dots,L_{m}\\}$. A real number is mapped to a hypervector
with the encoding function $\phi_{\mathbf{L}}$.

Let $[a,b]$ denote the interval $\\{x\in\mathbb{R}\mid a\leq x\leq b\\}$ we
want to represent. The first step is to place $m$ points
$\\{\xi_{1},\dots,\xi_{m}\\}$ evenly over the interval $[a,b]$, where:

$\displaystyle\xi_{i}=a+(i-1)\frac{b-a}{m-1}$

Any real number $x$ is then represented in the hyperspace by
$\phi_{\mathbf{L}}(x)=L_{l}$, where:

$\displaystyle l=\underset{i\in\\{1,\dots,m\\}}{\arg\min}\;\lvert
x-\xi_{i}\rvert$

The central question here is how to construct the set of hypervectors
$\mathbf{L}$. One might again consider using vectors uniformly sampled from
the $\mathcal{H}$-space. Although not entirely wrong, encoding a real interval
this way fails to capture an important relationship between the points on the
interval. There is clearly a stronger relation between neighboring points
(e.g., $\xi_{1}$ and $\xi_{2}$) when compared to $\xi_{1}$ and $\xi_{m}$, due
to the different distance between these points. As indicated by our results
presented in Section 6, encoding strategies capable of capturing such
relationships (see also Section 5) lead to more powerful models. In the next
section we present the way this relationship between hypervectors has thus far
been achieved. In addition, we propose an improved method that we argue has
more representational power.

##  4\. Generating level-hypervectors

A method for representing real numbers with linearly correlated hypervectors
was first described by Rahimi et al. (Rahimi et al., 2016a) and Widdows and
Cohen (Widdows and Cohen, 2015). These sets are widely used in HDC and are
generally referred to as level-hypervectors. The generation of a level-
hypervector set $\mathbf{L}=\\{L_{1},\dots,L_{m}\\}$ starts by assigning a
uniform random vector to $L_{1}$. Each subsequent vector is obtained by
flipping $d/2/m$ bits. During the process, flipped bits are never unflipped.
Therefore, the vectors $L_{1}$ and $L_{m}$, representing the endpoints of the
interval, share exactly $d/2$ bits, making them precisely orthogonal. We argue
that if the precise distance constraint is relaxed, a set with greater
representation power can be created. We substantiate this claim in the next
section.

###  4.1. The importance of quasi-orthogonality

From an information theory perspective, the amount of information conveyed in
the outcome of a random trial is a function of the probability of that
outcome. More formally, for a given random variable with possible outcomes
$\varepsilon_{1},\dots,\varepsilon_{n}$, which occur with probability
$\mathbb{P}(\varepsilon_{1}),\dots,\mathbb{P}(\varepsilon_{n})$, the Shannon
information content $\mathscr{I}$ of an outcome $\varepsilon_{i}$ is defined
as (MacKay et al., 2003):

$\displaystyle\mathscr{I}(\varepsilon_{i})=\log_{2}\frac{1}{\mathbb{P}(\varepsilon_{i})}$

If we think of a random-hypervector set as a random sample, the probability of
each realization is extremely low. Thus the entropy, or information content,
is very high. This is one of the main theoretical foundations of HDC.

Note that random-hypervectors are independently and uniformly sampled,
resulting in quasi-orthogonal vectors. These vectors are simple to create, but
more importantly, they have greater representational power than precisely-
orthogonal vectors. In mathematical terms, while the number of orthogonal
vectors in $\mathcal{H}$ is $d$, the number of quasi-orthogonal vectors is
almost $2^{d}$ (Kanerva, 1988). Given that each set is sampled uniformly, a
much larger sample space implies a much lower probability of occurrence per
outcome. By the definition above, this results in greater information content.

###  4.2. Level-hypervectors revisited: applying the notion of “quasi”

The existing method for generating a level-hypervector set does not
incorporate an important property of the random-hypervector set. As we
discussed in the previous section, the key to the representational power of
random-hypervectors—and more generally of HDC—comes from the relaxed notion of
distance: quasi-orthogonality. In contrast, the level-hypervectors created
with the existing method, as described above, have a fixed distance between
each pair of hypervectors. This limits the number of possible outcomes of
their generation which, in view of what has been discussed, is equivalent to
constraining the representation power of the basis-hypervector set. Instead,
we want the distance between two hypervectors $L_{i}$ and $L_{j}$ in
$\mathbf{L}$, with $i<j$, to be proportional to $j-i$ in expectation. If we
denote by $\Delta^{i,j}$ the desired value for
$\mathbb{E}\left[\delta(L_{i},L_{j})\right]$, then:

$\displaystyle\Delta^{i,j}=\frac{j-i}{2(m-1)}$

An intuitive idea, that we describe to clarify the problem, is to allow
multiple flips per position and perform a number of flips $\digamma^{i,j}$
that results in an expected distance $\Delta^{i,j}$. One could use a Markov
Chain as illustrated in Figure 4 to model the bit flipping process. Each state
$S(t)$ represents a distance $\delta$ from $L_{i}$. The process always starts
from $S(0)=0$. At each following step one bit is flipped at a random position,
moving either one bit away from $L_{i}$ (represented by solid arrows) or go
back one bit (dashed arrows). The probability of moving away from $L_{i}$ in
$S(t)$ is:

$\displaystyle\mathbb{P}\left[S(t+1)=S(t)+1\right]=\frac{d-S(t)}{d}$

Observe that $\digamma^{i,j}$ is the expected number of steps taken until
absorption in the $\Delta^{i,j}$ state.

$0$$1/d$$2/d$$\cdots$$\Delta^{i,j}-\frac{1}{d}$$\Delta^{i,j}$ Figure 4. Markov
Chain of a bit flipping process

Let $u(k)$ denote the expected absorption time starting from state $k$. By
considering each starting state and conditioning on each possible outcome, we
get the following linear recurrence relation:

$\displaystyle u(k)=\begin{cases}1+u(1)&\;\text{ if }\;k=0\\\
1+\frac{(d-k)u(k+1)+ku(k-1)}{d}&\;\text{ if }\;0<k<\Delta^{i,j}\\\ 0&\;\text{
if }\;k=\Delta^{i,j}\end{cases}$

For a given dimension $d$, this is a solvable tridiagonal linear system
(Stone, 1973). The number of bits $\digamma^{i,j}$ we need to invert to obtain
$L_{j}$ from $L_{i}$, such that
$\mathbb{E}\left[\delta(L_{i},L_{j})\right]=\Delta^{i,j}$ is exactly $u(0)$,
obtained from solving the system. This method generates what are called
scatter codes (Smith and Stanford, 1990) which map the input space nonlinearly
to the similarities in $\mathcal{H}$-space. In the next section we propose a
practical algorithm, simple to implement and use in HDC applications with a
linear mapping.

###  4.3. A new method for generating level-hypervectors

Presented below, Algorithm 1 starts by assigning two uniformly random
hypervectors to $L_{1}$ and $L_{m}$, in addition to a $d$-dimensional vector
$\Phi$ whose elements are sampled uniformly from [0,1]. Then, for each
remaining level $L_{l}$ an interpolation threshold value $\tau_{l}$ is set and
$\Phi$ acts as a filter to determine the origin of each bit, either from
$L_{1}$ or $L_{m}$. This differs from the method by Rachkovskiy et al. (2005),
which deterministically concatenates fractions of $L_{1}$ and $L_{m}$.
Proposition 4.1 establishes that the obtained set of level-hypervectors meets
the previously motivated property, that is, for any $j>i$, the expected
distance between any $L_{i}$ and $L_{j}$, is $\Delta^{i,j}$.

1

Input : Two integers $m$ and $d$.

Output : A set of $m$ $d$-dimensional level-hypervectors
$\mathbf{L}=\\{L_{1},\ldots,L_{m}\\}$

2 $L_{1}\leftarrow$ uniform_sample($\\{0,1\\}^{d}$)

3 $L_{m}\leftarrow$ uniform_sample($\\{0,1\\}^{d}$)

4 $\Phi\leftarrow$ uniform_sample($[0,1]^{d}$)

5

6for  _each remaining level $l\in\\{2,\ldots,m-1\\}$_ do

7 $\tau_{l}\leftarrow\frac{m-l}{m-1}$

8 for  _each dimension $\partial\in\\{1,\dots,d\\}$_ do

9 if  _$\Phi^{(\partial)} <\tau_{l}$_ then

10 $L_{l}^{(\partial)}\leftarrow L_{1}^{(\partial)}$

11 else

12 $L_{l}^{(\partial)}\leftarrow L_{m}^{(\partial)}$

return $\\{L_{1},\ldots,L_{m}\\}$

Algorithm 1 Creation of a level-hypervector set using interpolation filters.

###### Proposition 4.1.

Let $\mathbf{L}=\\{L_{1},\dots\,L_{m}\\}$ denote a set of hypervectors
generated by Algorithm 1. For all $i$ and $j>i$ in $\\{1,\dots,m\\}$, we have
$\mathbb{E}\left[\delta(L_{i},L_{j})\right]=\Delta^{i,j}$.

###### Proof.

First, from the definition of the normalized Hamming distance, we have:

$\displaystyle\delta\left(L_{i},L_{j}\right)=\frac{1}{d}\sum_{\partial=1}^{d}\mathbbm{1}\left(L_{i}^{\partial}\neq
L_{j}^{\partial}\right)$

where $\mathbbm{1}$ is the indicator function. By applying the linearity of
expectation property, the i.i.d. property for all dimensions of $L_{i}$, and
considering that the expectation of an indicator function equals the
probability of the event, we get:

(1)
$\displaystyle\mathbb{E}\left[\delta(L_{i},L_{j})\right]=\mathbb{P}\left(L_{i}^{\bar{\partial}}\neq
L_{j}^{\bar{\partial}}\right)$

where $\bar{\partial}\in\\{1,\dots,d\\}$ indicates that the probability is
dimension independent. Then, from Algorithm 1 we have:

$\displaystyle\mathbb{P}(L_{i}^{\bar{\partial}}=L_{j}^{\bar{\partial}})=\mathbb{P}(\Phi^{\bar{\partial}}<\tau_{i})\left(\genfrac{}{}{0.0pt}{}{\mathbb{P}(\Phi^{\bar{\partial}}<\tau_{j}|\Phi^{\bar{\partial}}<\tau_{i})\mathbb{P}(L_{1}^{\bar{\partial}}=L_{1}^{\bar{\partial}})}{+\mathbb{P}(\Phi^{\bar{\partial}}\geq\tau_{j}|\Phi^{\bar{\partial}}<\tau_{i})\mathbb{P}(L_{1}^{\bar{\partial}}=L_{m}^{\bar{\partial}})}\right)$
$\displaystyle+\mathbb{P}(\Phi^{\bar{\partial}}\geq\tau_{i})\left(\genfrac{}{}{0.0pt}{}{\mathbb{P}(\Phi^{\bar{\partial}}\geq\tau_{j}|\Phi^{\bar{\partial}}\geq\tau_{i})\mathbb{P}(L_{1}^{\bar{\partial}}=L_{1}^{\bar{\partial}})}{+\mathbb{P}(\Phi^{\bar{\partial}}<\tau_{j}|\Phi^{\bar{\partial}}\geq\tau_{i})\mathbb{P}(L_{1}^{\bar{\partial}}=L_{m}^{\bar{\partial}})}\right)$

Given that $\Phi^{\bar{\partial}}$ is uniform in $[0,1]$ and
$\tau_{i}=\frac{m-i}{m-1}$ according to the algorithm, we can calculate this
probability to be:

(2)
$\displaystyle\mathbb{P}\left(L_{i}^{\bar{\partial}}=L_{j}^{\bar{\partial}}\right)=1-\frac{j-i}{2(m-1)}$

Considering that the event is binary, from Equations 1 and 2, we get:
$\mathbb{E}\left[\delta\left(L_{i},L_{j}\right)\right]=\Delta^{i,j}$. ∎

##  5\. Encoding Circular Data

As described above, symbols and real numbers can be represented in the
hyperspace with random and level-hypervector basis sets, respectively.
However, not every type of data falls into these two categories. Consider, for
instance, angular data in $\Theta=[0,2\pi]$. The distance $\rho\in[0,1]$
between two angles $\alpha$ and $\beta$ in $\Theta$ is defined as (Lund,
1999):

$\displaystyle\rho(\alpha,\beta)=\frac{1}{2}\left(1-\cos(\alpha-\beta)\right)$

If we use level-hypervectors to encode the $\Theta$-interval, the distances
between the hypervectors would not be proportional to the distance between the
angles. Notice that the endpoints of an interval represented with level-
hypervectors are completely dissimilar, while a circle has no endpoints.

Angles are widely used to represent information in meteorology (Holzmann et
al., 2006), ecology (Tracey et al., 2005; Kempter et al., 2012), medicine (Gao
et al., 2006, 2014; Ahmidi et al., 2017), astronomy (Cabella and Marinucci,
2009; Marinucci and Peccati, 2011) and engineering (Chirikjian, 2000).
Moreover, many natural and social phenomena have circular-linear correlation
on some time scale. Consider for example the seasonal temperature variations
over a year or the behavior of fish with respect to the tides in a day. In
these cases, it makes sense to represent the time intervals (e.g., Jan 1st -
Dec 31st) as cyclic intervals (Lund, 1999; Kempter et al., 2012).

Given the multitude of applications using circular data, unsurprisingly there
has been great scientific effort to adapt statistical and learning
methodologies to handle it appropriately (Lee, 2010). This gave rise to a
branch of statistical methodology known as directional statistics (Mardia et
al., 2000; Pewsey and García-Portugués, 2021). Despite all this effort, to the
best of our knowledge, our work is the first to address the adaptation in the
context of HDC learning.

###  5.1. Circular-hypervectors

An algorithm for creating a set of hypervectors whose distances are
proportional to that of a set of equidistant points on a circle has recently
been proposed by Heddes et al. (Heddes et al., 2022). They used the set,
called circular-hypervectors, to create a dynamic hashing system, where the
circular structure helps with evenly distributing requests across a changing
population of servers (Karger et al., 1997). We propose to adapt and
generalize their algorithm to create a basis set of hypervectors suitable for
learning from circular data using HDC.

We want to build a set of hypervectors
$\mathbf{C}=\\{C_{1},\dots,C_{m}\\}$111We assume $m$ to be even to simplify
discussions. Sets of odd cardinality can be generated as subsets
$\\{C_{1},C_{3},C_{5},\dots,C_{2m-1}\\}$ of a set of size $2m$. such that for
all $C_{i}$ and $C_{j}$ in $\mathbf{C}$ their distance $\delta$ in
$\mathcal{H}$ is proportional to the distance between the angles they
represent:

$\displaystyle\mathbb{E}\left[\delta(C_{i},C_{j})\right]=\frac{1}{2}\,\rho\left((i-1)\frac{2\pi}{m},(j-1)\frac{2\pi}{m}\right)$

This relationship is in terms of expected value to improve the information
content as discussed in Section 4.

Phase 1Phase
2$C_{1}$$C_{2}$$\cdots$$C_{m/2+1}$$T_{1}$$T_{2}$$T_{m/2}$$C_{m/2+2}$$C_{m/2+3}$$\cdots$$C_{m}$$T_{1}$$T_{2}$$T_{3}$$T_{m/2-1}$$T_{m/2}$
Figure 5.  Diagram of the creation of circular-hypervectors. Phase 1 shows the
level-hypervectors and the transformations between them. Phase 2 shows the use
of transformations for the second half of the circle. The dashed
transformation is shown to complete the circle but is not needed since $C_{1}$
is already known.

The creation of circular-hypervectors, shown in Figure 5, is divided into two
phases, one for each half of the circle. The first half is simply a set of
$m/2+1$ level-hypervectors:

$\displaystyle C_{i}=L_{i}\text{ for }i\in\left\\{1,\dots,m/2+1\right\\}$

where $C_{1}$ and $C_{m/2+1}$ are quasi-orthogonal, ensuring that the opposite
side of the circle is completely dissimilar. The second half is created by
applying the transitions between the levels of the first half, in order, to
the last circular-hypervector:

(3) $\displaystyle C_{i}=C_{i-1}\otimes T_{i-m/2-1},\text{ for
}i\in\left\\{m/2+2,\dots,m\right\\}$

where the transition $T_{i}=C_{i}\otimes C_{i+1}$ are the flipped bits between
levels $i$ and $i+1$. The combined transitions $\\{T_{1},\dots,T_{m/2}\\}$ are
equal to the transition from $C_{1}$ to $C_{m/2+1}$ such that:

$\displaystyle C_{m/2+1}=C_{1}\otimes\bigotimes_{i=1}^{m/2}T_{i}$

Since binding is its own inverse, the transitions bound to $C_{i-1}$ in
Equation 3 make the new hypervector $C_{i}$ closer to $C_{1}$. Moreover, the
transitions $\\{T_{1},\dots,T_{m/2}\\}$ occur in any half of the circle,
ensuring that the hypervector at the opposite side from any point is always
quasi-orthogonal to it.

###  5.2. Controlling the trade-off between correlation preservation and
information content

The discussion in Section 4.1 illustrated the benefit of relaxing the distance
between generated hypervectors, resulting in greater information content.
Another concern is that, while level and circular-hypervectors have the
ability to translate important correlations into hyperspace, from the
perspective of information content this diminishes their representational
power: by forcing the vectors to be correlated, the probability distribution
over the possible outcomes becomes more concentrated, decreasing the entropy.
We argue that more powerful models can be created if this constraint, i.e.,
the correlation, is relaxed as well.

The random-hypervectors are the most capable at representation as they are
sampled uniformly, without any restriction. However, for this very reason they
are unable to map existing correlations in the input space to the hyperspace.
The level and circular sets preserve correlation but are restricted in
information content. The ideal basis set is then expected to have a balance
between its ability to preserve correlation and its information content.

To address this trade-off, we introduce a hyperparameter $r\in[0,1]$ that
interpolates between a level or circular-hypervector set, and the random set.
As can be seen in Figure 6, the $r$-hyperparameter changes the amount of
correlation between neighboring nodes. Intermediate values of $r$ thus enable
higher information content while locally the relative correlation is
preserved.

$r=0$Circular$r=0.5$$r=1$Random0.51.0 Figure 6.  Effect of the
$r$-hyperparameter on the similarities between each node and the bottom
reference node in a circular set of 10 hypervectors.

To interpolate we concatenate multiple level-hypervector sets created with
Algorithm 1. The last hypervector of one set becomes the first hypervector of
the next set. The number of transitions $n$ per level-hypervector set is given
by:

$\displaystyle n=r+(1-r)(m-1)$

where $m$ is the total number of hypervectors in the concatenated set. Each
level in the concatenated set is obtained by using the threshold value:

$\displaystyle\tau_{l}=1-\frac{(l-1)\;\mathrm{mod}\;n}{n}$

When $r=1$, each level set contains only two hypervectors, (i.e., one
transition) resulting in a set identical to a random-hypervector set. For
circular-hypervectors the change only applies to phase 1 (see Section 5.1).

##  6\. Experiments

We evaluate circular-hypervectors in classification and regression settings
where they are compared to random and level-hypervectors. The
$r$-hyperparameter is evaluated by observing its effect on the same two
settings.

###  6.1. Classification

To evaluate the performance of circular-hypervectors in a classification
setting, we use the JHU-ISI Gesture and Skill Assessment Working Set (JIGSAWS)
dataset (Gao et al., 2014; Ahmidi et al., 2017). The dataset contains videos
accompanied by 76-dimensional kinematic data of three different surgical
tasks, performed by eight different surgeons, operating the da Vinci robot. As
our goal is to show whether circular-hypervectors are more appropriate for
dealing with circular data, we use a subset of the dataset containing circular
data. Specifically, we use the 18 kinematic variables that represent the
rotation matrices of the left master tool manipulator and patient-side
manipulator.

Each sample has a label which indicates the surgical activity called
“gestures.” There are 15 gestures, each representing intentional surgical
actions such as “orienting needle,” “pushing needle through tissue” and
“transferring needle from left to right.” The task is to classify which
gesture is being performed. For this, we used the standard classification
framework presented in Section 2.2.

A sample is encoded as $\textstyle\bigoplus_{i=1}^{18}K_{i}\otimes V_{i}$
where the key $K_{i}$ is a random-hypervector that represents the index $i$,
and the value $V_{i}$ is encoded as a random, level or circular-hypervector,
depending on the experiment. For each of the three surgical tasks, Knot Tying,
Needle Passing and Suturing, a model was trained on the data from surgeon ”D”,
one of the most experienced in the experiment.

Table 1. Classification accuracy results. The circular hypervectors have $r=0.1$. Dataset | Random | Level | Circular
---|---|---|---
Knot Tying | 76.6% | 75.9% | 84.0%
Needle Passing | 76.0% | 76.0% | 83.6%
Suturing | 73.0% | 60.4% | 78.7%

The results comparing the classification accuracy of each basis-hypervector
set for each surgical task are shown in Table 1. The circular-hypervectors
perform an average of 7.2% better than random-hypervectors, which in-turn
slightly outperform level-hypervectors. The training and evaluation running
time are nearly equivalent among all basis sets because the one-time
differentiating cost of generating the basis set is negligible compared to the
training time.

###  6.2. Regression

In addition to classification, we evaluate the performance of circular-
hypervectors on two regression tasks. The first contains temperature data
measured in Beijing, from March 2013 till February 2017 at the Aotizhongxin
station (Zhang et al., 2017), available on the UCI Machine Learning Repository
(Dua and Graff, 2017). We hypothesize that the circular-hypervectors are more
appropriate for representing the day of the year and the hour of the day in
this setting because they are both proxies of angular values: the angle of the
earth in its orbit around the sun and the earth around its axis, respectively.
Since both of these values are highly correlated with the outside temperature,
we expect an HDC model that preserves the angular correlation to be better at
forecasting the temperature.

Each model was trained on the first 70% of the data using the regression
framework described in Section 2.3. The samples are encoded as $Y\otimes
D\otimes H$ with the year $Y$, day $D$, and hour $H$ hypervectors. The year
hypervector is a level-hypervector, enabling the model to capture macro trends
in temperature, such as global warming. The day and hour hypervectors change
between random, level, and circular depending on the experiment. The label is
the temperature at a given time, encoded as a level-hypervector. After the
models are trained, one for each type of basis-hypervector, their performance
is measured by calculating the mean squared error on predictions of the last
30% of the dataset.

The second dataset contains power level measurements from the Mars Express
satellite, provided by the European Space Agency (Dressler, 2019). The power
level of the satellite fluctuates based on its orbit and the on-board energy
consumption (Lucas and Boumghar, 2017). A more accurate model for available
power means that the safety margins can be reduced, therefore allowing more
energy to be dedicated towards scientific operations.

A training sample consists of the elapsed fraction of Mars’ orbit around the
sun, called the mean anomaly. The encoding of the mean anomaly changes based
on the experiment between random, level, and circular-hypervectors. The label
is the power level at a given time, encoded as a level-hypervector. The data
is randomly split between 70% training and 30% testing. The performance of
each basis set is determined on the test split using the mean squared error
metric.

Figure 7.  Regression normalized mean squared error results for each basis
hypervector type. Normalized against the performance of random hypervectors.
The circular hypervectors have $r=0.01$.

The results for both regression tasks are presented in Table 2. Circular-
hypervectors reduce the error by 67.7% and 84.4% on average compared to level-
hypervectors and random-hypervectors, respectively. These results, in
combination with those for classification, illustrate how domain knowledge
about the circular nature of the data can account for a significant
improvement in performance. The efficiency of HDC ensures that most embedded
systems can afford HDC models within their computation budget. This makes
circular-hypervectors ideally suited for embedded and IoT application that are
rich in circular data, such as robotics, where actuators and joints generate
much angular data.

Table 2. Regression mean squared error results. The circular hypervectors have $r=0.01$. Dataset | Random | Level | Circular
---|---|---|---
Beijing | 441.1 | 126.8 | 21.9
Mars Express | 1294.1 | 715.6 | 339.1

###  6.3. R-value

We evaluate the $r$-hyperparameter by observing the performance of the
classification and regression tasks described above as we vary the $r$-value
between 0 and 1, interpolating between circular and random-hypervectors. In
order to aggregate the effects in one plot we use the normalized mean squared
error metric for the regression tasks and the normalized accuracy error,
defined as $\frac{1-\alpha}{1-\bar{\alpha}}$ where $\alpha$ is the accuracy
and $\bar{\alpha}$ the reference accuracy. The reference for all tasks is set
to the performance of random-hypervectors, equivalent to the endpoint of the
interpolation.

Figure 8.  Error of the circular-hypervector basis set with varying
$r$-hyperparameter, normalized against the random-hypervector set performance
per dataset.

The normalized error plot shown in Figure 8 indicates that better performance
can be achieved when $r>0$, as is inline with the theoretical analysis
presented in Section 4.1. After improving initially, as $r$ gets closer to 1,
the performance approaches that of the random-hypervectors. These results
indicate the importance of considering the information content of a basis-
hypervector set as we propose in our work. In addition, it shows the value of
the proposed $r$-parameter to control the trade-off between representation
power and the ability to preserve correlations in the hyperspace mapping.

##  7\. Conclusion

We study basis-hypervectors: stochastically created vectors used to represent
atomic information in HDC. Taking inspiration from information theory, we
propose a methodology to create level-hypervectors with greater
representational power. Furthermore, we introduce a method to handle circular
data in HDC. This method, which uses the improved level-hypervectors, is the
first approach to learning from circular data in HDC. We believe that these
contributions have the potential to benefit HDC in general, as they improve
the accuracy of models based on circular and real data, present in most
learning applications.

## References

  * (1)
  * Ahmidi et al. (2017) Narges Ahmidi, Lingling Tao, et al. 2017\.  A dataset and benchmarks for segmentation and recognition of gestures in robotic surgery.  _Transactions on Biomedical Engineering_ 64, 9 (2017), 2025–2041.
  * Branco et al. (2019) Sérgio Branco, André G Ferreira, and Jorge Cabral. 2019.  Machine learning in resource-scarce embedded systems, FPGAs, and end-devices: A survey.  _Electronics_ 8, 11 (2019), 1289.
  * Cabella and Marinucci (2009) Paolo Cabella and Domenico Marinucci. 2009.  Statistical challenges in the analysis of cosmic microwave background radiation.  _The Annals of Applied Statistics_ 3, 1 (2009), 61–95.
  * Chirikjian (2000) Gregory S Chirikjian. 2000\.  _Engineering applications of noncommutative harmonic analysis: with emphasis on rotation and motion groups_.  CRC press.
  * Crick et al. (1989) Francis Crick et al. 1989\.  The recent excitement about neural networks.  _Nature_ 337, 6203 (1989), 129–132.
  * Denève et al. (2017) Sophie Denève, Alireza Alemi, and Ralph Bourdoukan. 2017\.  The brain as an efficient and robust adaptive learner.  _Neuron_ 94, 5 (2017), 969–977.
  * Dressler (2019) Thomas Dressler. 2019\.  THP 2.0 - Thermal Power Model Redesigned.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Fisher (1995) Nicholas I Fisher. 1995\.  _Statistical analysis of circular data_.  Cambridge University Press.
  * Gao et al. (2006) Fei Gao, Kee-Seng Chia, Ingela Krantz, Per Nordin, and David Machin. 2006.  On the application of the von Mises distribution and angular regression methods to investigate the seasonality of disease onset.  _Statistics in Medicine_ 25, 9 (2006), 1593–1618.
  * Gao et al. (2014) Yixin Gao et al. 2014\.  Jhu-isi gesture and skill assessment working set (JIGSAWS): A surgical activity dataset for human motion modeling. In _MICCAI workshop: M2cai_ , Vol. 3. 3\.
  * Ge and Parhi (2020) Lulu Ge and Keshab K Parhi. 2020.  Classification using hyperdimensional computing: A review.  _Circuits and Systems Magazine_ 20, 2 (2020), 30–47.
  * Heddes et al. (2022) Mike Heddes, Igor Nunes, Tony Givargis, Alexandru Nicolau, and Alex Veidenbaum. 2022.  Hyperdimensional Hashing: A Robust and Efficient Dynamic Hash Table. In _Design Automation Conference (DAC)_.
  * Hersche et al. (2020) Michael Hersche, Edoardo Mello Rella, Alfio Di Mauro, Luca Benini, and Abbas Rahimi. 2020\.  Integrating event-based dynamic vision sensors with sparse hyperdimensional computing: a low-power accelerator with online learning capability. In _International Symposium on Low Power Electronics and Design (ISLPED)_. 169–174.
  * Holzmann et al. (2006) Hajo Holzmann, Axel Munk, Max Suster, and Walter Zucchini. 2006\.  Hidden Markov models for circular and linear-circular time series.  _Environmental and Ecological Statistics_ 13, 3 (2006), 325–347.
  * James et al. (2017) Conrad D James, James B Aimone, Nadine E Miner, Craig M Vineyard, Fredrick H Rothganger, Kristofor D Carlson, Samuel A Mulder, Timothy J Draelos, Aleksandra Faust, Matthew J Marinella, et al. 2017\.  A historical survey of algorithms and hardware architectures for neural-inspired and neuromorphic computing applications.  _Biologically Inspired Cognitive Architectures_ 19 (2017), 49–64.
  * Kaelbling (1993) Leslie Pack Kaelbling. 1993\.  _Learning in embedded systems_.  MIT press.
  * Kanerva (1988) Pentti Kanerva. 1988\.  _Sparse distributed memory_.  MIT press.
  * Kanerva (2009) Pentti Kanerva. 2009\.  Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors.  _Cognitive computation_ 1, 2 (2009), 139–159.
  * Karger et al. (1997) David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and Daniel Lewin. 1997\.  Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the world wide web. In _Symposium on Theory of computing (STOC)_. 654–663.
  * Kempter et al. (2012) Richard Kempter, Christian Leibold, et al. 2012\.  Quantifying circular–linear associations: Hippocampal phase precession.  _Journal of Neuroscience Methods_ 207, 1 (2012), 113–124.
  * LeCun et al. (2015) Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015\.  Deep learning.  _Nature_ 521, 7553 (2015), 436–444.
  * Lee (2010) Alan Lee. 2010.  Circular data.  _Wiley Interdisciplinary Reviews: Computational Statistics_ 2, 4 (2010), 477–486.
  * Lucas and Boumghar (2017) Luke Lucas and Redouane Boumghar. 2017.  Machine learning for spacecraft operations support-The Mars Express power challenge. In _International Conference on Space Mission Challenges for Information Technology (SMC-IT)_. IEEE, 82–87.
  * Lund (1999) Ulric Lund. 1999\.  Least circular distance regression for directional data.  _Journal of Applied Statistics_ 26, 6 (1999), 723–733.
  * MacKay et al. (2003) David JC MacKay, David JC Mac Kay, et al. 2003\.  _Information theory, inference and learning algorithms_.  Cambridge University Press.
  * Manabat et al. (2019) Alec Xavier Manabat, Celine Rose Marcelo, et al. 2019\.  Performance analysis of hyperdimensional computing for character recognition. In _International Symposium on Multimedia and Communication Technology (ISMAC)_. IEEE, 1–5.
  * Marblestone et al. (2016) Adam H Marblestone, Greg Wayne, and Konrad P Kording. 2016\.  Toward an integration of deep learning and neuroscience.  _Frontiers in Computational Neuroscience_ (2016), 94.
  * Mardia et al. (2000) Kanti V Mardia, Peter E Jupp, and KV Mardia. 2000.  _Directional statistics_. Vol. 2.  Wiley Online Library.
  * Marinucci and Peccati (2011) Domenico Marinucci and Giovanni Peccati. 2011.  _Random fields on the sphere: representation, limit theorems and cosmological applications_. Vol. 389.  Cambridge University Press.
  * Nunes et al. (2022) Igor Nunes, Mike Heddes, Tony Givargis, Alexandru Nicolau, and Alex Veidenbaum. 2022.  GraphHD: Efficient graph classification using hyperdimensional computing. In _Design, Automation Test in Europe Conference Exhibition (DATE)_.
  * Pewsey and García-Portugués (2021) Arthur Pewsey and Eduardo García-Portugués. 2021\.  Recent advances in directional statistics.  _Test_ 30, 1 (2021), 1–58.
  * Rachkovskiy et al. (2005) Dmitriy A Rachkovskiy, Sergey V Slipchenko, Ernst M Kussul, and Tatyana N Baidyk. 2005.  Sparse binary distributed encoding of scalars.  _Journal of Automation and Information Sciences_ 37, 6 (2005).
  * Rahimi et al. (2016a) Abbas Rahimi, Simone Benatti, Pentti Kanerva, Luca Benini, and Jan M Rabaey. 2016a.  Hyperdimensional biosignal processing: A case study for EMG-based hand gesture recognition. In _International Conference on Rebooting Computing (ICRC)_. IEEE, 1–8.
  * Rahimi et al. (2016b) Abbas Rahimi, Pentti Kanerva, and Jan M Rabaey. 2016b.  A robust and energy-efficient classifier using brain-inspired hyperdimensional computing. In _International Symposium on Low Power Electronics and Design (ISLPED)_. 64–69.
  * Schmidhuber (2015) Jürgen Schmidhuber. 2015\.  Deep learning in neural networks: An overview.  _Neural Networks_ 61 (2015), 85–117.
  * Smith and Stanford (1990) Derek Smith and Paul Stanford. 1990.  A random walk in Hamming space. In _1990 IJCNN International Joint Conference on Neural Networks_. IEEE, 465–470.
  * Stone (1973) Harold S Stone. 1973\.  An efficient parallel algorithm for the solution of a tridiagonal linear system of equations.  _Journal of the ACM (JACM)_ 20, 1 (1973), 27–38.
  * Thomas et al. (2021) Anthony Thomas, Sanjoy Dasgupta, and Tajana Rosing. 2021\.  Theoretical Foundations of Hyperdimensional Computing.  _Journal of Artificial Intelligence Research (JAIR)_ 72 (2021), 215–249.
  * Tracey et al. (2005) JA Tracey, J Zhu, and K Crooks. 2005.  A set of nonlinear regression models for animal movement in response to a single landscape feature.  _Journal of Agricultural, Biological and Environmental Statistics (JABES)_ 10, 1 (2005), 1–18.
  * Whittington and Bogacz (2019) James CR Whittington and Rafal Bogacz. 2019.  Theories of error back-propagation in the brain.  _Trends in Cognitive Sciences_ 23, 3 (2019), 235–250.
  * Widdows and Cohen (2015) Dominic Widdows and Trevor Cohen. 2015.  Reasoning with vectors: A continuous model for fast robust inference.  _Logic Journal of the IGPL_ 23, 2 (2015), 141–173.
  * Zhang et al. (2017) Shuyi Zhang, Bin Guo, Anlan Dong, Jing He, Ziping Xu, and Song Xi Chen. 2017\.  Cautionary tales on air-quality improvement in Beijing.  _Royal Society A: Mathematical, Physical and Engineering Sciences_ 473, 2205 (2017), 20170457.