斯坦福机器学习笔记（1）

人工智能 机器学习 笔记 斯坦福

Course Map

• Supervised Learning
  
  • Linear Regression
  • Gradient Descent
  • Normal Equations
• Learning Theory
• Unsupervised Learning
• Intensive Learning

Notation

m = Training examples size
x = Input variables / features
y = Output variables / target variables
(x,y) = Training examples
ith = the ith training example, (x[i], y[i])

Supervised Learning

对于一个Input->Output，用一个模型去拟合它，使得对于Input'，该模型能产生接近于Output'的输出。监督型学习算法首先要构造一个模型（Hypothesis），其二在于用Output来度量模型的可靠性（Evulate：评估），其三在于监督模型使其可靠性不断提高（Optimization：优化）。
eg. HouseArea+Bedrooms->Price
eg. DigitImages->Digits

一、Hypothesis

在此例中，采用Linear Regression作为Hypothesis。
H(x) = θ1x1+θ2x2+...+θnxn

二、Evaluating

在此例中，采用最小二乘法做可靠性评估
J(θ) = 1/2*sum(square(H(x[i]) - y[i]))

三、Optimization

1、Start with θ (Say θ = 0)
2、Keep changing θ to reduce J(θ)
在此例中，采用梯度下降算法做优化（Gradient Descent Algorithm）

eg. Gradient Descent Algorithm
θi -= α*∂J/∂θi
// 由数学知识
∂J/∂θi = (H(x)-y)*xi
一、α是Learning Rate，决定了梯度下降步长。如果该值过小，则学习时间会过长；如果值过大，可能算法会跳过我们期望的最小值
二、θ的初值对结果可能会有影响，因为该算法其实是收敛到极小值而非最小值。
在接近最小值时，每次的改变值会越来越小，因为梯度越来越趋于零，最终每次的改变值也会趋于零。
当然，最终改变值可能不会恰好等于零，当改变值足够小时，我们就可以认为已经收敛了。
三、从算法复杂度的角度来考察这个算法，每次梯度下降都要O(m)的时间，当m达到1e6的数量级的时候，需要的时间就超出预算了。因为这个特性，这个算法也被叫做`Batch Gradient Descent Algorithm`
四、Statistical Gradient Descent Algorithm可以解决这个问题，伪码如下：
Repeat{
    For j = 1 to m {
        For i = 1 to n {
            θi -= α*(H(x[j])-y[j])*xi[j]
        }
    }
}
这样复杂度降到O(mn)

Normal Equation

对于Linear Regression + 最小二乘法这种模型，一个给定的数据集必然有一个固定的最佳结果。上面通过梯度下降算法不断逼近这个结果，这里从另一个角度来解决这个问题：通过线性代数知识直接像解方程一样把最佳结果计算出来。

这样的好处在于计算机的计算量大幅减少，且可靠性有保障。缺点是需要提前进行数学运算。

下面介绍此节中需要的记号（Notation）和定理（Fact）：

Notation

J = [θ1, θ2,..., θn]
grad J = [∂J/∂θ, ∂J/∂θ2,..., ∂J/∂θn]
f : R^m*n -> R
grad f(A) =
[∂f/∂A11, ... , ∂f/∂A1n]
[......................]
[∂f/∂An1, ... , ∂f/∂Ann]
tr A = sum(Aii)

Fact

=> Solution : θ=(XTX)-1XTy