מהם שרשראות מרקוב? 5 שימושים עולמיים אמיתיים

פרסומת

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

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

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

שרשראות מרקוב 101

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

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

תאר לעצמך שהייתה לך גישה לשלושים שנות נתוני מזג אוויר. אתה מתחיל בהתחלה, וציין כי יום 1 היה שטוף שמש. אתם ממשיכים להמשיך ולשים לב שגם יום 2 היה בהיר, אך יום 3 היה מעונן, ואז יום 4 היה גשום, מה שהוביל לסופת רעמים ביום 5, ואחריו שמיים בהירים וצלולים ביום 6.

באופן אידיאלי, תהיה גרעיני יותר ותבחר לניתוח לפי שעה במקום ניתוח יום-יומי, אבל זו רק דוגמא להמחשת המושג, אז תשבי איתי!

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

• סיכוי של 50 אחוז שמחר יהיה בהיר.
• סיכוי של 30 אחוזים שמחר יהיה מעונן.
• סיכוי של 20 אחוזים שמחר יהיה גשום.

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

מדינות מעבר

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

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

כיצד משתמשים בשרשרות מרקוב בעולם האמיתי

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

דור שם

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

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

כל מה שאתה צריך זה אוסף של אותיות שבכל אות יש רשימה של מכתבי מעקב פוטנציאליים עם הסתברויות. כך, למשל, לאות "M" יש סיכוי של 60 אחוז להוביל לאות "A" וסיכוי של 40 אחוז להוביל לאות "אני". עשה זאת עבור חבורה שלמה של אותיות אחרות, ואז הפעל את האלגוריתם. בום, יש לך שם הגיוני! (רוב הזמן, בכל מקרה.)

דירוג דף של גוגל

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

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

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

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

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

הקלדת חיזוי מילים

הטלפונים הניידים מקלידים הקלדה כבר עשרות שנים, אך האם אתה יכול לנחש כיצד נוצרות התחזיות האלה? בין אם אתה משתמש באנדרואיד (אפשרויות מקשים חלופיים מה המקלדת האלטרנטיבית הטובה ביותר עבור אנדרואיד?אנו בודקים כמה מהמקלדות הטובות ביותר בחנות Play ומעמידות אותן במבחן. קרא עוד ) או iOS (אפשרויות מקשים חלופיים עשרת האפליקציות הטובות ביותר למקלדות לאייפון: גופנים מפוארים, ערכות נושא, GIFs ועודנמאס לכם ממקלדת ה- iPhone המוגדרת כברירת מחדל? אפליקציות מקלדת אלחוטיות אלה מציעות GIF, ערכות נושא, חיפוש ועוד. קרא עוד ), יש סיכוי טוב שהאפליקציה שבחרת תשתמש ברשתות Markov.

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

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

סימולציה של Subreddit

אם מעולם לא השתמשת ב- Reddit, אנו ממליצים לך לפחות לבדוק את הניסוי המרתק הזה שנקרא /r/SubredditSimulator.

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

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

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

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