ปัญหา 1. เมทริกซ์ของความน่าจะเป็นการเปลี่ยนแปลงสำหรับห่วงโซ่มาร์คอฟที่ไม่ต่อเนื่องจาก ผมรัฐใน เจ-th ในขั้นตอนเดียว ( ผม, เจ=1, 2). การกระจายความน่าจะเป็นของรัฐใน ช่วงเวลาเริ่มต้น ที=0 ถูกกำหนดโดยเวกเตอร์ =(0.1; 0.9) หา:

1. เมทริกซ์ R2การเปลี่ยนห่วงโซ่จากสถานะ ผมเข้าสู่สถานะ เจสอง
ขั้นตอน;

2. การกระจายความน่าจะเป็นในแต่ละรัฐในขณะนี้ ที=2;

3. ความน่าจะเป็นในขณะนั้น ที=1 สถานะของวงจรจะเป็น A2;

4. การกระจายแบบอยู่กับที่

วิธีการแก้.สำหรับห่วงโซ่มาร์คอฟที่ไม่ต่อเนื่องในกรณีของความเป็นเนื้อเดียวกัน ความสัมพันธ์

โดยที่ P1 คือเมทริกซ์ของความน่าจะเป็นการเปลี่ยนแปลงในขั้นตอนเดียว
Pn - เมทริกซ์ของความน่าจะเป็นการเปลี่ยนแปลงสำหรับ n ขั้นตอน

1. ค้นหาเมทริกซ์การเปลี่ยนแปลง P2 ในสองขั้นตอน

ปล่อยให้การกระจายความน่าจะเป็นบนสถานะเปิด สขั้นตอน -th ถูกกำหนดโดยเวกเตอร์
.
รู้จักเมทริกซ์ พ.นการเปลี่ยนแปลงใน n ขั้นตอน เป็นไปได้ที่จะกำหนดการกระจายความน่าจะเป็นผ่านสถานะบน (เอส+น)ขั้นตอนที่ . (5)

2. ค้นหาการแจกแจงความน่าจะเป็นเหนือสถานะของระบบในขณะนี้ ที=2. ใส่ (5) ส=0 และ น=2. แล้ว .

เราได้รับ .

3. ค้นหาการแจกแจงความน่าจะเป็นเหนือสถานะของระบบในขณะนี้ ที=1.

ใส่ (5) ส=0 และ น=1 แล้ว
คุณจะเห็นได้อย่างไรว่าความน่าจะเป็นในขณะนั้น ที=1 สถานะของวงจรจะเป็น A2, เท่ากับ พี2(1)=0,69.
การกระจายความน่าจะเป็นในสถานะต่างๆ เรียกว่า คงที่ หากไม่เปลี่ยนจากขั้นหนึ่งไปอีกขั้นหนึ่ง นั่นคือ
จากนั้นจากความสัมพันธ์ (5) ที่ น= 1 เราได้รับ

4. ค้นหาการแจกแจงแบบอยู่กับที่ เนื่องจาก =2 เรามี =(p1; p2) มาจดระบบกันเถอะ สมการเชิงเส้น(6) ในรูปแบบพิกัด

เงื่อนไขสุดท้ายเรียกว่าการทำให้เป็นมาตรฐาน ในระบบ (6) สมการหนึ่งจะเป็นผลรวมเชิงเส้นของสมการอื่นเสมอ ดังนั้นจึงสามารถลบได้ ให้เราร่วมกันแก้สมการแรกของระบบและการทำให้เป็นมาตรฐาน เรามี 0.6 หน้า 1=0,3พี 2, นั่นคือ พี 2=2หน้า 1. แล้ว หน้า 1+2หน้า 1=1 หรือ นั่นคือ เพราะเหตุนี้, .
ตอบ:
1) เมทริกซ์การเปลี่ยนแปลงสองขั้นตอนสำหรับห่วงโซ่มาร์คอฟที่กำหนดมีรูปแบบ ;
2) การกระจายความน่าจะเป็นในแต่ละรัฐในขณะนี้ ที=2 เท่ากับ ;
3) ความน่าจะเป็นในขณะนั้น ที=1 สถานะของวงจรจะเป็น A2, เท่ากับ พี2(เสื้อ)=0,69;
4) การกระจายแบบคงที่มีรูปแบบ

กำหนดเมทริกซ์ ความเข้มของการเปลี่ยนผ่านของห่วงโซ่มาร์คอฟที่ต่อเนื่อง เขียนกราฟสถานะที่มีป้ายกำกับซึ่งสอดคล้องกับเมทริกซ์ Λ; วาดระบบ สมการเชิงอนุพันธ์ Kolmogorov สำหรับความน่าจะเป็นของรัฐ ค้นหาการแจกแจงความน่าจะเป็นที่จำกัด วิธีการแก้.ห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันกับ จำนวนจำกัดรัฐ A1, A2,…แต่โดดเด่นด้วยเมทริกซ์ความเข้มของการเปลี่ยนแปลง ,

ที่ไหน - ความรุนแรงของการเปลี่ยนแปลงของห่วงโซ่มาร์คอฟจากรัฐ AIเข้าสู่สถานะ อาจ; ริจ(Δt)- ความน่าจะเป็นการเปลี่ยนแปลง ไอ→อาจต่อช่วงเวลา Δ ที.

สะดวกในการระบุการเปลี่ยนระบบจากสถานะหนึ่งไปอีกสถานะหนึ่งโดยใช้กราฟสถานะที่มีป้ายกำกับ ซึ่งมีการทำเครื่องหมายส่วนโค้งที่สอดคล้องกับความเข้ม λ ไอเจ>0. สร้างกราฟสถานะที่มีป้ายกำกับสำหรับ เมทริกซ์ที่กำหนดความเข้มของการเปลี่ยนแปลง

ให้ เป็นเวกเตอร์ความน่าจะเป็น รเจ (เสื้อ),
เจ=1, 2,…,, ระบบอยู่ในสถานะ แต่เจในขณะนี้ ที.

เห็นได้ชัดว่า 0≤ รเจ (เสื้อ)≤1 และ . จากนั้นตามกฎความแตกต่าง ฟังก์ชันเวกเตอร์ อาร์กิวเมนต์สเกลาร์เราได้รับ . ความน่าจะเป็น รเจ (เสื้อ)ตอบสนองระบบสมการเชิงอนุพันธ์ของ Kolmogorov (SDUK) ซึ่งในรูปแบบเมทริกซ์มีรูปแบบ . (7)

หากในตอนแรกระบบอยู่ในสถานะ อาจดังนั้น SDUK ควรได้รับการแก้ไขภายใต้เงื่อนไขเริ่มต้น
รผม(0)=1, рj(0)=0, j≠i,j=1, 2,…,. (8)
ชุดของ SDUK (7) และเงื่อนไขเริ่มต้น (8) อธิบายห่วงโซ่ Markov ที่เป็นเนื้อเดียวกันโดยเฉพาะด้วย เวลาต่อเนื่องและรัฐจำนวนจำกัด
ให้เราเขียน SDUK สำหรับ Markov chain ที่กำหนด ตั้งแต่ =3 แล้ว เจ=1, 2, 3.

จากความสัมพันธ์ (7) เราได้รับ

.
ดังนั้นเราจะมี

เงื่อนไขสุดท้ายเรียกว่าการทำให้เป็นมาตรฐาน
การกระจายความน่าจะเป็นเหนือรัฐเรียกว่า เครื่องเขียนหากไม่เปลี่ยนแปลงเมื่อเวลาผ่านไปนั่นคือที่ไหน รเจ=คอสต์, เจ=1,2,…,. จากที่นี่ .

จากนั้นจาก SDUK (7) เราได้รับระบบสำหรับค้นหาการกระจายแบบคงที่
(9)
สำหรับปัญหานี้จาก SDUK เราจะมี

จากเงื่อนไขการทำให้เป็นมาตรฐานที่เราได้รับ 3p2+p2+p2=1หรือ . ดังนั้นการกระจายขีดจำกัดจึงมีรูปแบบ
โปรดทราบว่าสามารถรับผลลัพธ์นี้ได้โดยตรงจากกราฟสถานะที่มีป้ายกำกับโดยใช้กฎ: สำหรับการแจกแจงแบบอยู่กับที่ ผลรวมของผลิตภัณฑ์ λ จิปี่, เจ≠ผมสำหรับลูกศรที่โผล่ออกมาจาก ผมรัฐเท่ากับผลรวมของผลิตภัณฑ์ λ จิปี่, เจ≠ผมสำหรับลูกศรที่รวมอยู่ใน ผมรัฐ จริงๆ,

เห็นได้ชัดว่าระบบที่ได้นั้นเทียบเท่ากับระบบที่รวบรวมตาม SDUK ดังนั้นจึงมีวิธีแก้ไขเหมือนกัน
คำตอบ: การกระจายแบบคงที่มีรูปแบบ .

Markov chain คือชุดของเหตุการณ์ที่แต่ละเหตุการณ์ที่ตามมาขึ้นอยู่กับเหตุการณ์ก่อนหน้า ในบทความเราจะวิเคราะห์แนวคิดนี้โดยละเอียด

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

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

สถานการณ์

จินตนาการว่ามีเพียงสอง สภาพอากาศ: อาจมีแดดจัดหรือมีเมฆมากก็ได้ คุณสามารถกำหนดสภาพอากาศได้อย่างแม่นยำเสมอ ช่วงเวลานี้. รับประกันว่าจะใสหรือขุ่น

ตอนนี้คุณต้องการเรียนรู้วิธีพยากรณ์อากาศสำหรับวันพรุ่งนี้ โดยสัญชาตญาณ คุณเข้าใจว่าสภาพอากาศไม่สามารถเปลี่ยนแปลงอย่างรวดเร็วในหนึ่งวัน มีหลายปัจจัยที่มีอิทธิพลต่อสิ่งนี้ สภาพอากาศของวันพรุ่งนี้ขึ้นอยู่กับสภาพอากาศในปัจจุบันและอื่น ๆ ดังนั้นในการทำนายสภาพอากาศคุณรวบรวมข้อมูลเป็นเวลาหลายปีและสรุปว่าหลังจากวันที่มีเมฆมากความน่าจะเป็นของวันที่มีแดดคือ 0.25 มีเหตุผลที่จะสันนิษฐานว่าความน่าจะเป็นของสองวันที่มีเมฆมากติดต่อกันคือ 0.75 เนื่องจากเรามีสภาพอากาศที่เป็นไปได้เพียงสองสภาพอากาศ

ตอนนี้คุณสามารถพยากรณ์อากาศล่วงหน้าได้หลายวันตามสภาพอากาศปัจจุบัน

ตัวอย่างนี้แสดงให้เห็น แนวคิดหลักโซ่มาร์คอฟ ห่วงโซ่ของมาร์คอฟประกอบด้วยชุดของการเปลี่ยนผ่านที่กำหนดโดยการแจกแจงความน่าจะเป็น ซึ่งจะเป็นไปตามคุณสมบัติของมาร์คอฟ

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

แบบอย่าง

อย่างเป็นทางการ Markov chain เป็นหุ่นยนต์ที่น่าจะเป็น การแจกแจงความน่าจะเป็นในการเปลี่ยนแปลงมักจะแสดงเป็นเมทริกซ์ หากเชนมาร์คอฟมี N สถานะที่เป็นไปได้ เมทริกซ์จะมีลักษณะเหมือน N x N ซึ่งรายการ (I, J) จะเป็นความน่าจะเป็นของการเปลี่ยนจากสถานะ I เป็นสถานะ J นอกจากนี้ เมทริกซ์ดังกล่าวจะต้องสุ่ม นั่นคือ แถวหรือคอลัมน์ควรรวมกันได้ไม่เกินหนึ่งแถว ในเมทริกซ์ดังกล่าว แต่ละแถวจะมีการแจกแจงความน่าจะเป็นของตัวเอง

มุมมองทั่วไปของห่วงโซ่มาร์คอฟที่มีสถานะในรูปแบบของวงกลมและขอบในรูปแบบของการเปลี่ยนภาพ

เมทริกซ์การเปลี่ยนแปลงโดยประมาณที่มีสามสถานะที่เป็นไปได้

เชนมาร์คอฟมีเวกเตอร์สถานะเริ่มต้นซึ่งแสดงเป็นเมทริกซ์ N x 1 มันอธิบายการแจกแจงความน่าจะเป็นของการเริ่มต้นในแต่ละสถานะที่เป็นไปได้ N รายการที่ฉันอธิบายความน่าจะเป็นของการเริ่มเชนในสถานะ I

โครงสร้างทั้งสองนี้เพียงพอที่จะเป็นตัวแทนของห่วงโซ่มาร์คอฟ

เราได้พูดคุยกันแล้วว่าจะรับความน่าจะเป็นของการเปลี่ยนแปลงจากสถานะหนึ่งไปยังอีกสถานะหนึ่งได้อย่างไร แต่สิ่งที่เกี่ยวกับการได้รับความน่าจะเป็นนี้ในหลายขั้นตอน ในการทำเช่นนี้เราต้องกำหนดความน่าจะเป็นของการเปลี่ยนจากสถานะ I เป็นสถานะ J ในขั้นตอน M จริงๆแล้วมันง่ายมาก เมทริกซ์การเปลี่ยนแปลง P สามารถกำหนดได้โดยการคำนวณ (I, J) โดยการเพิ่ม P เป็นกำลังของ M สำหรับค่า M ที่น้อยสามารถทำได้ด้วยตนเองโดยการคูณซ้ำ แต่สำหรับ ค่ามาก M ถ้าคุณคุ้นเคยกับพีชคณิตเชิงเส้นมากกว่านี้ วิธีที่มีประสิทธิภาพการยกกำลังของเมทริกซ์จะทำให้เมทริกซ์นั้นเป็นแนวทแยงมุมก่อน

ห่วงโซ่มาร์คอฟ: ข้อสรุป

ตอนนี้ เมื่อรู้ว่า Markov chain คืออะไร คุณก็สามารถนำไปใช้ได้อย่างง่ายดายในภาษาการเขียนโปรแกรมภาษาใดภาษาหนึ่ง ห่วงโซ่ Markov แบบธรรมดาเป็นรากฐานสำหรับการเรียนรู้เพิ่มเติม วิธีการที่ซับซ้อนการสร้างแบบจำลอง

สถานะที่เป็นไปได้ทั้งหมดของระบบในห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกัน และเป็นเมทริกซ์สโทแคสติกที่กำหนดห่วงโซ่นี้ ซึ่งประกอบด้วยความน่าจะเป็นของการเปลี่ยนแปลง (ดูหน้า 381)

แสดงตามความน่าจะเป็นที่ระบบอยู่ในสถานะ ณ เวลาหนึ่ง หากทราบว่า ณ เวลานั้นระบบอยู่ในสถานะ (,) อย่างชัดเจน, . การใช้ทฤษฎีบทเกี่ยวกับการบวกและการคูณความน่าจะเป็น เราสามารถค้นหา:

หรือในรูปแบบเมทริกซ์

ดังนั้นเราจึงได้รับสูตรที่สำคัญ

หากมีข้อจำกัด

หรือในรูปแบบเมทริกซ์

แล้วปริมาณ เรียกว่าความน่าจะเป็นที่จำกัดหรือการเปลี่ยนแปลงขั้นสุดท้าย

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

เราจะเรียกเมทริกซ์สโตแคสติกและลูกโซ่มาร์คอฟที่เป็นเนื้อเดียวกันว่าปกติ ถ้าเมทริกซ์นั้นไม่มีจำนวนลักษณะเฉพาะแตกต่างจากเอกภาพและเท่ากันในโมดูลัสต่อเอกภาพ และปกติ ถ้าเอกภาพเพิ่มเติมคือ รากที่เรียบง่าย สมการคุณลักษณะเมทริกซ์

เมทริกซ์ปกติมีลักษณะเป็นรูปแบบปกติ (69) (หน้า 373) เมทริกซ์เป็นแบบดั้งเดิม สำหรับเมทริกซ์ปกติ นอกจากนี้ .

นอกจากนี้ห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันเรียกว่า indecomposable, decomposable, acyclic, cyclic ถ้าสำหรับเชนนี้เมทริกซ์สโตแคสติกคือตามลำดับ ย่อยสลายไม่ได้ ย่อยสลายได้ ดั้งเดิมไม่ดั้งเดิม

เนื่องจากเมทริกซ์สโตแคสติกดั้งเดิมเป็นเมทริกซ์ปกติชนิดพิเศษ โซ่มาร์คอฟแบบอไซคลิกจึงเป็นโซ่ปกติชนิดพิเศษ

เราจะแสดงให้เห็นว่าความน่าจะเป็นที่จำกัดของการเปลี่ยนแปลงนั้นมีอยู่เฉพาะสำหรับเชนมาร์คอฟที่เป็นเนื้อเดียวกันปกติเท่านั้น

แท้จริงแล้ว ให้ เป็นพหุนามขั้นต่ำของเมทริกซ์ปกติ แล้ว

ตามทฤษฎีบทที่ 10 เราสามารถสันนิษฐานได้ว่า

ตามสูตร (24) ช. V (หน้า 113)

(96)

ที่ไหน เป็นเมทริกซ์ที่อยู่ติดกันที่ลดลงและ

ถ้าเป็นเมทริกซ์ปกติ

ดังนั้นทางด้านขวาของสูตร (96) พจน์ทั้งหมด ยกเว้นอันแรก มีแนวโน้มเป็นศูนย์เป็น ดังนั้น สำหรับเมทริกซ์ปกติ จะมีเมทริกซ์ที่ประกอบด้วยความน่าจะเป็นการเปลี่ยนแปลงจำกัด และ

สิ่งที่ตรงกันข้ามนั้นชัดเจน หากมีช่องว่าง

ดังนั้นเมทริกซ์จึงไม่สามารถมีได้ หมายเลขลักษณะซึ่งสำหรับสิ่งนี้ และ ตั้งแต่นั้นมาขีดจำกัดจะไม่มีอยู่ [ต้องมีขีดจำกัดเดียวกันเนื่องจากการมีอยู่ของขีดจำกัด (97")]

เราได้พิสูจน์แล้วว่าสำหรับห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันที่ถูกต้อง (และถูกต้องเท่านั้น) มีเมทริกซ์อยู่ เมทริกซ์นี้ถูกกำหนดโดยสูตร (97)

ให้เราแสดงวิธีแสดงเมทริกซ์ในรูปของพหุนามลักษณะเฉพาะ

และเมทริกซ์ที่เกี่ยวข้อง .

จากเอกลักษณ์

อาศัยอำนาจตาม (95), (95") และ (98) ดังนี้

ดังนั้นจึงสามารถแทนที่สูตร (97) ได้ด้วยสูตร

(97)

สำหรับ Markov chain ปกติ เนื่องจากเป็นชนิดพิเศษของ chain ปกติ เมทริกซ์จึงมีอยู่และถูกกำหนดโดยสูตร (97), (97") ในกรณีนี้ สูตร (97") ก็มีรูปแบบเช่นกัน

2. พิจารณาห่วงโซ่ปกติประเภททั่วไป (ผิดปกติ) เราเขียนเมทริกซ์ที่เกี่ยวข้องในรูปแบบปกติ

(100)

โดยที่เมทริกซ์สโตแคสติกดั้งเดิมและเมทริกซ์ที่แยกย่อยไม่ได้จะมีจำนวนคุณลักษณะสูงสุด ทะลึ่ง

,

เขียนในแบบฟอร์ม

(101)

แต่ เนื่องจากจำนวนคุณลักษณะทั้งหมดของเมทริกซ์มีค่าน้อยกว่าเอกภาพในค่าสัมบูรณ์ นั่นเป็นเหตุผล

(102)

เนื่องจากเป็นเมทริกซ์สุ่มดั้งเดิม ดังนั้นเมทริกซ์ตามสูตร (99) และ (35) (หน้า 362) จึงเป็นค่าบวก

และในแต่ละคอลัมน์ของเมทริกซ์เหล่านี้ องค์ประกอบทั้งหมดจะเท่ากัน:

.

โปรดทราบว่ารูปแบบปกติ (100) ของเมทริกซ์สุ่มสอดคล้องกับการแบ่งสถานะของระบบออกเป็นกลุ่ม:

แต่ละกลุ่มใน (104) สอดคล้องกับกลุ่มของซีรีส์ใน (101) ตามคำศัพท์ของ L. N. Kolmogorov สถานะของระบบที่รวมอยู่ในนั้นเรียกว่า จำเป็น และสถานะที่รวมอยู่ในกลุ่มที่เหลือเรียกว่า ไม่จำเป็น

จากรูปแบบ (101) ของเมทริกซ์ เป็นไปตามนั้นสำหรับขั้นตอนจำนวนจำกัดใดๆ (จากช่วงเวลาหนึ่งไปอีกช่วงเวลาหนึ่ง) การเปลี่ยนแปลงของระบบเท่านั้นที่เป็นไปได้ a) จากสถานะสำคัญไปสู่สถานะสำคัญของกลุ่มเดียวกัน b ) จากสถานะที่ไม่มีนัยสำคัญไปสู่สถานะที่จำเป็น และค) จากสถานะที่ไม่มีนัยสำคัญไปสู่สถานะที่ไม่สำคัญของกลุ่มเดียวกันหรือก่อนหน้า

จากรูปแบบ (102) ของเมทริกซ์ เป็นไปตามกระบวนการเมื่อการเปลี่ยนแปลงเป็นไปได้จากสถานะใดๆ ไปสู่สถานะที่จำเป็นเท่านั้น กล่าวคือ ความน่าจะเป็นของการเปลี่ยนไปสู่สถานะที่ไม่มีนัยสำคัญใดๆ มีแนวโน้มที่จะเป็นศูนย์ด้วยจำนวนขั้นตอน ดังนั้น บางครั้งสถานะที่จำเป็นจึงเรียกอีกอย่างว่าสถานะจำกัด

3. จากสูตร (97) จะเป็นดังนี้:

.

นี่แสดงให้เห็นว่าแต่ละคอลัมน์ของเมทริกซ์เป็นเวกเตอร์ลักษณะเฉพาะของเมทริกซ์สุ่มสำหรับหมายเลขลักษณะเฉพาะ

สำหรับเมทริกซ์ปกติ หมายเลข 1 เป็นรากอย่างง่ายของสมการคุณลักษณะ และตัวเลขนี้สอดคล้องกับเมทริกซ์ไอเกนเวกเตอร์เพียงตัวเดียว (ไม่เกินตัวประกอบสเกลาร์) ดังนั้น ในคอลัมน์ที่ th ของเมทริกซ์ องค์ประกอบทั้งหมดมีค่าเท่ากับจำนวนที่ไม่เป็นลบเท่ากัน:

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

ในทางกลับกัน หากในห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันปกติ ความน่าจะเป็นของการเปลี่ยนแปลงแต่ละรายการไม่ขึ้นอยู่กับสถานะเริ่มต้น เช่น สูตร (104) ค้าง ดังนั้นในแผนภาพ (102) สำหรับเมทริกซ์จึงเป็นสิ่งที่บังคับ แต่แล้วโซ่ก็เป็นปกติเช่นกัน

สำหรับห่วงโซ่อไซคลิก ซึ่งเป็นกรณีพิเศษของห่วงโซ่ปกติ เป็นเมทริกซ์ดั้งเดิม ดังนั้นสำหรับบางคน (ดูทฤษฎีบท 8 ในหน้า 377) แต่แล้วและ .

ในทางกลับกัน มันเป็นไปตามนั้นสำหรับบางคน และตามทฤษฎีบทที่ 8 หมายความว่าเมทริกซ์เป็นแบบดั้งเดิมและดังนั้นห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันที่กำหนดจึงเป็นวัฏจักร

เรากำหนดผลลัพธ์ที่ได้ในรูปแบบของทฤษฎีบทต่อไปนี้:

ทฤษฎีบท 11. 1. เพื่อให้ความน่าจะเป็นการเปลี่ยนผ่านที่จำกัดทั้งหมดมีอยู่ในห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกัน จึงมีความจำเป็นและเพียงพอที่จะทำให้ห่วงโซ่เป็นปกติ ในกรณีนี้ เมทริกซ์ ซึ่งประกอบด้วยความน่าจะเป็นการเปลี่ยนผ่านที่จำกัด ถูกกำหนดโดยสูตร (95) หรือ (98)

2. เพื่อให้ความน่าจะเป็นของการเปลี่ยนแปลงที่จำกัดเป็นอิสระจากสถานะเริ่มต้นในห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันปกติ จึงมีความจำเป็นและเพียงพอที่ห่วงโซ่จะเป็นปกติ ในกรณีนี้ เมทริกซ์ถูกกำหนดโดยสูตร (99)

3. เพื่อให้ความน่าจะเป็นของการเปลี่ยนแปลงที่จำกัดทั้งหมดแตกต่างจากศูนย์ในห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันปกติ จึงมีความจำเป็นและเพียงพอที่ห่วงโซ่จะเป็นวัฏจักร

4. ให้เราแนะนำคอลัมน์ของความน่าจะเป็นสัมบูรณ์

(105)

ความน่าจะเป็นของระบบที่อยู่ในสถานะ (,) ในขณะนี้อยู่ที่ไหน การใช้ทฤษฎีบทของการบวกและการคูณของความน่าจะเป็น เราพบ:

(,),

หรือในรูปแบบเมทริกซ์

เมทริกซ์ทรานสโพสสำหรับเมทริกซ์อยู่ที่ไหน

ความน่าจะเป็นสัมบูรณ์ทั้งหมด (105) ถูกกำหนดจากสูตร (106) หากทราบความน่าจะเป็นเริ่มต้นและเมทริกซ์ของความน่าจะเป็นการเปลี่ยนแปลง

ให้เราแนะนำการพิจารณาความน่าจะเป็นสัมบูรณ์ที่จำกัด

ผ่านความเท่าเทียมกันทั้งสองส่วน (106) จนถึงขีด จำกัด ที่ เราได้รับ:

โปรดทราบว่าการมีอยู่ของเมทริกซ์ของความน่าจะเป็นแบบจำกัดการเปลี่ยนหมายถึงการมีอยู่ของความน่าจะเป็นสัมบูรณ์จำกัด สำหรับความน่าจะเป็นเริ่มต้นใดๆ และในทางกลับกัน.

จากสูตร (107) และจากรูปแบบ (102) ของเมทริกซ์ จะได้ว่าความน่าจะเป็นสัมบูรณ์จำกัดที่สอดคล้องกับสถานะที่ไม่มีนัยสำคัญมีค่าเท่ากับศูนย์

การคูณเมทริกซ์ทั้งสองข้างให้เท่ากัน

ทางด้านขวา เราอาศัยอำนาจตาม (107) ได้รับ:

นั่นคือ คอลัมน์ของความน่าจะเป็นสัมบูรณ์ส่วนเพิ่มคือเวกเตอร์ลักษณะเฉพาะของเมทริกซ์สำหรับจำนวนคุณลักษณะ

ถ้า ก ห่วงโซ่ที่กำหนดมาร์คอฟ ปกติ แล้วเป็นรากอย่างง่ายของสมการคุณลักษณะของเมทริกซ์ ในกรณีนี้ คอลัมน์ของการจำกัดความน่าจะเป็นสัมบูรณ์จะพิจารณาจาก (108) (sinc และ ) โดยไม่ซ้ำกัน

ให้ห่วงโซ่มาร์คอฟปกติ จากนั้นจาก (104) และจาก (107) จะเป็นดังนี้:

(109)

ในกรณีนี้ ความน่าจะเป็นสัมบูรณ์ที่จำกัดไม่ได้ขึ้นอยู่กับความน่าจะเป็นเริ่มต้น

ในทางกลับกัน อาจไม่ขึ้นอยู่กับการมีสูตร (107) ก็ต่อเมื่อทุกแถวของเมทริกซ์เหมือนกัน นั่นคือ

,

ดังนั้น (ตามทฤษฎีบทที่ 11) จึงเป็นเมทริกซ์ปกติ

ถ้า เป็นเมทริกซ์ดั้งเดิม ดังนั้น และเนื่องจาก (109)

ในทางกลับกัน ถ้าทั้งหมดและไม่ขึ้นอยู่กับความน่าจะเป็นเริ่มต้น ดังนั้นในแต่ละคอลัมน์ของเมทริกซ์องค์ประกอบทั้งหมดจะเหมือนกันและเป็นไปตาม (109) และนี่ตามทฤษฎีบท 11 หมายความว่านั่นคือเมทริกซ์ดั้งเดิม นั่นคือ นี่ ห่วงโซ่เป็นวัฏจักร

จากข้างต้นสามารถกำหนดทฤษฎีบท 11 ได้ดังนี้:

ทฤษฎีบท 11. 1. เพื่อให้ความน่าจะเป็นสัมบูรณ์ที่จำกัดทั้งหมดมีอยู่ในห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันสำหรับความน่าจะเป็นเริ่มต้นใดๆ จำเป็นและเพียงพอที่ห่วงโซ่จะเป็นปกติ

2. เพื่อให้ห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันมีการจำกัดความน่าจะเป็นสัมบูรณ์สำหรับความน่าจะเป็นเริ่มต้นใดๆ และไม่ขึ้นอยู่กับความน่าจะเป็นเริ่มต้นเหล่านี้ มีความจำเป็นและเพียงพอที่ห่วงโซ่จะเป็นปกติ

3. เพื่อให้ห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันมีความน่าจะเป็นสัมบูรณ์ที่จำกัดในเชิงบวกสำหรับความน่าจะเป็นเริ่มต้นใดๆ และความน่าจะเป็นที่จำกัดเหล่านี้จะไม่ขึ้นอยู่กับความน่าจะเป็นเริ่มต้น มีความจำเป็นและเพียงพอที่ห่วงโซ่จะเป็นวัฏจักร

5. พิจารณาห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกัน ประเภททั่วไปด้วยเมทริกซ์ของความน่าจะเป็นในการเปลี่ยนผ่าน

ขอให้เราใช้รูปแบบปกติ (69) ของเมทริกซ์และแสดงด้วยดัชนีความไม่แน่นอนของเมทริกซ์ใน (69) อนุญาต เป็นจำนวนเต็มร่วมน้อย จากนั้นเมทริกซ์ไม่มีจำนวนลักษณะเฉพาะที่มีค่าสัมบูรณ์เท่ากับหนึ่ง แต่แตกต่างจากหนึ่งคือเป็นเมทริกซ์ปกติ ในเวลาเดียวกัน - ตัวบ่งชี้ที่เล็กที่สุดซึ่ง - เมทริกซ์ที่ถูกต้อง เราเรียกตัวเลขจำนวนหนึ่งว่าระยะเวลาของห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันที่กำหนด และ ในทางกลับกัน ถ้า และ กำหนดโดยสูตร (110) และ (110")

ความน่าจะเป็นสัมบูรณ์จำกัดโดยเฉลี่ยที่สอดคล้องกับสถานะที่ไม่จำเป็นจะเท่ากับศูนย์เสมอ

หากมีตัวเลขอยู่ในรูปแบบปกติของเมทริกซ์ (และในกรณีนี้เท่านั้น) ความน่าจะเป็นสัมบูรณ์แบบจำกัดค่าเฉลี่ยจะไม่ขึ้นอยู่กับความน่าจะเป็นเริ่มต้น และจะถูกกำหนดโดยเฉพาะจากสมการ (111)

บทความนี้ให้ ความคิดทั่วไปเกี่ยวกับวิธีการสร้างข้อความโดยการสร้างแบบจำลองกระบวนการ Markov โดยเฉพาะอย่างยิ่ง เราจะทำความคุ้นเคยกับ Markov chains และในทางปฏิบัติ เราจะใช้ตัวสร้างข้อความขนาดเล็กใน Python

ในการเริ่มต้น เราเขียนคำจำกัดความที่เราต้องการ แต่ยังไม่ชัดเจนสำหรับเราจากหน้า Wikipedia เพื่อที่จะจินตนาการคร่าวๆ ว่าเรากำลังเผชิญกับอะไร:

กระบวนการของมาร์คอฟ ที ที

ห่วงโซ่มาร์คอฟ

ทั้งหมดนี้หมายความว่าอย่างไร? ลองคิดดูสิ

พื้นฐาน

ตัวอย่างแรกนั้นง่ายมาก การใช้ประโยคจากหนังสือเด็ก เราจะเข้าใจแนวคิดพื้นฐานของห่วงโซ่มาร์คอฟ ตลอดจนกำหนดสิ่งที่อยู่ในบริบทของเรา คลังข้อมูล ลิงก์ การแจกแจงความน่าจะเป็น และฮิสโตแกรม. แม้ว่าข้อเสนอนั้น ภาษาอังกฤษสาระสำคัญของทฤษฎีจะเข้าใจได้ง่าย

ข้อเสนอนี้คือ กรอบนั่นคือฐานบนพื้นฐานของข้อความที่จะถูกสร้างขึ้นในอนาคต ประกอบด้วยแปดคำ แต่ในเวลาเดียวกัน คำที่ไม่ซ้ำกันเพียงห้าเท่านั้น ลิงค์(เรากำลังพูดถึงมาร์คอฟ โซ่). เพื่อความชัดเจน เราจะระบายสีแต่ละลิงก์ด้วยสีของตัวเอง:

และเขียนจำนวนการเกิดขึ้นของแต่ละลิงก์ในข้อความ:

ภาพด้านบนแสดงให้เห็นว่าคำว่า ปลาปรากฏในข้อความบ่อยกว่าแต่ละคำถึง 4 เท่า ( หนึ่ง สอง แดง น้ำเงิน). นั่นคือความน่าจะเป็นที่จะพบคำในคลังข้อมูลของเรา ปลาสูงกว่าความน่าจะเป็นที่จะพบทุกคำในภาพถึง 4 เท่า การพูดในภาษาคณิตศาสตร์ เราสามารถกำหนดกฎการกระจายของตัวแปรสุ่มและคำนวณด้วยความน่าจะเป็นที่คำใดคำหนึ่งจะปรากฏในข้อความหลังจากคำปัจจุบัน คำนวณความน่าจะเป็นดังนี้: คุณต้องหารจำนวนคำที่เราต้องการในคลังข้อมูลด้วย จำนวนทั้งหมดทุกคำในนั้น สำหรับคำว่า ปลาความน่าจะเป็นนี้คือ 50% เนื่องจากปรากฏขึ้น 4 ครั้งในประโยค 8 คำ สำหรับแต่ละลิงก์ที่เหลือ ความน่าจะเป็นนี้คือ 12.5% ​​(1/8)

แสดงการกระจายแบบกราฟิก ตัวแปรสุ่มเป็นไปได้ด้วยความช่วยเหลือ ฮิสโตแกรม. ในกรณีนี้ ความถี่ของการเกิดขึ้นของแต่ละลิงก์ในประโยคจะมองเห็นได้ชัดเจน:

ดังนั้น ข้อความของเราประกอบด้วยคำและลิงก์เฉพาะ และเราได้แสดงการแจกแจงความน่าจะเป็นของลักษณะที่ปรากฏของแต่ละลิงก์ในประโยคบนฮิสโตแกรม หากคุณคิดว่าคุณไม่ควรยุ่งกับสถิติให้อ่าน และอาจช่วยชีวิตคุณได้

สาระสำคัญของคำนิยาม

ตอนนี้ขอเพิ่มองค์ประกอบข้อความของเราที่บอกเป็นนัยเสมอ แต่ไม่ได้เปล่งออกมาในการพูดในชีวิตประจำวัน - จุดเริ่มต้นและจุดสิ้นสุดของประโยค:

ประโยคใดก็ตามที่มี "จุดเริ่มต้น" และ "จุดจบ" ที่มองไม่เห็น ลองเพิ่มเป็นลิงก์ไปยังการกระจายของเรา:

กลับไปที่คำจำกัดความที่ให้ไว้ในตอนต้นของบทความ:

กระบวนการของมาร์คอฟเป็นกระบวนการสุ่มที่มีวิวัฒนาการหลังจากนั้น ตั้งค่าพารามิเตอร์เวลา ทีไม่ขึ้นกับวิวัฒนาการที่ผ่านมา ทีโดยมีเงื่อนไขว่าค่าของกระบวนการในขณะนี้ได้รับการแก้ไข

ห่วงโซ่มาร์คอฟ - กรณีพิเศษกระบวนการ Markov เมื่อพื้นที่ของรัฐไม่ต่อเนื่องกัน (เช่น นับได้ไม่เกิน)

สิ่งนี้หมายความว่าอย่างไร พูดอย่างคร่าว ๆ เรากำลังจำลองกระบวนการที่สถานะของระบบในช่วงเวลาถัดไปขึ้นอยู่กับสถานะในขณะนั้นเท่านั้น และไม่ได้ขึ้นอยู่กับสถานะก่อนหน้านี้ทั้งหมดในทางใดทางหนึ่ง

จินตนาการถึงสิ่งที่อยู่ตรงหน้าคุณ หน้าต่างซึ่งแสดงเฉพาะสถานะปัจจุบันของระบบ (ในกรณีของเราคือคำเดียว) และคุณต้องกำหนดว่าคำต่อไปจะขึ้นอยู่กับข้อมูลที่แสดงในหน้าต่างนี้เท่านั้น ในคลังข้อมูลของเรา คำต่างๆ จะตามมาทีละคำตามรูปแบบต่อไปนี้:

ดังนั้นคำคู่จึงเกิดขึ้น (แม้แต่ท้ายประโยคก็มีคู่ของมันเอง - ค่าว่าง):

ลองจัดกลุ่มคู่นี้ตามคำแรก เราจะเห็นว่าแต่ละคำมีชุดของการเชื่อมโยงซึ่งในบริบทของประโยคของเรา พฤษภาคมติดตามเขา:

ขอนำเสนอข้อมูลนี้ในวิธีที่แตกต่างกัน - แต่ละลิงก์จะได้รับอาร์เรย์ของคำทั้งหมดที่อาจปรากฏในข้อความหลังจากลิงก์นี้:

ลองมาดูกันดีกว่า เราจะเห็นว่าแต่ละลิงค์มีคำว่า พฤษภาคม มาหลังจากนั้นในประโยค หากเราแสดงไดอะแกรมด้านบนให้คนอื่นดู บุคคลนั้นอาจสร้างแผนภาพของเราขึ้นใหม่ได้ ข้อเสนอเริ่มต้นนั่นคือคลังข้อมูล

ตัวอย่าง.เริ่มจากคำว่า เริ่ม. จากนั้นเลือกคำ หนึ่งเนื่องจากเป็นไปตามรูปแบบของเรา คำเดียวซึ่งสามารถตามขึ้นต้นประโยคได้ หลังคำว่า หนึ่งมีเพียงคำเดียวเท่านั้นที่สามารถติดตามได้ - ปลา. ตอนนี้ข้อเสนอใหม่ในรุ่นกลางดูเหมือนว่า ปลาหนึ่งตัว. นอกจากนี้ สถานการณ์ยังซับซ้อนมากขึ้น ปลาคำสามารถเป็นไปได้เท่ากันใน 25% "สอง", "แดง", "น้ำเงิน"และจบประโยค จบ. หากเราคิดว่าคำถัดไปคือ - "สอง"การสร้างใหม่จะดำเนินต่อไป แต่เราสามารถเลือกลิงค์ได้ จบ. ในกรณีนี้ ตามแบบแผนของเรา ประโยคจะถูกสร้างขึ้นแบบสุ่มซึ่งแตกต่างจากคลังข้อมูลมาก - ปลาหนึ่งตัว.

เราเพิ่งสร้างแบบจำลองกระบวนการมาร์คอฟ - เราได้กำหนดคำถัดไปแต่ละคำบนพื้นฐานของความรู้เกี่ยวกับคำปัจจุบันเท่านั้น สำหรับการดูดซึมวัสดุอย่างสมบูรณ์ มาสร้างไดอะแกรมที่แสดงการพึ่งพาระหว่างองค์ประกอบต่างๆ ภายในคลังข้อมูลของเรา วงรีเป็นตัวแทนของลิงค์ ลูกศรนำไปสู่ลิงก์ที่เป็นไปได้ที่สามารถต่อท้ายคำในวงรีได้ ใกล้กับลูกศรแต่ละอัน - ความน่าจะเป็นที่ลิงก์ถัดไปจะปรากฏขึ้นหลังจากลิงก์ปัจจุบัน:

ยอดเยี่ยม! เราได้เรียนรู้ ข้อมูลที่จำเป็นเพื่อดำเนินการต่อและแยกวิเคราะห์แบบจำลองที่ซับซ้อนมากขึ้น

ขยายฐานคำศัพท์

ในส่วนนี้ของบทความนี้ เราจะสร้างแบบจำลองตามหลักการเดียวกับก่อนหน้านี้ แต่เราจะละเว้นบางขั้นตอนในคำอธิบาย หากคุณมีปัญหาใด ๆ ให้กลับไปที่ทฤษฎีในบล็อกแรก

มาดูคำพูดอีกสี่ข้อจากผู้เขียนคนเดียวกัน (เป็นภาษาอังกฤษด้วย จะได้ไม่ทำร้ายเรา):

“วันนี้คุณเป็นคุณ นั่นเป็นเรื่องจริงยิ่งกว่าจริง ไม่มีใครมีชีวิตที่เป็นคุณมากกว่าคุณ"

“คุณมีสมองอยู่ในหัวของคุณ คุณมีเท้าอยู่ในรองเท้าของคุณ คุณสามารถบังคับตัวเองไปในทิศทางใดก็ได้ที่คุณเลือก คุณเป็นของคุณเอง "

"ยิ่ง นั่นคุณอ่าน, ยิ่งสิ่งที่คุณจะได้รู้ ยิ่งเรียนรู้มาก ก็ยิ่งไปในที่ต่างๆ ได้มากขึ้น"

คิดซ้าย คิดขวา คิดต่ำ คิดสูง โอ้ความคิดที่คุณคิดได้ถ้าคุณลองเท่านั้น "

ความซับซ้อนของคลังข้อมูลเพิ่มขึ้น แต่ในกรณีของเรานี่เป็นเพียงข้อดี - ตอนนี้ตัวสร้างข้อความจะสามารถสร้างประโยคที่มีความหมายมากขึ้นได้ ความจริงก็คือในภาษาใด ๆ มีคำที่เกิดขึ้นในการพูดบ่อยกว่าคำอื่น ๆ (ตัวอย่างเช่นเราใช้คำบุพบท "ใน" บ่อยกว่าคำว่า "cryogenic") ยังไง คำมากขึ้นในคลังข้อมูลของเรา (และด้วยเหตุนี้การพึ่งพาระหว่างกัน) ยิ่งตัวสร้างมีข้อมูลมากขึ้นเกี่ยวกับคำที่มีแนวโน้มมากที่สุดที่จะปรากฏในข้อความหลังจากคำปัจจุบัน

วิธีที่ง่ายที่สุดในการอธิบายสิ่งนี้คือจากมุมมองของโปรแกรม เรารู้ว่าสำหรับแต่ละลิงก์มีชุดคำที่สามารถติดตามได้ นอกจากนี้แต่ละคำยังโดดเด่นด้วยจำนวนครั้งที่ปรากฏในข้อความ เราจำเป็นต้องรวบรวมข้อมูลทั้งหมดนี้ไว้ในที่เดียว พจนานุกรมที่เก็บคู่ "(คีย์, ค่า)" เหมาะที่สุดสำหรับจุดประสงค์นี้ คีย์พจนานุกรมจะบันทึกสถานะปัจจุบันของระบบ นั่นคือ ลิงก์หนึ่งในคลังข้อมูล (เช่น "เดอะ"ในภาพด้านล่าง); และพจนานุกรมอีกอันจะถูกเก็บไว้ในค่าพจนานุกรม ในพจนานุกรมที่ซ้อนกัน คีย์จะเป็นคำที่สามารถปรากฏในข้อความหลังจากหน่วยคลังข้อมูลปัจจุบัน ( "คิด"และ มากกว่าไปในข้อความหลัง "เดอะ") และค่า - จำนวนการเกิดขึ้นของคำเหล่านี้ในข้อความหลังลิงก์ของเรา (คำว่า "คิด"ปรากฏในข้อความหลังคำ "เดอะ" 1 ครั้ง คำ มากกว่าหลังจากคำว่า "เดอะ"- 4 ครั้ง):

อ่านย่อหน้าด้านบนซ้ำหลาย ๆ ครั้งเพื่อให้ถูกต้อง โปรดทราบว่าพจนานุกรมที่ซ้อนกันในกรณีนี้คือฮิสโตแกรมเดียวกัน ซึ่งช่วยให้เราติดตามลิงก์และความถี่ของการเกิดขึ้นในข้อความที่สัมพันธ์กับคำอื่นๆ ควรสังเกตว่าแม้แต่ฐานคำศัพท์ดังกล่าวยังเล็กมากสำหรับการสร้างข้อความที่เหมาะสม ภาษาธรรมชาติ- ควรมีมากกว่า 20,000 คำและควรมากกว่า 100,000 และดียิ่งขึ้น - มากกว่า 500,000 แต่ลองดูฐานพจนานุกรมที่เรามี

ห่วงโซ่มาร์คอฟในกรณีนี้ถูกสร้างขึ้นคล้ายกับตัวอย่างแรก - แต่ละคำถัดไปจะถูกเลือกบนพื้นฐานของความรู้เกี่ยวกับคำปัจจุบันเท่านั้นโดยไม่คำนึงถึงคำอื่น ๆ ทั้งหมด แต่เนื่องจากการจัดเก็บข้อมูลในพจนานุกรมเกี่ยวกับคำที่ปรากฏบ่อยกว่าคำอื่น ๆ เราจึงสามารถเลือกที่จะยอมรับได้ การตัดสินใจที่มีน้ำหนัก. ลองดูตัวอย่างที่เฉพาะเจาะจง:

มากกว่า:

นั่นคือถ้าคำปัจจุบันเป็นคำ มากกว่าหลังจากนั้นอาจมีคำที่มีความน่าจะเป็นเท่ากันใน 25% "สิ่งของ"และ "สถานที่"และด้วยความน่าจะเป็น 50% - คำ "นั่น". แต่ความน่าจะเป็นสามารถเป็นได้และทั้งหมดเท่ากัน:

คิด:

ทำงานกับหน้าต่าง

จนถึงตอนนี้ เราได้พิจารณาเพียงหนึ่งหน้าต่างคำ คุณสามารถเพิ่มขนาดของหน้าต่างเพื่อให้ตัวสร้างข้อความสร้างประโยคที่ "ยืนยัน" ได้มากขึ้น ซึ่งหมายความว่ายิ่งหน้าต่างใหญ่ขึ้นเท่าใด ความเบี่ยงเบนจากตัวถังก็จะยิ่งน้อยลงเท่านั้นในระหว่างการสร้าง การเพิ่มขนาดหน้าต่างสอดคล้องกับการเปลี่ยนแปลงของ Markov chain ให้มากขึ้น ลำดับสูง. ก่อนหน้านี้เราสร้างห่วงโซ่ของลำดับที่หนึ่งสำหรับหน้าต่างของสองคำเราได้รับห่วงโซ่ของลำดับที่สองของสาม - ของที่สามและอื่น ๆ

หน้าต่างเป็นข้อมูลใน สถานะปัจจุบันระบบที่ใช้ในการตัดสินใจ หากเรารวมหน้าต่างขนาดใหญ่และชุดข้อมูลขนาดเล็ก เรามักจะได้รับประโยคเดียวกันทุกครั้ง ลองใช้ฐานพจนานุกรมจากตัวอย่างแรกของเราแล้วขยายหน้าต่างเป็นขนาด 2:

ส่วนขยายส่งผลให้แต่ละหน้าต่างตอนนี้มีเพียงตัวเลือกเดียวสำหรับสถานะระบบถัดไป - ไม่ว่าเราจะทำอะไร เราก็จะได้รับประโยคเดียวกันเสมอ เหมือนกันกับคลังข้อมูลของเรา ดังนั้น เพื่อทดลองกับหน้าต่างและเพื่อให้ตัวสร้างข้อความแสดงเนื้อหาที่ไม่ซ้ำใคร ให้ตุนฐานคำศัพท์ 500,000 คำขึ้นไป

การใช้งานใน Python

โครงสร้างข้อมูลไดโคแกรม

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

นำเข้าคลาสสุ่ม Dictogram(dict): def __init__(self, iterable=None): # เริ่มต้นการกระจายของเราเป็นวัตถุคลาสใหม่ # เพิ่มองค์ประกอบที่มีอยู่ super(Dictogram, self).__init__() self.types = 0 # จำนวน คีย์เฉพาะในการแจกจ่ายโทเค็น self.token = 0 # ทั้งหมดของคำทั้งหมดในการแจกจ่าย if iterable: self.update(iterable) def update(self, iterable): # อัพเดตการแจกจ่ายด้วยไอเท็มจาก # ชุดข้อมูล iterable ที่มีอยู่สำหรับไอเท็มใน iterable: if item in self: self += 1 self .tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # คืนค่าตัวนับของไอเท็ม หรือ 0 ถ้า item ในตัวเอง: return self return 0 def return_random_word (ตัวเอง): Random_key = Random.sample(ตัวเอง, 1) # อีกวิธี: # Random.choice(histogram.keys()) คืนค่า Random_key def return_weighted_random_word(ตัวเอง): # สร้างตัวเลขสุ่มหลอกระหว่าง 0 ถึง (n- 1), # โดยที่ n คือจำนวนคำทั้งหมด Random_int = Random.randint(0, self.tokens-1) index = 0 list_of_keys = self.keys() # print "random index:", Random_int for i in range( 0, self.types): ดัชนี += self] # พิมพ์ดัชนี if(ดัชนี > Random_int): # พิมพ์ list_of_keys[i] ส่งคืน list_of_keys[i]

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

เรายังสร้างฟังก์ชันส่งคืนสองฟังก์ชัน คำสุ่ม. ฟังก์ชั่นหนึ่งเลือกคีย์สุ่มในพจนานุกรมและอีกฟังก์ชั่นหนึ่งโดยคำนึงถึงจำนวนการเกิดขึ้นของแต่ละคำในข้อความ ส่งคืนคำที่เราต้องการ

โครงสร้างลูกโซ่มาร์คอฟ

จากฮิสโตแกรมนำเข้าไดโทแกรม def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Just append to theromev_model distribution].update ( ]) อื่น: markov_model] = ไดสัญลักษณ์ (]) กลับ markov_model

ในการใช้งานข้างต้น เรามีพจนานุกรมที่เก็บหน้าต่างเป็นคีย์ในคู่ "(คีย์, ค่า)" และการกระจายเป็นค่าในคู่นั้น

โครงสร้างของห่วงโซ่มาร์คอฟลำดับที่ N

จากฮิสโตแกรมนำเข้าไดโทแกรม def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Create window window = tuple(data) # Add to dictionary if window in markov_model: # แนบไปกับการกระจายที่มีอยู่ markov_model.update(]) อื่น: markov_model = Dictogram(]) คืนค่า

คล้ายกับห่วงโซ่มาร์คอฟลำดับที่หนึ่ง แต่ในกรณีนี้เราจัดเก็บ ทูเพิลเป็นคีย์ในคู่ "(คีย์, ค่า)" ในพจนานุกรม เราใช้มันแทนรายการเนื่องจากทูเพิลได้รับการปกป้องจากการเปลี่ยนแปลงใด ๆ และนี่เป็นสิ่งสำคัญสำหรับเรา - ท้ายที่สุดแล้วคีย์ในพจนานุกรมไม่ควรเปลี่ยนแปลง

การแยกวิเคราะห์โมเดล

เยี่ยมมาก เราได้ใช้พจนานุกรมแล้ว แต่จะสร้างเนื้อหาตามสถานะปัจจุบันและก้าวไปสู่สถานะถัดไปได้อย่างไร มาดูโมเดลของเรากัน:

จากฮิสโตแกรม นำเข้าไดสโตแกรม นำเข้าสุ่มจากคอลเลกชัน นำเข้า deque นำเข้า re def create_random_start(model): # หากต้องการสร้างคำเริ่มต้นใดๆ ให้ใช้รหัสด้านล่าง: # ถูกต้อง คำเริ่มต้นคือสิ่งที่ขึ้นต้นประโยคใน if "END" ใน model corpus: seed_word = "END" ในขณะที่ seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return random.choice( รุ่น .keys()) def create_random_sentence(ความยาว, markov_model): current_word = create_random_start(markov_model) ประโยค = สำหรับ i ในช่วง (0, ความยาว): current_dictogram = markov_model Random_weighted_word = current_dictogram.return_weighted_random_word() current_word = Random_weighted_word ประโยคต่อท้าย (current_word ) ประโยค = ประโยค.capitalize() กลับ " ".join(ประโยค) + "." กลับประโยค

อะไรต่อไป?

ลองคิดว่าคุณสามารถใช้ตัวสร้างข้อความตามเชนมาร์คอฟได้ที่ไหน อย่าลืมว่าสิ่งที่สำคัญที่สุดคือวิธีที่คุณแยกวิเคราะห์โมเดลและข้อจำกัดพิเศษที่คุณตั้งไว้ในการสร้าง ตัวอย่างเช่น ผู้เขียนบทความนี้ใช้หน้าต่างขนาดใหญ่เมื่อสร้างโปรแกรมสร้างทวีต จำกัดเนื้อหาที่สร้างไว้ที่ 140 ตัวอักษร และใช้เฉพาะคำที่ "ถูกต้อง" เพื่อเริ่มประโยค นั่นคือคำที่ขึ้นต้นประโยคใน คลังข้อมูล

วิธี คำอธิบายทางคณิตศาสตร์กระบวนการสุ่มของมาร์คอฟในระบบที่มีสถานะไม่ต่อเนื่อง (DS) ขึ้นอยู่กับว่าจุดเวลาใด (ทราบล่วงหน้าหรือสุ่ม) การเปลี่ยนระบบจากสถานะหนึ่งไปอีกสถานะหนึ่งสามารถเกิดขึ้นได้
หากการเปลี่ยนแปลงของระบบจากสถานะหนึ่งไปยังอีกสถานะหนึ่งเป็นไปได้ในช่วงเวลาที่กำหนดไว้ล่วงหน้า เรากำลังดำเนินการอยู่ สุ่ม กระบวนการของมาร์คอฟด้วยเวลาที่ไม่ต่อเนื่องหากการเปลี่ยนแปลงเป็นไปได้ในเวลาสุ่ม เรากำลังเผชิญกับ กระบวนการมาร์คอฟแบบสุ่มพร้อมเวลาต่อเนื่อง
ปล่อยให้มี ระบบทางกายภาพ สซึ่งอาจจะอยู่ใน นรัฐ ส 1 , ส 2 , …, เอส เอ็น. การเปลี่ยนจากสถานะหนึ่งไปยังอีกสถานะหนึ่งเป็นไปได้ในบางครั้งเท่านั้น ที 1 , ที 2 , …, ที เคเรียกช่วงเวลาเหล่านี้ว่าขั้นตอนเวลา เราจะพิจารณา SP ในระบบ สเป็นฟังก์ชันของอาร์กิวเมนต์จำนวนเต็ม 1, 2, ..., เคโดยที่อาร์กิวเมนต์คือหมายเลขขั้นตอน
ตัวอย่าง: ส 1 → ส 2 → ส 3 → ส 2 .
ให้เราแสดงว่า ศรี (เค) เป็นเหตุการณ์ที่ประกอบด้วยความจริงที่ว่าหลังจาก เคขั้นตอนที่ระบบอยู่ในสถานะ S ผม.
สำหรับใดๆ เคเหตุการณ์ ส 1 ( เค), ส2 ( เค),…,ส น (เค) รูปร่าง ครบทุกกลุ่มกิจกรรมและเป็น เข้ากันไม่ได้

กระบวนการในระบบสามารถแสดงเป็นห่วงโซ่ของเหตุการณ์
ตัวอย่าง: ส 1 (0) , สส2(1) , ส3(2) , ส5(3) ,….
ลำดับดังกล่าวเรียกว่า ห่วงโซ่มาร์คอฟ ถ้าแต่ละขั้นตอนมีความน่าจะเป็นของการเปลี่ยนจากสถานะใดๆ ศรีในสถานะใด ๆ เอสเจไม่ได้ขึ้นอยู่กับว่าระบบมาถึงรัฐเมื่อไหร่และอย่างไร ศรี.
ให้เมื่อใดก็ได้หลังจากนั้น เคระบบขั้นตอนไป สสามารถอยู่ในรัฐใดรัฐหนึ่งได้ ส 1 , ส 2 , …, เอส เอ็นคือ เหตุการณ์หนึ่งเหตุการณ์จากกลุ่มเหตุการณ์ทั้งหมดสามารถเกิดขึ้นได้: ส 1 (เค), ส2 ( เค) , …, เอส เอ็น (เค) . ให้เราแสดงความน่าจะเป็นของเหตุการณ์เหล่านี้:
พี 1 (1) = พี(ส 1 (1)); พี 2 (1) = พี(ส 2 (1)); …; พี เอ็น(1) = พี(เอส เอ็น (เค));
พี 1 (2) = พี(ส 1 (2)); พี 2 (2) = พี(S2(2)); …; พี เอ็น(2) = พี(เอส เอ็น (2));
พี 1 (เค) = พี(ส 1 (เค)); พี 2 (เค) = พี(ส 2 (เค)); …; พี เอ็น(เค) = พี(เอส เอ็น (เค)).
มันง่ายที่จะเห็นว่าสำหรับแต่ละขั้นตอนหมายเลขเงื่อนไข
พี 1 (เค) + พี 2 (เค) +…+ พี เอ็น(เค) = 1.
เรียกความน่าจะเป็นเหล่านี้ว่า ความน่าจะเป็นของรัฐ.consoquently งานจะดัง: ค้นหาความน่าจะเป็นของสถานะระบบใดๆ เค.
ตัวอย่าง.ให้มีระบบบางอย่างที่สามารถอยู่ในสถานะใดก็ได้ในหกสถานะ จากนั้นกระบวนการที่เกิดขึ้นสามารถอธิบายได้ทั้งในรูปแบบของกราฟของการเปลี่ยนแปลงในสถานะของระบบ (รูปที่ 7.9 ก) หรือในรูปแบบของกราฟสถานะของระบบ (รูปที่ 7.9 ข).

ก)

ข้าว. 7.9
นอกจากนี้ กระบวนการในระบบสามารถแสดงเป็นลำดับของสถานะ: ส 1 , ส 3 , ส 2 , ส 2 , ส 3 , ส 5 , ส 6 , ส 2 .
ความน่าจะเป็นของรัฐใน ( เค+ 1)-ขั้นตอนที่ขึ้นอยู่กับสถานะเท่านั้นที่ k-ขั้นตอนเมตร
สำหรับขั้นตอนใดๆ เคมีความน่าจะเป็นบางประการของการเปลี่ยนระบบจากสถานะใดๆ ไปเป็นสถานะอื่น เรียกความน่าจะเป็นเหล่านี้ว่า ความน่าจะเป็นการเปลี่ยนแปลงของห่วงโซ่มาร์คอฟ
ความน่าจะเป็นบางส่วนเหล่านี้จะเป็น 0 ถ้าการเปลี่ยนจากสถานะหนึ่งไปอีกสถานะหนึ่งไม่สามารถทำได้ในขั้นตอนเดียว
เรียกว่าห่วงโซ่มาร์คอฟ เป็นเนื้อเดียวกันหากสถานะการเปลี่ยนไม่ขึ้นอยู่กับหมายเลขขั้นตอน มิฉะนั้นจะเรียกว่า ต่างกัน.
ปล่อยให้มีห่วงโซ่มาร์คอฟที่เป็นเนื้อเดียวกันและปล่อยให้ระบบ สมันมี นสถานะที่เป็นไปได้: ส 1 , …, เอส เอ็น. ให้ทราบความน่าจะเป็นของการเปลี่ยนไปสู่อีกสถานะหนึ่งในขั้นตอนเดียวสำหรับแต่ละสถานะ เช่น พี อิจ(จาก ศรีใน เอสเจในขั้นตอนเดียว) จากนั้นเราก็สามารถเขียนความน่าจะเป็นในการเปลี่ยนผ่านเป็นเมทริกซ์ได้

. (7.1)
บนเส้นทแยงมุมของเมทริกซ์นี้คือความน่าจะเป็นที่ระบบผ่านจากสถานะ ศรีในสถานะเดียวกัน ศรี.
โดยใช้เหตุการณ์ที่แนะนำก่อนหน้านี้ ความน่าจะเป็นในการเปลี่ยนแปลงสามารถเขียนเป็นความน่าจะเป็นแบบมีเงื่อนไขได้:
.
แน่นอนผลรวมของเงื่อนไข ในแต่ละแถวของเมทริกซ์ (1) เท่ากับหนึ่ง เนื่องจากเหตุการณ์ สร้างกลุ่มเหตุการณ์ที่เข้ากันไม่ได้ทั้งหมด

เมื่อพิจารณาห่วงโซ่มาร์คอฟ เช่นเดียวกับเมื่อวิเคราะห์มาร์คอฟ กระบวนการสุ่มใช้กราฟสถานะต่างๆ (รูปที่ 7.10)

ข้าว. 7.10

ระบบนี้สามารถอยู่ในหกสถานะใด ๆ ในขณะที่ พี อิจคือความน่าจะเป็นของการเปลี่ยนระบบจากสถานะ ศรีเข้าสู่สถานะ เอสเจ. สำหรับระบบนี้ เราเขียนสมการที่ระบบอยู่ในบางสถานะและจากนั้นในช่วงเวลานั้น ทีไม่ออกมา:

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

รู้เมทริกซ์ของความน่าจะเป็นการเปลี่ยนแปลงและ สถานะเริ่มต้นระบบคุณสามารถค้นหาความน่าจะเป็นของรัฐ หลังจากนั้น เคขั้นตอนที่ ให้ในช่วงเวลาเริ่มต้นระบบอยู่ในสถานะ ส. จากนั้นสำหรับ t = 0
.
ค้นหาความน่าจะเป็นหลังจากขั้นตอนแรก ออกจากรัฐ สระบบจะเข้าสู่สถานะ ส 1 , ส 2 ฯลฯ ด้วยความน่าจะเป็น น 1 , น 2 , …, พี มม, …, น. หลังจากขั้นตอนแรกความน่าจะเป็นจะเท่ากัน

. (7.2)
มาหาความน่าจะเป็นของรัฐหลังจากขั้นตอนที่สอง: . เราจะคำนวณความน่าจะเป็นเหล่านี้โดยใช้สูตร ความน่าจะเป็นอย่างเต็มที่ด้วยสมมติฐาน:
.
สมมติฐานจะเป็นข้อความต่อไปนี้:

• หลังจากขั้นตอนแรกระบบอยู่ในสถานะ S 1 -H 1 ;
• หลังจากขั้นตอนที่สอง ระบบอยู่ในสถานะ S 2 -H 2 ;
• หลังจาก นขั้นตอนที่ระบบอยู่ในสถานะ S n -H n

ความน่าจะเป็นของสมมติฐานทราบได้จากนิพจน์ (7.2) ความน่าจะเป็นแบบมีเงื่อนไขการเปลี่ยนสถานะ แต่สำหรับแต่ละสมมติฐานยังเป็นที่รู้จักและบันทึกไว้ในเมทริกซ์สถานะการเปลี่ยนผ่าน จากนั้นตามสูตรความน่าจะเป็นทั้งหมด เราได้รับ:

ความน่าจะเป็นของสถานะใด ๆ หลังจากขั้นตอนที่สอง:

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

(7.4)
ดังนั้นความน่าจะเป็นของรัฐหลังจากนั้น เคขั้นตอน -th ถูกกำหนดโดย สูตรที่เกิดซ้ำ(7.4) ในแง่ของความน่าจะเป็น ( k- 1) ขั้นตอนที่

ภารกิจที่ 6เมทริกซ์ของความน่าจะเป็นการเปลี่ยนแปลงสำหรับเชนมาร์คอฟในขั้นตอนเดียวจะได้รับ ค้นหาเมทริกซ์การเปลี่ยนแปลงของวงจรที่กำหนดในสามขั้นตอน .
วิธีการแก้.เมทริกซ์การเปลี่ยนแปลงของระบบเป็นเมทริกซ์ที่มีความน่าจะเป็นการเปลี่ยนแปลงทั้งหมดของระบบนี้:

แต่ละแถวของเมทริกซ์มีความน่าจะเป็นของเหตุการณ์ (การเปลี่ยนจากสถานะ ผมเข้าสู่สถานะ เจ) ซึ่งเป็นกลุ่มที่สมบูรณ์ ดังนั้นผลรวมของความน่าจะเป็นของเหตุการณ์เหล่านี้จึงเท่ากับหนึ่ง:

แสดงโดย p ij (n) ความน่าจะเป็นที่เป็นผลมาจาก n ขั้นตอน (การทดสอบ) ระบบจะย้ายจากสถานะ i เป็นสถานะ j ตัวอย่างเช่น หน้า 25 (10) - ความน่าจะเป็นของการเปลี่ยนจากสถานะที่สองเป็นสถานะที่ห้าในสิบขั้นตอน โปรดทราบว่าสำหรับ n=1 เราได้รับความน่าจะเป็นในการเปลี่ยนแปลง p ij (1)=p ij
เราเผชิญกับงาน: รู้ความน่าจะเป็นของการเปลี่ยนแปลง p ij ค้นหาความน่าจะเป็น p ij (n) ของการเปลี่ยนระบบจากสถานะ ผมเข้าสู่สถานะ เจต่อ นขั้นตอน ในการทำเช่นนี้ เราแนะนำตัวกลาง (ระหว่าง ผมและ เจ) สภาพ ร. กล่าวอีกนัยหนึ่งเราจะถือว่าจากสถานะเริ่มต้น ผมต่อ มขั้นตอน ระบบจะเข้าสู่สถานะกลาง รด้วยความน่าจะเป็น p ij (n-m) หลังจากนั้นสำหรับส่วนที่เหลือ นาโนเมตรจากสถานะระดับกลาง r มันจะผ่านไปยังสถานะสุดท้าย j ด้วยความน่าจะเป็น p ij (n-m) . ตามสูตรความน่าจะเป็นทั้งหมด เราได้รับ:
.
สูตรนี้เรียกว่าความเท่าเทียมกันของมาร์คอฟ เมื่อใช้สูตรนี้ คุณจะพบความน่าจะเป็นทั้งหมด p ij (n) และเมทริกซ์ P n เอง เนื่องจากแคลคูลัสเมทริกซ์นำไปสู่เป้าหมายได้เร็วขึ้น ให้เราเขียนความสัมพันธ์เมทริกซ์ต่อจากสูตรที่ได้มาในรูปแบบทั่วไป
คำนวณเมทริกซ์การเปลี่ยนแปลงของเชนมาร์คอฟในสามขั้นตอนโดยใช้สูตรผลลัพธ์:

ตอบ:.

งาน #1. เมทริกซ์ความน่าจะเป็นการเปลี่ยนแปลงสำหรับห่วงโซ่มาร์คอฟคือ:
.
การกระจายเหนือสถานะ ณ เวลา t=0 ถูกกำหนดโดยเวกเตอร์:
π 0 \u003d (0.5; 0.2; 0.3)
หา:ก) การกระจายไปทั่วรัฐในขณะนี้ t=1,2,3,4 .
c) การกระจายแบบอยู่กับที่