不同Halton抽樣方法在混合Logit模型中的比較

史楠楠 諸立超

(同濟大學交通運輸工程學院道路與交通工程教育部重點實驗室1) 上海 201804)(悉尼大學商學院交通運輸與物流研究所2) 悉尼 2006)

?

不同Halton抽樣方法在混合Logit模型中的比較

史楠楠1)諸立超1,2)

(同濟大學交通運輸工程學院道路與交通工程教育部重點實驗室1)上海 201804)(悉尼大學商學院交通運輸與物流研究所2)悉尼 2006)

以混合Logit模型參數估計中應用最廣泛的四類Halton抽樣方法為研究對象，包括Halton、變序Halton、亂序Halton和去隨機化Halton，借助平均絕對百分誤差箱型圖比較不同維度、不同抽樣方法得到的參數估計值，同時結合數百次模擬概率標準差判斷不同抽樣方法適用性.結果表明,在低維度情況下，各Halton抽樣方法參數估計結果相差不大，且亂序Halton抽樣性質與偽隨機抽樣無異；而隨著維度的增加，幾類Halton的抽樣點均勻程度逐漸與偽隨機抽樣接近，且變序Halton抽樣優于其他3類Halton抽樣.

混合Logit模型；參數估計；偽隨機抽樣；Halton抽樣

0 引 言

離散選擇模型從隨機效用最大化角度給定了個體選擇衡量標準，從最簡單的多項Logit模型(multinomial logit，MNL)一直到約束最少的混合Logit模型(mixed logit，ML)，參數估計方法也由極大似然估計(maximum likelihood estimation，MLE)拓展至極大模擬似然估計(maximum simulation likelihood estimation，MSLE).為能夠利用ML模型研究面板數據和決策者異質性等問題，需使用蒙特卡羅方法(monte carlo method，MC)估計參數.MC的主要思想是對概率密度函數進行多次抽樣，并以模擬概率均值作為積分近似解.自Train將Halton抽樣引入ML模型參數估計后，又有許多學者將Halton抽樣及其變形(變序Halton序列等)及其他低差異序列(Faure序列等)引入進來，極大豐富了ML模型參數估計中所使用的抽樣方法.

Train[1]通過比較ML模型概率的模擬方差(simulation variance)，得出Halton抽樣遠優于偽隨機抽樣(pseudo-random sampling)的結論.Bhat[2]從參數估計角度也得到了類似結論，其評價指標包括均方根誤差(root mean square error，RMSE)、平均絕對百分誤差(mean absolute percentage error，MAPE)和收斂時間(time to convergence，TTC)指標.此后，Bhat[3]進一步引入變序Halton(Scrambled Halton)抽樣，在多項Probit模型應用中比較3種方法，最后認為變序Halton抽樣最優，Halton抽樣次之.Hess等[4]則比較了包括Halton抽樣、變序Halton抽樣和亂序Halton(Shuffled Halton)抽樣等在內的3類抽樣方法，雖然后兩者均存在解決Halton相關性的潛力，但作者認為變序Halton抽樣在一定程度上并不穩定，并且維度局限于16維以下.Hess等[5]在3類Halton抽樣基礎上增加修正拉丁超立方體抽樣(modified latin supercube sampling，MLHS)估計16維參數，得到MLHS最優的結論.有趣的是，這4類方法與偽隨機抽樣的均方根誤差相差不大，Hess等認為，一維數列未結構化組合得到的多維序列性質會隨維度的增加而逐漸趨近于偽隨機抽樣.Status[6]對偽隨機抽樣、Halton抽樣和亂序Halton抽樣的研究結論與以往不同，認為雖然亂序Halton抽樣減小了Halton抽樣高維度的相關性、提高了抽樣分布均勻度，但從參數估計結果和極大似然值來看，利用亂序Halton抽樣得到的結果反而比Halton抽樣差，僅在少數情況下優于Halton抽樣.

鑒于目前尚無證據表明某一種低差異序列明顯優于另一種序列，并且學者們也未對幾種Halton抽樣的優劣形成統一意見，因此文中仍對Halton序列進行研究.文中的主要貢獻在于：(1)既有研究并未結合參數估計和概率計算兩方面結論比較抽樣方法優劣，文中借助箱型圖和平均絕對百分誤差指標比較分析各Halton抽樣方法優劣；(2)現有文獻對亂序Halton抽樣是否優于Halton抽樣和變序Halton抽樣持有兩種截然不同的觀點，文中針對這一問題研究得到相應結論.

1 偽隨機抽樣

所謂隨機序列，就是后一個數與前一個數無關的序列，真正的隨機數使用,例如,擲錢幣等物理現象產生，缺點在于技術要求較高，而在實際應用中往往使用偽隨機數便能滿足大部分要求.偽隨機數看似隨機，實際由固定、可重復的算法生成，并非真正隨機.偽隨機數的生成主要根據如下3種方法：(1)直接法(direct method)；(2)逆轉法(inversion method)；(3)接受拒絕法(acceptance-rejection method)[7].文中采用逆轉法生成偽隨機數，首先生成[0,1]之間服從均勻分布的隨機數U，假設U服從的累積分布函數為F，根據X=F-1(U)求得最終隨機數.

2 Halton抽樣及其變形

2.1 標準Halton抽樣

相比于偽隨機抽樣，Halton抽樣存在如下優點：(1)在絕大部分積分區域內，抽樣點分布十分均勻；(2)下一次抽樣點與上一次抽樣點存在負相關性，即下一次抽樣點可填補上一次抽樣點未包含的區域，提高了抽樣點覆蓋率.

2.2 變序Halton抽樣

Halton序列的主要問題在于高維度序列的相關性，導致積分區域抽樣不均并引起積分誤差.此問題并不僅僅針對高維度質數，主要由兩個質數之比過分接近于1所引起.變序Halton抽樣的想法最初由Braaten等[8]提出，旨在改善高維度Halton序列的均勻度.基本思想是打亂以r為數基、循環長度為r的Halton序列，從而降低不同維度間的相關性.通過變換b1(n)…bS(n)順序(見表1)得到變序Halton序列，并且變換后的序列仍保持Halton序列N-1(N為抽樣數)的積分誤差.

表1 變序Halton序列變換

2.3 亂序Halton抽樣

亂序Halton抽樣最初由Morokoff等[9]于1994年提出，為一種采用獨立隨機向量變換Halton序列的方法，隨后被Hess等[10]命名為亂序Halton序列.由前文可知，所生成的Halton序列和變序Halton序列固定，即每次生成序列不發生變化，而生成亂序Halton序列需融合Halton序列和偽隨機數，生成序列與隨機種子的設置相關.產生機理如下：(1)首先產生以r為數基、長度為N的Halton序列；(2)然后生成同樣長度的偽隨機序列，Halton序列與偽隨機序列一一匹配；(3)偽隨機序列從小到大(或從大到小)排列，相應地，變換Halton序列順序得到一維亂序Halton序列.若需生成d維亂序Halton序列，則應生成d維偽隨機序列(不同隨機種子)，然后根據步驟(3)便可生成d維亂序Halton序列.Hess等已證明亂序Halton序列比變序Halton序列更有潛力提供更佳的多維積分區域抽樣覆蓋率，但Schlier[11]認為亂序Halton抽樣并非低差異序列，其表現與偽隨機抽樣相近，下文也將探討這一問題.

2.4 去隨機化Halton序列

線性加擾是消除Halton序列相關性的簡單有效的方法，文中借鑒去隨機化Halton序列，基于數字置換變換Halton序列：

式中：φπri(n)為集合{0,1,2,…,ri-1}的置換.采用線性函數f(x)=wx進行加擾：

(2)

前12維去隨機化Halton序列的wi最優值見表2.

表2 去隨機化Halton序列的wi最優值

3 抽樣方法比較

圖1 二維抽樣點分布圖

下面以二維序列為例，進一步比較不同Halton抽樣所得抽樣點分布情況，選取低維質數2、3及高維質數59，61繪制100個抽樣點的分布圖，見圖2、圖3.

圖2 以2,3為數基的Halton序列二維點分布圖

圖3 以59,61為數基的Halton序列二維點分布圖

由圖2、圖3可見，當使用低維度質數時，直觀感覺亂序Halton抽樣點分布不如其他3類Halton抽樣均勻，其余3類Halton抽樣點均勻度并無顯著差異；但隨著使用質數維度的增加，如使用第17和18維質數時，由于高維度質數序列相關性導致Halton抽樣表現越來越差，見圖3a)；而亂序Halton抽樣表現基本不變，變序Halton抽樣和去隨機化Halton抽樣也可在一定程度上減輕Halton抽樣相關性問題.

4 混合Logit模型參數估計結果比較

4.1 混合Logit模型

(3)

(4)

這一指標越小說明得到的參數估計值與參數真值越接近，表明抽樣方法越好.

4.2 參數估計結果

偽隨機抽樣和亂序Halton抽樣會因每一次隨機種子選取的不同而產生不同序列，Halton抽樣、變序Halton抽樣和去隨機化Halton抽樣則保持不變.考慮到Halton抽樣前幾次抽樣點相關性較高，因此在第i次抽樣時，舍去前10×i個數，也可參考Tuffin對Halton序列作隨機化處理.文中所采用的數據為決策者對三種動力汽車(電力、天然氣和混合動力)的選擇數據，主要變量有價格、高性能、中高性能、運行費用、行駛距離范圍和啞元(電力和混合動力)等，文中不再贅述具體數據，詳見文獻[12].下文針對1至3個隨機參數的情況采用不同抽樣方法估計參數.

首先比較一維情況下的4類Halton抽樣，見圖4.由圖4可知，(1)Halton抽樣與變序Halton抽樣相同，并且均優于去隨機化Halton，緊接著是抽樣次數較多(250次)的隨機抽樣，亂序Halton表現最差；(2)隨著抽樣次數的增加，除去隨機化Halton略優于Halton和變序Halton外，其余Halton抽樣優劣保持不變，100(150)次Halton抽樣和變序Halton抽樣基本相同，略優于500(1000)次偽隨機抽樣.

圖4 一維參數估計結果比較(質數：2)

在二維情況下：(1)去隨機化Halton抽樣最優，亂序Halton抽樣的表現始終最差；(2)偽隨機抽樣與4類Halton抽樣的差異要比在一維情況下有所減小，甚至因抽樣次數較多而優于4類Halton抽樣，這在一定程度上證實隨著維度的增加，Halton抽樣會逐漸向偽隨機抽樣靠攏的結論.

在選用質數2,3和5作為數基的三維情況下，4類Halton抽樣除亂序Halton抽樣外，不同抽樣次數下的抽樣方法各有優劣，不能得到明確結論；而選用較大質數43、47和53作為數基時，結果發生明顯轉變，變序Halton和亂序Halton抽樣要優于其他2種抽樣，而變序Halton抽樣最佳，表明在高維情況下使用較大質數生成的變序Halton抽樣和亂序Halton抽樣更優.

通過比較不同維度、不同質數的Halton抽樣，可知亂序Halton抽樣的表現與偽隨機抽樣類似，在低維情況下始終是4類Halton抽樣中最差的，造成這一結果的原因是低維Halton序列不存在嚴重相關性，對其進行隨機化并不能起到改善作用，反而會使均勻度下降，但隨著維度的增加，其他Halton抽樣表現的惡化反而凸顯出亂序Halton抽樣的優勢.

DH50為50次去隨機化Halton抽樣)；H50為50次Halton抽樣；P250為250次偽隨機抽樣；SC50為50次變序Halton抽樣；SF50為50次亂序Halton抽樣.圖5～圖8中的橫坐標代表的參數依此類推.

圖5 二維參數估計結果比較(質數：2和3)

圖6 三維參數估計結果比較(質數：2,3和5)

圖7 三維參數估計結果比較(質數：43,47和53)

圖8 三維參數估計結果比較(質數：83,89和97)

4.3 概率計算結果

進一步根據如下方法研究模擬概率性質：選取某一樣本，結合上文所得3個隨機參數的估計結果，利用不同抽樣方法模擬該樣本概率1000次，假設每次模擬抽樣數為R，則序列長度為1 000×R+10(刪去前10個Halton抽樣點).表3給出了使用不同數量、不同抽樣方法的模擬概率統計量.標準差越小表明模擬概率越穩定、抽樣點分布越均勻，根據不同抽樣方法的1 000次模擬概率標準差可知：(1)當抽樣使用低維質數時，Halton抽樣以極小優勢優于變序Halton抽樣，緊接著是去隨機化Halton抽樣，亂序Halton抽樣表現最差；(2)當抽樣使用高維質數時，偽隨機抽樣和亂序Halton抽樣表現與使用低維質數時幾乎不變，亂序Halton抽樣表現略有下滑，而去隨機化Halton抽樣表現下滑幅度最明顯.

表3 不同抽樣方法及抽樣次數下的模擬概率統計量

5 結 束 語

文中從ML模型參數估計和模擬概率計算兩方面比較不同Halton抽樣優劣.在低維度情況下，除亂序Halton抽樣以外的其余3類Halton抽樣相對表現會隨抽樣次數的變化而波動，各有優劣，亂序Halton抽樣表現始終最差，其性質并未優于偽隨機抽樣；而隨著維度的增加，這一結論逐漸發生反轉，由于高維度Halton抽樣序列存在相關性，使原本表現不佳的亂序Halton抽樣逐漸好轉，并與變序Halton抽樣相差無幾；此外，結合模擬概率統計量，證實了變序Halton抽樣會隨維度的增加，逐漸成為幾種Halton抽樣中最佳的結論.不難推論，當隨機參數數量較少時，使用變序Halton抽樣所得參數估計值更加精確；而當隨機參數數量較多時，可能使用偽隨機抽樣所得參數估計值更為精確.但由于數據受限，文中未對高維度下的各種抽樣方法進行全面比較，所得結論仍需進一步論證，同時變序Halton抽樣與偽隨機抽樣在多少維度時表現相同也值得深入研究.

[1]TRAIN K. Halton sequences for mixed logit[EB/OL].(1999-08-02)[2016-03-22]. http://elsa.berkeley.edu/wp/train0899.pdf.

[2]BHAT R C. Quasi-random maximum simulated likelihood estimation of the mixed multinomial logit model[J]. Transportation Research Part B: Methodological,2001,35(7):677-693.

[3]BHAT R C. Simulation estimation of mixed discrete choice models using randomized and scrambled Halton sequences[J]. Transportation Research Part B: Methodological,2003,37(9):837-855.

[4]HESS S, POLAK J W. On the performance of shuffled Halton sequences in the estimation of discrete choice models[EB/OL].(2003-06-08)[2016-03-22].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.110.3610&rep=rep1&type=pdf.

[5]HESS S, TRAIN K, POLAK J W. On the use of a modified latin hypercube sampling (MLHS) method in the estimation of a mixed logit model for vehicle choice[J]. Transportation Research Part B: Methodological,2006,40(2):147-163.

[6]STAUS A. Standard and shuffled Halton sequences in a mixed logit model[EB/OL].(2008-09-07)[2016-03-22].https://marktlehre.uni-hohenheim.de/fileadmin/einrichtungen/marktlehre/Arbeitsberichte/haa_nr17.pdf.

[7]DíAZ C N, GIL A V, VARGAS M J. Assessment of the suitability of different random number generators for monte carlo simulations in gamma-ray spectrometry[J]. Applied Radiation and Isotopes,2010,68(3):469-473.

[8]BRAATEN E, WELLAR G. An improved low-discrepancy sequence for multidimensional quasi monte carlo integration[J]. Journal of Computational Physics,1979,33(2):249-258.

[9]MOROKOFF W J, CAFLISCH R E. Quasi-random sequences and their discrepancies[J]. Society for Industrial and Applied Mathematics,1994,15(6):1251-1279.

[10]HESS S, POLAK J W. The shuffled Halton sequence[R]. Centre for Transport Studies (CTS) Working paper,2003.

[11]SCHLIER C. On scrambled Halton sequences[J]. Applied Numerical Mathematics,2008,58(10):1467-1478.

[12]TUFFIN B. On the use of low discrepancy sequences in monte carlo methods[J]. Monte Carlo Methods and Applications,1996,2(4):295-320.

Comparison of Different Halton Sampling Methods in Mixed Logit Model

SHI Nannan1)ZHU Lichao1,2)

(CollegeofTransportationEngineering,KeyLaboratoryofRoadandTrafficEngineeringoftheMinistryofEducation,TongjiUniversityShanghai201804,China)1)(InstituteofTransportandLogisticsStudies,TheBusinessSchool,TheUniversityofSydney,NSW2006,Australia)2)

Several Halton sampling methods which are widely used in mixed logit model parameter estimation are taken as the research objects, including Halton, scrambled Halton, shuffled Halton and derandomized Halton sampling. Based on box plot of mean absolute percentage error, parameter estimators of different Halton samplings are compared under different dimensions. Meanwhile, standard error of hundreds of probability simulation is analyzed to judge the applicability of different methods. The result shows that: under low-dimension, all Halton sampling methods have almost no difference in parameter estimation results, and shuffled Halton sampling is the same as pseudo random sampling; with the increase of dimension, distribution uniformity of sampling points from Halton sampling methods is gradually approaching to pseudo-random sampling, while the scrambled Halton sampling is better than the other three Halton sampling methods.

mixed logit model; parameter estimation; pseudo sampling; Halton sampling

2016-08-20

U491 doi:10.3963/j.issn.2095-3844.2016.05.030

史楠楠(1992- )：女，碩士生，主要研究領域為交通運輸規劃與管理、離散選擇建模