The paper presents a method to obtain a hierarchical clustering of a planar graph by posing the problem as that of approximating a set of edge weights using an ultrametric. This is accomplished by minimizing the $\ell_2$ norm between the given edge weights and the learnt ultrametric. Learning the ultrametric amounts to estimating a collection of multicuts that satisfies a hierarchical partitioning constraint. An efficient algorithm is presented that solves an approximation based on a finding a linear combination of a subset of possible two-way cuts of the graph.

  * They describe an architecture for deep CNNs that contains short and long paths. (Short = few convolutions between input and output, long = many convolutions between input and output)
  * They achieve comparable accuracy to residual networks, without using residuals.

### How
  * Basic principle:
    * They start with two branches. The left branch contains one convolutional layer, the right branch contains a subnetwork.
    * That subnetwork again contains a left branch (one convolutional layer) and a right branch (a subnetwork).
    * This creates a recursion.
    * At the last step of the recursion they simply insert two convolutional layers as the subnetwork.
    * Each pair of branches (left and right) is merged using a pair-wise mean. (Result: One of the branches can be skipped or removed and the result after the merge will still be sound.)
    * Their recursive expansion rule (left) and architecture (middle and right) visualized:
      ![Architecture](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/FractalNet_Ultra-Deep_Networks_without_Residuals__architecture.png?raw=true "Architecture")
  * Blocks:
    * Each of the recursively generated networks is one block.
    * They chain five blocks in total to create the network that they use for their experiments.
    * After each block they add a max pooling layer.
    * Their first block uses 64 filters per convolutional layer, the second one 128, followed by 256, 512 and again 512.
  * Drop-path:
    * They randomly dropout whole convolutional layers between merge-layers.
    * They define two methods for that:
      * Local drop-path: Drops each input to each merge layer with a fixed probability, but at least one always survives. (See image, first three examples.)
      * Global drop-path: Drops convolutional layers so that only a single columns (and thereby path) in the whole network survives. (See image, right.)
    * Visualization:
      ![Drop-path](https://raw.githubusercontent.com/aleju/papers/master/neural-nets/images/FractalNet_Ultra-Deep_Networks_without_Residuals__drop_path.png?raw=true "Drop-path")

### Results
  * They test on CIFAR-10, CIFAR-100 and SVHN with no or mild (crops, flips) augmentation.
  * They add dropout at the start of each block (probabilities: 0%, 10%, 20%, 30%, 40%).
  * They use for 50% of the batches local drop-path at 15% and for the other 50% global drop-path.
  * They achieve comparable accuracy to ResNets (a bit behind them actually).
    * Note: The best ResNet that they compare to is "ResNet with Identity Mappings". They don't compare to Wide ResNets, even though they perform best.
  * If they use image augmentations, dropout and drop-path don't seem to provide much benefit (only small improvement).
  * If they extract the deepest column and test on that one alone, they achieve nearly the same performance as with the whole network.
    * They derive from that, that their fractal architecture is actually only really used to help that deepest column to learn anything. (Without shorter paths it would just learn nothing due to vanishing gradients.)

Overview. Strong consistency is expensive. The alternative, weak consistency, is hard to program against. The lack of distributed synchronization or consensus in a weakly consistent system means that replica state can diverge. Existing systems try to hide this divergence with causal consistency to deal with read-write conflicts and per-object eventual convergence to deal with write-write conflicts, but neither is sufficient to deal with complex multi-object write-write conflicts.

As a motivating example, imagine a Wikipedia article for Donald Trump with three parts: some text, an image, and some references. In one partition, Hillary modifies the text to oppose Trump and subsequently, Tim changes the picture to a nastier image of Trump. In another picture, Trump modifies to the text to support Trump and subsequently, Mike changes the references to link to pro-Trump websites. Later, the partitions need to be merged. The write-write conflict on the text needs to be reconciled. Moreover, the modifications to the image and references do not produce conflicts but still need to be updated to match the text. Existing systems solve this in one of two ways:

1. syntactic conflict resolution: Some policy like last-writer-wins is chosen.
2. lack of cross-object semantics: Users are forced to merge individual objects.

TARDiS (Transactional Asynchronously Replicated Divergent Store) is a distributed weakly-consistent transactional key-value store that supports branching computation as a core abstraction. When working off a single branch, applications are shielded from diverging computations. Conversely, applications can merge branches and reconcile conflicts. By allowing applications to merge entire branches rather than single objects, users have the ability to perform semantically rich multi-object merges.

TARDiS employs three techniques:

1. branch-on-conflict
2. inter-branch isolation
3. application-driven cross-object merge

and has the following properties:

1. TARDiS knows history: TARDiS maintains a DAG of branching execution and uses DAG compression to minimize memory overhead.
2. TARDiS merges branches, not objects: TARDiS allows applications to merge branches rather than single-objects.
3. TARDiS is expressive: TARDiS supports various isolation levels.
4. TARDiS improves performance of the local site: Branching on conflict and deferring merge until later can improve performance in a local setting as well as in a distributed setting.

Architecture. TARDiS is a distributed multi-master key value store with asynchronous replication. There are four main layers to TARDiS:

1. Storage layer: this layer implements a disk-backed multiversion B-tree.
2. Consistency layer: this layer maintains the DAG of execution branches where each vertex is a logical state.
3. Garbage collection layer: this layer performs DAG compression and record pruning.
4. Replicator service layer: this layer propagates transactions.

Interface. Applications use TARDiS in either

1. single-mode, where transaction execute on a single branch, or
2. multi-mode, where a transaction can read from multiple branches and create a new merged branch.

TARDiS provides an API to find the set of conflicting writes for a set of branches, the find the fork points for a set of branches, and to get the versioned values of objects. It also supports varying levels of begin and end constraints including serializability, snapshot isolation, read committed, etc.

Here's an example TARDiS application that implements a counter.

```
func increment(counter)
    Tx t = begin(AncestorConstraint)
    int value = t.get(counter)
    t.put(counter, value + 1)
    t.commit(SerializabilityConstraint)

func decrement(counter)
    Tx t = begin(AncestorConstraint)
    int value = t.get(counter)
    t.put(counter, value - 1)
    t.commit(SerializabilityConstraint)

func merge()
    Tx t = beginMerge(AnyConstraint)
    forkPoint forkPt = t.findForkPoints(t.parents).first
    int forkVal = t.getForId(counter, forkPt)
    list<int> currentVals = t.getForId(counter, t.parents)
    int result = forkVal
    foreach c in currentVals
        result += (c - forkVal)
    t.put(counter, result)
    t.commit(SerializabilityConstraint)
```

Design and Implementation. When a transaction begins, TARDiS performs a BFS from the leaves of the state DAG to find the first state satisfying the begin constraint. When a transaction is committed, TARDiS walks down the state DAG as far as possible until a state is reached that doesn't satisfy the end constraint, branching if necessary. Branches are represented as a set of (b, i) pairs to indicate the bth child of the ith node. Keys are mapped to a topologically sorted list of versions used during reading.

The garbage collector performs DAG compression, eliminating unneeded states in the state DAG. It also prunes record unneeded record versions after DAG compression.

_Objective:_ In an unconditional GAN it's not possible to control the mode of the data being generated which is what this paper tries to accomplish using the label data (but it can be generalized to any kind of conditional data).

_Dataset:_ [MNIST](yann.lecun.com/exdb/mnist/) and [MIRFLICKR](http://press.liacs.nl/mirflickr/).


#### Inner workings:

Changes the loss to the conditional loss:  
[![screen shot 2017-04-24 at 10 07 25 am](https://cloud.githubusercontent.com/assets/17261080/25327832/e86f53fe-28d5-11e7-8694-6df8f2e1ef18.png)](https://cloud.githubusercontent.com/assets/17261080/25327832/e86f53fe-28d5-11e7-8694-6df8f2e1ef18.png)

For implementation the only thing needed is to feed the label data to both the discriminator and generator:  
[![screen shot 2017-04-24 at 10 07 18 am](https://cloud.githubusercontent.com/assets/17261080/25327826/e53ab4a8-28d5-11e7-8056-1518602d50c9.png)](https://cloud.githubusercontent.com/assets/17261080/25327826/e53ab4a8-28d5-11e7-8056-1518602d50c9.png)

#### Results:

Interesting at the time but not surprising now. There's not much more to the paper than what is in the summary.

The paper wished to see whether distributed word representations could be used in a machine learning setting to achieve good performance in the task of natural language inference (also called recognizing textual entailment). 

## Summary
Paper investigates the use of two neural architectures for identifying the entailment and contradiction logical relationships. In particular, the paper uses tree-based recursive neural networks and tree-based recursive neural tensor networks relying on the notion of compositionality to codify natural language word order and semantic meaning. The models are first tested on a reduced artificial data set organized around a small boolean structure world model where the models are tasked with learning the propositional relationships. Afterwards these models are tested on another more complex artificial data set where simple propositions are converted into more complex formulas. Both models achieved solid performance on these datasets although in the latter data set the RNTN seemed to struggle when tested on larger-length expressions. The models were also tested on an artificial dataset where they were tasked with learning how to correctly interpret various quantifiers and negation in the context of natural logics. Finally, the models were tested on a freely available textual entailment dataset called SICK (that was supplemented with data from the Denotation Graph project). The models achieved reasonably good performance on the SICK challenge, showing that they have the potential to accurately learn distributed representations on noisy real-world data. 
    
## Future Work
The neural models proposed seem to show particular promise for achieving good performance on very natural language logical semantics tasks. It is firmly believed that given enough data, the neural architectures proposed have the potential to perform even better on the proposed task. This makes acquisition of a more comprehensive and diverse dataset a natural next step in pursuing this modeling approach. Further even the more powerful RNTN seems to show rapidly declining performance on larger expressions which leaves the question of whether stronger models or learning techniques can be used to improve performance on considerably-sized expressions. In addition, there is still the question as to how these architectures actually encode the natural logics they are being asked to learn.