随机样本上的最优分类器

KeyTo9_Fans

假设有$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$都成立？

王守恩

通项公式是这样的？
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,}

王守恩

前面部分
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

mathe

对于每个序列，我们可以转化为一个坐标上的折线图，从原点(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