# Fundamentally, what is a perfect language model?

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 1st words.
• $$\mathcal{W}_2$$ is a bag that contains words that can only appear as 2nd 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?

• Typical theory about languages uses the concept of a grammar, which results in a parse tree, representing the structure. Working left-to-right does not work for many languages. A grammar contains rules such as "a noun-phrase can consist of an article followed by a noun, or an adjective phrase followed by a noun, or ..." and so on. For example, here's a starting point: en.wikipedia.org/wiki/Probabilistic_context-free_grammar Sep 13, 2020 at 1:56
• @RobbyGoetschalckx. Thanks that is very helpful. I looked up parse trees (thanks to you), and I think your rules example is for a constituency-based parse tree? I also found dependency-based trees, though not very clear to me. I guess the constituency one stores syntax (words order), while the dependency one is more about the semantics and less of the syntax (tree doesn't encode words order)? Sep 13, 2020 at 2:21
• What kind of language do you have in mind: programming languages (like LISP, Ocaml, ...) or human languages (like French, English)? For human languages, do you assume some correct plain text representation (e.g. an UTF-8 encoded stream of bytes), or is it formatted (e.g. HTML5) with spelling mistakes, or is it sound? See also decoder-project.eu (I am on the photo) Sep 13, 2020 at 10:11
• @BasileStarynkevitch Does it matter which language? So far I'd say English UTF-8 typo-free, but I don't see why should it matter in defining language models correctly. Any example how language selection will affect the definition of the fundamental language model? Sep 13, 2020 at 15:35
• I am not so sure that Scheme R5RS, modern Chinese ideograms, written Latin (by Cicero...), and Egyptian hieroglyphs share some "common model" - more than what Noam Chomsky wrote about. Be sure to start a PhD thesis if you believe there is one. Consider using RefPerSys. Feel free to email me basile@starynkevitch.net for more, but do mention the URL of your question in your email ... Sep 13, 2020 at 15:43

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).
• Thanks a lot! Easy to understand despite me being a beginner. I have 2 questions if your time allows: (1) Isn't that actually similar to 1.1. sequential, except for adding BOS and EOS? I guess I was wrong for assuming that 1.2. Joint offers any advantage, since 1.1. is just the result of applying the chain rule. Am I right? (2) Is there any proof of some kind that this is the truth? I can intuitively see it being true, but any is there any proof that it cannot be any simpler? Sep 13, 2020 at 23:52