Note by gama79530: Coursera-Machine Learning-2019

Catalog

• Context
• Experience
• Machine Learning Definition
• Classes of Machine Learning Algorithm
• Problems
• Linear regression
• Logistic regression
• Neuron network

Context

1. Notation
   • $m$ : number of training example
   • $n$ : number of features
   • $x^{(i)} = \begin{bmatrix} x_{1}^{(i)} & x_{2}^{(i)} & \cdots & x_{n}^{(i)} \end{bmatrix}$ : i-th input variable / features
   • $y^{(i)}$ : i-th output variable / target variable
   • $h_{\theta}(x)$ : hypothesis function with parameters $\theta$ and input features $x$
   • $J(\theta)$ : cost function with parameters $\theta$
   • $\alpha$ : learning rate
   • $\lambda$ : regularization parameter


2. Vectorized Notation
   • $X = \begin{bmatrix} 1 & \;-\;x^{(1)}\;-\;\\ 1 & \;-\;x^{(2)}\;-\;\\ \vdots & \vdots\\ 1 & \;-\;x^{(m)}\;-\; \end{bmatrix}$
   • $Y = \begin{bmatrix} y^{(1)}\\ y^{(2)}\\ \vdots\\ y^{(m)}\\ \end{bmatrix}$
   • $\theta = \begin{bmatrix} \theta_{0}\\ \theta_{1}\\ \vdots\\ \theta_{n}\\ \end{bmatrix}$
   • $ \begin{cases} X \in \mathbb{R}^{m \times (n+1)}\\ Y \in \mathbb{R}^{m \times 1}\\ \theta \in \mathbb{R}^{(n+1) \times 1} \end{cases}$


3. Important functions
   • Sigmoid function : $\sigma(z) = \frac{1}{1 + e^{-z}}$

Experience

1. Useful plot
   • Contour plot
   • number_of_iteration - cost plot


2. Gradient descent
   • If $\alpha$ is too small : slow convergence.
   • If $\alpha$ is too large : may not decrease on every iteration and thus may not converge.
   • Try learning rate 3fold (i.e. 1, 0.3, 0.1, 0.03, 0.01, ...)
   • Debugging gradient descent : Make a plot with number of iterations on the x-axis. Now plot the cost function, $J(\theta)$ over the number of iterations of gradient descent. If $J(\theta)$ ever increases, then you probably need to decrease $\alpha$.
   • Automatic convergence test : Declare convergence if $J(\theta)$ decreases by less than $T_{converge}$ in one iteration, where $T_{converge}$ is some small value such as $10^{3}$ However in practice it's difficult to choose this threshold value.


3. Feature scaling
   • Feature scaling is a method used to normalize the range of independent variables or features of data.
   • Mean norminazion : for each feature $x_{i}$ , $x'_{i} = \frac{x_{i}-\mu_{i}}{s_{i}}$ where $\mu_{i}$ is the average of i-th feature and $s_{i}$ is either the range of i-th feature or the standard deviation of i-th feature.


4. Underfitting and overfitting
   • Underfitting (or high bias) is when the form of our hypothesis function h maps poorly to the trend of the data.
   • Overfitting (or high variance) is caused by a hypothesis function that fits the available data but does not generalize well to predict new data.
   • Solution of overfitting : reduce the number of features (manually select or use a model selection algorithm) , regularization


5. Regularization
   • Regularization works well when we have a lot of slightly useful features.
   • $J_{regularization}(\theta) = J(\theta) + \frac{\lambda}{2m} \sum_{j = 1}^{n} \theta_{j}^{2}$
   • $ \begin{cases} \frac{\partial J_{regularization}(\theta)}{\partial \theta_{0}} = \frac{\partial J(\theta)}{\partial \theta_{0}}\\ \frac{\partial J_{regularization}(\theta)}{\partial \theta_{j}} = \frac{\partial J(\theta)}{\partial \theta_{j}} + (\frac{\lambda}{m})\theta_{j} & \text{if }1 \leq j \leq n \end{cases}$


6. Non-linear hypotheses
   • If we want to use all i-th-order features in hypothesis function, then we have $\sum_{t = 1}^{i}\binom{n + t - 1}{t}$ terms in our hypothesis function.
   • This number grows very quickly as $i$ increasing when $n$ is large.

Machine Learning Definition

1. Arthur Samuel (1959). Field of study that gives computers the ability to learn without being explicitly programmed.


2. Tom Mitchell (1998) Well-posed Learning Problem : A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

Classes of Machine Learning Algorithm

1. Supervised learning
   • In supervised learning, we are given a data set and already know what our correct output should look like, having the idea that there is a relationship between the input and the output.
   • Supervised learning problems are categorized into "regression" and "classification" problems.
   • Regression problem : continuous output
   • Classification problem : discrete output


2. Unsupervised learning
   • Unsupervised learning allows us to approach problems with little or no idea what our results should look like. We can derive structure from data where we don't necessarily know the effect of the variables.
   • With unsupervised learning there is no feedback based on the prediction results.


3. Reinforcement learning


4. Recommender systems

Problems

1. Binary classification
   • Possible prediction : $y \in \{0 , 1\}$
   • Build a probability function model $P(y = 1 | x;\theta)$ and determine a threshold value $T$, we can predict y = 1 if $P(y = 1|x;\theta) \geq T$ and predict y = 0 otherwise.
   • Decision boundary definition : $\{ x : P(y = 1 | x;\theta) = T\}$
   • Logistic regression solution : use logistic regression model $h_{\theta}(x)$ and let $P(y = 1 | x;\theta) = h_{\theta}(x)$


2. Multiclass classification
   • Possible prediction : $y \in \{0 , 1 , \cdots , n\}$
   • One-vs-all (or one-vs-rest) solution
     • For each $i \in \{0 , 1 , \cdots , n\}$ , we can change the problem into binary classification problem by only classifying whether $y = i$ or not.
     • Predict y = i if $P(y = i | x;\theta^{(i)}) = \max\limits_{0 \leq j \leq n} P(y = j | x;\theta^{(j)})$ , where $P(y = i | x;\theta^{(i)})$ denote the probability function of i-th binary classification problem.
     • Logistic regression solution : use logistic regression model $h_{\theta^{(i)}}(x)$ to be the solution of i-th binary classification problem "whether $y = i$ or not" and let $P(y = i | x;\theta^{(i)}) = h_{\theta^{(i)}}(x)$
   • Neuron network solution
     • $y \in \overbrace{\left\{ \begin{bmatrix} 1\\ 0\\ 0\\ \vdots\\ 0 \end{bmatrix} , \begin{bmatrix} 0\\ 1\\ 0\\ \vdots\\ 0 \end{bmatrix} , \cdots , \begin{bmatrix} 0\\ 0\\ 0\\ \vdots\\ 1 \end{bmatrix}\right\}}^{(n + 1)\text{ possible outputs}}$
     • Use forward propagation and backward propagation to train the NN model.

Linear regression

1. Hypothesis & Cost function
   • $h_{\theta}(x) = \theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2} + \cdots + \theta_{n}x_{n}$
   • $J(\theta) = \frac{1}{2m} \sum_{i = 1}^{m} (h_{\theta}(x^{(i)})-y^{(i)})^{2}$


2. Hypothesis & Cost function(Vectorized)
   • $h_{\theta}(X) = X\theta$
   • $J(\theta) = \frac{1}{2m} \begin{Vmatrix} X\theta - Y \end{Vmatrix}^{2} = (\frac{1}{2m})(X\theta - Y)^{T}(X\theta - Y)$


3. Gradient descent
   • $ \begin{cases} \frac{\partial J(\theta)}{\partial \theta_{0}} = \frac{1}{m} \sum_{i = 1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})\\ \frac{\partial J(\theta)}{\partial \theta_{1}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{1}^{(i)}]\\ \frac{\partial J(\theta)}{\partial \theta_{2}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{2}^{(i)}]\\ \quad\quad\quad\quad\quad\quad\quad\quad\vdots\\ \frac{\partial J(\theta)}{\partial \theta_{n}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{n}^{(i)}] \end{cases}$
   • $ \left\{\begin{matrix} \theta_{0} := \theta_{0} - \alpha\frac{\partial J(\theta)}{\partial \theta_{0}}\\ \theta_{1} := \theta_{1} - \alpha\frac{\partial J(\theta)}{\partial \theta_{1}}\\ \vdots \\ \theta_{n} := \theta_{n} - \alpha\frac{\partial J(\theta)}{\partial \theta_{n}}\\ \end{matrix}\right.$
   • Summary : For all $1 \leq i \leq m$ and $0 \leq j \leq n$ , let $x_{0}^{(i)} = 1$, then $\begin{cases} \frac{\partial J(\theta)}{\partial \theta_{j}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{j}^{(i)}]\\ \theta_{j} := \theta_{j} - \alpha\frac{\partial J(\theta)}{\partial \theta_{j}}\\ \end{cases}$


4. Gradient descent(Vectorized)
   • $ \begin{bmatrix} \theta_{0}\\ \theta_{1}\\ \vdots\\ \theta_{n} \end{bmatrix} := \begin{bmatrix} \theta_{0}\\ \theta_{1}\\ \vdots\\ \theta_{n} \end{bmatrix} - (\frac{\alpha}{m}) \begin{bmatrix} 1 & 1 & \cdots & 1\\ x_{1}^{(1)} & x_{1}^{(2)} & \cdots & x_{1}^{(m)}\\ \vdots & \vdots & & \vdots\\ x_{n}^{(1)} & x_{n}^{(2)} & \cdots & x_{n}^{(m)}\\ \end{bmatrix} \begin{bmatrix} \theta_{0} + \theta_{1}x_{1}^{(1)} + \cdots + \theta_{n}x_{n}^{(1)} - y^{(1)}\\ \theta_{0} + \theta_{1}x_{1}^{(2)} + \cdots + \theta_{n}x_{n}^{(2)} - y^{(2)}\\ \vdots\\ \theta_{0} + \theta_{1}x_{1}^{(m)} + \cdots + \theta_{n}x_{n}^{(m)} - y^{(m)} \end{bmatrix}$
   • Summary : $\theta := \theta - (\frac{\alpha}{m})X^{T}(X\theta - Y)$


5. Normal equation
   • $\theta := (X^{T}X - \lambda L)^{-1}X^{T}Y$ where $L = \begin{bmatrix} 0 & & & &\\ & 1 & & &\\ & & 1 & &\\ & & & \ddots & \\ & & & & 1 \end{bmatrix}$
   
   

   • Gradient Descent	Normal Equation
     Need to choose $\alpha$	No need to choose $\alpha$
     Needs many iterations	No need to iterate
     $O(kn^{2})$	$O(n^{3})$, need to calculate inverse of $(X^{T}X + \lambda L)$
     Works well when n is large	Slow if n is very large



6. Extending - polynomial regression
   • Add some ploynomial features in hypothesis function $h_{\theta}(x)$ , such as $h_{\theta}(x) = x_{1} + x_{2} + x_{1}x_{2}$
   • In this case,we can regard $x_{1}x_{2}$ as feature $x_{3}$ and change polynomial regression problem into linear regression problem.

Logistic regression

1. Hypothesis & Cost function
   • $h_{\theta}(x) = \sigma(\theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2} + \cdots + \theta_{n}x_{n}) =\frac{1}{1 + e^{-(\theta_{0} + \theta_{1}x_{1} + \theta_{2}x_{2} + \cdots + \theta_{n}x_{n})}}$
   • $J(\theta) = (-\frac{1}{m})\sum_{i = 1}^{m}[y^{(i)}\log h_{\theta}(x^{(i)}) + (1 - y^{(i)})\log(1 - h_{\theta}(x^{(i)}))]$


2. Hypothesis & Cost function(Vectorized)
   • $h_{\theta}(X) = \sigma(X\theta)$
   • $J(\theta) = (-\frac{1}{m})[Y^{T}\log(h_{\theta}(X)) + (1 - Y)^{T}\log(1 - h_{\theta}(X))]$


3. Gradient descent
   • $ \begin{cases} \frac{\partial J(\theta)}{\partial \theta_{0}} = \frac{1}{m} \sum_{i = 1}^{m} (h_{\theta}(x^{(i)}) - y^{(i)})\\ \frac{\partial J(\theta)}{\partial \theta_{1}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{1}^{(i)}]\\ \frac{\partial J(\theta)}{\partial \theta_{2}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{2}^{(i)}]\\ \quad\quad\quad\quad\quad\quad\quad\quad\vdots\\ \frac{\partial J(\theta)}{\partial \theta_{n}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{n}^{(i)}] \end{cases}$
   • $ \left\{\begin{matrix} \theta_{0} := \theta_{0} - \alpha\frac{\partial J(\theta)}{\partial \theta_{0}}\\ \theta_{1} := \theta_{1} - \alpha\frac{\partial J(\theta)}{\partial \theta_{1}}\\ \vdots \\ \theta_{n} := \theta_{n} - \alpha\frac{\partial J(\theta)}{\partial \theta_{n}}\\ \end{matrix}\right.$
   • Summary : For all $1 \leq i \leq m$ and $0 \leq j \leq n$ , let $x_{0}^{(i)} = 1$, then $\begin{cases} \frac{\partial J(\theta)}{\partial \theta_{j}} = \frac{1}{m} \sum_{i = 1}^{m} [(h_{\theta}(x^{(i)}) - y^{(i)})x_{j}^{(i)}]\\ \theta_{j} := \theta_{j} - \alpha\frac{\partial J(\theta)}{\partial \theta_{j}}\\ \end{cases}$


4. Gradient descent(Vectorized)
   • $ \begin{bmatrix} \theta_{0}\\ \theta_{1}\\ \vdots\\ \theta_{n} \end{bmatrix} := \begin{bmatrix} \theta_{0}\\ \theta_{1}\\ \vdots\\ \theta_{n} \end{bmatrix} - (\frac{\alpha}{m}) \begin{bmatrix} 1 & 1 & \cdots & 1\\ x_{1}^{(1)} & x_{1}^{(2)} & \cdots & x_{1}^{(m)}\\ \vdots & \vdots & & \vdots\\ x_{n}^{(1)} & x_{n}^{(2)} & \cdots & x_{n}^{(m)}\\ \end{bmatrix} \begin{bmatrix} \frac{1}{1 + e^{-(\theta_{0} + \theta_{1}x_{1}^{(1)} + \cdots + \theta_{n}x_{n}^{(1)})}} - y^{(1)}\\ \frac{1}{1 + e^{-(\theta_{0} + \theta_{1}x_{1}^{(2)} + \cdots + \theta_{n}x_{n}^{(2)})}} - y^{(2)}\\ \vdots\\ \frac{1}{1 + e^{-(\theta_{0} + \theta_{1}x_{1}^{(m)} + \cdots + \theta_{n}x_{n}^{(m)})}} - y^{(m)} \end{bmatrix}$
   • Summary : $\theta := \theta - (\frac{\alpha}{m})X^{T}(\sigma(X\theta) - Y)$


5. Calculation process
   • Let $z^{(i)} = \theta_{0} + \theta_{1}x_{1}^{(i)} + \theta_{2}x_{2}^{(i)} + \cdots + \theta_{n}x_{n}^{(i)}$ , we have $J(\theta) = (-\frac{1}{m})\sum_{i = 1}^{m}[y^{(i)}\log\sigma(z^{(i)}) + (1 - y^{(i)})\log(1 - \sigma(z^{(i)}))]$
   • $\frac{\partial J(\theta)}{\partial \theta_{j}} = (-\frac{1}{m})\sum_{i = 1}^{m}\left(\frac{\partial J(\theta)}{\partial \sigma(z^{(i)})}\frac{\partial \sigma(z^{(i)})}{\partial z^{(i)}}\frac{\partial z^{(i)}}{\partial \theta_{j}}\right)$
   • $\frac{\partial J(\theta)}{\partial \sigma(z^{(i)})} = \frac{y^{(i)}}{\sigma(z^{(i)})} - \frac{1 - y^{(i)}}{1 - \sigma(z^{(i)})}$
   • $\frac{\partial \sigma(z^{(i)})}{\partial z^{(i)}} = \frac{e^{-z^{(i)}}}{(1 + e^{-z^{(i)}})^{2}} = \sigma(z^{(i)})(1 - \sigma(z^{(i)}))$
   • $\frac{\partial z^{(i)}}{\partial \theta_{j}} = x_{j}^{(i)}$
   • $ \begin{align*} \frac{\partial J(\theta)}{\partial \theta_{j}} & = (-\frac{1}{m})\sum_{i = 1}^{m}\left\{\left(\frac{y^{(i)}}{\sigma(z^{(i)})} - \frac{1 - y^{(i)}}{1 - \sigma(z^{(i)})}\right)\left[\sigma(z^{(i)})(1 - \sigma(z^{(i)}))\right](x_{j}^{(i)})\right\}\\ & = (-\frac{1}{m})\sum_{i = 1}^{m} \left\{[y^{(i)}(1 - \sigma(z^{(i)})) - (1 - y^{(i)})\sigma(z^{(i)})]x_{j}^{(i)}\right\}\\ & = (-\frac{1}{m})\sum_{i = 1}^{m}[(y^{(i)} - \sigma(z^{(i)}))x_{j}^{(i)}]\\ & = \frac{1}{m}\sum_{i = 1}^{m}[(h_{\theta}(x^{(i)}) - y^{(i)})x_{j}^{(i)}]\\ \end{align*}$

Neuron network

1. Notation
   • $l$ : number of layers in neuron network
   • $n_{[k]}$ : number of neurons in k-th layer.
   • $a^{[k]}(z)$ : activate function in k-th layer.
   • $\hat{a}_{j}^{(i)[k]}$ : j-th activate value of i-th training sample in k-th layer.
   • $\theta_{i}^{[k]} = \begin{bmatrix} \theta_{i1}^{[k]} & \theta_{i2}^{[k]} & \cdots & \theta_{in_{[k - 1]}}^{[k]} \end{bmatrix}$ : parameters for caculating i-th activate value in k-th layer.
   • $b_{i}^{[k]}$ : bias for caculating i-th activate value in k-th layer.
   • For convenient, we regard input layer as layer $0$ and output layer as layer $l$ and regard input features as activate values in layer $0$.


2. Notation(Vectorized)
   • $A^{[k]} = \begin{bmatrix} \mid & \mid & & \mid\\ A^{(1)[k]} & A^{(2)[k]} & \cdots & A^{(m)[k]}\\ \mid & \mid & & \mid \end{bmatrix}$ , where $A^{(i)[k]} = \begin{bmatrix} \hat{a}_{1}^{(i)[k]}\\ \hat{a}_{2}^{(i)[k]}\\ \vdots\\ \hat{a}_{n_{[k]}}^{(i)[k]}\\ \end{bmatrix}$
   • $\Theta^{[k]} = \begin{bmatrix} -\;\theta_{1}^{[k]}\;-\\ -\;\theta_{2}^{[k]}\;-\\ \vdots\\ -\;\theta_{n_{k}}^{[k]}\;- \end{bmatrix}$
   • $B^{[k]} = \overbrace{ \begin{bmatrix} \mid & \mid & & \mid\\ b^{[k]} & b^{[k]} & \cdots & b^{[k]}\\ \mid & \mid & & \mid \end{bmatrix} }^{m\text{ times}}$ , where $b^{[k]} = \begin{bmatrix} b_{1}^{[k]}\\ b_{2}^{[k]}\\ \vdots\\ b_{n_{[k]}}^{[k]}\\ \end{bmatrix}$
   • $ \begin{cases} A^{[k]} \in \mathbb{R}^{n_{[k]} \times m}\\ \Theta^{[k]} \in \mathbb{R}^{n_{[k]} \times n_{[k-1]}}\\ B^{[k]} \in \mathbb{R}^{n_{[k]} \times m}\\ \end{cases}$


3. Forward propagation
   • for($1 \leq k \leq l$){
       $ \begin{align*} &Z^{[k]} = \Theta^{[k]}A^{[k - 1]} + B^{[k]}\\ &A^{[k]} = a^{[k]}\left(Z^{[k]}\right ) \end{align*}$
     }