Kitobni o'qish: «Алгоритмы для жизни: Простые способы принимать верные решения»

Переводчик М. Волохова

Редактор Д. Сальникова

Руководитель проекта М. Шалунова

Корректоры О. Гриднева, Н. Витько

Компьютерная верстка А. Абрамов

Дизайн обложки Ю. Буга

© Brian Christian, Tom Griffiths, 2016

All rights reserved

© Издание на русском языке, перевод, оформление. ООО «Альпина Паблишер», 2017

Все права защищены. Произведение предназначено исключительно для частного использования. Никакая часть электронного экземпляра данной книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, включая размещение в сети Интернет и в корпоративных сетях, для публичного или коллективного использования без письменного разрешения владельца авторских прав. За нарушение авторских прав законодательством предусмотрена выплата компенсации правообладателя в размере до 5 млн. рублей (ст. 49 ЗОАП), а также уголовная ответственность в виде лишения свободы на срок до 6 лет (ст. 146 УК РФ).

* * *

Нашим семьям

Введение
Алгоритмы для жизни

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

Жестокие законы рынка не оставляют возможности для принятия взвешенного решения (а именно такие решения должны бы принимать рациональные потребители). В отличие от, скажем, покупателя в торговом центре или интернет-магазине, потенциальный житель Сан-Франциско должен решать мгновенно: либо соглашаться на апартаменты еще при осмотре, отметая при этом другие варианты, либо уходить и не возвращаться.

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

Так что же делать? Каким образом вы примете взвешенное решение, если сам факт обдумывания ставит под угрозу результат? Запутанная ситуация, граничащая с абсурдом.

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

Но, к счастью, есть ответ.

Тридцать семь процентов.

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

Это не просто компромисс между тем, чтобы отмерить и отрезать. Это обоснованно оптимальное решение.

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

Поиски квартиры – всего лишь один из примеров ситуации, где работает принцип оптимальной остановки. Решение придерживаться или не придерживаться определенной последовательности действий становится своего рода неотъемлемым элементом нашей повседневной жизни, возникая снова и снова в той или иной ипостаси.

Сколько раз следует объехать квартал, чтобы найти подходящее место для парковки?

Как долго стоит испытывать удачу в рискованном предприятии, прежде чем забрать свою долю?

Сколько ждать лучшего предложения на этот дом или автомобиль?

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

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

Алгоритм же подсказывает, что этот баланс и есть 37 %.

Существует определенный набор проблем, с которыми сталкиваются все, – проблем, которые обусловлены непосредственно тем фактом, что наша жизнь ограничена определенным пространством и временным отрезком. Что мы должны сделать, а за что лучше не браться сегодня или через 10 лет? До какой степени стоит пустить все на самотек и как понять, что упорядоченность становится чрезмерной? Где находится баланс между привнесением в жизнь нового опыта и следованием излюбленным привычкам, который поможет взять от жизни все?

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

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

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

Тем не менее алгоритм – это всего лишь ограниченная последовательность шагов, которая используется для решения какой-либо задачи. Задолго до того, как алгоритмы стали задействоваться в программировании, их начали применять люди.

Само слово «алгоритм» произошло от имени математика персидского происхождения аль-Хорезми – автора пособия по решению математических задач, написанного им в IX веке. Его книга называлась «Китаб аль-джебр ва-ль-мукабала». Известно, что современное слово «алгебра» произошло как раз от части названия книги – «аль-джебр».

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

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

В этой книге мы рассмотрим идею разработки алгоритмов для нашей жизни и найдем лучшие решения для задач, с которыми все мы сталкиваемся ежедневно.

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

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

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

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

Проще говоря, взгляд через призму компьютерной науки может раскрыть нам природу человеческого разума, значение понятия рациональности и ответить на извечный вопрос – «как жить?». Изучение мыслительных процессов человека как средства решения фундаментальных вычислительных задач, которые ставит перед нами жизнь, может в корне изменить наше представление о человеческой рациональности.

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

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

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

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

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

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

Решения повседневных задач, позаимствованные из компьютерной науки, расскажут совсем другую историю о человеческом разуме. Жизнь полна задач – и достаточно сложных. И ошибки, допускаемые людьми, зачастую говорят скорее об объективной сложности той или иной задачи, нежели о несовершенстве человеческого мозга. Алгоритмическое осмысление мира, изучение фундаментальных структур задач, с которыми мы сталкиваемся, и способов их решения поможет нам заново оценить свои сильные стороны и понять допускаемые ошибки.

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

И все же жить по заветам компьютерной науки не так уж и плохо. Ведь, в отличие от большинства советов, ее мудрость имеет обоснования.

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

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

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

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

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

1. Задача об оптимальной остановке
Когда пора остановить поиски

Хотя все христиане пишут в свадебных приглашениях, что брак их совершился по воле Божьей, я, будучи философом, готов поспорить с этим утверждением…

Иоганн Кеплер

Ежели мистер Мартин любезнее вам всякого другого мужчины, ежели никогда и ни с кем не было вам так приятно, как в его обществе, тогда зачем колебаться?

Джейн Остин. Эмма¹

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

Однажды к психологу на прием пришел Брайан, крайне возбужденный первокурсник. Его школьная подружка уехала учиться в другой колледж, и теперь у них был классический роман на расстоянии. Кроме того, их мучил непростой философский вопрос: а хорошие ли у них отношения? Сравнивать им было не с чем. Психолог посочувствовала Брайану, сказала, что это типичная дилемма первокурсников, и невозмутимым тоном предложила удивительное: «Собирай данные».

Сторонники серийной моногамии, как правило, сталкиваются с фундаментальной неизбежной проблемой. Когда можно считать, что вы познакомились с достаточным количеством людей, чтобы найти свою половинку? А что, если вы уже пропустили ее? Настоящая «уловка-22» в любовных делах!

Ответ на крик души этого влюбленного первокурсника содержится в теории, которую математики называют «задачей об оптимальной остановке». И звучит он так: 37 %.

Ну или как-то иначе. Все зависит от ваших взглядов на любовь.

Задача о секретаре

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

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

Считается, что задача о секретаре впервые была опубликована (без непосредственного упоминания секретарей) в февральском номере журнала Scientific American в 1960 году Мартином Гарднером в качестве одной из головоломок в его популярной колонке о занимательной математике. Однако само происхождение задачи остается загадкой. Наше собственное расследование с нуля привело нас к некоторой гипотезе еще до того, как оно неожиданно превратилось для нас в детективную работу в прямом смысле слова. Мы отправились в Стэнфорд, чтобы в архивах работ Гарднера найти его переписку середины прошлого века. Чтение писем немного напоминает подслушивание чужого телефонного разговора: вы слышите только одну сторону диалога, а ответ можете лишь предположить. В нашем случае у нас были только ответы на вопросы, которыми, очевидно, задавался сам Гарднер более 50 лет назад, исследуя историю происхождения задач. Чем больше мы читали, тем более запутанной и неясной казалась нам эта история. Гарвардский математик Фредерик Мостеллер вспомнил, что слышал об этой задаче в 1955 году от своего коллеги Эндрю Глизона, который, в свою очередь, слышал о ней от кого-то еще. Лео Мозер из Альбертского университета рассказывал в своем письме, что читал о головоломке в «неких записях» Р. И. Гаскелла из компании Boeing, который приписывал авторство задачи своему коллеге. Роджер Пинкхам из Ратгерского университета писал, что впервые услышал о головоломке в 1955 году от математика по фамилии Шонфильд из Университета Дьюка, а тот, по его убеждению, сам впервые услышал о задаче от кого-то из Мичигана. Этот «кто-то из Мичигана», с большой вероятностью, носил имя Меррил Флад. И хотя за пределами мира математики его имя мало кому известно, влияние Флада на развитие компьютерной науки нельзя не отметить. Именно он обратил внимание на задачу о коммивояжере (которую мы обсудим более подробно в главе 8), изобрел математическую игру «Два бандита» (которая будет описана в главе 11) и даже, весьма вероятно, ввел термин «программное обеспечение». По его же собственным словам, Флад приступил к изучению вопроса в 1949-м и в 1958 году стал автором своего первого известного открытия – правила 37 %. Хотя он и отдает пальму первенства в этом вопросе другим математикам.

Достаточно будет отметить, что вне зависимости от своего происхождения задача о секретаре оказалась едва ли не идеальной математической загадкой: ее легко объяснить, очень сложно решить, решение ее чрезвычайно лаконично, а выводы крайне занимательны. В результате она передавалась из уст в уста в математических кругах в 50-е годы, распространяясь со скоростью лесного пожара, и только благодаря Гарднеру и его колонке в 1960 году захватила воображение широкой общественности. К 80-м задача и различные ее вариации столько раз подвергались анализу, что ее стали обсуждать в газетах как подраздел самой себя.

А что до секретарей, довольно умилительно наблюдать, как каждая культура накладывает свой особый антропологический отпечаток на формальные системы. К примеру, при мысли о шахматах нам представляется средневековая Европа, хотя на самом деле появились шахматы в VIII веке в Индии. Они были достаточно грубо «европеизированы» в XV веке, когда «шахи» были переименованы в «королей», «визири» – в «королев», а «слоны» стали «офицерами».

Аналогичным образом менялись и задачи об оптимальной остановке, отражая насущные проблемы и переживания каждого поколения. В XIX веке типичными ситуациями для таких задач были барочные лотереи или выбор подходящего поклонника для дамы; в начале XX века – поиск лучшего отеля для автопутешественника и выбор подходящей спутницы для мужчины; в середине XX века, во время расцвета офисной рутины и доминирования мужчин, – подбор лучшей секретарши для руководителя-мужчины. Впервые название задачи о секретаре именно в такой формулировке было упомянуто в газете в 1964 году, позднее оно закрепилось окончательно.