يكي از رساترين و خواناترين باز نماييها براي يادگيري قضيه ها مجموعه قوانين if then است ما در اين مطلعه چندين الگوريتم براي چنين مجموعه قوانيني را مورد بررسي قرار مي دهيم . يك مورد خاص و مهم كه در يادگيري مجموعه قوانين درگير شده است شامل متغييرهايي است كه بندهاي Horn اول ترتيب ناميده مي شود به دليل اينكه مجموعه بندهاي Horn اول ترتيب مي تواند به برنامه هايي در زبان برنامه نويسي منطقي prolog تبديل شود .
محصولات مرتبط
 |  |
 | |
1. مقدمه
در تعداد زيادي از موارد يادگيري تابع هدف كه مانند يك مجموعه از قوانين If Then نشان داده شده است مفيد مي باشد. راههايي براي يادگيري مجموعه قوانين از طريق درخت تصميم و از طريق الگوريتم ژنتيك ارائه گشته است ولي در اين مطالعه ما قصد داريم تعدادي از الگوريتمهايي را كه مستقيماٌ مجموعه قوانين را ياد مي گيرند بررسي كنيم دو تفاوت اصلي اين الگوريتمها با الگوريتمها ي ذكر شده به ترتيب زير است اول : آنها براي يادگيري مجموعه قوانين اول ترتيب طراحي شده اند كه شامل متغيير ها هستند و اهميت اين قوانين رساتر بودن آنها به نسبت قوانين گزاره اي است دوم : الگوريتمهاي كه در اينجا بحث شده الگوريتمهاي پوششي متوالي[1] كه هر قانون در يك زمان ياد مي گيرد و به صورت افزايشي مجموعه قانون هاي نهايي توليد مي شود .
به عنوان مثال از يك مجموعه قوانين اول ترتيب دو قانون كه در زير مفهوم اجداد را توصيف مي كند در نظر بگيريد . در اينجا دو گزاره parent(x,y) نشان مي دهد كه y پدر يا مادر x است وگزاره Ancestor(x,y) نشان ميدهد كه y جد x است .
IF parent (x,y) THEN Ancestor(x,y)
IF parent (x,z)^ Ancestor (z,y) THEN Ancestor(x,y)
اين دو قانون به صورت فشرده يك تابع بازگشتي را توصيف مي كند كه بازنمايي آن به وسيله درخت تصميم و يا ديگر بازنماييها گزاره اي بسيار مشكل خواهد بود . يك راه براي ديدن قدرت بازنمايي قوانين اول ترتيب در نظر گرفتن زبان برنامه نويسي Prolog است درProlog برنامه ها مجموعه اي از قوانين اول ترتيب هستند همانگونه كه در بالا نشان داده شده است در عمل سيستمهاي يادگيري بر اساس بازنمايي اول ترتيبها در بكار بردن براي مشكلاتي چون يادگيري مسائلي در شيمي و يا يادگيري طراحي المانهاي نهايي براي تحليل استرس در يك ساختار فيزيكي و غيره كاربرد دارند و در همه اين كابردها فرضيه هايي كه بايد بازنمايي مي شدند در يك اعلان رابطه اي جاي گرفتند كه به راحتي با استفاده از بازنمايي هاي اول ترتيب قابل توصيف است در حاليكه توصيف آنها با استفاده از بازنماييهاي گزاره اي بسيار مشكل است .
در ادامه ما يك سري الگوريتمهايي كه مجموعه قوانين گزاره اي را ياد مي گيرند در نظر مي گيريم و سپس الگوريتمهايي براي جستجوي فضاي فرضيه ها به منظور يادگرفتن مجموعه فصلي قوانين كه اين دسته فهمش بسيار راحت تر است و بعد از اين مرحله توسعه اين الگوريتمها را در نظر مي گيريم كه بتوانند قوانين اول ترتيب را ياد بگيرند .
2. الگوريتمهاي پوشش متوالي
در اينجا خانواده اي از الگوريتمها در نظر گرفته مي شود كه يادگيري قوانين را بر پايه يادگيري يك قانون و حذف آن داده هايي كه ان قانون پوشش ميدهد و سپس تكراردوباره اين پروسس مي باشد اين الگوريتمها الگوريتمهاي پوشش متوالي ناميده مي شوند . تصور كنيد ما يك زير رويه[2] ” يادگيري يك قانون “[3] داريم كه يك مجموعه از مثالهاي آموزشي مثبت و منفي را به عنوان ورودي قبول مي كند وسپس يك قانون توليد مي كند كه تعداد زيادي از مثالهاي مثبت و تعداد كمي از مثالهاي منفي را پوشش مي دهد ما نياز داريم كه اين قانون خروجي بيشترين دقت را دارا باشد ولي لزومي ندارد بيشترين پوشش دهي را دارا باشد . منظور از دقت بالا اين است كه آن پيشگويي هايي كه اين قانون توليد مي كند بايد درست باشند و قبول كردن پوشش دهي كم به اين معني است كه نياز نيست كه براي همه مثالهاي آموزشي پيشگويي انجام شود .
زير رويه ” يادگيري يك قانون ” براي يادگيري يك قانون داده شده و يك خط مشي واضح براي يادگيري قوانين فراخواني ” يادگيري يك قانون ” روي همه مثال هاي آموزشي در دسترس است و حذف مثالهاي مثبت كه بوسيله آن قانوني كه ياد مي گيرد پوشش داده مي شود و سپس آنرا مجدداٌ فراخواني مي كند كه قانون دوم را براساس مثالهاي آموزشي باقيمانده ياد بگيرد . اين پروسيجراين پروسيجر مي تواند بارها و بارها تكرار شود تا از طريق مجموعه فصلي از قوانيني كه يادگرفته هر كسر مطلوبي از مثالهاي مثبت را پوشش دهند .
و اين الگوريتم پوشش متوالي ناميده مي شود . بخاطر توالي كه در يادگيري قوانين براي اينكه مجموعه كامل از مثالهاي مثبت را پوشش دهد . مجموعه قوانين ياد گرفته شده مي توانند بر حسب دقت مرتب شوند و وقتي كه يك نمونه جديد براي طبقه بندي وجود دارد اول پردقت ترين در نظر گرفته شوند . يك نمونه از اين الگوريتم در شكل آمده است .
الگوريتم پوشش متوالي يكي از شايع ترين خط مشي ها براي يادگيري مجموعه فصلي قوانين است .
اين الگوريتم مشكل يادگيري مجموعه فصلي قوانين را به توالي از مشكلات ساده تر كاهش مي دهد . چون اين الگوريتم جستجوي حريصانه بدون عقب گرد[4] انجام مي دهد هيچ تضميني وجود ندارد كه كوچكترين و بهترين مجموعه قوانين كه مثالهاي آموزشي را پوشش دهند پيدا كند .
ما يك الگوريتم نياز داريم كه بتواند يك قانون را با دقت بالا ايجاد كند اما نيازي نيست كه همه مثالهاي آموزشي مثبت را پوشش دهد . در اين بخش ما يك سري از الگوريتمهاي متنوع را نشان مي دهيم و فقط يادگيري قوانين گزاره اي را در نظر گيريم وسپس اين الگوريتمها را براي يادگيري first-order Horn claus ها گسترش مي دهيم .
جدول 1 – اين الگوريتم پوشش متوالي براي يادگيري مجموعه قوانين فصلي است . “يادگيري يك قانون ” بايد يك قانون برگرداند كه بايد حداقل بعضي از مثالها را پوشش دهد . كارايي[5] يك زير رويه است كه توسط كابر ايجاد شود و كارش ارزيابي كيفيت قانون است اين الگوريتم پوشش يادگيري قوانين را تا جايي ادامه مي دهد كه كارايي آن از آستانه [6] مشخص شده پايين تر نباشد .
1.2. جستجوي شعاعي عمومي به خصوصي[7]
يك خط مشي موثر براي پياده سازي ” يادگيري يك قانون ” سازماندهي جستجوي فضاي فرضيه مانند حالت عمومي الگوريتم ID3 است . اما فقط بايد در هر مرحله شاخه اي از درخت را كه بيشترين اميد بخشي را دارد ادامه دهد .
همانطور كه در شكل يك نشان داده شده جستجو با در نظر گرفتن پيش شرط عمومي ترين قانون ممكن شروع مي شود و سپس به صورت حريصانه ويژگي هاي را كه بهترين افزايش كارايي قانون را روي مثالهاي آموزشي مي دهند اضافه كردن حريصانه دومين ويژگي . مثل ID3 اين پروسس با اضافه كردن ويژگيهاي جديد به صورت حريصانه فرضيه ها را رشد مي دهند تا وقتي كه فرضيه ها به يك سطح قابل قبول از كارايي دست پيدا كنند . در تفاوت با ID3 پياده سازي ” يادگيري يك قانون ” فقط در يك فرزند در هر مرحله از جستجو ادامه پيدا مي كند – دو تايي ويژگي مقدار بهترين كارايي را نتيجه مي دهد – به نسبت رشد يك زير درخت كه همه مقدارهاي ممكن را براي ويژگي هاي انتخاب شده پوشش مي دهد .
اين خط مشي ” يادگيري يك قانون ” را پياده سازي مي كند به گونه اي كه يك جستجوي عمومي به خصوصي در فضاي قوانين ممكن انجام مي دهد براي جستجوي قانون با بيشترين دقت ولو اينكه پوشش كامل روي داده ها نداشته باشد . همانگونه كه در درخت تصميم ياد گرفتيم راههاي زيادي براي تعريف يك معيار براي انتخاب بهترين فرزند وجود دارد . با توجه به مطالب ذكر شده در مورد ID3 حال اجازه داريم كه بهترين فرزند را كسي بدانيم كه مثالهاي آموزشي را با كمترين بي نظمي[8] پوشش داده است . جستجوي عمومي به خصوصي براي الگوريتم ” يادگيري يك قانون ” پيشنهاد شده است كه يك جستجوي حريصانه اول عمق بدون عقب گرد است.
شكل-1
در هر جستجوي حريصانه اي اين يك خطر است كه يك انتخاب كه بهينه كامل نباشد انجام شود . براي كاهش اين خطر مي توان الگوريتم را به جستجوي شعاعي گسترش داد جستجويي است كه در الگوريتم آن يك ليست شامل K تا از بهترين كانديدها در هر مرحله نگهداري مي شود بجاي يك كانديد به عنوان بهترين . در هر مرحله از جستجو براي هر يك از اين K كانديد فرزند توليد مي شود و مجموعه نتايج دوباره به K عضو كه بيشترين اميد بخشي را دارند كاهش پيدا مي كند . الگوريتم جستجوي شعاعي عمومي به خصوصي بوسيله برنامه CN2 استفاده شده كه Clark & Niblett آنرا توصيف كردند .
يك ملاحظه سطحي روي الگوريتم جدول 2 به اين ترتيب است اول هر فرضيه در نظر گرفته شده در حلقه اصلي الگوريتم يك تركيب عطفي از قيدهاي ويژگي – مقدار است . هر فرضيه عطفي متناظر با يك مجموعه كانديد از پيش شرطها براي قانوني كه ياد گرفته است و توسط بي نظمي آن مثالهايي كه پوشش داده است ارزيابي شده است اين جستجو فرضيه هاي كانديد خاص را به صورت افزايشي در نظر مي گيرد تا اينكه به يك فرضيه خاص ماكسيمم كه شامل همه ويژگي هاي در دسترس است دست يابد . قانوني كه خروجي الگوريتم است در طول جستجو داراي بزرگترين كارايي بوده است . شرط بعدي براي قانون خروجي فقط در مرحله نهايي الگوريتم بعد از اينكه پيش شرط معين شده انتخاب شده است اين الگوريتم شرط بعدي قانون را براي پيش گويي مقدار از ويژگي هدف كه بين مثال هاي پوشش داده شده با پیش شرط قانون عمومي تر است ايجاد ميكند . سرانجام توجه كنيد با اينكه استفاده از جستجوی شعاعی ريسكي در جستجوی حریصانه وجود داشت را كاهش ميدهد با اين حال باز هم احتمال توليد قانوني كه بهينه ترين نباشد وجود دارد .
جدول 2 . يك راه پياده سازي ” يادگيري يك قانون ” يك جستجوي شعاعي عام به خاص است. مرز فرضيه هاي رايج با متغيير Candidate-hypotheses نشان داده شده .
2.2. تغييرات
الگوريتم پوشش متوالي بهمراه الگوريتم “يادگيري يك قانون” مجموعه از قوانين IF-THEN را يادمي گيرد كه مثالهاي آموزشي را پوشش ميدهند تغييرات زيادي روي اين خط مشي ايجاد شده است . براي مثال در بعضي موارد ممكن ، برنامه اي كه فقط مثال هاي مثبت را ياد ميگيرد وشامل يك پيش فرض است كه نمونه هايي را كه توسط هيچ قانوني پوشش داده نمي شوند به يك كلاس منفي ارجاع ميدهد مطلوب باشد .اين خط مشي ممكن است در اين حالت مطلوب باشد فرض كنيد اگر يك نفر قصد دارد مفهوم نهايي” زنان حامله اي كه احتمال دارد دوقلو داشته باشند” را ياد بگيرد در اين حالت مجموعه مثالهاي مثبت به نسبت كل داده ها كوچك است بنا براين قانون براي انسان قابل فهم تر و فشرده تر خواهد بود اگر آن فقط كلاسهاي مثالهاي مثبت را بشناسد وبا پيش فرض اينكه بقيه مثالها منفي هستند. اين خط مشي با استراتژي “negation-as-failure” از زبان PROLOG متناظر است كه هر عبارتي كه نمي توان درستي آنرا ثابت كرد به صورت پيش فرض اشتباه در نظر گرفته ميشود . الگوريتم “يادگيري يك قانون” ميتواند دست كاري شود كه يك آرگومان اضافه به عنوان ورودي براي مشخص كردن مقدار هدف از سود در نظر گرفته شود والگوريتم جستجوي شعاعي مثل قبل عمل ميكند و فقط زير رويه كارايي تغيير مكند واين رويه يك امتياز ماكزيمم به فرضيه هايي كه منحصراٌ مثالهاي منفي و يا منحصراٌ مثالهاي مثبت را پوشش ميدهند ميدهد. با يك معيار كه كسري از مثال هاي مثبت پوشش داده شده توسط فرضيه ها را ارزيابي ميكند .
تغير ديگر توسط عده اي از الگوريتم ها كه AQ ناميده ميشود ايجاد شده است .AQشبيه CN2 مجموعه اي از فضاي قوانين را ياد ميگيرد كه با هم تابع هدف را پوشش ميدهند .اما در چند مورد با الگوريتم هايي كه آمده است تفاوت دارد . اول ، الگوريتم AQبا الگوريتم پوشش متوالي متفاوت است بخاطر اينكه بطور آشكار قانون هايي كه يك مقدار هدف خاص را پوشش ميدهند پيگري مي كنند ويك مجموعه فصلي از قوانين براي هر مقدار هدف در هر نوبت ياد مي گيرد . تفاوت دوم در ياد گيري يك قانون است در حاليكه الگوريتم جستجوي شعاعي را براي هر قانون اجرا ميكند .آن يك مثال مثبت را در اين جستجو مورد تمركز قرار ميدهد و به ويژه فقط ويژگي هايي را در نظر مي گيرد كه آن مثال مثبت را ارضا ميكند و هر زمان كه آن يك قانون جديد ياد ميگيرئ يك مثال مثبت جديد از آنهايي كه هنوز پوشش داده نشده اند انتخاب ميكند و به صورت ذكر شده عمل ميكند .
3.يادگيري مجموعه قوانين : خلاصه
الگوريتم پوشش متوالي كه در بالا توصيف شد و الگوريتم درخت تصميم يكسري از متد هاي ممكن را براي يادگيري مجموعه قوانين ارائه ميدهند . در اين بخش چندين بعد كليدي در طراحي فضاي الگوريتم هاي يادگيري قوانين را در نظر مي گيريم .
اول، الگوريتم پوشش متوالي يك قانون را در يك زمان ياد مي گيرد مثالهاي آ موزشي پوشش داده شده را حذف ميكند و اين پروسس را براي مثال هاي باقيمانده تكرار مي كند . در مقابل الگوريتم هاي درخت تصميم مثل ID3 مجموعه كامل از تركيبات فصلي را در يك زمان ياد ميگيرند و بنابراين الگوريتم هايي چون ID3 را الگوريتم هاي پوشش همزمانه مي ناميم در مقابل الگوريتم هاي پوشش متوالي مثل CN2 و حال كدام بايد ترجيح داده شود ؟ تفاوت كليدي در تصميم گيري در ابتدايي ترين مرحله از جستجو رخ مي دهد در مرحله جستجو ID3 از بين ويژگي هاي موجود به وسيله مقايسه حد فاصل داده هايي كه آنها توليد كرده اند دست به انتخاب ميزند . در مقابل GN2 از بين دو تاي ها ويژگي – مقدار انتخاب مي كند به وسيله مقايسه زير مجموعه هايي از داده هايي كه آنها پوشش مي دهند . يك راه براي ديدن اين تفاوت مقايسه تعداد تفاوت انتخابهاي ايجاد شده با دو الگوريتم به منظور يا ديگري يك مجموعه مشابه از قوانين . الگوريتمهاي پوشش متوالي مثل CN2 تعداد بيشتري انتخابهاي مستقل دارند به نسبت الگوريتمهاي پوشش همزمان مثل ID3 . و جواب به اين سئوال كه كدام برتري دارد مي تواند به اين بستگي داشته باشد كه چقدر داده آموزشي در دسترس داريم. اگر داده زياد است مي توان الگوريتم پوششي متوالي را بكار برد كه تصميمات مستقل بيشتري مي گيرد و اگر داده كم باشد اشتراك گذاشتن تصميمات در مورد بيش فرضهاي قوانين متفاوت ممكن است بيشتر مؤثر باشد .
بعد دوم : در اين خط مشي هاي متنوع مسير جستجو در ” يادگيري – يك – قانون ” است . الگوريتمي كه در بالا ذكر شد يك جستجو از فرضيه هاي عام به خاص است . و الگوريتمهاي ديگري مثل Find-S از خاص به عام جستجو مي كنند . يك امتياز از جستجوهاي عام به خاص اين است كه در اينجا يك فرضيه ماكزيمم عمومي وجود دارد در حاليكه چندين فرضيه خاص در بيشتر فضاهاي فرضيه وجود دارد و نقطه شروع جستجو مشخص نيست . يم برنامه كه از روش خاص به عام استفاده مي كند GOLEAM نام دارد كه با انتخاب چندين مثال مثبت و آغاز به صورت رندوم هدايت مي شود .
بعد سوم : اين است كه آيا جستجوي ” يادگيري – يك – قانون ” يك جستجو توليد و سپس آزمايش از ميان فرضيه هاي مشروع طبق اصل نحوي است . يا مشتق شده از مثال[9] است چنانچه هر مثال آموزشي به تنهايي توليد فرضيه را محدود كند نمونه هايي از الگوريتم هاي جستجوي مشتق از مثال شامل Find-S و Candidate-Elimination الگوريتم AQ و الگوريتم Cigol كه بعداٌ بحث خواهد شد مي باشد .
يك امتياز مهم از خط مشي توليد و سپس آزمايش اين است كه هر انتخاب در اين جستجو بر پايه كارايي فرضيه ها روي تعداد زيادي مثال است . بنابراين تاثير يك مثال غلط بسيار كاهش پيدا مي كند و در مقابل الگوريتمهاي مشتق شده از مثال كه فرضيه هه را بر اساس مثالهاي آزمايشي پالايش مي كنند براحتي مي توانند با يك مثال آموزشي غلط به اشتباه بيافتند و از اينرو كمتر در مقابل خطاها در داده آموزشي قوي هستند .
بعد چهارم : اين است كه چه و چگونه قانونهايي هرس شده اند . همانطور در درخت تصميم ياد گرفتيم اين امكان براي ” يادگيري – يك – قانون ” وجود دارد كه قانونهايي را ايجاد كند كه براي داده هاي آموزشي خيلي خوب جواب مي دهند اما براي داده هاي بعد خوب نيستند . در درخت تصميم يك راه براي نشان دادن اين پي آمدها هرس كردن هر قانون بعد از يادگرفتن آن بود . بويژه ان پيش شرطهايي از قوانين مي توانند حذف شوند كه در عمل كردن روي داده هاي هرس شده بجاي داده اموزشي باعث بالا رفتن كارايي مي شوند .
بعد نهايي : تعريف خاص از كارايي قانون به منظور جستجو در ” يادگيري – يك – قانون ” است . توابع بررسي مختلفي استفاده مي شوند . بعضي از عمومي ترين توابع ارزيابي در زير امده است .
فراواني نسبي[10] :
n به تعداد مثالهايي اشاره دارد كه با قانون هماهنگ هستند و nc به تعداد از اينها كه درست دسته بندي شده اند . اين فراواني نسبي كه كارايي قانون را تقريب مي زند عبارت است از :
nc/n
با تخمين-m از دقت[11] :
اين تخمين دقت متمايل شده به سمت دقت پيش فرض كد از آن قانون مورد انتظار بوده . و اين معمولاٌ در مواردي كه داده كم است ترجيح دارد و قانون بر پايه مثالهاي كمي بايد ارزيابي شود . n وnc همان مقاديري كه در قبل ذكر شد هستند و p را احتمال اوليه كه يك مثال از بين كل داده ها آن تقسيم بندي ارجاع شده با آن قانون را خواهد داشت باشد . (اگر 12 تا از 100 مثال آن مقدار پيشبيني شده به وسيله آن قانون را داشته باشد سپس p=12 است . )سر انجام m وزن باشد يا تعداد هم ارز مثالهايي براي وزن كردن اين p اوليه
nc+mp/n+m
توجه كنيد اگر m به 0 تنظيم شود سپس تخمين m – به رابطه قبل تبديل مي شود . همانطور كه m افزايش مي يابد تعداد بيشتر از مثالها نياز دارند كه آن دقت فرض شده اوليه p را لغو كنند .
درجه بي نظمي:[12]
معياري است كه توسط زير رويه كارايي استفاده مي شود . فرض كنيد s مجموعه از مثالهايي است كه پيش شرطهاي قانون سازگار شده اند . بي نظمي يكنواختي از مقدارهاي تابع هدف را براي اين مجموعه از مثالها اندازه مي گيرد. علامت منفي براي اين است كه قوانين بهتر امتيازهاي بهتري خواهند داشت .
-Entropy(s) = Σpi log2 pi
Cتعداد مقدارهاي متمايزي است كه تابع هدف ممكن است آنها را پوشش ميدهد و pi نسبت مثالهاي sاست كم براي تابع هدف . مقدارi ام را پوشش مي دهند. معيار بي نظمي با يك آزمايش براي مفاهيم آماري در الگوريتم CN2 آزمايش شده است .
4.يادگيري قوانين اول – ترتيب[13]
در بخش قبل در مورد يادگيري قوانين گزاره اي بحث كرديم . در اين بخش ما يادگيري قوانيني شامل متغييرها را در نظر مي گيريم بويژه يادگيري تئوري هاي اول – ترتيب Horn . انگيزه هاي ما از اين كار رساتر بودن اين قوانين از قوانين گزاره اي است . يادگيري استنتاجي از قوانين يا تئوري هاي اول ترتيب اغلب به برنامهه نويسي منطقي استنتاجي[14] منسوب شده است .
1.4. قضيه اول – ترتيب Horn
ببينيم امتيازات بازنمايي اول ترتيب را به نسبت بازنمايي گزاره اي وظيفه يادگيري يك مفهوم هدف ساده را در نظر بگيريد كه Daughter(x,y) روي جفت x و y از مردم تعريف مي شود مقدار Daughter(x,y) هنگامي كه x دخترy است درست است و در غير اين صورت غلط است . فرض كنيد هر شخص در اين داده با ويژگي هاي نام مادر. پدر. زن و مرد توصيف شده است . بنابراين هر مثال آموزشي شامل توصيف دو نفر با مقداردهي آن ويژگي ها و يك مقدار از ويژگي هدف “دختر” است . براي مثال در زير يك مثال مثبت آورده شده كه نشان مي دهد Sharon دختر Bob است :
< Name1= Sharon , Mother1=Louise , Father1=Bob , Male1=False , Female1=True , Name2=Bob , Mother2=Nora , Father2=Victor, Male2= True, Female2= False >
حال اگر ما يك مجموعه از اين چنين مثالهاي آموزشي را به يك يادگيرنده قانون گزاره اي مثلCN2 يا C4.5 بدهيم نتيجه يك مجموعه از قانونهاي بسيار خاص خواهد بود از جمله :
IF (Father1=Bob)^( Name2=Bob)^( Female1=True)
THEN Daughter1,2=True
اگر چه اين درست است اما اين قانون بسيار خاص به ندرت در طبقه بندي جفت هاي مردم در آينده مفيد واقع شود اين مشكل از آنجا ناشي مي شود كه بازنمايي هاي گزاره اي يك راه عمومي براي توصيف رابطه هاي ضروري بين مقاديرويژگي ها ارائه نمي دهند .
در مقابل يك برنامه كه از باز نمايي اول – ترتيب استفاده مي كند مي تواند قانون عمومي زير را ياد بگيرد :
IF Father(y,x)^ Female(y), THEN Daughter(x,y)
جايي كه x و y متغيرهاي هستند كهمي توانند هر شخصي باشند .
قضيه هاي اول ترتيب Horn ممكن است كه همچنين به متغير هايي در پيش شرط اشاره ميكند كه در شرط بعدي آنها ظاهر نشوند . براي مثال :
IF Father(y,z)^ Mother(z,x)^ Female(y), THEN Daughter(x,y)
متغير z در اين قانون به پدرy اشاره مي كند و در شرط بعدي قانون وجود ندارد. متدهاي يادگيري ILP امكان ياد گرفتن يك سري از تابع هاي ساده بازگشتي مثل تابع اجداد كه در ابتدا ذكر شد و تابع هايي براي مرتب كردن المان هاي يك ليست و يا حذف يك المان خاص از يك ليست و الحاق دو ليست فراهم كرده است.
2.4.مجموعه اصطلاحات:
قبل از اينكه روي مجموعه قضيه هاي Horn كار كنيم اجازه دهيد تا بعضي از اصطلاحات پايه اي از منطق رسمي را معرفي كنيم . همه عبارات از ثابت ها[15] (Bob,Louise)متغيرها[16](x,y) نمادهاي گزاره اي[17](Married,Greater-Than) و نمادهاي تابعي[18](age) تشكيل ميشود.تفاوت بين توابع وگزاره ها اين است كه گزاره ها مقدار درست يا غلط بخود مي گيرند در صورتيكه توابع هر مقدار ثابتي را ممكن است به خود بگيرند . از حروف كوچك به عنوان متغيرها واز نمادهايي كه با حروف بزرگ شروع ميشوند به عنوان مقادير ثابت استفاده كرده ايم . وهمچنين از حروف كوچك براي توابع و از نمادهايي كه با حروف بزرگ شروع براي گزاره ها استفاده كرده ايم .
با استفاده از اين نمادها عبارات زير ساخته ميشود :
اصطلاح[19]:هر مقدار ثابت ،متغير ويا هر تابعي كه روي هر اصطلاح بكار بسته شده است مي باشد .
لفظ: [20]يك گزاره يا نفي آن است كه روي هر اصطلاح بكار بسته شده است .(Married (Bob),~Married(Bob))اگر يك لفظ شامل نماد نفي ~ باشد ما آنرا يك لفظ منفي ودر غير اين صورت لفظ مثبت ناميده ميشود.
بند: [21]يك بند هر تركيب فصلي از لفظ ها ميباشد در جاييكه فرض شده است همه متغير ها كميت خود را به صورت سراسري بيان كرده اند . بند Horn شامل حداكثر يك لفظ مثبت است مثل:
H ν ~L1 ν ….. ~Ln
در جاييكه Hلفظ مثبت است و~L1……~Ln لفظ هاي منفي هستند.و بدليل ايت دو تساوي ~(AΛB)=(~Aν~B),(Bν~A)=(B←A) بند Horn بالا را ميتوان به صورت زير نوشت :
H←(L1 Λ …….. Λ Ln)
كه هم ارز با قانون زير است :
IF L1Λ …….. Λ Ln, THEN H
وپيش شرط بند Horn (L1Λ ….. Λ Ln) بدنه يا مقدمه ناميده مشود و لفظ H كه شرط بعدي را تشكيل مي دهد head يا راس ناميده ميشود.اين تعاريف بصورت خلاصه در جدول 3 آمده اند.
جدول-3
5.یادگیری مجموعه قوانین اول –ترتیب:FOIL
در این بخش ما یک برنامه که FOIL نامیده میشود در نظر می گیریم که خط مشی مشابه الگوریتم های پوشش متوالی و”یادگیری-یک-قانون” بکار می گیرد. فرضیه هایی که به وسیله FOIL یادگرفته میشود مجموعه ای از قوانین اول ترتیب هستند در جاییکه هر قانون شبیه به بند Horn است با دو استثنا. اول, قانونی که به وسیله FOIL یادگرفته میشود از قانون عمومی بند Horn محدود تر است زیرا لفظ ها در این قانون مجاز نیستند که شامل نماد تابع باشند (این پیچیدگی جستجوی فضای فرضیه ها را کاهش می دهد)دوم قوانینFOIL رساتر از بند های Horn هستند زیرا لفظهایی که در بدنه این قوانین می آیند ممکن است منفی باشند .
FOIL در محدوده مسائل مختلف بکار برده شده است .برای مثال یک تعریف بازگشتی از الگوریتم Quick Sort و یادگرفتن تفاوت حالتهای مجاز وغیر مجاز از بازی شطرنج با استفاده از FOIL نشان داده شده است.
الگوریتم FOIL در جدول 4 به صورت خلاصه آمده است حلقه بیرونی یک تغیر از الگوریتم پوشش متوالی است و حلقه داخلی تغییری از الگوریتم “یادگیری-یک-قانون” است که با قوانین اول ترتیب وفق داده شده است. همچنین اینجا تفاوت های کوچکی بین FOIL و الگوریتم های قبل وجود دارد . FOIL فقط قوانینی را پیگیری میکند که پیشگویی وقتی انجام می شود که لفظ هدف درست است.در صورتی که الگوریتم های قبل هر دو نوع قانون را پیگیری میکنند. FOIL جستجوی Hill Climbing ساده را بجای جستجوی شعاعی انجام میدهد . جستجوی فضای فرضیه ها که با FOIL انجام میشود با دیدن آن سلسله مراتب بهتر فهمیده می شود هر بار تکرار حلقه بیرونی FOIL یک قانون جدید به فرضیه های فصلی Learned-rules اضافه میکند. تاثیر هر قانون جدید بر روی فرضیه های فصلی جاری با اضافه کردن یک فصل جدید تعمیم داده می شود (به منظور افزایش تعداد نمونه هایی که آن به صورت مثبت طبقه بندی می کند ). همانگونه که دیده شد در این مرحله جستجو یک جستجوی خصوصی به عمومی در فضای فرضیه هاست که با خصوصی ترین فرضیه ,ترکیب فصلی تهی شروع میشود و هنگامی که فرضیه به حد کافی عمومی شده برای پوشش همه مثال های آموزشی مثبت پایان میپذیرد. حلقه داخلی جستجوی finger-grained را برای معین کردن تعریف دقیق هر قانون جدید بکار میرود . حلقه داخلی فضای فرضیه دومی را جستجو میکند که از ترکیب عطفی لفظ ها تشکیل شده برای یافتن ترکیب عطفی که بتواند پیش شرط قانون جدید را ایجاد کند. داخل فضای فرضیه یک جستجوی Hill Climbing عام به خاص انجام میشود که با عمومی ترین پیش شرط ممکن (پیششرط تهی) آغاز و سپس با اضافه کردن لفظ ها به صورت یکی در یک زمان قانون را خاص می کند تا جایی که آن همه مثال های منفی را ممنوع کند.
جدول-4
دو تفاوت قابل توجه بین FOIL و الگوریتم های قبل به دنبال نیازی است که آن با قوانین اول ترتیب سازگار شده است این تفاوت ها عبارتند از :
1- در جستجوی عام به خاص برای یادگرفتن هر قانون جدید FOIL مراحل جزئی متفاوتی را بکار میگیرد این تفاوت از نیاز هماهنگ سازی متغیر ها در پیش شرط قانون ناشی میشود .
2- FOIL یک معیار کارایی بکار میگیرد بنام FOIL-Gain که با معیار بی نظمی متفاوت است این تفاوت از آنجا ناشی میشود که نیاز به تمایز بین الزامات متفاوت از متغیر ها ی هر قانون وجود دارد واین واقعیت که FOIL فقط قوانینی را پیگیری می کند کخ مثال های مثبت را پوشش میدهند.
در ادامه,این دو تفاوت با جزئیات بیشتردر نظر گرفته شده اند.
1.5.تولید کاندید های اختصاصی کننده در FOIL
FOIL یکسزی از لفظ ها ی جدید را تولید میکند که هر یک ممکن است به صورت انفرادی به پیش شرط اضافه گردند . دقیق تر, فرض کنید که قانون جاری به صورت زیر در نظر گرفته شود :
P(x1,x2,….xk) L1,……Ln
در جاییکه L1,……Ln لفظ هایی هستند که پیش شرط قانون جاری را تشکیل می دهند و P(x1,x2,….xk) لفظی است که Head یا راس قانون یا شرط بعدی را تشکیل می دهد.FOIL کاندید های اختصاصی کننده قانون را بوسیله در نظر گرفتن لفظ جدید Ln+1 که با یکی از فرم های زیر تطابق میکند :
- Q(V1….Vr) که Q نام هر گزاره ایست که در حال حاضر در گزاره ها وجود دارد و Vi متغیرهای جدید ویا متغیرهایی که قبلا در قانون حاضر بودند می باشد. حداقل یکی از این Vi ها در لفظ ایجاد شده باید قبلا به عنوان یک متغیر در قانون وجود داشته باشد .
- Equal(Xj,Xk) که و متغیرهایی هستند که قبلا در قانون حاضر بوده اند.
- منفی یا مکمل هر یک از حالات لفظی بالا.
یادگیری قوانینی را برای لفظ هدف Grand-daughter(x,y) در نظر بگیرید در حالیکه گزاره های دیگری که برای توصیف مثال ها آورده شده Father,Female و جستجوی عام به خاص درFOILبا عمومی ترین قانون شروع می کند
Grand-daughter(x,y)
که اعلام میکند که Grand-daughter(x,y)به ازای هر x و y درست است.برای اختصاصی کردن این قانون اولیه پروسیجر بالا لفظ های زیر را برای اضافه کردن به پیش شرط قانون تولید می کند
Equal(x,y),Female(x), Female(y),Father(x,y), Father(y,x), Father(z,x), Father(x,z), Father(y,z), Father(z,y)
ونفی هر یک از این لفظ ها .توجه کنید که z در اینجا یک متغیر جدید است ولی و قبلا در قانون جاری حضور داشتند .
حالا فرض کنید که بین لفظ های بالا FOIL به صورت حریصانه راFather(y,z)به عنوان آینده دارترین لفظ انتخاب می کند, که منجر به خاص تر شدن قانون می شود
Father(y,z) Grand-daughter(x,y)
درتولید لفظ های کاندید برای بیشتر اختصاصی شدن قانونFOILمی خواهد همه لفظ هایی را که در بالا ذکر شده در نظر بگیرد به اضافه لفظ های Equal(z,y),Female(z), Father(z,w), Father(w,z), Equal(z,x) این لفظ های جدید به این خاطر در این نقطه در نظر گرفته میشوند که متغیر z درمرحله قبل به این قانون اضافه شده بود.به همین دلیل حالا یک متغیر جدید w در نظر می گیرد .
اگرFOIL در این نقطه لفظFather(z,x) را ودر مرحله بعد لفظ Female(y) را انتخاب می کرد این کار به قانون زیر منجر می شد که فقط مثال های مثبت را پوشش می دهد و بنابراین جستجو را برای اختصاصی تر کردن قانون پایان میدهد.
Father(y,z)^ Father(z,x)^ Female(y) Grand-daughter(x,y)
در این مرحله FOIL,همه مثال های مثبت پوشش داده شده با این قانون جدید را حذف می کند.
2.5.راهنمای جستجو در FOIL
برای انتخاب آینده دار ترین لفظ از کاندیدهای تولید شده در هر مرحله FOIL,کارایی قانون را روی داده های آموزشی در نظر می گیرد. برای انجام این کار آن همه ملزومات ممکن برای هر متغیراز قانون جاری را در نظر می گیرد. برای نشان دادن این پروسس دوباره مثال Grand-daughter(x,y) را در نظر بگیرید.فرض کنید که داده آموزشی شامل مجموعه های ساده ای است که در ادامه آورده شده و و ما قرار داد می بندیم که P(x,y) را اینگونه بخوانیم.”the P of x is y”.
Grand-daughter(Victor,Sharon) Father(Sharon ,Bob) Father(Tom,Bob) Female(Sharon) Father(Bob,Victor)
برای انتخاب بهترین اختصاص دهنده برای قانون جاریFOIL راه های متمایز را در نظر می گیرد که متغیرهای قانون می توانند به مقدارهای ثابت در مثال های آموزشی مقدار دهی شوند . برای مثال در مرحله شروع هنگامی که قانون بدین صورت است :
Grand-daughter(x,y)
متغیر های x,y قانون با هیچ شرطی محدود نشده اند و بنابراین امکان مقدار گرفتن با هر ترکیبی از این 4 ثابتTom,Bob ,Victor,Sharon وجود دارد .ما از این روش نوشتن {x/Bob,y/Sharon} برای مقدار دهی متغیر ها استفاده می کنیم که یک نگاشت قابل تعویض از هر متغیر به یک مقدارثابت است وبا 4 مقدارثابتی که داریم میتوان16حالت متغیرهای این قانون رامقداردهی کرد.مقداردهی{x/ Victor,y/Sharon} با یک مثال مثبت متناظر است زیرا داده آموزشی شامل این پیام Grand-daughter(Victor,Sharon) این پیام است و 15 مقدار دهی باقیمانده ملاک منفی برای برای آن قانون تشکیل داده اند زیرا هیچ پیامی متناظر با اینها نمی توان پیدا کرد .در هر مرحله قانون برپایه مجموعه های مثبت و منفی مقدار دهی متغیرها بررسی میشود با این برتری که قانون هایی داده شده که بیشتر دارای مقدار دهی های مثبت باشند و کمتر شامل مقدار دهی های منفی باشند .هنگامی که لفظ های جدید به قانون اضافه میشود مجموعه های مقدار دهی تغیر خواهد کرد توجه کنید که اگر لفظی اضافه شده است که یک متغیر جدید معرفی می کند سپس مقدار دهی برای قانون رشد خواهد کرد مثلا اگر Father(y,z) به قانون بالا اضافه شود مقدار دهی اولیه {x/ Victor,y/Sharon} بلندتر خواهد شد{x/ Victor,y/Sharon,z/Bob}
تابع ارزیابی که بوسیله FOIL استفاده میشود اضافه کردن یک لفظ جدید را براساس مقدار پوشش دهی مثبت ومنفی قبل وبعد از اضافه کردن لفظ جدید ارزیابی میکند.
برای توجه بیشتر قانون R را در نظر بگیرید و یک لفظ کاندید Lکه ممکن است به بدنه R اضافه شده باشد . اجازه دهید R’ قانونی باشد که بوسیله اضافه کردن لفظ L به قانون R ایجاد شده است . مقدار FOIL-Gain(L,R) از اضافه کردن L به بدینR صورت تعریف می شود :
FOIL-Gain(L,R)≡t(log2 P1/(P1+n1)- log2 Po/(Po+no)) (1)
که Po تعداد مقدار دهیهای مثبت از قانون R است , no تعداد مقدار دهی های منفی از قانون R است ,1P تعداد مقدار دهیهای مثبت از قانون R’ است و n1 تعداد مقدار دهی های منفی از قانون R’ است و سر انجام t تعداد مقدار دهی های مثبت از قانون R است که بازهم بعد از اضافه کردن R به L پوشیده میشوند.تابع FOIL-Gain یک تفسیر مستقیم در واژه ها از تئوری اطلاعات دارد. مطابق تئوری اطلاعات,- log2 Po/(Po+no) مینیمم تعداد بیتهای مورد نیاز برای کد کردن طبقه بندی یک مقدار دهی مثبت دلخواه از بین مقدار دهی ها ی پوشیده شده بوسیله قانون R است و بطور مشابه , log2 P1/(P1+n1) تعداد بیتهای مورد نیاز است اگر مقدار دهی یکی از آنهایی باشد که توسط قانونR’پوشیده میشود.t فقط تعداد مقدار دهی های مثبت پوشیده شده توسط R که توسط R’هم پوشیده شده باقی می ماند. FOIL-Gain(L,R) می تواند کاهش تعداد بیت های مورد نیاز برای کد کردن طبقه بندی همه مقدار دهی های مثبت R به علت L را نشان دهد.
3.5. یادگیری مجموعه قانون باز گشتی
در بخش قبل ما احتمال ایتکه لفظ های جدید اضافه شده به بدنه قانون می تواند به گزاره هدف خودش اشاره کند (این گزاره ای که در راس قانون امده است)را نادیده گرفتیم .اگر ما اجازه دهیم که گزاره هدف در لیست ورودی گزاره ها شرکت کند سپسFOIL هنگام تولید لفظ های کاندید آنرا در نظر می گیرد این کار اجازه می دهد که قانون های باز گشتی ایجاد شود قانون هایی که از گزاره یکسان در بدنه و راسش استفاده میکند برای نمونه قانون زیر یک تعریف باز گشتی از رابطه اجداد ایجاد می کند .
IF parent (x,y) THEN Ancestor(x,y)
IF parent (x,z)^ Ancestor (z,y) THEN Ancestor(x,y)
4.5.خلاصه FOIL
بطور خلاصه FOIL الگوریتم پوششی متوالی CN2 را برای اجرا در مورد یادگیری قانون های اول-ترتیب شبیه به بند های Horn گسترش داده است برای یاد گیری هر قانون FOIL یک جستجوی عام به خاص انجام میدهد ودر هر مرحله یک لفظ جدید به پیش شرط قانون اضافه می کند . لفظ جدید ممکن است به متغیرهایی که قبلا در پیش شرط یا در شرط بعدی ذکر شده اشاره داشته باشد ویا ممکن است یک متغیر جدید معرفی کند در هر مرحله از تابع FOIL-Gain برای انتخاب بین این لفظ های جدید کاندید استفاده میکند. اگر لفظهای جدید اجازه داشته باشند به گزاره هدف اشاره کنند سپس میتواند مجموعه های بازگشتی را یاد بگیرند.
در مورد داده های آموزشی بدون خطا FOIL ممکن است اضافه کردن لفظ های جدید به آن قانون را تا وقتی که آن مثال منفی را پوشش ندهد ادامه دهد. برای برای اجرا روی داده های با خطا جستجو تا وقتی ادامه پیدا میکند که یک بالانس بین دقت , پوشش دهی و پیچیدگی ایجاد شود.
6.استقرا همانند معکوس استنتاج
بصورت عومی یادگیری ماشین شامل ساختن تئوری هایی است که داده های مشاهده شده را توضیح میدهند . داده های داده شده D و دانش زمینه B ویادگیری می تواند به عنوان تولید کننده فرضیه h توصیف شود که به همراه B,D را توضیح میدهد . برای دقیق تر شدن فرض کنید که D مثل همیشه مجموعه ای از مثال های آموزشی است که هر کدام بصورت (xi,f(xi)) بیان شده است. اینجا xi به iامین نمونه آموزشی اشاره دارد وf(xi) به مقدار هدف اشاره میکند. سپس مسئله پوشش یک فرضیه h که طبقه بندی f(xi) ها از هر نمونه آموزشی xi به صورت استنتاجی از فرضیه h ادامه پیدا میکند و سیستم توصیف xi و دانش زمینه ای B را میداند.
(.2)f(xi)—|(√<xi,f(xi)> € D)( B^h^xi)
عبارت y—|x به صورت “y به صورت استنتاجی از x نتیجه می شود” خوانده میشود ویا “x,y را موجب می شود“. عبارت .2 قید را که باید بوسیله فرضیه یاد گرفته شده h ارضا شود را توصیف می کند . برای مثال, برای هر نمونه آموزشی xi و طبقه بندی هدف f(xi) باید بصورت استنتاجی از xi,h,B نتیجه شود.
بعنوان مثال, موردی را در نظر بگیرید که مفهوم هدف یاد گرفته شده ” یک دوتایی از مردم<u,v> است که بچه v,u می باشد ” به وسیله گزاره Child<u,v> نشان داده شده است. فرض کنید ما یک مثال مثبت Child<Bob,Sharon> را داده ایم در جاییکه آن نمونه به وسیله لفظ های:
Male(Bob) , Female(Sharon), Father(Sharon, Bob) توصیف شده است.
فرض کنید ما دانش زمین Father(u,v) Parent(u,v) را داریم. می توان در این موقعیت واژه .2 را به این صورت توصیف کرد :
Xi: Male(Bob) , Female(Sharon), Father(Sharon, Bob)
f(Xi): Child<Bob,Sharon>
B: Father(u,v) Parent(u,v)
در این مورد دو تا از فرضیه های زیادی که قید f(xi)—| (B^h^xi) را ارضا میکنند وجود دارد :
h1:Child(u,v) Father(v,u)
h2: Child(u,v) Parent(v,u)
توجه کنید که لفظ هدف Child<Bob,Sharon> به وسیله h1^xi موجب شده و بدون نیاز به دانش زمینه B ایجاد شده است. در مورد فرضیه h2 موقعیت متفاوت است لفظ هدف Child<Bob,Sharon> از B^h^xi استنتاج شده است . این مثال نقش دانش زمینه ای را در توسعه مجموعه فرضیه های قابل قبول برای داده ها ی آموزشی داده شده را نشان می دهد . و همچنین نشان میدهد که چگونه یک گزاره جدید میتواند به فرضیه ها معرفی شود حتی وقتی که آن گزاره در توصیف اولیه نمونه Xi وجود ندارد .این پروسس اضافه کردن مجموعه گزاره ها بر پایه دانش زمینه ای, اغلب به عنوان constructive induction اشاره می شود .
مفهوم عبارت .2 این است که آن مسئله یادگیری را در یک چهار چوب از اثبات استنتاجی ومنطق رسمی قرار می دهد . در مورد منطق های گزاره ای و اول-ترتیب الگوریتم های قابل فهم برای استنتاج اتوماتیک وجود دارد . جالب توجه است که امکان گسترش برعکس این پروسیجرها به منظور خودکار کردن پروسس تولید استقرایی وجود دارد . این فکر که استقرا ممکن است بوسیله عکس کردن استنتاج ایجاد شود برای اولین بار بوسیله W.S.Jevons در قرن نوزدهم ظاهر شد.در ادامه این بخش ما می خواهیم این دید را مورد بررسی قرار دهیم .عمومی ترین خاصیتی که برای ما جالب خواهد بود طراحی طراحی عملگرهای الزامی معکوس کننده[22] می باشد. یک عملگر الزامی برای معکوس کردن , O(B,D) داده های آموزشی {<xi,f(xi)>}=D و دانش زمینه ای B را بعنوان ورودی می گیرد و بعنوان خروجی فرضیه h که معادله .2 را ارضا می کند تولید می کند.
O(B,D)=h such that (√<xi,f(xi)> € D)( B^h^xi)—|f(xi)
(√<xi,f(xi)> € D)( B^h^xi)—|f(xi) البته اینجا در حالت کلی فرضیه های زیادی که
را ارضا کند وجود خواهد داشت که در اینجا چندین ویژگی جذاب برای فرموله کردن وظیفه یادگیری مانند پیدا کردن فرضیه h که رابطه f(xi)—|(√<xi,f(xi)> € D)( B^h^xi)
را حل می کند وجود دارد .
- قاعده سازی تعاریف عمومی ازیادگیری راطبقه بندی می کند. مانند پیدا کردن بعضی مفاهیم عمومی که با مجموعه مثالهای آموزشی داده شده سازگارمی شود(که با مورد خاصی که دانش زمینه ای وجود ندارد تناظر دارد).
- با در نظر گرفتن دانش زمینه ای B قاعده سازی یک تعریف قوی تری را ایجاد می کند به نسبت حالتی که یک فرضیه ممکن است از سازگاری با داده حاصل شده باشد از قبل تا بحال ما همیشه فرضیه هایی را در نظر می گرفتیم که از روی داده نتیجه می شدند و منحصرا برپایه توصیف فرضیه وداده بودند و مستقل از دامنه ای که مطالعه در آن انجام می شد . در مقابل این قاعده سازی اجازه میدهد که دانش زمینه ای B در مورد دامنه خاص , قسمتی شود که بر اساس آن هماهنگ سازی فرضیه انجام میشود .
- با در نظر گرفتن دانش زمینه ای B , این قاعده سازی متدهای یادگیری که از این اطلاعات زمینه استفاده می کنند را به منظور راهنمای جستجو برای h بکار می گیرند . پروسیجر معکوس جزئیات در بخش بعد توضیح داده می شود .
7.معکوس جزئیات[23]:
یک متد عمومی برای استنتاج خودکار قانون جزئیات[24] است که بوسیله Robinson(1965) معرفی شده است. قانون جزئیات یک قانون کامل برای اثبات استنتاجی در منطق اول ترتیب است بنابراین این خواسته قابل حس است که آیا ما می توانیم قانون جزئیات را بشکل یک عملگر الزامی معکوس در آوریم . جواب بله است وعملگری که آنرا انجام می دهد . بر پایه برنامه CIGOL که بوسیله Muggelton وBuntine (1988) معرفی شده است می باشد.
راحت ترین حالت معرفی قانون جزئیات در شکل گزاره است اگر چه به سرعت به بازنمایی اول ترتیب گسترش داده شده است . اجازه دهید L را یک لفظ گزاره ای دلخواه و P,R بند های گزاره ای دلخواه باشند .قانون جزئیات به این صورت است :
که به این صورت خوانده می شود : دو بند بالای خط بند پائین خط را نتیجه می دهد .
دو پیام داده شده ~LvR , PvL است و آشکار است که یکی از Lو~L غلط است . بنابراین R یا P باید درست باشند. پس نتیجه PvR از قانون جزئیات به صورت ذاتی ارضا می شود.حالت عمومی عملگر جزئیات گزاره ای در جدول 5 توصیف شده است . دو بندC1و C2 داده شده است عملگر جزئیات اول لفظ L را شناسایی می کند در یکی از دو بندC1و C2 پیدا می کند به شرطی که~L در دیگری اتفاق افتاده باشد .سپس نتیجه ای که از فرمول بالا بدست آمد را برای مثال کاربرد عملگر جزئیات را که در سمت چپ شکل 2 نشان داده شده است در نظر بگیرید و مثالی دیگر نتیجه بکار بردن قانون جزئیات در بندهای C1=AvBvCv~B و C2=~BvEvF بند AvCv~DvEvF می باشد.
جدول-5
تبدیل عملگر جزئیات به عملگر الزامی معکوس O(C,C1) راحت است که اثبات استقرایی انجام میدهد. در حالت عمومی عملگر الزام معکوس باید از یکی از بندهای مسبب مثل C2 مشتق شود.
در حالیکه C به عنوان جواب و1 C بعنوان دیگر بند مسبب داده شده باشد. برای مثال فرض کنید جواب C=AvB وبند مسبب C1=BvD باشد. چگونه میتوان بند C2 را از
C—|C1^C2 مشتق کرد ؟ اول, طبق تعریف عملگر جزئیات هر لفظی که در بند C وجود دارد اما درC1وجود ندارد باید در C2 حاضر شود ودوم لفظی که در C1 آمده و در C نیامده است باید منفی اش درC2بیاید .در مثال ما مشخص می شود که C2باید شامل ~Dباشد و از این روC2=Av~D است.
شکل-2
نکته ای که باید مورد توجه قرار گیرد احتمال جواب دیگرچون C2=AvBv~D است که تفاوت این جواب با جواب اول این است که در اینجا C2 شامل لفظی است کهC1 نیز آنرا داراست واین واقعیت را نتیجه می دهد که معکوس جزئیات همواره قطعی نیست ودر حالت کلی ممکن است چندین بند C2 وجود داشته باشد که C1وC2 با هم C را تولید می کنند . یک راه حل برای انتخاب C2 از بین راه حل های موجود انتخاب کوتاه ترین بند است ویا راه حل دیگر این است که C2هیچ لفظ مشترکی با C1نداشته باشد اگر ما این روش را بکار ببریم حالت عمومی پروسیجر معکوس جزئیات در جدول ما آورده شده است .
جدول-6
ما می توانیم الگوریتم های یادگیری قانون را بر پایه عملگرهای الزامی معکوس مثل معکوس جزئیات بکار بگیریم . یک استراتژی بدین صورت است که از الگوریتم پوشش متوالی برای یادگیری مجموعه بند های Horn از این طریق استفاده شود. در هر مرحله از فرا خوانی الگوریتم یک مثال آموزشی <Xi,f(Xi) که هنوز پوشش داده نشده است را انتخاب می کند سپس قانون معکوس جزئیات برای تولید فرضیه های کاندید hiکه f(xi)—|B^h^xi را ارضا می کنند بکار برده می شود و B دانش زمینه به اضافه هر بند یاد گرفته شده در فرا خوانی قبلی است. این جستجو مشتق شده از مثال است زیرا هر فرضیه کاندید برای پوشش یک مثال خاص ساخته شده است البته اگر چندین فرضیه کاندید وجود دارد سپس یک استراتژی برای انتخاب بین انها لازم است که مثلا فرضیه ای که در بالاترین دقت را روی مثال های دیگر دارد انتخاب شود . برنامه CIGOL جزئیات معکوس را با این نوع از الگوریتم پوششی متوالی استفاده می کند . اگرچه CIGOL از باز نمایی اول ترتیب بجای بازنمایی گزاره ای استفاده می کند ودر زیر همساز شدن با باز نمایی اول ترتیب توصیف شده است .
1.7.جزئثیات اول ترتیب[25]
قانون جزئیات براحتی به عبارات اول ترتیب تعمیم داده میشود . در حالت گزاره ای دو بند را بعنوان ورودی دریافت می کند وبند سومی را بعنوان خروجی تولید می کند . تفاوت کلیدی با حالت گزاره ای در پروسسی است که برپایه جایگزینی یک کننده [26] است .ما یک جانشینی را هر نگاشت از یک متغیر به واژه تعریف می کنیم . برای مثال جانشینی Q={x/Bob,y/z} بیانگر این است که متغیر x با واژه Bob و متغیرy با واژه z جایگزین می شود. ما از علامت wبرای نشان دادن نتیجه بکار بردن جانشینی Qبه عباراتی مانندw استفاده میکنیم . برای مثال, اگرL لفظ Father(x,Bill)است وQ جایگزین کننده است که در بالا تعریف کردیم پس داریم :
L1Q=L2Q= Father(Bob,Bill)
ما Q را یک جایگزین یکی کننده برای دو لفظ L1,L2 میگوییم هرگاه L1Q=L2Q شود . برای مثال اگر L1=Father(x,y)L2=Father(Bill,z)و Q={x/Bill,z/y} سپس Q یک جایگزینی یکی کننده برای L1و L2است زیرا:
L1Q=L2Q= Father(Bill,y)
جزئیات در حالت گزارهای راه حلی به این صورت دارد که از بین دو بند C2,C1 لفظL در یکی و~L دردیگری یافت شود حال در جزئیات اول ترتیب به این صورت تعمیم داده می شود که لفظ L1از بند C1و لفظL2ازبند C2وجود داشته باشند.که بتوان برای آنها یک جانشین یکی کنندهQ برای L1و~L2 پیدا کرد. L1Q=~L2Q قانون جزئیات راه حل را به این صرت می سازد :
C=(C1-{L1})QU(C2-{L2})Q (3)
جمله عمومی قانون جزئیات در جدول 7 نشان داده شده است .برای مثال فرض کنید که دو بند C2,C1 به صورت زیر تعریف شده اند:
C1=White(x) Swan(x)
C2=Swan(Fred)
حال می خواهیم قانون جزئیات را روی این دو بتد بکار بندیم اما قبل از ان باید C1 را بصورت زیر بیان کنیم :
C1=White(x) v ~Swan(x)
قانون جزئیات حالا می تواند بکار رود. در مرحله اول L1وL2 را به صورت زیر پیدا می کنیم :
L1=~Swan(x) L2=Swan(Fred)
واگرL جایگزین یکی کنندهQ={x/Fred} را انتخاب کنیم داریم :
L1Q=L2Q=~Swan(Fred)
C=(C1-{L1}Q)U(C2-{L2}Q)= White(Fred)UØ= White(Fred)
جدول-7 عملگر جزئیات در حالت اول ترتیب
2.7.معکوس کردن جزئیات: برای اول ترتیب
ما می توانیم عملگر معکوس جزئیات را از دست کاری جبری معادله 3 مشتق کنیم . اول توجه کنید که جایگزین یکی کننده Q در 3 می تواند به صورت یکتا به دو فاکتور Q1 و Q2 شکسته شود .که Q1 شامل همه جانشینی ها برای متغیرهای C1 وQ2 شامل همه جانشینی ها برای متغیر های C2 است این امر امکان پذیر است چون C1 وC2 همواره با متغیرهای با نامهای متفاوت شروع می شود . با این فاکتور گیری می توان 3 را به این صورت تغییر داد :
C=(C1-{L1})Q1U(C2-{L2})Q2
حال اگر ما فرض کنیم که بند C2شامل هیچ لفظ مشترکی با C1نیستمی توان به صورت زیر 3 را بازنویسی کرد :
C_(C1-{L1})Q1=(C2-{L2})Q2
سرانجام ما این قانون که بوسیله تعریف قانون جزئیات ֿٰL2=~L1Q1Q2 تعریف می کند را داریم .
C2=(C_(C1-{L1}Q1) Q2ֿٰU~L1Q1Q2ֿٰ} (4)
معادله 4 قانون معکوس جزئیات را برای منطق اول ترتیب ارائه می دهد وهمانند حالت گزاره ای این عملگر الزامی معکوس کردن غیر قطعی است. شکل 3 یک کاربرد چند مرحله ای از این قانون معکوس جزئیات را برای یک مثال ساده نشان میدهد. در شکل ما می خواهیم قانون هایی را برای پیش گویی هدف Grand Child(y,x) یاد بگیریم و داده آموزشی D=Grand-Child(Bob,Sharon)
دانشزمینه ایB={Father(Sharon,Tom), Father(Tom,Bob)} داده شده است در شکل 3 پایین ترین مرحله از این درخت انعکاسی را در نظر بگیرید در اینجا ما نتیجه را با داده آموزشی جایگزاری می کنیم وبندFather(Sharon,Tom)ازاطلاعات زمینه را انتخاب می کنیم
شکل-3
عملگر معکوس جزئیات را بکار می بریم , ما تنها یک انتخاب برای لفظ داریم بنام .Father(Sharon,Tom)
فرض کنید ما معکوس جانشین{Sharon/x}= ֿٰQ2 { }= ֿٰQ1را انتخاب می کنیم در این مورد نتیجه بند اجتماع دو عبارت زیر می شود :
(C_(C1-{L1}Q1) Q2ֿٰ=(CQ1) Q2ֿٰ=Grand-Child(Bob,x)
و در هر یک از این مراحل ممکن است چندین خروجی وجود داشته باشد با توجه به انتخاب جانشین در مثال شکل 3 مجموعه انتخاب ها به ارضای این بند منجر شده است .
Grand-Child(y,x)← Father(x,z)^Father(z,y)
3.7. خلاصه از معکوس جزئیات
بطور خلاصه معکوس جزئیات یک روش عمومی فراهم می کند برای تولید خود کار فرضیه های h که قیدf(xi)—|( B^h^xi) را ارضا می کند این کار بوسیله معکوس کردن قانون جزئیات عمومی 3 انجام میشود با قانون جزئیات و حل کردن بند C2 شروع میشود وسپس قانون جزئیات 4 براحتی مشتق میشود.یک مجموعه از بند های اولیه داده شده ممکن است بوسیله تکرار کاربرد چندین فرضیه تولید کرده باشد .
توجه کنید که قانون جزئیات معکوس این امتیاز را دارد که فقط فرضیه هایی که f(xi)—|(B^h^xi) را تولید می کند در مقابل در مقابل جستجوی تولید وآزمایش FOIL که تعدادی فرضیه در هر مرحله جستجو تولید می کرد که در آنها فرضیه هایی وجود داشت که این قید را ارضا نمی کردند سپسFOILداده D را برای انتخاب از بین این فرضیه ها در نظر می گرفت .با این تفاوت داده شده ما انتظار داریم که جستجو برپایه معکوس جزئیات متمرکز تر وبهینه تر باشد. دلیل اینکه عملگر معکوس جزئیات برای تولید فرضیه فقط کسر کمی از داده های موجود را در نظر می گیرد در مقابل FOIL که برای انتخاب فرضیه از بین همه فرضیه ها همه داده های موجود را در نظر می گیرد تفاوت در استراتژی جستجویشان میباشد .
8.خلاصه:
نکات مهم این متن شامل :
- الگوریتم پوششی متوالی یک مجموعه فصلی از قوانین را یاد می گیرد به این صورت که اول یک قانون را به صورت دقیق یاد می گیرد و سپس مثال های مثبتی را که این قانون پوشش می دهد حذف می کند و دوباره این پروسس را روی مثال های اموزشی باقیمانده تکرار می کند. این الگوریتم حریصانه بهینه برای یادگیری مجموعه قوانین فراهم می کند ویک چاره موجود برای روش بالا به پایین الگوریتم های یادگیری درخت تصمیم مثل ID3 است که می تواند به نسبت الگوریتم های پوششی متوالی بصورت همزمان دیده شود.
- در مفهوم الگوریتم های پوششی متوالی یک سری متد ها برای یادگیری یک قانون ایجاد شده است که این متدها استراتژی جستجو را تغیر می دهد . آنها برای امتحان کردن فضای پیش شرط های قانون ممکن استفاده می شوند یک خط مشی محبوب که با مثال نشان داده شده مثل برنامه CN2 که یک جستجوی شعاعی عمومی به خصوصی استفاده می کند .تولید کردن و آزمایش کردن قوانین که بیشتر خاص هستند را تا جایی که یک قانون دقیق بهینه پیدا کند ادامه می دهد خط مشی جستجوی خصوصی به عمومی فرضیه ها از یک جستجوی مشتق شده از مثال استفاده می کند در مقابل جستجو تولید وازمایش و برای هدایت جستجو یکسری از مقیاس های آماری را برای دقت قوانین بکار می برد .
- مجموعه قوانین اول ترتیب یک بازنمایی بسیار رسا فراهم می کند . برای مثال زبان POROLG برنامه نویسی برنامه های عمومی را که از بند های Horn اول ترتیب استفاده می کند بازنمایی می کند . مسئله یاد گیری بندهایHorn اول ترتیب اغلب به برنامه نویسی منطقی استقرایی اشاره دارد.
- یک روش برای یادگیری مجموعه قوانین اول ترتیب تعمیم الگوریتم پوششی متوالی CN2 از حالت گزاره ای به بازنمایی اول ترتیب است . این روش به وسیله برنامه FOIL نشان داده شده است و می تواند را که مجموعه قوانین بازگشتی ساده را شامل می شوند یاد بگیرد.
- روش دوم برای یادگیری مجموعه ای از قوانین اول ترتیب را بر پایه این دید که استقرا عکس استنتاج است یاد می گیرد . از طرف دیگر مسئله استقرا پیدا کردن یک فرضیه h است که قید زیر را ارضا می کند :
f(xi)—|(√<xi,f(xi)> € D)( B^h^xi)
وB دانش زمینه ای است وX1…Xn توصیفات نمونه هایی از داده های آموزشی D هستند و. f(xn)..f(x1) مقدار هدف از نمونه آموزشی می باشد.
[1] Sequential covering
[2] Sub routin
[3] LEARN-ONE-RULE
[4] backtracking
[5] PERFORMANCE
[6] Threshold
[7] General to specific Beam Search
[8] Entropy
[9] Exampie-driven
[10] Relative frequency
[11] M-estimate of accuracy
[12] Entropy
[13] First-order
[14] Inductive logic programming or ILP
Constants [15]
[16] Variables
[17] Predicate symbols
[18] Function symbols
[19] term
[20] literal
[21] clause
[22] Inverse entailment oprators
[23] Inverting resolution
[24] Resolution rule
[25] First-order resolution
[26] Unifying substitution
باسلام و عرض خسته نباشید…بخش قوانین یا همون رولهای من شامل 19684رول هست…برنامه رو که اجرا می کنم اصلا اجرا نمیشه و هنگ میکنه نمیدونم مشکل از سیستم یا ورژن متلب من هست یا با توجه به تعداد قوانین فازی زیاد کلا روش دیگه ای هست که باید استفاده کنم و من ازش خبر ندارم؟میشه لطفا راهنمایی کنید
سلام
کاملا مشخص است که باید هنگ کند چون فایل فازی شما بسیار بزرگ می باشد.
روش برای ویرایش فایل فازی بدون استفاده از تولباکس فازی وجود دارد.
می توانید این روش را در بسته جامع فازی ایران متلب ببینید.