[S4] Efficiently Modeling Long Sequences with Structured State Spaces
Albert Gu, Karan Goel, Christopher Ré
Статья: https://arxiv.org/abs/2111.00396
Давно мы не писали про RNN, последний раз, кажется, это было про LEM (https://news.1rj.ru/str/gonzo_ML/857). Тогда также хотелось написать про State Space Models (SSM) и их ярких представителей в лице HiPPO и S4, но началась война и стало не до этого. Тема важная, хочется к ней таки вернуться.
Работа про S4 была принята на мою любимую конференцию ICLR в 2022 году и получила там Outstanding Paper Honorable Mentions (https://blog.iclr.cc/2022/04/20/announcing-the-iclr-2022-outstanding-paper-award-recipients/).
Есть большая проблема с моделированием длинных последовательностей. Длинные, это типа 10к элементов и больше. Ныне рулящие трансформеры по-прежнему испытывают с этим проблемы, в первую очередь благодаря квадратичной сложности механизма внимания (правда, есть куча неквадратичных механизмов, про многие из которых мы писали, например, https://news.1rj.ru/str/gonzo_ML/404 и далее по ссылкам).
На эту тему есть бенчмарк Long Range Arena (LRA, https://paperswithcode.com/sota/long-range-modeling-on-lra), где рулят в целом не трансформеры (но лидером там всё же теперь свежий скорее-трансформер одноголовый Mega, https://arxiv.org/abs/2209.10655).
Было много заходов на решение проблемы моделирования реально длинных последовательностей, и один из свежих это как раз state space model (SSM).
SSM описывается уравнениями:
x′(t)=Ax(t)+Bu(t)
y(t)=Cx(t)+Du(t)
где u(t) -- входной сигнал, x(t) -- n-мерное латентное представление, y(t) выходной сигнал, а A,B,C и D -- обучаемые матрицы.
В работе D считается равным нулю, потому что это аналог skip-connection и его легко вычислить.
На практике такая модель работает плохо, потому что решение такой ODE ведёт к экспоненциальной функции со всеми знакомыми по RNN прелестями в виде vanishing/exploding gradients.
Фреймворк HiPPO с NeurIPS 2020 (https://arxiv.org/abs/2008.07669) предлагает специальный класс матриц A, позволяющих лучше запоминать историю входных данных. Самая важная матрица этого класса, называемая HiPPO Matrix, выглядит так:
/ (2n + 1)^1/2 * (2k + 1)^1/2 if n > k
A_nk = − { n + 1 if n = k
\ 0 if n < k
Замена в SSM случайной матрицы A на эту приводит к улучшению результата на sequential MNIST с 60% to 98%.
Это было непрерывное описание, а чтобы применить его к дискретным входам, SSM надо дискретизировать с шагом Δ и входной сигнал будет сэмплиться с этим шагом. Для этого используется билинейный метод, заменяющий матрицу A на её аппроксимацию
x_k = Ax_k−1 + Bu_k
y_k = Cx_k
A = (I − ∆/2 · A)^−1 * (I + ∆/2 · A)
B = (I − ∆/2 · A)^ −1 * ∆B
C = C.
Уравнения состояния теперь рекуррентная формула с x_k по типу RNN, а сам x_k может рассматриваться как скрытое состояние с матрицей перехода A.
И есть ещё отдельный хак, что такую рекуррентную формулу можно развернуть и заменить на свёртку (с ядром K) размером в длину последовательности, но эту формулу я тут приводить не буду, потому что текстом она выглядит не очень. Такое можно быстро считать на современном железе.
Боттлнек discrete-time SSM в том, что надо многократно умножать на матрицу A.
Текущая работа предлагает расширение и улучшение SSM под названием Structured State Spaces (S4). Предлагается новая параметризация, где матрица A (которая HiPPO) раскладывается в сумму низкорангового и нормального (https://en.wikipedia.org/wiki/Normal_matrix) терма, Normal Plus Low-Rank (NPLR).
В дополнение к этому применяются ещё несколько техник: truncated SSM generating function + Cauchy kernel + применение Woodbury identity + подсчёт спектра ядра свёртки через truncated generating function + обратное БПФ, за подробностями и доказательствами вэлкам в статью. Доказывается, что у всех HiPPO матриц есть NPLR представление, и что свёрточный фильтр SSM можно вычислить за O(N + L) операций и памяти (и это главный технический контрибьюшн статьи).
Albert Gu, Karan Goel, Christopher Ré
Статья: https://arxiv.org/abs/2111.00396
Давно мы не писали про RNN, последний раз, кажется, это было про LEM (https://news.1rj.ru/str/gonzo_ML/857). Тогда также хотелось написать про State Space Models (SSM) и их ярких представителей в лице HiPPO и S4, но началась война и стало не до этого. Тема важная, хочется к ней таки вернуться.
Работа про S4 была принята на мою любимую конференцию ICLR в 2022 году и получила там Outstanding Paper Honorable Mentions (https://blog.iclr.cc/2022/04/20/announcing-the-iclr-2022-outstanding-paper-award-recipients/).
Есть большая проблема с моделированием длинных последовательностей. Длинные, это типа 10к элементов и больше. Ныне рулящие трансформеры по-прежнему испытывают с этим проблемы, в первую очередь благодаря квадратичной сложности механизма внимания (правда, есть куча неквадратичных механизмов, про многие из которых мы писали, например, https://news.1rj.ru/str/gonzo_ML/404 и далее по ссылкам).
На эту тему есть бенчмарк Long Range Arena (LRA, https://paperswithcode.com/sota/long-range-modeling-on-lra), где рулят в целом не трансформеры (но лидером там всё же теперь свежий скорее-трансформер одноголовый Mega, https://arxiv.org/abs/2209.10655).
Было много заходов на решение проблемы моделирования реально длинных последовательностей, и один из свежих это как раз state space model (SSM).
SSM описывается уравнениями:
x′(t)=Ax(t)+Bu(t)
y(t)=Cx(t)+Du(t)
где u(t) -- входной сигнал, x(t) -- n-мерное латентное представление, y(t) выходной сигнал, а A,B,C и D -- обучаемые матрицы.
В работе D считается равным нулю, потому что это аналог skip-connection и его легко вычислить.
На практике такая модель работает плохо, потому что решение такой ODE ведёт к экспоненциальной функции со всеми знакомыми по RNN прелестями в виде vanishing/exploding gradients.
Фреймворк HiPPO с NeurIPS 2020 (https://arxiv.org/abs/2008.07669) предлагает специальный класс матриц A, позволяющих лучше запоминать историю входных данных. Самая важная матрица этого класса, называемая HiPPO Matrix, выглядит так:
/ (2n + 1)^1/2 * (2k + 1)^1/2 if n > k
A_nk = − { n + 1 if n = k
\ 0 if n < k
Замена в SSM случайной матрицы A на эту приводит к улучшению результата на sequential MNIST с 60% to 98%.
Это было непрерывное описание, а чтобы применить его к дискретным входам, SSM надо дискретизировать с шагом Δ и входной сигнал будет сэмплиться с этим шагом. Для этого используется билинейный метод, заменяющий матрицу A на её аппроксимацию
x_k = Ax_k−1 + Bu_k
y_k = Cx_k
A = (I − ∆/2 · A)^−1 * (I + ∆/2 · A)
B = (I − ∆/2 · A)^ −1 * ∆B
C = C.
Уравнения состояния теперь рекуррентная формула с x_k по типу RNN, а сам x_k может рассматриваться как скрытое состояние с матрицей перехода A.
И есть ещё отдельный хак, что такую рекуррентную формулу можно развернуть и заменить на свёртку (с ядром K) размером в длину последовательности, но эту формулу я тут приводить не буду, потому что текстом она выглядит не очень. Такое можно быстро считать на современном железе.
Боттлнек discrete-time SSM в том, что надо многократно умножать на матрицу A.
Текущая работа предлагает расширение и улучшение SSM под названием Structured State Spaces (S4). Предлагается новая параметризация, где матрица A (которая HiPPO) раскладывается в сумму низкорангового и нормального (https://en.wikipedia.org/wiki/Normal_matrix) терма, Normal Plus Low-Rank (NPLR).
В дополнение к этому применяются ещё несколько техник: truncated SSM generating function + Cauchy kernel + применение Woodbury identity + подсчёт спектра ядра свёртки через truncated generating function + обратное БПФ, за подробностями и доказательствами вэлкам в статью. Доказывается, что у всех HiPPO матриц есть NPLR представление, и что свёрточный фильтр SSM можно вычислить за O(N + L) операций и памяти (и это главный технический контрибьюшн статьи).
Telegram
gonzo-обзоры ML статей
Long Expressive Memory for Sequence Modeling
T. Konstantin Rusch, Siddhartha Mishra, N. Benjamin Erichson, Michael W. Mahoney
Статья: https://arxiv.org/abs/2110.04744
Код: https://github.com/tk-rusch/LEM
Нельзя было пройти мимо модели под названием LEM.…
T. Konstantin Rusch, Siddhartha Mishra, N. Benjamin Erichson, Michael W. Mahoney
Статья: https://arxiv.org/abs/2110.04744
Код: https://github.com/tk-rusch/LEM
Нельзя было пройти мимо модели под названием LEM.…
👍22❤6🕊1
Дефолтный S4 работает на одной входной и выходной чиселке, а в реальности для DNN обычно нужны многомерные векторы. Чтобы поддержать работу не с одной фичей, а со множеством (H штук), делается H независимых копий S4, а H фичей замешиваются через position-wise linear layer (то есть, так понимаю, для каждой фичи свой такой слой, смотрящий на все остальные фичи). Это также похоже на depthwise-separable convolutions, а вся глубокая (многослойная) S4 близка к depthwise-separable CNN с глобальным ядром свёртки.
По дефолту также преобразование линейное, но добавление нелинейных преобразований между слоями делает всю глубокую SSM нелинейной.
Полученную S4 сравнивают с LSSL (Linear State-Space Layer, те же авторы, https://arxiv.org/abs/2110.13985) и S4 многократно лучше, и c эффективными трансформерами (сравнима с Performer или Linear Transformer).
На LRA на момент публикации порвала с дюжину разных эффективных трансформеров. Стандартный неэффективный тоже (хотя он по качеству неплох, но по скорости и памяти ужасен). С момента первой публикации статью ещё проапдейтили и ещё улучшили результаты S4.
Среди прочего S4 решил задачу Path-X, которую до него не решали. В этой задаче надо определять, соединены ли две точки путём на картинке 128x128, что приводит после разворачивания картинки к последовательности длины 16384. В свёртках при этом выучиваются какие-то интересные паттерны с “пониманием” двумерных данных.
Также проверялись на подмножестве задач SC10 из Speech Commands dataset. Фич хитрых при этом не использовали, работали с raw speech длины 16k и достигли 98.3% accuracy и побили методы использующие MFCC фичи.
Среди других задач был бенчмарк WikiText-103, там рулили трансформеры, и S4 их не обогнала, но зато при замене self-attention на S4 разница в perplexity получается всего 0.8, а скорость инференса при этом в 60 раз выше. Сейчас в моменте, кстати, на этом бенчмарке лидер H3 от этих же авторов или “Hungry Hungry Hippos: Towards Language Modeling with State Space Models” (https://arxiv.org/abs/2212.14052), принятая на ICLR 2023.
На задачах предсказания временных рядов сравнивались с Informer (специальный трансформер для time-series, про него тоже так и не успел написать, но может быть …) и другими бейзлайнами. S4 рулит вообще.
Провели интересные абляции, показали, что инициализация HiPPO очень важна, сильно бьёт гауссовую и по скорости обучения, и по финальному качеству.
В общем, среди SSM сейчас полно очень сильных представителей, тема достойна широкого внимания.
Другие ссылки в тему:
- “The Annotated S4” с кодом на JAX: https://srush.github.io/annotated-s4/
- Рассказ от одного из авторов: https://www.youtube.com/watch?v=EvQ3ncuriCM
- Ещё один разбор с фокусом на JAX: https://www.youtube.com/watch?v=GqwhkbrWDOI
- Код с имплементациями разных SSSM: https://github.com/HazyResearch/state-spaces
По дефолту также преобразование линейное, но добавление нелинейных преобразований между слоями делает всю глубокую SSM нелинейной.
Полученную S4 сравнивают с LSSL (Linear State-Space Layer, те же авторы, https://arxiv.org/abs/2110.13985) и S4 многократно лучше, и c эффективными трансформерами (сравнима с Performer или Linear Transformer).
На LRA на момент публикации порвала с дюжину разных эффективных трансформеров. Стандартный неэффективный тоже (хотя он по качеству неплох, но по скорости и памяти ужасен). С момента первой публикации статью ещё проапдейтили и ещё улучшили результаты S4.
Среди прочего S4 решил задачу Path-X, которую до него не решали. В этой задаче надо определять, соединены ли две точки путём на картинке 128x128, что приводит после разворачивания картинки к последовательности длины 16384. В свёртках при этом выучиваются какие-то интересные паттерны с “пониманием” двумерных данных.
Также проверялись на подмножестве задач SC10 из Speech Commands dataset. Фич хитрых при этом не использовали, работали с raw speech длины 16k и достигли 98.3% accuracy и побили методы использующие MFCC фичи.
Среди других задач был бенчмарк WikiText-103, там рулили трансформеры, и S4 их не обогнала, но зато при замене self-attention на S4 разница в perplexity получается всего 0.8, а скорость инференса при этом в 60 раз выше. Сейчас в моменте, кстати, на этом бенчмарке лидер H3 от этих же авторов или “Hungry Hungry Hippos: Towards Language Modeling with State Space Models” (https://arxiv.org/abs/2212.14052), принятая на ICLR 2023.
На задачах предсказания временных рядов сравнивались с Informer (специальный трансформер для time-series, про него тоже так и не успел написать, но может быть …) и другими бейзлайнами. S4 рулит вообще.
Провели интересные абляции, показали, что инициализация HiPPO очень важна, сильно бьёт гауссовую и по скорости обучения, и по финальному качеству.
В общем, среди SSM сейчас полно очень сильных представителей, тема достойна широкого внимания.
Другие ссылки в тему:
- “The Annotated S4” с кодом на JAX: https://srush.github.io/annotated-s4/
- Рассказ от одного из авторов: https://www.youtube.com/watch?v=EvQ3ncuriCM
- Ещё один разбор с фокусом на JAX: https://www.youtube.com/watch?v=GqwhkbrWDOI
- Код с имплементациями разных SSSM: https://github.com/HazyResearch/state-spaces
arXiv.org
Combining Recurrent, Convolutional, and Continuous-time Models...
Recurrent neural networks (RNNs), temporal convolutions, and neural differential equations (NDEs) are popular families of deep learning models for time-series data, each with unique strengths and...
👍14❤2🔥2
Interesting thoughts about AI vs. AGI in a recent podcast with David Deutsch:
Naval Ravikant: Related to that, we’ve touched upon AGI [artificial general intelligence] here and there. You have said AGI is absolutely possible, and that Turing settled that issue. Now some people are saying it’s almost inevitable and we have to worry about things like AGI alignment. I’m wondering if you have thoughts on both, is self-improving, runaway AGI here? And is this something that we need to align with our beliefs, whatever those are?
In fact, I don’t think we, as humans, can even agree upon alignment, but suppose we could. How would we align AGI?
David Deutsch: Yeah, and we don’t even any longer try to align humans in the way that people want to align AGIs, namely by physically crippling their thinking. Yes, I don’t think we’re anywhere near it yet, I’d love to be wrong about that, but I don’t think we’re anywhere near it. And I think that AI, although it’s a wonderful technology, and I think it’s going to go a lot further than it is now, AI has nothing to do with AGI. It’s a completely different technology and it is in many ways the opposite of AGI. And the way I always explain this is that with an AGI or a person, an artificial person, their thinking is unpredictable; we’re expecting them to produce ideas that nobody predicted they would produce, and which are good explanations, that’s what people can do. And I don’t mean necessarily write physics papers or whatever, we do this thing in our everyday lives all the time.
You can’t live an ordinary human life without creating new good explanations. An AGI would be needed to build a robot that can live in the world as a human, that’s Turing’s idea, with what is mistakenly called the Turing test. Now, why an AI is the opposite to an AGI is that an AGI, as I said, can do anything, whereas an AI can only do the narrow thing that it’s supposed to do, like a better chatbot is one that replies in good English, replies to the question you ask, can look things up for you, doesn’t say anything politically incorrect. The better the AGI is, the more constrained its output is. You may not be able to actually say what the result of all your constraints must be, it’s not constrained in the sense that you prescribe what it is going to say, but you prescribe the rule that what it is going to say must follow or the rules.
So if it’s a chess-playing machine, chess-playing program, then the idea is that you must win the game. And making a better one of these means amputating more of the possibilities of what it would otherwise do, like namely lose, or in the case of chatbots, say the wrong thing or not answer your question or contradict itself or whatever. So the art of making a good AI is to limit its possibilities tremendously. You limit them a trillion fold compared with what it could be. There are a trillion ways of being wrong for every way of being right, same is true of chess-playing programs. Whereas, for the perfect AGI, as it were, would be where you can show by looking at the program and you can show mathematically that there is no output that it couldn’t produce, including no output at all. So an AGI, like a person might refuse to answer, it should have that right by the first amendment.
So you can’t have a behavioral test for an AGI because the AGI may not cooperate. It may be right not to cooperate because it may be very right to suspect what you are going to do to it. So you see that this is not only a different kind of program, it’s going to require a different kind of programming because there is no such thing as the specification. We know sort of philosophically what we want the AGI to be, a bit like parents know philosophically that they want their children to be happy, but they don’t want — if they’re doing the right thing, they don’t want to say, “Well, my child will never say X, will never utter these words,” like you do for an AI. You will recognize what it means to be happy once they’ve done it.
(there are many other interesting things as well)
Naval Ravikant: Related to that, we’ve touched upon AGI [artificial general intelligence] here and there. You have said AGI is absolutely possible, and that Turing settled that issue. Now some people are saying it’s almost inevitable and we have to worry about things like AGI alignment. I’m wondering if you have thoughts on both, is self-improving, runaway AGI here? And is this something that we need to align with our beliefs, whatever those are?
In fact, I don’t think we, as humans, can even agree upon alignment, but suppose we could. How would we align AGI?
David Deutsch: Yeah, and we don’t even any longer try to align humans in the way that people want to align AGIs, namely by physically crippling their thinking. Yes, I don’t think we’re anywhere near it yet, I’d love to be wrong about that, but I don’t think we’re anywhere near it. And I think that AI, although it’s a wonderful technology, and I think it’s going to go a lot further than it is now, AI has nothing to do with AGI. It’s a completely different technology and it is in many ways the opposite of AGI. And the way I always explain this is that with an AGI or a person, an artificial person, their thinking is unpredictable; we’re expecting them to produce ideas that nobody predicted they would produce, and which are good explanations, that’s what people can do. And I don’t mean necessarily write physics papers or whatever, we do this thing in our everyday lives all the time.
You can’t live an ordinary human life without creating new good explanations. An AGI would be needed to build a robot that can live in the world as a human, that’s Turing’s idea, with what is mistakenly called the Turing test. Now, why an AI is the opposite to an AGI is that an AGI, as I said, can do anything, whereas an AI can only do the narrow thing that it’s supposed to do, like a better chatbot is one that replies in good English, replies to the question you ask, can look things up for you, doesn’t say anything politically incorrect. The better the AGI is, the more constrained its output is. You may not be able to actually say what the result of all your constraints must be, it’s not constrained in the sense that you prescribe what it is going to say, but you prescribe the rule that what it is going to say must follow or the rules.
So if it’s a chess-playing machine, chess-playing program, then the idea is that you must win the game. And making a better one of these means amputating more of the possibilities of what it would otherwise do, like namely lose, or in the case of chatbots, say the wrong thing or not answer your question or contradict itself or whatever. So the art of making a good AI is to limit its possibilities tremendously. You limit them a trillion fold compared with what it could be. There are a trillion ways of being wrong for every way of being right, same is true of chess-playing programs. Whereas, for the perfect AGI, as it were, would be where you can show by looking at the program and you can show mathematically that there is no output that it couldn’t produce, including no output at all. So an AGI, like a person might refuse to answer, it should have that right by the first amendment.
So you can’t have a behavioral test for an AGI because the AGI may not cooperate. It may be right not to cooperate because it may be very right to suspect what you are going to do to it. So you see that this is not only a different kind of program, it’s going to require a different kind of programming because there is no such thing as the specification. We know sort of philosophically what we want the AGI to be, a bit like parents know philosophically that they want their children to be happy, but they don’t want — if they’re doing the right thing, they don’t want to say, “Well, my child will never say X, will never utter these words,” like you do for an AI. You will recognize what it means to be happy once they’ve done it.
(there are many other interesting things as well)
🤔10❤4👍2😁1👌1🤣1
Podcast: https://tim.blog/2023/03/23/david-deutsch-naval-ravikant/
Trannoscript: https://tim.blog/2023/03/24/david-deutsch-naval-ravikant-trannoscript/
Trannoscript: https://tim.blog/2023/03/24/david-deutsch-naval-ravikant-trannoscript/
The Blog of Author Tim Ferriss
David Deutsch and Naval Ravikant — The Fabric of Reality, The Importance of Disobedience, The Inevitability of Artificial General…
David Deutsch and Naval Ravikant on The Tim Ferriss Show podcast
👍8❤1🔥1
Пока готовятся обзоры очередных интересных статей, вот ещё один старый, но хороший подкаст Девида Дойча:
https://www.ted.com/talks/the_ted_interview_david_deutsch_on_the_infinite_reach_of_knowledge/trannoscript
Оно же на Apple Podcasts: https://podcasts.apple.com/us/podcast/david-deutsch-on-the-infinite-reach-of-knowledge/id1437306870
И на Google Podcasts: https://podcasts.google.com/feed/aHR0cHM6Ly9mZWVkcy5mZWVkYnVybmVyLmNvbS9UZWRJbnRlcnZpZXc/episode/cHJ4XzE3OV83Y2I0ODNlMy1jN2I5LTRmYWQtYWJmYi1lNTUyOGJlNGVkNTg?ep=14
https://www.ted.com/talks/the_ted_interview_david_deutsch_on_the_infinite_reach_of_knowledge/trannoscript
Оно же на Apple Podcasts: https://podcasts.apple.com/us/podcast/david-deutsch-on-the-infinite-reach-of-knowledge/id1437306870
И на Google Podcasts: https://podcasts.google.com/feed/aHR0cHM6Ly9mZWVkcy5mZWVkYnVybmVyLmNvbS9UZWRJbnRlcnZpZXc/episode/cHJ4XzE3OV83Y2I0ODNlMy1jN2I5LTRmYWQtYWJmYi1lNTUyOGJlNGVkNTg?ep=14
Ted
David Deutsch on the infinite reach of knowledge
It can be easy to believe that humans are insignificant. We're specks of dust on a random planet in a vast universe. Less powerful than elephants. Fewer than ants. But David Deutsch believes that's all beside the point, because humans possess one unique skill:…
👍7🥰2
Нельзя сегодня не запостить Юдковского
https://time.com/6266923/ai-eliezer-yudkowsky-open-letter-not-enough/
https://time.com/6266923/ai-eliezer-yudkowsky-open-letter-not-enough/
TIME
Pausing AI Developments Isn’t Enough. We Need to Shut it All Down
One of the earliest researchers to analyze the prospect of powerful Artificial Intelligence warns of a bleak scenario
🤡70👍17🤔3👾3🤩2😁1🤯1