交叉熵法数学表示法的转换

Question

我想在我正在使用的算法中添加参数选择的交叉熵方法。问题是我不太懂数学表示法，也找不到用代码写成的交叉熵方法的这个版本。

在这张图像中，可以看到伪代码中的算法：

http://i.imgur.com/PXbFOhq.png (我不能把它粘贴在这里，因为它有很多胶乳)

摘自本文：thesis.pdf (第69页)

你能帮我把它翻译成c#或其他语言，甚至英语吗？

谢谢!

Answer 1

在罗伯特·多迪尔( Robert Dodier )澄清后，这在某种程度上帮助了我，但在另一些方面却让我更加困惑。之后，我回到了我所见过的交叉熵法的红宝石代码中，但我认为它与我试图“翻译”的算法不完全一样。随着新发现的知识(从澄清)，我看到它确实是相同的算法，并将它转化为c#。

原始红宝石代码：entropy.html

我把它翻译成c#：

class CrossEntropyMethod
{
    Random r = new Random();
    double objective_function(double[] vector)
    {
        double sum=0f;
        foreach (var f in vector)
        {
            sum+=(double)Math.Pow(f,2);
        }
        return -sum;
    }

    double QuadraticEquation(double[] vector)
    {
        // 5X^2 + 10X - 2 = 0 -> X=-2.183216 || X=0.183216
        double sum = 5 * Math.Pow(vector[0],2) + 10 * vector[0] - 2;
        return - Math.Abs(sum);
    }
    double QuadraticEquation2(double[] vector)
    {
        // 5X^2 + 10X - 2 = 0 -> X=-2.183216 || X=0.183216
        double sum1 = vector[0] * Math.Pow(0.183216, 2) + vector[1] * 0.183216 + vector[2];
        double sum2 = vector[0] * Math.Pow(-2.183216, 2) + vector[1] * -2.183216 + vector[2];
        return - (Math.Abs(sum1) + Math.Abs(sum2));
    }

    double random_variable(double min, double max)
    { 
        return min + ((max - min) * r.NextDouble());
    }

    double random_gaussian(double mean=0.0, double stdev=1.0)
    {
      double u1, u2, w;
      u1 = u2 = w = 0;
      do{
        u1 = 2 * r.NextDouble() - 1;
        u2 = 2 * r.NextDouble() - 1;
        w = u1 * u1 + u2 * u2;
      } while (w >= 1);

      w = Math.Sqrt((-2.0 * Math.Log(w)) / w);
      return mean + (u2 * w) * stdev;
    }

    double[] generate_sample(double[][] search_space, double[] means, double[] stdevs)
    {
      double[] vector = new double[search_space.Length];

          for (int i=0; i<vector.Length; i++)
          {
            vector[i] = random_gaussian(means[i], stdevs[i]);
            vector[i] = Math.Max(vector[i] ,search_space[i][0]);
            vector[i] = Math.Min(vector[i], search_space[i][1]);
        }

      return vector;
    }

    void update_distribution(double[][] samples, double alpha, ref double[] means, ref double[] stdevs)
    {
        for (int i=0; i< means.Length; i++)
        {
            double[] tArray = new double[samples.Length];
            for (int z = 0; z < samples.Length; z++)
            {
                tArray[z] = samples[z][i];
            }
            means[i] = alpha * means[i] + ((1.0 - alpha) * tArray.Average());
            stdevs[i] = alpha * stdevs[i] + ((1.0 - alpha) * MyExtensions.StandardDeviation(tArray));
        }
    }

    double[] search(double[][] bounds, int max_iter, int num_samples, int num_update, double learning_rate)
    {
        double[] means = new double[bounds.Length];
        double[] stdevs = new double[bounds.Length];
        for (int i=0; i< means.Count(); i++)
        {
            means[i]=random_variable(bounds[i][0], bounds[i][1]);
            stdevs[i]=bounds[i][1]-bounds[i][0];
        }
        double[] best=null;
        double bestScore=double.MinValue;
        for (int t=0; t<max_iter; t++)
        {
            double[][] samples= new double[num_samples][];
            double[] scores=new double[num_samples];
            for (int s=0; s<num_samples; s++)
            {
                samples[s]=generate_sample(bounds, means, stdevs);
                scores[s]=QuadraticEquation(samples[s]);
            }
            Array.Sort(scores,samples);
            Array.Reverse(scores);
            Array.Reverse(samples);
            if (best==null || scores.First() > bestScore)
            {
                bestScore=scores.First();
                best=samples.First();
            }
            double[][] selected = new double[num_update][];
            Array.Copy(samples,selected,num_update);
            update_distribution(selected, learning_rate, ref means, ref stdevs);
            Console.WriteLine("iteration={0}, fitness={1}", t, bestScore);
        }
      return best;
    }

    public void Run()
    {
        double[][] parameters = new double[][] { new double[] { -500, 500 }}; //QuadraticEquation parameters
        //double[][] parameters = new double[][] { new double[] { 4, 6 }, new double[] { 9, 11 }, new double[] { -3, -1} }; //QuadraticEquation2 parameters
        //double[][] parameters = new double[][] { new double[] { -5, 5 }, new double[] { -5, 5 }, new double[] { -5, 5 } }; //object_function parameters
        int maxIter = 100;
        int nSamples = 50;
        int nUpdate = 5;
        double alpha = 1;
        double[] best = search(parameters, maxIter, nSamples, nUpdate, alpha);
        string str = string.Join(" | ", best.Select(a => a.ToString("N10")).ToArray());
        Console.WriteLine("Best: " + str);
    }
}

Answer 2

嗯，它们的表示法并不是最清晰的，但我将尝试解释那些可能会令人困惑的部分。我想循环和分配对你来说不是什么问题。

• 粗体字体中的变量是向量值；普通字体中的相同名称是向量的单个元素。
• (粗体x)上升到(i)是(粗体x)的第一个值。注意(粗体x)是长度m的向量(其中m=你工作的维数)，其中有N个这样的向量，所以我从1到N。
• (mu )素数是(mu )的一个新值，即素数不是微分或其他任何东西。同样(西格玛^2次j)素数。
• (粗体x- mu)^T (粗体x- mu)是内积。标量积请注意，a^T只是(和在k上) ak。他们本来可以写出求和，但写a^ to是一种传统的速记。(上标T应该表示矩阵转置，但它适用于转置本身并不重要的情况，只是隐含的求和。)
• 圆心点表示标量乘法。

希望这足够让你走了。如有任何问题，请随时跟进。