Boolean threshold functions, neuron capacity, and memory retrieval

概要

How much information can a single neuron remember? How many memories can neural networks retrieve without creating false memories? These questions are related to a basic question: how many Boolean threshold functions $f(x)=\operatorname{sgn}(a_0+\langle a,x\rangle)$, $x\in\{-1,1\}^n$, are there? In this paper, we show that the number $T_n$ of distinct Boolean threshold functions is \[ T_n=2\binom{2^n-1}{n}\bigl(1+O(n^{-99})\bigr). \] Equivalently, the capacity of a single threshold neuron is $n^2-\log_2(n!)+1+O(n^{-99})$ bits, improving the $O(n)$ error term in the result of Kahn--Komlós--Szemerédi to $O(n^{-99})$. To prove this, we show that, for $1\le r\le n-1$, and $v_1,\ldots,v_r$ are chosen at random from $\{-1,1\}^n$, \[ \mathbb P\!\left\{ \langle v_1,\ldots,v_r\rangle\cap\{-1,1\}^n =\{\pm v_1,\ldots,\pm v_r\} \right\} =1-O(n^{-99}). \] In the context of the Kanter--Sompolinsky Hamiltonian for memory retrieval, this identifies $r=n-1$ as a sharp threshold, at which, for almost every collection of $r$ memories, the only ground states are these memories and their negatives, confirming a weaker form of the Kalai--Linial--Odlyzko conjecture. It also settles a recent open problem posed by M. Anthony on the specification number of Boolean threshold functions. In addition, we show that, for every $1\le r\le n-1$, \[ \mathbb P\{v_1,\ldots,v_r\text{ are linearly dependent}\} =2\binom r2\,2^{-n}+O\!\left(2^{-n}e^{-cn}\right), \] confirming a conjecture of Kahn--Komlós--Szemerédi.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Boolean threshold functions, neuron capacity, and memory retrieval

# 概要
How much information can a single neuron remember? How many memories can neural networks retrieve without creating false memories?

# 原典
https://arxiv.org/abs/2609.29756

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。