text:
\section{Motivation of Guiding Strategy}

\section{Guiding distribution function in the continuum}

Here we derive the tilted propagator used for importance sampling the driven brownian walker in the main text and discuss the adjoint operator for generating the Langevin dynamics. The Langevin equation that governs the overdamped motion of a particle in the presence of an external force, $F(\theta)$, is given by,
\begin{align}
\partial_t\theta = F(\theta) + \eta
\end{align}
As in the main text, the associated Fokker-Planck equation corresponding to this Langevin equation is
\begin{equation}
\partial_t p_t(\theta) = \mathcal{W}p_t(\theta)
\end{equation}
where $p_t(\theta)$ is the probability of observing the particle at $\theta$ at a time $t$ and
\begin{align}
\label{eq:supp_dbm2}
\mathcal{W} = -\partial_\theta(F-\partial_\theta)
\end{align}
is the Fokker-Planck operator.
We are interested in the large deviation function of the entropy production, $s(t_N)=\sigma(t_N)t_N$, which is proportional to the current around the ring, unwrapped so that winding numbers are included,
\begin{align}
s(t_N) = \int^{t_N}_0 f \dot{\theta}(\tau) d\tau = f\Delta\theta(t_N) \equiv fx
\end{align}
The generating function is related to the probability $p(\theta,s,t_N)$ of finding the particle at $\theta$ with entropy produced $s$ at a time $t_N$ by the Laplace transform,
\begin{align}
\rho(\theta,\lambda,t) = \int ds \, e^{-\lambda s} p(\theta,s,t_N).
\label{eq:supp_dbm1}
\end{align}
Since we are interested in the behavior of probability distribution conditioned on $x$ and $\theta$ and since both of them share the same noise source $\eta$, we expand the Fokker-Planck operator via
$\partial_\theta \rightarrow \partial_\theta + \partial_x$ to obtain:
 \begin{align}
 \tilde{\mathcal{W}} = \mathcal{W} + (2\partial_\theta - F(\theta))\partial_x + \partial^2_x
 \end{align}
and the corresponding modified Fokker-Planck equation is
\begin{align}
\partial_t p(\theta,s,t) =  \tilde{\mathcal{W}}p(\theta,s,t).
\label{eq:supp_dbm3}
\end{align}
By differentiating Eq. \ref{eq:supp_dbm1} with respect to $t$ and inserting Eq. \ref{eq:supp_dbm3} we get
\begin{align}
\partial_t\rho(\theta,\lambda,t) = \int ds e^{-\lambda s} \tilde{\mathcal{W}} p(\theta,s,t).
\end{align}
Now,
\begin{align}
 \int ds e^{-\lambda s} \tilde{\mathcal{W}} p(\theta,s,t)  =  &\int ds e^{-\lambda s} \mathcal{W} p(\theta,s,t) \nonumber\\
 + &\int ds e^{-\lambda s}  (2\partial_\theta - F(\theta))\partial_x p(\theta,s,t) \nonumber\\
 + &\int ds e^{-\lambda s}  \partial^2_x p(\theta,s,t)
 \end{align}
Performing integration by parts we get:
\begin{align}
\partial_t \rho(\theta,\lambda,t)  =  &\mathcal{W} \int ds e^{-\lambda s} p(\theta,s,t) \nonumber\\
 +  &(2\partial_\theta - F(\theta))(f\lambda) \int ds e^{-\lambda s} p(\theta,s,t) \nonumber\\
 +  &(f\lambda)^2 \int ds e^{-\lambda s} p(\theta,s,t) \nonumber\\
= &\mathbb{W}_\lambda \int ds e^{-\lambda s} p(\theta,s,t) = \mathbb{W}_\lambda \rho(\theta,\lambda,t),
\end{align}
where,
\begin{align}\
\label{Eq:Tilted}
{\mathbb{W}}_\lambda = \mathcal{W} + 2 f \lambda \partial_\theta  + f\lambda(f\lambda - F(\theta)),
\end{align}
is the tilted operator given by Eq. 8 in the main text used to obtain the modified or tilted dynamics \cite{Mehl:2008dw}. The mapping of the second-order differential operator
onto a stochastic diffusion process then follows the well-known Feynman-Kac theorem \cite{chetrite2015nonequilibrium}.

Following the general derivation of importance sampling in the main text, we use the specific form of $\mathbb{W}_\lambda$ to get
\begin{align}
\tilde{\Xi} \mathbb{W}_\lambda (\tilde{\Xi}^{-1}\rho) = \rho[\tilde{\Xi} \mathbb{W}_\lambda \tilde{\Xi}^{-1} + \partial_\theta \zeta] - \partial_\theta(\zeta - \partial_\theta)\rho,
\end{align}
with $\zeta = F - 2f\lambda + 2\partial_\theta\ln\tilde{\Xi}$.
The last term corresponds to a Fokker-Planck type of operator with a force term equal to $\zeta$ and can be used to generate trajectories. The first term changes normalization and is, therefore, used for branching. The equation of motion for $\theta$ is obtained from the adjoint operator $\mathcal{W}_\lambda^\dagger$, where,
\begin{align}
\tilde{\Xi}^{-1}\mathbb{W}_\lambda^\dagger\tilde{\Xi} = \tilde{\Xi} \mathbb{W}_\lambda \tilde{\Xi}^{-1} + \partial_\theta \zeta
\end{align}
which follows from integration by parts. The specific form of the branching term following the operators in the main text is given by
\begin{align}
\tilde{\Xi}^{-1}\mathbb{W}_\lambda^\dagger\tilde{\Xi} = \frac{1}{\tilde{\Xi}}\frac{d^2\tilde{\Xi}}{d\theta^2} + (F-2\lambda f)\frac{d \ln \tilde{\Xi}}{d\theta} + f\lambda (f\lambda - F(\theta)),
\end{align}
where $F(\theta) = f-\partial_\theta V(\theta)$, with $f$ a constant, nonconservative force, and $V(\theta) = v_o \cos(\theta)$ is a periodic potential.

As discussed in the text, the exact GDF can be computed by expanding $\tilde{\Xi}$ is plane waves. Specifically, we express
\begin{align}
\tilde{\Xi}(\theta) = \sum_{n=-m}^{m} c_n e^{i n \theta}
\end{align}
and inserting this expansion into eigenvalue relation, and using the tilter operator in Eq.~\ref{Eq:Tilted}, we can derive a recursion relationship for the coefficients $c_n$. This yields,
\begin{eqnarray}
c_n a_n - c_{n-1} b_{-}  - c_{n+1} b_{+}  = c_n \psi(\lambda)
\end{eqnarray}
with elements
$$
a_n =  i n (f+f\lambda )-n^2/2+\lambda f^2+\lambda^2 f^2/2
$$
$$
b_{\pm} = \pm v_o(-i\lambda f+n \pm 1)/2
$$
which specifies a tridiagonal matrix that can be diagonalized using standard techniques suitable for non-Hermitian matrices. In practice, we use $2M+1$ basis functions with $M = 50$ for the exact calculations. The instantonic solution is generated using only 1 basis function. Note that Ref. \cite{Touchette2016} contains an error in the typesetting of the equations defining the expansion coefficients.

\section{Guiding distribution functions from discrete mean-field solutions}

In this section we outline the procedure needed to generate mean-field (MF) and cluster solutions that
form the guiding distribution functions in our discrete models. We will illustrate the procedure for the SEP but it can be easily generalized to other models.

For the open boundary SEP the tilted matrix may be written as:
\begin{align}
\mathbb{W}_\lambda = {w}_L + \sum_{i=1}^{L} {w}_i + {w}_R
\end{align}
where the single particle transition matrices  $\{{w}_L, {w}_i, {w}_R\}$  and their operator representations are given by
\begin{align}
{w}_L &= \left[
\begin{array}{cc}
-\alpha & \gamma e^{\lambda} \\
\alpha e^{-\lambda} & -\gamma \\
\end{array}
\right]
\quad \quad
{w}_R &= \left[
\begin{array}{cc}
-\nu & \beta e^{-\lambda} \\
\nu e^{\lambda} & -\beta \\
\end{array}
\right]
\quad \quad
\end{align}
and
\begin{align}
{w}_i &= \left[
\begin{array}{cccc}
 0 & 0 & 0 & 0\\
 0 & -q & p e^{-\lambda} & 0\\
 0 & qe^{\lambda} & -p & 0\\
 0 & 0 & 0 & 0
\end{array}
\right]
\end{align}

These matrices can be combined to form a many-body matrix that in operator notation is written as\begin{widetext}
\begin{align}
\mathbb{W}_\lambda = &-\alpha(\mathbbm{1}-\hat{n}_1) + \alpha e^{-\lambda} \hat{c}_1^\dagger + \gamma e^{\lambda}\hat{c}_1 -\gamma \hat{n}_1 + pe^{-\lambda}\hat{c}^\dagger_2\hat{c}_1 - p\hat{n}_1(\mathbbm{1}-\hat{n}_2) \nonumber\\
&+ \sum_{i=2}^{L-1} pe^{-\lambda} \hat{c}^\dagger_{i+1}\hat{c}_i - p\hat{n}_i(\mathbbm{1}-\hat{n}_{i+1}) + qe^{\lambda}\hat{c}^\dagger_{i-1}\hat{c}_i - q\hat{n}_i(\mathbbm{1}-\hat{n}_{i-1}) \nonumber\\
&-\nu(\mathbbm{1}-\hat{n}_L) + \nu e^{\lambda} \hat{c}_L^\dagger + \beta e^{-\lambda}\hat{c}_L -\beta \hat{n}_L + qe^{\lambda}\hat{c}^\dagger_{L-1}\hat{c}_L - q\hat{n}_L(\mathbbm{1}-\hat{n}_{L-1}).
\label{eq:SEPM}
\end{align}
\end{widetext}
Here $\hat{c}^\dagger_i$ creates a particle at site $i$, $\hat{c}_j$ destroys a particle at site $j$, and $\hat{n}_i$ counts the number of particles at site $i$. The combined operators $\hat{c}^\dagger_i\hat{c}_j$ correspond to kinetic-like terms that move a particle from site $j$ to $i$, and $\hat{n}_i(\mathbbm{1}-\hat{n}_j)$ represents a hard-core interaction that prevents double occupation of sites. The exact solution is the usual eigenvalue problem ${\mathbb{W}_\lambda}|\Xi\rangle = \varepsilon|\Xi\rangle$ where $(\varepsilon,|\Xi\rangle)$ is a particular eigenpair (the inverse eigenvectors $\{\langle \Xi|\}$ can be constructed from $\{|\Xi\rangle\}$).

An obvious route to explore in constructing approximate GDF is to use a mean-field (MF) solution. The MF approach is to
approximate the many-body state as a product state. Starting with a product of single site states, we can systematically improve our results by moving to products of cluster states, where interactions in the cluster are treated explicitly, while the links between clusters are treated at the MF level. We first illustrate the procedure for single site clusters and then show how to
generalize to multi-site clusters.
\vspace{-10pt}

\subsection{Site-Decoupled Mean-Field and Generalized Variational Approximation}

For the single site clusters we approximate the solution by the form $|\tilde{\Xi}\rangle = \prod_{i=1}^L |\xi_i\rangle$, where the
single site state $|\xi_i\rangle = \sum_{n=0}^1 \xi_i (n) |n_i\rangle$ is written in a basis of occupation numbers $\{|n\rangle\}$. Here $\xi_i(n)$ is a scalar function dependent on the occupation number $n$. One subtlety is that because the tilted matrix is not Hermitian
we must distinguish between approximating its left and its right eigenvector. In this work, we will always approximate
the right eigenvector. The corresponding left eigenvector is then made of the product of left states
$\langle \xi_i| = \sum_{n=0}^1 {\xi}'_i(n) \langle n_i |$, where $\langle \xi_i|$ (and the coefficients $\xi_i'$) can be obtained
from the right states by the biorthogonality condition, $\langle \xi_i|\xi_j \rangle = \delta_{ij}$.
For the following discussion $\{|\tilde{\Xi}\rangle, \langle\tilde{\Xi}|\}$ represents the biorthogonal pair.

To determine the coefficients $\xi_i(n)$, we will use a generalized variational procedure to make the
functional
\begin{align}
\langle\tilde{\Xi}| (\mathbb{W}_\lambda - \varepsilon)|\tilde{\Xi}\rangle \label{eq:bifunctional}
\end{align}
stationary with respect to independent linear
variations in $\langle \tilde{\Xi}|$ and $|\tilde{\Xi\rangle}$. Although stationarity of Eq.~\ref{eq:bifunctional}
does not give a minimum principle, it leads to a mean-field approximation that approximates the right (or left) eigenvector
equation when projected into an appropriate space, similar to the use of collocation to solve a partial differential equation.
For example, considering stationarity with respect to small variations in the left state, we obtain
\begin{align}
  \langle \delta\tilde{\Xi} | \mathbb{W}_\lambda - \varepsilon | \tilde{\Xi}\rangle = 0 \label{eq:varfunc}
  \end{align}
The small variations in the left state take the explicit form
\begin{align}
\langle \delta\tilde{\Xi}| &=
\sum_{i=1}^L \langle \delta \xi_i| \prod_{j\ne i}^L \langle \xi_j| \nonumber\\
&= \sum_{i=1}^L \left[ \sum_{n_i=0}^1 \delta \xi'_i(n)\langle n_i| \right] \prod_{j\ne i}^L\left[\sum_{n_j=0}^1 \xi'_i(n)\langle n_j|\right] \label{eq:varstate}
\end{align}
We then evaluate Eq.~\ref{eq:varfunc} with respect to the specific variations in Eq.~\ref{eq:varstate} to obtain
mean-field equations.
Writing $\mathbb{W}_\lambda = ({\mathcal{W}}_\lambda-{V}_i) + {V}_i$ where ${V}_i$ represents all terms in ${\mathcal{W}}_\lambda$ that contains terms involving site $i$, we obtain the following equation for each $i$:
\begin{align}
\langle \delta \tilde{\Xi}| {V}_i |\tilde{\Xi}\rangle -\epsilon_i \langle\delta {\xi}_i| {\xi}_i\rangle = 0,
\label{eq:mfvareq}
\end{align}
which is equivalent to an eigenvalue equation with eigenvalue $\epsilon_i$,
where we have defined
\begin{align}
\epsilon_i &= \varepsilon - \left[\prod_{j\ne i}\langle {\xi}_j|\right]
(\mathbb{W}_\lambda - {V}_i)
\left[\prod_{k\ne i} | {\xi}_k\rangle\right]
\end{align}
As we are interested in the  maximal eigenvalue/eigenvector pair of $\mathbb{W}_\lambda$, we are interested
in the maximal eigenvalue/eigenvector pair for each site $i$.

For the SEP $\mathbb{W}_\lambda$, Eq. \ref{eq:mfvareq} implies solving the following decoupled eigenvalue equation  for $i = 1$
\begin{align}
&[(-\alpha-q\langle\hat{n}_2\rangle)(\mathbbm{1}-\hat{n}_1)
+ (pe^{-\lambda}\langle\hat{c}^\dagger_2\rangle + \gamma e^{\lambda})\hat{c}_1\nonumber\\
&+ (\alpha e^{-\lambda}  + qe^{\lambda}\langle\hat{c}_2\rangle))\hat{c}_1^\dagger
+ (-\gamma-p(1-\langle\hat{n}_2\rangle))\hat{n}_1] |\xi_1\rangle \nonumber\\
&= \varepsilon_1|\xi_1\rangle
\end{align}
where we have used the shorthand $\langle \ldots \rangle$ to denote the expectation value
$\langle \tilde{\Xi} | \ldots | \tilde{\Xi}\rangle$.
For $i = L$, the eigenvalue equation is
\begin{align}
&[(-\nu-p\langle\hat{n}_{L-1}\rangle)(\mathbbm{1}-\hat{n}_L)
+ (qe^{\lambda}\langle\hat{c}^\dagger_{L-1}\rangle + \beta e^{-\lambda})\hat{c}_{L-1}\nonumber\\
&+ (\nu e^{\lambda}  + pe^{-\lambda}\langle\hat{c}_{L-1}\rangle))\hat{c}_L^\dagger
+ (-\beta-q(1-\langle\hat{n}_{L-1}\rangle))\hat{n}_L] |\xi_L\rangle \nonumber\\
&= \varepsilon_L|\xi_L\rangle
\end{align}
Finally for all other $i$, the eigenvalue equation is
\begin{align}
&[(-p\langle\hat{n}_{i-1}\rangle - q\langle\hat{n}_{i+1}\rangle)(\mathbbm{1}-\hat{n}_i) \nonumber\\
&+(pe^{-\lambda}\langle\hat{c}^\dagger_{i+1}\rangle + qe^{\lambda}\langle\hat{c}^\dagger_{i-1}\rangle)\hat{c}_{i}\nonumber\\
&+ (qe^{\lambda}\langle\hat{c}_{i+1}\rangle + pe^{-\lambda}\langle\hat{c}_{i-1}\rangle)\hat{c}_{i}^\dagger \nonumber\\
&+ (-p(1-\langle\hat{n}_{i+1}\rangle)-q(1-\langle\hat{n}_{i-1}\rangle))\hat{n}_i] |\xi_i\rangle \nonumber\\
&= \varepsilon_i|\xi_i\rangle \, .
\end{align}

The maximal eigenvalue/eigenvector pair approximation can be obtained by solving the above equations for each site $i$ and choosing the set of states $\{|\xi_i\rangle\}$ corresponding to the largest eigenvalues $\{\epsilon_i\}$. Notice that even when collecting terms involving site $i$, there will inevitably be terms involving other sites due to the two-body interaction present in the matrix (\ref{eq:SEPM}). The natural way to solve this system, thus, requires the use of a self-consistent procedure. We start with an initial set of guess values for $\langle \hat{n}_i\rangle$, $\langle \hat{c}_i\rangle$ and $\langle \hat{c}^\dagger_i\rangle$ and proceed to solve the individual eigenvalue problems for each site. At the end of each iteration we use the states $\{|\xi_i\rangle\}$ to recompute $\langle \hat{n}_i\rangle$, $\langle \hat{c}_i\rangle$, and  $\langle \hat{c}^\dagger_i\rangle$ and use them for the next iteration. This is continued until $\{\langle \hat{n}_i\rangle, \langle \hat{c}_i\rangle, \langle \hat{c}^\dagger_i\rangle\}$ do not change.\\

Once the solutions have converged it is straightforward to obtain the MF estimate of the LDF, $\epsilon(\lambda) = \langle \tilde{\Xi} | \mathbb{W}_\lambda | \tilde{\Xi} \rangle$. The MF approximation to the state $\langle\tilde{\Xi}|$ is precisely the GDF that we need to construct the auxiliary process that will importance sample the LDF. The effective matrices incorporating the importance sampling are:

\begin{align}
\tilde{w}_L &= \left[
\begin{array}{cc}
-\alpha & \gamma e^{\lambda} \frac{\xi_1(0)}{\xi_1(1)}\\
\alpha e^{-\lambda} \frac{\xi_1(1)}{\xi_1(0)} & -\gamma \\
\end{array}
\right]
\end{align}

\begin{align}
\tilde{w}_i &= \left[
\begin{array}{cccc}
 0 & 0 & 0 & 0\\
 0 & -q & p e^{-\lambda} \frac{\xi_i(0) \xi_{i+1}(1)}{\xi_i(1) \xi_{i+1}(0)}& 0\\
 0 & qe^{\lambda} \frac{\xi_{i-1}(1) \xi_i(0)}{\xi_{i-1}(0) \xi_i(1)} & -p & 0\\
 0 & 0 & 0 & 0
\end{array}
\right]
\end{align}

\begin{align}
\tilde{w}_R &= \left[
\begin{array}{cc}
-\nu & \beta e^{-\lambda} \frac{\xi_{L}(0)}{\xi_{L}(1)}\\
\nu e^{\lambda} \frac{\xi_{L}(1)}{\xi_{L}(0)} & -\beta \\
\end{array}
\right]
\end{align}
Notice that these are not normalized and their renormalization determines the branching weights.
In the text, we use a first order Trotterization on the short-time importance-sampled propagator ($\langle \tilde{\Xi}| e^{dt\mathbb{W}_\lambda} |\tilde{\Xi}\rangle$) to obtain the Markovian transition probability matrix $\tilde{\mathbb{U}}_\lambda \equiv \mathbbm{1} + dt\langle \tilde{\Xi}| \mathbb{W}_\lambda  |\tilde{\Xi}\rangle$.
Therefore, $\tilde{\mathbb{U}}_\lambda$ follows directly from the transformed components of $\mathbb{W}_
\lambda$, and is given by
\begin{align}
\tilde{\mathbb{U}}_\lambda = \tilde{u}_L + \sum_{i=1}^{L} \tilde{u}_i + \tilde{u}_R,
\end{align}
where,
\begin{align}
\tilde{u}_L &= \left[
\begin{array}{cc}
1-\alpha dt & \gamma e^{\lambda} \frac{\xi_1(0)}{\xi_1(1)}\\
\alpha e^{-\lambda} \frac{\xi_1(1)}{\xi_1(0)} & 1-\gamma dt \\
\end{array}
\right]
\label{su:eq1}
\end{align}

\begin{align}
\tilde{u}_i &= \left[
\begin{array}{cccc}
1 & 0 & 0 & 0\\
 0 & 1-qdt & p e^{-\lambda} \frac{\xi_i(0) \xi_{i+1}(1)}{\xi_i(1) \xi_{i+1}(0)}& 0\\
 0 & qe^{\lambda} \frac{\xi_{i-1}(1) \xi_i(0)}{\xi_{i-1}(0) \xi_i(1)} & 1-pdt & 0\\
 0 & 0 & 0 & 1
\end{array}
\right]
\label{su:eq2}
\end{align}

\begin{align}
\tilde{u}_R &= \left[
\begin{array}{cc}
1-\nu dt & \beta e^{-\lambda} \frac{\xi_{L}(0)}{\xi_{L}(1)}\\
\nu e^{\lambda} \frac{\xi_{L}(1)}{\xi_{L}(0)} & 1-\beta dt \\
\end{array}
\right]
\label{su:eq3}
\end{align}
are the associated transition probabilities at the ends of the lattice, $\tilde{u}_L$ and $\tilde{u}_R$, or in its interior, $\tilde{u}_i$.
At every time step or Monte Carlo sweep, the current state $|\mathcal{C}\rangle = |n_1 n_2 ... n_L\rangle$ that corresponds to a column of $\tilde{\mathbb{U}}_\lambda$ is used to propose moves such that the outgoing state $|\mathcal{C}'\rangle$ has the probability $\tilde{\mathbb{U}}_\lambda(\mathcal{C}',\mathcal{C}) /\mathcal{N}(C)$ of being accepted, where $\mathcal{N}(C) \equiv \sum_{\mathcal{C'}} \tilde{\mathbb{U}}_\lambda(\mathcal{C}',\mathcal{C})$ is the normalization factor. Over the course of the short trajectory generated in between branching steps, a walker's weight is accumulated as a product of these normalization factors.\\

\subsection{Cluster Approach}
The idea of a site-decoupled mean-field can be extended to multiple sites collected into clusters. The MF ansatz is
then $|\tilde{\Xi}\rangle = \prod^{L/c_L}_{c=1} |\xi_c\rangle$
where $c_L$ is the number of sites that constitutes a cluster. $|\xi_c\rangle$
is expanded in the occupation basis of the cluster
$|\xi_c\rangle = \sum_{\{n\}} \xi_c(n_{(c-1)c_L+1},...,n_{cc_L})|n_{(c-1)c_L+1},...,n_{cc_L}\rangle$.
For each cluster $(c)$, we can write down the analogous $V_i$ operator
which contains all terms in Eq.~\ref{eq:SEPM} that involve sites in the cluster ($V_c$).
All terms involving only sites inside the given cluster are treated exactly (i.e. treated as operators)
while terms that involve sites that are inside two different clusters are split up via the MF approximation $\hat{A}_i \hat{B}_j \sim \langle \hat{A}_i \rangle \hat{B}_j + \hat{A}_i \langle \hat{B}_j \rangle - \langle \hat{A}_i \rangle \langle \hat{B}_j \rangle$, where as before $\langle \hat{A}_i \rangle$ and $\langle \hat{B}_j \rangle$ are determined self-consistently.

More explicitly, the mean-field cluster $V_c$ operator is
\begin{widetext}
\begin{align}
{V_c} &=  \hat{L}(j = c_L(c-1)+1) + \hat{R}(j = c_Lc-1) \nonumber\\
&+ \sum_{j=c_L(c-1)+1}^{c_Lc-1} pe^{-\lambda} \hat{c}^\dagger_{j+1}\hat{c}_j - p\hat{n}_j(\mathbbm{1}-\hat{n}_{j+1}) + qe^{\lambda}\hat{c}^\dagger_{j}\hat{c}_{j+1} - q\hat{n}_{j+1}(\mathbbm{1}-\hat{n}_{j}) \\
\text{where} \nonumber\\
\hat{L}(j) &= -p\langle \hat{n}_{j-1}\rangle(\mathbbm{1}-\hat{n}_{j}) + qe^{\lambda} \langle \hat{c}^\dagger_{j-1} \rangle \hat{c}_{j} + pe^{-\lambda} \langle \hat{c}_{j-1} \rangle \hat{c}^\dagger_{j}-q\hat{n}_{j}(1-\langle \hat{n}_{j-1}\rangle ) \quad&\text{ for } c > 1 \nonumber\\
\hat{L}(j) &= -\alpha(\mathbbm{1}-\hat{n}_1) + \alpha e^{-\lambda} \hat{c}_1^\dagger + \gamma e^{\lambda}\hat{c}_1 -\gamma \hat{n}_1  \quad&\text{ for } c = 1 \nonumber\\
\hat{R}(j) &= -q\langle \hat{n}_{j+1}\rangle(\mathbbm{1}-\hat{n}_{j}) + pe^{-\lambda} \langle \hat{c}^\dagger_{j+1} \rangle \hat{c}_{j} + qe^{\lambda} \langle \hat{c}_{j+1} \rangle \hat{c}^\dagger_{j}-p\hat{n}_{j}(1-\langle \hat{n}_{j+1}\rangle ) \quad&\text{ for } c < L/c_L%
\nonumber\\
\hat{R}(j) &= -\nu(\mathbbm{1}-\hat{n}_L) + \nu e^{\lambda} \hat{c}_L^\dagger + \beta e^{-\lambda}\hat{c}_L -\beta \hat{n}_L \quad&\text{ for } c = L/c_L\nonumber
\end{align}
\end{widetext}
This treatment ensures that all cluster based eigenvalue problems can be solved separately
using only expectation values to estimate the couplings between clusters. The latter couplings are calculated separately at the end of each self-consistent step. This is continued until the averages do not change. Once the MF calculations converge we will obtain the required GDF $\langle \tilde{\Xi}|$ needed to construct the generator of auxiliary dynamics, similar to the case for the single site MF. However, now the $\xi_c(n_{(c-1)c_L+1},...,n_{cc_L})$ involve multiple sites and thus the proposal matrix must be updated accordingly to distinguish between inter- and intra- cluster states. For instance, for a cluster of size $c_L = 2$ the intra-cluster hopping matrix for hops within a cluster is given by,
\begin{align}
\tilde{u}_c &= \left[
\begin{array}{cccc}
1 & 0 & 0 & 0\\
 0 & 1-qdt & p e^{-\lambda} \frac{\xi_c(0,1)}{\xi_c(1,0)}& 0\\
 0 & qe^{\lambda} \frac{\xi_{c}(1,0)}{\xi_{c}(0,1)} & 1-pdt & 0\\
 0 & 0 & 0 & 1
\end{array}
\right]
\label{scu:eq1}
\end{align}
For inter-cluster hopping the two matrices $\tilde{u}_{c}$ and $\tilde{u}_{c+1}$ must be combined and the hopping between edge sites $n_{cc_L}$ and $n_{(c)c_L+1}$ will depend on the state configuration of the two clusters. For e.g. the transition matrix elements given by $P(n_{cc_L-1}, n_{cc_L}; n_{cc_L+1},n_{cc_L+2} \rightarrow
n_{cc_L-1}, n_{cc_L}; n_{cc_L+1},n_{cc_L+2})$ are:
\begin{align}
P(i, 0; 0,j \rightarrow i, 0; 0,j) &= 1 \nonumber\\
P(i, 1; 0,j \rightarrow i, 0; 1,j) &= pe^{-\lambda} \frac{\xi_c(i,0)\xi_{c+1}(1,j)}{\xi_c(i,1)\xi_{c+1}(0,j)} \nonumber\\
P(i, 1; 0,j \rightarrow i, 1; 0,j) &= 1 - pdt \nonumber\\
P(i, 0; 1,j \rightarrow i, 1; 0,j) &= qe^{\lambda} \frac{\xi_c(i,1)\xi_{c+1}(0,j)}{\xi_c(i,0)\xi_{c+1}(1,j)} \nonumber\\
P(i, 0; 1,j \rightarrow i, 0; 1,j) &= 1 - qdt \nonumber\\
P(i, 1; 1,j \rightarrow i, 1; 1,j) &= 1
\end{align}
This can be generalized to other cluster sizes.

\subsection{2D Cluster Approximation}
For the 2D WASEP problem that we consider in the main text, the cluster approach outlined above for 1D systems can be generalized to 2D. The tilted operator for this problem is given by,
\begin{widetext}
\vspace{-10pt}
\begin{align}
\mathbb{W}_{\lambda_x,\lambda_y} = \sum_{i=1}^{L_x}\sum_{j=1}^{L_y} & p_x e^{-\lambda_x} \hat{c}^\dagger_{i+1,j}\hat{c}_{i,j} - p_x\hat{n}_{i,j}(\mathbbm{1}-\hat{n}_{i+1,j}) + q_xe^{\lambda_x}\hat{c}^\dagger_{i-1,j}\hat{c}_{i,j} - q_x\hat{n}_{i,j}(\mathbbm{1}-\hat{n}_{i-1,j}) \nonumber\\
& p_y e^{-\lambda_y} \hat{c}^\dagger_{i,j+1}\hat{c}_{i,j} - p_y\hat{n}_{i,j}(\mathbbm{1}-\hat{n}_{i,j+1}) + q_ye^{\lambda_y}\hat{c}^\dagger_{i,j-1}\hat{c}_{i,j} - q_y\hat{n}_{i,j}(\mathbbm{1}-\hat{n}_{i,j-1}),
\label{eq:WASEP}
\end{align}
\end{widetext}
where $p_x, q_x, p_y, q_y$ are transition rates associated with hopping along $\pm x, \pm y$ directions. Additionally for this model we use periodic boundary conditions. Here, $(L_x,L_y)$ are the number of sites in the respective directions. Notice that the biasing parameter is a vector $\bm{\lambda} = (\lambda_x,\lambda_y)$. Additionally to accommodate the extra dimension, operators are now indexed via the coordinates $(i,j)$. Much like the 1D case the MF solutions can be constructed as before except now the coupling terms are defined for the perimeter of the cluster at $(c_x,c_y)$. Suppose there are $(c_L^x,c_L^y)$ sites per cluster; then in explicit terms the cluster MF tilted operator $V_{c_x,c_y}$ is given by:
\begin{widetext}
\vspace{-20pt}
\begin{align}
V_{c_x,c_y} = \sum_{\substack{i=c_L^x(c_x-1)+1\\ j=c_L^y(c_y-1)+1}}^{\substack{c_L^xc_x-1, c_L^yc_y-1}}  &  p_x e^{-\lambda_x} \hat{c}^\dagger_{i+1,j}\hat{c}_{i,j} - p_x\hat{n}_{i,j}(\mathbbm{1}-\hat{n}_{i+1,j}) + q_xe^{\lambda_x}\hat{c}^\dagger_{i,j}\hat{c}_{i+1,j} - q_x\hat{n}_{i+1,j}(\mathbbm{1}-\hat{n}_{i,j}) \nonumber\\
 & + p_y e^{-\lambda_y} \hat{c}^\dagger_{i,j+1}\hat{c}_{i,j} - p_y\hat{n}_{i,j}(\mathbbm{1}-\hat{n}_{i,j+1}) + q_ye^{\lambda_y}\hat{c}^\dagger_{i,j}\hat{c}_{i,j+1} - q_y\hat{n}_{i,j+1}(\mathbbm{1}-\hat{n}_{i,j}) \nonumber\\
  + \hat{L}(i = (c_x-&1)c_L^x+1,c_y) + \hat{R}(i = c_xc_L^x,c_y) + \hat{T}(c_x, j = c_y c_L^y) + \hat{B}(c_x,j = (c_y-1)c_L^y+1) \nonumber\\
\end{align}
\vspace{-20pt}
\end{widetext}
\begin{widetext}
where
\begin{align}
\hat{L}(i,c_y) &= \sum_{j=c_L^y(c_y-1)+1}^{c_L^yc_y-1}
p_x e^{-\lambda_x} \hat{c}^\dagger_{i,j}\langle\hat{c}_{i-1,j}\rangle - p_x\langle\hat{n}_{i-1,j}\rangle(\mathbbm{1}-\hat{n}_{i,j}) +
q_xe^{\lambda_x}\langle\hat{c}^\dagger_{i-1,j}\rangle\hat{c}_{i,j} - q_x\hat{n}_{i,j}(\mathbbm{1}-\langle\hat{n}_{i-1,j}\rangle) \nonumber
\end{align}
\begin{align}
\hat{R}(i,c_y) &= \sum_{j=c_L^y(c_y-1)+1}^{c_L^yc_y-1}
p_x e^{-\lambda_x} \langle\hat{c}^\dagger_{i+1,j}\rangle\hat{c}_{i,j} - p_x \hat{n}_{i,j}(\mathbbm{1}-\langle\hat{n}_{i+1,j}\rangle) +
q_xe^{\lambda_x}\hat{c}^\dagger_{i,j}\langle\hat{c}_{i+1,j}\rangle - q_x\langle\hat{n}_{i+1,j}\rangle(\mathbbm{1}-\hat{n}_{i,j}) \nonumber\\
\hat{B}(c_x,j) &= \sum_{i=c_L^x(c_x-1)+1}^{c_L^xc_x-1}
p_y e^{-\lambda_y} \hat{c}^\dagger_{i,j}\langle\hat{c}_{i,j-1}\rangle - p_y\langle\hat{n}_{i,j-1}\rangle(\mathbbm{1}-\hat{n}_{i,j}) +
q_ye^{\lambda_y}\langle\hat{c}^\dagger_{i,j-1}\rangle\hat{c}_{i,j} - q_y\hat{n}_{i,j}(\mathbbm{1}-\langle\hat{n}_{i,j-1}\rangle) \nonumber\\
\hat{T}(c_x,j) &= \sum_{i=c_L^x(c_x-1)+1}^{c_L^yc_x-1}
p_y e^{-\lambda_y} \langle\hat{c}^\dagger_{i,j+1}\rangle\hat{c}_{i,j} - p_y \hat{n}_{i,j}(\mathbbm{1}-\langle\hat{n}_{i,j+1}\rangle) +
q_ye^{\lambda_y}\hat{c}^\dagger_{i,j}\langle\hat{c}_{i,j+1}\rangle - q_y\langle\hat{n}_{i,j+1}\rangle(\mathbbm{1}-\hat{n}_{i,j}) \nonumber
\end{align}
\end{widetext}
The operators $\hat{L}$, $\hat{R}$, $\hat{B}$ and $\hat{T}$ are the border terms for the cluster at $(c_x,c_y)$. They contain the mean-field coupling parameters that are enclosed with $\langle ... \rangle$. These are determined self-consistently much as in the 1D case. Finally the determined cluster states can then be used to construct the transformed tilted operator from which moves can be proposed.

\section{Calculation details for results in the main text}
\begin{figure}[b]
\begin{center}
\includegraphics[width=8.5cm]{FigS1.pdf}
\caption{Convergence of the 2D SEP DMC simulations with integration time step for $\lambda=-6$.}
\label{Fi:1}
\end{center}
\vspace{-20pt}
\end{figure}

\begin{figure}[b]
\begin{center}
\includegraphics[width=8.5cm]{FigS3.pdf}
\caption{Systematic error associated with walker population for 2D SEP DMC simulations for the large deviation function. Shown in red are the results for no importance sampling and in blue the results of the cluster GDF. Both were computed at $\lambda = -5.0$.}
\label{Fi:2}
\end{center}
\vspace{-20pt}
\end{figure}

\begin{figure}[b]
\begin{center}
\includegraphics[width=8.cm]{FigS2.pdf}
\caption{Fraction of independent walkers $f_I(t)$ as a function of simulation time for $\lambda = -5.0$ using GDF (blue) and not using GDF (red). Inset shows the ratio of fraction of independent walkers with GDF and without as a function of time.}
\label{Fi:3}
\end{center}
\vspace{-20pt}
\end{figure}

\emph{Driven brownian motion}: All of the calculations on the driven brownian walker were accomplished with a second order stochastic Runge-Kutta integrator with a timestep of 0.01. Observation times of 20.0 were needed to converge the calculations and branching steps attempted every 0.05 unit of time.\\

\emph{1D SEP}: For the 1D system consisting of $L = 8$ sites, clusters were made using $c_L = 1,2,4$ sites. All calculations were done using $N_{\mathrm{w}} = 2\times 10^4$ walkers, with a time step $dt = 0.001$, observation time $t_N = 1$ with branching occurring at intervals of time $t_\mathrm{int} = 0.01$. In the main text, we have used calculations done with cluster size of $0$ (``zeroth-order'' MF) to indicate a sampling strategy where the exponential $e^{-\lambda\mathcal{O}}$ has been absorbed directly into the proposed Monte Carlo moves. This essentially means $\xi_i = 1$ for equations \ref{su:eq1}-\ref{su:eq3}. We note that this last way of sampling should always be used if no higher order MF solutions are available. For the 2D WASEP system we discuss next, the bare sampling strategy is to at least use a zeroth-order MF. Generating trajectories from the unbiased distribution, i.e., without directly incorporating the exponential in the proposed Monte Carlo moves makes it impossible to converge calculations for the range of $\lambda$ we explore and the number of walkers we deploy.\\

\emph{2D WASEP}: The 2D WASEP system discussed in the main text is a generalization of the 1D model to an $L\times L$ lattice with  periodic boundary conditions. Along the principal direction, $x$, particles are subject to  biased hopping rates that are scaled by the length of the system $p_x = e^{-E/L_x}/2$ along $x$ and $q_x = e^{E/L_x}/2$ along $-x$ with $L_x = 12$ and $E = 10$. Along the $y$ direction particles diffuse symmetrically, with rates $p_y = q_y = 0.5$ \cite{tizon2016order}. These calculations are resource intensive so a careful study of convergence and statistical properties is needed to be able to compute the susceptibility $\chi(\lambda)$.

Towards this end we determine the time step error associated with Trotterization as shown in Fig. \ref{Fi:1} for the largest $\lambda$ value that we wish to access, since this sets the upper-bound on the error. We find that $dt = 0.001$ is sufficient to converge the error.

The second major source of error in these calculations is the systematic error due to finite walker population. Since the variance grows exponentially with $|\lambda|$ \cite{ray2017importance}, it is sufficient to determine the largest number of walkers needed for maximal $|\lambda|$ we use in our simulations. Fig. \ref{Fi:2} shows the convergence of $\psi(\lambda)$ with $N_{\mathrm{w}}$ for $\lambda = -5.0$ both using and not using importance sampling. It is evident that using auxiliary dynamics, even with $N_{\mathrm{w}} = 5\times 10^5$ our results would have been sufficiently converged. Comparing against calculations without auxiliary dynamics we have $\sim 4$-fold increase in efficiency mirroring the ratio of independent walkers of Fig. 3c in the main text. Despite the mean field GDF employed for this model not being particularly good at large $|\lambda|$, as the traveling wave state is not well described by a small single cluster, we still get a factor of 2-4 reduction in the required number of walkers to converge results (c.f. Fig. 3c in main text).

Following this analysis, we used $N_{\mathrm{w}} = 5\times 10^5$ walkers for $\lambda \le -3.0$ with $t_N = 100$ where branching was done every $t_\mathrm{int} = 0.01$.
For $\lambda > -3.0$ simulations used $N_{\mathrm{w}} = 10^6$ walkers with $t_N = 72$ and $t_\mathrm{int} = 1.4$. In Fig. 3c of the main text the ratio of independent clones was determined using independent clone counts at time $t = 0.32t_N$.
Fig. \ref{Fi:3} shows a comparison of the fraction of independent walkers, $f_\mathrm{I}(t)$, along the entire $t_N$ trajectory for $\lambda = -5.0$. It highlights the importance of using GDF for sampling purposes to ensure that that there are enough uncorrelated contributions to the estimator.

\section{Connection with the iterative feedback method of Nemoto et al}

In their work, Nemoto et al. have outlined an iterative feedback control algorithm by which they attempt to construct a potential to affect an importance sampling of the large deviation function\cite{Takahiro2016,nemoto2017finite}. These papers illustrate their method via two models: diffusion of a particle in a quartic potential and the FA model\cite{fredrickson1984kinetic}. The basic idea in the context of a lattice model is to modify the transition rate $w(\mathcal{C}\rightarrow\mathcal{F}[\mathcal{C}])$ between configurations $\mathcal{C}$ and $\mathcal{F}[\mathcal{C}] $ via a auxilary potential $U(\mathcal{C})$ as
\begin{align}
\tilde{w}(\mathcal{C}\rightarrow\mathcal{F}[\mathcal{C}]) = e^{-\lambda}w(\mathcal{C}\rightarrow\mathcal{F}[\mathcal{C}])e^{\frac{1}{2}[U(\mathcal{C})-U(\mathcal{F}[\mathcal{C}])]}.
\end{align}
where they biased on the activity, or number of configurational changes.
Here $\mathcal{F}[\mathcal{C}]$ is a function that maps the current configuration $\mathcal{C}$ to a new configuration and $\lambda$ is a counting field conjugate to the activity. Typically Nemoto et al. parametrize $U(\mathcal{C})$ iteratively using the criteria that in the optimum Doob transformed dynamics the distribution of order parameter values computed over the full simulation time -- the ``average distribution" and those constructed from the final ``end distribution" must be identical. Of the models they consider the more complicated many-particle-interacting simulations for the FA case is done by setting $U(\mathcal{C})-U(\mathcal{F}_i[\mathcal{C}]) \equiv u_d(n_{i-d},...,n_i,...,n_{i+d})$. Here $\mathcal{F}_i$ simply constitutes a spin-flip on site $i$ and $\mathcal{C}$ represents a 1D lattice of spins.

Nemoto et al. alluded to the relationship between their

 potential and the dominant left eigenvector of the tilted operator, but did not give an explicit expression. From the formalism presented in the text it is evident that
\begin{align}
e^{\frac{1}{2}[U(\mathcal{C})-U(\mathcal{F}[\mathcal{C}])]} = \frac{\tilde{\Xi}(\mathcal{F}[\mathcal{C}])}{\tilde{\Xi}(\mathcal{C})},
\end{align}
where $\tilde{\Xi}(\mathcal{C})$ is the GDF obtained by approximating the left eigenvector of the tilted operator, as we have  discussed in the main text. This connection  simplifies
the importance sampling in the sense that GDFs with larger overlap with the exact left eigenvector of the tilted operator immediately
lead to better sampling. The iterative mechanism outlined by Nemoto et al. may be seen as an analog of the variation of parameters
needed to determine a parametrized GDF. However, since the variational determination of the GDFs is carried out outside of the dynamics itself, we expect it
to be numerically less intensive in most situations than the iterative feedback algorithm.


text:
\section*{The Input: the Sequences $S_{k,l}^{(z)}(n)$}

Recall that a {\it Young  Shape} (alias {\it Ferrers diagram}) $\lambda=(\lambda_1, \lambda_2, \dots )$
is an arrangement of
left-justified  rows of boxes, with $\lambda_1$ boxes in the first row,
$\lambda_2$ boxes in the second row, etc. If the total number of boxes is $n$, we write
$\lambda \vdash n$.

The set of shapes $\lambda$ with $n$ cells with the property that $\lambda_{k+1} \leq l$ is denoted
by $H(k,l;n)$.

Recall also that a {\it Standard Young Tableau} (SYT) of shape $\lambda \vdash n$ is any way of placing the
integers from $1$ to $n$ inside the $n$ boxes in such a way that all rows and all columns are increasing.
There is a well-known, explicit, formula for $f^{\lambda}$, the number of SYTs of a given shape $\lambda$,
due to Young and Frobenius, as well as a more elegant reformulation, called the
hook-length formula, due to Frame, Robinson, and Thrall.

In \cite{BR}, Regev and Berele studied
the sequences
$$
S_{k,l}^{(z)}(n)=
\sum_{\lambda \in H(k,l;n)} (f^{\lambda})^{z} \quad ,
$$
and obtained explicit leading asymptotics for {\it general} $(k,l)$
as well as general (real) $z$.

Except for $(k,l) \in \{ (1,0),(2,0),(4,0),(1,1)\}$ (when $z=1$)
and $(k,l) \in \{ (1,0),(2,0),(1,1), (\infty, \infty) \}$ (for $z=2$),
there are no known ``nice'' expressions for $S_{k,l}^{(z)}(n)$ in terms
of $n$. Of course, using the Young-Frobenius formula one can always
express it as a {\it multi-sum} of hypergeometric terms, but, in general
with $k+l-1$  sigma signs.

 The next best thing to a closed-form formula is a {\it linear recurrence}.
It follows from the Fundamental Theorem of Wilf-Zeilberger theory (\cite{WilZ})
that for any specific $(k,l)$ and {\it positive integer} $z$, the sequence
$A(n)=S_{k,l}^{(z)}(n)$ is {\it holonomic} (alias $P$-recursive), in other words it satisfies
a (homogeneous) linear recurrence equation with {\it polynomial} coefficients. This
means that there exists a positive integer $L$, and polynomials $p_0(n), \dots, p_L(n)$ such that
$$
\sum_{i=0}^{L} p_i(n) A(n+i) =0 \quad , \quad n \geq  0 \quad .
$$

Furthermore there exist algorithms for computing these recurrences, but they are rather slow for
multi-sums.

Since we know {\it a priori} that such a recurrence exists, we may just as well find it {\it empirically}
by asking the computer to compute the first $60$ (or whatever) terms and then
guess the recurrence by {\it undetermined coefficients}. This is done by the command
{\tt listtorec} in Bruno Salvy and Paul Zimmermann's Maple package {\tt gfun}
(but we prefer to have our own version).

While there is a ``theoretical'' possibility that the guessed recurrence is not the ``right'' one,
this is very unlikely, and besides, using the recurrence one can extend the sequence very fast,
and check whether the continuation matches, and if it does
(say for the next $20$ terms), then
this is a {\it semi-rigorous} proof, good enough for us. We know that we have the {\it option} to
find a fully rigorous proof by the {\it multivariable Zeilberger algorithm} \cite{AT}
(that alas, will take much longer, and for larger $(k,l)$ may not terminate in a reasonable
amount of time) but {\it why bother?}.

The beauty of knowing a linear recurrence is that one can use the  Poincar\'e-Birkhoff-Trjitzinsky
method to derive higher-order asymptotics for the sequence. This method, described in \cite{WimZ},
is fully implemented in Doron Zeilberger's Maple package

\verb|http://www.math.rutgers.edu/~zeilberg/tokhniot/AsyRec| \quad .

The drawback of that method is that it does not output the {\it constant} factor,
that must be determined empirically, in general. Luckily,
thanks to \cite{BR}, we know
that constant exactly (expressed in terms of $\pi$), and this enables the computation
of very refined asymptotics of the sequences
$S_{k,l}^{(z)}(n)$ for the most interesting cases $z=1$ and $z=2$, and for
$k+l \leq 5$.

\section*{The Output: Recurrences and asymptotics for $S_{k,l}^{(1)}(n)$ and $S_{k,l}^{(2)}(n)$
for $k+l \leq 5$}

All the necessary algorithms have been implemented in the self-contained Maple package
{\tt HOOKER}, kindly written by Doron Zeilberger,
and available from

\verb|http://www.math.rutgers.edu/~zeilberg/tokhniot/HOOKER| \quad .

\bigskip

Detailed output files, with lots of terms in the sequences, and asymptotics to order $10$, can be viewed in the webpage of this article:

\verb|http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/hooker.html| \quad .

Here we only list (for the record)
the output for $(k,l) \in \{(2,1),(2,2)\}$ and $z=1,2$, and even for these, we only list the
first few terms, the annihilating operator and the refined asymptotics to order 3.

Below $N$ denotes the shift-operator in $n$, so, for example, the annihilating operator for
the Fibonacci sequence is $N^2-N-1$ and for $n!$ is $N-n-1$.

{\bf $(k,l)=(2,1)$, $z=1$}

$$
1, 2, 4, 10, 26, 71, 197, 554, 1570, 4477, 12827, 36895, 106471, 308114, 893804, 2598314, 7567466, 22076405,
$$
$$
64498427, 188689685
$$
$$
3\,{\frac {n+2}{n+3}}-{\frac {n \left( n+2 \right) N}{ \left( n+3 \right)  \left( n+1 \right) }}-{\frac { \left( 9+11\,n+3\,{n}^{2} \right) {N}^{2}}{
 \left( n+3 \right)  \left( n+1 \right) }}+{N}^{3}
$$

$$
1/4\,{3}^{n}\sqrt {{n}^{-1}} \left( 1-3/16\,{n}^{-1}+{\frac {1}{512}}\,{n}^{-2}+{\frac {135}{8192}}\,{n}^{-3} \right) \sqrt {3}{\frac {1}{\sqrt {\pi }}}
$$

{\bf $(k,l)=(2,1)$, $z=2$}

$$
1, 2, 6, 24, 120, 695, 4403, 29540, 206244, 1483371, 10919271, 81896661, 623810421,
$$
$$
4813777566, 37561178658, 295907998908, 2350767037116
$$
$$
-9\,{\frac { \left( n+2 \right) ^{2}}{ \left( n+3 \right) ^{2}}}+{\frac { \left( 19\,{n}^{2}+40\,n+18 \right)  \left( n+2 \right) ^{2}N}{ \left( n+3
 \right) ^{2}
\left( n+1 \right) ^{2}}}
$$
$$
-{\frac { \left( 45+148\,n+159\,{n}^{2}+70\,{n}^{3}+11\,{n}^{4} \right) {N}^{2}}{ \left( n+3 \right) ^{2} \left( n+1
 \right) ^{2}}}+{N}^{3}
$$

$$
{\frac {9}{128}}\,{9}^{n} \left( 1+3/4\,{n}^{-1}+{\frac {53}{32}}\,{n}^{-2}+{\frac {261}{64}}\,{n}^{-3} \right) \sqrt {3}{n}^{-2}{\pi }^{-1}
$$

{\bf $(k,l)=(2,2)$, $z=1$}

$$
1, 2, 4, 10, 26, 76, 232, 764, 2578, 9076, 32264, 117448, 428936, 1589680, 5897504, 22101304, 82851218,
$$
$$
312935236, 1182083272, 4491680504, 17067914056, 65167445872
$$

$$
128\,{\frac {n \left( n-1 \right) }{ \left( n+5 \right)  \left( n+4 \right) }}-32\,{\frac { \left( -1+4\,n+6\,{n}^{2} \right) N}{ \left( n+5 \right)
 \left( n+4 \right) }}+
$$
$$
8\,{\frac { \left( 4+21\,n+11\,{n}^{2} \right) {N}^{2}}{ \left( n+5 \right)  \left( n+4 \right) }}-4\,{\frac { \left( -24-7\,n+{n}^{2
} \right) {N}^{3}}{ \left( n+5 \right)  \left( n+4 \right) }}-2\,{\frac { \left( 3\,n+10 \right) {N}^{4}}{n+4}}+{N}^{5}
$$

$$
1/4\,{\frac {{4}^{n}}{\pi \,n}}
$$
(for more refined asymptotics see the webpage).

{\bf $(k,l)=(2,2)$, $z=2$}

$$
1, 2, 6, 24, 120, 720, 5040, 40320, 361116, 3540600, 37207368, 411988896, 4747167568,
$$
$$
56428884512, 687793860000, 8559142303296, 108400653865572
$$

$$
-512\,{\frac { \left( 2\,n-1 \right)  \left( n-1 \right) n}{ \left( n+5 \right)  \left( n+4 \right) ^{2}}}+16\,{\frac { \left( 231\,n+711\,{n}^{2}+164\,{n}^
{4}
+588\,{n}^{3}-2 \right) N}{ \left( n+5 \right)  \left( n+1 \right)  \left( n+4 \right) ^{2}}}
$$
$$
-16\,{\frac { \left( 1146\,{n}^{2}+545\,{n}^{3}+1003\,n+94\,
{n}^{4}+296 \right) {N}^{2}}{ \left( n+5 \right)  \left( n+1 \right)  \left( n+4 \right) ^{2}}}+4\,{\frac { \left( 2030\,{n}^{2}+85\,{n}^{4}+688\,{n}^{3}+
2501\,n+996 \right) {N}^{3}}{ \left( n+5 \right)  \left( n+1 \right)  \left( n+4 \right) ^{2}}}
$$
$$
-4\,{\frac { \left( 87\,{n}^{3}+8\,{n}^{4}+525\,n+336\,{n}^{2
}+250 \right) {N}^{4}}{ \left( n+5 \right)  \left( n+1 \right)  \left( n+4 \right) ^{2}}}+{N}^{5}
$$

$$
1/32\,{16}^{n} \left( {n}^{-1} \right) ^{7/2} \left( 1+{\frac {33}{8}}\,{n}^{-1}+{\frac {2145}{128}}\,{n}^{-2}+{\frac {81723}{1024}}\,{n}^{-3} \right) {\pi
}^{-3/2}
$$

redpajama_set_name: RedPajamaArXiv


text:
\section{}

The steady increase in use of online educational tools and services has led to a large amount of educational video materials made available for students to watch. Finding the right video content is usually supported by the overarching learning management system and its user interface that organises various video items by course, categories and weeks, and makes them searchable. However, once a wanted video is found, students are often left without further guidance as to  what parts in that video they should focus on.

In this article, an additional timeline visualisation to augment the conventional playback timeline is introduced which employs a novel playback weighting strategy in which the history of different video interactions generate  scores based on the context of each playback. This includes whether the playback started after jumping forward or backward in the video, whether the playback was at a faster or slower speed, and whether the playback window was in focus on the student's screen or was in the background. The resultant scores are presented  on the additional timeline, making it in effect a playback-centric usage graph nuanced by how each playback was executed. Students are informed by this visualisation on the playback by their peers and can selectively watch those portions which the contour of the usage visualisation suggests.

The visualisation was implemented as a fully-fledged web application and deployed in an undergraduate course at a university for two full semesters. A total of 270 students used the system throughout both semesters watching 52 videos, guided by  visualisations on what to  watch. Analysis of playback logs revealed that students selectively watched portions in videos corresponding to the most important portions of the videos as assessed by the instructor who created the videos. The characteristics of this method as a way of guiding  students as to where to watch as well as a complementary tool for playback analysis, are discussed.  Further insights into the potential values of this visualisation and its underlying playback weighting strategy are also discussed.

\tiny
 \fontsize{8}{11}\helveticabold { \section{Keywords:} learning analytics, online learning, educational video, interaction logging, system deployment}
\end{abstract}

\section{Introduction}

Increasing amounts of educational video materials are becoming available online. Coursera, one of the most popular Massive Open Online Course (MOOC) platforms, has over 3,000 online courses with 82 million registered learners as of March 2022 (https://about.coursera.org/), probably with millions of video materials of varying lengths available. When the COVID-19 pandemic hit in Spring 2020 forcing almost all universities to deliver their courses remotely, the amount of video content for students to remotely access further increased, with two main types of video content: (1) synchronous recorded lecture videos made available after the online, live lectures on Zoom or other video conferencing platform (typically lengthy, e.g. 30 minutes to 1 hour or longer), and (2)  video material prepared by the lecturer out of class and made available for students to watch asynchronous (typically shorter, e.g. 5 minutes to 15 minutes, but can also  be longer).

Regardless of the type of  video material, online courses meant a considerable amount of videos for students to wade through and watch, often multiple video items per week, including lengthy lecture recordings as well as short videos to review. These videos typically become available on the university's Learning Management System (LMS) so that the videos for each week to watch are grouped, arranged, ordered and possibly searchable for students to access: students are generally provided with some ways to find a suitable subset of videos that could satisfy their learning needs.

Once a video is selected and opened, however,  students are usually left  watching the contents without much support: (i) the inherent temporal nature of the video medium hides  the full content from being browsed, and (ii) the typically unprofessionally- and minimally-edited, linearly organised characteristics of educational contents (mixtures of PowerPoint slides sometimes with animated annotations and/or talking heads, etc.) mean no clear or explicit structure to be followed within the videos. This results in either having to watch the full video even when not all of the contents are relevant/useful for the student, or blindly jumping back and forth hoping a useful point in the video will show up. Without instrumenting a lot of sophisticated within-video content browsing facilities (storyboards, keyframe-based browsing, structured shot/scene navigation, etc.) often the subject of experimentation within the video retrieval community \citep{Smeaton2004}, how could  students be guided as to where to watch inside this type of videos?

Current  analytic studies of video usage in the educational setting usually target \emph{the instructors} as the beneficiary of the analytics, i.e. to show  instructors how  students are watching the videos, as there is a clear need for more objective insights and  better visibility of students' viewing behaviour to the teachers so that they can improve how they make and provide their video materials \citep{Fong2019}.

In this paper, we shift the focus of analytics \emph{from the instructor to the students}, i.e. the usage of video contents watched by the student cohort can be analysed and the results can be used to support students' navigation within the video content, an aspect which is missing in today's educational video platforms. By focusing on how potentially useful usage information could be fed back to the students so that it will guide them in choosing where to watch within each video, a \emph{playback-centric visualisation} was devised in which we developed a playback weighting strategy that takes into account various micro-level video interactions that students trigger and that are weighted differently. These weights are used to calculate an overall score for every 1-second window within a video, and we  then present this as a video timeline.

By computing the cumulative values of individual video interactions (e.g. play/pause clicks or seek actions), and presenting the cumulative values of playback derived from differently weighted video interactions, the unique timeline visualisation represents those parts within each video that have received the  most interaction from students as it reflects how they watched when they were watching e.g. were they skipping or perhaps using faster (1.25x, 1.5x, 2x) playback, as well as when during the semester they were watching the video. Our paper introduces this playback-centric visualisation of video usage, in which:

\begin{itemize}
    \item a playback weighting strategy is used and updated daily to calculate the second-by-second scores in each video based on judiciously chosen weightings for micro-level video interactions from students;
    \item a full-fledged system incorporating this strategy was built and deployed for two full semesters (2021 and 2022) at a university, and
    \item we analyse the usage data and the usefulness of this method, and share the insights gained from it.
\end{itemize}

The contributions of the paper are that by going through the above activities, we establish our understanding of the designed visualisation, which can be expressed as our attempt at answering the following research question:

{\leftskip=2cm\relax
 \rightskip=2cm\relax
  \noindent\emph{Does the proposed visualisation of weighted playback by peers help  students to selectively watch the more important parts within  videos?}
 \par}

More analyses of the usage, perceptions and attitudes of students on an exclusively online learning environment during the pandemic \citep{Popa2020} \citep{Coman2020} \citep{Chen2020} and attempts at capturing the students' attention level and monitoring it while they watch video or live lectures \citep{Lee2021} \citep{IntelliEye2018} \citep{Srivastava2021} \citep{Pham2015} are all very important, and the support for better guidance for students in more selectively/efficiently reviewing the video contents is a notable gap identified and addressed in this paper.

\section{Related Work}
There is a large body of literature in learning analytics for online platforms in general e.g. comprehensive reviews including \citep{Ihantola2015} and \citep{Dawson2019}, and a moderate amount of literature on analysing video watching behaviour in an educational context. When it comes to detailed analysis looking into the within-video-level watching behaviour such as the proportions actually watched and parts of videos that had more interactions, the number of publications decreases to a handful. The increased adoption of MOOC courses in universities certainly increased an interest in deeper understanding of the issues of online learning (e.g. decreased motivation, delayed feedback, feeling of isolation, etc. \citep{Yusuf2013} \citep{Coman2020}) and of the analysis of video material usage and student behaviour, the bulk of the latter will be  reviewed in this section. We expect a more recent line of such studies to appear soon as the COVID-19 restrictions in universities resulted in more intense e-learning thus an increased amount of video-based online classes.

\subsection{Within-video usage analytics in educational context}

Video usage analytics outside the educational context have been many and diverse including market surveys on why people re-watch the same commercial video content \citep{Bentley2016} and market studies using the commonly used ``views" and ``likes" counts in YouTube. The use of ``views" in particular, is the most basic, dominant metric used in learning analytics studies where the main focus is the usage of the whole learning management system (LMS) in which the video usage is a part (e.g.  \citep{Jovanovic2017}).

Other than views, there are other metrics typically used for video analytics including ``play rate" (ratio of playing a video to the number of links usually in the form of a thumbnail frame image, shown to the viewer) and ``view length" (how long the viewer watched the video). In the context of educational videos and pre-class asynchronous learning materials, ``punctuality" is sometimes used to measure whether the students watched the video before the class time. Common metrics used to look into within-video watching behaviour include ``coverage" (ratio of playback portion to the whole duration of the video), ``peak" (most frequently interacted part of the video) and ``drop-off point" (where the viewer stopped watching in the video). In the video usage analytics in the educational domain, some combinations of these metrics have been used.

An in-depth interview with 16 post-secondary instructors who use videos in their teaching \citep{Fong2019} showed that a more in-depth analysis of video watching behaviour of students would be very useful for them to assess the video quality and how they could revise accordingly. It is apparent that lecturers will benefit if there are more detailed information available to them on how video materials are viewed by students.

On the one hand, the majority of the literature on video playback interaction analysis to support such insights in an educational context comes from around 2013 when large-scale MOOC courses became popular  and a greater  variety of in-video interaction types (pause, seek, speed change, etc.) became the norm on these platforms. This meant  that the analysis of these click-level interactions became technically feasible in practice. On the other hand, the degree of detail that the studies look at within-video interaction varies, from simple view counting presented over time to  second-by-second cumulative calculation by different interaction types.

For example, one study \citep{Dazo2016} looked at the usage of 25 video materials across 3 consecutive semesters in a flipped classroom setting. Using views, coverage and punctuality as the main metrics, they found that  students' academic performance was connected to some of the video viewing behaviour, e.g. previewing the videos before the class. Looking at the watching behaviour inside the videos was through the metric of coverage, generally proportional to the view counts. Another study found out 2 distinctive clusters of students based on their video watching behaviour in a 15-week course on Matlab programming \citep{Moore2021}, where the high-performing cluster of students also showed significantly higher coverage in their watching, compared to the low-performing cluster.

Moving beyond the overall view count and coverage, an analysis of a MOOC course involving 48 videos  \citep{Atapattu2017} counted the number of video interactions (play, pause, speed change, etc.) that happened at each second in each of the videos, presenting the counts on a timeline within the video. While their focus was to use video transcripts to analyse the discourse and correlate with those video interaction counts on the video timeline, the counting of interactions at each second of the videos and seeing the highs and lows of them on a timeline of each video is a promising approach to reveal the minute details of interactions as they happened while the videos were playing.

Going even deeper into within-video interactivity, Li \textit{et al.} related the frequencies of different types of within-video interactions (pause, skip, replay, etc.) to the understandability of video contents (i.e. difficulty of learning) \citep{Li2015a} \citep{Li2015b}. Of particular interest is the metric ``replayed video length" that summed all played video durations by seconds that were re-watched (concluding that less re-watching indicated higher video difficulty). Differentiating different types of interactivity is certainly necessary if we want to understand the playback usage in more detail, and we describe later how in our study the different types of interactions will be assigned to different weightings in cumulative scoring inside each video.

A study in \citep{Kim2014} used similar second-by-second bin counting where play and pause interactions increased the count thus forming the ``peaks" in the usage timeline. They also used simple image similarity comparison between frames from every 1 second in the video to identify the points where high differences appear and thus  help categorise different types of transitions in video presentation (e.g. from PowerPoint slides to talking head). They show a prototype user-interface where different types of interactions (views, replay, skip, etc.) can be selected to see its cumulative peaks within the video.

Further related studies and analyses include video analytics that used aggregated time series to present  interactivity within the videos. This was used to check those parts of video contents in a specially designed 10-week course  \citep{Giannakos2015}, correlating the video playback time with student engagement level in 4 edX courses that happened in the same semester \citep{Guo2014}. This took a cognitive psychology angle where grouping of different sequences of video interactions into higher-level ``behavioural actions" to help predict the students' usage behaviour \citep{Sinha2014}.

Table~\ref{table:LiteratureTable} shows a summary of 7 video usage analysis studies (2014 - 2021) some of which addressed the above, selected as good representative studies in the literature that we reviewed. It can be observed from the table that:

\begin{itemize}
    \item Educational video contents span from a few dozen to a few hundreds of videos, and the length of each video varies from a few minutes to 45 minutes;
    \item Various sets of metrics are used in different studies;
    \item There are attempts at correlating the watching behaviour to some overall score (e.g. grades);
    \item Temporal mapping within videos (the last 3 rows in the table),  attempt at within-video locating of usage behaviour, could be explored more.
\end{itemize}

The studies that apply the last point (temporal mapping within video) count  video interactions at second-level points inside each video, including clicking of play/pause buttons, replay, etc. This allows them to show the cumulative effects of usage as the peaks of these interactions along the timeline. The peaks then point to the video contents, at those points.

It is this temporal mapping of within-video usage that our paper  builds upon, where the values to be presented are not the counting of interactions but the accumulated playback scores that take into account various video interactions, each weighted differently, in order to reflect the way students actually watched the videos.  We expect this will better guide  students as to where to watch.

\subsection{Within-video recommendation and timeline visualisation}

Typical usage of video content has been to linearly watch from start to finish, whether short  (e.g. a 5-minute YouTube clips) or long  (e.g. a 2-hour movie), thus not requiring any elaborate visualisation scheme to help to navigate or jump within the videos other than indicating where the current point of playback  is in time. Educational video content, on the other hand, will generally benefit from features which support within-video navigation/guidance as the videos in educational domains typically have a structure, a progression and different types of presentation, and students might be looking for certain parts within them. \textcolor{black}{There are cases where more use of video control features such as skip/pause was negatively associated with students' performance (e.g. \citep{Joordens2009}), though that work pre-dates the huge uptake in online learning over the past decade and in particular as a result of COVID. Thus thinking that providing various interactive video playback features will be beneficial for students may be only an assumption. Different learning strategies used by students (e.g. simply memorising vs. deeply understanding) along with the topic types of the course will have impact in deciding how beneficial the video control features are  \citep{Le2010}.}

Some of the video analysis studies in educational contexts, including some of the earlier-mentioned ones, do feature visual guidance on the playback timeline. For example, TrACE UI shows the portions of video that they already played \citep{Dazo2016} on its video timeline, guiding  students on where to play or avoid playing; Video timeline shows peaks and highlights that are dynamically changing as the usage increases \citep{Gajos2014}. YouTube's video analytics page features a ``key moments for audience retention" section in which the usage frequency is presented on a timeline (duration) of a video, visually showing the peaks and troughs presented based on  playback as well as other interactions such as sharing with others at those points. To support video-based learning of how to use Photoshop effects, the video timeline shows the highlight points for step-by-step navigation \citep{KimToolScape2014}.

Although not particularly for an educational context, Video timelines with bookmarks  allows smooth pre-fetching and the indication of buffering has been proposed \citep{Carlier2015}; Ice hockey goal events are highlighted and shown as mini icons on the timeline of the playback UI \citep{Muller2010}. Many experimental video retrieval systems in the field of multimedia (e.g. the annual Video Browser Showdown showcase \citep{Schoeffmann2019}) have been experimenting with more sophisticated and advanced within-video highlights where the retrieval unit is sub-video parts (e.g. a frame, camera shot, scene, etc.) and the searcher is supported by various visual strategies to highlight within-video match points within long videos. Examples include highlighting  the portions of a video timeline for a particular type of scene (dialogue, action or montage) in movies \citep{Lehane2006}, indicating the boundaries between short video chunks in a longer, concatenated video \citep{Lee2017}, and various ways of highlighting retrieval results on the video timeline \citep{Gaughan2003} \citep{Cooke2004} \citep{Leibetseder2018} \citep{Sauter2020}.
We do need  to see yet more effort in applying these sophisticated within-video timeline visualisations in an educational context. Judicious applications of some of these features could help students more efficiently learn the contents by more selectively picking and playing the parts of videos that are useful for them.

\section{System Description}

The system we built and deployed is a web-based archive of educational video materials made available throughout a semester, used in conjunction with the university-wide Learning Management System. The video materials, once they are available on the system for watching, can be played with  conventional playback-related functions. While all user interactions throughout the web interface are logged, the system's visual guidance feature which this paper  introduces and the analysis used to drive its operation, uses mainly the playback-related interaction portions  of the logs such as play, pause, and speed change as well as indirect, contextual usage logs such as whether the playback is happening as the window of focus on the student's screen.

Figure~\ref{fig:diagram} shows how the system works.  The lecturer  uploads  video clips that s/he created and offers the students to watch as part of the course material (1); the system will use a specially formulated playback weighting strategy to calculate what the score for each of the second-by-second bins in the timeline should be (2); scoring adds a time-decay function to construct the playback visualisation for  students (3); the resultant UI is then presented to  students (4); finally, students  interact with the system by playing, pausing, changing speed, etc. and this interaction is fed back to the system to re-calculate the scores using the weighting strategy (5). The cycle (2)-(3)-(4)-(5) continues through the semester as the shape of the timeline visualisation  evolves over time.

In the remainder of this section, we describe the user interaction and  visualisation, followed by the mechanism used to generate it.

\subsection{User interaction and the usage visualisation}

The web interface allows  students to log in by using their student email address and a unique 8-character code for the course. Once logged in, the student is presented with a list of available video materials on the left side of the screen (see Figure~\ref{fig:screenshot}). Selecting one  will load the video playback panel and the associated usage visualisation above it.

The visualisation feature is a time-based graph, aligned with the playback timeline of video content (panel above the playback screen in Figure~\ref{fig:screenshot}), where the height of the yellow shape suggests video usage to  students so that they could watch those portions within videos that show high levels of usage by their peers.

Using the yellow contour of the graph as a hint to select  parts of the video to watch,  students engage in selective playback of the video, data from which will, in turn, be taken into account using the playback weighting strategy to contribute to the shaping of the contour for other students. Establishing the usefulness of this visualisation in helping  students watch the important parts of videos is the focus of the analysis  presented later.

\subsection{Playback weighting strategy for the visualisation}
\label{weighting_strategy_section}

The height of the yellow areas within the visualisation is the result of our playback weighting strategy, the core technical component of the system.

Each video is divided into 1-second windows and each window starts with an initial score of 0 which is incremented every time any student plays or skips it. Every time any part of the video is played, that part will gain a score increment, thus over time as the usage increases the scores in each second-by-second window on the timeline will increase.

Since there are various playback-related interactions a user can perform at any time during video playback, the system uses the type of interaction that happened  to calculate the score increment for that second: thus the playback weighting strategy determines the shape of the visualisation, eventually serving as the guidance to students on what parts of the video to watch. The strategy is as follows:

\begin{itemize}
\item \textbf{Play}: As the most basic scoring strategy, the window gets \textbf{+1} when that portion is played. This is similar to calculating ``peak profile" in which play events are counted to show the peaks \citep{Kim2014}. However, if the video playback window was not the window of focus on the student's screen when the student was playing it, then this increment is \textbf{+0.25} only,  bringing down the score for  cases where the student may be reading email or doing something else while half-listening to the video.

\item \textbf{Replay (Seek backward, i.e. within the same session)}: All 1-second windows between the previous playback point and the point it skipped back to will each gain \textbf{+2} score, so each gets a cumulative +3: +1 from the initial playback and +2 from the replay). Re-watching could mean more difficulty in understanding that part of the video \citep{Li2015a}, although there could be other factors e.g. returning to  missed content, following the steps in tutorial-type videos, hearing again non-visual explanations, etc. \citep{Kim2014}. Whatever the reasons, the parts which students replayed are  parts to watch out for and  point out during students' course review.

\item \textbf{Faster play:} Playback at $2\times$ (double speed) will gain \textbf{+0.6} and if the window is not the window of focus then it will be \textbf{+0.2}  only because when the student is attending to another window, the double-speed playback is too fast to properly comprehend. Playback at $1.5\times$ will gain \textbf{+1.5}, and \textbf{+0.5} if the playback window is not the window of focus. In this study we assume that playing at $1.25\times$ speed will gain the same as playing at $1\times$ speed for student learning. Recent studies consistently show that playing  educational videos at $1.25\times$ resulted in better learning outcomes than when played at normal speed \citep{Lang2020} \citep{Mo2022}, and the benefits and drawbacks of other speeds (e.g. $0.75\times$ and $1.75\times$) are worth further investigation in order to incorporate them into our weighting strategy.

\item \textbf{Skip (Seek forward)}: There can be different reasons from a cognitive processing point of view as to why students want to skip familiar parts of a video or continue watching even if already familiar \citep{Sinha2014}, but skipping typically implies that the student finds those portions easier to understand \citep{Li2015a}. If a student skips forward from the current position at minute S0 by a segment of video then windows within  1-, 2-, and 3-minute  segments directly following the  segment S0 will get score adjustments as follows: S60: \textbf{-0.3}, S120: \textbf{-0.2}, and S180: \textbf{-0.1}. The rationale for this deduction in scores is that the student must have had an idea what was coming up next, after point S0, but anticipated it as being not interesting or useful for her/him at that point in time and thus less likely for other students to also find it   interesting or useful.

\end{itemize}

\noindent
\textbf{Adjusting the score over time}: Overarching the playback weighting strategy is a \textbf{decay function} based on recency of playback, with the most recent days of playback interaction being more meaningful or useful than prior to that. The scores calculated by the above strategy are re-calculated from the interaction log each midnight. In this way the score increments (both + and -) as above are called our BaseIncrements = (+1.0, +0.25, +2, +0.6, +0.2, +1.5, +0.5, -0.3, -0.2, -0.1) and the system makes those the actual increments on day 0. Then on day 1 it makes those increments each multiplied by 1.1  before adding, on day 2 the base increments  multiplied by 1.2, and so on.  The effect is that on day 10 we have a score for each 1-second window which has a 10-day linear decay function so that something played on day 9 has twice the value of something played on day 0 and by day 20 we have a score which has a 20-day linear decay with the half-life being 10 days.  This  continues  indefinitely. The decay function is useful for the lecturer who wants to understand the factual usage statistics of each video segment, but it serves an important role that will influence the shape of the usage visualisation for students who need to be selective at the time of reviewing the video.

The scores for the 1-second windows are normalised within each video usage graph at display time making the visualisation less susceptible over time to any maligned attempt at artificially inflating scores by jumping to or repeatedly playing an obscure segment of video.

A study found that the points in videos with more video interactions indicate those parts requiring higher-order thinking and more cognitive skills by students \citep{Giannakos2015}. Instead of scoring highly those parts with more interactions regardless of the type of interactions, our weighting strategy attempts a more fine-grained differentiation amongst different video interactions and uses the cumulative scores from it as  overall guidance to offer to students.

\section{Course Outline, Deployment and Data Captured}
\label{outline_section}

The course for which the system was deployed was an undergraduate-level course on data analytics for marketing applications delivered in the Spring semester (18 January - 15 May) in 2021, and again  the following Spring semester (10 January - 26 April) in 2022.

Since the Spring semester in 2021 was a lockdown period due to the COVID-19 pandemic, the course was delivered fully online: Zoom lectures were conducted live while video recordings of them were made available for students for later asynchronous review as they wish. The University's virtual learning environment was also used to present other course material including links to YouTube clips, news articles and other websites as well as the PowerPoint slides used for the online lectures and for creating the video materials and worked examples of data analytics. As an additional source of  course material, the Professor prepared  a set of 52 short form video clips for students to watch in their own time in addition to various links to the other  materials. In each week, the materials suitable for that week's lecture topic became available as entries on the course's LMS site. The number of students enrolled to the course in the first deployment was 131.

The Spring semester in 2022 was conducted with regular face-to-face in-class lectures as the main mode of course delivery and those lectures were also streamed live and Zoom recordings were made available, further augmented with the same additional online material as in the previous semester including the same set of video clips prepared by the Professor from 2021. Each of the video clips was pointed out and recommended for students to watch as the course progressed through the face-to-face lectures. The number of students enrolled in the second deployment was 139.

The video materials were screencasts created by the Professor who taught the course. Each video was about 10 minutes duration and 3-5 such videos were added for each week throughout the semester. \textcolor{black}{The topic for each of the videos is shown in Table~\ref{table:Topics}.}  The time of the addition of each video depended on  factors including the availability of certain materials to be mentioned in the video and time constraints of the Professor, resulting in some materials on later topics to be available earlier in the semester, and vice versa. A total of 52 videos had been made available to students in both deployments, and the usage of these 52 videos facilitated by the visualisation during the two deployments is our main focus in this paper.

For the duration of each of the two semesters,  enrolled students used the system actively playing and re-playing  video content as part of their studies thus feeding into the playback usage analysis which, in turn, helped shape the contours on the timelines for each video that guided them where to watch.

A manual annotation of the most important part within each of the videos was carried out in order to check whether the visualisations actually helped students locate the most important parts of videos in their study. The Professor who developed the video materials and delivered the course went through each video, marking the start and end points within each video that were judged as the most important part of that video, not knowing the actual playback usage that happened during the semester. The only constraint imposed on the Professor's annotation was that for each video there was to be only one continuous part as the most important, that is, not multiple different time blocks. The duration of this part was up to the Professor to decide purely based on the learning content. Although there might be multiple points that a lecturer sees as important in courses where video materials are longer in duration (e.g. 30 minutes or 1 hour or more), the videos in this course were short and the Professor specifically designed each video to be about one particular concept. Since the course and its video materials were all developed by the same Professor, there was no need to employ multiple assessors to indicate these important parts and to then check cross-annotation for consistency.

It is worth noting that the annotation of the important parts within each video is inevitably a manual task that had to be performed by the Professor in order to answer the research question in our study, and thus for the regular deployment of the system such a manual effort is not required.

\section{Findings and analysis}

Overall usage of the video materials using our system is summarised in Table~\ref{table:overallusage}, showing  combined usage from both semesters. The analysis and our evaluation of the usefulness of the proposed playback weighting strategy and visualisation uses the combined usage data collected from both semesters. Since the video clips were supplementary to the main lectures by the Professor either by Zoom or face to face or both, as well as to other online materials,  students were not required to watch all available videos (though they were encouraged to), which explains the overall low playback usage (an average 28.9 minutes of playback per student). This indicates that when students did use these videos it was not their main source of course material and could have been used to clarify some complex aspect of the course, though this is speculative.

\subsection{Playback usage according to playback weighting}
\label{playback_usage_subsection}

In order to answer our research question, we examine the playback usage according to the timeline visualisation shaped by our playback weighting strategy. Figure~\ref{fig:Minutes} shows the playback behaviour within each of the 52 videos according to our weighting strategy but without reflecting the decay function (designed to factor in the date  at which the student is watching the video).
Each graph represents the second-by-second playback scores presented for each video, according to the playback weighting strategy  described in Section~\ref{weighting_strategy_section}.

The blue contour lines in each video graph show the playback usage of each video. As can be seen, the contours are overall quite different-looking than those that present the counts of video interactions since here we present the cumulative, played parts of videos with the influence of the playback weighting strategy: there are fewer sharp peaks but a greater number of different levels of plateaus where  playback continued for some time.

To begin with, an initial observation from Figure~\ref{fig:Minutes} is that all graphs start with  high playback usage. Students start watching a video by clicking on the play button, and as the starting point is always at the start of the video when the video is first loaded, the playback score is always counted at the very start of every video. But after  playback starts, almost always the students will skip into the middle of the videos, making the playback scores at the start immediately drop. Exceptions to this behaviour can be found in only  a few videos, for example, the video labelled v45 in Figure~\ref{fig:Minutes} shows that from the very start,  playback usage was well maintained for  most of the video; the video labelled v31 shows a start with a low usage but steadily increasing until the end of the video at around the 5 minute point.

The timeline visualisation that students actually saw and were guided in choosing the portions to watch are the decay function-enhanced versions of the Figure~\ref{fig:Minutes}, that showed slightly different contours depending on when they watched the videos. It is not possible to accurately estimate how the usage might have been without the decay function influencing the visualisation as the usage evolved over time with the function, but by back-tracing the contours during the semester, we can estimate its effect (see Section~\ref{change_section}).

\textbf{Effectiveness of the visualisation: highlighting the important parts.}
\label{effectiveness_section}
Checking the playback usage together with the important parts manually annotated by the Professor is a central task to answer our main research question. In Figure~\ref{fig:Minutes} the green areas in each video graph are the important part in each video marked by the Professor who gave the course and annotated this independent of the actual usage.
The marking range for each video was then compared to the playback usage visualisation for each video, to check whether the parts with high plateau of playback scores (i.e. the part the students were guided to and watched) is where the Professor marked as the most important parts. The green check symbol on the right side of each video graph in Figure~\ref{fig:Minutes} shows that the highest playback regions matched the important parts of the videos, while the red 'X' symbol shows that they did not match. Out of 52 videos, 38  matched (73.1\%): that is, 38 out of 52 playback visualisations correctly guided  students to watch the most important parts within the videos and they actually watched those portions.

This deserves  more detailed analysis. For example, video v6 (see Figure~\ref{fig:Minutes}) shows a low usage for the first 5 minutes or so, then suddenly peaks maintaining the plateau for 30 seconds before flattening, and the peak point coincides with the important part as judged by the Professor. It is encouraging to see that the natural playback usage reinforced by the visualisation, results in  students watching that important part of the video. As another example, v41 shows relatively low usage throughout, but halfway into the video at around 3 minute point, the line slightly goes up and remains plateaued: the start of that plateau is the important part and students correctly catch that part.

On the other hand, v42 shows a middle third of the duration as the important part, yet the actual playback was pretty much a high plateau all throughout the duration of the video. The visualisation ends up not differentiating any part and is thus unable to effectively guide  students to be more selective, yet most students who opened this video did watch the important part.

\subsection{Contour changes over time}
\label{change_section}

As  students play the videos, the timeline visualisation for each video changes  as it is updated daily. Figure~\ref{fig:timeline-change} shows two example timelines  captured near the end of lecture weeks (Weeks 12 and 13 respectively) and again at/after the final exam, during the 1st deployment (since the visualisations that the students actually saw cannot be based on aggregated data across two semesters).  In case of v15, \textcolor{black}{the topic covers the normal distribution in a set of numeric values and the concept of how the standard captures the spread of data values.  The parts  played most are the the second half by the end of lecture classes as students grapple with the concept of what is a standard deviation.}   Approaching the final exam the playback portions changed and the week after the exam the timeline shows more coverage across the video, ending up with two moderate plateaus at the start and middle followed by the highest region nearer to the end of the video.

On the other hand, v50 \textcolor{black}{which is about how our digital footprints can be used to predict our personality using the 5-factor personality model}, this seems to maintain the overall playback usage after the high use at the exam, though slightly lower at the first 3 minutes or so, and higher at the latter 4 minutes.

\textcolor{black}{The change of contours becomes more noticeable as the usage becomes higher, and in our system, this understandably occurred right before the final exam period started. Whatever contours shaped thus far as a result of relatively low but continuous and gradual usage during the main part of the course  are then picked up as the hints to where to watch when the urgency of learning increases at the impending final exam (the danger of ``bandwagon effect'' and how our algorithm is resistant to it is discussed in the next section). However, the exact pattern in this more noticeable contour change near the exam time is not consistent and dependent on the video contents, as seen, for example, the way the peaks near the end becoming more spread out throughout v15 as the result of more usage due to final exam, and maintaining the peak near the end of video and becoming increasingly so due to final exam in v50, clearly contrasting to v15.}

\section{Discussion}
\label{discussion_section}

\textbf{Playback-centric view as complementary to video interaction view.}
The contours of the within-video graphs are quite different from those that present the counts of video interactions (e.g. \citep{Kim2014} \citep{Giannakos2015} and \citep{Atapattu2017}). Influenced by the playback weighting strategy that incorporates  video interactions but presented not by those interaction points but by the played parts, the playback-centric presentation is more range-based (i.e. from time A to time B) than point-based (i.e. this point in time). The message the visualisation  gives is the suggestion of the parts of the video to watch and is thus slightly different from the presentation of where the interactions occurred most often. The playback duration-based usage on the timeline is an additional aspect of the usage which is complementary to the interaction point-based usage, adding further dimensions to  understanding  the details of the use of video playback.

\textbf{High plateau = important part?}
In this study, we attempted to assess the usefulness of the visualisation (and its weighting strategy) with the broad assumption that the system's visualisation is effective when the most-watched parts in videos correspond to the most important parts as determined by the Professor. This assumption may be naive since the parts where the students need to review more frequently or need to think more deeply might not be same as the most important parts identified by the Professor.  Perhaps the more difficult parts, or the parts that omitted examples or were explained poorly, might have been watched more and thus the more difficult or poorly-explained parts are not necessarily the most important parts. However, as an initial deployment of the visualisation, such an assumption could still be useful without complicating or adding further intervention steps during and after the deployment. This needs to be kept in mind in the interpretation of our findings.

Currently our playback weighting strategy is purely based on  playback usage and influenced by the time-decay function. For 38 out of 52 videos in our study, the parts the students watched the most were largely the parts that the Professor judged as most important, but for the remaining videos this was not the case. The weighting strategy could incorporate content-related factors e.g. the instructor's indication of important parts in each video, perhaps by ranking a few different parts of the videos, to influence the baseline score of each second-by-second bins. However, the added manual input required from the course instructor would be an issue especially as the number of courses and videos increases.

The timeline visualisation changes over time as  students continue to play different parts of different videos. Students will not benefit from the visualisation in the early stages of the semester as not many parts will have been played and not a lot of noticeable contours will be shown. They benefit as the timeline plateaus become more prominent, only after it becomes clear where peaks are and this   comes only after  playback usage has occurred.

With this in mind, we now ask whether the proposed visualisation helps
students selectively watch more important parts within the videos and the answer is reasonably so (73.1\%), considering no explicit information or intervention was offered to influence video usage. Furthermore, given our approach of relying on usage data to feed into the system, the visualisation is likely to improve its guidance to important parts if there was a pedagogical mechanism to increase the overall usage by students e.g. enforcing the watching of the videos as mandatory, rather than as supplementary material as  in this course.

What happens when the high plateaus are not corresponding to important parts of the video? If so, it could mis-guide the students and potentially fall into a negative bandwagon effect as happens in social networks \citep{Wang2015}), in recommender systems \citep{Sundar2008} and perhaps take advantage of the effect in e-commerce and IoT products \citep{Choi2015}. Unintended mis-guiding formation of the usage visualisation is less likely to occur as the decay function embedded in the playback weighting strategy makes the shaping of the contours somewhat resistant to occasional random watching on obscure points within the videos. Initial ``seeding" of important parts in each video may be a way to further reduce such negative effects.

\textcolor{black}{Finally, the videos watched by the students in this study were the supplementary learning material in addition to the formal online/face-to-face lectures as well as other website links and YouTube resources that were made available for students. The playback usage pattern within the videos (thus the shapes of the contours) is expected to be different if the videos are to become the core delivery mechanism as is the case in many studies referenced in this paper so far (e.g. majority of the usage analytics studies and the ones in Table~\ref{table:LiteratureTable} are MOOC courses in which the video playback is the central vehicle for content delivery). The interpretation and the application of our findings and discussions on the behaviour of the visualisation and its effects for other courses, therefore, will need to take this into account.}

\textbf{Future studies.} This study was the first deployment using the strategy that weighed individual interactions differently. One reason for pushing for  full deployments integrated into an existing course was to identify which aspects of the system could or should be the main focus of  future studies within the design, implementation and deployment, and also how the system and the way the course is delivered could more tightly support each other.

There is  room for improvement by incorporating other more detailed playback contexts into the playback weighting. For example, the faster/slower speed setting could have more elaborate weighting variations depending on the target speed set, informed by other studies on the particular speed affecting the students' overall performance; other interaction factors that could be used include the   volume level used while playing and whether it was viewed full-screen.

While in this paper we focused on understanding the overall usefulness of the visualisation and its potential value, more detailed analysis specifically delving into different categories of session behaviours or student group behaviours with statistical means will allow us to characterise its usefulness in more specific ways. Similarly, designing a comparative study which has a half of the student user population with the visualisation and the other half without it or with a different weighting strategy will help understand the level of usefulness of the visualisation and its weighting parameters.

One of the potential issues inherent in our approach is when each video is first uploaded and  becomes available on the system without any prior playback usage data. The ``cold-start" issue is typical of many usage-based machine learning algorithms such as recommender systems (\citep{Natarajan2020} \citep{Kang2019}) where the effectiveness of the approach relies on its usage over time. In our system, when a video first becomes available, the visualisation does not have  usage data from which to calculate and populate  the timeline. As soon as a student starts using a video, its usage will be captured and reflected as a low, yellow area at the bottom of the timeline. A manual indication of the important parts by the lecturer at the time of uploading each video may be a simple solution that could also serve as a way to lead a more desirable evolution of the contour. However given one of the strengths of our approach is  fully-automated shaping of the visualisation without  extra  efforts by a human, other more automated ways to draw the data will be an important topic of further study. For example, some studies used supervised machine learning techniques applied to lecture video images to determine the important parts in  videos \citep{Brooks2009} or applied to the usage data (selecting a video, seeking within the video, as well as the heartbeat rates of the students) to develop a computational model of the usage patterns of students to predict a more desirable pattern \citep{Brooks2014}. Taking a bottom-up indexing approach (i.e. important parts emerge by looking at the video/usage data) rather than top-down (i.e. system first defines and codes in what the important events are), bringing some of these computational approaches into our system may help tackle this issue in a way aligned to what we eventually envision. In our second deployment, the same videos used in the first deployment were uploaded afresh without any use of the data captured from the first deployment. One possible approach would be to plug in the usage data from a previous running of the course (if it has run in  previous year(s)) at the start of the course, to be slowly overridden by the actual usage once this was sufficient.

More refined versions with a tailored playback weighting strategy could well be applied outside the educational domain. For example, such an indication could be useful cues in general video platforms such as YouTube and Vimeo in which the user communities already drive the access and usage.

\section{Conclusion}

We introduced visualisation guidance to students playing educational videos based on calculating a set of playback weightings for different video interactions from students occurring in different playback contexts.  The result shows that for 73.1\% of cases, those parts guided by the visualisation and thus actually watched by students, were the parts that the instructor judged as the most important parts of the videos. By placing the results of video playback usage not to the post-usage summative stage but to the middle of usage where it will help the users use the system, we  broadened the boundaries of video usage analytics, starting with an educational setting where more explicit within-video guidance is very much needed.

\section*{Acknowledgements}
This research was partly supported by Science Foundation Ireland under Grant Number SFI/12/RC/2289 P2, cofunded by the European Regional Development Fund. The
research was also supported by the Google Cloud COVID-19 Credits Program for our cloud based development work.

\section*{Data Availability Statement}
The datasets generated for this study can be found in the Figshare repository  (DOI: 10.6084/m9.figshare.20288763.v2).

\bibliographystyle{frontiersinSCNS_ENG_HUMS}