當前位置:首頁 » 操作系統 » 演算法的收斂性證明

演算法的收斂性證明

發布時間: 2023-07-17 13:42:16

1. 感知機演算法及收斂性證明

感知機演算法其實已經很熟悉了,這次看《統計學習方法》權當復習一遍,然後有一橘念個point對我來說是新的—— 感知機演算法實際上採用了隨機梯度下降 。這其實是一個很顯然的點,但我之前看到的資料都是直接說明了超平面參數的更新方式,並從幾何直觀上解釋了這樣做是為了讓超平面向誤分樣本點的方向旋轉,而未從梯度的角度來解釋,這里補充一下這個角度。

感知機(perceptron)是二分類線性分類模型,其輸入空間(特徵空間)是 ,輸出空間是 ,前伍簡由輸入空間到輸出空間的如下函數:

稱為感知機。 和 分別是感知機的權值和偏置。

感知機的損失函數定義為 所有誤分類點到超平面的距離慧褲之和 ,即:

其中 表示誤分類點的集合,若 固定,則損失函數梯度為:

採用隨機梯度下降法,每次隨機選取一個誤分類點 ,對 進行更新:

其中 稱為學習率。

感知機演算法流程如下:

(1)選取初值 。
(2)在訓練集中選取數據 。
(3)如果 ,則更新參數:

(4)轉至(2)直至訓練集中無誤分點。

所謂感知機演算法的收斂性,就是說只要給定而分類問題是線性可分的,那麼按上述感知機演算法進行操作,在有限次迭代後一定可以找到一個可將樣本完全分類正確的超平面。

首先,為了方便推導,我們將偏置 並入權重向量 ,記作 ,同樣將輸入向量加以擴充,記作 ,顯然, 。

既然樣本是線性可分的,我們可以假設有一個滿足條件 的超平面 將樣本點完全正確分開,且存在 ,對所有 ,有:

令 ,則感知機演算法在訓練集上誤分類次數 滿足:

證明:

結合上述兩個結論,可以得到:

從而感知機演算法的收斂性得證。

熱點內容
翻杯子演算法 發布:2025-03-16 03:34:31 瀏覽:602
ftp後台密碼怎麼設置 發布:2025-03-16 03:33:08 瀏覽:360
阿里雲伺服器的sdk是免費的嗎 發布:2025-03-16 03:33:04 瀏覽:7
卸載linux軟體 發布:2025-03-16 03:19:07 瀏覽:808
太平天國迅雷下載ftp 發布:2025-03-16 03:13:19 瀏覽:64
伺服器硬碟溫度怎麼調節 發布:2025-03-16 03:11:47 瀏覽:74
netcore編譯前執行代碼 發布:2025-03-16 03:05:17 瀏覽:475
飢荒聯機版伺服器搭建程序 發布:2025-03-16 02:55:18 瀏覽:684
win7如何訪問共享 發布:2025-03-16 02:55:14 瀏覽:37
centosphp升級 發布:2025-03-16 02:42:04 瀏覽:52