רגרסיה לינארית ושיטות לשחזור שלה

מקור: xkcd

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

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

על מה זה?

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

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

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

מקור: ויקיפדיה

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

שיטת הסבירות המקסימלית

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

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

כעת נחליף במקום זאת и המשתנים שאנו צריכים הם:

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

וזה, בתורו, מסתכם במזעור הפונקציה הבאה:

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

פירוק QR

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

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

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

מטריקס הוא אורתוגונלי. זה מאפשר לנו להיפטר מהעבודה :

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

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

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

ירידה בשיפוע

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

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

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

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

LSQR

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

שיטת LSQR מבוססת על הליך דו-אלכסון. זהו הליך איטרטיבי, כל איטרציה מורכבת מהשלבים הבאים:


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

גישה זו היא המשמשת בעת יישום רגרסיה ליניארית ב Apache Ignite ML.

מסקנה

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

מקור: www.habr.com