التسامح مع الأخطاء (التعلم الآلي)

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

فيما يلي، دع${\displaystyle X}$كن معنا${\displaystyle n}$فضاء إدخال ذو أبعاد n. ليكن${\displaystyle {\mathcal {H}}}$لنفترض وجود فئة من الدوال التي نرغب في استخدامها من أجل تعلم${\displaystyle \{0,1\}}$دالة الهدف ذات القيم -${\displaystyle f}$تم تعريفها على${\displaystyle X}$. يترك${\displaystyle {\mathcal {D}}}$ليكن توزيع المدخلات على${\displaystyle X}$هدف خوارزمية التعلم${\displaystyle {\mathcal {A}}}$يتمثل الهدف في اختيار الوظيفة الأفضل${\displaystyle h\in {\mathcal {H}}}$بحيث يقلل من${\displaystyle error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x))}$لنفترض أن لدينا دالة${\displaystyle size(f)}$التي يمكنها قياس مدى تعقيد${\displaystyle f}$. يترك${\displaystyle {\text{Oracle}}(x)}$كن أوراكلًا يُعيد مثالًا كلما تم استدعاؤه${\displaystyle x}$وملصقها الصحيح${\displaystyle f(x)}$.

عندما لا تفسد الضوضاء البيانات، يمكننا تعريف التعلم في إطار Valiant : ^{[ 1 ] [ 2 ]}

التعريف: نقول ذلك${\displaystyle f}$يمكن تعلمها بكفاءة باستخدام${\displaystyle {\mathcal {H}}}$في بيئة فاليانت ، إذا كانت هناك خوارزمية تعلم${\displaystyle {\mathcal {A}}}$الذي لديه إمكانية الوصول إلى${\displaystyle {\text{Oracle}}(x)}$ومتعددة الحدود${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$بحيث يكون لأي${\displaystyle 0<\varepsilon \leq 1}$و${\displaystyle 0<\delta \leq 1}$يُخرج هذا الأمر، في عدد من الاستدعاءات إلى أوراكل المحدودة بـ${\displaystyle p\left({\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,{\text{size}}(f)\right)}$، دالة${\displaystyle h\in {\mathcal {H}}}$الذي يرضي باحتمالية لا تقل عن${\displaystyle 1-\delta }$الحالة${\displaystyle {\text{error}}(h)\leq \varepsilon }$.

سنعرّف فيما يلي قابلية التعلم لـ${\displaystyle f}$عندما تتعرض البيانات لبعض التعديلات. ^{[ 3 ] [ 4 ] [ 5 ]}

في نموذج ضوضاء التصنيف ^{[ 6 ]} معدل الضوضاء${\displaystyle 0\leq \eta <{\frac {1}{2}}}$يتم تقديمها. ثم، بدلاً من${\displaystyle {\text{Oracle}}(x)}$التي تُعيد دائمًا التسمية الصحيحة للمثال${\displaystyle x}$خوارزمية${\displaystyle {\mathcal {A}}}$لا يمكن استدعاء أوراكل إلا إذا كان معيبًا${\displaystyle {\text{Oracle}}(x,\eta )}$سيؤدي ذلك إلى تغيير تصنيف${\displaystyle x}$باحتمال${\displaystyle \eta }$كما هو الحال في حالة فاليانت، فإن هدف خوارزمية التعلم${\displaystyle {\mathcal {A}}}$يتمثل الهدف في اختيار الوظيفة الأفضل${\displaystyle h\in {\mathcal {H}}}$بحيث يقلل من${\displaystyle error(h)=P_{x\sim {\mathcal {D}}}(h(x)\neq f(x))}$في التطبيقات، يصعب الوصول إلى القيمة الحقيقية لـ${\displaystyle \eta }$لكننا نفترض أن لدينا إمكانية الوصول إلى حدها الأعلى${\displaystyle \eta _{B}}$[ ^{7 ]} لاحظ أنه إذا سمحنا لمعدل الضوضاء بأن ^يكون${\displaystyle 1/2}$ثم يصبح التعلم مستحيلاً في أي قدر من وقت الحساب، لأن كل تصنيف لا ينقل أي معلومات حول الوظيفة المستهدفة.

التعريف: نقول ذلك${\displaystyle f}$يمكن تعلمها بكفاءة باستخدام${\displaystyle {\mathcal {H}}}$في نموذج ضوضاء التصنيف، إذا وُجدت خوارزمية تعلم${\displaystyle {\mathcal {A}}}$الذي لديه إمكانية الوصول إلى${\displaystyle {\text{Oracle}}(x,\eta )}$ومتعددة الحدود${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot )}$بحيث يكون لأي${\displaystyle 0\leq \eta \leq {\frac {1}{2}}}$، ${\displaystyle 0\leq \varepsilon \leq 1}$و${\displaystyle 0\leq \delta \leq 1}$يُخرج هذا الأمر، في عدد من الاستدعاءات إلى أوراكل المحدودة بـ${\displaystyle p\left({\frac {1}{1-2\eta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$، دالة${\displaystyle h\in {\mathcal {H}}}$ الذي يرضي باحتمالية على الأقل${\displaystyle 1-\delta }$الحالة${\displaystyle error(h)\leq \varepsilon }$.

يُعدّ تعلّم الاستعلام الإحصائي ^{[ 8 ]} نوعًا من أنواع مسائل التعلّم النشط التي تستخدم خوارزمية التعلّم${\displaystyle {\mathcal {A}}}$يمكن للمرء أن يقرر ما إذا كان سيطلب معلومات حول الاحتمالية${\displaystyle P_{f(x)}}$تلك دالة${\displaystyle f}$مثال على تسمية صحيحة${\displaystyle x}$ويتلقى إجابة دقيقة ضمن هامش التسامح${\displaystyle \alpha }$بشكل رسمي، كلما كانت خوارزمية التعلم${\displaystyle {\mathcal {A}}}$يُطلق عليه اسم العراف${\displaystyle {\text{Oracle}}(x,\alpha )}$، ويتلقى كاحتمالية التغذية الراجعة${\displaystyle Q_{f(x)}}$بحيث${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha }$.

التعريف: نقول ذلك${\displaystyle f}$يمكن تعلمها بكفاءة باستخدام${\displaystyle {\mathcal {H}}}$في نموذج التعلم الإحصائي للاستعلام، إذا وُجدت خوارزمية تعلم${\displaystyle {\mathcal {A}}}$الذي لديه إمكانية الوصول إلى${\displaystyle {\text{Oracle}}(x,\alpha )}$وكثيرات الحدود${\displaystyle p(\cdot ,\cdot ,\cdot )}$،${\displaystyle q(\cdot ,\cdot ,\cdot )}$، و${\displaystyle r(\cdot ,\cdot ,\cdot )}$بحيث يكون لأي ${\displaystyle 0<\varepsilon \leq 1}$ما يلي ينطبق:

1. ${\displaystyle {\text{Oracle}}(x,\alpha )}$يمكن التقييم${\displaystyle P_{f(x)}}$في الوقت المناسب${\displaystyle q\left({\frac {1}{\varepsilon }},n,size(f)\right)}$؛
2. ${\displaystyle {\frac {1}{\alpha }}}$يحدها${\displaystyle r\left({\frac {1}{\varepsilon }},n,size(f)\right)}$
3. ${\displaystyle {\mathcal {A}}}$يُخرج نموذجًا${\displaystyle h}$بحيث${\displaystyle يخطئ(h)<\varepsilon }$، في عدد من المكالمات إلى أوراكل المحددة بـ${\displaystyle p\left({\frac {1}{\varepsilon }},n,size(f)\right)}$.

لاحظ أن معامل الثقة${\displaystyle \delta }$لا يظهر في تعريف التعلم. وذلك لأن الغرض الرئيسي من${\displaystyle \delta }$يتمثل الهدف في السماح لخوارزمية التعلم باحتمالية ضئيلة للفشل بسبب عينة غير ممثلة. منذ الآن${\displaystyle {\text{Oracle}}(x,\alpha )}$يضمن دائمًا تلبية معيار التقريب${\displaystyle Q_{f(x)}-\alpha \leq P_{f(x)}\leq Q_{f(x)}+\alpha }$لم تعد هناك حاجة إلى احتمال الفشل.

يُعد نموذج الاستعلام الإحصائي أضعف بكثير من نموذج PAC: فأي فئة قابلة للتعلم بكفاءة باستخدام نموذج الاستعلام الإحصائي تكون قابلة للتعلم بكفاءة باستخدام نموذج PAC في وجود ضوضاء التصنيف، ولكن توجد مشاكل قابلة للتعلم بكفاءة باستخدام نموذج PAC مثل التكافؤ ، ولكنها ليست قابلة للتعلم بكفاءة باستخدام نموذج الاستعلام الإحصائي. ^{[ 8 ]}

في نموذج التصنيف الخبيث ^{[ 9 ]،} يقوم المهاجم بتوليد أخطاء لإحباط خوارزمية التعلم. يصف هذا الإعداد حالات انفجار الأخطاء ، والتي قد تحدث عندما تتعطل معدات الإرسال بشكل متكرر لفترة محدودة. رسميًا، الخوارزمية${\displaystyle {\mathcal {A}}}$يُطلق عليه اسم العراف${\displaystyle {\text{Oracle}}(x,\beta )}$ذلك يُعيد مثالاً مُصنَّفاً بشكل صحيح${\displaystyle x}$مستمد، كالمعتاد، من التوزيع${\displaystyle {\mathcal {D}}}$على مساحة الإدخال باحتمالية${\displaystyle 1-\beta }$لكنها تعود باحتمالية${\displaystyle \beta }$مثال مستمد من توزيع لا علاقة له بـ${\displaystyle {\mathcal {D}}}$علاوة على ذلك، قد يتم اختيار هذا المثال المختار بشكل خبيث بشكل استراتيجي من قبل خصم لديه معرفة بـ${\displaystyle f}$،${\displaystyle \beta }$،${\displaystyle {\mathcal {D}}}$أو التقدم الحالي لخوارزمية التعلم.

التعريف: بالنظر إلى حد معين${\displaystyle \beta _{B}<{\frac {1}{2}}}$ل${\displaystyle 0\leq \beta <{\frac {1}{2}}}$نقول ذلك${\displaystyle f}$يمكن تعلمها بكفاءة باستخدام${\displaystyle {\mathcal {H}}}$في نموذج التصنيف الخبيث، إذا وُجدت خوارزمية تعلم${\displaystyle {\mathcal {A}}}$الذي لديه إمكانية الوصول إلى${\displaystyle {\text{Oracle}}(x,\beta )}$ومتعددة الحدود${\displaystyle p(\cdot ,\cdot ,\cdot ,\cdot ,\cdot )}$بحيث يكون لأي ${\displaystyle 0<\varepsilon \leq 1}$،${\displaystyle 0<\delta \leq 1}$يُخرج هذا الأمر، في عدد من الاستدعاءات إلى أوراكل المحدودة بـ${\displaystyle p\left({\frac {1}{1/2-\beta _{B}}},{\frac {1}{\varepsilon }},{\frac {1}{\delta }},n,size(f)\right)}$، دالة${\displaystyle h\in {\mathcal {H}}}$ الذي يرضي باحتمالية على الأقل${\displaystyle 1-\delta }$الحالة${\displaystyle error(h)\leq \varepsilon }$.

في نموذج الضوضاء العشوائية غير المنتظمة ^{[ 10 ] [ 11 ]} ، تتعلم الخوارزمية دالة منطقية ، وهي عبارة عن أوراكل خبيث.${\displaystyle {\text{Oracle}}(x,\nu )}$قد يقلب كل منهما${\displaystyle i}$الجزء رقم - من المثال${\displaystyle x=(x_{1},x_{2},\ldots ,x_{n})}$بشكل مستقل باحتمالية${\displaystyle \nu _{i}\leq \nu }$.

يمكن لهذا النوع من الأخطاء أن يُفشل الخوارزمية بشكل لا يمكن إصلاحه، وفي الواقع تنطبق النظرية التالية:

في حالة الضوضاء العشوائية غير المنتظمة، خوارزمية${\displaystyle {\mathcal {A}}}$يمكن أن تُخرج دالة${\displaystyle h\in {\mathcal {H}}}$بحيث${\displaystyle error(h)<\varepsilon }$فقط إذا${\displaystyle \nu <2\varepsilon }$.