On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach

半自动机是一类丰富的序列处理算法，在自然语言处理、机器人学、计算生物学和数据挖掘等领域具有广泛应用。本文首次建立了在输入字串和初始状态服从均匀分布条件下，半自动机的统计查询（Statistical Query）计算困难性结果。我们证明了当字母表大小和输入长度关于状态数为多项式量级时，即可建立统计查询的困难性。与确定性有限自动机不同——其困难性通常源于所识别语言本身的难度（例如奇偶性问题）——我们的结果完全源自半自动机内部的状态转移结构。我们的分析将区分两个半自动机最终状态的问题，归约为研究在群 $S_{N} \times S_{N}$ 上随机游走的行为。通过应用傅里叶分析以及对称群的表示理论工具，我们得到了紧致的谱间隙界，表明在关于状态数的多项式步数之后，不同的半自动机之间几乎不再相关，从而得出所期望的困难性结果。

论文试图解决在均匀分布下，针对半自动机（semiautomata）的统计查询（Statistical Query, SQ）学习难度问题。这是一个相对较新的问题，因为以往对自动机的学习难度分析多集中在语言识别难度（如奇偶性语言），而本文首次从半自动机内部状态转移结构本身出发，证明其学习在SQ模型下的困难性，即使输入和初始状态服从均匀分布。

论文的关键思路是将区分两个半自动机最终状态的问题，转化为在对称群 $S_N \times S_N$ 上的随机游走行为分析。通过引入傅里叶分析和对称群的表示理论，推导出精确的谱间隙界限，从而证明在多项式步数后，不同半自动机的输出几乎不相关，导致在SQ模型中无法有效区分。这一思路的新颖之处在于不依赖语言复杂性，而是完全基于状态转移动力学来建立计算硬度。

论文的亮点包括：1）首次建立半自动机在均匀分布下的SQ硬度结果；2）技术上创新地结合了群表示论与学习理论；3）实验设计虽为理论分析，但通过严格的数学推导验证了相关性衰减速度；4）未提及具体数据集或开源代码，因属理论工作；5）未来可深入研究其他代数结构自动机的硬度、噪声下的学习能力，以及与神经序列模型的联系。

1. On the Learnability of Hidden Markov Models 2. The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length 3. Statistical Query Lower Bounds for PAC Learning 4. Fourier Analysis on Finite Groups and the Representation Theory of Symmetric Groups 5. Hardness of Learning Halfspaces with Noise