# English-Japanese Neural Machine Translation with Encder-Decoder-
Reconstructor

Yukio Matsumura

&Takayuki Sato
Tokyo Metropolitan University
Tokyo, Japan
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
&Mamoru Komachi

###### Abstract

Neural machine translation (NMT) has recently become popular in the field of
machine translation. However, NMT suffers from the problem of repeating or
missing words in the translation. To address this problem, Tu et al. (2017)
proposed an encoder-decoder-reconstructor framework for NMT using back-
translation. In this method, they selected the best forward translation model
in the same manner as Bahdanau et al. (2015), and then trained a bi-
directional translation model as fine-tuning. Their experiments show that it
offers significant improvement in BLEU scores in Chinese-English translation
task. We confirm that our re-implementation also shows the same tendency and
alleviates the problem of repeating and missing words in the translation on a
English-Japanese task too. In addition, we evaluate the effectiveness of pre-
training by comparing it with a jointly-trained model of forward translation
and back-translation.

##  1 Introduction

Recently, neural machine translation (NMT) has gained popularity in the field
of machine translation. The conventional encoder-decoder NMT proposed by Cho
et al. (2014) uses two recurrent neural networks (RNN): one is an encoder,
which encodes a source sequence into a fixed-length vector, and the other is a
decoder, which decodes the vector into a target sequence. A newly proposed
attention-based NMT by Bahdanau et al. (2015) can predict output words using
the weights of each hidden state of the encoder by the attention mechanism,
improving the adequacy of translation.

Even with the success of attention-based models, a number of open questions
remain in NMT. Tu et al. (2016) argued two of the common problems are over-
translation: some words are repeatedly translated unnecessary and under-
translation: some words are mistakenly untranslated. This is due to the fact
that NMT can not completely convert the information from the source sentence
to the target sentence. Mi et al. (2016) and Feng et al. (2016) pointed out
that NMT lacks the notion of coverage vector in phrase-based statistical
machine translation (PBSMT), so unless otherwise specified, there is no way to
prevent missing translations.

Another problem in NMT is an objective function. NMT is optimized by cross-
entropy; therefore, it does not directly maximize the translation accuracy.
Shen et al. (2016) pointed out that optimization by cross-entropy is not
appropriate and proposed a method of optimization based on a translation
accuracy score, such as expected BLEU, which led to improvement of translation
accuracy. However, BLEU is an evaluation metric based on n-gram precision;
therefore, repetition of some words may be present in the translation even
though the BLEU score is improved.

Figure 1: Attention-based NMT.

Figure 2: Encoder-Decoder-Reconstructor.

To address to problem of repeating and missing words in the translation, Tu et
al. (2017) introduce an encoder-decoder-reconstructor framework that optimizes
NMT by back-translation from the output sentences into the original source
sentences. In their method, after training the forward translation in a manner
similar to the conventional attention-based NMT, they train a back-translation
model from the hidden state of the decoder into the source sequence by a new
decoder to enforce agreement between source and target sentences.

In order to confirm the language independence of the framework, we experiment
on two parallel corpora of English-Japanese and Japanese-English translation
tasks using encode-decoder-reconstructor. Our experiments show that their
method offers significant improvement in BLEU scores and alleviates the
problem of repeating and missing words in the translation on English-Japanese
translation task, though the difference is not significant on Japanese-English
translation task.

In addition, we jointly train a model of forward translation and back-
translation without pre-training, and then evaluate this model. As a result,
the encoder-decoder-reconstructor can not be trained well without pre-
training, so it proves that we have to train the forward translation model in
a manner similar to the conventional attention-based NMT as pre-training.

The main contributions of this paper are as follows:

  * •

Experimental results show that encode-decoder-reconstructor framework achieves
significant improvements in BLEU scores (1.0-1.4) for English-Japanese
translation task.

  * •

Experimental results show that encode-decoder-reconstructor framework has to
train the forward translation model in a manner similar to the conventional
attention-based NMT as pre-training.

##  2 Related Works

Several studies have addressed the NMT-specific problem of missing or
repeating words. Niehues et al. (2016) optimized NMT by adding the outputs of
PBSMT to the input of NMT. Mi et al. (2016) and Feng et al. (2016) introduced
a distributed version of coverage vector taken from PBSMT to consider which
words have been already translated. All these methods, including ours, employ
information of the source sentence to improve the quality of translation, but
our method uses back-translation to ensure that there is no inconsistency.
Unlike other methods, once learned, our method is identical to the
conventional NMT model, so it does not need any additional parameters such as
coverage vector or a PBSMT system for testing.

The attention mechanism proposed by Meng et al. (2016) considers not only the
hidden states of the encoder but also the hidden states of the decoder so that
over-translation can be relaxed. In addition, the attention mechanism proposed
by Feng et al. (2016) computes a context vector by considering the previous
context vector to prevent over-translation. These works indirectly reduce
repeating and missing words, while we directly penalize translation mismatch
by considering back-translation.

The encoder-decoder-reconstructor framework for NMT proposed by Tu et al.
(2017) optimizes NMT by reconstructor using back-translation. They consider
likelihood of both of forward translation and back-translation, and then this
framework offers significant improvement in BLEU scores and alleviates the
problem of repeating and missing words in the translation on a Chinese-English
translation task.

##  3 Neural Machine Translation

Here, we describe the attention-based NMT proposed by Bahdanau et al. (2015)
as shown in Figure 2.

The input sequence ($\bm{x}=[x_{1},x_{2},\cdots,x_{|\bm{x}|}]$) is converted
into a fixed-length vector by the encoder using an RNN. At each time step $t$,
the hidden state $h_{t}$ of the encoder is presented as

$h_{t}=[\overrightarrow{h_{t}}^{\top}:\overleftarrow{h_{t}}^{\top}]^{\top}$
(1)

using a bidirectional RNN. The forward state $\overrightarrow{h_{t}}$ and the
backward state $\overleftarrow{h_{t}}$ are computed by

$\overrightarrow{h_{t}}=r(x_{t},h_{t-1})$ (2)

and

$\overleftarrow{h_{t}}=r^{\prime}(x_{t},h_{t+1})$ (3)

where $r$ and $r^{\prime}$ are nonlinear functions. The hidden states
$(h_{1},h_{2},\cdots,h_{|\bm{x}|})$ are converted into a fixed-length vector
$v$ as

$v=q([h_{1},h_{2},\cdots,h_{|\bm{x}|}])$ (4)

where $q$ is a nonlinear function.

The fixed-length vector $v$ generated by the encoder is converted into the
target sequence ($\bm{y}=[y_{1},y_{2},\cdots,y_{|\bm{y}|}]$) by the decoder
using an RNN. At each time step $i$, the conditional probability of the output
word $\hat{y}_{i}$ is computed by

$p(\hat{y}_{i}|\bm{y}_{<i},\bm{x})=f(s_{i},y_{i-1},c_{i})$ (5)

where $f$ is a nonlinear function. The hidden state $s_{i}$ of the decoder is
presented as

$s_{i}=g(s_{i-1},y_{i-1},c_{i})$ (6)

using the hidden state $s_{i-1}$ and the target word $y_{i-1}$ at the previous
time step and the context vector $c_{i}$.

The context vector $c_{i}$ is a weighted sum of each hidden state $h_{j}$ of
the encoder. It is presented as

$c_{i}=\sum_{j=1}^{|x|}\alpha_{ij}h_{j}$ (7)

and its weight $\alpha_{ij}$ is a normalized probability distribution. It is
computed by

$\alpha_{ij}=\frac{\exp(e_{ij})}{\sum_{k=1}^{|x|}\exp(e_{ik})}$ (8)

and

$e_{ij}=v_{a}^{\top}\tanh(W_{a}s_{i-1}+U_{a}h_{j})$ (9)

where $v_{a}$ is a weight vector and $W_{a}$ and $U_{a}$ are weight matrices.

The objective function is defined by

$\begin{split}\mathcal{L}(\theta)&=\frac{1}{N}\sum\nolimits_{n=1}^{N}\sum_{i=1}^{|y|}\log{p(\hat{y}_{i}^{(n)}|\bm{y}_{<i}^{(n)},\bm{x}^{(n)},\theta)}\end{split}$
(10)

where $N$ is the number of data and $\theta$ is a model parameter.

Incidentally, as a nonlinear function, the hyperbolic tangent function or the
rectified linear unit are generally used.

| ASPEC | NTCIR
---|---|---
train | 827,188 | 1,169,201
dev | 1,504 | 2,741
test | 1,556 | 2,300
Table 1: Numbers of parallel sentences. English-Japanese
---
Corpus | Model | BLEU |  $p$-value | Hours
| Baseline-NMT | 29.75 | - | 99
ASPEC | +Reconstructor | 30.76 | 0.00 | 149
| +Reconstructor (Jointly-Training) | 26.04 | - | 174
| Baseline-NMT | 30.03 | - | 116
NTCIR | +Reconstructor | 31.40 | 0.00 | 166
| +Reconstructor (Jointly-Training) | 29.04 | - | 252
Table 2: English-Japanese translation results. Japanese-English
---
Corpus | Model | BLEU |  $p$-value | Hours
| Baseline-NMT | 21.91 | - | 87
ASPEC | +Reconstructor | 22.27 | 0.10 | 127
| +Reconstructor (Jointly-Training) | 16.29 | - | 187
| Baseline-NMT | 29.48 | - | 180
NTCIR | +Reconstructor | 29.73 | 0.11 | 244
| +Reconstructor (Jointly-Training) | 28.95 | - | 300
Table 3: Japanese-English translation results.

##  4 Encoder-Decoder-Reconstructor

###  4.1 Architecture

Next, we describe the encoder-decoder-reconstructor framework for NMT proposed
by Tu et al. (2017) as shown in Figure 2. The encoder-decoder-reconstructor
consists of two components: the standard encoder-decoder as an attention-based
NMT proposed by Bahdanau et al. (2015) and the reconstructor which back-
translates from the hidden states of decoder to the source sentence.

In their method, the hidden state of the decoder is back-translated into the
source sequence ($\bm{x}$) by the reconstructor for the back-translation. At
each time step $i$, the conditional probability of the output word
$\hat{x}_{i}$ is computed by

$p(\hat{x}_{i}|\bm{x}_{<i},\bm{\hat{y}})=f^{\prime}(s^{\prime}_{i},x_{i-1},c^{\prime}_{i})$
(11)

where $f^{\prime}$ is a nonlinear function. The hidden state $s^{\prime}_{i}$
of the reconstructor is presented as

$s^{\prime}_{i}=g^{\prime}(s^{\prime}_{i-1},x_{i-1},c^{\prime}_{i})$ (12)

using the hidden state $s^{\prime}_{i-1}$ and the source word $x_{i-1}$ at the
previous time step and the new context vector (inverse context vector)
$c^{\prime}_{i}$.

The inverse context vector $c^{\prime}_{i}$ is a weighted sum of each hidden
state $s_{j}$ of the decoder (on forward translation). It is presented as

$c^{\prime}_{i}=\sum_{j=1}^{|y|}\alpha^{\prime}_{ij}s_{j}$ (13)

and its weight $\alpha^{\prime}_{ij}$ is a normalized probability
distribution. It is computed by

$\alpha^{\prime}_{ij}=\frac{\exp(e^{\prime}_{ij})}{\sum_{k=1}^{|y|}\exp(e^{\prime}_{ik})}$
(14)

and

$e^{\prime}_{ij}=v^{\prime}_{a}{\top}\tanh(W^{\prime}_{a}s^{\prime}_{i-1}+U^{\prime}_{a}s_{j})$
(15)

where $v^{\prime}_{a}$ is a weight vector and $W^{\prime}_{a}$ and
$U^{\prime}_{a}$ are weight matrices.

The objective function is defined by

$\begin{split}\mathcal{L}(\theta,\gamma)&=\frac{1}{N}\sum\nolimits_{n=1}^{N}\Bigl{\\{}\sum_{i=1}^{|y|}\log{p(\hat{y}_{i}^{(n)}|\bm{y}_{<i}^{(n)},\bm{x}^{(n)},\theta)}\\\
&\quad+\lambda\sum_{i=1}^{|x|}\log{p(\hat{x}_{i}^{(n)}|\bm{x}_{<i}^{(n)},\bm{s}^{(n)},\gamma)}\Bigr{\\}}\end{split}$
(16)

where $N$ is the number of data, $\theta$ and $\gamma$ are model parameters
and $\lambda$ is a hyper-parameter which can consider the weight between
forward translation and back-translation.

This objective function consists of two parts: forward measures translation
fluency, and backward measures translation adequacy. Thus, the combined
objective function is more consistent with the goal of enhancing overall
translation quality, and can more effectively guide the parameter training for
making better translation.

Example 1: Improvement in under-translation.
---
Input |  the conditions under which the effect of turbulent viscosity is correctly evaluated were examined on the basis of the relation between turbulent viscosity and numerical viscosity in size .
Baseline-NMT |  乱 流 粘性 の 影響 を 正確 に 評価 する 条件 を 検討 し た 。
+Reconstructor |  乱 流 粘性 の 影響 を 正確 に 評価 する 条件 を , 乱 流 粘性 と 数値 的 粘性
|  の 関係 を 基 に 調べ た 。
+Reconstructor |  乱 流 粘性 の 影響 を 考慮 し た 条件 を , 乱 流 粘性 と 粘性 の 粘性 と の
(Jointly-Training) |  関係 を もと に 検討 し た 。
Reference |  乱 流 粘性 と 数値 粘性 の 大小 関係 により , 乱 流 粘性 の 効果 が 正しく 評価 さ れる 条件 を 検討 し た 。

Example 2: Improvement in over-translation.
---
Input |  activity was high in cells of the young , especially newborn infant , and was very slight in cells of 30 ‐ year ‐ old or more .
Baseline-NMT |  活動 性 は 若 齢 , 特に 新生児 新生児 で は 30 歳 以上 の 細胞 で 高く ,
|  30 歳 以上 の 細胞 で は わずか で あっ た 。
+Reconstructor |  その 活性 は 若 齢 , 特に 新生児 は 細胞 が 高く , 30 歳 以上 の 細胞 で は
|  わずか で あっ た 。
+Reconstructor |  若 齢 の 新生児 で は 活性 は 高かっ た が , 30 歳 以上 の 場合 に は 極めて
(Jointly-Training) |  軽度 で あっ た 。
Reference |  活性 は 若い 個体 , 特に 新生児 の 細胞 で 高く , 30 歳 以上 の もの で は ごく わずか で あっ た 。

Table 4: Examples of outputs of English-Japanese translation.

Baseline-NMT

Encoder-Decoder-Reconstructor

Figure 3: The attention layer in Example 1 : Improvement in under-translation.

Baseline-NMT

Encoder-Decoder-Reconstructor

Figure 4: The attention layer in Example 2 : Improvement in over-translation.

###  4.2 Training

The encoder-decoder-reconstructor is trained with likelihood of both the
encoder-decoder and the reconstructor on a set of training datasets. Tu et al.
(2017) trained a back-translation model from the hidden state of the decoder
into the source sequence by reconstructor to enforce agreement between source
and target sentences using Equation 16 after training the forward translation
in a manner similar to the conventional attention-based NMT using Equation 10.

In addition, we experiment to jointly train a model of forward translation and
back-translation without pre-training. It may learn a globally optimal model
compared to locally optimal model pre-trained using the forward translation.

###  4.3 Testing

Tu et al. (2017) used a beam search to predict target sentences that
approximately maximizes both of forward translation and back-translation on
testing. In this paper, however, we do not use a beam search for simplicity
and effectiveness.

Corpus | Model | English-Japanese | Japanese-English
---|---|---|---
|  | (i) | (ii) | (iii) | (i) | (ii) | (iii)
| Baseline-NMT | 1,141 | 378 | 1,045 | 951 | 494 | 1,085
ASPEC | +Reconstructor | 988 | 336 | 1,042 | 836 | 418 | 1,014
| +Reconstructor (Jointly-Training) | 1,292 | 446 | 1,147 | 1,106 | 525 | 1,821
| Baseline-NMT | 2,122 | 1,015 | 1,106 | 2,521 | 1,073 | 1,630
NTCIR | +Reconstructor | 1,958 | 922 | 963 | 2,187 | 987 | 1,422
| +Reconstructor (Jointly-Training) | 1,978 | 916 | 1,078 | 2,475 | 1,107 | 1,610
Table 5: Numbers of redundant and unknown word tokens.

##  5 Experiments

We evaluated the encoder-decoder-reconstructor framework for NMT on English-
Japanese and Japanese-English translation tasks.

###  5.1 Datasets

We used two parallel corpora: Asian Scientific Paper Excerpt Corpus (ASPEC)
Nakazawa et al. (2016) and NTCIR PatentMT Parallel Corpus Goto et al. (2013).
Regarding the training data of ASPEC, we used only the first 1 million
sentences sorted by sentence-alignment similarity. Japanese sentences were
segmented by the morphological analyzer MeCab (version 0.996, IPADIC), and
English sentences were tokenized by tokenizer.perl of Moses. Table 1 shows the
numbers of the sentences in each corpus. Note that sentences with more than 40
words were excluded from the training data.

###  5.2 Models

We used the attention-based NMT Bahdanau et al. (2015) as a baseline-NMT, the
encoder-decoder-reconstructor Tu et al. (2017) and the encoder-decoder-
reconstructor that jointly trained forward translation and back-translation
without pre-training. The RNN used in the experiments had 512 hidden units,
512 embedding units, 30,000 vocabulary size and 64 batch size. We used Adagrad
(initial learning rate 0.01) for optimizing model parameters. We trained our
model on GeForce GTX TITAN X GPU. Note that we set the hyper-parameter
$\lambda=1$ on the encoder-decoder-reconstructor same as Tu et al. (2017).

###  5.3 Results

Tables 2 and 3 show the translation accuracy in BLEU scores, the $p$-value of
the significance test by bootstrap resampling Koehn (2004) and training time
in hours until convergence. The encoder-decoder-reconstructor Tu et al. (2017)
requires slightly longer time to train than the baseline NMT, but we emphasize
that decoding time remains the same with the encoder-decoder-reconstructor and
baseline-NMT. The results show that the encoder-decoder-reconstructor Tu et
al. (2017) significantly improves translation accuracy by 1.01 points on ASPEC
and 1.37 points on NTCIR in English-Japanese translation ($p<0.05$). However,
it does not significantly improve translation accuracy in Japanese-English
translation. In addition, it is proved that the encoder-decoder-reconstructor
without pre-training worsens rather than improves translation accuracy.

Table 4 shows examples of outputs of English-Japanese translations. In Example
1, “乱 流 粘性 と 数値 粘性 の 大小 関係 により ,” (on the basis of the relation between
turbulent viscosity and numerical viscosity in size) is missing in the output
of baseline-NMT, but “乱 流 粘性 と 数値 的 粘性 の 関係 を 基 に” (on the basis of the
relation between turbulent viscosity and numerical viscosity) is present in
the output of encoder-decoder-reconstructor. In Example 2, “新生児” (newborn
infant) and “30歳以上の” (of 30 ‐ year ‐ old or more) are repeated in the output
of baseline-NMT, but they appear only once in the output of encoder-decoder-
reconstructor.

In addition, Figures 4 and 4 show the attention layer on baseline-NMT and
encoder-decoder-reconstructor in each example. In Figure 4, although the
attention layer of baseline NMT attends input word “turbulent”, the decoder
does not output “乱流” (turbulent) but “検討” (examined) at the 13th word. Thus,
under-translation may be resulted from the hidden layer or the embedding layer
instead of the attention layer. In Figure 4, it is found that the attention
layer of baseline-NMT repeatedly attends input words “newborn infant” and “30
‐ year ‐ old or more”. Consequently, the decoder repeatedly outputs “新生児”
(newborn infant) and “30歳以上の” (of 30 ‐ year ‐ old or more). On the other hand,
the attention layer of encoder-decoder-reconstructor almost correctly attends
input words.

Table 5 shows a comparison of the number of word occurrences for each corpus
and model. The columns show (i) the number of words that appear more
frequently than the counterparts in the reference, and (ii) the number of
words that appear more than once but are not included in the reference. Note
that these numbers do not include unknown words, so (iii) shows the number of
unknown words. In all the cases, the number of occurrence of redundant words
is reduced in encoder-decoder-reconstructor. Thus, we confirmed that encoder-
decoder-reconstructor achieves reduction of repeating and missing words while
maintaining the quality of translation.

##  6 Conclusion

In this paper, we evaluated the encoder-decoder-reconstructor on English-
Japanese and Japanese-English translation tasks. In addition, we evaluate the
effectiveness of pre-training by comparing it with a jointly-trained model of
forward translation and back-translation. Experimental results show that the
encoder-decoder-reconstructor offers significant improvement in BLEU scores
and alleviates the problem of repeating and missing words in the translation
on English-Japanese translation task, and the encoder-decoder-reconstructor
can not be trained well without pre-training, so it proves that we have to
train the forward translation model in a manner similar to the conventional
attention-based NMT as pre-training.

## References

  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural Machine Translation by Jointly Learning to Align and Translate.  Proceedings of the 3rd International Conference on Learning Representations (ICLR), pages 1–15.
  * Cho et al. (2014) Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014.  Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translation.  Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1724–1734.
  * Feng et al. (2016) Shi Feng, Shujie Liu, Nan Yang, Mu Li, and Ming Zhou. 2016.  Improving Attention Modeling with Implicit Distortion and Fertility for Machine Translation.  Proceedings of the 26th International Conference on Computational Linguistics (COLING), pages 3082–3092.
  * Goto et al. (2013) Isao Goto, Ka-Po Chow, Bin Lu, Eiichiro Sumita, and Benjamin K Tsou. 2013.  Overview of the Patent Machine Translation Task at the NTCIR-10 Workshop.  Proceedings of the 10th NII Testbeds and Community for Information access Research Conference (NTCIR), pages 260–286.
  * Koehn (2004) Philipp Koehn. 2004.  Statistical Significance Tests for Machine Translation Evaluation.  Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 388–395.
  * Meng et al. (2016) Fandong Meng, Zhengdong Lu, Hang Li, and Qun Liu. 2016.  Interactive Attention for Neural Machine Translation.  Proceedings of the 26th International Conference on Computational Linguistics (COLING), pages 2174–2185.
  * Mi et al. (2016) Haitao Mi, Baskaran Sankaran, Zhiguo Wang, and Abe Ittycheriah. 2016.  Coverage Embedding Models for Neural Machine Translation.  Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 955–960.
  * Nakazawa et al. (2016) Toshiaki Nakazawa, Manabu Yaguchi, Kiyotaka Uchimoto, Masao Utiyama, Eiichiro Sumita, Sadao Kurohashi, and Hitoshi Isahara. 2016.  ASPEC: Asian Scientific Paper Excerpt Corpus.  Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC), pages 2204–2208.
  * Niehues et al. (2016) Jan Niehues, Eunah Cho, Thanh-Le Ha, and Alex Waibel. 2016.  Pre-Translation for Neural Machine Translation.  Proceedings of the 26th International Conference on Computational Linguistics (COLING), pages 1828–1836.
  * Shen et al. (2016) Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. 2016\.  Minimum Risk Training for Neural Machine Translation.  Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1683–1692.
  * Tu et al. (2017) Zhaopeng Tu, Yang Liu, Lifeng Shang, Xiaohua Liu, and Hang Li. 2017.  Neural Machine Translation with Reconstruction.  Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI), pages 3097–3103.
  * Tu et al. (2016) Zhaopeng Tu, Zhengdong Lu, Yang Liu, Xiaohua Liu, and Hang Li. 2016.  Modeling Coverage for Neural Machine Translation.  Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL), pages 76–85.


The primary use of any probabilistic model involving a set of random variables is to run inference and sampling queries on it. Inference queries in classical probabilistic models is concerned by the computation of marginal or conditional probabilities of events given as an input. When the probabilistic model is sequential, more sophisticated marginal inference queries involving complex grammars may be of interest in fields such as computational linguistics and NLP. In this work, we address the question of computing the likelihood of context-free grammars (CFGs) in Hidden Markov Models (HMMs). We provide a dynamic algorithm for the exact computation of the likelihood for the class of unambiguous context-free grammars. We show that the problem is NP-Hard, even with the promise that the input CFG has a degree of ambiguity less than or equal to 2. We then propose a fully polynomial randomized approximation scheme (FPRAS) algorithm to approximate the likelihood for the case of polynomially-bounded ambiguous CFGs.

Hidden Markov Models, Context-Free Grammars, Marginal Inference

Due to their simplicity and ease  of interpretation, Hidden Markov Models (HMMs) represent an important class of dynamic probabilistic models finding  its applications in many fields (bioinformatics, NLP, speech processing etc.). With regard to making inference in HMMs, two popular algorithms were proposed in the litterature: The forward algorithm and the Viterbi algorithm. The former computes the likelihood of generating a given sequence, while the latter is dedicated to the decoding problem. Algorithms for more elaborate marginal queries can be obtained by observing that HMMs restricted to a bounded support are nothing but tree-structured bayesian networks. Luckily, exact inference in this class of probabilistic models is known to be tractable ([Koller and Friedman, 2009]). With this correspondance, one can readily obtain procedures to compute infix (or, more generally island) probabilities in HMMs by straightforward reduction. In most applications where HMMs are employed, this suite of marginal inference queries proved to be sufficient for the task of interest. Yet, in fields such as computationnal linguistics, deeper structures of sequential data involving complex grammars are of interest. For instance, when HMMs are used in NLP tasks such as language modeling, we might be interested in extracting emergent grammars in the language model. Other concerns are related to the dicriminative bias in language models. Indeed, recent studies showed that trained language models are subject of capturing negative stereotypes present in the corpus used for training ([Sheng et al., 2019]), a problem that raises a major ethical concern regarding the deployment of these models in real-case situations. The goal of this article is to explore the perspective of widening the scope of marginal inference queries we can make on HMMs by bringing to the picture languages generated by sophisticated grammars. Informally, let $\mathcal{R}$ be a class of machines/grammars inducing languages over the alphabet formed by the observation space of the HMM, the $\mathcal{R}$-likelihood problem can be stated as follows: Given an HMM $M$, a machine/grammar $R \in \mathcal{R}$ and an integer $L>0$: How to compute the likelihood of generating a sequence of length $L$ from $M$ accepted by $R$?

From the perspective of formal language theory, this problem can be seen as a generalization of the classical problem of counting the number of words accepted by a given machine/grammar. This counting problem is easily reducible to our problem, by choosing $M$ to be the trivial single-state HMM that assigns equal mass probability to all words at a given length. Therefore, by this straightforward reduction, one can show that the $\mathcal{R}$-likelihood problem is $\#$P-Hard when $\mathcal{R}$ is the class of nondeterministic finite automata ([Kannan et al., 1995]). A fortiori, same negative results hold for general context-free grammars.

Positive results of the $\mathcal{R}$-likelihood problem can be found in the litterature of computational linguistics interested in the closely related problem of computing the weight of different classes of languages in stochastic grammars such as probabilistic context-free grammars and probabilistic finite automata (PFAs). Indeed, HMMs bounded to a given length can be efficiently converted to a PFA. Therefore, an algorithm designed for PFAs to compute the weight of languages represented by a class of machines/grammars $\mathcal{R}$ can be adapted to our problem. Earlier works adressed the problem of computing the weight of prefixes, suffixes and infixes in PFAs ([Corazza et al., 1991], [Fred, 2000]). Recently, [Cognetta et al., 2018, Cognetta et al., 2019] proposed an incremental algorithm for computing the weight of regular languages in PFAs, where the regular languages are represented by unambiguous regular expressions.

In this article, we shall be interested in computing the likelihood of languages generated by different subclasses of  CFGs from HMMs (i.e. when $\mathcal{R}$ is a subclass of CFGs). The studied subsclasses will correspond to the hirerarchy of CFGs according to their ambiguity degree. The outline of the article is as follows: In Section 1, we present algebric descriptions of machines/grammars of interest in this article, that is CFGs and HMMs. In Section 2, we present a polynomial-time dynamic algorithm for solving the likelihood problem for the case of unambiguous context-free grammars (UCFG). In Section 3, we prove that the likelihood problem is NP-Hard even with the promise that the input CFG has an ambiguity degree less or equal to 2. We give afterwards a randomized procedure that provides FPRAS guarantees of the likelihood problem for the case of CFGs with polynomial ambiguity degree.

§ ALGEBRIC DESCRIPTIONS OF CFGS/HMMS

Let $\Sigma$ be a finite alphabet, and $\epsilon$ a special symbol representing the empty word. $\Sigma^{+}$ is the set of all strings formed by alphabet $\Sigma$, and $\Sigma^{*} = \Sigma^{+} \cup \{\epsilon\}$. For a given string $w \in \Sigma^{*}$, we denote by $|w|$ its length, by $w_{i:j}$ the substring of $w$ that spans from the $i$-th letter to the $j$-th letter in $w$, and $w_{i}$ to refer to its $i$-th letter.  For a given integer $n > 0$, we denote by $[n]$ the set of all integers from $1$ to $n$. A language $f$ is a mapping from $\Sigma^{*}$ to $\mathbb{R}$. When the image of the mapping is binary, then we call the language binary, in which case the language represents a subset of $\Sigma^{*}$. We extend the definition of languages to binary languages over $\Sigma^{*}$: For a subset $L \subseteq \Sigma^{*}$, $f(L) \myeq \sum\limits_{w \in L} f(w)$ which may be infinite. The indicator function of a set $X$ is denoted by $\delta_{X}$. When a language $f$ is described by a machine/grammar $M$, we'll use the notation $f_{M}$ to refer to the language induced by $M$.

$\bullet$ Linear Algebra. For a subset $I \subseteq [n]$, the vector of dimension $n$ in which all elements indexed by an element in $I$ are equal to 1 and 0 otherwise will be denoted $e_{I}^{(n)}$. When the dimension of the vector is clear from context, we omit the superscript. The transpose of a vector $v$ will be denoted by $v^{T}$. For two matrices $A, ~B$, the kronecker product will be denoted as $A \otimes B$ ([Zhang and Ding, 2013]).
For a matrix $\mathbb{R}^{n \times m}$, $vec(A)$ denotes the vector in $\mathbb{R}^{n.m}$ that results from stacking columns of $A$ vertically. A generalization of vectors and matrices is tensors. A tensor is a multidimensional array $\mathbb{R}^{n_{1} \times..\times n_{d}}$, where $d$ is called the order of a tensor. The $(i_{1},..i_{d})$-th element of a tensor $\mathcal{T}$ will be denoted $\mathcal{T}[i_{1},..i_{d}]$. The mode-$k$ matriciziation of a tensor $\mathcal{T}$, denoted $\mathcal{T}_{k}$, is a reshape of a tensor into a matrix in $\mathbb{R}^{n_{k} \times n_{1}\dots n_{i-1}n_{i+1} \dots n_{d}}$. The columns $\mathcal{T}_{k}$ are the vectors

$$\{\mathcal{T}[i_{1},i_{2} \dots i_{k-1},:,i_{k+1},i_{d}]: (i_{1},\dots i_{k-1},i_{k+1},\dots,n_{d}) \in \mathbb{R}^{n_{1}}\times..\mathbb{R}^{n_{k-1}}\times \mathbb{R}^{n_{k+1}}\times..\times \mathbb{R}^{n_{d}} \}$$

stacked in the inverse lexicographical order. The kronecker product to two tensors $\mathcal{T},~\mathcal{M}$ of the same order, denoted $\mathcal{M} \otimes \mathcal{T}$, is given as $(\mathcal{T} \otimes \mathcal{M})_{k} = \mathcal{T}_{k} \otimes \mathcal{M}_{k}$, for some $k \in [d]$. One can verify that the resulting tensor is independent of the chosen dimension.

§.§ Context-Free Grammars.

A context-free grammar (CFG) $G$ in Chomsky form is represented by the tuple $G = <[n], \Sigma, R, S>$ where $[n]$ is the set of non-terminal symbols, $R$ is a set of production rules each having one of the following form: $i \rightarrow jk$ or $i \rightarrow \sigma$ where $i,j,k$ are non-terminals and $\sigma$ is a terminal symbol and $S \in [n]$ is the initial non-terminal symbol. The size of a CFG, denoted $|G|$, is equal to the cardinality of the set of production rules. A valid derivation tree of $G$ is a binary tree whose internal nodes are labelled by non-terminal symbols of $G$, and satisfies the following syntactic constraints: (a) The root node of the tree is labelled by $S$, (b) For any internal node $N$ labelled by a non-terminal symbol $i$, the labels of its children nodes must correspond to a production rule in $R$ from left to right.
The binary language accepted by $G$, denoted $L_{G}$, is the set of strings $w \in \Sigma^{*}$ for which there exists at least one derivation tree whose leaf nodes are labelled by $w$ (reading from left to right).

Using close connections between CFGs and tree automata, an alternative algebric representation of CFGs will be particularly useful in the context of our work:
Let $G= <[n], \Sigma, R, S>$ be a CFG in Chomsky Form. The algebraic representation of $G$ is given by the tuple: $G = <[n], \pi, \mathcal{M}, \{\beta_{\sigma}\}_{\sigma \in \Sigma}>$, where:

* $\pi \in \mathbb{R}^{n}$ is the initial vector equal to $e_{\{S\}}$,

* $\mathcal{M} \in \mathbb{R}^{n \times n \times n}$ is a tensor of order 3 where $\mathcal{T}(i,j,k) = 1$ if $i \rightarrow jk$ is in $R$, 0 otherwise,

* $\beta_{\sigma} \in \mathbb{R}^{n}$ is a vector associated to each symbol $\sigma$ in the alphabet where $\beta_{\sigma}[i] = 1$ if $i \rightarrow \sigma$ is in $R$, 0 otherwise

The algebric representation of a CFG $G$ associates to each tree structure $t$ a vector $\beta_{t}$ using the following recursive formula:

$\bullet$ The tree associated to a terminal symbol $\sigma \in \Sigma$, denoted $t(\sigma)$, is equal to $\beta_{\sigma}$,

$\bullet$ For two trees $t_{1}, t_{2}$, the embedding vector of the tree formed by adding a new root node and binding $t_{1}$ (resp. $t_{2}$) in its left (resp. right) is equal to $\mathcal{M}_{1} (\beta_{t_{1}} \otimes \beta_{t_{2}})$

$~~$ The language generated by the algebric representation of CFGs is given as: $f_{G}(w) = \pi^{T}.\sum\limits_{t: yield(t) = w} \beta_{t}$, which corresponds to
the number of valid derivation trees yielding a string $w \in \Sigma^{*}$.
This expression is not useful in practice as it involves the enumeration of all trees that yield a string $w$. We shall favor another way to compute $f_{G}$ that gives rise a more practical expression. Define the map $\beta_{G}: \Sigma^{*} \rightarrow \mathbb{R}^{n}$ where $\beta_{G}(w) = \sum\limits_{t: yield(t) = w} \beta_{t}$, we have:

\begin{equation} \label{betagw}
\beta_{G}(w) = \mathcal{M}_{1} \cdot [ \sum\limits_{\substack{w_{1}, w_{2} \in \Sigma^{+} \\ w_{1}w_{2} = w}} \beta_{G}(w_{1}) \otimes \beta_{G}(w_{2})]
\end{equation}

For $i \in [n]$, $\beta_{G}(w)[i]$ represents the number of derivation trees yielding $w$ whose root node is $i$. The expression (<ref>) expresses the fact that a derivation tree whose yield $w$ is necessarly obtained by a concatenation of two substrees yielding a factorization of $w$. The growth function for a CFG $G$ is a mapping $\phi_{G}: \mathbb{N} \rightarrow \mathbb{N}$ such that $\phi_{G}(n) = \max\limits_{w \in \Sigma^{n}} f_{G}(w)$. The hierarchisation of CFGs according to their ambiguity degree was extensively studied in the literature as an attempt to identify subsclasses of CFGs with interesting theoretical and computational properties ( [Shamir, 1971], [Crestin, 1972], [Wich, 2001, Wich, 2005]). We distinguish:

* CFGs with constant ambiguity: $\sup\limits_{n \in \mathbb{N}} \phi_{G}(n) \leq k$, for some $k > 0$. If $k=1$, then the CFG is said to be unambiguous (UCFG).

* CFGs with polynomial ambiguity (POLYCFG): $\phi_{G}(n) \leq \Theta(n^{k})$ for some $k > 0$,

* CFGs with exponential ambiguity (EXPCFG): $\phi_{G}(n) \leq 2^{\Theta(n)}$

§.§ Hidden Markov Models:

The observable operator representation of a HMM is given by the triplet $A = <[n], \pi, \{A_{\sigma}\}_{\sigma \in \Sigma}>$, where $\pi$ is a probability distribution over $[n]$, and $\{A_{\sigma}\}_{\sigma \in \Sigma}$ are positive matrices in $\mathbb{R}^{n \times n}$ such that $\sum\limits_{\sigma \in \Sigma} A_{\sigma}$ is a stochastic matrix [A non-negative matrix $A \in \mathbb{R}^{n \times n}$ is said to be stochastic if $\forall i \in [n]: \sum\limits_{j \in [n]} A[i,j] = 1 $]. The language induced by an HMM $A$ is given as: $f_{A}(w) = \pi^{T}.A_{w}.e_{[n]} = (e_{[n]} \otimes \pi)^{T}.vec(A_{w})$, where by definition $A_{w} \myeq \prod\limits_{i=1}^{|w|} A_{w_{i}}$.
For any $n \in \mathbb{N}$, the function induced by an HMM restricted to the support $\Sigma^{n}$ defines a probability distribution. To make the connection with CFGs, we shall design a tensorized representation of HMMs, derived from the observable operator representation. This tensorized representation is given in theorem <ref>, and can be seen as a reshape of the HMM into a CFG given in algebric representation.

Let $A' = <[n'], \pi', \{A'_{\sigma}\}_{\sigma \in \Sigma}>$ be an HMM. For any string $w \in \Sigma^{*}$, for any factorization $w = w_{1}.w_{2}$, we have

$$ f_{A'}(w) = (e_{[n']} \otimes \pi')^{T} \cdot \mathcal{T}_{1} \cdot  (vec(A'_{w_{1}}) \otimes vec(A'_{w_{2}}))$$

where the tensor $\mathcal{T} \in \mathbb{R}^{n'^{2} \times n'^{2} \times n'^{2}}$ is given as

$$\mathcal{T}(\phi(i_{1},j_{1}),\phi(i_{2},j_{2}),\phi(i_{3},j_{3})) \myeq \begin{cases} 1 & \text{if}~~ i_{1} = i_{2} \land j_{1} = j_{3} \land j_{2}=i_{3} \\ 0 & \text{otherwise}\end{cases}$$

for $\phi:[n'] \times [n'] \rightarrow [n'^{2}]$ an (invertible) mapping such that $\phi(i,j) = (i-1) \cdot n + j$

The proof of theorem <ref> is given in appendix A. It relies mostly on careful algebric manipulation of matrices and tensors. Note that the tensor $\mathcal{T}$ is a sparse binary tensor whose number of non-zero elements is equal to $n'^{3}$.

Before presenting the algorithm for computing the likelihood of generating strings in an UCFGs from HMMs, we shall first examine the complexity of the same problem applied to the restricted class of CFGs with bounded constant ambiguity.

Define the counting problem:

The k-CFG likelihood problem

$\bullet$ Instance: A CFG G with constant ambiguity $k$, An HMM $A'$, a length $L > 0$

$\bullet$ Problem: Compute $f_{A'}(L_{G} \cap \Sigma^{L})$

When the ambiguity level $k$ is treated as a complexity parameter, the problem is computationaly intractable.

The k-CFG counting problem is #P-Hard.

The reduction is from the #3SAT problem. The #3SAT problem takes as input a propositional formula made of conjective form where each clause is made of 3 litterals and outputs the number of true assignments of the formula.

Let $F = C_{1} \land C_{2} \land ..C_{k}$ be a propositional formula with $k$ clauses containing litterals from a set of $n$ boolean variables $\mathcal{X} = \{x_{i}\}_{i \in [n]}$, where each clause $C_{j}$ is a conjuction of 3 litterals written as $C_{j} = l_{1}^{(j)} \lor l_{2}^{(j)} \lor l_{3}^{(j)}$. Let #F denote the number of true assignments of the formula. Without a loss of generality, we equip the set of variables $\mathcal{X}$ with a relation order associated with its index, which makes a one-to-one correspondance between the set of assignments and the set of strings $\{0,1\}^{n}$. A clause $C_{j}$ can be seen as a representation of a set of strings, denoted $L_{C_{j}}$, in $\{0,1\}^{n}$ corresponding to the set of assignments of the variables that satisfy the clause. For each clause $C_{j}$ in the formula, we construct a UCFG $G_{j}$ such that $L_{G_{j}} = \bar{L}_{C_{k}} \cap \Sigma^{n}$, i.e. $L_{G_{j}}$ represents the set of all strings corresponding to assignments that don't satisfy the clausse $C_{j}$. One can verify that the construction of a determinstic finite automaton of size $n$ representing the language $\bar{L}_{C_{k}} \cap \{0,1\}^{n}$ is straightforward. Converting a determinstic finite automaton of size $n$ to an equivalent determinstic context-free grammar (hence, unambiguous) of same size is also straightforward. Let $G$ be the CFG that represents the union of languages induced by $\{G_{j}\}_{j \in [k]}$. $G$ is constructed by introducing a new root symbol $S$, and adding new production rules such that for each grammar $G_{j}$, we have $S \rightarrow N.N'$ if $S_{j} \rightarrow N.N'$ where $S_{j}$ is the root symbol of $G_{j}$, and omitting the production rule $S_{j} \rightarrow NN'$ from the grammar $G$.   It's easy to check that this construction can be done in polynomial time with respect to $n$ and $k$. Moreover, $G$ satisfies two additional properties: (1) the ambiguity of the constructed CFG is less than $k$, (2) $w \not \in L_{G} \cap \{0,1\}^{n}$ if and only if the assignment of variables associated to $w$ satisfies the formula $F$.

By (2), we have $\#F = |\bar{L}_{G}  \cap \Sigma^{n}| = 2^{n}. f_{A'}(\bar{L}_{G} \cap \{0,1\}^{n})$, where $A'$ is the trivial single-state HMM over the observation space $\{0,1\}$ such that $f_{A'}(w) = (\frac{1}{2})^{|w|}$. This is equivalent to $\#F = 2^{n}.(1 - f_{A'}(L_{G} \cap \{0,1\}^{n}))$.

§ THE LIKELIHOOD PROBLEM FOR UNAMBIGUOUS CONTEXT-FREE GRAMMARS

The $UCFG$-Likelihood problem can be formally defined as follows:

Let $G = <[n], \pi, \mathcal{M}, \{\beta_{\sigma}\}_{\sigma \in \Sigma}>$ be an algebric description of a UCFG, $A' = <[n'], \pi', \{A'_{\sigma}\}_{\sigma \in \Sigma}>$ be an HMM, and $L > 0$ an integer, the problem is to compute $f_{A'}(L_{G} \cap \Sigma^{L})$.

In this section, we shall derive a dynamic algorithm for solving the $UCFG$-Likelihood problem. For this, we first rewrite the quantity of interset $f_{A'}(L_{G} \cap \Sigma^{L})$ in a suitable algebric form. We have, for any $L > 0$

\begin{align}
f_{A'}(L_{G} \cap \Sigma^{L}) &= \sum\limits_{w \in \Sigma^{L}} \delta_{L_{G}}(w) \cdot f_{A'}(w) \nonumber \\
&= \sum\limits_{w \in \Sigma^{L}} [\pi^{T} \cdot \beta_{G}(w)]. [(e_{[n']} \otimes \pi')^{T} \cdot vec(A'_{w})] \nonumber \\
&= \sum\limits_{w \in \Sigma^{L}} (\pi \otimes e_{ [n']} \otimes \pi')^{T} \cdot (\beta_{G}(w) \otimes vec(A'_{w})) \nonumber \\
&= (\pi \otimes e_{[n']} \otimes \pi')^{T} \cdot \beta_{G,A'}^{(L)} \label{betasum}
\end{align}

where $\beta_{G,A'}^{(L)} \myeq \sum\limits_{w \in \Sigma^{L}} \beta_{G}(w) \otimes vec(A'_{w})$.
The transition from the first to the second equality is due to the fact that, for UCFGs, $f_{G} = \delta_{L_{G}}$, and the third equality is due to the mixed-product property of the kronecker product (i.e. $(AC) \otimes (BD) = (A \otimes B).(C \otimes D)$).
The expression (<ref>) reduces the computation of the target quantity $f_{A'}(L_{G} \cap \Sigma^{L})$ to the computation of the vector $\beta_{G,A'}^{(L)}$. A recursive formula to obtain this vector is given in the following theorem

Let $G = <[n], \pi, \mathcal{M}, \{\beta_{\sigma}\}_{\sigma \in \Sigma}>$ be a UCFG and  $A' = <[n'], \pi', \{A'_{\sigma}\}_{\sigma \in \Sigma}>$ be an HMM. We have

$\bullet ~~\beta_{G,A'}^{(1)} = \sum\limits_{\sigma \in \Sigma} \beta_{\sigma} \otimes vec(A'_{\sigma})$

$\bullet$ For $L > 0$:
$~\beta_{G,A'}^{(L)} = (\mathcal{M} \otimes \mathcal{T})_{1} \cdot P \cdot \sum\limits_{i=1}^{L-1}  (\beta_{G,A'}^{(i)} \otimes \beta_{G,A'}^{(L-i)})$

where $P \in \mathbb{R}^{n'^{4}.n^{2} \times n'^{4}.n^{2}}$ is a permutation matrix that induces the linear map

$$\forall (i,j,k,l) \in [n]\times[n'^{2}]\times [n]\times [n'^{2}]:~~P \cdot (e_{i}^{(n)} \otimes e_{j}^{(n'^{2})} \otimes e_{k}^{(n)} \otimes e_{l}^{(n'^{2}}) = e_{i}^{(n)} \otimes e_{k}^{(n)} \otimes e_{j}^{(n'^{2})} \otimes e_{l}^{(n'^{2})}$$

The first point of the theorem is straightforward from the definition of $\beta_{G,A'}^{(L)}$. Let's prove the second point, we have:

\begin{align*}
\beta_{G,A'}^{(L)} &= \sum\limits_{w \in \Sigma^{L}} \beta_{G}(w) \otimes vec(A'_{w}) \\
&= \sum\limits_{w \in \Sigma^{L}} [\sum_{\substack{w_{1},w_{2} \in \Sigma^{+} \\ w_{1}.w_{2} = w}} \mathcal{M}_{1} \cdot (\beta_{G}(w_{1}) \otimes \beta_{G}(w_{2})] \otimes vec(A'_{w}) \\
&= \sum\limits_{w \in \Sigma^{L}} \sum_{\substack{w_{1},w_{2} \in \Sigma^{+} \\ w_{1}.w_{2} = w}} (\mathcal{M}_{1} \cdot ( \beta_{G}(w_{1}) \otimes \beta_{G}(w_{2})) \otimes (\mathcal{T}_{1} \cdot  vec(A'_{w_{1}}) \otimes vec(A'_{w_{2}})) \\
&= \sum\limits_{i=1}^{L-1} \sum\limits_{w_{1} \in \Sigma^{i}} \sum\limits_{w_{2} \in \Sigma^{L-i}} (\mathcal{M}_{1} \otimes \mathcal{T}_{1}) \cdot (\beta_{G}(w_{1}) \otimes \beta_{G}(w_{2}) \otimes vec(A'_{w_{1}}) \otimes vec(A'_{w_{2}})) \\
&= \sum\limits_{i=1}^{L-1} \sum\limits_{w_{1} \in \Sigma^{i}} \sum\limits_{w_{2} \in \Sigma^{L-i}} (\mathcal{M} \otimes \mathcal{T})_{1} \cdot P \cdot (\beta_{G}(w_{1}) \otimes vec(A'_{w_{1}}) \otimes \beta_{G}(w_{2}) \otimes vec(A'_{w_{2}})) \\
&= (\mathcal{M} \otimes \mathcal{T})_{1} \cdot P \cdot \sum\limits_{i=1}^{L-1} \sum\limits_{w_{1} \in \Sigma^{i}} \sum\limits_{w_{2} \in \Sigma^{L-i}}  (\beta_{G}(w_{1}) \otimes vec(A'_{w_{1}}) \otimes \beta_{G}(w_{2}) \otimes vec(A'_{w_{2}})) \\
&= (\mathcal{M} \otimes \mathcal{T})_{1} \cdot P \cdot \sum\limits_{i=1}^{L-1} \beta_{G,A'}^{(i)} \otimes \beta_{G,A'}^{(L-i)}
\end{align*}

where the second equality is due to (<ref>), the third equality is due to lemma <ref> and the associativity property of the kronecker product, and the fourth equality is due to the mixed-product property of the kronecker product.

Due to space constraints, we omit the presentation of the detailed pseudo-code for the $UCFG$-Likelihood problem. Basically, the idea will follow the dynamic programming paradigm by constructing iteratively the forward vectors $\{\beta_{G,A'}^{(l)}\}_{l \in [L]}$from $1$ to $L$ according to the recursive formula in theorem <ref>. A suitable datastructure $H$ (e.g. an array of size $L.n.n'^{2}$) is used to store the intermediate forward vectors.

$\bullet$ Complexity: The base case will require $O(|G|\cdot n'^{2} \cdot |\Sigma|)$ operations of addition and multiplication to compute. The most expensive operation in the algorithm is due to the computation of the expression of the form $(\mathcal{M} \otimes \mathcal{T})_{1} \cdot P \cdot (\beta_{G,A'}^{(i)} \otimes \beta_{G,A'}^{(l-i)})$ $l-1$ times to form $\beta_{G,A'}^{(l)}$. A naive way of implementing this operation would be too costly. However, one observes that tensors/matrices involved in this expression enjoy a binary sparse structure that can be leveraged to drastically speed up the computation: $P$ is a permutation matrix which doesn't need to be explicitly constructed, and can be replaced algorithmically by a procedure that maps each dimension to its image. The tensor $\mathcal{T}$ doesn't have to be constructed neither, as its structure as given in theorem <ref> suggests its implementation with 3 nested iterators. The tensor $\mathcal{M}$ is a binary tensor whose number of non-zero elements is smaller than $|G|$. By exploiting these structures, the complexity of computing an expression of the form $(\mathcal{M} \otimes \mathcal{T})_{1} \cdot P \cdot (\beta_{G,A'}^{(i)} \otimes \beta_{G,A'}^{(l-i)})$ would require $O(|G| \cdot n'^{3})$ operations of addition and multiplication. This operation will be performed $l$ times at each iteration $l \in [L]$. Therefore, the overall complexity is $O(|G| \cdot n'^{2} \cdot \max(n'.L^{2}, |\Sigma|))$. The space complexity cost is due to the storage of intermediary results in the datastructure $H$, and it takes $O(n'^{2} \cdot n \cdot L)$.

$\bullet$ Note.
The closely related problem of sampling UCFGs from HMMs aims at drawing strings $w \in \Sigma^{L}$ according to the probability distribution $f_{G,A'}^{(L)}(w) = \frac{f_{A'}(w)}{f_{A' }(L_{G} \cap \Sigma^{L})} \cdot \delta_{L_{G}}(w)$, when $f_{A'}(L_{G} \cap \Sigma^{L}) \neq 0$. As pointed out by [Jelinek and Lafferty, 1991], the next token probability distribution can be reduced to the computation of prefix probabilities. Same algebric techniques applied in this section can be used to derive a polynomial-time dynamic algorithm to compute prefix probabilities, hence an efficient exact sampler for $f_{G,A'}^{(L)}$. Due to space constraints, we will omit the description of details of the construction of such sampler. We shall assume in the sequel the existence of a polynomial-time running procedure that takes as input a UCFG $G$, an HMM $A'$, and an integer $L$ and draws a sample according to $f_{G,A'}^{(L)}$, and we'll call it $UCFG$-Sample().

§ THE LIKELIHOOD PROBLEM OF AMBIGUOUS CFGS IN HMMS

§.§ The Hardness of the CFG-Likelihood problem for ambiguity degree less than 2

In the previous section, the unambiguity property of UCFGs played a crucial role to derive an efficient procedure for the $UCFG$-Likelihood problem. Implementing naively the UCFG-Likelihood algorithm presented in the previous section for arbitrary CFGs will lead to overcounting. On the other hand, it's a well-known fact that for arbitrary CFGs, the likelihood problem is NP-Hard ([Kannan et al., 1995]).
A POLYCFG $G = <[n], \pi, \mathcal{M}, \{\beta_{\sigma}\}_{\sigma \in \Sigma})$ with degree of ambiguity $\Theta(n^{k})$ for a given $k > 0$, an HMM $A' = <[n'], \pi', \{A'_{\sigma}\}_{\sigma \in \Sigma}>$, an integer $L$, $\epsilon \in (0,1)$
Approximate of $f_{A'}(L_{G} \cap \Sigma^{L})$
$\tilde{Z} \leftarrow \text{UCFG-Likelihood}(G,M,L)$

$\tilde{Z} = 0$

$N \leftarrow O((\frac{L^{k}}{\epsilon})^{2})$

$\tilde{p}_{N} \leftarrow 0 $

$i$ from $1$ to $O(N)$
$w \leftarrow UCFG-Sample(G,A', L)$

Compute $f_{G}(w)$ using the recursive formula (<ref>)

$X \sim \text{Bernoulli}(\frac{1}{f_{G}(w)})$

$X = 1$
$\tilde{p}_{N} \leftarrow \tilde{p}_{N} + 1$

This suggests that the ambiguity degree of CFGs is intrinsically related to the complexity of the problem. This raises a legitimate question on the complexity class to which belongs the likelihood problem for different subclasses of CFGs according to their ambiguity degree hierarchy. Unfortunately, even with the promise that the ambiguity degree of the CFG is less or equal to 2, the likelihood problem becomes computationnaly hard:

Let $G$ be a CFG with an ambigutiy degree less or equal to 2, let $A'$ be an HMM of size $n'$, and $L$ be an integer, there exists no algorithm that runs in polynomial time with respect to the size of $G$, $n'$ and $L'$ and outputs $f_{A'}(L_{G} \cap \Sigma^{L})$ unless $P=NP$.

The proof of this theorem can be found in appendix B. It's based on a reduction from the bounded non-emptiness intesection problem between UCFGs, which in turn is reduced to a variant of the bounded Post-Correspondence problem.

§.§ The POLYCFG-Likelihood problem is FPRAS

In this section, we shall give a randomized procedure to approximate the likelihood for the class of POLYCFGs in HMMs with strong probabilistic guarantees. An optimization/counting problem $P$ is said to admit a fully polynomial randomized approximation scheme (FPRAS) if there exists a procedure that takes as input an instance $I$ of the problem, an error parameter $\epsilon \in (0,1)$, runs in time polynmial in the size of the instance and $\frac{1}{\epsilon}$ and outputs a value $OUT$ that satisfies: $ (1 - \epsilon).OPT \leq OUT \leq (1 + \epsilon).OPT$
with probability greater than $\frac{3}{4}$. $OPT$ refers to the exact output for the instance $I$.
Algorithm 1 illustrates a randomized algorithm that provides FPRAS guarantees (Theorem <ref>) for the $POLYCFG$-Likelihood problem. The algorithm uses the $UCFG$ sampler as a proposal distribution in the framework of a accept/reject scheme by introducing a bernoulli random variable, denoted $X$ in the pseudo-code.
The following theorem <ref> proves the FPRAS guarantees of algorithm 1. The proof can be found in Appendix C.

Let $G$ be a POLYCFG with degree of ambiguity $\Theta(n^{k})$ for a constant $k > 0$, and an HMM $A'$. We have

* $\mathbb{P}(X = 1 ) \geq \Omega(\frac{1}{L^{k}})$,

* For any $\epsilon \in (0,1)$, with probability greater than $\frac{3}{4}$, algorithm 2 outputs a quantity $\tilde{Z}$ that satisfies  $(1 - \epsilon).f_{A'}(L_{G} \cap \Sigma^{L}) \leq \tilde{Z} \leq (1 + \epsilon).f_{A'}(L_{G} \cap \Sigma^{L}) $,
when the precision parameter given in the input is equal to $\epsilon$

§ CONCLUSION

We analyzed in this article the problem of computing the likelihood of languages generated by CFGs in HMMs. We showed that the computational complexity of this problem is closely related to the ambiguity of the CFGs. First, we proposed an efficient dynamic algorithm for the likelihood  problem for the case of UCFGs. Then, we showed that the likelihood problem is NP-hard even for the subclass of CFGs with an ambiguity degree smaller or equal to 2. We gave afterwards a randomized algorithm for approximating the likelihood of polynomially ambiguous CFGs with FPRAS guarantees. It's left as an open question if there exists a FPRAS algorithm for the class of exponentially ambiguous CFGs. Another interesting line of research would be to analyze variants of the problem for other classes of sequential probabilistic models such as stochastic context-free grammars and neural-based sequential models such as RNNs and transformers. $\Omega$

[Asveld and Nijholt, 2000]
Peter R.J. Asveld and Anton Nijholt.
The inclusion problem for some subclasses of context-free languages.
Theoretical Computer Science, 2300 (1):0
247–256, 2000.
ISSN 0304-3975.

[Cognetta et al., 2018]
Marco Cognetta, Yo-Sub Han, and Soon Chan Kwon.
Incremental computation of infix probabilities for probabilistic
finite automata.
In Proceedings of the 2018 Conference on Empirical Methods in
Natural Language Processing, pages 2732–2741, Brussels, Belgium,
October-November 2018. Association for Computational Linguistics.
URL <https://aclanthology.org/D18-1293>.

[Cognetta et al., 2019]
Marco Cognetta, Yo-Sub Han, and Soon Chan Kwon.
Online infix probability computation for probabilistic finite
In Proceedings of the 57th Annual Meeting of the Association
for Computational Linguistics, pages 5332–5337, Florence, Italy, July 2019.
Association for Computational Linguistics.
URL <https://aclanthology.org/P19-1528>.

[Corazza et al., 1991]
A. Corazza, R. De Mori, R. Gretter, and G. Satta.
Computation of probabilities for an island-driven parser.
IEEE Transactions on Pattern Analysis and Machine
Intelligence, 130 (9):0 936–950, 1991.

[Crestin, 1972]
J. P. Crestin.
Un langage non ambigu dont le carré est d'ambiguité non
In ICALP, 1972.

[Fred, 2000]
Ana L. N. Fred.
Computation of substring probabilities in stochastic grammars.
In Arlindo L. Oliveira, editor, Grammatical Inference:
Algorithms and Applications, pages 103–114, Berlin, Heidelberg, 2000.
Springer Berlin Heidelberg.

[Jelinek and Lafferty, 1991]
Frederick Jelinek and John D. Lafferty.
Computation of the probability of initial substring generation by
stochastic context-free grammars.
Computational Linguistics, 170 (3):0 315–353,
URL <https://aclanthology.org/J91-3004>.

[Kannan et al., 1995]
Sampath Kannan, Z. Sweedyk, and Steve Mahaney.
Counting and random generation of strings in regular languages.
In Proceedings of the Sixth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA '95, page 551–557, USA, 1995. Society for
Industrial and Applied Mathematics.
ISBN 0898713498.

[Koller and Friedman, 2009]
Daphne Koller and Nir Friedman.
Probabilistic Graphical Models: Principles and Techniques -
Adaptive Computation and Machine Learning.
The MIT Press, 2009.
ISBN 0262013193.

[Shamir, 1971]
Eliahu Shamir.
Some inherently ambiguous context-free languages.
Information and Control, 180 (4):0 355–363,
ISSN 0019-9958.

[Sheng et al., 2019]
Emily Sheng, Kai-Wei Chang, Premkumar Natarajan, and Nanyun Peng.
The woman worked as a babysitter: On biases in language generation.
In Proceedings of the 2019 Conference on Empirical Methods in
Natural Language Processing and the 9th International Joint Conference on
Natural Language Processing (EMNLP-IJCNLP), pages 3407–3412, Hong Kong,
China, November 2019. Association for Computational Linguistics.
URL <https://aclanthology.org/D19-1339>.

[Sipser, 2013]
Michael Sipser.
Introduction to the Theory of Computation.
Course Technology, Boston, MA, third edition, 2013.
ISBN 113318779X.

[Wich, 2001]
Klaus Wich.
Characterization of context-free languages with polynomially bounded
In Proceedings of the 26th International Symposium on
Mathematical Foundations of Computer Science, MFCS '01, page 703–714,
Berlin, Heidelberg, 2001. Springer-Verlag.
ISBN 3540424962.

[Wich, 2005]
Klaus Wich.
Sublogarithmic ambiguity.
Theoretical Computer Science, 3450 (2):0
473–504, 2005.
ISSN 0304-3975.
Mathematical Foundations of Computer Science 2004.

[Zhang and Ding, 2013]
Huamin Zhang and Feng Ding.
On the kronecker products and their applications.
Journal of Applied Mathematics, 2013, 01 2013.

Proof of theorem <ref>

The mode-k vector product of a tensor $\mathcal{T} \in \mathbb{R}^{n_{1} \times ..\times n_{d}}$ with a vector $v \in \mathbb{R}^{n_{k}}$ is a tensor of order $d-1$, denoted $\mathcal{T} \times_{k} v$, such that

$$ (\mathcal{T} \times_{k} v)[i_{1},..,i_{k-1},i_{k},..,i_{d}] = \sum\limits_{i_{k}=1}^{n_{k}} \mathcal{T}[i_{1},..,i_{d}].v[i_{k}]$$

The mode-k operation is commutative, i.e. for any $(k,k') \in [d]^{2}$ such that $k \neq k'$, we have $\mathcal{T} \times_{k} v \times_{k'} v' = \mathcal{T} \times_{k'} v' \times_{k} v $. For the proof of theorem 1, we will use the following fact: For a tensor $\mathcal{T} \in \mathbb{R}^{n \times n \times n}$ and two vectors $v,~v'$ in $\mathbb{R}^{n}$, we have

\begin{align} \label{modek}
\mathcal{T} \times_{2} v \times_{3} v' = \mathcal{T}_{1}.(v \bigotimes v')
\end{align}

Now, we are ready to prove theorem <ref>. We start by proving the following technical lemma:

Let $A, B$ be two matrices in $\mathbb{R}^{n \times n}$. We have

$$ vec(AB) = \mathcal{T} \times_{2} vec(A) \times_{3} vec(B)$$

where $\mathcal{T} \in \mathbb{R}^{n^{2} \times n^{2} \times n^{2}}$ such that

$$\mathcal{T}(\phi(i_{1},j_{1}),\phi(i_{2},j_{2}),\phi(i_{3},j_{3})) \myeq \begin{cases} 1 & \text{if}~~ i_{1} = i_{2} \land j_{1} = j_{3} \land j_{2}=i_{3} \\ 0 & \text{otherwise}\end{cases}$$

where $\phi:[n] \times [n] \rightarrow [n^{2}]$ is a function such that $\phi(i,j) = (i-1).n + j$

Note that the function $\phi$ maps the position of an element in a matrix $A$ in $\mathbb{R}^{n \times n}$ to its corresponding position in its vectorized form $vec(A)$ (i.e. $A[i,j] = vec(A)[\phi(i,j)]$. We have, for any $(i,j) \in [n] \times [n]$,

\begin{align*}
(\mathcal{T} \times_{2} vec(A) \times_{3} vec(B))[\phi(i,j)] &= \sum\limits_{(i_{2},j_{2},i_{3},j_{3}) \in [n]^{4}} \mathcal{T}[\phi(i,j), \phi(i_{2},j_{2}), \phi(i_{3},j_{3})]. \\
&~~~~~~~~~~~~~~~~~~~~~~vec(A)[\phi(i_{2},j_{2})].vec(B)[\phi(i_{3},j_{3})] \\
&= \sum\limits_{k \in [n]} vec(A)[\phi(i,k)].vec(B)[\phi(k,j)] \\
&= \sum\limits_{k \in [n]} A[i,k].B[k,j] \\
&= (AB)[i,j] = vec(AB)[\phi(i,j)]
\end{align*}

where the second equality is obtained from the definition of $\mathcal{T}$ in the lemma.

Theorem <ref> is a corollary of the previous lemma
(Theorem <ref>.)
By noting that for any vectors $u,v \in \mathbb{R}^{n}$, for any matrix $A \in \mathbb{R}^{n \times n}$,  $u^{T}.A.v = (v \bigotimes u)^{T}.vec(A)$, we  have

\begin{align*}
f_{A'}(w) &= \pi'^{T}.A'_{w}.e_{[n']} \\
&= (e_{[n']} \bigotimes \pi')^{T}.vec(A'_{w}) \\
&= (e_{[n']} \bigotimes \pi')^{T}.vec(A'_{w_{1}}.A'_{w_{2}}) \\
&= (e_{[n']} \bigotimes \pi')^{T}.(\mathcal{T} \times_{2} vec(A'_{w_{1}}) \times_{3} vec(A'_{w_{2}})) \\
&=  (e_{[n']} \bigotimes \pi')^{T}.\mathcal{T}_{1}. ( vec(A'_{w_{1}}) \bigotimes vec(A'_{w_{2}}))
\end{align*}

where the forth equality is obtained from lemma <ref>, and the last equality is due to (<ref>)

§ PROOF OF THEOREM <REF>

We present the $2$-CFG-Likelihood problem given as follows:

$\bullet$ Instance. A CFG $G$ with degree of ambiguity less or equal to 2, A HMM $A'$, $p \in (0,1)$, $L$ an integer

$\bullet$ Problem: Does $f_{A'}(L_{G} \cap \Sigma^{\leq L}) \geq p$

The $2$-CFG-Likelihood problem is NP-Hard.

The proof proceeds by reduction from the bounded non-emptiness intersection problem of UCFGs. This problem is given as follows:

$\bullet$ Instance: Two UCFGs $G_{1},~G_{2}$, an integer $L$

$\bullet$ Problem: Does $L_{G_{1}} \cap L_{G_{2}} \cap \Sigma^{\leq L} = \emptyset$?

We shall show that this problem is NP-Hard. But first, let's show that this problem is reducible in polynomial time to the $2$-CFG-Likelihood problem.

The bounded non-emptiness intersection problem between UCFGs is reducible in polynomial time to the $2$-CFG-Likelihood problem.

Let $G_{1},~G_{2}$ be two UCFGs, and $L$ be an integer. Let $A'$ be the trivial single-state HMM that affects equal mass probability to all strings of a given length (i.e. $f_{A'}(w) = \frac{1}{|\Sigma|^{|w|}}$). We have

\begin{align}  \label{intersection}
f_{A'}((L_{G_{1}} \cup L_{G_{2}}) \cap \Sigma^{\leq L}) = f_{A'}(L_{G_{1}} \cap \Sigma^{\leq L}) + f_{A'}(L_{G_{2}} \cap \Sigma^{\leq L}) - f_{A'}(L_{G_{1}} \cap L_{G_{2}} \cap \Sigma^{\leq L})
\end{align}

Since $G_{1}$ and $G_{2}$ are unambiguous, the two terms $f_{A'}(L_{G_{1}} \cap \Sigma^{\leq L})$ and $ f_{A'}(L_{G_{2}} \cap \Sigma^{\leq L})$ can be calculated exactly in polynomial time by calling $L$ times the algorithm UCFG-Likelihood presented in section 2.. Moreover, we can construct in polynomial time a CFG of degree of ambiguity smaller or equal to 2, denoted $G_{1} \cup G_{2}$, that generates the language $L_{G_{1}} \cup L_{G_{2}}$, by adding a new root symbol and two production rules, whose left side is the new root symbol and its right side is the root symbol correponding to $G_{1}$ and $G_{2}$. A normalization into Chomsky form can be done in polynomial time without changing the degree of ambiguity of the original CFG.  Consequently, by (<ref>), we have $L_{G_{1}} \cap L_{G_{2}} \cap \Sigma^{\leq L} = \emptyset $ if and only if $f_{A'}(L_{G_{1} \cup G_{2}} \cap \Sigma^{\leq L})$ is greater or equal to $f_{A'}(L_{G_{1}} \cap \Sigma^{\leq L}) + f_{A'}(L_{G_{2}} \cap \Sigma^{\leq L})$.

Next, we shall prove that the bounded non-emptiness intersection problem is NP-Hard, which entails immediately the result of theorem <ref> by the reduction given in lemma <ref>.

The bounded non-emptiness problem between UCFGs is NP-Hard.

We'll reduce this problem from a variant of the bounded Post Correspondence problem (BPCP) given as follows: Given a pair of $N$ strings  $\{(u_{i},v_{i})\}_{i \in [N]}$, and integer $M$:  Does there exist a sequence $i_{1},..i_{k}$ of elements in $[N]$ such that  $u_{i_{1}}...u_{i_{k}} = v_{i_{1}}..v_{i_{k}}$ and  $k + |u_{i_{1}}..u_{i_{k}}| \leq M$?

The proof of NP-Hardnss of the BPCP will be given later. For now, assume it's the case. The details of the reduction are similar to the classical proof of the undecidability of the non-emptiness intersection problem of two UCFGs <cit.>. In the following, we will give the important outlines of this construction, and we refer the interested reader to [Asveld and Nijholt, 2000], for more details. Let $\{(u_{i},v_{i})\}_{i \in [N]}$ be a pair of strings. Define the extended alphabet $\Sigma_{e} = \Sigma \cup \{1,2..,N\} \cup \{\#,\&\}$. The idea is to construct (in polynomial time) two UCFGs $G_{1}$ and $G_{2}$, where the $G_{1}$ generates the language $L_{G_{1}} = i_{1}..i_{k}\&j_{l}..j_{1}\#v_{j_{1}}..v_{j_{l}}\& u_{i_{k}}^{R}..u_{i_{1}}^{R}$, and $G_{2}$ generating the language $L_{G_{2}} = w\&w^{R}\#w'\&w'^{R}$, where $.^{R}$ is the mirror operation. The language $L_{G_{1}} \cap L_{G_{2}}$ corresponds exactly to words of the form $i_{1}..i_{k}\&j_{k}..j_{1}\#v_{j_{1}}..v_{j_{l}}\& u_{i_{k}}^{R}..u_{i_{1}}^{R}$ where $\forall l \in [k]: i_{l} = j_{l}$, and $u_{i_{1}}...u_{i_{k}} = v_{i_{1}}..v_{i_{k}}$. The length of such string is equal to $2(k + |u_{i_{1}}..u_{i_{k}}|) + 3$. Consequently, for any $M > 0$, there exists a word in $L_{G_{1}} \cap L_{G_{2}}$ of length smaller than $ 2M + 3$ if and only if there exists a sequence that satisfies the conditions of the BPCP problem.

To complete the proof of <ref>, we need to prove the NP-Hardness of the variant of the bounded post-correspondence problem defined above.

The BPCP is NP-Hard.

We reduce any language in NP to our variant of the Post-Correspondence problem. Let $L$ be any language in NP. Thus, there exists a non-deterministic Turing Machine (NTM) $N_{A}$, and a polynomial $p_{A}$ such that for any string $w$, the machine $N_{A}$ decides if $w \in L$ in a time at most $p_{A}(|w|)$. The construction (in polynomial time with respect to the size of the NTM and the length of the string) of an instance of the PCP problem, denoted $I_{N_{A},w},$ that simulates a turing machine on a string $w$ is classical for the proof of the PCP undecidability result. The PCP instance generates two sequences of computation configurations of a turing machine such that it accepts if and only if there exists a correspondence between the two sequences.  We refer the reader to [Sipser, 2013] for details of the construction. What's left is to find an upper bound of the sum of the list of pair of strings used with the length of such sequence. In what follows, we'll settle for the use big $O$ notation to dervie such upper bound. First, by definition of $p_{A}$, $k \leq O(p_{A}(|w|))$. Second, observe that a configuration of $N_{A}$ (i.e. the content of the turing machine tape) while running on  $w$ as input can't exceed $O(p_{A}(|w|))$. Hence, the length of the sequence of configurations of the NTM $N_{A}$ during a run on $w$ can't exceed $O(p_{A}^{2}(|w|))$. So, $N_{A}$ accepts $w$ if and only if there exists a solution of the PCP problem in $I_{N_{A},w}$ whose sum of the pair of strings used and the length of the string is smaller than $O(p_{A}^{2}(|w|))$.

Now, we are ready to prove theorem <ref>.
(Proof theorem <ref>.) Suppose there exists an algorithm $\mathcal{A}$ that can compute $f_{A'}(L_{G} \cap \Sigma^{L})$ in polynomial time. Then, by calling $\mathcal{A}$ $L$ times, we can compute in polynomial time $f_{A'}(L_{A} \cap \Sigma^{\leq L})$. Hence, we can decide the $2$-CFG-Problem in polynomial time. Since this problem is NP-Hard by theorem <ref>, this is possible only if $P = NP$, which completes the proof.

(Theorem <ref>)
We first write the term $\mathbb{P}(X = 1)$ in a suitable manner,
We have

\begin{align}
\mathbb{P}(X = 1) &= \sum\limits_{w \in \Sigma^{L}} \mathbb{P}(w , X = 1) \nonumber \\
& = \sum\limits_{w \in \Sigma^{L}} \frac{f_{G}(w).f_{A'}(w)}{\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w)}.\frac{1}{f_{G}(w)} \nonumber \\
&= \sum\limits_{w \in \Sigma^{L}} \frac{f_{A'}(w). \delta_{G}(w)}{\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w)} \nonumber \\
&= \frac{f_{A'}(L_{G} \cap \Sigma^{L})}{\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w)} \label{bern}
\end{align}

Now we can prove the statement 1.

(1) Let $G$ be a POLYCFG with degree of ambiguity $\Theta(n^{k})$ for some $k > 0$. We have, then

$$ \forall w \in \Sigma^{L}:~f_{G}(w) \leq \delta_{G}(w).O(L^{k}) $$

Multiplying each term by $f_{A'}(w)$ and summing up, we obtain

\begin{align*}
\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w) &\leq O(L^{k}). \sum\limits_{w \in \Sigma^{L}} \delta_{G}(w).f_{A'}(w) \leq O(L^{k}) f_{A'}(L_{G} \cap \Sigma^{L}) \\
\implies   \mathbb{P}(X = 1) & = \frac{f_{A'}(L_{G} \cap \Sigma^{L})}{\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w)}\geq \Omega(\frac{1}{L^{k}})
\end{align*}

(2) If $f_{A'}(L_{G} \cap \Sigma^{L}) = 0$, then algorithm 2 outputs 0. Indeed, we have $\sum\limits_{w \in \Sigma^{L}} \delta_{L_{G}}(w).f_{A'}(w) = 0$ if and only if $\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w) = 0$. Next, let's focus on the case $f_{A'}(L_{G} \cap \Sigma^{L}) \neq 0$. Let $\tilde{p}_{N}$ denote the empirical estimate of $\mathbb{P}(X = Accept)$ with a sample size equal to $N$. By Hoeffding's inequality, for $N \geq O((\frac{L^{k}}{\epsilon})^{2})$, we have with probability greater than $\frac{3}{4}$

$$ |\mathbb{P}(X = 1) - \tilde{p}_{N} | \leq \frac{\epsilon}{L^{k}} \implies | \frac{\tilde{p}_{N}}{\mathbb{P}(X=1)} - 1 | \leq \frac{\epsilon}{\mathbb{P}(X = 1).L^{k}} \leq \epsilon$$

where the second inequality is due to the first statement of the theorem.

Consequently, replacing $\mathbb{P}(X = 1)$ in the inequality above by its expression in (<ref>), we obtain, with probability greater than $\frac{3}{4}$,

$$ | \frac{\tilde{p}_{N}.\sum\limits_{w \in \Sigma^{L}} f_{G}(w).f_{A'}(w)}{f_{A'}(L_{G} \cap \Sigma^{L})} - 1 | \leq \epsilon$$