找回密码
 欢迎注册
查看: 9486|回复: 4

[原创] 随机样本上的最优分类器

[复制链接]
发表于 2021-7-17 20:01:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
假设有$n$个样本排成一列,每个样本都有一个标签,

标签只有$2$种:正和负。

在揭开每个样本的标签之前,这些标签都是完全随机的,

也就是正和负的概率各为$1/2$且相互独立。

在揭开每个样本的标签之后,我们需要对这列样本进行简单粗暴的分类,

也就是划定一条分界线,分界线左边的样本一律分为负类,分界线右边的样本一律分为正类。

我们选定的这条分界线,是$(n+1)$条可能的分界线中,分错数目最少或者是并列最少的那条分界线。

我们将这条最优分界线的分错数目记为随机变量$X$。

问$2^n*X$的期望值是多少?

#####

为了把这个期望值算出来,

我们可以将$2^n$种可能的样本标签逐一讨论一遍,

然后把每种可能的样本标签的最少分错数加起来即可。

例如,我们用 “|” 表示分界线,

当$n=1$时,$2$种可能的样本标签的最优分类方案如下:

分类方案 分错数目
负|         0
|正         0

每种分错数目加起来,得到$2^n*X$的期望值为$0$。

当$n=2$时,$4$种可能的样本标签的最优分类方案如下:

分类方案 分错数目
负负|       0
负|正       0
|正负       1
|正正       0

每种分错数目加起来,得到$2^n*X$的期望值为$1$。

当$n=3$时,$8$种可能的样本标签的最优分类方案如下:

分类方案 分错数目
负负负|     0
负负|正     0
负|正负     1
负|正正     0
正负负|     1
正负|正     1
|正正负     1
|正正正     0

每种分错数目加起来,得到$2^n*X$的期望值为$4$。

当$n=4$时,$16$种可能的样本标签的最优分类方案如下:

分类方案 分错数目
负负负负|     0
负负负|正     0
负负|正负     1
负负|正正     0
负正负负|     1
负|正负正     1
负|正正负     1
负|正正正     0
正负负负|     1
正负负|正     1
|正负正负     2
正负|正正     1
|正正负负     2
|正正负正     1
|正正正负     1
|正正正正     0

每种分错数目加起来,得到$2^n*X$的期望值为$13$。

对于更大的$n$,可以编程序来计算上述期望值,结果如下:

  1. 0: 0
  2. 1: 0
  3. 2: 1
  4. 3: 4
  5. 4: 13
  6. 5: 36
  7. 6: 94
  8. 7: 232
  9. 8: 557
  10. 9: 1300
  11. 10: 2986
  12. 11: 6744
  13. 12: 15074
  14. 13: 33320
  15. 14: 73116
  16. 15: 159184
  17. 16: 344701
  18. 17: 742068
  19. 18: 1590898
  20. 19: 3395320
  21. 20: 7222550
  22. 21: 15308920
  23. 22: 32362276
  24. 23: 68213424
  25. 24: 143463378
  26. 25: 300999816
  27. 26: 630353764
  28. 27: 1317415792
  29. 28: 2748991012
  30. 29: 5726300880
  31. 30: 11911913912
  32. 31: 24742452128
  33. 32: 51331847709
复制代码


本以为我们发现了一个新数列,可惜oeis上已经有这个数列了:

http://oeis.org/A206603

0, 0, 1, 4, 13, 36, 94, 232, 557, 1300, 2986, 6744, 15074, 33320, 73116, 159184, 344701, 742068, 1590898, 3395320, 7222550, 15308920, 32362276, 68213424, 143463378, 300999816, 630353764, 1317415792, 2748991012, 5726300880, 11911913912, 24742452128, 51331847709

经比对,前$32$项是完全相同的。

但奇怪的是,oeis的定义和我们的定义完全不同。

以$n=6$为例,oeis的定义如下:

在$[-n/2,n/2]$区间里以$1$为间隔,取出$(n+1)$个数“$-3$、$-2$、$-1$、$0$、$1$、$2$、$3$”,

然后把它们按照中间大两边小的方式排成一列:

-3 -1 1 3 2 0 -2

然后对相邻两个数求和,得到下一行,并重复这个过程,直到只剩$1$个数:

-3 -1 1 3 2 0 -2
  -4 0 4 5 2 -2
   -4 4 9 7 0
    0 13 16 7
    13 29 23
      42 52
        94

最后这个数$94$就是$n=6$时的$a(n)$值。

奇怪的是,在$n=6$个随机样本上构建最优分类器,分错的样本数的期望值乘以$2^n$之后也是$94$。

而且这个结果对$n=0$到$n=32$都成立。

所以我很好奇为啥定义差别这么大的两个数列,前$32$项竟然会完全一样。

有没有高人可以一起来证明一下,这个结果对所有的非负整数$n$都成立?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-18 20:46:43 | 显示全部楼层
本帖最后由 王守恩 于 2021-7-19 05:24 编辑

通项公式是这样的?
RecurrenceTable[{a[0] = 0,  a[n] = 2a[n - 1] + 2^n - n!/(Floor[n/2]! (n - Floor[n/2])!)}, a, {n, 0, 32}]
{0, 1, 4, 13, 36, 94, 232, 557, 1300, 2986, 6744, 15074, 33320, 73116, 159184, 344701, 742068,
  1590898, 3395320, 7222550, 15308920, 32362276, 68213424, 143463378, 300999816, 630353764,
  1317415792, 2748991012, 5726300880, 11911913912, 24742452128, 51331847709, 106357582324,}

点评

是这个通项公式没错。现在要证明“三角和”的通项公式和“分错数目”的通项公式都是这个。  发表于 2021-7-18 23:52
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-21 12:55:29 | 显示全部楼层
本帖最后由 王守恩 于 2021-7-21 17:00 编辑

前面部分
1×0=0
2×0=0
3×0+01×1=1
4×0+04×1=4
5×0+09×1+002×2=13
6×0+16×1+010×2=36
7×0+25×1+027×2+05×3=94
8×0+36×1+056×2+28×3=232
9×0+49×1+100×2+84×3+14×4=557

后面部分
-1*0 = 0
-1*1 + 1*1 = 0
-1*0 + 2*2  - 01*2 = 2
-1*1 + 3*3 + 03*1  - 01*3 = 8
-1*2 + 4*2 + 06*4 + 04*0  - 001*4 = 26
-1*3 + 5*1 + 10*5 + 10*3  - 005*1  - 001*5 = 72
-1*4 + 6*0 + 15*4 + 20*6 + 015*2  - 006*2  - 01*6 = 188
-1*5  - 7*1 + 21*3 + 35*7 + 035*5 + 021*1  - 07*3 - 01*7 = 464
-1*6  - 8*2 + 28*2 + 56*6 + 070*8 + 056*4 + 28*0 - 08*4 - 1*8 = 1114
-1*7  - 9*3 + 36*1 + 84*5 + 126*9 + 126*7 + 84*3 - 36*1 - 9*5  - 1*9 = 2600
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-7-21 16:21:10 | 显示全部楼层
对于每个序列,我们可以转化为一个坐标上的折线图,从原点(0,0)出发,每遇到一个符号,横坐标加一,而如果遇到的是正,纵坐标加一,遇到负数,纵坐标减一。
比如对于序列”负正负负正“,可以转化为折线图
(0,0)->(1,-1)->(2,0)->(3,-1)->(4,-2)->(5,-1)
而转化以后可以得到一个比较简单的结论,分界线应该标记在最小值点,比如上面的结果对应(4,-2),也就是划分为”负正负负|正“。如果有多个最小值,那么不论取哪个最小值作为分界线,结果是相等(我们可以限定总是取第一个)。而且这个分类错误的数目只跟最小值和结束点的位置相关。于是我们转化为对给定最小值和最总值以后的计数问题。
于是唯一的问题就是给定长度为n的序列,一直上面结束点纵坐标为s(s必然和n同奇偶), 最小值点坐标为(p,-m)
我们需要统计这种情况的折线数目。其中前面部分需要求(0,0)到(p,-m)的折线数目,其中折线中间所有点的总坐标会大于-m。同样后面部分是从(p,-m)到(n,s)的折线数目,其中每个点的纵坐标都不小于-m。
而这个计算问题是一个已经解决的问题,就是比赛中分数一路领先的计数问题。
比如 http://b014.hchs.hc.edu.tw/ezfiles/14/1014/img/161/100195181.pdf

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
KeyTo9_Fans + 3 + 3 + 3 + 3 + 3 非常棒,这样就找到了分类器问题的递推公式

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 07:24 , Processed in 0.045634 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表