meijun/maxspn

MAX SPN

maxspn's Issues

Paired p-test

Our experiment results should use the paired p-test.

Figure out what the SumMax sampling is

Generate random SPNs

Both ID-SPN and LearnSPN are actually learned by LeranSPN methods, so the data maybe have a huge bias such that the performance of many methods are not so good. So we need more data. If we cannot find other data easily, generating random data is not a so bad way.

Apx complexity from BN

We should transfer the inapproximability result from BN.

Gradient descent as continual variables

We can treat the discrete variables as continual variables and use the gradient descent method to get a local minimal. Finally, we round it to make discrete.

Combine the local search and exact search

Local search cannot promise exact solutions but can use efficient derivative methods. Exact search can use heuristic to pruning and find exact solution but cannot use the pros of efficient derivatives. What happens if we can find a method to combine the pros of them.

Design the final experiment

Relax the problem to find a heuristic

If we want to get the exact solution, we need some heuristics to pruning efficiently.

Exact-method experiments

We need an experiment to prove our heuristic and derivative help.

Get more SPN

We think that we cannot sample random SPNs from the SPN space, so we try to get SPN from other papers or github repos.

Top-K MaxMax

Top-K MaxMax is equivalent to Top-K TreeMAP. All the internal nodes are considered as hidden variables. The next step is to implement it to check the performance.

Summarize contributions

Derivative theorem checking

Check the first SPN paper to make sure our derivative theorem is new.

Construct a new SPN for each layer in exact search

Refine

• KBT + BS
• BT + Exact