نظرية معدل التشوه

تُعد نظرية معدل التشوه فرعًا رئيسيًا من نظرية المعلومات التي توفر الأسس النظرية لضغط البيانات مع فقدان البيانات ؛ وهي تعالج مشكلة تحديد الحد الأدنى لعدد البتات لكل رمز، كما هو مُقاس بالمعدل R ، الذي يجب نقله عبر قناة، بحيث يمكن إعادة بناء المصدر (إشارة الإدخال) تقريبًا عند جهاز الاستقبال (إشارة الإخراج) دون تجاوز التشوه المتوقع D.

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

تم ابتكار نظرية معدل التشوه بواسطة كلود شانون في عمله التأسيسي حول نظرية المعلومات.

في نظرية معدل التشوه، يُفهم المعدل عادةً على أنه عدد البتات لكل عينة بيانات يتم تخزينها أو إرسالها. أما مفهوم التشوه فهو موضوع نقاش مستمر. ^{[ 1 ]} في أبسط الحالات (وهي الأكثر شيوعًا)، يُعرَّف التشوه بأنه القيمة المتوقعة لمربع الفرق بين إشارة الإدخال وإشارة الإخراج (أي متوسط ​​مربع الخطأ ). مع ذلك، ولأننا نعلم أن معظم تقنيات الضغط مع فقدان البيانات تعمل على بيانات سيُدركها المستخدمون (الاستماع إلى الموسيقى ، ومشاهدة الصور والفيديوهات)، يُفضَّل أن يُصمَّم مقياس التشوه بناءً على الإدراك البشري ، وربما على الجماليات أيضًا : فكما هو الحال مع استخدام الاحتمالية في الضغط بدون فقدان البيانات ، يمكن في النهاية ربط مقاييس التشوه بدوال الخسارة المستخدمة في التقدير البايزي ونظرية القرار . في ضغط الصوت، تُعد النماذج الإدراكية (وبالتالي مقاييس التشوه الإدراكي) متطورة نسبيًا وتُستخدم بشكل روتيني في تقنيات الضغط مثل MP3 أو Vorbis ، ولكن غالبًا ما يصعب تضمينها في نظرية معدل التشوه. في ضغط الصور والفيديو، تكون نماذج الإدراك البشري أقل تطوراً، ويقتصر تضمينها في الغالب على مصفوفة ترجيح JPEG و MPEG ( التكميم ، والتطبيع ).

تقيس دوال التشوه تكلفة تمثيل الرمز${\displaystyle x}$بواسطة رمز تقريبي${\displaystyle {\hat {x}}}$. وظائف التشوه النموذجية هي تشوه هامينغ وتشوه الخطأ التربيعي.

يتم إيجاد الدوال التي تربط بين المعدل والتشويه كحل لمسألة التصغير التالية:

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}I_{Q}(Y;X){\text{ بشرط }}D_{Q}\leq D^{*}.}$

هنا${\displaystyle Q_{Y\mid X}(y\mid x)}$تُسمى أحيانًا قناة الاختبار، وهي دالة كثافة الاحتمال الشرطي (PDF) لمخرج قناة الاتصال (الإشارة المضغوطة).${\displaystyle Y}$بالنسبة لمدخل معين (الإشارة الأصلية)${\displaystyle X}$، و${\displaystyle I_{Q}(Y;X)}$المعلومات المتبادلة بين${\displaystyle Y}$و${\displaystyle X}$يُعرَّف بأنه

${\displaystyle I(Y;X)=H(Y)-H(Y\mid X)\,}$

أين${\displaystyle H(Y)}$و${\displaystyle H(Y\mid X)}$تمثل و على التوالي إنتروبيا إشارة الخرج Y والإنتروبيا الشرطية لإشارة الخرج بالنظر إلى إشارة الدخل:

${\displaystyle H(Y)=-\int _{-\infty}^{\infty }P_{Y}(y)\log _{2}(P_{Y}(y))\,dy}$

${\displaystyle H(Y\mid X)=-\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)\log _{2}(Q_{Y\mid X}(y\mid x))\,dx\,dy.}$

يمكن صياغة المسألة أيضاً كدالة معدل التشوه، حيث نجد الحد الأدنى للتشوهات الممكنة في ظل قيد معدل معين. والصيغة ذات الصلة هي:

${\displaystyle \inf _{Q_{Y\mid X}(y\mid x)}E[D_{Q}[X,Y]]{\text{ subject to }}I_{Q}(Y;X)\leq R.}$

تؤدي الصيغتان إلى وظائف معكوسة لبعضها البعض.

يمكن فهم المعلومات المتبادلة على أنها مقياس للشك "المسبق" الذي يشعر به المتلقي بشأن إشارة المرسل ( H ( Y ))، والذي يتضاءل بسبب الشك المتبقي بعد تلقي المعلومات حول إشارة المرسل (${\displaystyle H(Y\mid X)}$بالطبع، يعود انخفاض مستوى عدم اليقين إلى كمية المعلومات المُتبادلة، والتي هي${\displaystyle I\left(Y;X\right)}$.

على سبيل المثال، في حالة انعدام التواصل تماماً،${\displaystyle H(Y\mid X)=H(Y)}$و${\displaystyle I(Y;X)=0}$أو بدلاً من ذلك، إذا كانت قناة الاتصال مثالية والإشارة المستلمة${\displaystyle Y}$هو مطابق للإشارة${\displaystyle X}$ثم إلى المرسل${\displaystyle H(Y\mid X)=0}$و${\displaystyle I(Y;X)=H(X)=H(Y)}$.

في تعريف دالة معدل التشوه،${\displaystyle D_{Q}}$و${\displaystyle D^{*}}$التشوه بين${\displaystyle X}$و${\displaystyle Y}$بالنسبة لـ${\displaystyle Q_{Y\mid X}(y\mid x)}$والتشويه الأقصى المحدد، على التوالي. عند استخدام متوسط ​​مربع الخطأ كمقياس للتشويه، نحصل ( للإشارات ذات السعة المستمرة ):

${\displaystyle D_{Q}=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }P_{X,Y}(x,y)(xy)^{2}\,dx\,dy=\int _{-\infty }^{\infty }\int _{-\infty }^{\infty }Q_{Y\mid X}(y\mid x)P_{X}(x)(xy)^{2}\,dx\,dy.}$

كما توضح المعادلات أعلاه، فإن حساب دالة معدل التشوه يتطلب الوصف العشوائي للمدخلات${\displaystyle X}$فيما يتعلق بملف PDF${\displaystyle P_{X}(x)}$ثم يهدف إلى إيجاد دالة كثافة الاحتمال الشرطية${\displaystyle Q_{Y\mid X}(y\mid x)}$التي تقلل معدل التشوه المحدد${\displaystyle D^{*}}$. يمكن صياغة هذه التعريفات من الناحية النظرية القياسية لتفسير المتغيرات العشوائية المنفصلة والمختلطة أيضًا.

غالباً ما يصعب إيجاد حل تحليلي لمسألة التصغير هذه، باستثناء بعض الحالات التي سنقدم فيها مثالين من أشهرها. من المعروف أن دالة معدل التشوه لأي مصدر تخضع لعدة خصائص أساسية، أهمها أنها دالة مستمرة ، متناقصة بشكل رتيب، ومحدبة (U) ، وبالتالي فإن شكل الدالة في الأمثلة نموذجي (حتى دوال معدل التشوه المقاسة في الواقع العملي تميل إلى أن تكون لها أشكال متشابهة جداً).

على الرغم من ندرة الحلول التحليلية لهذه المشكلة، إلا أن هناك حدودًا عليا ودنيا لهذه الدوال، بما في ذلك حد شانون الأدنى الشهير (SLB)، والذي ينص في حالة الخطأ التربيعي والمصادر عديمة الذاكرة، على أنه بالنسبة للمصادر العشوائية ذات الإنتروبيا التفاضلية المحدودة،

${\displaystyle R(D)\geq h(X)-h(D)\,}$

حيث h ( D ) هي الإنتروبيا التفاضلية لمتغير عشوائي غاوسي ذي تباين D. هذا الحد الأدنى قابل للتعميم على المصادر ذات الذاكرة ومقاييس التشوه الأخرى. من السمات المهمة لحدود شانون الدنيا أنها دقيقة تقاربياً في نطاق التشوه المنخفض لفئة واسعة من المصادر، وفي بعض الحالات، تتطابق تماماً مع دالة معدل التشوه. يمكن إيجاد حدود شانون الدنيا عموماً إذا أمكن التعبير عن التشوه بين أي عددين كدالة للفرق بين قيمتي هذين العددين.

تُعد خوارزمية Blahut–Arimoto ، التي شارك في اختراعها ريتشارد بلاهوت ، تقنية تكرارية أنيقة للحصول عدديًا على دوال معدل التشوه لمصادر أبجدية الإدخال/الإخراج المحدودة التعسفية، وقد تم بذل الكثير من العمل لتوسيعها لتشمل حالات مشاكل أكثر عمومية.

يتطلب حساب دالة معدل التشوه معرفة التوزيع الأساسي، وهو أمر غالبًا ما يكون غير متوفر في التطبيقات المعاصرة في علوم البيانات والتعلم الآلي. مع ذلك، يمكن التغلب على هذا التحدي باستخدام مُقدِّرات دالة معدل التشوه القائمة على التعلم العميق. ^{[ 2 ]} تُعرف هذه المُقدِّرات عادةً باسم "المُقدِّرات العصبية"، وتتضمن تحسين شكل تبايني مُعَلم لهدف معدل التشوه.

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

${\displaystyle R(D)=\lim _{n\rightarrow \infty }R_{n}(D)}$

أين

${\displaystyle R_{n}(D)={\frac {1}{n}}\inf _{Q_ {Y^{n}\mid X^{n}}\in {\mathcal {Q}}}I(Y^{n},X^{n})}$

و

${\displaystyle {\mathcal {Q}}=\{Q_{Y^{n}\mid X^{n}}(Y^{n}\mid X^{n},X_{0}):E[d(X^{n},Y^{n})]\leq D\}}$

حيث تشير الأرقام المرتفعة إلى تسلسل كامل حتى ذلك الوقت، ويشير الرقم السفلي 0 إلى الحالة الأولية.

لنفترض أننا نريد نقل معلومات حول مصدر ما إلى المستخدم مع تشويه لا يتجاوز D. تخبرنا نظرية معدل التشويه أن على الأقل${\displaystyle R(D)}$يجب أن تصل بتات/رمز من المعلومات من المصدر إلى المستخدم. ونعلم أيضًا من نظرية ترميز قناة شانون أنه إذا كانت إنتروبيا المصدر H بت/رمز، وسعة القناة C (حيث${\displaystyle C<H}$)، ثم${\displaystyle H-C}$ستُفقد بعض البتات/الرموز عند إرسال هذه المعلومات عبر القناة المحددة. ولكي يتمكن المستخدم من إعادة بناء الصورة بأقصى تشويه D ، يجب أن نفرض شرطًا ألا تتجاوز المعلومات المفقودة أثناء الإرسال الحد الأقصى المسموح به للفقد.${\displaystyle H-R(D)}$بت/رمز. هذا يعني أن سعة القناة يجب أن تكون على الأقل بحجم${\displaystyle R(D)}$[ ^{5 ]​}

• خوارزمية بلاهوت-أريموتو – فئة من الخوارزميات في نظرية المعلومات 
• ضغط البيانات – ترميز مضغوط للبيانات الرقمية 
• فك الارتباط - عملية تقليل الارتباط داخل إشارة واحدة أو أكثر 
• تحسين معدل التشوه
• تعبئة الكرات – ترتيب الكرات داخل حيز مكاني 
• الضوضاء البيضاء – نوع من أنواع الإشارات في معالجة الإشارات 

• مارزن، سارة؛ ديديو، سيمون. "PyRated: حزمة بايثون لنظرية معدل التشوه" . PyRated هي حزمة بايثون بسيطة للغاية لإجراء أبسط العمليات الحسابية في نظرية معدل التشوه: تحديد "دفتر الشفرات" ومعدل الإرسال R ، بمعلومية دالة المنفعة (مصفوفة التشوه) ومضاعف لاغرانج بيتا .
• أداة VcDemo لتعليم ضغط الصور والفيديو