1
$\begingroup$

In many iterative machine learning algorithms, weight/parameters are initialized as random. But is there any mathematical relationship between the random starting point and initial accuracy?

For example, in Probabilistic PCA the Principal Subspace "W" is initialized as random, which is refined by Expectation maximization algorithm. In my simulation, the initial error is over 300% which reduces to 30% after running one iteration. Upon running multiple iterations, "W" is polished further so that error reaches 0%.

I was wondering if there is any mathematical formula that defines this accuracy of the initial random point. So any help/link to related paper will be much appreciated.

Thanks in advance.

$\endgroup$

1 Answer 1

1
$\begingroup$

If the question is whether there is a way to compute the expected loss $l$, or risk $R(\hat{f})=\mathbb{E}[l(Y, \hat{f}(X))]$ of an estimator $\hat{f}$ picked at random in some hypothesis space $\mathcal{H}$, then this cannot be done since the risk is an expectation over the true distribution of the data which one does not know.

Instead the empirical risk $\hat{R}(f) = \frac{1}{N} \sum_i l(y_i, f(x_i))$ is used as an approximation, i.e. one computes the error over the data. Minimisation of this risk is what most iterative algorithms do. PCA projections can be recast as empirical risk minimisation with squared loss under a linear model, I assume doing the same for PPCA is possible (see Bishop's paper on PPCA). There are many bounds on how well the empirical risk approximates the true risk (so-called generalisation bounds $|R(\hat{f})-\hat{R}(\hat{f})|$).

If the question is whether there are a priori bounds to estimate $\mathbb{E}[\hat{R}(\hat{f})]$ when picking $\hat{f} \in \mathcal{H}$ at random, where this expectation would not be wrt. datasets as is usually the case for the expected empirical risk of an estimator, but wrt. the distribution selecting $\hat{f}$, then I guess some computation is possible for each specific case. E.g. if we take squared loss and $\mathcal{H}$ to be parameterized by $\theta$, and we pick $\theta \sim \Theta$ then by linearity one has to compute

$$\frac{1}{N}\sum_i \mathbb{E}_{\theta \sim \Theta}[(y_i - \hat{f}_{\theta}(x_i))^2]$$

And this might be possible or not depending on the choice of $\mathcal{H}$.

$\endgroup$
2
  • $\begingroup$ is it possible to state how much error reduction is possible after the very first EM iteration for PPCA? Or in general is it possible to give any pessimistic bound on the error after one iteration if started with a random initialization point? $\endgroup$ Commented Dec 28, 2017 at 16:54
  • 1
    $\begingroup$ If you are interested in EM in particular, then this paper might be of interest: "In each case, our theory guarantees that with a suitable initialization, a relatively small number of EM (or gradient EM) steps will yield (with high probability) an estimate that is within statistical error of the MLE." $\endgroup$
    – Miguel
    Commented Dec 28, 2017 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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