ML-Blitz: تحليل مهام جولة التأهيل الأولى

لذا ، نحتاج إلى بناء تقريب سلس للدالة المعروفة. إذا كانت المعلمة $$$c$ معروف ثم ابحث عن المعلمات $$$a$ و $$$b$ بسيطة بما يكفي. يمكنك كتابة الحلول الرياضية كحل لمشاكل التحسين المناسبة. معلمة $$$a$ هو مقدار تنبؤات الجدعة الحاسمة في تلك الأشياء $$$(x_i، y_i)$ عينة التدريب التي $$$x_i <c$ . وبالمثل $$$b$ هو مقدار التنبؤات عند تلك الأشياء $$$(x_i، y_i)$ عينة التدريب التي $$$x_i \ ge c$ .

نقدم تدوين المجموعات الفرعية المقابلة من مجموعة التدريب: $$$L (ج)$ هي مجموعة فرعية من الكائنات على يسار نقطة $$$c$ ، $$$R (ج)$ - مجموعة فرعية من الأشياء على يمين النقطة $$$c$ .

ثم القيمة المثلى $$$a$ ستكون مساوية للمتوسط ​​الحسابي للإجابات في المجموعة $$$L (ج)$ والقيمة المثلى $$$b$ - على التوالي ، المتوسط ​​الحسابي للإجابات في المجموعة $$$R (ج)$ .

لذا أصبح من الواضح الآن كيفية العثور على المعلمات $$$a$ و $$$b$ مع معلمة معروفة $$$c$ . يبقى فهم كيفية العثور على قيمة المعلمة المثلى $$$c$ .

أول شيء يجب ملاحظته: المعلمة $$$c$ يمكن أن تأخذ أي قيم حقيقية ، ولكن العديد من الأقسام المختلفة محدودة. عينة التعلم من $$$n$ لا يمكن كسر الأشياء أكثر من $$$n + 1$ طرق للأجزاء "اليسرى" و "اليمنى". في الواقع ، يمكن أن يكون هناك عدد أقل من هذه الأقسام: على سبيل المثال ، بالنسبة لبعض الكائنات ، قد تتطابق قيم السمات. بالإضافة إلى ذلك ، فإن الأقسام متكافئة بالنسبة لنا ، حيث تكون جميع الأشياء في مجموعة التدريب على اليسار أو على اليمين.

للحصول على جميع الأقسام الممكنة ، يمكنك فرز كائنات التدريب حسب السمة غير المتناقصة:

من الواضح الآن أن قيم المعلمات المحتملة مثيرة للاهتمام $$$c$ هي الكميات

الآن أصبح من الواضح ما يجب فعله للحصول على حل. من الضروري فرز جميع قيم المعلمات التي قد تكون مثيرة للاهتمام $$$c$ ، لكل منهم تحديد الكميات المقابلة $$$a$ و $$$b$ وكذلك قيمة الخسارة الوظيفية. ثم تحتاج إلى تحديد مجموعة من المعلمات المقابلة للحد الأدنى من القيم الوظيفية للخسارة.

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

لجعل الحسابات فعالة ، تذكر ذلك للعثور على المعلمات $$$a$ و $$$b$ من الضروري فقط حساب متوسط ​​القيم على المجموعة. عند إضافة عنصر آخر إلى المجموعة (أو بعد إزالة عنصر من المجموعة) ، يمكن حساب متوسط ​​القيمة بشكل فعال للوقت الثابت إذا لم تقم بتخزين المتوسط ​​نفسه ، ولكن بشكل منفصل مجموع القيم وعددها بشكل منفصل. الوضع مشابه لمجموع الانحرافات المربعة. لحسابه ، وفقًا للصيغة المعروفة جيدًا لحساب التباين ، يمكنك تخزين مجموع الكميات ومجموع مربعات الكميات بشكل منفصل. بالإضافة إلى ذلك ، يمكنك استخدام أي طريقة حساب عبر الإنترنت . سبق لي أن كتبت عن ذلك في محور

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

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

class MeanCalculator: def __init__(self): self.Count = 0. self.Mean = 0. def Add(self, value, weight = 1.): self.Count += weight self.Mean += weight * (value - self.Mean) / self.Count def Remove(self, value, weight = 1.): self.Add(value, -weight) class SumSquaredErrorsCalculator: def __init__(self): self.MeanCalculator = MeanCalculator() self.SSE = 0. def Add(self, value, weight = 1.): curDiff = value - self.MeanCalculator.Mean self.MeanCalculator.Add(value, weight) self.SSE += weight * curDiff * (value - self.MeanCalculator.Mean) def Remove(self, value, weight = 1.): self.Add(value, -weight) 

الآن نحن بحاجة إلى فصل لتخزين ومعالجة مجموعة التدريب. أولاً ، نصف الحقول وطريقة الإدخال:

 class Instances: def __init__(self): self.Items = [] self.OverAllSSE = SumSquaredErrorsCalculator() def Read(self): fin = open('stump.in') for line in fin.readlines()[1:]: x, y = map(float, line.strip().split()) self.Items.append([x, y]) self.OverAllSSE.Add(y) self.Items.sort() 

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

الآن الشيء الأكثر إثارة للاهتمام: طريقة العثور على قيم المعلمات المثلى.

لنبدأ بالتهيئة. في الحالة الأولية ، تكون جميع الكائنات في العينة الفرعية الصحيحة. ثم المعلمة $$$a$ يمكن أن تكون مساوية لأي شيء ، معلمة $$$b$ يساوي متوسط ​​الاستجابة في العينة بأكملها ، والمعلمة $$$c$ بحيث تكون جميع الكائنات في التحديد على يمينها.

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

 left = SumSquaredErrorsCalculator() right = self.OverAllSSE bestA = 0 bestB = right.MeanCalculator.Mean bestC = self.Items[0][0] bestQ = right.SSE 

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

 for i in range(len(self.Items) - 1): item = self.Items[i] nextItem = self.Items[i + 1] left.Add(item[1]) right.Remove(item[1]) if item[0] == nextItem[0]: continue a = left.MeanCalculator.Mean b = right.MeanCalculator.Mean c = (item[0] + nextItem[0]) / 2 q = left.SSE + right.SSE if q < bestQ: bestA = a bestB = b bestC = c bestQ = q 

الآن يبقى فقط لإنشاء الرمز للحصول على حل:

 instances = Instances() instances.Read() a, b, c = instances.BestSplit() print >> open('stump.out', 'w'), a, b, c 

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

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

قم بتوسيع الأقواس ، متجاهلاً المتغيرات العشوائية:

$$ $$f (x) = a ^ 2 \ cdot \ sin ^ 2 (x) + b ^ 2 \ cdot \ ln ^ 2 (x) + 2ab \ cdot \ sin (x) \ cdot \ ln (x) + c \ cdot x ^ 2$$

الآن لدينا مشكلة الانحدار الخطي متعدد الأبعاد بدون معامل حر. الخصائص في هذه المشكلة هي الكميات $$$\ sin ^ 2 (x)$ ، $$$\ ln ^ 2 (x)$ ، $$$\ sin (x) \ cdot \ ln (x)$ ، $$$x ^ 2$ .

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

عند حل مشكلة الانحدار الخطي متعدد الأبعاد ، سيتم العثور على بعض المعاملات مع الميزات المعدلة. في الواقع ، سيتم العثور على التمثيل التالي للدالة $$$f$ :

$$ $$f (x) = t_1 \ cdot \ sin ^ 2 (x) + t_2 \ cdot \ ln ^ 2 (x) + t_3 \ cdot \ sin (x) \ cdot \ ln (x) + t_4 \ cdot x ^ 2$$

بعد ذلك ، يمكنك العثور على المعاملات $$$a$ ، $$$b$ ، $$$c$ :

$$ $$a = \ sqrt (t_1) ، b = \ sqrt (t_2) ، c = t_4$$

بالإضافة إلى ذلك ، يجدر التحقق من ذلك $$$2 \ cdot a \ cdot b \ تقريبا t_3$

بادئ ذي بدء ، يجب عليك قراءة البيانات وتشكيل العلامات:

 x = [] y = [] for line in open('data.txt'): xx, yy = map(float, line.strip().split()) x.append(xx) y.append(yy) features = [] for xx in x: curFeatures = [ math.sin(xx) ** 2, # a^2 math.log(xx) ** 2, # b^2 math.sin(xx) * math.log(xx), # 2ab xx ** 2 # c ] features.append(curFeatures) 

الآن من الضروري حل مشكلة الانحدار الخطي متعدد الأبعاد. هناك عدد كبير من الطرق للقيام بذلك - من أدوات مثل Weka ووظائف مكتبة sklearn إلى التنفيذ الخاص بي . ومع ذلك ، في هذه الحالة ، أردت الحصول على حل "مغلق": نص برمجي واحد يحل المشكلة تمامًا. لذلك ، استخدمت sklearn.

 linearModel = lm.LinearRegression() linearModel.fit(features, y) coeffs = linearModel.coef_ a = math.sqrt(coeffs[0]) b = math.sqrt(coeffs[1]) c = coeffs[3] print "free coeff: ", linearModel.intercept_ print "2ab error: ", coeffs[2] - 2 * a * b print a, b, c 

في هذه الحالة اتضح أن المعامل الحر هو -0.0007 والخطأ في الحساب $$$t_3$ بلغ 0.00135. وبالتالي ، فإن الحل الذي تم العثور عليه ثابت تمامًا.

الخط الأخير مع المعاملات:

 3.14172883822 2.71842889253 3.999957864335599 

باستبدالها كإجابة للمشكلة ، نحصل على موافق مستحق!

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

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

 0 Auxiliary 1 Auxiliary 8 Target 

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

 awk -F "\t" -vOFS="\t" '{print $0, 0}' fr_test.tsv > fr_test.fixed 

الآن يمكنك تدريب CatBoostL

 catboost calc --input-path fr_test.fixed --cd fields.cd 

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

سننطلق من حقيقة أن حصة الأمثلة الإيجابية في عينات التدريب والاختبار تتزامن. في عينة التدريب ، يحتوي حوالي 3/4 من جميع الاستعلامات على نقرات على المستندات الأخيرة. لذلك ، نختار عتبة التصنيف بحيث يكون ما يقرب من 3/4 من جميع الطلبات من عينة الاختبار ذات تنبؤات إيجابية. على سبيل المثال ، بالنسبة لعتبة 0.04 ، هناك 178925 من 200.000.

لذلك ، نقوم بتشكيل ملف الحل على النحو التالي:

 awk -F "\t" -vOFS="\t" 'NR > 1 {if ($2 > 0.04) print 1; else print 0}' output.tsv > solution.tsv 

هنا كان من الضروري تخطي السطر الأول ، لأنه يكتب CatBoost أسماء الأعمدة الخاصة به.

وبالتالي يتم إرسال ملف solution.tsv الذي تم الحصول عليه إلى نظام التحقق ويتلقى موافقًا شرعيًا كحكم.

كما تعلم ، هناك مجموعة متنوعة من الطرق لاختيار السمات.

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

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

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

تحتاج أولاً إلى تدريب النموذج:

 catboost fit --cd train.cd -f train.txt 

ثم قم بتشغيل تقييم الميزة:

 catboost fstr --input-path train.txt --cd train.cd 

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

 head feature_strength.tsv 9.897213004 f193 9.669603844 f129 7.500907599 f292 5.903810044 f48 5.268100711 f337 2.508377813 f283 2.024904488 f111 1.933500313 f208 1.878848285 f345 1.652808387 f110 

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

لنفترض أنك إذا حددت أهم 50 علامة ، فعندئذٍ في مجموعة اختبار عامة ، يمكنك الحصول على 3.6 نقاط ؛ إذا اخترت أعلى 40 أو أعلى 30 أو أعلى 20 ، فستحصل على 4 نقاط بالضبط. لذلك ، اخترت أفضل 20 علامة كحل - حصل هذا الحل على 4 نقاط في جناح اختبار مغلق.

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

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