\documentclass[10pt]{article}
%\newtheorem{define}{Definition}
\usepackage{amsfonts, graphicx}
\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in




\newcommand{\error}{{\mbox{error}}}
\newcommand{\bit}{{\{0 , 1\}}}
\newcommand{\pmone}{{\{-1 , 1\}}}
\newcommand{\bigand}{\displaystyle\bigwedge}
\newcommand{\bigsum}{\displaystyle\sum}
\newcommand{\calA}{{\cal A}}
\newcommand{\calC}{{\cal C}}
\newcommand{\sign}{\mathop{\rm sign}}

\begin{document}
\input{preamble.tex}


\lecture{10}{May 27, 2009}{Ronitt Rubinfeld}{Elya Dolev and Gilad Tsur}

Today:

\begin{enumerate}
\item Learning under the uniform distribution
\item Learning via Fourier representation.

\end{enumerate}


\section{Uniform Distribution Learning}


\begin{definition} Given hypothesis $h$, \emph{error of $h$ with respect to $f$} is $\emph{error}(h) = \displaystyle\Pr_{x \in_U} [f(x) \neq h(x)]$, where $U$ is the uniform distribution.
\end{definition}

\begin{definition}A \emph{uniform distribution learning algorithm} for concept class $\calC$ is an algorithm $\calA$ such that 
\begin{enumerate}
\item $\calA$ is given $\epsilon, \delta>0$, and has access to a set of samples $(x,f(x))$, where each $x$ is chosen uniformly from the domain.
\item $\calA$  outputs $h$ such that with probability at least $\geq 1 - \delta$, error of $h$ with respect to  $f$ is at most $\epsilon$.
\end{enumerate}
\end{definition}
Note that if $f$ is arbitrary, then the learning task is impossible without seeing almost all the inputs of $f$, however, if we know that $f$ is in a certain class of functions, referred to as the concept class $\calC$, then the learning task may become possible.  We are given access to an example oracle, and to the parameters $\delta$ and $\epsilon$. The value $\delta$ is often referred to as the ``security'' or ``confidence parameter'', and  $\epsilon$ is the approximation error or ``accuracy parameter''.

\subsection{Parameters of Interest}
\begin{itemize}
\item $m$: ``Sample complexity''.  The number of randomly chosen examples that we get from the oracle.
\item $\epsilon$: Accuracy parameter.  Discussed above.
\item $\delta$: Security parameter.  Discussed above.
\item Running time?  Might be different than the sample complexity or query complexity.  Note that, trivially,  $m \leq$ running time.  We would like to get something polynomial in $\frac{1}{\epsilon}$, $\frac{1}{\delta}$ (actually, $\log\frac{1}{\delta}$) $\log \abs{\mathcal{C}}$, $\log \abs{D}$.  Note that the requirement on the domain space assumes that we fully read the values $x, f(x)$ given to us from the example oracle, so they should be simple to describe.
\item Description of $h$ should be relatively compact.  Some models restrict this further.
\end{itemize}

Note that $h$ is not necessarily in $\mathcal{C}$.  In some models, ``proper learning algorithms,'' this is the case, but we will not restrict our attention to them.

\subsection{Remarks}
\begin{itemize}
\item This Uniform Distribution Learning model is a special case of the PAC (probably approximately correct) model.  More generally, Ex($f$) for unknown distribution $\mathcal{D}$.  
$$ \error(h) = \Pr_{x \in \mathcal{D}} [f(x) \neq h(x)]$$
\item Can get the dependence on $\delta $ to be $\log \frac{1}{\delta}$.  
\end{itemize}

\section{Brute Force Algorithm}
If the running time doesn't matter, only sample complexity, then it is easy to write learning algorithms, but as we will see, the algorithm that makes this possible is infeasible in practice.

\begin{itemize}
\item Draw $M = \frac{1}{\epsilon} ( \ln \abs{\mathcal{C}} + \ln \frac{1}{\delta}) $ samples.  $\mathcal{C}$ is generally regarded as a class of exponential size.
\item Search over all $h \in \mathcal{C}$ until one $h$ labels all examples correctly and output it.  Given multiple choices, chose arbitrarily.  Notice that the sample complexity is fine, because we reuse our samples for each iteration of the search.
\end{itemize}
Motivation:  $h$ is bad, if the error of $h$ with respect to $f \geq \epsilon$.  Whether $h = f$ on all inputs or just most, doesn't really matter.  

\begin{eqnarray*}
Pr[\mbox{specific bad } h \mbox{ is consistent with examples}] & \leq &(1 - \epsilon)^M \\
 Pr[\mbox{there exist a bad } h \mbox{ that ``survives''}] & \leq &\abs{\calC} (1 - \epsilon)^M  \\
 & \leq &\abs{\calC} (1 - \epsilon)^{\frac{1}{\epsilon} ( \ln \abs{\mathcal{C}} + \ln \frac{1}{\delta})} \\
 & \leq &\delta 
\end{eqnarray*}

Therefore, this algorithm is unlikely to output any bad $h$.  \\
\\
\begin{remark}Ignoring the sample size bounds leads to bad statistics, where the sample size is insufficient for an inordinately large class space to rule out all of the bad $h$ possibilities.  The key is to define in advance the concept class, rather than expanding the concept class to fit ``interesting'' results.
\end{remark}

\section{Example: Monomial Functions}
\begin{itemize}
\item $\calC  = $ conjunctions over $\bit^n$ (including negation).  $\abs{\calC} = 3^n$
\item Example: $f = x_i x_j \bar{x_k}$
\item Cannot learn efficiently with 0 error.  Think about a very long conjunction, which is 0 unless none of the variables are 0.  In a polynomial number of queries, there is no way to detect it is not the all zeros function.
\item Brute Force needs $\frac{1}{\epsilon} \left(\ln 3^n + \ln \frac{1}{\delta}\right) = O\left(\frac{n}{\epsilon} + \frac{1}{\epsilon} \ln \frac{1}{\delta}\right)$ samples. 
\end{itemize}

\subsection{Poly-time Algorithm}

We say that a sample (or an input) $(x,f(x))$ is \emph{positive} if $f(x) = 1$. If $f(x)=0$, we say that the sample is \emph{negative}. Let us describe the algorithm. We will set $k$ that appears in the algorithm later on.

\begin{enumerate}
\item Draw $O(\frac{1}{\epsilon^2}\log\frac{1}{\delta})$ samples to estimate the fraction of positive inputs within $\epsilon/4$ with probability at least $1-\frac{\delta}{2}$.

\item If in less than $\epsilon/2$ fraction of samples are positive, output $h(x) = 0$.

\item Take samples until have at least $k$ positive samples.

\item Let $V = \lbrace{i : \mbox{$x_i$ is the same in all positive examples}\rbrace}$.

\item Output hypothesis $h(x) = \bigand_{i \in V} x_i^b$, where $b$ is the complement or the variable.
\end{enumerate}

%% Figure 2

Why does this work? First we check if the function is sufficiently far from the all-zero function. If it is not, we can output the all-zero function as our hypothesis (Step 2).  Otherwise, we know in Steps 3--5 that $\Pr_x[f(x)=1] \ge \epsilon/4$. 
\\ If $x_i$ is in $f$, then it must have the same value for every positive sample, and $x_i\in V$.  
\\ If $x_i$ is not in $f$, $\Pr[x_i\in V]\leq \Pr[x_i\mbox{ is set the same in each positive example}]\leq\frac{1}{2^{k-1}}$. Thus using union bound, $\Pr[\mbox{any $x_i$ survives in $V$}]\leq\frac{n}{2^{k-1}}$, and we want this to be at most $\delta$. Thus we need $k=O(\log(\frac{n}{\delta}))$ positive examples, which we will draw with sufficiently high probability if we will draw a total number of $O(\frac{1}{\epsilon}\log(\frac{n}{\delta})\frac{1}{\delta})$ samples.

Notice that learning requires logarithmically many queries, even for singletons, while dictator testing takes a constant number of queries.  So, testing can be much faster than learning.

\section{Learning via Fourier Coefficients}
Recall:
\begin{itemize}
\item The Fourier representation of $f$ is:  $f(x)=\displaystyle\sum_z{\hat{f}(x)\chi_z(x)}$.
\item The Fourier coefficient for $s$ can be computed by: $\hat{f}(s)=\frac{1}{2^n}\displaystyle\sum_{x\in\{0,1\}^n}{f(x)\chi_s(x)}$.
\item The distance of $f$ from the linear function $chi_s$ can be expressed in terms of its Fourier coefficient corresponding to $s$ as follows: $dist(f,\chi_s)=\frac{1}{2}(1-\hat{f}(s))$.
\end{itemize}
Approximating a single Fourier coefficient of an unknown function:
\begin{lemma} We can approximate any specific Fourier coefficient $s$ to within $\gamma$ (i.e. $\abs{output - \hat{f}(s)} < \gamma$) with probability $\geq 1 - \delta$ in $O\left(\frac{1}{\gamma^2} \log \frac{1}{\delta}\right)$ samples.
\end{lemma}
\begin{proof}
We have $\hat{f}(s) = 2 \times \Pr[f = \chi_s]  - 1$, and we can estimate $\Pr[f = \chi_s]$ to within $\pm \gamma/2$ using Chernoff bounds.
\end{proof}

It is thought to be unlikely in this model that one can efficiently find the ``heavy'' Fourier coefficients with non-trivial values.  Exhaustive search is intractable, and no other method is immediately clear.  If we are dealing with a function class where most of the weight is in the coefficients with small $s$, we can exhaustively check these values.
First, however, we will describe and analyze the {\em Low Degree Algorithm}.

\section{Preliminaries}

We need a few definitions.
\begin{definition}
A function $f: \{\pm 1\}^n \rightarrow \R$ is said to have 
$\alpha(\epsilon, n)$ concentration if 
\begin{equation}
\sum_{S\subseteq [n],|S|>\alpha(\epsilon, n)} \hat{f}(S)^2\leq \epsilon, 
~\forall~0 < \epsilon < 1. 
\end{equation}
\end{definition}
In particular, for Boolean functions
$f: \{\pm 1\}^n \rightarrow \{\pm 1\}$, the above relation
is equivalent to 
\begin{equation}
\sum_{S\subseteq [n], |S|\leq\alpha(\epsilon, n)}\hat{f}(S)^2\geq 1-\epsilon,
~\forall~0 < \epsilon < 1. 
\end{equation}
This follows from Parseval's theorem,
which states that
\begin{equation}
\sum_{S\subseteq [n]}\hat{f}(S)^2 = 1.
\end{equation}
Intuitively, if $\alpha$ assumes small values,
then the concentration of the function is on the low-degree terms of its
Fourier decomposition. (Throughout these notes, we will use the terms
{\em Fourier concentration} and {\em Fourier degree} interchangeably.)

Let us now consider some functions which satisfy this property, i.e.
have low Fourier concentration.
The first example we consider is the class of {\em junta} functions. These
functions depend on only $k \ll n$ variables. Clearly, if $f$ is such a 
function which does not depend on a variable $i$, then
\begin{equation}
\hat{f}(S) = 0,
~\forall~S\subseteq [n],~i\in S.
\end{equation}
Since the junta function depends
on only $k$ variables (without loss of generality, assume that these variables are $1\dots k$), a direct consequence of the above observation is that
\begin{equation}
\sum_{S\subseteq [n], |S|>k} \hat{f}(S)^2 = 0.
\end{equation}
Thus, the junta function has Fourier degree at most $k$ for any value of
$\epsilon$.

Our next example is the following slightly unusually defined AND function.
\begin{equation}
\AND(x_1, x_2, \ldots, x_k) = \left\{\begin{array}{ll} 
1 & {\rm if}~\forall i,~x_i = -1 \\
-1 & {\rm otherwise}.
\end{array}\right.
\end{equation}
\begin{theorem}
The $\AND$ function defined above has Fourier concentration $\log (4/\epsilon)$.
\end{theorem}
\begin{proof}
We consider two cases depending on the value of $\epsilon$.\\
{\em Case 1:}  $k\leq \log(4/\epsilon)$. In this case, from our analysis of the
junta function above, we directly obtain
\begin{equation}
\sum_{S\subseteq [n], |S|>\log(4/\epsilon)} \hat{f}(S)^2 = 0 < \epsilon.
\end{equation}
{\em Case 2:}  $k > \log(4/\epsilon)$. Define 
\begin{eqnarray}
g(x) & = & \left\{\begin{array}{ll} 
1 & {\rm if}~\forall i,~x_i = -1 \\
0 & {\rm otherwise}
\end{array}\right.\\
g(x) & = & (\frac{1-x_1}{2})(\frac{1-x_2}{2})\ldots (\frac{1-x_k}{2}) \\
& = & \sum_{S\subseteq [k]}\frac{(-1)^{|S|}}{2^k} \chi_S.
\end{eqnarray}
Now, 
\begin{eqnarray}
\AND(x) & = & 2g(x) - 1\\
& = & (-1 + 2^{1-k}) + \sum_{S\subseteq [k], |S| > 0} (-1)^{|S|}2^{1-k}\chi_S.
\end{eqnarray}
Clearly, there are at most $2^k$ non-zero Fourier co-efficients corresponding 
to characters $S$ such that $|S|>0$. Thus,
\begin{eqnarray}
\sum_{S\subseteq [k], |S|>\log(4/\epsilon)} \hat{f}(S)^2 & 
\leq & \sum_{S\subseteq [k], |S|>0} \hat{f}(S)^2\\
& \leq & [(-1)^{|S|}2^{1-k}]^2 2^k\\
& = & \frac{4}{2^k}\\
& < & \epsilon.
\end{eqnarray}
The last inequality follows from the assumption that $k > \log(4/\epsilon)$.
\end{proof}

\section{The Low Degree Algorithm}

The low degree algorithm is a uniform distribution learning algorithm which 
is efficient for functions with low Fourier degree. The algorithm is presented
in Figure~\ref{fig:low-degree}. As an optimization, note that the result of a single set of $m$ queries to the function $f$ can be
re-used in estimating $C_S$ for each $S$, since we do not use the independence of the estimates in our analysis of correctness.

\begin{figure}
\centering
\noindent \fbox{
\begin{minipage}{5.5in}
%\centering
{\bf Input:} Oracle access to function $f$ under uniform sampling, 
Fourier degree
of $f$ denoted by $d = \alpha(\epsilon, n)$, accuracy parameter $\tau$
and confidence or security parameter $\delta$.
\begin{enumerate}
\item Let $m = O(\frac{n^d}{\tau}\ln \frac{n^d}{\delta})$.
\item Collect $m$ samples from the function.
\item For each set $S\subseteq [n]$ such that $|S|\leq d$,
let $C_S$ be an estimate for $\hat{f}(S)$.
\item Let $h = \sum_{S\subseteq [n], |S|\leq d} C_S \chi_S$.
\item Output $\sign(h)$ as the estimate of $f$.
\end{enumerate}
\end{minipage}
}
\caption{The low-degree algorithm}
\label{fig:low-degree}
\end{figure}

We now analyze the low-degree algorithm. We prove two lemmas
which will lead us to the ultimate result.

\begin{lemma}\label{lma:first}
If $f$ has $\alpha(\epsilon, n)$ Fourier concentration, then $h$ computed by the algorithm satisfies 
\begin{equation}
E_x[(f(x)-h(x))^2] \leq \epsilon + \tau,
\end{equation}
with probability $\geq 1-\delta$.
\end{lemma}
To prove this lemma, we need the following lemma.
\begin{lemma}
With probability $\geq 1-\delta$, for each $S$ satisfying $|S|\leq d$,
\begin{equation}
|C_S - \hat{f}(S)| \leq \gamma,
\end{equation}
where $\gamma = \sqrt{\frac{\tau}{n^d}}$.
\end{lemma}
\begin{proof}
Since the 
$O(\frac{n^d}{\tau}\log \frac{n^d}{\delta}) = O(\frac{1}{\gamma^2}\log \frac{n^d}{\delta})$ samples used to 
estimate any Fourier coefficient $\hat{f}(S)$ are independent,
we can claim, using Chernoff bound, that 
\begin{equation}
|C_S - \hat{f}(S)| > \gamma
\end{equation}
with probability $\leq \frac{\delta}{n^d}$. Since there are $\leq n^d$ 
sets $S$ such that $|S|\leq d$, the lemma follows using union bound.
\end{proof}

We now use this lemma to prove Lemma~\ref{lma:first}.

\begin{proof-of-lemma}{\ref{lma:first}}
Define 
\begin{equation}
g(x) = f(x) - h(x).
\end{equation}
Since the Fourier decomposition is linear, for each $S\subseteq [n]$, 
\begin{equation}
\hat{g}(S) = \hat{f}(S) - \hat{h}(S).
\end{equation}
From the algorithm, for any $S$ such that $|S| > d$, $\hat{h}(S) = 0$.
Thus, 
\begin{eqnarray}
\sum_{S\subseteq [n], |S|>d}\hat{g}(S)^2 & = & \sum_{S\subseteq [n], |S|>d}\hat{f}(S)^2\\
& \leq & \epsilon.
\end{eqnarray}
The second inequality holds since $d = \alpha(\epsilon, n)$.

On the other hand, for each $S$ such that $|S|\leq d$,
\begin{eqnarray}
\hat{g}(S)^2 & = & (\hat{f}(S) - \hat{h}(S))^2\\
& \leq & \gamma^2,
\end{eqnarray}
with probability $\geq 1-\delta$. 
The second inequality follows from Lemma~\ref{lma:first}. Since there are 
$\leq n^d$ sets $S$ such that $|S|\leq d$,
\begin{eqnarray}
\sum_{S\subseteq [n], |S|\leq d} \hat{g}(S)^2 & \leq & \gamma^2 n^d\\
& = & \tau.
\end{eqnarray}

We now have
\begin{eqnarray}
E_x[(f(x)-h(x))^2] & = & E[g(x)^2]\\
& = & \sum_{S\subseteq [n]} \hat{g}(S)^2\\
& = & \sum_{S\subseteq [n], |S|\leq d} \hat{g}(S)^2 + \sum_{S\subseteq [n], |S|> d} \hat{g}(S)^2\\
& \leq & \tau + \epsilon,
\end{eqnarray}
with probability $\geq 1-\delta$. The second equation follows from 
Plancherel's theorem.
\end{proof-of-lemma}

We now prove another lemma which will be useful in the final result.

\begin{lemma}\label{lma:second}
For any functions $f: \{\pm 1\}^n\rightarrow \{\pm 1\}$ and 
$h: \{\pm 1\}^n\rightarrow \R$,
\begin{equation}
Pr[f(x)\not= \sign(h(x))] \leq E_x[(f(x)-h(x))^2].
\end{equation}
\end{lemma}
\begin{proof}
We have
\begin{equation}
E_x[(f(x)-h(x))^2] = \frac{1}{2^n}\sum_x (f(x)-h(x))^2,
\end{equation}
while 
\begin{equation}
Pr[f(x)\not= \sign(h(x))] = \frac{1}{2^n}\sum_x {\bf 1}(x),
\end{equation}
where $\bf 1$ is defined as
\begin{equation}
{\bf 1}(x) = \left\{\begin{array}{ll}
1 & {\rm if}~f(x)\not=\sign(h(x))\\
0 & {\rm otherwise.}
\end{array}
\right.
\end{equation}
Now, for any $x$, if $f(x)\not= \sign(h(x))$, then 
\begin{equation}
(f(x)-h(x))^2 \geq 1 = {\bf 1}(x),
\end{equation}
and if $f(x) = \sign(h(x))$, then 
\begin{equation}
(f(x)-h(x))^2 \geq 0 = {\bf 1}(x).
\end{equation}
Thus, 
\begin{equation}
\sum_x (f(x)-h(x))^2 \geq \sum_x {\bf 1}(x).
\end{equation}
\end{proof}

We now arrive at our Main Theorem. However, before stating it, we
need another definition.
\begin{definition}
The Fourier concentration of a concept class of functions is the 
maximum Fourier concentration among all the functions in the class.
\end{definition}

\begin{theorem}[Main Theorem]
Let concept class $\cal C$ have Fourier concentration 
$d = \alpha(\epsilon, n)$. Then, there exists a 
$q = O(\frac{n^d}{\epsilon}\log \frac{n^d}{\delta})$-sample uniform
distribution learning algorithm for $\cal C$ (i.e. the algorithm uses
$q$ uniformly distributed independent samples and with probability
$\geq 1-\delta$, outputs a hypothesis $h'$ such that 
$Pr[f(x)\not= h'(x)]\leq 2\epsilon$).
\end{theorem}
\begin{proof}
The algorithm is to simply run the low-degree algorithm for 
$\tau = \epsilon$. The error bound follows from Lemmas~\ref{lma:first}
and \ref{lma:second} given above.
\end{proof}

What class of functions can we learn using the low-degree algorithm?
One such large class of functions that can be learned in quasi-polynomial 
($O(n^{{\rm polylog }n} )$) time using this algorithm are those which can be 
represented by constant depth circuits. Recall that a circuit consists of gates 
(typically AND, OR and NOT gates; we assume that the first two types
of gates have unbounded fan-in), constants 0 and 1 and variables
$X_1, X_2, \ldots, X_n$. It turns out that any function can be 
represented by a constant depth circuit, but we would also like
to ensure that the size of the circuit is polynomial in the number
of input variables $n$. So, one central question is whether all
functions can be computed using constant-depth, polynomial-sized
circuits? The answer is no, via a counting argument. In fact, it was proved by 
Furst, Saxe and Sipser that even the class of parity functions cannot be computed 
using constant depth, polynomial sized circuits.

But what about functions which are computable using constant depth,
polynomial sized circuits? The following theorem explores the 
Fourier concentration of such functions.
\begin{theorem}[H$\rm \bf \mathring{a}$stad, Linial Mansour Nisan]
For any function $f$ computable using a size-$s$ depth-$d$ circuit,
\begin{equation}
\sum_{S\in [n], |S|>t} \hat{f}(S)^2 \leq \alpha,
\end{equation} 
for $t=O((\log \frac{2s}{\alpha})^{d-1})$.
\end{theorem}

Taking $s$ as a polynomial in $n$, $d$ as a constant and 
$\alpha = O(\epsilon)$ gives us $t=O(\log^d \frac{n}{\epsilon})$.
Using our main theorem, we can conclude that the number of samples
required for learning such a constant depth polynomial sized circuit
is $n^{O(\log^d \frac{n}{\epsilon})}$, which is quasipolynomial in $n$.
For DNF formulas, this bound can be improved
to $O(n^{O(\log\log n)})$ samples.




%\includegraphics[scale=0.8]{decision_tree.JPG}



\includegraphics{decision_tree.JPG}


Another family of functions that can be learned using the low degree algorithm is that of functions computable by decision trees with few nodes. To characterize these functions we first define the function that represents a single {\em decision path $\ell$} in the decision tree: $f_\ell(x)= \prod_{i\in V_\ell}\frac{1\pm x_i}{2}$, where $V_\ell$ is the set of variables visited on path $\ell$. The plus or minus sign corresponds to the path's descent left or right in the decision tree. The Fourier representation for the path function is 
$ \frac{1}{2^{|V_\ell|}}\sum_{S\subseteq |V_\ell|}{(\pm 1)\chi_S}$. 
The function computed by the whole decision tree can thus be written as $f(x) = \sum_\ell{f_l(x)val(\ell)}$ where $val(\ell)$ is the value at the leaf reached by $\ell$. Note that exactly one value $f_\ell(x)$ will equal $1$ for any value $x$.

Finally, an additional class of families that can be learnt is that of halfspaces and combinations of half spaces. We define a halfspace function as follows: $h:{\pm 1}^n \rightarrow {\pm 1}$ be such that $h(x)= sign(w\cdot x - \theta)$ for some $w$ and $\theta$.

\begin{theorem}
$h$ has Fourier concentration $441/\epsilon^2$
\end{theorem}

\begin{corollary}
The low degree algorithm learns halfspaces under the uniform distribution with $n^{O(1/\epsilon^2)}$ queries
\end{corollary}

Note that other algorithms require only $n^5$ queries, so this isn't so great. However, any function $g$ which is a function of $k$ halfspaces has Fourier concentration $O(k^2/\epsilon^2)$ and as a corollary the low degree algorithm learns functions of $k$ halfspace with $n^{O(k^2/\epsilon^2)}$ queries, which is better than what was known before.

\end{document}




