التكميم بأقل مربّعات الخطأ في تعديل الشفرة النبضية

حين تتحدث في الهاتف، يكون صوتك إشارة كهربائية متصلة تتغيّر مع الزمن. لإرسالها رقمياً، نأخذ منها عيّنات على فترات منتظمة ثم نقرِّب كل عيّنة إلى واحدة من $N$ قيمة مسموحة — هذا التقريب هو ما نسمّيه التكميم. القيم المقرَّبة تُعرف بـقيم الإعادة أو المراكز الثقلية.

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

السؤال الذي طرحه لويد: إذا كنّا نعرف دالة الكثافة الاحتمالية للإشارة، أين نضع مستويات التكميم الـ $N$ بالضبط حتى يصبح متوسط الخطأ المربّع أصغر ما يمكن؟

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

القاعدة الأولى — شرط الجار الأقرب. كل عيّنة تُسنَد إلى أقرب مستوى تكميم إليها. مثلاً، إذا كانت العيّنة عند جهد 3.7 وكان لدينا مستويان عند 3.0 و4.0، فالعيّنة تذهب إلى 4.0 لأنه الأقرب. النتيجة المباشرة: حدّ القرار بين مستويين متجاورين يقع تماماً عند نقطة المنتصف بينهما.

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

هذان الشرطان ضروريان — خرقُ أيٍّ منهما يعني أن بإمكانك خفض الخطأ بتصحيح المخالفة. وباجتماعهما يتحدّد شكل أي مُكمِّم أمثل محلياً.

لنفترض أن سعة الإشارة $x$ تتبع دالة كثافة احتمالية $p(x)$. المُكمِّم ذو المستويات الـ $N$ يقسم خطّ الأعداد الحقيقية إلى $N$ فترة $[t_{i-1}, t_i)$، وفي كل فترة توجد قيمة إعادة $q_i$. الهدف هو تصغير التشوّه — وهو الفرق التربيعي المتوقع بين الإشارة الأصلية ونسختها بعد التكميم.

لنثبّت مستويات التكميم $q_i$ ونسأل: أين يقع حدّ القرار $t_i$ بين المستويين المتجاورين $q_i$ و$q_{i+1}$؟ عيّنة تقع عند $x = t_i$ تبعد المسافة نفسها عن كلا المستويين، لذا لا فرق في إسنادها. ما يسار هذه النقطة أقرب إلى $q_i$، وما يمينها أقرب إلى $q_{i+1}$. إذن الحدّ الذي يصغّر التشوّه هو ببساطة نقطة المنتصف:

لنثبّت الآن الحدود $t_i$ ونسأل: أين يجب أن يقع مستوى التكميم $q_i$ داخل فترته $[t_{i-1}, t_i)$؟ القيمة التي تصغّر الخطأ التربيعي لعيّنات تلك الفترة هي متوسطها المرجّح بالاحتمال — أي التوقع الشرطي:

لا يمكن لشرط واحد أن يعطي الحلّ الكامل — فالحدود تتوقف على المستويات، والمستويات تتوقف على الحدود. الفكرة المحورية عند لويد هي التناوب بينهما:

الخطوة 0 — التهيئة. اختر $N$ مستوى تكميم ابتدائي (عشوائياً أو بالتساوي). الخطوة 1 — الإسناد. ضع كل حدّ $t_i$ عند نقطة المنتصف بين المستويين المتجاورين (شرط الجار الأقرب). الخطوة 2 — التحديث. حرِّك كل مستوى $q_i$ إلى مركز ثقل العيّنات في فترته (شرط مركز الثقل). كرِّر الخطوتين 1 و2 حتى تتوقف المستويات عن التغيّر (التقارب).

في كل دورة، الخطوة الأولى لا يمكنها إلا أن تُنقص $D$ أو تُبقيه كما هو، والأمر ذاته ينطبق على الخطوة الثانية. وبما أن $D$ لا يمكن أن يقلّ عن الصفر، فلا بدّ أن تتقارب المتتالية.

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

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

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

لدينا $N$ نقطة وسحابة بيانات: (1) اربط كل عنصر بأقرب نقطة (تقسيم فورونوي)، (2) حرِّك كل نقطة إلى مركز ثقل خليّتها. كرِّر.

هذا بالضبط ما نسمّيه العنقَدة بالمتوسطات (k-means) — من أوسع الخوارزميات انتشاراً في تعلّم الآلة وعلم البيانات. أصل الخوارزمية هو تقرير لويد الفني غير المنشور من عام 1957، وإن كان فورغي قد توصّل إليها مستقلاً عام 1965، ثم أطلق عليها ماكوين اسم «k-means» عام 1967. حين نُشرت الورقة أخيراً عام 1982 انتشرت على نطاق واسع ورسّخت مكانتها في الأدبيات.

أثبت لويد أيضاً أنه كلّما كبر عدد المستويات $N$، يقترب حلّه المحدود من نتيجة معروفة منذ 1951: الكثافة المقاربية لمستويات التكميم ينبغي أن تتناسب مع $p(x)^{1/3}$ حيث $p(x)$ هي كثافة الإشارة الاحتمالية. المعنى العملي: منطقة يُحتمل أن تظهر فيها الإشارة 8 أضعاف لا تحتاج إلا $8^{1/3} = 2$ ضعف عدد المستويات فحسب — وليس 8 أضعاف. هذا القانون التكعيبي يوازن بين فائدة الدقة العالية في المناطق الكثيفة وبين تناقص العائد من حشد مستويات كثيرة فيها.