Алгоритмы неформально. Инструкция для начинающих питонистов - [20]

    rate_change = step_size * revenue_derivative(current_rate)

    current_rate = current_rate + rate_change

    if(abs(rate_change) < threshold):

        keep_going = False

    if(iterations >= maximum_iterations):

        keep_going = False

    iterations = iterations+1

После выполнения кода выясняется, что ставка налога, максимизирующая поступ­ления в бюджет, составляет около 0.528. Схема, реализованная в листинге 3.1, иногда называется градиентным подъемом. Она так названа из-за того, что алгоритм используется для подъема к максимуму, а направление движения определяется вычислением градиента. (В двумерном случае, как в нашей задаче, градиент называется производной.) Мы можем полностью перечислить все действия, которые были выполнены выше, включая описание критерия остановки.

1. Начать с текущей ставки current_rate и размера шага step_size.

2. Вычислить производную максимизируемой функции в точке current_rate.

3. Прибавить к текущей ставке величину step_size*revenue_deriva­tive(current_rate) для получения нового значения current_rate.

4. Повторять шаги 2 и 3, пока не подойдем к максимуму настолько близко, что изменение ставки налога на каждом шаге будет меньше очень малого порога или пока не будет выполнено достаточно большое количество итераций.

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

Аргументы против градиентного подъема

Мы только что воспользовались градиентным подъемом для максимизации доходов гипотетического правительства. У многих людей, освоивших градиентный подъем, возникали практические, если не моральные, возражения против этого метода. Ниже приведены аргументы, которые обычно выдвигаются против градиентного подъема:

• он не нужен, поскольку максимум можно найти визуально на графике;

• он не нужен, так как максимум можно найти с помощью стратегии предположений и проверок;

• он не нужен, поскольку его можно заменить решением условий первого порядка.

Рассмотрим все эти возражения по очереди. Визуальная проверка уже обсуждалась ранее. Для кривой ставки налога/бюджетных поступлений легко получить примерное представление о максимуме, просто взглянув на график. Однако визуальный анализ графика не дает высокой точности. Что еще важнее, наша кривая была чрезвычайно простой: она строилась в двух измерениях и на ней очевидно был только один максимум в интересующем нас диапазоне. Если представить себе более сложные функции, вы начнете видеть, почему визуальный метод нельзя признать удовлетворительным способом поиска максимума функции.

Для примера возьмем многомерный случай. Если экономисты сделали вывод, что бюджетные поступления зависят не только от ставки налога, но и от таможенных пошлин, то кривую пришлось бы строить в трех измерениях, а для комплексной функции (complex function) будет еще сложнее увидеть, где лежит максимум. А если экономисты создадут функцию, которая связывает 10, 20 или 100 факторов для вычисления ожидаемых поступлений, то нарисовать график для всех факторов будет вообще невозможно. Если вы не можете даже нарисовать кривую поступлений, то визуальный метод никак не позволит найти на ней максимум. Визуальный метод хорошо подходит для простых учебных примеров вроде кривой ставки/поступлений, но не для комплексных многомерных задач. Помимо прочего, построение графика кривой требует вычисления значения функции в каждой отдельной точке интересующего диапазона, поэтому всегда занимает больше времени, чем выполнение хорошо написанного алгоритма.

Может показаться, что градиентный метод усложняет задачу, а простой стратегии предположений и проверок будет достаточно для нахождения максимума. Стратегия предположений и проверок строится на попытках угадать потенциальный максимум и проверках того, превышает ли он все ранее предложенные потенциальные максимумы, пока вы не будете уверены в том, что максимум найден. Один возможный ответ указывает на то, что, как и в случае с визуальным методом, с многомерными функциями высокой сложности метод предположений и проверок становится неприемлемо сложным для успешной реализации на практике. Но лучший ответ на идею поиска максимума с помощью метода предположений и проверок заключается в том, что градиентный подъем именно это и делает. Градиентный подъем уже является стратегией предположений и проверок, но стратегией управляемой в том отношении, что предположения определяются направлением градиента, а не случайными догадками. Градиентный подъем — всего лишь более эффективная версия предположений и проверок.

Наконец, рассмотрим идею решения условий первого порядка для нахождения максимума. Этот метод преподают на курсах математического анализа по всему миру. Его можно назвать алгоритмом, и он состоит из шагов, которые перечислены ниже.