مستخدم:Gaith120/تعزيز التدرج

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

نشأت فكرة زيادة التدرج اللوني في ملاحظة ليو بريمان أن التعزيز يمكن تفسيره على أنه خوارزمية تحسين على دالة تكلفة مناسبة. تم تطوير خوارزميات تدرج الانحدار الصريح لاحقًا بواسطة Jerome H. Friedman ، وقت واحد مع منظور تدرج وظيفي أكثر عمومية من Llew Mason و Jonathan Baxter و Peter Bartlett و Marcus Frean. قدمت ورقتان في وقت لاحق وجهة نظر لتعزيز الخوارزميات باعتبارها خوارزميات النسب التدرج الوظيفية التكرارية. بمعنى ، الخوارزميات التي تعمل على تحسين دالة التكلفة على مساحة الوظيفة من خلال اختيار دالة (فرضية ضعيفة) تشير في اتجاه التدرج السلبي. لقد أدت وجهة النظر التدرج الوظيفية هذه إلى تطوير خوارزميات معززة في العديد من مجالات التعلم الآلي والإحصاءات إلى ما بعد الانحدار والتصنيف.

مقدمة غير رسمية

(يتبع هذا القسم عرض التدرج المعزز بواسطة لي. )

مثل أساليب التعزيز الأخرى ، فإن التدرج التدريجي يجمع بين "المتعلمين" الضعفاء في متعلم واحد قوي بطريقة تكرارية. من الأسهل شرحه في إعداد انحدار المربعات الصغرى ، حيث يكون الهدف هو "تعليم" نموذجًا $F$ للتنبؤ قيم النموذج ${\hat {y}}=F(x)$ عن طريق تقليل الخطأ التربيعي يعني ${\tfrac {1}{n}}\sum _{i}({\hat {y}}_{i}-y_{i})^{2}$ ، أين $i$ فهارس على بعض مجموعة التدريب من الحجم $n$ القيم الفعلية للمتغير الناتج $y$ .

في كل مرحلة $m$ ، $1\leq m\leq M$ ، لتعزيز التدرج ، قد يكون من المفترض أن هناك بعض النماذج غير الكاملة $F_{m}$ (في البداية ، يمكن استخدام نموذج ضعيف للغاية يتوقع متوسط y في مجموعة التدريب). خوارزمية تعزيز التدرج تتحسن $F_{m}$ من خلال بناء نموذج جديد يضيف مقدّر h لتوفير نموذج أفضل: $F_{m+1}(x)=F_{m}(x)+h(x)$ . لايجاد $h$ يبدأ حل زيادة التدرج بالملاحظة التي تشير إلى أن h الكمال يعني

$F_{m+1}(x)=F_{m}(x)+h(x)=y$

$h(x)=y-F_{m}(x)$ .

لذلك ، فإن التدرج اللوني سوف يلائم h للباقي $y-F_{m}(x)$ . كما هو الحال في متغيرات التعزيز الأخرى ، كل $F_{m+1}$ يحاول تصحيح أخطاء سلفه $F_{m}$ . تعميم هذه الفكرة على وظائف الخسارة بخلاف الخطأ التربيعي ، ومشكلات التصنيف والتصنيف ، يتبع من الملاحظة أن البقايا $y-F(x)$ لنموذج معين هي التدرجات السلبية (فيما يتعلق $F(x)$ ) وظيفة تربيع الخطأ المفقودة ${\frac {1}{2}}(y-F(x))^{2}$ . لذا ، فإن زيادة التدرج اللوني هي خوارزمية نزول التدرج ، وتعميمها يستلزم "توصيل" خسارة مختلفة وتدرجها.

خوارزمية

في العديد من مشكلات التعلم الخاضعة للإشراف ، يكون لدى أحد المتغيرات الناتجة y ومتجه لمتغيرات الإدخال x الموصوفة عبر توزيع الاحتمالات المشتركة {\ displaystyle P (x، y)}

. باستخدام مجموعة تدريب {\ displaystyle \ {(x_ {1} ، y_ {1}) ، \ dots ، (x_ {n} ، y_ {n}) \}}

  من القيم المعروفة لـ x والقيم المقابلة لـ y ، الهدف هو إيجاد تقريب {\ displaystyle {\ hat {F}} (x)}

  إلى دالة {\ displaystyle F (x)}

  الذي يقلل من القيمة المتوقعة لبعض وظيفة الخسارة المحددة

{\ displaystyle L (y، F (x))}

${\hat {F}}={\underset {F}{\arg \min }}\,\mathbb {E} _{x,y}[L(y,F(x))]$ .

تفترض طريقة التدرج اللوني قيمة y حقيقية وتسعى إلى تقدير تقريبي ${\hat {F}}(x)$ في شكل مجموع مرجح للوظائف $h_{i}(x)$ من بعض الصف ${\mathcal {H}}$ ، يسمى المتعلمين الأساسي (أو الضعيف ):

${\hat {F}}(x)=\sum _{i=1}^{M}\gamma _{i}h_{i}(x)+{\mbox{const}}$ .

وفقًا لمبدأ تقليل المخاطر التجريبية ، تحاول الطريقة إيجاد تقريب ${\hat {F}}(x)$ الذي يقلل من متوسط قيمة وظيفة الخسارة في مجموعة التدريب ، أي يقلل من المخاطر التجريبية. تقوم بذلك عن طريق البدء بنموذج يتكون من وظيفة ثابتة $F_{0}(x)$ وتوسيعه تدريجياً بطريقة جشعة :

$F_{0}(x)={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L(y_{i},\gamma )}}$ ،

$F_{m}(x)=F_{m-1}(x)+{\underset {h_{m}\in {\mathcal {H}}}{\operatorname {arg\,min} }}\left[{\sum _{i=1}^{n}{L(y_{i},F_{m-1}(x_{i})+h_{m}(x_{i}))}}\right]$ ،

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

والفكرة هي تطبيق خطوة النسب الأكثر حدة على مشكلة التقليل هذه (انخفاض التدرج الوظيفي). إذا نظرنا في حالة مستمرة ، أي أين ${\mathcal {H}}$ هي مجموعة من الوظائف التفاضلية التعسفية على $\mathbb {R}$ ، سنقوم بتحديث النموذج وفقًا للمعادلات التالية

$$F_{m}(x)=F_{m-1}(x)-\gamma _{m}\sum _{i=1}^{n}{\nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))},$$

$$\gamma _{m}={\underset {\gamma }{\arg \min }}{\sum _{i=1}^{n}{L\left(y_{i},F_{m-1}(x_{i})-\gamma \nabla _{F_{m-1}}L(y_{i},F_{m-1}(x_{i}))\right)}},$$

حيث تؤخذ المشتقات فيما يتعلق بالوظائف $F_{i}$ إلى عن على $i\in \{1,..,m\}$ و $\gamma _{m}$ هو طول الخطوة. في حالة منفصلة ومع ذلك ، أي عندما مجموعة ${\mathcal {H}}$ غير محدود، نختار المرشح وظيفة h الأقرب إلى التدرج من L التي يمكن بعد ذلك حساب γ معامل بمساعدة بحث خط على المعادلات أعلاه. لاحظ أن هذه الطريقة هي طريقة ارشادية وبالتالي لا تسفر عن حل دقيق للمشكلة المحددة ، ولكنها تقريبًا. في الكود الكاذب ، طريقة تعزيز التدرج العام هي:

Input: training set $\{(x_{i},y_{i})\}_{i=1}^{n},$ a differentiable loss function $L(y,F(x)),$ number of iterations M.

Algorithm:

1. Initialize model with a constant value:

   $F_{0}(x)={\underset {\gamma }{\arg \min }}\sum _{i=1}^{n}L(y_{i},\gamma ).$

2. For m = 1 to M:
   1. Compute so-called pseudo-residuals:

      $r_{im}=-\left[{\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}}\right]_{F(x)=F_{m-1}(x)}\quad {\mbox{for }}i=1,\ldots ,n.$

   2. Fit a base learner (or weak learner, e.g. tree) $h_{m}(x)$ to pseudo-residuals, i.e. train it using the training set $\{(x_{i},r_{im})\}_{i=1}^{n}$.
   3. Compute multiplier $\gamma _{m}$ by solving the following one-dimensional optimization problem:

      $\gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L\left(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})\right).$

   4. Update the model:

      $F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x).$

3. Output $F_{M}(x).$

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

إن التدرج العام الذي يدعم الخطوة m سوف يناسب شجرة القرار $h_{m}(x)$ لالبقايا الزائفة. سمح $J_{m}$ يكون عدد اوراقها. أقسام الشجرة مساحة الإدخال إلى $J_{m}$ مناطق مفككة $R_{1m},\ldots ,R_{J_{m}m}$ ويتوقع قيمة ثابتة في كل منطقة. باستخدام تدوين المؤشر ، خرج $h_{m}(x)$ للإدخال x يمكن كتابة كمجموع:

$h_{m}(x)=\sum _{j=1}^{J_{m}}b_{jm}\mathbf {1} _{R_{jm}}(x),$

ثم المعاملات $b_{jm}$ تتضاعف بعض القيمة $\gamma _{m}$ ، تم اختياره باستخدام البحث الخطي لتقليل وظيفة الخسارة ، ويتم تحديث النموذج على النحو التالي:

$F_{m}(x)=F_{m-1}(x)+\gamma _{m}h_{m}(x),\quad \gamma _{m}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{i=1}^{n}L(y_{i},F_{m-1}(x_{i})+\gamma h_{m}(x_{i})).$

يقترح فريدمان تعديل هذه الخوارزمية بحيث تختار قيمة مثالية منفصلة $\gamma _{jm}$ لكل من مناطق الشجرة ، بدلا من واحدة $\gamma _{m}$ للشجرة كلها. يسميه الخوارزمية المعدلة "TreeBoost". المعاملات $b_{jm}$ من إجراء تركيب الأشجار ، يمكن بعد ذلك تجاهلها ببساطة وتصبح قاعدة تحديث النموذج:

$F_{m}(x)=F_{m-1}(x)+\sum _{j=1}^{J_{m}}\gamma _{jm}\mathbf {1} _{R_{jm}}(x),\quad \gamma _{jm}={\underset {\gamma }{\operatorname {arg\,min} }}\sum _{x_{i}\in R_{jm}}L(y_{i},F_{m-1}(x_{i})+\gamma ).$

حجم الأشجار

$J$ ، رقم العقد الطرفية في الأشجار ، هو معلمة الطريقة التي يمكن ضبطها لمجموعة بيانات في متناول اليد. يتحكم في الحد الأقصى المسموح به للتفاعل بين المتغيرات في النموذج. مع $J=2$ ( جذوع القرار ) ، لا يسمح بالتفاعل بين المتغيرات. مع $J=3$ قد يشتمل النموذج على تأثيرات التفاعل بين ما يصل إلى متغيرين ، وهكذا.

هاستي وآخرون. علق ذلك بشكل طبيعي $4\leq J\leq 8$ تعمل بشكل جيد لتعزيز والنتائج ليست حساسة إلى حد ما لاختيار $J$ في هذا النطاق ، $J=2$ غير كافية للعديد من التطبيقات ، و $J>10$ من غير المرجح أن تكون مطلوبة.

تسوية

يمكن أن يؤدي تركيب مجموعة التدريب عن كثب إلى تدهور قدرة تعميم النموذج. عدة ما يسمى تنظيم تقنيات الحد من هذه overfitting التأثير من خلال تقييد الإجراء المناسب.

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

معلمة تنظيم أخرى هي عمق الأشجار. كلما زادت القيمة ، كلما زاد احتمال احتواء النموذج على بيانات التدريب.

انكماش

يتمثل جزء مهم من طريقة تعزيز التدرج اللوني في التقلص الذي يتكون من تعديل قاعدة التحديث كما يلي:

$F_{m}(x)=F_{m-1}(x)+\nu \cdot \gamma _{m}h_{m}(x),\quad 0<\nu \leq 1,$

من الناحية العملية ، وجد أن استخدام معدلات التعلم الصغيرة (مثل $\nu <0.1$ ) يعطي تحسينات هائلة في قدرة تعميم النماذج على زيادة التدرج دون تقلص ( $\nu =1$ ). ومع ذلك ، فإنه يأتي بثمن زيادة الوقت الحسابي أثناء التدريب والاستعلام : يتطلب معدل التعلم الأقل المزيد من التكرار.

مؤشر ستوكاستيك يعزز التدرج

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

حجم العينة الفرعي هو جزء ثابت $f$ من حجم مجموعة التدريب. متى $f=1$ ، الخوارزمية حتمية ومماثلة للخريطة الموضحة أعلاه. قيم أصغر من $f$ إدخال العشوائية في الخوارزمية والمساعدة في منع التحليق ، كنوع من التنظيم . تصبح الخوارزمية أسرع أيضًا ، لأن أشجار الانحدار يجب أن تكون مناسبة لمجموعات البيانات الأصغر في كل تكرار. حصل فريدمان على ذلك $0.5\leq f\leq 0.8$ يؤدي إلى نتائج جيدة لمجموعات التدريب الصغيرة والمتوسطة الحجم. وبالتالي، $f$ يتم ضبطه عادة على 0.5 ، مما يعني أن نصف مجموعة التدريب يستخدم لبناء كل متعلم أساسي.

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

عدد الملاحظات في الأوراق

غالبًا ما تستخدم تطبيقات تدعيم شجرة التدرج أيضًا التنظيم عن طريق تحديد الحد الأدنى لعدد الملاحظات في العقد الطرفية للأشجار (تسمى هذه المعلمة n.minobsinnode في حزمة R gbm ). يتم استخدامه في عملية بناء الأشجار من خلال تجاهل أي انشقاقات تؤدي إلى عقد تحتوي على أقل من هذا العدد من حالات مجموعة التدريب.

فرض هذا الحد يساعد على تقليل التباين في التنبؤات في الأوراق.

يعاقب على تعقيد شجرة

تقنيات أخرى مفيدة لتنظيم الأشجار المعززة التدرج هي معاقبة نموذج التعقيد للنموذج المكتسب. يمكن تعريف تعقيد النموذج على أنه العدد النسبي للأوراق في الأشجار المستفادة. يقابل التحسين المشترك للخسارة وتعقيد النموذج خوارزمية ما بعد التقليم لإزالة الفروع التي تخفق في تقليل الفاقد بمقدار عتبة. أنواع أخرى من التنظيم مثل $\ell _{2}$ ويمكن أيضا أن تضاف عقوبة على القيم ورقة لتجنب overfitting .

استعمال

تعزيز التدرج يمكن استخدامها في مجال التعلم لتصنيف . يستخدم محركا البحث التجاري على الويب Yahoo و Yandex أشكالًا مختلفة من التدرج التدريجي في محركات التصنيف التي تعلمتها الآلة.

أسماء

طريقة يمر بها مجموعة متنوعة من الأسماء. قدم فريدمان أسلوبه في الانحدار باعتباره "آلة تعزيز التدرج" (GBM). ميسون ، باكستر وآخرون. وصف الفئة التجريدية المعممة للخوارزميات بأنها "تعزيز التدرج الوظيفي". فريدمان وآخرون. وصف تقدم نماذج التدرج المعزز كأشجار انحدار مضافة متعددة (MART) ؛ Elith et al. وصف هذا النهج بأنه "أشجار الانحدار المعزز" (BRT).

هناك تطبيق مفتوح المصدر شائع لـ R يطلق عليه "نموذج التعميم العام" ، ومع ذلك تستخدم الحزم التي توسع هذا العمل BRT. تستخدم التطبيقات التجارية من Salford Systems أسماء "أشجار الانحدار المضافة المتعددة" (MART) و TreeNet ، وكلاهما علامة تجارية.  

أنظر أيضا

• AdaBoost
• غابة عشوائية
• XGBoost
• CatBoost
• تعلم شجرة القرار

روابط خارجية

• كيفية شرح زيادة التدرج.
• الانحدار عززت أشجار الانحدار.

[[تصنيف:خوارزميات تصنيف]] [[تصنيف:صفحات بترجمات غير مراجعة]]