2019-12-25 16:11:48 qq_42003997 阅读数 64

一个数据集、单个算法

一次留出法----二项检验

  m个样本的测试集上,泛化错误率为ϵ\epsilon的学习器被测得测试错误率为ϵ^\hat{\epsilon}的概率是:
P(ϵ^;ϵ)=(mc^×m)ϵe^×m(1ϵ)me^×m P(\hat{\epsilon} ; \epsilon)=\left(\begin{array}{c} {m} \\ {\hat{c} \times m} \end{array}\right) \epsilon^{\hat{e} \times m}(1-\epsilon)^{m-\hat{e} \times m}
  服从二项分布,可使用“二项检验”进行检验。

多次重复留出法或交叉验证法----t检验

  多次重复留出法或者交叉验证法进行训练/测试,会得到多个测试错误率,此时可使用“t检验”。假定获得了k个测试错误率,ϵ1^ϵ2^ϵ3^ϵ^k\hat{\epsilon1}、\hat{\epsilon2}、\hat{\epsilon3}…\hat{\epsilon}k,则平均测试错误率为Xˉ\bar{X}S2S^{2}
Xˉ=1ki=1kε^i,S2=1k1i=1k(ε^iXˉ)2 \bar{X}=\frac{1}{k} \sum_{i=1}^{k} \hat{\varepsilon}_{i} \quad, \quad S^{2}=\frac{1}{k-1} \sum_{i=1}^{k}\left(\hat{\varepsilon}_{i}-\bar{X}\right)^{2}
  根据中心极限定理可知,
(Xˉε)S/nt(n1) \frac{(\bar{X}-\varepsilon)}{S / \sqrt{n}} \sim t(\mathrm{n}-1)
  t分布示意图及常用双边临界值表如下所示:
在这里插入图片描述

一个数据集、两个算法----交叉验证t检验

  对于一个数据集,两个算法A和B,使用k折交叉验证法得到的测试错误率分别为ε^iAε^iB(i=1,2,,,k)\hat{\varepsilon}_{iA} 、 \hat{\varepsilon}_{iB}(i=1,2,,,k)。可采用k折交叉验证“成对t检验”来进行检验。
  基本思想是若两个算法的性能相同,则他们使用相同的训练集/测试集得到的测试错误率应相同,即ε^iA=ε^iB\hat{\varepsilon}_{iA} = \hat{\varepsilon}_{iB}
对每一组测试错误率求差值,Δi=ε^Aε^B\Delta_{i}=\hat{\varepsilon}_{A}-\hat{\varepsilon}_{B},若两个算法性能相同,则差值均值为零。可根据Δ1Δ2...Δk\Delta_{1、}\Delta_{2、}... \Delta_{k、}进行t检验,计算出差值的均值Δ|\vec{\Delta}|和方差S2S^2,则:
(Δˉ(εAεB)S/kt(k1) \frac{\left|\left(\bar{\Delta}-\left(\varepsilon_{A}-\varepsilon_{B}\right)\right\rangle\right|}{S / \sqrt{\mathrm{k}}} \sim t(\mathrm{k}-1)
  若假设H0:εA=εB,H1:εAεBH_{0}: \varepsilon_{A}=\varepsilon_{B}, H_{1}: \varepsilon_{A} \neq \varepsilon_{B},则,满足ΔˉS/kt/2\frac{|\bar{\Delta}|}{S / \sqrt{\mathrm{k}}} \leq \mathrm{t}_{\partial / 2}
  由于样本有限,在使用交叉验证等方法的时候,会导致不同轮次的训练集有一定程度的重叠,是的测试错误率不独立,导致过高估计假设成立的概率,为缓解这一问题,可采用“5次2折交叉验证”。

一组数据集、多个算法----Friedman检验与Nemenyi检验

Friedman检验

  假设有数据集D1、D2、D3、D4,算法A、B、C进行比较。
  使用留出法或者交叉验证得到每个算法在每个数据集上的测试结果,然后在每个数据集上根据测试性能由好到坏排序,并赋予序值1,2,…,若算法测试性能相同,则平分序值。
在这里插入图片描述
  使用Friedman检验来判断浙西额算法是否性能相同,若相同,则它们的平均序值应当相同。
  若在N个数据集,比较k个算法,令ri{r_i}表示第i个算法的平均序值,则ri{r_i}的均值和方差分别为(k+1)/2,(k+1)(k1)/12(k+1) / 2, \quad(k+1) \quad(k-1) / 12,则有:
τχ2=k1k12Nk21i=1k(rik+12)2=12Nk(k+1)(i=1kri2k(k+1)24) \begin{aligned} \tau_{\chi^{2}} &=\frac{k-1}{k} \cdot \frac{12 N}{k^{2}-1} \sum_{i=1}^{k}\left(r_{i}-\frac{k+1}{2}\right)^{2} \\ &=\frac{12 N}{k(k+1)}\left(\sum_{i=1}^{k} r_{i}^{2}-\frac{k(k+1)^{2}}{4}\right) \end{aligned}
  在k和N比较大时,服从自由度为k-1的χ2\chi^{2}分布。
τF=(N1)τχ2N(k1)τχ2 \tau_{F}=\frac{(N-1) \tau_{\chi^{2}}}{N(k-1)-\tau_{\chi^{2}}}
  服从自由度为k-1和(k-1)(N-1)的F分布。下面是F检验常用的临界值:
F检验常用临界值

Nemenyi检验

  若原假设被拒绝,则需要进行后续检验,来得到具体的算法之间的差异。常用的是Nemenyi检验。Nemenyi检验计算出平均序值差别的临界值域,下表是常用的qa值,若两个算法的平均序值差超出了临界值域CD,则相应的置信度1α1-\alpha拒绝“两个算法性能本相同”的假设。
CD=qαk(k+1)6N C D=q_{\alpha} \sqrt{\frac{k(k+1)}{6 N}}
  qa中常用的联临界值:
在这里插入图片描述

链接

https://blog.csdn.net/qqMiSa/article/details/98660515

2017-09-01 22:43:19 shiyongraow 阅读数 333

处理偏移数据

在前面的课程中,作者提到了误差分析以及设定误差度量值的重要性。那就是设定某个实数来评估你的学习算法,并衡量它的表现。有了算法的评估和误差度量值,有一件重要的事情要注意,就是使用一个合适的误差度量值。这有时会对于你的学习算法造成非常微妙的影响。即“偏斜类问题”。

作者这里以癌症分类问题为例:
1)、训练逻辑回归模型hθ(x)。(如果是癌症y=1,否则y=0)
2)、发现你在测试集上有1%的错误率。(99%的诊断是正确的)
3)、只有0.50%的病人患有癌症

我们训练逻辑回归模型,假设我们用测试集检验了这个分类模型,并且发现它只有1%的错误,因此我们99%会做出正确诊断。看起来是非常不错的结果,我们99%的情况都是正确的。
但是,假如我们发现,在测试集中只有0.5%的患者真正得了癌症,那么在这个例子中 1%的错误率就不再显得那么好了。

再举具体例子:

function y = predictCancer(x)
    y = 0; %ignore x!
return

这不是机器学习代码,它忽略了输入值X,它让y总是等于0,因此它总是预测没有人得癌症,那么这个算法实际上只有0.5%的错误率。因此这甚至比我们之前得到的1%的错误率更好。这是一个非机器学习算法,因为它只是预测y总是等于0。
这种情况发生在正例和负例的比率非常接近于一个极端值,在这个例子中,正样本的数量与负样本的数量相比,非常非常少。因为y=1非常少,我们把这种情况叫做偏斜类。

一个类中的样本数与另一个类的数据相比多很多,通过总是预测y=0或者总是预测y=1算法可能表现非常好。因此使用分类误差或者分类精确度来作为评估度量可能会产生如下问题:

假如说你有一个算法,它的精确度是99.2%,因此它只有0.8%的误差。假设你对你的算法做出了一点改动,现在你得到了99.5%的精确度,只有0.5%的误差,这到底是不是算法的一个提升呢?

用某个实数来作为评估度量值的一个好处就是,它可以帮助我们迅速决定我们是否需要对算法做出一些改进。将精确度从99.2%提高到99.5%,但是我们的改进到底是有用的,还是说我们只是把代码替换成了像y=0这样的东西?

因此如果你有一个偏斜类,用分类精确度并不能很好地衡量算法,因为你可能会获得一个很高的精确度,非常低的错误率。但是我们并不知道我们是否真的提升了分类模型的质量,因为y=0并不是一个好的分类模型。但是y=0会将你的误差降低至0.5%。


查准率(precision)和召回率(recall)

当我们遇到这样一个偏斜类时,我们希望有一个不同的误差度量值,或者不同的评估度量值。其中一种评估度量值叫做查准率(precision)和召回率(recall)。

查准率和召回率的具体解释:
假设我们正在用测试集来评估一个分类模型,对于测试集中的样本,每个测试集中的样本都会等于0或者1(假设这是一个二分问题)我们的学习算法要做的是:做出值的预测,并且学习算法会为每一个测试集中的实例做出预测,预测值也是等于0或1。
预测类别与实际类别

基于实际的类与预测的类:
1)、如果有一个样本它实际所属的类是1,预测的类也是1,那么我们把这个样本叫做真阳性(true positive),意思是说我们的学习算法 预测这个值为阳性,实际上这个样本也确实是阳性。
2)、如果我们的学习算法预测某个值是阴性(等于0),实际的类也确实属于0,那么我们把这个叫做真阴性(true negative),我们预测为0的值实际上也等于0。
3)、如果我们的学习算法预测某个值等于1,但是实际上它等于0,这个叫做假阳性(false positive)。比如我们的算法预测某些病人患有癌症,但是事实上他们并没有得癌症。
4)、最后如果我们的学习算法预测某个值等于0,但是实际上它等于1,这个叫做假阴性(false negative)。因为我们的算法预测值为0,但是实际值是1。

这样我们就有了另一种方式来评估算法的表现。即要计算查准率与召回率。

查准率(Precision)

查准率的意思是,对于所有我们预测他们患有癌症的病人,有多大比率的病人是真正患有癌症的。查准率越高就越好,这是说,对于那些病人,我们告诉他们:”非常抱歉,我们认为你得了癌症”,高查准率说明对于这类病人我们对预测他们得了癌症有很高的准确率。

召回率(Recall)

召回率是如果所有的在数据集中的病人(假设测试集中的病人,或者交叉验证集中的病人)确实得了癌症,有多大比率 我们正确预测他们得了癌症。同样地,召回率越高越好。

通过计算查准率和召回率我们能更好的知道分类模型到底好不好。
具体地说,如果我们有一个算法,总是预测y=0,即它总是预测没有人患癌症,那么这个分类模型的召回率等于0,因为它不会有真阳性。因此我们能会快发现这个分类模型不是一个好的模型。
总的来说,即使我们有一个非常偏斜的类,算法也不能够”欺骗”我们。我们能够更肯定的是:拥有高查准率或者高召回率的模型是一个好的分类模型。这给予了我们一个更好的评估值,给予我们一种更直接的方法来评估模型的好与坏。

最后一件需要记住的事,在查准率和召回率的定义中,我们总是习惯性地用y=1表示稀少的情况(比如癌症,我希望它是个很稀少的情况),查准率和召回率会被定义为y=1而不是y=0作为某种我们希望检测的出现较少的类。通过使用查准率和召回率,我们发现即使我们拥有非常偏斜的类,算法不能够通过总是预测y=1或y=0来”欺骗”我们。因为它不能够获得高查准率和召回率。具体地说,如果一个分类模型拥有高查准率和召回率,那么我们可以确信地说这个算法表现很好,即便它是一个很偏斜的类。

因此对于偏斜类的问题,查准率和召回率给予了我们更好的方法来检测学习算法表现如何,这是一种更好地评估学习算法的标准。当出现偏斜类时,比仅仅只用分类误差或者分类精度好。


权衡精确度和召回率

在之前的课程中,我们谈到查准率和召回率作为遇到偏斜类问题的评估度量值。在很多应用中,我们希望能够保证查准率和召回率的相对平衡。
仍然以癌症分类为例,以逻辑回归模型训练数据。
这里写图片描述
我们往往希望只有在非常确信的情况下,预测一个病人得了癌症。
为了肯定我们的判断,我们可以修改阈值(临界值)!

高查准率低召回率情况

我们不再将临界值设为0.5,也许我们只在hθ(x)≥0.7的情况下,才预测y=1。因此我们会在我们认为他有≥70%得癌症的概率情况下,告诉一个人他得了癌症。
如果你这么做,那么你只在非常确信地情况下才去预测癌症,那么你的回归模型会有较高的查准率,因为在所有你准备告诉他们患有癌症的病人中,他们有较高的可能性真的患有癌症。
你预测患有癌症的病人中有较大比率的人,他们确实患有癌症。因为这是我们在非常确信的情况下做出的预测。

与之相反,这个回归模型会有较低的召回率,因为当我们做预测的时候,我们只给很小一部分的病人预测y=1,现在我们把这个情况夸大一下,我们不再把临界值 设在0.7,我们把它设为0.9,我们只在至少90%肯定这个病人患有癌症的情况下才预测y=1。那么这些病人当中,有非常大的比率,真正患有癌症。因此这是一个高查准率的模型。但是召回率会变低,因为我们希望能够正确检测患有癌症的病人。

高召回率低查准率情况

假设我们希望避免遗漏掉患有癌症的人,即我们希望避免假阴性。具体地说,如果一个病人实际患有癌症,但是我们并没有告诉他患有癌症,那这可能会造成严重后果。因为如果我们告诉病人他们没有患癌症,那么他们就不会接受治疗。但是如果他们真的患有癌症,我们又没有告诉他们,那么他们就根本不会接受治疗,这可能会造成严重后果,甚至使病人丧失生命,因为我们没有告诉他患有癌症,他没有接受治疗。这种情况下,我们希望预测病人患有癌症,即y=1。这样他们会做进一步的检测,然后接受治疗以避免他们真的患有癌症。

在这个例子中,我们不再设置高的临界值,我们会设置另一个值,将临界值设得较低,比如0.3。这样以来,我们认为这些病人有>30%的概率患有癌症,我们以更加保守的方式来告诉他们患有癌症,因此他们能够接受治疗。但是在这种情况下,我们会有一个较高召回率的模型。因为在患有癌症的病人中,有很大一部分被我们正确标记出来了,但是我们会得到较低的查准率,因为我们预测患有癌症的病人比例越大,那么就有较大比例的人其实没有患癌症。

临界值的选取

当你改变临界值的值时,你可以画出曲线来权衡查准率和召回率,如上图右
取一个较高的临界值,这个临界值可能等于0.99,我们假设 只在有大于99%的确信度的情况下,才预测y=1。至少,有99%的可能性。因此这个点反应高查准率低召回率。
取一个较低的临界值,比如说0.01,毫无疑问,在这里预测y=1,如果你这么做,你最后会得到低查准率高的召回率的预测结果。

权衡不同算法的查准率和召回率(F值)

假设我们有三个不同的学习算法;或者这三个不同的学习曲线是同样的算法,但临界值不同。我们怎样决定哪一个算法是最好的?
F值

我们不用平均值而用F值来评估算法
如果用平均值来判定,明显算法3更高,但实际上算法3总是预测y=1这并不是一个好的模型。所以我们采用F值来判定,上图给出F值计算公式,根据F值,我们更倾向于算法1,F值取值范围一般在0~1之间。


机器学习的数据

作者建议不要一开始花大量时间来收集数据,这只能在某些条件下起作用。但是在满足一定条件下,通过大量的数据,在某种类型的学习算法中训练,确实能得到满意的效果。 这似乎是一个矛盾的结果?那需要满足什么条件呢???

作者这里给出了一个混淆词分类的例子
混淆词分类

即使是不同的算法,从图中可以也看出趋势非常明显。首先大部分算法都具有相似的性能,其次随着训练数据集的增大,这些算法的准确性也都对应的增强了。
这些结果表明,许多不同的学习算法有时倾向于表现出非常相似的效果,虽然这些效果的表现还取决于一些细节,但是真正能提高算法性能(准确度)的,就是你能够给到一个算法的大量的训练数据。类似这样的结论引起了一种在机器学习中的普遍共识。

那么?什么情况下获取大量的数据是提高算法性能的好方法呢???
在特征值x包含足够多的用来准确预测y的信息时,获取大量的数据是提高算法性能的好方法。
例如在上面介绍的混淆词的例子中:

For breakfast I ate __ eggs.

空白词附近的词就是我们需要捕捉的特征x,这些词中包含了大量的信息来告诉我空白处应该填写two而不是to或者too。实际上对于特征捕捉,哪怕是周围词语中的一个词,就能够给我足够的信息来确定出标签y是什么了。这就是通过一个有充足的信息的特征值x的来确定y的例子。

举一个反例:
设想在房屋价格预测问题中,我们获取的房屋信息中只有房屋面积信息,没有其他的特征值,那么如果我告诉你这个房子有500平方英尺,但是我没有告诉你其他的特征信息,我也不告诉你这个房子位于这个城市房价比较昂贵的区域还是便宜的区域,也不告诉你这所房子的房间数量,它里面陈设了多漂亮的家具,以及这个房子是新的还是旧的。我不告诉你除了这个房子有500平方英尺以外的其他任何信息,然而除此之外还有许多其他因素会影响房子的价格,不仅仅是房子的大小。但如果你仅仅知道房屋的尺寸,那么事实上是很难准确预测它的价格的。

2011-06-27 17:34:00 blueking109 阅读数 396

定义:不论是硬件临界资源,还是软件临界资源,多个线程必须互斥地对它进行访问。每个线程中访问临界资源的那段代码称为临界区(Critical Section)

 

 

每个线程中访问临界资源的那段程序称为临界区(Critical Section)(临界资源是一次仅允许一个线程使用的共享资源)。每次只准许一个线程进入临界区,进入后不允许其他线程进入。不论是硬件临界资源,还是软件临界资源,多个线程必须互斥地对它进行访问。

  多个线程中涉及到同一个临界资源的临界区称为相关临界区。   线程进入临界区的调度原则是: ①如果有若干线程要求进入空闲的临界区,一次仅允许一个线程进入。②任何时候,处于临界区内的线程不可多于一个。如已有线程进入自己的临界区,则其它所有 试图进入临界区的线程必须等待。③进入临界区的线程要在有限时间内退出,以便其它线程能及时进入自己的临界区。④如果线程不能进入自己的临界区,则应让出 CPU,避免线程出现“忙等”现象。   如果有多个线程试图同时访问临界区,那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起,并一直持续到进入临界区的线程离开。临界区在被释放后,其他线程可以继续抢占,并以此达到用原子方式操作共享资源的目的。

 

                                                             ----摘自百度百科

1.工作中遇到的问题: 同一个类A中有多处同时使用同一个临界区, 即会出现如下情况时

  FuncA()

      | enter---------------FuncB----------------leave

  FuncB()

      |-----------enter-----------------------------------------leave

  如果是一个线程调用FuncA后,另一个线程调用FuncB 则此时发生资源互斥,导致调用FuncB的线程无期限等待,造成未响应

  但如果是同一个线程调用FuncA后 又调用FucnB 则正常执行

  解绝外部线程调用FuncB的方法

  使用windows msg: SendMessage,PostMessage,  在类A的消息处理函数中调用FuncB

 

 

2017-06-15 09:11:53 swee111 阅读数 162

临界段代码的定义

临界段代码,也称作临界域,是一段不可分割的代码。uC/OS-III中包含了很多临界段代码。如果临界段可能被中断,那么就需要关中断以保护临界段。如果临界段可能被任务级代码打断,那么需要锁调度器保护临界段。uC/OS-III 中的临界段的保护方法决定于ISR 中对消息的处理方式。详见 “ 中断管理” 。如果OS_CFG_ISR_POST_DEFERRED_EN 被设为0(见OS_CFG.H),在进入临界段之前uC/OS-III 会关中断,在离开临界段之后开中断。如果OS_CFG_ISR_POST_DEFERRED_EN 被设为1,在进入大多数临界段之前会关调度器。

uC/OS-III 定义了一个进入临界段的宏和两个出临界段的宏。

OS_CRITICAL_ENTER(),

OS_CRITICAL_EXIT(),

OS_CRITICAL_EXIT_NO_SCHED()

这些是uC/OS-III 的内部宏,不能被用户代码调用。然而,如果你需要进入你自己定义的临界段。请查阅"资源管理"。

一:关中断

1.在上面我们说过的,当OS_CFG_ISR_POST_DEFERRED_EN 被设为0,在进入临界段之前uC/OS-III 会关中断,在离开临界段之后开中断。OS_CRITICAL_ENTER() 调用uC/CPU 的宏CPU_CRITICAL_ENTER() , 然后调用CPU_SR_Save() 。CPU_SR_Save()是用汇编写的用于保存当前CPU 寄存器并关中断。寄存器值以类型为“cpu_sr”的变量存于调用者堆栈。

OS_CRITICAL_EXIT() 和OS_CRITICAL_EXIT_NO_SCHED() 都会调用uC/CPU 的宏CPU_CRITICAL_EXIT() 。CPU_CRITICAL_EXIT()调用CPU_SR_Restore()。CPU_SR_Restore()恢复所保存寄存器值到CPU 寄存器,也就是OS_CRITICAL_ENTER()调用前的状态。如下:

#define  OS_CRITICAL_ENTER()                    CPU_CRITICAL_ENTER()
#define  OS_CRITICAL_ENTER_CPU_EXIT()
#define  OS_CRITICAL_EXIT()                     CPU_CRITICAL_EXIT()
#define  OS_CRITICAL_EXIT_NO_SCHED()            CPU_CRITICAL_EXIT()

2.测量关中断的时间

uC/CPU 提供了测量关中断时间的功能。通过设置CPU_CFG.H 中的CPU_CFG_TIME_MEAS_INT_DIS_EN (CPU_configure_time_measure_intrrupt_distance_enable其实是很好记的)为1 启用该功能。每次关中断前开始测量,开中断后结束测量。每个任务的关中断时间在上文保存的时候被保存于OS_TCB(详见OS_CPU.C 中的OSTaskSwHook()和第八章"上下文切换")

二:锁住调度器

1.当设置OS_CFG_ISR_POST_DEFERRED_EN 为1 时,在进入临界段前uC/OS-III 会锁住调度器,退出临界段后开启调度器。OS_CRITICAL_ENTER()递增OSSchedLockNestingCtr,给调度器加锁。这是一个决定调度器是否被开启的变量。如果它不为0 则调度器被锁。{称它为调度器锁嵌套值,表示调度器被加了几把锁}

OS_CRITICAL_EXIT()将OSSchedLockNestingCtr 递减,给调度器解锁。{调度器锁嵌套值被减为0 时,就会调用调度器}
OS_CRITICAL_EXIT_NO_SCHED() 也递减OSSchedLockNestingCtr 的值,不同的是当其值减为0 时,不调用调度器。

2.测量锁调度器时间uC/OS-III 提供了测量锁调度器时间的功能,通过设置OS_CFG.H中的OS_CFG_SCHED_LOCK_TIME_MEAS_EN 为1 开启。加锁调度器前测量开始,解锁调度器后测量结束。测得的两种值为:总的锁调度器时间,每个任务的锁调度器时间。因此,用户可以知道每个任务的锁调度器时间,并根据此优化代码。

三.uC/OS-III与长临界段

了解

四.总结
uC/OS-III 中会用到临界段, 用关中断(OS_CFG.H 中设置OS_CFG_ISR_POST_DEFERRED_EN 为0) 或者锁调度器( 设置OS_CFG_ISR_POST_DEFERRED_EN 为1)实现保护临界段的功能。用户程序不能使用这些代码:
OS_CRITICAL_ENTER()
OS_CRITICAL_EXIT()
OS_CRITICAL_EXIT_NO_SCHED()
如果设置了CPU_CFG.H 中的CPU_CFG_TIME_MEAS_INT_DIS_EN 为1 时。uC/CPU 将会任务总的关中断时间和每个任务的关中断时间。

如果设置了OS_CFG.H 中的OS_CFG_SCHED_LOCK_TIME_MEAS_EN 为1 时。uC/OS-III 会测量任务总的锁调度器时间和每个任务锁调度器时间。



临界区管理

阅读数 90

临界资源 & 临界区

阅读数 1194

没有更多推荐了,返回首页