التكميم المتجهي

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة

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

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

يعتمد التكميم المتجهي على نموذج التعلم التنافسي ، لذا فهو يرتبط ارتباطًا وثيقًا بنموذج الخريطة ذاتية التنظيم ونماذج الترميز المتفرقة المستخدمة في خوارزميات التعلم العميق مثل المشفر التلقائي .

تمرين

إحدى خوارزميات التدريب البسيطة لتكميم المتجهات هي: [ 1 ]

  1. اختر نقطة عينة عشوائياً
  2. حرك مركز متجه التكميم الأقرب نحو نقطة العينة هذه، بمقدار صغير من المسافة
  3. يكرر

تعمل خوارزمية أكثر تطوراً على تقليل التحيز في تقدير مطابقة الكثافة وتضمن استخدام جميع النقاط، وذلك من خلال تضمين معلمة حساسية إضافية:

  1. قم بزيادة حساسية كل مركزsأنا{\displaystyle s_{i}}بمقدار ضئيل
  2. اختر نقطة عينةP{\displaystyle P}عشوائيا
  3. لكل مركز متجه التكميمجأنا{\displaystyle c_{i}}، يتركد(P،جأنا){\displaystyle d(P,c_{i})}تشير إلى مسافةP{\displaystyle P}وجأنا{\displaystyle c_{i}}
  4. أوجد مركز الثقلجأنا{\displaystyle c_{i}}والتيد(P،جأنا)-sأنا{\displaystyle d(P,c_{i})-s_{i}}هو الأصغر
  5. يتحركجأنا{\displaystyle c_{i}}تجاهP{\displaystyle P}بجزء صغير من المسافة
  6. تعيينsأنا{\displaystyle s_{i}}إلى الصفر
  7. يكرر

يُفضّل استخدام جدول تبريد لتحقيق التقارب: انظر التلدين المحاكي . وهناك طريقة أخرى بسيطة هي LBG ، والتي تعتمد على خوارزمية k-means .

يمكن تحديث الخوارزمية بشكل متكرر باستخدام البيانات "الحية"، بدلاً من اختيار نقاط عشوائية من مجموعة بيانات، ولكن هذا سيؤدي إلى إدخال بعض التحيز إذا كانت البيانات مرتبطة زمنيًا عبر العديد من العينات.

التطبيقات

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

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

لتقدير الكثافة ، فإن المساحة/الحجم الأقرب إلى مركز معين من أي مركز آخر يتناسب عكسيًا مع الكثافة (بسبب خاصية مطابقة الكثافة للخوارزمية).

يُستخدم في ضغط البيانات

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

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

يتم تكميم مجموعة مستويات السعة المنفصلة بشكل مشترك بدلاً من تكميم كل عينة على حدة. لنفترض متجهًا ذا k بُعد[x1،x2،...،xك]{\displaystyle [x_{1},x_{2},...,x_{k}]}من مستويات السعة. يتم ضغطها عن طريق اختيار أقرب متجه مطابق من مجموعة من المتجهات ذات الأبعاد n[y1،y2،...،yن]{\displaystyle [y_{1},y_{2},...,y_{n}]}، حيث n < k .

جميع التوليفات الممكنة للمتجه ذي الأبعاد n[y1،y2،...،yن]{\displaystyle [y_{1},y_{2},...,y_{n}]}تشكل الفضاء المتجهي الذي تنتمي إليه جميع المتجهات الكمية.

يتم إرسال فهرس كلمة التشفير فقط في دفتر التشفير بدلاً من القيم الكمية. هذا يوفر مساحة ويحقق ضغطًا أكبر.

تعتبر تقنية التكميم المتجهي المزدوج (VQF) جزءًا من معيار MPEG-4 الذي يتعامل مع التكميم المتجهي المتداخل الموزون في المجال الزمني.

برامج ترميز الفيديو القائمة على التكميم المتجهي

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

برامج ترميز الصوت القائمة على التكميم المتجهي

يُستخدم في التعرف على الأنماط

استُخدمت تقنية التكميم المتجهي (VQ) أيضًا في ثمانينيات القرن الماضي في مجال التعرف على الكلام [ 5 ] والتعرف على المتحدثين [ 6 ] . ومؤخرًا، استُخدمت أيضًا في البحث الفعال عن أقرب جار [ 7 ] والتعرف على التوقيعات عبر الإنترنت [ 8 ] . في تطبيقات التعرف على الأنماط ، يُنشأ دفتر رموز لكل فئة (كل فئة تمثل مستخدمًا في التطبيقات البيومترية) باستخدام المتجهات الصوتية لهذا المستخدم. في مرحلة الاختبار، يُحسب تشوه التكميم لإشارة الاختبار باستخدام مجموعة دفاتر الرموز الكاملة التي تم الحصول عليها في مرحلة التدريب. ويشير دفتر الرموز الذي يوفر أقل تشوه تكميم متجهي إلى المستخدم المُحدد.

تتمثل الميزة الرئيسية لتقنية VQ في التعرف على الأنماط في انخفاض متطلباتها الحسابية مقارنةً بتقنيات أخرى مثل مطابقة الوقت الديناميكية (DTW) ونموذج ماركوف المخفي (HMM). أما عيبها الرئيسي مقارنةً بتقنيتي DTW وHMM فهو عدم مراعاتها للتطور الزمني للإشارات (الكلام، التوقيع، إلخ) نظرًا لاختلاط جميع المتجهات. وللتغلب على هذه المشكلة، تم اقتراح منهجية دفتر الشفرات متعدد الأقسام. [ 9 ] تتضمن هذه المنهجية نمذجة الإشارة باستخدام عدة أقسام (على سبيل المثال، دفتر شفرات للجزء الأولي، وآخر للوسط، وثالث للنهاية).

استخدم كخوارزمية تجميع

بما أن خوارزمية التكميم المتجهي (VQ) تبحث عن مراكز الكثافة كنقاط لعينات متقاربة، فيمكن استخدامها مباشرةً كطريقة تجميع قائمة على النماذج الأولية: حيث يُربط كل مركز كثافة بنموذج أولي واحد. ومن خلال السعي لتقليل خطأ التكميم التربيعي المتوقع [ 10 ] ، وإدخال كسب تعلم متناقص يحقق شروط روبنز-مونرو، فإن تكرارات متعددة على مجموعة البيانات بأكملها مع عدد محدد وثابت من النماذج الأولية تتقارب تدريجيًا نحو حل خوارزمية التجميع k-means .

الشبكات التوليدية التنافسية (GAN)

استُخدمت تقنية التكميم المتجهي (VQ) لتكميم طبقة تمثيل الميزات في مُميّز الشبكات التوليدية التنافسية . تُجري تقنية تكميم الميزات (FQ) مطابقة ضمنية للميزات. [ 11 ] تُحسّن هذه التقنية تدريب الشبكات التوليدية التنافسية، وتُحقق أداءً مُحسّنًا على مجموعة متنوعة من نماذج الشبكات التوليدية التنافسية الشائعة: BigGAN لتوليد الصور، وStyleGAN لتوليف الوجوه، وU-GAT-IT للترجمة غير الخاضعة للإشراف من صورة إلى أخرى.

انظر أيضاً

المواضيع الفرعية

مواضيع ذات صلة

استند جزء من هذه المقالة في الأصل إلى مواد من قاموس الحوسبة المجاني على الإنترنت، ويتم استخدامه بإذن بموجب رخصة GFDL.

مراجع

  1. ↑ دانا هـ. بالارد (2000). مقدمة في الحوسبة الطبيعية . مطبعة معهد ماساتشوستس للتكنولوجيا. ص  189. ISBN 978-0-262-02420-4.
  2. ↑ "فيديو بينك" . كتاب الحكمة . 27-12-2009 . تم الاطلاع عليه بتاريخ 16-03-2013 .
  3. ↑ فالين، ج.م. (أكتوبر 2012). التكميم المتجهي الهرمي لترميز الفيديو . IETF . المعرف draft-valin-videocodec-pvq-00 . تاريخ الاسترجاع 17-12-2013 .انظر أيضًا arXiv:1602.05209
  4. ↑ "مواصفات Vorbis I" . Xiph.org. 2007-03-09 . تم الاطلاع عليه بتاريخ 2007-03-09 .
  5. ↑ بيرتون، د.ك.؛ شور، ج.إ.؛ باك، ج.ت. (1983). "تعميم التعرف على الكلمات المنفردة باستخدام التكميم المتجهي". المؤتمر الدولي لهندسة الصوت والكلام ومعالجة الإشارات (ICASSP '83). المجلد 8. الصفحات 1021-1024 . doi : 10.1109 /ICASSP.1983.1171915 .  
  6. ↑Soong, F.; A. Rosenberg; L. Rabiner; B. Juang (1985). "A vector quantization approach to speaker recognition". ICASSP '85. IEEE International Conference on Acoustics, Speech, and Signal Processing. Vol. 1. pp. 387–390. doi:10.1109/ICASSP.1985.1168412. S2CID 8970593.
  7. ↑H. Jegou; M. Douze; C. Schmid (2011). "Product Quantization for Nearest Neighbor Search"(PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 33 (1): 117–128. CiteSeerX 10.1.1.470.8573. doi:10.1109/TPAMI.2010.57. PMID 21088323. S2CID 5850884. Archived(PDF) from the original on 2011-12-17.
  8. ↑Faundez-Zanuy, Marcos (2007). "offline and On-line signature recognition based on VQ-DTW". Pattern Recognition. 40 (3): 981–992. doi:10.1016/j.patcog.2006.06.007.
  9. ↑Faundez-Zanuy, Marcos; Juan Manuel Pascual-Gaspar (2011). "Efficient On-line signature recognition based on Multi-section VQ". Pattern Analysis and Applications. 14 (1): 37–45. doi:10.1007/s10044-010-0176-8. S2CID 24868914.
  10. ↑Gray, R.M. (1984). "Vector Quantization". IEEE ASSP Magazine. 1 (2): 4–29. doi:10.1109/massp.1984.1162229. hdl:2060/19890012969.
  11. ↑Yang Zhao; Chunyuan Li; Ping Yu; Jianfeng Gao; Changyou Chen (15 Jul 2020). "Feature Quantization Improves GAN Training". arXiv:2004.02088 [cs.LG].