PGM-class and MRF parameter learning

I’m taking Stanford CS 228 (a.k.a. pgm-class) on Coursera. The class is great, I guess it provides close to the maximum one can do under the constraints of remoteness and bulkness. The thing I miss is theoretical problems, which were taken aside from the on-line version because they could not be graded automatically.

There is an important thing about graphical models I fully realized only recently (partly due to the class). This thing should be articulated clearly in every introductory course, but is often just mentioned, probably because lecturers consider it obvious. The thing is there is no probabilistic meaning of MRF potentials whatsoever. The partition function is there not only for amenity: in contrast to Bayesian networks, there is no general way to assign potentials of an undirected graphical model to avoid normalization. The loops make it impossible. The implication is one should not assign potentials by estimating frequencies of assignments to factors (possibly conditioned on features) like I did earlier. This is quite a bad heuristic because it is susceptible to overcounting. Let me give an example.

For the third week programming assignment we needed to implement a Markov network for handwriting OCR. The unary and pairwise potentials are somewhat obvious, but there was also a task to add ternary factors. The accuracy of the pairwise model is 26%. Mihaly Barasz tried to add ternary factors with values proportional to trigram frequencies in English, which decreased performance to 21% (link for those who have access). After removing pairwise factors, the performance rose to 38%. Why has the joint model failed? The reason is overcounting evidence: different factor types enforce the same co-occurrences, thus creating bias towards more frequent assignments, and this shows it can be significant. Therefore, we should train models with cycles discriminatively. 

One more thought I’d like to share: graphical model design is similar to software engineering in the way that the crucial thing for the both is eliminating insignificant dependencies on the architecture design stage. 

Read Users' Comments (8)

8 Response to "PGM-class and MRF parameter learning"

  1. Yaroslav Bulatov says:
    20 April 2012 at 10:41

    Here's an interesting side point -- if you could assign potentials to avoid global normalization then computing the partition function could be done efficiently with dynamic programming. And vica versa, if you can compute the partition function efficiently, then you could rewrite your model as a product of factors which can be estimated using simple counting.

  2. Linda says:
    19 April 2017 at 17:40

    Good sharing. It is a very informative blog. Anyone who wants detailed summary of computer classes that theoretical concept can benefit from this blog to have a detailed overview and information.

  3. NitroIndia.org says:
    30 July 2017 at 18:07

    Online Computer Training Classes - Get the free computer courses, classes, training and certification online at your home free of cost. Nitro India one of the famous organization provide these services to you free of cost. Get now free classes, courses and certification from Nitro all over the world.

  4. Prwatech says:
    4 October 2019 at 09:45

    I learned World's Trending Technology from certified experts for free of cost. I got a job in decent Top MNC Company with handsome 14 LPA salary, I have learned the World's Trending Technology from python training in btm layout experts who know advanced concepts which can help to solve any type of Real-time issues in the field of Python. Really worth trying Instant Approval Blog Commenting Sites List

  5. easylearn says:
    10 December 2019 at 08:17

    I was searching for exactly the same information.Thanks for sharing.Good work.Keep it up.These days Big data is trending technology.“Without big data, companies are blind and deaf, wandering out onto the web like deer on a freeway.”If you are looking for any online courses on big data visit our site.
    Big Data Hadoop Online Training Courses

  6. Customer Support | Live Chat Service says:
    24 February 2020 at 12:19

    Firefox is no doubt one of the few such web browsers helping users to access high-speed browsing. However, to run the browser smooth and efficient, users need to Clear Browser Cache Firefox time-to-time. If you are unable to clear your browser’s cache, you must keep in touch with our service executive straight away.

  7. John Matt says:
    16 April 2020 at 00:21

    Norton antivirus is one of the most popular and well-reputed antivirus software in the market. It protects devices from virus, malware and other online threats. However, sometimes users face issues while performing the Norton Login process. If you are one of them who are getting the same issue then no need to worry as we are here to provide the best solution to the problem.



    Norton Internet Security Login
    Norton Antivirus Login
    Log into Norton Account
    My Norton Account Login
    Norton Antivirus Account Login
    Norton Antivirus Sign In
    Norton Security Login
    Norton Sign In
    Norton Account Login
    My Norton Account Sign In
    Norton Login My Account

  8. Gerry Max says:
    18 April 2022 at 12:10

    In some cases, you will have to modify the credentials of your account. If you think what you need to do is change Yahoo password on your iPad, the process is quite straightforward. Follow these simple instructions to change a password on Yahoo mail: first, log into your account and then go to the security page. Next, click on the 'Change password' option. Now, enter your new Yahoo password and confirm it if prompted. Further, click on the 'Continue' to save the settings. This is how you can easily follow the process to change your Yahoo email password on your iPad.

Post a Comment