Вивчайте Що таке методи Монте-Карло?

Визначення

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

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

Як це працює?

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

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

Приклади

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

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

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

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

\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy

Область визначення: цей подвійний інтеграл має дві змінні, $x \in [0, 1]$ та $y \in [0, 1]$ ;
Генерація: обидві ці змінні незалежні одна від одної та рівномірно розподілені;
Оцінювання: для отримання значення в точці використовується функція під інтегралом;
Агрегація: значення цього інтегралу можна визначити як об'єм під кривою. Об'єм можна обчислити як добуток площі основи та середньої висоти. Площа основи дорівнює 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}")

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

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

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

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

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

\frac{\text{Кількість точок у чверті кола}}{\text{Загальна кількість точок}} \approx \frac\pi4

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

\pi \approx 4 \cdot \frac{\text{Кількість точок всередині}}{\text{Загальна кількість точок}}


              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}")

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

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

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

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

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

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

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

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

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

Запитати АІ

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

Awesome!

Completion rate improved to 2.7

Свайпніть щоб показати меню

Визначення

Як це працює?

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

Приклади

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

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

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

\int_0^1 \int_0^1 \frac{1}{1 + (x + y)^2} \, dx \, dy

Область визначення: цей подвійний інтеграл має дві змінні, $x \in [0, 1]$ та $y \in [0, 1]$ ;
Генерація: обидві ці змінні незалежні одна від одної та рівномірно розподілені;
Оцінювання: для отримання значення в точці використовується функція під інтегралом;
Агрегація: значення цього інтегралу можна визначити як об'єм під кривою. Об'єм можна обчислити як добуток площі основи та середньої висоти. Площа основи дорівнює 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}")

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

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

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

\frac{\text{Кількість точок у чверті кола}}{\text{Загальна кількість точок}} \approx \frac\pi4

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

\pi \approx 4 \cdot \frac{\text{Кількість точок всередині}}{\text{Загальна кількість точок}}


              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}")

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

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

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

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

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

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

Як це працює?

Приклади

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

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

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

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

Awesome!

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

Як це працює?

Приклади

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

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

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

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

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

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