فصل ۱۰: قوانین تصمیم

عنوان اصلی: Decision Rules
منبع: https://christophm.github.io/interpretable-ml-book/rules.html
نویسنده: Christoph Molnar
مترجم: مریم محمودی

یک قانون تصمیم یک عبارت ساده IF-THEN است که از یک شرط (که پیش‌شرط یا antecedent نیز نامیده می‌شود) و یک پیش‌بینی تشکیل شده است. برای مثال:

اگر امروز باران ببارد و ماه آوریل باشد (شرط)، آن‌گاه فردا هم باران خواهد بارید (پیش‌بینی).

یک قانون تصمیم واحد یا ترکیبی از چند قانون می‌توانند برای پیش‌بینی به کار روند.

قوانین تصمیم از یک ساختار کلی پیروی می‌کنند: اگر شرایطی برآورده شود، آن‌گاه پیش‌بینی خاصی انجام می‌شود. قوانین تصمیم احتمالاً تفسیرپذیرترین مدل‌های پیش‌بینی هستند: ساختار IF-THEN آن‌ها از نظر معنایی شبیه زبان طبیعی و شیوهٔ فکر کردن ماست، به شرطی که شرط از ویژگی‌های قابل‌فهم ساخته شده باشد، طول شرط کوتاه باشد (تعداد کمی زوج ویژگی=مقدار که با AND ترکیب شده‌اند) و تعداد قوانین زیاد نباشد. در برنامه‌نویسی، نوشتن قوانین IF-THEN کاملاً طبیعی است. نکتهٔ جدید در یادگیری ماشین این است که این قوانین تصمیم توسط یک الگوریتم یاد گرفته می‌شوند.

تصور کنید از یک الگوریتم برای یادگیری قوانین تصمیم به‌منظور پیش‌بینی ارزش یک خانه (low، ok یا high) استفاده می‌کنیم. یکی از قوانینی که این مدل می‌آموزد می‌تواند این باشد: اگر خانه‌ای بزرگ‌تر از ۱۰۰ متر مربع باشد و باغ داشته باشد، آن‌گاه ارزش آن بالا است. به بیان رسمی‌تر:

اگر size>100 AND garden=1 آن‌گاه value=high.

بیایید این قانون تصمیم را تجزیه کنیم:

• size>100 اولین شرط در بخش IF است.
• garden=1 دومین شرط در بخش IF است.
• این دو شرط با یک «AND» به هم متصل شده‌اند تا شرط جدیدی بسازند. هر دو باید درست باشند تا قانون اعمال شود.
• نتیجهٔ پیش‌بینی‌شده (بخش THEN) برابر value=high است.

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

سودمندی یک قانون تصمیم معمولاً با دو عدد خلاصه می‌شود: پوشش (support) و دقت (accuracy).

پوشش یا support یک قانون: درصد نمونه‌هایی که شرط یک قانون برای آن‌ها صدق می‌کند، پوشش نامیده می‌شود. برای نمونه، قانون size=big AND location=good THEN value=high را برای پیش‌بینی ارزش خانه در نظر بگیرید. فرض کنید ۱۰۰ خانه از ۱۰۰۰ خانه بزرگ و در موقعیت خوب باشند؛ در این صورت پوشش این قانون ۱۰٪ است. بخش پیش‌بینی (THEN) در محاسبهٔ پوشش اهمیتی ندارد.

دقت یا confidence یک قانون: دقت یک قانون معیاری است از اینکه قانون تا چه اندازه در پیش‌بینی کلاس درست برای نمونه‌هایی که شرط آن اعمال می‌شود، دقیق است. برای مثال: فرض کنید از ۱۰۰ خانه‌ای که قانون size=big AND location=good THEN value=high برای آن‌ها اعمال می‌شود، ۸۵ خانه value=high، ۱۴ خانه value=ok و ۱ خانه value=low دارند؛ در این صورت دقت قانون ۸۵٪ است.

معمولاً یک موازنه (trade-off) میان دقت و پوشش وجود دارد: با افزودن ویژگی‌های بیشتر به شرط، می‌توانیم به دقت بالاتری برسیم اما پوشش را از دست می‌دهیم.

برای ساختن یک طبقه‌بند خوب جهت پیش‌بینی ارزش خانه، ممکن است لازم باشد نه فقط یک قانون، بلکه شاید ۱۰ یا ۲۰ قانون یاد بگیرید. در این صورت اوضاع می‌تواند پیچیده‌تر شود و ممکن است با یکی از مشکلات زیر روبه‌رو شوید:

• قوانین می‌توانند همپوشانی داشته باشند: چه می‌شود اگر بخواهم ارزش یک خانه را پیش‌بینی کنم و دو یا چند قانون اعمال شوند و پیش‌بینی‌های متناقضی به من بدهند؟
• هیچ قانونی اعمال نمی‌شود: چه می‌شود اگر بخواهم ارزش یک خانه را پیش‌بینی کنم و هیچ‌کدام از قوانین اعمال نشوند؟

دو راهبرد اصلی برای ترکیب چندین قانون وجود دارد: فهرست‌های تصمیم (ordered، مرتب) و مجموعه‌های تصمیم (unordered، نامرتب). هر دو راهبرد راه‌حل‌های متفاوتی برای مسئلهٔ همپوشانی قوانین ارائه می‌دهند.

یک فهرست تصمیم (decision list) ترتیبی به قوانین تصمیم اضافه می‌کند. اگر شرط اولین قانون برای یک نمونه درست باشد، از پیش‌بینی اولین قانون استفاده می‌کنیم. اگر نه، به قانون بعدی می‌رویم و بررسی می‌کنیم که آیا اعمال می‌شود، و به همین ترتیب ادامه می‌دهیم. فهرست‌های تصمیم مشکل همپوشانی قوانین را با بازگرداندن تنها پیش‌بینی نخستین قانونِ منطبق در فهرست حل می‌کنند.

یک مجموعه تصمیم (decision set) شبیه دموکراسی قوانین است، با این تفاوت که برخی قوانین ممکن است قدرت رأی بیشتری داشته باشند. در یک مجموعه، قوانین یا متقابلاً منحصربه‌فرد (mutually exclusive) هستند یا راهبردی برای حل تعارض وجود دارد، مانند رأی‌گیری اکثریت که ممکن است با دقت هر قانون یا معیارهای کیفیت دیگر وزن‌دهی شود. وقتی چند قانون همزمان اعمال شوند، تفسیرپذیری می‌تواند آسیب ببیند.

هم فهرست‌های تصمیم و هم مجموعه‌های تصمیم می‌توانند از این مشکل رنج ببرند که هیچ قانونی برای یک نمونه اعمال نشود. این مشکل را می‌توان با معرفی یک قانون پیش‌فرض حل کرد. قانون پیش‌فرض، قانونی است که هنگامی که هیچ قانون دیگری اعمال نشود، به کار می‌رود. پیش‌بینی قانون پیش‌فرض معمولاً پرتکرارترین کلاس در میان نقاط داده‌ای است که توسط قوانین دیگر پوشش داده نشده‌اند. اگر یک مجموعه یا فهرست از قوانین کل فضای ویژگی را پوشش دهد، آن را جامع (exhaustive) می‌نامیم. با افزودن یک قانون پیش‌فرض، یک مجموعه یا فهرست به‌طور خودکار جامع می‌شود.

روش‌های زیادی برای یادگیری قوانین از داده وجود دارد و این کتاب فاصلهٔ زیادی تا پوشش‌دادن همهٔ آن‌ها دارد. این فصل سه مورد از آن‌ها را نشان می‌دهد. این الگوریتم‌ها به گونه‌ای انتخاب شده‌اند که طیف گسترده‌ای از ایده‌های کلی برای یادگیری قوانین را پوشش دهند، بنابراین هر سه رویکردهای بسیار متفاوتی را نمایندگی می‌کنند.

۱. OneR قوانین را از یک ویژگی واحد یاد می‌گیرد. OneR با سادگی، تفسیرپذیری و کاربردش به‌عنوان یک معیار مرجع (benchmark) شناخته می‌شود. ۲. پوشش ترتیبی (Sequential covering) یک رویهٔ کلی است که به‌صورت تکراری قوانین را یاد می‌گیرد و نقاط داده‌ای را که توسط قانون جدید پوشش داده شده‌اند، حذف می‌کند. این رویه توسط بسیاری از الگوریتم‌های یادگیری قانون استفاده می‌شود. ۳. فهرست‌های قانون بیزی (Bayesian Rule Lists) الگوهای پرتکرار از‌پیش‌استخراج‌شده را با استفاده از آمار بیزی در یک فهرست تصمیم ترکیب می‌کنند. استفاده از الگوهای از‌پیش‌استخراج‌شده رویکردی رایج در بسیاری از الگوریتم‌های یادگیری قانون است.

بیایید با ساده‌ترین رویکرد شروع کنیم: استفاده از تنها بهترین ویژگی برای یادگیری قوانین.

یادگیری قانون از یک ویژگی واحد (OneR)

الگوریتم OneR (Holte, 1993) یکی از ساده‌ترین الگوریتم‌های استخراج قانون است. از میان همهٔ ویژگی‌ها، OneR ویژگی‌ای را انتخاب می‌کند که بیشترین اطلاعات را دربارهٔ نتیجهٔ مورد نظر حمل می‌کند و از این ویژگی، قوانین تصمیم می‌سازد.

با وجود نام OneR که مخفف «یک قانون» (One Rule) است، این الگوریتم بیش از یک قانون تولید می‌کند: در واقع به ازای هر مقدار منحصربه‌فرد ویژگیِ انتخاب‌شده، یک قانون ساخته می‌شود. نام مناسب‌تر برای آن OneFeatureRule (قانونِ یک‌ویژگی) بود.

این الگوریتم ساده و سریع است:

۱. ویژگی‌های پیوسته را با انتخاب بازه‌های مناسب، گسسته کنید. ۲. برای هر ویژگی:

• یک جدول متقاطع بین مقادیر ویژگی و نتیجهٔ (دسته‌ای) بسازید.
• برای هر مقدار ویژگی، قانونی بسازید که رایج‌ترین کلاس نمونه‌هایی را که آن مقدار ویژگی خاص را دارند پیش‌بینی کند (این کلاس را می‌توان از جدول متقاطع خواند).
• خطای کل قوانینِ آن ویژگی را محاسبه کنید. ۳. ویژگی‌ای را که کمترین خطای کل را دارد، انتخاب کنید.

OneR همیشه تمام نمونه‌های مجموعه داده را پوشش می‌دهد، زیرا از تمام سطوح ویژگی انتخاب‌شده استفاده می‌کند. مقادیر گم‌شده را می‌توان یا به‌عنوان یک مقدار ویژگی اضافی در نظر گرفت یا از پیش جایگزین (impute) کرد.

یک مدل OneR در واقع یک درخت تصمیم با تنها یک تقسیم است. این تقسیم لزوماً دودویی (binary) نیست، برخلاف CART، بلکه به تعداد مقادیر منحصربه‌فرد ویژگی بستگی دارد.

نکته: OneR معیار مرجع خوبی برای مقایسه با مدل‌های پیچیده‌تر است.

بیایید مثالی را ببینیم که در آن بهترین ویژگی توسط OneR انتخاب می‌شود. جدول ۱۰.۱ یک مجموعه دادهٔ مصنوعی دربارهٔ خانه‌ها را با اطلاعاتی دربارهٔ ارزش، موقعیت، اندازه، و اینکه آیا نگهداری حیوان خانگی مجاز است یا نه نشان می‌دهد. ما به یادگیری یک مدل ساده برای پیش‌بینی ارزش خانه علاقه‌مندیم.

جدول ۱۰.۱: مجموعه دادهٔ مصنوعی برای ارزش خانه.

OneR قوانین را بر اساس جداول متقاطع بین هر ویژگی و نتیجه می‌سازد. جدول ۱۰.۲ سه جدول متقاطع را نشان می‌دهد.

جدول ۱۰.۲: جداول متقاطع بین هر ویژگی و هدف.

برای هر ویژگی، سطر به سطر جدول را بررسی می‌کنیم: هر مقدار ویژگی، بخش IF یک قانون است؛ رایج‌ترین کلاس برای نمونه‌های دارای آن مقدار ویژگی، پیش‌بینی (بخش THEN) آن قانون است. برای مثال، ویژگی اندازه با سطوح کوچک، متوسط و بزرگ سه قانون تولید می‌کند. برای هر ویژگی، نرخ خطای کل قوانین تولیدشده را که مجموع خطاهاست، محاسبه می‌کنیم. ویژگی موقعیت مقادیر ممکن بد و خوب را دارد. رایج‌ترین مقدار برای خانه‌های در موقعیت بد پایین است و وقتی از پایین به‌عنوان پیش‌بینی استفاده کنیم، دو اشتباه می‌کنیم چون دو خانه ارزش متوسط دارند. مقدار پیش‌بینی‌شده برای خانه‌های در موقعیت خوب بالا است، و باز هم دو اشتباه می‌کنیم چون دو خانه ارزش متوسط دارند. خطایی که با ویژگی موقعیت مرتکب می‌شویم برابر ۴/۱۰ است، برای ویژگی اندازه ۳/۱۰ و برای ویژگی حیوان خانگی ۴/۱۰. ویژگی اندازه قوانینی با کمترین خطا تولید می‌کند و برای مدل نهایی OneR استفاده خواهد شد:

اگر size=small آن‌گاه value=low اگر size=medium آن‌گاه value=ok اگر size=big آن‌گاه value=high

برای درک بهتر (توضیح مترجم): به زبان ساده، OneR فقط یک سؤال می‌پرسد و بر اساس پاسخ آن تصمیم می‌گیرد. در مثال بالا آن سؤال «اندازهٔ خانه چقدر است؟» است، چون در مقایسه با «موقعیت» و «حیوان خانگی»، پاسخ به همین یک سؤال کمترین تعداد اشتباه (۳ اشتباه از ۱۰ خانه) را ایجاد می‌کند؛ بنابراین OneR این ویژگی را بر دو ویژگی دیگر ترجیح می‌دهد، حتی اگر ترکیب چند ویژگی با هم می‌توانست دقت بالاتری بدهد.

اگر اعتبارسنجی درستی صورت نگیرد، OneR ممکن است روی ویژگی‌هایی با سطوح زیاد بیش‌برازش (overfit) کند. مجموعه داده‌ای را تصور کنید که فقط نویز دارد و هیچ سیگنالی در آن نیست، به این معنا که تمام ویژگی‌ها مقادیر تصادفی می‌گیرند و هیچ ارزش پیش‌بینی‌کننده‌ای برای هدف ندارند. برخی ویژگی‌ها سطوح بیشتری نسبت به بقیه دارند. ویژگی‌هایی که سطوح بیشتری دارند حالا راحت‌تر می‌توانند بیش‌برازش کنند. ویژگی‌ای که برای هر نمونه از داده یک سطح جداگانه دارد، می‌تواند کل مجموعه دادهٔ آموزشی را به‌طور کامل پیش‌بینی کند. یک راه‌حل این است که داده را به مجموعه‌های آموزش و اعتبارسنجی تقسیم کنیم، قوانین را روی داده آموزشی یاد بگیریم و خطای کل را برای انتخاب ویژگی روی مجموعهٔ اعتبارسنجی ارزیابی کنیم.

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

مسئلهٔ دیگر، تساوی (ties) است، یعنی زمانی که دو ویژگی خطای کل یکسانی داشته باشند. OneR این تساوی‌ها را یا با انتخاب اولین ویژگی با کمترین خطا یا ویژگی‌ای که کمترین p-value را در یک آزمون کای‌دو (chi-squared) دارد، حل می‌کند.

مثال

بیایید OneR را روی داده‌های واقعی امتحان کنیم. از داده‌های پنگوئن‌های پالمر برای آزمایش الگوریتم OneR استفاده می‌کنیم. تمام ویژگی‌های پیوسته ورودی به ۵ کوانتیل گسسته شدند. قوانین ساخته‌شده توسط الگوریتم یادگیری OneR در جدول ۱۰.۳ نشان داده شده‌اند.

جدول ۱۰.۳: قانون یادگرفته‌شده توسط OneR برای طبقه‌بندی جنسیت پنگوئن.

ویژگی bill_depth_mm (عمق منقار) توسط OneR به‌عنوان بهترین ویژگی پیش‌بینی‌کننده انتخاب شد. برای درک بهتر عملکرد این تک‌قانون، بیایید نگاهی به جدول متقاطع بین ویژگی گسسته‌شدهٔ bill_depth_mm و گونهٔ پنگوئن بیندازیم؛ به جدول ۱۰.۴ مراجعه کنید.

جدول ۱۰.۴: ماتریس درهم‌ریختگی برای قانون طبقه‌بندی جنسیت پنگوئن که توسط OneR یافت شده است.

می‌بینیم که این ویژگی به‌ویژه برای طبقه‌بندی پنگوئن‌هایی با منقار عمیق مفید است. پنگوئن‌هایی با عمق منقار بیش از ۱.۹۸ سانتی‌متر به احتمال زیاد نر هستند. منقارهای بسیار کم‌عمق احتمال زیادی می‌دهند که با یک پنگوئن ماده سروکار داریم. نکتهٔ احتیاط: این مدل گونه (species) را نادیده می‌گیرد، یا بهتر بگوییم همهٔ گونه‌ها را با هم قاطی می‌کند. برای رفع این مشکل، می‌توانستیم یک مدل جداگانه برای هر گونه آموزش دهیم.

OneR ذاتاً از وظایف رگرسیون پشتیبانی نمی‌کند. اما می‌توانیم یک وظیفهٔ رگرسیون را با بریدن (cutting) خروجی پیوسته به بازه‌ها، به یک وظیفهٔ دسته‌بندی تبدیل کنیم. از این ترفند برای پیش‌بینی تعداد دوچرخه‌های اجاره‌شده با OneR استفاده می‌کنیم، با بریدن تعداد دوچرخه‌ها به چهار چارک آن (۰ تا ۲۵٪، ۲۵ تا ۵۰٪، ۵۰ تا ۷۵٪ و ۷۵ تا ۱۰۰٪). جدول ۱۰.۵ ویژگی انتخاب‌شده پس از برازش مدل OneR را نشان می‌دهد: ویژگی انتخاب‌شده تعداد کرایهٔ دوچرخهٔ روز قبل است.

جدول ۱۰.۵: قانون طبقه‌بندی OneR برای داده‌های کرایهٔ دوچرخه.

اکنون از الگوریتم سادهٔ OneR به سمت رویه‌ای پیچیده‌تر حرکت می‌کنیم که از قوانین با شرط‌های پیچیده‌تر متشکل از چند ویژگی استفاده می‌کند: پوشش ترتیبی (Sequential Covering).

پوشش ترتیبی (Sequential Covering)

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

ایده ساده است: نخست، قانون خوبی پیدا کنید که برای برخی از نقاط داده اعمال می‌شود. تمام نقاط داده‌ای را که توسط این قانون پوشش داده شده‌اند حذف کنید. یک نقطهٔ داده زمانی پوشش‌داده‌شده است که شرط‌ها برای آن اعمال شوند، فارغ از اینکه آن نقطه به‌درستی طبقه‌بندی شده باشد یا نه. یادگیری قانون و حذف نقاط پوشش‌داده‌شده را با نقاط باقی‌مانده تکرار کنید تا نقطه‌ای باقی نماند یا شرط توقف دیگری برآورده شود. نتیجه یک فهرست تصمیم است. به این رویکردِ یادگیری مکرر قانون و حذف نقاط پوشش‌داده‌شده، «جداسازی و تسخیر» (separate-and-conquer) گفته می‌شود.

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

• با یک فهرست خالی از قوانین (rlist) شروع کنید.
• یک قانون $r$ یاد بگیرید.
• تا زمانی که فهرست قوانین زیر یک آستانهٔ کیفیت مشخص باشد (یا نمونه‌های مثبت هنوز پوشش داده نشده باشند):
  • قانون $r$ را به rlist اضافه کنید.
  • تمام نقاط داده‌ای را که توسط قانون $r$ پوشش داده شده‌اند حذف کنید.
  • روی داده‌های باقی‌مانده، قانون دیگری یاد بگیرید.
• فهرست تصمیم را برگردانید.

شکل ۱۰.۱: مراحل الگوریتم پوشش ترتیبی. در گام نخست، یک قانون که بخشی از داده را به‌خوبی پوشش می‌دهد پیدا می‌شود (مربع مشکی رسم‌شده دور نمونه‌ها). در گام دوم، تمام نمونه‌های درون آن ناحیه از داده حذف می‌شوند. در گام سوم، الگوریتم روی داده‌های باقی‌مانده به دنبال قانون بعدی می‌گردد.

برای نمونه: وظیفه و مجموعه داده‌ای برای پیش‌بینی ارزش خانه‌ها بر اساس اندازه، موقعیت، و اینکه آیا نگهداری حیوان خانگی مجاز است یا نه داریم. اولین قانونی که یاد می‌گیریم این است: اگر size=big و location=good، آن‌گاه value=high. سپس تمام خانه‌های بزرگ در موقعیت خوب را از مجموعه داده حذف می‌کنیم. با داده‌های باقی‌مانده، قانون بعدی را یاد می‌گیریم؛ شاید: اگر location=good، آن‌گاه value=ok. توجه کنید که این قانون روی داده‌ای یاد گرفته می‌شود که دیگر خانه‌های بزرگ در موقعیت خوب را ندارد، و فقط خانه‌های متوسط و کوچک در موقعیت خوب باقی مانده‌اند.

برای مسائل چندکلاسه، رویکرد باید تغییر کند. نخست، کلاس‌ها بر اساس فراوانیِ فزاینده مرتب می‌شوند. الگوریتم پوشش ترتیبی با کم‌تکرارترین کلاس شروع می‌کند، برای آن یک قانون یاد می‌گیرد، تمام نمونه‌های پوشش‌داده‌شده را حذف می‌کند، سپس به سراغ دومین کلاس کم‌تکرار می‌رود، و به همین ترتیب ادامه می‌دهد. کلاس جاری همیشه به‌عنوان کلاس مثبت در نظر گرفته می‌شود و تمام کلاس‌های با فراوانی بالاتر در کلاس منفی ترکیب می‌شوند. آخرین کلاس همان قانون پیش‌فرض است. به این رویکرد در دسته‌بندی، راهبرد یک-در-برابر-همه (one-versus-all) نیز گفته می‌شود.

چگونه یک قانون واحد یاد می‌گیریم؟ الگوریتم OneR در اینجا کارساز نیست، چون همیشه کل فضای ویژگی را پوشش می‌دهد. اما راه‌های دیگر زیادی وجود دارد. یک امکان، یادگیری یک قانون واحد از یک درخت تصمیم با جست‌وجوی پرتوی (beam search) است:

• یک درخت تصمیم (با CART یا الگوریتم دیگری برای یادگیری درخت) یاد بگیرید.
• از گره ریشه شروع کنید و به‌طور بازگشتی خالص‌ترین گره را انتخاب کنید (مثلاً گره‌ای با کمترین نرخ طبقه‌بندی نادرست).
• کلاس اکثریت گرهٔ پایانی به‌عنوان پیش‌بینی قانون و مسیر منتهی به آن گره به‌عنوان شرط قانون استفاده می‌شود.

شکل ۱۰.۲: قانونی که با جست‌وجوی یک مسیر در یک درخت تصمیم یاد گرفته شده است. نتیجه این می‌شود: اگر location=good و size=big، آن‌گاه value=high.

یادگیری یک قانون واحد یک مسئلهٔ جست‌وجو است، که در آن فضای جست‌وجو، فضای همهٔ قوانین ممکن است. هدف جست‌وجو، یافتن بهترین قانون بر اساس معیاری مشخص است. راهبردهای جست‌وجوی متفاوت زیادی وجود دارد: کوه‌نوردی (hill-climbing)، جست‌وجوی پرتوی (beam search)، جست‌وجوی جامع (exhaustive search)، جست‌وجوی بهترین-اول (best-first search)، جست‌وجوی مرتب (ordered search)، جست‌وجوی تصادفی (stochastic search)، جست‌وجوی بالا-به-پایین (top-down)، جست‌وجوی پایین-به-بالا (bottom-up) و غیره.

RIPPER (Repeated Incremental Pruning to Produce Error Reduction، Cohen, 1995) یکی از انواع الگوریتم پوشش ترتیبی است. RIPPER کمی پیچیده‌تر است و از یک مرحلهٔ پس‌پردازش (هرس قوانین) برای بهینه‌سازی فهرست (یا مجموعهٔ) تصمیم استفاده می‌کند. RIPPER می‌تواند در حالت مرتب یا نامرتب اجرا شود و فهرست تصمیم یا مجموعهٔ تصمیم تولید کند.

مثال‌ها

نخست، قوانین را برای وظیفهٔ طبقه‌بندی جنسیت پنگوئن استخراج می‌کنیم. قوانین به‌همراه قانون پیش‌فرض در جدول ۱۰.۶ چاپ شده‌اند. تفسیر آن ساده است: برای پیش‌بینی یک نمونهٔ جدید، از بالای فهرست شروع کنید و بررسی کنید آیا یک قانون اعمال می‌شود. اگر شرط‌ها برقرار باشند، گونه‌ای که در سمت راست قانون آمده را پیش‌بینی کنید. اگر برقرار نباشند، به قانون بعدی بروید تا به یک طبقه‌بندی برسید. قانون پیش‌فرض تضمین می‌کند که همیشه یک پیش‌بینی وجود داشته باشد.

جدول ۱۰.۶: قوانین یادگرفته‌شده توسط JRip برای وظیفهٔ طبقه‌بندی پنگوئن.

RIPPER راهی مشخص برای حل تعارض میان قوانین دارد: قوانین را به‌ترتیب اعمال می‌کند. این تنها یکی از راهبردهای کلی ممکن است؛ راهبردهای دیگر از استفاده از قانونی با اختصاصی‌ترین بخش IF تا استفاده از قانونی با بالاترین دقت (precision) را نیز شامل می‌شوند.

وقتی RIPPER را برای پیش‌بینی تعداد کرایهٔ دوچرخه روی یک وظیفهٔ رگرسیون به کار می‌بریم، چند قانون یافت می‌شود. از آنجا که RIPPER فقط برای دسته‌بندی کار می‌کند، تعداد دوچرخه‌ها باید به یک نتیجهٔ دسته‌ای تبدیل شود؛ این کار با بریدن تعداد دوچرخه‌ها به چارک‌ها انجام شده است. برای مثال، بازهٔ $[4548, 5956]$ تعداد پیش‌بینی‌شدهٔ دوچرخه‌ها را بین ۴۵۴۸ و ۵۹۵۶ پوشش می‌دهد. جدول ۱۰.۷ فهرست تصمیمِ قوانین یادگرفته‌شده را نشان می‌دهد. تفسیر باز هم همان است: اگر شرط‌ها برقرار باشند، بازهٔ سمت راست را برای تعداد دوچرخه‌ها پیش‌بینی می‌کنیم. من از قوانین تصمیم این مثال چندان راضی نیستم. ماهیت ویژگی cnt_2d_bfr تعدیل روند کلی کرایهٔ دوچرخه است. cnt و cnt_2d_bfr رابطه‌ای خطی دارند که قوانین تصمیم به‌سختی می‌توانند آن را بازتاب دهند.

جدول ۱۰.۷: قوانین JRip برای وظیفهٔ کرایهٔ دوچرخه.

فهرست‌های قانون بیزی (Bayesian Rule Lists)

در این بخش، رویکرد دیگری برای یادگیری یک فهرست تصمیم نشان داده می‌شود که این دستورالعمل کلی را دنبال می‌کند:

۱. الگوهای پرتکرار را از داده از پیش استخراج کنید تا به‌عنوان شرط قوانین تصمیم استفاده شوند. ۲. یک فهرست تصمیم را از میان زیرمجموعه‌ای از قوانین از‌پیش‌استخراج‌شده یاد بگیرید.

رویکرد مشخصی که این دستورالعمل را دنبال می‌کند، فهرست‌های قانون بیزی (Letham et al., 2015) یا به‌اختصار BRL نامیده می‌شود. BRL از آمار بیزی برای یادگیری فهرست‌های تصمیم از الگوهای پرتکراری استفاده می‌کند که با الگوریتم FP-tree (Borgelt, 2005) از‌پیش استخراج شده‌اند.

اما بیایید آرام‌آرام با گام اول BRL شروع کنیم.

پیش‌استخراج الگوهای پرتکرار

یک الگوی پرتکرار (frequent pattern) هم‌رخدادی مکرر مقادیر ویژگی است. به‌عنوان یک مرحلهٔ پیش‌پردازش برای الگوریتم BRL، از ویژگی‌ها (در این مرحله به نتیجهٔ هدف نیازی نیست) استفاده می‌کنیم و الگوهای پرتکرار را از آن‌ها استخراج می‌کنیم. یک الگو می‌تواند یک مقدار ویژگی واحد مانند size=medium یا ترکیبی از مقادیر ویژگی مانند size=medium AND location=bad باشد.

فراوانی یک الگو با پوشش (support) آن در مجموعه داده اندازه‌گیری می‌شود:

$$Support(\mathbf{x}_j=A)=\frac{1}{n}\sum_{i=1}^nI(x^{(i)}_{j}=A)$$

که در آن $A$ مقدار ویژگی، $n$ تعداد نقاط داده در مجموعه داده، و $I$ تابع نشانگر (indicator function) است که اگر ویژگی $x_j$ نمونهٔ $i$ سطح $A$ داشته باشد ۱ و در غیر این صورت ۰ برمی‌گرداند. در مجموعه‌داده‌ای از ارزش خانه‌ها، اگر ۲۰٪ خانه‌ها بالکن نداشته باشند و ۸۰٪ یک یا چند بالکن داشته باشند، پوشش الگوی balcony=0 برابر ۲۰٪ خواهد بود. پوشش را می‌توان برای ترکیب مقادیر ویژگی نیز اندازه گرفت، برای مثال برای balcony=0 AND pets=allowed.

الگوریتم‌های زیادی برای یافتن چنین الگوهای پرتکراری وجود دارند، برای مثال Apriori یا FP-Growth. اینکه کدام‌یک را استفاده کنید چندان اهمیتی ندارد؛ تنها سرعت یافتن الگوها متفاوت است، اما الگوهای به‌دست‌آمده همیشه یکسان‌اند.

اجازه دهید ایدهٔ کلی‌ای از نحوهٔ کار الگوریتم Apriori در یافتن الگوهای پرتکرار ارائه دهم. در واقع، الگوریتم Apriori از دو بخش تشکیل شده است، که بخش نخست الگوهای پرتکرار را می‌یابد و بخش دوم از آن‌ها قوانین انجمنی (association rules) می‌سازد. برای الگوریتم BRL، ما فقط به الگوهای پرتکراری که در بخش نخست Apriori تولید می‌شوند علاقه‌مندیم.

در گام نخست، الگوریتم Apriori با تمام مقادیر ویژگی‌ای شروع می‌کند که پوششی بزرگ‌تر از حداقل پوشش تعیین‌شده توسط کاربر دارند. اگر کاربر بگوید حداقل پوشش باید ۱۰٪ باشد و تنها ۵٪ خانه‌ها size=big داشته باشند، آن مقدار ویژگی را حذف می‌کنیم و فقط size=medium و size=small را به‌عنوان الگو نگه می‌داریم. این به این معنا نیست که خانه‌ها از داده حذف می‌شوند؛ فقط یعنی size=big به‌عنوان یک الگوی پرتکرار بازگردانده نمی‌شود. بر اساس الگوهای پرتکرار با یک مقدار ویژگی واحد، الگوریتم Apriori به‌طور تکراری تلاش می‌کند ترکیب‌هایی از مقادیر ویژگی با مرتبهٔ فزاینده پیدا کند. الگوها با ترکیب عبارت‌های ویژگی=مقدار با عملگر منطقی AND ساخته می‌شوند، مثلاً size=medium AND location=bad. الگوهای تولیدشده‌ای که پوششی کمتر از حداقل پوشش داشته باشند حذف می‌شوند. در پایان، تمام الگوهای پرتکرار را در اختیار داریم.

هر زیرمجموعه‌ای از شرط‌های یک الگوی پرتکرار نیز پرتکرار است، که به آن ویژگی Apriori گفته می‌شود. این موضوع شهوداً منطقی است: با حذف یک شرط از یک الگو، الگوی کاسته‌شده تنها می‌تواند تعداد نقاط دادهٔ بیشتر یا برابر را پوشش دهد، نه کمتر. برای مثال، اگر ۲۰٪ خانه‌ها size=medium AND location=good باشند، آن‌گاه پوشش خانه‌هایی که فقط size=medium هستند ۲۰٪ یا بیشتر خواهد بود. از ویژگی Apriori برای کاهش تعداد الگوهایی که باید بررسی شوند استفاده می‌شود: فقط در صورتی که یک الگو پرتکرار باشد، نیاز داریم الگوهای مرتبهٔ بالاتر را بررسی کنیم.

اکنون گام پیش‌استخراج شرط‌ها برای الگوریتم فهرست‌های قانون بیزی به پایان رسیده است. اما پیش از رفتن به گام دوم BRL، مایلم به راه دیگری برای یادگیری قانون بر پایهٔ الگوهای از‌پیش‌استخراج‌شده اشاره کنم. رویکردهای دیگر پیشنهاد می‌کنند نتیجهٔ موردعلاقه نیز در فرآیند استخراج الگوی پرتکرار گنجانده شود و بخش دوم الگوریتم Apriori، که قوانین IF-THEN می‌سازد، نیز اجرا شود. از آنجا که این الگوریتم بدون‌نظارت (unsupervised) است، بخش THEN نیز شامل مقادیر ویژگی‌ای می‌شود که به آن‌ها علاقه‌ای نداریم. اما می‌توانیم قوانینی را فیلتر کنیم که فقط نتیجهٔ موردعلاقه در بخش THEN آن‌ها باشد. این قوانین از پیش یک مجموعهٔ تصمیم را تشکیل می‌دهند، اما امکان مرتب‌کردن، هرس، حذف یا ترکیب دوبارهٔ آن‌ها هم وجود دارد.

با این حال، در رویکرد BRL، ما با الگوهای پرتکرار کار می‌کنیم و بخش THEN و چگونگی چیدن الگوها در یک فهرست تصمیم را با استفاده از آمار بیزی یاد می‌گیریم.

یادگیری فهرست‌های قانون بیزی

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

توزیع احتمال پسینِ فهرست‌ها این امکان را می‌دهد که بگوییم یک فهرست تصمیم مشخص، با توجه به فرضیات کوتاهی و میزان برازش آن با داده، چقدر محتمل است. هدف ما یافتن فهرستی است که این احتمال پسین را بیشینه کند. از آنجا که یافتن مستقیمِ دقیقِ بهترین فهرست از توزیع فهرست‌ها ممکن نیست، BRL دستورالعمل زیر را پیشنهاد می‌کند:

۱. یک فهرست تصمیم اولیه تولید کنید که به‌طور تصادفی از توزیع پیشین کشیده شده است. ۲. فهرست را به‌طور تکراری با افزودن، جابه‌جایی یا حذف قوانین تغییر دهید، به‌گونه‌ای که فهرست‌های حاصل از توزیع پسینِ فهرست‌ها پیروی کنند. ۳. از میان فهرست‌های نمونه‌برداری‌شده، فهرستی را با بیشترین احتمال بر اساس توزیع پسین انتخاب کنید.

بیایید الگوریتم را از نزدیک‌تر بررسی کنیم: الگوریتم با پیش‌استخراج الگوهای مقدار ویژگی با الگوریتم FP-Growth شروع می‌شود. BRL چند فرض دربارهٔ توزیع هدف و توزیع پارامترهایی که توزیع هدف را تعریف می‌کنند در نظر می‌گیرد (این همان آمار بیزی است). اگر با آمار بیزی آشنا نیستید، لازم نیست خیلی درگیر جزئیات زیر شوید؛ نکتهٔ مهم این است که بدانید رویکرد بیزی راهی است برای ترکیب دانش یا نیازهای موجود (به‌اصطلاح توزیع‌های پیشین) همراه با برازش به داده. در مورد فهرست‌های تصمیم، رویکرد بیزی منطقی است، چون فرضیات پیشین، فهرست‌های تصمیم را به سمت کوتاه‌بودن و داشتن قوانین کوتاه سوق می‌دهند.

هدف، نمونه‌برداری از فهرست‌های تصمیم $d$ از توزیع پسین زیر است:

$$p(d \mid \mathbf{x}, \mathbf{y}, A, \alpha, \lambda, \eta) \propto p(\mathbf{y} \mid \mathbf{x}, d, \alpha) \cdot p(d \mid A, \lambda, \eta)$$

که در آن $d$ یک فهرست تصمیم، $\mathbf{x}$ ویژگی‌ها، $\mathbf{y}$ هدف، $A$ مجموعهٔ شرط‌های از‌پیش‌استخراج‌شده، $\lambda$ طول انتظاری پیشین فهرست‌های تصمیم، $\eta$ تعداد انتظاری پیشین شرط‌ها در هر قانون، و $\alpha$ شبه‌شمار پیشین (prior pseudo-count) برای کلاس‌های مثبت و منفی است که بهتر است روی $(1,1)$ ثابت شود.

$$p(d \mid \mathbf{x}, \mathbf{y}, A, \alpha, \lambda, \eta)$$

نشان می‌دهد که با توجه به داده‌های مشاهده‌شده و فرضیات پیشین، یک فهرست تصمیم چقدر محتمل است. این عبارت متناسب است با درستنمایی نتیجهٔ $Y$ با توجه به فهرست تصمیم و داده، ضربدر احتمال آن فهرست با توجه به فرضیات پیشین و شرط‌های از‌پیش‌استخراج‌شده.

$$p(\mathbf{y} \mid \mathbf{x}, d, \alpha)$$

درستنمایی $y$ مشاهده‌شده با توجه به فهرست تصمیم و داده است. BRL فرض می‌کند $y$ توسط یک توزیع Dirichlet-Multinomial تولید شده است. هرچه فهرست تصمیم $d$ داده را بهتر توضیح دهد، این درستنمایی بزرگ‌تر است.

$$p(d \mid A, \lambda, \eta)$$

توزیع پیشین فهرست‌های تصمیم است. این توزیع، به‌صورت ضربی، یک توزیع پواسون بریده‌شده (پارامتر $\lambda$) برای تعداد قوانین در فهرست و یک توزیع پواسون بریده‌شده (پارامتر $\eta$) برای تعداد مقادیر ویژگی در شرط‌های قوانین را ترکیب می‌کند.

اگر یک فهرست تصمیم هم نتیجهٔ $y$ را خوب توضیح دهد و هم با توجه به فرضیات پیشین محتمل باشد، احتمال پسین بالایی خواهد داشت.

برآوردها در آمار بیزی همیشه کمی دشوارند، چون معمولاً نمی‌توانیم مستقیماً پاسخ درست را محاسبه کنیم، بلکه باید کاندیداها را نمونه‌برداری کنیم، آن‌ها را ارزیابی کنیم و برآوردهای پسینِ خود را با روش زنجیرهٔ مارکوف مونت‌کارلو به‌روزرسانی کنیم. برای فهرست‌های تصمیم، این کار حتی دشوارتر است، چون باید از توزیع فهرست‌های تصمیم نمونه‌برداری کنیم. نویسندگان BRL پیشنهاد می‌کنند ابتدا یک فهرست تصمیم اولیه بکشیم و سپس آن را به‌طور تکراری تغییر دهیم تا نمونه‌هایی از فهرست‌های تصمیم را از توزیع پسینِ فهرست‌ها (یک زنجیرهٔ مارکوف از فهرست‌های تصمیم) تولید کنیم. نتایج به‌طور بالقوه به فهرست تصمیم اولیه وابسته‌اند، بنابراین توصیه می‌شود این رویه تکرار شود تا تنوع خوبی از فهرست‌ها تضمین شود. مقدار پیش‌فرض در پیاده‌سازی نرم‌افزار، ۱۰ بار است. دستورالعمل زیر نحوهٔ ساخت یک فهرست تصمیم اولیه را نشان می‌دهد:

• الگوها با استفاده از FP-Growth از‌پیش استخراج می‌شوند.
• پارامتر طول فهرست $m$ از یک توزیع پواسون بریده‌شده نمونه‌برداری می‌شود.
• برای قانون پیش‌فرض: پارامتر توزیع Dirichlet-Multinomial مقدار هدف ($\theta_0$) نمونه‌برداری می‌شود (یعنی قانونی که وقتی هیچ قانون دیگری اعمال نشود به کار می‌رود).
• برای قانون $j=1,\ldots,m$ در فهرست تصمیم:
  • پارامتر طول قانون $l$ (تعداد شرط‌ها) برای قانون $j$ نمونه‌برداری می‌شود.
  • یک شرط با طول $l_j$ از میان شرط‌های از‌پیش‌استخراج‌شده نمونه‌برداری می‌شود.
  • پارامتر توزیع Dirichlet-Multinomial برای بخش THEN (یعنی برای توزیع نتیجهٔ هدف با توجه به قانون) نمونه‌برداری می‌شود.
• برای هر مشاهده در مجموعه داده:
  • قانونی از فهرست تصمیم که نخست اعمال می‌شود (از بالا به پایین) پیدا می‌شود.
  • نتیجهٔ پیش‌بینی‌شده از توزیع احتمال (دوجمله‌ای) پیشنهادشده توسط قانونِ اعمال‌شده کشیده می‌شود.

گام بعدی، تولید فهرست‌های جدید زیاد با شروع از این نمونهٔ اولیه است تا نمونه‌های زیادی از توزیع پسینِ فهرست‌های تصمیم به دست آید.

فهرست‌های تصمیم جدید با شروع از فهرست اولیه و سپس با جابه‌جاییِ تصادفی یک قانون به موقعیت دیگری در فهرست، یا افزودن یک قانون از میان شرط‌های از‌پیش‌استخراج‌شده به فهرست تصمیم جاری، یا حذف یک قانون از فهرست تصمیم، نمونه‌برداری می‌شوند. اینکه کدام قانون جابه‌جا، اضافه یا حذف شود، به‌طور تصادفی انتخاب می‌شود. در هر گام، الگوریتم احتمال پسینِ فهرست تصمیم (ترکیبی از دقت و کوتاهی) را ارزیابی می‌کند. الگوریتم متروپلیس-هستینگز (Metropolis Hastings) تضمین می‌کند که فهرست‌های تصمیمی نمونه‌برداری شوند که احتمال پسین بالایی دارند. این رویه، نمونه‌های زیادی از توزیع فهرست‌های تصمیم در اختیار ما می‌گذارد. الگوریتم BRL از میان این نمونه‌ها، فهرست تصمیمی را با بیشترین احتمال پسین انتخاب می‌کند.

مثال‌ها

بحث نظری به پایان رسید؛ حالا بیایید روش BRL را در عمل ببینیم. مثال‌ها از نسخهٔ سریع‌تر BRL به نام Scalable Bayesian Rule Lists (SBRL؛ Yang, Rudin, and Seltzer, 2017) استفاده می‌کنند. از الگوریتم SBRL برای پیش‌بینی گونهٔ پنگوئن‌ها استفاده می‌کنیم. برای اینکه الگوریتم SBRL کار کند، لازم بود همهٔ ویژگی‌های ورودی را گسسته کنم. این کار را با دسته‌بندی ویژگی‌های پیوسته بر اساس فراوانی مقادیر با کوانتیل‌ها انجام دادم. قوانین نمایش‌داده‌شده در جدول ۱۰.۸ به‌دست می‌آیند.

جدول ۱۰.۸: قوانین مدل SBRL.

شرط‌ها از میان الگوهایی انتخاب شدند که با الگوریتم FP-Growth از‌پیش استخراج شده بودند. جدول زیر بخشی از انبار شرط‌هایی را نشان می‌دهد که الگوریتم SBRL می‌توانست از میان آن‌ها برای ساخت فهرست تصمیم انتخاب کند. حداکثر تعداد مقادیر ویژگی مجاز در یک شرط، که به‌عنوان کاربر تعیین کردم، دو بود. جدول ۱۰.۹ نمونه‌ای از ده الگو را نشان می‌دهد.

جدول ۱۰.۹: نمونه‌ای از شرط‌های از‌پیش‌استخراج‌شده برای وظیفهٔ طبقه‌بندی پنگوئن.

تُنُکی (sparsity) پادشاه است: قوانین کمتر و کوتاه‌تر، تفسیر مدل را بهتر می‌کنند. اما یک موازنه (trade-off) با پیچیدگی و در نتیجه با عملکرد پیش‌بینی وجود دارد.

توضیح مترجم: بخش فهرست‌های قانون بیزی چند فرمول دارد که ممکن است در نگاه اول پیچیده به نظر برسند؛ اما ایدهٔ پشت همهٔ آن‌ها یک قاعدهٔ ساده و بسیار معروف در آمار به نام قاعدهٔ بیز (Bayes' theorem) است:

$$\underbrace{p(\text{فرضیه} \mid \text{داده})}_{\text{پسین (posterior)}} ;\propto; \underbrace{p(\text{داده} \mid \text{فرضیه})}_{\text{درست‌نمایی (likelihood)}} \times \underbrace{p(\text{فرضیه})}_{\text{پیشین (prior)}}$$

به زبان ساده: باور نهایی ما دربارهٔ یک «فرضیه» (اینجا: یک فهرست تصمیم خاص) از ترکیب دو چیز به دست می‌آید — باور اولیهٔ ما پیش از دیدن داده («پیشین»، مثلاً اینکه فهرست‌های کوتاه‌تر را ترجیح می‌دهیم) و اینکه آن فرضیه چقدر خوب با داده‌های واقعی جور در می‌آید («درست‌نمایی»). هرچه یک فهرست هم کوتاه‌تر باشد و هم داده را بهتر توضیح دهد، احتمال پسین آن بالاتر می‌رود. تصویر زیر همین رابطهٔ بین پیشین، درست‌نمایی و پسین را به‌صورت هندسی نشان می‌دهد: ناحیهٔ اشتراکِ «فرضیه» و «داده» (که همان پسین است) از ضرب سهم هر کدام به دست می‌آید.

شکل ۱۰.۳: نمایش هندسی قاعدهٔ بیز. مربع کل، همهٔ حالت‌های ممکن را نشان می‌دهد؛ نوار آبی سهم «فرضیه» (اینجا معادل پیشین $p(d\mid A,\lambda,\eta)$)، نوار زرد سهم «داده» (معادل درست‌نمایی $p(\mathbf{y}\mid\mathbf{x},d,\alpha)$)، و ناحیهٔ سبز اشتراک آن دو (معادل پسین $p(d\mid\mathbf{x},\mathbf{y},A,\alpha,\lambda,\eta)$) است. منبع: Wikimedia Commons (کمیل کولاسینسکی، دامنهٔ عمومی).

مثال مترجم برای درک بهتر خوانندگان: فرض کنید در مثال ارزش خانه، از الگوریتم FP-Growth دو الگوی پرتکرار به‌دست آمده: size=big با پوشش (Support) ۰.۳ (یعنی طبق فرمول $Support(\mathbf{x}_j=A)=\frac{1}{n}\sum_{i=1}^nI(x^{(i)}_j=A)$، از هر ۱۰ خانه، ۳ تای آن‌ها بزرگ هستند) و location=good AND size=big با پوشش ۰.۲. فرض کنید BRL می‌خواهد بین دو فهرست تصمیمِ کاندیدا یکی را انتخاب کند:

• فهرست A (کوتاه، یک قانون): اگر size=big آن‌گاه value=high؛ در غیر این صورت value=ok. این فهرست ۹۰٪ نمونه‌ها را درست پیش‌بینی می‌کند.
• فهرست B (طولانی، پنج قانون با شرط‌های ترکیبی): همان دقت ۹۰٪ را دارد، اما با پنج قانون و شرط‌های تا سه‌تایی.

طبق فرمول پسین، $p(\mathbf{y}\mid\mathbf{x},d,\alpha)$ (درست‌نمایی) برای هر دو فهرست تقریباً یکسان است، چون هر دو ۹۰٪ داده را درست توضیح می‌دهند. اما $p(d\mid A,\lambda,\eta)$ (پیشین) برای فهرست A بسیار بزرگ‌تر است، چون توزیع پواسون بریده‌شدهٔ روی طول فهرست ($\lambda$) و طول شرط‌ها ($\eta$) به فهرست‌های کوتاه‌تر احتمال بیشتری می‌دهد. در نتیجه، حاصل‌ضرب درست‌نمایی در پیشین — یعنی احتمال پسین — برای فهرست A بزرگ‌تر خواهد بود و BRL آن را ترجیح می‌دهد؛ دقیقاً همان چیزی که در جعبهٔ «تُنُکی پادشاه است» بالا گفته شد.

مزایا

این بخش دربارهٔ مزایای کلیِ قوانین IF-THEN بحث می‌کند.

قوانین IF-THEN به‌راحتی تفسیر می‌شوند. آن‌ها احتمالاً تفسیرپذیرترین مدل‌های تفسیرپذیر هستند. این ادعا فقط زمانی صادق است که تعداد قوانین کم باشد، شرط‌های قوانین کوتاه باشند (حداکثر ۳ شرط، به نظر من)، و قوانین در یک فهرست تصمیم یا یک مجموعهٔ تصمیمِ بدون همپوشانی سازمان‌دهی شده باشند.

قوانین تصمیم می‌توانند به همان اندازهٔ درخت‌های تصمیم بیانگر باشند، در حالی که فشرده‌تر هستند. درخت‌های تصمیم اغلب از زیردرخت‌های تکراری رنج می‌برند، یعنی وقتی تقسیم‌های یک گره‌فرزندِ چپ و یک گره‌فرزندِ راست ساختار یکسانی دارند.

پیش‌بینی با قوانین IF-THEN سریع است، چون فقط باید چند عبارت باینری بررسی شوند تا مشخص شود کدام قوانین اعمال می‌شوند.

قوانین تصمیم در برابر تبدیل‌های تک‌نوای (monotonic transformations) ویژگی‌های ورودی مقاوم هستند، چون فقط آستانهٔ داخل شرط‌ها تغییر می‌کند. همچنین در برابر داده‌های پرت مقاوم‌اند، چون تنها اهمیت دارد که یک شرط اعمال می‌شود یا نه.

قوانین IF-THEN معمولاً مدل‌های تُنُک (sparse) تولید می‌کنند، به این معنا که ویژگی‌های زیادی در آن‌ها گنجانده نمی‌شود. این قوانین تنها ویژگی‌های مرتبط را برای مدل انتخاب می‌کنند. برای مثال، یک مدل خطی به‌طور پیش‌فرض به هر ویژگی ورودی یک وزن اختصاص می‌دهد؛ اما ویژگی‌های نامرتبط را می‌توان به‌سادگی توسط قوانین IF-THEN نادیده گرفت.

قوانین ساده، مانند قوانین OneR، می‌توانند به‌عنوان معیار مرجع (baseline) برای الگوریتم‌های پیچیده‌تر استفاده شوند.

محدودیت‌ها

این بخش به کاستی‌های کلیِ قوانین IF-THEN می‌پردازد.

تحقیقات و ادبیات مربوط به قوانین IF-THEN بر دسته‌بندی متمرکز است و رگرسیون را تقریباً به‌طور کامل نادیده می‌گیرد. اگرچه همیشه می‌توان یک هدف پیوسته را به بازه‌ها تقسیم کرد و آن را به یک مسئلهٔ دسته‌بندی تبدیل کرد، همیشه بخشی از اطلاعات از دست می‌رود. به‌طور کلی، رویکردهایی که هم برای رگرسیون و هم برای دسته‌بندی قابل استفاده باشند، جذاب‌ترند.

اغلب اوقات، ویژگی‌ها نیز باید دسته‌ای باشند. یعنی ویژگی‌های عددی باید دسته‌بندی شوند اگر بخواهید از آن‌ها استفاده کنید. راه‌های زیادی برای بریدن یک ویژگی پیوسته به بازه‌ها وجود دارد، اما این کار بی‌اهمیت نیست و سؤالات زیادی بدون پاسخ روشن به همراه دارد. ویژگی به چند بازه تقسیم شود؟ معیار تقسیم چیست: طول ثابت بازه‌ها، کوانتیل‌ها یا چیز دیگری؟ دسته‌بندی ویژگی‌های پیوسته موضوعی بی‌اهمیت نیست که اغلب نادیده گرفته می‌شود، و افراد فقط از نزدیک‌ترین روش در دسترس استفاده می‌کنند (همان‌طور که من در مثال‌ها انجام دادم).

بسیاری از الگوریتم‌های قدیمی‌تر یادگیری قانون مستعد بیش‌برازش هستند. الگوریتم‌های ارائه‌شده در اینجا همگی دست‌کم چند محافظ در برابر بیش‌برازش دارند: OneR محدود است چون فقط می‌تواند از یک ویژگی استفاده کند (فقط زمانی مشکل‌ساز است که آن ویژگی سطوح بسیار زیادی داشته باشد یا ویژگی‌های زیادی وجود داشته باشند، که معادل مسئلهٔ آزمون چندگانه است)، RIPPER هرس انجام می‌دهد، و فهرست‌های قانون بیزی یک توزیع پیشین بر فهرست‌های تصمیم اعمال می‌کنند.

قوانین تصمیم، مانند درخت‌های تصمیم، در توصیف روابط خطی میان ویژگی‌ها و خروجی ضعیف عمل می‌کنند. این مشکلی است که با درخت‌های تصمیم مشترک است. درخت‌ها و قوانین تصمیم فقط می‌توانند توابع پیش‌بینیِ پله‌ای تولید کنند، که در آن‌ها تغییرات پیش‌بینی همیشه جهش‌های گسسته هستند و هرگز منحنی‌های صاف نیستند. این موضوع با این مسئله مرتبط است که ورودی‌ها باید دسته‌ای باشند؛ در درخت‌های تصمیم، این کار به‌طور ضمنی از طریق تقسیم‌کردن ویژگی‌ها انجام می‌شود.

نرم‌افزار و جایگزین‌ها

OneR در بستهٔ R به نام OneR پیاده‌سازی شده است، که برای مثال‌های این کتاب استفاده شد. OneR همچنین در کتابخانهٔ یادگیری ماشین Weka پیاده‌سازی شده و به همین دلیل در Java، R و Python در دسترس است.

RIPPER نیز در Weka پیاده‌سازی شده است. برای مثال‌ها، از پیاده‌سازی R مربوط به JRIP در بستهٔ RWeka استفاده کردم.

SBRL به‌صورت یک بستهٔ R (که برای مثال‌ها استفاده کردم)، در Python، یا به‌صورت یک پیاده‌سازی C در دسترس است.

علاوه بر این، توصیه می‌کنم بستهٔ imodels را نیز بررسی کنید که مدل‌های مبتنی بر قانون مانند فهرست‌های قانون بیزی، CORELS، OneR، فهرست‌های قانون حریصانه و موارد دیگر را در قالب یک بستهٔ Python با رابط یکپارچهٔ سازگار با scikit-learn پیاده‌سازی می‌کند.

تلاش نمی‌کنم همهٔ جایگزین‌های یادگیری مجموعه‌ها و فهرست‌های قانون تصمیم را فهرست کنم، اما به چند کار جامع اشاره می‌کنم. کتاب Foundations of Rule Learning نوشتهٔ Fürnkranz، Gamberger و Lavrač (۲۰۱۲) را توصیه می‌کنم. این کتابی مفصل دربارهٔ یادگیری قوانین است، برای کسانی که می‌خواهند عمیق‌تر به این موضوع بپردازند. این کتاب چارچوبی جامع برای اندیشیدن دربارهٔ یادگیری قوانین ارائه می‌دهد و بسیاری از الگوریتم‌های یادگیری قانون را معرفی می‌کند. همچنین بررسی یادگیرنده‌های قانون Weka را توصیه می‌کنم که RIPPER، M5Rules، OneR، PART و بسیاری دیگر را پیاده‌سازی می‌کنند.

قوانین IF-THEN را می‌توان در مدل‌های خطی نیز به کار برد، همان‌طور که در فصل مربوط به الگوریتم برازش قانون در این کتاب توضیح داده شده است.