Поэт вычислений, открывающий далекие истины

Теоретик информатики Константинос Даскалакис получил премию имени Рольфа Неванлинны за объяснение ключевых вопросов теории игр и машинного обучения. Комментарий Сохранить статью Прочитать позже

Введение

Прокрутите вниз веб-страницу Константиноса Даскалакиса — там есть ссылки на его теоретические труды по информатике и на статьи его докторантов в Массачусетском технологическом институте — и вы наткнетесь на скромное стихотворение из 21 строки Константина Кавафиса «Сатрапия».

Написанное в 1910 году, оно адресовано безымянному человеку, «созданному для прекрасных и великих дел», но столкнувшемуся с ограниченностью и равнодушием, отказавшемуся от своих мечтаний и отправившемуся ко двору персидского царя Артаксеркса. Царь щедро одаривает его сатрапиями (губернаторскими должностями), но душа его, пишет Кавафис, «тоскует по другому… о с трудом добытом и бесценном «Добром даре»; об Агоре, Театре и Лаврах» — обо всем том, чего Артаксеркс дать ему не может. «Где ты найдешь это в сатрапии, — спрашивает Кавафис, — и какая жизнь без этого?»

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

Решения, которые 37-летний Даскалакис принимал на протяжении своей карьеры — например, отказ от высокооплачиваемой работы сразу после колледжа и решение самых сложных задач в своей области, — все они были направлены на раскрытие далёких истин. «Всё это проистекает из глубочайшей потребности понять что-то», — сказал он. «Вы просто не остановитесь, пока не поймёте; ваш мозг не может оставаться спокойным, пока вы не поймёте».

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

«Я действительно не могу представить себе никого другого, кто был бы лидером и влиятельным лицом в стольких областях», — сказала Эва Тардос, специалист по информатике из Корнеллского университета. «Это удивительно и впечатляет».

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

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

«Это невероятно важное наследие, которое я несу», — сказал он. «Это вдохновляет, это вселяет чувство смирения, это большая ответственность, это вызов».

Закрывать

Отказ от сатрапии

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

Константинос (или «Костис», как его называют большинство) проводил там летние каникулы, проникаясь самобытной культурой острова. Критяне всегда были «смутьянами», когда у них отнимали свободу, сказал Даскалакис, — они яростно сопротивлялись оккупации Османской империи, а затем и нацистов.

Эти героические истории глубоко повлияли на юного Даскалакиса. «Дело не только в культурных сказаниях, но и в том, что я чувствовал её в самой атмосфере», — сказал он. «Гордые горы Крита… этот прекрасный цвет, море и пейзаж».

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

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

Дома братья брались за один проект за другим — копались в математических текстах отца, рисовали комиксы или пытались вывести законы движения планет Кеплера. Мягкий характер Даскалакиса сочетался с огромным желанием познать окружающий мир. Когда он учился в третьем классе, отец принёс домой ранний компьютер Amstrad, и Даскалакис не спал всю ночь, пытаясь разобраться, как он работает. «Я сказал родителям: „Знаю, что мне нужно идти спать, но это очень важно“», — сказал он. «Они разрешили мне не спать».

Когда Даскалакис учился в старших классах школы, а затем и в бакалавриате по электротехнике и вычислительной технике в Национальном техническом университете Афин, быстро стало ясно, что он — крайняя неординарность. Он получил высшие баллы по всем предметам бакалавриата, кроме одного, — достижение, невиданное ранее за почти 200-летнюю историю университета. «Каждый учитель, которого вы спросите о Костисе, будет помнить его, даже спустя 20 лет», — сказал Александрос Димакис из Техасского университета в Остине, который был однокурсником Даскалакиса и в бакалавриате, и в магистратуре.

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

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

Одна лекция теоретика информатики Христоса Пападимитриу произвела на него особенно глубокое впечатление. В ней, среди прочего, обсуждалась проблема вычисления равновесия Нэша, одной из центральных концепций теории игр и экономики. «Я и представить себе не мог, что это станет моей докторской диссертацией», — сказал Даскалакис.

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

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

Но хотя Нэш и смог доказать, что равновесие всегда существует, его доказательство не давало способа его найти. Для сложных игр поиск равновесия Нэша может оказаться невероятно сложной вычислительной задачей, и если равновесие Нэша невозможно вычислить для практических целей, имеет ли вообще смысл представлять, как игроки находят и используют его стратегии? «Если для решения [равновесия Нэша] требуется время существования Вселенной, нельзя утверждать, что оно у вас есть», — сказал Пападимитриу.

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

Пападимитриу изучал задачу вычисления равновесий Нэша два десятилетия, но так и не смог доказать эту гипотезу. «Честно говоря, в глубине души я не ожидал, что смогу её решить», — сказал он.

«Многие считали это самым большим открытым вопросом в алгоритмической теории игр», — сказал Тим Рафгарден, специалист по информатике из Стэнфордского университета.

Заворожённый лекцией Пападимитриу, Даскалакис в конце концов решил подать заявление в аспирантуру Калифорнийского университета в Беркли, где тогда работал Пападимитриу. Через несколько часов после того, как он опустил заявление в почтовый ящик, он столкнулся с Пападимитриу на улице в Афинах — они увиделись впервые после летних лекций полгода назад. «Это было настоящее безумие», — сказал Даскалакис. «Каковы шансы на это?»

Пара обменялись лишь кивком в знак приветствия, но, по словам Пападимитриу, это был «судьбоносный момент». «Мы посмотрели друг на друга, и, думаю, мы оба поняли, что его примут [в Беркли] и он станет моим консультантом».

«Я не уверен, что верю в знаки», — сказал Даскалакис. «Но это была очень важная встреча».

Закрывать

Закрывать

Неоценимо хорошо сделано

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

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

Димакис рассказал, что у Даскалакиса была неиссякаемая интеллектуальная энергия. Однажды, вспоминает Димакис, они поехали кататься на лыжах на озеро Тахо, и после этого Димакис настолько устал, что едва мог двигаться. Но Даскалакис задумался о какой-то проблеме и вскоре с энтузиазмом её обсудил, хотя была уже полночь. «Я подумал: „Блин, я просто выбился из сил“», — сказал Димакис.

За эти годы Пападимитриу пытался решить задачу о равновесии Нэша с несколькими своими самыми талантливыми учениками, но безуспешно. Даскалакис же с энтузиазмом взялся за дело. «Я искал что-то сложное», — сказал он.

Вскоре Пападимитриу почувствовал, что решение проблемы сдвинулось с мёртвой точки, чего не чувствовал уже много лет. «Это было так же невозможно, как и всегда, но у меня было ощущение, что мы натыкаемся на новые, а не на старые стены».

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

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

Трое исследователей надеялись, что их результат можно будет распространить на игру втроём, и Даскалакис взялся за задачу со свойственным ему энтузиазмом. Но это оказалось непросто, и однажды, хорошенько поразмыслив, Даскалакис почувствовал, что готов сдаться, по крайней мере, на время. Он включил ноутбук, чтобы проверить почту, но тот сломался. Пока Даскалакис ждал долгого сканирования жёсткого диска, он снова обратил внимание на задачу для трёх игроков — и в одно мгновение понял, как её решить. Оглядываясь назад, он понимает, что, должно быть, уже решил её где-то в недоступной части своего сознания. «Это было прямо у меня в голове, но я этого не осознавал».

Многие озарения Даскалакиса, похоже, приходят именно в такие лиминальные моменты — когда он просыпается утром, ждёт перезагрузки ноутбука, принимает душ или болеет с температурой. «Обычно хорошие идеи приходят ко мне, когда я страдаю от смены часовых поясов», — сказал он.

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

Решение Даскалакисом задачи о равновесии Нэша мгновенно принесло ему известность в сообществе теоретической информатики. А в 2008 году, когда он был удостоен премии Ассоциации вычислительной техники за докторскую диссертацию, эта слава дошла и до широкой греческой общественности. После того, как пост в блоге о его награде стал вирусным, президент Греции пригласил его в гости, а документальные фильмы о нём неоднократно транслировались по греческому телевидению.

«В Греции он практически рок-звезда», — сказал Рафгарден. Он вспоминает, как однажды сопровождал Даскалакиса в греческий ресторан в Бостоне, где выступали музыканты. Когда Даскалакис подошёл к ним после концерта, чтобы похвалить, один из музыкантов ответил, что ему было трудно сосредоточиться, когда Даскалакис был в зале. Как вспоминает Рафгарден, музыкант сказал: «Я пытаюсь сыграть песню, смотрю налево и думаю: „Боже мой, это же Костис Даскалакис“».

Нажимая кнопку просмотра этого видео, вы соглашаетесь с нашей политикой конфиденциальности.

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

Прекрасные и великие произведения

После триумфа в аспирантуре Даскалакис задавался вопросом, сможет ли он когда-нибудь снова заняться работой такого же уровня. «Кажется, у многих учёных есть один большой результат в карьере», — сказал он. «А это был мой результат?» Но он не испытывал никакого желания гнаться за славой. «У меня всё ещё были интересные проблемы», — сказал он. «Иногда ты просто продолжаешь работать над теми, которые важны для тебя».

Даскалакис вскоре стал профессором Массачусетского технологического института и начал консультировать своих аспирантов. Вайнберг, один из его первых студентов, вспоминает, как пришёл в кабинет Даскалакиса и предложил поработать над улучшением числовых множителей в только что прочитанной им статье. «Помню, он вежливо сказал: „Хорошо, это хорошо, но, думаю, нам стоит быть немного более амбициозными“», — сказал Вайнберг.

В данном случае это означало решение проблемы, которая практически не решалась в течение 30 лет. В 1981 году Роджер Майерсон, экономист, ныне работающий в Чикагском университете, решил задачу: как организовать аукцион одного товара, чтобы максимизировать доход продавца, что принесло ему Нобелевскую премию по экономике.

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

Затем, в 2012 году, Даскалакис и Вайнберг совместно с другим учеником Даскалакиса, Янгом Каем, разработали алгоритм, способный эффективно находить оптимальную схему аукциона независимо от количества продаваемых товаров. В течение следующих нескольких лет Даскалакис и двое его аспирантов, Алан Декельбаум и Христос Цамос, развили этот анализ в случае, когда есть только один покупатель (например, человек, выбирающий между различными пакетами услуг сотовой связи). В этом случае Даскалакис и его ученики смогли охарактеризовать для любого механизма продажи точные условия, при которых этот механизм будет оптимальным.

«Многие экономисты работали над этой проблемой, — сказал Дирк Бергеманн, экономист Йельского университета. — Все они были весьма впечатлены этими результатами».

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

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

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

По словам Костиса, у братьев разные области знаний. По его словам, успех нашего сотрудничества обусловлен тем, что «мы оба очень заинтересованы в объединении наших двух областей».

Заботясь о студентах, посещая конференции и навещая родственников в Греции, Даскалакис почти не находит свободного времени. Во время интервью журналу Quanta Magazine в Северо-Западном университете, где он проходил двухмесячный семинар, каждый раз, когда появлялся перерыв, он хватался за мобильный телефон, чтобы позвонить одному из своих аспирантов. Даскалакис и его студенты готовили семь статей к дедлайну конференции, который должен был состояться на той неделе, и его невеста, Александра Куркулас, аспирантка факультета истории искусств Массачусетского технологического института, предсказала, что его ждёт ещё одна бессонная ночь.

Это насыщенная жизнь, но Даскалакис ни на что её не променяет. «В конечном счёте, всё сводится к искреннему интересу к происходящему и нежеланию думать об этом как о бремени», — сказал он.

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

Исправление: Статья была пересмотрена 9 августа 2018 года с целью отразить тот факт, что отец Даскалакиса принес домой ранний компьютер Amstrad, когда Даскалакис учился в третьем классе, а не в восьмом.

Источник: www.quantamagazine.org