עזרה בתרגיל הבא
שלום,
ניתן לי בקורס באוניברסיטה ואיני מצליחה להתמודד איתו.
אשמח לעזרה:
שלום,
ניתן לי בקורס התרגיל הבא ואיני מבינה מה עושים החל מסעיף 2 והלאה.
אשמח לעזרה.
תודה.שלב חשוב בתרגום אוטומטי הוא התאמה בין טקסטים מקבילים
במשימה הזו, נתונים לנו שני טקסטים בשתי שפות שונות כך שהאחד הוא התרגום של השני. מטרתנו היא
להרכיב מעין מילון המתאים מילים בשפה אחת למילים בשפה השנייה.
ו-”ג'ון אכל תפוח" יותאמו באופן הבא: ”John ate an apple" לדוגמא, המשפטים
מתאים ל-”ג'ון" ”John“ •
מתאים ל-”אכל" ”ate“ •
מתאים ל-”תפוח" ”apple“ •
הערות:
• חלק מהמילים באחת או בשתי השפות עשויות להשאר מיותמות.
• ההתאמה מתבצעת בין מילה אחת למילה אחת בלבד.
• בעיית ההתאמה המוצגת בתרגיל זה היא גרסא מפושטת של בעיית ההתאמה הכללית.
ואחרות) משתמשות בשיטות מתקדמות Google Translate מערכות מתוחכמות יותר (כמו
יותר. למשל, ההתאמה שם נעשית לא רק בין מילים בודדות אלא גם בין ביטויים מרובי
מילים.
• בתרגיל זה אנו מניחים שלכל מילה מתאימה מילה אחת ויחידה. הנחה זו איננה מתקיימת
”bank" במציאות כמובן, שכן למילה עשויים להיות מספר תרגומים בהקשרים שונים (למשל
עשוי להיות מתורגם ל-"בנק" בהקשר אחד ול-”גדה" באחר). עם זאת, הנחה זאת כן
מתקיימת בקירוב בהקשרים מסויימים ועשויה לשפר את הדיוק של ההתאמה.
• ניתן לייצג את בעיית ההתאמה כבעיית זיווג בגרף דו-צדדי. נגדיר גרף דו-צדדי באופן הבא:
• הקודקודים בצד שמאל יתאימו למילים בשפה א' (במקרה שלנו אנגלית).
• הקודקודים בצד ימין יתאימו למילים בשפה ב' (במקרה שלנו עברית).
• נמתח צלעות בין מילים שעשויות להיות תרגומים זו של זו.
אנחנו מעוניינים למצוא זיו וג שמתאים כמה שיותר זוגות מילים שהן אכן תרגום זו של זו. נזכיר שזיווג הוא
תת-קבוצה של צלעות הגרף כך שמכל קודקוד יוצאת לכל היותר צלע אחת.
בתרגיל זה נעסוק בטקסט הפשוט הבא:
עברית אנגלית
Yos s i went on a trip to US י וסי נסע ל-ארה"ב ל-טיול
ב-ביקורו ב-ארה”ב, הוא פגש את דינה
ש-עבדה ב- ני ו י ורק ב-מסעדה
On his visit there, Yos s i met Dina who
worked in a New York restaurant
דינה עברה ל- ני ו י ורק כמה שנים קודם
לכן
She moved to New York a few years
before
שמה של ה-מסעדה היה ארבע העונ ות,
והיא הייתה ממוקמת באיזור מרכזי של
העיר
The name of the restaurant was The
Four Seasons , and it was located in a
central part of town
Yos s i and Dina used to go strolling הזוג נהג לצאת לטיולים בפארק
together in the park
י וסי אהב את ני ו י ורק והחליט להשאר
שם
Yos s i loved New York and deceided
to stay there
אנו מניחים שהטקסטים מתאימים אחד לשני משפט-משפט. כמו כן, אנו מניחים שמיליות בעברית שנכתבות
צמודות למילים אחריהן (כגון, “ל", “כ", “ו" וכו') הן מילים נפרדות. כלומר נתייחס אליהן כאילו יש רווח בינן
לבין המילה העוקבת.
משימתנו בתרגיל זה היא להרכיב מילון אנגלי-עברי של השמות הפרטיים בטקסט הקצר לעיל.
נניח שנתון לנו אלגוריתם שמסמן את השמות הפרטיים בטקסט (מודגשים לעיל). אנו רוצים להתאים כל שם
פרטי לשם פרטי בשפה השנייה שמתאים לו. נבנה את הגרף הדו-צדדי כך שבצד שמאל יופיעו השמות
הפרטיים בעברית (“יוסי", “דינה", “אמריקה", “ניו יורק", “ארבע העונות") ובצד ימין השמות הפרטיים
באנגלית.
שימו לב שכל שם פרטי מופיע פעם אחת בגרף באופן בלתי תלוי במספר הפעמים בהן הוא מופיע בטקסט.
1. בשלב ראשון, נניח שזוג מילים שמופיעות במשפטים מתאימים יכולות להיות תרגום זו של זו. כלומר, אנו
נמתח צלע בין שם פרטי בעברית ושם פרטי באנגלית במשפט המתאים לו. לדוגמא נמתח צלע בין "יוסי"
.”US“- ו ”Yossi" לבין
ציירו את הגרף (קודקודים וצלעות) המתאים לדוגמא לעיל.
2. משימתנו כעת היא למצוא זיווג בעל גודל מקסימלי, כלומר זיווג המכיל את המספר הרב ביותר של צלעות.
נציע אלגוריתם פשוט עבור בעיית הזיווג המקסימלי:
• קלט: גרף דו-צדדי
להיות ריקה S • אתחל את קבוצת הצלעות
• כל עוד יש צלעות בגרף ששני קודקודיהן לא זווגו:
S- בחר צלע כזאת והוסף אותה ל ◦
S • פלט: הקבוצה
. נניח שהקלט לאלגוריתם הוא הדוגמא מסעיף 1
הריצו את האלגוריתם ורשמו את כל הצלעות שנבחרו במהלך הריצה לפי סדר בחירתן, ואת הזיווג .a
המתקבל (הפלט).
הראו עבור הדוגמא מסעיף 1 שעבור בחירה מסויימת של צלעות, האלגוריתם עשוי לסיים את ריצתו .b
ולהחזיר זיווג שאיננו מקסימלי (כלומר, זיווג עבורו יש זיווג אחר המכיל יותר צלעות ממנו).
הראו עבור הדוגמא מסעיף 1 שיש יותר מזיווג מקסימלי אחד בגרף, וממילא שיש זיווגים .c
מקסימליים שאינם נכונים.
3. בסעיף הקודם ראינו שאפילו במקרים בהם האלגוריתם מצליח למצוא זיווג מקסימלי, הוא לא בהכרח מוצא
זיווג שמתאים כל מילה לתרגום שלה.
על מנת ליצור מצב שבו הזיווג שנבחר מתאים מילים לתרגומים שלהם, נשנה מעט את הבעייה לבעיית
הזיווג הממושקל המקסימלי. לכל צלע בגרף ניתן משקל (שיכול להיות כל מספר חיובי). משקל הצלעות נקבע
ע"י אלגוריתם אחר שמספק הערכה ראשונית לגבי הסבירות שמילה אחת תתאים למילה אחרת. המטרה
במקרה זה היא להגיע לזיווג שסכום המשקולות על צלעותיו מקסימלי.
ומשקל נמוך לצלע בין "יוסי" ,”Yossi”- דוגמא: משקול טוב של הצלעות ייתן משקל גבוה לצלע בין "יוסי" ל
.”Dina”- ל
תנו משקל לכל צלע בגרף בסעיף הראשון בצורה כזו שהזיווג שסכום משקלותיו הוא הגבוה ביותר .a
הוא אכן הזיווג הנכון.
נציע אלגוריתם שנותן משקלים לצלעות. משקל צלע בין מילה א' (משפה א') למילה ב' (משפה ב') .b
יהיה מספר הפעמים בהם מילה א' ומילה ב' הופיעו במשפטים מתאימים. חשבו את המשקל של כל
צלע כפי שמתקבל מאלגוריתם זה עבור הטקסט הנתון בראש התרגיל.
הראו שבגרף הממושקל שחושב בסעיף הקודם, הזיווג הנכון (כלומר זה שמתאים לכל מילה את .c
התרגום שלה) הוא אכן זיווג ממושקל מקסימלי (כלומר אין אף זיווג אחר בעל סכום משקלים גדול
ממנו).
נציע אלגוריתם עבור מציאת הזיווג הממושקל המקסימלי: .d
• קלט: גרף דו-צדדי
להיות ריקה S • אתחל את קבוצת הצלעות
• עבור כל קודקוד בצד ימין (עברית) של הגרף בצע:
S- בחר את הצלע בעלת המשקל המקסימלי שיוצאת מקודקוד זה והוסף אותה ל ◦
S • פלט: הקבוצה
ורשמו את כל הצלעות שנבחרו במהלך הריצה b הריצו את האלגוריתם על הגרף הממושקל מסעיף
לפי סדר בחירתן. הראו שהפלט המתקבל איננו התאמה אחד לאחד. כלומר, ישנו קודקוד שנוגע
.S בשתי צלעות מהפלט
על כן הוא מפר את הנחתנו שההתאמה המבוקשת היא אחד לאחד (ראה הערה לעיל).
נציע אלגוריתם אחר: ,d על מנת לתקן את הבעייה שנוצרה בסעיף .e
G • קלט: גרף דו-צדדי
להיות ריקה S • אתחל את קבוצת הצלעות
• עבור כל קודקוד בצד ימין (עברית) של הגרף בצע:
.S- בחר את הצלע בעלת המשקל המקסימלי שיוצאת מהקודקוד והוסף אותה ל ◦
.y- נסמן את הקודקוד בצד שמאל שנוגע בצלע זו ב
.y- את כל הצלעות היוצאות מ G הסר מן הגרף הדו-צדדי ◦
S • פלט: הקבוצה
שימו לב שהפלט של אלגוריתם זה עשוי להיות תלוי בסדר בו עוברים על הקודקודים בצד ימין של
הגרף. לאור זאת, אלגוריתם זה עדיין לא פותר בהכרח את בעיית מציאת הזיווג הממושקל
המקסימלי (למרות שלרוב הוא נותן קירוב ראשוני סביר לבעיה).
הריצו את האלגוריתם פעמיים. בפעם אחת עברו על הקודקודים בסדר כך שעבורו הפלט המתקבל
לא יהיה הזיווג הממושקל המקסימלי. בפעם השנייה עברו על הקודקודים בסדר כך שעבורו הפלט
המתקבל יהיה הזיווג הממושקל המקסימלי. בכל הרצה רשמו את כל הצלעות שנבחרו ואת הפלט
שלום,
ניתן לי בקורס באוניברסיטה ואיני מצליחה להתמודד איתו.
אשמח לעזרה:
שלום,
ניתן לי בקורס התרגיל הבא ואיני מבינה מה עושים החל מסעיף 2 והלאה.
אשמח לעזרה.
תודה.שלב חשוב בתרגום אוטומטי הוא התאמה בין טקסטים מקבילים
במשימה הזו, נתונים לנו שני טקסטים בשתי שפות שונות כך שהאחד הוא התרגום של השני. מטרתנו היא
להרכיב מעין מילון המתאים מילים בשפה אחת למילים בשפה השנייה.
ו-”ג'ון אכל תפוח" יותאמו באופן הבא: ”John ate an apple" לדוגמא, המשפטים
מתאים ל-”ג'ון" ”John“ •
מתאים ל-”אכל" ”ate“ •
מתאים ל-”תפוח" ”apple“ •
הערות:
• חלק מהמילים באחת או בשתי השפות עשויות להשאר מיותמות.
• ההתאמה מתבצעת בין מילה אחת למילה אחת בלבד.
• בעיית ההתאמה המוצגת בתרגיל זה היא גרסא מפושטת של בעיית ההתאמה הכללית.
ואחרות) משתמשות בשיטות מתקדמות Google Translate מערכות מתוחכמות יותר (כמו
יותר. למשל, ההתאמה שם נעשית לא רק בין מילים בודדות אלא גם בין ביטויים מרובי
מילים.
• בתרגיל זה אנו מניחים שלכל מילה מתאימה מילה אחת ויחידה. הנחה זו איננה מתקיימת
”bank" במציאות כמובן, שכן למילה עשויים להיות מספר תרגומים בהקשרים שונים (למשל
עשוי להיות מתורגם ל-"בנק" בהקשר אחד ול-”גדה" באחר). עם זאת, הנחה זאת כן
מתקיימת בקירוב בהקשרים מסויימים ועשויה לשפר את הדיוק של ההתאמה.
• ניתן לייצג את בעיית ההתאמה כבעיית זיווג בגרף דו-צדדי. נגדיר גרף דו-צדדי באופן הבא:
• הקודקודים בצד שמאל יתאימו למילים בשפה א' (במקרה שלנו אנגלית).
• הקודקודים בצד ימין יתאימו למילים בשפה ב' (במקרה שלנו עברית).
• נמתח צלעות בין מילים שעשויות להיות תרגומים זו של זו.
אנחנו מעוניינים למצוא זיו וג שמתאים כמה שיותר זוגות מילים שהן אכן תרגום זו של זו. נזכיר שזיווג הוא
תת-קבוצה של צלעות הגרף כך שמכל קודקוד יוצאת לכל היותר צלע אחת.
בתרגיל זה נעסוק בטקסט הפשוט הבא:
עברית אנגלית
Yos s i went on a trip to US י וסי נסע ל-ארה"ב ל-טיול
ב-ביקורו ב-ארה”ב, הוא פגש את דינה
ש-עבדה ב- ני ו י ורק ב-מסעדה
On his visit there, Yos s i met Dina who
worked in a New York restaurant
דינה עברה ל- ני ו י ורק כמה שנים קודם
לכן
She moved to New York a few years
before
שמה של ה-מסעדה היה ארבע העונ ות,
והיא הייתה ממוקמת באיזור מרכזי של
העיר
The name of the restaurant was The
Four Seasons , and it was located in a
central part of town
Yos s i and Dina used to go strolling הזוג נהג לצאת לטיולים בפארק
together in the park
י וסי אהב את ני ו י ורק והחליט להשאר
שם
Yos s i loved New York and deceided
to stay there
אנו מניחים שהטקסטים מתאימים אחד לשני משפט-משפט. כמו כן, אנו מניחים שמיליות בעברית שנכתבות
צמודות למילים אחריהן (כגון, “ל", “כ", “ו" וכו') הן מילים נפרדות. כלומר נתייחס אליהן כאילו יש רווח בינן
לבין המילה העוקבת.
משימתנו בתרגיל זה היא להרכיב מילון אנגלי-עברי של השמות הפרטיים בטקסט הקצר לעיל.
נניח שנתון לנו אלגוריתם שמסמן את השמות הפרטיים בטקסט (מודגשים לעיל). אנו רוצים להתאים כל שם
פרטי לשם פרטי בשפה השנייה שמתאים לו. נבנה את הגרף הדו-צדדי כך שבצד שמאל יופיעו השמות
הפרטיים בעברית (“יוסי", “דינה", “אמריקה", “ניו יורק", “ארבע העונות") ובצד ימין השמות הפרטיים
באנגלית.
שימו לב שכל שם פרטי מופיע פעם אחת בגרף באופן בלתי תלוי במספר הפעמים בהן הוא מופיע בטקסט.
1. בשלב ראשון, נניח שזוג מילים שמופיעות במשפטים מתאימים יכולות להיות תרגום זו של זו. כלומר, אנו
נמתח צלע בין שם פרטי בעברית ושם פרטי באנגלית במשפט המתאים לו. לדוגמא נמתח צלע בין "יוסי"
.”US“- ו ”Yossi" לבין
ציירו את הגרף (קודקודים וצלעות) המתאים לדוגמא לעיל.
2. משימתנו כעת היא למצוא זיווג בעל גודל מקסימלי, כלומר זיווג המכיל את המספר הרב ביותר של צלעות.
נציע אלגוריתם פשוט עבור בעיית הזיווג המקסימלי:
• קלט: גרף דו-צדדי
להיות ריקה S • אתחל את קבוצת הצלעות
• כל עוד יש צלעות בגרף ששני קודקודיהן לא זווגו:
S- בחר צלע כזאת והוסף אותה ל ◦
S • פלט: הקבוצה
. נניח שהקלט לאלגוריתם הוא הדוגמא מסעיף 1
הריצו את האלגוריתם ורשמו את כל הצלעות שנבחרו במהלך הריצה לפי סדר בחירתן, ואת הזיווג .a
המתקבל (הפלט).
הראו עבור הדוגמא מסעיף 1 שעבור בחירה מסויימת של צלעות, האלגוריתם עשוי לסיים את ריצתו .b
ולהחזיר זיווג שאיננו מקסימלי (כלומר, זיווג עבורו יש זיווג אחר המכיל יותר צלעות ממנו).
הראו עבור הדוגמא מסעיף 1 שיש יותר מזיווג מקסימלי אחד בגרף, וממילא שיש זיווגים .c
מקסימליים שאינם נכונים.
3. בסעיף הקודם ראינו שאפילו במקרים בהם האלגוריתם מצליח למצוא זיווג מקסימלי, הוא לא בהכרח מוצא
זיווג שמתאים כל מילה לתרגום שלה.
על מנת ליצור מצב שבו הזיווג שנבחר מתאים מילים לתרגומים שלהם, נשנה מעט את הבעייה לבעיית
הזיווג הממושקל המקסימלי. לכל צלע בגרף ניתן משקל (שיכול להיות כל מספר חיובי). משקל הצלעות נקבע
ע"י אלגוריתם אחר שמספק הערכה ראשונית לגבי הסבירות שמילה אחת תתאים למילה אחרת. המטרה
במקרה זה היא להגיע לזיווג שסכום המשקולות על צלעותיו מקסימלי.
ומשקל נמוך לצלע בין "יוסי" ,”Yossi”- דוגמא: משקול טוב של הצלעות ייתן משקל גבוה לצלע בין "יוסי" ל
.”Dina”- ל
תנו משקל לכל צלע בגרף בסעיף הראשון בצורה כזו שהזיווג שסכום משקלותיו הוא הגבוה ביותר .a
הוא אכן הזיווג הנכון.
נציע אלגוריתם שנותן משקלים לצלעות. משקל צלע בין מילה א' (משפה א') למילה ב' (משפה ב') .b
יהיה מספר הפעמים בהם מילה א' ומילה ב' הופיעו במשפטים מתאימים. חשבו את המשקל של כל
צלע כפי שמתקבל מאלגוריתם זה עבור הטקסט הנתון בראש התרגיל.
הראו שבגרף הממושקל שחושב בסעיף הקודם, הזיווג הנכון (כלומר זה שמתאים לכל מילה את .c
התרגום שלה) הוא אכן זיווג ממושקל מקסימלי (כלומר אין אף זיווג אחר בעל סכום משקלים גדול
ממנו).
נציע אלגוריתם עבור מציאת הזיווג הממושקל המקסימלי: .d
• קלט: גרף דו-צדדי
להיות ריקה S • אתחל את קבוצת הצלעות
• עבור כל קודקוד בצד ימין (עברית) של הגרף בצע:
S- בחר את הצלע בעלת המשקל המקסימלי שיוצאת מקודקוד זה והוסף אותה ל ◦
S • פלט: הקבוצה
ורשמו את כל הצלעות שנבחרו במהלך הריצה b הריצו את האלגוריתם על הגרף הממושקל מסעיף
לפי סדר בחירתן. הראו שהפלט המתקבל איננו התאמה אחד לאחד. כלומר, ישנו קודקוד שנוגע
.S בשתי צלעות מהפלט
על כן הוא מפר את הנחתנו שההתאמה המבוקשת היא אחד לאחד (ראה הערה לעיל).
נציע אלגוריתם אחר: ,d על מנת לתקן את הבעייה שנוצרה בסעיף .e
G • קלט: גרף דו-צדדי
להיות ריקה S • אתחל את קבוצת הצלעות
• עבור כל קודקוד בצד ימין (עברית) של הגרף בצע:
.S- בחר את הצלע בעלת המשקל המקסימלי שיוצאת מהקודקוד והוסף אותה ל ◦
.y- נסמן את הקודקוד בצד שמאל שנוגע בצלע זו ב
.y- את כל הצלעות היוצאות מ G הסר מן הגרף הדו-צדדי ◦
S • פלט: הקבוצה
שימו לב שהפלט של אלגוריתם זה עשוי להיות תלוי בסדר בו עוברים על הקודקודים בצד ימין של
הגרף. לאור זאת, אלגוריתם זה עדיין לא פותר בהכרח את בעיית מציאת הזיווג הממושקל
המקסימלי (למרות שלרוב הוא נותן קירוב ראשוני סביר לבעיה).
הריצו את האלגוריתם פעמיים. בפעם אחת עברו על הקודקודים בסדר כך שעבורו הפלט המתקבל
לא יהיה הזיווג הממושקל המקסימלי. בפעם השנייה עברו על הקודקודים בסדר כך שעבורו הפלט
המתקבל יהיה הזיווג הממושקל המקסימלי. בכל הרצה רשמו את כל הצלעות שנבחרו ואת הפלט
