برنامه‌نویسی استقرایی

برنامه‌نویسی استقرایی (IP)  یک قسمت ویژه از برنامه‌نویسی اتوماتیک است، تحقیقات نوین در رابطه با هوش مصنوعی و برنامه‌نویسی، که یادگیری از نوع اعلامی (منطقی یا تابعی) و اغلب برنامه‌های بازگشتی از مشخصات ناقص، مانند ورودی/خروجی (input/output) مثال‌ها با محدودیت‌ها را نشان می‌دهد.

بسته به زبان برنامه‌نویسی مورد استفاده، چندین نوع برنامه‌نویسی استقرایی وجود دارد، برنامه‌نویسی تابعی استقرایی، که می‌توان از زبان‌های برنامه‌نویسی تابعی مانند Lisp و Haskell نام برد، برنامه‌نویسی منطقی استقرایی، که از زبان‌های برنامه‌نویسی منطقی مانند Prolog و دیگر نمایش‌های منطقی مانند منطق توصیفی. ولی از دیگر پارادایم‌های زبان‌ها (ی برنامه‌نویسی) مانند برنامه‌نویسی محدودیتی یا برنامه‌نویسی احتمالی نیز استفاده شده‌است.

 تعریف 
برنامه‌نویسی استقرایی شامل تمام رویکردهایی که مربوط به یادگیری برنامه‌ها یا الگوریتم‌ها از مشخصات ناقص است. ورودی‌های احتمالی در یک سیستم IP (inductive programming) مجموعه ای از ورودی‌های انتقال دهنده و خروجی‌های مربوط یا یک تابع ارزیابی خروجی است. توصیف رفتار مطلوب برنامه مورد نظر، ردیابی یا توالی عمل که فرایند محاسبه خروجی‌های خاص را توصیف می‌کنند، محدودیت برای برنامه در مورد کارایی زمان یا پیچیدگی ان ایجاد می‌شود، انواع مختلف دانش‌های پس زمینه مانند انواع داده‌های استاندارد، توابع از پیش تعریف شده مورد استفاده قرار می‌گیرد، طرح‌های برنامه یا قالب‌هایی که جریان داده برنامه مورد نظر را توصیف می‌کنند ابتکاری برای جستجوی راه حل یا سایر سوگیری‌ها.

خروجی یک سیستم IP یک برنامه در برخی از زبان‌های برنامه‌نویسی دلخواه شامل شرطی‌ها و ساختارهای کنترل حلقه یا بازگشتی، یا هرنوع دیگری از زبان بازنمایی تورینگ_کامل است.

در بسیاری از اپلیکیشن‌ها برنامه خروجی باید با توجه به مثال‌ها و مشخصات جزئی درست باشدو این امر منجر به در نظر گرفتن برنامه‌نویسی استقرایی به عنوان یک قسمت خاص در داخل برنامه‌نویسی اتوماتیک یا تحلیل برنامه می‌شود ، در موارد دیگر برنامه‌نویسی استقرایی به عنوان یک حوزه عمومی تر دیده می‌شود که در آن هر برنامه‌نویسی … یا … می‌تواند مورد استفاده قرار گیرد. حتی ممکن است در نمونه‌ها درجه ای از خطا داشته باشد. به‌طور کلی یادگیری ماشین، خاص تر از استخراج ساختار یا هوش مصنوعی نمادین است. یک ویژگی متمایز تعداد مثال‌ها یا مشخصات جزئی مورد نیاز است. به‌طور معمول، تکنیک‌های برنامه‌نویسی استقرایی می‌توانند تنها از چند مثال یاد بگیرند. تنوع برنامه‌نویسی استقرایی معمولاً از اپلیکیشن‌ها و زبان‌هایی که مورد استفاده قرار می‌گیرند می آید: به غیر از برنامه‌نویسی منطقی و برنامه‌نویسی تابعی، دیگر پارادایم‌های برنامه‌نویسی و زبان‌های بازنمایی در برنامه‌نویسی استقرایی مورد استفاده یا پیشنهاد قرار گرفته‌اند از جمله: برنامه‌نویسی منطقی_تابعی، برنامه‌نویسی محدود، برنامه‌نویسی احتمالی، برنامه‌نویسی منطقی قیاسی، منطق موجهات، زبان عمل، زبان‌های عامل و بسیاری دیگر از زبان‌های دستوری.

 تاریخچه 
تحقیقات در مورد تحلیل استقرای برنامه‌های تابعی بازگشتی از اوایل دهه ۱۹۷۰ آغاز شد و بر روی پایه‌های نظری مستحکم با سمینار THESIS system سامرز و کار بایرمن آورده شد. این رویکردها به دو فاز تقسیم شدند: اول این که نمونه‌های ورودی_خروجی با استفاده از مجموعه کوچکی از عملگرهای پایه به برنامه‌های غیر بازگشتی تبدیل می‌شوند. دوم، قانونمندی‌ها در ردیابی‌ها جستجو می‌شود و برای جمع آوری آنها در یک برنامه بازگشتی مورد استفاده قرار می‌گیرد.نتایج اصلی تا اواخر دهه ۱۹۸۰ توسط اسمیت مورد بررسی قرار می‌گیرد. به دلیل پیشرفت محدود با توجه به برنامه‌هایی که می‌توانستند تحلیل شوند فعالیت‌های تحقیقاتی در دهه آینده به‌طور قابل توجهی کاهش یافت.

ظهور برنامه‌نویسی منطقی دوره جدیدی را به ارمغان آورد اما در همان ابتدای دهه ۱۹۸۰ نیز جهت‌گیری‌های جدیدی دارد. خصوصاً به دلیل سیستم MIS شاپیرو که در نهایت زمینه جدید برنامه‌نویسی منطقی استقرایی را ایجاد کرد. آثار اولیه پلاتکین و نظریه «حداقل تعمیم عمومی نسبی» او تأثیر بسیار فراوانی در برنامه‌نویسی منطقی استقرایی داشت. بیشتر کار ILP به کلاس گسترده‌تری از مشکلات می‌پردازد، چرا که تمرکز نه تنها بر روی برنامه‌های منطقی_بازگشتی بلکه بر یادگیری ماشینی فرضیه‌های نمادین از نمایش‌های منطقی نیز هست. با این حال برخی نتایج تشویق کننده در یادگیری برنامه‌های بازگشتی Prolog مانند quicksort از نمونه‌های همراه با دانش پس زمینه به عنوان مثال با GOLEM وجود دارد. اما دوباره پس از موفقیت اولیه جامعه، از پیشرفت در مورد القای برنامه‌های بازگشتی با ILP ناامید شد که باعث تمرکز کمتر و کمتر بر روی برنامه‌های بازگشتی و تکیه بیشتر و بیشتر به سمت تنظیمات یادگیری ماشین با اپلیکیشن‌ها در داده کاوی رابطه ای و دانش پس زمینه ای شد.

 حوزه‌های کاربرد 
اولین کارگاه‌های آموزشی رویکرد هاو اپلیکیشن‌های برنامه‌نویسی‌استقرایی که همراه با ICML 2005 برگزار شد اپلیکیشن‌های کاربردی را شناسایی کرد که «فراگیری برنامه‌ها یا قوانین بازگشتی فراخوانده می‌شود، ابتدا در حوزه مهندسی نرم‌افزار که در ان یادگیری ساختاری، دستیاران نرم‌افزار و عوامل نرم‌افزار می‌توانند به راحتی برنامه نویسان از کارهای پیش پا افتاده، پشتیبانی برنامه‌نویسی برای کاربران نهایی، یا پشتیبانی از برنامه نویسان تازه‌کار و سیستم‌های آموزش برنامه‌نویسی کمک کنند. حوزه‌های بیشتر کاربرد عبارت اند: از یادگیری قوانین کنترل بازگشتی برای برنامه ریزی هوش مصنوعی، یادگیری مفاهیم بازگشتی در وب کاوی یا برای دگرگونی قالب‌های داده.

 منابع 



رده:پارادایم‌های برنامه‌نویسی 
رده:یادگیری ماشین
رده:برنامه‌نویسی منطقی
رده:هوش مصنوعی