<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                企業??AI智能體構建引擎,智能編排和調試,一鍵部署,支持知識庫和私有化部署方案 廣告
                # 數據挖掘十大算法----EM算法(最大期望算法) > 來源:http://blog.csdn.net/u011067360/article/details/23702125 **概念** 在統計計算中,最大期望(EM)算法是在概率(probabilistic)模型中尋找參數最大似然估計或者最大后驗估計的算法,其中概率模型依賴于無法觀測的隱藏變量(Latent Variable)。 最大期望經常用在機器學習和計算機視覺的數據聚類(Data Clustering)領域。 可以有一些比較形象的比喻說法把這個算法講清楚。 比如說食堂的大師傅炒了一份菜,要等分成兩份給兩個人吃,顯然沒有必要拿來天平一點一點的精確的去稱分量,最簡單的辦法是先隨意的把菜分到兩個碗中,然后觀察是否一樣多,把比較多的那一份取出一點放到另一個碗中,這個過程一直迭代地執行下去,直到大家看不出兩個碗所容納的菜有什么分量上的不同為止。(來自百度百科) EM算法就是這樣,假設我們估計知道A和B兩個參數,在開始狀態下二者都是未知的,并且知道了A的信息就可以得到B的信息,反過來知道了B也就得到了A。可以考慮首先賦予A某種初值,以此得到B的估計值,然后從B的當前值出發,重新估計A的取值,這個過程一直持續到收斂為止。 EM算法還是許多非監督聚類算法的基礎(如Cheeseman et al. 1988),而且它是用于學習部分可觀察馬爾可夫模型(Partially Observable Markov Model)的廣泛使用的Baum-Welch前向后向算法的基礎。 ### 估計_k_個高斯分布的均值 介紹EM算法最方便的方法是通過一個例子。 考慮數據_D_是一實例集合,它由_k_個不同正態分布的混合所得分布所生成。該問題框架在下圖中示出,其中_k_=2而且實例為沿著_x_軸顯示的點。 每個實例使用一個兩步驟過程形成。 首先了隨機選擇_k_個正態分布其中之一。 其次隨機變量_x<sub>i</sub>_按照此選擇的分布生成。 這一過程不斷重復,生成一組數據點如圖所示。為使討論簡單化,我們考慮一個簡單情形,即單個正態分布的選擇基于統一的概率進行選擇,并且_k_個正態分布有相同的方差_σ_<sup>2</sup>,且_σ_<sup>2</sup>已知。 學習任務是輸出一個假設_h_=&lt;_μ<sub>1</sub>_…_μ<sub>k</sub>_&gt;,它描述了_k_個分布中每一個分布的均值。我們希望對這些均值找到一個極大似然假設,即一個使_P_(_D_|_h_)最大化的假設_h_。 ![](https://box.kancloud.cn/2016-02-11_56bc53035bf6e.png) 注意到,當給定從一個正態分布中抽取的數據實例_x_<sub>1</sub>,_x_<sub>2</sub>, …, _x<sub>m</sub>_時,很容易計算該分布的均值的極大似然假設。 其中我們可以證明極大似然假設是使_m_個訓練實例上的誤差平方和最小化的假設。 使用當表述一下式,可以得到: ![](https://box.kancloud.cn/2016-02-11_56bc53037906f.png)(公式一) 然而,在這里我們的問題涉及到_k_個不同正態分布的混合,而且我們不能知道哪個實例是哪個分布產生的。因此這是一個涉及隱藏變量的典型例子。 **EM算法步驟** 在上圖的例子中,可把每個實例的完整描述看作是三元組&lt;_x<sub>i</sub>_,_z<sub>i</sub>_<sub>1</sub>, _z<sub>i</sub>_<sub>2</sub>&gt;,其中_x<sub>i</sub>_是第_i_個實例的觀測值,_z<sub>i</sub>_<sub>1</sub>和_z<sub>i</sub>_<sub>2</sub>表示兩個正態分布中哪個被用于產生值_x<sub>i</sub>_。 確切地講,_z<sub>ij</sub>_在_x<sub>i</sub>_由第_j_個正態分布產生時值為1,否則為0。這里_x<sub>i</sub>_是實例的描述中已觀察到的變量,_z<sub>i</sub>_<sub>1</sub>和_z<sub>i</sub>_<sub>2</sub>是隱藏變量。如果_z<sub>i</sub>_<sub>1</sub>和_z<sub>i</sub>_<sub>2</sub>的值可知,就可以用式一來解決均值_μ_<sub>1</sub>和_μ_<sub>2</sub>。因為它們未知,因此我們只能用EM算法。 EM算法應用于我們的_k_均值問題,目的是搜索一個極大似然假設,方法是根據當前假設&lt;_μ_<sub>1</sub>…_μ<sub>k</sub>_&gt;不斷地再估計隱藏變量_z<sub>ij</sub>_的期望值。然后用這些隱藏變量的期望值重新計算極大似然假設。這里首先描述這一實例化的EM算法,以后將給出EM算法的一般形式。 為了估計上圖中的兩個均值,EM算法首先將假設初始化為_h_=&lt;_μ_<sub>1</sub>,_μ_<sub>2</sub>&gt;,其中_μ_<sub>1</sub>和_μ_<sub>2</sub>為任意的初始值。然后重復以下的兩個步驟以重估計_h_,直到該過程收斂到一個穩定的_h_值。 步驟1:計算每個隱藏變量_z<sub>ij</sub>_的期望值_E_[_z<sub>ij</sub>_],假定當前假設_h_=&lt;_μ_<sub>1</sub>,_μ_<sub>2</sub>&gt;成立。 步驟2:計算一個新的極大似然假設_h_′=&lt;_μ_<sub>1</sub>′,_μ_<sub>2</sub>′&gt;,假定由每個隱藏變量_z<sub>ij</sub>_所取的值為第1步中得到的期望值_E_[_z<sub>ij</sub>_],然后將假設_h_=&lt;_μ_<sub>1</sub>,_μ_<sub>2</sub>&gt;替換為新的假設_h_′=&lt;_μ_<sub>1</sub>′,_μ_<sub>2</sub>′&gt;,然后循環。 現在考察第一步是如何實現的。步驟1要計算每個_z<sub>ij</sub>_的期望值。此_E_[_z<sub>ij</sub>_]正是實例_x<sub>i</sub>_由第_j_個正態分布生成的概率: ![](https://box.kancloud.cn/2016-02-11_56bc530386d61.png) ![](https://box.kancloud.cn/2016-02-11_56bc5303929d7.png) ? 因此第一步可由將當前值&lt;_μ_<sub>1</sub>,_μ_<sub>2</sub>&gt;和已知的_x<sub>i</sub>_代入到上式中實現。 在第二步,使用第1步中得到的_E_[_z<sub>ij</sub>_]來導出一新的極大似然假設_h_′=&lt;_μ_<sub>1</sub>′,_μ_<sub>2</sub>′&gt;。如后面將討論到的,這時的極大似然假設為: ![](https://box.kancloud.cn/2016-02-11_56bc5303a1a95.png) 注意此表達式類似于公式一中的樣本均值,它用于從單個正態分布中估計_μ_。新的表達式只是對_μ<sub>j</sub>_的加權樣本均值,每個實例的權重為其由第_j_個正態分布產生的期望值。 **上面估計_k_個正態分布均值的算法描述了EM方法的要點**:即當前的假設用于估計未知變量,而這些變量的期望值再被用于改進假設。 可以證明,在此算法第一次循環中,EM算法能使似然性_P_(_D_|_h_)增加,除非它已達到局部的最大。因此該算法收斂到對于&lt;_μ_<sub>1</sub>,_μ_<sub>2</sub>&gt;的一個局部極大可能性假設。 **? EM算法的一般表述** 上面的EM算法針對的是估計混合正態分布均值的問題。更一般地,EM算法可用于許多問題框架,其中需要估計一組描述基準概率分布的參數_θ_,只給定了由此分布產生的全部數據中能觀察到的一部分。 在上面的二均值問題中,感興趣的參數為_θ_=&lt;_μ_<sub>1</sub>,_μ_<sub>2</sub>&gt;,而全部數據為三元組&lt;_x<sub>i</sub>_,_z<sub>i</sub>_<sub>1</sub>, _z<sub>i</sub>_<sub>2</sub>&gt;,而只有_x<sub>i</sub>_可觀察到,一般地令_X_=&lt;_x_<sub>1</sub>, …,_x<sub>m</sub>_&gt;代表在同樣的實例中已經觀察到的數據,并令_Y_=_X_∪_Z_代表全體數據。注意到未觀察到的_Z_可被看作一隨機變量,它的概率分布依賴于未知參數_θ_和已知數據_X_。類似地,_Y_是一隨機變量,因為它是由隨機變量_Z_來定義的。在后續部分,將描述EM算法的一般形式。使用_h_來代表參數_θ_的假設值,而_h_′代表在EM算法的每次迭代中修改的假設。 EM算法通過搜尋使_E_[ln_P_(_Y_|_h_′)]最大的_h_′來尋找極大似然假設_h_′。此期望值是在_Y_所遵循的概率分布上計算,此分布由未知參數_θ_確定。考慮此表達式究竟意味了什么。 首先_P_(_Y_|_h_′)是給定假設_h_′下全部數據_Y_的似然性。其合理性在于我們要尋找一個_h_′使該量的某函數值最大化。 其次使該量的對數ln_P_(_Y_|_h_′)最大化也使_P_(_Y_|_h_′)最大化,如已經介紹過的那樣。 第三,引入期望值_E_[ln_P_(_Y_|_h_′)]是因為全部數據_Y_本身也是一隨機變量。 已知全部數據_Y_是觀察到的_X_和未觀察到的_Z_的合并,我們必須在未觀察到的_Z_的可能值上取平均,并以相應的概率為權值。換言之,要在隨機變量_Y_遵循的概率分布上取期望值_E_[ln_P_(_Y_|_h_′)]。該分布由完全已知的_X_值加上_Z_服從的分布來確定。 _Y_遵從的概率分布是什么?一般來說不能知道此分布,因為它是由待估計的_θ_參數確定的。然而,EM算法使用其當前的假設_h_代替實際參數_θ_,以估計_Y_的分布。現定義一函數_Q_(_h_′|_h_),它將_E_[ln_P_(_Y_|_h_′)]作為_h_′的一個函數給出,在_θ_=_h_和全部數據_Y_的觀察到的部分_X_的假定之下。 ![](https://box.kancloud.cn/2016-02-11_56bc5303b0269.png) 將_Q_函數寫成_Q_(_h_′|_h_)是為了表示其定義是在當前假設_h_等于_θ_的假定下。在EM算法的一般形式里,它重復以下兩個步驟直至收斂。 步驟1:估計(E)步驟:使用當前假設_h_和觀察到的數據_X_來估計_Y_上的概率分布以計算_Q_(_h_′|_h_)。 ![](https://box.kancloud.cn/2016-02-11_56bc5303bd797.png) 步驟2:最大化(M)步驟:將假設_h_替換為使_Q_函數最大化的假設_h_′: ![](https://box.kancloud.cn/2016-02-11_56bc5303cb21d.png) 當函數_Q_連續時,EM算法收斂到似然函數_P_(_Y_|_h_′)的一個不動點。若此似然函數有單個的最大值時,EM算法可以收斂到這個對_h_′的全局的極大似然估計。否則,它只保證收斂到一個局部最大值。因此,EM與其他最優化方法有同樣的局限性,如之前討論的梯度下降,線性搜索和變形梯度等。 總結來說,EM算法就是通過迭代地最大化完整數據的對數似然函數的期望,來最大化不完整數據的對數似然函數。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看