摘要：本文作者介绍了梯度下降算法，通过可微编程实现寻找一种佳的图像抖动模式，详细介绍了其中的五个步骤，并通过结果展示了图像效果。读懂本文，需要有一定的高等数学知识，以下是译文。
实现这篇文章的C++代码在Github上的网址是：https：//github.com/Atrix256/DitherFindGradientDescent
神经网络现在是一个热门话题。围绕它们有许多奥秘和神秘感，但是它们的核心其实只是简单的程序，程序参数通过使用梯度下降进行调整。
（如果对神经网络感兴趣，可能会觉得这篇文章很有趣：如何用反向传播训练神经网络）
虽然梯度下降可以用于很多其它情况，事实上，甚至可以推广神经网络的核心功能来处理其它类型的程序，这正是这篇文章中所做的。
为了能够使用梯度下降来优化程序的参数，程序必须有如下构成：
除了上述两点之外，就像着色器程序或SIMD程序一样，希望程序尽可能无分支（if 语句）。这样做的原因是因为在理想的情况下，整个程序应该由可微操作组成。分支（if语句）导致不连续和不可微。有些方法可以处理分支，有些分支实际上不会影响结果，但这是一个应该牢记在心的好的指导方针。正因为如此，还是希望远离不可微的函数——比如可以试图使用“step”函数而不是if语句。
这篇文章将详细介绍如何在C ++中使用可微编程来实现特定的目标。结果的展示，以及生成结果的简单/无外部依赖的C ++代码位于
https://github.com/Atrix256/DitherFindGradientDescent。
首先，简单介绍一下梯度下降。
以一个 f(x)形式的函数为例，它只需要一个输入，所以是一维的。
可以把这样的函数想象成在数轴上的每个点都有一个值。
可以将这些值看作一个高度，它给了一个函数形式 y=f(x)，仍然称之为一维形式的函数，尽管它现在有两个维度。
下面看一个函数 y=3x+1
还记得直线方程式是 y=mx+b ,其中m是线（riserun 或 yx）的斜率，而b是线与Y轴交叉的位置。
在微积分中，会发现斜率m也是函数的导数：dydx
斜率/导数表示x每添加1，y就会对应的增加多少。
假设在这个图上x=1( 这会让y=4）,并且假设希望从当前的位置向下走。可以通过查看这个点的斜率/导数，即3（对于线上的每个点是3）来做到这一点。由于导数是正数，这意味着向右移动会使y值变大（线向上走），向左移动会使y值变小（线向下走）。
所以，如果想向下到更小的y值，需要从x中减去值。
一种更简单的方法是，从x值中减去导数，使的y值更小。
这是一个核心的事实，它会帮助引导你克服困难：减去导数（稍后减去梯度），使值变小。减去的值通常乘以一些标量值，使其移动得更快或更慢。
如果有一个更复杂的函数会发生什么，比如y=(x−2)2
假设在这个图上的点x=1，那么y=1 。现在，沿着哪条路向下走？这个函数的导数是y=2x−4 ，可以将x值插入到该点的斜率/导数中：-3。
减去导数向下移，这意味着需要从x中减去一个负值; 又叫做需要添加一个值到X。
正如大家所看到的，给x增加一个值并使它向右移动，实际上就是向下移。
规则生效了，万岁！
当有不止一个维度的时候，事情会变得更复杂一点，但是并不是那么复杂，所以坚持下去！
看看这个函数z=xy
假设（x，y）在点（1,1）—在右上角：z=1，并且假设想要向下移。现在有两个变量（x和y），而不是只有一个变量取（x）的导数。如何处理这个问题？
答案是PARTIAL导数（偏导数）。
首先，假设y是一个常数值，而不是一个变量。这会给出x：的偏导数∂ z∂ x 。由此可知，如果向x加一个值，z会加多少。这是一个特殊的沿着x轴的斜率。
在这种情况下，z相对于x的偏导数就是：y。
对另一个变量做同样的事情，z相对于y的偏导数就是：x。
现在对每个变量都有偏导数，把它们放到一个矢量中。这个矢量被称为梯度，有一些吓人的符号，看起来像这样：
∇z=∇f(x,y)=(∂ z∂ x,∂ z∂ y)
对于这个函数，梯度是：
∇z=∇f(x,y)=(y,x)
这使得梯度在一个具体点：
∇z=∇f(1,1)=(1,1)
在后一节中，看到导数/斜率指向函数变大的地方。梯度也是如此，它们也指向函数变大的方向！
所以，如果想向下，需要从x和y中减去值。事实上，从当前的点向下快的方式是从x和y中减去相同的值。这是因为梯度不只是指向它变大的地方，而是指向快的地方。所以，逆向梯度也指向快变小的地方。
很酷吧？
可以通过查看函数图来直观的确认这一点。
在继续之前，关于斜率，导数和梯度的后一件事情，当它们指向大增长方向时，仅对于非线性函数的图上的无限小点有效。当沿着梯度的相反方向移动时，这将非常重要，但是要确保用非常小的步骤来帮助找到图表上的低点。
为什么要使用梯度下降？假设有一个函数：
w=f(x,y,z)
当然，可以为x，y和z选择一些随机的起始值，然后使用梯度下降找到小的w，但是谁在乎呢？
给这些变量一些其它名称，看看这个值是否变得更加明显一点：
DamageTakenMultiplier=CalculateDamageTakenMultiplier(Armor,Dodge,Resist)
现在，通过只改变变量的名称，可以看到，可以使用梯度下降来找到多少Armor，Dodge和resist，使得角色受到少的伤害。现在可以告诉你如何将统计点分配给一个角色以获得好的结果。
请注意，如果试图找到可能的高数字，而不是低数字，则可以将函数乘以-1，并以相同的方式执行其它所有操作。也可以做梯度ASCENT（梯度上升），这相当于乘以-1并做梯度下降。
下面是一些在进行梯度下降时可能遇到的常见问题:
下面是一个局部小值与全局小值的例子。可以看到，根据在这张图表上开始的位置，如果的规则是“向下”，可能会进入更深的碗，或更浅的碗。
（图片来自维基百科由KSmrq提供 http://commons.wikimedia.org/wiki/File:Extrema_example.svg, GFDL 1.2,
https://commons.wikimedia.org/w/index.php?curid=6870865）
下面是一个平坦导数的例子。可以想象，如果在x = 1时，可以看到导数会让左边减小y值，但是这个数字非常非常小。这是一个问题，因为通常在减去乘数之前乘以导数或梯度，所以只需要朝目标迈出一小步。
也可以想成一个完全平坦导数，而这个导数恰好为0。在这种情况下，无论数字有多大或多小，都可以乘以导数，根本不会移动！
下面是一个不连续的函数，如果x小于0.5，则值为1，否则为x。这基本上显示了在可微编程中使用if语句时会发生什么。如果从右侧开始，应该向左移动来提高分数。然而，它会一直持续向左移，直到x小于0.5，那么分数会突然变得更糟，导数将变成0，就被卡在这个地方了！
解决这些问题的方法有很多，但都是深层次的话题。如果没有别的，应该知道这些问题是存在的，所以可以知道它们什么时候会影响，和/或为什么应该避免它们，如果有所选择。
假设没有计算出所有这些偏导数。或者更务实一点，不想坐下来手工计算一些通用的C ++代码的梯度函数！
有一些好消息。
虽然需要梯度的偏导数，不需要做这些计算来获取它们。
以下是其它一些获得偏导数的方法：
仔细猜猜要使用哪一个？是的，对偶数！
一言以蔽之，如果有代码使用了浮点数，则可以将其更改为使用模板类型。然后，在代码中使用对偶数，而不是浮点数。得到的输出将是代码输出的特定值，也是代码在这个值的梯度。更好的是，这不是一个数值方法（它不是一个近似值），它是分析的方法（确切的说）。
对偶数是惊人的！
由于已将代码模板化，因此当不想要或不需要梯度时，仍然可以将它用于浮点数模式。
这里是将要使用梯度下降进行可微编程的一般框架：
这是策略，深入讨论将要探讨的具体问题。
以下是要解决的问题：
想要找到一个3×3抖动模式，当用它抖动一个图像（通过在图像上反复重复3×3模式），然后以特定的数量模糊结果，它是如此接近被同样数量的模糊的原始图像。
这听起来有点挑战性对不对？这不是真的那么糟糕，不要担心（：
代码的步骤（可微的）是：
再一次，需要用对偶数来微积分这个事情，这样就得到一个梯度来修改抖动模式，以便有更好的得分。
抖动图像是一个非常简单的过程。
要抖动它，以便将灰度图像作为输入，并使用抖动模式将其转换为黑白图像。
（如果开始使用彩色图像，则会显示如何将其转换为灰度：将RGB转换为灰度）
对于源图像中的每个像素（x，y），查看抖动模式中的像素（x％3，y％3），如果抖动模式像素小于源，则会写出黑色像素，否则将写一个白色的像素。
if (sourcePixel(x,y) < ditherPixel(x%3, y%3)) pixelOut(x,y) = 0.0; else pixelOut(x,y) = 1.0;但是有个问题，这是一个分支，它会造成不连续性，这将不能有很好的导数来帮助实现目标。
写上面的抖动操作的另一种方法是这样写的：
difference = ditherPixel(x%3, y%3) - sourcePixel(x,y); pixelOut(x,y) = step(difference);这里的“step”是“阶跃函数”（ 是一种特殊的连续时间函数，是一个从0跳变到1的过程，属于奇异函数），如果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语句），但仍然有一个不连续的函数。
幸运的是，可以用一个近似阶跃函数的其它函数。比如使用这样的公式0.5+atan(100∗x)/pi:
不幸的是，结果不是那么好，所以把它切换到 0.5+atan(1000∗x)/pi，得到了一个更好的结果：
这个函数确实有平坦导数问题，但它的效果却很好。在这种情况下，平坦导数似乎并不是一个大问题。
为了把它们集中在一起，所使用的抖动像素的可微版本看起来像这样：
difference = ditherPixel(x%3, y%3) - sourcePixel(x,y); pixelOut(x,y) = 0.5+atan(10000.0f * difference) / pi;作为这个抖动过程的输入，采取：
作为输出，这个抖动过程如下：
模糊抖动的结果并不是那么困难。本文中使用了高斯模糊（也叫高斯平滑，是在Adobe Photoshop、GIMP以及Paint.NET等图像处理软件中广泛使用的处理效果，通常用它来减少图像噪声以及降低细节层次），但用其它模糊也很容易。
这里有一些高斯模糊代码（可以从这篇博文：高斯模糊 阅读），在适当的地方把它转换为使用模板类型，而不是浮点/像素，也确保没有分支或任何不连续。
幸好这里并没有什么可修正的，所以不是太困难。
这使得抖动的结果是对偶数每像素的，并对它们进行高斯模糊，保留并正确地修改梯度（导数），就如同做高斯模糊。
模糊源图像很容易，因为后一步做了一个普通的高斯模糊函数。使用通用的高斯模糊函数来模糊图像。这不需要作为对偶数来完成，所以它是正常像素和常规像素。
大家可能想知道为什么这个部分不需要作为对偶数来完成。
简单点回答是因为这些值不依赖于抖动模式（这是用导数跟踪的）。
更数学的解释是，实际上可以考虑这些对偶数，它们只是有一个零的梯度，因为它们本质上是常数，而且与函数的参数无关。梯度只会隐含地为零，就像可能引入该函数的任何其它常数值一样。
接下来需要计算抖动和模糊结果（由对偶数组成）和源模糊（由正常像素组成）之间的相似度分数。
使用的相似度分数只是MSE或“均方误差”。
为了计算MSE，对每一个像素做如下操作：
error = ditheredBlurredImage(x,y) - blurredImage(x,y); errorSquared = error * error;在对每个像素做平方误差之后，只需取它们的平均值就可以得到MSE。
关于MSE的一个有趣的事情是，因为错误是取平方的，所以相比较大的错误，MSE更偏向于较小的错误，这是一个很好的属性。
关于MSE的不太好的属性是，它可能决定某个东西在数学上是一个很小的差别，即使人类会认为这是一个巨大的差异感知。反之亦然。尽管如此，选择用它，因为它很简单，并且终得到了相当好的结果。
如果想深入了解“感知相似度分数的图像”，看看这些链接：
在这个步骤之后，得到一个MSE值，该值表示图像的相似程度。较低的值意味着较低的平均平方误差，所以较低的数字确实更好。
另一个优点是，MSE的值是一个带有9个偏导数梯度的对偶数，用于描述在调整每个参数时MSE的变化量。
该梯度告诉我们如何调整参数（3×3抖动像素！）以降低MSE的值！
现在是把所有这些放在一起的时候了，并且使用梯度下降来使抖动模式更好。
下面是程序的运行方式：
做这个循环的1000次迭代：
1. 抖动并模糊源图像
2. 与源图像模糊相比，计算该结果的MSE
3. 使用MSE值的梯度，从抖动模式中的每个像素中减去相应的偏导数，但通过“学习率”缩放偏导数
输出好的结果
在从0处开始循环迭代，学习率从3.0开始，但是在每次迭代时都会衰减，在迭代到999时衰减到0.1。它从1开始以帮助逃离局部小值，并且在后使用非常小的速率来尝试并深入到小值的发现。
在调整抖动模式像素之后，将它们锁定在0和1之间。
还需要提到的一点是，当正在做梯度下降的时候，会跟踪看到的佳得分的抖动模式。
这样，在经过1000次迭代之后，如果看到了比现在更好的，就用它代替终的结果。
如果正确地调整参数（学习率，迭代等等），想来，这操作应该不会经常出现，但总的来说，终状态并不是遇到的佳状态，所以在大多数情况下，这是一个获得更好结果的好方法。
有没有注意到这个帖子叫做“寻找一种理想的抖动模式”而不是“发现一种理想的抖动模式”？（：
结果很不错，但是还有可能会更好。尽管如此，这里所讨论的技术是一个很好的开端，沿着可微程序设计的道路，以及相类似的主题。
下面是一些能够用代码得到的结果。点击查看完整大小的图像，缩小的图像有锯齿问题。
图像从左到右分别是：原始的图像，使用的抖动模式（重复）的图像，抖动的图像，模糊的抖动图像，后是模糊的原始图像。目的是使后两幅图像看起来尽可能接近，使用MSE作为它们多么接近的度量标准。
下图是使用sigma为10的高斯模糊的起始状态：
下图是梯度下降的1000次迭代之后。注意到顶部的黑色块与其开始的地方相比已经消失了。
下图是使用高斯模糊sigma 为1的起始状态：
下图是1000次迭代之后，这是相当不错的结果：
后，下图没有任何模糊：
经过1000次迭代之后，它实际上看起来更糟！
完全不用模糊会产生一些可怕的结果。模糊赋予了算法在如何成功上更多的自由，而没有模糊，找到解决方案的余地则少得多。
在MSE计算之前使用模糊的另一个好处是，模糊是低通滤波器。这意味着在MSE计算之前，更高的频率消失了。这样做的结果是该算法将有利于更接近蓝色噪声抖动的结果。相当整齐对吧？！
希望大家通过可微编程和梯度下降享受这个旅程，希望大家能够跟上。
以下是超出这篇文章讨论的一些可能有趣的事情：
本站文章版权归原作者及原出处所有 。内容为作者个人观点， 并不代表本站赞同其观点和对其真实性负责，本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台，网站上部分文章为转载，并不用于任何商业目的，我们已经尽可能的对作者和来源进行了通告，但是能力有限或疏忽，造成漏登，请及时联系我们，我们将根据著作权人的要求，立即更正或者删除有关内容。本站拥有对此声明的最终解释权。
