רשימת החלטה

רשימת החלטה (באנגלית: Decision list) היא דרך לייצוג פונקציות, עם שימושים בלמידה חישובית, בתכנות ובתקשורת מחשבים. ניתן לראות רשימת החלטה כגרסה של עץ החלטה בה מושרה סדר על החוקים, ועל כן אפשרית חפיפה ביניהם. לחלופין, ניתן לתאר רשימת החלטה כהיררכיה של מומחי סיווג, ובה מתקבל הסיווג של מומחה רק אם כל המומחים שקודמים לו בהיררכיה נמנעו מלסווג קלט נתון.

הגדרה

רשימת החלטה באורך $r$, היא רשימה של זוגות סדורים $(f_{1},b_{1}),(f_{2},b_{2}),...,(f_{r},b_{r})$ ובה הפונקציות $f_{1},...,f_{r}$ הן פונקציות בוליאניות מעל תחום נתון $X$, הפונקציה $f_{r}$ היא הקבוע $true$ (הערך "אמת" או 1), ו-$b_{1},...,b_{r}$ הם קבועים מתוך טווח נתון, $D$.

בהינתן הקלט $x_{1},...,x_{n}$, מחזירה רשימת החלטה את הפלט $b_{\arg \min _{1\leq i\leq r}f_{i}(x_{1},...,x_{n})=true}$, כלומר את הערך $b_{i}$ המתאים לפונקציה $f_{i}$ הראשונה שמחזירה $true$ על הקלט.

לחלופין, ניתן לראות רשימת החלטה כיצוג של שרשרת של פקודות תנאי:

if f1 then
    output b1
else if f2 then
    output b2
...
else
    output br

הפונקציות $f_{1}...f_{r}$ נקראות תנאים, הקבועים $b_{1}...b_{r}$ נקראים החלטות או פלטים, והזוגות הסדורים $(f_{i},b_{i})$ מכונים חוקים, צמתים או כללים. רשימת החלטה היא לכן קבוצה סדורה של חוקים.

שימושים

רשימות החלטה נמצאות ביסודן של מספר רב של מערכות מומחה מבוססות חוקים. הדוגמאות הנפוצות ביותר הן מערכות תקשורת מחשבים כגון נתבים וחומות אש. ברבות ממערכות אלו, קובע המשתמש את התצורה על ידי הגדרת חוקים המסודרים ברשימת החלטה. חבילות נתונים מגיעות למערכות אלו, ונתוניהם (בדרך כלל רק אלו שבכותרת שלהם) מושווים אל מול החוקים שקבע המשתמש, לפי סדר החוקים שגם אותו קבע המשתמש. תוצאת החוק הראשון שתואם לנתוני החבילה, היא הפעולה שתנקוט המערכת ביחס לחבילה, למשל, השמטת החבילה או העברתה ליעדה.

סוגים

סוגי רשימות החלטה נבדלים זה מזה בתחום של הפונקציות הבוליאניות ובטווח של הפלטים. הרשימות הפשוטות ביותר הן אלו שבהן גם תחום הפונקציות וגם טווח הפלטים הם בוליאנים.

בפרט, נחקרה רבות המחלקה k-DL ובה כל הפונקציות הבוליאניות הן מונומים עם $k$ משתנים בוליאנים לכל היותר (פסוקיות באורך עד $k$). במאמר משנת 1987 הראה רונלד ריבסט כי המחלקה k-DL מכלילה את המחלקות הבסיסיות k-CNF ו-k-DNF, וכן עצי החלטה בוליאנים בעומק עד $k$.

כמודל בלמידה חישובית

רשימות החלטה, בעיקר בוליאניות, נלמדו רבות כמודל בלמידה חישובית. במאמר הנזכר לעיל, הציג ריבסט אלגוריתם המשיג למידת PAC יעילה עבור המחלקה k-DL. גם במודל השגיאה החסומה ישנן תוצאות המראות למידה יעילה.

ראו גם

• עץ החלטה
• למידת מכונה