סיכום קורס: מבוא לבינה מלאכותית

1.1 מהי בינה מלאכותית? (4 הגישות)

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

1.2 דיסציפלינות תורמות והישגים בולטים

• 8 הדיסציפלינות שתרמו ל-AI: פילוסופיה (לוגיקה ורציונליות), מתמטיקה (חישוביות, לוגיקה והסתברות), כלכלה (תורת התועלת, תורת המשחקים ו-MDP), חקר העצבים (רשתות נוירונים), פסיכולוגיה (מדעי הקוגניציה), הנדסת מחשבים (חומרה), תורת הבקרה וקיברנטיקה, ובלשנות (ייצוג ידע ודקדוק).
• אבני דרך והישגים היסטוריים במדריך הלמידה: תוכנת Remote Agent של נאס"א שניהלה את החללית Deep Space 1; מחשב השחמט Deep Blue של IBM שניצח את גארי קספרוב (1997); רכבים אוטונומיים (ALVINN / DARPA); מערכות דיאגנוסטיקה רפואית ברשתות הסתברותיות; רובוט הניתוחים HipNav; מערכת התכנון הלוגיסטי DART במלחמת המפרץ (שהחזירה את כל השקעת משרד ההגנה האמריקאי ב-AI ב-30 שנה); סינון ספאם בלמידה מדוגמאות; Watson של IBM שניצח ב-Jeopardy (2010); והעוזרת האישית Siri (פרויקט CALO).

1.3 תחומי מחקר ותיאוריית הבר-למידה (Valiant)

2.1 סוכנים, סביבות ופונקציית הסוכן

• סוכן (Agent): כל ישות הבוחנת את סביבתה באמצעות חיישנים (Sensors) ופועלת עליה באמצעות אמצעי פעולה (Actuators). $$\text{Agent} = \text{Architecture (חומרה/פלטפורמה)} + \text{Program (תכנית)}$$
• תחושה (Percept) מול היסטוריית תחושות (Percept Sequence): תחושה היא קלט החיישנים ברגע נתון; היסטוריית התחושות היא הסדרה המלאה של כל מה שהסוכן קלט מאז תחילת פעולתו.
• פונקציית הסוכן מול תכנית הסוכן: פונקציית הסוכן היא תיאור מתמטי מופשט הממפה כל סדרת תחושות לפעולה ($f: P^* \to A$). תכנית הסוכן היא המימוש הקונקרטי שרץ על הארכיטקטורה.
  מדוע לא לממש סוכן כטבלת חיפוש (Lookup Table)? אם $P$ היא קבוצת התחושות האפשריות ו-$T$ אורך חיי הסוכן, גודל הטבלה הוא $\sum_{k=1}^T |P|^k$ — גודל אקספוננציאלי בלתי אפשרי בזיכרון!

2.2 רציונליות, ידיעת-כל ואוטונומיות

• רציונליות $\neq$ ידיעת-כל (Omniscience): סוכן יודע-כל יודע מראש את התוצאה הוודאית של פעולותיו (בלתי אפשרי במציאות). סוכן רציונלי ממקסם את תוחלת הביצועים לפי המידע שברשותו.
• איסוף מידע (Information Gathering) ולמידה: פעולות שנועדו לשפר תצפיות עתידיות (כמו להסתכל ימינה ושמאלה לפני חציית כביש) הן חלק הכרחי מהתנהגות רציונלית.
• אוטונומיות (Autonomy): סוכן המסתמך רק על הידע המוקדם של מתכננו ומתעלם מתחושותיו חסר אוטונומיות. סוכן אוטונומי לומד מניסיונו כדי לפצות על ידע מוקדם חלקי או שגוי.

2.3 מודל PEAS ו-7 תכונות סביבת העבודה

הצעד הראשון בתכנון סוכן הוא הגדרת סביבת המשימה באמצעות ראשי התיבות PEAS (דוגמת נהג מונית אוטונומי):

2.4 ארכיטקטורות סוכנים ו-3 רמות ייצוג מצבים

3.1 ניסוח בעיות, הפשטה ודוגמאות

בסביבה נראית במלואה, בדידה, ידועה ודטרמיניסטית, פתרון לכל בעיה הוא סדרה קבועה של פעולות. הסוכן פועל בשלושה שלבים: נסח (Formulate) $\to$ חפש (Search) $\to$ בצע (Execute).

• הפשטה (Abstraction): הסרת פרטים לא רלוונטיים מייצוג המצבים והפעולות. הפשטה היא תקפה (Valid) אם ניתן להרחיב כל פתרון מופשט לפתרון בעולם המפורט, והיא מועילה (Useful) אם ביצוע כל פעולה מופשטת קל יותר מפתרון הבעיה המקורית.
• חשיבות ניסוח הבעיה (דוגמת 8 המלכות): בניסוח נאיבי (הצבת 8 מלכות בכל משבצת בלוח) יש $\approx 1.8 \times 10^{14}$ מצבים. בניסוח חכם (הצבת מלכה בעמודה השמאלית הריקה ביותר כך שאינה מאוימת ע"י הקודמות) מרחב המצבים צונח ל-2,057 מצבים בלבד!

3.2 עץ חיפוש מול גרף ו-4 מדדי הערכה

• חיפוש-עץ (`TREE-SEARCH`) מול חיפוש-גרף (`GRAPH-SEARCH`): בחיפוש-עץ שומרים רק את קבוצת העלים הפתוחים לפיתוח הנקראת החזית (`OPEN` / `frontier`). בחיפוש-גרף מוסיפים רשימה סגורה (`CLOSE` / `explored set`) (ממומשת כטבלת גיבוב ב-$O(1)$) הזוכרת כל מצב שכבר פותח כדי למנוע לולאות אינסופיות ועבודה כפולה.
• 4 תכונות להערכת אלגוריתם חיפוש: (1) שלמות (האם מובטח שימצא פתרון כשקיים כזה?), (2) אופטימליות (האם מובטח שימצא את הפתרון הזול ביותר?), (3) סיבוכיות זמן (מספר הצמתים שנוצרים), (4) סיבוכיות מקום/זיכרון (מקסימום צמתים בזיכרון בו-זמנית).
  הפרמטרים: $b$ = מקדם הסתעפות מקסימלי, $d$ = עומק המטרה הרדודה ביותר, $m$ = אורך המסלול המקסימלי במרחב המצבים.

3.3 אסטרטגיות חיפוש חסרות ידע (עיוורות - Uninformed Search)

3.4 חיפוש מיודע (Informed Search): Greedy ו-A*

חיפוש מיודע משתמש בידע ספציפי על הבעיה באמצעות פונקציה יוריסטית $h(n)$ — אומדן (מחיר משוער) של המסלול הזול ביותר ממצב הצומת $n$ ועד למצב מטרה. תמיד מתקיים $h(n) \ge 0$ ולכל מצב מטרה $G$: $h(G) = 0$.

3.5 ★ קבילות, עקביות והוכחת האופטימליות של A*

3.6 חיפוש יוריסטי חסום בזיכרון (IDA*, RBFS, SMA*)

החיסרון הגדול של $A^*$ הוא צריכת הזיכרון האקספוננציאלית שלו. שלושת האלגוריתמים הבאים פותרים זאת:

3.7 בניית פונקציות יוריסטיות, שליטה ובעיות מוחלשות

• שליטה / דומיננטיות (Dominance): בהינתן שתי יוריסטיקות קבילות $h_1, h_2$, נאמר ש-$h_2$ שולטת על $h_1$ אם לכל צומת $n$: $h_2(n) \ge h_1(n)$ (למשל ב-8-פאזל: מרחק מנהטן $h_2$ שולט על מספר האריחים שלא במקומם $h_1$).
  כלל ברזל: תמיד נעדיף יוריסטיקה קבילה עם ערכים גבוהים ככל האפשר (קרובים ל-$h^*$), כי כל צומת עם $f(n) < C^* \iff h(n) < C^* - g(n)$ מפותח ע"י $A^*$, ולכן $h$ גבוהה יותר מפתחת פחות צמתים!
• שילוב מספר יוריסטיקות קבילות: אם $h_1, \dots, h_m$ כולן קבילות (ועקביות), אזי הפונקציה: $$h(n) = \max\{h_1(n), \dots, h_m(n)\}$$ היא בהכרח קבילה, עקבית, ושולטת על כולן! (זהירות: חיבור שלהן $h_1 + h_2$ אינו קביל באופן כללי כי הוא עלול לעבור את $h^*$).
• דרגת הסיעוף האפקטיבית ($b^*$): מדד לאיכות היוריסטיקה. אם $A^*$ יצר $N$ צמתים למציאת פתרון בעומק $d$, אז $N+1 = 1 + b^* + (b^*)^2 + \dots + (b^*)^d$. ככל ש-$b^*$ קרוב ל-1, היוריסטיקה טובה יותר.
• בעיות מוחלשות (Relaxed Problems): בעיה שמתקבלת מהבעיה המקורית ע"י הסרת חלק מהתנאים המקדימים (האילוצים) של הפעולות. מכיוון שרק הוספנו קשתות לגרף מרחב המצבים, המחיר של פתרון אופטימלי לבעיה המוחלשת הוא תמיד יוריסטיקה קבילה ועקבית לבעיה המקורית!
  ב-8-פאזל: (1) אם מותר להזיז אריח לכל משבצת סמוכה אפילו אם תפוסה $\leftarrow$ מקבלים את $h_2$ (מרחק מנהטן). (2) אם מותר להזיז אריח לכל מקום בלוח בצעד אחד $\leftarrow$ מקבלים את $h_1$ (מספר אריחים שלא במקומם).
• מסדי נתונים של תבניות (Pattern Databases - PDBs): פותרים מראש בחיפוש לאחור תת-בעיות (למשל רק את האריחים 1-2-3-4) ושומרים את המרחקים בטבלת Lookup. במסדי נתונים זרים של תבניות (Disjoint PDBs) מחלקים את האריחים לקבוצות זרות וסופרים בכל תת-בעיה רק הזזות של אריחי אותה קבוצה — ואז מותר לחבר את הערכים ולקבל יוריסטיקה קבילה ומדויקת להפליא!

4.1 עקרונות החיפוש המקומי ותמונת הנוף

אלגוריתמי חיפוש מקומי מיועדים לבעיות שבהן המסלול למטרה אינו חשוב כלל, אלא רק מצב המטרה הסופי (כמו בעיית 8 המלכות, תכנון מעגלים משולבים, שיבוץ ותזמון). במקום לשמור עץ חיפוש, הם משתמשים בניסוח מצב מלא (Complete-State Formulation) (למשל ב-8 מלכות: כל 8 המלכות נמצאות על הלוח, אחת בכל עמודה, וכל צעד מזיז מלכה לשורה אחרת בעמודה שלה — $8 \times 7 = 56$ שכנים לכל מצב), ושומרים מצב נוכחי יחיד בזיכרון.

4.2 טיפוס גבעה (Hill-Climbing) ווריאנטים

• טיפוס גבעה בסיסי (Steepest-Ascent Hill-Climbing): אלגוריתם חמדני מקומי. בכל שלב מפתח את כל השכנים של המצב הנוכחי ובוחר בשכן בעל הערך הטוב ביותר (במינימיזציה: $h(n)$ הקטן ביותר, כמו מספר זוגות המלכות המאיימות זו על זו). עוצר כאשר אין שכן שמשפר את המצב הנוכחי.
  הוספת צעדים הצידה (Sideways Moves): מתירים מעבר לשכן בעל ערך שווה למצב הנוכחי עד חסם קבוע (למשל עד 100 צעדים רצופים הצידה כדי לא להיתקע בלולאה אינסופית אם זה מקסימום מקומי שטוח ולא כתף). ב-8 מלכות זה מקפיץ את אחוז ההצלחה מ-14% ל-94%!
• טיפוס גבעה סטוכסטי (Stochastic Hill-Climbing): בוחר באקראי מבין הצעדים המשפרים, כאשר ההסתברות לבחירת צעד פרופורציונית לתלילות השיפור שלו. מתכנס לאט יותר אך לעיתים מוצא מקסימום טוב יותר.
• טיפוס גבעה עם בחירה ראשונה (First-Choice Hill-Climbing): כאשר מספר השכנים עצום (אלפים), במקום לחשב את כל השכנים, מגרילים שכנים אקראית בזה אחר זה ועוברים לשכן הראשון שמשפר את המצב הנוכחי.
• טיפוס גבעה חוזר עם אתחול אקראי (Random-Restart Hill-Climbing): מריץ סדרה של חיפושי טיפוס גבעה ממצבים התחלתיים אקראיים עד למציאת מצב מטרה ("אם לא תצליח – נסה שוב").
  • האלגוריתם שלם בהסתברות ששואפת ל-1!
  • אם ההסתברות להצלחה בריצה בודדת היא $p$, תוחלת מספר הריצות היא $1/p$ (ב-8 מלכות ללא צעדים הצידה: $p \approx 0.14 \implies \approx 7$ ריצות), ותוחלת מספר הצעדים הכוללת היא: $$E[\text{steps}] = \text{Cost(success)} + \frac{1-p}{p} \cdot \text{Cost(failure)}$$

4.3 הדמיית חישול (Simulated Annealing) וחיפוש קרן (Beam Search)

4.4 אלגוריתמים גנטיים (Genetic Algorithms - GA)

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

5.1 הגדרת משחק ואלגוריתם Minimax

בפרק זה אנו עוסקים במשחקי שני שחקנים (השחקן הפותח MAX ויריבו MIN) המשחקים לסירוגין בסביבה דטרמיניסטית, נראית במלואה (Perfect Information) ובסכום אפס (Zero-Sum) — כלומר מה שאחד מרוויח השני מפסיד.

• הגדרה פורמלית של משחק: מצב התחלתי $S_0$, פונקציית תור $\text{Player}(s)$, מהלכים חוקיים $\text{Actions}(s)$, מודל מעברים $\text{Result}(s,a)$, מבחן סיום $\text{Terminal-Test}(s)$, ופונקציית תועלת $\text{Utility}(s,p)$ הנותנת ציון מספרי למצבי הסיום (העלים).
• אלגוריתם Minimax: מבצע סריקת DFS מלאה של עץ המשחק ומפעפע ערכים מהעלים כלפי מעלה עד לשורש: $$\text{Minimax}(s) = \begin{cases} \text{Utility}(s) & \text{if Terminal-Test}(s) \\ \max_{a \in \text{Actions}(s)} \text{Minimax}(\text{Result}(s,a)) & \text{if Player}(s) = \text{MAX} \\ \min_{a \in \text{Actions}(s)} \text{Minimax}(\text{Result}(s,a)) & \text{if Player}(s) = \text{MIN} \end{cases}$$
• תכונות Minimax: שלם (בעצים סופיים), אופטימלי מול יריב אופטימלי (אם MIN טועה ולא משחק אופטימלית, MAX ישיג תוצאה טובה לפחות כמו ערך המינימקס ואף יותר!). סיבוכיות מקום: $O(b \cdot m)$ (בגלל סריקת DFS), אך סיבוכיות הזמן היא $O(b^m)$ אקספוננציאלית (בשחמט $35^{100}$ – בלתי אפשרי ללא גיזום וחיתוך!).
• הרחבה למשחקים מרובי שחקנים (Multiplayer): במקום ערך בודד, בכל צומת שומרים וקטור של ערכים $(v_A, v_B, v_C)$, ובכל תור השחקן שמשחק בוחר את המהלך שממקסם את הרכיב שלו בווקטור.

5.2 ★ גיזום אלפא-ביתא ($\alpha-\beta$ Pruning) ושיטת המעקב

גיזום אלפא-ביתא מוותר על פיתוח תת-עצים שלמים שאינם יכולים בשום אופן להשפיע על ההחלטה הסופית בשורש. הגיזום מחזיר תמיד בדיוק את אותו מהלך וערך כמו Minimax המלא!

function ALPHA-BETA-SEARCH(state) returns an action
    v := MAX-VALUE(state, -∞, +∞)
    return the action in ACTIONS(state) with value v

function MAX-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state)
    v := -∞
    for each a in ACTIONS(state) do
        v := MAX(v, MIN-VALUE(RESULT(state, a), α, β))
        if v ≥ β then return v   // Beta cutoff (pruning!)
        α := MAX(α, v)
    return v

function MIN-VALUE(state, α, β) returns a utility value
    if TERMINAL-TEST(state) then return UTILITY(state)
    v := +∞
    for each a in ACTIONS(state) do
        v := MIN(v, MAX-VALUE(RESULT(state, a), α, β))
        if v ≤ α then return v   // Alpha cutoff (pruning!)
        β := MIN(β, v)
    return v

• השפעת סדר פיתוח הבנים על סיבוכיות $\alpha-\beta$:
  • בסידור אופטימלי ("סידור מושלם" – המהלך הטוב ביותר לכל שחקן נבחן ראשון): סיבוכיות הזמן צונחת מ-$O(b^m)$ ל-$O(b^{m/2})$! משמעות הדבר היא שדרגת הסיעוף האפקטיבית יורדת מ-$b$ ל-$\sqrt{b}$, ולכן ניתן להכפיל את עומק החיפוש באותו זמן חישוב!
  • בסידור אקראי: סיבוכיות הזמן היא $O(b^{3m/4})$.
  • בסידור הגרוע ביותר (אין גיזומים כלל): סיבוכיות הזמן נשארת $O(b^m)$.
  • כיצד מסדרים בנים בפועל (סידור יוריסטי)? בוחנים בשחמט קודם לקיחות/הכאות, אח"כ איומים (שח), אח"כ מהלכים קדימה ולבסוף אחורה; או נעזרים בתוצאות האיטרציה הקודמת של Iterative Deepening ובטבלאות טרנספוזיציה (Transposition Tables) השומרות הערכות של מצבים חוזרים.

5.3 החלטות זמן-אמת: פונקציית הערכה, אפקט האופק ו-Quiescence

מכיוון שלא ניתן לרדת עד העלים במשחקים אמיתיים, קלוד שאנון (Shannon) הציע שני שינויים באלגוריתם אלפא-ביתא: (1) החלפת `TERMINAL-TEST` במבחן חיתוך (`CUTOFF-TEST`) הקובע מתי לעצור את העמקת החיפוש, (2) החלפת `UTILITY` בפונקציית הערכה יוריסטית (`EVAL(s)`) האומדת את סיכויי הניצחון ממצב ביניים.

6.1 הגדרת CSP וסוגי אילוצים

בניגוד לחיפוש בפרקים 3–5 שהתייחס לכל מצב כ"קופסה שחורה" אטומית, בבעיות סיפוק אילוצים (CSP) אנו מנצלים את הייצוג המחולק לגורמים (Factored) כדי לפסול חלקים עצומים ממרחב החיפוש מיד כשמזהים הפרת אילוץ, באמצעות יוריסטיקות כלליות שאינן תלויות בבעיה ספציפית.

• סוגי אילוצים:
  • אילוץ אונרי (Unary): מגביל משתנה יחיד (למשל $SA \neq \text{Green}$). מטופל מיד ע"י מחיקת הערך מה-Domain של אותו משתנה (עקביות צומת - Node Consistency).
  • אילוץ בינארי (Binary): מתייחס לזוג משתנים (למשל $SA \neq NSW$, או ב-8 מלכות $Q_i \neq Q_j \land |Q_i - Q_j| \neq |i - j|$). ניתן לייצוג כגרף אילוצים.
  • אילוץ גלובלי ($n$-ary): מערב מספר שרירותי של משתנים, והנפוץ ביותר הוא Alldiff (כל המשתנים בקבוצה חייבים לקבל ערכים שונים זה מזה, כמו בשורה/עמודה/ריבוע בסודוקו). הערה: כל אילוץ מסדר גבוה מעל תחומים סופיים ניתן להמרה לאילוצים בינאריים בעזרת משתני עזר!
  • אילוצי קדימות (Preference Constraints): אילוצים "רכים" המגדירים אילו פתרונות עדיפים (בעיות אופטימיזציה תחת אילוצים - COP).

6.2 ★ עקביות קשת ואלגוריתם AC-3

• מתי AC-3 אינו מספיק? (עקביות מסלול ו-$k$-עקביות): במשולש של 3 מדינות סמוכות (כמו $WA, NT, SA$) עם 2 צבעים בלבד $\{R, B\}$, כל הקשתות עקביות לפי AC-3 למרות שאין פתרון!
  • עקביות מסלול (Path Consistency / 3-consistency): בודקת שלכל זוג ערכים עקבי ב-$\{X_i, X_j\}$ קיים ערך מתאים במשתנה שלישי $X_m$.
  • גרף $k$-עקבי חזק (Strongly $k$-consistent): אם הוא $k$-עקבי, $(k-1)$-עקבי וכו' עד $1$-עקבי. אם גרף בעל $n$ משתנים הוא $n$-עקבי חזק, ניתן לפתור אותו ללא נסיגות כלל (Backtrack-free) בזמן $O(n^2 d)$, אך אכיפת $n$-עקביות דורשת זמן ומקום אקספוננציאליים ב-$n$.

6.3 חיפוש Backtracking ויוריסטיקות כלליות (MRV, Degree, LCV)

כאשר הפצת אילוצים (AC-3) מסתיימת ועדיין נותרו משתנים עם יותר מערך אחד ב-Domain שלהם, אנו מפעילים חיפוש לעומק עם נסיגה (Backtracking Search). בגלל ש-CSP היא קומוטטיבית (סדר הצבת המשתנים אינו משנה את התוצאה), בכל רמה בעץ בוחרים משתנה אחד בלבד להשמה, מה שמקטין את מספר העלים מ-$n! \cdot d^n$ ל-$d^n$.

6.4 בדיקה קדימה (Forward Checking) וחיפוש מקומי (Min-Conflicts)

• בדיקה קדימה (Forward Checking - FC) מול AC-3 (MAC):
  • ב-Forward Checking, בכל פעם שמציבים ערך במשתנה $X$, עוברים רק על השכנים הישירים של $X$ שטרם הושמו ומוחקים מה-Domains שלהם ערכים שסותרים את ההשמה של $X$. זוהי בדיקה מהירה שמספקת את המידע הדרוש ליוריסטיקת MRV, אך היא לא מסתכלת מעבר לשכנים הישירים (ולכן לא תזהה ששני שכנים של $X$ נותרו שניהם עם אותו צבע יחיד בלבד!).
  • ב-MAC (Maintaining Arc Consistency) מריצים את אלגוריתם AC-3 המלא אחרי כל השמה בחיפוש, וכך מזהים חוסר עקביות מוקדם הרבה יותר.
• חיפוש מקומי ל-CSP – יוריסטיקת מינימום סתירות (Min-Conflicts): מתחילים מהשמה שלמה לכל המשתנים (אפילו שהיא מפרה אילוצים). בכל צעד בוחרים אקראית משתנה שמעורב בסתירה, ומשנים את ערכו לערך שיוצר הכי מעט התנגשויות (סתירות) עם שאר המשתנים.
  • ביצועים מדהימים: פותר את בעיית $n$-המלכות (אפילו עבור $n = 1,000,000$ מלכות!) בזמן ריצה שהוא כמעט קבוע ובלתי תלוי ב-$n$! בנוסף, מצוין לבעיות דינמיות כמו שיבוץ טיסות שהשתבש ודורש תיקון מינימלי מהלוח הקיים.

7.1 בסיס ידע, נביעה לוגית, נאותות ושלמות

• סוכן מבוסס-ידע (Knowledge-Based Agent): מורכב מבסיס ידע (KB - Knowledge Base) המאחסן פסוקים בשפה פורמלית, וממנגנון היסק (Inference Engine). ממשק הסוכן מבוסס על שתי פעולות: TELL (הוספת עובדה/פסוק ל-KB) ו-ASK (שליפת מסקנה/פעולה הנובעת מה-KB).
• תחביר (Syntax) מול סמנטיקה (Semantics): התחביר מגדיר אילו רצפי סימנים הם פסוקים חוקיים בשפה; הסמנטיקה מגדירה את ערך האמת (True/False) של כל פסוק ביחס לכל מודל (Model - עולם אפשרי $m$).
• נביעה לוגית (Entailment — $\text{KB} \models \alpha$): פסוק $\alpha$ נובע לוגית מ-$\text{KB}$ אם ורק אם בכל מודל שבו $\text{KB}$ אמיתי, גם $\alpha$ אמיתי (כלומר $M(\text{KB}) \subseteq M(\alpha)$).

7.2 תחשיב הפסוקים, CNF והוכחה ברזולוציה

• בדיקת מודלים באמצעות טבלת אמת (`TT-ENTAILS?`): עוברת על כל $2^n$ השורות בטבלת האמת (עבור $n$ סימבולים) ובודקת שבכל שורה שבה $\text{KB}=\text{True}$, גם $\alpha=\text{True}$. האלגוריתם נאות ושלם, סיבוכיות מקום $O(n)$, אך סיבוכיות זמן $O(2^n)$.
• תקפות (Validity) מול ספיקות (Satisfiability - SAT):
  • פסוק הוא תקף (Valid / טאוטולוגיה) אם הוא אמיתי בכל המודלים. (משפט הדדוקציה: $\alpha \models \beta \iff (\alpha \Rightarrow \beta)$ תקף).
  • פסוק הוא ספיק (Satisfiable) אם קיים לפחות מודל אחד שבו הוא אמיתי.
  • הקשר הדואלי והוכחה בדרך השלילה (Refutation): $\alpha$ תקף $\iff \neg \alpha$ אינו ספיק. לכן: $$\text{KB} \models \alpha \iff (\text{KB} \land \neg \alpha) \text{ is Unsatisfiable (סתירה!)}$$
• צורה קוניונקטיבית נורמלית (CNF - Conjunctive Normal Form): פסוק הכתוב כקוניונקציה ($\land$) של פסוקיות (Clauses), כאשר כל פסוקית היא דיסיונקציה ($\lor$) של ליטרלים: $(L_{1,1} \lor L_{1,2}) \land (L_{2,1} \lor \neg L_{2,2})$.
• כלל הרזולוציה ואלגוריתם הרזולוציה (`PL-RESOLUTION`): בהינתן שתי פסוקיות המכילות ליטרל משלים (אחת עם $\ell$ והשנייה עם $\neg \ell$), ניתן לגזור פסוקית חדשה (Resolvant) המכילה את איחוד כל שאר הליטרלים משתי הפסוקיות ללא הזוג המשלים: $$\frac{(\alpha \lor \ell), \quad (\beta \lor \neg \ell)}{\alpha \lor \beta}$$ כדי להוכיח $\text{KB} \models \alpha$, ממירים את $(\text{KB} \land \neg \alpha)$ ל-CNF ומפעילים רזולוציה עד שמתקבלת הפסוקית הריקה ($\emptyset$ / $\{\}$) המעידה על סתירה (ולכן המשפט הוכח!), או עד שלא ניתן לגזור פסוקיות חדשות (ואז $\alpha$ אינו נובע). אלגוריתם הרזולוציה הוא נאות ושלם!

7.3 פסוקיות Horn, שרשור קדימה (FC) ושרשור אחורה (BC)

7.4 בדיקת מודלים יעילה (DPLL, WalkSAT) ובעיית המסגרת

8.1 תחביר, סמנטיקה והצרנה בלוגיקה מסדר ראשון (FOL)

בעוד תחשיב הפסוקים מניח שהעולם מורכב מעובדות אטומיות בלבד, לוגיקה מסדר ראשון (FOL) מניחה שהעולם מורכב מ-3 אלמנטים: אובייקטים (עצמים), יחסים/פרדיקטים (מחזירים True/False), ופונקציות (מחזירות אובייקט!).

9.1 כללי הצבה לכמתים (UI, EI), האחדה ו-MGU

• כלל ההצבה לכמת כולל (UI - Universal Instantiation): מ-$\forall v \, \alpha$ מותר להסיק את $\text{SUBST}(\{v/g\}, \alpha)$ לכל ביטוי קרקעי (ללא משתנים) $g$. ניתן להפעילו פעמים רבות.
• כלל ההצבה לכמת ישי (EI - Existential Instantiation): מ-$\exists v \, \alpha$ מותר להסיק את $\text{SUBST}(\{v/k\}, \alpha)$ כאשר $k$ הוא קבוע Skolem חדש לחלוטין שלא הופיע עד כה בבסיס הידע. מופעל פעם אחת בלבד.
• משפט הרברנד (Herbrand): אם פסוק נובע לוגית מ-KB ב-FOL, אז יש לו הוכחה סופית לאחר הצבת קבועים ומופעי פונקציות עד עומק סופי. אולם אם הפסוק אינו נובע, חיפוש ההוכחה עלול לרוץ לנצח — לכן הנביעה ב-FOL היא כריעה למחצה (Semidecidable)!

9.2 ★ 6 שלבי ההמרה ל-CNF וסקולמיזציה

9.3 ★ הוכחה ברזולוציה ב-FOL ואסטרטגיות ייעול (Set of Support)

11. ¬loc(Fred, Museum)                                 [Negated Goal - Set of Support]
12. ¬gooddog(Fred) ∨ ¬master(Fred, d) ∨ ¬loc(d, Museum) [Res 11 & 8 with {c/Fred, e/Museum}]
13. ¬collie(Fred) ∨ ¬trained(Fred) ∨ ¬master(Fred, d) ∨ ¬loc(d, Museum) [Res 12 & 7 {b/Fred}]
14. ¬trained(Fred) ∨ ¬master(Fred, d) ∨ ¬loc(d, Museum) [Res 13 & 1]
15. ¬master(Fred, d) ∨ ¬loc(d, Museum)                  [Res 14 & 5]
16. ¬loc(Sam, Museum)                                   [Res 15 & 2 with {d/Sam}]
17. ¬day(Sat) ∨ warm(Sat)                               [Res 16 & 10]
18. ¬day(Sat)                                           [Res 17 & 4]
19. {} (Empty Clause - Contradiction!)                  [Res 18 & 3 -> Proven!]

10.1 הגדרת תכנון קלאסי ושפת PDDL

תכנון קלאסי עוסק במציאת סדרת פעולות (Plan) בסביבה דטרמיניסטית, סופית, סטטית ונראית במלואה. כדי להתמודד עם מרחבי מצבים עצומים שבהם חיפוש אטומי נכשל, משתמשים בשפת הייצוג PDDL (Planning Domain Definition Language):

// דוגמה לסכימת פעולה ב-PDDL (עולם הקוביות):
Action( Stack(x, y),
    PRECOND: Holding(x) ∧ Clear(y) ∧ Block(x) ∧ Block(y) ∧ (x ≠ y)
    EFFECT:  On(x, y) ∧ Handempty ∧ ¬Holding(x) ∧ ¬Clear(y) )
    // ADD(Stack) = {On(x,y), Handempty},  DEL(Stack) = {Holding(x), Clear(y)}

10.2 תכנון כחיפוש: קדימה (Progression) מול אחורה (Regression) ויוריסטיקות

• יצירת יוריסטיקות אוטומטיות ב-PDDL (בעיות מוחלשות):
  1. התעלמות מתנאים מקדימים (Ignore Preconditions): כל פעולה ניתנת לביצוע מיד.
  2. התעלמות מרשימות המחיקה (Ignore Delete Lists): מוחקים את כל הליטרלים השליליים מכל ה-EFFECT של הפעולות. כך שום פעולה אינה מקלקלת התקדמות של פעולות אחרות! מציאת הפתרון האופטימלי לבעיה מוחלשת זו נותנת יוריסטיקה קבילה (ואת הקירוב שלה מוצאים במהירות באמצעות טיפוס גבעה).

10.3 ★ גרפי תכנון (Planning Graphs), יחסי Mutex ואלגוריתם GRAPHPLAN

גרף תכנון הוא גרף מכוון בשכבות המתחלפות בין שכבת ליטרלים $S_i$ לשכבת פעולות $A_i$: $S_0 \to A_0 \to S_1 \to A_1 \dots$.
• $S_0$ מכילה את הליטרלים של המצב ההתחלתי.
• $A_i$ מכילה את כל הפעולות שהתנאים המקדימים שלהן מופיעים ב-$S_i$ (ללא Mutex ביניהם), ובנוסף פעולות התמדה (`No-Op` / Persistence) לכל ליטרל $C \in S_i$ המעבירות אותו ללא שינוי ל-$S_{i+1}$!
• הגרף נבנה בזמן ומקום פולינומיאליים: $O(n(a + l)^2)$.

13.1 לפעול בתנאי אי-ודאות, אי-תלות מותנה ועקרון MEU

• מקורות אי-ודאות בעולם האמיתי: נראות חלקית, חיישנים רועשים, חוסר הבנה מלאה של חוקי העולם (כמו ברפואה), ומורכבות חישובית שלא מאפשרת מעקב מדויק אחר כל גורם. בניגוד ללוגיקה שבה פסוק הוא True/False, בהסתברות משייכים לכל עובדה מידת אמונה (Degree of Belief) מספרית ב-$[0,1]$ ביחס לידע של הסוכן.
• תורת קבלת ההחלטות ועקרון MEU: $$\text{Decision Theory} = \text{Probability Theory (מהם הסיכויים?)} + \text{Utility Theory (מהן ההעדפות?)}$$ לפי עקרון מקסימום תוחלת התועלת (MEU - Maximum Expected Utility), סוכן הוא רציונלי אם ורק אם הוא בוחר בפעולה המניבה את תוחלת התועלת הגבוהה ביותר על פני כל התוצאות האפשריות.
• התפלגות משותפת מלאה מול אי-תלות מותנה: טבלת ההתפלגות המשותפת המלאה עבור $n$ משתנים בוליאניים דורשת $2^n$ שורות (עבור $n=30$ מעל מיליארד מספרים!). הפתרון הוא ניצול אי-תלות מותנה (Conditional Independence):
  • אי-תלות מוחלטת: $P(X, Y) = P(X) \cdot P(Y) \iff P(X \mid Y) = P(X)$.
  • אי-תלות מותנה ($X$ ו-$Y$ בלתי תלויים בהינתן $Z$): $$P(X, Y \mid Z) = P(X \mid Z) \cdot P(Y \mid Z) \iff P(X \mid Y, Z) = P(X \mid Z)$$ (למשל: כאב שיניים `Toothache` ותפיסת מכשיר הרופא `Catch` תלויים זה בזה, אך בהינתן שאנו יודעים אם יש או אין חור בשן `Cavity`, הם הופכים לבלתי תלויים!).

14.1 מבנה רשת בייסיאנית, CPTs וקומפקטיות

14.2 ★ אלגוריתם d-separation ומורליזציה לבדיקת אי-תלות מותנה

שאלה קלאסית במבחן: בהינתן גרף של רשת בייסיאנית, "האם המשתנים $X$ ו-$Y$ בלתי תלויים מותנה בהינתן קבוצת המשתנים הידועים $Z$ (ה-givens)?" (כלומר האם $P(X \mid Y, Z) = P(X \mid Z)$?).
להלן אלגוריתם 5 השלבים (המבוסס על גרף אנצסטרלי ומורליזציה) שפותר כל שאלת d-separation במבחן בצורה מכנית ונטולת טעויות:

14.3 ★ חישוב הסתברויות ברשת בייסיאנית

17.1 הגדרת MDP, מדיניות ($\pi$) והפליית העתיד ($\gamma$)

בעיית קבלת סדרת החלטות בסביבה סטוכסטית ונראית במלואה עם מודל מעברים מרקובי ותגמולים מצטברים ממודלת כ-MDP (Markov Decision Process) המורכב מ-4 רכיבים:

• מהו פתרון של MDP? מדיניות (Policy — $\pi$): בסביבה סטוכסטית סדרת פעולות קבועה מראש תיכשל ברגע שהסוכן יחליק למשבצת לא צפויה. לכן הפתרון ל-MDP הוא מדיניות $\pi(s)$ — פונקציה המתאימה לכל מצב $s$ את הפעולה המומלצת לביצוע בו. המדיניות שממקסמת את תוחלת התועלת נקראת המדיניות האופטימלית $\pi^*(s)$.
• אופק סופי מול אופק אינסופי: באופק סופי (יש Deadline קבוע $N$) המדיניות האופטימלית היא תלוית-זמן (Nonstationary). באופק אינסופי (אין הגבלת זמן מראש) המדיניות האופטימלית היא קבועה (Stationary).
• תגמולים מהוונים ומקדם הפליית העתיד (Discount Factor — $\gamma \in [0,1)$): כדי שהתועלת של סדרת מצבים אינסופית תהיה סופית ומוגדרת היטב (ולשקף העדפה של רווח מיידי על פני רווח עתידי), מגדירים את התועלת כסכום מהוון: $$U_h([s_0, s_1, s_2, \dots]) = R(s_0) + \gamma R(s_1) + \gamma^2 R(s_2) + \dots = \sum_{t=0}^\infty \gamma^t R(s_t) \le \frac{R_{\max}}{1 - \gamma}$$

17.2 ★ נוסחת בלמן ואלגוריתם Value Iteration (VI)

17.3 אלגוריתם Policy Iteration (PI) והשוואה מול VI

אלגוריתם Policy Iteration (PI) מנצל את העובדה שהמדיניות $\pi$ הופכת לאופטימלית הרבה לפני שערכי ה-$U(s)$ מתכנסים לערכם המדויק. הוא מתחיל ממדיניות אקראית $\pi_0$ ומבצע לסירוגין שני צעדים:

18.1 אופני למידה, סיווג מול רגרסיה והתער של אוקם

• 3 סוגי הלמידה העיקריים (לפי סוג המשוב):
  1. למידה לא מפוקחת (Unsupervised Learning): הסוכן מקבל קלטים ללא תוויות פלט נכונות כלל, ומגלה תבניות ואשכולות בנתונים (כמו Clustering).
  2. למידה מחיזוקים (Reinforcement Learning): הסוכן לומד מסדרת תגמולים (חיזוקים חיוביים) ועונשים (חיזוקים שליליים) בעקבות פעולותיו בסביבה.
  3. למידה מפוקחת (Supervised Learning / למידה אינדוקטיבית): הסוכן מקבל קבוצת אימון (Training Set) של זוגות קלט-פלט מתויגים $(x, f(x))$, ומחפש פונקציית השערה $h \approx f$ שתכליל היטב על דוגמאות חדשות בקבוצת הבדיקה (Test Set).
• סיווג (Classification) מול רגרסיה (Regression): כאשר טווח ערכי הפלט $f(x)$ הוא בדיד/סופי (למשל כן/לא, ספאם/תקין) – הבעיה נקראת סיווג. כאשר הפלט הוא רציף (למשל חיזוי טמפרטורה או מחיר מניה) – הבעיה נקראת רגרסיה.
• התער של אוקם (Ockham's Razor): כאשר יש מספר השערות שעקביות עם קבוצת האימון (למשל קו ישר מול פולינום ממעלה 7 שעובר בכל הנקודות), נעדיף תמיד את ההשערה הפשוטה ביותר (למשל עץ ההחלטה הקטן ביותר), כי היא צפויה להכליל טוב יותר על נתונים חדשים.

18.2 ★ למידת עצי החלטה (DTL / ID3), אנטרופיה ו-Information Gain

עץ החלטה (Decision Tree) מייצג פונקציה המקבלת וקטור של ערכי תכונות ומחזירה החלטת סיווג: כל צומת פנימי בודק תכונה $A_i$, כל קשת מייצגת ערך אפשרי של התכונה, וכל עלה מכיל את סיווג הפלט.
• כושר ביטוי: עצי החלטה יכולים לבטא כל פונקציה בוליאנית! עבור $n$ תכונות בוליאניות יש $2^n$ שורות בטבלת האמת ולכן $2^{2^n}$ פונקציות/עצים שונים. מסיבה זו חיפוש העץ הקטן ביותר הוא NP-קשה, ואנו משתמשים באלגוריתם חמדני של הפרד-ומשול (DTL / ID3) הבוחר בכל שלב לפצל לפי התכונה הכי אינפורמטיבית.

18.3 התאמת יתר (Overfitting), גיזום ואימות צולב (Cross-Validation)

• בעיית התכונות מרובות הערכים ו-Overfitting: מדד תוספת האינפורמציה (Gain) נוטה להעדיף באופן מוטה תכונות שיש להן המון ערכים אפשריים שונים (למשל תכונת "תאריך" או "מספר סידורי" שבה לכל דוגמה יש ערך ייחודי – ה-Remainder שלה יהיה 0 וה-Gain מקסימלי, אך העץ שייווצר לא יכליל כלל!).
  התאמת יתר (Overfitting): מצב שבו העץ לומד את ה"רעש" הספציפי של קבוצת האימון — ככל שמספר הצמתים בעץ גדל, הדיוק על קבוצת האימון עולה ל-100%, אך הדיוק על קבוצת הבדיקה (Test Set) יורד!
• כיצד מונעים Overfitting? גיזום עץ ההחלטה (Pruning): בונים את העץ המלא בעזרת DTL, ואז עוברים מלמטה למעלה על צמתי בדיקה שכל צאצאיהם הם עלים. אם הפיצול בצומת אינו מובהק סטטיסטית (תוספת האינפורמציה שלו קרובה ל-0 והיחס $\frac{p}{p+n}$ בתתי-הקבוצות זהה ליחס בצומת האב) — גוזמים את הצומת ומחליפים אותו בעלה עם סיווג הרוב!
• מקרי קצה בעצי החלטה:
  • רעש בנתונים (שתי דוגמאות עם אותן תכונות בדיוק אך סיווג שונה): כשנגמרו התכונות לפיצול, העלה מחזיר את ערך הרוב (Majority Value) של הדוגמאות שנפלו אליו.
  • עלה ריק (אין בדוגמאות האימון אף מופע לערך מסוים של התכונה): העלה מחזיר כברירת מחדל את סיווג הרוב של צומת האב שלו.
  • תכונות רציפות: ביצוע דיסקרטיזציה (נקודות חתך, למשל $\text{Temp} > 25$).
• הערכת ביצועי השערה (Holdout ו-$k$-Fold Cross-Validation): תחת הנחת i.i.d (דוגמאות בלתי תלויות ובעלות התפלגות זהה), מודדים את שיעור השגיאה על קבוצת בדיקה נפרדת (Holdout Cross-Validation). כדי לנצל את כל הנתונים בצורה מיטבית משתמשים ב-$k$-Fold Cross-Validation (בדרך כלל $k=5$ או $k=10$): מחלקים את המדגם ל-$k$ תתי-קבוצות שוות, מריצים $k$ פעמים כשבכל פעם $\frac{1}{k}$ משמש כקבוצת בדיקה ו-$\frac{k-1}{k}$ כקבוצת אימון, וממצעים את הציון.

18.4 סיווג מבוסס דוגמאות: השכן הקרוב (Nearest Neighbor) ו-IB3