WikiEdge:ArXiv速递/2025-04-15：修订间差异
Created page by Carole |
Updated page by Carole |
||
| 第8行： | 第8行： | ||
'''中文摘要'''：[[斯坦纳森林问题]]（又称广义[[斯坦纳树问题]]）是边加权图上的一个基本优化问题，其目标是在给定顶点对集合的情况下，选择一个最小成本的子图使得每对顶点都连通。该问题推广了1811年首次提出的[[斯坦纳树问题]]，后者的最佳已知近似因子为1.39 [[Byrka等，2010]]（[[STOC]] 2010最佳论文奖）。[[Agrawal等，1989]]（[[STOC]] 2023三十年时间检验奖）的开创性工作与[[Goemans和Williamson，1992]]（[[SICOMP]]'95）的改进，在35年前就建立了[[斯坦纳森林问题]]的2-近似算法。[[Jain]]（[[FOCS]]'98）开创性的迭代舍入技术后来将这些结果扩展到更高连通性场景。尽管该问题具有长期重要性，但突破2的近似因子始终是重大挑战，甚至引发类似[[顶点覆盖问题]]的猜想——获得更好因子可能确实困难。值得注意的是，包括[[Gupta和Kumar]]（[[STOC]]'15）以及[[Gro{\ss}等]]（[[ITCS]]'18）的基础性工作，分别提出了96和69近似算法，可能寄望为[[斯坦纳森林问题]]实现低于2的常数因子近似突破铺路。 | '''中文摘要'''：[[斯坦纳森林问题]]（又称广义[[斯坦纳树问题]]）是边加权图上的一个基本优化问题，其目标是在给定顶点对集合的情况下，选择一个最小成本的子图使得每对顶点都连通。该问题推广了1811年首次提出的[[斯坦纳树问题]]，后者的最佳已知近似因子为1.39 [[Byrka等，2010]]（[[STOC]] 2010最佳论文奖）。[[Agrawal等，1989]]（[[STOC]] 2023三十年时间检验奖）的开创性工作与[[Goemans和Williamson，1992]]（[[SICOMP]]'95）的改进，在35年前就建立了[[斯坦纳森林问题]]的2-近似算法。[[Jain]]（[[FOCS]]'98）开创性的迭代舍入技术后来将这些结果扩展到更高连通性场景。尽管该问题具有长期重要性，但突破2的近似因子始终是重大挑战，甚至引发类似[[顶点覆盖问题]]的猜想——获得更好因子可能确实困难。值得注意的是，包括[[Gupta和Kumar]]（[[STOC]]'15）以及[[Gro{\ss}等]]（[[ITCS]]'18）的基础性工作，分别提出了96和69近似算法，可能寄望为[[斯坦纳森林问题]]实现低于2的常数因子近似突破铺路。 | ||
本文通过设计一种新颖的确定性算法，实现了$2 - 10^{-11}$的近似比，突破了2的近似壁垒。作为方法的核心组件，我们还针对[[斯坦纳树问题]]提出了一种基于对偶的局部搜索算法，其近似保证为$1.943$，该成果本身也具有独立价值。 | 本文通过设计一种新颖的确定性算法，实现了$2 - 10^{-11}$的近似比，突破了2的近似壁垒。作为方法的核心组件，我们还针对[[斯坦纳树问题]]提出了一种基于对偶的局部搜索算法，其近似保证为$1.943$，该成果本身也具有独立价值。 | ||
== 摘要 == | |||
* '''原文标题'''：Progressive Rock Music Classification | |||
* '''中文标题'''：渐进摇滚音乐分类 | |||
* '''发布日期'''：2025-04-15 02:48:52+00:00 | |||
* '''作者'''：Arpan Nagar, Joseph Bensabat, Jokent Gaza, Moinak Dey | |||
* '''分类'''：cs.SD, cs.AI, cs.LG, eess.AS | |||
*'''原文链接'''：http://arxiv.org/abs/2504.10821v1 | |||
'''中文摘要'''：本研究探讨[[前卫摇滚]]音乐的[[分类问题]]，该[[音乐流派]]以复杂的[[作曲结构]]和多样化的[[器乐编配]]为特征，与其他[[音乐风格]]截然不同。针对这一[[音乐信息检索]]（[[MIR]]）任务，我们使用[[Librosa]]库从[[歌曲]]片段中提取了包括[[声谱图]]、[[梅尔频率倒谱系数]]（[[MFCCs]]）、[[色度图]]和[[节拍位置]]在内的综合[[音频特征]]，并通过[[赢家通吃]]投票策略将片段级预测聚合为最终歌曲分类。我们对多种[[机器学习]]技术进行了对比分析：在[[计算资源]]受限情况下，采用[[主成分分析]]（[[PCA]]）进行[[降维]]处理，探索了包含[[Bagging]]（[[随机森林]]、[[极端随机树]]、[[Bagging分类器]]）和[[Boosting]]（[[XGBoost]]、[[梯度提升]]）的[[集成方法]]；同时研究了[[深度学习方法]]，包括开发具有特定[[层配置]]、[[归一化]]和[[激活函数]]的定制[[一维卷积神经网络]]（[[1D CNN]]）架构（命名为"Zuck"和"Satya"），并微调了基于[[注意力机制]]的最先进[[音频声谱图变换器]]（[[AST]]）模型。[[验证集]]和[[测试集]]的[[性能评估]]显示不同[[模型]]效果各异，其中[[极端随机树]]等集成方法最高达到76.38%的测试[[准确率]]。本研究为[[前卫摇滚]]流派分类这一精细任务提供了多种[[机器学习范式]]应用及相对性能的深入见解。 | |||
2025年4月16日 (三) 10:20的版本
摘要
- 原文标题：Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
- 中文标题：突破长期障碍：斯坦纳森林问题的2-ε近似算法
- 发布日期：2025-04-15 17:13:48+00:00
- 作者：Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi
- 分类：cs.DS
- 原文链接：http://arxiv.org/abs/2504.11398v1
中文摘要：斯坦纳森林问题（又称广义斯坦纳树问题）是边加权图上的一个基本优化问题，其目标是在给定顶点对集合的情况下，选择一个最小成本的子图使得每对顶点都连通。该问题推广了1811年首次提出的斯坦纳树问题，后者的最佳已知近似因子为1.39 Byrka等，2010（STOC 2010最佳论文奖）。Agrawal等，1989（STOC 2023三十年时间检验奖）的开创性工作与Goemans和Williamson，1992（SICOMP'95）的改进，在35年前就建立了斯坦纳森林问题的2-近似算法。Jain（FOCS'98）开创性的迭代舍入技术后来将这些结果扩展到更高连通性场景。尽管该问题具有长期重要性，但突破2的近似因子始终是重大挑战，甚至引发类似顶点覆盖问题的猜想——获得更好因子可能确实困难。值得注意的是，包括Gupta和Kumar（STOC'15）以及[[Gro{\ss}等]]（ITCS'18）的基础性工作，分别提出了96和69近似算法，可能寄望为斯坦纳森林问题实现低于2的常数因子近似突破铺路。 本文通过设计一种新颖的确定性算法，实现了$2 - 10^{-11}$的近似比，突破了2的近似壁垒。作为方法的核心组件，我们还针对斯坦纳树问题提出了一种基于对偶的局部搜索算法，其近似保证为$1.943$，该成果本身也具有独立价值。
摘要
- 原文标题：Progressive Rock Music Classification
- 中文标题：渐进摇滚音乐分类
- 发布日期：2025-04-15 02:48:52+00:00
- 作者：Arpan Nagar, Joseph Bensabat, Jokent Gaza, Moinak Dey
- 分类：cs.SD, cs.AI, cs.LG, eess.AS
- 原文链接：http://arxiv.org/abs/2504.10821v1
中文摘要：本研究探讨前卫摇滚音乐的分类问题，该音乐流派以复杂的作曲结构和多样化的器乐编配为特征，与其他音乐风格截然不同。针对这一音乐信息检索（MIR）任务，我们使用Librosa库从歌曲片段中提取了包括声谱图、梅尔频率倒谱系数（MFCCs）、色度图和节拍位置在内的综合音频特征，并通过赢家通吃投票策略将片段级预测聚合为最终歌曲分类。我们对多种机器学习技术进行了对比分析：在计算资源受限情况下，采用主成分分析（PCA）进行降维处理，探索了包含Bagging（随机森林、极端随机树、Bagging分类器）和Boosting（XGBoost、梯度提升）的集成方法；同时研究了深度学习方法，包括开发具有特定层配置、归一化和激活函数的定制一维卷积神经网络（1D CNN）架构（命名为"Zuck"和"Satya"），并微调了基于注意力机制的最先进音频声谱图变换器（AST）模型。验证集和测试集的性能评估显示不同模型效果各异，其中极端随机树等集成方法最高达到76.38%的测试准确率。本研究为前卫摇滚流派分类这一精细任务提供了多种机器学习范式应用及相对性能的深入见解。