Machine learning (Part 1)

machine learning （1）

machine learning ：

pattern recognition

Computer vision

data mining

speech recognition

Statistical learning

natural language processing

1. The training sample
2. feature extraction
3. Learn functions
4. forecast

• With supervision problems ： Yes label

• Unsupervised problems ： nothing label

• Return to ： Output specific values

• classification ： Problems classified

Linear regression

$h_{\theta }(x)={\theta }_0+{\theta }_1{x}_1+{\theta }_2{x}_2$

$h_{\theta }(x)=\sum _{i=0}^n{\theta }_i{x}_i={\theta }^{T}x$

$y^{(i)}={\theta }^T{x}^{(i)}+{\varsigma }^{(i)}$

The error is Independent and with the same distribution It is generally believed that the mean value is 0 The variance of ${\theta }^2$ Gaussian distribution of

$p({\varsigma }^{(i)})=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{{\varsigma }^{(i{)}^2}}{2{\sigma }^2})$

$p(y^{(i)}|x^{(i)};\theta )=\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2})$

Maximum likelihood function ：
$$\begin{gathered} L(\theta )=\prod _{i=1}^{m}p(y^{(i)}|x^{(i)};\theta ) \\ =\prod _{i=1}^{m}p(y^{(i)}|x^{(i)};\theta )\frac{1}{\sqrt{2\pi }\sigma }exp(-\frac{(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2}{2{\sigma }^2}) \end{gathered}$$
On demand requirements $\arg \max (L(\theta ))$

$l(\theta )=logL(\theta )$

$l(\theta )=m\log \frac{1}{\sqrt{2\pi }\sigma }-\frac{1}{{\sigma }^2}.\frac{1}{2}\sum _{i=1}^m(y^{(i)}-{\theta }^T{x}^{(i)}{)}^2$

$J(\theta )=\frac{1}{2}\sum _{i=1}^m(h_{\theta }(x^{(i)})-y^{(i)}{)}^2$

On demand requirements $arg\min J(\theta )$

$$\begin{gathered} J(\theta )=\frac{1}{2}(X\theta -y{)}^T(X\theta -y) \\ {\nabla }_{\theta }J(\theta )={\nabla }_{\theta }(\frac{1}{2}({\theta }^T{X}^T-y^T)(X\theta -y)) \\ ={\nabla }_{\theta }(\frac{1}{2}({\theta }^T{X}^{T}X\theta -{\theta }^T{X}^{T}y-y^{T}X\theta +y^{t}y)) \\ =X^{T}X\theta -X^{T}y \\ \theta =(X^{T}X{)}^{-1}{X}^{T}y \end{gathered}$$

Logical regression

Available for classification （ Two classification ） And return

$h_{\theta }(x)=g({\theta }^{T}x)=\frac{1}{1+e^{-{\theta }^{T}x}}$

Value range [0,1]

$h_{\theta }(x{)}^{{}^{\prime }}=h(x)(1-h(x))$

Gradient descent is used for optimization

You don't have to find the derivative

Decision trees and random forests

Classification algorithm

The tree structure represents the results of data classification

• The root node
• Nonleaf node （ Decision point ）
• Leaf node （ Classification marks ）
• Branch （ Test results ）

Training phase

Classification stage

The two events are independent of each other ：$P(X,Y)=P(X)\ast P(Y)$$Log(XY)=Log(X)+Log(Y)$

Start at the root , Start sorting layer by layer .

It is necessary to use entropy to judge who is the node with low level

$H(x)$ As the uncertainty of the event , The level of internal chaos

$P(A\; fewrateThe\; moreBig)->H(X)valueThe\; moreSmall$

$P(A\; fewrateThe\; moreSmall)->H(X)valueThe\; moreBig$

entropy = $-\sum _{i=1}^n{p}_{i}ln(P_i)$

$GinisystemCount=Gini(p)=\sum _{i=1}^K{p}_k(1-p_k)=1-\sum _{k=1}^K{p}_k^2$

p The bigger it is , Entropy sum Gini The smaller the coefficient

The basic idea of constructing decision tree

The basic idea of constructing a tree is to increase the depth of the tree , The entropy of nodes decreases rapidly .

The faster entropy decreases, the better , Can make the depth smaller

After each division , The sum of entropy of a set is the smallest and the best , Can result in maximum information gain , Make the information entropy drop the fastest

The version of the decision tree

ID3： Information gain

C4.5： Information gain rate

CART：Gini coefficient

ID3 defects ：

The information gain rate is too large ： Too many samples , The number of samples per sample is small

Evaluation function ：$C(T)=\sum _{t\in leaf}{N}_{t}H(t)$$N_t$ Weight value ,$H(t)$ Entropy

The smaller the evaluation function, the better , Similar to the loss function

Able to handle continuous attributes , Firstly, the continuous attribute is discretized , Divide the values of continuous attributes into different intervals

Consideration of missing data ： Build decision tree , Loss data can be ignored , When calculating the gain , Only records with attribute values are considered

Decision tree pruning

pre-pruning ： The process of building a decision tree , Early termination （ Prevent over fitting ）

After pruning ： After the decision tree structure is built , Just started cutting

$C_{\alpha }(T)=C(T)+\alpha |T_{leaf}|$ The more leaf nodes there are , The greater the loss

Random forests

Bootstrapping： There is a return sample

Bagging： There is a return sample n A total of samples are used to build classifiers

A decision tree makes the same decision together

Random ： What percentage of the samples are randomly selected for training , Randomly selected features

Bayesian algorithm

Bayes' formula

$P(A|B)=\frac{P(B|A)P(A)}{P(B)}$

Spelling correction

Spam filtering

Model comparison theory

maximum likelihood ： Most consistent with observed data （$P(h|D)$ The biggest advantage ） The greater the posterior probability, the more advantageous

Okam razor ：$P(h)$ Larger models have greater advantages The greater the prior probability, the better , Higher order polynomials are less common

Naive Bayes ： Features are independent of each other , They don't influence each other

Xgboost

Ensemble classifiers

Predictive value ：$\widehat{y_i}={\sum }_j{w}_j{x}_{ij}$

Objective function ：$l(y_i,\widehat{y_i})=(y_i-\widehat{y_i}{)}^2$

Optimal solution ：$F^{\ast }(x)=\arg \min E_{(x,y)}[L(y,F(x))]$

The basic idea ： It means that every tree added will be improved on the original basis

${\widehat{y_i}}^{(0)}=0$

${\widehat{y_i}}^{(1)}=f_1(x_i)={\widehat{y_i}}^{(0)}+f_1(x_i)$

${\widehat{y_i}}^{(t)}=\sum _{k=1}^t{f}_k(x_i)={\widehat{y_i}}^{(t-1)}+f_t(x_i)$

It is equivalent to t Wheel model prediction , Keep the front $t-1$ Wheel model prediction , Add a new function

Penalty item ：$\Omega (f_t)=\gamma T+\frac{1}{2}\lambda \sum _{j=1}^T{w}_j^2$ For every tree

The first term is the number of leaf nodes , The latter term is the penalty term of regularization , Constitute the total loss function

$ob{j}^{(t)}=\sum _{i=1}^{n}l(y_i,{\widehat{y_i}}^{(t)})+{\sum }_{i=1}^t\Omega (f_i)$

​ $=\sum _{i=1}^{n}l(y_i,{\widehat{y_i}}^{(t-1)}+f_t(x_i))+\Omega (f_t)+c$

Goals need to be found $f_t$ To optimize your goals

Optimization with Taylor expansion

$ob{j}^{(t)}={\sum }_{i=1}^n[l(y_i,{\widehat{y_i}}^{(t-1)})+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i)]+\Omega (f_t)+const$

$g_i$ First order conductance ,$h_i$ The two order derivative.

Into traversal of leaf nodes

$ob{j}^{(t)}={\sum }_{i=1}^n[g_i{w}_q(x_i)+\frac{1}{2}{h}_i{w}_{q(x_i)}^2]+\gamma T+\lambda \frac{1}{2}{\sum }_{j=1}^T{w}_j^2$

​ $={\sum }_{j=1}^T[({\sum }_{i\in I_j}{g}_i)w_j+\frac{1}{2}({\sum }_{i\in I_j}{h}_i+\lambda )w_j^2]+\gamma T$

$G_j={\sum }_{i\in I_j}{g}_i$$H_j={\sum }_{i\in I_j}{h}_i$

$ob{j}^{(t)}={\sum }_{i=1}^T[G_j{w}_j+\frac{1}{2}(H_j+\lambda w_j^2)]+\gamma T$

Partial derivative =0

To calculate the $w_j=-\frac{G_j}{H_j+\lambda }$

$Obj=-\frac{1}{2}{\sum }_{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$

Whether to perform the segmentation between the left node and the right node

Calculate the difference after segmentation

$Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }-\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }]-\gamma$

Adaboost

Adaptive enhancement

The wrong samples of the previous classifier will be strengthened , After weighting, all samples are used to train the next basic classifier . meanwhile , A new weak classifier is added in each round , Until a predetermined error rate small enough is reached , Or the maximum number of iterations specified in advance

Finally, the new classifier is weighted by multiple classifiers

1. Initialize the weight distribution of the data , At the beginning, all samples have the same weight
2. Train weak classifiers , If a sample is not accurately classified , Then increase its weight ; If correctly classified , Lower the weight
3. The weak classifiers are weighted and combined into strong classifiers

Support vector machine

Classification problem

Suppose there is a hyperplane ：$w^{T}x+b=0$

There are two points on the hyperplane ：$x^{{}^{\prime }}{x}^{{}^{\prime \prime }}$ Satisfy $w^T{x}^{{}^{\prime }}=-b{w}^T{x}^{{}^{\prime \prime }}=-b$

The normal vector of the plane w：$w^T(x^{{}^{\prime \prime }}-x^{{}^{\prime }})=0$

$x^{\prime \prime }and{x}^{\prime }$ It's in vector form

distance(point to line)=$\frac{w^T}{||w||}(x-x^T)$=$\frac{1}{||w||}|w^{T}x+b|$

SVM In classification , In the right time $y=1$, Negative examples $y=-1$

This will satisfy $y_{i}y(x_i)>0$

Find a straight line , Make the point closest to the line farther away ：

$\underset{w,b}{\arg }\max (\min \frac{y_i(w^T{x}_i+b)}{||w||})$

By retracting ：$y_i(w^T{x}_i+b)\ge 1$

You need to ask for $ma{x}_{w,b}\frac{1}{||w||}$

To find the minimum ${\min }_{w,b}\frac{1}{2}{w}^2$ And $y_i(w^T{x}_i+b)\ge 1$

Using Lagrange multipliers ：

$L(w,b,\alpha )=\frac{1}{2}||w|{|}^2-\sum _{i=1}^n{\alpha }_i(y_i(w^T{x}_i+b)-1)$

The dual problem ：$\underset{w,b}{\min }\underset{\alpha }{\max }L(w,b,\alpha )>\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$

Respectively for w and b Finding partial derivatives , We get two conditions respectively

$\frac{\partial L}{\partial w}=0$ -> $w=\sum _{i=1}^n{\alpha }_i{y}_i{x}_n$

$\frac{\partial L}{\partial b}=0$ -> $\sum _{i=1}^n{\alpha }_i{y}_i=0$

In the face of $\alpha$ Just ask for the derivative

Lagrange multiplier method

$\min f(x)$

$s.t.g_i(x)\le 0i=1,\dots ,m$

The support vector determines the point of the split face , Determines the interval separation hyperplane

Soft space

Individual points affect the separation of the entire hyperplane

Introduce relaxation factor , It becomes a soft interval problem

$y_i(w{x}_i+b)\ge 1-{\epsilon }_i$

Objective function ：$\min \frac{1}{2}||w|{|}^2+C\sum _{i=1}^n{\epsilon }_i$

When C Approaching infinity ： It means that there should be no mistakes in the classification

When C Close to very little ： It means that there can be greater tolerance for mistakes

Kernel function

Mapping from low dimensional space to high dimensional space

The benefits of kernel functions ： Calculate the inner product of high-dimensional samples in a low dimensional space

It can be simplified as inner product in low dimension to map the result to high dimension

The result is the same as that of inner product in high dimension

Gaussian kernel

$K(X,Y)=exp\{\frac{||X-Y|{|}^2}{2{\sigma }^2}\}$

ARIMA

Stability ：

• Stationarity is the fitting curve obtained through the sample time series , In the future, we can still follow the existing form “ inertia ” To continue
• Stationarity requires that the mean and variance of the sequence do not change significantly

Strict stability and weak stability ：

• Yan pingwen ： The distribution of strict stationary representation does not change with time . White noise ： No matter how you take , Expectation is 0, The variance is 1
• Weakly stationary ： Expectation and correlation coefficient （ Dependence ） unchanged . At some point in the future t The value of depends on its past information , So we need dependence

The data is relatively stable ：

• The difference method ： The time series t And t-1 Time difference

Autoregressive model （AR）

• Describe the relationship between current value and historical value , Use the historical time data of variables to predict themselves
• Autoregressive model must satisfy the requirement of stationarity
• p The formula definition of order autoregressive process ：$y_t=\mu +{\sum }_{i=1}^p{\gamma }_i{y}_{t-i}+{ϵ}_t$
• $y_t$ It's the current value ,$\mu$ It's a constant term ,$P$ It's order ,${\gamma }_i$ Is the autocorrelation coefficient ,${ϵ}_t$ It's error

Limitations of autoregressive models ：

• Autoregressive model uses its own data to predict
• Must be stable
• Must have autocorrelation , If the autocorrelation coefficient $({\phi }_i)<0.5$, ... should not be used
• Autoregression is only applicable to predict the phenomenon related to its own early stage

Moving average model （MA）

• The moving average model focuses on the accumulation of error terms in the autoregressive model
• q The formula definition of order autoregressive process ：$y_t=\mu +{ϵ}_t+{\sum }_{i=1}^q{\theta }_i{ϵ}_{t-i}$
• The moving average method can effectively eliminate the random fluctuation in prediction

Autoregressive moving average model ：$(ARMA)$

• The combination of autoregressive and moving average
• Formula definition ：$y_t=\mu +{\sum }_{i=1}^p{\gamma }_i{y}_{t-i}+{ϵ}_t+{\sum }_{i=1}^q{\theta }_i{ϵ}_{t-i}$

ARIMA： Differential autoregressive moving average model

Transforming non-stationary time series into stationary time series

Then the model is established by regressing the dependent variable only to its lag value and the present value and lag value of the random error term

choice p Values and q value

Autocorrelation function ACF

• An ordered sequence of random variables is compared to itself Autocorrelation function reflects the correlation between the values of the same sequence in different time series
• $ACF(k)={\varrho }_k=\frac{Cov(y_t,y_{t-k})}{Var(y_t)}$

Partial autocorrelation function （PACF）

• ACF What we get from it is not $x(t)$ And $x(t-k)$ A simple correlation between
• $x(t)$ At the same time, it will be $x(t-1)\dots x(t-k+1)$ Influence
• PACF Cut out the middle $k-1$ Random variables $x(t-1),\dots ,x(t-k+1)$ After the interference of ,$x(t-k)$ Yes $x(t)$ The relevance of the impact

Model	ACF	PACF
AR（p）	Attenuation tends to 0（ Geometric or oscillatory ）	p End after step
MA（q）	q End after step	Attenuation tends to 0（ Geometric or oscillatory ）
ARMA（p,q）	q The post order attenuation tends to 0（ Geometric or oscillatory ）	p The post order attenuation tends to 0（ Geometric or oscillatory ）

truncation ： Fall within the confidence interval （95% All of the points conform to the rule ）

Modeling process

• Smooth the sequence （ Determination by difference method d）
• p and q Order determination ：ACF And PACF
• ARIMA（p,d,q）

Model selection AIC And BIC：（ The lower the better ）

AIC： Red pool information criterion . $AIC=2k-2ln(L)$

BIC： Bayesian information rule $BIC=kln(n)-2ln(L)$

k There are several parameters in the model ,n Is the number of samples ,L Is the likelihood function

Model residual test ：

ARIMA Whether the residual error of the model is the average value 0 And the variance is a constant normal distribution

neural network

A picture is represented as a three-dimensional array in a computer

K Nearest neighbor algorithm

One thing it's nearest k Which class does one belong to more , It is divided into which class

For points in the unknown category attribute dataset ：

• Calculate the distance between the point in the known category dataset and the current point
• Sort by distance
• Select the least distance from the current point k A little bit
• Make sure before k Probability of occurrence of the category in which a point is located
• Return to the former k The category with the highest frequency of points is used as the current point prediction classification

No training required , The computational complexity is proportional to the number of documents in the training set , Complexity $O(n)$

Distance calculation ：

$d_1(I_1.I_2)=\sum _p|I_1^p-I_2^P|$

Distance is also called a super parameter

Manhattan distance ：$L1$：$d_1(I_1,I_2)=\sum _p|I_1^P-I_2^p|$

Euclidean distance ：$L2$：$d_2(I_1,I_2)=\sqrt{\sum _p(I_1^p-I_2^p{)}^2}$

K Determination of nearest neighbor parameters ：

Use cross validation ： Take part of the training set as the verification set （ Adjust model parameters ）（ Alternately take one of them as the verification set ）

Neural network loss function

$L_i=\frac{1}{N}{\sum }_{i=1}^N{\sum }_{j\ne y_i}max(0,f(x_i;W{)}_j-f(x_i;W{)}_{y_i}+\delta )$

$\delta$ Tolerable degree

Regularization penalty term

$L_i=\frac{1}{N}{\sum }_{i=1}^N{\sum }_{j\ne y_i}max(0,f(x_i;W{)}_j-f(x_i;W{)}_{y_i}+\delta )+\lambda \sum _k\sum _l{W}_{k,l}^2$

effect ： Penalty weight parameter

Softmax classifier

$softmax$ Output ： Normalized classification probability

Loss function ： Cross entropy loss $L_i=-\log \frac{e^{f_{y_i}}}{{\sum }_j{e}^{f_j}}$

$f_j(z)=\frac{e^{z_j}}{{\sum }_k{e}^{z_k}}$, Referred to as softmax function

The input value is a vector , The score value of any real number in the vector

Output a vector , Each element value is in 0 To 1 Between , And the sum of all elements is 1

Machine learning optimization

Back propagation

gradient descent

$batchsize$： The amount of load on the computer , Multiple sheets in one iteration （ Forward propagation + Back propagation ）

In training , The overall trend is convergent

epoch： All the data have been run

Back propagation

Additive gate unit ： Equal distribution

MAX Door unit ： To the biggest

Multiplication gate unit ： swap

characteristic ：

• hierarchy
• Nonlinear structure

sigmoid Function gradient vanishes seriously , Is no longer used

Now we mainly use RELU $max(0,x)$

The more neurons , The better the classification

Prevent over fitting ： Regularization

Data preprocessing

Weight initialization ：b Constant initialization ,w Random

Prevent over fitting ：

drop-out： In training , A part of neurons are randomly reserved for forward and backward propagation