User Tools

Site Tools


keynote:lesson02

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
Next revision Both sides next revision
keynote:lesson02 [2010/03/26 21:29]
10921007
keynote:lesson02 [2010/06/26 14:22]
10921021
Line 16: Line 16:
 |4        |Sunny ​ |Warm      |High     ​|Strong ​ |Cool   ​|Change ​   |Yes     | |4        |Sunny ​ |Warm      |High     ​|Strong ​ |Cool   ​|Change ​   |Yes     |
 **实例空间X**:概念是定义在一个实例集合上的,本例中X是所有可能的日子,而Sky,​AirTemp之类是日子的属性;​\\ **实例空间X**:概念是定义在一个实例集合上的,本例中X是所有可能的日子,而Sky,​AirTemp之类是日子的属性;​\\
-**目标函数C**:学习的函数,可以是定义在实例集X上的任意布尔函数,​形式化为C:​X->​{0,​1};​\\+**目标函数C**:学习的函数,可以是定义在实例集X上的任意布尔函数,​形式化为C:​X->​{0,​1};​\\
 **训练样本D**:是为学习概念而提供的训练实例,训练样本中的每一个条目为X中的一个实例加上此实例对应的目标函数的值C(x);​\\ **训练样本D**:是为学习概念而提供的训练实例,训练样本中的每一个条目为X中的一个实例加上此实例对应的目标函数的值C(x);​\\
 **假设空间H**:所有可能假设的集合,它中的每一个假设h表示X上定义的布尔函数,即h:X->​{0,​1};​\\ **假设空间H**:所有可能假设的集合,它中的每一个假设h表示X上定义的布尔函数,即h:X->​{0,​1};​\\
Line 84: Line 84:
   * 否则迭代执行上面的循环   * 否则迭代执行上面的循环
  
 +那么,哪个属性是最佳的分类属性呢?\\ 
 +这就需要用到“奥坎姆剃刀”原则\\ 
 +**奥坎姆剃刀**:优先选择拟合数据的最简单假设。\\ 
 +这是一个心理学问题,哲学家们以及其他学者已经对这样的问题争论几个世纪了,而且这个争论至今还未解决。\\ 
 +决策树遵照这个原则:**较短的树比较长的优先**\\ 
 +那么怎么确定一个属性能够较好的划分训练数据呢?这就用到了信息论(information theory)\\ 
 +信息论是一个数学分支,由Claude shannon在20世纪40年代创建。信息论是一门用数理统计方法来研究信息的度量、传递和变换规律的科学。它主要是研究通讯和控制系统中普遍存在着信息传递的共同规律以及研究最佳解决信息的获限、度量、变换、储存和传递等问题的基础理论。\\ 
 +信息就是不确定性的减少,并获取新的知识。\\ 
 +**信息是确定性的增加**----逆Shannon信息定义。\\ 
 +一个事件的信息量与它出现的概率最为相关。在信息论中,使用的基本单位是位(**bits**)。\\ 
 +如果一个确定发生的事件发生了,那么确定性没有任何变化,所以得到的信息为0。而如果小概率的事件发生了,那么将得到比可能发生的事情更多的信息量。所以信息量与事件发生的概率成反比。\\ 
 +举例来说:设字母表为{$S_1,S_2,S_3,。。。S_n$} 
 +那么每个符号$S_i$的概率为$P(S_i)=P_i(P_i>​=0 且 \sum_{i=1}^{n}P_i=1)$\\ 
 +对两个不相关的事件来说,I($S_iS_j)=I(S_i)+I(S_j)$\\ 
 +P($S_iS_j)=P(S_i)P(S_j)$ 
 +从这两个关系式中可以看出,I($S_i$)应该以P($S_i$)对数形式给出,所以有\\ 
 +I($S_i$)=-$log_2P_i$\\ 
 +所以每个符号的平均信息是 $E_t=-\sum_{i=1}^{M}P_ilog_2P_i$ 
 +这就是“熵”\\ 
 +用熵建立一个信息增量的方程\\ 
 +{{:​keynote:​infogain.jpg|}}\\ 
 +信息增量最大的属性就是最佳的属性\\
 <note important>​ Revised by Li Xin (李昕),​ <​lixin@zjucadcg.com>​ </​note>​ <note important>​ Revised by Li Xin (李昕),​ <​lixin@zjucadcg.com>​ </​note>​
  
Line 93: Line 114:
  
 根据贝叶斯公式: 根据贝叶斯公式:
-<​note>​$P(Y|X) = \frac{P(X)P(Y|X)}{P(Y)}$</​note>​ +<​note>​$P(Y|X) = \frac{P(Y)P(X|Y)}{P(X)}$</​note>​ 
-于是我们需要计算P(X),P(Y|X)即可+于是我们需要计算P(Y),P(X|Y)即可
  
 构造一个分类器(Naive Beyes Classifier),即目标函数$f:​X \to Y$ 构造一个分类器(Naive Beyes Classifier),即目标函数$f:​X \to Y$
Line 111: Line 132:
  
  
 +<note important>​ Revised by Bin Xu(徐斌), <​xu_bin@zju.edu.cn>​ </​note>​
  
 ===== 2.4 支持向量机(SVM) ===== ===== 2.4 支持向量机(SVM) =====
Line 122: Line 144:
   -注意到一般情况下这种超平面会有无数多个可能,所以定义margin:超平面距离两类数据集中最近的点的和。使得margin最大的超平面就是最优的超平面。   -注意到一般情况下这种超平面会有无数多个可能,所以定义margin:超平面距离两类数据集中最近的点的和。使得margin最大的超平面就是最优的超平面。
   -很多时候数据集并不是线性可分的,也就是说找不到合适的超平面把数据集严格的分成两类,这是有两种方法:   -很多时候数据集并不是线性可分的,也就是说找不到合适的超平面把数据集严格的分成两类,这是有两种方法:
-    -引入训练误差,即允许少量数据点被分在错误的类。 +    -引入训练误差,即允许少量数据点被分在错误的类。详细来说就是加入一些松弛变量 (slack variables) $\xi_i$ ,使得数据 $x_i$ 即使不能被超平面线性分割而是有 $\xi_i$ 那么大的误差也是允许的,同时,为了避免无限制的松弛,将 slack variables 也加入需要最小化的目标函数中,并(通常)使用一个参数 $C$ 来控制原本的目标函数和松弛变量的权重,即加入 $C\sum_{i=1}^l\xi_i$ 这样一项。 
-    -使用非线性的分类方式,也就是高维可分。+    -使用非线性的分类方式,也就是高维可分。这是通过 Kernel 方法来实现,具体来说,在原始空间中无法线性可分的数据,我们希望通过一个映射 $\Phi(\cdot)$ 将原始空间中的数据映射到一个更高维度(甚至是无穷维度)的空间中。这样的做法的可行性在于考虑到 SVM (以及许多相关线性算法)中使用数据的方式仅仅是依靠于数据之间的内积 $<​x_i,​x_j>​$ ,而我们可以通过核方法直接使用低维的数据计算出高维空间中映射后的数据点的内积:$K(x_i,​x_j) = <​\Phi(x_i),​\Phi(x_j)>​_\mathcal{H}$ (其中 $<​\cdot,​\cdot>​_\mathcal{H}$ 表示在高维空间 $\mathcal{H}$ 中的内积)。通过这样的方法,就能有效地解决了线性不可分的问题。 
 + 
 +<note important>​ 
 + ​Extended by //​[[pluskid@gmail.com|张弛原]] 2010/04/26 13:28// 
 +</​note>​
  
 ====2.4.3 SVM的应用==== ====2.4.3 SVM的应用====
keynote/lesson02.txt · Last modified: 2021/04/13 21:35 (external edit)