# Investigating Event-Based Cameras for
Video Frame Interpolation in Sports

Antoine Deckyvere  Montefiore Institute, University of Liège
Email<EMAIL_ADDRESS>Anthony Cioppa  Montefiore
Institute, University of Liège
Email<EMAIL_ADDRESS>Silvio Giancola  IVUL, KAUST
Email<EMAIL_ADDRESS>Bernard Ghanem  IVUL, KAUST
Email<EMAIL_ADDRESS>Marc Van Droogenbroeck  Montefiore
Institute, University of Liège
Email<EMAIL_ADDRESS>
###### Abstract

Slow-motion replays provide a thrilling perspective on pivotal moments within
sports games, offering a fresh and captivating visual experience. However,
capturing slow-motion footage typically demands high-tech, expensive cameras
and infrastructures. Deep learning Video Frame Interpolation (VFI) techniques
have emerged as a promising avenue, capable of generating high-speed footage
from regular camera feeds. Moreover, the utilization of event-based cameras
has recently gathered attention as they provide valuable motion information
between frames, further enhancing the VFI performances. In this work, we
present a first investigation of event-based VFI models for generating sports
slow-motion videos. Particularly, we design and implement a bi-camera
recording setup, including an RGB and an event-based camera to capture sports
videos, to temporally align and spatially register both cameras. Our
experimental validation demonstrates that _TimeLens_ , an off-the-shelf event-
based VFI model, can effectively generate slow-motion footage for sports
videos. This first investigation underscores the practical utility of event-
based cameras in producing sports slow-motion content and lays the groundwork
for future research endeavors in this domain.

Keywords. Event-based camera, video frame interpolation, video understanding,
sports analysis, slow motion.

##  I Introduction

Slow-motion footage has become an indispensable tool in sports broadcasting,
serving to highlight or replay pivotal moments with enhanced emotions and
accurate details. Beyond its aesthetic appeal, slow-motion technology offers a
multifaceted utility in sports analysis. By slowing down the action, it
provides analysts and coaches with a finer temporal resolution to scrutinize
player movements, dissecting techniques and strategies with precision.
Moreover, slow-motion footage empowers referees to make more informed
decisions regarding fouls, as it allows for a comprehensive review of
contentious incidents at lower speeds. This dual function of slow-motion
technology, therefore, both enriches the viewing experience for fans and
enhances the decisions of coaches and officials.

Figure 1: Bi-camera recording setup for event-based video frame interpolation
in sports. We propose a two camera recording setup, including an RGB camera
and an event-based camera to capture sports videos, and temporally align and
spatially register both cameras. We record video footage of racquet sports
characterized by high-speed movements of the ball and racquets, utilizing our
specialized setup, and demonstrate the effectiveness of off-the-shelf event-
based video frame interpolation techniques in producing slow-motion footage.

However, the widespread adoption of slow-motion technology in sports
broadcasting has been held back by the prohibitive costs associated with high-
speed camera setups, which are typically only feasible for major competitions.
As a result, lower leagues and smaller-scale sporting events often lack access
to this technology, further increasing the accessibility gap in sports media
production. Additionally, the infrastructure required to support high-speed
camera systems entails considerable investment, presenting a significant
barrier for many organizations.

Fortunately, recent advancements in deep learning started to revolutionize the
landscape of slow-motion production. New techniques enable Video Frame
Interpolation (VFI), aiming to generate intermediate frames produced by
standard cameras, circumventing the need for specialized, high-cost equipment.
Moreover, the emergence of event-based cameras represents a groundbreaking
development in this field. Unlike conventional cameras that capture entire
frames at fixed intervals, event-based cameras detect and record individual
pixel-level changes in luminance asynchronously, only transmitting data when a
_visual event_ occurs. This innovative approach reduces data redundancy and
provides crucial information on motion dynamics between frames at a much
higher frame rate. By capturing motion in a continuous fashion, event-based
cameras offer unparalleled precision in frame interpolation, enabling the
generation of seamless slow-motion sequences with enhanced realism.

In this study, we investigate the use of an off-the-shelf event-based video
frame interpolation method, namely _TimeLens_ [1], for the creation of slow-
motion footage in the sports domain. In particular, we design and implement a
bi-camera recording setup, including an RGB camera and an event-based camera
to capture sports videos. We then temporally align and spatially register both
cameras to project the information provided by the event-based camera to the
RGB frames. As illustrated in Figure 1, our experimental approach entails
recording sports video footage, with a particular focus on racquet sports,
characterized by high-speed movements of the ball and racquets, utilizing our
specialized setup. Through our analysis, we demonstrate the effectiveness of
TimeLens in generating slow-motion sequences, providing valuable insights into
the dynamics of sports events. This study serves as an initial step towards
exploring the potential of event-based camera systems in sports video
production, laying the groundwork for future research aimed at refining and
expanding this technology for broader applications in the sports industry.

##  II Related Work

Our work relates to the research fields of video frame interpolation, event-
based cameras, and sports video understanding.

###  II-A Video frame interpolation

Video Frame Interpolation (VFI) involves generating intermediate frames
between existing video frames, effectively increasing the frame rate and
allowing the creation of slow-motion content [2]. Over the years, various
methods have been proposed, leveraging convolutional neural networks (CNNs)
[3], phase-based techniques [4], optical flow algorithms [5], or Generative
Adversarial Networks (GANs) [6]. Moreover, industrial tools such as
_XtraMotion_ from EVS Broadcast Equipment [7] facilitate slow-motion video
production in professional settings. The field can count on the availability
of numerous datasets and benchmarks to develop methods, including popular
resources such as Vimeo90K [8], UCF101 [9], X4K1000FPS [10], Middlebury [11],
and the SNU-FILM [12] datasets. Recently, SportsSlowMo [13] introduced the
first dataset dedicated to human-centric sports video clips for VFI using only
the RGB modality. Our study also aims to investigate sports-centric videos,
incorporating event-based camera feeds as an additional modality for VFI.

###  II-B Event-based camera

Event-based cameras, also known as neuromorphic sensors, operate differently
from traditional cameras. Rather than capturing entire frames at fixed
intervals, event-based cameras only record changes in brightness, known as
“events”, at pixel level. These cameras provide several advantages over
conventional cameras, such as a high temporal resolution of up to $10{,}000$
frames per second, low power consumption, wide dynamic range, sparse data
output for efficient data transmission and storage, and low latency [14].
Recently, event-based cameras have emerged as integral components in video
frame interpolation pipelines thanks to their ability to capture information
between RGB frames. This feature enables the modeling of more intricate
scenarios, including non-linear motion often present in sports content.
Notable methods like Timelens [1], Timelens++ [15], or SuperFast [16] have
demonstrated impressive performance in generating slow-motion footage from
both modalities. However, their application has predominantly focused on
close-up shots within controlled environments. In this study, we investigate
the ability of event-based VFI methods to handle sports videos captured in
natural, uncontrolled settings.

###  II-C Sports Video understanding

Over the past decade, there has been an increased focus on sports video
understanding research [17, 18] thanks to the availability of large-scale
datasets [19, 20, 21, 22]. The SoccerNet datasets and challenges [23, 24] have
contributed to multiple video understanding tasks in sports such as, action
spotting [25], replay grounding [26], camera calibration and player re-
identification [27], multiple player tracking [28], multi-view video
recognition [29], and dense video captioning [30]. Recently, deep learning
enabled real-time data and analysis on player performance [31, 32, 33],
including, segmentation and tracking of players and the ball [34, 35], game
tactics [36], action spotting [25, 26, 37, 38, 39, 40, 41, 42, 43], and the
creation of video highlights or summaries [44, 45]. Overall, these
developments elevate coaching strategies and enhance the overall viewer
experience [46, 47]. In this work, we show the capabilities of event-based VFI
methods to generate high-speed footage for downstream sports video analysis.

##  III Methodology

In this section, we provide a rigorous definition of the event-based video
frame interpolation task, describe our sports data recording setup, and
explain the temporal alignment and spatial registration between our bi-camera
setup.

###  III-A Event-based video frame interpolation

Let $\mathbf{I}(t_{i})$ represent the video image recorded at time $t_{i}$ by
a regular RGB camera, where $\mathbf{I}(t_{i})\in\mathbb{R}^{H\times W\times
C}$ denotes an image frame with height $H$, width $W$, and $C$ channels. Then,
let $\mathbf{E}(t_{i})$ be the event data recorded by the event-based camera
between time $t_{i}$ and $t_{i+1}$, consisting of a set of events
$\\{\mathbf{e}_{j}\\}$, where each event
$\mathbf{e}_{j}=(x_{j},y_{j},t^{\prime}_{j},p_{j})$ corresponds to a change in
luminance at pixel location $(x_{j},y_{j})$ and at time $t^{\prime}_{j}$ with
polarity $p_{j}\in\\{-1,1\\}$.

The event-based video frame interpolation problem can be formulated as
follows. Given a sequence of event data
$\\{\mathbf{E}(t_{1}),\mathbf{E}(t_{2}),...,\mathbf{E}(t_{n})\\}$, where
$t_{1}<t_{2}<...<t_{n}$, and the corresponding image frames
$\\{\mathbf{I}(t_{1}),\mathbf{I}(t_{2}),...,\mathbf{I}(t_{n})\\}$, the
objective is to estimate some intermediate frame $\hat{\mathbf{I}}(t_{i+\Delta
t})$ at any arbitrary time $t_{i+\Delta t}\in\interval[open]{t_{i}}{t_{i+1}}$.
Hence, event-based video frame interpolation aims to generate intermediate
frames between consecutive frames captured by a regular RGB camera, using the
information provided by an event-based camera.

In this work, we focus on a particular case of event-based video frame
interpolation where only the bounding image frames $\mathbf{I}(t_{i})$ and
$\mathbf{I}(t_{i+1})$, along with the _registered_ event data,
$\mathbf{E}(t_{i})$ are used to compute intermediate frames
$\hat{\mathbf{I}}(t_{i+\Delta t})$.

###  III-B Bi-camera sports data recording setup

We design and implement a bi-camera (RGB and event-based) recording setup for
sports data collection by aligning two camera supports and mounting them on
tripods, as illustrated in Figure 2. To ensure accurate alignment, we position
the event-based camera such that its optical center is aligned with the center
of the RGB camera lens.

Figure 2: Camera setup. Picture of our bi-camera setup used for sports data
collection. We align both the RGB camera and event-based camera on a tripod.

For the RGB camera, we use an iPhone $12$, capable of capturing videos at
$120$ frames per second (FPS) with a resolution of $1920\times 1080$ pixels.
For the event-based camera, we employ the Prophesee EVK4, which offers a
resolution of $720\times 1280$ pixels, a time resolution equivalent to over
$10{,}000$ FPS, and a dynamic range exceeding $120$ decibels (dB). Moreover,
the event-based camera exhibits a low light cutoff of $0.08$ lux, ensuring
reliable performance even in dimly lit conditions. We employed the Metavision
software suite for both recording and post-processing of the event-based
camera footage directly on-site.

We recorded footage of two semi-professional tennis players engaging in a game
on an indoor court illuminated by LED panels to avoid flickering caused by
traditional neon lighting. The players were instructed to play a regular game
while we moved the cameras between each game session. In total, we recorded
approximately $30$ minutes of usable footage captured from the RGB and event-
based cameras.

###  III-C Temporal alignment and spatial registration

Before proceeding with event-based video frame interpolation, it is crucial to
temporally align and spatially register both cameras. Hereafter, we describe
the components and objectives, and then detail our alignment and registration
processes step-by-step.

Let $(x_{j},y_{j})$ denote a pixel location at time $t_{j}$ in the event-based
camera, and $(x_{i},y_{i})$ represent the corresponding pixel location at time
$t_{i}$ in the RGB camera. We define the projection function
$\mathbf{P}:\mathbb{R}^{H_{\text{event}}\times W_{\text{event}}\times
T_{\text{event}}}\rightarrow\mathbb{R}^{H_{\text{image}}\times
W_{\text{image}}\times T_{\text{image}}}$ as

$(x_{i},y_{i},t_{i})=\mathbf{P}(x_{j},y_{j},t_{j})\,,$ (1)

where $H_{\text{event}}$, $W_{\text{event}}$, $T_{\text{event}}$,
$H_{\text{image}}$, $W_{\text{image}}$, and $T_{\text{image}}$ denote the
height, width, and time of the event-based camera image, and the RGB camera
image, respectively. We compute the temporal and spatial projection from the
event-based camera to the RGB camera in three steps:

1\. Temporal synchronization: We aim to find the event sequence
$\mathbf{E}(t_{j})$ that aligns temporally with $\mathbf{I}(t_{i})$. Since the
frame rate of $\mathbf{I}$ is 120 FPS, we first calculate a sequence of
accumulated events, denoted by $\mathbf{A()}$, at the same frame rate, and
proceed to a visual inspection to align both sequences. This produces a first
estimate of $t_{i}$ and $t_{j}$.

We then reduce the temporal shift $\Delta t_{j\rightarrow i}=t_{j}-t_{i}$ as
follows. As the greatest common divisor between the sampling rates of
$\mathbf{I}()$ and $\mathbf{E}()$ is 40, we split the $\mathbf{I}()$ original
sequence into three interleaved sub-sequences $\mathbf{Seq}$ at 40 FPS.
Likewise, we generate 250 sequences of accumulated events over a period of 25
ms, starting at $t_{j}+k\times 100\mu s$ with $k\in\\{0,\,...,\,249\\}$.
Finally, we compute the mean structural similarity index measure (SSIM, see
[48]) between the grayscale differences of successive frames of Seq and
$\mathbf{A}(t_{j}+k\times 100\mu s)$ over 10 frames for all values of $k$, and
select the sequence and $k$ value that maximize the SSIM. An illustration of
the evolution of the SSIM with respect to $k$ is shown in Figure 3. In that
example, we chose Seq 3 and $k$ around 220. This calculation is repeated for
each video snapshot, except that we use a previous estimate to skip further
visual inspection steps.

Figure 3: SSIM values for different time shifts calculated for three
interleaved sequences at a frame rate of 40 FPS.

2\. Spatial shift estimation: Once synchronized temporally, we identify common
features between the two images, such as the borders of sports equipment or
the athletes. Let $(x_{j}^{(1)},y_{j}^{(1)})$ denote a first feature location
in the event-based camera, and $(x_{i}^{(1)},y_{i}^{(1)})$ represent the
corresponding feature location in the RGB camera. We calculate the horizontal
and vertical shift as $\Delta_{x}=x_{j}^{(1)}-x_{i}^{(1)}$ and
$\Delta_{y}=y_{j}^{(1)}-y_{i}^{(1)}$, respectively.

Original 120 FPS
---
40$\rightarrow$ 120 FPS
20$\rightarrow$ 120 FPS
10$\rightarrow$ 120 FPS
Figure 4: Qualitative results obtained by Timelens with different input frame
rates. The first line shows the original $120$ FPS video, the second the $40$
FPS with two intermediate frame interpolated, the third line a $20$ FPS
subsampled with $5$ out of $6$ frames interpolated, and finally a $10$ FPS
input video with $11$ frames interpolated (only $6$ shown). It can be seen
that the tennis ball is well-placed on all interpolated frames. However, for
the racquet, the fast movement is only well interpolated with an initial frame
rate of $20$ and $40$ while $10$ FPS does not provide satisfactory results.
Original frames are shown in red, while interpolated ones are shown in green.

3\. Scale estimation: Similarly, let $(x_{j}^{(2)},x_{j}^{(2)})$ and
$(x_{i}^{(2)},y_{i}^{(2)})$ denote another set of feature locations, we
compute the scale ratio between the two images based on the distance between
the matched features. Let $\Delta_{\text{event}}$ and $\Delta_{\text{image}}$
denote the Euclidean distances between the matched features in the event-based
and RGB cameras, respectively. The scale ratio $r$ is given by

$r=\frac{\Delta_{\text{image}}}{\Delta_{\text{event}}}=\frac{\sqrt{(x_{i}^{(2)}-x_{i}^{(1)})^{2}+(y_{i}^{(2)}-y_{i}^{(1)})^{2}}}{\sqrt{(x_{j}^{(2)}-x_{j}^{(1)})^{2}+(y_{j}^{(2)}-y_{j}^{(1)})^{2}}}\,.$

The overall projection function then becomes

$\mathbf{P}=\begin{cases}x_{i}=r\times(x_{j}-\Delta_{x})\\\
y_{j}=r\times(y_{j}-\Delta_{y})\\\ t_{i}=t_{j}-\Delta_{j\rightarrow
i}\,,\end{cases}$ (2)

which enables the projection of pixel coordinates from the event-based camera
to the corresponding locations on the RGB camera, facilitating the generation
of intermediate frames for event-based video frame interpolation.

##  IV Experiments

###  IV-A Experimental setup

In this section, we provide a detailed overview of the experimental setup used
to generate intermediate frames on our captured data footage to produce slow-
motion content. We focus on two main aspects: the initial temporal resolution
and upscaling factor, and the summary of the literature method Timelens [1]
that we used in our experiments.

Temporal resolution and upscaling. To comprehensively evaluate the performance
of our method, we explore various combinations of initial temporal resolution
and upscaling factors. Given access to a $120$ FPS camera, we conduct
experiments with different subsampling rates, including $10$, $20$, $40$, and
the original $120$ FPS. Additionally, we test different upscaling factors
applied by the event-based VFI method, ranging from $\times 3$, $\times 6$,
$\times 10$, $\times 12$, and $\times 25$. By examining a wide range of
temporal resolutions and upscaling factors, we aim to assess the robustness
and scalability of the event-based VFI method across different input
configurations.

Timelens. Timelens [1] leverages the complementary strengths of synthesis-
based and warping-based interpolation techniques. The method consists of four
modules: warping-based interpolation, warping refinement, interpolation by
synthesis, and attention-based averaging. Each module serves a specific
purpose, such as estimating optical flow, refining interpolated frames, and
blending synthesis-based and warping-based results. The method utilizes a
voxel grid representation for encoding event sequences and a backbone
architecture based on an hourglass network with skip connections.
Interpolation by synthesis directly regresses new frames given input RGB key
frames and event sequences, allowing it to handle changes in lighting.
However, it may distort image edges and textures in the presence of noisy or
insufficient event data. Warping-based interpolation estimates optical flow
from events to warp boundary key frames, making it suitable for handling blur
and non-linear motion. The warping refinement module computes refined
interpolated frames by estimating residual optical flow between warping-based
and synthesis-based results. Finally, the attention averaging module blends
synthesis-based and warping-based results to achieve a final interpolation
result. We use the open-source code of Timelens with default parameters for
generating our sequences.

###  IV-B Qualitative results

Qualitative results of the interpolated frames are provided in Figure 4 for
all four input frame rates brought up to $120$ FPS. It can be seen that the
interpolation process effectively tracks the trajectory of the tennis ball
across all interpolated frames, showcasing Timelens’ ability in maintaining
object consistency. However, the racquet’s swift motion demonstrates uneven
performance at the initial frame rate. Notably, the $20$ FPS and $40$ FPS
inputs exhibit more faithful interpolation of the racquet’s trajectory
compared to the $10$ FPS input, where evident artifacts emerge. We supplement
these observations with additional original frame rates and scale factors,
provided in a side-by-side video format for enhanced visualization, in
supplementary material 111Supplementary material: https://bit.ly/3xmhRKU.
Despite the promising outcomes, residual artifacts persist, suggesting avenues
for improvement in future iterations of the methodology.

###  IV-C Future work

In future work, we plan to explore several avenues for enhancing the method
and extend the scope of our research:

Optical Alignment Improvement. We noticed that misaligned events generate
artifacts in the interpolated stream. Therefore, we intend to implement a beam
splitter setup to achieve better alignment of the optical centers between the
RGB camera and the event-based camera.

Performance enhancement. We also aim to investigate techniques to further
improve the performance of Timelens, particularly when applied to sports-
centric videos captured by event-based cameras. This may involve incorporating
domain-specific features to enhance the accuracy and realism of the generated
slow-motion footage.

Exploration of downstream analysis techniques. Beyond video frame
interpolation, we plan to explore downstream analysis techniques enabled by
the generated slow-motion footage. One potential avenue is player movement
analysis, where we can leverage the detailed temporal information provided by
the slow-motion videos to gain insights into player movement and performance.

##  V Conclusion

In conclusion, this project contributes to the advancement of sports video
understanding through the analysis of the potential of event-based video frame
interpolation. Our primary contributions lie in the recording of sports data,
including the alignment of the RGB and event-based camera temporally and
spatially. Leveraging these recorded sport sequences, we conducted tests of
Timelens, an already established event-based video frame interpolation method.
Through qualitative analysis, we have provided insights into the performance
of Timelens in generating slow-motion footage on our dataset, showcasing its
applicability and effectiveness in the context of sports videos captured in
dynamic and uncontrolled environments. Moving forward, further research in
this domain could explore better physical setups, refinements to existing
methods with the development of specialized algorithms tailored to the unique
characteristics of sports footage, ultimately enhancing the quality and
utility of sports video analysis tools.

## Acknowledgment

A. Cioppa is funded by the F.R.S.-FNRS. This work was partly supported by the
King Abdullah University of Science and Technology (KAUST) Office of Sponsored
Research through the Visual Computing Center (VCC) funding and the SDAIA-KAUST
Center of Excellence in Data Science and Artificial Intelligence (SDAIA-KAUST
AI). We thank Adrien Deliège and Arnaud Leduc, the two semi-pro tennis
players, as well as the Royal Tennis Club de Liège for allowing us to record
one of their game.

## References

  * [1] S. Tulyakov, D. Gehrig, S. Georgoulis, J. Erbach, M. Gehrig, Y. Li, and D. Scaramuzza, “Time Lens: Event-based video frame interpolation,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (Nashville, TN, USA), pp. 16150–16159, Inst. Electr. Electron. Eng. (IEEE), Jun. 2021.
  * [2] A. S. Parihar, D. Varshney, K. Pandya, and A. Aggarwal, “A comprehensive survey on video frame interpolation techniques,” Vis. Comput., vol. 38, pp. 295–319, Jan. 2021.
  * [3] S. Niklaus, L. Mai, and F. Liu, “Video frame interpolation via adaptive separable convolution,” in IEEE Int. Conf. Comput. Vis. (ICCV), (Venice, Italy), pp. 261–270, Inst. Electr. Electron. Eng. (IEEE), Oct. 2017.
  * [4] S. Meyer, O. Wang, H. Zimmer, M. Grosse, and A. Sorkine-Hornung, “Phase-based frame interpolation for video,” in IEEE Conf. Comput. Vis. Pattern Recognit. (CVPR), (Boston, MA, USA), pp. 1410–1418, Inst. Electr. Electron. Eng. (IEEE), Jun. 2015.
  * [5] S. Niklaus and F. Liu, “Context-aware synthesis for video frame interpolation,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (Salt Lake City, UT, USA), pp. 1701–1710, Inst. Electr. Electron. Eng. (IEEE), Jun. 2018.
  * [6] J. van Amersfoort, W. Shi, A. Acosta, F. Massa, J. Totz, Z. Wang, and J. Caballero, “Frame interpolation with multi-scale deep loss functions and generative adversarial networks,” arXiv, vol. abs/1711.06045, 2017.
  * [7] EVS Broadcast Equipment, “XtraMotion.” https://evs.com/products/live-replays-storytelling/xtramotion.
  * [8] T. Xue, B. Chen, J. Wu, D. Wei, and W. T. Freeman, “Video enhancement with task-oriented flow,” Int. J. Comput. Vis., vol. 127, pp. 1106–1125, Feb. 2019.
  * [9] K. Soomro, A. R. Zamir, and M. Shah, “UCF101: A dataset of 101 human actions classes from videos in the wild,” arXiv, vol. abs/1212.0402, 2012.
  * [10] H. Sim, J. Oh, and M. Kim, “XVFI: eXtreme video frame interpolation,” in IEEE/CVF Int. Conf. Comput. Vis. (ICCV), (Montréal, Can.), pp. 14469–14478, Inst. Electr. Electron. Eng. (IEEE), Oct. 2021.
  * [11] S. Baker, S. Roth, D. Scharstein, M. J. Black, J. Lewis, and R. Szeliski, “A database and evaluation methodology for optical flow,” in IEEE Int. Conf. Comput. Vis. (ICCV), (Rio de Janeiro, Brazil), pp. 1–8, Inst. Electr. Electron. Eng. (IEEE), 2007.
  * [12] M. Choi, H. Kim, B. Han, N. Xu, and K. M. Lee, “Channel attention is all you need for video frame interpolation,” in AAAI Conf. Artif. Intell., vol. 34, pp. 10663–10671, Association for the Advancement of Artificial Intelligence (AAAI), Apr. 2020.
  * [13] J. Chen and H. Jiang, “SportsSloMo: A new benchmark and baselines for human-centric video frame interpolation,” arXiv, vol. abs/2308.16876, 2023.
  * [14] X. Zheng, Y. Liu, Y. Lu, T. Hua, T. Pan, W. Zhang, D. Tao, and L. Wang, “Deep learning for event-based vision: A comprehensive survey and benchmarks,” arXiv, vol. abs/2302.08890, 2023.
  * [15] S. Tulyakov, A. Bochicchio, D. Gehrig, S. Georgoulis, Y. Li, and D. Scaramuzza, “Time Lens++: Event-based frame interpolation with parametric nonlinear flow and multi-scale fusion,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (New Orleans, LA, USA), pp. 17734–17743, Inst. Electr. Electron. Eng. (IEEE), Jun. 2022.
  * [16] Y. Gao, S. Li, Y. Li, Y. Guo, and Q. Dai, “SuperFast: 200$\times$ video frame interpolation via event camera,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 45, pp. 7764–7780, Jun. 2023.
  * [17] T. B. Moeslund, G. Thomas, and A. Hilton, Computer vision in sports.  Springer, 2014.
  * [18] B. T. Naik, M. F. Hashmi, N. D. Bokde, and Z. M. Yaseen, “A comprehensive review of computer vision in sports: Open issues, future trends and research directions,” Appl. Sci., vol. 12, pp. 1–49, Apr. 2022.
  * [19] C. K. Ingwersen, C. Møller Mikkelstrup, J. N. Jensen, M. Rieger Hannemose, and A. B. Dahl, “SportsPose - a dynamic 3D sports pose dataset,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Vancouver, Can.), pp. 5219–5228, Inst. Electr. Electron. Eng. (IEEE), Jun. 2023.
  * [20] A. Scott, I. Uchida, M. Onishi, Y. Kameda, K. Fukui, and K. Fujii, “SoccerTrack: A dataset and tracking algorithm for soccer with fish-eye and drone videos,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (New Orleans, LA, USA), pp. 3568–3578, Inst. Electr. Electron. Eng. (IEEE), Jun. 2022.
  * [21] G. Van Zandycke, V. Somers, M. Istasse, C. D. Don, and D. Zambrano, “DeepSportradar-v1: Computer vision dataset for sports understanding with high quality annotations,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Lisbon, Port.), pp. 1–8, ACM, Oct. 2022.
  * [22] M. Istasse, V. Somers, P. Elancheliyan, J. De, and D. Zambrano, “DeepSportradar-v2: A multi-sport computer vision dataset for sport understandings,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Ottawa, Ontario, Can.), pp. 23–29, ACM, Oct. 2023.
  * [23] S. Giancola, A. Cioppa, A. Deliège, F. Magera, V. Somers, L. Kang, X. Zhou, O. Barnich, C. De Vleeschouwer, A. Alahi, B. Ghanem, M. Van Droogenbroeck, and _et al._ , “SoccerNet 2022 challenges results,” in Int. ACM Work. Multimedia Content Anal. Sports (MMSports), (Lisbon, Port.), pp. 75–86, ACM, Oct. 2022.
  * [24] A. Cioppa, S. Giancola, V. Somers, F. Magera, X. Zhou, H. Mkhallati, A. Deliège, J. Held, C. Hinojosa, A. M. Mansourian, P. Miralles, O. Barnich, C. De Vleeschouwer, A. Alahi, B. Ghanem, M. Van Droogenbroeck, and _et al._ , “SoccerNet 2023 challenges results,” arXiv, vol. abs/2309.06006, 2023.
  * [25] S. Giancola, M. Amine, T. Dghaily, and B. Ghanem, “SoccerNet: A scalable dataset for action spotting in soccer videos,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Salt Lake City, UT, USA), pp. 1792–179210, Inst. Electr. Electron. Eng. (IEEE), Jun. 2018.
  * [26] A. Deliège, A. Cioppa, S. Giancola, M. J. Seikavandi, J. V. Dueholm, K. Nasrollahi, B. Ghanem, T. B. Moeslund, and M. Van Droogenbroeck, “SoccerNet-v2: A dataset and benchmarks for holistic understanding of broadcast soccer videos,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Nashville, TN, USA), pp. 4508–4519, Jun. 2021.
  * [27] A. Cioppa, A. Deliège, S. Giancola, B. Ghanem, and M. Van Droogenbroeck, “Scaling up SoccerNet with multi-view spatial localization and re-identification,” Sci. Data, vol. 9, pp. 1–9, Jun. 2022.
  * [28] A. Cioppa, S. Giancola, A. Deliege, L. Kang, X. Zhou, Z. Cheng, B. Ghanem, and M. Van Droogenbroeck, “SoccerNet-tracking: Multiple object tracking dataset and benchmark in soccer videos,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (New Orleans, LA, USA), pp. 3490–3501, Inst. Electr. Electron. Eng. (IEEE), Jun. 2022.
  * [29] J. Held, A. Cioppa, S. Giancola, A. Hamdi, B. Ghanem, and M. Van Droogenbroeck, “VARS: Video assistant referee system for automated soccer decision making from multiple views,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Vancouver, Can.), pp. 5086–5097, Inst. Electr. Electron. Eng. (IEEE), Jun. 2023.
  * [30] H. Mkhallati, A. Cioppa, S. Giancola, B. Ghanem, and M. Van Droogenbroeck, “SoccerNet-caption: Dense video captioning for soccer broadcasts commentaries,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Vancouver, Can.), pp. 5074–5085, Inst. Electr. Electron. Eng. (IEEE), Jun. 2023.
  * [31] R. Vandeghen, A. Cioppa, and M. Van Droogenbroeck, “Semi-supervised training to improve player and ball detection in soccer,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (New Orleans, LA, USA), pp. 3480–3489, Inst. Electr. Electron. Eng. (IEEE), Jun. 2022.
  * [32] K. Seweryn, G. Cheć, S. Łukasik, and A. Wróblewska, “Improving object detection quality in football through super-resolution techniques,” arXiv, vol. abs/2402.00163, 2024.
  * [33] M. Boeker and C. Midoglu, “Soccer athlete data visualization and analysis with an interactive dashboard,” in Int. Conf. Multimedia Retr., vol. 13833 of Lect. Notes Comput. Sci., pp. 565–576, Springer Int. Publ., 2023.
  * [34] A. Cioppa, A. Deliege, M. Istasse, C. De Vleeschouwer, and M. Van Droogenbroeck, “ARTHuS: Adaptive real-time human segmentation in sports through online distillation,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Long Beach, CA, USA), pp. 2505–2514, Inst. Electr. Electron. Eng. (IEEE), Jun. 2019.
  * [35] A. Maglo, A. Orcesi, and Q.-C. Pham, “Efficient tracking of team sport players with few game-specific annotations,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (New Orleans, LA, USA), pp. 3460–3470, Inst. Electr. Electron. Eng. (IEEE), Jun. 2022.
  * [36] A. Arbués Sangüesa, A. Martín, J. Fernández, C. Ballester, and G. Haro, “Using player’s body-orientation to model pass feasibility in soccer,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), (Seattle, WA, USA), pp. 3875–3884, Inst. Electr. Electron. Eng. (IEEE), Jun. 2020.
  * [37] A. Cioppa, A. Deliège, and M. Van Droogenbroeck, “A bottom-up approach based on semantics for the interpretation of the main camera stream in soccer games,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Salt Lake City, UT, USA), pp. 1846–1855, Jun. 2018.
  * [38] J. V. B. Soares, A. Shah, and T. Biswas, “Temporally precise action spotting in soccer videos using dense detection anchors,” in IEEE Int. Conf. Image Process. (ICIP), (Bordeaux, France), pp. 2796–2800, Inst. Electr. Electron. Eng. (IEEE), Oct. 2022.
  * [39] J. Hong, H. Zhang, M. Gharbi, M. Fisher, and K. Fatahalian, “Spotting temporally precise, fine-grained events in video,” arXiv, vol. abs/2207.10213, 2022.
  * [40] L. Wu, Z. Yang, Q. Wang, M. Jian, B. Zhao, J. Yan, and C. W. Chen, “Fusing motion patterns and key visual information for semantic event recognition in basketball videos,” arXiv, vol. abs/2007.06288, 2020.
  * [41] J. Denize, M. Liashuha, J. Rabarisoa, A. Orcesi, and R. Hérault, “COMEDIAN: Self-supervised learning and knowledge distillation for action spotting using transformers,” arXiv, vol. abs/2309.01270, 2023.
  * [42] K. Seweryn, A. Wróblewska, and S. Łukasik, “Survey of action recognition, spotting and spatio-temporal localization in soccer – current trends and research perspectives,” arXiv, vol. abs/2309.12067, 2023.
  * [43] A. Cioppa, A. Deliège, S. Giancola, F. Magera, O. Barnich, B. Ghanem, and M. Van Droogenbroeck, “Camera calibration and player localization in SoccerNet-v2 and investigation of their representations for action spotting,” in IEEE Int. Conf. Comput. Vis. Pattern Recognit. Work. (CVPRW), CVsports, (Nashville, TN, USA), pp. 4532–4541, Jun. 2021.
  * [44] A. Cioppa, A. Deliège, S. Giancola, B. Ghanem, M. Van Droogenbroeck, R. Gade, and T. B. Moeslund, “A context-aware loss function for action spotting in soccer videos,” in IEEE/CVF Conf. Comput. Vis. Pattern Recognit. (CVPR), (Seattle, WA, USA), pp. 13123–13133, Inst. Electr. Electron. Eng. (IEEE), Jun. 2020.
  * [45] S. Gautam, C. Midoglu, S. S. Sabet, D. B. K. Kshatri, and P. Halvorsen, “Assisting soccer game summarization via audio intensity analysis of game highlights,” in IOE Graduate Conference, vol. 12, pp. 25–32, Oct. 2022.
  * [46] C. Midoglu, S. Hicks, V. Thambawita, T. Kupka, and P. Halvorsen, “MMSys’22 grand challenge on AI-based video production for soccer,” in ACM Multimedia Systems Conference (MMSys), (Athlone, Ireland), pp. 1–6, Jun. 2022.
  * [47] M. H. Sarkhoosh, S. M. M. Dorcheh, C. Midoglu, S. S. Sabet, T. Kupka, D. Johansen, M. A. Riegler, and P. Halvorsen, “AI-based cropping of soccer videos for different social media representations,” in Int. Conf. Multimedia Retr., vol. 14557 of Lect. Notes Comput. Sci., pp. 279–287, Springer Nat. Switz., 2024.
  * [48] Z. Wang, A. C. Bovik, H. R. Sheikh, and E. P. Simoncelli, “Image quality assessment: From error visibility to structural similarity,” IEEE Trans. Image Process., vol. 13, pp. 600–612, Apr. 2004.


# Efficient Online Inference for Infinite Evolutionary Cluster models with
Applications to Latent Social Event Discovery

Wei Wei  Carnegie Mellon University<EMAIL_ADDRESS>,  Kennth Joseph
Northeastern University 111The work was completed while the author was a
graduate student at Carnegie Mellon University<EMAIL_ADDRESS>and
Kathleen M. Carley  Carnegie Mellon University<EMAIL_ADDRESS>
(2016)

###### Abstract.

The Recurrent Chinese Restaurant Process (RCRP) is a powerful statistical
method for modeling evolving clusters in large scale social media data. With
the RCRP, one can allow both the number of clusters and the cluster parameters
in a model to change over time. However, application of the RCRP has largely
been limited due to the non-conjugacy between the cluster evolutionary priors
and the Multinomial likelihood. This non-conjugacy makes inference difficult
and restricts the scalability of models which use the RCRP, leading to the
RCRP being applied only in simple problems, such as those that can be
approximated by a single Gaussian emission. In this paper, we provide a novel
solution for the non-conjugacy issues for the RCRP and an example of how to
leverage our solution for one specific problem - the _social event discovery
problem._ By utilizing Sequential Monte Carlo methods in inference, our
approach can be massively paralleled and is highly scalable, to the extent it
can work on tens of millions of documents. We are able to generate high
quality topical and location distributions of the clusters that can be
directly interpreted as real social events, and our experimental results
suggest that the approaches proposed achieve much better predictive
performance than techniques reported in prior work. We also demonstrate how
the techniques we develop can be used in a much more general ways toward
similar problems.

ACM proceedings, LaTeX, text tagging

††copyright: rightsretained††doi: 10.475/123_4††isbn:
123-4567-24-567/08/06††conference: ACM Woodstock conference; July 1997; El
Paso, Texas USA††journalyear: 1997††price: 15.00††ccs: Computer systems
organization Embedded systems††ccs: Computer systems organization
Redundancy††ccs: Computer systems organization Robotics††ccs: Networks Network
reliability

##  1\. Introduction

With the increasing amount of unlabeled data sets that can be easily acquired,
clustering techniques have become increasingly important to the community of
machine learning. Thanks to the growing amount of social media and social
networking applications, publicly available text data, specifically, has grown
at a massive, exponential rate. As the amount of such data produced has
rapidly surpassed human capacity for interpretation of it, one of the most
important questions we face today is how we can effectively organize this text
into clusters that are meaningful for humans and allow for actionable
insights.

Bayesian ad-mixture based methods such as Latent Dirichlet Allocation (LDA)
(Blei et al., 2003), otherwise known as “topic models”, have been one of the
most popular clustering methods for text data. In topic models, latent
representations of clusters referred to as “topics”, which are distributions
over words in the corpus, are learned by scanning a large text corpus.
Extensions of topic models have been developed for when meta information such
as spatial coordinates or timestamps are present. Examples include the
geographical topic model(Hong et al., 2012), the dynamic topic model (Blei and
Lafferty, 2006) and the event detection model (Wei et al., 2015). In these
models, topics usually contain distributions that describe metadata in
addition to the word distributions found in traditional topic models.

When topic models are applied to data over long periods of time, it is likely
that topics will change or evolve. For example, a topic about the presidential
elections trained on data from 2012 might contain words like “debate”,
“Democrat”, “election”, generic to almost any presidential election, and words
like “marriage” and “Romney” that were specific to the 2012 race. Similarly, a
topic trained on data from 2016 might contain the same general terms but refer
to “wall” and “Trump” as opposed to “marriage” and “Romney”. A temporal
evolutionary model such as the dynamic topic model (Blei and Lafferty, 2006)
can be trained on data from both 2012 and 2016 and can identify a single
“presidential election” topic that shifted slightly over time between 2012 and
2016, rather than creating two totally distinct topics. Rather than having to
perform manual, post-hoc analyses to make such connections, temporal
evolutionary topic models thus can easily allow for understanding how general
themes of importance in the data shift over time.

Temporal evolutionary topic models can also address the fact that over time,
not only do old topics shift, new topics also arise. The non-parametric
version of the evolutionary dynamic models uses the Recurrent Chinese
Restaurant Process (RCRP)(Ahmed and Xing, 2008) and therefore allows for the
number topics to be automatically determined by the data set rather than
setting a fixed value. Because the model works on temporally ordered data,
inference techniques such as Sequential Monte Carlo can allow for massively
paralleled online algorithms to be developed to deal with streaming data sets.
Non-parametric evolutionary dynamic models thus allow for both the creation of
“new” topics dynamically from the data as well as the evolution of “old”
topics over time, making them an ideal candidate for the rapid analysis of
large-scale text data.

Unfortunately, such models are difficult to apply to large-scale text data,
because inference is too inefficient. One of the primary issues in this
inference is the non-conjugacy between the data likelihood and the priors of
the evolutionary model. In such models, cluster evolutionary priors are
usually chosen to be logistic-normal distributions (Blei and Lafferty, 2006;
Ahmed and Xing, 2008), which are not conjugate with the Multinomial likelihood
used in topic modeling. Non-conjugacy puts significant computational
limitations on the evaluation of marginal likelihood, which is usually
required for the inference of such statistical models. The usual solution to
this issue is to utilize Laplace Approximations to approximate the marginal
likelihoods. In this approximation, Taylor expansion up to the second order is
used to approximate the integral around a point that maximizes the original
function. However, the particular form of the evolutionary dynamic model makes
it difficult to solve this maximum point. Based on Bayesian theory, prior work
therefore chose the point to maximize the data likelihood instead of the
posterior in order to obtain a tractable solution (Ahmed and Xing, 2008). This
solution, however, ignored information on the prior, which contains historical
clusters on previous time steps.

Another issue with the evolutionary dynamic models for clustering is the
difficulties involved in inference in general. Prior work (Ahmed and Xing,
2008) uses RTS smoothing to solve the model, which is only feasible when the
emission functions are in the form of strictly Gaussian. Thus, in situations
where emission functions can not be expressed as a single Gaussian, new
inferences technique has to be developed.

In this paper, we study inference techniques to solve the evolutionary dynamic
clustering problem. To illustrate how our technique works, we apply it onto
the _Evolutionary Social Event Discovery (ESED)_ problem Based on prior work
on event detection(Wei et al., 2015). The ESED task is to discover
evolutionary latent clusters of documents that characterize distinct social
events by monitoring an evolving set of documents with spatiotemporal meta-
data that contain text about social events. Our experimental results suggest
that we are able to detect major evolutionary social events on a set of
Twitter data. Although the methods are illustrated through a model to solve a
specific problem, we note that our inference technique can be used to solve
latent evolutionary clustering models in general that are not restricted to
the ESED problem.

##  2\. Background

###  2.1. Topic Modeling

Topic modeling has become a popular approach to discover latent topics in
large collections of text data(Blei et al., 2003; Griffiths and Steyvers,
2004). Over the past decade, a significant amount of work has considered how
to extend topic modeling by incorporating metadata(Wei et al., 2015), by
improving its sampling efficiencies(Li et al., 2014; Yao et al., 2009), and by
improving the generalizability of the model(Blei and Lafferty, 2006). Within
the topic modeling literature, perhaps the most relevant work for our purposes
are those models dealing with temporal dynamics. Specifically, the dynamic
topic model (Blei and Lafferty, 2006) uses a parametric model to characterize
changes of topics over time by assuming logistic-normally distributed topics.

Figure 1. Graphical Model

###  2.2. Non-parametric Bayesian

There exist a wide range of Bayesian non-parametric techniques that are
relevant to topic modeling, most of which are based on Dirichlet Process (DP)
(Ferguson, 1973). One of the strands of research addresses the temporal
dynamics of non-parametric clustering or topic modeling specifically. For
example, the recurrent Chinese Restaurant Process (RCRP) (Ahmed and Xing,
2008) divides data into epochs and the process of choosing a specific cluster
membership for the $d^{th}$ document at time (epoch) $t$, $s_{t,d}$, is given
by Equation 1. Here $s_{1:(t,d)-1}$ denotes the set of all documents before
(and excluding) the $d^{th}$ document at time $t$. Documents can either create
a new cluster with probability proportional to the dispersion parameter
$\gamma$ or reuse the existing cluster $k$ with probability proportional to
$\sum_{\delta=0}^{\Delta}e^{-\frac{\delta}{\alpha}}m_{t-\delta,k}^{-d}$. Here
$m_{t-\delta,k}^{-d}$ is the number of documents belong to cluster $k$ at time
$t-\delta$ that includes all the documents before (and excluding) $d$.
$e^{-\frac{\delta}{\alpha}}$ here is a decay factor that put more weights on
recent time steps rather than historical ones. By using Gaussian transiting
distributions, we are able to develop evolutionary document clustering
algorithms such as the one in (Ahmed and Xing, 2008).

(1)
$P(s_{t,d}=k|s_{1:(t,d)-1})\propto\begin{cases}\sum_{\delta=0}^{\Delta}e^{-\frac{\delta}{\alpha}}m_{t-\delta,k}^{-d}&\text{
k exists }\\\ \gamma,&\text{k is new}\end{cases}$

###  2.3. Non-conjugacy on Logistic-Normal Prior with Multinomial Likelihood

Temporal dynamic models with a topic modeling component (Ahmed and Xing, 2008;
Blei and Lafferty, 2006) rely on the logistic normal distribution to provide
the ability to model topic evolutions. A logistic normally distributed
variable $L(X)$ can be acquired by applying a logistic function $L(\cdot)$
onto the normally distributed variable $X$. Unfortunately, the non-conjugacy
between the logistic normal prior and Multinomial likelihood makes it
difficult to integrate the topic variable out, which is essential for
efficient and effective inference in practice. Many solutions have been
proposed to address this issue, such auxiliary sampling using the Polya-Gamma
distribution (Chen et al., 2013) and Laplace approximation (Ahmed and Xing,
2008). In this paper, we favor the later approach since the auxiliary sampling
method still needs to sample each dimension of the latent variable. In the
Bayesian setting of the Laplace approximation, our goal is to come up with an
approximation to the marginal likelihood, denoted as $M$. The basic idea of
Laplace approximation is to use a single point $\widehat{\theta}$ to
approximate the whole integral mass. Here we let $h(\theta)=-\frac{1}{N}(\log
P(X|\theta)+\log\pi(\theta))$ with $N$ being the number samples, $d$ being the
dimension of the data, and $\Sigma=(D^{2}h(\widehat{\theta}))^{-1}$.

(2) $\displaystyle M$ $\displaystyle=\int P(X|\theta)\pi(\theta)\approx
P(X|\widehat{\theta})\pi(\widehat{\theta})(2\pi)^{d/2}|\Sigma|^{1/2}N^{-d/2}$

A Laplace approximation solution that is similar to the problem we are
studying in this paper has been proposed in (Ahmed and Xing, 2008). However,
their solution ignored the historical data and, for reasons described below,
makes too many simplifying assumptions. We will remedy this issue here by
providing a better solution to the approximation that is efficient at the same
time.

###  2.4. Sequential Monte Carlo

Sequential Monte Carlo (SMC) methods, otherwise known as particle filtering
(Doucet et al., 2001) methods, are widely used in the inference of Bayesian
models (Canini et al., 2009; Ahmed et al., 2011; Du et al., 2015). SMC
algorithm keeps track of several sets of instances, known as “particles” and
update them sequentially. For each instance, an SMC algorithm maintains the
posterior distribution of latent variables given the data. In our case, since
documents are organized into epochs, SMC maintains the posterior
$P(z_{1,(t,d)},s_{1:(t,d)}|x_{1:(t,d)})$. Here $z_{1,(t,d)}$ is the set of
latent variables up to the $d^{th}$ document at time $t$. Similar notations
apply to $s_{1:(t,d)}$ and $x_{1:(t,d)}$, which are cluster indicators and the
data, respectively. An SMC algorithm updates this posterior to
$P(z_{1,(t,d+1)},s_{1:(t,d+1)}|x_{1:(t,d+1)})$ after scanning another piece of
data $x_{(t,d+1)}$ by sampling a proposal distribution in the form of
$Q(z_{(t,d+1)},s_{(t,d+1)}|x_{1:(t,d+1)},z_{1,(t,d)},s_{1:(t,d)})$. Here, like
in all SMC algorithms, we maintain several sets of those particles and
calculate “particle weights” to evaluate how good of a representation of the
true posterior distribution they are. Once the weights in the particles become
unbalanced, we eliminate low particles and duplicate high weight ones. This
process is referred to as resampling in the SMC literature (Ahmed and Xing,
2008).

##  3\. Statistical Model

Table 1. The notation used in the construction of our statistical model Symbol |  Description
---|---
$(t,d)$ |  index of document $d^{th}$ document at time $t$
$1:(t,d)$ |  a collection of documents up to the $d^{th}$ document at time $t$
$K_{t}$ |  num. of events at time $t$
$D_{t}$ |  num. of documents at time $t$
$N_{t,d}$ |  num. of words belongs to document $(t,d)$
$M$ |  num. of Gaussian distributed location centers
$F$ |  num. of particles in Sequential Monte Carlo
$s_{t,d}$ |  event index of document $(t,d)$
$\pi_{t,k}$ |  mixture weight (before logistic transform) of location centers of event $k$ at time $t$
$\phi_{t,k}$ |  topic distribution (before logistic transform) of event $k$ at time $t$
$\mu_{m}$ |  mean parameter for location $m$
$\Sigma_{m}$ |  co-variance matrix of component $m$
$l_{t,d}$ |  location of document $(t,d)$
$w_{t,d}$ |  text that belongs to document $(t,d)$
$\alpha$ |  decay factor for RCRP
$\gamma$ |  dispersion parameter for RCRP
$\Delta$ |  temporal width for RCRP
$\tau_{0}$ |  parameter for topic transition Gaussian co-variance matrix
$\rho_{0}$ |  parameter for location weight Gaussian co-variance matrix
$L(\cdot)$ |  logistic function
$\tau_{k}$ |  the first time step when cluster $k$ presents.

Rooted in prior work on event discovery (Wei et al., 2015), our model
characterizes a social event as a collection of distributions on text and
location that change with time. Figure 1 displays a probabilistic graphical
model representation of our model and Table 1 provides an overview of notation
used. Our model can roughly be characterized as follows: we assume that a
cluster at a particular time step is characterized by a spatial distribution
and a topical distribution over words. Importantly, these distributions are
allowed to evolve over time. Within a given time step, each document is
characterized by the cluster it belongs to. The cluster to which it belongs
informs the set of words the document is likely to have, as well as the
location the document is likely to be sent from. On the latter point, each
document is characterized by a location represented by a latitude, longitude
pair. In our model, this latitude and longitude is generated by selecting a
specific pre-defined _region_ , described below.

A key component of the model we develop is that we discretize the time stamps
of tweets (referred to generically here as documents) and organize them into
$epochs$. For example, if we chose to discretize our data into month-long time
periods, all documents with a timestamp in January, 2016 would fall into the
same epoch, while February 2016 will be another epoch, etc. The $d^{th}$
document at time step (or synonymously, epoch) $t$ is labeled with the
subscript $(t,d)$. More specifically, each document has a unique _event index_
$s_{t,d}$ generated from a RCRP with dispersion parameter $\gamma$, temporal
width $\Delta$ and decay factor $\alpha$ (Ahmed and Xing, 2008). Here
$m_{t,k}=\sum_{i=1}^{D_{t}}\mathbbm{I}(s_{t,i}=k)$ represents the number of
documents that belong to cluster $k$ at time $t$ and $m_{t,k}^{-d}$ represents
this same quantity up to document $d$.

Compared to Dirichlet Process (Ferguson, 1973), the RCRP considers the
temporal dynamics of clusters in the history. Specifically, the hyper-
parameter $\Delta$ controls the amount of history information to be taken into
account. From Equation 1, we can see that recent data will receive a much
higher weight and that this weight decays exponentially over time. The
parameter $\alpha$ controls the speed of such decay. As a result of RCRP, new
events can be “born” and old events can “die out” once the weight becomes
zero, as the event will therefore not be able to attract subsequent documents.

Within each cluster $k$ in our model, there exists a topical component
$\phi_{t,l}$ and a spatial component $\pi_{t,l}$ for each time $t$ that are
initially generated by a Gaussian centered on $0$ with diagonal covariance
$\tau_{0}I$ and $\rho_{0}I$ respectively.

(3) $\phi_{t,k}\sim\mathcal{N}(0,\tau_{0}I)$

(4) $\pi_{t,k}\sim\mathcal{N}(0,\rho_{0}I)$

For a given document, the probability of generating the words in the document,
$w_{(t,d),i}$ and the region index of the document $z_{t,d}$ are determined
using a multinomial distribution. By applying a logistic function $L(*)$, the
parameters $\phi_{t,l}$ and $\pi_{t,l}$ serve as the natural parameter of
these distributions. Hence, $w$ and $z$ follows a logistic normal
distribution. Such structure is not new to the community of topic modeling and
has been explored by many prior work such as the Correlated Topic Model (Blei
and Lafferty, 2007).

(5) $w_{(t,d),i}\sim Multi(L(\phi_{t,s_{t,d}}))$

(6) $z_{t,d}\sim Multi(L(\pi_{t,s_{t,d}}))$

Once the region index $z_{t,d}$ of a document is determined, the actual
document location $l_{t,d}$, which contains a two-dimensional vector
representing latitude and longitude, can be generated by using the Gaussian
prior $\mu$ and $\Sigma$ generated from each region.

(7) $l_{(t,d)}\sim\mathcal{N}(\mu_{z},\Sigma_{z})$

One unique characteristic of our model is to allow both the topical parameter
$\phi_{t,k}$ and the spatial parameter $\pi_{t,k}$ to evolve with time. This
can be achieved by using another Gaussian evolutionary prior on existing
events for the current time step that is centered on but that can deviate from
the value of the last time step. This idea has been explored in (Ahmed and
Xing, 2008). However, as we mentioned, the authors tried to approximate the
emission function using a single Gaussian, which is a reasonable assumption in
that model but no longer holds in our scenario since we are modeling spatial
component as well.

(8) $\phi_{t,k}\sim\mathcal{N}(\phi_{t-1,k},\tau_{0}I)$

(9) $\pi_{t,k}\sim\mathcal{N}(\pi_{t-1,k},\rho_{0}I)$

The model can be summarized with a description of its generative process,
which is as follows:

  1. (1)

For each time period $t$:

    1. (a)

For each existing event $k$

      1. (i)

Draw $\pi_{t,k}\sim\mathcal{N}(\pi_{t-1,k},\rho_{0}I)$

      2. (ii)

Draw $\phi_{t,k}\sim\mathcal{N}(\phi_{t-1,k},\tau_{0}I)$

    2. (b)

For each document $d$

      1. (i)

Draw event index $s_{t,d}$ from $RCRP(\gamma,\alpha,\Delta)$

      2. (ii)

If $s_{t,d}=k$ is a new event

        1. (A)

Draw $\pi_{t,k}\sim\mathcal{N}(0,\rho_{0}I)$

        2. (B)

Draw $\phi_{t,k}\sim\mathcal{N}(0,\tau_{0}I)$

      3. (iii)

Draw $w_{(t,d),i}$ , $z{t,d}$ and $l_{t,d}$ according to Eq.5, Eq.6, and Eq.7

##  4\. Scalable Inference

###  4.1. Integrating Variables

We start with the joint probability of the model and seek a collapsed version
of it, $P(s,z,w,l|\mu,\sigma,\gamma,\Delta,\alpha,\rho_{0},\tau_{0})$ by
integrating out the natural parameters $\phi_{t,k}$ and $\pi_{t,k}$. In the
following derivations, we will omit hyper-parameters and use “$\cdot$” to
annotate them for cleaner notation. We also define $g(\cdot)$ to be the
likelihood function. The location likelihood $g(\pi_{t,k})$ and the text
likelihood $g(\phi_{t,k})$ are defined in Equation 10 and Equation 11,
respectively. Here $n^{\pi}_{t,k,g}$ and $n^{\phi}_{t,k,i}$ are the number of
occurrence in cluster $k$ at time $t$ for location component $g$ and
vocabulary $i$, respectively.

(10) $\displaystyle g(\pi_{t,k})$
$\displaystyle=\prod_{d=1}^{D_{t}}P(z_{t,d}|\pi_{t,k},s_{t,d}=k)=\prod_{g}\bigl{(}\frac{e^{\pi_{t,k,g}}}{\sum_{j}e^{\pi_{t,k,j}}}\bigr{)}^{n^{\pi}_{t,k,g}}$

(11) $\displaystyle g(\phi_{t,k})$
$\displaystyle=\prod_{d=1}^{D_{t}}P(w_{t,d}|\phi_{t,k},s_{t,d}=k)=\prod_{i}\bigl{(}\frac{e^{\phi_{t,k,i}}}{\sum_{j}e^{\phi_{t,k,j}}}\bigr{)}^{n^{\phi}_{t,k,i}}$

By utilizing the notations defined above, the integration can be expressed in
Equation 12. Here we use $\tau_{k}$ to denote the fist time step when cluster
$k$ occurs. We also define $\psi^{\pi}_{t,k}=0$ when $t=\tau_{k}$ and
$\psi^{\pi}_{t,k}=\pi_{t-1,k}$ if $t>\tau_{k}$. A similar definition is
applied to $\psi^{\phi}_{t,k}$.

(12) $\displaystyle P$ $\displaystyle(s,z,w,l|\cdot)$ $\displaystyle=$
$\displaystyle\prod_{k=1}^{K}\prod_{t=\tau_{k}}^{T}\int_{\pi_{t,k}}g(\pi_{t,k})P(\pi_{t,k}|\psi^{\pi}_{t,k})\int_{\phi_{t,k}}g(\phi_{t,k})P(\phi_{t,k}|\psi^{\phi}_{t,k})$
$\displaystyle\prod_{t=1}^{T}\prod_{t=\tau_{k}}^{T}\prod_{d=1}^{D_{t}}P(s_{t,d}|s_{1:(t,d)-1})P(l_{t,d}|\mu_{k},\Sigma_{k},z_{t,d}=k)$

The key to the integration is to correctly deal with terms involving the
likelihood function $g(\cdot)$ and its priors,
$\prod_{t=\tau_{k}}^{T}\int_{\pi_{t,k}}g(\pi_{t,k})P(\pi_{t,k}|\psi^{\pi}_{t,k})$.
As we will see shortly, we can conduct integrations in a chain fashion from
the very beginning when $t=\tau_{k}$ all the way to the end when $t=T$. When
an integration is done for a specific time step, we will get a constant term
and a “future term”. The future term, which we denote as
$f_{t,k}(\pi_{t+1,k}|\theta_{t,k})$ contains the information for a future
integration and will participate in the integration for the next time step.
The constant term, which we annotate as $D_{t,k}$ will be emitted as part of
our final integration result. Here we will focus on the terms that involves
$\pi$ and we will omit the procedures for $\phi$ since it can be derived
similarly.

As we mentioned above, the future term $f_{t,k}(\pi_{t+1,k}|\theta_{t,k})$ is
generated as part of the integration result at time $t$. It contains variable
$\pi_{t+1,k}$ that will participate the integration of the next time step
$t+1$ with parameter $\theta_{t,k}$ that is determined by information on the
previous time steps. To illustrate how the future term
$f_{t,k}(\pi_{t+1,k}|\theta_{t,k})$ interplay with the integration, we define
the following relationship in Equation 13. We also assume that
$f_{t-1,k}(\pi_{t,k}|\theta_{t-1,k})$ is in the form of Gaussian distribution
with mean $\theta_{t-1,k}$ and covariance matrix $\rho_{0}I$. We will prove
this using mathematical induction.

(13)
$\displaystyle\int_{\pi_{t,k}}g(\pi_{t,k})P(\pi_{t+1,k}|\pi_{t,k},\rho_{0}I)f_{t-1,k}(\pi_{t,k}|\theta_{t-1,k})$

For the base cases, where $t=\tau_{k}-1$ we define
$f_{\tau_{k}-1,k}(\pi_{t=\tau_{k},k}|\theta_{\tau_{k}-1,k})$ to be a zero mean
Gaussian with covariance matrix $\rho_{0}I$. One can validate this definition
by taking $f_{\tau_{k}-1,k}(\pi_{t=\tau_{k},k}|\theta_{\tau_{k}-1,k})$ into
Equation 13 to get the expression for the first integration.

(14) $\displaystyle
f_{\tau_{k}-1,k}(\pi_{t=\tau_{k},k}|\theta_{\tau_{k}-1,k})=\mathcal{N}(\pi_{t,k}|0,\rho_{0}I)$

For the general case where $\tau_{k}\leq t<T$, we define the recursive formula
of $f_{t,k}(\cdot)$ in Equation 16 to be the integration of $\pi_{t,k}$
divided by a constant $D_{t,k}$, which is defined in Equation 15 and is
designed to absorb all constants that are not related to the Gaussian
distribution to “participate” in the next round of integration.

(15) $\displaystyle
D_{t,k}=\mathcal{N}(\widehat{\pi_{t,k}}|\theta_{t-1,k},\rho_{0}I)(2\pi)^{d/2}|\Sigma_{t,k}|^{1/2}N_{t,k}^{-d/2}g(\widehat{\pi_{t,k}})$

Here we utilize the induction assumption that $f_{t-1,k}$ is a Gaussian
distribution with mean $\theta_{t-1,k}$ and covariance matrix $\rho_{0}I$. We
also use Laplace Approximation to approximate the integral around a point
$\widehat{\pi_{t,k}}$, which will be discussed in more detail in the next sub-
section. After letting $D_{t,k}$ to absorb all the constants, we again get a
Gaussian form of $f_{t,k}(\cdot)$ with mean value equal to
$\widehat{\pi_{t,k}}$ and covariance matrix $\rho_{0}I$.

(16) $\displaystyle f_{t,k}$ $\displaystyle(\pi_{t,k}|\theta_{t-1,k})$
$\displaystyle=\frac{\int_{\pi_{t,k}}P(\pi_{t+1,k}|\pi_{t,k},\rho_{0}I)\cdot
f_{t-1,k}(\pi_{t,k}|\theta_{t-1,k})g(\pi_{t,k})}{D_{t,k}}$
$\displaystyle=\frac{\int_{\pi_{t,k}}\mathcal{N}(\pi_{t,k}|\frac{\pi_{t+1,k}+\theta}{2},\rho_{0}I/2)\mathcal{N}(\pi_{t+1,k|\theta_{t-1,k},2\rho_{0}I})g(\pi_{t,k})}{D_{t,k}}$
$\displaystyle=\mathcal{N}(\widehat{\pi_{t,k}}|\frac{\pi_{t+1,k}+\theta_{t-1,k}}{2},\rho_{0}I/2)\mathcal{N}(\pi_{t+1,k|\theta_{t-1,k},2\rho_{0}I})$
$\displaystyle\hskip
11.9501pt\frac{g(\widehat{\pi_{t,k}})(2\pi)^{d/2}|\Sigma|^{1/2}N^{-d/2}}{D_{t,k}}$
$\displaystyle=\mathcal{N}(\pi_{t+1,k}|\widehat{\pi_{t,k}},\rho_{0}I)\mathcal{N}(\widehat{\pi_{t,k}}|\theta_{t-1,k},\rho_{0}I)$
$\displaystyle\hskip
11.9501pt\frac{(2\pi)^{d/2}|\Sigma_{t,k}|^{1/2}N_{t,k}^{-d/2}g(\widehat{\pi_{t,k}})}{D_{t,k}}$
$\displaystyle=\mathcal{N}(\pi_{t+1,k}|\widehat{\pi_{t,k}},\rho_{0}I)$

Note that we do not define $f_{t,k}(\cdot)$ when $t=T$ since there will be no
term to contribute to future integrations. To summarize, the integration of
$\pi_{t,k}$ over time equals to the $\prod_{t=\tau_{k}}^{T}D_{t,k}$. We can
use the same technique to get the integration of $\phi_{t,k}$ to be
$\prod_{\tau_{k}}^{T}C_{t,k}$ with $C_{t,k}$ defined below:

(17) $\displaystyle
C_{t,k}=\mathcal{N}(\widehat{\phi_{t,k}}|\theta_{t,k},\rho_{0}I)(2\pi)^{d/2}|\Sigma|^{1/2}N^{-d/2}g(\widehat{\phi_{t,k}})$

We then use the same notation to get the joint distribution after $\pi$ and
$\phi$ are integrated out by taking the results in the previous steps into
Equation 12:

(18) $\displaystyle P(s,z,w,l|\cdot)=$
$\displaystyle\prod_{t=1}^{T}\prod_{k=1}^{K_{t}}C_{t,k}D_{t,k}$
$\displaystyle\prod_{t=1}^{T}\prod_{d=1}^{D_{t}}P(s_{t,d}|s_{1:(t,d)-1})P(l_{t,d}|\mu,\Sigma,z_{t,d})$

The collapsed joint distribution thus leaves only two variables to be
inferred: $z_{t,d}$ and $s_{t,d}$ for each document $(t,d)$. In experiments we
found that the MCMC converges very quickly and only several Gibbs iteration
steps are necessary for the algorithm to reach convergence.

###  4.2. Laplace Approximation to Marginal Likelihood

Although we have discussed the general form of the joint distribution after
the integration, we haven’t covered the details on how we conducted the
Laplace Approximation when taking the integral. As seen in Equation 2,
Laplace’s method approximates the integral around a specific point where the
majority of the probability mass lies on. In our case, $h(\cdot)$ takes the
form of a negative log of a Multinomial likelihood function with a Gaussian
prior.

Ideally, we should choose $\widehat{\pi_{t,k}}$ to minimize $h(\pi_{t,k})$.
However, when we use sequential techniques to solve the model, we do not have
the knowledge of cluster parameters in the next time step, $\pi_{t+1,k}$,
which is required to evaluate $h(\pi_{t,k})$. Instead, we use the expectation
of its prior information $\pi_{t-1,k}$ to approximate $h(\pi_{t,k})$.
$h(\pi_{t,k})$ then becomes:

(19) $\displaystyle h(\pi_{t,k})=$
$\displaystyle\frac{-\log\bigl{(}\mathcal{N}(\pi_{t,k}|\frac{\theta_{t-1,k}+\pi_{t+1,k}}{2},\frac{\rho_{0}^{2}}{2}I)g(\pi_{t,k})\bigr{)}}{N_{t,k}}$
$\displaystyle=$
$\displaystyle\frac{-\log\bigl{(}\mathcal{N}(\pi_{t,k}|\theta_{t-1,k},\frac{\rho_{0}^{2}}{2}I)g(\pi_{t,k})\bigr{)}}{N_{t,k}}$

When the sample size $N_{t,k}$ is large enough, the impact of the prior will
be very small and a natural selection of $\widehat{\pi_{t,k}}$ will be the one
that maximize its likelihood. This solution is illustrated in Equation 20 as
Solution 1 and is used by (Ahmed and Xing, 2008). Here, we illustrate the
solution by its logistic form rather than its original form, which is more
useful since $g(\pi_{t,k})$ utilizes the logistic form of $\pi_{t,k}$. This
solution simply normalizes the number of documents having the locations in
spatial component $i$ for each cluster $k$ at time $t$, $N^{\pi}_{t,k,i}$ with
the total number of documents that belong to cluster $k$ at time $t$,
$N^{\pi}_{t,k}$. However, this solution ignores all the historical data before
time $t$ since it ignored the prior information.

(20) $\displaystyle
Solution1:\frac{e^{\widehat{\pi_{t,k,i}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}=\frac{N^{\pi}_{t,k,i}}{N^{\pi}_{t,k}}$

Another solution that can be used as an natural comparison to Solution 1 is to
use the document count of all historical data that cluster $k$ has on this
location component $i$ instead of the count just on this particular time step.
Equation 21 illustrates the exact form of Solution 2. Here the solution is
taken to be the normalized count of all the documents belong to cluster $k$
that are located in location component $i$, $N^{\pi}_{k,i}$. This solution,
however, ignores the temporal importance and information across all time steps
are treated equally.

(21) $\displaystyle
Solution2:\frac{e^{\widehat{\pi_{t,k,i}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}=\frac{N^{\pi}_{k,i}}{N^{\pi}_{k}}$

However, we note that neither of the solutions above take into account of the
prior information. A better approach is to solve $\widehat{\pi_{t,k}}$ to
minimize the whole $h(\pi_{t,k})$ rather than only the likelihood part. In
order to do this, we take the derivative of Equation 19 and set it to zero.
After we assume that $\sum_{j}e^{\pi_{t,k,j}}=1$, we are left with the
relations in Equation 22.

(22)
$\displaystyle\frac{2\theta_{t,k,i}+n_{t,k,i}\rho_{0}^{2}}{n_{t,k}}-\frac{2}{\rho_{0}^{2}n_{t,k}}\pi_{t,k,i}=e^{\pi_{t,k,i}}$

A novel observation of the present work is that the above equation falls into
the set of problems that can be solved using the notation of _Lambert’s W_
(Corless et al., 1996). Conveniently, this solution can be expressed
analytically and we illustrate it in Equation 23 in the logistic form. In this
equation, we define $n^{{}^{\prime}}_{t,k,i}$ such that
$e^{\theta_{t,k,i}}=\frac{n^{{}^{\prime}}_{t,k,i}}{n_{t,k}}$ to represent the
pseudo counting that is introduced by the prior, an important trick that will
be utilized later.

(23)
$\displaystyle\frac{e^{\widehat{\pi_{t,k,i}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}$
$\displaystyle=\frac{2}{\rho_{0}^{2}n_{t,k}}W(\frac{e^{\theta_{i}}\rho_{0}^{2}n_{t,k}}{2}e^{\frac{\rho_{0}^{2}n_{t,k,i}}{2}})$
$\displaystyle=\frac{2}{\rho_{0}^{2}n_{t,k}}W(\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2}e^{\frac{\rho_{0}^{2}n_{t,k,i}}{2}})$

We observed that terms inside Lambert W’s function can be bounded by two
quantities.

(24)
$\displaystyle\min\\{\frac{\rho_{0}^{2}n_{t,k,i}}{2}e^{\frac{\rho_{0}^{2}n_{t,k,i}}{2}},\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2}e^{\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2}}\\}$
$\displaystyle\leq\frac{e^{\widehat{\pi_{t,k,i}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}\leq$
$\displaystyle\max\\{\frac{\rho_{0}^{2}n_{t,k,i}}{2}e^{\frac{\rho_{0}^{2}n_{t,k,i}}{2}},\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2}e^{\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2}}\\}$

By utilizing the fact that $W(xe^{x})=x$, we know that the actual solution of
$\frac{e^{\widehat{\pi_{t,k,i}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}$ must lie
in the linear combination of its lower and upper bounds. A good choice of the
linear weight is the use the information on the variance, $\rho_{0}$. Since
$\rho_{0}$ controls the amount of information that we can allow to change from
one time step to the other, a natural choice of the combination weight would
be $1/(1+\rho_{0})$ and $\rho_{0}/(1+\rho_{0})$. We put weight
$1/(1+\rho_{0})$ on the bound that contains the information about the prior
while using $\rho_{0}/(1+\rho_{0})$ on the bound that contains the information
on the current time step. Our solution, which here will be referred to as
Solution 3, takes the linear combination of the document count $n_{t,k,i}$ at
time $t$ of cluster $k$ on component $i$ and the pseudo document count on the
prior $n^{{}^{\prime}}_{t,k,i}$ normalized by the total number of documents
that belong to cluster $k$ on this time step $t$, $n_{t,k}$. And since
$n^{{}^{\prime}}_{t,k,i}$ is normalized by $n_{t,k}$, our solution takes value
range from 0 to 1.

(25) $\displaystyle
Solution3:\frac{e^{\widehat{\pi_{t,k,i}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}$
$\displaystyle=\frac{2}{\rho_{0}^{2}n_{t,k}}\bigl{(}\frac{1}{1+\rho_{0}}W(\frac{\rho_{0}^{2}n_{t,k,i}}{2}e^{\frac{n_{t,k,i}\rho_{0}^{2}}{2}}\bigr{)}+\frac{\rho_{0}}{1+\rho_{0}}W(\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2}e^{\frac{n^{{}^{\prime}}_{t,k,i}\rho_{0}^{2}}{2}}))$
$\displaystyle=\frac{2}{\rho_{0}^{2}n_{t,k}}(\frac{1}{1+\rho_{0}}\frac{\rho_{0}^{2}n_{t,k,i}}{2}+\frac{\rho_{0}}{1+\rho_{0}}\frac{\rho_{0}^{2}n^{{}^{\prime}}_{t,k,i}}{2})$
$\displaystyle=\frac{\frac{1}{1+\rho_{0}}n^{{}^{\prime}}_{t,k,i}+\frac{\rho_{0}}{1+\rho_{0}}n_{t,k,i}}{n_{t,k}}$

We can derive a similar solution for the optimal points to be used in Laplace
approximation for $\phi_{t,k}$. For the length of this paper we will omit the
exact derivation since the results are highly similar.

###  4.3. Sample Cluster Index $s_{t,d}$

Starting from Equation 18, it is now straightforward to derive Equation 26 to
sample the cluster index $s_{t,d}$ for each document. Here we see that the
equation is linear to the number of words in the document, $N_{t,d}$. We need
to choose one of the three solutions proposed in the previous section to
substitute $\widehat{\phi_{t,k,n}}$ and $\widehat{\pi_{t,k,z}}$.
$P(s_{t,d}|s_{1:(t,d)-1})$ is the RCRP prior defined in Equation 1.

(26) $\displaystyle P$
$\displaystyle(s_{t,d}=k|s_{1:(t,d)-1},w_{t,d},z_{t,d})$
$\displaystyle\propto\prod_{n=1}^{N_{t,d}}\bigl{(}\frac{e^{\widehat{\phi_{t,k,w_{t,d,n}}}}}{\sum_{j}e^{\widehat{\phi_{t,k,j}}}}\bigr{)}^{N_{d,t,i}}\bigl{(}\frac{e^{\widehat{\pi_{t,k,z_{t,d}}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}\bigr{)}P(s_{t,d}|s_{1:(t,d)-1})$

###  4.4. Sample Region Index $z_{t,d}$

Similarly, we can derive the equation to sample the location region index
$z_{t,d}$ for each document from the joint distribution in Equation 18. Here
we see that the probability of selecting $z_{t,d}$ is proportional to the
logistic normal component
$\frac{e^{\widehat{\pi_{t,k,z}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}$ and
$P(l_{t,d}|\mu_{z},\Sigma_{z})$, which is the Gaussian probability of location
$sl_{t,d}$ on the $z_{t}h$ component of the Gaussian prior.

(27) $\displaystyle
P(z_{t,d}=z|s_{t,d}=k,l_{t,d})\propto\bigl{(}\frac{e^{\widehat{\pi_{t,k,z}}}}{\sum_{j}e^{\widehat{\pi_{t,k,j}}}}\bigr{)}P(l_{t,d}|\mu_{z},\Sigma_{z})$

###  4.5. SMC Updates

As we stated in the background section, SMC evaluates a weight for each
particle and we need to update this weight every time after we have sampled a
new document. Our result is illustrated in Equation 28. Here we see that the
weight update is proportional to the likelihood of the newly sampled data.

(28) $\displaystyle\omega_{1:(t,d)}^{f}\propto$
$\displaystyle\omega_{1:(t,d)-1}^{f}\prod_{n=1}^{N_{t,d}}P(w_{t,d,n}=v|s_{t,d}=k,\phi_{t,k,v})$
$\displaystyle P(l_{t,d}|z_{t,d}=z,\mu_{z},\Sigma_{z})$

###  4.6. Algorithm

The general procedure of our approach is illustrated in Algorithm 1. We
organize our data into epochs and for each epoch $t$ we process documents one
by one. For each document $(t,d)$, only two variables $z$ and $s$ are sampled
and we iterate through the MCMC step $MaxIter$ times. Particle weights are
then updated and we evaluate whether it is necessary to resample particles by
comparing the L2 norm of the particle weight to a threshold.

Algorithm 1 Particle Filtering Algorithm Framework

1:Initialize $\omega_{1}^{f}$ to $\frac{1}{F}$ for all $f\in\\{1,..F\\}$

2:for epoch $t$ from $1$ to $T$ do

3: for document $d$ from $1$ to $D_{t}$ do

4: for particle $f\in\\{1,..F\\}$ do

5: for iter $\in MaxIter$ do

6: Sample $s$,$z$ using Eq. 26 and 27

7: end for

8: Update $\omega^{f}$ using Eq. 28

9: end for

10: Normalize particle weight $\omega^{f}$

11: if $||\omega_{t}||_{2}^{-2}<$ threshold then

12: resample particles

13: end if

14: end for

15:end for

##  5\. Data

We collected Twitter data from August, 2010 to September, 2012 using Twitter’s
Decahose API. Only tweets with geo-coordinates within United States are kept;
everything else is discarded. We conducted basic natural language processing
on the data and deleted stop words and punctuations. Words in the documents
are converted to lower cases and are tokenized. Low frequency words that
appear below a threshold are deleted. At the end, we are left with a
dictionary size of 40,173 unique tokens and a document size of 5,298,978. We
keep 90$\%$ of them for training and $10\%$ of them for testing.

Table 2. Summary of dataset used in the experiment Item | Statistics
---|---
Spatial Coverage | United States
Temporal Coverage | Aug, 2010 to Sep, 2012
Vocabulary Size | 40,173
Num. Documents | 5,298,978

##  6\. Experimental Results

###  6.1. Qualitative Results

We first evaluate our model qualitatively by manually examining the contents
of various topics (clusters) uncovered by the model during out experiment.
Figure 2 illustrates one particular cluster that demonstrates the ability of
the model to capture an evolving spatio-temporal topic focused on the Super
Bowl, the championship game of the National Football League (NFL). As a
convenience, we also list a fact sheet about the Super Bowls in these two
years, which can be found in Table 3. Shown in Figure 2 are two pairs of
summary figures (split by the left and right) characterizing the
parameterizations of a single topic detected by the algorithm we propose. The
pair of figures on the left characterizes the representative distributions of
this topic in February 2011, the pair on the right characterizes these same
distributions in February 2012. Each pair of figures is characterized by a
word cloud (top) that represents the distribution of words for the topic and a
map (bottom) with dots representing the spatial distribution of the topic in
terms of weights in its mixture distribution over the modeled spatial centers.

Clearly, the two events characterized in Figure 2 share many common terms
relevant to the Super Bowl in general - “super”, “bowl”, and “Sunday” being
examples. However, at these two different points in time, this topic also
exhibits important distinct properties. In the word cloud visualization of the
2011 Super Bowl (top left of Figure 2, we see words such as “Steelers” and
“Packers”, which were the names of the two competing teams in that year.
Further, the spatial distribution of the event topic at this time clearly
highlights an area in central Texas, which was the actual location at which
the Super Bowl was held event is held at that year. Since the Super Bowl is a
nationwide event, the method also captures minor levels of activity across the
country.

In contrast, on the right hand side of Figure 2, we see terms relevant to the
2012 Super Bowl, including the names of the two teams playing in it (“Giants”
and “Patriots”). Importantly, teams from the previous year are no longer
important to the topic, even though terms relevant to the Super Bowl itself
have been retained. Similarly, the spatial visualization clearly illustrated
the spatial center of the event, which lies in the state of Indiana, but as
the Super Bowl was still a nationwide event in 2001, location of interests
exist across the country. This is particularly true in 2012, relative to 2011,
in the New York City and Boston areas, which are where the two teams playing
in the game were from.

This analysis of the output of our model gives us confidence that the model
can capture events of interest in the manner expected. We now turn to a
quantitative analysis of model performance on several different prediction
problems.

Table 3. Fact sheet about the Superbowl Event | Superbowl XLV | Superbowl XLVI
---|---|---
Time | February 6, 2011 | February 5, 2012
Location | Arlington, TX | Indianapolis, IN
Teams | Pittsburgh Steelers | New York Giants
Green Bay Packers | New England Patriots

(a) Superbowl event on February 2011

(b) Superbowl event on February 2012

Figure 2. Superbowl Event Detected by Our Algorithm

###  6.2. Numerical Results

We conducted numerical results by first training our model using $90\%$ of the
data and then testing it on the rest of the data set by measuring its testing
perplexity and the Mean Square Error (MSE) of prediction on held out document
locations. We compared three different solutions for Laplace approximation in
Eq. 20, Eq. 21 and Eq. LABEL:eq2:lambert_final. Although our theoretical
results favor Solution 3, comparison is still important since prior work
reported using Solution 1 and Solution 2 in similar models.

In the perplexity result in Figure 3, we tested for results using various
parameterizations of the model and the three different solutions for the
Laplace approximation. Here, perplexity is calculated according to Equation
29. The first thing we see here is that Solution 3 generally performs better
than the other two baseline approaches. However, it is clear that this result
is impacted by the setting of model parameters.

Figure 3. Perplexity and prediction for document location when model
parameters are changed

For example, perplexity on testing data changes with the parameter $\alpha$,
which is the decay factor of the RCRP prior defined in Equation 1\- the
perplexity when $\alpha$ is large is generally better than those with smaller
$\alpha$. Our proposed approach (Solution 3) beats the other two baseline
methods when $\alpha$ is larger than $0.1$. This indicates that our model
prefers a less radical weight distribution on previous epochs. Instead, taking
more epochs into considerations generates a much better result.

We observe a similar pattern for variable $\gamma$, which is a dispersion
parameter that controls the way that new clusters are created in the model. We
see that a high $\gamma$ yields a better performance for our proposed
approach, which is not surprising since generally the higher model complexity
the better expressiveness the model will be able to generalize our data.

The pattern of perplexity for variable $\tau_{0}$ is also very interesting.
Recall that $\tau_{0}$ is the Markov transiting prior that controls the
variance of the same topic from one time to the other. Since both the baseline
solutions ignore this prior information, one of their performance will change
with $\tau_{0}$. Our approach, however, does change with $\tau_{0}$ and we can
clearly observe a region where our approach outperform the others. When
$\tau_{0}$ is close to infinity, our proposed approach approximates Solution
1. When $\tau_{0}$ is close to zero, no counting on the current time step
(i.e. $n_{t,k,i}$) is being used and nothing is being learned in the model.
The Markov transiting prior for location, $\rho_{0}$ has less impacts to the
perplexity results than the prediction error for location, which we will
discuss in the next paragraph.

(29) $\displaystyle
perp(\mathcal{D}_{test})=-\frac{\Sigma_{t}\Sigma_{d}\Sigma_{n}\log{p(w_{t,d,n}|s_{t,d}=k,\phi_{t,k})}}{\Sigma_{t}\Sigma_{d}\Sigma_{n}1}$

Figure 3 shows the Mean Square Error (MSE) for the task of prediction the
location specified of the left out posts. The results are illustrated in
Figure 3. Here we see that our proposed method (Solution 3) outperform the
baselines significantly throughout the range of the tested parameters. Most
parameters do not impact location prediction results. The only exception is
$\rho_{0}$, which is the Markov transitioning prior for location. Here we see
that the MSE climbed slightly with an increase of $\rho_{0}$ but declined
sharply after $\rho_{0}$ reaches $0.1$. This indicates that higher prior
values that put more weight on recent counting information are beneficial for
the model to effectively learn to predict locations.

##  7\. Conclusion

In this paper, we proposed a Bayesian non-parametric model to discover
evolutionary social events. We experimented with the model on Twitter data and
are able to identified evolutionary latent social events that change over time
- an example of the Super Bowl was given to highlight our model’s ability to
do so. There are several limitations to this paper that are open to potential
future work. First, the assumption that each document has to belong to a
specific event is a bit simplistic considering many tweets are not event-
centric. Second, the fact that the spatial priors are predetermined makes the
model difficult to deal with streaming data outside the predetermined spatial
regions. And finally, spatial components do not penalize towards their
distances to the event centers and this assumption can sometime generate
universal events that doesn’t contain any specific event information. Future
word should address these issues.

## References

  * (1)
  * Ahmed et al. (2011) Amr Ahmed, Qirong Ho, Choon H Teo, Jacob Eisenstein, Eric P Xing, and Alex J Smola. 2011\.  Online inference for the infinite topic-cluster model: Storylines from streaming text. In International Conference on Artificial Intelligence and Statistics. 101–109.
  * Ahmed and Xing (2008) Amr Ahmed and Eric P Xing. 2008.  Dynamic Non-Parametric Mixture Models and the Recurrent Chinese Restaurant Process: with Applications to Evolutionary Clustering.. In SDM. SIAM, 219–230.
  * Blei and Lafferty (2006) David M Blei and John D Lafferty. 2006.  Dynamic topic models. In Proceedings of the 23rd international conference on Machine learning. ACM, 113–120.
  * Blei and Lafferty (2007) D. M. Blei and J. D. Lafferty. 2007.  A correlated topic model of science.  The Annals of Applied Statistics (2007), 17–35.  http://www.jstor.org/stable/10.2307/4537420
  * Blei et al. (2003) David M. Blei, Andrew Y. Ng, and Michael I. Jordan. 2003\.  Latent dirichlet allocation.  J. Mach. Learn. Res. 3 (March 2003), 993–1022.  http://dl.acm.org/citation.cfm?id=944919.944937
  * Canini et al. (2009) Kevin Robert Canini, Lei Shi, and Thomas L Griffiths. 2009\.  Online Inference of Topics with Latent Dirichlet Allocation.. In AISTATS, Vol. 9. 65–72.
  * Chen et al. (2013) Jianfei Chen, Jun Zhu, Zi Wang, Xun Zheng, and Bo Zhang. 2013.  Scalable inference for logistic-normal topic models. In Advances in Neural Information Processing Systems. 2445–2453.
  * Corless et al. (1996) Robert M Corless, Gaston H Gonnet, David EG Hare, David J Jeffrey, and Donald E Knuth. 1996.  On the LambertW function.  Advances in Computational mathematics 5, 1 (1996), 329–359.
  * Doucet et al. (2001) Arnaud Doucet, Nando De Freitas, and Neil Gordon. 2001\.  An introduction to sequential Monte Carlo methods.  In Sequential Monte Carlo methods in practice. Springer, 3–14.
  * Du et al. (2015) Nan Du, Mehrdad Farajtabar, Amr Ahmed, Alexander J Smola, and Le Song. 2015.  Dirichlet-hawkes processes with applications to clustering continuous-time document streams. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 219–228.
  * Ferguson (1973) Thomas S Ferguson. 1973\.  A Bayesian analysis of some nonparametric problems.  The annals of statistics (1973), 209–230.
  * Griffiths and Steyvers (2004) Thomas L Griffiths and Mark Steyvers. 2004.  Finding scientific topics.  Proceedings of the National academy of Sciences 101, suppl 1 (2004), 5228–5235.
  * Hong et al. (2012) Liangjie Hong, Amr Ahmed, Siva Gurumurthy, Alexander J Smola, and Kostas Tsioutsiouliklis. 2012.  Discovering geographical topics in the twitter stream. In Proceedings of the 21st international conference on World Wide Web. ACM, 769–778.
  * Li et al. (2014) Aaron Q Li, Amr Ahmed, Sujith Ravi, and Alexander J Smola. 2014\.  Reducing the sampling complexity of topic models. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 891–900.
  * Wei et al. (2015) Wei Wei, Kenneth Joseph, Wei Lo, and Kathleen M Carley. 2015\.  A Bayesian Graphical Model to Discover Latent Events from Twitter. In Ninth International AAAI Conference on Web and Social Media.
  * Yao et al. (2009) Limin Yao, David Mimno, and Andrew McCallum. 2009.  Efficient methods for topic model inference on streaming document collections. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 937–946.