# Multi-answer Constrained Optimal Querying: Maximum Information Gain Coding

Zhefan Li, Pingyi Fan∗,
This work was supported by the National Key R & D Program of China under Grant
2021YFA1000500(4).Z. Li and P. Fan are with the Department of Electronic
Engineering, Tsinghua University, Beijing 100084, China and Beijing National
Research Center for Information Science and Technology (BNRist), Beijing
100084, China (e-mail<EMAIL_ADDRESS>fpy@tsinghua.edu.cn).

###### Abstract

As the rapidly developments of artificial intelligence and machine Learning,
behavior tree design in multiagent system or AI game become more important.
The behavior tree design problem is highly related to the source coding in
information theory. “Twenty Questions” problem is a typical example for the
behavior tree design, usually used to explain the source coding application in
information theory and can be solved by Huffman coding. In some realistic
scenarios, there are some constraints on the asked questions. However, for
general question set, ﬁnding the minimum expected querying length is an open
problem, belongs to NP-hard. Recently, a new coding scheme has been proposed
to provide a near optimal solution for binary cases with some constraints,
named greedy binary separation coding (GBSC). In this work, we shall
generalize it to D-ary cases and propose maximum information gain coding
(MIGC) approach to solve the multi-answer decision constrained querying
problem. The optimality of the proposed MIGC is discussed in theory. Later on,
we also apply MIGC to discuss three practical scenarios and showcase that MIGC
has better performance than GBSC and Shannon Coding in terms of bits
persymbol.

###### Index Terms:

source coding, decision tree, greedy algorithm, information theory.

##  I Introduction

Constucting a decision tree for identification is a fundamental problem in
information theory and discrete mathematics [1]. As the rapidly developments
of artificial intelligence and machine Learning, behavior tree design in
multiagent system or AI game become more important. The behavior tree design
problem is highly related to the source coding in information theory. “Twenty
Questions” problem is a typical example for the behavior tree design, usually
used to explain the source coding application in information theory and can be
solved by Huffman coding. For the multiple agent systems, reinforcement
learning[2], Q-learning[3, 4], and federated learning [5, 6, 7] may be the
most important tools or frameworks to enhance the decision tree or behavior
tree design.

Let us review the well-known game “Twenty Questions”, where a player is
required to determine the identity of an item in a certain set by asking a
minimum number of “yes/no” questions [8]. It is equivalent to the binary
source coding in information theory. Its optimal solution can be given by
Huffman coding for the scenario without any constraint [9, 10].

In general, numerous variants of the game could be designed by adding
constraints. One example is to restrict the times of the question query [11,
12, 13], which can be solved by bounded-length Huffman coding. In the presence
of large sets or multiple sources, the limited memory becomes the key
constraint factor [14], which may cause conventional source coding methods can
not give a reasonable solution. In particular, if each question is endowed
with a cost, the problem can be turned from minimum length into minimum cost
[1].

In this paper, we focus on the decision constrained case, where the question
or decision set is limited. That is, one cannot divide the subtrees
arbitrarily when building the decision tree. Generally, finding the optimal
solution to it is an NP-hard problem[15]. Hence, it is common to utilize
greedy algorithms to find some near optimal solutions rather than the exact
solution [8]. In the literature, there exist heuristic algorithms that admit
$O($log$n)$-approximation [16, 17]. Furthermore, if the decision constraints
can be described by a graph, an approximation with $O($loglog$n)$ from the
optimal one was given[1]. Some algorithms based on active learning were also
presented in[18, 19] .

Recently, the authors in [8] proposed a Greedy Binary Separation Coding (GBSC)
algorithm to the problem based on information theory. However, it is only
suitable to the ”yes/no” binary cases. Inspired by that, we generalize it to
D-ary cases and propose a new algorithm MIGC referred to as Maximum
Information Gain Coding. More specifically, the contribution can be mainly
expressed as follows,

(i) We prove that for general distribution, the information quantity of the
query is the entropy of the ”answer”.

(ii) We propose a Maximum Information Gain Coding algorithm to solve multi-
answer decision constrained querying problem.

(iii) The optimality of MIGC is discussed in theory and some applications are
given.

The rest of this paper is organized as follows. In Section II, we give a brief
review of the GBSC algorithm. In Section III, we first build a generalized
model for the multi-answer constrained problem and present the algorithm,
Maximum Information Gain Coding (MIGC), to it. Then, we prove MIGC is better
than Shannon Coding in terms of the average bits per symbol. In Section IV,
three specific tasks are discussed to showcase the advantage of our proposed
MIGC algorithm. Finally, the conclusion is given in Section V.

##  II Related Works

###  II-A Binary Identification Problem

First, we consider the binary case. Given a ramdom variable
$X=\\{1,2,...,N\\}$ with distribution $P=\\{p_{1},p_{2},\dots,p_{N}\\}$, and a
set of questions $A=\\{S_{1},S_{2},...,S_{K}\\}$, our objective is to find the
minimum average query times by asking questions and present the selection of
the $X$ in the sequel. Here, it is assumed that $S_{i}$ is the subset of X,
and the query can be designed as ”Is $X$ in the set $S_{i}$ ?”, where
$S_{i}\in A$. If the query set is $2^{\emph{X}}$, then the optimal sulotion
can be given by Huffman coding. However, for some complex structures, Huffman
coding algorithm may not be workable. Let us see some examples.

######  Example 1.

Suppose $X\in\\{1,2,3,4\\}$, distribution of $X$ is $P=\\{0.1,0.4,0.2,0.3\\}$,
and the query set is $A=\\{\\{1,2\\},\\{2,3\\},\\{3,4\\}\\}$.

The solution of Example 1 is shown as Huffman decision tree mode in Fig.1.
From the Huffman decision tree, one can find that the query set should contain
$\\{1,3,4\\}$ and $\\{2\\}$, but the query set in Example 1 did not contain
them. That means the solution given by the Huffman decision tree is not valid
to the problem in Example 1.

Figure 1: Huffman decision tree of the Example 1

###  II-B Greedy Binary Separation Coding

To solve such a binary identification problem, recently, authors in [8]
proposed an approximation algorithm based on a coding sheme, referred to as
Greedy Binary Separation Coding (GBSC). The method constructs the decision
tree from top to bottom and at each node, it chooses the query making the
total probabilities of the left and right subtrees as close as possible. In
this way, one can build the decision tree of Example 1 as in Fig.2

Figure 2: GBSC decision tree of the example 1

The intuition of GBSC is to greedily maximize the information gain at each
node. It is proved that the mutual information between the target $X$ and the
query $Q$ is equal to the binary entropy of the answer to the query. This
indicates that it obeys the rule of the probability of answer ”yes” to be
close to $1/2$. However, in [8], it is only proved GBSC is valid when $X$ is
uniformly distributed. Now we will extend it and prove that for general
discrete distributions, GBSC is still valid by using the near equal
probability partition rule.

Note that GBSC is only suitable to the query problem in binary cases. Inspired
by maximizing the information gain of GBSC, we generalize it and propose the
Maximum Information Gain Coding (MIGC) method to multi-answer cases .

##  III Maximum Information Gain Coding

In this Section, we first introduce multi-answer constrained query problem and
then present a new solution referred to as Maximum Information Gain Coding.
Meanwhile we also analyze its optimality.

###  III-A Multi-answer Constrained Query Problem

Different from the constrained query problem in binary cases, the query now
has $D$ possible answers. Each answer can be uniquely mapped to one of $D$
disjoint subsets of $\mathcal{X}$. For simplicity, we first introduce some
definitions.

######  Definition 1.

The i-th query is mapped to $S_{i}=\\{U_{i1},U_{i2},\dots,U_{iD}\\}$, where
$U_{ij}\subseteq\mathcal{X}$, $U_{ij}\cap U_{iq}=\emptyset,1\leq j<q\leq D$
and $\emptyset$ represents the empty set.

That is, the i-th query can be described as ”Which subset $U_{ij}$ is $X$ in”,
where $U_{ij}\in S_{i}$.

We now formally desciribe MIGC.

######  Definition 2.

$S=\\{U_{1},U_{2},...,U_{D}\\}$ is a $D$-ary partition of $\mathcal{X}$, if
$\bigcup_{1\leq j\leq D}U_{j}=X$ and $U_{j}\cap U_{q}=\emptyset,\forall 1\leq
j<q\leq D$

######  Definition 3.

For a subset $U\subseteq X$, its total probability

$p(U)=\sum_{x_{i}\in U}p_{i}$ (1)

######  Definition 4.

The entropy of the partition $S=\\{U_{1},U_{2},...,U_{D}\\}$ is defined as

$H(S)=-\sum_{j=1}^{D}p(U_{j})logp(U_{j})$ (2)

######  Definition 5.

A partition $S^{*}$ of $\mathcal{X}$ is optimal, if for any partition $S$,
$H(S^{*})\geq H(S)$

Similar to GBSC, the rule from top to bottom is still adopted for constructing
the MIGC decision tree. The process can be described as follows. At the root,
we choose the query that makes the partition of $\mathcal{X}$ optimal as
defined in Definition 5, and split the tree according to the partition. We
repeat it recursively at each node, and choose the query corresponding to the
optimal partition. In this way, it is easily to know that GBSC is the special
case of MIGC for $D=2$.

######  Example 2.

Suppose $X\in\\{1,2,3,4,5\\}$, distribution of $X$ is
$P=\\{0.1,0.2,0.3,0.15,0.25\\}$, $D=3$ and the query set is unconstrained.

Based on the rule of MIGC, the corresponding decision tree of Example 2 is
shown in Fig.3. It gives clearly solution to the query problem in Example 2.

Figure 3: MIGC decision tree of the Example 2

###  III-B Intuition

In this subsection, we illustrate why the MIGC can approach maximum entropy at
each query. For a query $Q$ on the node
$X\in\mathcal{X}=\\{x_{1},x_{2},\dots,x_{N}\\}$, each $x_{i}$ gives a $D$-ary
answer. The probability of getting answer $j$ is given by

$P(Q=j)=p_{j}=\sum_{x_{i}\in\mathcal{X}\land\,x_{i}\,gives\,answer\,j}p(x_{i}),$
(3)

The information gain of query $Q$ with respect to node $X$ is

$\begin{split}I(X;Q)&=H(X)-H(X|Q)\\\
&=H(X)-\sum_{j=1}^{D}p_{j}H(X|Q=j)\end{split}$ (4)

######  Lemma 1.

$I(X;Q)=H(Q)$ (5)

In [8], it proved $I(X;Q)=H(Q)$ is true when $X$ is discrete uniformly
distributed. Now we will show that for any discrete distribution of $X$, Lemma
1 always holds.

###### Proof.

$\begin{split}I(X;Q)&=H(X)-\sum_{j=1}^{D}p_{j}H(X|Q=j)\\\
&=H(X)+\sum_{j=1}^{D}p_{j}\sum_{n=1}^{N}\frac{P(x_{i},Q=j)}{p_{j}}log\frac{P(x_{i},Q=j)}{p_{j}}\\\
&=H(X)+\sum_{j=1}^{D}\sum_{n=1}^{N}[P(x_{i},Q=j)logP(x_{i},Q=j)\\\
&\quad-P(x_{i},Q=j)logp_{j}]\end{split}$ (6)

Notice that

$\sum_{j=1}^{D}\sum_{n=1}^{N}P(x_{i},Q=j)logP(x_{i},Q=j)=-H(X)$ (7)
$\sum_{j=1}^{D}\sum_{n=1}^{N}-P(x_{i},Q=j)logp_{j}=-\sum_{j=1}^{D}p_{j}logp_{j}=H(Q)$
(8)

Then we have

$\displaystyle I(X;Q)=H(X)-H(X)+H(Q)=H(Q)$ (9)

∎

Lemma 1 indicates the information we gain from the query about $X$ is equal to
the entropy of the answer. In fact, the uniform distribution of the answer
maximizes the information gain, which means each answer should appear with the
same probability.

Since different answers divide the $\mathcal{X}$ into non-overlap partitions,
$H(Q)$ can also be seen as the partition entropy as defined in section IIIA.

###  III-C Near-optimality

In this subsection, we discuss the optimality of MIGC. For simplicity, we only
consider unconstrained condition. It is well known Huffman coding gives the
optimal solution to the unconstrained query problem. However, both GBSC and
MIGC may not reach the optimal solution for the unconstrained problem. That
means there exists a gap between Huffman coding approach and GBSC or MIGC in
terms of bits persymbol. In fact, GBSC for unconstrained query problem looks
like the Fano’s source coding, but the main difference from Fano’s source
coding is that Fano requires the order ranking of the answer probability from
the least to the largest. GBSC does not require such preprocessing. In [8], it
proves that GBSC is at least as good as Shannon coding[10] and better than
Fano’s approach in terms of the upper bound of the average coding length. It
is remarkable that the coding length for each symbol in GBSC is no more than
the corresponding coding length in Shannon coding. In the sequel, we will
prove it for MIGC.

######  Theorem 1.

Assume that the expected coding length is $L_{m}$ for MIGC, and $L_{s}$ for
Shannon coding, then $L_{m}\leq L_{s}$

######  Corollary 1.

Assume that the expected code length is $L_{m}$ for MIGC, then $L_{m}<H(X)+1$

Since $L_{s}<H(X)+1$, using Theorem 1, one can easily get the upper bound of
$L_{m}$ in Corollary 1.

Now we shall prove Theorem 1, and we first prove the Lemma 2.

######  Lemma 2.

Assume the code length for symbol with probability $p$ is $L_{D}$ for MIGC,
then $L_{D}\leq\lceil logp\rceil$

Note that this is a much stronger result in source coding theory. For the
binary case, it has been proven in [8] by contradiction. However, such method
cannot be directly generalized to D-ary cases. This is because each node in a
binary tree only has two children, which can be easy to discuss separately.
But for D-ary scenario, it is necessary to sort the children nodes at each
step. Now we give the detail of the proof as follows.

Figure 4: Illustration for the proof of Lemma 2.

###### Proof.

On the children nodes sorting process, it is illustrated in Fig.4, where a
circle represents a single node while a rectangle represents a leaf or a
subtree. The content in the nodes are indices of the nodes. $p_{n(i)}$ is the
sum of probabilities of all the children nodes of node $n(i)$.

Without lose of generality, we assume for any $n$ and $i<j$,
$p_{n(i)}<p_{n(j)}$.

Similar to [8], we will prove it by contradiction. Without lose of generality,
assume $p_{k+1(*)}\geq D^{-k}$ where $p_{k+1(*)}$ is the maximum among its
sister nodes. For $n\leq k$, $n(*)$ represents the nodes on the path from
$k+1(*)$ to the root.

Then we want to prove the following two propositions hold for any integer
$1\leq n\leq k$ by mathematical induction.

(i) $p_{n(D)}\geq D^{-n}$

(ii) $p_{n-1(*)}\geq D^{-(n-1)}+p_{k+1(1)}$

######  Remark 1.

if (i) and (ii) holds, then $p_{0(1)}\geq 1+p_{k+1(1)}>1$ , causing a
contradiction.

Basic step.

First, we prove the case when $k=n$. Since

$\begin{split}&p_{k(D)}\geq p_{k(*)}\\\ &p_{k(*)}\geq
p_{k+1(1)}+p_{k+1(*)},\end{split}$ (10)

then

$p_{k(D)}\geq p_{k+1(*)}\geq D^{-k},$ (11)

Proposition (i) is true.

If $p_{k(*)}-p_{k(1)}>p_{k+1(1)}$, then moving node $k+1(1)$ from $k(*)$ to
$k(1)$ will make $|p_{k(*)}-p_{k(1)}|$ smaller. According to the convex
property of entropy, this will increase the partition entropy of node
$k-1(*)$, which contradicts to the optimal partition defined in Definition 5.
Hence,

$p_{k(*)}-p_{k(1)}\leq p_{k+1(1)},$ (12)

so we have

$p_{k(1)}\geq p_{k(*)}-p_{k+1(1)}\geq p_{k+1(*)}\geq D^{-k}.$ (13)

And

$\begin{split}p_{k-1(*)}&=\sum_{i=1}^{D}p_{k(i)}\geq(D-1)p_{k(1)}+p_{k(*)}\\\
&\geq(D-1)D^{-k}+D^{-k}+p_{k+1(1)}\\\ &\geq D^{-(k-1)}+p_{k+1(1)}\end{split}$
(14)

Proposition (ii) is true.

Inductive step.

Assume the propositions are true for $n=m+1(1\leq m\leq k-1)$. Then

$p_{m(D)}\geq p_{m(*)}\geq D^{-m}+p_{k+1(1)}\geq D^{-m},$ (15)

Proposition (i) is true.

If $p_{m(*)}-p_{m(1)}>p_{k+1(1)}$, then moving node $k+1(1)$ from $m(*)$ to
$m(1)$ will make $|p_{m(*)}-p_{m(1)}|$ smaller. According to the convex
property of entropy, this will increase the partition entropy of node
$m-1(*)$, which contradicts to the optimal partition defined in Definition 5.
Hence,

$p_{m(*)}-p_{m(1)}\leq p_{k+1(1)},$ (16)

so we have

$p_{m(1)}\geq p_{m(*)}-p_{k+1(1)}\geq D^{-m}.$ (17)

And

$\begin{split}p_{m-1(*)}&=\sum_{i=1}^{D}p_{m(i)}\geq(D-1)p_{m(1)}+p_{m(*)}\\\
&\geq(D-1)D^{-m}+D^{-m}+p_{k+1(1)}\\\ &\geq D^{-(m-1)}+p_{k+1(1)}\end{split}$
(18)

Proposition (ii) is true. This demonstrates when $n=m$, the two propositions
also hold.

By using Remark 1 and the discussion above, Lemma 2 is proved.

∎

##  IV Some Practical Scenario Discussion

In this section, we use three practical scenarios to compare the performance
of MIGC and other coding algorithms.

###  IV-A Average Coding Length of General Discrete Distributed X for D=3
Without Constraints

Set $D=3$ and $N\in[3,12]$, and we generate $t=10000$ samples of discrete
distribution randomly for each $N$ where each sample represents a discrete
probability distribution. Fig.5(a) shows the average coding length of three
different algorithms changes with $N$. It is observed that when $N>5$, the
average coding length of MIGC is between the Huffman coding and Shannon
coding. Note that the Huffman coding is the optimal.

Figure 5: Performance of MIGC, Huffman coding and Shannon coding. (a) shows
how the expected code length change with $N$. (b)shows the gap of code length
between MIGC and Shannon coding when N=10. (c) shows the gap of code length
between Huffman coding and MIGC when N=10.

By setting $N=10$, Fig.5(b) shows the gap between the coding length of MIGC
and that of Shannon coding for each symbol, it is easily seen that all the
results are non-negative, which validates Lemma 2. Fig.5(c) shows the gap
between the coding length of Huffman coding and that of MIGC for each symbol.
Interestingly, although Huffman coding has less average coding length than
MIGC, MIGC has more symbols that have less coding length than that of Huffman
coding. And for a few symbols, their coding length of MIGC can be shorter than
that of Huffman coding by 3.

###  IV-B Application to DNA Detection

The identification of genes is important in molecular biology, and is usually
used to determine genomic sequences of different organisms[20]. An exon, which
is an interval of the DNA and does not overlap with each other. A gene is a
set of exons[21]. For simplicity, assume the target gene only contains one
exon. Here, different from [8], we set two target genes A and B for the
detection work. Each time, one can detect a continuous interval of the DNA,
and acquire four kinds of results, “detect A”, “detect B”, “detect A and B”,
“detect neither”. Due to the position of the target genes being fixed, the DNA
detection is to find the optimal detection querying with minimum expected
detection times. The procedure is shown in Fig.6.

Figure 6: DNA detection

DNA detection can be viewed as decision constrained coding problem. Set the
number of exons $N=6$ and generate $t=10000$ samples of discrete distributions
for testing. Fig.7 shows the gap between the MIGC and the optimal solution by
using brute force. In Fig.7(a), the red line represents the minimum average
detection times, while the blue dots represent the results provided by MIGC.
One can see that most blue dots are very close to the red line, which
illustrates the effectiveness of MIGC. Fig.7(b) shows the distribution of the
gap between MIGC and brute force. It demonstrates that the gap is less than
0.16 detection times with 95$\%$ probability while the optimal average
detection times is 2.16. Fig.8 compares the performance of MIGC and GBSC when
$N$ changes, illustrating that MIGC has less average detection times than
GBSC.

Figure 7: The DNA detection by using brute force and MIGC
Figure 8: The DNA detection by using GBSC and MIGC

###  IV-C Application to Battleship Games with 2 players

Battleship is a popular strategy game[22]. In conventional battleship game, it
requires two players to place ”ships” on 10 by 10 boards, which are hidden to
the opponent. The rules are expressed as follows, (i) the two players will
play in turn to choose a grid $(i,j)$ (ii) if all the grids of one ship have
been chosen by its owner’s opponent, then the ship is ”bombed” (iii) when one
player’s ships are all ”bombed”, the game ends and another player will win the
game.

Now we modify the battleship games as follows.

Assume two players only place their ships on the same 10 by 10 board randomly.
They do not participate in the following procedure of the game. A third player
tries to bomb the ships placed by the former two players. Each time, the third
player can get the result from $\\{$“hit player1’s ship”, “hit player2’s
ship”, “hit nothing”$\\}$. The target for the third player is to sink all the
ships with fewest tries (bombs).

(i) If we do not distinguish the owner of the ships as in [8], the problem
reduces to the binary case, i.e., the bombing result for the third player is
either ”hit” or not. This can be well handled by GBSC.

(ii) If we take the owner of the ships into account, it corresponds to the
multi-answer constrained cases ( each time, the third player can get the
result from $\\{$“hit player1’s ship”, “hit player2’s ship”, “hit
nothing”$\\}$). In this case, GBSC does not work and we ultilize MIGC instead.
The query set is the coordinates $\\{(i,j),1\leq i,j\leq 10\\}$ of the board.
For each try of the third player, one needs to maximize the entropy of the
hitting result.

Assume each of the former two players place a 1 by 5 and a 1 by 3 ships on the
board, i.e., there are total 4 ships. We generate $n=3^{12}$ possible board
layouts randomly, and the game starts by choosing one of them as target board
(every legal board is equally possible). Since each query (bombing) acquires
in average at most $log_{2}3$ bits of information, the theoritical minimal
number of average tries is no less than 12.

Fig.9 shows the distribution of the average try times of the third player.
Fig. 10 illustrates an example showcase of the game where color of each grid
represents the probability of whether there exist ships of player 1. As the
game progresses, the probability of the ships being bombed will become
gradually larger. From Fig.10(d), after trying bombs of $t=16$ times, one ship
of size 1 by 5 can be bombed definitely next time and the location of the
other ship of size 1 by 3 has been narrowed to four possibilities.

Figure 9: Distribution of the average try times for the battleship problem
Figure 10: The process of playing battleship

Fig. 11 shows how MIGC plays the game from the perspective of information
theory. Since every target board has the same probability of being chosen, we
can calculate the entropy of the board by $H(X_{t})=log_{3}|X_{t}|$, where
$X_{t}$ represents the set of boards meeting the hitting results after $t$
tries, and $|\cdot|$ represents counting the number of elements in the set. We
choose 10 boards randomly and show how the entropy or uncertainty of each
board changes with the number of tries. The red dashed line represents the
theoretical best result in average, which means each query (bombing) acquires
$log_{2}3$ bits of information. We can observe two types of the declination of
entropy silimlar to the results in [8]. Most of times, the first few tries
will not hit ships and the algorithm needs to explore the board, e.g., $t<5$
for board 6. At that stage, the declination of entropy is relatively slow.
When a ”hit” happens, the entropy drops rapidly until the information provided
by this ”hit” is fully ultilized. The process ends when the entropy reduces to
the zero.

Figure 11: How the uncertainty of the board changes with the number of tries.

The modified battleship problem for the third player illustrates that MIGC can
give an effective solution to the problem than that of GBSC.

##  V Conclusion

In this paper, we discussed an open problem in information theory, the multi-
answer constrained optimal query problem and proposed an Maximum Information
Gain Coding, MIGC, solution to it. We also discussed its optimality of MIGC in
theory. It is proved that MIGC has better performance than that of Shannon
coding in terms of the average coding length. Furthermore, an interesting
result is obtained that the coding length persymbol in MIGC is less than that
by Shannon coding for $D\geq 3$. Finally, we discuss three different scenarios
and show that MIGC provides better results than GBSC and Shannon coding. It is
expected the MIGC method can be combined with or embedded in some machine
learning frameworks, i.e., federated learning mode in [23, 24] and got more
applications in the future.

## Acknowledgment

The authors would like to appreciate the support of the National Key R & D
Program of China No. 2021YFA1000504. The authors thank the members of Wistlab
of Tsinghua University for their good suggestions and discussions.

## References

  * [1] A. Karbasi and M. Zadimoghaddam, “Constrained binary identification problem,” in _Proceedings of the 30th Symposium on Theoretical Aspects of Computer Science_ , 2013.
  * [2] Y. Fu, L. Qin, and Q. Yin, “A reinforcement learning behavior tree framework for game ai,” in _2016 International Conference on Economics, Social Science, Arts, Education and Management Engineering_. Atlantis Press, 2016, pp. 573–579.
  * [3] Q. Zhang, L. Sun, P. Jiao, and Q. Yin, “Combining behavior trees with maxq learning to facilitate cgfs behavior modeling,” in _2017 4th International Conference on Systems and Informatics (ICSAI)_. IEEE, 2017, pp. 525–531.
  * [4] S. S. O. Venkata, R. Parasuraman, and R. Pidaparti, “Kt-bt: A framework for knowledge transfer through behavior trees in multirobot systems,” _IEEE Transactions on Robotics_ , 2023.
  * [5] Y. Shi, P. Fan, Z. Zhu, C. Peng, F. Wang, and K. B. Letaief, “Sam: An efficient approach with selective aggregation of models in federated learning,” _IEEE Internet of Things Journal_ , 2024.
  * [6] S. Wan, J. Lu, P. Fan, Y. Shao, C. Peng, and K. B. Letaief, “Convergence analysis and system design for federated learning over wireless networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 12, pp. 3622–3639, 2021.
  * [7] Z. Zhu, S. Wan, P. Fan, and K. B. Letaief, “Federated multiagent actor–critic learning for age sensitive mobile-edge computing,” _IEEE Internet of Things Journal_ , vol. 9, no. 2, pp. 1053–1067, 2021.
  * [8] S. Zhang, J. Sun, and S. Chen, “Constrained optimal querying: Huffman coding and beyond,” _arXiv preprint arXiv:2210.04013_ , 2022.
  * [9] Mamta and Sharma, “Compression using huffman coding,” _International Journal of Computer Science and Network Security Ijcsns_ , 2010.
  * [10] T. M. Cover, _Elements of information theory_. John Wiley & Sons, 1999.
  * [11] M. B. Baer, “Twenty (or so) questions: bounded-length huffman coding,” _IEEE_ , 2006.
  * [12] L. L. Larmore and D. S. Hirschberg, “A fast algorithm for optimal length-limited huffman codes,” _Journal of the ACM (JACM)_ , vol. 37, no. 3, pp. 464–473, 1990.
  * [13] M. B. Baer, “D-ary bounded-length huffman coding,” in _2007 IEEE International Symposium on Information Theory_. IEEE, 2007, pp. 896–900.
  * [14] S. J. Lee and C. W. Lee, “Determination of huffman parameters for memory-constrained entropy coding of multiple sources,” _IEEE Signal Processing Letters_ , vol. 4, no. 3, pp. 65–67, 1997.
  * [15] H. Laurent and R. L. Rivest, “Constructing optimal binary decision trees is np-complete,” _Information processing letters_ , vol. 5, no. 1, pp. 15–17, 1976.
  * [16] V. T. Chakaravarthy, V. Pandit, S. Roy, and Y. Sabharwal, “Approximating decision trees with multiway branches,” in _International Colloquium on Automata, Languages, and Programming_. Springer, 2009, pp. 210–221.
  * [17] S. R. Kosaraju, T. M. Przytycka, and R. Borgstrom, “On an optimal split tree problem,” in _Workshop on Algorithms and Data Structures_. Springer, 1999, pp. 157–168.
  * [18] S. Dasgupta, “Analysis of a greedy active learning strategy,” _Advances in neural information processing systems_ , vol. 17, 2004.
  * [19] R. D. Nowak, “The geometry of generalized binary search,” _IEEE Transactions on Information Theory_ , vol. 57, no. 12, pp. 7893–7906, 2011.
  * [20] T. Biedl, B. Brejová, E. D. Demaine, A. M. Hamel, A. López-Ortiz, and T. Vinař, “Finding hidden independent sets in interval graphs,” _Theoretical Computer Science_ , vol. 310, no. 1-3, pp. 287–307, 2004.
  * [21] A. C. Hoffmann, D. Vallböhmer, K. Prenzel, R. Metzger, M. Heitmann, S. Neiss, F. Ling, A. H. Hölscher, and S. J. Brabender, “Methylated dapk and apc promoter dna detection in peripheral blood is significantly associated with apparent residual tumor and outcome,” _Journal of Cancer Research $\&$Clinical Oncology_, 2009.
  * [22] A. Fiat and A. Shamir, “How to find a battleship,” _Networks_ , vol. 19, no. 3, pp. 361–371, 1989.
  * [23] Z. Zhu, Y. Shi, J. Luo, F. Wang, C. Peng, P. Fan, and K. B. Letaief, “Fedlp: Layer-wise pruning mechanism for communication-computation efficient federated learning,” in _ICC 2023-IEEE International Conference on Communications_. IEEE, 2023, pp. 1250–1255.
  * [24] Q. Wu, Y. Zhao, Q. Fan, P. Fan, J. Wang, and C. Zhang, “Mobility-aware cooperative caching in vehicular edge computing based on asynchronous federated and deep reinforcement learning,” _IEEE Journal of Selected Topics in Signal Processing_ , vol. 17, no. 1, pp. 66–81, 2022.


# Hyperdimensional Feature Fusion for Out-of-Distribution Detection

Samuel Wilson
Queensland University of Technology
2 George St, Brisbane, QLD 4000, Australia
<EMAIL_ADDRESS>Tobias Fischer
Queensland University of Technology
2 George St, Brisbane, QLD 4000, Australia
<EMAIL_ADDRESS>Niko Sünderhauf
Queensland University of Technology
2 George St, Brisbane, QLD 4000, Australia
<EMAIL_ADDRESS>Feras Dayoub
University of Adelaide
North Terrace, Adelaide, SA 5005, Australia
<EMAIL_ADDRESS>
###### Abstract

We introduce powerful ideas from Hyperdimensional Computing into the
challenging field of Out-of-Distribution (OOD) detection. In contrast to most
existing works that perform OOD detection based on only a single layer of a
neural network, we use similarity-preserving semi-orthogonal projection
matrices to project the feature maps from _multiple_ layers into a common
vector space. By repeatedly applying the _bundling_ operation $\oplus$, we
create expressive class-specific descriptor vectors for all in-distribution
classes. At test time, a simple and efficient cosine similarity calculation
between descriptor vectors consistently identifies OOD samples with
competitive performance to the current state-of-the-art whilst being
significantly faster. We show that our method is orthogonal to recent state-
of-the-art OOD detectors and can be combined with them to further improve upon
the performance.

##  1 Introduction

Deep Neural Networks can achieve excellent performance on many vision tasks
when the distribution of training data closely matches the test data. However,
this assumption is often violated during deployment: especially in embodied AI
application domains such as robotics and autonomous systems, objects and
scenes that were not part of the training data distribution will inevitably be
encountered. When confronted with such out-of-distribution (OOD) samples, deep
neural networks tend to fail silently, producing overconfident but erroneous
predictions [16, 47] that can pose severe risks [52]. It is therefore
critically important that OOD samples are identified effectively during
deployment.

Figure 1: Illustration of our HDFF OOD detector. Top: After training, we
extract the feature maps of in-distribution classes from multiple layers of
the DNN and project them into a new hyperdimensional space with a similarity-
preserving projection matrix. Using the bundling operation $\oplus$ we create
class-specific hyperdimensional descriptor vectors. Bottom: During testing, we
repeat feature extraction, projection and bundling to obtain a
hyperdimensional image descriptor. OOD samples will produce descriptors with a
large angular distance to all class descriptors (red vector).

Previous techniques for OOD detection used softmax probabilities [18, 27] or
distances in logit space [17] to distinguish in-distribution (ID) from OOD
samples, making the implicit assumption that the features of a _single_ layer
in a Deep Neural Network (DNN) contain sufficient information to identify OOD
data. However, deeper layers of a DNN can be more sensitive to OOD samples
than the softmax probabilities [42], which are often overconfident in the
presence of OOD samples [16]. Recent work investigating the utility of multi-
scale deep features from a DNN found that modelling ID classes from raw
features is difficult without first reducing the number of dimensions [42, 26,
40] due to the curse of dimensionality [58].

In this paper, we introduce the powerful concepts of similarity-preserving
projection, binding and bundling from Hyper Dimensional Computing (HDC) [51]
to OOD detection. Figure 1 provides a high-level description of our proposed
OOD detector. We project the feature maps from _multiple_ layers of a network
into a common high-dimensional vector space, using similarity-preserving semi-
orthogonal projection matrices. This allows us to effectively _fuse_ the
information contained in multiple layers: a series of _bundling_ operations
$\oplus$ creates a class-specific high-dimensional vector representation for
each of the in-distribution classes from the training dataset. During testing,
we use the same principles of projection and bundling to obtain a single
vector representation for a new input image. OOD samples can then be
efficiently identified through cosine similarity operations with the class-
specific representations.

Our Hyperdimensional Feature Fusion (HDFF) approach relies on the pseudo-
random nature of its projection matrices and the similarity-preserving
properties of the bundling operation $\oplus$ to effectively fuse information
contained in the feature maps across multiple layers in a deep network. HDFF
avoids the difficulties of estimating densities in high-dimensional spaces
[42, 26], removes the limitation of relying on a single layer [18, 17], does
not require to select informative layers based on example OOD data [20, 55,
29], and does not necessarily rely on expensive sampling techniques (such as
ensembles [24] or Monte Carlo Dropout [10]) to identify OOD samples. HDFF can
be applied to a trained network and does not require re-training or fine-
tuning. Our HDFF detector competes with or exceeds state-of-the-art
performance for OOD detection in conjunction with networks trained with
standard cross-entropy loss or more sophisticated logit space shaping
approaches [56].

In summary, our contributions are the following:

  1. 1.

We propose a novel OOD detector based on the principles of Hyperdimensional
Computing that is competitive with state-of-the-art OOD detectors whilst
requiring significantly less training and inference time.

  2. 2.

We show that fusing features from multiple layers is critical for general OOD
detection performance, as different layers vary in sensitivity to different
OOD data, but fusion results in OOD performance that is approximately on par
or even better than the best single layer.

  3. 3.

We show that the angles between HDFF vectors can be interpreted as visual
similarity between inputs allowing for failure diagnosis.

We release a publicly available code repository to replicate our experiments
at: [released upon publication].

##  2 Related Work

Out-of-distribution (OOD) detection has been addressed in the context of image
classification [27, 29, 56, 18] and semantic segmentation [17, 8, 1, 2] with a
diverse set of solutions to each of the problems. In this section, we
highlight overarching concepts and most relevant contributions in three areas:
i) Many approaches try to extrapolate the properties of the distribution of
OOD data by utilising a small subset of the data to fine-tune on. ii) When
this information is unavailable (OOD agnostic), distances or densities in the
softmax probabilities and logit spaces are used. iii) Comparatively few bodies
of work exist that use multiple feature maps for OOD detection.

OOD Fine-tuning Some prior work [46, 20, 55, 29, 27, 8, 1] requires the
availability of an OOD dataset to train or fine-tune the network or adjust the
OOD detection process. However, such approaches are problematic. By
definition, the OOD dataset has to always be incomplete: during deployment,
samples that do not match the assumptions embedded in the OOD dataset can
still be encountered, leaving such methods exposed to high OOD risk. In
contrast, we do not require prior knowledge about the characteristics of OOD
data, instead we directly model the in-distribution data and measure
deviations from this set.

OOD Agnostic Most approaches that do not rely on the availability of OOD data
during training or validation analyse the model outputs to identify OOD data
during deployment. Early work [18] showed the maximum of a model’s softmax
output to be a good baseline. Expanding on this idea, [17] proposed using the
maximum of the unnormalised output logits. Additional methods focus on
extracting more information from the outputs [39] or learning calibrated
confidence estimates [7, 25]. Model averaging techniques such as Deep
Ensembles [24], Monte Carlo (MC) Dropout [10, 17] and SWA-G [30, 56] often
improve the OOD detection performance. Training networks with specialised
losses that impose a beneficial structure on the feature space has been
growing in popularity [32, 56, 33]. E.g. the recent 1D Subspaces [56] OOD
estimator encourages the network to learn orthogonal features in the layer
before the logits. The approaches discussed above attempt OOD detection based
on only a _single_ layer in the network. In contrast, we show that utilising
_multiple_ layers is beneficial for OOD detection.

Multi-Feature OOD Detection Newer approaches incorporate and analyse multi-
scale feature maps extracted from a DNN to detect OOD samples. The use of
feature maps and additional information extracted from a network has been
shown to set a new state-of-the-art in both OOD segmentation [8, 1] and
classification [9] when used as input to an auxiliary OOD detection network.
The requirement on an auxiliary network necessarily entails training on OOD,
or proxy-OOD, data that is strongly representative of the OOD samples likely
to be drawn from target distribution. Related work with auxiliary networks in
online performance monitoring demonstrates that this class of networks can be
robust to failures of the primary network without prior knowledge of the exact
failures that are likely to be encountered [44, 45]. Avoiding these problems
altogether, recent works have tried to model in-distribution classes without
an auxiliary network [42, 26, 40]. However, the curse of dimensionality
requires these methods to rely on PCA reductions [42, 26] or random
projections [40], losing information from the feature maps. By contrast, we
use techniques from Hyperdimensional Computing to model our in-distribution
data without the need for an auxiliary network. We seek to build upon evidence
in the literature [42, 48, 28, 9] that multi-scale features benefit OOD
detection performance.

##  3 Hyperdimensional Computing

Hyperdimensional Computing (HDC), also known as Vector Symbolic Architectures,
is the field of computation with vectors in hyperdimensional, very large,
spaces. HDC techniques leverage the large amount of expressive power in the
hyperdimensional (HD) space to model associations between data points using
redundant HD vector encodings. Redundant means that in spaces of $10^{4}$
dimensionality it can be seen that two random vectors are almost guaranteed to
be within 5 degrees of orthogonal [50] known as _quasi-orthogonality_. The
associations between data points are represented as vectors, and the set of
the representative vectors is known as the _associative memory_ [13].
Construction of the associative memory is done through the structured
combination of HD vectors using a set of standard operations. For our
application we are primarily interested in the _bundling $\oplus$_ and
_binding $\otimes$_ operation for combining feature vectors, and the encoding
operation for projecting low dimensional representations into our target HD
space.

Bundling The bundling $\oplus$ operation is used to store a representation of
multiple input vectors that retains similarity to all of the input vectors
[41]. Concretely, given random vectors $\mathbf{a}$, $\mathbf{b}$ and
$\mathbf{c}$, the vector $\mathbf{a}$ will be similar to the bundles
$\mathbf{a}\oplus\mathbf{b}$, $\mathbf{a}\oplus\mathbf{c}$ and
$\mathbf{a}\oplus\mathbf{b}\oplus\mathbf{c}$, although in the final case it
will be less similar as the bundled vector needs to be similar to all 3 input
vectors. Typically, the bundling operation is implemented as element-wise
addition with some form of normalisation to the required space for the
architecture [50]. Normalisation steps that are commonly seen are
normalisation to a magnitude of one [14, 11] or cutting/thresholding to a
range of desired values [12]. Without normalisation, the bundling operation is
commutative and associative; when normalisation steps are added the
associative aspect of the operation is approximate,
$(\mathbf{a}\oplus\mathbf{b})\oplus\mathbf{c}\approx\mathbf{a}\oplus(\mathbf{b}\oplus\mathbf{c})$
[50].

Binding The binding $\otimes$ operation is used to combine a set of vectors
into one representation that is dissimilar to all of the input vectors [41].
Given the quasi-orthogonality property of HD spaces, this entails that in all
likelihood, the binding operation will generate a vector orthogonal to all of
the input vectors in the cosine similarity space. The second core trait of the
binding operation is that it approximately preserves the similarity of two
vectors before and after binding if they are bound to the same target vector.
More precisely, for a set of vectors in the same hyperdimensional space
$\mathbf{a}$, $\mathbf{b}$ and $\mathbf{c}$, that
$sim(\mathbf{a},\mathbf{b})\approx
sim(\mathbf{a}\otimes\mathbf{c},\mathbf{b}\otimes\mathbf{c})$.

Encoding The format of the original data will not always be in the
hyperdimensional space that is required. Encoding addresses this by projecting
each data point from the original space into the new HD space. The selection
of data encoding into a HD space depends on the type of the original data [43,
19]. An important principle of encoding is that distances in the input are
preserved in the output [19], much like the binding operation. Examples of
encoding include multiplication with a projection matrix [34], fractional
binding [22] that preserves real numbered differences, or the encoding
proposed in [19] that preserves similarities of vectors over time and spatial
coordinates.

We provided only a brief introduction to HDC, for more in-depth discussions
and comparisons between known architectures we encourage the reader to
consider [50, 37, 21].

##  4 Hyperdimensional Feature Fusion

We propose Hyperdimensional Feature Fusion (HDFF), a novel OOD detection
method that applies the HDC concepts of Encoding and Bundling to the features
from _multiple_ layers in a deep neural network, without requiring re-training
or any prior knowledge of the OOD data. Our core idea is to project the
feature maps from multiple layers into a common vector space, using
similarity-preserving semi-orthogonal projection matrices. Through a series of
bundling operations, we create a class-specific vector-shaped representation
for each of the classes in the training dataset. During deployment, we repeat
the projection and bundling steps for a new input image, and use the cosine
similarity to the class representatives to identify OOD samples. We provide
pseudo code to assist with describing our HDFF detector in Algorithm 1.

Preliminaries From a pretrained network $f$, we can extract feature maps
$\mathbf{m}_{l}$ from different layers $l\in\\{1,\dots,L\\}$ in the the
network. We apply a pooling operation across the spatial dimensions to reduce
the tensor-shaped (height $\times$ width $\times$ channels) feature maps to
vector representations $\mathbf{v}_{l}$ of length (channels) for each layer;
we ablate the effects of different pooling in the Supplementary Material.
Since the feature maps of different layers have a different number of channels
$c_{l}$, we need to project the vectors $\mathbf{v}_{l}$ into a common
$m$-dimensional vector space $\mathbb{R}^{m}$ in order to combine them.
Conventional sizes for HD spaces range around $10^{3}$ \- $10^{4}$ [38, 34,
19], meaning that typically our HD space will be much larger than our original
space $m>>c$.

Feature Encoding Any $m\times c$ matrix $\mathbf{P}$ projects a
$c$-dimensional vector $\mathbf{v}$ into a $m$-dimensional space by left-
multiplying: $\mathbf{P}\mathbf{v}$. However, preserving the cosine similarity
of the projected vectors is a crucial consideration for our application in OOD
detection. We therefore impose that the projection matrices $\mathbf{P}_{l}$
preserve the inner product of any two vectors $\mathbf{a}$ and $\mathbf{b}$ in
their original and their projected vector spaces. Formally, this means that

$\displaystyle(\mathbf{P}\cdot\mathbf{a})^{\mathsf{T}}\cdot(\mathbf{P}\cdot\mathbf{b})$
$\displaystyle=$ $\displaystyle\mathbf{a}^{\mathsf{T}}\cdot\mathbf{b}$ (1)
$\displaystyle\mathbf{a}^{\mathsf{T}}\cdot\mathbf{P}^{\mathsf{T}}\cdot\mathbf{P}\cdot\mathbf{b}$
$\displaystyle=$ $\displaystyle\mathbf{a}^{\mathsf{T}}\cdot\mathbf{b}$ (2)

Above condition is satisfied by any matrix that fulfils the requirement
$\mathbf{P}^{\mathsf{T}}\mathbf{P}=\mathbf{I}$, which is the defining property
of a semi-orthogonal matrix. Using the approach of [49], we therefore create a
unique, pseudo-random, semi-orthogonal projection matrix $\mathbf{P}_{l}$ for
each of the considered layers $l$. These project the feature vectors
$\mathbf{v}_{l}$ into a common $m$-dimensional vector space:

$\mathbf{h}_{l}=\mathbf{P}_{l}\mathbf{v}_{l}\quad\text{so
that}\;\;\mathbf{h}_{l}\in\mathbb{R}^{m}\;\;\forall l\in\\{1,\dots,L\\}$ (3)

Inputs: Set of images from the training set $x^{\\{1,\dots,I\\}}$ with
corresponding labels $j^{\\{1,\dots,I\\}}$. Set of models in an ensemble
$f_{\\{1,\dots,E\\}}$ that produces a set of feature maps
$\mathbf{m}_{\\{1,\dots,L\\}}$ given an input $x^{(i)}$.

Outputs: Set of class descriptor vectors per input model
$d^{(e)}_{\\{1,\dots,c\\}}$ and a set of ensemble class descriptor vectors
$d^{*}$

for e $\in$ {1,…,E} do

for i $\in$ {1,…,I} do

$m^{(i)}_{\\{1,\dots,L\\}}\leftarrow f_{e}(x^{(i)})$

for l $\in$ {1,…,L} do

$v^{(i)}_{l}\leftarrow Pool(m^{(i)}_{l})$

$h^{(i)}_{l}\leftarrow P_{l}\cdot v^{(i)}_{l}$

end for

$y^{(i)}\leftarrow h^{(i)}_{1}\oplus h^{(i)}_{2}\oplus...\oplus h^{(i)}_{L}$

$d^{(e)}_{j^{(i)}}\leftarrow d^{(e)}_{j^{(i)}}\oplus y^{(i)}$

end for

end for

$d^{*}\leftarrow(d^{(1)}\otimes z^{(1)})\oplus...\oplus(d^{(E)}\otimes
z^{(E)})$

Algorithm 1 Computation of the model-wise class descriptors and ensemble
descriptor vectors from training set.

Feature Bundling Following the previous steps, we obtain a set of $L$ high-
dimensional vectors $\mathbf{h}_{l}^{(i)}$ for an input image
$\mathbf{x}^{(i)}$. Since all $\mathbf{h}_{l}^{(i)}$ are elements of the same
vector space, we can use the bundling operation $\oplus$ to combine them into
a single vector $\mathbf{y}^{(i)}$ that serves as an expressive descriptor for
the input image $\mathbf{x}^{(i)}$:

$\mathbf{y}^{(i)}=\bigoplus_{l=1}^{L}\mathbf{h}_{l}^{(i)}=\bigoplus_{l=1}^{L}\mathbf{P}_{l}\cdot\mathbf{v}_{l}^{(i)}$
(4)

As explained in Section 3, the resulting vector $\mathbf{y}^{(i)}$ will be
cosine-similar to all contributing vectors $\mathbf{h}_{l}^{(i)}$, but
dissimilar to vectors from $\mathbb{R}^{m}$ that were not part of the bundle.
Essentially, $\mathbf{y}^{(i)}$ provides a summary of the feature vectors
$\mathbf{v}_{l}^{(i)}$ of the entire network for a single image
$\mathbf{x}^{(i)}$.

By bundling the descriptors of all images from the training set belonging to
class $c$, we obtain a class-specific descriptor $\mathbf{d}_{c}$:

$\mathbf{d}_{c}=\bigoplus_{j\in\mathbb{I}_{c}}\mathbf{y}^{(j)}$ (5)

where $\mathbb{I}_{c}$ denotes the set of indices of the training images
belonging to class $c$.

As discussed in Section 3, the bundling operation $\oplus$ can be implemented
in various ways. We implement $\oplus$ to be an element-wise sum, without
truncation.

Out-of-Distribution Detection During testing or deployment, an image
$\mathbf{x}$ can be identified as OOD by obtaining its image descriptor
$\mathbf{y}$ according to (4), and calculating the cosine similarity to each
of the class-specific descriptors $\mathbf{d}_{c}$. Let $\theta$ be the angle
to the class descriptor $\mathbf{d}_{c}$ that is most similar to $\mathbf{y}$

$\theta=\min_{c}\cos^{-1}\left(\frac{\mathbf{y}^{\mathsf{T}}\mathbf{d}_{c}}{\|\mathbf{y}\|\cdot\|\mathbf{d}_{c}\|}\right),\;c\in\\{1,\dots,C\\},$
(6)

The input $\mathbf{x}$ is then treated as OOD if $\theta$ is bigger than a
threshold: $\theta>\theta^{*}$.

Ensembling While HDFF does not rely on ensembling, we briefly show that our
method is amenable to ensembling to further boost performance (however at the
cost of added compute). When using a set of pretrained networks $f_{e}$ in an
ensemble $e\in\\{1,\dots,E\\}$ we collect inputs from all models and fuse them
into singular image and class descriptors $\mathbf{y}_{*}$ and
$\mathbf{d}^{*}$ respectively. For each model $f_{\\{1,\dots,E\\}}$ the same
process using equations (4) and (5) is used to compute the set of class
descriptors for each model in the ensemble $\mathbf{d}^{\\{1,\dots,E\\}}$. To
ensure that each class descriptor is sufficiently distinct from all other
descriptors, a set of random hyperdimensional vectors $\mathbf{z}^{(e)}$ are
generated and bound $\otimes$ to the class descriptor. By bundling the bound
class descriptors, we obtain the ensemble class descriptor $\mathbf{d}^{*}$:

$\mathbf{d}^{*}=\bigoplus_{e=1}^{E}\mathbf{d}^{(e)}\otimes\mathbf{z}^{(e)}$
(7)

When new input samples arrive $\mathbf{y}_{*}$ is computed according to (7) by
substituting $\mathbf{d}$ for $\mathbf{y}$. OOD detection is done according to
(6) using $\mathbf{d}^{*}$ and $\mathbf{y}_{*}$.

##  5 Experiments

We conduct a series of experiments to demonstrate the efficacy of
Hyperdimensional Feature Fusion for OOD detection. We compare HDFF to the
current state-of-the-art in the typical far-OOD settings, where the
distributions of the of ID and OOD are very dissimilar (e.g. CIFAR10
$\rightarrow$ SVHN), and the more challenging near-OOD where the ID and OOD
datasets are drawn from similar distributions (e.g. CIFAR10 $\rightarrow$
CIFAR100). Further, we report the results of some critical ablation studies,
in particular, we identify which layers are most sensitive to OOD data and how
sensitive HDFF is to the decision parameter $\theta^{*}$ during deployment.

###  5.1 Experimental Setup

Datasets For our comparisons to existing OOD detectors we use a wide array of
popular datasets composed from multiple recent state-of-the-art OOD detectors.
We construct our evaluation suite as the combination of datasets from [27, 48,
28]. For our comparison to existing OOD detectors, we use the popular dataset
splits for near- and far-OOD detection using CIFAR10 and CIFAR100 [23] as the
ID datasets. For our ID sets, we use the 50,000 training examples for training
and computation of the class bundles, whilst the 10,000 testing images are
used as our unseen ID data. For the near-OOD configurations, the test set of
whichever CIFAR dataset is not being used for training will be used as the OOD
set. For the far-OOD detection settings, we use a suite of benchmarks: iSUN,
TinyImageNet [5] (cropped and resized: TINc and TINr), LSUN [54] (cropped and
resized: LSUNc and LSUNr)111Download links for OOD datasets can be found in
the following repository: https://github.com/facebookresearch/odin, SVHN [36],
MNIST [6], KMNIST [4], FashionMNIST [53], and Textures [3]. In the interest of
brevity, we only show the settings where CIFAR10 is the ID set, the settings
of CIFAR100 as ID are provided in the Supplementary Material.

Evaluation Metrics We consider the standard metrics [56, 48] for our
comparison to existing OOD literature. AUROC: The Area Under The Receiver
Operating Characteristic curve corresponds to the area under the ROC curve
with true positive rate (TPR) on the y-axis and false positive rate (FPR) on
the x-axis. AUROC can be interpreted as the probability that an OOD sample
will be given a higher score than an ID sample [17]. FPR95: The FPR95 metric
reports the FPR at a critical threshold which achieves a minimum of 95% in
TPR. Detection Error: Detection Error indicates the minimum misclassification
probability with respect to the critical threshold. F1: F1-score corresponds
to the harmonic mean of precision and recall. We make use of F1-score to
evaluate the general binarisation performance in our ablations. In the
interests of brevity, we only evaluate using the AUROC metric for our
evaluations. We provide additional evaluations with FPR95 and Detection Error
in the Supplementary Material.

Baselines We divide our selected baselines and SOTA comparisons into two
evaluation streams, these being; statistics and training. The statistics
stream contains methods that are generally applied post-hoc to a pretrained
network, requiring no training and only minimal calibration to represent in-
distribution data. The training stream contains methods that allow for the
retraining of the base network or the training of an auxiliary monitoring
network. The distinction between the two streams is important for a fair
comparison as the methods in the training stream have a significantly longer
calibration (training) time as well as biases towards the OOD data, either
explicitly through proxy-OOD training or implicitly through assumptions about
the formation of OOD data with a custom loss.

In the statistics stream we compare against: maximum softmax probability [18]
(MSP), max logit [17] (ML), gramian matrices [48] (Gram) and energy-based
model [29] without calibration on OOD data. For the training stream we compare
against: NMD [9], Spectral Discrepancy trained with the 1D Subspaces
methodology [56] (1DS), Deep Deterministic Uncertainty [35] (DDU) and MOOD
[28].

Implementation We follow the evaluation procedure defined in [56, 27],
implementing the standard WideResNet [57] network with a depth of 28 and a
width of 10. In the statistics stream, this model is trained to convergence
with standard cross-entropy loss. Custom loss objectives are restricted to the
training stream.

As HDFF is a post-hoc statistics-based method, it is innately orthogonal to
the methods contained within the training stream and can be combined with many
of them in a post-hoc fashion. To demonstrate the robustness of HDFF we
combine it with two of the other state-of-the-art detectors, 1D Subspaces [56]
and NMD [9]. The HDFF-1DS method applies as described in Section 4 but the
base model has been trained with the 1D Subspaces custom objective. The second
model HDFF-MLP trains an auxiliary MLP as a binary ID/OOD classifier using the
generated HDFF image descriptor vectors $\mathbf{y}^{(i)}$ of perturbed
(proxy-OOD) and normal (ID) images from the ID training set as input into the
MLP alike NMD [9].

We re-implement the MSP, ML and Gram detectors for the WideResNet
architecture, for all other methods, excluding NMD [9] and MOOD [28], we
report the published results on the same architecture. At the time of writing,
a publicly available implementation of NMD [9] is unavailable and as such we
utilise their published results in the zero-shot OOD scenario on ResNet34
[15]. MOOD [28] is built upon a custom network architecture that enables early
exits during inference, we report the published results on this custom
architecture due to the unclear applicability of the method to other network
architectures.

When applying HDFF and Gram [48] to the WideResNet model we attempt to
faithfully recreate the hook locations of Gram from the original architecture.
Specifically, features are recorded from the outputs of almost all of the
following modules within the network: Conv2d, ReLU, BasicBlock, NetworkBlock
and shortcut connections. In total, there are 76 features extracted per sample
and hence the same number of semi-orthogonal projection matrices $\mathbf{P}$
are generated for HDFF.

Unless otherwise stated, we operate in a hyperdimensional space of $10^{4}$
dimensions, we ablate this hyperparameter in the Supplementary Material.
Before projecting feature maps into the hyperdimensional space as per (5), we
apply mean-centering by subtracting the layer-wise mean activations (obtained
from the training set) from all $\mathbf{m}_{l}$. For pooling we apply max
pooling over the spatial dimensions to reduce our feature maps
$\mathbf{m}_{l}$ to a vector representation, we ablate the effect of this
choice in the Supplementary Material.

Statistics Stream - CIFAR10
---
OOD | HDFF | HDFF-Ens | Gram | MSP | ML | Energy
Dataset | (Ours) | (Ours) | [48] | [18] | [17] | [29]
iSun | 99.2 | 99.3 | 99.9 | 96.4 | 97.8 | 92.6
TINc | 98.3 | 98.4 | 99.4 | 95.4 | 96.8 | -
TINr | 99.2 | 99.4 | 99.8 | 95.0 | 96.5 | -
LSUNc | 96.2 | 96.8 | 98.1 | 95.7 | 97.1 | 98.4
LSUNr | 99.2 | 99.4 | 99.9 | 96.5 | 98.0 | 94.2
SVHN | 99.4 | 99.5 | 99.4 | 96.0 | 97.2 | 91.0
MNIST | 99.6 | 99.7 | 99.97 | 89.4 | 90.6 | -
KMNIST | 99.0 | 99.1 | 99.98 | 92.7 | 93.4 | -
FMNIST | 98.7 | 99.1 | 99.8 | 93.6 | 95.2 | -
Textures | 94.5 | 94.8 | 98.2 | 92.7 | 93.5 | 85.2
CIFAR100 | 75.4 | 75.8 | 79.4 | 87.8 | 87.3 | -
Average | 96.2 | 96.5 | 97.6 | 93.7 | 94.9 | 93.2
Table 1: OOD detection results for the against the methods contained belonging
to the statistics stream. Comparison metric is AUROC, higher is better. Best
results are shown in blue and bold, second best results are shown in green and
italics. The ensemble in HDFF-Ens always consists of 5 models. HDFF and Gram
are consistently the top two performers across the significant majority of the
far-OOD detection settings. Training Stream - CIFAR10
---
OOD | HDFF-MLP | HDFF-1DS | 1DS | NMD | DDU | MOOD
Dataset | (Ours) | (Ours) | [56] | [9] | [35] | [28]
iSun | 99.99 | 99.9 | - | 99.9 | - | 93.0
TINc | 99.9 | 99.7 | 98.1 | 99.2* | 91.1* | -
TINr | 99.96 | 99.8 | 98.5 | - | 91.1* | -
LSUNc | 98.2 | 99.1 | 99.4 | 98.8 | - | 99.2
LSUNr | 99.99 | 99.9 | 99.3 | - | - | 93.3
SVHN | 84.8 | 99.2 | - | 99.6 | 97.9 | 96.5
MNIST | 99.4 | 99.3 | - | - | - | 99.8
KMNIST | 98.6 | 99.3 | - | - | - | 99.9
FMNIST | 99.6 | 99.3 | - | - | - | -
Textures | 97.4 | 97.3 | - | 98.9 | - | 93.3
CIFAR100 | 69.9 | 90.7 | - | 90.1 | 91.3 | -
Average | 95.2 | 98.5 | 98.8 | 97.8 | 94.6 | 95.0
Table 2: OOD detection results for the against the methods contained belonging
to the training stream. Comparison metric is AUROC, higher is better. Best
results are shown in blue and bold, second best results are shown in green and
italics. Published results that are unclear which variant of TIN they
correspond to are identified with a *. The incorporation of HDFF into pre-
existing pipelines leads to consistently improving or comparable results,
demonstrating the robust nature of HDFF. Figure 2: F1-score for binarisation
at different critical values of angular distance to closest class descriptor.
The model used is the 1D Subspaces trained WideResNet. The grey region
corresponds to binarisations that would produce a result within 5% of the
maximum F1-score achieved for all far-OOD datasets. To avoid clutter, far-OOD
datasets have been grouped: i) MNIST (AVG) contains KMNIST, MNIST and
FashionMNIST. ii) SUN (AVG) contains iSUN, LSUNr and LSUNc. iii) Other (AVG)
contains all other far-OOD datasets. As expected, the near-OOD task (CIFAR100)
leads to significantly lower thresholds compared to all far-OOD tasks.

###  5.2 Results and Discussion

Table 1 compares the results of our HDFF OOD detector on the AUROC metric to
all of the methods in the statistics stream under both the near- and far-OOD
settings. In the far-OOD setting HDFF and Gram are consistently the top
performers with small performance differences of less than 1% AUROC between
the two methods on most OOD dataset configurations. This finding indicates
that the feature representations of the in-distribution data from both Gram
and HDFF are powerful for the far-OOD detection task. On this note, we
identify that the vector representation of HDFF is far more compact than the
square matrix representations from Gram. The difference in representation
complexity accounts for the performance differences, but also introduces large
gaps in computational performance with gram requiring $\approx$4.5x longer per
inference pass compared to HDFF as described in Section 5.3.

We note that the MSP detector outperforms all other methods in the statistics
stream in the near-OOD detection setting (CIFAR10 as in-distribution and
CIFAR100 as OOD). Considering that HDFF is effectively detecting deviations in
convolutional feature activations this would indicate that images with similar
features are being grouped with in-distribution classes, this behaviour is
discussed more in Section 5.6.

Table 2 compares the results of the methods in the training stream on the
AUROC metric in the near- and far-OOD settings. The first finding from this
table is the broadly powerful nature of the HDFF vector representation in
combination with the MLP. Across the board, the majority of the top performing
results are from the HDFF MLP detector demonstrating the power of the HDFF
representation when combined with latest state-of-the-art detectors.

Secondly and more specifically, we note that when HDFF is applied to the 1D
Subspaces trained model it improves upon the performance of the Spectral
Discrepancy detector on 3 out of the 4 comparable benchmarks. We additionally
note that the Spectral discrepancy detector requires 50 SWA-G [31] samples to
achieve these performance levels whilst the HDFF detector requires only one
inference pass, mandating a 5000% increase in computational time when using
Spectral Discrepancy. These two findings combined reinforce the claim that
HDFF is generally applicable to a wide range of models and training regimes.

###  5.3 Computational Efficiency

HDC techniques are commonly used for computation or learning in low-power
situations [34, 19] and as such, we expect HDFF to introduce minimal
computational overhead. For a full pass of the CIFAR10 test set, HDFF takes
7.0$\pm$0.9s compared to a standard inference pass at 6.0$\pm$0.7s, averaged
over 5 independent runs. We note that this $\approx$17% increase is
comparatively minor considering the large performance gains that HDFF boasts
over the MSP and ML detectors. By comparison, the closest equivalent method to
ours, Gram [48] takes 31.4$\pm$0.3s to complete a full inference pass over the
CIFAR10 test set, resulting in an $\approx$4.5x longer inference time than
HDFF. Additionally, we expect the computational efficiency of Gram to drop on
larger networks due to the gram matrices scaling $O(n^{2})$ in computation and
memory requirements with the number of channels whereas HDFF scales linearly
$O(n)$ with the number of channels.

Characteristic of belonging to the statistics stream, HDFF requires far less
calibration or training than other methods belonging to the training stream.
In particular, the closest comparative method, NMD, prescribes a training
regime of 60-100 epochs for the MLP detector, whereas HDFF only requires a
single epoch to collect the full in-distribution statistics, resulting in a
minimum 60x decrease in computational time. Additionally, HDFF can be applied
post-hoc to common networks, requiring no additional computation in the
training or fine-tuning of the network. We further note that HDFF with only a
single inference pass competes with or exceeds the Spectral Discrepancy
detector [56] that requires 50 MC samples to be collected, necessitating a
minimum inference increase of 5000%.

###  5.4 Critical Threshold Ablation

During deployment, it is often more useful if an OOD detector produces a
binarisation of ID vs OOD rather than a raw OOD estimate; the grey regions in
Figure 2 show a range of critical thresholds that will produce performance
reasonably close to optimal in this setting. Specifically, the grey region in
Figure 2 shows a region of confidence where any critical value would produce
an F1-score within 5% of the maximum value achieved on each far-OOD dataset,
an approximate standard of reasonable performance. The near-OOD detection task
is plotted but does not contribute towards the definition of the grey region
due to the severe differences between the near- and far-OOD tasks. As we can
see, a large region of critical values around the range of 18-29 degrees will
result in generally good performance for far-OOD detection.

###  5.5 Which Layers Are Most Sensitive To OOD Data?

Congruent with other multi-layer OOD detectors [9, 48] we ablate the
sensitivity of individual layers with respect to OOD samples from different
target distributions. Figure 3 demonstrates the effectiveness of individual
layers when they are used in isolation for OOD detection based on our HDFF OOD
estimator. For the sake of readability, we explicitly change the hook function
to only collect features from the outputs of the 12 BasicBlocks and only
consider the TIN and LSUN datasets for simplicity. We see in both ID settings
that earlier features in the network appear to be less reliable at detecting
OOD samples. This trend is particularly obvious in the CIFAR10 setting where
there is a clear upwards trend as the layer number increases. This observation
lends weight towards the suggestions in prior work that shallow layers in a
DNN are unable to or at least are less effective at detecting OOD data [42].

Figure 3: Comparison of effectiveness for OOD detection of each layer
individually with the AUROC measure. CIFAR10 is the in-distirbution dataset.
Mean and 95% confidence interval over 5 randomly initialised models trained
with the 1D Subspaces methodology. Dotted lines correspond to the results
attained by the fusion of all 12 BasicBlocks. Performance of individual layers
shows a trend toward later layers being more effective at detecting OOD data.
The fusion of feature maps from across the network provides good general
performance across all datasets and does not require calibration on OOD data
to set.

The dotted lines, and related 95% confidence shaded area, for each dataset
correspond to the fusion of information from all layers; we consider these
lines the best that can be reasonably achieved within the bounds of the OOD
task. In Figure 3 we observe that no single individual layer is able to detect
the OOD data as well as the fusion of all feature maps. Critically, we note
two points in favour of the fusion of features: (1) without OOD data the
optimal layer combination for a given data set is unknown, and (2) the optimal
layer combination is not consistent between OOD data configurations as shown
by the drop in performance on LSUNc. To summarise, note that if there is no
access to OOD data at training time to determine which layer(s) are the best
then the fusion of feature maps from across the network often provides the
best performance or a close approximation. We provide extra ablations against
other metrics and the CIFAR100 ID set in the Supplementary Material.

###  5.6 Distance of Features as Visual Similarity

As HDFF uses similarity preserving projections, the angular distance directly
represents the differences between two input sets of raw features. Since these
features are extracted from a deep CNN we can consider the angular distance
between any two vectors to be a proxy for their visual dissimilarity. This
definition leads to intuitive understandings of how HDFF behaves and
identifying failure cases; we discuss these points here.

Using our definition, since HDFF separates based on visual similarity, we can
infer that failures in OOD detection are due either to ID samples being
visually dissimilar to the training set or OOD samples are as similar, if not
more so, to the training set than the ID samples. To aid in understanding
this, Figure 4 visualises the differences in distributions of angular distance
between the ID and OOD datasets in the CIFAR10 ID setting through a KDE
estimate (for smoothing) over binned angular distances on the HDFF 1D
Subspaces model. The area of overlap between the test set and any OOD set can
be considered as erroneous detection. Inspecting Figure 4, we observe that, in
the far-OOD settings, errors due to dissimilar ID samples are more likely to
appear due to the distributional shift between the training and testing
distributions, i.e. false positives. By contrast, in the near-OOD detection
task we see that a significant number of errors are due to OOD samples
appearing very similar to ID samples, i.e. false negatives.

Figure 4: KDE estimate of separation between ID and OOD sets based on minimum
angular distance to closest class representative in the CIFAR10 setting. To
avoid clutter, far-OOD datasets have been grouped: i) MNIST (AVG) contains
KMNIST, MNIST and FashionMNIST. ii) SUN (AVG) contains iSUN, LSUNr and LSUNc.
iii) Other (AVG) contains all other far-OOD datasets. Overlap between the test
and OOD distributions can be considered erroneous samples.

As a more concrete example, Figure 5 demonstrates HDFF separating input
samples based on the angle to the nearest class descriptor vector, in this
case, the CIFAR10 truck class. Consistent with our previous assertions, we
observe in Figure 5 that samples that are $<15^{\circ}$ from the class
descriptor vector appear visually very similar, with no far-OOD samples
occupying this range. In the range of $15-30^{\circ}$ we observe that samples
from all datasets still have vehicle-like appearance, but whether or not these
accurately represent a truck is debatable; this region is still predominantly
populated by ID and near-OOD samples. Once outside the $30^{\circ}$ ring, we
see that the significant majority of samples do not appear vehicle-like with
the very few ID samples in this region having the truck visually obscured;
this region is dominated by far-OOD samples.

Figure 5: Sample images from in-distribution (CIFAR10, blue), near-OOD
(CIFAR100, green) and far-OOD (TINc, red) datasets with their approximate
distance to the nearest class descriptor vector, corresponding to the CIFAR10
ID truck class. The underlying model is the 1D Subspaces trained WideResNet.
Distances to the class bundle (centre blue dot) can be approximately inferred
from which circle the sample is encapsulated by. This figure reinforces the
hypothesis that HDFF separates based on visual similarity to the in-
distribution class as truck-like objects appear within the inner circle,
vehicle-like objects in the middle region and heavily dissimilar object
falling outside both of those regions.

##  6 Conclusion

This paper introduced powerful ideas from hyperdimensional computing into the
important task of OOD detection. We investigate the sensitivity of individual
layers to OOD data and find that the fusion of feature maps provides the best
general performance with no requirements for OOD data to fine-tune on. We
perform competitively with state-of-the-art OOD detection methods with the
added benefit of significantly reducing the computational costs associated
with the current state-of-the-art. We show the interpretation of cosine
distance as a proxy for visual similarity allows for additional failure
diagnosis capabilities over competing methods. In this paper, we utilised the
simple but powerful element-wise addition for bundling, however, this is one
of potentially many applications of HDC to DNNs, opening new future research
directions.

Acknowledgements: The authors acknowledge continued support from the
Queensland University of Technology (QUT) through the Centre for Robotics. TF
was partially supported by funding from ARC Laureate Fellowship FL210100156
and Intel’s Neuromorphic Computing Lab. We also thank Peer Neubert from
Chemnitz University of Technology for greatly insightful discussions on the
topic of Hyperdimensional Computing.

## References

  * [1] Petra Bevandić, Ivan Krešo, Marin Oršić, and Siniša Šegvić.  Simultaneous semantic segmentation and outlier detection in presence of domain shift.  In Pattern Recognition, pages 33–47, 2019.
  * [2] Hermann Blum, Paul-Edouard Sarlin, Juan Nieto, Roland Siegwart, and Cesar Cadena.  The fishyscapes benchmark: Measuring blind spots in semantic segmentation.  International Journal of Computer Vision, 129(11):3119–3135, 2021\.
  * [3] M. Cimpoi, S. Maji, I. Kokkinos, S. Mohamed, , and A. Vedaldi.  Describing textures in the wild.  In Proceedings of the IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2014.
  * [4] Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha.  Deep learning for classical japanese literature.  CoRR, abs/1812.01718, 2018.
  * [5] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
  * [6] Li Deng.  The mnist database of handwritten digit images for machine learning research.  IEEE Signal Processing Magazine, 29(6):141–142, 2012.
  * [7] Terrance DeVries and Graham W Taylor.  Learning confidence for out-of-distribution detection in neural networks.  arXiv preprint arXiv:1802.04865, 2018.
  * [8] Giancarlo Di Biase, Hermann Blum, Roland Siegwart, and Cesar Cadena.  Pixel-wise anomaly detection in complex driving scenes.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 16918–16927, 2021.
  * [9] Xin Dong, Junfeng Guo, Ang Li, Wei-Te Ting, Cong Liu, and H.T. Kung.  Neural mean discrepancy for efficient out-of-distribution detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 19217–19227, June 2022.
  * [10] Yarin Gal and Zoubin Ghahramani.  Dropout as a Bayesian approximation: Representing model uncertainty in deep learning.  In International Conference on Machine Learning, 2016.
  * [11] Stephen I. Gallant and T. Wendy Okaywe.  Representing Objects, Relations, and Sequences.  Neural Computation, 25(8):2038–2078, 2013.
  * [12] R. Gayler.  Multiplicative binding, representation operators & analogy.  In Advances in analogy research: Integr. of theory and data from the cogn., comp., and neural sciences, 1998.
  * [13] Lulu Ge and Keshab K. Parhi.  Classification using hyperdimensional computing: A review.  IEEE Circuits and Systems Magazine, 20(2):30–47, 2020.
  * [14] Jan Gosmann and Chris Eliasmith.  Vector-derived transformation binding: An improved binding operation for deep symbol-like processing in neural networks.  Neural Computation, 31(5):849–869, 2019.
  * [15] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2016.
  * [16] Matthias Hein, Maksym Andriushchenko, and Julian Bitterwolf.  Why ReLU networks yield high-confidence predictions far away from the training data and how to mitigate the problem.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 41–50, 2019.
  * [17] Dan Hendrycks, Steven Basart, Mantas Mazeika, Mohammadreza Mostajabi, Jacob Steinhardt, and Dawn Song.  Scaling out-of-distribution detection for real-world settings.  arXiv preprint arXiv:1911.11132, 2019.
  * [18] Dan Hendrycks and Kevin Gimpel.  A baseline for detecting misclassified and out-of-distribution examples in neural networks.  In International Conference on Learning Representations, 2017.
  * [19] Alejandro Hernández-Cano, Cheng Zhuo, Xunzhao Yin, and Mohsen Imani.  Real-time and robust hyperdimensional classification.  In Great Lakes Symposium on VLSI, page 397–402, 2021.
  * [20] Haiwen Huang, Zhihan Li, Lulu Wang, Sishuo Chen, Bin Dong, and Xinyu Zhou.  Feature space singularity for out-of-distribution detection.  In Workshop on Artificial Intelligence Safety, 2021.
  * [21] Pentti Kanerva.  Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors.  Cognitive Computation, 1(2):139–159, 2009.
  * [22] Brent Komer, Terrence Stewart, Aaron Voelker, and Chris Eliasmith.  A neural representation of continuous space using fractional binding.  In CogSci, pages 2038–2043, 2019.
  * [23] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, 2009.
  * [24] Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell.  Simple and scalable predictive uncertainty estimation using deep ensembles.  In Advances in Neural Information Processing Systems, 2017.
  * [25] Kimin Lee, Honglak Lee, Kibok Lee, and Jinwoo Shin.  Training confidence-calibrated classifiers for detecting out-of-distribution samples.  In International Conference on Learning Representations, 2018.
  * [26] Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin.  A simple unified framework for detecting out-of-distribution samples and adversarial attacks.  In Advances in Neural Information Processing Systems, 2018.
  * [27] Shiyu Liang, Yixuan Li, and R. Srikant.  Enhancing the reliability of out-of-distribution image detection in neural networks.  In International Conference on Learning Representations, 2018.
  * [28] Ziqian Lin, Sreya Dutta Roy, and Yixuan Li.  Mood: Multi-level out-of-distribution detection.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 15313–15323, June 2021.
  * [29] Weitang Liu, Xiaoyun Wang, John Owens, and Yixuan Li.  Energy-based out-of-distribution detection.  In Advances in Neural Information Processing Systems, 2020.
  * [30] Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson.  A simple baseline for bayesian uncertainty in deep learning.  In Advances in Neural Information Processing Systems, 2019.
  * [31] Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry P Vetrov, and Andrew Gordon Wilson.  A simple baseline for bayesian uncertainty in deep learning.  In Advances in Neural Information Processing Systems, pages 13153–13164, 2019.
  * [32] Dimity Miller, Niko Sunderhauf, Michael Milford, and Feras Dayoub.  Class anchor clustering: A loss for distance-based open set recognition.  In IEEE/CVF Winter Conference on Applications of Computer Vision, pages 3570–3578, 2021.
  * [33] Dimity Miller, Niko Sünderhauf, Michael Milford, and Feras Dayoub.  Uncertainty for identifying open-set errors in visual object detection.  IEEE Robotics and Automation Letters, 7(1):215–222, 2021.
  * [34] Justin Morris, Yilun Hao, Roshan Fernando, Mohsen Imani, Baris Aksanli, and Tajana Rosing.  Locality-based encoder and model quantization for efficient hyper-dimensional computing.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2021.  to appear.
  * [35] Jishnu Mukhoti, Andreas Kirsch, Joost van Amersfoort, Philip H. S. Torr, and Yarin Gal.  Deep deterministic uncertainty: A simple baseline.  arXiv preprint arXiv:2102.11582, 2022.
  * [36] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Ng. Andrew.  Reading digits in natural images with unsupervised feature learning.  In NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
  * [37] Peer Neubert, Stefan Schubert, and Peter Protzel.  An introduction to hyperdimensional computing for robotics.  Künstliche Intelligenz, 33(4):319–330, 2019.
  * [38] Peer Neubert, Stefan Schubert, Kenny Schlegel, and Peter Protzel.  Vector semantic representations as descriptors for visual place recognition.  In Robotics: Science and Systems, 2021.
  * [39] Philipp Oberdiek, Matthias Rottmann, and Gernot A. Fink.  Detection and retrieval of out-of-distribution objects in semantic segmentation.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 1331–1340, 2020.
  * [40] Nicolas Papernot and Patrick D. McDaniel.  Deep k-nearest neighbors: Towards confident, interpretable and robust deep learning.  arXiv preprint arXiv:1803.04765, 2018.
  * [41] Tony Plate.  A common framework for distributed representation schemes for compositional structure.  In Connectionist Systems for Knowledge Representation and Deduction, pages 15–34, 1997.
  * [42] Janis Postels, Hermann Blum, Cesar Cadena, Roland Siegwart, Luc Van Gool, and Federico Tombari.  Quantifying aleatoric and epistemic uncertainty using density estimation in latent space.  arXiv preprint arXiv:2012.03082, 2020.
  * [43] Abbas Rahimi, Pentti Kanerva, and Jan M. Rabaey.  A robust and energy-efficient classifier using brain-inspired hyperdimensional computing.  In International Symposium on Low Power Electronics and Design, page 64–69, 2016.
  * [44] Quazi Marufur Rahman, Niko Sünderhauf, and Feras Dayoub.  Online monitoring of object detection performance post-deployment.  arXiv preprint arXiv:2011.07750, 2020.
  * [45] Quazi Marufur Rahman, Niko Sünderhauf, and Feras Dayoub.  Did you miss the sign? A false negative alarm system for traffic sign detectors.  In IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3748–3753, 2019.
  * [46] Jie Ren, Stanislav Fort, Jeremiah Liu, Abhijit Guha Roy, Shreyas Padhy, and Balaji Lakshminarayanan.  A simple fix to mahalanobis distance for improving near-OOD detection.  arXiv preprint arXiv:2106.09022, 2021.
  * [47] Amir Rosenfeld, Richard S. Zemel, and John K. Tsotsos.  The elephant in the room.  CoRR, abs/1808.03305, 2018.
  * [48] Chandramouli Shama Sastry and Sageev Oore.  Detecting out-of-distribution examples with Gram matrices.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8491–8501. PMLR, 13–18 Jul 2020\.
  * [49] Andrew M. Saxe, James L. McClelland, and Surya Ganguli.  Exact solutions to the nonlinear dynamics of learning in deep linear neural networks.  In International Conference on Learning Representations, 2014.
  * [50] Kenny Schlegel, Peer Neubert, and Peter Protzel.  A comparison of vector symbolic architectures.  Artificial Intelligence Review, pages 1–33, 2021.
  * [51] Paul Smolensky.  Tensor product variable binding and the representation of symbolic structures in connectionist systems.  Artificial Intelligence, 46(1):159–216, 1990.
  * [52] Niko Sünderhauf, Oliver Brock, Walter Scheirer, Raia Hadsell, Dieter Fox, Jürgen Leitner, Ben Upcroft, Pieter Abbeel, Wolfram Burgard, Michael Milford, et al.  The limits and potentials of deep learning for robotics.  The International Journal of Robotics Research, 37(4-5):405–420, 2018.
  * [53] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [54] Fisher Yu, Yinda Zhang, Shuran Song, Ari Seff, and Jianxiong Xiao.  LSUN: Construction of a large-scale image dataset using deep learning with humans in the loop.  arXiv preprint arXiv:1506.03365, 2015.
  * [55] Qing Yu and Kiyoharu Aizawa.  Unsupervised out-of-distribution detection by maximum classifier discrepancy.  In IEEE/CVF International Conference on Computer Vision, pages 9518–9526, 2019.
  * [56] Alireza Zaeemzadeh, Niccolo Bisagno, Zeno Sambugaro, Nicola Conci, Nazanin Rahnavard, and Mubarak Shah.  Out-of-distribution detection using union of 1-dimensional subspaces.  In IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 9452–9461, 2021.
  * [57] Sergey Zagoruyko and Nikos Komodakis.  Wide residual networks.  In British Machine Vision Conference, pages 87.1–87.12, 2016.
  * [58] Arthur Zimek, Erich Schubert, and Hans-Peter Kriegel.  A survey on unsupervised outlier detection in high-dimensional numerical data.  Statistical Analysis and Data Mining, 5(5):363–387, 2012.