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

Визначення

Методи Монте-Карло (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{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

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

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

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

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

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

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

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

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

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

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

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

Запитати АІ

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

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

Визначення

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

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

Приклади

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

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

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

\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{Points inside the quarter circle}}{\text{Total points}} \approx \frac\pi4

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

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

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

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

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

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

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

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

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

Приклади

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

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

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

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

Awesome!

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

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

Приклади

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

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

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

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

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

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