בתשובה לדובי קננגיסר, 11/01/04 17:01
מן המפורסמות היא. 189940
אפשר לגשת להתפלגות חי בריבוע בכמה דרכים. אפשר גם לגשת לשאלה שלך בכמה דרכים (למשל: "הנה הסבר:", או "פרק 3 בספר Seminumerical Algorithms של Knuth פשוט נפלא, וסעיף 3.3.1 מטפל בחי בריבוע"). אבל קודם אני מוכרח לומר שקצת בלבלת אותי בהערה ‏1 שלך - לרוב, יותר קל לי לזכור משהו אם אני מבין אותו. משתמע מהערתך שכבר הבנת (כמה פעמים?) מהי התפלגות חי בריבוע ולמה היא טובה, אבל אתה לא מצליח לזכור זאת. האם כך? מה לדעתך יהפוך הסבר לכזה שתצליח לזכור - שהוא יהיה קצר יותר, נוסחתי יותר, אינטואיטיבי יותר...?

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

(תראו שם - פרפר!)
(איפה?)

וגם: למי אתה קורא קורא תמים?

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

(חוץ מזה היא מתוקה להפליא ואני מצטרף לברכת המזלטעף)
תודה! 190183
יש לה חבר? 190189
יש לך שם? 190190
יש לך שם? 190229
מה, אתה כזה אבא? אמאל'ה.

(מזל טוב).
יש לך שם? 190289
תודה גם לך!

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

ב''כזה'' התכוונתי למגונן מדי. וגם זה, כמובן, היה בצחוק.
איזו מתוקה! 190384
איזה כיף. תודה גם לך! 190436
פרפר? איפה?! 190717
יש לך את כל הסיבות להיות גאה, הילדה שלך מקסימה ממש!

מה זה knuth?

(הבחנתי שהתמונות נמצאות על אתר של קומפיוג'ן - "הגם אתה ברוטוס?")
שיו, אני *בטוח* שהיה שם פרפר 190757
חן חן!

Knuth: מתמטיקאי ואיש מדעי-המחשב אגדי (עודנו חי) שכתב סדרת ספרים בשם The Art of Computer Programming. המטרה המוצהרת של הספרים היא בניית תשתית מתמטית לניתוח מסודר של יעילות אלגוריתמים והצגת אלגוריתמים יעילים לבעיות יסודיות; בפועל, יש שם את זה ועוד *הרבה* יותר. יופי של ספרים. השמועות מספרות שהאיש נוהג לשבת בהרצאות ולסרוג. אה, והוא גם המציא ופיתח את TeX, MetaFont וכו', אם אתה מכיר במקרה.

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

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

באותה הרצאה ממש, אגב, הוא הראה גילוי שלו מתורת הגרפים, ובו צפונה הוכחה לשימושיות המחקר: הוא הראה את אותו גילוי לביל גייטס, כשזה ביקר בסטנפורד; גייטס הודה שלא הבין כלום, ותרם 10 מיליון דולר לפקולטה.
שיו, אני *בטוח* שהיה שם פרפר 190780
כן, יש בו את הלו-טקיות החמודה הזו. הוא גם לא משתמש ב-e-mail, והאמת? אני מקנא.
שיו, אני *בטוח* שהיה שם פרפר 193961
הערה קטנה לגבי הספרים הנ"ל: אני עדיין לא נתקלתי במדען מחשב שקרא אותם.
שיו, אני *בטוח* שהיה שם פרפר 193966
אז לא חיפשת טוב מספיק. אתה נוהג לשאול מדעני-מחשב אם הם קראו את Knuth? אני קראתי (חלקים גדולים) בהנאה רבה, אבל אני בלי שום ספק לא מדען מחשב. חוץ מזה, למדנו בדיון אחר שזה שספר נחשב קלאסי לא אומר שמישהו קרא אותו.

מומלץ במיוחד: הפרק שדן בחישוב חזקות. מדהים כמה עומק יש בבעייה הפשוטה הזו, ובאיזו שמחה K צולל לתוכו. די חסר חשיבות מעשית, אבל כיף אמיתי.
"חסר חשיבות מעשית"? 193968
רוב שיטות ההצפנה המודרניות משתמשות בהעלאה-בחזקה.
"חסר חשיבות מעשית"? 193976
לא אמרתי שהעלאה בחזקה היא חסרת-חשיבות. הפער בין השיטות הפשוטות לעשות זאת לבין השיפורים והחסמים המדוייקים הנדונים אצל Knuth הוא קטנטן, כך שה*פרק* בספר הוא די חסר חשיבות מעשית, אך יש בו חן תיאורטי רב.
שיו, אני *בטוח* שהיה שם פרפר 193979
זה לא מפתיע אותי שאתה קראת אותו, נראה לי שיש משהו בספרים האלה שמושך יותר מתמטיקאים ממדעני מחשב.

ככלל, אחד מהדברים שמפריד בין מתמטיקאים למדעני מחשב הוא הנטיה של האחרונים להתמקד בהערכות (approximations) לעומת הנטיה של הראשונים להתמקד בחישובים מדויקים. כך למשל לרוב מדעני מחשב מתעניינים רק בסדרי גודל של כל מיני כמויות ‏1 לעומת הערך המדויק של הכמות. אחת הסיבות לכך היא שהרבה פעמים יש כלל של 80/20 (או אפילו משהו ששואף ל100/0) בבעיות כאלה: בשביל לקבל הערכה שמספיקה לך ל80% מהצרכים, אתה צריך לעשות 20% מהעבודה. מדעני מחשב לא מוכנים בד"כ "להזיע" ע"מ לשפר את ההערכה, אם השיפור הוא לא קריטי עבורם.

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

---
1 כמו למשל מספר צעדי החישוב שמחשב לוקח ע"מ לבצע משימה מסוימת או הגודל של קליקה מקסימלית בגרף מקרי.

2 כמו הגדרה מדויקת של איזה מחשב ואיזה שפת מחשב משתמשים בה.
שיו, אני *בטוח* שהיה שם פרפר 193980
בינתיים ראיתי שבתגובה 193976 נתת עוד דוגמא (שלא ידעתי עליה) למקרה שבו K מוכן להשקיע הרבה מאמץ בשביל לתת חישוב יותר מדויק, כאשר רמת הדיוק הזו לא ממש מעניינת את רוב מדעני המחשב.
שיו, אני *בטוח* שהיה שם פרפר 193985
דוגמא לפער הזה בין מתמטיקאים למדעני המחשב הוא המשפט שנקרא ה Prime Number Theorem

המשפט הזה נחשב למשפט מפורסם וחשוב במתמטיקה, והוא מראה מספר המספרים הראשוניים בין 1 ל n שואף ל n/lnn (ככל שn שואף לאינסוף).

עעבור מדעני מחשב,כמעט לכל שימוש אפשרי מספיקה התוצאה של צ'בישב שהמספר הזה הוא בתחום שבין 0.8n/lnn ל 1.2n/lnn, את ההערכה הזו אפשר לקבל בצורה הרבה יותר פשוטה מאשר ה prime number theorem (יש לתוצאה הזו הוכחה של בערך 4 שורות), ולכן מן הסתם אם זה היה תלוי במדעני מחשב, לתוצאה של צ'בישב היו קוראים ה prime number theorem.
שיו, אני *בטוח* שהיה שם פרפר 193989
כשיגיעו לכאן היצורים הירוקים בעלי שלוש העיניים, אני בטוח שהשאלה הראשונה שלהם תהיה אם כבר הצלחנו להוכיח שההפרש בין מספר הראשוניים מתחת x לבין (x/log(x אינו עולה על קבוע כפול (sqrt(x)*log(x.
שיו, אני *בטוח* שהיה שם פרפר 193994
ואני חושב שהם יתעניינו יותר במיקומו של פח הזבל הקוסמי. עד שיקחו אותם לרמת חובב.
שיו, אני *בטוח* שהיה שם פרפר 194006
זאת תהיה השאלה השניה, אחרי שהם ישאלו אם הצלחנו להוכיח שאין מעגל בגודל
2^{sqrt(n)}
לחישוב ספיקות של נוסחה בוליאנית בגודל n.

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

"מיפקד" זה כשיש לך אוכלוסייה ואתה סופר, כמה אנשים נופלים לכל מיני קטיגוריות. דוגמה: אתה זורק קובייה 120 פעם, ומקבל 18 פעמים 1, 23 פעמים 2, וכו' (שש קטגוריות). או, אתה שואל מבקרים באתר האינטרנט שלך איך הם מעדיפים את המים שלהם (שבע קטגוריות). וכאלה.

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

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

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

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

אם לא תתבלבל, אזכיר שיש גם מצב ש-Q כל-כך *קטן* שזה לא סביר. ההתפלגות תאמר לך "הסיכוי לקבל Q כזה או יותר הוא 99.9999999999%". כלומר, יש התאמה מופלאה מדי בין המיפקדים. מישהו רימה? הקובייה מתוכנתת ליפול כל פעם על המספר הבא? משהו כזה.

זהו, בערך. אפשר להסביר עוד הרבה, אבל תגיד איך זה נראה וננסה שוב.

1 למה k-1? כי אם אתה יודע את התוצאות של k-1 קטגוריות ואת כמות הנבדקים, אתה יודע כמה נפלו לקטגוריה ה-k. לכן יש רק k-1 "דרגות חופש".
נוסחאות 190187
הבעיה היא לא עם הפונטים אלא עם יוניקוד. כדי לכתוב נוסחאות פשוט עוברים לשורה חדשה, ונמנעים מעברית:
((Ei-Xi)^2)/Ei
נוסחאות 190188
הבנתי. זה נראה רע (אצלי לפחות) עד שלוחצים על ''אשר''. תודה.
מן המפורסמות היא. 190191
אוקיי, לא רע. הבהרה: Q הוא הסכום של הנוסחה ההיא שטל כתב עבור כל ה-iים, (כלומר כל הקטגוריות) נכון?

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

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

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

הזנב הימני זה באמת בגלל שהסבירות להתאמה יורדת ככל ש-Q גדל, ו-Q איננו חסום. מה שקורה כש-Q שואף ל-‏0 משתקף כמובן בצד ה*שמאלי* של דבשת הגמל - וכן, נכון, אתה צודק גם פה. לכן טרחתי להזכיר שגם Q מאוד קטן הוא לא סביר.
שאלה: 190204
לא יתקבל גודל יותר משמעותי אם ננרמל את Q ע"י חלוקה במס' הקטגוריות?

(אני שואל כי בחישוב ישר הההפרשים המינימליים, Excel מחשב איזה גודל בשם R^2 שמזכיר לי את Q שלך, והוא הולך וגדל בכל פעם שאני מבצע מדידה נוספת גם אם התוצאה שקיבלתי קרובה לישר. יוצא שהאינטואיציה שלי אומרת שהישר מתאר טוב יותר את התוצאות שלי, אבל R^2 דוקא גדל).
שאלה: 190209
R בריבוע הוא מדד השונות המוסברת, והוא מבוסס על R, שהוא מקדם המתאם של פירסון. המדד הזה יגדל ככל שהמדידות תהיינה קרובות יותר לקו, כי זה מה שהוא מודד - עד כמה הקו מתאר את הנקודות באופן מהימן. האינטואיציה שלך צדקה: R בריבוע (וגם סתם R) גדול יותר, משמעו שהישר מתאר טוב יותר את התוצאות.
למיטב הבנתי, אין שום דמיון בין R (או R בריבוע) ל-Q.

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

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

פירסון - זה ההוא מכאן ? http://www.larryniven.org/puppeteer/
טבלאות זה למפונקים 190252
במקום לרוץ לחפש טבלה בכל פעם שמחשבים את הסכום Q של חי-בריבוע, אפשר לזכור שה*ממוצע* של אותם ריבועים (דהיינו, Q המנורמל), אמור להיות 1 (והשונות היא 3 חלקי (מספר הקטגוריות פחות 1)).
למשל: במבחן על 6 קטגוריות יוצא Q=20. הממוצע Q/5=4 גדול משמעותית מ- 1, ולכן ההתפלגויות שאנחנו משווים שונות זו מזו. בלי טבלאות.
טבלאות זה למפונקים 190268
4 גדול משמעותית מ- 1, זהו ניסוח של מתמטיקאי. מהנדס כבר היה אומר שזה אותו סדר גודל. :)
טבלאות זה למפונקים 190301
במקרה הזה, "גדול משמעותית" פירושו שהמרחק הוא יותר מ- 4.5 סטיות תקן, ו(אפילו למהנדס) ברור שזה "גדול משמעותית".
p's in a pod 190259
דוגמא מפורסמת ל- Q קטן באופן חשוד היא הסיפור של מנדל וחוקי התורשה. אם אני זוכר נכון, התוצאות המספריות של ניסויי הכלאת האפונים שלו היו משכנעות באופן בלתי סביר, ויש שטענו שהוא "בישל" אותן כדי שיתמכו בתאוריה שלו.

היה ברשותי פעם מאמר שכותרתו היא ככותרת תגובה זו (די שנון, לא?) שטען בדיוק ההיפך, דהיינו מתח ביקורת על מותחי הביקורת על מנדל. לא קראתי את המאמר, כך שאני לא סגור על הפרטים.
p's in a pod 190277
דוגמה טובה. הסיפור צץ כפעם בפעם (נדמה לי שלאחרונה נתקלתי בו ב"הגמד של מנדל"). תשובה שנשמעת לי סבירה (כן ולא) מופיעה כאן:

בסעיף "Did Mendel fudge his data".

חזרה לעמוד הראשי

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