لسو

**لَسو** یکی از روش‌های تنظیم مدل برای انتخاب ویژگی و جلوگیری از بیش‌برازش در رگرسیون است که انتخاب متغیر و نرمال سازی را به منظور افزایش دقت پیش‌بینی و تفسیرپذیری مدل آماری حاصل انجام می‌دهد. این روش باعث می‌شود بسیاری از پارامترهای مدل نهائی صفر شده و مدل به اصطلاح خلوت شود. در روش لَسو نُرمِ L_1 به تابع هزینه اضافه می‌شود.   

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

## تاریخچه
لسو به منظور بهبود دقت پیش‌بینی و تفسیرپذیری مدل‌های رگرسیون معرفی شد. در این روش، مجموعه کاهش یافته ای از متغیرها برای استفاده در یک مدل انتخاب می شوند.

لسو به طور مستقل در سال ۱۹۸۶ در زمینه ژئوفیزیک توسعه یافت و در سال ۱۹۹۶ توسط آماردان رابرت تیبشیرانی ترویج شد. این روش، دقت پیش‌بینی را بهبود بخشیده و با کاهش ضرایب خاصی از مدل به صفر، تأثیر آنها در پیش‌بینی نهایی را از میان می برد. با وجود شباهت میان این روش و رگرسیون خط الراس، عملکرد آنها متفاوت است. در رگرسیون خط الراس، اندازه مجموع توان های دوم ضرایب از مقدار ثابتی کوچک تر شده، اما خود ضرایب صفر نمی شوند (انتخاب متغیر انجام نمی پذیرد).

## تعریف ریاضی
اگر در مسئله رگرسیون، داده‌ها را به صورت D = \{({x_{1}}, y_1), \cdots , ({x_{N}}, y_N)\}  نمایش دهیم، هدف بدست آوردن y به عنوان ترکیبی خطی از x  است یعنی x^T \beta + \beta_0 . رگرسیون خطی معمولی به شکل پایین در پی یافتن \beta  و \beta_0  بهینه است به طوری که خطای میانگین مربعات را کمینه کند:

 \min_{ \beta_0, \beta } \left\{ \frac{1}{N} \sum_{i=1}^N (y_i - \beta_0 - x_i^T \beta)^2 \right\}  

حال اگر داده‌ها را در ماتریس X  و بردار Y  بگنجانیم، مسئله به عبارت پایین تغییر شکل می‌دهد:

 \min_{ \beta \in \mathbb{R}^p } \left\{ \frac{1}{N} \left\| Y - X \beta \right\|_2^2 \right\}  
دو دلیل کلی برای تغییر و بهبود روش خطای میانگین مربعات وجود دارد. مورد اول اینکه پیچیدگی مدل‌های پارامتری با تعداد پارامترهای مدل و مقادیر آن‌ها سنجیده می‌شود. هرچه این پیچیدگی بیشتر باشد خطر بیش‌برازش برای مدل بیشتر است. پدیدهٔ بیش‌برازش زمانی رخ می‌دهد که مدل به‌جای یادگیری الگوهای موجود در داده، خود داده را به خاطر می‌سپارد. در این حالت، مدل برای آن مجموعه دادهٔ به‌خصوص خوب عمل می‌کند اما برای داده‌های مشابه دیگر عملکرد خوبی ندارد، که یعنی عمل یادگیری به خوبی انجام نشده‌است. در این حالت مدل، بایاس کم و واریانس زیادی دارد و در واقع بیش‌برازش اتفاق افتاده است. برای جلوگیری از بیش‌برازش در مدل‌های خطی مانند رگرسیون خطی یا رگرسیون لجستیک، یک «جریمه» به تابع هزینه اضافه می‌شود تا از افزایش پارامترها جلوگیری شود. به این کار تنظیم مدل گفته می‌شود. 

در روش لَسو ضریبی از نُرمِ L_1 به تابع هزینه اضافه می‌شود:

 \min_{ \beta \in \mathbb{R}^p } \left\{ \frac{1}{N} \left\| Y - X \beta \right\|_2^2 + \lambda \| \beta \|_1 \right\} 

اضافه کردن ضریبی از نُرمِ L_1 به تابع هزینه معادلِ ایجاد محدودیتی بر روی نُرمِ L_1 است:

 \min_{ \beta \in \mathbb{R}^p } \left\{ \frac{1}{N} \left\| Y - X \beta \right\|_2^2 \right\} \text{ subject to } \| \beta \|_1 \leq t 
که منظور از \| v \|_p در واقع، نُرمِ \ell^p است که به صورت زیر محاسبه می‌شود:
 
\| v \|_p = \left( \sum_{i=1}^N | v_i |^p \right)^{1/p}استفاده از این باعث می‌شود بسیاری از پارامترهای مدل نهائی که دارای کم‌ترین میزان اهمیت هستند، صفر شده و مدل به اصلاح خلوت شود. بدین ترتیب بایاس مقداری افزایش یافته اما واریانس کاهش می‌یابد. بنابراین لَسو به طور کلی می‌تواند منجر به افزایش دقت مدل شود. 

هدف دیگری که استفاده از این روش دنبال می‌کند، افزایش قابلیت تبیین مدل است که با کاهش تعداد پارامترهای تخمین‌گر انجام می‌شود.

در نرمال سازی لسو، اگر Y بردار n \times 1 ، X بردار n \times d ، \epsilon  \theta^* بردار d \times 1 مقادیر پارامتر واقعی و \hat{\theta} جواب باشد، آنگاه

\frac{1}{2n} ||X(\hat{\theta} - \theta^*)||^2 \leq \epsilon^T \frac{X(\hat{\theta} - \theta^*)}{n} + \lambda_n (||\theta^*||_1 - ||\hat{\theta}||_1)

اثبات:

\frac{1}{2n} (||\epsilon||^2 +  ||X(\hat{\theta}  - \theta^*)||^2 - 2 \epsilon^T {X(\hat{\theta} - \theta^*)} ) + \lambda_n ( ||\hat{\theta}||_1) = \frac{1}{2n} || \epsilon - X(\hat{\theta} - \theta^*)||^2 + \lambda_n ( ||\hat{\theta}||_1)

= \frac{1}{2n} ||Y - X\theta\hat ||^2 + \lambda_n ( ||\hat{\theta}||_1)

\leq \frac {1}{2n} ||Y-X \theta^* ||^2 + \lambda_n||\theta^*||_1

= \frac {1}{2n} ||\epsilon||^2 + \lambda_n ||\theta^*||_1

## سرعت بخشیدن به لسو
برای تسریع لسو، باید مفروضات دیگری در موردX وجود داشته باشد. این مفروضات همچنین سازگاری تخمین \theta
 را نیز تضمین می کنند. یک شرط بسیار مفید، شرط مقدار ویژه محدود شده است. برای تعریف شرط، باید چندین نماد را معرفی کنیم. برای S \subset \{1,2,...,d\}   و \alpha > 0، داریم

C(\alpha , S) = \{ \Delta \in \Bbb{R}^d : ||\Delta_Sc||_1 \leq \alpha ||\Delta_S||_1 \}

متغیر X  شرط محدودیت مقدار ویژه RE(\alpha , \kappa) روی   S = {1,...,d} \neq \empty را برآورده می کند اگر

\frac {1}{n} ||X \Delta ||^2 \geq \kappa ||\Delta||^2 for \, all \, \Delta \in C(\alpha , S)

برای فهم بهتر، تصور کنید دلتا همان هت-ستار است. مطلوب این است که  ۲  کوچک باشد. دقت کنید که در این صورت ۲ کوچک است، خصوصاً اگر

\Delta \to \frac{||X \Delta||^2}{n}

در نزدیکی \hat{\theta} - \theta^* صاف باشد. برای پیشگیری از این امر، لازم است تابع فوق خمیده باشد. این شرط در صورتی محقق خواهد شد که

\frac {||X \Delta ||^2 }{n} \geq \kappa ||\Delta||^2 for \, all \, \Delta \in \Bbb{R}^d

که نتیجه خواهد داد \lambda_{min} (X^T X) \geq C_{min} > 0  اگر d>n که امکانپذیر نیست. به جای آن، حالتی را در نظر میگیریم که تابع تنها در جهات خاصی خمیده باشد. این جهات همان C(\alpha , S)  هستند که S توسط پشتیبان \theta^* یا s = { J: \theta^* \neq 0} تعریف میشود. 

## کوواریانس ارتونرمال
اکنون می توان برخی از ویژگی های اساسی برآوردگر لسو را شرح داد.

ابتدا فرض کنید که متغیرهای کمکی متعامد هستند به طوری که  x_i^T x_j = \delta_{ij}  ، که \delta_{ij}  دلتای کرونکر است، یا به طور معادل، X^T X = I ، سپس با استفاده از روش های زیرگرادیان می توان نشان داد که


\begin{align}
\hat{\beta}_j = {} & S_{N \lambda}( \hat{\beta}^\text{OLS}_j ) = \hat{\beta}^\text{OLS}_j \max \left( 0, 1 - \frac{ N \lambda }{ |\hat{\beta}^\text{OLS}_j| } \right) \\
& \text{ where } \hat{\beta}^\text{OLS} = (X^T X)^{-1} X^T y = X^T y
\end{align}

 
از S_\alpha  به عنوان عملگر آستانه نُرم یاد می شود، زیرا به جای اینکه مقادیر کوچکتر را به صفر سوق داده و مقادیر بزرگتر را دست نخورده باقی بگذارد، همه مقادیر را به سمت صفر میل می دهد (اگر به اندازه کافی کوچک باشند آنها را دقیقاً صفر می کند) 

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

**متغیرهای وابسته**

در یک مورد خاص، دو متغیر کمکی، مثلاً j و k، برای هر مشاهده یکسان هستند، به طوری که x_{(j)} = x_{(k)} ، که x_{(j),i} = x_{(k),i} . سپس مقادیر \beta_j  و \beta_k  که تابع هدف کمند را به حداقل می رساند به طور منحصر به فرد تعیین نمی شود. در واقع، اگر برخی از \hat{\beta}  که در آن \hat{\beta}_j \hat{\beta}_k \geq 0 ، سپس اگر s \in [0,1]  جایگزین کردن \hat{\beta}_j  توسط s ( \hat{\beta}_j + \hat{\beta}_k )  و \hat{\beta}_k  توسط (1 - s ) ( \hat{\beta}_j + \hat{\beta}_k ) ، در حالی که همه موارد دیگر را حفظ می کند \hat{\beta}_i  ثابت است، راه حل جدیدی ارائه می دهد، بنابراین تابع هدف کمند دارای پیوستاری از حداقل سازهای معتبر است. انواع مختلفی از کمند، از جمله متعادل‌سازی کشسان، برای رفع این نقص طراحی شده است.

## مصورسازی

برای مصورسازی محدودیت‌های اعمال شده در دو مدل رگرسیون خط الرأس  و لَسو با پارامترهای \beta_1 و \beta_2 را  توجه کنید که جمع خطای مربعات، به شکل خطوط تراز بیضوی نمایش داده می‌شود. به علاوه در مسألۀ رگرسیون ریج، ناحیه‌ای که ضرایب مدل را مشخص می‌کند از رابطه زیر به‌ دست می‌آید:


\beta_1^2 + \beta_2^2 
\le
t^2
 

که دایره‌ای به شعاع t را نمایش می‌دهد. تصویر برخورد خطوط تراز با محدوده ضرایب در رگرسیون خط الرأس در تصویر روبه‌رو نمایش داده شده است (شکل 1).

اما در لَسو، محدودیت اعمال شده روی ضرایب به صورت زیر است:


|\beta_1| + |\beta_2|
\le
t
 

که در مختصات دوبعدی ناحیه‌ای به شکل لوزی را تشکیل می‌دهد (شکل 2).

در هر دو روش اولین محل برخورد این نواحی با خطوط تراز بیضوی به عنوان جواب مسأله در نظر گرفته‌ می‌شود.

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

## پیاده‌سازی (پایتون)
با استفاده از کتابخانۀ Sickit-Learn زبان برنامه‌نویسی پایتون می‌توان مدل لَسو را به سادگی، به صورت زیر پیاده‌سازی کرد:
```python3
from sklearn.linear_model import Lasso

lasso = Lasso(alpha=0.1)
lasso.fit(X_train, y_train)
prediction= lasso.predict(X_test)
```
پارامتر تنظیم مدل در این مثال ساده برابر با 0.1 در نظر گرفته‌ شده و پس از آموزش، از مدل برای پیشبینی روی دادۀ جدید استفاده شده است.

## یادداشت‌ها

## منابع

رده:الگوریتم‌های یادگیری ماشین
رده:تحلیل رگرسیون