Skip to main content
LibreTexts - Ukrayinska

10.2.1: Застосування ланцюгів Маркова (вправи)

  1. Last updated
  2. Save as PDF
  • Page ID
    67161

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    РОЗДІЛ 10.2 НАБІР ЗАДАЧ: ЗАСТОСУВАННЯ ЛАНЦЮГІВ МАРКОВА

    Питання 1-2 стосуються наступного:

    Довідка: Барт Сінклер, модель ремонту машин. OpenStax CNX. 9 черв 2005 р. Ліцензія Зазначення Авторства 1.0. Завантажити безкоштовно можна за адресою http://cnx.org/contents/56f1bed0-bd34-4c28-a2ec-4a3f9ded8e18@3. Цей матеріал був змінений Робертою Блумом, як це дозволено цією ліцензією.

    Ланцюг Маркова може використовуватися для моделювання стану обладнання, такого як машина, яка використовується у виробничому процесі. Припустимо, що можливі стани для машини

    У режимі очікування та очікування роботи (I) Робота над роботою/завданням (W) Зламаний (B) У ремонті (R)

    Машина контролюється через рівні проміжки часу, щоб визначити її стан; для зручності інтерпретації в цій проблемі ми припускаємо, що стан контролюється щогодини. Матриця переходу показана нижче:

    Розділ 10.5.2 PNG

    1. Використовуйте матрицю переходу для виявлення наступних ймовірностей, що стосуються стану машини через годину
      1. Знайдіть ймовірність того, що машина працює на роботі через годину, якщо машина зараз простоює.
      2. Знайдіть ймовірність того, що машина простоює через годину, якщо машина працює на роботі зараз.
      3. Знайдіть ймовірність того, що машина працює на роботі через годину, якщо машина зараз ремонтується.
      4. Знайдіть ймовірність того, що машина ремонтується за одну годину, якщо вона зламана зараз.
    1. Виконайте відповідні розрахунки за допомогою матриці переходу, щоб знайти наступні ймовірності щодо стану машини через три години.
      1. Знайдіть ймовірність того, що машина працює на роботі через три години, якщо машина зараз простоює.
      2. Знайдіть ймовірність того, що машина простоює через три години, якщо машина зараз працює на роботі.
      3. Знайдіть ймовірність того, що машина працює на роботі через три години, якщо машина зараз ремонтується.
      4. Знайдіть ймовірність того, що машина ремонтується через три години, якщо вона зламана зараз.

    Питання 3-4 стосуються наступного опису того, як ланцюг Маркова може бути використаний для «навчання» комп'ютера для створення музики.

    Навчання теорії комп'ютерної музики, щоб вона могла створювати музику було б надзвичайно виснажливим завданням.
    Ви повинні були б навчити акорду будові, різним музичним стилям і так далі. Що робити, якби ви могли дати програмі приклади творів, які ви вважали музикою, і попросити її: «Напишіть щось подібне для мене». По суті, так працювала б наша ланцюг Маркова. Принцип, що лежить в основі ланцюгів Маркова в музиці, полягає в тому, щоб створити таблицю ймовірностей, щоб визначити, яка нота повинна наступити далі. Подаючи програмі приклад музичного твору, програма може проаналізувати твір і створити таблицю ймовірностей, щоб визначити, які ноти, швидше за все, слідують заданій ноті. За допомогою матриці ймовірності переходу можна генерувати випадкові ноти, які все ще мають певну музичну структуру. Побудувавши подібну матрицю для ударів або тривалості нот, можна завершити ланцюгову модель Маркова для генерації музики.

    Джерело: © Грудня 18, 2008 Френк Чен. Вміст підручника, створений Френком Ченом, ліцензується на умовах ліцензії Creative Commons Із зазначенням авторства 2.0. Завантажити безкоштовно можна за адресою http://cnx.org/contents/62219fba-96df-418a-b9aa-14fddd7c30fa@2.» Змінено Робертою Блумом, як це дозволено цією ліцензією.

    У наведеній нижче матриці переходу наведено приклад. Стани - це ноти A, A #, B, C, D, E, F, G, G#.
    Матриця показує ймовірність наступної ноти (стан стовпця), враховуючи поточну ноту (стан рядка).

    Для створення музики, створеної комп'ютером, комп'ютерна програма випадковим чином вибирає наступну ноту на основі попередньої ноти та ймовірностей, наведених у матриці переходу.

    Розділ 10.5.2-3.PNG

    1. Знайти ймовірність наступної ноти, враховуючи поточну ноту
      1. P (наступна нота - A | поточна нота G) = ______
      2. P (наступна нота G | поточна нота - A) = ______
      3. P (наступна нота - C | поточна нота F) = ______
      4. P (наступна нота E | поточна нота D) = ______

    4а. Якщо поточна нота - A # (A-sharp), що матриця переходу говорить нам про наступну ноту?

    4б. Якщо наступна нота F, що ми знаємо про поточну ноту.

    Питання 5 стосується наступного:

    Марківські ланцюги грають важливу роль в онлайн-пошуку.

    «PageRank - це алгоритм, який використовується Google Search для ранжування веб-сайтів у своїх результатах пошуку. PageRank був названий на честь Ларрі Пейджа, одного із засновників Google. PageRank — це спосіб вимірювання важливості сторінок веб-сайту»
    Джерело: https://en.Wikipedia.org/wiki/PageRank за Ліцензією Creative Commons Із зазначенням авторства — Поширення На Тих Самих Умовах

    Теорія PageRank полягає в тому, що сторінки, на які посилаються частіше, є більш важливими та корисними; виявлення тих, на які частіше посилаються теми, допомагає визначити сторінки, які повинні бути представлені як найбільш відповідні в пошуку.

    У реальному світі пошуку є тисячі або мільйони сторінок, що зв'язуються між собою, що призводить до величезних матриць переходу. Через розмір та інші властивості цих матриць математика за PageRank є більш складною, ніж невеликий приклад, який ми розглядаємо тут лише з чотирма веб-сайтами. Однак наш приклад адекватний, щоб передати основну концепцію PageRank і її використання в пошукових алгоритмах.

    Слід зазначити, що алгоритми пошуку в реальному світі, PageRank або аналогічні схеми ранжирування ланцюга Маркова - це лише один з безлічі використовуваних методів.

    Припустимо, у нас є 4 веб-сторінки, які містять посилання один на одного. Називаємо сторінки A, B, C, D.

    • Зі сторінки А 30% людей посилаються на сторінку B, 50% посилання на сторінку C і 20% посилання на сторінку D
    • Зі сторінки B 50% popele посилання на сторінку A і 50% посилання на сторінку D
    • З сторінки C 10% людей посилаються на сторінку B, 70% посилання на сторінку C і 20% посилання на сторінку D
    • Зі сторінки D 20% людей посилаються на сторінку A, 40% на сторінку B, 10% на сторінку C, 30% - на сторінку D

    (У цьому прикладі, коли сторінка посилається на себе, це означає, що людина, яка переглядає сторінку, залишається на цій сторінці і не посилається на іншу сторінку.)

    1. Запишіть матрицю переходу T
    1. Знайдіть ймовірність того, що людина, яка переглядає сторінку С, буде посилатися на сторінку D далі.
    1. Знайдіть ймовірність того, що людина, яка переглядає сторінку C, перегляне сторінку D після двох посилань
    1. Знайдіть ймовірність того, що людина, яка переглядає сторінку C, перегляне сторінку D після трьох посилань
    1. Знайдіть ймовірність того, що людина, яка переглядає сторінку C, залишиться на сторінці С і не посилається на будь-яку іншу сторінку поруч.
    1. Знайти ймовірність того, що людина, яка переглядає сторінку C, буде переглядати сторінку А далі