1.6　验证算法

验证算法指的是确保它是为待求解问题找到了一个数学求解方案。验证过程应该在尽可能多的输入值和输入类型上检验求解结果。

1.6.1　精确算法、近似算法和随机算法

验证算法要依据算法的类型展开，因为对不同类型的算法，其验证技术也不同。我们先区分确定型算法和随机算法。

确定型算法在特定输入上始终产生完全相同的输出结果。但是，在某些类型的算法中，随机数序列也被当作输入，这些随机数使得算法每次运行时产生的输出都不同。在第6章中将要详细介绍的k-means聚类算法就是这类算法的一个例子，如图1-12所示。

图　1-12

算法也可以分为如下两种类型，分类的依据是简化算法逻辑，使其运行速度更快时所采用的假设或近似：

• 精确算法：精确算法预计在不引入任何假设或近似的情况下产生精确解。
• 近似算法：当问题的复杂度过大，在给定的资源下难以处理时，我们会通过一些假设来简化问题。基于这些简化或假设的算法称为近似算法，它并不能给我们提供完全精确的解。

让我们通过一个例子来理解精确算法和近似算法之间的区别。1930年，人们提出了著名的旅行商问题：为特定的旅行商找出最短路线，让他能够沿该路线访问城市列表中的每个城市之后返回出发点（这就是问题被命名为旅行商问题的原因）。寻找解决方案时，第一个想法就是生成所有城市的排列组合，然后选择路线最短的排列组合。这种解决方案的复杂度是O(n!)，其中n是城市的数量。显然，城市数量超过30之后，时间复杂度就变得无法处理了。

如果城市数量超过30，那么降低复杂度的方法之一就是引入一些近似和假设。

对于近似算法来说，在需求分析时设置好期望的准确度很重要。验证近似算法就是要验证结果的误差是否在可接受的范围内。

1.6.2　可解释性

算法在临界条件下使用时，能够在需要时解释每一个结果背后的原因变得很重要。这是很有必要的，因为这能够确保基于算法结果得出的决策不会带来偏差。

有些特征会直接或间接用于得到某种特定决策，能够准确地识别出这些特征的能力，称为算法的可解释性。算法在临界条件下使用时，需要评估算法是否存在偏差和偏见。如果算法可能影响到与人们生活相关的决策，则算法的伦理分析将会成为验证过程中的标准环节。

对于处理深度学习的算法，很难实现算法的可解释性。例如，如果某个算法用于拒绝某些人的抵押贷款申请，则透明度和解释原因的能力都很重要。

算法可解释性是一个活跃的研究领域。最近发展起来的有效技术之一是局部可理解的模型无关解释（Local Interpretable Model-Agnostic Explanation, LIME），参见2016年第22届国际计算机学会知识发现和数据挖掘国际会议（ACM SIGKDD）论文集。LIME基于如下概念，对每个输入实例均做出各种细微改变，然后尽力映射出该实例的局部决策边界，它可以量化每种细微改变对该实例的影响。