Non-Separable Data And Types of Learning
0.说在前面
1.PLA优缺点
2.Packet Alogrithm
4.Leaning with Different Output Space Y
5. Learning with Different Data Label yn
6.Learning with Different Protocol f(xn,yn)
7.Learning with Different Input Space X
8.作者的话
0.说在前面
上一节最终得出结论，PLA可以停下来并正确分类，但是停下来之前需要满足数据集是线性可分的。
但是如果是非线性情况，w(f)实际上并不存在，那之前的推导跟结论也就不正确。
因此本节主要讨论在线性可分的PLA上做出修改后的Packet Algorithm算法。 除此之外，介绍一下机器学习的种类。
1.PLA优缺点
优缺点图
2.Packet Alogrithm
对于非线性可分的情况，我们可以把它当成是数据集D中掺杂了一些noise，事实上，大多数情况下，我们的数据集在收集资料中就存在一些noise.此时的机器学习流程为：
Packet算法图
那么到这里就提出了一个问题：当数据集不是线性可分或者说数据集有noise情况下，还是可以找到一条好的线呢？
假设noise很小，小的状况下，y与f有一定的对应程度。
现在的情况是，我们假设找不到一条完美的线，那么我们找可以一条所犯错误最小的线(最好的线)。
有噪点图
事实上，上面的解是NP-hard问题，难以求解！
然而我们可以利用上述思想，通过找一条犯错误最小的线，将其应用到非线性可分数据集中，获得近似最好的g。、
那么这个思想就被称为，修改后的PLA，简称Packet Algorithm。
【思想】
类似于PLA，不同之处在于，在修正同时，将修正后的线划分的错误点个数与修正之前的错误点个数比对，取个数较小的直线作为当前选择的分类直线。
之后，经过n次迭代，不断比较当前分类错误点个数与之前最少的错误点个数比较，选择最小的值保存。直到迭代次数完成后，选取个数最少的直线对应的w，即为我们最终想要得到的权重值。
Packet算法图
对于线性可分的资料，一般情况下，Pocket Algorithm要比PLA速度慢一些！
原因：PA要存储，其次是要检查哪条线比较好。
4.Leaning with Different Output Space Y
上几节中提到了银行发卡例子，发卡用 1表示(正类)，不发卡用-1表示(负类)。
这个在分类问题中为二元分类问题，除了这个例子之外还有判断邮件是否为垃圾邮件，患者是否患癌症等。
二元分类分为线性和非线性模型。需要根据情况选择相应的模型。
在大类方面除了，二分类以外，还包括多分类问题。多分类问题描述为，输出多于两个，y={1，2，…,K}，K>2。一般多分类的应用有数字识别、硬币价值分类等。
上述提到的不管是二分类，还是多分类问题，输出都为离散值。而像预测房价股票收益等情况，输出为连续值，则称这类问题叫做回归。比如线性回归就是一个简单的模型。
除了分类和回归之外，在NLP领域，经常用到的一个机器学习问题：结构化学习(Structured Learning)。结构化学习的输出空间包含了某种结构在里面，由于比较复杂，所以这个在后续的学习中，深入研究。
5. Learning with Different Data Label yn
【监督式学习】英文为：Supervised Learning ，描述为对于一个训练样本D既有输入特征x，也有输出yn。
典型的监督式学习包括：
二分类，多分类或回归，最重要的是知道输出标签yn。
【非监督式学习】 英文为：Unsupervised learning，描述为对于一个训练样本D只有输入特征x，而无输出yn。
典型的非监督学习包括：
聚类问题，比如：对网页上新闻的自动分类；
密度估计，比如：交通路况分析；
异常检测，比如：用户网络流量检测；
两者对比：非监督学习可以用监督学习方法来解决相应的问题，而且非监督一般要比监督学习复杂一点。
【半监督学习】 英文为：Semi-supervised Learning，描述为一部分数据有输出标签yn，另一部分输出没有标签yn。
在现实生活中，半监督学习会经常用到，比如医药公司对某些药物进行检测，由于受到成本和实验人群限制等问题，只有一部分数据有输出标签yn。这时候就需要用到监督学习。
【增强学习】 英文为：Reinforcement Learning，又称强化学习，描述为我们给模型或系统一些输入，但是给不了我们希望的真实输出y，根据模型的输出反馈，如果反馈结果良好，更接近真实输出，就给其奖励，反之，偏离真输出，就给惩罚，这种不断通过“反馈-修正”的形式，一步一步让模型学习的更好，这就是增强学习的核心所在。
实例：增强学习可以类比成训练宠物的过程，我们给狗发一条“sit down”的指令，在训练过程中，如果它表现得好，我们就给予奖励，否则给予惩罚。这样不断修正狗的动作，最终让它能按照我们的指令来行动。
6.Learning with Different Protocol f(xn,yn)
【Batch Learning】
一次性拿到整个D，对其进行学习建模，得到最终的机器学习模型。最广泛的一种。
【Online】
一种在线学习模型，数据实时更新，根据数据一个一个进来，同步更新我们的算法。比如邮件过滤系统，根据每封邮件的内容，不断判定是否为垃圾邮件，再根据用户反馈，及时更新算法。类似于这种动态且在线的过程还有前面提到的PLA和增强学习。
【Active Learning】
新出现的一种机器学习类型，即让机器具备主动问问题的能力，例如：手写数字识别，机器可以主动提问。
这种方法的优势之处在于获取样本label困难时候，可以节约成本和时间，只对一些重要的label提出问题。
7.Learning with Different Input Space X
前面提到了输出空间进行分类，根据输出y进行打label，那么本节将输入X有哪些类型。
【concerte features】
具体的特征，X的每个维度都具有复杂的物理含义。比如说年龄，性别，年收入等等。使用具体的特征进行学习。
【raw features】
考虑一个"手写数字识别"任务，如果使用具体特征，我们可以考虑对称性、密度之类的。
手写数字识别图
如上图所示，仅分类1，5两类，可以注意到1的对称性更强，密度更低。
所以1的实例大部分分布在左上角，5在右下角。 这就是根据具体特征来学习。
考虑更原始的特征，即图片的像素。每张图片的分辨率都是16∗16，16∗16，所以可以将输入图转化为一个256维的向量。每个维度的物理含义很简单，代表一个像素点。原始特征的物理含义更简单，因此机器根据原始特征进行学习过程更难。
原始特征经常需要人工或机械地转化为具体特征，转化的过程叫做特征工程，深度学习也是特征工程的一种。
【abstract features】
抽象特征如用户id，或者加密过的资料编号，这些特征X完全抽象，几乎没有物理含义，更需要进行特征工程。
8.作者的话
以上正文图片来源于林老师课程！ 最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多内容，请关注本公众号机器学习系列！
