Show that variable elimination on poly trees can performed

Assignment Help Computer Engineering

Reference no: EM131851473

Problem

a. Show that variable elimination on poly trees can be performed in linear time, assuming that the local probability models are represented as full tables. Specifically, for any poly tree, describe an elimination ordering, and show that the complexity of variable elimination with your ordering is linear in the size of the network. Note that the linear time bound here is in terms of the size of the CPTs in the network, so that the cost of the algorithm grows exponentially with the number of parents of a node.

b. Extend your result from (1) to apply to cases where the CPDs satisfy independence of causal influence. Note that, in this case, the network representation is linear in the number of variables in the network, and the algorithm should be linear in that number.

c. Now extend your result from (1) to apply to cases where the CPDs are tree-structured. In this case, the network representation is the sum of the sizes of the trees in the individual CPDs, and the algorithm should be linear in that number.

Reference no: EM131851473

Questions Cloud

The difference between your opinion and the truth : How do you know the difference between your opinion and the 'truth'?Is your opinion true simply because it is your opinion?

What did you find most interesting about this speaker : What were the main points of this speaker's presentation? What did you find most interesting about this speaker?

Discuss the importance of integrating sales and operations : Summarize the ways through which sales and operations planning can be integrated.

Define the structure of the graph : For each counterexample, define the structure of the graph and the cardinality of the variables, and show the ordering produced by each member of the pair.

Show that variable elimination on poly trees can performed : Show that variable elimination on poly trees can be performed in linear time, assuming that the local probability models are represented as full tables.

Provide characterization of when two distributions will have : In this exercise, we will provide a characterization of when two distributions P1 and P2 will have the same M-projection.

What is liability of newness : What is liability of newness? What are the differences between a heterogeneous and a homogeneous founding team?

Which federal antitrust statute would apply : Evaluate whether the executives can be charged with criminal violations of federal antitrust laws. Which federal antitrust statute would apply?

Prepare a statement calculating each partner share : Prepare a statement calculating each partner's share of Partnership Net Income (PNI). Calculate the net tax payable by Ron for the 2014/15 tax year

User Account

All Pages