神經(jīng)網(wǎng)絡(luò)在測試抽樣中的應(yīng)用

1.     工具產(chǎn)生的背景

導(dǎo)航對人們的生活起著越來越重要的作用，由于公司一直在做導(dǎo)航產(chǎn)品，所以為了從深度上保證產(chǎn)品的質(zhì)量（已經(jīng)通過大量的case從廣度上來保證產(chǎn)品質(zhì)量），做為Routing的測試負(fù)責(zé)人，我對導(dǎo)航算法進(jìn)行了深入的研究。

在做Map Data的Regression時，我們是基于導(dǎo)航對底層的數(shù)據(jù)進(jìn)行測試，而MapData是經(jīng)過Tools Team 轉(zhuǎn)換的，所以原始數(shù)據(jù)的改動、Tools的改動都會引起導(dǎo)航的變化，而這兩層對從上層測試的我們來說都是blackbox。測試時，用自動化工具找出difference很容易，但check起來相當(dāng)困難，因?yàn)槲覀儾还庑枰缆肪€變了，而且需要知道它是怎么變的，否則你不知道你的模型是不斷優(yōu)化的。當(dāng)時一天也就check十幾條路線變化的case，對于五六千條case的一輪Regression，測試工作量是呈指數(shù)增長的，已經(jīng)不是增加一兩個人就能解決問題的。

導(dǎo)航，本身就是機(jī)器學(xué)習(xí)的過程，所以用傳統(tǒng)的功能測試抽取case覆蓋各個feature的方法在這種情況下不是完全適用：一是因?yàn)橐粭l規(guī)劃的路線會涉及到幾百、甚至上萬條link，每條link又有多個影響因子，如果有一個或幾個因子變化，都可能引起導(dǎo)航路徑的變化，更何況是這么多個可變因子，而且以前設(shè)計(jì)的覆蓋Feature的case，可能會因?yàn)閿?shù)據(jù)變了就cover不到了；二是因?yàn)闄C(jī)器學(xué)習(xí)本身就是通過大量的數(shù)據(jù)，對原型不斷進(jìn)行訓(xùn)練、不斷優(yōu)化的過程，所以減少case進(jìn)行測試，很可能會使模型陷入局部最優(yōu)。所以作為數(shù)學(xué)系的我，認(rèn)為機(jī)器學(xué)習(xí)的原型用機(jī)器學(xué)習(xí)的方法測試才是最好的解決方案，于是想到了神經(jīng)網(wǎng)絡(luò)。

在這個時期飽受折磨的不光是我們team的QA，ToolsTeam的dev也被要求用我們的Regression工具check case，要知道他們對導(dǎo)航的邏輯不了解，check起來難度多大（即使知道導(dǎo)航變了，但為什么變，你得知道）。這使我深刻意識到自動化工具的思想，比自動化工具的開發(fā)要重要得多，Tools  Team的lead曾經(jīng)說過一句話：只要你有想法，我們就能把工具做出來。所以經(jīng)過大概兩周的折磨，在凌晨四點(diǎn)的睡夢中終于有了solution，而不是idea，當(dāng)時那叫一個興奮啊JJ

第二天，跟mgr討論了之后，他同意了我的solution，于是找到ToolsTeam的一個牛人，僅用了幾天時間，就把工具生成出來了。

2.      人工神經(jīng)網(wǎng)絡(luò)ANN (Artificial Neural Network)

主要類型：

·        前向神經(jīng)網(wǎng)絡(luò)

·        反饋網(wǎng)絡(luò)

·        自組織網(wǎng)絡(luò)

·        相互結(jié)合型網(wǎng)絡(luò)

為了使模型相對簡單、準(zhǔn)確，我們采用三層前向神經(jīng)網(wǎng)絡(luò)（即含一個隱含層）

3.     實(shí)現(xiàn)的思想

·        抽取difference

        采用第三方工具(diff.exe)將新舊地圖的difference進(jìn)行對比（類似Beyond Compare的功能）并且輸出。

·        使用神經(jīng)網(wǎng)絡(luò)模型

輸入層：diff.exe的output。

隱含層：內(nèi)部處理邏輯

輸出層：分類的結(jié)果和變化的cost

輸入層到隱含層的權(quán)重：w(ih)

隱含層到輸出層的權(quán)重：w(ho)

·        實(shí)現(xiàn)分類

根據(jù)feature 進(jìn)行分類，通過config.xml手動配置來定義分類的優(yōu)先級：

·        計(jì)算從輸入層到隱含層的權(quán)重w(ih)

將priority 轉(zhuǎn)換成 [0, 1]之間的數(shù)（當(dāng)時就卡在了這個轉(zhuǎn)換過程上，想到了神經(jīng)網(wǎng)絡(luò)，但就是不知道怎么將現(xiàn)有的輸入和期望的輸出轉(zhuǎn)換成數(shù)學(xué)模型）：

F1 = (1/2)^1

F2= (1/2)^2

F3 =(1/2)^3

F4 = (1/2)^4

F5 =(1/2)^5

F6 = (1/2)^6

F7=(1/2)^7

…

Notes:

1）  Fn: 代表第n個feature

2）  根據(jù)等比數(shù)列1/2^n 給每個分類因素定義權(quán)重，這樣做的目的是為了使每個weight最后加起來的值無限接近但<1，即使所有的expectedresult 全變化了，最大值不會超過1

3）分類的順序可以根據(jù)每次的改動調(diào)整

4）Config.xml的格式可修改為：

<priority>

       <pr name="F1"value=1/>

       <pr name="F2"value=2/>

       <pr name="F3" value=3/>

       <pr name="F4"value=4/>

<prname="F5"value=5/>

       <pr name="F6" value=6/>

       <pr name="F7" value=7/>

…

       <pr name="Fn" value=0/>

</priority>

因此每個分類的weight=(1/2)^value

（對于不需要check的difference，不用計(jì)算，value設(shè)為0）

4.      定義隱含層到輸出層的權(quán)重w(ho)：

對于每個feature，可能不止一處發(fā)生變化，根據(jù)經(jīng)驗(yàn)，設(shè)置可能變化的最大個數(shù)（config.xml里配置，可手動修改）

Config.xml可定義為

                        <hidden_output>

                                        <f1weight="1/5"/>

                                        <f3 weight="1/10"/>

                                        <f4weight ="1/3"/>

                                        <f5weight="1/10"/>

…

                        </hidden_output >

·          由于之前把主要的精力放到了check路線變化的case上，既慢又發(fā)現(xiàn)不了什么問題，后來經(jīng)過經(jīng)驗(yàn)和簡單利用了下統(tǒng)計(jì)的原理，證明了引起長路徑的變化的主要因子是路的等級和速度（通常這兩個因子會引起一些列link都變），所以根據(jù)路線變化的段數(shù)計(jì)算cost，而非長路徑導(dǎo)航。

·          這里比較麻煩的地方是Maneuver，因?yàn)槊總€Maneuver的提示（左轉(zhuǎn)、右轉(zhuǎn)、上高速等等）還有另外一整套邏輯，是分類工具比較復(fù)雜的地方。

·          權(quán)重的計(jì)算思想為：通過對Tools調(diào)研，知道Tools對哪些屬性進(jìn)行了處理（因?yàn)?/span>Tools的復(fù)雜度較高，了解詳細(xì)的邏輯cost非常大，所以只是通過代碼復(fù)雜度和邏輯復(fù)雜度知道個大概的情況）。根據(jù)line by line的讀導(dǎo)航的 code，知道Maneuver的產(chǎn)生條件，并計(jì)算出Tools處理過的屬性占每個maneuver的cost；根據(jù)Tools的代碼復(fù)雜度和邏輯復(fù)雜度（復(fù)雜度越高，bug可能越多）以及客戶（Customer bug is very important）報(bào)的bug類型，計(jì)算出每類maneuver的cost, 根據(jù)這兩個cost，計(jì)算出Tools的影響和客戶發(fā)現(xiàn)的bug占每個maneuver的cost；最后進(jìn)行歸一化處理。即：從導(dǎo)航的邏輯、客戶、Tools的改動，以及最后的表現(xiàn)形式上計(jì)算cost。

·          config.xml可定義為：

                                <all_maneuvers>

                                <amname="NC." weight=0.XX/>

                                <amname="CO." weight=0.XX/>

                                                <amname="KP." weight=0.XX/>

                                                <amname="KP.L" weight=0.XX/>

…

</all_maneuvers>

5.     計(jì)算從輸入層到輸出層的cost：

·        F1: cost = w(ih)(F1)*(1/2+n*w(ho)(F1))=(1/2)^1*(1/2+1/2*n*1/5)

·        F2: cost = w(ih)(F2)*(1/2+each w(ho)(F2))=(1/2)^2*(1/2+ 1/2*each maneuver weightfrom hidden layer to output layer)

·        F3: cost = w(ih)(F3)*(1/2+n*w(ho)(F3))=(1/2)^3*(1/2+1/2*n*1/10)

·        F4: cost = w(ih)( F4)*(1/2+n*w(ho)( F4))=(1/2)^4*(1/2+1/2*n*1/3)

·        Fm: cost = w(ih)( Fm)*(1/2+n*w(ho)( Fm))=(1/2)^9*(1/2+1/2*n*1/30)

(n 代表每類feature的變化數(shù)量)

Notes:

1）  由此可見，F1的取值范圍應(yīng)該是[1/4, 1/2],F2的取值范圍是[1/8, 1/4], F3的取值范圍是[1/16, 1/8], …

2）  由于一條case里，可能既含有F1的，又含有F2, 所以F1的權(quán)重應(yīng)該在[1/4,1],同理類推F2分類里權(quán)重的總和應(yīng)該在[1/8, 1/2],,…（在已經(jīng)正確分類的基礎(chǔ)上，即使F2的cost比F1的大，也不會影響case的選?。?/span>

6.     用聚類分析方法根據(jù)最終的cost大小抽取指定數(shù)量的case。

7.     優(yōu)點(diǎn)：

1.       在不減少Test Scope的情況下，可以合理的抽取case；在有限的時間內(nèi)，check變化最大的case。

2.       通過了解Tools的改動，手動配置測試范圍和優(yōu)先級，來保證產(chǎn)品質(zhì)量。

3.      由于人工check結(jié)果時會把difference里的所有變化全check，所以此工具也是在模擬人的操作。

8.     缺點(diǎn)：

1．由于Case的output是基于Maneuver的，而非Routing，所以計(jì)算時存在分類錯誤，但考慮到改動開發(fā)的code cost比較高，只能根據(jù)現(xiàn)有的結(jié)果和經(jīng)驗(yàn)進(jìn)行優(yōu)化。

2．神經(jīng)網(wǎng)絡(luò)本身可能陷入局部最優(yōu)，所以即使權(quán)重調(diào)整再大，期望結(jié)果也可能會很小。