# A novel 1D state space for efficient music rhythmic analysis

###### Abstract

Inferring music time structures has a broad range of applications in music
production, processing and analysis. Scholars have proposed various methods to
analyze different aspects of time structures, such as beat, downbeat, tempo
and meter. Many state-of-the-art (SOFA) methods, however, are computationally
expensive. This makes them inapplicable in real-world industrial settings
where the scale of the music collections can be millions. This paper proposes
a new state space and a semi-Markov model for music time structure analysis.
The proposed approach turns the commonly used 2D state spaces into a 1D model
through a jump-back reward strategy. It reduces the state spaces size
drastically. We then utilize the proposed method for causal, joint beat,
downbeat, tempo, and meter tracking, and compare it against several previous
methods. The proposed method delivers similar performance with the SOFA joint
causal models with a much smaller state space and a more than 30 times
speedup.

Index Terms—  State space, semi-Markov process, jump-back reward, inference
optimization, music time structure analysis

##  1 Introduction

Time is a fundamental concept in music. Automatic analysis of music time
structures enables many applications in music generation, manipulation, and
recommendation. As an example, such analysis is essential for tasks like
music-score alignment [1, 2] and music transcription [3]. Several approaches
have been proposed to extract music rhythmic parameters such as tempo, meter,
beat, and downbeat. Although SOFA models for some of the mentioned tasks are
promising, computational efficiency considerations make many of them not
applicable in massive industry-scale settings. Furthermore, recent
advancements of augmented and virtual reality and their interactive
applications demands real-time processing, in which computational efficiency
is a critical factor.

Many models attempt to estimate music rhythmic parameters separately e.g., [4,
5, 6] . However, due to the underlying inter-dependencies among these
parameters, joint approaches have demonstrated promising results as well [7,
8, 9]. Joint models often employ state spaces to model these inter-
dependencies, and use some probabilistic models such as Bayesian models to
infer the parameters of interest. As rhythmic parameters are intrinsically
continuous variables, the state spaces are ideally continuous or discretized
with a fine granularity. Hence, the inference can be computationally expensive
when the state spaces are high dimensional.

To make the inference stages tractable, some works e.g., [2, 10, 11, 12, 13]
used numeric approaches such as particle filtering (PF) to approximate the
probability of the states in continuous state spaces. Another set of
approaches e.g., [14, 15, 9, 16, 17] discretize the state space to deal with a
limited number of hidden variables during the inference. Discretizing the
state spaces makes it possible to use some efficient inference algorithms such
as the forward algorithm to compute posterior probability of the hidden
states.

In our previous work [8], we demonstrated that the combination of the ideas
mentioned above can deliver the SOFA performance for causal and joint time
structure analysis. It utilized a cascade of discrete state spaces and an
enhanced PF inference strategy using a proposed information gate technique to
make the inference faster.

In contrast to the above-mentioned Bayesian methods that assume the Markovian
property, in this paper, we introduce a compact 1D state space and a semi-
Markov jump-back reward technique where the transition model is time-variant.
Such variance across time is likely to make the inference process more
complex, in return, it makes the model much more efficient. Although semi-
Markov processes are used before for some specific tasks, e.g., score-
alignment [1], here we propose a generic model that can be utilized as an
efficient alternative for the well-known bar pointer models to improve the
efficiency on several music rhythmic analysis tasks.

##  2 Approach

In this section, we describe the jump-back reward strategy. To elaborate it,
we first describe the bar pointer model [14] and its more efficient version
[15]. Then, we present the new model and demonstrate how it covers the same
parameters i.e., tempo range and time resolution, with much fewer states.

###  2.1 Bar pointer models

The bar pointer model for joint meter, tempo, and rhythmic pattern inference
was proposed by Whiteley et al. [14] to model the dynamics of a bar pointer
that moves through a 2D state space throughout a piece of music. The two
dimensions of the state space represent relative positions within a bar
$\Phi_{k}\in\\{1,2,...,M\\}$ with $M$ being the last position, and the tempo
(in the unit of frames per bar)
$\dot{\Phi}_{k}\in\\{\dot{\Phi}_{min},\dot{\Phi}_{min+1},...,\dot{\Phi}_{max}\\}$,
in the $k$-th audio frame. This state space is discretized into even grids
along both dimensions, assigning the equal number of positions per bar for
different tempi, leading to different time resolutions for them.

Under the same framework, assuming a known and fixed meter, Krebs et al. [15]
proposed a different discretization strategy for the state space, where the
number of positions within a bar $M(T)$ depends on the tempo $T$ (in BPM) as:

$M(T)=Round(\frac{B\times 60}{T\times\Delta}),$ (1)

where $B$ is the number of beats per bar that is fixed and known, and $\Delta$
is the frame length in seconds. By assigning fewer positions for higher tempi,
this model ensures the same time resolution for different tempi. This makes
the inference more efficient hence is called the efficient bar pointer model.

Similarly, for beat tracking alone, a beat pointer model and its efficient
counterpart can be derived, by replacing the horizontal axis with the relative
positions within a beat.

When the meter is unknown, however, one limitation of the efficient bar
pointer model is that the inference needs to be performed on multiple state
spaces independently, making the total state space much larger. For instance,
given the tempo axis ranging from 55 BPM to 215 BPM and the audio frame hop
size of 20 ms, if a bar may contain 2 to 6 beats, then a total of 28,980
states will be needed counting all of the 5 independent state spaces. This
problem is addressed by some works such as the BeatNet [8], using a cascade
model of two separate state spaces for music beat-tempo tracking and downbeat-
meter tracking, respectively. This allows to consider different bar lengths in
a single state space, and shrinks the total state space size from 28,980
states down to 1,469 states for the example above. Fig. 1a and 1c demonstrate
the state space of the efficient beat pointer model. and the downbeat state
space to cover a bar length from 2 to 6 beats for the cascade model. The
disadvantage of the cascade model is that the inference of downbeat and meter
depends on the inference of beat and tempo. In other words, errors in beat and
tempo tracking will be propagated to downbeat and meter tracking.

Fig. 1: Comparison of the state spaces for music time analysis for a tempo
range of [55, 215] BPM, a frame hop size of 20 ms, and a bar length of [2, 6]
beats. a) The efficient beat pointer state space [15] for beat-tempo tracking.
b) The proposed 1D state space with jump-backs for beat-tempo tracking. c) The
cascade state space for downbeat-meter tracking [8]. d) The proposed 1D state
space with jump-backs for downbeat-meter tracking.

###  2.2 Proposed 1-D state space

The main idea of the proposed approach is to modify the 2D bar pointer or beat
pointer state space into a compact 1D space that covers the same tempo or
meter range and time resolution but with much fewer states. This is achieved
by re-defining the position dimension and replacing the tempo dimension with a
jump-back strategy.

Specifically, taking the beat space as an example, instead of defining the
position dimension as relative positions within a beat, the proposed 1D state
space defines it as audio frame indices within a beat interval. The first
index corresponds to the beat position, while the last corresponds to the last
frame within the beat for the smallest possible tempo. As an audio frame
arrives, a pointer hypothesis moves along this dimension one step to the
right. It jumps back to the left end when it believes that a new beat arrives.
As the tempo is unknown, there is uncertainty on when jump-back should happen.
We hence use a probability distribution $\gamma(\phi_{k})$ to describe this
uncertainty, where $\phi_{k}$ is the position (i.e., the frame index within a
beat) of the $k$-th audio frame. This is illustrated in Fig. 1b. The key of
this jump-back operation is that it circulates back some probability mass of
the pointer’s position distribution to the left end (i.e, the beat position),
which is then gradually transported to the right as new frames arrive. When
the music demonstrates regular beats, the jump-back probability will show a
strong peak at the frame index corresponding to the beat interval, and the
posterior distribution of the pointer position will be reinforced to show a
significant peak that moves forward but circles back after each beat interval.

Fig. 1a illustrates the efficient beat pointer state space [15] that includes
multiple rows corresponding to different tempi from $M(T_{min})=55$ (frames
per beat interval) in the bottom row to $M(T_{max})=14$ (frames per beat
interval) in the top one. The proposed state space, in contrast, is 1D as
demonstrated in Fig. 1b. The number of states in Fig. 1b is equal to the
number of frames within one beat interval for the smallest possible tempo. By
taking the same example used in Fig. 1a, this number is 55. Therefore, the
number of states is reduced from 1,449 in Fig. 1a to 55 in Fig. 1b.

This 1D state space can also be constructed for the downbeat (bar) state space
following the same logic. Fig. 1c shows the bar state space in the cascade
approach [8], where the horizontal axis is relative positions within a bar at
the granularity of a beat, and the vertical axis is the bar length. Fig. 1d
reduces this space into 1D with only the position dimension; the bar length
range and the position granularity are kept the same as those in Fig. 1c. It
is clear that the number of states reduces from 20 in Fig. 1c to 6 in Fig. 1d.

In addition to assisting with computational cost reduction, fewer states may
help increase the accuracy, given that the system should infer the correct
states out of fewer hypotheses. Note that the new state space includes a
vector of jump-back weights corresponding to the beat/bar positions, and the
position that achieves the maximum one represents the local tempo/meter. The
weights are updated based on the reward-punishment mechanism discussed in the
next session.

###  2.3 Inference

This section describes an approach to incorporating the proposed state space
into the HMM process for online music rhythmic analysis tasks in which the
inference cost and speed are crucial factors. Given that the proposed state
space is much smaller than previous ones, we compute the pointer’s posterior
probability exactly instead of approximating it using Monte Carlo PF [8]. In
the following, we describe the computational process for the beat state space.
The process for the downbeat state space is the same, and is omitted here to
save space.

Let $\phi_{k}$ and $y_{k}$ denote the latent state and observation at frame
$k$, respectively. Suppose the position posterior $p(\phi_{k}|y_{1:k})$ is
already estimated, then a “predict-update” iterative procedure can be used to
compute the next frame’s position posterior $p(\phi_{k+1}|y_{1:k+1})$. First,
a one-step-ahead prediction is computed as:

$p(\phi_{k+1}|y_{1:k})=\sum_{\phi_{k}}p(\phi_{k+1}|\phi_{k})p(\phi_{k}|y_{1:k}),$
(2)

where $p(\phi_{k+1}|\phi_{k})$ is the state transition probability:

$p(\phi_{k+1}|\phi_{k})=\left\\{\begin{array}[]{ll}\gamma(\phi_{k})&\text{if
}\phi_{k+1}=1\\\ 1-\gamma(\phi_{k})&\text{if }\phi_{k+1}=\phi_{k}+1\\\
0&\text{otherwise }\end{array}\right.,$ (3)

where $\gamma(\phi_{k})$ is the normalized jump-back probability for the
pointer to jump from position $\phi_{k}$ back to the beat state. The pointer
can also move one step to the right with the probability of
$1-\gamma(\phi_{k})$, but no other transition is allowed.

Given the tempo range $[T_{min},T_{max}]$, the jump-back would only happen
between states $M(T_{max})$ and $M(T_{min})$, where the former is the least
possible number of frames within a beat and the latter is the maximum possible
number of frames. In other words, $\gamma({\phi_{k}})=0$ for
$\phi_{k}\in\\{1,2,...,M(T_{max})-1\\}$. Also, we set $\gamma(M(T_{min}))=1$
to guarantee that the probability mass never exceeds the last possible state.
For the rest of the states i.e.,
$\phi_{k-1}\in\\{M(T_{max}),M(T_{max})+1,...,M(T_{min})-1\\}$, jump-back
probabilities require updating.

Then the update step absorbs the newly observed audio frame as follows:

$p(\phi_{k+1}|y_{1:k+1})=\frac{1}{Z_{k+1}}p(y_{k+1}|\phi_{k+1})p(\phi_{k+1}|y_{1:k}),$
(4)

where $Z_{k+1}$ is the normalization constant, and the observation likelihood
$p(y_{k+1}|\phi_{k+1})$ is defined as:

$p(y_{k+1}|\phi_{k+1})\propto\left\\{\begin{array}[]{ll}b_{k+1}&\quad\text{if
}\phi_{k+1}=1\text{ and }b_{k+1}\geq T\\\
\epsilon&\quad\text{otherwise}\end{array}\right.,$ (5)

where the first branch is for the beat state, i.e., the pointer position
$\phi_{k}$ is at the left end of Fig. 1b. We also use a threshold $T$ to omit
frames that have too low beat activation $b_{k}$, which is computed from audio
features using a neural network [8] or other models. The second branch is for
the other states, and a small constant $\epsilon$ is assigned as the
likelihood.

###  2.4 Jump-back reward strategy

In this section, we introduce a method to update the jump-back probability
vector. It is noted that jump back technique should not be confused with back
tracking operation that is included in some dynamic programming offline
inferences such as that of Ellis [18]. The transition model used in the
prediction stage returns a portion of the position probability to the beat
state. For the update step, when the beat activation is larger than the
threshold, it increases the position probability of the beat state, and
decreases that of the other states. For
$\phi_{k+1}\in\\{M(T_{max}):M(T_{min})-1\\}$, updating the jump-back
probabilities is accomplished through an iterative equation with a forgetting
factor $\lambda$ at each frame using an update signal denoted by
$\Gamma(\phi_{k+1})$:

$\gamma(\phi_{k+1})=\lambda\gamma(\phi_{k})+(1-\lambda)\Gamma(\phi_{k+1}),\text{where}$
(6)
$\Gamma(\phi_{k+1})=\left\\{\begin{array}[]{ll}p(\phi_{k+1}|y_{1:k})-p(\phi_{k+1}|y_{1:k+1})\
\ \ \text{if }\ b_{k+1}\geq T\\\ \\\
-(p(\phi_{k}|y_{1:k})-p(\phi_{k+1}|y_{1:k}))\ \ \ \ \ \text{if }\ b_{k+1}<T\\\
\qquad\qquad\qquad\qquad\qquad\qquad\ \ \ \ \text{and}\ \phi_{k+1}=1\\\
0\qquad\qquad\qquad\qquad\qquad\qquad\ \ \ \ \text{otherwise}\\\
\end{array}\right..$ (7)

The first branch corresponds to the situation where the $(k+1)$-th frame is
likely a beat. It computes the amount of probability changes in the update
step, which are probability decreases for non-beat states. This probability
change would be informative in detecting the main loop (tempo), since the
higher contrast between before and after update stage indicates that from
which state the majority of the probability mass (frame phase) loops back. The
second branch corresponds to the situation where the $k+1$-th frame is not
likely a beat. It is the negative amount of probability mass that is jumped
back to the beat state in the prediction step. This wrong jump back would have
been avoided in an ideal case, and its negative value serves as a punishment
for the wrong jumps. The source code and video demos of the implementation are
available111https://github.com/mjhydri/1D-StateSpace.

##  3 Evaluation

To demonstrate the capability of the 1D state space, we implemented a causal
joint beat and downbeat tracking system using the proposed model. It is
important to note that the model does not require tempo and meter prior
knowledge and decodes them as well. The beat and downbeat activations are
obtained from the pre-trained neural networks in our previous BeatNet work
[8]. Also, The states’ probabilities and jump-back probabilities are
initialized randomly. Following the SOFA online methods, we employ the GTZAN
dataset to evaluate the performance of the proposed inference model. It is a
comprehensive dataset including 1000 excerpts from 10 different music genres.
Another reason that makes it more suitable for the evaluation is that it was
entirely unseen during the training stage of all reported supervised models.

Table 1 illustrates the beat and downbeat F-measure performance of several
online methods. To demonstrate the efficiency of the proposed model, the
processing time of each model is reported as well. The reported numbers are
the average computational time for 30-second music excerpts of the GTZAN
dataset. Note that we measure the speed of all methods on the same Windows
machine with an AMD Ryzen 9 3900X CPU and 3.80 GHz clock. For DLB [5] and
BeatNet [8], their paper-reported default number of particles is used, which
is 1000 and 1750, respectively.

Among all of the methods in Table 1, the new model and BeatNet [8] are joint
beat and downbeat tracking approaches, and the rest are only beat tracking
models. Also, except IBT [6] and Aubio [19], all the other models are
supervised, and they leverage deep neural networks to extract beat and/or
downbeat activations. Table 1 demonstrates that the proposed model can deliver
the same beat tracking F-measure performance as the BeatNet [8], which is the
SOFA online approach. However, its downbeat performance is moderately lower
than that of the BeatNet. The primary point is that using the proposed 1D
state space and the jump-back reward technique leads to a more than 30x
speedup than BeatNet, making it much more suitable for large scale industrial
usages.

Another interesting observation is that Aubio [19] is even faster than the
proposed model. The reason is that it is a classical signal processing model
and it does not use Bayesian temporal decoding at the inference stage. Its
main drawback, however, is its performance which is the lowest and suffering
from the common issues of the sliding window approaches [6]. DLB [5], on the
other hand, addresses the sliding window issues and delivers much better
results, but it is the slowest model. Finally, comparing the proposed model
with Böck FF [20, 21], which also performs exact inference instead of using a
sampling approach, we see that the proposed method achieves a similar
F-measure on beat tracking and a 7.5x speedup, even though the proposed model
is a multi-task approach that also performs downbeat tracking.

Table 1: Performance and speed comparison of several online beat and downbeat
tracking models on the GTZAN.
Method | F-Measure | F-Measure | Comp. Time
---|---|---|---
| Beats | Downbeats | (Seconds)
Aubio [19] | 57.09 | — | 0.1
BeatNet [8] | 75.44 | 46.49 | 8.87
Böck ACF [22] | 64.63 | — | 7.01
Böck FF [20] | 74.18 | — | 2.19
DLB [5] | 73.77 | — | 21.30
IBT [6] | 68.99 | — | 4.89
1D state space | 76.48 | 42.57 | 0.29

##  4 Conclusion and Future works

In this paper, we introduced a novel semi-Markov state space and a jump-back
reward technique to reduce the computational cost of music rhythmic analysis
tasks. This new state space is much smaller than the previous efficient space
in the literature. We also implemented an online model to infer several music
rhythmic parameters jointly. We showed that using the new state space along
with the new inference process delivers the SOFA results for beat tracking and
comparable results for downbeat tracking with a drastically faster speed.

## References

  * [1] A. Cont,  “A coupled duration-focused architecture for real-time music-to-score alignment,”  IEEE transactions on pattern analysis and machine intelligence, vol. 32, no. 6, pp. 974–987, 2009.
  * [2] Z. Duan and B. Pardo,  “A state space model for online polyphonic audio-score alignment,”  in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), 2011.
  * [3] K. Shibata, E. Nakamura, and K. Yoshii,  “Non-local musical statistics as guides for audio-to-score piano transcription,”  Information Sciences, vol. 566, pp. 262–280, 2021.
  * [4] S. Durand, J. P. Bello, B. D., and G. Richard,  “Robust downbeat tracking using an ensemble of convolutional networks,”  IEEE/ACM Transactions on Audio Speech and Language Processing, vol. 25, 2017.
  * [5] M. Heydari and Z. Duan,  “Don’t Look Back: An online beat tracking method using rnn and enhanced particle filtering,”  in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), 2021.
  * [6] J. L. Oliveira, F. Gouyon, L. G. Martins, , and L. P. Reis,  “IBT: A real-time tempo and beat tracking system,”  in Proc. of the 11th Intl. Conf. on Music Information Retrieval (ISMIR), 2010, pp. 291–296.
  * [7] S. Böck, F. Krebs, and G. Widmer,  “Joint beat and downbeat tracking with recurrent neural networks,”  in Proc. of the 17th Intl. Conf. on Music Information Retrieval (ISMIR), 2016, pp. 255–261.
  * [8] M. Heydari, F. Cwitkowitz, and Z. Duan,  “BeatNet: CRNN and particle filtering for online joint beat downbeat and meter tracking,”  in Proc. of the 22th Intl. Conf. on Music Information Retrieval (ISMIR), 2021.
  * [9] G. Peeters and H. Papadopoulos,  “Simultaneous beat and downbeat-tracking using a probabilistic framework: Theory and large-scale evaluation,”  IEEE Transactions on Audio, Speech, and Language Processing, vol. 19, August 2011.
  * [10] A. Srinivasamurthy, A. Holzapfel, A. Cemgil, and X. Serra,  “Particle filters for efficient meter tracking with dynamic bayesian networks,”  in Proc. of the 16th Intl. Conf. on Music Information Retrieval (ISMIR), 2015.
  * [11] S. Hainsworth and M.Macleod,  “Beat tracking with particle filtering algorithms,”  in Proc. IEEE Workshop on Applications of Sienal Proc. to Audio and Acoust., 2003.
  * [12] A. Cemgil and B. Kappen,  “Monte carlo methods for tempo tracking and rhythm quantization,”  Journal of Artificial Intelligence Research, vol. 18, pp. 45–81, March 2003.
  * [13] N. Whiteley, A. Cemgil, and S. Godsill,  “Sequential inference of rhythmic structure in musical audio.,”  in Proc. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), 2007.
  * [14] N. Whiteley, A. Cemgil, and S. Godsill,  “Bayesian modelling of temporal structure in musical audio,”  in Proc. of the 7th Intl. Conf. on Music Information Retrieval (ISMIR), 2006.
  * [15] F. Krebs, S. Böck, and G. Widmer,  “An efficient state-space model for joint tempo and meter tracking,”  in Proc. of the 16th Intl. Conf. on Music Information Retrieval (ISMIR), 2015, pp. 72–78.
  * [16] F. Krebs, S. Böck, , and G. Widmer,  “Rhythmic pattern modeling for beat and downbeat tracking in musical audio,”  in Proc. of the 14th Intl. Conf. on Music Information Retrieval (ISMIR), 2013, pp. 227–232.
  * [17] A. Holzapfel, F. Krebs, and A. Srinivasamurthy,  “Meter inference in a culturally diverse music corpus,”  in Proc. of the 18th Intl. Conf. on Music Information Retrieval (ISMIR), 2017, pp. 425–430.
  * [18] D. P. Ellis,  “Beat tracking by dynamic programming,”  Journal of New Music Research, vol. 36, no. 1, pp. 51–60, 2007\.
  * [19] P. M. Brossier,  “Automatic annotation of musical audio for interactive applications,”  pp. 58–102. Queen Marry University, London, UK, August 2006.
  * [20] S. Böck, F. Krebs, and G.Widmer,  “A multi-model approach to beat tracking considering heterogeneous music styles,”  in Proc. of the 15th Intl. Conf. on Music Information Retrieval (ISMIR), 2014, pp. 603–608.
  * [21] S. Böck, F. Krebs, A. Durand, S. Pöll, and R. Balsyte,  “ROBOD: a real-time online beat and offbeat drummer sebastian,”  in IEEE signal processing cup, 2017.
  * [22] S. Böck and S. Schedl,  “Enhanced beat tracking with context-aware neural networks,”  in Proc. of the 14th International Conference on Digital Audio Effects (DAFx-11), 2011, pp. 135–139.


which implicitly define the sheaf $\mathcal{M}$. The first one can be used to compute the cohomology of $\mathcal{M}$: in particular one finds that $H^1 (\mathcal{M} (k)) = 0$ for any $k$, so that the long exact cohomology sequence of the short exact sequence (<ref>) gives

0 [r]     H^0 (ℳ (k)) [r]     H^0 (𝒪_Y (k+1,k+1)^⊕8  ) [r]     H^0 (𝒩_Y (k) )  [r]     0.

Computing $H^0(\mathcal{M} (k))$ from (<ref>), one gets

\begin{align}
h^0 (\mathcal{N}_{Y}) & = \frac{1}{2}(k+3)^2(k+2)(k+5)
\end{align}

We now consider the conormal bundle. First it can be observed that the (<ref>) is a resolution via vector bundles. This means that every map has constant rank and dualizing gives again an exact sequence

\begin{equation}\label{resconormal}
0 \rightarrow \mathcal{N}^\vee_{Y} \xrightarrow{\epsilon^\vee}  \mathcal{O}_{Y} (-1,-1)^{\oplus 8} \xrightarrow{f^\vee}  \mathcal{O}_Y(-1,0)^{\oplus 2} \oplus \mathcal{O}_Y (0,-1)^{\oplus 4} \xrightarrow{\beta^\vee}  \mathcal{O}_Y \rightarrow  0.
\end{equation}

Once again the (<ref>) can be broken into two short exact sequences, namely

0 [r]     𝒩^∨_Y [r]     𝒪_Y (-1,-1)^⊕8 [r]     ℳ^∨[r]     0,

0 [r]     ℳ^∨[r]     𝒪_Y(-1,0)^⊕2 ⊕𝒪_Y (0,-1)^⊕4 [r]     𝒪_Y [r]     0.

We first need to study $\mathcal{M}^\vee$. We have the following commutative diagram.

0 [d]     0 [d]     0 [d]

0 [r]     𝒩^∨_Y [r] [d]^=     Ω^1_7|_Y [d] [r]     Ω^1_Y [d] [r]     0

0 [r]     𝒩^∨_Y [d] [r]     𝒪_Y (-1,-1) [d] [r]     ℳ^∨[d] [r]     0

0 [r]     𝒪_Y [d] [r]^≅     Q [r] [d]     0

0     0

Notice that $Q$ is of rank 1, hence $Q\cong \mathcal{O}_Y$, which shows that $\mathcal{M}^\vee$ is a (non split) extension

0 [r]     Ω^1_Y [r]     ℳ^∨[r]      𝒪_Y [r]     0.

Studying the cohomology of $\mathcal{M}^\vee (k)$ for $k\geq 1$ — when $\mathcal{N}^\vee_{Y}$ can have global sections —, one finds $H^1 (\mathcal{M}^{\vee} (k)) = 0$ and

\begin{align}
h^0 (\mathcal{M}^\vee (k)) & = h^0 (\Omega^1_Y (k)) + h^0 (\mathcal{O}_Y (k, k))
% &= (k-1) \left ( \binom{k+3}{k} + (k+1) \binom{k+2}{k} \right ) + (k+1) \binom{k+3}{3} \\
= 2k \binom{k+3}{3} + (k^2-1) \binom{k+2}{2}.
\end{align}

Going back to the conormal bundle $\mathcal{N}^\vee_{Y}$ and looking at the resolution twisted by $\mathcal{O}_Y(k)$ and split into the above two exact sequences (<ref>) and (<ref>) one has

\begin{align} \hspace*{-2cm}
\xymatrix@R=14pt{
%& & & & 0 \\
0 \ar[r] & \mathcal{N}^\vee_{Y} (k) \ar[r]^{\pi^\vee \qquad } &
\mathcal{O}_{Y} (k-1,k-1)^{\oplus 8} \ar@/^2pc/[rr]^{f^\vee} \ar[r]^{\qquad \quad \bar f^\vee} & \mathcal{M}^\vee(k) \ar[dr] \ar[r]^{ i \quad \qquad \qquad } &  \mathcal{O}_Y(k-1,k)^{\oplus 2} \oplus \mathcal{O}_Y (k,k-1)^{\oplus 4}
\ar[r]^{\qquad \quad \qquad \beta^\vee} & \mathcal{O}_Y (k,k)\ar[r] & 0\\
& &  0 \ar[ur] & & 0
\end{align}

where $\bar f^\vee$ is surjective and $i$ is injective.
Then, the long exact cohomology sequence of (<ref>) yields

\begin{equation}
0 \rightarrow   H^0 (\mathcal{N}^\vee_{Y}) \rightarrow H^0 (\mathcal{O}_{Y} (k-1,k-1)^{\oplus 8} ) \xrightarrow{ \bar{f}^\vee}  H^0 (\mathcal{M}^\vee(k)) \rightarrow H^1 (\mathcal{N}^\vee_{Y}) \rightarrow 0.
\end{equation}

Hence in particular,
H^1 (𝒩^∨_Y (k)) =  (H^0 (𝒪_Y (k-1,k-1)^⊕8 ) f̅^∨⟶ H^0 (ℳ^∨(k))),
so that

\begin{align}
h^1 (\mathcal{N}^\vee_{Y} (k)) &  = h^0 (\mathcal{M}^\vee (k)) - 8 h^0 (\mathcal{O}_Y(k-1, k-1)) + \dim ( \ker \bar f^\ast ).
\end{align}

Now, one has $f^\vee = i \circ \bar f^\vee$, but since $i $ is injective, then $\ker (f^\vee) = \ker (\bar f^\vee)$, where
f^∨:  𝒪_Y (k-1,k-1)^⊕8  →𝒪_Y(k-1,k)^⊕2 ⊕𝒪_Y (k,k-1)^⊕4.
This implies that

\begin{align} \label{h1}
h^1 (\mathcal{N}^\vee_{Y} (k)) & = h^0 (\mathcal{M}^\vee (k)) - 8 h^0 (\mathcal{O}_Y(k-1, k-1))  + \dim ( \ker (f^\vee )) \nonumber \\
& = 2k \binom{k+3}{3} + (k^2-1) \binom{k+2}{2} - 8k \binom{k+2}{3} + \dim (\ker (f^\vee))
\end{align}

Notice that $\dim (\ker (f^\vee) ) = h^0 (\mathcal{N}^\vee_{Y})$, hence the kernel of the maps yields the number of global sections of the conormal bundle. The map $f^\vee$ can indeed be described explicitly, and it is given by the transpose of $f$ introduced above for the normal bundle: it is a $6\times 8$ matrix given in the above affine cones coordinates
[f^∨] = [f]^⊤= (

x_0     x_1     x_2     x_3     0     0     0     0

0     0     0     0     x_0     x_1     x_2     x_3

u_0     0     0     0     u_1     0     0     0

0     u_0     0     0     0     u_1     0     0

0     0     u_0     0     0     0     u_1     0

0     0     0     u_0     0     0     0     u_1

In the special case $k=1$ the long exact cohomology sequence reads

\begin{equation}
0 \rightarrow H^0 (\mathcal{N}^\vee_{Y} (1)) \rightarrow H^0 (\mathcal{O}_Y^{\oplus 8}) \rightarrow H^0 (\mathcal{M}^\vee (1)) \cong H^0 (\mathcal{O}_Y (1,1)) \rightarrow H^1 (\mathcal{N}^\vee_{Y} (1) )\rightarrow 0.
\end{equation}

Here the middle map is an isomorphism, corresponding to the multiplication by $u_i x_j$. It follows that $H^0 (\mathcal{N}^\vee_{Y} (1)) \cong 0 \cong  H^1 (\mathcal{N}^\vee_{Y} (1)).$
In the remaining case, for $k\geq 2$, the kernel of the map $f^\vee$ in cohomology can be evaluated directly, and it yields
h^0 (𝒩^∨_Y (2)) = (f^∨_H^0) = 8k k+23 - 2k k+33 - (k^2-1) k+22.
so that in particular it follows from (<ref>) that $H^1 (\mathcal{N}^\vee_{Y}) = 0.$

Missing 'biblatex' package
The bibliography requires the 'biblatex' package.

title$D$-branes on Calabi–Yau manifolds

IOP Publishing

titleSuper-Poincaré covariant quantization of the superstring
journaltitleJournal of High Energy Physics

Springer Science
Business Media LLC

titleTowards covariant quantization of the supermembrane
journaltitleJournal of High Energy Physics

titleCohomology of Lie Superalgebras: Forms, Integral Forms and
Coset Superspaces

title$D=11$ supergravity with manifest supersymmetry
journaltitleMod. Phys. Lett. A

titlePure spinor superfields – an overview
journaltitleSpringer Proc. Phys.

titlePure spinor superspace action for $D = 6$, $\cN = 1$ super
Yang–Mills theory

titlePure spinors and $d= 6$ super Yang–Mills

noteto appear

titleTwisted supergravity and its quantization

American Institute of Physics

title$D$-branes, categories and $\N= 1$ supersymmetry
journaltitleJournal of Mathematical Physics

titlePerspectives on the pure spinor superfield formalism

titleNilpotence varieties
journaltitleAnnales Henri Poincaré

Springer-Verlag, New York

isbn0-387-94268-8; 0-387-94269-6
noteWith a view toward algebraic geometry
seriesGraduate Texts in Mathematics
titleCommutative algebra

titleThe derived pure spinor formalism as an equivalence of

titleTopological twists of supersymmetric algebras of observables
journaltitleCommunications in Mathematical Physics

titleThe Berkovits complex and semi-free extensions of Koszul
journaltitleAnn. Fac. Sci. Toulouse Math. (6)

titleFeynman rules in N=2 projective superspace: 1. Massless
journaltitleNucl. Phys. B

SIGMA. Symmetry, Integrability
Geometry: Methods

titleHomological algebra and divergent series
journaltitleSIGMA. Symmetry, Integrability and Geometry: Methods
and Applications

howpublishedAvailable at
titleMacaulay2, a software system for research in algebraic

noteGraduate Texts in Mathematics, No. 52
titleAlgebraic geometry
New York

titlePure spinor lines in superspace and ten-dimensional
supersymmetric theories
journaltitlePhysics Letters B

titlePure spinors, function superspaces, and supergravity theories
in ten and eleven dimensions
journaltitlePhysics Letters B

Oxford University Press

seriesOxford mathematical monographs
titleFourier-Mukai transforms in algebraic geometry

booktitleAlgebraic geometry
titleOn dg-modules over the de Rham complex and the vanishing
cycles functor

Cambridge University Press

seriesCambridge Tracts in Mathematics
titleSingularities of the Minimal Model Program

Elsevier BV

titleQuantum field theory as effective BV theory from
journaltitleNuclear Physics B

titleNew superconformal multiplets and higher derivative
invariants in six dimensions
journaltitleNucl. Phys. B

titleSix-dimensional Supergravity and Projective Superfields

We consider ten-dimensional supersymmetric Yang–Mills theory (10D SUSY YM
theory) and its dimensional reductions, in particular, BFSS and IKKT models.
We formulate these theories using algebraic techniques based on application
of differential graded Lie algebras and associative algebras as well as of
more general objects, L∞- and A∞-algebras. We show that using pure spinor
formulation of 10D SUSY YM theory equations of motion and isotwistor
formalism one can interpret these equations as Maurer–Cartan equations for
some differential Lie algebra. This statement can be used to write BV action
functional of 10D SUSY YM theory in Chern–Simons form. The differential Lie
algebra we constructed is closely related to differential associative algebra
(Ω,∂̄) of (0,k)-forms on some supermanifold; the Lie algebra is tensor
product of (Ω,∂̄) and matrix algebra. We construct several other algebras
that are quasiisomorphic to (Ω,∂̄) and, therefore, also can be used to
give BV formulation of 10D SUSY YM theory and its reductions. In particular,
(Ω,∂̄) is quasiisomorphic to the algebra (B,d), constructed by Berkovits.
The algebras (Ω0,∂̄) and (B0,d) obtained from (Ω,∂̄) and (B,d) by
means of reduction to a point can be used to give a BV-formulation of IKKT
model. We introduce associative algebra SYM as algebra where relations are
defined as equations of motion of IKKT model and show that Koszul dual to the
algebra (B0,d) is quasiisomorphic to SYM.

titleOn maximally supersymmetric Yang–Mills theories
journaltitleNuclear Physics B

titleHomology of Lie algebra of supersymmetries and of
super-Poincaré Lie algebra
journaltitleNucl. Phys. B

given=Bengt E.W.,

IOP Publishing

titlePure spinors as auxiliary fields in the ten-dimensional
supersymmetric Yang–Mills theory
journaltitleClassical and Quantum Gravity

titleOn the Geometry of Forms on Supermanifolds

titleA note on super Koszul complex and the Berezinian
journaltitleAnnali di Matematica Pura ed Applicata (1923-)

Springer New York, NY

titleVector Bundles on Complex Projective Spaces

titleTwisting pure spinor superfields, with applications to

titleFaisceaux algébriques cohérents
journaltitleAnnals of Mathematics

title$D$-branes, derived categories, and Grothendieck groups
journaltitleNuclear Physics B

titleFoundations of Algebraic Geometry
given=Marc A.A.,

howpublishedAvailable at
<http://www-math.univ-poitiers.fr/ maavl/LiE/>
titleLiE, A package for Lie group computations


# An effective estimate for the sum of two cubes problem

Saunak Bhattacharjee  Indian Institute of Science Education and Research,
Tirupati
Andhra Pradesh, India – 517619.
<EMAIL_ADDRESS>
###### Abstract.

Let $f(x,y)\in\mathbb{Z}[x,y]$ be a cubic form with non-zero discriminant, and
for each integer $m\in\mathbb{Z}$, let,
$N_{f}(m)=\\#\left\\{(x,y)\in\mathbb{Z}^{2}:f(x,y)=m\right\\}$. In 1983,
Silverman proved that $N_{f}(m)>\Omega\left((\log|m|)^{3/5}\right)$ when
$f(x,y)=x^{3}+y^{3}$. In this paper, we obtain an explicit bound for
$N_{f}(m)$, namely, showing that $N_{f}(m)>4.2\times 10^{-6}(\log|m|)^{11/13}$
(holds for infinitely many integers m), when $f(x,y)=x^{3}+y^{3}$.

###### 2020 Mathematics Subject Classification:

11G50

##  1\. Introduction

Let $f(x,y)\in\mathbb{Z}[x,y]$ be a cubic form with non-zero discriminant, and
for each integer $m\in\mathbb{Z}$, define

$N_{f}(m)=:\\#\left\\{(x,y)\in\mathbb{Z}^{2}:f(x,y)=m\right\\}.$

It has been a topic of interest to study how large can $N_{f}(m)$ be. In 1935,
Mahler [6] proved that

$N_{f}(m)>\Omega\left((\log|m|)^{1/4}\right),$

i.e., there exists a constant $c>0$, independent of $m$, such that for
infinitely many integers $m$,

$N_{f}(m)>c\,(\log|m|)^{1/4}.$

Invoking the theory of height functions, Silverman[1] extended the idea of
Mahler (Mordell, Pillai and Chowla[5]). This resulted in an improvement of the
exponent from $1/4$ to $1/3$ and simplification of calculation as well.

More specifically, restricting $f(x,y)=x^{3}+y^{3}$ , Silverman proved that,

$N_{f}(m)>\Omega\left((\log|m|)^{3/5}\right).$

In this short note, we are interested in the special case, when
$f(x,y)=x^{3}+y^{3}$. Using the methods employed by Silverman and exploiting
the properties of canonical height function on elliptic curves, we explicitly
capture the implied constant in the formula.

######  Theorem 1.1.

Let $f(x,y)=x^{3}+y^{3}\in\mathbb{Z}[x,y]$. Let $m_{0}\in\mathbb{Z}$ be a non
zero integer. Consider the curve $E$ with homogeneous equation

$E:f(x,y)=m_{0}\,z^{3}$

with the point $[1,-1,0]$ defined over $\mathbb{Q}$. Using that point as
origin, we give $E$ the structure of an elliptic curve. Let

$r=\operatorname{rank}E(\mathbb{Q})$

the rank of the Mordell-Weil group of $E/\mathbb{Q}$. Then the following
inequality holds for infinitely many integers $m$,

$N_{f}(m)>\frac{1}{(9\times
2^{r+1}-20)^{r/r+2}(\hat{h}(\bar{P}))^{r/r+2}}(\log|m|)^{r/(r+2)}$

Where $\hat{h}(\bar{P})$ denotes the Canonical height of a specified point
$\bar{P}$ on the elliptic curve $E^{\prime}:Y^{2}=X^{3}-432m_{0}^{2}$, defined
over $\mathbb{Q}$, with the base point $[0,1,0]$ at infinity.

As an immediate corollary, we have the following.

######  Corollary 1.1.

Let $f(x,y)=x^{3}+y^{3}\in\mathbb{Z}[x,y]$. Then the following inequality
holds for infinitely many integers $m$,

$N_{f}(m)>4.2\times 10^{-6}(\log|m|)^{11/13}$

##  2\. Preliminaries

We state and develop the necessary tools to prove our main theorem.

######  Lemma 2.1.

Let there exist integers $x$, $y$, $z$ and $m_{0}$, such that
$x^{3}+y^{3}=m_{0}z^{3}$ with $gcd(x,y,z)=1$, $gcd(12m_{0}z,x+y)=d$, then
$|d|<3^{1/3}12m_{0}^{5/2}|z|^{1/2}$.

###### Proof.

Let,

$da=12m_{0}z$ and $db=x+y$, where $gcd(a,b)=1$.

Now, our aim is to show that,

$d^{2}|3.12^{3}m_{0}^{2}b.$

Let, $p$ be a prime dividing $d$ and having the maximum power $k$ in $d$.

We will show that, $p^{2k}$ will always divide $3.12^{3}m_{0}^{2}b$.

As, $p^{k}|d\Rightarrow{p^{k}|12m_{0}z}$, we have two possible cases,

$p^{k}|12m_{0}$ or $p|z$

If $p^{k}|12m_{0}$, then we are done. So, it is enough to show when $p|z$.

We have,

$x^{3}+y^{3}=m_{0}z^{3}\Rightarrow
12^{3}m_{0}^{2}(x+y)((x+y)^{2}-3xy)=12^{3}m_{0}^{3}z^{3}$

$\Rightarrow 12^{3}m_{0}^{2}b(d^{2}b^{2}-3xy)=d^{2}a^{3}$

$\Rightarrow d^{2}|3.12^{3}m_{0}^{2}bxy$

now,

$p|d\Rightarrow p|x+y$

but,

on the other hand, we have $p|z$ and $gcd(x,y,z)=1$, which clearly implies
$p\nmid xy$.

As we have $d^{2}|3.12^{3}m_{0}^{2}bxy$, the primes dividing $d$ and not
dividing $xy$, should be completely contained in the factorisation of
$3.12^{3}m_{0}^{2}b$.

Hence,

$p^{2k}|3.12^{3}m_{0}^{2}b$ , for all prime $p$ dividing $d$ $\Rightarrow
d^{2}|3.12^{3}m_{0}^{2}b$.

$\Rightarrow|d|^{2}\leq 3.12^{3}m_{0}^{2}|b|\Rightarrow|d|^{3}\leq
3.12^{3}m_{0}^{2}|b||d|=3.12^{3}m_{0}^{2}|x+y|$

$\Rightarrow|d|^{6}\leq(3.12^{3}m_{0}^{2})^{2}(|x+y|)^{2}\leq(3.12^{3}m_{0}^{2})^{2}|x^{3}+y^{3}|=(3.12^{3}m_{0}^{2})^{2}m_{0}|z|^{3}$

$\Rightarrow|d|<3^{1/3}12m_{0}^{5/2}|z|^{1/2}.$

∎

Next, we state the following result due to Nèron and Tate from [2], which
gives the required properties of the canonical height, we are going to apply
in the proof of the theorem.

######  Lemma 2.2.

(Néron, Tate) Consider the canonical height or Nèron-Tate height denoted by
$\hat{h}$ on an elliptic curve $E/\mathbb{Q}$, defined as the following

$\hat{h}(P)=\frac{1}{2}\lim_{{k\to\infty}}\left(4^{-k}h_{x}\left([2^{k}]P\right)\right)$
where $h_{x}(P)=\log\left(H\left([x(P),1]\right)\right)$ , then

  1. (a)

For all $P,Q\in E(\overline{\mathbb{Q}})$ we have

$\hat{h}(P+Q)+\hat{h}(P-Q)=2\hat{h}(P)+2\hat{h}(Q)$

(parallelogram law).

  2. (b)

For all $P\in E(\overline{\mathbb{Q}})$ and all $m\in\mathbb{Z}$,

$\hat{h}([m]P)=m^{2}\hat{h}(P).$

  3. (c)

The canonical height $\hat{h}$ is a quadratic form on $E$, i.e., $\hat{h}$ is
an even function, and the pairing

$\langle\cdot,\cdot\rangle:E(\overline{\mathbb{Q}})\times
E(\overline{\mathbb{Q}})\to\mathbb{R},\quad\langle
P,Q\rangle=\hat{h}(P+Q)-\hat{h}(P)-\hat{h}(Q),$

is bilinear.

  4. (d)

Let $P\in E(\overline{\mathbb{Q}})$. Then $\hat{h}(P)\geq 0$, and
$\hat{h}(P)=0$ if and only if $P$ is a torsion point.

  5. (e)

$\hat{h}=\frac{1}{2}h_{x}+O(1),$

where the $O(1)$ depends on $E$ and $x$.

###### Proof.

See pp. $248-251$ [2]. ∎

Note that, in $(e)$ of Lemma 2.2, the implied constant is not explicit. In
1990, Silverman proved a general result which explicitly determines the
constant in terms of the $j$-invariant and discriminant of the elliptic curve.
From [3] we invoke a specific case of this result here.

######  Lemma 2.3.

Let, $E/\mathbb{Q}$ be an elliptic curve given by the Weierstrass equation

$y^{2}=x^{3}+B$ , then for every $P\in E(\bar{\mathbb{Q}})$

$-\frac{1}{6}h(B)-1.48\leq\hat{h}(P)-\frac{1}{2}h_{x}(P)\leq\frac{1}{6}h(B)+1.576$

###### Proof.

See pp. $726$ [3] . ∎

Once we have the lower bound of $N_{f}(m)$ in theorem 1.1, the explicit lower
bound in corollary 1.1 follows from the existence of a specific elliptic curve
of rank 11, which is recently given by Elkies and Rogers in [4]. We state this
result as a proposition below.

######  Proposition 2.1.

The elliptic curve given by the equation

$x^{3}+y^{3}=m_{0}z^{3}$ or the Weierstrass form $Y^{2}=X^{3}-432m_{0}^{2}$

where, $m_{0}=13293998056584952174157235$ , has the Mordell-Weil rank $11$.

Moreover, $\max\\{h_{x}(P_{i})\mid 1\leq i\leq 11\\}=76.61$ where $P_{i}$
varies over $11$ independent points of the Mordell-Weil group.

###### Proof.

For the construction of this elliptic curve and the list of 11 independent
points; see pp. 192-193 [4] . The rest follows by simple computation. ∎

##  3\. Proof of theorem 1.1 and corollary 1.1

We are given, that the elliptic curve $E/\mathbb{Q}$

$E:x^{3}+y^{3}=m_{0}z^{3}$

with the base point $[1,-1,0]$ has the Mordell-Weil rank $r$.

Observe that, any non-torsion point $Q=[x(Q),y(Q),z(Q)]\in E(\mathbb{Q})$ has
$z(Q)\neq 0$ as the only point in $E(\mathbb{Q})$ with $z(Q)=0$ is
$Q=[1,-1,0]$, the identity of the Mordell-Weil group $E(\mathbb{Q})$.

As the rank of $E(\mathbb{Q})$ is $r$, we can choose $r$ independent points
$P_{1},...,P_{r}$ from the free part of the group $E(\mathbb{Q})$ and for any
point $Q\in E(\mathbb{Q})$, we will always write $Q=[x(Q),y(Q),z(Q)]$ with
$x(Q),y(Q),z(Q)\in\mathbb{Z}$ and $gcd\left(x(Q),y(Q),z(Q)\right)=1$.

Now fix a large positive integer $N$ and for each
$n=(n_{1},...,n_{r})\in\mathbb{Z}^{r}$ with $1\leq n_{i}\leq N$, consider the
sum

$Q_{n}=n_{1}P_{1}+...+n_{r}P_{r}$

which gives $N^{r}$ distinct points in $E(\mathbb{Q})$.

Now consider

$m=m_{0}\prod_{n}z(Q_{n})^{3},$

where the product runs over all $r-$tuples $(n_{1},...,n_{r})$. Note that,
$m\neq 0$ as $z(Q_{n})\neq 0$.

Hence for each $r$-tuple $n^{\prime}=(n_{1}^{\prime},...,n_{r}^{\prime})$, the
equation $f(x,y)=x^{3}+y^{3}=m$ has the following integral solution

$(x,y)=\left(x(Q_{n^{\prime}})\prod_{n\neq
n^{\prime}}z(Q_{n})^{3},y(Q_{n^{\prime}})\prod_{n\neq
n^{\prime}}z(Q_{n})^{3}\right).$

From this, we immediately get

$N_{f}(m)>N^{r}$.

Now, we will use the properties of height functions to give an upper bound for
$m$ in terms of $N$. To do this in an explicit manner, we will first transform
the elliptic curve $E/\mathbb{Q}$ into it’s Weierstrass form and then will
proceed by using the explicit properties of the height functions on that
Weierstrass form.

Consider the following morphism which takes $E/\mathbb{Q}$ to it’s Weierstrass
form $E^{\prime}/\mathbb{Q}$

$\Phi:E\rightarrow E^{\prime}$

defined as

$\Phi([x,y,z])=\begin{cases}\left[12m_{0}\,\frac{z}{y+x},\,36m_{0}\,\frac{y-x}{y+x},1\right],&z\neq
0,\\\ [0,1,0],&z=0.\end{cases}$

where $E^{\prime}:Y^{2}=X^{3}-432\,m_{0}^{2}$ denotes the Weierstrass form of
$E:x^{3}+y^{3}=m_{0}z^{3}$.

Note that, $\Phi$ induces a group homomorphism $\Phi:E(\mathbb{Q})\rightarrow
E^{\prime}(\mathbb{Q})$ of the corresponding Mordell-Weil groups.

Let $Q_{n}=[x(Q_{n}),y(Q_{n}),z(Q_{n})]\in E(\mathbb{Q})$ as above. Then the
height (with respect to $x$) of $Q_{n}$ under $\Phi$ is given by

$h_{x}\left(\Phi(Q_{n})\right)=h\left(x\left(\Phi(Q_{n})\right)\right),$

where $h(x(P)=\log\left(H\left([x(P),1]\right)\right)$, $H$ is the height on
$\mathbb{P}^{1}(\mathbb{Q})$ [2, pp. 234].

As $z(Q_{n})\neq 0$, we have

$x\left(\Phi(Q_{n})\right)=12m_{0}\frac{z(Q_{n})}{y(Q_{n})+x(Q_{n})}$

for simplicity we will write $x,y,z$ respectively for $x(Q_{n}),y(Q_{n})$ and
$z(Q_{n})$.

Hence, we can write

$\displaystyle h_{x}\left(\Phi(Q_{n})\right)$
$\displaystyle=\log\left(H\left([12m_{0}\frac{z}{y+x},1]\right)\right)$
$\displaystyle=\log\left(H\left([12m_{0}z,x+y]\right)\right)$
$\displaystyle=\log\left(\text{max}\\{|\frac{12m_{0}z}{d}|,|\frac{x+y}{d}|\\}\right)$

where, $d=gcd(12m_{0}z,x+y)$ and
$\log\left(\text{max}\\{|\frac{12m_{0}z}{d}|,|\frac{x+y}{d}|\\}\right)\geq\log\left(\frac{|12m_{0}z|}{|d|}\right)$.

So, clearly

$h_{x}\left(\Phi(Q_{n})\right)+\log(|d|)\geq\log(12|m_{0}|)+\log(|z|).$

Now, using Lemma 2.1 we have

$h_{x}\left(\Phi(Q_{n})\right)\geq b_{m_{0}}+\frac{1}{2}\log(|z|)$

where, $b_{m_{0}}$ is a constant depending on $m_{0}$.

Further, using (e) of Lemma 2.2, we have

$\log(|z|)\leq 4\hat{h}(\Phi(Q_{n}))+c_{m_{0}}$

where, $c_{m_{0}}$ is another constant depending on $m_{0}$.

As, $\Phi:E(\mathbb{Q})\rightarrow E^{\prime}(\mathbb{Q})$ is group
homomorphism,

$\hat{h}\left(\Phi(Q_{n})\right)=\hat{h}\left(\sum_{i=1}^{r}n_{i}\Phi(P_{i})\right)$.

Now, using (a), (b) and (d) of Lemma 2.2, we have the following estimate for
$\hat{h}$.

$\displaystyle\hat{h}(\Phi(Q_{n}))\leq(3\times
2^{r-1}-2)\max\\{\hat{h}(n_{i}\Phi(P_{i}))\mid 1\leq i\leq r\\}$
$\displaystyle\leq(3\times 2^{r-1}-2)N^{2}\max\\{\hat{h}(\Phi(P_{i}))\mid
1\leq i\leq r\\}$

For simplicity of notation, write $\max\\{\hat{h}(\Phi(P_{i}))\mid 1\leq i\leq
r\\}=\hat{h}(\bar{P})$, $\bar{P}=\Phi(P_{i})$ for some $i$.

Hence, altogether we have

$\displaystyle\log(|z(Q_{n})|)$ $\displaystyle\leq 4(3\times
2^{r-1}-2)N^{2}\hat{h}(\bar{P})+c_{m_{0}}$ $\displaystyle\leq(3\times
2^{r+1}-7)N^{2}\hat{h}(\bar{P})$

as we can choose a large $N$ such that $c_{m_{0}}\leq N^{2}\hat{h}(\bar{P})$.

Now, we have total $N^{r}$ points $Q_{n}$ on $E(\mathbb{Q})$, so for large
enough $N$,

$\log|m|=3\sum_{n}\log|z(Q_{n})|+\log(|m_{0}|)\leq(3^{2}\times
2^{r+1}-20)N^{r+2}\hat{h}(\bar{P}).$

So, clearly we have the following estimate

$N_{f}(m)>N^{r}\geq\frac{1}{(9\times
2^{r+1}-20)^{r/r+2}(\hat{h}(\bar{P}))^{r/r+2}}(\log|m|)^{r/(r+2)}$

which concludes the proof of theorem 1.1, because we can choose arbitrarily
large $N$, giving infinitely many choices for $m$.

The proof of the corollary 1.1 follows by using the elliptic curve of
Proposition 2.1 in Theorem 1.1. Observe that, using Lemma 2.3 on the elliptic
curve $Y^{2}=X^{3}-432m_{0}^{2}$ with $m_{0}=13293998056584952174157235$, we
have

$\hat{h}(\bar{P})\leq 121.767/6+76.61/2+1.576=60.17$

by putting $r=11$, we have the required estimate holding for infinitely many
integers $m$

$N_{f}(m)>4.2\times 10^{-6}(\log|m|)^{11/13}.$

##  4\. Concluding remarks

It will be interesting to know, if a similar explicit bound can be obtained
for other cubic forms as well. The key idea is to get a result similar to
Lemma 2.1 for a general form, then using the similar methods in this article
an explicit bound can be obtained. In our case, for $f(x,y)=x^{3}+y^{3}$, the
computation turned out to be much simpler which can be a bit complicated for
other forms.

## Acknowledgments

I am thankful to Dr. Anup Dixit and Sushant Kala for their invaluable support,
guidance and numerous fruitful discussions. I would also like to thank The
Institute of Mathematical Sciences, Chennai(HBNI) for supporting my stay as a
visiting student.

## References

  * [1] Silverman, J.H., 1983. Integer points on curves of genus 1. Journal of the London Mathematical Society, 2(1), pp.1-7.
  * [2] Silverman, J.H., 2009. The arithmetic of elliptic curves (Vol. 106, pp. xx+-513). New York: Springer.
  * [3] Silverman, J.H., 1990. The difference between the Weil height and the canonical height on elliptic curves. Mathematics of computation, 55(192), pp.723-743.
  * [4] Elkies, N.D. and Rogers, N.F., 2004. Elliptic curves x 3+ y 3= k of high rank. In Algorithmic Number Theory: 6th International Symposium, ANTS-VI, Burlington, VT, USA, June 13-18, 2004, Proceedings 6 (pp. 184-193). Springer Berlin Heidelberg.
  * [5] A. CHOWLA, 1933. Contributions to the analytic theory of numbers (II), J. Indian Math. Soc, 20, pp. 120—128.
  * [6] Mahler, K., 1935. On the lattice points on curves of genus 1. Proceedings of the London Mathematical Society, 2(1), pp.431-466.


# Modeling human road crossing decisions as reward maximization with visual
perception limitations

Yueyang Wang1⋆, Aravinda Ramakrishnan Srinivasan1, Jussi P.P. Jokinen2, Antti
Oulasvirta3, Gustav Markkula1
1 University of Leeds, UK 2 University of Jyväskylä, Finland 3 Aalto
University, Finland ∗ Corresponding author<EMAIL_ADDRESS>project
has received funding from UK Engineering and Physical Sciences Research
Council under fellowship COMMOTIONS - Computational Models of Traffic
Interactions for Testing of Automated Vehicles - EP/S005056/1.

###### Abstract

Understanding the interaction between different road users is critical for
road safety and automated vehicles (AVs). Existing mathematical models on this
topic have been proposed based mostly on either cognitive or machine learning
(ML) approaches. However, current cognitive models are incapable of simulating
road user trajectories in general scenarios, and ML models lack a focus on the
mechanisms generating the behavior and take a high-level perspective which can
cause failures to capture important human-like behaviors. Here, we develop a
model of human pedestrian crossing decisions based on computational
rationality, an approach using deep reinforcement learning (RL) to learn
boundedly optimal behavior policies given human constraints, in our case a
model of the limited human visual system. We show that the proposed combined
cognitive-RL model captures human-like patterns of gap acceptance and crossing
initiation time. Interestingly, our model’s decisions are sensitive to not
only the time gap, but also the speed of the approaching vehicle, something
which has been described as a “bias” in human gap acceptance behavior.
However, our results suggest that this is instead a rational adaption to human
perceptual limitations. Moreover, we demonstrate an approach to accounting for
individual differences in computational rationality models, by conditioning
the RL policy on the parameters of the human constraints. Our results
demonstrate the feasibility of generating more human-like road user behavior
by combining RL with cognitive models.

###### Index Terms:

Human behavior, computational rationality, noisy perception, reinforcement
learning

##  I Introduction

The interaction between road users is defined as “a situation where the
behavior of at least two road users can be interpreted as being influenced by
the possibility that they are both intending to occupy the same region of
space at the same time in the near future” [1]. Interdependence between
vehicles and pedestrians makes interactions between road users instrumental
for road safety and automated vehicles(AVs), which pushes the research into
road user interaction.

Pedestrian is the most vulnerable group among all road users [2], and their
behavior is difficult to predict. How drivers may behave is limited by the
machinery of a vehicle and traffic rules, whereas pedestrians have more
freedom, and are limited only by traffic rules. To better understand
pedestrian behavior, some detailed metrics related to crossing behavior were
investigated [3, 4, 5]. For example, gap acceptance, where the gap is defined
as the time or spatial distance between the pedestrian and approaching
vehicle, is an important metric for understanding the crossing decision [3].
Lobjois and Cavallo [4] found that speed-dependent gap acceptance was shown in
different age groups i.e., the gap acceptance rate was higher when the
approaching vehicle was faster in a given time gap. Petzoldt [5] investigated
the relationship between gap acceptance and time to arrival (TTA) estimation.
They speculated that speed-dependent crossing decisions were caused by the
biased TTA estimation. Another important factor affecting the safety of
crossing is cross initiation time (CIT). Tian et al. [3] observed that CIT was
greater when the vehicle was driven at a higher speed for any given initial
TTA, which led to unsafe behavior.

A descriptive study of road user behavior is insufficient for AVs to
understand and predict other road users’ actions; therefore, mathematical
models of road user behavior are required for AVs [6]. In recent years, many
mechanistic models have been proposed to generate and understand pedestrian
behavior. For example, rule-based models, such as the social force model, were
successful in traffic flow simulation [7, 8]. However, they are limited in
capturing the details of road user interactions. To generate more explainable
and accurate road user interactive behavior, cognitive models, such as the
evidence accumulation model, were utilized to model pedestrian crossing
decisions [9, 10].

With increased computing power and more available data, machine learning (ML)
models have gained increasing attention for road user behavior prediction.
Long Short-Term Memory (LSTM), a variant of Recurrent Neural Networks (RNN),
was used in pedestrian trajectory prediction [11]. To better predict the
interactive behavior between pedestrians, Alahi et al proposed a ‘Social
LSTM’, with a social layer into the LSTM algorithm, and the model outperformed
state-of-the-art methods [12].

Many efforts have been made to understand and simulate the microscopic
behavior of road users. ML models can reproduce accurate trajectories across a
diverse range of scenarios, and cognitive models can provide the
interpretability of the interactive behavior and the underlying mechanism.
However, both streams of methods have some limitations. In conventional
cognitive models, the modeler should define how the specific task is completed
and the model should be updated if the environment and task change. This makes
it difficult to simulate road users’ trajectories in general scenarios.
Whereas ML models focus on the minimization of high-level error metrics,
rather than the mechanisms generating the behavior or whether the aspects of
behavior that are important to humans are being captured. Sometimes the model
with high accuracy does not necessarily generate realistic human behavior
[13].

Computational rationality, as a general approach of modeling human behavior,
has shown promising properties in modeling human-computer interaction (HCI)
[14]. This framework is based on the idea that human behaviors are generated
by cognitive mechanisms that are adapted to the structure both of the
environment and the mind and brain itself [15]. In this paper, we developed a
model of human pedestrian crossing decisions based on computational
rationality, using deep reinforcement learning (RL) to adopt optimal behavior
policies given human-like constraints. We show that when we constrain the
agent by a simple model of human visual perception, it reproduces human gap
acceptance behavior qualitatively, including the speed-dependencies, which
have not been previously considered as rational behavior. We also demonstrate
an approach to using computational rationality to model individual
differences, by conditioning RL on the parameters of human constraints.

##  II Method

###  II-A Dataset

The dataset used for validation was collected in the previous experiment
reported by Giles et al. [10]. Figure 1 shows a birds-eye view of the
experiment. A brief summary of the experimental setup is provided below. 20
participants were recruited for the experiment. In the experiment, they wore
an HTC Vive Virtual Reality (VR) headset and experienced the virtual crossing
task. The VR environment consisted of a straight two-lane road with a total
width of $5.85$ m, with a zebra crossing at the participant’s location.

In terms of the experimental procedure, participants stood in front of the
zebra crossing. When participants were ready to start the trial, they turned
their head to the right to trigger the scene. A car at the predefined initial
position $d_{0}$ would approach the participant at different speeds $v_{0}$.
The experiment included a mix of scenarios; in this paper, we will only
consider the scenarios where the speed of the approaching vehicle was
constant. The detail of these scenarios is shown in TABLE I, where also the
initial time to arrival (TTA) $\tau_{0}=d_{0}/v_{0}$ is listed. Participants
pressed the button on the HTC Vive’s controller when they felt safe to cross.
Upon this button press, CIT was recorded, and the location of the participant
in the virtual environment moved across the zebra crossing at the speed of
$1.31$ m/s. This button-press approach was chosen in favor of physically
crossing the road, to reduce the impact of variability in motor constraints on
the crossing decision. Each participant experienced $6$ different constant-
speed trials. Therefore, $120$ data trials were used for the validation of the
model.

Figure 1: Birds-eye view of the experiment.

###  II-B Model

This research aims to model the pedestrian crossing decision under the
assumption that human behaves rationally within limits. Therefore, two models
were compared, as shown in Figure 2. One is the ideal observer crossing model,
in which the agent has perfect information about the environment. Another is
the model considering the visual limits. In this model, the agent perceives
the environment subject to noise, but Bayes-optimal perception.

TABLE I: Vehicle approach scenarios $v_{0}~{}m/s$ | $d_{0}~{}(m)$ | $\tau_{0}~{}(s)$
---|---|---
$6.94$ | $15.90$ | $2.29$
$13.89$ | $31.81$ | $2.29$
$6.94$ | $31.81$ | $4.58$
$13.89$ | $63.61$ | $4.58$
$6.94$ | $47.71$ | $6.87$
$13.89$ | $95.42$ | $6.87$

####  II-B1 Noisy perception

We assume the agent has a noisy perception of the state of vehicles and
perfect knowledge about their own state.

##### Noisy visual input

The observation obtained by the agent is according to the principle of the
human visual system, i.e., the sensory input received by our human visual
system is noisy [16]. It is important to consider the nature of this noise;
here we are building on models which assume that visual noise is introduced at
the level of the human retina, as angular noise [17]. In the current model, we
assume that the agent observes the position of the other agent along its line
of travel by observing the angle below the horizon of the other agent [18,
19], with a constant Gaussian noise of standard deviation $\sigma_{v}$. In
practice, this means that the pedestrian observes the position of the vehicle
with a distance-dependent noise of standard deviation
$\sigma_{x}(k)=f_{v}[x(k)]$, where $x(k)$ is the true world state, and:

$f_{v}[x(k)]=|d_{l}|\left(1-\frac{h}{d\cdot\tan(\arctan\frac{h}{d}+\sigma_{v})}\right),$

where $d_{l}$ is the longitudinal distance between the pedestrian agent and
the crossing point, $d$ is the distance between the agent and the approaching
vehicle, $h$ is the eye height over the ground of the ego agent, which is set
to $1.6$ m for all pedestrian agents for simplicity, and $\sigma_{v}$ could
vary between pedestrians.

Figure 2: Comparison of models. (a) Ideal observer model, where the agent had
full information about the environment. (b) Model with visual limitations. Two
variants were developed. One was the model without noise magnitude parameter.
Another was the model with noise magnitude parameter, as shown in the orange
dashed box.

##### Kalman filter

There is psychophysical evidence that human perception system works like a
Bayesian optimizer, and Bayesian methods have been successful in modeling
perception and sensorimotor control [17, 20]. Therefore, we used a Kalman
Filter as a model of the human visual perception to percept the environment
[19]. In our model, we initialized the Kalman filter with a noisy position of
the vehicle, and a noisy velocity centered at the true velocity with a
standard deviation of all velocity values. At each step, the Kalman filter
received the noisy position about the other agent, and the output, i.e., the
filtered position and velocity of the vehicle, and the variance of the
position and the velocity, was the input of the RL agent.

####  II-B2 Reinforcement learning model

In our model, in line with the theory of computational rationality, we view
pedestrian behavior as a Partially Observable Markov Decision Process (POMDP)
under bounds posed by perception. RL algorithm, where the agent interacts with
the environment and learns the optimal strategy by trial and error, can be
used to derive the boundedly optimal policy for this type of problem [14, 21].

##### State space $S$

The time step in the simulation affects the resolution of the results of the
decision time. In our mode, one time step corresponds to $0.1$ seconds, which
is suitable for the dataset we are using. At each time step t, the environment
is in a state $s_{t}\in S$. A state contains true information about the
vehicle and the agent, i.e., the position and velocity of the vehicle and the
agent.

##### Action space $A$

At each time step t, the agent takes an action $a_{t}\in A$. In this paper, in
line with the button press in the experiment, the agent can make the decision
to Go or Not Go. If the Go decision is made, the agent will go straight at the
speed of $1.31~{}m/s$, as in the experiment, resulting either in a successful
crossing or in a collision, and the scenario will finish.

##### Reward $R$

In the experiment where the datasets were collected, the participant’s task
was to cross the road as soon as they felt safe to do so, either before or
after the car had passed them [22]. Therefore, in our model we want the agent
to cross the road in as short a time as possible without a collision. At each
time step t, the agent will receive a negative reward of $0.5\times
simulationsteps$, which helps the agent to cross the road faster. The agent
will be given a reward of $200$ when crossing the road without collision, and
a reward of $-200$ if a collision happens. The form of this reward function
was chosen based on some initial testing. As the focus of this study is on the
potential effect of noisy perception on the crossing decision, we kept the
reward function simple; future work can further refine it to better capture
human preferences.

##### Observation space $O$

The agent receives observation $o_{t}\in O$ at each time step. In the ideal
observer model, the agent gets the complete information about the environment.
In the model with visual limits, the agent only observes partial information
about the state of the environment. At each time step, the agent receives the
processed estimates of the position and velocity and uncertainty about the
position and velocity of the other agent from the Kalman Filter and the exact
position and velocity of the ego agent.

Figure 3: Gap acceptance rate by human participants and different models. See
the main text for explanations of the model abbreviations.

##### Transition function $T$

The transition function defines how the current state $s_{t}$ changes to the
next state $s_{t+1}$ taking action $a_{t}$. In our model, if Not Go action is
chosen, the vehicle will move according to the kinematic equations with the
given speed, and the position of the agent will not change. Once Go action is
chosen, whether the collision happens will be calculated, and the
corresponding reward will be given to the agent. Then, the simulation
finishes.

##### Deep Q-Networks

Deep-Q Network (DQN) is a method using the neural network to learn the optimal
policy to maximize the state-action function (Q function), $Q(s,a)$, the
expected rewards for an action taken in a given state [23]. DQN is suitable
for the problem with a continuous state space and a discrete action space. For
the extensibility of the model to more complex situations, we utilized an
enhanced version of DQN, Double DQN (DDQN). The Double DQN (DDQN) structure,
which decouples the update of the neural network parameter for action
selection and evaluation, can avoid the overestimation of the action value
[23]. Furthermore, the dueling network was used, in which the Q-function is
decoupled to a value function and a state-dependent action advantage $A(s,a)$
function. Compared with the single-stream DQN, the Duelling DQN shows better
performance especially when different actions lead to a similar value because
of the consideration of the state value in the Q value [24]. We trained the
agent through a two-layer fully connected network, with $512$ and $256$ nodes.
The learning rate and discount factor are $0.001$ and $0.99$ respectively. To
explore the optimal policy, an $\epsilon$ \- greedy algorithm was used for
exploration: At each time step $t$, a random action is chosen with probability
$\epsilon$, and the action with maximum Q value is chosen with probability
$1-\epsilon$. We decreased $\epsilon$ by $10^{-4}$ in each learning step. The
minimum value was set to $0.001$.

###  II-C Training and fitting

As we don’t know the correct value for $\sigma_{v}$, and additionally each
participant in the experiment may have an individual $\sigma_{v}$, we trained
the model for different $\sigma_{v}$ ranging from $0-1$ with a step size of
$0.002$. We trained the model in two different ways. First, we trained a
separate model for each $\sigma_{v}$. With this approach, for any given
$\sigma_{v}$, we can get a boundedly optimal policy from the model trained
with that $\sigma_{v}$. This approach is somewhat inconvenient and will not
scale well to more complete models of human constraints, with more parameters
than just one. Therefore, as an alternative approach, we instead trained just
a single model, across all of the different $\sigma_{v}$, and in this case we
also provided $\sigma_{v}$ as an input to the model, as illustrated by the
dashed line in Figure 2. In other words, we conditioned the RL on
$\sigma_{v}$. With this approach, for any given $\sigma_{v}$, we get a
boundedly optimal policy from this single model, by also giving it
$\sigma_{v}$ as an input.

With the $1.31~{}m/s$ walking speed used in the experiment, it is in fact
possible to cross before the vehicle without collision even for the lowest TTA
of $2.29~{}s$. To avoid our agents learning this trivial policy of always just
immediately crossing, in the model training we also included a lower TTA of
$1~{}s$, in which the agent did not have enough time to cross safely before
the vehicle.

We used three criteria to identify model convergence and stop training:(1) the
collision rate is less than or equal to $0.01$, which means one collision at
most happened in the last $100$ episodes; (2) $\epsilon$ has reached the
lowest value of the epsilon-greedy algorithm; (3) the difference in average
reward between the last $100$ episodes and the last $200$ to $100$ episodes is
less than $1$ to make sure that the average reward does not improve much and
becomes stable and converged.

We also identified the $\sigma_{v}$ that fitted the experimental data best for
each participant by likelihood maximization. We estimated the probability
density function (PDF) of CIT predicted for each model by kernel density
estimation, separately for each of the six scenarios (Table 1). This allowed
us to calculate the model likelihood of each $\sigma_{v}$ for each
participant, by multiplying the model PDF values at the participant’s observed
button press times. Finally, we combined all the PDFs from the different
participants, with tuned $\sigma_{v}$. We applied this method to both model
types, i.e., separate models for each $\sigma_{v}$, and a single model for all
$\sigma_{v}$. In addition to this per-participant fit, we also selected one
$\sigma_{v}$ from the models with separate $\sigma_{v}$, which best fitted the
entire dataset.

Abbreviations will be introduced here for referring to different model
variants; e.g., EXP: experimental data; IO: ideal observer model; LMD:
multiples model with separate visual limits parameter and one $\sigma_{v}$
fitted across the entire dataset; LMP: multiple models with separate visual
limits parameter and different $\sigma_{v}$ fitted per participant; LSP: one
model with different visual limits parameters and different $\sigma_{v}$
fitted per participant.

##  III Results

###  III-A Experimental results

First, we reanalyzed the experimental data reported by Pekkanen et al. [22].
As shown in the first panel on the left in Figure 3, this experiment
replicated the general finding that the gap acceptance rate strongly depended
on initial TTA, i.e., more pedestrians crossed before the car when there was a
larger time gap. In addition, we can observe the speed-dependent gap
acceptance rate, i.e., for a given initial TTA, more pedestrians accepted the
gap if the speed was higher [3, 4]. This effect was strongest at the initial
TTA of $4.6~{}s$. Regarding CIT, which is shown in the first row in Figure 4,
there was some spread in CIT, both when crossing before and after the car.

###  III-B Behavior of the model

The results of the model without visual limits (IO) are shown in the second
panel on the left in Figure 3 and the second row in Figure 4. In the model
without visual limits, the agent had full information about the environment,
and crossed the road without collision in the shortest time. Therefore, as
shown in the second row of Figure 4, the agent always started to cross at the
first time step when it was safe. The second panel in Figure 3 shows that the
agent always accepted the gap in $2.3~{}s$, $4.6~{}s$, and $6.9~{}s$ initial
TTA conditions.

Figure 4: Cumulative probability for CIT. The four columns show different
initial TTA conditions. See the main text for explanations of the model
abbreviations. (Note: CDF curves are extended to the right after after the
cumulative probability reaches $y=1$.) Figure 5: Distributions of initial
estimated TTA from the output of the visual perception model, across the
different scenarios in the experiment.

The three graphs on the right in Figure 3, and the last three rows in Figure 4
show the results of the models with visual limits. In models with visual
limits, the agent received the processed information of the Kalman filter
instead of the exact information about the environment.

As shown in Figure 3, the models with visual limits captured the pattern of
the gap acceptance rate observed in the experiment. The TTA-dependent gap
acceptance rate, i.e., the gap acceptance rate increased with the initial TTA,
was predicted by all three model types. Unexpectedly, the difference within
the same TTA group was also captured by the model. The agent was more likely
to accept the gap when the vehicle speed was higher in the given initial TTA.
This pattern was shown by all model types. Overall, the model has a slightly
greater tendency to accept gaps than the human participants. This may be what
is causing the model to show a speed dependency at $2.3~{}s$ TTA (because the
model sometimes crosses there, whereas the humans almost never did), but not
at $6.9~{}s$ TTA (because the model has already reached full gap acceptance at
this TTA, which the humans had not).

####  III-B1 Variability within and between individuals

From Figure 4, there was some spread in CIT also for model LMD – i.e., the
model showed some within-individual variability – due to the trial-to-trial
variability in visual noise. That model LMP, with different $\sigma_{v}$ for
different participants, came closer to capture the human variability,
suggesting that some of the variability in the human data is from between-
individual differences.

To test this, we did the Akaike Information Criterion (AIC) analysis of LMD,
LMP, and LSP. AIC, which considers both the log-likelihood and the cost of
more parameters, allows us to compare the performance of different models, and
the preferred model is the one with the minimum AIC value [25]. The AIC values
are $113$, $57$, and $79$ for the LMD, LMP and LSP respectively. Therefore,
LMP, the model with different individual $\sigma_{v}$, outperformed other
model variants. This suggested that some of the variability in human CIT is
due to between-individual variability in sensory noise.

####  III-B2 Speed-dependent gap acceptance

To investigate the reason why the model showed speed-dependence in its gap
acceptance rate, we calculated the estimated TTA through the velocity and
position estimated by Kalman filter at the first time step. Figure 5 shows the
distribution, the mean value, which is shown in the grey vertical line, and
the $5^{th}$ and $95^{th}$ percentiles of the estimated TTA, which is shown in
the shading area. As shown in Figure 5, for the same time gap, the
distribution for the estimated TTA was more dispersed at lower speed
conditions. In other words, at low speeds, there was greater uncertainty about
the estimated TTA, which could be the reason why it is better, from a reward
maximization perspective, to be more careful about crossing in these
situations. This perspective aligns with the findings of Chen et al. [26], who
showed that apparently biased behavior in a more abstract choice task might
also be explained as a consequence of optimal sequential decisions under
uncertainty. Interestingly, Tian et al. [3] showed that in the road-crossing
context, humans may in practice be achieving this strategy by making use of
relatively simple visual cues.

##  IV Discussions and conclusion

We developed a model of human pedestrian crossing decisions based on
computational rationality, using deep RL to adopt optimal behavior policies
given human-like constraints. We show that when we constrain the agent by a
simple model of human visual perception, it reproduces human gap acceptance
behavior qualitatively. Furthermore, the model also predicts the speed-
dependencies that are typically observed in human gap acceptance. These have
previously been considered as evidence of biases in human pedestrian decision-
making, but our results demonstrate that this type of speed-dependence is a
rational adaption to noisy visual perception. When comparing the results of
LMP and LSP, it shows that these two approaches learned similar policies, but
not identical policies. We believe that the approach of conditioning RL on
constraint parameters is a promising approach for considering individual
differences. As an early attempt in using computational rationality in
modeling road user interaction, we see the feasibility to use computational
rationality to model road user behavior. The developed model could be served
as the agent model in the test environment of AVs.

There is ample scope for further improvements to our model. For example, our
agent is more likely to show faster responses than humans. One reason is that
the human perceptual filtering might be slower than the Kalman filter we used,
which can process the information without delay. Another reason is that we
have not considered the non-decision time in the model. We can also observe
more variability in human CITs than in model CITs. This could be due to both
between- and within-individual variability of unmodeled sources. In addition,
our reward function is simple and so far we have not tuned it. This is enough
for our purposes, to show qualitative patterns of human road-crossing.
However, this limitation is probably the reason why the model has a greater
tendency for gap acceptance than humans. In future work, following a similar
approach to what we did with $\sigma_{v}$ here, we could tune also for example
the time-loss penalty in the reward function. Furthermore, in the current
work, the agent is interacting with a constant speed approaching vehicle.
However, in the real world, the pedestrian will interact with vehicles with
various kinematic states, which also affect the crossing behavior. For
example, [22] suggests that human pedestrians are also perceiving and
interpreting vehicle deceleration. A major advantage of the approach we have
taken here is that deep RL is scalable to much more complex traffic
scenarios., far beyond what is possible with conventional cognitive models. We
therefore conclude that computational rationality overall holds great promise
for applied modeling of human-like road user interaction behavior.

## References

  * [1] G. Markkula, R. Madigan, D. Nathanael, E. Portouli, Y. M. Lee, A. Dietrich, J. Billington, A. Schieben, and N. Merat, “Defining interactions: A conceptual framework for understanding interactive behaviour in human and automated road traffic,” _Theoretical Issues in Ergonomics Science_ , vol. 21, no. 6, pp. 728–752, 2020.
  * [2] “Reported road casualties great britain, annual report: 2021 - gov.uk,” https://www.gov.uk/government/statistics/reported-road-casualties-great-britain-annual-report-2021, accessed: 2023-01-24.
  * [3] K. Tian, G. Markkula, C. Wei, Y. M. Lee, R. Madigan, N. Merat, and R. Romano, “Explaining unsafe pedestrian road crossing behaviours using a psychophysics-based gap acceptance model,” _Safety Science_ , vol. 154, p. 105837, 2022.
  * [4] R. Lobjois and V. Cavallo, “Age-related differences in street-crossing decisions: The effects of vehicle speed and time constraints on gap selection in an estimation task,” _Accident analysis & prevention_, vol. 39, no. 5, pp. 934–943, 2007.
  * [5] T. Petzoldt, “On the relationship between pedestrian gap acceptance and time to arrival estimates,” _Accident Analysis & Prevention_, vol. 72, pp. 127–133, 2014.
  * [6] F. Camara, N. Bellotto, S. Cosar, F. Weber, D. Nathanael, M. Althoff, J. Wu, J. Ruenz, A. Dietrich, G. Markkula _et al._ , “Pedestrian models for autonomous driving part ii: high-level models of human behavior,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 22, no. 9, pp. 5453–5472, 2020.
  * [7] D. Helbing and P. Molnar, “Social force model for pedestrian dynamics,” _Physical review E_ , vol. 51, no. 5, p. 4282, 1995.
  * [8] D. Yang, Ü. Özgüner, and K. Redmill, “A social force based pedestrian motion model considering multi-pedestrian interaction with a vehicle,” _ACM Transactions on Spatial Algorithms and Systems (TSAS)_ , vol. 6, no. 2, pp. 1–27, 2020.
  * [9] G. Markkula, R. Romano, R. Madigan, C. W. Fox, O. T. Giles, and N. Merat, “Models of human decision-making as tools for estimating and optimizing impacts of vehicle automation,” _Transportation research record_ , vol. 2672, no. 37, pp. 153–163, 2018.
  * [10] O. Giles, G. Markkula, J. Pekkanen, N. Yokota, N. Matsunaga, N. Merat, and T. Daimon, “At the zebra crossing: Modelling complex decision processes with variable-drift diffusion models,” in _Proceedings of the 41st annual meeting of the cognitive science society_. Cognitive Science Society, 2019, pp. 366–372.
  * [11] Y. Wang, L. Jiang, M.-H. Yang, L.-J. Li, M. Long, and L. Fei-Fei, “Eidetic 3d lstm: A model for video prediction and beyond,” in _International conference on learning representations_ , 2018.
  * [12] A. Alahi, K. Goel, V. Ramanathan, A. Robicquet, L. Fei-Fei, and S. Savarese, “Social lstm: Human trajectory prediction in crowded spaces,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2016, pp. 961–971.
  * [13] A. R. Srinivasan, Y.-S. Lin, M. Antonello, A. Knittel, M. Hasan, M. Hawasly, J. Redford, S. Ramamoorthy, M. Leonetti, J. Billington _et al._ , “Beyond RMSE: Do machine-learned models of road user interaction produce human-like behavior?” _arXiv preprint arXiv:2206.11110_ , 2022.
  * [14] A. Oulasvirta, J. P. Jokinen, and A. Howes, “Computational rationality as a theory of interaction,” in _CHI Conference on Human Factors in Computing Systems_ , 2022, pp. 1–14.
  * [15] R. L. Lewis, A. Howes, and S. Singh, “Computational rationality: Linking mechanism and behavior through bounded utility maximization,” _Topics in cognitive science_ , vol. 6, no. 2, pp. 279–311, 2014.
  * [16] A. A. Faisal, L. P. Selen, and D. M. Wolpert, “Noise in the nervous system,” _Nature reviews neuroscience_ , vol. 9, no. 4, pp. 292–303, 2008.
  * [17] O.-S. Kwon, D. Tadin, and D. C. Knill, “Unifying account of visual motion and position perception,” _Proceedings of the National Academy of Sciences_ , vol. 112, no. 26, pp. 8142–8147, 2015.
  * [18] T. L. Ooi, B. Wu, and Z. J. He, “Distance determined by the angular declination below the horizon,” _Nature_ , vol. 414, no. 6860, pp. 197–200, 2001.
  * [19] G. Markkula, Y.-S. Lin, A. R. Srinivasan, J. Billington, M. Leonetti, A. H. Kalantari, Y. Yang, Y. M. Lee, R. Madigan, and N. Merat, “Explaining human interactions on the road requires large-scale integration of psychological theory,” 2022.
  * [20] D. C. Knill and A. Pouget, “The bayesian brain: the role of uncertainty in neural coding and computation,” _TRENDS in Neurosciences_ , vol. 27, no. 12, pp. 712–719, 2004.
  * [21] V. François-Lavet, P. Henderson, R. Islam, M. G. Bellemare, J. Pineau _et al._ , “An introduction to deep reinforcement learning,” _Foundations and Trends® in Machine Learning_ , vol. 11, no. 3-4, pp. 219–354, 2018.
  * [22] J. Pekkanen, O. T. Giles, Y. M. Lee, R. Madigan, T. Daimon, N. Merat, and G. Markkula, “Variable-drift diffusion models of pedestrian road-crossing decisions,” _Computational Brain & Behavior_, vol. 5, no. 1, pp. 60–80, 2022.
  * [23] H. Van Hasselt, A. Guez, and D. Silver, “Deep reinforcement learning with double q-learning,” in _Proceedings of the AAAI conference on artificial intelligence_ , vol. 30, no. 1, 2016.
  * [24] Z. Wang, T. Schaul, M. Hessel, H. Hasselt, M. Lanctot, and N. Freitas, “Dueling network architectures for deep reinforcement learning,” in _International conference on machine learning_. PMLR, 2016, pp. 1995–2003.
  * [25] P. A. Murtaugh, “In defense of p values,” _Ecology_ , vol. 95, no. 3, pp. 611–617, 2014.
  * [26] H. Chen, H. J. Chang, and A. Howes, “Apparently irrational choice as optimal sequential decision making,” in _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 35, no. 1, 2021, pp. 792–800.