Machines Learning 学习笔记(Week9)

# Anomaly Detection

## Algorithm (based on Gaussian Distribution)

1, Choose features $x_i$ that you think might be indicative of anomalous examples

2, Fit parameters $\mu_1,...,\mu_n, \sigma_1^2,...,\sigma_n^2$

```math
\mu_j = \frac{1}{m}\sum_{i=1}^mx_j^{(i)}\\
\sigma_j^2 = \frac{1}{m}\sum_{i=1}^m(x_j^{(i)}-\mu_j)^2
```

3, Given new examples x, compute $p(x)$:

```math
p(x) = \prod_{j=1}^n p(x_j;\mu_j,\sigma_j^2) = \prod_{j=1}^n \frac{1}{\sqrt{2\pi}\sigma_j}exp(-\frac{(x_j-\mu_j)^2}{2\sigma_j^2})
```

Anomaly if $p(x)<\varepsilon$

### Developing and Evaluating 

Assume we have some labeled data, of anomalous and non-anomalous examples (y=0 if normal, y=1 if anomalous).

Training set(60%): $x^{(1)},x^{(2)},...,x^{(m)}$(assume normal examples/not anomalous)

Cross validation set(20%):$(x_{cv}^{(1)},y_{cv}^{(1)}),...,(x_{cv}^{(m_{cv})},y_{cv}^{(m_{cv})})$

Test set(20%):$(x_{test}^{(1)},y_{test}^{(1)}),...,(x_{test}^{(m_{test})},y_{test}^{(m_{test})})$

>**Aircraft engines example**

>10000 good (normal) engines, 20 flawed engines (anomalous)

>Training set: 6000 good engines
CV set: 2000 good engines, 10 anomalous
Test set: 2000 good engines, 10 anomalous

####Evaluation

Fit model p(x) on the training set
On a cross validation set, predict:
- y=1 if p(x)<ε (anomaly)
- y=0 if p(x)>=ε (normal)
Possible evaluation metrics:
- Precision/Recall
- F1 Score
Can also use cross validation set to choose parameter ε

### Anomaly Detection vs. Supervised Learning
| Anomaly Detection     |   Supervised Learning |
|:-----------------:|:------------------:|
| Very small number of positive examples(y=1). (0-20 is common). Large number of negative examples(y=0). |              Large number of positive and negative examples. |
|Many different "types" of anomalies. Hard for any algorithm to learn from positive examples what the anomalies look like; future anomalies may look like nothing like any of the anomalous examples we've seen so far.| Enough positive examples for algorithm to get a sense of what positive examples are like, future positive examples likely to be similar to ones in training set.|

### Non-gaussian features

Transform the data: $log(x),\,log(x+c),\,x^{\frac{1}{2}},\,x^{\frac{1}{3}}...$

![Screen Shot 2020-06-11 at 22.50.22.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/b1e4b1e4-26e5-9829-566e-a9d946a21bba.png)


## Multivariate Gaussian Distribution (Optional)

Purpose: capture correlations between different features in case of unusual combinations of features

### Anomaly detection with the multivariate Gaussian
1, Fit model p(x) by setting

```math
\mu = \frac{1}{m}\sum_{i=1}^mx^{(i)}\\
\Sigma = \frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu)(x^{(i)}-\mu)^T\\
(\mu \in R^n,\,\Sigma\in R^{n*n})
```

2, Given a new example x, compute

```math
p(x) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp\Bigl(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu)\Bigr)\\
(|\Sigma|=determinant\,of\,\Sigma)
```
Flag an anomaly if $p(x) < \varepsilon$

### Relationship with orignial model

- $\Sigma$ measures the correlations between features. If Sigma is all 0s except the diagonal, then it's identical to the original Gaussian model.
![Screen Shot 2020-06-11 at 22.49.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/fea788b8-e3dc-bdfa-5d7d-9443ad4988dc.png)

- Change the 0s to positive numbers, means 正相关
![Screen Shot 2020-06-11 at 22.57.03.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/c29f5fc6-e659-83c6-12fa-1b55af57ed41.png)

- Similarly, change the 0s to negative numbers, means 负相关
![Screen Shot 2020-06-11 at 22.57.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/d4ba368d-f61b-65a9-d2ea-e629aee85bdf.png)

### Original Model vs. Multivariate Gaussian

![Screen Shot 2020-06-11 at 22.48.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/b753b83f-3016-c8b1-9871-51940832470a.png)

#Recommender Systems

![Screen Shot 2020-06-12 at 22.07.08.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/4d78a0a5-9484-c714-e4c0-aa32129496e6.png)

$r(i,j)=1$ if user j has rated movie i (0 otherwise)
$y^{(i,j)}=$ rating by user j on movie i (if defined)
$\theta^{(j)}=$ parameter vector for user j
$x^{(i)}=$ feature vector for movie i
For user j, movie i, predicted rating: $(\theta^{(j)})^T(x^{(i)})$
$n_u=$ no. users
$n_m=$ no. movies
$m^{(j)}=$ no. of movies rated by user j

## Content-based Recommendations
We know what the content is and how the content is. We are trying to predict users' preferences.

###Optimization algorithm:

```math
\min_{\theta^{(1)},...,\theta^{(n_u)}} \frac{1}{2}\sum_{j=1}^{n_u} \sum_{i:r(i,j)=1} \Bigl((\theta^{(j)})^Tx^{(i)}-y^{(i,j)}\Bigr)^2+\frac{\lambda}{2}\sum_{j=1}^{n_u}\sum_{k=1}^n(\theta_k^{(j)})^2\\
(\theta^{(j)} \in R^{n+1})
```

#### Gradient descent update:

![Screen Shot 2020-06-12 at 22.22.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/aad0f0d9-be20-5966-1cc9-c875427500c3.png)

## Collaborative Filtering
We don't know the content or the users' preferences. But we are trying to:
<img width="722" alt="Screen Shot 2020-06-12 at 22.28.31.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/24e9b112-9cbe-5ed4-86c6-e1def4c827fa.png">

$x \in R^n$ 
$\theta \in R^n$
Don't need $x_0$ and $\theta_0$

### Collaborative filtering algorithm
![Screen Shot 2020-06-12 at 22.32.48.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/b00b3deb-dce4-8dc2-7c03-7f03473dd002.png)

####Vectorization: Low rank matrix factorization

![Screen Shot 2020-06-12 at 22.38.06.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/3df400b9-68eb-139b-44b9-9540754b6892.png)

#### Find related products (movies)
For each product i, we learn a feature vector $x^{(i)} \in R^n$.

Find the products (movies) j with the smallest $||x^{(i)}-x^{(j)}||$.

### Mean Normalization
For users who have not rated any movies, cannot predict initial values (all 0s):
![Screen Shot 2020-06-12 at 22.45.32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/a9805b6d-68ea-ad15-0cf1-04b13470c83c.png)

![Screen Shot 2020-06-12 at 22.47.41.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/620849/d8c61392-c9ef-dfb3-11e8-d00f4f86e73e.png)