周报-2016-10-22

1.Rademacher Complexity and VC-Dimension

• 1.图灵机的定义：根据某一特定规则操作一条带上的符号。
  A Turing machine is an abstract machine that manipulates symbols on a strip of tape according to a table of rules。（From Wikipedia）
  一个存储带：
  机器操作的内存是无限长的被划分成单元的胶带（tape）,胶带双向无限长，上面有一个个小单元（cell），每个单元可以存储信息。
  一个控制器：
  可以存储当前自身状态，包含一个读写头（head），可以读写数据和移动。参考自知乎
• 2.NP-Hard
  non-deteministic ployminial-time hard.
• 3.Empirical Rademacher complexity
  G:和H相关的损失函数集。将Z映射到 $\{0,1\}$.
  $S=(S_1,\ldots,S_m)$
  经验 Rademacher 复杂度：
  定义：
  $$\widehat{{\cal{R}}_s}(G)=\mathop{E}\limits_{\sigma}\left[ \mathop{sup}\limits_{g\in G} \frac {1}{m} \sum_{i=1}^m \sigma _i g(z_i)\right]$$
  $\sigma =(\sigma _1,\ldots,\sigma_m)$为独立的单位随机变量，$g_s=(g(z_1),\ldots,g(z_m))$，则上式可简化为：
  $$\widehat{{\cal{R}}_s}(G)=\mathop{E}\limits_{\sigma}\left[ \mathop{sup}\limits_{g\in G} \frac {\sigma g_s}{m} \right]$$
• 4.Rademacher complexity:
  Rademacher complexity
  定义：
  $${\cal{R}}_m(G)=\mathop{E} \limits_{S \sim D^m}\left[ \widehat{\cal{R}}_s(G) \right ]$$
  上界：$\mathop{sup}\limits_{g\in G} \frac {\sigma g_s}{m}$是描述函数集G对于样本S和$\sigma$的相关性。

2.增长函数（Growth function）

• 增长函数$\Pi _H :N \rightarrow N$关于假设H的定义：
  $$\forall m\in N,\quad \Pi _H =\mathop{max} \limits_{\{x_1,\ldots,x_m \}\subseteq X} \left | \{ (h(x_1),\ldots,h(x_m)) :h\in H \} \right |$$
  $\Pi _H (m)$表示了假设集H所能归类m个点得不同方法数。提供了另一种描述H的丰富度(richness)的方法。

相关数学

• Markov不等式
  $$Pr\left [ x>\epsilon \right ] \leq \frac {E[x]} {\epsilon}$$
• Hoeffding引理
  X为随机变量，E[X]=0,$a \leq X \leq b$,有 $\forall t>0$:
  满足： $$E\left [ e^{tX} \right ] \leq e^{ \frac {t^2(b-a)^2}{8}}$$
• （定理）Hoeffding不等式
  $X_1,\ldots,X_m$为独立随机变量，满足$\forall i \in [1,m], X_i \in[a_i,b_i]$,计$S_m=\sum_{i=1}^{m}X_i$,以下等式成立：
  $$Pr\left[ S_m-E[S_m] \geq \epsilon \right]\leq \frac {e^{-2{\epsilon}^2}}{\sum_{i=1}^{m}{(b_i-a_i)^2}}$$
  $$Pr\left[ S_m-E[S_m] \leq -\epsilon \right]\leq \frac {e^{-2{\epsilon}^2}}{\sum_{i=1}^{m}{(b_i-a_i)^2}}$$
• 鞅差序列(Martingale difference sequence)
  Wikipedia定义：若一个随机级数满足对于先前的条件期望为0，则其为一个鞅差序列。
  $$E[X]=0,E[X|F_{t-1}]=0$$
  From wikipedia
  一个随机变量序列$V_1,V_2,\ldots$是鞅差序列，如果：
  $$E \left [V_{i+1}|X_1,\ldots,X_i \right ]=0.$$
  其中：$V_i$ 是关于$X_1,\ldots,X_i$的函数。
• （定理）Azuma定理
  $V_1,V_2,\ldots$是关于$X_1,X_2,\ldots$鞅差序列,假设：$\forall i > 0$,$\exists c_i>0$ 关于$X_1,X_2,\ldots,X_{i-1}$随机变量$Z_i$,满足：$Z_i \leq V_i <Z_i+c_i$
  有一下结论成立：
  $$\forall \epsilon >0 \quad and \quad m，\quad Pr\left[ \sum_{i=1}^{m}{V_i} \geq \epsilon \right] \leq e^{\frac {-2{\epsilon}^2}{\sum_{i=1}^{m}{c_i^2}}}$$
  $$Pr\left[ \sum_{i=1}^{m}{V_i} \leq -\epsilon \right] \leq e^{\frac {-2{\epsilon}^2}{\sum_{i=1}^{m}{c_i^2}}}$$
• McDiarmid 不等式
  $X_1,X_2,\ldots,X_{i-1},X_m \in \chi ^m$是独立随机变量，假设$\exists c_1,c_2,\ldots,c_m >0, \quad and \quad f:\chi ^m \rightarrow R$,满足：
  $$\forall i\in [1,m], \quad x_1\ldots,x_m,x_{i^{'}} \in \chi ,\quad \left | f(x_1,\ldots,x_i,\ldots,x_m)-f(x_1,\ldots,x_{i^{'}},\ldots,x_m) \right | \leq c_i$$
  有以下结论（将$f(x_1,\ldots,x_m)$记做f(S)）:
  $$Pr\left[ f(S)-E[f(S)] \geq \epsilon \right] \leq e^{\frac {-2{\epsilon}^2}{\sum_{i=1}^{m}{c_i^2}}}$$
  $$Pr\left[ f(S)-E[f(S)] \leq -\epsilon \right] \leq e^{\frac {-2{\epsilon}^2}{\sum_{i=1}^{m}{c_i^2}}}$$