INT 104_LEC 06

1. Support Vector Machine【支持向量机】

---

1.1. Hyperplane【超平面】

1.1.1. 描述

• 超平面是 n 维欧氏空间中余维度等于一的线性子空间，其维度必须是 (n-1)
• 余维数是衡量子空间 (子簇等等)大小的一个数值量。 假设X是一个代数簇，Y是X中的一个子簇。X的维数是n，Y的维数是m，那么我们称Y在X中的余维数是n-m，特别地，如果X和Y都是线性空间，那么Y在X中的余维数就是Y的补空间的维数

1.1.2. 定义

• 数学
  • ​​​​​设为域(可考虑为)，维空间的超平面是由方程：定义的子集，其中是不全为零的常数
• 线性代数
  • 矢量空间中的超平面是指形如：的子空间，其中是任一非零的线性映射
• 射影几何
  • 在齐次坐标下，射影空间的超平面是由方程：定义，其中是不全为零的常数

1.1.3. 一些特殊类型

• 仿射超平面

  • 仿射超平面是仿射空间中的代数1的仿射子空间在笛卡尔坐标中，可用方程：描述，其中是不全为零的常数

  • 在真实仿射空间的情况下，换句话说，当坐标为实数时，该仿射空间将空间分成两个半空间，它们是超平面的补码的连接分量，由不等式和给出

  • 仿射超平面用于定义许多机器学习算法中的决策边界,例如线性组合(倾斜)决策树和感知器

• 矢量超平面

  • 在矢量空间中,矢量超平面是代数1的子空间,只能通过向量从原点移位,在这种情况下,它被称为平面。这样的超平面是单一线性方程的解

• 投影超平面

  • 投影子空间是一组具有属性的点,对于集合中的任何两个点,由两点确定的线上的所有点都包含在集合中。投影几何可以被看作是添加了消失点(无穷远点)的仿射几何。仿射超平面与无限相关点形成投影超平面。投影超平面的一个特殊情况是无限或理想的超平面,其定义为无限远的所有点的集合

  • 在投影空间中,超平面不会将空间分为两部分:相反,它需要两个超平面来分离点并分割空间。其原因是空间基本上“包围",使得单个超平面的两侧彼此连接

1.1.4. PPT

• A hyper plane could be used to split samples belonging to different classes
• The hyperplane can be written as WX + b = 0 hence
  • Positive class will be taken as WX + b > +1
  • Negative class will be taken as WX + b < -1

1.2. Support Vector【支持向量】

1.2.1. INFO

• 支持向量机(SVM)是一类按监督学习(Supervised Learning)方式对数据进行二元分类的广义线性分类器(Generalized Linear Classifier),其决策边界是对学习样本求解的最大边距超平面(Maxmum Margin Hyperplane)
• SVM使用铰链损失函数(Hinge Loss)计算经验风险(Empirical Risk)并在求解系统中加入了正则化项以优化结构风险(Structural Risk)，是一个具有稀疏性和稳健性的分类器
• SVM可以通过和方法(Kernel Method)进行非线性分类，是常用的核学习(Kernel Learning)方法之一

1.2.2. What do we want?

• 超平面和支持向量之间的最大距离
•  
• Optimal hyperplane                               【最优超平面】
• Optimal Margin                                      【最优间隔】
• Dashed Line                                          【支持向量】

1.3. Kernel Function【核函数】

1.3.1. 定义

• 支持向量机通过某非线性变换，将输入空间映射到高维特征空间。如果在求解支持向量是只用到内积计算，而在低位输入空间又存在某个函数，它恰好等于在高维空间中这个内积，即，那么支持向量机就不用计算复杂的非线性变换，而由这个函数直接得到非线性变换的内积，使大大简化了计算。这样的函数称为核函数

1.3.2. 分类

• 核函数的选择要满足Mercer's Theorem，即核函数在样本空间内的任意Gram Matrix【格拉姆矩阵】为半正定矩阵
• 常用的：
  • 线性核函数
  • 多项式核函数
  • 径向基核函数
  • Sigmoid核函数
  • 复合核函数
  • 傅里叶级数核函数
  • B样条核函数
  • 张量积核函数
  • ......

1.3.3. 理论

• 根据模式识别理论，低维空间线性不可分的模式通过非线性映射到高维特征空间则可能实现线性可分
• 采用核函数技术可以有效地避免高维特征空间运算时存在的“维数灾难”
  • 设属于空间，非线性函数实现输入空间到特征空间的映射，其中属于，，根据核函数技术有
    • ，其中为内积，为核函数
  • 核函数将m维高维空间的内积运算转化为n维低维输入空间的核函数计算，从而巧妙地解决了在高维特征空间中计算的“维数灾难”等问题，从而为在高维特征空间解决复杂的分类或回归问题奠定了理论基础

1.3.4. 性质

• 避免了“维数灾难”，大大减小了计算量，有效处理高维输入
• 无需知道非线性变换函数的形式和参数
• 核函数的形式和参数的变化会隐式地改变从输入空间到特征空间的映射，进而对特征空间的性质产生影响，最终改变各种核函数方法的性能
•  核函数方法可以和不同的算法相结合，形成多种不同的基于核函数技术的方法，且这两部分的设计可以单独进行，并可以为不同的应用选择不同的核函数和算法

1.3.5. PPT

• 

1.4. Multiple Classes【多分类问题】

1.4.1. OvO---One Vernus One

• Figure
  • 
• 思想
  • 将N个类别两两配对，每次使用2个类别的数据训练分类器
  • 将样本提供给所有的分类器，通过投票产生最终结果
• 分类器数量
  • 
• 特点
  • 分类器较多，且每个分类器在训练时只使用了2个类别的样本数据

1.4.2. OvM---One Vernus Many

• 思想
  • 每次将一个类作为样例的正例，其他所有均作为反例
  • 每个分类器能识别一个固定类别
  • 使用时，若有一个分类器为正类，则就为该类别；若有多个分类器为正类，则选择置信度最高的分类器识别的类别
• 分类器数量
  • 
• 特点
  • 相比OvO分类器数量较少，并且每个分类器在训练时都使用了所有样本数据

1.4.3. MvM---Many Vernus Many

• 思想
  • 每次将若干个类作为正例、若干个类作为反例
  • 常用的技术是ECOC【纠错输出码】
  • 编码阶段
    • 对N个类做M次划分，每次划分将一部分作为正类，一部分划分反类
    • 编码矩阵共有两种形式：二元码和三元码
      • 二元码：分为正类和反类
      • 三元码：分为正类和反类以及停用类
    • 一共产生M个训练集，训练出M个分类器
  • 解码阶段
    • M个分类器分别对测试样本进行预测，这些预测标记组成一个编码，将这个预测编码与每个类各自的编码进行比较，返回其中距离最小的类别作为最终结果
• 分类器数量
  • M个
• 特点
  • ECOC编码长度和纠错能力正相关
  • 编码越长所需要的训练的分类器越多，计算存储开销都会增大；另一方面对于有限类别码长超过一定范围就没有意义了。对于同等长度的编码，理论上来说，任务两个类别之间的编码距离越远，则纠错能力越强
• 实例
  • ECOC编码示意图中，“+1”和“-1”分别表示正、反例，三元码中“0”表示不使用该类样本
  • 黑色和白色分别表示正、反例，三元码中灰色表示不使用该类样本

  • 二元ECOC码
    							海明距离	欧氏距离
    测试样例

  • 三元ECOC码
    									海明距离	欧氏距离
    测试样例

---

2. Naive Bayes【朴素贝叶斯】

---

2.1. Baye's Rule

2.1.1. Definition

• States the relationship between prior probability distribution【先验概率分布】 and posterior probability distribution【后验概率分布】

2.1.2. Formula

• 
• 
• 
• 
• 

2.1.3. Application

• Parameter estimation
• Classification
• Model selection

2.2. Baye's Rule for Classification

2.2.1. How can we make use of Bayes’ Rule for Classification?

• We want to maximise the posterior probability of observations
• This method is named MAP estimation (Maximum A Posteriori)

2.2.2. How to use?

• Presume that   means that a sample  belongs to class  where all samples belong to class  from dataset 
• Recall Bayes' Rule
  • 
• As the observation is same(the same training dataset), we have
  • 
• So we need to find the CCP and the prior probability
• According to Law of Large Numbers, the prior probability can be taken as the probability resulted from the frequency of observations
• So we only care about the term
  • 

2.3. Naïve Bayes Classifier【朴素贝叶斯】

2.3.1. Calculate

• Calculate the term  is never an easy task
• A way to simplify the process is to assume the conditions / features of  are independent to each other
• Assume that , we have
  • 

2.3.2. Example 01

• Will you play on the day of Mild?

  • Original Dataset
    Outlook	Temprature	Humidity	Windy	Play
    Overcast	Hot	High	False	Yes
    Overcast	Cool	Normal	True	Yes
    Overcast	Mild	High	True	Yes
    Overcast	Hot	Normal	False	Yes
    Rainy	Mild	High	False	Yes
    Rainy	Cool	Normal	False	Yes
    Rainy	Cool	Normal	True	No
    Rainy	Mild	Normal	False	Yes
    Rainy	Mild	High	True	No
    Sunny	Hot	High	True	No
    Sunny	Hot	High	False	No
    Sunny	Mild	High	False	No
    Sunny	Cool	Normal	False	Yes
    Sunny	Mild	Normal	True	Yes

• Solution

  • Temprature	Yes	No	p
    Hot	2	2	0.28
    Mild	4	2	0.43
    Cool	3	1	0.28
    p	0.64	0.36

  • 
  • 
  • 
  • 
  • 

2.3.3. Example 02

• Will you play on the day of Rainy, Cool , Normal and Windy?

  • Original Dataset
    Outlook	Temprature	Humidity	Windy	Play
    Overcast	Hot	High	False	Yes
    Overcast	Cool	Normal	True	Yes
    Overcast	Mild	High	True	Yes
    Overcast	Hot	Normal	False	Yes
    Rainy	Mild	High	False	Yes
    Rainy	Cool	Normal	False	Yes
    Rainy	Cool	Normal	True	No
    Rainy	Mild	Normal	False	Yes
    Rainy	Mild	High	True	No
    Sunny	Hot	High	True	No
    Sunny	Hot	High	False	No
    Sunny	Mild	High	False	No
    Sunny	Cool	Normal	False	Yes
    Sunny	Mild	Normal	True	Yes

• Solution​​​​​​

  • Outlook	Yes	No	p
    Overcast	4	0	0.28
    Rainy	3	2	0.36
    Sunny	2	3	0.36
    p	0.64	0.36

  • Temprature	Yes	No	p
    Hot	2	2	0.28
    Mild	4	2	0.43
    Cool	3	1	0.28
    p	0.64	0.36

  • Humidity	Yes	No	p
    High	3	4	0.50
    Normal	6	1	0.50
    p	0.64	0.36

  • Windy	Yes	No	p
    T	3	3	0.43
    F	6	2	0.57
    p	0.64	0.36

  •  
    • ​​​​​​​
    • ​​​​​​​​​​​​​​
    • ​​​​​​​​​​​​​​
    • ​​​​​​​
  • 
    • 
    •  
    • 
    • ​​​​​​​
  • Yes

---

3. Methods

---

3.1. Parametric Methods【参数化方法】

• We presume that there exists a model, either a Bayesian model (e.g. Naïve Bayes) or a mathematical model (e.g. Linear Regression)
  • We seldom obtain a “true” model due to the lack of prior knowledge
  • For the same reason, we never know which model should be used

3.2. Non-parametric Methods【非参数方法】

• Non-parametric models can be used with arbitrary distributions and without the assumption that the forms of the underlying densities are known.
• Moreover, they can be used with multimodal distributions which are much more common in practice than unimodal distributions.
• ​​​​​​​With enough samples, convergence to an arbitrarily complicated target density can be obtained.
• The number of samples needed may be very large (number grows exponentially with the dimensionality of the feature space).
• These methods are very sensitive to the choice of window size (if too small, most of the volume will be empty, if too large, important variations may be lost).
• There may be severe requirements for computation time and storage.
• Two major methods
  • Decision tree
  • k-nearest neighbour

---

4. Decision Tree【决策树】

---

4.1. Steps

4.1.1. Provide

• Suppose we have a training dataset  whose labels are  respectively, where 

4.1.2. Step

• Given a node as root node
• Determine whether the node is a leaf note by
  • Whether the node contains no samples
  • Whether the samples belong to the node is from a universal class
  • Whether a common attribute is shared
  • Whether attributes are yet to be further analysed
• The decision of leaf is determined by voting
• Select attribute in ​​​​​​​ to build a new branch for each value of the selected branch then determine the mode of nodes by the previous procedure
  • Entropy gain【Do not consider the size of dataset】
    • 
    • 
  • Ratio gain (C4.5)【Prefer small size】
    • 
    • 
  • Gini index (CART)【R: Regression】
    • ​​​​​​​
    • 

4.2. Example

4.1.1. Dataset

• Original Dataset
  Outlook	Temprature	Humidity	Windy	Play
  Overcast	Hot	High	False	Yes
  Overcast	Cool	Normal	True	Yes
  Overcast	Mild	High	True	Yes
  Overcast	Hot	Normal	False	Yes
  Rainy	Mild	High	False	Yes
  Rainy	Cool	Normal	False	Yes
  Rainy	Cool	Normal	True	No
  Rainy	Mild	Normal	False	Yes
  Rainy	Mild	High	True	No
  Sunny	Hot	High	True	No
  Sunny	Hot	High	False	No
  Sunny	Mild	High	False	No
  Sunny	Cool	Normal	False	Yes
  Sunny	Mild	Normal	True	Yes

4.1.2. Analysis

• Outlook

  • Outlook	Yes	No
    Overcast	4	0	4
    Rainy	3	2	5
    Sunny	2	3	5

  • Entropy of Outllook
    • ​​​​​​​
    • 
    • 
    • 
  • Entropy of Overcast
    • ​​​​​​​
    • 
    • 
    • 
  • Entropy of Rainy
    • ​​​​​​​
    • 
    • 
    • 
  • Entropy of Sunny
    • ​​​​​​​
    • 
    • 
    • 
  • 
    • 
    • 
    • 
  • Entropy Gain
    • 
    • 
    • 
• Build the decision tree
  • ​​​​​​​Select the attribute with highest entropy gain to build up
  • e.g.
    • ​​​​​​​Suppose Entropy Gain of Outlook is the highest
    • The 1st level of decision tree will look like
    • ​​​​​​​​​​ 

4.3. Overfitting【过拟合】

4.3.1. Too good to be true

• Sometimes, the decision tree has fit the sample distribution too well such that unobserved samples cannot be predicted in a sensible way
• We could prune(remove) the branches that cannot introduce system performance

4.4. Random Forest → Typical  Example of Boosting【随机森林】

• Another way to improve the system is to have multiple decision tree and vote for the final results
• Attributes for each decision tree is random selected
• ​​​​​​​Each decision tree is only trained by a part set of attributes of samples
  • ​​​​​​​e.g.
    • ​​​​​​​For attribute {A,B,C,D}
      • Tree 1 ={A,B,C} 
      • Tree 2 ={B,C,D} 
      • Tree 3 = {C,D}
    • Trained
      • ​​​​​​​Tree 1 ={A,B,C} → Yes
      • Tree 2 ={B,C,D} → Yes
      • Tree 3 = {C,D}    → No

---

5. KNN

---

5.1. PPT

• As in the general problem of classification, we have a set of data points for which we know the correct class labels
• When we get a new data point, we compare it to each of our existing data points and find similarity
• Take the most similar k data points (k nearest neighbours)
• From these k data points, take the majority vote of their labels. The winning label is the label / class of the new data point

5.2. Extra

5.2.1.核心思想

• 如果一个样本在特征空间中的K个最相邻的样本中的大多数属于某一个类别，则该样本也属于这个类别，并具有这个类别上样本的特性

5.2.2. 算法流程

• 对数据进行预处理

• 计算测试样本点（也就是待分类点）到其他每个样本点的距离【一般用欧式距离】

• 对每个距离进行排序，然后选择出距离最小的K个点

• 对K个点所属的类别进行比较，根据少数服从多数的原则，将测试样本点归入在K个点中占比最高的那一类

5.2.3. 优缺点

• 优点
  • ​​​​​​​思路简单，易于理解，易于实现，无需估计参数
• ​​​​​​​缺点
  • ​​​​​​​当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数
  • 计算量较大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点

5.2.4. 改进策略

• 寻求更接近于实际的距离函数以取代标准的欧氏距离               【WAKNN、VDM】
• 搜索更加合理的K值以取代指定大小的K值                                【SNNB、DKNAW】
• 运用更加精确的概率估测方法去取代简单的投票机制               【KNNDW、LWNB、ICLNB】
• 建立高效的索引，以提高KNN算法的运行效率                         【KDTree、NBTree】