برازش حداقل مربعات – به زبان ساده
برازش منحنی به برازش یک تابع از پیش تعریف شده اطلاق میشود که متغیرهای مستقل و وابسته را به یکدیگر مربوط میکند. گام اول در محاسبه بهترین منحنی یا خط، پارامتری کردن تابع خطا با استفاده از متغیرهای اسکالر کمتر، محاسبه مشتق خطا نسبت به پارامترها و در نهایت محاسبه پارامترهایی است که تابع هزینه خطا را کمینه میکنند. در روش «برازش حداقل مربعات» (Least-Square Fitting)، به جای آنکه از قدر مطلق خطا استفاده کنیم، مربع آن را در نظر میگیریم، زیرا در این صورت، دادههای دور از منحنی برازش شده با بالا بردن مقیاس توسط اندازه خطا جریمه میشوند. این یعنی اینکه برای مثال، انحراف ۲ به اندازه ۴ در نظر گرفته خواهد شد.
بنابراین، کمینهسازی مجموع مربعات خطا منجر به برازشی میشود که خطاهای کوچکتری را در نظر میگیرد. رایجترین روش برای تعیین پارامترهایی که منحنی را مشخص میکنند، تعیین جهت کاهش خطا و یک گام کوچک در آن جهت و تکرار فرایند تا جایی است که به همگرایی برسیم. این فرایند حل تکراری پارامترها به عنوان روش «گرادیان کاهشی» (Gradient Descent) نیز شناخته میشود. در این آموزش، از محاسبات ماتریسی پایه استفاده میکنیم و آنها را برای به دست آوردن پارامترها به منظور بهترین برازش منحنی به کار میگیریم. در حالتهای خاص، جایی که تابع پیشبین در پارامترهای مجهول خطی است، یک فرم بسته از جواب شبهوارون (Pseudoinverse) را میتوان به دست آورد. در این آموزش، هر دو راهحل گرادیان نزولی و شبهوارون را برای محاسبه پارامترهای برازش بررسی میکنیم.
مشتق مرتبه اول نسبت به اسکالر و بردار
در این بخش اصول حسابان ماتریسی را بیان کرده و نشان میدهیم که چگونه باید از آن برای بیان مشتقات یک تابع استفاده کرد. ابتدا، چند نماد را معرفی میکنیم: یک اسکالر برای حرف انگلیسی کوچک و عادی مثل ، یک بردار با حرف کوچک انگلیسی و پررنگ مثل و یک ماتریس با حرف انگلیسی بزرگ و پررنگ مثل .
مشق تابع اسکالر نسبت به بردار
مشتق یک تابع اسکالر نسبت به یک بردار، برداری از مشتق تابع اسکالر نسبت به تک تک درایههای بردار است. بنابراین، برای تابع از بردار داریم:
به طور مشابه، مشتق ضرب نقطهای دو بردار و در را میتوان به صورت زیر نوشت:
به طور مشابه، داریم:
نکته: اگر تابع اسکالر بوده و برداری که نسبت به آن مشتق میگیریم دارای بعد باشد، آنگاه بعد مشتق است.
مشتق تابع برداری نسبت به اسکالر
مشتق یک تابع برداری نسبت به یک اسکالر، برداری از مشتق درایههای تابع برداری نسبت به متغیر اسکالر است. بنابراین، برای تابع از متغیر ، خواهیم داشت:
اگر بعد تابع برداری باشد، آنگاه مشتق آن نسبت به یک اسکالر دارای بعد خواهد بود.
مشتق تابع برداری نسبت به بردار
مشتق یک تابع برداری نسبت به یک بردار، ماتریسی است که درایههای آن مشتق درایههای تابع برداری نسبت به درایههای بردار هستند. بنابراین، برای تابع برداری از بردار ، داریم:
نکته: اگر تابع برداری با ابعاد بوده و برداری که نسبت به آن مشتق میگیریم، دارای بعد باشد، آنگاه بعد مشتق خواهد بود.
برای حالت خاصی که داشته باشیم:
مشتق به صورت زیر است:
برازش حداقل مربعات
مثالی که مفاهیم مذکور بالا را میتوان به آن اعمال کرد، برازش حداقل مربعات خط است. در برازش حداقل مربعات خط، هدف یافتن بردار وزنها به گونهای است که خطای بین مقدار هدف و پیشبینیهای یک مدل خطی را کمینه کند.
شرح مسئله
تعداد نقطه آموزش را در نظر بگیرید که برای هر ، بردار را به یک خروجی اسکالر نگاشت میدهد. هدف یافتن بردار خطی به گونهای است که خطای زیر کمینه شود:
که در آن، برابر با اُمین درایه و عرض از مبدأ است.
حل: بردار مستقل را با قرار دادن درایه جدید ۱ به انتهای آن و بردار را با قرار دادن در انتها افزایش میدهیم. در نتیجه، تابع هزینه به صورت زیر در خواهد آمد:
تابع هزینه بالا را میتوان به عنوان یک ضرب نقطهای از بردار خطا نوشت:
که در آن، ماتریسی با اندازه در و یک بردار با طول و برداری به طول است.
بنابراین، اکنون تابع هزینه به صورت زیر خواهد بود:
با اعمال ترانهاده در فرمول بالا، خواهیم داشت:
لازم به ذکر است که همه جملات در معادله بالا اسکالر هستند. با مشتقگیری نسبت به ، خواهیم داشت:
روش گرادیان کاهشی
کمینه زمانی به دست میآید که مشتق بالا برابر با صفر باشد. رایجترین روش مورد استفاده یک راه حل مبتنی بر گرادیان کاهشی است که در آن، از یک حدس اولیه برای شروع کرده و آن را به صورت زیر بهروز میکنیم:
میتوان صحیح بودن محاسبه تحلیلی مشتق را بررسی کرد. این کار با استفاده از روش تفاضل مرکزی قابل انجام است.
روش تفاضل مرکزی روش مناسبی است، زیرا این روش دارای خطای است، در حالی که خطای روش تفاضل مستقیم است. از سری تیلور نیز میتوان برای این منظور استفاده کرد.
روش شبهوارون
یک روش دیگر، محاسبه مستقیم بهترین جواب با صفر قرار دادن مشتق اول تابع هزینه است:
با اعمال ترانهاده، مقدار به صورت زیر به دست میآید:
مثال برازش حداقل مربعات خط
در این بخش، تعدادی داده تولید کرده و روشهای ارائه شده در بالا را به آنها اعمال میکنیم. میخواهیم بهترین خط برازش کننده را با استفاده از روشهای گرادیان کاهشی و شبهوارون محاسبه و آنها را با هم مقایسه کنیم.
دادهها را در پایتون به صورت زیر تولید میکنیم:
1## Generate toy data
2import numpy as np
3import matplotlib.pyplot as plt
4import time
5%pylab inline
6
7X = 4*np.random.rand(100)
8Y = 2*X + 1+ 1*np.random.randn(100)
9
10X_stack = np.vstack((X,np.ones(np.shape(X)))).T
11
12plt.plot(X,Y,'*')
13plt.xlabel('X')
14plt.ylabel('Y')
این دادههای نویزی به صورت زیر هستند.
برازش حداقل مربعات با استفاده از گرادیان کاهشی
همانطور که گفتیم، روش گرادیان کاهشی برای محاسبه بهترین برازش خط به کار میرود. در این روش از یک مقدار کوچک نرخ یادگیری استفاده میشود. انتخاب نرخ یادگیری خود بحث مفصلی دارد که در اینجا از بیان آن صرفنظر میکنیم. در اینجا فرض میکنیم ۰٫۰۰۰۰۵ انتخاب مناسبی برای نرخ یادگیری باشد. گرادیان با استفاده از معادلهای که پیشتر بیان کردیم، قابل محاسبه است و وزنها (یا ضرایب) در هر مرحله ذخیره میشوند.
برنامههای زیر در پایتون، پیادهسازی روش گرادیان کاهشی را نشان میدهند.
1def get_numerical_derv(W):
2 h = 0.00001
3
4 W1 = W + [h,0]
5 errpl1 = np.dot(X_stack,W1)-Y
6 W1 = W - [h,0]
7 errmi1 = np.dot(X_stack,W1)-Y
8 W2 = W + [0,h]
9 errpl2 = np.dot(X_stack,W2)-Y
10 W2 = W - [0,h]
11 errmi2 = np.dot(X_stack,W2)-Y
12
13 dJdW_num1 = (np.dot(errpl1,errpl1)-np.dot(errmi1,errmi1))/2./h/2.
14 dJdW_num2 = (np.dot(errpl2,errpl2)-np.dot(errmi2,errmi2))/2./2./h
15
16 dJdW_num = [dJdW_num1,dJdW_num2]
17 return dJdW_num
1t0 = time.time()
2W_all = []
3err_all = []
4W = np.zeros((2))
5lr = 0.00005
6h = 0.0001
7for i in np.arange(0,250):
8
9
10
11 W_all.append(W)
12 err = np.dot(X_stack,W)-Y
13 err_all.append( np.dot(err,err) )
14 XtX = np.dot(X_stack.T,X_stack)
15 dJdW = np.dot(W.T,XtX) - np.dot(Y.T,X_stack)
16 if (i%50)==0:
17 dJdW_n = get_numerical_derv(W)
18 print 'Iteration # ',i
19 print 'Numerical gradient: [%0.2f,%0.2f]'%(dJdW_n[0],dJdW_n[1])
20 print 'Analytical gradient:[%0.2f,%0.2f]'%(dJdW[0],dJdW[1])
21
22 W = W - lr*dJdW
23
24tf = time.time()
25print 'Gradient descent took %0.6f s'%(tf-t0)
26
27plt.plot(err_all)
28plt.xlabel('iteration #')
29plt.ylabel('RMS Error')
جواب حاصل از اجرای برنامه فوق به صورت نوشتاری و شکل زیر هستند:
Iteration # 0 Numerical gradient: [-1255.13,-505.70] Analytical gradient:[-1255.13,-505.70] Iteration # 50 Numerical gradient: [-264.16,-115.18] Analytical gradient:[-264.16,-115.18] Iteration # 100 Numerical gradient: [-53.40,-31.67] Analytical gradient:[-53.40,-31.67] Iteration # 150 Numerical gradient: [-8.69,-13.53] Analytical gradient:[-8.69,-13.53] Iteration # 200 Numerical gradient: [0.68,-9.32] Analytical gradient:[0.68,-9.32] Gradient descent took 0.006886 s
حال برای درک بهتر، شکلهای خط برازش شده را برای تکرارهای مختلف رسم میکنیم. برنامه و شکلها در ادامه آورده شدهاند.
1plt.figure(figsize=(15,20))
2for i in np.arange(0,8):
3 num_fig = i*30
4 Y_pred = W_all[num_fig][0]*X + W_all[num_fig][1]
5 plt.subplot(4,2,i+1)
6 plt.plot(X,Y,'*',X,Y_pred)
7 title_str = 'After %d iterations: %0.2f X + %0.2f'%(num_fig,
8 W_all[num_fig][0],W_all[num_fig][1])
9 plt.title(title_str)
برازش حداقل مربعات با روش شبهوارون
محاسباتی را که در بالا برای روش شبهوارون بیان کردیم، به صورت زیر در پایتون پیادهسازی میشود:
1t0 = time.time()
2XTX_inv = np.linalg.inv(np.dot(X_stack.T,X_stack))
3XtY = np.dot(X_stack.T,Y)
4W = np.dot(XTX_inv, XtY)
5Y_pred = W[0]*X + W[1]
6tf = time.time()
7print 'Pseudoinverse took %0.6f s'%(tf-t0)
8
9title_str = 'Predicted function is %0.2f X + %0.2f'%(W[0],W[1])
10
11plt.plot(X,Y,'*',X,Y_pred)
12plt.title(title_str)
13plt.xlabel('X')
14plt.ylabel('Y')
شکل زیر، حاصل از اجرای این برنامه است.
برازش دایره
مجموعه نقاطی را در نظر بگیرید که میخواهیم یک دایره را برای آنها برازش کنیم. همانطور که میدانیم، دایره یک تابع خطی نیست. البته، معادله یک دایره را میتوان طوری بازنویسی کرد که برحسب پارامترهای مجهول (یعنی محل مرکز و شعاع) خطی باشد. معادله دایرهای را در نظر بگیرید که مرکز آن و شعاعش است:
با بسط معادله بالا و مرتبسازی آن، داریم:
معادله بالا دارای سه مجهول ، و است و معادله یک دایره برحسب این سه پارامتر خطی است.
و را به صورت زیر تعریف میکنیم:
بنابراین، معادله برازش دایره بالا را میتوان به صورت زیر نوشت:
که در آن، .
برنامه پیادهسازی برازش دایره در پایتون به صورت زیر است:
1th = np.linspace(0,2*3.14,100)
2
3x = 2.+2*cos(th) + .8*np.random.rand(len(th))
4y = 1.+2*sin(th) + .8*np.random.rand(len(th))
5
6
7
8A = np.vstack((-2*x,-2*y,np.ones(len(x)))).T
9b = -(x**2 + y**2)
10
11ATA_inv = np.linalg.inv(np.dot(A.T,A))
12Atb = np.dot(A.T,b)
13W = np.dot(ATA_inv, Atb)
14
15x_c = W[0]
16y_c = W[1]
17r = np.sqrt( x_c**2+y_c**2 - W[2])
18
19x_fit = x_c+r*cos(th)
20y_fit = y_c+r*sin(th)
21
22plt.figure(figsize=(4,4))
23plt.plot(x,y,'go')
24plt.plot(x_fit,y_fit,'r')
25plt.axis('equal')
26
27print x_c,y_c,r
شکل زیر، نتیجه اجرای این برنامه است.
اگر علاقهمند به یادگیری مباحث مشابه مطلب بالا هستید، آموزشهایی که در ادامه آمدهاند نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای محاسبات عددی
- آموزش محاسبات عددی (مرور و حل مساله)
- مجموعه آموزشهای دروس ریاضیات
- آموزش محاسبات عددی با MATLAB
- بیش برازش (Overfitting)، کم برازش (Underfitting) و برازش مناسب — مفهوم و شناسایی
- آزمون نیکویی برازش (Goodness of Fit Test) و استقلال — کاربرد توزیع کای۲
- روش ژاکوبی — به زبان ساده
^^
سلام ممنون از آموزشتون
در قسمت شرح مسئله تابع خطایی که باید کمینه شود از کجا آمده است و اینکه چرا xij داریم درحالی که x یک بردار است و باید xi باشد؟؟
سلام بر استاد عزیز
واقعا عالی بود، خیلی خوب مبحث رو برای من باز کردید. خیلی مثالها عالی بودن، گفتم حتما از استاد عزیز، جناب حمیدی تشکر کنم.
از تیم فرادرس بخاطر سایت خوبتون ممنون و سپاسگزارم.
دستتون طلا
شاد و سلامت باشید.
امید زندی عزیز! دمت گرم و تشکر از تدریس خوبت
سلام و سپاس از زحمات گروه فرادرس
و تشکر از استاد زندی با نحوه ی عالی تدریسشون
اگر ما یک معادله دیفرانسیل داشته باشیم و بخواهیم جواب تقریبی آن را با استفاده از روش حداقل مربعات خطا(LSE) و یا روش گالرکین بدست بیاوریم چگونه بدست میاید؟
با فرض این که جواب تحلیلی یا دقیق آن را نمی دانیم.
اگه امکانش هست از این دو روش هم آموزش تهیه کنید.
البته بیشتر دنبال کدش هستم!:)
با تشکر