[1] SanghoonNa

1]Department of Mathematics, University of Maryland,
College Park, MD 20742, USA

# Frame Quantization of Neural Networks

WojciechCzaja  *<EMAIL_ADDRESS>[

###### Abstract

We present a post-training quantization algorithm with error estimates relying
on ideas originating from frame theory. Specifically, we use first-order
Sigma-Delta ($\Sigma\Delta$) quantization for finite unit-norm tight frames to
quantize weight matrices and biases in a neural network. In our scenario, we
derive an error bound between the original neural network and the quantized
neural network in terms of step size and the number of frame elements. We also
demonstrate how to leverage the redundancy of frames to achieve a quantized
neural network with higher accuracy.

###### keywords:

Neural Network Quantization, Post-Training Quantization, Sigma-Delta
Quantization, Finite Frames

##  1 Introduction

Quantization is the process of compressing input from a continuous or large
set of values into a small-sized discrete set. It gained popularity in signal
processing, where one of its primary goals is obtaining a condensed
representation of the analogue signal suitable for digital storage and
recovery. Examples of quantization algorithms include truncated binary
expansion, pulse-code modulation (PCM) and sigma-delta ($\Sigma\Delta$)
quantization. Among them, $\Sigma\Delta$ algorithms stand out due to their
theoretically guaranteed robustness. Mathematical theories were developed in
several seminal works [8, 11, 4, 5, 3], and have been carefully studied since,
e.g., [15, 19, 27, 14].

In recent years, the concept of quantization also captured the attention of
the machine learning community. The quantization of deep neural networks
(DNNs) is considered one of the most effective network compression techniques
[9]. Computers express parameters of a neural network as 32-bit or 64-bit
floating point numbers. In neural network quantization, one tries to replace
these parameters using compact formats such as 8 bits (or lower), while
preserving the architecture and performance of the network. An effective
neural network quantization method enables users to run DNNs on portable
devices, such as smartphones, without relying on external servers. This
benefits storage requirements and helps to avoid privacy-related issues. Due
to these reasons, there have been numerous efforts to develop neural network
quantization schemes that preserve the model accuracy.

Neural network quantization can be categorized into 2 classes. The first class
is Quantization-Aware-Training (QAT). QAT methods [7, 18, 26, 31, 20, 21]
retrain the given neural network, by restricting the domain of parameters to a
finite set of alphabets. The second class is Post-Training Quantization (PTQ).
PTQ methods [24, 29, 25, 16, 22, 33, 1, 30, 32, 23] take a pre-trained neural
network and convert it directly into a fixed-point neural network. They demand
less computation because they do not require end-to-end training. In addition,
unlike QAT methods, PTQ methods do not require the training dataset - they
usually require only a small calibration set. These reasons make PTQ methods
attractive. For a detailed explanation of QAT and PTQ methods, see [9] and
references therein.

Despite the popularity of PTQ methods, unfortunately, most of them lack
theoretical error analysis. While some algorithms [22, 33, 32, 23] are
equipped with error estimates, they are typically probabilistic estimates with
additional requirements on input distributions. Moreover, their error
estimates are proved only for feed-forward networks. However, there are
popular neural networks with different architectures, such as ResNet [17],
which is constructed by stacking together a series of residual blocks.
Therefore, the design of a PTQ method with error estimates for different types
of neural networks is still an open question.

To address this problem, we return to the methods of quantization from signal
processing and investigate how to utilize them in the neural network setting
while retaining their theoretical guarantees. We focus on $\Sigma\Delta$
quantization algorithms. While [8, 11] focus on $\Sigma\Delta$ quantization
for bandlimited functions, [4, 3, 5] provide mathematical analysis of
$\Sigma\Delta$ quantization for finite frames in $\mathbb{R}^{d}$ and
$\mathbb{C}^{d},$ which is suitable for quantization of weight matrices in
neural networks. Leveraging the tools from [4, 3, 5], we are able to provide a
new PTQ algorithm with error estimates. Our contributions are threefold:

  1. 1.

In Section 4 we propose an algorithm for quantizing layers of a pre-trained
neural network using the first-order $\Sigma\Delta$ quantization algorithm for
finite unit-norm tight frames in $\mathbb{R}^{d}.$ Our algorithm does not
require any training data, hence a data-free quantization. To the best of our
knowledge, our work is the first to utilize the tools from frame theory in
this context (recent work [34] studies quantizing random Fourier features
(RFFs) using $\Sigma\Delta$ algorithm, which is different from our study of
DNNs).

  2. 2.

We provide error estimates for both $n$-layer feed-forward neural networks and
neural networks formed by a series of residual blocks in Section 5. These
results demonstrate how to control the error using the step size and the
number of frame elements.

  3. 3.

We provide numerical results for quantizing neural networks trained on the
MNIST data set using our proposed algorithm in Section 6. We quantize all
layers and demonstrate that our algorithm can even perform 1-bit quantization
with a small loss of accuracy.

##  2 Preliminaries

In this paper, all vectors are column vectors in $\mathbb{R}^{d}$,
$d\in\mathbb{N}.$ For a vector $x$, $\|x\|$ denotes the Euclidean norm of $x$.
For a matrix $A$, $\|A\|$ denotes the matrix 2-norm of $A$, which is the
largest singular value of $A$.

We introduce the mathematical formulation of neural networks used in this
paper. First, a fully connected feed-forward neural network (FNN) with $n$
layers is a function $f:\mathbb{R}^{m_{0}}\rightarrow\mathbb{R}^{m_{n}}$ which
acts on data $x\in\mathbb{R}^{m_{0}}$ via

$\displaystyle f(x)=h^{[n]}\circ\sigma\circ
h^{[n-1]}\circ\cdots\circ\sigma\circ h^{[1]}(x),$ (1)

where $h^{[l]}(x)=W_{l}x+b_{l}$ with weight matrix
$W_{l}\in\mathbb{R}^{m_{l}\times m_{l-1}}$ and bias
$b_{l}\in\mathbb{R}^{m_{l}}$, $l=1,2,\cdots,n,$ and nonlinear activation
function $\sigma$ which acts on each component of a vector. Here, we omit the
activation for the last layer because the choice of the final activation can
be different from $\sigma$. For example in classification problems, softmax
activation function is used in the last step, while $\sigma$ is often chosen
as the Rectified Linear Unit (ReLU) function, defined as
$x\mapsto\max\\{0,x\\}$ for $x\in\mathbb{R}$. Note that ReLU is a 1-Lipchitz
continuous function attaining $0$ at $x=0$. Throughout this paper we will
assume activation function $\sigma$ is an $L$-Lipschitz continuous function
with $\sigma(0)=0,$ which makes ReLU a special case. In addition, we will also
assume that $m_{i}\geq 3$ for all $i$’s. This is a natural assumption since
typical neural network architectures set the number of neurons at each layer
to be greater than $2$.

Next we introduce the mathematical formulation for residual blocks and
residual neural networks used in this paper. We adopt the mathematical
formulation from Chapter 3.8.2 in [10]. A residual neural network with $n$
residual blocks is a function $g:\mathbb{R}^{k}\rightarrow\mathbb{R}^{k}$
defined as

$\displaystyle g(x)=z^{[n]}\circ\sigma\circ
z^{[n-1]}\circ\cdots\circ\sigma\circ z^{[1]}(x),$ (2)

where each residual block $z^{[i]}$ has a structure
$z^{[i]}(x)=W_{i,2}\sigma(W_{i,1}x+b_{i})+x,$ with weight matrices
$W_{i,1},W_{i,2}\in\mathbb{R}^{k\times k}$ and bias $b_{i}\in\mathbb{R}^{k}.$
For residual networks, we only consider ReLU as the activation function.

For a neural network $F(x)$, the quantized neural network $F_{Q}(x)$ is
defined as a network formed by replacing weight matrices and biases of $F(x)$
with quantized weight matrices and quantized biases from any quantization
algorithm. For example, for a fully connected FNN $f(x)$ in (1), assume that
$Q_{i}$’s and $c_{i}$’s are quantized weight matrices and quantized biases of
$W_{i}$’s and $b_{i}$’s, respectively. Then,

$\displaystyle f_{Q}(x)=h^{[n]}_{Q}\circ\sigma\circ
h^{[n-1]}_{Q}\circ\sigma\cdots\circ\sigma\circ h^{[1]}_{Q}(x),$ (3)

where $h^{[i]}_{Q}(x)=Q_{i}x+c_{i}$ for $i=1,\cdots,n.$ Similarly for a
residual network $g(x)$ in (2),

$\displaystyle g_{Q}(x)=z^{[n]}_{Q}\circ\sigma\circ
z^{[n-1]}_{Q}\circ\cdots\circ\sigma\circ z^{[1]}_{Q}(x),$ (4)

where $z^{[i]}_{Q}(x)=Q_{i,2}\sigma(Q_{i,1}x+c_{i})+x$ for $i=1,\cdots,n.$
Here, $Q_{i,2}$’s, $Q_{i,1}$’s and $c_{i}$’s are quantized weight matrices and
quantized biases of $W_{i,2}$’s, $W_{i,1}$’s and $b_{i}$’s respectively.

Note that if we write $\widetilde{W}_{l}=(W_{l},b_{l})$ and
$\tilde{x}=(x^{T},1)^{T},$ then
$h^{[l]}(x)=W_{l}x+b_{l}=\widetilde{W}_{l}\tilde{x}$ holds. Therefore, without
loss of generality, we will omit the biases in our analysis. This means we
assume $b_{i}=0$ for all $i$’s, so $h^{[i]}(x)$’s in (1) can be regarded as
$h^{[i]}(x)=W_{i}x$ and $z^{[i]}(x)$’s in (2) can be regarded as
$z^{[i]}(x)=W_{i,2}\sigma(W_{i,1}x)+x$.

Next we recall some basics from frame theory. In this paper, we only discuss
finite frames for $\mathbb{R}^{d}$. For the discussion of finite frames for
general Hilbert spaces, see [6]. We say a set $\\{e_{1},\cdots,e_{N}\\}$ in
$\mathbb{R}^{d}$ is a finite frame for $\mathbb{R}^{d}$ if there exist
$0<A\leq B<\infty$, such that $A\|x\|^{2}\leq\sum_{i=1}^{N}|\langle
x,e_{i}\rangle|^{2}\leq B\|x\|^{2}$ holds for all $x\in\mathbb{R}^{d}.$ The
constants $A$ and $B$ are called frame bounds, and $\\{\langle
x,e_{i}\rangle\\}_{i=1}^{N}$ are called the frame coefficients of $x$ with
respect to frame $\\{e_{1},\cdots,e_{N}\\}$. A frame
$\\{e_{1},\cdots,e_{N}\\}$ in $\mathbb{R}^{d}$ is called tight if $A=B.$ If a
finite tight frame $F=\\{e_{1},\cdots,e_{N}\\}$ satisfies $\|e_{i}\|=1$ for
all $i$, then we say $F$ is a finite unit-norm tight frame (FUNTF). For a
finite frame $\\{e_{1},\cdots,e_{N}\\}$ in $\mathbb{R}^{d}$, the linear
function $S:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ defined by

$\displaystyle Sx=\sum_{i=1}^{N}\langle x,e_{i}\rangle e_{i},$ (5)

is the frame operator of $F$. Note that if $F=\\{e_{1},\cdots,e_{N}\\}$ is a
finite frame for $\mathbb{R}^{d}$ with frame bounds $A$ and $B$, then it is
easy to see that $S$ is a $d\times d$ positive definite matrix satisfying
$AI_{d}\leq S\leq BI_{d},$ where $I_{d}$ is the identity matrix of
$\mathbb{R}^{d}$. Therefore, its inverse $S^{-1}$ exists and it satisfies
$\frac{1}{B}I_{d}\leq S^{-1}\leq\frac{1}{A}I_{d}.$ This inverse operator
$S^{-1}$ is called the dual frame operator. Multiplying (5) by $S^{-1}$ gives
us an atomic decomposition of an arbitrary $x\in\mathbb{R}^{d}$:

$\displaystyle x=S^{-1}Sx=S^{-1}\Big{\\{}\sum_{i=1}^{N}\langle x,e_{i}\rangle
e_{i}\Big{\\}}=\sum_{i=1}^{N}\langle x,e_{i}\rangle S^{-1}e_{i}.$ (6)

It is straightforward to check $\\{S^{-1}e_{1},\cdots,S^{-1}e_{N}\\}$ is a
frame for $\mathbb{R}^{d}$ with frame bounds $1/B$ and $1/A.$ We say that
$\\{S^{-1}e_{1},\cdots,S^{-1}e_{N}\\}$ is the canonical dual frame of $F$. For
detailed proofs of the aforementioned statements, see [6]. When
$F=\\{e_{1},\cdots,e_{N}\\}$ is a tight frame for $\mathbb{R}^{d}$ with frame
bound $A$, then $S=AI_{d}$ and $S^{-1}=\frac{1}{A}I_{d}.$ In this case, (6)
gives us the frame expansion $x=\frac{1}{A}\sum_{i=1}^{N}\langle
x,e_{i}\rangle e_{i}$, for any $x\in\mathbb{R}^{d}.$ Moreover, if $F$ is a
FUNTF, then it is known that $A=N/d$ holds [5]. Therefore, we have the frame
expansion $x=\frac{d}{N}\sum_{i=1}^{N}\langle x,e_{i}\rangle e_{i}$ for any
$x\in\mathbb{R}^{d}.$

##  3 Frame quantization

In vector quantization, first-order $\Sigma\Delta$ quantization algorithm has
a uniform upper bound on the error in the case of finite frames [4] and it is
known to outperform PCM most of the time for realistic settings [2]. Since a
matrix can be interpreted as a stack of column vectors, $\Sigma\Delta$ becomes
an option for quantizing a weight matrix. In this section, we introduce first-
order $\Sigma\Delta$ quantization algorithms for finite frames for
$\mathbb{R}^{d}.$ We begin with some common definitions in [3, 5, 6, 33, 4].
Given $K\in\mathbb{N}$ and $\delta>0,$ the midrise quantization alphabet
$A^{\delta}_{K}$ is defined as

$\displaystyle
A^{\delta}_{K}=\Big{\\{}(-K+\frac{1}{2})\delta,(-K+\frac{3}{2})\delta,\cdots,-\frac{1}{2}\delta,\frac{1}{2}\delta,\cdots,(K-\frac{1}{2})\delta\Big{\\}}.$
(7)

The $2K$-level midrise uniform scalar quantizer $Q$ with step size $\delta$ is
defined as

$\displaystyle Q(u)=\arg{\min_{q\in A^{\delta}_{K}}|u-q|}.$

Therefore, $Q(u)$ is the element in $A^{\delta}_{K}$ which is closest to $u$.

######  Definition 3.1.

[4] Given $K\in\mathbb{N}$ and $\delta>0,$ define the midrise quantization
alphabet $A^{\delta}_{K}$ and the $2K$-level midrise uniform scalar quantizer
$Q$ with stepsize $\delta$ . Let $F=\\{e_{1},\cdots,e_{N}\\}$ be a finite
frame for $\mathbb{R}^{d}$ where $d\geq 3$ and let $p$ be a permutation of
$\\{1,2,\cdots,N\\}.$ For a given input sequence
$\\{x_{1},x_{2},\cdots,x_{N}\\}$, the associated first-order _$\Sigma\Delta$
quantization_ is defined by the iteration:

$\displaystyle u_{n}=u_{n-1}+x_{p(n)}-q_{n},$ $\displaystyle
q_{n}=Q(u_{n-1}+x_{p(n)}),$

for $n=1,2,\cdots,N$ where $u_{0}=0.$ This produces the quantized sequence
$\\{q_{1},\cdots,q_{N}\\}$ and an auxiliary sequence
$\\{u_{0},\cdots,u_{N}\\}$ of state variables.

In the above it is possible to consider nonzero initial condition
$\|u_{0}\|<\delta/2,$ but for simplicity, we will only consider the case
$u_{0}=0$ as in [4].

We now describe the vector quantization process. Let
$F=\\{e_{1},\cdots,e_{N}\\}$ be a finite frame for $\mathbb{R}^{d}$ and let
$p$ be a permutation of $\\{1,2,\cdots,N\\}.$ Choose an arbitrary vector
$x\in\mathbb{R}^{d}$ and represent it as $x=\sum_{i=1}^{N}x_{i}S^{-1}e_{i}$
with frame expansion in (6). We say
$\bar{x}=\sum_{i=1}^{N}q_{i}S^{-1}e_{p(i)}$ is the quantized expansion of $x$,
where $\\{q_{1},\cdots,q_{N}\\}$ are the quantized sequence from the first-
order $\Sigma\Delta$ quantization in Definition 3.1. The first-order
$\Sigma\Delta$ scheme in Definition 3.1 is an iterative scheme that depends
heavily on the choice of permutation $p$. Given a finite frame
$F=\\{e_{1},\cdots,e_{N}\\}$ for $\mathbb{R}^{d}$, its frame variation with
respect to a permutation $p$ of $\\{1,2,\cdots,N\\}$ is defined as
$\sigma(F,p):=\sum_{i=1}^{N-1}\|e_{p(i)}-e_{p(i+1)}\|.$ Frame variation is a
measurement that captures the interdependencies between the frame elements
resulting from the choice of $p$. It is an important quantity that reflects
the role of permutation $p$ in the error estimates for first-order
$\Sigma\Delta$ quantization.

We provide an error bound on the approximation error $\|x-\bar{x}\|$. Here, we
only state the result for the case of a FUNTF. For general results, see [4]
and [5].

######  Theorem 3.1.

[4] Let $F=\\{e_{1},\cdots,e_{N}\\}$ be a finite unit-norm tight frame for
$\mathbb{R}^{d}$, and let $p$ be a permutation of $\\{1,2,\cdots,N\\}.$ Let
$x\in\mathbb{R}^{d}$ satisfy $\|x\|\leq(K-1/2)\delta$ and have the frame
expansion $x=\sum_{i=1}^{N}\langle x,e_{i}\rangle S^{-1}e_{i},$ where $S^{-1}$
is the inverse frame operator for $F$. Then, $\bar{x}$ satisfies the
approximation error

$\displaystyle\|x-\bar{x}\|\leq\frac{\delta d}{2N}(\sigma(F,p)+1).$

To obtain a quantized expansion with a small error, it is desirable to choose
a permutation $p$ that makes frame variation $\sigma(F,p)$ small. In [28], the
author proved that for a set
$\\{e_{1},\cdots,e_{N}\\}\subset[-\frac{1}{2},\frac{1}{2}]^{d},$ with $d\geq
3$, there exists a permutation $p$ of $\\{1,2,\cdots,N\\}$ which satisfies
$\sum_{i=1}^{N-1}\|e_{p(i)}-e_{p(i+1)}\|\leq
2\sqrt{d+3}N^{1-\frac{1}{d}}-2\sqrt{d+3}.$ Note that for a unit-norm frame
$F=\\{e_{1},\cdots,e_{N}\\}$ for $\mathbb{R}^{d}$, the set
$\frac{1}{2}F=\\{\frac{1}{2}e_{1},\cdots,\frac{1}{2}e_{N}\\}$ is a subset of
$[-\frac{1}{2},\frac{1}{2}]^{d}.$ In [5], the authors combined these results
to obtain the following result.

######  Theorem 3.2.

[5] Let $F=\\{e_{1},\cdots,e_{N}\\}$ be a unit-norm frame for
$\mathbb{R}^{d}$, $d\geq 3.$ Then, there exists a permutation $p$ of
$\\{1,2,\cdots,N\\}$ such that

$\displaystyle\sigma(F,p)\leq 4\sqrt{d+3}N^{1-\frac{1}{d}}-4\sqrt{d+3}.$ (8)

Next, we estimate the approximation error in terms of $\delta,d,$ and $N$.

######  Corollary 3.3.

Let $F=\\{e_{1},\cdots,e_{N}\\}$ be a finite unit-norm tight frame for
$\mathbb{R}^{d}$, $d\geq 3,$ and let $x\in\mathbb{R}^{d}$ satisfy
$\|x\|\leq(K-1/2)\delta$. Let $p$ be a permutation of $\\{1,2,\cdots,N\\}$
that satisfies (8). Let $\bar{x}$ be the quantized expansion. Then, the
approximation error satisfies

$\displaystyle\|x-\bar{x}\|\leq\frac{\delta
d}{2N}(4\sqrt{d+3}N^{1-\frac{1}{d}}-4\sqrt{d+3}+1).$

###### Proof.

Apply Theorem 3.2 to Theorem 3.1. ∎

Corollary 3.3 shows that we can bound the approximation error by only using
the variables $\delta,d,$ and $N$. We use this result to obtain error bounds
between a neural network and its quantized version in Section 5.

##  4 Frame Quantization for Neural Networks

In this section, we explain our method to quantize a weight matrix
$W_{i}\in\mathbb{R}^{m_{i}\times m_{i-1}}$. Let
$F_{i}=\\{e^{i}_{1},\cdots,e^{i}_{N_{i}}\\}$ be a FUNTF for
$\mathbb{R}^{m_{i}}$ that we are using for quantization. Write
$W_{i}=[w^{i}_{1},w^{i}_{2},\cdots,w^{i}_{m_{i-1}}]$ where $w^{i}_{j}$ is a
$m_{i}\times 1$ column vector for $j=1,2,\cdots,m_{i-1}.$ First, choose
appropriate positive integer $K_{i}$ and step size $\delta_{i}>0$ that satisfy

$\displaystyle\max_{j=1,\cdots,m_{i-1}}\|w^{i}_{j}\|\leq(K_{i}-\frac{1}{2})\delta_{i}.$
(9)

Next, we find a permutation $p_{i}$ of $\\{1,\cdots,N_{i}\\}$ that satisfies
(8). The algorithm to find such permutations is described in [5, 28], so we
omit the details. Then, we compute the quantized expansions of $w^{i}_{j}$’s,
using frame $F_{i}$, constant $K_{i},$ and step size $\delta_{i}$ for
$i=1,\cdots,n$. Let $q^{i}_{j}$ be the quantized expansion of $w^{i}_{j}.$
Since we are using finite unit-norm tight frame, the dual frame operator
$S^{-1}$ is $\frac{m_{i}}{N_{i}}I_{m_{i}}$, where $I_{m_{i}}$ is the identity
matrix of $\mathbb{R}^{m_{i}}$. Therefore $q^{i}_{j}$’s can be written as

$\displaystyle
q^{i}_{j}=\sum_{k=1}^{N_{i}}q^{i}_{j,k}S^{-1}e^{i}_{p_{i}(k)}=\frac{m_{i}}{N_{i}}\sum_{k=1}^{N_{i}}q^{i}_{j,k}e^{i}_{p_{i}(k)}.$
(10)

Note that the first-order $\Sigma\Delta$ quantization in Definition 3.1 forces
$q^{i}_{j,k}\in A^{\delta_{i}}_{K_{i}}$ for all
$(j,k)\in\\{1,\cdots,m_{i-1}\\}\times\\{1,\cdots,N_{i}\\}.$ Therefore, at most
$2K_{i}$ values are candidates for $q^{i}_{j,k}$. In our scenario, we store
$C_{i}=[q^{i}_{j,k}]_{1\leq j\leq m_{i-1},1\leq k\leq
N_{i}}\in(A^{\delta_{i}}_{K_{i}})^{m_{i-1}\times N_{i}}$. When we need a
quantized neural network, then we use the finite unit-norm tight frames
$F_{i}$’s and matrices $C_{i}$’s to reconstruct a network using (10).

Current neural network quantization methods convert a weight matrix
$W=[w_{ij}]_{1\leq i\leq m,1\leq j\leq n}\in\mathbb{R}^{m\times n}$ into a
quantized matrix $Q=[q_{ij}]_{1\leq i\leq m,1\leq j\leq n}$, where each
$q_{ij}$ uses fewer bits compared to the corresponding $w_{ij}$. Note that $W$
and $Q$ have the same dimensions. Our method differs from typical approaches
because we are storing matrices $C_{i}$’s that have different dimensions from
the weight matrices $W_{i}$’s. Due to their different dimensions, we will not
say $C_{i}$’s are quantized weights. Instead, we will say that the matrix
$Q_{i}=[q^{i}_{1},\cdots,q^{i}_{m_{i-1}}]\in\mathbb{R}^{m_{i}\times m_{i-1}}$,
where the columns are the quantized expressions $q^{i}_{j}$’s, is the
quantized weight matrix of $W_{i}\in\mathbb{R}^{m_{i}\times m_{i-1}}$ for
$i=1,\cdots,n.$

Algorithm 1 Frame Quantization

Weight matrix $W_{i}\in\mathbb{R}^{m_{i}\times m_{i-1}}$ and FUNTF
$F_{i}=\\{e^{i}_{1},\cdots,e^{i}_{N_{i}}\\}$ for $\mathbb{R}^{m_{i}}.$

1\. Set level $K_{i}\in\mathbb{N}$ and stepsize $\delta_{i}$ that satisfy
$\max_{j=1,\cdots,m_{i-1}}\|w^{i}_{j}\|\leq(K_{i}-\frac{1}{2})\delta_{i}.$

2\. Find a permutation $p_{i}$ of $\\{1,\cdots,N_{i}\\}$ that satisfies (8).

for $j=1,\cdots,m_{i-1}$ do

1\. Compute frame expansion
$w^{i}_{j}=\frac{m_{i}}{N_{i}}\sum_{k=1}^{N_{i}}w^{i}_{j,k}e^{i}_{k}.$

2\. Use first-order $\Sigma\Delta$ quantization algorithm 3.1 with $K_{i}$ and
$\delta_{i}$ to compute
$q^{i}_{j}=\frac{m_{i}}{N_{i}}\sum_{k=1}^{N_{i}}q^{i}_{j,k}e^{i}_{p_{i}(k)}.$

end for

3\. Set $C_{i}=[q^{i}_{j,k}]_{1\leq j\leq m_{i-1},1\leq k\leq
N_{i}}\in(A^{\delta_{i}}_{K_{i}})^{m_{i-1}\times N_{i}}.$

Quantized matrix
$Q_{i}=[q^{i}_{1},\cdots,q^{i}_{m_{i-1}}]\in\mathbb{R}^{m_{i}\times m_{i-1}}.$
Store $C_{i}.$

Note that the above algorithm uses first-order $\Sigma\Delta$ quantization for
the column vectors of the weight matrix $W_{i}.$ On the other hand, we may
consider applying first-order $\Sigma\Delta$ quantization algorithm for the
row vectors of the weight matrix $W_{i}$. In this case, we apply Algorithm 1
to $W_{i}^{T}$.

Note that we can also quantize biases by adding them to the final columns of
weight matrices. This means we can also quantize $b_{i}$’s while we quantize
the weight matrices $W_{i}$’s by applying Algorithm 1 to matrices
$\widetilde{W_{i}}=(W_{i},b_{i})$’s.

##  5 Error Estimates

We begin with some auxiliary lemmas, which play an important role in proving
error estimates between a neural network and its approximation by a quantized
network.

######  Lemma 5.1.

Let $Q_{i}$ be the quantized matrix for weight matrix
$W_{i}\in\mathbb{R}^{m_{i}\times m_{i-1}}$ using Algorithm 1. Then,

$\displaystyle\|W_{i}-Q_{i}\|\leq
2\sqrt{2}\delta_{i}m_{i}\sqrt{m_{i-1}m_{i}}N_{i}^{-\frac{1}{m_{i}}},$

where $\delta_{i}$ is the step size and $N_{i}$ is the number of elements in
the frame $F_{i}=\\{e^{i}_{1},\cdots,e^{i}_{N_{i}}\\}$ used in Algorithm 1.

###### Proof.

Write $W_{i}=[w^{i}_{1}\cdots
w^{i}_{m_{i-1}}],Q_{i}=[q^{i}_{1},\cdots,q^{i}_{m_{i-1}}]\in\mathbb{R}^{m_{i}\times
m_{i-1}}$ where $w^{i}_{j}$’s and $q^{i}_{j}$’s are $m_{i}\times 1$ column
vectors. Since Algorithm 1 uses $p_{i}$ that satisfies (8), Corollary 3.3
gives us the error estimate

$\displaystyle\|w^{i}_{j}-q^{i}_{j}\|\leq\frac{\delta_{i}m_{i}}{2N_{i}}(4\sqrt{m_{i}+3}N_{i}^{1-\frac{1}{m_{i}}}-4\sqrt{m_{i}+3}+1)$
(11)

for all $j=1,\cdots,m_{i-1}.$ Now, using (11) and the assumption $m_{i}\geq 3$
from Section 2, we have

$\displaystyle\|W_{i}-Q_{i}\|$
$\displaystyle=\max_{\|x\|=1}\|(W_{i}-Q_{i})x\|\leq\max_{\|x\|=1}\\{\sum_{j=1}^{m_{i-1}}|x_{j}|\times\|w^{i}_{j}-q^{i}_{j}\|\\}$
$\displaystyle\leq\frac{\delta_{i}m_{i}}{2N_{i}}(4\sqrt{m_{i}+3}N_{i}^{1-\frac{1}{m_{i}}}-4\sqrt{m_{i}+3}+1)\times\max_{\|x\|=1}\\{\sum_{j=1}^{m_{i-1}}|x_{j}|\\}$
$\displaystyle\leq\frac{\delta_{i}m_{i}\sqrt{m_{i-1}}}{2N_{i}}(4\sqrt{m_{i}+3}N_{i}^{1-\frac{1}{m_{i}}}-4\sqrt{m_{i}+3}+1)$
$\displaystyle\leq\frac{\delta_{i}m_{i}\sqrt{m_{i-1}}}{2N_{i}}\times
4\sqrt{m_{i}+3}N_{i}^{1-\frac{1}{m_{i}}}\leq
2\sqrt{2}\delta_{i}m_{i}\sqrt{m_{i-1}m_{i}}N_{i}^{-\frac{1}{m_{i}}}.$

∎

Next we provide an upper bound for the norm of the quantized matrices
$Q_{i}$’s. This is used in deriving the error estimate between an $n$-layer
FNN and its corresponding quantized neural network.

######  Lemma 5.2.

Let $Q_{i}$ be the quantized matrix of $W_{i}.$ Let $\sigma_{i}=\|W_{i}\|.$
Then we have

$\displaystyle\|Q_{i}\|\leq
2\sqrt{2}\delta_{j}m_{j}\sqrt{m_{j}m_{j-1}}N_{j}^{-\frac{1}{m_{j}}}+\sigma_{i}.$

###### Proof.

Using Lemma 5.1 and the triangle inequality of matrix norms, we have

$\displaystyle\|Q_{i}\|\leq\|Q_{i}-W_{i}\|+\|W_{i}\|\leq
2\sqrt{2}\delta_{i}m_{i}\sqrt{m_{i}m_{i-1}}N_{i}^{-\frac{1}{m_{i}}}+\sigma_{i}.$

∎

###  5.1 Feedforward Networks

In this section, we derive an upper estimate for $\|f(x)-f_{Q}(x)\|$, where
$f(x)$ is a FNN with $n$ layers (1) and $f_{Q}(x)$ its quantized neural
network (3). For convenience, we adopt the assumptions from Section 2 and omit
the biases in our analysis. Thus, we can write
$f(x)=W_{n}(\sigma(\cdots\sigma(W_{1}x)\cdots))$ and
$f_{Q}(x)=Q_{n}(\sigma(\cdots\sigma(Q_{1}x)\cdots))$. As in Lemma 5.2, we let
$\sigma_{i}=\|W_{i}\|$ for $i=1,\cdots,n.$

######  Theorem 5.3.

Let $f(x)=W_{n}(\sigma(\cdots\sigma(W_{1}x)\cdots))$ be a feed-forward neural
network with $n$ layers. Let
$f_{Q}(x)=Q_{n}(\sigma(\cdots\sigma(Q_{1}x)\cdots))$ be the quantized neural
network obtained by means of Algorithm 1. Then, for any input
$X\in\mathbb{R}^{m_{0}}$, we have

$\displaystyle\|f(X)-f_{Q}(X)\|$ $\displaystyle\leq
L^{n-1}\|X\|\times\sum_{j=1}^{n}\Big{\\{}2\sqrt{2}\delta_{j}m_{j}\sqrt{m_{j}m_{j-1}}N_{j}^{-\frac{1}{m_{j}}}\times\prod_{i=j+1}^{n}\sigma_{i}$
$\displaystyle\times\prod_{l=1}^{j-1}(2\sqrt{2}\delta_{l}m_{l}\sqrt{m_{l}m_{l-1}}N_{l}^{-\frac{1}{m_{l}}}+\sigma_{l})\Big{\\}}.$
(12)

###### Proof.

Note that since $\sigma$ is an $L-$Lipschitz continuous function with
$\sigma(0)=0,$ we have

$\displaystyle\|\sigma(v)\|=\|\sigma(v)-\sigma(0)\|\leq L\|v-0\|=L\|v\|$

for any vector $v$. Using this, for $j=1,\cdots,n,$ we have

$\displaystyle\|W_{n}\sigma\cdots W_{j}\sigma Q_{j-1}\sigma Q_{j-2}\cdots
Q_{1}X-W_{n}\sigma\cdots W_{j+1}\sigma Q_{j}\sigma Q_{j-1}\sigma Q_{j-2}\cdots
Q_{1}X\|$ $\displaystyle\leq
L^{n-j}\|W_{n}\|\cdots\|W_{j+1}\|\times\|W_{j}-Q_{j}\|\|\sigma Q_{j-1}\sigma
Q_{j-2}\cdots Q_{1}X\|$ $\displaystyle\leq
L^{n-1}\|W_{n}\|\cdots\|W_{j+1}\|\times\|W_{j}-Q_{j}\|\times\|Q_{j-1}\|\cdots\|Q_{1}\|\|X\|.$

Next, using Lemma 5.1, Lemma 5.2, and triangle inequality, we get

$\displaystyle\|f(X)-f_{Q}(X)\|=\|W_{n}(\sigma(\cdots\sigma(W_{1}x)\cdots))-Q_{n}(\sigma(\cdots\sigma(Q_{1}x)\cdots))\|$
$\displaystyle\leq\sum_{j=1}^{n}\|W_{n}\sigma\cdots W_{j}\sigma Q_{j-1}\sigma
Q_{j-2}\cdots Q_{1}X-W_{n}\sigma\cdots W_{j+1}\sigma Q_{j}\sigma Q_{j-1}\sigma
Q_{j-2}\cdots Q_{1}X\|$
$\displaystyle\leq\sum_{j=1}^{n}L^{n-1}\|W_{n}\|\cdots\|W_{j+1}\|\times\|W_{j}-Q_{j}\|\times\|Q_{j-1}\|\cdots\|Q_{1}\|\|X\|$
$\displaystyle\leq
L^{n-1}\|X\|\times\sum_{j=1}^{n}\Big{\\{}2\sqrt{2}\delta_{j}m_{j}\sqrt{m_{j}m_{j-1}}N_{j}^{-\frac{1}{m_{j}}}\times\prod_{i=j+1}^{n}\sigma_{i}$
$\displaystyle\times\prod_{l=1}^{j-1}(2\sqrt{2}\delta_{l}m_{l}\sqrt{m_{l}m_{l-1}}N_{l}^{-\frac{1}{m_{l}}}+\sigma_{l})\Big{\\}}.$

∎

Note that $\\{\sigma_{i}\\}_{i=1}^{n},\\{m_{i}\\}_{i=0}^{n},$ and $L$ are
constants determined by the given FNN $f(x).$ Therefore, the upper bound in
(5.3) can be only controlled by the step sizes $\delta_{i}$ and the numbers of
frame elements $N_{i}$. Once we fix $\delta_{i}$’s, then the upper bound in
(5.3) can be written as $\sum_{j=1}^{n}O(N_{j}^{-1/m_{j}})\|X\|.$ This shows
we can leverage the redundancy of frames for the accuracy of quantized neural
networks. On the other hand, if we fix frames $F_{1},\cdots,F_{n}$, then the
upper bound in (5.3) depends only on $\delta_{i}$’s and can be written as
$\sum_{i=1}^{n}O(\delta_{i})\|X\|.$ Therefore, smaller $\delta_{i}$’s and
larger $N_{i}$’s would generate a quantized neural network with higher
accuracy.

When the number of neurons in each hidden layer is the same, that is when
$m_{1}=\cdots=m_{n-1}$, then we have a simplified version of Theorem 5.3.

######  Corollary 5.4.

Let $f(x)=W_{n}(\sigma(\cdots\sigma(W_{1}x)\cdots))$ be a feed-forward neural
network with $n$ layer with $m_{1}=m_{2}=\cdots=m_{n-1}=m$. Fix a FUNTF
$F\subset\mathbb{R}^{m}$ with $N$ elements and a stepsize $\delta.$ Choose a
permutation $p$ of $\\{1,2,\cdots,N\\}$ that satisfies (8). Now, use Algorithm
1 to quantize $W_{1},\cdots,W_{n-1}$ and $W_{n}^{T}$ with the same $F,\delta,$
and $p$. Let $M=\max\\{m_{0},m,m_{n}\\}.$ Then, the quantized neural network
$f_{Q}(x)=Q_{n}(\sigma(\cdots\sigma(Q_{1}x)\cdots))$ satisfies

$\displaystyle\|f(X)-f_{Q}(X)\|\leq 2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}L^{n-1}\|X\|\sum_{j=1}^{n}\Big{\\{}\prod_{i=j+1}^{n}\sigma_{i}\prod_{l=1}^{j-1}(2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}+\sigma_{l})\Big{\\}}$ (13)

for any data $X\in\mathbb{R}^{m_{0}}.$

###### Proof.

By Lemma 5.1, we have $\|W_{i}-Q_{i}\|\leq
2\sqrt{2}\delta_{i}m_{i}\sqrt{m_{i-1}m_{i}}N_{i}^{-\frac{1}{m_{i}}}\leq
2\sqrt{2}\delta M^{2}N^{-\frac{1}{m}}$ for $i=1,\cdots,n-1.$ For $i=n,$ we
have $\|W_{n}-Q_{n}\|=\|W_{n}^{T}-Q_{n}^{T}\|\leq
2\sqrt{2}\delta_{n}m_{n-1}\sqrt{m_{n-1}m_{n}}N_{n}^{-\frac{1}{m_{n-1}}}\leq
2\sqrt{2}\delta M^{2}N^{-\frac{1}{m}}$. These estimates yield
$\|Q_{i}\|\leq\|W_{i}-Q_{i}\|+\|W_{i}\|\leq 2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}+\sigma_{i}.$ Therefore, from the proof of Theorem 5.3,
we get

$\displaystyle\|f(X)-f_{Q}(X)\|\leq
L^{n-1}\|X\|\times\sum_{j=1}^{n}\Big{\\{}\prod_{i=j+1}^{n}\sigma_{i}\times\|W_{j}-Q_{j}\|\times\|Q_{j-1}\|\cdots\|Q_{1}\|\Big{\\}}$
$\displaystyle\leq L^{n-1}\|X\|\sum_{j=1}^{n}\Big{\\{}2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}\prod_{i=j+1}^{n}\sigma_{i}\prod_{l=1}^{j-1}(2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}+\sigma_{l})\Big{\\}}$ $\displaystyle=2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}L^{n-1}\|X\|\sum_{j=1}^{n}\Big{\\{}\prod_{i=j+1}^{n}\sigma_{i}\prod_{l=1}^{j-1}(2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}+\sigma_{l})\Big{\\}}.$

∎

If we use a FUNTF for $\mathbb{R}^{m}$ with $N$ elements where
$N\geq\Big{(}\frac{2\sqrt{2}\delta
M^{2}}{\min\\{\sigma_{1},\cdots,\sigma_{n}\\}}\Big{)}^{m},$ then we have the
following simplification.

######  Corollary 5.5.

If we have $N\geq\Big{(}\frac{2\sqrt{2}\delta
M^{2}}{\min\\{\sigma_{1},\cdots,\sigma_{n}\\}}\Big{)}^{m}$ in Corollary 5.4,
then

$\displaystyle\|f(X)-f_{Q}(X)\|\leq\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}L^{n-1}\|X\|\prod_{i=1}^{n}\sigma_{i}\sum_{j=1}^{n}\frac{2^{j}}{\sigma_{j}},$

for any input data $X\in\mathbb{R}^{m_{0}}.$

###### Proof.

$N\geq\Big{(}\frac{2\sqrt{2}\delta
M^{2}}{\min\\{\sigma_{1},\cdots,\sigma_{n}\\}}\Big{)}^{m}$ implies
$2\sqrt{2}\delta
m^{2}N^{-\frac{1}{m}}\leq\min\\{\sigma_{1},\cdots,\sigma_{n}\\}.$ Hence we
have

$\displaystyle\prod_{i=j+1}^{n}\sigma_{i}\prod_{l=1}^{j-1}(2\sqrt{2}\delta
M^{2}N^{-\frac{1}{m}}+\sigma_{l})\leq\prod_{i=j+1}^{n}\sigma_{i}\prod_{l=1}^{j-1}(\sigma_{l}+\sigma_{l})=\frac{2^{j-1}}{\sigma_{j}}\prod_{i=1}^{n}\sigma_{i}.$

Applying this to (13) yields the result. ∎

Note that the above results are for general FUNTFs. On the other hand, some
special families of FUNTFs yield better error estimates. For example, harmonic
frame $H^{d}_{N}$ is a FUNTF for $\mathbb{R}^{d}$ with $N$ elements that
satisfy $\sigma(H^{d}_{N},p)\leq\frac{2\pi(d+1)}{\sqrt{3}}$ for identity
permutation $p$. This holds for any $N\geq d$, see [4] for details. If we use
harmonic frames $\\{H^{m_{i}}_{N_{i}}\\}_{i=1}^{n}$ and identity permutation
to quantize weight matrices $W_{i}$’s using Algorithm 1, then one can easily
prove a variant of Lemma 5.1:

$\|W_{i}-Q_{i}\|\leq\frac{\delta_{i}m_{i}\sqrt{m_{i-1}}}{2N_{i}}\Big{(}\frac{2\pi(m_{i}+1)}{\sqrt{3}}+1\Big{)}\leq\frac{\delta_{i}m_{i}\sqrt{m_{i-1}}}{2N_{i}}\times\frac{8\pi+\sqrt{3}}{3\sqrt{3}}m_{i}.$

The last inequality holds since we assume $m_{i}\geq 3$ for all $i$’s. Using
this, we can show (5.3) can be rewritten as an explicit upper bound for
harmonic frames, which is a stronger upper bound in terms of $N_{i}$’s:

$\displaystyle\|f(X)-f_{Q}(X)\|$ $\displaystyle\leq
L^{n-1}\|X\|\times\sum_{j=1}^{n}\Big{\\{}\frac{(8\pi+\sqrt{3})}{6\sqrt{3}}\delta_{j}m_{j}\sqrt{m_{j}m_{j-1}}N_{j}^{-1}\times\prod_{i=j+1}^{n}\sigma_{i}$
$\displaystyle\times\prod_{l=1}^{j-1}(\frac{(8\pi+\sqrt{3})}{6\sqrt{3}}\delta_{l}m_{l}\sqrt{m_{l}m_{l-1}}N_{l}^{-1}+\sigma_{l})\Big{\\}}.$
(14)

That is, if we treat $\delta_{i}$’s as fixed constants, then we can say
$\|f(X)-f_{Q}(X)\|\leq\sum_{i=1}^{n}O(N_{i}^{-1})\|X\|.$ We can get similar
results when we use families of frames such as harmonic frames, where their
frame variations are uniformly bounded. These frames may help us to construct
a quantized network with higher accuracy.

###  5.2 Neural Networks with Residual Blocks

We now prove error estimates for residual networks. Again, for convenience, we
follow the assumptions from Section 2 and omit the biases in our analysis.
Recall that from (2), the weight matrices $W_{i,1}$’s and $W_{i,2}$’s are all
$k\times k$ square matrices. Hence we quantize all the weight matrices using
the same frame $F$ with $N$ elements, the same permutation $p$ of
$\\{1,2,\cdots,N\\}$ that satisfies (8), the same constant $K$, and the same
step size $\delta$ as in Algorithm 1. Note that the quantized weight matrices
$Q_{i,1}$’s and $Q_{i,2}$’s are also $k\times k$ matrices.

######  Theorem 5.6.

Let $g(x)$ be a residual neural network with $n$ residual blocks (2). Let

$\lambda=\max_{i=1,\cdots,n}\Big{\\{}\max\\{\|W_{i,2}\|,\|W_{i,1}\|\\}\Big{\\}}.$

Let $g_{Q}(x)$ be the quantized residual neural network of $g(x)$ (4) from
Algorithm 1. Then for any input $X\in\mathbb{R}^{k},$ we have

$\displaystyle\|g(X)-g_{Q}(X)\|$ $\displaystyle\leq 4\delta
k\sqrt{k(k+3)}(\delta k\sqrt{k(k+3)}+\lambda)N^{-\frac{1}{k}}\|X\|$
$\displaystyle\times\sum_{j=0}^{n-1}(\lambda^{2}+1)^{j}\Big{(}(2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}+\lambda)^{2}+1\Big{)}^{n-1-j}.$ (15)

###### Proof.

For simplicity, let $A=4\delta k\sqrt{k(k+3)}(\delta
k\sqrt{k(k+3)}+\lambda)N^{-\frac{1}{k}}$ and $B=(2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}+\lambda)^{2}+1$. Let $y_{0}(x)=y_{0,Q}(x)=x$
and define $y_{i}(x)=z^{[i]}\circ\sigma\cdots\circ\sigma\circ z^{[1]}(x)$, and
$y_{i,Q}(x)=z_{Q}^{[i]}\circ\sigma\cdots\circ\sigma\circ z_{Q}^{[1]}(x)$ for
$i=1,\cdots,n$. We shall show that

$\displaystyle\|y_{i}(X)-y_{i,Q}(X)\|\leq
A\|X\|\sum_{j=0}^{i-1}(\lambda^{2}+1)^{j}B^{i-1-j},$ (16)

for $i=1,\cdots,n.$ Note that we have recurrence relations:

$\displaystyle
y_{i}(X)=W_{i,2}(\sigma(W_{i,1}(\sigma(y_{i-1}(X)))))+\sigma(y_{i-1}(X)),$
(17) $\displaystyle
y_{i,Q}(X)=Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1,Q}(X)))))+\sigma(y_{i-1,Q}(X)).$
(18)

By using the triangle inequality repeatedly, we obtain:

$\displaystyle\|y_{i}(X)-y_{i,Q}(X)\|$
$\displaystyle\leq\|W_{i,2}(\sigma(W_{i,1}(\sigma(y_{i-1}(X)))))-Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1,Q}(X)))))\|$
$\displaystyle+\|\sigma(y_{i-1}(X))-\sigma(y_{i-1,Q}(X))\|$
$\displaystyle\leq\|W_{i,2}(\sigma(W_{i,1}(\sigma(y_{i-1}(X)))))-W_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))\|$
$\displaystyle+\|W_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))-Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))\|$
$\displaystyle+\|Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))-Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1,Q}(X)))))\|$
$\displaystyle+\|\sigma(y_{i-1}(X))-\sigma(y_{i-1,Q}(X))\|.$ (19)

Since $\sigma$ is ReLU, we have $\|\sigma(x)-\sigma(y)\|\leq\|x-y\|$ and
$\|\sigma(x)\|\leq\|x\|$ for any vectors $x,y\in\mathbb{R}^{k}.$ Using this
fact, the first term in (5.2) is bounded by:

$\displaystyle\|W_{i,2}(\sigma(W_{i,1}(\sigma(y_{i-1}(X)))))-W_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))\|$
$\displaystyle\leq\|W_{i,2}\|\|W_{i,1}-Q_{i,1}\|\|y_{i-1}(X)\|\leq\lambda\|W_{i,1}-Q_{i,1}\|\|y_{i-1}(X)\|.$

The second term in (5.2) is bounded by:

$\displaystyle\|W_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))-Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))\|$
$\displaystyle\leq\|W_{i,2}-Q_{i,2}\|\|\sigma(Q_{i,1}(\sigma(y_{i-1}(X))))\|\leq\|W_{i,2}-Q_{i,2}\|\|Q_{i,1}\|\|y_{i-1}(X)\|.$

The third term in (5.2) is bounded by:

$\displaystyle\|Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1}(X)))))-Q_{i,2}(\sigma(Q_{i,1}(\sigma(y_{i-1,Q}(X)))))\|$
$\displaystyle\leq\|Q_{i,2}\|\|Q_{i,1}\|\|y_{i-1}(X)-y_{i-1,Q}(X)\|.$

Finally, the fourth term in (5.2) is bounded by:

$\displaystyle\|\sigma(y_{i-1}(X))-\sigma(y_{i-1,Q}(X))\|\leq\|y_{i-1}(X)-y_{i-1,Q}(X)\|.$

From the four inequalities above, we obtain:

$\displaystyle\|y_{i}(X)-y_{i,Q}(X)\|$
$\displaystyle\leq\\{\lambda\|W_{i,1}-Q_{i,1}\|+\|W_{i,2}-Q_{i,2}\|\|Q_{i,1}\|\\}\times\|y_{i-1}(X)\|$
$\displaystyle+\\{\|Q_{i,2}\|\|Q_{i,1}\|+1\\}\times\|y_{i-1}(X)-y_{i-1,Q}(X)\|.$
(20)

From Lemma 5.1 and Lemma 5.2, we have
$\|W_{i,1}-Q_{i,1}\|,\|W_{i,2}-Q_{i,2}\|\leq 2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}$ and $\|Q_{i,1}\|,\|Q_{i,2}\|\leq 2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}+\lambda.$ Applying these to (5.2), we have:

$\displaystyle\|y_{i}(X)-y_{i,Q}(X)\|$ $\displaystyle\leq 2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}(\lambda+2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}+\lambda)\|y_{i-1}(X)\|$
$\displaystyle+\Big{(}(2\delta
k\sqrt{k(k+3)}N^{-\frac{1}{k}}+\lambda)^{2}+1\Big{)}\|y_{i-1}(X)-y_{i-1,Q}(X)\|$
$\displaystyle=A\|y_{i-1}(X)\|+B\|y_{i-1}(X)-y_{i-1,Q}(X)\|.$ (21)

From the recurrence relations (17) and (18), one can easily check that

$\displaystyle\|y_{i}(X)\|$
$\displaystyle=\|W_{i,2}(\sigma(W_{i,1}(\sigma(y_{i-1}(X)))))+\sigma(y_{i-1}(X))\|$
$\displaystyle\leq\|W_{i,2}\|\|W_{i,1}\|\|\|y_{i-1}(X)\|+\|y_{i-1}(X)\|\leq(\lambda^{2}+1)\|y_{i-1}(X)\|.$
(22)

Using (5.2) repeatedly, we obtain
$\|y_{i}(X)\|\leq(\lambda^{2}+1)^{i}\|y_{0}(X)\|=(\lambda^{2}+1)^{i}\|X\|,$
which together with (5.2) implies:

$\displaystyle\|y_{i}(X)-y_{i,Q}(X)\|$ $\displaystyle\leq
A\|y_{i-1}(X)\|+B\|y_{i-1}(X)-y_{i-1,Q}(X)\|$ $\displaystyle\leq
A(\lambda^{2}+1)^{i-1}\|X\|+B\|y_{i-1}(X)-y_{i-1,Q}(X)\|.$ (23)

To prove (16), we proceed by induction. When $i=1,$ (5.2) yields:

$\|y_{1}(X)-y_{1,Q}(X)\|\leq
A(\lambda^{2}+1)^{0}\|X\|+B\|y_{0}(X)-y_{0,Q}(X)\|=A\|X\|.$

Therefore, (16) holds when $i=1.$ Now, let’s assume that (16) holds for $i=t.$
When $i=t+1,$ by (5.2) and induction hypothesis, we have

$\displaystyle\|y_{t+1}(X)-y_{t+1,Q}(X)\|\leq
A(\lambda^{2}+1)^{t}\|X\|+B\|y_{t}(X)-y_{t,Q}(X)\|$ $\displaystyle\leq
A\|X\|\\{(\lambda^{2}+1)^{t}+B\sum_{j=0}^{t-1}(\lambda^{2}+1)^{j}B^{t-1-j}\\}=A\|X\|\sum_{j=0}^{t}(\lambda^{2}+1)^{j}B^{t-j}.$

Hence, (16) holds. Note that $g(x)=y_{n}(x)$ and $g_{Q}(x)=y_{n,Q}(x).$ Taking
$i=n$ in (16) completes the proof. ∎

Theorem 5.6 shows that using smaller step size $\delta$ and larger $N$ can
generate a quantized neural network with higher accuracy. If we treat $\delta$
as a fixed constant, we can view the upper bound in (5.6) as
$O(N^{-1/k})\|X\|$. This is the result for general FUNTFs. If we use a family
of frames with uniformly bounded variation like harmonic frames, then one can
also prove that the upper bound in (5.6) is $O(N^{-1})\|X\|$ if we treat
$\delta$ as a fixed constant.

##  6 Numerical Results

In this section, we present numerical results which demonstrate the
performance of our proposed algorithm. We analyze the accuracy of frame
quantized networks for a classification task with the MNIST dataset. For our
implementation, we used the same $K$ and step size $\delta$ for quantizing
each layer as well as the residual blocks. The nonlinear activation function
$\sigma$ is ReLU. We used harmonic frames $H^{d}_{N}$ and identity permutation
for Algorithm 1. We trained each neural network 10 times and quantized it with
different values of $N$ and $\delta,$ where $N$ is the number of elements in
harmonic frames. We report the average accuracy and standard deviations.

###  6.1 Feedforward Network with 3 Layers

FNN in our experiment is $f(x)=h^{[3]}\circ\sigma\circ h^{[2]}\circ\sigma\circ
h^{[1]}(x)$ where
$h^{[1]}:\mathbb{R}^{784}\rightarrow\mathbb{R}^{256},h^{[2]}:\mathbb{R}^{256}\rightarrow\mathbb{R}^{256},$
and $h^{[3]}:\mathbb{R}^{256}\rightarrow\mathbb{R}^{10}$ are affine maps in as
in (1) without bias terms. Our results are presented in Table 1. As expected,
quantizing with smaller $\delta$’s and larger $N$’s results in higher
accuracy.

$N$ | $\delta=1/16$ | $\delta=1/8$ | $\delta=1/4$ | $\delta=1/2$ | $\delta=1$
---|---|---|---|---|---
256 | $97.53\pm 0.24\%$ | $97.03\pm 0.35\%$ | $93.39\pm 1.92\%$ | $63.76\pm 4.54\%$ | $22.85\pm 3.67\%$
320 | $97.62\pm 0.19\%$ | $97.35\pm 0.29\%$ | $95.47\pm 1.34\%$ | $84.93\pm 4.66\%$ | $50.30\pm 8.24\%$
384 | $97.65\pm 0.25\%$ | $97.46\pm 0.28\%$ | $95.99\pm 1.59\%$ | $90.68\pm 3.80\%$ | $62.48\pm 6.54\%$
448 | $97.68\pm 0.22\%$ | $97.55\pm 0.24\%$ | $96.92\pm 0.59\%$ | $93.75\pm 2.03\%$ | $76.66\pm 5.25\%$
512 | $97.68\pm 0.25\%$ | $97.57\pm 0.25\%$ | $97.20\pm 0.30\%$ | $95.71\pm 1.36\%$ | $86.97\pm 1.92\%$
Table 1: Frame Quantization for FNN with 3 layers. The accuracy for the
trained neural network is $97.72\pm 0.21\%$.

We now demonstrate the connection between theory and numerical results. Since
we are using harmonic frames with the same $N$ and $\delta$ for quantizing
each layer, the error bound (5.1) can be represented as $\|f(X)-f_{Q}(X)\|\leq
C\delta N^{-1}\|X\|,$ where $C$ is a positive constant depending only on the
FNN $f$. In Figure 2 we present the worst-case error. The worst-case error
decreases as $N$ increases or $\delta$ decreases, but it may be large if the
worst-case scenario corresponds to large $\|X\|$. To remove the dependence on
$X$ and to focus on the dependence of $N$ and $\delta,$ we compute the average
and represent the error bound as $\mathrm{E}_{X}\|f(X)-f_{Q}(X)\|\leq
C\times\mathrm{E}\|X\|\times\delta N^{-1}.$ Note that $\mathrm{E}\|X\|$ is now
a constant depending only on the MNIST dataset, so by taking logarithm on both
sides, we can write $\log\mathrm{E}_{X}[\|f(X)-f_{Q}(X)\|\times N/\delta]\leq
K$, for some constant $K>0$. In Figure 2, we present the values of
$\log\mathrm{E}_{X}[\|f(X)-f_{Q}(X)\|\times N/\delta].$ We can see that the
values are bounded and behave approximately constant as $N$ grows. These
numerical results imply that our theoretical error bound is tight in terms of
$\delta$ and $N.$

Figure 1: Worst-case error $\|f(X)-f_{Q}(X)\|$ for FNN with 3 layers.

Figure 2: $\log\mathrm{E}_{X}[\|f(X)-f_{Q}(X)\|\times N/\delta]$ for FNN with
3 layers.

###  6.2 Network with 2 Residual Blocks

Neural network in our experiment has a form of $g(x)=h^{[2]}\circ\sigma\circ
z^{[2]}\circ\sigma\circ z^{[1]}\circ\sigma\circ h^{[1]}(x)$ where
$h^{[1]}:\mathbb{R}^{784}\rightarrow\mathbb{R}^{256}$ and
$h^{[2]}:\mathbb{R}^{256}\rightarrow\mathbb{R}^{10}$ are affine maps in (1),
and $z^{[1]},z^{[2]}:\mathbb{R}^{256}\rightarrow\mathbb{R}^{256}$ are residual
blocks in (2). Our results are listed in Table 2. Quantizing with smaller
$\delta$’s and larger $N$’s results in higher accuracy.

$N$ | $\delta=1/16$ | $\delta=1/8$ | $\delta=1/4$ | $\delta=1/2$ | $\delta=1$
---|---|---|---|---|---
256 | $97.44\pm 0.28\%$ | $96.17\pm 0.67\%$ | $77.20\pm 6.23\%$ | $15.61\pm 2.89\%$ | $9.68\pm 2.55\%$
320 | $97.52\pm 0.32\%$ | $97.09\pm 0.35\%$ | $92.54\pm 1.19\%$ | $41.03\pm 6.94\%$ | $11.67\pm 2.58\%$
384 | $97.60\pm 0.19\%$ | $97.23\pm 0.27\%$ | $95.12\pm 0.62\%$ | $66.27\pm 8.36\%$ | $17.84\pm 2.83\%$
448 | $97.64\pm 0.22\%$ | $97.37\pm 0.28\%$ | $96.35\pm 0.42\%$ | $85.28\pm 3.53\%$ | $28.96\pm 6.04\%$
512 | $97.66\pm 0.20\%$ | $97.54\pm 0.25\%$ | $97.00\pm 0.29\%$ | $92.30\pm 3.11\%$ | $45.80\pm 10.09\%$
Table 2: Frame Quantization for Neural Network with 2 Residual Blocks. The
accuracy for the trained neural network is $97.72\pm 0.20\%$.

###  6.3 1-Bit Quantization

1-bit quantization of neural network, in other words, binarization of neural
network, refers to a method of compressing weights or even activations into
1-bit numbers. For example, [7] quantized the weights of the neural networks
to $\\{-1,1\\}.$ Mathematical theories were also developed in 1-bit
$\Sigma\Delta$ quantization for bandlimited signals [12] and approximation
capabilities of 1-bit neural networks [13].

In our method, since we are storing $q^{i}_{jk}$’s appearing in the quantized
expansions, we will say 1-bit quantization is obtained when all $q^{i}_{jk}$’s
are in $\\{-a,a\\}$ for some positive number $a>0.$ Note that once we choose
appropriate $K\in\mathbb{N}$ and step size $\delta>0,$ our method forces
$q^{i}_{jk}$’s as elements of the midrise quantization alphabet
$A^{\delta}_{K}$ (7). If we recall the structure of
$A^{\delta}_{K}=\\{(-K+\frac{1}{2})\delta,(-K+\frac{3}{2})\delta,\cdots,-\frac{1}{2}\delta,\frac{1}{2}\delta,\cdots,(K-\frac{1}{2})\delta\\},$
one can easily see that $A^{\delta}_{K}$ achieves a form of $\\{-a,a\\}$ if
and only if $K=1.$

Therefore in our experiments for 1-bit quantization, we set $K=1$ for all
layers and found the uniform step size $\delta$ that satisfies (9) for
$i=1,\cdots,n.$ For both neural networks in the previous experiments, setting
$\delta=8$ enables us to set $K=1$. Our 1-bit quantization results are in
Table 3 and Table 4.

Now we shall explain how our algorithm can benefit in storage while
maintaining the accuracy. Consider 1-bit quantization for a neural network
with 3 layers. We use a harmonic frame $H^{256}_{N}$ to quantize the first and
second weight matrices $W_{1}$ and $W_{2},$ the total bits that we need to
store the quantized matrices $Q_{1}$ and $Q_{2}$ is $1\times 784\times
N+1\times 256\times N=1040N$ bits. The total bits that we need to represent
the weight matrices $W_{1}$ and $W_{2}$ are $32\times 256\times 784+32\times
256\times 256=8192\times 1040$ bits. Suppose that we use $N=7000$. Then the
total bits that we can save is $8192\times 1040-1040N=1192\times 1040$ bits,
but we have an average accuracy of $97.29\%$ for the quantized networks, where
the average accuracy for the trained neural networks is $97.72\%.$ So we can
even benefit in storage for a 1-bit quantization case with a small sacrifice
in the accuracy.

$N$ | 1000 | 2000 | 3000 | 4000 | 5000 | 6000 | 7000
---|---|---|---|---|---|---|---
Average | 36.18% | 74.09% | 88.47% | 94.62% | 96.04% | 96.83% | 97.29%
Standard Deviation | 7.65 | 4.71 | 1.82 | 0.44 | 0.82 | 0.36 | 0.25
Table 3: 1-Bit Frame Quantization for FNN with 3 layers $N$ | 1000 | 2000 | 3000 | 4000 | 5000 | 6000 | 7000
---|---|---|---|---|---|---|---
Average | 14.12% | 31.52% | 66.93% | 86.47% | 92.88% | 95.28% | 96.30%
Standard Deviation | 2.52 | 6.56 | 5.69 | 4.04 | 1.44 | 0.64 | 0.50
Table 4: 1-Bit Frame Quantization for Neural Network with 2 Residual Blocks

##  7 Conclusions and Future Work

In this paper, we proposed a PTQ method with a rigorous mathematical analysis
of the error estimates between a neural network and its quantized network. We
use frame theory in neural network quantization for the first time. Also, we
demonstrate that 1-bit quantization with our method has a benefit in storage
while attaining accuracy near the accuracy of the original neural network. But
still, there are many open questions left. Here, we list some of them.

  1. 1.

In this paper we only focus on using FUNTFs for $\mathbb{R}^{d}.$ Designing a
quantization method using different types of frames would be a new task for
the future.

  2. 2.

Our method uses first-order $\Sigma\Delta$ quantization, but one may consider
using higher-order $\Sigma\Delta$ quantization. In this case, how much can we
benefit from the error bound in terms of the number of frame elements? Also,
which quantization rule should be used for higher-order schemes?

  3. 3.

To the best of our knowledge, this is the first attempt to adopt frame theory
to neural network quantization. We were able to explain the accuracy and
storage benefits, but we must admit we do not immediately see a connection
between using frames and saving inference time. To develop a new frame
quantization algorithm that reduces inference time, we may need to use some
specific frame.

## References

  * [1] Banner, Ron, Yury Nahshan, and Daniel Soudry. Post training 4-bit quantization of convolutional networks for rapid-deployment. Advances in Neural Information Processing Systems 32 (2019).
  * [2] Benedetto, John J., and Onur Oktay. Pointwise comparison of PCM and $\Sigma\Delta$ quantization. Constructive Approximation 32 (2010): 131-158.
  * [3] Benedetto, John J., Alexander M. Powell, and Özgür Yılmaz. Second-order Sigma–Delta ($\Sigma\Delta$) quantization of finite frame expansions. Applied and Computational Harmonic Analysis 20.1 (2006): 126-148.
  * [4] Benedetto, John J., Alexander M. Powell, and Özgür Yılmaz. Sigma-delta ($\Sigma\Delta$) quantization and finite frames. IEEE Transactions on Information Theory 52.5 (2006): 1990-2005.
  * [5] Benedetto, John J., Onur Oktay, and Aram Tangboondouangjit. Complex Sigma–Delta quantization algorithms for finite frames. Contemp. Math. 464 (2008): 27–51.
  * [6] Casazza, Peter G., and Gitta Kutyniok, eds. Finite frames: Theory and applications. Springer Science & Business Media (2012).
  * [7] Courbariaux, Matthieu, Yoshua Bengio, and Jean-Pierre David. Binaryconnect: Training deep neural networks with binary weights during propagations. Advances in Neural Information Processing Systems 28 (2015).
  * [8] Daubechies, Ingrid, and Ron DeVore. Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order. Annals of Mathematics 158.2 (2003): 679-710.
  * [9] Gholami, Amir, et al. A survey of quantization methods for efficient neural network inference. Low-Power Computer Vision. Chapman and Hall/CRC (2022): 291-326.
  * [10] Grohs, Philipp, and Gitta Kutyniok, eds. Mathematical aspects of deep learning. Cambridge University Press (2022).
  * [11] Güntürk, C. Sinan. Approximating a bandlimited function using very coarsely quantized data: improved error estimates in sigma-delta modulation. Journal of the American Mathematical Society 17.1 (2004): 229-242.
  * [12] Güntürk, C. Sinan. One‐bit sigma‐delta quantization with exponential accuracy. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 56.11 (2003): 1608-1630.
  * [13] Güntürk, C. Sinan, and Weilin Li. Approximation of functions with one-bit neural networks. arXiv preprint arXiv:2112.09181 (2021).
  * [14] Güntürk, C. Sinan, et al. Sigma delta quantization for compressed sensing. 2010 44th Annual Conference on Information Sciences and Systems (CISS). IEEE, 2010.
  * [15] Güntürk, C. Sinan, et al. Sobolev duals for random frames and $\Sigma\Delta$ quantization of compressed sensing measurements. Foundations of Computational mathematics 13 (2013): 1-36.
  * [16] Guo, Cong, et al. SQuant: On-the-fly data-free quantization via diagonal hessian approximation. arXiv preprint arXiv:2202.07471 (2022).
  * [17] He, Kaiming, et al. Deep residual learning for image recognition. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2016).
  * [18] Hubara, Itay, et al. Binarized neural networks. Advances in Neural Information Processing Systems 29 (2016).
  * [19] Krahmer, Felix, Rayan Saab, and Özgür Yilmaz. Sigma–delta quantization of sub-gaussian frame expansions and its application to compressed sensing. Information and Inference: A Journal of the IMA 3.1 (2014): 40-58.
  * [20] Kummer, Lorenz, et al. Adaptive Precision Training (AdaPT): A dynamic quantized training approach for DNNs. Proceedings of the 2023 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2023.
  * [21] Long, Ziang, Penghang Yin, and Jack Xin. Recurrence of optimum for training weight and activation quantized networks. Applied and Computational Harmonic Analysis 62 (2023): 41-65.
  * [22] Lybrand, Eric, and Rayan Saab. A greedy algorithm for quantizing neural networks. The Journal of Machine Learning Research 22.1 (2021): 7007-7044.
  * [23] Maly, Johannes, and Rayan Saab. A simple approach for quantizing neural networks. Applied and Computational Harmonic Analysis 66 (2023): 138-150.
  * [24] Nagel, Markus, et al. Up or down? adaptive rounding for post-training quantization. International Conference on Machine Learning. PMLR (2020).
  * [25] Nahshan, Yury, et al. Loss aware post-training quantization. Machine Learning 110.11-12 (2021): 3245-3262.
  * [26] Rastegari, Mohammad, et al. Xnor-net: Imagenet classification using binary convolutional neural networks. European conference on computer vision. Cham: Springer International Publishing (2016).
  * [27] Saab, Rayan, Rongrong Wang, and Özgür Yılmaz. Quantization of compressive samples with stable and robust recovery. Applied and Computational Harmonic Analysis 44.1 (2018): 123-143.
  * [28] Wang, Yang. Sigma–Delta quantization errors and the traveling salesman problem. Advances in Computational Mathematics 28 (2008): 101-118.
  * [29] Wei, Xiuying, et al. Qdrop: Randomly dropping quantization for extremely low-bit post-training quantization. arXiv preprint arXiv:2203.05740 (2022).
  * [30] Yao, Zhewei, et al. Zeroquant: Efficient and affordable post-training quantization for large-scale transformers. Advances in Neural Information Processing Systems 35 (2022): 27168-27183.
  * [31] Yin, Penghang, et al. Binaryrelax: A relaxation approach for training deep neural networks with quantized weights. SIAM Journal on Imaging Sciences 11.4 (2018): 2205-2223.
  * [32] Zhang, Jinjie, and Rayan Saab. SPFQ: A Stochastic Algorithm and Its Error Analysis for Neural Network Quantization. arXiv preprint arXiv:2309.10975 (2023).
  * [33] Zhang, Jinjie, Yixuan Zhou, and Rayan Saab. Post-training quantization for neural networks with provable guarantees. SIAM Journal on Mathematics of Data Science 5.2 (2023): 373-399.
  * [34] Zhang, Jinjie, et al. Sigma-Delta and distributed noise-shaping quantization methods for random Fourier features. Information and Inference: A Journal of the IMA 13.1 (2024): iaad052.


# Deep Generative Models of Music Expectation

Ninon Lizé Masclef
<EMAIL_ADDRESS>
&T. Anderson Keller
<EMAIL_ADDRESS>

###### Abstract

A prominent theory of affective response to music revolves around the concepts
of surprisal and expectation. In prior work, this idea has been
operationalized in the form of probabilistic models of music which allow for
precise computation of song (or note-by-note) probabilities, conditioned on a
‘training set’ of prior musical or cultural experiences. To date, however,
these models have been limited to compute exact probabilities through hand-
crafted features or restricted to linear models which are likely not
sufficient to represent the complex conditional distributions present in
music. In this work, we propose to use modern deep probabilistic generative
models in the form of a Diffusion Model to compute an approximate likelihood
of a musical input sequence. Unlike prior work, such a generative model
parameterized by deep neural networks is able to learn complex non-linear
features directly from a training set itself. In doing so, we expect to find
that such models are able to more accurately represent the ‘surprisal’ of
music for human listeners. From the literature, it is known that there is an
inverted U-shaped relationship between surprisal and the amount human subjects
‘like’ a given song. In this work we show that pre-trained diffusion models
indeed yield musical surprisal values which exhibit a negative quadratic
relationship with measured subject ‘liking’ ratings, and that the quality of
this relationship is competitive with state of the art methods such as IDyOM.
We therefore present this model a preliminary step in developing modern deep
generative models of music expectation and subjective likability.

##  1 Introduction

The fields of psychology and musicology have identified expectation as a
crucial factor that conveys meaning in music [14], especially affective
response [12, 21, 26]. The malleability of musical experience underscores that
listening to music is not merely a passive activity, but an active learning
process in which expectations are formed that shape our emotional responses
[22]. Indeed, prior work has found that the sweet spot of expectation which
maximizes information learning and reward system-related responses is that of
intermediate complexity [18]. Wilhelm Wundt [30] proposed an inverted U-curve
to describe the relationship between stimulus intensity and pleasant feeling.
However, it was operationalized decades later and applied specifically to
aesthetic pleasure by Berlyne [4]. Since then, the Wundt effect has dominated
psychological research on music preference for more than two decades [7].
Specifically, the author [3] found that arousal is a predominant factor in
aesthetic preference, with three types of variables determining the level of
arousal of a stimulus input. One in particular, collative variables,
encompassing novelty, complexity, and uncertainty, has been shown to
contribute most to musical liking [2]. Among these collative variables,
predictability has been empirically shown to contribute to music preference
[29], although this finding is not unanimous [17]. Furthermore, there is a
growing body of research on serendipity as a new evaluation metric for music
recommendation systems [31, 23, 5], linking surprisal and pleasure of music.

###  1.1 Models of musical expectancy

Meyer (1956) first theorized musical anticipation by applying principles of
Gestalt psychology to the auditory domain to form an "emotional syntax of
music" [14]. Influenced by Meyer’s work, Narmour (1990) [15] developed the
Implication-Realization (I-R) model of melodic expectation, which emphasized
cognitive evaluation of the music rather than musical analysis of the stimuli.
Instead, Narmour explained that music listening is the product of two
expectation processes, one top-down and the other bottom-up [16]. A whole
tradition of predictive models of music listening was developed later in the
lineage of Meyer’s work. Pearce created the Information Dynamics of Music
(IDyOM) model of melodic expectations [20], but replaced the rules with
statistical distribution learning. IDyOM simultaneously predicts the pitch and
onset time of the next note using probabilistic prediction, and calculates the
final probability of the note using the joint probability of these two
predictions [21]. IDyOM was effective at predicting liking from surprise,
reproducing the Wundt effect along a U-shaped curve [6]. Unlike Narmour’s
model, IDyOM is not built from symbolic rules of musical knowledge. However,
it still relies on hand-crafted features such as pitch duration. Contrary to
recent diffusion models, which have billions of parameters learned from large
datasets, IDyOM has only a few trainable parameters. In contrast to Narmour,
Pearce argued that only top-down processing occurs, rather than both top-down
and bottom-up [21]. Furthermore, it is conditioned on the input of stimuli
encoded in MIDI format. Therefore, musical features based on timbral or
dynamic changes are not considered by the model. Instead, IDyOM focuses on
syntactic features, following Meyer’s argument that those features present in
symbolic music are primary to the formation of musical style [21, 14].While
symbolic music can convey emotion through expressive velocity, some affective
cues are inherent in the live recording of a piece, such as rubato [25]. The
D-REX model was designed to address this issue with a model of surprise
working on raw audio from an ecologically valid perspective of studying the
music listening experience [1]; however, the features used to compute the
surprisal values in the D-REX model are restricted to learned linear
transformations of the input, and therefore limited in their modeling
complexity.

Nowadays, predictive coding theories are becoming dominant in modeling human
expectations over time [19]. The basic premise of predictive coding is that
the brain operates as an expectation machine [9], constantly generating and
updating predictions. Namely, humans embody a Bayesian generative model that
maps beliefs to observations. As a consequence, modern generative models, such
as diffusion models, can be seen as instantiations of predictive coding.

Predictive coding theories claim that nervous system activity represents a
process of matching internally generated predictions with external stimuli
[8]. This has been demonstrated at a variety of spatial and temporal scales in
the brain including music processing [26], which has been crystallized in the
predictive coding of music (PCM) model [27].

##  2 Methods

In this work, our goal is to leverage modern deep probabilistic generative
models as measures of expectancy for music. To evaluate the quality of such a
model of expectancy, we will measure the correlation structure between the
output of our model — the estimated likelihood of the data interpreted as a
‘surprisal’ value — and a dataset of subjective human ratings of ‘liking’ for
a set of short musical pieces. Given prior work relating music expectancy and
preference, if our model is a valid model of human music expectancy, we would
therefore expect to find an inverted U-shaped curve relating the surprisal and
ratings.

To approach this goal, we begin with the baseline denoising diffusion
probabilistic models of Ho et al. (2020) [10] as they form the foundation for
much of today’s state of the art in generative modeling. As we will detail in
this section, due to the specific construction of these models, they admit an
easily computable bound on the likelihood of the data which we will use as our
approximate estimated ‘surprisal’. Furthermore, there exist open source
implementations and model weights trained on raw musical audio, allowing for
direct evaluation of such models without retraining [24]. In the following
section we give an overview of how such models operate, how to compute the
approximate likelihood, as well as how we perform analysis to accurately
compare this measure of surprisal with human listener ratings of liking.

#### Denoising Diffusion Probabilistic Models.

In brief, diffusion models can be understood as latent variable generative
models composed of both a forwards and reverse process. The forward process is
defined to start from the datapoint ${\bm{x}}_{0}$ and produce sequentially
noisier versions ${\bm{x}}_{t}$ which we call the latent variables. At the end
of the forward process, the distribution of final latent variables
${\bm{x}}_{T}$ is intended to match that of the prior, typically a standard
normal distribution. The reverse process then inverts this procedure, mapping
from the simple prior distribution
$p_{{\bm{x}}_{T}}({\bm{x}})=\mathcal{N}({\bm{x}};\mathbf{0},\mathbf{I})$ to
the complex data distribution $p_{{\bm{x}}_{0}}({\bm{x}})$ by slowly removing
noise step by step – ‘denoising’. In practice, the forwards process is Markov,
with the joint distribution (factorizing into a product of conditionals) and
the conditional distribution of each step defined as:

$q(\\{{\bm{x}}_{t}\\}_{t=1}^{T}|{\bm{x}}_{0})=\prod_{t=1}^{T}q({\bm{x}}_{t}|{\bm{x}}_{t-1}),\hskip
28.45274ptq({\bm{x}}_{t}|{\bm{x}}_{t-1})=\mathcal{N}({\bm{x}}_{t};\sqrt{\alpha_{t}}{\bm{x}}_{t-1},(1-\alpha_{t})\mathbf{I})$
(1)

where $\alpha_{1},\ldots,\alpha_{T}$ denotes the noise schedule. The reverse
process is similarly Markov, and the conditional distribution which aims to
remove the noise is often parameterized by a neural network with parameters
$\theta$:

$p_{\theta}({\bm{x}}_{t-1}|{\bm{x}}_{t})=\mathcal{N}({\bm{x}}_{t-1};\mu_{\theta}({\bm{x}}_{t},t),\Sigma_{\theta}({\bm{x}}_{t},t))$
(2)

In practice, Ho et al. (2020) [10] find that a reparamterization where the
network is trained to directly predict the noise component of ${\bm{x}}_{t}$,
($\bm{\hat{\epsilon}_{\theta}}({\bm{x}}_{t},t)\approx\bm{\epsilon}$) is easier
to optimize than predicting ${\bm{x}}_{t}$ itself.

#### Evaluating the Likelihood of Diffusion Models.

Training the parameters of denoising diffusion models can then be done by
optimizing a variational bound on the negative log-likelihood:

$\mathbb{E}[-\log
p({\bm{x}})]\leq\mathbb{E}_{q}\left[\mathcal{L}_{T}+\sum_{t=1}^{T}\mathcal{L}_{t-1}-\mathcal{L}_{0}\right]$
(3)

where $\mathcal{L}_{0}=\log p({\bm{x}}_{0}|{\bm{x}}_{1})$ is the
reconstruction loss of the true data given ${\bm{x}}_{1}$;
$\mathcal{L}_{T}=D_{KL}\left(q({\bm{x}}_{T}|{\bm{x}}_{0})||p_{{\bm{x}}_{T}}({\bm{x}})\right)$
is the prior loss, measuring the distance of the final latent variable from
the prior; and $\mathcal{L}_{t}$ is the diffusion loss over all time steps
defined below. Following this, Kingma et al. (2023) [13] show that the
diffusion loss term can be expressed simply as:

$\mathcal{L}_{t}({\bm{x}})=\mathbb{E}_{\bm{\epsilon}\sim\mathcal{N}(\mathbf{0},\mathbf{I})}\left[\frac{1}{2}\left(1-\mathrm{SNR}(t-1)/\mathrm{SNR}(t)\right)||\bm{\epsilon}-\bm{\hat{\epsilon}_{\theta}}({\bm{x}}_{t},t)||^{2}\right]$
(4)

where $\mathrm{SNR}(t)=\frac{\alpha^{2}_{t}}{1-\alpha^{2}_{t}}$. Further,
following [11] we know that $\mathcal{L}_{T}$ is close to zero when the noise
schedule is defined such that $\alpha_{T}\approx 0$. In this work, we take
this bound on the likelihood as our approximate measure of expectancy or
surprisal for each music sample in our dataset.

#### Data.

To evaluate the diffiusion models, we make use of the dataset from Gold et al.
[6] which contains 57 audio files, liking ratings from 44 subjects, and the
associated output of the IDyOM model (mean duration weighted information
content, mDW-IC) which we use as a baseline. Since we are working with pre-
trained diffusion models which operate on 5-second audio clips, we simply
break each clip into 5-second non-overlapping blocks and take the sum of the
estimated likelihoods as the total likelihood value. Although this is non-
ideal and introduces significant boundary effects, we find in practive it
works sufficiently well for this study.

#### Analysis.

To compare our surprisal value with liking ratings, we follow the procedure of
Gold et al. [6], first fitting a linear mixed effects model to the data
(python $\mathrm{statsmodels}$’s $\mathrm{mixedlm}$) and using this to adjust
each subjects rating based on their estimated individual random effects. This
allows to us account for the subjective properties of likability rating per
user, and compare them to our model which only produces a single likelihood
value per audio clip. We then compute the goodness of fit of a quadratic
function mapping from surprisal values to adjusted rating using ordinary least
squares.

##  3 Experiments

In this section we report the results of evaluating the pretrained Audio-
Diffusion model (audio-diffusion-256) from Smith [24] on the Gold et al.
(2019) [6] audio dataset. The model is trained on a dataset of over 20,000 mel
spectrograms of resolution 256x256 computed using a sampling rate of 22050 Hz,
a window length of 2048, and a stride of 512.

#### Measuring the Wundt Effect.

As a primary result of this study, we seek to discover if an inverted U-shape
relationship exists between the surprisal values computed by a diffusion model
and the human liking ratings from the dataset. In Figure 1, we plot the
results of our analysis for both the baseline IDyOM model (left) and the Audio
Diffusion model (right). We see that indeed the Wundt effect is present, with
the diffusion model exhibiting a further rightward shift of peak likeability
compared with IDyOM. From the literature [6] , this shift is consistent with
expertise and perhaps is a result of the diffusion model’s more diverse
training set compared with the IDyOM counterpart.

Figure 1: Plot of the observed Wundt effect for the IDyOM model (left) and our
proposed diffusion model (right). Data points for the adjusted human-subject
ratings of each song are plotted in blue, with the best quadratic fit model
plotted in orange.

#### Goodness of Fit.

To evaluate the quality of the above fit, in Table 1 we evaluate standard
goodness of fit measures compared with the IDyOM model (such as $R^{2}$, Log-
likelihood, AIC and BIC). We see that fitted polynomial resulting from the
diffusion model output achieves a higher likelihood, and better AIC/BIC
values, with a lower $R^{2}$ value due the the significant inter-subject
variability per song. Despite this lower $R^{2}$, we see that the coefficient
of the quadratic term of the polynomial is indeed negative and the fit is
highly significant (coeff=$-1.135$, 95% CI [$-1.573$ $-0.697$], $p<1e-4$).

Table 1: Goodness of fit measures for the IDyOM model and the diffusion model. We see that while the IDyOM model has a higher $R^{2}$, indicating greater variance of the data is explained, the Log-likelihood of the diffusion model is markedly lower. Surprisal Model | $R^{2}$ | Log-Likelihood | AIC | BIC
---|---|---|---|---
IDyOM | 0.240 | -1869.0 | 3744 | 3761
Audio-Diffusion | 0.062 | -1860.5 | 3727 | 3744

##  4 Discussion

This work is proposed primarily as a proof of concept that modern deep
generative models can be used to model music expectancy. We believe that the
experiments presented in this study, while not fully exploiting the power of
state of the art diffusion models, adequately demonstrate that surprise scores
from diffusion models do exhibit the Wundt effect, and thus validate the idea
that diffusion models can be used to model music expectancy. The potential
advantages of diffusion models over existing expectation models, e.g. IDyOM
and D-REX, on a practical level are the larger numbers of trainable
parameters, allowing the ingestion of larger datasets, as well as the use of
deep feature extractors which should be able to more accurately model complex
distributions. Future research endeavors should involve replicating the
experiment training on a variety of datasets, especially non-Western music,
and studying the interaction of unexpectedness with other collative variables
such as complexity and familiarity. Furthermore, as demonstrated by the low
$R^{2}$ values of our experiments, intersubject variability is significantly
challenging to capture with a single model. Significant future work should be
directed towards training of individual subject-level models of expectancy,
either through fine-tuning or self-supervised training. As a result, an
application of this work could be the construction of an individual profile of
serendipitous music recommendation systems [23]. In the same way as diffusion
models were used by Wang [28] for music recommendation, our measure of musical
expectation could predict the user’s liking profile from the audio level
instead of the user’s listening trajectory. In addition, it would be useful to
compare the likelihood score of the diffusion model with biosignal correlates
of surprise, such as event-related potentials (ERPs), as done in [1].

## References

  * [1] Ellie Bean Abrams, Eva Muñoz Vidal, Claire Pelofi, and Pablo Ripollés.  Retrieving musical information from neural data: how cognitive features enrich acoustic ones, December 2022.  Pages: 160-168 Publication Title: Proceedings of the 23rd International Society for Music Information Retrieval Conference Publisher: ISMIR.
  * [2] D. E. Berlyne.  Aesthetics and psychobiology.  Aesthetics and psychobiology. Appleton-Century-Crofts, East Norwalk, CT, US, 1971.  Pages: xiv, 336.
  * [3] Daniel E. Berlyne.  Conflict, arousal and curiosity.  Martino Publishing, Mansfield Centre, CT, 1960.
  * [4] Anthony Chmiel and Emery Schubert.  Back to the inverted-U for music preference: A review of the literature.  Psychology of Music, 45(6):886–909, November 2017.  Publisher: SAGE Publications Ltd.
  * [5] Zhe Fu and Xi Niu.  Modeling Users’ Curiosity in Recommender Systems.  ACM Transactions on Knowledge Discovery from Data, 2023.  Just Accepted.
  * [6] Benjamin P. Gold, Marcus T. Pearce, Ernest Mas-Herrero, Alain Dagher, and Robert J. Zatorre.  Predictability and Uncertainty in the Pleasure of Music: A Reward for Learning?  Journal of Neuroscience, 39(47):9397–9409, November 2019.  Publisher: Society for Neuroscience Section: Research Articles.
  * [7] David Hargreaves and A. North.  Hargreaves. D.J. & North, A.C. (2010). Experimental aesthetics and liking for music. In P. N. Juslin and J. A. Sloboda (eds.), The Handbook of Music and Emotion: Theory, Research, Applications. Oxford: OUP, pp. 515-546. ISBN 978-0-19-923014-3., 2010.
  * [8] Hauke R. Heekeren, Sean Marrett, and Leslie G. Ungerleider.  The neural systems that mediate human perceptual decision making.  Nature Reviews. Neuroscience, 9(6):467–479, June 2008.
  * [9] Hermann von Helmholtz.  Handbuch der physiologischen Optik.  Allgemeine Encyklopädie der Physik. Voss, Leipzig, 1867.  OCLC: 3431763.
  * [10] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising Diffusion Probabilistic Models, December 2020.  arXiv:2006.11239 [cs, stat].
  * [11] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling.  Equivariant Diffusion for Molecule Generation in 3D, June 2022.  arXiv:2203.17003 [cs, q-bio, stat].
  * [12] Patrik N. Juslin.  From everyday emotions to aesthetic emotions: Towards a unified theory of musical emotions.  Physics of Life Reviews, 10(3):235–266, September 2013.
  * [13] Diederik P. Kingma, Tim Salimans, Ben Poole, and Jonathan Ho.  Variational Diffusion Models, April 2023.  arXiv:2107.00630 [cs, stat].
  * [14] L.B. Meyer.  Emotion and meaning in music.  Emotion and meaning in music. Chicago, University of Chicago Press, 1956.
  * [15] Eugene Narmour.  The analysis and cognition of basic melodic structures: the implication-realization model.  University of Chicago Press, Chicago, 1990.
  * [16] Eugene Narmour.  The top-down and bottom-up systems of musical implication: Building on Meyer’s theory of emotional syntax.  Music Perception, 9(1):1–26, 1991.  Place: US Publisher: University of California Press.
  * [17] Mark G. Orr and Stellan Ohlsson.  Relationship Between Complexity and Liking as a Function of Expertise.  Music Perception, 22(4):583–611, 2005.  Place: US Publisher: University of California Press.
  * [18] P.-Y. Oudeyer, J. Gottlieb, and M. Lopes.  Intrinsic motivation, curiosity, and learning: Theory and applications in educational technologies.  Progress in Brain Research, 229:257–284, 2016.
  * [19] Thomas Parr, Giovanni Pezzulo, and K. J. Friston.  Active inference: the free energy principle in mind, brain, and behavior.  The MIT Press, Cambridge, Massachusetts, 2022.
  * [20] M. T. Pearce.  The construction and evaluation of statistical models of melodic structure in music perception and composition.  doctoral, City University London, December 2005.
  * [21] Marcus T. Pearce.  Statistical learning and probabilistic prediction in music cognition: mechanisms of stylistic enculturation.  Annals of the New York Academy of Sciences, 1423(1):378–395, May 2018.
  * [22] Mark Reybrouck, Peter Vuust, and Elvira Brattico.  Neural Correlates of Music Listening: Does the Music Matter?  Brain Sciences, 11(12):1553, November 2021.
  * [23] Markus Schedl, David Hauger, and Dominik Schnitzer.  A Model for Serendipitous Music Retrieval.  ACM International Conference Proceeding Series, May 2012.
  * [24] Robert Dargavel Smith.  audio-diffusion, September 2023.  original-date: 2022-08-07T09:11:37Z.
  * [25] Neil Todd.  Towards a cognitive theory of expression: The performance and perception of rubato.  Contemporary Music Review, 4(1):405–416, January 1989.  Publisher: Routledge _eprint: https://doi.org/10.1080/07494468900640451.
  * [26] Peter Vuust, Ole A. Heggli, Karl J. Friston, and Morten L. Kringelbach.  Music in the brain.  Nature Reviews Neuroscience, 23(5):287–305, May 2022.
  * [27] Peter Vuust and Maria A. G. Witek.  Rhythmic complexity and predictive coding: a novel approach to modeling rhythm and meter perception in music.  Frontiers in Psychology, 5, 2014.
  * [28] Wenjie Wang, Yiyan Xu, Fuli Feng, Xinyu Lin, Xiangnan He, and Tat-Seng Chua.  Diffusion Recommender Model, April 2023.  arXiv:2304.04971 [cs].
  * [29] Maria A. G. Witek, Eric F. Clarke, Mikkel Wallentin, Morten L. Kringelbach, and Peter Vuust.  Syncopation, Body-Movement and Pleasure in Groove Music.  PLOS ONE, 9(4):e94446, 2014.  Publisher: Public Library of Science.
  * [30] Wilhelm Wundt.  Principles of physiological psychology.  (e. b. titchener, trans.). leipzig, germany: Engelmann. edition, 1874.
  * [31] Reza Jafari Ziarani and Reza Ravanmehr.  Serendipity in Recommender Systems: A Systematic Literature Review.  Journal of Computer Science and Technology, 36(2):375–396, April 2021.