3.3.2　期望最大化填補法

3.3.1節詳細介紹了極大似然估計法，期望最大化填補法是基于極大似然估計法的缺失值填補方法。在該方法中，缺失值作為變量參與到參數估計過程中，以迭代的方式交替更新缺失值與待估計參數，以此達到缺失值填補的目標。

針對數據集X中第c類樣本構成的子集X^(c)，假設其中的所有現有值構成集合Xp^(c)，而所有的缺失值構成集合X_m^(c)。對參數向量β^(c)進行估計時，需最大化式（3-85）所示的對數似然函數：

由于X_m^(c)為缺失值，故無法參照3.3.1節中的描述估計參數向量β^(c)。此時，可采用期望最大化算法以迭代的方式在估計參數的同時進行缺失值填補。該算法每輪迭代包括兩個步驟，即期望步和最大化步，以下簡稱E步和M步。在E步中，根據參數向量β^(c)和現有值計算缺失值；在M步中，根據填補結果對參數向量β^(c)進行極大似然估計。為了更加具體地說明填補過程，下面給出一個例子。

現在有3個編號分別為A、B、C的箱子，每個箱子中都有黑白兩種球，各箱子中黑球所占的比例分別為p_A、p_B、p_C。實驗步驟如下：從箱子A中取出一個球，若為黑球，則從箱子B中取出一個球；若為白球，則從箱子C中取出一個球。箱子B或箱子C所抽取球的顏色即為實驗結果。對于抽取球的顏色，如果是黑色則記為1，如果是白色則記為0。獨立重復實驗N次，假設每次實驗只能觀測到最終實驗結果，不能觀測抽取過程，則對于此實驗而言，箱子A的抽取結果可視作缺失值，待估計參數p_A、p_B、p_C組成參數向量β=[p_A,p_B,p_C]。下面通過EM算法對參數向量β進行極大似然估計，并同時填補箱子A的抽取結果。

如3.3.1節所述，極大似然估計法的目的是：利用已知的樣本結果，反推最大概率導致這種結果的參數值。本節加入EM算法的目的則是在估計參數值的同時進行缺失值填補。在上述黑白球問題中，每次獨立重復實驗的結果是完整的，N次實驗的結果被記為Y=[y₁,y₂,…,y_N]；箱子A的抽取結果是缺失的，該抽取結果記為Z=[z₁,z₂,…,z_N]，其僅有兩種可能的取值，即1或0。

根據式（3-75），參數向量β=[p_A,p_B,p_C]對于Y=[y₁,y₂,…,y_N]和Z=[z₁,z₂,…,z_N]的似然函數如式（3-86）所示：

式中，P(y_i,z_i|β)為在參數向量β條件下y_i、z_i的概率分布。基于式（3-86）所得的對數似然函數如式（3-87）所示：

極大似然估計的目標為尋找使得該對數似然函數取最大值的參數向量，其目標函數如式（3-88）所示：

由于Z=[z₁,z₂,…,z_N]為缺失數據，故采用EM算法在填補缺失值的基礎上進行參數估計。在EM算法開始之前，需隨機初始化參數向量β=[p_A,p_B,p_C]，記該初始參數向量為β⁽⁰⁾。EM算法采用迭代的方式交替更新填補值和待估計參數，每輪迭代分為E步和M步。假設迭代次數的上限為L，則第l次迭代中，E步可分為兩個階段，第一階段基于現有數據Y=[y₁,y₂,…,y_N]和當前參數向量β^(l-1)=[p_A^(l-1),p_B^(l-1),p_C^(l-1)]填補缺失值，第二階段基于填補結果求對數似然函數H(β)的期望。在第一階段中，由于Z為離散變量，故在缺失值填補時將該變量取各離散值的概率作為填補結果。對于z_i∈Z，其取值范圍為{0,1}，根據概率學的相關知識求得其取值為1的概率，如式（3-89）所示：

式（3-89）中，P(y_i,z_i=1|β^(l-1))的計算過程如式（3-90）所示：

同理可得，P(y_i,z_i=0|β^(l-1))如式（3-91）所示：

將式（3-90）和式（3-91）帶入式（3-89），所得結果如式（3-92）所示：

由式（3-92）可見，z_i=1的概率完全可由y_i和β^(l-1)表示，即根據現有值y_i和參數向量β^(l-1)計算出離散變量z_i的填補值。為方便描述，記μ_i^(l)=P(z_i=1|y_i,β^(l-1))為第l次迭代中z_i取值為1的概率，則z_i=0的概率如式（3-93）所示：

在第二階段中，基于填補結果組成的向量Z求對數似然函數H(β)的期望，計算方法如式（3-94）所示：

式（3-94）中，P(y_i,z_i=1|β^(l-1))和P(y_i,z_i=0|β^(l-1))分別如式（3-90）和式（3-91）所示，P(z_i=1|y_i,β^(l-1))和P(z_i=0|y_i,β^(l-1))分別如式（3-92）和式（3-93）所示。因此，第二階段基于填補結果所得對數似然函數H(β)的期望如式（3-95）所示：

在M步中，對各參數求偏導得到使式（3-95）期望最大化的參數值。對于第l輪迭代(l=1,2,…,δ)，M步所求參數組成的參數向量為β^(l)=[p_A^(l),p_B^(l),p_C^(l)]。

該期望對參數p_A的偏導如式（3-96）所示：

對式（3-96）簡化得式（3-97）：

同理，可求得參數p_B和p_C的更新規則，分別如式（3-98）和式（3-99）所示：

每一輪迭代分E步和M步進行，在E步，首先根據式（3-89）和式（3-93）更新填補值，隨后基于填補結果根據式（3-95）計算對數似然函數的期望；在M步，根據式（3-97）、式（3-98）和式（3-99）進行參數估計。重復上述迭代直到兩次迭代之間的參數更新幅度小于設定的閾值，或迭代次數達到上限。最后一輪迭代的填補值為最終填補結果，該輪迭代中M步估計的參數為極大似然估計結果。

基于上述黑白球實例對期望最大化填補法進行提煉總結。假設數據集X中第c類樣本構成子集X^(c)，其中現有值的集合為X_p^(c)，缺失值的集合為X_m^(c)，其中樣本分布由參數向量β^(c)唯一確定。以下為期望最大化算法填補缺失值的流程。

步驟1：初始化參數向量β^(c)，EM算法的閾值為ε，迭代次數上限為L；

步驟2：構建參數向量β^(c)對于子集X^(c)的對數似然函數，如式（3-100）所示：

在式（3-100）的基礎上設定如式（3-101）所示的優化目標：

式中，^(c)表示使H(β^(c))達到最大值的參數向量β^(c)取值；

步驟3：根據當前參數和現有值進行缺失值填補，即E步的第一階段。第l輪迭代(l=1,2,…,L)獲得的填補值可表示為_m^(c)(l)；

步驟4：基于填補結果_m^(c)(l)計算極大似然函數的期望，即E步的第二階段，記為；

步驟5：對各參數求偏導計算使該期望取最大值的參數值，即M步。第l輪迭代（l=1,2,…,δ）獲得的參數向量記為β^(c)(l)；

步驟6：如果兩輪迭代參數的變化幅度小于閾值ε，或迭代次數達到上限L，則迭代結束。將最后一輪的填補值作為最終填補結果，記為_m^(c)，最后一輪求得的參數向量為極大似然估計結果，記為^(c)；否則，返回步驟3。

期望最大化填補法以極大似然估計法作為理論基礎，采用迭代的方式填補缺失值，對數據集中完整數據的利用較為充分，通常能夠獲得較為精確的填補結果。但該方法的精度與缺失率相關，當缺失率太大時，上述迭代優化過程容易陷入局部最優解，在影響填補精度的同時還會導致方法的收斂速度顯著降低。