algorithm - 使用最少的 for_loop 计算条件概率，Matlab

Question

我想一定有一种算法可以最有效地解决我的问题，但我还没有找到。我的问题是计算 A 的离散分布 Prob(A)。使用条件概率，我们知道: 概率(A)=概率(A|B,C,D)*概率(B|C,D)*概率(C|D)*概率(D) A、B、C、D 是相关的，我只知道上面每个术语的表达式。 所以在我的代码中，我使用了 4 层 for 循环:

    Solution=zeros(1,max_A)  % store Prob(A=0,1,2,3,...max_A) in each cell.
    for a =0 to max_A
        for b=0 to max_B
            for c=0 to max_C
                for d=0 to max_D
                Result= Prob(A=a|B=b,C=c,D=d)*Prob(B|C,D)*Prob(C|D)*Prob(D)
                Solution(a)= Solution(a)+Result % sum up the result 
                                                %in each iteration
                end
            end
        end
    end

在我处理Prob(A|B,C,D), Prob(B|C,D), Prob(C|D), Prob(D)的真实程序中，每一个调用一个21层的For环形。这是非常低效和缓慢的。 Matlab 卡住了我的代码，它已经运行了 5 天。

非常感谢任何帮助我消除一些循环的想法或演示代码。

非常感谢! 酯类

Answer 1

我认为它之所以这么慢，是因为您在不必要地重复计算。如果您存储部分结果，它应该更快。我真的不能尝试这个，因为你的代码不是一个完整的运行示例，但是这样的事情怎么样:

for c = 0 to max_C
    pC(c) = 0;
    for d = 0 to max_D
        pC(c) = pC(c) + Prob(C|D) * Prob(D);
    end
end
for b = 0 to max_B
    pB(b) = 0;
    for c = 0 to max_C
        pB(b) = pB(b) + Prob(B|C) * pC(c);
    end
end
for a = 0 to max_A
    pA(a) = 0;
    for b = 0 to max_B
        pA(a) = pA(a) + Prob(A|B) * pB(b);
    end
end
Solution = sum(a)

这里的pC、pB、pA是数组，用来存放中间结果。

应该可以通过预分配和向量化使这更加高效，特别是如果 Prob() 函数采用并返回向量参数，但我认为这是使您的算法在合理的时间内完成的最重要的一步。

顺便说一句，最终结果 Solution 可能不是那么有趣，因为它应该是 1，因为它是一组详尽可能性的概率总和 – 对吗？