Feeds:
Posts

## Conditional Random Fields: A Beginner’s Survey

One interesting project that I am involved in these days involves certain problems in Intelligent Tutors. It turns out that perhaps one of the best ways to tackle them is by using Conditional Random Fields (CRFs). Many attempts to solving these problems still involve Hidden Markov Models (HMMs). Since I have never really been a Graphical Models guy (though I am always fascinated) so I found the going on studying CRFs quite difficult. Now that the survey is more or less over, here are my suggestions for beginners to go about learning them.

Tutorials and Theory

1. Log-Linear Models and Conditional Random Fields (Tutorial by Charles Elkan)

Log-linear Models and Conditional Random Fields
Charles Elkan

6 videos: Click on Image above to view

Two directions of approaching CRFs are especially useful to get a good perspective on their use. One of these is considering CRFs as an alternate to Hidden Markov Models (HMMs) while another is to think of CRFs building over Logistic Regression.

This tutorial makes an approach from the second direction and is easily one of the most basic around. Most people interested in CRFs would ofcourse be familiar with ideas of maximum likelihood, logistic regression etc. This tutorial does a good job, starting with the absolute basics – talking about logistic regression (for a two class problem) to a more general multi-label machine learning problem with a structured output (outputs having a structure). I tried reading a few tutorials before this one, but found this to be the most comprehensive and the best place to start. It however seems that there is one lecture missing in this series which (going by the notes) covered more training algorithms.

2. Survey Papers on Relational Learning

These are not really tutorials on CRFs, but talk of sequential learning in general. For beginners, these surveys are useful to clarify the range of problems in which CRFs might be useful while also discussing other methods for the same briefly. I would recommend these two tutorials to help put CRFs in perspective in the broader machine learning sub-area of Relational Learning.

— Machine Learning for Sequential Learning: A Survey (Thomas Dietterich)

PDF

This is a very broad survey that talks of sequential learning, defines the problem and some of the most used methods.

— An Introduction to Structured Discriminative Learning (R Memisevic)

PS

This tutorial is like the above, however focuses more on comparing CRFs with large margin methods such as SVM. Giving yet another interesting perspective in placing CRFs.

3. Comprehensive CRF Tutorial (Andrew McCallum and Charles Sutton)

PDF

This tutorial is the most compendious tutorial available for CRF. While it claims to start from the bare bone basics, I found it hard for a start and took it on third (after the above two). It is potentially the starting and ending point for a more advanced Graphical Models student. It is extensive (90 pages) and gives a feeling of comfort with CRFs when done. It is definitely the best tutorial available though by no means the most easiest point to start if you have never done any sequential learning before.

This might be considered an extension to this tutorial by McCallum et al : CRFs for Relational Learning (PDF)

4. Original CRF Paper (John Lafferty et al.)

PDF

Though not necessary to learn CRFs given many better tutorials, this paper is still recommended, being the first on CRFs.

5. Training/Derivations (Rahul Gupta)

PDF

This report is good for the various training methods and for one to go through the derivations associated.

6. Applications to Vision (Nowozin/Lampert)

If your primary focus is using structured prediction in Computer Vision/Image Analysis then a good tutorial (with a large section on CRFs) can be found over here:

Structured prediction and learning in Computer Vision (Foundations and Trends Volume).

PDF

___________________

Extensions to the CRF concept

There are a number of extensions to CRFs. The two that I have found most helpful in my work are (these are easy to follow given the above):

Both of these extensions work to include hidden variables in the CRF framework.

___________________

Software Packages

1. Kevin Murphy’s CRF toolbox (MATLAB)

2. MALLET (I haven’t used MALLET, it is Java based)

3. HCRF – LDCRF Library (MATLAB, C++, Python). As as the name suggests, this package is for HCRF and LDCRF, though can be used as a standalone package for CRF as well.

### 16 Responses

1. Nice post

2. do you know what temporal CRFs are?

• Actually I had not heard of temporal CRFs. So, thanks for telling me about them. But looking at the T-CRF paper seems that it is a simple addition to the basic CRF idea wherein they use optical flow etc. so that it could be used for tracking (as the name seems to indicate anyway).

3. Thanks. I’m just getting started in CRFs. I realized that I had to go through a lot of related to topics too like Logistic Regression and others. I was just wondering if it was easy to implement them (apart from BFGS, Batch Gradient Descent, etc for training which I will use existing packages/apis)? Any tips, common trivial problems that you faced while implementing them or using them?

4. I’m sorry. I was talking about CRFs (in the above comment).

• I’m sorry I just saw this. I had notifications turned off and I didn’t check my blog till today. Is it too late for my input now?

5. Please comment on my question. Its never too late!

• Thanks, I just wrote to you.

6. Reblogged this on Wikia.

7. Reblogged this on simplicity and commented:

8. Thanks a ton!

9. I would like to do a project related to entity recognition from text.
I would like to apply CRF based toolkits for the same.

How good is CRF++ Toolkit?
Is there any good tutorial available for MIRA learning methods (basics)?

10. Awesome! Thanks a lot for posting this. Super helpful resources. Exactly ehat I was looking for. You saved me a lot of time.

11. on March 29, 2015 at 5:09 pm | Reply Megha Sharma

Hello Sir,
Please help me I am a B.Tech second year student and want to learn about working on conditional random field using matlab or r tool or any other way but i have no idea how to start please provide guidance.

12. thank you very much!!!

13. how i can work with conditional random fields …..just give me a simple implemendation………………