הקדמה

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

(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

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

הקדמה

מהו PCA

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

מדוע PCA משפר ?

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

תוצאות

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

הפקת ערך, יש לך שאלה, מצאת טעות, נשמח לדעתך:

הקדמה

מהו PCA

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

מדוע PCA משפר ?

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

תוצאות

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

Share this:

הפקת ערך, יש לך שאלה, מצאת טעות, נשמח לדעתך: