أنماط تصميم تمثيل البيانات :السمة المجزأة

يعالج نمط تصميم السمة المجزأة (Hashed Feature)  ثلاث مشكلات محتملة في تمثيل البيانات المرتبطة بالسمات الفئوية: المفردات غير المكتملة ، وحجم النموذج بسبب العناصر في المجموعة ، و البداية الباردة (cold start). يقوم بذلك عن طريق تجميع السمات الفئوية وقبول مفاضلة التصادمات في تمثيل البيانات.

المشكلة

خط الترميز الأحادي (One-hot encoding) هو متغير إدخال فئوي  يتطلب معرفة المفردات مسبقًا. هذه ليست مشكلة إذا كان متغير الإدخال شيء مثل اللغة التي تمت كتابة الكتاب بها أو يوم الأسبوع الذي يتم فيه التنبؤ بمستوى حركة المرور.

ماذا لو كان المتغير الفئوي المعني شيئًا مثل اسم المستشفى الخاص بمكان ولادة الطفل أو معرّف الطبيب الخاص بالشخص الذي يولد الطفل؟ المتغيرات الفئوية مثل هذه تشكل بعض المشاكل:

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

كمثال ، دعنا نأخذ مشكلة التنبؤ بتأخير وصول الرحلة. أحد مدخلات النموذج هو مطار المغادرة. كان هناك ، في وقت جمع مجموعة البيانات ، 347 مطارًا في الولايات المتحدة:

SELECT 
   DISTINCT(departure_airport)
FROM `bigquery-samples.airline_ontime_data.flights`

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

مجموعة بيانات الخطوط الجوية ، هي مجموعة بيانات عامة في BigQuery ، لذا يمكنك تجربتها.

الحل

يمثل نمط تصميم السمة المجزأة متغير إدخال فئوي عن طريق القيام بما يلي:

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

في BigQuery SQL ، يتم تحقيق هذه الخطوات على النحو التالي:

ABS(MOD(FARM_FINGERPRINT(airport), numbuckets))

الوظيفة المساعدة FARM_FINGERPRINT  تستخدم FarmHash ، وهي مجموعة من خوارزميات التجزئة التي تعتبر حتمية وموزعة جيدًا والتي تتوفر لها تطبيقات في عدد من لغات البرمجة.

في TensorFlow ، يتم تنفيذ هذه الخطوات بواسطة وظيفة feature_column:

tf.feature_column.categorical_column_with_hash_bucket(
    airport, num_buckets, dtype=tf.dtypes.string)

على سبيل المثال ، يوضح الجدول FarmHash لبعض رموز مطار IATA عند تجزئتها في 3 و 10 و 1000 حاوية.

صفمطار المغادرةhash3hash10hash1000
1DTW13543
2LBB29709
3SNA27587
4MSO27737
5ANC08508
6PIT17267
7PWM19309
FarmHash لبعض رموز المطارات IATA عند تجزئتها في أعداد مختلفة من الحاويات

لماذا يعمل

افترض أننا اخترنا تجزئة رمز المطار باستخدام 10 حاويات (hash10 في الجدول). كيف يعالج هذا المشاكل التي حددناها؟

المدخلات خارج المفردات

حتى إذا لم يكن المطار الذي يحتوي على عدد قليل من الرحلات الجوية جزءًا من مجموعة بيانات التدريب ، فستكون قيمة سمة التجزئة الخاصة به في النطاق [0–9]. لذلك ، لا توجد مشكلة مرونة أثناء الخدمة – سيحصل المطار المجهول على التنبؤات المقابلة للمطارات الأخرى في حاوية التجزئة. النموذج لن يخطئ.

إذا كان لدينا 347 مطارًا ، فسيحصل 35 مطارًا في المتوسط ​​على نفس رمز حاوية التجزئة إذا قمنا بتجزئته في 10 مجموعات. المطار المفقود من مجموعة بيانات التدريب سوف “يستعير” خصائصه من 35 مطارًا مشابهًا آخر في حاوية التجزئة. بالطبع ، لن يكون التنبؤ بمطار مفقود دقيقًا (من غير المعقول توقع تنبؤات دقيقة لمدخلات غير معروفة) ، لكنه سيكون في النطاق الصحيح.

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

عدد العناصر الكبير

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

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

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

بداية باردة

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

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

المقايضات والبدائل

تتضمن معظم أنماط التصميم نوعًا من المقايضة ، ونمط تصميم  السمة المجزئة  ليس استثناءً. المفاضلة الرئيسية هنا هي أننا نفقد دقة النموذج.

تصادم الحاويات 

يعد جزء modulo من تنفيذ السمة المجزأة عملية يصحبها فقدان للبيانات (lossy operation) . باختيار حجم حاوية التجزئة 100 ، فإننا نختار أن يكون لدينا 3-4 مطارات تشترك في حاوية .

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

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

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

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

num_hash_bucketsentries_per_bucketcollision_prob
3115.6666671.000000
1034.7000001.000000
1003.4700001.000000
100000.3470001.000000
1000000.0347000.997697
1000000.0034700.451739
العدد المتوقع للإدخالات لكل مجموعة واحتمال حدوث تصادم واحد على الأقل عند تجزئة رموز مطار IATA إلى أعداد مختلفة من الحاويات

الإنحراف 

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

CREATE TEMPORARY FUNCTION hashed(airport STRING, numbuckets INT64) AS (
   ABS(MOD(FARM_FINGERPRINT(airport), numbuckets))
);

WITH airports AS (
SELECT 
   departure_airport, COUNT(1) AS num_flights
FROM `bigquery-samples.airline_ontime_data.flights`
GROUP BY departure_airport 
)

SELECT 
   departure_airport, num_flights
FROM airports
WHERE hashed(departure_airport, 100) = hashed('ORD', 100)

تظهر النتيجة أنه في حين أن هناك ما يقرب من 3.6 مليون رحلة جوية من ORD ، لا يوجد سوى 67000 رحلة من BTV (برلنغتون ، فيرمونت):

departure_airportnum_flights
ORD3610491
BTV66555
MCI597761

يشير هذا إلى أنه ، لجميع الأغراض العملية ، سيحسب النموذج أوقات التاكسي الطويلة وتأخيرات الطقس التي تعاني منها شيكاغو إلى مطار البلدية في برلنغتون ، فيرمونت! ستكون دقة نموذج BTV و MCI (مطار كانساس سيتي) ضعيفة للغاية نظرًا لوجود العديد من الرحلات الجوية من شيكاغو.

تجميع السمة 

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

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

في بعض الحالات ، قد نتمكن من تجنب استخدام اسم المطار كسمة بالكامل ، نظرًا لأن التكرار النسبي للرحلات في الوقت المحدد قد يكون كافياً.

ضبط مدخلات الضبط (Hyperparameter tuning)

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

- parameterName: nbuckets
      type: INTEGER
      minValue: 10
      maxValue: 20
      scaleType: UNIT_LINEAR_SCALE
      

تأكد من أن عدد المجموعات يظل ضمن النطاق المعقول لعدد العناصر الأساسية للمتغير الفئوي الذي يتم تجزئته.

تجزئة التشفير (Cryptographic hash)

ما يجعل السمة المجزاة  تفقد بيانات هو طريقة تنفيد جزئية  modulo. ماذا لو تجنبنا ذلك تمامًا؟ بعد كل شيء ، فإن farm fingerprint  لها طول ثابت (INT64 هو 64 بت) ، وبالتالي يمكن تمثيلها باستخدام 64 قيمة سمة ، كل منها هي 0 أو 1. وهذا ما يسمى الترميز الثنائي.

ومع ذلك ، فإن الترميز الثنائي لا يحل مشكلة المدخلات خارج المفردات أو البداية الباردة (فقط مشكلة ارتفاع عدد العناصر). إذا لم نقم بعمل modulo ، فيمكننا الحصول على تمثيل فريد ببساطة عن طريق تشفير الأحرف الثلاثة التي تشكل رمز IATA (وبالتالي استخدام سمة طولها 3 * 26 = 78).

مشكلة هذا التمثيل واضحة على الفور: لا يوجد شيء مشترك بين المطارات التي تبدأ أسماؤها بالحرف O عندما يتعلق الأمر بخصائص تأخير الرحلة – فقد أوجد الترميز علاقة زائفة بين المطارات التي تبدأ بالحرف نفسه. لهذا السبب ، لا يوصى بتشفير ثنائي لقيم farm fingerprint.

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

 ومع ذلك ، على عكس خوارزمية Farm Fingerprint ، فإن تجزئة MD5 ليست حتمية وليست فريدة – إنها تجزئة أحادية الاتجاه وستتضمن العديد من التصادمات غير المتوقعة.

في نمط تصميم السمة المجزأة ، يتعين علينا استخدام خوارزمية تجزئة البصمات (fingerprint hashing)  وليس خوارزمية تجزئة التشفير (cryptographic hashing).

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

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

ملاحظة

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

هذا ضروري لإحباط الهجمات التي تستند إلى “جداول قوس قزح (rainbow tables) ” ، وهي هجمات تعتمد على قواميس كلمات المرور المختارة بشكل شائع والتي تقارن تجزئة كلمة المرور المعروفة مقابل التجزئة في قاعدة البيانات.

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

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

ترتيب العمليات

لاحظ أننا نقوم بعمل modulo أولاً ، ثم القيمة المطلقة:

CREATE TEMPORARY FUNCTION hashed(airport STRING, numbuckets INT64) AS (
   ABS(MOD(FARM_FINGERPRINT(airport), numbuckets))
);

يعتبر ترتيب ABS و MOD و FARM_FINGERPRINT في المقتطف السابق مهمًا لأن نطاق INT64 غير متماثل. على وجه التحديد ، يتراوح مداها بين 9 ، 223 ، 372 ، 036 ، 854 ، 775 ، 808  و  9 ، 223 ، 372 ، 036 ، 854 ، 775 ، 807  (كلاهما ضمنيًا). لذا ، إذا أردنا القيام بما يلي:

ABS(FARM_FINGERPRINT(airport))

قد نواجه خطأ تجاوز نادر وغير قابل للتكرار إذا حدث أن عملية FARM_FINGERPRINT  قامت بإرجاع – 9 ، 223 ، 372 ، 036 ، 854 ، 775 ، 808  نظرًا لأنه لا يمكن تمثيل قيمتها المطلقة باستخدام INT64!

حاويات التجزئة 

على الرغم من أنه من غير المحتمل ، هناك احتمال بعيد أنه حتى إذا اخترنا 10 حاويات تجزئة لتمثيل 347 مطارًا ، فسيكون أحد حاويات التجزئة فارغًا.

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

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

إضافة تعليق