




\subsection{Interleaved input Transformers}

The DEformer is directly inspired by \texttt{baller2vec++}{} \cite{alcorn2021baller2vecplusplus}, a multi-agent spatiotemporal Transformer that used an identical interleaved input design to model the behaviors of coordinated agents.
Our key contribution is recognizing that this interleaved architecture design can be applied to OADE.
The DEformer is architecturally similar to the independently developed XLNet language model \cite{yang2019xlnet}.
Compared to XLNet, the DEformer:

\begin{enumerate}
    \item encodes feature identity by including it as an input to the network (instead of using positional embeddings) and
    \item uses a full lower triangular attention mask to attend to \textit{both} identity feature vectors and identity/value feature vectors that occur earlier in the shuffled input (instead of only attending to the ``content stream'').
\end{enumerate}

\noindent
Notably, XLNet was trained to only predict the final six tokens of a shuffled sentence because the authors observed ``slow convergence in preliminary experiments''.
The DEformer was capable of modeling the values for all 784 pixels in our binarized-MNIST experiments.

\subsection{DeepNADE}

One important way DeepNADE \cite{uria2014deep, uria2016neural} and the DEformer differ is in the size of the outputs for their final classification layers, which are $DC$ and $C$, respectively.
While this difference is not particularly important for a relatively simple dataset like binarized-MNIST, for more complex datasets like CIFAR-10 \cite{krizhevsky2009learning}, these contrasting designs produce dramatically different parameter counts.
Specifically, the size of the output for a CIFAR-10 DeepNADE model would be $32 \times 32 \times 3 \times 256 =$ 786,432 (because each pixel has three channels, and each channel can take on one of 256 different integer values).
Therefore, if the input dimension to the final layer was 500 (as it was in the DeepNADE model for binarized-MNIST), the final layer alone would have 500 $ \times $ 786,432 + 786,432 $ = $ 394,002,432 parameters.
While the number of outputs can be reduced for image datasets by using a discretized logistic mixture likelihood \cite{Salimans2017PixeCNN}, this strategy restricts the complexity of the model, and the discretized logistic mixture likelihood is not applicable to datasets where the labels do not have a clear underlying order.

On the other hand, due to the attention mechanism, the DEformer suffers from the same quadratic complexity problem known to plague Transformers.
However, recent work in sparse Transformers (e.g., \cite{child2019generating, NEURIPS2020_c8512d14, beltagy2020longformer, Kitaev2020Reformer:}) may allow the DEformer to scale to larger inputs.

When training DeepNADE, a mask is randomly generated for each sample by: (1) randomly selecting an integer $c \in \{0, \dots, D - 1\}$ to serve as the number of conditioning variables and (2) randomly assigning a value of one to $c$ locations in the mask and assigning a value of zero to the remaining locations.
The loss for each sample is then:

\[
    \mathcal{L} = \frac{D}{D - c} \sum_{d=1}^{D} (1 - m_{d}) (-\ln{}(f(\hat{\textbf{x}}, \textbf{m})_{(d - 1)C + l_{d}}))
\]

\noindent
where $l_{d}$ is the label for the $d$-th feature of $\textbf{x}$, and $\frac{D}{D - c}$ is a scaling factor ensuring the loss for each sample is an unbiased estimator (which is necessary because the error signal is only computed for $D - c$ features of the sample due to the $1 - m_{d}$ term).
In contrast, for the DEformer, there is always an error signal for all of the features of each sample.
While MADE \cite{germain2015made} also produces an error signal for all of the features of each sample, the authors observed that sampling many different weight masks led to the model underfitting, so it is unclear how well MADE can perform fully OADE.

\subsection{Spatial inputs as feature identities}

A number of neural network architectures operate directly on spatial coordinates, which can be interpreted as feature identities in their various contexts (e.g., images \cite{ha2016generating}, point clouds \cite{pointcloudsurvey}, and 3D scenes \cite{sitzmann2019srns}).
Additionally, \citet{liu2018coord} observed that adding channels to feature maps that contain the spatial coordinates of the pixels greatly improved the performance of convolutional neural networks on certain spatial reasoning tasks.
However, none of these models are performing autoregressive distribution estimation, nor do they employ the interleaved input design of the DEformer.

\section{Introduction}
\input{Introduction}

\section{Architecture}
\input{Architecture}

\section{Experiments}
\input{Experiments}

\section{Results}
\input{Results}

\section{Related Work}
\input{Related}

\section{Conclusion}
\input{Conclusion}

\section*{Author Contributions}
MAA conceived and implemented the architecture, designed and ran the experiments, and wrote the manuscript.
AN partially funded MAA and provided the GPUs for the experiments.

\section*{Acknowledgements}
We would like to thank Iain Murray and Rasool Fakoor for their helpful feedback.

