הצגת המקור של הדף "רשימת החלטה"

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

==הגדרה==
רשימת החלטה באורך <math>r</math>, היא רשימה של [[זוג סדור|זוגות סדורים]]  <math>(f_1, b_1), (f_2, b_2), ..., (f_r, b_r)</math> ובה הפונקציות <math>f_1, ..., f_r</math> הן [[פונקציה בוליאנית|פונקציות בוליאניות]] מעל [[תחום של פונקציה|תחום]] נתון <math>X</math>, הפונקציה <math>f_r</math> היא הקבוע <math>true</math> (הערך "אמת" או 1), ו-<math>b_1, ..., b_r</math> הם קבועים מתוך [[טווח של פונקציה|טווח]] נתון, <math>D</math>.

בהינתן הקלט <math>x_1,...,x_n</math>, מחזירה רשימת החלטה את הפלט <math>b_{\arg\min_{1\leq i \leq r}f_i(x_1, ..., x_n)=true}</math>, כלומר את הערך <math>b_i</math> המתאים לפונקציה <math>f_i</math> הראשונה שמחזירה <math>true</math> על הקלט.

לחלופין, ניתן לראות רשימת החלטה כיצוג של שרשרת של [[פקודת תנאי|פקודות תנאי]]:
{{ltr|
 '''if''' {{math|''f''<sub>1</sub>}} '''then'''
     output {{math|''b''<sub>1</sub>}}
 '''else if''' {{math|''f''<sub>2</sub>}} '''then'''
     output {{math|''b''<sub>2</sub>}}
 ...
 '''else'''
     output {{mvar|b<sub>r</sub>}}
}}

הפונקציות <math>f_1...f_r</math> נקראות '''תנאים''', הקבועים <math>b_1...b_r</math> נקראים '''החלטות''' או '''פלטים''', והזוגות הסדורים <math>(f_i, b_i)</math> מכונים '''חוקים''', '''צמתים''' או '''כללים'''. רשימת החלטה היא לכן קבוצה סדורה של חוקים.

==שימושים==
רשימות החלטה נמצאות ביסודן של מספר רב של [[מערכת מומחה|מערכות מומחה]] מבוססות חוקים.<ref>{{קישור כללי|כתובת=https://www.ibm.com/docs/en/spss-modeler/18.4.0?topic=nodes-decision-list|כותרת=IBM SPSS Modeller}}</ref> הדוגמאות הנפוצות ביותר הן מערכות תקשורת מחשבים כגון [[נתב]]ים ו[[חומת אש|חומות אש]]. ברבות ממערכות אלו, קובע המשתמש את ה[[קובץ תצורה|תצורה]] על ידי הגדרת חוקים המסודרים ברשימת החלטה.<ref>{{קישור כללי|כתובת=https://linux.die.net/man/8/iptables|כותרת=תיאור של מנגנון iptables במערכת ההפעלה Linux}}</ref><ref>{{קישור כללי|כתובת=https://docs.aws.amazon.com/vpc/latest/userguide/vpc-network-acls.html|כותרת=Control traffic to subnets using network ACLs|אתר=AWS}}</ref> [[חבילת נתונים|חבילות נתונים]] מגיעות למערכות אלו, ונתוניהם (בדרך כלל רק אלו שב[[תקורה|כותרת]] שלהם) מושווים אל מול החוקים שקבע המשתמש, לפי סדר החוקים שגם אותו קבע המשתמש. תוצאת החוק הראשון שתואם לנתוני החבילה, היא הפעולה שתנקוט המערכת ביחס לחבילה, למשל, השמטת החבילה או העברתה ליעדה.
==סוגים==
סוגי רשימות החלטה נבדלים זה מזה בתחום של הפונקציות הבוליאניות ובטווח של הפלטים. הרשימות הפשוטות ביותר הן אלו שבהן גם תחום הפונקציות וגם טווח הפלטים הם בוליאנים.

בפרט, נחקרה רבות המחלקה '''k-DL''' ובה כל הפונקציות הבוליאניות הן [[מונום|מונומים]] עם <math>k</math> משתנים בוליאנים לכל היותר ([[DNF|פסוקיות]] באורך עד <math>k</math>). במאמר משנת 1987 הראה [[רונלד ריבסט]] כי המחלקה k-DL מכלילה את המחלקות הבסיסיות k-CNF ו-k-DNF, וכן עצי החלטה בוליאנים בעומק עד <math>k</math>.<ref>{{צ-מאמר|מחבר=Ronald Rivest|שם=Learning Decision Lists|כתב עת=Machine Learning|כרך=2|שנת הוצאה=1987|עמ=229–246|קישור=https://people.csail.mit.edu/rivest/pubs/Riv87b.pdf}}</ref>
==כמודל בלמידה חישובית==
רשימות החלטה, בעיקר בוליאניות, נלמדו רבות כמודל בלמידה חישובית. במאמר הנזכר לעיל, הציג ריבסט אלגוריתם המשיג [[למידת PAC|למידת PAC יעילה]] עבור המחלקה k-DL. גם ב[[מודל השגיאה החסומה]] ישנן תוצאות המראות למידה יעילה.<ref>{{צ-מאמר|מחבר=Adam R. Klivans and Rocco A. Servedio|שם=Toward Attribute Efficient Learning of Decision Lists and Parities|כתב עת=Journal of Machine Learning Research|כרך=7|שנת הוצאה=2006|עמ=587-602|קישור=https://www.jmlr.org/papers/volume7/klivans06a/klivans06a.pdf}}</ref>

== ראו גם ==
* [[עץ החלטה]]
* [[למידת מכונה]]

== הערות שוליים ==
{{הערות שוליים|יישור=שמאל}}
[[קטגוריה:ערכים שבהם תבנית בריטניקה אינה מתאימה]]
[[קטגוריה:למידת מכונה]]
[[קטגוריה:קבלת החלטות]]