====== 第一课 课程导言 ======
===== 1.1 导言 =====
===大纲===
* 涵盖由浅入深的一系列机器学习技术
* 将会学到:
*PCA, MDS, K-mean, 基于频谱的聚类方法,贝叶斯分类,boosting, logistic回归,决策树,EM算法,隐马尔可夫模型,卡尔曼滤波……
*讲述算法、理论、应用背后的故事
*将会既有趣又辛苦
===时间安排===
*03.04 介绍
*03.11 分类
*03.18 聚类
*03.25 隐马尔可夫与卡尔曼滤波
===原则===
*简即美
*在理论性和应用性上达到平衡
===先修课程===
*概率论
* 分布、密度、边界……
* 统计基础
* 矩、经典分布、回归……
* 算法
* 动态规划、基本数据结构、复杂度……
* 编程
* C/C++, Java, Matlab……
* 将会提供一些背景知识,但课程步调还是会比较快
* 处理抽象数学概念的能力
===参考书===
*[[http://www-2.cs.cmu.edu/~tom/mlbook.html|Machine Learning]]
* by Tom Mitchell
* [[http://rii.ricoh.com/~stork/DHS.html|Pattern Classsification (2nd Edition)]]
* by Duda, Hart and Stork
* [[http://www.cs.toronto.edu/~mackay/itila/|Information Theory, Inference, and Learning Algorithm]]
* by David MacKay
* **Statistical Inference**
* by George Casella and Roger L. Berger
* [[http://research.microsoft.com/en-us/um/people/cmbishop/prml/|Pattern Recogniation and Machine Learning]]
* Christopher M.Bishop
* And more ...
* 以上均为可选参考书目,每人都会有自己的学习方法
===网络资源===
*http://www.cad.zju.edu.cn/home/zhx/csmath/
===享受之!===
*机器学习在科学、工作及其它领域正变得无所不在
*本课程将提供应用机器学习、开发新方法的基础
===== 1.2 机器学习单元概况 =====
===== 1.3 什么是机器学习? =====
===大纲===
* 背景
* 什么是机器学习
* 机器学习对于计算机科学和技术有何帮助
===当今计算机科学的最大挑战===
* 数据,数据,数据……
* 需要大量乏味的重复的工作才能创建数字化的世界
* 需要寻找新的交互方式,创造新类型的媒体
* 花费高的代价才能请专家(科学家、工程师、电影制作人员、图形设计师、优秀艺术家和游戏设计人员)来完成工作
* 需要高效地处理已经存在的数据,并通过它们获得新的数据
===计算机是高效运行的机器===
* 各种图像、场景,只要人能够创造,就可以利用计算机来得到它
* 但是如何来创造这些图像、场景
===完全过程化合成VS完全数据化===
* 为电影中的一个角色创造动作
* 完全过程化合成
* 动作比较连贯,但是很容易让人觉得是伪造的,很少在实际中这样用
* 完全手工制作或者完全数据化
* 效果质量很高,但是连贯性不好
* 把两者结合起来的混合方法或许是最好的!?
===贝叶斯推理===
* 关于不确定性的一个规则模型
* 非结构化数据的通用模型
* 数据拟合和不确定分析的有效算法
**但是,当前它通常被当做一个黑盒来使用**
**确定性 VS 机率性**
===数据驱动模型===
{{:keynote:81.jpg?500*320}}
===什么是机器学习===
{{:keynote:82.jpg?500*320}}
**机器学习 != 人工智能**
* Mitchell在1997年定义的:机器学习乃于某类任务兼性能度量的经验中学习之程序;若其作用于任务,可由度量知其于已知经验中获益。
* Hertzmann在2003年的评论:对于计算机图形学上的一些应用,机器学习应该被看作处理数据的一系列技术。给定一些数据,可以得到一个方法模型用于生产新的数据。
* 编制学习系统不只是用来解决一个问题,而是基于一些特征来使系统本身更加优化:
* 关于系统应该如何做出响应的一些例子
* 关于系统在解决问题的过程中反复试验学习到的经验
* 不同于通常的计算机科学,去实现一个未知的功能;仅仅是处理已知的输入输出数据对(学习过程中的训练例子)
===学习问题的主要分类===
* 学习情景根据训练例子中提供的有效信息的改变而改变
* 监督的:需要正确的输出
* 分类:输入N个目标,输出结果为选择其中一个(语音识别、目标辨认、医学诊断)
* 回归:输出准确值(预测未来的市场价格、温度)
* 部分监督的:只输出一部分有效结果
* 无监督的:没有反馈,需要对输出进行自我评估
* 聚类:聚类是指将数据分割成连贯的群集的技术
* 结构异常识别:检测超出正常范围的数据点
* 加强的:标量反馈,可能暂时推迟
===更多信息===
* 时间序列分析
* 降维
* 模型选择
* 泛型方法
* 图形建模
===为什么要学习机器学习?===
* 开发强化的计算机系统
* 能够自动适应用户,更加符合用户要求
* 旧的系统往往很难获得必要的知识
* 发掘大型数据库中离线的新数据挖掘模式
* 提高对人的认识,生物学习
* 提供具体的理论计算分析,预测
* 分析大脑的学习过程中的爆发式活动
* 研究时机很好
* 数据量的快速增长
* 计算机不再昂贵而且功能强大
* 理论得到了很好的发展,有一系列的算法组件
===机器学习对计算机科学和技术有用吗?===
* 赞成方:所有事物都是机器学习,所有事物都是人的调整
* 在有些时候,这个说法是正确的
* 反对方:虽然是对“学习”的一种深化,但还有其它更强大和有效的算法。
* 问题分类
* 通用模型
* 通过概率进行推算
* 相信数学的魔力
===怎样才是一个成功的机器学习算法?===
* 计算效率
* 鲁棒性
* 统计稳定性
===一些实际应用===
* Google!
* 目标识别和辨认——机器学习的力量
* 文档处理——贝叶斯分类器
* 网格处理——数据聚类和分割
* 纹理合成和分析——隐式马尔科夫模型
* 反射纹理合成——降维
* 人体建模——降维
* 图像处理和合成——图形建模
* 人体运动合成——时间序列分析
* 视频纹理——强化学习
===总结===
* 机器学习就是这样简单明了的东西:-D
* 关键字:
* 名词:数据、模型、模式、特征
* 形容词:概率性的、统计的
* 动词:拟合、推理、挖掘
===作业===
* 在你的研究方向上寻找机器学习的潜在应用
===参考文献===
* Reinforcement learning: A survey
Edit by Xinyuan Luo(骆歆远),
===未来体系结构对机器学习的支持===
* 通用图灵机模型与冯诺依曼架构在并行处理上的局限[1]
* 冯诺依曼架构源自通用图灵机模型(Universal Turing Machine)
* 优点:便于建造、编程
* 缺点:“解析指令->执行指令->处理数据”这种循环存在瓶颈,不利于并行处理
* 设计与演化:生物神经元系统的达尔文主义解释[2]
* 生物的神经元网络是基于达尔文进化论的模式演化出来的
* 知识和技能都是通过后天的不断学习和训练获得。在这种学习和训练中,大脑中神经元网络的结构不断完善
* 不论是对一个物种的长期进化而言,还是单个个体的一生成长而言,其大脑的学习过程都是进化论(Darwinism)的
* 区别“知识”与“技能”,即"Knowledge" vs "Skill"
* 机器学习形成的知识,其应用过程的算法效率未必最优
* 等价的知识,存在多种表达和应用方式
* 对某一知识,更高效的表达和应用算法,可以称之为技能(Skill),以区别于知识(Knowledge)
* 技能可以通过设计获得,也可以通过演化获得。
* 演化思想在计算模式与体系结构设计中的萌芽
* 自动并行化研究[3,4,5]
* 代码级别的知识学习与存储[6]
* 未来发展
* 更高效的核间通讯:NoC、片上光通信
* 新的计算模型:函数式编程语言、并行计算语言、GPGPU
* 自主进化(可重构)的众核处理器架构
* 参考文献
* [1] John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Commun. ACM, Vol. 21, No. 8. (August 1978), pp. 613-641. doi:10.1145/359576.359579
* [2] Gerald Edelman, "Bright Air and Brilliant Fire: on the matter of mind", New York: Basic Books, 1992.
* [3] Gurindar S. Sohi, Scott E. Breach, T. N. Vijaykumar, Multiscalar Processors, SIGARCH Comput. Archit. News In ISCA '95: Proceedings of the 22nd annual international symposium on Computer architecture, Vol. 23 (May 1995), pp. 414-425. doi:10.1145/223982.224451
* [4] L. Hammond, B. A. Hubbert, M. Siu, M. K. Prabhu, M. Chen, K. Olukolun, The Stanford Hydra CMP, IEEE Micro, Vol. 20, No. 2. (March 2000), pp. 71-84. doi:10.1109/40.848474
* [5] Guilherme Ottoni, Ram Rangan, Adam Stoler, David I. August, Automatic Thread Extraction with Decoupled Software Pipelining,Microarchitecture, 2005. MICRO-38. Proceedings. 38th Annual IEEE/ACM International Symposium on In Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture (2005), pp. 105-118. doi:10.1109/MICRO.2005.13
* [6] Yushi Kamiya, Tomoaki Tsumura, Hiroshi Matsuo, Yasuhiko Nakashima, A Speculative Technique for Auto-Memoization Processor with Multithreading, (December 2009), pp. 160-166. doi:10.1109/PDCAT.2009.67
Edit by Ye Minjiao (叶敏娇, 11021036),
===== 1.4 点估计 =====
最大似然, 最大化后验估计, 贝叶斯估计, 回归方法与过拟合问题
==== 你将要学习 ====
* 点估计
* 最大似然估计(MLE, Maximal Likelihood Estimation)
* 贝叶斯学习(Bayesian Learning)
* 最大化后验(MAP, Maximize A Posterior)
* 高斯估计
* 回归(Regression)
* 基础方程 = 特性
* 方差和的最优化
* 回归与高斯估计的关系
* 倾向与方差的折中
==== 你的第一个咨询工作 ====
* 一个北京的IT亿万富翁咨询你如下问题:
* 富:我有一些图钉,我将其抛出,那么它尾部朝上的概率是多少?
* 你:那么扔几次看看吧...
* (图待上传)
* 你:概率是3/5
* 富:这是为什么呢?
* 你:这是因为...
==== 二值分布 ====
* 设头朝下的概率 P(Heads)= θ,尾朝下的概率 P(Tails)=1-θ,发生的事件D={T,H,H,T,T}
* 抛图钉是一种独立重复分布(i.i.d. Independent Identically distributed)
* 每一次实验彼此独立
* 根据二值分布的分布概率相同
* 如果一个事件D包含αH个头朝下的概率和αT个尾朝下的概率,这样事件的概率是:\\P(D|θ)=θαH(1-θ)αT
==== 最大似然估计 ====
* 数据:观察事件集合D包含α H 个头朝下的事件和α T 个尾朝下的事件
* 前提:二值分布
* 在优化问题中对θ进行学习:
* 目标函数是什么?\\ D = {T, H, H, T, T}
* MLE: 找出使观察到的现象的概率最大化的 θ
\begin{aligned}
\hat{\theta} & = \arg\max_\theta P(D|\theta) \\\\
& = \arg\max_\theta \ln P(D|\theta) \\\\
& = \arg\max_\theta \ln (\theta^{\alpha_H} (1-\theta)^{\alpha_T}) \\\\
& = \arg\max_\theta \alpha_H\ln\theta + \alpha_T\ln(1-\theta)
\end{aligned}
* 导数为0时取极值,则有
\[
\hat{\theta} = \frac{\alpha_T}{\alpha_H+\alpha_T} = \frac{3}{2+3}
\]
==== 我需要抛多少次? ====
θ^ = αT / αH + αT
* 富:我抛了两个头朝上和三个尾朝上
* 你:θ是3/5,我可以证明
* 富:如果我抛了20个头朝上和30个尾朝上呢
* 你:答案依然一样,我可以证明
* 富:能多解释一下吗
* 你:越多约好吗
* 富:所以我才会给你这么多报酬啊
==== 简单边界(基于Höffding不等式) ====
* 对于N = αH + αT 和 θ^ = αT / αH + αT,有
* 令θ*为真实值,对任意ε>0,有
P(|θ^ - θ*|≥ε)≤2e-2Nε^2
edit by Zhang Li,[[zhangli85@zju.edu.cn]]