אלגוריתמים אבולוציונים וחיים מלאכותיים

עבודה 4

 

 

 

מגישים:

יסמין שטיינר – 011950466

איציק חאב – 040210148

 

הגדרת הבעיה:

בניית רשת נוירונים שתדע לזהות ניצחון של X בלוח סוף משחק של המשחק XO.

הלמידה של הרשת היא למידה מפוקחת, כאשר מסופק מאגר נתונים שמכיל 958 Inputs לרשת (לוחות סוף משחק) ועבור כל אחד מהם את ה- Output הרצוי (האם זהו לוח שבו יש נצחון ל- X או לא). במהלך הלמידה נספק לרשת רק חלק מהמקרים במאגר הנתונים ולאחר סיום שלב הלמידה, נריץ על הרשת שנוצרה את שאר המקרים כדי לראות עד כמה הרשת הצליחה להגיע למצב של הכללה ויכולה לזהות גם מקרים שלא ראתה בשלב הלמידה.

 

תהליך הביצוע:

 

קישור לקוד: SourceFiles.zip

 

רשת הנוירונים נבנתה בצורה הבאה:

*) 9 נוירוני קלט (אחד עבור כל מיקם בלוח)

*) H שכבות חבויות של נוירונים

*) N נוירונים בכל שכבה חבויה

*) נוירון פלט אחד

 

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

הנוירונים שהם מסוג InputNeuron הם נוירונים אשר רק מעבירים הלאה את מה שהם קיבלו.

הנוירונים שהם מסוג HiddenNeuron הם נוירונים מסוג Sigmoid אשר מחשבים את הסכום של WiXi עבור כל ה- Inputs של אותו נוירון, ועל הסכום הזה מפעילים את פונקציית ה- Sigmoid שמוגדרת כך: f(x) = 1/(1+e-x) ומה שפונקציה זו מחזירה זה בעצם ה- Output של אותו נוירון.

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

לאחר שלב הלמידה, לצורך בדיקת הרשת, הגדרנו Threshold חיצוני לרשת, שעבור כל Output שהרשת הוציאה, בדקנו אם הוא עבר את ה- Threshold הזה ולפי זה החלטנו אם ה- Output שהרשת הוציאה הוא החלטה על נצחון ל- X או לא. את ה- Threshold קבענו להיות האמצע בין הייצוג של "נצחון ל- X" לבין הייצוג של "לא ניצחון ל- X" במאגר הנתונים, כלומר במקרה הנתון ה- Threshold יקבע ל- 0.5.

 

הלמידה של הרשת תתבצע בעזרת אלגוריתם Back-Propagation שנלמד בכיתה, עם Eta = 0.1 כפי שהוגדר.

 

תוצאות:

את ההרצות עשינו על המון קונפיגורציות שונות של הרשת.

הפרמטרים והערכים אותם קינפגנו הם:

*) מספר השכבות ברשת – /31/2 (עבור 3 שכבות ביצענו רק חלק מהקומבינציות המתוארות)

*) מספר נוירונים בכל שכבה – /355/10/15/20/25/30

*) מספר המקרים מתוך מאגר הנתונים איתם המערכת תלמד – Start-End: 400/600/800, Random: 400

 

בהתחלה הרצנו את כל הקונפיגורציות כאשר תנאי העצירה שלנו ללמידה הוא כאשר הרשת יודעת לזהות את כל מקרי ה- Training, כלומר אחוז השגיאה מגיע ל- 0 עבור מקרים אלה. אך עבור רשתות עם קצת נוירונים (למשל שכבה אחת עם 5 נוירונים) ראינו שהרשת לא מצליחה להגיע למצב שהיא יודעת לזהות את כל מקרי ה- Training ותנאי עצירה נוסף ששמנו היה חסם עליון של 5000 על מספר ה- Epochs. בריצה זו, שמנו לב שאומנם הרשת לא הגיעה למצב של אפס אחוז שגיאה ב- Training-set אך בהרצת ה- Test-set גילינו שרשת זו הגיעה לאחוז שגיאה קטן בהרבה מרשתות עם יותר נוירונים אשר הגיעו תוך בערך 200 Epochs למצב שבו הן מסווגות נכון את כל מקרי ה- Training והפסיקו את הלמידה. בשלב זה הבנו שאכן השיקול שלנו לכך שה- Output של הרשת בשלב הלמידה לא יהיה בינארי היה נכון, מכיוון שזו הסיבה שגרמה לרשת בעצם להמשיך ללמוד ולהשתפר גם אחרי שכבר הגיעה למצב יציב לגבי זיהוי ה- Training-set ולכן הרשת שרצה הרבה יותר Epochs ידעה לסווג את כל ה- Test-cases הרבה יותר טוב.

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

 

בין הריצות עם גודל ה- Training-set השונה, כמובן שככל שהגדלנו את כמות המקרים איתם למדנו, הרשת הצליחה ללמוד בצורה טובה יותר ולהגיע לאחוז שגיאה נמוך יותר גם עבור מקרי ה- Test-set מכיוון שהמערכת ראתה הרבה יותר מקרים ונשאר לה להכליל עבור פחות מקרים, ולכן זה היה צפוי שזה מה שיקרה (עשינו זאת מכיוון שריצה עם Training-set בגודל 400 נתנה תוצאות לא טובות, כלומר אחוז שגיאה גבוה עבור ה- Test-set).

אך הדבר היותר מעניין היה שבריצה בה ה- Training-set היה בגודל 400, אך הוא נבחר רנדומלית מתוך הקובץ, קיבלנו תוצאות טובות בהרבה מאשר הריצות בהן בחרנו 400 בצורה של 200 מההתחלה ו- 200 מהסוף. ההבנה שלנו לכך היא שהמקרים בקובץ מסודרים באיזשהו סדר שבו מקרים דומים מופיעים קרוב אחד לשני (למשל שמנו לב ש- 78 המקרים הראשונים במאגר הנתונים מייצגים כולם לוח אשר בו הניצחון ל- X הוא ע"י מילוי השורה העליונה), ולכן קרה מצב שבו הרשת למדה 200 מקרים מההתחלה ו- 200 מהסוף שביניהם היו כל מיני מקרים דומים, ואת כל 558 המקרים שבאמצע הקובץ, הרשת לא ראתה כלל, כאשר אלה מקרים שרובם כנראה לא דומים לאלה שהרשת כן למדה, ולכן ההכללה הייתה קשה ונתנה אחוזי שגיאה מאוד גבוהים. כאשר 400 המקרים נבחרים בצורה רנדומלית מתוך מאגר הנתונים, המקרים אותם הרשת תלמד יהיו הרבה יותר מפוזרים בתוך כל 958 המקרים, ובכך הרשת תראה הרבה מקרים שונים ומגוונים, וההכללה תהיה הרבה יותר קלה עבור כל המקרים שלא נלמדו ואינם מתוך ה- Training-set.

לכן, נראה את הגרפים רק עבור התוצאות הטובות ביותר שקיבלנו, שזה המקרה בו ה- Training-set היה בגודל 400 אך נבחר רנדומלית (מתוך הנחה שלמידה עם 400 מקרים טובה יותר מלמידה עם 800 מקרים שגם נתנה תוצאות טובות).

 

את כל תוצאות הביניים (קבצי הפלט והקלט) ניתן למצוא בקישור הבא: InputsOutputs.zip

 

תחילה נראה את הטבלאות והגרפים של אחוז השגיאה הסופית של ה- Training/Test/All Sets עבור כל N.

(השורה שמסומנת בתכלת זו השורה שבה קיבלנו שגיאה מינימלית)

כל הגרפים הם עבור המקרה בו הלמידה נעשתה עם 400 מקרים רנדומלים מתוך מאגר הנתונים.

הנתונים במלואם נמצאים בקובץ האקסל - Exercise4_ErrorPerN.xls

 

 

רשת נוירונים עם שכבה חבויה אחת

 

1 Layer

N

Train

Test

All

5

5.50%

14.16%

10.54%

10

0.00%

11.29%

6.58%

15

0.00%

4.84%

2.82%

20

0.00%

2.87%

1.67%

25

0.00%

2.15%

1.25%

30

0.00%

1.25%

0.73%

35

0.00%

2.15%

1.25%

 

 

 

 

רשת נוירונים עם שתי שכבות חבויות

 

2 Layers

N

Train

Test

All

5

1.75%

4.84%

3.55%

10

0.00%

5.20%

3.03%

15

0.00%

3.94%

2.30%

20

0.00%

2.51%

1.46%

25

0.00%

1.97%

1.15%

30

0.00%

1.43%

0.84%

35

0.00%

3.41%

1.98%

 

 

 

 

כעת נראה את הטבלאות והגרפים של אחוז השגיאה של ה- Training/Test/All Sets בכל Epoch עבור ה- N שנתן את השגיאה הנמוכה ביותר במקרה של שכבה חבויה אחת ובמקרה של שתי שכבות חבויות (בשני המקרים קיבלנו ש- N=30 נותן את השגיאה הנמוכה ביותר).

גם פה כל הגרפים הם עבור המקרה בו הלמידה נעשתה עם 400 מקרים רנדומלים מתוך מאגר הנתונים.

בגרפים הראנו את אחוז השגיאה רק עד Epoch 700 כדי שיהיה יותר ברור, מכיוון שאחרי 700 כבר אין הרבה שינויים.

הנתונים במלואם נמצאים בקובץ האקסל - Exercise4_Epochs.xls

 

רשת נוירונים עם שכבה חבויה אחת

 

1 Layer, 30 Hidden Neurons Per Layer

Epoch

Error- Training Set

Error- Test Set

Error- All Sets

0

30.50%

29.39%

29.85%

50

6.75%

13.80%

10.86%

100

1.50%

6.27%

4.28%

500

0.00%

1.79%

1.04%

1000

0.00%

1.43%

0.84%

3000

0.00%

1.43%

0.84%

5000

0.00%

1.25%

0.73%

 

 

 

רשת נוירונים עם שתי שכבות חבויות

 

2 Layers, 30 Hidden Neurons Per Layer

Epoch

Error- Training Set

Error- Test Set

Error- All Sets

0

35.75%

33.69%

34.55%

50

3.25%

9.32%

6.78%

100

0.25%

2.51%

1.57%

500

0.00%

1.79%

1.04%

1000

0.00%

1.61%

0.94%

3000

0.00%

1.43%

0.84%

5000

0.00%

1.43%

0.84%

 

 

 

 

 

מסקנות:

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

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

3) למדנו שעבודה עם נוירוני Output מסוג Sigmoid אשר לא כופים עליהם ערך "תוצאה חוקית" (ע"י Threshold) בשלב הלמידה, אלא אך ורק בשלב הרצת ה- Test-sets יכול לשפר את יכולת ההכללה של רשת הנוירונים. זאת ניתן להסביר ע"י כך שבתהליך הלמידה (Back-propagation) גם כאשר Training-set כביכול היה נותן "תוצאה חוקית" נכונה (אשר הייתה גורמת לאי ביצוע Back-propagate על השגיאה אשר במקרה זה הייתה 0), במידה ולא כופים "תוצאה חוקית", ניתן יהיה עדיין להתחשב בשגיאה "הקטנה" ולבצע Back-propagate עליה, ובכך לגרום לעוד תיקון ברשת.

4) דבר נוסף שגילינו הוא שעל מנת שהרשת תלמד לכדי יכולת להכליל את הזיהוי של המקרים הרצויים, חשוב שה- Training-set יהיה מגוון ויכלול כמה שיותר מקרים "שונים" של מקרים רצויים. למשל, בדוגמא שלנו, חשוב לשים לב ששני לוחות "שונים" בהם X מנצח ע"י מילוי השורה העליונה, נחשבים פחות "שונים" (למטרת למידה) מאשר שני לוחות בהם X מנצח בדרך שונה בכל אחד. זאת משום שהמערכת אמורה ללמוד לזהות בראש ובראשונה את שמונת האפשרויות לניצחון של X, ורק לאחר מכן  לפתח יכולות זיהוי/סינון טובות יותר.