מהעולם אל הדאטה

יחידה 1 בקורס שיטות מתמטיות בבינה מלאכותית (ד"ר ארז שיינר).

יחידה 1 · מהעולם אל הדאטה: ייצוג ראשוני ואובדן מידע

קול, תמונה, צבע ושחמט: מה נשמר ומה אובד

מאיפה באנו, ומה הפרק הזה מוסיף

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

מבוסס על המאמרים:

Shannon, C. E. (1949). Communication in the presence of noise. Proceedings of the IRE, 37(1), 10–21. Sections II–III.

Alfvin, R. L., & Fairchild, M. D. (1997). Observer variability in metameric color matches using color reproduction media. Color Research & Application, 22(3), 174–188.

Wyszecki, G., & Stiles, W. S. (1982). Color Science: Concepts and Methods, Quantitative Data and Formulae (2nd ed.). Wiley. Stockman, A., & Sharpe, L. T. (2000). The spectral sensitivities of the middle- and long-wavelength-sensitive cones derived from measurements in observers of known genotype. Vision Research, 40(13), 1711–1737.

הסיפור הבסיסי

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

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

אנלוגי ודיגיטלי

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

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

הגדרה 1ייצוג דיגיטלי

ייצוג דיגיטלי הוא סדרה סופית של סמלים מתוך קבוצה סופית של סמלים. במחשב הקבוצה היא [math]\displaystyle{ \{0,1\} }[/math].

ייצוג אנלוגי מתקלקל בכל העתקה: קצת רעש נוסף לאות, וההעתק של ההעתק רועש יותר. ייצוג דיגיטלי אפשר להעתיק בלי שגיאה, כי המקבל צריך רק להחליט איזה מבין ערכים ספורים נשלח. למשל, קו שמעביר ספרות [math]\displaystyle{ 0 }[/math] ו־[math]\displaystyle{ 1 }[/math] בלבד: את [math]\displaystyle{ 0 }[/math] שולחים כמתח של אפס וולט ואת [math]\displaystyle{ 1 }[/math] כמתח של וולט אחד. בדרך נוסף רעש, ובמקום וולט אחד מגיעים [math]\displaystyle{ 0.9 }[/math] וולט; המקבל מעגל לקרוב מבין השניים וקורא [math]\displaystyle{ 1 }[/math], בדיוק מה שנשלח. ההעתק זהה למקור, והרעש אינו עובר הלאה. זו הסיבה שהעולם עבר לדיגיטלי, וזה נושא המאמר של שאנון: תקשורת בנוכחות רעש.

המעבר מאנלוגי לדיגיטלי הוא שני צעדים. הראשון הוא דגימה: במקום למדוד את האות בכל רגע, מודדים אותו רק ברגעים נבחרים, למשל אלף פעמים בשנייה; בתמונה, במקום בכל נקודה, רק ברשת של נקודות, הפיקסלים. מה שקורה בין המדידות אינו נמדד. השני הוא קוונטיזציה: המדידה עצמה היא מספר ממשי, ולמחשב אין מקום לאינסוף ספרות, ולכן מעגלים אותה לאחת מרשימה סופית של רמות, למשל [math]\displaystyle{ 256 }[/math] רמות בהירות לפיקסל. יש גם עולמות שהם דיגיטליים מטבעם: טקסט הוא סדרת אותיות, ולוח שחמט הוא [math]\displaystyle{ 64 }[/math] משבצות. בהם אין מה לדגום ואין מה לעגל, ונחזור אליהם בסוף הפרק.

קול: כמה פעמים בשנייה צריך למדוד

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

נסמן ב־[math]\displaystyle{ f(t) }[/math] את המתח שהמיקרופון מוציא ברגע [math]\displaystyle{ t }[/math] (בשניות).

הגדרה 2דגימה

יהי [math]\displaystyle{ f_s>0 }[/math] קצב דגימה (מדידות בשנייה). הדגימות של [math]\displaystyle{ f }[/math] בקצב [math]\displaystyle{ f_s }[/math] הן המספרים

[math]\displaystyle{ x_n=f\!\left(\frac{n}{f_s}\right),\qquad n\in\mathbb Z . }[/math]

הניחוש הטבעי: מה שקורה בין שתי דגימות אובד; ככל שדוגמים צפוף יותר אובד פחות, אבל תמיד משהו. הניחוש שגוי, ובשביל לראות למה צריך לדעת דבר אחד על קול: כל צליל הוא צירוף של גלי סינוס בתדרים שונים, בעוצמות שונות ובפאזות שונות (היסטים בזמן). תו לה של כינור הוא גל של [math]\displaystyle{ 440 }[/math] הרץ (מחזורים בשנייה), ועליו גלים חלשים יותר של [math]\displaystyle{ 880 }[/math], [math]\displaystyle{ 1320 }[/math] וכן הלאה. נאמר שאות חסום־תדר ב־[math]\displaystyle{ W }[/math] הרץ אם אין בצירוף שלו גל מהיר מ־[math]\displaystyle{ W }[/math] מחזורים בשנייה. קול אמיתי אינו בהכרח חסום־תדר, הגלים העיליים נמשכים לכאורה בלי סוף; אבל הקול שהאוזן קולטת חסום: היא אינה שומעת מעל כ־[math]\displaystyle{ 20{,}000 }[/math] הרץ, ולכן די לשמור את מה שמתחת לזה, וכך עושה גם מיקרופון, שמעצמו חוסם תדרים גבוהים.

הצירוף הזה הוא גם מה שמבדיל בין כלים: כינור וחליל שמנגנים אותו לה נשמעים שונים, אף שבשניהם הגל הבסיסי הוא [math]\displaystyle{ 440 }[/math] הרץ. ההבדל הוא אילו גלים נוספים יש מעל הגל הבסיסי, ובאיזו עוצמה. האוזן מבחינה בהבדל הזה כי היא מודדת את הצירוף עצמו: בשבלול יש אלפי תאי שיער, וכל אחד מגיב לתדר אחר. נזכור את זה; העין, כפי שנראה בסעיף על הצבע, עושה את ההפך.

משפט 3משפט הדגימה, שאנון

יהי [math]\displaystyle{ f }[/math] אות חסום־תדר ב־[math]\displaystyle{ W }[/math] הרץ, ויהיו [math]\displaystyle{ x_n=f(n/2W) }[/math] הדגימות שלו בקצב [math]\displaystyle{ f_s=2W }[/math]. אזי לכל [math]\displaystyle{ t }[/math]

[math]\displaystyle{ f(t)=\sum_{n=-\infty}^{\infty}x_n\,\operatorname{sinc}(2Wt-n), }[/math]  כאשר  [math]\displaystyle{ \operatorname{sinc}(u)=\frac{\sin(\pi u)}{\pi u},\ \ \operatorname{sinc}(0)=1 . }[/math]

הערה: במאמר: “If a function [math]\displaystyle{ f(t) }[/math] contains no frequencies higher than [math]\displaystyle{ W }[/math] cps, it is completely determined by giving its ordinates at a series of points spaced [math]\displaystyle{ 1/2W }[/math] seconds apart.” (Theorem 1)

במילים: [math]\displaystyle{ 2W }[/math] מספרים בשנייה קובעים את הקול לגמרי, לא בקירוב. הפונקציה [math]\displaystyle{ \operatorname{sinc}(2Wt-n) }[/math] היא "גבעה" שמרכזה ברגע הדגימה ה־[math]\displaystyle{ n }[/math]: שם היא שווה [math]\displaystyle{ 1 }[/math], ובכל רגעי הדגימה האחרים היא [math]\displaystyle{ 0 }[/math]. מכפילים אותה בערך הדגימה [math]\displaystyle{ x_n }[/math] ומקבלים גבעה שגובהה [math]\displaystyle{ x_n }[/math], וסכום הגבעות של כל הדגימות הוא פונקציה ששווה לאות המקורי בכל נקודות הדגימה. דרך הנקודות האלה עוברות אינסוף פונקציות, אבל הסכום הזה הוא גם חסום־תדר ב־[math]\displaystyle{ W }[/math], ואות חסום־תדר נקבע לגמרי על ידי דגימותיו בקצב [math]\displaystyle{ 2W }[/math] (יחידות, שלא נוכיח כאן). לכן הסכום הוא האות [math]\displaystyle{ f }[/math] עצמו, בכל רגע, גם בין הדגימות.

משפט הדגימה עם [math]\displaystyle{ W=\tfrac12 }[/math], כלומר דגימה בכל שלם: הדגימות [math]\displaystyle{ x_n }[/math] (חרוזים), וכל אחת תורמת גבעה [math]\displaystyle{ x_n\operatorname{sinc}(2Wt-n) }[/math] (ירוק; הגבעה של [math]\displaystyle{ x_0 }[/math] כהה). כל גבעה מתאפסת בכל נקודות הדגימה האחרות, וסכום הגבעות הוא האות [math]\displaystyle{ f }[/math] (תכלת), שעובר בדיוק דרך כל הדגימות.

ההוכחה של שאנון משתמשת בטורי פורייה, ולא נביא אותה כאן; פורייה נכנס לקורס ביחידה 3, ב־Shazam. כאן מספיקה לנו המסקנה, והמספרים שהיא נותנת: תקליטור דוגם [math]\displaystyle{ 44{,}100 }[/math] פעמים בשנייה, קצת יותר מפעמיים [math]\displaystyle{ 20{,}000 }[/math]; טלפון, שמעביר קול אנושי עד כ־[math]\displaystyle{ 4000 }[/math] הרץ, דוגם [math]\displaystyle{ 8000 }[/math] פעמים בשנייה. ומכאן ואילך בקורס, שנייה של קול טלפוני היא וקטור ב־[math]\displaystyle{ \mathbb R^{8000} }[/math], ולפי המשפט הווקטור הזה לא איבד דבר.

מה קורה כשדוגמים לאט מדי

מה קורה אם בקול יש תדרים מעל [math]\displaystyle{ f_s/2 }[/math]? הניחוש הטבעי: הם יאבדו, והקול ייצא עמום. זה לא מה שקורה. הם אינם נעלמים, הם מתחפשים.

טענה 4קיפול תדרים

יהיו [math]\displaystyle{ f_s>0 }[/math] קצב דגימה, [math]\displaystyle{ \nu }[/math] תדר ו־[math]\displaystyle{ k\in\mathbb Z }[/math]. לכל [math]\displaystyle{ n\in\mathbb Z }[/math]

[math]\displaystyle{ \cos\!\left(2\pi(\nu+kf_s)\frac{n}{f_s}\right)=\cos\!\left(2\pi\nu\frac{n}{f_s}\right). }[/math]

במילים: בנקודות הדגימה, גל בתדר [math]\displaystyle{ \nu }[/math] וגל בתדר [math]\displaystyle{ \nu+kf_s }[/math] זהים. הדגימות אינן יכולות להבחין ביניהם.

דוגמה 5צליל של 900 הרץ שנדגם 1000 פעמים בשנייה

[math]\displaystyle{ \nu=900 }[/math], [math]\displaystyle{ f_s=1000 }[/math], [math]\displaystyle{ k=-1 }[/math]: הדגימות של [math]\displaystyle{ \cos(2\pi\cdot900\,t) }[/math] זהות לדגימות של [math]\displaystyle{ \cos(2\pi\cdot(-100)\,t)=\cos(2\pi\cdot100\,t) }[/math]. מי שמשחזר מהדגימות שומע צליל נמוך של [math]\displaystyle{ 100 }[/math] הרץ. הצליל הגבוה לא נחלש; הוא הופיע במקום אחר.

למעלה: אות חסום־תדר, סכום של שני גלים שהמהיר בהם עושה [math]\displaystyle{ 2.3 }[/math] מחזורים ליחידת זמן, נדגם [math]\displaystyle{ 6 }[/math] פעמים ליחידה, מעל [math]\displaystyle{ 2W=4.6 }[/math]: חרוז בכל דגימה, ומהחרוזים אפשר לשחזר את החבל כולו. למטה: [math]\displaystyle{ \cos(2\pi\cdot900\,t) }[/math] נדגם [math]\displaystyle{ f_s=1000 }[/math] פעמים בשנייה במשך 10 אלפיות שנייה. החרוזים יושבים על גל איטי של 100 הרץ (ירוק): טענה 4 עם [math]\displaystyle{ k=-1 }[/math].

בלשון הפרק: דגימה איטית מדי מקבצת יחד שני קולות שונים, ושום עיבוד שיבוא אחריה לא יפריד ביניהם. לכן לפני הדגימה מסננים: מוחקים מהאות את התדרים שמעל [math]\displaystyle{ f_s/2 }[/math]. מה שנמחק אובד, אבל אנחנו יודעים מה אבד, ומה שנשאר חוזר בדיוק. זה ההבדל בין מידע שאבד לבין מידע מזויף.

קוונטיזציה: כמה סיביות לכל מדידה

הדגימות [math]\displaystyle{ x_n }[/math] הן מספרים ממשיים, והמחשב שומר לכל אחת מספר סופי של סיביות, ספרות בינאריות, [math]\displaystyle{ 0 }[/math] או [math]\displaystyle{ 1 }[/math]; ב־[math]\displaystyle{ b }[/math] סיביות יש [math]\displaystyle{ 2^{b} }[/math] צירופים, ולכן [math]\displaystyle{ 2^{b} }[/math] רמות אפשריות. כאן, לראשונה, אובד משהו בכל מקרה, וכמה אובד אפשר לחשב.

הגדרה 6קוונטיזציה אחידה

יהיו [math]\displaystyle{ b\in\mathbb N }[/math] ו־[math]\displaystyle{ A>0 }[/math], ונסמן [math]\displaystyle{ \Delta=\dfrac{2A}{2^{b}} }[/math]. הקוונטיזציה של [math]\displaystyle{ x\in[-A,A] }[/math] ל־[math]\displaystyle{ b }[/math] סיביות היא

[math]\displaystyle{ q(x)=\Delta\cdot\operatorname{round}\!\left(\frac{x}{\Delta}\right), }[/math]

כאשר [math]\displaystyle{ \operatorname{round} }[/math] מעגלת לשלם הקרוב (ואם [math]\displaystyle{ q(x) }[/math] יוצא מחוץ ל־[math]\displaystyle{ [-A,A] }[/math], מקצצים לקצה).

טענה 7שגיאת הקוונטיזציה

לכל [math]\displaystyle{ x\in[-A,A] }[/math] מתקיים [math]\displaystyle{ |x-q(x)|\le\dfrac{\Delta}{2} }[/math].

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

קוונטיזציה אחידה עם [math]\displaystyle{ b=3 }[/math] סיביות על [math]\displaystyle{ [-1,1] }[/math], כלומר [math]\displaystyle{ \Delta=1/4 }[/math]: האות [math]\displaystyle{ x }[/math] (ירוק), המדרגות [math]\displaystyle{ q(x) }[/math] (תכלת) והרמות (הקווים הדקים). למטה השגיאה [math]\displaystyle{ e=x-q(x) }[/math], שנשארת בין [math]\displaystyle{ \pm\Delta/2 }[/math], כבטענה 7.

תקליטור שומר [math]\displaystyle{ 16 }[/math] סיביות לדגימה, כלומר [math]\displaystyle{ 2^{16}=65{,}536 }[/math] רמות, ו־[math]\displaystyle{ 44{,}100\cdot16=705{,}600 }[/math] סיביות לשנייה לכל ערוץ. ב־[math]\displaystyle{ 8 }[/math] סיביות הקול נשמע כמו טלפון ישן, ובסיבית אחת נשאר רק הסימן.

תמונה: דגימה במקום

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

החיישן של מצלמה הוא רשת של תאים זעירים, וכל תא מודד את כמות האור שפגעה בריבוע הקטן שלו. זו דגימה במקום: מצלמה של [math]\displaystyle{ 12 }[/math] מגה־פיקסל דוגמת את התמונה ב־[math]\displaystyle{ 4000\times3000 }[/math] נקודות. כל מדידה נשמרת בדרך כלל ב־[math]\displaystyle{ 8 }[/math] סיביות, [math]\displaystyle{ 256 }[/math] רמות. תמונה בגווני אפור בגודל [math]\displaystyle{ n\times k }[/math] היא אם כן וקטור ב־[math]\displaystyle{ \mathbb R^{nk} }[/math]: הפרצופים של יחידה 3 הם תמונות של [math]\displaystyle{ 64\times64 }[/math], וקטורים ב־[math]\displaystyle{ \mathbb R^{4096} }[/math].

גם כאן יש קיפול תדרים. חולצה עם פסים דקים וצפופים נראית לפעמים בשידור טלוויזיה מכוסה בגלים רחבים שזזים, שאינם בחולצה. הסיבה: המצלמה מודדת את התמונה רק בפיקסלים, וכשיש יותר מפס אחד לכל שני פיקסלים, הדגימות אינן יכולות לעקוב אחרי הפסים. בדיוק כמו שצליל של [math]\displaystyle{ 900 }[/math] הרץ נרשם כצליל של [math]\displaystyle{ 100 }[/math] הרץ, הפסים הצפופים נרשמים כפסים רחבים שלא היו שם; וכשהאדם זז, הפסים הרחבים זזים איתו, ולכן נראים כגלים.

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

מצלמה דוגמת במקום: התמונה הופכת לרשת של פיקסלים, וכל פיקסל הוא שלושה מספרים, אדום, ירוק וכחול, כל אחד ב־[math]\displaystyle{ 8 }[/math] סיביות. לפיקסל המסומן, בשמש, [math]\displaystyle{ (R,G,B)=(241,202,98) }[/math].

הערת צד: מה המצלמה מדדה באמת

במצלמה רגילה יש חיישן אחד, וכל תא בו מודד מספר אחד: כמה אור הגיע אליו. כדי לקבל צבע, כל תא מכוסה במסנן של צבע אחד, בדוגמת פסיפס שהציע בייר מקודאק ב־1976: חצי מהתאים ירוקים, רבע אדומים ורבע כחולים. חיישן של [math]\displaystyle{ 12 }[/math] מיליון תאים נותן אפוא [math]\displaystyle{ 12 }[/math] מיליון מדידות, אבל בקובץ התמונה יש [math]\displaystyle{ 12 }[/math] מיליון פיקסלים כפול שלושה מספרים. את שני המספרים החסרים בכל פיקסל המעבד של המצלמה משערך מהתאים השכנים (demosaicking); רק קובץ RAW שומר את המדידות עצמן, מספר אחד לכל תא. המקור: הסקירה של Gunturk ועמיתיו, Demosaicking: color filter array interpolation, IEEE Signal Processing Magazine, 2005.

מה זה צהוב

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

אור הוא קרינה אלקטרומגנטית שאפשר להציג כסכום של גלים, כל אחד באורך גל [math]\displaystyle{ \lambda }[/math] משלו; העין רואה אורכי גל שבין כ־[math]\displaystyle{ 380 }[/math] ננומטר (סגול) לכ־[math]\displaystyle{ 780 }[/math] ננומטר (אדום).

האם האור "באמת" סכום של גלים? האור הוא שדה שמשתנה בזמן, פונקציה אחת של הזמן, והפירוק שלה לגלי סינוס הוא ייצוג: בחירה של בסיס, ובבסיס אחר היו יוצאים רכיבים אחרים. מה שמייחד את הבסיס הזה אינו המתמטיקה אלא החומר. כל מה שהאור פוגש, זכוכית, אוויר, פיגמנט ברשתית, אטום בנורה, מגיב לכל תדר לחוד: גל סינוס שעובר בזכוכית יוצא גל סינוס באותו תדר, רק חלש יותר או מוסט, ואטום של נתרן פולט ובולע בתדר מסוים. לכן מנסרה מפרידה את האור דווקא לתדרים, ולכן שני אורות עם אותו ספקטרום, הפונקציה [math]\displaystyle{ P(\lambda)\ge0 }[/math] שאומרת כמה אור יש בכל אורך גל, זהים לכל מכשיר ולכל עין: אין ניסוי שמבחין ביניהם. במובן הזה, ורק בו, הספקטרום הוא הייצוג המלא של האור. אור צהוב ממנורת נתרן הוא כמעט תדר אחד, סביב [math]\displaystyle{ 589 }[/math] ננומטר; הצהוב של מסך הוא אדום ועוד ירוק; ואור השמש הוא רצף. אלה שלושה ספקטרומים שונים, ומנסרה מבחינה ביניהם.

העין עושה את ההפך מהמנסרה: במקום להפריד, היא מסכמת, וכמו ש־[math]\displaystyle{ 2+3 }[/math] ו־[math]\displaystyle{ 5+0 }[/math] נותנים אותו [math]\displaystyle{ 5 }[/math], ספקטרומים שונים נותנים לה אותם מספרים. ברשתית יש שלושה סוגי קולטנים (מדוכים), וכל סוג בולע אור בטווח רחב של אורכי גל, ברגישות אחרת: לסוג [math]\displaystyle{ S }[/math] השיא סביב [math]\displaystyle{ 440 }[/math] ננומטר, ל־[math]\displaystyle{ M }[/math] סביב [math]\displaystyle{ 540 }[/math] ול־[math]\displaystyle{ L }[/math] סביב [math]\displaystyle{ 565 }[/math]. שימו לב ש־[math]\displaystyle{ L }[/math] ו־[math]\displaystyle{ M }[/math] אינם "אדום" ו"ירוק": שני השיאים בצהוב־ירוק, במרחק [math]\displaystyle{ 25 }[/math] ננומטר זה מזה, ורק הזנב של [math]\displaystyle{ L }[/math] מגיע לאדום. כל סוג מוסר למוח מספר אחד, כמה אור בלע, משוקלל ברגישות שלו. העין אינה מודדת את הספקטרום; היא מסכמת אותו לשלושה מספרים, ובסכום הפירוק אובד: הצהוב של הנתרן והצהוב של המסך, שני ספקטרומים שונים, נותנים לה אותם שלושה מספרים. זה ההפך מהאוזן, שמודדת כל תדר לחוד.

הגדרה 8תגובת הצופה; מטאמרים

לצופה יש שלוש פונקציות רגישות רציפות [math]\displaystyle{ l,m,s\colon[380,780]\to[0,\infty) }[/math], כל אחת עם אינטגרל חיובי. התגובה שלו לאור בעל ספקטרום רציף [math]\displaystyle{ P }[/math] היא

[math]\displaystyle{ c(P)=\left(\int_{380}^{780}P(\lambda)\,l(\lambda)\,d\lambda,\ \int_{380}^{780}P(\lambda)\,m(\lambda)\,d\lambda,\ \int_{380}^{780}P(\lambda)\,s(\lambda)\,d\lambda\right)\in\mathbb R^{3}. }[/math]

שני אורות [math]\displaystyle{ P_1\ne P_2 }[/math] הם מטאמרים עבור הצופה אם [math]\displaystyle{ c(P_1)=c(P_2) }[/math].

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

שלוש פונקציות הרגישות של הגדרה 8, מקורבות כאן בגאוסיאנים: [math]\displaystyle{ l }[/math] בשיא [math]\displaystyle{ 565 }[/math] ננומטר, [math]\displaystyle{ m }[/math] ב־[math]\displaystyle{ 540 }[/math] ו־[math]\displaystyle{ s }[/math] ב־[math]\displaystyle{ 445 }[/math]. כל אחת היא המשקל שבו הקולטן שלה סוכם את הספקטרום: [math]\displaystyle{ \int P\,l }[/math] הוא המספר [math]\displaystyle{ L }[/math] של [math]\displaystyle{ c(P) }[/math], וכך [math]\displaystyle{ M }[/math] ו־[math]\displaystyle{ S }[/math]. שיאי [math]\displaystyle{ l }[/math] ו־[math]\displaystyle{ m }[/math] קרובים, שניהם בצהוב־ירוק.

זהו המודל הלינארי המקובל של ראיית הצבע (חוקי גראסמן; Wyszecki ו־Stiles, Color Science, 1982); הפונקציות [math]\displaystyle{ l,m,s }[/math] של העין האנושית נמדדו על ידי Stockman ו־Sharpe (2000), ועליהן מבוסס תקן CIE משנת 2006.

מצלמה עובדת באותה צורה בדיוק, עם שלושת המסננים שלה במקום [math]\displaystyle{ l,m,s }[/math]. מסך עובד בכיוון ההפוך: יש לו שלושה מקורות אור, והוא מערבב אותם כך שהתגובה של העין תהיה הנכונה.

טענה 9לכל אור יש אינסוף מטאמרים

יהי [math]\displaystyle{ P }[/math] ספקטרום רציף עם [math]\displaystyle{ P(\lambda)>0 }[/math] לכל [math]\displaystyle{ \lambda\in[380,780] }[/math]. אזי יש אינסוף ספקטרומים רציפים [math]\displaystyle{ Q\ne P }[/math], [math]\displaystyle{ Q\ge0 }[/math], עם [math]\displaystyle{ c(Q)=c(P) }[/math].

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

דוגמה 10גחלילית, בננה ומסך

גחלילית פולטת אור בפס צר סביב [math]\displaystyle{ 560 }[/math] ננומטר. קליפת בננה בשלה מחזירה כחמישית מהאור הכחול, וכ־[math]\displaystyle{ 60 }[/math] אחוז מהאור מ־[math]\displaystyle{ 550 }[/math] ננומטר ומעלה, ירוק, צהוב, כתום ואדום, עם שקע סביב [math]\displaystyle{ 680 }[/math] ננומטר, שארית הכלורופיל של הקליפה הירוקה (מדידה של Vrhel, Gershon ו־Iwan, 1994); באור שמש זה בקירוב הספקטרום שמגיע לעין. אלה שני ספקטרומים שונים מאוד: האחד גל מסודר ונקי, השני צירוף מבולגן. לשניהם תגובה דומה: הרבה [math]\displaystyle{ L }[/math] ו־[math]\displaystyle{ M }[/math], מעט [math]\displaystyle{ S }[/math], ולכן שניהם צהובים. והבננה שבתמונה שלה על מסך? המסך מדליק את הנקודות האדומות והירוקות שלו, ומעט מהכחולות; לתמונת הגחלילית, אדומות וירוקות בלבד. אין בצהוב של המסך אור צהוב כלל; המסך אינו משחזר את הספקטרום, הוא מייצר מטאמר שלו.

דוגמה 10 במספרים: למעלה הבננה, למטה הגחלילית. בכל לוח שני ספקטרומים שהם מטאמרים זה של זה: האור האמיתי, ומה שהמסך פולט כשהוא מציג את התמונה שלו. משמאל [math]\displaystyle{ c(P) }[/math], התגובה של העין, אחת לשניהם ([math]\displaystyle{ L=1 }[/math]; לבננה [math]\displaystyle{ M=0.77 }[/math], [math]\displaystyle{ S=0.15 }[/math], לגחלילית [math]\displaystyle{ M=0.90 }[/math], [math]\displaystyle{ S=0 }[/math]), ו־[math]\displaystyle{ (R,G,B) }[/math], שלושת המספרים שבקובץ התמונה: מינוני הנוריות שנותנים את אותה תגובה (הגדול [math]\displaystyle{ 1 }[/math]). שתי השלשות אינן אותו דבר: בגחלילית [math]\displaystyle{ L>M }[/math], ובכל זאת [math]\displaystyle{ G>R }[/math].

עכשיו אפשר לענות לשאלת הפתיחה: "יותר צהוב" תלוי במה מודדים. לספקטרומטר הבננה והגחלילית שונות מאוד, ואף אחת מהן אינה "צהובה"; הן שתי פונקציות. לעין הן קרובות, והשאלה היא על שלושה מספרים. ומצלמה מודדת שלושה מספרים אחרים, של המסננים שלה, שאינם [math]\displaystyle{ l,m,s }[/math]; לכן שני חפצים יכולים להיראות לנו זהים ולצאת שונים בתמונה, וגם להפך. תמונה אינה יכולה להכריע בשאלה טוב יותר מהעין, כי יש בה רק שלושת המספרים של המצלמה.

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

אנשים שונים רואים אחרת

פונקציות הרגישות [math]\displaystyle{ l,m,s }[/math] אינן אותן פונקציות אצל כל האנשים: עדשת העין מצהיבה עם הגיל ובולעת יותר כחול, ריכוז הפיגמנטים שונה, והשיאים של [math]\displaystyle{ L }[/math] ו־[math]\displaystyle{ M }[/math] זזים מעט מאדם לאדם. לכן שני אורות שהם מטאמרים עבור אדם אחד אינם בהכרח מטאמרים עבור אחר. אצל עיוורי צבעים חסר אחד מסוגי הקולטנים, התגובה היא שני מספרים בלבד, ויש הרבה יותר מטאמרים: אדום וירוק מסוימים נראים זהים.

אלפווין ופיירצ'יילד מדדו את התופעה בדיוק במקום שבו היא חשובה לטכנולוגיה: התאמה בין צבע מודפס לצבע על מסך. עשרים צופים בעלי ראיית צבעים תקינה, בגילים [math]\displaystyle{ 21 }[/math] עד [math]\displaystyle{ 56 }[/math], ראו דרך מנסרה שדה אחד שחציו דוגמה מודפסת (או שקופית) וחציו מסך, וכיוונו את הצבע במסך עד שהשדה נראה אחיד. היו שבעה צבעים, ביניהם צהוב. הספקטרום של המסך שונה לגמרי מזה של הדיו, ולכן כל התאמה כזאת היא מטאמר. התוצאות: ההתאמות של צופים שונים נבדלות זו מזו, בממוצע בכ־[math]\displaystyle{ 2.5 }[/math] יחידות CIELAB בין שני צופים (יחידה אחת היא בערך ההבדל הקטן ביותר שעין מבחינה בו), ובטווח של עד [math]\displaystyle{ 19 }[/math] יחידות; והפיזור בין אנשים היה בערך כפול מהפיזור של אדם אחד שחזר על הניסוי עשרים פעמים.

הערה: במאמר: “A metameric color-match perceived by one observer may appear to be a significant mismatch to another observer.”

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

לוח שחמט: דיגיטלי מטבעו

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

לוח שחמט הוא [math]\displaystyle{ 64 }[/math] משבצות, וכל משבצת ריקה או מכילה אחד מ־[math]\displaystyle{ 12 }[/math] כלים (שישה סוגים בשני צבעים). זו סדרה של [math]\displaystyle{ 64 }[/math] סמלים מתוך [math]\displaystyle{ 13 }[/math], ייצוג דיגיטלי במובן של הגדרה 1, בלי שום מדידה ובלי שום אובדן. הניחוש הטבעי: המצב של המשחק הוא התמונה של הלוח. הניחוש שגוי, כי חוקי המשחק תלויים בעוד דברים:

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

דוגמה 11שני לוחות זהים

הפתיחה הספרדית אחרי 1.e4 e5 2.Nf3 Nc6 3.Bb5 a6 4.Ba4 Nf6, אחת העמדות הנפוצות בשחמט; המהלך הטבעי של לבן עכשיו הוא להצריח. בלוח השני אותה עמדה בדיוק, אבל הגיעו אליה אחרי 5.Kf1 Ng8 6.Ke1 Nf6: המלך הלבן הלך ל־f1 וחזר, וההצרחה אסורה לו לתמיד. התמונה זהה, המהלכים החוקיים שונים, ולכן גם ערך המצב יכול להיות שונה.

דוגמה 11: שני לוחות זהים, ומתחת לכל אחד ה־FEN שלו. מימין העמדה אחרי 4...Nf6, וזכויות ההצרחה KQkq; משמאל אותה עמדה אחרי שהמלך הלבן הלך ל־f1 וחזר (החבל) והפרש השחור חזר ל־f6, ונשארו רק kq של שחור. התמונה אחת, המצבים שניים.

הייצוג המקובל של מצב, FEN, כולל את כל אלה בשורה אחת. מצב הפתיחה:

rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

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

בלשון הפרק: התמונה של הלוח מקבצת יחד מצבים שחייבים להבחין ביניהם. מצד שני, ההיסטוריה המלאה של המשחק מבחינה יותר מדי: שני משחקים שהגיעו לאותו לוח עם אותן זכויות בסדר מהלכים אחר הם אותו מצב, וממנו והלאה הכול זהה. הייצוג הנכון נמצא ביניהם, והוא בדיוק מה שמשפיע על המשך המשחק. ביחידה 12 נראה שהקלט של AlphaZero כולל, מלבד הכלים, את זכויות ההצרחה, את תור מי, את מונה חמישים המהלכים ואת מספר החזרות של המצב. ושאנון, שפתח את הפרק הזה, העריך ב־1950 שיש כ־[math]\displaystyle{ 10^{43} }[/math] מצבים; טבלה של כולם לא תיבנה לעולם, ולכן צריך ללמוד.

זיכרון מלא מול זיהוי דפוסים

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

סיכום: מה נשמר ומה אבד

כל וקטור בהמשך הקורס, קול, תמונה, טקסט מקודד, לוח משחק, עבר בדרך הזאת או בדומה לה, והשאלה "מה נשמר ומה אבד" תחזור בכל יחידה.

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

טביעת אצבע

מקור מרכזי. Shannon (1949), Communication in the Presence of Noise, כ־8,000 ציטוטים; לצדו Alfvin & Fairchild (1997), Observer Variability in Metameric Color Matches, כ־200; מודל הצופה לפי Wyszecki & Stiles (1982), Color Science.

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

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

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

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

המונחים של הפרק

signal — אות; sampling — דגימה; aliasing — קיפול תדרים; quantization — קוונטיזציה; digital representation — ייצוג דיגיטלי; information loss — אובדן מידע; metamer — מטאמר; state representation — ייצוג מצב.

ראו גם

פתח דבר ← יחידה 1: מהעולם אל הדאטה ← יחידה 2: פרספטרון ← יחידה 5: הפצה לאחור

שיטות מתמטיות בבינה מלאכותית - ארז שיינר: כל יחידות הקורס