技术博客


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

  • 搜索

机器学习12-1--K-means算法(无监督)

发表于 2014-06-09 | 分类于 机器学习 | | 阅读次数:
字数统计: 475 | 阅读时长 ≈ 1

#机器学习12-1--K-means算法(无监督) 本章开始接触第一个无监督学习算法。无监督学习算法可用在新闻局累、图像分割等。 ## 无监督学习概念 - 定义:简单讲,就是没有分类标签y。非监督式学习是一种机器学习的方式,并不需要人力来输入标签。它是监督式学习和强化学习等策略之外的一种选择。 - K-means是最简单的聚类,聚类属于无监督学习。

K-means的步骤

  1. 符号: > 类的数目:\(k\) 训练样本: 质心点: 类:\({c^{(1)}, c^{(2)}, ……, c^{(k)}}\)
  2. 步骤: K-means 算法是将样本聚类成 k 个簇(cluster),具体算法描述如下:
  3. 二维效果图(k=2):
  4. Kmeans收敛的原因 > 首先,我们定义畸变函数(distortion function)如下: 注:由于畸变函数 J 是非凸函数,意味着我们不能保证取得的最小值是全局最小值,也就是说 k-means对质心初始位置的选取比较感冒,但一般情况下k-means达到的局部最优已经满足需求。但如果你怕陷入局部最优,那么可以选取不同的初始值跑多遍 k-means,然后取其中最小的 J 对应的μ和 c 输出。
  5. 聚类后结果是一个个星团,星团里面的点相互距离比较近,星团间的星星距离就比较远了。

K-means与EM的关系:

  1. EM的基本思想: > - E步:固定参数θ,优化隐含类别Q > - M步:固定隐含类别Q,优化参数θ

  2. K-means用到的EM的基本思想: > - E步:确定隐含类别变量c > - M步:更新其他参数μ来使J最小化

  3. 两种算法都类似于坐标上升法。固定一个,优化另外一个。

机器学习11-2--怎样用机器学习ML解决问题和在线学习

发表于 2014-06-05 | 分类于 机器学习 | | 阅读次数:
字数统计: 481 | 阅读时长 ≈ 1

机器学习11-2--怎样用机器学习ML解决问题和在线学习

本章讲了,通过误差、偏差和优化算法来进行算法的调试。并讲了一些调试的方法。然后,进行了误差分析,去掉一些不必要的特征。最后举例说明。

算法的调试(Debugging Learning Algorithms)

存在的问题

1、对于贝叶斯逻辑回归问题: 2、如果,误差太大,我们怎样做? 3、很显然,这样很耗时。

改进方法1:方差variance和偏差bias分析

改进方法2:优化算法和参数

参数是否恰当

算法是否收敛;是否正确优化了函数。

优化算法:通过对比两种算法

改进方法3:直觉

总结

出现的问题,及其解决方法:

误差分析和销蚀分析( Error analyses and ablative analysis)

误差分析

通过加入新的成分使得准确率逐步升高: ### 销蚀分析 逐一去除某一成分,分析那一个去除时,准确率下降最快。

###总结 - Error analysis tries to explain the difference between current performance and perfect performance. - Ablative analysis tries to explain the difference between some baseline (much poorer) performance and current performance.

实例问题分析(Getting started on a learning problem)

要解决一个问题,下面列出了两种方法。我们一般采用方法2(Approach #2)。因为,此方法可以快速实现我们的要求。此方法看似简单,但是NG说,很多人没有按照步骤做,结果导致半年甚至一年时间白白浪费掉。

总结

在线学习(online learning)

这一节相对比较独立,我就放在这里吧。 > 1. 以前我们的学习算法:批学习算法(batch learning);这里为:在线学习(online learning)。 2. 简而言之,每增加一个样本 都要重新计算一次\(\theta\) 。即:

eg:我们举一个简单的例子,在逻辑回归中

机器学习11-1--贝叶斯统计和规则化

发表于 2014-06-05 | 分类于 机器学习 | | 阅读次数:
字数统计: 972 | 阅读时长 ≈ 3

机器学习11-1--贝叶斯统计和规则化

贝叶斯统计和规则化( Bayesian statistics and regularization)

  • 贝叶斯统计和规则化的目的:找更好的估计方法来减少过度拟合情况的发生。
  • 回顾,总结: > 1. 线性回归中使用的估计方法是最小二乘法
  1. logistic 回归是条件概率的最大似然估计
  2. 朴素贝叶斯是联合概率的最大似然估计
  3. SVM 是二次规划。

频率学派和贝叶斯学派

看待 \(\theta\) 的角度不同 #### 频率学派(frequentist statistics) 认为θ不是随机变量,只是一个未知的常量,因此我们没有把 #### 贝叶斯学派(Bayesian) 认为θ是随机变量。 步骤: 1、先验概率p(θ):不同的θ值就有不同的概率。训练集:。则:θ的后验概率: > 分母有误:

2、在θ是随机变量的情况下,如果新来一个样例特征为 x,那么为了预测 y。我们可以使用下面的公式: > 注:在不同的模型下计算方式不同。比如在贝叶斯 logistic 回归中: 其中,

3、进而得到期望: > 

4、注: > 1. 这次求解p(y|x, S)与之前的方式不同,以前是先求θ,然后直接预测,这次是对所有可 能的θ作积分。 2. 贝叶斯估计将θ视为随机变量,θ的值满足一定的分布,不是固定值,我们无法通过计算获得其值,只能在预测时计算积分。 3. 由于上述问题的存在;显然,后验概率p(θ|S)很难计算。为了解决这个问题,我们需要改变思路。看p(θ|S)公式中的分母,分母其实就是 P(S),而我们就是要让P(S)在各种参数的影响下能够最大(这里只有参数θ) 。 因此我们只需求出随机变量θ中最可能的取值,这样求出θ后,可将θ视为固定值,那么预测时就不用积分了,而是直接像最大似然估计中求出θ后一样进行预测,这样就变成了点估计。这种方法称为MAP 最大后验概率估计(Maximum a posteriori)方法。

5、MAP 最大后验概率估计(Maximum a posteriori)方法,Θ估计公式为 >

6、进行预测: > \(h_{\hat{\theta}_{MAP}}(X)=\hat{\theta}_{MAP}^{T}X\)

7、总结与应用: > 1. 与最大似然估计对比发现,MAP 只是将θ移进了条件概率中,并且多了一项p(θ)。 2. 一般情况下我们认为。 3. 贝叶斯最大后验概率估计相对于最大似然估计来说更容易克服过度拟合问题。原因: >> a. 整个公式由两项组成,极大化时,不代表此时p(θ)也能最大化。相反,θ是多值高斯分布,极大化时, p(θ)概率反而可能比较小。要达到最大化需要在两者之间达到平衡,也就靠近了偏差和方差线的交叉点。 b. 这个跟机器翻译里的噪声信道模型比较类似,由两个概率决定比有一个概率决定更靠谱。作者声称利用贝叶斯 logistic 回归(使用θMAP的 logistic 回归)应用于文本分类时,即使特征个数 n 远远大于样例个数 m,也很有效。

L1和L2规则化???????

老师上课没有讲到该部分,看了一下Pro Set3。也不是很理解。先引出正则化参数的损失函数,然后介绍了怎样最小化损失函数(过程不是很理解)。对于L1和L2在ODPS的XLab中有提到。后面,再仔细研究研究。对于L2:将后面一项改为2范数。 ### 贝叶斯xi回归L1

机器学习10--学习理论的基础知识

发表于 2014-06-05 | 分类于 机器学习 | | 阅读次数:
字数统计: 585 | 阅读时长 ≈ 2

机器学习10--学习理论的基础知识

本章:模型选择(交叉选择的方法)-->特征选择。

模型选择

  • 设可选的模型集合为: ,那么 SVM、 logistic 回归、神经网络等模型都包含在 M 中。
  • 训练集使用 S 来表示
  • 任务:从 M 中选择最好的模型

方法一:简单交叉验证(数据集大)

> - 测试集的比例一般占全部数据的 1/4-1/3。30%是典型值。 > - 由于测试集是和训练集中是两个世界的,因此我们可以认为这里的经验错误接近于泛化错误。 > - 得到的最好模型,在全部数据上重新训练的到所需模型。

方法二:k-折叠交叉验证(数据集小)

> - 简而言之,这个方法就是将简单交叉验证的测试集改为 1/k,每个模型训练 k 次,测试 k 次,错误率为 k 次的平均。 - 一般讲k 取值为 10 - 数据集非常小的时候:极端情况下,k 可以取值为 m,意味着每次留一个样例做测试,这个称为 leave-one-out cross validation。

特征选择

  • 其实,很多特征对于结果是无用的,想剔除 n 中的无用特征。n 个特征就有\(2^n\)种去除情况(每个特征去或者保留)。属于NP难问题。
  • 本节主要将该问题简化:NP难\(2^n\)-->\(n^2\)-->\(n\)

第一种:启发式搜索方法:前向搜索和后向搜索\(O(n^2)\)

\(时间 复杂度为O(n + (n − 1) +(n − 2) + ⋯ + 1) = O(n^2)\)。 #### 前向搜索 #### 后向搜索 先将 F 设置为{1,2,..,n},然后每次删除一个特征,并评价,直到达到阈值或者为空,然后选择最佳的 F。 ### 第二种:过滤特征选择(Filter feature selection)\(O(n)\) 过滤特征选择方法的想法是针对每一个特征 ,i 从 1 到 n,计算相对于类别标签y的信息量S(i),得到 n 个结果,然后将 n 个S(i)按照从大到小排名,输出前 k 个特征。显然,这样复杂度大大降低,为 O(n)。 > 1、 $x_i \(是 0/1 离散值的时候 :** 互信息(Mutual information)公式:![](/img/1401938493509.png) 2、**\)x_i $是多个离散值 注:

机器学习9--学习理论的基础知识

发表于 2014-06-05 | 分类于 机器学习 | | 阅读次数:
字数统计: 833 | 阅读时长 ≈ 3

#机器学习9--学习理论的基础知识 ## 基本符号 > - \(\epsilon\) 泛化误差: >> - 从训练样本数据中推导的规则,能够适用于新的样本的能力。 >> - 对服从分布D的样本,分类错误的概率。 - \(\hat{\epsilon}\) 训练误差 >> - 训练误差在训练样本中训练出的规则,能够适用于训练样本的能力。 >> - 对训练样本,分类错误的部分,在总的训练集中所占比例。 - \(h\) - \(\hat{h }\) >> - \(\theta\) 和 \(\hat{\theta }\)关系:ERM风险最小化\(\theta\)的过程: - \(h\)和 \(\hat{h }\)关系:ERM风险最小化\(h\)的过程: - \(\epsilon\)和\(\hat{\epsilon}\)关系:误差随着模型复杂度(VC维)**的增加的变化趋势。模型复杂度过低:欠拟合;过大:过拟合。其中,模型复杂度为假设类\(\left| H\right|\)的大小,比如:某一个值为多项式多次。 >>

  • \(H\):假设类。对于先行分类器:
  • \(D\): 某一种分布。

基本公式

1、 2、 3、

##两个引理 1、联合界引理: 2、Hoeffding不等式 > 利用中心极限定理进行推导。其物理意义如下图所示。其中,表示阴影的概率,即错误的上届概率。当m增大时,钟形图收缩,误差下降。

\(H\)为有限的

即: 其中,H为: 1、 2、 即: > 表示: - \(m\)很大时,右边很小,两个误差很接近。 - 是人为给定的值。

3、对于任意h: 4、对于任意非h: > \(m\)很大时,右边很小,两个误差很接近。称为:一致收敛

5、我们关心的是m(样本大小), (两个误差的差值)和概率(两个误差接近的概率)三者的值。下面,我们对其进行求解。 6、令,当时,我们得到样本的大小: 7、进一步,我们得到的值: 8、对7进行展开: 9、最终得到我们的定理:得到 \(\gamma\) 的值 > 物理意义:我们可以近似地认为:为假设类H的偏差bias;为假设的方差variance。偏差表示误差的大小,随着模型复杂度增大而减小;方差表示拟合得有多好,随着模型复杂度增大,而先减小后增大。如下图:

10、最终,我们还得到另外一个定理,简而言之,固定,求m: > 两个误差收敛的概率

下面开始为第10j ## \(H\)为无限的--更实用 当H有无限值时,即:**$|H|==k \(**。则上面公式10中![](/img/1401850414368.png),k将趋于无穷大;则m将无穷大。显然,这样是不行的。为了解决这种问题我们引入VC维。从而得到我们的理论。 ### shatters的定义 ![](/img/1401931065879.png) ### VC维的定义: ![](/img/1401931155527.png) > 结论:**对于n维线性分类器:\)VC(H)=n+1\(** eg. ![](/img/1401931314231.png)时:\)VC(H)=3$

最终我们得到学习理论中的重要理论:

1、定理:得到 \(\gamma\) 的值

> - m为样本数目; - ,从而我们可以得到\(\gamma\)的值。

2、推论:得到\(m\)的值

总结

通过学习本节我们可以大概知道:SVM和LR都不是直接的ERM算法,都是对其近似。本章推荐的理论给出了这两种算法的直观含义的一种解释。如下图:

1…678
DanielJyc

DanielJyc

数据驱动 Java 大数据 算法

40 日志
5 分类
28 标签
RSS
Links
  • Danieljyc blog
© 2014 — 2019 DanielJyc | Site words total count: 53k
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.4
京ICP备 - 19007489号