Self-Attention 的时间复杂度/空间复杂度是怎么计算的

主要观点总结

本文介绍了Self-Attention和Multi-Head Attention的时间复杂度分析。文章详细解释了Self-Attention的三个步骤：相似度计算、softmax和加权平均，并指出其时间复杂度为O(n^2·d)。对于Multi-Head Attention，文章解释了其类似于CNN中的多核作用，并分析了其时间复杂度也是O(n^2·d)。此外，文章还涉及了空间复杂度的分析，并提供了相关参考文献。

关键观点总结

关键观点1: Self-Attention的时间复杂度分析

Self-Attention包括三个步骤：相似度计算、softmax和加权平均。其中，相似度计算的时间复杂度为O(n^2·d)，softmax的时间复杂度为O(n^2)，加权平均的时间复杂度也为O(n^2·d)。因此，Self-Attention的总时间复杂度为O(n^2·d)。

关键观点2: Multi-Head Attention的时间复杂度分析

Multi-Head Attention的作用类似于CNN中的多核。其时间复杂度分析与Self-Attention类似，也是O(n^2·d)。

关键观点3: 空间复杂度的分析

存储QK T的空间复杂度为O(N^2)，存储Softmax(QK T/d^0.5)V的空间复杂度为O(N^2 + Nd)，如果把向量维度d看作常数，则可以说Self-Attention的空间复杂度是序列长度的平方。

文章预览

技术总结专栏 作者：喜欢躺躺的瓦力 Self-Attention时间复杂度：𝑂(𝑛^2⋅𝑑) ，这里，n是序列的长度，d是embedding的维度。 回顾矩阵乘法 C = np.zeros((m, l)) for i in range ( m ): for j in range ( l ): for k in range ( n ): C[i][j] + = A[i][k] * B[k][j] 显而易见，3 个𝑓𝑜𝑟 循环，因此矩阵乘法时间复杂度𝑂(𝑚𝑛𝑙)。 具体步骤 Self-Attention包括 三个步骤：相似度计算，softmax和加权平均 step1: 相似度计算可以看作大小为(n,d)和(d,n)的两个矩阵相乘：(𝑛,𝑑)∗(𝑑,𝑛)=𝑂(𝑛^2⋅𝑑) ，得到一个(n,n)的矩阵. step2: softmax就是直接计算了，时间复杂度为 𝑂(𝑛^2) step3: 加权平均可以看作大小为(n,n)和(n,d)的两个矩阵相乘：(𝑛,𝑛)∗(𝑛,𝑑)=𝑂(𝑛^2⋅𝑑) ，得到一个(n,d)的矩阵 因此，Self-Attention的时间复杂度是 𝑂(𝑛^2⋅𝑑) 。 再分析一下Multi-Head Attention， ………………………………