Answers.Body: <p>One of your hypothesis is very close to the truth, it's 1.2</p>
  <p>So, a language model measures the probability of a given sentence in a language <span class="math-container">$L$</span>. The sentences can have any length and the sum of probabilities of all the sentences in the language <span class="math-container">$L$</span> 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 <span class="math-container">$w_1, \dots, w_n$</span> and a language model computes the probability of the sequence <span class="math-container">$p([w_1, \dots w_n])$</span> (it's not joint distrribution yet). It can be decomposed into a joint distribution with some special tokens added <span class="math-container">$p(BOS, w_1, \dots w_n, EOS])$</span>. BOS is begin of the sentence and EOS is end of sentence. Then this joint distribution can be decomposed using the chain rule <span class="math-container">$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)$</span>. There are 2 types of probabilities that are usually modelled differently: a prior probability <span class="math-container">$p(BOS)$</span> 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 <span class="math-container">$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)}$</span>. Where <span class="math-container">$c$</span> 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).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-13T23:52:14.493Z
Answers.Text: 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?
Answers.UserDisplayName: caveman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-13T23:56:00.343Z
Answers.Text: 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).
Answers.UserDisplayName: caveman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T08:25:41.350Z
Answers.Text: 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
Answers.UserDisplayName: Michał Słodki
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T08:31:54.097Z
Answers.Text: 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.
Answers.UserDisplayName: Michał Słodki
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T08:40:30.787Z
Answers.Text: Since a language model can generate any bit sequence, any reason why it cannot calculate/emulate every thing?  E.g., can't a language model have things like:  if text starts by `2 + 1 = `, then the next character must be `3`.  This way it is speaking the language of mathematics (aka a calculator).
Answers.UserDisplayName: caveman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T10:29:06.027Z
Answers.Text: 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)
Answers.UserDisplayName: Michał Słodki
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T14:42:24.980Z
Answers.Text: Interesting.  So I guess natural languages are codes of a Turing complete machine, except that the machine in this case is a biological one (animal), where data exchange is by shaking air (sound) and storage is by altering neural states (brain).  Is there anything done about Turing complete machines that can prove to us that the tightest probability description we have for this fundamental/general level is that of a joint distribution?
Answers.UserDisplayName: caveman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T14:53:18.530Z
Answers.Text: I haven't heard anything about it.
Answers.UserDisplayName: Michał Słodki
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-14T18:10:37.340Z
Answers.Text: Here is my thought: since language conveys any information, it can output any bit sequence.  And since this is "any bit sequence" it means that we cannot assume easy shortcuts, and since non-joint probabilities are only the result of knowing a shortcut (i.e. removing dependence), therefore the only probability for this case is the joint one (unless someone runs an experiment with human brain to conclude that we cannot generate certain bit sequences).
Answers.UserDisplayName: caveman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-09-13T18:37:13.790Z
Answers.LastActivityDate: 2020-09-13T18:37:13.790Z
Answers.UserDisplayName: Michał Słodki
Body: <p>Suppose that we want to generate a sentence made of words according to language <span class="math-container">$L$</span>:
  <span class="math-container">$$
  W_1 W_2 \ldots W_n
  $$</span></p>
  <p><strong>Question:</strong> What is the perfect language model?</p>
  <p>I ask about <em>perfect</em> 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.</p>
  <hr />
  <h1>1. My thoughts so far</h1>
  <h2>1.1. Sequential</h2>
  <p>One possible way to think about it is moving from left to right.  So, 1st, we try to find out value of <span class="math-container">$W_1$</span>. To do so, we choose the specific word <span class="math-container">$w$</span> from the space of words <span class="math-container">$\mathcal{W}$</span> that's used by the language <span class="math-container">$L$</span>.  Basically:
  <span class="math-container">$$
  w_1 = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_1 = w)
  $$</span></p>
  <p>Then, we move forward to find the value of the next word <span class="math-container">$W_2$</span> as follows
  <span class="math-container">$$
  w_2 = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_2 = w | W_1 = w_1)
  $$</span></p>
  <p>Likewise for <span class="math-container">$W_3, \ldots, W_n$</span>:
  <span class="math-container">$$
  w_3 = \underset{w \in \mathcal{W}}{\text{arg max }} \Pr(W_3 = w | W_1 = w_1, W_2=w_2)
  $$</span>
  <span class="math-container">$$
  \vdots
  $$</span>
  <span class="math-container">$$
  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})
  $$</span></p>
  <p>But is this really <em>perfect</em>?  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, <em>you</em>, 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.</p>
  <h2>1.2. Joint</h2>
  <p>Here we find all the <span class="math-container">$n$</span> words jointly. Of course ridiculously expensive computationally (if implemented), but our goal here is to only know what is the problem at its fullest.</p>
  <p>Basically, we get the <span class="math-container">$n$</span> words as follows:</p>
  <p><span class="math-container">$$
  (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)
  $$</span></p>
  <p>This is a <em>perfect</em> 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 <em>words candidates space</em> is needlessly large!</p>
  <p>E.g. this formalism is basically saying that the following is a candidate words sequence: <span class="math-container">$(., Hello, world, !)$</span> even though we know that in (say) English a sentence cannot start by a dot &quot;.&quot;.</p>
  <h2>1.3. Joint but <em>slightly</em> smarter</h2>
  <p>This is very similar to <strong>1.2 Joint</strong>, except that it deletes the single bag of all words <span class="math-container">$\mathcal{W}$</span>, and instead introduces several bags <span class="math-container">$\mathcal{W}_1, \mathcal{W}_2, \ldots, \mathcal{W}_n$</span>, which work as follows:</p>
  <ul>
  <li><span class="math-container">$\mathcal{W}_1$</span> is a bag that contains words that can <em>only</em> appear as <em>1<sup>st</sup></em> words.</li>
  <li><span class="math-container">$\mathcal{W}_2$</span> is a bag that contains words that can <em>only</em> appear as <em>2<sup>nd</sup></em> words.</li>
  <li><span class="math-container">$\vdots$</span></li>
  <li><span class="math-container">$\mathcal{W}_n$</span> is a bag that contains words that can <em>only</em> appear as <em><span class="math-container">$n$</span><sup>th</sup></em> words.</li>
  </ul>
  <p>This way, we will avoid the <em>stupid</em> candidates that <strong>1.2. Joint</strong> evaluated by following this:
  <span class="math-container">$$
  (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)
  $$</span></p>
  <p>This will also guarantee being a <em>perfect</em> representation of a language model, yet it its <em>candidates</em> space is smaller than one in <strong>1.2. Joint</strong>.</p>
  <h2>1.4. Joint but <em>fully</em> smart</h2>
  <p>Here is where I'm stuck!</p>
  <p><strong>Question rephrase (in case it helps):</strong> Is there any formalism that gives the perfect correctness of <strong>1.2.</strong> and <strong>1.3.</strong>, except for also being <em>fully</em> smart in that its candidates space is smallest?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-13T01:56:56.103Z
Comments.Text: 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: https://en.wikipedia.org/wiki/Probabilistic_context-free_grammar
Comments.UserDisplayName: Robby Goetschalckx
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-13T02:21:37.090Z
Comments.Text: @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)?
Comments.UserDisplayName: caveman
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-13T10:11:40.203Z
Comments.Text: 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 https://www.decoder-project.eu/ (I am on the photo)
Comments.UserDisplayName: Basile Starynkevitch
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-13T15:35:56.880Z
Comments.Text: @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?
Comments.UserDisplayName: caveman
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-13T15:43:27.420Z
Comments.Text: I am not so sure that [Scheme R5RS](https://schemers.org/Documents/Standards/R5RS/), modern Chinese ideograms, written Latin (by [Cicero](https://en.wikipedia.org/wiki/Cicero)...), and Egyptian hieroglyphs share some "common model" - more than what [Noam Chomsky](https://en.wikipedia.org/wiki/Noam_Chomsky) wrote about. Be sure to start a PhD thesis if you believe there is one. Consider using [RefPerSys](http://refpersys.org/). Feel free to email me `basile@starynkevitch.net`  for more, but do mention the URL of your question in your email ...
Comments.UserDisplayName: Basile Starynkevitch
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-13T15:48:45.237Z
Comments.Text: AFAIK, some human languages don't even have verbs.... Read a few books about the scientific controversy of an hypothetical single proto-human-language. And certainly, some (obscure) human language spoken a few dozen years ago had no written form at all. Others don't even have verbs. Try also learning [esperanto](https://en.wikipedia.org/wiki/Esperanto) - its grammar is (on purpose) extremely simple.
Comments.UserDisplayName: Basile Starynkevitch
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-14T10:58:12.893Z
Comments.Text: This is a quite long post. 2 people have voted to close it as "needs more details or clarity". It also seems that you're asking more than one question here. It's highly advisable to ask only one question per post and to focus on simple (and specific) problems/questions. What is your main question? Which question in the title is your main question? Or maybe your main question is "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?"? Please, try to clarify what your main question is.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-14T11:00:34.713Z
Comments.Text: Please, take a look at our on-topic page https://ai.stackexchange.com/help/on-topic, so that you know exactly what is on-topic here and the type of question we look for.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-14T14:24:19.333Z
Comments.Text: @nbro — it's a fundamental/theoretical question about the definition of the perfect language.  I removed 2nd question in title, and rephrased the last question "question" into "question rephrase".  Topic's length is optional read that shows that I think so far (in case it helps the reader to understand my question better).  Because I suspect that a lot of people may miss what I mean by "fundamental" and "perfect" since they are used to simplified heuristics that sort of work in practice (at the expense of correctness).
Comments.UserDisplayName: caveman
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-14T18:56:15.837Z
Comments.Text: Err, perfect language _model_*.
Comments.UserDisplayName: caveman
Tags: <language-model>
Title: Fundamentally, what is a perfect language model?
UserDisplayName: caveman
ThreadText: # Fundamentally, what is a perfect language model?
  
  (Asked by: username_0 on 2020-09-13)
  
  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?
  
  **Tags:** language-model
  > **Comments:**
  > **username_1**: 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: https://en.wikipedia.org/wiki/Probabilistic_context-free_grammar  
  > **username_0**: @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)?  
  > **username_2**: 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 https://www.decoder-project.eu/ (I am on the photo)  
  > **username_0**: @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?  
  > **username_2**: I am not so sure that [Scheme R5RS](https://schemers.org/Documents/Standards/R5RS/), modern Chinese ideograms, written Latin (by [Cicero](https://en.wikipedia.org/wiki/Cicero)...), and Egyptian hieroglyphs share some "common model" - more than what [Noam Chomsky](https://en.wikipedia.org/wiki/Noam_Chomsky) wrote about. Be sure to start a PhD thesis if you believe there is one. Consider using [RefPerSys](http://refpersys.org/). Feel free to email me `basile@starynkevitch.net`  for more, but do mention the URL of your question in your email ...  
  > **username_2**: AFAIK, some human languages don't even have verbs.... Read a few books about the scientific controversy of an hypothetical single proto-human-language. And certainly, some (obscure) human language spoken a few dozen years ago had no written form at all. Others don't even have verbs. Try also learning [esperanto](https://en.wikipedia.org/wiki/Esperanto) - its grammar is (on purpose) extremely simple.  
  > **username_3**: This is a quite long post. 2 people have voted to close it as "needs more details or clarity". It also seems that you're asking more than one question here. It's highly advisable to ask only one question per post and to focus on simple (and specific) problems/questions. What is your main question? Which question in the title is your main question? Or maybe your main question is "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?"? Please, try to clarify what your main question is.  
  > **username_3**: Please, take a look at our on-topic page https://ai.stackexchange.com/help/on-topic, so that you know exactly what is on-topic here and the type of question we look for.  
  > **username_0**: @nbro — it's a fundamental/theoretical question about the definition of the perfect language.  I removed 2nd question in title, and rephrased the last question "question" into "question rephrase".  Topic's length is optional read that shows that I think so far (in case it helps the reader to understand my question better).  Because I suspect that a lot of people may miss what I mean by "fundamental" and "perfect" since they are used to simplified heuristics that sort of work in practice (at the expense of correctness).  
  > **username_0**: Err, perfect language _model_*.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_4 on 2020-09-13. Score: 1 | Accepted answer
  
  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).
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_0**: 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).  
  > **username_4**: 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  
  > **username_4**: 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.  
  > **username_0**: Since a language model can generate any bit sequence, any reason why it cannot calculate/emulate every thing?  E.g., can't a language model have things like:  if text starts by `2 + 1 = `, then the next character must be `3`.  This way it is speaking the language of mathematics (aka a calculator).  
  > **username_4**: 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)  
  > **username_0**: Interesting.  So I guess natural languages are codes of a Turing complete machine, except that the machine in this case is a biological one (animal), where data exchange is by shaking air (sound) and storage is by altering neural states (brain).  Is there anything done about Turing complete machines that can prove to us that the tightest probability description we have for this fundamental/general level is that of a joint distribution?  
  > **username_4**: I haven't heard anything about it.  
  > **username_0**: Here is my thought: since language conveys any information, it can output any bit sequence.  And since this is "any bit sequence" it means that we cannot assume easy shortcuts, and since non-joint probabilities are only the result of knowing a shortcut (i.e. removing dependence), therefore the only probability for this case is the joint one (unless someone runs an experiment with human brain to conclude that we cannot generate certain bit sequences).  
  
  ---
  
  