1
$\begingroup$

If we have a neural network that learns the generative model for P(A, B, C)

And now, we want to learn the generative model for P(A, B, C, D)

Is there any theory that says learning P(A,B,C) and then composing it with P(D | A,B,C) is faster than learning P(A,B,C,D) from scratch?

$\endgroup$
1
$\begingroup$

Probably not. Here is a possible "counterexample".

Let $P(D)$ be some distribution over fixed-length strings which is not too difficult to model.

Now let $P(A, B, C|D) = I(A,D)I(B,D+1)I(C,D+2)$, where $I(x,y)$ is 1 if $\text{hash}(y) = x$ and otherwise 0. Also fix the output of $\text{hash}$ to be much longer than the input, so the probability of any collision is low. And assume $\text{hash}$ has all the standard cryptographic properties such as pre-image resistance, etc.

Given a decent model of $P(D)$, sampling the joint distribution $P(A,B,C,D)$ is easy. Obtaining an explicit density model is also not hard, since $P(A = x|\text{hash}(D) \neq x) \approx 0$, etc.

On the other hand, modeling $P(A, B, C)$ is much harder, since the output of the hash function will look essentially random. Modeling $P(D|A,B,C)$ is equivalent to trying to break pre-image resistance, which is also virtually impossible.

$\endgroup$
  • $\begingroup$ What is the purpose of the hash function? $\endgroup$ – user3180 May 5 '19 at 7:17
  • $\begingroup$ Why is the RHS of P(A,B,C|D) even considered a pdf? $\endgroup$ – user3180 May 5 '19 at 7:17
  • $\begingroup$ What theory do we have for compositionality and transfer learning? $\endgroup$ – user3180 May 5 '19 at 7:18
  • $\begingroup$ @user3180 i am demonstrating that it can be much more difficult to model the conditional rather than the joint in some cases. the hash function is used to construct such a pathological case $\endgroup$ – shimao May 5 '19 at 17:41
0
$\begingroup$

It's hard to say in general. P(A,B,C,D) has 4 variables so naturally its harder than learning P(A,B,C), but if you already have P(A,B,C), and need P(D|A,B,C), well running a linear regression to get P(D|A,B,C) is probably gonna be quicker than doing P(A,B,C,D) though a neural network, OTOH, if you did P(D|A,B,C), it might have a lot of singularities and other nasties that make it heard to learn the function. This is why in the EM algorithm they work with P(A,B) rather than P(A|B).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.