*Equal contributionfootnote

The ability to understand physical dynamics is essential to learning agents acting in the world. This paper uses Counterfactual World Modeling (CWM), a candidate pure vision foundational model, for physical dynamics understanding. CWM consists of three basic concepts. The first is a simple and powerful temporally-factored masking policy for masked prediction of video data, which encourages the model to learn disentangled representations of scene appearance and dynamics. Second, as a result of the factoring, CWM is capable of generating counterfactual next-frame predictions by manipulating a few patch embeddings to exert meaningful control over scene dynamics. Third, the counterfactual modeling capability enables the design of counterfactual queries to extract vision structures similar to keypoints, optical flows, and segmentations, which are useful for dynamics understanding. Here, we show that zero-shot readouts of these structures extracted by the counterfactual queries attain competitive performance to prior methods on real-world datasets. Finally, we demonstrate that CWM achieves state-of-the-art performance on the challenging Physion benchmark for evaluating physical dynamics understanding.

§ INTRODUCTION

At a glance, humans rapidly estimate physical dynamics in everyday tasks, such as predicting ball trajectories while catching, assessing stability in plate stacking, and gauging vehicle speeds during highway merging. The ability to understand physical dynamics is fundamental to how we interact with the physical world. Building vision algorithms that learn physical dynamics from real-world data remains a critical challenge for learning agents acting in the world, such as robots and autonomous vehicles. Research [Bear et al., 2021] has shown that current vision algorithms are lacking in understanding the physical dynamics of scenarios such as objects colliding, falling, or bouncing.

One class of existing methods for learning physics depends on structured object representations such as object segmentations and particle graphs [Battaglia et al., 2016, Mottaghi et al., 2016, Li et al., 2018, Bates et al., 2019, Tacchetti et al., 2018, Sanchez-Gonzalez et al., 2018, Mrowca et al., 2018, Ajay et al., 2019, Smith et al., 2019, Ye et al., 2019, Qi et al., 2020]. While these methods have been shown to accurately predict physical scene dynamics, they depend on simulated or manually annotated datasets. The scalability of these approaches to large-scale, real-world data is limited due to the impracticality of acquiring manual annotations.  While unsupervised methods aimed at extracting intermediates for these structured representations have been proposed [Locatello et al., 2020, Chen et al., 2022, Karazija et al., 2022, Sitzmann et al., 2019, Yu et al., 2021, Du et al., 2020, Yu et al., 2021, Chen et al., 2022], these methods have had limited success generalizing robustly to complex real-world scenarios.

A contrasting class of approaches avoids the use of structured intermediates by learning to predict raw pixels of future video frames [Agrawal et al., 2016, Finn and Levine, 2017, Babaeizadeh et al., 2021, Hafner et al., 2019, Fragkiadaki et al., 2015, Hafner et al., 2019, Piloto et al., 2022, Wu et al., 2022]. These approaches are directly applicable to any video input, eliminating the need for annotations. However, learning to predict future frame pixels poses many challenges due to the high-dimensionality of image pixels and the stochasticity of real-world physical dynamics, and the joint learning of scene parsing and prediction can make it more difficult to learn useful scene representations. Previous work [Bear et al., 2021] indicates that methods with unstructured video prediction tend to underperform compared to methods with structured object-centric representations, and substantially lag behind particle-based methods that have direct access to 3D physical state information.

Beyond task-specific methods for physical dynamics prediction, recent years have seen substantial progress in learning general task-agnostic visual representations [Caron et al., 2021, He et al., 2022, Tong et al., 2022], following the paradigm shift to foundational models in Natural Language Processing (NLP) [Chowdhery et al., 2022, Hoffmann et al., 2022, Touvron et al., 2023]. These models leverage large quantities of internet data to learn visual representations that transfer well to downstream vision tasks. Methods including but not limited to DINO [Caron et al., 2021, Oquab et al., 2023], masked autoencoder (MAE) [He et al., 2022], and VideoMAE [Feichtenhofer et al., 2022, Tong et al., 2022, Wang et al., 2023] are promising early efforts towards pure vision foundation models. Although they focus on core traditional vision tasks such as image classification, action recognition, and semantic segmentation, their learned representations are potentially useful for dynamics understanding.

Besides learning useful representations, it is promising that vision structures such as segmentations could potentially emerge from this class of vision foundation models [Caron et al., 2021, Oquab et al., 2023]. These intermediate structures are useful for dynamics understanding [Mottaghi et al., 2016, Qi et al., 2020, Ye et al., 2019, Smith et al., 2019]. However, these models are mostly used in the paradigm of transfer learning or finetuning. They cannot be prompted like a Large Language Model (LLM) to extract meaningful structures without model re-training.

One potential workaround for this shortcoming is Vision-Language models [Awadalla et al., 2023, Shen et al., 2023, Du et al., 2022, Chen et al., 2023], which utilize the prompting capabilities of an LLM to answer questions about visual embeddings. However, low-level descriptions of physical dynamics are almost never present in internet-scale vision-text corpora. Thus we cannot expect such models to contain dynamics understanding capabilities.

It would be desirable to have a pure vision foundation model that can be pre-trained on real-world video data and queried visually to extract structures useful for dynamics understanding. In this paper, we use a simple, effective, and scalable framework, called Counterfactual World Modeling (CWM) [Bear et al., 2023]. Figure <ref> illustrates the three core concepts of the CWM framework. First, we pre-train the model with a temporal-factored masking policy for structured masked prediction of video data . Given an input frame pair, we train a masked autoencoder to predict the second frame given only a few patches of it, along with a fully visible first frame [Bear et al., 2023]. This design is motivated by the observation that the transition between a frame pair can often be explained by a few latent causes (e.g. the motion of an object or a camera pan). As a result, we can simply modify those patches to exert meaningful control on scene dynamics. Second, by virtue of these few embeddings representing latent causes, CWM is capable of generating counterfactual next-frame predictions by taking actions, specified as changes to the corresponding patches. Third, we design unified counterfactual queries for extracting useful vision structures similar to keypoints, optical flows, and segmentations, which are useful for dynamics understanding. We show that the zero-shot readouts of vision structures extracted by CWM attain competitive performance on real-world datasets. Further, we demonstrate that CWM achieves state-of-the-art performance on the challenging Physion benchmark for physical scene understanding.

A small number of visual patches exert meaningful control of scene dynamics. Each triplet shows the input image (left), an action constructed from the input image (middle), and the counterfactual prediction of the model (right). Each action is constructed by copying 2-3 patches from the input image. A red patch in the action is copied from the input image into the same location as its source. This prompts the predictor to simulate the appearance of holding an object fixed.  A green patch is copied from the input image, but into a different location at an offset from the source location. This simulates the appearance of an apparent object motion.

§ RELATED WORKS

Structured dynamics prediction
Researchers in the past decade have made progress in physical dynamics prediction using structured object representations such as segmentations and particle graphs as inputs [Battaglia et al., 2016, Mottaghi et al., 2016, Li et al., 2018, Bates et al., 2019, Tacchetti et al., 2018, Sanchez-Gonzalez et al., 2018, Mrowca et al., 2018, Ajay et al., 2019, Smith et al., 2019, Ye et al., 2019, Qi et al., 2020]. The scalability of these approaches on real-world unlabelled data remains limited.

Video prediction
One class of approaches [Agrawal et al., 2016, Finn and Levine, 2017, Babaeizadeh et al., 2021, Hafner et al., 2019, Fragkiadaki et al., 2015, Hafner et al., 2019, Piloto et al., 2022, Wu et al., 2022] learns general physics understanding through future frame pixel prediction on large unstructured videos of real-world scenes [Tung et al., 2023]. Recent video diffusion models [Voleti et al., 2022, Lu et al., 2023, Höppe et al., 2022, Chen et al., 2023] and transformer-based prediction models [Gupta et al., 2022, Yu et al., 2023] have made progress towards more realistic pixel prediction of future video frames.

Self-supervised visual representation learningfrom large-scale unlabeled image or video data has drawn increasing attention in recent years. These methods learn to generate visual features that transfer well to downstream vision tasks. One school of works leverages different pretext tasks for pre-training [Doersch et al., 2015, Noroozi and Favaro, 2016, Wang and Gupta, 2015, Zhang et al., 2016, Pathak et al., 2017, Gidaris et al., 2018]. The recent family of contrastive learning methods models image similarity and dissimilarity between augmented
views of an image [Wu et al., 2018, Oord et al., 2018, He et al., 2020, Chen et al., 2020] and different clips of a video [Qian et al., 2021, Zhuang et al., 2020, Dave et al., 2022].

Mask visual modelingapproaches learn effective visual representations via masking and reconstruction of visual tokens. iGPT [Chen et al., 2020] and ViT [Dosovitskiy et al., 2020] pioneer this direction by training transformers on pixel or patch tokens and exploring masked prediction with patches. MAE [He et al., 2022] introduces autoencoding with an asymmetric encoder-decoder architecture and empirically shows that a high masking ratio is crucial for image tasks. VideoMAE [Tong et al., 2022, Feichtenhofer et al., 2022] extends to the video domains and shows that an even higher masking ratio leads to strong performance for activity recognition tasks.

§ METHOD

In this section we discuss in generality the three core concepts of CWM (as originally introduced in [Bear et al., 2023]): (a) pre-training with temporal-factored masked prediction, (b) counterfactual predictions via sampling actions, and (c) counterfactual queries for extracting structures. We will discuss the application of CWM to physical dynamics understanding in Section <ref>.

§.§ Temporal-factored masked prediction

Masked prediction Following MAE [He et al., 2022] and VideoMAE [Tong et al., 2022, Feichtenhofer et al., 2022], we train an encoder-decoder architecture to reconstruct masked observations of video data. Given an input frame pair $x_1, x_2 \!\in\! \mathbb{R}^{3 \times H \times W}$, we first divide them into non-overlapping spatiotemporal square patches. Then a subset of the patches is masked, and only the remaining visible patches are passed as inputs into the transformer encoder. Finally, the embeded tokens from the encoder and learnable mask tokens, with added positional embedding on all the tokens, are passed as inputs into a shallow decoder to reconstruct the masked patches. The model is trained with the mean squared error (MSE) loss between the reconstructed patches and the original masked patches.

Masking policy Unlike VideoMAE [Tong et al., 2022, Feichtenhofer et al., 2022], which randomly samples “tubes” or “cubes” of spatiotemporal patches to be masked, we use a temporal-factored masking policy for video data. This is motivated by the observation that the next frame of a video can be predicted well by simply copying large chunks of the previous frame to nearby locations, especially on short timescales [Bear et al., 2023]. In other words, information about scene dynamics has a low-dimensional structure even if per-frame appearance does not. This asymmetry between dynamics and appearance can be harnessed with a temporal-factored masking policy [Bear et al., 2023]. Specifically, given an input frame pair $x_1, x_2 \in \mathbb{R}^{3 \times H \times W}$, we train a predictor $\Psi$:

\begin{equation}
\Psi(x_1, x_2^m) = \tilde{x}_2
\end{equation}

which takes in a fully visible first frame $x_1$ and a masked second frame $x_2^m \in \mathbb{R}^{3 \times H \times W}$ with only a random subset of patches visible. The predictor $\Psi$ predicts the masked patches of the second frame, and minimizes the mean squared error (MSE) between reconstructed patches $\tilde{x}_2$ and the masked patches in the original $x_2$.

When the masking fraction $p \in [0,1]$ of $x_2$ is high, the predictor $\Psi$ must complete the second frame given only a few patches of it, along with the fully visible first frame; the only way it can do this is by detecting how objects are moving from the small set of second-frame patches, then applying these transformations to the full objects in the first frame [Bear et al., 2023]. Thus the predictor trained with this masking policy learns implicitly to use the embeddings of a few patches to represent the latent causes underlying scene dynamics.

§.§ Counterfactual prediction via action

By virtue of patch embeddings representing latent causes, we can modify the content of these patches to steer the next-frame predictions output by the predictor $\Psi$, as illustrated by Figure <ref>. Formally, given a static input image $x \!\in \!\mathbb{R}^{3 \times H \times W}$ during inference, we define action as a sparse frame with a few patches that control the dynamics of the scene, denoted by $a \! \in \! \mathbb{R}^{3 \times H \times W}$. The action will be passed as an input to the predictor along with the input image to steer the output of the predictor:

\begin{equation}
\Psi(x, a) = \tilde{x}
\end{equation}

The alternative prediction $\tilde{x}$ given an action is a counterfactual prediction [Bear et al., 2023]. Next, we define an operator for sampling actions $a$ that meaningfully controls the dynamics of the scenes.

Sampling operator
Algorithm <ref> describes the operator for sampling actions. Given an input RGB image $x$, the sampling operator constructs an action $a \!\in\! \mathbb{R}^{3 \times H \times W}$, which has $n$ visible patches. Each visible patch is copied from a source location in the input image, with each source location randomly sampled from a spatial probability distribution $p \in \mathbb{R}^{H \times W}$. In addition, each visible patch can be optionally copied to a new patch location with a random offset within radius $r$ from the source location. This will create a motion counterfactual that simulates the appearance of moving the object associated with the patch.

§.§ Counterfactual queries for structure extraction

With a predictor and an operator for sampling actions, we can compose these two ingredients into programs for extracting vision structures, including keypoints, optical flows, and segmentation.

Keypoints are local features of a scene that capture more information than other features [Minderer et al., 2019, Mian et al., 2008, Bear et al., 2023]. In our approach, keypoints are naturally defined as those tokens that, when made visible to the predictor $\Psi$, yield lowest reconstruction error on the rest of the scene [Bear et al., 2023]. Keypoints turn out to be good loci for exerting counterfactual control. Intuitively, this is because they are the few visual tokens most able to reduce uncertainty and yield a concrete prediction about many other tokens [Bear et al., 2023]. Figure <ref> describes an iterative procedure for constructing keypoints. Given a frame pair $x_1, x_2$, we start from a null action with no visible patches and iteratively add visual patches one-by-one greedily to reduce the reconstruction error of $x_2$ given $x_1$ and the action as inputs. At each iteration, we choose the location with maximum reconstruction error as the keypoint and add its corresponding patch into action. These keypoint patches are most able to reduce uncertainty of the scenes.

Optical flow

Flow-like structure can be queried by adding a small “tracer” to the first frame at position $(i,j)$ and localizing the response of the perturbation in the counterfactual prediction of the next frame [Bear et al., 2023]. The procedure is described in Figure <ref>. Given a frame pair $x_1, x_2$ and a pixel location $(i,j)$, we add a small perturbation to the pixel and construct an action $a$ with randomly selected patches from $x_2$ to specify the motion between frame pair. In the predicted next frame $\tilde{x}$ output by $\Psi$, the perturbation is propagated to the corresponding location according to the scene motion. Taking the difference between $\tilde{x}$ and $x_2$ gives the perturbation responses over the entire image, and the location with the highest response is set as the corresponding pixel location $(i',j')$ in $x_2$. Flow is calculated as the spatial displacement between $(i,j)$ and $(i',j')$.

Segmentation Our querying procedure for segmentation is inspired by the notion of Spelke object in infant object recognition: babies typically treat things that move together as a single object [Spelke, 1990]. The CWM model segments objects by sampling counterfactual motion at a pixel location, predicting the next frame, and grouping together parts of the image that move similarly to the counterfactual motion.

Figure <ref> describes an iterative procedure for generating motion counterfactual and extracting segments associated with a pixel location $(i, j)$. Given a single input image $x$, we instantiate an action by creating a new frame that is mostly blank, but in which the content of the patch at location $(i, j)$ of the input image is copied to a new location $(i\!+\!\epsilon_1, j\!+\!\epsilon_2)$, where $\epsilon_1,\epsilon_2$ are location offsets sampled within a radius $r\!>\!0$. With a pre-trained predictor, moving a single patch causes the whole object to move in the predicted frame [Bear et al., 2023]. We extract the flow between the input and predicted frame, and threshold it to obtain a segment. To further refine the segments, we repeat this procedure by iteratively adding more patches within the segment region into the action, where the number of iterations is set as 3.

To automatically discover multiple objects in a single image, we choose actions at pixel locations based on a sampling probability distribution $p$, which has high probability at pixel locations belonging to Spelke objects and low otherwise. Once a segment is discovered, we mask out the probability distribution values using the segments and repeat the process to discover the next object. We discuss more details about computing the sampling distribution in the supplementary materials.

§.§ Implementation details

CWM uses the standard ViT-B and ViT-L architectures with a patch size of 8, which allows structure extraction at a higher resolution. We pre-train CWM on the Kinetics-400 dataset [Kay et al., 2017], without requiring any specialized sparse operations or temporal downsampling. While the discussion about CWM thus far assumes a frame pair as input, it can be easily generalized to take in multiple frames as input. Our default setting is sampling 3 video frames 150ms apart on the Kinetics-400 dataset. It takes approximately 6 days to train 3200 epochs on a TPU v4-256 pod.

§ EXPERIMENTS

In this section, we first evaluate CWM's ability to  extract zero-shot visual structures such as optical flow and Spelke object segments on real-world datasets (Section <ref>). Second, we investigate whether these structures help improve performance on downstream physical dynamics understanding tasks (Section <ref>). Last, we perform ablations studies on CWM design with the ViT-B architecture on Kinetics-400 [Kay et al., 2017] dataset (Section <ref>).

§.§ Visual structure extraction

Optical flow We evaluate the quality of optical flows using the SPRING benchmark [Mehl et al., 2023], which is a simulated movie dataset with high-resolution videos and ground-truth optical flows. We compare CWM to previous supervised flow estimation methods including RAFT [Teed and Deng, 2020], PWCNet [Sun et al., 2018] and SpyNet [Ranjan and Black, 2017]. We report the average endpoint error (epe) metric [Otte and Nagel, 1994] in Table <ref>. Although CWM is not trained with the specific objective of learning optical flow, the extracted flow-like structures are meaningful, as illustrated in Figure <ref>. While CWM, trained in an unsupervised manner is inferior to RAFT and PWCNet trained with ground-truth supervision, it still achieves comparable performance to the prior supervised method SpyNet. We include qualitative comparisons to these methods and additional implementation details in the supplementary.

Spelke object segmentation We extract zero-shot segmentations on images from COCO  [Lin et al., 2014] using counterfactual queries.  Although Spelke object are segment-like structures, the definition of Spelke objects is not exactly aligned with the definition of instance segmentations in the COCO datasets, therefore we are not optimizing our querying procedure for the COCO evaluation metrics. We follow the same procedures in CutLER [Wang et al., 2023] to learn a detector using the popular Cascade Mask R-CNN [Cai and Vasconcelos, 2018] on these coarse masks in a self-supervised manner while being robust to objects missed by the query. We compare CWM with TokenCut [Wang et al., 2023], FreeSOLO [Wang et al., 2022] and CutLER [Wang et al., 2023]. These methods extract segment-like structures from pre-trained models and learn a detector using pseudo ground-truth masks as self-supervision. We train CutLER on COCO training images for a fair comparison.

Table <ref> shows the quantitative performance of CWM and the baseline methods in unsupervised class-agnostic object detection and segmentation on COCO [Lin et al., 2014] validation set. CWM outperforms prior methods TokenCut [Wang et al., 2023], and FreeSOLO [Wang et al., 2022] significantly and attains similar performance to the current state-of-the-art, CutLER [Wang et al., 2023].

§.§ Physical Dynamics Understanding

Having demonstrated CWM can use patch embeddings to meaingingfully control scene dynamics and query different vision structures, we study the usefulness of these embeddings and the extracted structures for dynamics understanding. We adopt a similar evaluation procedures as the Physion [Bear et al., 2021] benchmark, which assesses physical scene understanding of pre-trained models by how well those models predict whether two objects will collide in the future given a context video.

Physion benchmark consists of realistic simulations of diverse physical scenarios where objects are manipulated in a variety of configurations to test different types of physical reasoning such as stability, rolling motion, containment, object linkage, etc. We use the latest version of Physion [Bear et al., 2021], referred to as Physion v1.5[ https://physion-benchmark.github.io], which has improved rendering quality and more physically plausible simulations. In the ideal scenario, we would evaluate CWM on a real-world physics-understanding benchmark, but such benchmarks are not available. Despite being a synthetic dataset, Physion serves as a strong out-of-distribution generalization test for vision foundation models trained on real world data. Physion is also more challenging as it contains diverse physical phenomena, object dynamics and realistic 3D simulations. This makes it a preferable choice when compared to other benchmarks such as ShapeStacks [Groth et al., 2018] and IntPhys [Riochet et al., 2021] which contain very limited object dynamics, or Phyre [Bakhtin et al., 2019] which only operates in 2D environments.

The benchmark consists of two tasks: (a) Object contact prediction (OCP), which tests the model's ability to predict whether two objects will contact at some point in the future given a context video, and (b) Object contact detection (OCD) which tests the model's ability to detect if two objects have already come into contact in the observed video. For both tasks, the two objects of interest are rendered with red and yellow texture to cue the model. Figure <ref> shows  example stimuli for the two tasks.

Evaluation protocol
We follow the three-step evaluation protocol of the Physion benchmark [Bear et al., 2021]. First, we extract features from the last layer of a frozen pre-trained encoder on a training set of 5608 videos for OCP and OCD tasks, respectively. For image-based methods, features are extracted from 4 frames that are 150 ms apart. For video-based methods, the input frames are fed to the model at the specific frame rate used during their training. Second, the extracted features are used to train a logistic regression model to predict the contact label for the given video stimulus. We search for the optimal regularization strength by validating over 5 training-set folds. Lastly, the trained classifier is evaluated on a test set of 1035 videos, sampled equally across different physical scenarios.

Baseline methods
We compare CWM with four classes of baseline approaches: (a) video prediction models including MCVD [Voleti et al., 2022], R3M [Nair et al., 2022], FitVid [Babaeizadeh et al., 2021], and TECO [Yan et al., 2023], (b) self-supervised representation learning methods on images including DINO [Caron et al., 2021], DINOv2 [Oquab et al., 2023], and MAE [He et al., 2022], (c) self-supervised representation learning methods on videos including VideoMAE [Tong et al., 2022] and VideoMAEv2 [Wang et al., 2023], and lastly (d) vision-language model like GPT4-V [OpenAI, 2023].

In Table <ref> we report results on the two Physion tasks for both CWM with ViT-B and ViT-L architectures and other baseline methods discussed above. We evaluate CWM in two settings: CWM-feat only uses the embeddings from the last layer of the pre-trained encoder as the input to the linear classifier, and CWM uses both features and extracted vision structures. We find that even without extracted structures, CWM-feat with ViT-B achieves state-of-the-art results on both OCP and OCD metrics. It is interesting to note that CWM outperforms baseline methods such as DINOv2 ViT-g and MAE ViT-H which have 13 and 7 times more parameters. This shows that CWM is a more effective and efficient learner of physical scene dynamics. We also observe that CWM, when scaled up to the ViT-L architecture, achieves superior performance on the OCP task. With the extracted structures, the OCP improves from 73.6% to 75.9% in ViT-B architecture and 74.6% to 76.1% in ViT-L architecture. This shows that the extracted vision structures are useful for dynamics understanding.

We find that video prediction models perform poorly especially on the harder OCP task. Self-supervised methods on the other hand, are better in terms of both OCP and OCD metrics, but they saturate around 72% and 87% respectively with the ViT-B architecture.

We also evaluate GPT4-V [OpenAI, 2023] on Physion v1.5 tasks by providing it with a single composite image with a sequence of four video frames sampled at a gap of 150ms. The model is prompted with questions similar to those in Figure <ref> (see supplementary for more details about the specific prompts used). We find GPT4-V scores nearly at chance on OCP and slightly above chance on OCD, which highlights a considerable limitation in the ability of large-scale VLMs to understand physical scene dynamics.

§.§ Ablation studies

We ablate the CWM design with the default backbone of ViT-B. Each ablated model is trained for 800 epochs on the Kinetics-400 dataset. Although optimal performance is not reached at 800 epochs, reasonable results are achieved, allowing fair and efficient ablations.

Mask ratio Table <ref> shows the influence of the target frame mask ratio. We observe that a high ratio during model training achieves good performance on both the OCP and OCD tasks. The optimal mask ratio for CWM is higher than the mask ratio used in MAE [He et al., 2022] which is 75%. This trend aligns with our aforementioned hypothesis that the dynamics between frame pairs at a short timescale has a low-dimensional causal structure, which can be concentrated into a small number of tokens.

Context length We compare the performance of CWM with different numbers of context frames in Table <ref>. CWM with 2 context frames during pre-training performs better as compared to using 1 context frame. However, including 4 context frames degrades the performance.

Patch size We find that the choice of patch size has relatively small influence on the OCP and OCD accuracy (See Table <ref>). We choose the default patch size to be 8 since it enables CWM to output higher resolution segmentation and optical flow maps when prompted.

Training schedule A longer training schedule (3200 epochs) has a relatively small influence on the OCP accuracy, but it has noticeable improvement on the OCD accuracy. We report these results in Table <ref>.

Vision structures Table <ref> studies the importance of different visual structures in the performance of OCP and OCD using ViT-B architecture. We find that incorporating vision structures from CWM improves performance. First, adding patch features at keypoint locations improves the OCP scores from 73.6% to 74.4%. Second, enriching these patch features with optical flow patches computed at keypoint locations further improve the OCP scores to 75.5%. Finally, including spelke object segments achieves a score of 75.9%, demonstrating the cumulative impact of successive additions.

§ DISCUSSION AND CONCLUSION

In this work, we show how Counterfactual World Modeling, an approach for building pure vision foundation models, can be useful for dynamics understanding. CWM utilizes a temporal-factored masked prediction objective for pre-training, which encourages the model to learn disentangled visual and motion representations over a short video clip. CWM supports counterfactual prediction, which enables a spectrum of queries for extracting useful vision structures such as keypoints, optical flows, and Spelke object segments from the model in a zero-shot manner. This serves as a general framework for pre-training on internet-scale video datasets and visually querying the pre-trained model to extract structures useful for dynamics understanding.

Currently the model is only capable of predicting future frames at short timescale around 450 ms. While this is enough for extracting useful vision structures, future versions could extend to longer time scales in order to solve meaningful predictive control tasks.

In future work, the CWM framework could be extended to query 2.5D structures such as depth and lifting multiview information to 3D structures. Additionally, automatic query discovery systems could identify useful structures without human design. CWM could also serve as a powerful tokenization scheme for modeling longer-range dynamics prediction via both the extracted structures and embeddings that represents latent causes of the scene dynamics. The capability of long-range prediction coupled with the counterfactual querying mechanism could be a promising tool for applications that involve model-predictive control and planning such as robotics and autonomous driving.

Acknowledgements This work was supported by the following awards: To D.L.K.Y.: Simons Foundation grant 543061, National Science Foundation CAREER grant 1844724, Office of Naval Research grant S5122, ONR MURI 00010802 and ONR MURI S5847. We also thank the Google TPU
Research Cloud team for computing support.

[Agrawal et al., 2016]
Pulkit Agrawal, Ashvin V Nair, Pieter Abbeel, Jitendra Malik, and Sergey Levine.
Learning to poke by poking: Experiential learning of intuitive physics.
Advances in neural information processing systems, 29, 2016.

[Ajay et al., 2019]
Anurag Ajay, Maria Bauza, Jiajun Wu, Nima Fazeli, Joshua B Tenenbaum, Alberto Rodriguez, and Leslie P Kaelbling.
Combining physical simulators and object-based networks for control.
In 2019 International Conference on Robotics and Automation (ICRA), pages 3217–3223. IEEE, 2019.

[Awadalla et al., 2023]
Anas Awadalla, Irena Gao, Josh Gardner, Jack Hessel, Yusuf Hanafy, Wanrong Zhu, Kalyani Marathe, Yonatan Bitton, Samir Gadre, Shiori Sagawa, Jenia Jitsev, Simon Kornblith, Pang Wei Koh, Gabriel Ilharco, Mitchell Wortsman, and Ludwig Schmidt.
Openflamingo: An open-source framework for training large autoregressive vision-language models.
arXiv preprint arXiv:2308.01390, 2023.

[Babaeizadeh et al., 2021]
Mohammad Babaeizadeh, Mohammad Taghi Saffar, Suraj Nair, Sergey Levine, Chelsea Finn, and Dumitru Erhan.
Fitvid: Overfitting in pixel-level video prediction.
arXiv preprint arXiv:2106.13195, 2021.

[Bakhtin et al., 2019]
Anton Bakhtin, Laurens van der Maaten, Justin Johnson, Laura Gustafson, and Ross Girshick.
Phyre: A new benchmark for physical reasoning.
Advances in Neural Information Processing Systems, 32, 2019.

[Bao et al., 2021]
Hangbo Bao, Li Dong, Songhao Piao, and Furu Wei.
Beit: Bert pre-training of image transformers.
arXiv preprint arXiv:2106.08254, 2021.

[Bates et al., 2019]
Christopher J Bates, Ilker Yildirim, Joshua B Tenenbaum, and Peter Battaglia.
Modeling human intuitions about liquid flow with particle-based simulation.
PLoS computational biology, 150 (7):0 e1007210, 2019.

[Battaglia et al., 2016]
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al.
Interaction networks for learning about objects, relations and physics.
Advances in neural information processing systems, 29, 2016.

[Bear et al., 2021]
Daniel M Bear, Elias Wang, Damian Mrowca, Felix J Binder, Hsiao-Yu Fish Tung, RT Pramod, Cameron Holdaway, Sirui Tao, Kevin Smith, Fan-Yun Sun, et al.
Physion: Evaluating physical prediction from vision in humans and machines.
arXiv preprint arXiv:2106.08261, 2021.

[Bear et al., 2023]
Daniel M Bear, Kevin Feigelis, Honglin Chen, Wanhee Lee, Rahul Venkatesh, Klemen Kotar, Alex Durango, and Daniel LK Yamins.
Unifying (machine) vision via counterfactual world modeling.
arXiv preprint arXiv:2306.01828, 2023.

[Cai and Vasconcelos, 2018]
Zhaowei Cai and Nuno Vasconcelos.
Cascade r-cnn: Delving into high quality object detection.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 6154–6162, 2018.

[Caron et al., 2021]
Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.
Emerging properties in self-supervised vision transformers.
In Proceedings of the International Conference on Computer Vision (ICCV), 2021.

[Chen et al., 2022]
Honglin Chen, Wanhee Lee, Hong-Xing Yu, Rahul Mysore Venkatesh, Joshua B Tenenbaum, Daniel Bear, Jiajun Wu, and Daniel LK Yamins.
Unsupervised 3d scene representation learning via movable object inference.

[Chen et al., 2022]
Honglin Chen, Rahul Venkatesh, Yoni Friedman, Jiajun Wu, Joshua B Tenenbaum, Daniel LK Yamins, and Daniel M Bear.
Unsupervised segmentation in real-world images via spelke object inference.
In European Conference on Computer Vision, pages 719–735. Springer, 2022b.

[Chen et al., 2023]
Jun Chen, Deyao Zhu, Xiaoqian Shen, Xiang Li, Zechu Liu, Pengchuan Zhang, Raghuraman Krishnamoorthi, Vikas Chandra, Yunyang Xiong, and Mohamed Elhoseiny.
Minigpt-v2: large language model as a unified interface for vision-language multi-task learning.
arXiv preprint arXiv:2310.09478, 2023a.

[Chen et al., 2020]
Mark Chen, Alec Radford, Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and Ilya Sutskever.
Generative pretraining from pixels.
In International conference on machine learning, pages 1691–1703. PMLR, 2020a.

[Chen et al., 2020]
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.
A simple framework for contrastive learning of visual representations.
In International conference on machine learning, pages 1597–1607. PMLR, 2020b.

[Chen et al., 2023]
Xinyuan Chen, Yaohui Wang, Lingjun Zhang, Shaobin Zhuang, Xin Ma, Jiashuo Yu, Yali Wang, Dahua Lin, Yu Qiao, and Ziwei Liu.
Seine: Short-to-long video diffusion model for generative transition and prediction.
arXiv preprint arXiv:2310.20700, 2023b.

[Chowdhery et al., 2022]
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al.
Palm: Scaling language modeling with pathways.
arXiv preprint arXiv:2204.02311, 2022.

[Dave et al., 2022]
Ishan Dave, Rohit Gupta, Mamshad Nayeem Rizve, and Mubarak Shah.
Tclr: Temporal contrastive learning for video representation.
Computer Vision and Image Understanding, 219:0 103406, 2022.

[Doersch et al., 2015]
Carl Doersch, Abhinav Gupta, and Alexei A Efros.
Unsupervised visual representation learning by context prediction.
In Proceedings of the IEEE international conference on computer vision, pages 1422–1430, 2015.

[Dosovitskiy et al., 2020]
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.
An image is worth 16x16 words: Transformers for image recognition at scale.
arXiv preprint arXiv:2010.11929, 2020.

[Du et al., 2020]
Yilun Du, Kevin Smith, Tomer Ulman, Joshua Tenenbaum, and Jiajun Wu.
Unsupervised discovery of 3d physical objects from video.
arXiv preprint arXiv:2007.12348, 2020.

[Du et al., 2022]
Zhengxiao Du, Yujie Qian, Xiao Liu, Ming Ding, Jiezhong Qiu, Zhilin Yang, and Jie Tang.
Glm: General language model pretraining with autoregressive blank infilling.
In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 320–335, 2022.

[Ebert et al., 2021]
Frederik Ebert, Yanlai Yang, Karl Schmeckpeper, Bernadette Bucher, Georgios Georgakis, Kostas Daniilidis, Chelsea Finn, and Sergey Levine.
Bridge data: Boosting generalization of robotic skills with cross-domain datasets.
arXiv preprint arXiv:2109.13396, 2021.

[26]
elenium Contributors.
Selenium: Browser automation framework.

[Feichtenhofer et al., 2022]
Christoph Feichtenhofer, Yanghao Li, Kaiming He, et al.
Masked autoencoders as spatiotemporal learners.
Advances in neural information processing systems, 35:0 35946–35958, 2022.

[Finn and Levine, 2017]
Chelsea Finn and Sergey Levine.
Deep visual foresight for planning robot motion.
In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 2786–2793. IEEE, 2017.

[Fragkiadaki et al., 2015]
Katerina Fragkiadaki, Pulkit Agrawal, Sergey Levine, and Jitendra Malik.
Learning visual predictive models of physics for playing billiards.
arXiv preprint arXiv:1511.07404, 2015.

[Gan et al., 2020]
Chuang Gan, Jeremy Schwartz, Seth Alter, Damian Mrowca, Martin Schrimpf, James Traer, Julian De Freitas, Jonas Kubilius, Abhishek Bhandwaldar, Nick Haber, et al.
Threedworld: A platform for interactive multi-modal physical simulation.
arXiv preprint arXiv:2007.04954, 2020.

[Geiger et al., 2013]
Andreas Geiger, Philip Lenz, Christoph Stiller, and Raquel Urtasun.
Vision meets robotics: The kitti dataset.
The International Journal of Robotics Research, 320 (11):0 1231–1237, 2013.

[Gidaris et al., 2018]
Spyros Gidaris, Praveer Singh, and Nikos Komodakis.
Unsupervised representation learning by predicting image rotations.
arXiv preprint arXiv:1803.07728, 2018.

[Goyal et al., 2017]
Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noordhuis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Yangqing Jia, and Kaiming He.
Accurate, large minibatch sgd: Training imagenet in 1 hour.
arXiv preprint arXiv:1706.02677, 2017.

[Groth et al., 2018]
Oliver Groth, Fabian B Fuchs, Ingmar Posner, and Andrea Vedaldi.
Shapestacks: Learning vision-based physical intuition for generalised object stacking.
In Proceedings of the european conference on computer vision (eccv), pages 702–717, 2018.

[Gupta et al., 2022]
Agrim Gupta, Stephen Tian, Yunzhi Zhang, Jiajun Wu, Roberto Martín-Martín, and Li Fei-Fei.
Maskvit: Masked visual pre-training for video prediction.
arXiv preprint arXiv:2206.11894, 2022.

[Hafner et al., 2019]
Danijar Hafner, Timothy Lillicrap, Jimmy Ba, and Mohammad Norouzi.
Dream to control: Learning behaviors by latent imagination.
arXiv preprint arXiv:1912.01603, 2019a.

[Hafner et al., 2019]
Danijar Hafner, Timothy Lillicrap, Ian Fischer, Ruben Villegas, David Ha, Honglak Lee, and James Davidson.
Learning latent dynamics for planning from pixels.
In International conference on machine learning, pages 2555–2565. PMLR, 2019b.

[He et al., 2020]
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.
Momentum contrast for unsupervised visual representation learning.
In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729–9738, 2020.

[He et al., 2022]
Kaiming He, Xinlei Chen, Saining Xie, Yanghao Li, Piotr Dollár, and Ross Girshick.
Masked autoencoders are scalable vision learners.
In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 16000–16009, 2022.

[Hoffmann et al., 2022]
Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al.
Training compute-optimal large language models.
arXiv preprint arXiv:2203.15556, 2022.

[Höppe et al., 2022]
Tobias Höppe, Arash Mehrjou, Stefan Bauer, Didrik Nielsen, and Andrea Dittadi.
Diffusion models for video prediction and infilling.
arXiv preprint arXiv:2206.07696, 2022.

[Karazija et al., 2022]
Laurynas Karazija, Subhabrata Choudhury, Iro Laina, Christian Rupprecht, and Andrea Vedaldi.
Unsupervised multi-object segmentation by predicting probable motion patterns.
Advances in Neural Information Processing Systems, 35:0 2128–2141, 2022.

[Kay et al., 2017]
Will Kay, Joao Carreira, Karen Simonyan, Brian Zhang, Chloe Hillier, Sudheendra Vijayanarasimhan, Fabio Viola, Tim Green, Trevor Back, Paul Natsev, et al.
The kinetics human action video dataset.
arXiv preprint arXiv:1705.06950, 2017.

[Li et al., 2018]
Yunzhu Li, Jiajun Wu, Russ Tedrake, Joshua B Tenenbaum, and Antonio Torralba.
Learning particle dynamics for manipulating rigid bodies, deformable objects, and fluids.
arXiv preprint arXiv:1810.01566, 2018.

[Lin et al., 2014]
Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.
Microsoft coco: Common objects in context.
In Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13, pages 740–755. Springer, 2014.

[Locatello et al., 2020]
Francesco Locatello, Dirk Weissenborn, Thomas Unterthiner, Aravindh Mahendran, Georg Heigold, Jakob Uszkoreit, Alexey Dosovitskiy, and Thomas Kipf.
Object-centric learning with slot attention.
Advances in Neural Information Processing Systems, 33:0 11525–11538, 2020.

[Loshchilov and Hutter, 2016]
Ilya Loshchilov and Frank Hutter.
Sgdr: Stochastic gradient descent with warm restarts.
arXiv preprint arXiv:1608.03983, 2016.

[Loshchilov and Hutter, 2017]
Ilya Loshchilov and Frank Hutter.
Decoupled weight decay regularization.
arXiv preprint arXiv:1711.05101, 2017.

[Lu et al., 2023]
Haoyu Lu, Guoxing Yang, Nanyi Fei, Yuqi Huo, Zhiwu Lu, Ping Luo, and Mingyu Ding.
Vdt: An empirical study on video diffusion with transformers.
arXiv preprint arXiv:2305.13311, 2023.

[Mehl et al., 2023]
Lukas Mehl, Jenny Schmalfuss, Azin Jahedi, Yaroslava Nalivayko, and Andrés Bruhn.
Spring: A high-resolution high-detail dataset and benchmark for scene flow, optical flow and stereo.
In Proc. IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023a.

[Mehl et al., 2023]
Lukas Mehl, Jenny Schmalfuss, Azin Jahedi, Yaroslava Nalivayko, and Andrés Bruhn.
Spring: A high-resolution high-detail dataset and benchmark for scene flow, optical flow and stereo.
arXiv preprint arXiv:2303.01943, 2023b.

[Mian et al., 2008]
Ajmal S Mian, Mohammed Bennamoun, and Robyn Owens.
Keypoint detection and local feature matching for textured 3d face recognition.
International Journal of Computer Vision, 79:0 1–12, 2008.

[Minderer et al., 2019]
Matthias Minderer, Chen Sun, Ruben Villegas, Forrester Cole, Kevin P Murphy, and Honglak Lee.
Unsupervised learning of object structure and dynamics from videos.
Advances in Neural Information Processing Systems, 32, 2019.

[Mottaghi et al., 2016]
Roozbeh Mottaghi, Hessam Bagherinezhad, Mohammad Rastegari, and Ali Farhadi.
Newtonian scene understanding: Unfolding the dynamics of objects in static images.
In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 3521–3529, 2016.

[Mrowca et al., 2018]
Damian Mrowca, Chengxu Zhuang, Elias Wang, Nick Haber, Li F Fei-Fei, Josh Tenenbaum, and Daniel L Yamins.
Flexible neural representation for physics prediction.
Advances in neural information processing systems, 31, 2018.

[Nair et al., 2022]
Suraj Nair, Aravind Rajeswaran, Vikash Kumar, Chelsea Finn, and Abhinav Gupta.
R3m: A universal visual representation for robot manipulation.
arXiv preprint arXiv:2203.12601, 2022.

[Noroozi and Favaro, 2016]
Mehdi Noroozi and Paolo Favaro.
Unsupervised learning of visual representations by solving jigsaw puzzles.
In European conference on computer vision, pages 69–84. Springer, 2016.

[Oord et al., 2018]
Aaron van den Oord, Yazhe Li, and Oriol Vinyals.
Representation learning with contrastive predictive coding.
arXiv preprint arXiv:1807.03748, 2018.

[OpenAI, 2023]
Gpt-4 for vision (chatgpt with image input), 2023.
Accessed: October 27, 2023.

[Oquab et al., 2023]
Maxime Oquab, Timothée Darcet, Theo Moutakanni, Huy V. Vo, Marc Szafraniec, Vasil Khalidov, Pierre Fernandez, Daniel Haziza, Francisco Massa, Alaaeldin El-Nouby, Russell Howes, Po-Yao Huang, Hu Xu, Vasu Sharma, Shang-Wen Li, Wojciech Galuba, Mike Rabbat, Mido Assran, Nicolas Ballas, Gabriel Synnaeve, Ishan Misra, Herve Jegou, Julien Mairal, Patrick Labatut, Armand Joulin, and Piotr Bojanowski.
Dinov2: Learning robust visual features without supervision, 2023.

[Otte and Nagel, 1994]
Michael Otte and H H Nagel.
Optical flow estimation: advances and comparisons.
In Computer Vision—ECCV'94: Third European Conference on Computer Vision Stockholm, Sweden, May 2–6, 1994 Proceedings, Volume I 3, pages 49–60. Springer, 1994.

[Pathak et al., 2017]
Deepak Pathak, Ross Girshick, Piotr Dollár, Trevor Darrell, and Bharath Hariharan.
Learning features by watching objects move.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2701–2710, 2017.

[Perazzi et al., 2016]
F. Perazzi, J. Pont-Tuset, B. McWilliams, L. Van Gool, M. Gross, and A. Sorkine-Hornung.
A benchmark dataset and evaluation methodology for video object segmentation.
In Computer Vision and Pattern Recognition, 2016.

[Piloto et al., 2022]
Luis S Piloto, Ari Weinstein, Peter Battaglia, and Matthew Botvinick.
Intuitive physics learning in a deep-learning model inspired by developmental psychology.
Nature human behaviour, 60 (9):0 1257–1267, 2022.

[Pont-Tuset et al., 2017]
J. Pont-Tuset, F. Perazzi, S. Caelles, P. Arbelaez, A. Sorkine-Hornung, and L. Van Gool.
The 2017 davis challenge on video object segmentation.
arXiv preprint arXiv:1704.00675, 2017.

[Qi et al., 2020]
Haozhi Qi, Xiaolong Wang, Deepak Pathak, Yi Ma, and Jitendra Malik.
Learning long-term visual dynamics with region proposal interaction networks.
arXiv preprint arXiv:2008.02265, 2020.

[Qian et al., 2021]
Rui Qian, Tianjian Meng, Boqing Gong, Ming-Hsuan Yang, Huisheng Wang, Serge Belongie, and Yin Cui.
Spatiotemporal contrastive video representation learning.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 6964–6974, 2021.

[Ranjan and Black, 2017]
Anurag Ranjan and Michael J Black.
Optical flow estimation using a spatial pyramid network.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4161–4170, 2017.

[Riochet et al., 2021]
Ronan Riochet, Mario Ynocente Castro, Mathieu Bernard, Adam Lerer, Rob Fergus, Véronique Izard, and Emmanuel Dupoux.
Intphys 2019: A benchmark for visual intuitive physics understanding.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 440 (9):0 5016–5025, 2021.

[Sanchez-Gonzalez et al., 2018]
Alvaro Sanchez-Gonzalez, Nicolas Heess, Jost Tobias Springenberg, Josh Merel, Martin Riedmiller, Raia Hadsell, and Peter Battaglia.
Graph networks as learnable physics engines for inference and control.
In International Conference on Machine Learning, pages 4470–4479. PMLR, 2018.

[Shen et al., 2023]
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang.
Hugginggpt: Solving ai tasks with chatgpt and its friends in huggingface.
arXiv preprint arXiv:2303.17580, 2023.

[Sitzmann et al., 2019]
Vincent Sitzmann, Michael Zollhöfer, and Gordon Wetzstein.
Scene representation networks: Continuous 3d-structure-aware neural scene representations.
Advances in Neural Information Processing Systems, 32, 2019.

[Smith et al., 2019]
Kevin Smith, Lingjie Mei, Shunyu Yao, Jiajun Wu, Elizabeth Spelke, Josh Tenenbaum, and Tomer Ullman.
Modeling expectation violation in intuitive physics with coarse probabilistic object representations.
Advances in neural information processing systems, 32, 2019.

[Spelke, 1990]
Elizabeth S Spelke.
Principles of object perception.
Cognitive science, 140 (1):0 29–56, 1990.

[Stone et al., 2021]
Austin Stone, Daniel Maurer, Alper Ayvaci, Anelia Angelova, and Rico Jonschkowski.
Smurf: Self-teaching multi-frame unsupervised raft with full-image warping.
In Proceedings of the IEEE/CVF conference on Computer Vision and Pattern Recognition, pages 3887–3896, 2021.

[Sun et al., 2018]
Deqing Sun, Xiaodong Yang, Ming-Yu Liu, and Jan Kautz.
Pwc-net: Cnns for optical flow using pyramid, warping, and cost volume.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 8934–8943, 2018.

[Tacchetti et al., 2018]
Andrea Tacchetti, H Francis Song, Pedro AM Mediano, Vinicius Zambaldi, Neil C Rabinowitz, Thore Graepel, Matthew Botvinick, and Peter W Battaglia.
Relational forward models for multi-agent learning.
arXiv preprint arXiv:1809.11044, 2018.

[Teed and Deng, 2020]
Zachary Teed and Jia Deng.
Raft: Recurrent all-pairs field transforms for optical flow.
In Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part II 16, pages 402–419. Springer, 2020.

[Tong et al., 2022]
Zhan Tong, Yibing Song, Jue Wang, and Limin Wang.
Videomae: Masked autoencoders are data-efficient learners for self-supervised video pre-training.
Advances in neural information processing systems, 35:0 10078–10093, 2022.

[Touvron et al., 2023]
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al.
Llama: Open and efficient foundation language models.
arXiv preprint arXiv:2302.13971, 2023.

[Tung et al., 2023]
Hsiao-Yu Tung, Mingyu Ding, Zhenfang Chen, Daniel Bear, Chuang Gan, Joshua B Tenenbaum, Daniel LK Yamins, Judith E Fan, and Kevin A Smith.
Physion++: Evaluating physical scene understanding that requires online inference of different physical properties.
arXiv preprint arXiv:2306.15668, 2023.

[Voleti et al., 2022]
Vikram Voleti, Alexia Jolicoeur-Martineau, and Chris Pal.
Mcvd-masked conditional video diffusion for prediction, generation, and interpolation.
Advances in Neural Information Processing Systems, 35:0 23371–23385, 2022.

[Wang et al., 2018]
Limin Wang, Yuanjun Xiong, Zhe Wang, Yu Qiao, Dahua Lin, Xiaoou Tang, and Luc Van Gool.
Temporal segment networks for action recognition in videos.
IEEE transactions on pattern analysis and machine intelligence, 410 (11):0 2740–2755, 2018.

[Wang et al., 2023]
Limin Wang, Bingkun Huang, Zhiyu Zhao, Zhan Tong, Yinan He, Yi Wang, Yali Wang, and Yu Qiao.
Videomae v2: Scaling video masked autoencoders with dual masking.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14549–14560, 2023a.

[Wang and Gupta, 2015]
Xiaolong Wang and Abhinav Gupta.
Unsupervised learning of visual representations using videos.
In Proceedings of the IEEE international conference on computer vision, pages 2794–2802, 2015.

[Wang et al., 2022]
Xinlong Wang, Zhiding Yu, Shalini De Mello, Jan Kautz, Anima Anandkumar, Chunhua Shen, and Jose M Alvarez.
Freesolo: Learning to segment objects without annotations.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14176–14186, 2022.

[Wang et al., 2023]
Xudong Wang, Rohit Girdhar, Stella X Yu, and Ishan Misra.
Cut and learn for unsupervised object detection and instance segmentation.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3124–3134, 2023b.

[Wang et al., 2023]
Yangtao Wang, Xi Shen, Yuan Yuan, Yuming Du, Maomao Li, Shell Xu Hu, James L Crowley, and Dominique Vaufreydaz.
Tokencut: Segmenting objects in images and videos with self-supervised transformer and normalized cut.
IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023c.

[Wu et al., 2018]
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin.
Unsupervised feature learning via non-parametric instance discrimination.
In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3733–3742, 2018.

[Wu et al., 2022]
Ziyi Wu, Nikita Dvornik, Klaus Greff, Thomas Kipf, and Animesh Garg.
Slotformer: Unsupervised visual dynamics simulation with object-centric models.
arXiv preprint arXiv:2210.05861, 2022.

[Yan et al., 2023]
Wilson Yan, Danijar Hafner, Stephen James, and Pieter Abbeel.
Temporally consistent transformers for video generation.

[Ye et al., 2019]
Yufei Ye, Maneesh Singh, Abhinav Gupta, and Shubham Tulsiani.
Compositional video prediction.
In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 10353–10362, 2019.

[Yu et al., 2021]
Alex Yu, Vickie Ye, Matthew Tancik, and Angjoo Kanazawa.
pixelnerf: Neural radiance fields from one or few images.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 4578–4587, 2021a.

[Yu et al., 2021]
Hong-Xing Yu, Leonidas J Guibas, and Jiajun Wu.
Unsupervised discovery of object radiance fields.
arXiv preprint arXiv:2107.07905, 2021b.

[Yu et al., 2023]
Lijun Yu, Yong Cheng, Kihyuk Sohn, José Lezama, Han Zhang, Huiwen Chang, Alexander G Hauptmann, Ming-Hsuan Yang, Yuan Hao, Irfan Essa, et al.
Magvit: Masked generative video transformer.
In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10459–10469, 2023.

[Zhang et al., 2016]
Richard Zhang, Phillip Isola, and Alexei A Efros.
Colorful image colorization.
In Computer Vision–ECCV 2016: 14th European Conference, Amsterdam, The Netherlands, October 11-14, 2016, Proceedings, Part III 14, pages 649–666. Springer, 2016.

[Zhuang et al., 2020]
Chengxu Zhuang, Tianwei She, Alex Andonian, Max Sobol Mark, and Daniel Yamins.
Unsupervised learning from video with deep neural embeddings.
In Proceedings of the ieee/cvf conference on computer vision and pattern recognition, pages 9563–9572, 2020.

§ SUPPLEMENTARY MATERIAL


# Using Elementary Techniques to Characterize the Relationship Between
Wythoff’s Game and the Golden Ratio

Vincent Wang  Nikhil Sampath  Eric Yule Special thanks Ethan
Wang11footnotemark: 1

(January 2023)

##  1 Introduction

Wythoff’s game is a modification of the well-known game of “nim.” Wythoff’s
game, which does not resemble the Fibonacci sequence, has direct relation to
the Golden ratio. We will explore the sequence behind this surprising
relationship, and consider the implications of our elementary methods.

Wythoff’s game is also known as the game of Ps and Qs. The game has two
players taking turns removing chips of two types: P and Q (hence the game’s
name). Each turn has a player take any number of available Ps (and only Ps),
any number of available Qs (and only Qs), or any same number of available Ps
and Qs (for example a turn can have 2 Ps and 2 Qs being taken). Players
alternate their turns until the player to remove the last chip wins [1].

Let us begin with notations and conventions. The first player is the player
who took the first turn. The second player is the other player. Denote the
state of $x$ Ps and $y$ Qs by $\left<x,y\right>$. If we start with
$\left<1,2\right>$, no matter what turn the first player took, the second
player can take a turn to win. We call a state where the second player can
force a win a losing state, so that $\left<1,2\right>$ is losing. Analogously
define a state where the first player can force a win a winning state.

We have some early observations. We observe that “most” states are winning
states, which motivates us to find the “fewer” losing states. With some work,
we find that $\left<3,5\right>$ is the next losing state (because of symmetry
of the game with respect to P and Q, take $x<y$). Our final observation is
that if $\left<x,y\right>$ has the property that exactly one of $x$ or $y$ was
a component of a previously found losing state $\left<z,w\right>$, we can
sometimes reduce $\left<x,y\right>$ to $\left<z,w\right>$, making
$\left<x,y\right>$ a winning state. Wythoff, the mathematician for which the
game is named after, characterizes this precisely in his fourth observation
[2]. Our observations and computations111For reference Wythoff lists the first
few pairs of losing states on page 200 of [2] of the first few losing states
motivate the following conjecture:

Define the sequences $p(n)$, $q(n)$ for $n\geq 1$ recursively as follows:
$p(1)=1$, $q(n)=p(n)+n$ for all $n\geq 1$, and $p(n+1)$ the smallest positive
integer not contained in

$U_{n}=\\{p(1),p(2),p(3),\dots,p(n),q(1),q(2),q(3),\dots,q(n)\\}.$

Then $\left<p(n),q(n)\right>$ for $n\geq 1$ characterizes all losing states.

We believe some scholarship already shows that $p$ and $q$ solve the game. The
conjecture is provable by inducting on the value of $y-x$ over all such states
$\left<x,y\right>$ in addition to significant casework on potential moves by
each player. Such casework and induction is rather uninteresting. We are not
focused on the game theory, but rather the analysis of the sequences $p$ and
$q$. Hence we will not prove the previous conjecture in this paper. Upon
further inspection of our first few losing states, we find that the ratio of
$q(n)$ to $p(n)$ does not grow as $n$ grows. If we plot $q$ versus $p$ in the
Cartesian coordinate plane we find that the set of all points $(p,q)$ closely
follows the line through the origin with slope $\phi$, the Golden ratio.
Consequently, we instead focus on the following conjecture:

$p(n)=\left\lfloor\phi n\right\rfloor\text{ and
}q(n)=\left\lfloor\phi^{2}n\right\rfloor\text{ for all }n\geq 1.$

This direct relationship between the Golden ratio $\phi$ and our sequences $p$
and $q$ is very motivating.

Although Wythoff proves our conjecture brilliantly, we will offer an alternate
partial proof. Wythoff’s solution is effective as it quickly exploits the
properties of $p$ and $q$, but it is also contrite as these properties are
used in unison. Our elementary methods are incremental and offer ideas that
can be applied to other problems.

##  2 Understanding $p$ and $q$

We will understand the behavior of $p$ and $q$ before we formalize the
relationship between $p$, $q$, and $\phi$. For convenience we have the
following naming conventions. $p$ by itself refers to the sequence
$p(1),p(2),p(3),\dots$. If $N$ is a $p$, $N$ is contained in $p$. $N$ $p$s
refers to a collection of $N$ elements of $p$. We have analogous names for
$q$. Denote the set $\\{1,2,3,\dots,m\\}$ by $[m]$. We begin with a couple
lemmas.

Lemma 1: $p$ is strictly increasing
Proof of Lemma 1: We show the case of $p(n+2)>p(n+1)$ for all $n\geq 1$. The
case of $p(2)>p(1)$ is left to the reader. Then it remains to show
$[p(n+1)]\subseteq U_{n+1}$. Note for $n\geq 1$, $[p(n+1)-1]\subseteq U_{n}$
by the minimality of $p(n+1)$. Therefore

$[p(n+1)-1]\cup\\{p(n+1)\\}\subseteq U_{n}\cup\\{p(n+1)\\}\subseteq
U_{n}\cup\\{p(n+1),q(n+1)\\},$

or $[p(n+1)]\subseteq U_{n+1}$, as desired.

Corollary 2: There cannot be two consecutive $q$s. Define $\Delta
q(n)=q(n+1)-q(n)$ for $n\geq 1$. Then $\Delta q(n)\geq 2$.
Proof of Corollary 2: Follows from Lemma 1 and $q(n)=p(n)+n$.

Lemma 3: $p$ and $q$ partition $\mathbb{Z}^{+}$. That is, given any $N\geq 1$,
$N$ appears exactly once in $p$ or $q$ (but not both).
Proof of Lemma 3: This fact should be rather natural. After some
experimentation, one should see that $q$ is generated “first”, while $p$ fills
in the gaps left by $q$. For completeness, our two part proof is as follows.
We first show that any $N\geq 1$ appears in some $U$, then show the elements
of $U$ are distinct. As seen in the proof for $p$ increasing (Lemma 1), we
have $[p(n+1)\subseteq U_{n+1}]$. Take $n$ sufficiently large, so $N\leq
p(n+1)$ (we can do this because $p$ is strictly increasing). Then
$N\in[p(n+1)]$, and $N\in U_{n+1}$. $p$s are pairwise distinct as $p$ is
increasing. $q$s are pairwise distinct as $q$ is increasing. It remains for us
to show a $p$ cannot be a $q$. Consider any $p(k)$ and $q(j)$ for $k,j\geq 1$.
If $j<k$, $p(k)\neq q(j)$ by construction. If $j\geq k$, $q(j)\geq
q(k)=k+p(k)>p(k)$, completing the proof.

Lemma 4: Similarly define $\Delta p(n)=p(n+1)-p(n)$ for $n\geq 1$. Then
$\Delta p(n)\in\\{1,2\\}$.
Proof of Lemma 4: $p(n)$ is increasing, so then next $p$ is at least $p(n)+1$.
If $p(n)+1$ is a $p$, we are done and $p(n+1)=p(n)+1$. Otherwise, $p(n)+1$ is
a $q$ as $p,q$ partition $\mathbb{Z}^{+}$. There cannot be two consecutive
$q$s by Corollary 2, so $p(n)+2$ cannot be a $q$, and hence must be a $p$,
again by $p,q$ being a partition of $\mathbb{Z}^{+}$. In this case,
$p(n+1)=p(n)+2.$ We have exhausted all cases, proving the lemma.

Corollary 5: $\Delta q(n)\in\\{2,3\\}$ for all $n\geq 1$
Proof of Corollary 5: Follows from $\Delta p(n)\in\\{1,2\\}$ and
$q(n)=p(n)+n$.

Corollary 6: There do not exist three consecutive $p$s.
Proof of Corollary 6: Follows from the previous corollary, $q(1)=2$, and $p$,
$q$ partition $\mathbb{Z}^{+}$.

After much consideration, we realize that there is little more we can say
directly about $p$ and $q$. We have reached a “bottleneck.” To push through
this bottleneck, we have a clever construction, which is a key focus of our
paper.

Lemma 7: $q(n)=p(p(n))+1$ for all $n\geq 1$.
Proof of Lemma 7: Consider the set $[q(n)]$. The $q$s of this set are
precisely $\\{q(1),q(2),q(3),\dots,q(n)\\}$, and there are $n$ of them. $p$
and $q$ partition $\mathbb{Z}^{+}$, so there are $q(n)-n=p(n)$ $p$s of
$[q(n)]$ (1). There cannot be two consecutive $q$s, so $q(n)-1$ is a $p$.
Moreover, $q(n)-1$ is the largest $p$ in $[q(n)]$ (2). Combining (1) and (2)
gives $q(n)-1=p(p(n))$, as desired.

The crux idea of this proof is that $p$ and $q$ partition $\mathbb{Z}^{+}$, so
each positive integer is either a $p$ or a $q$. This seemingly trivial idea of
being one or the other is very powerful. More generally, the fact that for any
item $x$ and set $S$, we have either $x\in S$ or $x\not\in S$. We believe that
strong theorems can be proven using set constructions exploiting the
properties of the elements of that set. Here we used the property that there
cannot be two consecutive $q$s and $q(n)=p(n)+n$. Let us see the implications
of this result.

Lemma 8: $\Delta p(n)=2$ if and only if $n$ is a $p$ for all $n\geq 1$.
Proof of Lemma 8: We present a non-typical method of proof, which we verify
first as follows. Let $a$, $b$, and $c$ be statements and $\neg a$ denote the
negation of statement $a$. We claim that if we show $a\rightarrow b$,
$a\rightarrow c$, $\neg a\rightarrow\neg b$, and $\neg a\rightarrow\neg c$,
then $b\leftrightarrow c$. The reason for the truth of this is as follows.
$\neg a\rightarrow\neg b$ and $\neg a\rightarrow\neg c$ become $b\rightarrow
a$ and $c\rightarrow a$ as any statement is equivalent to its contrapositive.
From this we find $a\leftrightarrow b$ and $a\leftrightarrow c$, so
$b\leftrightarrow c$, as desired.

In our proof, $a$ is “$p(n)+1$ is a $p$”, $b$ is “$\Delta p(n)=1$”, and $c$ is
“$n$ is a $q$”. It follows that $\neg a$ is “$p(n)+1$ is a $q$”, $\neg b$ is
“$\Delta p(n)=2$”, and $c$ is “$n$ is a $p$”. By our work for $\Delta
p(n)\in\\{1,2\\}$, we know $a\rightarrow b$ and $\neg a\rightarrow\neg b$. It
suffices to show $a\rightarrow c$ and $\neg a\rightarrow\neg c$. In words, we
want to show that “If $p(n)+1$ is a $p$, then $n$ is a $q$” and “If $p(n)+1$
is a $q$, then $n$ is a $p$”. For convenience, consider our proof for $n\geq
2$ to avoid edge cases. Edge cases are left to the reader.

Suppose $p(n)+1$ is a $p$. $p(n)-1$ must be a $q$, say $q(l)$, as there cannot
exist three consecutive $p$s. Similarly, we know $q(l+1)=p(n)+2$. In all,
$p(n-1)+1=q(l)$ ($q(l)$ is one more than the $p$ before $p(n)$), and
$p(n+1)+1=q(l+1)$ (with similar reasoning). By the previous lemma,
$q(l)=p(p(l))+1$ and $q(l+1)=p(p(l+1))+1$, so $p(p(l))=p(n-1)$ and
$p(p(l+1))=p(n+1)$. From $p$ and $q$ being strictly increasing, $n-1=p(l)$ and
$n+1=p(l+1)$. That is, $n-1$ and $n+1$ are $p$s, from which we must have that
$n$ is a $q$.

Now suppose $p(n)+1$ is a $q$, say $q(l)$. From the previous lemma again,
$q(l)=p(p(l))+1$, so $p(p(l))=p(n)$. Hence $p(l)=n$ as $p$ is increasing. In
other words, $n$ is a $p$, as desired.

If we know $\Delta p(n)$ for all $n\geq 1$, it is natural to think that we can
write $p(n)$ recursively of itself. The following corollary confirms our
intuition.

Corollary 9: $p(n+1)$ is the number of $i$ in the range $1\leq i\leq n$
appearing in $\\{p(1),p(2),p(3),\dots,p(n)\\}$, added to $n+1$.
Proof of Corollary 9: This is a straightforward induction argument following
from the previous lemma and $p(n)\geq n$ (as $p$ is strictly increasing).

A big idea here is that we have found a recurrence for $p(n)$ independent of
$q(n)$, which we will exploit later. This statement is very powerful as the
previous two-sequence definition of $p(n)$ and $q(n)$ was too clumsy to use
effectively. Another other big idea is the methodology of using clever set
construction to compute $p(p(n))$ (and therefore $q(p(n))=p(p(n))+p(n)$). We
are very motivated to develop forms for $p(q(n))$ and $q(q(n))$, which we
achieve in next few lemmas in the next section. A couple of corollaries follow
from these new forms. The next section is not our main focus. Instead it shows
the application of our crux method of attack and brings out the beauty of the
coupled sequences $p$ and $q$. It is possible to skip the next section to see
the relationship between $p$, $q$, and $\phi$.

##  3 The Beauty of $p$ and $q$

We will apply our method of set construction to discover beautiful relations
in $p$ and $q$.

Corollary 10: $q(p(n))=p(n)+q(n)-1$.
Proof of Corollary 10: Follows from $p(p(n))=q(n)+1$ and the definition of
$q$.

Lemma 11: $p(q(n))=p(n)+q(n)$.
Proof of Lemma 11: Consider $[q(p(n))+1]$. There are $p(n)$ $q$s in
$[q(p(n))+1]$, so there are $q(p(n))+1-p(n)=p(p(n))+1$ $q$s. We know
$q(n)=p(p(n))+1$, so there are $q(n)$ $p$s in $[q(p(n))+1]$. There cannot
exist two consecutive $q$s, so $q(p(n))+1$ is a $p$, in fact the largest $p$
of $[q(p(n))+1]$. Hence $p(p(n))=q(p(n))+1$. The previous corollary finishes.

Corollary 12: If $\left<p(n),q(n)\right>$ is a $p-q$ pair, then so is
$\left<p(n)+q(n),p(n)+2q(n)\right>$.
Proof of Corollary 12: We know $p(n)+q(n)=p(q(n))$ and
$p(n)+2q(n)=p(q(n))+q(n)=q(q(n))$, as needed.

The previous corollary reminds us greatly of the Fibonacci sequence. We finish
with the most beautiful equation.

Corollary 13: $p(q(n))=q(p(n))+1$.
Proof of Corollary 13: Follows from our forms for $p(q(n))$ and $q(p(n))$.

##  4 Linking $p$, $q$, and $\phi$

Recall that we had the really motivating conjecture of $p(n)=\left\lfloor\phi
n\right\rfloor$ and $q(n)=\left\lfloor\phi^{2}n\right\rfloor$. With our
knowledge of the behavior of $p$ and $q$, we are finally ready to attack this
conjecture. Unfortunately, we were unable to show equality. However, we
present promising partial work.

Lemma 14:  Define by $E(n)=p(n)-\left\lfloor n\phi\right\rfloor$. Then
$E(n)\in\\{-1,0,1\\}$ for all $n\in\mathbb{Z}^{+}$.
Proof of Lemma 14:  We proceed by strong induction on $n$.

Base case(s):  By direct computation, we have
$E(1)=E(2)=E(3)=E(4)=E(5)=E(6)=0\in\\{-1,0,1\\}$.
Inductive Step:  Assume that the result holds for $n=1,2,3,\dots,k$ for some
$k\geq 6$. We wish to show that the result holds for $n=k+1$. That is,
$E(k+1)\in\\{-1,0,1\\}$.

There is a unique $j\in\mathbb{Z}^{+}$ for which $p(j)\leq k<p(j+1)$. Our
subgoal is to show that $j\leq k-1$, so we can apply the inductive hypothesis
to $p(j)$ and $p(j+1)$. Denote by $j^{\prime}$ the maximum positive integer
for which $j^{\prime}\leq k-1\text{ }(1)$ and
$j^{\prime}<\frac{k-E(j)+1}{\phi}\text{ }(2)$. We can write $(2)$ equivalently
as:

$j^{\prime}\phi<k-E(j^{\prime})+1\Longleftrightarrow\left\lfloor
j^{\prime}\phi\right\rfloor\leq k-E(j^{\prime})\Longleftrightarrow\left\lfloor
j\phi\right\rfloor+E(j^{\prime})\leq k\Longleftrightarrow p(j^{\prime})\leq
k.$

Now $(1)$ is weaker than $(2)$ (as for $k\geq 6$,
$\frac{k-E(j^{\prime})+1}{\phi}\leq\frac{k+2}{\phi}\leq k-1$), so we in fact
have $j^{\prime}=j$. We can now safely apply the induction hypothesis to $j$
and $j+1$.

We know $j<\frac{k-E(j)+1}{\phi}\leq\frac{k+2}{\phi}$, so
$j\leq\left\lfloor\frac{k+2}{\phi}\right\rfloor$. From $k<p(j+1)$, we have

$\displaystyle k<\left\lfloor(j+1)\phi\right\rfloor+E(j+1)$
$\displaystyle\Longleftrightarrow k-E(j+1)<\left\lfloor(j+1)\phi\right\rfloor$
$\displaystyle\Longleftrightarrow
k-E(j+1)+1\leq\left\lfloor(j+1)\phi\right\rfloor$
$\displaystyle\Longleftrightarrow k-E(j+1)+1<(j+1)\phi$
$\displaystyle\Longleftrightarrow\frac{k-E(j+1)+1}{\phi}-1<j$
$\displaystyle\Longrightarrow\frac{k-1+1}{\phi}-1<j$
$\displaystyle\Longrightarrow\left\lfloor\frac{k}{\phi}\right\rfloor\leq j.$

This means that $\left\lfloor\frac{k}{\phi}\right\rfloor\leq
j\leq\left\lfloor\frac{k+2}{\phi}\right\rfloor$.

We now use the properties that for all $a,b\in\mathbb{R}$, we have
$\left\lfloor a+b\right\rfloor\leq\left\lfloor a\right\rfloor+\left\lfloor
b\right\rfloor+1$ and $\left\lfloor a+b\right\rfloor\geq\left\lfloor
a\right\rfloor+\left\lfloor b\right\rfloor$. Let
$X=j-\left\lfloor\frac{k}{\phi}\right\rfloor\geq 0$. Then

$X\leq\left\lfloor\frac{k+2}{\phi}\right\rfloor-\left\lfloor\frac{k}{\phi}\right\rfloor\leq\left\lfloor\frac{k}{\phi}\right\rfloor+\left\lfloor\frac{2}{\phi}\right\rfloor+1-\left\lfloor\frac{k}{\phi}\right\rfloor=2.$

Somewhat similarly, define $Y=\left\lfloor(k+1)\phi\right\rfloor-\left\lfloor
k\phi\right\rfloor$ for some $Y\in\mathbb{Z}_{\geq 0}$. Again using the above
floor property, we find

$Y\leq\left\lfloor
k\phi\right\rfloor+\left\lfloor\phi\right\rfloor+1-\left\lfloor
k\phi\right\rfloor=2.$

Using the other floor property, we find

$Y\geq\left\lfloor
k\phi\right\rfloor+\left\lfloor\phi\right\rfloor-\left\lfloor
k\phi\right\rfloor=1.$

In all, we know $X\in\\{0,1,2\\}$ and $Y\in\\{1,2\\}$.

Note that the number of $l\leq k$ for which $l$ is in
$p(1),p(2),p(3),\dots,p(n)$ is precisely $j$. It follows by Corollary 3, the
recursive definition of $p(n)$ using itself, that $p(k+1)=k+1+j$, and that:

$\displaystyle E(k+1)$
$\displaystyle=p(k+1)-\left\lfloor(k+1)\phi\right\rfloor$
$\displaystyle\stackrel{{\scriptstyle 1}}{{=}}k+1+\left\lfloor
k/\phi\right\rfloor+X-\left\lfloor k\phi\right\rfloor-Y$
$\displaystyle\stackrel{{\scriptstyle 2}}{{=}}k+1+\left\lfloor
k(\phi-1)\right\rfloor+X-\left\lfloor k\phi\right\rfloor-Y$
$\displaystyle=k+1+\left\lfloor k\phi\right\rfloor-k+X-\left\lfloor
k\phi\right\rfloor-Y$ $\displaystyle=1+X-Y.$

Note that step $1$ is from the definitions of $X$ and $Y$ and step $2$ is from
a well known property of $\phi$. It remains to show that
$1+X-Y\in\\{-1,0,1\\}$.

The only case when $E(k+1)\not\in\\{-1,0,1\\}$ is when $(X,Y)=(2,1)$. It
remains for us to show that this case is impossible. Suppose for the sake of
contradiction that $E(j)\leq 0$. Then from $j<\frac{k-E(j)+1}{\phi}$, we have
$j<\frac{k+1}{\phi}$, so $j\leq\left\lfloor\frac{k}{\phi}\right\rfloor+1$ and
hence $X\leq 1$, a contradiction. This means $E(j)=-1$ and
$j=\frac{k+2}{\phi}$, from which we find
$\left\lfloor\frac{k+2}{\phi}\right\rfloor=\left\lfloor\frac{k}{\phi}\right\rfloor+2$
as $X=2$. We rewrite this equation as follows:

$\displaystyle\left\lfloor\frac{k+2}{\phi}\right\rfloor=\left\lfloor\frac{k}{\phi}\right\rfloor+2$
$\displaystyle\Longleftrightarrow\left\lfloor(k+2)(\phi-1)\right\rfloor=\left\lfloor
k(\phi-1)\right\rfloor+2$
$\displaystyle\Longleftrightarrow\left\lfloor(k+2)\phi\right\rfloor-k-2=\left\lfloor
k\phi\right\rfloor-k+2$
$\displaystyle\Longleftrightarrow\left\lfloor(k+2)\phi\right\rfloor=\left\lfloor
k\phi\right\rfloor+4\text{ }(3).$

Using the fact that $Y=1$, or that
$\left\lfloor(k+1)\phi\right\rfloor=\left\lfloor k\phi\right\rfloor+1$ with
$(3)$, we get
$\left\lfloor(k+2)\phi\right\rfloor=\left\lfloor(k+1)\phi\right\rfloor+3$,
which is impossible.

We have therefore shown $E(k+1)\in\\{-1,0,1\\}$ and hence completed the strong
induction.

The main takeaway from this proof is that we used local information relative
to the functions $f(n)=\left\lfloor n\phi\right\rfloor$ and $g(n)=\left\lfloor
n/\phi\right\rfloor$ by applying it to what we already know about $p(n)$. If
we can extract stronger local information of $f$ and $g$, we can possibly
sharpen our result to $p(n)=\left\lfloor n\phi\right\rfloor$. Regardless of
potential improvement, our result is already very strong. If we are given any
$n$, we can guarantee $p(n)$ to be within $1$ away from $\left\lfloor
n\phi\right\rfloor$ without having to perform any recursion.

##  5 Future Work

Our method of set construction has weak application to the primes. Let $P$
denote the sequence of all primes in increasing order. That is, $P$ contains
$2,3,5,7,\dots$ in that order. Define by $Q$ the gaps of composites that $P$
left. That is, $Q$ contains $4,6,8,9,10,12,14,15,16,18,20,21,22,\dots$ in that
order. We claim that $Q(P(n)-n-1)=P(n)-1$ for $n\geq 3$. Consider the set
$[P(n)]$. There are $n$ $P$s in this set, so there are $P(n)-n-1$ $Q$s in this
set (as we do not count $1$ in either $P$ or $Q$). For $n\geq 3$, $P(n)-1$
must be a $Q$ as the only consecutive primes are $2$ and $3$. Hence
$Q(P(n)-n-1)=P(n)-1$, as desired. We believe that it is possible to create
constructions that better exploit the properties of the primes and create more
useful equations. Here we only used the fact that most primes are
nonconsecutive.

##  6 Conclusion

We used elementary techniques to prove non-elementary results. Our initial
confusing definition of $p$ and $q$ gave the unexpected conjecture of
$p(n)=\left\lfloor\phi n\right\rfloor$ and
$q(n)=\left\lfloor\phi^{2}n\right\rfloor$. We were close to proving this
relationship by showing that $p(n)$ is at most $1$ away from $\left\lfloor\phi
n\right\rfloor$. Our elementary technique of clever set constructions allowed
us to convert qualitative data about $p$ and $q$ into quantitative data.

## References

  * [1] Wikipedia  “Wythoff’s Game”  URL: https://en.wikipedia.org/wiki/Wythoff%27s_game
  * [2] W.A. Wythoff  “A Modification of the Game of Nim”, New Archive for Math  Mathematical Society in Amsterdam, 1981


# A call for better unit testing for Invariant Risk Minimisation

Chunyang Xiao1,†, Pranava Madhyastha2,⋆
1Bloomberg
2Imperial College London
Email: †<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper we present a controlled study on the linearized IRM framework
(IRMv1) introduced in Arjovsky et al. (2020). We show that IRMv1 (and its
variants) framework can be potentially unstable under small changes to the
optimal regressor. This can, notably, lead to worse generalisation to new
environments, even compared with ERM which converges simply to the global
minimum for all training environments mixed up all together. We also highlight
the isseus of scaling in the the IRMv1 setup. These observations highlight the
importance of rigorous evaluation and importance of unit-testing for measuring
progress towards IRM.

##  1 Introduction

Invariant risk minimization (IRM) (Arjovsky et al., 2020) is a machine
learning framework whose primary goal is to learn invariances across multiple
training environments. In contrast to Empirical Risk Minimisation (ERM)
(Vapnik, 1991), IRM does not make any assumptions on training samples to be
identically distributed; instead, samples are sampled from multiple
environments and hence proposes to find associations that are invariant across
these environments.

ERM approaches usually assume the training set is independently sampled from a
single distribution and seek to optimize the performance of the machine
learning algorithms for samples from the same distribution. In reality,
however, training data constitutes samples from a heterogeneous sets of
distributions: such as data sampled from different sources, different time,
etc.. Thus an ideal algorithm would have learned correlations that are ‘
_true_ ’ correlations which are consistent across environments and hence
reduce the chances of capturing spurious correlations that are only correct
under a specific environment.

The IRM framework attempts to find a data representation that aims to
disregard the spurious correlations and optimising ‘ _true_ ’ correlations
that are generally correct across the different environments. The general IRM
framework (Arjovsky et al., 2020) is a non-linear framework which while
powerful can be difficult to realise in many scenarios111For more details, we
refer the reader to the discussion in Arjovsky et al. (2020).

In this paper, we focus on a simpler, linearized variant of IRM (Arjovsky et
al., 2020) also called IRMv1 which is defined with respect to risks. The
_risks_ in this context are defined on the basis of population errors that
include both training errors and feature stability penalization in contrast to
solely training errors in ERM. In this paper we perform a controlled study of
the linearized setting, which is one of the prominent approaches explored in
the recent work (Ahuja et al., 2020; Koyama & Yamaguchi, 2021), and highlight
that IRM is highly unstable over the initial settings of the optimal regressor
especially for benchmark tasks. Our observations strongly recommend for a more
rigorous unit-testing and evaluation setup to correctly estimate progress
towards this framework. Our code can be found at
https://github.com/chunyangx/IRM_research.

##  2 Method

###  2.1 Background

ERM is the de facto machine learning framework that is used out of box in most
of the current models. Briefly it works by building a model which chooses the
hypothesis space that minimizes the risk. However, it has been noted that this
standard formulation and procedure is not without issues, for example the
model tends to learn biases from the dataset, as shown by both simple but
illustrating problems (Beery et al., 2018) and real problems (Sturm, 2014;
Torralba & Efros, 2011).

One promising direction that attempts to address such issues is to bias the
model to learn causal relations and ignore spurious correlations. IRM
(Arjovsky et al., 2020) is one such framework that attempts to achieve this.
The basic intuition behind IRM is that causal features are stable across
different learning settings (also called environments) while spurious features
tend to have larger variance across environments; thus by retaining and
focusing only on the stable features across environments, a model trained in
the IRM framework can potentially retain causal components and thereby can
generalize better across various testing settings.

We present the simplified IRM objective as proposed in Arjovsky et al. (2020)
in Equation 1 which is composed of two terms.

$\min_{\Phi:\mathcal{X}\to\mathcal{Y}}\sum_{e\in\mathcal{E}_{\text{tr}}}\mathbf{R}^{e}{(\Phi)}+\lambda\|\nabla_{w{\mid}w=1.0}\mathbf{R}^{e}(w\cdot\Phi)\|^{2};$
(1)

where, $\mathbf{R}^{e}{(\Phi)}$ corresponds to the standard ERM framework and
minimizes the risk across all environments. Whereas,
$\|\Delta_{w{\mid}w=1.0}\mathbf{R}^{e}(w\cdot\Phi)\|^{2}$ penalizes features
that have large gradient222We note that the gradient computed based on a fixed
uniform classifier, which is in contrast to usual settings where the weights
of the classifier is learned via optimization thus is non-fixed.. Intuitively,
a stable feature once optimized will converge to a representation where the
gradient tends to zero; non-stable features will have gradients which differ a
lot across environments, and will thus be penalized by the second term, making
the feature’s norm tend to zero and thus ignored by the final model through
optimization.

###  2.2 An IRM testing setting

To test the empirical performance of IRM algorithm, several simple but
illustrative settings have been proposed and compared in the literature. In
this work, we focus on one graphical regression setting, the graphical model
is depicted in Figure 1. The setting is proposed in the IRM original paper
(Arjovsky et al., 2020) and are discussed and bench-marked in many followup
works that include (Ahuja et al., 2020; Aubin et al., 2021; Koyama &
Yamaguchi, 2021).

The setting consists of a simple regression setting with spurious variables.
As shown by Figure 1, $Z_{1}^{e}$ causes $Y^{e}$ across environments, contrary
to $Z_{2}^{e}$ which is “caused” by $Y^{e}$ and thus is treated as spurious
features in the learning setting.333As we can see in subsection 3.1.2, the
main difference between $Z_{1}^{e}$ and $Z_{2}^{e}$ is not the arrow direction
but the noise applied to these variables with the corresponding implications.
This main chain of variables can be further complicated by introducing a co-
founder hidden variable $H^{e}$. Finally, two noise models namely
homoskedastic and heteroskedastic with different scales are applied to
$Z_{1}^{e}$ and $Z_{2}^{e}$ respectively. Thus in total, We consider a total
of four different settings.444We note that this is the same set of settings
considered in Ahuja et al. (2020), which omits the weight matrices
transformation cases compared to Arjovsky et al. (2020).

Compared to the graphical model as specified in Equation 1, we observe that
previous work on IRM (Ahuja et al., 2020; Aubin et al., 2021; Koyama &
Yamaguchi, 2021) have further simplified the assumptions where the variable
$Y^{e}$ to regress to is reduced to a scalar which is considered as the sum of
all its coordinates. This is usually performed to facilitate model analysis.
In this case, it is easy to show that the optimal weight turns into a vector
which is essentially the sum of corresponding weight in $W_{1\rightarrow y}$.
In this paper, we call this vector the optimal regressor.

##  3 Experimental Investigation

###  3.1 On experimental settings

In this section, we focus on the IRMv1 experimental setting and explore in two
directions.

Figure 1: The unit test considered in this work.

#### The problem with scaling

In the original IRM experimental setup (Arjovsky et al., 2020), the optimal
regressor is set to a uniform vector of ones. The same setup is further used
in the follow up works such as Ahuja et al. (2020). While Aubin et al. (2021)
show that IRM is able to generalise sufficiently well under a wider range of
settings by sampling the weight matrix from Gaussian distributions, we however
notice that the Gaussian distributions in their experimental framework do not
vary in scales as we do in this work. In this paper we focus on the effects of
changes in the results and/or the conclusions based on simply drawing from the
Gaussian samples with a small change in scale.

Our focus on the scales are first inspired by the results that gradient based
algorithms have been shown to have difficulties finding optima as they are
sensitive to scaling issues (Beery et al., 2018). But our empirical results
show that IRM formulation seems to particularly suffer from the scaling
issues, which can not be simply explained by the optimization aspect.

In the following we first analyse the experimental setup before present a
hypothesis that reflects on this instability.

#### Noise with multiple roles

There are two noise terms in the equations shown in Figure 1.555To simplify
the discussion, we will omit the hidden variables $H^{e}$ in the discussion of
here, although one can note that this doesn’t lose generality as we focus only
on the noise terms. The noise $\sigma_{y}^{2}$ is the natural Gaussian noise
that we see in linear regression. However, we note that the noise
$\sigma_{2}^{2}$ plays quite a different role as shown in in Figure 1. To
examine this further, we first inverse the arrow such that the equation
confirms to the normal prediction based formulation as the arrow now points
from target variable $Y$ to spurious features $Z_{2}$ (as seen in the graph).
Let $W_{y\rightarrow 2}^{-1}$ the inverse of the matrix $W_{y\rightarrow 2}$,
by omitting the $H^{e}$ term, we get:

$Y^{e}\leftarrow W_{y\rightarrow 2}^{-1}(Z_{2}^{e}-N(0,\sigma_{2}^{2}))$

Thus, the noise term now adds noise in the features instead of targets as
$\sigma_{y}^{2}$. Similar effects of feature noise has been recently studied
in (Khani & Liang, 2019) where the authors show that it seems to play very
different roles compared to the target variable noise. For simplicity, we omit
the derivation here and directly use the result in linear setting, i.e., if
the noise term $N(0,\sigma_{2}^{2})$ has a covariance matrix whose norm is
significantly larger than $W_{y\rightarrow 2}^{-1}$, then the optimal weight
will tend to zero (i.e. a vector of zeros).

Therefore, although in this paper, we propose to test a larger variety of unit
test cases for the ground truth model, we observe that only a small subset is
sufficient for such testing. For the cases where $W_{y\rightarrow 2}^{-1}$ has
a small covaraince matrix, the model will naturally converge to weights with
smaller magnitudes and thus seem to ignore the spurious features.666We
conducted preliminary experiments where each term in the weight matrix is
sampled form $G(0,1)$ and the results do show that the weights will naturally
tend to zero.

Figure 2: Results comparing IRM and ERM on synthetic datasets under various
settings. The first shows the results under various settings when the Gaussian
is sampled from $G(0,0.1)$ and the second row shows the results under the same
settings when the Gaussian is sampled from $G(0,0.35)$.

###  3.2 Experiments

Based on these observations, we propose to conduct tests on the similar
settings as Ahuja et al. (2020) but with the only difference where we also
consider varying the scale of the ground truth weight matrix $W_{y\rightarrow
2}$ and $W_{1\rightarrow y}$ respectively. In our setting, instead of fixing
the weights, each term in the matrix is always sampled from a Gaussian
distribution; we consider two distributions for the ground truth matrices
which are sampled from $G(0,0.35)$ and $G(0,0.1)$. We believe this is a rather
realistic setting as the ground truth scale can differ mildly for different
real world applications even under normalized features.

We choose these two ground truth settings specifically to test the scale
issue, on $G(0,0.35)$ cases, there is a $~{}70\%$ chance that the each ground
truth regressor term falls in the range of $[0.5,1.5]$. This is similar to the
scale in the original setting. In the $G(0,0.1)$ setting, the sum of weights
tend to shrink to a much smaller number and there is almost zero chance that a
regressor term lies between $[0.5,1.5]$.

###  3.3 Algorithms under consideration and Results

In this paper we restrict our empirical investigations to IRM and ERM under
the settings described above. In this linear setting, we present the ERM
results through both the analytical form777Similar to Arjovsky et al. (2020),
we use an off the shelf scikit learn solver for this. and SGD optimization.
Our empirical observations confirm that under the mild scale change, SGD
optimization are still largely capable of convergence under ERM settings,
achieving the same performance as the analytical solution.

Our main results are shown in Figure 2, we observe that under $G(0,0.35)$
settings, IRM outperforms ERM in all the cases. This is consistent to the
previous work (Arjovsky et al., 2020; Aubin et al., 2021). However, when we
change the samples to have optimal regressor’s weight-norms further away from
1, we obtain markedly opposite results. When the weights are sampled from
$G(0,0.1$, we observe that for all the considered settings, IRM is
outperformed by the simple ERM algorithm.

##  4 Discussion

Our empirical observations show that, when the optimal regressor deviates
mildly from the dummy vector set by the IRM (i.e. a vector where each
dimension is norm 1), IRM seems to find worse solutions than ERM. However,
when the norm is close to the dummy vector, it outperforms ERM. Our
observation might be related to other observations888We point the reader to
https://github.com/reiinakano/invariant-risk-minimization for IRM replication
experiments. showing that IRM is difficult to optimize, and fall easily to
local minimum when $\lambda$ balancing the feature stability term and ERM term
is not well tuned. On the theoretical side, our results might be related to
Kamath et al. (2021) which shows that IRMv1 indeed performs worse than ERM
depending on the ground truth models.

Our observations suggests that a careful analysis with better unit tests is
paramount to better understanding and design of frameworks. A careful setting
in simple and well understood environments can benefit real settings (Koh et
al., 2021). However, we note that in these settings, Koh et al. (2021) show
that current popular methods including IRM and Group DRO (Sagawa et al., 2019;
Hu et al., 2018) do not consistently outperform ERM.

## References

  * Ahuja et al. (2020) Kartik Ahuja, Karthikeyan Shanmugam, and Amit Dhurandhar.  Linear regression games: Convergence guarantees to approximate out-of-distribution solutions, 2020.
  * Arjovsky et al. (2020) Martin Arjovsky, Léon Bottou, Ishaan Gulrajani, and David Lopez-Paz.  Invariant risk minimization, 2020.
  * Aubin et al. (2021) Benjamin Aubin, Agnieszka Słowik, Martin Arjovsky, Leon Bottou, and David Lopez-Paz.  Linear unit-tests for invariance discovery, 2021.
  * Beery et al. (2018) Sara Beery, Grant van Horn, and Pietro Perona.  Recognition in terra incognita, 2018.
  * Hu et al. (2018) Weihua Hu, Gang Niu, Issei Sato, and Masashi Sugiyama.  Does distributionally robust supervised learning give robust classifiers?, 2018.
  * Kamath et al. (2021) Pritish Kamath, Akilesh Tangella, Danica J. Sutherland, and Nathan Srebro.  Does invariant risk minimization capture invariance?, 2021.
  * Khani & Liang (2019) Fereshte Khani and Percy Liang.  Noise induces loss discrepancy across groups for linear regression.  _CoRR_ , abs/1911.09876, 2019.  URL http://arxiv.org/abs/1911.09876.
  * Koh et al. (2021) Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Balsubramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, Tony Lee, Etienne David, Ian Stavness, Wei Guo, Berton A. Earnshaw, Imran S. Haque, Sara Beery, Jure Leskovec, Anshul Kundaje, Emma Pierson, Sergey Levine, Chelsea Finn, and Percy Liang.  Wilds: A benchmark of in-the-wild distribution shifts, 2021.
  * Koyama & Yamaguchi (2021) Masanori Koyama and Shoichiro Yamaguchi.  When is invariance useful in an out-of-distribution generalization problem ?, 2021.
  * Sagawa et al. (2019) Shiori Sagawa, Pang Wei Koh, Tatsunori B. Hashimoto, and Percy Liang.  Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization.  _CoRR_ , abs/1911.08731, 2019.  URL http://arxiv.org/abs/1911.08731.
  * Sturm (2014) Bob L. Sturm.  A simple method to determine if a music information retrieval system is a ”horse”.  _I E E E Transactions on Multimedia_ , 16(6):1636–1644, October 2014.  ISSN 1520-9210.  doi: 10.1109/TMM.2014.2330697.
  * Torralba & Efros (2011) A. Torralba and A. A. Efros.  Unbiased look at dataset bias.  In _Proceedings of the 2011 IEEE Conference on Computer Vision and Pattern Recognition_ , CVPR ’11, pp. 1521–1528, USA, 2011. IEEE Computer Society.  ISBN 9781457703942.  doi: 10.1109/CVPR.2011.5995347.  URL https://doi.org/10.1109/CVPR.2011.5995347.
  * Vapnik (1991) V. Vapnik.  Principles of risk minimization for learning theory.  In _Proceedings of the 4th International Conference on Neural Information Processing Systems_ , NIPS’91, pp. 831–838, San Francisco, CA, USA, 1991. Morgan Kaufmann Publishers Inc.  ISBN 1558602224.