We introduce a new class of objectives for optimal transport computations of datasets in high-dimensional Euclidean spaces. The new objectives are parametrized by $\rho \geq 1$, and provide a metric space $\calR_{\rho}(\cdot, \cdot)$ for discrete probability distributions in $\R^d$. As $\rho$ approaches $1$, the metric approaches the Earth Mover's distance, but for $\rho$ larger than (but close to) $1$, admits significantly faster algorithms. Namely, for distributions $\mu$ and $\nu$ supported on $n$ and $m$ vectors in $\R^d$ of norm at most $r$ and any $\eps > 0$, we give an algorithm which outputs an additive $\eps r$-approximation to $\calR_{\rho}(\mu, \nu)$ in time $(n+m) \cdot \poly((nm)^{(\rho-1)/\rho} \cdot 2^{\rho / (\rho-1)} / \eps)$.

Optimal transport, Earth Mover's distance, Sinkhorn distance

§ OPEN PROBLEMS

We hope that our approach, of slightly changing the problem, will prove useful for other Euclidean problems for which we do not have fast algorithms with $(1+\eps)$-approximations. We mention two immediate open problems:

* Multiplicative $(1+\eps)$-approximations for $\mathcal{R}_{\rho}(\mu, \nu)$. Our algorithms achieved additive $\eps r$-approximations for datasets bounded within distance $r$, but a more accurate multiplicative $(1+\eps)$-approximation would be desired when the dataset may not necessarily be bounded. Does there exists an algorithm which is just as fast as Theorem <ref> and outputs a number $\hat{\boldeta}$ which is between $\mathcal{R}_{\rho}(\mu, \nu)$ and $(1+\eps) \mathcal{R}_{\rho}(\mu, \nu)$ with high probability?

* Accurate Approximations for $\EMD$. It is still possible that for any $\eps > 0$, there exists an algorithm which can estimate the cost of $\EMD(\mu, \nu)$ up to a multiplicative $(1+\eps)$-factor in time $n \cdot \poly(d \log n/\eps)$. Does there exist such an algorithm, or is there compelling complexity-theoretic reasons why this may not be possible? We note that [Rohatgi, 2019] shows that, in the case $\mu$ and $\nu$ are uniform on a support of size $n$, such an algorithm should not be able to output a $(1+\eps)$-approximate matching between points of $\mu$ and $\nu$ (assuming the Hitting Set conjecture). However, no such evidence against near-linear time algorithms for the cost of $\EMD$ exists.

Part of this work was done while Erik Waingarten was a postdoc at Stanford University, supported by an NSF postdoctoral fellowship and by Moses Charikar's Simons Investigator Award.

[Agarwal and Sharathkumar, 2014]
Pankaj K. Agarwal and R. Sharathkumar.
Approximation algorithms for bipartite matching with metric and
geometric costs.
In Proceedings of the 46th ACM Symposium on the Theory of
Computing (STOC '2014), pages 555–564, 2014.

[Agarwal et al., 2022]
Pankaj K. Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao.
Deterministic, near-linear $\epsilon$-approximation algorithm for
geometric bipartite matching.
In Proceedings of the 54th ACM Symposium on the Theory of
Computing (STOC '2022), 2022.

[Altschuler et al., 2017]
Jason Altschuler, Jonathan Weed, and Philippe Rigollet.
Near-linear time approximation algorithms for optimal transport via
sinkhorn iteration.
In Proceedings of Advances in Neural Information Processing
Systems (NeurIPS '2017), 2017.

[Altschuler et al., 2019]
Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles-Weed.
Massively scalable sinkhorn distances via the nyström method.
In Proceedings of Advances in Neural Information Processing
Systems 32 (NeurIPS '2019), 2019.

[Andoni and Razenshteyn, 2015]
Alexandr Andoni and Ilya Razenshteyn.
Optimal data-dependent hashing for approximate near neighbors.
In Proceedings of the 47th ACM Symposium on the Theory of
Computing (STOC '2015), pages 793–801, 2015.
Available as arXiv:1501.01062.

[Andoni et al., 2008]
Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer.
Earth mover distance over high-dimensional spaces.
In Proceedings of the 19th ACM-SIAM Symposium on Discrete
Algorithms (SODA '2008), pages 343–352, 2008.

[Andoni et al., 2009]
Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David Woodruff.
Efficient sketches for earth-mover distance, with applications.
In Proceedings of the 50th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '2009), 2009.

[Andoni et al., 2014]
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev.
Parallel algorithms for geometric graph problems.
In Proceedings of the 46th ACM Symposium on the Theory of
Computing (STOC '2014), 2014.

[Andoni et al., 2015]
Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn.
Sketching and embedding are equivalent for norms.
In Proceedings of the 47th ACM Symposium on the Theory of
Computing (STOC '2015), pages 479–488, 2015.
Available as arXiv:1411.2577.

[Arjovsky et al., 2017]
Martin Arjovsky, Soumith Chintala, and Léon Bottou.
Wasserstein generative adversarial networks.
In Proceedings of the 34th International Conference on Machine
Learning (ICML '2017), 2017.

[Backurs et al., 2018]
Arturs Backurs, Moses Charikar, Piotr Indyk, and Paris Siminelakis.
Efficient density evaluation for smooth kernels.
In Proceedings of the 59th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '2018), 2018.

[Backurs et al., 2020]
Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner.
Scalable nearest neighbor search for optimal transport.
In Proceedings of the 37th International Conference on Machine
Learning (ICML '2020), 2020.

[Backurs et al., 2021]
Arturs Backurs, Piotr Indyk, Cameron Musco, and Tal Wagner.
Faster kernel matrix algebra via density estimation.
In Proceedings of the 38th International Conference on Machine
Learning (ICML '2021), 2021.

[Bakshi et al., 2022]
Ainesh Bakshi, Piotr Indyk, Praneeth Kacham, Sandeep Silwal, and Samson Zhou.
Sub-quadratic algorithms for kernel matrices via kernel density
In arXiv preprint arXiv:2212.00642, 2022.

[Bačkurs and Indyk, 2014]
Arturs Bačkurs and Piotr Indyk.
Better embeddings for planar earth-mover distance over sparse sets.
In Proceedings of the 41st International Colloquium on
Automata, Languages and Programming (ICALP '2014), 2014.

[Bonneel et al., 2015]
Nicolas Bonneel, Julien Rabin, Gabriel Peyré, and Hanspeter Pfister.
Sliced and radon wasserstein barycenters of measures.
Journal of Mathematical Imaging and Vision, 51, 2015.

[Charikar, 2002]
Moses Charikar.
Similarity estimation techniques from rounding algorithms.
In Proceedings of the 34th ACM Symposium on the Theory of
Computing (STOC '2002), pages 380–388, 2002.

[Charikar and Siminelakis, 2017]
Moses Charikar and Paris Siminelakis.
Hashing-based-estimators for kernel density in high dimensions.
In Proceedings of the 58th Annual IEEE Symposium on
Foundations of Computer Science (FOCS '2017), 2017.

[Charikar et al., 2020]
Moses Charikar, Michael Kapralov, Navid Nouri, and Paris Siminelakis.
Kernel density estimation through density constrained near neighbor
In Proceedings of the 61st Annual IEEE Symposium on
Foundations of Computer Science (FOCS '2020), 2020.

[Chen et al., 2022]
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg,
and Sushant Sachdeva.
Maximum flow and minimum-cost flow in almost-linear time.
In Proceedings of the 63rd Annual IEEE Symposium on
Foudnations of Computer Science (FOCS '2022), 2022a.

[Chen et al., 2022]
Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten.
New streaming algorithms for high dimensional emd and mst.
In Proceedings of the 54th ACM Symposium on the Theory of
Computing (STOC '2022), 2022b.

[Courty et al., 2016]
Nicolas Courty, Rémy Flamary, Devis Tuia, and Alain Rakotomamonjy.
Optimal transport for domain adaptation.
IEEE Transactions on Pattern Analysis and Machine
Intelligence, 390 (9):0 1853 – 1865, 2016.

[Cuturi, 2013]
Marco Cuturi.
Sinkhorn distances: Lightspeed computation of optimal transport.
In Proceedings of Advances in Neural Information Processing
Systems (NIPS '2013), 2013.

[Har-Peled et al., 2013]
Sariel Har-Peled, Piotr Indyk, and Anastasios Sidiropoulos.
Euclidean spanners in high dimensions.
In Proceedings of the 24th ACM-SIAM Symposium on Discrete
Algorithms (SODA '2013), 2013.

[Indyk, 2004]
Piotr Indyk.
Approximate nearest neighbor under edit distance via product metrics.
In Proceedings of the 15th ACM-SIAM Symposium on Discrete
Algorithms (SODA '2004), pages 646–650, 2004.

[Indyk and Thaper, 2003]
Piotr Indyk and Nitin Thaper.
Fast color image retrieval via embeddings.
In Workshop on Statistical and Computational Theories of Vision
(at ICCV), 2003.

[Khesin et al., 2019]
Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov.
Preconditioning for the geometric transportation problem.
In Proceedings of the 35th International Symposium on
Computational Geometry (SoCG '2019), 2019.

[Kiem et al., 2020]
Pham Kiem, Khang Le, Nhat Ho, Tung Pham, and Hung Bui.
On unbalanced optimal transport: An analysis of sinkhorn algorithm.
In Proceedings of the International Conference on Machine
Learning (ICML '2020), 2020.

[Kusner et al., 2015]
Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger.
From word embeddings to document distances.
In Proceedings of the 32nd International Conference on Machine
Learning (ICML '2015), 2015.

[Le et al., 2021]
Khang Le, Huy Nguyen, Quang M Nguyen, Tung Pham, Hung Bui, and Nhat Ho.
On robust optimal transport: computational complexity and barycenter
In Proceedings of Advances in Neural Information Processing
Systems 34 (NeurIPS '2021), 2021.

[Paty and Cuturi, 2019]
François-Pierre Paty and Marco Cuturi.
Subspace robust wasserstein distances.
In Proceedings of the 36th International Conference on Machine
Learning (ICML '2019), 2019.

[Peyré and Cuturi, 2019]
Gabriel Peyré and Marco Cuturi.
Computational optimal transport: With applications to data science.
Foundations and Trends® in Machine Learning,
110 (5–6):0 355–607, 2019.

[Rohatgi, 2019]
Dhruv Rohatgi.
Conditional hardness of earth movers distance.
In Approximation, Randomization and Combinatorial Optimization.
Algorithms and Techniques, 2019.

[Sharathkumar and Agarwal, 2012]
R. Sharathkumar and Pankaj K. Agarwal.
A near-linear time $\epsilon$-approximation algorithm for bipartite
geometric matching.
In Proceedings of the 44th ACM Symposium on the Theory of
Computing (STOC '2012), 2012.

[Sherman, 2017]
Jonah Sherman.
Generalized preconditioning and undirected minimum cost flow.
In Proceedings of the 28th ACM-SIAM Symposium on Discrete
Algorithms (SODA '2017), 2017.

[Siminelakis et al., 2019]
Paris Siminelakis, Kexin Rong, Peter Bailis, Moses Charikar, and Philip Levis.
Rehashing kernel evaluation in high dimensions.
In Proceedings of the 36th International Conference on Machine
Learning (ICML '2019), 2019.


# Information Theoretic Interpretation of Deep learning

Tianchen Zhao
Department of Mathematics
University of Michigan
Ann Arbor, MI 48104
<EMAIL_ADDRESS>
###### Abstract

We interpret part of the experimental results of Shwartz-Ziv and Tishby
(2017). Inspired by these results, we established a conjecture of the dynamics
of the machinary of deep neural network. This conjecture can be used to
explain the counterpart result by Saxe et al. (2018).

##  1 Introduction

###  1.1 Set up

Consider a deep learning problem, the training data set
$\mathcal{D}=\\{(X_{i},Y_{i})\\}_{i=1:n}$ is known, where
$\\{X_{i}\\}_{i=1:n}$ are the objects of interest, and $\\{Y_{i}\\}_{i=1:n}$
are the corresponding labels, sampled from random variables $(X,Y)$ with
unknown joint distribution. For example, $X$ could be the continuous random
variable over $[0,1]^{n}$ for some large integer $n$, representing the image
of a single digit, and $Y$ is a discrete random variable with integer ranging
from 0 to 9.

In practice, the data $\mathcal{D}$ is fed into a deep neural network
$\mathcal{F}$ parametrized by $w$ which is of very high dimension. For each
object $x$, $\mathcal{F}(\tilde{y}|x;w)$ assigns $\\{\tilde{Y}=\tilde{y}\\}$ a
probability, and the prediction is taken from the value with highest
probability. In practice this is usually achieved by using softmax function.
The goal is to use an optimization algorithm to train the parameter $w$ of
$\mathcal{F}$ such that the joint probability of$(X,\tilde{Y})$ matches the
joint probability of $(X,Y)$.

###  1.2 Motivation

Our work is primarily motivated by Zhang et al. (2017a) and Poggio et al.
(2017). In an underdeterministic problem where the number of parameter $w$ is
way larger than the amount of samples $\mathcal{D}$, there are typically
infinite many solutions for $w$. According to Occam’s razor, "simple"
solutions are usually desired. In practice, the training of a deep neural
network is not explicitly regularized, so there’s no obvious guarantee that
the solution $w$ we trained is "simple". However, the experimental results
report that the model is still steadly improving after the set of solutions
have already been reached. It’s commonly believed that the optimization
algorithm used, named stochastic gradient descent, is improving $w$ among the
solutions of the underdetermined system.

The experiments performed by Shwartz-Ziv and Tishby (2017) give an answer to
this phenomina from an information theoretic perspective. In their experiment,
they designed a binary classification problem and trained a fully connected
feed-forward neural network using SGD and cross-entropy loss function.

For each epoch during the training, they discretized the values for the last
feature layer $\tilde{Y}$ into 30 bins over -1 and 1(which follows from the
sigmoid activation function). Then $P(\tilde{Y},X)$ can be directly
approximated by running the neural nets. Then they compute

$P(\tilde{Y}|x)=\frac{P(\tilde{Y},x)}{P(x)},$

which is used to compute

$P(\tilde{Y},Y)=\sum_{x}P(x,Y)P(\tilde{Y}|x,Y)=\sum_{x}P(x,Y)P(\tilde{Y}|x).$

$P(\tilde{Y},X)$ and $P(\tilde{Y},Y)$ are all we need to estimate
$\mathrm{I}(\tilde{Y};X)$ and $\mathrm{I}(Y;\tilde{Y})$.

Their goal is to estimate the dynamics of the mutual information
$\mathrm{I}(\tilde{Y};X)$ and $\mathrm{I}(Y;\tilde{Y})$. Here
$\mathrm{I}(\tilde{Y};X)$ can be interpreted as a measure of how much
information $\tilde{Y}$ retains("encodes") from $X$, and similarly
$\mathrm{I}(Y;\tilde{Y})$ is how much information $\tilde{Y}$
preserves("decodes") from $Y$. We encourage the reader to watch the fantastic
video of the optimization process in the information plane at
https://goo.gl/rygyIT.

In this paper we are interested in the behaviour of their last layer(in
orange), which is essentially the behaviour of $\mathrm{I}(X;\tilde{Y})$ and
$\mathrm{I}(Y;\tilde{Y})$. At the beginning of the training, both
$\mathrm{I}(X;\tilde{Y})$ and $\mathrm{I}(Y;\tilde{Y})$ increases, meaning the
network is "memorizing" the data from $X$ and outputing more meaningful
information to $Y$, note that this process is fast. Then
$\mathrm{I}(X;\tilde{Y})$ starts to decrease while $\mathrm{I}(Y;\tilde{Y})$
keeps increasing, meaning the network is "forgetting" the data it just
memorized but is still improving to give more information about $Y$, note that
this process is slow. The first part is named the fitting phase and the second
part is named the compression phase.

Saxe et al. (2018) started a similar line of work measuring the dynamics of
the mutual information. They proposed the following:

1\. The compression phase is not explicit if the network uses ReLU activation
function instead throughout the network.

2\. The compression phase is happening alongside with the fitting phase if the
input data is Gaussian-like and the labels are assigned randomly.

3\. It is theoretically implausible to measure the information in the
intermediate layer, given that mutual information between continuous random
variables is in general ill-defined.

###  1.3 Our contribution

####  1.3.1 Decomposition of Deep Network

We propose the following conjecture of the machinary of deep neural
network(see Figure 1): the data is transformed into linearly seperable feature
by the nonlinear ReLU network, which is "almost invertible" as to be explained
in detail below. The following full connected layer and sigmoid/softmax
function together behave like a multiclass SVM, giving the best prediction
among all available classes.

Figure 1: Our proposed decomposition of Deep Neural Network

####  1.3.2 Interpretation of Information Theory

Given this structure, we can give interpretation to the experimental results
by Shwartz-Ziv and Tishby (2017). The fitting phase corresponds to finding
parameters from ReLU network to organize the features in last layer into a
linearly seperable fashion, and find full connected parameters represent
hyperplanes to seperate the features. The compression phase corresponds to
finding parameters maximizing the margin of the linear seperation, which is
essentially driven by the randomness of the SGD algorithm. This progresses
slowly as we will prove in Section 2.1. Note that the procedure of the margin
maximization is to find the "support feature" and "forgetting" other features,
enabled by the sigmoid/softmax function. It follows that mutual information
between input $X$ and prediction $\tilde{Y}$ is diminising during this phase.

The phenomena propose by Saxe et al. (2018) can therefore be explained:

1\. If the activation function used in last layer is replaced by ReLU, then
the SVM structure will be destroyed. The network is not "forgetting"
approximately half of the features, so the compression phase will not be
explicit.

2\. The Gaussian input is isotropic so no network can transform this data into
a linearly seperable one. We argue that compression phase only exists if
there’s a margin between data from different classes.

3\. We agree that it’s often dangerous to define mutual information between
continuous valued random variables. In general, if the joint probability of
two continuous random variable is not degenerate over an open neighborhood,
then there exists an invertible mapping, which needs infinite amount of
information to describe the mutual relationship. In fact, we do believe that
the neural network will have better performance if the intermediate layers can
fully preserve the information of $X$. In this case ReLU does a better job
than sigmoid or tanh functions do, which matches the experimental reports by
Nair and Hinton (2010). But the last layer should be fully connected and
activated by sigmoid function, as indicated by Krizhevsky et al. (2012).

However, the mutual information between continuous valued random variable and
discrete valued random variable is well defined in a sense that the
discretized measurement converges(see Appendix C). So we argue that the
expirical measurement by Shwartz-Ziv and Tishby (2017) on the last layer
remains theoretical valid, which supports our hypothesis. Throughout our
theoretical analysis below, both $Y$, $\tilde{Y}$ represent a discretized
prediction random variable when comparing with $X$.

####  1.3.3 Interpretation of Res-Net

Residual Network by He et al. (2015), the winner of ILSVRC2015, is one of the
best existing deep network structures. Here we explain why it is so successful
from our theory.

It’s well known that a network that is too deep is not working very well. One
of the reason could be, from our perspective, there’s too much information
loss from the first part, $F$, of our proposed structure (Figure 1). Res-Net
is designed to allow the model to "learn" identity map easily. Specifically,
in Kraskov et al. (2004), they mentioned in appendix that mutual information
is fully preserved under homeomorphisms (smooth and uniquely invertible maps).
In Res-Net, the building block with input vector $x$ and output vector $y$ is
related as:

$y=\mathcal{L}(x)+x=(\mathcal{L}+I)(x),$ (1)

where the operator $\mathcal{L}$ could be a composition of activation
functions, convolution, drop-out(Srivastava et al. (2014)) and batch
normalization(Ioffe and Szegedy (2015)). See Section 3.1 for more details.

It can be shown that (see Appendix E for a proof) if the operator norm
$|\mathcal{L}|<1$, then $\mathcal{L}+I$ is theoretically guaranteed to have an
inverse, which enables information preservation between intermediate layers.
In Section 3.3 we experimentally verified that $|\mathcal{L}|<1$ for all
intermediate layers.

The main strength of Res-Net, in our understanding, is it allows the deep
mapping $F$ in Figure 1 to be invertible, independent of $\mathcal{L}$, which
is almost never invertible due to the use of ReLU, convolution, drop-out and
other singular operations.

In the work by Jacobsen et al. (2018), they built an deep invertible networks
and showed that a network could be successful without losing any information
in the intermediate layers.

###  1.4 Related work

Zheng et al. (2018) understood DNN from a Maximum entropy perspective.
Chaudhari et al. (2016) used entropy to detect wide valleys for SGD algorithm.
Shamir et al. (2010) proved generalization property of IB framework. Achille
and Soatto (2016) investigated the amount of information loss through various
of operations in deep network. Troost et al. (2018) proved an upper bound on
the number of nodes needed for a two-layer network to seperate the data. Alemi
et al. (2016) designed a variational approximation to the IB framework.

##  2 Proofs

In this section we prove our conjecture in Figure 1 as follows:

Figure 2: Chart of logic for our proof.

1\. We prove that it takes $\mathrm{I}(Y;\tilde{Y})$ a time with polynomial
order to grow during the fitting phase, and a time with exponential order to
grow during the compression phase, which matches the video of the information
plane dynamics by Shwartz-Ziv and Tishby (2017).

2\. We assume that $F$ in Figure 1 is almost invertible in the sense that
$\mathrm{I}(F(X);Y)\approx\mathrm{I}(X;Y)$.

We argue that the Deep Network $\mathcal{F}$, treated as an abstract function
describing relationship between $\tilde{Y}$ and $(X,Y)$, is governed, if the
word "parametrized" is not proper, by the quantities $\mathrm{I}(X;\tilde{Y})$
and $\mathrm{I}(Y;\tilde{Y})$.

From an information theoretic set up, the IB problem can be considered as:

$\mathrm{I}(X;\tilde{Y})-\alpha\mathrm{I}(Y;\tilde{Y})=\mathrm{I}(F(X);\tilde{Y})-\alpha\mathrm{I}(Y;\tilde{Y}),$
(2)

where $\alpha$ is some positive constant. Therefore we can abuse the notation
between $X$ and $F(X)$ as they are equivalent in the information theoretic
setting. In particular, we have $\tilde{Y}=f(X)$ where $f$ is defined in
Figure 1.

Then we prove there’s a direct relationship between IB problem and SVM problem
in linear case.

We conclude that deep neural network, from a information theoretic point of
view, can be reduced to a hard-margin SVM problem.

3\. We discuss the notion of generalization in our context.

###  2.1 Machinary of SGD

There is a history of work towarding the behaviour of discrete SGD. In
particular, Roberts and Tweedie (1996) shows that the discrete Langevin
difussion converges to the target distribution exponentially fast in time.
This is a general result applying to Markov Chain Monte Carlo(MCMC) and is not
practical because SGD is a "path-finder" with a diminishing step length.
Raginsky et al. (2017) and Tzen et al. (2018) showed that the searching path
of SGD needs time of exponential order to jump from one local min to another
local min, which is intuitively why the compression phase is slow. Zhang et
al. (2017b) showed that the SGD path needs time of polynomial order to enter
the first "good" local min, which is intuitively why the fitting phase is
fast.

In our work, we present a similar result from an information theoretic
perspective, by using an analogy to standard stochastic convex analysis in
Bottou (1998).

Recall this video from Shwartz-Ziv and Tishby (2017) on information plane at
https://goo.gl/rygyIT.

######  Claim 2.1.

The general form of SGD is given by:

$w_{t+1}=w_{t}-a_{t}\nabla F(w_{t})-b_{t}B,$ (3)

where $a_{t},b_{t}$ are positive constant varying with time $t$ and $B$ is the
standard Gaussian $\mathcal{N}(0,\mathrm{I})$.

In particular, consider a Langevin Monte Carlo(LMC) setting where
$a_{t}=\frac{1}{t}$ and $b_{t}=\frac{1}{\sqrt{t}}$.

Then $\mathrm{I}(Y;\tilde{Y})$ reaches local maximum in time with polynomial
order, and hits higher local maximum in time with exponential order.

###### Proof.

From Appendix A, we have:

$\mathrm{I}(X;\tilde{Y})\leq
2(\mathrm{Var}(p(\tilde{y}))+\mathrm{Var}(p(\tilde{y}|x))).$ (4)

From Appendix B, we have:

$\mathrm{I}(Y;\tilde{Y})\geq
A+\log(\prod_{i=1}^{n}f(y_{i}|x_{i};w_{t}))+\sum_{i=1}^{n}\log(p(y_{i}|x_{i})).$
(5)

Now I focus on showing this lower bound (5) is first increasing polynomially
fast, then logarithmically slow, driven by the machinary of SGD.

Denote $F(w_{t})=-\sum_{i=1}^{n}\log(f(y_{i}|x_{i},w_{t}))$ and consider the
SGD mechanics in general form as follows:

$w_{t+1}=w_{t}-a_{t}\nabla F(w_{t})-b_{t}B,$ (6)

where $a_{t},b_{t}$ are positive constant varying with time $t$ and $B$ is
standard Gaussian $\mathcal{N}(0,\mathrm{I})$.

Denote a discrete set of local minimas and saddle points of $F$ as
$\mathcal{C}$.

Define the metric $\rho$ as:

$\rho(w,\mathcal{C})=\inf\\{||w-c||_{2}:c\in\mathcal{C}\\}.$ (7)

Assumption:

(1) $F$ is $M$ smooth with respect to $\mathcal{C}$:

Let $c_{x}=arg\,inf_{c}\\{||x-c||_{2}:c\in\mathcal{C}\\}$, then $||\nabla
F(x)-\nabla F(x)||_{2}\leq M||x-y||_{2}$, for all $x,y\in W$ satisfying
$c_{x}=c_{y}$.

(2) $F$ is $m$ strongly convex with respect to $\mathcal{C}$:

Let $c_{x}=arg\,inf_{c}\\{||x-c||_{2}:c\in\mathcal{C}\\}$, then $\langle\nabla
F(x)-\nabla F(x),x-y\rangle\geq m||x-y||_{2}^{2}$, for all $x,y\in W$
satisfying $c_{x}=c_{y}$.

Now suppose $w_{1}$ is closed to $w^{*}\in\mathcal{C}$, where $w^{*}$ is more
than O(t) away from other element in $\mathcal{C}$, then if we consider the
training process restricted to a polynomial time regime, we have
$\rho(w_{t},\mathcal{C})=||w_{t}-w^{*}||$, and we have the following:

$\begin{array}[]{lcl}||w_{t+1}-w^{*}||^{2}&=&||w_{t}-a_{t}\nabla
F(w_{t})-b_{t}B-w^{*}||^{2}\\\ &=&||w_{t}-w^{*}||^{2}-2\langle
w_{t}-w^{*},a_{t}\nabla F(w_{t})+b_{t}B\rangle+||a_{t}\nabla
F(w_{t})+b_{t}B||^{2}\end{array}$ (8)

Taking expectation with respect to filtration $\mathcal{F}_{t}$ at time $t$
gives:

$\begin{array}[]{lcl}\mathrm{E}(||w_{t+1}-w^{*}||^{2}|\mathcal{F}_{t})&=&||w_{t}-w^{*}||^{2}-2a_{t}\langle
w_{t}-w^{*},\nabla F(w_{t})\rangle+a_{t}^{2}||\nabla
F(w_{t})||^{2}+b_{t}^{2}\\\
&\leq&||w_{t}-w^{*}||^{2}-2a_{t}m||w_{t}-w^{*}||^{2}+a_{t}^{2}M^{2}||w_{t}-w^{*}||^{2}+b_{t}^{2}\\\
&=&(1-2a_{t}m+a_{t}^{2}M)||w_{t}-w^{*}||^{2}+b_{t}^{2}\end{array}$ (9)

Now consider a Langevin Monte Carlo(LMC) setting where $a_{t}=\frac{1}{t}$ and
$b_{t}=\frac{1}{\sqrt{t}}$. Then (7) becomes:

$\begin{array}[]{lcl}\mathrm{E}(||w_{t+1}-w^{*}||^{2}|\mathcal{F}_{t})&=&(1-2\frac{m}{t}+\frac{M^{2}}{t^{2}})||w_{t}-w^{*}||^{2}+\frac{1}{t}\\\
\mathrm{E}(||w_{t+1}-w^{*}||^{2})&=&(1-2\frac{m}{t}+\frac{M^{2}}{t^{2}})\mathrm{E}(||w_{t}-w^{*}||^{2})+\frac{1}{t}\\\
\mathrm{E}(||w_{t+1}-w^{*}||^{2})&\leq&\prod_{s=1}^{t}(1-2\frac{m}{s}+\frac{M^{2}}{s^{2}})\mathrm{E}(||w_{1}-w^{*}||^{2})+\sum_{s=1}^{t}\frac{1}{s}\\\
&=&\prod_{s=1}^{t}(1-2\frac{m}{s}+\frac{M^{2}}{s^{2}})\mathrm{E}(||w_{1}-w^{*}||^{2})+O(\log(t)+1)\end{array}$
(10)

According to L’Hopital’s rule:

$\begin{array}[]{lcl}\lim_{s\rightarrow\infty}\frac{\log(1-2\frac{m}{s}+\frac{M^{2}}{s^{2}})}{\frac{1}{s}}&=&\lim_{s\rightarrow\infty}\frac{\frac{2s^{-2}m-2M^{2}s^{-3}}{1-2\frac{m}{s}+\frac{M^{2}}{s^{2}}}}{-s^{-2}}\\\
&=&-2m.\end{array}$ (11)

So $\log(1-2\frac{m}{s}+\frac{M^{2}}{s^{2}})$ is comparable with
$\frac{1}{s}$, and $\sum_{s=1}^{t}\log(1-2\frac{m}{s}+\frac{M^{2}}{s^{2}})$ is
comparable with $-\log(t)$ and therefore
$\prod_{s=1}^{t}(1-2\frac{m}{s}+\frac{M^{2}}{s^{2}})$ is of order
$O(\frac{1}{t})$.

So our conclusion is:

$\mathrm{E}(||w_{t+1}-w^{*}||^{2})=O(\frac{1}{t})\mathrm{E}(||w_{1}-w^{*}||^{2})+O(\log(t))$
(12)

This shows under a polynomial time regime, $w_{t}$ is converging to a local
min of $F$ linearly fast.

But if we consider the exponential time regime, the above analysis is invalid
because the last term of (10) is innegligible. There’s a possibility that
$w_{t}$ may jump to another $w^{**}\in\mathcal{C}$.

Here we conclude that the lower bound (5) of the quantity of interest
converges to a local min in polynomial time, then switch higher to "better"
local max in exponential time, which explains the video of Tishby’s. ∎

###  2.2 Relationship between IB and SVM

For simplicity we prove the result for binary classification.

######  Claim 2.2.

Consider a binary classification problem where the data set
$\mathcal{D}=(x_{i},y_{i})$ are linearly seperable. $p(\tilde{y}=1|x,w)$ is
modeled by $f(x,w)=\sigma(w^{t}x)$ and $p(\tilde{y}=-1|x,w)=1-f(x,w)$. Recall
that $\sigma(t)=\frac{1}{1+e^{-t}}$.

Given a IB problem:

$Minimize\textrm{ }\mathrm{I}(X;\tilde{Y})-\alpha\mathrm{I}(Y;\tilde{Y})$ (13)

it can be formulated as hard margin SVM problem.

###### Proof.

From Appendix A we have that:

$\mathrm{I}(X;\tilde{Y})\leq
2(\mathrm{Var}(p(\tilde{y}))+\mathrm{Var}(p(\tilde{y}|x)))$ (14)

Here we make an assumption that for the models we trained over time, it’s
output $\tilde{Y}$ is approximately uniform distributed over the finite
labels. So we treat $p(\tilde{y_{i}})$ as constant for all $i$. In particular,
we assume: $p(\tilde{y}=1)\approx p(\tilde{y}=-1)\approx\frac{1}{2}$, then the
first term of (14) on RHS can be controlled:

$\mathrm{Var}(p(\tilde{y}))\leq D,$ (15)

for some constant $D$.

We can bound the second term of (14) on RHS by:

$\begin{array}[]{lcl}\mathrm{Var}(p(\tilde{y}|x))&\leq&\int_{\tilde{Y}}\int_{X}p(x,\tilde{y})p(\tilde{y}|x)^{2}dxd\tilde{y}\\\
&=&\int_{X}p(\tilde{y}=1|x)^{3}p(x)dx+\int_{X}p(\tilde{y}=-1|x)^{3}p(x)dx\\\
&=&\int_{X}(\sigma(w^{t}x))^{3}p(x)dx+\int_{X}(1-\sigma(w^{t}x))^{3}p(x)dx\\\
&=&\int_{X}(1-3\sigma(w^{t}x)+3\sigma(w^{t}x)^{2})p(x)dx\\\
&=&\frac{1}{4}+3\int_{X}(\sigma(w^{t}x)-\frac{1}{2})^{2}p(x)dx\\\ \end{array}$
(16)

Consider the 1st order Taylor expansion:

$\sigma(w^{t}x)=\sigma(0)+\sigma^{\prime}(c)(w^{t}x)\leq\frac{1}{2}+\frac{1}{4}w^{t}x.$
(17)

Substitute it into (16) to get:

$\begin{array}[]{lcl}\mathrm{Var}(p(\tilde{y}|x))&\leq&\frac{1}{4}+3\int_{X}(\sigma(w^{t}x)-\frac{1}{2})^{2}p(x)dx\\\
&=&\frac{1}{4}+\frac{3}{16}\int_{X}(w^{t}x)^{2}p(x)dx\\\
&=&\frac{1}{4}+(\frac{3}{16}\int_{X}x^{2}p(x)dx)||w||^{2}\end{array}$ (18)

To conclude, we have a bound of (14) the form:

$\mathrm{I}(X;\tilde{Y})\leq A+B||w||^{2}.$ (19)

From Appendix B, we approximate the Mutual information
$\mathrm{I}(Y;\tilde{Y})$ by:

$\begin{array}[]{lcl}\mathrm{I}(Y;\tilde{Y})&=&\sum_{i}\log(\frac{p(y_{i},\tilde{y_{i}})}{p(y_{i})p(\tilde{y_{i}})})\\\
&=&\sum_{i=1}^{n}\log(\frac{\sum_{j=1}^{n}p(y_{i},\tilde{y_{i}}|x_{j})}{p(y_{i})p(\tilde{y_{i}})})\\\
&=&\sum_{i=1}^{n}\log(\frac{\sum_{j=1}^{n}p(y_{i}|\tilde{y_{i}},x_{j})p(\tilde{y_{i}}|x_{j})}{p(y_{i})p(\tilde{y_{i}})})\\\
&=&\sum_{i=1}^{n}\log(\frac{\sum_{j=1}^{n}p(y_{i}|x_{j})p(\tilde{y_{i}}|x_{j})}{p(y_{i})p(\tilde{y_{i}})}).\end{array}$
(20)

with high probability.

Also note that $p(\tilde{y_{i}}|x_{j})$ is given by the model
$f(\tilde{y_{i}}|x_{j};w)$.

where the prediction $\tilde{y_{i}}$ satisfies:

$p(\tilde{y_{i}}=1|x_{i})=f(x_{i},w)=\sigma(w^{t}x_{i}).$ (21)

So $\mathrm{I}(Y;\tilde{Y})$ is now of the form:

$\begin{array}[]{lcl}\mathrm{I}(Y;\tilde{Y})&\geq&A+\sum_{i=1}^{n}\log(\sum_{j=1}^{n}p(y_{i}|x_{j})f(\tilde{y_{i}}|x_{j};w))\\\
&\geq&A+\sum_{i=1}^{n}\log(p(y_{i}|x_{i})f(\tilde{y_{i}}|x_{i};w))\\\
&\geq&A+\sum_{i=1}^{n}\log(f(\tilde{y_{i}}|x_{i};w))+\sum_{i=1}^{n}\log(p(y_{i}|x_{i}))\\\
&\geq&A+\sum_{i=1}^{n}\log(|\sigma(w^{t}x_{i})-\frac{1}{2}|+\frac{1}{2})+\sum_{i=1}^{n}\log(p(y_{i}|x_{i}))\end{array}$
(22)

with high probability for some constant $A$.

Finnally we put (19)&(22) together:

$\mathrm{I}(X;\tilde{Y})-\alpha\mathrm{I}(Y;\tilde{Y})\leq
A^{\prime}+B||w||^{2}-\alpha\sum_{i}\log(|\sigma(w^{t}x_{i})-\frac{1}{2}|+\frac{1}{2}).$
(23)

This is a Lagrangian form of an optimal margin classifier. ∎

###  2.3 Generalization

Consider the target random variable $X$ with unknown distribution. We have a
collection of samples of it, denoted as $\mathcal{D}=\\{x_{i}\\}_{i=1}^{n}$.
Also denote the hypothesis class as $\mathcal{H}$.

The loss function is defined as:

$l:X\times\mathcal{H}\mapsto\mathbb{R_{+}}$ (24)

And the risk:

$\mathcal{R}=\mathrm{E}_{X}[l(x,f)].$ (25)

The optimal function is defined as:

$f^{*}\in arg\,min_{f\in\mathcal{H}}\mathcal{R}(f).$ (26)

Empirical risk minimization(ERM) is given as:

$\hat{f}\in arg\,min_{f\in\mathcal{H}}\hat{\mathcal{R}}(f),$ (27)

where $\hat{\mathcal{R}}(f)$ is given as:

$\hat{\mathcal{R}}(f)=\frac{1}{n}\sum_{i=1}^{n}l(x_{i},f).$ (28)

Consider the following decomposition:

$\begin{array}[]{lcl}\mathcal{R}(\hat{f})&=&\mathcal{R}(\hat{f})-\hat{\mathcal{R}}(\hat{f})+\hat{\mathcal{R}}(\hat{f})-\hat{\mathcal{R}}(f^{*})+\hat{\mathcal{R}}(f^{*})-\mathcal{R}(f^{*})+\mathcal{R}(f^{*})\\\
&\leq&\sup_{f\in\mathcal{H}}|\mathcal{R}(f)-\hat{\mathcal{R}}(f)|+0+|\hat{\mathcal{R}}(f^{*})-\mathcal{R}(f^{*})|+\mathcal{R}(f^{*}).\end{array}$
(29)

Here in (29), the second $\hat{\mathcal{R}}(\hat{f})-\hat{\mathcal{R}}(f^{*})$
is bounded by zero by definition;
$\hat{\mathcal{R}}(f^{*})-\mathcal{R}(f^{*})$ is small, guaranteed by the law
of large number under the assumption that the number of samples $n$ is
sufficiently large. $\mathcal{R}(f^{*})$ is a constant depending on the
hypothesis class $\mathcal{H}$.

The bound $\sup_{f\in\mathcal{H}}|\mathcal{R}(f)-\hat{\mathcal{R}}(f)|$ for
$\mathcal{R}(\hat{f})-\hat{\mathcal{R}}(\hat{f})$ is typically controlled by
the VC theory in the literature, see Vapnik (1995). But as pointed out in
Zhang et al. (2017a), if the number of parameters is much larger than the
number of samples, some form of regularization is needed to ensure small
generalization error. Neyshabur et al. (2017b) mentioned that a sharper bound
can be obtained by making it dependent on the choice of $\hat{f}$.

We would like to provide more insights to generalization, by formally
establishing relationship between generalization in deep learning and margin.
In our model, the SVM in the last layer generalizes better if the margin is
larger. In Neyshabur et al. (2017a), they carefully analysized the notion of
normed based control on margin with relation to generalization. In Bartlett et
al. (2017), they also proved a bound on generalization with margin by using
Rademacher complexity.

##  3 Experiments

In this section we interpret existing experimental reults using our theory. We
also did experiment verifying features of our own interest on Res-Net.

###  3.1 Deep Residual Network

Here we use full reference to experimental results from He et al. (2016).

Table 1: Classification error (%) on the CIFAR-10 test set using different activation functions. case | Fig. | ResNet-110 | ResNet-164
---|---|---|---
original Residual Unit | Fig. 3(a) | 6.61 | 5.93
BN after addition | Fig. 3(b) | 8.17 | 6.50
ReLU before addition | Fig. 3(c) | 7.84 | 6.14
ReLU-only pre-activation | Fig. 3(d) | 6.71 | 5.91
full pre-activation | Fig. 3(e) | 6.37 | 5.46
Figure 3: Various usages of activation in Table 1. All these units consist of
the same components — only the orders are different.

Here they compared different structures for building blocks and report the
performance in Table 1. We give an interpretation to their result according to
our theory: (a)&(b) both have ReLU after adding the identity mapping, which
makes the whole mapping not invertible; (c) makes $\mathcal{L}$ defined in (1)
an nonnegative operator, which may potentially enlarge this operator norm out
of our theoretical guarantee (Appendix E); (d) performs ReLU directly to
input, which loses information, applying Batch Normalization after convolution
also is meaningless.

###  3.2 Flat Basins

Figure 4: Large batch training immediately followed by small batch training on
the full dataset of CIFAR10 with a raw version of AlexNet.

Here we use full reference to experimental results from Sagun et al. (2017).

On generalization property of GD, Poggio et al. (2017) proved in appendix that
GD converges to optimal solution to underdetermined least square problem,
under proper initialization; Soudry et al. (2018) proved that GD converges to
the optimal solution of a hard margin SVM slowly.

Their work motivated us to see the corresponding result in deep learning. The
difference is, in our theory, the seperable data is not deterministic as it’s
controlled by the feature learning map $F$ in Figure 1. The network is looking
for a $F$ to create a larger margin between data of different category and a
"weighted" linear seperator $f$ to achieve that maximum margin.

Back to their experiment, they trained a neural network with batch gradient
descent(GD) for the first 2.5k steps and switch to stochastic gradient
descent(SGD) for the rest 2.5k steps. Notice there’s a significant jump at
step 2.5k when the optimization algorithm is changed.

They argue that despite the jump, there exists a linear interpolation between
LHS and RHS so GD and SGD lead to essentially the same "basin". As pointed out
by Dauphin et al. (2014), in a very high dimensional problem, it’s very hard
to encounter a strict local minima: almost all critical points are saddle
points as there could always exist some direction that is not "going up" in
the landscape. So we do suspect that almost all "basins" are connected
together in some sense. In the work by Dinh et al. (2017), they argued that a
universal definition of flatness of the error surface is still unclear. In
particular, they proved that the geometry of a local minimum can be changed
arbitrarily by reparametrization, without changing what function it
represents.

Instead concerning about the notion of flatness, we can talk about margin.
According to our theory, GD only seperates the feature data, but does not
maximize the margin. At step 2.5k, there are some feature point sitting right
at the boundary of the linear seperator and SGD will break this balance, which
leads to that sudden jump in the training error. In the end SGD generalizes
better because the linear seperator in the last layer seperates the feature
data by a larger margin. The notion of margin needs to be defined carefully as
it scales with the norm of the weights and data.

###  3.3 Norm of $\mathcal{L}$

Figure 5: Values of $\frac{|\mathcal{L}(x)|}{|x|}$ for each building blocks
over the training steps.

We used tensorflow code uploaded on Github by wenxinxu, ran a 32-layer
residual network on CIFAR-10 for 80k steps and computed the
$\frac{|\mathcal{L}(x)|}{|x|}$ for each building blocks at each step. Here
$|\cdot|$ is defined to be the square-root of the sum of squares of all
entries in the tensor. We exported the output for all 15 building blocks over
the training, from tensorboard. We can conclude that operator norm for every
building block is smaller than 1, which meets our hypothesis.

###  3.4 Advantage of ReLU over Sigmoid/Tanh

Figure 6: Stochastic training and the information plane. (A) tanh network
trained with SGD. (B) tanh network trained with BGD. (C) ReLU network trained
with SGD. (D) ReLU network trained with BGD. Both random and non-random
training procedures show similar information plane dynamics.

Here we use full reference to experimental results from Saxe et al. (2018).

Although Sigmoid and Tanh functions are mathematically invertible, they push
large amount of information to the boundary of the range, which in practice
will be classified as a single bin, making them highly noninvertible. On the
other hand, ReLU keeps at least half of the information from input.

Their experimental result matches our theory: Tanh function compresses
information and ReLU keeps fair amount of information.

We would like to emphasis again that a network only needs one compressive
activation function, which is in the last layer playing the role similar to
SVM.

###  3.5 iRevNet

Figure 7: Accuracy of a linear SVM and nearest neighbor against the number of
principal components retaine.

Here we use full reference to experimental results from Jacobsen et al.
(2018).

They projected the feature data of last layer of the network to a low
dimensional space by PCA and did SVM on them. The good performance of SVM
shows the intrinsic dimensionality of the feature data in the last layer is
low, which supports our seperability assumptions.

##  4 Conclusion

In this paper, we analyzed the dynamics of the information plane proposed by
Shwartz-Ziv and Tishby (2017). More importantly, we gave a hypothesis for the
learning structure of deep neural network, and answered the questions arised
from Saxe et al. (2018).

## References

  * Achille and Soatto [2016] Alessandro Achille and Stefano Soatto.  Information dropout: learning optimal representations through noise.  _CoRR_ , abs/1611.01353, 2016.  URL http://dblp.uni-trier.de/db/journals/corr/corr1611.html#AchilleS16.
  * Alemi et al. [2016] Alexander A. Alemi, Ian Fischer, Joshua V. Dillon, and Kevin Murphy.  Deep variational information bottleneck.  _CoRR_ , abs/1612.00410, 2016.  URL http://arxiv.org/abs/1612.00410.
  * Bartlett et al. [2017] Peter L. Bartlett, Dylan J. Foster, and Matus Telgarsky.  Spectrally-normalized margin bounds for neural networks.  _CoRR_ , abs/1706.08498, 2017.  URL http://arxiv.org/abs/1706.08498.
  * Bottou [1998] Léon Bottou.  On-line learning in neural networks.  chapter On-line Learning and Stochastic Approximations, pages 9–42. Cambridge University Press, New York, NY, USA, 1998.  ISBN 0-521-65263-4.  URL http://dl.acm.org/citation.cfm?id=304710.304720.
  * Chaudhari et al. [2016] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Levent Sagun, and Riccardo Zecchina.  Entropy-sgd: Biasing gradient descent into wide valleys.  _CoRR_ , abs/1611.01838, 2016.  URL http://arxiv.org/abs/1611.01838.
  * Dauphin et al. [2014] Yann Dauphin, Razvan Pascanu, Çaglar Gülçehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio.  Identifying and attacking the saddle point problem in high-dimensional non-convex optimization.  _CoRR_ , abs/1406.2572, 2014.  URL http://arxiv.org/abs/1406.2572.
  * Dinh et al. [2017] Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio.  Sharp minima can generalize for deep nets.  _CoRR_ , abs/1703.04933, 2017.  URL http://arxiv.org/abs/1703.04933.
  * He et al. [2015] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  _CoRR_ , abs/1512.03385, 2015.  URL http://arxiv.org/abs/1512.03385.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Identity mappings in deep residual networks.  _CoRR_ , abs/1603.05027, 2016.  URL http://arxiv.org/abs/1603.05027.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  _CoRR_ , abs/1502.03167, 2015.  URL http://arxiv.org/abs/1502.03167.
  * Jacobsen et al. [2018] Jörn-Henrik Jacobsen, Arnold Smeulders, and Edouard Oyallon.  i-RevNet: Deep Invertible Networks.  In _ICLR 2018 - International Conference on Learning Representations_ , Vancouver, Canada, April 2018.  URL https://hal.archives-ouvertes.fr/hal-01712808.
  * Kraskov et al. [2004] Alexander Kraskov, Harald Stögbauer, and Peter Grassberger.  Estimating mutual information.  _Phys. Rev. E_ , 69:066138, Jun 2004.  doi: 10.1103/PhysRevE.69.066138.  URL https://link.aps.org/doi/10.1103/PhysRevE.69.066138.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems 25_ , pages 1097–1105. Curran Associates, Inc., 2012.  URL http://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf.
  * Lax [2002] P.D. Lax.  _Functional analysis_.  Pure and applied mathematics. Wiley, 2002.  ISBN 9780471556046.  URL https://books.google.com/books?id=-jbvAAAAMAAJ.
  * Nair and Hinton [2010] Vinod Nair and Geoffrey E. Hinton.  Rectified linear units improve restricted boltzmann machines.  In _Proceedings of the 27th International Conference on International Conference on Machine Learning_ , ICML’10, pages 807–814, USA, 2010\. Omnipress.  ISBN 978-1-60558-907-7.  URL http://dl.acm.org/citation.cfm?id=3104322.3104425.
  * Neyshabur et al. [2017a] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro.  Exploring generalization in deep learning.  _CoRR_ , abs/1706.08947, 2017a.  URL http://arxiv.org/abs/1706.08947.
  * Neyshabur et al. [2017b] Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro.  Exploring generalization in deep learning.  In _NIPS_ , 2017b.
  * Poggio et al. [2017] Tomaso Poggio, Qianli Liao, Brando Miranda, Lorenzo Rosasco, Xavier Boix, Jack Hidary, and Hrushikesh Mhaskar.  Theory of deep learning iii: explaining the non-overfitting puzzle.  12/2017 2017.
  * Raginsky et al. [2017] Maxim Raginsky, Alexander Rakhlin, and Matus Telgarsky.  Non-convex learning via stochastic gradient langevin dynamics: a nonasymptotic analysis.  In Satyen Kale and Ohad Shamir, editors, _Proceedings of the 2017 Conference on Learning Theory_ , volume 65 of _Proceedings of Machine Learning Research_ , pages 1674–1703, Amsterdam, Netherlands, 07–10 Jul 2017. PMLR.  URL http://proceedings.mlr.press/v65/raginsky17a.html.
  * Roberts and Tweedie [1996] Gareth O. Roberts and Richard L. Tweedie.  Exponential convergence of langevin distributions and their discrete approximations.  _Bernoulli_ , 2(4):341–363, 12 1996.  URL https://projecteuclid.org:443/euclid.bj/1178291835.
  * Sagun et al. [2017] Levent Sagun, Utku Evci, V. Ugur Güney, Yann Dauphin, and Léon Bottou.  Empirical analysis of the hessian of over-parametrized neural networks.  _CoRR_ , abs/1706.04454, 2017.  URL http://arxiv.org/abs/1706.04454.
  * Saxe et al. [2018] Andrew Michael Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan Daniel Tracey, and David Daniel Cox.  On the information bottleneck theory of deep learning.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=ry_WPG-A-.
  * Shamir et al. [2010] Ohad Shamir, Sivan Sabato, and Naftali Tishby.  Learning and generalization with the information bottleneck.  _Theoretical Computer Science_ , 411(29):2696 – 2711, 2010.  ISSN 0304-3975.  doi: https://doi.org/10.1016/j.tcs.2010.04.006.  URL http://www.sciencedirect.com/science/article/pii/S030439751000201X.  Algorithmic Learning Theory (ALT 2008).
  * Shwartz-Ziv and Tishby [2017] Ravid Shwartz-Ziv and Naftali Tishby.  Opening the black box of deep neural networks via information.  _arXiv preprint arXiv:1703.00810_ , 2017.
  * Soudry et al. [2018] Daniel Soudry, Elad Hoffer, and Nathan Srebro.  The implicit bias of gradient descent on separable data.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=r1q7n9gAb.
  * Srivastava et al. [2014] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: A simple way to prevent neural networks from overfitting.  _Journal of Machine Learning Research_ , 15:1929–1958, 2014\.  URL http://jmlr.org/papers/v15/srivastava14a.html.
  * Troost et al. [2018] Marjolein Troost, Katja Seeliger, and Marcel van Gerven.  Generalization of an upper bound on the number of nodes needed to achieve linear separability.  02 2018.
  * Tzen et al. [2018] Belinda Tzen, Tengyuan Liang, and Maxim Raginsky.  Local optimality and generalization guarantees for the langevin algorithm via empirical metastability.  _CoRR_ , abs/1802.06439, 2018.  URL http://arxiv.org/abs/1802.06439.
  * Vapnik [1995] Vladimir N. Vapnik.  _The Nature of Statistical Learning Theory_.  Springer-Verlag New York, Inc., New York, NY, USA, 1995.  ISBN 0-387-94559-8.
  * Vershynin [2018] Roman Vershynin.  _High-Dimensional Probability: An Introduction with Applications in Data Science_.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
  * Zhang et al. [2017a] Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals.  Understanding deep learning requires rethinking generalization.  2017a.  URL https://arxiv.org/abs/1611.03530.
  * Zhang et al. [2017b] Yuchen Zhang, Percy Liang, and Moses Charikar.  A hitting time analysis of stochastic gradient langevin dynamics.  In _COLT_ , 2017b.
  * Zheng et al. [2018] Guanhua Zheng, Jitao Sang, and Changsheng Xu.  Understanding deep learning generalization by maximum entropy, 2018.  URL https://openreview.net/forum?id=r1kj4ACp-.

##  Appendix A Bound for $\mathrm{I}(X;\tilde{Y})$

The intuition is Jensen’s inequality is loose if the term in $\log$ deviates
from constant by a lot.

Consider the second quantity $\mathrm{I}(X;\tilde{Y})$ given by:

$\mathrm{I}(X;\tilde{Y})=\int_{\tilde{Y}}\int_{X}p(x,\tilde{y})\log(\frac{p(x,\tilde{y})}{p(x)p(\tilde{y})})dxd\tilde{y}$
(30)

Our goal is to show that (1) is decreasing at a rate upper bounded by
polynomial.

Denote $f(x,\tilde{y})=\frac{p(x)p(\tilde{y})}{p(x,\tilde{y})}$, consider the
2nd order Taylor form around 1:

$\log(f(x,\tilde{y}))=\log(1)+(f(x,\tilde{y})-1)-\frac{1}{2c^{2}}(f(x,\tilde{y})-1)^{2},$
(31)

where $c$ is between $f(x,\tilde{y})$ and 1.

Observing $\mathrm{E}(f(x,\tilde{y}))=1$, then substitute (2) into (1) get:

$\mathrm{I}(X;\tilde{Y})=\int_{\tilde{Y}}\int_{X}p(x,\tilde{y})\frac{1}{2c^{2}}(f(x,\tilde{y})-1)^{2}dxd\tilde{y}.$
(32)

If $c\geq 1$, then
$\frac{1}{2c^{2}}(f(x,\tilde{y})-1)^{2}\leq\frac{1}{2}(f(x,\tilde{y})-1)^{2}$;
if $c\leq 1$, then
$\frac{1}{2c^{2}}(f(x,\tilde{y})-1)^{2}\leq\frac{1}{2f(x,\tilde{y})^{2}}(f(x,\tilde{y})-1)^{2}=\frac{1}{2}(1-\frac{1}{f(x,\tilde{y})})^{2}$.

It follows we can upper bound (3) by:

$\begin{array}[]{lcl}\mathrm{I}(X;\tilde{Y})&\leq&\frac{1}{2}\int_{\tilde{Y}}\int_{X}p(x,\tilde{y})[(f(x,\tilde{y})-1)^{2}+(1-\frac{1}{f(x,\tilde{y})})^{2}]dxd\tilde{y}\\\
&=&\mathrm{Var}(f(X,\tilde{Y}))+\mathrm{Var}(\frac{1}{f(X,\tilde{Y})})\\\
&=&\mathrm{Var}(\frac{p(\tilde{y})}{p(\tilde{y}|x)})+\mathrm{Var}(\frac{p(\tilde{y}|x)}{p(\tilde{y})})\\\
&\leq&2(\mathrm{Var}(p(\tilde{y}))+\mathrm{Var}(p(\tilde{y}|x)))\end{array}$
(33)

##  Appendix B Approximation for $\mathrm{I}(Y;\tilde{Y})$

Consider

$\mathrm{I}(Y;\tilde{Y})=\int_{\tilde{Y}}\int_{Y}p(y,\tilde{y})\log(\frac{p(y,\tilde{y})}{p(y)p(\tilde{y})})dyd\tilde{y}.$
(34)

which can be regarded as $\mathbb{E}Z$ for some random variable $Z$ with
probability density:

$p_{Z}(\log(\frac{p_{\tilde{Y},Y}(y,\tilde{y})}{p_{\tilde{Y}}(\tilde{y})p_{Y}(y)}))=p_{\tilde{Y},Y}(y,\tilde{y}).$
(35)

By Appendix F, $Z$ is subexponential, so by Bernstein’s inequality(see
Vershynin [2018]) we have, for sample size large enough, a high probability
bound guarantees the empirical approximation of $\mathrm{I}(Y;\tilde{Y})$:

$\sum_{i=1}^{n}\log(\frac{p(y_{i},\tilde{y_{i}})}{p(y_{i})p(\tilde{y_{i}})}).$
(36)

which has another empirical version:

$\sum_{i=1}^{n}\log(\frac{\sum_{j=1}^{n}p(y_{i},\tilde{y_{i}}|x_{j})}{p(y_{i})p(\tilde{y_{i}})})=\sum_{i=1}^{n}\log(\frac{\sum_{j=1}^{n}p(y_{i}|\tilde{y_{i}},x_{j})p(\tilde{y_{i}}|x_{j})}{p(y_{i})p(\tilde{y_{i}})})=\sum_{i=1}^{n}\log(\frac{\sum_{j=1}^{n}p(y_{i}|x_{j})p(\tilde{y_{i}}|x_{j})}{p(y_{i})p(\tilde{y_{i}})}).$
(37)

Here we make an assumption that for the models we trained over time, it’s
output $\tilde{Y}$ is approximately uniform distributed over the finite
labels. So we treat $p(y_{i})p(\tilde{y_{i}})$ as constant for all $i$. Also
note that $p(\tilde{y_{i}}|x_{j})$ is given by the model
$f(\tilde{y_{i}}|x_{j};w_{t})$.

The prediction $\tilde{y}_{i}$ satisfies:

$\tilde{y}_{i}=arg\,max_{y}f(y|x_{i},w_{t}),$ (38)

So $\mathrm{I}(Y;\tilde{Y})$ is now of the form:

$\begin{array}[]{lcl}\mathrm{I}(Y;\tilde{Y})&\geq&A+\sum_{i=1}^{n}\log(\sum_{j=1}^{n}p(y_{i}|x_{j})f(\tilde{y_{i}}|x_{j};w_{t}))\\\
&\geq&A+\sum_{i=1}^{n}\log(p(y_{i}|x_{i})f(\tilde{y_{i}}|x_{i};w_{t}))\\\
&\geq&A+\log(\prod_{i=1}^{n}f(\tilde{y_{i}}|x_{i};w_{t}))+\sum_{i=1}^{n}\log(p(y_{i}|x_{i}))\\\
&\geq&A+\log(\prod_{i=1}^{n}f(y_{i}|x_{i};w_{t}))+\sum_{i=1}^{n}\log(p(y_{i}|x_{i}))\end{array}$
(39)

with high probability for some constant $A$.

##  Appendix C Continuous entropy

The natural definition of a mutual information of a discrete random variable
$X$ to $g(x)$ where $g$ is a deterministic function, if we try to define it at
all, is as follows:

$\mathrm{I}(X;g(X))=-\sum_{x}p(x)\log p(x),$ (40)

where for simplicity we assume the range of $X$ is in $\mathbb{R}$.

If instead we consider $X$ has a continuous range, for example $\mathbb{R}$,
we can take a uniform mesh over $\mathbb{R}$ with interval $\Delta$ and do the
approximation:

$p(X\in[x,x+\Delta])=\int_{x}^{x+\Delta}f(a)da\approx f(x)\Delta.$ (41)

And therefore:

$\mathrm{I}(X;g(X))\approx-\sum_{i=-\infty}^{i=\infty}f(x_{i})\Delta\log(f(x_{i})\Delta),$
(42)

where $\\{[x_{i},x_{i}+\Delta]\\}$ is the mesh on $\mathbb{R}$. We expect this
estimation to be precise if we take $\Delta\rightarrow\infty$.

But this limit is different from the intuitive definition of differential
entropy $\mathrm{I}(X)$, provide it exists:

$\mathrm{I}(X)=\int_{\mathbb{R}}f(x)\log(f(x))=-\lim_{\Delta\rightarrow
0}\sum_{i=-\infty}^{i=\infty}f(x_{i})\Delta\log(f(x_{i})).$ (43)

Intuitively the $\log$ term in (3) will blow down as $\Delta\rightarrow 0$.

In practice people estimate the mutual information by (3) but it doesn’t yield
a meaningful quantity. In particular, we don’t know whether (3) converges or
not if we take $\Delta\rightarrow 0$.

Here key point here is that for general random variables $X,Y$, if $p(x,y)$ is
not degenerate over some open interval $U\subset\mathbb{R}$, then by inverse
function theorem, there exists some invertible relationship between $X,Y$ in
$U$ and we need infinite amount of information to describe what is happening
in $U$.

But if we consider instead the mutual information between a discrete random
variable $Y$ with finite range and a continuous random variable $X$ with
continuous density, then the estimation would take the form:

$\mathrm{I}(X;Y)\approx\sum_{i=1}^{n}\sum_{j=-\infty}^{\infty}p(x_{j},y_{i})\Delta\log(\frac{p(x_{j}|y_{i})\Delta}{\sum_{l}p(x_{j}|y_{l})\Delta}),$
(44)

which has a limit:

$\mathrm{I}(X;Y)=\sum_{i=1}^{n}\int_{\mathbb{R}}f(x,y_{i})\log(\frac{f(x|y_{i})}{\sum_{l}f(x|y_{l})})dx.$
(45)

So if the analytical form (6) of $\mathrm{I}(X;Y)$ is finite, we know our
practical approximation is meaningful.

In practice, the true quantity $\mathrm{I}(X;Y)$ is usually finite. For
example, in MNIST, both image $X$ and its label $Y$ are essentially discrete
so their mutual information can be defined in a strict discrete sense.

As a conclusion, it’s always sensible to define the mutual information between
discrete finite random variable and continuous random variable in an exact
integral form.

##  Appendix D Heat Equation

Given a Cauchy problem for heat equation:

$\begin{array}[]{lcl}u_{t}&=ku_{xx}\\\ u(x,0)&=\phi(x)\end{array}$ (46)

The solution is known as:

$u(x,t)=\frac{1}{\sqrt{4\pi
kt}}\int^{\infty}_{-\infty}e^{-\frac{(x-y)^{2}}{4kt}}\phi(y)dy=K(x,t)*\phi(x),$
(47)

where $K(x,t)=\frac{1}{\sqrt{4\pi kt}}e^{-\frac{x^{2}}{4kt}}.$

Without losing generality assuming $k=1$, consider:

$||K(x,t)||_{2}^{2}=Ct^{-1}\int_{-\infty}^{\infty}e^{-\frac{x^{2}}{2t}}dx.$
(48)

Substitude $x^{\prime}=t^{-1/2}x$ gives:

$||K(x,t)||_{2}^{2}=Ct^{-1/2}\int_{-\infty}^{\infty}e^{-\frac{x^{\prime
2}}{2}}dx^{\prime}=C^{\prime}t^{-1/2}.$ (49)

##  Appendix E Convergence in Banach Space

######  Claim E.1.

Consider Holder Space $C^{0,1}(\overline{U})$, where $\overline{U}$ is the
closure of some bounded open set $U$, with equiped Holder norm
$|\mathcal{L}|=\alpha\sup_{x\in U}|\mathcal{L}(x)|+\sup_{x,y\in U,x\neq
y}\\{\frac{|\mathcal{L}(x)-\mathcal{L}(y)|}{|x-y|}\\}$, here $\alpha$ is some
positive scalar. If $\mathcal{L}\in C^{0,1}(\overline{U})$ and
$|\mathcal{L}|<1$, then there exists $\mathcal{B}$ such that
$\mathcal{B}(I+\mathcal{L})=(I+\mathcal{L})\mathcal{B}=I$.

###### Proof.

It’s well known that $C^{0,1}(\overline{U})$ is a Banach space (Lax [2002]).
Note that $\alpha$ can be scale down to an arbitrary small constant in
practice, which has no influence to our proof.

Define

$\mathcal{B}=\sum_{n=0}^{\infty}(-\mathcal{L})^{n}.$ (50)

Since $|\mathcal{L}|<1$, the sequence in (51) is a Cauchy sequence. So it
coverges in Banach space. Convergence sequence can be multiplied termwise, it
follows that

$\mathcal{B}\mathcal{L}=\mathcal{L}\sum_{n=0}^{\infty}(-\mathcal{L})^{n}=-\sum_{n=1}^{\infty}(-\mathcal{L})^{n}=-(\mathcal{B}-I).$
(51)

So $\mathcal{B}(I+\mathcal{L})=I$. The other equality can be shown similarly.
∎

##  Appendix F Subexponential

######  Claim F.1.

Let $A,B$ be two discrete real-valued random variable with probability density
$p_{A},p_{B}$. Then the real valued random variable $Z$ with probability
density $p_{Z}(\log(\frac{p_{AB}(a,b)}{p_{A}(a)p_{B}(b)}))=p_{AB}(a,b)$ is
subexponential.

###### Proof.

Let $s=\log(\frac{p_{AB}(a,b)}{p_{A}(a)p_{B}(b)})$, then

$e^{s}=\frac{p_{AB}(a,b)}{p_{A}(a)p_{B}(b)}\leq\frac{p_{AB}(a,b)}{p_{AB}(a,b)^{2}}=\frac{1}{p_{AB}(a,b)},$
(52)

and

$e^{s}=\frac{p_{AB}(a,b)}{p_{A}(a)p_{B}(b)}\geq p_{AB}(a,b).$ (53)

It follows that:

$p_{AB}(a,b)\leq\min\\{e^{-s},e^{s}\\},$ (54)

which implies:

$p_{Z}(s)=p_{AB}(a,b)\leq\min\\{e^{-s},e^{s}\\},$ (55)

Then the tail bound satisfies:

$\begin{array}[]{lcl}\mathbb{P}(|Z|\geq
t)&=&\int_{t}^{\infty}p_{Z}(s)ds+\int_{-\infty}^{-t}p_{Z}(s)ds\\\
&\leq&\int_{t}^{\infty}e^{-s}ds+\int_{-\infty}^{-t}e^{s}ds\\\
&=&2e^{-t}.\end{array}$ (56)

∎


# An Assessment Model for Cybercrime Investigation Capacity

Joshua I. James1, Yunsik Jake Jang2
<EMAIL_ADDRESS><EMAIL_ADDRESS>

1Digital Forensic Investigation Research Group
University College Dublin
Belfield, Dublin 4, IE

2International Cybercrime Research Center
Korean National Police University
Yongin-si, South Korea

###### Abstract

Digital technologies are constantly changing, and with it criminals are
finding new ways to abuse these technologies. Cybercrime investigators, then,
must also keep their skills and knowledge up to date. This work proposes a
holistic training development model – specifically focused on cybercrime
investigation – that is based on improving investigator capability while also
considering the capacity of the investigator or unit. Along with a training
development model, a cybercrime investigation capacity assessment framework is
given for attempting to measure capacity throughout the education process.
First, a training development model is proposed that focuses on the expansion
of investigation capability as well as capacity of investigators and units.
Next, a capacity assessment model is given to evaluate the effectiveness of
the training program. A description of how the proposed model is being applied
to the development of training programs for cybercrime investigators in
developing countries will then be given, as well as already observed
challenges. Finally, concluding remarks as well as proposed future work is
discussed.

Keywords: Cybercrime Investigation Capacity Assessment, Cybercrime
investigation capability, Training Development, Education, Law Enforcement

##  1 Introduction

Continuous development of information communication technology and large scale
proliferation is leading to an increase in victims of digital crime, as well
as tools and evidence in criminal investigations [1]. Many crimes, even
traditionally non-digital crimes such as murder, now normally have some sort
of digital component [2,3]. Even so much so that some law enforcement agencies
claim that there are rarely cases that do not involve some sort of digital
device [4]. Because of this, the ability of law enforcement to handle
electronic evidence is vital during entire investigative procedure. A survey
recently conducted by the United Nations (U.N.) reported that more than 90% of
respondent countries have at least some capability to conduct digital
investigations [5].

However, the U.N. report also showed a global need for expansion of digital
investigation capability. Key areas of concern were with the investigation
capabilities in less developed countries, as well as the capability of
organizations to conduct international investigations. This mirrors Huber [6],
who claimed that “digital forensics is very much an interstate and
international issue”. General cybercrime investigation, computer forensics and
digital evidence handling were the most commonly cited areas that require more
development and assistance. Currently, many public and private organizations
around the world are investing in the infrastructure of developing countries.
However, international assistance in regards to digital crime investigation
has been slower that other sectors, such as information technology [7].

Many countries, developing and developed alike, are beginning to invest in the
capability of their investigators to investigate digital crimes. This has
caused a rapid growth in the number of digital crime investigation programs
offered at training institutions and universities around the world. These
programs are targeted at improving an investigator’s capability in dealing
with certain types of digital crime; however, improvement of capability does
not necessarily improve investigation capacity.

Hekim, Gul et al. [8] previously examined investigation capacity in law
enforcement to assess whether information technology improves investigation
capacity. In their work, they define investigation capacity as the case
clearance rate. James and Jang [9], however, claim that the case clearance
rate alone does not adequately represent an investigator or unit’s
investigation capacity. They instead define investigation capacity as case
clearance rates as related to time, where:

$capacity(T)=((\frac{cases\ closed}{average\ investigators})+((\frac{cases\
closed}{average\ investigators})\cdot down\ time))\cdot(average\
investigators)$

where:

  * •

$T$ is the time span for which capacity should be measured

Capability and capacity are related terms that have to do with quality. In
investigations a highly capable investigator may be able to conduct quality
investigations unless there are more investigation requests than he or she has
the capacity to deal with at a time, at which point quality may be reduced.
Many investigators have to cope with a lack of resources [10], meaning that
they are normally working at – if not over – capacity. Because of this, when
attempting to educate investigators both expansion of capability and capacity
should be considered and measured.

###  1.1 Contribution and Structure

This work proposes a holistic training development model – specifically
focused on cybercrime investigation – that is based on improving investigator
capability while also considering the capacity of the investigator or unit.
Along with a training development model, a cybercrime investigation capacity
assessment framework is given for attempting to measure capacity throughout
the education process.

First, a training development model is proposed that focuses on the expansion
of investigation capability as well as capacity of investigators and units.
Next, a capacity assessment model is given to evaluate the effectiveness of
the training program. A description of how the proposed model is being applied
to the development of training programs for cybercrime investigators in
developing countries will then be given, as well as already observed
challenges. Finally, concluding remarks as well as proposed future work will
be discussed.

##  2 Building Investigation Capability

The growing number and complexity of digital devices related to criminal acts
means that digital investigators must attempt to increase their knowledge of a
broad range of technologies, as well as increase the pace at which such
devices can be analyzed [11]. There are a number of challenges that digital
investigators face, and education and training is a primary challenge for many
investigation units today [7,10]. Not only is receiving training sometimes a
challenge, but the way training is organized and delivered can also cause
issues. Further, in many training programs the content may be such that
investigators don’t – or can’t – implement trained material in practical
investigations. Such a situation could be the product of a training program
that did not meet the needs of the trainees; however, without post-training
assessment there is no way to know whether skills and knowledge are being
transferred to practice. The Korean National Police, for example, are active
contributors for building investigation capability and capacity with
developing countries; however, few development programs have adequately
evaluated the effectiveness of such initiatives.

With many organizations, evaluation may be at the end of a training session
and perhaps award the trainee a simple qualification upon completion. However,
short term trainings do not necessarily lead to long-term knowledge gain, even
if a trainee does well on an examination immediately after the course [7].
Also, because no further evaluation is normally done, training organizations
have no way of assessing if knowledge or skills have been practically
transferred.

For the issues of generally targeting the training to the needs of the
trainees, and ensuring that knowledge and skills are being practically
transferred for the improvement of capability and capacity, this work proposes
a holistic training development methodology to increase cybercrime
investigation capability and capacity.

As shown in Figure 1, the method begins with an extensive assessment of the
organization, attempting to determine what their goals, processes and current
knowledge are. During the observation phase, a training group should gain
understanding of the current state of knowledge and skills of the organization
to be trained as well as how the organization can/will implement new
knowledge. In our experience, it is common for the trainers to find that
organizations to be trained are either already knowledgeable about many of the
areas, or that the organization has no skills in the area and may require
remediation. It is relatively uncommon to have a group, even within the same
organization, in which all participants have the same level of knowledge and
skills in a particular area.

Figure 1: Cybercrime investigation capacity expansion framework with a focus
on human resource training

Once a better understanding of how the organization functions has been
established, the needs of the organization should be determined. This stage
should be approached with some skepticism as many organizations tend to have
difficulty differentiating between wants and needs, and in some cases are
simply ignorant of their actual needs. Based on knowledge gained in the
observation phase, paired with lists of the organization’s needs, a training
developer should attempt to assess identified needs in the context of the
organization’s goals and current practices. Many organizations, for example,
often identify ‘more equipment’ as a need to expand capacity. Capacity,
however, can be expanded in many ways, such is more efficient processes. The
training developer, then, should attempt to determine major problem areas at
the national, organizational, divisional and personal levels, and evaluate
what is needed to make a lasting positive impact on the organization. Again
considering more equipment as a example, additional equipment may make up for
inefficient processes in the short-term, but will exacerbate inefficient
processes as capacity again reaches its peak.

###  2.1 Program Development

Once needs of the organization have been established, program development can
begin. There are many course development strategies, but we tend to prefer the
Successive Approximation Model (SAM). SAM is essentially a breadth first
approach to curricula design, where the design is iterative – from general to
specific – for approximately three iterations [12]. SAM is composed of three
specific phases: preparation, design and development.

  * •

Preparation

    * –

Information gathering

      * *

Background information

      * *

Needs analysis

  * •

Interactive design

    * –

Iterate through the design, prototype and review phases

    * –

“Savvy start”

    * –

Project planning

    * –

Additional design

  * •

Interactive development

    * –

Iterate through development, implementation and evaluation

    * –

Design proof

    * –

Alpha Version

    * –

Beta Version

    * –

Final ‘Gold’ Version

SAM is general and intuitive enough to be easily applied to many different
areas. Iteration in the development and design phases means that the developer
can be more abstract and focus in once they have more information and
feedback, rather than picking a design and sticking strictly with it. Further,
iterations of SAM include an evaluation phase ensuring quality standards are
maintained. In this case, SAM is used for course design for the manager and
train-the-trainer programs.

####  2.1.1 Management Training

As discussed, many training and education initiatives focus on the expansion
of capabilities of investigators. However, to improve capability and capacity,
management must also be involved. In the proposed model, management receives
in-house training designed to suit the organization’s identified needs. Such
training could focus on improving work flows, data management, evidence
intake, etc. as can be seen by a work flow process analysis in [13].

Once initial in-house training has been given, management is expected to form
action plans that begin to apply what they have learned. Created action plans
should be practically implementable in their organization. Implementation of
new knowledge is assessed and supplemented via practical ’management’ on-site
training. On-site training allows the trainer to better understand how – or if
– the trainees are attempting to apply what was learned to improve processes
in the organization. This also allows the trainer to help point out potential
areas of improvement, and answer practical implementation questions with the
organization as an example.

The outputs of management training are crime management, investigation and
prevention strategies that are beginning to be implemented. This includes
management’s, possibly newly created, goals for investigator training and
investigation needs.

####  2.1.2 Train-the-Trainer

Training for investigators is developed in parallel with manager training,
again using SAM. The first content to be created for investigators is the
e-learning component. E-learning allows busy organizations to complete some
training at a time that is convenient for them. It also allows trainers to
assess trainees’ current level of knowledge, and provide remedial education,
if necessary. This will allow all participants to have a similar starting
baseline knowledge, which is missing in many training programs.

Next, in-house training for investigators is developed around the previously
identified needs, using the same themes as the management training. Once,
skills and knowledge for investigators have been developed, and practical
feedback has been given from the management training, then investigators
undergo domestic training that feeds directly into their investigation
process. These processes continue, and are supplemented with on-site training.

###  2.2 Online Consultation

Oftentimes when organizations receive training and education, trainees may
make informal social network connections that may help in the application of
learned skills and knowledge. However, this support may not be responsive,
consistent, or the best suited for helping organizations. For this reason,
online consultation with experts associated with the training organization is
provided in this model. In this case, if trainees have questions, they can
consult with experts in the knowledge domain rather than other practitioners
that may also be learning these processes. With such support, the trainees may
be more confident about attempting to develop and implement better
investigation processes and techniques.

##  3 Cybercrime Investigation Capacity Assessment Framework

The cybercrime investigation capacity assessment framework includes
observation and assessment throughout the training program. Observation of the
organization is conducted before and after each training initiative for the
whole organization.

The observation phase is composed of a survey of the organization to determine
the basic level of skills and knowledge for the organization. This survey,
along with knowledge about organization processes determined during the first
observation phase give the training organization a baseline with witch to
compare skills and knowledge development.

After a training session has been delivered – either in-house or on-site – an
assessment of the trainees is given to attempt to evaluate their short term
understanding of the objectives. From three to six months after training has
been received, the survey will again be administered to assess capability, and
an assessment of changed processes will be conducted to evaluate efficiency
improvements. Finally, the previously described capacity measurement model [9]
will be used to assess improvements in capacity over time.

By using a qualitative survey, an observation of process changes, and a
quantitative approach to capacity assessment, greater understanding of how the
organization’s process has change, and what the effects of this change are in
terms of capacity can be determined.

##  4 Application to Cybercrime Training Development

This process has been developed in response to shortcomings observed in
current cybercrime investigation training initiatives, especially in the area
of assessment. The overall process is currently being applied to three (3)
year cybercrime investigation capacity building programs for 5 Asian
countries. In many of these countries, such a project will be the first
attempt to measure the countries’ cybercrime investigation capacity, and
evaluate an organization’s investigation process in relation with training.
Such an initiative, however, is only a first effort towards measuring the
effects of training on cybercrime investigators. Therefore the model, although
currently general, is expected to be modified with experience. This is
especially true from the cybercrime investigation capacity assessment
framework as better metrics for metrics are identified.

##  5 Conclusions and Future Work

This work proposed a holistic training development model – specifically
focused on cybercrime investigation – that is based on improving investigator
capability while also considering the capacity of the investigator or unit.
Along with a training development model, a cybercrime investigation capacity
assessment framework was given for attempting to assess investigation
capability and capacity throughout the education process.

Such a model is proposed to a attempt to improve pre and post training
assessment, as well as allowing training developers more information about the
organization that will receive the training so such training can be better
targeted, or remediation can take place before training begins if necessary.

As discussed previously, this development and assessment model is currently
being applied to training programs with five Asian countries. Ideally this
model will allow training developers to understand the individual needs of
each country, but will result in a relatively generalized program that meets
the needs of each group. Future work will attempt to assess the weaknesses of
each step of the model, especially with metrics used in the capacity
assessment framework.

## Bibliography

  1. 1.

Casey, E. (2004). Digital evidence and computer crime : forensic science,
computers and the Internet (2nd ed., pp. xviii, 690p.). Amsterdam, London:
Elsevier Academic.

  2. 2.

RTE. (2010). Text message evidence in murder trial. RTE News. Retrieved from
http://www.rte.ie/news/2010/0423/drimnagh.html

  3. 3.

Nguyen, L. (2012). Tori Stafford trial: Cellphone record shows gap during
abduction, murder. Postmedia News. Retrieved from http://www.canada.com
/life/Tori+Stafford+trial+Cellphone+record+shows+during+abduction+
murder/6486178/story.html

  4. 4.

Philipp, J. (2013). Nearly Every NYC Crime Involves Cyber, Says Manhattan DA.
The Epoch Times. Retrieved from http://www.theepochtimes.com
/n2/united-states/nearly-every-nyc-crime-involves-cyber-says-manhattan-
da-355692.html

  5. 5.

(2013) “Comprehensive Study on Cybercrime”. United Nations Office on Drugs and
Crime. http://www.unodc.org/documents/commissions
/CCPCJ_session22/13-80699_Ebook_2013_study_CRP5.pdf

  6. 6.

Huber, E. (2010). Certification, Licensing, and Accreditation in Digital
Forensics. A Fistful of Dongles. Retrieved from http://ericjhuber.blogspot.com
/2010/11/certification-licensing-and.html

  7. 7.

James, J. I., & Gladyshev, P. (2013). Challenges with Automation in Digital
Forensic Investigations, 17. Computers and Society. Retrieved from
http://arxiv.org/abs/1303.4498

  8. 8.

Hekim, H., Gul, S., & Akcam, B. (2013). Police use of information technologies
in criminal investigations. European Scientific Journal, 9(4), 221-240.
Retrieved from http://eujournal.org/index.php/esj/article/view/778

  9. 9.

James, J. I., & Jang, Y. J. (2013). Measuring digital crime investigation
capacity to guide international crime prevention strategies. Unpublished paper
in the 7th International Symposium on Digital Forensics and Information
Security.

  10. 10.

Gogolin, G. (2010). The Digital Crime Tsunami. Digital Investigation, 7(1-2),
3-8. doi:10.1016/j.diin.2010.07.001

  11. 11.

Casey, E., Ferraro, M., & Nguyen, L. (2009). Investigation Delayed Is Justice
Denied: Proposals for Expediting Forensic Examinations of Digital Evidence.
Journal of forensic sciences, 54(6), 1353?1364.
doi:10.1111/j.1556-4029.2009.01150.x

  12. 12.

Allen, M. W. (2003). Michael Allen’s guide to e-learning: Building
interactive, fun, and effective learning programs for any company. Wiley.

  13. 13.

James, J. I., & Gladyshev, P. (2013). A survey of digital forensic
investigator decision processes and measurement of decisions based on enhanced
preview. Digital Investigation, 1-10. doi:10.1016/j.diin.2013.04.005