نزول در جهت گرادیان

2 دقیقه مطالعه

نزول در جهت گرادیان

نزول در جهت گرادیان (Gradient Descent) یه الگوریتم معروفه که زیرمجموعه‌ی دسته‌ای از الگوریتم‌ها به نام الگوریتم‌های جستجوی خطی (line search) قرار می‌گیره. توی این دسته از روش‌ها ایده‌‌ی اصلی اینه که یه جهت در فضای برداری مسله پیدا می‌کنیم و به صورت تکراری در جهت اون مسیر با اندازه قدم‌هایی معیین حرکت می‌کنیم. تحت شرایطی این جور حرکت کردن میتونه منجر به جواب‌های خیلی خوبی بشه.

ایده‌‌ی کلی روش

در این روش

  • یه مقدار شروع به صورت دلخواه انتخاب می‌کنیم (به بردار مثل ) که توی دامنه‌ی جستجومون باشه.

  • بعد از اینکار یه مقدار آلفا () بنا به شرایط مساله انتخاب می‌کنیم. به این پارامتر می‌گن نرخ یادگیری الگوریتم.

  • گرادیان تابع هدف رو محاسبه می‌کنیم:

\begin{align} F(x_1, x_2, …, x_D) \rightarrow \nabla{F(x_1, x_2, …, x_D)} = [\frac{\partial{F}}{\partial{x_1}},…,\frac{\partial{F}}{\partial{x_D}}] ^ T \end{align}

  • با فورمول زیر به صورت تکراری سعی می‌کنیم به سمت نقطه‌ی بهینه حرکت کنیم:

\begin{align} X_{i + 1} = X_i - \alpha \nabla{F(X_i)},~ i=1, 2, … \end{align}

ويژگی‌های این روش به‌ شرح هستن:

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

پیاده‌سازی

برای مثال، تابع Rosenbrock رو در نظر بگیرین. این تابع یه تابع دوبعدی غیر محدب (non-convex) هست که به عنوان یه تابع محک برای بررسی عملکرد روش‌های بهینه‌سازی مورد استفاده قرار می‌گیره. این تابع شکل هندسیش یه دره‌ی عمیقه که نقطه‌ی بهینش در قرار گرفته که که برابر صفره. الگوریتم‌ها باید تا حد ممکن به کف این دره که توش نقطه‌ي کمینه قرار گرفته حرکت‌ کنن.

\begin{align} &F(x_1, x_2) = (1-x_1)^2 + 100(x_2 - x_1^2)^2 \newline &\nabla{F(x_1, x_2)} = [-2(1-x_1) -400x_1(x_2 - x_1^2), 200(x_2 - x_1^2)] ^ T \end{align}

import numpy as np
import matplotlib
import matplotlib.pylab as plt
from time import time
%matplotlib inline
matplotlib.rcParams['figure.figsize'] = (10, 10)

def f(x_1: 'component 1', x_2: 'component 2') -> 'F(x_1, x_2)':
    """Rosenbrock function in 2D, for more information please have a look at 
       `https://en.wikipedia.org/wiki/Rosenbrock_function`
    """
    return (1 - x_1) ** 2 + 100 * (x_2 - x_1 ** 2) ** 2

def gradient_of_objective_function(x_1: 'component 1', x_2: 'component 2') -> '\nabla{F(x_1, x_2)}':
    """Gradinet of Rosenbrock function in 2D, for more information please have a look at 
       `https://en.wikipedia.org/wiki/Rosenbrock_function`
    """
    return np.asarray([-2 * (1 - x_1) - 400 * x_1 * (x_2 - x_1 ** 2), 200 * (x_2 - x_1 ** 2)])

start = time() # a varibale for storing the starting time of the algorithm
gradient_function = gradient_of_objective_function # gradient of objective function to be `minimized` 
alpha = 0.005 # learning rate
x = np.asarray([0, 0]) # initial solution 
max_iteraions = 200 # number of iterations
function_evaluations = [] # a list for saving the progress of SA

for i in range(max_iteraions):
    x = x - alpha * gradient_function(x_1=x[0], x_2=x[1]) 
    function_evaluations.append(f(x_1=x[0], x_2=[1]))

end =  time() # it is all done!
print("best solution found is: ", "(" + str(x) + "," + str(function_evaluations[-1]) + ")")
print("It took about ", end - start,  " seconds")  

plt.plot(function_evaluations)
plt.xlabel('# function evaluations')
plt.ylabel('f(best_solution)')
best solution found is:  ([0.75650369  0.38004224], 18.35220503)
It took about  0.007579326629638672  seconds

gd

نظر ها

Hello! This is my first comment here so I just wanted to give a quick shout out and say I genuinely enjoy reading your articles. Can you suggest any other blogs/websites/forums that go over the same subjects? Many thanks!

Greetings, I believe your blog could possibly be having internet browser compatibility problems. Whenever I look at your web site in Safari, it looks fine however, if opening in Internet Explorer, it has some overlapping issues.

I just wanted to give you a quick heads up! Aside from that, wonderful website!

Hiya! I know this is kinda off topic nevertheless I’d figured I’d ask. Would you be interested in trading links or maybe guest authoring a blog post or vice-versa? My blog discusses a lot of the same topics as yours and I feel we could greatly benefit from each other. If you are interested feel free to shoot me an email.

I look forward to hearing from you! Fantastic blog by the way!

Hey there! Someone in my Myspace group shared this website with us so I came to check it out. I’m definitely enjoying the information. I’m bookmarking and will be tweeting this to my followers! Fantastic blog and great design and style.

Having read this I believed it was rather informative. I appreciate you taking the time and energy to put this information together. I once again find myself spending a significant amount of time both reading and posting comments. But so what, it was still worthwhile!

Howdy! I could have sworn I’ve visited this site before but after looking at many of the posts I realized it’s new to me.

Regardless, I’m definitely pleased I stumbled upon it and I’ll be bookmarking it and checking back regularly!

I enjoy what you guys are usually up too. Such clever work and exposure! Keep up the wonderful works guys I’ve added you guys to my personal blogroll.

Howdy! I realize this is kind of off-topic but I needed to ask. Does building a well-established blog such as yours take a lot of work? I’m completely new to blogging however I do write in my diary everyday. I’d like to start a blog so I can easily share my personal experience and thoughts online.

Please let me know if you have any suggestions or tips for brand new aspiring blog owners. Thankyou!

Please let me know if you’re looking for a article writer for your weblog. You have some really good articles and I think I would be a good asset. If you ever want to take some of the load off, I’d love to write some material for your blog in exchange for a link back to mine. Please shoot me an email if interested. Cheers!

Hello There. I found your blog the use of msn. This is a very neatly written article. I’ll be sure to bookmark it and return to read more of your helpful info. Thanks for the post. I’ll certainly comeback.

Hey there would you mind letting me know which webhost you’re working with? I’ve loaded your blog in 3 different browsers and I must say this blog loads a lot quicker then most. Can you recommend a good internet hosting provider at a reasonable price? Many thanks, I appreciate it!

A motivating discussion is definitely worth comment. There’s no doubt that that you need to write more about this subject, it might not be a taboo matter but usually folks don’t speak about these issues. To the next! Kind regards!!

You can definitely see your enthusiasm in the article you write. The world hopes for even more passionate writers like you who aren’t afraid to say how they believe. All the time go after your heart.

Hey there! Would you mind if I share your blog with my myspace group? There’s a lot of folks that I think would really appreciate your content. Please let me know. Many thanks

If you are going for finest contents like myself, simply pay a quick visit this web page all the time for the reason that it offers feature contents, thanks

Link exchange is nothing else except it is only placing the other person’s web site link on your page at suitable place and other person will also do similar in favor of you.

Howdy would you mind stating which blog platform you’re using? I’m going to start my own blog soon but I’m having a difficult time selecting between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design seems different then most blogs and I’m looking for something unique. P.S Apologies for being off-topic but I had to ask!

Nice blog here! Also your website loads up very fast! What host are you using? Can I get your affiliate link to your host? I wish my website loaded up as quickly as yours lol

Nice weblog right here! Additionally your website lots up fast! What web host are you using? Can I am getting your associate hyperlink in your host? I want my site loaded up as fast as yours lol

Thank you for the good writeup. It in fact was a amusement account it. Look advanced to far added agreeable from you!

By the way, how could we communicate?

Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is completely off topic but I had to tell someone!

Hi, i think that i saw you visited my blog so i came to “return the favor”.I am trying to find things to improve my web site!I suppose its ok to use a few of your ideas!!

I’m not that much of a internet reader to be honest but your sites really nice, keep it up! I’ll go ahead and bookmark your website to come back later on. Many thanks

Descargar facebook You actually make it seem so easy with your presentation but I find this matter to be really something that I think I would never understand. It seems too complex and extremely broad for me. I’m looking forward for your next post, I will try to get the hang of it! Descargar facebook

Hi! I just wanted to ask if you ever have any issues with hackers?

My last blog (wordpress) was hacked and I ended up losing a few months of hard work due to no backup. Do you have any solutions to protect against hackers?

Thanks for the marvelous posting! I really enjoyed reading it, you may be a great author. I will be sure to bookmark your blog and may come back from now on. I want to encourage one to continue your great job, have a nice morning!

Thanks for some other great article. Where else may anybody get that type of information in such an ideal way of writing? I’ve a presentation next week, and I am at the search for such information.

Descargar facebook http://twitter.com/descargar_hq descargar facebook Do you have any video of that? I’d like to find out more details.

Descargar facebook http://twitter.com/descargar_hq descargar facebook

Quest bars cheap fitnesstipsnew1 quest bars cheap 516999410492780544 quest bars cheap Having read this I thought it was rather informative.

I appreciate you finding the time and energy to put this content together. I once again find myself spending a significant amount of time both reading and leaving comments.

But so what, it was still worthwhile! Quest bars cheap fitnesstipsnew1 quest bars cheap 516999410492780544 quest bars cheap

Hey there would you mind letting me know which webhost you’re using? I’ve loaded your blog in 3 completely different browsers and I must say this blog loads a lot quicker then most. Can you suggest a good internet hosting provider at a reasonable price? Cheers, I appreciate it!

Hi! I know this is kinda off topic but I was wondering if you knew where I could find a captcha plugin for my comment form? I’m using the same blog platform as yours and I’m having problems finding one? Thanks a lot!

Hey! Do you know if they make any plugins to help with Search Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good gains. If you know of any please share. Appreciate it!

نظر خود را بنویسید

ایمیل شما منتشر نخواهد شد. فیلد های الزامی *

در حال بارگذاری...