0 引言

雷达告警接收机(Radar Warning Receiver, RWR)系统通过测量与分析照射到载机上的雷达信号，对截获雷达数据与雷达威胁数据库中的数据进行匹配来确定威胁雷达辐射源的类型、工作状态、方位、威胁等级等信息，从而对飞行员提供有效建议，采取有效措施^[1]。对于常规体制雷达，采用基于参数的雷达告警技术^[2]便可对雷达辐射源型号和工作状态进行有效识别。多功能雷达(Multi-Function Radar, MFR)为新体制雷达，是一种有源相控阵火控雷达^[3]，采用电子扫描技术和复杂的软件算法对波束进行控制，极大地提高了目标探测和跟踪能力；但这也导致雷达信号参数空间成指数增长，对RWR系统的数据存储和处理能力有着极高的要求，而且常规体制雷达的5大参数，即射频(Radio Frequency, RF)、到达方向(Direction Of Arrival, DOA)、到达时间(Time Of Arrival, TOA)、脉冲宽度(Pulse Width，PW)以及脉冲幅度(Pulse Amplitude, PA)，无法描述MFR工作模式的快速变化，使得RWR系统的工作性能急剧下降^[4]。为了克服MFR的动态性问题，Visnevski^[5]利用形式语言中的随机上下文无关文法(Stochastic Context-Free Grammar, SCFG)对MFR信号产生机制和工作模式进行动态分析和数学建模，提出了模式类的雷达告警技术。

在MFR文法建模的基础上，利用截获的雷达数据对文法产生式概率进行学习^[6]，对MFR参数和状态进行估计是模式类雷达告警技术中的核心问题。IO(Inside-Outside)算法^[7]和VS(Viterbi-Score)算法^[8]是两种常见的参数估计方法，文献[9]将期望最大化(Expectation-Maximization, EM)算法应用到IO算法和VS算法中对文法产生式概率进行学习，实现对MFR参数的估计，在得到文法参数后，再利用Viterbi算法实现对MFR状态的估计^[10]。IO算法通过寻求训练数据集的全局最大似然对文法产生式概率进行学习，计算量较大；而VS算法只寻求训练数据集的全局最优解的最大似然对文法产生式概率进行学习，相对于IO算法，虽然减小了计算量，但却牺牲了精度，所以这两种算法都无法满足RWR系统的实用需要。

针对上述问题，本文提出基于Earley算法^[11]的MFR文法概率快速学习算法，在原有IO算法和VS算法的基础上得到两种新的算法，即E(IO)算法和E(VS)算法。E(IO)算法通过对截获雷达数据进行预处理，构造Earley剖析表；加入点规则减少匹配中的冗余操作，以及能够反映规则匹配的状态；剖析表中的文法产生式都参与重估过程；E(VS)算法在E(IO)算法的基础上，基于最大子树概率原则从剖析表提取出最优剖析树，只有最优剖析树上的文法产生式参与重估过程。通过构造剖析表和加入点规则，可以解决有歧义文法产生式重复剖析、无效文法产生式重复剖析以及排除未参与派生过程的产生式等问题，从而对MFR参数和状态进行估计。通过理论分析和实验仿真，与IO算法和VS算法在计算复杂度、运行时间和状态估计精度等方面进行比较可知，E(IO)算法和E(VS)算法在保持估计精度的同时可以有效减少计算复杂度和运行时间，验证了Earley算法可以提高文法概率的学习速度。

1 MFR文法建模

对MFR进行文法建模，需要引入雷达脉冲信号、雷达字、雷达短语3个层级的雷达信号结构的概念。雷达字是MFR的最小辐射单元^[12]，为有限个数的雷达脉冲信号的固定排列，能够反映MFR的工作状态和威胁等级；而雷达短语是有限个数的雷达字的固定排列，每个短语对应一个雷达功能状态。因此可将MFR信号当成依据某种特定文法产生的形式语言，从而利用文法分析技术对MFR参数和状态进行估计。

其中上下文无关文法(Context-Free Grammar，CFG)结构简单、表达能力强、描述性好^[13]，因此可以利用CFG对MFR进行建模。一个CFG是一个四元组G={V, N, R, S}, 其中：V为非终结符的非空有穷集，表示雷达短语集合；N是终结符的非空有穷集，即雷达字集合，且N∩V=∅;R为产生式的非空有穷集，R中的元素具有形式A→λ, 其中A∈V, λ∈(V∪N)⁺, A→λ被称为产生式；S∈V, 为文法G的开始符号。SCFG为CFG的扩展，它是一个五元组G_S={V, N, R, S, P}, P为CFG文法产生式的概率，且P必须满足$\sum\limits_\lambda {P\left( {A \to \lambda } \right) = 1} $的约束条件^[14]。

基于SCFG建模的RWR系统如图 1所示。基于SCFG建模的RWR系统首先利用MFR信号模拟器模拟多部交错的雷达脉冲信号，通过接收机对雷达脉冲信号进行截获，脉冲序列中的脉冲描述字通过脉冲串分析器去交错后，利用TOA模板库进行雷达字提取^[15]。每一路雷达字通过序列识别模块进行MFR辐射源识别，每个SCFG模板对应一部特定的MFR。在确定MFR类型之后，再进行MFR文法概率快速学习，从而进行MFR参数和状态估计，最后进行威胁估计和态势分析，判定威胁等级，本文研究MFR文法概率快速学习的内容。

2 Earley算法描述

由文献[15]可知，一个随机文法G_S从初始符S开始产生序列η∈Lg(G_s)的最左导出称为η的派生过程。文法产生式序列的派生过程仅与文法结构有关，而与文法概率参数无关，所以本文利用Earley算法对每个雷达数据进行预处理，构造能描述派生过程的剖析表，并从中提取出最优剖析树，以降低计算复杂度和减少运行时间。

Earley算法是一种基于线图的、兼具自顶向下和自底向上优势的句法剖析方法，可以在O(n³)时间内处理任何上下文无关文法。它在剖析过程中加入了点规则^[16]，所谓点规则，是在规则的右部的终结符或非终结符之间的某一位置上加上一个圆点，表示右部被匹配的程度，可以反映规则匹配的状态，进一步减少了规则匹配中的冗余操作。

约定下文中使用以下记号^[17]:A, B, C, …代表任意非终结符；a, b, c, …代表任意终结符；α, β, γ, …代表由非终结符或终结符组成的任意序列。算法运算过程中输入符号串从左向右扫描，每读入输入符a_j, 分析器产生一个状态集S_j。状态集由形如[A→α·β, i]的分析项目组成，表示：

1)当前参与匹配的产生式是A→αβ;

2)产生式右部的α已匹配，而β将被匹配；

3)已匹配部分在输入串中的位置是i。

在构造剖析表时，为了能正确地列出所有项目，要完成Earley算法的三个操作：首先进行扫描运算，再进行完成运算，最后进行预测运算，直到剖析表稳定为止，这样就可以不遗漏所有的状态集^[18]。

输入一个随机上下文无关文法G={V, N, R, S, P}和一个输入符号串x=a₁a₂…a_n, 以此构造x的剖析表列I₀, I₁, …, I_n, 步骤^[19]如下：

1)I₀的构造。

步骤1  若S→α在R中，则把项目[S→·α, 0]添加到I₀。

步骤2  若[B→γ·0]在I₀中，则对所有[A→α·Bβ, 0], 把项目[A→αB·β, 0]添加到I₀。

步骤3  若[A→αB·β, 0]是I₀的一个项目，则对R中所有形如B→γ的产生式，把项目[B→γ·0]添加到I₀, 除非该项目已在I₀中。

重复步骤2、3，直至I₀中不增加新的内容为止。

2)由I₀, I₁, …, I_i, …, I_j-1构造I_j。

步骤4  对I_j-1中每个使a=a_j的[B→α·aβ, i], 把项目[B→αa·β, i]添加到I_j, 其中a_j是x的第j个终结符。

步骤5  令[A→α·, i]是I_j的一个项目，检查I_i以寻找形如[B→α·Aβ, k]的项目，对找到的每一个如此项目，把[B→αA·β, k]添加到I_j。

步骤6  令[A→α·aβ, i]是I_j的一个项目，对R中所有B→γ, 把项目[B→·γ, j]添加到I_j。

重复步骤5和步骤6，直到没有新项目可以添加到I_j, 使文法迭代至不能迭代为止。

3)判决。

x∈L(G)的充要条件为：I_n中有某个形为[S→α·, 0]的项目。

由上述步骤可以看出，不论文法产生式结构满足Chomsky正则形式，即R中只含有辐射规则A→w_j和转移规则A→BC两种形式的产生式, A, B, C∈V, w_j∈N, 还是文法产生式结构为任意形式的产生式，通过构造Earley剖析表、加入点规则和反映规则匹配的状态，能有效减少冗余操作，解决迭代过程中歧义产生式重复剖析、无效产生式重复剖析以及排除未参与派生过程的产生式等问题。所以将Earley算法应用到MFR文法概率快速学习中，可以大大降低计算复杂度和减少运行时间。

3 MFR文法概率快速学习方法

令x_1:m=(x₁, x₂, …, x_m)为未知的MFR状态序列，x_k∈N_r, N_r为雷达任务的集合，即雷达短语；η_1:n=(η₁, η₂, …, η_n)为截获的雷达命令中的n个终结符序列，每一个η_k=(w₁, w₂, …, w_k)代表一个雷达字，k为η_k的长度；只考虑文法产生式结构为Chomsky正则形式的情形。

定义如下2个变量：内部概率α_{A(i, j)}⁽ⁿ⁾=P(w_pq|A_pq^j, x_k=e_i, G_s)，表示G_s从非终结符A开始，生成终结符序列w_p, w_p+1, …, w_q的概率，k时刻雷达处于状态e_i; 外部概率β_{A(i, j)}⁽ⁿ⁾=P(w_1(p-1), A_pq^j, w_(q+1)m|x_k=e_i, G_s)，表示从G_s的起始符S开始生成非终结符A以及w_p, w_p+1, …, w_q外部所有终结符序列的概率，k时刻雷达处于状态e_i。图 2为SCFG中内部概率和外部概率示意图。

3.1 E(IO)算法对MFR概率参数估计

IO算法是一种传统的参数估计方法，用于对MFR文法概率快速学习，它寻求训练数据集的全局最大似然；E(IO)算法是一种改进的IO算法，在IO算法的基础上构造Earley剖析表，它寻求进入到剖析表中所有产生式的最大似然。具体算法步骤如下：

步骤1  自底向上计算内部概率。对于每一个训练序列x_1:m=(x₁, x₂, …, x_m), 若现在仅有一个终结符x_j, 则内部概率为：

$ \alpha _{A\left( {j - 1,j} \right)}^{\left( n \right)} = {P^{\left( n \right)}}\left( {A \to {w_j}} \right) $

(1)

若有多个终结符w_i, w_i+1…, w_j, 对内部概率进行递归计算：

$ \alpha _{A\left( {i,j} \right)}^{\left( n \right)} = \sum\limits_{B,C \in N} {\sum\limits_{i < k < j} {\alpha _{B\left( {i,j} \right)}^n} } \alpha _{C\left( {k,j} \right)}^n{P^n}\left( {A \to BC} \right) $

(2)

步骤2  自顶向下计算外部概率。首先确定初始训练序列：

$ \beta _{A\left( {0,m} \right)}^{\left( n \right)} = \left\{ \begin{array}{l} 1,\;\;\;\;A是初始符\\ 0,\;\;\;\;A不是初始符 \end{array} \right. $

(3)

再对外部概率进行递归计算：

$ \begin{array}{l} \beta _{A\left( {i,j} \right)}^{\left( n \right)} = \sum\limits_{B \in N} {\sum\limits_{C \in N} {\sum\limits_{k = j + 1}^m {\alpha _{C\left( {i,j} \right)}^n} } } \beta _{B\left( {i,k} \right)}^n{P^n}\left( {B \to AC} \right) + \\ \sum\limits_{B \in N} {\sum\limits_{C \in N} {\sum\limits_{k = 0}^{i - 1} {\alpha _{C\left( {k,i} \right)}^n} } } \beta _{B\left( {k,j} \right)}^n{P^n}\left( {B \to CA} \right) \end{array} $

(4)

步骤3  计算产生式的平衡频率和使用次数。

由步骤1、2可得，文法产生式的平衡频率为：

$ {f^{\left( n \right)}}\left( {A \to a} \right) = \sum\limits_{x \in \Omega } {\left[ {\frac{1}{{\alpha _{Start\left( {0,m} \right)}^{\left( n \right)}}}\sum\limits_{j\left| {{w_j} = a} \right.} {\beta _{A\left( {j - 1,j} \right)}^{\left( n \right)}} {P^{\left( n \right)}}\left( {A \to a} \right)} \right]} $

(5)

$ \begin{array}{l} {f^{\left( n \right)}}\left( {A \to BC} \right) = \\ \sum\limits_{x \in \Omega } {\left[ {\frac{1}{{\alpha _{Start\left( {0,m} \right)}^{\left( n \right)}}}\sum\limits_{0 \le i \le k \le j \le m} {\beta _{A\left( {i,j} \right)}^{\left( n \right)}} {\alpha _{B\left( {i,k} \right)}}\alpha _{C\left( {k,j} \right)}^n{P^{\left( n \right)}}\left( {A \to BC} \right)} \right]} \end{array} $

(6)

文法G_s⁽ⁿ⁾产生序列η_t时产生式的期望使用次数为：

$ {N^{\left( n \right)}}\left( {A \to a\left| {{\eta _t}} \right.} \right) = \sum\limits_{A\left( {j,j} \right) \to a} {\frac{{\beta _{A\left( {j,j} \right)}^{\left( n \right)}\alpha _{A\left( {i,j} \right)}^{\left( n \right)}}}{{\alpha _{S\left( {1,m} \right)}^{\left( n \right)}}}} $

(7)

$ {N^{\left( n \right)}}\left( {A \to BC\left| {{\eta _t}} \right.} \right) = \sum\limits_{B \in N} {\sum\limits_{C \in N} {\frac{{\beta _{A\left( {i,j} \right)}^{\left( n \right)}\alpha _{A\left( {i,k} \right)}^{\left( n \right)}\alpha _{A\left( {k,j} \right)}^{\left( n \right)}}}{{\alpha _{S\left( {1,m} \right)}^{\left( n \right)}}}} } $

(8)

步骤4  概率重估。经过迭代后文法产生式的概率可以估计为：

$ {P^{\left( {n + 1} \right)}}\left( {A \to \lambda } \right) = \frac{{{\eta ^{\left( n \right)}}\left( {A \to \lambda } \right)}}{{\sum\limits_\mu {{\eta ^{\left( n \right)}}\left( {A \to \mu } \right)} }} $

(9)

每经过一次迭代，模型的精确度和数据的似然性都会提高，当第n+1次迭代结果与第n次迭代结果的均方误差和小于0.1%时结束重估，这保证了每次迭代都会产生更优的模型参数，可以更好地进行MFR参数估计。

3.2 E(VS)算法对MFR概率参数估计

VS算法也是一种传统的参数估计方法，用于对MFR文法概率快速学习，它寻求训练数据集全局最优解的最大似然；E(VS)算法是一种改进的VS算法，在E(IO)算法的基础上，依据子树概率最大准则从Earley剖析表中提取最优剖析树，它只寻求最优剖析树上文法产生式的最大似然。具体算法步骤如下：

步骤1  自底向上计算内部概率。终结符序列w_i+1, w_i+2, …, w_j由非终结符A生成，若现在仅有一个终结符w_j, 最大内部概率为：

$ \bar \alpha _{A\left( {j - 1,j} \right)}^{\left( n \right)} = {P^{\left( n \right)}}\left( {A \to {w_j}} \right) $

(10)

对于子序列中包含不仅一个终结符的，最大内部概率为：

$ \bar \alpha _{A\left( {i,j} \right)}^{\left( n \right)} = \mathop {\max }\limits_{B,C \in N} \mathop {\max }\limits_{i < k < j} {P^{\left( n \right)}}\left( {A \to BC} \right)\bar \alpha _{B\left( {i,k} \right)}^{\left( n \right)}\bar \alpha _{C\left( {k,j} \right)}^{\left( n \right)} $

(11)

步骤2  计算最优剖析树的产生式平衡频率。令Φ保存每个最优子树的路径：

$ \Phi _{A\left( {i,j} \right)}^{\left( n \right)} = \mathop {\arg \;\max }\limits_{\left( {B,C,k} \right)} {p^{\left( n \right)}}\left( {A \to BC} \right)\alpha _{B\left( {i,k} \right)}^{\left( n \right)}\alpha _{C\left( {k + 1,j} \right)}^{\left( n \right)} $

(12)

由Φ开始从上到下迭代，可得序列的最优剖析树为：

$ {{\hat d}_x} = \mathop {\arg \;\max }\limits_{{d_x}} P\left( {x,{d_x}\left| {{G_s}} \right.} \right) $

(13)

其中d_x为所有剖析树序列，计算文法产生式平衡频率为：

$ {{\hat f}^{\left( n \right)}}\left( {A \to \lambda } \right) = \sum\limits_{x \in \Omega } {N\left( {A \to \lambda ,{{\hat d}_x}^{\left( n \right)}} \right)} $

(14)

步骤3  概率重估。方法与3.1节步骤4相同。

3.3 利用Viterbi算法对MFR状态估计

在迭代终止后，实现对MFR参数估计，得到文法参数后，可通过Viterbi算法对MFR状态进行估计。MFR在k时刻所处的状态估计为：

$ {{\hat x}_k} = \mathop {\arg \;\max }\limits_i P\left( {{x_k} = {e_i}\left| {{\eta _{1:n}}} \right.} \right) $

(15)

定义Viterbi变量为：

$ {\delta _i}\left( k \right) = \mathop {\max }\limits_{{x_0},{x_1}, \cdots ,{x_{k - 1}}} P\left( {{x_0},{x_1}, \cdots ,{x_k} = {e_i},{\eta _1},{\eta _2}, \cdots ,{\eta _k}} \right) $

(16)

利用Viterbi算法MFR对状态估计步骤如下：

步骤1  初始化：

$ {\delta _i}\left( 1 \right) = {\pi _i}{O_i}\left( {{\eta _1}} \right);1 \le i \le M $

(17)

步骤2  归纳法：

$ {\delta _i}\left( {k + 1} \right) = \mathop {\max }\limits_{1 \le j \le M} \left[ {{\delta _i}\left( k \right){\alpha _{ji}}\left( \psi \right)} \right]{O_i}\left( {{\eta _{k + 1}}} \right) $

(18)

$ {\psi _i}\left( {k + 1} \right) = \mathop {\arg \;\max }\limits_{1 \le j \le M} \left[ {{\delta _i}\left( k \right){\alpha _{ji}}} \right] $

(19)

步骤3  终止：

$ {{\hat x}_n} = \mathop {\arg \;\max }\limits_{1 \le j \le M} \left[ {{\delta _i}\left( n \right)} \right] $

(20)

步骤4  求解最佳转换状态序列：

$ {{\hat x}_k} = {\psi _{k + 1}}\left( {{{\hat x}_{k + 1}}} \right);k = n - 1,n - 2, \cdots ,1 $

(21)

通过对MFR状态进行估计，可以验证E(IO)算法和E(VS)算法在降低计算复杂度和减少运行时间的同时，估计精度的变化情况，以此验证改进算法的有效性。

4 实验仿真与分析 4.1 资源需求分析

计算复杂度T表示一个序列进行一次迭代所需要的乘法和除法次数。首先定义表 1中的变量。

在文法产生式概率均匀分布时的计算复杂度最大，此时以下近似需要被考虑：

$ \left| {{\varphi _t}} \right| = {M_{{\rm{nt}}}} \cdot \left( {{L^2} - 1} \right) $

(22)

$ \left| {{\varphi _{\rm{e}}}} \right| = {M_{{\rm{nt}}}} \cdot L $

(23)

$ \left| {\Delta {l_t}} \right| = M_{{\rm{nt}}}^2 \cdot L $

(24)

对于IO算法，其计算复杂度T_IO为：

$ \begin{array}{l} {T_{{\rm{IO}}}} = M \cdot \left[ {\frac{4}{3}M_{{\rm{nt}}}^3} \right. \cdot L \cdot \left( {{L^2} - 1} \right) + \\ \;\;\;\;\;\;\;\;{M_{{\rm{nt}}}} \cdot {M_{\rm{t}}}\left( {L + 2} \right) + \left( {{L^2} + 1} \right) + 2 \cdot \left. {M_{{\rm{nt}}}^3} \right] \end{array} $

(25)

对于VS算法，其计算复杂度T_VS为：

$ {T_{{\rm{VS}}}} = M \cdot \left\{ {M_{{\rm{nt}}}^3 \cdot \left[ {\left( {L \cdot \left( {{L^2} - 1} \right)/3} \right) + 1} \right]} \right\} $

(26)

对于E(IO)算法，其计算复杂度T_E(IO)为：

$ \begin{array}{l} {T_{{\rm{E}}\left( {{\rm{IO}}} \right)}}{\rm{ = }}M \cdot \left( {4 \cdot \left| {{\varphi _{\rm{t}}}} \right|} \right. \cdot \left| {\Delta {l_{\rm{t}}}} \right| + \\ \;\;\;\;\;\;\;\;\;2 \cdot \left| {{\varphi _{\rm{e}}}} \right| + M_{{\rm{nt}}}^3 + {M_{{\rm{nt}}}} \cdot \left. {{M_{\rm{t}}}} \right){\rm{ = }}\\ \;\;\;\;\;\;\;\;\;M_{{\rm{nt}}}^3 \cdot \left( {4{L^3} - 4L + 1} \right) + 2{M_{{\rm{nt}}}} \cdot L + {M_{{\rm{nt}}}} \cdot {M_{\rm{t}}} \end{array} $

(27)

对于E(VS)算法，其计算复杂度T_E(VS)为：

$ \begin{array}{l} {T_{{\rm{E}}\left( {{\rm{VS}}} \right)}} = \left| {{\varphi _{\rm{t}}}} \right| \cdot \left| {\Delta {l_{\rm{t}}}} \right| + M_{{\rm{nt}}}^3 + {M_{{\rm{nt}}}} \cdot {M_{\rm{t}}} = \\ \;\;\;\;\;\;\;\;\;\;\;M_{{\rm{nt}}}^3 \cdot \left( {{L^3} - L + 1} \right) \end{array} $

(28)

由于保密的原因，公开资料中涉及MFR识别的文献较少，并且各国的MFR名称、型号、参数等很少对外公布，对研究造成了很大影响。本文利用文献[5]中描述的“水星”MFR部分文法产生式进行计算，“水星”MFR有7个功能状态：搜索(Search，S1)状态，捕获扫描(ACQusition, ACQ)状态，非自适应性跟踪(NonAdaptive Track, NAT)状态，3个阶段的距离分辨(Range Resolution, RR)状态和跟踪保持(Track Maintenance, TM)状态。其部分文法产生式如下所示：S→ACQ RR; ACQ→ACQ NA|W₁W₁|W₂W₂|W₃W₃|W₄W₄; NAT→S1 TM; RR→RR NAT|RR_P ACQ; TM→W₂W₅; NAT→W₂|W₃; RR_P→W₄|W₅; S1→W₁|W₂|W₃; W₁→w₁; W₂→w₂; W₃→w₃; W₄→w₄; W₅→w₅。产生式中：S表示初始符号，RR_P中的p=(1, 2, 3), 符号w₁，w₂，w₃，w₄，w₅表示“水星”MFR的雷达字，其余符号均表示“水星”MFR的雷达短语。

由式(25)~(28)，计算“水星”MFR部分文法产生式在四种算法下前50个序列计算复杂度(算法运算量)大小，得到不同序列长度与不同算法的计算复杂度比较结果，如图 3所示。

由图 3可得：

$ {T_{{\rm{E}}\left( {{\rm{VS}}} \right)}} < {T_{{\rm{E}}\left( {{\rm{IO}}} \right)}} \ll {T_{{\rm{VS}}}} < {T_{{\rm{IO}}}} $

(29)

由式(29)可得，E(IO)算法和E(VS)算法通过对截获的雷达数据进行预处理，分别构造剖析表和最优剖析树，可以有效解决迭代过程中有歧义产生式重复剖析、无效产生式重复剖析以及排除未参与派生过程的产生式等问题，能够大幅度降低IO算法和VS算法的计算复杂度。

4.2 算法性能分析

为了验证Earley剖析算法的正确性，本文利用上述“水星”MFR部分产生式进行分析^[20]，设计了两个实验。

4.2.1 实验一

实验一通过改变训练序列个数和迭代次数，对算法的运行时间进行比较。假设“水星”MFR有两个状态，对应随机上下文无关文法G₁和G₂, 根据上述“水星”MFR部分文法产生式，令非终结符V={S, ACQ, RR, NAT, S1, TM, RR_P, W₁, W₂, W₃, W₄, W₅}，终结符N=(w₁, w₂, w₃, w₄, w₅), S为初始符。设状态转移矩阵A′=(0.8, 0.2;0.3, 0.7), 先令A′的Markov链随机产生一系列雷达状态，再对文法参数进行估计，最后经过100次蒙特卡洛实验，得到结果如图 4、5所示。

由图 4、5可知，随着序列数和迭代次数的增加，算法的运行时间逐渐增加，其中IO算法的运行时间最长，VS算法相对于IO算法只对训练数据集最优解进行训练，运行时间大大减少。E(IO)算法和E(VS)算法的运行时间相比VS算法减小了1/10以上，大大降低了算法的时间复杂度，实验所得的MFR参数估计值符合理论分析。

4.2.2 实验二

实验二通过对比四种算法在序列数和迭代次数增加时状态估计精度的变化情况来判别算法性能。当第n+1次迭代结果与第n次迭代结果的均方误差和小于0.1%时结束迭代，完成概率参数估计，得到文法参数后，利用Viterbi算法对MFR状态进行估计。设状态转移矩阵为A′=(0.9, 0.1;0.1, 0.9), 经过100次蒙特卡洛实验，结果如图 6、7所示。

由图 6、7可以看出，随着序列数和迭代次数的增加，状态估计精度会越来越高，IO算法和E(IO)算法的状态估计概率相同，而VS与E(VS)算法的状态估计精度相同。这说明E(IO)和E(VS)算法在有效降低计算复杂度和减少运行时间的前提下，始终可以保持状态估计精度，验证了Earley算法可以提高文法概率学习速度。

5 结语

本文针对基于SCFG建模的MFR参数和状态估计方法进行研究，在原有IO算法和VS算法的基础上，提出了E(IO)算法和E(VS)算法两种MFR文法概率快速学习算法。E(IO)算法通过对截获的雷达数据集进行预处理，在派生过程中加入点规则，构造Earley剖析表；E(VS)算法基于最大子树概率准则从剖析表中提取出最优剖析树。通过构造剖析表和最优剖析树，E(IO)算法和E(VS)算法可以解决迭代过程中有歧义产生式重复剖析、无效产生式重复剖析以及能排除未参与派生过程的产生式等问题，有效进行MFR参数估计。在得到文法参数后，利用Viterbi算法对MFR状态进行估计。通过理论分析和建模仿真表明，E(IO)算法和E(VS)算法在降低计算复杂度和减少运行时间的同时，可以有效保持状态估计精度，验证了Earley算法可以提高文法概率学习速度。