Naseer et al. propose to smooth local gradients as defense against adversarial patches. In particular, as illustrated in Figure 1, the local image gradient is computed through convolution. Then, in local, overlapping windows, the gradients are set to zero if the total sum of absolute gradient values exceeds a specific threshold. The remaining gradient map is supposed to indicate regions where it is likely that adversarial patches can be found. Using this gradient map, the image is smoothed, i.e., blurred, afterwards. In experiments, the authors show that this reduces the impact of adversarial patches.

Also find this summary at [davidstutz.de](https://davidstutz.de/category/reading/).

This paper performs a fascinating toy experiment, to try to see if something language-like in structure can be effectively induced in a population of agents, if they are given incentives that promote it. In some sense, a lot of what they find “just makes sense,” but it’s still a useful proof of concept to show that it can be done. 

The experiment they run takes place in a simple, two-dimensional world, with a fixed number of landmarks (representing locations goals need to take place), and agents, and actions. In this construction, each agent has a set of internal goals, which can either be actions (like “go to green landmark”) they themselves need to perform, or actions that they want another agent to perform. Agents’ goals are not visible to other agents, but all agents’ reward is defined to be the aggregated reward of all agents together, so if agent A has a goal involving an action of agent B’s, it’s in B’s “interest” to do that action, if it can be communicated to them. In order to facilitate other agents performing goals, at each step, each agent both takes an action, and also emits an “utterance”, which is just a discrete symbolic “word” out of some some fixed vocabulary of words (Note that applying “word” here is a but fuzzy; the agents do not pronounce or spell a character-based word, they just pick a discrete symbol that is playing the role of a word”. Even though other agents cannot see a given agent’s goals, they can see its public utterances, and so agents learn that communication is a way to induce other agents to perform desired actions. 

As a mathematically interesting aside: this setup, of allowing each agent to sample a single discrete word out of a small vocabulary at each setting, takes the deployment of some interesting computational tricks to accomplish. First off, in general, sampling a discrete single symbol out of a set of possible symbols is not differentiable, since it’s a discrete rather than continuous action, and derivatives require continuous functions. However, a paper from 2016 proposed a (heuristic) solution to this problem by means of the Gumbel Softmax Trick. This derives from the older “Gumbel Max Trick”, which is the mathematical fact that if you want to sample from a categorical distribution, a computationally easy way to do so is to add a variable sampled from a (0,1) Gumbel distribution to the log probability of each category, and then take the argmax of this as the index of the sample category (I’m not going to go another level down into why this is true, since I think it’s too far afield of the scope of this summary). Generally, argmax functions are also not differentiable. However, they can be approximated with softmaxes, which interpolate between a totally uniform and very nearly discrete-sample distribution based on a temperature parameter. In practice, or, at least, if this paper does what the original Gumbel Softmax paper did, during training, a discrete sample is taken, but a low-temperature continuous approximation is used for actual gradient calculation (i.e. for gradients, the model pretends that it used the continuous approximation rather than the discrete sample). 

https://i.imgur.com/0RpRJG2.png

Coming back to the actual communication problem, the authors do find that under these (admittedly fairly sanitized and contrived) circumstances, agents use series of discrete symbols to communicate goals to other agents, which ends up looking a lot like a very simple language. 

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

As one might expect, in environments where there were only two agents, there was no symbol that ended up corresponding to “red agent” or “blue agent”, since each could realize that the other was speaking to it. However, in three-agent environments, the agents did develop symbols that clearly mapped to these categories, to specify who directions were being given to. The authors also tried cutting off verbal communication; in these situations, the agents used gaze and movement to try to signal what they wanted other agents to do. Probably most entertainingly, when neither verbal nor visual communication was allowed, agents would move to and “physically” push other agents to the location where their action needed to be performed. 

This paper introduces the B-link tree: a variant of a B+ tree (the paper says B* tree, but they mean B+ tree) which allows for concurrent searches, insertions, and deletions. Operations on a B-link tree lock at most three nodes at any given time, and searches are completely lock free.

#### Storage Model

We assume that every node of a B+ tree or B-link tree is stored on disk. Threads read nodes from disk into memory, modify them in memory, and then write them back to disk. Threads can also lock a specific node which will block other threads trying to acquire a lock on the same node. However, we'll also see that threads performing a search will not acquire locks at all and may read a node which is locked by another thread.

#### Concurrent B+ Trees

Let's see what goes wrong when we concurrently search and insert into a B+ tree without any form of concurrency control. Consider a fragment of a B+ tree shown below with two nodes x and y. Imagine a thread is searching for the value 2 and reads the pointer to y from x.

```
            +-------+
          x | 5 |   |
            +-------+
           /    |
  +-------+    ...
y | 1 | 2 |
  +-------+
```

Then, another thread inserts the value 3 which reorganizes the tree like this:

```
            +-------+
          x | 2 | 5 |
            +-------+
           /    |    \
  +-------+ +-------+ ...
y | 1 |   | | 2 | 3 |
  +-------+ +-------+
```

Next, the searching thread reads from y but cannot find the value 2!

Clearly, concurrently searching and inserting into a B+ tree requires some sort of locking. There are already a number of locking protocols:

 - The simplest protocol requires searches and insertions to lock every node along their path from root to leaf. This protocol is correct, but limits concurrency.
 - Smarter protocols have insertions place write intention locks along a path and upgrade those locks to exclusive locks when performing a write. Searches can read nodes with write intention locks on them but not with exclusive locks on them.
 - Even smarter protocols lock a subsection of the tree and bubble this subsection upwards through the tree. B-link trees will do something similar but will guarantee that at most three nodes are locked at any given point in time.

#### B-link Trees

 - Typically, an internal node in a B+ tree with $n$ keys has $n + 1$ pointers. For example, if an internal node has keys $(5, 10, 15)$, then it has four pointers for values in the range $[-\infty, 5)$, $[5, 10)$, $[10, 15)$, and $[15, \infty)$. Internal nodes in a B-link tree with $n$ keys have $n$ pointers where the last key is known as the <strong>high key</strong>. For example, if an internal node has keys $(5, 10, 15)$ then it has three pointers for values in the range $[-\infty, 5)$, $[5, 10)$, and $[10, 15)$.
 - In a B+ tree, leaves are linked together, but internal nodes are not. In a B-link tree, all sibling nodes (internal nodes and leaves) are linked together left to right.

#### Search Algorithm

The search algorithm for a B-link tree is very similar to the search algorithm for a B+ tree. To search for a key $k$, we traverse the tree from root to leaf. At every internal node, we compare $k$ against the internal node's keys to determine which child to visit next.

However, unlike with a B+ tree, we might have to walk rightward along the B-link tree to find the correct child pointer. For example, imagine we are searching for the key $20$ at an internal node $(5, 10, 15)$. Because $20 \gt 15$, we have to walk rightward to the next internal node which might have keys $(22, 27, 35)$. We do something similar at leaves as well to find the correct value.

Note that searching does not acquire any locks.

#### Insertion Algorithm

To insert a key $k$ into a B-link tree, we begin by traversing the tree from root to leaf in exactly the same way as we did for the search algorithm. We walk downwards and rightwards and do not acquire locks. One difference is that we maintain a stack of the rightmost visited node in each level of the tree. Later, we'll use the stack to walk backwards up the tree.

One we reach a leaf node, we acquire a lock on it and crab rightward until we reach the correct leaf node $a$. If $a$ is not full, then we insert $k$ and unlock $a$. If $a$ is full, then we split it into $a'$ (previously $a$) and $b'$ (freshly allocated). We flush $b'$ to disk and then flush $a'$ to disk. Next, we have to adjust the parent of $a'$ (formerly $a'$). We acquire a lock on the parent node and then crab rightward until we reach the correct parent node. At this point, we repeat our procedure upwards through the tree.

At worst, we hold three locks at a time.

#### Correctness Proof

To prove that the B-link tree works as we intend, we have to prove three things:

 - First, we have to prove that multiple threads operating on a B-link tree cannot deadlock. This is straightforward. If we totally order nodes bottom-to-top and left-to-right, then threads always acquire locks according to this total order.
 - Second, we have to prove that whenever a node modifies a B-link tree, the B-link tree still appears like a valid tree to all nodes except the modifying thread. Again, this is straightforward. The insertion procedure only makes three writes to disk.
   - Writing to a node that is not full clearly does not invalidate the tree.
   - Writing a newly allocated $b'$ node does not affect the tree because there are not any pointers to it.
   - Writing $a'$ atomically transitions the tree from one legal state to another.
 - Finally, we have to ensure that concurrently executing operations do not interfere with one another. See paper for proof (it's complicated).

#### Deletion
B-link trees punt on deletion. They simply let leaf nodes get underfull and periodically lock the whole tree and reorganize it if things get too sparse.

# Improving Word Representations via Global Context and Multiple Word Prototypes

## Introduction

* This paper pre-dated papers like Glove and Word2Vec and proposed an architecture that
    * combines local and global context while learning word embeddings to capture the word semantics.
    * learns multiple embeddings per word to account for homonymy and polysemy.
* [Link to the paper](http://www.aclweb.org/anthology/P12-1092)

## Global Context-Aware Neural Language Model

### Training Objective

* Given a word sequence *s* (local context) and a document *d* in which the sequence occurs (global context), learn word representations while learning to discriminate the last correct word in *s* from other words.
* *g(s, d)* - scoring function giving liklihood of correct sequence.
* *g(s<sup>w</sup>, d)* - scoring function giving liklihood of last word in *s* repalced by a word *w*.
* Objective - *g(s, d)* > *g(s<sup>w</sup>, d)* + 1 for any other word *w*.

### Architecture

* Two scoring components (neural networks) to capture:
    
    * Local Context
        * Map word sequence *s* into an ordered list of vectors *x = [x<sub>1</sub>, ..., x<sub>m</sub>]*.
        * *x<sub>i</sub>* - embedding corresponding to *i<sup>th</sup>* word in the sequence.
        * Compute local score *score<sub>l</sub>* by using a neural network (with one hidden layer) over *x*.
        * Preserves word order and syntactic information.
    * Global Context
        * Map document *d* to an ordered list of word embeddings, *d = (d<sub>1</sub>, ..., d<sub>k</sub>)*.
        * Compute *c*, the weighted average of all word vectors in document.
        * The paper uses *idf* score for weighting the documents.
        * *x = * concatenation of *c* and vector of the last word in *s*.
        * Compute global score *score<sub>g</sub>* by using a neural network (with two hidden layers) over *x*.
        * Similar to bag-of-words features.
    *score = score<sub>l</sub> + score<sub>g</sub>*
    * Train the weights of the hidden layers and the word embeddings.

### Multi-Prototype Neural Language Model

* Words can have different meanings in different contexts which are difficult to capture when we train only one vector per word.
* Solution - train multiple vectors per word to capture the different meanings.
* Approach
    
    * Gather all the fixed-sized context windows for all occurrences of a given word.
    * Find the context vector by performing weighted averaging of all the words in the context window.
    * Cluster the context vectors using spherical k-means.
    * Each word occurrence in the corpus is re-labeled to its associated cluster.
    * To find similarity between a pair of words *(w, w')*:
        * For each possible cluster of *i* and *j* corresponding to the words *w* and *w'*, find distance between cluster centers for *i* and *j* and weight them by the product of probabilities of *w* belonging to *i* and *w'* belonging to *j* given their respective contexts.
        * Average the value over the *k<sup>2</sup>* pairs.

## Training
    
* Dataset
  * Wikipedia corpus

* Parameters
  * 10-word windows
  * 100 hidden units
  * No weight regularization
  * 10 different word embeddings learnt for words having multiple meanings.

## Evaluation

* Dataset
  * WordSim-353 
      * 353 pairs of nouns
      * words represented without context
      * contains human similarity judgements on pair of words
  * The paper contributed a new dataset
      * captures human similarity judgements on pair of words in the context of a sentence
      * consists of verbs and adjectives along with nouns
      * for details on how the dataset is constructed, refer the paper

* Performance
  * Proposed model achieves higher correlation to human scores than models using only the local or global context.
  * Performance can be improved by removing the stop words.
  * Using multi-prototype approach (multiple vectors for the same word) benefits the model on the tasks where the context is also given.

## Comments

* This work predated the more general word embedding models like [Word2Vec](https://gist.github.com/shagunsodhani/176a283e2c158a75a0a6) and [Glove](https://gist.github.com/shagunsodhani/efea5a42d17e0fcf18374df8e3e4b3e8). While this model performs good at intrinsic evaluation tasks like word similarity, it is outperformed by the more general and recent models on downstream tasks like NER. 

This paper discusses some amazing results. The goal is to learn how to count by end-to-end training. The network input is an image and the output is a count of the objects inside it. They do not perform any direct training using the locations of the objects in the image. 

The reason for avoiding direct training is that labeled data is expensive. Employing a surrogate objective ,such as the count of items in the image, is much cheaper and makes more sense because it is the goal of the system we want to learn. This paper states that it is possible! The discuss experiments on two datasets; one of MNIST digits placed in an image and one with the UCSD Pedestrian Database.  

The network description seems to be general and they don't report any special constraints on the design  `"We consider networks of two or more convolutional layers followed by one or more fully connected layers. Each convolutional layer consist of several elements: a set of convolutional filters, ReLU non-linearities, max pooling layers and normalization layers."` and `"We use a five layers architecture CNN with two convolutional layers followed by three fully connected layers"`. They provide these two tables for their designs:

$$\begin{array}{c|c|c|c}
 Conv1 &  Conv2 & FC1 & FC2  \\ \hline
10\text{x}15\text{x}15 & 10\text{x}3\text{x}3 & 32 & 6 \\
\text{x2 pool} & \text{x2 pool} & & \\ \hline
\end{array}\\
\text{CNN arch for numbers}$$

$$
\begin{array}{c|c|c|c|c}
 Conv1 &  Conv2 & FC1 & FC2 & FC3 \\ \hline
8\text{x}9\text{x}9 & 8\text{x}5\text{x}5 & 128 & 128 & 25 \\
\text{x2 pool} & \text{x2 pool} & & \\ \hline
\end{array}\\
\text{CNN arch for people}$$

They state that they use a method based on hypercolumns \cite{1411.5752} but the description is not clear at all: `" Starting with the hypercolumn representation
on the last layer we cluster the resulting hypercolumns
into a set of prototypes using an online k-means
algorithm. Then, a MIL approach with positive and negative
instances with the concept of interest is used."`

![](https://i.imgur.com/x2q3E9Y.png)

Interesting work but I wish it was a longer paper with more details. This paper doesn't really give me enough information to reproduce it.