保留正文与补采附件。源页面当前未重新核验；具体限制见交付清单。

Revisit consent button We value your privacy We use cookies to enhance your browsing experience, serve personalised ads or content, and analyse our traffic. By clicking "Accept All", you consent to our use of cookies. Customise Reject All Accept All Customise Consent Preferences We use cookies to help you navigate efficiently and perform certain functions. You will find detailed information about all cookies under each consent category below. The cookies that are categorised as "Necessary" are stored on your browser as they are essential for enabling the basic functionalities of the site. ... Show more NecessaryAlways Active Necessary cookies are required to enable the basic features of this site, such as providing secure log-in or adjusting your consent preferences. These cookies do not store any personally identifiable data.

Functional Functional cookies help perform certain functionalities like sharing the content of the website on social media platforms, collecting feedback, and other third-party features.

Analytics Analytical cookies are used to understand how visitors interact with the website. These cookies help provide information on metrics such as the number of visitors, bounce rate, traffic source, etc.

Performance Performance cookies are used to understand and analyse the key performance indexes of the website which helps in delivering a better user experience for the visitors.

Advertisement Advertisement cookies are used to provide visitors with customised advertisements based on the pages you visited previously and to analyse the effectiveness of the ad campaigns.

Uncategorised Other uncategorised cookies are those that are being analysed and have not been classified into a category as yet. No cookies to display. Reject All Save My Preferences Accept All Toggle SearchToggle Mobile Navigation Publish AI, ML & data-science insights to a global community of data professionals. Sign inSubmit an Article LatestEditor's PicksNewsletterShipAI

Write For TDS LinkedInXToggle Search Deep Learning

Structured State Space Models Visually Explained

Part 2 - Towards Mamba State Space Models for Images, Videos and Time Series Sascha Kirch August 22, 202418 min read

🐍 Towards Mamba State Space Models for Images, Videos and Time Series

Image by Sascha Kirch. Image by Sascha Kirch.

This is part 2 of my new multi-part series 🐍 Towards Mamba State Space Models for Images, Videos and Time Series. State space models, known to many disciplines of engineering for decades, are now making their debut in deep learning. On our journey towards Mamba selective state space models and their recent achievements in research, understanding the state space model is crucial. And, as is often the case in engineering, it is the details that make theoretical concepts applicable in practice. In addition to state space models, we must also discuss how to apply them to sequence data, how to handle long-range dependencies, and how to efficiently train them by exploiting certain matrix structures. Structured state space models build the theoretical foundation for Mamba. However, their connection to system theory and advanced algebra might be one of the obstacles to adopt this new framework. So, let's break it down, ensure we understand the key concepts and visualize them to shed some light onto this new-old theory. Even if you don't end up using State Space models, understanding some of the tricks like why we need to speed up matrix multiplication and how we can exploit certain structures of matrices for that will certainly level up your skills as an engineer or developer. Mamba State Space Models for Images, Videos and Time Series

Outline

  1. State Space Models in a Nutshell 2.1 Continuous Time Representation of the State Space Model 2.2 Discretization of the State Space Model 2.3 The Recurrent and Convolutional Representations of the SSM
  2. Enabling Long-Range Relationships 3.1 State Size Matters 3.2 The HiPPO Framework
  3. Impose Structure on State Matrices for Efficiency 4.1 What Are Structured Matrices and Why Do They Matter? 4.2 Putting It All Together - S4: Structured State Space Sequence Models
  4. Wrapping Up 5.1 Summary 5.2 Limitations of Structured SSMs 5.3 Continue Reading Part 3

1. Where We Left Off in Part 1

Towards Mamba State Space Models for Images, Videos and Time Series In part 1 we reviewed the strengths and weaknesses of recurrent neuronal networks (RNNs) and Transformers to motivate why we need a new model architecture. We said RNNs are fast at inference time but slow during training and the Transformer is fast to train but slowly inferred. What we want is to find a model that is fast for both, training and inference, while beeing competititve with the Transformer's performance.

2. State Space Models in a Nutshell

Mamba builds on the idea of using a state space model for deep learning by learning its various matrices. So, let's have a brief primer on state space models before exploring what the "structured" part is all about. A state space model can be defined in continuous time representation to deal with continuous signals or can be discretized to handle discrete sequences of data. It is the discretized state space model we are mostly interested in, since like recurrent neuronal networks (RNNs) and Transformers, a discrete SSM processes sequences of data., e.g. text tokens or samples of an analog time signal.

2.1 Continuous Time Representation of the State Space Model

A continuous-time state space model describes the relationship between an input signal propagating through a stateful system and the resulting output signal. Figure 1: High-level functionality of a state space model. Image by Sascha Kirch. Figure 1: High-level functionality of a state space model. Image by Sascha Kirch. It is an idea borrowed from system theory. The output depends on the input and on the current state of the system, while the current state depends on the previous state and the input. This relationship can be formulated efficiently by two simple equations, where A , B , C and D are matrices (which, as we'll see later, will be learned), x(t) is the input signal, y(t) the output signal and h(t) and h'(t) are the current and updated state respectively. Equation. 1: State and output equations of the continuous time SSM. Equation. 1: State and output equations of the continuous time SSM. Matrix D transforms the input x(t) and maps it to the output y(t) , which is typically included in the output equation of a classical SSM. However, when applying an SSM to deep learning, we remove this transformation and model it as a simple skip connection, thereby simplifying the SSM. We can represent those equations in a block diagram that looks something like this: Figure 2: Block diagram of a continuous time state space model. Image by Sascha Kirch. Figure 2: Block diagram of a continuous time state space model. Image by Sascha Kirch. This is the continuous-time representation of an SSM. There are two difficulties though:

  1. finding an analytic solution for the state h(t) of the model is challenging and
  2. since we work on computers we usually work with discrete signals, not continuous ones.

2.2 Discretization of the State Space Model

So, instead of mapping a function x(t) to a function y(t) , we are actually mapping a sequence x[k] to a sequence y[k]. This implies we need a discretized state space model that can handle discrete signals. Figure 3: High-level functionality of a discrete state space model. Image by Sascha Kirch. Figure 3: High-level functionality of a discrete state space model. Image by Sascha Kirch. To do so, we discretize our matrices A and B. This results in the discretized representation of our state space model, now including a discretized state h[k]. Equation 2: State and output equations of the discretized SSM. Equation 2: State and output equations of the discretized SSM. To discretize our state space model, we use yet another trick frequently used in system theory: We use a Zero-Order Hold (ZOH) module to turn our discrete signal x[k] into a continuous time signal x(t) which is then fed into the continuous SSM. The SSM will generate a continuous output y(t) , which we then sample to obtain the discrete output sequence y[k] : Figure 4: Block diagram of a discretized state space model. Image by Sascha Kirch. Figure 4: Block diagram of a discretized state space model. Image by Sascha Kirch. To discretize the state space model, we must discretize matrices A and B. Initially, most of the first deep learning based state space models like LSSL and S4 used the bilinear discretization, while later ones like the DSS and Mamba use the ZOH discretization. For now, all we care about is that we need to discretize and that there might be more than one way to do so. Equation 3: Zero Order Hold ZOH discretization vs. bilinear discretization. Equation 3: Zero Order Hold (ZOH) discretization vs. bilinear discretization. A and B are the SSM's continuous-time matrices, I is the identity matrix and Δ is the step size representing the resolution of the input, which in the deep learning setting is learned.

Note that the discretization allows us to use the time-continuous formulation of the SSM and apply it to discrete signals used in a computer. This implies that we become resolution invariant since we learn the underlying time-signal. Check out the S4ND paper for some further reading on that. Paper Walkthroughs by Sascha Kirch

2.3 The Recurrent and Convolutional Representations of the SSM

Have you noticed the recurrency in the state equation because h[k] depends on h[k-1]? In fact, the state space model is quite like an RNN in that manner: Figure 5: Recurrent representation of a discretized state space model. Image by Sascha Kirch. Figure 5: Recurrent representation of a discretized state space model. Image by Sascha Kirch. The matrices A , B and C are time-invariant. That means that each input and each state is transformed with the same parameters, regardless of the time step. Linear time invariant systems, or short LTI-systems, have a very neat property: they can be represented as a convolution! Equation 4: Convolution kernel of the discretized state space model. Equation 4: Convolution kernel of the discretized state space model. The kernel is constructed from the matrix C and the discretized matrices A and B. Note that the kernel has the same length L as the input sequence. The kernel is convolved with the input x to obtain the output y. To end up with the same sequence length at the output as at the input, the input is usually padded. Figure 6: Example of the convolutional representation of a discretized state space model. Image by Sascha Kirch. Figure 6: Example of the convolutional representation of a discretized state space model. Image by Sascha Kirch. That's awesome because we know that convolutions are parallelizable and that GPUs and other HW-accelerators are optimized to calculate them fast. To conclude this section, leveraging the properties of a L inear T ime I nvariant System, we ended up with 3 different ways to represent the SSM: Figure 7: Different representations of state space models. Image by Sascha Kirch. Figure 7: Different representations of state space models. Image by Sascha Kirch. Both the recurrent and the convolutional representations of the SSM are equal, hence we can decide whether we use one or the other. During training we would choose the convolutional representation because we have access to the entire sequence x[k] and labels y[k] ahead of time through our training data. During inference we would choose the recurrent representation because usually we only have access to samples from the past (e.g. autoregressive text generation). **** Note that the inference scales linearly with the sequence length since our next output only depends on the previous state and the current input. We now have a model with efficient training and efficient inference. Awesome! 😎

It was the LSSL (Linear State Space Layer) paper, that showed that we can train an SSM and that highlighted the connection between the different representations. Get an email whenever Sascha Kirch publishes 🚀 _Get an email whenever Sascha Kirch publishes 🚀 Looking to learn more about deep learning or simply stay up to dat_e...medium.com

3. Enabling Long-Range Relationships

Matrix A is responsible to create the next state from the previous state. The state of the system is a result of multiple updates considering past states and new inputs. It could be said that the state contains the information of the entire history of inputs. It is not hard to imagine that for very long sequences it might be a difficult task to remember all inputs accurately. So, how can we handle long-range dependencies?

3.1 State-Size Matters

Let's first talk about the state, its compression and the efficiency of inference. Figure 8: Efficiency vs. performance of the RNN, SSM, Transformer and the desired model. Image by Sascha Kirch. Figure 8: Efficiency vs. performance of the RNN, SSM, Transformer and the desired model. Image by Sascha Kirch. RNNs and Transformers can both theoretically deal with a never-ending sequence of data (sometimes people say: these models are unbound). The RNN does this by compressing the entire history into a single low-dimensional state. This is very efficient for inference, because now the next state only depends on the previous state and the current input. The performance of the RNN depends on how well the model learns to do this compression. Additionally, for long sequences and especially due to vanishing gradients, this is not an easy task to achieve, even for more advanced RNNs using gating mechanisms like GRUs and LSTMs. The Transformer on the other hand does not compress the history at all. It considers the entire history (and future if not masked like in autoregressive generation) through its attention mechanism. This allows the Transformer being trained in parallel, but at the same time memory and compute requirements explode with increasing sequence lengths during inference. ❓ So, again: how can we handle long-range dependencies with a highly compressed state, without the difficulties during training while achiving high performance? One Solution: we initialize our matrices using the HiPPO (Hi gh-order P olynomial P rojection O perators) framework.

3.2 The HiPPO Framework

The main idea is to parametrize the matrices A and B from the state equation in such a way that we can reconstruct the history (i.e. the input signal from time t=0 to t=now) at any given point. Specifically, if the state is represented as some coefficients of certain orthogonal polynomials (e.g. the Legendre Polynomial), we can simply evaluate the polynomial to reconstruct the input signal up until the current time. For example: We have an input function x(t). At any given time step ti , we want to find a reconstruction g(ti) that approximates x(t for t <ti) for all t before ti. The approximation g(ti) is fully described by the coefficients c(ti) that can be inserted into the Legendre Polynomial to reconstruct g(ti). Figure 9: Approximation gt of the input function xt in the HiPPO framework. Image by Sascha Kirch. Figure 9: Approximation g(t) of the input function x(t) in the HiPPO framework. Image by Sascha Kirch. This is important to understand: Instead of having only access to a compressed representation of the input, we can reconstruct the input at any given time. Still, it is a recurrent model with all the benefits of linear complexity. These coefficients evolve over time, since for every ti , we have different coefficients c(ti). So, how do we get those coefficients? As it turns out, c(t) can be defined as an ordinary differential equation (ODE): Equation 5: ODE of the coefficients of the HiPPO framework. Equation 5: ODE of the coefficients of the HiPPO framework. With some mathematical tricks (e.g. assuming orthogonality of x and g) and by choosing a weighting µ(t) of different time steps, this problem is fully defined. We can solve the ODE and obtain A(t) and B(t) that satisfy our choice of weighting and use those in our SSM. Different HiPPO Matrices have been provided as a solution for different weightings of past samples and different polynomials as a basis.

LegS is the most prominent one used by follow-up works. Here is the solution for matrix A : Equation 6: HiPPO matrix definition and example for N=4. Equation 6: HiPPO matrix definition and example for N=4. A naive python implementation could look something like this: python

def get_hippo_A(N:int) -> np.ndarray:
    A = np.zeros((N,N))
    for n in range(N):
        for k in range(N):
            if n > k:
                A[n,k] = (2*n+1)**0.5*(2*k+1)**0.5
            elif n == k:
                A[n,k] = (n+1)
    return A

The LSSL mentioned earlier did show that one can train an SSM if initialized with the HiPPO matrix and it did show that its performance even surpasses those of the Transformer in the shown experiments. However, its expensive computation and memory requirements made the LSSL infeasible as a general sequence model. This hasn't been solved until the introduction of the S4 (Structured State Space Sequen ce) model, which we will address in the next chapter.

4. Impose Structure on State Matrices for Efficiency

It is finally time to talk about what the structure in the structured state space model is all about. We'll first try to gain some very basic intuition what structure is and why it is important, and then we will take a closer look onto the S4 model.

4.1 What Are Structured Matrices and Why Do They Matter?

Let's consider a standard square matrix of NxN elements. We will focus on two aspects:

  1. how much memory do we need to represent this matrix,
  2. how fast can we multiply 2 matrices, where fast can be a result of several things, like being able to parallelize the computation, exploiting redundancies, and having less values to deal with in the first place.

How Much memory do we need? Let's start with the memory requirements to store a matrix. We can have different kinds of matrices. Sometimes they are already in a certain form and sometimes we can bring them into a certain form leveraging rules from linear algebra. Let's have a look on some common matrix types: Figure 10: Number of values to store for several common matrix types. Image by Sascha Kirch. Figure 10: Number of values to store for several common matrix types. Image by Sascha Kirch. We see that in the worst case for a dense matrix, we need to store N² values in memory. Not only that, but we must also load N² values from the CPU to the GPU, where we then apply certain matrix operations. Note that there is a difference on how much values we need to store in our memory on CPU side (meaning in RAM or on disk) and how much memory we occupy in the GPU for computations. To make this clear, let's look at the low-rank factorization. Some matrices can be factorized into 2 low-rank matrices of NxR , where R is the rank of these matrices. We now only need to store NR values for each of the two matrices, hence 2NR values. That also means we only need to load 2NR values instead of N² from CPU to GPU. But if we want to make calculations with the original matrix, we first need to reconstruct the original matrix (some say materialize them) inside the GPU, meaning we still need N² values in the cache of the GPU. Other representations like the diagonal or the sparse matrix on the other hand decrease both: the values stored on disk and the number of values needed to perform matrix operations on the GPU. How many computations are required? Now let's consider a standard matrix multiplication C=AB , where A and B are either dense or diagonal matrices and C is the result of the matrix multiplication: Figure 11: Number of operations for matrix multiplication of different matrix types. Image by Sascha Kirch. Figure 11: Number of operations for matrix multiplication of different matrix types. Image by Sascha Kirch. For the case where both are dense matrices , using the standard algorithm we all know for matrix multiplication, we need N³ multiplications and (N-1)N² additions. In case Ais a dense matrix and Bis a diagonal matrix , this reduces to N² multiplications and 0 additions. In case both Aand Bare diagonal , we only require N multiplications which are the element-wise multiplications of the entries of the diagonal. While this is desirable in terms of hardware resources, note that a diagonal matrix might be less expressive as a dense matrix, because it has less values. Like everything, it is a trade-off. Parallelization of Computations If you take a closer look onto the dense matrix multiplication, you might notice that calculating a single row of the output C , involves all values of B , but only a single row of A. Naively, you could speed up the computation by calculating each row of C in parallel on different cores of a GPU. This means each core would only need N² multiplications and (N-1)N additions instead of N³ multiplications and (N-1)N² additions as in the single core case because we now have a vector-matrix product, not a matrix-matrix product. Long Story Short To conclude, and using the example of a square matrix of NxN , by trying to exploit certain properties of matrices, we want to bring them into a structured form such that we need to store and load less than N² values and that we require less than N³ multiplications and (N-1)N² additions for matrix multiplications. Of course, there are many other matrix structures that we can exploit all with their own pros and cons. Throughout this series on Mamba state space models we will encounter many of those, and all serve the same purpose: requiring less resources while keeping the best performance possible.

4.2 Putting It All Together - S4: Structured State Space Sequence Models

S4 aims to make SSMs more efficient by enforcing a certain structure upon the involved matrices. By doing so, it can apply well studied rules of algebra to reduce the complexity of the involved computations and save memory, especially for the repeated computation of the kernel K of the convolutional view. Figure 12: S4 Structured State Sequence Model. Image by Sascha Kirch. Figure 12: S4 Structured State Sequence Model. Image by Sascha Kirch. Compared to LSSL, S4 is has been shown to be 30x faster with 400x less memory usage while it also gained a boost in performance.

The S4 paper is involves a lot of advanced linear algebra I will mostly skip in this blog post. If you want to dive deeper into the math and also the code implementation I recommend you to check out The Annotated S4. Recall that calculating the convolution kernel K for the convolutional representation of the SSM, repeated matrix multiplications of the discretized square matrix A are required. Remember that the kernel has the same length L as the input sequence x and that the power of the matrix A is increased with each entry of the kernel. Equation 6: Convolutional kernel of the discretized state space model. Equation 6: Convolutional kernel of the discretized state space model. To be clear, a sequence of length L=101 would have matrices to the power of 100! And 99 and 98 and... you get the point. Of course, we could reuse previous results, but still this is a lot to compute. The main goal of S4 is to reduce the number of resources needed to calculate the kernel K , by imposing a certain structure on matrix A. Ideally, matrix A would be a diagonal matrix because as we saw earlier in Figure 11, multiplying two diagonal matrices result in another diagonal matrix requiring only N multiplications. Since a HiPPO matrix cannot be diagonalized in a numerically stable manner (as proofed in the S4 paper), the next best thing is to decompose it into a normal plus low-rank (NPLR) form that can then further be simplified into a diagonal plus low-rank (DPLR) form by conjugation. Note that we want to hold on to the HiPPO matrix and do not change it to another diagonalizable matrix, because we need it for dealing with long-range dependencies. Figure 13: Comparing different representations of matrix A and there resulting complexity to compute the convolution kernel K. Image by Sascha Kirch. Figure 13: Comparing different representations of matrix A and there resulting complexity to compute the convolution kernel K. Image by Sascha Kirch. Having matrix A in DPLR form allows us to apply many complicated tricks. In summary, the kernel is calculated in the frequency domain and having the DPLR form allows rearranging the matrices into a Cauchy matrix, for which many hardware optimized algorithms exist. Further, using the Woodburry identity allows transforming the calculation of multiple powers of A into a single inverse. Finally, the inverse FFT (Fast Fourier Transform) is applied to obtain the final convolutional filter K. So, the SSM(A,B,C) previously a function of A, B, and C , is now a function _SSM(__Λ-_PP*,B,C) , where _Λ,_P, B and C are learnable parameters of the S4. If you are interested in the original implementation, here is the dplr() function and the nplr() function of the S4 repository.

5. Wrapping Up

5.1 Summary

Thank You!

🤝 I'd like to thank you, t he readers of my stories, for your constant support, clapping for my stories and, following me to never miss any of my latest articles. It is you who motivates me to continue writing, dive deep into complex topics, and become a better engineer/researcher by writing about them. You are awesome!

5.2 Limitations of Structured SSMs

There is one big big issue though: SSMs cannot reason about different inputs at different time steps, since the matrices A , B and C are time invariant meaning the same for all inputs.

5.3 Continue Reading Part 3

Here Comes Mamba: The Selective State Space Model In Part 3 we will discover how Mamba solves the issue of the structured state space model not differentiating between samples in the input sequence by adding selectivity to the model architecture. ❓ But what do we gain and at which cost?

6. Further Readings & Resources

Mamba State Space Models for Images, Videos and Time Series Paper Walkthroughs by Sascha Kirch

Blog Posts

Papers:

Code

Register Now to Continue Reading

Unlock Towards Data Science with a Free Account

All articles on Towards Data Science are available to registered users. Create a free account today to access this article and thousands more. Register for freeSign in to your account

Written By

Sascha Kirch

See all from Sascha Kirch Deep DivesDeep LearningLinear AlgebraMambaMamba Image Video Signal Share This Article

Towards Data Science is a community publication. Submit your insights to reach our global audience and earn through the TDS Author Payment Program. Write for TDS

Related Articles

Using PyTorchVideo for efficient video understanding

Deep Learning Learn how to easily visualize and evaluate activity classification models from the PyTorchVideo library The... Eric Hofesmann May 19, 20218 min read

Writing custom CUDA kernels with Triton

Artificial Intelligence Triton is a language compiler to write highly optimized CUDA kernels. Learn the basics of GPU programming and how to use Triton. Kushajveer Singh September 12, 20218 min read

Generating Haiku with Deep Learning

Deep Learning Using neural networks to generate haiku while enforcing the 5-7-5 syllable structure. Jeremy Neiman December 29, 20189 min read

MobileNetV3 Paper Walkthrough: The Tiny Giant Getting Even Smarter

Artificial Intelligence MobileNetV3 with PyTorch — now featuring SE blocks and hard activation functions Muhammad Ardi Putra November 2, 202527 min read

Neural Networks are like human bodies

Deep Learning Optimizers are like personal trainers Pascal Janetzky October 25, 20216 min read

Prefill Is Compute-Bound. Decode Is Memory-Bound. Why Your GPU Shouldn’t Do Both.

Large Language Models Inside disaggregated LLM inference — the architecture shift behind 2-4x cost reduction that most ML teams haven't adopted yet. Gokul Chandra Purnachandra Reddy April 15, 202614 min read

Reinforcement Learning 101: Q-Learning

Artificial Intelligence Decoding the Math behind Q-Learning, Action-Value Functions, Bellman Equations, and building them from scratch in Python. Cristian Leo February 28, 202434 min read

Paired t-test to evaluate Machine Learning classifiers using Python

Artificial Intelligence Learn how to compare classifiers using hypothesis testing Marcello Politi July 6, 20225 min read

7+ Reinforcement learning competitions to check out in 2022

Deep Learning A list of ongoing and annual competitions suitable for getting hands-on practice with reinforcement learning (while winning a prize or... Joy Zhang October 28, 20214 min read

Your home for data science and AI. The world's leading publication for data science, data analytics, data engineering, machine learning, and artificial intelligence professionals. Subscribe to Our NewsletterWrite For TDS•About•Advertise•Privacy Policy•Terms of Use © Insight Media Group, LLC 2026•The New Stack•roadmap.sh•Creator Network

Recommended Articles

Close

word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word word

mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1
mmMwWLliI0fiflO&1