Perplexity of a Non-Statistical Language Model

Question

I have a piece of software that, given a input phrase, returns an ordered list of the next most likely words (entire vocab is ordered 1 to n). This is essentially an Language Model with the exception that the candidate output words are simply an ordered list and there are no probabilities associated with them.

This (https://web.stanford.edu/class/cs124/lec/languagemodeling.pdf) does a nice job of explaining perplexity and from the description of "intuitive perplexity" I thought I may be able to estimate perplexity by simply averaging the correct location of the output words. ie.. If the correct words, for 3 different phrases, shows up on the list at positions 40,50,60, then the perplexity would be 50. Trying this with a standard statistical LM gave quite a bit higher (worse) results than the normal perplexity calculation so I suspect this isn't correct.

A second way I thought might work was to try to assign a distribution to the words based on their rank on the list but I'm unsure of the exact math here. Experimentally assigning a probability to each predicted word of 1/rank, normalized by the sum all ranks to 1.0, gives numbers that are ballpark of what I'd expect but I wonder if this is mathematically valid.

Is there a correct way to get an estimate of perplexity (even a pseudo estimate just for rough comparison purposes) of ranked list of words like this?

Answer 1

After a bit of research it appears there is no "right" way to do this.

You can get close by assigning probabilities to the word's rank on a list but the two methods I tried were not accurate enough for a good comparison.

1. Use 1/rank normalized to 1.0. Est perplexity = 132. Actual = 100
2. Use the unigram prob curve. Est perplexity = 156. Actual = 100

There is a paper Estimation of gap between current language models and human performance where they ran into a similar need. The authors used 2 different measurement criteria, mean-log-rank (Rank) and percent-words-correct (Top1). In the paper, they ran these metrics against a number of different language models and calculated perplexity too. Table #2 of the paper is a few dozen models with perplexity measured along with the two new metrics. There is a reasonably good correlation between all three metrics so, using the table, you can estimate perplexity (PPL), given "Rank" or "Top1".