Алгоритмы неформально. Инструкция для начинающих питонистов - [21]
1. Найти производную функцию, которую вы пытаетесь максимизировать.
2. Приравнять эту производную нулю.
3. Найти точку, в которой производная равна нулю.
4. Убедиться в том, что эта точка соответствует максимуму, а не минимуму.
(В многомерных задачах можно работать с градиентом вместо производной, а в остальном процесс остается тем же.) Этот оптимизационный алгоритм в принципе не плох, но найти аналитическое решение с нулевой производной (шаг 2) может быть трудно или невозможно, и может оказаться, что найти это решение будет сложнее, чем просто выполнить градиентный подъем. Кроме того, это может потребовать огромных вычислительных ресурсов, включая дисковое пространство, вычислительные мощности или время, и не все программные продукты наделены возможностями символической алгебры. В этом смысле градиентный подъем надежнее, чем данный алгоритм.
Проблема локальных экстремумов
Каждый алгоритм, который пытается найти минимум или максимум, сталкивается с очень серьезной потенциальной проблемой локальных экстремумов (локальных максимумов и минимумов). Вы можете идеально реализовать градиентный подъем, а потом осознать, что найденный пик оказался только «локальным» пиком — он выше любой точки в окрестностях, но не выше некоторого удаленного глобального максимума. Нечто похожее может произойти и в реальной жизни: вы пытаетесь взобраться на гору, находите пик, который выше всего вокруг, а потом понимаете, что это всего лишь предгорье, а настоящая вершина находится далеко и намного выше. Как ни парадоксально, вам придется немного спуститься, чтобы в итоге добраться до вершины, так что «наивная» стратегия градиентного подъема — постоянный подъем на более высокую точку в непосредственных окрестностях — не позволит добраться до глобального максимума.
Образование и пожизненный доход
Локальные экстремумы создают очень серьезную проблему для градиентного подъема. Например, рассмотрим задачу максимизации пожизненного дохода за счет выбора оптимального уровня образования. В данном случае можно предположить, что пожизненные заработки связываются с продолжительностью образования следующей формулой:
import math
def income(edu_yrs):
return(math.sin((edu_yrs - 10.6) * (2 * math.pi/4)) + (edu_yrs - 11)/2)
Здесь переменная edu_yrs представляет продолжительность обучения в годах, а income — оценка пожизненного дохода. Можно построить график, показанный ниже, с точкой для человека, учившегося в течение 12,5 лет, то есть того, кто окончил старшие классы общеобразовательной школы2:
import matplotlib.pyplot as plt
xs = [11 + x/100 for x in list(range(901))]
ys = [income(x) for x in xs]
plt.plot(xs,ys)
current_edu = 12.5
plt.plot(current_edu,income(current_edu),'ro')
plt.title('Education and Income')
plt.xlabel('Years of Education')
plt.ylabel('Lifetime Income')
plt.show()
Полученный график изображен на рис. 3.3.
Этот график, а также использованная для его генерирования функция, не основан на эмпирических исследованиях, а используется как чисто гипотетический пример. Он отражает интуитивные представления между образованием и доходом. Скорее всего, у человека, который не окончил старшие классы общеобразовательной
Рис. 3.3. Отношения между продолжительностью образования и пожизненным доходом
школы (менее 12 лет образования), пожизненный доход будет невысоким. Окончание старших классов — 12 лет — является важной вехой, которая гарантирует людям более высокие заработки по сравнению с доходами тех, кто не окончил школу. Другими словами, это максимум, но, что очень важно, максимум локальный. Тот, кто всего несколько месяцев проучился в колледже, вряд ли получит работу заметно лучшую, чем выпускник общеобразовательной школы. С другой стороны, посещая колледж в течение нескольких месяцев, человек упускает возможность зарабатывать в этот период. Так что его пожизненный заработок будет ниже, чем у тех, кто начинает работать сразу же после окончания школы.
Только через несколько лет обучения в колледже студент приобретает навыки, позволяющие ему заработать за жизнь больше, чем выпускнику школы (с учетом потерянного заработка за годы обучения). Затем выпускники колледжа (16 лет образования) оказываются на более высоком пике заработка, превышающем локальный пик дохода после общеобразовательной школы. Но и этот пик является только локальным. А если вы захотите получить чуть больше знаний, получив степень бакалавра, то оказываетесь в такой же ситуации, как при дополнительном образовании после школы: не получаете достаточно знаний для компенсации времени, в течение которого не зарабатывали. Со временем ситуация меняется, и после получения степени магистра появляется еще один пик. Дальнейшее развитие событий прогнозировать слишком сложно, но этого упрощенного представления о связи продолжительности образования и заработка будет достаточно для наших целей.
Правильный путь к вершинам образования
Для человека из нашего примера, отмеченного на графике как имеющего 12,5 лет образования, можно выполнить градиентный подъем точно так же, как объяснялось выше. В листинге 3.2 приведена слегка измененная версия кода градиентного подъема из листинга 3.1.
