一恋追、摘要
當(dāng)前深度學(xué)習(xí)中用于捕獲長(zhǎng)距離依賴(lài)關(guān)系的主要方式——堆疊卷積或者使用循環(huán)模塊凭迹，均為局部鄰域處理組件。本文提出了另一種捕獲長(zhǎng)距離依賴(lài)關(guān)系的通用組件——非局部處理模塊苦囱。
【待完善】
二嗅绸、Non-Local Neural Network
2.1 回顧Non local means
??Non local means filter，即非局部均值濾波算法撕彤，是圖像去噪領(lǐng)域一個(gè)非常有名的算法鱼鸠。我讀研一時(shí)有個(gè)大四的學(xué)妹在做畢設(shè)，問(wèn)我說(shuō)她想找個(gè)傳統(tǒng)去噪算法作為她跑的DL代碼的對(duì)比方法，我就給她推薦了NLM（當(dāng)時(shí)我也沒(méi)聽(tīng)過(guò)幾個(gè)傳統(tǒng)去噪算法哈哈蚀狰，所以應(yīng)該算是大名鼎鼎了）漆弄。
??NLM的思路非常直觀，首先其出發(fā)點(diǎn)在于：在去噪任務(wù)中造锅，對(duì)圖像的每個(gè)小塊撼唾，如果能用和其相同性質(zhì)的其他小塊加權(quán)平均（去噪任務(wù)主流的方法是在不改變?cè)驾斎胄盘?hào)的情況下通過(guò)加權(quán)平均，或者說(shuō)濾波哥蔚，來(lái)去除噪聲）倒谷，會(huì)對(duì)當(dāng)前小塊噪聲抑制起到較好的效果。這樣相同性質(zhì)的小塊越多糙箍，加權(quán)平均之后的效果就越好渤愁。
??因此，NLM算法簡(jiǎn)單來(lái)說(shuō)就是兩個(gè)步驟：一是確定當(dāng)前小塊與圖像所有位置的小塊之間的接近程度深夯，即所有小塊與當(dāng)前小塊加權(quán)平均時(shí)的權(quán)值抖格；二是將各個(gè)小塊的像素值與當(dāng)前小塊按照該權(quán)值，加權(quán)平均之后作為去噪的結(jié)果咕晋。算法示意圖如Fig. 1：
??Fig. 2展示了對(duì)一副大圖雹拄，以中心像素為基準(zhǔn)，圖像所有像素的權(quán)重可視化結(jié)果掌呜∽揖粒可以看出與中心像素所在鄰域性質(zhì)相似的區(qū)域獲得的權(quán)重明顯高一些。
??NLM的模型如下：
质蕉，其中
代表圖像势篡，
代表位置下標(biāo)；
表示權(quán)重模暗。非局部均值濾波算法中具體使用的
為：
禁悠，
為歸一化因子，其值為當(dāng)前小塊和圖像所有小塊權(quán)重之和：
??這里著重記錄一下兑宇。求
兩位置的權(quán)重
也就是衡量圖像在這兩個(gè)位置的相似度碍侦，最簡(jiǎn)單的方法是直接評(píng)估兩位置對(duì)應(yīng)像素灰度值的差距」四酰考慮到使用鄰域比單獨(dú)的像素可靠一些祝钢，鄰域相似度高則認(rèn)為這兩個(gè)像素的相似度高，故論文中用比較兩個(gè)像素所在鄰域來(lái)代替像素值直接比較若厚。
??衡量?jī)蓚€(gè)圖像塊相似度最常用的方法是計(jì)算他們之間的歐氏距離，不過(guò)在求歐式距離的時(shí)候蜒什，不同位置的像素的權(quán)重應(yīng)當(dāng)是不一樣的测秸，距離塊的中心越近的像素，權(quán)重越大，距離中心越遠(yuǎn)霎冯，權(quán)重越小铃拇。這個(gè)權(quán)重可以看作一個(gè)符合高斯分布的kernel。（不過(guò)實(shí)際計(jì)算中考慮到計(jì)算量的問(wèn)題沈撞，常常采用均勻分布的權(quán)重慷荔。另外原始NLM算法速度很慢，后續(xù)又出了很多優(yōu)化版本缠俺，這里不做討論显晶。）
?? 聯(lián)想：在harris特征匹配算法中，計(jì)算像素之間相似程度也用到鄰域之間的相似度壹士，不過(guò)計(jì)算的是歸一化互相關(guān)系數(shù)磷雇；sift匹配則是對(duì)鄰域提取到的特征，利用余弦相似定理（歸一化的dot product）來(lái)計(jì)算特征相似程度躏救。
??通過(guò)下面一段matlab代碼唯笙，可以看出NLM具體計(jì)算過(guò)程：
for r=rmin:1:rmax
for s=smin:1:smax
if(r==i1 && s==j1) continue; end;
W2= input2(r-f:r+f , s-f:s+f);
d = sum(sum(kernel.*(W1-W2).*(W1-W2)));
w=exp(-d/h);
if w>wmax
wmax=w;
end
sweight = sweight + w;
average = average + w*input2(r,s);
end
end
其中kernel由以下代碼生成：
function [kernel] = make_kernel(f)
kernel=zeros(2*f+1,2*f+1);
for d=1:f
value= 1 / (2*d+1)^2 ;
for i=-d:d
for j=-d:d
kernel(f+1-i,f+1-j)= kernel(f+1-i,f+1-j) + value ;
end
end
end
kernel = kernel ./ f;
2.2 從NLM到NLNN
??上面一部分回顧了經(jīng)典的NLM算法。另外之所以去細(xì)看NLM的論文盒使，實(shí)際上就是因?yàn)樵诳碞on-local Neural Networks論文時(shí)對(duì)Fig. 3這張論文截圖有兩個(gè)疑問(wèn)：
- 為什么作者在選擇
時(shí)說(shuō)“一個(gè)自然的選擇是使用高斯函數(shù)”
- 作者說(shuō)使用"gaussian function"但是給出的式子只是一個(gè)矩陣乘法之后的指數(shù)函數(shù)崩掘，如何代表高斯？
??我自己先嘗試對(duì)這2個(gè)問(wèn)題進(jìn)行解答：
??首先使用exponential function并不是gaussian的體現(xiàn)呢堰，按照NLM論文的說(shuō)法，指數(shù)函數(shù)的作用其實(shí)就是為了讓歐式距離較大位置的權(quán)重能夠快速衰減到0附近凡泣，也即"fast decay"枉疼。（值得注意的是，后續(xù)還出現(xiàn)了不少針對(duì)nlm中的指數(shù)kernel進(jìn)行優(yōu)化的論文鞋拟。）
??然后真正體現(xiàn)gaussian的是上面代碼段中在兩個(gè)鄰域計(jì)算歐式距離時(shí)加入的gaussian kernel衰減矩陣颅和，其作用在于眯勾，按照鄰域中像素距離中心的遠(yuǎn)近來(lái)控制求鄰域間歐式距離時(shí)的像素權(quán)重，即代表gaussian版本的歐式距離。
??從這個(gè)角度來(lái)說(shuō), NLNN(Non Local Neural Network)論文中提到的gaussian function貌似并不是真的用了gaussian衰減组力，因?yàn)镹LNN在比較兩個(gè)位置時(shí)，甚至并未通過(guò)比較任何形式的鄰域
來(lái)確定該
位置與
的接近程度影涉，而僅僅是直接比較輸入信號(hào)在
兩個(gè)位置對(duì)應(yīng)向量或者向量的embedding的距離測(cè)度膏秫。
??具體來(lái)說(shuō)，對(duì)于NLM懈叹，輸入信號(hào)為2D圖像乖杠，通過(guò)計(jì)算以像素為中心的鄰域相似度來(lái)決定位置
處的權(quán)重；對(duì)于NLNN澄成，若輸入信號(hào)為3D特征圖胧洒，則每個(gè)空間位置
對(duì)應(yīng)一個(gè)向量畏吓，故論文計(jì)算的是
和
兩個(gè)1D向量的點(diǎn)積再對(duì)得到的標(biāo)量過(guò)一個(gè)指數(shù)函數(shù)。
??接下來(lái)回到NLNN論文中卫漫，首先看一下作者給出的通用non-local operation模型:
??其中菲饼，代表當(dāng)前待計(jì)算的output position的index，
代表輸入信號(hào)（圖像列赎、序列宏悦、視頻或者他們的特征），
為輸出信號(hào)包吝，通常和
保持size相同饼煞。二元函數(shù)
輸出一個(gè)標(biāo)量，如兩個(gè)位置
的某種接近程度的metric漏策。一元函數(shù)負(fù)責(zé)給出輸入信號(hào)在
位置處的一個(gè)表示派哲。計(jì)算出的輸出信號(hào)在
處的響應(yīng)最后會(huì)經(jīng)過(guò)一個(gè)歸一化因子
以進(jìn)行歸一化。
??上式從形式上看與NLM的模型掺喻，即式(1)沒(méi)有差異芭届。接下來(lái)作者在"Instantiations"部分為該通用模版舉了幾個(gè)具體的例子，使之更易理解感耙，同時(shí)也用于說(shuō)明non local block的通用性褂乍。
??代表位置
處輸入信號(hào)的一個(gè)表示，為了簡(jiǎn)潔起見(jiàn)即硼，作者就直接把其形式固定為原始輸入的一個(gè)embedding：
逃片，
為
對(duì)應(yīng)的權(quán)重矩陣，如最簡(jiǎn)單的只酥，對(duì)于CNN中的feature褥实，
可以是
卷積（或者進(jìn)一步擴(kuò)展到多個(gè)
卷積，即由一個(gè)卷積層提取之后的新特征裂允？）
??然后作者討論了對(duì)函數(shù)的選擇损离。這里有必要再對(duì)NLM和NLNN的區(qū)別做一個(gè)強(qiáng)調(diào)：
- 輸入信號(hào)形式： NLM輸入信號(hào)形式固定，為2D圖像绝编，NLNN輸入信號(hào)形式多樣僻澎，可以是2D(第一層輸入特征)、3D（中間層輸入特征）甚至4D（加入時(shí)序的中間層特征）
-
計(jì)算相似程度時(shí)有無(wú)使用鄰域信息：
兩個(gè)位置的相似程度十饥。由于NLM輸入形式簡(jiǎn)單窟勃，
均只代表一個(gè)灰度數(shù)值，故求相似程度時(shí)利用鄰域信息提高魯棒性逗堵。NLM在使用鄰域信息時(shí)為了突出中心像素坐標(biāo)秉氧，所以要用gaussian kernel。而對(duì)于NLNN來(lái)說(shuō)
各自代表一個(gè)向量砸捏，求兩向量之間的相似程度來(lái)表征
??所以NLNN論文中的gaussian與embedded gaussian或許改成exponential與embedded exponential更貼切梆暖？畢竟后面還把式子轉(zhuǎn)化成softmax，softmax中的exp與gaussian有隱含關(guān)系嗎掂骏？
2.3 NLNN block公式推導(dǎo)
2.3.1 權(quán)重與softmax
??接下來(lái)就是這一章最重要的內(nèi)容：將上述公式（以embedded gaussian為例子）簡(jiǎn)化為softmax的形式轰驳。為了便于理解，這里可以以我們比較熟悉的CNN某中間層特征來(lái)作為輸入信號(hào)弟灼，其shape為HxWx1024级解。對(duì)于兩個(gè)位置，計(jì)算其embedded gausssian:
對(duì)于輸入信號(hào)的某個(gè)位置田绑，因?yàn)閕確定是C為常數(shù)勤哗，故可寫(xiě)成：
然后把C代入進(jìn)來(lái)：
可以看出對(duì)于固定的，中間那一塊符合softmax的定義掩驱，因此有：
至此我們推導(dǎo)了對(duì)于單個(gè)位置芒划，輸出信號(hào)的響應(yīng)
。接下來(lái)需要對(duì)這個(gè)公式進(jìn)行向量化欧穴。大家在寫(xiě)反向傳播相關(guān)練習(xí)時(shí)都知道民逼，單個(gè)樣本的公式比較好推導(dǎo)，但是如果要在代碼中實(shí)現(xiàn)涮帘，還是需要向量化之后的公式拼苍。
2.3.2 公式向量化
??首先保持固定，去掉
：
??注意调缨，這里的和
本身是3維向量
疮鲫，但是如果推導(dǎo)時(shí)直接用3維的shape，后面會(huì)非常麻煩弦叶。故這里的一個(gè)技巧是將
和
均看成
的矩陣（假設(shè)
使用的embedding也是C個(gè)kernel）俊犯。這樣sum就是沿著列方向進(jìn)行。
??可以先檢查下各個(gè)向量的維度：為
湾蔓，
為
瘫析，softmax相當(dāng)于是activation不改變維度，故經(jīng)過(guò)softmax之后的維度為
默责，然后
為
贬循，故對(duì)于每個(gè)
，通過(guò)廣播得到
的矩陣桃序，然后對(duì)列求和得到輸出響應(yīng)杖虾。
??然后嘗試去除,得到最終的向量化公式：
??為了實(shí)現(xiàn)對(duì)樣本維度的向量化，一種個(gè)人比較喜歡的做法是先將可能的取值代進(jìn)去媒熊，并排寫(xiě)到一起觀察規(guī)律奇适，比如下面的草稿：
看起來(lái)要求坟比，需要做的就是對(duì)每一個(gè)
的
向量（注意這張圖中的
相當(dāng)于上面用的
記號(hào))分別與
廣播相乘并把結(jié)果矩陣堆到一起，再對(duì)列求和即可嚷往，也就是下圖的第一行：
（圖示：第一個(gè)矩陣的每一行分別與第二個(gè)矩陣相乘（利用廣播）皮仁，得到的A個(gè)CxB的矩陣concat到一起籍琳，再沿著列方向求和）
??這里直接給出結(jié)論，第一行的結(jié)果和第二行的結(jié)果等價(jià)贷祈。感興趣的同學(xué)可以證明下趋急？（我挑了幾個(gè)位置對(duì)比了下是一樣的hh）
??到這里，我們可以寫(xiě)出去掉之后的向量化公式：
其中"·"代表dot product势誊，即矩陣乘法呜达，其在向量化過(guò)程中起到關(guān)鍵的一步，并且將讓人頭疼的sum去掉了粟耻。這樣我們就可以寫(xiě)出NLNN關(guān)鍵組件的代碼查近，同時(shí)也可以看懂論文中的Figure2，尤其是為什么右上那個(gè)乘法用的是矩陣乘法勋颖。（注意嗦嗡，看該圖時(shí)可以忽略掉維度T，并將embedding所用權(quán)重簡(jiǎn)化為饭玲，這樣會(huì)稍微容易理解一些）
??嚴(yán)格來(lái)說(shuō)侥祭，根據(jù)輸出響應(yīng)的定義，softmax之后那個(gè)矩陣乘法的結(jié)果就是當(dāng)采取embedded gaussia時(shí)的輸出信號(hào)茄厘。但是這張圖后面還有個(gè)通過(guò)1024個(gè)1x1 conv將輸出映射回emedding之前的維度矮冬，然后加上原始輸入信號(hào)。個(gè)人理解這里最左邊那條通路以及逐元素相加運(yùn)算應(yīng)該算是構(gòu)成了NLNN版“卷積”的shortcut次哈。
【待續(xù)】
四胎署、記錄
對(duì)長(zhǎng)距離依賴(lài)關(guān)系的建模方式：
- 堆疊卷積層
- 使用循環(huán)網(wǎng)絡(luò)組件
- graphic models，如條件隨機(jī)場(chǎng)窑滞、GNN
詞語(yǔ)記錄：
- showcase：v. display/exhibit
- amenable：合適的琼牧，易順?lè)?/li>
- affinity：n. 接近，親和力
參考文獻(xiàn)：
https://developers.google.com/machine-learning/clustering/similarity/measuring-similarity
https://blog.csdn.net/piaoxuezhong/java/article/details/78345929
