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

Визначення

Методи Монте-Карло (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

Запитати АІ

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

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{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$