Limiting predicted tags using a dictionary

[amironoff]

Hi @zhongkaifu,

Sometimes we know the possible tags to choose from for a single token. E.g. consider POS tagging: if we have a dictionary that maps terms to all possible tags, we could use this information to:

1. Limit CRF# output
2. Prune non-perspective paths and save some CPU time (we know that 'pizza' can't be a verb, so don't even check that path)

I'm looking at adding this feature into CRF#. My first approach just skips calcCost(node) in buildLattice, if node maps to a tag that isn't on the dictionary.

Wondering what your suggestions are to implement this the most pain-free way? :)

[zhongkaifu]

Hi @amironoff
Yes, this is a good idea to speed up and reduce memory usage for CRFSharp.

For easier way, yes, you can modify buildLattice() method to assign fixed cost (0.0 or 1/n, n is the number of possible tags for the token) to each nodes according mapping between token and tagging.

By this way, we can speed up CRFSharp, but cannot reduce memory usage since we still build entire feature set.

So, the better solution is to deal with feature set building. According mapping between token and tagging, those useless features can be filtered out. However, by this way, the data structure of feature set need to be changed, and those code related to feature set need to be updated as well. I don't think this would be a small change.

[amironoff]

zhongkaifu let's start with the easy way :) I modified buildLattice to

• Set node.cost to 1/dictionary_tag_count if its tag (node.y) is in the list of dictionary tags;
• set node.cost to 0 if its tag isn't in the list of dictionary tags
• if the list of dictionary tags for the current token is empty, use calcCost(node)

This doesn't work though - the tagger output becomes incorrect.

• Am I right in assuming that larger node.cost = more likely to choose this node over others?
• Shouldn't node paths also be updated?

Here's a snippet of the code I ended up with

            for (int i = 0; i < word_num; ++i)
            {
                string currentToken = x_[i][0];
                IEnumerable<string> tokenTags = getTokenTags(currentToken);
                bool shouldPrune = tokenTags != null && tokenTags.Any();
                for (int j = 0; j < ysize_; ++j)
                {
                    var currentNode = node_[i, j];

                    // skip non-perspective paths
                    string pathTag = yname(j);
                    if (!shouldPrune)
                        calcCost(currentNode);
                    else
                    {
                        if (tokenTags.Contains(pathTag))
                            currentNode.cost = 1/(double)tokenTags.Count();
                        else
                        {
                            currentNode.cost = 0;
                        }
                    }

                    for (int index = 0; index < currentNode.lpathList.Count; ++index)
                    {
                        Path p = currentNode.lpathList[index];
                        calcCost(p);
                    }
                }
            }

[zhongkaifu]

Yes, node path must be updated, otherwise, the result won't be correct, since CRF algorithm considers entire tokens path to calculate result. The path cost between previous token and current token needs to be updated as well.