1.6　驗證算法

驗證算法指的是確保它是為待求解問題找到了一個數學求解方案。驗證過程應該在盡可能多的輸入值和輸入類型上檢驗求解結果。

1.6.1　精確算法、近似算法和隨機算法

驗證算法要依據算法的類型展開，因為對不同類型的算法，其驗證技術也不同。我們先區分確定型算法和隨機算法。

確定型算法在特定輸入上始終產生完全相同的輸出結果。但是，在某些類型的算法中，隨機數序列也被當作輸入，這些隨機數使得算法每次運行時產生的輸出都不同。在第6章中將要詳細介紹的k-means聚類算法就是這類算法的一個例子，如圖1-12所示。

算法也可以分為如下兩種類型，分類的依據是簡化算法邏輯，使其運行速度更快時所采用的假設或近似：

• 精確算法：精確算法預計在不引入任何假設或近似的情況下產生精確解。
• 近似算法：當問題的復雜度過大，在給定的資源下難以處理時，我們會通過一些假設來簡化問題?；谶@些簡化或假設的算法稱為近似算法，它并不能給我們提供完全精確的解。

讓我們通過一個例子來理解精確算法和近似算法之間的區別。1930年，人們提出了著名的旅行商問題：為特定的旅行商找出最短路線，讓他能夠沿該路線訪問城市列表中的每個城市之后返回出發點（這就是問題被命名為旅行商問題的原因）。尋找解決方案時，第一個想法就是生成所有城市的排列組合，然后選擇路線最短的排列組合。這種解決方案的復雜度是O(n!)，其中n是城市的數量。顯然，城市數量超過30之后，時間復雜度就變得無法處理了。

如果城市數量超過30，那么降低復雜度的方法之一就是引入一些近似和假設。

對于近似算法來說，在需求分析時設置好期望的準確度很重要。驗證近似算法就是要驗證結果的誤差是否在可接受的范圍內。

1.6.2　可解釋性

算法在臨界條件下使用時，能夠在需要時解釋每一個結果背后的原因變得很重要。這是很有必要的，因為這能夠確?；谒惴ńY果得出的決策不會帶來偏差。

有些特征會直接或間接用于得到某種特定決策，能夠準確地識別出這些特征的能力，稱為算法的可解釋性。算法在臨界條件下使用時，需要評估算法是否存在偏差和偏見。如果算法可能影響到與人們生活相關的決策，則算法的倫理分析將會成為驗證過程中的標準環節。

對于處理深度學習的算法，很難實現算法的可解釋性。例如，如果某個算法用于拒絕某些人的抵押貸款申請，則透明度和解釋原因的能力都很重要。

算法可解釋性是一個活躍的研究領域。最近發展起來的有效技術之一是局部可理解的模型無關解釋（Local Interpretable Model-Agnostic Explanation, LIME），參見2016年第22屆國際計算機學會知識發現和數據挖掘國際會議（ACM SIGKDD）論文集。LIME基于如下概念，對每個輸入實例均做出各種細微改變，然后盡力映射出該實例的局部決策邊界，它可以量化每種細微改變對該實例的影響。