In NLP/probability/ML notation: what does a tilde over a letter mean?

Question

I am reading this paper. In section 1.1 he says:

What do the tildes above the letters mean? How can I translate this sentence into ordinary English?

Answer 1

There are basically two objects which you have to understand

• P(.) (notation without tilde) refer to the actual, true, unknown distribution of data/labels/features/other things. We assume that such objects exists and we are trying to somehow estimate it
• ~P(.) (notation with tilde) usually refers to some kind estimation of P(.) (or at least an object which is proportional to P(.)). In most cases it is some simple empirical estimator, like fraction of things passing the predicate to all "things". However, it can get arbitrary complex (like Kneser-Nay estimation of language model with markov property)

So the translation would be:

• P(.) -> probablity of ...
• ~P(.) -> estimation of the probablity of ...

Answer 2

In the quote, P-tilde denotes the empirical distribution. However, the usual symbol for empirical distribution is P-hat -- by extension of the use of ^ to mark estimates. P-tilde is often used to denote an unnormalized distribution: a measure that is intended to be a probability but does not sum/integrate to 1, so it needs to be normalized to be a proper probability distribution.