האם עתיד האחסון נמצא ב-DNA?

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

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

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

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

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

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

כדי לממש אנליזה בין-פרוצדורלית אנו נדרשים לגרף קריאות (call graph) מדויק, אך אלגוריתמים לבנייה של גרף קריאות חייבים לתעדף בין דיוק ועלות. שיטות רבות לקירוב נאות (sound) של גרף קריאות מסובכות וסובלות מקושי לנתח תכניות גדולות, עקב השיטה בה הם עושים שימוש להסקת הטיפוסים (type inference), המבוססת על גרסה כלשהי של שיטת points-to. עובדה זאת מאלצת שימושים הדורשים קירוב נאות לגרף הקריאות עבור תכניות גדולות (למשל, הסרת פרוצדורות לא נגישות) לעשות שימוש באנליזות פשטניות יותר, כמו למשל, אנליזת היררכיית טיפוסים (Class Hierarchy Analysis). שיטות פשטניות אלה אינן נאותות עבור שפות דינמיות כדוגמת פייתון (Python) וג'אווה-סקריפט (JavaScript), אשר נעשו פופולריות במיוחד בשנים האחרונות.

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

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

כפל בין שני מספרים הוא אחד הפעולות החישוביות הבסיסיות ביותר, עם זאת הסיבוכיות האמיתית של החישוב אינה ידועה לנו. בשנת 2019 הארווי וואן-דר הובן הציגו אלגוריתם המחשב כפל בין שני מספרים בני $n$ ספרות במעגל בוליאני בגודל $O(n\text{log}n)$. בהרצאה זו נוכיח שתחת ההנחה שהשערה מרכזית בתחום שנקרא "קידוד ברשתות" היא נכונה, כל מעגל בוליאני בדרגה קבועה המחשב כפל בין שני מספרים חייב להיות בגודל לפחות $\Omega(n\text{log}n)$, ובכך אנחנו מיישבים כמעט לגמרי את שאלת הסיבוכיות של פעולת הכפל (ומוכיחים שכפל אכן יותר קשה לחישוב מחיבור 🙂).

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

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

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

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

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

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

אסקור בקצרה:

•    הגדרת התחום.
  

•    מה נושאי המחקר המובילים כיום.
  

•    נושאים בהם עסקתי.
  

•    רעיונות לשאלות שיכולות להוביל לתזה או עבודת גמר
  

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

אקנח בדוגמה למאמר שכתבתי שנולד מבעיה שבאה "בשטח" בנושא Data Reduction.

אלו דוגמאות לכנסים מובילים בתחום:

· FAST - USENIX Conference on File and Storage Technologies

· HotStorage - Hot Topics in Storage and File Systems

· IEEE Cloud - IEEE International Conference on Cloud Computing

· SYSTOR - ACM International Systems and Storage Conference

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

HP Mosaic is an algorithm that generates a potentially unlimited number of unique graphic designs based on a fixed number of base patterns (images with complex patterns). This base pattern is the central element of the process. The algorithm scales, rotates and changes colors from a base pattern and can create millions of variations from a single complex base image. This project tries to create those base patterns with machine learning and help designers create unique jobs.

תוכנית המפגש:

11:00 - 11:30 : עדי שרייבמן - שיחה על הסמינר. הצגת תחומי המחקר שלו.

11:30 - 12:30 : ראיד סעאבנה - הצגת תחומי מחקר.

תוכנית המפגש:

11:00 - 11:25 : ראיד סעאבנה - הצגת תחומי מחקר.

11:30 - 11:50 : ירון הובר - ידבר על המחקר שלו בתואר השני ועל התהליך.

11:55 - 12:15 : רז סרויה - ידבר על הפרויקט שלו בתואר השני ועל התהליך.

12:20 - 12:45 : שראל כהן - הצגת תחומי מחקר.

תוכנית המפגש:

11:05 - 11:30 : דיון חופשי.

11:30 - 12:05 : עדי שרייבמן - שיחה על הסמינר. הצגת תחומי המחקר שלו.

12:05 - 12:45 : שירי מורשטיין תדבר על המחקר שלה בתואר שני ועל התהליך.