This paper considers "the problem of learning logical structure [...] as expressed by satisfiability problems". This is an attempt at incorporating symbolic AI into neural networks. The key contribution of the paper is the introduction of "a differentiable smoothed MAXSAT solver", that is able to learn logical relationships from examples. 

The example given in the paper is Sudoku. The proposed model is able to learn jointly the rules of the game and how to solve the puzzles, **without prior on the rules**.

The core of the system is a new layer that learns satisfiability constraints while being differentiable. This layer can be embedded in a typical ConvNet:
![satnet](https://user-images.githubusercontent.com/8659132/59875340-85ae7780-936e-11e9-946c-c8e8bcb2f869.png)

Previous attempts to solve Sudoku with a neural network were unsuccessful. The networks were able to reach a high accuracy on the training set but were completely unable to generalize on new puzzles, showing they were unable to learn the underlying logic. SATNet reaches 99% test accuracy on an encoded representation of Sudoku puzzles and 63% test accuracy on images of Sudoku puzzles. 

# Comments

This layer can probably be used to solve other puzzle games, but I'm not familiar enough with SAT to know what kind of practical problems can be solved with this system. Operational research problems maybe?

Code: https://github.com/locuslab/SATNet

Batch Normalization doesn't work well when using small batch sizes, which is often required for memory intensive tasks such as detection or segmentation, or memory intensive data such as 3D images, videos or high-res images.

Group Normalization is a simple alternative that is independent of the batch size:
![image](https://user-images.githubusercontent.com/8659132/57881829-3e255080-77f0-11e9-8ba0-56089c711e7b.png)

It works as BN, except with a different set of features for computing the mean and std:
![image](https://user-images.githubusercontent.com/8659132/57882429-ab85b100-77f1-11e9-86df-2c9865d28e8b.png)
The $\gamma$ and $\beta$ are learned per group and applied as usual:
![image](https://user-images.githubusercontent.com/8659132/57882468-c9ebac80-77f1-11e9-9d19-82b83b49ea24.png)

A group is defined as a set of channels, and the mean and std is computed for that set of channels for one sample, as illustrated:
![image](https://user-images.githubusercontent.com/8659132/57882184-200c2000-77f1-11e9-9d2c-8d3fad6d6827.png)
By default, there are 32 groups, but they show GN works well as long as there is more than one group but less than the number of channels.

In term of experiments, they try on ImageNet classification, detection and segmentation in COCO, and video classification in Kinetics. The conclusion is that **GN results in the same performance no matter the batch size, and that performance is the same as BN in large batches.** The most impressive result is a 10% increase in accuracy on ImageNet with a batch size of 2 over BN.

# Comments

- This paper got an honorable mention at ECCV 2018.
- I don't understand how it works at the entrance of the network, when there is only 1 or 3 channels. Are we just not supposed to put GN there?
- Also, the number of channels tends to increase in the network, but the number of groups stays fixed. Should it scale with the number of channels?
- They tested GN on many tasks, but mostly on ResNet. There was only one experiment on VGG-16, where they found no big difference with BN. For now I'm not convinced GN is useful outside of ResNet.

Code: https://github.com/facebookresearch/Detectron/tree/master/projects/GN

Natural images can be decomposed in frequencies, higher frequencies contain small changes and details, while lower frequencies contain the global structure. We can see an example in this image:
![image](https://user-images.githubusercontent.com/8659132/58988729-4e599b80-87b0-11e9-88e2-0ecde2cce369.png)

Each filter of a convolutional layer focuses on different frequencies of the image. This paper proposes a way to group them explicitly into high and low frequency filters. 

To do that, the low frequency group is reduced spatially by 2 in all dimensions (which they define as an octave), before applying the convolution. The spatial reduction, which is a pooling operation, makes sense as it is a low pass filter, small details are discarded but the global structure is kept.

More concretely, the layer takes as input two groups of feature maps, one with a higher resolution than the other. The output is also two groups of feature maps, separated as high/low frequencies. Information is exchanged between the two groups by pooling or upsampling as needed, and as is shown on this image:

![image](https://user-images.githubusercontent.com/8659132/58990790-c7f38880-87b4-11e9-8bca-6a23c63963ad.png)

The proportion of high and low frequency feature maps is controlled through a single parameter, and through testing the authors found that having around 25% of low frequency features gives the best performance.

One important fact about this layer is that it can simply be used as replacement for a standard convolutional layer, and thus does not require other changes to the architecture. They test on various ResNets, DenseNets and MobileNets.

In terms of tasks, they get performance near state-of-the-art on [ImageNet top-1](https://paperswithcode.com/sota/image-classification-on-imagenet) and top-5. So why use this octave convolution? Because it reduces the amount of memory and computation required by the network. 

# Comments

- I would have liked to see more groups of varying frequencies. Since an octave is a spatial reduction of 2^n, the authors could do the same with n > 1. I expect this will be addressed in future work.
- While the results are not quite SOTA, octave convolutions seem compatible with EfficientNet, and I expect this would improve the performance of both.
- Since each octave convolution layer outputs a multi-scale representation of the input, doesn't that mean that pooling becomes less necessary in a network? If so, octave convolutions would give better performances on a new architecture optimized for them.

Code: [Official](https://github.com/facebookresearch/OctConv), [all implementations](https://paperswithcode.com/paper/drop-an-octave-reducing-spatial-redundancy-in)  

This paper was presented at ICML 2019.

Do you remember greedy layer-wise training? Are you curious what a modern take on the idea can achieve? This is the paper for you then. And it has its own very good summary:

> We use standard convolutional and fully connected network architectures, but instead of globally back-propagating errors, each weight layer is trained by a local learning signal,that is not back-propagated down the network. The learning signal is provided by two separate single-layer sub-networks, each with their own distinct loss function. One sub-network is trained with a standard cross-entropy loss, and the other with a similarity matching loss.

If it's a bit unclear, this figure might help: 
![local_error_signal](https://user-images.githubusercontent.com/8659132/59717441-ff672980-91e5-11e9-90d5-8f81c3468391.png)

The cross-entropy loss is the standard classification loss. The similarity loss is between the output of the layer and the one-hot encoded labels:
$$
L_{\mathrm{sim}}=\|\| S(\text { NeuralNet }(H))-S(Y) \|\|_{F}^{2}
$$

The similarity is a cosine similarity matrix $S$ where the elements are:
$$
s_{i j}=s_{j i}=\frac{\tilde{\mathbf{x}}_{i}^{T} \tilde{\mathbf{x}}_{j}}{\|\|\widetilde{\mathbf{x}}_{i}\|\|_{2}\|\|\widetilde{\mathbf{x}}_{j}\|\|_{2}}
$$

The method is used to train VGG-like models on MNIST, Fashion-MNIST, CIFAR-10 and 100, SVHN and STL-10. While it gets near-SOTA up to CIFAR-10, it's not there yet for more complex datasets. It gets 80% accuracy on CIFAR-100 where SOTA is 90% accuracy. Still, this is better than a standard ResNet for example. 

Why would we prefer a local loss to a global loss? A big advantage is that the weights can be updated during the forward pass, thus avoiding storing the activations in memory.

There was another paper on a similar topic, which I didn't read: [Greedy Layerwise Learning Can Scale to ImageNet](https://arxiv.org/abs/1812.11446).

# Comments

- While this is clearly not ready to just replace standard backprop, I find this line of work very interesting as it casts a doubt on one of the assumption of backprop: that we need a global signal to learn complex functions.
- Though not mentioned in the paper, wouldn't a local loss naturally avoid vanishing and exploding gradients?

Often the best learning rate for a DNN is sensitive to batch size and hence need significant tuning while scaling batch sizes to large scale training. Theory suggests that when you scale the batch size by a factor of $k$ (in the case of multi-GPU training), the learning rate should be scaled by $\sqrt{k}$ to keep the variance of the gradient estimator constant (remember the variance of an estimator is inversely proportional to the sample size?). But in practice, often linear learning rate scaling works better (i.e. scale learning rate by $k$), with a gradual warmup scheme. 

This paper proposes a slight modification to the existing learning rate scheduling scheme called LEGW (Linear Epoch Gradual Warmup) which helps us in bridging the gap between theory and practice of large batch training.

The authors notice that in order to make square root scaling work well in practice, one should also scale the warmup period (in terms of epochs) by a factor of $k$. In other words, if you consider learning rate as a function of time period in terms of epochs, scale the periodicity of the function by $k$, while scaling the amplitude of the function by $\sqrt{k}$, when the batch size is scaled by $k$. The authors consider various learning rate scheduling schemes like exponential decay, polynomial decay and multi-step LR decay and find that square root scaling with LEGW scheme often leads to little to no loss in performance while scaling the batch sizes. In fact, one can use SGD with LEGW with no tuning and make it work as good as Adam.

Thus with this approach, one can tune the learning rate for a small batch size and extrapolate it to larger batch sizes while making use of parallel hardwares.

**TL;DR:** This paper summarizes some of the practical tips for training a transformer model for MT task, though I believe some of the tips are task-agnostic. The parameters considered include number of GPUs, batch size, learning rate schedule, warmup steps, checkpoint averaging and maximum sequence lengths. 

**Framework used for the experiments:** [Tensor2Tensor](https://github.com/tensorflow/tensor2tensor)  

The effect of varying the most important hyper-parameters on the performances are as follows:

**Early Stopping:** Usually papers don't report the stopping criterion except in some vague terms (like number of days to train). The authors suggest that with a large dataset, even a very large model almost never converges and keeps improving by small amounts. So, keep training your model for long periods if your GPU budget supports such an option.

**Data Preprocessing:** Mostly neural architectures these days use sub word units instead of words. It's better to create the sub word vocabulary using a sufficiently large dataset. Also, its advised to filter datasets based on *max_sequence_length* and store them (for eg. as TFRecords) before training your model and not do the filtering every epoch to save precious CPU time.

**Batch Size:** Computational throughput (number of tokens executed per unit time) increases sub-linearly w.r.t. the batch size, which means after a particular number, increasing the batch size may not be that useful. From performance POV however, increasing the batch size usually leads to faster and better convergence. So, try using the maximum batch size, be it a single or multi-GPU training. Keep in mind, however, that due to random batching you may run out of memory suddenly even after days of training. So, leave some backup memory for such cases while increasing the batch size.

**Dataset size:** Experiments from the paper reinforce the fact that with BIG models, more data is better. While comparing datasets of different sizes, its advised to train the models for long enough periods because the effect of dataset sizes kicks in usually after long periods.

**Model size:** A bigger model even with a smaller batch size performs better than a smaller model with larger batch sizes after a few days of training. For debugging, use the smallest models btw!

**Maximum sequence length:** Decreasing the *max_sequence_length* leads to more examples from the dataset excluded while allowing bigger batch sizes. So, its a trade-off. Often, the presence of more examples off-sets the gains from increasing batch sizes while training for enough time. But even such a gain plateaus after a sufficient sequence length, since very long sentences are often outliers and won't contribute much to performance gains. 

**Learning rate and Warm-up steps:** The usual advice of using a not-so-high and not-so-low learning rates apply here. Using large warm-up steps often off-set the damage caused by large learning rates. So does gradient clipping.

**Number of GPUs:** For the fastest convergence, use as many GPUs as available. There would be no noticeable variation in the performances. There is a huge debate on scaling of learning rates while going from single to multiple GPUs, though the authors report that there is no significant variation while using the same learning rates, independent of the batch size (which increases with more GPUs)

**Checkpoint averaging:** Averaging last n (=10) model checkpoints saved at 1hr/30mins intervals almost always leads to better performances. This is similar to Averaged SGD from AWD-LSTM (*Merity et al.*)

What is stopping us from applying meta-learning to new tasks? Where do the tasks come from? Designing task distribution is laborious. We should automatically learn tasks!

Unsupervised Learning via Meta-Learning: The idea is to use a distance metric in an out-of-the-box unsupervised embedding space created by BiGAN/ALI or DeepCluster to construct tasks in an unsupervised way. If you cluster points to randomly define classes (e.g. random k-means) you can then sample tasks of 2 or 3 classes and use them to train a model.

Where does the extra information come from? The metric space used for k-means asserts specific distances. The intuition why this works is that it is useful model initialization for downstream tasks.

This summary was written with the help of Chelsea Finn.

In terms of model based RL, learning dynamics models is imperfect, which often leads to the learned policy overfitting to the learned dynamics model, doing well in the learned simulator but not in the real world.

Key solution idea: No need to try to learn one accurate simulator. We can learn an ensemble of models that together will sufficiently represent the space. If we learn an ensemble of models (to be used as many learned simulators) we can denoise estimates of performance. In a meta-learning sense these simulations become the tasks. The real world is then just yet another task, to which the policy could adapt quickly.  One experimental observation is that at the start of training there is a lot of variation between learned simulators, and then the simulations come together over training, which might also point to this approach providing improved exploration.

This summary was written with the help of Pieter Abbeel.

How can we learn causal relationships that explain data? We can learn from non-stationary distributions. If we experiment with different factorizations of relationships between variables we can observe which ones provide better sample complexity when adapting to distributional shift and therefore are likely to be causal.

If we consider the variables A and B we can factor them in two ways:

$P(A,B) = P(A)P(B|A)$ representing a causal graph like $A\rightarrow B$

$P(A,B) = P(A|B)P(B)$ representing a causal graph like $A \leftarrow B$

The idea is if we train a model with one of these structures; when adapting to a new shifted distribution of data it will take longer to adapt if the model does not have the correct inductive bias. For example let's say that the true relationship is $A$=Raining causes $B$=Open Umbrella (and not vice-versa). Changing the marginal probability of Raining (say because the weather changed) does not change the mechanism that relates $A$ and $B$ (captured by $P(B|A)$), but will have an impact on the marginal $P(B)$. 

So after this distributional shift the function that modeled $P(B|A)$ will not need to change because the relationship is the same.  Only the function that modeled $P(A)$ will need to change. Under the incorrect factorization $P(B)P(A|B)$, adaptation to the change will be slow because both $P(B)$ and $P(A|B)$ need to be modified to account for the change in $P(A)$ (due to Bayes rule).

Here a difference in sample complexity can be observed when modeling the joint of the shifted distribution.  $B\rightarrow A$ takes longer to adapt:
https://i.imgur.com/B9FEmA7.png

Here the idea is that sample complexity when adapting to a new distribution of data is a heuristic to inform us which causal graph inductive bias is correct.

Experimentally this works and they also observe that when models have more capacity it seems that the difference between the models grows.

This summary was written with the help of Yoshua Bengio.

For a machine learning model to be trusted/ used one would need to be confident in its capabilities of dealing with all possible scenarios. To that end, designing unit test cases for more complex and global problems could be costly and bordering on impossible to create.

**Idea**: We need a basic guideline that researchers and developers can adhere to when defining problems and outlining solutions, so that model interpretability can be defined accurately in terms of the problem statement.

**Solution**: This paper outlines the basics of machine learning interpretability, what that means for different users, and how to classify these into understandable categories that can be evaluated. This paper highlights the need for interpretability, which arises from *incompleteness*,either of the problem statement, or the problem domain knowledge. This paper provides three main categories to evaluating a model/ providing interpretations:
- *Application Grounded Evaluation*: These evaluations are more costly, and involve real humans evaluating real tasks that a model would take up. Domain knowledge is necessary for the humans evaluating the real task handled by the model.
- *Human Grounded Evaluation:* these evaluations are simpler than application grounded, as they simplify the complex task and have humans evaluate the simplified task. Domain knowledge is not necessary in such an evaluation. 
- *Functionally Grounded Evaluation:* No humans are involved in this version of evaluation, here previously evaluated models are perfected or tweaked to optimize certain functionality. Explanation quality is measured by a formal definition of interpretability.

This paper also outlines certain issues with the above three evaluation processes, there are certain questions that need answering before we can pick an evaluation method and metric. 
-To highlight the factors of interpretability, we are provided with the Data-driven approach. Here we analyze each task and the various methods used to fulfill the task and see which of these methods and tasks are most significant to the model.
- We are introduced to the term latent dimensions of interpretability, i.e. dimensions that are inferred not observed. These are divided into task related latent dimensions and method related latent dimensions, these are a long list of factors that are task specific or method specific.

Thus this paper provides a basic taxonomy for how we should evaluate our model, and how these evaluations differ from problem to problem.  The ideal scenario outlined is that researchers provide the relevant information to evaluate their proposition correctly (correctly in terms of the domain and the problem scope).

## **Introduction**
This paper presents a novel interactive tool for efficient and reproducible boundary extraction with minimal user input. Despite the user not being very accurate with the manual marking of the seed points, the algorithm snaps the boundary to the nearest strong object edge. Unlike active contour models where the user is unaware of how the final boundary will look like after energy minimization (which, if unsatisfactory, requires the entire process to be repeated again), this algorithm is interactive and therefore the user is aware of the "live-wire boundary snapping". Moreover, "boundary cooling" and "on-the-fly training" are two novel contributions of the paper which help reduce user input while maintaining the stability of the boundary.

## **Method**
Modeling the boundary detection problem as a graph search, the new objective is to find the optimal path between a start node (pixel) to a goal node (pixel), where the total cost of any path is the sum of the local costs of the path. Let the local cost of a directed edge from pixel ${p}$ to a neighboring pixel ${q}$ be
$$
    l({p}, {q}) = \underbrace{0.43f_Z({q})}_{\text{Laplacian zero crossing}} + \underbrace{0.43f_G({q})}_{\text{gradient magnitude}} + \underbrace{0.14f_D({p}, {q})}_{\text{gradient direction}}
$$
where the weights have been empirically chosen by the authors.

The gradient magnitude $f_G({g})$ needs to be a term so that higher image gradients will correspond to lower costs in order to provide a "first-order" positioning of the live wire boundary. As such, the gradient magnitude G is defined as

$$
    f_G = 1 - \frac{G}{max(G)}
$$
The Laplacian zero crossing term is a binary edge feature and acts as a "second order" fine tuning term for boundary localization.

$$
  f_Z({q}) = \left\{
  \begin{array}{@{}ll@{}}
    0, & \text{if}\ I_L({q}) = 0 \: or \: a \: neighbor \: with \: opposite \: sign \\
    1, & \text{otherwise} \\
  \end{array}\right.
$$
where $I_L$ represents the convolution of the image with a Laplacian edge operator.

The gradient direction term is associated with penalizing sharp changes in the boundary direction and therefore effectively adds a boundary smoothness constraint.

Let ${D(p)}$ be the unit vector normal to the image gradient at pixel ${p}$. Then the gradient direction cost can be represented as:
$$
    f_D({p}, {q}) = \frac{2}{3\pi}\big\{cos[d_p(({p}, {q})]^{-1} + cos[d_q(({p}, {q})]^{-1}\big\}
$$ where
$$
    d_p(({p}, {q}) = {D(p).L(p,q)}
    $$$$
    d_p(({p}, {q}) = {L(p,q).D(q)}, \: and \text{} \\ 
    $$$$
      {L(p,q)} = \left\{
      \begin{array}{@{}ll@{}}
        {q-p}, & \text{if}\ {D(p).(q-p)} \geq 0 \\
        {p-q}, & \text{otherwise} \\
      \end{array}\right.
$$
where ${L(p,q)}$ represents the normalized the bidirectional edge between pixels ${p}$ and ${q}$ and represents the direction of the link between them so that the difference between ${p}$ and this direction is minimized. Intuitively, this cost is low when the gradient direction of the two pixels are similar to each other and the link between them.

Starting at a user-selected seed point, the boundary finding is continued in the direction of the minimum cumulative cost, which creates a dynamic 'wavefront' along the directions to highest interest (which happen to be along the edges). For a path length of $n$, the boundary growing requires $n$ iterations, which is significantly more efficient than the previously used approaches.

A distribution of a variety of features (such as the image gradient $f_G$ weighted with a monotonically decreasing function (either linear or Gaussian) determines the contribution of each of the closest $t$ pixels, and the algorithm follows the edge of current interest (rather than the strongest) and associates lower costs with current edge features and higher costs for edge features not belonging to the current edge, thereby performing a dynamic or "on-the-fly" training.

The algorithm also exhibits what the paper calls "data-driven path cooling" - as the cursor (and therefore the free point) moves further away from the seed point, progressively longer portions of the boundary become fixed and only the new parts of the boundary need to be updated.

## **Results and Discussion**
Using the algorithm, the boundaries are extracted in one-fifth of the time required for manually tracing the boundary, while doing so with a 4.4x higher accuracy and 4.8x higher reproducibility. However, the paper admits that boundary detection can be difficult with objects with "hair like boundaries". Moreover, this technique cannot be extended to N-dimensional images.

## **Introduction**
This paper presents a stochastic active contour model for image segmentation from cardiac MR images. The proposed algorithms aims to minimize an energy functional by the level set method while incorporating stochastic region based and edge based information as well as shape priors of the heart and local contour properties. Moreover, the algorithm also uses a parameter annealing component to dynamically balance the weightage of the components of the energy functional.


## **Method**
The paper locates a contour $C$ in a cardiac MR image that segments the image into two groups - the heart and the background. The corresponding objective energy functional can be represented by
$$
    J(C) = \lambda_1 J_1(C) + \lambda_2 J_2(C) + \lambda_3 J_3(C) + \lambda_4 J_4(C)
$$

Looking at these individual components, we have
* _Region Based Term: Model Matching_ **$J_1(\phi)$**: In order to segment the image into 2 regions, let the two regions inside and outside the contour C be represented by $\Omega_1$ and $\Omega_2$ respectively. For each region, consider a stochastic model to describe the pixel statistics of that region. Assuming that the pixel intensities of all the pixels in each region are statistically independent, the objective is to minimize the negative log-likelihood  of pixels belonging to the correct regions.
*  _Edge Based Term_ **$J_2(\phi)$**: In order for the contour C to be aligned to the prominent edges in the image, the edge map of the image (which can be obtained by various image smoothing methods such as Gaussian kernel blurring, edge-preserving anisotropic diffusions, Min/Max flow algorithms, etc.) has to be minimized.
* _Heart Shape Prior Term_ **$J_3(\phi)$**: In order to distinguish between similar looking tissues in the foreground and the background, an elliptical heart shaped prior is used. An ellipse can be described with 5 parameters with certain constraints in the conic equation. 
* _Contour Smoothing Term_ **$J_4(\phi)$**: In order to obtain a smooth contour of the segmented heart, the total Euclidean arc length of the contour C should be minimized.

The parameters ($\lambda_1$, $\lambda_2$, and $\lambda_3$) of the energy functional $J(C)$ need to be dynamically updated during the energy minimization. For example, the region-based and the edge-based terms should have a higher weightage in $J(C)$ during the initial steps of the segmentation, and at the later stages, their weightage should be reduced and that of the shape prior should be increased in order to keep the segmented output similar to the desired shape.

## **Results**

The two metrics used for assessing the performance were Area Similarity and Shape Similarity. The algorithm was tested on 48 images covering 143 contours, including manually annotated contours by an expert on six rat cardiac sequences of eight frames each, and the results indicated excellent segmentation agreement with the manually traced contours.

## **Discussion and Shortcomings**
Since STACS uses stochastic models instead of deterministic models, it can be applied to a large variety of images, and is especially helpful when distinguishing between visually similar adjacent regions.

Since STACS incorporates both region-based and edge-based information in its energy functional, this makes it more robust to noise as well as reduces the susceptibility to curve initialization.

Perhaps the most highlighting feature of STACS that distinguishes it from other active contour based models is that it incorporates shape based priors into the energy functional. This helps segment the heart from the chest wall, which is especially difficult since the two regions share similar texture.

Moreover, the scheduled parameter annealing adjusts the weights of the components of the energy functional, which helps dynamically vary the importance to different components at different stages of the segmentation process.

## **Introduction**
This paper presents an active contour model to detect and segment objects in images whose boundaries may or may not be defined by their gradients. The curve evolution is based on the Mumford Shah energy functional and the level set methods, making it less susceptible to curve initialization errors.


## **Method**
Using an implicit shape representation, the boundary(s) C can be represented using the zero level set of an embedding function $\phi : \Omega \rightarrow$ **R** such that

$$
    C = \{x \in \Omega \:|\: \phi(x) = 0\}
$$

Such a representation of the boundary does not require a choice of parameterization.

The embedding function $\phi(.)$ is defined as 
$$
    \phi(x) = \pm \: distance(x,C)
$$
where the sign is either + or - depending upon whether the point is inside or outside the curve. This means that the boundary can be determined by finding out the point at which $\phi$ changes its sign.

According to the level set method [1], the embedding function is zero at all the points on the curve C at any time.

$$
    \phi(C(t),\:t) = 0 \:\: \forall t
$$

Consider the piecewise Mumford Shah energy functional model [2] with 2 regions $\Omega_{1}$ and $\Omega_{2}$ such that $\Omega = \Omega_{1} + \Omega_{2}$.

Let us define the Heaviside step function as 

$$
  H\phi \equiv H(\phi)\left\{
  \begin{array}{@{}ll@{}}
    1, & \text{if}\ \phi > 0 \: \Rightarrow x \in \Omega_{1} \\
    0, & \text{otherwise}\ \Rightarrow x \in \Omega_{2} \\
  \end{array}\right.
$$

Moving from an energy functional defined on the boundary C to one defined on the embedding function $\phi$, we get

$$
    E(\phi) = \int\limits_{\Omega_{1}} \: ({I}(x,y) - \mu_{1})^{2} \: dx + \int\limits_{\Omega_{2}} \: ({I}(x,y) - \mu_{2})^{2} \: dx + \nu \left| \partial \Omega_{1} \right|
$$

where we approximate the average brightness/intensity of all the pixels in the $\Omega_{1}$ and $\Omega_{2}$ regions to be $\mu_{1}$ and $\mu_{2}$ respectively. The term $\left| \partial \Omega_{1} \right|$ represents the length of the boundary and is added as a penalizer/regularizer.

Simplifying this expression, we get
$$
    \begin{align*}
    E(\phi) & =
    \int\limits_{\Omega} \: \Big[\big[({I}(x,y) - \mu_{1})^{2} - ({I}(x,y) - \mu_{2})^{2}\big]H\phi \\
    & + ({I}(x,y) - \mu_{2})^{2}\Big]\:dx + \nu \int\limits_{\Omega}\left| \nabla H\phi \right|\:dx
\end{align*}
$$

Since $H(\phi)$ is not differentiable everywhere, we assume a slightly smoothened Heaviside function such that

$$
    \frac{\mathrm{d} H(\phi)}{\mathrm{d} \phi} = \delta(\phi)
$$

One such choice of the smoothened delta function is

$$
    \delta_{\epsilon}(\phi) = \frac{1}{\pi} \frac{\epsilon}{\epsilon^{2} + \phi^{2}}, \: \epsilon > 0
$$

Now, the gradient descent equation can be computed as 
$$
    \frac{\partial \phi}{\partial t} =  \delta(\phi) \Big[\: \nu\:div\Big(\frac{\nabla \phi}{\left|\nabla \phi\right|}\Big) + ({I}(x,y) - \mu_{1})^{2} - ({I}(x,y) - \mu_{2})^{2}\Big]
$$

As the embedding function $\phi(.)$ evolves over time, the boundary points can be detected when it undergoes a sign change.


## **Discussion and Shortcomings**
As compared to the edge-based segmentation approaches such as geodesic active contours [3], this method uses region based segmentation, and can, therefore, result in curve evolution that is not just local.

The segmentation results are not dependent on the initialization of the curve. Because of the choice of the embedding function $\phi$ as a signed distance function, the curves can split and merge. Moreover, unlike geodesic active contours [3], new curves can also be formed. This is because of the numerical approximation of the delta function - since the delta function never actually goes to 0. This means that objects with interior contours such as a ring can also be segmented, which was not possible with previously available active contour models.

#### [1] S. Osher, and J. A. Sethian, "Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations,'' *Journal of Computational Physics*, vol. 79, no. 1, pp. 12-49, 1988.

#### [2] D. Mumford, and J. Shah, "Optimal approximations by piecewise smooth functions and associated variational problems,'' *Communications on Pure and Applied Mathematics*, vol. 42, no. 5, pp. 577-685, 2006.

#### [3] V. Caselles, R. Kimmel, and G. Sapiro, "Geodesic Active Contours,'' *International Journal of Computer Vision*, vol. 22, no. 1, pp. 61-79, February 1997.

## **Introduction**
This paper presents a generalized technique of matching a deformable model to an image through energy minimization. An active contour model called snakes has been proposed which is a continuous and deformable spline always minimizing its energy under the influence of image forces as well as internal energy of the spline and external constraint forces. Because of its dynamic nature, snakes can be applied to image segmentation tasks (edges, lines, and subjective contours) as well as to motion tracking and stereo matching.

## **Method**
A snake can be parametrically represented as
$$
    {v}(s) = (x(s), y(s))
$$

The energy functional of a snake consists of the internal and the external energy components.
$$
    E_{snake}(C) = \underbrace{E_{ext}(C)}_{\text{data term}} + \underbrace{E_{int}(C)}_{\text{regularization term}}
$$

This can be decomposed into the following components:
$$
    E^{*}_{snake} = \int_{0}^{1} \Big[\: E_{int}({v}(s)) + E_{image}({v}(s)) + E_{constr}({v}(s)) \:\Big] \: ds
$$

where the components represent the internal energy of the snake due to its shape and bending, the image forces, and the external constraint forces on the snake respectively.

The internal energy of the snake can be represented as 
$$
    E_{int} = \frac{1}{2} \{\alpha (s)\left | {v}_{s}(s) \right |^{2} \:+\: \beta (s)\left | {v}_{ss}(s) \right |^{2}\}
$$
where the first order term and the second order term represent the elastic length and the stiffness of the snake respectively. 

The energy minimization is a $O(n)$ technique in time using sparse matrix methods (semi-implicit Euler method), which is is much faster than a $O(n^{2})$ fully explicit method.

The energy due to the image forces is composed of three components:
$$
    E_{image} = w_{line}E_{line} + w_{edge}E_{edge} + w_{terminal}E_{terminal}
$$ where
$$E_{line} = -\big( G_{\sigma} * \nabla^{2}{I} \big)^{2},$$ $$ E_{edge} = -\left | \nabla {I}(x,y) \right |^{2},$$ $$E_{term} = \frac{\partial \theta}{\partial {n}_{\perp}} = \frac{C_{yy}C_{x}^{2} - 2C_{xy}C_{x}C_{y} + C_{xx}C_{x}^{2}}{(C_{y}^{2} + C_{x}^{2})^\frac{3}{2}}$$

* The minima of the $E_{line}$ energy functional define the edges of the image. Depending upon the sign of the $w_{line}$ term, the snake tries to align itself to the lightest or the darkest contour near it. Smoothening the image gradient with a Gaussian allows the snake to reach an equilibrium on a blurred energy functional, and when the blurring is slowly reduced, the snake stays in shape despite the small scale textural details because of its own smoothness constraint.
    
* Because of the $E_{edge}$ term, the snake is attracted to the contours corresponding to large image gradients.
    
* Consider $C(x,y)$ to be a slightly smoothened image obtained by applying a Gaussian filter to it. The $E_{terminal}$ represents the energy corresponding to the curvature of the level contours of $C(x,y)$, and can be calculated as the rate of change of the gradient angle $\theta$ along the direction of the outer unit normal to the curve. The combination of $E_{edge}$ and $E_{terminal}$ ensures that during the energy minimization, the snake is attracted to the edges and/or the terminations.

Snakes can also be applied to the problem of stereo matching by adding an additional constraint to the energy functional. The constraint is that the disparities in the human visual system do not change too rapidly with space, meaning the following disparity has to be minimized, where the ${v}^{L}(s)$ and the ${v}^{R}(s)$ represent the left and the right snake contours respectively.

$$
    E_{stereo} = \big( {v}^{L}_{s}(s) - {v}^{L}_{s}(s) \big)^{2}
$$

Similarly, snakes can also be applied to the problem of motion tracking since the snakes are able to "lock on" to salient visual features and can, therefore, track them accordingly across frames.

## **Discussion and Shortcomings**
The snakes were the first variational approach to the image segmentation task, and therefore this was a seminal paper in image processing. By introducing the gradient (edge strength) as an energy term, they improved on the shortcomings of the prior published works.

Because snakes are "active" and are therefore always minimizing their energy, they show hysteresis in response to moving input.

The energy minimization for the snakes is achieved through gradient descent, and since the energy functional is not convex, it can get stuck on local minima. Therefore, a prerequisite for the snakes is that the curve initialization must be done sufficiently close to the desired solution.

Moreover, because of numerical instabilities, as the control points move in time, the curve can have self-intersections which is undesired in image segmentation tasks.

The fundamental unit of Reinforcement Learning is the reward function, with a core assumption of the area being that actions induce rewards, with some actions being higher reward than others. But, reward functions are just artificial objects we design to induce certain behaviors; the universe doesn’t hand out “true” rewards we can build off of.  Inverse Reinforcement Learning as a field is rooted in the difficulty of designing reward functions, and has the aspiration of, instead of requiring a human to hard code a reward function, inferring rewards from observing human behavior. The rough idea is that if we imagine a human is (even if they don’t know it) operating so as to optimize some set of rewards, we might be able to infer that set of underlying incentives from their actions, and, once we’ve extracted a reward function, use that to train new agents. This is a mathematically quite tricky problem, for the basic reason that a human’s actions are often consistent with a wide range of possible underlying  “policy” parameters, and also that a given human policy could be an optimal for a wide range of underlying reward functions. 

This paper proposes using an adversarial frame on the problem, where you learn a reward function by trying to make reward higher for the human demonstrations you observe, relative to the actions the agent itself is taking. This has the effect of trying to learn an agent that can imitate human actions. However, it specifically designs its model structure to allow it to go beyond just imitation. The problem with learning a purely imitative policy is that it’s hard for the model to separate out which actions the human is taking because they are intrinsically high reward (like, perhaps, eating candy), versus actions which are only valuable in a particular environment (perhaps opening a drawer if you’re in a room where that’s where the candy is kept). If you didn’t realize that the real reward was contained in the candy, you might keep opening drawers, even if you’re in a room where the candy is laying out on the table. 

In mathematical terms, separating out intrinsic vs instrumental (also known as "shaped") rewards is a matter of making sure to learn separate out the reward associated with a given state from value of taking a given action at that state, because the value of your action is only born out based on assumptions about how states transition between each other, which is a function of the specific state to state dynamics of the you’re in. The authors do this by defining a g(s) function, and a h(s) function. They then define their overall reward of an action as (g(s) + h(s’)) - h(s), where s’ is the new state you end up in if you take an action. 

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

This follows the natural form of a Bellman update, where the sum of your future value at state T should be equal to the sum of your future value at time T+1 plus the reward you achieve at time T. 

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

By adopting this structure, and learning a separate neural network to capture the h(s) function representing the value from here to the end, the authors make it the case that the g(s) function is a purer representation of the reward at a state, regardless of what we expect to happen in the future. Using this, they’re able to use this learned reward to bootstrap good behavior in new environments, even in contexts where a learned value function would be invalid because of the assumptions of instrumental value. They compare their method to the baseline of GAIL, which is a purely imitation-learning approach, and show that theirs is more able to transfer to environments with similar states but different state-to-state dynamics. 

In the area of explaining model predictions over images, there are two main strains of technique: methods that look for pixels that have the highest gradient effect on the output class, and assign those as the “reason” for the class, and approaches that ask which pixel regions are most responsible for a given classification, in the sense that the classification would change the most if they were substituted with some uninformative reference value. 

The tricky thing about the second class of methods is that you need to decide what to use as your uninformative fill-in value. It’s easy enough to conceptually pose the problem of “what would our model predict if it couldn’t see this region of pixels,” but as a practical matter, these models take in full images, and you have to put *something* to give the classifier in a region, if you’re testing what the score would be if you removed the information contained in the pixels in that region. What should you fill in instead? The simplest answers are things like “zeros”, or “a constant value” or “white noise”. But all of these are very off-distribution for the model; it wouldn’t have typically seen images that resemble white noise, or all zeros, or all a single value. So if you measure the change in your model score from an off-distribution baseline to your existing pixels, you may not be getting the marginal value of the pixels, so much as the marginal disutility of having something so different from what the model has previously seen. There are other, somewhat more sensible approaches, like blurring out the areas around the pixel region of interest, but these experience less intense forms of the same issue. 

This paper proposes instead, using generative models to fill in the regions conditioned on the surrounding pixels, and use that as a reference. The notion here is that a conditioned generative model, like a GAN or VAE, can take into account the surrounding pixels, and “imagine” a fill-in that flows smoothly from the surrounding pixels, and looks generally like an image, but which doesn’t contain the information from the pixels in the region being tested, since it wasn’t conditioned on that. 

https://i.imgur.com/2fKnY0M.png

Using this approach, the authors run two types of test: one where they optimize to find the smallest region they can remove from the image, and have it switch class (Smallest Deletion Region, or SDR), and also the smallest informative region that can be added to an otherwise uninformative image, and have the model predict the class connected to that region. They find that regions calculated using their generative model fill in, and specifically with GANs, find a smaller and more compact pixel region as their explanation for the prediction, which is consistent with both human intuitions and also with a higher qualitative sensibleness of the explanations found. 

This paper tries to do an exhaustive empirical evaluation of the question of how effectively you can reduce the number of training steps needed to train your model, by increasing the batch size. This is an interesting question because it’s becoming increasingly the case that computational costs scale very slowly with additional datapoints added to a batch, and so your per-example cost will be lower, the larger a batch you do your gradient calculation in. 

In the most ideal world, we might imagine that there’s a perfect trade-off relationship between batch size and training steps. As a simplistic example, if it were the case that your model only needed to see each observation in the dataset once in order to obtain some threshold of accuracy, and there was an unbounded ability to trade off batch size against training steps, then one might imagine that you could just take one large step based on the whole dataset (in which case you’d then be doing not Stochastic Gradient Descent, but just Batch Gradient Descent). However, there’s reason to suspect that this won’t be possible; for one thing, it seems like having multiple noisier steps is better for optimization than taking one single step of training. 

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

This paper set out to do a large-scale evaluation of what this behavior looks like over a range of datasets. They did so by setting a target test error rate, and then measuring how many training steps were necessary to reach that error rate, for a given batch size. For fairness, they trained hyperparameters separately for each batch size. They found that, matching some theoretical predictions, at small to medium batch sizes, your increase in batch size pays off 1:1 in fewer needed training steps. As batch size increases more, the tradeoff curve diverges from 1:1, and eventually goes flat, meaning that, even if you increase your batch size more, you can no longer go any lower in terms of training steps. This seems to me connected to the idea that having a noisy, multi-step search process is useful for the non-convex environments that neural net optimizers are working in. 

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

A few other notes from the paper:
- Different model architectures can extend 1:1 scaling to higher batch sizes, and thus plateau at a lower number of training steps
- Momentum also has the effect of plateauing at a lower number of needed training steps
- It’s been previously suggested that you need to scale optimal learning rate linearly or according to the square root of the batch size, in order to maintain best performance. The authors find that there are different learning rates across batch size, but that they aren’t well-approximated by a linear or square-root relationship

This was definitely one of the more conceptually nuanced and complicated papers I’ve read recently, and I’ve only got about 60% confidence that I fully grasp all of its intuitions. However, I’m going to try to collect together what I did understand. 

There is a lot of research into generative models of text or image sequences, and some amount of research into building “models” in the reinforcement learning sense, where your model can predict future observations given current observations and your action. There’s an important underlying distinction here between model-based RL (where you learn a model of how the world evolves, and use that to optimize reward) and model-free RL (where you leave don’t bother explicitly learning a world model, and just directly try to optimize rewards)  However, this paper identifies a few limitations of this research. 

1) It’s largely focused on predicting observations, rather than predicting *state*. State is a bit of a fuzzy concept, and corresponds to, roughly, “the true underlying state of the game”. An example I like to use is a game where you walk in one door, and right next to it is a second door, which requires you to traverse the space and find rewards and a key before you can open. Now, imagine that the observation of your agent is it looking at the door. If the game doesn’t have any on-screen representation of the fact that you’ve found the key, it won’t be present in your observations, and you’ll observe the same thing at the point you have just entered and once you found the key. However, the state of the game at these two points will be quite different, in that in the latter case, your next states might be “opening the door” rather than “going to collect rewards”. Scenarios like this are referred to broadly as Partially Observable games or environments. This paper wants to build a model of how the game evolves into the future, but it wants to build a model of *state-to-state* evolution, rather than observation-to-observation evolution, since observations are typically both higher-dimensionality and also more noisy/less informative. 

2) Past research has typically focused on predicting each next-step observation, rather than teaching models to be able to directly predict a state many steps in the future, without having to roll out the entire sequence of intermediate predictions.  This is arguably quite valuable for making models that can predict the long term consequences of their decision 

This paper approaches that with an approach inspired by the Temporal Difference framework used in much of RL, in which you update your past estimate of future rewards by forcing it to be consistent with the actual observed rewards you encounter in the future. Except, in this model, we sample two a state (z1) and then a state some distance into the future (z2), and try to make our backwards-looking prediction of the state at time 1, taking into account observations that happened in between, match what our prediction was with only the information at time one. 

An important mechanistic nuance here is the idea of a “belief state”, something that captures all of your knowledge about game history up to a certain point. We can then directly sample a state Zt given the belief state Bt at that point. This isn’t actually possible with a model where we predict a state at time T given the state at time T-1, because the state at time Z-1 is itself a sample, and so in order to get a full distribution of Zt, you have to sample Zt over the distribution of Zt-1, and in order to get the distribution of Zt-1 you have to sample over the distribution of Zt-2, and so on and so on. Instead, we have a separate non-state variable, Bt that is created conditional on all our past observations (through a RNN). 

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

All said and done, the mechanics of this model look like: 
1) Pick two points along the sequence trajectory
2) Calculate the belief state at each point, and, from that, construct a distribution over states at each timestep using p(z|b) 
3) Have an additional model that predicts z1 given z2, b1, and b2 (that is, the future beliefs and states), and push the distribution over z1 from this model to be close to the distribution over z1 given only the information available at time t1
4) Have a model that predicts Z2 given Z1 and the time interval ahead that we’re jumping, and try to have this model be predictive/have high likelihood over the data 
5) And, have a model that predicts an observation at time T2 given the state Z2, and train that so that we can convert our way back to an observation, given a state 

They mostly test it on fairly simple environments, but it’s an interesting idea, and I’d be curious to see other people develop it in future. 

(A strange aspect of this model is that, as far as I can tell, it’s non-interventionist, in that we’re not actually conditioning over agent action, or trying to learn a policy for an agent. This is purely trying to learn the long term transitions between states) 

Current work in image generation (and generative models more broadly) can be split into two broad categories: implicit models, and likelihood-based models. Implicit models is a categorically that predominantly creates GANs, and which learns how to put pixels in the right places without actually learning a joint probability model over pixels. This is a detriment for applications where you do actually want to be able to calculate probabilities for particular images, in addition to simply sampling new images from your model. Within the class of explicit probability models, the auto-encoder and the autoregressive model are the two most central and well-established. 

An auto-encoder works by compressing information about an image into a central lower-dimensional “bottleneck” code, and then trying to reconstruct the original image using the information contained in the code. This structure works well for capturing global structure, but is generally weaker at local structure, because by convention images are generated through stacked convolutional layers, where each pixel in the image is sampled separately, albeit conditioned on the same latent state (the value of the layer below). This is in contrast to an auto-regressive decoder, where you apply some ordering to the pixels, and then sample them in sequence: starting the prior over the first pixel, and then the second conditional on the first, and so on. In this setup, instead of simply expecting your neighboring pixels to coordinate with you because you share latent state, the model actually has visibility into the particular pixel sampled at the prior step, and has the ability to condition on that. This leads to higher-precision generation of local pixel structure with these models .

If you want a model that can get the best of all of these worlds - high-local precision, good global structure, and the ability to calculate probabilities - a sensible approach might be to combine the two: to learn a global-compressed code using an autoencoder, and then, conditioning on that autoencoder code as well as the last sampled values, generate pixels using an autoregressive decoder. However, in practice, this has proved tricky. At a high level, this is because the two systems are hard to balance with one another, and different kinds of imbalance lead to different failure modes. If you try to constrain the expression power of your global code too much, your model will just give up on having global information, and just condition pixels on surrounding (past-sampled) pixels. But, by contrast, if you don’t limit the capacity of the code, then the model puts even very local information into the code and ignores the autoregressive part of the model, which brings it away from playing our desired role as global specifier of content. 

This paper suggests a new combination approach, whereby we jointly train an encoder and autoregressive decoder, but instead of training the encoder on the training signal produced by that decoder, we train it on the training signal we would have gotten from decoding the code into pixels using a simpler decoder, like a feedforward network. The autoregressive network trains on the codes from the encoder as the encoder trains, but it doesn’t actually pass any signal back to it. Basically, we’re training our global code to believe it’s working with a less competent decoder, and then substituting our autoregressive decoder in during testing. 

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

Some additional technical notes: 
- Instead of using a more traditional continuous-valued bottleneck code, this paper uses the VQ-VAE tactic of discretizing code values, to be able to more easily control code capacity. This essentially amounts to generating code vectors as normal, clustering them, passing their cluster medians forward, and then ignoring the fact that none of this is differentiable and passing back gradients with respect to the median 
- For their auxiliary decoders, the authors use both a simple feedforward network, and also a more complicated network, where the model needs to guess a pixel, using only the pixel values outside of a window of size of that pixel. The goal of the latter variant is to experiment with a decoder that can’t use local information, and could only use global

Unsupervised representation learning is a funny thing: our aspiration in learning representations from data is typically that they’ll be useful for future tasks, but, since we (by definition) don’t have access to labels, our approach has historically been to define heuristics, such as representing the data distribution in a low-dimensional space, and hope that those heuristics translate to useful learned representations. And, to a fair extent, they have. However, this paper’s goal is to attach this problem more directly, by explicitly meta-learning an unsupervised update rule so that performs well in future tasks. They do this by: 

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

1) Defining a parametrized weight update function, to slot into the role that Stochastic Gradient Descent on a label-defined loss function would play in a supervised network. This function calculates a “hidden state”, is defined for each neuron in each layer, and takes in the pre and post-nonlinearity activations for that batch, the hidden state of the next layer, and a set of learned per-layer “backwards weights”. The weight update for that neuron is then calculated using the current hidden state, the last batch's hidden state, and the current value of the weight. In the traditional way of people in this field who want to define some generic function, they instantiate these functions as a MLP. 

2) Using that update rule on the data from a new task, taking the representing resulting from applying the update rule, and using it in a linear regression with a small number of samples. The generalization performance from this k-shot regression, taken in expectation over multiple tasks, acts as our meta training objective. By back-propagating from this objective, to the weight values of the representation, and from there to the parameters of the optimization step, they incentivize their updater to learn representations that are useful across some distribution of tasks. 


A slightly weird thing about this paper is that they train on image datasets, but shuffle the pixels and use a fully connected network rather than a conv net. I presume this has to do with the complexities of defining a weight update rule for a convolution, but it does make it harder to meaningfully compare with other image-based unsupervised systems, which are typically done using convolution. An interesting thing they note is that, early in meta-training on images, their update rules generalize fairly well to text data. However, later in training the update rules seem to have specialized to images, and generalize more poorly to images.