New answers tagged

0

The VC-dim seems to be finite for $X = N$ (thus is PAC-learnable). So what about for $X = R$? It feels like the VC-dim is still the same in that case, so can we assume it's still PAC-learnable right?


0

The VC-dimension of a hypothesis class $\mathcal{H}$ is the maximal size of a set shattered by $\mathcal{H}$, if such a maximal size exists, and $\infty$ otherwise. Therefore to prove that the VC-dimension of $\mathcal{H}$ is $d < \infty$, you need to show that $\mathcal{H}$ shatters some set of size $d$, but no set of size $d+1$.


1

Every finite hypothesis class $\mathcal{H}$ is PAC-learnable. Indeed, $VCdim(\mathcal{H})\le |\mathcal{H}|<\infty$ (one can even create a more strict bound, but this is irrelevant for now). Hence, $\mathcal{H}$ is PAC-learnable. Infinite classes however, can either be PAC-learnable or not. Being a countable, or an uncountable class does not matter here. ...


0

I'm not sure when you mean that the VC dimension of a singleton is 0? I have always thought it was 1. How I think about it is that given some $H$ of classifiers, I will pick any one point in the domain space $\mathcal{X} = \mathbb{R}$. Then an adversary will have to label it whichever way he wants. And if one of my classifiers in $H$ is able to classify ...


1

First, let's see what a learning algorithm looks like. It takes as input samples $(x_1,y_1),\ldots,(x_m,y_m)$, where $x_i \in X$ and $y_i \in \{0,1\}$, with the promise that $y_i = h(x_i)$ for some $h \in H_{\mathit{sing}}$. It should output some $h' \in H_{\mathit{sing}}$. Second, let's see when a learning algorithm is successful, according to the ...


2

What the backpropagation is computing, is the derivative (gradient) of that final output with respect to each neuron and each weight in the metwork. This isn't a problem! You can think of it as computing the derivative of $f(g(x;w_1);w_2)$, once with respect to $w_2$, and once with respect for $w_1$. Do note that $f$ and $g$ would be very simple functions ...


1

Backpropagation computes the gradient of the loss function (with respect to the weights). Then, the weights are updated using this gradient. There are many tutorials on how back propagation works. Note that supervised learning assumes all training set instances are labelled, so we do know what the real answer is for each sample in the training set; the ...


Top 50 recent answers are included