\documentclass[runningheads]{llncs}
\usepackage{graphicx}
\usepackage{comment}
\usepackage{amsmath,amssymb} %
\usepackage{color}
\usepackage{microtype}
\usepackage{wrapfig}
\usepackage{pifont}
\usepackage{color}
\usepackage{booktabs}
\usepackage{multirow}
\usepackage{subfigure}
\usepackage{etoolbox}
\usepackage{epsfig}
\usepackage{subfiles}

\newcommand{\smallsec}[1]{\vspace{0.2em}\noindent\textbf{#1}}

\usepackage[width=122mm,left=12mm,paperwidth=146mm,height=193mm,top=12mm,paperheight=217mm]{geometry}
\usepackage[pagebackref=true,breaklinks=true,letterpaper=true,colorlinks,bookmarks=false]{hyperref}
\begin{document}
\pagestyle{headings}
\mainmatter

\title{Unsupervised Learning of Video Representations via Dense Trajectory Clustering} %

\titlerunning{Unsupervised Learning of Video Representations via IDT Clustering}
\author{Pavel Tokmakov\inst{1}\and Martial Hebert\inst{1}\and Cordelia Schmid\inst{2}}
\institute{Carnegie Mellon University \and Inria}
\authorrunning{P. Tokmakov, et al.}
\maketitle

\begin{abstract}
This paper addresses the task of unsupervised learning of representations for action recognition in videos. Previous works proposed to utilize future prediction, or other domain-specific objectives to train a network, but achieved only limited success. In contrast, in the relevant field of image representation learning, simpler, discrimination-based methods have recently bridged the gap to fully-supervised performance. We first propose to adapt two top performing objectives in this class - instance recognition and local aggregation, to the video domain. In particular, the latter approach iterates between clustering the videos in the feature space of a network and updating it to respect the cluster with a non-parametric classification loss. We observe promising performance, but qualitative analysis shows that the learned representations fail to capture motion patterns, grouping the videos based on appearance. To mitigate this issue, we turn to the heuristic-based IDT descriptors, that were manually designed to encode motion patterns in videos. We form the clusters in the IDT space, using these descriptors as a an unsupervised prior in the iterative local aggregation algorithm. Our experiments demonstrates that this approach outperform prior work on UCF101 and HMDB51 action recognition benchmarks\footnote{\url{https://github.com/pvtokmakov/video_cluster}}. We also qualitatively analyze the learned representations and show that they successfully capture video dynamics.
\keywords{unsupervised representation learning, action recognition}
\end{abstract}
\section{Introduction}
The research on self-supervised learning of image representation has recently experienced a major breakthrough. Early approaches carefully designed objective functions to capture properties that the authors believed would result in learning rich representations~\cite{doersch2015unsupervised,noroozi2016unsupervised,gidaris2018unsupervised,zhang2016colorful}. For instance, Doersch et al.~\cite{doersch2015unsupervised} proposed to predict relative positions of two patches in an image, and Zhang et al.~\cite{zhang2016colorful} trained a network to colorize images. 
However, they have achieved only limited success. The methods that have brought the performance of self-supervised image representations close to those learned in a fully-supervised way, rely on a different principle instead.  
They use the standard cross-entropy loss and either treat each image as an individual class~\cite{dosovitskiy2014discriminative,wu2018unsupervised,oord2018representation}, or switch between clustering images in the feature space of the network, and updating the model to classify them into clusters~\cite{caron2018deep,zhuang2019local}. The resulting representations effectively capture discriminative image cues without having to manually separate images into categories.

Self-supervised feature learning for videos has so far mostly relied on manually designed objective functions. While some works adopted their objectives directly from the image-based methods, such as predicting video rotation~\cite{jing2018self}, or relative position of space-time patches~\cite{kim2019self}, others utilize video-specific cues, such as predicting feature representations of video patches in future frames~\cite{han2019video}. Very recently, Sun et al.~\cite{sun2019contrastive}, have proposed a variant of the instance classification objective for videos.

In this work we first investigating whether the recent, classification-based objectives proposed for image representation learning can be applied to videos. We  introduce a video variant of the non-parametric Instance Recognition approach of Wu et al.,~\cite{wu2018unsupervised}  (Video IR). It simply treats each video as its own class and trains a 3D ConvNet~\cite{tran2015learning,hara2018can} to discriminate between the videos. We observe that this naive approach is already competitive with prior work in the video domain.

To further improve the results, we capitalize on the observation of Zhuang et al.~\cite{zhuang2019local} that  embedding semantically similar instances close to each other in feature space is equally important to being able to discriminate between any two of them. We adapt their Local Aggregation approach to videos (Video LA). As shown in the top part of Figure~\ref{fig:meth}, this method first encodes a video using a 3D ConvNet, and the resulting embeddings are clustered with K-means. A non-parametric clustering loss proposed in~\cite{zhuang2019local} is then used to update the network and the algorithm is iterated in an Expectation-Maximization framework. This approach results in an improvement over Video IR, but the gap between the two objectives remains smaller than in the image domain.

We identify the reasons behind this phenomenon, by examining the video clusters discovered by the algorithm. Our analysis shows that they mainly capture appearance cues, such as scene category, and tend to ignore the temporal information, which is crucial for the downstream task of action recognition. For instance, as shown in the top right corner of Figure~\ref{fig:meth}, videos with similar background, but different activities are embedded closer than examples of the same action. This is not surprising, since appearance cues are both dominant in the data itself, and are better reflected in the 3D ConvNet architecture.

To mitigate this issue, we turn to the heuristic-based video representations of the past.
Improved Dense Trajectories (IDT)~\cite{wang2013action} were the state-of-the-art approach for action recognition in the pre-deep learning era, and remained competitive on some datasets until very recently. The idea behind IDT is to manually encode the cues in videos that help to discriminate between human actions. To this end, individual pixels are first tracked with optical flow, and heuristics-based descriptors~\cite{dalal2005histograms,dalal2006human,wang2013dense} are aggregated along the trajectories to encode both appearance and motion cues.  

In this work, we propose to transfer the notion of similarity between videos encoded in IDTs to 3D ConvNets via non-parametric clustering. To this end, we first compute IDT descriptors for a collection of unlabeled videos. We then cluster these videos in the resulting  features space and use the non-parametric classification objective of~\cite{zhuang2019local} to train a 3D ConvNet to respect the discovered clusters (bottom part of Figure~\ref{fig:meth}). The network is first trained until convergence using the fixed IDT clusters, and then finetuned in the joint IDT and 3D ConvNet space with the iterative Video LA approach. The resulting representation outperforms the baselines described above by a significant margin. We also qualitatively analyze the clusters and find that they effectively capture motion information. 

Following prior work~\cite{han2019video,jing2018self,sun2019contrastive}, we use the large-scale Kinetics~\cite{carreira2017quo} dataset for self-supervised pretraining, ignoring the labels.  The learned representations are evaluated by finetuing on UCF101~\cite{soomro2012ucf101} and HMDB51~\cite{kuehne2011hmdb} action recognition benchmarks. To gain a better insight into the quality of the representations, we additionally provide an evaluation in a few-shot regime, using the model as a fixed feature extractor. 

\section{Related work}
\label{sec:rl}
In this section, we first briefly review previous work on image-based unsupervised representation learning. We then discuss various approaches to video modeling, and conclude by presenting relevant video representation learning methods.

\textbf{Image representation} learning from unlabeled data is a well explored topic. Due to space limitations, we will only review the most relevant approaches here. The earliest methods were built around auto-encoder architectures: one network is trained to compress an image into a vector in such a way, that another network is able to reconstruct the original image from the encoding~\cite{hinton2006fast,lee2009convolutional,kingma2013auto,donahue2016adversarial,goodfellow2014generative}. In practice, however, the success of generative methods in discriminative representation learning has been limited. 

Until very recently, manually designing self-supervised objectives has been the the dominant paradigm. For example, Doersch et al.~\cite{doersch2015unsupervised} and Noroozi and Favaro~\cite{noroozi2016unsupervised} predict relative positions of patches in an image, Zhang et al.~\cite{zhang2016colorful} learn to colorize images, and Gidaris et al.~\cite{gidaris2018unsupervised} learn to recognize image rotations. While these methods have shown some performance improvements compared to random network initialization, they remain significantly below a fully-supervised baseline. 
The most recent methods, instead of designing specialized objective functions, propose to use the standard cross-entropy loss and either treat every image as its own class~\cite{dosovitskiy2014discriminative,oord2018representation,wu2018unsupervised}, or switch between clustering the examples in the feature space of the network and updating the network with a classification loss to respect the clusters~\cite{caron2018deep,zhuang2019local}. These methods exploit the structural similarity between semantically similar images, to automatically learn a semantic image embedding. In this paper we adapt the methods of Wu et al.~\cite{wu2018unsupervised} and Zhuang et al.~\cite{zhuang2019local} to the video domain, but demonstrate that they do not perform as well due to the structural priors being less strong in videos. We then introduce explicit prior in the form of IDT descriptors and show this indeed improves performance.  

\textbf{Video modeling} has traditionally been approached with heuristics-based methods. Most notably, Dense Trajectories (DT)~\cite{wang2013dense} sample points in frames and track them with optical flow. Then appearance and motion descriptors are extracted along each track and encoded into a single vector. The discriminative ability of DT descriptors was later improved in~\cite{wang2013action} by suppressing camera motion with the help of a human detector, and removing trajectories that fall into background regions. 
The resulting representation focuses on relevant regions in  videos (humans and objects in motion) and encodes both their appearance and motion patterns.

More recently, the success of end-to-end trainable CNN representation has been extended to the video domain. Simonyan et al.~\cite{simonyan2014two} proposed to directly train 2D CNNs for action recognition, fusing several frames at the first layer of the network. Their approach, however, had a very limited capacity for modeling temporal information. This issue was later addressed in~\cite{tran2015learning} by extending the 2D convolution operation in time. Introduction of the large scale Kinetcis dataset for action recognition~\cite{carreira2017quo} was a major step forward for 3D CNNs. Pretrained on this dataset, they were finally able to outperform the traditional, heuristic-based representations. Several variants of 3D ConvNet architectures have been proposed since, to improve performance and efficiency~\cite{carreira2017quo,hara2018can,xie2017rethinking}. In this work, we demonstrate how the IDT descriptors can be used to improve unsupervised learning of 3D ConvNet representations.

\textbf{Video representation} learning from unlabeled data is a less explored topic. This is largely because the community has only recently converged upon the 3D ConvNets as thr standard architecture. Early methods used recurrent networks, or 2D CNNs, and relied on future-prediction~\cite{srivastava2015unsupervised}, as well as various manually designed objectives~\cite{mobahi2009deep,misra2016shuffle,lee2017unsupervised,gan2018geometry,fernando2017self}. In particular, several works utilized temporal consistency between consecutive frames as a learning signal~\cite{misra2016shuffle,lee2017unsupervised,mobahi2009deep}, whereas Gan et al.~\cite{gan2018geometry} used geometric cues, and Fernando et al.~\cite{fernando2017self} proposed the odd-one-out objective function.

With 3D ConvNets, generative architectures~\cite{kim2019self,vondrick2016generating}, as well as some self-supervised objectives have been explored~\cite{jing2018self,kim2019self,wang2019self}. For example, Jing et al.~\cite{jing2018self} train a model to predict video rotation, Kim et al.~\cite{kim2019self} use relative spatio-temporal patch location prediction as an objective, and Wang et al.~\cite{wang2019self} regress motion and appearance statistics. In another line of work, future frame colorization was explored as a self-supervision signal~\cite{vondrick2018tracking}. Recently, Han et al.~\cite{han2019video} proposed to predict feature representations of video patches in future frames. Most similarly, Sun et al.~\cite{sun2019contrastive} use a variant of the instance discrimination loss. In this work, we demonstrate that simply adapting instance discrimination~\cite{wu2018unsupervised} and local aggregation~\cite{zhuang2019local} objectives from the image to the video domain already achieves competitive results, and augmenting local aggregation with IDT priors further improves the results, outperforming the state-of-the-art.

\section{Method}
\label{sec:meth}
Our goal is to learn an embedding function $f_{\boldsymbol{\theta}}$ that maps videos $V = \{v_1, v_2, ..., v_N\}$ into compact descriptors $f_{\boldsymbol{\theta}}(v_i) = \boldsymbol{d}_i$ in such a way, that they can be discriminated based on human actions, using unlabeled videos. For instance, as shown in Figure~\ref{fig:meth}, we want the two videos of people to doing handstands to be close to each other in the embedding space, and well separated from the video of a person training a dog. 
Below, we first introduce the two objective functions used in our work - instance recognition~\cite{wu2018unsupervised} and local aggregation~\cite{zhuang2019local}, and then describe our approach of using IDT~\cite{wang2013action} descriptors as unsupervised priors in non-parametric clustering.

\subsection{Video instance recognition}
This objective is based on the intuition that the best way to learn a discriminative representation is to use a discriminative loss. And, in the absence of supervised class labels, treating each instance as a distinct class of its own is a natural surrogate. 

Using the standard softmax classification criterion, the probability of every video $v$ with the feature $\boldsymbol{d}$ belonging to its own class $i$ is expressed as:
\begin{equation}
    P(i | \boldsymbol{d}) = \frac{\exp(\boldsymbol{w}_{i}^T \boldsymbol{d})}{\sum_{j=1}^N{\exp(\boldsymbol{w}_{j}^T \boldsymbol{d})}},
\end{equation}
where $\boldsymbol{w}_j$ is the weight vector of the $j$'th classifier. In this case, however, every class contains only a single example, thus $\boldsymbol{w}_j$ can be directly replaced with $\boldsymbol{d}_j$. The authors of~\cite{wu2018unsupervised} then 
propose the following formulation of the class probability: 
\begin{equation}
    P(i | \boldsymbol{d}) = \frac{\exp(\boldsymbol{d}_{i}^T \boldsymbol{d} / \tau)}{\sum_{j=1}^N{\exp(\boldsymbol{d}_{j}^T \boldsymbol{d} / \tau)}},
\label{eq:instance_prob}
\end{equation}
where $\tau$ is a temperature parameter that controls the concentration level of the distribution, and helps convergence~\cite{wang2017normface,hinton2015distilling}. The final learning objective is the standard negative log likelihood over the training set.
Recall that training is done in batches, thus a memory bank of encodings $D = \{\boldsymbol{d}_1, \boldsymbol{d}_2, ..., \boldsymbol{d}_N\}$ has to be maintained to compute Equation~\ref{eq:instance_prob}. 

\begin{figure}
\begin{center}
  \makebox[0.9\textwidth]{\includegraphics[width=0.8\paperwidth]{figures/method2.png}}
  \caption{Our approach for unsupervised representation learning from video collections. Directly applying a non-parametric clustering objective results in a representation that groups videos based on appearance (top right corner). 
  To mitigate this issue, we propose to first cluster the videos in the space of IDT descriptors (bottom right corner), which results in a grouping that better reflects video dynamics. We then apply the non-parametric clustering loss to transfer the properties of this embedding to a 3D ConvNet.}
  \label{fig:meth}
\end{center}
\vspace{-20px}
\end{figure}

\subsection{Video local aggregation}
While being able to separate any two instances is a key property for an image or video embedding space, another, complementary and equally desirable property is minimizing the distance between semantically similar instances. To this end, Zhuang et al.~\cite{zhuang2019local} proposed to use clusters of instances instead of individual examples as class surrogates. We adapt their approach to the video domain, and briefly describe it below.

Firstly, the video embedding vectors ${\boldsymbol{d}_1, \boldsymbol{d}_2, ..., \boldsymbol{d}_N}$ are grouped into $K$ clusters $G = \{G_1, G_2, .., G_K\}$ using K-means. The embedding function $f_{\boldsymbol{\theta}}$ is then updated to respect the cluster, using the non-parametric clustering objective proposed in~\cite{zhuang2019local}, and the two steps are iterated in an EM-framework. In particular, for every instance $v_i$ together with its embedding $\boldsymbol{d}_i$, two sets of neighbours are identified: close neighbours $\boldsymbol{C}_i$ (shown with a dashed circle in Figure~\ref{fig:meth}) and background neighbours $\boldsymbol{B}_i$. Intuitively, close neighbours are those examples that fall into the same cluster as $v_i$ and background neighbors are simply those that have a small distance to $\boldsymbol{d}_i$ in the feature space (they include both close neighbors and hard negative examples). Please see~\cite{zhuang2019local} for more details on how $\boldsymbol{C}_i$ and $\boldsymbol{B}_i$ are constructed.

The objective is then to minimize the distance between $\boldsymbol{d}_i$ and its close neighbours (instances in the same cluster), while maximizing the distance to those background neighbors that are not in $\boldsymbol{C}_i$ (hard negatives). The authors formulate this objective in a probabilistic way as minimizing the negative log likelihood of $\boldsymbol{d}_i$ being recognized as a close neighbor, given that it is recognized as a background neighbor:
\begin{equation}
L(\boldsymbol{C}_i, \boldsymbol{B}_i | \boldsymbol{d}_i, \boldsymbol{\theta}) = -\log \frac{P(\boldsymbol{C}_i \cap \boldsymbol{B}_i | \boldsymbol{d}_i)}{P(\boldsymbol{B}_i | \boldsymbol{d}_i)},
\label{eq:localagg}
\end{equation}
where the probability of $\boldsymbol{d}$ being a member of a set $\boldsymbol{A}$ is defined as:
\begin{equation}
    P(\boldsymbol{A}| \boldsymbol{d}) = \sum_{i \in \boldsymbol{A}} P(i | \boldsymbol{d}),
\end{equation}
and the definition of $P(i | \boldsymbol{d})$ is adapted from Equation~\ref{eq:instance_prob}. Despite the involved formulation, one can see that this objective does exactly what it is intended to do - minimizes the distance between examples inside a cluster and maximize it between those belonging to different clusters in a non-parametric way.

Intuitively, the Local Aggregation objective relies on the structural similarity between semantically similar images, together with deep image prior in CNN architectures~\cite{ulyanov2018deep}, to form meaningful clusters in the embedding space. In videos, however, both structural and architectural priors are less strong. Indeed, pixels that are close to each other in the spatio-temporal volume of a video are not always strongly correlated due to the presence of object and camera and motion. On the architecture side, 3D ConvNets are also worse at capturing spatio-temoral patterns, compared to CNNs at capturing spatial patterns. To mitigate this lack of implicit priors, we propose to introduce an explicit one in the form of IDT descriptors. 

\subsection{IDT descriptors as priors for video representation learning}
While state-of-the-art architectures for action recognition~\cite{tran2015learning,carreira2017quo,hara2018can} simply extend 2D CNN filters into the temporal dimension, treating videos as spatio-temporal cuboids of pixels, classical approaches~\cite{wang2013dense,wang2013action} explicitly identified and encoded spatio-temporal interest points that are rich in motion patterns relevant to action classification. 
In our experiments, we use the original implementation of IDT~\cite{wang2013action} to compute video descriptors for unlabeled videos (shown in the lower part of Figure~\ref{fig:meth}). We supply the IDT extractor with human detection form the state-of-the-art Mask-RCNN~\cite{he2017mask} model trained on MS COCO~\cite{lin2014microsoft} for improved camera stabilization (see~\cite{wang2013action} for details). 

This method, however, produces thousands of descriptors $\boldsymbol{x} \in \mathcal{X}$ per video. To encode them into a compact vector we follow prior work~\cite{wang2013action,wang2019hallucinating} and first apply PCA to reduce the dimensionality of each individual trajectory descriptor $\boldsymbol{x_i}$. We then utilize Fisher vector coding~\cite{perronnin2010improving}, which is based on a Gaussian Mixture Model (GMM) with K components $G(w_k, \boldsymbol{\mu}_k, \boldsymbol{\sigma}_k)$, parameterized by mixing probability, mean, and diagonal standard deviation. The encoding for a trajectory descriptor $\boldsymbol{x}$ is then computed by stacking the derivatives of each components of the GMM with respect to mean and variance:
\begin{equation}
\phi^*_k(\boldsymbol{x}) = \frac{p(\boldsymbol{\mu}_k | \boldsymbol{x})}{\sqrt{w_k}}[\phi_k(\boldsymbol{x}), \frac{\phi_k^{'}(\boldsymbol{x})}{\sqrt{2}}],
\end{equation}
where the first- and second-order features $\phi_k, \phi_k^{'} \in R^D$ are defined as:
\begin{equation}
    \phi_k(\boldsymbol{x}) = \frac{(\boldsymbol{x} - \boldsymbol{\mu_k})}{\boldsymbol{\sigma}_k}, \phi_k^{'}(\boldsymbol{x}) = \phi_k(\boldsymbol{x})^{2} - 1,
\end{equation}
thus, the resulting Fisher vector encoding $\phi(\boldsymbol{x}) = [\phi^*_1(\boldsymbol{x}), \phi^*_2(\boldsymbol{x}), ..., \phi^*_k(\boldsymbol{x})]$ is of dimensionality $2KD$. To obtain the video-level descriptor $\boldsymbol{\psi}$, individual trajectory encodings are averaged $\boldsymbol{\psi} = avg_{\boldsymbol{x} \in \mathcal{X}}\phi(\boldsymbol{x})$, and power-~\cite{koniusz2018deeper} and l2-normalization are applied. Finally, to further reduce dimensionality, count sketching~\cite{weinberger2009feature} is used: $p(\boldsymbol{\psi}) = \boldsymbol{P}\boldsymbol{\psi}$,
where $\boldsymbol{P}$ is the sketch projection matrix (see~\cite{weinberger2009feature} for details). 

The resulting encoding $p(\boldsymbol{\psi})$ is a 2000-dimensional vector, providing a compact representation of a video, which captures discriminative motion and appearance information. Importantly, it is completely unsupervised. Both the PCA projection and the parameters of the Gaussian mixture model are estimated using a random sample of trajectory encodings, and matrix $\mathbf{P}$ is selected at random as well. 

To transfer the cues encoded in IDTs descriptors to a 3D ConvNet, we first cluster the videos in the $p(\boldsymbol{\psi})$ space with K-means, to obtain the clusters $G$. We then use $G$ to compute the sets of neighborhoods $(\boldsymbol{C}_i, \boldsymbol{B}_i)$ for each video $v_i$ in an unlabeled collection (shown in the bottom right corner on Figure~\ref{fig:meth}), and apply the objective in Equation~\ref{eq:localagg} to train the network. This forces the learned representation to capture the motion patterns that dominate the IDT space (note that IDTs encode appearance cues as well in the form of HOG descriptors).

Finally, we construct a joint space of IDT and 3D ConvNet representations by concatenating the vectors $\boldsymbol{d}$ and $p(\boldsymbol{\psi})$ for each video. We further finetune the network in this joint space for a few epochs. This step allows the model to capitalize on appearance cues encoded by the the expressive 3D ConvNet architecture. We analyze the resulting model quantitatively and qualitatively, and find that it both outperforms the state-of-the-art, and is better at capturing motion information.  
  
\section{Experiments}
\label{sec:exp}
\subsection{Datasets and evaluation}
We use the Kinetics~\cite{carreira2017quo} dataset for unsupervised representation learning and evaluate the learned models on UCF101~\cite{soomro2012ucf101} and HMDB51~\cite{kuehne2011hmdb} in a fully-supervised regime. Below, we describe each dataset in more detail.

\textbf{Kinetics} is a large-scale, action classification dataset collected by querying videos on YouTube.
We use the training set of Kinetics-400, which contains 235 000 videos, for most of the experiments in the paper, but additionally report results using fewer as well as more videos in Section~\ref{sec:vids}. Note that we do not use any annotations provided in Kinetics.

\textbf{UCF101} is a classic dataset for human action recognition, which consists of 13,320 videos, covering 101 action classes. It is much  smaller than Kinetics, and 3D ConvNets fail to outperform heuristic-based methods on it without fully-supervised pretraining on larger datasets. Following prior work~\cite{jing2018self,han2019video}, we use UCF101 to evaluate the quality of representations learned on Kinetics in an unsupervised way via transfer learning. In addition to using the full training set of UCF101, we report few-shot learning results to gain more insight into the learned representations. We use the first split of the dataset for ablation analysis, and report results averaged over all splits when comparing to prior work.

\textbf{HMDB51} is another benchmark for action recognition, which consists of 6,770 videos, collected from movies, and split into 51 categories. Due to the small size of the training set, it, poses an even larger challenge for learning-based methods. As with UCF101, we report ablation results on the first split, and use the results averaged over all splits for comparison to prior work. 

Following standard protocol, we report classification accuracy as the main evaluation criteria on UCF101 and HMDB51. However, this makes direct comparison between different approaches difficult, due to the differences in network architectures. Thus, whenever possible, we additionally report the fraction of the fully-supervised performance for the same architecture.

\subsection{Implementation details}
\label{sec:impl}
\subsubsection{Self-supervised objectives}
We study three self-supervised objective functions: Video Instance Recognition (Video IR), Video Local Aggregation (Video LA) and Video Local Aggregation with IDT prior. For Video IR we follow the setting of ~\cite{wu2018unsupervised} and set $\tau$ in Equation~\ref{eq:instance_prob} to 0.07. We use 4096 negative samples for approximating the denominator of Equation~\ref{eq:instance_prob}.

In addition to the parameters described above, Local Aggregation requires choosing the number of clusters $K$, as well as the number of runs of K-means that are combined for robustness. The authors of~\cite{zhuang2019local} do not provide clear guidelines on selecting these hyperparameters, so we choose to take the values used in their ImageNet experiments and decrease them proportionally to the size of Kinetics. As a result, we set $K$ to 6000 and the number of clusterings to 3. We validate the importance of this choice in Appendix~\ref{sec:obj}.

For experiments with with IDT priors we use exactly the same hyper-parameters for the LA objective as described above. We use the original implementation of ~\cite{wang2013action} to extract IDT descriptors. Human detections are computed with ResNet101 variant of Mask-RCNN~\cite{he2017mask} model pretrained on MS COCO~\cite{lin2014microsoft}. We evaluate the importance of human detections for the final performance of our approach in Appendix~\ref{sec:abl}. When computing Fisher vector encoding, we generally follow the setting of~\cite{wang2019hallucinating}. In particular, we set the feature importance to 90\% when computing PCA, and the number of components in GMM to 256. When fitting the PCA and GMM models we randomly choose 3500 videos from Kinetics and 500 IDT descriptors from each video, to get a representative sample. Note that extracting IDTs and encoding them into Fisher vectors does not require GPUs, and thus the code can be efficiently run in parallel on a CPU cluster. As a result, we were able to compute the descriptors for Kinetics in just 5 days.
\vspace{-15px}

\subsubsection{Network architecture and optimization}
Following most of the prior work, we use a 3D ResNet18 architecture~\cite{hara2018can} in all the experiments, but also report results with deeper variants in Appendix~\ref{sec:depth}. The embedding dimension for self-supervised objectives is set to 128, as in~\cite{zhuang2019local}. We use SGD with momentum to train the networks, and apply multi-scale, random spatio-temporal cropping for data augmentation, with exactly the same setting as in~\cite{hara2018can}. We also perform the standard mean subtraction. All the models are trained on 16 frames clips of spatial resolution of $112 \times 112$, unless stated otherwise.

During self-supervised learning we follow the setting of~\cite{zhuang2019local} and set the learning rate to 0.03, and momentum to 0.9, with batch size of 256. All the models are trained for 200 epoch, and the learning rate is dropped by a factor 0.1 at epochs 160 and 190. As in~\cite{zhuang2019local}, we initialize the LA models with 40 epoch of IR pretraining. 

When finetuning on UCF101 and HMDB51, we set the learning rate to 0.1 and momentum to 0.9, using batch size 128. We drop the learning rate by a factor of 0.1 when the validation performance stops improving. Following~\cite{jing2018self}, we freeze the first ResNet block when finetuning on UCF101, and the first two blocks on HMDB51 to avoid overfitting. During inference, for every video we sample five clips at random, using the center crop. The final prediction is obtained by averaging softmax scores over the five clips. For few-shot experiments, we use the protocol of~\cite{chen2019closer} and freeze the entire network, only learning a linear classifier.
\subsection{Analysis of self-supervised objectives}
We begin by comparing different variants of self-supervised objectives described in Section~\ref{sec:meth}. They are used to learn a representation on Kinetics-400 in a self-supervised way, and the resulting models are transferred to UCF101 and HMDB51. We additionally evaluate two baselines - Supervised, which is pretrained on Kinetics using ground-truth labels, and Scratch, which is initialized with random weights. The results are reported in Table~\ref{tab:anal}. 
\begin{table}[bt]
\caption{Comparison between variants of unsupervised learning objective using classification accuracy and fraction of fully supervised performance on the fist split of UCF101 and HMDB51. All models use a 3D ResNet18 backbone, and take 16 frames with resolution of $112 \times 112$ as input. Video LA with IDT prior consistently outperforms other objectives, with improvements on HMDB51 being especially significant.}
\label{tab:anal}
 \centering
  {
    \begin{tabular}{l|c@{\hspace{1em}}c@{\hspace{1em}}|c@{\hspace{1em}}c@{\hspace{1em}}}
        Method         & \multicolumn{2}{c|}{UCF101}           & \multicolumn{2}{c}{HMDB51}       \\\hline
        & Accuracy & \% sup. & Accuracy & \% sup. \\ \hline
     Scratch~\cite{hara2018can}
        & 42.4 & 50.2       & 17.1 & 30.3          \\\hline
    Video IR
        & 70.0 & 82.9       & 39.9 & 70.7        \\
    Video LA
        & 71.4 & 84.6       & 41.7 & 73.9         \\
    Video LA + IDT prior
        & \textbf{72.8} & \textbf{86.3}       & \textbf{44.0} & \textbf{78.0}      \\ \hline
    Supervised~\cite{hara2018can}
        & 84.4 & 100      & 56.4 & 100       \\ \hline
\end{tabular}
}
\vspace{-10px}
\end{table}

Firstly, we observe that supervised pretraining is indeed crucial for achieving top performance on both datasets, with the variant trained from scratch reaching only 50.2\% and 30.3\% of the accuracy of the fully supervised model on UCF101 and HMDB51 respectively. The gap is especially large on HMDB51, due to the small size of the dataset. Using the video variant of the Instance Recognition objective (Video IR in the table), however, results in a 27.6\% accuracy improvement on UCF101 and 22.8\% HMDB51, reaching 82.9\% and 70.7\% of the supervised accuracy respectively. Notice that this simple method already outperforms some of the approaches proposed in prior works~\cite{jing2018self,han2019video,kim2019self}. 

Next, we can see that the Local Aggregation objective (Video LA in the table) further improves the results, reaching 84.6\% and 73.9\% of the fully-supervised performance on UCF101 and HMDB51 respectively. This shows that despite the higher-dimensionality of the video data, this method is still able to discover meaningful clusters in an unsupervised way. However, the gap to the IR objective is smaller than in the image domain~\cite{zhuang2019local}. 

Finally, our full method, which uses IDT descriptors as an unsupervised prior when clustering the videos (Video LA + IDT prior in the table), is indeed able to further boost the performance, reaching 86.3\% and 78.0\% of fully supervised performance on the two datasets. The improvement over Video LA is especially significant on HMDB51. We explain this by the fact that categories in UCF101 are largely explainable by appearance, thus the benefits of better modeling the temporal information are limited on this dataset. In contrast, on HMDB51 capturing scene dynamics is crucial for accurate classification.

\subsection{Few-shot evaluation}
When finetuning a model, even on a datasets of modest size, like UCF101, the effect of self-supervised pretraining is confounded by the effectiveness of the adaptation strategy itself. Indeed, it has been show recently that, on several tasks that were traditionally used to measure the effectiveness of image-based unsupervised learning approaches, fully supervised performance can be achieved with no pretraining at all, by simply better utilizing the existing data~\cite{he2019rethinking}. Thus, to gain more insight into our objectives, we propose to use pretrained models as feature extractors, and learn linear classifiers in a few-shot regime. The results on UCF101 are reported in Table~\ref{tab:fs}.
\begin{table}[bt]
\caption{Comparison between variants of unsupervised learning objective on the first split of UCF101 in a few-shot regime, using classification accuracy. The networks are fully frozen, and a linear classifier is learned, gradually decreasing the amount of training data. The gap between unsupervised and supervised representations increases, but our full method (`Video LA + IDT') still outperforms other variants across the board.}
\label{tab:fs}
 \centering
  {
    \begin{tabular}{l|c@{\hspace{1em}}c@{\hspace{1em}}c@{\hspace{1em}}c@{\hspace{1em}}c@{\hspace{1em}}}
         Method  & 1-shot & 5-shot & 10-shot & 20-shot & All \\ \hline
     Scratch
        & 1.7 & 7.5       & 10.6 & 17.2 & 38.2         \\\hline
    Video IR
        & 13.4  & 27.7 & 35.2 & 42.4 & 56.5       \\
    Video LA &
        15.6 & 30.6       & 36.4 & 44.2 & 58.6        \\
    Video LA + IDT prior
        & \textbf{17.8} & \textbf{31.5}       & \textbf{38.4} & \textbf{45.5} & \textbf{58.8}      \\ \hline
    Supervised
        & 46.4 & 62.0      & 67.7 & 73.3 & 81.8       \\ \hline
\end{tabular}
}
\vspace{-10px}
\end{table}

The most important observation here is that the gap between fully-supervised and unsupervised representations increases as the data becomes scarcer. This shows that, despite being useful in practice, unsupervised pretraining is still far from making large datasets obsolete. Among the objectives studied in our work, however, Video LA with IDT prior shows the strongest performance across the board, and is especially effective in the low-data regime. 

\subsection{Qualitative analysis of the representations}
To gain further insight into the effect of our IDT prior on representation learning, we now visualize some of the clusters discovered by the vanilla LA, and the variant with the prior in Figures~\ref{fig:la} and~\ref{fig:fv} respectively. Firstly, we observe that, in the absence of external constraints LA defaults to using appearance, and primarily scene information to cluster the videos. For instance, the first cluster (top left corner) corresponds to swimming pools, the one on the top right seems to focus on grass, and the two clusters in the bottom row capture vehicles and backyards, irrespective of the actual scene dynamics. This is not surprising, since appearance cues are both more dominant in the data itself, and are better reflected by the 3D ConvNet architecture.
\begin{figure}
\vspace{-3px}
\begin{center}
  \makebox[0.9\textwidth]{\includegraphics[width=0.8\paperwidth]{figures/la1.png}}
  \caption{Visualization of the clusters discovered by the Video LA objective without IDT prior. This variant groups videos in the space of a 3D ConvNet. As a results, the clusters are primarily defined by the appearance, grouping swimming pools, grass fields, vehicles, and backyards. The activity happening in the videos does not seem to play a significant role.}
  \label{fig:la}
  \end{center}
 \vspace{-25px}
\end{figure}

\begin{figure}
\begin{center}
  \makebox[0.9\textwidth]{\includegraphics[width=0.8\paperwidth]{figures/fv1.png}}
  \vspace{-5px}
  \caption{Visualization of the clusters discovered by variant of Video LA objective that uses IDT prior. In contrast to the examples above, the videos are mainly grouped by motion properties, such as forward-backward hand motion, person rotation, fast person motion, and `riding' action.}
  \label{fig:fv}
\end{center}
 \vspace{-25px}
\end{figure}

In contrast, the model learned with IDT prior is better at capturing motion cues. For example, the cluster in the top left corner of Figure~\ref{fig:fv} is characterized by forward-backward hand motion, such as observed during cleaning or barbecuing. The cluster in the top-right captures humans spinning or rotating. The bottom left cluster mostly contains videos with very fast actor motion, and the one in the bottom right closely corresponds to the action `riding'. 

Importantly, neither set of clusters is perfectly aligned with the definition of actions in popular computer vision dataset. For instance, despite having a clear motion-based interpretation, the top left cluster in Figure~\ref{fig:fv} combines Kinetcis categories `cleaning window', `cleaning floor', and `barbecuing'. Indeed, the actions vocabulary used in the literature is defined by a complex combination of actor's motion and scene appearance, making automatic discovery of well-aligned clusters challenging, and partially explaining the remaining gap between clustering-based methods and fully-supervised pretraining. 

\subsection{Learning long-term temporal dependencies}
\begin{table}[bt]
\caption{Evaluation of the effect of clip length on the Video LA objective with and without IDT prior on the first split of UCF101 and HMDB51 using classification accuracy. Scratch and Supervised baselines are also reported. All models use a 3D ResNet18 backbone, and take frames with resolution of $112 \times 112$ as input. Both self-supervised and fully-supervised variants benefit from longer sequences, but the model trained from scratch is not able to capitalize on more information.}
\label{tab:clip_len}
 \centering
  {
    \begin{tabular}{l|c@{\hspace{1em}}c@{\hspace{1em}}c@{\hspace{1em}}|c@{\hspace{1em}}c@{\hspace{1em}}c@{\hspace{1em}}}
     Method         & \multicolumn{3}{c|}{UCF101}           & \multicolumn{3}{c}{HMDB51}       \\\hline
          & 16-fr & 32-fr & 64-fr & 16-fr & 32-fr & 64-fr \\ \hline
     Scratch
        & 42.4 & 44.9       &  45.3 &  17.1 & 18.0       &  17.4     \\\hline
    Video LA &
        71.4 & 75.0       & 79.4 & 41.7 & 43.1       & 48.9       \\
    Video LA + IDT prior
        & \textbf{72.8} & \textbf{76.3} & \textbf{81.5} & \textbf{44.0} & \textbf{44.7}       & \textbf{49.6}    \\ \hline
    Supervised
        & 84.4 & 87.0  & 91.2 & 56.4 & 63.1 & 67.5      \\ \hline
\end{tabular}
}
\end{table}

Next, we experiment with applying our Video LA objective with IDT prior over longer clips. Recall that this approach attempts to capture the notion of similarity between the videos encoded in the IDT descriptors that are computed over the whole video. The model reported so far, however, only takes 16-frame clips as input, which makes the objective highly ambiguous. In Table~\ref{tab:clip_len} we evaluate networks trained using 32- and 64-frame long clips instead, reporting results on UCF101 and HMDB51.

We observe that, as expected, performance of our approach (`Video LA + IDT' in the table) increases with more temporal information, but the improvement is non-linear, and our model is indeed able to better capture long-term motion cues when trained using longer clips. Similar improvements are observed for the plain Video LA objective, but our approach still shows top performance. Supervised model is also able to capitalize on longer videos, but on UCF101 the improvements are lower than seen by our approach (6.8\% for the supervised model, compared to 8.7\% for ours).
Interestingly, the model trained from scratch does not benefit from longer videos as much as self-supervised or supervised variants. In particular, on HMDB51 its performance improves by about 1-2\% with 32 frames, but actually decreases with 64. We attribute this to the fact that using longer clips lowers the diversity of the training set, which is crucial for optimizing an untrained representation. These results further demonstrate the importance of model pretraining for video understanding.

\subsection{Effect of the number of videos}
\label{sec:vids}
So far, we have reported all the results using 235 000 videos in the training set of Kinetics-400~\cite{carreira2017quo}. We now train the model with our final objective (Video LA with IDT prior) using a varying number of videos to study the effect of the dataset size on the quality of the learned representations. In particular, we subsample the training set to 185 000 and 135 000 examples at random to see whether smaller datasets can be used for representation learning. We also add the videos from the larger Kinetics-600 dataset to see if our method scales to larger video collections. We use the 3D ResNet18 architecture with 16-frames long clips and input resolution of $112 \times 112$ in all experiments, and report results on the first split of UCF101 and HMDB51 in Figure~\ref{fig:data}.
\begin{figure}
\vspace{-15px}
\begin{center}
  \makebox[0.9\textwidth]{\includegraphics[width=0.8\paperwidth]{figures/data1.png}}
  \caption{Varying the number of Kinetics videos when training a 3D ConvNet with the `Video LA with IDT prior' objective. Using more data for unsupervised pretraining results in better representations, as evident form transfer learning results on the first split of UCF101 and HMDB51 (reported using classification accuracy).}
  \label{fig:data}
\end{center}
\vspace{-20px}
\end{figure}

Firstly, we observe that useful representations can be learned with as few 135 000 videos. However, using more data results in improved performance on both datasets. On UCF101 the improvements are mostly linear, but accuracy drops somewhat for the largest training set (370 000 videos). We attribute this to the randomness in training and hypothesize that further improvements can be achieved with more data. On HMDB51 accuracy seems to plateau after  235 000 videos, but improves with 370 000. We will use the model trained on the largest available dataset for comparison to the state-of-the-art in the next section.

\subsection{Comparison to the state-of-the-art}
Finally, we compare our approach (Video LA with IDT prior) to the state-of-the-art unsupervised video representations in Table~\ref{tab:sot}. As noted in Section~\ref{sec:impl}, to fairly compare results achieved by methods with different network architectures, we use the fraction of fully supervised performance as an additional metric, whenever this information is available. To make the table size manageable, we only report approaches that use 3D ConvNets pretrained on Kinetics. These, however, cover all the top performing methods in the literature.
\begin{table}[bt]
\caption{Comparison to the state-of-the-art using accuracy and fraction of the fully-supervised performance on UCF101 and HMDB51, averaged over 3 splits. `Ours': Video LA with IDT prior. DPC uses a non-standard version of 3D ResNet, and does not report fully-supervised performance for it. Our method shows top accuracy among the models using the same network architecture. When normalized for the architecture differences, it outperforms all the approaches.}
\label{tab:sot}
 \centering
  {
    \begin{tabular}{l|c|c|c|c@{\hspace{0.5em}}c@{\hspace{0.5em}}|c@{\hspace{0.5em}}c@{\hspace{0.5em}}}
        Method &    Network &  Frame size & \#Frames  & \multicolumn{2}{c|}{UCF101}            & \multicolumn{2}{c}{HMDB51}        \\\hline
        \multicolumn{4}{c|}{}  & Acc. & \% sup.           & Acc. & \% sup.       \\\hline
     PMAS~\cite{wang2019self} & C3D & $112 \times 112$ & 16
        & 61.2       & 74.3 & 33.4 & -        \\ \hline
    3D-Puzzle~\cite{kim2019self} & 3D ResNet18 & $224 \times 224$ & 16
        & 65.8       & 78.0 & 33.7 & 59.8          \\
    DPC~\cite{han2019video} & 3D ResNet18 & $112 \times 112$ & 40
        & 68.2       & -        & 34.5 & -   \\
    Ours & 3D ResNet18 & $112 \times 112$ & 16
        & 73.0      & 86.5 & 41.6 & 73.8   \\ \hline
    3D-RotNet~\cite{jing2018self} & 3D ResNet18 & $112 \times 112$ & 64
        & 66.0       & 72.1 & 37.1 & 55.5                   \\
    Ours & 3D ResNet18 & $112 \times 112$ & 64
        & \textbf{83.0}       & \textbf{90.7} & \textbf{50.4} & \textbf{75.6}   \\ \hline
    DPC~\cite{han2019video} & 3D ResNet34 & $224 \times 224$ & 40
        & 75.7       & - & 35.7 & -    \\ \hline
    CBT~\cite{sun2019contrastive} & S3D & $112 \times 112$ & 16 & 79.5 & 82.1 & 44.6 & 58.8  
    \\ \hline
    IDT~\cite{wang2013action} & - & Full & All & 85.9 & - & 57.2 & -  
\end{tabular}
}
\vspace{-10px}
\end{table}

Firstly, we observe that our principled approach is indeed a lot more effective that manually designed objectives used in PMAS~\cite{wang2019self}, or 3D-Puzzle~\cite{jing2018self}, confirming the effectiveness of clustering-based training. The improvements are especially large on HMDB, which is, as we have shown previously, can be attributed to the IDT prior helping to better model the temporal information.  Our approach also outperforms DPC~\cite{han2019video}, when the network depth is the same for both methods, even though DPC uses much longer sequences (40 frames with a stride 2, so the effective length is 120). Notably, on HMDB our approach even outperforms a variant of DPC with a deeper network, and bigger frame size by a large margin. When trained with longer temporal sequences, our method also outperforms the deeper variant of DPC on UCF by 7.3\%. On HMDB we are 14.7\% ahead. 

The very recent approach of Sun et al.~\cite{sun2019contrastive} (`CBT' in the table), reports high accuracy on both datasets. However, we show that this is due to the authors of~\cite{sun2019contrastive} using a much deeper network than other methods in the literature. In terms of the fraction of fully-supervised performance, the 16-frame variant of our method outperforms CBT by 4.4\% on UCF and by 15.0\% on HMDB. Moreover, the 64-frame variant also outperforms CBT in raw accuracy on both datasets.

Finally, we report the performance of Fisher vector encoded IDT descriptors (`IDT' in the table, the numbers are taken from~\cite{simonyan2014two}). Please note that these descriptors are computed on the full length of the video, using the original resolution. Despite this, our 64 frame model comes close to the IDT performance on both datasets. Training a deeper variant of this model with a larger input resolution can close the remaining gap.
\section{Conclusions}
\label{sec:concl}
This paper introduced a novel approach for unsupervised video representation learning. Our method transfers the heuristic-based IDT descriptors, that are effective at capturing motion information, to 3D ConvNets via non-parametric clustering, using an unlabeled collection of videos. We quantitatively evaluated the learned representations on UCF101 and HMDB51 action recognition benchmarks, and demonstrated that they outperform prior work. We also qualitatively analyzed the discovered video clusters, showing that they successfully capture video dynamics, in addition to appearance. This analysis highlighted that the clusters do not perfectly match with the human-defined action classes, partially explaining the remaining gap to the fully-supervised performance.

{\footnotesize \smallsec{Acknowledgements:} We thank Piotr Koniusz and Lei Wang for sharing their implementation of Fisher vector encoding. This work was supported in part by the Inria associate team GAYA, and by the Intelligence Advanced Research Projects Activity (IARPA) via Department of Interior/Interior Business Center (DOI/IBC) contract number D17PC00345. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes not withstanding any copyright annotation theron. Disclaimer: The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied of IARPA, DOI/IBC or the U.S. Government.}
\clearpage

\bibliographystyle{splncs04}
\bibliography{egbib}

\clearpage

\appendix

\begin{center}\Large\bfseries Appendix\end{center}
\subfile{supplementary.tex}

\end{document}


Peer review:
Unsupervised Learning of Video Representations via Dense Trajectory Clustering
#### 1. [Summary] In 2-3 sentences, describe the key ideas, experiments, and their significance.
The paper proposes a method which uses IDT descriptor and 3DConvNet to obtain action clusters and learns the unsupervised video representation.

#### 2. [Strengths] What are the strengths of the paper? Clearly explain why these aspects of the paper are valuable.
- Using IDT as prior knowledge
- Effective motion capturing
- Performance
- Extensive related works and ablation study

#### 3. [Weaknesses] What are the weaknesses of the paper? Clearly explain why these aspects of the paper are weak.
- It requires training with other big dataset.
- Do the authors have any evidence of the performance without the usage of any other dataset?

#### 4. [Overall rating] Paper rating
9

#### 5. [Justification of rating] Please explain how the strengths and weaknesses aforementioned were weighed in for the rating. 
The paper has nice analyses and the proposed method outperforms other methods by using IDT descriptors and 3DConvNet.

#### 6. [Detailed comments] Additional comments regarding the paper (e.g. typos or other possible improvements you would like to see for the camera-ready version of the paper, if any.)
- L.318: Can you elaborate with the fine-tuning stage?
- Can you please clarify for the Table 3 if you train your network with Kinetics-400 or 600? Most of the methods (DPC, 3D-Puzzle, PMAS) in the table use Kinetics-400 for self supervised training.
- What are the limitations?
- Do you have any memory usage and time analyses?

Typos:
- L.406: first
- L.507: Kinetics
Rating: 9: Top 15% of accepted papers, strong accept
Confidence: 5: The reviewer is absolutely certain that the evaluation is correct and very familiar with the relevant literature