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

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

يجب أن يفي نظام التوصية لـ dynrem بالمتطلبات التالية:

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

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

يحتوي القسم 2 على الأسس النظرية لبناء أنظمة التوصية ، ويناقش القسمان 3 و 4 الجانب العملي للقضية ، ويلخص القسم 5 النتيجة الإجمالية.

المفاهيم الأساسية

النظر في مهمة بناء نظام التوصية لمتجر واحد وسرد النهج الرياضية الأساسية.

تحليل القيمة الفردية (SVD)

نهج شعبية لبناء أنظمة التوصية هو نهج التحلل المفرد (SVD). مصفوفة التقييم $$$R = (r_ {ui})$ تمثل كمنتج اثنين من المصفوفات $$$P$ و $$$ف دولا$ لذلك $$$R \ approx P Q ^ T$ ثم تقييم تصنيف المستخدم $$$u$ للبضائع $$$i$ ممثلة $$$\ hat {r} _ {ui} = <p_u، q_i>$ [1] ، حيث تكون عناصر المنتج القياسي عبارة عن متجهات الأبعاد $$$ك$ (المعلمة الرئيسية للنموذج). هذه الصيغة بمثابة أساس لنماذج SVD الأخرى. مهمة الاكتشاف $$$P$ و $$$ف دولا$ يتعلق الأمر بتحسين الوظائف:

(2.1)

$$ $$J (P، Q) = \ sum _ {(u، i)} \ mathcal {L} (r_ {ui}، \ hat {r} _ {ui}) + \ Lambda (P، Q) \ rightarrow \ min_ {P ، Q} ،$$

حيث $$$L$ - وظيفة الخطأ (على سبيل المثال ، RMSE كما هو الحال في مسابقة Netflix ) ، $$$Λ$ - التنظيم ، والجمع هو أكثر من أزواج التي يعرف التقييم. نعيد كتابة التعبير (2.1) بشكل واضح:

(2.2)

$$ $$J (P، Q) = \ sum _ {(u، i)} (r_ {ui} - <p_u، q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 \ rightarrow \ min_ {P، Q}،$$

هنا $$$λ1 دولا$ . $$$λ2 دولا$ - معاملات التنظيم L2 لتمثيل المستخدم $$$p_ {u}$ والسلع $$$q_ {i}$ على التوالي. كان النموذج الأساسي لمسابقة Netflix:

(2.3)

$$ $$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u، q_i>،$$

(2.4)

$$ $$J (P، Q) = \ sum _ {(u، i)} (r_ {ui} - \ mu - b_u - b_i - <p_u، q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 + \ lambda_3 b_u ^ 2 + \ lambda_4 b_i ^ 2 \ rightarrow \ min_ {P، Q}،$$

حيث $$$µ$ . $$$b_ {u}$ و $$$b_ {i}$ - التحيزات لتصنيف المستخدم والمنتج ، على التوالي. يمكن تحسين النموذج (2.3) - (2.4) عن طريق إضافة تفضيل ضمني للمستخدم إليه. في مثال مسابقة Netflix ، تتمثل الاستجابة الصريحة في النتيجة التي حددها المستخدم للفيلم "بناءً على طلبنا" ، وغيرها من المعلومات حول "تفاعل المستخدم مع المنتج" (عرض الفيلم ووصفه وتعليقاته عليه ؛ أي أن الاستجابة الضمنية لا تقدم استجابة ضمنية) معلومات مباشرة عن تصنيف الفيلم ، ولكن في الوقت نفسه يشير إلى الاهتمام). يتم تطبيق محاسبة الاستجابة الضمنية في نموذج SVD ++:

(2.5)

$$ $$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u + \ frac {1} {\ sqrt {\ sigma_u}} \ sum_ {j \ in S (u)} y_j، \، \ ، q_i> ،$$

حيث $$$S (ش)$ - مجموعة من الأشياء التي تفاعل معها المستخدم ضمنيًا ، $$$σ_ {u} = | S (u) |، y_ {j}$ - تمثيل البعد $$$ك$ لكائن من $$$S (ش)$ .

آلات التخصيم (FM)

كما يتبين من الأمثلة ذات نماذج SVD المختلفة ، يختلف أحد النماذج عن الآخر في مجموعة المصطلحات المتضمنة في صيغة التقييم. علاوة على ذلك ، فإن توسيع النموذج في كل مرة يمثل مهمة جديدة. نريد تنفيذ مثل هذه التغييرات (على سبيل المثال ، إضافة نوع جديد من الاستجابة الضمنية ، مع مراعاة معلمات الوقت) بسهولة دون تغيير رمز تنفيذ النموذج. يمكن تمثيل النماذج (2.1) - (2.5) في شكل عالمي مناسب باستخدام المعلمة التالية. نحن نمثل المستخدم والمنتج كمجموعة من الميزات:

(2.6)

$$ $$\ overline {x} ^ U = (x_1 ^ U ، x_2 ^ U ، \ dots ، x_l ^ U) \ in \ mathbb {R} ^ l ،$$

(2.7)

$$ $$\ overline {x} ^ I = (x_1 ^ I ، x_2 ^ I ، \ dots ، x_m ^ I) \ in \ mathbb {R} ^ m.$$

التين. 1: مثال لمصفوفة المعالم في حالة CF.

على سبيل المثال ، في حالة التصفية التعاونية (CF) ، عند استخدام البيانات المتعلقة بتفاعل المستخدمين والمنتجات فقط ، تبدو متجهات الميزات ككود واحد ساخن (الشكل 1). إدخال ناقلات $$$\ overline {x} = (\ overline {x} ^ U ، \ overline {x} ^ I)$ ، ثم يتم تقليل مهمة التوصية إلى مشاكل الانحدار مع المتغير الهدف $$$r_ {ui}$ :

1. نموذج خطي:
   (2.8)
   

   $$ $$h_ {lin} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j$$

2. poly2:
   (2.9)
   

   $$ $$h_ {poly2} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} w_ {ij} x_i x_j$$

3. وزير الخارجية:
   (2.10)
   

   $$ $$h_ {FM} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} x_i x_j <\ overline {v} _i ، \ overline {v} _j>$$

حيث $$$w_ {j}$ - معلمات النموذج ، $$$v_ {i}$ هي ناقلات البعد $$$ك$ يمثل علامة $$$i$ في الفضاء الكامن $$$ل$ و $$$م دولا$ - عدد علامات المستخدم والمنتج ، على التوالي. بالإضافة إلى رموز التشغيل السريع ، يمكن أن تكون الميزات المستندة إلى المحتوى (القائمة على المحتوى ، CB) بمثابة علامات (الشكل 2) ، على سبيل المثال ، الأوصاف الموجهة للمنتجات وتوصيفات المستخدم.


التين. 2: مثال لمصفوفة المعالم الموسعة.

نموذج FM المقدم في [2] هو تعميم لـ (2.1) - (2.5) ، (2.8) ، (2.10). جوهر FM هو أنه يأخذ في الاعتبار التفاعل المزدوج للميزات باستخدام منتج العددية $$$<\ overline {v} _i ، \ overline {v} _j>$ ، لا تستخدم المعلمة $$$w_ {ij}$ . ميزة FM عبر Poly2 هي انخفاض كبير في عدد المعلمات: للمتجهات $$$v_ {i}$ سنحتاج $$$(ل + م) · ك دولا$ المعلمات ، ول $$$w_ {ij}$ سوف تكون مطلوبة $$$م م دولا$ المعلمات. في $$$ل$ و $$$م دولا$ من الطلبات الكبيرة ، يستخدم النهج الأول معلمات أقل بكثير.

يرجى ملاحظة: إذا لم يكن هناك زوج محدد في مجموعة التدريب $$$(i، j)$ ، ثم المصطلح المقابل مع $$$w_ {ij}$ في Poly2 لا يؤثر على تدريب النموذج ، ويتم تشكيل درجة التصنيف فقط على الجزء الخطي. ومع ذلك ، فإن النهج (2.10) يتيح لنا إقامة علاقات من خلال ميزات أخرى. بمعنى آخر ، تساعد البيانات الموجودة على تفاعل واحد في تقييم معلمات السمات غير المضمنة في هذا المثال.

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

LightFM

في التنفيذ الشعبي لـ FM ، يتم التركيز على الفصل بين خصائص المستخدم والمنتج. المصفوفات بمثابة معلمات النموذج $$$E ^ U$ و $$$E ^ I$ تقديم ميزات مخصصة و المنتج:

(2.11)

$$ $$E ^ U = \ start {pmatrix} \ overline {e} _1 ^ U \\ \ vdots \\ \ overline {e} _l ^ U \ end {pmatrix}، \، \، E ^ I = \ تبدأ {pmatrix } \ overline {e} _1 ^ I \\ \ vdots \\ \ overline {e} _m ^ I \ end {pmatrix}، \ overline {e} _i ^ U \ in \ mathbb {R} ^ k، \ overline { e} _i ^ I \ in \ mathbb {R} ^ k$$

وكذلك تعويضات $$$\ overline {b} ^ U، \ overline {b} ^ I \ in \ mathbb {R} ^ k$ . باستخدام طرق عرض المستخدم والمنتج:

(2.12)

$$ $$\ overline {p} ^ U = \ overline {x} ^ U \ cdot E ^ U = \ sum_ {j = 1} ^ l x_j ^ U \ cdot \ overline {e} _j ^ U،$$

(2.13)

$$ $$\ overline {q} ^ I = \ overline {x} ^ I \ cdot E ^ I = \ sum_ {j = 1} ^ m x_j ^ I \ cdot \ overline {e} _j ^ I،$$

الحصول على تصنيف الزوج $$$(ش ، ط)$ :

(2.14)

$$ $$\ hat {r} _ {ui} = <\ overline {p} ^ U ، \ overline {q} ^ I> + <\ overline {x} ^ U ، \ overline {b} ^ U> + <\ overline {x} ^ I ، \ overline {b} ^ I>.$$

وظائف الخسارة

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

1. اللوجيستية هي تطبيق يتطلب سلبيًا لم يتم تقديمه بشكل صريح في معظم المهام.
2. BPR [3] هو زيادة الفرق في التصنيفات بين الأمثلة الإيجابية والسلبية لمستخدم معين. يتم الحصول على السلبي باستخدام أخذ عينات bootstrap. يشبه الجودة الوظيفية المستخدمة في الخوارزمية ROC-AUC.
3. يختلف WARP [4] عن BPR في طريقة أخذ العينات من الأمثلة السلبية ووظيفة الخسارة ، والتي يتم ترتيبها أيضًا ، ولكن في نفس الوقت تعمل على تحسين أفضل التوصيات للمستخدم.

التنفيذ العملي

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

معالجة البيانات مسبقا

يتم تنفيذ معالجة البيانات المسبقة بواسطة أدوات Spark SQL القابلة للتحجيم تلقائيًا. الميزات المحددة في النموذج النهائي هي الأوصاف النصية للسلع والكتالوجات مع التحويلات القياسية.

ما الذي ساعدنا عند التفاعل مع Spark:

1. تقسيم البيانات المعدة (مصفوفة تفاعلات المستخدم والمنتج ، علامات لهم) من قبل المتاجر. يتيح لك ذلك توفير الوقت أثناء مرحلة التدريب على قراءة البيانات من HDFS. خلاف ذلك ، يتعين على كل مهمة قراءة البيانات في ذاكرة Spark وتصفيتها بمعرف المتجر.
2. يتم حفظ / تلقي البيانات من / إلى Spark في أجزاء. هذا يرجع إلى حقيقة أنه خلال أي من هذه الإجراءات يتم تحميل البيانات في ذاكرة JVM. لماذا لا تزيد فقط من ذاكرة JVM؟ أولاً ، تنخفض الذاكرة المتاحة للتدريب على النموذج ، وثانياً ، ليست هناك حاجة لتخزين أي شيء في JVM ، فهي تعمل في هذه الحالة كمخزن مؤقت.

التدريب النموذجي

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

تفتقر LightFM إلى آليات التوقف المبكر ، وبالتالي ، فإننا ننفق موارد إضافية على التكرار الإضافي للتدريب عند عدم وجود زيادة في القياس المستهدف. لقد اخترنا AUC كمقياس ، يتم تأكيد العلاقة مع CTR بشكل تجريبي.

دلالة:

$$$S$ - جميع التفاعلات المعروفة بين المستخدمين والمنتجات ، أي الأزواج $$$(ش ، ط)$ .
$$$I$ - الكثير من جميع السلع $$$i$ .
$$$يو$ - الكثير من جميع المستخدمين $$$u$ .
لمستخدم معين $$$u$ أعرض أيضا $$$I_ {u} = {i ∈ I: (u، i) ∈ S}$ - الكثير من المنتجات التي تفاعل المستخدم معها. يمكن حساب AUC على النحو التالي [المرجع]:

(3.1)

$$ $$AUC (u) = \ frac {1} {| \ mathcal {I} _u || \ mathcal {I} \ setminus \ mathcal {I} _u |} \ sum_ {i \ in \ mathcal {I} _u} \ sum_ {j \ in \ mathcal {I} \ setminus \ mathcal {I} _u} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}) ،$$

(3.2)

$$ $$AUC = \ frac {1} {| \ mathcal {U} |} \ sum_ {u \ in \ mathcal {U}} AUC (u).$$

في الصيغة (3.1) نحتاج إلى حساب التصنيف لجميع الأزواج الممكنة $$$(ش ، ط)$ ( $$$u$ ثابت) ، وكذلك مقارنة التقييمات للعناصر من $$$\ mathcal {I} _u$ مع تقييمات من $$$\ mathcal {I} \ setminus \ mathcal {I} _u$ . بالنظر إلى أن المستخدم يتفاعل مع الجزء الضئيل من التشكيلة ، فإن تعقيد الحساب هو $$$O (| \ mathcal {U} || \ mathcal {I} |)$ . في الوقت نفسه ، فإن عصر تدريب FM يكلفنا $$$O (| \ mathcal {U} |)$ .

لذلك ، قمنا بتعديل حساب AUC. أولاً ، يجب تقسيم العينة إلى تدريب $$$\ mathcal {S} ^ {train} \ subset \ mathcal {S}$ والتحقق من الصحة $$$\ mathcal {S} ^ {val} \ subset \ mathcal {S}$ و $$$\ mathcal {S} ^ {val} = \ mathcal {S} \ setminus \ mathcal {S} ^ {train}$ . بعد ذلك ، نستخدم أخذ العينات لإنشاء العديد من المستخدمين للتحقق من الصحة $$$\ mathcal {U} ^ {val} \ subset \ {u \ in \ mathcal {U}: (u، i) \ in \ mathcal {S} ^ {val} \}$. للمستخدم $$$u$من $$$\ mathcal {U} ^ {val}$سيتم اعتبار عناصر الطبقة الإيجابية كثيرة $$$\ mathcal {I} _u ^ {+} = \ {i \ in \ mathcal {I}: (u، i) \ in \ mathcal {S} ^ {val} \}$لمماثلة $$$\ mathcal {I} _u$. كعناصر لفئة سلبية ، نأخذ عينة فرعية $$$\ mathcal {I} _u ^ {-} \ subset \ mathcal {I}$بحيث لا عناصر من $$$\ mathcal {I} _u$. يمكن أخذ حجم العينة الفرعي بما يتناسب مع الحجم. $$$\ mathcal {I} _u ^ {+}$هذا هو $$$| \ mathcal {I} _u ^ {-} | = c \ cdot | \ mathcal {I} _u ^ {+} |$. ثم الصيغ (3.1) ، (3.2) لحساب AUC سوف تتغير:

(3.3)

$$ $$AUC (u) = \ frac {1} {| \ mathcal {I} _u ^ {+} || \ mathcal {I} _u ^ {-} |} \ sum_ {i \ in \ mathcal {I} _u ^ {+}} \ sum_ {j \ in \ mathcal {I} _u ^ {-}} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}) ،$$

(3.4)

$$ $$AUC = \ frac {1} {| \ mathcal {U} ^ {val} |} \ sum_ {u \ in \ mathcal {U} ^ {val}} AUC (u).$$

نتيجة لذلك ، نحصل على وقت ثابت لحساب AUC ، نظرًا لأننا نأخذ فقط جزءًا ثابتًا من المستخدمين والمجموعات $$$\ mathcal {I} _u ^ {+}$و $$$\ mathcal {I} _u ^ {-}$لديك حجم صغير. تتوقف عملية التعلم الخاصة بالمخزن بعد توقف AUC (3.4) عن التحسن.

البحث عن كائنات مماثلة

كجزء من مهمة item2item ، يجب عليك تحديد لكل عنصر $$$ن$(أو منتجات مماثلة قدر الإمكان) لتلك التي تزيد من قابلية النقر فوق الشعار. افتراضنا: يجب اعتبار المرشحين للراية من أعلى $$$ك$الأقرب في حفلات الزفاف الفضاء. اختبرنا الطرق التالية لحساب "أقرب الجيران": Scala + Spark ، ANNOY ، SCANNs ، HNSW.


بالنسبة إلى Scala + Spark لمتجر يحتوي على 500 ألف كائن ، استغرق حساب مقياس جيب التمام الصادق 15 دقيقة وكمية كبيرة من موارد المجموعة ، فيما يتعلق باختبارنا الطرق التقريبية للعثور على أقرب الجيران. عند البحث عن طريقة SCANNs ، تباينت المعلمات التالية: bucketLimit و shouldSampleBuckets و NumHashes و setSignatureLength ، لكن النتائج اتضح أنها غير مرضية مقارنة بالطرق الأخرى (تقع كائنات مختلفة جدًا في المجموعة). أظهرت خوارزميات ANNOY و HNSW نتائج مماثلة لجيب التمام الصادق ، ولكنها عملت بشكل أسرع بكثير.

	200k المنتجات		500 كيلو البضائع		2.2m المنتجات
خوارزمية	غضب	HNSW	غضب	HNSW	غضب	HNSW
بناء الوقت مؤشر (ثانية)	59.45	8.64	258.02	25.44	1190.81	90.45
الوقت الإجمالي (ثانية)	141.23	14.01	527.76	43.38	2081.57	150.92

نظرًا لحقيقة أن HNSW عملت بشكل أسرع من جميع الخوارزميات ، فقد قررنا التوقف عن ذلك.
نحن نبحث أيضًا عن أقرب الجيران في حاوية Spark ونكتب النتيجة في Hive مع التقسيم المناسب.

استنتاج

أذكر: نحن نستخدم WARP لتدريب النموذج ، AUC للتوقف المبكر ، ويتم إجراء تقييم الجودة النهائي باستخدام اختبار A / B على حركة المرور المباشرة.

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

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

شكرا لاهتمامكم!

أدب

[1] Ricci F.، Rokach L.، Shapira B. Introduction to recommender systems manual
// كتيب نظم التوصية. - سبرينغر ، بوسطن ، ماجستير ، 2011. - S. 147160.

[2] آلات Rendle S. Factorization // 2010 IEEE International Conference on Mining Mining. - IEEE ، 2010. - S. 995-1000.

[3] Rendle S. et al. BPR: تصنيف بايزي شخصية من ردود الفعل الضمنية
// وقائع المؤتمر الخامس والعشرين حول عدم اليقين في الذكاء الاصطناعي.
- AUAI Press ، 2009. - S. 452-461.

[4] Weston J.، Bengio S.، Usunier N. Wsabi: - 2011.