Статьи

Алгоритм недели: методы Монте-Карло

Октябрь 2, 2018

Первый: почему?

Методы Монте-Карло отлично подходят для задач, которые являются достаточно сложными, поэтому точное решение почти невозможно, и 100% -ная точная точность не требуется. Какие проблемы? Хорошо, что я собираюсь рассмотреть в этом посте, это найти область под кривой (AKA Integration для Исчисления наклонен).

Но что это?

Методы Монте-Карло — это когда вы запускаете МНОГИЕ случайные «симуляции» и используете результаты для вычисления достаточно точного решения. В нашем примере интеграции мы будем случайным образом генерировать тысячи точек, вычислять процентное соотношение, которое произошло под рассматриваемой кривой, а затем использовать эти знания для вычисления площади.

Черная магия!

INORITE? Но серьезно. Вот наглядное пособие для того, что я буду делать: 

(из статьи в Википедии  здесь )

Я выберу несколько случайных точек вдоль оси x и выясню, где функция говорит, что мои максимальные и минимальные значения будут. Как только я это получу, моя функция разбивает эту прямоугольную область на две части. Здесь происходит волшебство. Мы знаем, как вычислить площадь  любого  прямоугольника. Путем случайного тестирования областей внутри прямоугольника и отслеживания того, какая доля наших тестов попала под кривую, мы получим процент. Этот процент будет представлять процент прямоугольной области, попадающей под кривую нашей функции.

Это казалось таким простым, пока я его не напечатал …

Код

Давайте начнем с самого высокого уровня в моем коде, чтобы дать вам краткое изложение того, что я делаю.

var integrate = function(fn, left_x, right_x, sample_count){
	var random_x_points = generate_x_values(left_x, right_x, sample_count);
	var y_bounds = compute_y_bounds(fn, random_x_points);
	var random_points = create_random_points(random_x_points, y_bounds);
	var points_under_curve = count_points_under_curve(fn, random_points)

	var percent_under_curve = points_under_curve / (1.0*random_points.length);
	var rectangle_area = (y_bounds.upper_bound-y_bounds.lower_bound)*(right_x-left_x)
	var area_under_curve = percent_under_curve * rectangle_area;

	return area_under_curve;
};

Прежде всего, давайте посмотрим на параметры. Функция интегрирования принимает функцию ‘fn’ для оценки, левую и правую границу x для нашего определенного интеграла… и счетчик выборок. Счетчик образцов странный. Помните изображение выше, где мы случайно застрелили тысячи точек на нашем графике? Вот что это. Это количество случайных точек, которые мы будем отбирать в данной области, и мы заинтересованы в ее вычислении.

На самом деле, интересным моментом являются первые пару строк функции. Сначала я генерирую несколько случайных значений x, затем прочесываю их и выясняю, каковы y-границы. Таким образом, я могу создать прямоугольник, который включает в себя как можно меньшую площадь.

Как только я получил свои x-точки и обнаружил мои y-границы, у меня появляется достаточно информации, чтобы создать все мои случайные точки. Когда это будет сделано, я беру все свои случайные точки и сравниваю их с реальной функцией и вижу, сколько моих случайных точек попадают под кривую функции.

Остальная часть функции довольно проста, когда вы ее визуализируете. По сути, я разграничил прямоугольную область, которая содержит функцию и все мои точки выборки. У нас есть левая и правая границы (заданные left_x и right_x), а также верхняя и нижняя границы (заданные y_bounds.upper_bound и y_bounds.lower_bound).

Вы можете увидеть весь мой пример и код здесь:  Нажмите здесь, чтобы попробовать

В этом примере я жестко закодировал функцию, которая кажется сложной: sin (log (x) ^ 2). Вот как я это называю:

var fn = function(x){
	return Math.sin(Math.pow(Math.log(x),2));
};
var result = integrate(fn, 0, 2, 10000);

Но одна ошибка

Есть одна особенность, и тогда кривая опускается ниже оси X. В исчислении вы можете помнить о необходимости проверить это и исправить положительную отрицательную область (в зависимости от вашего применения техники). Этот метод не имеет этой проблемы. Вместо этого по умолчанию вы можете получить код, который проверяет область под кривой вплоть до нижней границы y.

В функции «count_points_under_curve» здесь вы можете увидеть, где я проверяю fn_value на наличие выше или ниже нуля, прежде чем решить, какое определение «под кривой» я решу проверить.

var count_points_under_curve = function(fn, random_points){
	var points_under_curve = 0;
	for(var i in random_points){
		var random_point = random_points[i];
		var fn_value = fn(random_point.x);
		if(fn_value >= 0){
			if(random_point.y < fn_value){
				points_under_curve += 1;
			}
		} else {
			if(random_point.y > fn_value){
				points_under_curve += 1;
			}
		}
	}
	return points_under_curve;
};

В следующий раз

Это один из способов использования методов Монте-Карло. У меня есть другой пост, над которым я работаю, где я буду использовать методы Монте-Карло, чтобы исследовать сплит-тестирование и, надеюсь, проверить некоторые из теорий. В прошлом я также использовал его для изучения упрощенной модели разработки программного обеспечения.

Если вы когда-нибудь подумаете: «Я мог бы полностью найти ответ, если бы смог написать миллион разных примеров и увидеть результаты». Вы, вероятно, нашли вескую причину использовать этот инструмент.

35
Share: