מדע בזיוני

מעניין. אולי זה אפילו נכון.

הבלוג של אורן צור-

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

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


(עד כאן אני. מכאן והלאה המיקרופון, כלומר המקלדת, ליובל).

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

spaminacan.jpg
למה אנשים שולחים אליכם ספאם? כי הם מרוויחים מזה כסף. ניקח לדוגמה את יוסי (שם בדוי). יוסי הוא בן 16, גר בעליית הגג של הוריו וחוסך כסף לשיעורי נהיגה. בעלות אפסית יוסי שולח שני מיליון הודעות ספאם באחר-צהריים אחד. נניח שרק אחד מעשרת אלפים מקבלי הספאם לחץ על הקישור, ושיוסי מקבל שקל ללוחץ. הנה הגענו ל-200 שקל ליום. בהנחה שיוסי יעבור בטסט שני, שליחת הספאם השתלמה. מעניין איך יחסוך לטיול שאחרי הצבא…
כל כלכלן מתחיל יגיד לכם שאין ארוחות חינם. אז מי משלם עבור הספאם? אתם, כמובן. נו טוב, גם אני. ספקי האינטרנט של יוסי ושל כולנו קונים בכסף טוב את רוחב הפס הנדרש להעברת אימייל, ומוכרים אותו ברווח קטן למשתמשיהם. כיון שהודעותיו של יוסי משתמשות ברוחב הפס הנ"ל, עלותן מתחלקת בין כלל לקוחות הספקים. מי עוד משלם עבור הספאם? שוב אתם – עלות הזמן שלוקח להבין שהודעת אימייל מציעה שעון או כלה ממזרח אירופה מוטלת עליכם.
אם נסתכל לרגע בראיה כוללת יותר, יש הערכה שעלות הטיפול בספאם בארה"ב בשנת 2007 הייתה 10 מיליארד דולר, כלומר אחד ועשרה אפסים אחריו. לצורך השוואה, תקציב מדינת ישראל לשנת 2008 הוא כ-314 מיליארד שקלים, שהם כ-90 מיליארד דולר. מכאן קיבלנו שעלות הספאם בארה"ב היא כתשיעית מתקציב מדינת ישראל. מאחר שיש מוטיבציה כלכלית ברורה, התפתח שוק ער של ספאמרים, מצד אחד, ושל רעיונות נגד דואר זבל, מצד שני.

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

עיבוד שפה טבעית כפיתרון לדואר זבל

לאחד מסוגי הטכנולוגיה שיכולים לעזור בצד המקבל קוראים עיבוד שפה טבעית. בשנת 2002 פרסם פול גרהם את המסה A Plan for SPAM בה תיאר דרך תכנותית פשוטה לזיהוי ספאם. הוא השתמש במסווג בייסיאני. לטובת הקוראים שעוד נשארו – הנה הסבר על רגל אחת (אני מקווה שהכומר בייס אכן עמד על רגל אחת מדי פעם): כדי לזהות אם הודעה היא ספאם או לא-ספאם (המונח המקצועי הוא הַאם [חזיר]– כן, הפוסט הזה טרף, סליחה אורן) – נשתמש בשתי קבוצות של הודעות – אחת מהן כולה ספאם והשנייה כולה הַאם. לשתי קבוצות ההודעות יחד קוראים קבוצת אימוּן. אם הודעה חדשה דומה יותר להודעות הספאם, ננחש שהיא ספאם. אם היא דומה יותר להודעות ההאם, ננחש שהיא האם. פשוט, נכון?
שכחתי כמה עניינים קטנים – מזתומרת הודעה "דומה יותר" להודעות אחרות? לשם קביעת הדמיון בין הודעות, נחשב ראשית פרופיל של כל הודעה. במקרה שלנו, לצורך קבלת הפרופיל, נספור כמה פעמים מופיעה כל מילה בהודעה. השם המקובל לפרופיל כזה הוא bag of words. נשים לב שהפרופיל אינו מתחשב בסדר המילים, ולכן "אדם נשך כלב" ו"כלב נשך אדם" יקבלו את אותו הפרופיל. כעת, בעזרת הכומר בייס, נחשב פרופיל מייצג לקבוצת הספאם ולקבוצת ההאם מתוך פרופילי ההודעות.
הכומר האנגלי בן המאה השמונה-עשרה תומס בייס לא קרא אימייל. הוא התעניין במידת החסד של האל, בהגנה על תורת הקלקולוס של ניוטון מהתקפותיו של הבישוף ברקלי, ובתורת ההסתברות. נוסחת בייס, הרלבנטית לענייננו, עוסקת בהסתברות מותנה.

קצת סטטיסטיקה

לדוגמה: הטלנו קוביה הוגנת. מה הסיכוי שיצא מספר הגדול מ-4? שליש.
כעת, נניח שהטלנו קוביה הוגנת וגם ידוע לנו שהמספר שיצא גדול מ-3. מה הסיכוי שהמספר גדול גם מ-4? שני שליש. המידע שהתווסף לנו (המספר שיצא גדול מ-3) שינה את הערכתנו לגבי הסיכוי לתוצאה הגדולה מ-4. והרי הנוסחה:
(P(A|B) = P(B|A)P(A)/P(B
כאשר A ו-B הם מאורעות מקריים, הסיכוי ש-A קרה בהינתן B, הוא מכפלת הסיכוי ש-A קרה בסיכוי של B בהינתן A, מחולקת בסיכוי של B.
בדוגמת הקוביה – הסיכוי שהתוצאה גדולה מ-4 (A) בהינתן שהתוצאה גדולה מ-3 (B), היא
מכפלת הסיכוי שהתוצאה גדולה מ-3 בהינתן שהיא גדולה מ-4 (תמיד, ולכן הסיכוי הוא 1),
בסיכוי שהתוצאה גדולה מ-4 (שליש) המחולקת בסיכוי שהתוצאה גדולה מ-3 (חצי)
ולכן מקבלים שני שליש.
נוסחת בייס מאפשרת לנו לשלב מידע ממספר מקורות כדי לקבל הערכת סיכויים משופרת. בצורה דומה, הופעה של מילים מסוימות בהודעה תאפשר לנו להעריך את הסיכוי שההודעה היא ספאם (ואת הסיכוי המשלים שההודעה היא האם).
שאלתנו היא: בהינתן הודעת אימייל, מה הסיכוי שהיא הודעת ספאם?
A שלנו יהיה – ההודעה היא הודעת ספאם.
B יהיה – ההודעה בייצוג Bag of words מכילה את המילים שהתקבלו.
נפעיל את נוסחת בייס פעמיים, פעם כדי לחשב את הסיכוי לספאם ופעם כדי לחשב את הסיכוי להאם:

P(spam|message) = P(message|spam)P(spam)/p(message)
P(ham|message) = P(message|ham)P(ham)/p(message)

monty_python_spam.jpg

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

ולבחור במחלקה הנותנת ציון יותר גבוה לפרופיל ההודעה החדשה.
איך מחשבים את שני הגורמים?
(P(spam – ניקח את מספר הודעות הספאם ונחלק במספר ההודעות הכולל בקבוצת האימון. ( P(ham הוא הסיכוי המשלים.
כדי לחשב את הסיכוי לקבל את הפרופיל בהינתן הודעת ספאם, נבחר בגישה שנקראת "בייס נאיבי": לא רק שהסיכוי אינה תלויה בסדר המילים, הסיכוי לקבל מילה מסוימת אינה תלויה בסיכוי לקבל מילים אחרות:
P(w1,w2,…,wn|spam) = P(w1|spam)P(w2|spam)…P(wn|spam)
כדי למצוא את ( P(wi|spam ניקח את מספר ההופעות של המילה wi בהודעות ספאם ונחלק במספר ההופעות הכולל של wi בקבוצת האימון.
לסיכום, כדי לחשב ציון בייס נאיבי להודעה:
א. נהפוך כל הודעה במאגר לפרופיל שלה ע"י ספירת מילים.
ב. נחשב את הסיכוי לספאם ולהאם ע"י ספירת הודעות.
ג. נחשב את הסיכוי להופעת כל מילה שראינו במחלקת הספאם ובמחלקת ההאם.
ד. נהפוך את ההודעה החדשה לפרופיל.
ה. נחשב את שני הגורמים לפי סיכויי הספאם וההאם של המילים המופיעות בהודעה החדשה.
ו. נבחר את המחלקה שמקבלת ציון גבוה יותר.

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

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

ספאם בטפסים ותגובות

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

מי ישלם? בנון ישלם!

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

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

לקריאה נוספת:
הכומר והבינה ההסתברותית – מאמרו של ישראל בנימיני אודות שימושי התורה הבייסיאנית .
Machine learning in automated text categorization – סקירה מקיפה על סיווג טקסט שכתב פבריציו סבסטיאני (מדעי אך מעניין).
– רשימה שלי (אורן) מ'רשימות' על ספאם בבלוגים: ספלוג וספלינג.

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

7 תגובות עבור “לוף, חזיר, כומר ושופט (או איך מסננים ספאם)”

  1. כמה מחשבות לא טכנולוגיות בעליל:
    1. אני לא ממש בטוח לגבי הרלוונטיות של חישוב הנזק הכלכלי שהספאם גורם. כלומר אני מסכים שהעומס על השרתים גובה מחיר יקר, אבל אני לא מסכים שאפשר פשוט לסכום את אובדן שניות העבודה (נניח 20 שניות לעובד ליום) ואז להכריז שיש עשרות מליוני עובדים ולפיכך המשק מאבד מליוני שעות עבודה ביום. במקרה הזה השלם קטן בהרבה מסכום חלקיו ואת העשרים שניות הייתי מבזבז בדרך כזו או אחרת. הדרך להרוויח אות השניות האלו חזרה היא לשלוח את העובדים למחנה ריכוז או פשוט לנתק אותם מהרשת ולא להכריז מלחמה על הספאם.
    2. אני מעדיף לקבל ספאם מאשר את עלוני הפרסומת לדואר. עלוני הפרסומת מבזבזים נייר, משמידים את יערות הגשם, מלכלכים את הרחוב ומבזבזים את מספר השניות שלוקח להשליך אותם לפח. ספאם פשוט מוחקים או מסמנים כספאם, לא לא מבזבז עצים וכימיקלים.
    3. אז למה ספאם כל כך מפריע לנו (וגם לי, כן, בניגוד לאמור לעיל ספאם מביא לי ת'קריזה) – אולי כי יש תחושה של אובדן פרטיות גדול יותר. התרגלנו ששמים לנו עלוני-זבל בתיבת הדואר שבעצם נמצאת ברחוב, אבל את הספאם אנחנו קוראים בתוך הבית, הוא מגיע ל'חשבון הפרטי' שלנו ואנחנו מרגישים שמישהו ממש חדר לנו לתוך הבית וגם עשה את זה תוך חדירה לפרטיות שהרי מאיפה יש לספאמר את כתובת האימייל הפרטית שלנו…
    עוד לא הפנמנו שאין ממש פרטיות אם כתובת האימייל שלנו מופיעה ברשת או נמסרה לאתרים כאלה ואחרים, וגם לא את העובדה שהאינבוקס מייצג אותנו לעולם בדיוק כמו תיבת הדואר אל מול הרחוב הפיזי.

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

    אורן

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

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

    שירי

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

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

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

    יואב

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

    או שמא טעות בידי?

    Day-Walker

  5. דיי-ווקר –
    המסנן של ג'ימייל מצויין ו/כי הוא פועל בדיוק בשיטות שיובל הסביר (קצת יותר מורכב אבל הרעיון זהה).

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

    אורן

  6. והנה גם אצלנו הצעת חוק ממשלתית נגד ספאם:
    http://it.themarker.com/tmit/article/3146

    יובל

  7. והנה תגובה מעניינת לחוק הספאם:
    http://mila-mila.com/?p=178
    שם טוענים שבחוק יש מידה לא מבוטלת של צביעות.

    אורן

להוספת תגובה