Fundamentally, what is a perfect language model?

Question

Suppose that we want to generate a sentence made of words according to language $L$: $$ W_1 W_2 \ldots W_n $$

Question: What is the perfect language model?

I ask about perfect because I want to know the concept fundamentally at its fullest extent. I am not interested in knowing heuristics or shortcuts that reduce the complexity of its implementation.

---

1. My thoughts so far

1.1. Sequential

One possible way to think about it is moving from left to right. So, 1st, we try to find out value of $W_1$. To do so, we choose the specific word $w$ from the space of words $\mathcal{W}$ that's used by the language $L$. Basically: $$ w_1 = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_1 = w) $$

Then, we move forward to find the value of the next word $W_2$ as follows $$ w_2 = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_2 = w | W_1 = w_1) $$

Likewise for $W_3, \ldots, W_n$: $$ w_3 = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_3 = w | W_1 = w_1, W_2=w_2) $$ $$ \vdots $$ $$ w_n = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_n = w | W_1 = w_1, W_2=w_2, \ldots W_{n-1}=w_{n-1}) $$

But is this really perfect? I personally doubt. I think while language is read and written usually from a given direction (e.g. left to right), it is not always done so, and in many cases language is read/written possibly in a funny order as we always do. E.g. even when I wrote this question, I jumped back and forth, then went to edit it (as I'm doing now). So I clearly didn't write it from left to right! Similarly, you, the reader; you won't really read it in a single pass from left to right, will you? You will probably read it in some funny order and go back and forth for awhile until you conclude an understanding. So I personally really doubt that the sequential formalism is perfect.

1.2. Joint

Here we find all the $n$ words jointly. Of course ridiculously expensive computationally (if implemented), but our goal here is to only know what is the problem at its fullest.

Basically, we get the $n$ words as follows:

$$ (w_1, w_2, \ldots, w_n) = \underset{(w_1,w_2,\ldots,w_n) \in \mathcal{W}^n}{\text{arg max }} \Pr(W_1 = w_1, W_2=w_2, \ldots W_n=w_n) $$

This is a perfect representation of language model in my opinion, because its answer is gauranteed to be correct. But there is this annoying aspect which is that its words candidates space is needlessly large!

E.g. this formalism is basically saying that the following is a candidate words sequence: $(., Hello, world, !)$ even though we know that in (say) English a sentence cannot start by a dot ".".

1.3. Joint but slightly smarter

This is very similar to 1.2 Joint, except that it deletes the single bag of all words $\mathcal{W}$, and instead introduces several bags $\mathcal{W}_1, \mathcal{W}_2, \ldots, \mathcal{W}_n$, which work as follows:

• $\mathcal{W}_1$ is a bag that contains words that can only appear as 1^st words.
• $\mathcal{W}_2$ is a bag that contains words that can only appear as 2^nd words.
• $\vdots$
• $\mathcal{W}_n$ is a bag that contains words that can only appear as $n$^th words.

This way, we will avoid the stupid candidates that 1.2. Joint evaluated by following this: $$ (w_1, w_2, \ldots, w_n) = \underset{w_1 \in \mathcal{W}_1,w_2 \in \mathcal{W}_2,\ldots,w_n \in \mathcal{W}_n) \in \mathcal{W}^n}{\text{arg max }} \Pr(W_1 = w_1, W_2=w_2, \ldots W_n=w_n) $$

This will also guarantee being a perfect representation of a language model, yet it its candidates space is smaller than one in 1.2. Joint.

1.4. Joint but fully smart

Here is where I'm stuck!

Question rephrase (in case it helps): Is there any formalism that gives the perfect correctness of 1.2. and 1.3., except for also being fully smart in that its candidates space is smallest?

Answer 1

One of your hypothesis is very close to the truth, it's 1.2

So, a language model measures the probability of a given sentence in a language $L$. The sentences can have any length and the sum of probabilities of all the sentences in the language $L$ is 1. It's very difficult to compute, thus people use some simplifications, like say if the words are located far enough from each other, then the occurrence of a current word doesn't depend on a word which was occurred far away in the past. Each sentence is a sequence $w_1, \dots, w_n$ and a language model computes the probability of the sequence $p([w_1, \dots w_n])$ (it's not joint distrribution yet). It can be decomposed into a joint distribution with some special tokens added $p(BOS, w_1, \dots w_n, EOS])$. BOS is begin of the sentence and EOS is end of sentence. Then this joint distribution can be decomposed using the chain rule $p(BOS, w_1, \dots w_n, EOS]) = p(BOS) p(w_1 | BOS) \Big[ \prod\limits_{i=1}^n p(w_i | BOS, w_1, \dots, w_{i-1}) \Big] p(EOS | BOS, w_1, \dots, w_n)$. There are 2 types of probabilities that are usually modelled differently: a prior probability $p(BOS)$ which is always equal to 1, because you always have BOS as the first token in the augmented sequence. Then conditional probabilities can be computed as follows $p(w_i | BOS, w_1, \dots, w_{i-1}) = \frac{c(BOS, w_1, \dots, w_{i-1}, w_i)}{\sum_{w_i \in W} c(BOS, w_1, \dots, w_{i-1}, w_i)}$. Where $c$ is a counter function that measures how many times a given sequence occured in the dataset you specified to train your model. You can notice it's a maximum likelihood estimate of the unknown conditional probabilities. Obviously if you're using a certain dataset you compute a model of that dataset, not of a language, but that's the to approximate true probabilities of sentences in a language. The EOS token is needed to make difference between a probability of a non-finished yet sequence and that which has finished, because if you take those counters from above and forget about adding the EOS into your dataset in the end of all sentences, you'll get probabilities that don't sum into 1 (which is bad).