# naive bayes classifier for non-binary feature values

Given a training set $$\{{(x^{(i)},y^{(i)});i=\{1,...,m}\}\}$$ where $$x^{(i)}\in\{1,2,...s\}^n$$ and $$y^{(i)}\in{0,1}$$. We model the label as a biased coin with $$\theta_0=P(y^{(i)}=0)$$ and $$1-\theta_0=P(y^{(i)}=1)$$. We model each non-binary feature value $$x_j^{(i)}$$ (an element of $$x^{(i)}$$) as a biased dice for each class. This is parametrized by:

$$P(x_j=k|y=0) = \theta_{j,k|y=0}, k = 1, \ldots, s-1;$$

$$P(x_j=s|y=0) = \theta_{j,s|y=0}=1-\sum_{k=1}^{s-1}\theta_{j,k|y=0};$$

$$P(x_j=k|y=1) = \theta_{j,k|y=1}, k = 1, \ldots, s-1;$$

$$P(x_j=s|y=1) = \theta_{j,s|y=1}=1-\sum_{k=1}^{s-1}\theta_{j,k|y=1};$$

[![enter image description here][1]][1]

(1) Using the Naive Bayes assumption, write down the joint probability of the data: $$P(x^{(1)},\ldots,x^{(m)},y^{(1)},\ldots,y^{(m)})$$ in terms of the parameters $$\theta_0, \theta_{j,k|y=0},$$ and $$\theta_{j,k|y=1},$$ Using the indicator function 1(.) may be useful

(2) Maximizing the joint probability you get in (1) with respect to $$\theta_0, \theta_{j,k|y=0},$$ and $$\theta_{j,k|y=1},$$, write down your resulting $$\theta_0, \theta_{j,k|y=0},$$ and $$\theta_{j,k|y=1},$$ and show intermediate steps. Comment on the meaning of your results.

My attempt:

I know that $$P(Y,X_1,X_2,\ldots,X_d)=P(Y)\cdot \Pi_{i=1}^{d}{P(X_i|Y)}$$. To expand this to non-binary, I'm not sure how to proceed. Any help is appreciated.

\begin{align} &P(x^{(1)}, \ldots, x^{(m)}, y^{(1)}, \ldots, y^{(m)})\\ &=\prod_{i=1}^m P(x^{(i)},y^{(i)})\\ &= \prod_{i=1}^m P(y^{(i)})P(x^{(i)}|y^{(i)})\\ &= \prod_{i=1}^m \left[\textbf{1}(y^{(i)}=1)(1-\theta_0)\prod_{j=1}^nP(x^{(i)}_j|y^{(i)}=1)+\textbf{1}(y^{(i)}=0)\theta_0\prod_{j=1}^nP(x^{(i)}_j|y^{(i)}=1)\right]\\ &=(1-\theta_0)^{\sum_{i=1}^m\textbf1(y^{(i)}=1)}\theta_0^{\sum_{i=1}^m\textbf1(y^{(i)}=0)}\prod_{j=1}^n\prod_{k=1}^s \theta_{j,k|y=1}^{\sum_{i=1}^m\textbf1(x_j^{(i)}=k, y^{(i)}=1)}\theta_{j,k|y=0}^{\sum_{i=1}^m\textbf1(x_j^{(i)}=k, y^{(i)}=0)} \end{align}

Let's take the logarithm of the expression above and we want to maximize the following

\begin{align}&\sum_{i=1}^m \textbf1(y^{(i)}=1)\log(1-\theta_0)+\sum_{i=1}^m \textbf1(y^{(i)}=0)\log(\theta_0)+\\& \sum_{j=1}^n \sum_{k=1}^s \sum_{i=1}^m\left[ \textbf1(x_j^{(i)}=k, y^{(i)}=1) \log \theta_{j,k|y=1} + \textbf1(x_j^{(i)}=k, y^{(i)}=0) \log \theta_{j,k|y=0}\right]\end{align}

subject to the condition that

$$\sum_{k=1}^s \theta_{j,k|y=1}=1$$ $$\sum_{k=1}^s \theta_{j,k|y=0}=1$$

as well as the nonnegative constraints.

Let the Langrange multiplier for the sum to $$1$$ constraint be $$\lambda_{j,1}$$ and $$\lambda_{j,0}$$.

The Langrangian that we want to optimize is

\begin{align}&\sum_{i=1}^m \textbf1(y^{(i)}=1)\log(1-\theta_0)+\sum_{i=1}^m \textbf1(y^{(i)}=0)\log(\theta_0)+\\& \sum_{j=1}^n \sum_{k=1}^s \sum_{i=1}^m\left[ \textbf1(x_j^{(i)}=k, y^{(i)}=1) \log \theta_{j,k|y=1} + \textbf1(x_j^{(i)}=k, y^{(i)}=0) \log \theta_{j,k|y=0}\right]\\ &-\sum_{j=1}^n \lambda_{j,1}\left(\sum_{k=1}^s \theta_{j,k|y=1}-1\right)-\sum_{j=1}^n \lambda_{j,0}\left(\sum_{k=1}^s \theta_{j,k|y=0}-1\right)\end{align}

Differentiate with respect to $$\theta_0$$ and equate it to zero, we get

$$-\frac{\sum_{i=1}^m\textbf1(y^{(i)}=1)}{1-\theta_0}+\frac{\sum_{i=1}^m\textbf1(y^{(i)}=0)}{\theta_0}=0$$

Solving it which is just solving a linear equation, we can check that $$\theta_0=\frac{\sum_{i=1}^m\textbf1(y^{(i)}=0)}{m}$$.

We can also differentiate with respect to $$\theta_{j,k|y=1}$$,

$$\frac{\sum_{i=1}^m\textbf{1}(x_j^{(i)}=k, y^{(i)}=1)}{\theta_{j,k|y=1}}=\lambda_{j,1}$$

That is fixing $$j$$,$$\theta_{j,k|y=1}$$ is proportional to $$\sum_{i=1}^m\textbf{1}(x_j^{(i)}=k, y^{(i)}=1)$$. With the sum to $$1$$ constraint, we have

$$\theta_{j,k|y=1}=\frac{\sum_{i=1}^m\textbf{1}(x_j^{(i)}=k, y^{(i)}=1)}{\sum_{k=1}^s\sum_{i=1}^m\textbf{1}(x_j^{(i)}=k, y^{(i)}=1)}$$

I will leave the last part as an exercise.