第二十一讲 分类预测机器学习的6个核心算法（吴恩达，AndrewNgLinearRegression:Straight&NarrowLogisticRegression:FollowtheCurveGradientDescent:It'sAllDownhillNeural Networks:FindtheFunctionDecisionTrees:FromRoottoLeavesK-Means Clustering:GroupThink
第二十一讲 分类预测 1 机器学习的6个核心算法(吴恩达,Andrew Ng) • Linear Regression: Straight & Narrow • Logistic Regression: Follow the Curve • Gradient Descent: It’s All Downhill • Neural Networks: Find the Function • Decision Trees: From Root to Leaves • K-Means Clustering: Group Think
分类（预测、判别)预测(prediction)：对未知的随机变量进行“估计”。当待预测随机变量是类别的时候，预测也称为分类（classification）或判别(discriminant（当待预测随机变量是连续变量的时候，称为回归）。y：类别，比如y取0-1类别数据：(yixi)i=1,.,n,x：自变量或特征feature求解p(x)=E(ylx）E(ylx)=p(y= 1|x)是概率训练=argmin(- Z[y;logpi + (1 - yi)log(1 - pi)] )参数估计，拟合曲线y=p（x，）pi = p(xi, 0) = P(yi = 1xi, 0)判别回归：=argminZ(i-f(x0))2预测预测=p(x,0)
2 预测(prediction)：对未知的随机变量进行“估计”。当待预测随机变量 是类别的时候，预测也称为分类(classification)或判别(discriminant) （当待预测随机变量是连续变量的时候，称为回归）。 分类（预测、判别） 数据: 𝑦𝑖 , 𝐱𝑖 , 𝑖 = 1, . , 𝑛, 求解 𝑝 𝐱, 𝜃 = 𝐸 𝑦 𝐱 𝜃መ=argmin − σ[𝑦𝑖 log𝑝𝑖 + 1 − 𝑦𝑖 log(1 − 𝑝𝑖)] 𝑝𝑖 = 𝑝 𝐱𝑖 , 𝜃 = 𝑃(𝑦𝑖 = 1|𝐱𝑖 , 𝜃) 𝑦: 类别,比如𝑦取0-1类别 𝐱: 自变量或特征feature 训练 参数估计𝜃መ，拟合曲线𝑦 = 𝑝 𝐱, 𝜃መ 判别 预测 𝑦ො = 𝑝(𝐱, 𝜃መ) 预测 𝐸 𝑦 𝐱 = 𝑝(𝑦 = 1|𝐱)是概率 回归: 𝜃=argminσ(𝑦𝑖−𝑓(𝐱𝑖 , 𝜃)) 2
例1（手写体识别）.n=50个数字0-9手写模式Q00QV体样本如右图。每个手写数字是16×16像识别-素图像，每个像素点的值1（黑）或0（白）.将--7像素强度矩阵拉直成RP向量，p=196。数据：X1.,XnERP：手写数字的像素向量，y1,,yn：手写体的真实标签（0-9，类）。训练预测(判别)准则：将RP划分成10个区域，资与0-9对应（下图）2直线划分：线性判别、（线性）logistic回归10如果划分准则是曲线，3则是非线性预测，比如神经网络。预测：判别新的手写体6是什么数字一其向量表示x落在上图哪个区域？33
例1 (手写体识别). 𝑛 = 50 个数字0−9手写 体样本如右图。每个手写数字是16 × 16像 素图像，每个像素点的值1(黑)或0(白).将 像素强度矩阵拉直成𝑅 𝑝向量, 𝑝 = 196。 33 数据： 𝐱1, . , 𝐱𝑛 ∈ 𝑅 𝑝 : 手写数字的像素向量， 𝑦1, . , 𝑦𝑛: 手写体的真实标签 (0−9,类)。 训练预测(判别)准则: 将𝑅 𝑝划分成10个区域，与0−9对应(下图) 0 2 3 1 直线划分：线性判别、 (线性)logistic回归 如果划分准则是曲线， 则是非线性预测，比如 神经网络。 模式 识别 预测： 判别新的手写体 是什么数字 ⇔ 其向量表示 𝐱 落在上图哪个区域？
统计学分为两大流派：频率学派（Fisher学派，古典）和贝叶斯学两个派（条件概率），随着人工智能的发展，贝叶斯学派越来越被重视。学派对于判别分析，Fisher的方法称为Fisher线性判别分析（LDA：lineardiscriminantanalysis），贝叶斯方法可得到类似的线性判别以及二次判别或其它非线性判别，RonaldFisher（1890-1962）英国统计学家组间与组内平方和：T=W+BThomasBayes（1701-1761），英国统计学家、哲学家，发现了贝叶斯公式。编码与解码：p(zx)与p(xz),z:latentP(x/y)P(y)Z,P(xly=)P(y=1), y:类别p(ylx)-
Ronald Fisher （1890-1962）英国统计学家. Thomas Bayes （1701-1761），英国统计学家、 哲学家，发现了贝叶斯公式。 统计学分为两大流派：频率学派（Fisher学派，古典）和贝叶斯学 派（条件概率） ，随着人工智能的发展，贝叶斯学派越来越被重视。 对于判别分析，Fisher的方法称为Fisher线性判别分析(LDA: linear discriminant analysis), 贝叶斯方法可得到类似的线性 判别以及二次判别或其它非线性判别. 4 两个 学派 编码与解码：𝑝 𝒛 𝐱 与 𝑝 𝐱 𝒛 , 𝒛: 𝑙𝑎𝑡𝑒𝑛𝑡 𝑝 𝑦 𝐱 = 𝑃 𝐱 𝑦 𝑃(𝑦) σ𝑖 𝑃 𝐱 𝑦 = 𝑖 𝑃(𝑦=𝑖) , 𝑦: 类别 组间与组内平方和: 𝑇 = 𝑊 + 𝐵
贝叶斯判别与logistic回归假设xERP，类别两类标号y=0,1，假设两个类的概率密度两类判别/预测xly=1~fi, xly=0~fo如果fi，fo已知（从数据(yi,xi），i=1,,n训练/估计得到)，我们希望判别/预测x所属类别（来自于f还是f.？）一个自然的分类方式是比较概率，比如：贝叶斯判别贝叶斯分类判别（分类）：阈值c是常数，不同地方出现的C未必相同。若P(y=1/x)>C,则预测y=1记第一类在总体中的比例p=P(y=1),利用贝叶斯公式得pfi(x)P(y = 1/x) =pfi(x)+(1-p)fo(x)exp(a+b(x))pfi(x)/(1-p)fo(x)1+exp(a+b(x))1+pfi(x)/(1-p)fo(x)fi(x))其中 b(x) = log),p = P(y = 1).,a = log(fox5
5 贝叶斯判别与logistic回归 一个自然的分类方式是比较概率，比如： 两类判 别/预测 假设𝐱 ∈ 𝑅 𝑝 , 类别两类标号𝑦 = 0,1, 假设两个类的概率密度 𝐱|𝑦=1~𝑓1, 𝐱|𝑦=0~𝑓0 如果𝑓1，𝑓0已知 (从数据(𝑦𝑖 , 𝐱𝑖) , 𝑖 = 1, . , 𝑛训练/估计得到)，我们 希望判别/预测𝐱所属类别（来自于𝑓1还是𝑓0？） 贝叶斯 判别 贝叶斯分类判别(分类)： 若 𝑃 𝑦 = 1 𝐱 > 𝑐, 则预测𝑦 = 1. 阈值 𝑐 是常数,不同地 方出现的 𝑐 未必相同。 记第一类在总体中的比例𝑝 = 𝑃 𝑦 = 1 , 利用贝叶斯公式得 𝑃 𝑦 = 1 𝐱 = 𝑝𝑓1 𝐱 𝑝𝑓1 𝐱 +(1−𝑝)𝑓0 𝐱 = 𝑝𝑓1 𝐱 /(1−𝑝)𝑓0 𝐱 1+𝑝𝑓1 𝐱 /(1−𝑝)𝑓0 𝐱 ≜ exp 𝑎+𝑏 𝐱 1+exp 𝑎+𝑏 𝐱 . 其中 𝑏 𝐱 = log 𝑓1 𝐱 𝑓0 𝐱 , 𝑎 = log 𝑝 1−𝑝 , 𝑝 = 𝑃 𝑦 = 1
因此，利用贝叶斯公式我们得到回归函数E(yx）=P(y=1/x）Logistic的logistic回归的一般形式：回归exp(a+b(x))(一般)logistic回归：P(y=1|x)=1+exp(a+b(x)(f1(x))其中 b(x) = log((),a = log(),p = P(y = 1).如果两类分布是等方差正态：fi=Np(μ1,Z),fo=Np(μo,Z)，则特例1：线性判别fi(x)b(x) = log=()T-1x-(-μ-) ,0(x)是x的线性函数，此时得到通常的（线性）logistic回归模型：exp(α+βTx)(线性)logistic回归：P(y=1风)=1+exp(α+βTx)其=()-, =(--)6
6 (一般)logistic回归：𝑃 𝑦 = 1 𝐱 = exp 𝑎+𝑏 𝐱 1+exp 𝑎+𝑏 𝐱 , 其中 𝑏 𝐱 = log 𝑓1 𝐱 𝑓0 𝐱 , 𝑎 = log 𝑝 1−𝑝 , 𝑝 = 𝑃 𝑦 = 1 . Logistic 回归 因此，利用贝叶斯公式我们得到回归函数 E 𝑦 𝐱 = 𝑃 𝑦 = 1 𝐱 的logistic回归的一般形式： 特例1： 线性判别 如果两类分布是等方差正态：𝑓1 = 𝑁𝑝 𝛍1, Σ , 𝑓0 = 𝑁𝑝 𝛍0, Σ ， 则 𝑏 𝐱 = log 𝑓1 𝐱 𝑓0 𝐱 = (𝛍1 − 𝛍0) ⊤Σ −1𝐱 − 1 2 𝛍1 ⊤Σ −1𝛍1 − 𝛍0 ⊤Σ −1𝛍0 ， 是𝐱的线性函数，此时得到通常的（线性）logistic回归模型： (线性)logistic回归：𝑃 𝑦 = 1 𝐱 = exp 𝛼+𝛃 ⊤𝐱 1+exp 𝛼+𝛃⊤𝐱 其中 𝛃 ⊤ = (𝛍1 − 𝛍0) ⊤Σ −1𝐱, 𝛼 = 𝑎 − 1 2 𝛍1 ⊤Σ −1𝛍1 − 𝛍0 ⊤Σ −1𝛍0
此时，贝叶斯判别或logistic回归判别是经典的Fisher线性判别（LDA：lineardiscriminantanalysis)：如果P(y=1|x)>c,等价地若f1fo(μ - μo) T-1 (x - i+μ)>C,Ho2μi.则预测y=1。LDA经典的Fisher投影求法参见下页。线性分类特例2：若fi = Np(μ1,Z1), fo= Np(μo,Zo),Z1 ± Zo,则二次判别()=βTx+xTQx=x的二次函数，此时b(x) = logfyfiP(y = 1|x) = _exp(a+β*x+xTox)1+exp(α+βTx+xTQx)Hi.·o判别准则：如果P(y=1|x）>c,fo等价地若βTx+TQ>，则预测=1。二次分类神经网络方法容许b(x)具有一般的非线性形式，即非线性分类或判别
7 特例2： 二次判别 若𝑓1 = 𝑁𝑝 𝛍1, Σ1 , 𝑓0 = 𝑁𝑝 𝛍0, Σ0 ，Σ1 ≠ Σ0，则 𝑏 𝐱 = log 𝑓1 𝐱 𝑓0 𝐱 = 𝛃 ⊤ 𝐱 + 𝐱 ⊤𝑄𝐱 = 𝐱的二次函数，此时 𝑃 𝑦 = 1 𝐱 = exp 𝛼+𝛃 ⊤𝐱+𝐱 ⊤𝑄𝐱 1+exp 𝛼+𝛃⊤𝐱+𝐱⊤𝑄𝐱 判别准则：如果 𝑃 𝑦 = 1 𝐱 > 𝑐, 等价地若𝛃 ⊤𝐱 + 𝜸 ⊤𝑄𝜸 > 𝑐, 则预测 𝑦 = 1。 𝑓1 𝑓0 𝛍1 𝛍0 此时， 贝叶斯判别或logistic回归判别是经典的 Fisher线性判别（LDA：linear discriminant analysis)： 如果𝑃 𝑦 = 1 𝐱 > 𝑐 , 等价地若 (𝛍1 − 𝛍0) ⊤Σ −1 𝐱 − 𝛍1+𝛍0 2 > 𝑐， 则预测 𝑦 = 1。 𝑓1 𝑓0 𝛍1 𝛍0 LDA经典的Fisher投影求法参见下页。 神经网络方法容许𝑏 𝐱 具有一般的非线性形式，即非 线性分类或判别。 线性分类 二次分类
线性判别(LDA，lineardiscriminantanalysis)μi + μo2Fisher投影方法：fifo假设fi=N,(μ,2),fo=N，(μo,Z)，求v使得Hi.两类数据在v方向区分度最大：Ho(μ/+μ0)/2(Tμ -vTμo)2maxVTZVV预测y=1=最优方向=-1(1—0）预测1V=（区分度与组间方差/组内方差之比BW-1有关）假设两类数据Fisher线性判别准则：Xi1,.,Xini~fi;μi+o若v>c，则判别/预测y=1Xo1,..,Xono~fo.2判别准则中o以代入注：当c=0.边界i+μo=0 台 fi (x)=fo(x)等概线2(μ)-1(x-μ)<(-μo)T-1(x-μo)，等(马氏)距线8
8 Fisher投影方法: 假设𝑓1 = 𝑁𝑝 𝛍1, Σ , 𝑓0 = 𝑁𝑝 𝛍0, Σ ，求𝐯使得 两类数据在𝐯方向区分度最大: max 𝐯 (𝐯 ⊤𝛍1 − 𝐯 ⊤𝛍𝟎) 2 𝐯 ⊤Σ𝐯 ⇒ 最优方向𝐯∗ = Σ −1 (𝛍1 − 𝛍0) (区分度与组间方差/组内方差之比 𝐵𝑊−1有关) 𝐯∗ (𝛍1+𝛍0)/2 𝑓1 Fisher线性判别准则: 若 𝐯∗ ⊤ 𝐱 − 𝛍1+𝛍0 2 > 𝑐，则判别/预测𝑦 = 1 𝐯∗ ⊤ 𝐱 − 𝛍1 + 𝛍0 2 =0 𝑓0 𝛍1 𝛍0 假设两类数据 𝐱11, . , 𝐱1𝑛1~𝑓1； 𝐱01, . , 𝐱0𝑛0~𝑓0。 判别准则中𝛍1, 𝛍0, Σ 以𝐱ത1, 𝐱ത0, 𝑆 代入 注: 当𝑐 = 0, 边界 𝐯∗ ⊤ 𝐱 − 𝛍1+𝛍0 2 =0 ⇔ 𝑓1 𝐱 = 𝑓0 𝐱 等概线 ⇔ (𝐱 − 𝛍1) ⊤ Σ −1 𝐱 − 𝛍1 < (𝐱 − 𝛍0) ⊤Σ −1 𝐱 − 𝛍0 ，等(马氏)距线 线性判别(LDA，linear discriminant analysis)
假设xERP类别标号v=0.1....K-1.假设各类的概率密度多类判别和多项回xly=k~fk, 0,1, ,K -1归(fk(x))Pk则有记pk= P(y = k),记ak= log(bk(x) = logfo(x)多项回归（multinomialregression）P(xly = k)pkfk(x)pkP(y = k|x) =P(x)ZK-1fi(x)piexp(ak+bk(x))Z1 exp(ai+b;(x) ao = 0, bo(x) = 0若fk=N（μuk,2)，则模型具有普通形式（指数上线性）：特例：多类Fisherexp(α +βx)P(y= k|x) = :线性判别Z1 exp(αi +βx)Fisher多类线性判别准则：若ko=arg,max,P(y=klx)，判别y=kok=0....K-1bk(x)非线性?9
9 多类判别 和多项回 归 假设𝐱 ∈ 𝑅 𝑝 , 类别标号𝑦 = 0,1, . ,𝐾 − 1, 假设各类的概率密度 𝐱|𝑦=𝑘~𝑓𝑘, 0,1, . ,𝐾 − 1 记𝑝𝑘 = 𝑃 𝑦 = 𝑘 , 记 𝑎𝑘 = log 𝑝𝑘 𝑝0 ，𝑏𝑘 𝐱 = log 𝑓𝑘 𝐱 𝑓0 𝐱 , 则有 多项回归(multinomial regression). 𝑃 𝑦 = 𝑘 𝐱 = 𝑃 𝐱 𝑦 = 𝑘 𝑝𝑘 𝑃(𝐱) = 𝑓𝑘(𝐱)𝑝𝑘 σ𝑖=1 𝐾 𝑓𝑖(𝐱)𝑝𝑖 = exp(𝑎𝑘+𝑏𝑘 𝐱 ) σ𝑖=1 𝐾 exp(𝑎𝑖+𝑏𝑖 𝐱 ) , 𝑎0 = 0, 𝑏0 𝐱 = 0 若𝑓𝑘 = 𝑁𝑝 𝛍𝑘, Σ , 则模型具有普通形式（指数上线性）： 𝑃 𝑦 = 𝑘 𝐱 = exp(𝛼𝑘 + 𝛃𝑘 ⊤𝐱) σ𝑖=1 𝐾 exp(𝛼𝑖 + 𝛃𝑘 ⊤𝐱) Fisher多类线性判别准则: 若 𝑘0 = arg max 𝑘=0,.,.𝐾−1 𝑃 𝑦 = 𝑘 𝐱 , 判别𝑦 = 𝑘0. 特例: 多 类Fisher 线性判别 𝑏𝑘 𝐱 非线性？
以二类预测为例（多类问题类似）神经网络神经网络假设logistic回归中b(x）非线性b(x) >cexp(a + b(x))P(y = 1/x) =1 + exp(a + b(x))如果P(y=1x)>c台 b(x)>c（右图），预测y= 1。b(x) ≤c如何生成非线性函数b(x)？多个ReLU(或其它非线性激活)的组合：(x,x> 0ReLU(分段线性)：X+=(0,x≤ 00,x≤b1b(x) = β1(x - b1)+ + β2(x - b2)+ = 3βi(x -b1),b1 b210
10 以二类预测为例（多类问题类似）。 神经网络假设 logistic回归中𝑏 𝐱 非线性 𝑃 𝑦 = 1 𝐱 = exp 𝑎 + 𝑏 𝐱 1 + exp 𝑎 + 𝑏 𝐱 如果𝑃 𝑦 = 1 𝐱 > 𝑐 ⇔ 𝑏 𝐱 > 𝑐（右图），预测 𝑦 = 1。 𝑏 𝐱 > c 𝑏 𝐱 ≤ c 如何生成非线性函数𝑏 𝐱 ？多个ReLU(或其它非线性激活)的组合： ReLU(分段线性): 𝑥+ = ቊ 𝑥, 𝑥 > 0 0, 𝑥 ≤ 0 𝑥 ≤ 𝑏1 𝑏1 𝑏2 神经 网络 𝑏 𝑥 = 𝛽1(𝑥 − 𝑏1)+ + 𝛽2(𝑥 − 𝑏2)+ = ൞ 0, +𝛽2 𝑥 − 𝑏2 𝛽1 𝑥 − 𝑏1 ，, +𝛽2 𝑥 − 𝑏2 𝛽1 𝑥 − 𝑏1 + 𝛽2 𝑥 − 𝑏2