ياگيري قوانين فازي rule learning

 

يكي از رساترين و خواناترين باز نماييها براي يادگيري قضيه‌ها مجموعه قوانين 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

 

لينك دريافت اصل فايل

پیام بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

+ eighty one = eighty three