วิธีการครอส-เอนโทรปี

วิธีครอส-เอนโทรปี (อังกฤษ: Cross-Entropy Method) เป็นขั้นตอนวิธีที่ใช้หลักการของ Monte Carlo เพื่อที่จะแก้ปัญหา ถูกนำเสนอโดย R.Y. Rubinstein ซึ่งประเภทของปัญหาที่สามารถใช้วิธีครอส-เอนโทรปีได้นั้นจะมีอยู่สองลักษณะ คือ การประมาณค่า หรือ การหาค่าที่ดีที่สุด โดยวิธีการนี้ถูกประยุกต์ใช้ในปัญหาเชิงวิศวกรรม และวิทยาศาสตร์มากมาย

ภาพรวมของวิธีครอส-เอนโทรปี

วิธีการครอส-เอนโทรปีนั้นถูกพัฒนาขึ้นโดย Reuven Y. Rubinstein ซึ่งเป็นนักวิทยาศาสตร์ชาวอิสราเอลที่ให้ความสนใจทางด้านการพัฒนาขั้นตอนวิธีเชิงสถิติมากมาย เขียนหนังสือหกเล่มและตีพิมพ์ผลงานกว่าร้อยผลงาน ซึ่งแน่นอนว่าวิธีการครอส-เอนโทรปีเป็นหนึ่งในขั้นตอนวิธีเชิงสถิติเหล่านั้นเช่นกัน โดยเป็นขั้นตอนวิธีที่มีประสิทธิภาพตัวหนึ่งที่ใช้สำหรับปัญหาการประมาณค่าความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก (rare-event probability) ปัญหาการหาค่าที่เหมาะสมที่สุดเชิงการจัด (combinatorial optimization)

วิธีการครอสเอนโทรปีนั้นได้ชื่อมาจาก "" ซึ่งเป็นการหาระยะห่างระหว่าง "ข้อมูล" ที่ใช้กันแพร่หลายในทางวิทยาศาสตร์และวิศวกรรมกว่าศตวรรษ

วิธีการครอส-เอนโทรปีนั้นถูกนำไปใช้ในปัญหาการหาค่าที่เหมาะสมที่สุดเชิงการจัดมากมาย เช่น ปัญหาการตัดที่มากที่สุด (Maximum Cut Problem) ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem) ปัญหาการหากราฟย่อยบริบูรณ์ที่มีขนาดใหญ่ที่สุดในกราฟ (Clique Problem) และปัญหาต่างๆอีกมากมาย และจุดเด่นพิเศษอีกอย่างหนึ่งสำหรับวิธีการครอส-เอนโทรปีคือ สามารถหาค่าที่เหมาะสมที่สุดสำหรับปัญหาที่มีค่ารบกวน (noisy problem) ได้ เพราะลักษณะขั้นตอนวิธีแก้ปัญหาที่เป็นเชิงสถิตินั่นเอง

วิธีการครอสเอนโทรปีนั้นสามารถแตกขั้นตอนที่สำคัญออกได้เป็นสองส่วน คือ

1. ขั้นสุ่มตัวอย่าง (Generate) จะสร้างตัวอย่างจากความหนาแน่นของความน่าจะเป็นที่ได้มาจากการคำนวณในขั้นตอนวิธี
2. ขั้นปรับปรุง (Update) ปรับพารามิเตอร์บางอย่าง เพื่อให้การสุ่มครั้งต่อไป ได้ตัวอย่างที่ดีขึ้นไปอีก
   

ประเด็นสำคัญสำหรับวิธีการครอส-เอนโทรปี คือ จะนิยามขั้นตอนในเชิงคณิตศาสตร์อย่างไรให้สามารถปรับปรุงค่าพารามิเตอร์เพื่อให้เข้าใกล้ค่าที่เหมาะสมได้อย่างรวดเร็ว

ในด้านของการประมาณค่าความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยากนั้น วิธีการครอส-เอนโทรปีจะใช้ร่วมกับกลวิธีการสุ่มตัวอย่างสำคัญ (Importance Sampling Technique) วิธีการครอส-เอนโทรปีจะปรับค่าของพารามิเตอร์ซ้ำๆ หลายๆรอบเพื่อให้เข้าใกล้ค่าที่เหมาะสมที่สุด ปัญหาที่ประยุกต์วิธีนี้ตัวอย่างเช่นปัญหาการวัดประสิทธิภาพในระบบเครือข่ายทางคมนาคม หรือ ระบบที่ต้องการความน่าเชื่อถือ

การใช้วิธี ครอส-เอนโทรปี ในปัญหาการประมาณค่า

แนวคิด

ในกรณีที่เราพยายามที่จะใช้วิธีครอส-เอนโทรปีเพื่อประมาณค่านั้น สามารถแปลงปัญหาเป็นสมการคณิตศาสตร์ของการประมาณหาง่ายๆได้ดังสมการที่ (1)

${\displaystyle \ell =\mathbb {E} _{f}[H(X)]=\int H(x)f(x)\,dx}$ (1)

เมื่อ H คือฟังก์ชันที่เราต้องการประมาณค่า เรียกได้อีกอย่างหนึ่งว่า ฟังก์ชันของประสิทธิภาพของตัวอย่างสุ่ม
และ f คือฟังก์ชันของความหนาแน่นของความน่าจะเป็นของตัวแปรสุ่ม X

ซึ่งสำหรับวิธีการประมาณค่า ${\displaystyle l}$ ในสมการที่ 1 นั้น ในกรณีที่สามารถสุ่มตัวอย่างสุ่มด้วยความหนาแน่นของความน่าจะเป็น ${\displaystyle f(x)}$ ได้ยาก จะทำการสร้างฟังก์ชัน ${\displaystyle f(x)}$ เพื่อที่จะสามารถประมาณค่าได้ง่ายขึ้นตามสมการที่ 2

${\displaystyle \ell =\int H(x){\frac {f(x)}{g(x)}}g(x)\,dx=\mathbb {E} _{g}[H(x){\frac {f(x)}{g(x)}}]}$ (2)

โดยที่กำหนดให้

${\displaystyle g(x)=0\,}$ เมื่อ ${\displaystyle H(x)f(x)=0\,}$

เนื่องจาก g เป็นความหนาแน่นของความน่าจะเป็นที่เราเป็นคนสร้างขึ้น ทำให้การสุ่มตัวอย่างเป็นไปได้ง่ายกว่า f ดังนั้น เราจึงสามารถสุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N}}$ ตามความหนาแน่นของความน่าจะเป็นของ g(x) ได้ง่ายกว่า ทำให้ประมาณค่าของ l ด้วยตัวประมาณค่าที่ไม่ลำเอียงได้ง่ายขึ้นตามสมการที่ (3)

${\displaystyle {\widehat {\ell }}={\frac {1}{N}}\sum _{k=1}^{N}H(X_{k}){\frac {f(X_{k})}{g(X_{k})}}}$ (3)

จากปัญหาการประมาณค่า ก็จะเหลือแค่ปัญหาว่าจะสร้างความหนาแน่นของความน่าจะเป็น g ที่ดีที่สุดได้อย่างไรซึ่งค่า g ที่ดีที่สุดในอุดมคตินั้นนิยามด้วย

${\displaystyle g^{*}(x)\alpha |H(x)|f(x)\,}$

แต่สิ่งที่เกิดขึ้นก็คือ เราสามารถหาค่า g*(x) ได้ยาก สำหรับวิธีครอส-เอนโทรปีนี้แทนที่จะมุ่งไปที่การหาค่าของ g*(x) จะพยายามหาค่าของ g ที่ทำให้ความแตกต่างระหว่าง g และ g* น้อยที่สุด ซึ่งความแตกต่างนั้นเองที่เรียกว่าครอส-เอนโทรปีตามที่เกริ่นไว้ในช่วงต้น ซึ่งครอส-เอนโทรปีของความหนาแน่นของความน่าจะเป็นของสองฟังก์ชันนั้น นิยามได้ดังสมการที่ (4)

${\displaystyle D(f,g)=\mathbb {E} _{f}[ln{\frac {f(X)}{g(X)}}]=\int f(x)ln(f(x))dx-\int f(x)ln(g(x))dx}$ (4)

หลังจากที่ได้รู้หลักการคร่าวๆของวิธีการครอส-เอนโทรปีเพื่อการประมาณค่าในทางทฤษฎีไปแล้วว่าเป็นไปในลักษณะอย่างไร หากพิจารณาในทางปฏิบัติแล้วนั้นฟังก์ชัน f นอกจากจะแปรไปตามตัวแปรต้น x แล้ว ยังถูกควบคุมโดยพารามิเตอร์ u บางอย่าง ซึ่งสามารถเขียนฟังก์ชัน f ได้เป็น f(x; u) ซึ่งคงเดาได้ไม่ยากว่าบางกรณีนั้น พารามิเตอร์ u นี้หาได้ยากมาก เราจึงพยายามหาค่าของ g ที่ทำให้มี v ที่ทำให้ g(x) = f(x; v) และ v ทำให้ความแตกต่างของ f(x; v) และ f(x; u) น้อยๆ ซึ่งความแตกต่างนี้วัดโดยครอส-เอนโทรปีตามสมการที่ 4 นั่นเอง ก็จะทำให้ปัญหาเล็กลงอีกขั้นหนึ่งคือเป็นปัญหาที่จะพยายามหาค่าของ v ที่ดีที่สุดเท่านั้น ซึ่งนิยาม v ในอุดมคติว่า v* ลองไปแทนค่าของ f(x; v) และ f(x; u) ลงในสมการที่ (4) แล้วจัดรูปสักเล็กน้อยก็จะรู้ว่า v ที่ดีที่สุดจะทำให้ ${\displaystyle \int H(x)f(x;u)ln(f(x;v))dx\,}$ มีค่ามากที่สุดนั่นเอง ซึ่งการแก้ปัญหานี้ก็สามารถหาได้ตามสมการที่ (5)

${\displaystyle max_{v}({\frac {1}{N}}\sum _{k=1}^{N}H(X_{k}){\frac {f(X_{k};u)}{f(X_{k};w)}}ln(f(X_{k};v))\,}$ (5)

ซึ่งจากสมการที่ (5) R. Y. Rubinstein ได้นำเสนอวิธีสำหรับแก้ปัญหานี้ไว้แล้ว
ในปัญหาเฉพาะที่ชื่อว่าปัญหาการหาความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก(rare event probability) ซึ่งเป็นปัญหาที่ประยุกต์ด้วยวิธีครอส-เอนโทรปีกันอย่างแพร่หลาย โดยเป็นกรณีเฉพาะที่ฟังก์ชัน H เป็นฟังก์ชันตัวชี้ของฟังก์ชัน ${\displaystyle S(x)}$ วัดที่ระดับ ${\displaystyle \gamma }$ ตามสมการ ${\displaystyle H(x)=I_{S(X)\geq \gamma }}$ ซึ่งในการประมาณค่าของ ${\displaystyle \ell }$ ด้วยวิธีเดิมเพื่อหาความน่าจะเป็นที่ ${\displaystyle S(x)\geq \gamma }$ นั้นจะยากโดยดูได้จากสมการที่ (5) คือค่าของ ${\displaystyle H(X_{k})}$ ส่วนมากจะมีค่าเป็น 0 ไปมากพอสมควรจะไม่สามารถประมาณหาค่าที่แม่นยำได้ วิธีการแก้ไขคือต้องทำวิธีการ ครอส-เอนโทรปีหลายๆรอบ หลายๆชั้น โดยจะปรับค่าพารามิเตอร์ v และระดับปัจจุบันให้เข้าใกล้ v* และ ${\displaystyle \gamma }$ ไปเรื่อยๆจนถึงเงื่อนไขยุติที่พอใจ สามารถเขียนขั้นตอนวิธีตามที่ได้อธิบายมาเป็นรหัสเทียมได้ดังนี้

รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อประมาณความน่าจะเป็นสำหรับเหตุการณ์ที่พบเจอได้ยาก

 1 ${\displaystyle {\widehat {v}}_{0}=u}$ และ 2 ${\displaystyle N^{e}=\lceil \rho \,N\rceil }$ 3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N}\,}$ ตามความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-:{\widehat {v}}_{t-1})\,}$ 8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 ${\displaystyle S_{(i)}=S(X_{i})\,}$ 10 เรียงลำดับจากน้อยไปหามาก(S) 11 ${\displaystyle {\widehat {\gamma }}_{t}=S_{(N-N^{e}+1)}\,}$ 12 ${\displaystyle {\widehat {\gamma }}_{t}\,}$ = ค่าต่ำสุด(${\displaystyle \gamma \,}$,${\displaystyle {\widehat {\gamma }}_{t}}$) 13 คำนวณ ${\displaystyle {\widehat {v}}_{t}}$ จากสมการ (5) ด้วย ${\displaystyle X_{1},...,X_{N}}$ และ ${\displaystyle w={\widehat {v}}_{t-1}}$ 14 ระหว่างที่ ${\displaystyle {\widehat {\gamma }}_{t}<\gamma }$ 15 16 สุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N_{1}}\,}$ ตามความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-:{\widehat {v}}_{t})}$ 17 คำนวณ ${\displaystyle \ell }$ จากสมการ (3) ด้วย ${\displaystyle X_{1},...,X_{N_{1}}\,}$ 18 คืนค่า ${\displaystyle \ell }$ 

จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า ${\displaystyle {\widehat {v}}_{0},N,\rho }$ ให้เหมาะสมกับความต้องการ ซึ่งโดยปกติ ${\displaystyle \rho }$ จะมีค่าอยู่ระหว่าง 0.01 และ 0.1 และค่าของ ${\displaystyle N}$ จะน้อยว่า ${\displaystyle N_{1}}$ มากๆ เช่น ${\displaystyle N=10000}$ ในขณะที่ ${\displaystyle N_{1}=100000}$ และขั้นตอนวิธีนี้จะรับประกันว่าสามารถทำงานจนจบได้แน่นอนหากค่าของ ${\displaystyle \rho }$ มีค่าเล็กมากพอ

การใช้วิธี ครอส-เอนโทรปี ในปัญหาการหาค่าที่เหมาะสมที่สุด

แนวคิด

ให้ ${\displaystyle \chi }$ เป็นเซตของสถานะ และ S เป็นฟังก์ชันจริงซึ่ง S(x) จะให้ค่าความเหมาะสมของ x โดยที่ x เป็นสมาชิกของ ${\displaystyle \chi }$ โดยค่า x ที่เหมาะสมที่สุดคือ x* ซึ่งจะทำให้ค่าของ S(x*) มีค่าสูงที่สุด สามารถเขียนเป็นปัญหาในรูปของสมการทางคณิตศาสตร์ได้ดังสมการที่ (6)

${\displaystyle S(x^{*})=\gamma ^{*}=max_{x}S(x)\,}$ (6)

หาพิจารณาปัญหานี้เทียบกับปัญหาการประมาณค่าของ ${\displaystyle H(x)=I_{S(X)\geq \gamma }}$ เมื่อ X เป็นตัวแปรสุ่มที่มีความหนาแน่นของความน่าจะเป็น ${\displaystyle f(x;u)}$ และให้ ${\displaystyle \gamma }$ เป็นค่าระดับชั้น จะสังเกตว่าถ้าค่า ${\displaystyle \gamma }$ มีค่าใกล้เคียงกับ ${\displaystyle \gamma ^{*}}$ (ค่าสูงสุดของ S) แล้ว จะทำให้ค่าของ ${\displaystyle H(x)=I_{S(X)\geq \gamma }}$ เป็นความน่าจะเป็นของเหตุการณ๊ที่พบเจอได้ยาก ซึ่งปัญหานี้เราจะต้องการสร้างตัวอย่างสุ่มจำนวนหนึ่งที่มีค่าใกล้เคียงกับ x* โดยเป็นเรื่องที่ดีที่วิธีครอส-เอนโทรปี สามารถทำเรื่องนี้ได้

หากเปรียบเทียบความแตกต่างของปัญหาระหว่างการหาค่าที่เหมาะสมที่สุด กับ การประมาณค่า ความแตกต่างก็คือการหาค่าที่เหมาะสมที่สุด เราจะไม่รู้ค่าของระดับชั้น ${\displaystyle \gamma =\gamma ^{*}}$ ล่วงหน้าเหมือนในการประมาณค่า แต่อย่างไรก็ตามขั้นตอนวิธีในการแก้ปัญหาก็ไ่ม่ค่อยแตกต่างกันมากคือเราจะสร้างลำดับของ ${\displaystyle \gamma _{t}}$ และ ${\displaystyle {\widehat {v}}_{t}}$ ไปเรื่อยๆ โดยจะพยายามให้ทั้งสองค่าเข้าใกล้ ${\displaystyle \gamma ^{*}}$ และ ${\displaystyle v^{*}}$ ตามลำดับ ซึ่งค่าของ ${\displaystyle v^{*}}$ จะสอดคล้องกับค่าของ ${\displaystyle x^{*}}$ ที่ต้องการหาเช่นกัน

รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อใช้ในปัญหาการหาค่าที่เหมาะสมที่สุด

 1 ${\displaystyle {\widehat {v}}_{0}=u}$ และ 2 ${\displaystyle N^{e}=\lceil \rho \,N\rceil }$ 3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม ${\displaystyle X_{1},...,X_{N}\,}$ ตามความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-:{\widehat {v}}_{t-1})\,}$ 8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 ${\displaystyle S_{(i)}=S(X_{i})\,}$ 10 เรียงลำดับจากน้อยไปหามาก(S) 11 ${\displaystyle {\widehat {\gamma }}_{t}=S_{(N-N^{e}+1)}\,}$ 12 ${\displaystyle {\widehat {\gamma }}_{t}\,}$ = ค่าต่ำสุด(${\displaystyle \gamma \,}$,${\displaystyle {\widehat {\gamma }}_{t}}$) 13 คำนวณ ${\displaystyle v={\widehat {v}}_{t}\,}$ ที่ทำให้ ${\displaystyle {\frac {I_{S(X_{k})\geq {\widehat {\gamma }}_{t}}ln(f(X_{k};v))}{N}}}$ สูงที่สุด 14 ระหว่างที่ ยังไม่ถึงเงื่อนไขยุติ 15 16 คืนค่า ${\displaystyle {\widehat {v}}_{t}\,}$ 

จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า ${\displaystyle {\widehat {v}}_{0},N,\rho }$ และเงื่อนไขยุติให้เหมาะสม

ตัวอย่างปัญหาที่สามารถประยุกต์ใช้วิธีการครอสเอนโทรปีได้

ปัญหาการหาเส้นทางเดินของพนักงานขาย (Traveling Salesman Problem)

นิยามปัญหา

ปัญหาการเดินของพนักงานขายคือปัญหาที่มีผู้ที่ให้ความสนใจพอสมควรในวงการคอมพิวเตอร์ ปัญหาจะกำหนดด้วยกราฟเชื่อมโยงประกอบด้วยปม n ชื่อว่า 1,2,...,n ปมซึ่งเชื่อมกันด้วยเส้นเชื่อมที่มีน้ำหนัก เส้นเชื่อมจากปม i ไปยังปม j จะมีน้ำหนัก ${\displaystyle c_{ij}>0\,}$ให้ทำการหาเส้นทางซึ่งเป็นวงที่สั้นที่สุดซึ่งผ่านทุกปมและกลับมาที่จุดเดิม

แนวทางการแก้ปัญหา

โดยไม่เสียนัยสำคัญทั่วไป ให้กราฟเป็นกราฟบริบูรณ์ ซึ่งจะมีบางเส้นเชื่อมที่มีน้ำหนักเป็น +∞ ให้ ${\displaystyle \chi \,}$ เป็นเซตของวงจรที่ผ่านทุกปม และให้ ${\displaystyle S(x)\,}$ เป็นความยาวของวงจร ${\displaystyle x\in \chi \,}$ ปมละหนึ่งครั้งตามเงื่อนไข เราสามารถแทนแต่ละวงจรใน Χ ได้ด้วยการเรียงสับเปลี่ยน(permutation) ของปม 1,2,...,n ซึ่งจริงๆแล้วเราสามารถให้วงจร ${\displaystyle x=x_{1},x_{2},x_{3},...,x_{n}\,}$ โดยที่ ${\displaystyle x_{1}=1}$ ได้โดยไม่เสียนัยสำคัญทั่วไป เราสามารถแปลงปัญหาทางเดินของพนักงานขายได้เป็นสมการที่ (7)

${\displaystyle min_{x}(S(x))=min_{x}(\sum _{i=1}^{n-1}c_{x_{i},x_{i+1}}+c_{x_{n},1})}$ (7)

สังเกตว่าขนาดของสมาชิกใน ${\displaystyle \chi \,}$ มีขนาดใหญ่มาก ${\displaystyle |\chi |=(n-1)!\,}$

จากสมการที่ (7) จะเห็นว่าปัญหาเป็นลักษณะของการหาค่าที่เหมาะสมที่สุดซึ่งสามารถแก้ไขได้ด้วยวิธีการครอส-เอนโทรปี แต่แทนที่จะเป็นลักษณะของการหาค่าที่มากที่สุดจะต้องเปลี่ยนเป็นปัญหาการหาค่าที่น้อยที่สุด โดยหากจะแก้ปัญหาด้วยวิธีการครอส-เอนโทรปีนั้นเราจะต้องกำหนด

1. จะสร้างเส้นทางแบบสุ่มอย่างไร?
2. จะทำการปรับปรุงพารามิเตอร์ในแต่ละรอบการทำงานอย่างไร?
   

ก่อนที่จะหาวิธีการสร้างและปรับปรุงดังกล่าว จะขอนิยามเซตใหม่ขึ้นมาก่อน ให้

${\displaystyle {\widehat {\chi }}={(x_{1},x_{2},...,x_{n}):x_{1}=1,x_{i}\in {1,2,...,n},i=2,3,...,n}}$

จะเห็นว่าการหาเส้นทางเดินตามเงื่อนไขบนเซตของเส้นทางเดินใน ${\displaystyle {\widehat {\chi }}\,}$ จะสมมูลกับปัญหาเส้นทางเดินของพนักงานขายเดิม และเพิ่มนิยาม ${\displaystyle {\widehat {S}}(x)=S(x)}$ เมื่อ ${\displaystyle x\in {\widehat {\chi }}}$ มิฉะนั้น ${\displaystyle {\widehat {S}}(x)=\infty }$
ก็จะสามารถเปลี่ยนปัญหาทางเดินของพนักงานขายได้เป็นหาค่าที่ต่ำที่สุดของ ${\displaystyle {{\widehat {S}}(x)}\,}$ บน ${\displaystyle x\in {\widehat {\chi }}\,}$

วิธีง่ายๆวิธีหนึ่งที่จะสร้างทางเดินสุ่ม ${\displaystyle X=(X_{1},X_{2},...,X_{n})\in {\widehat {\chi }}}$ คือการสร้าง(Markov Chain) ของกราฟ G เริ่มต้นที่ปม 1 และหยุดหลังจากขั้นที่ n ให้ ${\displaystyle P=(p_{ij})}$ คือเมตริกซ์ nxn เพื่อเปลี่ยนสถานะไปหนึ่งขั้นสำหรับลูกโซ่มาร์คอฟนี้ หรือจะพูดให้เข้าใจง่ายขึ้นเป็นภาษาทั่วไปก็คือเมตริกซ์ P จะเป็นส่วนที่ใช้เก็บเส้นทางเดินนั่นเอง กำหนดให้ในสมาชิกตามแนวเส้นทแยงมุมของ P เป็น 0 และสมาชิกอื่นๆใน P เป็นจำนวนจริงบวก ความหนาแน่นของความน่าจะเป็น ${\displaystyle f(-;P)}$ ของ ${\displaystyle X}$ ที่ถูกจำกัดด้วยพารามิเตอร์เป็นเมตริกส์ P นิยามโดย

${\displaystyle lnf(x;P)=\sum _{r=1}^{n}\sum _{i,j}I_{x\in {\widehat {\chi }}_{ij}(r)}ln(p_{ij})}$(8)
เมื่อ ${\displaystyle {\widehat {\chi }}_{ij}(r)}$ เป็นเซตของเส้นทางทั้งหมดที่ "จำนวนครั้ง" ที่ต้องเดินระหว่างปม i ไปปม j เป็น r ครั้ง

หลังจากนี้จะเริ่มเป็นการคำนวณเชิงคณิตศาสตร์ที่ซับซ้อนหากผู้สนใจสามารถไปศึกษาเพิ่มเติมได้ตามแหล่งอ้างอิง

หากจะสรุปเฉพาะใจความสำคัญให้เข้าใจอย่างสั้นๆสามารถสรุปได้ว่าในขณะนี้เราจะแทนการเปลี่ยนสถานะจากปมปัจจุบันไปยังปมใดๆไ้ด้ด้วยเมตริกซ์ซึ่งก็คือ ${\displaystyle P=(p_{ij})}$ นั่นเอง โดยเมตริกซ์นี้จะได้มาในแต่ละรอบที่ทำการสุ่มตัวอย่างและปรับปรุงพารามิเตอร์ ซึ่งทั้งสองขั้นตอนนี้สามารถทำได้โดย

1. ขั้นสุ่มตัวอย่าง สามารถสุ่มตัวอย่างให้ได้ x ต่างๆได้ตามสมการที่ 8
2. ขั้นปรับปรุง ปรับปรุงพารามิเตอร์ ${\displaystyle p_{ij}}$ ของสมการที่ 8 ได้ด้วยตัวประมาณค่าของ ${\displaystyle p_{ij}}$ ตามสมการที่ (9)

${\displaystyle {\widehat {p}}_{ij}={\frac {\sum _{k=1}^{N}I_{{\widehat {S}}(X_{k})\leq \gamma }\sum _{r=1}^{n}I_{X_{k}\in {\widehat {\chi }}_{ij}(r)}}{\sum _{k=1}^{N}I_{{\widehat {S}}(X_{k})\leq \gamma }\sum _{r=1}^{n}I_{X_{k}\in {\widehat {\chi }}_{i}(r)}}}}$ (9)

ซึ่งรายละเอียดการได้มาซึ่งสมการที่ 10 นั้นผู้สนใจสามารถไปค้นคว้าได้ตามแหล่งอ้่างอิงที่ได้ระบุไว้ข้างต้น

เมื่อเราสามารถนิยามว่าจะสุ่มตัวอย่างและปรับปรุงได้อย่างไรแล้วนั้น เราก็จะสามารถสร้างขั้นตอนวิธีเพื่อที่จะแก้ปัญหานี้ได้ดังรหัสเทียมด้านล่าง

รหัสเทียมสำหรับปัญหา

 1 ตั้งค่า ${\displaystyle P^{(1)}=P\,}$ และ ${\displaystyle X_{1}=1\,}$ 2 t = 0 /*ตัวนับจำนวนรอบ*/ 3 ทำ 4 t = t + 1 5 ตั้งค่าในในหลักที่ ${\displaystyle X_{t}\,}$ ของ ${\displaystyle P^{(t)}}$ เป็น 0 6 ทำการทำค่าในแต่ละแถวของ ${\displaystyle P^{(t)}\,}$ ให้เป็นมาตรฐาน(normalize) //เฉลี่ยค่าในแต่ละแถวให้รวมกันได้ 1 7 ใช้สมการที่ (8) สร้าง ${\displaystyle X_{t+1}\,}$ ด้วยพารามิเตอร์ ${\displaystyle P_{t}\,}$ 8 ทำการปรับปรุงค่าให้ได้ ${\displaystyle P^{(t+1)}\,}$ ในแต่ละแถว i และหลักที่ j ตามสมการที่ (9) 9 ระหว่างที่ t < n-1 // ถ้ายังสร้างลำดับของทางเดินไม่ครบทุกจุด 10 คืนค่า ${\displaystyle P^{(t)}\,}$ 

ดูเพิ่ม

โปรแกรมภาษา C++ ของ Shark Machine Learning Library 2013-11-18 ที่ เวย์แบ็กแมชชีน

อ้างอิง

1. R. Y. Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and Computing in Applied Probability, 2:127–190, 1999.
2. R. Y. Rubinstein. Combinatorial optimization, cross-entropy, ants and rare events. In S. Uryasev and P. M. Pardalos, editors, Stochastic Optimization: Algorithms and Applications, pages 304–358, Dordrecht, 2001. Kluwer.
3. . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2010-09-30. สืบค้นเมื่อ 2011-09-29.
4. R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo Method. John Wiley & Sons, New York, second edition, 2007.
5. Pieter-Tjerk de Boer. A Tutorial on the Cross-Entropy Method, P.25 - 27.