Non-Local Neural Networks

1 Non-Local Neural NetworksXiaolong Wang1,2 Ross Girshick2 Abhinav Gupta1 Kaiming He21 Carnegie Mellon University2 Facebook AI ResearchAbstractBoth convolutional and recurrent operations are buildingblocks that process one local neighborhood at a time. Inthis paper, we present Non-Local operations as a genericfamily of building blocks for capturing long-range depen-dencies. Inspired by the classical Non-Local means method[4] in computer vision, our Non-Local operation computesthe response at a position as a weighted sum of the featuresat all positions. This building block can be plugged intomany computer vision architectures. On the task of videoclassification, even without any bells and whistles, our Non-Local models can compete or outperform current competitionwinners on both Kinetics and Charades datasets. In staticimage recognition, our Non-Local models improve object de-tection/segmentation and pose estimation on the COCO suiteof tasks.

2 Code will be made IntroductionCapturinglong-rangedependenc ies is of central impor-tance in deep Neural Networks . For sequential data ( ,in speech, language),recurrentoperations [38,23] are thedominant solution to long-range dependency modeling. Forimage data, long-distance dependencies are modeled by thelarge receptive fields formed by deep stacks ofconvolutionaloperations [14,30].Convolutional and recurrent operations both process alocalneighborhood, either in space or time; thus long-rangedependencies can only be captured when these operationsare applied repeatedly, propagating signals progressivelythrough the data. Repeating local operations has severallimitations. First, it is computationally inefficient. Second,it causes optimization difficulties that need to be carefullyaddressed [23,21]. Finally, these challenges make multi-hop dependency modeling, , when messages need to bedelivered back and forth between distant positions, this paper, we presentnon-localoperations as an ef-ficient, simple, and generic component for capturing long-range dependencies with deep Neural Networks .

3 Our pro-posed Non-Local operation is a generalization of the classicalnon-local mean operation [4] in computer vision. Intuitively,a Non-Local operation computes the response at a position Work done during an internship at Facebook AI 1. A spacetimenon-localoperation in our network trainedfor video classification in Kinetics. A positionxi s response iscomputed by the weighted average of the features ofallpositionsxj(only the highest weighted ones are shown here). In this examplecomputed by our model, note how it relates the ball in the first frameto the ball in the last two frames. More examples are in a weighted sum of the features atall positionsin the in-put feature maps (Figure1). The set of positions can be inspace, time, or spacetime, implying that our operations areapplicable for image, sequence, and video are several advantages of using Non-Local opera-tions: (a) In contrast to the progressive behavior of recurrentand convolutional operations, Non-Local operations capturelong-range dependencies directly by computing interactionsbetween any two positions, regardless of their positional dis-tance; (b) As we show in experiments, Non-Local operationsare efficient and achieve their best results even with onlya few layers ( , 5); (c) Finally, our Non-Local operationsmaintain the variable input sizes and can be easily combinedwith other operations ( , convolutions as we will use).

4 We showcase the effectiveness of Non-Local operations inthe application of video classification. In videos, long-rangeinteractions occur between distant pixels in space as well astime. A single Non-Local block, which is our basic unit, candirectly capture these spacetime dependencies in a feedfor-ward fashion. With a few Non-Local blocks, our architecurescallednon-local Neural networksare more accurate for videoclassification than 2D and 3D convolutional Networks [48](including the inflated variant [7]). In addition, non-localneural Networks are more computationally economical thantheir 3D convolutional counterparts. Comprehensive abla-tion studies are presented on the Kinetics [27] and Charades[44] RGB only and without any bells andwhistles( , optical flow, multi-scale testing), our methodachieves results on par with or better than the latest competi-tions winners on both demonstrate the generality of Non-Local operations,we further present object detection/segmentation and poseestimation experiments on the COCO dataset [33].

5 On top ofthe strong Mask R-CNN baseline [19], our Non-Local blockscan increase accuracy on all three tasks at a small extracomputational cost. Together with the evidence on videos,these image experiments show that Non-Local operations aregenerally useful and can become a basic building block indesigning deep Neural Related WorkNon-local image means [4] is a clas-sical filtering algorithm that computes a weighted mean ofall pixels in an image. It allows distant pixels to contribute tothe filtered response at a location based on patch appearancesimilarity. This Non-Local filtering idea was later developedinto BM3D (block-matching 3D) [10], which performs filter-ing on a group of similar, but Non-Local , patches. BM3D isa solid image denoising baseline even compared with deepneural Networks [5]. Block matching was used with neuralnetworks for image denoising [6,31]. Non-Local match-ing is also the essence of successful texture synthesis [12],super-resolution [16], and inpainting [1] dependencies can be mod-eled by graphical models such as conditional random fields(CRF) [29,28].

6 In the context of deep Neural Networks , aCRF can be exploited to post-process semantic segmenta-tion predictions of a network [9]. The iterative mean-fieldinference of CRF can be turned into a recurrent networkand trained [56,42,8,18,34]. In contrast, our method is asimpler feedforward block for computing Non-Local these methods that were developed for segmentation,our general-purpose component is applied for classificationand detection. These methods and ours are also related to amore abstract model called graph Neural Networks [41].Feedforward modeling for thereemerged a trend of using feedforward ( , non-recurrent) Networks for modeling sequences in speech and language[36,54,15]. In these methods, long-term dependenciesare captured by the large receptive fields contributed byvery deep 1-D convolutions. These feedforward models areamenable to parallelized implementations and can be moreefficient than widely used recurrent work is related to the recentself-attention[49] method for machine translation.

7 A self-attention module computes the response at a position ina sequence ( , a sentence) by attending to all positionsand taking their weighted average in an embedding we will discuss in the next, self-attention can be viewedas a form of the Non-Local mean [4], and in this sense ourwork bridges self-attention for machine translation to themore general class of Non-Local filtering operations that areapplicable to image and video problems in computer Networks (IN) [2,52]were proposed recently for modeling physical systems. Theyoperate on graphs of objects involved in pairwise [24] presented the more efficient Vertex AttentionIN (VAIN) in the context of multi-agent predictive variant, named Relation Networks [40], computes afunction on the feature embeddings at all pairs of positionsin its input. Our method also processes all pairs, as we willexplain (f(xi,xj)in Eq.(1)). While our Non-Local networksare connected to these approaches, our experiments indicatethat thenon-localityof the model, which is orthogonal tothe ideas of attention/interaction/relation ( , a networkcan attend to a local region), is the key to their empiricalsuccess.

8 Non-Local modeling, a long-time crucial element ofimage processing ( , [12,4]), has been largely overlookedin recent Neural Networks for computer classification natural solution tovideo classification is to combine the success of CNNs forimages and RNNs for sequences [55,11]. In contrast, feed-forward models are achieved by 3D convolutions (C3D)[26,48] in spacetime, and the 3D filters can be formed by inflating [13,7] pre-trained 2D filters. In addition to end-to-end modeling on raw video inputs, it has been found thatoptical flow [45] and trajectories [50,51] can be flow and trajectories are off-the-shelf modules thatmay find long-range, Non-Local dependency. A systematiccomparison of video architectures can be found in [7].3. Non-Local Neural NetworksWe first give a general definition of Non-Local operationsand then we provide several specific instantiations of FormulationFollowing the Non-Local mean operation [4], we define ageneric Non-Local operation in deep Neural Networks as:yi=1C(x) jf(xi,xj)g(xj).

9 (1)Hereiis the index of an output position (in space, time, orspacetime) whose response is to be computed andjis theindex that enumerates all possible the inputsignal (image, sequence, video; often their features) andyis the output signal of the same size asx. A pairwise func-tionfcomputes a scalar (representing relationship such asaffinity) betweeniand allj. The unary functiongcomputesa representation of the input signal at the positionj. Theresponse is normalized by a factorC(x).The Non-Local behavior in Eq.(1) is due to the fact thatall positions ( j) are considered in the operation. As acomparison, a convolutional operation sums up the weightedinput in alocalneighborhood ( ,i 1 j i+ 1in a1D case with kernel size 3), and a recurrent operation at time7795iis often based only on the current and the latest time steps( ,j=iori 1).The Non-Local operation is also different from a fully-connected (fc) layer. Eq.(1) computes responses based onrelationships between different locations, whereasfcuseslearned weights.

10 In other words, the relationship betweenxjandxiis not a function of the input data infc, unlike in Non-Local layers. Furthermore, our formulation in Eq.(1) supportsinputs ofvariablesizes, and maintains the correspondingsize in the output. On the contrary, anfclayer requires afixed-size input/output and loses positional correspondence( , that fromxitoyiat the positioni).A Non-Local operation is a flexible building block and canbe easily used together with convolutional/recurrent can be added into the earlier part of deep Neural Networks ,unlikefclayers that are often used in the end. This allows usto build a richer hierarchy that combines both Non-Local andlocal InstantiationsNext we describe several versions offandg. Interest-ingly, we will show by experiments (Table2a) that our Non-Local models are not sensitive to these choices, indicatingthat the generic Non-Local behavior is the main reason for theobserved simplicity, we only considergin the form of a linearembedding:g(xj) =Wgxj, whereWgis a weight matrixto be learned.