Joe*_*and 5 optimization matlab machine-learning convex-optimization minimization
这是我的第一篇文章stackoverflow,所以如果这不是正确的区域我道歉.我正致力于最小化L1规范化系统.
这周末是我第一次进入优化,我有一个基本的线性系统Y = X*B,X是一个n×p矩阵,B是模型系数的p-by-1矢量,Y是n-by -1输出向量.
我试图找到模型系数,我已经实现了梯度下降和坐标下降算法,以最小化L1正则化系统.为了找到我的步长我正在使用回溯算法,我通过查看渐变的范数-2来终止算法,并且如果它'足够接近'到零则终止(现在我使用0.001).
我试图最小化的函数是以下(0.5)*(范数((Y - X*B),2)^ 2)+ lambda*范数(B,1).(注意:按范数(Y,2),我指的是矢量Y的范数-2值.我的X矩阵是150乘5并且不稀疏.
如果我将正则化参数lambda设置为零,我应该收敛于最小二乘解,我可以验证我的算法都能很好地并且相当快地完成.
如果我开始增加lambda我的模型系数都倾向于零,这就是我所期望的,我的算法永远不会终止,因为渐变的范数-2总是正数.例如,lambda为1000将给出10 ^( - 19)范围内的系数,但我的渐变的norm2为~1.5,这是经过几千次迭代后,而我的渐变值全部收敛到0到1之间的某个值范围,我的步长变得非常小(10 ^( - 37)范围).如果我让算法运行的时间更长,情况没有改善,它似乎已经被卡住了.
我的梯度和坐标下降算法都收敛于同一点,并为终止条件提供相同的norm2(梯度)数.它们也很适合lambda为0.如果我使用一个非常小的lambda(比如0.001)我得到收敛,一个0.1的lambda看起来如果我跑了一两个小时会收敛,一个lambda任何更大的和收敛率很小,没用.
我有几个问题,我认为可能与问题有关?
在计算梯度时,我使用有限差分法(f(x + h)-f(xh))/(2h)),h为10 ^( - 5).关于这个h值的任何想法?
另一个想法是,在这些非常微小的台阶上,它在几乎垂直于最小值的方向上来回移动,使收敛速度变得如此之慢,以至于无用.
我的最后一个想法是,如果收敛速度极慢然后终止,也许我应该使用不同的终止方法,可能会考虑收敛速度.这是一种常见的终止方法吗?
1范数是不可区分的.这将导致许多事情的根本问题,特别是您选择的终止测试; 梯度将在最小值附近急剧变化,并且在一组度量零点上不存在.
你真正想要的终止测试将是"子梯度中有一个非常短的向量".
在|| Ax-b || _2 ^ 2 + lambda || x || _1的次梯度中找到最短向量是相当容易的.明智地选择容差eps
并执行以下步骤:
计算 v = grad(||Ax-b||_2^2).
如果x[i] < -eps
,则从中减去lambda v[i]
.如果x[i] > eps
,则将lambda添加到v[i]
.如果-eps <= x[i] <= eps
,则将数字添加[-lambda, lambda]
到v[i]
最小化v[i]
.
您可以在此处进行终止测试,将其v
视为渐变.我还建议v
在选择下一个迭代的位置时使用渐变.
归档时间: |
|
查看次数: |
937 次 |
最近记录: |