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

史楠楠 諸立超

(同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室1) 上海 201804)(悉尼大學(xué)商學(xué)院交通運(yùn)輸與物流研究所2) 悉尼 2006)

?

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

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

(同濟(jì)大學(xué)交通運(yùn)輸工程學(xué)院道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室1)上海 201804)(悉尼大學(xué)商學(xué)院交通運(yùn)輸與物流研究所2)悉尼 2006)

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

混合Logit模型；參數(shù)估計(jì)；偽隨機(jī)抽樣；Halton抽樣

0 引 言

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

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

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

1 偽隨機(jī)抽樣

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

2 Halton抽樣及其變形

2.1 標(biāo)準(zhǔn)Halton抽樣

相比于偽隨機(jī)抽樣，Halton抽樣存在如下優(yōu)點(diǎn)：(1)在絕大部分積分區(qū)域內(nèi)，抽樣點(diǎn)分布十分均勻；(2)下一次抽樣點(diǎn)與上一次抽樣點(diǎn)存在負(fù)相關(guān)性，即下一次抽樣點(diǎn)可填補(bǔ)上一次抽樣點(diǎn)未包含的區(qū)域，提高了抽樣點(diǎn)覆蓋率.

2.2 變序Halton抽樣

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

表1 變序Halton序列變換

2.3 亂序Halton抽樣

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

2.4 去隨機(jī)化Halton序列

線性加擾是消除Halton序列相關(guān)性的簡(jiǎn)單有效的方法，文中借鑒去隨機(jī)化Halton序列，基于數(shù)字置換變換Halton序列：

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

(2)

前12維去隨機(jī)化Halton序列的wi最優(yōu)值見表2.

表2 去隨機(jī)化Halton序列的wi最優(yōu)值

3 抽樣方法比較

圖1 二維抽樣點(diǎn)分布圖

下面以二維序列為例，進(jìn)一步比較不同Halton抽樣所得抽樣點(diǎn)分布情況，選取低維質(zhì)數(shù)2、3及高維質(zhì)數(shù)59，61繪制100個(gè)抽樣點(diǎn)的分布圖，見圖2、圖3.

圖2 以2,3為數(shù)基的Halton序列二維點(diǎn)分布圖

圖3 以59,61為數(shù)基的Halton序列二維點(diǎn)分布圖

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

4 混合Logit模型參數(shù)估計(jì)結(jié)果比較

4.1 混合Logit模型

(3)

(4)

這一指標(biāo)越小說明得到的參數(shù)估計(jì)值與參數(shù)真值越接近，表明抽樣方法越好.

4.2 參數(shù)估計(jì)結(jié)果

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

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

圖4 一維參數(shù)估計(jì)結(jié)果比較(質(zhì)數(shù)：2)

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

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

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

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

圖5 二維參數(shù)估計(jì)結(jié)果比較(質(zhì)數(shù)：2和3)

圖6 三維參數(shù)估計(jì)結(jié)果比較(質(zhì)數(shù)：2,3和5)

圖7 三維參數(shù)估計(jì)結(jié)果比較(質(zhì)數(shù)：43,47和53)

圖8 三維參數(shù)估計(jì)結(jié)果比較(質(zhì)數(shù)：83,89和97)

4.3 概率計(jì)算結(jié)果

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

表3 不同抽樣方法及抽樣次數(shù)下的模擬概率統(tǒng)計(jì)量

5 結(jié) 束 語

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

[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- )：女，碩士生，主要研究領(lǐng)域?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理、離散選擇建模