摘要:學習速率的取值問題當取值較大時,即梯度下降迭代的步長較大,梯度下降迭代過程較快。在處的次梯度集稱為微分集并表示為。在隨機梯度下降中,我們不要求更新方向完全基于梯度。相反,我們允許方向為隨機向量,并要求其期望值為當前向量處函數的次梯度。
假定給定函數:?,求解該函數的極小值時,k的取值是多少?
通常做法:對??求導,然后令導數=0,求解 k 值即為所求:
求導解法在復雜實際問題中很難計算。迭代法通過從一個初始估計出發尋找一系列近似解來解決優化問題。其基本形式如下:
其中??被稱為學習效率。
假設初始化??,為了通過迭代讓??趨近最優解2,?要滿足兩個條件:
- ?要能使??向最優解逼近。
- 當??達到最優解時,?要等于0。當??達到最優解的時候,?要等于?,即:
因此,我們的核心問題:尋找??滿足上述兩個要求。
隨著迭代的不斷進行,?可以使??向最優值逼近。而且,當??離最優值越近時,?的絕對值就越來越小。當達到最優解時,。
學習速率的取值問題:
- 當??取值較大時,即梯度下降迭代的步長較大,梯度下降迭代過程較快。可以快速迭代到最優解附近,但是可能一直在最優解附近徘徊,無法找出最優解。
- 當??取值較小時,即梯度下降迭代的步長較小,梯度下降迭代過程較慢。
梯度優化:方向+步長
可微函數的梯度??:?在? 處,?表示為是? 的偏導數的向量,即:
梯度下降是一種迭代算法:
- 從初始值? 開始。
- 在每次迭代中,我們沿著當前點梯度的負方向邁出下一步:
其中,?為學習率。直觀地說,該算法在梯度點的相反方向上邁出了一小步,從而降低了函數的值。在? 次迭代之后,算法輸出最后一個向量?。
輸出也可以是平均向量?。取平均值是非常有用的,特別是當我們將梯度下降推廣到不可微函數和隨機情況時。
【證明】,即:梯度不斷下降。
由于,。
由于?,學習率?,所以 ,故:
Lipschitz連續:對于在實數集的子集的函數?,若存在常數?,使得??,則稱函數?符合利普希茨條件。
為了分析GD算法的收斂速度,我們僅限于凸 Lipschitz 函數的情況。?是??在?條件下的最小值的點坐標。
- 假設:
- 求證:?有界
凸函數性質(1):
證明方法(1):
即,判斷上述關系即可:
從圖上可以看出,,且趨近于0時取等號。
故,
凸函數性質(2):
證明:將??進行泰勒展開可得:
?,且??處為偏導最小處,即??。
?,且??處為偏導最小處,即??。
即:
故:
因此:
?
合體證明性質(1)(2):
設? 是向量的任意序列。任何具有初始化? 和以下形式的更新規則的算法:
滿足:
前提(1):
前提(2):
證明:
即:
特別的,對每個??,如果對所有的??都存在??使得??,且對每個??且?,都存在:
證明:由前面可得
令?
令??,可得??得極小值,因此也是T的最小值。
且:
,當且僅當??
在允許一定誤差的情況下:對任意的??,使得:
則必須滿足:
即:,T 存在最小值。
次梯度方法是傳統的梯度下降方法的拓展,用來處理不可導的凸函數。它的優勢是比傳統方法處理問題范圍大,劣勢是算法收斂速度慢。
對于光滑的凸函數而言,我們可以直接采用梯度下降算法求解函數的極值,但是當函數不處處光滑、處處可微的時候,梯度下降就不適合應用了。因此,我們需要計算函數的次梯度。對于次梯度而言,其沒有要求函數是否光滑,是否是凸函數,限定條件很少,所以適用范圍更廣。
允許? 是一個開凸集。?函數? 是一個凸函數。滿足下列條件的向量?:
稱為? 在? 處的次梯度。?在?處的次梯度集稱為微分集并表示為 。?
【定義法】如果??在? 處可微,那么? 包含一個元素? 在? 處的梯度為?。例如:?。
?由于??在??處不可導,因此根據定義:
?
即:
【對比法】令??關于??的凸可微函數??。存在某些??使得??,則 ?。
此時,取值C,D處作為次梯度點。
證明:
前提:
選擇 C 作為次梯度點:
即,可得:
可得:
選擇 B? 作為次梯度點:
即,可得:
?此時,?無解,故不可作為次梯度點。
在隨機梯度下降中,我們不要求更新方向完全基于梯度。相反,我們允許方向為隨機向量,并要求其期望值為當前向量處函數的次梯度。
在隨機梯度下降中,我們不要求更新方向完全基于梯度。相反,我們允許方向為隨機向量,并要求其期望值為當前向量處函數的次梯度。
SGD偽碼:在學習問題的背景下,很容易找到期望值為風險函數次梯度的隨機向量。例如,每個樣本的風險函數梯度。
機器學習:支持向量機(SVM)_燕雙嚶-CSDN博客1,算法描述支持向量機(SVM)是用來解決分類問題的。作為數據挖掘領域中一項非常重要的任務,分類目前在商業上應用最多(比如分析型CRM里面的客戶分類模型、客戶流失模型、客戶盈利等,其本質上都屬于分類問題)。而分類的目的則是構造一個分類函數或分類模型,該模型能吧數據庫中的數據項映射到給定類別中的某一個,從而可以用來預測未知類別。先考慮最簡單的情況,比如豌豆和米粒,用篩子很快可以分離它們,小顆粒漏下去,大顆粒保留。用函數來表示就是當直徑d大于某個值D,就判定其為豌豆,小于D就是米粒。在數軸上就是D左邊https://shao12138.blog.csdn.net/article/details/121164645當最優化時的函數不是全區間可微時,無法通過對偶問題解決,此時可以使用SGD實現SVM。
為了應用SGD,我們必須將上式中的優化問題轉化為無約束問題:
更新規則:
求梯度可得:
:在迭代? 選擇的隨機例子上,?處損失函數的次梯度。
?特別的,對每個??,如果對所有的??都存在??使得??,且對每個??且?,都存在:
證明:
由2.3節證明的性質可得:
下面過程同2.4節,得:
,
故:
即證明:
同理,如果使得??都成立,則要求:
即:,T 存在最小值。
在之前對GD和SGD算法的分析中,我們要求??,這相當于對??劃定了一個半徑為??的區間,然后進行選擇。
但大部分時候我們無法保證全部的???的時候,可以采用增加投影的方法求解問題:?
,不考慮范圍求得一個值。
,然后投影到??上。
我們可以求得,D為最近的點,即投影點,B,E也是,但是不是最小的投影點。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/123509.html
摘要:在大量對象上應用了回歸分析甚至包括人的身高。孩子的高度向著平均高度回退回歸。回歸的目的是預測數值型的目標值。這就是監督學習算法的一個例子。 @toc 1 預測數值型數據:回歸 1.1 什么是回歸? 大自然讓我們回歸到一定的區間范圍之內;反過來說就是,有一個平均的水平,可以讓突出的事物能向他靠攏。 回歸是由達爾文(Charles Darwin)的表兄弟Francis Galton發明的...
摘要:在大量對象上應用了回歸分析甚至包括人的身高。孩子的高度向著平均高度回退回歸。回歸的目的是預測數值型的目標值。這就是監督學習算法的一個例子。 @toc 1 預測數值型數據:回歸 1.1 什么是回歸? 大自然讓我們回歸到一定的區間范圍之內;反過來說就是,有一個平均的水平,可以讓突出的事物能向他靠攏。 回歸是由達爾文(Charles Darwin)的表兄弟Francis Galton發明的...
摘要:在回歸分析中,只包括一個自變量和一個因變量,且二者的關系可用一條直線近似表示,這種回歸分析稱為一元線性回歸分析如果回歸分析中包括兩個及以上個自變量,且因變量和自變量直接是線性關系,則稱之為多元線性回歸分析。參考斯坦福大學機器學習公開課 定義 假設函數與代價函數(損失函數) 特征量放縮 最小化代價函數 收斂判定 1.什么是線性回歸 在統計學中,線性回歸是利用被稱為線性回歸方程的最小平...
閱讀 1735·2023-04-25 19:37
閱讀 1298·2021-11-16 11:45
閱讀 2802·2021-10-18 13:30
閱讀 2763·2021-09-29 09:34
閱讀 1615·2019-08-30 15:55
閱讀 3110·2019-08-30 11:10
閱讀 1833·2019-08-29 16:52
閱讀 994·2019-08-29 13:18