自适应线性单元–Adaptive Linear Units–Adaline

模型结构

• 在M-P模型的基础上
• $\begin{aligned}s(k)&=\sum_{i=1}^nw_ix_i(k)-\theta\\&=\sum_{i=0}^nw_ix_i(k)\\&=W^TX(k)\end{aligned}$s(k)​=i=1∑n​wi​xi​(k)−θ=i=0∑n​wi​xi​(k)=WTX(k)​
• $y(k)$y(k)依然是二值输出，$\varphi(s)$φ(s)可以取$\varphi(s)=U(s)$φ(s)=U(s)或$\varphi(s)=Sgn(s)$φ(s)=Sgn(s)
• $d(k)$d(k)依然是期望输出（不是二值，是任意值）
• 区别：使线性部分（任意值）来逼近理想输出

• 学习算法：LMS，利用$d(k)和s(k)$d(k)和s(k)的差别，使$e(k)=d(k)-s(k)$e(k)=d(k)−s(k)，来调整权重$w_i$wi​，使得线性输出$s(k)\rarr d(k)$s(k)→d(k)，从而使得$y(k)$y(k)逼近理想的二值函数

最小均方误差算法(The Least Mean Squared Error Algorithm，LMS)

• 算法的存在性和收敛性

• 设理想权值为$W^*$W∗

  $s(k)=W^TX(k),W=[w_0,w_1,...,w_n]^T,X(k)=[1,x_1(k),...,x_n(k)]^T$s(k)=WTX(k),W=[w0​,w1​,...,wn​]T,X(k)=[1,x1​(k),...,xn​(k)]T

  则误差$e(k)$e(k)为：$e(k)=d(k)-W^TX(k)$e(k)=d(k)−WTX(k)，$e(k)$e(k)是关于$W$W的线性函数

  定义误差平方的数学期望为$J(W)=E[e^2(k)]\xrightarrow{W}\min$J(W)=E[e2(k)]W​min选取合适的$W$W，使得$J(W)$J(W)取得最小值

  $\begin{aligned}J(W)&=E[(d(k)-W^TX(k))^2]=E[(d^2(k)-2W^TX(k)d(k)+W^TX(k)X^T(k)W)))]\\&=E[d^2(k)]-2W^TR_{Xd}+W^TR_{XX}W\end{aligned}$J(W)​=E[(d(k)−WTX(k))2]=E[(d2(k)−2WTX(k)d(k)+WTX(k)XT(k)W)))]=E[d2(k)]−2WTRXd​+WTRXX​W​

  第一项为理想输出的数学期望，为常数，不关心；

  第二项中，$R_{Xd}=E[X(k)d(k)]$RXd​=E[X(k)d(k)]为$x(k)和d(k)$x(k)和d(k)的互相关矢量

  第三项中，$R_{XX}=E[X(k)X^T(k)]$RXX​=E[X(k)XT(k)]为$X(k)$X(k)的自相关矩阵

  求$J(W)$J(W)的最小值，对其求导：

  令$\frac{\partial J(W)}{\partial W}=0$∂W∂J(W)​=0

  $\frac{\partial J(W)}{\partial W}\vert_{W=W^*}=-2R_{Xd}+2R_{XX}W^*=0$∂W∂J(W)​∣W=W∗​=−2RXd​+2RXX​W∗=0

  $W^*=R_{XX}^{-1}R_{Xd}$W∗=RXX−1​RXd​

  带入得$J(W^*)=E[d^2(k)]-W^{*T}R_{Xd}$J(W∗)=E[d2(k)]−W∗TRXd​

  表面上看，如果知道了$R_{XX},R_{Xd}$RXX​,RXd​，就能够求出$W^*$W∗

  好看不好用

  问题：

  1. 在实际应用中，互相关矢量和自相关矩阵不知道
  2. 两个矩阵维数太高，不好估计
  3. 在这里面还需要求$R_{XX}^{-1}$RXX−1​，大矩阵求逆很困难
  4. 只对线性模型成立，对非线性模型不成立$W^*\not=R_{XX}^{-1}R_{Xd}$W∗​=RXX−1​RXd​

  在实际应用中，用迭代的方式来解决。

梯度下降算法（Gradient Descent Algorithm）

• 目标函数：$J(W)=E[e^2(k)]=E[d^2(k)]-2W^TR_{Xd}+W^TR_{XX}W=E$J(W)=E[e2(k)]=E[d2(k)]−2WTRXd​+WTRXX​W=E

• 目标函数梯度：$\nabla E=\frac{\partial E}{\partial W}=-2R_{Xd}+2R_{XX}W=2R_{XX}(W-R_{XX}^{-1}R_{Xd})=2R_{XX}(W-W^*)$∇E=∂W∂E​=−2RXd​+2RXX​W=2RXX​(W−RXX−1​RXd​)=2RXX​(W−W∗)

• 为了调整$W$W使得$W\rarr W^*$W→W∗，需要使KaTeX parse error: Got function '\min' with no arguments as subscript at position 10: E\rarr E_\̲m̲i̲n̲

• 权值调整思路：梯度下降法

  $E$E是关于$W$W的二次函数，存在一个最低点使得$E$E得到最小值KaTeX parse error: Got function '\min' with no arguments as subscript at position 3: E_\̲m̲i̲n̲，通过求$E$E的梯度，按照梯度增加的相反方向调整权值，就能使误差能量朝下降的方向发展。

• 梯度下降法（假设$\nabla E$∇E已知）

  • 初始化：

    $W(0)\larr$W(0)←较小的数，$k\larr0$k←0

  • 使用梯度下降法更新权重

    $W(k+1)\larr W(k)+\alpha(-\nabla E)$W(k+1)←W(k)+α(−∇E)

    $\alpha$α为学习率，$0<\alpha\leq1$0<α≤1

  • 循环：$k\larr k+1$k←k+1直到收敛（判断误差能量是否足够小）

• 敛散性分析（通过分析可以得到学习率应该怎么取）

  • 误差能量的梯度为$\nabla E=2R_{XX}(W-W^*)$∇E=2RXX​(W−W∗)，通过迭代使得$W(k)\xrightarrow{k\rarr\infty}W^*$W(k)k→∞​W∗

  • 证明过程：

    $\begin{aligned}W(k+1)-W^*=W(k)-\alpha\nabla E-W^*&=W(k)-W^*-2\alpha R_{XX}(W(k)-W^*)\\&=(I-2\alpha R_{XX})(W(k)-W^*)\end{aligned}$W(k+1)−W∗=W(k)−α∇E−W∗​=W(k)−W∗−2αRXX​(W(k)−W∗)=(I−2αRXX​)(W(k)−W∗)​

    定义$W(k)-W^*=V(k)$W(k)−W∗=V(k)

    则上式可写为：

    $V(k+1)=(I-2\alpha R_{XX})V(k)$V(k+1)=(I−2αRXX​)V(k)

    接下来只需要证明$V(k)\xrightarrow{k\rarr\infty}0$V(k)k→∞​0

    由于$R_{XX}$RXX​为自相关矩阵，是对称矩阵，根据其性质可以作特征值分解，即存在一个可逆矩阵$Q$Q，使得$Q^{-1}R_{XX}Q=\varLambda$Q−1RXX​Q=Λ

    $\therefore R_{XX}=Q\varLambda Q^{-1}$∴RXX​=QΛQ−1，其中$\varLambda$Λ为对角阵，对角元素为$R_{XX}$RXX​的特征值。

    $\therefore V(k+1)=(QQ^{-1}-2\alpha Q\varLambda Q^{-1})V(k)=Q(I-2\alpha\varLambda)Q^{-1}V(k)$∴V(k+1)=(QQ−1−2αQΛQ−1)V(k)=Q(I−2αΛ)Q−1V(k)

    $(I-2\alpha\varLambda)$(I−2αΛ)为对角阵，两边同时左乘$Q^{-1}$Q−1

    $Q^{-1}V(k+1)=(I-2\alpha\varLambda)Q^{-1}V(k)$Q−1V(k+1)=(I−2αΛ)Q−1V(k)

    令$V'(k)=Q^{-1}V(k)$V′(k)=Q−1V(k)，则$V'(k+1)=(I-2\alpha\varLambda)V'(k)$V′(k+1)=(I−2αΛ)V′(k)

    $\therefore V'(1)=(I-2\alpha\varLambda)V'(0),V'(2)=(I-2\alpha\varLambda)^2V'(0),...$∴V′(1)=(I−2αΛ)V′(0),V′(2)=(I−2αΛ)2V′(0),...

    $V'(k)=(I-2\alpha\varLambda)^kV'(0)$V′(k)=(I−2αΛ)kV′(0)

    $(I-2\alpha\varLambda)$(I−2αΛ)为对角阵，如果要对角阵趋近于零，要看对角矩阵中各个元素的k次方是否趋近于零

    $\varLambda=\begin{bmatrix}\lambda_1\quad\quad0\\\ddots\\0\quad\quad\lambda_n\end{bmatrix}$Λ=⎣⎡​λ1​0⋱0λn​​⎦⎤​

    即要使$(1-2\alpha\lambda_i)^k\rarr0,(i=1,...,n)$(1−2αλi​)k→0,(i=1,...,n)

    则$-1<(1-2\alpha\lambda_i)<1$−1<(1−2αλi​)<1，在这里，唯一的变量是$\alpha$α，$\alpha$α的条件为$0<\alpha<1/\lambda_i$0<α<1/λi​

    要对所有的特征值都满足

    $\therefore0<\alpha<1/max_i\{\lambda_i\}$∴0<α<1/maxi​{λi​}

    实际情况中特征值并不好求，所以$\alpha$α只能估算

LMS的随机逼近算法（Stochastic Approximation Algorithm of LMS）

• $\nabla E=2R_{XX}(W-W^*)$∇E=2RXX​(W−W∗)

• $\nabla E=\frac{\partial E}{\partial W}=\frac{\partial}{\partial W}\{E[(d(k)-W^TX(k))^2]\}=-2\{E[(d(k)-W^TX(k))X(k)]\}=-2\{E[e(k)X(k)]\}$∇E=∂W∂E​=∂W∂​{E[(d(k)−WTX(k))2]}=−2{E[(d(k)−WTX(k))X(k)]}=−2{E[e(k)X(k)]}

• 期望本身还是没有办法求，但如果有大量的样本，可以求出大量的误差，可以用样本期望来代替

• 用一个样本来逼近：$e(k)X(k)\approx E[e(k)X(k)]$e(k)X(k)≈E[e(k)X(k)]

• LMS算法：

  • 初始化：$W(0)$W(0)为很小的随机数，$k\larr0$k←0

  • 使用随机LMS来更新权值

    $W(k+1)=W(k)+\alpha e(k)X(k)=W(k)+\alpha(d(k)-W^TX(k))X(k)$W(k+1)=W(k)+αe(k)X(k)=W(k)+α(d(k)−WTX(k))X(k)

    其中$\alpha$α为学习率，$0<\alpha\leq1$0<α≤1

  • 迭代知道收敛：$k\larr k+1$k←k+1

• 对该算法进行分析可得到结论，算法收敛的条件是：$\sum_k\alpha^2(k)<\infty,\sum_k\alpha(k)\rarr\infty$∑k​α2(k)<∞,∑k​α(k)→∞

通常将该算法就成为LMS算法。

最速下降法（The Steepest Descent Algorithm）

• 与随即逼近算法的区别为，不用单个样本的结果代替数学期望，而是使用N个样本来计算期望：

  $\frac{1}{N}\sum_p{e_p(k)X_p(k)}\approx E[e(k)X(k)]$N1​∑p​ep​(k)Xp​(k)≈E[e(k)X(k)]

• 这样使得梯度下降更快

• 有改进，但是计算量有增加

Madaline（Multiple Adalines）

• 多个线性单元构成的系统

应用实例

• 自适应滤波器

• 时间序列预测（天气预报）

  • 给定事时间序列$\{x(k),k=1,...,M\}${x(k),k=1,...,M}

    利用$x(t),x(t-1),...,x(t-p)$x(t),x(t−1),...,x(t−p)来预测$x(t+1)$x(t+1)

    求：$d(t)=x(t+1)$d(t)=x(t+1)

    $x(t+1)=\sum_{i=0}^{p-1}a_ix(t-i)+n(t)$x(t+1)=∑i=0p−1​ai​x(t−i)+n(t)使得$y(t)\rarr x(t+1)$y(t)→x(t+1)

    从而通过$y(t)=\sum_{i=0}^{p-1}a_ix(t-i)$y(t)=∑i=0p−1​ai​x(t−i)预测$d(t)$d(t)

• 陷波滤波器

• 信道均衡

  手机信号源为$a(t)$a(t)，发送出来后通过信道$h(t)$h(t)得到$a_h(t)$ah​(t)，信道中还有信号干扰$n(t)$n(t)，最后接收到的信号为$x(t)$x(t)，设计一个自适应信道均衡器，使输出$y(t)$y(t)逼近$a(t)$a(t)。

  思路：

  用自适应滤波来实现。

  在训练阶段使用固定信号来训练滤波器，即训练阶段知道$a(t)$a(t)能收集到输出$x(t)$x(t)，就可以进行训练。