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

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

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

* * *

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

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

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

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

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

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

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

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

* * *

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

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

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

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

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

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

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

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

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

x = 0, x₁x₂x₃x₄…

y = 0, y₁y₂y₃y₄…

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

0, x₁y₁x₂y₂x₃y₃x₄y₄…,

образовав ее путем перемешивания десятичных знаков первых двух чисел, как при тасовке карт методом «рифл шафл», когда колоду делят на две части, а затем вставляют их друг в друга{24}24
  Здесь необходима тщательность, поскольку некоторые действительные числа не имеют единственного десятичного представления, например 0,500000… = 0,499999… Но с этим несложно разобраться.


[Закрыть]. Разница состоит в том, что колода карт у Кантора бесконечна. Когда вы перемешиваете таким образом две бесконечные колоды, то получаете одну бесконечную колоду. Именно таким способом Кантор умудряется втиснуть две координаты в одну. Если первоначально измерения три, просто берется три колоды и т. д.

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

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

* * *

В 1879 году Ойген Нетто{25}25
  E. Netto. «Beitrag zur Mannigfaltigkeitslehre», Journal für die Reine und Angewandte Mathematik 86 (1879) 263–268.


[Закрыть] ответил на один очевидный вопрос, доказав отсутствие непрерывного взаимно однозначного соответствия между единичным отрезком и заполненным единичным квадратом. Это сложнее, чем может показаться. Самый значительный прорыв произошел в 1890 году, когда Пеано показал, что наше интуитивное представление о непрерывной кривой может быть обманчивым.

В статье Пеано никаких рисунков нет. Он определяет кривую, записывая координаты точек единичного отрезка в троичной системе счисления, и его построение эквивалентно геометрическому построению на рисунке слева ниже{26}26
  H. Sagan. «Some reflections on the emergence of space-filling curves: the way it could have happened and should have happened, but did not happen», Journal of the Franklin Institute 328 (1991) 419–430. Объяснение см. в: A. Jaffer. «Peano space-filling curves», http://people.csail.mit.edu/jaffer/Geometry/PSFC.


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

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

Заполняющие пространство кривые применяются в компьютерных вычислениях, в частности при хранении и считывании многомерных данных{27}27
  J. Lawder. «The application of space-filling curves to the storage and retrieval of multi-dimensional data», PhD Thesis, Birkbeck College, London (1999).


[Закрыть]. Базовая идея состоит в том, что мы можем обходить многомерный массив по приближенной заполняющей пространство кривой, упрощая таким образом задачу и сводя ее к одномерному случаю. Еще одно практическое применение – это быстрое и приблизительное решение задачи коммивояжера. Идея заключается в наложении конечной аппроксимации заполняющей пространство кривой на область с городами, определении последовательности городов на кривой, а затем в посещении их в этом порядке, пользуясь на каждом этапе кратчайшим связующим путем. В результате получается маршрут, который обычно не более чем на 25 % превышает по длине оптимальный{28}28
  J. Bartholdi. «Some combinatorial applications of spacefilling curves», www2.isye.gatech.edu/~jjb/research/mow/mow.html.


[Закрыть].

Какие еще фигуры может заполнить кривая? Построение Гильберта можно расширить на три измерения, получив кривую, заполняющую единичный куб, а вообще, кривые могут заполнять гиперкубы любой размерности. Последнее слово в этом вопросе – теорема, которую доказали Ханс Хан и Стефан Мазуркевич. Она полностью характеризует топологические пространства, которые может заполнить кривая{29}29
  H. Hahn. «Über die allgemeinste ebene Punktmenge, die stetiges Bild einer Strecke ist», Jahresbericht der Deutschen Mathematiker-Vereinigung, 23 (1914) 318–322. H. Hahn. «Mengentheoretische Charakterisierung der stetigen Kurven», Sitzungsberichte der Kaiserlichen Akademie der Wissenschaften, Wien 123 (1914) 2433–2489. S. Mazurkiewicz. «O aritmetzacji kontinuóv», Comptes Rendus de la Société Scientifique de Varsovie 6 (1913) 305–311 and 941–945.


[Закрыть]. Как оказалось, эти пространства могут быть практически любыми при условии, что они компактны (имеют конечную протяженность) и удовлетворяют нескольким формальным условиям, позволяющим исключить всякие глупости.

* * *

Возможно, последнее слово все еще остается за коммивояжером. В 1992 году Санджив Арора и его коллеги{30}30
  Опубликовано в 1998 году: S. Arora, M. Sudan, R. Motwani, C. Lund and M. Szegedy. «Proof verification and the hardness of approximation problems», Journal of the Association for Computing Machinery 45 (1998) 501–555.


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

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

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

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

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

Ласло Бабаи и другие ученые ввели методы «диалогового» доказательства такого типа в концепцию прозрачного доказательства, использовав при этом такие математические инструменты, как многочлены над конечными полями и корректирующие коды{31}31
  L. Babai. «Transparent proofs and limits to approximation», in: First European Congress of Mathematics. Progress in Mathematics 3 (eds. A. Joseph, F. Mignot, F. Murat, B. Prum and R. Rentschler) 31–91, Birkhäuser, Basel (1994).


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

* * *

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

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

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

* * *

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

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

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

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

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

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

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

Изображения такого рода называют «состязательными», поскольку они появляются, когда кто-то пытается намеренно обмануть систему. На практике компьютер воспримет большинство подобных изображений как кошку. Кристиан Сегеди с коллегами обратил внимание на существование таких изображений в 2013 году{32}32
  C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow and R. Fergus. «Intriguing properties of neural networks», arXiv:1312.6199 (2013).


[Закрыть]. В 2018 году Ади Шамир с коллегами{33}33
  A. Shamir, I. Safran, E. Ronen and O. Dunkelman. «A simple explanation for the existence of adversarial examples with small Hamming distance», arXiv:1901.10861v1 [cs.LG] (2019).


[Закрыть] объяснил, почему в системах глубокого обучения могут возникать состязательные примеры, почему они неизбежны и почему достаточно изменить всего несколько пикселей, чтобы ввести нейросеть в заблуждение.

Корень такой восприимчивости к серьезным ошибкам кроется в размерности. Обычный способ измерения различия между двумя битовыми строками состоит в том, чтобы найти расстояние Хэмминга между ними: определить, сколько бит следует заменить, чтобы из одной строки получить другую. Так, расстояние Хэмминга между 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 км/ч. Все это лишь усиливает тревожное ощущение, что беспилотные автомобили внедряются с излишней поспешностью из-за коммерческих интересов. Если вы с этим не согласны, повторю: мы никогда не стали бы внедрять новое лекарство или медицинскую процедуру с такой небрежностью. Особенно если есть серьезные основания подозревать, что это лекарство или процедура могут оказаться опасными.