摘要：至於爲什麼說這種方法只有線性複雜度：首先，我們需要對每個時間步 操作，而對它而言，我們只需要計算一個前綴和的差即可，而前綴和是預先計算得到的，所以可以看作是一個常量。本文提出一種時間自適應的卷積，在每一個時間步，都動態地得到當前的卷積大小，並使用前綴和實現了 O(n)  的複雜度。

論文標題：

Time-aware Large Kernel Convolutions

論文作者：

Vasileios Lioutas, Yuhong Guo

論文鏈接：

https://arxiv.org/pdf/2002.03184v1.pdf

在本文，我們介紹一篇非常有趣的工作： 使用“時間自適應”的卷積去替換Transformer中的自注意力 ， 從而將時間複雜度從 降低到O(n) ， 極大加快了文本生成的速度，同時還得到了非常好的效果。

在數據集WMT En-De, En-Fr和IWSLT De-En上取得了和當前最優相同的結果。

Transformer的時間複雜度

作爲大家熟悉的老朋友，Transformer在各種NLP模型、任務上已經被反覆提及了。

Transformer使用了自注意力(Self-attention)去建模每個字符和所有字符的關係，從而，它的時間複雜度是 的。

顯然，這在模型運行的過程中是一筆不可忽略的開銷，尤其當句子長度 很大的時候，運行Transformer的時間開銷是非常大的。

那麼，有沒有什麼方法既能實現Transformer的效果，又能加快速度嗎？

動態卷積給出了一個比較好的答案：使用卷積網絡建模語義關係，從而將複雜度降低到 O(kn) ，這裏k 是卷積核大小。

那麼，有沒有進一步減小時間開銷呢？爲此，本文繼續從卷積網絡出發，提出一種時間自適應的卷積：對每個時間步（即每個位置的字符），動態地預測得到它的卷積核大小，進而利用現有的“並行點綴和”技術降低時間複雜度，使其達到最理想的 O(n) 。

在降低時間開銷的同時，本方法還能達到和當前最優相同的結果，既高效又強大。

總的來說，本文貢獻如下：

  • 提出時間自適應卷積，對每個字符得到其不同的卷積核大小；

  • 極大降低自注意力的時間開銷，將複雜度降低到了 O(n) ，同時還有更少的內存開銷；

  • 在WMT En-De, En-Fr和IWSLT De-En和WikiText-103上實現了和當前最優十分相近的結果。

在閱讀完本文後，讀者可以思考一個簡單的問題： 爲什麼說這種方法可以實現線性複雜度 O(n) ？

時間自適應卷積

設輸入是長度爲 n  的文本 ，每個 都是 d  維向量， 就是所謂的時間步。

爲此降低編碼時間開銷，我們首先直接考慮把第 i  個時間步周圍的向量相加（相當於一個窗口）：

其中 是窗口的兩端。

當然，如果對每個時間步 i  都單獨相加，這就非常低效，因爲有很多項被重複相加。爲此，我們直接考慮 前綴和 ：

那麼，現在 就可以寫成：

我們現在想要對每個時間步 i ，它的窗口大小是不同的，所以需要爲每個 計算它的窗口 。 由於直接計算窗口大小的絕對值不方便，我們轉而計算其相對值：

其中， 是相對大小， 是最大允許的窗口大小。

由於計算得到的 實值，我們需要把它轉化爲整數。 下面，我們就從這實值附近採樣整數：

這裏 。 上述操作都是可微的。

然而，這種方法的問題是，隨着模型層數的增加，向量的和會越來越大，導致模型無法收斂。所以，我們還需要對得到的結果歸一化：

此外，對得到的 加以Dropout也有助於過擬合。

類似Transformer，該方法也可以應用到多頭機制上。這隻需要把原始的輸入 分成若干組，然後對所有組並行操作即可，下圖是一個示例：

圖中有兩個頭，分別是綠色和藍色，各自的絕對窗口大小分別在左右。

在解碼的時候，只需要令 即可。

實驗

本文在機器翻譯數據集WMT English to German (En-De), WMT English to French (En-Fr) and IWSLT German to English (De-En)和語言模型數據集WikiText-103上實驗。具體實驗細節詳見論文。

下面是在WMT上的實驗結果。可以看到，在參數量幾乎相同的情況下，本方法（TaLK）實現了幾乎和當前最優結果相同的結果（實際上還要更快）。

而在IWSLT De-En上，本方法達到了35.5的BLEU值，比之前最好的35.2更高。

而在語言模型上，在相同的參數量下，本方法取得了最好的結果，爲20.3的PPL，如下表所示：

下面我們重點比較各方法的編碼時間和內存上的開銷，結果如下表所示。

首先看內存開銷，隨着句子長度 的增加，本方法相比自注意力就更加有優勢，並且比動態卷積還要略好。

再看每秒迭代次數，在 n=10,100 的時候，本方法每秒迭代次數大概是自注意力和動態卷積的兩倍。

在 n=1000  的時候，是自注意力的四倍，是動態迭代的兩倍；而在 n=10000  時，自注意力直接OUt of Memory，而本方法依舊堅挺。

最後我們來看看本方法各組成的作用，如下表所示。顯然，沒有歸一化，模型原地狗帶，無法收斂。增大窗口最終效果所有幫助，其他方面的技巧似乎幫助不太大。

小結及思考題

本文提出一種時間自適應的卷積，在每一個時間步，都動態地得到當前的卷積大小，並使用前綴和實現了 O(n)  的複雜度。在機器翻譯和語言模型的實驗上表明瞭該方法又快又好，還能節省內存開銷。

至於爲什麼說這種方法只有線性複雜度：首先，我們需要對每個時間步 操作，而對它而言，我們只需要計算一個前綴和的差即可，而前綴和是預先計算得到的，所以可以看作是一個常量。從而總的來說，編碼的複雜度就是  O(n ) 。

:mag:

現在，在 「知乎」 也能找到我們了

進入知乎首頁搜索 「PaperWeekly」

點擊 「關注」 訂閱我們的專欄吧

關於PaperWeekly

PaperWeekly 是一個推薦、解讀、討論、報道人工智能前沿論文成果的學術平臺。如果你研究或從事 AI 領域，歡迎在公衆號後臺點擊 「交流羣」 ，小助手將把你帶入 PaperWeekly 的交流羣裏。

相關文章