# A Tight Threshold Bound for Search Trees with 2-way Comparisons††thanks:
Research supported by NSF grant CCF-2153723.

Sunny Atalig  University of California at Riverside, USA  Marek Chrobak
University of California at Riverside, USA

###### Abstract

We study search trees with 2-way comparisons (2wcst’s), which involve separate
less-than and equal-to tests in their nodes, each test having two possible
outcomes, yes and no. These trees have a much subtler structure than standard
search trees with 3-way comparisons (3wcst’s) and are still not well
understood, hampering progress towards designing an efficient algorithm for
computing minimum-cost trees. One question that attracted attention in the
past is whether there is an easy way to determine which type of comparison
should be applied at any step of the search. Anderson, Kannan, Karloff and
Ladner studied this in terms of the ratio between the maximum and total key
weight, and defined two threshold values: $\lambda^{-}$ is the largest ratio
that forces the less-than test, and $\lambda^{+}$ is the smallest ratio that
forces the equal-to test. They determined that $\lambda^{-}=\tfrac{1}{4}$, but
for the higher threshold they only showed that
$\lambda^{+}\in[\tfrac{3}{7},\tfrac{4}{9}]$. We give the tight bound for the
higher threshold, by proving that in fact $\lambda^{+}=\tfrac{3}{7}$.

##  1 Introduction

Search trees are decision-tree based data structures used for identifying a
query value within some specified set $\mathcal{K}$ of keys, by applying some
simple tests on the query. When $\mathcal{K}$ is a linearly ordered set, these
tests can be comparisons between the query and a key from $\mathcal{K}$. In
the classical model of 3-way comparison trees (3wcst’s), each comparison has
three outcomes: the query can be smaller, equal, or greater than the key
associated with this node. In the less studied model of search trees with
2-way comparisons (2wcst’s), proposed by Knuth [7, §6.2.2, Example 33], we
have separate less-than and equal-to tests, with each test having two
outcomes, yes or no. In both models, the search starts at the root node of the
tree and proceeds down the tree, following the branches corresponding to these
outcomes, until the query ends up in the leaf representing the key equal to
the query value 111Here we assume the scenario when the query is in
$\mathcal{K}$, often called the _successful-query_ model. If arbitrary queries
are allowed, the tree also needs to have leaves representing inter-key
intervals. Algorithms for the successful-query model typically extend
naturally to this general mode without increasing their running time..

The focus of this paper is on the static scenario, when the key set
$\mathcal{K}$ does not change over time222There is of course vast amount of
research on the dynamic case, when the goal is to have the tree to adapt to
the input sequence, but it is not relevant to this paper.. Each key $k$ is
assigned a non-negative weight $w_{k}$, representing the frequency of $k$, or
the probability of it appearing on input. Given these weights, the objective
is to compute a tree $T$ that minimizes its cost, defined by
$\operatorname{cost}(T)=\sum_{k\in\mathcal{K}}w_{k}\cdot\operatorname{depth}(k)$,
where $\operatorname{depth}(k)$ is the depth of the leaf representing key $k$
in $T$. This concept naturally captures the expected cost of a random query.

Figure 1:  An example of a 2wcst. This tree handles keys 1, 2, 3, 4, 5, 6, 7,
8 with respective weights 8, 3, 4, 3, 2, 9, 8, 7. Computing the cost in terms
of leaves, we get $8\cdot 2+3\cdot 4+4\cdot 4+3\cdot 4+2\cdot 4+9\cdot
2+8\cdot 3+7\cdot 3=127$.

Optimal 3wcst’s can be computed in time $O(n^{3})$ using the now standard
dynamic programming algorithm. As shown already by Knuth [6] in 1971 and later
by Yao [10] in 1980, using a more general approach, the running time can be
improved to $O(n^{2})$. This improvement leverages the property of 3wcst’s
called the quadrangle inequality (which is essentially equivalent to the so-
called Monge property or total monotonicity — see [3]). In contrast, the first
(correct333Anderson et al. [1] reference an earlier $O(n^{5})$-time algorithm
by Spuler [8, 9]. However, as shown in [5], Spuler’s proof is not correct. )
polynomial-time algorithm for finding optimal 2wcst’s was developed only in
2002 by Anderson, Kannan, Karloff and Ladner [1]. Its running time is
$O(n^{4})$. A simpler and slightly more general $O(n^{4})$-time algorithm was
recently given in [4].

The reason for this disparity in the running times lies in the internal
structure of 2wcst’s, which is much more intricate than that of 3wcst’s.
Roughly, while the optimal cost function of 3wcst’s has a dynamic-programming
formulation where all sub-problems are represented by key intervals, this is
not the case for 2wcst’s. For 2wcst’s, a similar approach produces intervals
with holes (corresponding to earlier failed equal-to tests), leading to
exponentially many sub-problems. As shown in [1] (and conjectured earlier by
Spuler [8, 9]), this can be reduced to $O(n^{3})$ sub-problems using the so-
called heaviest-first key property.

One other challenge in designing a faster algorithm is that, for any sub-
problem, it is not known a priori whether the root should use the less-than
test or the equal-to test. The intuition is that when some key is sufficiently
heavy then the optimum tree must start with the equal-to test (to this key) at
the root. On the other hand, if all weights are roughly equal (and there are
sufficiently many keys), then the tree should start with a less-than test, to
break the instance into two parts with roughly the same total weight.
Addressing this, Anderson et al. [1] introduced two threshold values for the
maximum key weight. Denoting by $W$ the total weight of the keys in the
instance, these values are defined as follows:

  * •

$\lambda^{-}$ is the largest $\lambda$ such that if all key weights are
smaller than $\lambda W$ then there is no optimal tree with an equal-to test
at the root.

  * •

$\lambda^{+}$ is the smallest $\lambda$ such that if any key has weight at
least $\lambda W$ then there is an optimal tree with an equal-to test at the
root.

In their paper444In [1] the notation for the threshold values $\lambda^{-}$
and $\lambda^{+}$ was, respectively, $\lambda$ and $\mu$. We changed the
notation to make it more intuitive and consistent with [2]., they proved that
$\lambda^{-}=\tfrac{1}{4}$ and $\lambda^{+}\in[\tfrac{3}{7},\tfrac{4}{9}]$.
These thresholds played a role in their $O(n^{4})$-time algorithm for
computing optimal 2wcst’s. The more recent $O(n^{4})$-time algorithm in [4]
uses a somewhat different approach and does not rely on any threshold bounds
on key weights.

Nevertheless, breaking the $O(n^{4})$ barrier will require deeper
understanding of the structure of optimal 2wcst’s; in particular, more
accurate criteria for determining which of the two tests should be applied
first are likely to be useful. Even if not improving the asymptotic
complexity, such criteria reduce computational overhead by limiting the number
of keys to be considered for less-than tests.

With these motivations in mind, in this work we give a tight bound on the
higher weight threshold, by proving that the lower bound of $\tfrac{3}{7}$ for
$\lambda^{+}$ in [1] is in fact tight.

######  Theorem 1.1.

For all $n\geq 2$, if an instance of $n$ keys has total weight $W$ and a
maximum key weight at least $\tfrac{3}{7}W$ then there exists an optimal 2wcst
rooted at an equal-to test. In other words, $\lambda^{+}\leq\tfrac{3}{7}$.

The proof is given in Section 3, after we introduce the necessary definitions
and notation, and review fundamental properties of 2wcst’s, in Section 2.

_Note:_ For interested readers, other structural properties of 2wcst’s were
recently studied in the companion paper [2]. In particular, that paper
provides other types of threshold bounds, including one that involves two
heaviest keys, as well as examples showing that the speed-up techniques for
dynamic programming, including the quadrangle inequality, do not work for
2wcst’s.

##  2 Preliminaries

### Notation.

Without any loss of generality we can assume that set of keys is
$\mathcal{K}={\left\\{{1,2,...,n}\right\\}}$, and their corresponding weights
are denoted $w_{1},w_{2},\ldots,w_{n}$. Throughout the paper, we will
typically use letters $i,j,k,...$ to represent keys. The total weight of the
instance is denoted by $W=\sum_{k\in\mathcal{K}}w_{k}$. For a tree $T$ by
$w{\left({T}\right)}$ we denote the total weight of keys in its leaves,
calling it the _weight of $T$_. For a node $v$ in $T$, $w{\left({v}\right)}$
denotes the weight of the sub-tree of $T$ rooted at $v$.

Each internal node is either an equal-to test to a key $k$, denoted by
${\langle{=k}\rangle}$, or a less-than test to $k$, denoted by
${\langle{<k}\rangle}$. Conventionally, the left and right branches of the
tree at a node are labelled by “yes” and “no” outcomes, but in our proof we
will often depart from this notation and use relation symbols “$=$”, “$\neq$”,
“$<$”, etc, instead. For some nodes only the comparison key $k$ will be
specified, but not the test type. Such nodes will be denoted
${\langle{\mathrel{\ast}k}\rangle}$, and their outcome branches will be
labeled “$=\\!\\!/\\!\\!\geq$” and “$\neq\\!\\!/\\!\\!<$”. The interpretation
of these is natural: If ${\langle{\mathrel{\ast}k}\rangle}$ is
${\langle{=k}\rangle}$ then the first branch is taken on they “yes” answer,
otherwise the second branch is taken. If ${\langle{\mathrel{\ast}k}\rangle}$
is ${\langle{<k}\rangle}$ then the second branch is taken on the “yes” answer
and otherwise the first branch is taken. This convention will be very useful
in reducing the case complexity.

A branch of a node is called _redundant_ if there is no query value
$q\in\mathcal{K}$ that traverses this branch during search. A 2wcst $T$ is
called _irreducible_ if it does not contain any redundant branches. Each tree
can be converted into an irreducible tree by “splicing out” redundant branches
(linking the sibling branch drectly to the grandparent). This does not
increase cost. So throughout the paper we tacitly assume that any given tree
is irreducible. In particular, note that any key $k$ appearing in a node
${\langle{\mathrel{\ast}k}\rangle}$ of an irreducible tree must satisfy all
outcomes of the tests on the path from the root to
${\langle{\mathrel{\ast}k}\rangle}$. (The only non-trivial case is when
${\langle{\mathrel{\ast}k}\rangle}$ is ${\langle{<k}\rangle}$ and there is a
node ${\langle{=k}\rangle}$ along this path. In this case,
${\langle{<k}\rangle}$ can be replaced by ${\langle{<k+1}\rangle}$, as in this
case $k$ cannot be $n$ if $T$ is irreducible.)

### Side weights.

We use some concepts and auxiliary lemmas developed by Anderson et al. [1]. In
particular, the concept of side-weights is useful. The _side-weight_ of a node
$v$ in a 2wcst $T$ is defined by

$\textit{sw}{\left({v}\right)}=\begin{cases}0&\text{if }v\text{ is a leaf}\\\
w_{k}&\text{if }v\text{ is an equal-to test ${\langle{=k}\rangle}$ }\\\
\min{\left\\{{w{\left({L}\right)},w{\left({R}\right)}}\right\\}}&\text{if
}v\text{ is a less-than test with sub-trees }L,R\end{cases}$

######  Lemma 2.1.

_[1]_ Let $T$ be an optimal 2wcst. Then
$\textit{sw}{\left({u}\right)}\geq\textit{sw}{\left({v}\right)}$ if $u$ is a
parent of $v$.

The lemma, while far from obvious, can be proved by applying so-called
“rotations” to the tree, which are local rearrangements that swap some
adjacent nodes. As a simple example, if $u={\langle{=k}\rangle}$ is a child of
$v={\langle{=l}\rangle}$ and $sw(u)>sw(v)$ then exchanging these two
comparisons would reduce the tree cost, contradicting optimality. For the
complete proof, see [1].

Lemma 2.1 implies immediately the following:

######  Lemma 2.2.

_[1]_ For $n>2$, if an optimal 2wcst for an instance of $n$ keys is rooted at
an equal-to test on $i$, then $i$ is a key of maximum-weight.

We remark that in case of ties between maximum-weight keys a subtlety arises
that led to some complications in the algorithm in [1]. It was shown later in
[4] that this issue can be circumvented. This issue does not arise in our
paper, and the above statement of Lemma 2.2 is sufficient for our argument.

### More about rotations.

We will extend the concept of rotations to involve nodes of the form
${\langle{\mathrel{\ast}k}\rangle}$, with unspecified tests. This makes the
rotations somewhat non-trivial, since such nodes represent two different
possible subtrees, and we need to justify that the tree obtained from the
rotation is correct in both cases.

$\boldsymbol{\Longrightarrow}$

Figure 2: A tree rotation using general queries.

$\boldsymbol{\Longrightarrow}$

(a) Valid if tree is irreducible.

$\boldsymbol{\Longrightarrow}$

(b) Valid if $a<b$ or
${\langle{\mathrel{\ast}b}\rangle}={\langle{=b}\rangle}$.

Figure 3: Rotating a node with double outcomes.

To give a simple condition for ensuring valid rotations, we generalize 2wcsts
by considering arbitrary types of tests, not merely equal-to or less-than
tests. Any binary test can be identified by the set of keys that satisfy the
“yes” outcome. We can thus represent such a test using the set element
relation, denoted ${\langle{\in A}\rangle}$, with branches labelled “$\in$”
and “$\notin$”. An equal-to test ${\langle{=k}\rangle}$ can be identified by
the singleton set ${\left\\{{k}\right\\}}$ or its complement
${\mathcal{K}}-{\left\\{{k}\right\\}}$, and a less-than test
${\langle{<k}\rangle}$ can be identified by ${\left({-\infty,k}\right)}$ or
$[k,\infty)$.

Consider the rotation in Figure 2, where we denote the sub-trees and the keys
they contain by $X$, $Y$, and $Z$. Comparing the trees on the left and the
right, we must have $X=A\cap B=B$, which implies that for the rotation to be
correct we need $B\subseteq A$. (If the tree on the left is irreducible, the
containment must in fact be strict.) On the other hand, if $B\subseteq A$ then
in both trees we have $Y=A\setminus B$ and $Z=\mathcal{K}-A$. This gives us
the following property:

Containment Property: The rotation shown in Figure 2 is valid if and only if
$B\subseteq A$.

We remark that other rotations, such as when ${\langle{\in B}\rangle}$ is in
the $\notin$-branch of ${\langle{\in A}\rangle}$, can be accounted for by the
above containment property, by replacing ${\langle{\in A}\rangle}$ with
${\langle{\in{\bar{A}}}\rangle}$, where ${\bar{A}}$ is the complement of $A$.

Consider Figure 3(a), with tests ${\langle{<a}\rangle}$ and
${\langle{\mathrel{\ast}b}\rangle}$. Assuming the original tree is
irreducible, we have $b\geq a$, with strict inequality if
${\langle{\mathrel{\ast}b}\rangle}$ is a less-than test. We identify
${\langle{<a}\rangle}$ with set $A=[a,\infty)$ and
${\langle{\mathrel{\ast}b}\rangle}$ with $B={\left\\{{b}\right\\}}$ or
$[b,\infty)$ (second option corresponds to ${\langle{<b}\rangle}$). Then by
our inequalities, it is clear that $B\subset A$ and the rotation is valid. By
a similar reasoning, the rotation shown in Figure 3(b) is also valid, assuming
either $a<b$ or ${\langle{\mathrel{\ast}b}\rangle}$ is an equal-to test. For
proving Theorem 1.1, we need only consider these two rotations (or the
corresponding reverse rotations).

Not all tree modifications in our proof are rotations. Some modifications also
_insert_ a new comparison test into the tree. This modification has the effect
of making a tree reducible, though it can be converted into a irreducible
tree, as explained earlier in this section. Insertions are used by Anderson et
al. [1] in proving the tight bound for $\lambda^{-}$ and will also be used in
proving Theorem 1.1

##  3 Proof of Theorem 1.1

In this section we prove Theorem 1.1, namely that the lower bound of
$\tfrac{3}{7}$ on $\lambda^{+}$ in [1] is tight.

Before proceeding with the proof, we remind the reader that
${\langle{\mathrel{\ast}k}\rangle}$ denotes an unspecified comparison test on
key $k$, and that its outcomes are specified with labels“$=\\!\\!/\\!\\!\geq$”
and “$\neq\\!\\!/\\!\\!<$”.

The proof is by induction on the number of nodes $n$. The cases $n=2,3$ are
trivial so we’ll move on to the inductive step. Assume that $n\geq 4$ and that
Theorem 1.1 holds for all instances where the number of keys is in the range
${\left\\{{2,\ldots,n-1}\right\\}}$.

To show that the theorem holds for any $n$-key instance, consider a tree $T$
for an instance with $n$ keys and whose maximum-weight key $m$ satisfies
$w_{m}\geq\tfrac{3}{7}w{\left({T}\right)}$, and suppose that the root of $T$
is a less-than test ${\langle{<r}\rangle}$. We show that we can then find
another tree $T^{\prime}$ that is rooted at an equal-to test node and has cost
not larger than $T$.

If $r\in{\left\\{{2,n}\right\\}}$, then one of the children of
${\langle{<r}\rangle}$ is a leaf, and we can simply replace
${\langle{<r}\rangle}$ by an appropriate equal-to test. So we can assume that
$2<r\leq n-1$, in which case each sub-tree of ${\langle{<r}\rangle}$ must have
between $2$ and $n-1$ nodes. By symmetry, we also can assume that a heaviest-
weight key $m$ is in the left sub-tree $L$ of ${\langle{<r}\rangle}$. Since
$w_{m}\geq\tfrac{3}{7}w{\left({T}\right)}\geq\tfrac{3}{7}w{\left({L}\right)}$,
we can replace $L$ with a tree rooted at ${\langle{=m}\rangle}$ without
increasing cost, by our inductive assumption. (A careful reader might notice
that, if a tie arises, the inductive assumption only guarantees that the root
of this left subtree will be an equal-to test to a key of the same weight as
$m$. For simplicity, we assume that this key is $m$, for otherwise we can just
use the other key in the rest of the proof.) Let $T_{1}$ be the $\neq$-branch
of ${\langle{=m}\rangle}$ and $T_{2}$ be the $\geq$-branch of
${\langle{<r}\rangle}$.

By applying Lemma 2.1 to node ${\langle{=m}\rangle}$ and its parent
${\langle{<r}\rangle}$, we have that $w{\left({T_{2}}\right)}\geq
w_{m}\geq\tfrac{3}{7}w{\left({T}\right)}$, which in turn implies that
$w{\left({T_{1}}\right)}\leq\tfrac{1}{7}w{\left({T}\right)}$. Since $T_{2}$ is
not a leaf, let its root be ${\langle{\mathrel{\ast}i}\rangle}$ with sub-trees
$T_{3}$ and $T_{4}$, where $T_{3}$ is the $=\\!\\!/\\!\\!\geq$-branch. The
structure of $T$ is illustrated in Figure 4(a).

(a) Original tree $T$

(b) Modified tree $T^{\prime}$

Figure 4: On the left, tree $T$ in the proof of Theorem 1.1. On the right, the
modification for Case 3. Notice that $T_{3}$ is either the leaf $i$ or
contains all keys greater than or equal to $i$, depending on the comparison
test ${\langle{\mathrel{\ast}i}\rangle}$.

To modify the tree, we break into two cases based on $T_{3}$’s weight:

### Case 1:

$w{\left({T_{3}}\right)}\geq\tfrac{1}{3}w{\left({T_{2}}\right)}$. To obtain
$T^{\prime}$, rotate ${\langle{=m}\rangle}$ to the root of the tree, then
rotate ${\langle{\mathrel{\ast}i}\rangle}$ so that it is the ${\neq}$-branch
of ${\langle{=m}\rangle}$. (The irreducibility of $T$ implies that the
Containment Property in Section 2 holds for both rotations.) Node $m$ goes up
by $1$ in depth and subtrees $T_{1}$ and $T_{4}$ both go down by $1$ (see
Figure 4(b)). So the total change in cost is

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle=\;w{\left({T_{1}}\right)}+w{\left({T_{4}}\right)}-w_{m}$
$\displaystyle=\;w{\left({T}\right)}-2w_{m}-w{\left({T_{3}}\right)}$
$\displaystyle
w_{m}+w{\left({T_{1}}\right)}+w{\left({T_{3}}\right)}+w{\left({T_{4}}\right)}=w{\left({T}\right)}$
$\displaystyle\leq\;w{\left({T}\right)}-2w_{m}-\tfrac{1}{3}w_{m}$
$\displaystyle
w{\left({T_{3}}\right)}\geq\tfrac{1}{3}w{\left({T_{2}}\right)},w{\left({T_{2}}\right)}\geq
w_{m}$ $\displaystyle=\;w{\left({T}\right)}-\tfrac{7}{3}w_{m}$
$\displaystyle\leq\;0$ $\displaystyle
w_{m}\geq\tfrac{3}{7}w{\left({T}\right)}$

### Case 2:

$w{\left({T_{3}}\right)}<\tfrac{1}{3}w{\left({T_{2}}\right)}$. Note that in
this case, $w{\left({T_{4}}\right)}>\frac{2}{3}w{\left({T_{2}}\right)}$. We’ll
first handle some trivial cases. If $T_{4}$ is a leaf $j$, we can replace
${\langle{\mathrel{\ast}i}\rangle}$ with ${\langle{=j}\rangle}$ and do the
same rotations as in Case 3 (swapping the roles of $T_{4}$ and $T_{3}$). If
$T_{4}$ contains only two leaves, say $k$ and $j$, applying Lemma 2.1 we
obtain that $w_{k},w_{j}\leq w{\left({T_{3}}\right)}$, which in turn implies
that $w{\left({T_{2}}\right)}\leq
3w{\left({T_{3}}\right)}<w{\left({T_{2}}\right)}$ — a contradiction.

Therefore, we can assume that $T_{4}$ contains at least 3 leaves and at least
2 comparison nodes. Let ${\langle{\mathrel{\ast}j}\rangle}$ be the test in the
root of $T_{4}$. If ${\langle{\mathrel{\ast}j}\rangle}$ is a less-than test
and any of its branches is a leaf, we can replace
${\langle{\mathrel{\ast}j}\rangle}$ with an equal-to test. If
${\langle{\mathrel{\ast}j}\rangle}$ is an equal-to test than its $\neq$-branch
is not a leaf (because $T_{4}$ has at least 3 leaves). Thus we can assume that
the $\neq\\!\\!/\\!\\!<$-branch of ${\langle{\mathrel{\ast}j}\rangle}$ is not
a leaf, and let ${\langle{\mathrel{\ast}k}\rangle}$ be the root of this
branch. This means that both ${\langle{\mathrel{\ast}j}\rangle}$ and
${\langle{\mathrel{\ast}k}\rangle}$ follow from an
$\neq\\!\\!/\\!\\!<$-outcome. Let $T_{5}$ be the $=\\!\\!/\\!\\!\geq$-branch
of ${\langle{\mathrel{\ast}j}\rangle}$ and $T_{6}$ and $T_{7}$ be the branches
of ${\langle{\mathrel{\ast}k}\rangle}$. The structure of $T$ is shown in
Figure 6a.

This idea behind the remainng argument is this: We now have that $T_{5}$,
$T_{6}$ and $T_{7}$ together are relatively heavy (because $T_{4}$ is), while
$T_{1}$ and $T_{3}$, which are at lower depth, are light. If this weight
difference is sufficiently large, it should be thus possible to rebalance the
tree and reduce the cost. We will accomplish this rebalancing by using keys
$i,j$ and $k$, although it may require introducing a new less-than test to one
of these keys.

For convenience, re-label the keys
${\left\\{{i,j,k}\right\\}}={\left\\{{b_{1},b_{2},b_{3}}\right\\}}$ such that
$b_{1}\leq b_{2}\leq b_{3}$. The goal is to use ${\langle{<b_{2}}\rangle}$ as
a “central” cut-point to divide the tree, with ${\langle{<r}\rangle}$ and
${\langle{\mathrel{\ast}b_{1}}\rangle}$ in its $<$-branch. The $\geq$-branch
will contain ${\langle{\mathrel{\ast}b_{3}}\rangle}$ and, if
${\langle{\mathrel{\ast}b_{2}}\rangle}$ is an equal-to test, also
${\langle{\mathrel{\ast}b_{2}}\rangle}$.

$\boldsymbol{\Longrightarrow}$

Figure 5: An example conversion of $T$ (on the left) into $T^{\prime}$ (on the
right) in Case 3, where $k<j<i$. $T^{\prime}_{7}$ and $T^{\prime\prime}_{7}$
are copies of $T_{7}$.

The idea is illustrated by the example in Figure 5. In tree $T^{\prime}$ we
have two copies of $T_{7}$, denoted $T^{\prime}_{7}$ and
$T^{\prime\prime}_{7}$. (Because of this $T^{\prime}$ is not irreducible. As
explained in Section 2, $T^{\prime}$ can be then converted into an irreducible
tree by splicing out redundant branches.) These copies are needed because the
range of $T_{7}$ is partitioned by the ${\langle{<j}\rangle}$ test into two
subsets, with query keys smaller than $j$ following the $<$-branch and the
other following the $\geq$-branch. We refer to this in text later as
“fracturing” of $T_{7}$. However, since these subsets form a disjoint
partition of the range of $T_{7}$, the total contribution of $T^{\prime}_{7}$
and $T^{\prime\prime}_{7}$ to the cost of $T^{\prime}$ is the same as the
contribution of $T_{7}$ to the cost of $T$. More generally, such fracturing
does not affect the cost as long as the fractured copies of a subtree are at
the same depth as the original subtree.

Ultimately, using the case assumption that
$w{\left({T_{3}}\right)}<\tfrac{1}{3}w{\left({T_{2}}\right)}$, we want to show
the following:

######  Claim 3.1.

There exists a tree $T^{\prime}$ such that

$\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;\leq\;w{\left({T_{1}}\right)}-w_{m}+2w{\left({T_{3}}\right)}.$

In other words, we want to show that in the worst case scenario, we have a
modified tree whose cost is at worst equivalent to moving key $m$ up by one,
$T_{1}$ down by one, and $T_{3}$ down by 2. This suffices to prove Case 3 as
then

$\displaystyle\operatorname{cost}(T^{\prime})-\operatorname{cost}(T)\;$
$\displaystyle\leq\;w{\left({T_{1}}\right)}-w_{m}+2w{\left({T_{3}}\right)}$
$\displaystyle=\;w{\left({T}\right)}-2w_{m}+w{\left({T_{3}}\right)}-w{\left({T_{4}}\right)}$
$\displaystyle
w_{m}+w{\left({T_{1}}\right)}+w{\left({T_{3}}\right)}+w{\left({T_{4}}\right)}=w{\left({T}\right)}$
$\displaystyle\leq\;w{\left({T}\right)}-2w_{m}+\tfrac{1}{3}w{\left({T_{2}}\right)}-\tfrac{2}{3}w{\left({T_{2}}\right)}$
$\displaystyle
w{\left({T_{3}}\right)}<\tfrac{1}{3}w{\left({T_{2}}\right)},w{\left({T_{4}}\right)}>\tfrac{2}{3}w{\left({T_{2}}\right)}$
$\displaystyle=\;w{\left({T}\right)}-2w_{m}-\tfrac{1}{3}w{\left({T_{2}}\right)}$
$\displaystyle\leq\;w{\left({T}\right)}-2w_{m}-\tfrac{1}{3}w_{m}$
$\displaystyle w{\left({T_{2}}\right)}\geq w_{m}$ $\displaystyle\leq\;0$

Before describing the construction of $T^{\prime}$, we’ll first establish
Claim 3.2 below.

######  Claim 3.2.

$r<b_{2}$ (so that ${\langle{<r}\rangle}$ and ${\langle{<b_{2}}\rangle}$ are
distinct tests).

Because keys $i$, $j$, and $k$ are in the ${\geq}$-branch of
${\langle{<r}\rangle}$, we have that $r\leq b_{1},b_{2},b_{3}$. As any
irreducible tree can perform at most two tests on the same key, if $b_{i}=r$
then $b_{i}$ is distinct from the other two keys. Then $b_{i}=b_{1}$ must hold
to preserve order, and thus $b_{2}>b_{1}=r$. This proves Claim 3.2.

The modified tree $T^{\prime}$ then has the following form:
${\langle{=m}\rangle}$ is at the root, ${\langle{<b_{2}}\rangle}$ is at the
${\neq}$-branch of ${\langle{=m}\rangle}$, and ${\langle{<r}\rangle}$ is at
the ${<}$-branch of ${\langle{<b_{2}}\rangle}$. Notably, $T_{1}$ will still be
in the $<$-branch of ${\langle{<r}\rangle}$ in $T^{\prime}$, which implies
that $m$ moves up by 1 and $T_{1}$ moves down by 1, thus matching the
$w{\left({T_{1}}\right)}-w_{m}$ terms in Claim 3.1. The right branch of
${\langle{<r}\rangle}$ leads to ${\langle{\mathrel{\ast}b_{1}}\rangle}$. The
rest of $T^{\prime}$ will be designed so that all subtrees $T_{3}$, $T_{5}$,
$T_{6}$ and $T_{7}$ will have roots at depth at most $4$, so in particular
$T_{6}$ and $T_{7}$ will never move down.

Then it suffices to show that the new depths of $T_{3}$ and $T_{5}$ imply a
cost increase no greater than $2w{\left({T_{3}}\right)}$. More precisely, we
will show that $T^{\prime}$ has one of the following properties: Compared to
$T$, in $T^{\prime}$

  1. (j1)

$T_{3}$ moves down by at most $2$ and $T_{5}$’s depth doesn’t change, _or_

  2. (j2)

If ${\langle{\mathrel{\ast}j}\rangle}$ is an equal-to test then $T_{5}$ and
$T_{3}$ move down at most by $1$ each. (This suffices because
$w{\left({T_{5}}\right)}=w_{j}\leq w{\left({T_{3}}\right)}$ if
${\langle{\mathrel{\ast}j}\rangle}$ is an equal-to test, by applying Lemma 2.1
to $T$.)

To describe the rest of our modification, we break into two sub-cases,
depending on whether ${\langle{\mathrel{\ast}b_{2}}\rangle}$ is and equal-to
test or less-than test.

### Case 2.1:

${\langle{\mathrel{\ast}b_{2}}\rangle}={\langle{<b_{2}}\rangle}$. In this
case, ${\langle{\mathrel{\ast}b_{3}}\rangle}$ is at the $\geq$-branch of
${\langle{<b_{2}}\rangle}$ in $T^{\prime}$. We do not introduce any new
comparison tests, obtaining $T^{\prime}$ shown in Figure 6(b). We now break
into further cases based on which key $b_{2}$ is.

First, we observe that $b_{2}\neq i$, as for $b_{2}=i$ the structure of $T$
would imply that $j,k<i$, meaning that $i$ would be the largest key, instead
of the middle one. Thus, $b_{2}\in{\left\\{{j,k}\right\\}}$. This gives us two
sub-cases.

Case 2.1.1: $b_{2}=j$. Then we have $k<j$ by the structure of $T$, implying
$k=b_{1}$, and $i\geq j$ since $i$ must now be $b_{3}$. Then, in $T^{\prime}$,
${\langle{\mathrel{\ast}b_{1}}\rangle}$ has branches $T_{6}$ and $T_{7}$,
while ${\langle{\mathrel{\ast}b_{3}}\rangle}$ has branches $T_{3}$
($=\\!\\!/\\!\\!\geq$-branch) and $T_{5}$ ($\neq\\!\\!/\\!\\!<$-branch). In
which case, only $T_{3}$ moves down by 1, satisfying (j1).

Case 2.1.2: $b_{2}=k$. Then the structure of $T$ implies that
$k\neq{\left\\{{i,j}\right\\}}$, so $b_{1}<k$, which in turn implies that
${\langle{\mathrel{\ast}b_{1}}\rangle}$ is an equal-to test. We now have two
further sub-cases. If $(i,j)=(b_{1},b_{3})$ then, in $T^{\prime}$, $T_{5}$ is
in the $=\\!\\!/\\!\\!\geq$-branch of ${\langle{\mathrel{\ast}b_{3}}\rangle}$
and leaf $T_{3}=i$ is in the $=\\!\\!/\\!\\!\geq$-branch of
${\langle{\mathrel{\ast}b_{1}}\rangle}$, implying $T_{5}$’s depth doesn’t
change and $T_{3}$ moves down by 2, satisfying (j1). If $j=b_{1}$, then leaf
$T_{5}=j$ is below ${\langle{\mathrel{\ast}b_{1}}\rangle}$ and $T_{3}$ is
below ${\langle{\mathrel{\ast}b_{3}}\rangle}$, both moving down by 1,
satisfying (j2).

(a) Original tree $T$

(b) Modified tree $T^{\prime}$

Figure 6: Original and modified tree for Case 3. $S_{1},S_{2},S_{3},S_{4}$ is
simply some permutation of $T_{3},T_{5},T_{6},T_{7}$.

(a) Original tree $T$

(b) Modified tree $T^{\prime}$, ${\langle{=b_{2}}\rangle}$ goes first

(c) Modified tree $T^{\prime}$, ${\langle{\mathrel{\ast}b_{3}}\rangle}$ goes
first

Figure 7: Original and modified tree for Case 3. In this case, $T_{5}=b_{2}$,
and $S_{1},S_{2},S_{3},S_{4}$ is some permutation of
$T_{3},T_{6},T_{7},T^{\prime\prime}$, where $T^{\prime\prime}$ is a copy of
$T_{6}$ or $T_{7}$.

### Case 2.2:

${\langle{\mathrel{\ast}b_{2}}\rangle}={\langle{=b_{2}}\rangle}$ and both
tests ${\langle{\mathrel{\ast}b_{1}}\rangle}$,
${\langle{\mathrel{\ast}b_{3}}\rangle}$ are different from
${\langle{<b_{2}}\rangle}$. In this case, ${\langle{<b_{2}}\rangle}$ (the
$\neq$-child of ${\langle{=m}\rangle}$ in $T^{\prime}$) is a newly introduced
test. In $T^{\prime}$, we will have ${\langle{=b_{2}}\rangle}$ and
${\langle{\mathrel{\ast}b_{3}}\rangle}$ in the $\geq$-branch of
${\langle{<b_{2}}\rangle}$. The order in which we perform
${\langle{=b_{2}}\rangle}$ and ${\langle{\mathrel{\ast}b_{3}}\rangle}$ will be
determined later.

We will say ${\langle{=b_{2}}\rangle}$ is “performed first” if it is the root
of the $\geq$-branch of ${\langle{<b_{2}}\rangle}$, in which case
${\langle{\mathrel{\ast}b_{3}}\rangle}$ is rooted at the $\neq$-branch of
${\langle{=b_{2}}\rangle}$, or “performed second”. Likewise if
${\langle{\mathrel{\ast}b_{3}}\rangle}$ is performed first, then
${\langle{=b_{2}}\rangle}$ is performed second, rooted at the
$\neq\\!\\!/\\!\\!<$-branch of ${\langle{\mathrel{\ast}b_{3}}\rangle}$. Figure
7 illustrates these two possible configurations. In most cases,
${\langle{=b_{2}}\rangle}$ and ${\langle{\mathrel{\ast}b_{3}}\rangle}$ are
performed in the same order as in the original tree $T$ (i.e.
${\langle{\mathrel{\ast}i}\rangle}$ comes before
${\langle{\mathrel{\ast}j}\rangle}$, which comes before
${\langle{\mathrel{\ast}k}\rangle}$), though one case (Case 2.2.2) requires
going out-of-order, implying a rotation.

Because ${\langle{<b_{2}}\rangle}$ is a new comparison, one of the sub-trees
$T_{3}$, $T_{5}$, $T_{6}$, $T_{7}$ in $T$ may fracture, meaning that some of
its keys may satisfy this comparison and other may not. We will in fact show
that only $T_{6}$ or $T_{7}$ can fracture, but their depths do not increase.
So, as explained earlier, this fracturing will not increase cost. (As also
explained before, the redundancies created by this fracturing, and other that
can occur as a result of the conversion, can be eliminated by post-processing
$T^{\prime}$ that iteratively splices out redundant branches.) We again break
into further cases based on which key $b_{2}$ is.

Case 2.2.1: $b_{2}=i$ and ${\langle{\mathrel{\ast}j}\rangle}$ is an equal-to
test. Then $T_{3}=i$ and $T_{5}=j$ are both leaves and can’t fracture. Perform
${\langle{=b_{2}}\rangle}$ first and ${\langle{\mathrel{\ast}b_{3}}\rangle}$
second (since $i=b_{2}$, this follows order of comparisons in the original
tree). Then $T_{3}$ and $T_{5}$ both move down by 1, satisfying (j2), with
$T_{3}=i=b_{2}$ in the $=$-branch of ${\langle{=b_{2}}\rangle}$ and $T_{5}=j$
in the $=$-branch of either ${\langle{\mathrel{\ast}b_{1}}\rangle}$ or
${\langle{\mathrel{\ast}b_{3}}\rangle}$ (depending on whether $j$ is $b_{1}$
or $b_{3}$).

Case 2.2.2: $b_{2}=i$ and ${\langle{\mathrel{\ast}j}\rangle}$ is a less-than
test. Then $k<j$, so $j=b_{3}$ and $k=b_{1}$. By the case assumption, we have
that $j>i$. Then in the $\geq$-branch of ${\langle{<b_{2}}\rangle}$, we
perform ${\langle{<j}\rangle}$ _before_ ${\langle{=i}\rangle}$ (going out-of-
order compared to the original tree), which will be in the $<$-branch of
${\langle{<j}\rangle}$. Then $T_{3}=i$ will be below ${\langle{=i}\rangle}$
moving down twice and $T_{5}$ will be in the $\geq$-branch of
${\langle{<j}\rangle}$ staying at the same depth, satisfying (j1).

Case 2.2.3: $b_{2}=j$. Then we may simply perform ${\langle{=b_{2}}\rangle}$
and ${\langle{\mathrel{\ast}b_{3}}\rangle}$ in the same order as in the
original tree. If ${\langle{\mathrel{\ast}i}\rangle}$ is an equal-to test,
then $T_{3}$ and $T_{5}$ are both leaves, and either both will go down by 1
(if $i=b_{3}$ and $k=b_{1}$), satisfying (j2), or only $T_{3}$ goes down by 2
(if $i=b_{1}$ and $k=b_{3}$), satisfying (j1). If
${\langle{\mathrel{\ast}i}\rangle}$ is a less-than test, then $j,k<i$, so
$k=b_{1}$ and $i=b_{3}$. ${\langle{<i}\rangle}$ will be performed first in the
$\geq$-branch of ${\langle{<b_{2}}\rangle}$ and $T_{3}$ will be in the
$\geq$-branch of ${\langle{<i}\rangle}$, implying $T_{3}$ and $T_{5}$ both go
down by 1, satisfying (j2).

Case 2.2.4: $b_{2}=k$. The analysis is similar to Case 2.1.2. By the structure
of $T$, $k\neq{\left\\{{i,j}\right\\}}$, so $b_{1}<k$, implying
${\langle{\mathrel{\ast}b_{1}}\rangle}$ is an equal-to test. Then perform
${\langle{=b_{2}}\rangle}$ and ${\langle{\mathrel{\ast}b_{3}}\rangle}$ in the
same order as the original tree (that is, ${\langle{=k}\rangle}$ is always
performed second). Thus ${\langle{\mathrel{\ast}b_{1}}\rangle}$ is in the
$\geq$-branch of ${\langle{<r}\rangle}$ and
${\langle{\mathrel{\ast}b_{3}}\rangle}$ is in the $\geq$-branch of
${\langle{<b_{2}}\rangle}$. If $(i,j)=(b_{1},b_{3})$, then $T_{3}$ (which is a
leaf $i$) is at the $=\\!\\!/\\!\\!\geq$-branch of
${\langle{\mathrel{\ast}b_{1}}\rangle}$ and $T_{5}$ is at the
$=\\!\\!/\\!\\!\geq$-branch of ${\langle{\mathrel{\ast}b_{3}}\rangle}$,
implying $T_{5}$’s depth stays the same and $T_{3}$ moves down by 2,
satisfying (j1). If $(i,j)=(b_{3},b_{1})$, then leaf $T_{5}=j$ is below
${\langle{\mathrel{\ast}b_{1}}\rangle}$ and $T_{3}$ is below
${\langle{\mathrel{\ast}b_{3}}\rangle}$, implying both trees move down by 1,
satisfying (j2).

## References

  * [1] R. Anderson, S. Kannan, H. Karloff, and R. E. Ladner.  Thresholds and optimal binary comparison search trees.  Journal of Algorithms, 44:338–358, 2002.
  * [2] Sunny Atalig, Marek Chrobak, Erfan Mousavian, Jiri Sgall, and Pavel Veselý.  Structural properties of search trees with 2-way comparisons.  CoRR, abs/2311.02224, 2023.
  * [3] Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, and Yan Zhang.  The Knuth-Yao quadrangle-inequality speedup is a consequence of total monotonicity.  ACM Trans. Algorithms, 6(1):17:1–17:22, 2009.
  * [4] Marek Chrobak, Mordecai Golin, J. Ian Munro, and Neal E. Young.  A simple algorithm for optimal search trees with two-way comparisons.  ACM Trans. Algorithms, 18(1):2:1–2:11, December 2021.
  * [5] Marek Chrobak, Mordecai Golin, J. Ian Munro, and Neal E. Young.  On Huang and Wong’s algorithm for generalized binary split trees.  Acta Informatica, 59(6):687–708, December 2022.
  * [6] D. E. Knuth.  Optimum binary search trees.  Acta Informatica, 1:14–25, 1971.
  * [7] D. E. Knuth.  The Art of Computer Programming, Volume 3: Sorting and Searching.  Addison-Wesley Publishing Company, Redwood City, CA, USA, 2nd edition, 1998.
  * [8] D. Spuler.  Optimal search trees using two-way key comparisons.  Acta Informatica, 31(8):729–740, 1994.
  * [9] D. A. Spuler.  Optimal search trees using two-way key comparisons.  PhD thesis, James Cook University, 1994.
  * [10] F. Frances Yao.  Efficient dynamic programming using quadrangle inequalities.  In Raymond E. Miller, Seymour Ginsburg, Walter A. Burkhard, and Richard J. Lipton, editors, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 429–435. ACM, 1980.


# Connecting metrics for shape-texture knowledge in computer vision

Tiago Oliveira1, Tiago Marques2,3,4,5, Arlindo L. Oliveira1,6

1Instituto Superior Tecnico / INESC-ID, Lisbon, Portugal
2Department of Brain and Cognitive Sciences, MIT, Cambridge, MA
3McGovern Institute for Brain Research, MIT, Cambridge, MA
4Center for Brains, Minds and Machines, MIT, Cambridge, MA
5Champalimaud Clinical Centre, Champalimaud Foundation, Lisbon, Portugal
6Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA

###### Abstract

Modern artificial neural networks, including convolutional neural networks and
vision transformers, have mastered several computer vision tasks, including
object recognition. However, there are many significant differences between
the behavior and robustness of these systems and of the human visual system.
Deep neural networks remain brittle and susceptible to many changes in the
image that do not cause humans to misclassify images. Part of this different
behavior may be explained by the type of features humans and deep neural
networks use in vision tasks. Humans tend to classify objects according to
their shape while deep neural networks seem to rely mostly on texture.
Exploring this question is relevant, since it may lead to better performing
neural network architectures and to a better understanding of the workings of
the vision system of primates. In this work, we advance the state of the art
in our understanding of this phenomenon, by extending previous analyses to a
much larger set of deep neural network architectures. We found that the
performance of models in image classification tasks is highly correlated with
their shape bias measured at the output and penultimate layer. Furthermore,
our results showed that the number of neurons that represent shape and texture
are strongly anti-correlated, thus providing evidence that there is
competition between these two types of features. Finally, we observed that
while in general there is a correlation between performance and shape bias,
there are significant variations between architecture families.

##  1 Introduction

Modern artificial neural networks (ANNs) such as some convolutional neural
networks (CNNs) [1, 2, 3] and vision transformers [4, 5] have achieved human-
level performance in challenging computer vision tasks like object
recognition. Additionally, some of these models often learn representations
that resemble those found in neuronal populations along the primate visual
ventral stream areas [6] suggesting a parallelism in how visual information is
processed in both ANNs and biological neural networks in the brain. However,
significant differences between these systems remain, namely in the ANNs’
vulnerability to adversarial examples [7, 8], or their lack of generalization
capacity to out-of-distribution (OOD) datasets [9, 10]. Another such
difference is in the type of features humans and ANNs use predominantly for
making inferences. Unlike humans, who tend to classify objects according to
their shape, ANNs have been reported to rely mostly on texture cues [11, 12].
Due to this, ANNs are known for exhibiting a ’texture bias’ or lacking a more
human-aligned ’shape bias’. These biases are typically studied using images
with conflicting texture and shape cues while recording the ANNs’ behavioral
outputs [11, 12] or their internal activity [13].

There are multiple reasons why exploring this question is relevant. From a
neuroscientific perspective, there is an increasing interest in using ANNs to
model brain processing, particularly visual behaviors such as object
recognition. Therefore, the apparent lack of shape bias of ANNs is a crucial
limitation that should be addressed. From a machine learning standpoint,
understanding these divergences might provide insights on how to build
networks that are more aligned with human vision, and thus more interpretable,
as well as more accurate and robust. Multiple studies have related robustness,
OOD generalization and shape bias, but a coherent theory connecting them has
not emerged, yet. Reasoning using shape cues was initially thought to explain
the success of human vision to generalize to many domains [11], though more
recent studies have contradicted this hypothesis [12, 14]. On the other hand,
there is plenty of evidence relating adversarial robustness with increased
shape bias [15, 16, 17]). Interestingly, the relationship between adversarial
training and OOD generalization accuracy is less clear with some studies
suggesting some degree of correlation [18] and others little connection [19].
Another interesting result is that while maximizing accuracy during standard
training leads to increases in model shape-bias, the opposite is not
necessarily true [12].

In this work, we build on and complement existing literature on this subject
to fill in existing gaps. Hermann et al. showed that the shape bias measured
at the ANNs outputs (behavior) was correlated with their ImageNet accuracy
[12]. Similarly, Islam et al. used a metric to estimate the shape
dimensionality bias in latent representations of ANNs and found that it was
also related with their accuracy [13]. Both these studies used a very small
number of models with little diversity in their architectures to make these
inferences. The contributions of our work are the following:

  1. 1.

We extend and combine the results of Hermann et al. and Islam et al. to a much
larger pool of models (more than 600) with considerably different network
architectures (both CNNs and vision transformers). We found that as models
achieve higher ImageNet accuracy, they also increase their shape bias measured
at the output and in their penultimate layer.

  2. 2.

We observed that shape and texture dimensionalities are strongly anti-
correlated, thus quantifying the trade-off between the model’s knowledge of
these two concepts.

  3. 3.

We studied these relationships in the context of different model families,
observing a large variance in the results despite the overall correlations.

##  2 Methods

###  2.1 Shape Bias Evaluation

####  2.1.1 Shape Behavioral Bias

For a dataset that has a shape-texture conflict in each image (for example, an
image with a cat shape and dog texture), the shape behavioral bias, here
termed shape-bias, measures the inclination of the model to classify images
according to shape, as opposed to texture [11]. This is given by:

$\text{shape-bias}=\frac{\\#\text{correct shapes}}{\\#\text{correct
shapes}+\\#\text{correct textures}}$ (1)

###  2.2 Shape Dimensionality Bias

Following the definition of Esser et al., we here use the term dimensionality
to quantify the number of neurons associated with the knowledge about a given
concept in a neural network layer [20]. In this study, we consider three
concepts, or factors: shape, texture and residual. The latter captures all the
remaining knowledge in a given layer that is neither shape or texture.

In order to estimate the dimensionality of a certain factor, multiple pairs of
images, $x^{a}$ and $x^{b}$, are presented to an ANN, and a given layer’s
activations, respectively $z^{a}$ and $z^{b}$, are collected. For each image
pair, the factor of interest is shared while the other differs (for example,
two images of the same object with one having its texture swapped to that of
another object). The idea behind this approach is to estimate how much these
activations vary if the factor of interest is kept. To do this, we measure how
much do $z^{a}$ and $z^{b}$ correlate (neuron-wise),

$\rho_{\text{factor}}=\frac{1}{N}\sum_{i}^{N}\frac{\text{Cov}(z_{i}^{a},z_{i}^{b})}{\sqrt{\text{Var}(z_{i}^{a})\text{Var}(z_{i}^{b})}},$
(2)

where $i$ is the neuron number and $\rho_{\text{residual}}$ is $1$ by
definition. The stronger the correlation, the more relevant that factor is for
that model layer’s representation. To obtain the final estimate of
dimensionality of the factor, we then apply the softmax function to all factor
correlations and multiply them by the total number of neurons in the layer.
Here, we employ this approach to study the dimensionality of these factors in
the penultimate model layer. Unlike Islam et al. [13], we propose to study the
shape-texture bias, not with the absolute dimensionality, but with the
fraction between shape and texture neurons which we call shape-dim-ratio,

$\text{shape-dim-ratio}=\frac{\text{shape-dim}}{\text{shape-
dim}+\text{texture-dim}}$ (3)

###  2.3 Visual Stimuli

We use the cue-conflict image dataset proposed by Geirhos et al. to calculate
the shape behavioral bias in ANNs [11]. This dataset contains images generated
with neural style transfer [21]. Each generated image combines the shape of
one original image with the texture of another. In total, there are 16 object
classes, with 10 examples per each class providing the shape, and 3 examples
of each class providing the texture (1200 generated images). For each image,
the shape and texture class are never the same - this is the cue-conflict.

For the shape dimensionality bias estimate, we use Stylized Pascal VOC 2012
[13], which was created by combining a subset of the PASCAL VOC 2012 dataset
[22] and the Describable Textures Dataset [23]. Each object image (from 20
classes) is stylized [21] into 5 new ones, using 5 different texture images
(21845 generated images). This allows to sample image pairs that are either
similar in shape or similar in textures.

###  2.4 Models

We consider a very large pool of ANN models (624 models trained on ImageNet)
to measure both the shape behavioral and dimensionality biases in order to
better analyze and compare these metrics. These models vary greatly in their
architecture in terms of their overall structure (CNNs and vision
transformers), architectural families, number of layers, data augmentation,
ImageNet accuracy, and so on.

For one analysis, we look in more detail in how the results change for
different model families. We chose all the families that had at least nine
different models, forming a total of 17 families: Cait [24] (n=10), convnext
[3] (n=15), crossvit [25] (n=11), deit [26] (n=22), efficientnet [1] (n=38),
efficientnetv2 [27] (n=11), hrnet [28] (n=9), mobilenet [29, 30, 31] (n=17),
mobilevit [32] (n=16), regnet [33] (n=35), resmlp [34] (n=9), resnet [35]
(n=89), swin [5] (n=9), swinv2 [36] (n=13), vit [4], volo [37] (n=10), and
xcit [38] (n=42).

To measure the object classification performance of a given model, we use the
reported top-1 accuracy on ImageNet (ILSVRC-2012 validation set).

##  3 Results

###  3.1 Shape Behavioral Bias, Shape Dimensionality Bias, and Accuracy

Similarly to the results in Herman et al. [12], we observed a positive
correlation between the shape behavioral bias and object recognition
performance in our model pool (Figure 1, left; r=0.45,p<10E-32). The models
tested vary considerably more than those in the previous study in both these
two metrics (accuracy $\sim$60%-90%, shape-bias $\sim$10%-60%), thus extending
the range in which this relationship is observed. While the correlation is far
from perfect, our results show that the vast majority of models with
relatively high shape behavioral bias (larger than 40%) also have relatively
high ImageNet accuracy (larger than 80%). Interestingly, we observe that some
models solely trained for ImageNet performance without any optimization for
shape bias can achieve very high shape bias. For example, one model (Noisy
Student EfficientNet L2 [2]) has a shape-bias larger than 60%, something that
previously had only been reported in models exploring more unconventional data
augmentations, usually at the cost of ImageNet performance [12]. This was not
the case here, as the model was also the one with the highest object
classification accuracy.

Our model pool also varies considerably in the shape dimensionality bias
(shape-dim-ratio $\sim$35%-55%). This variance is also correlated with
ImageNet accuracy, and, similarly to the shape-dim, the models with the
highest shape-dim-ratio were also the best performing models in ImageNet
(Figure 1, center; r=0.57, p<10E-55).

Finally, when we directly compare the two shape bias metrics, we observe that
the shape bias present at the behavioral output correlates strongly with the
shape bias in the internal representations (Figure 1, right; r=0.66,
p<10E-80). While this result was expected, it is important to emphasize that
these metrics were measured using different image datasets. Interestingly, for
models with very high shape-bias, further improving this metric leads to
diminishing returns in shape-dim-ratio.

Figure 1: Comparison of shape dimensionality metrics and model accuracy. Shape
behavioral bias (shape-bias), shape dimensionality bias (shape-dim-ratio), and
object classification performance (ImageNet top-1 accuracy) are positively
correlated. Model pool consists of 624 ImageNet trained models. r is the
Pearson correlation coefficient.

###  3.2 Trade-Off between Shape and Texture Dimensionality

Previously, Islam et al., using a very small set of models, noticed that there
was a trend for the shape dimensionality to decrease with increasing texture
dimensionality. With the total dimensionality being capped at 100%, there is a
trade-off between the texture, shape and residual dimensionalities. Here, we
quantify and measure this trade-off in our large model pool. Over the whole
ranges of absolute shape dimensionality ($\sim$18%-27%) and texture
dimensionality ($\sim$21%-32%), these two metrics are negatively correlated
with a slope of approximately -1 (Figure 2, left; r=-0.91, p<10E-246). In
other words, as models acquire more shape neurons, they lose texture neurons
in the same proportion on average. Because of this, the number of residual
neurons is similar across the model pool (residual dim $\sim$50%-55%, data not
shown). Finally, another consequence of this trade-off is that with increasing
performance in object recognition, models have smaller texture dimensionality
(Figure 2, right; r=-0.55, p<10E-50).

Figure 2: Trade-off between shape and texture dimensionality in models’
penultimate layer. Left, texture and shape dimensionality are negatively
correlated with a slope $\sim$-1. Right, as models perform better in object
classification they have lower texture dimensionality.

###  3.3 Correlation between Shape Bias Metrics and Accuracy across
Architecture Families

How robust are these results for different model families? We attempt to
answer this question by looking at how the metrics under study relate with
each other when grouping the models according to their architectural family.
We consider all the families that have at least nine different models (16
families in total) and calculate the correlations between the shape behavioral
bias, the shape dimensionality bias, and the object classification accuracy
(Figure 3, left). While, the correlation between these metrics is present on
most model families (see the correlation between shape-bias and accuracy for
the ResNext models on Figure 3, center; r=0.78, p<10E-9), there is a large
degree of variability in how the metrics relate to each other in each model
family. For some model families, there is no significant correlation between
these metric pairs (see the correlation between shape-bias and accuracy for
the ViT models on Figure 3, center; r=0.22, p<0.22).

Figure 3: Effect of model family in the correlations between metrics. Left,
distribution of correlation coefficients of different model families for the
following metric pairs: accuracy vs shape-bias, accuracy vs shape-dim-ratio,
shape-bias vs shape-dim-ratio. Center, example of a model family, ResNext,
showing a very strong correlation between shape behavioral bias and ImageNet
accuracy. Right, same but for a model, family, ViT, showing no correlation
between the same metrics.

##  4 Discussion

In this paper, we extend the results of previous studies on the relationship
between shape bias, measured at both the model’s output and penultimate layer,
and ImageNet accuracy [12, 13]. By using a very large and varied model pool,
we confirm that optimizing models for performance in an object classification
task naturally leads to higher shape bias. This is true even when considering
a very wide range of top-1 ImageNet accuracy values ($\sim$60%-90%). The best
performing model in the model pool is also the one with the highest shape
behavioral bias, achieving a level that previously had only been reported with
a trade-off in ImageNet accuracy [12]. These are important observations since
they suggest that it may not be necessary to adopt strategies to specifically
deal with the lack of shape bias in ANNs. If the observed trend continues, one
should expect models to continue approaching human-level shape bias as they
become increasingly more accurate. When looking into individual model
families, while we observe that most follow the overall trend, some have
weaker correlations between accuracy and shape bias. The implications of this
is that the expected increase in shape bias with increasing ImageNet accuracy
may not be present in all ANN architectures. In those cases, additional
training strategies should be used to overcome this limitation [12]. Finally,
we observe that model improvement in ImageNet accuracy is accompanied by a
replacement of texture-based representations by shape-based ones, with
residual dimensionality remaining mostly unchanged at their penultimate layer.
Thus, there appears to be a trade-off between knowledge about shape and
texture at the level of the ANNs’ final stages and that texture information is
discarded in favor of shape information as models perform better in object
classification.

The topic of shape-texture bias in humans and ANNs has received plenty of
attention recently, including this study. However, much work remains to be
done if one wishes to close the gap between ANNs and human-level shape bias.
While we observe that some of the best performing ANNs have relatively high
shape bias ($\sim$60%), it is still considerably lower than what is observed
in humans ($\sim$95%) [11]. As accuracy in the ImageNet dataset approaches its
ceiling, further gains in shape bias may be starting to saturate, and, thus,
other optimization goals may be useful. A clear understanding of how shape
bias affects other important model performance metrics such as OOD
generalizationa and adversarial robustness is also lacking. Future work
extending the analyses of this study to include these and other important
metrics should provide insights to this topic. Finally, there have been
several neuroscience studies looking into how shape and texture information is
represented along the primate visual ventral stream areas [39, 40, 41, 42]. It
remains to be seen whether ANN models with higher shape bias are also better
models of biological vision, particularly in how they represent these two
visual concepts.

## Acknowledgments and Disclosure of Funding

This work was supported by the Portuguese Science Foundation, under projects
PRELUNA PTDC/CCI-INF/4703/2021 and UIDB/50021/2020. The last author
acknowledges the support of a Fulbright fellowship while he was a visiting
professor at the CSAIL laboratory at MIT.

## References

  * [1] Mingxing Tan and Quoc Le  “EfficientNet: Rethinking model scaling for convolutional neural networks”  In _International conference on machine learning_ , 2019, pp. 6105–6114  PMLR
  * [2] Qizhe Xie, Minh-Thang Luong, Eduard Hovy and Quoc V Le  “Self-training with noisy student improves ImageNet classification”  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , 2020, pp. 10687–10698
  * [3] Zhuang Liu et al.  “A ConvNet for the 2020s”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 11976–11986
  * [4] Alexey Dosovitskiy et al.  “An image is worth 16x16 words: Transformers for image recognition at scale”  In _arXiv preprint arXiv:2010.11929_ , 2020
  * [5] Ze Liu et al.  “Swin transformer: Hierarchical vision transformer using shifted windows”  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 10012–10022
  * [6] Chengxu Zhuang et al.  “Unsupervised neural network models of the ventral visual stream”  In _Proceedings of the National Academy of Sciences_ 118.3, 2021, pp. e2014196118
  * [7] Christian Szegedy et al.  “Intriguing properties of neural networks”  In _2nd International Conference on Learning Representations, ICLR 2014_ , 2014
  * [8] Alexey Kurakin, Ian J Goodfellow and Samy Bengio  “Adversarial examples in the physical world”  In _Artificial intelligence safety and security_ ChapmanHall/CRC, 2018, pp. 99–112
  * [9] Robert Geirhos et al.  “Generalisation in humans and deep neural networks”  In _Advances in neural information processing systems_ 31, 2018
  * [10] Dan Hendrycks and Thomas Dietterich  “Benchmarking neural network robustness to common corruptions and perturbations”  In _7th International Conference on Learning Representations, ICLR 2019_ , 2019, pp. 1–16
  * [11] Robert Geirhos et al.  “ImageNet-trained CNNs are biased towards texture; increasing shape bias improves accuracy and robustness”  In _arXiv preprint arXiv:1811.12231_ , 2018
  * [12] Katherine Hermann, Ting Chen and Simon Kornblith  “The origins and prevalence of texture bias in convolutional neural networks”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 19000–19015
  * [13] Md Amirul Islam et al.  “Shape or texture: Understanding discriminative features in CNNs”  In _arXiv preprint arXiv:2101.11604_ , 2021
  * [14] Chaithanya Kumar Mummadi et al.  “Does enhanced shape bias improve neural network robustness to common corruptions?”  In _arXiv preprint arXiv:2104.09789_ , 2021
  * [15] Robert Geirhos et al.  “Partial success in closing the gap between human and machine vision”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 23885–23899
  * [16] Peijie Chen, Chirag Agarwal and Anh Nguyen  “The shape and simplicity biases of adversarially robust ImageNet-trained CNNs”  In _arXiv preprint arXiv:2006.09373_ , 2020
  * [17] Tianyuan Zhang and Zhanxing Zhu  “Interpreting adversarially trained convolutional neural networks”  In _International Conference on Machine Learning_ , 2019, pp. 7502–7511  PMLR
  * [18] Cihang Xie et al.  “Adversarial examples improve image recognition”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 819–828
  * [19] Joel Dapello et al.  “Simulating a primary visual cortex at the front of CNNs improves robustness to image perturbations”  In _NeurIPS_ , 2020, pp. 1–30
  * [20] Patrick Esser, Robin Rombach and Bjorn Ommer  “A disentangling invertible interpretation network for explaining latent representations”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 9223–9232
  * [21] Leon A Gatys, Alexander S Ecker and Matthias Bethge  “Image style transfer using convolutional neural networks”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 2414–2423
  * [22] Mark Everingham et al.  “The PASCAL visual object classes (VOC) challenge”  In _International journal of computer vision_ 88.2 Springer, 2010, pp. 303–338
  * [23] Mircea Cimpoi et al.  “Describing textures in the wild”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2014, pp. 3606–3613
  * [24] Hugo Touvron et al.  “Going deeper with image transformers”  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 32–42
  * [25] Chun-Fu Richard Chen, Quanfu Fan and Rameswar Panda  “CrossViT: Cross-attention multi-scale vision transformer for image classification”  In _Proceedings of the IEEE/CVF international conference on computer vision_ , 2021, pp. 357–366
  * [26] Hugo Touvron et al.  “Training data-efficient image transformers & distillation through attention”  In _International Conference on Machine Learning_ , 2021, pp. 10347–10357  PMLR
  * [27] Mingxing Tan and Quoc Le  “EfficientNetV2: Smaller models and faster training”  In _International Conference on Machine Learning_ , 2021, pp. 10096–10106  PMLR
  * [28] Jingdong Wang et al.  “Deep high-resolution representation learning for visual recognition”  In _IEEE transactions on pattern analysis and machine intelligence_ 43.10 IEEE, 2020, pp. 3349–3364
  * [29] Andrew G Howard et al.  “MobileNets: Efficient convolutional neural networks for mobile vision applications”  In _arXiv preprint arXiv:1704.04861_ , 2017
  * [30] Mark Sandler et al.  “MobileNetV2: Inverted residuals and linear bottlenecks”  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 4510–4520
  * [31] Andrew Howard et al.  “Searching for MobileNetV3”  In _Proceedings of the IEEE/CVF international conference on computer vision_ , 2019, pp. 1314–1324
  * [32] Sachin Mehta and Mohammad Rastegari  “MobileViT: light-weight, general-purpose, and mobile-friendly vision transformer”  In _arXiv preprint arXiv:2110.02178_ , 2021
  * [33] Jing Xu et al.  “RegNet: self-regulated network for image classification”  In _IEEE Transactions on Neural Networks and Learning Systems_ IEEE, 2022
  * [34] Hugo Touvron et al.  “ResMLP: Feedforward networks for image classification with data-efficient training”  In _arXiv preprint arXiv:2105.03404_ , 2021
  * [35] 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_ , 2016, pp. 770–778
  * [36] Ze Liu et al.  “Swin transformer V2: Scaling up capacity and resolution”  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2022, pp. 12009–12019
  * [37] Li Yuan et al.  “VOLO: Vision outlooker for visual recognition”  In _arXiv preprint arXiv:2106.13112_ , 2021
  * [38] Alaaeldin Ali et al.  “XCiT: Cross-covariance image transformers”  In _Advances in neural information processing systems_ 34, 2021, pp. 20014–20027
  * [39] C Cavina-Pratesi, RW Kentridge, CA Heywood and AD Milner  “Separate processing of texture and form in the ventral stream: evidence from FMRI and visual agnosia”  In _Cerebral Cortex_ 20.2 Oxford University Press, 2010, pp. 433–446
  * [40] Taekjun Kim, Wyeth Bair and Anitha Pasupathy  “Neural Coding for Shape and Texture in Macaque Area V4”  In _Journal of Neuroscience_ 39.24 Society for Neuroscience, 2019, pp. 4760–4774
  * [41] Jeremy Freeman et al.  “A functional and perceptual signature of the second visual area in primates”  In _Nature Neuroscience_ 16.7, 2013, pp. 974–981
  * [42] Jay Hegdé and David C. Van Essen  “A comparative study of shape representation in macaque visual areas V2 and V4”  In _Cerebral Cortex_ 17.5, 2007, pp. 1100–1116


The Computational Lens:
from Quantum Physics to Neuroscience
Chi-Ning Chou
Boaz Barak

Doctor of Philosophy
Computer Science
Engineering And Applied Sciences

National Taiwan University