Thunder Bird
Communication & Improvement
posts - 47,  comments - 155,  trackbacks - 0
求多维函数极值的一种算法,由Nelder和Mead提出,又叫单纯形算法,但和线性规划中的单纯形算法是不同的,由于未利用任何求导运算,算法比较简单,但收敛速度较慢,适合变元数不是很多的方程求极值,算法的基本思想如下:
给定n个特征,可以构造一个具有n+1个顶点的单纯形,初始化时需(n+1)*n维矩阵(看成是有n+1个顶点的单纯形) ,矩阵的每一行为n元向量,x0为第一行,xi=x0+r*ei,r为对问题的特征长度大小的估计值,ei为单位向量,x0可初始化为全为1的向量,即认为每个特征权重是相同的,然后选取其余的,在选取过程中,r可以取相同的值也可以取不同的值(r可以看作是对第i个特征权重的调整)  。
算法运行过程(以机器翻译中的rerank为例):
 假定BLEU=f(特征的和),对n+1个顶点(n维向量)分别计算BLEU值(取相反数),然后从中选出BLEU(相反数)最大,次大和最小的三个点,算法每次都是把其中的最大点对应的各权重进行调整,使其变小向最小点靠拢,调整完毕后,计算其对应的BLEU,再从这些BLEU中选出BLEU(相反数)最大,次大和最小的三个点,一直迭代下去,直到最高点到最低点的比率范围合适或达到最大迭代次数为止。
源码:
double famoeb(double x[],vector<double> feat)
{//计算所有特征*权重的和
 double y=0.0;
 for(int i=0;i<FeatNum;i++)
 {
  y+=x[i+1]*feat[i];
 }
 return y;
}
//单纯形算法
void amoeba(double p[],double y[],int mp,int np,int ndim,double ftol,int& iter)
{
 int i,j,ihi,inhi,mpts,nmax=20;
 double ypr,yprr,rtol,alpha=1.0;
 double beta=0.5;
 double gamma=2.0;
 int itmax=500;
 double pr[21],prr[21],pbar[21];
 mpts=ndim+1;
 iter=0;
 do
 {
  int ilo=1;
  if(y[1]>y[2])
  {
   ihi=1;
   inhi=2;
  }
  else
  {
   ihi=2;
   inhi=1;
  }
  for(i=1;i<=mpts;i++)
  {//寻找函数值中的最大,最小和次大值
   if(y[i]<y[ilo])
   {
    ilo=i;
   }
   if(y[i]>y[ihi])
   {
    inhi=ihi;
    ihi=i;
   }
   else
   {
    if(y[i]>y[inhi])
    {
     if(i!=ihi)
     {
      inhi=i;
     }
    }
   }
  }//结束寻找各种函数极值
  rtol=2.0*fabs(y[ihi]-y[ilo])/(fabs(y[ihi])+fabs(y[ilo]));//计算从最高点到最低点的比率范围,如合适则返回
  if(rtol<ftol)
  {
   erase(pbar,prr,pr);
   return;
  }
  if(iter==itmax)//如到了最大的迭代次数,则返回
  {
   cout<<"amoeba exceeding maximum iterations."<<endl;
   return;
  }
  iter=iter+1;//进行下一次迭代
  for(j=1;j<=ndim;j++)
  {
   pbar[j]=0.0;
  }
  for(i=1;i<=mpts;i++)
  {
   if(i!=ihi)
   {
    for(j=1;j<=ndim;j++)
    {
     pbar[j]=pbar[j]+p[(i-1)*np+j];
    }
   }
  }
  for(j=1;j<=ndim;j++)
  {
   pbar[j]=pbar[j]/ndim;
   pr[j]=(1.0+alpha)*pbar[j]-alpha*p[(ihi-1)*np+j];//求反射点
  }
  vector<int> BestNo;
  ChooseOneBest(pr,numSentences,alldata,StartEndIndices,BestNo);
  //开始计算BLEU值
  vector<pairnum> initialScore(N_gram);
  double referenceLength=0.0;//参考翻译总长度
  for(int k=0;k<numSentences;k++)
  {
   int sent=BestNo[k];//当前句子的最好候选翻译的序号
   for(int l=0;l<N_gram;l++)
   {
    initialScore[l].left+=alldata[sent].ngram_data[l].left;
    initialScore[l].right+=alldata[sent].ngram_data[l].right;
   }
   referenceLength+=alldata[sent].closest_length;
  }
  ypr=-BLEU(initialScore,referenceLength);//计算本轮lamda所对应的bleu
  if(ypr<=y[ilo])
  {//得到一个比最佳点稍好的结果,用gamma做一次外推
   for(j=1;j<=ndim;j++)
   {
    prr[j]=gamma*pr[j]+(1.0-gamma)*pbar[j];
   }
   vector<int> BestNo1;
   ChooseOneBest(prr,numSentences,alldata,StartEndIndices,BestNo1);
   //开始计算BLEU值
   vector<pairnum> initialScore1(N_gram);
   double referenceLength1=0.0;//参考翻译总长度
   for(int m=0;m<numSentences;m++)
   {
    int sent=BestNo1[m];//当前句子的最好候选翻译的序号
    for(int n=0;n<N_gram;n++)
    {
     initialScore1[n].left+=alldata[sent].ngram_data[n].left;
     initialScore1[n].right+=alldata[sent].ngram_data[n].right;
    }
    referenceLength1+=alldata[sent].closest_length;
   }
   yprr=-BLEU(initialScore1,referenceLength1);//计算本轮lamda所对应的bleu
   if(yprr<y[ilo])
   {//以扩张点prr作为新的单纯形中的点
    for(j=1;j<=ndim;j++)
    {
     p[(ihi-1)*np+j]=prr[j];
    }
    y[ihi]=yprr;
   }
   else
   {//以反射点pr作为单纯形中得点
    for(j=1;j<=ndim;j++)
    {
     p[(ihi-1)*np+j]=pr[j];
    }
    y[ihi]=ypr;
   }
  }
  else
  {//反射点不如最佳点,同次高点比较
   if(ypr>=y[inhi])
   {//反射点不如次高点,取一个中等程度低的点作一次一维收缩
    if(ypr<y[ihi])
    {
     for(j=1;j<=ndim;j++)
     {
      p[(ihi-1)*np+j]=pr[j];
     }
    }
    y[ihi]=ypr;
    for(j=1;j<=ndim;j++)
    {
     prr[j]=beta*p[(ihi-1)*np+j]+(1.0-beta)*pbar[j];
    }
    vector<int> BestNo2;
    ChooseOneBest(prr,numSentences,alldata,StartEndIndices,BestNo2);
    //开始计算BLEU值
    vector<pairnum> initialScore2(N_gram);
    double referenceLength2=0.0;//参考翻译总长度
    for(int s=0;s<numSentences;s++)
    {
     int sent=BestNo2[s];//当前句子的最好候选翻译的序号
     for(int t=0;t<N_gram;t++)
     {
      initialScore2[t].left+=alldata[sent].ngram_data[t].left;
      initialScore2[t].right+=alldata[sent].ngram_data[t].right;
     }
     referenceLength2+=alldata[sent].closest_length;
    }
    yprr=-BLEU(initialScore2,referenceLength2);//计算本轮lamda所对应的bleu
    if(yprr<y[ihi])
    {//以prr作为新单纯形中的点
     for(j=1;j<=ndim;j++)
     {
      p[(ihi-1)*np+j]=prr[j];
     }
     y[ihi]=yprr;//更新当前最高点出的函数值
    }
    else
    {//单纯性太大,缩小原来的单纯形
     for(i=1;i<=mpts;i++)
     {
      if(i!=ilo)
      {
       for(j=1;j<=ndim;j++)
       {
        pr[j]=0.5*(p[(i-1)*np+j]+p[(ilo-1)*np+j]);
        p[(i-1)*np+j]=pr[j];
       }
       vector<int> BestNo3;
       ChooseOneBest(pr,numSentences,alldata,StartEndIndices,BestNo3);
       //开始计算BLEU值
       vector<pairnum> initialScore3(N_gram);
       double referenceLength3=0.0;//参考翻译总长度
       for(int u=0;u<numSentences;u++)
       {
        int sent=BestNo3[u];//当前句子的最好候选翻译的序号
        for(int v=0;v<N_gram;v++)
        {
         initialScore3[v].left+=alldata[sent].ngram_data[v].left;
         initialScore3[v].right+=alldata[sent].ngram_data[v].right;
        }
        referenceLength3+=alldata[sent].closest_length;
       }
       y[i]=-BLEU(initialScore3,referenceLength3);//计算本轮lamda所对应的bleu
      }
     }
    }
   }
   else
   {//反射点好于次高点,以反射点pr作为单纯形中得点
    for(j=1;j<=ndim;j++)
    {
     p[(ihi-1)*np+j]=pr[j];
    }
    y[ihi]=ypr;
   }
  }
 }while(1);
}
posted on 2006-01-17 13:22 Thunder 阅读(11767) 评论(10)  编辑 收藏 引用

FeedBack:
# re: Nelder-Mead(simplex,“单纯形”)算法
2006-02-25 09:30 | 关学生
你好,我最近看到的一篇文章,上面有这句话:“The Nelder-Mead simplex search method was used to identify the control parameters.”请问这个方法说的跟你所说的“单纯形”算法是一个意思吗?这个方法可以用来便是控制参数吗?  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2006-02-25 10:38 | Thunder
应该就是这个算法,这个算法是用来训练参数的,主要是求维数比较小(<20)得多元极小化的算法  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2006-09-13 11:39 |
谢谢!  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2007-05-12 12:20 | kira
有该程序的matlab版吗?  回复  更多评论
  
# Nelder-Mead(實例)算法
2008-04-06 21:20 |
Nelder Mead簡單的實例會不會較易於另人瞭解,謝謝  回复  更多评论
  
# 单纯形计算线性规划题目
2008-04-29 13:11 | 轻悠
哪位高手帮我用单纯性法计计算一道题o
是非感谢!!  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2010-05-09 14:36 | zhenzhu
怎么样用matlab实现干算法 谢谢  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2010-05-09 14:38 | zhenzhu
哦 上面的‘干’写错了,应该是‘该’。我是想知道Nelder-Mead 算法在MATLAB里如何实现,解决最优化问题 谢谢  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2010-05-16 15:48 | Hexyl
@zhenzhu
fminsearch  回复  更多评论
  
# re: Nelder-Mead(simplex,“单纯形”)算法
2010-12-24 14:58 | jspanwen
@zhenzhu
matlab里面有个函数叫做fminsearch,这个函数就是用的这个算法,所以不用编写代码就能在matlab里面方便实现  回复  更多评论
  
只有注册用户登录后才能发表评论。

<2012年6月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(8)

随笔档案

相册

搜索

  •  

最新评论

阅读排行榜

评论排行榜