מבוא לרשתות מרקוב עם דוגמאות - שרשראות מרקוב עם פיתון

מבוא לרשתות מרקוב:

האם תהית אי פעם כיצד גוגל מדרגת דפי אינטרנט? אם ביצעת את המחקר שלך, עליך לדעת שהוא משתמש באלגוריתם PageRank המבוסס על הרעיון של רשתות מרקוב. מאמר זה על מבוא לרשתות מרקוב יעזור לך להבין את הרעיון הבסיסי העומד מאחורי רשתות מרקוב וכיצד ניתן לדגם אותם כפתרון לבעיות בעולם האמיתי.

הנה רשימה של נושאים שיוסקרו בבלוג זה:

1. מהי שרשרת מרקוב?
2. מהו נכס מרקוב?
3. הבנת שרשרות מרקוב עם דוגמה
4. מהי מטריצת מעבר?
5. שרשרת מרקוב בפייתון
6. יישומי שרשרת מרקוב

כדי לקבל ידע מעמיק במדעי נתונים ולמידת מכונה באמצעות פייתון, אתה יכול להירשם לשידור חי מאת אדוריקה עם תמיכה 24/7 וגישה לכל החיים.

מהי שרשרת מרקוב?

אנדריי מרקוב הציג לראשונה את רשתות מרקוב בשנת 1906. הוא הסביר את רשתות מרקוב כ:

תהליך סטוכסטי המכיל משתנים אקראיים, המעבר ממצב אחד למשנהו בהתאם להנחות מסוימות וכללים הסתברותיים מוגדרים.

אלה אקראיים משתנים עוברים מאחד למצב לאחר, בהתבסס על מאפיין מתמטי חשוב הנקרא נכס מרקוב.

זה מביא אותנו לשאלה:

מהו נכס מרקוב?

מאפיין זמן נפרד של מרקוב קובע כי ההסתברות המחושבת של מעבר אקראי למצב אפשרי הבא תלויה רק ​​במצב ובזמן הנוכחי והוא אינו תלוי בסדרת המצבים שקדמה לו.

העובדה שהפעולה / מצב האפשרי הבא של תהליך אקראי אינה תלויה ברצף המצבים הקודמים, הופכת את שרשראות מרקוב כתהליך נטול זיכרון שתלוי אך ורק במצב / פעולה הנוכחי של משתנה.

בואו נגזור זאת מתמטית:

תן לתהליך האקראי להיות, {Xm, m = 0,1,2, ⋯}.

תהליך זה הוא רשת מרקוב רק אם,

שרשרת מרקוב - מבוא לרשתות מרקוב - אדוריקה

מערך מיון c ++

לכל m, j, i, i0, i1, ⋯ im & minus1

למספר סופי של מצבים, S = {0, 1, 2, ⋯, r}, זה נקרא שרשרת מרקוב סופית.

P (Xm + 1 = j | Xm = i) מייצג כאן את הסתברויות המעבר למצב ממצב אחד למשנהו. הנה, אנו מניחים שהסתברויות המעבר אינן תלויות בזמן.

מה שאומר ש- P (Xm + 1 = j | Xm = i) אינו תלוי בערך 'm'. לכן אנו יכולים לסכם,

נוסחת שרשרת מרקוב - מבוא לרשתות מרקוב - אדוריקה

אז המשוואה הזו מייצגת רשת מרקוב.

עכשיו בואו להבין מהן בדיוק רשתות מרקוב עם דוגמא.

דוגמא לשרשרת מרקוב

לפני שאביא לך דוגמה, נגדיר מהו מודל מרקוב:

מהו מודל מרקוב?

מודל מרקוב הוא מודל סטוכסטי המדגם משתנים אקראיים באופן שהמשתנים עוקבים אחר מאפיין מרקוב.

עכשיו בואו להבין איך מודל מרקוב עובד עם דוגמה פשוטה.

כאמור, רשתות מרקוב משמשות ליישומי הפקת טקסטים והשלמה אוטומטית. לדוגמא זו, נסתכל על משפט לדוגמא (אקראי) ונראה כיצד ניתן לעצב אותו באמצעות רשתות מרקוב.

דוגמא לשרשרת מרקוב - מבוא לרשתות מרקוב - אדוריקה

המשפט הנ'ל הוא הדוגמה שלנו, אני יודע שזה לא הגיוני במיוחד (זה לא חייב), זה משפט המכיל מילים אקראיות, שבו:

1. מפתחות ציין את המילים הייחודיות במשפט, כלומר 5 מקשים (אחד, שניים, ברד, שמח, אדוריקה)

2. אסימונים ציין את מספר המילים הכולל, כלומר 8 אסימונים.

בכדי להתקדם, עלינו להבין את תדירות הופעתן של מילים אלה, התרשים שלהלן מציג כל מילה יחד עם מספר המציין את תדירות המילה.

מפתחות ותדרים - מבוא לשרשראות מרקוב - אדוריקה

אז העמודה השמאלית כאן מציינת את המקשים והעמודה הימנית מציינת את התדרים.

מהטבלה לעיל, אנו יכולים להסיק כי המפתח 'edureka' עולה פי 4 כמו כל מפתח אחר. חשוב להסיק מידע כזה מכיוון שהוא יכול לעזור לנו לחזות איזו מילה עשויה להתרחש בנקודת זמן מסוימת. אם הייתי מנחש לגבי המילה הבאה במשפט הדוגמא, הייתי הולך עם 'edureka' מכיוון שיש לה את הסבירות הגבוהה ביותר להתרחש.

אם כבר מדברים על הסתברות, מדד נוסף שאתה חייב להיות מודע אליו הוא חלוקות משוקללות.

במקרה שלנו, ההתפלגות המשוקללת של 'edureka' היא 50% (4/8) מכיוון שהתדירות שלה היא 4, מתוך סך 8 האסימונים. לשאר המקשים (אחד, שניים, ברד, שמח) לכולם סיכוי 1/8 להתרחש (& אסימפ 13%).

כעת, כשיש לנו הבנה של ההתפלגות המשוקללת ורעיון כיצד מילים ספציפיות מתרחשות בתדירות גבוהה יותר מאחרות, נוכל להמשיך עם החלק הבא.

הבנת שרשראות מרקוב - מבוא לרשתות מרקוב - אדוריקה

באיור לעיל, הוספתי שתי מילים נוספות המציינות את תחילת המשפט ואת סוף המשפט, אתה תבין מדוע עשיתי זאת בחלק שלהלן.

עכשיו נקצה את התדירות גם למפתחות אלה:

מפתחות ותדרים מעודכנים - מבוא לרשתות מרקוב - אדוריקה

עכשיו בואו ניצור מודל מרקוב. כאמור, מודל מרקוב משמש למודל משתנים אקראיים במצב מסוים באופן שהמצבים העתידיים של משתנים אלה תלויים אך ורק במצבם הנוכחי ולא במצבי העבר שלהם.

אז בעצם במודל מרקוב, כדי לחזות את המצב הבא, עלינו לשקול רק את המצב הנוכחי.

בתרשים שלהלן תוכלו לראות כיצד כל אסימון במשפט שלנו מוביל לאחד אחר. זה מראה שהמצב העתידי (האסימון הבא) מבוסס על המצב הנוכחי (האסימון הנוכחי). אז זה הכלל הבסיסי ביותר במודל מרקוב.

התרשים שלהלן מראה כי ישנם זוגות אסימונים כאשר כל אסימון בזוג מוביל לשני באותו זוג.

זוגות שרשרת מרקוב - מבוא לרשתות מרקוב - אדוריקה

בתרשים שלהלן יצרתי ייצוג מבני המציג כל מפתח עם מערך של אסימונים אפשריים הבאים שהוא יכול להתאים איתם.

מערך זוגות שרשרות מרקוב - מבוא לרשתות מרקוב - אדוריקה

לסיכום דוגמה זו שקול תרחיש שבו תצטרך ליצור משפט באמצעות מערך המפתחות והאסימונים שראינו בדוגמה שלעיל. לפני שנבצע דוגמה זו, נקודה חשובה נוספת היא שעלינו לציין שני מדדים ראשוניים:

1. התפלגות הסתברות ראשונית (כלומר, מצב ההתחלה בזמן = 0, (מקש 'התחל'))

2. הסתברות מעבר לקפיצה ממצב אחד למשנהו (במקרה זה, ההסתברות לעבור מסמל אחד לשני)

הגדרנו את ההתפלגות המשוקללת בהתחלה עצמה, אז יש לנו את ההסתברויות ואת המצב ההתחלתי, עכשיו נמשיך עם הדוגמה.

• אז ראשית מהאסימון הראשוני הוא [התחל]

• לאחר מכן, יש לנו רק אסימון אחד אפשרי כלומר [אחד]

• נכון לעכשיו, למשפט יש מילה אחת בלבד, כלומר 'אחת'.

• מהאסימון הזה, האסימון הבא האפשרי הוא [edureka]

• המשפט מעודכן ל'אדוריקה אחת '

• מ [edureka] אנו יכולים לעבור לכל אחד מהאסימונים הבאים [שניים, ברד, שמח, סוף]

• קיים סיכוי של 25% ש'שניים 'ייבחרו, הדבר עלול לגרום להיווצרות המשפט המקורי (edureka one edureka hagl edureka happy edureka). עם זאת, אם נבחר 'סוף' אז התהליך ייפסק ובסוף נוצר משפט חדש, כלומר, 'אדוריקה אחת'.

תני לעצמך טפיחה על השכם כי פשוט בנית מודל מרקוב וניהלת באמצעותו מקרה מבחן. לסיכום הדוגמה לעיל, בעצם השתמשנו במצב הנוכחי (המילה הנוכחית) כדי לקבוע את המצב הבא (המילה הבאה). וזה בדיוק מה שתהליך מרקוב.

זהו תהליך סטוכסטי שבו משתנים אקראיים עוברים ממצב אחד למשנהו באופן שמצב עתידי של משתנה תלוי רק במצב הנוכחי.

בואו ניקח את זה לשלב הבא ונצייר את מודל מרקוב לדוגמא זו.

תרשים מעבר מדינה - מבוא לרשתות מרקוב - אדוריקה

האיור לעיל מכונה דיאגרמת המעבר של המדינה. נדבר על כך יותר בסעיף להלן, לעת עתה רק זכרו כי תרשים זה מראה את המעברים וההסתברות ממצב אחד למשנהו.

שימו לב שכל סגלגל באיור מייצג מפתח והחיצים מופנים לעבר המקשים האפשריים שיכולים לעקוב אחריו. כמו כן, המשקולות על החצים מציינות את הסתברות או התפלגות משוקללת של מעבר מ / למדינות המתאימות.

אז זה היה בערך איך עובד מודל מרקוב. עכשיו בואו ננסה להבין כמה טרמינולוגיות חשובות בתהליך מרקוב.

מהי מטריצת הסתברות מעבר?

בחלק לעיל דנו בעבודה של מודל מרקוב עם דוגמה פשוטה, כעת בואו נבין את המינוחים המתמטיים בתהליך מרקוב.

בתהליך מרקוב אנו משתמשים במטריצה ​​כדי לייצג את הסתברויות המעבר ממצב אחד למשנהו. מטריצה ​​זו נקראת מטריצת מעבר או הסתברות. זה בדרך כלל מסומן על ידי פ.

מטריקס מעבר - מבוא לרשתות מרקוב - אדוריקה

שים לב, pij & ge0, ו- 'i' לכל הערכים הוא,

נוסחת מטריצת מעבר - מבוא לרשתות מרקוב - אדוריקה

תן לי להסביר את זה. בהנחה שמצבנו הנוכחי הוא 'אני', המדינה הבאה או הקרובה צריכה להיות אחת המדינות הפוטנציאליות. לכן, תוך כדי סיכום כל הערכים של k, עלינו להשיג אחד.

מהי תרשים מעבר מדינה?

מודל מרקוב מיוצג על ידי תרשים מעבר מדינה. התרשים מראה את המעברים בין המצבים השונים בשרשרת מרקוב. בואו ונבין את מטריצת המעבר ואת מטריצת המעבר למדינה בדוגמא.

דוגמה למטריקס מעבר

שקול שרשרת מרקוב עם שלוש מצבים 1, 2 ו- 3 וההסתברויות הבאות:

דוגמה למטריקס מעבר - מבוא לרשתות מרקוב - אדוריקה

דוגמה לתרשים מעבר מדינה - מבוא לרשתות מרקוב - אדוריקה

התרשים שלמעלה מייצג את דיאגרמת המעבר למצב של שרשרת מרקוב. כאן, 1,2 ו- 3 הם שלושת המצבים האפשריים, והחצים המצביעים ממצב אחד למדינות אחרות מייצגים את הסתברויות המעבר pij. כאשר, pij = 0, המשמעות היא שאין מעבר בין מצב 'אני' למצב 'j'.

עכשיו כשאנחנו מכירים את המתמטיקה וההיגיון שמאחורי רשתות מרקוב, בואו נפעיל הדגמה פשוטה ונבין היכן ניתן להשתמש ברשתות מרקוב.

שרשרת מרקוב בפייתון

כדי להריץ הדגמה זו, אשתמש בפייתון, כך שאם אינך מכיר את פייתון, תוכל לעבור על הבלוגים הבאים:

2. כיצד ללמוד פיתון 3 מ- Scratch - מדריך למתחילים

עכשיו בואו נתחיל בקידוד!

מחולל טקסטים בשרשרת מרקוב

הצהרת בעיה: כדי להחיל נכס Markov וליצור מודל Markov שיכול ליצור הדמיות טקסט על ידי עיון בערכת נתוני הדיבור של דונלד טראמפ

תיאור מערך הנתונים: קובץ הטקסט מכיל רשימת נאומים שנשא דונלד טראמפ בשנת 2016.

הִגָיוֹן: החל את Markov Property כדי ליצור את נאום טראמפ של דונלד על ידי בחינת כל מילה המשמשת בנאום, ועבור כל מילה, צור מילון של מילים המשמשות בהמשך.

שלב 1: ייבא את החבילות הנדרשות

ייבא קהה כ- np

שלב 2: קרא את מערך הנתונים

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', קידוד = 'utf8'). קרא () # הצג את הדפסת הנתונים (trump) דובר 1 ... תודה אתה כל כך. זה כל כך נחמד. הוא לא בחור נהדר. הוא לא מקבל עיתונות הוגנת הוא לא מקבל את זה. זה פשוט לא פייר. ואני חייב להגיד לך שאני כאן, ובאופן מאוד חזק כאן, כי יש לי כבוד רב לסטיב קינג וכבוד גדול גם כלפי סיטיזנס יונייטד, דייוויד וכולם, וכבוד עצום למסיבת התה. כמו כן, גם תושבי איווה. יש להם משהו במשותף. אנשים עובדים קשה ....

שלב 3: פצל את מערך הנתונים למילים בודדות

corpus = trump.split () # הצג את הדפוס הקורפוס (corpus) 'חזק', 'אבל', 'לא', 'חזק', 'כמו', 'לנו', 'איראן', 'יש', ' נזרע ',' אימה ', ...

לאחר מכן, צור פונקציה שיוצרת את זוגות המילים השונים בנאומים. כדי לחסוך מקום, נשתמש באובייקט גנרטור.

שלב 4: יצירת זוגות למפתחות ולמילות ההמשך

def make_pairs (corpus): עבור i בטווח (len (corpus) - 1): תשואה (corpus [i], corpus [i + 1]) זוגות = make_pairs (corpus)

לאחר מכן, בוא נתחיל מילון ריק לאחסון זוגות המילים.

במקרה שהמילה הראשונה בזוג היא כבר מפתח במילון, פשוט הוסף את המילה הפוטנציאלית הבאה לרשימת המילים העוקבות אחר המילה. אבל אם המילה אינה מפתח, אז צור ערך חדש במילון והקצה את המפתח השווה למילה הראשונה בזוג.

שלב 5: הוספת המילון

word_dict = {} עבור word_1, word_2 בזוגות: אם word_1 ב- word_dict.keys (): word_dict [word_1]. הוסף (word_2) אחר: word_dict [word_1] = [word_2]

לאחר מכן אנו בוחרים באקראי מילה מהקורפוס שתפתח את רשת מרקוב.

שלב 6: בנה את מודל מרקוב

# בחר באופן אקראי את המילה הראשונה first_word = np.random.choice (corpus) # בחר את המילה הראשונה כמילה באותיות רישיות כדי שהמילה שנבחרה לא תילקח בין משפט בעוד first_word.islower (): # התחל את השרשרת מ שרשרת המילים שנבחרה = [first_word] # יזם את מספר המילים המגורות n_words = 20

בעקבות המילה הראשונה, כל מילה בשרשרת נדגמת באקראי מרשימת המילים שבאו בעקבות אותה מילה ספציפית בנאומיו החיים של טראמפ. זה מוצג בקטע הקוד שלהלן:

עבור אני בטווח (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

שלב 7: חיזויים

לסיום, בואו ונציג את הטקסט המגורה.

#Join מחזיר את השרשרת כהדפס מחרוזת ('' .צטרף (שרשרת)) מספר האנשים המדהימים. ולהילרי קלינטון, יש לאנשים שלנו עבודה כל כך נהדרת. ולא ננצח את אובמה

אז זה הטקסט שנוצר שקיבלתי בהתחשב בנאומו של טראמפ. זה אולי לא הגיוני מאוד, אבל זה מספיק טוב כדי לגרום לך להבין כיצד ניתן להשתמש ברשתות מרקוב ליצירת טקסטים באופן אוטומטי.

עכשיו בואו נסתכל על כמה יישומים נוספים של רשתות מרקוב וכיצד הן משמשות לפתרון בעיות בעולם האמיתי.

יישומי שרשרת מרקוב

הנה רשימה של יישומים בעולם האמיתי של רשתות מרקוב:

1. דירוג הדף של גוגל: ניתן לחשוב על כל הרשת כמודל של מרקוב, כאשר כל דף אינטרנט יכול להיות מדינה וניתן לחשוב על הקישורים או ההפניות בין עמודים אלה כמעברים עם הסתברויות. כך שבעצם, ללא קשר לאיזה דף אינטרנט אתה מתחיל לגלוש, הסיכוי להגיע לדף אינטרנט מסוים, נניח, X הוא סבירות קבועה.

2. הקלדת חיזוי מילים: ידוע כי רשתות מרקוב משמשות לחיזוי מילים הקרובות. ניתן להשתמש בהם גם בהשלמה אוטומטית ובהצעות.

3. סימולציית Subreddit: אין ספק שנתקלתם ברדיט והייתה לכם אינטראקציה באחד מהשרשורים או הערכות המשנה שלהם. Reddit משתמש בסימולטור subreddit שצורך כמות עצומה של נתונים המכילה את כל התגובות והדיונים שנערכו בקבוצות שלהם. על ידי שימוש ברשתות מרקוב, הסימולטור מייצר הסתברויות מלה במילה, ליצירת הערות ונושאים.

   סכום הספרות של מספר בג'אווה באמצעות לולאה

4. מחולל טקסטים: רשתות מרקוב משמשות לרוב ליצירת טקסטים דמהיים או הפקת מאמרים גדולים וליקוט נאומים. הוא משמש גם במחוללי השמות שאתה רואה באינטרנט.

עכשיו שאתה יודע לפתור בעיה בעולם האמיתי באמצעות רשתות מרקוב, אני בטוח שאתה סקרן ללמוד עוד. הנה רשימה של בלוגים שיעזרו לך להתחיל עם מושגים סטטיסטיים אחרים:

עם זאת, אנו מגיעים לסוף הבלוג 'מבוא למרקוב שרשראות'. אם יש לך שאלות בנוגע לנושא זה, השאיר תגובה למטה ונחזור אליך.

הישאר מעודכן לבלוגים נוספים על הטכנולוגיות החמות.

אם אתם מחפשים הכשרה מובנית מקוונת במדעי הנתונים, אדוריקה! בעל אוצר מיוחד תוכנית המסייעת לך להשיג מומחיות בסטטיסטיקה, התעסקות בנתונים, ניתוח נתונים חקר, אלגוריתמים של למידת מכונה כמו אשכולות K-Means, עצים של החלטות, יער אקראי, Naive Bayes תלמדו את המושגים של סדרות זמן, כריית טקסטים וגם מבוא ללימוד עמוק. קבוצות חדשות לקורס זה מתחילות בקרוב !!