learning rate adaptation and stopping criterion
最近读了一篇文章,关于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个循环过程中。
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,
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!..
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!..
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.
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..
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!..
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. 카지노사이트
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
Mon, 20 Dec 2021 21:12:19 +0800
Hey, I’ve been ranking the crap out of “pre spun articles”. Quearn
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
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. 高雄頂級飯店
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
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
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? 메이저사이트
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
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! 안전놀이터
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. 안전놀이터
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. 토토사이트
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 .. 카지노사이트
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? 소액결제현금화
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. 메이저사이트
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ใหม่ล่าสุด
Sat, 26 Mar 2022 19:20:12 +0800
Hello i would really love to subscribe and read your blog posts .! Cognitive Behavioral Therapy
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. 온라인카지노
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. 먹튀검증
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? 腳架
Sun, 12 Jun 2022 21:46:03 +0800
I love to visit your web-blog, the themes are nice.’-\'-; ipad回收
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
Sat, 01 Oct 2022 23:55:06 +0800
Thanks for this excellent article. One other thing is that a lot of digital cameras come equipped with the zoom lens that enables more or less of your scene to get included by means of ‘zooming’ in and out. All these changes in concentration length are usually reflected while in the viewfinder and on significant display screen right at the back of the specific camera. adobe
Tue, 01 Nov 2022 18:49:12 +0800
This is the right weblog for anybody who desires to find out about this topic. You realize a lot its almost arduous to argue with you (not that I really would want…HaHa). You positively put a new spin on a subject thats been written about for years. Great stuff, simply great! 카지노사이트
Mon, 14 Nov 2022 00:23:25 +0800
Nice to read your article! I am looking forward to sharing your adventures and experiences. online quran teacher contact number
Fri, 18 Nov 2022 20:30:53 +0800
<p>
I am happy that I detected this blog , precisely the right information that I was looking for! . <a href="https://www.mtpolice.pro/">온라인카지노</a></p>