פרויקטי גמר - הנדסת מחשבים - עיבוד נתונים וגרפיקה תש"פ

801  Data Fusion of strings and applications to movies & scripts

היתוך מידע של מחרוזות ושימושיו בסרטים

שם המנחה: פרופ' צביקה לוטקר וד"ר רן גלס

אחראי אקדמי: פרופ' צביקה לוטקר

הרקע לפרויקט:

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

מטרת הפרויקט:

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

תכולת בפרויקט:

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

דרישות:

  • אלגוריתמים 1

מקורות:

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael E. Saks:
Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time. FOCS 2018: 979-990

802  Differentially Private Clustering Algorithms

אלגוריתמי קלאסטרינג פרטיים

שם המנחה: Or Sheffet

אחראי אקדמי: Or Sheffet

הרקע לפרויקט:

Differential privacy has been established in recent years as the "de-facto" gold standard of privacy preserving data analysis. In this project the students are expected to read, understand, implement and test a differentially private algorithm for locating a cluster / multiple clusters in a given dataset of points in the Euclidean space.

מטרת הפרויקט:

This project is centered around the problem of private data clustering. The students are expected to implement randomized algorithms that deal with clustering, including: noisy counting, above-threshold, locally-sensitive hashing, and randomly chosen axes.

Furthermore, the students are expected to test and compare the performance of said algorithms over multiple datasets.

Academically, the goal of the project is to have the students acquainted with differential privacy (DP) and the high-level ideas of differential privacy, as well as the technical difficulties that arise from the promise of DP.

Practically, the goal is to publish the project's code online, available for researchers world-wide.

תכולת בפרויקט:

The project's main focus is on understanding and implementing a scientific paper in differential privacy.

The project is based on 3 stages:

  1. reading and understanding existing work,
  2. implementation of algorithms in code and
  3. testing empirical performance over synthetic / real-life data.

The main focus of the project is the 1-cluster algorithm of Nissim and Stemmer, composed of multiple building blocks.

The students are required to implement each of these subroutines and then wrap it all together in an algorithm of bounded privacy lose (i.e. a (\epsilon,\delta)-DP algorithm).

דרישות:

  • Advanced algorithms
  • Probability / statistics --- a significant component of the course is centered on randomized algorithms
  • Differential privacy as a co-requisite.

מקורות:

803  Differentially Private Linear Regression

רגרסיה ליניארית פרטית

שם המנחה: Or Sheffet

אחראי אקדמי: Or Sheffet

הרקע לפרויקט:

Differential privacy has been established in recent years as the "de-facto" gold standard of privacy preserving data analysis. In this project the students are expected to read, understand, implement and test a suite of differentially private algorithms for the classic problem of linear regression, and test performance under the classical Ordinary Least Squares (OLS) model.

מטרת הפרויקט:

This project is centered around the problem of private linear regression. The students are expected to implement randomized algorithms that deal with a single and multiple regressions. Furthermore, the students are expected to test and compare the performance of said algorithms over multiple datasets.

Academically, the goal of the project is to have the students acquainted with differential privacy (DP) and the high-level ideas of differential privacy, as well as the technical difficulties that arise from the promise of DP. Practically, the goal is to publish the project's code online, available for researchers world-wide.

תכולת בפרויקט:

The project's main focus is on understanding and implementing a scientific paper in differential privacy.

The project is based on 3 stages:

  1. reading and understanding existing work
  2. implementation of algorithms in code
  3. testing empirical performance over synthetic / real-life data.

The project is centered around implementation of multiple different algorithms for linear regression: output perturbation, input perturbation, stochastic gradient descent, Analyze Gauss and the Johnson-Lindenstrauss transform.

דרישות:

  • Advanced algorithms
  • Probability / statistics --- a significant component of the course is centered on randomized algorithms
  • Differential privacy as a co-requisite.

מקורות:

804  Parallel Computation of Distance Maps

חישוב מקבילי של מפות מרחקים

שם המנחה: פרופ' אופיר וובר

אחראי אקדמי: פרופ' אופיר וובר

הרקע לפרויקט:

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

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

מטרת הפרויקט:

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

תכולת בפרויקט:

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

דרישות:

  • עיבוד דיגיטלי של גיאומטריה (83-656). ניתן לקחת במקביל.
  • מומלץ (לא חובה) - חישוב מקבילי ב-GPU (83-920). ניתן לקחת במקביל.
  • מומלץ (לא חובה) - אופטימיזציה והבנה של צורות (83-641). ניתן לקחת במקביל.
  • יכולת תכנות טובה.
  • יכולת עבודה עצמאית והגדלת ראש.

מקורות:

http://www.eng.biu.ac.il/~weberof/Publications/PMM/SIGGRAPH08.zip

805 Geometric Deep Learning

למידה גיאומטרית עמוקה

שם המנחה: פרופ' אופיר וובר
אחראי/ת אקדמי/ת: פרופ' אופיר וובר

הרקע לפרויקט:

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

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

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

מטרת הפרויקט:

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

תכולת הפרויקט:

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

ראשית, המודלים התלת מימדיים ימופו לתחום שטוח תוך שימוש בשיטות גאומטריות מתקדמות תוך שימוש בחבילות תוכנה גרפיות וחישוביות מסחריות (כמו למשל Matlab, Autodesk Maya, CGAL).

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

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

בתום תהליך הלמידה והאימון, המודל יופעל על צורות חדשות.

קורסי קדם:

• עיבוד דיגיטלי של גיאומטריה (83-656). ניתן לקחת במקביל.
• אופטימיזציה והבנה של צורות (83-641). ניתן לקחת במקביל.

דרישות נוספות:

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

מקורות:

http://geometricdeeplearning.com/

/*-->*/ 806 Metric Parameterization

פרמטריזציה מטרית

שם המנחה: פרופ' אופיר וובר
אחראי/ת אקדמי/ת: פרופ' אופיר וובר

הרקע לפרויקט:

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

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

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

מטרת הפרויקט:

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

תכולת הפרויקט:

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

הפרויקט ידרוש מימוש של אלגוריתם מורכב בתוכנה תוך שימוש בחבילות תוכנה גרפיות וחישוביות מסחריות כמו למשל Matlab, Autodesk Maya, CGAL.

בסיס האלגוריתם מתואר במאמר 2) ברשימת המקורות. בפרויקט נשנה את האלגוריתם באופן שיוביל למימוש יעיל יותר מזה המוצע במאמר ע"י מימוש אופטימיזציה בטכניקת Sequential Quadratic Programming.

קורסי קדם:

  • חובה - עיבוד דיגיטלי של גיאומטריה (83-656).
  • מומלץ (לא חובה) - אופטימיזציה והבנה של צורות (83-641).
  • מומלץ (לא חובה) - עיבוד דיגיטלי של גיאומטריה 2 (83-633).

          דרישות נוספות:

  • תכנות Matlab ו C++.
  • יכולת עבודה עצמאית והגדלת ראש.

מקורות:

  1. Polygon mesh processing (book). Botsch, M., Kobbelt, L., Pauly, M., Alliez, P., & Lévy, B. (2010). CRC press.
  2. http://www.eng.biu.ac.il/~weberof/Publications/Metric-Param/Bounded_Distortion_Parametrization_in_the_Space_of_Metrics.pdf

פרויקטים נוספים מומלצים

404 Why are quantum algorithms so efficient?

מדוע אלגוריתמים קוונטיים כה יעילים?

שם המנחה: ד"ר אליהו כהן

אחראי אקדמי: ד"ר אליהו כהן

הרקע לפרויקט:

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

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

מטרת הפרויקט:

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

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

תכולת בפרויקט:

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

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

דרישות:

  • מכניקה קוונטית שימושית
  • מומלץ לקחת במקביל את הקורס חישוב קוונטי

מקורות:

  1. https://link.springer.com/article/10.1007/s10701-010-9452-0
  2. https://advances.sciencemag.org/content/5/4/eaav8370/

601  A web-based tool for analysis of single-cell RNAseq datasets

ממשק לניתוח נתונים גנומיים רב מימדיים של מדידות רנ"א מתאים בודדים

שם המנחה: ד"ר תומר קליסקי

אחראי אקדמי: ד"ר תומר קליסקי

הרקע לפרויקט:

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

מטרת הפרויקט:

בניית יישום רשת (web application) מבוסס python או R להצגת נתונים רב מימדיים של ביטוי גנים מעשרות אלפי תאים על ידי הטלה למרחב דו מימדי בשיטות PCA ו tSNE בהתאם לבחירת המשתמש.

תכולת בפרויקט:

  1. בניית יישום רשת (web application) מבוסס python או R להצגת נתונים רב מימדיים של ביטוי גנים מעשרות אלפי תאים.
  2. הצגת המידע באמצעות הטלה למרחב דו מימדי בשיטות PCA ו tSNE בהתאם לבחירת המשתמש.
  3. סימון תאים המבטאים גן מסויים על פי בחירת המשתמש.
  4. ייצור היסטוגרמה של רמות ביטוי של גן מסויים על פי בחירת המשתמש.
  5. מתן אפשרות למשתמש להגדיל ולהקטין ולסובב את התמונה.
  6. מתן אפשרות למשתמש לסמן קבוצות של תאים לייצר גרף עמודות (bar plot) של ממוצעי רמות ביטוי היסטוגרמות של שלהם עבור גנים נבחרים על פי בחירת המשתמש.
  7. ביצוע שאילתות על חתכים שונים של המידע (למשל, בחירת תת קבוצה של תאים והוצאת רשימת הגנים המאפיינים אותה ביחס לשאר) בהתאם לבחירת המשתמש.

דרישות:

  • עדיפות למסיימי הקורסים "ביג דאטה" ו"ביולוגיה חישובית וביואינפורמטיקה"
  • עדיפות למי שמכיר תכנות בשפת R או Python

מקורות:

  1. Plotly R Open Source Graphing Library (https://plot.ly/r/)
  2. The Jupyter Notebook (https://jupyter.org/)
  3. t-SNE (https://lvdmaaten.github.io/tsne/)
  4. Single-cell transcriptomes from human kidneys reveal the cellular identity of renal tumors, Science 2018 (https://www.ncbi.nlm.nih.gov/pubmed/30093597)

602 Genetic pattern analysis in Immunological repertoires

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

שם המנחה: אילת פרס

אחראי אקדמי: ד"ר גור יערי

הרקע לפרויקט:

We have previously developed efficient computational pipelines for processing antibody repertoire data. Here, we propose to utilize this framework to investigate novel repertoire features related to clonal connectivity across biological compartments (temporal, tissues or cell subsets).

מטרת הפרויקט:

Analyze antibody DNA sequencing datasets. Assess the relevancy of different features on the ability to classify the datasets according to the clinical status of the individuals.

תכולת בפרויקט:

איסוף הנתונים, הכנת מבנה נתונים, ניתוח הנתונים וכתיבת המחקר

דרישות:

  • Big data analysis

מקורות:

  1. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4113560/
  2. https://genomemedicine.biomedcentral.com/articles/10.1186/s13073-015-0243-2