Это база: Зачем нужна математика в повседневной жизни

3 Пусть голубь ведет автобус

Мо Виллемс рисовал забавные картинки с трехлетнего возраста. Опасаясь, что взрослые могут хвалить его не от чистого сердца, он начал писать смешные истории. Ему казалось, что фальшивый смех легче распознать. В 1993 году он присоединился к команде сценаристов и мультипликаторов классической «Улицы Сезам», что принесло ему за 10 лет шесть премий «Эмми». Главным героем его детского мультсериала «Баран в большом городе» стал баран по имени Баран, чья идиллическая жизнь на ферме рушится, когда тайная военная организация начинает гоняться за ним и ловить для создания лучевой пушки на бараньей силе. Первым опытом Виллемса в жанре детской книги стала книжка «Не позволяйте голубю вести автобус!», продолжавшая тему животных. Мультфильм по этой книге принес автору медаль Карнеги, а сама книга – премию Калдекотта, которую получают те, кто попадает в шорт-лист претендентов на медаль Калдекотта. Главный герой книги – голубь – использует все возможное и невозможное, пытаясь убедить читателя, что ему можно доверить управление автобусом, когда обычному водителю внезапно приходится покинуть транспортное средство.

В 2012 году книга Виллемса получила неожиданное научное продолжение – солидную статью в уважаемом журнале Animal Cognition, авторами которой стали заслуживающие доверия исследователи Бретт Гибсон, Мэттью Уилкинсон и Дебби Келли. Они экспериментально доказали, что голуби способны находить решения, близкие к оптимальным, для простых случаев известной математической диковинки – задачи коммивояжера. Их статья называлась «Позвольте голубю вести автобус: голуби способны планировать маршруты в помещении»{19}.

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

Задача коммивояжера – не просто любопытная диковинка. Это хороший пример целого класса задач, имеющих громадное практическое значение и известных как задачи комбинаторной оптимизации. У математиков есть привычка формулировать глубокие и значительные вопросы тривиальным на первый взгляд языком. Американские конгрессмены осудили напрасное расходование бюджетных денег на теорию узлов, не понимая, что эта область математики принципиально важна для понимания топологии малых размерностей, которая используется в теории ДНК и квантовой теории. Основные методы топологии включают в себя теорему о причесывании ежика и теорему о бутерброде, так что, я полагаю, мы сами на это напросились, но дело не только в нас. Я не осуждаю тех, кто чего-то не знает, – с каждым случается, – но почему бы этим людям просто не спросить?{20}

Как бы то ни было, та показательная чепуха, которая вдохновила меня на эту главу, берет свое начало в одной полезной книге для – как вы, наверное, уже догадались – коммивояжеров. Тех, что обходили дома и предлагали свой товар. Я еще помню их, даже если вы не помните. Они часто продавали пылесосы. Как любые разумные деловые люди, немецкие коммивояжеры в 1832 году (а в те времена все они, конечно, были мужчинами) очень трепетно относились к эффективности использования своего времени и снижению расходов. К счастью, помощь всегда была под рукой в виде руководства: «Коммивояжер. Каким ему следует быть и что ему следует делать, чтобы получать заказы и быть уверенным в успехе своего дела. Советы старого коммивояжера» (Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiss zu sein – von einem alten Commis-Voyageur). Этот пожилой странствующий торговец указывал, что:

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

Маршрут (1285 км) по 45 немецким городам из руководства 1832 года, показанный сплошными (толстыми и тонкими) линиями. Сплошными толстыми и пунктирными линиями показан кратчайший маршрут (1248 км), найденный современными методами

Задача коммивояжера – а именно такое название она получила – стала первым фундаментальным примером математической области, известной сегодня как комбинаторная оптимизация, что означает «нахождение лучшего варианта среди множества возможностей, слишком большого, чтобы проверять их последовательно». Забавно, но название «задача коммивояжера» не использовалось явно ни в одной публикации на эту тему до 1984 года[4], хотя в неформальных дискуссиях математиков оно вовсю фигурировало и до этого.

Несмотря на свое приземленное практическое происхождение, задача коммивояжера завела математическое сообщество в реальные глубины, вплоть до одной из «задач тысячелетия» «P ≠ NP?», приз за решение которой размером $1 млн до сих пор ожидает своего получателя. В задаче спрашивается в строгой математической форме: если имеется задача, предполагаемый ответ на которую – догадка, если угодно, – может быть эффективно проверен, то может ли этот ответ быть эффективно найден во всех случаях? Большинство математиков и компьютерщиков считают, что ответ должен быть «нет»: безусловно, проверка любой конкретной догадки может быть проведена намного быстрее, чем поиск корректного ответа. В конце концов, если кто-то показывает вам собранный пазл из 500 элементов, то быстрого взгляда, как правило, хватает, чтобы понять, все ли правильно собрано, но собрать весь пазл с самого начала – совершенно другое дело. К несчастью, пазлы не дают нам ответа: это всего лишь удобная метафора, строго говоря, они не имеют отношения к вопросу. Так что сейчас никто не может ни доказать, ни опровергнуть предположение о том, что P отличается от NP, – именно поэтому решение вопроса принесет вам круглую сумму $1 млн{21}. Я вернусь к задаче P ≠ NP позже, а сначала рассмотрим первые успехи в решении задачи коммивояжера.

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

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

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

Среди других применений можно назвать и эффективное прокладывание авиамаршрутов, и разработку и производство компьютерных микрочипов и печатных плат. Приближенные решения задачи коммивояжера используются для нахождения эффективных маршрутов доставки еды нуждающимся (программа Meals on Wheels) и оптимизации доставки крови в больницы. Один из вариантов задачи коммивояжера засветился даже в программе «Звездных войн» или, как ее правильнее называть, в гипотетической Стратегической оборонной инициативе президента США Рональда Рейгана, где мощный лазер, находящийся на околоземной орбите, должен был наводиться на ряд приближающихся ядерных ракет.

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

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

Одна из причин, по которым метод ближайшего соседа не работает. Начните с точки A и всегда переходите к ближайшей из точек, которые вы еще не посетили. Маршрут слева будет выглядеть как ABCDE. Однако маршрут справа – ACBDE – короче

Менгер шесть месяцев в 1930 и 1931 годах читал в Гарвардском университете лекции, часть из которых прослушал великий тополог Хасслер Уитни. Годом позже Уитни выступил с лекцией, где высказался о том, как следует подходить к поиску кратчайшего пути по всем 48 (на тот момент) штатам Америки. Некоторое время в математических кругах эту проблему называли «задачей 48 штатов», но потом кто-то придумал более изящное название «задача коммивояжера». В печати оно впервые было упомянуто в 1949 году в докладе Джулии Робинсон.

Менгер продолжал работать над задачей коммивояжера и родственными вопросами. В 1940 году Ласло Фейеш Тот заинтересовался, по существу, этой же задачей: нахождением кратчайшего пути через n точек единичного квадрата. В 1951 году Самюэл Верблунски доказал, что ответ составляет меньше чем 2 +√2 · 8n. Позже математики доказывали, что минимальная длина пути через n точек в фиксированной области не превышает определенной константы, умноженной на квадратный корень из n, причем величина константы с каждым разом все уменьшалась.

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

Первого по-настоящему значимого успеха в решении задачи коммивояжера добились в 1954 году исследователи RAND Данциг, Делберт Фалкерсон и Селмер Джонсон при помощи метода линейного программирования Данцига. Они адаптировали метод к решению именно этой задачи и предложили систематические новые методы, в частности использование «секущих плоскостей». В результате был найден нижний предел длины оптимального маршрута. Если вам удается находить маршрут лишь ненамного длиннее, то вы на правильном пути и внутреннее чутье не обманывает вас. Данциг, Фалкерсон и Джонсон воспользовались этими идеями, чтобы получить первое решение задачи коммивояжера для разумного числа городов, а именно найти кратчайший маршрут через 49 городов: по одному в каждом из 48 штатов США плюс столичный Вашингтон. Это, похоже, та самая задача, которую упоминал Уилкинсон в 1930-е годы, и определенно та самая, о которой писала Джулия Робинсон в 1949 году.

В 1956 году пионер исследования операций Меррилл Флуд заявил, что задача коммивояжера сложна. Возникает ключевой вопрос: насколько сложна? Чтобы ответить, мы должны вернуться к P и NP – показателям вычислительной сложности ценой миллион долларов. Похоже, что Флуд был прав, причем очень сильно.

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

Мой любимый пример – то, что я называю Шатром Матушки Мушки. Малышка Мушка парит в футе (в метре, в километре – на любой ненулевой высоте) над полом. Матушка Мушка хочет сшить шатер с основанием на полу, чтобы он прикрывал Малышку, и использовать при этом как можно меньше материи. Какой шатер имеет минимальную площадь? Если мы представим Малышку Мушку в виде точки, то ответ будет «такого шатра не существует». Сшить можно конический шатер любой ненулевой площади, если площадь нулевая, то это линия, а не шатер. Для любого заданного шатра существует другой, вдвое меньшей площади, который тоже выполняет свою задачу. Поэтому наименьшей площади не существует.

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

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

Главный вопрос звучит так: насколько быстро возрастает время вычислений (измеренное как число вычислительных шагов) в любом методе вычисления ответа в сравнении с объемом данных, необходимых для постановки задачи? То есть если для описания задачи необходимо n двоичных знаков, то как будет зависеть от n время вычислений? Для практичных алгоритмов время расчета обычно растет как степень n, скажем, n² или n³. Говорят, что эти алгоритмы выполняются за полиномиальное время. Символически их обозначают как класс P. Время выполнения непрактичных алгоритмов растет много быстрее, часто экспоненциально, как 2ⁿ или 10ⁿ. Алгоритм «просчитать все маршруты» для задачи коммивояжера примерно таков – он выполняется за факториальное время n!, которое растет быстрее любой экспоненты. В промежутке находится серая зона, где время выполнения больше любого полинома, но меньше экспоненты. Иногда такие алгоритмы практичны, иногда нет. В целях настоящей книги мы можем принять очень строгий взгляд и отправить их все в корзину с надписью «непрактичные».

Это не то же самое, что NP.

Эта аббревиатура обозначает куда более тонкое понятие: недетерминированное полиномиальное время. Это время выполнения алгоритма, который может решить, является ли каждое конкретное предложенное решение верным. Вспомним, что число называется простым, если не имеет других делителей, кроме 1 и самого себя, так что числа 2, 3, 5, 7, 11, 13 и т. д. являются простыми. В противном случае число называется составным. Так что 26 – составное число, поскольку равно 2 × 13. Числа 2 и 13 – простые сомножители числа 26. Предположим, что вы хотите найти простой делитель числа, состоящего из 200 десятичных знаков. Вы тратите год на безрезультатный поиск такого числа, а затем в отчаянии обращаетесь за советом к Дельфийскому оракулу. Оракул называет в качестве ответа конкретное большое число. Вы понятия не имеете, откуда оно взялось (в конце концов, оракул обладает волшебным даром предсказания), но вы можете сесть и подсчитать, действительно ли число, названное оракулом, разделит нацело то очень большое число, о котором шла речь. Такой расчет намного, намного проще, чем собственно поиск простого делителя.

Предположим, что всякий раз, когда оракул предлагает ответ, вы можете проверить его при помощи алгоритма с полиномиальным временем выполнения (P). Тогда сама задача относится к классу NP – недетерминированному полиномиальному. Задача оракула намного сложнее вашей, но вы всегда можете решить, верный ли ответ он вам дал.

Очевидно, что проверка предложенного ответа должна быть намного проще его отыскания. Проверить, спрятано ли сокровище в месте, отмеченном крестиком на карте, намного проще, чем выяснить, где этот крестик должен стоять. Или возьмем математический пример: почти все верят, что нахождение простых делителей намного сложнее, чем проверка, является ли делителем данное простое число. В пользу этого свидетельствует, в частности, то серьезное обстоятельство, что быстрые алгоритмы проверки любого предложенного делителя известны, а их поиска – нет. Если P = NP, то для любой задачи, имеющей быстро проверяемый ответ, найти ответ тоже быстро. Это звучит слишком хорошо, чтобы быть правдой, и опыт математиков в решении задач говорит прямо противоположное. Поэтому почти все убеждены, что P ≠ NP.

Однако все попытки доказать это – или опровергнуть – зашли в тупик. Вы можете доказать, что задача принадлежит к классу NP, записав детальный алгоритм и подсчитав время его выполнения, но для доказательства того, что задача не относится к классу P, вам придется рассмотреть все возможные алгоритмы ее решения и показать, что ни один из них не относится к классу P. Как это сделать? Никто не знает.

Из этих попыток проистекает тот любопытный факт, что в одну и ту же категорию попадает огромное число задач-кандидатов. Все эти задачи относятся к NP. Более того, если для какой-то из них можно доказать, что она не принадлежит P, то и все остальные не принадлежат P. Они живут или умирают вместе. Подобные задачи называют NP-полными. Связанную с ними более крупную категорию называют NP-трудными задачами: она состоит из алгоритмов, способных эмулировать решение любой NP-задачи за полиномиальное время. Если выяснится, что данный алгоритм выполняется за полиномиальное время, это автоматически докажет, что то же верно для любой NP-задачи. В 1979 году Майкл Гэри и Дэвид Джонсон доказали, что задача коммивояжера относится к классу NP-трудных{22}. Если P ≠ NP, то любой алгоритм для ее решения потребует время выполнения, превышающее полиномиальное.

Флуд был прав.

Это, впрочем, не повод опускать руки, потому что существует по крайней мере два потенциально возможных пути вперед.

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

В 1980 году рекорд составлял 318 городов; к 1987 году их уже было 2392. К 1994 году рекорд увеличился до 7397 городов и ответ потребовал около трех лет вычислительного времени сети очень мощных компьютеров. В 2001 году точное решение для 15 112 немецких городов было получено с использованием сети из 110 процессоров. На обычном настольном компьютере этот расчет занял бы более 20 лет. В 2004 году задача коммивояжера была решена для маршрута по 24 978 городам Швеции. В 2005 году группа Concorde TSP Solver решила задачу коммивояжера для маршрута по 33 810 точкам на печатной плате. Рекорды не единственный мотив для таких исследований: методы, использованные в рекордных достижениях, работают необычайно быстро при решении менее масштабных задач. Задачу при числе городов не более сотни обычно можно решить за несколько минут, а не более тысячи – за несколько часов на типовом настольном компьютере.

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

Один из методов поиска хороших, но не оптимальных решений задачи коммивояжера родился из таких глупых препятствий. Несколько десятилетий на переломе XIX и XX веков математика находилась в состоянии перехода. Царивший ранее авантюризм почти исчерпал себя, а игнорирование таких фундаментальных вопросов, как «о чем, собственно, идет речь?» и «действительно ли все так очевидно, как всем кажется?», сеяло смятение и растерянность там, где требовались ясность и понимание. Беспокойство по поводу таких продвинутых областей, как дифференциальное и интегральное исчисление, где математики легко и непринужденно разбрасывались бесконечными процессами, постепенно переходило с изотерических вещей на повседневные. Вместо сомнений в интегралах сложных математических функций вроде комплексного логарифма математики стали задаваться вопросом о том, что такое функция. Вместо того чтобы определять непрерывную кривую как кривую, которую можно «свободно нарисовать от руки», они стремились к большей строгости и обнаруживали ее отсутствие. Даже природа такого фундаментального и очевидного объекта, как число, вдруг оказалась весьма туманной. И речь здесь не только о новых конструктах, таких как комплексные числа: речь шла о добрых старых натуральных числах 1, 2, 3. Традиционная математика продолжала идти вперед, опираясь на предположение, что вопросы такого рода со временем непременно разъяснятся и все будет хорошо. Логический статус основ можно было без опаски оставить занудам и педантам. И все же… постепенно формировалось мнение о том, что такой неосмотрительный подход к дисциплине долго не продержится.

Дело по-настоящему осложнилось, когда прежние сумасбродные методы стали давать противоречащие друг другу ответы. Теоремы, издавна считавшиеся правильными, оказывались неверными в особых обстоятельствах. Интеграл, вычисленный двумя способами, давал разные ответы. Последовательности, сходившиеся, как считалось, при всех значениях переменной, иногда расходились. Конечно, все было не настолько плохо, как если бы вдруг обнаружилось, что 2 + 2 иногда равно 5, но все эти странности заставили некоторых ученых задуматься о том, что такое на самом деле 2 и 5, не говоря уже о знаках + и =.

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

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

Одно из наиболее фундаментальных свойств кривых, настолько очевидное, что никто даже не пытался в нем усомниться, состоит в том, что эти кривые тонкие. Как писал Евклид в «Началах», «линия – это то, что не имеет толщины». Площадь линии – просто линии, а не того, что она окружает, – очевидно, равна нулю. Но в 1890 году Джузеппе Пеано предложил способ построения непрерывной кривой, которая полностью заполняет внутренность квадрата{23}. Она не просто блуждает внутри квадрата, создавая сложные каракули и приближаясь к каждой точке: она проходит через каждую точку квадрата. Кривая Пеано «не имеет толщины» в том смысле, что вы проводите ее карандашом, кончик которого представляет собой единственную геометрическую точку, но эта линия блуждает по квадрату, раз за разом посещая те области, которые ранее покинула. Пеано понял, что если заставить эту линию бесконечно извиваться, причем определенным образом, то она полностью заполнит квадрат. При этом площадь кривой будет равна площади квадрата, то есть ненулевой.

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

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

Традиционалисты были заинтересованы в расширении границ и считали, что все в логическом саду чудесно, но новый скептицизм с его шквалом пугающих контринтуитивных явлений был необходимой реакцией на наивность. К 1930-м годам ценность этого более строгого подхода начала становиться очевидной, и к 1960-м годам он почти полностью взял верх. Можно написать целую книгу об этом периоде развития нашей дисциплины, и кое-кто уже так и поступил. Я же хочу сосредоточиться на непрерывных кривых и концепции размерности.

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

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

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

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

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

Третий из приведенных вопросов адресован скорее экспериментальной физике и ведет через Эйнштейна и его общую теорию относительности к предположению, что физическое пространство на самом деле не является плоским трехмерным пространством Евклида, а представляет собой его искривленную версию. Или, если правы сторонники теории струн, пространство-время имеет 10 или 11 измерений, которые, за исключением четырех, либо слишком малы, чтобы их заметить, либо недоступны. Первый и второй вопросы можно разрешить удовлетворительно, но далеко не тривиально – для этого надо определить евклидово пространство с точки зрения системы из трех координат, а затем посвятить пять или шесть недель университетского курса векторным пространствам, в которых бывает любое число координат, и доказать, что размерность любого векторного пространства единственна.

Подход, связанный с векторными пространствами, изначально подразумевает, что наша система координат построена на прямых линиях и что пространство плоское. В самом деле, ведь не случайно этот курс называется «линейной алгеброй». А что, если мы вслед за Эйнштейном позволим системе координат искривиться? Ну, если она искривляется гладко (в классической теории это называется «криволинейными координатами»), то все хорошо. Но в 1890 году итальянский математик Джузеппе Пеано обнаружил, что если она искривляется совершенно произвольно – настолько, что перестает быть гладкой, хотя остается непрерывной, – то пространство с двумя измерениями может иметь систему координат всего с одним числом. То же относится и к пространству с тремя измерениями. При таких более общих и гибких условиях число измерений неожиданно становится изменчивым.

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

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

Предположим, такая кривая существует. Тогда это не просто некая извилистая линия с собственной внутренней системой координат, показывающей, как далеко вдоль линии следует пройти. Чтобы обозначить это, достаточно одного числа, так что кривая одномерна. Раз эта извилистая линия проходит через каждую точку заполненного квадрата (объекта двумерного), то теперь мы можем обозначить каждую точку этого квадрата при помощи всего одного непрерывно меняющегося числа. Получается, что на самом деле квадрат одномерен!

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

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

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

Так или иначе, началось все с Кантора и с введенных им трансфинитных кардинальных чисел – средства оценки числа членов бесконечного множества. Он доказал, что одни бесконечности больше, чем другие. Точнее говоря, то, что между целыми и действительными числами нет взаимно однозначного соответствия. Занимаясь поисками трансфинитного кардинального числа, превышающего таковое для действительных чисел, он на какое-то время пришел к убеждению, что кардинальное число для плоскости больше, чем для прямой. В 1874 году он писал Рихарду Дедекинду:

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

Основная идея проста: задав две точки на единичном отрезке (между 0 и 1), мы можем записать их в десятичном виде как

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

образовав ее путем перемешивания десятичных знаков первых двух чисел, как при тасовке карт методом «рифл шафл», когда колоду делят на две части, а затем вставляют их друг в друга{24}. Разница состоит в том, что колода карт у Кантора бесконечна. Когда вы перемешиваете таким образом две бесконечные колоды, то получаете одну бесконечную колоду. Именно таким способом Кантор умудряется втиснуть две координаты в одну. Если первоначально измерения три, просто берется три колоды и т. д.

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

Идеи Кантора были противоречивы. Некоторые видные математики сочли их чепухой, наверное, потому, что они были слишком оригинальными. Другие, в первую очередь Гильберт, объявили новую область математики, открытую Кантором, настоящим «раем». Полное признание работы Кантора получили только после его смерти.

В 1879 году Ойген Нетто{25} ответил на один очевидный вопрос, доказав отсутствие непрерывного взаимно однозначного соответствия между единичным отрезком и заполненным единичным квадратом. Это сложнее, чем может показаться. Самый значительный прорыв произошел в 1890 году, когда Пеано показал, что наше интуитивное представление о непрерывной кривой может быть обманчивым.

В статье Пеано никаких рисунков нет. Он определяет кривую, записывая координаты точек единичного отрезка в троичной системе счисления, и его построение эквивалентно геометрическому построению на рисунке слева ниже{26}. В 1891 году Гильберт опубликовал еще один пример заполняющей пространство кривой, нарисовав что-то похожее на рисунок справа. Оба построения довольно сложны: на рисунках показана начальная стадия рекурсивного процесса, при котором простые многоугольники раз за разом заменяются более сложными. За прошедшее с тех пор время было найдено много других заполняющих пространство кривых.

Слева: начальный этап геометрической интерпретации заполняющей пространство кривой Пеано. Справа: начальный этап построения заполняющей пространство кривой Гильберта

Заполняющие пространство кривые применяются в компьютерных вычислениях, в частности при хранении и считывании многомерных данных{27}. Базовая идея состоит в том, что мы можем обходить многомерный массив по приближенной заполняющей пространство кривой, упрощая таким образом задачу и сводя ее к одномерному случаю. Еще одно практическое применение – это быстрое и приблизительное решение задачи коммивояжера. Идея заключается в наложении конечной аппроксимации заполняющей пространство кривой на область с городами, определении последовательности городов на кривой, а затем в посещении их в этом порядке, пользуясь на каждом этапе кратчайшим связующим путем. В результате получается маршрут, который обычно не более чем на 25 % превышает по длине оптимальный{28}.

Какие еще фигуры может заполнить кривая? Построение Гильберта можно расширить на три измерения, получив кривую, заполняющую единичный куб, а вообще, кривые могут заполнять гиперкубы любой размерности. Последнее слово в этом вопросе – теорема, которую доказали Ханс Хан и Стефан Мазуркевич. Она полностью характеризует топологические пространства, которые может заполнить кривая{29}. Как оказалось, эти пространства могут быть практически любыми при условии, что они компактны (имеют конечную протяженность) и удовлетворяют нескольким формальным условиям, позволяющим исключить всякие глупости.

Возможно, последнее слово все еще остается за коммивояжером. В 1992 году Санджив Арора и его коллеги{30} обнаружили, что класс сложности NP («легко проверяемые») обладает любопытным свойством, которое ставит под сомнение перспективы нахождения алгоритмов класса P («легко вычислимые»), дающих хорошие приближенные решения. Они доказали, что если P ≠ NP и размер задачи превышает пороговое значение, то вычислить хорошее приближение к ответу не проще, чем найти сам ответ. Единственной альтернативой этому выводу могло бы стать равенство P = NP, что могло бы принести доказавшим миллион долларов, но так и остается гипотезой.

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

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

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

Специалисты по информатике, изучающие машинную проверку доказательств, предложили совершенно иной подход: интерактивные доказательства. Вместо того чтобы представлять доказательство как повествование, написанное одним математиком и читаемое другим, этот подход превращает доказательство в диспут. Один математик, традиционно его называют Пат, хочет убедить Ванну в том, что его доказательство корректно. Ванна, напротив, хочет убедить его, что он ошибается. Они задают друг другу вопросы и дают на них ответы, пока один из них не уступит. (Пат Саджак и Ванна Уайт были ведущими популярного американского телешоу «Колесо фортуны».) Все это напоминает партию в шахматы, где Пат обещает «мат в четыре хода». Ванна не соглашается, так что Пат делает ход. Ванна ходит в ответ: «А что, если я пойду так?» И Пат делает следующий ход. Этот обмен репликами продолжается до тех пор, пока Ванна не проиграет. После этого она начинает отыгрывать назад. «А если бы мой последний ход был таким на самом деле?» Пат ходит по-другому, шах и мат! И так продолжается до тех пор, пока Ванна не исчерпает возможные ответы, а Пат не выиграет, или до тех пор, пока он не признает, что мат в четыре хода невозможен. Согласно моему опыту, именно так ведут себя настоящие математики, когда работают вместе над решением исследовательской задачи, и споры разгораются нешуточные. А нарратив нужен, чтобы представить окончательный результат на семинаре.

Ласло Бабаи и другие ученые ввели методы «диалогового» доказательства такого типа в концепцию прозрачного доказательства, использовав при этом такие математические инструменты, как многочлены над конечными полями и корректирующие коды{31}. После отладки этих методов выяснилось, что компьютеры способны использовать одно свойство, которое несовместимо с ясностью и лаконичностью, а именно избыточность. Оказывается, любое логическое доказательство можно переписать таким образом, что оно станет намного длиннее, но при этом и ошибка, если она в нем присутствует, проявится едва ли не всюду. Каждый логический шаг размазывается по всему доказательству в виде многочисленных взаимосвязанных почти идентичных копий. Это немного напоминает принцип голограммы, где изображение преобразуется так, что его можно восстановить по любой небольшой части данных. После этого доказательство можно проверить, взяв из него небольшой случайный образец. Ошибка почти наверняка окажется в нем. Сделайте это, и вы получите прозрачное доказательство. Интересующая нас теорема о невозможности существования приближенных решений класса P – следствие этой процедуры.

Вернемся к голубиной статье Гибсона, Уилкинсона и Келли в журнале Animal Cognition. Авторы начинают с замечания о том, что в последнее время задача коммивояжера используется для исследования некоторых аспектов когнитивных процессов у людей и животных, в первую очередь способности планировать действия до их осуществления. Однако долгое время было неясно, ограничивается ли эта способность приматами. Могут ли другие животные тоже планировать действия заранее, или они просто следуют жестким правилам, выработанным в процессе эволюции? Исследователи решили использовать голубей в лабораторных испытаниях с двумя или тремя точками-кормушками. Голуби стартуют из одного места, посещают все кормушки в каком-то порядке и улетают к финишу. Исследователи пришли к выводу, что «голуби отдавали предпочтение ближайшей локации, но, судя по всему, планировали на несколько шагов вперед, когда издержки неэффективного поведения очевидно возрастали. Результаты ясно свидетельствуют, что не только приматы способны планировать сложные маршруты передвижения».

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

Пусть голубь ведет автобус.

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

А может быть, и нет.

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

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

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

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

На приведенном рисунке слева и справа показаны кошки. Все очевидно. Изображения различаются всего несколькими пикселями и для нас выглядят совершенно идентичными. Стандартная нейросеть, натренированная на громадном количестве изображений кошек и некошек, верно распознает на левой картинке кошку. Однако она считает, что на картинке справа изображено гуакамоле – мексиканское блюдо из авокадо. Мало того, уверенность компьютера в том, что это гуакамоле, составляет 99 %, тогда как для кошки уверенность не превышает 88 %. Как говорится, компьютер – это устройство, способное очень быстро делать миллионы ошибок.

Изображения такого рода называют «состязательными», поскольку они появляются, когда кто-то пытается намеренно обмануть систему. На практике компьютер воспримет большинство подобных изображений как кошку. Кристиан Сегеди с коллегами обратил внимание на существование таких изображений в 2013 году{32}. В 2018 году Ади Шамир с коллегами{33} объяснил, почему в системах глубокого обучения могут возникать состязательные примеры, почему они неизбежны и почему достаточно изменить всего несколько пикселей, чтобы ввести нейросеть в заблуждение.

Корень такой восприимчивости к серьезным ошибкам кроется в размерности. Обычный способ измерения различия между двумя битовыми строками состоит в том, чтобы найти расстояние Хэмминга между ними: определить, сколько бит следует заменить, чтобы из одной строки получить другую. Так, расстояние Хэмминга между 10001101001 и 10101001111 равно четырем, и различают их выделенные жирным цифры: 10101001111. В компьютере любое изображение представлено в виде очень длинной битовой строки. Если изображение занимает 1 Мб (мегабайт), то длина этой строки составляет 2²³, или около 8 млн бит. Так что пространство изображений имеет размерность 8 млн над конечным полем, состоящим из 0 и 1. Оно содержит 2^{8 388 608} точек.

Алгоритм распознавания образов, воплощенный в обученной нейросети, должен поместить каждое изображение в этом пространстве в одну из гораздо меньшего числа категорий. В простейшем случае это сводится к рассечению пространства образа на отдельные области при помощи гиперплоскостей – эта процедура для двумерного пространства показана на рисунке ниже. Она делит пространство на множество сегментов, по одному на каждую категорию. Если мы меняем изображение на другое, отстоящее от него, скажем, на 40 единиц по Хэммингу, то на картинке изменяются всего 40 бит. Глаз воспринимает одновременно 8 млн бит, так что эти 40 бит составят всего лишь 0,0005 % от общего их числа – намного меньше порогового значения, при котором человек способен заметить какую-либо разницу. Однако число изображений на таком хэмминговском расстоянии от первого составляет 2⁵⁰, то есть около одного квадриллиона. Это намного больше, чем число категорий, которые способна различать система компьютерного зрения. Поэтому неудивительно, что такое небольшое изменение картинки может заставить компьютер ошибочно прочитать ее.

Рассечение пространства изображения гиперплоскостями. Пространство здесь двумерное, и пять гиперплоскостей (в данном случае, линий) разделяют его на 13 сегментов. Один из них закрашен

Для математического анализа удобно представлять битовые строки не над конечным полем, а в виде действительных чисел. Например, один байт, состоящий из восьми бит и равный, скажем, 10001101, можно рассматривать как действительное число с двоичной записью дробной части 0,10001101. В этом случае пространство всех изображений размером 1 Мб становится миллионномерным пространством векторов. При помощи такой модификации Шамир и его коллеги доказали гораздо более существенное. Если дано изображение в одном из сегментов, выделенных гиперплоскостями, и второй сегмент, то сколько бит нужно поменять в изображении, чтобы переместить его во второй сегмент? Их анализ показывает, что, например, если пространство образа разделено на миллион сегментов при помощи 20 гиперплоскостей, то достаточно изменить всего лишь две координаты для перемещения заданной точки в любой сегмент при условии, что размерность пространства образа превышает 250. В общем случае, если нейросеть обучена различать заданное число категорий, то число координат, которые необходимо изменить, чтобы переместить заданное изображение в любую категорию, примерно соответствует числу категорий.

Исследователи проверили эту теорему на коммерческой системе распознавания чисел. В ней всего 10 категорий – это цифры от 0 до 9. Они сгенерировали несколько состязательных изображений, способных убедить систему принять за цифру 7 любую из 10 возможных цифр. Чтобы этого добиться, достаточно поменять всего 11 бит. То же относится и к остальным цифрам, отличным от 7.

Следует ли нам беспокоиться по этому поводу? «Естественные» образы того типа, с которым беспилотный автомобиль будет обычно встречаться, не нацелены специально на обман системы. Однако автомобилю придется распознавать порядка полумиллиона изображений в день, а чтобы вызвать ДТП, достаточно одной неверной интерпретации. Главная угроза здесь в том, что вандалы или террористы могут без труда изменить дорожные знаки, добавив к ним маленькие кусочки черной или белой изоленты, и заставить компьютер поверить, что знак STOP – это на самом деле ограничение скорости 90 км/ч. Все это лишь усиливает тревожное ощущение, что беспилотные автомобили внедряются с излишней поспешностью из-за коммерческих интересов. Если вы с этим не согласны, повторю: мы никогда не стали бы внедрять новое лекарство или медицинскую процедуру с такой небрежностью. Особенно если есть серьезные основания подозревать, что это лекарство или процедура могут оказаться опасными.

Не позволяйте автобусу управлять самим собой.