# Can a model of P(Y|X) be trained via stochastic gradient descent from non-i.i.d. samples of P(X) and i.i.d. samples of P(Y|X)?

When training a parameterized model (e.g. to maximize likelihood) via stochastic gradient descent on some data set, it is commonly assumed that the training samples are drawn i.i.d. from the training data distribution. So if the goal is to model a joint distribution $P(X,Y)$, then each training sample $(x_i,y_i)$ should be drawn i.i.d. from that distribution.

If the goal is instead to model a conditional distribution $P(Y|X)$, then how does the i.i.d. requirement change, if at all?

1. Must we still draw each sample $(x_i,y_i)$ i.i.d. from the joint distribution?
2. Should we draw $x_i$ i.i.d. from $P(X)$, then draw $y_i$ i.i.d. from $P(Y|X)$?
3. Can we draw $x_i$ not i.i.d. from $P(X)$ (e.g. correlated over time), then draw $y_i$ i.i.d. from $P(Y|X)$?

Can you comment on the validity of these three approaches for stochastic gradient descent? (Or help me rephrase the question if necessary.)

I would like to do #3 if possible. My application is in reinforcement learning, where I'm using a parameterized conditional model as a control policy. The sequence of states $x_i$ is highly correlated, but the actions $y_i$ are sampled i.i.d. from a stochastic policy conditioned on the state. The resulting samples $(x_i,y_i)$ (or a subset of them) are used to train the policy. (In other words, imagine running a control policy for a long time in some environment, gathering a data set of state/action samples. Then even though the states are correlated over time, the actions are generated independently, conditioned on the state.) This is somewhat similar to the situation in this paper.

I found a paper, Ryabko, 2006, "Pattern Recognition for Conditionally Independent Data," which at first seemed relevant; however, there the situation is reversed from what I need, where $y_i$ (the label/category/action) can be draw not i.i.d from $P(Y)$, and $x_i$ (the object/pattern/state) is drawn i.i.d. from $P(X|Y)$.

Update: Two papers (here and here) mentioned in the Ryabko paper seem relevant here. They assume the $x_i$ come from an arbitrary process (e.g. not iid, possibly nonstationary). They show that nearest-neighbor and kernel estimators are consistent in this case. But I'm more interested in whether estimation based on stochastic gradient descent is valid in this situation.

-
 Maybe I'm missing something, and I haven't read the paper, but: you're drawing $x_i$ non-iid from $P(X)$ and then sampling $y_i$ iid from $P(Y \mid X)$. Ryabko (2006) is drawing $y_i$ non-iid from $P(Y)$ and then sampling $x_i$ iid from $P(X \mid Y)$. These seem the same up to renaming. Is there something fundamentally different about the objects $x$ and $y$ that makes this not the same situation? – Dougal Apr 20 at 4:33 @Dougal: The difference is that conditional distribution models, like conditional random fields, treat $X$ and $Y$ (the "inputs" and "outputs") differently... they model only one direction ($P(Y|X)$ but not $P(X|Y)$). – Tyler Streeter Apr 20 at 14:01

 So are you saying that with approach #3, I would get an unbiased result with potentially high variance? – Tyler Streeter Aug 21 '12 at 20:06 If there is no data at or near a point x$_1$ then you can't even estimate P(Y|X=x$_1$) and if there are only a few points the variance of the estimate will be large. – Michael Chernick Aug 21 '12 at 20:53 Yes, that makes sense that the variance could be large. I guess my main concern is whether the estimated P(Y|X) will be biased. – Tyler Streeter Aug 21 '12 at 20:56 We didn't discuss a point estimate. If you have unbiased estimates for P(X), P(Y) and P(X|Y) and plug them into the formula P(Y|X)= P(X|Y) P(Y)/P(X) you will get a biased estimate. – Michael Chernick Aug 21 '12 at 21:11 I should emphasize that I'm talking about estimating P(Y|X) via stochastic gradient descent, in which case the order of the training samples can influence how fast or whether it converges to the correct model. I'm not just using sample averages, where the order of the samples doesn't matter. – Tyler Streeter Aug 21 '12 at 22:45