0

I guess there must be an algorithm that does my problem most efficiently but I haven't found it. My problem is to compute a discrete distribution for A, Prob(A). Using conditional Probability, we know: Prob(A)=Prob(A|B,C,D)*Prob(B|C,D)*Prob(C|D)*Prob(D) A,B,C,D are dependent and I only know the expressions for each term above. So in my code, I used 4 layers of for loop:

    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

In the real program I am dealing with Prob(A|B,C,D), Prob(B|C,D), Prob(C|D), Prob(D), each invokes a 21 layers of For Loop. It is terribly inefficient and slow. Matlab choked on my code and it has been 5 days that it run.

Really appreciate any idea or demo codes that help me eliminate some of the loops.

Many Thanks! Ester

4

1 回答 1

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，因为它是一组详尽可能性的概率之和——对吧？

于 2013-11-10T19:45:30.050 回答