[PGM] Section 6. Inference-Overview
前面都是讲PGM的representation，从这里开始，后面讲的是Inference，即当我们有了一个完整的PGM之后，如何使用它来回答一些问题。这一小节就是在说有哪几种类型的“问题”。
Conditional Probability Queries
说白了，就是在给定一个PGM的情况下，要算\(P(Y|E=e)\)的概率分布是啥；其中E=e称为Evidence，也就是已知的某些变量的取值，而Y为Query，也就是我们的目标变量。
不幸的是，给定一个PGM \(P_{\Phi}\)，一个变量X及其某个取值x，想要计算其概率\(P(X=x)\)或者判断是否满足\(P(X=x) > 0\)都是NP-hard；更不幸的是，即使我们降低要求，只想要一个近似解，那么这个问题也是NP-hard。万幸的是，这些都只是worst case，对于general case还是有希望能得到efficient solution的。
计算Conditional Probability Query的通用方式称为Sum-Product，在介绍之前需要先声明一下：后面所有的操作都是针对factor来做的，对于MN这样毫无问题，因为factor原来就是MN的component；而对于BN，其原始component是条件分布\(\hat P(X|Par_X)\)(注意这里是unormalized measure)，所以需要做一个定义，即\(\phi(X, Par_X) = \hat P(X|Par_X)\)，这样BN也可以使用factor来表示了。
Sum-Product实际上工作就是把所有的factor做product，然后marginalize所有无关变量，比如说像下面这个BN中计算\(P(J)\)例子：
这里忽略了一点，就是这里没有Evidence。如果要计算的是\(P(J, D=d)\)怎么办？很简单，实际就是直接把D=d代入到上面那个等式中，变成了
\[P(J, D=d) = \sum_{C,I,G,S,L,H} \phi_C(C) \phi_D(C, d) \phi_I(I) \phi_G(G, I, d)...\]
这里需要注意一点，通常factor product出来的是\(\hat P\)而不是\(P\)，需要再normalize，这个例子是BN，它的factor对应条件概率分布，也就没有这个问题了。
\(P(J, D=d)\)是算出来了，但是它不是Conditional Probability Query啊，我们的任务是计算形为\(P(J|D=d)\)的分布吧？下面给出通用步骤。
定义Y为目标变量，E=e为Evidence，令\(W = \{X_1,...,X_n\} - Y - E\)，即余下的所有变量，有如下等式
\[P(Y|E=e) = \frac{P(Y, E=e)}{P(E=e)}\]
这个就是贝叶斯公式
\[P(Y, E=e) = \sum_W P(Y, W, E=e) = \sum_W \frac{1}{Z} \Pi_k \phi_k(D_k, E = e) = \sum_W \frac{1}{Z} \Pi_k \phi^{'}_k(D^{'}_k)\]
这个其实就是上面那个Sum-Product+Renormalize
\[P(E = e) = \sum_Y P(Y, E=e)\]
把后面那个两个计算式代入贝叶斯公式，发现归一化常量Z是可以被约掉的，所以我们要做的其实就是计算\(\sum_W\Pi_k \phi^{'}_k(D^{'}_k)\)，也就是Sum-Product，然后再做一次renormalize就完事了。注意这里的renormalize使用的归一化常量跟上面第二行公式后注的那个不一样。
计算条件概率的算法有很多，课件中列了一些，在后面课程中都会讲到，包括Variable Elimination，Message Passing以及Random Sampling instantiations。
MAP Inference
这个是第二类问题，给定Evidence E=e，希望能得所有其它变量Y的一个conherent assignment y，使得\(P(Y=y|E=e)\)最大。应用场景包括Message decoding（最可能的原信息），Image segmentation（superpixels上最可能的label assignment）。
MAP is not equal to Max over Marginals! 其实这是句费话，学过点概率统计的应该都知道。
不幸的消息又来了，找使用\(P(X)\)最大的x也是NP-hard问题，甚至于判断\(P(x) > p\)是否成立也是NP-hard的。好在它仍然只在worst case下成立，在average case下还是有希望的。
与Sum-Product相对应的，解决MAP问题使用的方式是Max-Product，而且计算更简单。根据前面写的贝叶斯公式，我们知道选择最优的y只需要考虑分子，因为分母是与Y无关的，而进一步地
\[P(Y, E=e) = \frac{1}{Z} \Pi_k \phi^{'}_k(D^{'}_k) \propto \Pi_k \phi^{'}_k(D^{'}_k)\]
最后一步同样是因为，归一化常量并不影响y之间的相对大小，因此可以忽略。于是我们要得到的就是让最后一个表达式最大的y。
解决MAP的算法也列出一些：Variable Elimination, Message Passing, integer programming, graph-cut method(for some networks), combinatorial search。
2020年2月22日 17:29
Because the name suggests, deep washing represents another amount of cleaning upwards your house or office. Basic washing includes general tidy up like wiping and also vacuuming the kitchen, bathroom, bedroom and family area floors, along with cleaning the particular cupboard gates, tables, chair, and etc, using h2o or any basic washing products; nonetheless, deep cleaning is approximately making time for the information and removing hidden airborne dirt and dust, dirt, and also small staining. It can be a top to be able to bottom scrubbing of your property, from ceilings to be able to floors, Samples of deep washing include washing what’s involving the tiles, behind the automatic washer, under the particular sink, in the oven, cleaning the space corners…etc.
2020年2月23日 13:14
A final thing you must check in before using the services of a carpet cleaners company can be they sort of carpet cleanup equipment along with methods that they can use if they are experts in any a real type involving service. You also have to ask whenever they have an understanding of your specific sort of rugs along with carpets if they will use the right technique of cleaning for what we have. A final thing you desire is for ones Oriental rugs or Local carpets to get ruined want . company used an unacceptable carpet cleanup process as well as chemicals.
2022年8月07日 12:25
HDFC Life is one of the top insurance providers in India which helps many subscribers with their benefited plans, and customers get easy avenues that make their online payment and other options very easy, where HDFC was established in 2000 and it has been growing in service that it provides to customers. HDFC Life Online Premium Payment The insurance policy through HDFC Life does carry in every different stream which ensures customers get their desired policy for their purpose, and customers can get more information about the HDFC Life Insurance from the official website of HDFC and here we will let you know how to get the installments for the policy to be paid.
2023年7月10日 23:43
The activation code will appear on the TV screen when the streaming device has been connected. To enter the activation code, go to official website. First, you must log in to your TV provider and then select the Activate Now option to begin the activation procedure. bravotv.com/link activation code roku Users may log in to the Bravo TV channel on their Smart TV or streaming device with this code and the service is now available on Android, Roku, Amazon Fire TV, Apple TV, iOS devices, computers, tablets, and Smart TVs.
2023年8月21日 18:30
CBSE Curriculum is based on the National Curriculum Framework and Provides Opportunities for Students to Achieve Excellence in Learning, CBSE Provides the Syllabus for 2nd Class, This new Syllabus CBSE 2nd Class Syllabus 2024 are Designed Strategically by a Team of Subject Experts and are Prescribed by the Ministry of Human Resource Development, formerly Ministry of Education, is Responsible for the Development of Human Resources in India, Primary Level Syllabus for the Children of has been developed with the Supervision of the Central Board of Secondary Education.