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

Листинг 3.2. Реализация градиентного подъема для максимизации заработка (вместо поступлений в бюджет)

def income_derivative(edu_yrs):

    return(math.cos((edu_yrs - 10.6) * (2 * math.pi/4)) + 1/2)

threshold = 0.0001

maximum_iterations = 100000

current_education = 12.5

step_size = 0.001

keep_going = True

iterations = 0

while(keep_going):

    education_change = step_size * income_derivative(current_education)

    current_education = current_education + education_change

    if(abs(education_change) < threshold):

        keep_going = False

    if(iterations >= maximum_iterations):

        keep_going=False

    iterations = iterations + 1

Код в листинге 3.2 реализует точно такой же алгоритм градиентного подъема, как алгоритм максимизации налоговых поступлений, который был реализован ранее. Отличается только кривая, с которой мы работаем. Кривая ставки налога/поступ­лений имела один глобальный максимум, который к тому же был единственным локальным максимумом. С другой стороны, кривая образования/заработка сложнее: она имеет глобальный максимум, но также несколько локальных максимумов (локальных пиков), которые ниже глобального максимума. Мы должны задать производную кривой (в первых строках листинга 3.2), используется другое исходное значение (12,5 лет вместо 70 % ставки налога, и переменным присвоены другие имена (current_education вместо current_rate). Тем не менее все эти различия поверхностны; по сути происходит то же самое: мы делаем несколько шагов в направлении градиента к максимуму, пока не будет достигнута подходящая точка остановки.

В результате процесса градиентного подъема будет сделан вывод, что этот человек излишне образован, и в действительности максимальный доход достигается приблизительно при 12 годах образования. Если действовать слишком наивно и чрезмерно доверять градиентному подъему, то можно порекомендовать первокурснику колледжа бросать учебу и немедленно браться за работу, чтобы обес­печить максимальный заработок в этом локальном максимуме. К этому выводу уже приходили некоторые студенты, когда видели, что их друзья после школы начинали зарабатывать больше них, работавших на свое неопределенное будущее. Очевидно, этот вывод ошибочен; процесс градиентного подъема нашел вершину локального «холма», но не глобальный максимум. Процесс градиентного подъема удручающе локален: он взбирается только на ту вершину, возле которой уже находится, и не способен сделать несколько временных шагов вниз ради того, чтобы подняться на другой «холм» с более высокой вершиной. У этого процесса есть аналогии в реальной жизни: например, некоторые люди не получают университетский диплом, поскольку это помешает им зарабатывать в ближайшем будущем. Они не учитывают, что их долгосрочный заработок только увеличится, если они перейдут от локального максимума к другой вершине (следующей, более высокой ступени).

Локальные экстремумы — сложная задача, и идеального ее решения не существует. В одном из подходов к ее решению алгоритм пытается сделать несколько начальных предположений и проводит процедуру градиентного подъема для каждого из них. Например, если выполнить градиентный подъем для 12,5, 15,5 и 18,5 лет обучения, то мы получим три разных результата. Сравнивая их, можно увидеть, что глобальный максимум достигается при максимальной продолжительности образования (по крайней мере, на этой шкале).

Это разумный подход к решению проблемы локальных экстремумов, но многократное проведение градиентного подъема для получения правильного результата может занять слишком много времени, и правильный ответ не гарантирован даже при сотне попыток. Очевидно, лучший способ предотвратить эту проблему — внести некоторую степень случайности в процесс, чтобы мы могли иногда сделать шаг, который ведет к локально худшему решению, но в долгосрочной перспективе может привести к лучшему максимуму. Улучшенная версия градиентного подъема, называемая стохастическим градиентным подъемом, внедряет в этот процесс случайность, другие алгоритмы (такие как метод имитации отжига) делают то же самое. Метод моделирования отжига и проблемы, связанные с нетривиальной оптимизацией, рассматриваются в главе 6. А пока учтите, что при всей своей эффективности градиентный подъем всегда будет сталкиваться с проблемами, связанными с локальными экстремумами.

От максимизации к минимизации

До настоящего момента мы старались максимизировать некоторую величину, то есть подниматься по «склону» вверх. Разумно задаться вопросом, потребуется ли когда-нибудь пойти в обратную сторону, и что-то минимизировать (например, затраты или ошибку). Можно подумать, что для минимизации потребуется совершенно новый набор приемов или что существующие приемы необходимо перевернуть с ног на голову либо применить в обратном порядке.

На самом деле переход от максимизации к минимизации достаточно прост. Как вариант, можно «перевернуть» функцию, или, говоря точнее, использовать инвертированную функцию. Возвращаясь к примеру с кривой ставки налога/поступлений, для этого достаточно определить новую инвертированную функцию: