brief overview of machine learning

Contents

Content

NN

At the first, we use the model

h (x, θ)

$h(x, \theta)$

$h$ can be one layer or multiply layer.

[X, Y] = [x^{(i)}, y^{(i)}]_{i = 1, 2, \dots, m} x^{(i)} \in R^{n} y^{(i)} \in R^{1}

$[\mathcal{X},\mathcal{Y}] = [x^{(i)},y^{(i)}]_{i=1,2,\dots,m} \\ x^{(i)} \in \mathbb{R}^{n} \\ y^{(i)} \in \mathbb{R}^{1}$

Loss function

J (θ) = \frac{1}{2} [\sum_{i = 1}^{m} (h (x^{(i)}, θ) - y^{(i)})^{2}]

$J(\theta) = \frac{1}{2} \left[ \sum\limits_{i=1}^{m}(h(x^{(i)},\theta) - y^{(i)})^{2} \right]$

Derivation

\frac{\partial J (θ)}{\partial θ} = \sum_{i = 1}^{m} [(h (x^{(i)}, θ) - y^{(i)}) \frac{\partial h (x^{(i)}, θ)}{\partial θ}] \frac{\partial^{2} J (θ)}{\partial θ^{2}} = \sum_{i = 1}^{m} [{(\frac{\partial h (x^{(i)}, θ)}{\partial θ})}^{2} + (h (x^{(i)}, θ) - y^{(i)}) \frac{\partial^{2} h (x^{(i)}, θ)}{\partial θ^{2}}]

$\frac{\partial J(\theta)}{\partial \theta} = \sum\limits_{i=1}^{m}\left[ (h(x^{(i)},\theta) - y^{(i)})\frac{\partial h(x^{(i)}, \theta)}{\partial \theta} \right] \\ \frac{\partial^{2} J(\theta)}{\partial \theta^{2}} = \sum\limits_{i=1}^{m}\left[ \left( \frac{\partial h(x^{(i)}, \theta)}{\partial \theta} \right)^{2} + (h(x^{(i)},\theta) - y^{(i)})\frac{\partial^{2} h(x^{(i)}, \theta)}{\partial \theta^{2}} \right]$

When $h$ is only Linear Regression, the we can get

\frac{\partial^{2} J (θ)}{\partial θ^{2}} \geq 0

$\frac{\partial^{2} J(\theta)}{\partial \theta^{2}} \geq 0$

It follows that Linear Regression must be convex.

We assume difference

ε^{(i)} = h (x^{(i)}, θ) - y^{(i)}

$\varepsilon^{(i)} = h(x^{(i)}, \theta) - y^{(i)}$

then we think it obeys the normal distribution, and we assume the mean is 0.

ε \sim N (0, σ^{2}) P (ε^{(i)}) = \frac{1}{\sqrt{2 π} σ} \exp (- \frac{(ε^{(i)} - 0)^{2}}{2 σ^{2}})

$\varepsilon \sim N(0, \sigma^{2}) \\ P(\varepsilon^{(i)}) = \frac{1}{\sqrt{2 \pi} \sigma} \exp{\left( -\frac{(\varepsilon^{(i)} -0)^{2}}{2 \sigma^{2}} \right)}$

It implies that

P (y^{(i)} | x^{(i)}; θ) = \frac{1}{\sqrt{2 π} σ} \exp (- \frac{((h (x^{(i)}, θ) - y^{(i)}) - 0)^{2}}{2 σ^{2}})

$P(y^{(i)}|x^{(i)};\ \theta) = \frac{1}{\sqrt{2 \pi} \sigma} \exp{\left( -\frac{((h(x^{(i)}, \theta) - y^{(i)}) -0)^{2}}{2 \sigma^{2}} \right)}$

It is hard to understand how to convert the before formula to the after formula.

Likelihood function

\begin{aligned} L (θ) & = \prod_{i = 1}^{m} P (y^{(i)} | x^{(i)}; θ) \\ = \prod_{i = 1}^{m} \frac{1}{\sqrt{2 π} σ} \exp (- \frac{(h (x^{(i)}, θ) - y^{(i)})^{2}}{2 σ^{2}}) \end{aligned}

$\begin{align} L(\theta) &= \prod\limits_{i=1}^{m}P(y^{(i)}|x^{(i)};\ \theta) \\ & = \prod\limits_{i=1}^{m} \frac{1}{\sqrt{2 \pi} \sigma} \exp{\left( -\frac{(h(x^{(i)}, \theta) - y^{(i)})^{2}}{2 \sigma^{2}} \right)} \end{align}$

The more larger $L$ is, the more similar the $h(x)$ is to $f(x)$ .

Then we can get the follow formula from $L$

The action that we maximize $\log(L)$ is equivalent to that we maximize $L$ .

\begin{aligned} \log (L (θ)) & = \log (\prod_{i = 1}^{m} \frac{1}{\sqrt{2 π} σ} \exp (- \frac{(h (x^{(i)}, θ) - y^{(i)})^{2}}{2 σ^{2}})) \\ = \sum_{i = 1}^{m} \log [\frac{1}{\sqrt{2 π} σ} \exp (- \frac{(h (x^{(i)}, θ) - y^{(i)})^{2}}{2 σ^{2}})] \\ = \sum_{i = 1}^{m} \log \frac{1}{\sqrt{2 π} σ} + \sum_{i = 1}^{m} (- \frac{(h (x^{(i)}, θ) - y^{(i)})^{2}}{2 σ^{2}}) \end{aligned}

$\begin{align} \log(L(\theta)) &= \log\left( \prod\limits_{i=1}^{m} \frac{1}{\sqrt{2 \pi} \sigma} \exp{\left( -\frac{(h(x^{(i)}, \theta) - y^{(i)})^{2}}{2 \sigma^{2}} \right)} \right)\\ &= \sum\limits_{i=1}^{m}\log \left[\frac{1}{\sqrt{2 \pi} \sigma} \exp{\left( -\frac{(h(x^{(i)}, \theta) - y^{(i)})^{2}}{2 \sigma^{2}} \right)} \right] \\ & = \sum\limits_{i=1}^{m}\log\frac{1}{\sqrt{2 \pi} \sigma} + \sum\limits_{i=1}^{m}\left( -\frac{(h(x^{(i)}, \theta) - y^{(i)})^{2}}{2 \sigma^{2}} \right) \end{align}$

Conclusion

The less difference between $h(x, model)$ and $y$ , the bigger the function $L$ is, in other words, the model fit $f(x)$ very well near the points $[x_i, y_i]$ .
When the difference between $h(x, model)$ and $y$ is small enough, the more smaller variance is, the bigger the function $L$ is also. Please pay attention to it, the model fit $f(x)$ very well in this case, not just near the points $[x_i, y_i]$ .

Cross-Entropy

Let us consider binary classification.

Sigmoid

x, θ \in R^{n} h : R^{n} ⟶ [0, 1] h_{θ} (x) = \frac{1}{1 + e^{- θ^{T} x}}

$x,\theta\in \mathbb{R}^{n} \\ h : \mathbb{R}^{n} \longrightarrow [0, 1] \\ h_{\theta}(x) = \frac{1}{1+e^{-\theta^{T} x}}$

Let us assume that

P (y = 1 | x; θ) = h_{θ} (x) P (y = 0 | x; θ) = 1 - h_{θ} (x)

$P(y=1 | x \ ; \ \theta) = h_{\theta}(x) \\ P(y=0 | x \ ; \ \theta) = 1-h_{\theta}(x) \\$

Then

\begin{aligned} P (y | x; θ) & = [h_{θ} (x)]^{y} \cdot [1 - h_{θ} (x)]^{1 - y} \\ y = 1 & ⟹ P (y = 1 | x; θ) = [h_{θ} (x)]^{1} \cdot [1 - h_{θ} (x)]^{1 - 1} = h_{θ} (x) \\ y = 0 & ⟹ \dots \end{aligned}

$\begin{align} P(y|x\ ; \ \theta)&=[h_{\theta}(x)]^{y}\cdot [1-h_{\theta}(x)]^{1-y} \\ y=1 &\Longrightarrow P(y=1|x;\theta)=[h_{\theta}(x)]^{1}\cdot [1-h_{\theta}(x)]^{1-1} = h_{\theta}(x) \\ y = 0 &\Longrightarrow \cdots \end{align}$

Likelihood function

\begin{aligned} L & = \prod_{i = 1}^{m} P (y^{(i)} | x^{(i)}; θ) \\ = \prod_{i = 1}^{m} [h_{θ} (x^{(i)})]^{y^{(i)}} \cdot [1 - h_{θ} (x^{(i)}))]^{1 - y^{(i)}} \end{aligned}

$\begin{align} L &= \prod\limits_{i=1}^{m} P(y^{(i)}|x^{(i)}; \theta ) \\ &=\prod\limits_{i=1}^{m} [h_{\theta}(x^{(i)})]^{y^{(i)}}\cdot [1-h_{\theta}(x^{(i)}))]^{1-y^{(i)}} \end{align}$

Log likelihood function

\log L = \sum_{i = 1}^{m} y^{(i)} \log h_{θ} (x^{(i)}) + (1 - y^{(i)}) \log (1 - h_{θ} (x^{(i)}))

$\log L = \sum\limits_{i=1}^{m}y^{(i)}\log{h_{\theta}(x^{(i)})} + (1-y^{(i)})\log{(1-h_{\theta}(x^{(i)}))}$

iterative formula

θ_{j} = θ_{j} + α (y^{(i)} - h_{θ} (x^{(i)})) x_{j}^{(i)}

$\theta_{j} = \theta_{j} + \alpha (y^{(i)}-h_{\theta}(x^{(i)}))x_{j}^{(i)}$

Softmax

θ^{(i)} \in R^{n}, i = 1, \dots, k p (y^{(i)} | x^{(i)}; θ) = \frac{\exp ({θ^{(y^{(i)})}}^{T} x)}{\sum_{j = 1}^{k} \exp ({θ^{(j)}}^{T} x)} L = \prod_{i = 1}^{m} \frac{\exp ({θ^{(y^{(i)})}}^{T} x)}{\sum_{j = 1}^{k} \exp ({θ^{(j)}}^{T} x)} \log L = \sum_{i = 1}^{m} \log \frac{\exp ({θ^{(y^{(i)})}}^{T} x)}{\sum_{j = 1}^{k} \exp ({θ^{(j)}}^{T} x)}

$\theta^{(i)}\in \mathbb{R}^{n}, \quad i =1,\dots, k \\ p(y^{(i)}|x^{(i)};\theta)=\frac{\exp{(\{\theta^{(y^{(i)})}}\}^{T}x)}{\sum\limits_{j=1}^{k}\exp{(\{\theta^{(j)}}\}^{T}x)} \\ L = \prod\limits_{i=1}^{m} \frac{\exp{(\{\theta^{(y^{(i)})}}\}^{T}x)}{\sum\limits_{j=1}^{k}\exp{(\{\theta^{(j)}}\}^{T}x)} \\ \log L = \sum\limits_{i=1}^{m}\log \frac{\exp{(\{\theta^{(y^{(i)})}}\}^{T}x)}{\sum\limits_{j=1}^{k}\exp{(\{\theta^{(j)}}\}^{T}x)} \\$

Hidden Markov Model (HMM)

\begin{aligned} y_{1} & \to & y_{2} & \to & \dots & \to & y_{i} & \to & y_{n} \\ ↓ & ↓ & ↓ & ↓ \\ x_{1} & x_{2} & \dots & x_{i} & x_{n} \end{aligned}

$\begin{align} & y_1 & \rightarrow & y_2 & \rightarrow &\cdots &\rightarrow & y_i &\rightarrow & y_n \\ & \downarrow & \downarrow & &&& \downarrow && \downarrow \\ & x_1 & & x_2 & &\cdots & & x_i & & x_n \\ \end{align}$

${y_1, y_2, \cdots , y_n}$ : status variable

${s_1,s_2,\cdots,s_N}$ : status space

Y = {s_{1}, s_{2}, \dots, s_{N}} y_{i} \in Y

$\mathcal{Y}=\{s_{1},s_{2},\dots,s_{N}\} \\ y_i \in \mathcal{Y}$

${x_1, x_2, \cdots, x_n}$ : observable variable

${o_1,o_2,\cdots,o_M}$ : observable space

X = {o_{1}, o_{2}, \dots, o_{M}} x_{i} \in X

$\mathcal{X} = \{o_{1},o_{2},\dots,o_{M}\} \\ x_{i} \in \mathcal{X}$

joint probability distribution:

P (x_{1}, y_{1}, \dots, x_{n}, y_{n}) = P (y_{1}) P (x_{1} | y_{1}) \prod_{i = 2}^{n} P (y_{i} | y_{i - 1}) P (x_{i} | y_{i})

$P(x_{1},y_{1},\dots,x_{n},y_{n})=P(y_{1})P(x_{1}|y_1) \prod\limits_{i=2}^{n}P(y_{i}|y_{i-1})P(x_{i}|y_{i})$

state-transition matrix:

A = [a_{i j}]_{N \times N} a_{i j} = P (y_{t + 1} = s_{j} | y_{t} = s_{j})

$A=[a_{ij}]_{N \times N} \\ a_{ij}=P(y_{t+1}=s_{j}|y_{t}=s_{j})$

observable probability matrix:

B = [b_{i j}]_{N \times M} b_{i j} = P (x_{t} = o_{j} | y_{t} = s_{i})

$B=[b_{ij}]_{N \times M} \\ b_{ij}=P(x_{t}=o_{j}|y_{t}=s_{i})$

Initial state probability:

π = (π_{1}, π_{2}, \dots, π_{N}) π_{i} = P (y_{i} = s_{i})

$\pi=(\pi_{1},\pi_{2},\dots,\pi_{N}) \\ \pi_{i}=P(y_{i}=s_{i})$

HMM:

λ = [A, B, π]

$\lambda = [A,B,\pi]$

How to generate the observable series of $[x_1,x_2,\cdots,x_n]$ :

$t = 1$ , getting $y_1$ according to initial state probability.
getting $x{i}$ from $y{i}$ according to $B$ , which is observable probability matrix.
getting $y{i+1}$ from $y{i}$ according to $A$ , which is state-transition matrix.
if $t < n$ , set $t = t+1$ , or not be end.

Markov Random Field (MRF)

Clique (C):

clique

Maximal clique $(C^{*}): {x_1, x_2}, {x_1, x_3}, {x_2, x_4}, {x_3, x_5}, {x_2, x_5, x_6}$

P (x) = \frac{1}{Z} \prod_{Q \in C} ψ_{Q} (x_{Q}) Z = \sum_{x} [\prod_{Q \in C} ψ_{Q} (x_{Q})]

$P(x) = \frac{1}{Z} \prod\limits_{Q\in \mathcal{C}} \psi_{Q}(x_{Q}) \\ Z = \sum\limits_{x} \left[ \prod\limits_{Q\in \mathcal{C}} \psi_{Q}(x_{Q}) \right]$

For convenience, we express the probability with maximal clique $(C^{*})$ .

P (x) = \frac{1}{Z^{*}} \prod_{Q \in C^{*}} ψ_{Q} (x_{Q}) Z^{*} = \sum_{x} [\prod_{Q \in C^{*}} ψ_{Q} (x_{Q})]

$P(x) =\frac{1}{Z^{*}} \prod\limits_{Q\in \mathcal{C}^{*}} \psi_{Q}(x_{Q})\\ Z^{*} = \sum\limits_{x} \left[ \prod\limits_{Q\in \mathcal{C}^{*}} \psi_{Q}(x_{Q}) \right]$

Follow the above picture:

P (x) = \frac{1}{Z} ψ_{12} (x_{1}, x_{2}) ψ_{13} (x_{1}, x_{3}) ψ_{24} (x_{2}, x_{4}) ψ_{35} (x_{3}, x_{5}) ψ_{256} (x_{2}, x_{5}, x_{6})

$P(x) = \frac{1}{Z} \psi_{12}(x_{1}, x_{2})\psi_{13}(x_{1}, x_{3})\psi_{24}(x_{2}, x_{4})\psi_{35}(x_{3}, x_{5})\psi_{256}(x_{2}, x_{5}, x_{6})$

MLP

i n p u t : x_{1}, x_{2} o u t p u t : y_{1} a c t i v e : φ (x)

$input: x_1,x_2\\ output: y_1 \\ active: \varphi(x) \\$

MLP

maxout

Maxout layer will supersede active layer (etc. Relu, Sigmoid).

maxout

maxpooling

RBF network

RBF

The middle layer is the difference between RBF network and BP network.

BP: affine (linear)
RBF: gaussian RBF units (nonlinear):

\exp ({- γ ‖ x - c_{i} ‖}^{2})

$\exp({-\gamma \| x-c_{i} \|}^{2})$

RBF network middle layer only has one layer.

RBF

It has the greatest response at the middle; The reaction is maximal near the middle and the more farther from it the more weaker.

autoencoder

https://www.cs.toronto.edu/~lczhang/360/lec/w05/autoencoder.html

AlexNet

Imagenet classification with deep convolutional neural networks 2012

Prevent overfitting:

Data Augmentation

Generate new data from original data by some simply transformations, e.g. rotation.
Dropout

Regularization

As usual, we have the follow optimization problem:

x \in R^{n}, θ \in R^{m} L (θ) = \frac{1}{2 n} [\sum_{i = 1}^{n} {(h_{θ} (x^{(i)}) - y^{(i)})}^{2}] min L (θ)

$x \in \mathbb{R}^{n}, \ \theta \in \mathbb{R}^{m} \\ L(\theta) = \frac{1}{2n}\left[ \sum\limits_{i=1}^{n}\left( h_{\theta}(x^{(i)}) - y^{(i)} \right)^{2} \right]\\ \min\ L(\theta)$

If model has some parameters are very large, then it will make the model overfitting.

So we should append the decay items (\lambda) to prevent model parameter values to rise too high.

x \in R^{n}, θ \in R^{m} L (θ) = \frac{1}{2 n} [\sum_{i = 1}^{n} {(h_{θ} (x^{(i)}) - y^{(i)})}^{2} + λ \sum_{i = 1}^{m} θ_{i}^{2}] min L (θ)

$x \in \mathbb{R}^{n}, \ \theta \in \mathbb{R}^{m} \\ L(\theta) = \frac{1}{2n}\left[ \sum\limits_{i=1}^{n}\left( h_{\theta}(x^{(i)}) - y^{(i)} \right)^{2} + \lambda \sum\limits_{i=1}^{m} \theta_{i}^{2} \right] \\ \min\ L(\theta)$

Decision tree

Information entropy

E n t (D) = - \sum_{k = 1}^{| Y |} p_{k} \log_{2} p_{k}

$Ent(D)=-\sum\limits_{k=1}^{|\mathcal{Y}|} p_{k} \log_{2}p_{k}$

Information gain

max G a i n (D, a) = E n t (D) - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} E n t (D^{v})

$\max \quad Gain(D, a)=Ent(D) - \sum\limits_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v})$

ID3 algorithm

a^{*} = \arg max_{a \in A} G a i n (D, a)

$a^{*} = \arg\max\limits_{a\in A} Gain(D, a)$

It prefers over items for which the quantities are very filling.

C4.5 algorithm, gain radio

I V (a) = - \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} \log_{2} \frac{| D^{v} |}{| D |} G a i n R a d i o (D, a) = \frac{G a i n (D, a)}{I V (a)}

$IV(a) = -\sum\limits_{v=1}^{V}\frac{|D^{v}|}{|D|}\log_{2}\frac{|D^{v}|}{|D|} \\ GainRadio(D, a)=\frac{Gain(D,a)}{IV(a)}$

It prefers over items for which the quantities are small. The result shows that it will choose the max gain radio from the gain() which are higher than average.

CRAT

\begin{aligned} G i n i (D) & = \sum_{k = 1}^{| Y |} \sum_{k^{'} \neq k} p_{k} p_{k^{'}} \\ = 1 - \sum_{k = 1}^{| Y |} p_{k}^{2} \end{aligned}

$\begin{align} Gini(D)&=\sum\limits_{k=1}^{|\mathcal{Y}|} \sum\limits_{k' \neq k} p_{k}p_{k'} \\ & = 1-\sum\limits_{k=1}^{|\mathcal{Y}|}p_{k}^{2} \end{align}$

G i n i I n d e x (D, a) = \sum_{v = 1}^{V} \frac{| D^{v} |}{| D |} G i n i (D^{v})

$GiniIndex(D, a)=\sum\limits_{v=1}^{V}\frac{|D^{v}|}{|D|}Gini(D^{v})$

a^{*} = \arg min_{a \in A} G i n i I n d e x (D, a)

$a^{*}=\arg\min\limits_{a\in A} GiniIndex(D, a)$

Requirement

It needs labels

Bagging and Random Forest

Bagging, we can separate the dataset into $T$ subsets which has m examples. Then $T$ prototype models can individually be trained out. When test data need to be predicted, we put the data into the $T$ subsets and refer the max confidence model as the predicted result.

Random forest, it is the same as Bagging, except it used decision tree to choose ultimate model.

Knowledge Graph

In knowledge representation and reasoning, knowledge graph is a knowledge base that users a graph-structured data model or topology to integrate data. Knowledge graphs are often used to store interlink descriptions of entities - objects, events, situations or abstract concepts - while also encoding the semantics underlying the used terminology.

Since the development of Semantic Web, knowledge graphs are often associated with linked open data projects, focusing on the connections between concepts and entities. They are also prominently associated with and used by search engines such as Google, Bing, and Yahoo; knowledge-engines and question-answering services such as WolframAlpha, Apple's Siri, and Amazon Alexa; and social networks such as Linkedin and facebook.

Singhal, Amit (May 16, 2012). "Introducing the Knowledge Graph: things, not strings". Official Google Blog. Retrieved 21 March 2017.
[Jens Lehmann et al., 2015] DBpedia: A Large-scale, Multilingual Knowledge Base Extracted from Wikipedia.
[Fabian, M. S. et al. 2007] Yago: A core of semantic knowledge unifying wordnet and wikipedia
[Roberto Navigli et. al., 2012] BabelNet: The automatic construction, evaluation and application of a wide-coverage multilingual semantic network
[Banko et al. 2007] "Open information extraction from the web." IJCAI. Vol. 7. 2007.
[Newell, Allen et al. 1976] “Computer Science as Empirical Inquiry: Symbols and Search”, Communications of the ACM, 19 (3)

Appendices

Model averaging

Each neural node has averaging weight, and prevents to exist heavy nodes.

We want get the model like:

Averaging

instead of:

Averaging2

Bayes theorem

P (A B) = P (A) P (B | A) P (A | B) P (B) = P (A) P (B | A)

$P(AB)=P(A)P(B|A) \\ P(A|B)P(B)=P(A)P(B|A)$

Brief overview of machine learning

Content

NN

Cross-Entropy

Hidden Markov Model (HMM)

Markov Random Field (MRF)

MLP

maxout

maxpooling

RBF network

autoencoder

AlexNet

Regularization

Decision tree

Bagging and Random Forest

Knowledge Graph

Appendices

Model averaging

Bayes theorem