Autoregressive models for modeling conditional probabilities

Question

I'm reading Tomczak's Deep Generative Modeling. When the author discusses auto-regressive models, he mentions that we model the probability distribution $p(\mathbf{x})$ of the data $\mathbf{x}$ as $$p(\mathbf{x}) = p(x_1)\prod_{d=2}^Dp(x_d|\mathbf{x}_{<d})$$where $D$ is the feature dimension (e.g number of pixels in an image) and $\mathbf{x}_{<d} = [x_1, x_2, ..., x_{d-1}]$. He then mentions that we can simplify this model by assuming "finite memory," i.e $p(x_d|\mathbf{x}_{<d}) = p(x_d|x_{d-1}, x_{d-2})$, where we assume that $x_d$ only depends on the values of the previous two features. Finally, he explains that in practice, we could model this as the following MLP (let's assume we're dealing with images and pixels): $$[x_{d-1}, x_{d-2}] \rightarrow \text{Linear(2, M)} \rightarrow \text{ReLU} \rightarrow \text{Linear}(M, 256) \rightarrow \text{softmax} \rightarrow \theta_d$$ where $M$ is the hidden dimension and $\theta_d$ is the probability distribution for pixel $d$ across the 256 possible values. My question is about the training process of such a model. Wouldn't you need to train this model "pixel by pixel" since making predictions for the next pixel depends on the values of the previous two, and so it would be quite an inefficient model?

Answer 1

This depends on your definition of inefficient. It’s linear in the number of pixels, but not parallelizable.

This is how language modeling was done for decades, though.

Answer 2

What do you mean it would have to be trained "pixel by pixel"? Since the objective is a sum of terms of the form $\log p(x_d|x_{d-1},x_{d-2})$, you can evaluate it by splitting up the input into a "batch" of tuple of the form $(x_{d-2},x_{d-1},x_d)$ and evaluating each corresponding term in the loss in parallel.