\documentclass[11pt,french]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[a4paper]{geometry}
\usepackage{babel}
\usepackage[tbtags]{amsmath}
\usepackage{amsthm}
\usepackage{bbm} %package for the indicator
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{dsfont}
\usepackage{fancyhdr}
\usepackage[svgnames]{xcolor}

\newtheorem{q}{Q}
\newtheorem{rem}{Remark}

\setlength{\paperwidth}{21cm} \setlength{\paperheight}{32cm}
\setlength{\evensidemargin}{-0cm} \setlength{\oddsidemargin}{-0.5cm}
\setlength{\topmargin}{-2cm} \setlength{\headsep}{0.7cm}
\setlength{\headheight}{1cm} \setlength{\textheight}{26.5cm}
\setlength{\textwidth}{17.5cm}
\setlength{\topskip}{0.cm}
\setlength{\footskip}{1cm}
\pagestyle{fancy}
\fancyhf{}
\fancyhead[L]{{\footnotesize  Teor\'ia asint\'otica}}
\fancyhead[R]{{\footnotesize Doctorado/Maestr\'ia 2017/2018}}


%Command specific to the paper
\usepackage{mathtools}
\DeclarePairedDelimiter{\ceil}{\lceil}{\rceil}
\newcommand{\esp}[1]{\mathbb{E}\left[#1\right]} % The expected value
\newcommand{\var}[1]{\text{Var}\left(#1\right)} % The variance
\newcommand{\prob}[1]{\mathbb{P}\left(#1\right)} % The probability
\newcommand{\probi}[2]{\mathbb{P}_{#1}\left(#2\right)} % The probability with ind
\newcommand{\R}{\mathbb{R}} %The R set
\newcommand{\A}{\mathcal{A}}
\newcommand{\Sh}{\mathcal{S}}
\newcommand{\C}{\mathbb{C}} %The set of complexes
\newcommand{\N}{\mathbb{N}^*} %The integers
\newcommand{\ex}{\noindent \underline{Ex :} }
\newcommand{\1}[1]{\mathbbm{1}_{#1}} %The indicator
\newcommand{\funk}[5]{
\begin{displaymath}
#1:
  \begin{array}{rcl}
    #2 & \longrightarrow & #3 \\
    #4 & \longmapsto & #5 \\
  \end{array}
\end{displaymath}}

\date{}
\begin{document}
\begin{center}
\Huge{Tarea n$^{\circ}$2}
\end{center}
El objetivo de esta tarea es investigar el comportamiento de la dimensión de Vapnik-Chernonenkis $V$. Para una clase $\A$ de subconjuntos de $\R^d$ y elementos $x_1,\dots, x_n \in \R^d$, denotamos
\begin{equation*}
\A(x_1^n) = \{b=(b_1,\dots,b_n)\in \{0,1\}^n : \exists A\in \A : b_i=\1{x_i\in A}, i=1,\dots,n\}.
\end{equation*}
El coeficiente de \textit{añicos} (eg : \textit{shatter} coefficient) es
\begin{equation*}
\Sh_{\A}(n) = \max_{x_1,\dots,x_n \in \R^d} |\A(x_1^n)|
\end{equation*}
Finalmente, sea $V(\A)$ el mayor $n$ tal que $\Sh_\A(n)=2^n$. El numero $V(\A)$ se llama la dimensión de Vapnik-Chervonenkis (VC) de $\A$. Si por cada $n$, $\Sh_\A(n)=2^n$ pongamos $V(\A)=\infty$. (¡Cuidado! Este definición cambia de una unidad de la del curso.)
\paragraph{P.1}
Sean $\A$ y $\mathcal{B}$ dos clases de subconjuntos de $\R^d$ y sean $n,m \geq 1$ números naturales. Mostrar que
\begin{enumerate}
  \item $\Sh_{\A}(n+m)\leq \Sh_{\A}(n)\Sh_{\A}(m)$.
  \item Si $\mathcal{C} = \A\cup\mathcal{B}$, entonces $\Sh_{\mathcal{C}}(n)\leq \Sh_{\A}(n)+\Sh_{\mathcal{B}}(n)$.
  \item Si $\mathcal{C} = \{C =A^c : A\in \A\}$, entonces $\Sh_{\mathcal{C}}(n)=\Sh_{\A}(n)$.
  \item Si $\mathcal{C} = \{C =A\cap B : A\in \A \text{ and } B\in \mathcal{B}\}$, entonces $\Sh_{\mathcal{C}}(n)\leq \Sh_{\A}(n)\Sh_{\mathcal{B}}(n)$
  \item Si $\mathcal{C} = \{C =A\cup B : A\in \A \text{ and } B\in \mathcal{B}\}$, entonces $\Sh_{\mathcal{C}}(n)\leq \Sh_{\A}(n)\Sh_{\mathcal{B}}(n)$
  \item Si $\mathcal{C} = \{C =A\times B : A\in \A \text{ and } B\in \mathcal{B}\}$, entonces $\Sh_{\mathcal{C}}(n)\leq \Sh_{\A}(n)\Sh_{\mathcal{B}}(n)$
\end{enumerate}

\paragraph{P.2} Justificar que la dimensión VC es bien definida.\\ \\
Digamos que un conjunto $B\subset \{0,1\}^n$ \textit{rompe} un conjunto $S=\{s_1,\dots,s_m\}\subset\{1,2,\dots,n\}$ si la restricción de B a los componentes $s_1,\dots,s_m$ es el hypercubo binario completo de dimensión $m$. Eso significa que
\begin{equation*}
  \{(b_{s_1},\dots,b_{s_m}): b=(b_1,\dots,b_n)\in B\} = \{0,1\}^m.
\end{equation*}
\paragraph{P.3.a} Sea $B_0 \in \{0,1\}^n$, $S=\{s_1,\dots,s_m\}$ y
  \funk{\Psi_1}{\mathcal{P}(\{0,1\}^n)}{\mathcal{P}(\{0,1\}^n)}{B}{\Psi_1(B)}
una transformación de cada $b =(b_1,\dots,b_n) \in B$ en $\bar{b}$ tal que :
\begin{itemize}
  \item Por los $b$ tal que $b_1=1$, $\bar{b}=(0,b_2,\dots,b_n)$ si $(0,b_2,\dots,b_n)\notin B$ y $\bar{b}=b$ si no.
  \item Por los $b$ tal que $b_1=0$, $\bar{b}=b$.
\end{itemize}
Denotamos $B_1=\Psi_1(B_0)$. Probar que $|B_0|=|B_1|$ y que $B_1$ rompe $S$ $\implies$ $B_0$ rompe $S$.

\paragraph{P.3.b} Denotamos $\Psi_2,\dots,\Psi_n$ las mismas transformaciones análogas  por cada coordenada $2,\dots,n$. Sea $B_n=\Psi_n\circ \dots \circ \Psi_1 (B_0)$ y $V\in \N$. Supongamos que para cada $S\subset \{1,\dots,n\}$ con $|S|=m>V$, $B_0$ no rompe $S$.
Mostrar que si $v=(v_1,\dots,v_n) \in \{0,1\}^n$ es un vector fijo tal que $v \in B_n$, entonces
\begin{equation*}
  T_v=\{b\in\{0,1\}^n : b_i = 0 \text{ si } v_i=0\}
\end{equation*}
es un subconjunto de $B_n$. Deducir que $v$ no contiene más que $V$ unos.

\paragraph{P.3.c} Sea $T=\cup_{v\in \mathcal{V}} T_v$, donde $\mathcal{V}$ es el conjunto de vectores que contienen no más que $V$ unos. Mostrar que $B_n\subset T$ y calcular el valor de $|T|$ en función de $V$ y $n$.

\paragraph{P.3.d} Utilizando las preguntas anteriores mostrar el \textbf{Lema (de Sauer)} :\\
Sea $\A$ una clase tal que $V(\A) <\infty$, entonces para cada $n$,
\begin{equation*}
  \Sh_{\A}(n)\le \sum_{i=0}^V \binom{n}{i}.
\end{equation*}

\paragraph{P.4} Sea $\A$ con $V=V(\A)<\infty$. Mostrar que $\Sh_{\A}(n)\le (n+1)^V$. Mostrar que en el caso particular $n \ge V$, $\Sh_{\A}(n)\le \left(\frac{ne}{V}\right)^V$. (Así si $V<\infty$ el shatter coefficient crece de manera polinomial...)

\paragraph{P.5} Sean $\A$ y $\mathcal{B}$ dos clases de dimensión VC, $V_1$ y $V_2$ respectivamente. Mostrar que la dimensión VC de $\A\cup\mathcal{B}$ es menor or igual a $V_1+V_2+1$.
\\

\noindent Sea $\rho$ la distancia sobre $\{0,1\}^n$ dada por $b,c \in \{0,1\}^n$,
\begin{equation*}
\rho(b,c)=\sqrt{\frac{1}{n}\sum_{i=1}^n \1{b_i\neq c_i}}.
\end{equation*}
En los siguientes preguntas supongamos que $\A$ tiene una dimensión de Vapnik-Chervonenkis \textbf{finita $V$}.
\paragraph{P.6.a} Fijo $x_1,\dots,x_n$, sea $B=\A(x_1^n)$ y $0\le r\le 1$. Sea $B_r \subset \{0,1\}^n$ los centros de las bolas de una cubierta mínima de $B$ por bolas de radio $r$. (Justificar que siempre existe). Mostrar que existe un conjunto $C_r \subset B$ tal que, para cada $b,c\in C_r$, $\rho(b,c)>r$ y tal que $|B_r|\le |C_r|$.

\paragraph{P.6.b} Denotamos $c^{(1)},\dots,c^{(M)}$ los elementos del conjunto $C_r$ definido en la pregunta anterior. Sean, para cada $c^{(i)},c^{(j)}$
\begin{equation*}
  A_{i,j}=\{m=1,\dots,n : c_m^{(i)}\neq c_m^{(j)}\}.
\end{equation*}
Ademas, sean $K\in \N$ fijo y $Y_1,\dots,Y_K$ variables aleatorias independientes y uniformes sobre $\{1,\dots,n\}$. Mostrar que, $\forall k \le K$,
\begin{equation*}
\prob{Y_k \in A_{i,j}} \ge r^2.
\end{equation*}

\paragraph{P.6.c} Probar que
\begin{equation*}
  \prob{\forall i,j\le M : i\neq j, \text{ al menos un }Y_k\text{ pertenece a }A_{i,j}} \ge 1-M^2e^{-Kr^2}.
\end{equation*}

\paragraph{P.6.d} Tomar $K = \ceil{2\log M/r^2}+1$. Mostrar que existen unos indices $y_1,\dots,y_K \in \{1,\dots,n\}$ todos diferentes tal que todos los elementos de $(C_r)_{|y}$ construidos por restricción de los elementos de $C_r$ a las coordenadas $y_1,\dots,y_K$ son distintos. Mostrar que $|(C_r)_{|y}|=M$.

\paragraph{P.6.e} Justificar que $C_r$ no rompe cualquier conjunto de tamaño mas grande que $V$. Deducir que
\begin{equation*}
  M\le \left(\frac{eK}{V}\right)^V \qquad \text{por } K\ge V.
\end{equation*}

\paragraph{P.6.f} Utilizando la pregunta anterior mostrar que
\begin{equation*}
  \log M \le \frac{V}{1-1/e}\log \frac{4e}{r^2}
\end{equation*}
(Pista : Pensar que para cada $x>0, \log x \le x/e$. Estudiar los casos $\log M \ge V$ y $\log M \le V$)

\paragraph{P.6.g} Concluir que\\ \\
\textbf{Teorema} Sea $\A$ una clase de subconjuntos de $\R^d$ de dimensión de Vapnik-Chervonenkis finita $V$. Entonces, por cada $x_1,\dots,x_n \in \R^d$ y $0\le r \le 1$,
\begin{equation*}
  H(r,\A(x_1^n),\rho)\le \frac{V}{1-1/e}\log \frac{4e}{r^2}
\end{equation*}

\end{document}
