Origin of the computational hardness for learning with binary synapses
Origin of the computational hardness for learning with binary synapses
复制标题
DOI：
10.1103/physreve.90.052813
复制
发表时间：
2014-08
期刊：
影响因子：
--
通讯作者：
Haiping Huang;Y. Kabashima
中科院分区：
文献类型：
--
作者：
Haiping Huang;Y. Kabashima
通过在二元感知器中的监督学习，人们能够通过适当地分配二进制突触权重来分类大量的随机模式。然而，在实践中找到这样的任务是一项相当不容易的任务。权空间结构和算法难度之间的关系还没有完全被理解。为此，我们从权的平衡解出发，通过探索它周围的权空间结构，解析地推导出二元感知器问题的Franz-Parisi势。我们的结果揭示了权空间的几何组织；权空间是由孤立的解组成的，而不是由指数级的许多邻近解组成的簇。在权重空间中彼此相距较远的点状簇解释了先前观察到的随机局部搜索启发式算法的玻璃行为。
Through supervised learning in a binary perceptron one is able to classify an extensive number of random patterns by a proper assignment of binary synaptic weights. However, to find such assignments in practice is quite a nontrivial task. The relation between the weight space structure and the algorithmic hardness has not yet been fully understood. To this end, we analytically derive the Franz-Parisi potential for the binary perceptron problem by starting from an equilibrium solution of weights and exploring the weight space structure around it. Our result reveals the geometrical organization of the weight space; the weight space is composed of isolated solutions, rather than clusters of exponentially many close-by solutions. The pointlike clusters far apart from each other in the weight space explain the previously observed glassy behavior of stochastic local search heuristics.