Contents
Storage capacity of a simple perceptron¶
Storage capacity of machine learning models is anaylzed by a method in Stastical mechanics [Gardner, 1988].
import numpy as np
import matplotlib.pyplot as plt
from scipy.special import erfc
def H(x):
return erfc(x / np.sqrt(2)) * 0.5
def H_1st_deriv(x):
return -np.exp(-x**2 / 2) / np.sqrt(2 * np.pi)
def H_2nd_deriv(x):
return np.exp(-x**2 / 2) * x / np.sqrt(2 * np.pi)
def saddle_point_equation(alpha, kappa=0.0, q_init=0.5,
num_samples=100000, c=0.9, max_step=200):
q = q_init
step = 0
eps = 1e-8
error = 1e10
while error > eps:
step += 1
q_prev = q
# q
z = np.random.randn(num_samples)
x = (kappa - np.sqrt(q) * z) / np.sqrt(1 - q)
h = H(x)
indices = np.where(h != 0)[0]
h = h[indices]
x = x[indices]
h1 = H_1st_deriv(x)
h2 = H_2nd_deriv(x)
int_z = (h1 / h)**2 - h2 / h
q = alpha * np.mean(int_z)
# qtilde
qtilde = q / (1 - q)**2
# Update
q = (1 - c) * q + c * q_prev
error = abs(q - q_prev)
Qtilde = (1 - 2*q) / (1 - q)**2
if q > 1.0:
q = 1.0
break
if max_step is not None and step >= max_step:
break
print(f'step={step}, Qtilde={Qtilde}, qtilde={qtilde}, q={q}')
return q
params = dict(
num_samples=100000,
c=0.99,
max_step=1000,
)
alpha_list = [0.0, 0.5, 1.0, 1.5, 2.0]
alpha_q_hists = {}
for alpha in alpha_list:
print(f'alpha={alpha}')
q = saddle_point_equation(alpha, kappa=1.0, **params)
alpha_q_hists[alpha] = q
alpha=0.0
step=1000, Qtilde=0.9999999995340407, qtilde=0.0, q=2.158562370532892e-05
alpha=0.5
step=801, Qtilde=0.5373326273852124, qtilde=1.1428611117978906, q=0.4048315426950762
alpha=1.0
step=1000, Qtilde=-20.574391619354625, qtilde=26.341073344259986, q=0.8228465636932442
alpha=1.5
step=210, Qtilde=-2387291405.2465324, qtilde=59.55624878953845, q=1.0
alpha=2.0
step=58, Qtilde=-2721684.4813690456, qtilde=146.29040847822128, q=1.0
plt.plot(alpha_list, list(alpha_q_hists.values()), marker='o', linestyle='--')
plt.xlabel(r'$\alpha$')
plt.ylabel(r'$q$')
plt.show()
Asymptotic form¶
In \(q \rightarrow 1\),
\[
\alpha_{\mathrm{c}}(\kappa)=\left\{\int_{-\kappa}^{\infty} \mathrm{D} y(\kappa+y)^{2}\right\}^{-1}
\]
def critical_alpha(kappa, num_samples=100000):
y = np.random.randn(num_samples)
Dy = (kappa + np.where(-kappa <= y, y, 0))**2
return 1 / np.mean(Dy)
kappa_list = np.linspace(0, 3, 50)
alpha_c_hists = []
for kappa in kappa_list:
alpha_c = critical_alpha(kappa)
alpha_c_hists.append(alpha_c)
plt.plot(kappa_list, alpha_c_hists)
plt.xlabel(r'$\kappa$')
plt.ylabel(r'$\alpha_c(\kappa)$')
plt.show()
References¶
- Gar88
E Gardner. The space of interactions in neural network models. Journal of Physics A: Mathematical and General, 21(1):257–270, January 1988. URL: https://iopscience.iop.org/article/10.1088/0305-4470/21/1/030 (visited on 2021-10-08).