Sparse and Structured Visual Attention
Authors: Pedro Henrique Martins
Vlad Niculae
Zita Marinho
André F.T. Martins
Venue:  (2020)
Keywords: Sparsity
attention
structured attention
total variation
fused lasso
image captioning

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 TVmax transformation improves interpretability. We present results in the Microsoft COCO and Flickr30k datasets, obtaining gains in comparison to softmax.  TVmax outperforms the other compared attention mechanisms in terms of human-rated caption quality and attention relevance.

Under review as a conference paper at ICLR 2020
SPARSE AND STRUCTURED VISUAL ATTENTION
Anonymous authors
Paper under double-blind review
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 transformations: sparsemax and Total-Variation Sparse Attention (TVMAX), With sparsemax, we obtain sparse attention weights, selecting relevant features. In or- der to promote sparsity and encourage fusing of the related adjacent spatial lo- cations, we propose TVMAX. By selecting relevant groups of features, the TV- MAX transformation improves interpretability. We present results the Microsoft COCO and Flickr30k datasets, obtaining gains in comparison to softmax. TV- MAX outperforms the other compared attention mechanisms in terms of human- rated caption quality and attention relevance.
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 al. 2015). Image captioning is a multimodal task: it combines text generation with the detection and identification of objects the
image, along with their relations. While neural encoder-decoder models have achieved impressive
performance in many text generation tasks (Bahdanau et al. [0015] Vaswani et al. 2017 Chorowski
al. 2015 Chopra al.) 2016), 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
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 at- tention over features generated by 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 strietly dense, i.e., it devotes some attention probability mass to every region of the image. Not only is this wasteful, also leads to "lack of focus": : for complex images with many objects, this may lead to vague captions with substantial repetitions. Figure [ 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 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 new capabil- ity: 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 selec- tion (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 at- tention mechanism: Total- Variatio Sparse Attention (which work in structured sparsity (Tibshirani et al., 22055 Bach et al., 2012). With TVMAX, sparsity is allied to the ability of selecting compact regions. According to our human evaluation experiments,
dub TVMAX) inspired by prior

---

Under review as a conference paper at ICLR 2020
tru
and
Irust
boo
Seanges
tabtc
boad
ocanges
and
Danana
on
lable
0.000
0.025
0.050
0.075
0.100
0.125
0.150
Figure 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
this leads to better interpretability, since the model's behaviour is better understood by looking the selected image regions when a particular word is generated. also leads to a better selection of the relevant features, and consequently the improvement of the generated captions.
This paper introduces three main contributions:
We propose a novel visual attention mechanism using sparse attention, based on sparse- max (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 T'mmx can evaluated by composing proximal operator with a sparsemax projection, and we provide closed-form expression for its Jacobian. This leads 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 generated captions as well as the perceived relevance of the selected regions.
human evaluation experiment, taking into account the
2 SELECTIVE VISUAL ATTENTION
Attention mechanisms have the ability seleet the relevant features, in this case spatial locations. This requires a mapping from importance scores to a distribution, z E T + E A*, where
* p E & E Pj 1, > 0} denotes the simplex (the all probability distributions over l values). The standard choice for this mapping is softmax, defined as:
exp(z;)
[softmax(2)]+ Σ, exp(2;)
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

---

Under review as a conference paper at ICLR 2020
2.1 SPARSEMAX
To achieve selective capabilities, propose the of sparsemax (Martins & Astudillo 2016). sparse mapping consisting in the Euclidean projection of z onto the probability simplex:
1 sparsemax(z) := arg min 2 -1p ==122 PEA
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 informa- tion 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 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). transformation based on fused lasso, to the 2D case. To this end, we first extend fusedmax even more generally, to arbitrary graphs.
2.2. GENERALIZED FUSED LASSO
Let E R and let I {1.... ........ k}. Consider graph I defined by its edges E S I I, where an edge between and j means we want to encourage wy to be close to wj. For simplicity we i ~ shorthand for (i.j) E.
The generalized fused lasso penalty (Tibshirani et al. 2005 is defined as:
[F(w) Σ ww wyy
Minimizing DE encourages "fused" solutions, i.e., it encourages w; = w for i ~ j. In particu- lar, its proximal operato can be seen as fused signal approximator, seeking a vector w that approximates well (in terms of Euclidean distance) and that is encouraged to be fused:
prox (z) = arg min 7 w 21 (ww
wERd
Computing the value of proxxng non-trivial general (Xin et al. 2016), but for certain edge configurations, described below, efficient algorithms exist.
If E forms a chain, i.c. i < j-j--, the problem is called 1D total variation and can be solved in O(k) time using the laut 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 2D grid, in image, and i ~ holds iff. is to the right or immediately below i, the problem is called 2D total variation. Unlike the 1D case, exact algorithms not available. However, for input of size b, is possible to split the penalty into a column- wise and row-wise 1D problems. We may then apply number of iterative methods, for instance proximal Dykstra (Barbero & Sra 2014
I 'The proximal operator defined Eq. Appendix A.1 We use the implementation readily available in the copt library, available at http:://oppree
github. io/copt/
3

---

Under review as a conference paper at ICLR 2020
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 imgge. TVMAX defined as follows:
Definition 1 (TVMAX), Let R& such that z's indices can be decomposed into rows and columns. The TVMAX transformation is defined as
TVMAX(2) = arg min PEΛ* 2 lpp 2112 X2 (p).
(5)
where À is an hyper-paramett controlling the amount of fusion (A = 0 recovers sparsemax) and 2D is 2D total variation penalty.
Note that Eq. 11.55dito differs from Eq. Qin which the variable p is further constrained to lie in the proba- bility simplex. We show next how the forward and backward passes be efficiently computed.
2.2.3 GENERALIZED FUSED SPARSE ATTENTION
To construct generalized fused sparse attention, we follow Niculac & Blondel (0017) and define gfusedmax (z) arg min PÊA
=13 (p
This be seen constrained fused lasso approximator, because the solution p must be prob- ability distribution vector. While the optimization function very similar to Eq. + the additional constraint that p A increases complexity. Fortunately, the following result holds: Proposition 1 (Computing generalized fusedmax).
gfusedmaxg(2) = proja (proxxne(2) (z))
The proof is given in Appendix A.2
Proposition T also provides shortcut for deriving the Jacobian of generalized fusedmax via the chain rule: denoting by JF the Jacobian of prox we have
i gfusedmaxx
Jgfusedmax sparsemax
Paaarsmax(proxxxxr (proxang (z)))=(z))
Oz
As we already know how to compute J sparsemax (Appendix A.I we may concentrate our effort on deriving the simpler F (Eq, 9).
Proposition 2 (Group-wise characterization of prox x)g) Let w = prox and denote by G; the set of indices fused to w; in the solution, G; may be defined recursively:
1. E for all i, and
2. G there exists m Ge such that j and w w...
Define 8ig sign(w; wg). Then, the solution has the expression
2j
Asmj
Asjm
(8)
G
jEG,
jowm mgG;
mgC.
Proposition2sshowe how to easily compute generalized Jacobian of gfusedmax: since small pertur- bations in never change the groups G, nor the signs of across-group differences Sij, differentiating Eq. [ yields
Owf Ozy
j G.,
J Fij
G 0,
(9)
j E G,,
This generalizes Lemma 1 of Niculae Blondel proof, given in Appendix A.3
2017
to generalized fused lasso, with a simpler
4

---

Under review as a conference paper at ICLR 2020
2.2.4 COMPUTATION
As we show in Proposition | computing TVMAX's forward pass can be done by chaining efficient algorithms for TV2D and sparsemax.
From Eq. we have that TVMAX'S Jacobian can be computed Jp Aprox (v)), where Ss is the sparsemax's Jacobian and Jtv is the Jacobian of the Total Variation proximal operator As derived Proposition 2 (Jw)a, = 1/nis i and j are fused in group with M4j elements, and 0 otherwise.
J JIVMAX
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 in Olk++N log k) where N₂ is the number of groups of fused positions. the worst case, when there are no positions fused, the complexity is OO + k log k). This algorithm is inspired by flood filling algorithms (Burtsev & Kuzmin 1993).
Algorithm MAX backward pass (Jacobian-vectr) products)
Input: p TV MAM((==)..... dp E R
2 Output: dz = J T (dp) E 1e*
# chain rule neighbours stack
Initialize:
V Vea Ø
# visited positions # current group
5
G + 2
== dw (J dp
intermediate value used for JTVaax computation
Eqs. 14and
of A.1
15
while VV < k do 8
# check if all positions have been visited get not visited position and add to neighbours stack
pick (io:jo) Jo) g V. push (o)
10
while N not empty do
11
pop (i.j) from N
# get element from neighbours stack # check if element is fused # add neighbour to group and to visited positions sun of the dow of each element of the group
12
if p., = Pio.jo then
G GUG Vu
14
8 (dw)
15
for all neighbours )") ~ (i.j) do
(i' then push (V', j") to
add not visited neighbours of (1.j) to the stack
17
if G not empty then:
18
(dz),, + 5/IG) for all (4.5) E G
compute JIvsux for elements in group G
G Ø
20
s ==0
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]
Given an image, we use a residual CNN pretrained on ImageNet (He et al. 2016 Russakovsky al. 2014) get feature map with spatial dimension of size
and channel dimension of size 2048, that go through a fine-tuned feedforward layer yielding = 512 feature maps. The visual feature matrix V [v1, :2. Uk), with v. RR. 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 select the relevant features for the current generation. To generate the word at position f, the input attention, Q4, is computed using the LSTM's previous hidden state, h E Rd. First, a similarity score 21, E (l.....kh k), is computed between h4-1 and the 7th image cell feedforward transformation (Bahdanau et al. 2015). as 24, = w Ttahh (affine(((v; h)),))), for all l image cells. Then, ar is obtained by normalizing the k-dimensional vector of scores 2 with softmax, a, = softmax(z;). Using these attention weights, a vector representation of the image to be used as input of the LSTM, is obtained,
Va,, The output attention ar, is
Jyy is special case of Jr, when using the graph F. that consists in 2D grid.
5

---

Under review as a conference paper at ICLR 2020
computed in the same way as above, but applied to the current LSTM hidden state hę, instead of h and normalized with the different proposed transformations. This produces output visual features s, Vä,, which are passed through a feedforward layer yield the image representation rt = tanh(affine(s.)) Finally, the predictive probability of the next word is:
P(ye 11:(t-1); Image) x softmax (affine((r:: softmax(affine(Irz
ha])).
(10)
Image Encoder
Image
ResNet 152
FF
V(visual features)
Input Att. (ar)
Output Att. (Gt)
h
he
LSTM
FF
Zt
Pt
caption:
Mt-1
3/+
Figure 2: Diagram of the caption generation network.
EXPERIMENTS
Settings. The input images resized to 256 x 256 before going through the residual CNN and the feature maps obtained have a size of 8. We use an LSTM hidden size of = 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 epoch, the learning rate starts decaying with a decay factor of 0.99. For TVMAX, we set À = 0.01.
Datasets and Metries. We report our results on the Microsoft COCO (MSCOCO) and Flickr30k datasets. MSCOCO is composed of 1132877 images of common objects in context while Flickr30k consists in 31,000 pictures of people involved in everyday activities and events. Each image is an- notated with 5 captions. We use the split proposed by Karpathy & Fei-Feil (2015), which stipulates equal validation and test sizes of 5,000 images (MSCOCO) and 1,000 (Flick30kk). The metrics we report are SPICE (Anderson et al. 2016), CIDEr (Vedantam et al.) 2015). longest common subse- quence ROUGE, (denoted ROUGE,; Lin 2004). to gram BLEU (denoted BLEU,; 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).
Table 1: Automatic evaluation of caption generation on MSCOCO and Flickr30k.
MSCOCO
Flickr30k
SPICE CIDER ROUGE, BLEU, METEOR REP.
SPICE CIDER ROUGE, BLEU, METEOR REP.
softmax
18.4
0.967
52.9
29.9
24.9
3.76
13.5
0.443
44.2
19.9
19.1
6.09
sparsemax
18.9
0.990
53,5
31.5
25.3
3.69
13.7
0.444
44.3
20.7
19.3
5.84
TVMAX
18.5
0.974
53.1
29.9
25.1
3.17
13.3
0.438
44.2
20.5
19.0
3.97
Automated metrics. As can be seen in table I overall sparsemax and TVMAX attention mech- anisms achieve better results when compared with softmax. indicating that the use of selective at- tention leads to better captions. This improvement does not come a high computational cost:

---

Under review as a conference paper at ICLR 2020
soozer
Player
pumming
bassa
BOCORE
player
tunning
feeld
OLOUR
peorde
playing
Sopget
on
Beld
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
inference time, models using TVMAX and sparsemax are only 1.3x and 1.1x slower than softmax. Moreover, for TVMAX automatic metrics results slightly worse than sparsemax but still supe- rior 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.
Table 2: Human evaluation results with different attention mechanisms MSCOCO.
CAPTION (1-5)
ATTENTION RELEVANCE (1-5)
softmax
3.50
3.38
sparsemax
3.71
3.89
T'MAX
3.87
4.10
Human rating. The caption evaluation consisted 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 to 5, when generating the non stop words of the captions. A full description 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 evalua- tion, 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[iillustrates Illlstrates that softmax attention is prone spuriously repeating references to the same object. Selective attention mechanisms like sparsemax and especially MAX reduce rep- etition, measured by the REP metric reported in Table [ This expected success can be attributed to the sparsity of the attention weights distribution and to the ability to select compact regions ex- though
clusively and can be of the causes of the human evaluation results. This happens TV MAX 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

---

Under review as a conference paper at ICLR 2020
intuition that sparsity leads to less repetition, we measured the Jensen -haann-S 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 distri- butions along the generation of the captions and, consequently, less repetitions.
Object detection. Using the MSCOCO object detection ground truth, we compared the percentage of objects present in the image that are referred 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 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, display the output attention in Figures] I and 3 As expected, softmax weights are spread widely across the image, ending up missing the relevant regions. In contrast, sparsemax and TV MAX weights are zero for the non-relevant spatial locations.
Qualitative comparison. As the image of Figure 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, ment. In Figure 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.
revealed by human attention assess-
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 tention, 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 non-differentiable, requiring imitation learning or Monte Carlo policy gradient cntrroxiiiaiiosnnneeeee 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 Waan et al. (2019) pro- posed an hierarchical attention network composed by a patch detector, object detector, and concept detector. Using object detection models is less demanding the attention mechanism, since it only has to select the boxes the model should attend to. However, such models are limited by the bound- ing boxes position's accuracy. (aa et al. (2019) introduced a deliberate attention network to refine the attended visual features. Yet, the attention distribution remained dense.
et al. (2018)
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 (017) 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 ID fusedmax.
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 TV MAX. Results the image captioning task, show that the attention mechanism is able to select better
8

---

Under review as a conference paper at ICLR 2020
features when using sparsemax 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 's interpretability.
In future work. TVMAX attention can be applied to other multimodal problems such as visual ques- tion 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.
REFERENCES
Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. SPICE: Semantic proposi- tional image caption evaluation In Proc. ECCV, 2016.
Peter Anderson, Xiaodong He, Chris Buehler, Damien Teney, Mark Johnson, Stephen Gould, and Lei Zhang. Bottom-up and top-down attention for image captioning and visual question answer- ing. In Proc. CVPR, 2018.
Francis Bach, Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, et al. Optimization with sparsity-inducing penalties. Foundations and Trends Machine Learning, 4(1):1-106, 2012.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate In Proc. ICLR, 2015.
Satanjeev Banerjee and Alon Lavie. METEOR: An automatic metric for MT evaluation with im- proved correlation with human judgments) In Proc. ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for Machine Translation and/or Summarization, 2005.
Álvaro Barbero and Suvrit Sra. Modular proximal optimization for multidimensional total-variation regularization preprint arXiv:1411.058) 2014.
Sergei Burtsev and Ye.P. Kuzmin. An efficient flood-filling algorithm. Computers & Graphics, 17: 549-561, 09 1993.
Sumit Chopra, Michael Auli, and Alexander M Rush. Abstractive sentence summarization with attentive recurrent neural networks] In Proc. NAACI- 2016.
Jan K Chorowski, Dzmitry Bahdanau, Dmitriy Serdyuk, Kyunghyun Cho, and Yoshua Bengio. Attention-based models for speech recognition
In Proc. NeurlPS, 2015.
Laurent Condat. direct algorithm for 1-d total variation denoising Letters, 20(1 I): 105400140111 1057, 2013.
IEEE Signal Processing
Laurie Davies and Arne Kovac. Local extremes, runs, strings and multiresolution Statistics, 29(1):1-48 2001. ISSN 00905364.
The Annals of
Ali Farhadi, Mohsen Hejrati, Mohammad Amin Sadeghi, Peter Young, Cyrus Rashtchian, Julia Hockenmaier, and David Forsyth. EEvery picture tells a story: Generating sentences from images. In Proc. ECCV, 2010.
Jerome Friedman, Trevor Hastie, Holger Höfling, and Robert Tibshirani. Pathwise coordinate opti- mization The Annals of Applied Statistics, 1(2)3002-32, 2007.
Lianli Gao, Kaixuan Fan, Jingkuan Song, Xianglong Liu, Xing Xu, and Heng Tao Shen. Deliberate attention networks for image captioning. 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog nition In Proc. CVPR, 2016.
Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descrip- tions. In Proceedings of the IEEE conference on computer vision and pattern recognition, 2015.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. preprint arXiv:1412.n 1412,6980 2014.

---

Under review as a conference paper at ICLR 2020
Girish Kulkarni, Visruth Premraj, Sagnik Dhar, Siming Li, Yejin Choi, Alexander C Berg, and Tamara L Berg. Baby talk: Understanding and generating image descriptions. In Proc. CVPR, 2011.
Chin-Yew Lin. ROUGE: A package for automatic evaluation of summaries
Text Summarization
Branches Out, 2004.
Fenglin Liu, Xuancheng Ren, Yuanxin Liu, Houfeng Wang, and Xu Sun. simNet: Stepwise image- topic merging network for generating detailed and comprehensive image captions) Preprint arXiv:1808.08732, 2018a.
Xihui Liu, Hongsheng Li, Jing Shao, Dapeng Chen, and Xiaogang Wang. Show, tell and discrim- inate: Image captioning by self-retrieval with partially labeled data. preprint TrXXvv:803.083/11 2018b.
Jiasen Lu, Jianwei Yang, Dhruv Batra, and Devi Parikh. Neural baby talk. In Proc. CVPR, 2018.
Chaitanya Malaviya, Pedro Ferreira, and André FT Martins. Sparse and constrained attention for neural machine translation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 370-376, 2018.
Andre Martins and Ramon Astudillo. From softmax to sparsemax: A sparse model of attention and multi-label classification. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proc. ICML, 20-22 Jun 2016.
Vlad Niculae and Mathieu Blondel. A regularized framework for sparse and structured neural atten- tion. In Proc. NeurlPS, 2017.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. evaluation of machine translation In Proc. ACL, 2002.
BLEU: method for automatic
Ben Peters, Vlad Niculae, and André FT Martins. Sparse sequence-to-sequeecce models. In Proc. ACL, 2019.
Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei Imagenet large scale visual recognition challenge, 2014.
Robert Tibshirani, Michael Saunders, Saharon Rosset, Ji Zhu, and Keith Knight. Sparsity and ssmoothness via the fused lasso) Journal of the Royal Statisticul Society: Series (Statistical Methodology), 67(1):91-108, 2005.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, tukasz Kaiser, and Illia Polosukhin. Attention all you need In Proc. NeurlPS, 2017.
Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. CIDEr: Consensus- based image
description evaluation In Proc. CVPR, 2015.
Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator In Proc. CVPR, 2015.
Weixuan Wang, Zhihong Chen, and Haifeng Hu. Hierarchical attention network for image caption- ing. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 8957-8964, 2019.
Bo Xin, Yoshinobu Kawahara, Yizhou Wang, Lingjing Hu, and Wen Gao. Efficient generalized fused lasso and its applications/ ACM Trans. Intell. Syst. Technol., 7(4):60:1-60222 May 2016.
ISSN 2157-6904.
Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention In Proc. ICML, 2015.
Yaoliang Yu. On decomposing the proximal map In Proc. NeurlPS, 2013.
10

---

Under review as a conference paper at ICLR 2020
A FORWARD AND BACKWARD PASS OF 2D FUSEDMAX ATTENTION.
A. PRELIMINARIES
The proximal operator of function f: IR R U {oo} is defined
prox (z) arg min (() + 2 2 - w|l2
(11)
wERe
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 C Rd is the function
0, w E C, co,
le: RRd + R {oo}:
(c(w))
(12)
w $ C.
The projection onto convex set C C R2d is defined as
(rojc(z) = arg min
2 || w12 prox (z),
(13)
WEC
showing that the proximal operator can be The sparsemax attention mapping (Martins & Astudillo 2016) is the projection onto the simplex,
generalization of projection.
sparsemax(z) == proj (z) = arg min
PEA 2 |p - 21/2.
(14)
A necessary component for using sparsemax for attention is its Jacobian, the matrix of its partial
derivatives (J sparsemax);; )i,j a @sparsemax()).
Martins & Astudillo (016)) derive its expression
Oz;
sparsemax (x) diag
|| 88
(15)
where sj 1 sparsemax(z)) > and 8 otherwise.
A.2 PROOF OF PROPOSITION
Proof. This result is slight extension of Proposition 2 in Niculae & Blondel (017)). and also follows from Corrolary 4 Yu (2013). by taking f = 1Λ. and noting that L is symmetric: p A, then any vector p' obtained by permuting p also in A, because its values remain non- negative and sum to I.
A.3 PROOF OF PROPOSITION 2
Let w² prox and denote by G, the set of indices fused to w, in the solution. Define Sij sign w w
Proof. The subgradient optimality conditions of Eq. are: (Friedman et al. 2007
: - 24 + Σ Xt.a
Σ At4a = 0,
15
(16)
k:cnok
where f. sign(w; - wz) if w +f w3. otherwise tij is free variable in [-1,
We focus single group G G;, dropping the index i for brevity. Within fused group, the solution is constant, i.c., = = for j E G. We separate the sums in Eq. 16 according to whether k or not, and move the "constant" terms the right hand side, yielding the system
W +
Atsk-
Ataj 2j + Σ Asks Σ Asyk.
jEC G.
(17)
J~h KEG
k~j kEG
RNj KGC
j-k
kgG

---

Under review as a conference paper at ICLR 2020
Summing up the Eq. 17 over all j G. observe that for any l G, the term λtyk appears twice with opposite signs. Thus,
Σ JEG
w
Σ
2j
Asej
(18)
JEG
k- kgG
jruk kgG
Dividing by |G] gives exactly Eq. This reasoning applies to any group G4.
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 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 the relevant regions of the image when generating 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 [ and 3 and we emphasized sparsity with simply
hard white mask, for the human evaluation the sparse regions of the attention plots fully transparent, to avoid biasing the evaluators. The possible scores were also between 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, computed the mean of the captions evaluation scores and the mean of the attention relevance evaluation scores. The results are reported in Table
C ADDITIONAL ATTENTION VISUALIZATION
0,000
0.025
0.050
0.075
0.100
0.125
0.150
Figure 4: Example generated captions using softmax attention (top), sparsemax attention (middle) and TVMAX attention (bottom). The captions are "A bowl fruit and bowl of fruit". "A bowl of fruit and oranges on a table" and "A bowl of oranges and a banana on table".
12

---

Under review as a conference paper at ICLR 2020
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 field".
13


Reviews:
[{"review_id": "SyeAYTPb9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes two sparsifying methods of computing attention weights, dubbed sparsemax and TVmax, which appear to slightly improve objective and subjective image captioning scores.    The sparsifying projections are posed as optimization problems, and algorithms for their computation, along with formula for their gradients are given.  Proof of the optimality of these algorithms relies significantly on prior work, so could not be checked deeply without bringing in additional sources.  \n\nIt is not clear that the motivation for these sparsifying objectives is sound.   The conventional softmax approach to attention weights should be capable of producing attention weights near zero, which would be effectively sparse, especially if the pre-activations, z_i, in equation (1), are allowed to have a large enough range.   It's not clear why weights should need to be zero exactly in the ignored regions, since being near zero should be sufficient to contribute almost nothing to the subsequent weighted sum.    So it is also not clear why the strict sparsity itself, as opposed to the effective sparsity of the softmax, should explain the differences in Figure 1, and in the results.  In particular it is unclear why the strict sparsity should prevent repetition; when looking at the weight distributions in the two cases, a more likely story seems to be that the weight distributions don't repeat as much from one word to the next in the second case, but there is no clear reason to attribute this to sparsity.   The pictures of the attention weights are lacking a color scale, so it is impossible to see how close to zero it comes in the unattended regions, although the gray color values chosen for these regions might be misleading. \nThe TVmax approach, in addition to sparsity, also constrains the non-zero region to be contiguous.   To the extent that this improves performance, this presumably introduces an inductive bias that matches the data.   It is unclear why this fails to produce better objective scores than sparsemax, while producing better human ratings.   In any case it is not clear why this should necessarily be a good inductive bias for all images, although it is plausible that it helps in some cases.  \nIn many neural network problems, what makes a difference has more to do with the optimizability of the gradients, than the specific activations per se, and that might be the case here too, although the paper does not analyze this aspect of the proposed models.   \n\nOverall the paper is flawed by the lack of clarity in the motivation for the proposed methods, and the lack of retrospective analysis and understanding of why the proposed methods should improve results. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Hygts56c5H", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper produces a new method call TVmax and presents that the selective visual attention could improve the score in the Image Captioning task. Different from the fusedmax[2] which fuses attention in one dimension, the proposed method encourages the sparse attention over contiguous 2D regions. Compared with the softmax function, the sparsemax[1]  and the TVmax are able to sparse the visual attention very well. The paper also evaluates the score in both automated metrics and the human rating. Experiments show that the sparse visual attention achieves higher performance with a little computational cost.\n\nOne problem in this paper is that the author applies their proposed TVmax on Image Captioning  task, however it only achieves a little improvement on the automated metrics compared with the baseline(softmax). I wonder whether there is a better task for evaluating the visual attention. \n\nAlthough the proposed method (TVmax) is slightly worse than the sparsemax in the automated metrics, it is still promising in multimodal problems. \n\nTherefore, My decision leans to a weak accept.\n\nSome questions:\n1.From the experiments, the proposed method achieved only a little higher performance than the baseline(softmax). Could you please show some reasons about that?\n2.Could you show some results of TVmax on the other task in order to show the effectiveness of the proposed method?\n\n\n[1]From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classification.      André F. T. Martins, Ramón Fernandez Astudillo\n[2]A Regularized Framework for Sparse and Structured Neural Attention .            Vlad Niculae, Mathieu Blondel", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HkxewMw0tH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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.\n\n[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.]", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents sparse attention mechanisms for image captioning. In addition to recent sparsemax based method, authors proposed to extend it by incorporating structural constraints in 2D images, which is called TVMAX. The proposed methods are shown to improve the quality of captioning, particularly in terms of fewer erroneous repetitions, and obtain better human evaluation scores. 
Through reviewer discussion, one reviewer updated the score to rejection. A major concern raised by the reviewers is that the motivation of introducing sparse attention is not clear, and the reason why it improves the quality (particularly, why it can reduce repetition) is not convincing. While we understand it is plausible for long sequences as in text domain, we are not convinced that it is really necessary for image captioning problems. Although authors seem to have some ideas, we cannot see how they will be reflected in the paper so I’d like to recommend rejection.
I recommend authors to polish the paper with a clearer description of the motivation and high-level analysis of the method as well as testing on other visual tasks to show its generality. 

Decision: Reject