LPBoost

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

يُعدّ تعزيز البرمجة الخطية ( LPBoost ) مصنفًا خاضعًا للإشراف من عائلة مصنفات التعزيز . يعمل LPBoost على زيادة الهامش بين عينات التدريب من فئات مختلفة، وبالتالي فهو ينتمي أيضًا إلى فئة خوارزميات تصنيف الهامش .

لنفترض دالة تصنيفو:X→{-1،1}،{\displaystyle f:{\mathcal {X}}\to \{-1,1\},} الذي يصنف العينات من فضاءX{\displaystyle {\mathcal {X}}}يُصنّف البيانات إلى فئتين، تحملان الرمزين 1 و-1 على التوالي. LPBoost هي خوارزمية لتعلم دالة التصنيف هذه، وذلك باستخدام مجموعة من الأمثلة التدريبية ذات التصنيفات المعروفة. تُعدّ LPBoost تقنية تعلّم آلي مناسبة بشكل خاص للتصنيف المشترك واختيار الميزات في المجالات المنظمة.

نظرة عامة على LPBoost

كما هو الحال في جميع المصنفات المعززة، فإن دالة التصنيف النهائية تكون على الشكل التالي:

و(x)=∑ج=1جαجحج(x)،{\displaystyle f({\boldsymbol {x}})=\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}}),}

أينαج{\displaystyle \alpha _{j}}هي أوزان غير سالبة للمصنفات الضعيفةحج:X→{-1،1}{\displaystyle h_{j}:{\mathcal {X}}\to \{-1,1\}}كل مصنف ضعيف فرديحج{\displaystyle h_{j}}قد يكون أفضل قليلاً من العشوائي، لكن التركيبة الخطية الناتجة عن العديد من المصنفات الضعيفة يمكن أن تؤدي أداءً جيدًا للغاية.

LPBoost constructsو{\displaystyle f}بالبدء بمجموعة فارغة من المصنفات الضعيفة. وبشكل تكراري، يتم اختيار مصنف ضعيف واحد لإضافته إلى مجموعة المصنفات الضعيفة المدروسة، وإضافته، ثم يتم ضبط جميع الأوزان.α{\displaystyle {\boldsymbol {\alpha }}}يتم تعديل مجموعة المصنفات الضعيفة الحالية. وتتكرر هذه العملية حتى لا يتبقى أي مصنفات ضعيفة لإضافتها.

تُعرف خاصية تعديل جميع أوزان المصنف في كل تكرار بخاصية التصحيح الكامل . أما طرق التعزيز المبكرة، مثل AdaBoost ، فلا تمتلك هذه الخاصية، وبالتالي يكون تقاربها أبطأ.

البرنامج الخطي

وبشكل أعم، دعح={ح(⋅؛ω)|ω∈Ω}{\displaystyle {\mathcal {H}}=\{h(\cdot ;\omega )|\omega \in \Omega \}} هيالمصنفات الضعيفة التي قد تكون لانهائية ، والتي تُسمى أيضًا بالفرضيات . إحدى طرق صياغة المشكلة التي يحلها LPBoost هي كبرنامج خطي ذي عدد لا نهائي من المتغيرات.

البرنامج الخطي الأولي لـ LPBoost، الذي يُحسِّن على متجه الوزن غير السالبα{\displaystyle {\boldsymbol {\alpha }}}، المتجه غير السالبξ{\displaystyle {\boldsymbol {\xi }}}من متغيرات الركود والهامشρ{\displaystyle \rho }وهو التالي.

مينα،ξ،ρ-ρ+د∑ن=1ℓξنsb.t.∑ω∈Ωyنαωح(xن؛ω)+ξن≥ρ،ن=1،...،ℓ،∑ω∈Ωαω=1،ξن≥0،ن=1،...،ℓ،αω≥0،ω∈Ω،ρ∈R.{\displaystyle {\begin{array}{cl}{\underset {{\boldsymbol {\alpha }},{\boldsymbol {\xi }},\rho }{\min }}&-\rho +D\sum _{n=1}^{\ell }\xi _{n}\\{\textrm {sb.t.}}&\sum _{\omega \in \Omega } y_ {n}\alpha _ {\omega} h({\boldsymbol {x}}_{n};\omega )+\xi _{n}\geq \rho ,\qquad n=1,\dots ,\ell ,\\&\sum _{\omega \in \Omega }\alpha _ {\omega }=1,\\&\xi _{n}\geq 0,\qquad n=1,\dots,\ell ,\\&\alpha _{\omega }\geq 0,\qquad \omega \in \Omega ,\\&\rho \in {\mathbb {R} }.\end{array}}}

لاحظ تأثيرات المتغيرات الراكدةξ≥0{\displaystyle {\boldsymbol {\xi }}\geq 0}: يتم معاقبة معيارهم الواحد في دالة الهدف بمعامل ثابتد{\displaystyle D}، وهو ما يؤدي دائمًا - إذا كان صغيرًا بما فيه الكفاية - إلى برنامج خطي أولي قابل للتطبيق.

اعتمدنا هنا تدوين فضاء المعلماتΩأوميغابحيث يكون للاختيارω∈Ω{\displaystyle \omega \in \Omega }المصنف الضعيفح(⋅؛ω):X→{-1،1}{\displaystyle h(\cdot ;\omega ):{\mathcal {X}}\to \{-1,1\}} معرف بشكل فريد.

عندما تم تدوين البرنامج الخطي المذكور أعلاه لأول مرة في المنشورات المبكرة حول أساليب التعزيز، تم تجاهله باعتباره غير قابل للحل بسبب العدد الكبير من المتغيرات.α{\displaystyle {\boldsymbol {\alpha }}}. وفي وقت لاحق فقط تم اكتشاف أنه يمكن بالفعل حل مثل هذه البرامج الخطية بكفاءة باستخدام التقنية الكلاسيكية لتوليد الأعمدة .

توليد الأعمدة لـ LPBoost

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

مشكلة LPBoost المزدوجة

تُقابل الأعمدة في البرنامج الخطي الأولي الصفوف في البرنامج الخطي الثنائي . البرنامج الخطي الثنائي المكافئ لـ LPBoost هو البرنامج الخطي التالي.

الأعلىλ،γγsb.t.∑ن=1ℓyنح(xن؛ω)λن+γ≤0،ω∈Ω،0≤λن≤د،ن=1،...،ℓ،∑ن=1ℓλن=1،γ∈R.// _ {n}+\gamma \leq 0,\qquad \omega \in \Omega ,\\&0\leq \lambda _{n}\leq D,\qquad n=1,\dots ,\ell ,\\&\sum _{n=1}^{\ell }\lambda _{n}=1,\\&\gamma \in \mathbb {R} .\نهاية {صفيف}}}

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

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

لنفترض مجموعة جزئية من القيود المُحققة في المسألة الثنائية. لأي مجموعة جزئية منتهية، يمكننا حل البرنامج الخطي وبالتالي تحقيق جميع القيود. إذا استطعنا إثبات أنه من بين جميع القيود التي لم نضيفها إلى المسألة الثنائية، لا يوجد قيد واحد مُنتهك، نكون قد أثبتنا أن حل مسألتنا المُقيدة يُكافئ حل المسألة الأصلية. بتعبير أدق، ليكنγ*{\displaystyle \gamma ^{*}}ليكن قيمة دالة الهدف المثلى لأي حالة مقيدة. عندئذٍ، يمكننا صياغة مسألة بحث عن "القيد الأكثر انتهاكًا" في فضاء المسألة الأصلي، أي إيجادω*∈Ω{\displaystyle \omega ^{*}\in \Omega }مثل

ω*=argmaxω∈Ω∑ن=1ℓyنح(xن؛ω)λن.{\displaystyle \omega ^{*}={\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}.}

أي أننا نبحث في الفضاءح{\displaystyle {\mathcal {H}}}لقرار واحدح(⋅؛ω*){\displaystyle h(\cdot ;\omega ^{*})} تعظيم الطرف الأيسر من القيد الثنائي. إذا لم يكن بالإمكان انتهاك القيد بأي اختيار لجذع القرار، فلن يكون أي من القيود المقابلة فعالاً في المسألة الأصلية، وتكون المسألة المقيدة مكافئة.

ثابت الجزاءد{\displaystyle D}

القيمة الموجبة لثابت الجزاءد{\displaystyle D}يجب إيجادها باستخدام تقنيات اختيار النموذج . ومع ذلك، إذا اخترناد=1ℓν{\displaystyle D={\frac {1}{\ell \nu }}}، أينℓ{\displaystyle \ell }يمثل عدد عينات التدريب و0<ν<1{\displaystyle 0<\nu <1}ثم المعلمة الجديدةν{\displaystyle \nu }له الخصائص التالية.

  • ν{\displaystyle \nu }يمثل حدًا أعلى لنسبة أخطاء التدريب؛ أي، إذاك{\displaystyle k}يشير إلى عدد عينات التدريب المصنفة بشكل خاطئ، ثمكℓ≤ν{\displaystyle {\frac {k}{\ell }}\leq \nu }.
  • ν{\displaystyle \nu }يمثل الحد الأدنى لنسبة عينات التدريب الموجودة خارج أو على الهامش.

الخوارزمية

  • مدخل:
    • مجموعة التدريبX={x1،...،xℓ}{\displaystyle X=\{{\boldsymbol {x}}_{1},\dots ,{\boldsymbol {x}}_{\ell }\}}،xأنا∈X{\displaystyle {\boldsymbol {x}}_{i}\in {\mathcal {X}}}
    • ملصقات التدريبY={y1،...،yℓ}{\displaystyle Y=\{y_{1},\dots ,y_{\ell }\}}،yأنا∈{-1،1}{\displaystyle y_{i}\in \{-1,1\}}
    • عتبة التقاربθ≥0{\displaystyle \theta \geq 0}
  • الناتج:
    • دالة التصنيفو:X→{-1،1}{\displaystyle f:{\mathcal {X}}\to \{-1,1\}}
  1. التهيئة
    1. أوزان موحدةλن←1ℓ،ن=1،...،ℓ{\displaystyle \lambda _{n}\leftarrow {\frac {1}{\ell }},\quad n=1,\dots ,\ell }
    2. حافةγ←0{\displaystyle \gamma \leftarrow 0}
    3. عدد الفرضياتج←1{\displaystyle J\leftarrow 1}
  2. أعاد
    1. ح^←argmaxω∈Ω∑ن=1ℓyنح(xن؛ω)λن{\displaystyle {\hat {h}}\leftarrow {\underset {\omega \in \Omega }{\textrm {argmax}}}\sum _{n=1}^{\ell }y_{n}h({\boldsymbol {x}}_{n};\omega )\lambda _{n}}
    2. لو∑ن=1ℓyنح^(xن)λن+γ≤θ{\displaystyle \sum _{n=1}^{\ell }y_{n}{\hat {h}}({\boldsymbol {x}}_{n})\lambda _{n}+\gamma \leq \theta }ثم
      1. استراحة
    3. حج←ح^{\displaystyle h_{J}\leftarrow {\hat {h}}}
    4. ج←ج+1{\displaystyle J\leftarrow J+1}
    5. (λ،γ)←{\displaystyle ({\boldsymbol {\lambda }},\gamma )\leftarrow }حل ثنائي LPBoost
    6. α←{\displaystyle {\boldsymbol {\alpha }}\leftarrow }مضاعفات لاغرانج لحل المسألة الثنائية لـ LPBoost
  3. و(x):=لافتة(∑ج=1جαجحج(x)){\displaystyle f({\boldsymbol {x}}):={\textrm {sign}}\left(\sum _{j=1}^{J}\alpha _{j}h_{j}({\boldsymbol {x}})\right)}

لاحظ أنه إذا تم ضبط عتبة التقارب علىθ=0{\displaystyle \theta =0}الحل الذي تم الحصول عليه هو الحل الأمثل الشامل للبرنامج الخطي المذكور أعلاه. عملياً،θ{\displaystyle \theta }يتم ضبطها على قيمة موجبة صغيرة للحصول على حل جيد بسرعة.

هامش الربح المحقق

يُطلق على الهامش الفعلي الذي يفصل بين عينات التدريب اسم الهامش المحقق ، ويُعرَّف على النحو التالي:

ρ(α):=مينن=1،...،ℓyن∑αω∈Ωαωح(xن؛ω).{\displaystyle \rho ({\boldsymbol {\alpha }}):=\min _{n=1,\dots ,\ell }y_{n}\sum _{\alpha _{\omega }\in \Omega }\alpha _{\omega }h({\boldsymbol {x}}_{n};\omega ).}

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

ضمان التقارب

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

المتعلم الأساسي

LPBoost هي طريقة تعلم جماعية ، وبالتالي فهي لا تفرض اختيار المتعلمين الأساسيين، أو نطاق الفرضيات.ح{\displaystyle {\mathcal {H}}}أظهر ديميريز وآخرون أنه في ظل افتراضات بسيطة، يمكن استخدام أي نموذج تعلم أساسي. وإذا كانت نماذج التعلم الأساسية بسيطة للغاية، فغالباً ما يُشار إليها باسم " جذوع القرار" .

عدد المتعلمين الأساسيين الذين يُستخدمون عادةً مع تقنية التعزيز في الدراسات المنشورة كبير. على سبيل المثال، إذاX⊆Rن{\displaystyle {\mathcal {X}}\subseteq {\mathbb {R} }^{n}}يمكن أن يكون المتعلم الأساسي آلة متجهات دعم خطية ذات هامش ناعم . أو حتى أبسط من ذلك، جذع بسيط على شكل

ح(x؛ω∈{1،-1}،ص∈{1،...،ن}،ت∈R):={ωإذا~xص≤ت-ωخلاف ذلك.{\displaystyle h({\boldsymbol {x}};\omega \in \{1,-1\},p\in \{1,\dots ,n\},t\in {\mathbb {R} }):=\left\{{\begin{array}{cl}\omega &{\textrm {if~}}{\boldsymbol {x}}_{p}\leq t\\-\omega &{\textrm {otherwise}}\end{array}}\right..}

ينظر نموذج اتخاذ القرار المذكور أعلاه إلى بُعد واحد فقط.ص{\displaystyle p}من مساحة الإدخال، ويقوم ببساطة بتحديد عتبة العمود المقابل من العينة باستخدام عتبة ثابتةت{\displaystyle t}ثم، يمكنها اتخاذ القرار في أي من الاتجاهين، بناءً علىω{\displaystyle \omega }لفئة موجبة أو سالبة.

بفرض أوزان لعينات التدريب، فإن بناء جذع القرار الأمثل بالشكل المذكور أعلاه يتضمن ببساطة البحث على طول جميع أعمدة العينات وتحديدص{\displaystyle p}،ت{\displaystyle t}وω{\displaystyle \omega }من أجل تحسين دالة الكسب.

مراجع