Title: SPARSE AND STRUCTURED VISUAL ATTENTION

Abstract: Visual attention mechanisms have been widely used in image captioning models. In this paper, to better link the image structure with the generated text, we replace the traditional softmax attention mechanism by two alternative sparsity-promoting transformations: sparsemax and Total-Variation Sparse Attention (TVMAX). With sparsemax, we obtain sparse attention weights, selecting relevant features. In order to promote sparsity and encourage fusing of the related adjacent spatial locations, we propose TVMAX. By selecting relevant groups of features, the TV-MAX transformation improves interpretability. We present results in the Microsoft COCO and Flickr30k datasets, obtaining gains in comparison to softmax. TV-MAX outperforms the other compared attention mechanisms in terms of humanrated caption quality and attention relevance.

1. INTRODUCTION:

The goal of image captioning is to generate a fluent textual caption that describes a given image (Farhadi et al., 2010; Kulkarni et al., 2011; Vinyals et al., 2015; Xu et al., 2015) . Image captioning is a multimodal task: it combines text generation with the detection and identification of objects in the image, along with their relations. While neural encoder-decoder models have achieved impressive performance in many text generation tasks (Bahdanau et al., 2015; Vaswani et al., 2017; Chorowski et al., 2015; Chopra et al., 2016) , it is appealing to design image captioning models where structural bias can be injected to improve their adequacy (preservation of the image's information), therefore strengthening the link between their language and vision components.

State-of-the-art approaches for image captioning (Liu et al., 2018a; b; Anderson et al., 2018; Lu et al., 2018) are based on encoder-decoders with visual attention. These models pay attention either to the features generated by convolutional neural networks (CNNs) pretrained on image recognition datasets, or to detected bounding boxes. In this paper, we focus on the former category: visual attention over features generated by a CNN. Without explicit object detection, it is up to the attention mechanism to identify relevant image regions, in an unsupervised manner.

A key component of attention mechanisms is the transformation that maps scores into probabilities, with softmax being the standard choice (Bahdanau et al., 2015) . However, softmax is strictly dense, i.e., it devotes some attention probability mass to every region of the image. Not only is this wasteful, it also leads to "lack of focus": for complex images with many objects, this may lead to vague captions with substantial repetitions. Figure 1 presents an example in which this is visible: in the caption generated using softmax (top), the model attends to the whole image at every time step, leading to a repetition of "bowl of fruit." This undesirable behaviour is eliminated by using our alternative solutions: sparsemax (middle) and the newly proposed TVMAX (bottom).

In this work, we introduce novel visual attention mechanisms by endowing them with a new capability: that of selecting only the relevant features of the image. To this end, we first propose replacing softmax with sparsemax (Martins & Astudillo, 2016) . While sparsemax has been previously used in NLP for attention mechanisms over words, it has never been applied to computer vision to attend over image regions. With sparsemax, the attention weights obtained are sparse, leading to the selection (non-zero attention) of only a few relevant features. Second, to further encourage the weights of related adjacent spatial locations to be the same (e.g., parts of an object), we introduce a new attention mechanism: Total-Variation Sparse Attention (which we dub TVMAX), inspired by prior work in structured sparsity (Tibshirani et al., 2005; Bach et al., 2012) . With TVMAX, sparsity is allied to the ability of selecting compact regions. According to our human evaluation experiments, Figure 1 : Example of captions generated using softmax (top), sparsemax (middle) and TVMAX attention (bottom). Shading denotes the attention weight, with white for zero attention. The darker the green is, the higher the attention weight is. The full sequences are presented in Appendix C. this leads to better interpretability, since the model's behaviour is better understood by looking at the selected image regions when a particular word is generated. It also leads to a better selection of the relevant features, and consequently to the improvement of the generated captions.

This paper introduces three main contributions::

• We propose a novel visual attention mechanism using sparse attention, based on sparsemax (Martins & Astudillo, 2016) , that improves the quality of the generated captions and increases interpretability.

• We introduce a new attention mechanism, TVMAX, that encourages sparse attention over contiguous 2D regions, giving the model the capability of selecting compact objects. We show that TVmax can be evaluated by composing a proximal operator with a sparsemax projection, and we provide a closed-form expression for its Jacobian. This leads to an efficient implementation of its forward and backward pass.

• We perform an empirical and qualitative comparison of the various attention mechanisms considered. We also carry out a human evaluation experiment, taking into account the generated captions as well as the perceived relevance of the selected regions.

2. SELECTIVE VISUAL ATTENTION:

Attention mechanisms have the ability to select the relevant features, in this case spatial locations. This requires a mapping from importance scores to a distribution,

z ∈ R k → p ∈ k , where k := p ∈ R k | k i=1 p i = 1

, p 0 denotes the simplex (the set of all probability distributions over k values). The standard choice for this mapping is softmax, defined as:

[softmax(z)] i = exp(z i ) j exp(z j )

.

(1)

However, as softmax is strictly positive, its output is dense. Thus, the model must pay some attention to the whole image and, consequently, assign lower attention weights to the relevant regions. This motivates our proposed selective visual attention mechanisms, which, by being sparse, are able to better isolate the relevant image regions.

2.1. SPARSEMAX:

To achieve selective capabilities, we propose the use of sparsemax (Martins & Astudillo, 2016) , a sparse mapping consisting in the Euclidean projection of z onto the probability simplex:

EQUATION

which allows to obtain sparse outputs with a small increase in complexity. Output sparsity is an attractive property for attention mechanisms, since some features do not provide relevant information for the current prediction. In the image captioning case, using sparsemax allows focusing only on the spatial locations of the image that are relevant to the word being generated, assigning zero attention weight to all other regions.

2.2. SPARSE AND STRUCTURED VISUAL ATTENTION:

To generate descriptive captions, the model should identify the objects present in the image. Thus, when generating object-related words, the attention mechanism should assign high weights to the regions of the image containing the object. However, sparsemax is unstructured and index-invariant, leading it to select discontinuous regions. To overcome this, we propose a new visual attention mechanism, TVMAX. TVMAX is a non-trivial generalization of fusedmax (Niculae & Blondel, 2017) , a transformation based on fused lasso, to the 2D case. To this end, we first extend fusedmax even more generally, to arbitrary graphs.

2.2.1. GENERALIZED FUSED LASSO:

Let w ∈ R k , and let I = {1, . . . , k}. Consider a graph over I defined by its edges E ⊆ I × I, where an edge between i and j means we want to encourage w i to be close to w j . For simplicity we use i ∼ j as shorthand for (i, j) ∈ E.

The generalized fused lasso penalty (Tibshirani et al., 2005) is defined as:

EQUATION

Minimizing Ω E encourages "fused" solutions, i.e., it encourages w i = w j for i ∼ j. In particular, its proximal operator1 can be seen as a fused signal approximator, seeking a vector w that approximates z well (in terms of Euclidean distance) and that is encouraged to be fused:

EQUATION

Computing the value of prox λΩ E is non-trivial in general (Xin et al., 2016) , but for certain edge configurations, described below, efficient algorithms exist.

• If E forms a chain, i.e. i ∼ j ⇐⇒ i = j -1, the problem is called 1D total variation and can be solved in O(k) time using the taut string algorithm (Davies & Kovac, 2001; Barbero & Sra, 2014) . We use the quasilinear algorithm of Condat (2013) , which is very fast in practice.

• If the indices are aligned on a 2D grid, as in an image, and i ∼ j holds iff. j is to the right or immediately below i, the problem is called 2D total variation. Unlike the 1D case, exact algorithms are not available. However, for an input of size a × b, it is possible to split the penalty into a column-wise and b row-wise 1D problems. We may then apply a number of iterative methods, for instance proximal Dykstra (Barbero & Sra, 2014 ).2 

2.2.2. TVMAX:

TVMAX combines 2D total variation (TV2D) regularization with sparsemax. This way it promotes sparsity and encourages the attention weights of adjacent spatial locations to be the same, selecting contiguous regions of the image. TVMAX is defined as follows: Definition 1 (TVMAX). Let z ∈ R k , such that z's indices can be decomposed into rows and columns. The TVMAX transformation is defined as

EQUATION

)

where λ is an hyper-parameter controlling the amount of fusion (λ = 0 recovers sparsemax) and Ω T V 2D is a 2D total variation penalty.

Note that Eq. 5 differs from Eq. 4 in which the variable p is further constrained to lie in the probability simplex. We show next how the forward and backward passes can be efficiently computed.

2.2.3. GENERALIZED FUSED SPARSE ATTENTION:

To construct generalized fused sparse attention, we follow Niculae & Blondel (2017) and define

EQUATION

This can be seen as a constrained fused lasso approximator, because the solution p must be a probability distribution vector. While the optimization function is very similar to Eq. 4, the additional constraint that p ∈ increases complexity. Fortunately, the following result holds: Proposition 1 (Computing generalized fusedmax).

EQUATION

)

The proof is given in Appendix A.2.

Proposition 1 also provides a shortcut for deriving the Jacobian of generalized fusedmax via the chain rule: denoting by J F the Jacobian of prox λΩ E , we have

∂ gfusedmax ∂z = J gfusedmax = J sparsemax (prox λΩ E (z))J F (z).

As we already know how to compute J sparsemax (Appendix A.1), we may concentrate our effort on deriving the simpler J F (Eq. 9). Proposition 2 (Group-wise characterization of prox λΩ E ). Let w := prox λΩ E , and denote by G i the set of indices fused to w i in the solution, G i may be defined recursively:

1. i ∈ G i for all i, and 2. j ∈ G i if there exists m ∈ G i such that m ∼ j and w m = w j .

Define s ij = sign(w i -w j ). Then, the solution has the expression

w i = 1 |G i | j∈Gi     z j + m∼j m ∈Gi λs mj - j∼m m ∈Gi λs jm     . (8)

Proposition 2 shows how to easily compute a generalized Jacobian of gfusedmax: since small perturbations in z never change the groups G i nor the signs of across-group differences s ij , differentiating Eq. 8 yields

EQUATION

This generalizes Lemma 1 of Niculae & Blondel (2017) to generalized fused lasso, with a simpler proof, given in Appendix A.3.

2.2.4. COMPUTATION:

As we show in Proposition 1, computing TVMAX's forward pass can be done by chaining efficient algorithms for TV2D and sparsemax.

From Eq. 7 we have that TVMAX's Jacobian can be computed as

J TVMAX = J sp (prox λΩ T V 2D (z))J tv (z)

, where J sp is the sparsemax's Jacobian and J tv is the Jacobian of the Total Variation proximal operator. 3 As derived in Proposition 2, (J tv ) i,j = 1 /nij if i and j are fused in a group with n ij elements, and 0 otherwise. The backward pass intuitively involves "spreading" the credit assigned to one image location evenly across all locations fused with it. This can be implemented by Algorithm 1 in O(k+N g log k) where N g is the number of groups of fused positions. In the worst case, when there are no positions fused, the complexity is O(k + k log k). This algorithm is inspired by flood filling algorithms (Burtsev & Kuzmin, 1993) .

Algorithm 1 TVMAX backward pass (Jacobian-vector products) 

1 Input: p = TVMAX(z), dp ∈ R k . 2 Output: dz = J TVMAX (dp) ∈ R k # chain rule 3 Initialize: N ← ∅ # neighbours stack 4 V ← ∅ # visited positions 5 G ← ∅ # current

if pi,j = pi 0 ,j 0 then # check if element is fused 13 G ← G ∪ {(i, j)}, V ← V ∪ {(i,

3. IMAGE CAPTIONING MODEL:

To compare the proposed attention mechanisms, we use a straight-forward simple encoder-decoder model with visual attention, inspired by Liu et al. (2018a) . The model is sketched in Figure 2 .

Given an image, we use a residual CNN pretrained on ImageNet (He et al., 2016; Russakovsky et al., 2014) to get a feature map with spatial dimension of size 8 × 8 and channel dimension of size 2048, that go through a fine-tuned feedforward layer yielding g = 512 feature maps. The visual feature matrix V = [v 1 , v 2 , . . . , v k ], with v i ∈ R g and k = 64 = 8 × 8, contains the image information used to generate the corresponding caption. Following Liu et al. (2018a) , we use input and output attention to select the relevant features for the current generation. To generate the word at position t, the input attention, α t , is computed using the LSTM's previous hidden state, h t-1 ∈ R d . First, a similarity score z t,i , i ∈ {1, . . . , k}, is computed between h t-1 and the i th image cell via a feedforward transformation (Bahdanau et al., 2015) , as z t,i = w tanh(affine([v i ; h t-1 ])), for all k image cells. Then, α t is obtained by normalizing the k-dimensional vector of scores z t with softmax, α t = softmax(z t ). Using these attention weights, a vector representation of the image to be used as input of the LSTM, is obtained, s t = V α t . The output attention α t , is computed in the same way as above, but applied to the current LSTM hidden state h t , instead of h t-1 , and normalized with the different proposed transformations. This produces output visual features s t = V α t , which are passed through a feedforward layer to yield the image representation r t = tanh(affine( s t )). Finally, the predictive probability of the next word is: 

P (y t |

4. EXPERIMENTS:

Settings. The input images are resized to 256 × 256 before going through the residual CNN and the feature maps obtained have a size of 8 × 8. We use an LSTM hidden size of d = 512 and a word embedding size of 256, for all models. The models were trained for 50 epochs using the Adam optimizer (Kingma & Ba, 2014) with a learning rate of 0.0001 and a decay of 0.8 and 0.999 for the first and second momentum, respectively. After the 10 th epoch, the learning rate starts decaying with a decay factor of 0.99. For TVMAX, we set λ = 0.01.

Datasets and Metrics. We report our results on the Microsoft COCO (MSCOCO) and Flickr30k datasets. MSCOCO is composed of 113,287 images of common objects in context while Flickr30k consists in 31,000 pictures of people involved in everyday activities and events. Each image is annotated with 5 captions. We use the split proposed by Karpathy & Fei-Fei (2015) , which stipulates equal validation and test sizes of 5,000 images (MSCOCO) and 1,000 (Flickr30k). The metrics we report are SPICE (Anderson et al., 2016) , CIDEr (Vedantam et al., 2015) , longest common subsequence ROUGE, (denoted ROUGE L ; Lin, 2004), 1-to 4-gram BLEU (denoted BLEU 4 ; Papineni et al., 2002) , and METEOR (Banerjee & Lavie, 2005) . To investigate whether selective attention alleviates repetition, we also measure the n-gram repetition metric REP (Malaviya et al., 2018) . Automated metrics. As can be seen in table 1, overall sparsemax and TVMAX attention mechanisms achieve better results when compared with softmax, indicating that the use of selective attention leads to better captions. This improvement does not come at a high computational cost: at inference time, models using TVMAX and sparsemax are only 1.3x and 1.1x slower than softmax. Moreover, for TVMAX, automatic metrics results are slightly worse than sparsemax but still superior to softmax on MSCOCO and similar on Flickr30k. We show next that this is compensated with fewer repetitions and higher scores in the human evaluation of the captions and attention relevance. Human rating. The caption evaluation consisted in attributing a score from 1 to 5 to the caption of each model while the attention evaluation consisted in scoring the relevancy of the attended areas, from 1 to 5, when generating the non stop words of the captions. A full description of the human assessment can be found in Appendix B.

Despite performing slightly worse than sparsemax under automated metrics, TVMAX outperforms sparsemax and softmax in the caption human evaluation and the attention relevance human evaluation, reported in Table 2 . The superior score on attention relevance shows that TVMAX is better at selecting the relevant features and its output is more interpretable. Additionally, the better caption evaluation results demonstrate that the ability to select compact regions induces the generation of better captions. We next explore possible explanations for the TVMAX superior results.

Repetition. Figure 1 illustrates that softmax attention is prone to spuriously repeating references to the same object. Selective attention mechanisms like sparsemax and especially TVMAX reduce repetition, as measured by the REP metric reported in Table 1 . This expected success can be attributed to the sparsity of the attention weights distribution and to the ability to select compact regions exclusively and can be one of the causes of the human evaluation results. This happens even though TVMAX generates longer sentences than sparsemax and softmax (9.5 against 9.0 words on average) and shows the benefit of promoting structured and sparse attention simultaneously. To corroborate our intuition that sparsity leads to less repetition, we measured the Jensen-Shannon divergence (JS) between the attention distributions for each step of the generation of the captions correspondent to the images of the MSCOCO test set. The mean JS values are 0.12, 0.29, and 0.34 for softmax, sparsemax, and TVmax, respectively. This shows that sparsity leads to less similar attention distributions along the generation of the captions and, consequently, to less repetitions.

Object detection. Using the MSCOCO object detection ground truth, we compared the percentage of objects present in the image that are referred to in the captions, using each attention mechanism. With TVMAX 28.2% of the reference objects are referred, against 27.5% and 27.4% for sparsemax and softmax, repectively. This shows that promoting high attention to groups of spatial locations of the image leads to a more precise identification of the objects.

Sparsity. The average image area that receives zero attention is 34% for sparsemax and 25% for TVMAX. To illustrate where the models attend to, we display the output attention in Figures 1 and 3 . As expected, softmax weights are spread widely across the image, ending up missing the relevant regions. In contrast, sparsemax and TVMAX weights are zero for the non-relevant spatial locations.

Qualitative comparison. As the image of Figure 1 contains various similar objects, the softmax model (top) generates a incoherent, repetition-laden caption. In contrast, the sparsemax (middle) and TVMAX (bottom) models better identify the relevant parts of the image, generating coherent and descriptive captions. Moreover, the groups obtained with TVMAX are clearly visible and more aligned to object boundaries, offering better interpretability, as revealed by human attention assessment. In Figure 3 it can also be noticed that with TVMAX (bottom) the model correctly identified "a group of people" instead of "a soccer player" as with sparsemax (middle) and softmax (top). This indicates its superior ability to correctly define the relevant groups of features and that this ability leads to improved captions.

5. RELATED WORK:

Image captioning. In the last years, neural models with visual attention mechanisms have been receiving increased interest. Several researchers have been studying diverse attention mechanisms in order to refine visual information for image captioning. Xu et al. (2015) proposed the use of hard attention, which only attends to one region at each step. However, to generate descriptive captions the model should, often, focus on more than one region. In addition, hard attention is non-differentiable, requiring imitation learning or Monte Carlo policy gradient approximations. Anderson et al. (2018) proposed bottom-up attention, using an object detection model designed to identify bounding boxes of objects, and top-down attention, selecting the relevant bounding-boxes. Wang et al. (2019) proposed an hierarchical attention network composed by a patch detector, object detector, and concept detector. Using object detection models is less demanding on the attention mechanism, since it only has to select the boxes the model should attend to. However, such models are limited by the bounding boxes position's accuracy. Gao et al. (2019) introduced a deliberate attention network to refine the attended visual features. Yet, the attention distribution remained dense.

Sparse attention. In several tasks only a few features are relevant for the current prediction. This can be attained when using sparse attention. Various prior works have proposed sparse attention mechanisms with promising results, (Xu et al., 2015; Martins & Astudillo, 2016; Malaviya et al., 2018; Peters et al., 2019) . Niculae & Blondel (2017) proposed 1D fusedmax, which incorporates the fused lasso, so that adjacent words are encouraged to have the same attention weight. In this work, the authors were able to improve interpretability without sacrificing performance, obtaining superior results on textual entailment and summarization. We derive a generalized fused attention mechanism, extending 1D fusedmax.

6. CONCLUSIONS AND FUTURE WORK:

We propose using sparse and structured visual attention, in order to improve the process of selecting the features relevant to the caption generation. For that, we used sparsemax and introduced TVMAX.

Results on the image captioning task, show that the attention mechanism is able to select better features when using sparsemax or TVMAX. Furthermore, in the human assessment and attention analysis we see that the improved selection of the relevant features as well as the ability to group spatial features lead to the generation of better captions, while improving the model's interpretability.

In future work, TVMAX attention can be applied to other multimodal problems such as visual question answering. It can also be applied in other tasks for which we have prior knowledge of the data's stucture, for instance graphs or trees.

A FORWARD AND BACKWARD PASS OF 2D FUSEDMAX ATTENTION.

A.1 PRELIMINARIES:

The proximal operator of a function f : R d → R ∪ {∞} is defined as

EQUATION

)

and it is guaranteed to have a unique solution, thanks to the strong convexity of the Euclidean distance.

The indicator function of a set C ⊂ R d is the function

EQUATION

The projection onto a convex set C ⊂ R d is defined as

EQUATION

showing that the proximal operator can be seen as a generalization of projection.

The sparsemax attention mapping (Martins & Astudillo, 2016) is the projection onto the simplex,

EQUATION

A necessary component for using sparsemax for attention is its Jacobian, the matrix of its partial derivatives (J sparsemax ) i,j = ∂ sparsemax(z)i ∂zj . Martins & Astudillo (2016) derive its expression

EQUATION

where s j = 1 if sparsemax(z) j > 0 and s j = 0 otherwise.

A.2 PROOF OF PROPOSITION 1:

Proof. This result is a slight extension of Proposition 2 in Niculae & Blondel (2017) , and also follows from Corrolary 4 of Yu (2013) , by taking f = ι , and noting that ι is symmetric: if p ∈ , then any vector p obtained by permuting p is also in , because its values remain nonnegative and sum to 1.

A.3 PROOF OF PROPOSITION 2:

Let w := prox λΩ E , and denote by G i the set of indices fused to w i in the solution. Define s ij = sign(w i -w j ).

Proof. The subgradient optimality conditions of Eq. 4 are: (Friedman et al., 2007) w

EQUATION

)

where

t ij = sign(w i -w j ) if w i = w j , otherwise t ij is a free variable in [-1, 1].

We focus on a single group G = G i , dropping the index i for brevity. Within a fused group, the solution is constant, i.e., w j = w for j ∈ G. We separate the sums in Eq. 16 according to whether k ∈ G or not, and move the "constant" terms to the right hand side, yielding the system w + 

Summing up the Eq. 17 over all j ∈ G, we observe that for any k ∈ G, the term λt jk appears twice with opposite signs. Thus, (18)

Dividing by |G| gives exactly Eq. 8. This reasoning applies to any group G i .

B HUMAN EVALUATION DESCRIPTION:

To perform the human evaluation firstly 100 images were randomly selected from the test set of the MSCOCO dataset (using the split proposed by Karpathy & Fei-Fei (2015) ). For each of the selected images, the human evaluators selected a score from 1 to 5 for the captions generated by the models using softmax attention, sparsemax attention, and TVMAX attention. They were also asked to evaluate whether the models attend to the relevant regions of the image when generating a certain word. For that they observed the attention plots corresponding to the non stop words of the caption of each of the models. While in Figures 1 and 3 , 4, and 5 we emphasized sparsity with a hard white mask, for the human evaluation the sparse regions of the attention plots were simply fully transparent, to avoid biasing the evaluators. The possible scores were also between 1 and 5. The 100 images were judged by 6 persons both for the captions evaluation and attention evaluation.

The order of the captions and attention plots was randomly chosen for each image.

With these scores, we computed the mean of the captions evaluation scores and the mean of the attention relevance evaluation scores. The results are reported in Table 2 .

C ADDITIONAL ATTENTION VISUALIZATION and TVMAX attention (bottom). The captions are "A bowl of fruit and a bowl of fruit", "A bowl of fruit and oranges on a table" and "A bowl of oranges and a banana on a table".

Figure 5 : Example generated captions using softmax attention (top), sparsemax attention (middle) and TVMAX attention (bottom). The captions are "A soccer player is running to the base", "A soccer player is running to the field" and "A group of people playing soccer on a field".

:

The proximal operator is defined in Eq. 11 of Appendix A.1.

We use the implementation readily available in the copt library, available at http://openopt. github.io/copt/.

J tv is a special case of J F, when using the graph E that consists in a 2D grid.

Figures and Tables:

Figure 2: Diagram of the caption generation network.

Figure 3: Example of captions generated using softmax (top), sparsemax (middle) and TVMAX attention (bottom). Shading denotes the attention weight, with white for zero attention. The darker the green is, the higher the attention weight is. The full sequences are presented in Appendix C.

Figure 4: Example generated captions using softmax attention (top), sparsemax attention (middle)and TVMAX attention (bottom). The captions are "A bowl of fruit and a bowl of fruit", "A bowl of fruit and oranges on a table" and "A bowl of oranges and a banana on a table".

Automatic evaluation of caption generation on MSCOCO and Flickr30k.

Table content: <table><tr><td/><td colspan="2">MSCOCO</td><td/><td colspan="2">Flickr30k</td><td/></tr><tr><td/><td colspan="3">SPICE CIDER ROUGEL BLEU4 METEOR REP↓</td><td colspan="3">SPICE CIDER ROUGEL BLEU4 METEOR REP↓</td></tr><tr><td>softmax</td><td>18.4 0.967 52.9</td><td>29.9</td><td>24.9 3.76</td><td>13.5 0.443 44.2</td><td>19.9</td><td>19.1 6.09</td></tr><tr><td colspan="2">sparsemax 18.9 0.990 53.5</td><td>31.5</td><td>25.3 3.69</td><td>13.7 0.444 44.3</td><td>20.7</td><td>19.3 5.84</td></tr><tr><td>TVMAX</td><td>18.5 0.974 53.1</td><td>29.9</td><td>25.1 3.17</td><td>13.3 0.438 44.2</td><td>20.5</td><td>19.0 3.97</td></tr></table>

Human evaluation results with different attention mechanisms on MSCOCO.

Table content: <table><tr><td/><td>CAPTION (1-5)</td><td>ATTENTION RELEVANCE (1-5)</td></tr><tr><td>softmax</td><td>3.50</td><td>3.38</td></tr><tr><td>sparsemax</td><td>3.71</td><td>3.89</td></tr><tr><td>TVMAX</td><td>3.87</td><td>4.10</td></tr></table>

Peer review (iclr2020):
This paper studies the problem of applying attention to the problem of image captioning. To this end the authors first apply full attention where the probabilities are computed using softmax before applying the recently proposed Sparsemax - which essentially computes probabilities from scores by performing a projection on to the probability simplex. The authors then propose a variant of Sparsemax which they call TVMax, which has the property that it encourages assigning probability weights to contiguous regions in 2D space unlike Sparsemax which has no such incentive. The main idea is to augment the Sparsemax projection loss with a Lasso like penalty which penalizes assigning different attention probabilities to contiguous regions in the image. The authors then compare their TVMax approach with softmax and Sparsemax attention for image captioning and show improvements on the MSCOCO and Flickr datasets. The idea of applying additional structural constraints on the sparsity structure induced by Sparsemax is a cool idea, and I like the idea of incentivizing contiguous pixels to have similar attention probabilities. Sparse attention patterns seems like an important direction of research with the motivation of either 1) improving generalization over full attention or 2) scaling to inputs of length where full attention is not feasible. This seems like a good progress in the first direction. The major weakness I see in this work is that the authors only limited their experiments to image captioning. It would be interesting to see if their approach could benefit other tasks such as machine translation, image generation etc. The other issue with their approach is that it doesn*t seem to scale well - if I understand correctly their algorithm takes O(n^2logn) for sequence length n. The other issue potentially could be weak baselines since the authors use an LSTM for their caption generation network instead of Transformer. [Edit: After going through reviewer discussion, I updated my score to reject. I am not convinced of the motivation for sparse attention unless it is for long sequences, since otherwise the regular softmax should be able to assign 0*s to the un-needed items. Moreover, for generalization one can use attention dropout which is simpler instead.]