Post #19

Продолжение Reformer: В этой работе используется очень известный алгоритм LSH хэширования. Сделаем Q=K и будем с помощью LSH находить кластеры похожих эмбеддингов. В таком случае attention скоры нам нужно будет посчитать только внутри этих кластеров. С одной стороны, сложность уменьшается до логлинейной (n * logn), но на практике внутри О большого сидит константа 128^2. Кстати, похожий метод используется в одном из алгоритмов ANN. Performer: Авторы доказывают, что результат attention (softmax(Q x K^T) можно аппроксимировать произведением двух матриц. И собственно эту аппроксимацию модель и выучивает. Доказательство не самое простое, но идея заключается в использовании kernel methods. Если такая аппроксимация у нас есть (softmax(Q x K^T) ~ Q1 x K1^T), то мы можем сначала умножить K и V, а потом их результат умножить на Q (сложность из-за порядка таких умножений изменится, посмотрите картинку или выпишите размерности на листочке). Здесь линейная зависимость по времени и по памяти. Не стоит забывать, что сложность attention зависит не только от длины контекста, но и от размера эмбеддинга. Здесь мы говорили только про первое. Метрики не привожу, их можно поглядеть в самих статьях, если интересно. Я написал далеко не про все работы, посвященные этим темам, — есть еще MEGA, Sparse Transformers, Longformer, MQA, GQA и другие. О них — возможно в следующих постах.