文章/答案/技术大牛

发布

社区首页 >问答首页 >超立方体顶点的不可分赋值

问超立方体顶点的不可分赋值
EN

Data Science用户

提问于 2019-06-06 20:32:04

回答 1查看 117关注 0票数 1

在曼宁等人的“信息检索导论”中，我有一个关于练习14.17的问题。

问题是：

“假设两个类，表明当M>1时，超立方体顶点不可分离赋值的百分比随着维数M的增加而减小。例如，对于M=1时，不可分离赋值的比例为0，对于M= 2，则为2/16。通过解析或仿真解决这个问题。”

N维超立方体的顶点赋值总数为：2^{(2^N)}。

正如我在这里中所发现的，可分离赋值的数目是O(2^{(N^2)})。因此，不可分离作业的百分比随着N的增加而增加(这与练习中所说的相反)。

我在这里错过了什么？

classification

machine-learning

回答 1

Data Science用户

发布于 2019-06-28 20:46:28

你似乎是对的。我相信这很简单地证明了相反的事实：

设s(n)表示n-cube中可分集的数目。设Q_0, Q_1表示一个较小维的子立方体，假设最后一个坐标分别等于0，1。关键的事实是，整个立方体的任何可分集都在可分集中与每个Q_0, Q_1相交。(分离超平面与馀维-1空间相交，形成分离超平面。)所以

s(n)\leq [s(n-1)]^2.

现在的比例r(n)满足

r(n)= \frac{s(n)}{2^{2^n}}\leq \frac{[s(n-1)]^2}{(2^{2^{n-1}})^2}= [r(n-1)]^2< r(n-1),

其中最后一个不等式仍然有效，因为r(n-1)<1 for n>2。

票数 0

页面原文内容由Data Science提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://datascience.stackexchange.com/questions/53358

复制

相似问题

问超立方体顶点的不可分赋值
EN

回答 1

Data Science用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问超立方体顶点的不可分赋值EN

回答 1

Data Science用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问超立方体顶点的不可分赋值
EN