首页 大数据

ML-HW2 PDF
Update on October 19, 2019: ML-HW2 Solution PDF

Question 1

Q1

(a) Considering Naive Bayes model, the features are conditionally independent. And because of the binary features, we can use Bernoulli distribution for the class-conditional probability

$$ p(\vec{x}|y=c) = \prod_{j=1}^2Ber(x_j|\mu_{jc}) $$

Use Bayes rules, the posterior probability

$$ \begin{aligned} p(y=c|\vec{x}) &= \frac{P(\vec{x},y=c)}{P(\vec{x})} \\ &= \frac{P(y=c)}{P(\vec{x})} \cdot p(\vec{x}|y=c) \\ &= \frac{P(y=c)}{P(\vec{x})} \cdot \prod_{j=1}^2Ber(x_j|\mu_{jc}) \end{aligned} $$

(b) For instance 1, $\vec{x}=\{x_1,x_2\}=\{0,0\}$

$$ P(\vec{x},y=0) = P(y=0) \cdot Ber(x_1|\mu_{10}) \cdot Ber(x_2|\mu_{20}) = \frac{3}{8} \times 0 \times \frac{2}{3} = 0 $$

$$ P(\vec{x},y=1) = P(y=1) \cdot Ber(x_1|\mu_{11}) \cdot Ber(x_2|\mu_{21}) = \frac{5}{8} \times \frac{4}{5} \times \frac{2}{5} = \frac{1}{5} $$

$$ \therefore P(\vec{x}) = 0 + \frac{1}{5}=\frac{1}{5} $$

$$ p(y=0|\vec{x}) = \frac{P(\vec{x},y=0)}{P(\vec{x})} = \frac{0}{1/5} = 0 $$

$$ p(y=1|\vec{x}) = \frac{P(\vec{x},y=1)}{P(\vec{x})} = \frac{1/5}{1/5} = 1 $$

For instance 7, $\vec{x}=\{x_1,x_2\}=\{1,1\}$

$$ P(\vec{x},y=0) = P(y=0) \cdot P(\vec{x}|y=0) = P(y=0) \cdot Ber(x_1|\mu_{10}) \cdot Ber(x_2|\mu_{20}) = \frac{3}{8} \times 1 \times \frac{1}{3} = \frac{1}{8} $$

$$ P(\vec{x},y=1) = P(y=1) \cdot Ber(x_1|\mu_{11}) \cdot Ber(x_2|\mu_{21}) = \frac{5}{8} \times \frac{1}{5} \times \frac{3}{5} = \frac{3}{40} $$

$$ \therefore P(\vec{x}) = \frac{1}{8} + \frac{3}{40} = \frac{1}{5} $$

$$ p(y=0|\vec{x}) = \frac{P(\vec{x},y=0)}{P(\vec{x})} = \frac{1/8}{1/5} = \frac{5}{8} $$

$$ p(y=1|\vec{x}) = \frac{P(\vec{x},y=1)}{P(\vec{x})} = \frac{3/40}{1/5} = \frac{3}{8} $$

Question 2

Q2

If all classes shares the same covariance matrix

$$ \begin{aligned} P(y=c|\vec{x}) & \propto P(y=c) \cdot P(\vec{x}|y) \\ & \propto \pi_c \cdot e^{-\frac{(\vec{x}-\vec{\mu_c})^T \cdot \Sigma^{-1} \cdot (\vec{x}-\vec{\mu_c)}}{2}} \\ &= \pi_c \cdot e^{-\frac{1}{2}\vec{x}^T\Sigma^{-1}\vec{x}} \cdot e^{\frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{x} - \frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{\mu_c}} \\ & \propto e^{\vec{\mu_c}^T\Sigma^{-1}\vec{x} - \frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{\mu_c} + log\pi_c} \end{aligned} $$

Let $\vec{w_c}^T=\vec{\mu_c}^T\Sigma^{-1}$ and $b_c=-\frac{1}{2}\vec{\mu_c}^T\Sigma^{-1}\vec{\mu_c} + log\pi_c$. Then

$$P(y=c|\vec{x}) \propto e^{\vec{w_c}^T\vec{x}+b_c}$$

According to the above analysis, if all classes shares the same covariance matrix, the GDA goes back to softmax regression. And if let $C=2$, we can get the logistic regression model.

ComparisionLogistic RegressionGDA
Distribution of Data$P(y=c \mid \vec{x},\vec{w})=Ber(y\mid \sigma(\vec{w}^T\vec{x}))$ . It's a weaker assumption but performs more robust. It's a simpler and lower-lever model.$P(\vec{x}\mid y=c)= N(\vec{x}\mid \vec{\mu},\vec{\Sigma})$. It is a stronger assumption but may not be reliable when encountering some extreme situations.
Amount of DataIt requires more data so it's harder for training.It requires less data to achieve a certain level of performance than logistic regression. It's easier to learn parameters.

Question 3

Q3

The logistic regression is a kind of dicriminative model and the GDA is a kind of generative model. When we come to the topic of classification, we have other kinds of classifiers. For example, on the one hand, Naive Bayes classifier, Bayesian networks, LDA and etc. belong to generative model. On the other hand, SVM, Softmax, decision tree, neural network. The comparision of generative classifiers and discriminative classifiers is as follows:

ComparisionGenerative ClassifierDiscriminative Classifier
Parameter EstimationGenerative classifier finds the best class the object belongs to by maximizing the joint probability $P(\vec{x}, y)$ using $P(y)$ and $P(\vec{x}\mid y)$. It's easier to do this because it has closed-form formulae for MLEDiscriminative classifier directly do classificaton by maxizing the conditional probability $P(y\mid \vec{x})$. More complex to do parameter estimation because it requires gradient descent to compute MLE
Missing DataNo principled way to handleEM algorithm
Features TransformHard because the new feature are correlated in complex waysEasy. $\vec{x} \rightarrow \Phi(\vec{x})$. Used in deep learning.
Semi-supervised LearningCan use unlabeled data to help with trainingHarder

Question 4

Q4

figure1

The curve(ii) represents the training error. On the one hand, this is because that generally the test error will be larger than training error. On the other hand, when the training data set is small, the data set cannot well illustrate the nature of the whole data. It's easy to train a model with zero training error but very high test error. When gradually increasing the trainning set, the training error would increase from zero to a stable value and the test error would decrease from a large value to the stable value.

The gap is called generalization gap. According to VC Theorem, I use $m$ to represent the sample size and $d=VC(H)$ to represent the model complexity. The gap between training error $\hat{\epsilon}(h)$ and test error $\epsilon(h)$ satisfies an inequality relation as follows:

With probability at least $1-\delta$, we have that all for $h\in H$

$$ |\epsilon(h)-\hat{\epsilon}(h)| \leq O \left( \sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta}} \right) $$

generalization-gap

In general, we have $\frac{m}{d}>e$ so in the interval $[e,+\infty]$

  • Fixing m. $d$ increases $\rightarrow$ $\frac{m}{d}$ decreases $\rightarrow$ $\frac{d}{m}log\frac{m}{d}$ increases $\rightarrow$ $O(\cdot)$ increases $\rightarrow$ generalization gap widens. i.e. When increasing the model complexity, the geralization gap would widen. Their relationship can be further illustrated by figure 2. As we see, the gap between green line and blue line is getting bigger and bigger as the model capacity increases.
  • Fixing d. $m$ increases $\rightarrow$ $\frac{m}{d}$ increases $\rightarrow$ $\frac{d}{m}log\frac{m}{d}$ decreases $\rightarrow$ $O(\cdot)$ decreases $\rightarrow$ generalization gap narrows. i.e. The generalization gap narrows as the sample size becomes larger. And this is already shown in figure 1. Hence, more data implies better performance of learning an algorithm.



文章评论

captcha