feng's Blog

Happy coding

learning rate adaptation and stopping criterion

feng posted @ Sun, 30 Sep 2012 01:36:08 +0800 in 未分类 , 1494 readers

最近读了一篇文章,关于Binary Multidimensional Scaling的。原文见下面的链接:

http://tedlab.mit.edu/~dr/Papers/bmds.jou.pdf

其中4.4部分讲到了关于learning rate的设置的一个经验方法,觉得讲得很好。以下谈谈自己的理解。

------------------------------------------------------------------

处理的问题,是一个无约束的优化问题。也就是说,我们希望去找到一个\(\mathbf{x}\)能够最小化\(f(\mathbf{x})\)。这里的\(\mathbf{x}\)是一个向量,如果是\(1\times1\),就是一个标量。如果我们处理的未知数是一个矩阵,那么把这个矩阵中得未知数排成一列之后,也是一个未知的向量。

 

接下来考虑如何得到这样的\(\mathbf{x}\)。其中一个经常用到的方法是梯度下降法。也就是这样的一种迭代算法

\[\mathbf{x}_{t + 1} = \mathbf{x}_t - s  \nabla{f(\mathbf{x}_t)}\]

这里的\(\mathbf{x}_t\)指的是第\(t\)次迭代时,\(\mathbf{x}\)的值。$s$是步长,$\nabla{f(\mathbf{x}_t)}$是函数在$\mathbf{x}_t$的梯度值。在梯度的相反方向上,可以期望能够找到一个新的$\mathbf{x}_{t + 1}$使得目标函数值,尽可能的小。这里的问题来了,

如何确定这个步长$s$?

 

对这个问题的研究很多。这里我们只讨论一种经验性的简单做法。首先令$s = \alpha {\|\mathbf{x}_t\|}/{\|\nabla{f(\mathbf{x}_t)}\|}$。这是因为一般情况下,我们很难确定这个梯度值的取值范围。比如说$\mathbf{x}$的取值范围是在0到1之间,而它的梯度值有可能是在100左右的位置,也可能是在0.01左右的样子。那么这是时候,直接确定$s$,比较困难。在这个时候,我们在$\nabla{f(\mathbf{x}_t)}$前面乘以一个标量${\|\mathbf{x}_t\|}/{\|\nabla{f(\mathbf{x}_t)}\|}$,起到了一个矫正的作用。我们就可以确定,如果当前的$\mathbf{x}_t$是1,那么这个矫正之后梯度方向的模也是1。接下来就考虑$\alpha$应该如何确定。

 

总的来说,是首先给定一个初始值$\alpha = 0.2$。然后根据情况,对这个$\alpha$做一定的修改。

初始值$0.2$是文章中的原话,在最近做的一个项目中,用的是$0.1$,实验进行的很好。

接下来,我们定义,或者说在实验的过程中,维护两个变量。一个是progress,一个事instability。其中progress的定义为

\[progress = \frac{S_{t} - S_{t + 1}}{|S_{t}|}\]

其中$S_{t}=f(\mathbf{x}_t)$。可以看到,如果progress小于0的话,代表$S_{t + 1}$比$S_{t}$小,目标函数值减小了,正是我们所期望的事情。如果很不幸的,progress大于0的话,说明了函数值没有减小,反而变大。这个时候,我们就需要减小一个步长$\alpha$了。按照文章中的参数,$\alpha$变为原来的0.75。根据新的$\alpha$,可以算出来新的$\mathbf{x}_{t + 1}$,从而可以得到新的$S_{t + 1}$。如果比$S_{t}$变小了,也就是这个时候progress小于0了,就进入下一个循环。否则的话,继续减小$\alpha$,直到progress小于0,或者达到了循环停止的条件。

另一个参数是instability,其定义如下

 \[instability = I_{t + 1} = 0.5 (I_{t} + \frac{|P_{t - 1} - P_{t}|}{|P_{t - 1}|})|\]

可以想象,如果我们的目标函数值能够稳定的下降的话,那么$P_{t}$将会是一个常数,代表了目标函数值下降的程度。这个时候instability就会趋近于0。也就是说,instability越小,越是我们希望的事情。它的初值设置成10,同时,我们约定,每一次$\alpha$发生变动的时候,$I_{t}$都被重置成10。接下来,在考虑,如果这个instability比较大的话,说明不是很稳定,也就是说,目标函数值下降的时快时慢,有可能函数的曲线就是这样子的,很凹凸不平。也有可能是在最优值附近,在最优值附近不停地摆动。但不管怎么说,目标函数值是下降到的,所以尽管instability很大,我们依然不去做任何事情。唯一需要做的是这样的一种情况,instability很小,说明很稳定,但是呢,progress也很小。也就是说我们的目标函数值减小的速度很慢,就像蚂蚁一样。这是情况,说明了步长$\alpha$比较小,我们需要增大这个数值。具体来说,在$progress < 0.02$并且$instability<0.2$的时候,将$\alpha$乘以1.2。

 

循环停止的条件,在这里的设置是progress小于0.01,在连续的10个循环过程中。

Avatar_small
buy youtube likes said:
Tue, 20 Apr 2021 08:37:07 +0800

Thank you again for all the knowledge you distribute,Good post. I was very interested in the article, it's quite inspiring I should admit. I like visiting you site since I always come across interesting articles like this one.Great Job, I greatly appreciate that.Do Keep sharing! Regards,

Avatar_small
Car Bluetooth Device said:
Sun, 25 Apr 2021 03:35:07 +0800

Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!..

Avatar_small
Concrete Contractor said:
Tue, 27 Apr 2021 03:35:59 +0800

Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!..

Avatar_small
NFT ART said:
Wed, 28 Apr 2021 03:36:16 +0800

I have not any word to appreciate this post.....Really i am impressed from this post....the person who create this post it was a great human..thanks for shared this with us.

Avatar_small
couple sweatshirt said:
Mon, 03 May 2021 19:31:24 +0800

I was looking at some of your posts on this website and I conceive this web site is really instructive! Keep putting up..

Avatar_small
photo booth rental said:
Sun, 23 May 2021 17:29:43 +0800

Great write-up, I am a big believer in commenting on blogs to inform the blog writers know that they’ve added something worthwhile to the world wide web!..

Avatar_small
AAA said:
Sun, 12 Dec 2021 00:12:31 +0800

This really is awesome publish as well as i like to see this particular publish. your site is actually wonderful and also you possess great personnel inside your weblog. good discussing continue the good work. 카지노사이트

Avatar_small
AAA said:
Sun, 12 Dec 2021 21:19:00 +0800

Thanks for the post and great tips.. even I also think that hard work is the most important area of getting success. acrylic keychain

Avatar_small
AAA said:
Mon, 20 Dec 2021 21:12:19 +0800

Hey, I’ve been ranking the crap out of “pre spun articles”. Quearn

Avatar_small
AAA said:
Thu, 23 Dec 2021 00:12:18 +0800

The site is very interesting, you made some compelling remarks and the matter is on point. I decided to add your blog to my bookmarks so I can return to it at a later date. instagram smm panel

Avatar_small
AAA said:
Tue, 28 Dec 2021 19:25:46 +0800

The site is very interesting, you made some compelling remarks and the matter is on point. I decided to add your blog to my bookmarks so I can return to it at a later date. 高雄頂級飯店

Avatar_small
AAA said:
Thu, 30 Dec 2021 21:09:21 +0800

But wanna state that this is very useful , Thanks for taking your time to write this. Denver to Vail Car Service

Avatar_small
AAA said:
Fri, 31 Dec 2021 14:20:02 +0800

Great work! This is the type of info that should be shared around the web. Shame on the search engines for not positioning this post higher! Come on over and visit my site . Thanks =) minecraft servers

Avatar_small
AAA said:
Sat, 01 Jan 2022 13:55:10 +0800

I tried to publish a comment earlier, yet it has not shown up. I assume your spam filter may possibly be broken? 메이저사이트

Avatar_small
AAA said:
Sat, 08 Jan 2022 03:37:47 +0800

Some genuinely wonderful work on behalf of the owner of this internet site , absolutely outstanding content material . Car Shipping

Avatar_small
AAA said:
Tue, 08 Feb 2022 18:14:01 +0800

Thanks with regard to publishing this type of excellent post! I discovered your site ideal for my personal requirements. It has fantastic as well as useful articles. Continue the great function! 안전놀이터

Avatar_small
AAA said:
Sat, 12 Feb 2022 21:01:41 +0800

With thanks for any posting plus superb recommendations.. sometimes I actually as well reckon that diligence is definitely a vey important ingredient of finding being successful. 안전놀이터

Avatar_small
AAA said:
Sun, 13 Feb 2022 21:16:32 +0800

Thanks for the blog loaded with so many information. Stopping by your blog helped me to get what I was looking for. 토토사이트

Avatar_small
AAA said:
Mon, 21 Feb 2022 16:35:19 +0800

Nicely picked details, many thanks to the author. It’s incomprehensive in my experience at present, however in common, the convenience and importance is mind-boggling. Regards and all the best .. 카지노사이트

Avatar_small
AAA said:
Wed, 23 Feb 2022 17:53:48 +0800

I’m curious to find out what blog system you have been working with? I’m experiencing some small security problems with my latest blog and I would like to find something more safe. Do you have any suggestions? 소액결제현금화

Avatar_small
AAA said:
Mon, 28 Feb 2022 21:03:42 +0800

You made some decent points there. I looked on the web for that problem and found most individuals will go coupled with along with your web site. 메이저사이트

Avatar_small
AAA said:
Mon, 21 Mar 2022 03:45:41 +0800 Great article with excellent idea!Thank you for such a valuable article. I really appreciate for this great information.. สล็อตpgใหม่ล่าสุด
Avatar_small
AAA said:
Sat, 26 Mar 2022 19:20:12 +0800

Hello i would really love to subscribe and read your blog posts .! Cognitive Behavioral Therapy

Avatar_small
AAA said:
Sat, 09 Apr 2022 17:07:30 +0800

Nice to be visiting your blog again, it has been months for me. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, great share. 온라인카지노

Avatar_small
AAA said:
Wed, 25 May 2022 04:35:40 +0800

I love what you guys are up too. Such clever work and exposure! Keep up the very good works guys I’ve incorporated you guys to my own blogroll. 먹튀검증

Avatar_small
AAA said:
Fri, 03 Jun 2022 20:46:15 +0800

Thanks , I have recently been looking for info approximately this subject for a long time and yours is the best I’ve discovered till now. But, what about the conclusion? Are you sure concerning the source? 腳架

Avatar_small
AAA said:
Sun, 12 Jun 2022 21:46:03 +0800

I love to visit your web-blog, the themes are nice.’-\'-; ipad回收

Avatar_small
qqhow said:
Thu, 23 Jun 2022 17:00:46 +0800

You made some decent points there. I looked over the internet for that problem and located most people may go coupled with with all your site. slotxo

 

============================

 

I was rattling glad to find this web site on bing, just what I was looking for : joker123


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter