$2.(35$ points$)$ Effect of constraints on optimal solutions. A key result that optimal classifiers pick the most probable class, which defines Bayes optimality. One of the consequences is that optimal decisions are pure or crisp, they don't weight or mix decisions. But is this result always true? Here we show how constraints can make the answer to this question NO by understanding how they change the nature of an optimal solution.

One of the key ideas in the course is that the knowledge we have about the structure of our data also constitutes data that we can encode as constraints. A simple example is when a variable has upper and$/$or lower bounds. As a concrete example, we might want to choose the best product $($e$.$g$.$ pizza$)$ for a discrete set of use cases $($e$.$g$.$ food

restriction types like vegatarian $=1,$ gluten$-$free $=2,$ dairy$-$free $=3,$ etc.$)$ for the lowest price, given a dataset with features x $=[$Xitem$,$ Xcust, Xprice$]$ labeled by the best use case y $=\{0,1,2,...\}.$

Consider a N$-$class classification problem with features x in Rd and one$-$hot encoded labels y $=$ ex$,$ where ex are unit vectors with $1$ at component k and zero elsewhere, and k in $\{1,...,$ N$.$ Assume the data is D$-$distributed $($x$,$ y$)$ ~ D$,$ where D is a fixed $($but unknown$)$ distribution on Rd x $\{0,1,2,...\}.$ Assume p$($y $=$ ex$)=$ ak such that k $=1.$ Consider the classifier given by

f$($x$)=\{$k: P$($y$=$ekx$)>=$ BjkP$($y $=$ ex$))($jk$)\}$

The standard classification loss is the error rate, given by

L$($f$)=$ P$($f$($x$)$ y$)=$ E$($x$,$y$)$~D $[1($f$($x$)!=$ y$)],$ where $1$ is the indicator function $($for $0-1$ loss$),$ and L$(.)$ is the expected $0-1$ loss or true error rate. Professor Bayes claims the following for any other classifier function

gf: Rd $\{0,1,2,...\},$ we have L $($f$)$ L$($g$),$ which is the definition of Bayes optimal for the proper choice of Bjk$.$ The result is standard and easy to find.