پیش‌نویس:حداقل مربعات منظم

حداقل مربعات منظم (RLS) خانواده ای از روش ها برای حل مسئله حداقل مربعات طوری که از منظم سازی برای محدود کردن بیشتر راه حل استفاده می شود.

RLS به دو دلیل اصلی استفاده می شود. اولین مورد زمانی مطرح می شود که تعداد متغیرها در سیستم خطی از تعداد مشاهدات بیشتر شود. در چنین تنظیماتی، مسئله حداقل مربعات معمولی نامناسب است و در نتیجه برازش آن غیرممکن است زیرا مسئله بهینه سازی مرتبط دارای راه حل های بی نهایت زیادی است. RLS اجازه می دهد تا محدودیت های بیشتری را معرفی کند که به طور منحصر به فرد راه حل را تعیین می کند.

دلیل دوم استفاده از RLS زمانی به وجود می آید که مدل آموخته شده از تعمیم ضعیف رنج می برد. RLS می تواند در چنین مواردی برای بهبود تعمیم پذیری مدل با محدود کردن آن در زمان آموزش استفاده شود. این محدودیت می‌تواند راه‌حل را به نحوی «پراکنده» کند یا دانش قبلی را در مورد مشکل منعکس کند، مانند اطلاعات مربوط به همبستگی بین ویژگی‌ها. با نشان دادن این که روش‌های RLS غالباً معادل راه‌حل‌های حداقل مربعات هستند، می‌توان به درک بیزی از این موضوع دست یافت.

فرمولاسیون عمومی

یک نوع یادگیری ارائه شده توسط یک فضای احتمالاتی را در نظر بگیرید $(X\times Y,\rho (X,Y))$ ، $Y\in R$ . فرض کنید $S=\{x_i,y_i{\}}_{i=1}^n$ مجموعه آموزشی از $n$ جفت متغیر دوبه‌دو مستقل هم‌توزیع نسبت به $\rho$ را نشان می دهد. فرض کنید $V:Y\times R\to [0;\mathrm{\infty })$ تابع ضرر باشد، $F$ را به عنوان فضای توابع به گونه ای که ریسک مورد انتظار به صورت زیر باشد تعریف می کنیم:

$\epsilon (f)=\int V(y,f(x))d\rho (x,y)$

هدف اصلی به حداقل رساندن ریسک مورد انتظار است:

$\underset{f\in F}{\inf }\epsilon (f)$

از آنجایی که مشکل به‌طور کاملا دقیق قابل حل نیست، نیاز داریم تا چگونگی اندازه‌گیری کیفیت یک راه‌حل را بررسی کنیم. یک الگوریتم یادگیری خوب باید یک برآوردگر با ریسک کمی ارائه دهد.

به عنوان توزیع توام، توزیع $\rho$ به طور معمول ناشناخته است، ریسک تجربی درنظر گرفته شده است. برای حداقل مربعات منظم، مربع تابع ضرر به صورت زیر معرفی شده است:

$\epsilon (f)=\frac{1}{n}\sum _{i=1}^{n}V(y_i,f(x_i))=\frac{1}{n}\sum _{i=1}^n(y_i-f(x_i){)}^2$

با این حال، اگر توابع از یک فضای نسبتاً نامحدود باشند، مانند مجموعه ای از توابع مربعی انتگرال‌پذیر در $X$ ، این رویکرد ممکن است باعث بیش‌برازش مدل شود و منجر به تعمیم ضعیف شود. بنابراین، باید به نوعی پیچیدگی تابع $f$ را محدود یا جریمه کند. در کمترین مربعات منظم‌شده، این کار با انتخاب توابع از فضای بازتولید هسته هیلبرت$\mathscr{H}$ (RKHS) و همچنین با افزودن یک عبارت منظم‌سازی متناسب با نرم تابع در $\mathscr{H}$ به تابع هدف انجام می شود:

$\underset{f\in F}{\inf }\epsilon (f)+\lambda R(f),\lambda >0$

.

رگرسیون ریج (یا منظم سازی تیخونوف)

یکی از گزینه های رایج برای تابع پناتی $R$، نرم درجه 2 می باشد.

$R(w)=\sum _{j=1}^d{w}_j^2$

$\frac{1}{n}\Vert Y-\mathrm{X}w{\Vert }_2^2+\lambda \sum _{j=1}^d|w_j{|}^2\to \underset{w\in {ℝ}^d}{\min }$

متداول ترین نام ها برای این امر منظم سازی تیخونوف و رگرسیون ریدج نامیده می شود. این یک فرم برای $w$ به شکل زیر معرفی می کند:

$w=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$

نام رگرسیون ریج به این واقعیت اشاره دارد که عبارت $\lambda I$ مقدار های مثبتی در راستای قطر "ridge" ماتریس کووارینانس ماتریس $X^{T}X$ اضافه می کند.

زمانی که $\lambda =0$ یعنی در مورد حداقل مربعات معمولی، شرط $d>n$ باعث میشود که ماتریس کوواریانس نمونه رتبه کامل نداشته باشد و بنابراین نمی توان آن را معکوس کرد تا یک راه حل منحصر به فرد به دست آید. به همین دلیل است که در صورتی که $d>n$ می تواند بی نهایت راه حل برای مسئله حداقل مربعات معمولی وجود داشته باشد. با این حال، زمانی که $\lambda >0$، یعنی زمانی که از رگرسیون ریدج استفاده می شود، اضافه شدن $\lambda I$ به ماتریس کوواریانس نمونه تضمین می‌کند که همه مقادیر ویژه آن بزرگتر مساوی 0 خواهند بود، به بیان دیگر وارون پذیر خواهد شد و جواب یکتا خواهد شد.

در مقایسه با حداقل مربعات معمولی، رگرسیون ریج بدون تورش نیست. برای کاهش واریانس و میانگین مربعات خطا، مقداری تورش می پذیرد.

رگرسیون لسو

حداقل انتخاب مطلق و تابع لسو یک انتخاب دیگر می باشد. در رگرسیون لسو، تابع پنالتی لسو به صورت نرم درجه 1 انتخاب می شود.

$R(w)=\sum _{j=1}^d\left|w_j\right|$

$\frac{1}{n}\Vert Y-\mathrm{X}w{\Vert }_2^2+\lambda \sum _{j=1}^d|w_j|\to \underset{w\in {ℝ}^d}{\min }$

توجه داشته باشید که تابع پنالتی لسو محدب است اما کاملا محدب نیست. برخلاف منظم‌سازی تیخونوف، این طرح راه‌حلی با فرم بسته مناسب ندارد، در عوض راه‌حل معمولاً با استفاده از برنامه‌نویسی درجه دوم یا روش‌های بهینه‌سازی محدب عمومی‌تر و همچنین با الگوریتم‌های خاص مانند الگوریتم رگرسیون حداقل زاویه، پیدا می‌شود.

تفاوت مهم بین رگرسیون لسو و منظم سازی تیخونوف این است که رگرسیون لسو در مقابل حالت دیگر مقادیر بیشتری از $w$ را مجبور می‌کند تا برابر 0 باشد. در مقابل در حالی که منظم سازی تیخونوف مقادیر $w$ را مجبور می‌کند تا مقادیر کوچکی داشته باشند و درنتیجه مقادیر کمی از آن‌ها را مجبور به صفر بودن می‌کند. بنابراین منظم‌سازی LASSO در مواردی است که ما انتظار داریم تعداد ورودی های غیر صفر از $w$، کم باشد مناسب تر از منظم‌سازی تیخونوف می‌باشد. زمانی که ما انتظار داریم که ورودی‌های $w$ به صورت کلی کوچک باشند و نه لزوما صفر، منظم‌سازی تیخونوف مناسب‌تر است. اینکه کدام یک از این سازوکارها مناسب‌تر است به مجموعه داده های خاص موجود بستگی دارد.

علاوه بر نحوه‌ی انتخاب ویژگی که در بالا توضیح داده شد، لسو دارای محدودیت هایی است. رگرسیون ریج دقت بهتری در صورتی که $n>d$ ارائه می دهد(برای متغیرهای بسیار همبسته ). در حالت دیگر $n<d$ ، لسو حداکثر $n$ متغیر انتخاب می کند. علاوه بر این لسو تمایل دارد برخی از متغیرهای دلخواه را از گروه نمونه‌های بسیار همبسته انتخاب کند، بنابراین هیچ اثر گروه‌بندی‌ای وجود ندارد.

جریمه ℓ ₀

$\frac{1}{n}\Vert Y-\mathrm{X}w{\Vert }_2^2+\lambda \Vert w_j{\Vert }_0\to \underset{w\in {ℝ}^d}{\min }$

افراطی ترین راه برای اعمال پراکندگی این است که بگوییم قدرمطلق ضرایب $w$ مهم نیست؛ بلکه تنها چیزی که پیچیدگی را تعیین می کند تعداد ورودی های غیر صفر است. این مربوط به تنظیم است. این متناظر این می‌باشد که $R(w)$ را برابر نرم ${\ell }_0$ norm، $w$ قرار دهیم. این تابع منظم‌سازی در حالی که برای پراکندگی که تضمین می کند جذاب است، اما حل آن بسیار دشوار است زیرا انجام این کار مستلزم بهینه سازی تابعی است که حتی محدب ضعیف هم نیست. رگرسیون لسو حداقل ساده‌سازی جریمه ${\ell }_0$ می‌باشد که منجر به یک مسئله بهینه سازی محدب ضعیف می شود.

الستیک‌نت

برای هر ${\lambda }_1$ و ${\lambda }_2$ غیر منفی، هدف به صورت زیر می‌باشد:

$\frac{1}{n}\Vert Y-\mathrm{X}w{\Vert }_2^2+{\lambda }_1\sum _{j=1}^d|w_j|+{\lambda }_2\sum _{j=1}^d|w_j{|}^2\to \underset{w\in {ℝ}^d}{\min }$

فرض کنید $\alpha =\frac{{\lambda }_1}{{\lambda }_1+{\lambda }_2}$ ، سپس راه حل مساله کمینه‌سازی به صورت زیر است:

$\frac{1}{n}\Vert Y-\mathrm{X}w{\Vert }_2^2\to \underset{w\in {ℝ}^d}{\min }\text{ s.t. }(1-\alpha )\Vert w{\Vert }_1+\alpha \Vert w{\Vert }_2\le t$ برای برخی $t$ .

عبارت $(1-\alpha )\Vert w{\Vert }_1+\alpha \Vert w{\Vert }_2\le t$ را به عنوان یک تابع جریمه الاستیک‌نت درنظر بگیرید.

زمانی که α=1 باشد الستیک نت همان ریدج رگرسیون می شود و زمانی که$\alpha =0$ باشد همان لسو رگرسیون می شود. $\mathrm{\forall }\alpha \in (0,1]$ تابع جریمه الاستیک‌نت در نقطه صفر مشتق اول ندارد و به‌طور اکید محدب می‌شود. ,برای $\mathrm{\forall }\alpha >0$ ویژگی‌های هر دو رگرسیون لسو و ریدج را دارد.

یکی از ویژگی های اصلی الستیک‌نت توانایی انتخاب گروه‌هایی از متغیر‌های همبسته می باشد. تفاوت بین بردارهای وزنی برای دو نمونه‌ی $x_i$ و $x_j$ از رابطه زیر بدست می آید:

$|w_i^{*}({\lambda }_1,{\lambda }_2)-w_j^{*}({\lambda }_1,{\lambda }_2)|\le \frac{\sum _{i=1}^n|y_i|}{{\lambda }_2}\sqrt{2(1-{\rho }_{ij})}$ ، طوری‌که ${\rho }_{ij}=x_i^T{x}_j$ .

اگر $x_i$ و $x_j$ همبستگی بالایی داشته‌باشند یعنی ( ${\rho }_{ij}\to 1$ )، فاصله بین بردارهای وزنی بسیار کم است. در مورد نمونه های همبستگی منفی ( ${\rho }_{ij}\to -1$ ) نمونه های $-x_j$ را می‌توان درنظر گرفت.

فهرست جزئی از روش های RLS

لیستی از انتخاب های ممکن تابع منظم سازی$R(\cdot )$ در ادامه آمده است.

Name	Regularization function	Corresponding prior	Methods for solving
Tikhonov regularization	$\Vert w{\Vert }_2^2$	Normal	Closed form
Lasso regression	$\Vert w{\Vert }_1$	Laplace	Proximal gradient descent, least angle regression
${\ell }_0$ penalization	$\Vert w{\Vert }_0$	–	Forward selection, Backward elimination, use of priors such as spike and slab
Elastic nets	$\beta \Vert w{\Vert }_1+(1-\beta )\Vert w{\Vert }_2^2$	Normal and Laplace mixture	Proximal gradient descent
Total variation regularization	$\sum _{j=1}^{d-1}|w_{j+1}-w_j|$	–	Split–Bregman method, among others

همچنین ببینید

• Least squares
• Regularization in mathematics.
• Generalization error, one of the reasons regularization is used.
• Tikhonov regularization
• Lasso regression
• Elastic net regularization
• Least-angle regression

لینک های خارجی

• http://www.stanford.edu/~hastie/TALKS/enet_talk.pdf منظم سازی و انتخاب متغیر از طریق شبکه الاستیک (ارائه)
• حداقل مربعات منظم و ماشین‌های بردار پشتیبان (ارائه)
• حداقل مربعات منظم (ارائه)