计算思维导论第15讲-机器怎样学习

第15讲机器学习与人工智能哈尔滨工业大学计算学部教学委员会主任国家教学名师战德dechen@第15讲机器学习一、从AlphaGo看人工智能二、机器学习的基本思维—有监督学习-分类三、机器学习的基本思维—无监督学习-聚类四、机器学习的基本思维—其他【思考】AlphaGo战胜人类围棋世界冠军为什么引发了人工智能的高关注度？AlphaGo使用了什么样的创新技术，这些技术对人工智能发展有什么意义？

从AlphaGo看人工智能AlphaGo是什么？AlphaGo是首个击败人类围棋选手职业冠军的计算机程序从AlphaGo看人工智能围棋规则及行棋复杂性棋盘：19*19的平行线构成，形成361个交叉点，交叉点放置棋子。对局：双方各执一色棋子，轮流下子于交叉点。胜负：围住空间多的一方获胜。复杂性：假如用1,2,…,361来表示每一个交叉点即棋子位置，则一盘棋局就是这些棋子位置的一种组合。而棋盘上所有可能位置组合(枚举)多达10170(=3361)：361个位置，每个位置黑子、白子、无子3种状态），是一种非常复杂的游戏。围棋可观测宇宙的直径达920亿光年，包含不计其数的星系，估算出的原子总量也只有1080个从AlphaGo看人工智能围棋的智能问题围棋形势判断围棋形势的判断行棋到某一状态时，对围棋胜负局面的判断围棋待行棋位置的决策轮黑方或白方下子时，选择哪一个交叉点落子才能取胜机器是怎样通过学习提高智能的？围棋对弈与人工智能和机器学习有什么关系？人工智能机器学习有监督学习无监督学习半监督学习强化学习专家系统多智能体系统演化计算知识表示深度学习机器学习是一门从数据中研究算法的多领域交叉学科。机器学习研究计算机如何模拟或实现人类的学习行为机器学习从以往的经验中得到数据，通过学习构建模型，预测新数据，并提供对问题的决策支持典型方法：决策树、随机森林、人工神经网络、贝叶斯学习、关联规则学习、深度学习等数据模型决策学习经验从AlphaGo看人工智能机器学习与人工智能机器是怎样学习的？……AlphaGo战胜人类围棋世界冠军为什么引发了人工智能的高关注度，你的理解是___________。因为围棋被认为是一种非常复杂的游戏，其解空间非常庞大。在如此庞大的解空间中，AlphaGo能够战胜人类顶尖棋手，说明机器“智能”的强大AlphaGo推动了机器学习，尤其是深度学习技术的发展AlphaGo推动了强化学习--自主学习技术的发展AlphaGo运用了多种技术，体现的不仅仅是算力的提升，还包括在搜索过程中如何通过优化降低搜索空间ABCD提交E除上述外，还有许多…投票最多可选5项第15讲机器学习一、从AlphaGo看人工智能二、机器学习的基本思维—有监督学习-分类三、机器学习的基本思维—无监督学习-聚类四、机器学习的基本思维—其他【示例】有100个病患，已知每个病患的两个项目的检查数据，且每个病患的诊断结果（疾病类别1或疾病类别2）已知。问：如何根据这些数据反推出疾病诊断的标准并用于对未分类病患的疾病诊断？机器学习的基本思维—有监督学习-分类已知模型，对【数据】进行分类--两特征两类别分类问题怎样求出这条直线的方程呢？待求方程形式：其中<x(i),y(i)>为样本点，而为按方程计算的点已知样本数据及其分类结果，反求模型：线性回归（拟合）【线性回归】枚举w和b，使【损失函数】L值最小枚举-计算-验证-优化算法

算法：最小二乘法、梯度下降法（略）机器学习的基本思维—有监督学习-分类两特征方程形式：多特征方程形式：机器学习的基本思维—有监督学习-分类多特征线性方程形式：多特征两类别分类模型形式一定是线性的吗？模型假设？---仍用直线分割（分类）？模型假设？---用曲线如何？理想很丰满，现实很骨感--对于更复杂的数据，如何求解？机器学习的基本思维—有监督学习-分类曲线拟合分类问题：线性分类vs.非线性分类数学是不是很有用呢？哪些函数形式能产生什么形式的曲线？机器学习的基本思维—有监督学习-分类曲线拟合存在的问题：【欠拟合】与【过拟合】

机器学习的基本思维—有监督学习-分类逻辑回归：将结果映射为0和1的函数—如何判断边界内外

分类问题模型形式具有待确定参数w1,w2,…wn的关于x1,x2,…xn的一组方程分类/识别（已知方程求分类结果）结果S属于哪一类别的判断已明确分类结果(标签)的样本数据集合{Si,<标签>}其中每个Si都有n个特征值Si:(x1,x2,…xn)

训练/学习已知分类结果,反求方程参数w1,w2,…wn模型具有明确参数的w1,w2,…wn的一组方程待分类的数据S:(x1,x2,…xn)

已标注标签的样本数据集合{Si,<标签>},其中每个Si都有n个特征值Si:(x1,x2,…xn)

调试/开发(调优:改变学习过程的一些参数，如迭代次数、收敛程度等)机器学习的基本思维—有监督学习-分类机器学习的基本概念与过程你知道了吗：什么是训练？什么是调试？什么是识别？要开发什么？例如：训练集:验证集:测试集=7：1：2多类分类问题可以转化为两类分类问题进行解决--例如将其中一个类视为正类、其它类统一视为负类ONE-VS-REST模式）推广到多类问题，如何求解？机器学习的基本思维—有监督学习-分类多类别分类问题机器学习的基本思维—有监督学习-分类运用两分类方法解决多分类问题【One-vs-One】一种运用两分类方法解决多类别分类问题的思想(1)将小说、散文、诗歌、戏剧，两两组合组成6个两类别分类器CiC1(小说，散文)，C2(小说，诗歌)，C3(小说，戏剧)

C4(散文，诗歌)，C5(散文，戏剧)，C6(诗歌，戏剧)(2)应用这6个两类别分类器对新文章归类，假设得到的结果是:C1-小说，C2-小说，C3-小说，C4-散文，C5-散文，C6-诗歌(3)从上述结果中选择归属类别多的作为该篇文章的分类类别【示例】一篇文章，可被分类为小说、散文、诗歌、戏剧等等。一篇新文章，应该归到哪一类呢？机器学习的基本思维—有监督学习-分类运用两分类方法解决多分类问题【One-vs-Rest】另一种运用两分类方法解决多类别分类问题的思想(1)四个类别构造4个两类别分类器CiC1(小说，非小说)，C2(散文，非散文)，C3(诗歌，非诗歌)，C4(戏剧，非戏剧)每个分类器的结果是一种概率：(以C1为例)小说的概率为70%，非小说的概率为30％。(2)应用这4个两类别分类器对新文章归类，假设得到的结果是:

C1-小说的概率是70%；C2-散文的概率是50%；

C3-诗歌的概率是40%；C4-戏剧的概率是30%；(3)从上述结果中选择概率最大的类别作为该篇文章的分类类别【示例】一篇文章，可被分类为小说、散文、诗歌、戏剧等等。一篇新文章，应该归到哪一类呢？问题：假设有N个类别的分类问题，分别采用One-vs-One和One-vs-Rest模式，问：分别需要构建多少个二类别分类器？N,NCN2，NN，CN2CN2,CN2ABCD提交单选题1分监督学习是用已知类别【标签】的样本来学习模型参数分类：对离散数据，寻找决策边界（属于哪一类）回归：对连续数据，寻找最优拟合无监督学习是用未知类别【标签】的样本来学习模型参数聚类：一组数据究竟应该分为几类，怎样将样本分类到不同的类别中机器学习的基本思维—有监督学习-分类有监督学习与无监督学习什么是机器学习？你的理解是___________。机器学习是一种利用大量数据反求模型的一种技术机器学习，包括有监督学习和无监督学习有监督学习，就是从大量有标签(分类结果标识)数据集中通过学习获得模型（分类模型）的一种机器学习方法无监督学习，就是从大量无标签(分类结果标识)数据集中通过学习获得模型（分类模型）的一种机器学习方法ABCD提交E机器学习，就是先假定模型形式给定初值，然后依据其对数据的分类/聚类结果与事实中的分类/聚类结果的偏差，返回去调整模型的参数。重复此一过程直到偏差越来越小多选题1分第15讲机器学习一、从AlphaGo看人工智能二、机器学习的基本思维—有监督学习-分类三、机器学习的基本思维—无监督学习-聚类四、机器学习的基本思维—其他【类】，类别，指的是具有某种相似性的对象集合。【聚类】是指将数据集划分为若干类别，使得类内之间的数据呈现更高的相似度（差别更小），而各类之间的数据呈现更低的相似度（差别更大）。它以相似性为基础，归于无监督学习范畴。机器学习的基本思维—无监督学习-聚类聚类的概念机器学习的基本思维—无监督学习-聚类一种聚类方法示例【示例】假设有9个样品S1-S9，每个仅测量一项指标，指标值分别是1，2，5，8，11，12，16，18，20。如何聚类？（1）初始：9个样品9个类别，S1-S9。计算类别之间的距离如左图。（2）将类别之间的距离<=1的合并，形成S12,S3,S4,S56,S7,S8,S9={1.5，5，8，11.5，16，18,20}七个类别。计算类别之间的距离如右图。

S1S2

S3

S4

S5

S6

S7

S8

S9S1

0

1471011151719

S2

036910141618

S3

0367111215S4

03481012

S5

01579

S6

0468S7

024S8

02S9

0S12

S3

S4

S56

S7

S8

S9S12

0

3.56.51014.516.518.5

S3

036.5111315S4

03.581012

S56

04.56.58.5

S7

024S8

02S9

0机器学习的基本思维—无监督学习-聚类一种聚类方法示例（3）将类别之间的距离<=2的合并，形成S12,S3,S4,S56,S789={1.5，5，8，11.5，18}五个类别。计算类别之间的距离如右上图。（4）将类别之间的距离<=3的合并，形成S12,S34,S56,S789={1.5，6.5，11.5，18}四个类别。见右中图。（5）将类别之间的距离<=5的合并，形成S123456,S789={6.5，18}两个类别，见右下图。S12

S3

S4

S56

S7

S8

S9S12

0

3.56.51014.516.518.5

S3

036.5111315S4

03.581012

S56

04.56.58.5

S7

024S8

02S9

0S12

S3

S4

S56

S789S12

0

3.56.51016.5

S3

036.513S4

03.510

S56

06.5

S789

0S12

S34

S56

S789S12

0

51016.5

S34

0511.5S56

06.5

S789

0S123456

S789S123456

0

11.5S789

0机器学习的基本思维—无监督学习-聚类示例聚类思想回顾确定样本距离的计算方法。确定类间距离的计算方法（初始每个样本为一个类）距离较近的样本先聚成类，距离较远的样本后聚成类。持续迭代。每个样本都能被聚到合适的类中。不同的距离计算方法会产生不同的聚类效果。不同的聚类方法也可能会产生不同的聚类效果。聚类是一种什么方法？你的理解是___________。聚类是一种无监督的机器学习方法聚类就是依据“类内距离最小”和“类间距离最大”的原则，将一组数据集划分成N个类别的方法聚类可以从一个样本是一个类别开始聚集，直到所有样本归于一个或N个类别为止聚类是针对无标签数据集进行分类的方法ABCD提交E聚类方法的关键是类内距离和类间距离的计算方法多选题1分机器学习的基本思维—无监督学习-聚类不同的距离度量常用的距离度量方法有多种衡量有序属性的方法：明氏/闵氏距离----两个空间点的距离欧式距离----两个空间点的距离切比雪夫距离----两个空间点的距离曼哈顿距离----两个空间点的距离余弦距离等----两个向量的距离衡量无序属性的方法VDM(ValueDifferenceMetric)—值差度量编辑距离：海明距离、莱文斯坦距离----两个字符串的距离杰卡德距离----两个集合的距离机器学习的基本思维—无监督学习-聚类n维空间中两点的距离度量：欧式距离与明氏距离dist明氏距离(P,Q)

=dist欧氏距离(P,Q)

=dist曼哈顿距离(P,Q)

=dist切比雪夫距离(P,Q)

=

机器学习的基本思维—无监督学习-聚类两个向量的距离度量：余弦相似度与余弦距离余弦相似度经常被用作解决高维欧氏距离问题。余弦相似度只是两个向量之间夹角的余弦。如果将向量归一化为长度为1，则它也具有相同的向量内积。两个方向完全相同的向量的余弦相似度为1，而两个完全相反的向量的相似度为-1。请注意，大小并不重要，因为这是方向的度量。数学中，向量(矢量)，指具有大小和方向的量。与向量大小对应的量叫做数量(标量)，即数量(或标量)只有大小，没有方向。张量(Tensor)是一个定义在一些向量空间上的多重线性映射，其坐标是n维空间内，有n个分量的一种量。同构意义下，零阶张量为标量(Scalar)，一阶张量为向量(Vector)，二阶张量则为矩阵(Matrix)。机器学习的基本思维—无监督学习-聚类两个字符串的距离度量：编辑距离假设：A、B为两个字符串【编辑距离】指的是将A转换为B的最少操作次数。【汉明距离/海明距离】是一种编辑距离。两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。【莱温斯坦距离】也是一种编辑距离。两个单词的莱文斯坦距离是一个单词变成另一个单词要求的最少单个字符编辑数量。字符编辑只允许：插入一个字符，删除一个字符，替换一个字符。特性：1.至少总是两个字符串大小的差值；2.至多是较长字符串的长度；3.当且仅当两个字符串相等时值为0；4.如果两个字符串大小相等，汉明距离是其上界；5.两个字符串的莱文斯坦距离不大于分别与第三个字符串的莱文斯坦距离之和（三角不等式）。机器学习的基本思维—无监督学习-聚类两个集合的距离度量：杰卡德距离

机器学习的基本思维—无监督学习-聚类两个无序属性的距离度量：VDM对无序属性可采用【VDM距离】

(ValueDifferenceMetric/值差度量)。令mu,a表示在属性u上取值为a的样本数，mu,a,i表示在第i个样本簇中在属性u上取值为a的样本数，k为样本簇数，则属性u上两个离散值a与b之间的VDM距离为：编号城市数量下列的距离，你理解了哪几个___________。欧式距离—衡量两个空间点的距离-用两个空间点的直线距离来度量曼哈顿距离—衡量两个空间点的距离-用两个空间点各坐标差的绝对值之和来度量余弦距离—衡量两个向量的相似程度-用两个向量的方向之夹角来度量编辑距离—衡量两个字符串的相似程度-用一个字符串变成另一个字符串的编辑/替换次数来度量，一次只能替换一个字符。ABCD提交E杰卡德距离—衡量两个集合的相似程度-用集合中交集元素的多少来度量投票最多可选5项机器学习的基本思维—无监督学习-聚类不同的类间距离计算方法

假设：样本Xi,Xj,两个样本之间的距离dij,类Gp,Gq，两个类之间的距离Dpq

前面讲的距离和这里讲的距离是一样的吗？两个样本之间的距离两个类别(样本集合)之间的距离你理解了哪几个类间距度量方法___________。【最短距离法】两类最近样品的距离【最长距离法】两类最远样品的距离【中间距离法】取最短距离与最长距离之中间一点。【重心法/质心法】一类别的重心距另一类别的重心的距离ABCD提交E【类平均法】两类别各取一元素，则两两元素之间距离平方的平均数。投票最多可选5项【k均值(k-means)聚类】算法是一种迭代聚类算法，采用距离作为相似性度量，从而发现给定数据集的K个类，且每个类的中心是根据类中所有值的均值得到。【基本步骤】（1）从样本中选择K个点作为初始质心（完全随机，每个质心代表一个类别）（2）计算每个样本到各个质心的距离。将样本划分到距离最近的质心所对应的类别中（3）计算每个类别内所有样本的均值，并使用该均值更新该类别的质心（4）重复步骤（2）与（3），直到达到以下条件之一结束：

（4.1）质心的位置变化小于指定的阈值（例如0.0001）

（4.2）达到最大迭代次数机器学习的基本思维—无监督学习-聚类最常见聚类算法-k均值聚类算法机器学习的基本思维—无监督学习-聚类典型的聚类算法【1】【划分法】-基于划分的方法。给定有N个元组或者记录的数据集，构造K个分组，每一个分组就代表一个聚类，K<N，K个分组满足下列条件：（1）每一个分组至少包含一个数据记录；（2）每一个数据记录属于且仅属于一个分组。

代表性算法：k-means、k-modes、k-prototypes、k-medoids、CLARA、CLARANS、FocusedCLARAN、PCM等。【层次法】-基于层次的方法。对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。

代表性算法：CURE、ROCK、CHEMALOEN、SBAC、BIRCH、BUBBLE、BUBBLE-FM【密度法】-基于密度的方法。它是基于密度而不是基于各种各样距离的，只要一个区域中的点的密度大过某个阈值，就把它加到与之相近的聚类中去。

代表性算法：DBSCAN、GDBSCAN、OPTICS、FDC、DBLASD这些算法需要读者通过文献自主学习机器学习的基本思维—无监督学习-聚类典型的聚类算法【2】【图论聚类法】-基于图的方法。建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，主要优点是易于处理局部数据。【网格算法】-基于网格的算法。将数据空间划分成有限个单元（cell）的网格结构，以单个单元为对象进行处理。突出优点是处理速度快，通常与目标数据库中记录的个数无关，而只与把数据空间分为多少个单元有关。

代表性算法：STING、WaveCluster、CLIQUE、OPTIGRID【模型法】-基于模型的算法。给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向：统计的方案和神经网络的方案。

代表性算法：COBWeb、AutoClass、CLASSIT、自组织神经网络SOM这些算法需要读者通过文献自主学习第15讲机器学习一、从AlphaGo看人工智能二、机器学习的基本思维—有监督学习-分类三、机器学习的基本思维—无监督学习-聚类四、机器学习的基本思维—其他半监督学习是综合使用大量的未标记数据，以及小部分标记数据来进行学习迁移学习是把为任务A开发的模型重新应用在为任务B开发模型的过程中

强化学习是通过智能体与环境的交互学习策略以实现回报最大化或实现特定目标时序信息，在决定合适的行动时，需要考虑后续步骤延后给出的奖励值（如下棋最终的胜负）机器学习的基本思维—其他其他类型的学习AlphaGo是怎样学习的？机器学习的基本思维—其他再从机器学习看AlphaGo0000000000000000000000000000000001000000000000000000001000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000100000100000000000000000000000000000000000000000000000多个19*19的矩阵表示当前第N-k步到第N步的黑棋棋谱或白棋棋谱N个围棋19*19二值矩阵表示白棋棋谱：0无;1白棋19*19二值矩阵表示黑棋棋谱：0无;1黑棋机器学习的基本思维—其他围棋规则及行棋复杂性围棋形势判断围棋形势的判断所围空间形状拟合—计算所围空间大小---较难将所围空间形状拟合问题转变为图像匹配问题，找到包含该局面的所有对局，然后由已知输赢结果的对局来判断围棋形势围棋待行棋位置的决策（选择下在哪一个交叉点的决策）围棋未来N步可能行棋后的形势判断（用于辅助即将行棋位置的决策，即所谓“走一步前看N步”）蒙特卡罗树搜索算法由已知输赢结果的对局训练算法AlphaGo首先利用了人类职业六段以上选手已知输赢结果的16万局对局来训练机器在不同状态下的最优位置选择能力AlphaGoZero使用两个机器相互对局来训练最优位置选择能力白方胜1盘历史对局白方负n盘历史对局在n盘对局中出现m盘，其中k盘胜，m-k盘负机器学习的基本思维—其他蒙特卡洛树搜索算法思想基于当前状态，选择出评估值最优的节点，准备扩展将前步选择出的节点展开其子树节点对每个子树的叶节点，模拟直到已知胜负，从而算出评估值作为该叶节点的评估值。将该子树叶节点的评估值反向传播，修改其父节点的评估值，直到根节点。【节点示例

】评估值=胜局数/总对局数(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)111xy12341234机器学习的基本思维—其他蒙特卡洛树搜索示例【机器人路径规划问题求解】(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)(1,2)(1,3)over111xy12341234机器学习的基本思维—其他蒙特卡洛树搜索示例【机器人路径规划问题求解】0(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)(1,2)(1,3)over0/111xy12341234机器学习的基本思维—其他蒙特卡洛树搜索示例【机器人路径规划问题求解】0/10/10(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)(1,2)(1,3)over(3,2)(3,3)(2,3)2/201xy12341234机器学习的基本思维—其他蒙特卡洛树搜索示例【机器人路径规划问题求解】0/10/10/102/22/2(4,3)1(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)(1,2)(1,3)over(3,2)(3,3)(2,3)2/21xy12341234机器学习的基本思维—其他蒙特卡洛树搜索示例【机器人路径规划问题求解】0/10/10/102/22/2(4,3)1(4,1)over(4,2)00/10/10/1(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)(1,2)(1,3)over(3,2)(3,3)(2,3)2/21xy12341234机器学习的基本思维—其他蒙特卡洛树搜索示例【机器人路径规划问题求解】0/10/10/102/22/2(4,3)1(4,1)over(4,2)00/10/10/1(2,1)A/B

A成功次数B模拟总次数(1,1)(2,2)(3,1)(1,2)(1,3)over(3,2)(3,3)(2,3)2/21x