Алгоритмы неформально. Инструкция для начинающих питонистов - [19]
Рис. 3.2. Чтобы вычислить производную, нужно провести касательную к кривой в точке и определить ее угол наклона
Мы можем написать на Python функцию, которая задает производную следующим образом:
def revenue_derivative(tax):
return(100 * (1/(tax + 1) - 2 * (tax - 0.2)))
Для вычисления этой функции были использованы четыре правила. Во-первых, мы использовали правило о том, что производная log(x) равна 1 / x. Отсюда следует, что производная log(tax + 1) равна 1 / (tax + 1). Во-вторых, производная x2 равна 2x, поэтому производная (tax – 0,2)2 равна 2(tax – 0,2). Два последних правила — производная постоянного числа всегда равна 0, а производная 100f(x) равна 100 × производная f(x). Объединяя все эти правила, мы находим, что функция 100(log(tax + 1) – (tax – 0,2)2 + 0,04) имеет следующую производную, которая соответствует приведенной выше функции Python:
Простая проверка показывает, что при текущей ставке налога производная действительно отрицательна:
print(revenue_derivative(0.7))
Команда выводит результат -41.17647.
Отрицательная производная означает, что увеличение ставки налога приведет к снижению поступлений. И наоборот, снижение ставки должно привести к их повышению. Хотя точное значение ставки, обеспечивающее максимум кривой, нам пока не известно, по крайней мере, можно утверждать, что при небольшом смещении в сторону уменьшения ставки налога поступления должны возрасти.
Чтобы сделать шаг в направлении максимальных поступлений, необходимо сначала выбрать его размер. Мы сохраним достаточно малый размер шага в переменной Python:
step_size = 0.001
Затем продвинемся в направлении максимума и вычислим новую ставку, находящуюся в одном шаге от текущей в направлении максимума:
current_rate = current_rate + step_size * revenue_derivative(current_rate)
На данный момент процесс поиска максимума выглядит так: мы начинаем с текущей ставки налога и продвигаемся к максимуму на величину, пропорциональную выбранному значению step_size, в направлении, определяемом производной функции «ставка налога-поступления» при текущем значении ставки.
Можно убедиться в том, что после этого шага новое значение current_rate составит 0.6588235 (ставка налога около 66 %), а поступления, соответствующие этой ставке, равны 33.55896. Но хотя мы сделали шаг в направлении максимума и увеличили поступления, по сути, оказываемся в той же ситуации, что и прежде: максимум еще не достигнут, но мы знаем производную функции и общее направление для дальнейшего перемещения. Таким образом, мы просто делаем еще один шаг — точно так же, как и прежде, но со значениями, соответствующими новой ставке. Снова выполняется присваивание:
current_rate = current_rate + step_size * revenue_derivative(current_rate)
После повторного присваивания новое значение current_rate равно 0.6273425, а поступления, соответствующие новой ставке, составят 34.43267. Мы сделали еще один шаг в правильном направлении. Тем не менее максимум еще не достигнут, и чтобы приблизиться к нему, нужно сделать еще один шаг.
Преобразование шагов в алгоритм
Нетрудно разглядеть постепенно проявляющуюся закономерность. Мы многократно выполняем действия, которые указаны ниже.
1. Начать с текущей ставки current_rate и размера шага step_size.
2. Вычислить производную максимизируемой функции в точке current_rate.
3. Прибавить к текущей ставке величину step_size*revenue_derivative(current_rate) для получения нового значения current_rate.
4. Повторять шаги 2 и 3.
В этой схеме не хватает только одного: правила остановки, то есть правила, срабатывающего при достижении максимума. На практике весьма вероятно, что мы будем приближаться к максимуму асимптотически, то есть подходить к нему все ближе и ближе, но всегда оставаясь на микроскопическом расстоянии от него. Итак, мы, возможно, никогда не достигнем максимума, но можем подойти достаточно близко к нему с точностью до 3-го, 4-го и даже 20-го знака в дробной части. Мы узнаем, что подошли достаточно близко к асимптоте, если размер приращения очень мал. Соответствующее значение можно задать в программе Python:
threshold = 0.0001
Процесс должен остановиться, когда ставка изменяется на величину, которая меньше порога threshold при каждой итерации процесса. Возможно и то, что процесс пошагового приближения вообще не сойдется к искомому максимуму, поэтому простой цикл может выполняться бесконечно. Чтобы подготовиться к этой возможности, мы зададим максимальное количество итераций, и если количество выполненных приближений достигнет этой величины, то программа просто отказывается от дальнейших попыток и останавливается.
Теперь все фрагменты можно собрать воедино (листинг 3.1).
Листинг 3.1. Реализация градиентного подъема
threshold = 0.0001
maximum_iterations = 100000
keep_going = True
iterations = 0
while(keep_going):
rate_change = step_size * revenue_derivative(current_rate)
