信号与系统中的机器学习相关的算法的进展和理解（期末作业）

机器学习是一门多学科交叉专业，涵盖概率论知识，统计学知识，近似理论知识和复杂算法知识，使用计算机作为工具并致力于真实实时的模拟人类学习方式， 并将现有内容进行知识结构划分来有效提高学习效率。

机器学习有下面几种定义：

(1) 机器学习是一门人工智能的科学,该领域的主要研究对象是人工智能，特别是如何在经验学习中改善具体算法的性能。

(2) 机器学习是对能通过经验自动改进的计算机算法的研究。

(3) 机器学习是用数据或以往的经验,以此优化计算机程序的性能标准。  

发展历程：机器学习实际上已经存在了几十年或者也可以认为存在了几个世纪。追溯到17世纪，贝叶斯、拉普拉斯关于最小二乘法的推导和马尔可夫链，这些构成了机器学 习广泛使用的工具和基础。1950年(艾伦.图灵提议建立一个学习机器)到2000年初 (有深度学习的实际应用以及最近的进展，比如2012年的AlexNet)，机器学习有了很大的进展。

从20世纪50年代研究机器学习以来，不同时期的研究途径和目标并不相同，可以划分为四个阶段。

第一阶段是20世纪50年代中叶到60年代中叶，这个时期主要研究“有无知识的学习”。这类方法主要是研究系统的执行能力。这个时期，主要通过对机器的环境及其相应性能参数的改变来检测系统所反馈的数据，就好比给系统一个程序，通过改变它们的自由空间作用，系统将会受到程序的影响而改变自身的组织，最后这个系统将会选择一个最优的环境生存。在这个时期最具有代表性的研究就是Samuet的下棋程序。但这种机器学习的方法还远远不能满足人类的需要。

第二阶段从20世纪60年代中叶到70年代中叶，这个时期主要研究将各个领域的知识植入到系统里，在本阶段的目的是通过机器模拟人类学习的过程。同时还采用了图结构及其逻辑结构方面的知识进行系统描述，在这一研究阶段，主要是用各种符号来表示机器语言，研究人员在进行实验时意识到学习是一个长期的过程，从这种系统环境中无法学到更加深入的知识，因此研究人员将各专家学者的知识加入到系统里，经过实践证明这种方法取得了一定的成效。在这一阶段具有代表性的工作有Hayes-Roth和Winson的对结构学习系统方法。  

第三阶段从20世纪70年代中叶到80年代中叶，称为复兴时期。在此期间，人们从学习单个概念扩展到学习多个概念，探索不同的学习策略和学习方法，且在本阶段已开始把学习系统与各种应用结合起来，并取得很大的成功。同时，专家系统在知识获取方面的需求也极大地刺激了机器学习的研究和发展。在出现第一个专家学习系统之后，示例归纳学习系统成为研究的主流，自动知识获取成为机器学习应用的研究目标。1980 年，在美国的卡内基梅隆(CMU)召开了第一届机器学习国际研讨会，标志着机器学习研究已在全世界兴起。此后，机器学习开始得到了大量的应用。1984 年，Simon等20多位人工智能专家共同撰文编写的Machine Learning文集第二卷出版，国际性杂志Machine Learning创刊，更加显示出机器学习突飞猛进的发展趋势。这一阶段代表性的工作有Mostow的指导式学习、Lenat的数学概念发现程序、Langley的BACON程序及其改进程序。  

第四阶段20世纪80年代中叶,是机器学习的最新阶段。这个时期的机器学习具有如下特点：

(1) 机器学习已成为新的学科，它综合应用了心理学、生物学、神经生理学、数学、自动化和计算机科学等形成了机器学习理论基础。

(2) 融合了各种学习方法，且形式多样的集成学习系统研究正在兴起。

(3) 机器学习与人工智能各种基础问题的统一性观点正在形成。

(4) 各种学习方法的应用范围不断扩大，部分应用研究成果已转化为产品。

(5) 与机器学习有关的学术活动空前活跃。

机器学习是人工智能及模式识别领域的共同研究热点，其理论和方法已被广泛应用于解决工程应用和科学领域的复杂问题。2010 年的图灵奖获得者为哈佛大学的Leslie vlliant 教授，其获奖工作之一是建立了概率近似正确(Probably Approximate Correct，PAC)学习理论；2011年的图灵奖获得者为加州大学洛杉矶分校的Judea Pearll教授，其主要贡献为建立了以概率统计为理论基础的人工智能方法。这些研究成果都促进了机器学习的发展和繁荣。

机器学习是研究怎样使用计算机模拟或实现人类学习活动的科学，是人工智能中最具智能特征，最前沿的研究领域之一。自 20世纪80年代以来，机器学习作为实现人工智能的途径，在人工智能界引起了广泛的兴趣，特别是近十几年来，机器学习领域的研究工作发展很快，它已成为人工智能的重要课题之一。机器学习不仅在基于知识的系统中得到应用，而且在自然语言理解、非单调推理、机器视觉、模式识别等许多领域也得到了广泛应用。一个系统是否具有学习能力已成为是否具有“智能”的一个标志。机器学习的研究主要分为两类研究方向：第一类是传统机器学习的研究，该类研究主要是研究学习机制，注重探索模拟人的学习机制；第二类是大数据环境下机器学习的研究，该类研究主要是研究如何有效利用信息，注重从巨量数据中获取隐藏的、有效的、可理解的知识。

机器学习历经70年的曲折发展 ，以深度学习为代表借鉴人脑的多分层结构、神经元的连接交互信息的逐层分析处理机制，自适应、自学习的强大并行信息处理能力，在很多方面收获了突破性进展，其中最有代表性的是图像识别领域。

传统机器学习的研究方向主要包括决策树、随机森林、人工神经网络、贝叶斯学习等方面的研究。

决策树是机器学习常见的一种方法。20 世纪末期，机器学习研究者J. Ross Quinlan将Shannon的信息论引入到了决策树算法中，提出了ID3算法。1984年I.Kononenko、E. Roskar和I. Bratko在ID3算法的基础上提出了AS-SISTANT Algorithm，这种算法允许类别的取值之间有交集。同年，A. Hart提出了Chi- Squa统计算法，该算法采用了一种基于属性与类别关联程度的统计量。1984年L. Breiman、C.Ttone、R.Olshen和J.Freidman提出了决策树剪枝概念，极大地改善了决策树的性能。1993年，Quinlan在ID3算法的基础上提出了一种改进算法，即C4.5算法。C4.5 算法克服了ID3算法属性偏向的问题增加了对连续属性的处理通过剪枝，在一定程度上避免了“过度适合”现象。但是该算法将连续属性离散化时，需要遍历该属性的所有值，降低了效率，并且要求训练样本集驻留在内存，不适合处理大规模数据集。2010年Xie提出一种CART算法，该算法是描述给定预测向量X条件分布变量Y的一个灵活方法，已经在许多领域得到了应用。CART算法可以处理无序的数据，采用基尼系数作为测试属性的选择标准。CART算法生成的决策树精确度较高，但是当其生成的决策树复杂度超过一定程度后，随着复杂度的提高，分类精确度会降低，所以该算法建立的决策树不宜太复杂。2007年房祥飞表述了一种叫SLIQ(决策树分类)算法，这种算法的分类精度与其他决策树算法不相上下，但其执行的速度比其他决策树算法快，它对训练样本集的样本数量以及属性的数量没有限制。SLIQ算法能够处理大规模的训练样本集，具有较好的伸缩性；执行速度快而且能生成较小的二叉决策树。SLIQ算法允许多个处理器同时处理属性表，从而实现了并行性。但是SLIQ算法依然不能摆脱主存容量的限制。2000年RajeevRaSto等提出了PUBLIC算法，该算法是对尚未完全生成的决策树进行剪枝，因而提高了效率。近几年模糊决策树也得到了蓬勃发展。研究者考虑到属性间的相关性提出了分层回归算法、约束分层归纳算法和功能树算法，这三种算法都是基于多分类器组合的决策树算法，它们对属性间可能存在的相关性进行了部分实验和研究，但是这些研究并没有从总体上阐述属性间的相关性是如何影响决策树性能。此外，还有很多其他的算法，如Zhang.J于2014年提出的一种基于粗糙集的优化算法、Wang.R在2015年提出的基于极端学习树的算法模型等。

随机森林(RF)作为机器学习重要算法之一，是一种利用多个树分类器进行分类和预测的方法。近年来，随机森林算法研究的发展十分迅速，已经在生物信息学、生态学、医学、遗传学、遥感地理学等多领域开展的应用性研究。 [2]

人工神经网络(Artificial Neural Networks，ANN)是一种具有非线性适应性信息处理能力的算法，可克服传统人工智能方法对于直觉，如模式、语音识别、非结构化信息处理方面的缺陷。早在20世纪40年代人工神经网络已经受到关注，并随后得到迅速发展。

贝叶斯学习是机器学习较早的研究方向，其方法最早起源于英国数学家托马斯，贝叶斯在1763年所证明的一个关于贝叶斯定理的一个特例。经过多位统计学家的共同努力，贝叶斯统计在20世纪50年代之后逐步建立起来，成为统计学中一个重要的组成部分。

大数据的价值体现主要集中在数据的转向以及数据的信息处理能力等等。在产业发展的今天，大数据时代的到来，对数据的转换，数据的处理数据的存储等带来了更好的技术支持，产业升级和新产业诞生形成了一种推动力量，让大数据能够针对可发现事物的程序进行自动规划，实现人类用户以计算机信息之间的协调。 另外现有的许多机器学习方法是建立在内存理论基础上的。大数据还无法装载进计算机内存的情况下，是无法进行诸多算法的处理的，因此应提出新的机器学习算法，以适应大数据处理的需要。大数据环境下的机器学习算法，依据一定的性能标准，对学习结果的重要程度可以予以忽视。 采用分布式和并行计算的方式进行分治策略的实施，可以规避掉噪音数据和冗余带来的干扰，降低存储耗费，同时提高学习算法的运行效率。

随着大数据时代各行业对数据分析需求的持续增加，通过机器学习高效地获取知识，已逐渐成为当今机器学习技术发展的主要推动力。大数据时代的机器学习更强调“学习本身是手段"机器学习成为一 种支持和服务技术。如何基于机器学习对复杂多样的数据进行深层次的分析，更高效地利用信息成为当前大数据环境下机器学习研究的主要方向。所以，机器学习越来越朝着智能数据分析的方向发展，并已成为智能数据分析技术的一个重要源泉。另外，在大数据时代，随着数据产生速度的持续加快，数据的体量有了前所未有的增长，而需要分析的新的数据种类也在不断涌现，如文本的理解、文本情感的分析、图像的检索和理解、图形和网络数据的分析等。使得大数据机器学习和数据挖掘等智能计算技术在大数据智能化分析处理应用中具有极其重要的作用。在2014年12月中国计算机学会(CCF)大数据专家委员会上通过数百位大数据相关领域学者和技术专家投票推选出的“2015年大数据十大热点技术与发展趋势”中，结合机器学习等智能计算技术的大数据分析技术被推选为大数据领域第一大研究热点和发展趋势。

机器学习的分类

几十年来，研究发表的机器学习的方法种类很多，根据强调侧面的不同可以有多种分类方法。

基于学习策略的分类

(1) 模拟人脑的机器学习

符号学习：模拟人脑的宏现心理级学习过程，以认知心理学原理为基础，以符号数据为输入，以符号运算为方法，用推理过程在图或状态空间中搜索，学习的目标为概念或规则等。符号学习的典型方法有记忆学习、示例学习、演绎学习.类比学习、解释学习等。

神经网络学习(或连接学习)：模拟人脑的微观生理级学习过程，以脑和神经科学原理为基础，以人工神经网络为函数结构模型，以数值数据为输人，以数值运算为方法，用迭代过程在系数向量空间中搜索，学习的目标为函数。典型的连接学习有权值修正学习、拓扑结构学习。

(2) 直接采用数学方法的机器学习

主要有统计机器学习。

统计机器学习是基于对数据的初步认识以及学习目的的分析，选择合适的数学模型，拟定超参数，并输入样本数据，依据一定的策略，运用合适的学习算法对模型进行训练，最后运用训练好的模型对数据进行分析预测。

统计机器学习三个要素：

模型(model)：模型在未进行训练前，其可能的参数是多个甚至无穷的，故可能的模型也是多个甚至无穷的，这些模型构成的集合就是假设空间。

策略(strategy)：即从假设空间中挑选出参数最优的模型的准则。模型的分类或预测结果与实际情况的误差(损失函数)越小，模型就越好。那么策略就是误差最小。

算法(algorithm)：即从假设空间中挑选模型的方法(等同于求解最佳的模型参数)。机器学习的参数求解通常都会转化为最优化问题，故学习算法通常是最优化算法，例如最速梯度下降法、牛顿法以及拟牛顿法等。

基于学习方法的分类

(1) 归纳学习

符号归纳学习：典型的符号归纳学习有示例学习、决策树学习。

函数归纳学习(发现学习)：典型的函数归纳学习有神经网络学习、示例学习、发现学习、统计学习。

(2) 演绎学习

(3) 类比学习：典型的类比学习有案例(范例)学习。

(4) 分析学习：典型的分析学习有解释学习、宏操作学习。

基于学习方式的分类

(1) 监督学习(有导师学习)：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函数模型，采用迭代计算方法，学习结果为函数。

(2) 无监督学习(无导师学习)：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。

(3) 强化学习(增强学习)：以环境反惯(奖/惩信号)作为输入，以统计和动态规划技术为指导的一种学习方法。

基于数据形式的分类

(1) 结构化学习：以结构化数据为输人，以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习、规则学习。

(2) 非结构化学习：以非结构化数据为输人，典型的非结构化学习有类比学习案例学习、解释学习、文本挖掘、图像挖掘、Web挖掘等。

基于学习目标的分类

(1) 概念学习：学习的目标和结果为概念，或者说是为了获得概念的学习。典型的概念学习主要有示例学习。

(2) 规则学习：学习的目标和结果为规则，或者为了获得规则的学习。典型规则学习主要有决策树学习。

(3) 函数学习：学习的目标和结果为函数，或者说是为了获得函数的学习。典型函数学习主要有神经网络学习。

(4) 类别学习：学习的目标和结果为对象类，或者说是为了获得类别的学习。典型类别学习主要有聚类分析。

(5) 贝叶斯网络学习：学习的目标和结果是贝叶斯网络，或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学习和多数学习。

梯度下降：

梯度下降（gradient descent）在机器学习中应用十分的广泛，不论是在线性回归还是Logistic回归中，它的主要目的是通过迭代找到目标函数的最小值，或者收敛到最小值。

梯度下降法的基本思想可以类比为一个下山的过程。

假设这样一个场景：一个人被困在山上，需要从山上下来(找到山的最低点，也就是山谷)。但此时山上的浓雾很大，导致可视度很低；因此，下山的路径就无法确定，必须利用自己周围的信息一步一步地找到下山的路。这个时候，便可利用梯度下降算法来帮助自己下山。怎么做呢，首先以他当前的所处的位置为基准，寻找这个位置最陡峭的地方，然后朝着下降方向走一步，然后又继续以当前位置为基准，再找最陡峭的地方，再走直到最后到达最低处；同理上山也是如此，只是这时候就变成梯度上升算法了。梯度下降的基本过程就和下山的场景很类似。

首先，我们有一个可微分的函数。这个函数就代表着一座山。我们的目标就是找到这个函数的最小值，也就是山底。根据之前的场景假设，最快的下山的方式就是找到当前位置最陡峭的方向，然后沿着此方向向下走，对应到函数中，就是找到给定点的梯度 ，然后朝着梯度相反的方向，就能让函数值下降的最快！因为梯度的方向就是函数之变化最快的方向(在后面会详细解释)

所以，我们重复利用这个方法，反复求取梯度，最后就能到达局部的最小值，这就类似于我们下山的过程。而求取梯度就确定了最陡峭的方向，也就是场景中测量方向的手段。

代码：

#!/usr/bin/env python3

# -*- coding: utf-8 -*-

# @Time    : 2019/1/21 21:06

# @Author  : Arrow and Bullet

# @FileName: gradient_descent.py

# @Software: PyCharm

# @Blog    ：https://blog.csdn.net/qq_41800366

from numpy import *

# 数据集大小 即20个数据点

m = 20

# x的坐标以及对应的矩阵

X0 = ones((m, 1))  # 生成一个m行1列的向量，也就是x0，全是1

X1 = arange(1, m+1).reshape(m, 1)  # 生成一个m行1列的向量，也就是x1，从1到m

X = hstack((X0, X1))  # 按照列堆叠形成数组，其实就是样本数据

# 对应的y坐标

Y = array([

    3, 4, 5, 5, 2, 4, 7, 8, 11, 8, 12,

    11, 13, 13, 16, 17, 18, 17, 19, 21

]).reshape(m, 1)

# 学习率

alpha = 0.01

# 定义代价函数

def cost_function(theta, X, Y):

    diff = dot(X, theta) - Y  # dot() 数组需要像矩阵那样相乘，就需要用到dot()

    return (1/(2*m)) * dot(diff.transpose(), diff)

# 定义代价函数对应的梯度函数

def gradient_function(theta, X, Y):

    diff = dot(X, theta) - Y

    return (1/m) * dot(X.transpose(), diff)

# 梯度下降迭代

def gradient_descent(X, Y, alpha):

    theta = array([1, 1]).reshape(2, 1)

    gradient = gradient_function(theta, X, Y)

    while not all(abs(gradient)