Deep Expectation-Maximization in Hidden Markov Models via Simultaneous Perturbation Stochastic Approximation
Authors: Chong Li
Dan Shen
C.J. Richard Shi
Hongxia Yang
Venue:  (2020)
Keywords: recommender system
gradient approximation
Hidden Markov Model

Abstract: We propose a novel method to estimate the parameters of a collection of Hidden Markov Models (HMM), each of which corresponds to a set of known features. The observation sequence of an individual HMM is noisy and/or insufficient, making parameter estimation solely based on its corresponding observation sequence a challenging problem. The key idea is to combine the classical Expectation-Maximization (EM) algorithm with a neural network, while these two are jointly trained in an end-to-end fashion, mapping the HMM features to its parameters and effectively fusing the information across different HMMs. In order to address the numerical difficulty in computing the gradient of the EM iteration, simultaneous perturbation stochastic approximation (SPSA) is employed to approximate the gradient. We also provide a rigorous proof that the approximated gradient due to SPSA converges to the true gradient almost surely. The efficacy of the proposed method is demonstrated on synthetic data as well as a real-world e-Commerce dataset. 

Under review as a conference paper at ICLR 2020
DEEP EXPECTTATION-MAXIIIIATTOOO IN HIDDEN MARKOV MODELS VIA SIMULTANEOUS PERTURBATION STOCHASTIC APPROXIMATION
Anonymous authors Paper under double-blind review
ABSTRACT
We propose a novel method estimate the parameters of collection of Hidden Markov Models (HMM), each of which corresponds to a set of known features. The observation sequence of an individual HMM is noisy and/or insufficient, making parameter estimation solely based on its corresponding observation sequence a challenging problem. The key idea is to combine the classical Expectation- Maximization (EM) algorithm with neural network, while these two are jointly trained in an end-to-end fashion, mapping the HMM features to its parameters and effectively fusing the information across different HMMs. In order address the numerical difficulty in computing the gradient of the EM iteration, simultaneous perturbation stochastic approximation (SPSA) employed to approximate the gradient. We also provide a rigorous proof that the approximated gradient due to SPSA converges to the true gradient almost surely. The efficacy of the proposed method is demonstrated on synthetic data as well as real-world e-Commerce dataset.
INTRODUCTION
Hidden Markov Model (HMM) is powerful statistical framework in sequential data analysis. One advantage HMM lies in its strong model interpretability (Rabiner) 1989). Estimating the parameters of HMM given its observation sequence is well-studied problem. The celebrated Expectation-Maxinn Maximizaaiinnn (EM) algorithm (Dempster et al. 1977) finds a locally optimal estimation in the maximum likelihood sense with provable optimality 1983). Numerous modifications and enhancements to the EM algorithm have been proposed (Jamshidian & Jennrich 1997 Capp, 201 Notably, explicitly modeling the duration of the states in HMM can be enabled by extension
named Hidden Semi-Markov Models (HSMM) (Ostendorf et al. 1996).
This paper concerns estimating the parameters of collection of HMMs, each of which corresponds to a set of known features. The observation sequence of each individual HMM is noisy and/or insufficient, making parameter estimation solely based its corresponding observation sequence using the traditional EM algorithm impractical. The problem arises recommender systems online E-Commerce platforms. The objective is train a HMM (HSMM) model predict the category of product that the user would purchase based on the user's 's feature (demographic, location, income level) and observation sequence (past click history). The observation sequence of particular user is generally noisy (click not reflective of true purchase intention) and insufficient (user only clicked a small number of items), making parameter estimation highly challenging.
The intuition is that while the information regarding each individual user is quite limited, we have access to a much larger amount of information concerning all the users collectively. If we were able to quantify some kind of correlation among the users using their features, we can combine their information for parameter estimation. Formally, we propose to deduce correlations among the HMMs using their features, that we can fuse the information across different HMMs to estimate the parameters. The basic idea is to combine the classical Expectation- Maximization (EM) algorithm with neural network which maps HMM's feature its parameters. The weight of the neural network captures the correlation among the HMMs and is shared across all the users. The EM iteration, with the estimated HMM parameter step & (denoted by Ax) input and the refined
Expectation-MMxxiiizztoooo

---

Under review as a conference paper at ICLR 2020
parameter Ak+1 output, can be considered as building block (or layer) in the resulted neural network. In order to enable end-to-end training, it is necessary to compute the gradient of the EM iteration 0 1 /0Az. While this gradient exists, we will show in Section 3 that exactly computing this gradient is computationally expensive. A key technical contribution of this paper is in proving the gradient of the EM iteration can be reliably approximated via simultaneous perturbation stochastic
approximation (SPSA) (Spall 1992, Sadegh & Spall 1998; Spall, 1998; Sadegh 1997), which only involves function evaluation and can be easily computed. With such gradient approximation technique, we expect large body of functions whose gradient is difficult to compute can now be incorporated as layers in deep neural networks, dramatically expanding the choice of network layers and increasing the flexibility of network architecture design. We name our method DENNL (Differentiable EM as Neural Network Layer).
It is worth noting that a user's feature consists of number of categorical and numerical fields. Instead of hand-crafting dedicated neural network to encode the user feature, we used a pre-trained low-dimensional user embedding to represent such information. The user embedding was trained on a link prediction task using the graph convolutional network (GraphSage) (Hamilton et al. 2017 Cheng et al., 2016). Much similar to the success of pre-trained word embedding in downstream natural language processing tasks (Peters et al. 2018: Devlin et al.) (0188), we demonstrate that the embedding trained using GraphSage is effective in summarizing information with complex structures and can be highly instructive in seemingly unrelated downstream tasks.
2 BACKGROUNDS
Hidden Markov Model and EM Algorithm. In this section, we only introduce the concepts and notations related to HMM and EM algorithm that are necessary for further discussion, and refer the readers to (Rabiner 1989) and (Bilmes et al. 1998) for a more comprehensive treatment of the topics.
A HMM is defined by a set of hidden states, the transition probability of the hidden states, and the emission distribution. The Markov property mandates that the state transition and the emission distribution is only dependent on the current hidden state. The realizations of the emission distribution are what we can observe as an observation sequence. Let the distribution of the initial hidden state be and Qt. {t 1, ... T be the hidden state at time step t. Then transition probability is defined by time-homogeneous transition matrix A with elements 0s.j = P(Q, = j|Q,-1 = i). where i,j (1..... ) are the indices of the hidden states. Let O₂ be observable time step and o, to be a realization of O.. The emission distribution defines the probability of a particular observation conditioned on the current hidden state
bo(o.) P(O, = o. j)-
The emission probability of all hidden states can be represented by B (.).
Now we follow the notation in (Bilmes et al. 1998) to present a brief introduction of EM algorithms applied in HMMs. A key concept is the forward and backward probability, which is used compute the likelihood efficiently. Forward probability is the probability of seeing the partial sequence 01, Ot and ending up in hidden state at time f, Define the forward probability as:
(I) = p(0 = . , Or = oc; Q: = i[A), where parameters = (A, B, x) = {Ai,... } and M is the number of parameters. The forward probability can be computed efficiently in an iterative manner,
N
(1) m,b((1)), a)(t+1)= Σ aa(t)ass bo(0)+1)
(2)
Similarly, Backward probability is the probability of the ending partial sequence 0141, .T given the hidden state i at time and is defined as:
(t) = p(O = 0111 Or or = i, 2).
(3)
Similarly backward probability can also be computed iteratively:
B((T)= 1, B,(1) Σ
(o, 1).
(4)
1=1
2

---

Under review as a conference paper at ICLR 2020
Given the observation sequence 01, P....... or and the parameter estimation at the k-th iteration (4) the parameter estimation at the k + 1-th iteration can be computed as follows:
a; (1)),,(11
#
(k+1)
(5)
(1)
11+11
04
(6)
Et= a:(1))((1)
== (t(t))(()))a..
(h)
Et=1 (1)
where on is an indicator function which equals to 0; - vn and otherwise.
Hidden Semi-Markov Model. HSMM (Ostendorf et al. 1996) explicitly models the duration of
state, by introducing a duration distribution, with which multiple observations could be emitted from a hidden state before state transition occurs. A HSMM can be parameterized as HMM by introducing a counter of the time steps in the current state (Yildirim et al. 20133] Bietti et al. 2015). For this reason, the computation methods as well as the analysis of HMM naturally apply to HSMM.
3 PROBLEM STATEMENT AND PROPOSED SOLUTION
In this section we formally state the problem and describe our proposed method. The objective is to estimate the parameters {>(u)) } of collection of HMM models, using the corresponding observation sequence (ot,1:I,..)) and feature embedding {e(w) } as input. Here (u) is the index of HMM in the collection of HMMs, and T(w) is the length of the observation sequence. The observation sequence (0), is noisy or insufficient for the conventional EM algorithm to apply. The feature embedding ((u) is a fow-dimensional vector that encodes our prior knowledge of {Awu) We propose to use neural network to combine the information across all the HMMs for more effective parameter estimation.
(8) where & the parameter of the neural network that is shared by the HMM models. Formally, the loss function to be minimized is
Aa) V (e(u), Or,1:T +)
C ④
= Σ L (A(a))) Yu
where L(-) the log- likelihoooood of observing sequence or,1:T(,) given HMM parameter A(u)-
The overview of our proposed method is shown in Figure Our architecture can be considered as an unrolled Recurrent Neural Network (RNN), where each recurrence (or stage) of the RNN corresponds to an EM iteration. Our key novelty is in rendering EM iteration as network layer. The resulted "EM layer" serves as the output function of the RNN. This is contrast to the traditional RNN where output function is fully connected layer with non-linearity. Note that the EM layer is parameter-less and directly reflects the domain knowledge and design intent of network designer. As we will show in Section 6) such recurrent structure that mimics the iterative EM iterations in conventional setting is critical to the success of our proposed method.
As in the conventional EM algorithm, initial parameter is provided and is iteratively refined. After the keth EM iteration is performed, a multilayer perceptron (MLP) which is labeled as DNN in the figure transforms (k), the latent state from the previous iteration hg, and the user embedding to an updated (k+1) and an updated latent state hg+1- The parameters of the MLP are shared across EM iterations. It is worth emphasizing that the latent state h captures the state of the DNN and shall not be confused with the hidden state of the HMMs. We use the So Softplus function and L normalization to ensure the elements of the resulted À are in proper range.
Differentiability of the EM iteration. The EM iterations shown in Figure I can be considered as layers of neural network, with (R) and the observation sequence as input and (k+11 as output. To enable end-to-end training, is necessary to compute the partial gradient ( (k) Even though the EM iteration for HMM can be explicitly stated (Equation 5)). directly computing the partial gradient a (5+1) 1 (1) using a automatic differentiation engine faces two numerical challenges, both of which are related to the forward and backward probability (Equation 2 4).
3

---

Under review as a conference paper at ICLR 2020
Diservation
Embedding
User Embeddlnn
User Embedding
Oiserrvatios
X
2
-X.0
EM
Iteratioon on
DNN
DNN
Likelthood
h
1,
Stochastic Perturbation
0k+k1
4 (1)
2r. 4
X
EM
x
8 200
[k.
2.
AM
2
26
20
Figure 1: Overview DENNL. The EM iteration are incorporated a deep neural network as layers. End-to-end training is enabled by approximating the gradient of the "EM layer" using SPSA, as shown in the low half the figure.
While evaluating the alpha-beta equation is O(T') operation where T is the length of the observation sequence, the number of nodes required build the forward and backward probability in the computation graph of an automatic differentiation engine is on the order (TT2). Empirically we found this leads to intractable computation cost.
The length of the observation sequence T varies across different HMM models, thus separate computation graph for the forward and backward probability has to be rebuilt for every distinct T value. This is particularly problematic when the HMMs mini-batch comes with different 1" values.
To address the aforementioned numerical challenges, we propose to approximate the gradient 0x (k++)) (0x(k) using SPSA. Much similar to how we can approximate the gradient of a one- dimensional function using the finite difference method, SPSA estimates the gradient of function by evaluating the function with stochastically perturbed input vectors. A series of work by Spall and colleagues (Spail 1992 Sadegh Spall 1998 Spall 1998 Sadegh 1997) established theoretically rigorous error bound for certain scalar functions. Note that such gradient approximation only involves evaluating the EM iteration and can be efficiently computed.
important question to answer is how well can SPSA approximate the gradient ((++))/aX( in our specific application. In the next section, we formally describe how SPSA is performed and establish its convergence property for EM iterations.
SPSA AND CONVERGENCE ANALYSIS
As the name suggests, Simultancous Perturbation Stochastic Approximation approximates the gradient (Jacobian) of function by simultaneously applying small perturbation to all the dimensions of the argument of the function. Let A RM be M -d-mmnnsional random vector, where elements A A AM M are independent with zero mean. We do not assume specific distribution of A long as E(I/A) ) is bounded. We treat the EM iteration stated equation equation and equation 7 as a function, with the HMM parameter the k-th iteration (k) being the function argument and refindd parameter at (I + 1)-th iteration X (k+1) the output:
X (k+1) f(o,
(10)
where f: RM_ RM and for,... ... is the observation sequence.
The SPSA estimates the gradient (Jacobian) of a function through two function evaluations. The arguments of the two function evaluation positively and negatively perturbed respectively as
4

---

Under review as a conference paper at ICLR 2020
following:
A(x+)) f (110)) + c, (R.t)) A f {((()) - a c(l)-)
(11)
(12)
where C₁: is a positive scalar and (lRitt, e(ki-) are measurement noise. Let Fx be the random field generated by ( ... (kk), We assume the measure noise satisfy the following conditions:
E - e(t Fr: =0,
(13)
where 0 the M M-dimensional zero column vector.
With ( and (kt-),, the approximation of the true gradient (Jacobian) ((k) due to SPSA is defined
as
( (R. -x
2ny, A11
2r A (4) M
j(k)
(14)
AM -1
(k++) (k-))
2
2c,, (c)
where A! (1++)
(R)-) A (R) are the i-th element of X (R,+) (k: (k), respectively.
We now quantify the approximation error of ((k and establish the convergence property of the gradient approximation due to SPSA for the EM iteration. Our primary theoretical contribution Lemma [ and Theorem [ which theoretical results but their results only apply to functions with scalar output. Our proof took a very different approach from the proof in (Spall 1992) to bound the Frobenius Norm of the approximated Jacobian to account for the fact that EM iteration a function with vector input and vector output (f RM RM, Please see Appendix A for the detailed proof.
stated below. Note that (Spall) 1992) offered similar
Lemma 1. For i-th function fi of f in equation 10
f
exist and are uniformly bounded M.
Tx BA OAts
on the ranges of parameter À such that for i, j1, J2.
f.
(o, 10 To.
(15)
0A,, 02, aA
where the observation sequence and To is positive scalar. Theorem 1. Suppose that for each k, A
M are independent to each other and have zero
mean such that E(A, (k)) = 0, 1,2, M. In addition, as k co, almost surely (15) S Tı
and E| AT S 72, 1.... M, where Ti and Ta are positive constants. Then for k oc, almost
surely
| (J10) - J(M)
O(c))
(16)
where [|-[|æ is Frobenius norm.
Sketch of Proof: The difference between the j-th element of the approximated Jacobian j(k) and the true Jacobian J (k) is denoted by ( J(() We compute the third order Taylor series expansion (Taylor & Lay 1958) of this difference, and establish that the first order terms vanish. The constant term is obviously zero. The first order term disappears because the elements of A are independent with zero mean. The second order term is also zero because the positive perturbation and the negative perturbation cancel out. According to Lemma ] the third order term uniformly bounded, which guarantees the convergence rate of SPSA for estimating the gradient of the EM iteration.
5 RELATED WORK
shown in WWn et al. 2017) that even a crude approximation the gradient sufficient for stochastic gradient descent to converge. Such theoretical result is among motivations explore
5

---

Under review as a conference paper at ICLR 2020
gradient approximation techniques for layers whose gradient is expensive compute. There are number of works on enhancing classical sequential data analysis methods with deep neural networks. Krishnan (Krishnan et al. (017) employs RNN to parameterize variational approximation of the posterior distribution in a Gaussian state space model. Other works along this line include (Bui et al.
2016), (Salinas et al. 2017) and (Linderman al. 2017).
Perhaps the most related existing work is [Rangauuram et al. 2018). where the authors used a deep neural network to parameterize a collection of linear state space models so the information across multiple time series can be shared. The underlying linear state space model is updated via Kalman Filtering. which only involves matrix-to toxxx-tttmatrii multiplication and is differentiable. The price to pay for such differentiability is the underlying sequential data analysis method has to be relative simple form (e.g. linear state space model) with limited expressiveness and flexibility. In contrast, this work we do not have to limit ourselves to methods whose gradient are easy to compute.
Another closely related work is Gref et al. (Greff et al. 2017), where the author incorporates the so-called general EM algorithm (Wu 1983) in the neural network for unsupervised clustering. The key difference that instead of performing a complete EM update, the general EM algorithm (Greff et al. 2017) only takes one step of gradient descent in the M step of the EM algorithm to refine the parameter estimation. It may take a much larger number of iterations for the general EM algorithm to converge (Wul 1983). Larger number of iterations leads to deeper neural network, an additional layer is stacked in the neural network per iteration. A network that is too deep may cause difficulty in training (He et al. 2016)) Hinton al. (Hinton al., 2018) directly computes the gradient of EM based routing procedure. With small number of EM iterations, (Hinton et al. (018)) does not face the numerical challenge outlined in Section 3 because the sizes of their inputs in mini-batch are fixed and the problem is of much smaller scale.
Relationship with other recommender systems algorithms. Graph embedding (Hamilton et al. 2017 Grbovic & Cheng 2018)) is one of the backbone algorithms for today's 's industrial recommender systems. While graph embedding is highly effective in capturing complex interactions among hun- dreds of millions of users and items, most of the algorithms fail to consider the temporal evolvement of the user's interest (with a few exceptions such as (Kumar et al.) 2019). (Trivedi al. (201)) and (Zhou et al. 2018), none of which provides interpretable model of user interest evolvement). We do not consider our proposed method as general solution for item level recommendation, as is unlikely that proposed method in its current form can be scaled to millions of items. Rather, the focus our proposed method is to capture highly detailed temporal interest evolvement of the users across a limited number of categories.
6 EXPERIMENT
In this section, we evaluate the effectiveness of our proposed method on synthetic data as well as real-world e-Commerce data.
The primary contribution of our proposed method is to share the information across multiple HMMs for parameter estimation in cases where the observation sequence is noisy or insufficient. To the best of our knowledge, there is no directly comparable method in the existing literature. We perform ablation studies against the following baselines to justify our design choices:
1. Conventional EMM The HSMM parameters are estimated by the conventional EM algorithm, with no information sharing across the HSMM models.
2. EM Mapping. We first estimate the HSMM parameters using the conventional EM algo- rithm, then train neural network (a stack of fully connected layers) that maps the user embedding to the HSMM parameters due to conventional EM algorithm. The training objective is minimize the square error. Though the neural network establishes some correlation across the HSMM models, the HSMM parameters due to the conventional EM algorithm solely relies on the user's corresponding observation sequence that is noisy and/or insufficient.
3. MLP Mapping. In this baseline, a multilayer perceptron (MLP) maps the user embedding to the HMM parameters, then the likelihood is computed based on the HMM parameters and the observation sequence. We use gradient ascent to maximize the likelihood. Note that this baseline is purely based gradient ascent and does not involve the EM algorithm.

---

Under review as a conference paper at ICLR 2020
4. Initial Fusion. A DNN maps user embedding to HMM parameters, which are refined by the EM iterations. Here we only fuse the observations across different HMMs at the initial stage. In sense, this architecture identifies optimal initial parameter guess. In contrast, our proposed method fuses observations across different HMMs at every HM iteration.
Observation
Observation
User Embedding
User Embedding
EM
EM Iteration
DNN
DNN
Iteration
Likelihood Function
Likelihood Function
User Embedding
User Embedding
EM Iteration
Iteration
Figure 2: Overview of baselines. Left: MLP Mapping. Right: Initial Fusion.
6.1 SYNTHETIC DATA
The purpose evaluating the proposed method on synthetic data is to compare the decoded hidden state with known ground truth state. Being able to correctly infer the hidden state is key metric of HMM models (Sarkar Dunson 2018). We pre-designed the parameters of a collection HSMM, each of which has T0 hidden states. The emission distribution is 5-dimension Gaussian distribution. The duration distribution Poisson distribution. To generate an informative feature embedding for vector and apply non-linear transformation
each HSMM, we serialize the HSMM parameters (in the form of Az + b followed by ReLU, where æ is the parameter vector, A is a known full rank matrix and b is known vector). The resulted feature embedding is strongly related to its underlying parameter, but one cannot recover the HMM parameters from its feature embedding. The evaluation metric the percentage of the decoded states (Viterbi 1967 Munkres truth state, or the labeling accuracy.
[957) that match the ground
We first evaluate our method cases where the observation sequence is insufficient. We also compared DENNL to baseline methods when a certain percentage of the observations in the observation sequence generated by the ground truth model is contaminated by noise. a particular observation chosen to be noisy, its value is replaced by the value of another randomly chosen observation in the sequence. The results are reported in Table
Table 1: Labeling accuracy comparison of DENNL to the baseline methods on the synthetic data.
Sequence Length:
Sequence Length:
Sequence Length:
Noisy Sample:
Noisy Sample:
Method
50
100
400
20%
10%
Conventional EM
82.0%
85.5%
94.1%
83.1%
91.5%
Direct Mapping
71.4%
72.2%
73.0%
67.9%
71.4%
MLP Mapper
51.5%
50.3%
52.1%
46.2%
48.5%
Initial Fusion
82.4%
83.7%
92.6%
82.8%
89.7%
DENNL
88.3%
90.0%
93.5%
88.1%
92.3 %
Discussion: As shown Table 1 DENNL consistently outperforms the baseline methods with noisy or insufficient observations. When the observation sequence is of sufficient length or noise-less, the benefit of the proposed method diminishes as expected. Even though Direct Mapping method enables some information sharing across HMMs, its performance was poor because the regression target due to the conventional EM and can be inaccurate to begin with. This experiment illustrates the necessity to fuse information across HMM in every EM iteration. While the Initial Fusion method seems to enable information sharing, its performance is very close to that of conventional EM. This method essentially attempts to identify optimal initial solution with shared information across HMMs. However, at least in our application, the EM algorithm appears to be insensitive to the initial solution. The MLP Mapper method enables information sharing with simple architecture, but is
7

---

Under review as a conference paper at ICLR 2020
slow converge and is not competitive against conventional EM. To explain this, note that in a conventional setting, we seldom use gradient ascent for HMM parameter estimation. Rather, the common practice is to use the EM algorithm which is carefully designed for the particular application.
This is the key message that we would like to convey to the community; operations that are inspired by well-studied classical methods (such as EM iteration) be significantly more effective than operations that are synthesized using generic layers (convolution, fully connected, etc). If the gradient of the classical method is incomputable, it could potentially be numerically approximated. This formulation dramatically expands the choices of network layers and allows network designers to directly apply their domain knowledge in the network architecture.
6.2 E-COMMERCE DATA
As previously discussed in Section DENNL is not considered as a general solution for recommen- dation systems in its current form. Rather, it is suitable to model the shift of user's interest across a small number of categories. We apply DENNL in clearly defined and fast-growing sector on our e-Commerce platform, namely Home Decoration. The Home Decoration sector comes with certain well-defined shopping patterns that follow the progress of the decoration of a newly purchased condo. Formally, we model the behavior of the user in the Home Decoration category by HSMM with 17 states, each of which corresponds to sub-category in the Home Decoration sector. Please see Appendix A.. for more information of the e-Commerce dataset.
In this setting we no longer have access to the ground truth states, thus we can no longer use labeling accuracy as the metric. Instead, we use link prediction metric. Using the trained HSMM model, we could compute the likelihood of user interacting with each of the 17 sub-categories. The prediction considered to be successful if the user interacted with the predicted sub-category with the highest likelihood, top-3 and top-5 likelihood.
Table 2: Sub-cateogry prediction accuracy in the e-Commerce dataset.
Method
Top-1
Top-3
Top-5
Conventional EM
10.3%
23.9%
50.5%
GraphSage (Hamilton et al. 2017
17.7%
37.4%
65.5%
MLP Mapper
7.4%
19.6%
35.1%
Initial Fusion
11.5%
21.6%
48.2%
DENNL
21.8%
48.5%
75.2%
Our proposed method outperforms the conventional EM as well as the GraphSage (Hamilton et al.. 2017) in this experiment. Note that the user feature used is the user embedding due to GraphSage, thus DENNL has all the information that GraphSage can offer. One way to interpret the result is that method is enhancing GraphSage with HSMM that captures the temporal interest shift of the users.
7 CONCLUSION
In this work, we proposed a novel method in combining EM algorithm with neural network to predict the parameters of a collection of Hidden Markov Models. The basic idea to use the neural network to capture correlation among the HMMs so the information across different HMMs can be shared and re-used. The key technical contribution of this work is in providing a proof that the gradient of the EM iteration can be efficiently and reliably approximated using the SPSA. We evaluated our proposed on synthetic data as well as real-world e- e-Commerce data. An interesting observation is that the user embedding trained in unrelated task using graph convolutional neural network can be highly informative HMM parameter estimation. Parallels can be drawn between this observation and the success of pre-trained word embedding in downstream natural language processing tasks.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
A. Bietti, F. Bach, and A. Cont. An online EM algorithm in hidden (semi-)markov models for audio segmentation and clustering. In 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 1881-1885, April 2015, doi: 10. 10.1009/CASSP2221177777
Jeff A Bilmes et al. A gentle tutorial of the em algorithm and its application to parameter estimation for gaussian mixture and hidden markov models. International Computer Science Institute, 4(510); 126, 1998.
Thang D. Bui, Daniel Hernández-Lobato Yingzhen Li, José Miguel Hermández-Lobat, and Richard Turner. Deep Gaussian Processes for Regression using Approximate Expectation Propagation. arXiv e-prints, art. 16X.:1160..0133, Feb 2016.
Olivier Capp. Online EM Algorithm for Hidden Markov Models. Journal of Computational and Graphical Statisties,, 20(3):728-744 749, 2011. ISSN 10618600. httt::////wwat hott:://www.sttor.oorggg
stable e 23248849
Heng-Tze Cheng, Levent Koc, Jeremiah Harmsen, Tal Shaked, Tushar Chandra, Hrishi Aradhye, Glen Anderson, Greg Corrado, Wei Chai, Mustafa Ispir, et al. Wide & deep learning for recommender systems. In Proceedings of the 1st Workshop on Deep Learning for Recommender Systems, pp. 7-10. ACM, 2016.
A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological) 39(1):1-38 1977. ISSN 00359246. httt:ht::/// //tt::://ww.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lec, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: /8/00v 10.04005 2018.
Mihajlo Grbovic and Haibin Cheng. Real-time personalization using embeddings for search ranking at airbnb. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery ##38: Data Mining, KDD '1, pp. 311 311-320, New York, NY, USA, 2018. ACM. doi: 10.1145/3218819.322999
ISBN 978-1 1145/321981 3t5p/221989...0 9885
htRlhhtp://dde acm. art.////.0.oo.o/.0.o
Klaus Greff, Sjoerd van Steenkiste, and Jürgen Schmidhuber: Neural Expectation Maximization. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 6691 6701. 2017. URL http: 7/papers www.:issss.sppppem wwtpppppppppppeteeccccccccee..et wttpappppreeaeaaaeaaa----------- nww.al in maximi zat ion, pdf
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems. pp. 1024-1033 2017.
K. He, X. Zhang. S. Ren, and Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 770-778, June 2016. doi: 10.1109/CVPR.2016.
Geoffrey Hinton, Sara Sabour, and Nicholas Frosst. Matrix capsules with EM routing. In International Conference on Learning Representations, 2018. URL URR.tttps///ppereviiee
net p Forum?id www.miididhhhhGGHHH HJWL
Mortaza Jamshidian and Robert I. Jennrich. Acceleration of the EM algorithm by using Quasi-Newton methods. Journal of the Royal Statistical Society. Series B (Methodological), 59(3):569-587 1997.
ISSN 00359246. URL WRLLhtp::// //wtt: httptt.....ggtttel/ee////00
Rahul G Krishnan, Uri Shalit, and David Sontag. Structured inference networks for nonlinear state space models. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal
interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '19, pp. 1269.1278 New York, NY, USA, 2019. ACM. ISBN
doi: 10. htt.:/222220003338999 URL http: /oi. acm.
org 0tc/100.115/32222550

---

Under review as a conference paper at ICLR 2020
Scott Linderman, Matthew Johnson, Andrew Miller, Ryan Adams, David Blei, and Liam Paninski. Bayesian Learning and Inference in Recurrent Switching Linear Dynamical Systems. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 914-922, Fort Lauderdale, FI., USA, 20-22 Apr 2017. PMLR. URL httt:://proceeeeeee ngs. ml press/
html
James Munkres. Algorithms for the assignment and transportation problems. Journal the Society for Industrial and Applied Mathematics, 5(1):32-38, 1957. ISSN 03684245. URL http:
www. , jstor.stoo..ooo . org/ stableaaaaaaaeeeeee 2098689
Mari Ostendorf, Vassilios Digalakis, and Owen Kimball. From HMM's to segment models: A unified view of stochastic modeling for speech recognition. IEEE Transactions on Speech and Audio Processing, 4(3)3360-378, 1996. ISSN 10636676.
Matthew E. Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. In Proc. of NAACL, 2018.
L. R. Rabiner. A tutorial on hidden markov models and selected applications in speech recognition. Proceedings of the IEEE, 7722)257-286, Feb 1989. ISSN 0018-9219. doi: 10.1 10.1109/5.18666
Syama Sundar Rangapuram, Matthias W Seeger, Jan Gasthaus, Lorenzo Stella, Yuyang Wang, and Tim Januschowski. Deep state space models for time series forecasting. In Advances in Neural Information Processing Systems 31. 2018. URL httpt:::/ppapee..eem nwtps.s.iiscccccoo..o..o httpppppccppppppppppppp 8004- -dep- state space-models models for t time series fowecasting..oo
Walter Rudin al. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1964.
Sadegh and C. Spall. Optimal random perturbations for stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 43 (10):1480-1484, Oct 1998. ISSN 0018-9286
doi: 10.1109/9.720513.
Payman Sadegh. Constrained optimization via stochastic approximation with simultancous perturbation gradient approximation. Automatica, 33(5):889 892, 1997. ISSN 0005-1098 doi: http:://do.oo////00000sss//oss00 com/ http://ccoooeerreeeee///////1113
URL http: www. sci www.ncedireeeeeeeecceeceeeeeeeee
David Salinas, Valentin Flunkert, and Jan Gasthaus. DeepAR: Probabilistic Forecasting with Autore-
gressive Recurrent Networks. arXiv e-prints, art. arXiv: 1704:0404441 10, Apr 2017.
Abhra Sarkar and David B. Dunson. Bayesian Higher Order Hidden Markov Models. arXiv e-prints, art. arXiv:1805, 12201, May 2018.
J. C. Spall. Adaptive stochastic approximation by the simultaneous perturbation method. In Proceed- ings of the 37th IEEE Conference on Decision and Control (Cat. No.98CH36171), volume 4, pp. 3872-3879 vol.4, Dec 1998. doi: 10.1109/CDC.1998.77 1998.76183....
James Spall. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation. IEEE Transactions on Automatic Control, 37(3):332-344 1992.
Angus Ellis Taylor and David C Lay. Introduction to functional analysis, volume Wiley New York, 1958.
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. Know-evolve: Deep temporal reasoning for dynamic knowledge graphs. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3462334423443 3471, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. http::epp//oceeeeiiieo
wt..........ss.................s PMLR. utl. press wtttt////////tttt
17a.iil1....... htmm]
A. Viterbi. Error bounds for convolutional codes and asymptotically optimum decoding algorithm.
IEEE Transactions on Information Theory, 13(2):260-26) April 1967. ISSN 0018-9444 doi:
10

---

Under review as a conference paper at ICLR 2020
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Temgrad: Ternary gradients to reduce communication in distributed deep learning. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems 30, pp. 1509-1519. 2017.
C. F. Jeff Wu. the convergence properties of the EM algorithm. The Annals of Statistics, I1(I): 95-103, 1983. ISSN 00905364. URL / jstor.sto...........
Sinan Yildirim. Sumeetpal S. Singh, and Arnaud Doucet. An online expectatoommaximizatio
algorithm for changepoint models. Journal of Computational and Graphical Statisticss 22(4): 2013. doi: 00000/00666000202..066 10618600 2012 674653
URL http:: http:////ooooooo.oooo/oo/o/g
Guorui Zhou, Xiaoqiang Zhu, Chenru Song, Ying Fan, Han Zhu, Xiao Ma, Yanghui Yan, Junqi Jin, Han Li, and Kun Gai. Deep interest network for click-through rate prediction. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '18, pp. 1059-1 1068, New York, NY, USA, 2018. ACM. ISBN 978-114503-5552-00 doi: 0111532219889332192222 URL URL http:://toooo acm. wtlg//...115///001
A APPENDIX
A.1 PROOF OF LEMMA THEOREM
Lemma 1. For i-th dimension fa of f in equation
10
8
exist and are uniformly bounded
Ths d2ig 0r,
on the range of parameter such that for i, J2,
J3
M.
8¹
(0, 2)
s To.
(17)
where o is the observation sequence and To is a positive scalar.
Proof. We first show that that the numerator and denominator of fi is the polynomial function of M-parameters. Since the range of parameters closed and bounded set, then it follows (Rudin cct al., 1964) that the third partial gradient of fi is uniformly continuous and up bounded and then Lemma is established.
Rewrite equation
as
[ai(t 1), ,aN(t + 1)] [ai(t), (ax(t)))..,,((())) ((+1))
(18)
where
bi(ot+))
E(++) = Ax
(19)
bx(04+1)
Then it follows that
(t)] = [al (.N.)........(( (1) x II
D
(20)
2
where = 1,..., T. Fort = let I[ g() = IN where IN is N x N identity matrix. According
to equation 18 we have
(t = [a)(())) .......... (ax))...aa))) x II
(()) x E
(21)
t=2
where e; is N-column vector, the i-th element equals to one and the rest elements equal to zeros.
Rewrite equation 4 as
[()(1)
+((++1)
I(++1) x
(NN
(x((+1)
11

---

Under review as a conference paper at ICLR 2020
which together with (((T) 1, 1,... N, yields that
[1(t)]
πI
Dd x
IN.
(22)
[xx(t]
1=(+1
where 1N N-ddimensional column vector with all elements equaling to onc, = ,, ,, For
t = T, let Ii D = IN According to equation 22 we have
T
(.()) ef
II (=++1
0
IN:
which together with equation 21 yields that
0s (1) [a,(1), ,n((I)
Σ x cee x II
Σ( x 1N-
(23)
1=2
i=++1
Define N-dimensional column vector as
T II 1=1-1
((.)) II
0 x e x
3 x 1n.
(24)
Let mijh be the it, jr-th element of ( Then the f-th element of (8.0)) is just linear combina- tion of elements miz.ja .. -inrrrr where the coefficient in front of miz.j mirjjr fr is defined as (6,t,) pada,riirrd It follows that
Eindhe Sr 12.32." er jr Mig.ja Miyor
(1,11)
((6))
(25)
Eig ir Cagda." Srirr Miz.j mirjr.
(1,NN)
Combining equation
23 equation 24 and equation 25 we have
a (x)
Σ
Σ
Tebe Jase.... ir jr Mi2.22
(1.0,))
Mirdr
(26)
According to equation 19 given that observation or h, m a (0i)
aig. by (h). From
equation 26 it is clearly that (t) is the polynomial function of parameters {A,, B, T.. From equation and equation 26 we have
Σ Einjar Anjjr Tebe(or j2.ja... innfr Miaij
(1,1,))
(R+1)
Miy
(27)
EN EN Emaier br mebe(o1) (6.1.8)
2222. Jr Minja mir.fr
The numerator and denominator of π. (k++) are polynomial function of parameters À = {A, x).
According to (Rudin et al. 1964). the third partial gradient of म (k+1) to uniformly bounded on the range of parameters, which is bounded and closed set on RM
Since (o041) misse where is = i.j: then similar as equation 26 we have ((0))),b((00)))(((--
a,(t)m,,,,8,tt 1)
Σ
Σ
Tebe(on )
(.4.0 Aader miggs Mir. (28)
E=1 12. Jr
where index j, of coefficients (ig4.)
Ca Jr corresponds to i, in (t)a + 1).
Combining equation equation 26 and equation
28
we have
1 En ánár Tebr
( (b.....))
(k+1) j
22.2." 5r jr Mig.ja ... miy dr
(29)
EI-1 ΣN En En brii mebe (1 12daar .z in Mig.in
(1,t,))
May
12

---

Under review as a conference paper at ICLR 2020
Similarly, it follows from equation and equation that
(h) Ei=EE Einger in (ebe(01)80n (1.2,)
12.2. 5r Mig.ja" Mer-dr
(30)
EE Enatar in Tebe(o)) (0(()0))))) (100)i1g2aa j2 Ar M4a.22 Mirdo
(1,4,))
Note that the numerator and denominator of 1. parameters = B, J.). Then the third partial gradient a,j (R+1) and 6. b(*++1)) (h) are also bounded
(k++) and b (h) are also polynomial function of
b(*+1(()))))))))))))))))())))b
on the range of parameters. Since f in equation 10 is equivalent to equation 27 equation 29 and
equation 30 the first partial gradient of f is uniformly bounded.
Theorem 1. Suppose that for each k, A ... A (k) M are independent each other and have
mean such that E(A, (K) 0, = 1,2, ... ,. In addition, as k + oo, almost surely |A (M) | S TI
and E1 A
S T2, i = 1, 1, M. where TI and 72 are positive constants. Then for i + oc, almost
surely
| (j J Frr |= |
= 0
(31)
where ||-||= is Frobenius norm.
Proof. According to equation 11
equation 12 and equation 14 the i-th row, j-th column element
difference between j (k) and (R) is
Sa (2(A) + ea (k) Jo (A(t) a (k)
(f((A())
(k,-
(k-))
(1)
(K) iJ
6. C,
(32)
A (1)
abg
2
(k)
Taylor series expansion
(Taylor & Lay
1958 of fi(.) is represented as
Si (Ax + cs ())
1((A(0) +
(k) (f(()())
2
1
ΣΣ 1=1j==1
G (1) A 83
02, 02,2
h=
M
f (H) + +g(( (())
A (k) (1) A
(1)
+
02 02
and
M
0f((1()) A
M M
GA (K) (1) (((()(()))
Si (xx A4--cade -2 = )( - Σ
ΣΣ
Σ
2
J7 82,0
==
m==1j==
M M
O. (2(+) a())
ΣΣΣ
(
(b) AMA
(1)
0x
j==1 11=
1==1
where g(+),g(-) E (0. ck). Then it follows that
fi (2(x) + (1)) ft (A A Of((A(1)
1
Σ
A
(k) Of(()())
+ +RES, (33)
2rq A (K)
A
(K)
where
M
M
M
03 (2(t) + ((+)
03 -
(K) (k)
RES
+
12A
(k)
0x
0x,0220ss
ja
===1
Since E
A
(k:)
0, then
)1
1
(7(M)
(AA(A) = =0.
E
F4)
Fk = E
E
(34)
Oyn
f1
3173
13

---

Under review as a conference paper at ICLR 2020
Since f..(()) 0AA S 7p from Lemma almost surely
and E
1 < 72, as + oc,
A
then given Fk, the expectation of RES in equation 33
is bounded such that as k - co, almost surely
[E(ES|)F <
Tock
Σ
E
J1
(k)
js
(R)
To T2
(35)
(E)
ja=1
Combining equation 33 equation 34 and equation 35|
almost surely
ft (A A (46) ft (A(e) (A)(
(f((1(k))
E
-(()),
(36)
2cz 2
(R)
In addition, from equation 13
we have
(1++)
(R,-)
E
E
FR
2ck
A
(k)
which together with equation
32 and equation
336 yields that as - oo, almost surely
E
(10
J (1)
F&) O(2t),
It follows that
E (j(N)- ((() (10)-
- O(22).
A.2 DESCRIPTION OF E-COMMERCE DATASET
The operation specialist who has deep domain knowledge in the Home Decoration sector have concluded that after a condo purchased, the customer will likely go through distinct phases: Planning. Indoor Const ructi on, Furniture and Accessor es. In the P Planning ng phase the customer mainly browses listing of designing services and contractors. Representative items in the Indoor Const construction ion includes electrical and plumbing supplies. The user's interest changes according to the actual decoration progress of the condo. Once we have identified that a user likely switch from one phase to another, we can begin recommend the items that belong the next phase. The ability to incorporate such detailed temporal information is key improvement over existing recommender system algorithms.
The hidden states include the four phases discussed above, as well as NotDecorat inrcoorating state to indicate that the user not actively considering items in the Home Decoration. We summarize the user's behavior on the platform on a daily basis. Each day, we assign strength value to total of 17 sub-categories (each the four phases consists of four sub-categories, plus one for no action). The strength value is calculated based on the number of clicks/purchases and serves an indicator of the level of interest of the user in a particular sub-category. The strength value across the 17 sub-categories is normalized to 1. With this formulation, the emission probability is the Multinomial distribution. The duration distribution is Poisson distribution.
The user feature that provided to the neural network is 128 dimension embedding trained in a link prediction task using GraphSage. The task is to predict whether a user would click an item solely based the user embedding and item embedding. Such embedding not only encodes the numerical and categorical information of the users (such as location and income level), but also captures the user-to-item interaction on the platform. We chose 10000 users the platform that has a large number of clicks/purchases in Home Decoration, and used 180 days of their behavior between January 2018 and July 2018 as training data. The user's behavior between July 1st and July 2nd 2018 is used as validation data.
14


Reviews:
[{"review_id": "SyerVLaBqr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is about a method for estimation of parameters of a collection of HMMs and the main contribution is the  combination of classical EM with a neural net. \n\n+ I like the idea of generally approximating gradients in more specific layers that are usually not easy to compute. They clearly formulate their message here and the technical parts of adapting work from prior literature looks solid. \n- At the same time I don’t know how much the computational constraints that are formulated are really constraints in practice. A couple of the related works that are cited don’t seem to have these issues. Naively O(T^2) doesn’t really sound like too much of a problem unless the sequences are really long. (In their practical example that isn’t applied to more general recommender systems, this doesn’t really seem to be the case. So it’s unclear )\n+ The technical contribution of the gradient estimation seems sound. While I didn’t really go through the proof of convergence, it at least looks rigorous. But I would have to spend a lot more time here to form a well informed opinion.\n+ The experiments on synthetic data are clear and further empirically motivate the authors’ work. \n\nThe paper is very well written in some parts and in other parts is difficult to understand.\n\n- I am not sure what the benefit of the “e-commerce” application is to the community. The dataset seems to be neither open-source, nor referenced and is insufficiently described. The comparison and conclusion with respect to e.g. GraphSage is hard to interpret as GraphSage is neither explained nor referenced properly (unless I missed it somehow). The authors repeatedly emphasize that their approach works well here but not in the “more general recommender systems scenario”. It would be good if the authors showed something that the rest of the community can directly relate to instead of something that is closed-source and by definition not reproducible. \n- I suppose “We apply DENNL in a clearly defined and fast-growing sector on OUR e-Commerce platform, namely Home Decoration” is technically a violation of the blind review if the authors were to now include a reference/link etc. to the dataset. On the other hand, if the dataset remains closed-source then blind review isn’t violated but results aren’t reproducible and hard to follow by the community with the current level of description. \n\nIf the authors can comment about the last few points above (especially about open dataset, reproducibility) then I will reconsider raising the rating. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJecXUON9B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose to use numerical differentiation (using random perturbation) to approximate the Jacobian of a particular update (essentially equations 5~7) which plays an important role in the estimation of HMMs.  To do so, the authors provide first a concise intro to HMM models (well known stuff in S2), presenting the iteration in detail, jump into their model (cryptically presented in my opinion in S3) and then propose a numerical approximation scheme using SPSA (building upon literature from the 90's, with Theo 1 being the main contribution), before moving onto experiments.\n\nI have found the paper poorly presented. Its general motivation stands on a shaky ground (as illustrated by the choice of words by the authors, see below). In terms of presentation, reminders on HMM are welcome, but unfortunately the authors have not kept the same standard for clarity of notation in Section 3, which makes reading and understanding what the authors are doing quite difficult. Not being a specialist in this field, I have struggled a bit to understand the model itself, and the practical motivation of adding a DNN in the middle of what is otherwise an unrolled back-and-forth between k steps of EM estimation of transition parameters and the addition of a DNN layer. Despite the complexity in the story, what the authors propose is essentially to apply a numerical approximation scheme for Jacobians of these EM updates instead of backprop. Since this is the crux of the contribution,  I feel some more numerical evidence that their approach works compared to baselines (e.g. Hinton et al 2018) is needed. For these reasons my assessment is a bit on the lower side. \n\n- parenthesis bug in b_j(... in Eq.4\n- in Eq. 5, index i appears both in numerator (as regular index) and denominator (as sum index)\n- what is \\Psi in Eq.8 ?\n- \"While HMM is arguably less prevalent in the era of deep learning\": odd way to start an intro. All papers cited date back to more than 2011, 2 in 2006, all the rest in 20th century. This is particularly strange given the few citations to papers >2015 in Section 5.\n- the observation sequence o_{t,1:T(u)} is \"weakly\" indexed by u (since T(u) is just a length)\n- What is the \\forall u notation below Eq. 9?\n- \"the number of nodes required to build the forward and backward\nprobability in the computation graph of an automatic differentiation engine is on the order of O(T^2). Empirically we found this leads to intractable computation cost.\" since this is critical, where is this empirical evidence? this seems to be a storage problem and cannot be a complexity issue. There are ways to mitigate this problem by only storing partially information, I feel this comparison would add a lot of value to the authors' claim.\n- Where is J^{(k)} defined (as opposed to \\hat{J}^{(k)}) defined in Eq.14?\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose to use numerical differentiation to approximate the Jacobian while estimating the parameters for a collection of Hidden Markov Models (HMMs). Two reviewers provided detailed and constructive comments, while unanimously rated weak rejection. Reviewer #1 likes the general idea of the work, and consider the contribution to be sound. However, he concerns the reproducibility of the work due to the niche database from e-commerce applications. Reviewer #2 concerns the poor presentation, especially section 3. The authors respond to Reviewers’ concerns but did not change the rating. The ACs concur the concerns and the paper can not be accepted at its current state.
Decision: Reject