שְׁאֵלָה:
באיזה אלגוריתם משתמשים רגרסיה לינארית?
Belmont
2010-08-18 18:30:32 UTC
view on stackexchange narkive permalink

בדרך כלל אני שומע על "ריבועים הכי פחות רגילים". האם זהו האלגוריתם הנפוץ ביותר המשמש לרגרסיה לינארית? האם יש סיבות להשתמש באחרת?

@hxd, חסום כל מבנה מיוחד במטריצת העיצוב, כל אלה הם אלגוריתמים $ O (mn ^ 2) $, שונים רק בגורם הקבוע.גישת הפירוק היא הרגל טוב שעובר בירושה מהמסורת של אלגברה לינארית מספרית.
@hxd, ובגלל זה התשובה שלי הותאמה לתצוגה של האלגוריתמים המעורבים.אם יש לך שאלות שאינן מכוסות על ידי פתיל זה, שקול לשאול שאלה חדשה.
שֵׁשׁ תשובות:
#1
+73
J. M. is not a statistician
2010-08-19 11:42:28 UTC
view on stackexchange narkive permalink

כדי לענות על אות השאלה, "ריבועים לפחות רגילים" אינו אלגוריתם; אלא זהו סוג של בעיה באלגברה ליניארית חישובית, אשר רגרסיה לינארית היא דוגמא לכך. בדרך כלל יש נתונים $ \ {(x_1, y_1), \ נקודות, (x_m, y_m) \} $ ופונקציה זמנית ("מודל") להתאמה לנתונים כנגד הצורה $ f (x) = c_1 f_1 (x) + \ נקודות + c_n f_n (x) $. $ F_j (x) $ נקראים "פונקציות בסיס" ויכולים להיות כל דבר, החל ממונומים $ x ^ j $ ועד פונקציות טריגונומטריות (למשל $ \ sin (jx) $, $ \ cos (jx) $) ופונקציות אקספוננציאליות ($ \ exp (-jx) $). המונח "ליניארי" ב"רגרסיה ליניארית "כאן אינו מתייחס לפונקציות הבסיס, אלא למקדמים $ c_j $, בכך שלקחת הנגזרת החלקית של המודל ביחס לכל אחד מה- $ c_j $ נותנת לך את גורם המכפל $ c_j $; כלומר $ f_j (x) $.

כעת יש $ m \ times n $ מטריצה ​​מלבנית $ \ mathbf A $ ("מטריצת עיצוב") שיש לה (בדרך כלל) יותר שורות מאשר עמודות, וכל ערך הוא בצורה $ f_j (x_i) $, $ i $ הוא אינדקס השורה ו- $ j $ הוא אינדקס העמודות. OLS היא כעת המשימה למצוא את הווקטור $ \ mathbf c = (c_1 \, \ dots \, c_n) ^ \ top $ שממזער את הכמות $ \ sqrt {\ sum \ limits_ {j = 1} ^ {m} \ שמאל (y_j-f (x_j) \ ימין) ^ 2} $ (בסימון מטריצה, $ \ | \ mathbf {A} \ mathbf {c} - \ mathbf {y} \ | _2 $; כאן, $ \ mathbf { y} = (y_1 \, \ dots \, y_m) ^ \ top $ נקרא בדרך כלל "וקטור התגובה").

ישנן לפחות שלוש שיטות המשמשות בפועל לחישוב פתרונות ריבועים זעירים: המשוואות הרגילות, פירוק QR ופירוק ערך יחיד. בקצרה, הן דרכים להפוך את המטריצה ​​$ \ mathbf {A} $ למוצר של מטריצות הניתנות לתמרון קל לפתרון עבור הווקטור $ \ mathbf {c} $.

ג'ורג 'כבר הראה את שיטת משוואות רגילות בתשובתו; פשוט פותרים את קבוצה של $ n \ times n $ של משוואות ליניאריות

$ \ mathbf {A} ^ \ top \ mathbf {A} \ mathbf {c} = \ mathbf {A} ^ \ top \ mathbf {y} $

עבור $ \ mathbf {c} $. בשל העובדה שהמטריצה ​​$ \ mathbf {A} ^ \ top \ mathbf {A} $ היא חיובית סימטרית (למחצה), השיטה הרגילה בה משתמשים היא פירוק Cholesky, אשר גורם $ \ mathbf {A} ^ \ למעלה \ mathbf {A} $ לטופס $ \ mathbf {G} \ mathbf {G} ^ \ top $, עם $ \ mathbf {G} $ מטריצה ​​משולשת תחתונה. הבעיה בגישה זו, למרות היתרון שבאפשרות לדחוס את מטריצת העיצוב $ m \ times n $ למטריצת $ n \ פעמים n $ קטנה בהרבה (בדרך כלל), היא שפעולה זו נוטה לאובדן נתונים משמעותיים זה קשור ל"מספר התנאי "של מטריצת העיצוב).

דרך טובה יותר היא פירוק QR, שעובד ישירות עם מטריצת העיצוב. זה גורם $ \ mathbf {A} $ ל- $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, כאשר $ \ mathbf {Q} $ הוא מטריצה ​​אורתוגונלית (הכפלת מטריצה ​​כזו עם השינוי שלה נותנת מטריצת זהות) ו- $ \ mathbf {R} $ הוא משולש עליון. לאחר מכן מחושב $ \ mathbf {c} $ כ $ \ mathbf {R} ^ {- 1} \ mathbf {Q} ^ \ top \ mathbf {y} $. מסיבות שלא אכנס אליהם (רק ראה טקסט אלגברי לינארי מספרי הגון, כמו זה), יש לזה מאפיינים מספריים טובים יותר משיטת המשוואות הרגילות.

אחת וריאציה בשימוש בפירוק QR היא שיטת של משוואות סמי-נורמליות. בקצרה, אם יש את הפירוק $ \ mathbf {A} = \ mathbf {Q} \ mathbf {R} $, המערכת הליניארית שיש לפתור לובשת את הצורה

$$ \ mathbf {R} ^ \ top \ mathbf {R} \ mathbf {c} = \ mathbf {A} ^ \ top \ mathbf {y} $$

למעשה, אחד משתמש בפירוק QR כדי ליצור את המשולש Cholesky של $ \ mathbf {A} ^ \ top \ mathbf {A} $ בגישה זו. זה שימושי במקרה בו $ \ mathbf {A} $ הוא דליל, והאחסון המפורש ו / או היווצרות $ $ mathbf {Q} $ (או גרסה מעובדת שלו) אינו רצוי או לא מעשי.

לבסוף, הדרך היקרה ביותר, אך הבטוחה ביותר לפתרון OLS היא פירוק הערך היחיד (SVD). הפעם, $ \ mathbf {A} $ מחושב כ- $ \ mathbf {A} = \ mathbf {U} \ mathbf \ Sigma \ mathbf {V} ^ \ top $, שם $ \ mathbf {U} $ ו- $ \ mathbf {V} $ שניהם אורתוגונליים, ו- $ \ mathbf {\ Sigma} $ היא מטריצה ​​אלכסונית, שהערכים האלכסוניים שלה מכונים "ערכים יחידים". כוחה של הפירוק הזה טמון ביכולת האבחונית המוענקת לך על ידי הערכים היחידים, בכך שאם אחד רואה ערכים יחודיים זעירים או יותר, סביר להניח שבחרת מערך בסיס לא לגמרי עצמאי, ובכך נחוץ ניסוח מחדש של המודל שלך. ("מספר התנאי" שהוזכר קודם לכן קשור למעשה ליחס בין הערך היחיד הגדול ביותר לקטן ביותר. היחס כמובן הופך להיות עצום (והמטריצה ​​לפיכך אינה מותנית) אם הערך היחיד הקטן ביותר הוא "זעיר" .)

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

הסבר נחמד!
איך מחשבים את 'R ^ {- 1} Q ^ T y` אם A אינו מרובע?האם אתה מוריד את אפס השורות ב- R?
@bhan, אני מניח את גרסת ה"חסכון "(או" הדק ") של פירוק QR, כאשר $ \ mathbf R $ הוא מרובע ו- $ \ mathbf Q $ יש את אותם המידות כמו מטריצת העיצוב.משהו שתוכל לעשות: חפש את ההבדל בין "QR מלא" לבין "QR דק".
@J.M.המלצות על "ספר טוב לסטטיסטיקה חישובית ואלגברה לינארית מספרית"?באמת רוצה ללמוד עוד.
@hxd, מעל לראש ראשי: Monahan לסטטיסטיקה חישובית, ו- Golub / van Loan לאלגברה לינארית מספרית.
@J.M.באמת אוהב את התשובה שלך, ברצונך לשפר אותה על ידי כיסוי של שיטות נוספות, כגון LU, Cholesky ושיטות איטרטיביות כגון שיפוע הגון?
אם עברת על ההודעה שלי, @hxd, היית רואה שכבר כיסיתי את Cholesky.LU לא באמת משמש לפתרון בעיות בריבועים קטנים ביותר, מכיוון שהוא לא מנצל את מבנה הבעיה.מעולם לא שמעתי על ירידת שיפוע המשמשת לריבועים קטנים ביותר;אם יש לך מידע על כך, כתוב כתוב תשובה נפרדת.
@hxd, לבעיות * לא לינאריות *, בטח.שיטות אופטימיזציה הן דרך יקרה לפתור בעיה * לינארית *.
#2
+34
George Dontas
2010-08-18 21:19:28 UTC
view on stackexchange narkive permalink

לגבי השאלה בכותרת, אודות מהו האלגוריתם המשמש:

בפרספקטיבה אלגברה לינארית, אלגוריתם הרגרסיה הליניארית הוא הדרך לפתור מערכת ליניארית $ \ mathbf {A} x = b $ עם יותר משוואות מאשר לא ידוע. ברוב המקרים אין פתרון לבעיה זו. וזה מכיוון שהווקטור $ b $ אינו שייך למרחב העמודה $ \ mathbf {A} $, $ C (\ mathbf {A}) $.

הקו הישר הטוב ביותר הוא זה שהופך את השגיאה הכוללת $ e = \ mathbf {A} x-b $ לקטן ככל שנדרש. ונוח לחשוב שהוא קטן באורך בריבוע, $ \ lVert e \ rVert ^ 2 $, מכיוון שהוא לא שלילי, והוא שווה 0 רק כאשר $ b \ ב- C (\ mathbf {A}) $.

הקרנת (אורתוגונלית) הווקטור $ b $ לנקודה הקרובה ביותר בחלל העמודה של $ \ mathbf {A} $ נותן את הווקטור $ b ^ * $ הפותר את המערכת (הרכיבים שלה שוכבים על הקו הישר הטוב ביותר) עם השגיאה המינימלית.

$ \ mathbf {A} ^ T \ mathbf {A} \ hat {x} = \ mathbf {A} ^ Tb \ Rightarrow \ hat {x} = (\ mathbf {A} ^ T \ mathbf {A}) ^ {- 1} \ mathbf {A} ^ Tb $

והווקטור המוקרן $ b ^ * $ ניתן על ידי:

$ b ^ * = \ mathbf {A} \ hat {x} = \ mathbf {A} (\ mathbf {A} ^ T \ mathbf {A}) ^ {- 1} \ mathbf {A} ^ Tb $

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

תן לי דוגמה פשוטה ב- R, הפותרת את בעיית הרגרסיה באמצעות אלגוריתם זה:

  library (fBasics) reg.data <- read.table (textConnection ( "bx 12 0 10 1 8 2 11 3 6 4 7 5 2 6 3 7 3 8"), כותרת = T) צרף (reg.data) <- model.matrix (b ~ x) # יירוט ו- slopeinv (t (A)% *% A)% *% t (A)% *% b # ערכים מותאמים - הווקטור המוקרן b ב- C (A) A% *% inv (t (A)% *% A)% *% t (A)% *% b # ההקרנה קלה יותר אם משתמשים במטריקס האורתוגונלי Q, # כי t (Q)% *% Q = IQ <- qr.Q (qr (A)) R <- qr.R ( qr (A)) # יירוט ושיפוע בצורה הטובה ביותר. קו <- inv (R)% *% t (Q)% *% b
# ערכים מותאמים Q% *% t (Q)% *% bplot (x, b, pch = 16) abline (best.line [1], best.line [2])  
אני מקבל שגיאה `לא הצלחתי למצוא אינב '?!
טען את חבילת fBasics. http://finzi.psych.upenn.edu/R/library/fBasics/html/matrix-inv.html
האם יש סיבה לשימוש ב- inv מ- fBasics כשזה רק מילה נרדפת לפתרון? האם לא עדיף שהתשובה לא תדרוש תלות בחבילות חיצוניות אם היא מיותרת?
@George אני אוהב את התשובה הברורה, עם זאת, אני חושב שהשאלה המקורית הייתה שאלת אלגוריתמים, ו- QR הוא רק אחד מהם.מה דעתך על LU, SVD, פירוק Cholesky?כמו כן, ב- R, השיטה עבור `lm` היא QR, יש לכך סיבות, האם תוכל להסביר מדוע?
@GeorgeDontas שים לב שיכול להיות ש- $ A ^ T A $ אינו הפיך.כפי שהוסבר ב [תשובה זו] (https://stats.stackexchange.com/a/363874/215801), אחת הדרכים להתמודד איתה היא הסרת עמודות של $ A $ שהן שילובים ליניאריים של עמודות אחרות.
#3
+6
user28
2010-08-18 19:01:06 UTC
view on stackexchange narkive permalink

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

לא מתייחס לשאלה (הדף אפילו לא מזכיר QR)
#4
+4
Dirk Eddelbuettel
2010-08-18 19:01:20 UTC
view on stackexchange narkive permalink

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

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

נכון, בגלל זה אני רואה ב- OLS "אלגוריתם" המשמש ברגרסיה לינארית ...
ריבועים הכי פחות רגילים הם אומדן. ישנם מגוון אלגוריתמים לחישוב האומדן: בדרך כלל נעשה שימוש באיזשהו פירוק מטריצות אורתוגונליות, כגון QR. ראה http://en.wikipedia.org/wiki/Numerical_methods_for_linear_least_squares
#5
+4
Jeromy Anglim
2010-08-18 19:57:01 UTC
view on stackexchange narkive permalink

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

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

לפי אלגוריתם, אני מתכוון בערך ליישום התוכנה המשמש להתאמת קו לדגם ממוצע ההפצה.
#6
+3
F. Tusell
2011-10-26 13:50:45 UTC
view on stackexchange narkive permalink

ספר ישן, ובכל זאת ספר שאני מוצא את עצמי פונה אליו שוב ושוב, הוא

Lawson, C.L. והנסון, ר.ג'יי. פתרון בעיות ריבועים קטנים ביותר , Prentice-Hall, 1974.

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

אם אתה קורא את הספר הישן הזה, אתה צריך לבדוק את * [שיטות מספריות לבעיות ריבועים קטנים] של Åke Björck (http://books.google.com/books/?id=ZecsDBMz5-IC) *, שיש בו דברים שלא נדון בלוסון / הנסון. השגרה הכלולה בספר לוסון / הנסון הינה זמינה ב- Netlib (http://netlib.org/lawson-hanson/).


שאלה ותשובה זו תורגמה אוטומטית מהשפה האנגלית.התוכן המקורי זמין ב- stackexchange, ואנו מודים לו על רישיון cc by-sa 2.0 עליו הוא מופץ.
Loading...