_Objective:_ Theoretical study of Deep Neural Network, their expressivity and regularizations.

## Results:

The key findings of the article are:

### A. Deep neural networks easily fit random labels.

Both when randomizing labels, replacing images with raw noise or all situations in-between.

1.  The effective capacity of neural networks is sufficient for memorizing the entire data set.
2.  Even optimization on random labels remains easy. In fact, training time increases only by a small constant factor compared with training on the true labels.
3.  Randomizing labels is solely a data transformation, leaving all other properties of the learning problem unchanged.

### B. Explicit regularization may improve generalization performance, but is neither necessary nor by itself sufficient for controlling generalization error.

By explicit regularization they mean batch normalisation, weight decay, dropout, data augmentation, etc.

### C. Generically large neural networks can express any labeling of the training data.

More formally, a very simple two-layer ReLU network with `p = 2n + d` parameters can express any labeling of any sample of size `n` in `d` dimensions.

### D. The optimization algorithm itself is implicitly regularizing the solution.

SGD acts as an implicit regularizer and properties are inherited by models that were trained using SGD.

Most of the interesting mechanics within living things are mediated by interactions between proteins, making it important and useful to have good predictive models of whether proteins will interact with one another, for validating possible interaction graph structures. 

Prior methods for this problem - which takes as its input sequence representations of two proteins, and outputs a probability of interaction - have pursued different ideas for how to combine information from the two proteins. On a basic level, you need your method to be independent to the ordering of the proteins, since the property we care about is a property of a pair of proteins, not a property of a particular ordering of proteins. Some examples of those have included: 

- A kernel function between some representation of proteins
- Representing a protein pair according to whether and how often given k-mer sequences co-occur in both proteins

This paper's DPPI method is built on a Siamese network, which applies a single shared set of convolutional layers to each of the two proteins, and then calculates a "binding score," that structurally acts a bit like a similarity score, but with allowances for proteins to be complementary, rather than just similar. In more detail: 

https://i.imgur.com/8ruY9es.png

1. Crop each protein into multiple overlapping subsequences of length 512 amino acids. Perform all following steps for every combination of cropped subsequences between the two proteins. (If A is divided into A1 and A2, you'd do the following steps for A1 x B and A2 x B and take the max score out of the two) 
2. Each cropped protein is represented as a probabilistic sequence. Since we can't get fully certain sequences of what amino acid is at each point in the chain, we instead pass in a 20x512 representation, where at each of the 512 locations we have a distribution over 20 possible amino acids. This tensor is passed into multiple layers of convolutional network, with the same network weights applied to each of the two proteins. 
3. A random projection is applied to the outputs of the convolutional network. The features that come out of the projection are conceptually similar to feature maps that might come out of a neural network layer, except that the weights aren't learned. This random projection has a specialized structure, in that it's composed of two (randomly-weighted) networks, A and B, each of which result in feature maps A1...K and B1...K. For protein 1, the outputs of the network are ordered A1...AK B1...BK, whereas for protein 2, the weights are swapped, and so the outputs are ordered B1...BK A1...AK. 
4. A Hadamard product between the two random projection outputs. This is basically a dot product, but for matrices (you multiply each element in the matrix by the corresponding element in the other matrix). This is basically like calculating a similarity score between the feature values of the randomly projected features. One benefit of doing the odd reordering in the prior step is that it breaks symmetry: if we took a dot product between features calculated by a fully shared-weight network, then we'd be looking explicitly for similarity between sequence features, which might not be sufficient to know if proteins interact in a complementary way. Another benefit is that it makes the final fully connected layer (which predicts interaction) agnostic to the order of inputs. (Caveat: I only about 70% follow the logic of this) In the example above, the 1st element will end up being A1(Prot1) x B1(ProtB), and the K+1th element will end up being B1(Prot1) x A1(ProtB). Since multiplication is order-independent,  both values 1 and K+1 represent the similarity between the proteins according to features A/B1. 
5. Once you have this final representation, feed it into a fully connected layer 

https://i.imgur.com/3LsgZNn.png

The authors show superior performance to past methods, and even show that they can get 96% accuracy on protein interactions within humans from training on a non-human species, showing that a lot of the biomechanical logic transfers. 

https://i.imgur.com/REoU3Ab.png

They did an ablation test and showed that the random projection layer added value, but also that it was better to have the weights be random than learned, which was surprising to me, and suggests the model as a whole is prone to overfit.

This work is a direct improvement of Collaborative Metric Learning. While CML tries to retrieve user and item embeddings in a direct way by placing them in metric space and adjusting with triplet loss, this paper focuses on introduction of latent relational vectors.

 A relational vector $r$ must describe relation between user $p$ and item $q$ in a way that  $s(p,q)=\parallel \ p + r - q \parallel \approx 0$.

Vectors $r$ are introduced as a softmax-weighted linear combination of vectors from Latent Relational Attentive Memory (LRAM).

The net is trained with BPR-like loss via negative sampling $max(0, s(p,q) - s(p', q') + margin)$

PyCM is a multi-class confusion matrix library written in Python that supports both input data vectors and direct matrix, and a proper tool for post-classification model evaluation that supports most classes and overall statistics parameters.	PyCM is the swiss-army knife of confusion matrices, targeted mainly at data scientists that need a broad array of metrics for predictive models and an accurate evaluation of large variety of classifiers.

This paper directly relies on understanding [Gumbel-Softmax][gs] ([Concrete][]) sampling.

The place to start thinking about this paper is in terms of a distribution over possible permutations. You could, for example, have a categorical distribution over all the permutation matrices of a given size. Of size 2 this is easy:

```
p(M)   0.1    0.9

M:     1, 0   0, 1
       0, 1   1, 0
```

You could apply the Gumbel-Softmax trick to this, and other selections of permutation matrices in small dimensions, but the number of possible permutations grows factorially with the dimension. If you want to infer the order of $100$ items, you now have a categorical over $100!$ variables, and you can't even store that number in floating point.

By breaking up and applying a normalised weight to each permutation matrix, we are effectively doing a [Naive Birkhoff-Von Neumann decomposition][naive] to return a sample from the space of Doubly Stochastic matrices. This paper proposes *much* more efficient ways to sample from this space in a way that is amenable to stochastic variational (read *SGD*) methods, such that they have an experiment working with permutations of 278 variables.

There are two ingredients to a good stochastic variational recipe:

1. A differentiable sampling method; for example (most famously): $x = \mu + \sigma \epsilon \text{ where } \epsilon \sim \mathcal{N}(0,1)$
2. A density over this sampling distribution; in the preceding example: $\mathcal{N}(\mu, \sigma)$

This paper presents two recipes: Stick-breaking transformations and Rounding towards permutation matrices.

Stick-breaking
--------------------

[Shakir Mohamed wrote a good blog post on stick-breaking methods.][sticks]

One problem, which you could guess from the categorical-over-permutations example above, is we can't possibly store a probability for each permutation matrix ($N!$ is a lot of numbers to store). Stick-breaking gives us another way to represent these probabilities implicitly through $B \in [0,1]^{(N-1)\times (N-1)}$. The row `x` gets recursively broken up like this:

```
    B_11    B_12*(1-x[:1].sum())     1-x[:2].sum()
x: |-------|------------------------|---------------------|
    x[0]    x[1]                     x[2]
    <---------------------------------------------------->
                               1.0
```

For two dimensions, this becomes a little more complicated (and is actually a novel part of this paper) so I'll just refer you to the paper and say: *this is also possible in two dimensions*.

OK, so now to sample from the distribution of Doubly Stochastic matrices, you just need to sample $(N-1) \times (N-1)$ values in the range $[0,1]$. The authors sample a Gaussian and pass it through a sigmoid. Along with a temperature parameter, the values get pushed closer to 0 or 1 and the result is a permutation matrix.

To get the density, the authors *appear to* (this would probably be annoying in high dimensions) automatically differentiate through the $N^2$ steps of the stick-breaking transformation to get the Jacobian and use change of variables.

Rounding
-------------

This method is more idiosyncratic, so I'll just copy the steps straight from the paper:

> 1. Input $Z \in R^{N \times N} $, $M \in R_+^{N \times N}$, and $V \in  R_+^{N \times N}$;
> 2. Map $M \to \tilde{M}$, a point in the Birkhoff polytope, using the [Sinkhorn-Knopp algorithm][sk];
> 3. Set $\Psi = \tilde{M} + V \odot Z$ where $\odot$ denotes elementwise multiplication;
> 4. Find $\text{round}(\Psi)$, the nearest permutation matrix to $\Psi$, using the [Hungarian algorithm][ha];
> 5. Output $X = \tau \Psi + (1- \tau)\text{round}(\Psi)$.

So you can just schedule $\tau \to 0$ and you'll be moving your distribution to be a distribution over permutation matrices.

The big problem with this is we *can't easily get the density*. Step 4 is not differentiable. However, the authors argue the function is still piecewise-linear so we can just get around this. Once they've done that, it's possible to evaluate the density by change of variables again.

Results
----------

On a synthetic permutation matching problem, the rounding method gets a better match to the true posterior (the synthetic problem is small enough to enumerate the true posterior). It also performs better than competing methods on a real matching problem; matching the activations in neurons of C. Elegans to the location of neurons in the known connectome.

[sticks]: http://blog.shakirm.com/2015/12/machine-learning-trick-of-the-day-6-tricks-with-sticks/
[naive]: https://en.wikipedia.org/wiki/Doubly_stochastic_matrix#Birkhoff_polytope_and_Birkhoff.E2.80.93von_Neumann_theorem
[gs]: http://www.shortscience.org/paper?bibtexKey=journals/corr/JangGP16
[concrete]: http://www.shortscience.org/paper?bibtexKey=journals/corr/1611.00712
[sk]: https://en.wikipedia.org/wiki/Sinkhorn%27s_theorem#Sinkhorn-Knopp_algorithm
[ha]: https://en.wikipedia.org/wiki/Hungarian_algorithm