0
$\begingroup$

I asked the following in Math Stack Exchange and was told "You may be more likely to get an answer on stats.stackexchange.com". I figured this is a more suitable place.

In what follows, an axis-aligned rectangle is an element of the set $\mathcal{C}:=\{[l,r]\times [b,t]\in\mathscr{P}(\mathbb{R}^2)\mid l,r,b,t\in \mathbb{R}\}$. This will be our concept class and our hypothesis set, i.e., $\mathcal{H}=\mathcal{C}$.

I'm trying to solve problem 2.6 of Foundations of Machine Learning (Second Edition) by M. Mohri et al which goes as follows.

The Problem.

2.6 Learning in the presence of noise - rectangles. In example 2.4, we showed that the concept class of axis-aligned rectangles is PAC-learnable. Consider now the case where the training points received by the learner are subject to the following noise: points negatively labeled are unaffected by noise but the label of a positive training point is randomly flipped to negative with probability $\eta \in (0,1/2)$. The exact value of the noise rate $\eta$ is not known to the learner but an upper bound $\eta'$ is supplied to him with $\eta\leq \eta'<1/2$. Show that the algorithm returning the tightest rectangle containing positive points can still PAC-learn axis-aligned rectangles in the presence of this noise.

My Attempted Solution.

Let $\mathcal{A}$ be the algorithm described in the problem and $R\in \mathcal{C}$. Let $\varepsilon>0$, $m\in\mathbb{N}$ and $\mathcal{D}$ a distribution over $\mathbb{R}^2\times \{0,1\}$ such that $(X,Y)\sim \mathcal{D}$ where the described property is satisfied for $Y$ (that is, $Y=1$ with probability $1-\eta$ when $X\in R$ and $Y=0$ with probability $\eta$ in the same scenario. $Y=0$ if $X\notin R$). Let $l,r,b,t\in\mathbb{R}$ be such that $R = [l,r]\times [b,t]$.

Let $S:=((X_1,Y_1),\dots, (X_m,Y_m))\sim \mathcal{D}^m$ $i.i.d.$ and $R_S = \mathcal{A}(S)$. If $\mathbb{P}(X\in R)<\varepsilon$, then, since $R_S\subseteq R$, we are done (since the only error can come from $R\setminus R_S \subseteq R$). If not, define $r_1 = [l,s_1]\times [b,t]$ where $s_1=\inf\{s\geq l\mid \mathbb{P}(X\in [l,s]\times [b,t])\geq \varepsilon /4\}$ (so that $r_1$ consists of taking a chunk from the left of $R$). Define $r_2,r_3,r_4$ similarly (taking a chunk from the right, bottom, and top of $R$). If the risk of $R_S$, $\mathcal{R}(R_S):=\mathbb{P}(\mathbb{1}_{R_S}(X)\neq \mathbb{1}_{R}(X))=\mathbb{P}(X\in R_S\triangle R)=\mathbb{P}(X\in R\setminus R_S)$, is greater or equal than $\varepsilon$, then $R_S\cap r_i=\emptyset$ for some $i$ (since $R\setminus R_S\subseteq r_1\cup\dots \cup r_4$ otherwise). Therefore, $$\begin{align} \mathbb{P}(\mathcal{R}(R_S)\geq \varepsilon) &\leq \mathbb{P}\left(\bigcup_{i=1}^4\{R_S\cap r_i=\emptyset\}\right)\\ & \leq \sum_{i=1}^4 \mathbb{P}\left(R_S\cap r_i=\emptyset\right)\\ & \leq \sum_{i=1}^4 \mathbb{P}\left(\lnot (X_1\in r_i\land Y_1=\mathbb{1}_{R}(X)),\dots , \lnot (X_m\in r_i\land Y_m=\mathbb{1}_R(X))\right)\\ & = \sum_{i=1}^4 \mathbb{P}\left(X\notin r_i\lor Y\neq\mathbb{1}_{R}(X)\right)^m\\ \end{align} $$

Using $$\begin{align*} \mathbb{P}\left(X\notin r_i\lor Y\neq\mathbb{1}_{R}(X)\right)&=1-\mathbb{P}\left(X\in r_i, Y=1\right)\\ & =1-\mathbb{P}(Y=1\mid X\in r_i)\mathbb{P}(X\in r_i)\\ & \leq 1-(1-\eta)\varepsilon/4\\ & \leq 1-(1-\eta')\varepsilon/4\\ & \leq \exp(-(1-\eta')\varepsilon/4)\\ \end{align*}$$ it follows that $\sum_{i=1}^4 \mathbb{P}\left(X\notin r_i\lor Y\neq\mathbb{1}_{R}(X)\right)^m\leq 4\exp(-m(1-\eta')\varepsilon/4)$ and thus $\mathbb{P}(\mathcal{R}(R_S)\geq \varepsilon)\leq 4\exp(-m(1-\eta')\varepsilon/4)$. Therefore, setting the RHS smaller than $\delta$, we obtain the sample complexity $$m\geq \frac{4}{(1-\eta')\varepsilon}\log\left(\frac{4}{\delta}\right).$$

My Question.

Is my answer correct? The book states that for the noisy scenario, the correct setting is agnostic PAC-learning, however, the problem asks for PAC-learnability, so I'm not sure if I'm doing what is expected. Furthermore, I've used $\mathcal{R}(R_S)=\mathbb{P}(\mathbf{1}_{R_S}(X)\neq \mathbf{1}_{R}(X))$, should have I used $\mathcal{R}(R_S)=\mathbb{P}(\mathbf{1}_{R_S}(X)\neq Y)$ instead? Why and why not?

Thanks in advance.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .