Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose $r$ is a set of attributes with probabilities while $p$ is a set of attributes without probabilities. For example, say that $r$ = {$a$:0.4, $b$:1.0} and $p$ = {$a$, $c$}. (Here, $a.prob = 0.4$ and $b.prob = 1.0$.) There are two possible worlds for $r$: {$a$, $b$} with probability 0.4*1 = 0.4 and {$b$} with probability (1-0.4)*1 = 0.6.

I would like to efficiently compute the following equation:

$F(r,p)$ = $\sum_{r' \in 2^r} (\Pi_{a \in r'} a.c)(\Pi_{a \in r-r'} 1 - a.c)\frac{|W(r')\cap p|}{|W(r')|}$

where $W(r')$ strips off the probabilities from $r'$ (e.g., $W$({$b$:1.0}) = {$b$}). Hence, $F(r,p)$ = 0.4 * 1/2 + 0.6 * 0 = 0.2.

The above equation is clearly inefficient to compute because of the exponential size of the power set $2^r$. The approximation

$F'(r,p)$ = $\frac{\sum_{a \in r \cap p} a.prob}{\sum_{a \in r} a.prob}$

does not seem accurate because $F'(r,p)$ = 0.4 / 0.4+1 = 0.285 $\neq$ 0.2 = $F(r, p)$.

Is $F'$ still an theoretically approximate result or is there some better way to efficiently compute $F$ (say in polynomial time)? What are the related math problems?

share|cite|improve this question
How do evaluate that when $|W(r')|=0$? Also, is this notation standard anywhere? Is it ok to change it? – Douglas Zare May 11 '11 at 23:36
Good point, I only want to use non-empty r' values. The notation is not standard and can be changed. Thanks. – Steven May 12 '11 at 3:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.