برنامه‌ریزی منطقی قیاسی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به ناوبری پرش به جستجو

برنامه‌ریزی منطقی قیاسی (انگلیسی: Abductive logic programming یا به‌طور مخفف ALP)، چارچوب ارائه دانش در سطح بالا است که می‌توان از آن برای حل مشکلات ناشی از استدلال قیاسی استفاده کرد. برنامه‌ریزی منطقی نرمال با استفاده از بعضی مفروضات که به‌طور ناقص تعریف شده‌اند، اجازه گسترده شدن را به گزاره‌های قیاسی می‌دهد. حل مسئله با استخراج فرضیه‌ها در مورد گزاره‌های مورد نظر (فرضیه قیاسی) به عنوان راه‌حل مسائل ارائه می‌شود. این مسائل می‌توانند مشاهداتی باشند که باید توضیح داده شوند، یا اهدافی که باید به دست آید. این روش می‌تواند برای حل مسائل در تشخیص، برنامه‌ریزی، زبان طبیعی و یادگیری ماشین به کار رود.

علم نحو[ویرایش]

برنامه‌های منطقی قیاسی دارای سه مؤلفه هستند:

  • P یک برنامه منطقی دقیقاً مشابه برنامه‌نویسی منطقی است.
  • A مجموعه ای از نام‌های پیشین است که نام‌های محرمانه نامیده می‌شود.
  • IC مجموعه ای از فرمول‌های کلاسیک مرتبه اول است.

به‌طور معمول، برنامه منطقی P شامل هیچ شرطی نیست که در اصل (یا نتیجه‌گیری) به یک گزاره قیاسی اشاره کند.

همچنین در عمل، بسیاری از اوقات، محدودیت‌های درستی در IC اغلب به شکل انکار، یعنی عباراتی به شکل زیر محدود می‌شوند:

false:- A1,... ,An, not B1, … , not Bm

چنین محدودیتی بدان معنی است که برای همهA1، …، An درست نیست و در عین حال تمام B1، …، Bm به اشتباه است.

معنای غیررسمی و حل مسئله[ویرایش]

شروط در P مجموعه گزاره‌های قیاسی را تعریف می‌کنند و از طریق آن یک توصیف (یامدل) حوزه مسئله را ارائه می‌کنند. محدودیت انسجام در IC ویژگی‌های عمومی مسئله را مشخص می‌کند که باید در هر راه‌حل مسئله مورد بررسی قرار گیرد. مسئله، G، یک مشاهده را بیان می‌کند که باید توضیح داده شود یا هدفی را بیان می‌کند که با ترکیب مثبت و منفی (NAF) مطلوب نشان داده می‌شود. چنین مسائلی توسط محاسبه «توضیحات قیاسی» G حل می‌شود. توضیح قیاسی در مورد مسئله G مجموعه‌ای از موارد مثبت (و گاهی منفی) از گزاره‌های قیاسی است، مثلاً هنگامی که این موارد به برنامه منطقی P، مسئله G و محدودیت‌های IC اضافه می‌شوند؛ بنابراین توضیحات قیاسی، برنامه منطقی P را با افزودن تعاریف کامل یا نسبی گزاره‌های قیاسی بسط می‌دهد. به این ترتیب، توضیحات قیاسی راه‌حل مسئله را با توجه به توصیف حوزه مسئله در P و ICشکل می‌دهند. تمدید یا تکمیل توصیف مسئله ارائه شده توسط توضیحات قیاسی، اطلاعات جدیدی را فراهم می‌کند که تا کنون در راه‌حل مسئله گنجانده نشده‌است. معیارهای کیفیت برای ترجیح دادن یک راه‌حل نسبت به دیگری که اغلب از طریق محدودیت‌های درستی بیان می‌شوند، می‌تواند برای انتخاب توضیحات خاص قیاسی در مورد مسئله G اعمال شود. محاسبه درALP، استدلال معکوس برنامه‌نویسی منطقی را با نوعی کنترل ترکیب می‌کند تا نشان دهد که توضیحات قیاسی محدودیت‌های درستی رابرطرف می‌کند. در ادامه چند مثال را ارائه می‌دهیم:

مثال ۱[ویرایش]

برنامه منطق قیاسیدر با جملات زیر:

چمن مرطوب است '' 'اگر' '' باران ببارد.

چمن مرطوب است '' 'اگر' '' آب پاش روشن باشد.

خورشید می‌درخشید.

محموله‌های قیاسی در A باران ببارد و آب پاش روشن باشد هستند و تنها محدودیت یکپارچگی در IC به صورت زیر است:

دروغ می‌گوید و خورشید درخشید.

این مشاهده که چمن مرطوب است، دو توضیح بالقوه دارد، «باران می‌بارد» و «آب‌پاش روشن باشد»، که مستلزم این مشاهده بود.

مثال ۲[ویرایش]

برنامه منطقی قیاسی شامل مواد زیر را در نظر بگیرید:

X یک شهروند است اگر X در ایالات متحده آمریکا متولد شود.

X یک شهروند است اگر X در خارج از ایالات متحده آمریکا متولد شود و X یک ساکن ایالات متحده است و X طبیعی است.

X یک شهروند است اگر X در خارج از ایالات متحده آمریکا متولد شود و Y مادر X و Y یک شهروند است و X ثبت می‌شود.

مریم مادرِ جان است.

مری یک شهروند است.

همراه با پنج عبارت قیاسی، «در ایالات متحده آمریکا متولد شده‌است»، «خارج از ایالات متحده آمریکا متولد شده‌است»، «ساکن ایالات متحده آمریکا»، «طبیعی است» و «ثبت شده‌است» و محدودیت یکپارچگی به صورت زیر است:

دروغ است اگر جان ساکن ایالات متحده باشد.

هدف «جان ساکن است» دارای دو راه حل قیاسی است، یکی از آن‌ها «جان در ایالات متحده آمریکا متولد شد» دیگری این است که «جان در خارج از ایالات متحده آمریکا متولد شده‌است» و «جان ثبت شده» است. راه حل بالقوه تبدیل شدن به یک شهروند به وسیله محل اقامت و طبقهٔ قانونی، به دلیل عدم وجود محدودیت یکپارچگی، ناکام ماند.

یک مثال پیچیده از ALP به صورت زیر است:

مثال ۳[ویرایش]

برنامه منطق قیاسی زیر یک مدل ساده از متابولیسم لاکتوز باکتری E.coli را توصیف می‌کند. برنامه، P، (در اولین قاعده خود) توصیف می‌کند که E.coli می‌تواند از لاکتوز قند تغذیه کند اگر دو آنزیم پرمیز و گالاکدوسیداس را تولید کند. مانند همه آنزیم‌ها، این‌ها در صورتی ساخته می‌شوند که توسط ژن کد گذاری شده باشند. دو آنزیم پرمیز و گالاکدوسیداس با دو ژن lac(y) و lac(z) کد می‌شود. در یک خوشه از ژن‌ها به نام اپرون (lac(X)) که وقتی مقادیر (amt)گلوکز پایین و لاکتوز پایین هستندیا زمانی که هر دو در سطح متوسط قرار دارند، بیان می‌شود. اطلاعات ناقص باید در هر مسئله مشخص شود. محدودیت انسجام، IC، بیان می‌کند که مقدار هر ماده (S)تن‌ها می‌تواند یک مقدار داشته باشد.

دانش دامنه (P)

تغذیه (لاکتوز): - ایجاد (پرمیز)، ساخت (گالاکتوزیداز).

ساختن (آنزیم): - کد (ژن، آنزیم)، بیان (ژن).

بیان (lac (X)): - مقدار (گلوکز، کم)، مقدار (لاکتوز، سلام).

بیان (lac (X)): - مقدار (گلوکز، متوسط)، مقدار (لاکتوز، متوسط).

کد (lac(y) و پرمیز)

کد (lac(z) و گالاکدوسیداس)

دمای (کم): - مقدار (گلوکز، کم).

محدودیتهای یکپارچگی (IC)

نادرست: - مقدار (S, V1)، مقدار (S, V2)، V1 ≠ V2.

قیاس (A)

گزاره - قیاسی (مقدار)

هدف این مسئله عبارت است از . این مسئله به عنوان یک نظریه توضیح داده می‌شود یا به عنوان وضعیتی که باید با پیدا کردن یک برنامه به دست آید. این هدف دارای دو توضیح است:

تصمیم‌گیری که از دو طرف اتخاذ می‌شود می‌تواند به اطلاعات اضافی که در دسترس هستندبستگی داشته باشد، به عنوان مثال ممکن است مشخص شود که وقتی سطح گلوکز پایین باشد، ارگانیسم، رفتار خاصی را نشان می‌دهد. در این مدل اطلاعات اضافی این است که دمای ارگانیسم پایین است و با مشاهده حقیقت یا نادرستی این توضیح امکان‌پذیر است که به ترتیب اولین یا دومین توضیح را انتخاب کند.

معانی رسمی[ویرایش]

معناشناسی صوری مفهوم اصلی توضیح قیاسی در ALP را می‌توان به روش زیر تعریف کرد:

با توجه به یک برنامه منطق قیاسی توضیح قانع‌کننده‌ای برای یک مسئله محموعه در گزاره‌های قیاسی است به طوری که:

سازگاری (منطق ریاضی) دارد.

این تعریف انتخاب معانی پایه برنامه‌نویسی منطقی را باز می‌کند که از طریق آن ما معنی دقیق رابطه و مفهوم ثبات برنامه‌های منطقی (گسترش یافته) را می‌فهمیم. هر کدام از معانی مختلف برنامه‌نویسی منطقی مانند تکمیل، معانی پایدار یا معقول می‌تواند (و در عمل کاربردی باشد)، مفاهیم مختلف توضیحات قیاسی و اشکال مختلف الگوریتم‌های ALP را ارائه دهد. تعریف فوق یک دیدگاه خاص در مورد رسمیت دادن نقش محدودیت‌های یکپارچگی {IC} به عنوان محدودیت در راه حل‌های احتمالی ابداعیدر نظر می‌گیرد. این امر مستلزم آن است که این برنامه‌ها از طریق برنامه منطقی توسعه‌یافته با یک راه‌حل قیاسی تعمیم یابند، بنابراین در هر مدل از برنامه منطق بسط یافته، الزامات محدودیت‌ها به درستی برآورده می‌شود. در عمل، در بسیاری از موارد، این دو روش تعیین نقش محدودیت‌های تمامیت همزمان با برنامه منطق و گسترش آن همیشه یک مدل منحصر به فرد دارند. بسیاری از سیستم‌های ALP از دیدگاه تطبیقی از محدودیت‌های درستی استفاده می‌کنند، زیرا این دیدگاه می‌تواند به راحتی بدون نیاز به هر روش تخصصی اضافی برای رضایت از محدودیت‌ها به درستی اجرا شود و محدودیت‌ها را به همان روش به عنوان هدف حل کند. توجه داشته باشید که در بسیاری از موارد عملی، شرط سوم در این تعریف رسمی از یک توضیح قیاسی درALP یا به‌طور جزیی برطرف می‌شود یا در شرط دوم از طریق استفاده از محدودیت‌های یکپارچگی خاص که سازگاری را ثبت می‌کنند، وجود دارد.

پیاده‌سازی و سیستم[ویرایش]

بسیاری از پیاده‌سازی‌های ALP، مدل محاسباتی SLD را برای برنامه‌نویسی منطقی گسترش می‌دهند.ALP همچنین می‌تواند با پیوند آن با برنامه تنظیم پاسخ (ASP)، که در آن سیستم‌های ASP می‌تواند مورد استفاده قرار گیرد، اجرا شود. نمونه‌هایی از سیستم‌های رویکرد سابق عبارتند از ACLP, A-system, CIFF, SCIFF, ABDUAL و ProLogICA.

جستارهای وابسته[ویرایش]

منابع[ویرایش]

https://en.wikipedia.org/wiki/Abductive_logic_programming