Through algorithms, machines can learn rules from a large number of data and make decisions on new sample

---

Four Elements in Machine Learning

• Data
• Model
• Learning Rule
• Optimization Algorithm

Learning Rules

A good model should be consistent with the real mapping function in all values:

$$|f(x,{\theta }^{\ast })-y|\le ϵ,\forall (x,y)\in X\times Y$$

Loss Func

it is a non-negative real function, used to quantify the difference between model’s prediction and true label

For example,Quadratic loss function:

$$L(y,f(x;\theta ))=\frac{1}{2}(y-f(x;\theta ){)}^2$$

Empirical risk minimization

After selecting the appropriate risk function, we look for a parameter ${\theta }^{\ast }$ to minimize the empirical risk function:

$${\theta }^{\ast }={\text{argmin}}_{\theta }\hat{\mathcal{R}}(\theta )$$

ML problem is transformed into an optimization problem

Expected Risk

期望风险(真实风险):

$$R(\theta )=E_{(}x,y)\sim p_r(x,y)[L(y,f(x;\theta ))]$$

• $E_{(}x,y)\sim p_r(x,y)$: Real data distribution

Empirical Risk(经验风险)

Expected risk is unknown, approximated by empirical risk

$$\hat{\mathcal{R}}(\theta )=\frac{1}{n}\sum _{i=1}^n\mathcal{L}(y_i,f(x_i;\theta ))$$

Stochastic Gradient Descent

SGD: sampling one samples in each iteration

$${\theta }_t+1=\frac{{\theta }_t-\alpha \partial L(y^n,f(x^n;\theta ))}{\partial \theta },n=1\cdots N$$

Generalization Error (泛化误差)

Generalization error:

$$G_D(f)=R(f)-R_D^{emp}(f)$$

Regularization

the principle of empirical risk minimization can easily lead to a low error rate in the training set, but a high error rate in the unknown data.