class: center, middle, inverse, title-slide # PLN models ### Mahendra Mariadassou, INRAE ### Shandong University, Weihai (CN)
Summer School 2021 --- --- class: middle # Reminder .pull-left[ - Interest for .alert[multivariate count data] - Counts in ecology have .alert[peculiar] features: - sparse (.grey[grey cell] = null count) - overdispersed - not centered around a central location parameter - Example from Jakuschkin, Fievet, Schwaller, Fort, Robin, and Vacher [Jak+16]  ] .pull-right[ ![](04_pln_models_files/figure-html/unnamed-chunk-1-1.png) ] --- # PLN models 1. Multivariate Normal 1. The Log Normal distribution 1. The Poisson Log Normal distribution 1. Variational Approximation 1. Parameter Estimation --- class: inverse, center, middle # Multivariate Normal --- ## Multivariate Normal distribution (MVN) The .alert[multivariate normal distribution] of a p-dimensional random vector `\(\bY = (Y_1,\ldots, Y_p)\)` can be written in the following notation: $$ \bY \sim \N(\bmu, \bSigma) \quad \text{or sometimes} \quad \N_p(\bmu, \bSigma) $$ where `\(\bmu\)` is the mean vector of `\(\bY\)` $$ \bmu = E[\bY] = (E[Y_1], \dots, E[Y_p]) $$ and `\(\bSigma\)` is the `\(p \times p\)` variance matrix $$ `\begin{equation} \bSigma = (\Sigma_{jj'})_{j,j'} \; \text{ where } \; \Sigma_{j,j'} = Cov(Y_j, Y_{j'}) \end{equation}` $$ -- The density of `\(Y\)` is given by $$ `\begin{align} P(Y; \bmu, \bSigma) & = \frac{1}{\sqrt{(2\pi)^p |\bSigma|}} \exp\left( -\frac{(\bY - \bmu)^\top \bSigma^{-1} (\bY - \bmu)}{2} \right) \end{align}` $$ and for any `\(\bx \in \Rbb^p\)`, `\(\bx^\top \bY \sim \N(\bx^\top \bmu, \bx^\top \bSigma \bx)\)` --- ## Moments of the MVN (I) - Let `\(\bOmega = \bSigma^{-1}\)` and note `\(\bfeta_1 = \bSigma^{-1} \bmu\)` and `\(\bfeta_2 = -\bSigma^{-1}/2\)`. - Note that for any vector `\(\bx\)` and symmetric matrix `\(\bA\)`, - `\(\bx^\top A \bx = \langle \bx \bx^\top, \bA\rangle\)` where `\(\langle \bA, \bB \rangle = Tr(\bA^\top \bB)\)` is the matrix dot product. $$ `\begin{align} P(Y; \bmu, \bSigma) & = \frac{1}{\sqrt{(2\pi)^p |\bSigma|}} \exp\left( -\frac{(\bY - \bmu)^\top \bSigma^{-1} (\bY - \bmu)}{2} \right) \\ & = \frac{1}{(2\pi)^{p/2}} \exp\left( \bY^\top \bSigma^{-1} \bmu -\frac{1}{2}\bY^T \bSigma^{-1}\bY - \frac{1}{2}\bmu^\top\bSigma^{-1}\bmu - \frac{1}{2}\log|\bSigma|\right) \\ & = \frac{1}{(2\pi)^{p/2}} \exp\left( \bY^\top \bSigma^{-1} \bmu -\frac{1}{2}\langle \bY \bY^T, \bSigma^{-1}\rangle - \frac{1}{2}\bmu^\top\bSigma^{-1}\bmu - \frac{1}{2}\log|\bSigma|\right) \\ & = \frac{1}{(2\pi)^{p/2}} \exp\left( \bY^\top \bfeta_1 + \langle \bY \bY^T, \bfeta_2 \rangle + \frac{1}{4}\bfeta_1^\top\bfeta_2\bfeta_1 + \frac{1}{2}\log|-2\bfeta_2|\right) \\ \end{align}` $$ In particular, the MVN is an exponential family with natural parameters `\((\bfeta_1, \bfeta_2) = (\bOmega\bmu, -\bOmega/2)\)`, sufficient statistics `\((\bY, \bY\bY^\top)\)` and log-normalizer `\(A(\bfeta_1, \bfeta_2) = -\frac{1}{4}\bfeta_1^\top\bfeta_2\bfeta_1 - \frac{1}{2}\log|-2\bfeta_2|\)`. --- ## Moments of the MVN (II) By definition of the MVN, `\(E[\bY]\)` and `\(V[\bY]\)` are given by: $$ E[\bY] = \bmu \quad \text{ and } V[\bY] = \bSigma $$ By definition of the variance matrix, $$ V[\bY] = E[\bY \bY^\top] - E[\bY]E[\bY]^\top \Rightarrow E[\bY \bY^\top] = \bSigma + \bmu\bmu^\top $$ -- In addition, for all `\(\bx \in \Rbb^p\)`, the moment generating function of the MVN is given by $$ E[\exp(\bx^\top \bY)] = \exp\left( \bx^\top \bmu + \frac{1}{2} \bx^t \bSigma \bx\right) $$ The last useful equality is that for `\(\bx\)` and symmetric matrix `\(\bS\)` $$ E[(\bY - \bx)^\top \bS (\bY - \bx)] = (\bmu - \bx)^\top \bS (\bmu - \bx) + Tr(\bSigma \bS) $$ --- ## MGF of the MVN: demo Based on the MGF of a univariate gaussian function --- class: inverse, center, middle # Log Normal distribution --- ## Log normal (LN) distribution A random variable `\(\bY\)` is .alert[multivariate lognormal] with parameters `\((\bmu, \bSigma)\)`, noted `\(\bY \sim \LN(\bmu, \bSigma)\)`, iff - `\(\bY\)` has positive components - the vector `\(\bZ = \log(\bY) = (\log(Y_1), \dots, \log(Y_p))\)` is gaussian with `\(\bZ \sim \N(\mu, \bSigma)\)`. -- The density of the multivariate density is quite involved but the density of the univariate log-normal is easy. If `\(Y \sim \LN(\mu, \sigma^2)\)`, the density of `\(Y\)` is given by $$ f_Y(x) = \frac{1}{x\sigma\sqrt{2\pi}} \exp\left( - \frac{(\ln(x) - \mu)^2}{2\sigma^2} \right) $$ -- Demo: Based on the cumulative distribution function --- ## Moments of the LN Since `\(\bY \sim e^{\N(\bmu, \bSigma)}\)`, one could be tempted to say `\(E[\bY] = e^{\bmu}\)` and `\(V[\bY] = e^{\bSigma}\)` where the exponential is applied coefficient by coefficient. -- But this is wrong due to Jensen's inequality and the convexity of `\(\exp\)`. Fortunately, we can use the MGF of MVN to compute `\(E[Y_j]\)`, `\(V[Y_j]\)` and `\(Cov(Y_j, Y_{j'})\)`: -- .pull-left[ $$ `\begin{align} E[Y_j] & = e^{\mu_j + \Sigma_{jj}/2} \\ V[Y_j] & = e^{2\mu_j + \Sigma_{jj}}(e^{\Sigma_{jj}} - 1) \\ & = E[Y_j]^2 (e^{\Sigma_{jj}} - 1) \\ Cov[Y_j, Y_{j'}] & = e^{\mu_j + \mu_{j'} + \frac{1}{2}(\Sigma_{jj}+\Sigma_{j'j'})}(e^{\Sigma_{jj'}} - 1) \\ & = E[Y_j]E[Y_{j'}] (e^{\Sigma_{jj'}} - 1) \end{align}` $$ ] .pull-right[ Note `\(\bZ = \log(\bY) \sim \N(\bmu, \bSigma)\)`. Proof based on the fact that $$ `\begin{align} E[Y_j] & = E[e^{Z_j}] \\ E[Y_j^2] & = E[e^{2Z_j}] \\ E[Y_j Y_{j'}] & = E[e^{Z_j + Z_{j'}}] \\ \end{align}` $$ ] -- In particular `\(Cov[Y_j, Y_{j'}]\)` has the .alert[same sign] as `\(\Sigma_{jj'}\)` and can thus be .alert[positive or negative]. --- class: inverse, center, middle # Poisson Log Normal distribution --- ## Poisson Log Normal (PLN) distribution A `\(p\)`-dimensional random variable `\(\bY\)` taking values in `\(\Nbb^p\)` is said to be .alert[PLN] [AH89] with parameters `\((\bmu, \bSigma)\)` iff there exists a `\(p\)`-dimensional random variable `\(\bZ\)` such that $$ `\begin{align} \bZ & \sim \LN(\bmu, \bSigma) \\ Y_j | Z_j & \sim \P(Z_j) \; \text{independently for all } j\\ \end{align}` $$ -- Or equivalently $$ `\begin{align} \bZ & \sim \N(0, \bSigma) \\ Y_j | Z_j & \sim \P(e^{\bmu + Z_j}) \; \text{independently for all } j \end{align}` $$ Since the canonical form of the Poisson distribution is `\(\P(e^\theta)\)`, we prefer the .alert[last formulation]. --- ## Moments of the PLN `\(\bY\)` is an (infinite) mixture of independent Poisson variable so we can use the laws of .alert[total expectation] and .alert[total covariance] to compute its mean and covariance. -- .pull-left[ $$ `\begin{align} E[Y_j] & = E[E[Y_j | Z_j]] \\ & = E[e^{Z_{j}}] = e^{\mu_j + \Sigma_{jj}/2} \end{align}` $$ $$ `\begin{align} V[Y_j] & = E[V[Y_j | Z_j]] + V[E[Y_j | Z_j]] \\ & = E[e^{Z_j}] + V[e^{Z_j}] \\ & = E[Y_j] + E[Y_j]^2(E) (e^{\Sigma_{jj}} - 1) \end{align}` $$ Note that `\(V[Y_j] > E[Y_j]\)` `\(\Rightarrow\)` .alert[overdispersion] compared to Poisson with same mean. ] -- .pull-right[ $$ `\begin{align} Cov[Y_j, Y_{j'}] & = E[Cov[\underbrace{Y_j, Y_{j'}}_{\text{independent}}| Z_j, Z_{j'}]] \\ & \quad + Cov[E[Y_j | Z_j]E[Y_{j'} | Z_{j'}]] \\ & = Cov[e^{Z_j}, e^{Z_{j'}}] \\ & = E[Y_j]E[Y_{j'}](e^{\Sigma_{jj'}} - 1) \end{align}` $$ Note that `\(Cov[Y_j, Y_{j'}]\)` has the .alert[same sign] as `\(\Sigma_{jj'}\)` and can be .alert[negative or positive]. ] --- ## Density .pull-left[ If `\(\bZ\)` is .alert[observed] $$ `\begin{align} P(\bY, \bZ; \bmu, \bSigma) & = P(\bY | \bZ) P(\bZ; \bmu, \bSigma) \\ & = \prod_{j=1}^p \underbrace{P(Y_j|Z_j)}_{\text{Poisson}} \underbrace{P(\bZ; \bmu, \bSigma)}_{\text{MVN}} \\ \log P(\bY, \bZ; \bmu, \bSigma) & = \sum_{j=1}^p \log P(Y_j|Z_j) + \log P(\bZ; \bmu, \bSigma)) \\ & = \sum_{j=1}^p (Z_jY_j - e^{Z_j} + \log(Y_j!)) + \\ & \quad -\frac{1}{2}\log|\bSigma| - \frac{p}{2}\log(2\pi) \\ & \quad -\frac{(\bZ - \bmu)^\top \bSigma^{-1} (\bZ - \bmu)}{2} \end{align}` $$ ] -- .pull-right[ If `\(\bZ\)` is .alert[not observed] $$ `\begin{align} P(\bY; \bmu, \bSigma) & = \int_{\bZ} P(\bY | \bZ) P(\bZ; \bmu, \bSigma) d\bZ \\ & = \frac{1}{\prod_j Y_j!}\int_{\bZ} [ e^{\bY^\top \bZ - \sum_{j} e^{Z_j}} ]{}P(\bZ; \bmu, \bSigma)dZ \\ & = \frac{1}{\prod_j Y_j!} E_{\bZ}[e^{\bY^\top \bZ - \sum_{j} e^{Z_j}}] \end{align}` $$ We can compute `\(E_{\bZ}[e^{\bY^\top \bZ}]\)` using the MGF of `\(\bZ\)` but not `\(E_{\bZ}[e^{\bY^\top \bZ} - \sum_j e^{Z_j}]\)`... $$ \log P(\bY; \bmu, \bSigma) = ? $$ ] -- .center[ We can compute `\(\ell_{comp}(\bmu, \bSigma)\)` but not `\(\ell_{obs}(\bmu, \bSigma)\)`. ] --- ## Accouting for covariates and offset In many cases we have access to covariates `\(\bx\)` and we're interested in the matrix `\(\bTheta\)` of the effects of covariates on species `\(j\)`. We can include them in the model by setting $$ \bmu = \bTheta\bx $$ -- We also have access to offsets to account for differences in observation effort `\(\bo\)`, we can include them by setting $$ Y_j | Z_j \sim \P(e^{o_j + Z_j}) $$ This change the complete log-likelihood to $$ `\begin{align} \log P(\bY, \bZ; \bTheta, \bSigma) & = \sum_{j=1}^p Y_j (o_j + Z_j) - e^{o_j + Z_j} + \log(Y_j!)) \\ & \quad -\frac{1}{2}\log|\bSigma| - \frac{p}{2}\log(2\pi) -\frac{(\bZ - \bTheta\bx)^\top \bSigma^{-1} (\bZ - \bTheta\bx)}{2} \end{align}` $$ --- ## Maximum Likelihood Estimation The observed likelihood `\(\ell_{obs}(\bTheta, \bSigma)\)` is .alert[untractable]. -- Remember the .alert[lower bound] from the Mixture of Multinomial section. For any distribution `\(Q(.)\)` over `\(\bZ\)`, $$ `\begin{align} \ell_{obs}(\bTheta, \bSigma) & = \log\left( \int_{\bZ} P(\bY, \bZ; \bTheta, \bSigma)d\bZ\right) \\ & = \log\left( \int_{\bZ} \frac{P(\bY, \bZ; \bTheta, \bSigma)}{q(\bZ)} q(\bZ)d\bZ\right) \\ & \geq \int_{\bZ} \log\left( \frac{P(\bY, \bZ; \bTheta, \bSigma)}{q(\bZ)}\right) q(\bZ) \\ & = E_Q\left[ \log(P(\bY, \bZ; \bTheta, \bSigma)\right] - E_Q\left[ \log Q(\bZ)\right] \\ & = F(Q, (\bTheta, \bSigma)) \\ % & = E_Q\left[ \log(P(\bY | \bZ)\log(P(\bZ; \bTheta, \bSigma)\right] - E_Q\left[ \log Q(\bZ)\right] \\ % & = E_Q\left[ \log(P(\bY | \bZ)] + E_Q[\log(P(\bZ; \bTheta, \bSigma)\right] - E_Q\left[ \log Q(\bZ)\right] \\ \end{align}` $$ We can maximize `\(\ell_{obs}(\bTheta, \bSigma)\)` by iteratively .alert[updating] - E-step: `\(Q = \text{arg}\max_Q F(Q, (\bTheta, \bSigma))\)` - M-step: `\((\bTheta, \bSigma) = \text{arg}\max_{(\bTheta, \bSigma)} F(Q, (\bTheta, \bSigma))\)` --- ## Variational Approximation In the mixture of MN, we solved the E-step explicitly by setting $$ `\begin{equation} Q(.) = P(.|\bY; (\bTheta, \bSigma)) = \frac{P(.|\bY; (\bTheta, \bSigma))}{\int_{\bZ} P(\bY, \bZ; (\bTheta, \bSigma))} \end{equation}` $$ but we can't compute `\(\int_{\bZ} P(\bY, \bZ; (\bTheta, \bSigma))\)`... -- Instead of finding the .alert[absolute best] distribution `\(Q\)`, we .alert[restrict] the search to a space of distribution which makes `\(F(Q, (\bTheta, \bSigma))\)` tractable. -- Assuming we have `\(n\)` samples `\(\bY = (\bY_1, \dots, \bY_n)\)`, we consider `\(Q\)` of the form $$ Q(\bZ_1, \dots, \bZ_n) = Q_1(\bZ_1) \otimes \dots \otimes Q_n(\bZ_n) = \N(\bm_1, Diag(\bs^2_1)) \otimes \dots \otimes \N(\bm_n, Diag(\bs^2_n)) $$ where `\(\bm_i\)` and `\(\bs_i\)` are .alert[variational parameters] for sample `\(i\)` and can be interpreted as `\(\bm_i \simeq E[\bY_i | \bZ_i; \bTheta, \bSigma]\)` and `\(\bs^2_i \simeq V[\bY_i | \bZ_i; \bTheta, \bSigma]\)` --- ## Variational Objective Note that `\(Q\)` depends only on `\(\bM = (\bm_1, \dots, \bm_n)\)` and `\(\bS = (\bs^2_1, \dots, \bs^2_n)\)`. $$ `\begin{align} F(Q, (\bTheta, \bSigma)) & = F((\bM, \bS), (\bTheta, \bSigma)) \\ & = \sum_{i=1}^n E_Q\left[ \log(P(\bY_i, \bZ_i; \bTheta, \bSigma)\right] - E_Q\left[ \log Q(\bZ_i)\right] \\ & = \sum_{i=1}^n E_Q\left[ \log(P(\bY_i | \bZ_i)\log(P(\bZ_i; \bTheta, \bSigma) \right] - E_Q\left[ \log Q(\bZ_i)\right] \\ & = \sum_{i=1}^n E_Q\left[ \log(P(\bY_i | \bZ_i)\right] + E_Q\left[\log(P(\bZ_i; \bTheta, \bSigma) \right] - E_Q\left[ \log Q(\bZ_i)\right] \end{align}` $$ --- ## `\(E_Q\left[ \log P(\bY_i | \bZ_i)\right]\)` Remember that the coordinates of `\(\bY_i|\bZ_i\)` are Poisson-distributed. -- $$ `\begin{align} \log P(\bY_i | \bZ_i) & = \sum_{j=1}^p Y_{ij}(o_{ij} + Z_{ij}) - e^{Z_{ij}} + C \\ E_Q\left[ \log P(\bY_i | \bZ_i) \right] & = \sum_{j=1}^p Y_{ij} (o_{ij} + E_Q[Z_{ij}]) - E_Q[e^{Z_{ij}}] + C\\ & = \sum_{j=1}^p Y_{ij} (o_{ij} + m_{ij}) - e^{m_{ij} + s_{ij}^2/2} + C \\ & = \bY_i^\top (\bo_i + \bm_i) + 1_p^\top e^{\bm_i + \bs_i^2/2} \end{align}` $$ --- ## `\(E_Q\left[\log(P(\bZ_i; \bTheta, \bSigma) \right]\)` Remember that `\(P(\bZ_i; \bTheta, \bSigma)\)` is a Gaussian density -- $$ `\begin{align} \log(P(\bZ_i; \bTheta, \bSigma) & = -\frac{1}{2}\left[ \log|\bSigma| + (\bZ_i -\bTheta\bx_i)^\top \bSigma^{-1} (\bZ_i -\bTheta\bx_i) \right] + C\\ E_Q\left[ \log(P(\bZ_i; \bTheta, \bSigma) \right] & = -\frac{1}{2}\left( \log|\bSigma| + E_Q\left[(\bZ_i -\bTheta\bx_i)^\top \bSigma^{-1} (\bZ_i -\bTheta\bx_i) \right] \right) + C \\ & = -\frac{1}{2}\left( \log|\bSigma| + (\bm_i -\bTheta\bx_i)^\top \bSigma^{-1} (\bm_i -\bTheta\bx_i) + Tr\left[\bSigma^{-1} Diag(\bs_i^2)\right] \right) + C \\ \end{align}` $$ --- ## `\(E_Q\left[\log(Q(\bZ_i) \right]\)` Remember that `\(Q(\bZ_i)\)` is a Gaussian density with parameters `\(\bm_i\)` and `\(\bs_i^2\)` -- $$ `\begin{align} \log Q(\bZ_i) & = -\frac{1}{2}\left[ \log|Diag(\bs_i^2)| + (\bZ_i -\bm_i)^\top Diag(\bs_i^2)^{-1} (\bZ_i -\bm_i) \right] + C\\ E_Q\left[ \log Q(\bZ_i) \right] & = -\frac{1}{2}\left( \log|Diag(\bs_i^2)| + E_Q\left[(\bZ_i -\bm_i)^\top Diag(\bs_i^2)^{-1} (\bZ_i -\bm_i) \right] \right) + C \\ & = -\frac{1}{2}\left( \log|Diag(\bs_i^2)| + p \right) + C \\ & = -\frac{1}{2}\log|Diag(\bs_i^2)| + C \\ \end{align}` $$ --- class: inverse, center, middle # Parameter estimation --- ## Variational Objective Putting all the parts together, the variational objective is $$ `\begin{align} F(\bM, \bS, \bTheta, \bSigma) = & -\frac{n}{2}\log|\bSigma| - \frac{1}{2}\sum_{i=1}^n \left( (\bm_i - \bTheta\bx_i)^\top \bSigma^{-1} (\bm_i - \bTheta\bx_i) + Tr(\bSigma^{-1} Diag(\bS_i^2)) \right) \\ & + \sum_{i=1}^n \bY_i^\top (\bo_i + \bm_i) - 1_p^\top \exp(\bo_i + \bm_i + \bs_i^2/2) \end{align}` $$ We can thus compute the partial derivatives of `\(F\)` with respect to `\(\bM, \bS, \bTheta, \bSigma\)`. --- ## M step In matrix form, we can write $$ `\begin{equation} \frac{\partial F}{\partial \bTheta} = - \bSigma^{-1}\left[ \bX^\top\bX \bTheta - \bX^\top \bM\right] \quad \text{and} \quad \frac{\partial F}{\partial \bSigma^{-1}} = \frac{n}{2}\bSigma^{-1} - \frac{1}{2}\left[ \sum_{i=1}^n (\bm_i - \bTheta\bx_i)^\top (\bm_i - \bTheta\bx_i) + \sum_{i=1}^n Diag(\bs_i^2) \right] \end{equation}` $$ -- Setting the derivatives to `\(0\)` leads to the following update $$ `\begin{align} \bTheta^{(t+1)} & = (\bX^\top\bX)^{-1}\bX^\top \bM^{(t)} \\ \bSigma^{(t+1)} & = \frac{1}{n}\left[ \sum_{i=1}^n (\bm_i^{(t)} - \bTheta^{(t+1)}\bx_i)^\top (\bm_i^{(t)} - \bTheta^{(t+1)}\bx_i) + \sum_{i=1}^n Diag({\bs_i^2}^{(t)}) \right] \\ \end{align}` $$ --- ## E step Noting `\(\bA\)` the matrix with coordinates `\(A_{ij} = \exp(o_{ij} + m_{ij} + s_{ij}^2/2)\)`, we have $$ `\begin{align} \frac{\partial F}{\partial \bm_i} & = \bSigma^{-1} (\bTheta^{(t+1)}\bx_i - \bm_i) + (\bY_i - \bA_i) \\ \frac{\partial F}{\partial \bs_i^2} & = \frac{1}{2} \left[ Diag\left({\bSigma^{(t+1)}}^{-1}\right) - \bA_i + Diag(\bs_i^2)^{-1} \right] \end{align}` $$ -- There is no explicit solution for setting those derivatives to `\(0\)` so we use .alert[gradient descent] to find `\(\text{arg}\max_{(\bM, \bS)} F(\bM, \bS, \bTheta^{(t+1)}, \bSigma^{(t+1)})\)` --- class: middle, center  --- ## Take Home Message - ### The PLN model is .alert[flexible] for modelling (no sign constraint) - ### Parameter estimation is tricky and relies a lot of computational tricks and .alert[variational estimation] (see [CMR21] for details) - ### Variational estimation is a .alert[powerful tool] to estimate parameter in .alert[untractable models] --- Aitchison, J. and C. Ho (1989). "The multivariate Poisson-log normal distribution". In: _Biometrika_ 76.4, pp. 643-653. Chiquet, J., M. Mariadassou, and S. Robin (2021). "The Poisson-lognormal model as a versatile framework for the joint analysis of species abundances". In: _Frontiers in Ecology and Evolution_ 9, p. 188. DOI: [10.3389/fevo.2021.588292](https://doi.org/10.3389%2Ffevo.2021.588292). Jakuschkin, B., V. Fievet, L. Schwaller, et al. (2016). "Deciphering the pathobiome: intra-and interkingdom interactions involving the pathogen Erysiphe alphitoides". In: _Microbial ecology_ 72.4, pp. 870-880.


Hello {user_name},
You have reset your account password.
Your credentials are:
Site Link: {site_link} Username: {email} Password: {password}
Best regards, {site_name}


Browser JavaScript execution flow, as well as in Node.js, is based on an event loop.
Understanding how event loop works is important for optimizations, and sometimes for the right architecture.
In this chapter we first cover theoretical details about how things work, and then see practical applications of that knowledge.
The event loop concept is very simple. There’s an endless loop, where the JavaScript engine waits for tasks, executes them and then sleeps, waiting for more tasks.
The general algorithm of the engine:
That’s a formalization for what we see when browsing a page. The JavaScript engine does nothing most of the time, it only runs if a script/handler/event activates.
Examples of tasks:
<script src="...">
loads, the task is to execute it.mousemove
event and execute handlers.setTimeout
, the task is to run its callback.Tasks are set – the engine handles them – then waits for more tasks (while sleeping and consuming close to zero CPU).
It may happen that a task comes while the engine is busy, then it’s enqueued.
The tasks form a queue, so-called “macrotask queue” (v8 term):
For instance, while the engine is busy executing a script
, a user may move their mouse causing mousemove
, and setTimeout
may be due and so on, these tasks form a queue, as illustrated on the picture above.
Tasks from the queue are processed on “first come – first served” basis. When the engine browser is done with the script
, it handles mousemove
event, then setTimeout
handler, and so on.
So far, quite simple, right?
Two more details: 1. Rendering never happens while the engine executes a task. It doesn’t matter if the task takes a long time. Changes to the DOM are painted only after the task is complete. 2. If a task takes too long, the browser can’t do other tasks, such as processing user events. So after a time, it raises an alert like “Page Unresponsive”, suggesting killing the task with the whole page. That happens when there are a lot of complex calculations or a programming error leading to an infinite loop.
That was the theory. Now let’s see how we can apply that knowledge.
Let’s say we have a CPU-hungry task.
For example, syntax-highlighting (used to colorize code examples on this page) is quite CPU-heavy. To highlight the code, it performs the analysis, creates many colored elements, adds them to the document – for a large amount of text that takes a lot of time.
While the engine is busy with syntax highlighting, it can’t do other DOM-related stuff, process user events, etc. It may even cause the browser to “hiccup” or even “hang” for a bit, which is unacceptable.
We can avoid problems by splitting the big task into pieces. Highlight first 100 lines, then schedule setTimeout
(with zero-delay) for the next 100 lines, and so on.
To demonstrate this approach, for the sake of simplicity, instead of text-highlighting, let’s take a function that counts from 1
to<PHONE_NUMBER>
.
If you run the code below, the engine will “hang” for some time. For server-side JS that’s clearly noticeable, and if you are running it in-browser, then try to click other buttons on the page – you’ll see that no other events get handled until the counting finishes.
```js run let i = 0;
let start = Date.now();
function count() {
// do a heavy job for (let j = 0; j < 1e9; j++) { i++; }
alert(“Done in” + (Date.now() - start) + ‘ms’); }
count(); ```
The browser may even show a “the script takes too long” warning.
Let’s split the job using nested setTimeout
calls:
```js run let i = 0;
let start = Date.now();
function count() {
// do a piece of the heavy job (*) do { i++; } while (i % 1e6 != 0);
if (i == 1e9) { alert(“Done in” + (Date.now() - start) + ‘ms’); } else { setTimeout(count); // schedule the new call (**) }
}
count(); ```
Now the browser interface is fully functional during the “counting” process.
A single run of count
does a part of the job (*)
, and then re-schedules itself (**)
if needed:
i=1...1000000
.i=1000001..2000000
.Now, if a new side task (e.g. onclick
event) appears while the engine is busy executing part 1, it gets queued and then executes when part 1 finished, before the next part. Periodic returns to the event loop between count
executions provide just enough “air” for the JavaScript engine to do something else, to react to other user actions.
The notable thing is that both variants – with and without splitting the job by setTimeout
– are comparable in speed. There’s not much difference in the overall counting time.
To make them closer, let’s make an improvement.
We’ll move the scheduling to the beginning of the count()
:
```js run let i = 0;
let start = Date.now();
function count() {
// move the scheduling to the beginning if (i < 1e9 - 1e6) { setTimeout(count); // schedule the new call }
do { i++; } while (i % 1e6 != 0);
if (i == 1e9) { alert(“Done in” + (Date.now() - start) + ‘ms’); }
}
count(); ```
Now when we start to count()
and see that we’ll need to count()
more, we schedule that immediately, before doing the job.
If you run it, it’s easy to notice that it takes significantly less time.
Why?
That’s simple: as you remember, there’s the in-browser minimal delay of 4ms for many nested setTimeout
calls. Even if we set 0
, it’s 4ms
(or a bit more). So the earlier we schedule it - the faster it runs.
Finally, we’ve split a CPU-hungry task into parts - now it doesn’t block the user interface. And its overall execution time isn’t much longer.
Another benefit of splitting heavy tasks for browser scripts is that we can show progress indication.
As mentioned earlier, changes to DOM are painted only after the currently running task is completed, irrespective of how long it takes.
On one hand, that’s great, because our function may create many elements, add them one-by-one to the document and change their styles – the visitor won’t see any “intermediate”, unfinished state. An important thing, right?
Here’s the demo, the changes to i
won’t show up until the function finishes, so we’ll see only the last value:
```
…But we also may want to show something during the task, e.g. a progress bar.
If we split the heavy task into pieces using setTimeout
, then changes are painted out in-between them.
This looks prettier:
```html run```
Now the <div>
shows increasing values of i
, a kind of a progress bar.
In an event handler we may decide to postpone some actions until the event bubbled up and was handled on all levels. We can do that by wrapping the code in zero delay setTimeout
.
In the chapter info:dispatch-events we saw an example: custom event menu-open
is dispatched in setTimeout
, so that it happens after the “click” event is fully handled.
menu.onclick = function() {
// ...
// create a custom event with the clicked menu item data
let customEvent = new CustomEvent("menu-open", {
bubbles: true
});
// dispatch the custom event asynchronously
setTimeout(() => menu.dispatchEvent(customEvent));
};
Along with macrotasks, described in this chapter, there are microtasks, mentioned in the chapter info:microtask-queue.
Microtasks come solely from our code. They are usually created by promises: an execution of .then/catch/finally
handler becomes a microtask. Microtasks are used “under the cover” of await
as well, as it’s another form of promise handling.
There’s also a special function queueMicrotask(func)
that queues func
for execution in the microtask queue.
Immediately after every macrotask, the engine executes all tasks from microtask queue, prior to running any other macrotasks or rendering or anything else.
For instance, take a look:
```js run setTimeout(() => alert(“timeout”));
Promise.resolve() .then(() => alert(“promise”));
alert(“code”); ```
What’s going to be the order here?
code
shows first, because it’s a regular synchronous call.promise
shows second, because .then
passes through the microtask queue, and runs after the current code.timeout
shows last, because it’s a macrotask.The richer event loop picture looks like this (order is from top to bottom, that is: the script first, then microtasks, rendering and so on):
All microtasks are completed before any other event handling or rendering or any other macrotask takes place.
That’s important, as it guarantees that the application environment is basically the same (no mouse coordinate changes, no new network data, etc) between microtasks.
If we’d like to execute a function asynchronously (after the current code), but before changes are rendered or new events handled, we can schedule it with queueMicrotask
.
Here’s an example with “counting progress bar”, similar to the one shown previously, but queueMicrotask
is used instead of setTimeout
. You can see that it renders at the very end. Just like the synchronous code:
```
A more detailed event loop algorithm (though still simplified compared to the specification):
To schedule a new macrotask: - Use zero delayed setTimeout(f)
.
That may be used to split a big calculation-heavy task into pieces, for the browser to be able to react to user events and show progress between them.
Also, used in event handlers to schedule an action after the event is fully handled (bubbling done).
To schedule a new microtask - Use queueMicrotask(f)
. - Also promise handlers go through the microtask queue.
There’s no UI or network event handling between microtasks: they run immediately one after another.
So one may want to queueMicrotask
to execute a function asynchronously, but within the environment state.
```smart header=“Web Workers” For long heavy calculations that shouldn’t block the event loop, we can use Web Workers.
That’s a way to run code in another, parallel thread.
Web Workers can exchange messages with the main process, but they have their own variables, and their own event loop.
Web Workers do not have access to DOM, so they are useful, mainly, for calculations, to use multiple CPU cores simultaneously. ```


%inherit file="../base.html"/>
## SEO Stuff
<%block name="title">MFA · Glowstone%block>
<%block name="description">Multi-factor authentication%block>
<%block name="og_title">MFA%block>
<%block name="og_description">Multi-factor authentication%block>
Multi-Factor Authentication
Enter the code from your authenticator app below


{% extends "base.html" %} {% import 'macros.html' as macros with context %} {% block styles %} {{ super() }} {% endblock %} {% block content %}
HistSync automatically uploads every command you type,
and lets you bookmark and share the most important commands.


Noram Ventures (CVE:NRM) Sets New 52-Week Low at $0.05
by Jessica MooreNoram Ventures Inc (CVE:NRM)’s share price reached a new 52-week low on Friday . The company traded as low as C$0.05 and last traded at C$0.05, with a volume of 6000 shares changing hands. The stock had previously closed at C$0.06.
The stock has a market capitalization of $2.42 million and a P/E ratio of -1.25. The business’s 50 day simple moving average is C$0.07 and its two-hundred day simple moving average is C$0.10. The company has a quick ratio of 0.30, a current ratio of 0.36 and a debt-to-equity ratio of 7.93.
About Noram Ventures (CVE:NRM)
Noram Ventures Inc, a junior exploration company, engages in the acquisition, exploration, and development of mineral properties. It explores for lithium and graphite deposits. The company's flagship property is the Zeus Lithium property located in Clayton Valley, Nevada. Noram Ventures Inc was founded in 2010 and is headquartered in Vancouver, Canada.
Featured Story: What is the Hang Seng index?


Number of players:
Start game
You haven't started yet, this will result in an error.
Player 1 has to start
Take coins and card
Coins will be shown here
Total for this card:
______
0


Aramco IPO: Institutional tranche gains $17 bn in orders, says Al Arabiya
The retail portion of the planned deal had received 10 billion riyals, it also said.
by ReutersThe institutional tranche of Saudi Aramco's initial public offering (IPO) has received more than 64 billion riyals ($17.1 billion) in orders, Saudi-owned news channel Al-Arabiya said on Thursday, citing a banking source.
The retail portion of the planned deal had received 10 billion riyals, it also said.
Saudi Aramco plans meetings with investors in Dubai next week, sources previously told Reuters, as it seeks to raise up to $25.6 billion for what it is expected to be the world's biggest share sale.


{% extends "base.html" %} {% load static %} {% block header %} {% endblock %} {% block title %}Cal Day{% endblock %} {% block heading %}Cal Day{% endblock %} {% block content %}
Cal Day is UC Berkeley’s free annual public open house, and HKN will be holding drop-in introductory EECS workshops for campus visitors. In past years, our hands-on workshop projects have included creating a programmable LED array that could flash in different patterns using a MSP430 microcontroller, or a blinking LED controlled by a 555 timer IC chip.
Annual, Spring Semester
Unfortunately, Cal Day has been cancelled this semester as part of campus policies regarding COVID-19.


Request a feature /
Report a bug
jPList - jQuery Data Grid Controls
PHP and MySQL with JSON and Handlebars Templates
jPList Actions
Architecture
Christmas
Nature
Lifestyle
No results found


Dashboard
Records
Manager
Approval
Designer
History
Users
Profiles
Logout
Delete
Mark as unread
Mark as read


Amazon EC2 SpotFleet SpotFleetRequestConfigData
SpotFleetRequestConfigData
is a property of the AWS::EC2::SpotFleet resource
that defines the configuration of a Spot fleet request.
Syntax
JSON
{ "AllocationStrategy" :
String
, "ExcessCapacityTerminationPolicy" :String
, "IamFleetRole" :String
, "InstanceInterruptionBehavior" :String
, "LaunchSpecifications" : [ LaunchSpecifications,...
], "LaunchTemplateConfigs" : [ LaunchTemplateConfigs,...
], "LoadBalancersConfig" : LoadBalancersConfig, "ReplaceUnhealthyInstances" :Boolean
, "SpotPrice" :String
, "TargetCapacity" :Integer
, "TerminateInstancesWithExpiration" :Boolean
, "Type" :String
, "ValidFrom" :String
, "ValidUntil" :String
}
YAML
AllocationStrategy:
String
ExcessCapacityTerminationPolicy:String
IamFleetRole:String
InstanceInterruptionBehavior:String
LaunchSpecifications: - LaunchSpecifications LaunchTemplateConfigs: - LaunchTemplateConfigs LoadBalancersConfig: LoadBalancersConfig ReplaceUnhealthyInstances:Boolean
SpotPrice:String
TargetCapacity:Integer
TerminateInstancesWithExpiration:Boolean
Type:String
ValidFrom:String
ValidUntil:String
Properties
For more information, including property defaults, valid values, and constraints, see SpotFleetRequestConfigData in the Amazon EC2 API Reference.
AllocationStrategy
-
Indicates how to allocate the target capacity across the Spot pools that you specified in the Spot fleet request.
Required: No
Type: String
Update requires: Replacement
ExcessCapacityTerminationPolicy
-
Indicates whether running Spot instances are terminated if you decrease the target capacity of the Spot fleet request below the current size of the Spot fleet.
Required: No
Type: String
Update requires: No interruption
IamFleetRole
-
The Amazon Resource Name (ARN) of an AWS Identity and Access Management (IAM) role that grants the Spot fleet the ability to bid on, launch, and terminate instances on your behalf. For more information, see Spot Fleet Prerequisites in the Amazon EC2 User Guide for Linux Instances.
Required: Yes
Type: String
Update requires: Replacement
InstanceInterruptionBehavior
-
The behavior when a Spot Instance is interrupted.
Required: No
Type: String
Update requires: Replacement
LaunchSpecifications
-
The launch specifications for the Spot fleet request.
Required: Conditional. You must specify either
LaunchSpecifications
orLaunchTemplateConfigs
.Type: List of Amazon Elastic Compute Cloud SpotFleet LaunchSpecifications
Update requires: Replacement
LaunchTemplateConfigs
-
Describes a launch template and overrides.
Required: Conditional. You must specify either
LaunchSpecifications
orLaunchTemplateConfigs
.Type: List of LaunchTemplateConfig
Update requires: Replacement
LoadBalancersConfig
-
One or more Classic Load Balancers and target groups to attach to the Spot Fleet request. Spot Fleet registers the running Spot Instances with the specified Classic Load Balancers and target groups.
Required: No
Type: LoadBalancersConfig
Update requires: Replacement
ReplaceUnhealthyInstances
-
Indicates whether the Spot fleet should replace unhealthy instances.
Required: No
Type: Boolean
Update requires: Replacement
SpotPrice
-
The bid price per unit hour. For more information, see How Spot Fleet Works in the Amazon EC2 User Guide for Linux Instances.
Required: No
Type: String
Update requires: Replacement
TargetCapacity
-
The number of units to request for the spot fleet. You can choose to set the target capacity as the number of instances or as a performance characteristic that is important to your application workload, such as vCPUs, memory, or I/O. For more information, see How Spot Fleet Works in the Amazon EC2 User Guide for Linux Instances.
Required: Yes
Type: Integer
Update requires: No interruption
TerminateInstancesWithExpiration
-
Indicates whether running Spot instances are terminated when the Spot fleet request expires.
Required: No
Type: Boolean
Update requires: Replacement
Type
-
The type of request, which indicates whether the fleet will only request the target capacity or also attempt to maintain it.
Required: No
Type: String
Update requires: Replacement
ValidFrom
-
The start date and time of the request, in UTC format (
YYYY
-MM
-DD
THH
:MM
:SS
Z). By default, Amazon Elastic Compute Cloud (Amazon EC2 ) starts fulfilling the request immediately.Required: No
Type: String
Update requires: Replacement
ValidUntil
-
The end date and time of the request, in UTC format (
YYYY
-MM
-DD
THH
:MM
:SS
Z). After the end date and time, Amazon EC2 doesn't request new Spot instances or enable them to fulfill the request.Required: No
Type: String
Update requires: Replacement


There is a problem
You can invite people to create a new external user account, so they can be added to this live project.
9 Pending invitations
| Name | Role | Email address | |
|---|---|---|---|
You can invite people to create a new external user account, so they can be added to this live project.
9 Pending invitations
| Name | Role | Email address | |
|---|---|---|---|


{% load static %}
AnalysisChoice - SpartanData
SpartanData
Home
Login
Dashboard
Data Analysis Selection
Choose Which Data Analysis Method you Want:
Predictive Anaylsis
Regular Anaylsis