首页时事民生政务教育文化科技财富体娱健康情感

旅行百科职场楼市企业乐活学术汽车时尚创业美食幽默美体文摘

2023计算机科学7项重大突破！「P与NP」50年经典难题，大模型密集涌现上榜

文摘 2023-12-25 10:43 澳大利亚

来源||新智元

【导读】2023年，计算机领域都发生了哪些大事？Quanta Magazine的年终盘点来了。

一年一度的年终盘点来了！

2023年，计算机科学领域大事件人人都能脱口而出，火遍全网的ChatGPT一系列大模型、AI作画神器Midjourney，AI视频生成Gen-2、Pika飞速迭代......

在「P与NP」最经典的问题上，研究人员取得了微妙但重要的进展。

秀尔算法（Shor’s algorithm），量子计算的杀手级应用程序，在近30年后进行了首次重大升级。还有研究人员终于学会了如何在理论上通过一种普通类型的网络，以最快速度找到最短路径。

此外，加密学家在与AI建立意想不到的连接时，展示了机器学习模型和机器生成内容也必须应对隐藏的漏洞和消息。

Top 1：50年P与NP难题，「元复杂性」理论开路

50年来，计算机科学家一直试图解决所在领域中最大，且悬而未决的问题，即「P与NP」。

简单讲，「P与NP」就是探讨已知的困难的计算问题，具体有多难，是否存在更高效的算法。

但是，50年来想要解决这个问题的科学家们，都以失败而告终。

就在许多科学家感觉快要有突破的时候，总是会遇到无法跨越的障碍，证明他们的方法行不通。

久而久之，科学家开始质疑，为什么就连证明一个问题「很难」本身也这么困难。

在回答这类内省式问题的努力中，出现了一个新兴的领域「元复杂性」（meta-complexity）理论。它为这个问题提供了迄今为止最好的见解。

8月，Quanta一篇文章中曾介绍了「元复杂性」的理念，以及科学家们开始的探索。

三位数学家对数学推理的局限性不同看法

「P与NP」问题破解，能够解决无数日志问题，使所有密码学毫无意义，甚至揭示人类能够知晓的事物的本质。

简单来说，P是那些可以轻松解决的问题，比如按字母顺序排列。NP是那些解决方案易于检查的问题，如数独。

由于所有易于解决的问题也易于检查，所以P中的问题也属于NP。

但有些NP问题似乎很难解决，你无法在不先尝试许多可能性的情况下直观地得出数独难题的解决方案。

通过研究这些内省式问题，研究人员了解到，证明计算难度的困难程度，与乍看起来似无关的基本问题密切相关。

在明显随机的数据中发现隐藏的模式有多难？如果确实存在真正困难的问题，那么这些问题多久会出现一次？

德克萨斯大学奥斯汀分校的复杂性理论家Scott Aaronson表示，「很明显，元复杂性与事物的核心关系密切」。

「P与NP」问题引领研究人员进入「元复杂性」理论艰难的旅程。

然而对于「元复杂性」的研究人员来说，这段在未知领域的旅程就是它自身的回报。

Top 2：大模型涌现，黑盒谁能打开

涌现，可以成为大模型领域年度热词。

OpenAI团队曾在2022年一篇论文中，给「涌现」下了一个定义：

在参数规模较小的模型中不存在，在规模较大的模型中存在，那么这种能力就是涌现。

比如，你给大模型几个表情包，然后询问这代表着什么电影？LLM会根据已有的知识，去预测下一个token，最后给出答案。

答案：海底总动员

不仅如此，小模型无法完成的任务，其中许多似乎与分析文本没有什么关系，从乘法到生成可执行的计算机代码，再到显然基于表情符号对电影进行解码。

OpenAI这项研究也表明，对于一些任务和一些模型，存在一个复杂性阈值，超过这个阈值，模型的能力会迅速增长。

但是，不得不承认，随着LLM能力不断增长，引发了新的担忧。

这些强大的AI系统不仅编造谎言，制造社会偏见，甚至连人类语言中一些最基本的元素都无法处理。

最重要的是，这些AI仍旧是一个黑盒，内部推理逻辑无法得知。

不过，在打开AI「黑盒」上的研究也在不断涌现。比如，OpenAI团队用GPT-4去解释30万个GPT-2神经元，甚至在最新研究中提出用GPT-2监督GPT-4。

总而言之，揭开大模型内部运作机制还有很长的路要走。

Top 3：40年前算法，找到最短路径

计算机科学家很早就知道，可以快速遍历图网络的算法（由边连接的节点网络），而且其中的连接是有一定成本的，比如连接两个城市的收费公路。

但几十年来，如果只考虑一条路的成本和回报，科学家找不到任何快速算法来确定最短路径。

去年年底，来自罗格斯大学的3位研究人员提出了一种可行的算法。

他们的新算法找到了从一个给定的「源」节点到每一个其他节点的图中的最短路径，几乎赶上了很久以前正权重算法所达到的速度。

论文地址：https://arxiv.org/abs/2203.03456

值得一提的是，Dijkstra这一算法早在1956年，是由荷兰计算机科学家Edsger Dijkstra开发的快速算法，可以在只有正权的图上找到最短路径。

对此，研究人员反转思路，给出了负权图的最短路径算法。

今年3月，芝加哥大学的华人计算机科学家Xiaorui Sun提出了一种更快的算法，以更快的速度打破了群同构问题中最难解决的实例。

论文地址：https://arxiv.org/abs/2303.15412

它可以精确地确定两种被称为组的数学对象何时相同。

此外，今年的其他重大算法新闻还包括，通过结合随机和确定性方法计算素数的新方法，反驳了一个关于信息有限算法性能的长期猜想。

以及一项分析，展示了一个非直观的想法如何提高渐降算法的性能，梯度下降算法在机器学习程序和其他领域中随处可见。

Top 4：AI生图爆火，背后技术沉淀多年

今年，DALL·E、Midjourney、Stable Diffusion等图像生成工具，深受人们欢迎。

只需给一个文字提示，AI就可以按照你的要求创作出一幅艺术作品。

不过，这些AI艺术家背后的技术，其实早已经历了多年的积累——

扩散模型（diffusion models）基于的是物理学中流体扩散的原理，它们能有效地把模糊的噪声转换为清晰的图形——就好比将咖啡中混合均匀的奶油再次分离出来，恢复成清晰的形状。

此外，AI工具在提高现有图像的清晰度方面也取得了进展，虽然这距离电视剧中警察反复大喊「增强！」的场景还有很长的路要走。

最近，研究人员开始研究扩散以外的其他物理过程，来寻找机器生成图像的新方法。

其中一种新的方法是基于泊松方程（Poisson equation）——用于描述电场力随距离变化的过程。这种方法已经证明在处理错误方面更加高效，并且在某些情况下比扩散模型更容易训练。

Top 5：30年后，量子因数分解运算速度飙升

几十年来，秀尔算法（Shor’s algorithm）一直被视为量子计算机强大能力的象征。

这套由Peter Shor在1994年开发的算法，让量子计算机能够利用其量子物理特性，比经典计算机更快地将大数分解为质因数。而这对目前大部分的互联网安全系统，构成了潜在威胁。

2023年8月，一位计算机科学家开发出了一个更快的Shor算法变体，这是自该算法被发明以来的首次重大改进。

尽管如此，真正实用的量子计算机仍然遥不可及。

在实际应用中，微小的误差会迅速累积，从而破坏计算结果，并进一步消除了量子计算带来的所有优势。

事实上，去年年底，一组计算机科学家的研究表明，对于一个特定的问题，经典算法与包含误差的量子算法大致相同。

但希望还是有的：8月的研究显示，某些纠错码（称为低密度奇偶校验码）的效率，至少是现行标准的10倍。

Top 6：密码学+AI的隐藏秘密

在密码学和人工智能交叉领域的一项不寻常研究中。

最近，一组计算机科学家证明了可以在机器学习模型中嵌入后门，这些后门不仅几乎无法被发现，而且它们的隐蔽性得到了类似于现代最先进加密技术的逻辑支持。

不过，团队主要研究的是较简单的模型，因此目前还不清楚这一发现是否也适用于当今AI技术中使用的更复杂的模型。

然而，这些研究成果为未来系统如何防御这类安全漏洞提供了可能的方向。

正是因为这类安全问题，Cynthia Rudin强烈推荐使用可解释的模型，来更深入地了解机器学习算法内部的运作机制。

与此同时，像Yael Tauman Kalai这样的研究人员，也在安全性和隐私领域取得了进展，而这对即将到来的量子技术来说极为重要。

而在隐写术这一相关领域，研究成果展示了如何在机器生成的媒体中以绝对安全的方式隐藏信息。

Top 7：向量注入语义，让LLM推理更高效

尽管人工智能已经非常强大，但支撑大多数现代系统的人工神经网络存在两大问题：

1. 在训练和运行时需要消耗大量资源

2. 容易变成难以理解的「黑箱」

因此，很多研究人员都认为，现在或许是采取新方法的时候了——

通过成千上万的超维向量来表现概念，而不是用人工神经元来检测单个特征或特性。

这种系统用途更广，处理错误的能力更强，计算效率也高得多。

而且，研究人员还可以直接操作模型所考虑的想法和关系，从而更深入地了解它的推理过程。

今年3月，苏黎世IBM研究院的团队，使用带有神经网络的超维计算来解决抽象视觉推理中的一个经典问题——「瑞文的递进矩阵」。

它将几何对象的图像呈现在一个3x3的网格中。网格中的一个位置为空，对象必须从一组候选图像中选择最适合空白的图像。

为了使用超维计算解决这个问题，该团队首先创建了一个超向量字典来表示每幅图像中的对象。

字典中的每个超向量代表一个对象及其属性的某种组合。

然后，该团队训练神经网络来检查图像并生成一个双极超向量，一个元素可以是+1或−1，它尽可能接近字典中超向量的某种叠加。

因此，生成的超向量包含关于图像中所有对象及其属性的信息。

他们提出的方法在一组问题上的准确率接近88%，而仅使用神经网络的解决方案的准确率不到61%。

目前超维计算尚处于初期阶段，但随着其在更大规模的测试中的应用，我们可能会看到这种新方法开始展现其潜力。

参考资料：

https://www.quantamagazine.org/the-biggest-discoveries-in-computer-science-in-2023-20231220/

深度强化学习实验室

【开源开放、共享共进】强化学习社区\x26amp;实验室，分享推动DeepRL技术落地与社区发展，社区 deeprlhub.com

最新文章

NeurIPS 2024 | DACER：扩散模型与在线强化学习强强联合创造新SOTA！

清华团队提出RL专用神经网络优化器，性能位居榜首

【第二弹】强化微调，用少量样本训练专家模型

【清华大学】当鲁棒控制遇到强化学习：零和博弈视角的非线性拓展

【重磅】阿尔伯塔大学提出“Stream-X”强化学习新范式，无需经验重放、目标网络或批量更新。

强化学习之父Sutton万字采访：炮轰深度学习只是瞬时学习，持续学习才是智能突破的关键

开放式物理RL环境空间，智能体零样本解决未见过人类设计环境！

控制系统可控性检验理论的变革：从模型驱动到数据驱动

【图灵奖得主Yoshua Bengio】提出强化学习新策略，解决策略KL正则化漏洞问题。

【NeurlPS2024分享】北航提出“结构信息原理指导的高效智能体探索”(末尾附开源代码)

【Nature重磅】AlphaChip，谷歌用强化学习设计多代TPU芯片速度超越人类，开源预训练代码

【清华北大腾讯等】联合综述OpenAI o1背后的自博弈(Self-Play)方法原理与技术细节

【重磅发布】OpenAI o1模型(草莓)问世，五级AGI再突破！使用「强化学习」再立大功。

【Nature重磅】RL教父Rich. S. Sutton提出持续反向传播算法，Mujoco中效果良好，深度学习还不如浅层网络？

【清华大学】李升波教授团队总结“强化学习和模型预测控制的区别与联系”

【顶会速递】RLC2024—128篇Accept论文汇总

【首届RL领域会议】Barto、Sutton、Sliver师徒3代，7篇杰出论文奖，独有论文评审机制公布。

【重磅头条】Agent Q智能体发布，利用自我对弈和强化学习, 实现自我纠正和自主改进！

【人物观点】RLHF 只是勉强 RL，前OpenAI大牛Andrej Karpathy全面解读与AlphaGo区别

【滴滴实习生招聘】强化学习项目落地(有转正机会)

【重磅快讯】强化学习大牛John Schulman离职OpenAI, 曾开发PPO|TRPO等, 领导OpenAI强化学习团队！

【重磅最新】OpenAI为RL设计出新的奖励机制

【字节招聘】强化学习智能体研究员

【顶会速递】清华大学提出“利用强化学习破解火箭回收过程的控制难题”

【粉丝福利】抽奖赠书《GPT图解：大模型是怎样构建的》

【重磅最新】OpenAI机密五级AGI路线图曝光！GPT-4仍处L1，智能体是核心！

【腾讯招聘】游戏AI强化学习算法研究员

从文字模型到世界模型！Meta新研究让AI Agent理解物理世界

【重磅开源】LeCun新作Puppeteer=基于强化学习+数据驱动+视觉全身人形控制方法

【好书力荐】大规模语言模型与强化学习：从理论到实践(文末抽奖赠送5本)

【最新综述！】「大模型+强化学习」详解四条主流技术路线

【今日头条招聘】机器人强化学习研究员(2024届优先)

【书籍推荐】《ChatGPT原理与应用开发》+代码，B站播放超30万。文末抽奖赠送X(>5)本

重磅 | 南栖仙策发布强化学习工业决策软件REVIVE 1.0

【开放源码】强化学习经典教材《RL for Sequential Decision and Optimal Control》

【腾讯招聘】强化学习岗位汇总

【吴恩达来信】AI智能体的黎明时刻

【LSTM之父Schmidhuber总结博客】利用循环世界模型和人工好奇心进行强化学习和规划

Richard Sutton ||智能决策器通用模型的探索

顶会最新速递@ ICLR2024，强化学习领域约301篇Accept论文汇总整理，附原文与交流群

【Nature重磅】DeepMind数学模型AlphaGeometry，做对25道几何题，GPT-4惨败得0分

【重磅推荐】盘古Agent，华为诺亚让智能体学会结构化推理，解决和适应复杂工作！

2023计算机科学7项重大突破！「P与NP」50年经典难题，大模型密集涌现上榜

论文分享| AAAI 2024 北航开源社交机器人行为对抗仿真计算平台SIASM，高效提升网络行为对抗能力

【真伪鉴别】OpenAI内幕文件惊人曝出，Q*疑能破解加密！是否具有元认知能力？

新书《面向工业控制的强化学习理论与方法》

【书籍推荐】清华大学李升波教授撰写《面向工业控制的强化学习理论与方法》

OpenAI神秘Q*项目解密！诞生30+年「Q学习」算法引全球网友终极猜想

【官方公布】2023中国科学院院士、中国工程院增选当选院士名单公布

【重磅最新】DeepMind发布"AGI 的六个层次及原则：实现 AGI 道路上的最近进展"！

分类

原创标签

时事社会财经军事教育体育科技汽车科学房产搞笑综艺明星音乐动漫游戏时尚健康旅游美食生活摄影宠物职场育儿情感小说曲艺文化历史三农文学娱乐电影视频图片新闻宗教电视剧纪录片广告创意壁纸头像心灵鸡汤星座命理教育培训艺术文化金融财经健康医疗美妆时尚餐饮美食母婴育儿社会新闻工业农业时事政治星座占卜幽默笑话独立短篇连载作品文化历史科技互联网

发布位置

广东北京山东江苏河南浙江山西福建河北上海四川陕西湖南安徽湖北内蒙古江西云南广西甘肃辽宁黑龙江贵州新疆重庆吉林天津海南青海宁夏西藏香港澳门台湾美国加拿大澳大利亚日本新加坡英国西班牙新西兰韩国泰国法国德国意大利缅甸菲律宾马来西亚越南荷兰柬埔寨俄罗斯巴西智利卢森堡芬兰瑞典比利时瑞士土耳其斐济挪威朝鲜尼日利亚阿根廷匈牙利爱尔兰印度老挝葡萄牙乌克兰印度尼西亚哈萨克斯坦塔吉克斯坦希腊南非蒙古奥地利肯尼亚加纳丹麦津巴布韦埃及坦桑尼亚捷克阿联酋安哥拉