4

Recall that the final hypothesis after $T$ rounds is $h_T(x)=sign\left(\sum\limits_{i=1}^T \alpha_t h_t(x)\right)$, i.e. $\alpha_t$ is the weight of $h_t$ in $h_T$. If $\epsilon_t$ is high (near one) you want to answer the opposite of $h_t$, so you want $\alpha_t$ to be negative and very large in absolute value. If on the other hand $\epsilon_t$ is very low ...


3

Håstad gave an even better example in his paper On the Size of Weights for Threshold Gates, which requires super exponential weights. A simple example which requires exponential weights is the function $\sum_i 2^i (x_i - y_i) \geq 0$ or variants.


2

It's hard to answer what you "need", as that depends on your purpose, and hard to answer this question concretely, as it is very broad. I recommend you focus on learning concepts and ideas, as these are more likely to be of lasting use. Sometimes, though, to understand how some interesting capability is achieved, you will need to understand the ...


2

This answer (as, I presume, the question) uses the notation of the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David. Suppose our domain set is $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such ...


2

The VC-dimension of your hypothesis class $\mathcal H$ is 2. To see this, we begin by showing that $\mathcal H$ shatters any 2-element set $\{(a_1 a_2), (b_1, b_2)\}$ of real numbers where all components of the pairs are positive: $\emptyset$ is accounted for by $f_{c, c + \varepsilon}$ for any real $c$ such that $ca_1 \neq a_a$ and $cb_1 \neq b_2$ and some ...


1

Generally, every class of finite VC dimension admits to a (exponential size in the dimension) compression scheme. This was an open question resolved a few years ago by Shay and Amir in this paper. However, this is an overkill for your question, since $H_k$ obviously has a $k$-comprresion scheme (only keep the samples labeled $1$, of which there are at most $...


1

Suppose that $H$ shatters a set $S$ of size $\ell$, and has a compression scheme of size $k$. For each of the $2^\ell$ labelings of $S$, the compression scheme associates a labeled subset of size $k$, in an injective way. There are $2^k \binom{\ell}{k}$ such labeled subsets, and so $2^\ell \leq 2^k \binom{\ell}{k}$. Using $\binom{\ell}{k} \leq (e\ell/k)^k$, ...


1

The density $p_R$ of the uniform distribution over a rectangle $R$ is given by $p_R(x) = 0$ if $x \notin R$, and $p_R(x) = 1/\mathit{area}(R)$ otherwise. Indeed, up to scaling the distribution must have this form, and the choice $1/\mathit{area}(R)$ ensures that $p_R$ is a distribution. In your case, you have a mixture of two such distributions: with ...


Only top voted, non community-wiki answers of a minimum length are eligible