3
$\begingroup$

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?

$\endgroup$
10
  • 2
    $\begingroup$ 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 $\endgroup$ – Robby Goetschalckx Sep 13 '20 at 1:56
  • $\begingroup$ @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)? $\endgroup$ – caveman Sep 13 '20 at 2:21
  • $\begingroup$ 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) $\endgroup$ – Basile Starynkevitch Sep 13 '20 at 10:11
  • $\begingroup$ @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? $\endgroup$ – caveman Sep 13 '20 at 15:35
  • $\begingroup$ 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 ... $\endgroup$ – Basile Starynkevitch Sep 13 '20 at 15:43
1
$\begingroup$

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).

$\endgroup$
9
  • 1
    $\begingroup$ 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? $\endgroup$ – caveman Sep 13 '20 at 23:52
  • $\begingroup$ E.g. if we say that language is a machine that encodes information by generating some output (e.g. we usualy call it text), then can we say that language, in this generality, has to be a Turing complete machine? And if it is Turing complete, is there any way to extend this into a proof that says something like "the simplest correct probability model is joint"? I feel it can be done, but I don't see how connect these claims. I feel that I am jumping, which makes me feel that I might be wrong (as usual when I jump). $\endgroup$ – caveman Sep 13 '20 at 23:56
  • $\begingroup$ In the 1.1 you used argmax to generate samples from a language model, while you can also sample from that distribution or do whatever you want. Basiacally a language model is that distribution. You were right, when you decomposed the probabilities using chain rule from left to right, but you also could fave done it from right to left or in your specific order, or just leave certain word phrases without decomposition. These are just different wasy to represent the same thing $\endgroup$ – Michael Solotky Sep 14 '20 at 8:25
  • $\begingroup$ Oh, I don't think it has anything in common with Turing completeness. It's just a probability distribution over sequences (just like multinomial with dependencies between elements), it can't see how it can emulate any Turing machine. $\endgroup$ – Michael Solotky Sep 14 '20 at 8:31
  • 1
    $\begingroup$ Aha, got it. I think it can. It's like a patricular probability distribution is a program for a Turing machine and when you send there a patricular sequence (it's like initial state of memory tape) it can continue it by predicting the next elements of a sequence. All conditional probabilities it uses to continue a sequence can be made degenerate and they would implement specific command from the table of instructions. Also you've got a EOS symbol which can stop the LM generating new elements (or you cannot generate it at all in some cases) $\endgroup$ – Michael Solotky Sep 14 '20 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.