```python
from itertools import product
import numpy as np
```

# Introducing DenseNet
  
  
  
Ming Li  
  
  
Data Scientist  
Open Source Contributor (pandas, scikit-learn, etc).

<figure>
<center>
<figcaption><font size="-1">A single Dense Block of 5 layers. Huang et al 2016.</font></figcaption></center></figure>

* Novel connectivity pattern to increase network connections to quadratic in relation to layers: $\frac{𝐿(𝐿+1)}{2}$
* Feature reuse.
* Parameters and computation efficient.
* Outperform current state-of-the-art results across various benchmarks.
* Easy and efficient (Pleiss et al 2017) implementation available.

## Convolution
In continuous domain of $\tau$, convolution is defined as:  
  
$$(f * g)(\tau) = \int_{0}^{t} f(\tau) g(\tau - t) d\tau$$
In discrete coordinate space $[h, w]$, this is equivalently defined as:  
  
$$(f * g)[h, w] = \sum_{i}\sum_{j} f(h, w)g(h - i, w - j)$$


```python
f = np.array([[1, 1, 1, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 1, 1], [0, 0, 1, 1, 0], [0, 1, 1, 0, 0]])
g = np.array([[1, 0, 1], [0, 1, 0], [1, 0, 1]])
```

<figure>
<center>
<figcaption><font size="-1">Convolution during Forward Propagation, <a href=http://ufldl.stanford.edu/wiki/index.php/Feature_extraction_using_convolution>source of image</a></font></figcaption></center>
</figure>


```python
def element_conv():
    h, w = 3, 3
    element_conv = np.zeros_like(g, dtype=np.float32)
    for i in range(h):
        for j in range(w):
            kernel = f[i:h+i, j:w+j]
            element_conv[i, j] = np.sum(kernel * g)
    return element_conv

%timeit -n 1000 element_conv()
```

    92.2 µs ± 10.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



```python
element_conv()
```




    array([[4., 3., 4.],
           [2., 4., 3.],
           [2., 3., 4.]], dtype=float32)



Implementation as Matrix Multiplication:


```python
def matmul_conv():
    h, w = 3, 3
    col = np.zeros([9, 9])
    for i, j in product(range(h), range(w)):
        col[i*w+j] = f[i:h+i, j:w+j].flatten()
    return (g.flatten() @ col).reshape(g.shape)

%timeit -n 1000 matmul_conv()
```

    23.9 µs ± 6.66 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)



```python
# check identity
assert np.allclose(element_conv(), matmul_conv())
```

## Dense Block

A Dense Block in DenseNet is a block of hidden layers where subsequent layer reuses feature from preceding layers, through concatenation of feature maps along the depth. More concretely,
$$\begin{align*}
x_{l} &= f_{composite}(x_{0})\\
x_{2} &= f_{composite}([x_{0}, x_{1}])\\
\dots\\
x_{l} &= f_{composite}([x_{0}, x_{1}, x_{2}, \dots, x_{l-1}])
\end{align*}$$

- inspired by "identity skip connection" in ResNet
- avoids informaiton loss by using concatenation (not summation).
- bottleneck and compression techniques to control growth.

<figure>
<center>
<figcaption><font size="-1">An illustration of Dense Block of 2 layers</font></figcaption></center>
</figure>

## Composite Function

$f_{composite}$ consists of 3 functions inspired from 'pre-activation' in ResNet: Batch Normalization, ReLU, Convolution. Concretely:
  
  
$$
f_{composite}(x) = Conv(ReLU(BN(x)))
$$
  
  

<figure>
<center>
<figcaption><font size="-1">full pre-activation as in ResNet, note that "weight" indicates conv. He et al 2016</font></figcaption></center>
</figure>

**Batch Normalizing Transform** is defined as:  
$$\begin{align}
\hat{x_{i}} &= \frac{x_{i} - \mu_{B}}{\sqrt{\sigma_{B}^2 + \epsilon}}\\
BN(x_{i}; \gamma, \beta) &= \gamma \hat{x_{i}} + \beta
\end{align}$$  

It has the benefit of reducing internal covariance shift (moments of activations), accelerating training, regularizing. In addition, with DenseNet, it produces data augmentation every time a feature map is reused.  

<figure>
<center>
<figcaption><font size="-1">Test Acurracy and Distribution of Logits over time. Ioffe and Szegedy 2015</font></figcaption></center>
</figure>


**Rectified Linear Unit (ReLU)** is defined as: $$f(x) = \max({0, x})$$  
  
- faster evaluation than sigmoid function $\sigma(z) = \frac{1}{1 + e^{-z}}$
- $\frac{\partial{f(x)}}{\partial{x}} \in \{0, 1\}$ is more favourable to $\frac{\partial{\sigma(x)}}{\partial{x}} \in [0., 0.25]$ in regards to reducing gradient vanishing.
- may cause 'dead neurons', unable to recover due to $\forall x \in (-\infty, 0), \ \frac{\partial{f(x)}}{\partial{x}} = 0$.


<figure>
<center>
<figcaption><font size="-1">Saturated layer slowing down learning. Glorot and Bengio et al 2010</font></figcaption></center>
</figure>


## Dense Connectivity

- direct connections allow Jacobians to travel further with reduced gradient vanishing, so deeper network is sensibly possible.
- fewer parameters required, less prone to overfitting.
- pseudo-augmentation due to feature resuse and Batch Normalization

<figure>
<center>
<figcaption><font size="-1">A DenseNet with multiple dense blocks.</font></figcaption></center>
</figure>

a _very_ illustrative example:

$$\begin{align*}
\delta{w_1} &= \frac{\partial{E_{1}}}{\partial{w_1}} + \frac{\partial{E_{2}}}{\partial{w_1}} + \dots \\
\delta{w_1} &= \frac{\partial{E_{1}}}{\partial{f(x_1)}}\frac{\partial{f(x_1)}}{\partial{x_1}}\frac{\partial{x_1}}{\partial{w_1}} + \frac{\partial{E_{2}}}{\partial{f([x_1, x_2])}}\frac{\partial{f([x_1, x_2])}}{\partial{x_1}}\frac{\partial{x_1}}{\partial{w_1}} + \dots\\
\text{then}\\
\hat{w_1} &= w_1 - \lambda\delta{w_1}
\end{align*}$$


## Implementation

- Pleiss et al 2017 reduces memory consumption exploiting cheap concatenation and BN operations.
- Two pre-allocated shared memory storages for intermediate outputs from concatenation and BN.
  
  
<figure>
<center>
<figcaption><font size="-1">efficient implementation. Pleiss et al 2017</font></figcaption></center>
</figure>

## Not Mentioned

- bottleneck
- transition layers
- compression

## Reference

- Huang et al 2016. Densely Connected Convolutional Networks. accessible at: https://arxiv.org/abs/1608.06993
- Glorot and Bengio et al 2010. Understanding the difficulty of training deep feedforward neural networks. accessible at: http://proceedings.mlr.press/v9/glorot10a/glorot10a.pdf
- He et al 2016. Identity Mappings in Deep Residual Networks. accessible at: https://arxiv.org/abs/1603.05027
- Ioffe and Szegedy 2015. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. accessible at: https://arxiv.org/abs/1502.03167
- Pleiss et al 2017. Memory-Efficient Implementation of DenseNets. accessible at: https://arxiv.org/abs/1707.06990


## Reads
- Wan et al 2018. Reconciling Feature-Reuse and Overfitting in DenseNet with Specialized Dropout. accessible at: https://arxiv.org/abs/1810.00091
- Zhang et al 2015. Character-level Convolutional Networks for Text Classification. accessible at: https://arxiv.org/abs/1509.01626
- He et al 2015. Deep Residual Learning for Image Recognition. accessible at: https://arxiv.org/abs/1512.03385
- Krizhevsky et al 2012. Deep Convolutional Neural Networks. accessible at : https://papers.nips.cc/paper/4824-imagenet-classification-with-deep-convolutional-neural-networks.pdf
- Simonyan and Zisserman 2014. Very Deep Convolutional Networks for Large-Scale Image Recognition. accessible at: https://arxiv.org/pdf/1409.1556.pdf
- Szegedy et al 2014. Going Deeper with Convolutions. accessible at https://www.cs.unc.edu/~wliu/papers/GoogLeNet.pdf
  
## Slides
https://github.com/minggli/densenet

22f1158d9be9bc162219b60a91f09e35a27117ed
ipynb
Jupyter Notebook
LDSJC.ipynb
minggli/densenet
01420e090e72413be9345757f35371a9af813b41
MIT
2017-11-17T14:07:23.000Z
2017-11-17T14:07:23.000Z
LDSJC.ipynb
minggli/DenseNet
01420e090e72413be9345757f35371a9af813b41
MIT
2020-03-24T16:40:36.000Z
2021-03-25T22:37:42.000Z
LDSJC.ipynb
minggli/DenseNet
01420e090e72413be9345757f35371a9af813b41
MIT
Qwen/Qwen-72B
1. YES
2. YES