计算函数/蒙特卡罗方法合理性的算法

Question

我正在编写一个试图复制本文开头讨论的算法的程序,

http://www-stat.stanford.edu/~cgates/PERSI/papers/MCMCRev.pdf

F是从char到char的函数.假设P1(f)是该函数的"合理性"度量.算法是:

从对函数的初步猜测开始,比如f,然后是新的函数f* -

• 计算Pl(f).
• 通过对值f进行随机转置来更改为f*,将其分配给两个符号.
• 计算Pl(f*); 如果这大于P1(f),则接受f*.
• 如果没有,翻转一个Pl(f)/ Pl(f*)硬币; 如果它出现在头上,接受f*.
• 如果硬币抛出尾巴,请留在f.

我正在使用以下代码实现此功能.我正在使用c#,但试图让每个人都更加简化.如果有更好的论坛,请告诉我.

 var current_f = Initial();    // current accepted function f
 var current_Pl_f = InitialPl();  // current plausibility of accepted function f

 for (int i = 0; i < 10000; i++)
        {
            var candidate_f = Transpose(current_f); // create a candidate function

            var candidate_Pl_f = ComputePl(candidate_f);  // compute its plausibility

            if (candidate_Pl_f > current_Pl_f)            // candidate Pl has improved
            {
                current_f = candidate_f;            // accept the candidate
                current_Pl_f = candidate_Pl_f; 
            }
            else                                    // otherwise flip a coin
            {
                int flip = Flip(); 

                if (flip == 1)                      // heads
                {
                    current_f = candidate_f;        // accept it anyway
                    current_Pl_f = candidate_Pl_f; 
                }
                else if (flip == 0)                 // tails
                {
                    // what to do here ?
                }
            }
        }

我的问题基本上是否看起来像是实现该算法的最佳方法.尽管实施了这种方法,但我似乎可能会陷入某些局部最大值/局部最小值.

编辑 - 这是Transpose()方法背后的本质问题.我使用类型为<< char,char >>的字典/哈希表,候选函数用来查看任何给定的char - > char转换.因此,转置方法只是在字典中交换两个指示函数行为的值.

    private Dictionary<char, char> Transpose(Dictionary<char, char> map, params int[] indices)
    {
        foreach (var index in indices)
        {
            char target_val = map.ElementAt(index).Value;   // get the value at the index

            char target_key = map.ElementAt(index).Key;     // get the key at the index

            int _rand = _random.Next(map.Count);   // get a random key (char) to swap with

            char rand_key = map.ElementAt(_rand).Key;

            char source_val = map[rand_key]; // the value that currently is used by the source of the swap

            map[target_key] = source_val; // make the swap

            map[rand_key] = target_val;
        }

        return map; 
    }

请记住,使用基础字典的候选函数基本上只是:

public char GetChar(char in, Dictionary<char, char> theMap)
{
     return theMap[char]; 
}

这是计算Pl(f)的函数:

    public decimal ComputePl(Func<char, char> candidate, string encrypted, decimal[][] _matrix)
    {
        decimal product = default(decimal);

        for (int i = 0; i < encrypted.Length; i++)
        {
            int j = i + 1;

            if (j >= encrypted.Length)
            {
                break;
            }

            char a = candidate(encrypted[i]);
            char b = candidate(encrypted[j]);

            int _a = GetIndex(_alphabet, a); // _alphabet is just a string/char[] of all avl chars 
            int _b = GetIndex(_alphabet, b);

            decimal _freq = _matrix[_a][_b]; 

            if (product == default(decimal))
            {
                product = _freq;
            }
            else
            {
                product = product * _freq;
            }
        }

        return product;
    }

Answer 1

暂时来说，codereview.stackexchange.com可能是一个“更好的论坛”。
不管怎样，我会快速尝试一下：

• 乍一看，显示的代码片段是该算法的正确实现。
• 算法是否会“陷入”局部极小值是与算法有关的问题，而不是与实现有关的问题。（见下面的讨论）
• 您对“最佳方法”的追求似乎是针对算法的调整（ 偏离原始算法），而不是针对实现的调整（以使其更快和/或消除一些可能的缺陷）。有关算法的注意事项，请参阅下面的讨论；对于有关实施的讨论，请考虑以下内容：
  • 确保 Flip() 方法是公平的
  • 确保 ComputePl() 正确：由于值函数中的算术精度问题，经常会出现一些错误。
  • 使用 Transpose() 方法确保公平性（等概率）。
  • 性能改进可能来自 ComputePl() 方法（未显示）中的优化，而不是主循环中的优化。

关于算法本身及其对不同问题的适用性的讨论。
简而言之，该算法是一种引导随机搜索，其中使用两个随机设备对[巨大]解空间进行采样：Transpose() 方法（每次非常轻微地修改）当前候选函数和 Flip() 方法决定[局部]次优解决方案是否应该生存。搜索由目标函数 ComputePl() 引导，该函数本身基于某个参考语料库中的一阶转换矩阵。

在这种情况下，可以通过增加选择“次优”函数的概率来避免局部最小值“焦油坑”：而不是公平的 50-50 Flip()，可以尝试保留 66% 的“次优”解决方案的概率或甚至75%。这种方法通常会延长收敛到最佳解决方案所需的代数，但是，如上所述，可以避免陷入局部最小值。

确保算法适用性的另一种方法是确保更好地评估给定函数的合理性。该算法相对成功和通用性的可能解释是

• 英语中一阶转换的分布不是很均匀（因此通过对匹配的奖励和对不匹配的惩罚来很好地模拟给定函数的合理性）。这种多维统计数据比给定语言/语料库中字符的“0 阶”分布更能适应偏离参考语料库的情况。
• 一阶转换的分布虽然是特定于语言的，但在不同语言和/或行话词汇的上下文中通常是相似的[基于所述语言]。在速记行话的情况下，事情确实会崩溃，因为元音等字母通常会被省略。

因此，为了提高算法对给定问题的适用性，请确保所使用的分布矩阵与底层文本的语言和领域尽可能匹配。