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

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

מקצרמר למובחר.PNG


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

למידה חישובית (Machine Learning) (לעתים מכונה גם למידת מכונה) היא תת-תחום במדעי המחשב ובבינה מלאכותית ומשיק לתחומי הסטטיסטיקה והאופטימזציה. התחום עוסק בפיתוח אלגוריתמים המיועדים לאפשר למחשב ללמוד מתוך דוגמאות ופועל במגוון משימות חישוביות בהן התכנות הקלאסי אינו אפשרי. אין לבלבל בין תחום זה, שבו המחשב הוא הלומד, ובין למידה ממוחשבת, שבה המחשב משמש כעזר למידה על ידי הרצת לומדה או בדרך אחרת. שני תחומים מקבילים ללמידה חישובית הם תחום כריית מידע (Data Mining) ותחום זיהוי תבניות (Pattern Recognition) שרבים מן הכלים והאלגוריתמים שפותחו משותפים לתחומים הללו.

הגדרה[עריכת קוד מקור | עריכה]

ארתור סמואל הגדיר את הלמידה החישובית בשנת 1959 כ - "תחום מחקר המאפשר למחשבים את היכולת ללמוד ללא להיות מתוכנתים באופן ספציפי". [1] טום מ. מיטשל סיפק הגדרה פורמלית יותר: "תוכנית מחשב תיקרא לומדת מנסיון E ביחס למחלקת משימות T ומדד ביצועים P, במידה והביצועים של משימות ב- T, בהתאם למדד P, משתפרים עם הנסיון E".[2]

מטרות ושימושים[עריכת קוד מקור | עריכה]

המטרה המרכזית של למידה חישובית היא טיפול ממוחשב בנתונים מן העולם האמיתי עבור בעיה מסוימת, כאשר לא ניתן לכתוב תוכנת מחשב עבורה‏[3] למשל, בעיית זיהוי שמומחה אנושי מסוגל לפתור, אך לא מסוגל לכתוב את הכללים לזיהוי בצורה מפורשת, או שהם משתנים עם הזמן ולא ניתנים לכתיבה מראש.

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

תאוריה[עריכת קוד מקור | עריכה]

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

בעקבות הגישות התאורטיות צמחו מספר אלגוריתמים מעשיים. למשל, תאוריית PAC עוררה השראה לאלגורתמי Boosting, תאוריית VC הובילה לאלגוריתם מכונת וקטורים תומכים (SVM) והסקה בייסיאנית הובילה לאלגוריתמי רשתות בייסיאניות.

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

הסקה והחלטה - כאשר אנו מדברים על בעיית סיווג בדרך כלל נחלק את הבעיה לשני שלבים. בשלב הראשון נרצה להסיק (inference) מתוך סט האימון את ההתפלגות האחודה p(x , C_k), שמספקת לנו תיאור הסתברותי שלם על המצב. בשלב שני נרצה להחליט (Decision) במידה אופטימלית על מידע חדש שלא ראינו בסט האימון לאילו מן המחלקות C_k הוא שייך וזאת על סמך ההתפלגות שמצאנו בשלב הראשון. לעיתים שלב ההחלטה יכול להיות טריוויאלי ולהיגזר ישירות מהשלב הראשון. ניתן לזהות שלוש גישות שונות לפתרון בעיות החלטה:

  1. תחילה נפתור את בעיית ההסקה ע"י קביעת ההסתברויות המותנות p(x | C_k) באופן נפרד לכל מחלקה C_k, הסתברות זו מכונה לעיתים "הנראות" (Likelihood). בנפרד נקבע את ההסתברות "הא-פריורית" (Prior) של המחלקות השונות p(C_k) שאותה אנו יודעים לעיתים מתוך האוכלוסיה הכללית. ואז נמצא את ההסתברות "הפוסטריורית" (Posterior) p(C_k | x) באמצעות משפט בייס שהוא מן הצורה:
    p(C_k|x) = \frac{p(x|C_k)p(C_k)}{p(x)})
    את ההסתברות p(x) ניתן לחשב מתוך כלל הסכום בצורה הבאה:
    p(x) = \sum_{k}p(x|C_k)p(C_k)

    בהינתן ההיסתברויות הפוסטרריות נפעיל את כלל ההחלטה לקבוע לאיזו מחלקה שייכת דוגמא חדשה. גישות מסוג זה מכונות גם מודלים גנרטיביים (Generative Models), משום שלאחר קביעת ההתפלגויות ניתן לייצר מהן דוגמאות סינטטיות.
  2. תחילה נפתור את בעיית הההסקה על-ידי קביעת ההסתברות הפוסטריורית p(C_k|x) ואז נפעיל את כלל ההחלטה לקבוע לאיזו מחלקה שייכת דוגמא חדשה. גישות מסוג זה מכונות גם מודלים דיסקרימינטיביים (Discriminative Models).
  3. נמצא פונקציה f(x) הנקראת פונקציה דיסקרמיננטית, הממפה כל x למחלקה מסויימת. במקרה זה אין שימוש בהסתברות.

סוגי למידה[עריכת קוד מקור | עריכה]

נהוג לחלק את אלגוריתמי הלמידה החישובית למספר סוגים:

  • למידה מונחית (supervised learning). כל דוגמה מגיעה ביחד עם תווית סיווג. מטרת האלגוריתם היא לחזות את הסיווג של דוגמאות חדשות שאותן לא פגש בתהליך הלמידה. אימון של רשת עצבית מלאכותית ("רשת נוירונים") מסתמך על אלגוריתמים מסוג זה.
  • למידה בלתי מונחית (unsupervised learning). מטרת האלגוריתמים היא למצוא ייצוג פשוט וקל להבנה של אוסף הנתונים. שיטות נפוצות מסוג זה הן חלוקה לצברים (clustering), והטלה ליריעות ממד נמוך כגון Principle component analysis.
  • למידת חיזוק (reinforcement learning). אלגוריתם הלמידה מקבל משוב חלקי על ביצועיו (רק לאחר סיום ביצוע המטלה) ועליו להסיק אילו מהחלטותיו הביאו להצלחה/כישלון.

סוגי בעיות[עריכת קוד מקור | עריכה]

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

אלגוריתמים נפוצים[עריכת קוד מקור | עריכה]

למידת מכונה כוללת אוסף ידוע של כמה עשרות אלגוריתמים. ניתן לסווג אלגוריתמים אילו על פי מספר תבחינים.

עצלנים (Lazzy) מול חרוצים (Eager).[עריכת קוד מקור | עריכה]

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

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

מקומי (Local) מול גלובלי (Global).[עריכת קוד מקור | עריכה]

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

אלגוריתם גלובלי לעומתו מחשב מודל שאמור להיות תקף בכל מרחב הנתונים הרלוונטי.

להלן מספר אלגוריתמים ידועים:

היסטוריה[עריכת קוד מקור | עריכה]

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

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

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

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

למידה חישובית בישראל[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ Phil Simon (March 18, 2013). Too Big to Ignore: The Business Case for Big Data. Wiley, 89. ISBN 978-1118638170. 
  2. ^ * Mitchell, T. (1997). Machine Learning, McGraw Hill. ISBN 0-07-042807-7, p.2.
  3. ^ Introduction to Machine Learning, Ethem Alpaydin, MIT Press, 2004
  4. ^ Valiant, Leslie, "A theory of the learnable" (עמודים 1134–1142), ‏1984 (באנגלית)
  5. ^ V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16(2):264–280, 1971.
  6. ^ א.מ גולד, Language Identification in the Limit (עמודים 447–474), Information and Control, ‏1967 (באנגלית)


P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.