<commit_before>\documentclass[11pt]{article}

\usepackage{mathtools}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage[margin=0.5in]{geometry}
\usepackage{graphicx}

\everymath{\displaystyle}
\setlength\parindent{0pt}

\begin{document}
\title{Stanford CS 229, Public Course, Problem Set 3}
\date{\today}
\author{<NAME>}
\maketitle 

% custom commands
\newcommand{\hhat}[1][]{\hat{h}_#1}
\newcommand{\CvtError}[0]{\hat{\varepsilon}_{S_{cv}}}
\newcommand{\GError}[0]{\varepsilon}

\section*{1}

\subsection*{a)}
By the Hoeffding inequality, we know that \\

$P(|\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma) \le 2\exp(-2 \gamma^2 \beta m) $ \\

Let $A_i$ denote the event that $|\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma$. Then \\
\begin{align*}
    P(\exists \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma) 
        &= P(A_1 \cup ... \cup A_k) \\
        &\le \sum_k P(A_i) \\
        &\le \sum_k 2\exp(-2 \gamma^2 \beta m) \\
        &= 2k \exp(-2 \gamma^2 \beta m)
\end{align*}
Therefore, \begin{align*}
    &P(\neg \exists \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma) \\
    &= P(\forall \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| \le \gamma) \\
    &\geq 1 - 2k\exp(-2 \gamma^2 \beta m)
\end{align*}
Let $\frac{\delta}{2} = 2k\exp(-2 \gamma^2 \beta m)$. Then
\begin{align*}
                          \frac{\delta}{4k} &= \exp(-2 \gamma^2 \beta m) \\
                          \frac{4k}{\delta} &= \exp(2 \gamma^2 \beta m) \\
                     \log \frac{4k}{\delta} &= 2 \gamma^2 \beta m \\
 \frac{1}{2 \beta m} \log \frac{4k}{\delta} &= \gamma^2 \\
                                     \gamma &= \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}}
\end{align*}
Therefore,

$P\Bigg(\forall \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| \le \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}}\Bigg) \geq 1 - \frac{\delta}{2}$

\subsection*{b)}

From part (a), we have that 

$P(|\GError(\hhat{i}) - \CvtError(\hhat{i})| \le \gamma) \geq 1 - \frac{\delta}{2}$, where $\gamma = \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}}$

Because $\hhat{} \in \{\hhat{1}...\hhat{k}\}$

$P(|\GError(\hhat{}) - \CvtError(\hhat{})| \le \gamma) \geq 1 - \frac{\delta}{2}$ \\

Let $h^* = \arg \min_{\hhat{i} \in \{\hhat{1}...\hhat{k}\}} \GError(\hhat{i})$

Then with probability at least $1 - \frac{\delta}{2}$ \begin{align*}
    \GError(\hhat{}) &\le \CvtError(\hhat{}) + \gamma \\
                     &\le \CvtError(h^*) + \gamma & \text{By the definition of $\hhat{}$ it has the lowest $\CvtError$ of any $\hhat{i} \in \{\hhat{1}...\hhat{k}\}$} \\
                     &\le \GError(h^*) + 2 \gamma & \text{By the uniform convergence result proved in part (a)} \\
                     &= \min_{i=1,...,k} \GError(\hhat{i}) + 2 \gamma & \text{By the definition of $h^*$} \\
                     &= \min_{i=1,...,k} \GError(\hhat{i}) + 2 \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}} \\
                     &= \min_{i=1,...,k} \GError(\hhat{i}) + \sqrt{\frac{2}{\beta m} \log \frac{4k}{\delta}} \\
\end{align*}

\subsection*{c)}

\section*{2}

\setlength\unitlength{2pt}

\subsection*{a)}

$h(x) = 1\{a < x\},\quad a \in \mathbb{R}$

$h(x)$ can shatter a set of 1 point:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(24,0){a}
    \put(25,5){\line(0,1){10}}
    \put(50,10){\circle*{3}}
\end{picture}
\begin{picture}(100,20)(-50,0)
    \put(0,10){\line(1,0){100}}
    \put(50,10){\circle{3}}
    \put(74,0){a}
    \put(75,5){\line(0,1){10}}
\end{picture}

$h(x)$ cannot shatter any set of 2 points because in the labeling situation shown below, no choice of $a$ will successfully label both the points:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(25,10){\circle*{3}}
    \put(75,10){\circle{3}}
\end{picture}

Therefore $VC(h(x)) = 1$

\subsection*{b)}

$h(x) = 1\{a < x < b\}, \quad a,b \in \mathbb{R}$

$h(x)$ can shatter a set of 2 points:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(9,0){a}
    \put(10,5){\line(0,1){10}}
    \put(25,10){\circle*{3}}
    \put(75,10){\circle*{3}}
    \put(89,0){b}
    \put(90,5){\line(0,1){10}}
\end{picture}
\begin{picture}(100,20)(-50,0)
    \put(0,10){\line(1,0){100}}
    \put(0,0){a}
    \put(1,5){\line(0,1){10}}
    \put(9,0){b}
    \put(10,5){\line(0,1){10}}
    \put(25,10){\circle{3}}
    \put(75,10){\circle{3}}
\end{picture}
\\
\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(9,0){a}
    \put(10,5){\line(0,1){10}}
    \put(25,10){\circle*{3}}
    \put(75,10){\circle{3}}
    \put(49,0){b}
    \put(50,5){\line(0,1){10}}
\end{picture}
\begin{picture}(100,20)(-50,0)
    \put(0,10){\line(1,0){100}}
    \put(25,10){\circle{3}}
    \put(49,0){a}
    \put(50,5){\line(0,1){10}}
    \put(75,10){\circle*{3}}
    \put(89,0){b}
    \put(90,5){\line(0,1){10}}
\end{picture}

$h(x)$ cannot shatter any set of 3 points because in the labeling situation shown below, no choice of $a$ and $b$ will successfully label all the points:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(25,10){\circle*{3}}
    \put(50,10){\circle{3}}
    \put(75,10){\circle*{3}}
\end{picture}

Therefore, $VC(h(x)) = 2$

\end{document}<commit_msg>Added parts c and d of problem 2.<commit_after>\documentclass[11pt]{article}

\usepackage{mathtools}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage[margin=0.5in]{geometry}
\usepackage{graphicx}

\everymath{\displaystyle}
\setlength\parindent{0pt}

\begin{document}
\title{Stanford CS 229, Public Course, Problem Set 3}
\date{\today}
\author{<NAME>}
\maketitle 

% custom commands
\newcommand{\hhat}[1][]{\hat{h}_#1}
\newcommand{\CvtError}[0]{\hat{\varepsilon}_{S_{cv}}}
\newcommand{\GError}[0]{\varepsilon}

\section*{1}

\subsection*{a)}
By the Hoeffding inequality, we know that \\

$P(|\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma) \le 2\exp(-2 \gamma^2 \beta m) $ \\

Let $A_i$ denote the event that $|\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma$. Then \\
\begin{align*}
    P(\exists \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma) 
        &= P(A_1 \cup ... \cup A_k) \\
        &\le \sum_k P(A_i) \\
        &\le \sum_k 2\exp(-2 \gamma^2 \beta m) \\
        &= 2k \exp(-2 \gamma^2 \beta m)
\end{align*}
Therefore, \begin{align*}
    &P(\neg \exists \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| > \gamma) \\
    &= P(\forall \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| \le \gamma) \\
    &\geq 1 - 2k\exp(-2 \gamma^2 \beta m)
\end{align*}
Let $\frac{\delta}{2} = 2k\exp(-2 \gamma^2 \beta m)$. Then
\begin{align*}
                          \frac{\delta}{4k} &= \exp(-2 \gamma^2 \beta m) \\
                          \frac{4k}{\delta} &= \exp(2 \gamma^2 \beta m) \\
                     \log \frac{4k}{\delta} &= 2 \gamma^2 \beta m \\
 \frac{1}{2 \beta m} \log \frac{4k}{\delta} &= \gamma^2 \\
                                     \gamma &= \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}}
\end{align*}
Therefore,

$P\Bigg(\forall \hhat{i} \in \{\hhat{1}...\hhat{k}\}. |\GError(\hhat{i}) - \CvtError(\hhat{i})| \le \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}}\Bigg) \geq 1 - \frac{\delta}{2}$

\subsection*{b)}

From part (a), we have that 

$P(|\GError(\hhat{i}) - \CvtError(\hhat{i})| \le \gamma) \geq 1 - \frac{\delta}{2}$, where $\gamma = \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}}$

Because $\hhat{} \in \{\hhat{1}...\hhat{k}\}$

$P(|\GError(\hhat{}) - \CvtError(\hhat{})| \le \gamma) \geq 1 - \frac{\delta}{2}$ \\

Let $h^* = \arg \min_{\hhat{i} \in \{\hhat{1}...\hhat{k}\}} \GError(\hhat{i})$

Then with probability at least $1 - \frac{\delta}{2}$ \begin{align*}
    \GError(\hhat{}) &\le \CvtError(\hhat{}) + \gamma \\
                     &\le \CvtError(h^*) + \gamma & \text{By the definition of $\hhat{}$ it has the lowest $\CvtError$ of any $\hhat{i} \in \{\hhat{1}...\hhat{k}\}$} \\
                     &\le \GError(h^*) + 2 \gamma & \text{By the uniform convergence result proved in part (a)} \\
                     &= \min_{i=1,...,k} \GError(\hhat{i}) + 2 \gamma & \text{By the definition of $h^*$} \\
                     &= \min_{i=1,...,k} \GError(\hhat{i}) + 2 \sqrt{\frac{1}{2 \beta m} \log \frac{4k}{\delta}} \\
                     &= \min_{i=1,...,k} \GError(\hhat{i}) + \sqrt{\frac{2}{\beta m} \log \frac{4k}{\delta}} \\
\end{align*}

\subsection*{c)}

\section*{2}

\setlength\unitlength{2pt}

\subsection*{a)}

$h(x) = 1\{a < x\},\quad a \in \mathbb{R}$ \\

$h(x)$ can shatter a set of 1 point:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(24,0){a}
    \put(25,5){\line(0,1){10}}
    \put(50,10){\circle*{3}}
\end{picture}
\begin{picture}(100,20)(-50,0)
    \put(0,10){\line(1,0){100}}
    \put(50,10){\circle{3}}
    \put(74,0){a}
    \put(75,5){\line(0,1){10}}
\end{picture}

There is no set of 2 points that $h(x)$ can shatter because in the labeling situation shown below, no choice of $a$ will successfully label both the points:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(25,10){\circle*{3}}
    \put(75,10){\circle{3}}
\end{picture}

Therefore $VC(h(x)) = 1$

\subsection*{b)}

$h(x) = 1\{a < x < b\}, \quad a,b \in \mathbb{R}$ \\

$h(x)$ can shatter a set of 2 points:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(9,0){a}
    \put(10,5){\line(0,1){10}}
    \put(25,10){\circle*{3}}
    \put(75,10){\circle*{3}}
    \put(89,0){b}
    \put(90,5){\line(0,1){10}}
\end{picture}
\begin{picture}(100,20)(-50,0)
    \put(0,10){\line(1,0){100}}
    \put(0,0){a}
    \put(1,5){\line(0,1){10}}
    \put(9,0){b}
    \put(10,5){\line(0,1){10}}
    \put(25,10){\circle{3}}
    \put(75,10){\circle{3}}
\end{picture}
\\
\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(9,0){a}
    \put(10,5){\line(0,1){10}}
    \put(25,10){\circle*{3}}
    \put(75,10){\circle{3}}
    \put(49,0){b}
    \put(50,5){\line(0,1){10}}
\end{picture}
\begin{picture}(100,20)(-50,0)
    \put(0,10){\line(1,0){100}}
    \put(25,10){\circle{3}}
    \put(49,0){a}
    \put(50,5){\line(0,1){10}}
    \put(75,10){\circle*{3}}
    \put(89,0){b}
    \put(90,5){\line(0,1){10}}
\end{picture}

There is no set of 3 points that $h(x)$ can shatter because in the labeling situation shown below, no choice of $a$ and $b$ will successfully label all the points:

\begin{picture}(100,20)
    \put(0,10){\line(1,0){100}}
    \put(25,10){\circle*{3}}
    \put(50,10){\circle{3}}
    \put(75,10){\circle*{3}}
\end{picture}

Therefore, $VC(h(x)) = 2$

\subsection*{c)}
$h(x) = 1\{a \sin x > 0\}, \quad a \in \mathbb{R}$ \\

$h(x)$ can shatter a set of 1 point by manipulating the sign of $a$. This will ensure that $h(x)$ can evaluate to a 1 or a 0 no matter where the point lies. \\

There is no set of 2 points that $h(x)$ can shatter. $h(x)$ divides the input space into $\pi$-wide sections which alternate evaluating to 1 or 0. E.g. with $a = 1$, $x \in (0,\pi)$ will evaluate to 1, $x \in [\pi,2\pi]$ will evaluate to 0, $x \in (2\pi,3\pi)$ will evaluate to 1, etc. Because of this, with any set of two points there is a labeling which $h(x)$ cannot achieve. There are two cases to consider: the two points both lie within sections that evaluate the same (i.e. both 1 or both 0) or they lie within sections that evaluate differently. In the first case, if the points are labeled differently $h(x)$ will not be able to achieve the labeling because no matter how you manipulate $a$ both points will evaluate to 1 or both points will evaluate to 0. Similarly in the second case, if the points are labeled the same $h(x)$ will not be able to achieve the labeling because no matter how you manipulate $a$ one point will evaluate to 1 and the other point will evaluate to 0. \\

Therefore $VC(h(x)) = 1$

\subsection*{d)}
$h(x) = 1\{\sin(x+1) > 0\}, \quad a \in \mathbb{R}$ \\

$h(x)$ can shatter a set of 1 point:
\begin{align*}
    x = \{0\} &\quad \text{label } \{1\},\quad a = \frac{\pi}{2} \\
              &\quad \text{label } \{0\},\quad a = 0 \\
\end{align*}

$h(x)$ can shatter a set of 2 points:
\begin{align*}
    x = \{0,\frac{\pi}{2}\} &\quad \text{label } \{0,0\},\quad a = -\frac{\pi}{2} \\
                            &\quad \text{label } \{0,1\},\quad a = 0 \\
                            &\quad \text{label } \{1,0\},\quad a = \frac{\pi}{2} \\
                            &\quad \text{label } \{1,1\},\quad a = \frac{\pi}{4} \\
\end{align*}

There is no set of 3 points which $h(x)$ can shatter because the points must span a distance of $\pi$ to realize the labeling $\{0,1,0\}$, but in that case they cannot realize the labeling $\{1,1,1\}$. \\

Therefore $VC(h(x)) = 2$

\end{document}
{'fraction_non_alphanumeric': 0.25519010963377653, 'fraction_numerical': 0.06251457895964543, 'mean_word_length': 2.7248769186214887, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '1645694', 'n_tokens_mistral': 5642, 'n_tokens_neox': 5238, 'n_words': 1175}