الاستقرار (نظرية التعلم)

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

الاستقرار ، أو ما يُعرف أيضًا بالاستقرار الخوارزمي ، مفهومٌ في نظرية التعلم الحسابي يُشير إلى كيفية تغير مخرجات خوارزمية التعلم الآلي مع التغيرات الطفيفة في مدخلاتها. خوارزمية التعلم المستقرة هي تلك التي لا يتغير تنبؤها كثيرًا عند تعديل بيانات التدريب تعديلًا طفيفًا. على سبيل المثال، لنفترض خوارزمية تعلم آلي تُدرَّب على تمييز الأحرف المكتوبة بخط اليد، باستخدام 1000 مثال من الأحرف المكتوبة بخط اليد وتصنيفاتها ("من الألف إلى الياء") كمجموعة تدريب. إحدى طرق تعديل مجموعة التدريب هذه هي حذف مثال واحد، بحيث يتبقى 999 مثالًا فقط من الأحرف المكتوبة بخط اليد وتصنيفاتها. ستُنتج خوارزمية التعلم المستقرة مُصنِّفًا مشابهًا باستخدام كلتا مجموعتي التدريب، سواءً كانت 1000 مثال أو 999 مثالًا.

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

تاريخ

يتمثل أحد الأهداف الرئيسية في تصميم نظام التعلم الآلي في ضمان قدرة خوارزمية التعلم على التعميم ، أو الأداء بدقة على أمثلة جديدة بعد تدريبها على عدد محدود منها. في تسعينيات القرن الماضي، تحققت إنجازات هامة في تحديد حدود التعميم لخوارزميات التعلم الخاضع للإشراف . وكانت التقنية المستخدمة تاريخيًا لإثبات التعميم هي إظهار اتساق الخوارزمية ، وذلك باستخدام خصائص التقارب المنتظم للكميات التجريبية نحو متوسطاتها. وقد استُخدمت هذه التقنية للحصول على حدود التعميم لفئة واسعة من خوارزميات تقليل المخاطر التجريبية (ERM). وخوارزمية تقليل المخاطر التجريبية هي خوارزمية تختار حلاً من فضاء الفرضيات.ح{\displaystyle H}بطريقة تقلل من الخطأ التجريبي على مجموعة التدريبS{\displaystyle S}.

تتمثل إحدى النتائج العامة، التي أثبتها فلاديمير فابنيك لخوارزميات التصنيف الثنائي ERM ، في أنه لأي دالة هدف وتوزيع إدخال، فإن أي فضاء فرضياتح{\displaystyle H}مع بُعد VCد{\displaystyle d}، ون{\displaystyle n}مع أمثلة التدريب، تكون الخوارزمية متسقة وستنتج خطأ تدريب لا يتجاوزيا(دن){\displaystyle O\left({\sqrt {\frac {d}{n}}}\right)}(بالإضافة إلى عوامل لوغاريتمية) من الخطأ الحقيقي. وقد تم توسيع نطاق هذه النتيجة لاحقًا لتشمل خوارزميات شبه ERM ذات فئات الدوال التي لا تحتوي على نقاط دنيا فريدة.

أرست أعمال فابنيك، باستخدام ما أصبح يُعرف بنظرية VC ، علاقة بين تعميم خوارزمية التعلم وخصائص فضاء الفرضيات.ح{\displaystyle H}فيما يتعلق بالوظائف التي يتم تعلمها. مع ذلك، لا يمكن تطبيق هذه النتائج على الخوارزميات ذات فضاءات الفرضيات ذات بُعد VC غير المحدود. بعبارة أخرى، لا يمكن تطبيق هذه النتائج عندما تكون المعلومات التي يتم تعلمها ذات تعقيد كبير جدًا بحيث يتعذر قياسه. بعض أبسط خوارزميات التعلم الآلي - على سبيل المثال، خوارزميات الانحدار - لها فضاءات فرضيات ذات بُعد VC غير محدود. مثال آخر هو خوارزميات تعلم اللغة التي يمكنها إنتاج جمل ذات أطوال عشوائية.

طُوِّر تحليل الاستقرار في العقد الأول من الألفية الثانية لنظرية التعلم الحسابي ، وهو أسلوب بديل للحصول على حدود التعميم. يُعد استقرار الخوارزمية خاصية من خصائص عملية التعلم، وليس خاصية مباشرة لمساحة الفرضيات.ح{\displaystyle H}ويمكن تقييم ذلك في الخوارزميات التي تحتوي على فضاءات فرضيات ذات بُعد VC غير محدود أو غير مُحدد، مثل خوارزمية أقرب جار. خوارزمية التعلم المستقرة هي تلك التي لا تتغير دالتها المُتعلمة كثيرًا عند تعديل مجموعة التدريب تعديلًا طفيفًا، على سبيل المثال بحذف مثال. يُستخدم مقياس خطأ حذف عنصر واحد في خوارزمية التحقق المتقاطع بحذف عنصر واحد (CVloo) لتقييم استقرار خوارزمية التعلم بالنسبة لدالة الخسارة . وبذلك، يُعد تحليل الاستقرار تطبيقًا لتحليل الحساسية في مجال التعلم الآلي.

ملخص النتائج الكلاسيكية

  • أوائل القرن العشرين - تم وصف الاستقرار في نظرية التعلم لأول مرة من حيث استمرارية خريطة التعلمل{\displaystyle L}، تم تتبعه إلى أندريه نيكولايفيتش تيخونوف .
  • 1979 - لاحظ ديفروي وواغنر أن سلوك حذف عنصر واحد في الخوارزمية يرتبط بحساسيتها للتغيرات الطفيفة في العينة. [ 2 ]
  • 1999 - اكتشف كيرنز ورون وجود صلة بين البعد المحدود لـ VC والاستقرار. [ 3 ]
  • في عام 2002 ، اقترح بوسكيه وإليسيف، في ورقة بحثية رائدة، مفهوم استقرار الفرضيات المنتظم لخوارزمية التعلم، وأظهرا أنه يؤدي إلى انخفاض خطأ التعميم . ومع ذلك، يُعد استقرار الفرضيات المنتظم شرطًا قويًا لا ينطبق على فئات واسعة من الخوارزميات، بما في ذلك خوارزميات ERM ذات فضاء الفرضيات المكون من دالتين فقط. [ 4 ]
  • في عام 2002 ، قام كوتين ونيوجي بتوسيع نتائج بوسكيه وإليسيف من خلال تقديم حدود تعميمية لعدة أشكال أضعف من الاستقرار أطلقوا عليها اسم " الاستقرار شبه الشامل" . علاوة على ذلك، فقد اتخذوا خطوة أولية في إرساء العلاقة بين الاستقرار والاتساق في خوارزميات ERM في إطار "الصواب التقريبي المحتمل" (PAC). [ 5 ]
  • في عام 2004 ، أثبت بوجيو وآخرون وجود علاقة عامة بين الاستقرار واتساق خوارزمية إدارة المخاطر. واقترحوا صيغة إحصائية لاستقرار حذف عنصر واحد، أطلقوا عليها اسم استقرار CVEEEloo ، وأظهروا أنها: أ) كافية للتعميم في فئات الخسارة المحدودة، و ب) ضرورية وكافية لاتساق (وبالتالي تعميم) خوارزميات إدارة المخاطر لبعض دوال الخسارة مثل خسارة التربيع، والقيمة المطلقة، وخسارة التصنيف الثنائي. [ 6 ]
  • في عام 2010 ، لاحظ شاليف شوارتز وآخرون وجود مشاكل في النتائج الأصلية لـ فابنيك بسبب العلاقات المعقدة بين فضاء الفرضيات وفئة الخسارة. وناقشوا مفاهيم الاستقرار التي تشمل فئات الخسارة المختلفة وأنواع التعلم المختلفة، الخاضعة للإشراف وغير الخاضعة للإشراف. [ 7 ]
  • 2016 - أثبت موريتز هاردت وآخرون استقرار خوارزمية التدرج الهبوطي في ظل افتراضات معينة حول الفرضية وعدد مرات استخدام كل حالة لتحديث النموذج. [ 8 ]

تعريفات أولية

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

خوارزمية التعلم الآلي، والمعروفة أيضًا باسم خريطة التعلمل{\displaystyle L}، تقوم برسم خريطة لمجموعة بيانات التدريب ، وهي عبارة عن مجموعة من الأمثلة المصنفة(x،y){\displaystyle (x,y)}، على دالةو{\displaystyle f}منX{\displaystyle X}لY{\displaystyle Y}، أينX{\displaystyle X}وY{\displaystyle Y}تقع هذه الدوال في نفس نطاق أمثلة التدريب.و{\displaystyle f}يتم اختيارها من فضاء فرضيات للدوال يسمىح{\displaystyle H}.

تُعرَّف مجموعة التدريب التي يتعلم منها الخوارزمية على النحو التالي:

S={z1=(x1، y1) ،..، zم=(xم، yم)}{\displaystyle S=\{z_{1}=(x_{1},\ y_{1})\ ,..,\ z_{m}=(x_{m},\ y_{m})\}}

وهو بحجمم{\displaystyle m}فيZ=X×Y{\displaystyle Z=X\times Y}

تم سحبها بشكل مستقل ومتطابق التوزيع من توزيع غير معروف D.

وبالتالي، خريطة التعلمل{\displaystyle L}يُعرَّف بأنه عملية ربط منZم{\displaystyle Z_{m}}داخلح{\displaystyle H}رسم خريطة لمجموعة التدريبS{\displaystyle S}على دالةوS{\displaystyle f_{S}}منX{\displaystyle X}لY{\displaystyle Y}هنا، نقتصر على دراسة الخوارزميات الحتمية حيثل{\displaystyle L}متناظر بالنسبة إلىS{\displaystyle S}أي أن ذلك لا يعتمد على ترتيب العناصر في مجموعة التدريب. علاوة على ذلك، نفترض أن جميع الدوال قابلة للقياس وأن جميع المجموعات قابلة للعد.

الخسارةV{\displaystyle V}فرضيةو{\displaystyle f}فيما يتعلق بمثالz=(x،y){\displaystyle z=(x,y)}ثم يُعرَّف على النحو التالي:V(و،z)=V(و(x)،y){\displaystyle V(f,z)=V(f(x),y)}.

الخطأ التجريبي لـو{\displaystyle f}يكونأناS[و]=1ن∑V(و،zأنا){\displaystyle I_{S}[f]={\frac {1}{n}}\sum V(f,z_{i})}.

الخطأ الحقيقي لـو{\displaystyle f}يكونأنا[و]=هـzV(و،z){\displaystyle I[f]=\mathbb {E} _{z}V(f,z)}

بالنظر إلى مجموعة تدريب S بحجم m، سنقوم ببناء مجموعات تدريب معدلة لجميع قيم i = 1....,m على النحو التالي:

  • بإزالة العنصر رقم i

S|أنا={z1،...، zأنا-1، zأنا+1،...، zم}{\displaystyle S^{|i}=\{z_{1},...,\ z_{i-1},\ z_{i+1},...,\ z_{m}\}}

  • عن طريق استبدال العنصر رقم i

Sأنا={z1،...، zأنا-1، zأنا′، zأنا+1،...، zم}{\displaystyle S^{i}=\{z_{1},...,\ z_{i-1},\ z_{i}',\ z_{i+1},...,\ z_{m}\}}

تعريفات الاستقرار

استقرار الفرضية

خوارزميةل{\displaystyle L}تتمتع الفرضية باستقرار β فيما يتعلق بدالة الخسارة V إذا تحقق ما يلي:

∀أنا∈{1،...،م}،هـS،z[|V(وS،z)-V(وS|أنا،z)|]≤β.{\displaystyle \forall i\in \{1,...,m\},\mathbb {E} _{S,z}[|V(f_{S},z)-V(f_{S^{|i}},z)|]\leq \beta .}

استقرار الفرضية نقطة بنقطة

خوارزميةل{\displaystyle L}تتمتع باستقرار فرضية نقطي β بالنسبة لدالة الخسارة V إذا تحقق ما يلي:

∀أنا∈ {1،...،م}،هـS[|V(وS،zأنا)-V(وS|أنا،zأنا)|]≤β.{\displaystyle \forall i\in \ \{1,...,m\},\mathbb {E} _{S}[|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|]\leq \beta .}

استقرار الخطأ

خوارزميةل{\displaystyle L}تتمتع بثبات خطأ β بالنسبة لدالة الخسارة V إذا تحقق ما يلي:

∀S∈Zم،∀أنا∈{1،...،م}،|هـz[V(وS،z)]-هـz[V(وS|أنا،z)]|≤β{\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},|\mathbb {E} _{z}[V(f_{S},z)]-\mathbb {E} _{z}[V(f_{S^{|i}},z)]|\leq \beta }

استقرار موحد

خوارزميةل{\displaystyle L}تتمتع بثبات منتظم β بالنسبة لدالة الخسارة V إذا تحقق ما يلي:

∀S∈Zم،∀أنا∈{1،...،م}،رشفةz∈Z|V(وS،z)-V(وS|أنا،z)|≤β{\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta }

الصيغة الاحتمالية للاستقرار المنتظم β هي:

∀S∈Zم،∀أنا∈{1،...،م}،PS{رشفةz∈Z|V(وS،z)-V(وS|أنا،z)|≤β}≥1-دلتا{\displaystyle \forall S\in Z^{m},\forall i\in \{1,...,m\},\mathbb {P} _{S}\{\sup _{z\in Z}|V(f_{S},z)-V(f_{S^{|i}},z)|\leq \beta \}\geq 1-\delta }

يُقال إن الخوارزمية مستقرة عندما تكون قيمةβ{\displaystyle \beta }يتناقص معيا(1م){\displaystyle O({\frac {1}{m}})}.

استقرار التحقق المتقاطع بحذف عنصر واحد (CVloo)

خوارزميةل{\displaystyle L}تتمتع بثبات CVloo β بالنسبة لدالة الخسارة V إذا تحقق ما يلي:

∀أنا∈{1،...،م}،PS{|V(وS،zأنا)-V(وS|أنا،zأنا)|≤βجV}≥1-دلتاجV{\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{|V(f_{S},z_{i})-V(f_{S^{|i}},z_{i})|\leq \beta _{CV}\}\geq 1-\delta _{CV}}

تعريف استقرار (CVloo) يعادل استقرار الفرضية النقطية الذي تم عرضه سابقًا.

خطأ متوقع في حذف عنصر واحد (هـلooهـرر{\displaystyle Eloo_{err}}) استقرار

خوارزميةل{\displaystyle L}لديههـلooهـرر{\displaystyle Eloo_{err}}الاستقرار إذا كان لكل n يوجدβهـلم{\displaystyle \beta _{EL}^{m}}و أدلتاهـلم{\displaystyle \delta _{EL}^{m}}بحيث:

∀أنا∈{1،...،م}،PS{|أنا[وS]-1م∑أنا=1مV(وS|أنا،zأنا)|≤βهـلم}≥1-دلتاهـلم{\displaystyle \forall i\in \{1,...,m\},\mathbb {P} _{S}\{|I[f_{S}]-{\frac {1}{m}}\sum _{i=1}^{m}V(f_{S^{|i}},z_{i})|\leq \beta _{EL}^{m}\}\geq 1-\delta _{EL}^{m}}، معβهـلم{\displaystyle \beta _{EL}^{m}}ودلتاهـلم{\displaystyle \delta _{EL}^{m}}الوصول إلى الصفر لـم،→∞{\displaystyle m,\rightarrow \infty }

النظريات الكلاسيكية

من بوسكيه وإليسيف (02) :

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

يُعدّ الاستقرار المنتظم شرطًا قويًا لا تستوفيه جميع الخوارزميات، ولكنه، على نحوٍ مُثير للدهشة، يستوفيه فئة كبيرة وهامة من خوارزميات التنظيم. ويُقدّم حدّ التعميم في المقالة.

من موخيرجي وآخرون (06) :

  • بالنسبة لخوارزميات التعلم المتناظر ذات الخسارة المحدودة، إذا كانت الخوارزمية تتمتع بكل من استقرار التحقق المتقاطع بحذف عنصر واحد (CVloo) وخطأ حذف عنصر واحد المتوقع (هـلooهـرر{\displaystyle Eloo_{err}}) الاستقرار كما هو محدد أعلاه، ثم تعمم الخوارزمية.
  • لا يكفي أي من الشرطين بمفرده للتعميم. ومع ذلك، فإن الجمع بينهما يضمن التعميم (بينما العكس غير صحيح).
  • بالنسبة لخوارزميات ERM على وجه التحديد (على سبيل المثال لخسارة المربع)، فإن التحقق المتقاطع Leave-one-out (CVloo) ضروري وكافٍ للاتساق والتعميم.

تُعدّ هذه النتيجة مهمة لأسس نظرية التعلّم، لأنها تُظهر أن خاصيتين كانتا غير مرتبطتين سابقًا للخوارزمية، وهما الاستقرار والاتساق، متكافئتان بالنسبة لخوارزمية ERM (وبعض دوال الخسارة). وقد ورد حدّ التعميم في المقالة.

خوارزميات مستقرة

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

مراجع

  1. ↑ بوسكيه، أوليفييه؛ إليسيف، أندريه (2002). "الاستقرار والتعميم" . مجلة أبحاث تعلم الآلة . 2 (مارس): 499-526 . ISSN 1533-7928 . 
  2. 1 2 L. Devroye and Wagner, Distribution-free performance bounds for potential function rules, IEEE Trans. Inf. Theory 25(5) (1979) 601–604.
  3. ↑ M. Kearns and D. Ron , Algorithmic stability and sanity-check bounds for leave-one-out cross validation, Neural Comput. 11(6) (1999) 1427–1453.
  4. 1 2 3 4 5 O. Bousquet and A. Elisseeff. Stability and generalization. J. Mach. Learn. Res., 2:499–526, 2002.
  5. ↑ S. Kutin and P. Niyogi, Almost-everywhere algorithmic stability and generalization error, Technical Report TR-2002-03, University of Chicago (2002).
  6. ↑ إس. موخرجي، بي. نيوجي، تي. بوجيو، و آر إم ريفكين. نظرية التعلم: الاستقرار كافٍ للتعميم وضروري وكافٍ لاتساق تقليل المخاطر التجريبية. مجلة الرياضيات الحاسوبية المتقدمة، 25(1-3):161–193، 2006.
  7. ↑ Shalev Shwartz, S., Shamir, O., Srebro, N., Sridharan, K., Learnability, Stability and Uniform Convergence, Journal of Machine Learning Research, 11(Oct):2635-2670, 2010.
  8. ↑ موريتز هاردت، بنيامين ريخت، يورام سينجر، التدريب بشكل أسرع، والتعميم بشكل أفضل: استقرار التدرج العشوائي، ICML 2016.
  9. ↑ إليسيف، أ. دراسة حول استقرار الخوارزميات وعلاقتها بأداء التعميم. تقرير فني. (2000)
  10. 1 2 ريفكين، ر. كل قديم جديد مرة أخرى: نظرة جديدة على المناهج التاريخية في التعلم الآلي. أطروحة دكتوراه، معهد ماساتشوستس للتكنولوجيا، 2002
  11. ↑ روساسكو، ل. وبوجيو، ت. استقرار تنظيم تيخونوف ، 2009

للمزيد من القراءة

  • S.Kutin وP.Niyogi. الاستقرار الخوارزمي وخطأ التعميم في كل مكان تقريبًا. في بروك. من UAI 18، 2002
  • س. راخلين، س. موخرجي، وت. بوجيو. نتائج الاستقرار في نظرية التعلم. التحليل والتطبيقات، 3(4): 397-419، 2005
  • في. إن. فابنيك. طبيعة نظرية التعلم الإحصائي. سبرينغر، 1995
  • فابنيك، ف.، نظرية التعلم الإحصائي. وايلي، نيويورك، 1998
  • بوجيو، تي.، ريفكين، آر.، موخرجي، إس. ونيوجي، بي.، "نظرية التعلم: الشروط العامة للتنبؤ"، مجلة نيتشر، المجلد 428، الصفحات 419-422، 2004
  • أندريه إليسيف، ثيودوروس إيفجينيو، ماسيميليانو بونتيل، استقرار خوارزميات التعلم العشوائي، مجلة أبحاث تعلم الآلة 6، 55-79، 2010
  • إليسيف، أ. بونتيل، م.، خطأ حذف عنصر واحد واستقرار خوارزميات التعلم مع التطبيقات، سلسلة علوم الناتو، السلسلة الفرعية الثالثة، علوم الحاسوب والأنظمة، 2003، المجلد 190، الصفحات 111-130
  • شاليف شوارتز، إس.، شامير، أو.، سريبرو، إن.، سريدهاران، ك.، قابلية التعلم، والاستقرار، والتقارب المنتظم، مجلة أبحاث تعلم الآلة، 11 (أكتوبر): 2635-2670، 2010