AI如何发现一个更快的矩阵乘法算法-AI如何发现一个更快的矩阵乘法算法

热门回复：

• 阿希伯特风暴:简介不是统治算法，是分治算法，divide and conquer
• MarvinCat:算法发现过程：研究团队将矩阵乘法算法的发现过程表述为一个名为TensorGame的单人游戏。在这个游戏中，玩家需要选择如何组合矩阵的不同条目以执行乘法。游戏根据所需操作的数量给予分数，目标是用最少的操作达到正确的乘法结果。AlphaTensor利用一个神经网络来引导寻找高效矩阵乘法算法的计划过程。这个框架使用单个智能体来分解各种尺寸的矩阵乘法张量【10†source】。 神经网络架构：AlphaTensor采用基于变压器的架构，专门用于处理张量输入。输入张量被投影到三个特征向量网格中，然后通过一系列的注意力操作处理，最终将特征表示传递给策略头部（自回归模型）和价值头部（多层感知器）【11†source】。 蒙特卡洛树搜索（MCTS）规划程序：网络输入当前状态（即要分解的张量），并输出策略和价值。策略提供潜在动作的分布，价值则提供从当前状态开始的返回分布估计。AlphaTensor从目标张量开始游戏，每一步使用MCTS规划程序选择下一个动作。完成的游戏被用作网络参数改进的反馈【12†source】。 合成演示：由于张量分解是NP难问题，但其逆过程（从秩一因子构造张量）则相对简单，研究人员生成了大量的张量-因子化对（合成演示），并在此基础上训练网络。这种混合训练策略在训练目标张量和随机张量上表现优异【13†source】。 基础变换：研究人员通过在每个游戏开始时随机采样一个基础变换，并将其应用于张量，从而注入了多样性。在自定义基础上的分解可以映射回规范基础，从而获得实用算法【14†source】。
• KellyFrog:Strassen 算法并不是用加法换乘法，在分治过程中，2*2 矩阵 7 次乘法的每一次乘法都在 n*n 的矩阵乘法中对应了一次 n/2*n/2 的矩阵乘法，因此 8 次和 7 次实际上是递归的次数，两者的时间复杂度有本质的区别，不仅仅是乘法次数，加法次数在 n 更大的时候也会更少。 Strassen 中的复杂度 T(n)=7T(n/2)+O(n^2)，解得 T(n)=O(n^(log2 7)) 而在普通的分治乘法中复杂度 T(n)=8T(n/2)+O(n^2)，解得 T(n)=O(n^3)，或直接乘也是 O(n^3) 而 Strassen 没有广泛采用的原因之一是其常数因子太大，而且递归的内存开销也很大，因此在“能算出来”的范围里不太实用。
• 燕狮屋庵鹰:这应该都是针对计算机的吧[笑哭]，自己算还是得原来方法，刚学每次算都要愣半天😂
• 转关抽AirPodsPro:字幕是gpt生成的吧[doge]开头没删