บทนำสู่ Markov Chains: ข้อกำหนดเบื้องต้น คุณสมบัติ & การใช้งาน

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

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

ข้อกำหนดเบื้องต้น

จำเป็นต้องรู้แนวคิดสองสามข้อก่อนที่เราจะเริ่มพูดถึงเครือ Markov และส่วนใหญ่มาจากทฤษฎีความน่าจะเป็น ในทางคณิตศาสตร์ คุณสามารถกำหนดค่าของตัวแปรสุ่มอันเป็นผลจากเหตุการณ์สุ่มได้ ตัวอย่างเช่น หากตัวแปรเป็นผลมาจากการกลิ้งลูกเต๋า มันจะเป็นตัวเลข ในขณะที่ถ้ามันเป็นผลมาจากการพลิกเหรียญ มันจะเป็นบูลีน (0 หรือ 1) ชุดของผลลัพธ์ที่เป็นไปได้เหล่านี้อาจเป็นแบบต่อเนื่องและไม่ต่อเนื่อง

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

อ่าน: โครงสร้างข้อมูลที่สร้างขึ้นใน Python

บทนำสู่ Markov Chains

กลุ่ม Markov ได้ชื่อมาจาก Andrey Markov ผู้ซึ่งนำแนวคิดนี้มาใช้เป็นครั้งแรกในปี 1906 Markov chains อ้างถึงกระบวนการสุ่มที่มีตัวแปรสุ่ม และตัวแปรเหล่านั้นเปลี่ยนจากสถานะเป็นอีกสถานะหนึ่งตามกฎความน่าจะเป็นและสมมติฐาน

กฎความน่าจะเป็นและสมมติฐานเหล่านั้นคืออะไร? สิ่งเหล่านี้เรียกว่าคุณสมบัติ Markov ดูข้อมูลเพิ่มเติมเกี่ยวกับ Markov Chain ใน Python Tutorial

ทรัพย์สินของ Markov คืออะไร?

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

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

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

นี่คือการแสดงทางคณิตศาสตร์ของห่วงโซ่ Markov:

X = ( X n ) n N =( X 0 , X 1 , X 2 , …)

คุณสมบัติของ Markov Chains

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

ความสามารถในการลดทอน

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

Aperiodic

สมมุติว่าระยะเวลาของรัฐคือ k ถ้า k = 1 สถานะนี้จะเป็นระยะ ๆ เมื่อการกลับคืนสู่สถานะใด ๆ ต้องใช้เวลา k หลายครั้ง เมื่อสถานะของสาย Markov ทั้งหมดเป็นแบบ aperiodic เราสามารถพูดได้ว่าห่วงโซ่ Markov เป็น aperiodic

สถานะชั่วคราวและกำเริบ

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

มีสถานะกำเริบสองประเภทที่เราสามารถมีได้ สถานะแรกเป็นสถานะที่เกิดซ้ำเป็นค่าบวกที่มีเวลาส่งคืนที่คาดไว้จำกัด และสถานะที่สองคือสถานะเกิดซ้ำเป็น null ที่มีเวลาส่งคืนที่คาดไว้ไม่สิ้นสุด เวลาส่งคืนที่คาดหวังหมายถึงเวลาที่เกิดซ้ำเฉลี่ยเมื่อเราออกจากรัฐ

การใช้งานของ Markov Chains

กลุ่ม Markov พบการใช้งานในหลายพื้นที่ นี่คือแอปพลิเคชันที่โดดเด่นของพวกเขา:

• อัลกอริธึม PageRank ของ Google ปฏิบัติต่อเว็บเหมือนโมเดล Markov คุณสามารถพูดได้ว่าหน้าเว็บทั้งหมดเป็นสถานะ และลิงก์ระหว่างหน้านั้นเป็นช่วงการเปลี่ยนภาพที่มีความน่าจะเป็นเฉพาะ กล่าวอีกนัยหนึ่ง เราสามารถพูดได้ว่าไม่ว่าคุณกำลังค้นหาอะไรบน Google มีความเป็นไปได้ที่แน่นอนที่คุณจะได้ลงเอยที่หน้าเว็บบางหน้า
• หากคุณใช้ Gmail คุณต้องสังเกตเห็นคุณลักษณะป้อนอัตโนมัติ คุณลักษณะนี้จะคาดเดาประโยคของคุณโดยอัตโนมัติเพื่อช่วยให้คุณเขียนอีเมลได้อย่างรวดเร็ว เครือ Markov ช่วยเหลือในภาคส่วนนี้อย่างมาก เนื่องจากสามารถให้การคาดการณ์ในลักษณะนี้ได้อย่างมีประสิทธิภาพ
• คุณเคยได้ยิน Reddit ไหม? เป็นแพลตฟอร์มโซเชียลมีเดียที่สำคัญซึ่งเต็มไปด้วย subreddits (ชื่อชุมชนใน Reddit) ของหัวข้อเฉพาะ Reddit ใช้เครือและโมเดลของ Markov เพื่อจำลอง subreddits เพื่อความเข้าใจที่ดีขึ้นในสิ่งเดียวกัน

เรียนรู้เพิ่มเติม: วิวัฒนาการของการสร้างแบบจำลองภาษาในชีวิตสมัยใหม่

ความคิดสุดท้าย

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

หากคุณต้องการเรียนรู้เพิ่มเติมเกี่ยวกับหัวข้อนี้ คุณควรไปที่ส่วนหลักสูตรของเรา คุณจะพบทรัพยากรอันมีค่ามากมายที่นั่น

หากคุณอยากเรียนรู้เกี่ยวกับวิทยาศาสตร์ข้อมูล ให้ลองดูประกาศนียบัตร PG ด้านวิทยาศาสตร์ข้อมูลของ IIIT-B และ upGrad ซึ่งสร้างขึ้นสำหรับมืออาชีพด้านการทำงานและเสนอกรณีศึกษาและโครงการมากกว่า 10 รายการ เวิร์กช็อปภาคปฏิบัติจริง การให้คำปรึกษากับผู้เชี่ยวชาญในอุตสาหกรรม 1- on-1 กับที่ปรึกษาในอุตสาหกรรม การเรียนรู้มากกว่า 400 ชั่วโมงและความช่วยเหลือด้านงานกับบริษัทชั้นนำ