Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Вивчайте Що Таке Методи Монте-Карло? | Методи Монте-Карло
Вступ до навчання з підкріпленням
course content

Зміст курсу

Вступ до навчання з підкріпленням

Вступ до навчання з підкріпленням

1. Основна Теорія Навчання з Підкріпленням
2. Проблема Багаторукого Бандита
3. Динамічне Програмування
4. Методи Монте-Карло
5. Навчання з часовою різницею

book
Що Таке Методи Монте-Карло?

Note
Визначення

Методи Монте-Карло (MC) — це клас обчислювальних алгоритмів, які ґрунтуються на випадковому вибірковому відборі для оцінки числових результатів.

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

Як вони працюють?

Методи Монте-Карло можуть відрізнятися залежно від завдання, але всі вони зазвичай дотримуються єдиного шаблону:

  1. Визначення області можливих вхідних даних;
  2. Генерування випадкових вхідних даних з імовірнісного розподілу;
  3. Оцінювання функції на цих вхідних даних;
  4. Агрегування результатів для отримання оцінки.

Приклади

Хоча описаний вище шаблон може здаватися складним, ці приклади допоможуть краще зрозуміти його суть.

Обчислення інтегралу

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

Спробуємо застосувати метод Монте-Карло для розв'язання цього інтегралу:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Область визначення: цей подвійний інтеграл має дві змінні, x[0,1]x \in [0, 1] та y[0,1]y \in [0, 1];
  2. Генерація: обидві ці змінні незалежні одна від одної та рівномірно розподілені;
  3. Оцінка: для отримання значення в точці використовується функція під інтегралом;
  4. Агрегація: значення цього інтегралу можна визначити як об'єм під кривою. Об'єм можна обчислити як добуток площі основи та середньої висоти. Площа основи — 1 (одиничний квадрат), а середня висота — це середнє значення результатів, отриманих на попередньому кроці.
12345678910111213141516
import numpy as np result = 0 # Many samples are required for estimates to be precise for i in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Computation of point value value = 1 / (1 + (x + y) ** 2) # Mean aggregation result += (value - result) / (i + 1) # Closed-form solution of this integral true_result = 2*np.arctan(2) - np.pi/2 - (1/2)*np.log(5) + np.log(2) print(f"Approximated result: {result}") print(f"True result: {true_result}")
copy

Наближення π\Large\pi

Наближення π\pi є одним із найвідоміших застосувань методу Монте-Карло. Це демонструє, як випадкове вибіркове дослідження може розв'язати геометричну задачу без складного числення.

Розглянемо одиничний квадрат із вписаною в нього чвертю кола:

  • Квадрат займає [0,1]×[0,1][0, 1] \times [0, 1];
  • Чверть кола має радіус 1 і центр у початку координат.

Площа чверті кола дорівнює πr24\displaystyle\frac{\pi r^2}{4} або π4\displaystyle\frac{\pi}{4}, а площа квадрата — 1. Тепер вибираємо випадкові точки всередині квадрата. За достатньо великої кількості вибірок:

Points inside the quarter circleTotal pointsπ4\frac{\text{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

Отже, значення π\pi можна обчислити як

π4Points insideTotal points\pi \approx 4 \cdot \frac{\text{Points inside}}{\text{Total points}}
1234567891011121314151617181920212223242526272829
import numpy as np import matplotlib.pyplot as plt # Lists for coordinates inside = [] outside = [] # Many samples are required for estimates to be precise for _ in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Splitting points inside and outside of the circle if x**2 + y**2 <= 1: inside.append((x, y)) else: outside.append((x, y)) # Plotting points plt.figure(figsize=(6,6)) plt.scatter(*zip(*inside), color="blue", s=1, label="Inside") plt.scatter(*zip(*outside), color="red", s=1, label="Outside") plt.legend() plt.xlabel("x") plt.ylabel("y") plt.show() estimate = 4 * len(inside) / (len(inside) + len(outside)) print(f"Estimated value of pi: {estimate}") print(f"True value of pi: {np.pi}")
copy

Задача багаторукого бандита

У задачі багаторукого бандита основною метою є оцінка цінності дії для кожного важеля — тобто, очікуваної винагороди за вибір певної дії. Поширеною стратегією є оцінювання цих значень шляхом усереднення спостережуваних винагород, отриманих при багаторазовому використанні кожного важеля з часом. Ця техніка фактично є методом Монте-Карло.

Методи Монте-Карло для MDP

На відміну від методів динамічного програмування, які залежать від повної та точної моделі динаміки середовища, методи Монте-Карло навчаються виключно на основі досвіду — тобто, з реальних або змодельованих послідовностей станів, дій і винагород.

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

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

question mark

Яка основна перевага використання методів Монте-Карло порівняно з методами динамічного програмування при розв'язанні MDP?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 4. Розділ 1

Запитати АІ

expand

Запитати АІ

ChatGPT

Запитайте про що завгодно або спробуйте одне із запропонованих запитань, щоб почати наш чат

course content

Зміст курсу

Вступ до навчання з підкріпленням

Вступ до навчання з підкріпленням

1. Основна Теорія Навчання з Підкріпленням
2. Проблема Багаторукого Бандита
3. Динамічне Програмування
4. Методи Монте-Карло
5. Навчання з часовою різницею

book
Що Таке Методи Монте-Карло?

Note
Визначення

Методи Монте-Карло (MC) — це клас обчислювальних алгоритмів, які ґрунтуються на випадковому вибірковому відборі для оцінки числових результатів.

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

Як вони працюють?

Методи Монте-Карло можуть відрізнятися залежно від завдання, але всі вони зазвичай дотримуються єдиного шаблону:

  1. Визначення області можливих вхідних даних;
  2. Генерування випадкових вхідних даних з імовірнісного розподілу;
  3. Оцінювання функції на цих вхідних даних;
  4. Агрегування результатів для отримання оцінки.

Приклади

Хоча описаний вище шаблон може здаватися складним, ці приклади допоможуть краще зрозуміти його суть.

Обчислення інтегралу

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

Спробуємо застосувати метод Монте-Карло для розв'язання цього інтегралу:

010111+(x+y)2dxdy\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy
  1. Область визначення: цей подвійний інтеграл має дві змінні, x[0,1]x \in [0, 1] та y[0,1]y \in [0, 1];
  2. Генерація: обидві ці змінні незалежні одна від одної та рівномірно розподілені;
  3. Оцінка: для отримання значення в точці використовується функція під інтегралом;
  4. Агрегація: значення цього інтегралу можна визначити як об'єм під кривою. Об'єм можна обчислити як добуток площі основи та середньої висоти. Площа основи — 1 (одиничний квадрат), а середня висота — це середнє значення результатів, отриманих на попередньому кроці.
12345678910111213141516
import numpy as np result = 0 # Many samples are required for estimates to be precise for i in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Computation of point value value = 1 / (1 + (x + y) ** 2) # Mean aggregation result += (value - result) / (i + 1) # Closed-form solution of this integral true_result = 2*np.arctan(2) - np.pi/2 - (1/2)*np.log(5) + np.log(2) print(f"Approximated result: {result}") print(f"True result: {true_result}")
copy

Наближення π\Large\pi

Наближення π\pi є одним із найвідоміших застосувань методу Монте-Карло. Це демонструє, як випадкове вибіркове дослідження може розв'язати геометричну задачу без складного числення.

Розглянемо одиничний квадрат із вписаною в нього чвертю кола:

  • Квадрат займає [0,1]×[0,1][0, 1] \times [0, 1];
  • Чверть кола має радіус 1 і центр у початку координат.

Площа чверті кола дорівнює πr24\displaystyle\frac{\pi r^2}{4} або π4\displaystyle\frac{\pi}{4}, а площа квадрата — 1. Тепер вибираємо випадкові точки всередині квадрата. За достатньо великої кількості вибірок:

Points inside the quarter circleTotal pointsπ4\frac{\text{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

Отже, значення π\pi можна обчислити як

π4Points insideTotal points\pi \approx 4 \cdot \frac{\text{Points inside}}{\text{Total points}}
1234567891011121314151617181920212223242526272829
import numpy as np import matplotlib.pyplot as plt # Lists for coordinates inside = [] outside = [] # Many samples are required for estimates to be precise for _ in range(100000): # Generation of random variables x, y = np.random.uniform(), np.random.uniform() # Splitting points inside and outside of the circle if x**2 + y**2 <= 1: inside.append((x, y)) else: outside.append((x, y)) # Plotting points plt.figure(figsize=(6,6)) plt.scatter(*zip(*inside), color="blue", s=1, label="Inside") plt.scatter(*zip(*outside), color="red", s=1, label="Outside") plt.legend() plt.xlabel("x") plt.ylabel("y") plt.show() estimate = 4 * len(inside) / (len(inside) + len(outside)) print(f"Estimated value of pi: {estimate}") print(f"True value of pi: {np.pi}")
copy

Задача багаторукого бандита

У задачі багаторукого бандита основною метою є оцінка цінності дії для кожного важеля — тобто, очікуваної винагороди за вибір певної дії. Поширеною стратегією є оцінювання цих значень шляхом усереднення спостережуваних винагород, отриманих при багаторазовому використанні кожного важеля з часом. Ця техніка фактично є методом Монте-Карло.

Методи Монте-Карло для MDP

На відміну від методів динамічного програмування, які залежать від повної та точної моделі динаміки середовища, методи Монте-Карло навчаються виключно на основі досвіду — тобто, з реальних або змодельованих послідовностей станів, дій і винагород.

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

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

question mark

Яка основна перевага використання методів Монте-Карло порівняно з методами динамічного програмування при розв'язанні MDP?

Select the correct answer

Все було зрозуміло?

Як ми можемо покращити це?

Дякуємо за ваш відгук!

Секція 4. Розділ 1
some-alt