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 (12)

12 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. Milo Anderson 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. Unknown says:
    26 May 2018 at 11:48

    nice blog
    android training in bangalore
    ios training in bangalore
    machine learning online training

  5. Unknown says:
    26 May 2018 at 12:32

    useful blog
    python interview questions
    cognos interview questions
    perl interview questions
    vlsi interview questions
    web api interview questions
    msbi interview questions

  6. Unknown says:
    26 May 2018 at 12:33

    laravel interview questions aem interview questions
    salesforce interview questions
    oops abab interview questions itil interview questions
    informatica interview questions
    extjs interview questions

  7. Unknown says:
    26 May 2018 at 12:33

    sap bi interview questions
    hive interview questions
    seo interview questions
    as400 interview questions
    wordpress interview questions accounting interview questions
    basic accounting and financial interview questions

  8. 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

  9. 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

  10. mozilla firefox tech support says:
    31 December 2019 at 12:11

    In case you are also getting bothered by these errors and require technical assistance, then do have a word with mozilla firefox customer support

  11. 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.

  12. 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

Post a comment