یادگیرنده استقرایی مرتبه اول
در یادگیری ماشین، یادگیرنده استقرایی مرتبه اول (FOIL) یک الگوریتم یادگیری مبتنی‌بر قاعده و قانون است.
تاریخچه ویرایش
این الگوریتم در سال ۱۹۹۰ توسط راس کوینلان[۱] توسعه یافت. این الگوریتم عبارات هورن مستقل از تابع، زیرمجموعه ای از محاسبات گزاره مرتبه اول را با توجه به مثال‌های مثبت و منفی برخی از مفاهیم و مجموعه‌ای از گزاره‌های دانش پیشینه، می‌آموزد. الگوریتم یادگیرنده استقرایی مرتبه اول بااستفاده از استقرا یک مفهوم منطقی یا یک قاعده و قانون برای مفهوم ایجاد می‌کند. قاعده ای که استقرا شده نباید شامل هیچ ثابتی باشد (رنگ (X، قرمز) تبدیل به رنگ (X,Y)، قرمز (Y)) یا نمادهای تابعی می‌شود، اما ممکن است گزاره‌های نفی را بپذیرد. مفاهیم بازگشتی همچنین قابل یادگیری هستند. مانند الگوریتم آی‌دی۳، تپه این الگوریتم با استفاده از یک استاندارد مبتنی بر نظریه اطلاعات با ایجاد قاعده ای که داده‌ها را پوشش می‌دهد، صعود می‌کند. برخلاف الگوریتم آی‌دی۳، الگوریتم یادگیرنده استقرایی مرتبه اول به جای رهیافت تقسیم و غلبه، از روش جدا کردن و غلبه کردن استفاده می‌کند و تمرکز بر ایجاد یک قاعده و قانون در یک زمان و جمع آوری نمونه‌های پوشش داده نشده برای تکرارهای بعدی الگوریتم است.
مثال ویرایش
فرض کنید وظیفه الگوریتم یادگیرنده استقرایی مرتبه اول یادگیری مفهوم پدربزرگ (X,Y) با توجه به روابط پدر (X,Y) و والد (X,Y) است. علاوه بر این، فرض کنید بدنهٔ فعلی ما شامل والد (X,Z) ← پدربزرگ (X,Y) است. این را می‌توان با الحاق بدنه با هر یک از گزاره‌های والد (X, X), والد (Y,Z), والد (U,Y) یا بسیاری دیگر توسعه داد. برای ایجاد این گزاره، الگوریتم باید هم نام گزاره را و هم مجموعه ای از متغیرها را برای گزاره انتخاب کند. مثال‌های مثبت شامل آن مقادیری از <X,Y,Z> می‌باشند به طوری که پدربزرگ(X,Y) درست و والد(X,Z) نیز درست است. مثال‌های منفی آن دسته از مثال‌هایی هستند که پدربزرگ (X,Y) درست است اما والد (X,Z) نادرست است. در تکرار بعدی این الگوریتم بعد از اینکه والد (X,Z) اضافه شد این الگوریتم تمام ترکیبات گزاره‌ها و متغیرها را به گونه ای در نظر می‌گیرد که حداقل یک متغیر در گزاره جدید در عبارات موجود وجود داشته باشد. این منجر به فضای جستجوی بسیار بزرگ می‌شود.[۲]
افزودنی‌ها ویرایش
الگوریتم آموزنده ترکیبی مرتبه اول الگوریتم یادگیرنده استقرایی مرتبه اول را به روش‌های مختلفی گسترش می‌دهد، که بر چگونگی انتخاب گزاره‌ها توسط الگوریتم آموزنده ترکیبی مرتبه اول برای آزمایش در حین گسترش یک گزاره در حال ساخت اثر می‌گذارد. اعمال محدودیت در فضای جستجو قابل قبول است. هدف اصلی این الگوریتم ترکیب روش‌های یادگیری مبتنی بر توضیح (EBL) با روش‌های تجربی الگوریتم یادگیرنده استقرایی مرتبه اول است.
محدودیت‌ها ویرایش
برخلاف الگوریتم یادگیرنده استقرایی مرتبه اول که محدودیت‌های تایپ را روی متغیرهای خود اعمال نمی‌کند، الگوریتم آموزنده ترکیبی مرتبه اول از تایپ متغیرها به عنوان روشی بهینه برای ترکیب یک شکل ساده از دانش پیشین استفاده می‌کند. به عنوان مثال، یک گزاره livesAt(X,Y) ممکن است دارای تایپ‌هایی از جنس livesAt (شخص، مکان) باشد. همچنین ممکن است نیاز به معرفی گزاره‌های اضافی باشد. اگرچه – بدون تایپ‌ها، گزاره nextDoor(X,Y) می‌تواند تعیین کند که آیا شخص X و شخص Y در همسایگی یکدیگر زندگی می‌کنند یا اینکه آیا دو مکان در مجاورت یکدیگر هستند. وقتی A و B به عنوان متغیرهای شخص تعریف می‌شوند، فضای جستجو را کاهش می‌دهند. علاوه بر این، استفاده از تایپ می‌تواند دقت قاعده و قانون حاصل را با حذف کردن گزاره‌های غیرممکن مانند livesAt(A,B) افزایش دهد تا اطلاعات غنی تری بدست آوریم. الگوریتم آموزنده ترکیبی مرتبه اول به جای پیاده‌سازی گزاره‌های بی‌اهمیتی مانند برابری(X,X) یا بین (X,X,Y)، محدودیت‌های ضمنی را بر روی متغیرها تعریف می‌کند و فضای جستجو را بیشتر کاهش می‌دهد.
قواعد عملیاتی ویرایش
قواعد عملیاتی آن دسته از قوانینی هستند که به صورت گسترده تعریف می‌شوند، یا به صورت فهرستی از چندتایی‌ها که یک گزاره برای آنها صادق است.
قواعد اولیه ویرایش
افزودن قواعد غیرعملیاتی به پایگاه دانش، اندازه فضایی را که الگوریتم آموزنده ترکیبی مرتبه اول باید جستجو کند، افزایش می‌دهد. الگوریتم به جای ارائه یک الگوریتم با مفهوم هدف (مثلاً پدربزرگ(X,Y))، مجموعه ای از قوانین غیرعملیاتی را به عنوان ورودی می‌گیرد که صحت آنها را آزمایش می‌کند و برای مفهوم آموخته شده خود، آن را عملیاتی می‌کند. یک مفهوم هدف صحیح به وضوح زمان و دقت محاسباتی را بهبود می‌بخشد، اما حتی یک مفهوم نادرست به الگوریتم، زمینه و مبنایی برای کار و بهبود دقت و زمان می‌دهد.[۳]
منابع ویرایش
- ↑ J.R. Quinlan. Learning Logical Definitions from Relations. Machine Learning, Volume 5, Number 3, 1990
- ↑ Let Var be the largest number of distinct variables for any clause in rule R, excluding the last conjunct. Let MaxP be the number of predicates with largest arity MaxA. Then an approximation of the number of nodes generated to learn R is: NodesSearched ≤ 2 * MaxP * (Var + MaxA – 1)MaxA, as shown in Pazzani and Kibler (1992).
- ↑ Michael Pazzani and Dennis Kibler. The Utility of Knowledge in Inductive Learning. Machine Learning, Volume 9, Number 1, 1992.