معيار التعلم لقواعد الاحتمالات

يقترح هذا البحث معيار تعلم لقواعد الاحتمالات. يتم تطوير هذا المعيار من خلال توسيع نموذج التعلم PAC لValiant (صحيح تقريبًا على الأرجح)، والذي يعد معيار تعلم للقواعد الحتمية. تشير قواعد الاحتمالات هنا إلى تلك التي تعين احتماليًا عددًا من الفئات، lYr، لكل متجه خاصية X. يعتمد المعيار المقترح على فكرة أن تعلم قواعد الاحتمالات يمكن اعتبارها تحديدًا صحيحًا تقريبًا لتوزيعات الاحتمالات الشرطية عبر الفئات للمتجهات الخاصة المدخلة المعطاة. يُستخدم خوارزمية (خوارزمية MDL) قائمة على مبدأ MDL (أقل طول وصف) لتعلم قواعد الاحتمالات. بشكل محدد، لقواعد الاحتمالات ذات التقسيم المحدود (التي يتم تحديد كل منها بعدد有限 من الخلايا المتميزة في النطاق وناقل معلمات احتمالية مرتبط بها)، يستنتج هذا البحث حدودًا عليا تعتمد على الهدف وحدودًا عليا في أسوأ الحالات لحجم العينة المطلوبة من قبل خوارزمية MDL لتعلم قواعد الاحتمالات بدقة وثقة معينة. استنادًا إلى هذه الحدود لحجم العينة، يثبت هذا البحث قابلية التعلم من حيث حجم العينة المتعدد الحدود للقوائم القرارية الاحتمالية (التي تم اقتراحها حديثًا في هذا البحث كنظير احتمالي لقوائم Rivest القرارية) مع حد أقصى من k رموز (k ثابت) في كل قرار، وقابلية التعلم من حيث حجم العينة المتعدد الحدود للأشجار القرارية الاحتمالية (نظير احتمالي لأشجار القرارات) بحد أقصى من k عمق. كما يتم اشتقاق الشروط الكافية لقابلية التعلم من حيث حجم العينة المتعدد الحدود وقابلية التعلم في الزمن المتعدد الحدود لأي فئات من قواعد الاحتمالات ذات التقسيم المحدود.