Текст книги "Алгоритмы для жизни: Простые способы принимать верные решения"

Исследовать/эксплуатировать

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

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

Но более того – исследование может быть проклятием.

Что, например, хорошо в музыке: всегда есть что-то новенькое, чтобы послушать. А что ужасно в музыке, если ты, к примеру, музыкальный обозреватель, так это то, что всегда есть что-то новенькое, чтобы послушать. Быть музыкальным обозревателем означает, что ты можешь исследовать материал сутками и все равно останется пара новых непрослушанных композиций. Любители музыки сочтут работу в музыкальной журналистике раем, но, когда тебе приходится постоянно исследовать новое, у тебя не остается возможности насладиться плодами своего профессионализма. А это своего рода ад. Мало кто разбирается в этом столь же глубоко, как Скотт Плагенхоф, бывший главный редактор журнала Pitchfork. «Во время работы ты пытаешься найти время послушать то, что тебе хочется, а не то, что нужно», – говорит он о жизни музыкального критика. Его отчаянное желание прекратить продираться сквозь дебри непрослушанных мелодий сомнительного качества и просто слушать любимую музыку было столь сильным, что он нарочно скачивал в свой iPod только новую музыку, чтобы было физически невозможно отказаться от выполнения своих обязанностей в те моменты, когда ему больше всего на свете хотелось послушать The Smiths. Журналист, таким образом, является мучеником, исследующим, чтобы другие могли эксплуатировать.

В информатике связь между исследованием и эксплуатацией наиболее ярко отражается в сценарии под названием «проблема многорукого бандита». Это странное название произошло от разговорного термина, обозначающего вид игровых автоматов, – «однорукий бандит». Представьте, что вы входите в зал казино, полный разных игровых автоматов, каждый из которых дает шанс на выигрыш. Закавыка в том, что вы не знаете ничего об этих шансах заранее: пока вы не начнете играть, вы не поймете, какие автоматы наиболее прибыльные («многоиграющие», как говорят игроманы), а какие только вытянут из вас все денежки.

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

Для понимания всех тонкостей данной задачи представьте, что у вас есть только два игровых автомата. На одном из них вы сыграли 15 раз; 9 раз он выдал вам выигрыш, а 6 раз – нет. На другом вы сыграли всего дважды; один раз выиграли и один раз проиграли. Какой из автоматов перспективнее?

Просто разделите количество выигрышей на общее количество раз, что вы дернули ручку, и вы получите «ожидаемую выгоду». Согласно этому способу, первый автомат явно лидирует. Его соотношение 9: 6 дает нам 60 % ожидаемой выгоды, в то время как у второго соотношение 1: 1 дает всего 50 %. Но это еще не все. В конце концов, всего две игры – это не слишком показательно, и можно предположить, что мы просто пока не знаем, насколько хорош второй автомат.

Выбор ресторана или музыкального альбома по сути своей – это тот же выбор, за какую ручку дернуть в жизненном казино. Но поиск компромисса между «исследовать» и «эксплуатировать» – это не просто более легкий способ принять решение, где поужинать или какой диск послушать. Он дает нам базовое представление о том, как наши цели должны меняться с годами и почему наиболее рациональный принцип действий не всегда подразумевает выбор самого лучшего. И это, как выясняется, составляет самую суть процессов веб-дизайна и клинических исследований – двух понятий, которые обычно не встречаются в одном предложении.

Люди склонны раздумывать над решениями в одиночестве, чтобы сосредоточиться и понять, какое из них принесет в результате наибольшую ожидаемую выгоду. Но так редко получается на практике, да и ожидаемая выгода – еще не конец истории. Если вы размышляете не только над вашим следующим шагом, но и над всеми теми шагами, которые вы предпримете в аналогичных обстоятельствах в будущем, то соблюдение баланса «исследовать/эксплуатировать» имеет решающее значение. В этом случае, как пишет математик Питер Уиттл, проблема многорукого бандита «воплощает в себе самую суть конфликта, проявляющегося в любой деятельности человека».

Так какой же из двух рычагов дернуть? Вот тут и кроется подвох. Это целиком и полностью зависит от того, что мы еще не обсудили: как долго мы вообще собираемся оставаться в казино.

Поймай интервал

«Лови мгновение», – призывает Робин Уильямс в одной из самых памятных сцен в фильме «Общество мертвых поэтов» (1989). «Ловите мгновение, мальчики! Пусть ваша жизнь будет необыкновенной!»

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

«Я скорее пойду в новый ресторан, когда я только приехал в город, нежели когда я уже покидаю его», – рассказывает специалист по обработке и анализу данных и блогер Крис Стуккио, ветеран боев за компромисс «исследовать/эксплуатировать» как в работе, так и в жизни. «Сейчас я в основном посещаю рестораны, которые давно знаю и люблю, потому что собираюсь вскоре покинуть Нью-Йорк. При этом, когда я пару лет назад переехал в Индию, в город Пуна, я был готов поесть в любой чертовой забегаловке, лишь бы она не выглядела так, словно меня там собираются отравить! И когда я собрался уезжать, я ходил по старым проверенным местам вместо того, чтобы исследовать новые… Даже если бы я нашел местечко получше, я бы смог побывать там всего раз или два. Так зачем рисковать?»

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

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

Интересно отметить, что раз стратегия определяется интервалом, то, наблюдая за стратегией, мы можем определить этот интервал. Возьмем, к примеру, Голливуд: среди десяти самых кассовых фильмов 1981 года только два были сиквелами. В 1991-м – три. В 2001-м – уже пять. А в 2011-м восемь из десяти самых кассовых фильмов оказались сиквелами! На самом деле 2011 год показал рекордный процент сиквелов от всех основных релизов киностудии. А следом 2012-й побил этот рекорд; и следующий год точно так же побьет рекорд предыдущего. В декабре 2012-го журналист Ник Аллен с заметным усталым равнодушием предсказывал наступление нового года:

Публике покажут шестую часть «Людей Икс», а заодно и «Форсаж-6», «Крепкий орешек – 5», «Очень страшное кино – 5» и «Паранормальное явление – 5». Также выйдет «Железный человек – 3», «Мальчишник в Вегасе – 3» и вторые части «Маппетов», «Смурфиков», «Броска кобры» и «Плохого Санты».

С точки зрения киностудии, сиквел – это фильм с гарантированной аудиторией поклонников: дойная корова, беспроигрышное дело. Но перегрузка этими «верняками» – недальновидный подход, как и у Стуккио с его отъездом из города. Сиквелы скорее, чем абсолютно новые фильмы, станут хитами этого года, но откуда брать следующие желанные серии в будущем? Это наводнение сиквелами не только прискорбно (как полагают критики), но и несколько мучительно. Входя в фазу чистейшей воды эксплуатации, киноиндустрия, кажется, подходит к концу своего интервала.

И беглый анализ экономики Голливуда подтверждает эту догадку. Прибыль крупнейших киностудий к 2011 году упала на 40 % по сравнению с 2007-м, а продажи билетов снизились в 7 раз за последние 10 лет. Как выразились в журнале The Economist, «зажатые между ростом расходов и падением доходов, крупные киностудии ответили на вызов выпуском новых фильмов, которые, по их мнению, должны стать хитами: обычно сиквелов, приквелов или чего-то с участием узнаваемых персонажей». Другими словами, они дергают за рычаги лучших игровых автоматов, пока их не вышвырнули из казино.

Закрепи победу

Поиск оптимальных алгоритмов, которые подсказали бы нам, как укротить «многорукого бандита», оказался весьма сложной задачей. Как рассказывает Питер Уиттл, в ходе Второй мировой войны попытки решить данную задачу «настолько подорвали силы и умы союзников… что было выдвинуто предложение подкинуть Германии эту проблему как самый действенный способ интеллектуальной диверсии».

Первые шаги к решению были предприняты годы спустя после войны, когда колумбийский математик Герберт Роббинс продемонстрировал, что существует простая стратегия, которая хоть и не идеальна, но дает некоторые гарантии. Роббинс предметно рассмотрел тот случай, когда у нас ровно два игровых автомата, и предложил способ под названием «победил – закрепи результат, проиграл – переключись»: выберите наугад любой рычаг и дергайте его до тех пор, пока автомат выдает деньги. Если после определенного рывка автомат не выдал выигрыш, стоит перейти к другому автомату. И хотя эта простая стратегия далека от оптимального решения, Роббинс в 1952 году доказал, что работает она куда лучше случайности.

Вслед за Роббинсом некоторые исследователи дальше занялись изучением принципа «оставайся победителем». Ясно, что если вы и так собирались дернуть за рычаг именно этого автомата, а он вдруг еще и выдал вам выигрыш, это немедленно увеличит его ценность в ваших глазах и вам будет хотеться и дальше дергать рычаг. И действительно, данный принцип оказывается элементом оптимальной стратегии балансирования между исследованием и использованием в широком диапазоне условий.

А вот «проиграл – переключись» – это уже совсем другая история. Менять рычаг каждый раз, как проиграешь, – довольно опрометчивый шаг. Допустим, вы посетили некий ресторан сто раз и всегда оставались довольны вкусной едой. Неужели одного-единственного разочарования будет достаточно, чтобы вы перестали туда ходить? Хорошие варианты не должны слишком строго караться за возможные несовершенства.

Что важно, принцип «победил – закрепи результат, проиграл – переключись» не имеет никакого отношения к промежутку времени, который вы пытаетесь оптимизировать. Если ваш любимый ресторан разочаровал вас в последнее посещение, данный алгоритм гласит, что вы должны отправиться на ужин в другое место – даже если это ваша последняя ночь в городе.

Таким образом, работа Роббинса о проблеме многорукого бандита дала старт появлению значительного количества прочей литературы на эту тему, и за последние годы исследователи добились существенного прогресса. Ричард Беллман, математик из корпорации РЭНД (RAND), нашел верное решение для случаев, когда мы заранее точно знаем, сколько всего шансов и возможностей у нас будет. Как и в ситуации с полной информацией в проблеме секретаря, трюк Беллмана заключался в том, чтобы на самом деле действовать от обратного, представив вначале последний рывок и предположив, какой из автоматов выбрать, учитывая все возможные результаты предыдущих решений. Выяснив это, уже можно переходить к предпоследнему варианту, потом к третьему с конца и т. д. до исходной точки старта.

Выводы, проистекающие из метода Беллмана, неоспоримы, но при большом количестве вариантов и длительном визите в казино он потребует головокружительного – или попросту невозможного – объема работы. Более того, даже если нам удастся просчитать все возможные расклады, мы все равно не будем знать точно, сколько возможностей (или хотя бы сколько способов) нам будет дано. По этим причинам проблема многорукого бандита так и остается нерешенной. По словам Уиттла, «она быстро стала классикой и синонимом неуступчивости».

Индекс Гиттинса

Как обычно бывает в математике, частное – это путь к общему. В 1970-х годах корпорация Unilever попросила молодого математика Джона Гиттинса помочь им оптимизировать некоторые клинические испытания их препаратов. И неожиданно получилось, что вместе с этим Гиттинс нашел ключ к математической загадке, которая оставалась нерешенной целым поколением.

Гиттинс, сегодня – профессор статистики в Оксфорде, размышлял над задачей, поставленной Unilever. При наличии нескольких химических соединений как быстрее всего определить, какое из них будет наиболее эффективным в борьбе с болезнью? Гиттинс попытался решить эту задачу наиболее общим способом: множественные варианты следования, разная вероятность вознаграждения за каждый из них и определенное количество усилий (или денег, или времени), которые будут между этими вариантами распределены. Это было, по сути, иное воплощение проблемы многорукого бандита.

И некоммерческие фармацевтические компании, и медицинские работники постоянно сталкиваются с противоречивыми требованиями соотношения «исследовать/эксплуатировать». Компании хотят вкладывать средства, выделяемые на научно-исследовательскую работу, в открытие новых лекарств, но в то же время желают быть уверены, что их уже существующие прибыльные производственные линии процветают. Доктора же хотят выписывать лучшие из существующих лекарств, чтобы их пациенты получали соответствующее лечение, но также хотят стимулировать экспериментальные разработки с тем, чтобы были созданы препараты, которые будут еще лучше.

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

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

С этим дисконтированием мы не раз сталкивались в жизни. В конце концов, если вы приезжаете в город на 10 дней, вы будете принимать решение о выборе ресторана, держа в уме именно этот временной промежуток; но если вы живете здесь постоянно, то это теряет смысл. Вместо этого вы можете представить себе ценность выгод, уменьшающихся в будущем: вас больше заботит, что съесть на ужин сегодня, а не что будет на ужин завтра, а завтрашний ужин – больше, чем тот, что состоится через год, особенно в зависимости от лично вашей «дисконтной функции». Гиттинс в свою очередь предположил, что ценность, приписываемая выгодам, уменьшается в геометрической прогрессии: каждый ваш визит в ресторан стоит некой относительной доли вашего предыдущего визита. Если, к примеру, вы допускаете, что ваш шанс в любой день быть сбитым автобусом равен 1 %, то вам нужно оценить ваш завтрашний ужин на 99 % от ценности сегодняшнего, потому что есть вероятность его не съесть.

В работе над этим предположением о дисконтировании в геометрической прогрессии Гиттинс изучал стратегию, которая, как он думал, «была бы по меньшей мере хорошим приближением»: думать о каждой «руке» многорукого бандита по отдельности и попытаться вычислить ее самостоятельную ценность. Объяснял он это на весьма забавном примере – на взятках.

В популярной телеигре «Сделка?!» участник выбирает один из 26 портфелей, в которых находятся призы от одного цента до миллиона долларов. По ходу игры таинственный персонаж по имени Банкир периодически звонит и предлагает участнику различные суммы, чтобы тот не открывал выбранный портфель. Задача участника – решить, какую названную Банкиром сумму предпочесть неизвестному призу в чемодане.

Гиттинс (пусть и за много лет до выхода в эфир первого выпуска игры) понял, что проблема многорукого бандита ничем не отличается. О каждом игровом автомате мы знаем крайне мало, а то и вовсе ничего, но есть некая гарантированная сумма выигрыша, которая, если нам предложат ее взамен игры на автомате, заставит нас больше никогда не дергать этот рычаг. Эта цифра, которую Гиттинс назвал «динамический индекс распределения» и которую весь мир знает сегодня как индекс Гиттинса, предлагает очевидную стратегию поведения в казино: всегда играйте на автомате с наивысшим индексом[6]6
  Краткое содержание данного фрагмента: делай ноги, пока Гиттинс хорош.


[Закрыть].

По факту стратегия индексирования оказалась удачной. Она полностью решает проблему многорукого бандита с геометрически дисконтированными выигрышами. Напряженные взаимоотношения между исследованием и эксплуатацией превращаются в более простую задачу по максимизации единственной величины, которая составляет долю и того и другого. Гиттинс скромно оценивает свои достижения: «Это, конечно, не великая теорема Ферма, – говорит он со смешком, – но это теорема, позволяющая решить ряд вопросов дилеммы "исследование/эксплуатация"».

Расчет индекса Гиттинса для конкретного агрегата, учитывая показатели его работы и нашу ставку дисконтирования, используется и сегодня. Но как только индекс Гиттинса для определенного набора предпосылок становится известен, он может в дальнейшем использоваться для решения всех задач такого плана. Примечательно, что количество рычагов не имеет значения, поскольку индекс для каждого рассчитывается отдельно.

В таблице ниже приведены значения индекса Гиттинса для девяти успехов и неудач с тем расчетом, что выигрыш в следующей игре будет стоить 90 % от выигрыша нынешнего. Эти значения могут использоваться для решения задач многорукого бандита в повседневных делах. Например, руководствуясь данными предположениями, вы должны выбрать тот игровой автомат, у которого результат прошлых игр 1: 1 (и ожидаемая ценность 50 %), а не тот, у которого результат 9: 6 (и ожидаемая ценность 60 %). Сравнение соответствующих значений в таблице показывает, что у менее известного автомата индекс 0,6346, а у другого индекс всего 0,6300. Проблема решена: испытай удачу в этот раз и исследуй.

Глядя на таблицу значений индекса Гиттинса, можно отметить несколько интересных моментов. Во-первых, наглядно показано, как работает принцип «оставайся победителем»: в любой строке слева направо значение индекса возрастает. То есть если вы выбрали автомат, дернули за рычаг и получили выигрыш, то (согласно таблице) имеет смысл снова дергать именно его. Во-вторых, можно увидеть, в каких случаях принцип «проиграл – переключись» может вас подвести. Девять выигрышей подряд и следующий за ними проигрыш дадут индекс 0,8695, который выше других значений в таблице, и, таким образом, вам нужно оставаться у этого автомата по меньшей мере еще на одну игру.

Но самое интересное в таблице можно увидеть в верхнем левом углу. Результат 0: 0 – у автомата, который совершенно неизвестен, – обладает ожидаемой ценностью в 0,5000, а индекс Гиттинса – 0,7029. Иными словами, нечто неизведанное не является более привлекательным, чем автомат, который, как вы уже знаете, выдает деньги в семи играх из десяти! Если посмотреть по диагонали вниз, можно заметить, что соотношение 1: 1 дает в итоге индекс 0,6346, соотношение 2: 2 дает индекс 0,6010 и т. д. Если тенденция к 50 %-ным выигрышам сохраняется, то мы в итоге приходим к индексу 0,5000, тогда как практика доказывает, что в автомате нет ровным счетом ничего особенного и он в итоге забирает тот «бонус», который подталкивает нас к дальнейшему исследованию. Но конвергенция происходит довольно медленно; азарт исследователя – это все же мощная сила. И действительно, смотрите: даже неудача с самой первой игры (соотношение 0: 1) имеет индекс по-прежнему выше 50 %.

Мы также можем заметить, насколько меняется баланс «исследовать/эксплуатировать» по мере того, как мы «обесцениваем» будущее. В следующей таблице представлена точно такая же информация, как в предыдущей, но предполагается, что последующий выигрыш стоит 99 % от нынешнего, а не 90 %. В будущем, продуманном столь же четко, как настоящее, ценность случайного открытия, относящегося к принятию беспроигрышных решений, возрастает еще больше. Здесь игра на абсолютно непроверенном автомате с результатом 0: 0 имеет 86,99 % гарантированного успеха!

Индекс Гиттинса, таким образом, дает нам формальное строгое обоснование, почему мы всегда предпочитаем узнавать нечто новое при условии, что у нас есть некоторая возможность воспользоваться результатами исследования. Старая пословица утверждает, что «по ту сторону забора трава всегда зеленее», а математика объясняет, почему это так: у неизведанного всегда есть шанс оказаться лучше, даже если мы не ожидаем особой разницы и даже если оно может оказаться хуже. Непроверенный новичок ценится больше (на ранних этапах, во всяком случае), чем ветеран с такими же, казалось бы, способностями именно потому, что о новичке мы меньше знаем. Исследование ценно само по себе, поскольку поиски нового увеличивают наши шансы найти лучшее. Таким образом, именно расчет на будущее, а не концентрация на сегодняшнем дне и побуждает нас к новшествам.

Из этого следует, что индекс Гиттинса предлагает удивительно простое решение проблемы многорукого бандита. Но это вовсе не обязательно ставит точку в данном вопросе или помогает нам ориентироваться во всех соотношениях исследования/эксплуатации в повседневной жизни. С одной стороны, индекс Гиттинса оптимален только при определенных строгих условиях. Он основан на обесценивании будущих выигрышей в геометрической прогрессии, оценивая каждый на долю меньше предыдущего, то есть делая ровно то, чего, согласно многочисленным исследованиям в области бихевиористской экономики и психологии, люди обычно не делают. Но если появляются затраты на переключение между разными вариантами, индекс Гиттинса перестает быть оптимальным. (Трава по ту сторону забора, может быть, и зеленее, но это не обязательно служит основанием для того, чтобы лезть через забор – не говоря уж о том, чтобы взять второй ипотечный кредит.) И, вероятно, еще более важно то, что индекс Гиттинса невозможно вычислить походя, на лету. Если вы постоянно таскаете с собой таблицу значений индекса, то вы, конечно, можете оптимизировать свой выбор кафе и ресторанов, но затраченные время и усилия могут не стоить того. («Погодите, сейчас я разрешу наш спор. Так, этот ресторан получил 29 хороших оценок из 35, а этот – 13 из 15, и, таким образом, индекс Гиттинса… Эй, а куда все ушли?!»)

C тех пор как был разработан индекс Гиттинса, этот подход заставил ученых-компьютерщиков и статистиков искать более простые и гибкие стратегии обращения с многорукими бандитами. Эти стратегии более удобны людям (и автоматам) для применения в различных ситуациях, чем напряженные подсчеты индекса Гиттинса, и при этом они обеспечивают сравнительно хорошие показатели работы. Кроме того, они борются с одним из главных человеческих страхов относительно принятия решений о том, какой шанс нельзя упустить.