提出神经网络在线学习的误判上限，揭示维度与边界对学习性能的关键影响。
Online Learning of Neural Networks
- 基于符号激活函数，通过边际条件刻画可在线学习性
- 误判数上界为约 $\mathtt{TS}(d,γ)$，且在某些情况下不可改进
- 在多指标或扩展边际假设下，误判数可摆脱维度依赖
研究前馈神经网络在符号激活函数下的在线学习问题，其输出映射从 $\mathbb{R}^d$ 单位球到有限标签集 $\{1, \ldots, Y\}$。首先，我们提出一个充分必要边际条件：第一层每个神经元对所有输入样本具有远离零的固定边距 $γ$。理论上证明，任意网络的最优误判界限不超过约 $\mathtt{TS}(d,γ)$，即 $(d,γ)$-完全可分打包数，是标准 $(d,γ)$-打包数的更严格形式。我们进一步构造出需达 $\mathtt{TS}(d,γ)$ 次误判的网络实例。同时给出下界 $\mathtt{TS}(d,γ) \geq \max\{1/(γ\sqrt{d})^d, d\}$（当 $γ\geq 1/2$ 时），表明部分网络在输入序列下误判次数可达 $\exp(d)$，维度无关的误判界几乎不可能实现。为缓解此依赖，考虑两类自然约束：一是多指标模型，函数仅依赖 $k \ll d$ 个正交方向，此时误判界约为 $(1.5/γ)^{k + 2}$；二是扩展边际假设，要求所有层神经元对前一层输出均有 $γ$ 边距，此时误判界约为 $(\log Y)/ γ^{O(L)}$，其中 $L$ 为网络深度。
原文摘要 · Abstract (English)
We study online learning of feedforward neural networks with the sign activation function that implement functions from the unit ball in $\mathbb{R}^d$ to a finite label set $\{1, \ldots, Y\}$. First, we characterize a margin condition that is sufficient and in some cases necessary for online learnability of a neural network: Every neuron in the first hidden layer classifies all instances with some margin $γ$ bounded away from zero. Quantitatively, we prove that for any net, the optimal mistake bound is at most approximately $\mathtt{TS}(d,γ)$, which is the $(d,γ)$-totally-separable-packing number, a more restricted variation of the standard $(d,γ)$-packing number. We complement this result by constructing a net on which any learner makes $\mathtt{TS}(d,γ)$ many mistakes. We also give a quantitative lower bound of approximately $\mathtt{TS}(d,γ) \geq \max\{1/(γ\sqrt{d})^d, d\}$ when $γ\geq 1/2$, implying that for some nets and input sequences every learner will err for $\exp(d)$ many times, and that a dimension-free mistake bound is almost always impossible. To remedy this inevitable dependence on $d$, it is natural to seek additional natural restrictions to be placed on the network, so that the dependence on $d$ is removed. We study two such restrictions. The first is the multi-index model, in which the function computed by the net depends only on $k \ll d$ orthonormal directions. We prove a mistake bound of approximately $(1.5/γ)^{k + 2}$ in this model. The second is the extended margin assumption. In this setting, we assume that all neurons (in all layers) in the network classify every ingoing input from previous layer with margin $γ$ bounded away from zero. In this model, we prove a mistake bound of approximately $(\log Y)/ γ^{O(L)}$, where L is the depth of the network.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。