Sequence Modeling2022متقدم10 دقيقة قراءة

النمذجة الكفوءة للتسلسلات الطويلة عبر فضاءات الحالة المُهيكلة

Efficiently Modeling Long Sequences with Structured State Spaces

Gu, A. · Goel, K. · Ré, C. — ICLR

المشكلة

التحدي الأساسي في نمذجة التسلسلات هو التقاط العلاقات بين عناصر تفصل بينها آلاف الخطوات. يفعل ذلك عبر ، لكن تكلفتها تنمو تربيعياً مع طول التسلسل فتصبح غير عملية فوق عشرة آلاف خطوة. الشبكات التكرارية تعالج التسلسل خطوة بخطوة بذاكرة ثابتة الحجم، لكنها تعاني من تلاشي التدرّجات الذي يمحو الذاكرة البعيدة. حتى عام 2021 لم يستطع أي نموذج التعامل فعلاً مع هذه الروابط البعيدة: معيار Long Range Arena المصمَّم لاختبار تسلسلات من ألف إلى ستة عشر ألف خطوة أعجز كل البنيات الموجودة في أصعب مهامه.

الإسهام

يطرح S4 طريقة جديدة لمَعلَمة نماذج فضاء الحالة انطلاقاً من إطار . الفكرة الجوهرية أن مصفوفة HiPPO — المصمَّمة رياضياً لحفظ التاريخ الطويل — يمكن تفكيكها إلى صيغة (DPLR). بفضل هذا التفكيك يتحوّل الحساب إلى تقييم ، وهو حساب ينجز بتعقيد $O(N \log N)$ . المحصّلة: نموذج يتدرّب كعملية التفاف (بالتوازي كالشبكة الالتفافية) ويعمل عند كتكرار (بكفاءة الشبكة التكرارية). حقّق S4 دقة 91% على CIFAR-10 التتابعي وحلّ مهمة Path-X بطول 16,384 التي أعجزت كل النماذج السابقة، وتصدّر جميع مهام Long Range Arena بمتوسط 80.48% مقابل أقل من 60% للنماذج الأخرى.

الأثر

أعاد S4 الاعتبار لنماذج فضاء الحالة بديلاً حقيقياً للمحوِّلات في نمذجة التسلسلات. بيّن أن أفكاراً من نظرية التحكم الكلاسيكية — أنظمة ديناميكية في الزمن المتصل وتقطيع زمني ومصفوفات مُهيكلة — تستطيع التفوّق على الانتباه في التسلسلات الطويلة. أطلق S4 موجة أعمال متتالية: S4D بسّط المَعلَمة إلى صيغة قُطرية بحتة، وS5 قدّم ، ثم أضاف Mamba آلية اختيار تعتمد على المدخلات فأصبح أول نموذج فضاء حالة ينافس المحوِّلات في النمذجة اللغوية. المنظومة التي دشّنها S4 تُشغّل اليوم نماذج في الصوت والجينوم والفيديو والسلاسل الزمنية.

تخيّل طريقتين لتذكّر محاضرة طويلة. طريقة المُحوِّل: تُسجّل كل كلمة، وكلما احتجت إجابة تعود وتبحث في التسجيل بالكامل — نتائج ممتازة، لكن مع محاضرة من عشر ساعات يصبح البحث بطيئاً لدرجة غير عملية. طريقة : تُدوّن ملاحظاتك على ورقة لاصقة واحدة وتمسح القديم كلما دوّنت شيئاً جديداً — سريعة جداً، لكنك بحلول الساعة العاشرة تكون قد نسيت كل شيء عن الساعة الأولى.

S4 يشبه دفتراً مُهيكلاً: مجموعة صفحات مُصمَّمة رياضياً بحيث تُحدِّث كل جملة جديدة كل صفحة وتحتفظ بالقدر المناسب تماماً من المعلومات السابقة. هذا الدفتر لا يمتلئ ولا ينسى البداية، والأهم أنه يمكن قراءته بطريقتين: صفحة بصفحة (كما تفعل الشبكة التكرارية عند الاستدلال) أو دفعة واحدة (كما تفعل أثناء ).

المشكلة: لماذا تفشل النماذج الحالية مع التسلسلات الطويلة

هي جوهر التعلم الآلي: اللغة والصوت والسلاسل الزمنية بل حتى الصور يمكن التعامل معها كتسلسلات. والتحدي الأكبر هو التقاط ما نسميه الروابط بعيدة المدى — حين يؤثر حدث عند الخطوة الأولى على النتيجة عند الخطوة رقم عشرة آلاف.

المحوِّلات تحلّ هذا بآلية الانتباه التي تسمح لكل موقع بالنظر إلى كل المواقع الأخرى. الآلية قوية، لكن تكلفتها تربيعية $O(L^2)$ حيث $L$ طول التسلسل. بتسلسل طوله 16,000 نتكلم عن 256 مليون مقارنة ثنائية في كل طبقة.

الشبكات التكرارية (بما فيها LSTM) تسير في الاتجاه المعاكس: تعالج خطوة واحدة كل مرة وتضغط التاريخ كله في ثابتة الحجم. تكلفتها خطية $O(L)$ ، لكن مشكلة تجعل التدرّجات تتقلّص أسيّاً عبر الزمن، فيصبح تعلُّم أي رابط يمتد لأبعد من بضع مئات خطوة شبه مستحيل.

ما كان ينقص الميدان هو نموذج يجمع التعقيد الخطي لـالشبكة التكرارية مع ذاكرة المحوِّل البعيدة. هذا النموذج هو S4.

افتح في المختبر

قارن بين ثلاثة نماذج مع زيادة طول التسلسل: المحوِّل (تعقيد تربيعي)، والشبكة التكرارية (خطي لكنها تنسى)، وS4 (خطي مع ذاكرة طويلة).

تستيقظ التجربة عند وصولك…

نماذج فضاء الحالة: الأساس الرياضي

فكرة مستعارة من نظرية التحكم ومعالجة الإشارات. الفكرة ببساطة: لدينا نظام له حالة مخفية $x(t)$ تتطور في الزمن المتصل. النظام يستقبل إشارة دخل $u(t)$ ، يُحدِّث حالته الداخلية، ثم يُخرج $y(t)$ .

لتبسيط الصورة، تخيّل منظومة خزّانات مياه: الدخل $u(t)$ هو الماء المتدفق إلى المنظومة، و $x(t)$ هو مستوى الماء في عدة خزّانات متصلة ببعضها، و $y(t)$ هو القراءة التي نأخذها. المصفوفة $A$ تحدّد كيف ينساب الماء بين الخزّانات — أي كيف تتصل ببعضها. المصفوفة $B$ تحدّد نقطة دخول الماء، و $C$ تحدّد ما نقيسه.

يُعرَّف هذا النموذج في الزمن المتصل بمعادلتين. الأولى هي معادلة الحالة التي تصف كيف تتطور الحالة المخفية:

x'(t) = A\,x(t) + B\,u(t)

معادلة الحالة — كيف تتطوّر الحالة المخفية — الحالة

x(t) \in \mathbb{R}^N

هي ذاكرة النظام. المصفوفة

A \in \mathbb{R}^{N \times N}

تحكم الديناميكا الداخلية — أي كيف تتفاعل مكونات الحالة فيما بينها. المصفوفة

B \in \mathbb{R}^{N \times 1}

تُدخل الإشارة العددية إلى فضاء الحالة. وجود المشتقة

x'(t)

يعني أن التحديث مستمر وليس منفصلاً.

أما المعادلة الثانية فهي معادلة الخرج — ماذا نستطيع أن نقرأ من الحالة المخفية:

y(t) = C\,x(t) + D\,u(t)

معادلة الخرج — إسقاط الحالة إلى تنبؤ — المصفوفة

C \in \mathbb{R}^{1 \times N}

تقرأ المعلومة من الحالة. الحدّ

D\,u(t)

هو وصلة تخطٍّ تسمح للدخل بالوصول مباشرة إلى الخرج. عملياً يكون

D

مجرد وصلة بسيطة، والتعلّم الحقيقي يتركّز في المصفوفات

A

B

C

افتح في المختبر

تابع تدفق الدخل عبر فضاء الحالة: الماء يدخل ويتوزع بين الخزّانات ويُنتج قراءة. عدّل المصفوفة A لترى كيف يتغيّر سلوك الذاكرة حسب طريقة اتصال الخزّانات.

تستيقظ التجربة عند وصولك…

التقطيع الزمني: من الزمن المتصل إلى خطوات منفصلة

النموذج المتصل أنيق رياضياً، لكنه لا يتعامل مباشرة مع بيانات منفصلة كرموز النص أو عيّنات الصوت. لذلك نحتاج إلى — أي تحويل المعادلات المتصلة إلى تكرار يعمل خطوة بخطوة على تسلسل منفصل $(u_0, u_1, u_2, \ldots)$ .

يستخدم S4 طريقة ثنائية الخطوط (Tustin) مع حجم خطوة قابل للتعلُّم $\Delta$ لتحويل المصفوفات المتصلة $(A, B)$ إلى نظيراتها المنفصلة $(\bar{A}, \bar{B})$ :

\bar{A} = \left(I - \tfrac{\Delta}{2} A\right)^{-1} \left(I + \tfrac{\Delta}{2} A\right), \quad \bar{B} = \left(I - \tfrac{\Delta}{2} A\right)^{-1} \Delta B

التقطيع الزمني ثنائي الخطوط — تحويل الديناميكا المتصلة إلى خطوات منفصلة — حجم الخطوة

\Delta

يحدّد الدقة الزمنية: قيمة صغيرة تلتقط التغيرات السريعة، وقيمة كبيرة ترصد الاتجاهات البطيئة. النقطة المهمة أن

\Delta

*قابل للتعلُّم* — كل طبقة تكتشف بنفسها المقياس الزمني الأنسب لمهمتها.

بعد التقطيع الزمني يصبح النموذج تكراراً خطياً بسيطاً — يشبه تماماً الشبكة التكرارية، لكن بمصفوفات مُهيكلة:

x_k = \bar{A}\,x_{k-1} + \bar{B}\,u_k, \quad y_k = C\,x_k

تكرار نموذج فضاء الحالة المنفصل — المنظور التكراري — في كل خطوة

k

نضرب الحالة السابقة في

\bar{A}

ونضيف المدخل الجديد مضروباً في

\bar{B}

. هذا هو *المنظور التكراري* — وهو المنظور الكفء عند التوليد الذاتي الارتجاعي حين نولّد رمزاً واحداً كل خطوة.

افتح في المختبر

شاهد كيف ينتج فرد التكرار نواة الالتفاف. بدّل بين المنظور التكراري (خطوة بخطوة) والمنظور الالتفافي (حساب متوازٍ).

تستيقظ التجربة عند وصولك…

HiPPO: المصفوفة التي تتذكّر كل شيء

المصفوفة $A$ هي قلب نموذج فضاء الحالة — هي من يحدّد ماذا يتذكر النموذج وماذا ينسى. لو بدأنا بمصفوفة عشوائية لنسي النموذج كل شيء بسرعة. الاختراق جاء من إطار HiPPO (مؤثّر الإسقاط كثير الحدود عالي الرتبة) الذي طوّره المؤلفون أنفسهم في عمل سابق.

الفكرة بسيطة: في كل لحظة $t$ نريد أن تحتفظ الحالة $x(t)$ بـأفضل تقريب بكثيرات الحدود لكامل تاريخ الدخل $u(s)$ حيث $s \leq t$ . تخيّل أنك ترسم منحنى يمرّ بأفضل شكل عبر كل البيانات التي رأيتها حتى الآن، وتُحدّثه باستمرار مع كل نقطة بيانات جديدة. مصفوفة HiPPO هي بالضبط المصفوفة التي تحقق هذا التقريب المثالي المتجدد.

بشكل محدد، صيغة HiPPO-LegS (بمقياس لوجندر المُقيَّس) هي:

A_{nk} = -\begin{cases} (2n+1)^{1/2}(2k+1)^{1/2} & \text{if } n > k \\ n+1 & \text{if } n = k \\ 0 & \text{if } n < k \end{cases}

مصفوفة HiPPO-LegS — ذاكرة كثيرات الحدود المثلى — كل صف

n

يمثّل معامل كثير حدود لوجندر من الدرجة

n

لتاريخ الدخل المتراكم. المعاملات ذات الدرجات المنخفضة تلتقط الاتجاهات العريضة، والدرجات العالية تلتقط التفاصيل الدقيقة. باجتماعها توفّر

N

معاملاً تقريباً مثبتاً رياضياً للتاريخ الكامل.

افتح في المختبر

تابع كيف يُحدّث HiPPO تقريبه بكثيرات الحدود لتاريخ الدخل لحظة بلحظة. كل معامل يرصد مركّبة ترددية مختلفة من الإشارة.

تستيقظ التجربة عند وصولك…

التحدي الحسابي: جعل HiPPO سريعة

HiPPO يمنحنا مصفوفة الذاكرة المثالية، لكن المشكلة أن حساب نواة الالتفاف $\bar{K}$ بالطريقة المباشرة يستلزم حساب جميع قوى $\bar{A}^k$ حيث $k = 0, \ldots, L-1$ . مع مصفوفة كثيفة $N \times N$ وتسلسل بطول $L$ تصبح التكلفة $O(N^2 L)$ — وهذا بطيء جداً عملياً مع أحجام حالة كبيرة.

هنا يأتي الإسهام الجوهري لـ S4: تفكيك بنيوي ذكي. أثبت المؤلفون أن كل مصفوفات HiPPO يمكن كتابتها في صيغة طبيعية زائد منخفضة الرتبة (NPLR):

$A = V \Lambda V^* - PQ^\top$

حيث $V$ أحادية و $\Lambda$ قُطرية و $P, Q$ ذات رتبة $r = 1$ أو $2$ . وبالاقتران مع $V$ نحصل على صيغة قُطرية زائد منخفضة الرتبة (DPLR):

$\tilde{A} = \Lambda - \tilde{P}\tilde{Q}^*$

هذه البنية هي الاختراق الحقيقي: تحوّل حساب النواة إلى تقييم نواة كوشي — وهي مسألة مدروسة جيداً ولها خوارزميات سريعة بتعقيد $O(N \log N)$ عبر تحويل فورييه السريع.

\hat{\bar{K}}_\Omega(z) = \frac{2\Delta}{1+z} \left[ \tilde{C}^\top \left( \frac{2}{\Delta} \frac{1-z}{1+z} - \tilde{A} \right)^{-1} \tilde{B} \right]

نواة S4 في المجال الترددي — الاتصال بنواة كوشي — في مجال تحويل z تأخذ النواة هذه الصيغة المغلقة. بفضل البنية القُطرية زائد منخفضة الرتبة تتحول المعكوسة

(\omega I - \tilde{A})^{-1}

إلى جداء نقطي من نوع كوشي يُقيَّم عند كل الترددات

L

دفعة واحدة بتحويل فورييه السريع.

افتح في المختبر

شاهد كيف تتفكّك مصفوفة HiPPO إلى جزء قُطري وتصحيح منخفض الرتبة، وكيف يُتيح ذلك حساب نواة كوشي بسرعة.

تستيقظ التجربة عند وصولك…

بنية S4 العميقة

طبقة فضاء الحالة الواحدة تربط قناة دخل بقناة خرج. لبناء نموذج عميق عملي يُكدّس S4 عدة طبقات في بنية تشبه كتلة المحوِّل:

كل كتلة تتكوّن من: (1) طبقة SSM خطية تعالج التسلسل، (2) لاخطية (عادةً GELU)، (3) نقطية لخلط السمات، (4) و.

القنوات المتعددة تُعالَج بتشغيل نسخ مستقلة من SSM بالتوازي — نسخة لكل قناة — بأسلوب يشبه . ثم تمزج طبقة خطية المعلومات عبر القنوات.

النموذج الكامل يكدّس 4 إلى 6 كتل من هذا النوع. ورغم بساطة البنية تأتي النتائج قوية، لأن طبقة SSM — بتهيئتها من HiPPO وحجم خطوتها القابل للتعلُّم — تقدّم شيئاً لا تقدّمه أي طبقة أخرى: ذاكرة بعيدة المدى مُثبتة رياضياً مع حساب كفوء.

افتح في المختبر

استكشف بنية كتلة S4: انقر على أي مكوّن لترى كيف تعمل طبقة SSM ودالة التنشيط والشبكة الأمامية والوصلات المتبقية معاً.

تستيقظ التجربة عند وصولك…

النتائج: حلّ ما كان مستحيلاً

نتائج S4 كانت لافتة. على معيار Long Range Arena — ست مهام مصمَّمة لاختبار الفهم بعيد المدى على تسلسلات من ألف إلى ستة عشر ألف خطوة — تفوّق S4 على أحد عشر متغيّراً من المحوِّل وكل النماذج السابقة في كل مهمة بلا استثناء، بمتوسط 80.48% مقابل أقل من 60% لبقية النماذج.

الأكثر إثارة كان Path-X (تسلسل بطول 16,384): مهمة يحتاج فيها النموذج لتحديد ما إذا كانت نقطتان على صورة 128×128 متصلتين بمسار. كل النماذج السابقة — بما فيها جميع المحوِّلات الكفوءة — وقفت عند مستوى التخمين العشوائي (50%). S4 حقّق 94.20%.

وعلى CIFAR-10 التتابعي — تصنيف صور تُعالَج بكسلاً ببكسل في 1,024 خطوة — بلغ S4 دقة 91.13%، وهي تضاهي شبكة ResNet ثنائية الأبعاد رغم أنه يرى الصورة كتسلسل مسطّح أحادي البعد.

وفي أوامر الكلام — تصنيف صوت خام بـ 16,000 عيّنة — حقّق S4 دقة 98.32% على المهمة الكاملة بخمس وثلاثين فئة، متجاوزاً بنيات صوتية متخصصة.

افتح في المختبر

قارن أداء S4 مع المحوِّلات والشبكات التكرارية في مهام Long Range Arena. مرّر على كل مهمة لتشاهد فارق الأداء.

تستيقظ التجربة عند وصولك…

S4 في الكود: الحساب الجوهري

حساب نواة S4 المبسَّطpython

مبسَّط لإظهار الفكرة — ليس التنفيذ الحقيقي.

import torch
import torch.nn as nn
import torch.fft as fft

class S4Kernel(nn.Module):
    """حساب نواة الالتفاف لنموذج S4 باستخدام البنية القُطرية زائد منخفضة الرتبة."""
    def __init__(self, N: int, L: int):
        super().__init__()
        # الجزء القُطري من A (مركّب، قابل للتعلّم)
        self.Lambda = nn.Parameter(torch.randn(N, dtype=torch.cfloat))
        # التصحيح منخفض الرتبة
        self.P = nn.Parameter(torch.randn(N, 1, dtype=torch.cfloat))
        self.Q = nn.Parameter(torch.randn(N, 1, dtype=torch.cfloat))
        self.B = nn.Parameter(torch.randn(N, 1, dtype=torch.cfloat))
        self.C = nn.Parameter(torch.randn(1, N, dtype=torch.cfloat))
        # حجم الخطوة القابل للتعلّم
        self.log_dt = nn.Parameter(torch.randn(1))
        self.L = L

    def forward(self):
        dt = self.log_dt.exp()  # حجم الخطوة
        # تقييم النواة عند L تردد عبر نواة كوشي
        omega = torch.arange(self.L, dtype=torch.cfloat)
        # مبسَّط: الجداء النقطي لكوشي عند كل تردد
        # النسخة الكاملة تستخدم Woodbury للتصحيح منخفض الرتبة
        z = 2 * (1 - omega) / (1 + omega)  # تحويل ثنائي الخطوط
        vals = (z.unsqueeze(-1) - self.Lambda.unsqueeze(0))
        K_hat = (self.C @ (1.0 / vals * self.B)).squeeze(-1)
        # العودة إلى المجال الزمني
        K = fft.ifft(K_hat, n=self.L).real
        return K  # الشكل: (L,)

ثورة نماذج فضاء الحالة: من HiPPO إلى Mamba

2020
HiPPO — أساس الذاكرة
طرح Gu وآخرون إطار HiPPO وأثبتوا أن مصفوفات بعينها تستطيع تقريب تاريخ إشارة متصلة عبر إسقاطات كثيرات الحدود. هذا حلّ مشكلة الذاكرة النظرية لنماذج فضاء الحالة.
2021
LSSL — الجمع بين الشبكات التكرارية والالتفافية ونماذج فضاء الحالة
بيّنت طبقة فضاء الحالة الخطي أن نماذج فضاء الحالة يمكن التعامل معها كنماذج تكرارية والتفافية في آن واحد، فأرست المنظور المزدوج الذي بنى عليه S4 لاحقاً.
2022
S4 — الاختراق المُهيكل (هذه الورقة)
حلّ S4 عنق الزجاجة الحسابي عبر تفكيك DPLR، فحقّق أفضل النتائج على Long Range Arena وحلّ مهمة Path-X لأول مرة. نُشر في ICLR 2022 كعرض شفهي.
2022
S4D وDSS — تبسيطات قُطرية
أظهر Gupta وآخرون وGu وآخرون أن المَعلَمة القُطرية البحتة تكفي لمطابقة أداء S4 مع تبسيط كبير في التنفيذ، والإبقاء على تهيئة مستوحاة من HiPPO.
2023
Mamba — فضاءات الحالة الانتقائية
أدخل Gu وDao آلية اختيار تعتمد على المدخلات، فصارت المصفوفتان B وC دوالاً في المدخل. كسر ذلك الثبات الزمني الخطي لكنه جعل نماذج فضاء الحالة تنافس المحوِّلات في النمذجة اللغوية لأول مرة.

أثبت S4 أن المسافة بين نظرية الأنظمة الديناميكية الكلاسيكية والتعلم العميق الحديث لم تكن فجوة بل جسراً ينتظر من يبنيه. حين أظهر أن المصفوفات المُهيكلة من نظرية التحكم تتفوق على الانتباه في أصعب مهام التسلسلات، فتح الباب أمام عائلة جديدة كلياً من نماذج التسلسلات تنافس اليوم منظومة المحوِّل.

المرجعGu, Goel, Ré. Efficiently Modeling Long Sequences with Structured State Spaces. ICLR, 2022.

مصطلحات هذه الورقة

نموذج فضاء الحالةState Space Model
HiPPOHiPPO
التمييزDiscretization
الالتفاف الرقميConvolution
الشبكة العصبية التكراريةRecurrent Neural Network (RNN)
الاعتمادية البعيدة المدىLong-Term Dependency
نواة كوشيCauchy Kernel
قُطرية زائد منخفضة الرتبةDiagonal Plus Low-Rank
ثبات الزمن الخطّيLinear Time Invariance
مرشِّح كالمنKalman Filter
المسح المتوازيParallel Scan
الشبكة العصبية الالتفافيةConvolutional Neural Network (CNN)
اضمحلال متجهات الميلVanishing Gradient
نمذجة التتابعاتSequence Modeling
دالة التنشيطActivation Function