摘要：本文作者介紹了梯度下降算法，通過可微編程實(shí)現(xiàn)尋找一種佳的圖像抖動(dòng)模式，詳細(xì)介紹了其中的五個(gè)步驟，并通過結(jié)果展示了圖像效果。讀懂本文，需要有一定的高等數(shù)學(xué)知識，以下是譯文。
實(shí)現(xiàn)這篇文章的C++代碼在Github上的網(wǎng)址是：https：//github.com/Atrix256/DitherFindGradientDescent
神經(jīng)網(wǎng)絡(luò)現(xiàn)在是一個(gè)熱門話題。圍繞它們有許多奧秘和神秘感，但是它們的核心其實(shí)只是簡單的程序，程序參數(shù)通過使用梯度下降進(jìn)行調(diào)整。
（如果對神經(jīng)網(wǎng)絡(luò)感興趣，可能會(huì)覺得這篇文章很有趣：如何用反向傳播訓(xùn)練神經(jīng)網(wǎng)絡(luò)）
雖然梯度下降可以用于很多其它情況，事實(shí)上，甚至可以推廣神經(jīng)網(wǎng)絡(luò)的核心功能來處理其它類型的程序，這正是這篇文章中所做的。
為了能夠使用梯度下降來優(yōu)化程序的參數(shù)，程序必須有如下構(gòu)成：
除了上述兩點(diǎn)之外，就像著色器程序或SIMD程序一樣，希望程序盡可能無分支（if 語句）。這樣做的原因是因?yàn)樵诶硐氲那闆r下，整個(gè)程序應(yīng)該由可微操作組成。分支（if語句）導(dǎo)致不連續(xù)和不可微。有些方法可以處理分支，有些分支實(shí)際上不會(huì)影響結(jié)果，但這是一個(gè)應(yīng)該牢記在心的好的指導(dǎo)方針。正因?yàn)槿绱耍€是希望遠(yuǎn)離不可微的函數(shù)——比如可以試圖使用“step”函數(shù)而不是if語句。
這篇文章將詳細(xì)介紹如何在C ++中使用可微編程來實(shí)現(xiàn)特定的目標(biāo)。結(jié)果的展示，以及生成結(jié)果的簡單/無外部依賴的C ++代碼位于
https://github.com/Atrix256/DitherFindGradientDescent。
首先，簡單介紹一下梯度下降。
以一個(gè) f(x)形式的函數(shù)為例，它只需要一個(gè)輸入，所以是一維的。
可以把這樣的函數(shù)想象成在數(shù)軸上的每個(gè)點(diǎn)都有一個(gè)值。
可以將這些值看作一個(gè)高度，它給了一個(gè)函數(shù)形式 y=f(x)，仍然稱之為一維形式的函數(shù)，盡管它現(xiàn)在有兩個(gè)維度。
下面看一個(gè)函數(shù) y=3x+1
還記得直線方程式是 y=mx+b ,其中m是線（riserun 或 yx）的斜率，而b是線與Y軸交叉的位置。
在微積分中，會(huì)發(fā)現(xiàn)斜率m也是函數(shù)的導(dǎo)數(shù)：dydx
斜率/導(dǎo)數(shù)表示x每添加1，y就會(huì)對應(yīng)的增加多少。
假設(shè)在這個(gè)圖上x=1( 這會(huì)讓y=4）,并且假設(shè)希望從當(dāng)前的位置向下走。可以通過查看這個(gè)點(diǎn)的斜率/導(dǎo)數(shù)，即3（對于線上的每個(gè)點(diǎn)是3）來做到這一點(diǎn)。由于導(dǎo)數(shù)是正數(shù)，這意味著向右移動(dòng)會(huì)使y值變大（線向上走），向左移動(dòng)會(huì)使y值變小（線向下走）。
所以，如果想向下到更小的y值，需要從x中減去值。
一種更簡單的方法是，從x值中減去導(dǎo)數(shù)，使的y值更小。
這是一個(gè)核心的事實(shí)，它會(huì)幫助引導(dǎo)你克服困難：減去導(dǎo)數(shù)（稍后減去梯度），使值變小。減去的值通常乘以一些標(biāo)量值，使其移動(dòng)得更快或更慢。
如果有一個(gè)更復(fù)雜的函數(shù)會(huì)發(fā)生什么，比如y=(x?2)2
假設(shè)在這個(gè)圖上的點(diǎn)x=1，那么y=1 。現(xiàn)在，沿著哪條路向下走？這個(gè)函數(shù)的導(dǎo)數(shù)是y=2x?4 ，可以將x值插入到該點(diǎn)的斜率/導(dǎo)數(shù)中：-3。
減去導(dǎo)數(shù)向下移，這意味著需要從x中減去一個(gè)負(fù)值; 又叫做需要添加一個(gè)值到X。
正如大家所看到的，給x增加一個(gè)值并使它向右移動(dòng)，實(shí)際上就是向下移。
規(guī)則生效了，萬歲！
當(dāng)有不止一個(gè)維度的時(shí)候，事情會(huì)變得更復(fù)雜一點(diǎn)，但是并不是那么復(fù)雜，所以堅(jiān)持下去！
看看這個(gè)函數(shù)z=xy
假設(shè)（x，y）在點(diǎn)（1,1）—在右上角：z=1，并且假設(shè)想要向下移。現(xiàn)在有兩個(gè)變量（x和y），而不是只有一個(gè)變量取（x）的導(dǎo)數(shù)。如何處理這個(gè)問題？
答案是PARTIAL導(dǎo)數(shù)（偏導(dǎo)數(shù)）。
首先，假設(shè)y是一個(gè)常數(shù)值，而不是一個(gè)變量。這會(huì)給出x：的偏導(dǎo)數(shù)? z? x 。由此可知，如果向x加一個(gè)值，z會(huì)加多少。這是一個(gè)特殊的沿著x軸的斜率。
在這種情況下，z相對于x的偏導(dǎo)數(shù)就是：y。
對另一個(gè)變量做同樣的事情，z相對于y的偏導(dǎo)數(shù)就是：x。
現(xiàn)在對每個(gè)變量都有偏導(dǎo)數(shù)，把它們放到一個(gè)矢量中。這個(gè)矢量被稱為梯度，有一些嚇人的符號，看起來像這樣：
?z=?f(x,y)=(? z? x,? z? y)
對于這個(gè)函數(shù)，梯度是：
?z=?f(x,y)=(y,x)
這使得梯度在一個(gè)具體點(diǎn)：
?z=?f(1,1)=(1,1)
在后一節(jié)中，看到導(dǎo)數(shù)/斜率指向函數(shù)變大的地方。梯度也是如此，它們也指向函數(shù)變大的方向！
所以，如果想向下，需要從x和y中減去值。事實(shí)上，從當(dāng)前的點(diǎn)向下快的方式是從x和y中減去相同的值。這是因?yàn)樘荻炔恢皇侵赶蛩兇蟮牡胤剑侵赶蚩斓牡胤健Ｋ裕嫦蛱荻纫仓赶蚩熳冃〉牡胤健?
很酷吧？
可以通過查看函數(shù)圖來直觀的確認(rèn)這一點(diǎn)。
在繼續(xù)之前，關(guān)于斜率，導(dǎo)數(shù)和梯度的后一件事情，當(dāng)它們指向大增長方向時(shí)，僅對于非線性函數(shù)的圖上的無限小點(diǎn)有效。當(dāng)沿著梯度的相反方向移動(dòng)時(shí)，這將非常重要，但是要確保用非常小的步驟來幫助找到圖表上的低點(diǎn)。
為什么要使用梯度下降？假設(shè)有一個(gè)函數(shù)：
w=f(x,y,z)
當(dāng)然，可以為x，y和z選擇一些隨機(jī)的起始值，然后使用梯度下降找到小的w，但是誰在乎呢？
給這些變量一些其它名稱，看看這個(gè)值是否變得更加明顯一點(diǎn)：
DamageTakenMultiplier=CalculateDamageTakenMultiplier(Armor,Dodge,Resist)
現(xiàn)在，通過只改變變量的名稱，可以看到，可以使用梯度下降來找到多少Armor，Dodge和resist，使得角色受到少的傷害。現(xiàn)在可以告訴你如何將統(tǒng)計(jì)點(diǎn)分配給一個(gè)角色以獲得好的結(jié)果。
請注意，如果試圖找到可能的高數(shù)字，而不是低數(shù)字，則可以將函數(shù)乘以-1，并以相同的方式執(zhí)行其它所有操作。也可以做梯度ASCENT（梯度上升），這相當(dāng)于乘以-1并做梯度下降。
下面是一些在進(jìn)行梯度下降時(shí)可能遇到的常見問題:
下面是一個(gè)局部小值與全局小值的例子。可以看到，根據(jù)在這張圖表上開始的位置，如果的規(guī)則是“向下”，可能會(huì)進(jìn)入更深的碗，或更淺的碗。
（圖片來自維基百科由KSmrq提供 http://commons.wikimedia.org/wiki/File:Extrema_example.svg, GFDL 1.2,
https://commons.wikimedia.org/w/index.php?curid=6870865）
下面是一個(gè)平坦導(dǎo)數(shù)的例子。可以想象，如果在x = 1時(shí)，可以看到導(dǎo)數(shù)會(huì)讓左邊減小y值，但是這個(gè)數(shù)字非常非常小。這是一個(gè)問題，因?yàn)橥ǔＴ跍p去乘數(shù)之前乘以導(dǎo)數(shù)或梯度，所以只需要朝目標(biāo)邁出一小步。
也可以想成一個(gè)完全平坦導(dǎo)數(shù)，而這個(gè)導(dǎo)數(shù)恰好為0。在這種情況下，無論數(shù)字有多大或多小，都可以乘以導(dǎo)數(shù)，根本不會(huì)移動(dòng)！
下面是一個(gè)不連續(xù)的函數(shù)，如果x小于0.5，則值為1，否則為x。這基本上顯示了在可微編程中使用if語句時(shí)會(huì)發(fā)生什么。如果從右側(cè)開始，應(yīng)該向左移動(dòng)來提高分?jǐn)?shù)。然而，它會(huì)一直持續(xù)向左移，直到x小于0.5，那么分?jǐn)?shù)會(huì)突然變得更糟，導(dǎo)數(shù)將變成0，就被卡在這個(gè)地方了！
解決這些問題的方法有很多，但都是深層次的話題。如果沒有別的，應(yīng)該知道這些問題是存在的，所以可以知道它們什么時(shí)候會(huì)影響，和/或?yàn)槭裁磻?yīng)該避免它們，如果有所選擇。
假設(shè)沒有計(jì)算出所有這些偏導(dǎo)數(shù)。或者更務(wù)實(shí)一點(diǎn)，不想坐下來手工計(jì)算一些通用的C ++代碼的梯度函數(shù)！
有一些好消息。
雖然需要梯度的偏導(dǎo)數(shù)，不需要做這些計(jì)算來獲取它們。
以下是其它一些獲得偏導(dǎo)數(shù)的方法：
仔細(xì)猜猜要使用哪一個(gè)？是的，對偶數(shù)！
一言以蔽之，如果有代碼使用了浮點(diǎn)數(shù)，則可以將其更改為使用模板類型。然后，在代碼中使用對偶數(shù)，而不是浮點(diǎn)數(shù)。得到的輸出將是代碼輸出的特定值，也是代碼在這個(gè)值的梯度。更好的是，這不是一個(gè)數(shù)值方法（它不是一個(gè)近似值），它是分析的方法（確切的說）。
對偶數(shù)是驚人的！
由于已將代碼模板化，因此當(dāng)不想要或不需要梯度時(shí)，仍然可以將它用于浮點(diǎn)數(shù)模式。
這里是將要使用梯度下降進(jìn)行可微編程的一般框架：
這是策略，深入討論將要探討的具體問題。
以下是要解決的問題：
想要找到一個(gè)3×3抖動(dòng)模式，當(dāng)用它抖動(dòng)一個(gè)圖像（通過在圖像上反復(fù)重復(fù)3×3模式），然后以特定的數(shù)量模糊結(jié)果，它是如此接近被同樣數(shù)量的模糊的原始圖像。
這聽起來有點(diǎn)挑戰(zhàn)性對不對？這不是真的那么糟糕，不要擔(dān)心（：
代碼的步驟（可微的）是：
再一次，需要用對偶數(shù)來微積分這個(gè)事情，這樣就得到一個(gè)梯度來修改抖動(dòng)模式，以便有更好的得分。
抖動(dòng)圖像是一個(gè)非常簡單的過程。
要抖動(dòng)它，以便將灰度圖像作為輸入，并使用抖動(dòng)模式將其轉(zhuǎn)換為黑白圖像。
（如果開始使用彩色圖像，則會(huì)顯示如何將其轉(zhuǎn)換為灰度：將RGB轉(zhuǎn)換為灰度）
對于源圖像中的每個(gè)像素（x，y），查看抖動(dòng)模式中的像素（x％3，y％3），如果抖動(dòng)模式像素小于源，則會(huì)寫出黑色像素，否則將寫一個(gè)白色的像素。
if (sourcePixel(x,y) < ditherPixel(x%3, y%3)) pixelOut(x,y) = 0.0; else pixelOut(x,y) = 1.0;但是有個(gè)問題，這是一個(gè)分支，它會(huì)造成不連續(xù)性，這將不能有很好的導(dǎo)數(shù)來幫助實(shí)現(xiàn)目標(biāo)。
寫上面的抖動(dòng)操作的另一種方法是這樣寫的：
difference = ditherPixel(x%3, y%3) - sourcePixel(x,y); pixelOut(x,y) = step(difference);這里的“step”是“階躍函數(shù)”（ 是一種特殊的連續(xù)時(shí)間函數(shù)，是一個(gè)從0跳變到1的過程，屬于奇異函數(shù)），如果x> = 0則為1，否則為0。
（來自維基百科的圖像由Omegatron提供（自己的工作）[CC BY-SA 3.0
（https://creativecommons.org/licenses/by-sa/3.0）或GFDL（http://www.gnu.org/copyleft/fdl.HTML）％5D，通過維基共享資源）
去掉了分支（if語句），但仍然有一個(gè)不連續(xù)的函數(shù)。
幸運(yùn)的是，可以用一個(gè)近似階躍函數(shù)的其它函數(shù)。比如使用這樣的公式0.5+atan(100?x)/pi:
不幸的是，結(jié)果不是那么好，所以把它切換到 0.5+atan(1000?x)/pi，得到了一個(gè)更好的結(jié)果：
這個(gè)函數(shù)確實(shí)有平坦導(dǎo)數(shù)問題，但它的效果卻很好。在這種情況下，平坦導(dǎo)數(shù)似乎并不是一個(gè)大問題。
為了把它們集中在一起，所使用的抖動(dòng)像素的可微版本看起來像這樣：
difference = ditherPixel(x%3, y%3) - sourcePixel(x,y); pixelOut(x,y) = 0.5+atan(10000.0f * difference) / pi;作為這個(gè)抖動(dòng)過程的輸入，采取：
作為輸出，這個(gè)抖動(dòng)過程如下：
模糊抖動(dòng)的結(jié)果并不是那么困難。本文中使用了高斯模糊（也叫高斯平滑，是在Adobe Photoshop、GIMP以及Paint.NET等圖像處理軟件中廣泛使用的處理效果，通常用它來減少圖像噪聲以及降低細(xì)節(jié)層次），但用其它模糊也很容易。
這里有一些高斯模糊代碼（可以從這篇博文：高斯模糊 閱讀），在適當(dāng)?shù)牡胤桨阉D(zhuǎn)換為使用模板類型，而不是浮點(diǎn)/像素，也確保沒有分支或任何不連續(xù)。
幸好這里并沒有什么可修正的，所以不是太困難。
這使得抖動(dòng)的結(jié)果是對偶數(shù)每像素的，并對它們進(jìn)行高斯模糊，保留并正確地修改梯度（導(dǎo)數(shù)），就如同做高斯模糊。
模糊源圖像很容易，因?yàn)楹笠徊阶隽艘粋€(gè)普通的高斯模糊函數(shù)。使用通用的高斯模糊函數(shù)來模糊圖像。這不需要作為對偶數(shù)來完成，所以它是正常像素和常規(guī)像素。
大家可能想知道為什么這個(gè)部分不需要作為對偶數(shù)來完成。
簡單點(diǎn)回答是因?yàn)檫@些值不依賴于抖動(dòng)模式（這是用導(dǎo)數(shù)跟蹤的）。
更數(shù)學(xué)的解釋是，實(shí)際上可以考慮這些對偶數(shù)，它們只是有一個(gè)零的梯度，因?yàn)樗鼈儽举|(zhì)上是常數(shù)，而且與函數(shù)的參數(shù)無關(guān)。梯度只會(huì)隱含地為零，就像可能引入該函數(shù)的任何其它常數(shù)值一樣。
接下來需要計(jì)算抖動(dòng)和模糊結(jié)果（由對偶數(shù)組成）和源模糊（由正常像素組成）之間的相似度分?jǐn)?shù)。
使用的相似度分?jǐn)?shù)只是MSE或“均方誤差”。
為了計(jì)算MSE，對每一個(gè)像素做如下操作：
error = ditheredBlurredImage(x,y) - blurredImage(x,y); errorSquared = error * error;在對每個(gè)像素做平方誤差之后，只需取它們的平均值就可以得到MSE。
關(guān)于MSE的一個(gè)有趣的事情是，因?yàn)殄e(cuò)誤是取平方的，所以相比較大的錯(cuò)誤，MSE更偏向于較小的錯(cuò)誤，這是一個(gè)很好的屬性。
關(guān)于MSE的不太好的屬性是，它可能決定某個(gè)東西在數(shù)學(xué)上是一個(gè)很小的差別，即使人類會(huì)認(rèn)為這是一個(gè)巨大的差異感知。反之亦然。盡管如此，選擇用它，因?yàn)樗芎唵危⑶医K得到了相當(dāng)好的結(jié)果。
如果想深入了解“感知相似度分?jǐn)?shù)的圖像”，看看這些鏈接：
在這個(gè)步驟之后，得到一個(gè)MSE值，該值表示圖像的相似程度。較低的值意味著較低的平均平方誤差，所以較低的數(shù)字確實(shí)更好。
另一個(gè)優(yōu)點(diǎn)是，MSE的值是一個(gè)帶有9個(gè)偏導(dǎo)數(shù)梯度的對偶數(shù)，用于描述在調(diào)整每個(gè)參數(shù)時(shí)MSE的變化量。
該梯度告訴我們?nèi)绾握{(diào)整參數(shù)（3×3抖動(dòng)像素！）以降低MSE的值！
現(xiàn)在是把所有這些放在一起的時(shí)候了，并且使用梯度下降來使抖動(dòng)模式更好。
下面是程序的運(yùn)行方式：
做這個(gè)循環(huán)的1000次迭代：
1. 抖動(dòng)并模糊源圖像
2. 與源圖像模糊相比，計(jì)算該結(jié)果的MSE
3. 使用MSE值的梯度，從抖動(dòng)模式中的每個(gè)像素中減去相應(yīng)的偏導(dǎo)數(shù)，但通過“學(xué)習(xí)率”縮放偏導(dǎo)數(shù)
輸出好的結(jié)果
在從0處開始循環(huán)迭代，學(xué)習(xí)率從3.0開始，但是在每次迭代時(shí)都會(huì)衰減，在迭代到999時(shí)衰減到0.1。它從1開始以幫助逃離局部小值，并且在后使用非常小的速率來嘗試并深入到小值的發(fā)現(xiàn)。
在調(diào)整抖動(dòng)模式像素之后，將它們鎖定在0和1之間。
還需要提到的一點(diǎn)是，當(dāng)正在做梯度下降的時(shí)候，會(huì)跟蹤看到的佳得分的抖動(dòng)模式。
這樣，在經(jīng)過1000次迭代之后，如果看到了比現(xiàn)在更好的，就用它代替終的結(jié)果。
如果正確地調(diào)整參數(shù)（學(xué)習(xí)率，迭代等等），想來，這操作應(yīng)該不會(huì)經(jīng)常出現(xiàn)，但總的來說，終狀態(tài)并不是遇到的佳狀態(tài)，所以在大多數(shù)情況下，這是一個(gè)獲得更好結(jié)果的好方法。
有沒有注意到這個(gè)帖子叫做“尋找一種理想的抖動(dòng)模式”而不是“發(fā)現(xiàn)一種理想的抖動(dòng)模式”？（：
結(jié)果很不錯(cuò)，但是還有可能會(huì)更好。盡管如此，這里所討論的技術(shù)是一個(gè)很好的開端，沿著可微程序設(shè)計(jì)的道路，以及相類似的主題。
下面是一些能夠用代碼得到的結(jié)果。點(diǎn)擊查看完整大小的圖像，縮小的圖像有鋸齒問題。
圖像從左到右分別是：原始的圖像，使用的抖動(dòng)模式（重復(fù)）的圖像，抖動(dòng)的圖像，模糊的抖動(dòng)圖像，后是模糊的原始圖像。目的是使后兩幅圖像看起來盡可能接近，使用MSE作為它們多么接近的度量標(biāo)準(zhǔn)。
下圖是使用sigma為10的高斯模糊的起始狀態(tài)：
下圖是梯度下降的1000次迭代之后。注意到頂部的黑色塊與其開始的地方相比已經(jīng)消失了。
下圖是使用高斯模糊sigma 為1的起始狀態(tài)：
下圖是1000次迭代之后，這是相當(dāng)不錯(cuò)的結(jié)果：
后，下圖沒有任何模糊：
經(jīng)過1000次迭代之后，它實(shí)際上看起來更糟！
完全不用模糊會(huì)產(chǎn)生一些可怕的結(jié)果。模糊賦予了算法在如何成功上更多的自由，而沒有模糊，找到解決方案的余地則少得多。
在MSE計(jì)算之前使用模糊的另一個(gè)好處是，模糊是低通濾波器。這意味著在MSE計(jì)算之前，更高的頻率消失了。這樣做的結(jié)果是該算法將有利于更接近藍(lán)色噪聲抖動(dòng)的結(jié)果。相當(dāng)整齊對吧？！
希望大家通過可微編程和梯度下降享受這個(gè)旅程，希望大家能夠跟上。
以下是超出這篇文章討論的一些可能有趣的事情：
本站文章版權(quán)歸原作者及原出處所有 。內(nèi)容為作者個(gè)人觀點(diǎn)， 并不代表本站贊同其觀點(diǎn)和對其真實(shí)性負(fù)責(zé)，本站只提供參考并不構(gòu)成任何投資及應(yīng)用建議。本站是一個(gè)個(gè)人學(xué)習(xí)交流的平臺(tái)，網(wǎng)站上部分文章為轉(zhuǎn)載，并不用于任何商業(yè)目的，我們已經(jīng)盡可能的對作者和來源進(jìn)行了通告，但是能力有限或疏忽，造成漏登，請及時(shí)聯(lián)系我們，我們將根據(jù)著作權(quán)人的要求，立即更正或者刪除有關(guān)內(nèi)容。本站擁有對此聲明的最終解釋權(quán)。
