基于不變量的機器學習算法分析

寧一璇

(浙江理工大學 信息學院，杭州311121)

0 引 言

近年來，人工智能與機器學習技術已經越來越成熟，已經滲透到人們生活的方方面面。例如，圖像識別、無人駕駛等領域。伴隨著智能技術的發展，人們對于機器學習程序高質量的需求日益增加，但現階段對機器學習算法的分析與理解不足，并且傳統的軟件測試方法和評價標準也并不適用機器學習算法［1］。如何分析機器學習算法，已成為亟待解決的問題。

目前對機器學習進行質量分析，主要集中在以下幾種方法:

（1）提高數據集質量。如Chakarov等人［2］提出PSI工具。認為對于分類任務，訓練集中的錯誤會導致大量的分類錯誤。

（2）測試訓練好的模型。如Groce等［3］提出了WYSIWYT／ML框架，幫助終端用戶測試機器學習系統。

（3）利用蛻變測試方法，來測試機器學習程序代碼。如Xie等人［4］嘗試用蛻變測試來進行機器學習程序的測試。但從算法上對機器學習進行質量分析的研究甚少。

程序不變量常被用于追蹤軟件缺陷［5］、硬件錯誤［6］和軟件評估［7］。在程序運行時，能夠反映程序代碼在整個運行過程中，具有不變性質的邏輯斷言。不僅如此，還可以反映程序數據結構等各方面的信息，在程序的設計、測試等各方面都發揮著巨大的作用［8］。因此，可以將程序不變量用于機器學習算法的質量分析。

基于此，本文提出了基于不變量的機器學習算法分析。該分析方法將程序不變量與關鍵變量篩選提取方法相結合，通過對不同參數輸入下的機器學習算法進行程序不變量的生成，然后對生成得到的不變量集合進行關鍵變量的提取，進而對機器學習算法進行分析。本文使用5種機器學習算法作為示例算法，并對每個示例算法選取一種對算法性能產生影響的參數作為輸入。實驗結果表明，本文提出的方法可以從算法內部的屬性特點，分析機器學習算法的參數設置對算法準確率的影響。

1 方法概述

1.1 問題描述

通常的軟件測試方法，是通過執行測試用例集來發現程序源代碼中的錯誤。但機器學習算法與普通的代碼不同，其輸出是沒有對錯之分的，只有一個更適合于某個問題（數據集）的模型。機器學習算法的好壞程度，需要從正確率、時間空間復雜度以及數據集大小對算法效率的影響等幾個方面去比較分析［9］。若要保證算法結果的正確性，最重要的是:算法推導的正確性、算法效果的正確性以及算法應用的正確性?？偠灾?，僅用軟件測試的方法考慮機器學習是不充分的，應該從統計理論的角度，去分析一個機器學習算法是否優秀，是否有足夠高的正確率。

軟件分析技術可以應用在開發階段、維護階段以及復用階段。文獻［10］中，將軟件分析定義為:對軟件進行人工或者自動分析，以驗證、確認或發現軟件性質（或規約、約束）的過程或活動。軟件分析技術分為靜態分析與動態分析技術。

靜態與動態分析技術的一個基本過程如圖1所示。

圖1 靜態分析與動態分析的基本過程Fig.1 The basic process of static analysis and dynamic analysis

在軟件分析技術中，程序不變量檢測技術是一種將靜態分析和動態監測相結合的有效分析方法。程序不變量是影響軟件質量的要素之一，其在程序運行的整個過程中，反映了程序代碼具有不變性質的邏輯語句。不但能表現代碼的各種屬性特點，還能夠反映程序數據結構等各方面的信息［10］。

在程序開發過程中，程序不變量檢測技術已經開始被人們廣泛應用。程序不變量可以作為斷言插入到程序中，保證程序在進一步測試時隨著代碼的變化不被改變；可以過濾失效測試用例、驗證并改進測試套件、檢測軟件缺陷并對軟件進行精確的錯誤定位；可以檢測程序是否發生并發錯誤［11，14］等等。

因此，對于機器學習算法來說，可以應用程序不變量檢測技術，從算法內部的邏輯屬性，來分析機器學習算法是否擁有足夠高的正確率。

1.2 方法提出

本文方法的實現步驟以及工作流程如圖2所示。其中最重要的2個步驟分別是生成不變量與關鍵變量篩選。

圖2 基于不變量的機器學習算法分析流程圖Fig.2 The flow chart of machine learning algorithm analysis based on invariants

1.2.1 Daikon生成不變量

Daikon［13］是一個應用十分廣泛的不變量生成工具，其通過程序的動態運行來產生可能的不變量，可以對Java、C和C++等程序語言生成程序不變量。其產生不變量的過程如圖3所示。

圖3 Daikon處理流程圖Fig.3 Daikon processing flowchart

Daikon利用機器學習的原理，使用前端對程序注入特定的程序監測點，動態分析運行程序后，得到相應的數據軌跡文件（數據軌跡即為變量的行為，它反映了程序變量之間的關系），分析數據軌跡文件便能得到程序不變量。例如，本文使用一個名為Kvasir的前端對c++機器學習代碼生成數據軌跡文件，然后Daikon對數據軌跡文件進行處理，從數據軌跡文件中動態提取似然不變量，這些似然不變量在程序的某一或幾個特定的程序監測點上保持成立［11-14］。

1.2.2 關鍵變量篩選

盡管程序不變量是觀察代碼內部邏輯關系、檢測錯誤的有效方法，但由于機器學習算法是智能算法，運行時需要巨大的開銷，且其中產生的不變量過于龐大，而對系統中每個變量的監控是不必要的?；诖耍疚奶岢隽藢﹃P鍵變量進行篩選。在關鍵變量篩選階段，首先采用動態過濾機制Ⅰ和動態過濾機制Ⅱ，對成功執行程序后得到的所有變量進行過濾，得到一個關鍵變量集合［15］；然后使用靜態約簡機制，對關鍵變量集合進行進一步的約簡；最后從約簡的關鍵變量集合中，手動對算法正確性產生最大影響的關鍵變量提取。

1.2.2.1 動態過濾機制Ⅰ

動態過濾機制Ⅰ可以過濾第一類非關鍵變量。在程序分析階段，這類非關鍵變量并不會隨著參數的改變，對程序的結果產生關鍵的影響，因此不需要被監控。文中使用增量△來表示變量值的增加或減少。△是通過當前觀察值減去上一次的觀察值來獲得的［16］，如式（1）、式（2）所示。

△:＝CurrentValue-LastValue if LastValue≠?，（1）

△:＝0if LastValue＝?.（2）

動態過濾機制Ⅰ可以過濾掉第一類非關鍵變量，并將篩選出的關鍵變量儲存到集合KEY1中。動態過濾機制Ⅰ在訓練階段的處理過程如下:

（1）當觀察到第一個值Obersvation1時，給△賦值為0，最后一個值Last＿Observation更新為第一個值Obersvation1。

（2）在 下 一 次 觀 察 時，將 新 觀 察 到 的 值Obersvation2和最后一個值Last＿Observation之差更新為△。

（3）每次觀察后，生成一個更新的△（△2），并將其與當前△進行比較。若新△等于當前的△，則繼續進行判斷，否則將保存一個false標志，并將該變量的信息儲存到集合KEY1中。

（4）退出訓練過程，并返回關鍵變量集合KEY1。

1.2.2.2 動態過濾機制Ⅱ

使用動態過濾機制Ⅱ的目的，是從關鍵變量集合KEY1中再次過濾掉對算法的結果不產生影響、不需要被監控的非關鍵變量。動態過濾機制Ⅱ從關鍵變量集合KEY1中過濾掉這類非關鍵變量后，將剩余的關鍵變量儲存到新的關鍵變量集合KEY2中。動態過濾機制Ⅱ在訓練階段的處理過程如下:

（1）在程序第一次執行期間，范圍不變量Range＿Invariable會隨著給定變量的每次觀察而不斷更新，并將其范圍賦值給最新的Last＿Range＿Invariable。

（2）在下一次成功執行后，得到新的范圍不變量觀察值Range＿Invariable。判斷新的Range＿Invariable是否在上一次執行得到的Last＿Range＿Invariable范圍內。若在范圍內，則繼續進行下一次執行；否則保存一個false標志，并將該變量的信息儲存到集合KEY2中。

（3）退出訓練，并得到一個更新的關鍵變量集合KEY2。

1.2.2.3 靜態約簡機制

靜態約簡機制是通過分析函數之間的調用關系，對KEY2集合中的關鍵變量進一步的過濾約簡，并得到新的關鍵變量集合KEY3。

函數調用圖可以描述一個程序中各個函數之間的調用關系［17］。一般來說，函數調用圖可以分為靜態函數調用圖和動態函數調用圖兩類，靜態函數調用圖展示了程序在不運行狀態下的函數調用情況，而動態函數調用圖記錄了程序運行時的函數調用情況。在本文中，使用工具Cflow和Graphviz，構建靜態函數調用圖。例如，本文利用遺傳算法，解決TSP問題的tsp.cpp程序的靜態函數調用圖如圖4所示。

圖4 GA-tsp.cpp程序的函數調用圖Fig.4 Function call graph of GA-tsp.cpp program

1.2.2.4 關鍵變量提取

使用2個動態過濾機制和靜態約簡機制對程序中的變量進行過濾后，得到了一個關鍵變量集合KEY3。通過運行程序，調整程序運行時的輸入參數。在KEY3中發現，隨著參數的改變，將有一個變量會產生明顯的變化，而這個變量在程序中也與歐氏距離有著直接的關系，則定義這個變量為關鍵變量，并對其進行提取分析。

2 實驗與分析

實驗中共有5個機器算法程序，見表1。

表1 5種機器學習算法參數表Tab.1 5 machine learning algorithms

其中，Key＿N表示每個程序關鍵變量集合中關鍵變量的個數；Para＿N表示每個程序所取參數的個數；Run＿N表示每個參數運行次數。

2.1 遺傳算法

本文使用的第一個程序，是用遺傳算法求解TSP問題（Traveling Salesman Problem，旅行商問題）。

旅行商問題（TSP）是引起數學家和計算機科學家廣泛關注的一個問題，特別是因為其描述起來既容易又難以解決。問題簡單地表述為:如果一個旅行推銷員希望一次訪問m個城市列表中的每個城市一次（從i到j的旅行成本為cij），然后返回家鄉，那么旅行推銷員如何選擇最短的路徑［18］。

以規模較小的城市為例（這里取14個）。其中，種群數目sizepop＝100；交叉概率pc＝0.8；變異概率pm＝0.02；染色體長度（即城市個數）Lenchrom＝14。選擇最大進化代數maxgen為可變參數，并取20、40、60、80、100這5種參數和14個城市坐標作為輸入。首先，對最大進化代數為20的程序進行不變量生成，以14個城市的坐標點為輸入。通過2次動態篩選機制和靜態篩選機制，過濾掉了一些非關鍵變量，并得到關鍵變量集合見表2。

表2 GA-TSP中關鍵變量集合Tab.2 Collection of key variables in GA-TSP

接下來，對表2中的關鍵變量集合進行關鍵變量提取，提取出main（）:::EXIT程序點中的關鍵變量::min＿distance進行對比分析。由已經生成的主函數調用圖4中可以發現，關鍵變量::min＿distance是用歐式距離定義的變量。

得到關鍵變量后，需對其它4個參數（最大進化代數為40、60、80、100）的程序進行不變量的生成和關鍵變量::min＿distance的提取。由于遺傳算法每次運行得到的結果波動較大，因此對每一個參數都進行10次運行和關鍵變量的篩選與提取，并做了平均數比較。如圖5所示，圖中橫軸是每個參數運行的次數，縱軸是關鍵變量::min＿distance的大小。從圖中可知，隨著參數的變化，即最大進化代數的增大，::min＿distance逐漸趨于穩定，不會輕易產生較大的結果波動，也不會輕易地陷入局部最優解。如圖6所示，在做了平均值對比后，隨著參數（最大進化代數）的增大，::min＿distance是一個持續減小的過程，更加說明了機器學習算法的正確率與穩定性，會隨著參數的變化越來越好，從而印證了該方法的可行性。

圖5 每個參數運行10次Fig.5 Run 10 times for each parameter

圖6 不同參數的關鍵變量Fig.6 Key variables for different parameters

2.2 蟻群算法

本文使用的第二個程序，是以蟻群系統為模型的蟻群算法程序（非螞蟻周模型），并以TSP問題為測試對象。蟻群算法是一種基于種群的啟發式隨機搜索算法，具有正反饋、魯棒性、并行性等優點，可以使用蟻群算法解決最短路徑問題。在計算最短路徑時，使用最近鄰方法是從源節點出發，每次選擇一個距離最短的點來遍歷所有的節點得到的路徑（距離可以用歐式距離公式來表示）。但蟻群算法在計算兩節間的最短距離時易陷入局部最優，且隨著算法復雜程度的增加其收斂速度慢，還有可能出現停滯現象。

在蟻群算法中，主要有6個參數:信息啟發因子α，期望啟發因子β，全局信息素揮發參數ρ，局部信息素揮發參數α1，螞蟻數量M，以及最大循環次數NcMax。本實驗探究最大循環次數NcMax與蟻群算法性能之間的關系。函數調用如圖7所示。

圖7 ACO-tsp.cpp程序的函數調用圖Fig.7 Function call graph of ACO-tsp.cpp program

通過2次關鍵變量篩選機制和關鍵變量提取，得到直接反應歐氏距離的關鍵變量::Lnn。對每個參數進行20次運行和關鍵變量的篩選與提取，并做了平均數比較，結果如圖8所示。得到的關鍵變量集合見表3。

表3 ACO-TSP中關鍵變量集合Tab.3 Set of key variables in ACO-TSP

由圖8可知，最大循環次數NcMax對算法的正確性以及穩定性有較大影響，可以直接從與歐氏距離相關的關鍵變量中反映出來。當循環次數越大，蟻群算法的性能越好，也越穩定。

2.3 模擬退火算法

本文使用的第三個程序，是用模擬退火算法解決TSP問題。該問題給定平面上10個點的名稱與坐標，2點之間的距離為其歐幾里得距離。求一條路徑，剛好經過每個點一次，使其路徑長度最短。

模擬退火算法是一種基于自身退火原理的隨機搜索算法，其準確率與最優解的精度主要與退火速率Δ、初始溫度T、終止溫度e、以及循環代數L有關。根據實驗可得:當循環代數L越大時，與歐幾里得距離直接相關的關鍵變量this-＞loc＿distance和this-＞min＿distance越來越小，模擬退火算法越能跳出局部最優解，得到最短路徑。關鍵變量集合與實驗結果見表4和圖9所示。

圖9 不同參數的關鍵變量Fig.9 Key variables of different parameters

表4 SA-TSP中關鍵變量集合Tab.4 Set of key variables in SA-TSP

2.4 K-means聚類算法

第四個示例程序，是一個K-means聚類算法實現。輸入數據集為所有點的集合，是一個二維矩陣。給定k值，將數據集中的所有點分為k類，計算k個中心點（質心）、每個點所屬的歸類以及距離值。其中，每個點與質心的距離由歐氏距離定義與計算。如圖10所示，取k＝｛2，3，4，5，6｝后發現，當k值越大時，聚類效果越好。

圖10 k-means聚類結果Fig.10 K-means clustering results

從不變量角度看，取k＝｛2，3，4，5，6｝后，會產生｛2，3，4，5，6｝個類別。每個類別里，質心與歸類的每個點之間的歐氏距離，即關鍵變量＿＿first［］.minDist會越來越小，如圖11所示。關鍵變量集合見表5。

圖11 關鍵變量趨勢圖Fig.11 Trend chart of key variables

表5 k-means中關鍵變量集合Tab.5 Set of key variables in k-means

2.5 KNN分類算法

第五個示例程序假設了一個場景，用KNN分類算法為坐標上的點進行分類，如圖12所示。由圖所見，共提供13個坐標點，每個坐標點都有相應的坐標（x，y）以及其所屬的類別A或B?，F給定一個點坐標（1.5，-0.5），判斷其屬于類別A或類別B。對于KNN分類算法:參數k是指選擇樣本數據中前k個最相似數據；計算待分類點與已知類別點之間的歐氏距離；選擇k個最相似數據中出現次數最多的分類，作為測試數據的分類。

圖12 KNN示例程序Fig.12 KNN sample program

本次示例中選取k＝｛3，5，7，9｝。經過不變量的生成和關鍵變量的篩選與提取后，可以發現，前k個歐式距離最短的關鍵變量在分類中起著決定性的作用。而隨著k的增大，最相似數據的數量不斷增大，歐式距離最短的關鍵變量所代表的數據標簽出現的可能性也會越來越大，這時分類結果也會更加的準確。關鍵變量集合見表6，其中:distance即為該實例程序中與歐氏距離直接相關的關鍵變量。

表6 KNN中關鍵變量集合Tab.6 Set of key variables in KNN

3 結束語

本文提出了一種基于不變量的機器學習算法分析方法。通過改變算法的參數，得到不同參數下的關鍵變量并分析其變化?？梢缘贸?當機器學習算法的準確性，隨著參數的調整越來越好時，基于歐氏距離的關鍵變量總會以一種特定的規律變化。使用靜態分析加動態分析的方法，從程序不變量的角度初步探索了機器學習算法的質量，驗證了對應算法的魯棒性；探索了機器學習算法中的不變量，有別于普通程序和并發程序的不變量；機器學習算法中的不變量數量龐大，并且具有很大的不穩定性，需要進行反復多次的實驗和變量的篩選。

進一步的研究將把本文方法擴展到更大、更復雜的機器學習算法中，改進關鍵變量的篩選機制，研究是否有更多的關鍵變量對算法正確率有影響，以及不同的算法與關鍵變量之間的關系。希望可以通過除Daikon以外其它的工具來生成不變量。此外，需要改進和研究的方面主要包括:開發一種方法來獲得更加完整的關鍵變量集合；在更龐大、更復雜的機器學習算法上進行實驗驗證。