Uri.itai

רשתות קונבולוציה על יריעות

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

נכתב על ידי Uri.itai

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

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

אבל מה קורה בבעיות בהן מרחב הנתונים אינו אוקלידי ?

מה לא אוקלידי ?

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

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

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

תודה ל AugPi

ישנן עוד מגוון דוגמאות מעולמות תוכן נוספים כגון רשתות חברתיות, דגימות מסנסורי IOT וכו’

קצת מתמטיקה

כדי להתקדם נצטרך לדבר על שני מונחים מתמטיים:

המונח הראשון הוא יריעה גאומטרית.

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

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

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

 

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

אז איך עושים קונבולוציה על יריעה ?

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

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

ז”א האם מתוך שמיעת התיפוף ניתן לשערך את צורתו הגיאומטרית ?

 

או אותו דבר לגבי פילים:

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

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

לסיכום

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

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

1) לרשתות על יריעה לא אוקלידית:

Geometric deep learning: going beyond euclidean data

MM Bronstein, J Bruna, Y LeCun… – IEEE Signal …, 2017 – ieeexplore.ieee.org

2) לפלסיאן של גרף:

 Godsil, C.; Royle, G. (2001). Algebraic Graph Theory, Graduate Texts in Mathematics. Springer-Verlag.

3) לפלס בלטרמי

Flanders, Harley (1989), Differential forms with applications to the physical sciences, Dover, ISBN 978-0-486-66169-8

Posted by Uri.itai in deep