PyTorch教程-12.2. 凸度

凸性在優(yōu)化算法的設(shè)計(jì)中起著至關(guān)重要的作用。這主要是因?yàn)樵谶@種情況下分析和測(cè)試算法要容易得多。換句話說(shuō)，如果算法即使在凸設(shè)置中也表現(xiàn)不佳，通常我們不應(yīng)該希望在其他情況下看到很好的結(jié)果。此外，盡管深度學(xué)習(xí)中的優(yōu)化問(wèn)題通常是非凸的，但它們通常在局部最小值附近表現(xiàn)出凸問(wèn)題的某些性質(zhì)。這可能會(huì)導(dǎo)致令人興奮的新優(yōu)化變體，例如 ( Izmailov et al. , 2018 )。

%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l

%matplotlib inline
from mpl_toolkits import mplot3d
from mxnet import np, npx
from d2l import mxnet as d2l

npx.set_np()

%matplotlib inline
import numpy as np
import tensorflow as tf
from mpl_toolkits import mplot3d
from d2l import tensorflow as d2l

12.2.1。定義

在凸分析之前，我們需要定義凸集和凸函數(shù)。它們導(dǎo)致了通常應(yīng)用于機(jī)器學(xué)習(xí)的數(shù)學(xué)工具。

12.2.1.1。凸集

集合是凸性的基礎(chǔ)。簡(jiǎn)單的說(shuō)，一套X 在向量空間中是凸的，如果對(duì)于任何a,b∈X 連接的線段a和b也在 X. 用數(shù)學(xué)術(shù)語(yǔ)來(lái)說(shuō)，這意味著對(duì)于所有 λ∈[0,1]我們有

(12.2.1)λa+(1?λ)b∈Xwhenevera,b∈X.

這聽(tīng)起來(lái)有點(diǎn)抽象?？紤]圖 12.2.1。第一組不是凸的，因?yàn)榇嬖诓话谄渲械木€段。其他兩組沒(méi)有這樣的問(wèn)題。

圖 12.2.1第一組是非凸的，另外兩組是凸的。

定義本身并不是特別有用，除非您可以對(duì)它們做些什么。在這種情況下，我們可以查看如圖 12.2.2所示的交叉點(diǎn)。假使，假設(shè)X和 Y是凸集。然后 X∩Y也是凸的。要看到這一點(diǎn)，請(qǐng)考慮任何a,b∈X∩Y. 自從 X和Y是凸的，連接的線段a和b都包含在 X和Y. 鑒于此，它們還需要包含在X∩Y，從而證明了我們的定理。

圖 12.2.2兩個(gè)凸集的交集是凸的。

我們可以毫不費(fèi)力地加強(qiáng)這個(gè)結(jié)果：給定凸集 Xi, 他們的交集∩iXi 是凸的。要看到相反的情況不成立，請(qǐng)考慮兩個(gè)不相交的集合X∩Y=?. 現(xiàn)在挑 a∈X和b∈Y. 圖 12.2.3中的線段連接a和b 需要包含一些既不在X也不在 Y, 因?yàn)槲覀兗僭O(shè) X∩Y=?. 因此線段不在X∪Y要么，從而證明通常凸集的并集不一定是凸的。

圖 12.2.3兩個(gè)凸集的并集不一定是凸集。

通常，深度學(xué)習(xí)中的問(wèn)題是在凸集上定義的。例如，Rd, 的集合d維實(shí)數(shù)向量，是一個(gè)凸集（畢竟，在任何兩點(diǎn)之間的線Rd留在Rd). 在某些情況下，我們使用有界長(zhǎng)度的變量，例如半徑為 r定義為 {x|x∈Rdand‖x‖≤r}.

12.2.1.2。凸函數(shù)

現(xiàn)在我們有了凸集，我們可以引入凸函數(shù) f. 給定一個(gè)凸集X, 一個(gè)函數(shù) f:X→R是凸的，如果對(duì)所有 x,x′∈X對(duì)于所有人λ∈[0,1]我們有

(12.2.2)λf(x)+(1?λ)f(x′)≥f(λx+(1?λ)x′).

為了說(shuō)明這一點(diǎn)，讓我們繪制一些函數(shù)并檢查哪些函數(shù)滿足要求。下面我們定義了幾個(gè)函數(shù)，包括凸函數(shù)和非凸函數(shù)。

f = lambda x: 0.5 * x**2 # Convex
g = lambda x: torch.cos(np.pi * x) # Nonconvex
h = lambda x: torch.exp(0.5 * x) # Convex

x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
  d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

f = lambda x: 0.5 * x**2 # Convex
g = lambda x: np.cos(np.pi * x) # Nonconvex
h = lambda x: np.exp(0.5 * x) # Convex

x, segment = np.arange(-2, 2, 0.01), np.array([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
  d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

f = lambda x: 0.5 * x**2 # Convex
g = lambda x: tf.cos(np.pi * x) # Nonconvex
h = lambda x: tf.exp(0.5 * x) # Convex

x, segment = tf.range(-2, 2, 0.01), tf.constant([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
  d2l.plot([x, segment], [func(x), func(segment)], axes=ax)

正如預(yù)期的那樣，余弦函數(shù)是非凸的，而拋物線和指數(shù)函數(shù)是。請(qǐng)注意，要求 X是一個(gè)凸集是使條件有意義所必需的。否則結(jié)果 f(λx+(1?λ)x′)可能沒(méi)有明確定義。

12.2.1.3。詹森不等式

給定一個(gè)凸函數(shù)f，最有用的數(shù)學(xué)工具之一是詹森不等式。它相當(dāng)于凸性定義的概括：

(12.2.3)∑iαif(xi)≥f(∑iαixi)andEX[f(X)]≥f(EX[X]),

在哪里αi是非負(fù)實(shí)數(shù)使得 ∑iαi=1和X是一個(gè)隨機(jī)變量。換句話說(shuō)，凸函數(shù)的期望不亞于期望的凸函數(shù)，后者通常是更簡(jiǎn)單的表達(dá)式。為了證明第一個(gè)不等式，我們一次重復(fù)將凸性的定義應(yīng)用于總和中的一項(xiàng)。

Jensen 不等式的一個(gè)常見(jiàn)應(yīng)用是用一個(gè)更簡(jiǎn)單的表達(dá)式來(lái)約束一個(gè)更復(fù)雜的表達(dá)式。例如，它的應(yīng)用可以關(guān)于部分觀察到的隨機(jī)變量的對(duì)數(shù)似然。也就是說(shuō)，我們使用

(12.2.4)EY～P(Y)[?log?P(X∣Y)]≥?log?P(X),

自從∫P(Y)P(X∣Y)dY=P(X). 這可以用于變分法。這里Y通常是未觀察到的隨機(jī)變量，P(Y)是對(duì)它可能如何分布的最佳猜測(cè)，并且P(X)是分布Y整合出來(lái)。例如，在聚類Y可能是集群標(biāo)簽和 P(X∣Y)是應(yīng)用集群標(biāo)簽時(shí)的生成模型。

12.2.2。特性

凸函數(shù)有許多有用的性質(zhì)。我們?cè)谙旅婷枋隽艘恍┏Ｓ玫摹?/p>

12.2.2.1。局部最小值是全局最小值

首先，凸函數(shù)的局部最小值也是全局最小值。我們可以用反證法證明如下。

考慮一個(gè)凸函數(shù)f定義在凸集上 X. 假設(shè)x?∈X是局部最小值：存在一個(gè)小的正值p這樣對(duì)于 x∈X滿足 0<|x?x?|≤p我們有f(x?)

假設(shè)局部最小值x?不是全局最小值f： 那里存在x′∈X為了哪個(gè) f(x′)

然而，根據(jù)凸函數(shù)的定義，我們有

(12.2.5)f(λx?+(1?λ)x′)≤λf(x?)+(1?λ)f(x′)<λf(x?)+(1?λ)f(x?)=f(x?),

這與我們的聲明相矛盾x?是局部最小值。因此，不存在x′∈X為了哪個(gè)f(x′)

例如，凸函數(shù)f(x)=(x?1)2有一個(gè)局部最小值x=1，這也是全局最小值。

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')

凸函數(shù)的局部最小值也是全局最小值這一事實(shí)非常方便。這意味著如果我們最小化功能，我們就不會(huì)“卡住”。但是請(qǐng)注意，這并不意味著不能有一個(gè)以上的全局最小值，或者甚至可能存在一個(gè)。例如，函數(shù)f(x)=max(|x|?1,0) 在區(qū)間內(nèi)達(dá)到最小值[?1,1]. 相反，函數(shù)f(x)=exp?(x)沒(méi)有達(dá)到最小值 R： 為了x→?∞它漸近于 0, 但沒(méi)有x為了哪個(gè)f(x)=0.

12.2.2.2。下面的凸函數(shù)集是凸的

我們可以通過(guò)下面的一組凸函數(shù)方便地定義凸集。具體來(lái)說(shuō)，給定一個(gè)凸函數(shù)f定義在凸集上X, 任何以下集合

(12.2.6)Sb=def{x|x∈Xandf(x)≤b}

是凸的。

讓我們快速證明這一點(diǎn)。回想一下，對(duì)于任何 x,x′∈Sb我們需要證明 λx+(1?λ)x′∈Sb只要 λ∈[0,1]. 自從f(x)≤b和 f(x′)≤b, 根據(jù)凸性的定義我們有

(12.2.7)f(λx+(1?λ)x′)≤λf(x)+(1?λ)f(x′)≤b.

12.2.2.3。凸性和二階導(dǎo)數(shù)

每當(dāng)函數(shù)的二階導(dǎo)數(shù) f:Rn→R存在很容易檢查是否f是凸的。我們需要做的就是檢查 Hessian 是否f是半正定的： ?2f?0，即表示Hessian矩陣 ?2f經(jīng)過(guò)H, x?Hx≥0對(duì)全部 x∈Rn. 例如，函數(shù) f(x)=12‖x‖2是凸的，因?yàn)??2f=1，即它的 Hessian 矩陣是一個(gè)單位矩陣。

形式上，一個(gè)二次可微分的一維函數(shù) f:R→R是凸的當(dāng)且僅當(dāng)它的二階導(dǎo)數(shù)f″≥0. 對(duì)于任何二次可微的多維函數(shù) f:Rn→R, 它是凸的當(dāng)且僅當(dāng)它是 Hessian 矩陣?2f?0.

首先，我們需要證明一維情況?？吹降耐剐詅暗示f″≥0我們使用這樣的事實(shí)

(12.2.8)12f(x+?)+12f(x??)≥f(x+?2+x??2)=f(x).

由于二階導(dǎo)數(shù)由有限差分的極限給出，因此

(12.2.9)f″(x)=lim?→0f(x+?)+f(x??)?2f(x)?2≥0.

看到那個(gè)f″≥0暗示f是凸的，我們使用這個(gè)事實(shí)f″≥0暗示f′是單調(diào)非遞減函數(shù)。讓a

(12.2.10)f′(α)=f(x)?f(a)x?aandf′(β)=f(b)?f(x)b?x.

通過(guò)單調(diào)性f′(β)≥f′(α)， 因此

(12.2.11)x?ab?af(b)+b?xb?af(a)≥f(x).

自從x=(1?λ)a+λb， 我們有

(12.2.12)λf(b)+(1?λ)f(a)≥f((1?λ)a+λb),

從而證明凸性。

其次，在證明多維情況之前我們需要一個(gè)引理： f:Rn→R是凸的當(dāng)且僅當(dāng)對(duì)所有x,y∈Rn

(12.2.13)g(z)=deff(zx+(1?z)y)wherez∈[0,1]

是凸的。

為了證明凸性f暗示g是凸的，我們可以證明對(duì)于所有a,b,λ∈[0,1]（因此 0≤λa+(1?λ)b≤1)

(12.2.14)g(λa+(1?λ)b)=f((λa+(1?λ)b)x+(1?λa?(1?λ)b)y)=f(λ(ax+(1?a)y)+(1?λ)(bx+(1?b)y))≤λf(ax+(1?a)y)+(1?λ)f(bx+(1?b)y)=λg(a)+(1?λ)g(b).

為了證明相反的情況，我們可以證明對(duì)于所有 λ∈[0,1]

(12.2.15)f(λx+(1?λ)y)=g(λ?1+(1?λ)?0)≤λg(1)+(1?λ)g(0)=λf(x)+(1?λ)f(y).

最后，利用上面的引理和一維情況的結(jié)果，多維情況可以證明如下。多維函數(shù) f:Rn→R是凸的當(dāng)且僅當(dāng)對(duì)所有x,y∈Rn g(z)=deff(zx+(1?z)y)， 在哪里z∈[0,1], 是凸的。根據(jù)一維情況，這成立當(dāng)且僅當(dāng) g″=(x?y)?H(x?y)≥0 (H=def?2f） 對(duì)全部 x,y∈Rn，相當(dāng)于 H?0根據(jù)半正定矩陣的定義。

12.2.3。約束條件

凸優(yōu)化的一個(gè)很好的特性是它允許我們有效地處理約束。也就是說(shuō)，它允許我們解決 以下形式的約束優(yōu)化問(wèn)題：

(12.2.16)minimizexf(x)subject toci(x)≤0for alli∈{1,…,n},

在哪里f是目標(biāo)和功能ci是約束函數(shù)?？纯催@確實(shí)考慮了以下情況 c1(x)=‖x‖2?1. 在這種情況下，參數(shù)x被限制在單位球內(nèi)。如果第二個(gè)約束是 c2(x)=v?x+b，那么這對(duì)應(yīng)于所有x躺在半空間上。同時(shí)滿足這兩個(gè)約束相當(dāng)于選擇球的一部分。

12.2.3.1。拉格朗日量

通常，解決約束優(yōu)化問(wèn)題很困難。解決這個(gè)問(wèn)題的一種方法來(lái)自物理學(xué)，具有相當(dāng)簡(jiǎn)單的直覺(jué)。想象一個(gè)盒子里的球。球?qū)L動(dòng)到最低的位置，重力將與盒子側(cè)面可以施加在球上的力平衡。簡(jiǎn)而言之，目標(biāo)函數(shù)（即重力）的梯度將被約束函數(shù)的梯度所抵消（由于墻壁“推回”，球需要留在盒子內(nèi)）。請(qǐng)注意，某些約束可能未激活：球未接觸的墻壁將無(wú)法對(duì)球施加任何力。

跳過(guò)拉格朗日量的推導(dǎo) L，上述推理可以通過(guò)以下鞍點(diǎn)優(yōu)化問(wèn)題來(lái)表達(dá)：

(12.2.17)L(x,α1,…,αn)=f(x)+∑i=1nαici(x)whereαi≥0.

這里的變量αi(i=1,…,n) 是所謂的拉格朗日乘數(shù)，可確保正確執(zhí)行約束。它們被選擇得足夠大以確保 ci(x)≤0對(duì)全部i. 例如，對(duì)于任何 x在哪里ci(x)<0自然地，我們最終會(huì)選擇αi=0. 此外，這是一個(gè)想要最大化的鞍點(diǎn)優(yōu)化問(wèn)題 L關(guān)于所有αi并同時(shí)將其最小化x. 有大量的文獻(xiàn)解釋了如何達(dá)到這個(gè)功能 L(x,α1,…,αn). 為了我們的目的，知道鞍點(diǎn)就足夠了L是原始約束優(yōu)化問(wèn)題得到最優(yōu)解的地方。

12.2.3.2。處罰

至少近似滿足約束優(yōu)化問(wèn)題的一種方法 是采用拉格朗日量L. 而不是滿足ci(x)≤0我們只需添加 αici(x)到目標(biāo)函數(shù)f(x). 這確保了約束不會(huì)被嚴(yán)重違反。

事實(shí)上，我們一直在使用這個(gè)技巧?？紤]第 3.7 節(jié)中的權(quán)重衰減。在其中我們添加 λ2‖w‖2到目標(biāo)函數(shù)以確保w不會(huì)長(zhǎng)得太大。從約束優(yōu)化的角度我們可以看出，這將確?！瑆‖2?r2≤0對(duì)于一些半徑r. 調(diào)整值λ允許我們改變大小 w.

通常，添加懲罰項(xiàng)是確保近似約束滿足的好方法。在實(shí)踐中，這比完全滿意更穩(wěn)健。此外，對(duì)于非凸問(wèn)題，許多使精確方法在凸情況下如此有吸引力的屬性（例如，最優(yōu)性）不再成立。

12.2.3.3。預(yù)測(cè)

滿足約束的另一種策略是預(yù)測(cè)。同樣，我們以前遇到過(guò)它們，例如，在9.5 節(jié)中處理梯度裁剪時(shí)。在那里我們確保梯度的長(zhǎng)度為θ通過(guò)

(12.2.18)g←g?min(1,θ/‖g‖).

這原來(lái)是一個(gè)投影g到半徑球上θ. 更一般地，凸集上的投影 X定義為

(12.2.19)ProjX(x)=argminx′∈X?‖x?x′‖,

這是最近的點(diǎn)X到x.

圖 12.2.4凸投影。

投影的數(shù)學(xué)定義聽(tīng)起來(lái)有點(diǎn)抽象。 圖 12.2.4解釋得更清楚一些。其中有兩個(gè)凸集，一個(gè)圓和一個(gè)菱形。兩組（黃色）內(nèi)的點(diǎn)在投影期間保持不變。兩個(gè)集合外的點(diǎn)（黑色）被投影到集合內(nèi)最接近原始點(diǎn)（黑色）的點(diǎn)（紅色）。而對(duì)于?2球這會(huì)使方向保持不變，一般情況下不必如此，正如在菱形的情況下所看到的那樣。

凸投影的用途之一是計(jì)算稀疏權(quán)重向量。在這種情況下，我們將權(quán)重向量投影到?1球，這是圖 12.2.4 中菱形情況的一般化版本 。

12.2.4。概括

在深度學(xué)習(xí)的背景下，凸函數(shù)的主要目的是激發(fā)優(yōu)化算法并幫助我們?cè)敿?xì)理解它們。下面我們將看到梯度下降和隨機(jī)梯度下降是如何相應(yīng)推導(dǎo)出來(lái)的。

凸集的交集是凸的。工會(huì)不是。

凸函數(shù)的期望不亞于期望的凸函數(shù)（詹森不等式）。

當(dāng)且僅當(dāng)它的 Hessian（二階導(dǎo)數(shù)矩陣）是半正定的時(shí)，二次可微函數(shù)是凸函數(shù)。

可以通過(guò)拉格朗日添加凸約束。在實(shí)踐中，我們可以簡(jiǎn)單地將它們與對(duì)目標(biāo)函數(shù)的懲罰相加。

投影映射到凸集中最接近原始點(diǎn)的點(diǎn)。

12.2.5。練習(xí)

假設(shè)我們要通過(guò)在集合內(nèi)的點(diǎn)之間繪制所有線并檢查是否包含這些線來(lái)驗(yàn)證集合的凸性。

證明僅檢查邊界上的點(diǎn)就足夠了。

證明僅檢查集合的頂點(diǎn)就足夠了。

表示為 Bp[r]=def{x|x∈Rdand‖x‖p≤r} 半徑球r使用p-規(guī)范。證明 Bp[r]對(duì)所有人都是凸的p≥1.

給定凸函數(shù)f和g， 顯示 max(f,g)也是凸的 證明 min(f,g)不是凸的。

證明softmax函數(shù)的歸一化是凸的。更具體地證明的凸性 f(x)=log?∑iexp?(xi).

證明線性子空間，即 X={x|Wx=b}, 是凸集。

證明在線性子空間的情況下 b=0投影 ProjX可以寫(xiě)成 Mx對(duì)于一些矩陣M.

表明對(duì)于二次可微凸函數(shù)f我們可以寫(xiě) f(x+?)=f(x)+?f′(x)+12?2f″(x+ξ) 對(duì)于一些ξ∈[0,?].

給定一個(gè)凸集X和兩個(gè)向量 x和y，證明投影永遠(yuǎn)不會(huì)增加距離，即 ‖x?y‖≥‖ProjX(x)?ProjX(y)‖.

Discussions