第一课 课程导言

• 涵盖由浅入深的一系列机器学习技术
• 将会学到：
  • PCA, MDS, K-mean, 基于频谱的聚类方法，贝叶斯分类，boosting, logistic回归，决策树，EM算法，隐马尔可夫模型，卡尔曼滤波……
• 讲述算法、理论、应用背后的故事
• 将会既有趣又辛苦

• 03.04 介绍
• 03.11 分类
• 03.18 聚类
• 03.25 隐马尔可夫与卡尔曼滤波

• 简即美
• 在理论性和应用性上达到平衡

• 概率论
  • 分布、密度、边界……
• 统计基础
  • 矩、经典分布、回归……
• 算法
  • 动态规划、基本数据结构、复杂度……
• 编程
  • C/C++, Java, Matlab……
• 将会提供一些背景知识，但课程步调还是会比较快
• 处理抽象数学概念的能力

• Machine Learning
  • by Tom Mitchell
• Pattern Classsification (2^nd Edition)
  • by Duda, Hart and Stork
• Information Theory, Inference, and Learning Algorithm
  • by David MacKay
• Statistical Inference
  • by George Casella and Roger L. Berger
• Pattern Recogniation and Machine Learning
  • Christopher M.Bishop
• And more …
• 以上均为可选参考书目，每人都会有自己的学习方法

• http://www.cad.zju.edu.cn/home/zhx/csmath/

• 机器学习在科学、工作及其它领域正变得无所不在
• 本课程将提供应用机器学习、开发新方法的基础

• 背景
• 什么是机器学习
• 机器学习对于计算机科学和技术有何帮助

• 数据，数据，数据……
  • 需要大量乏味的重复的工作才能创建数字化的世界
    • 需要寻找新的交互方式，创造新类型的媒体
    • 花费高的代价才能请专家（科学家、工程师、电影制作人员、图形设计师、优秀艺术家和游戏设计人员）来完成工作
• 需要高效地处理已经存在的数据，并通过它们获得新的数据

• 各种图像、场景，只要人能够创造，就可以利用计算机来得到它
• 但是如何来创造这些图像、场景

• 为电影中的一个角色创造动作
  • 完全过程化合成
    • 动作比较连贯，但是很容易让人觉得是伪造的，很少在实际中这样用
  • 完全手工制作或者完全数据化
    • 效果质量很高，但是连贯性不好
  • 把两者结合起来的混合方法或许是最好的！？

• 关于不确定性的一个规则模型
• 非结构化数据的通用模型
• 数据拟合和不确定分析的有效算法

但是，当前它通常被当做一个黑盒来使用

确定性 VS 机率性

机器学习 != 人工智能

• Mitchell在1997年定义的：机器学习乃于某类任务兼性能度量的经验中学习之程序；若其作用于任务，可由度量知其于已知经验中获益。
• Hertzmann在2003年的评论：对于计算机图形学上的一些应用，机器学习应该被看作处理数据的一系列技术。给定一些数据，可以得到一个方法模型用于生产新的数据。
• 编制学习系统不只是用来解决一个问题，而是基于一些特征来使系统本身更加优化：
  • 关于系统应该如何做出响应的一些例子
  • 关于系统在解决问题的过程中反复试验学习到的经验
• 不同于通常的计算机科学，去实现一个未知的功能；仅仅是处理已知的输入输出数据对（学习过程中的训练例子）

• 学习情景根据训练例子中提供的有效信息的改变而改变
  • 监督的：需要正确的输出
    • 分类：输入N个目标，输出结果为选择其中一个（语音识别、目标辨认、医学诊断）
    • 回归：输出准确值（预测未来的市场价格、温度）
  • 部分监督的：只输出一部分有效结果
  • 无监督的：没有反馈，需要对输出进行自我评估
    • 聚类：聚类是指将数据分割成连贯的群集的技术
    • 结构异常识别：检测超出正常范围的数据点
  • 加强的:标量反馈,可能暂时推迟

• 时间序列分析
• 降维
• 模型选择
• 泛型方法
• 图形建模

• 开发强化的计算机系统
  • 能够自动适应用户，更加符合用户要求
  • 旧的系统往往很难获得必要的知识
  • 发掘大型数据库中离线的新数据挖掘模式
• 提高对人的认识，生物学习
  • 提供具体的理论计算分析，预测
  • 分析大脑的学习过程中的爆发式活动
• 研究时机很好
  • 数据量的快速增长
  • 计算机不再昂贵而且功能强大
  • 理论得到了很好的发展，有一系列的算法组件

• 赞成方：所有事物都是机器学习，所有事物都是人的调整
  • 在有些时候，这个说法是正确的
• 反对方：虽然是对“学习”的一种深化，但还有其它更强大和有效的算法。
  • 问题分类
  • 通用模型
  • 通过概率进行推算
• 相信数学的魔力

• 计算效率
• 鲁棒性
• 统计稳定性

• Google!
• 目标识别和辨认——机器学习的力量
• 文档处理——贝叶斯分类器
• 网格处理——数据聚类和分割
• 纹理合成和分析——隐式马尔科夫模型
• 反射纹理合成——降维
• 人体建模——降维
• 图像处理和合成——图形建模
• 人体运动合成——时间序列分析
• 视频纹理——强化学习

• 机器学习就是这样简单明了的东西
  • 关键字：
    • 名词：数据、模型、模式、特征
    • 形容词：概率性的、统计的
    • 动词：拟合、推理、挖掘

• 在你的研究方向上寻找机器学习的潜在应用

• Reinforcement learning: A survey

• 通用图灵机模型与冯诺依曼架构在并行处理上的局限[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

最大似然, 最大化后验估计, 贝叶斯估计, 回归方法与过拟合问题

• 点估计
  • 最大似然估计(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: 找出使观察到的现象的概率最大化的 θ

• 导数为0时取极值，则有

θ<sup>^</sup> = α<sub>T</sub> / α<sub>H</sub> + α<sub>T</sub>
* 富：我抛了两个头朝上和三个尾朝上
* 你：θ是3/5，我可以证明
* 富：如果我抛了20个头朝上和30个尾朝上呢
* 你：答案依然一样，我可以证明
* 富：能多解释一下吗
* 你：越多约好吗
* 富：所以我才会给你这么多报酬啊

• 对于N = α_H + α_T 和 θ^{^} = α_T / α_H + α_T,有
• 令θ^*为真实值，对任意ε>0，有

P(|θ^{^} - θ^*|≥ε)≤2e^{-2Nε^2}