# Reliable Geofence Activation with Sparse and Sporadic Location Measurements:
Extended Version

Kien Nguyen  Department of Computer Science
University of Southern California
Los Angeles, CA, USA
<EMAIL_ADDRESS>John Krumm  Microsoft Research
Microsoft Corporation
Redmond, WA, USA
<EMAIL_ADDRESS>
###### Abstract

Geofences are a fundamental tool of location-based services. A geofence is
usually activated by detecting a location measurement inside the geofence
region. However, location measurements such as GPS often appear sporadically
on smartphones, partly due to weak signal, or privacy preservation, because
users may restrict location sensing, or energy conservation, because sensing
locations can consume a significant amount of energy. These unpredictable, and
sometimes long, gaps between measurements mean that entry into a geofence can
go completely undetected. In this paper we argue that short term location
prediction can help alleviate this problem by computing the probability of
entering a geofence in the future. Complicating this prediction approach is
the fact that another location measurement could appear at any time, making
the prediction redundant and wasteful. Therefore, we develop a framework that
accounts for uncertain location predictions and the possibility of new
measurements to trigger geofence activations. Our framework optimizes over the
benefits and costs of correct and incorrect geofence activations, leading to
an algorithm that reacts intelligently to the uncertainties of future
movements and measurements.111A short version of this paper appears in the
proceedings of the 23rd IEEE International Conference on Mobile Data
Management MDM 2022.

###### Index Terms:

location-based services, geofence, sporadic locations, location prediction,
decision theory, payoff matrix

##  I Introduction

Geofences are virtual geographic regions used to trigger certain actions upon
entry or exit. A typical example is a region near a store where an advertiser
may want to deliver ads to the phones of people in the region. When someone
with a location-sensitive device enters a geofence, some action is
automatically triggered.

Figure 1: A trajectory passing through three goefences can be missed when
relying on only discrete location samples.

One problem with geofences is they may fail to activate if there is no
location measurement taken inside the geofence, even if the person passes
through. For example, in Figure 1, a full trajectory of a person is shown in
blue dots where each blue dot is five seconds apart from the ones before and
after. The trajectory passes through three geofences with a 1.5-mile radius
from three different Starbucks stores. However, when the trajectory is
subsampled to have, in expectation, one measurement every minute to simulate
the case where measurements come sporadically, none of the remaining
measurements shown with purple pins was found within the three geofences (The
data and subsampling process are described in Section IV). Thus, relying
solely on the existence of measurements inside a geofence would fail to
activate in this case, although the person passed through all three.

This problem can occur whenever the gaps between measurements are large enough
to miss a geofence, including when a person is walking or in a vehicle. With a
high enough sampling rate, this is not a problem. However, geofence
applications may not able to proactively trigger new measurements. One reason
is when the location signal is too weak, e.g., inside a tunnel or surrounded
by high buildings. Another reason is that user may only allow such
applications to monitor location readings after a time delay due to, e.g.,
privacy concerns. Yet another reason is that sensing location, especially with
GPS, drains a phone’s battery. For instance, Liu  _et al._ [1] estimate that
running a GPS receiver continuously will drain a phone’s battery in about six
hours. Therefore, some power management programs of the device may restrict,
e.g., the frequency of location sensing. This leads to conservative sensing,
where measurements are often relatively far apart in time. As an example,
Figure 2 shows a histogram of time spans between measurements for a random
sample of 1000 users (described in detail later in Section IV). It shows that
over half the points are separated by five minutes or more, making it easy to
miss a geofence depending on the geofence’s size and the user’s speed. Our
results in Section V show that the current practice of waiting for a
measurement to trigger a geofence performs poorly.

Figure 2: The time between location measurements can be long enough to miss a
geofence.

Short term location prediction can help alleviate this problem by giving the
probability that the person will enter the geofence in the near future.
However, there are two issues: (1) probability by itself may not be sufficient
to make the optimal, benefit-maximizing decision of activating the geofence or
not, and (2) a new measurement could arrive at any time, wasting prediction
computations that go beyond that time.

In this paper we develop a novel framework that uses short term location
prediction to solve the problem of triggering geofences with sparse and
sporadic location measurements. Our framework takes into account both the
predictive uncertainty for decision making and the potentially wasted
computation issues. The fundamental approach is to use decision theory as a
principled way to manage the trade-off between costs and benefits of acting or
waiting. Decision theory is enabled by computing the probability that a user
will intersect the geofence before the next measurement is available using a
probabilistic location prediction method. This is a new approach for deciding
whether or not to trigger a geofence, reflecting richer, more subtle reasoning
than the traditional method of passively waiting for a point to appear inside
the geofence. In addition, when we use location prediction, decision theory
helps bridge the gap between the accuracy of location prediction and the
benefit/penalty of geofence triggers in a principled way. We further reason
explicitly about the temporally sporadic nature of location measurements by
modeling their arrival times as Poisson distributed. This reasoning gives us a
principled way to stop the prediction process, thus avoiding redundant
predictions. We show how our approach is superior to the baseline technique of
using only the given measurements without considering the possibility of
missing a geofence. To the best of our knowledge, in the context of geofences,
neither probabilistic location prediction, nor decision theory, nor reasoning
about sporadic measurements has appeared in the research literature before.

For both privacy and energy conservation, our approach is designed to be
simple enough to run on the user’s local device rather than transmitting any
location data. Likewise, it does not trigger any new measurements, relying
instead on opportunistic measurements that are made available by other
processes on the device.

Specifically, our new research contributions are:

  * •

Probabilistically predicting geofence intersections

  * •

Modeling costs/benefits of geofence activations with decision theory

  * •

Reasoning about temporally sporadic location measurements with a Poisson
distribution

  * •

Extensive experiments over different settings for location measurements and
algorithmic parameters

##  II Related Work

While it seems obvious to use location prediction with geofences, there is
surprisingly little research on the topic. We are solving the problem of
missing a user’s entrance into a geofence due to low sampling rates. In [2],
Zimbelman  _et al._ characterize a similar problem of trying to detect when a
moving geofence (_e.g._ around a person) intersects a static location. Their
experiments looked at the effects of geofence speed, geofence size, location
sampling interval, and intersection angle on the delay of detecting geofence
intersections. Fattepur  _et al._ [3] present a state transition algorithm for
a GNSS chipset that does simple reasoning about geofences, but does not use
location prediction. The work most closely related to ours is from Nakagawa
_et al._ [4]. Their solution to the problem of missing geofences is to
adaptively increase the location sampling rate when the user is getting closer
to a geofence. The estimated distance to the geofence is based on a simple,
deterministic prediction from the last two measured locations. In contrast,
our method uses a probabilistic prediction, decision theory, and does not
trigger new measurements.

While there has not been much research on geofence intersection detection,
there is a large literature on location prediction, which is one of the
central components of our approach. A survey of location prediction approaches
appears in [5]. We are particularly interested in short-term location
prediction that gives future location estimates in the relatively short span
between measurements. For instance, the median time between measurements for
the 1000 random users represented in Figure 2 was about 8.5 minutes. Our
framework requires a probabilistic location prediction in order to accommodate
decision theory about whether or not to activate a geofence. In the realm of
short term, probabilistic location prediction, a classic example is the Kalman
filter [6], which creates a Gaussian-distributed prediction as part of its
measurement update algorithm. The particle filter [7] also has a prediction
step, as does the unscented Kalman filter [8].

Location prediction is one component of our approach, but our main
contribution is a framework for optimally reasoning about when to trigger a
geofence in light of the inherent uncertainty about the location prediction
and uncertainty about when the next measurement will be available. We handle
the uncertainty using decision theory, which lets us reason not about
accuracy, but about the ultimate costs and benefits of decisions which are
likely more relevant and explainable to a geofence owner.

##  III Decision Theory with Location Predictions

This section introduces our geofence decision theory inspired by the
uncertainty of users’ future locations, our use and modification of Gaussian
process for probabilistic location prediction, and our reasoning for the
temporally sporadic nature of location measurements.

###  III-A Decision Theory

A geofence triggers some action when a user enters222An action may be
triggered when a user _leaves_. For that, we imagine a complementary ”entry”
geofence covering everywhere except the region of the ”exit” geofence..
However, a user’s location typically has some uncertainty due to measurement
noise or prediction error. This leads to uncertainty about whether or not the
user is inside the geofence. We represent a user’s two-dimensional location
coordinates at time $t$ as the vector $\bm{x}(t)=[x(t),y(t)]^{T}$, distributed
according to the probability distribution
$P_{\bm{X}(t)}\big{(}\bm{x}(t)\big{)}$. If the geofence region is represented
by $\mathcal{R}$, the scalar probability that the user is inside the geofence
is

$p_{\mathcal{R}}(t)=\int_{\mathcal{R}}P_{\bm{X}(t)}\big{(}\bm{x}(t)\big{)}d\bm{x}$
(1)

as illustrated in Figure 3.

Figure 3: With an uncertain location $\bm{x}(t)\sim
P_{\bm{X}(t)}\big{(}\bm{x}(t)\big{)}$, there is a probability that the user is
inside $\mathcal{R}$.

Based on $p_{\mathcal{R}}(t)$, the geofence can be programmed to either act or
wait: acting means the geofence triggers some action, e.g. the delivery of an
advertisement to the user, while waiting means nothing is triggered. A payoff
matrix captures the value $V(t)$ of acting or waiting depending on whether or
not the user is inside the geofence, shown in Table I. The value of acting
when the user is inside $\mathcal{R}$ is $\beta$, which would normally be
positive, reflecting the intended functioning of the geofence. The value of
the two error conditions are acting when the user is outside ($\delta$) and
waiting when the user is inside ($\alpha$). Both of these values would likely
be negative. Waiting while the user is outside is the correct decision, but
the payoff in this case would normally be zero. The exact values of the
elements of the payoff matrix depend on the scenario. For advertising, the
values would depend on the cost of delivering an ad and the response rate.
These values are normally proprietary and beyond the scope of this paper,
although this would be an interesting extension of our work. We explore
different payoff matrix settings in our experiments. Using a payoff matrix
instead of raw prediction accuracy has two advantages. First, it allows us to
express and evaluate the true costs of mistakes and successes. Second, by
using costs, it lets the algorithm optimize for cost rather than raw accuracy,
which can lead to different decisions.

|  | user state |
---|---|---|---
|  | in | out |
decision | wait | $\alpha$ | 0 |
act | $\beta$ | $\delta$ |
TABLE I: The payoff matrix gives values of decisions depending on the state of
the user.

The expected payoff values, given an activation decision, can be computed from
$p_{\mathcal{R}}(t)$ and the payoff matrix:

$\displaystyle\mathbb{E}\big{[}V(t)\mid\textrm{wait}\big{]}$
$\displaystyle=\alpha p_{\mathcal{R}}(t)+0(1-p_{\mathcal{R}}(t))$ (2)
$\displaystyle\mathbb{E}\big{[}V(t)\mid\textrm{act}\big{]}$
$\displaystyle=\beta p_{\mathcal{R}}(t)+\delta(1-p_{\mathcal{R}}(t))$ (3)
$\displaystyle\mathbb{E}\big{[}V(t)\big{]}$
$\displaystyle=\textrm{max}\Big{(}\mathbb{E}\big{[}V(t)\mid\textrm{wait}\big{]},\mathbb{E}\big{[}V(t)\mid\textrm{act}\big{]}\Big{)}$
(4)

The decision to wait or act corresponds to which has the larger expected
value. This changes with time depending on $p_{\mathcal{R}}(t)$. In our
scenario, after the first ”act” decision, the geofence is deactivated,
disallowing any acts for that user for some time.

This rule for waiting or acting, based on Equation 4, is a principled way to
account for the costs and benefits of acting under uncertainty for geofences,
and is our main contribution to the problem of geofence activation. The values
from the payoff matrix allow the geofence owner (_e.g._ advertiser) to
quantify the urgency of delivering a message to someone who should receive it
($\beta$), versus the cost of not delivering it to someone who should receive
it ($\alpha$), versus the cost of mistakenly delivering it to someone who
should not receive it ($\delta$). The probability $p_{\mathcal{R}}(t)$
accounts for measurement uncertainty, and would be especially applicable for
less precise location sensing modalities, e.g. cell towers or WiFi. However,
we are interested in further dealing with the problem of low sample rate data,
when entering a geofence can be completely missed. For this we can use
location prediction, described next.

###  III-B Location Prediction

We can predict whether or not a user will be inside a geofence by predicting
the user’s location $\bm{x}(t)$. Referring to Figure 4, we reset the clock to
$t=0$ at the most recent location measurement $\bm{x}_{0}$, thus
$\bm{x}(0)=\bm{x}_{0}$. Then we use an algorithm to create probabilistic
predictions $p_{\mathcal{R}}(t)$ for $t>0$. At each $t>0$, we evaluate
Equation 4, and we ”act” the first time
$\mathbb{E}\big{[}V(t)\mid\textrm{act}\big{]}>\mathbb{E}\big{[}V(t)\mid\textrm{wait}\big{]}$.
Once we have acted on the user (_e.g._ sent a message) for this geofence, we
will not act again for that user on that geofence, or we may not act again
until some preset time elapses, such as a few hours.

Figure 4: $t=0$ is the time of the most recent measurement. Our algorithm
makes probabilistic predictions of location to infer the future probability of
being inside the geofence.

Our framework accepts any type of probabilistic location prediction. That is,
the prediction must produce a distribution $\bm{x}(t)\sim
P_{\bm{X}(t)}\big{(}\bm{x}(t)\big{)}$ for $t>0$. However, as we aim for mobile
applications, we also prefer a light-weight model that can run on-device, even
without sending measurements out of the device. Therefore, for our
experiments, we predicted location with Gaussian processes (GPs) [9]. For a
scalar function $x(t)$, a GP implies that any subset of points sampled from
the function is distributed according to a multidimensional Gaussian. We
create independent GPs for $x(t)$ and $y(t)$ to predict two-dimensional
location $\bm{x}(t)=[x(t),y(t)]^{T}$.

Several choices are required for implementing a GP. One of them is the
standard deviation of the assumed Gaussian noise of the measurements. Gaussian
noise is an acceptable approximation of GPS noise [10], and we nominally
assume a standard deviation of $\sigma_{m}=3$ meters. A GP also depends on a
scalar covariance function $k(t,t^{\prime})$ defining how much a measurement
$x(t)$ correlates with a measurement $x(t^{\prime})$. In general, the
correlation decreases to zero as $|t-t^{\prime}|$ gets larger. A common kernel
is the squared exponential

$k(t,t^{\prime})=\sigma^{2}_{f}\exp\Bigg{[}-\frac{(t-t^{\prime})^{2}}{2l^{2}}\Bigg{]}$
(5)

for some choice of parameters $\sigma_{f}$ and $l$ trained on previous data
whenever a new measurement arrives. So, another choice is the number of points
prior to $\bm{x}_{0}$ used for this training.

Finally, a GP also depends on a mean function $m(t)$ which defines the
expected mean values of the data points. Some GPs are assumed to have a zero
mean, and some are not. We explore the effects of all these choices in our
experiments in Section V.

Although a GP can capture the trends of the user’s movement to predict future
locations, the movement in the short-term may not follow such trends. For
example, a right turn made a minute ago might not indicate another right turn.
Therefore, we propose an adaptation of the GP for short-term location
prediction. With the intuition that the short-term movement would be affected
more by recent movements than by older movements, we aim to make the
prediction rely more on the linear extrapolation of the most recent
measurements. This can be captured by utilizing the mean function. In our
adaption, the mean function $m(t)$ of a GP is set to be the line going through
the two latest points $x(t_{-1})$ and $x(t_{0})$. We denote this as GP + mean
func.

Nominally the geofence processor runs the prediction of $\bm{x}(t)$ forward in
time until the value of acting exceeds the value of waiting. Specifically, it
looks for the smallest time $\hat{t}>0$ when
$\mathbb{E}\big{[}V(\hat{t})\mid\textrm{act}\big{]}>\mathbb{E}\big{[}V(\hat{t})\mid\textrm{wait}\big{]}$.

We emphasize that although the application of GPs to geofences is novel,
location prediction is not the focus of this paper, and other types of
probabilistic prediction could be used as well. GPs are particularly well-
suited for our application because they give time-dependent, probabilistic
predictions which are suitable for our decision theory approach. In the end,
however, we evaluate our methods by how much value they return based on the
payoff matrices, not raw prediction accuracy. This would make it easier for
the adminsitrator of the geofences (_e.g._ advertiser) to understand the
ultimate advantages of using our proposed technique.

###  III-C Sporadic Location Measurements

In Section III-B, we showed how to compute $\hat{t}$, which is the first time
when the expected value of acting is predicted to exceed the expected value of
waiting. We assume the underlying architecture includes a real time process
scheduler. When a new measurement arrives, our algorithm computes $\hat{t}$
and instructs the process scheduler to schedule an ”act” for the user/geofence
combination at $\hat{t}$.

However, $\hat{t}$ may be very large, especially if the geofence is a long
distance from the user, leading to long, possibly infinite, computations of
the location predictions for those geofences. In these cases, a new
measurement could occur before the computed $\hat{t}$, causing much of the
previous computation to become wasted. This section describes a principled way
to suspend the prediction.

Assuming the timing of location measurements follows a Poisson process, we can
compute the probability of receiving a new measurement as a function of time.
A Poisson process is characterized by $\lambda$, which is the average number
of events occurring in some predefined interval $\Delta T$. For us, these
events are location measurements, and the predefined interval is set
arbitrarily to one minute. The parameter $\lambda$ is called the event rate or
the rate parameter. The probability of receiving $n$ measurements in the next
$t$ minutes is

$P\big{(}N(t)=n\big{)}=\frac{(\lambda t)^{n}e^{-\lambda t}}{n!}$ (6)

The probability of having no measurement by time $t$ is
$P\big{(}N(t)=0\big{)}=e^{-\lambda t}$, and of receiving at least one
measurement by time $t$ is $P\big{(}N(t)>0\big{)}=1-e^{-\lambda t}$. Our
algorithm stops making predictions when the probability of having at least one
measurement is sufficiently high, _i.e._ when
$P\big{(}N(t)>0\big{)}>1-\epsilon$, for some small value of $\epsilon$,
$0<\epsilon<1$. This occurs at time $t^{*}=-\ln(\epsilon)/\lambda$.

Whenever a new measurement arrives, our algorithm sets $t=0$. It then computes
$t^{*}$ as described above, which is the cutoff time for making location
predictions. Starting at $t=0$, it samples forward in time until it finds a
time when the expected value of acting exceeds the expected value of waiting
(_i.e._ $\hat{t}$) or until $t$ exceeds $t^{*}$. If this second condition
happens, the algorithm will not schedule the geofence to act, essentially
making $\hat{t}=\infty$ and temporarily deactivating the geofence for that
user. This process is repeated every time a new measurement arrives, which
means the geofence could be reactivated depending on new location data. We
believe this approach can also be a principled way to stop the location
prediction process in other mobile-related problems such as estimated time of
arrival.

##  IV Experimental Data

We tested our algorithm on 530 location trajectories from 165 subjects.
Testing on up to 13,824 geofences simultaneously, this means our test data
covered over 7 million trajectory-geofence scenarios.

###  IV-A Data Source

The location data came from a commercial aggregator
333https://www.safegraph.com/ that ingests, cleans, and sells location data
gathered from mobile phones. The data comes from individuals using their phone
normally, occasionally running applications that trigger location
measurements, e.g. weather, web browsing, or navigation applications. This
data simulates a geofencing application that is not actively taking location
measurements, instead relying passively on measurements triggered by other
applications.

For each of 1000 randomly selected users with at least one data point, we
extracted all their data for the date of 1 June 2019 to understand
representative statistics on the quantity and frequency of location data that
is normally available from a user. As we show below, the data from these 1000
users varied in terms of the number of data points.

For our experiments, we used the same data source from the same day, but this
time we extracted data from the 1000 users with the _most_ data points for
that day. We refer to these two data sets as the ”random” and ”high density”
sets. The random data set is used to understand representative statistics of
available data, while the high density data is used to simulate various data
densities to understand how our algorithm performs. Thus, even though the test
trajectories originated from high density trips, our controlled subsampling
simulated lower sampling rates for our experiments.

###  IV-B Data Statistics

Histograms of the number of points in the random and high density sets of
trajectories are shown in Figure 5. A trajectory $\mathcal{S}$ of a user is a
sequence of location measurements
$\\{\bm{x}(t_{1}),\bm{x}(t_{2}),\dots,\bm{x}(t_{N_{\mathcal{S}}})\\}$ where
$N_{\mathcal{S}}$ is the number of measurements and $\forall
i<N_{\mathcal{S}}:t_{i}<t_{i+1}$. High density means that, on average, the
time gap $|t_{i}-t_{i+1}|$ is small. The larger number of points in the high
density trajectories enable us to delete some of the points for experiments.

Figure 5: Histograms of the number of points in the random and high density
trajectories.

In Section III-C we show how to compute a cutoff time for predictions assuming
that timing of new location measurements is governed by a Poisson process. The
sole parameter of the Poisson distribution (Equation 6) is $\lambda$, which is
the mean number of events over some unit time. For our experiments, our unit
time is one minute. For each of the 1000 random trajectories, we computed the
maximum likelihood value of $\lambda$. The mode of this distribution of
$\lambda$’s occurs at 0.04, which corresponds to one measurement every 25
minutes.

We subjected each random trajectory to a statistical test to determine if the
timing of the measurements was Poisson distributed. Using the chi-square test
[11] for Poisson distributions, we found that 88.3% of the random users passed
at the $p=0.05$ level. This indicates that the Poisson distribution is
appropriate for modeling the arrival time of location measurements in our
data. For the high density data, none of the users passed the statistical
test, but these trajectories are outliers, chosen for experimental advantages.
Specifically, we downsampled the high density data to simulate different
values of $\lambda$ in the Poisson process, described next.

###  IV-C Data Pre-Processing

We processed the high density data to simulate the Poisson processes of the
randomly chosen users. Our goal was to find, in the high density data, long
sequences of measurements with temporally uniform sampling, since uniform
sampling is convenient for down-sampling to measurement times that are Poisson
distributed.

For each user, we found the most frequently occurring time gap $\tau$ between
temporally adjacent measurements. For the high density data, $\tau$ varied
between five to ten seconds. We then split the time series wherever the time
gap was not $\tau$, resulting in separate trajectories whose time gaps were
uniformly $\tau$.

We then removed trajectories that were short in either time or space. For the
time aspect, we aim to have at least five minutes of data for training the GP
and five minutes of data for testing. Thus, all trajectories that were shorter
than ten minutes were removed. For the space aspect, we removed trajectories
where the user was not moving much. We assumed a minimum driving speed of 5m/s
(or 18km/h), and removed all trajectories where the distance between the first
and last measurements is less than the distance one can travel with minimum
driving speed over that time, resulting in total 530 trajectories from 165
unique users.

For these trajectories, we used the first five minutes for training the
parameters of the GP. We used the remaining data for testing. Note that the GP
does not depend on a large corpus of training data. It computes its own
parameters for each trajectory prediction based on the last few points of the
measured trajectory.

Then, in the test data period (_i.e._ after five minutes) for each of these
trajectories, we computed the first time it entered the geofence, $t_{in}$,
and the first time it exited the geofence, $t_{out}$. Normally this required
interpolation, where we assumed constant, straight line speed between
temporally adjacent points.

A subtended degree in latitude and longitude represent different arc lengths
on the earth. Therefore, we converted the latitude/longitude coordinates in
each trajectory to local Euclidean coordinates $(x,y)$ in meters. For each
trajectory, the reference origin $(lat_{0},long_{0})$ was arbitrarily chosen
as the last training point.

To simulate a Poisson process from our uniformly sampled trajectories, we
sample points from the uniform trajectories with a Bernoulli process [12],
which is the discrete-time version of a Poisson process. That is, for every
point in the uniform data, we retain it as a measurement with probability $p$
and delete it with probability $1-p$. For the Poisson process, the expected
number of events in time $\Delta T$ is $\lambda$. The time between points in
the uniform trajectory is $\tau$, meaning there will be $\frac{\Delta
T}{\tau}$ points in time $\Delta T$. If we sample with probability $p$, then
the expected number of sampled points is $\mathbb{E}[N]=p\frac{\Delta
T}{\tau}$ in $\Delta T$. Setting $\mathbb{E}[N]=\lambda$ gives the Bernoulli
probability of $p=\lambda\frac{\tau}{\Delta T}$.

For each trajectory, the training and testing data are sub-sampled separately.
We also keep the first and last data points of each part to aid evaluation:
the first training data point is kept to make sure that with each
configuration for training data for the GPs, we have enough data to provide
(_e.g._ , data in the last 5 minutes); the last training data point is kept to
be used as the reference origin $(lat_{0},long_{0})$; and the first and last
test data points are kept as the pivot for evaluation, as later shown in
Section V-A.

##  V Experiments

In this section, we describe our evaluation metric, the baselines, our
experimental setup, and our results with some discussion.

###  V-A Evaluation metric

We first describe our evaluation metric to evaluate the effectiveness of our
technique for the geofence decision problem. The reason we need a new metric
instead of using the whole dense trajectory is because we need a fair way to
evaluate proposed methods. Simply comparing a case when the whole dense
trajectory is available with when only sporadic data is available (which is
our problem setting) is not fair, because our approach is designed to work
when data is unavoidably sporadic. Therefore, we propose a ”realized value”
evaluation score that is analogous to the expected value in Equation 4. The
realized value is the actual payoff, as per the payoff matrix, of using our
algorithm to make the act or wait decisions for geofences. Starting first with
a single point below, we show how we aggregate the realized value over
multiple points in a trajectory $\mathcal{S}$, multiple geofences on the map
$\mathcal{R}$, and multiple trajectories in a test set.

We first calculate the realized value, called
$V_{\mathcal{R},\mathcal{S}}(t_{i})$, for each measurement
$\bm{x}(t_{i})\in\mathcal{S}\setminus\bm{x}(t_{N_{\mathcal{S}}})$. The last
measurement $\bm{x}(t_{N_{\mathcal{S}}})$ is used as a pivot and is not
evaluated.

Given $t_{in}$ and $t_{out}$ as the first timestamps that the user enters and
exits a geofence $\mathcal{R}$, $t_{i}$ and $t_{i+1}$ as the timestamps of
$i$-th and $(i+1)$-th measurements, and $\hat{t}$ as the predicted timestamp
that the geofence should ”act” when we receive $\bm{x}(t_{i})$, the realized
value of the $i$-th measurement $V_{\mathcal{R},\mathcal{S}}(t_{i})$ is
defined as:

$V_{\mathcal{R},\mathcal{S}}(t_{i})=\begin{cases}\alpha,&t_{i+1}<\hat{t}\wedge
t_{i}\leq t_{out}\leq t_{i+1},\\\ \beta,&\hat{t}\leq
t_{i+1}\wedge\hat{t}\in[t_{in},t_{out}],\\\ \delta,&\hat{t}\leq
t_{i+1}\wedge\hat{t}\notin[t_{in},t_{out}].\end{cases}$ (7)

where $\alpha$, $\beta$, and $\delta$ come from the payoff matrix in Table I.

Elaborating on the compact notation in Equation 7, the condition $\hat{t}\leq
t_{i+1}$ indicates that we ”act” before the next measurement arrives. Then,
based on the actual user state at the time of acting, we receive reward
$\beta$ or penalty $\delta$ if we act when the user is inside (_i.e._ ,
$\hat{t}\in[t_{in},t_{out}]$) or outside (_i.e._ ,
$\hat{t}\notin[t_{in},t_{out}]$), respectively. This explains the $\beta$ and
$\delta$ payoffs in Equation 7.

In the case of $t_{i+1}<\hat{t}$, which means we ”wait” before the next
measurement arrives, we further investigate different cases of
$[t_{in},t_{out}]$ and $[t_{i},t_{i+1}]$ to decide the reward/penalty. These
cases are illustrated in Figure 6. In case (1) where $t_{out}<t_{i}$, we
”wait” while the user is outside, thus, the payoff is $0$. In cases (2) and
(3) where $t_{i}\leq t_{out}\leq t_{i+1}$, we ”wait” while the user is inside,
thus the payoff is $\alpha$. In cases (4), (5), and (6) where have
$t_{i+1}<t_{out}$, although the user might be inside, we still have a chance
to act when the next measurement arrives. Therefore, the evaluation is
deferred to the next measurements and the payoff of the current measurement is
$0$. In short, we only receive payoff $\alpha$ when $t_{i}\leq t_{out}\leq
t_{i+1}$. This explains the $\alpha$ payoff in Equation 7.

Figure 6: Illustrations of cases when we ”wait” (_i.e._ , $t_{i+1}<\hat{t}$).

Recall that $\hat{t}$ in Equation 7 comes from the location prediction in
Section III-B and expected value computations from Equation 4 in Section
III-A. The computed value of $\hat{t}$ varies depending on various algorithmic
choices, such as the kernel function of the GP. Different values of $\hat{t}$
affect $V_{\mathcal{R},\mathcal{S}}(t_{i})$, so we can assess the effect of
our algorithmic choices.

For a given trajectory, we should only act on a geofence a maximum of one
time. Thus, for evaluation purposes, we stop calculating the realized value
for this trajectory after the measurement $\bm{x}(t_{k})$ for which we receive
$\beta$ (_i.e._ act when inside the geofence), and set
$V_{\mathcal{R},\mathcal{S}}(t_{i})$ of all following measurements to $0$,
_i.e._ $\forall
i\in[k+1,N_{\mathcal{S}}-1]:V_{\mathcal{R},\mathcal{S}}(t_{i})=0$. This means
we can receive the payoff $\beta$ only once.

The realized value of a whole trajectory $\mathcal{S}$ is then the sum of
realized values of all the measurements of $\mathcal{S}$:

$V_{\mathcal{R},\mathcal{S}}=\sum_{i=1}^{N_{\mathcal{S}}-1}V_{\mathcal{R},\mathcal{S}}(t_{i})$
(8)

To avoid any bias towards any geofence positioning, we consider sum of
$V_{\mathcal{R},\mathcal{S}}$ of a trajectory $\mathcal{S}$ over a set of
multiple geofences as the score of $\mathcal{S}$:

$V_{\mathcal{S}}=\sum_{\mathcal{R}}V_{\mathcal{R},\mathcal{S}}$ (9)

Our set of experimental geofences is a grid described below.

The final realized value is the average of $V_{\mathcal{S}}$ over all
trajectories:

$V=\frac{1}{N_{T}}\sum_{\mathcal{S}}V_{\mathcal{S}}$ (10)

where $N_{T}$ is the number of trajectories. The realized value $V$ is a
simple way to compare the aggregated payoff of different algorithms, tested
over multiple trajectories and geofences.

###  V-B Baselines

Our baseline algorithm is called Passive Wait (PW), where the geofence
passively waits to act until there is an actual location measurement inside.
This appears to be the basis of the algorithm used by both iOS [13] and
Android [14]. Formally, when receiving the most recent measurement
$\bm{x}(t_{0})=\big{(}x(t_{0}),y(t_{0})\big{)}$ at time $t=t_{0}=0$ with the
measurement noise defined by the standard deviation $\sigma_{m}$, then for
each $t<t^{*}$, the PW method makes a prediction:

$\bm{x}(t)\sim\mathcal{N}\big{(}\bm{\mu}(t),\bm{\Sigma}(t)\big{)}=\mathcal{N}\Bigg{(}\Bigg{[}\begin{matrix}x(t_{0})\\\
y(t_{0})\\\ \end{matrix}\Bigg{]},\sigma^{2}_{m}I\Bigg{)}$ (11)

where $I$ is the $2\times 2$ identity matrix. While we call this a prediction,
it is simply asserting that the user stays at the measurement point
$\bm{x}(t)=\big{[}x(t_{0}),y(t_{0})\big{]}^{T}$ until the next measurement and
that the uncertainty in location is solely due to measurement noise. Although
this is a simple baseline algorithm, it appears to be the most sophisticated
existing algorithm for geofences, both in practice and in research. We also
explore and compare different instantiations of the GP.

###  V-C Experiment Setup

We present several experiments on 530 trajectories from 165 unique users,
processed from high-density data described in Section IV. It is difficult to
accurately predict the parameters of an actual geofence application, so we
experiment with a thorough range of experimental parameters to show our
algorithm performs well in a variety of operating conditions.

For each trajectory, we created a grid of geofences centered at the last
training point. The grid covered the entire bounding box of the testing data
of the trajectory. In order to account for predictions beyond the bounds of
the trajectory, we expanded the grid on all four sides by 18 kilometers. This
expansion assumed a maximum driving speed of 30m/s (or 108km/h) and a duration
of 600 seconds. The choice of 600(s) is explained in our discussion of
$\epsilon$ in Section V-D2.

Each grid cell is considered as a geofence with size $L\times L$. We tested
with sizes $L\in\\{500,\textbf{1000},1500,2000,2500\\}$ meters for square
cells, creating from 230 to 13,824 geofences per grid for evaluation depending
on $L$ and the specific trajectory. The bold value indicates the default value
used in the experiments where this parameter is fixed. The grids have sizes
ranging from 1444 $km^{2}$ to 3456 $km^{2}$. We chose these grid sizes to
represent a range of possible scenarios. Our algorithm tends to work better
for smaller cells, hence for fairness we did not experiment with sizes below
500 meters on a side. With up to 13,824 geofences, combined with the 530
trajectories, this gives a test size of over 7 million trajectory-geofence
pairs.

Each trajectory is sub-sampled with
$\lambda\in\\{0.25,\textbf{0.5},1,2,4,8\\}$ with a Poisson time interval
$\Delta T$ of one minute. Roughly speaking, these values of $\lambda$ mean we
expect to receive one measurement from every $4$ minutes
($\lambda=\frac{1}{4}$) to every $7.5$ seconds ($\lambda=8$).

Then, for each test measurement, the prediction model is allowed to use all
measurements in the last $\omega$ seconds as the training data. $\omega$ is
called the maximum look-back range and takes values in
$\\{200,\textbf{300},400,500,600\\}$ seconds. The maximum prediction threshold
$\epsilon$, which is used to find the maximum prediction time $t^{*}$, is set
to $\epsilon\in\\{0.1,\textbf{0.2},0.3,\dots,0.9\\}$.

Two settings for the payoff matrix is considered to represent two real-world
use cases: the advertising matrix where
$\alpha,\beta,\delta=-\frac{1}{2},1,-\frac{1}{4}$, respectively; and the
alert-zone matrix where $\alpha,\beta,\delta=-2,1,-\frac{1}{4}$, respectively.
For the advertising case, the geofence messenger wants to deliver an
advertisement to users inside the geofence. The alert-zone case involves a
messenger who wants to deliver an important message, e.g., a safety warning.
The intuition behind those values of $\alpha,\beta,\delta$ is that the value
received when we act correctly ($\beta$) is often higher than the penalty when
we act incorrectly (_i.e._ , $|\beta|>|\delta|$); and when the user is inside
a geofence, there are much more hazardous consequences if we fail to act in
case of alert zone than advertising (_i.e._ , $|\alpha_{\textit{alert-
zone}}|>|\alpha_{\textit{advertising}}|$). While these values were set based
on our own reasoning to mimic advertising and alert-zone scenarios, we assume
the payoff matrix is given or can be learned. We instead focus on the problem
of making decisions for geofence activations.

We use the squared exponential kernel from Section III-B as the default kernel
due to its popularity. Other popular kernels, such as Rational Quadratic and
Matérn kernels[15], also achieve comparable performance but we omit those
results due to space limitations.

###  V-D Experimental Results

####  V-D1 Varying Poisson $\lambda$

As we focus on the sporadic setting, we first evaluate the methods for
different values of $\lambda$. Figure 7 shows the realized values $V$ when
$\lambda$ varies and other parameters are fixed as the bold values shown in
Section V-C, for both advertising and alert-zone payoff matrices. Roughly
speaking, each data point in a result graph shows the average dollar amount
per trajectory that one model achieved over all geofences. As a concrete
example, in Figure 7(a), the realized value of GP + mean func for $\lambda=4$
is about 8. This means that GP + mean func achieved $8 benefit per trajectory
summed over all geofences.

The general observation is that GP-based algorithms greatly outperform PW,
especially with smaller $\lambda$, _i.e._ , more sporadic. This confirms our
hypothesis that for sporadic measurements, using principled decision theory
with a proper location prediction method brings significant improvement.

(a) Advertising

(b) Alert-zone

Figure 7: The realized value with different values of $\lambda$

The improvement is even more prominent in the case of the alert-zone payoff
matrix in Figure 7(b), where the penalty is higher if the messenger waits
until the user is inside the dangerous area (_i.e._ , larger $|\alpha|$). The
reason is that we tend to act more readily when $\alpha$ is larger, while PW
does not. We can gain more insight into this improvement by investigating our
decision making process further. We decide to act when:

$\mathbb{E}\big{[}V(t)\mid\textrm{act}\big{]}>\mathbb{E}\big{[}V(t)\mid\textrm{wait}\big{]}$
(12)

which means:

$\beta p_{\mathcal{R}}(t)+\delta(1-p_{\mathcal{R}}(t))>\alpha
p_{\mathcal{R}}(t)+0(1-p_{\mathcal{R}}(t))$ (13)

After re-arranging with the fact that typically $\delta+\alpha-\beta<0$:

$p_{\mathcal{R}}(t)>\frac{\delta}{\delta+\alpha-\beta}$ (14)

When $|\alpha|$ increases with fixed $\delta$ and $\beta$, the value of the
right hand side of Equation 14 becomes smaller, which means that we might act
with a smaller probability $p_{\mathcal{R}}(t)$. In our specific experimental
settings, this probability is $\frac{1}{7}$ for advertising and $\frac{1}{13}$
for alert-zone. Therefore, an advertising act needs a larger probability of
being inside the geofence than an alert-zone act, because missing an alert-
zone act is is more costly.

When location measurements are frequent (_i.e._ , larger $\lambda$),
prediction does not offer much benefit. This is understandable because with
frequent measurements, there is a much higher chance a measurement arrives
when the user is inside the geofence. Therefore, the prediction might be
unnecessary.

The modified version of the GPs with a linear mean function, denoted as ”GP +
mean func” in the figures, offers a better realized value in the alert-zone
setting compared to the standard GP. This improvement is also shown in other
following experiments. Besides the intuition that the movement in the near
future tends to rely more on the recent locations, another potential
explanation is that the modified GP produces predictions with smaller
variance, because the line going through the most recent measurements might be
a better mean function than a zero mean. The smaller variances, along with the
aforementioned analysis of $p_{\mathcal{R}}(t)$, might give a higher number of
acts. Therefore, in the alert-zone setting where the risk is higher for
waiting than acting, the modified GP can achieve a higher payoff. Figure 8
shows the comparison between the standard GP and the modified GP. First,
Figure 8(a) shows the average value of the standard deviation per prediction.
This value of the modified GP is smaller than that of the standard GP, and
they become closer to each other when $\lambda$ increases. Second, in Figure
8(b) we can see a clear gap between the number of ”act” decisions of the
modified GP and that of the standard GP in the alert-zone setting. However,
again, these differences do not play an important role for the performance
when the measurements arrive frequently (_i.e._ , large $\lambda$).

(a) Average standard deviation per prediction

(b) Average number of acts per trajectory (alert-zone setting)

Figure 8: The comparison between the standard GP and the GP with linear mean
function

####  V-D2 Varying Prediction Threshold $\epsilon$

Next, we consider the effect of the maximum prediction threshold $\epsilon$.
Recall that $\epsilon$ is combined with $\lambda$ to decide the maximum
prediction time $t^{*}$ as the principled way of taking into account the fact
that the next location measurement may come at any time in the future, which
would suspend the current prediction. For a fixed $\lambda$, a smaller
$\epsilon$ leads to a larger $t^{*}$.

The corresponding $t^{*}$ for each value of $\epsilon$ is shown in Figure 9.
The general observation is that we need to make predictions further ahead in
time (_i.e._ , larger $t^{*}$) when data is more sporadic and/or $\epsilon$ is
smaller, and vice versa. In our most sporadic setting, where
$\lambda=\frac{1}{4}$, and most conservative threshold, $\epsilon=0.1$, we
need to make predictions up to $600s$ ahead. That explains why $600s$ is used
in our expansion of the geofence grid discussed in Section V-C.

Figure 9: Maximum prediction time $t^{*}$ given $\epsilon$.

Figure 10 shows the realized values for different values of $\epsilon$ when
$\lambda$ is fixed at $\frac{1}{2}$. The general trend is that smaller values
of $\epsilon$ give larger realized values. With larger $\epsilon$, the
realized value becomes smaller and closer to the value obtained by the PW,
which does not make predictions, thus, is not affected by the change of
$\epsilon$. In general, using a smaller $\epsilon$ is more conservative,
because it leads to longer prediction times, lessening the chance that we will
terminate the location prediction before the next measurement arrives.

(a) Advertising

(b) Alert-zone

Figure 10: The realized values when varying $\epsilon$ $t^{*}$ (s) | 194 | 277 | 600 | 3600 | 36,000
---|---|---|---|---|---
Time (s) | 0.38 | 0.53 | 1.08 | 6.12 | 60.52
TABLE II: Time to calculate $p_{\mathcal{R}}(t)$ for all $0<t<t^{*}$

Another important effect of $\epsilon$ is that the suspension of the
prediction greatly reduces computation time. In our experiments, running with
a single thread on a personal computer , the training and prediction time of
the GPs are about $1.7$s and $0.6$s, respectively. These times are independent
of $\epsilon$. However, for prediction, for all $0<t<t^{*}$, we need to
calculate the integrals on the predicted location distributions to calculate
$p_{\mathcal{R}}(t)$ as in Equation 1. Table II shows the time required to
calculate $p_{\mathcal{R}}(t)$ for all $0<t<t^{*}$, for different values of
$t^{*}$ with $\lambda=\frac{1}{2}$, and for a single geofence. While all these
values of $t^{*}$ result in similar realized values, with $\epsilon=0.1$ and
$0.2$, we can suspend the prediction at $t^{*}=194$s and $277$s, and the
calculation time is just $0.38$s and $0.53$s, respectively. Any computation
after these values of $t^{*}$ can be considered as wasted computation. Without
this principled approach to identify $t^{*}$, one could arbitrarily choose
some values for $t^{*}$, which would result in an almost linear increase in
the computation time. For $t^{*}=3600$s and $36,000$s, the computation times
are $6$s and $60$s, respectively, which are often not suitable for most real-
time mobile applications.

####  V-D3 Varying Geofence Size $L$

Next, we evaluate the performance with different sizes of the geofences. The
result is shown in Figure 11. We can see a clear advantage of GPs over PW in
smaller geofence sizes. The reason is that with smaller geofences, there is a
higher chance that we might not receive any measurement when the user is
inside. Thus, the PW approach would miss those geofences while the prediction
of the GPs can still help us take the right action. On the other hand, when
the size of the geofence is larger, then, again, there is a higher chance a
measurement arrives inside the geofence even though the measurements do not
come frequently. However, the prediction of GPs still gives a better realized
value than the PW.

(a) Advertising

(b) Alert-zone

Figure 11: The realized values when varying geofence size $L$

####  V-D4 Varying Look-Back Range $\omega$

The effect of the maximum look-back range $\omega$ is shown in Figure 12. This
parameter controls how far back in time we look for training data to train the
parameters of the GP. While both GP-based methods still outperform PW, when
$\omega$ becomes too large (_e.g._ , 600s), it negatively affects the
performance of the GP-based methods. One possible explanation is that the
movement pattern too far into the past may not relate well to the movement in
the near future. Also the change of $\omega$ shows a greater effect on the GP
with the linear mean function than the normal GP. This is because the linear
mean function further drives the prediction towards the linear extrapolation
of the most recent measurements, thus making a larger difference between the
pattern in the far past and the near future.

(a) Advertising

(b) Alert-zone

Figure 12: The realized values when varying $\omega$ (in seconds)

####  V-D5 Varying Measurement Noise $\sigma_{m}$

Next, we investigate the effect of the measurement noise given by the standard
deviation $\sigma_{m}$ in Figure 13. In our algorithm, we must set the value
of $\sigma_{m}$ as an estimate of the measurement noise. In Figure 13(a) and
13(b), $\sigma_{m}$ is varied from a reasonable GPS error of $3$m to a very
noisy $500$m. These values of $\sigma_{m}$ are provided to the prediction
methods. The GP-based methods successfully capture the pattern and bring
superior realized values compared to the standard approach of PW.

(a) Advertising

(b) Alert-zone

Figure 13: The realized values when varying measurement standard deviation
$\sigma_{m}$ (in meters)

##  VI Conclusions and Future Work

While geofences have proven useful for decades, the problem of using them with
sparsely sampled, sporadic data has not received attention in the research
literature. If location is not sampled frequently enough, it increases the
chances of missing a geofence. We proposed a fundamentally new approach to
this problem from a probabilistic and utility-based perspective. We presented
a conceptually simple solution that predicts a user’s location between
measurements. The prediction gives a probability distribution over locations
that changes with time, and thus the predicted probability of being inside the
geofence changes with time. This uncertainty is combined with a payoff matrix
that allows us compute the expected value of either triggering the geofence’s
preprogrammed action or instead waiting and doing nothing. We used Gaussian
processes for our location predictions, but any prediction that gives a
probability distribution as a function of time would work in our framework.

The prediction begins after each measurement and continues until the next
measurement. Since the arrival time of the next measurement is unknown, we
presented a method to stop the prediction based on Poisson-distributed arrival
time for the next measurement. Our technique leads to a light-weight model
that can operate on a mobile device, without triggering new measurements nor
transmitting measurements out of the device. To the best of our knowledge,
none of our major contributions (which includes decision theory, probabilistic
location prediction, and reasoning about sporadic measurements) has appeared
in the research literature of geofences before.

While our algorithm consistently outperforms the baseline over a variety of
settings, there are still opportunities for further work in this area. Example
directions include investigating other techniques for short term location
prediction such as Kalman filters and techniques exploiting the road network;
moving geofences; or a better method to decide when to trigger, such as such
as when entry into a geofence reaches a certain confidence level.

## References

  * [1] J. Liu, B. Priyantha, T. Hart, H. S. Ramos, A. A. Loureiro, and Q. Wang, “Energy efficient gps sensing with cloud offloading,” in _Proceedings of the 10th ACM Conference on Embedded Network Sensor Systems_ , 2012, pp. 85–98.
  * [2] E. G. Zimbelman, R. F. Keefe, E. K. Strand, C. A. Kolden, and A. M. Wempe, “Hazards in motion: Development of mobile geofences for use in logging safety,” _Sensors_ , vol. 17, no. 4, p. 822, 2017.
  * [3] M. B. Fattepur, G. Sharvani, and J. B. Huttanagoudar, “A solution to improve the performance of geofence enabled gnss chipset,” in _2016 International Conference on Computation System and Information Technology for Sustainable Solutions (CSITSS)_. IEEE, 2016, pp. 112–116.
  * [4] T. Nakagawa, W. Yamada, C. Doi, H. Inamura, K. Ohta, M. Suzuki, and H. Morikawa, “Variable interval positioning method for smartphone-based power-saving geofencing,” in _2013 IEEE 24th Annual International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC)_. IEEE, 2013, pp. 3482–3486.
  * [5] C. Cheng, R. Jain, and E. van den Berg, “Location prediction algorithms for mobile wireless systems,” in _Wireless internet handbook: technologies, standards, and application_ , 2003, pp. 245–263.
  * [6] R. E. Kalman _et al._ , “A new approach to linear filtering and prediction problems,” _Journal of basic Engineering_ , vol. 82, no. 1, pp. 35–45, 1960\.
  * [7] A. Doucet, N. De Freitas, and N. Gordon, “An introduction to sequential monte carlo methods,” in _Sequential Monte Carlo methods in practice_. Springer, 2001, pp. 3–14.
  * [8] E. A. Wan and R. Van Der Merwe, “The unscented kalman filter for nonlinear estimation,” in _Proceedings of the IEEE 2000 Adaptive Systems for Signal Processing, Communications, and Control Symposium (Cat. No. 00EX373)_. Ieee, 2000, pp. 153–158.
  * [9] C. K. Williams and C. E. Rasmussen, “Gaussian processes for regression,” in _Proceedings of the 8th International Conference on Neural Information Processing Systems_ , 1995, pp. 514–520.
  * [10] F. V. Diggelen, “Gnss accuracy: Lies, damn lies, and statistics,” _GPS world_ , vol. 18, no. 1, pp. 26–33, 2007.
  * [11] J. H. Zar, _Biostatistical Analysis_ , 4th ed. Upper Saddle River, NJ: Prentice Hall, 1999, pages 575–578.
  * [12] M. Bonakdarpour. (2016) Poisson process: The limiting case of the bernoulli process. [Online]. Available: https://stephens999.github.io/fiveMinuteStats/
bernoulli_poisson_process.html

  * [13] iOS. Monitoring the user’s proximity to geographic regions. [Online]. Available: https://developer.apple.com/documentation/corelocation/
monitoring_the_user_s_proximity_to_geographic_regions

  * [14] Android. Create and monitor geofences. [Online]. Available: https://developer.android.com/training/location/geofencing
  * [15] C. E. Rasmussen and C. K. I. Williams, _Gaussian Processes for Machine Learning_. The MIT Press, 2005.


# Win the Lottery Ticket via Fourier Analysis: Frequencies Guided Network
Pruning

###### Abstract

With the remarkable success of deep learning recently, efficient network
compression algorithms are urgently demanded for releasing the potential
computational power of edge devices, such as smartphones or tablets. However,
optimal network pruning is a non-trivial task which mathematically is an NP-
hard problem. Previous researchers explain training a pruned network as buying
a lottery ticket. In this paper, we investigate the Magnitude-Based Pruning
(MBP) scheme and analyze it from a novel perspective through Fourier analysis
on the deep learning model to guide model designation. Besides explaining the
generalization ability of MBP using Fourier transform, we also propose a novel
two-stage pruning approach, where one stage is to obtain the topological
structure of the pruned network and the other stage is to retrain the pruned
network to recover the capacity using knowledge distillation from lower to
higher on the frequency domain. Extensive experiments on CIFAR-10 and
CIFAR-100 demonstrate the superiority of our novel Fourier analysis based MBP
compared to other traditional MBP algorithms.

Index Terms—  Network Compression, Network Pruning, Unstructured Pruning,
Fourier Analysis

##  1 Introduction

Over the past decade, utilizing deep learning to tackle intricate tasks, which
are barely solved using shallow machine learning techniques solely, has
achieved extremely outstanding performance in various domains of computer
vision [1, 2, 3], information retrieval [4, 5] and multi-modal learning [6, 7,
8]. However, with the drastic increase of neural network parameters,
computational resources are often short-handed. This hinders the broader
deployment of deep models especially for edge devices. To solve this shortage
problem, network pruning is proposed, which builds upon the prune-retrain-
prune paradigm [9] and is proved to be a practical approach to reduce the
computation cost of overparameterized deep neural networks (DNNs).

Following the prune-retrain-prune paradigm, MBP is proposed in [10, 11] which
show that pruning weights of small magnitudes and then retraining the model
without contaminating the overall accuracy where simultaneously reach a pretty
low compression rate on neural network models. Frankle et al. [12] manifests
that the MBP algorithm is to seek an efficient trainable subnetwork as a
replacement for the original dense neural networks, where they empirically
demonstrate that there exist sparse sub-networks that can be trained from
scratch and perform competitively only if the initialization weights of this
subnetwork are appropriate. Moreover, MBP is studied further in [13, 14] where
the authors use a straight-through an estimator in the backward pass and by
which they achieve the state-of-the-art for unstructured pruning in DNNs. Yet
despite all of MBP methods testify the effectiveness of MBP, no rational
explanation has been endowed for why we can successfully retrain the pruned
networks driven from MBP.

In this paper, we investigate the MBP scheme from a novel perspective, Fourier
analysis where we regard DNN as a complex function extracting abstract
representations for different datasets or tasks. Whilst pruning tries to
remove less important representations, measuring the importance of those
representations is non-trivial. Thanks to the power of Fourier analysis which
can approximate any arbitrary functions by the sum of simpler eigenfunctions
on the frequency domain, we intuitively want to measure the importance of the
DNN’s representations with Fourier analysis. It is proved that harmonic
analysis, especially Fourier analysis, can efficiently obtain a spectral
perspective of a perplexing system. However, due to the complexity of DNNs,
conducting Fourier transformation on them remains a problem. Lately, [15, 16,
17] and [18] study DNNs training by Fourier analysis and reveal some profound
results which are: (i) DNNs tend to fit lower-frequency components first
during training by gradient descent, and (ii) lower-frequency components are
more robust to random perturbations of network parameters. We draw
inspirations from [15, 18] and design our network pruning scheme.
Additionally, we endow an explanation using Fourier analysis for why the
pruned network succeeds.

By embracing network pruning with Fourier analysis, the knowledge of data can
be divided into lower frequencies and higher frequencies in the frequency
domain in term of the phase of training unpruned network. Motivated by above
assumptions, we propose a novel two-stage pruning method WILTON (WIn the
Lottery Tickets through the FOurier ANalysis: Frequencies Guided Network
Pruning, using the names “Lottery Tickets” adopted from “Lottery Ticket
Hypothesis” [12]). We first acquire the topological structure and
initialization weights by MBP scheme from the network representing lower-
frequency, and then utilize knowledge distillation to recover the capacity
where we learn the pruned network from the unpruned network which contains
higher-frequency components. As shown in Fig. 1, our architecture is designed
in a parallel fashion to separately learn the structure and parameters of the
pruned network.

In summary, our contributions can be highlighted as follows. (i) Fourier
transform is introduced to the network pruning tasks to understand the
generalization ability of MBP. (ii) A novel pruning method called WILTON is
proposed to train the pruned neural network gradually from lower frequency to
higher frequency. (iii) Our experimental results demonstrate that the proposed
pruning scheme outperforms other recent MBPs on various network architectures,
including ResNet [2] and VGGNet [19].

##  2 WILTON

Fig. 1: The architecture of WILTON. The upper line demonstrates that the
knowledge of data is divided into lower frequencies and higher frequencies in
terms of the phase of training unpruned network by gradient descent. The
bottom line shows that the two-stage pruning scheme firstly learns the
topology structure from lower frequency and then use knowledge distillation to
transfer the higher frequency to the pruned network.

###  2.1 Fourier Analysis of Neural Networks

For general purpose, we only take the networks with rectified linear unit
(ReLU) activations as an example in this section.

We define the ReLU network with $L$ layers of widths $d_{1},\cdots
d_{L}(d=\sum_{k=1}^{L}d_{k})$ and a single output neuron a scalar
function$f:\mathbb{R}^{d}\longmapsto\mathbb{R}$ :

$f(\mathbf{x})=(T^{(L)}\circ\sigma\circ
T^{(L-1)}\circ\cdot\cdot\cdot\circ\sigma\circ T^{(1)})(\mathbf{x})$ (1)

where each $T^{(k)}:\mathbb{R}^{d_{k-1}}\longmapsto\mathbb{R}^{d_{k}}$ is an
affine function and $\sigma(\mathbf{u})=max(0,u_{i})$ denotes the ReLU
activation function acting elementwise on a vector $\mathbf{u}=(u_{1},\cdots
u_{n})$. In the standard basis,
$T^{(k)}(\mathbf{u})=W^{k}\mathbf{u}+\mathbf{b}^{k}$, the $W^{k}$ and
$\mathbf{b}^{k}$ stand for the weight matrix and bias vector of the network’s
$k$-th layer, respectively. For clarity and brevity, we discard the bias term
of the network, then the network can be represented as:

$f(W^{1},\cdots,W^{L};\mathbf{x})$ (2)

The Fourier transform of the ReLU network is fairly an intricate mathematical
problem. In [20] and [18], the authors develop an elegant procedure for
evaluating it in arbitrary dimensions via a recursive application of Stokes
theorem. We study the structure of ReLU networks in terms of their Fourier
representation,
$f(\mathbf{x}):={(2\pi)^{d/2}\int\tilde{f}(\mathbf{k})e^{i\mathbf{k}\cdot\mathbf{x}}\mathbf{dk}}$,
where $\tilde{f}(\mathbf{k}):=\int
f(\mathbf{x})e^{i\mathbf{k}\cdot\mathbf{x}}\mathbf{dx}$ is the Fourier
transform. We skip the formula derivation process and only present the main
corollary here.

The Fourier components of the ReLU network $\widetilde{f}_{\theta}$ with
parameters $\theta$ is given by the function:

$\widetilde{f}_{\theta}(\mathbf{k})=\sum_{n=0}^{d}\frac{C_{n}(\theta,\mathbf{k})1_{H_{n}^{\theta}}(\mathbf{k})}{k^{(n+1)}}$
(3)

where $C_{n}(\theta,\cdot):\mathbb{R}^{d}\longmapsto\mathbb{C}$,
$H_{n}^{\theta}$ is the union of n-dimensional subspaces and
$1_{H_{n}^{\theta}}$ is the indicator over ${H_{n}^{\theta}}$. Note that Eq.3
applies to general ReLU networks with arbitrary width and depth.

The numerator in Eq.3 is bounded by $O(L_{f})$, where $L_{f}$ is the Lipschitz
constant of the network $f(\mathbf{x})$. Further the Lipschitz constant
$L_{f}$ can be bounded by:

$L_{f}\leq\prod_{k=1}^{L}\|W^{k}\|\leq\|\theta\|_{\infty}^{L}\sqrt{d}\prod_{k=1}^{L}d_{k}$
(4)

where $\|\cdot\|$ is the spectral norm of matrix and $\|\cdot\|_{\infty}$ is
the max norm of vector, $d_{k}$ is the number of units in $k$-th layer,
$d=\sum_{k=1}^{L}d_{k}$ and $\theta$ is the concatenated vector of the
network’s whole parameters.

###  2.2 WILTON Pruning Architecture

For mathematical formulation, we use ${M}^{k}\in{\\{0,1\\}}^{d_{k-1}\times
d_{k}},(k=1,\cdots L)$ to denote a mask on $W^{k}$ and define
$W_{p}^{k},(k=1,\cdots L)$ as the parameters of pruned network. Note that the
matrix ${M}^{k},W^{k}$ and $W_{p}^{k},(k=1,\cdots L)$ have same shape. Then
the network pruned network process can be defined by the matrix element-wise
(Hadamard) product of mask $M^{k}$ and original weights $W^{k}$:
$W_{p}^{k}=M^{k}\odot W^{k},(k=1,\cdots L)$. The pruned network can be
represented as:

$f(W_{p}^{1},\cdots,W_{p}^{L};\mathbf{x})=f(M^{1}\odot W^{1},\cdots,M^{L}\odot
W^{L};\mathbf{x}).$ (5)

And then we can define the sparsity of pruned network
$s=\frac{\sum_{k=1}^{L}\|M^{k}\|_{0}}{d}$. A pruning strategy should yield a
pruned network, which can maximize prediction accuracy given an overall
parameter budget.

In the view of knowledge distillation, [21, 22, 23] demonstrate that the
distilled knowledge can be considered as the flow between layers of network.
As the neural network maps from the input space to the output space through
many layers sequentially, by simplifying Eq.2, we assume the distilled
knowledge to be transferred in terms of flow between layers, which is
calculated by computing the Matrix-chain multiplication from successive
layers’ matrix:

$\mathbf{\bar{W}}=\prod_{k=1}^{L}W^{k}.$ (6)

Hereto, we define $\mathbf{\bar{W}}$ an important indicator to measure two
networks’ similarity. So, this indicator of the pruned and unpruned network
should be close. In other word, after pruning the change form
$\mathbf{\bar{W}}$ to $\mathbf{\bar{W}}_{p}=\prod_{k=1}^{L}W^{k}_{p}$ should
be stable. And based on Eq.4, we have an approach to quantitatively analyze
this term.

We obtain an upper bound of $\|\mathbf{\bar{W}}\|$:

$\|\mathbf{\bar{W}}\|=\|\prod_{k=1}^{L}W^{k}\|\leq\prod_{k=1}^{L}\|W^{k}\|.$
(7)

By combining Eq.4 and Eq.7, we have:

$\|\mathbf{\bar{W}}\|\leq\prod_{k=1}^{L}\|W^{k}\|\leq\|\theta\|_{\infty}^{L}\sqrt{d}\prod_{k=1}^{L}d_{k}.$
(8)

Therefore we only have to focus on the last term of Eq.8. After pruning the
redundant weights from unpruned network, we have
$\|\mathbf{\bar{W}}_{p}\|=\|\prod_{k=1}^{L}W^{k}_{p}\|$ of pruned neural
network. The pruning scheme should have the ability to keep this term stable.
Because pruning itself reduces the number of parameters of layers, which leads
to the decrease of $d_{k}$ and $d$. Therefore, the pruning scheme must keep
$\|\theta\|_{\infty}^{L}$ as big as possible. When pruning, we should prune
those weights whose magnitudes are small to keep Eq.8 stable, which is also an
explanation of why magnitude-based pruning methods make sense from the
perspective of Fourier analysis.

Besides the explanation, we also find more intriguing properties of DNN
training through Fourier analysis. In [15, 18], the authors both demonstrate
that during the DNN training process, the lower frequency of data is learned
first and more robust to parameters perturbation. Based on those properties,
we manually unravel the lower and higher frequency knowledge of data on the
frequency domain and bridge the ideology of knowledge distillation [24, 25].
We propose our two-stage pruning scheme, WILTON, where we first obtain a
topological structure and initialization weights by MBP from a low-accuracy
network and then distillate knowledge from the high-accuracy unpruned network
into our pruned network. The architecture of proposed WILTON is shown in Fig.
1.

##  3 experiment

Datasets and Metrics. CIFAR-10 and CIFAR-100 [26] are widely used image
classification datasets, which consists of 60k $32\times 32$ color images
divided into 10 and 100 classes, respectively. We compare the top-1 accuracy
on CIFAR datasets for our approach (WILTON), with vanilla MBP [10], LT [12]
and STR [13].

Implementation details. We define the pruning ratio to be $r_{p}=s\cdot
100(\%)$, where $s$ is the sparsity of pruned network. For a given pruning
ratio $r_{p}$, we train the unpruned network for 200 epochs and prune the
unpruned network at epoch #100. We discuss this hyperparameter in Section.
3.3. After pruning, we use the knowledge distillation to train the pruned
network by the standard way. Specifically, we train the models using SGD with
momentum of 0.9, batch size of 512, and the weight decay rate of 0.0005,
unless state otherwise. The initial learning rate is set to 0.2 and decayed by
0.1 at every 20 or 40 epochs for CIFAR-10 and CIFAR-100, respectively.
Additionally, we use the standard data augmentation (i.e., random horizontal
flip and translation up to 4 pixels) for both the unpruned and pruned models.
We keep 10% of the training data as a validation set and use only 90% for
training.

Table 1: Test accuracy of pruned ResNet32 and VGG16 on CIFAR-10 dataset. The
higher the better. 10.00$\pm$0.00 means the network cannot be trained and thus
infer as random guessing.

Pruning ratio | 90% | 95% | 98%
---|---|---|---
ResNet32(Full Network) | 92.30 | - | -
random | 65.12$\pm$3.89 | 18.87$\pm$2.24 | 10.00$\pm$0.00
vanilla-MBP[10] | 91.17$\pm$0.06 | 87.35$\pm$0.20 | 87.64$\pm$0.28
LT[12] | 92.08$\pm$0.18 | 92.78$\pm$0.04 | 91.24$\pm$0.21
STR[13] | 93.22$\pm$0.11 | 92.76$\pm$0.16 | 91.48$\pm$0.10
WILTON(Ours) | 93.24$\pm$0.13 | 92.79$\pm$0.11 | 91.64$\pm$0.09
VGG16(Full Network) | 91.11 | - | -
random | 43.26$\pm$0.34 | 10.0$\pm$0.00 | 10.00$\pm$0.00
vanilla-MBP[10] | 87.26$\pm$0.15 | 41.17$\pm$0.33 | 10.00$\pm$0.00
LT[12] | 92.50$\pm$0.31 | 91.17$\pm$0.09 | 10.00$\pm$0.00
WILTON(Ours) | 92.88$\pm$0.03 | 91.26$\pm$0.38 | 10.00$\pm$0.00

Table 2: Test accuracy of pruned network from various training period of
unpruned ResNet32 with different pruning ratios.

Ratio Epoch $\\#$ | 0 | 50 | 100 | 150 | 200
---|---|---|---|---|---
90% | 93.25 | 93.27 | 93.37 | 92.28 | 91.30
95% | 92.60 | 92.90 | 92.71 | 92.66 | 92.09
98% | 91.40 | 91.73 | 91.71 | 91.37 | 91.23

Table 3: Test accuracy of pruned ResNet32, ResNet56 and VGG16 on CIFAR-100
dataset. The higher the better. 1.00$\pm$0.00 means the network cannot be
trained and thus infer like random guessing.

Pruning ratio | 90% | 95% | 98%
---|---|---|---
ResNet32(Full Network) | 72.30 | - | -
random | 6.30$\pm$0.21 | 1.00$\pm$0.00 | 1.00$\pm$0.00
vanilla-MBP[10] | 34.96$\pm$0.90 | 27.49$\pm$0.21 | 1.00$\pm$0.00
LT[12] | 70.75$\pm$0.18 | 70.26$\pm$0.27 | 65.52$\pm$0.15
STR[13] | 72.23$\pm$0.06 | 71.40$\pm$0.17 | 68.05$\pm$0.13
WILTON(Ours) | 72.31$\pm$0.26 | 70.39$\pm$0.02 | 68.77$\pm$0.19
ResNet56(Full Network) | 72.32 | - | -
random | 11.02$\pm$0.85 | 4.59$\pm$0.23 | 1.00$\pm$0.00
vanilla-MBP[10] | 49.71$\pm$0.28 | 27.86$\pm$0.57 | 1.00$\pm$0.00
LT[12] | 70.88$\pm$0.25 | 70.17$\pm$0.48 | 66.94$\pm$0.95
STR[13] | 72.40$\pm$0.74 | 71.83$\pm$0.55 | 68.58$\pm$0.22
WILTON(Ours) | 72.31$\pm$0.29 | 71.39$\pm$0.32 | 69.00$\pm$0.19
VGG16(Full Network) | 71.09 | - | -
random | 29.70$\pm$0.77 | 1.00$\pm$0.00 | 1.00$\pm$0.00
vanilla-MBP[10] | 65.38$\pm$0.36 | 8.27$\pm$0.54 | 1.00$\pm$0.00
LT[12] | 70.49$\pm$0.63 | 39.50$\pm$0.48 | 1.00$\pm$0.00
WILTON(Ours) | 70.44$\pm$0.03 | 45.29$\pm$0.60 | 1.00$\pm$0.00

###  3.1 Results on CIFAR-10

On CIFAR-10 [26], we perform experiments on two standard network architectures
– ResNet32 and VGG16 where ResNet32 contains 0.47M parameters and VGG16
consists of 15.3M parameters. We compared our method with vanilla MBP [10,
11], LT [12] and STR [13]. We also report the performance of a full network
and a random pruning baseline. All the methods are compared extensively in the
pruning ratio of 90%, 95%, 98%.

Overall, Table.3 shows that our method WILTON constantly outperform or evenly
perform other pruning state-of-the-art methods in all pruning ratios with
different network architectures. For further comparisons, we discuss the
experimental results for ResNet32 and VGG16, respectively. For ResNet32, as
pruning ratio increases, the performances of all methods drop in different
levels. However, among all methods, WILTON tends to decay slowly which shows
the robustness of our method. For VGG16, the result shows the same trend as of
ResNet32 – accuracy with WILTON deteriorates more slowly than other methods.

###  3.2 Results on CIFAR-100

On CIFAR-100 [26], we conduct experiment with three network architectures –
ResNet32, ResNet56 and VGG16. We compare our method with vanilla MBP [10, 11],
LT [12] and STR [13]. We also report the performance of a full network and a
random pruning baseline. All the methods are compared in the pruning ratio of
90%, 95%, 98%.

Our method achieves competitive and even better performance for all pruning
ratios on different network architectures in Table.3. For ResNet32, as pruning
ratio increases, the performances of all methods drop in different levels.
However, among all methods, WILTON tends to decay slowly which shows the
robustness of our method. For instance, the experiment about pruning ResNet32
shows that the model pruned by WILTON retain 69% accuracy even with only 2%
remaining weights. In contrast, the model pruned with vanilla-MBP lose the
ability of inference completely. It proves the observation that lower-
frequency components are more robust to recover the capability of the network.
For ResNet56, the pruned model with only 10% parameters remaining can
outperform its unpruned counterpart over 0.3%, which indicates the
overparameterization of ResNet. For VGG16, the result shows the same trend as
of ResNet32 – accuracy with WILTON deteriorates more slowly than other
methods. While high-pruning-ratio pruning networks without shortcut structure
tends to block the pathway for forward and backward propagation, the pruning
of VGG16 (without shortcut) shows that the structure of VGG16 without 98%
parameters is destroyed so that all methods perform randomly guessing. An
intuitive explanation is that the network approximating the lower-frequency
components can be represented by a sparse network, so the pruned network
driven from WILTON can keep effective to a large extent.

###  3.3 Pruning Phase Evaluation and Ablation Study

WILTON is a two-stage pruning scheme, first obtaining a topological structure
and initialization weights of the pruned network by MBP and then distilling
knowledge from the high-accuracy unpruned network into the pruned network. On
the unpruned ResNet32 training process on CIFAR-10, we prune 90% weights of
the unpruned network at different epoch (#0, #50, #100, #150 and #200) and
compare different pruned networks. The results are shown in Table. 3. The
performance for early pruning tends to be better than late pruning where
certifies the robustness of lower-frequency components. However, extreme case
like pruning in epoch #0 degrades the performance since the network has not
learn enough representations. That also gives us insights on how to choose the
time to pruning our model such that we can recover the capacity of the
unpruned model.

##  4 conculsion

In this paper, we propose a novel two-stage pruning method named WILTON which
is an interpretable and versatile pruning approach based on Frequency domain
decomposition. By separating knowledge from lower frequency to higher
frequency on the frequency domain, WILTON provides a novel pathway for
exploring network pruning. Finally, our proposed WILTON serves as the
stepstone to understand the optimization and initialization of deep neural
networks.

## References

  * [1] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton,  “Deep learning,”  Nature, 2015.
  * [2] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun,  “Deep residual learning for image recognition,”  in CVPR, 2016.
  * [3] Yupeng Hu, Meng Liu, Xiaobin Su, Zan Gao, and Liqiang Nie,  “Video moment localization via deep cross-modal hashing,”  TIP, 2021.
  * [4] Yinwei Wei, Xiang Wang, Liqiang Nie, Xiangnan He, Richang Hong, and Tat-Seng Chua,  “Mmgcn: Multi-modal graph convolution network for personalized recommendation of micro-video,”  in ACMMM, 2019.
  * [5] Yinwei Wei, Xiang Wang, Qi Li, Liqiang Nie, Yan Li, Xuanping Li, and Tat-Seng Chua,  “Contrastive learning for cold-start recommendation,”  in ACMMM, 2021.
  * [6] Ye Zhu, Yu Wu, Yi Yang, and Yan Yan,  “Saying the unseen: Video descriptions via dialog agents,”  TPAMI, 2021.
  * [7] Ye Zhu, Yu Wu, Yi Yang, and Yan Yan,  “Describing unseen videos via multi-modal cooperative dialog agents,”  in ECCV, 2020.
  * [8] Yupeng Hu, Liqiang Nie, Meng Liu, Kun Wang, Yinglong Wanga, and Xiansheng Hua,  “Coarse-to-fine semantic alignment for cross-modal moment localization,”  TIP, 2021.
  * [9] Yann LeCun, John S Denker, and Sara A Solla,  “Optimal brain damage,”  in NeurIPS, 1990.
  * [10] Song Han, Huizi Mao, and William J Dally,  “Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding,”  in ICLR, 2015.
  * [11] Michael Zhu and Suyog Gupta,  “To prune, or not to prune: exploring the efficacy of pruning for model compression,”  arXiv:1710.01878, 2017.
  * [12] Jonathan Frankle and Michael Carbin,  “The lottery ticket hypothesis: Finding sparse, trainable neural networks,”  in ICLR, 2018.
  * [13] Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi,  “Soft threshold weight reparameterization for learnable sparsity,”  in ICML, 2020.
  * [14] Trevor Gale, Erich Elsen, and Sara Hooker,  “The state of sparsity in deep neural networks,”  arXiv:1902.09574, 2019.
  * [15] Zhiqin John Xu,  “Understanding training and generalization in deep learning by fourier analysis,”  arXiv:1808.04295, 2018.
  * [16] Dong Yin, Raphael Gontijo Lopes, Jon Shlens, Ekin Dogus Cubuk, and Justin Gilmer,  “A fourier perspective on model robustness in computer vision,”  in NeurIPS, 2019.
  * [17] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein,  “On the expressive power of deep neural networks,”  in ICML, 2017.
  * [18] Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred Hamprecht, Yoshua Bengio, and Aaron Courville,  “On the spectral bias of neural networks,”  in ICML, 2019.
  * [19] Karen Simonyan and Andrew Zisserman,  “Very deep convolutional networks for large-scale image recognition,”  arXiv:1409.1556, 2014.
  * [20] Ricardo Diaz, Quang-Nhat Le, and Sinai Robins,  “Fourier transforms of polytopes, solid angle sums, and discrete volume,”  arXiv:1602.08593, 2016.
  * [21] Seung Hyun Lee, Dae Ha Kim, and Byung Cheol Song,  “Self-supervised knowledge distillation using singular value decomposition,”  in ECCV, 2018.
  * [22] Junho Yim, Donggyu Joo, Jihoon Bae, and Junmo Kim,  “A gift from knowledge distillation: Fast optimization, network minimization and transfer learning,”  in CVPR, 2017.
  * [23] Yuzhang Shang, Bin Duan, Ziliang Zong, Liqiang Nie, and Yan Yan,  “Lipschitz continuity guided knowledge distillation,”  in ICCV, 2021.
  * [24] Geoffrey Hinton, Oriol Vinyals, and Jeff Dean,  “Distilling the knowledge in a neural network,”  arXiv:1503.02531, 2015.
  * [25] Jimmy Ba and Rich Caruana,  “Do deep nets really need to be deep?,”  in NeurIPS, 2014.
  * [26] Alex Krizhevsky, Geoffrey Hinton, et al.,  “Learning multiple layers of features from tiny images,”  Tech Report, 2009.