Course talk:CPSC522/Variable Elimination

Hi, Ritika,

Wonderful draft! Lots of examples and detailed explanation make it easy to understand the algorithm. Here are my scores, with some suggestions below that. Scale of 1 to 5, where 1 = strongly disagree and 5 = strongly agree:

• (5) The topic is relevant for the course.
• (4) The writing is clear and the English is good.
• (5) The page is written at an appropriate level for CPSC 522 students (where the students have diverse backgrounds).
• (4) The formalism (definitions, mathematics) was well chosen to make the page easier to understand.
• (4) The abstract is a concise and clear summary.
• (4) There were appropriate (original) examples that helped make the topic clear.
• (n) There was appropriate use of (pseudo-) code.
• (4) It had a good coverage of representations, semantics, inference and learning (as appropriate for the topic).
• (4.5) It is correct.
• (4) It was neither too short nor too long for the topic.
• (4) It was an appropriate unit for a page (it shouldn't be split into different topics or merged with another page).
• (3.5) It links to appropriate other pages in the wiki.
• (3.5) The references and links to external pages are well chosen.
• (4) I would recommend this page to someone who wanted to find out about the topic.
• (3.5) This page should be highlighted as an exemplary page for others to emulate.

Suggestions:

• 1.It is better to add math tag to variables that in the paragraph.
• 2.Abstract can be more concise. Maybe put some contents in other sections.
• 3. It is better to give some pseudo code for the the algorithm.

Sincerely,

YuYan

Thank you for your comments YuYan. I shall try to incorporate your suggestions in improving my page. Thanks and regards, Ritika

Hey Ritika,

Nice colours and pictures!

Some things that can be made clearer I think:

- A link to Bayesian networks can be very helpful. (Links to other wiki pages seem to be non-existent.)

- Is there a reason why we're working with 'factors' instead of just conditional and marginal probability. Is it because this eliminates the need to normalize until the very end? Is there a formula (proportionality of conditional and joint probabilities) that can help illustrate this?

- Is it possible for a Bayes net to not have any valid variable elimination ordering?

- First sentence in Complexity section: Why does a factor containing $n$ variables must have $2^{n}$ storage complexity? Previously, you never made the assumption that variables can only take one of two values...

Awesome demo!

Thanks for the great read,

Ricky

Hi Ricky, Thank you so much for your feedback! 1. Yes indeed I could add a link to the page for Bayesian network to make things clearer. 2. Well the traditional approach is to take the entire JPD and condition and marginalize on it. However the space and time complexity for this is O(dⁿ) where 'd' is the size of the largest domain and 'n' is number of variables.n We do feel the need to normalize at the very end even though the factors don't need to sum to 1. But after multiplying factors we need to normalize (as shown in the demo). In essence, 'summing out a variable' kind of relates to marginalizing and 'assigning a variable' relates to conditioning intuitively. I'm not sure what you mean by the formula part of the question? 3. As long as the conditional independencies are not violated (i.e.all the necessary dependencies are represented through the links between nodes in the Bayesian network), any elimination order should be valid. The maximum factor size could however be a concern. 4. Sorry, I meant to say 'n' binary variables. I mentioned binary because usually variables have few parents in Bayesian network. Thank you for you comments. Regards, Ritika

Hi Ritika, Nice to see your wiki about variable elimination, which helped me a lot in understanding this technical field which I was unfamiliar with. I have some questions regarding your topic. First, you mentioned in the abstract that the traditional method is extremely inefficient and doesn't scale well, can you give some detail about the reason? Second, do you have pseudo code for the variable elimination algorithm? Third, can you provide any real examples that uses variable elimination? Regards Arthur

Hi Arthur, Thank you for your comments. I shall try to answer them to the best of my abilities. 1. So the traditional method is inference by enumeration. So basically we are given the entire JPD (joint probability distribution) on set of variables and we need to say, for instance compute conditional probability given some evidence. How you would traditionally go about doing this is that you will first condition on the distribution to incorporate evidence e, which basically means that you will eliminate those records from your table which don't agree with your evidence and then normalize. After that you will marginalize on this new distribution to accommodate 'observation' part of the conditional probability. If we have 'n' variables and 'd' is the size of the largest domain, space complexity to store JPD is O(d^n). Time complexity is also O(d^n) because in the worst case we need to sum over all entries in the JPD. 2. I have given the algorithm in Section 5, which in essence is similar to pseudocode I guess? 3. Sorry I was updating my 'Applications' section when you wrote this. I hope that answers your question now. Thanks and regards, Ritika