$3$ Learning DNFs with kernel perceptron

Suppose that we have $S=\{(x^{(i)},y^{(i)}){\}}_i=1^n$ with $x^{(i)}in\{0,1{\}}^d$ and $y^{(i)}in\{-1,1\}.$ Let $$:$\{0,1{\}}^d\{0,1\}$ be a

"target function" which "labels" the points. Additionally assume that $$ is a DNF formula $($i$.$e$.$ is a disjunction of

conjunctions, or a boolean $"$or$"$ of a bunch of boolean "and"s$).$ The fact that it "labels" the points simply means that

$1[y^{(i)}=1]=(x^{(i)}).$

For example, let $(x)=(x_1^{{?}^{?}}{x}_2)vv(x_1^{{?}^{?}}{\stackrel{}{x}}_2^{{?}^{?}}{x}_3)($where $x_i$ denotes the $i$ th entry of $\{$:$x),x^{(i)}=([1,0,1]{)}^{TT},$

and $x^{(j)}=([1,0,0]{)}^{TT}.$ Then, we would have $(x^{(i)})=1$ and $(x^{(j)})=0,$ and thus $y^{(i)}=1$ and $y^{(j)}=-1.$

$($i$)$ Give an example target function $($make sure its a DNF formula$)$ and set $S$ such that the data is not linearly

separable.

Part $($i$)$ clearly shows that running the perceptron algorithm on $S$ cannot work in general since the data does not

need to be linearly separable. However, we can try to use a feature transformation and the kernel trick to linearize the

data and thus run the kernelized version of the perceptron algorithm on these datasets.

Consider the feature transformation $$:$\{0,1{\}}^d\{0,1{\}}^{3^d}$ which maps a vector $x$ to the vector of all the conjunc$-$

tions of its entries or of their negations. So for example if $d=2$ then

$($note that $1$ can be viewed as the empty conjunction, i$.$e$.$ the conjunction of zero literals$).$

Let $K$:$\{0,1{\}}^d\{0,1{\}}^{d}R$ be the kernel function associated with $($i$.$e$.$ for $a,$bin$\{0,1{\}}^d$:$K(a,b)=$

$(a)*(b).$ Note that the naive approach of calculating $K(a,b)($simply calculating $(a)$ and $(b)$ and taking the dot

product$)$ takes time $(3^d).$

Also let $w^{**}in\{0,1{\}}^{3^d}$ be such that $w_1^{**}=-0\mathrm{.}5($this is the entry which corresponds to the empty conjunction, i$.$e$.$

$\{$:AAxin$\{0,1{\}}^d$:$(x{)}_1=1)$ and AAi$>1$:$w_i^{**}=1$ iff the $i$ th conjunction is one of the conjunctions of $.$ So for example

letting $(x)=(x_1^{{?}^{?}}{x}_2)vv(\frac{?}{\text{b}\text{a}\text{r}}(x_1))$ we would have:

$w^{**}=([-0\mathrm{.}5,0,0,1,0,1,0,0,0]{)}^{TT}$

$($ii$)$ Find a way to compute $K(a,b)$ in $O(d)$ time.

$($iii$)$ Show that $w^{**}$ linearly separates is just a shorthand for $\{$:$\{((x^{(i)}),y^{(i)}){\}}_i=1^n)$ and find a lower bound

for the margin $$ with which it separates the data. Remember that $=mi{n}_{((x^{(i)}),y^{(i)})in(S)}{y}_i(\frac{w^{**}}{||w^{**}||}*(x^{(i)})).$

Your lower bound should depend on $s,$ the number of conjunctions in $.$

$($iv$)$ Find an upper bound on the radius $R$ of the dataset $(S).$ Remember that

$R=ma{x}_{((x^{(i)}),y^{(i)})in(S)}||(x^{(i)})||.$

$($v$)$ Use parts $($ii$),($iii$),$ and $($iv$)$ to show that we can run kernel perceptron efficiently on this transformed space

in which our data is linearly separable $($show that each iteration only takes $O(nd)$ time per point$)$ but that

unfortunately the mistake bound is very bad $($show that it is $O(s{2}^d)).$

There are ways to get a better mistake bound in this same kernel space, but the running time then becomes very

bad $($exponential$).$ It is open whether there are ways to get both polynomial mistake bound and running time.