0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.