View Single Post
Old 04-01-2016, 06:32 AM
MaciekLeks MaciekLeks is offline
Join Date: Jan 2016
Location: Katowice, Upper Silesia, Poland
Posts: 17
Default Re: Problem 1.10 (b)

IMHO, the answer to (b) is not an infinite number. As for part (a) the anwer is not \frac{1}{2}, so here the anwer is not as simple as it seems.

My way of thinking is as follows:
We must recall that the assumption from (a) does not work here, and we still do not know function f. We also do not know the dimensionality of the datapoint in the input space \mathcal{X}=\{\mathbf{x}_{1,}\mathbf{x}_{2},...,\mathbf{x}_{N},\mathbf{x}_{N+1},...,\mathbf{x}_{N+M}\} but we know that this input space is fixed (all \mathbf{x}_{k} for 1\leq k\leq N+M are already set). In this case we have \mathcal{D} of size N generated in a deterministic way, and y_{n}=f(\mathbf{x}_{n})(1\leq n\leq N) is not affected by any noise. So, how many possible f:\mathcal{X}\mathcal{\rightarrow\mathcal{Y}} can 'generate' \mathcal{D}? The subtle point in this case is the assumption: “For a fixed \mathcal{D} of size N”, which means that \mathcal{D}=\{(\mathbf{x}_{1},y_{1}),(\mathbf{x}_{2},y_{2}),...,(\mathbf{x}_{N},y_{n})\} is already generated. We can calculate how many possible outputs y_{n} for 1\leq n\leq N we can get? Only 1. But there are remaining \{\mathbf{x}_{N+1},...,\mathbf{x}_{N+M}\} datapoints for which we can have 2^{M} possible values \{-1,1\}. So, the anwer is 2^{M}.

Am I wrong?
Reply With Quote