K-SVD: خوارزمية لتصميم قواميس زائدة الاكتمال للتمثيل المُتفرِّق

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

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

القاموس زائد الاكتمال يحتوي على ذرّات أكثر من أبعاد الإشارة ($K > n$). هذه الوفرة تعني أن لكل إشارة طرقًا عديدة لتفكيكها — لكن قيد التفرُّق يفرض اختيار التفكيك الذي يستعمل أقل عدد ممكن من الذرّات. الأمر أشبه بصندوق أدوات واسع: كلما زادت الأدوات المتاحة، استطعت اختيار الأنسب لكل مهمة وتقليل ما تحتاجه فعلاً.

نبدأ من المعطيات: لدينا $N$ إشارة تدريب $\{y_i\}$، كل منها متجه بـ$n$ بُعدًا. المطلوب إيجاد قاموس $D$ مكوّن من $K$ ذرّة (أعمدة المصفوفة) ومصفوفة معاملات مُتفرِّقة $X$ بحيث $Y \approx DX$، وكل عمود في $X$ يحتوي على عدد قليل جدًّا من القيم غير الصفرية. بعبارة أخرى، نريد تقليل خطأ إعادة البناء الإجمالي مع فرض قيد تفرُّق على كل متجه معاملات.

هذه المسألة صعبة لأن أمثَلة $D$ و$X$ معًا مسألة غير محدّبة — لا يوجد حل مباشر. الحيلة التي تستخدمها K-SVD هي التناوب: نُثبِّت القاموس $D$ ونبحث عن أفضل رموز $X$ (الترميز المُتفرِّق)، ثم نُثبِّت $X$ ونُحسِّن $D$ عمودًا عمودًا (تحديث القاموس). هذا الأسلوب التناوبي مألوف — فهو يُشبه خوارزمية EM ويُشبه k-means نفسها.

أسهل طريقة لفهم K-SVD هي أن نراها تعميمًا طبيعيًّا لـالعنقدة بأسلوب K-means. في K-means، كل نقطة بيانات تُنسب إلى مركز عنقود واحد — أقرب نقطة مركزية إليها. وهذا يعني عمليًّا أننا نُمثِّل كل إشارة بذرّة واحدة فقط بمعامل قدره 1، أي أقصى درجات التفرُّق ($T_0 = 1$).

K-SVD ترفع هذا القيد وتسمح لكل إشارة باستخدام حتى $T_0$ ذرّة بأوزان مختلفة. الفرق جوهري: K-means تُقسّم البيانات إلى مجموعات منفصلة، بينما K-SVD تسمح بتمثيلات مرنة متداخلة. مثلاً، صورة وجه يمكن أن تستخدم ذرّة لمنطقة العينين وأخرى للأنف وثالثة للفك — وهذا مستحيل مع K-means التي تُجبرك على اختيار «أقرب وجه واحد» فقط.

اسم «K-SVD» يعكس هذا الأصل: K ذرّة يجري تحديثها بتحليل القيمة المفردة.

في هذه المرحلة لدينا القاموس الحالي $D$ ونريد إيجاد أكثر تمثيل مُتفرِّق ممكن لكل إشارة تدريب. تستخدم K-SVD لهذا الغرض خوارزمية المُطاردة المتعامدة الجشعة (OMP) — وهي خوارزمية جشعة تبني التمثيل ذرّة تلو الأخرى.

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

تخيّل محققًا يحل قضية: يبدأ بالدليل الأهم، ثم ينتقل إلى الدليل التالي الأهم بعد استبعاد ما فسّره الدليل الأول، وهكذا حتى تكتمل الصورة.

هنا نصل إلى الابتكار الجوهري الذي يُميّز K-SVD. بعد مرحلة الترميز المُتفرِّق أصبح لدينا معاملات $X$ ونريد تحسين كل ذرّة $d_k$ (العمود $k$ في القاموس $D$).

الملاحظة المفتاحية: حين نُحدّث ذرّة معيّنة $d_k$، يمكننا عزل مساهمتها وحدها. التمثيل الكلي $DX$ عبارة عن مجموع حدود من الرتبة الأولى — كل ذرّة مضروبة في صف معاملاتها. إذا أزلنا مساهمة الذرّة $k$، نحصل على خطأ المتبقّي $E_k$:

المطلوب الآن إيجاد أفضل $d_k$ وصف معاملاتها $x_T^k$ اللذين يُقلِّلان $\|E_k - d_k x_T^k\|_F^2$. هذه في جوهرها مسألة تقريب مصفوفة بمصفوفة من الرتبة الأولى — وأفضل تقريب من هذا النوع يُعطيه مباشرةً تحليل القيمة المفردة (SVD).

لكن هناك نقطة دقيقة وحاسمة: لا يمكننا تطبيق SVD على $E_k$ بالكامل. لماذا؟ لأن ذلك سيُولِّد معاملات غير صفرية لإشارات لم تكن تستخدم الذرّة $k$ أصلاً، فيتحطّم التفرُّق الذي اجتهدنا لبنائه. الحل: تُقيّد K-SVD التحديث بالإشارات التي تستخدم الذرّة $k$ فعلاً فقط — أي المجموعة $\omega_k = \{i : x_k^i \neq 0\}$. نبني مصفوفة مقيَّدة $E_k^R$ من هذه الأعمدة وحدها، ونُطبّق عليها SVD، فنُحدِّث الذرّة ومعاملاتها غير الصفرية معًا في خطوة واحدة.

بتجميع المرحلتين تعمل K-SVD كالتالي: أولاً، الترميز المُتفرِّق — نستخدم OMP لإيجاد أفضل تمثيل مُتفرِّق لكل إشارة تدريب بالقاموس الحالي. ثانيًا، تحديث القاموس — لكل ذرّة $k = 1, \ldots, K$ نحسب المتبقّي المُقيَّد $E_k^R$ ونُطبّق SVD من الرتبة الأولى ونُحدِّث الذرّة ومعاملاتها معًا. ثم نُكرّر حتى يتحقق التقارب.

النقطة المهمة: كل تكرار مضمون أن يُقلِّل خطأ التمثيل الكلي أو يُبقيه كما هو على الأقل. عمليًّا تتقارب الخوارزمية في حدود 10 إلى 50 تكرارًا.

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

أظهر الأد وأهارون (2006) أن إزالة الضجيج بـ K-SVD حققت أعلى نسبة إشارة إلى ضجيج ذروية (PSNR) على المعايير القياسية، متفوّقةً على المويجات والطرق المنافسة المتاحة حينها.