Machine Learning笔记

学习吴恩达的machine learning课程笔记。

resources

website

http://cs229.stanford.edu/
https://see.stanford.edu/Course/CS229

tool

商业软件Matlab or 免费开源软件Octave

动机与应用

why?

很多程序是无法手动编写出来的,eg. 手写文字识别,自动飞行器,自然语言处理NLP

应用

  • learning algorithm容易实现手动无法编写程序的问题。
  • learning algorithm在数据挖掘(data mining)有很好的效果,eg.电子化病例数据,帮助医生更好地决策
  • zip code识别
  • amazon,netflix推荐系统

machine learning definiton

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

  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.

课程由4部分组成

Supervised Learning(监督学习)

监督学习中所有的样本都是带有标记的,“正确答案”已经在样本中。

  1. regression problem(回归问题)
    预测的值是连续(continuous)的。

    regression problem
  2. classification problem(分类问题)
    预测的值是离散(discreet)的,eg. SVM(supported vector machine)

    classification problem

Learning Theory

learning algorith 为什么是有效的;可以证明什么时候(eg.多大的数据量)可以保证算法有效(eg.>99.9%的正确率)。

Unspervised Learning(无监督学习)

无监督学习的样本是不带有标记的,无监督学习需要从数据中自己发现特定的结构。

Reinforcement Learning(增强学习)

reward function(回报函数)

Supervised Learning

Linear regression

supervised_learning_notation_1.png supervised_learning_notation_2.png supervised_learning_notation_3.png

Gradient descent

gradient_descent.png

随机选择一个点(特征参数),通过梯度算法找到下降最陡的方向,一步一步迭代,直到找到一个局部最优解(cost函数取最小值)。
如果初始化的值不一样,得到的局部最优解可能会不一样。
适用于:局部最优解等于全局最优解的情况,想象一个碗形的代价函数。

Batch gradient descent

每次迭代都要遍历所有的训练数据,适用于数据量小的训练集合。
batch_gradient_descent.png
这种迭代规则,称为LMS(Least Mean Squares) update rule.

Stochastic gradient descent(Incremental gradient descent)

只需要遍历一次训练数据,适用于数据量很大的训练集合。
stochastic_gradient_descent.png

$ \alpha $表示学习速率,训练的步进,可以随着梯度的下降,减小该值。

Normal equations

通过矩阵(matrix)的方法推导出的一种不需要迭代,直接可以计算出特征向量的方法。
normal_equation.png
$(X^TX)$不可逆的可能原因:

  • 存在冗余特征($\theta $中存在重复)
  • 特征数量n过多,训练样本数m太少

Non-parameterical learning algorithm

  • parameterical learning algorithm 的参数数量n是固定的,训练完成后不需要样本。
    特征参数过少,导致欠拟合(underfitting);特征数过多,导致过拟合(overfitting)。
    可以通过Feature slection algorithm来自动选取特征参数。

  • Non-parameterical learning algorithm 的参数数量n是随着样本数m的增加而增加的,每次输出结果都需要重新评估训练样本。
    LWR(Locally weighted linear regressioin)是一种无参数的算法

    LWR_1.png LWR_2.png

Probabilistic interpretatioin

最小二乘法的概率学解释:假设误差服从正态分布(高斯分布),最小二乘法求得的特征参数,可以使代价函数最小。

Classification and logistic regression

除了y的取值是离散的之外,分类问题与线性回归问题类似。

Logistic regression

sigmoid function

logistic_regression_1.png logistic_regression_2.png logistic_regression_3.png

Newton’s method

Newtons_method_1.png Newtons_method_2.png

Perceptron learning algorithm

perceptron_learning_algorithm.png

GLM(Generalized Linear Models)

Exponential family

之前的例子中,线性回归算法(最小二乘法)服从高斯分布,逻辑回归算法(sigmoid函数)服从伯努利分布。而这些都是GLM的一些特例。
exponential_family.png

以下分布都属于指数家族:
高斯分布(Gaussian):结果是连续的
伯努利分布(Bernoulli):结果是离散的,只有两种结果
多项式分布(multinomial):结果是离散的,有k种结果
泊松分布(Poisson):计数问题,eg.网站访客量,放射性衰变数目。
伽马分布(gamma):时间间隔,eg.等公交车的时间
指数分布
beta分布
Dirichlet分布

Constructing GLMs

一个重要的设计决策是:
GLM_design_decision.png

Ordinary Least Squares

高斯分布在指数家族的表示如下:
Gaussian_in_exponential_family.png

可以推导出,最小二乘法是GLM的一个特例:
ordianary_least_squares_in_GLM.png

Logistic regression

伯努利分布在指数家族表示如下:
Bernoulli_in_exponential_family.png

可以推导出,逻辑回归是GLM的一个特例:
logistic_regression_in_GLM.png

Softmax regression

多项式分布在指数家族表示如下:
multinomial_in_exponential_family.png
softmax函数:
softmax_functin.png
可以推导出,softmax回归是GLM的一个特例:
softmax_regression_in_GLM.png

logistic回归是softmax回归在k=2时的特例。

Generative learning algorithms

  • 判别(discriminative)学习算法
    如逻辑回归,直接学习p(y|x);或者如感知器算法(perceptron),直接尝试学习从输入到输出的映射(mapping)。
  • 生成(generative)学习算法
    对每种类别分别建模,然后通过贝叶斯公式计算出在给定x条件下y的后验分布。generative_learning_algorithm_1.png generative_learning_algorithm_2.png

GDA(Gaussian Discriminant Analysis)

GDA假设p(x|y)服从多元正态分布(multivariate normal distribution)。

多元正态分布

multivariant_normal_distribution_1.png multivariant_normal_distribution_2.png

高斯判定分析模型

GDA_1.png

通过计算最大化的似然函数,可以得到参数$\phi \mu_0 \mu_1 \Sigma$的值。
GDA_2.png

GDA与逻辑回归

如果我们将$p(y=1|x;\phi, \mu_0, \mu_1, \Sigma)$视为$x$的函数,那么我们发现可以有如下表示形式:
$$ p(y=1|x;\phi, \mu_0, \mu_1, \Sigma)={1 \over {1+exp(-\theta^T x)}}$$
这就是逻辑回归—一种判定算法—用来给$p(y=1|x)$建模的形式。

也就是说,如果数据服从多元高斯分布,那后验分布是逻辑函数;反之,不成立。

如果$x|y=0 ~ Poisson(\lamda_0), x|y=1 ~Poisson(\lamda_1$,那么$p(y|x)$也是逻辑的(logistic)。
也就是说,如果数据服从泊松分布,那后验分布也是逻辑函数;反之,不成立。

逻辑回归对多元高斯分布,泊松分布等都有效。

相比逻辑回归,GDA使用了更强的(stronger)假设。
如果模型假设正确(服从多元高斯分布),那么GDA可以更好地fit数据,可以通过更少的数据达到更好的效果,这种情况下GDA是更好的模型;
与之相对,逻辑回归使用了更弱(weaker)的假设,所以逻辑回归更健壮(robust),且对不正确的模型假设更不敏感。
如果数据不符合高斯分布,使用GDA得不到更好的估算,此时使用逻辑回归更好。

朴素贝叶斯算法(Naive Bayes)

Naive Bayes

  • GDA的特征向量是连续的实数向量。
  • Naive Bayes的特征向量是离散的值。
    以垃圾邮件分类器(email span filter)为例,这个模型也称为多元伯努利事件模型(multi-variate Bernoulli event model):
NB_feature_vector_1.png NB_feature_vector_2.png

朴素贝叶斯算法假设:
NB_assumption.png

朴素贝叶斯算法的参数:

NB_1.png NB_2.png NB_3.png NB_4.png

Laplace smoothing

设想如下场景:
一个从来没有在训练邮件中出现过的单词,但是这个单词在字典里,如果有一天收到一封邮件里包含这类单词。
会导致$\phi_{i|y=1}=0$,且$\phi_{i|y=0}=0$
从而
$$ p(y=1|x) = {0 \over 0}$$
这是一个未定义的值,无法作出估计。

Laplace_smoothing.png

计算明天太阳升起来的概率(假设太阳已经连续n天升起来了)
明天太阳不会升起来的概率:
$$ \phi_0 = {1 \over n+2}$$
明天太阳还会升起来的概率:
$$ \phi_1 = {n+1 \over n+2}$$

Event models for text classification

multinomial_event_model_1.png multinomial_event_model_2.png multinomial_event_model_3.png multinomial_event_model_4.png

References:

  1. 机器学习笔记03:Normal equation与梯度下降的比较
  2. 深度学习算法原理——Softmax Regression
  3. 生成模型(Generative)和判别模型(Discriminative)