ผู้ใช้:Pathpot/ทดลองเขียน
- วิธีครอส-เอนโทรปี(อังกฤษ: Cross-Entropy Method) เป็นขั้นตอนวิธีที่ใช้หลักการของ Monte Carlo เพื่อที่จะแก้ปัญหา ถูกนำเสนอโดย R.Y. Rubinstein[1][2] ซึ่งประเภทของปัญหาที่สามารถใช้วิธีครอส-เอนโทรปีได้นั้นจะมีอยู่สองลักษณะ คือ การประมาณค่า หรือ การหาค่าที่ดีที่สุด
โดยวิธีครอส-เอนโทรปีนั้น หากจะอธิบายภาพโดยรวมให้เข้าใจคร่าวๆถึงประเด็น ก็คือการประมาณค่าของค่าคาดหวังของฟังก์ชันของตัวแปรสุ่มฟังก์ชันหนึ่ง โดยที่เราอาจจะไม่รู้ว่าค่าความหนาแน่นของความน่าจะเป็นของฟังก์ชันนั้น อย่างแน่นอน จึงประมาณค่าโดยการประมาณค่าความหนาแน่นของความน่าจะเป็นออกมาเป็น โดยพยายามให้ความหนาแน่นของความน่าจะเป็นให้ใกล้เคียงความเป็นจริงมากที่สุด โดยตัวชี้วัดว่าฟังก์ชันที่เราสร้างขึ้นมา กับฟังก์ชันจริงนั้นห่างกันมากแค่ไหน คือสิ่งที่เรียกว่าครอส-เอนโทรปีนั้นเอง โดยจะอธิบายในรายละเอียดได้ในหัวข้อถัดไป
การใช้วิธี ครอส-เอนโทรปี ในปัญหาการประมาณค่า
แก้แนวคิด
แก้ในการณีที่เราพยายามที่จะใช้วิธีครอส-เอนโทรปีเพื่อประมาณค่านั้น สามารถแปลงปัญหาเป็นสมการคณิตศาสตร์ของการประมาณหาค่าคาดหวังง่ายๆได้ดังสมการที่ (1)
- (1)
เมื่อ H คือฟังก์ชันที่เราต้องการประมาณค่า เรียกได้อีกอย่างหนึ่งว่า ฟังก์ชันของประสิทธิภาพของตัวอย่างสุ่ม
และ f คือฟังก์ชันของความหนาแน่นของความน่าจะเป็นของตัวแปรสุ่ม X
ซึ่งสำหรับวิธีการประมาณค่า ในสมการที่ 1 นั้น ในกรณีที่สามารถสุ่มตัวอย่างสุ่มด้วยความหนาแน่นของความน่าจะเป็น ได้ยาก จะทำการสร้างฟังก์ชัน เพื่อที่จะสามารถประมาณค่าได้ง่ายขึ้นตามสมการที่ 2
- (2)
- (2)
โดยที่กำหนดให้
- เมื่อ
เนื่องจาก g เป็นความหนาแน่นของความน่าจะเป็นที่เราเป็นคนสร้างขึ้น ทำให้การสุ่มตัวอย่างเป็นไปได้ง่ายกว่า f ดังนั้น เราจึงสามารถสุ่มตัวอย่างสุ่ม ตามความหนาแน่นของความน่าจะเป็นของ g(x) ได้ง่ายกว่า ทำให้ประมาณค่าของ l ด้วยตัวประมาณค่าที่ไม่ลำเอียงได้ง่ายขึ้นตามสมการที่ (3)
- (3)
จากปัญหาการประมาณค่า ก็จะเหลือแค่ปัญหาว่าจะสร้างความหนาแน่นของความน่าจะเป็น g ที่ดีที่สุดได้อย่างไรซึ่งค่า g ที่ดีที่สุดในอุดมคตินั้นนิยามด้วย
แต่สิ่งที่เกิดขึ้นก็คือ เราสามารถหาค่า g*(x) ได้ยาก สำหรับวิธีครอส-เอนโทรปีนี้แทนที่จะมุ่งไปที่การหาค่าของ g*(x) จะพยายามหาค่าของ g ที่ทำให้ความแตกต่างระหว่าง g และ g* น้อยที่สุด ซึ่งความแตกต่างนั้นเองที่เรียกว่าครอส-เอนโทรปีตามที่เกริ่นไว้ในช่วงต้น ซึ่งครอส-เอนโทรปีของความหนาแน่นของความน่าจะเป็นของสองฟังก์ชันนั้น นิยามได้ดังสมการที่ (4)
- (4)
- (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 ที่ดีที่สุดจะทำให้ มีค่ามากที่สุดนั่นเอง ซึ่งการแก้ปัญหานี้ก็สามารถหาได้ตามสมการที่ (5)
- (5)
ซึ่งจากสมการที่ (5) R. Y. Rubinstein ได้นำเสนอวิธีสำหรับแก้ปัญหานี้ไว้แล้ว[3]
ในปัญหาเฉพาะที่ชื่อว่าปัญหาการหาความน่าจะเป็นของเหตุการณ์ที่พบเจอได้ยาก(rare event probability) ซึ่งเป็นปัญหาที่ประยุกต์ด้วยวิธีครอส-เอนโทรปีกันอย่างแพร่หลาย โดยเป็นกรณีเฉพาะที่ฟังก์ชัน H เป็นฟังก์ชันตัวชี้ของฟังก์ชัน วัดที่ระดับ ตามสมการ ซึ่งในการประมาณค่าของ l ด้วยวิธีเดิมเพื่อหาความน่าจะเป็นที่ นั้นจะยากโดยดูได้จากสมการที่ (5) คือค่าของ ส่วนมากจะมีค่าเป็น 0 ไปมากพอสมควรจะไม่สามารถประมาณหาค่าที่แม่นยำได้ วิธีการแก้ไขคือต้องทำวิธีการ ครอส-เอนโทรปีหลายๆรอบ หลายๆชั้น โดยจะปรับค่าพารามิเตอร์ v และระดับปัจจุบันให้เข้าใกล้ v* และ ไปเรื่อยๆจนถึงเงื่อนไขยุติที่พอใจ สามารถเขียนขั้นตอนวิธีตามที่ได้อธิบายมาเป็นรหัสเทียมได้ดังนี้
รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อประมาณความน่าจะเป็นสำหรับเหตุการณ์ที่พบเจอได้ยาก
แก้1 และ 2 3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม ตามความหนาแน่นของความน่าจะเป็น 8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 10 เรียงลำดับจากน้อยไปหามาก(S) 11 12 = ค่าต่ำสุด( , ) 13 คำนวณ จากสมการ (5) ด้วย และ 14 ระหว่างที่ 15 16 สุ่มตัวอย่างสุ่ม ตามความหนาแน่นของความน่าจะเป็น 17 คำนวณ l จากสมการ (3) ด้วย 18 คืนค่า l
จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า ให้เหมาะสมกับความต้องการ ซึ่งโดยปกติ จะมีค่าอยู่ระหว่าง 0.01 และ 0.1 และค่าของ จะน้อยว่า มากๆ เช่น ในขณะที่ และขั้นตอนวิธีนี้จะรับประกันว่าสามารถทำงานจนจบได้แน่นอนหากค่าของ มีค่าเล็กมากพอ
การใช้วิธี ครอส-เอนโทรปี ในปัญหาการหาค่าที่เหมาะสมที่สุด
แก้แนวคิด
แก้ให้ เป็นเซตของสถานะ และ S เป็นฟังก์ชันจริงซึ่ง S(x) จะให้ค่าความเหมาะสมของ x โดยที่ x เป็นสมาชิกของ โดยค่า x ที่เหมาะสมที่สุดคือ x* ซึ่งจะทำให้ค่าของ S(x*) มีค่าสูงที่สุด สามารถเขียนเป็นปัญหาในรูปของสมการทางคณิตศาสตร์ได้ดังสมการที่ (6)
- (6)
หาพิจารณาปัญหานี้เทียบกับปัญหาการประมาณค่าของ เมื่อ X เป็นตัวแปรสุ่มที่มีความหนาแน่นของความน่าจะเป็น และให้ เป็นค่าระดับชั้น จะสังเกตว่าถ้าค่า มีค่าใกล้เคียงกับ (ค่าสูงสุดของ S) แล้ว จะทำให้ค่าของ เป็นความน่าจะเป็นของเหตุการณ๊ที่พบเจอได้ยาก ซึ่งปัญหานี้เราจะต้องการสร้างตัวอย่างสุ่มจำนวนหนึ่งที่มีค่าใกล้เคียงกับ x* โดยเป็นเรื่องที่ดีที่วิธีครอส-เอนโทรปี สามารถทำเรื่องนี้ได้
หากเปรียบเทียบความแตกต่างของปัญหาระหว่างการหาค่าที่เหมาะสมที่สุด กับ การประมาณค่า ความแตกต่างก็คือการหาค่าที่เหมาะสมที่สุด เราจะไม่รู้ค่าของระดับชั้น ล่วงหน้าเหมือนในการประมาณค่า แต่อย่างไรก็ตามขั้นตอนวิธีในการแก้ปัญหาก็ไ่ม่ค่อยแตกต่างกันมากคือเราจะสร้างลำดับของ และ ไปเรื่อยๆ โดยจะพยายามให้ทั้งสองค่าเข้าใกล้ และ ตามลำดับ ซึ่งค่าของ จะสอดคล้องกับค่าของ ที่ต้องการหาเช่นกัน
รหัสเทียมสำหรับวิธีครอส-เอนโทรปีเพื่อใช้ในปัญหาการหาค่าที่เหมาะสมที่สุด
แก้1 และ 2 3 t = 0 /*ตัวนับจำนวนรอบ*/ 4 5 ทำ 6 t = t + 1 7 สุ่มตัวอย่างสุ่ม ตามความหนาแน่นของความน่าจะเป็น 8 สำหรับทุก i ตั้งแต่ 1 ถึง N 9 10 เรียงลำดับจากน้อยไปหามาก(S) 11 12 = ค่าต่ำสุด( , ) 13 คำนวณ ที่ทำให้ \frac{I_{S(X_k) \ge \widehat{\gamma}_t}ln(f(X_k;v))}{N} สูงที่สุด 14 ระหว่างที่ ยังไม่ถึงเงื่อนไขยุติ 15 16 คืนค่า
จะเห็นว่าหากต้องการใช้ขั้นตอนวิธีนี้ต้องทำการปรับค่า และเงื่อนไขยุติให้เหมาะสม การทำครอส-เอนโทรปีสำหรับหาค่าที่เหมาะสมที่สุดนั้น ประกอบด้วยสองขั้นตอนสำคัญ
- สร้าง : สร้างสถานะที่ถูกสุ่มตัวอย่างมาจะสถานะที่เป็นไปได้ โดยเป็นไปตามความหนาแน่นของความน่าจะเป็นที่กำหนด
- ปรับแก้ไข : ปรับพารามิเตอร์สำหรับการกระจายโดยให้ ครอส-เอนโทรปี น้อยที่สุด
อ้างอิง
แก้- ↑ R. Y. Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and Computing in Applied Probability, 2:127–190, 1999.
- ↑ 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.
- ↑ R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo Method. John Wiley & Sons, New York, second edition, 2007.