naive bayes classifier for non-binary feature values

Question

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.

Answer 1

\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.