Body: <p>One of the main arguments against <span class="math-container">$n$</span>-gram models is that, as <span class="math-container">$n$</span> increases, there is no way to compute <span class="math-container">$P(w_n|w_1,\cdots,w_{n-1})$</span> from training data (since the chance of visiting <span class="math-container">$w_n,...,w_1$</span> is practically zero).</p>
  <p>Wondering why we cannot estimate <span class="math-container">$P(w_n|w_1,\cdots,w_{n-1})$</span> using the following:</p>
  <p>Let <span class="math-container">$P_i(u|v)$</span> be the probability of having sequences where word <span class="math-container">$u$</span> comes exactly <span class="math-container">$i$</span> words after word <span class="math-container">$v$</span> (This is easy to compute).</p>
  <p>Then we can esitmate <span class="math-container">$P(w_n|w_1,\cdots,w_{n-1})$</span> as a function of <span class="math-container">$P_i(u|v)$</span>. I could not find any reference to such approach in the literature. The most similar approach is the smoothing/backoff methods.</p>
  <p>Is there any reason why no-one used this approach? Or if one can share some previous work about this approach.</p>
  <p>P.S.1. The disadvantage of this approach, comparing with standard <span class="math-container">$n$</span>-gram model, is its running time.</p>
  <p>P.S.2. We could use bucketing idea: Instead of computing/storing/using <span class="math-container">$P_i$</span>, for every <span class="math-container">$i$</span>, we can compute/store/use <span class="math-container">$PB_{i}=P_{2^i}$</span> . Then <span class="math-container">$P_i(u|v) \approx PB_{\log i}(u|v)$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-21T18:45:30.780Z
Comments.Text: There is another downside to your suggested approach. It is not as representationally powerful as standard $n$-grams. For example, consider 3-grams on the alphabet $\{0, 1\}$ where the third value is always equal to the XOR of the first 2. With 3-grams, we can represent this, but with your suggested approach, we cannot. It's a bit more like a Naive Bayes-version in that respect. It might work well enough in practice, though.
Comments.UserDisplayName: Robby Goetschalckx
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-09-21T19:45:28.990Z
Comments.Text: @RobbyGoetschalckx That's right: As I said, the proposed approach is an estimator for n-gram model.
Comments.UserDisplayName: Amir
Tags: <machine-learning><natural-language-processing>
Title: Estimating an $n$-Gram model using on bigrams
UserDisplayName: Amir
ThreadText: # Estimating an $n$-Gram model using on bigrams
  
  (Asked by: username_0 on 2020-09-21)
  
  One of the main arguments against $n$-gram models is that, as $n$ increases, there is no way to compute $P(w\_n|w\_1,\cdots,w\_{n-1})$ from training data (since the chance of visiting $w\_n,...,w\_1$ is practically zero).
  
  Wondering why we cannot estimate $P(w\_n|w\_1,\cdots,w\_{n-1})$ using the following:
  
  Let $P\_i(u|v)$ be the probability of having sequences where word $u$ comes exactly $i$ words after word $v$ (This is easy to compute).
  
  Then we can esitmate $P(w\_n|w\_1,\cdots,w\_{n-1})$ as a function of $P\_i(u|v)$. I could not find any reference to such approach in the literature. The most similar approach is the smoothing/backoff methods.
  
  Is there any reason why no-one used this approach? Or if one can share some previous work about this approach.
  
  P.S.1. The disadvantage of this approach, comparing with standard $n$-gram model, is its running time.
  
  P.S.2. We could use bucketing idea: Instead of computing/storing/using $P\_i$, for every $i$, we can compute/store/use $PB\_{i}=P\_{2^i}$ . Then $P\_i(u|v) \approx PB\_{\log i}(u|v)$.
  
  **Tags:** machine-learning, natural-language-processing
  > **Comments:**
  > **username_1**: There is another downside to your suggested approach. It is not as representationally powerful as standard $n$-grams. For example, consider 3-grams on the alphabet $\{0, 1\}$ where the third value is always equal to the XOR of the first 2. With 3-grams, we can represent this, but with your suggested approach, we cannot. It's a bit more like a Naive Bayes-version in that respect. It might work well enough in practice, though.  
  > **username_0**: @RobbyGoetschalckx That's right: As I said, the proposed approach is an estimator for n-gram model.  
  
  ---
  
  ## 0 answers
  
  