《从零开始学习自然语言处理(NLP)》-基础准备(0)

发表于 2019-01-12

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/54731715

写在最前面

在这个日新月异的信息时代，海量数据的积累，计算能力的不断提升，机器学习尤其是深度学习的蓬勃发展，使得人工智能技术在不同领域焕发出蓬勃的活力。自己经历了嵌入式开发，移动互联网开发，目前从事自然语言处理算法开发工作。从工程软件开发到自然语言处理算法开发，希望通过这个系列的文章，能够由浅入深，通俗易懂的介绍自然语言处理的领域知识，分享自己的成长，同大家一起进步。

信心与兴趣

很多同学提到算法可能就会打退堂鼓，尤其是一直从事纯工程的软件开发。工作中连经典的数据结构都很少使用，更不用提五花八门的机器学习和深度学习算法。尤其各个大厂的算法专家、数据科学家都是背景爆表，动不动就是国外名校的Phd，至少也是国内清北、C9。实际上，针对普通的算法开发岗，从学习梯度上来讲，算法和工程的差异并不大。当然也并不需要非要名校硕博。
以前经常和同事开玩笑说，好歹大家都是985的本硕，但手上这工作，找个高中生也能妥妥搞定啊。虽然是玩笑，线上的产品当然也不是像Demo那么简单，但真实的工作真的没有那么明显的条条框框限制。自己也是面试官，百度这样的大厂对普通的开发要求也只是大专。针对普通的算法开发，自己觉得本科基本足够了，当然更没有像211/985这样的限制。
一般来讲，从事某个领域的工作，从底层基础到业务实现一般包括如下的几个层次（以互联网移动开发和算法开发为例）：

方向	通用基础	专业基础	领域基础	业务方向
移动开发	操作系统、计算机网络、编译原理、数据结构、编程语言、设计模式	Android开发、iOS开发	驱动开发、Framework开发、应用开发	电商、社交、智能硬件
算法开发	编程语言(python)、数学基础(线性代数、概率/统计、微积分)	机器学习，深度学习	语音、自然语言理解、计算机视觉、推荐、计算广告、风控	搜索，智能客服，广告推荐，互联网金融

从技能栈的对比来看，算法开发对数学要求要高些，这又会让很多同学看着头痛。实际上对数学的恐惧主要原因在于，对大多数人来说，数学主要是用来应付作业和考试的，而很少在真实的工程场景中使用它。
自己的本科专业是电子信息方向（觉得空闲时间多，顺手拿了个计算机科学与技术的双学士），有一些专业课程也蛮让人头痛的，比如《通信原理》、《信号与系统》、《数字信号处理》、《微机原理》、《数字电路》等，五花八门的抽象概念和算法公式。当时参加全国大学生电子设计竞赛，选入的学校的电子设计校队，参加系统的学习和培训（有半年的时间参加集中培训，不用像其他同学一样日常上课）：
当大家还在纠结《通信系统》里的调制解调原理时，我们已经在做单边带调制收音机了；
当大家还在纠结《信号与系统》的傅里叶变换时，我们已经在做基于快速傅里叶变换的频谱仪了；
当大家还在纠结《数字信号处理》里的滤波器时，我们已经在做50Hz及其谐波过滤的工频陷波器了；
当大家还在纠结《微机原理》的X86汇编指令时，我们已经用上工业级的Msp430和C8051F系列控制器了；
当大家还在纠结《数字电路》的逻辑控制和抱怨VHDL难学时，我们已经在用Verilog玩Altera的FPGA了。
本来是非常枯燥有难以对付的专业课，但有了实际的使用场景和工程实践，反而变得非常有趣，不但专业课的教材就在手边经常翻阅，还会专门找相应的Paper，看看有没有更好更新的方案。自己对这些专业课不但没有反感，反而觉得超级有用，知识就是力量，在这一刻特别贴切。
我们回过头来说数学，也是同样的体验。算法的开发工作为数学和算法提供了实践的土壤，理论有了实践这块沃土，也就不再那么枯燥和晦涩。像很多数学大神一样徒手推公式确实是件很难的事情，但基于基础的数学知识来解决工程问题，这并没有想象中的那么难。而且，学习本来就是一个往复的过程，先有一个大概，尝试用已有的知识解决问题，当问题解决不掉时，再反过来学习自己欠缺的知识。
说了信心再说兴趣，很多同学会觉得目前机器学习和深度学习大火，是不是就该放弃手上的工程岗位，全力以赴的加入到算法的大军中。自己觉得要不加入这个方向还是看个人兴趣吧，现在算法岗位炙手可热，但三五年之后就不好说了。典型的就是Android/iOS移动开发，10年左右如日中天，市场蓝海，人才紧俏，公司抢人的盛况应该跟现在差不多。收益的决定因素是市场，但个人的成长从长期来看，还要看自己的兴趣。依照T型能力理论来说，深度方面，前端、后台、架构、嵌入式、客户端都OK；广度方面，机器学习和深度学习不论从是否要从事相关的领域开发，花些时间了解和学习一下，总的来说也还是不错的。
好了，下面我们就具体看看从事自然语言处理需要准备的基础知识吧。

编程语言

编程语言的要求是很低的，弄掌握Python就基本OK。我的自己经验是：

1 在网上找一篇Python入门的帖子，搭建环境，运行简单的例子（半天）
2 找一本基础书籍，系统的熟悉下语言的基本特性和完整框架（1~2天）
ps：我之前有C/C++和Java的语音基础
3 开始正常使用Python进行开发，遇到问题，求助搜索引擎（2个月以上）
4 觉得自己对语言就基本的掌握后，可以根据选择进行进阶学习了

系统的基础学习可以参考：《Python基础教程》
晋级学习可以参考：《流畅的Python》

经典数据结构与算法

经典的数据结构和算法，主要指数组、链表、队列、堆栈、树、图这样的经典数据结构，以及各种排序/查找、深度搜索、广度搜索、最小路径、Hash等算法。对一般的算法开发，这部分不是必须项。如果时间有限，可以跳过这部分。但从长远来看，无论是普通的工程开发还是算法开发，经典的数据结构和算法还是必要了。
落实到具体的学习上，基础的《数据结构与算法》应该随便一本教科书都OK。在实际操作方面，可以抽空刷一刷LeetCode，书的话可以考虑《进军硅谷，程序员面试解密》，内容基本都是LeetCode的原题，可以先刷题再看书。如果LeetCode上能持续刷上200+的题目，以后面对经典的数据结构和算法问题，应该也就没有恐惧的感觉了，反而遇到新问题还会饶有兴趣的去研究研究解决方案。

数学基础

对于算法开发，本科学习的《微积分》、《线性代数》、《概率/统计》基本上就够用了。有些同学会提到《概率图模型》和《凸优化》等。我觉得对于入门来说，前面的三门课基本够用，后面如果真的觉得需要深入，再看后面的内容也不迟。
如果觉得当时大学的课程成绩还不错，那最快的方法就是把大学的教材拿出来重新再扫一般即可。如果觉得时间充裕，想再系统的学习一遍，在线视频是个不错的选择，
MIT：《单变量微积分》
MIT：《线性代数》
可汗学院：《概率》
可汗学院：《统计学》
学习的过程不要太苛求全面理解，没必要像数学大牛一样能把所有的公式都手动的推导一遍。能理解基本的概念和原理，关键是有系统的知识框架，后面遇到细节问题，可以回过头来再看。

机器学习

这部分目前资料应该是铺天盖地的多，当然还有各式各样的培训班。自己觉得从入门角度，只要把吴恩达在Coursera上的机器学习课程完整的学习完，并完成作业拿到证书，机器学习这部分就算及格了。
Coursera：《MachineLearning》
一定要完成作业！一定要完成作业！一定要完成作业！重要的事情说三遍。
Coursera不翻墙速度好像有些慢，网易云课堂也有视频，但不能提交作业作业。
至于书的话，可以看看周志华老师的“西瓜书”：《机器学习》

深度学习

看完前面机器学习的内容你会发现两个事情：

机器学习的各种算法好像都是些非常经典的算法，基本都是2000年之前提出的
现在大家都在搞深度学习了，这些老掉牙的算法越来越没人用了

真实情况也大抵如此，如果直接跳过机器学习直接学习深度学习可以吗？当然可以啊，而且，直接学习深度学习还会觉得深度学习的入门门槛更低。
这估计会让很多同学觉得反常识。但反过来你问问自己，如果没有学习过汇编，上来就用C语言搞嵌入式应用开发可以吗？没有学习过C++，上来就用Java搞Android开发可以吗？当然可以啊。从入门角度没问题，但从长期来看还是需要的，想深入一个领域，知识的完备是必要的。比如嵌入开发用汇编写过两级中断向量表，做Android开发也开发过JNI。
深度学习也是一样，从最快入门的角度来看，可以跳过机器学习，直接进入深度学习，但从长期看机器学习还是必要的。而且，看完了吴恩达的《机器学习》课程，再看他的深度学习也更流畅。
Coursera：《DeepLearning》
一定要完成作业！一定要完成作业！一定要完成作业！重要的事情说三遍。
补充下，吴恩达在Coursera上的课程，《MachineLearning》是免费观看的，在线作业是付费的。《DeepLearning》无论是视频还是在线作业都是付费的。网易云课堂有免费的视频课程，但不能提交在线作业。其实，Coursera上的课程也挺便宜的，做完作业还有证书，还是挺不错的。
至于书的话，可以看看“花书”《深度学习》

自然语言处理

好了终于到了这篇文章的核心部分了，因为是专业基础，所有市面上的系统学习资料也就没前面那么多了。但仔细找找的话也不少（都需要翻墙，手动捂脸）：
经典自然语言处理（斯坦福）：《Natural Language Processing course by Dan Jurafsky and Christopher Manning》
经典+深度学习（National Research University Higher School of Economics）：《Natural Language Processing》
深度学习自然语言处理（斯坦福）：《Natural language processing with DeepLearning》
深度学习自然语言处理（CMU）：《CMU Neural Nets for NLP》
除了第一个之外，后面的视频都比较新。相对来说，书的资料就相对滞后了，如果有兴趣可以翻翻经典的宗成庆的《统计自然语言处理》，主要是针对经典的自然语言处理方法，虽然方法是经典的，但领域问题的描述还是很全面的。

小节

总的来说，算法开发和普通的工程开发，从学习梯度上来讲差别不大，也不需要高大上的背景和学历。确定兴趣，看好方向，就坚持一步一步积累，理论结合实践，相信很快你也能像我一样，跨过算法开发的门槛，体会用算法解决实际工程问题的乐趣。

TensorFlow Servering C/S通信约束

发表于 2018-09-21

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/45109527

TensorFlow Serving以Server方式提供模型能力服务，作为服务的使用者（Client）可以通过gRPC和RESTfull API两种方式来获取模型能力。虽然TensorFlow对C/S的通信约束做了说明，但感觉介绍的并不是特别的清晰易用，需要自己根据使用示例，并结合文档进行梳理和总结。

官方参考示例

在文档中提到了两个参考示例，一个用于gRPC通信约束测试，一个用于RESTfull API通信约束测试。

1. gRPC示例

示例使用说明：https://www.tensorflow.org/serving/serving_basic

模型输出

minist_save_model.py
示例代码：https://github.com/tensorflow/serving/blob/master/tensorflow_serving/example/mnist_saved_model.py

客户端验证

mnist_client.py
示例代码：https://github.com/tensorflow/serving/blob/master/tensorflow_serving/example/mnist_client.py

2. RESTfull API示例

示例使用说明:https://www.tensorflow.org/serving/api_rest

模型输出

export_half_plus_two.py
示例代码：
https://github.com/tensorflow/serving/blob/master/tensorflow_serving/servables/tensorflow/testdata/export_half_plus_two.py

客户端验证

Http请求，通过curl命令完成

示例代码分析

虽然官网提供了两个示例，但实际上RESTfull API的示例过于简单，并且做了封装，实际的参考价值不大。下面主要结合gRPC的示例代码进行分析。

客户端同服务端进行通信交互的核心是几个标识，我们分别介绍下。

1. 模型标识

指定要使用哪一个模型。
参考mnist_client.py

模型标识在Serving的模型保存输出代码中并没有显示的声明。模型标识实际上是在指定模型输出路径，和设置TF Serving “target”时指定的。

参考:https://www.tensorflow.org/serving/serving_basic

2. 签名标识

可以粗糙的理解为，用来指定需要调用模型中的哪个方法。
官网定义（参考：https://www.tensorflow.org/serving/signature_defs）

参考mnist_client.py

签名标识在Serving的模型保存输出代码中设置，
参考minist_save_model.py

3. 输入标识

设置输入，传入待处理的数据。
官网定义（参考：https://www.tensorflow.org/serving/signature_defs）

参考minist_save_model.py

参考mnist_client.py

4. 输出标识

设置哪些数据作为返回值，只在Serving中进行设置，Client获取的返回值中，能够获取对应的标识。
官网定义（参考：https://www.tensorflow.org/serving/signature_defs）

参考minist_save_model.py

参考mnist_client.py

总结

客户端向服务端发起请求时，指定了模型标识、签名标识、输入标识（包含数据），便可以从服务端获取处理结果，结果中包含输出标识。
gRPC和RESTfull API在通信约束上是一致的。

TensorFlow Serving入门

发表于 2018-09-21

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/45109194

大家习惯使用TensorFlow进行模型的训练、验证和预测，但模型完善之后的生产上线流程，就变得五花八门了。针对这种情况Google提供了TensorFlow Servering，可以将训练好的模型直接上线并提供服务。在2017年的TensorFlow开发者Summit上便提出了TensorFlow Serving。
传送门：https://www.youtube.com/watch?v=q_IkJcPyNl0&list=PLOU2XLYxmsIKGc_NBoIhTn2Qhraji53cv&index=13
但那时候客户端和服务端的通信只支持gRPC。在实际的生产环境中比较广泛使用的C/S通信手段是基于RESTfull API的，幸运的是从TF1.8以后，TF Serving也正式支持RESTfull API通信方式了。

服务框架

基于TF Serving的持续集成框架还是挺简明的，基本分三个步骤：

模型训练
这是大家最熟悉的部分，主要包括数据的收集和清洗、模型的训练、评测和优化；
模型上线
前一个步骤训练好的模型在TF Server中上线；
服务使用

客户端通过gRPC和RESTfull API两种方式同TF Servering端进行通信，并获取服务；

TF Serving工作流程

TF Serving的工作流程主要分为以下几个步骤：

Source会针对需要进行加载的模型创建一个Loader，Loader中会包含要加载模型的全部信息；
Source通知Manager有新的模型需要进行加载；
Manager通过版本管理策略（Version Policy）来确定哪些模型需要被下架，哪些模型需要被加载；
Manger在确认需要加载的模型符合加载策略，便通知Loader来加载最新的模型；
客户端像服务端请求模型结果时，可以指定模型的版本，也可以使用最新模型的结果；

简单示例

TF Serving客户端和服务端的通信方式有两种（gRPC和RESTfull API）

示例（一）：RESTfull API形式

1. 准备TF Serving的Docker环境

目前TF Serving有Docker、APT（二级制安装）和源码编译三种方式，但考虑实际的生产环境项目部署和简单性，推荐使用Docker方式。

# docker pull tensorflow/serving

2. 下载官方示例代码

示例代码中包含已训练好的模型和与服务端进行通信的客户端（RESTfull API形式不需要专门的客户端）

# mkdir -p /tmp/tfserving
# cd /tmp/tfserving
# git clone https://github.com/tensorflow/serving

3. 运行TF Serving

# docker run -p 8501:8501 \
  --mount type=bind,\
   source=/tmp/tfserving/serving/tensorflow_serving/servables/tensorflow/testdata/saved_model_half_plus_two_cpu,\
target=/models/half_plus_two \
-e MODEL_NAME=half_plus_two -t tensorflow/serving &

这里需要注意的是，较早的docker版本没有“–mount”选项，比如Ubuntu16.04默认安装的docker就没有（我的环境是Ubuntu 18.04）。

4.客户端验证

# curl -d '{"instances": [1.0, 2.0, 5.0]}' \
  -X POST http://localhost:8501/v1/models/half_plus_two:predict

返回结果，

# { "predictions": [2.5, 3.0, 4.5] }

示例（二）：gRPC形式

1. 准备TF Serving的Docker环境

目前TF Serving有Docker、APT（二级制安装）和源码编译三种方式，但考虑实际的生产环境项目部署和简单性，推荐使用Docker方式。

#  docker pull tensorflow/serving

2. 下载官方示例代码

# mkdir -p /tmp/tfserving
# cd /tmp/tfserving
# git clone https://github.com/tensorflow/serving

3. 模型编译

# python tensorflow_serving/example/mnist_saved_model.py models/mnist

4. 运行TF Serving

# docker run -p 8500:8500 \
--mount type=bind,source=$(pwd)/models/mnist,target=/models/mnist \
-e MODEL_NAME=mnist -t tensorflow/serving

这里需要注意的是，较早的docker版本没有“–mount”选项，比如Ubuntu16.04默认安装的docker就没有（我的环境是Ubuntu 18.04）。

4.客户端验证

# python tensorflow_serving/example/mnist_client.py --num_tests=1000 --server=127.0.0.1:8500

返回结果，

#  Inference error rate: 11.13%

这里需要注意的是，直接运行mnist_client.py会出现找不到“tensorflow_serving”的问题，需要手动安装，

# pip install tensorflow-serving-api

资料参考

TF Serving官方文档：https://www.tensorflow.org/serving/

《机器学习》笔记-强化学习（16）

发表于 2018-09-21

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/38402296

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

任务与奖赏
K-摇臂赌博机
有模型学习
免模型学习
值函数近似
模仿学习
（一）任务与奖赏
以种西瓜为例。种瓜有许多步骤，从一开始的选种，到定期浇水、施肥、除草、杀虫，经过一段时间才能收获西瓜。通常要等到收获后，我们才知道种出的瓜好不好。若将得到好瓜作为辛勤种瓜劳动奖赏，则在种瓜过程中，当我们执行某个操作（例如，施肥）时，并不能立即获得这个最终奖励，甚至难以判断当前操作对最终奖赏的影响，仅能得到一个当前反馈（例如，瓜苗看起来更健壮了）。我们需多次种瓜，在种瓜过程中不断摸索，然后才能总结出比较好的种瓜策略。这个过程抽象出来，就是“强化学习”（Reinforcement Learning）。
下图给出了强化学习的一个简单图示，

强化学习任务通常用马尔科夫决策过程（Markov Decision Process，简称MDP）来描述：
机器处于环境E中；
状态空间为X，其中，每个状态x∈X是机器感知环境的描述，如在种瓜任务上，这就是当前瓜苗长势的描述；
机器能采取的动作构成动作空间A，如种瓜过程中有浇水、施不同的肥、使用不同农药等多种可供选择的动作；
若某个动作a∈A作用在当前状态x上，则潜在的转移函数P将使得环境从当前状态按某种概率转移到另一个状态，如瓜苗状态为缺水，若选择动作为浇水，则瓜苗长势会发生变化，瓜苗有一定概率恢复健康，也有一定概率无法恢复；
在转移到另一个状态的同时，环境会根据潜在的“奖赏”（reward）函数R反馈给机器一个奖赏。
综合起来，强化学习任务对应了四元组E=。下图给出了一个简单的例子，

需要注意“机器”与“环境”的界限，例如，在种西瓜任务中，环境是西瓜生长的自然世界；在下棋对弈中，环境是棋盘与对手；在机器人控制中，环境是机器人的躯体与物理世界。总之，在环境中的状态的转移、奖赏的返回是不受机器控制的，机器只能通过选择要执行的动作来影响环境，也只能通过观察转移后的状态和返回的奖赏来感知环境。
机器要做的是通过在环境中不断的尝试而学得一个“策略”（policy）π，根据这个策略，在状态x下就能得知要执行的动作a=π(x)，例如看到瓜苗状态是缺水时，能返回动作“浇水”。
策略有两种表示方法：
一种是将策略表示为函数π：X->A，确定性策略常用这种表示；
另一种是概率表示π：XxA->R，随机性策略常用这种表示，π(x, a)为状态x下选择动作a的概率，这里必须有∑π（x，a）=1；

策略的优劣取决于长期执行这一策略后得到的累积奖赏，例如某个策略使得瓜苗枯死，它的累积奖赏会很小，另一个策略种出了好瓜，他的累积奖赏会很大。在强化学习任务中，学习的目标是要找到能使长期累积奖赏最大化的策略。
大家也许已经感觉到强化学习与监督学习的差别。若将这里的“状态”对应为监督学习中的“示例”、“动作”对应“标记”，则可看出，强化学习中的“策略”实际上就相当于监督学习中的“分类器”（当动作是离散的）或“回归器”（当动作是连续的），模型的形式并无差别。但不同的是，在强化学习中并没有监督学习中的有标记样本（即“示例-标记”对），换言之，没有人直接告诉机器在什么状态下该做什么动作，只有等到最终结果揭晓，才能通过“反思”之前的动作是否正确来进行学习。因此，强化学习在某种意义上可看做具有“延迟标记信息”的监督学习问题。

（二）K-摇臂赌博机

与一般监督学习不同，强化学习任务的最终奖赏是在多步动作之后才能观察到，这里我们不妨先考虑比较简单的情形：最大化单步奖赏，即仅考虑一步操作。需要注意的是，即便在这样的简化情形下，强化学习仍与监督学习有明显不同，因为机器需要通过尝试来发现各个动作产生的结果，而没有训练数据告诉机器应该做哪个动作。
欲最大化单步奖赏需考虑两个方面，

一是需要知道每个动作带来的奖赏；
二是要执行奖赏最大的动作；

若每个动作对应的奖赏是一个确定值，那么尝试一遍所有的动作便能找出奖赏最大的动作。然而，更一般的情形是，一个动作的奖赏来自于一个概率分布，仅通过一次尝试并不能确切的获得平均奖赏。
实际上，单步强化学习任务对应了一个理论模型，即“K-摇臂赌博机”（K-armed bandit），如下图所示，

K-摇臂赌博机有K个摇臂，赌徒在投入一个硬币后可选择按下其中一个摇臂，每个摇臂以一定概率吐出硬币，但这个概率赌徒并不知道。赌徒的目标是通过一定的策略最大化自己的奖赏，即获得最多的硬币。

若仅为获知每个摇臂的期望奖赏，则可采用“仅探索”（exploration-only）法：将所有尝试机会平均分配给每个摇臂（即轮流按下每个摇臂），最后以每个摇臂各自的平均吐币概率作为其奖赏期望的近似估计；
若仅为执行奖赏最大的动作，则可采用“仅利用”（exploitation-only）法：按下目前最优的（即到目前为止平均奖赏最大的）摇臂，若有多个摇臂同为最优，则从中随机选取一个。

显然，“仅探索”法能很好的估计每个摇臂的奖赏，却会失去很多选择最优摇臂的机会；“仅利用”法则相反，它没有很好的估计摇臂期望奖赏，很可能经常选不到最优摇臂。因此，这两种方法都难以使最终的累计奖赏最大化。
事实上，“探索”（即估计摇臂的优劣）和“利用”（即选择当前最优摇臂）是矛盾的，因为尝试次数（即总投币数）有限，加强了一方面则会削弱另一方，这就是强化学习所面临的“探索-利用窘境”（Exploration-Exploitation dilemma）。显然，欲累计奖赏最大，则必须在探索与利用之间达成较好的折中。

ε -贪心

ε -贪心基于一个概率来对探索和利用进行折中。

Softmax

Softmax算法基于当前已知的摇臂平均奖赏来对探索和利用进行折中。

（三）有模型学习

考虑多步强化学习任务，暂且先假定任务对应的马尔科夫决策过程四元组E=均为已知，这种情形称为“模型已知”，即机器已对环境进行了建模，能在机器内部模拟出与环境相同或相近的情况。在已知模型的环境中学习称为“有模型学习”（model-based Learning）。

（四）免模型学习

在现实的强化学习任务中，环境的转移概率、奖励函数往往很难得知，甚至很难知道环境中一共有多少状态。若学习算法不依赖于环境建模，则称为“免模型学习”（model-free learning），这比有模型学习要困难得多。

（五）值函数近似

前面我们一直假定强化学习任务是在有限状态空间上进行，每个状态可用一个编号来指代。然而，现实强化学习任务所面临的状态空间往往是连续的，有无穷多个状态。这该怎么办呢？
一个直接的想法是对状态空间进行离散化，将连续状态空间转化为有限离散状态空间，然后就能使用前面介绍的方法求解。遗憾的是，如何有效的对状态空间进行离散化是一个难题，尤其是在对状态空间进行搜索之前。
实际上，我们不妨直接对连续状态空间的值函数进行学习。

（六）模仿学习

在强化学习的经典任务设置中，机器所能获得的反馈信息仅有多步决策后的累积奖赏，但现实任务中，往往能得到人类专家的决策过程范例。例如在种瓜任务上得到农业专家的种植过程范例。从这样的范例中学习，称为“模仿学习”（imitation learning）。

《机器学习》笔记-规则学习（15）

发表于 2018-05-17

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/36986684

写在最前面

章节目录

基本概念
序贯覆盖
剪枝优化
一阶规则学习
归纳逻辑程序设计

（一）基本概念

规则学习是“符号主义学习”（symbolism learning）的主要代表，是最早开始研究的机器学习技术之一。
机器学习中的“规则”（rule）通常是指语义明确、能描述数据分布所隐含的客观规律或领域概念、可写成“若…，则…”形式的逻辑规则。“规则学习”（rule learning）是从训练数据中学习出一组能用于对未见示例进行判别的规则。一般形式如下所示，

与神经网络、支持向量机这样的“黑箱模型”相比，规则学习具有更好的可解释性，能使用户更直观地对判别过程有所了解。另一方面，数理逻辑具有极强的表达能力，绝大多数人类知识都能通过数理逻辑进行简洁的刻画和表达。因此，规则学习能更自然的在学习过程中引入领域知识。此外，逻辑规则的抽象描述能力在处理一些高复杂度的AI任务时具有显著的优势，例如在问答系统中有时可能遇到非常多、甚至无穷种可能的答案，此时若能基于逻辑规则进行抽象表述或者推理，则将带来极大的便利。
从形式语言表达能力而言，规则可分为两类：

”命题规则“（propositional rule）
由”原子命题“（propositional atom）和逻辑连接词“与”、“或”、“非”和“蕴含”构成的简单陈述句；
“一阶规则”（first-order rule）
基本成分是能描述事物的属性或关系的“原子公式”（automic formula）；

从形式语言系统的角度来看，命题规则是一阶规则的特例，因此一阶规则的学习比命题规则要复杂得多。

（二）序贯覆盖

规则学习的目标是产生一个能覆盖尽可能多的样例规则集。最直接的做法是“序贯覆盖”（sequential covering），即逐条归纳：在训练集上每学到一条规则，就将该规则覆盖的训练样例去除，然后以剩下的训练样例组成训练集重复上述过程。由于每次只处理一部分数据，因此也被称为“分治”（separate-and-conquer）策略。
由于序贯覆盖法简单有效，几乎所有规则学习算法都以它为基本框架。它能方便地推广到多分类问题上，只需将每类分别处理即可。

（三）剪枝优化

规则生成本质是一个贪心搜索过程，需有一定的机制来缓解过拟合的风险，最常见的做法是剪枝（pruning）。与决策树相似，剪枝可发生在规则生长过程中，即“预剪枝”，也可发生在规则产生后，即“后剪枝”。通常是基于某种性能度量指标来评估增/删逻辑文字前后的规则性能，或增/删规则前后的规则集性能，从而判断是否要进行剪枝。

（四）一阶规则学习

受限于命题规则表达能力，命题规则学习难以处理对象之间的“关系”（relation），而关系信息在很多任务中非常重要。需用一阶逻辑表示，并且要使用一阶规则学习。

##（五）归纳逻辑程序设计
归纳逻辑程序设计（Inductive Logic Programming，简称ILP）在一阶规则学习中引入了函数和逻辑表达式嵌套。一方面，这使得机器学习系统具备了更为强大的表达能力；另一方面，ILP可看作用机器学习技术来解决基于背景知识的逻辑程序（logic program）归纳，其学得的“规则”可被PROLOG等逻辑程序设计语言直接使用。

《机器学习》笔记-概率图模型（14）

发表于 2018-05-13

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/36804199

写在最前面

章节目录

隐马尔可夫模型
马尔可夫随机场
条件随机场
学习与推断
近似推断
话题模型

（一）隐马可科夫模型

机器学习最重要的任务，是根据一些已观察到的证据（例如训练样本）来对感兴趣的未知变量（例如类别标记）进行估计和推测。概率模型（probabilistic model）提供了一种描述框架，将学习任务归结于计算变量的概率分布。在概率模型中，利用已知变量推测位置变量的分布称为“推断”（inference），其核心是如何基于可观测变量推测出未知变量的条件分布。具体来说，假定所关心的变量集合为Y，可观测变量集合为O，其他变量集合为R，

“生成式”（generative）模型考虑联合分布P(Y,R,O)；
“判别式”（discriminative）模型考虑条件分布P(Y,R|O);

给定一组观测变量值，推断就是由P(Y,R,O)或P(Y,R|O)得到条件分布P(Y|O)。
直接利用概率和规则消去变量R显然不可行。为了便于研究高效的推断和学习算法，需要有一套能简洁紧凑地表达变量间关系的工具。
概率图模型（probabilistic graphical model）是一类用图来表达变量相关关系的概率模型。它以图为表示工具，最常见的是用一个结点表示一个或一组随机变量，结点之间的边表示变量间的概率相关关系，即“变量关系图”。根据边的性质不同，概率图模型可大致分为两类：

第一类是使用有向无环图表示变量间的依赖关系，称为有向图模型或贝叶斯网（Bayesian network）；
第二类是使用无向图表示变量间的相关关系，称为无向图模型或马尔可夫网（Markov network）；

隐马尔可夫模型（Hidden Markov Model，简称HMM）是结构最简单的动态贝叶斯网（dynamic Bayesian network），这是一种著名的有向图模型，主要用于时序数据建模，在语音识别、自然语言处理等领域有广泛应用。
隐马尔可夫模型中的变量可分为两组。第一组是状态变量{y1，y2，…，yn}，其中，yi∈Y表示第i时刻的系统状态。通常假定状态变量是隐藏的、不可被观测的，因此状态变量亦称隐变量（hidden variable）。第二组是观测变量{x1，x2，…，xn}，其中，xi∈X表示第i时刻的观测值。在隐马尔可夫模型中，系统通常在多个状态{s1，s2，…，sN}之间转换。如下图所示，

在任一时刻，观测变量的取值仅依赖于状态变量，即xt由yt确定，与其他状态变量及观测变量的取值无关。同时，t时刻的状态yt仅依赖于
t-1时刻的状态yt-1，与其余n-2个状态无关。这就是所谓的“马尔可夫链”（Markov chain），即：系统下一时刻的状态仅由当前状态决定，不依赖于以往的任何状态。
在实际应用中，人们常常关注隐马尔可夫模型的三个基本问题：

如何评价模型与观察序列之间的匹配程度
例如许多任务需根据以往的观察序列{x1，x2，…，xn-1}来推测当前时刻最可能的观测值xn；
如何根据观测序列推断出隐藏的模型状态
例如在语音识别等任务中，观测值为语音信号，隐藏状态为文字，目标就是根据观测信号来推断最有可能的状态序列（即对应的文字）；
如何训练模型使其能最好的描述观测数据
例如在大多数现实应用中，人工指定模型参数已变得越来越不可行，如何根据训练样本学得最优的模型参数；

（二）马尔可夫随机场

马尔可夫随机场（markov Random Field，简称MRF）是典型的马尔可夫网，这是一种著名的无向图模型。图中每个结点表示一个或一组变量，结点之间的边表示两个变量之间的依赖关系。马尔可夫随机场有一组势函数（potential function），亦称“因子”（factor），这是定义在变量子集上的非负函数，主要用于定义概率分布模型。

（三）条件随机场

条件随机场（Conditional Random Field，简称CRF）是一种判别式无向图模型。生成式模型是直接对联合分布进行建模，而判别式模型则是对条件分布进行建模。前面介绍的隐马尔可夫模型和马尔可夫随机场都是生成式模型，而条件随机场是判别式模型。

（四）学习与推断

基于概率图模型定义的联合概率分布，我们能对目标变量的边际分布（marginal distribution）或以某些可观测变量为条件的条件分布进行推断。
对概率图模型，还需确定具体分布的参数，这称为参数估计或参数学习问题。
概率图模型的推断方法大致可分为两类：

第一类是精确推断方法
希望能计算出目标变量的边际分布或条件分布的精确值。遗憾的是，一般情形下，此类算法的计算复杂度随着极大团规模的增长呈指数增长，适用范围有限。
第二类是近似推断方法
希望在较低时间复杂度下获得原问题的近似解。此类方法在现实任务中更常用。

精确推断具有代表性的方法有，

1.变量消去

精确推断的实质是一类动态规划算法，它利用图模型所描述的条件独立性来消减计算目标概率值所需的计算量。变量消去是最直观的精确推断算法，也是构建其他精确推断算法的基础。
变量消去法有一个明显的缺陷：若需计算多个边际分布，重复使用变量消去法将对造成大量的冗余计算。

2. 信念传播

信念传播（Belief Propagation）算法将变量消去法中的求和操作看作一个消息传递过程，较好的解决了求解多个边际分布时重复计算问题。

（五）近似推断

精确推断方法通常需要很大的计算开销，因此在现实应用中近似推断方法更为常用。近似推断方法大致可分为两大类：

第一类是采样（sampling）
通过使用随机化方法完成近似；
第二类是使用确定性近似完成近似推断
典型代表为变分推断（variational inference）；

1. MCMC采样

概率图模型中最常用的采用技术是马尔可夫链蒙特卡罗（Markov Chain Monte Carlo，简称MCMC）方法。

2. 变分推断

变分推断通过使用已知简单分布来逼近所需推断的复杂分布，并通过限制近似分布的类型，从而得到一种局部最优、但具有确定解的近似后验分布。

（六）话题模型

话题模型（topic model）是一族生成式有向图模型，主要用于处理离散型的数据（如文本集合），在信息检索、自然语言处理等领域有广泛应用。隐狄利克雷分配模型（Latent Dirichlet Allocation，简称LDA）是话题模型的典型代表。
话题模型中有几个重要概念：词（word）、文档（document）和话题（topic）。

词
“词”是待处理数据的基本离散单元，例如在文本处理任务中，一个词就是一个英文单词或有独立意义的中文词。
文档
“文档”是待处理的数据对象，它由一组词组成，这次词在文档中是不计顺序的，例如一篇论文、一个网页都可看做一个文档；这种表示方式称为“词袋”（bag-of-words）。数据对象只要能用词袋描述，就可使用话题模型。
话题
“话题”表示一个概念，具体表示为一系列相关的词，以及它们在该概念下出现的概率。

《机器学习》笔记-半监督学习（13）

发表于 2018-05-02

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/36351628

写在最前面

章节目录

未标记样本
生成式方法
半监督SVM
图半监督学习
基于分歧的方法
半监督聚类

（一）未标记样本

让学习器不依赖外界交互，自动地利用未标记样本来提升学习性能，就是半监督学习(semi-supervised learning)。
要利用未标记样本，必然要做一些未标记样本所揭示的数据分布信息与类别标记相联系的假设。最常见的是“聚类假设”（cluster assumption），即假设数据存在簇结构，同一个簇样本属于同一个类别。半监督学习中另一个常见假设是“流形假设”（manifold assumption），即假设数据分布在一个流形结构上，邻近的样本拥有相似的输出值。“邻近”程度常用“相似”程度来刻画，因此，流行假设可看作聚类假设的推广，但流形假设对输出值没有限制，因此比聚类假设的适用范围更广，可用于更多类型的学习任务。事实上，无论聚类假设还是流形假设，其本质都是“相似的样本拥有相似的输出”这个基本假设。
半监督学习可进一步划分为纯（pure）半监督学习和直推学习（transductive learning），前者假定训练数据中的未标记样本并非待预测数据，而后者则假定学习过程中所考虑的未标记样本恰是待预测数据，学习的目的就是在这些未标记样本上获得最优泛化性能。换言之，纯半监督学习是基于“开放世界”假设，希望学得模型能适用于训练过程中未观察到的数据；而直推学习是基于“封闭世界”假设，仅试图对学习过程中观察到的未标记数据进行预测。如下图所示，

（二）生成式方法

生成式方法（generative methods）是直接基于生成式模型的方法。此类方法假设所有数据（无论是否有标记）都是由同一个潜在的模型“生成”的。这个假设使得我们能通过潜在模型的参数将未标记数据与学习目标联系起来，而未标记数据的标记则可看作模型的缺失参数，通常可基于EM算法进行极大似然估计求解。此类方法的区别主要在于生成式模型的假设，不同的模型假设将产生不同的方法。

（三）半监督SVM

半监督支持向量机（Semi-Supervised Support Vector Machine，简称 S3VM）是支持向量机在半监督学习上的推广。在不考虑未标记样本时，支持向量机试图找到最大间隔划分超平面，而在考虑未标记样本后，S3VM试图找到能将两类有标记样本分开，且穿过数据低密度区域的划分超平面。如下图所示，

这里的基本假设是“低密度分隔”（low-density separation），显然，这是聚类假设在考虑了线性超平面划分后的推广。

（四）图半监督学习

给定一个数据集，我们可将其映射为一个图，数据集中每个样本对应于图中一个结点，若两个样本之间的相似度很高（或相关性很强），则对应结点之间存在一条边，边的“强度”（strength）正比于样本之间的相似度（或相关性）。我们可将有标记样本所对应的结点想象为染过色，而未标记样本所对应的结点尚未染色。于是，半监督学就对应于“颜色”在图上扩散或传播的过程。由于一个图对应了一个矩阵，这使得我们能基于矩阵运算来进行半监督学习算法的推到和分析。
图半监督学习方法在概念上相当清晰，且易于通过对所涉矩阵运算的分析来探索算法性质。但此类算法的缺陷也相当明显。首先是在存储开销上，若样本数为O(m)，则算法中所涉及的矩阵规模未O(m2)，这使得此类算法很难直接处理大规模数据；另一方面，由于构图过程仅能考虑训练样本集，难以判断新样本在图中的位置，因此，在接收到新样本时，或是将其加入原数据集对图进行重构并重新进行标记传播，或是需引入额外的预测机制。

（五）基于分歧的方法

与生成式方法、半监督SVM、图半监督学习等基于单学习器利用未标记数据不同，基于分歧的方法（disagreement-base methods）使用多学习器，而学习器之间的“分歧”（disagreement）对未标记数据的利用至关重要。
基于分歧的方法只需采用合适的基学习器，就能较少受到模型假设、损失函数非凸性和数据规模的影响，学习方法简单有效、理论基础相对坚实、适用范围较为广泛。为了使用此类方法，需能生成具有显著分歧、性能尚可的多个学习器，但当有标记样本很少，尤其是数据不具有多视图时，要做到这一点并不容易，需有技巧的设计。

（六）半监督聚类

聚类是一种典型的无监督学习任务，然而在现实聚类任务中我们往往能获得一些额外的监督信息，于是可通过半监督聚类（semi-supervised clustering）来利用监督信息以获得更好的聚类效果。
聚类任务中获得的监督信息大致有两种类型。第一种类型是“必连”（must-link）与“勿连”（cannot-link）约束，前者是指样本必属于同一个簇，后者是指样本必不属于同一个簇；第二种类型的监督信息则是少量的有标记样本。

《机器学习》笔记-计算学习理论（12）

发表于 2018-04-15

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/35715053

写在最前面

章节目录

基础知识
PAC学习
有限假设空间
VC维
Rademacher复杂度
稳定性

（一）基础知识

顾名思义，计算学习理论(computation learning theory)研究的是关于通过“计算”来进行“学习”的理论。即关于机器学习的理论基础，其目的是分析学习任务的困难本质，为学习算法提供理论保证，并根据分析结果指导算法设计。

（二）PAC学习

计算学习理论中最基本的是概率近似正确(Probably Approximately Correct，简称PAC)学习理论。
给定训练集D，我们希望基于学习算法ξ学得的模型所对应的假设h尽可能接近目标概念c。
PAC学习中一个关键因素是假设空间H的复杂度。H包含了学习算法ξ所有可能输出的假设，若在PAC学习中假设空间与概念类完全相同，即H=C，这称为“恰PAC可学习”（properly PAC learnable）；直观地看，这意味着学习的能力与学习任务“恰好匹配”。然而，这种让所有候选假设都来自概念类的要求看似合理，但却并不实际，因为在现实应用中我们对概念类C通常一无所知，更别说获得一个假设空间与概念类恰好相同的学习算法。显然，更重要的研究假设空间与概念类不同的情形，即H≠C。一般而言，H越大，其包含任意目标概念的可能性越大，但从中找到某个具体目标概念的难道也越大。|H|有限时，我们称H为“有限假设空间”，否则称为“无限假设空间”。

（三）有限假设空间

可分情形
可分情形意味着目标概念c属于假设空间H，即c∈H；
不可分情形
对较为困难的学习问题，目标概念c往往不存在与假设空间H中；

（四）VC维

现实学习任务所面临的通常是无限假设空间。欲对此种情形的学习性进行研究，需度量假设空间的复杂度。最常见的办法是考虑假设空间的“VC维”（Vapnik-Chervonenkis dimension）。

（五）Rademacher复杂度

基于VC维的泛化误差界是分布无关、数据独立的，也就是说，对任何数据分布都成立。这使得基于VC维的学习性分析结果具有一定的“普适性”；但从另一个方面来说，由于没考虑数据自身，基于VC维得到的泛化误差界通常比较“松”，对那些与学习问题的典型情况相差甚远的较“坏”分布来说尤其如此。
Rademacher复杂度（Rademacher complexity）是另一种刻画假设空间复杂度的途径，与VC维不同的是，它在一定程度上考虑了数据分布。

（六）稳定性

无论是基于VC维还是Rademacher复杂度来推导泛化误差界，所得到的结果均与具体学习算法无关。对所有学习算法都适用。这使得人们能够脱离具体学习算法的设计来考虑学习问题本身的性质。但在另一方面，若希望获得与算法有关的分析结果，则需另辟蹊径。稳定性（stability）分析是这方面一个值得关注的方向。
顾名思义，算法的“稳定性”考察的是算法在输入发生变化时，输出是否会随之发生较大的变化。

《机器学习》笔记-特征选择与稀疏学习（11）

发表于 2018-02-23

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/33943881

写在最前面

章节目录

子集搜索与评价
过滤式选择
包裹式选择
嵌入式选择与L1正则化
稀疏表示与字典学习
压缩感知

（一）子集搜索与评价

我们称样本属性为“特征”（feature），对当前学习任务有用的属性称为“相关特征”（relevant feature）、没什么用的属性称为“无关特征”（inrelevant feature）。从特征集合中选择相关特征子集的过程，称为“特征选择”（feature selection）。
特征选择是一个重要的“数据预处理”（data preprocessing）过程，在现实机器学习中，获得数据之后通常进行特征选择，之后再进行训练学习器。
特征选择的原因主要包括：

首先，我们在现实任务中经常会遇到维数灾难问题，这是由于属性过多而造成的，若能从中选择出重要的特征，使得后续学习过程仅需要在一部分特征上构建模型，则维数灾难问题会大为减轻（降维和特征选择是处理高维数据的两大主流技术）。
其次，去除不相关特征，只留下关键因素，往往会降低学习任务的难度。

从初始的特征集合中选取一个包含了所有重要信息的特征子集，涉及两个关键环节：

“子集搜索”（subset search）
搜索策略包括“前向”（forward）搜索，“后向”（backward）搜索和”双向“（bidirectional）搜索；
”子集评价“（subset evaluation）
子集评价采用信息增益作为评价准则；

将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。
常见的特征选择方法大致可分为三类：过滤式（filter）、包裹式（wrapper）和嵌入式（embedding）。

（二）过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行”过滤“，再用过滤后的特征来训练模型。
其中，Relief（Relevant Feature）是一种著名的过滤式特征选择方法，该方法设计了一个”相关统计量“来度量特征的重要性。

（三）包裹式选择

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定的学习器选择最有利其性能、“量身定做”的特征子集。
一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。
LVW(Las Vegs Wrapper)式一个典型的包裹式特征选择方法。

（四）嵌入式选择与L1正则化

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明确的分别；与此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一过程中完成，即在学习器训练过程中自动地进行了特征选择。
当样本特征很多，而样本数较少时，训练很容易陷入过拟合。为了缓解过拟合问题，引入正则化项。
L1范数和L2范数都有助于降低过拟合风险，但前者会带来一个额外的好处：它比后者更容易获得“稀疏(sparse)解”，即它求得的w会有更少的非零分量。

（五）稀疏表示与字典学习

把数据集D考虑成一个矩阵，其每一行对应于一个样本，每列对应与于一个特征。特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征寻找去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高。
现在考虑另一种稀疏性：D所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。
当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处。例如具有高度的稀疏性使大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。
为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为”字典学习“（dictionary learning），亦称”稀疏编码“(sparse coding)。这两个称谓稍有差别，”字典学习“更侧重于学得字典的过程，而”稀疏编码“则更侧重于对样本稀疏表达的过程。

（六）压缩感知

与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具备的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为”感知测量“和”重构恢复“这两个阶段。”感知测量“关注如何对原始信号进行处理以获得稀疏样本表示；”重构恢复“关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓，当我们谈到压缩感知时，通常是指该部分。
基于部分信息来恢复全部信息的技术在许多现实任务中有重要应用。例如网上书店通过收集读者在网上对书的评价，可根据读者的读书偏好来进行新书推荐，从而达到定向广告投放的效果。显然，没有哪位读者读过所有的书，也没有那本书被所有读者读过，因此，网上书店所搜索到的仅有部分信息，如下图所示，

那么，能够将上图中通过读者评价得到的数据当做部分信号，基于压缩感知的思想恢复出完整的信号呢？
矩阵补全（matrix completion）技术可用于解决这个问题。

《机器学习》笔记-降维与度量学习（10）

发表于 2018-02-10

由于图片外链被禁止了，图片不能显示，完整文章看这里吧：https://zhuanlan.zhihu.com/p/33739227

写在最前面

章节目录

k近邻学习
低纬嵌入
主成分分析
核化线性降维
流形学习
度量学习

（一）k近邻学习

k近邻（k-Nearest，简称kNN）学习是一种常用的监督学习方法，其工作机制非常简单：给定测试样本，基于某种距离度量找出训练集中与其最靠近的k个训练样本。然后基于这k个“邻居”的信息进行预测。通常，在分类任务中可使用“投票法”，即选择这k个样本中出现最多的类别标记作为预测结果；在回归任务中可使用“平均法”，即将这k个样本的实际值输出标记的平均值作为预测结果。还可基于距离远近的加权平均或加权投票，距离越近的样本权重越大。
与先前介绍的学习方法相比，k近邻学习有一个明显的不同之处，它似乎没有显示的训练过程。事实上，它是“懒惰学习”（lazy learning）的著名代表，此类学习技术在训练阶段仅仅是将样本存储起来，训练开销为零，待收到测试样本后再进行处理；相应的，那些在训练阶段就对样本进行学习处理的方法，称为“急切学习”（eager learning）。
下图给出了k近邻分类器的一个示意图，

近邻分类器虽简单，但它的泛化错误率不超过贝叶斯最优分类器的错误率的两倍。

（二）低维嵌入

上一节的讨论是基于一个重要假设：任意测试样本x附近任意小的δ距离范围内总能找到一个训练样本，即训练样本的采样密度足够大，或称为“密采样”（dense sample）。然而，这个假设在现实任务中通常很难满足。此外，许多学习方法都涉及距离计算，而高维空间会给距离计算带来很大麻烦，例如当维数很高时，甚至连计算内积都不再容易。
事实上，在高维情形下出现的数据样本稀疏，计算距离困难等问题，是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”（curse of dimensionality）。
缓解维数灾难的一个重要途径是降维（dimension reduction），亦称“维数简约”，即通过某种数学变换将原始高纬度属性空间转变为一个低维“子空间”（subspace），在这个子空间中样本密度大幅提高，计算距离也变得更为容易。为什么能进行降维？这是因为在很多时候，人们人们观测或收集到的数据样本虽是高维的，但与学习任务密切相关的也许仅是某个低维分布，即高维空间的一个底维“嵌入”（embedding）。下图给出了一个直观的例子，原始高维空间中的样本点，在这个低纬嵌入子空间中更容易进行学习。

若要求原始空间中的样本之间距离在低维空间中得以保持，如上图所示，即得到“多维缩放”（Multiple Dimensional Scaling，简称MDS）这样一种经典的降维方法。
对降维效果的评估，通常是比较降维前后学习器的性能，若性能有所提高则认为降维起到了作用。若维数降低到二维或三维，则可通过可视化技术来直观的判断降维效果。

（三）主成分分析

主成分分析（Principal Component Analysis，简称PCA）是最常用的一种降维方法。
PCA仅需保留W与与样本的均值向量即可通过简单的向量减法和矩阵向量乘法将样本投影到低维空间中。显然，低维空间与原始高维空间必有不同，因为对应于最小的d-d’个特征值的特征向量被舍弃了，这是降维导致的结果。但舍弃这样的信息往往是必要的：

一方面，舍弃这部分信息之后能使样本的采样密度增大，这正是降维的重要动机；
另一方面，当数据受到噪声影响时，最小的特征值所对应的特征向量往往与噪声有关，将它们舍弃能在一定程度上起到去噪的效果。

（四）核化线性降维

线性降维方法假设从高维空间到低维空间的函数映射是线性的，然而，在不少实际任务中，可能需要非线性映射才能找到恰当的低维嵌入。
非线性降维的一种常用方法，是基于核技巧对线性降维方法进行”核化“（kernelized）。

（五）流形学习

流形学习（manifold learning）是一类借鉴了拓扑流形概念的降维方法。”流形“是在局部与欧氏空间同胚的空间，换言之，它在局部具有欧氏空间的性质，能用欧氏距离来进行距离计算。这给降维方法带来了很大的启发。若低维流形嵌入到高维空间中，则数据样本在高维空间的分布虽然看上去非常复杂，但在局部上仍具有欧氏空间的性质，因此，可以容易的在局部建立降维映射关系，然后，再设法将局部映射关系推广到全局。当维数被降至二维或三维时，能对数据进行可视化展示，因此流形学习也可被用于可视化。
其中，等量度映射和局部线性嵌入式两种著名的流形学习方法。

（六）度量学习

在机器学习中，对高维数据进行降维的主要目的是希望找到一个合适的低维空间，在此空间中进行学习能比原始空间性能更好。事实上，每个空间对应了在样本属性上定义的一个距离度量，而寻找合适的空间，实质上就是在寻找一个合适的距离度量。直接尝试”学习“出一个合适的距离度量，就是度量学习（metric learning）的基本动机。

写在最前面

信心与兴趣

编程语言

经典数据结构与算法

数学基础

机器学习

深度学习

自然语言处理

小节

官方参考示例

1. gRPC示例

2. RESTfull API示例

示例代码分析

1. 模型标识

2. 签名标识

3. 输入标识

4. 输出标识

总结

服务框架

TF Serving工作流程

简单示例

示例（一）：RESTfull API形式

1. 准备TF Serving的Docker环境

2. 下载官方示例代码

3. 运行TF Serving

4.客户端验证

示例（二）：gRPC形式

1. 准备TF Serving的Docker环境

2. 下载官方示例代码

3. 模型编译

4. 运行TF Serving

4.客户端验证

资料参考

写在最前面

章节目录

（一）任务与奖赏

（二）K-摇臂赌博机

ε -贪心

Softmax

（三）有模型学习

（四）免模型学习

（五）值函数近似

（六）模仿学习

写在最前面

章节目录

（一）基本概念

（二）序贯覆盖

（三）剪枝优化

（四）一阶规则学习

写在最前面

章节目录

（一）隐马可科夫模型

（二）马尔可夫随机场

（三）条件随机场

（四）学习与推断

1.变量消去

2. 信念传播

（五）近似推断

1. MCMC采样

2. 变分推断

（六）话题模型

写在最前面

章节目录

（一）未标记样本

（二）生成式方法

（三）半监督SVM

（四）图半监督学习

（五）基于分歧的方法

（六）半监督聚类

写在最前面

章节目录

（一）基础知识

（二）PAC学习

（三）有限假设空间

（四）VC维

（五）Rademacher复杂度

（六）稳定性

写在最前面

章节目录

（一）子集搜索与评价