Ori Cohen

Apr

2019

למידה עמוקה על גרפים

מיועד ל- מטיבי לכת (כתבה מאוד טכנית)

נכתב על ידי Ori Cohen

מהם גרפים והיכן הם מופיעים

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

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

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

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

למידה עקיפה

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

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

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

למידה מתוך מבנה הגרף

למידה מתוך מאפיינים שבנויים ידנית, למרות הצלחתה היחסית, לא יכולה להיות השיטה הטובה ביותר. דוגמה לתהליך מסוג זה אנחנו יכולים לראות בהתפתחות הלמידה העמוקה על תמונות. בעבר הרחוק (בערך עד 2012) מעבר לשימוש ברשתות נוירונים רגילות (Feed-Forward Networks), הדרך היחידה לשפר למידה על תמונות הייתה ע”י שינויים ידניים שנעשו לתמונות, בין אם שינויים לתמונות שהוכנסו ללמידה ובין אם פיצ’רים שחושבו על התמונות והוכנסו לרשתות בנוסף לתמונות עצמן. קפיצת המדרגה הגדולה בלמידה על תמונות הייתה כאשר הכניסו למשחק רשתות שיודעות גם ללמוד את הפיצ’רים האופטימליים עבור הנתונים, רשתות שכיום ידועות בשם רשתות קונבולוציה.

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

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

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

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

קונבולוציות על גרפים Graph Convolutional Network

בשנת 2017 הוציאו שניים מהמוחות המבריקים ביותר בתחום למידת המכונה על גרפים, תומס קיפף ומקס וולינג, את אחד מהמאמרים בעלי ההשפעה הרחבה ביותר בתחום, Semi-Supervised Classification with Graph Convolutional Networks. במאמר זה הציגו לראשונה השניים את מה שהם כינו “רשתות קונבולוציה על גרפים”, רשתות שיכולות ללמוד תבניות בין קודקודים שונים באופן דומה לקונבולוציות על תמונות. השניים הציעו את המבנה הבא לשכבה אחת ברשת שלהם:

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

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

למעשה מחשב עבורנו את אוסף הפילטרים הפשוטים יותר, מה שמאפשר לנו לחשב בשכבה זו צירופים של פילטרים אלו על מנת ליצור מבנים מורכבים יותר.

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

תוצאות

מעבר לתאוריה היפה, למבנה זה גם תוצאות מרשימות במיוחד.

במאמר, מציגים את רשת בעל שתי שכבות שמצליחה ללמוד את החלוקה שמוצגת בצד ימין מתוך 5% מהתוויות בלבד (על Cora dataset שהינו מאגר נתונים במבנה גרף של מאמרים מדעיים וקשרי ציטוטים ביניהם). למעשה, הרשת הצליחה לזהות קודקודים (ז”א מאמרים מדעיים) דומים והניחה שהם מקבלים סיווג דומה למעט הקודקודים עליהם היה לה מידע.

לקוח מ https://arxiv.org/pdf/1609.02907.pdf

במאמר משווים הכותבים את המאמר שלהם לשש מהשיטות הקיימות לסיווג של קודקודים:

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

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

קישורים

Jan

2019

AdaNet – איך לומדים איך ללמוד

מיועד ל- מתחילים (כתבה קצת טכנית)

נכתב על ידי Ori Cohen

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

אופטימיזציה של מודלים

לאורך שנים פיתחו שיטות היוריסטיות רבות למצוא את מודל זה, אך באופן כללי כולן אומרות אותו דבר:

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

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

כלומר, כמו כל בעיה שעליה אנו עובדים במדעי הנתונים – אם אנחנו לא יודעים לפתור את הבעיה ננסה להשתמש בלמידת מכונה כדי לפתור אותה…

למידת מכונה מאפטמת (מיטיבה) למידת מכונה

גוגל, במאמר פורץ דרך, פיתחו מערכת חדשה בשם AdaNet שמשתמשת בכוח של למידת מכונה כדי לבנות מודלים אופטימליים. המעלה הגדולה ביותר של המערכת – היא מבוססת קוד פתוח ומשתלבת באופן חלק יחד עם TensorFlow, המערכת הקיימת של גוגל לכתיבת מודלים ללמידה עמוקה.

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

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

ע”י שילוב מודלים קטנים, AdaNet יכולה ללמוד מודלים גדולים ומורכבים בצורה אופטימלית.

לקוח מ introducing-adanet-fast-and-flexible

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

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

תוצאות מדווחות

התוצאות של מודל זה מרשימות במיוחד. ע”י שימוש ברשתות נוירונים פשוטות (Fully-connected feed forward) המערכת הצליחה ללמוד מודלים שמשתווים, או אפילו עולים עליהם בביצועיהם, בדר”כ ע”י שימוש בפחות פרמטרים מהמודלים הטובים ביותר שבנויות מאותו סוג רשת.

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

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

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

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

צלילה קלה לקוד

עבור המעוניינים, את הקוד המלא למערכת (כולל הוראות התקנה ודוגמות) ניתן למצוא ב- https://github.com/tensorflow/adanet .

ניתן להתקין בקלות:

$ pip install adanet

ולהשתמש בזה (כקופסה שחורה) גם די בפשטות:

head = tf.contrib.estimator.multi_class_head(10)

estimator = adanet.Estimator(
    head=head,
    subnetwork_generator=CNNGenerator(),
    max_iteration_steps=max_iteration_steps,
    evaluator=adanet.Evaluator(
        input_fn=adanet_input_fn,
        steps=None),
    adanet_loss_decay=.99)

כאשר head מגדיר שכבת ה-softmax במוצא הרשת המשולבת. (למשל 10 מחלקות)

CNNGenerator הינה ירושה של המחלקה adanet.subnetwork.Generator שמחזירה כמה רשתות מועמדות לכל איטרציה ומבוססת על מחלקה שיורשת מ-adanet.subnetwork.Builder

ההפעלה עצמה מתבצעת ע”י קריאה ל-

tf.estimator.train_and_evaluate()

למעשה, גם את הקופסה השחורה הזו ניתן להבין די בקלות, במיוחד עבור אלו שמכירים High level APIs כדוגמת Keras. הממשק Estimator מתפקד כמו כל פונקציית fit אחרת, ומתאים את הפרמטרים בהתאם לפונקצית המחיר, שבמקרה זה ניתנת בפרמטר evaluator. הייחוד בקריאה זו לממשק הוא שאנו נותנים לרשת לבחור את תתי הרשתות בצורה דינמית מתוך האופציות שאנו מספקים בפונקציה subnetwork_generator. למי שמעוניין, ממשק זה נמצא בשימוש גם באופן כללי ב- Tensorflow וניתן ללמוד עליו כאן.

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

Nov

2018

ניתוח מתמטי לאלגוריתם PCA

מיועד ל- מטיבי לכת (כתבה מאוד טכנית)

נכתב על ידי Ori Cohen

הקדמה

“בתוך ערימות הנתונים האלה מוסתר ידע שיכול לשנות את חייו של מטופל, או שיכול לשנות את העולם”.

(Atul Butte, Stanford School of Medicine)

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

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

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

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

הפשטה – על המידע המתקבל להיות פשוט/מובן יותר מהמידע המקורי.
רלוונטיות – על התהליך להדגיש את המידע אותו אנו מנסים לחלץ.
עקביות – על התהליך להיות עקבי ביחס למידע המקורי, על מנת שיהיה ניתן להסיק מסקנות בעלות משמעות.

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

תהליך ה-PCA, בו אנו נשתמש, פותח במקור בשנת 1901 ע”י קרל פירסון, עוד לפני שהיו מחשבים שיכלו לבצע את החישובים הדרושים בצורה יעילה. התורה פותחה שוב באופן עצמאי ע”י הוטלינג בשנת 1933.

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

כעת השאלה המתבקשת היא כיצד תהליך שכזה עוזר ללמידת מכונה.

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

מהו PCA

תהליך ה-PCA הוא מהתהליכים הפופולריים ביותר להורדת ממדים בנתונים.

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

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

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

למה זה מעניין אותנו?

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

בדקנו את תוצאות הפעלת התהליך על בעיית למידה קלאסית בתחום סיווג תמונות, סט המידע MNIST, שמורכב מאלפי תמונות של ספרות שנכתבו בכתב יד שעלינו לזהות. במקרה שלנו במקום תמונות בגודל 21X21 אימנו את המודל על קלטים בגודל 50 בלבד (בעקבות הפעלת ה-PCA).

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

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

ניתן לראות בבירור כי הן הדיוק והן הזמן שלוקח למודל להגיע לכל רמת דיוק משתפר משמעותית בעקבות תהליך ה-PCA.

מדוע PCA משפר ?

השאלה שבאמת מעניינת אותנו עכשיו היא למה זה קורה?

על מנת לענות על שאלה זו עלינו לחשוב על בעיית למידת מכונה כבעיית חיפוש.

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

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

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

ניסוח פורמלי של השיטה

הגדרה: משתנה מקרי הוא התאמה של ערך מספרי לאירועים אפשריים במרחב ההסתברות. פורמלית, משתנה מקרי $X$ מעל מרחב הסתברות $\Omega$ הוא פונקציה $X:\Omega \rightarrow \Re$ .

הגדרה: וקטור מקרי $X$ הוא וקטור $p$ -ממדי המקיים כי לכל $1\leq i\leq p$ : $X_i$ הוא משתנה מקרי.

הגדרה: מטריצת שונויות היא מטריצה $V$ מגודל $pxp$ בה:

$V_ij=cov(X_i,X_j )=E[X_i X_j ]-E[X_i ]E[X_j ]$

הגדרה: גורם עיקרי של וקטור מקרי $X$ הוא משתנה מקרי $({\alpha \in }\Re ^{p})z=\alpha \cdot x$ כך ש- $Var(z)$ מקסימלי תחת האילוץ $\left \| \alpha \right \|=1$ .

הערה: למרות שבדר”כ ניקח את הנורמה האוקלידית (כלומר, נדרוש כי $\alpha \cdot \alpha =1$ ), ניתן להחליף זאת בנורמות אחרות (נורמת מקסימום, נורמת סכום וכו’).

מסקנה: המקדמים $\alpha _k$ של הגורמים העיקריים $z_k$ ( $1\leq k\leq p$ ) הם הווקטורים העצמיים של מטריצת השונויות $V$ , המתאימים לערכים העצמיים $\lambda _k$ .

הגדרה: התפלגות D עם פרמטרים $(a_1,a_2,...)$ היא משפחת פונקציות המתאימות לכל מאורע מהצורה $X<c$

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

$P(X<c|a_1,a_2...)$

סימון: אם המשתנה המקרי $X$ מתפלג לפי ההתפלגות עם הפרמטרים $(a_1,a_2,...)$ נסמן:

$X\sim D(a_1,a_2,...)$

הגדרה: סדרת התפלגויות $D$ עם הפרשים $(\triangle a_1,\triangle a_2,...)$ הינה אוסף של התפלגויות

$D_i=D_i(a_{1}^{i},a_{2}^{i},...), 1\leq i\leq N$

כך שמתקיים:

$a_{j}^{i}=a_{j}^{0}+(i-1)\Delta a_j$

כלומר, בכל שלב מוסיפים לכל פרמטר את ההפרש המתאים.

הגדרה: רכיב עיקרי יקרא מסדר $k$ אם הע”ע המתאים לו הינו ה- $k$ בגודלו.

סימון: את אוסף הרכיבים מסדר $k$ של סדרת ההתפלגויות $D=D(\Delta a_1,\Delta a_2,...)$ נסמן ע”י:

$PC_k(D)$

כעת, באופן פורמלי השיטה שלנו מורכבת מהשלבים הבאים:

נקבע את התפלגות בסיסית $D_0(a_1,a_2,...)$ . במקרה שלנו ההתפלגות הבסיסית הינה ההתפלגות הנורמלית הסטנדרטית $N(0,1)$
נקבע את ההפרשים $(\bigtriangleup a_1,\bigtriangleup a_2,...)$ . במקרה שלנו נרצה לשנות את סטיית התקן של ההתפלגות.
נייצר סדרת התפלגויות $\left \{ D_i \right \}_{i=1}^{N}$ כאשר מספר גדול מספיק. למעשה אנו משנים את ענן הנקודות אותם אנו דוגמים על מנת לראות את ההשפעה של הפרמטרים על התוצאות לאחר הפעלת תהליך ה-PCA.
עבור כל התפלגות $D_i$ נחשב את הגורמים העיקריים
נשרטט בדיאגרמת פיזור (scatter plot) את האוסף $\left \{ PC(D_i)) \right \}_{i=1}^{N}$ עבור הגורמים העיקריים הראשונים. אם נזכר בדוגמה של למידת המכונה, נשים לב כי הפיזורים הללו הם למעשה מרחב הקלטים האפשריים של מודל הלמידה שלנו.

תוצאות

לצורך כך נייצר וקטורים עצמיים מתוך וקטור מקרי באורך 6 בו כל קואורדינטה מתפלגת בהתפלגות נורמלית.

כעת נבצע 100 חזרות של השלבים הבאים:

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

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

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

לדוגמה, כל נקודה בגרף הראשון מייצגת את אחד מהגורמים העיקריים הראשונים (כלומר, כל אחד מהם מתאים לערך העצמי הגדול ביותר שנובע מהתהליך ה-PCA עבור ההתפלגות ממנה הוא נוצר) ואנו יכולים לראות שבעוד השינוי שחוללנו בהתפלגות הווקטור המקרי שינתה את הערכים שמופיעים בקואורדינטות $y,z$ בטווח רחב ( $[-10,10]$ ) הערך בציר ה- $x$ כמעט ולא משתנה.

נשים לב לכמה דברים:

בשני הממדים הראשונים אנו יכולים לראות כי השינויים בתוצאות התהליך נמצאים אך ורק על מישורים, כלומר במונחים של בעיות חיפוש, חסכנו לעצמנו חיפוש במרחב תלת ממדי וכעת אנו צריכים לחפש אך ורק על מרחב דו-ממדי.
שני הממדים הראשונים מייצגים את רוב המידע שנמצא בנתונים, כאשר אנו מגיעים לרכיב השלישי הערכים שלו הם כבר בסדרי גודל של $10^{-2}$ , כלומר חסרי מידע מועיל על הנתונים המקוריים.

סיכום ומסקנות

אז מה אנו יכולים להסיק מכל זה?

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

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

ניתן לראות את תהליך ה-PCA במגוון רחב של שימושים, החל מניתוח תמונות וכלה בסיווג של תנועות בני אדם בהתבסס על חיישנים שונים. רשימה ארוכה של שימושים ניתן למצוא באתרים הבאים:

https://www.intechopen.com/books/principal-component-analysis-engineering-applications

https://www.intechopen.com/books/principal-component-analysis-multidisciplinary-applications