Redian新闻
>
开创性CVM算法破解40多年计数难题!计算机科学家掷硬币算出「哈姆雷特」独特单词

开创性CVM算法破解40多年计数难题!计算机科学家掷硬币算出「哈姆雷特」独特单词

公众号新闻



  新智元报道  

编辑:桃子
【新智元导读】预估一个数组中不重复数字的个数,最简便的方法是什么?计算机科学家们提出了一种全新CVM算法,通过利用随机性,预估出数据流中大量不同的对象。

计数,听起来简单,却在实际执行很有难度。

想象一下,你被送到一片原始热带雨林,进行野生动物普查。每当看到一只动物,拍一张照片。

数码相机只是记录追踪动物总数,但你对独特动物的数量感兴趣,却没有统计。

那么,若想获取这一独特动物数量,最好的方法是什么?

这时,你一定会说,从现在开始计数,最后再从照片中将每一种新物种与名单进行比较。

然而,这种常见的计数方法,有时并不适用于高达数十亿条目的信息量。

来自印度统计研究所、UNL、新加坡国立大学的计算机科学家提出了一种新算法——CVM。

它可以近似计算长列表中,不同条目的的数量,而且只需要记住少量条目就可实现。

论文地址:https://arxiv.org/pdf/2301.10191

这一算法适用于任何一次出现一个条目的清单,比如演讲中的文字、传送带上的商品,或州际公路上的汽车。

CVM算法是以三位作者首字母命名,在解决「不同元素问题」上取得的一个重大进展。

而这一问题,长期困扰计算机科学家40多年。

它要求有一种高效的方法来监控一个元素流(其总数可能超过可用内存),并估算出其中独特元素的数量。

那么,CVM算法究竟是如何解决问题的?

开创性CVM算法,秘诀在于「随机化」


假设你在听《哈姆雷特》有声读物。

这部戏剧共有30557个字,有多少是不同的?

为了找到答案,你可以边听边暂停,按字母顺序写下每个单词,然后跳过清单上已有的单词,最后,只需要数一下清单上每个单词数。

这种方法是可行的,但太考验一个人的「记忆量」了。

研究者Vinodchandran Variyam表示,「在典型的数据流情况中,可能会有数百万个项目需要追踪。你可能不想把所有的信息都存储起来。

这就是,云服务器算法可以提供更简单方法的地方」。

诀窍,就在于「随机化」。

Vinodchandran Variyam帮助发明了一种估算数据流中不同元素数量的CVM算法

「哈姆雷特」有多少个独特词?掷硬币大挑战


再回到《哈姆雷特》,假设你的「有效内存」只能容纳100个单词。

一旦音频开始播放,你记下听到的前100个单词,并跳过任何重复的单词。

当完成100个单词记录后,剩下的就是为每个单词掷硬币——

正面,保留单词。若为反面,将其删除。

在这一轮初选之后,你将留下大约50个不同的单词。

现在,你继续团队所说的第一轮游戏Round 1,继续阅读《哈姆雷特》,添加新单词。

如果你再次遇到一个已经在清单上的单词,再次掷硬币决定,一直到你的内存白板中,有100个单词。

然后,根据100次掷硬币的结果,再次随机删除大约一半的单词。Round 1到此结束。

接下来,进入第二轮Round 2。

和第一轮一样,我们要增加一个单词的难度——当你遇到一个重复的单词时,再次掷硬币。

条件是,如果是反面,就像之前一样删除它。但如果是正面,就再掷一次硬币。只有当第二次出现正面时,才保留这个单词。

一旦内存白板写满,结束这一轮,然后根据100次抛掷结果,再次删除大约一半的单词。

在第三轮Round 3中,你需要连续三次掷硬币正面,才能保留一个单词。

在第四轮中,连续四次正面保留一个单词,以此类推。

最终,在第k轮,你会听完整部《哈姆雷特》戏剧。

这个练习的重点是,确保每个单词都有相同的出现概率:1/2 (k) 。

假设,如果在《哈姆雷特》音频结束时,你的列表中有61个单词,用了六轮的时间完成。

你可以用61除以概率1/2 (6)来估计不同单词的数量——最终在这个游戏中的结果是3904个。

算法精度与内存量成正比


研究人员Chakraborty、Variyam和Meel从数学上证明了CVM算法的精确度与内存量的大小成比例。

而《哈姆雷特》恰好有3967个独特的单词。(通过普通的计数方法)

在使用100个单词内存的实验中,5轮实验结果的平均估计为3955个单词。

在1000个单词内存忆量下,平均提高到3964个。

Variyam表示,「如果(内存量)大到可以容纳所有单词,那么我们就可以达到100%的准确率」。

哈佛大学William Kuszmau表示,「这是一个很好的例子,说明即使是非常基础和被广泛研究过的问题,有时也可能存在简单但并不明显的解决方案仍待被发现」。

参考资料:
https://www.quantamagazine.org/computer-scientists-invent-an-efficient-new-way-to-count-20240516/




微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。
相关阅读
澳洲录取来了!恭喜学员斩获QS排名19的悉尼大学计算机科学硕士OFFER!描写江南最好的诗词大模型时代的计算机视觉!CVPR 2024线上论文分享会启动2024 CSRankings全美计算机科学排名发布!CMU霸榜,MIT跌出前5众多IT巨头都无法解决的“计算机科学最大难题”CS留学参考!CSRankings全球计算机科学排名(2024更新版)CVPR 2024 | 李飞飞和吴佳俊团队新作「BVS」套件评估计算机视觉模型[录取捷报]波士顿大学 计算机科学硕士录取 来啦!美股基本面 - 2024_03_23 * 晨报 * 51Talk去年净亏损缩窄至1400万美元,预计今年一季度净收入增逾四成。4K图像理解轻松拿捏!IXC2-4KHD:开创性的大型视觉语言模型!计算机科学里最大的难题:居中显示毕业生薪资高达97万!恭喜学员斩获斯坦福大学王牌专业——计算机科学硕士项目!Kidney Int|重塑肾移植未来:CAR-T细胞疗法破冰难配型与高敏排斥谷歌数学版Gemini破解奥赛难题,堪比人类数学家!寄居蟹的家 (Hermit Crabs' Home)Tech Goes Home推出开创性的倡导社区奖学金计划神还原《哈姆雷特1964》,给老师和弗林都贡献了绝佳演技《老无所依》深度赏析五:真枪实弹 人类无效沟通实录「哈利·波特」来啦!耗时3年,400万名游戏玩家终于联手打败了最先进的计算机算法死亡率高!生牛奶首次测出「浓度极高」的禽流感病毒!科学家发警告!要当心了!申请吸引力增强?英伟达和佐治亚理工学院推出「AI超级计算机中心」,真“遥遥领先”了!清明AX美高补录捷报|康州Pomfret School庞弗雷特中学补录+1招聘量下降67%!计算机专业跌落神坛,留学生选专业的下一个风口是?刚刚!全球首例猪肾移植患者死亡!基因编辑依旧无法破除活不过两月魔咒?2024 QS排名发布!计算机MIT霸榜,清华11,北大15「量子大军」出动,中国实验室破解世界级算法难题!MRD码微秒级加密防窃听,6G无人机爆炸性飞跃大模型时代的计算机视觉!CVPR 2024线上分享会全日程公布计算机学霸4.0gpa+逆天实习,TOP25UMich顶级电气与计算机工程项目易如反掌!顶刊TPAMI 2024!计算机学会像人脑一样“听话”了!清华苑克鑫/胡晓林团队实现混合语音分离技术突破!CS专业选校重要参考!CSRankings全球计算机科学排名(2024更新版)陶哲轩转赞!40多年「忙碌海狸」数学难题获突破,4万行Coq代码立大功北京、南京还有海边的阿那亚,我们都可以走进《哈姆雷特》的排练厅CS专业留学重要参考!CSRankings全球计算机科学排名(2024更新版)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。