5
$\begingroup$

this is my first question here :)

Problem Statement

Let $h \in \mathcal{H}$ be a hypothesis to some class of binary classifiers $\mathcal{H}$. Show that $$\mathbb{E}_{\mathcal{D}_n}\left[R_e(h)\right] = R(h)$$ where the expectation on the LHS is over all possible training datasets $\mathcal{D}_n$ of size $n$.

  1. $R_e(h)$ is the empirical risk of the algorithm over a given dataset $\mathcal{D}_n$. It is defined as

$$R_e(h) = \frac1n\sum_{i=1}^{n}\mathcal{L}(x_i, h(x_i))$$

  1. Here $\mathcal{L}$ is the loss function for the binary classification problem defined as $$\mathcal{L}(x,h) = \begin{cases} 1, & s(x) \not= h(x) \\ 0, & \text{otherwise} \end{cases} $$

  2. $s(x)$ is the system we are trying to model

  3. $R(h)$ is the true risk of the hypothesis $h$

My work

$$R_e(h) = \frac1n\sum_{i=1}^{n}\mathcal{L}(X_i, h(x_i))$$ $$\mathbb{E}_{\mathcal{D}_n}\left[R_e(h)\right] = \int_{\mathcal{D}_n}{R_e(h)p(\mathcal{D}_n)}$$ $$ = \frac{1}{n}\int_{\mathcal{D}_n}{\sum_{x_i \in \mathcal{D}_n}\mathcal{L}(x_i, h)p(\mathcal{D}_n)}$$

Since I want to manipulate this to convert it to $R(h) = \int_{x}{\mathcal{L}(x,h)p(x)dx}$, I though of group all $x_i$ out of the above equation. But then I couldn't find a way to get the term $p(x)$ into the picture and this is where I am stuck.

I am looking for progressive hints that will help me solve this myself. Thanks!

$\endgroup$
  • $\begingroup$ I don't think this is true, actually. The empirical risk for a hypothesis $h$ converges a.s. to its true risk when $n\to\infty$ (Law of Large Numbers), not over training sets of fixed sample size. $\endgroup$ – DeltaIV Sep 3 '18 at 19:33
  • $\begingroup$ @DeltaIV Wouldn't the two be equivalent for i.i.d. data, since the average of the empirical risk over many datasets would be the same as the empirical risk for a giant dataset formed by concatenating the smaller ones? $\endgroup$ – user20160 Sep 4 '18 at 0:29
  • $\begingroup$ @user20160 yes, it would. I thought of it when in my bed. I see you beat me to it :-) $\endgroup$ – DeltaIV Sep 4 '18 at 7:16
  • $\begingroup$ @DeltaIV it's nice talking w/ people who like to think about these things at all hours of the day (or night as the case may be :) $\endgroup$ – user20160 Sep 4 '18 at 9:23
  • $\begingroup$ @user20160 😂actually, I am careful not to do that at all, usually! But today I'm really sick, so I had a long and sleepless night, and I thought of the weirdest things 🙂Also, the question is objectively quite interesting. It made me think of an interesting connection between two different limits often used in Statistical Learning Theory. I'll probably write an answer later. $\endgroup$ – DeltaIV Sep 4 '18 at 10:15
2
+50
$\begingroup$

Suppose the dataset is $\mathcal{D} = \{X_1, \dots, X_n\}$ where each data point $X_i$ is drawn i.i.d. from some distribution $f_X$. The true risk is:

$$R(h) = E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

Show that $E_{\mathcal{D}_n}[R_e(h)] = R(h)$

  1. Start with the LHS:

$$E_{\mathcal{D}_n}[R_e(h)]$$

  1. Plug in the expression for the empirical risk $R_e(h)$:

$$= E_{\mathcal{D}_n} \left [ \frac{1}{n} \sum_{i=1}^n \mathcal{L}(X_i, h(X_i)) \right ]$$

  1. By linearity of expectation:

$$= \frac{1}{n} \sum_{i=1}^n E_{\mathcal{D}_n}[\mathcal{L}(X_i, h(X_i))]$$

  1. Because $\mathcal{L}(X_i, h(X_i))$ only depends on $X_i$, the joint expectation (over datasets) is equal to the marginal expectation (over data point $X_i$):

$$= \frac{1}{n} \sum_{i=1}^n E_{X_i}[\mathcal{L}(X_i, h(X_i))]$$

  1. The expected value is the same for all $X_i$ because they're identically distributed. So, we can replace $X_i$ with a generic variable $X$ drawn from the same distribution $f_X$:

$$= \frac{1}{n} \sum_{i=1}^n E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

  1. Simplify:

$$= E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

This is equal to the true risk $R(h)$.


Alternative

Here's an equivalent way of proceeding, starting after step (3) above.

Explicitly write out the expected value over datasets. Because the data points are independent, the joint distribution of the dataset is equal to the product of the marginal distributions of the data points.

$$= \frac{1}{n} \sum_{i=1}^n \int \cdots \int \left ( \prod_{j=1}^n f_X(x_j) \right ) \mathcal{L}(x_i, h(x_i)) \ dx_1 \cdots dx_n$$

Reorder the integrals (see Fubini's theorem) and pull terms involving $x_i$ to the outside:

$$= \frac{1}{n} \sum_{i=1}^n \int f_X(x_i) \mathcal{L}(x_i, h(x_i)) \left [ \int \cdots \int \left ( \prod_{j \ne i} f_X(x_j) \right ) \ dx_1 \cdots dx_{i-1} \ dx_{i+1} \cdots dx_n \right ] dx_i$$

The expression inside the brackets is simply integrating a distribution, so it's equal to one:

$$= \frac{1}{n} \sum_{i=1}^n \int f_X(x_i) \mathcal{L}(x_i, h(x_i)) dx_i$$

The integral is the expected value of $\mathcal{L}(\cdots)$ with respect to $f_X$:

$$= \frac{1}{n} \sum_{i=1}^n E_{X \sim f_X}[\mathcal{L}(X, h(X))]$$

This is the same as the result of step (5) above, so proceed to (6).

$\endgroup$
2
$\begingroup$

It's actually an immediate consequence of the fact that $R_e(h)$ is a Monte Carlo estimator for $R(h)$ (for fixed h). This is evident if, instead of the terrible notation often used in some introductory books to Machine Learning, where "datasets" are considered, we more properly consider a random vector $\mathbf{X}$ whose $n$ components are iid. The random vector has a probability distribution

$$p(\mathbf{X})=p(X_1,\dots,X_n)$$

Now, obviously $R_e(h(X_1),\dots,h(X_n))=f(\mathbf{X})$ is a random variable and we really want to compute its expectation:

$$\mathbb{E}_{\mathbf{X}\sim p(\mathbf{X})}[R_e(h)]$$

But this is immediate if we just notice that

$$f(\mathbf{X})=\frac{1}{n} \sum_{i=1}^n \mathcal{L}(X_i, h(X_i))=\frac{1}{n} \sum_{i=1}^n g(X_i)=\frac{1}{n} \sum_{i=1}^n Y_i$$

is nothing more than the Monte Carlo estimator for the mean of $Y=g(X)$, a random variable whose mean is nothing more than the true risk. Proof: all $Y_i$ are iid and we have

$$\mathbb{E}[Y]=\mathbb{E}_{X\sim p(X)}[g(X)]=\mathbb{E}_{X\sim p(X)}[\mathcal{L}(X, h(X))]=R(h)$$

Now, the Monte Carlo estimator has many interesting properties, but we only need two (actually one, but thanks to the second one I'll also show you an interesting property of Empirical Risk, you didn't ask about):

  1. it is an unbiased estimator of true risk, i.e., its mean is equal to the mean of $Y$. As a matter of fact,

$$\mathbb{E}_{\mathbf{X}\sim p(\mathbf{X})}[R_e(h(X_1),\dots,h(X_n))]=\mathbb{E}[Y]=R(h)$$

  1. it is a consistent estimator of true risk, i.e., the Monte Carlo estimator converges a.s. to the mean of $Y$ for the sample size $n\to\infty$. In other words

$$R_e(h)\overset{a.s.}\to R(h) \ \text{as} \ n\to\infty$$

$\endgroup$
  • 1
    $\begingroup$ nice, hope you feel better soon $\endgroup$ – user20160 Sep 4 '18 at 12:36

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.